Geosharded Recommendations Part 1: Sharding Approach
Tinder · 2019 · 3. Quy mô lớn · Độ khó: Trung bình — bài gốc
Sheet trỏ tới phần 3 (consistency); wiki đọc phần 1 (cách chia shard). Phần 2: Tinder 2019; phần 3: Tinder 2019.
Bối cảnh
- Search là thành phần chính của hệ gợi ý realtime. Nhiều năm Tinder chạy một cluster Elasticsearch, một index, 5 shard mặc định, scale bằng thêm replica và máy mạnh hơn. Đến lúc dùng rất nhiều máy mạnh mà CPU vẫn cao và chi phí lớn.
- Gợi ý của Tinder theo vị trí, tối đa 100 dặm: user ở California không cần thấy user ở London. Test tải cho thấy hiệu năng tăng tuyến tính khi index nhỏ lại.
Thay đổi chính
-
Geoshard (shard theo vị trí địa lý) đặt trên Elasticsearch: user ở gần nhau nằm cùng một index nhỏ.
-
Cân bằng là cốt lõi. Chia lưới đều theo kinh/vĩ độ sai vì ô ngoài biển rỗng, ô châu Âu chứa nhiều thành phố lớn, và bản đồ méo gần cực. Họ định nghĩa load score (đơn giản nhất: số user duy nhất) và đo độ cân bằng bằng độ lệch chuẩn của load giữa các shard.
-
Số shard:
- quá nhỏ thì một query 100 dặm phải chạm hàng trăm shard (p90/p99 tệ);
- user di chuyển qua ranh giới phải dời giữa index, mà việc này không nguyên tử nên càng nhiều lần dời càng nhiều bất nhất tạm thời;
- khu vực rất đông (New York, London) có load cao dù diện tích nhỏ.
Test tải cho thấy 40–100 geoshard toàn cầu là cân bằng tốt nhất.
-
Google S2 (dựa trên đường Hilbert, giữ tính gần nhau về không gian; ô cùng cấp có diện tích gần như nhau, tốt hơn geohash): dùng cấp 7 (~45 dặm) hoặc 8 (~22,5 dặm). Thuật toán: đi dọc đường Hilbert, cộng dồn load của từng ô vào một "thùng" có sức chứa cố định, tràn thì sang shard mới. Thử mọi sức chứa và chọn cấu hình có độ lệch chuẩn nhỏ nhất. Kết quả là shard liền nhau về địa lý và rộng hơn ở vùng thưa. Ánh xạ ô S2 → shard lưu thành JSON (dùng token chuỗi vì ID dạng số khác nhau giữa các thư viện Java/Node/Go).
-
Dùng: khi index, vị trí → ô S2 → shard. Khi query, vòng tròn → các ô phủ nó → shard (ví dụ một query 100 dặm chỉ chạm 3/55 shard).
-
Reshard (khi cần): chạy song song hai bộ index với hai ánh xạ, reindex offline, rồi cắt sang. Họ chừa đủ chỗ để không cần làm trong vài năm.
Kết quả
Theo Tinder: index geoshard xử lý được gấp 20 lần lượng tính toán so với một index duy nhất.
Bài học cho SWE
- Chọn khoá shard theo mẫu truy vấn tự nhiên (ở đây là vị trí, có bán kính tối đa) để mỗi query chạm ít shard.
- Cân bằng theo tải, không theo diện tích hay số khoá: đo load score rồi tối ưu độ lệch chuẩn. Cùng bài toán skew với Uber subcluster (Uber 2026).
- Số shard là đánh đổi giữa fan-out của query và chi phí dời dữ liệu giữa shard.