Avatar
1
Tuấn Vũ Đặng Beginner
Hỏi về bài post Reddit count views
Hi a Dũng, e có đọc qua blog của Reddit (https://www.redditinc.com/blog/view-counting-at-reddit), họ có nói là sử dụng Redis hyperloglog để count. Em muốn hỏi là tại sao họ k dùng redis incr để count, nếu mà dùng thì sẽ như thế nào. Vì redis là single thread nên nó sẽ tránh được race condition.

Em muốn hỏi thêm là bth những hệ thống count như này (stackaks) thì sẽ implement bằng cách nào ạ, chủ yếu là scale và tránh race condition.

Em cảm ơn ạ.

  • Answer
redis hyperloglog
Remain: 5
2 Answers
Avatar
monkey Beginner
monkey Beginner
Đầu tiên thì cần hiểu 1 chút về HyperLogLogs em nhỉ? Thì theo như bài viết này: A HyperLogLog is a probabilistic data structure used in order to count unique things (technically this is referred to estimating the cardinality of a set). Usually counting unique items requires using an amount of memory proportional to the number of items you want to count, because you need to remember the elements you have already seen in the past in order to avoid counting them multiple times. However there is a set of algorithms that trade memory for precision: you end with an estimated measure with a standard error, which in the case of the Redis implementation is less than 1%. The magic of this algorithm is that you no longer need to use an amount of memory proportional to the number of items counted, and instead can use a constant amount of memory! 12k bytes in the worst case, or a lot less if your HyperLogLog (We'll just call them HLL from now) has seen very few elements.

Như vậy thì redis đã cài đặt 1 cấu trúc dữ liệu cho HyperLogLog để chuyên cho mục đích counting, và ưu điểm của nó là chỉ tốn tối đa 12KB bộ nhớ thôi. Ví dụ nếu như bình thường muốn count số lượng vote của 1 bài viết em sẽ cần map thế này: bài viết 1: setOf(user1, user2, user3) để cho ra count = 3, tuy nhiên khi em có hàng triệu user thì set kia nó sẽ lớn và em sẽ cần tốn hàng MB cho mỗi lần query, sẽ dễ gây out of memory. Tuy nhiên với HyperLogLog thì dù thế nào nó cũng chỉ tốn tối đa 12KB mà thôi.

Tại sao không dùng incr?

Bây giờ nếu em phải dùng incr thì em sẽ phải lưu thế nào?

bài viết 1 | user1 | count = 1
bài viết 1 | user2 | count = 1

Hay

user1 | bài viết 1 | count = 1
user2 | bài viết 1 | count = 1

Hay

bài viết 1 | count = 123
bài viết 2 | count = 456

Cả 3 cách đều không được, riêng cách 3 thì có thể được, nhưng em sẽ phải sinh ra 1 con server riêng biệt (để tránh race) để kiểm tra thằng user nó đã vote chưa rồi mới incr lên được.

Vậy nếu có 1 phương án gần đúng và nhẹ nhàng và sử dụng được trong môi trường nhiều server như HyperLogLog sẽ là giải pháp tốt hơn.

Còn về stackask thì sao?

Đối với những trang như stackask khi cơ sở dữ liệu còn bé (dưới vài triệu bản ghi) thì để cho đơn giản vẫn query từ MySQL thôi em ạ.

  • 0
  • Reply
Avatar
Hi a Dũng, cảm ơn a đã trả lời bài viết.

Em có thắc mắc đoạn "riêng cách 3 thì có thể được, nhưng em sẽ phải sinh ra 1 con server riêng biệt (để tránh race) để kiểm tra thằng user nó đã vote chưa rồi mới incr lên được."

Em chưa hiểu lắm tại sao phải dùng 1 con server riêng ạ.

Ý em là mình có thể lưu đúng như a nói: post1|count = 123, mỗi lần có user view thì mình lại inc count lên post1|count = 124. Em nghĩ cái này quan trọng là lúc tăng phải tránh race vì 2 user có thể vào cùng 1 lúc,nhưng mà may là redit có single thread nên có support chỗ này : https://redis.io/commands/incr/. Một vấn đề nữa là với traffic lớn thì mình incr +1 liên tục vào 1 key như vậy thì redis có handle được không ạ.

  • 0
  • Reply
Hãy giả sử em có 2 server, lúc này user sẽ gọi cùng lúc 2 api /api/v1/vote trên cả 2 server (do click đúp chẳng hạn). Thì lúc này em sẽ lư bản ghi user vote ở đâu đó (redis, db chẳng hạn) vậy thì trên cả 2 server có khả năng khi kiểm tra sẽ đề trả về user chưa vote, vậy thì biến count sẽ tăng lên 2 thay vì 1, vậy sẽ gây sai.

Trên thực tế incr là phép tính đơn giản, nên anh nghĩ sẽ không có gì với traffic lớn cả.

 –  monkey 1658953399000