Bạn có 20.000 khoá và 3 node. Cách hiển nhiên để chia: node = hash(key) % 3. Nó chạy hoàn hảo — cho tới ngày bạn thêm node thứ 4. Lúc đó hash(key) % 3 và hash(key) % 4 cho kết quả khác nhau ở gần như mọi khoá, và cả hệ thống phải xáo trộn lại dữ liệu. Với một cache phân tán đó là cơn bão cache miss; với một CSDL đó là chuyển hàng terabyte. Bài này mổ xẻ cách Amazon Dynamo (paper SOSP 2007) giải bài toán này bằng consistent hashing, rồi dựng thật một Redis Cluster để đo trực tiếp — vì Redis Cluster chính là một bản production của cùng ý tưởng.
Bài toán: modulo hashing xáo trộn cả kho khi đổi số node
Modulo hashing gắn khoá với node theo số lượng node. Đổi số node là đổi mẫu số, mọi phép chia dư đổi theo — thêm một node buộc ~(N/(N+1)) tỉ lệ khoá đổi chỗ. Với 3→4 node, ~75% khoá phải dời. Ở quy mô lớn, điều này khiến việc mở rộng (thêm node) gần như bất khả thi trong lúc chạy.
Cách giải của Dynamo, và bản production: Redis Cluster
Ý tưởng consistent hashing: băm cả node lẫn khoá vào cùng một không gian (một "vòng"), khoá thuộc về node đầu tiên gặp khi đi theo chiều kim đồng hồ. Thêm một node chỉ chèn vào một cung của vòng và nhận khoá trong cung đó — mọi node khác không đổi. Paper Dynamo mô tả thêm/bớt node "chỉ ảnh hưởng hàng xóm kề". Dynamo còn dùng virtual nodes (mỗi node vật lý là nhiều điểm trên vòng) để cân tải.
Redis Cluster là một bản production của cùng ý tưởng, chỉ khác dạng: thay vòng liên tục bằng 16384 hash slot cố định. Mỗi khoá thuộc một slot theo slot = CRC16(key) mod 16384, mỗi master ôm một dải slot. 16384 slot đóng vai trò như virtual nodes — đủ mịn để CRC16 rải khoá đều.
redis-cli CLUSTER KEYSLOT key:1 # -> 6657 (slot = CRC16 mod 16384)
redis-cli CLUSTER KEYSLOT user:42 # -> 15880
redis-cli CLUSTER SLOTS # slot 0-5460 -> A, 5461-10922 -> B, 10923-16383 -> C
Thêm node là reshard: chỉ chuyển các slot được chọn; chỉ khoá trong slot đó migrate:
redis-cli --cluster add-node $IP4:6379 $IP1:6379 # node D vào cụm
redis-cli --cluster reshard $IP1:6379 \
--cluster-from all --cluster-to $ID4 \
--cluster-slots 4096 --cluster-yes # chuyển 1/4 slot cho D
Hình 1: Redis Cluster là consistent hashing bản production — khoá thuộc 1 trong 16384 slot theo CRC16 mod 16384, mỗi master ôm một dải slot (16384 slot đóng vai virtual nodes), thêm node chỉ reshard các slot được chọn.
Đo THẬT: cụm Redis Cluster 3→4 node
Ta dựng một Redis Cluster 3 master thật (mỗi node một container), nạp 20.000 khoá, rồi thêm node thứ 4 và đo trực tiếp.
Phân bố ban đầu (3 master): hash slot tự cân bằng, không cần cấu hình gì:
rc1 (slot 0-5460) : 6675 khoá
rc2 (slot 5461-10922) : 6667 khoá
rc3 (slot 10923-16383) : 6658 khoá
Thêm node 4 + reshard 4096 slot (1/4): cụm thật chuyển từng slot ("Moving slot 6825 from rc3 to rc4 ..."). Kết quả:
rc1: 5002 rc2: 5013 rc3: 4999 rc4: 4986 (tổng 20.000, không mất khoá)
>> Chỉ 4986/20000 = 24,9% khoá dời sang node mới (~1/4 = đúng lý thuyết)
Chỉ 24,9% khoá phải dời sang node mới — đúng ~1/N. ~75% khoá còn lại không hề đụng tới. So với modulo hashing (đổi 3→4 node phải dời ~75%), đây là khác biệt giữa "mở rộng được trong lúc chạy" và "không". Và đây là số đo trực tiếp từ một cụm thật, không phải mô phỏng.
Hình 2: Chạy thật trên cụm Redis Cluster — 3 master cân bằng tự nhiên (6675/6667/6658), thêm node thứ 4 và reshard 4096 slot chỉ dời 24,9% khoá (~1/N), 75% ở nguyên. Kèm cách Dynamo dùng vòng băm + virtual nodes + quorum.
Dynamo trong bức tranh lớn
Consistent hashing chỉ là một mảnh. Theo paper Dynamo 2007, nó ghép với:
- Sao chép theo preference list: mỗi khoá lưu ở N node kế tiếp trên vòng (N thường = 3).
- Quorum điều chỉnh được: đọc cần R, ghi cần W, đặt R + W > N để đọc luôn thấy ghi mới nhất.
- Sloppy quorum + hinted handoff: khi node đích hỏng, ghi vào N node khoẻ đầu tiên và giao lại khi node cũ hồi — ưu tiên tính sẵn sàng.
Redis Cluster cũng có sao chép (mỗi master một hoặc nhiều replica) và cơ chế failover, nhưng mô hình nhất quán khác Dynamo (Redis Cluster ưu tiên tính nhất quán hơn ở mặc định). Điểm chung cốt lõi là sharding bằng hash để thêm/bớt node không phải dời cả kho — điều demo ở trên chứng minh trực tiếp.
Đánh đổi cần cân nhắc
Consistent hashing giảm dời khoá, không xoá bỏ. Vẫn có ~1/N khoá phải chuyển khi thêm node (dữ liệu phải nằm đâu đó) — nó chỉ đưa con số từ "gần 100%" về "tối thiểu cần thiết". Và với dữ liệu trạng thái, việc migrate 1/N đó vẫn cần cơ chế chuyển an toàn (Redis Cluster migrate từng slot, có thể chặn ghi ngắn trên slot đang chuyển).
Slot cố định vs vòng liên tục. Redis chọn 16384 slot cố định (đơn giản, dễ suy luận, CLUSTER KEYSLOT tra được) thay vì vòng băm liên tục + virtual nodes như Dynamo/Cassandra. Đánh đổi: slot cố định giới hạn số node tối đa hợp lý (~ vài trăm đến ngàn) nhưng vận hành đơn giản hơn. Không có lựa chọn đúng tuyệt đối.
Reshard là thao tác vận hành, không miễn phí. Như đã thấy khi dựng demo, reshard cần cụm khoẻ (không open slot dở), và di chuyển slot có chi phí. Ở production phải làm từ tốn, theo dõi, và tính tới việc client cần biết topology mới (Redis Cluster client tự học qua MOVED/ASK).
Ba ý mang về
- Modulo hashing không mở rộng được: thêm một node buộc ~75% khoá đổi node (3→4) — với cache/DB phân tán đó là bão cache miss / chuyển dữ liệu khổng lồ.
- Consistent hashing chỉ dời ~1/N khoá: đo thật trên cụm Redis Cluster, thêm node thứ 4 + reshard 4096 slot chỉ dời 24,9% khoá (~1/N), 75% ở nguyên — bản production của ý tưởng Dynamo, với 16384 hash slot đóng vai virtual nodes.
- Hash-slot/vòng băm là nền của sharding hiện đại: Dynamo (vòng + virtual nodes + quorum), Redis Cluster (16384 slot), Cassandra, ScyllaDB đều dựa trên nó — nhưng reshard vẫn là thao tác vận hành có chi phí, phải làm cẩn thận.
Nguồn
- DeCandia et al. — Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007): https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
- Redis Docs — Cluster specification / scaling: https://redis.io/docs/latest/operate/oss_and_stack/reference/cluster-spec/
Phần sau ta xét một hệ thống lấy ghi tuần tự làm siêu năng lực: Kafka và log phân tán — cũng dựng thật và đo throughput bằng công cụ của chính Kafka.
