Giao diện
Partitioning (sharding)
Khi dữ liệu hoặc lượng truy cập vượt sức một máy, chia dữ liệu ra nhiều máy, mỗi máy giữ một phần (partition, shard). Câu hỏi chính: key nào nằm ở máy nào, và khi thêm hay bớt máy thì bao nhiêu dữ liệu phải di chuyển.
Áp dụng cho cả cache (Redis, Memcached) lẫn database (MySQL qua Vitess, Cassandra, DynamoDB). Cách làm cụ thể trên MySQL và cách chọn shard key: MySQL chương 10.
Chia theo khoảng hay theo hash
| Theo khoảng (range) | Theo hash | |
|---|---|---|
| Cách chia | id 1–1 triệu ở máy 1, 1–2 triệu ở máy 2… | hash(key) quyết định máy |
| Query theo khoảng | Gọn, thường chỉ chạm một máy | Phải hỏi mọi máy |
| Phân bố | Dễ lệch: key tăng dần dồn mọi lệnh ghi vào máy cuối | Đều |
| Ví dụ | HBase, TiKV (chia region theo khoảng), bảng partition theo tháng | Cassandra, DynamoDB, Redis Cluster |
Hash mod N và vấn đề khi đổi số máy
node = hash(key) mod N đơn giản và đều. Nhưng đổi N thì phép chia đổi mẫu số, gần như mọi key đổi chỗ: từ N lên N+1 máy, khoảng N/(N+1) số key phải di chuyển. Cụm 10 máy thêm 1 máy là khoảng 91% key đổi chỗ. Với cache, đó là 91% cache miss cùng lúc, tức một cache avalanche (Sự cố); với database, đó là sao chép gần toàn bộ dữ liệu.
Consistent hashing
Đề xuất năm 1997 (Karger, Lehman, Leighton, Panigrahy, Levine, Lewin), dùng trong Akamai, Amazon Dynamo, Cassandra.
- Vòng hash: không gian giá trị hash (ví dụ 0 đến 2³² − 1) uốn thành một vòng tròn.
- Đặt máy lên vòng: hash id hoặc địa chỉ của từng máy để có vị trí trên vòng.
- Tìm máy cho key: hash key để có vị trí, đi theo chiều kim đồng hồ, máy đầu tiên gặp là máy giữ key.
- Thêm một máy: máy mới chỉ nhận phần key nằm giữa nó và máy liền trước; các key khác giữ nguyên. Chỉ khoảng K/N key di chuyển (K là số key).
- Virtual node: với ít máy, khoảng cách giữa các máy trên vòng rất lệch nên tải lệch. Mỗi máy được đặt ở nhiều điểm trên vòng (
cache-0#1,cache-0#2…), tải đều dần khi số điểm tăng. Máy mạnh hơn có thể được cho nhiều điểm hơn. - Cài đặt: mảng các điểm đã sắp xếp (hoặc TreeMap) + tìm nhị phân.
Số node: 4
1 = mỗi server chỉ có một điểm trên vòng, tải thường lệch rất nhiều.
–hash mod N: key đổi node
–consistent hashing: key đổi node
Bấm thêm hoặc bớt node để đo.
Số key mỗi node · node nặng nhất = 2,48× trung bình
Vạch ngoài là các điểm (virtual node) của từng server; chấm bên trong là 300 key; chấm viền đậm là key vừa đổi node.
Slot cố định (bucket ảo)
Chia sẵn một số lượng cố định bucket (Redis Cluster: 16384 slot; Vitess: dải keyspace id), rồi gán bucket cho máy. Key luôn thuộc cùng một bucket; thêm máy chỉ là chuyển một số bucket. Ưu điểm so với consistent hashing: phân bố được chủ động quyết định thay vì phụ thuộc vị trí ngẫu nhiên trên vòng, và client không phải dựng vòng hash. Chi tiết: Redis Cluster; mô phỏng chuyển bucket: MySQL chương 10.
Ai biết key nằm ở đâu
| Mô hình | Cách làm | Ví dụ |
|---|---|---|
| Client tự định tuyến | Thư viện client giữ vòng hash hoặc bảng slot, tự chọn máy | Thư viện memcached có Ketama, client Redis Cluster (ioredis) |
| Proxy | App gửi cho proxy, proxy chọn máy | Twemproxy, Envoy, ProxySQL, Vitess (VTGate) |
| Máy trong cụm chuyển hướng | Gửi tới máy bất kỳ, máy đó chuyển tiếp hoặc trả về địa chỉ đúng | Cassandra, DynamoDB, Redis Cluster (MOVED) |
Không phải thư viện nào cũng mặc định dùng consistent hashing. Ví dụ gomemcache (Go) mặc định chọn máy bằng crc32(key) % N; spymemcached (Java) phải bật Ketama. Kiểm tra trước khi thêm node vào cụm cache.
Phát hiện máy hỏng:
- Bị động: client đếm lỗi, quá ngưỡng thì tự bỏ máy đó khỏi vòng. Các client có thể thấy khác nhau (client 1 bỏ máy A, client 2 chưa), mỗi client dùng một vòng khác nhau.
- Chủ động: mỗi máy đăng ký và gửi heartbeat tới service discovery (Consul, etcd); máy chết thì service discovery đẩy thay đổi tới mọi client hoặc proxy cùng lúc.
Index phụ trên dữ liệu đã chia
- Index cục bộ: mỗi máy tự index phần dữ liệu của mình. Ghi đơn giản; query theo cột không phải partition key phải hỏi mọi máy rồi gộp (scatter-gather).
- Index toàn cục: index cũng được chia, theo giá trị cột được index. Đọc chỉ hỏi một máy; ghi một dòng có thể phải cập nhật index ở máy khác, thường làm bất đồng bộ nên index có độ trễ.
Ghi nhớ
- Hash mod N: đổi số máy làm khoảng N/(N+1) key di chuyển.
- Consistent hashing: chỉ khoảng 1/N key di chuyển; virtual node để tải đều.
- Slot cố định (Redis Cluster 16384 slot) cho phép chủ động phân bố, client không phải dựng vòng.
- Định tuyến ở client, proxy, hoặc trong cụm; phát hiện máy hỏng chủ động qua service discovery thì các client thấy giống nhau.