FollowFeed: LinkedIn's Feed Made Faster and Smarter

LinkedIn · 2016 · 3. Quy mô lớn · Độ khó: Khó — bài gốc

Bối cảnh

• Mọi trải nghiệm feed của LinkedIn chạy trên một hạ tầng chung. Trước đó là Sensei: hệ search phân tán trên Lucene, query viết bằng BQL gồm cả lọc lẫn relevance, broker fan-out tới mọi searcher node rồi gộp top N.
• Lý do thay Sensei (theo LinkedIn): phải giữ toàn bộ inverted index trong RAM nên chi phí phần cứng tăng theo nội dung; ghép từ nhiều thành phần (Bobo, Norbert, Zoie) lệch với stack chung; Galene đã thay Sensei cho search nên chỉ còn feed dùng; code đầy "performance hack".
• Số member tăng từ 200 triệu lên hơn 400 triệu trong ba năm (2013→2015), đồ thị dày hơn nên một bài được phân phối tới nhiều người hơn; ranking ngày càng tốn tính toán.

Thay đổi chính

• Timeline: danh sách bản ghi theo thời gian giảm dần của một entity (member, công ty, trường). Key = (entity id, content type). Feed của viewer được dựng lúc đọc bằng cách gộp timeline của các entity họ quan tâm.
• Fan-out-on-read, không pre-materialize: thử nghiệm cho thấy fan-out-on-write làm dữ liệu lớn gấp 62 lần; feed dựng sẵn phải lưu theo thứ tự của model relevance, nên đổi model hay A/B test là phải sắp lại mọi feed. Tính điểm lúc query thì đổi model tức thì.
• Đưa tính toán tới dữ liệu: index node vừa lưu timeline vừa lọc và chấm điểm relevance tại chỗ, chỉ trả top N về broker.
• Over-partition: 720 partition (chia hết cho nhiều số) để cụm có thể là 40, 45, 60, 80, 360 máy; rebalance bằng cách di chuyển nguyên partition, không tách.
• Lưu trữ: RocksDB (LinkedIn viết JNI binding và đóng góp lại). Timeline là danh sách liên kết các blob có kích thước giới hạn; chèn = tìm nhị phân blob theo metadata rồi read-update-write; blob vượt ngưỡng thì tách.
• Cache: Guava cache bản ghi đã deserialize (deserialize là nút cổ chai), chia nhiều sub-cache để giảm tranh chấp; hai cache "fat" (key có bản ghi, giới hạn theo số bản ghi) và "skinny" (key rỗng, giới hạn theo số key).
• Schema registry Avro lưu ngay trong RocksDB của từng node.
• Relevance: sinh code Java tối ưu từ cấu hình transform + hồi quy, nhanh hơn thư viện chấm điểm cũ 15 lần (khoảng 50 µs p99 mỗi bản ghi cho feed mobile).
• Ingest bất đồng bộ qua Kafka: service Partitioner đọc stream mọi nội dung rồi ghi lại sang topic có partition khớp partition của index node; cùng một hàm partition dùng cho cả ghi lẫn định tuyến query. Thêm replica = cho thêm node đọc cùng partition Kafka.
• Broker nhận từ mid-tier danh sách entity, lọc, số lượng; đổi thành timeline key, tra partition → node qua D2 (ZooKeeper), fan-out, rồi khử trùng lặp, đa dạng hoá, sắp lại. Replica master-master, đều phục vụ đọc.
• Multi-DC: viewer được sticky-route tới một DC; mọi DC giữ timeline của mọi entity, ingest từ Kafka aggregate. Cỡ cụm mỗi DC theo phần traffic đọc của DC đó.
• Vận hành từ đầu: backup gia tăng lên NAS kèm offset Kafka để khôi phục; node riêng chỉ ingest và backup, không phục vụ traffic; broker gửi request trùng tới 1–3 replica có timeout xen giữa, nhận cái về trước; D2 giảm tải node quá tải; bật TRACE log theo từng viewer bằng dynamic config.

Vì sao

• Feed cần chấm hàng chục nghìn bản ghi mỗi request; kéo dữ liệu qua mạng về chỗ tính là quá chậm, nên tính ngay chỗ dữ liệu nằm.
• Theo LinkedIn, tốc độ thử model relevance quan trọng hơn chi phí đọc, nên chọn fan-out-on-read.

Kết quả (2016)

• p99 feed mobile khoảng 140 ms, nhanh gấp 5 lần Sensei; p90 tải trang giảm 150 ms.
• Chứa dữ liệu gấp khoảng 20 lần; capex giảm 50%, số server giảm một nửa.

Bài học cho SWE

• Chọn fan-out-on-read hay on-write không chỉ là bài toán đọc/ghi: nếu thứ tự feed phụ thuộc model hay đổi, materialize sẵn sẽ khoá tốc độ thử nghiệm.
• Dùng cùng một hàm partition cho đường ghi (Kafka) và đường đọc (broker) thì không cần lớp định tuyến riêng.
• Over-partition từ đầu để rebalance chỉ là di chuyển partition.
• Scatter-gather chịu tail latency của node chậm nhất: hedged request và giảm tải ở client là phần của thiết kế, không phải tối ưu sau.

Liên quan

• Chi phí hạ tầng và build vs buy
• LinkedIn 2018 (hai năm sau, chính cơ chế retry này suýt gây death spiral) · LinkedIn 2019 · LinkedIn 2017 · LinkedIn 2014 · LinkedIn 2015
• Realtime và fan-out · Sharding và tách database · Cache và invalidation · Nền tảng ML (feature, training, serving, giám sát model)