Consistent hashing: thêm một máy cache mà không làm mất gần hết cache

Cụm cache của BanHang có 4 node. API chọn node cho mỗi key bằng hash(key) % 4. Trước đợt sale, đội vận hành thêm node thứ năm để có thêm bộ nhớ. Ngay sau khi đổi cấu hình, khoảng 80% key được tìm ở một node chưa có chúng, và các lượt đọc đó rơi xuống SQL Server. Bài này tính và đo hiện tượng đó trên 1.000.000 key, dựng consistent hashing bằng Python thư viện chuẩn, đo lại, rồi đi qua virtual node, các phương án khác và checklist mở rộng cụm cache.

1. Thêm node thứ năm, mất 80% cache #

Lớp cache trong API của BanHang băm key thành số 64 bit h rồi lấy h % N. Mọi API server tự tính ra cùng một node mà không cần hỏi ai. Cách này đúng cho tới ngày N đổi.

Key giữ nguyên node khi h % N == h % (N+1). N và N+1 nguyên tố cùng nhau. Theo định lý số dư Trung Hoa, khi h phân bố đều thì cặp (h % N, h % (N+1)) phân bố đều trên N·(N+1) cặp. Chỉ N cặp có hai số bằng nhau: (0, 0), (1, 1), …, (N−1, N−1).

tỉ lệ key giữ nguyên node khi đi từ N lên N+1 = N / (N·(N+1)) = 1/(N+1)
N = 4:  giữ 1/5  = 20%,  đổi node 80%
N = 9:  giữ 1/10 = 10%,  đổi node 90%

Cụm càng lớn, thêm một node càng làm nhiều key đổi chỗ. Nhân đôi số node đỡ hơn nhưng vẫn mất một nửa: h % 8 quyết định h % 4, nên đi từ 4 lên 8 node chỉ giữ key có h % 8 < 4, tức 50%.

Ước lượng tải lên SQL Server như sau. Lúc cao điểm API nhận khoảng 300 request mỗi giây. Giả sử mỗi request đọc 3 key cache và hit rate là 95%. SQL Server nhận 900 × 0,05 = 45 truy vấn mỗi giây do cache miss. Ngay sau khi đổi sang 5 node:

tỉ lệ miss ngay sau khi đổi ≈ 0,80 + 0,20 × 0,05 = 0,81
truy vấn xuống SQL Server   ≈ 900 × 0,81 ≈ 729 mỗi giây, gấp 16 lần

Mức này giảm dần khi key nóng được nạp lại, nhanh hay chậm tùy phân bố truy cập. Trong lúc đó, 80% dữ liệu trên bốn node cũ thành bản thừa, chiếm bộ nhớ tới khi hết TTL hoặc bị evict. Cách nhận ra SQL Server đang nghẽn CPU, với request xếp hàng runnable và wait SOS_SCHEDULER_YIELD, có trong Điều tra một truy vấn chậm.

2. Vòng băm #

Karger, Lehman, Leighton, Panigrahy, Levine và Lewin đưa ra consistent hashing tại hội nghị STOC năm 1997, cho bài toán cache web: cache server thêm bớt liên tục, và mỗi client có thể chỉ biết một phần các server. Mục tiêu là khi tập node đổi, ánh xạ từ key sang node đổi ít nhất có thể. Cơ chế có ba bước:

1. Coi không gian hash 64 bit là một vòng: sau 2^64 − 1 là 0.
2. Đặt mỗi node lên vòng ở một hoặc nhiều điểm. Mỗi điểm là hash của tên node kèm số thứ tự: h64("cache-1#0"), h64("cache-1#1"), … Mỗi điểm gọi là một virtual node.
3. Băm key lên cùng vòng. Key thuộc về điểm đầu tiên gặp khi đi theo chiều tăng của hash, tức chiều kim đồng hồ. Quá điểm cuối thì vòng về điểm đầu.

