Real-Time Indexing for Billions of Vectors: How we built fast, fresh vector indexing at scale in CockroachDB

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

Bài nhà cung cấp, giới thiệu tính năng còn ở dạng preview; không có số đo hiệu năng. Mọi nhận định ghi "theo Cockroach Labs".

Bối cảnh

• Search ngữ nghĩa quy về tìm vector gần nhau (embedding vài trăm tới vài nghìn chiều). Vector không có thứ tự tự nhiên nên index truyền thống không dùng được; ở quy mô lớn phải dùng index xấp xỉ (ANN).
• Theo Cockroach Labs, nhiều giải pháp giả định cả tập dữ liệu nằm trong RAM một máy (hoặc SSD cục bộ), không đa region, đòi ghi theo lô, trả kết quả cũ hoặc phải dựng lại định kỳ. DB phân tán giao dịch thì cần kết quả tươi.
• Ràng buộc kiến trúc cho index trong CockroachDB: không có điều phối trung tâm (node nào cũng đọc/ghi được); không có cấu trúc lớn trong RAM (trạng thái nằm ở storage, không phải "làm ấm" khi khởi động, quan trọng với serverless); ít round-trip mạng; ánh xạ tự nhiên vào range key-value để split, merge, rebalance như dữ liệu thường; không có điểm nóng; cập nhật tăng dần không chặn query.

Thay đổi chính

• C-SPANN (ghép ý từ SPANN, SPFresh của Microsoft và ScaNN của Google): cây K-means phân tầng; mỗi partition vài chục tới vài trăm vector, có centroid; centroid lại được gom thành tầng trên. Mỗi partition là một dải hàng liền nhau trong một range. Fanout khoảng 100 nên cây rộng và nông: 1 triệu vector cần 3 tầng, 10 tỉ vector chỉ 5 tầng, tức số round-trip nhỏ và đoán trước được. Partition dùng block cache của storage như dữ liệu thường.
• Giữ index khoẻ khi dữ liệu đổi: vector mới rải khắp partition nên không có range nóng. Partition quá to thì tách nền bằng K-means cân bằng; vector có thể phải dời sang partition có centroid gần hơn sau khi tách (ý từ SPFresh); partition quá nhỏ thì gộp. Theo họ, vì vậy gần như không cần dựng lại index sau khi nạp dữ liệu.
• Nén 94% bằng RaBitQ: mỗi chiều còn 1 bit (vector OpenAI 1.536 chiều từ khoảng 3 KB xuống khoảng 200 byte), lượng tử hoá tương đối với centroid của partition nên tách/gộp chỉ phải lượng tử lại cục bộ. Sai số bù bằng bước rerank: lấy dư ứng viên rồi đọc vector đầy đủ từ bảng để tính khoảng cách chính xác.
• Mỗi tenant một index: cột tiền tố (ví dụ user_id) làm index giữ một cây K-means riêng cho mỗi user; chi phí ghi/tìm tỉ lệ với số vector của user đó, không với tổng; các user ít tranh chấp nhau. Ghép với REGIONAL BY ROW để vector của user nằm ở region nhà.
• Chưa xong (25.2): gộp partition và dời vector chưa hoàn chỉnh; mới có khoảng cách Euclid; lọc bằng WHERE ngoài cột tiền tố chưa dùng được index.

Bài học cho SWE

• Đưa một loại index mới vào DB phân tán: thiết kế cho nó khớp đơn vị chia nhỏ sẵn có (range) để thừa hưởng split, rebalance, HA thay vì tự làm.
• Cây rộng và nông giữ số round-trip có trần khi dữ liệu lớn.
• Phần lớn query vector bị giới hạn theo chủ sở hữu; index theo tenant vừa nhanh vừa là ranh giới an toàn.

Liên quan

• Vector search và index ANN
• Multi-tenancy và cô lập tenant
• Cockroach Labs 2026 · Upstash 2026 · PlanetScale 2026 (search nhúng trong DB)
• Hạ tầng tìm kiếm · Hot partition và thundering herd