Hạ tầng tìm kiếm

Bài toán

Lúc đầu, tìm kiếm là LIKE trên database hoặc một thư viện (Lucene) nhúng trong app. Khi dữ liệu và tính năng tăng, search thành một hệ có trạng thái riêng, khác database ở mấy điểm:

• Index là dữ liệu dẫn xuất (từ database, từ repo): phải dựng, cập nhật, và dựng lại được khi đổi schema hay khi hỏng.
• Index có thể lớn ngang dữ liệu gốc (NGram, soft delete, replica) và đắt.
• Mỗi query fan-out tới mọi shard; query nặng (aggregation, cardinality cao) đủ để làm nóng cả cụm.
• Nhiều tính năng cần search (typeahead, tìm theo quan hệ, theo vertical), dễ dẫn tới nhiều backend riêng, rồi phải gom lại.

Trang này nói về hạ tầng (index, cập nhật, phân phối, HA, vận hành cụm search). Relevance và ranking bằng ML nằm ngoài phạm vi wiki.

Diễn tiến theo thời gian

• 2009→2013 · Facebook: nhiều backend search chồng nhau (PPS theo từ khoá, Typeahead 2010 với index giới hạn, backend riêng cho Nearby và tag). Unicorn (inverted index trong bộ nhớ, từ 2009) được mở rộng thành search engine năm 2011 và mọi backend cũ chuyển sang trước khi ra Graph Search. Cạnh đồ thị là "từ khoá" (friend:<id>), có toán tử apply cho truy vấn nhiều bước nhảy; posting list sắp theo static rank; index dựng bằng MapReduce từ Hive cộng pipeline cập nhật trực tuyến trong vài giây. Meta 2013
• 2013→2014 · LinkedIn: Lucene được đắp thêm Sensei, Search Content Store, Zoie và nhiều thành phần nhỏ, đến mức không dựng lại được index và không ai sở hữu trọn. Galene giữ Lucene làm tầng index, bỏ hết phần còn lại: index dựng offline trên Hadoop hằng tuần, bất biến, cộng buffer cập nhật trong bộ nhớ và snapshot vài giờ một lần do indexer riêng gộp; phân phối index bằng BitTorrent; Federator/Broker/Searcher với plugin rewriter và scorer. Typeahead nhanh gấp đôi với một phần ba phần cứng (theo LinkedIn). LinkedIn 2014
• 2015→2018 · LinkedIn: ba mid-tier federation (search, typeahead...) có logic gần giống nhau được gộp về một, mỗi vertical là một workflow ghép từ operator dùng chung; QPS của mid-tier từ 16K xuống 8K. LinkedIn 2018
• 2015 · Instagram: đầu 2015 chuyển toàn bộ search từ Elasticsearch sang Unicorn của Facebook. Dữ liệu vào bằng sự kiện Thrift denormalize qua Firehose (best-effort, chấp nhận mất ít) cộng base build dựng lại từ snapshot Postgres trong Hive rồi gộp với luồng sự kiện. Media search là hạ tầng thuần, không có query của user: Explore, trang hashtag, posting list sắp theo thời gian ngược, WEAK AND để đảm bảo đa dạng. Instagram 2015
• 2016 · Airbnb: Search indexing làm lại trên Nebula: index sinh offline từ snapshot hằng ngày, chia shard sẵn, deploy như binary; rollback index nhanh, máy search mới chỉ cần tải index. Airbnb 2016
• 2018 · Zillow: index Elasticsearch lệch DB do job index chạy từ after_save (trước commit) và đọc replica trễ; sửa sang after_commit, đọc master, thêm job đối chiếu. Zillow 2018
• 2019 · GitLab: muốn bật Elasticsearch cho GitLab.com nhưng index tốn khoảng 66% dung lượng repo; forcemerge để lấy lại chỗ soft delete làm sụt hiệu năng nên bỏ; tách index không bớt chỗ nhưng index nhanh hơn. Chuyển sang index chọn lọc theo group/project và dogfood: bật cho gitlab-org (2,2 triệu document, 15 GB) ngày 24/6/2019 sau một production readiness review; tự động backfill khi thêm group; đổi schema vẫn phải re-index tất cả. GitLab 2019 GitLab 2019
• 2019 · Tinder: hàm relevance bằng Painless chạm giới hạn 16.384 ký tự và chậm; plugin Java thì mỗi lần cập nhật phải restart cụm. Viết script plugin nạp jar lúc chạy (ClassLoader riêng, cache theo tên + phiên bản), phát hành qua staging → cụm canary chép dữ liệu production → dark run → tăng dần. Sau đó đẩy danh sách bỏ qua (thay terms query lớn) thành RoaringBitmap giải nén trên data node: latency giảm khoảng 80%, CPU giảm 35–50%. Tinder 2019 Tinder 2019
• 2019 · Grab: ELK cho log ở quy mô PB: tách vai node, hạ giới hạn field data, tính shard theo segment memory (khoảng 8 TB shard cho heap 32 GB), sửa mapping và analyzer (bớt 1 GB index memory, tương đương 8 node). Grab 2019
• 2020 · Stack Overflow: Articles là một loại Post và "loại article" là tag đặc biệt, nên không phải thêm field vào index Elasticsearch: đổi cấu trúc document nghĩa là rebuild index trên mọi site và mọi Team, vì Teams và site công khai chung code. Stack Overflow 2020
• 2021→2022 · Grab: search chỉ khớp văn bản, trộn kết quả nhiều vertical ở tầng API phía sau. Làm lại thành boosting → multi-recall → ranking, trộn vertical trong search; framework của nền tảng cộng plugin của team service. Grab 2022
• 2021 · Mozilla: autocomplete của MDN chạy hoàn toàn ở trình duyệt: 11.690 tiêu đề nén Brotli còn khoảng 144 KB, chỉ tải khi ô search được focus/hover; thứ tự mảng (sắp sẵn theo pageview lúc build) là xếp hạng. Lý do thêm: phải chạy cả trên bản preview tĩnh không có server. Mozilla 2021
• 2021 · Dropbox: search ảnh chạy trên chính search engine Nautilus: forward index lưu vector thưa của ảnh, inverted index một posting list mỗi lớp; nhờ latency ngang search văn bản, hai loại search chạy song song rồi gộp. Dropbox 2021
• 2022 · Instacart: thêm nguồn ứng viên thứ ba (embedding-based retrieval qua ANN/FAISS) cạnh retrieval theo keyword và danh mục; index rebuild hằng ngày từ job offline, embedding query của các query phổ biến lấy sẵn từ feature store Instacart 2022
• 2022 · DoorDash: search đồ ăn mở sang tạp hoá, rượu...: indexing thế hệ mới (materialized view trước khi index, đường tăng dần cho cập nhật ưu tiên cao để không kẹt sau rebuild, control plane chuyển index cũ/mới), federate-then-blend theo ngành (SLA riêng, lỗi một ngành không sập toàn bộ), thử rời Elasticsearch bản host sang Lucene tự vận hành vì cần logic sát storage và vì chi phí. DoorDash 2022
• 2022 · Zillow: gợi ý chuyển từ batch sang realtime: Elasticsearch sinh 100 ứng viên từ khoảng 1,3 triệu listing với điểm theo hồ sơ người dùng; đổi fetch từ _source sang doc values giảm CPU service 38,7% và p99 25,6%. Zillow 2022
• 2023 · GitHub: search của GitHub Docs rời index trong bộ nhớ tiến trình Node.js (index serialize lưu trong repo) sang Elasticsearch khi nhân 8 ngôn ngữ × 5 phiên bản; một query duy nhất với ma trận boost (mỗi trường index hai lần, có và không stemming) cộng độ phổ biến từ pageview; query chạy khoảng 20 ms. GitHub 2023
• 2023 · eBay: engine tìm theo vector cho gợi ý và listing tương tự: shard là đơn vị scale, số shard tự chọn theo kích thước embedding và chia lại nền với ít dữ liệu di chuyển nhất; mỗi shard nhân bản trên nhiều query node ở nhiều cluster; gateway gửi query tới mọi shard rồi gộp theo khoảng cách. eBay 2023
• 2024 · Zalando: cụm Elasticsearch trên Kubernetes scale theo lịch kẹt ở 7 node vì zone awareness không cho dời shard khỏi node duy nhất ở một AZ, cộng bug operator không bỏ việc dở và để lại node "zombie" trong danh sách loại trừ. Zalando 2024
• 2025 · Zalando: một ứng dụng nội bộ gửi query facet aggregation trên trường cardinality cao (chỉ 20–100 request/giây) giữ cụm nóng và bỏ đói traffic thường; cô lập theo nhóm thị trường giới hạn được phạm vi. Khắc phục: rate limit theo loại client, X-Opaque-Id cho slow log, giới hạn bucket. Zalando 2025
• 2025 · Cockroach Labs (nhà cung cấp): vector index trong DB phân tán: cây K-means rộng và nông (10 tỉ vector chỉ 5 tầng), partition là dải hàng trong range nên split/rebalance như dữ liệu thường, tự tách/gộp/dời vector khi dữ liệu đổi, RaBitQ nén 94% + rerank, mỗi tenant một cây. Cockroach Labs 2025
• 2025 · Mercari: search cho Global App (4 tỉ listing tích luỹ, 50 nước trong 3 năm): chọn Vertex AI Search for Commerce (managed, tính theo request, đa ngôn ngữ, nhận product model có biến thể) để ra nhanh dù A/B test kém search Nhật, với kế hoạch chuyển về Elasticsearch khi traffic lớn tới mức không còn lời; backend mới có plugin móc tiền/hậu xử lý query thay cho if rải rác, tách trừu tượng khỏi engine. Nền tảng EaaS (Elasticsearch trên ECK) chỉ cấp engine nên tính năng search của Nhật không dùng lại được; dựng thêm một lớp tính năng dùng chung trên EaaS. Mercari 2025
• 2026 · Atlassian: hơn 300 cụm OpenSearch, 1,7 PB, index chính là sản phẩm nên không dựng lại offline được. Plugin AOSC đổi hình index online theo mẫu database: copy ban đầu + phát lại thay đổi theo sequence number (retention lease) + chặn ghi vài giây + đổi alias; chạy chậm, đều, có giới hạn để không làm hại cụm đang phục vụ. Atlassian 2026
• 2026 · GitHub: trong bản tự host, một cụm Elasticsearch trải cả primary lẫn replica tạo phụ thuộc vòng khi bảo trì; chuyển sang mỗi node một cụm một node và Cross Cluster Replication để khớp mô hình leader/follower của hệ chứa nó. GitHub 2026
• 2026 · PlanetScale (nhà cung cấp): giải phẫu inverted index (term dictionary, postings nén delta/bitmap, BM25, top-k bỏ khối, segment/merge/tombstone) và cái giá khi nhúng vào Postgres: index có WAL, tự giữ danh sách trang trống, merge ở worker nền, VACUUM đổi ctid, top-k vẫn phải trả đủ k dòng thấy được theo MVCC. PlanetScale 2026
• 2026 · Upstash (nhà cung cấp): Redis Search index theo key prefix ngay trong DB: tài liệu ghi vào queue trên đĩa trước khi trả lời lệnh Redis, Tantivy (fork, writer foreground cho multi-tenant) ghi segment lên kho KV nhân bản toàn cầu (trang 8 KB mỗi key); crash thì phát lại queue từ lần commit cuối. Upstash 2026
• 2026 · Elastic, Qdrant (nhà cung cấp): vector search có filter trong engine search: Elastic tự chọn lọc trước/sau theo độ chọn lọc ước tính, Qdrant vá đồ thị HNSW bằng cạnh thêm lúc dựng và ACORN lúc tìm. Chi tiết ở Vector search và index ANN. Elastic 2026 Qdrant 2026
• 2026 · Uber: index Lucene Plus riêng cho nhà hàng và grocery, làm mới đồng bộ với model hai tuần một lần bằng snapshot mới không đụng đường đọc; blue/green bằng hai cột embedding trong một index thay vì hai index (rẻ hơn, cần cổng mạnh hơn). Uber 2026
• 2026 · Uber: gRPC native cho OpenSearch, làm upstream thay vì giữ adaptor Protobuf ↔ JSON trong Search Gateway: Bulk của M3 p99 34,1 → 13,6 ms, vector search grocery p50 83 → 38 ms; Protobuf và REST giữ đồng bộ bằng pipeline sinh từ OpenAPI có kiểm tương thích wire. Uber 2026
• 2026 · Uber: latency search Uber Eats giảm một nửa: đo ATF (màn hình đầu hiện xong) thay latency API; bỏ chiến lược retrieval ít đóng góp (−120 ms); tách hydration cho ranking khỏi hydration cho hiển thị (hơn −100 ms); bỏ phụ thuộc giả trong DAG; hedging ở bốn tầng hydration (−40 ms); dữ liệu quảng cáo dạng cột trong bộ nhớ (khoảng −130 ms). Tiếp theo: microbatching, search theo sản phẩm, lọc ngay ở index. Uber 2026

