Sáu phần trước là về nhiều máy giữ cùng dữ liệu. Phần này là câu hỏi ngược: dữ liệu chia ra nhiều máy, khoá này ở máy nào? Câu trả lời ngắn nhất — key % n — đúng tuyệt đối cho tới ngày bạn thêm máy thứ 11, và lúc đó nó vẫn đúng, chỉ có điều gần như mọi khoá đã đổi chỗ. Consistent hashing là họ kỹ thuật để thêm bớt máy mà chỉ một phần nhỏ khoá phải di chuyển. Bài này đo "phần nhỏ" là bao nhiêu, và hai cái bẫy khiến nó không nhỏ như sách nói.

Ba cách trả lời "khoá này ở đâu"

Ảnh chụp đoạn mã nền tối khoá này ở máy nào modulo vòng băm jump hash với Go 1.23 1.000.000 khoá user i băm FNV-64 10 node thành 11 thành 9 đo trên một tiến trình không mạng, modulo đúng đều và đổi gần hết khi n đổi gồm node bằng key mod n với ghi chú n đổi từ 10 sang 11 thì 10 phần 11 số khoá đổi chỗ, vòng băm mỗi node đặt v điểm trên vòng 2 mũ 64 khoá đi tới điểm kế tiếp theo chiều kim đồng hồ gồm vòng for i tới n và j tới v, p bằng h64 của chuỗi node-i#j, p bằng tron p là splitmix64 với ghi chú không có dòng này thì FNV của node-3#0 tới node-3#9 dính chùm, append p vào diem và i vào node, sort diem giữ song song với node, tim k bằng node tại sort.Search diem lớn hơn hoặc bằng k tìm nhị phân O log n nhân v hết vòng thì quay về 0, jump hash không bảng không bộ nhớ chỉ một vòng lặp số học gồm func jump key n với b bằng trừ 1 j bằng 0, while j nhỏ hơn n thì b bằng j, key bằng key nhân 2862933555777941757 cộng 1, j bằng int64 của float64 b cộng 1 nhân float64 1 dịch 31 chia float64 key dịch 33 cộng 1, return b với ghi chú node đánh số 0 tới n trừ 1 chỉ thêm bớt được ở cuối

Hình 1: Modulo một dòng. Vòng băm với node ảo và một bước trộn bit mà thiếu nó thì toàn bộ phép đo sai. Jump hash năm dòng, không bảng.

  • Modulo: key % n. Phân bố hoàn hảo, tra cứu một nano-giây, và khi n đổi thì gần như mọi khoá đổi node.
  • Vòng băm (Karger et al., 1997): đặt mỗi node tại nhiều điểm trên vòng tròn 0..2⁶⁴, khoá thuộc về node có điểm kế tiếp theo chiều kim đồng hồ. Thêm node là thêm điểm, chỉ các khoá nằm ngay trước những điểm đó đổi chủ. "Nhiều điểm" — node ảo — để một node không ôm cả một cung lớn.
  • Jump hash (Lamping & Veach, Google 2014): một vòng lặp số học tính thẳng số node từ khoá, không bảng, không bộ nhớ, phân bố gần hoàn hảo. Đổi lại, node phải đánh số liên tục 0..n−1 và chỉ thêm bớt được ở cuối.

Đo thật: bao nhiêu khoá đổi chỗ, lệch tải bao nhiêu

