Lời mở đầu

Tiếp tục phần trước, phần này chúng ta tiếp tục đào bới mã nguồn của Qdrant xem có gì hay ho không ?

Ta sẽ tập trung vào package collection

Let go !

1. Probabilistic Undersampling (Lấy mẫu xác suất)

Bài toán: Trong kiến trúc phân tán của Qdrant, một Collection được phân mảnh vật lý thành nhiều Shard chạy trên các node khác nhau. Nhờ vào kỹ thuật Consistent Hashing (Auto-sharding), dữ liệu vector được phân phối hoàn toàn ngẫu nhiên và đồng đều trên các Shard này.

Khi người dùng thực hiện một truy vấn tìm kiếm Vector với tham số limit = N (ví dụ: tìm N = 1000 điểm có độ tương đồng cao nhất):

• Node điều phối gửi yêu cầu truy vấn đến tất cả $X$ Shard.
• Mỗi shard tìm kiếm và trả về đúng $N$ kết quả tốt nhất của riêng nó.
• Node điều phối nhận được tổng cộng $S \times N$ điểm, thực hiện gộp, sắp xếp lại và lọc ra đúng $N$ điểm tốt nhất toàn cục để trả về cho người dùng.

Vấn đề:

• Network Bandwidth: Nếu Collection có 10 shards và $N = 1000$, Node điều phối phải nhận về $10 \times 1000 = 10.000$ điểm kèm theo payloads và vectors. Điều này gây nghẽn băng thông mạng nghiêm trọng.
• Thời gian xử lý (CPU & Serialization): Việc mã hóa và giải mã 10.000 vector và payload từ các node tiêu tốn rất nhiều chu kỳ CPU của cả Shard lẫn Node điều phối.
• Tỉ lệ gạt bỏ cực cao: Thực tế, do dữ liệu được phân bố đều, mỗi shard chỉ đóng góp trung bình khoảng $N/S$ (tức là $1000/10 = 100$ điểm) vào danh sách Top-$N$ cuối cùng. Gần $90$ kết quả tải về từ các shard sẽ bị gạt bỏ trong quá trình gộp.

Ý tưởng:

Vì dữ liệu được phân tán hoàn toàn ngẫu nhiên và đồng đều trên các Shard, mỗi Shard trung bình chỉ đóng góp khoảng $1/10$ kết quả tốt nhất vào danh sách cuối cùng.

Vậy thay vì yêu cầu mỗi Shard trả về cả 1000 điểm, tại sao ta không chỉ yêu cầu mỗi Shard trả về một số lượng $k$ nhỏ hơn nhiều (ví dụ: $k = 171$)?

Nhưng chọn $k$ bằng bao nhiêu để không bị bỏ sót kết quả tốt? Đây là lúc toán học xác suất thống kê vào cuộc. Đội ngũ Qdrant đã áp dụng mô hình toán học để tính toán: Với số lượng Shard và giới hạn tìm kiếm hiện tại, số lượng điểm $k$ tối thiểu cần lấy từ mỗi Shard là bao nhiêu để đảm bảo tỷ lệ bỏ sót kết quả gần như bằng 0 (độ tin cậy đạt 99.9%)?

Triển khai: Để hiện thực hóa ý tưởng này mà không làm quá tải CPU khi tính toán, Qdrant triển khai dựa trên Phân phối Poisson với cách triển khai cực kỳ thông minh:

• Sử dụng Phân phối Poisson để tính trước: Phân phối Poisson là một công cụ toán học chuyên dùng để tính xác suất xảy ra của một sự kiện ngẫu nhiên. Qdrant dùng hàm Poisson PPF (Percent Point Function - hàm phân vị) để tính toán chính xác số lượng điểm $k$ cần thiết.
• Để tránh việc hệ thống phải tính toán các công thức lũy thừa, giai thừa phức tạp của Poisson khi đang chạy, Qdrant đã tính toán sẵn một bảng tra cứu tĩnh chứa các cặp giá trị kỳ vọng và số lượng mẫu $k$ tương ứng.
• Tra cứu siêu tốc bằng Tìm kiếm Nhị phân (Binary Search)
• Cơ chế tự kiểm tra lỗi: Sau khi gộp kết quả, Node điều phối sẽ chạy thuật toán tự đối chiếu điểm số để so sánh điểm số của phần tử cuối cùng trong nhóm gộp với các điểm trả về từ các shard. Nếu phát hiện rủi ro có điểm tốt hơn bị bỏ sót, hệ thống sẽ ghi log debug để các kỹ sư theo dõi độ chính xác của phân phối xác suất.