Các lựa chọn và đánh đổi

Quy tắc rút ra

1. Khi nhiều tính năng cần search, gom về một hạ tầng index chung có plugin, thay vì mỗi tính năng một backend; làm nền trước rồi chuyển hệ cũ sang trước khi ra tính năng mới. Meta 2013 LinkedIn 2014 LinkedIn 2018
2. Thiết kế để dựng lại toàn bộ index là chuyện thường (index offline bất biến + lớp cập nhật nhỏ); nếu index là dữ liệu sống không dựng lại được, cần cơ chế đổi hình online kiểu CDC. LinkedIn 2014 Atlassian 2026
3. Việc tốn kém của index (gộp segment, snapshot, migration) chạy ở máy hay luồng không phục vụ query, hoặc chạy chậm và có giới hạn. LinkedIn 2014 Atlassian 2026
4. Kích thước index là chi phí hạng nhất: NGram, soft delete, replica có thể đưa nó lên ngang dữ liệu gốc. GitLab 2019
5. Bật search trên instance lớn bằng phạm vi chọn lọc, mở rộng dần, tự dogfood, và tự động backfill theo vòng đời dữ liệu nguồn. GitLab 2019
6. Một loại query nặng đủ làm nóng cả cụm dù lượng nhỏ; cần định danh client trong slow log, rate limit theo loại client, và giới hạn aggregation. Zalando 2025
7. Mô hình HA và tự động hoá của cụm search phải khớp với hệ chứa nó và với ràng buộc an toàn của chính nó (zone awareness). GitHub 2026 Zalando 2024
8. Static rank sắp posting list theo độ quan trọng để dừng sớm, dành CPU cho scorer. Meta 2013 LinkedIn 2014 Instagram 2015
9. Bắt đầu ở mức nhỏ nhất đủ dùng: dữ liệu vài chục nghìn mục có thể search ngay trên client hay trong bộ nhớ; chuyển sang cụm riêng khi dữ liệu nhân theo nhiều chiều. Mozilla 2021 GitHub 2023
10. Index dẫn xuất không cần luồng cập nhật hoàn hảo nếu có dựng lại định kỳ từ snapshot nguồn để sửa phần mất. Instagram 2015 LinkedIn 2014
11. Code chạy trong cụm search cần đường phát hành không restart cụm và các tầng kiểm như service (canary trên dữ liệu thật, dark run); tìm nút cổ chai bằng cách bỏ từng phần của query rồi đo. Tinder 2019 Tinder 2019
12. Index dẫn xuất cập nhật bất đồng bộ cần phát sau commit và job đối chiếu định kỳ: job phát trước commit hoặc đọc replica trễ sẽ ghi dữ liệu cũ vào index (Zillow 2018). Zillow 2018
13. Search nhúng trong DB (Postgres extension, Redis Search) bỏ được việc đồng bộ hai hệ, nhưng gánh mọi đòi hỏi của DB đó (WAL, MVCC, VACUUM, multi-tenant) cộng chi phí segment/merge chạy ngoài đường ghi (theo PlanetScale, Upstash 2026). PlanetScale 2026 Upstash 2026
14. Ghi việc index vào log bền trước khi trả lời, index bất đồng bộ, giữ log tới khi segment đã commit; phục hồi bằng phát lại thay vì phân tích từng trường hợp ghi dở. Upstash 2026