Minh họa với bốn node, mỗi node một điểm:

0                                                    2^64 (vòng về 0)
|---A---k1-------B-----k2-----k3---C--------D---k4---|
k1 → B,  k2 → C,  k3 → C,  k4 → A (vòng qua mốc 0)

Thêm E vào giữa k2 và k3:
|---A---k1-------B-----k2--E--k3---C--------D---k4---|
k2: C → E.  k1, k3, k4 giữ nguyên.

E chỉ nhận key trong cung từ B tới E, và chỉ lấy chúng từ C. Không key nào chuyển giữa A, B, C, D. Paper của Karger gọi tính chất này là monotonicity: khi thêm bucket, key chỉ chuyển từ bucket cũ sang bucket mới. Phần key đổi node bằng phần vòng mà node mới chiếm, kỳ vọng 1/(N+1).

# ring.py
import hashlib
from bisect import bisect_right


def h64(s: str) -> int:
    """64 bit đầu của MD5. Chỉ để trộn bit, không dùng cho bảo mật."""
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")


class HashRing:
    def __init__(self, nodes=(), vnodes=100):
        self.vnodes = vnodes
        self.nodes = set(nodes)
        self._rebuild()

    def _rebuild(self):
        # Mỗi node có `vnodes` điểm trên vòng: h64("cache-1#0"), h64("cache-1#1"), ...
        pts = sorted((h64(f"{n}#{i}"), n) for n in self.nodes for i in range(self.vnodes))
        self._pos = [p for p, _ in pts]
        self._owner = [n for _, n in pts]

    def add(self, node):
        self.nodes.add(node)
        self._rebuild()

    def remove(self, node):
        self.nodes.discard(node)
        self._rebuild()

    def lookup(self, kh: int) -> str:
        """Node của key có hash kh: điểm đầu tiên theo chiều kim đồng hồ."""
        i = bisect_right(self._pos, kh)
        return self._owner[i % len(self._pos)]  # qua điểm cuối thì vòng về điểm đầu

    def get(self, key: str) -> str:
        return self.lookup(h64(key))

bisect_right tìm điểm đầu tiên lớn hơn hash của key. Với 5 node × 100 điểm, đó là tìm nhị phân trên 500 số, khoảng 9 phép so sánh. Vòng chỉ là hai list song song. Mỗi API server tự dựng vòng từ cùng danh sách node, không cần trao đổi với nhau.

3. Đo trên 1.000.000 key #

Tập key mô phỏng gồm 5.000 key sản phẩm, từ san-pham:SP-00001 tới san-pham:SP-05000, và 995.000 key giỏ hàng, từ gio-hang:0 tới gio-hang:994999, tính cả giỏ của khách chưa đăng nhập. Với mỗi số virtual node, script đo: phần key đổi node khi thêm cache-5, số key chuyển giữa các node cũ, độ lệch tải khi đã có 5 node, và nơi key của cache-2 đi tới khi cache-2 bị gỡ.

# do_dac.py, đặt cùng thư mục với ring.py
from collections import Counter
from statistics import pstdev
from ring import HashRing, h64

keys = [f"san-pham:SP-{i:05d}" for i in range(1, 5001)]
keys += [f"gio-hang:{i}" for i in range(995_000)]
kh = [h64(k) for k in keys]          # băm một lần, dùng lại cho mọi phép đo
N = len(kh)

giu = sum(h % 4 == h % 5 for h in kh)
print(f"modulo 4 -> 5: giữ {giu / N:.2%}, đổi node {1 - giu / N:.2%}")