Ơ đây là xác suất không may rơi vào trường hợp bị sót mất dữ liệu thì sao ?

/// Unlike segments, however, the cost of re-requesting the data is much higher for shards.
/// So we "accept" the risk of not getting enough results.

Do chi phí yêu cầu lại dữ liệu khá tốn nên chúng ta bắt buộc phải đánh đổi.

2. Hợp nhất dòng dữ liệu bằng K-way Merge

Bài toán: Khi gom kết quả từ $N$ shard khác nhau, Node điều phối cần hợp nhất chúng lại để đưa ra Top-K. Nếu gộp tất cả vào một vector lớn rồi gọi .sort(), độ phức tạp thuật toán sẽ là $O(M \log M)$ với $M$ là tổng số điểm từ toàn bộ các shard.

Kỹ thuật: Vì dữ liệu trả về từ mỗi shard vốn đã được sắp xếp sẵn theo Score, Qdrant sử dụng hàm kmerge_by của thư viện itertools:

• Thuật toán này sử dụng một cấu trúc dữ liệu Binary Heap để ghép $N$ dòng dữ liệu đã sắp xếp sẵn với độ phức tạp tối ưu hơn rất nhiều: $O(M \log N)$ (trong đó $N$ là số lượng shard - thường rất nhỏ, khoảng 2 đến 16).
• Kết hợp với dedup() và take(), thuật toán sẽ dừng ngay lập tức khi đã thu thập đủ Top-K mong muốn mà không cần duyệt hết toàn bộ dữ liệu.

3. Dự báo thời gian hoàn thành

Bài toán: Khi xây dựng chỉ mục (HNSW Indexing) hoặc tối ưu hóa phân đoạn dữ liệu, tiến trình diễn ra rất lâu. Các bộ tính toán ETA (Estimated Time of Arrival) thông thường dựa trên công thức đơn giản: $\text{Tốc độ} = \text{Tiến độ hiện tại} / \text{Tổng thời gian đã qua}$. Tuy nhiên, tốc độ xây dựng chỉ mục đồ thị là phi tuyến tính (càng về sau càng chậm vì cấu trúc đồ thị phức tạp lên). Ngoài ra, việc lưu trữ toàn bộ lịch sử tiến độ sẽ tốn bộ nhớ và tính toán chậm.

Giải pháp: Qdrant phát triển một bộ EtaCalculator sử dụng cấu trúc Ring Buffer kích thước cố định thông qua kỹ thuật Const Generics của Rust (ConstGenericRingBuffer<(Instant, usize), 16>):

• Cửa sổ trượt (Moving Window): Chỉ theo dõi lịch sử tiến độ trong vòng khoảng 10 giây gần nhất (16 phần tử x 625ms).
• Hợp nhất cập nhật: Để tránh nhiễu và lãng phí bộ nhớ, nếu hai cập nhật tiến độ liên tiếp xảy ra trong vòng ít hơn DURATION (625ms), nó sẽ ghi đè phần tử cuối cùng thay vì thêm phần tử mới.
• Xử lý sự cố treo: Nếu phát hiện tốc độ xử lý bị treo hoặc không thay đổi (last_progress == old_progress), hàm estimate sẽ trả về None thay vì hiển thị một con số ETA vô hạn hay sai lệch lớn.
• Tự động reset khi quay lui: Nếu phát hiện tiến trình bị đảo ngược (khi chuyển pha công việc), bộ đếm tự động reset về trạng thái ban đầu để tránh tính toán ra tốc độ âm.

4. Đếm tần suất truy vấn xấp xỉ bằng Count-Min Sketch

Bài toán: Khi hiển thị danh sách các câu truy vấn chậm, người dùng muốn biết một câu truy vấn chậm cụ thể đã xuất hiện bao nhiêu lần. Việc lưu trữ chính xác số lần xuất hiện của mọi dạng truy vấn bằng HashMap sẽ dẫn đến nguy cơ rò rỉ bộ nhớ vì số lượng biến thể truy vấn thực tế là vô hạn.

Giải pháp:

• Qdrant sử dụng cấu trúc dữ liệu xác suất Count-Min Sketch
• Mỗi khi có một slow request đi qua hệ thống băm và cập nhật vào sketch. Khi cần lấy thông tin, hệ thống sẽ ước lượng tần suất từ sketch này.
• Lợi ích: Giới hạn không gian bộ nhớ cố định nhưng vẫn cho ra kết quả thống kê tần suất xuất hiện với độ chính xác cực cao (95% xác suất đúng, sai số tối đa 10%).