Ảnh chụp output thật nền tối thêm node thứ 11 modulo chuyển 90,9 phần trăm vòng băm 9 phần trăm với Go 1.23 1.000.000 khoá lý tưởng thêm 1 node chuyển 1 phần 11 khoảng 9,1 phần trăm bớt 1 node chuyển 1 phần 10 bằng 10 phần trăm, mục 1 số khoá phải chuyển chỗ khi đổi số node cho thấy modulo key mod n 908739 tức 90,9 phần trăm khi 10 sang 11 và 899654 tức 90,0 phần trăm khi 10 sang 9, vòng băm 100 ảo FNV thô 165981 tức 16,6 phần trăm và 302571 tức 30,3 phần trăm với ghi chú điểm ảo cùng node dính chùm, vòng băm 1 node ảo 93140 tức 9,3 phần trăm và 11840 tức 1,2 phần trăm đúng tỉ lệ nhưng ngẫu nhiên theo node, 10 node ảo 85622 tức 8,6 và 94138 tức 9,4, 100 node ảo 83971 tức 8,4 và 102761 tức 10,3, 1000 node ảo 90183 tức 9,0 và 101385 tức 10,1, jump hash 90332 tức 9,0 và 100393 tức 10,0, mục 2 độ lệch tải với 10 node so với trung bình 100.000 khoá mỗi node cho thấy modulo nặng nhất 1.002 nhẹ nhất 0.998, vòng băm 100 ảo FNV thô 3.026 và 0.315, 1 node ảo 3.185 và 0.118 tức một node gánh 27 lần node khác, 10 node ảo 1.679 và 0.378, 100 node ảo 1.114 và 0.908, 1000 node ảo 1.031 và 0.953, jump hash 1.005 và 0.995, mục 3 tra cứu 1 triệu khoá 100 node cho thấy modulo 0.7 ms 1 ns mỗi khoá, vòng băm 100 node ảo 26.1 ms 26 ns tìm nhị phân trên 10.000 điểm, 1000 node ảo 36.4 ms 36 ns trên 100.000 điểm 6,4 MB bảng, jump hash 35.2 ms 35 ns không bảng không bộ nhớ, mục 4 bớt node ở giữa node 3 trong 10 cho thấy vòng băm node 3 giữ 94377 khoá chuyển đúng 94377 tức 9,4 phần trăm các node khác không đổi còn jump hash chỉ bớt được node cuối 9 là 100393 khoá bỏ node 3 là phải đánh số lại 4 tới 9 không có chỉ chuyển của node 3, nói thẳng modulo không sai nó chỉ đổi 90 phần trăm khoá mỗi lần cụm đổi cỡ với cache đó là 90 phần trăm miss với DB là 90 phần trăm dữ liệu di chuyển vòng băm cần node ảo và hàm băm trộn tốt jump hash miễn phí bộ nhớ nhưng chỉ co giãn ở đuôi

Hình 2: Kết quả thật trên một triệu khoá. Hàng "FNV thô" là phép đo đầu tiên của mình, trước khi tìm ra vì sao nó sai.

cách 10 → 11 node 10 → 9 node lệch tải (nặng nhất / nhẹ nhất)
modulo 90,9% 90,0% 1,002× / 0,998×
vòng băm, 1 node ảo 9,3% 1,2% 3,185× / 0,118×
vòng băm, 100 node ảo 8,4% 10,3% 1,114× / 0,908×
vòng băm, 1000 node ảo 9,0% 10,1% 1,031× / 0,953×
jump hash 9,0% 10,0% 1,005× / 0,995×

Modulo chuyển 90,9% khoá khi thêm một node. Không phải 9%, là 90%: với n từ 10 lên 11, khoá k ở lại node cũ chỉ khi k % 10 == k % 11, tức khoảng 1/11 trường hợp. Với cache, đó là 90% miss cùng một lúc — chính cơn bão sê-ri caching đã đo, nhân lên toàn cụm. Với database shard, là 90% dữ liệu phải chép sang máy khác trước khi cụm mới dùng được.

Vòng băm với đủ node ảo chuyển đúng 9,0% và 10,1% — sát lý tưởng 1/11 và 1/10. Lý do: thêm node là thêm 1.000 điểm rải khắp vòng, mỗi điểm "cắt" một cung nhỏ từ node đang giữ cung đó, và tổng các cung bị cắt là 1/11 vòng. Bớt node thì các cung của nó chia đều cho hàng xóm.

Bẫy thứ nhất: ít node ảo. Một node ảo cũng chuyển ~9% khi thêm, nhưng nhìn cột lệch tải: node nặng nhất gánh 3,185× trung bình, nhẹ nhất 0,118× — gấp 27 lần nhau. Với 10 điểm ngẫu nhiên trên vòng, các cung có độ dài rất không đều, và đó là lý do 10 → 9 chỉ chuyển 1,2%: node bị bỏ tình cờ là một node nhỏ. 100 node ảo đưa lệch về 1,11×, 1.000 về 1,03× — giá là bảng 100.000 điểm (6,4 MB) và tra cứu chậm hơn.

Bẫy thứ hai: hàm băm trộn kém. Phép đo đầu tiên của mình dùng FNV-1a thẳng cho vị trí node ảo "node-3#0", "node-3#1"... Kết quả: 100 node ảo mà lệch tải 3,026×, và thêm node chuyển 16,6% thay vì 9%. Nguyên nhân: các chuỗi chỉ khác ký tự cuối, FNV-1a cho ra giá trị gần nhau, nên 100 điểm của cùng một node dính chùm trên vòng — hành xử như một điểm. Thêm một bước trộn bit (splitmix64 finalizer) sau FNV là mọi con số về đúng. Hàm băm "đủ tốt cho hash map" chưa chắc đủ tốt cho vòng băm; đây là lý do các bản cài đặt thật dùng MurmurHash3, xxHash hoặc SHA-1 cắt ngắn.