cu = [f"cache-{i}" for i in range(1, 5)]
print("vnode | đổi node | sang node cũ | max/TB | lệch chuẩn | gỡ cache-2: 1 node nhận")
for v in (1, 10, 100, 200):
    r = HashRing(cu, vnodes=v)
    truoc = [r.lookup(h) for h in kh]
    r.add("cache-5")
    sau = [r.lookup(h) for h in kh]
    doi = sum(a != b for a, b in zip(truoc, sau))
    sai = sum(a != b and b != "cache-5" for a, b in zip(truoc, sau))
    tai = Counter(sau)
    tb = N / 5
    r.remove("cache-2")                     # cache-2 chết: key của nó đi đâu
    nhan = Counter(r.lookup(h) for h, n in zip(kh, sau) if n == "cache-2")
    print(f"{v:5} | {doi / N:8.2%} | {sai:12} | {max(tai.values()) / tb:6.3f} | "
          f"{pstdev(tai.values()) / tb:9.1%} | {max(nhan.values()) / tai['cache-2']:.0%}")

Kết quả với Python 3.14.3. Script không có phần ngẫu nhiên, nên chạy lại ở đâu cũng ra cùng số. Trên laptop Intel Core Ultra 5 125U, Windows 11, script chạy khoảng 30 giây; thời gian đổi theo máy.

modulo 4 -> 5: giữ 19.95%, đổi node 80.05%
vnode | đổi node | sang node cũ | max/TB | lệch chuẩn | gỡ cache-2: 1 node nhận
    1 |    8.04% |            0 |  1.955 |     73.7% | 100%
   10 |   26.60% |            0 |  1.408 |     33.4% | 45%
  100 |   21.14% |            0 |  1.057 |      3.4% | 35%
  200 |   21.47% |            0 |  1.076 |      7.3% | 30%

• Modulo đổi node cho 80,05% key, khớp công thức 4/5.
• Cột sang node cũ bằng 0 ở cả bốn dòng. Mọi key đổi node đều sang cache-5.
• Với 1 điểm mỗi node, cache-5 rơi vào một cung hẹp và chỉ nhận 8,04% key. Ít miss, nhưng node mới gần như không gánh bớt cho bốn node cũ.
• max/TB là số key của node nặng nhất chia cho mức trung bình 200.000. Với 1 điểm, node nặng nhất giữ 1,955 lần trung bình, khoảng 39% toàn bộ key, và sẽ evict trước các node khác.
• Cột cuối là phần key của cache-2 dồn về một node khi cache-2 bị gỡ. Với 1 điểm, 100% đổ vào node kế tiếp trên vòng: cache-2 chết giữa giờ sale thì node đó gánh gấp đôi. Với 200 điểm, con số là 30%, gần mức chia đều 25%.

Trước khi đổi cấu hình thật, chạy cùng script với tên node thật và một mẫu key thật để biết trước bao nhiêu key sẽ đổi node và node nào nặng nhất.

4. Virtual node: bao nhiêu điểm là đủ #

Hash làm key rải đều trên vòng, nhưng không làm các cung đều nhau. Với M điểm ngẫu nhiên, cung dài nhất có độ dài kỳ vọng H_M / M, với H_M = 1 + 1/2 + … + 1/M. Với 5 node, mỗi node 1 điểm, H_5 ≈ 2,28: node nặng nhất kỳ vọng giữ 2,28 lần mức trung bình.

Một node có v điểm sở hữu tổng của v cung. Cộng nhiều cung ngẫu nhiên thì sai số tương đối giảm theo 1/√v. Chính xác hơn, độ dài các cung theo phân phối Dirichlet, nên phần vòng của một node theo phân phối Beta(v, (N−1)·v):

độ lệch chuẩn tương đối của phần vòng một node = √((N − 1) / (N·v + 1))
N = 5, v = 1:    √(4/6)    ≈ 81,6%
N = 5, v = 100:  √(4/501)  ≈ 8,9%
N = 5, v = 200:  √(4/1001) ≈ 6,3%

Bảng ở mục 3 là một lần rút thăm. Cụm cache-1 tới cache-5 với 100 điểm tình cờ cân hơn với 200 điểm: độ lệch chuẩn 3,4% so với 7,3%. Muốn thấy xu hướng thì đo nhiều cụm. Script dưới đặt điểm ngẫu nhiên với hạt giống 42, tính thẳng độ dài cung thay vì băm key, lặp trên 1.000 cụm 5 node:

