Under the Hood: Building out the infrastructure for Graph Search

Meta · 2013 · 3. Quy mô lớn · Độ khó: Trung bình — bài gốc

Bối cảnh

Facebook có nhiều hệ search cũ chồng nhau: PPS (theo từ khoá, cá nhân hoá, lọc theo loại entity); Typeahead (2009–2010, tìm theo tiền tố khi gõ, viết lại toàn bộ backend và frontend để đạt hiệu năng, nhưng index bị giới hạn nên khi người dùng muốn thêm kết quả lại chuyển sang PPS); và các tính năng khác (Nearby, tag trong post, tag địa điểm) với backend riêng.
Graph Search muốn tìm theo quan hệ giữa entity (cạnh của đồ thị), bằng câu tự nhiên: "nhà hàng ở San Francisco được người tốt nghiệp trường X thích". Việc này cần index rất lớn, ví dụ phải index từng check-in thay vì chỉ gộp làm tín hiệu xếp hạng. Đồng thời team đã quá tải vì duy trì nhiều backend search.

Dùng Unicorn, hệ inverted index phát triển trong Facebook từ 2009 (cuối 2010 đã dùng như một "database" trong bộ nhớ để tra entity theo tổ hợp thuộc tính). Năm 2011 quyết định mở rộng Unicorn thành search engine và chuyển mọi backend search cũ sang như bước đầu của Graph Search.
Index là ánh xạ thuộc tính → entity, trong đó thuộc tính có thể là cạnh: friend:<id>, lives-in:<id>, like:<id>; hỏi "bạn của David" giống hỏi một từ khoá. Hỗ trợ AND, OR, và toán tử apply cho truy vấn nhiều bước nhảy (lấy kết quả bước một làm đầu vào bước hai, ví dụ "nơi làm việc của bạn tôi sống ở New York").
Posting list sắp theo static rank (độ quan trọng không phụ thuộc query) và truy vấn kèm giới hạn số kết quả, để chỉ lấy phần quan trọng nhất.
Dựng index bằng MapReduce từ bảng Hive, cộng pipeline cập nhật trực tuyến riêng đưa thay đổi vào index trong vài giây (Facebook 2013: hơn 2,5 tỉ nội dung mới và 2,7 tỉ lượt like mỗi ngày).
Kết quả: một hệ thống nhất index toàn bộ đồ thị.

Tính năng mới cần index lớn hơn mọi backend cũ; đồng thời nhiều backend riêng làm chậm phát triển. Một lần làm lại giải quyết cả hai.

Gom nhiều backend search theo tính năng về một hạ tầng index chung khi tính năng mới vượt sức tất cả (Hạ tầng tìm kiếm).
Chuẩn bị nền trước (Unicorn dùng nội bộ từ 2009) rồi chuyển các hệ cũ sang trước khi ra tính năng mới, thay vì vừa chuyển vừa ra (Migration không downtime).
Inverted index không chỉ cho văn bản: coi cạnh đồ thị là "từ khoá" biến truy vấn quan hệ thành phép giao/hợp posting list.
Index offline + cập nhật trực tuyến và static rank để dừng sớm: cùng khung với LinkedIn Galene một năm sau (LinkedIn 2014).