proto.lib

Resize Concurrent HashMap không chặn cả thế giới

Map dùng chung được chia segment/shard để writer thường chỉ đụng một lock; khi resize, bảng cũ và bảng mới cùng tồn tại trong lúc chuyển tiếp — reader vẫn đọc được và có thể tự tay giúp migrate bucket mà nó chạm tới, nên không thread nào phải trả toàn bộ chi phí rehash một lần.

ConcurrencyNâng cao2026-08-24
Resize Concurrent HashMap không chặn cả thế giới

Tags

#concurrent-hashmap#resize#incremental-rehash#sharding#weakly-consistent#java-concurrenthashmap

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

Thread-per-Core, Shared-Nothing

Mỗi core ghim đúng một thread, thread đó sở hữu riêng một phần dữ liệu và một event loop riêng; công việc được định tuyến tới core sở hữu theo key thay vì lock, nên trong luồng bình thường không có race và không có cache-line ping-pong giữa các core.

#thread-per-core#shared-nothing#sharding#message-passing
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

Thiết kế cache LRU đồng thời (sharded, không một khoá lớn)

Một cache LRU dùng một mutex toàn cục sẽ khiến mọi lookup nối hàng nhau; giải pháp thực tế là chia map thành nhiều shard (mỗi shard tự có lock) để lookup chỉ chạm một shard, và thay việc di chuyển node trong danh sách LRU nghiêm ngặt trên mỗi lần hit bằng CLOCK/second-chance bit hoặc access log theo lô để tránh tuần tự hoá.

#cache#lru#sharding#clock-algorithm