# thong_ke.py
import random
from statistics import mean, pstdev

def thi_phan(so_node, v, rng):
    """Phần vòng mỗi node sở hữu: tổng các cung kết thúc ở điểm của nó."""
    pts = sorted((rng.random(), n) for n in range(so_node) for _ in range(v))
    phan = [0.0] * so_node
    truoc = pts[-1][0] - 1.0                # cung đầu tiên vòng qua mốc 0
    for p, n in pts:
        phan[n] += p - truoc
        truoc = p
    return phan

rng = random.Random(42)
for v in (1, 10, 100, 200):
    cum = [thi_phan(5, v, rng) for _ in range(1000)]
    lech = mean(pstdev(s) * 5 for s in cum)    # chia cho trung bình 1/5
    lon = mean(max(s) * 5 for s in cum)
    print(f"v={v:3}: lệch chuẩn TB {lech:5.1%}, max/TB TB {lon:.2f}, "
          f"công thức {((5 - 1) / (5 * v + 1)) ** 0.5:5.1%}")

v=  1: lệch chuẩn TB 76.7%, max/TB TB 2.27, công thức 81.6%
v= 10: lệch chuẩn TB 26.3%, max/TB TB 1.39, công thức 28.0%
v=100: lệch chuẩn TB  8.5%, max/TB TB 1.12, công thức  8.9%
v=200: lệch chuẩn TB  6.0%, max/TB TB 1.08, công thức  6.3%

Max/TB trung bình với 1 điểm là 2,27, khớp H_5 ≈ 2,28. Độ lệch chuẩn trung bình thấp hơn công thức một chút vì lấy trung bình của căn, không phải căn của trung bình. Từ 100 lên 200 điểm, độ lệch chuẩn chỉ giảm từ 8,5% xuống 6,0%, vì sai số giảm theo căn bậc hai. Lamping và Veach ghi lại rằng thí nghiệm của Karger dùng 1.000 điểm mỗi bucket để đạt độ lệch chuẩn 3,2%. Bộ nhớ không phải vấn đề với cụm nhỏ: 5 node × 200 điểm là 1.000 phần tử.

Virtual node làm đều phần vòng, không làm đều lượt truy cập. Một key nóng như san-pham:SP-00042 trong giờ sale vẫn nằm trọn trên một node. Khi các máy có dung lượng khác nhau, cho máy lớn nhiều điểm hơn, như paper Dynamo đề xuất.

5. Các phương án khác #

Rendezvous hashing, còn gọi là highest random weight (Thaler và Ravishankar, IEEE/ACM Transactions on Networking, 1998). Mỗi node chấm điểm key bằng h(node, key), node điểm cao nhất thắng. Không có vòng, không cần virtual node. Thêm node chỉ làm đổi các key mà node mới có điểm cao nhất. Giá phải trả là mỗi lần tra băm N lần.

Jump Consistent Hash (Lamping và Veach, Google, 2014). Khoảng 5 dòng code, không cần bộ nhớ, số vòng lặp kỳ vọng dưới ln(n) + 1. Giới hạn: bucket phải đánh số liên tục từ 0 tới n−1, nên chỉ thêm hoặc bớt được bucket cuối. Không bỏ được cache-2 mà giữ nguyên các node khác. Chính paper nói nó hợp với lưu trữ phân shard, nơi shard có bản sao và không tự biến mất, hơn là cache web.

# phuong_an_khac.py, đặt cùng thư mục với ring.py
from collections import Counter
from ring import h64

def hrw(key, nodes):
    """Rendezvous: node có điểm h64(node|key) cao nhất thắng. Tra một key tốn O(số node)."""
    return max(nodes, key=lambda n: h64(f"{n}|{key}"))

