Trang chủ video của chúng tôi hiện hiển thị một bộ 24 đề xuất mới mỗi khi làm mới, nhờ vào việc chuyển sang phương pháp lấy mẫu hồ chứa có trọng số (weighted reservoir sampling - A-Res). Thay đổi này đã loại bỏ vấn đề "lưới hiển thị không đổi" vốn gây khó chịu cho luồng dữ liệu sắp xếp theo điểm số trước đây của chúng tôi.

Tại sao cách tiếp cận cũ làm hỏng trải nghiệm người dùng

Cứ mỗi hai giờ, chúng tôi lại lấy các video đang thịnh hành nhất từ tám khu vực và đổ kết quả vào một bảng SQLite. Giải pháp đơn giản (naïve) là sắp xếp toàn bộ tập hợp—theo điểm số liên quan—và lấy ra 24 mục đầu tiên. Phương pháp đó đảm bảo các mục có điểm cao nhất sẽ xuất hiện, nhưng nó cũng đảm bảo rằng chúng sẽ luôn nằm ở đó. Một clip lan truyền (viral) duy nhất có thể chiếm lĩnh vị trí số 1 trong nhiều ngày, và người dùng sẽ thấy một lưới hiển thị giống hệt nhau mỗi khi họ tải lại trang.

Ngoài trải nghiệm nhàm chán, việc sắp xếp toàn bộ bảng cho mỗi yêu cầu còn buộc SQLite phải tải một cấu trúc tạm thời lớn vào bộ nhớ, gây lãng phí tài nguyên.

Lấy mẫu hồ chứa có trọng số mang lại cho chúng ta điều gì

Lấy mẫu hồ chứa có trọng số giải quyết hai vấn đề cùng một lúc:

  1. Sự tươi mới có tính thiên kiến (Freshness with bias) – xác suất được chọn của mỗi video tỉ lệ thuận với trọng số của nó (ví dụ: điểm số liên quan). Một video có trọng số gấp đôi sẽ có khả năng xuất hiện cao gấp đôi, nhưng không có mục nào được đảm bảo chắc chắn có một vị trí.
  2. Hiệu quả bộ nhớ – thuật toán chỉ giữ một "hồ chứa" (reservoir) có kích thước cố định gồm k mục (k = 24 cho luồng dữ liệu của chúng tôi). Nó xử lý luồng dữ liệu chỉ trong một lần quét duy nhất (single pass), vì vậy bộ nhớ luôn ở mức O(k) bất kể có bao nhiêu ứng viên được đưa vào.

Ý tưởng cốt lõi rất đơn giản. Khi chúng tôi quét các hàng dữ liệu đang đến, chúng tôi gán cho mỗi mục một khóa ngẫu nhiên (random key) có kết hợp với trọng số của nó, sau đó giữ lại k mục có khóa cao nhất.

Thuật toán trong thực tế

Đối với mỗi video, chúng tôi:

  1. Rút một số ngẫu nhiên đồng nhất u ∈ (0, 1).
  2. Tính toán một khóa k = u^(1/weight).
    (Trọng số càng cao, khóa kỳ vọng càng lớn.)
  3. Chèn mục đó vào một min-heap (đống tối thiểu) dùng để lưu trữ k khóa cao nhất hiện tại.
    Nếu heap vượt quá kích thước k, chúng tôi sẽ loại bỏ khóa nhỏ nhất.

Khi luồng dữ liệu kết thúc, heap sẽ chứa 24 video mà chúng tôi sẽ hiển thị.

Xử lý các giới hạn của số dấu phẩy động

Khi trọng số của một video rất lớn, u^(1/weight) sẽ bị thu hẹp thành một giá trị không thể phân biệt được với 1.0 trong tính toán số thực dấu phẩy động độ chính xác kép (double-precision), khiến nhiều mục có trọng số lớn chia sẻ cùng một khóa và làm mất tính ngẫu nhiên. Cách khắc phục là làm việc trong không gian log (log space):

  • Tính log_key = log(u) / weight thay vì sử dụng biểu thức lũy thừa.

Vì logarit chuyển phép lũy thừa thành phép nhân, thứ tự của các khóa vẫn được bảo toàn trong khi tránh được sự sụt giảm độ chính xác (precision cliff). Việc tính toán này hầu như không tốn thêm chi phí nào.

Danh sách kiểm tra triển khai

  • Cấu trúc dữ liệu: một min-heap (hàng đợi ưu tiên) có kích thước k giúp giữ các khóa lớn nhất một cách hiệu quả (O(log k) cho mỗi lần chèn).
  • Kiểu dữ liệu số: sử dụng số thực dấu phẩy động 64-bit cho u và các khóa dựa trên log; chúng cung cấp đủ độ chính xác cho các phạm vi trọng số thông thường.
  • Kiểm tra tính hợp lý về mặt thống kê: chạy một thử nghiệm Monte-Carlo nhanh trên một tập mẫu nhỏ. Nếu các mục có trọng số 10 xuất hiện nhiều gấp khoảng mười lần so với trọng số 1, thì việc triển khai là chính xác.
  • Truyền dữ liệu một lần duy nhất (Single-pass streaming): thuật toán không cần biết trước tổng số ứng viên, điều này hoàn toàn phù hợp với con trỏ (cursor) SQLite của chúng tôi vốn trả về các hàng theo từng cái một.

Bài học rút ra

Lấy mẫu hồ chứa có trọng số cho phép dịch vụ đề xuất video giữ cho trang chủ luôn tươi mới, tôn trọng điểm số liên quan và tiết kiệm bộ nhớ—tất cả chỉ với một lần quét qua hàng chục nghìn ứng viên. Bằng cách chuyển việc tính toán khóa sang không gian log và sử dụng min-heap, phương pháp này vừa đảm bảo độ chính xác vừa duy trì hiệu suất cao.