proto.lib

Concurrent Sketch Merge: đếm ở quy mô lớn không cần khoá

Mỗi luồng cập nhật một sketch riêng (HyperLogLog, Count-Min Sketch...) hoàn toàn không đồng bộ, và các sketch được gộp lại khi đọc vì cấu trúc này có tính mergeable — biến một bộ đếm toàn cục tranh chấp cao thành ghi cục bộ theo luồng cộng với gộp định kỳ.

ConcurrencyTrung bình2026-08-25
Concurrent Sketch Merge: đếm ở quy mô lớn không cần khoá

Tags

#hyperloglog#count-min-sketch#sharded-counter#mergeable#approximate-counting#contention

Tài liệu tham khảo

Mở rộng

Animation gốc là một file HTML tự chứa, có thể nhúng lại ở bất kỳ trang nào khác. Mở file gốc

Liên quan

ConcurrencyNâng cao

Rate Limiter Token Bucket dùng chung giữa nhiều thread

Token bucket kiểu naive lock toàn bộ bucket mỗi request nên chính bộ giới hạn trở thành điểm nghẽn; thiết kế mở rộng gói tokens và timestamp vào một word rồi cập nhật bằng compare-and-swap, hoặc chia bucket theo từng core và rebalance định kỳ, đánh đổi độ chính xác lấy throughput.

#rate-limiter#token-bucket#cas#atomic
ConcurrencyNâng cao

Bitmap allocator không lock bằng CAS

Cấp một slot từ một pool dùng chung mà không cần lock: free set là bitmap gồm nhiều word, một thread quét tìm word có bit trống và chiếm bit đó bằng compare-and-swap, thử lại nếu va (collision); mỗi thread bắt đầu quét từ một offset khác nhau (hoặc trong vùng riêng) để tránh tranh chấp cùng word đầu tiên.

#bitmap-allocator#compare-and-swap#lock-free#id-allocation
ConcurrencyTrung bình

Striped Counter (LongAdder)

LongAdder chia bộ đếm thành nhiều cell riêng biệt theo từng luồng, cộng dồn cục bộ để giảm tranh chấp CAS, chỉ gộp tổng khi cần đọc giá trị.

#longadder#striped-counter#cas#contention