def jump(key: int, n: int) -> int:
    """Jump Consistent Hash, dịch từ bản C++ trong paper của Lamping và Veach."""
    b, j = -1, 0
    while j < n:
        b = j
        key = (key * 2862933555777941757 + 1) % 2**64
        j = int((b + 1) * (2**31 / ((key >> 33) + 1)))
    return b

keys = [f"san-pham:SP-{i:05d}" for i in range(1, 5001)]
keys += [f"gio-hang:{i}" for i in range(195_000)]      # 200.000 key cho nhanh
cu = [f"cache-{i}" for i in range(1, 5)]
for ten, f4, f5 in [("rendezvous", lambda k: hrw(k, cu), lambda k: hrw(k, cu + ["cache-5"])),
                    ("jump", lambda k: jump(h64(k), 4), lambda k: jump(h64(k), 5))]:
    truoc, sau = [f4(k) for k in keys], [f5(k) for k in keys]
    tai = Counter(sau).values()
    print(f"{ten:10}: đổi node {sum(a != b for a, b in zip(truoc, sau)) / len(keys):.2%}, "
          f"max/TB {max(tai) / (len(keys) / 5):.3f}")

rendezvous: đổi node 19.99%, max/TB 1.004
jump      : đổi node 20.09%, max/TB 1.006

Bản Python của jump cho đúng các giá trị kiểm thử của thư viện go-jump. Cả hai cách đổi node khoảng 20% và gần như cân tuyệt đối; phần lệch 0,4–0,6% còn lại chủ yếu do mẫu 200.000 key. Script chạy khoảng 30 giây trên cùng máy, phần lớn là 9 lần MD5 mỗi key của rendezvous.

Bounded loads (Mirrokni, Thorup và Zadimoghaddam, SODA 2018) đặt trần ⌈(1+ε)·m/n⌉ cho mỗi node, với m key và n node. Key rơi vào node đã đầy thì đi tiếp theo chiều kim đồng hồ tới node còn chỗ. HAProxy có tùy chọn hash-balance-factor cho hash-type consistent theo cách này: giá trị 150 nghĩa là không server nào nhận quá 1,5 lần tải trung bình.

6. Hệ thống thật dùng gì #

• Dynamo (DeCandia và cộng sự, Amazon, SOSP 2007) dùng consistent hashing với virtual node, gọi là token, vì vị trí ngẫu nhiên làm tải không đều. Mục 6.2 kể Dynamo sau đó chuyển từ token ngẫu nhiên sang chia không gian hash thành Q phân vùng bằng nhau, mỗi node giữ Q/S phân vùng. Cách này cân tải tốt nhất trong ba cách được thử và giảm thông tin membership mỗi node ba bậc độ lớn.
• Cassandra phân vùng dữ liệu bằng token ring và vnode. File cassandra.yaml mẫu đặt num_tokens: 256 ở bản 3.11. Từ Cassandra 4.0, giá trị đổi thành 16 (CASSANDRA-13701), kèm allocate_tokens_for_local_replication_factor: 3. Ít token vẫn cân được vì từ 3.x có bộ cấp token chọn vị trí có chủ đích thay vì ngẫu nhiên.
• Redis Cluster không dùng consistent hashing, và tài liệu Redis viết đúng như vậy. Mỗi key thuộc một trong 16.384 hash slot, HASH_SLOT = CRC16(key) mod 16384, và mỗi master giữ một tập slot. Thêm node là chuyển một số slot sang node mới; redis-cli chuyển key bằng MIGRATE, client đi đúng node nhờ lỗi MOVED và ASK. Dữ liệu đi theo slot, nên không có đợt miss hàng loạt, đổi lại là lưu lượng chuyển dữ liệu trong lúc reshard.