Câu hỏi mở

• Chưa có nguồn kể chi phí vận hành search theo thời gian (tỉ lệ hạ tầng search trên tổng) hay so sánh tự vận hành Elasticsearch/OpenSearch với dịch vụ managed.
• Search vector (embedding) đã có trang riêng từ đợt 33: Vector search và index ANN (Cockroach 2025, Memgraph, Qdrant, Elastic 2026, đều là nhà cung cấp).
• Ranh giới hạ tầng/relevance: GitHub Docs 2023 và Tinder 2019 cho thấy chỉnh xếp hạng (boost, script) chạm thẳng vào hạ tầng (số query, plugin); wiki chỉ giữ phần hạ tầng.
• GitLab 2019 nói muốn quản lý thay đổi index "như migration database" nhưng chưa có bài tiếp kể kết quả.
• Managed hay tự vận hành: Mercari 2025 chọn Vertex AI Search for Commerce để ra nhanh dù kết quả A/B kém, kèm điều kiện quay về Elasticsearch khi traffic lớn (Mercari 2025); chưa có bài kể lần chuyển đó và ngưỡng chi phí thật.
• Liên hệ: Vector search và index ANN (index ANN, filter), Migration không downtime (đổi hình index online), Sharding và tách database (shard index, tenant lớn), Load shedding, rate limit và backpressure (cắt tải khi cụm nóng), Failover, replica và dự phòng dữ liệu (replication của cụm search), Chi phí hạ tầng và build vs buy (kích thước index).