Bloom-Filter technique in checking element if existed

Khi ở VCCorp, mình được tiếp cận với một hệ thống khá lớn sử dụng Hadoop Ecosystem. Công việc ở đây khá là thoải mái và họ có một văn hóa rất hay, đó là văn hóa tạm ứng niềm tin, đó là thấy ai chỉ cần có tiềm năng thôi, là sẽ được giao phó và tin tưởng trong công việc. Từ khi vào đây, mình được chủ động tìm hiểu, đưa ra giải pháp cho bài toán được giao một cách tự do, khiến mình cảm nhận và tiến bộ lên khá nhiều.

Bài toán mình phải làm ở đây đó là phải xây dựng một hệ thống A/B testing. Các tác vụ test ở đây có thể là test trên các tập user (guid) đã được xây dựng sẵn, gọi là các tập Audience. Mục đích của hệ thống này là test everything, test giữa các tập audience xem phù hợp với campaign nào và ngược lại. Một trong những điểm quan trọng của hệ thống này là phải có latency cực thấp. Lí do là khi 1 người dùng view đến trang web, hệ thống phải qua các bước xử lý, check người dùng này có trong tập audience ta cần test không, đưa ra lựa chọn và log lại, trả về cho người dùng thông tin cần thiết. Sau đó ta có thể analytic realtime trên cơ sở dữ liệu đã được log lại.

Do để có latency thật thấp nên mình đã xem xét các stage và nhận thấy có 2 stage tốn thời gian nhất: - Random phương án cho người dùng (Việc này do thư viện Planout của Glassdoor). - Check xem người dùng có trong tập audience không. Một tập audience có số lượng rất lớn, từ 1 triệu cho đến 5 triệu. Việc này sẽ còn tăng khi số lượng test nhiều lên.

Để xử lý phương án thứ nhất, mình đã xem code của Planout. Code này chậm vì nó quá cồng kềnh, có nhiều đoạn cần cast object, và nhiều phần random mình cứ nghĩ họ dùng cái thuật toán nào lạ lạ, hóa ra cũng chỉ sử dụng phân phối Multinomial để cần random 1 option theo tỉ lệ. Ví dụ bạn muốn random 1 button màu gì theo 2 options là đỏ - 0.2 và xanh - 0.8 thì phân phối Multinomial sẽ giúp bạn làm việc này. Chính vì vậy, mình đã quyết định viết lại 1 thư viện A/B Testing nhỏ gọn của mình, phù hợp với bài toán của mình và để hiệu năng cao hơn.

Ở phần check người dùng có trong tập audience hay không, ta có thể hiểu như thế này. Một người dùng sẽ được định nghĩa bằng 1 guid, và 1 tập audience chính 1 tập các guid. Việc sử dụng database thậm chí cả In-memory database đều không thể đáp ứng latency đủ thấp cho 1 tác vụ như thế này. Thật may trước đó mình đã đọc được slide về Probability Data Model của 1 anh bên VNG trên slideshare của ITLC Leader, có nhắc đến Bloom-Filter(BF) có rất nhiều ứng dụng cho các bài toán counting và check existing. Về cơ bản như sau:

Một BF là một dãy các bit có độ dài là m, ban đầu đều là 0 hết. Cùng với đó là k hàm hashing khác nhau. Mỗi 1 phần tử được đưa vào BF sẽ được hash bằng k hàm hashing này vào các vị trí trên dãy bit. Với mỗi phần tử đưa vào được hashing vào các vị trí đó thì các vị trí đó sẽ được set giá trị bằng 1.

Khi kiểm tra một phần tử có tồn tại trong BF không thì ta làm theo các tương tự, hash phần tử này bởi k hàm hashing khác nhau và check xem các vị trí thu được có giá trị bằng 1 không. Nếu tất cả bằng 1 thì phần tử đó thuộc BF, còn nếu không thì phần tử đó có thể thuộc BF với sác xuất khá thấp, gọi là sác xuất false-positive. Về cơ sở lý thuyết mình cũng được học trên lớp thầy Văn ở BK, nhưng ngại viết ra đây, mọi người có thể xem qua

Tức là ta sẽ chấp nhận có thể sai số, 1 user sẽ được nhận diện sai trong 1 audience là không có với 1 sác xuất rất thấp. Để chọn sác xuất thấp này thì mọi người xem qua trong 2 link mình gửi, do sác xuất thấp nên ta có thể chấp nhận được, và do đặc thù logic, ở nghiệp vụ A/B testing nhận diện sai như vậy không vấn đề gì cả do sác xuất quá bé.

Công việc của ta là hàng ngày xây dựng các Bloom Filter cho các tập user. Mặc dù các tập này rất lớn, được lưu trên Hbase nhưng khi xây dựng các Bloom Filter thì chỉ mất tầm 500MB cho khoảng 600 bloom-filters. Và tất nhiên quá trình Hash rất nhanh, đặc biệt là sử dụng hàm hash Murphur nên việc đáp ứng latency là một điểm giải pháp này đảm bảo.