Hash slot vẫn là modulo, nhưng modulo theo một số cố định thay vì theo số node. Thứ thay đổi khi thêm node là bảng slot → node. Đó cùng họ ý tưởng với Q phân vùng cố định của Dynamo.

7. Checklist mở rộng cụm cache của BanHang #

1. Chạy trước vòng mới trên mẫu key thật như do_dac.py. Kỳ vọng: khoảng 1/(N+1) key đổi node, max/TB dưới 1,1. Lệch hơn thì tăng số điểm hoặc chọn lại tên node.
2. Đổi cấu hình ngoài khung cao điểm 10:00–11:30, vài ngày trước sale, để cache nóng lại bằng lưu lượng thường.
3. Thêm từng node một, chờ hit rate về mức cũ rồi mới thêm node tiếp. Thêm 2 node một lúc, từ 4 lên 6, chuyển 2/6 ≈ 33% key trong một lần. Thêm lần lượt là 20% rồi 1/6 ≈ 17%.
4. Làm nóng node mới. Trong thời gian chuyển, khi node mới miss thì đọc node cũ theo vòng cũ trước khi xuống SQL Server, rồi ghi vào node mới. Nạp trước key của các sản phẩm trong đợt sale.
5. Đổi vòng trên mọi API server gần như cùng lúc. Hai vòng cùng tồn tại lâu thì một key có bản ở hai node, và lệnh xóa key khi đổi giá chỉ chạm một bản.
6. Theo dõi hit rate từng node, số truy vấn SQL Server mỗi giây, CPU SQL Server, p95 của API, số key bị evict, bộ nhớ từng node. Định trước ngưỡng để quay lại cấu hình cũ.
7. Quay lại vòng cũ cũng là một lần đổi vòng. Key về lại node cũ, nơi bản cũ có thể đã lỗi thời. Xóa các key đã đổi node, hoặc giữ TTL ngắn trong thời gian chuyển.

Những chỗ hay hiểu sai #

• "Consistent hashing làm thêm node không gây miss." Vẫn có khoảng 1/(N+1) key miss: đo được 21,14% khi đi từ 4 lên 5 node.
• "Thủ phạm là phép modulo." Thủ phạm là modulo theo số node. Redis Cluster dùng modulo 16.384 cố định cộng bảng slot.
• "Hash đã đều thì một điểm mỗi node là đủ." Key đều, nhưng 5 điểm ngẫu nhiên chia vòng rất lệch: node mới chỉ nhận 8,04%, node nặng nhất giữ 1,955 lần trung bình.
• "Redis Cluster dùng consistent hashing." Tài liệu Redis ghi rõ là không.
• "Virtual node chữa được key nóng." Một key vẫn nằm trên một node, bất kể có bao nhiêu điểm.

Đọc tiếp #

• Bloom filter
• Bài toán hai vị tướng và giới hạn của "gửi đúng một lần"
• Điều tra một truy vấn chậm từ cảnh báo đến bản sửa

Nguồn #

• Karger, Lehman, Leighton, Panigrahy, Levine, Lewin. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. STOC 1997.
• Lamping, Veach. A Fast, Minimal Memory, Consistent Hash Algorithm. arXiv 1406.2294, 2014.
• Thaler, Ravishankar. Using name-based mappings to increase hit rates. IEEE/ACM Transactions on Networking 6(1), 1998.
• Mirrokni, Thorup, Zadimoghaddam. Consistent Hashing with Bounded Loads. SODA 2018.
• HAProxy Configuration Manual 3.0: hash-balance-factor.
• DeCandia và cộng sự. Dynamo: Amazon's Highly Available Key-value Store. SOSP 2007, mục 4.2 và 6.2.
• Apache Cassandra. Dynamo architecture, NEWS.txt bản 4.0, cassandra.yaml 3.11.
• Redis. Redis cluster specification, Scale with Redis Cluster.
• go-jump, bộ giá trị kiểm thử.
• Python. PYTHONHASHSEED. Microsoft. String.GetHashCode.