Jump hash cân nhất và rẻ nhất về bộ nhớ: 1,005×, 9,0%/10,0%, không bảng, 35 ns mỗi khoá. Nhưng mục 4 cho thấy cái giá: node được đánh số 0..n−1, nên chỉ bớt được node cuối. Bỏ node 3 trong 10 node là phải đánh số lại 4..9 và kéo theo hàng loạt khoá đổi chỗ. Vòng băm thì bỏ node 3 chuyển đúng 94.377 khoá của node 3 và không động tới ai khác. Jump hash hợp với cụm chỉ to ra (hoặc co lại từ đuôi) và với thứ không có "máy chết" theo nghĩa bất kỳ — ví dụ chia dải shard logic; vòng băm hợp với cụm máy thật, nơi máy hỏng là máy bất kỳ.

Đánh đổi cần cân nhắc

Số node ảo là đánh đổi giữa cân bằng và bộ nhớ/tốc độ. 100–200 là con số nhiều hệ thống dùng (Cassandra mặc định 256 token mỗi node trước khi đổi sang 16 với thuật toán cấp token thông minh hơn). 1.000 cho 1,03× nhưng bảng 100.000 phần tử cho 100 node — vẫn nhỏ; vấn đề thật là khi có 10.000 node.

"Chuyển 9% khoá" vẫn là chuyển 9% khoá. Với cache, 9% miss có thể chấp nhận; với database, 9% của 10 TB là 900 GB phải chép, và trong lúc chép thì khoá đó ở đâu? Consistent hashing trả lời "ở đâu" nhưng không trả lời "chuyển thế nào mà không dừng" — phần 11 về sharding sẽ đo chính việc chuyển đó.

Băm đều không có nghĩa tải đều. Mọi con số lệch tải ở trên đếm số khoá; nếu một khoá nóng gấp 10.000 lần khoá khác (hot key của sê-ri caching), node giữ nó quá tải dù nhận đúng 1/10 số khoá. Băm giải quyết phân bố khoá, không giải quyết phân bố truy cập.

Có những cách khác với đánh đổi khác. Rendezvous hashing (HRW) cân tốt, bớt node bất kỳ được, không cần bảng, nhưng tra cứu O(n) theo số node. Maglev của Google cân rất đều và tra cứu O(1) nhưng xây bảng lớn. Vòng băm với node ảo vẫn là mặc định tốt vì nó là thứ duy nhất trong bảng đo ở trên vừa cân (với đủ node ảo), vừa bớt node bất kỳ, vừa tra cứu O(log n).

Một triệu khoá là mẫu thống kê, không phải tải thật. Tỉ lệ chuyển và lệch tải ổn định từ vài trăm nghìn khoá trở lên; với 10.000 khoá thì nhiễu lớn hơn nhiều và lệch tải thực tế tệ hơn bảng trên.

Ba ý mang về

  1. Modulo chuyển 90% khoá mỗi lần cụm đổi cỡ; vòng băm với đủ node ảo chuyển ~9% (1/n+1) — đúng lý thuyết, đo được trên một triệu khoá. Chênh lệch 10 lần đó là 90% cache miss cùng lúc hay 90% dữ liệu phải di chuyển.
  2. Vòng băm có hai bẫy đo được: ít node ảo thì một node gánh 27 lần node khác (1 node ảo: 3,185×/0,118×), và hàm băm trộn kém làm điểm ảo dính chùm (FNV thô: 3,026× dù có 100 node ảo). Cần ≥100 node ảo và một hàm băm trộn tốt.
  3. Jump hash cân nhất (1,005×) với 0 byte bảng, nhưng chỉ thêm bớt node ở cuối; vòng băm bớt node bất kỳ và chỉ chuyển đúng khoá của node đó. Chọn theo cụm của bạn to ra theo thứ tự hay có máy hỏng bất kỳ.

Nguồn

Phần sau quay lại chuyện ghi: khi một thao tác phải chạm hai database ở hai máy — trừ tiền ví và tạo đơn — hoặc cả hai thành công hoặc không gì cả. Hai pha commit bằng PREPARE TRANSACTION thật của PostgreSQL, đo giá của nó, và chuyện gì xảy ra khi điều phối viên chết giữa hai pha.