Consistent Hashing

Thêm một node cache, mất 80% dữ liệu cache

gdev-shop có 4 node cache phân tán. Mỗi khóa (ví dụ product:7) được gán cho một node bằng công thức đơn giản: hash(khóa) mod 4. Cách này đều và nhanh. Đợt khuyến mãi tới, nhóm thêm node thứ năm và đổi công thức thành hash(khóa) mod 5. Ngay lập tức, phần lớn khóa bị ánh xạ sang node khác với node đang giữ nó. Một request đọc product:7 đến node mới theo công thức, nhưng dữ liệu vẫn nằm ở node cũ, nên cache miss. Gần như toàn bộ cache coi như vô dụng cùng một lúc, và database nhận một cơn lũ truy vấn.

Ta tính được con số: với mod 4 và mod 5, chỉ khoảng 20% khóa có cùng kết quả (các khóa mà k mod 4 bằng k mod 5), nên khoảng 80% khóa đổi node. Đây là vấn đề mà consistent hashing sinh ra để giải quyết.

Consistent hashing là gì?

Consistent hashing (băm nhất quán) là kỹ thuật ánh xạ khóa sang node sao cho khi thêm hoặc bớt một node, chỉ một phần nhỏ khóa phải đổi chỗ, thay vì gần như tất cả. Với N node, thêm một node chỉ di chuyển trung bình khoảng 1 trên N+1 số khóa.

Cách hoạt động: vòng băm

1. Tưởng tượng một vòng tròn các giá trị băm, từ 0 đến giá trị lớn nhất, rồi nối đầu cuối lại. Đây là hash ring.
2. Mỗi node được băm (ví dụ băm tên hoặc địa chỉ) và đặt tại một vị trí trên vòng.
3. Mỗi khóa cũng được băm ra một vị trí trên vòng.
4. Để biết khóa thuộc node nào: từ vị trí của khóa, đi theo chiều kim đồng hồ đến node đầu tiên gặp. Node đó giữ khóa.

Ví dụ đơn giản hóa với không gian băm từ 0 đến 99 và ba node:

Mỗi node chịu trách nhiệm cho đoạn của vòng từ node trước nó (không tính) đến chính nó. B giữ các khóa trong khoảng (10, 40], C giữ (40, 70], A giữ (70, 99] và [0, 10].

Cách đọc hình kiến trúc. Cả node (A, B, C) và khóa (k1 đến k4) được băm thành vị trí trên một vòng. Mỗi khóa thuộc node đầu tiên gặp khi đi theo chiều kim đồng hồ: k1 ở vị trí 25 thuộc B ở vị trí 40, còn k3 ở 85 đi vòng qua điểm cuối và thuộc A ở 10. Khi bớt B, chỉ khóa nằm trong đoạn của B (k1) chuyển sang C, các khóa khác không đổi. Đó là lý do consistent hashing chỉ di chuyển một phần nhỏ khóa, trong khi hash mod N di chuyển phần lớn.

Cách đọc sơ đồ

Luồng tra cứu một khóa gồm bốn bước: băm khóa thành một vị trí trên vòng, đi theo chiều kim đồng hồ từ vị trí đó, node đầu tiên gặp phải sở hữu khóa, và request được gửi đến node ấy. Điều quan trọng là phép chọn node chỉ phụ thuộc vào vị trí trên vòng, không phụ thuộc vào tổng số node, nên thay đổi một node chỉ tác động đến vùng lân cận trên vòng.

Thêm một node: chỉ một đoạn nhỏ di chuyển

Thêm node D tại vị trí 55:

• Trước đó, các khóa trong khoảng (40, 70] thuộc C.
• Sau khi thêm D tại 55, các khóa trong (40, 55] gặp D trước, nên chuyển từ C sang D. Các khóa trong (55, 70] vẫn thuộc C.
• Khóa k2 (vị trí 55) chuyển từ C sang D. Các khóa còn lại, k1, k3, k4, không đổi.

Cách đọc sơ đồ

Khi thêm D, chỉ node kế tiếp của nó theo chiều kim đồng hồ (C) mất một phần khóa, và phần đó chuyển sang D. A và B không bị ảnh hưởng. Với dữ liệu phân bố đều, node mới chỉ nhận khoảng một trên N+1 tổng số khóa, thay vì làm xáo trộn gần như tất cả như mod N. Khi bớt một node thì ngược lại: các khóa của nó được chuyển cho node kế tiếp theo chiều kim đồng hồ, các node khác không đổi.

Nhờ đó cache vẫn dùng được phần lớn: khoảng 80% khóa vẫn nằm đúng nơi, thay vì mất gần hết như đầu bài.

Virtual node: giải quyết vấn đề phân bố không đều

Nếu mỗi node chỉ có một điểm trên vòng, vị trí ngẫu nhiên có thể làm các đoạn rất không đều: một node có thể phải gánh đoạn dài gấp nhiều lần node khác. Khi một node bị bớt đi, toàn bộ đoạn của nó dồn sang một node kế tiếp, có thể làm node đó quá tải.

Giải pháp: virtual node (node ảo). Mỗi node thật được đặt tại nhiều điểm trên vòng (ví dụ 100 đến 200 điểm), mỗi điểm là một node ảo. Hệ quả:

• Các đoạn nhỏ và rải đều hơn, nên tải cân bằng hơn.
• Khi một node thật bị bớt, các đoạn nhỏ của nó chuyển cho nhiều node khác nhau, nên phụ tải chia ra thay vì dồn vào một.
• Có thể cho node mạnh hơn nhiều node ảo hơn để nhận nhiều khóa hơn.

Một cài đặt tối giản bằng Java để minh họa ý tưởng:

import java.util.Map;
import java.util.TreeMap;

public class HashRing {
    private final TreeMap<Integer, String> ring = new TreeMap<>();
    private final int virtualNodes;

    public HashRing(int virtualNodes) {
        this.virtualNodes = virtualNodes;
    }

    public void addNode(String node) {
        for (int i = 0; i < virtualNodes; i++) {
            ring.put(hash(node + "#" + i), node);
        }
    }

    public void removeNode(String node) {
        for (int i = 0; i < virtualNodes; i++) {
            ring.remove(hash(node + "#" + i));
        }
    }

    public String nodeFor(String key) {
        Map.Entry<Integer, String> entry = ring.ceilingEntry(hash(key));
        return entry != null ? entry.getValue() : ring.firstEntry().getValue();
    }

    private int hash(String value) {
        return value.hashCode() & 0x7fffffff;
    }
}

TreeMap giữ các vị trí đã sắp xếp. ceilingEntry tìm vị trí lớn hơn hoặc bằng vị trí của khóa, tức "đi theo chiều kim đồng hồ". Nếu không có (khóa nằm sau điểm lớn nhất), nó quay vòng về điểm đầu tiên. Lưu ý đây là mã minh họa: hashCode của String không phân bố đủ đều cho sản xuất, nơi người ta dùng hàm băm tốt hơn như Murmur, và cần xử lý trường hợp vòng rỗng.

Dùng ở đâu, và những hạn chế

Consistent hashing xuất hiện ở:

• Cache phân tán: mỗi khóa luôn tìm đến cùng một node, thêm bớt node ít làm mất cache.
• Chia dữ liệu (sharding) và các database phân tán: giảm việc di chuyển dữ liệu khi thay đổi số node.
• Cân bằng tải có tính "dính theo khóa": cùng một khóa vào cùng backend, và ít bị xáo trộn khi backend đổi.

Hạn chế và cái giá:

• Vẫn có di chuyển dữ liệu: dù ít, vẫn cần chuyển phần dữ liệu thuộc đoạn bị thay đổi.
• Khóa nóng không biến mất: một khóa nhận lượng truy cập quá lớn vẫn dồn vào một node dù băm tốt đến đâu.
• Phức tạp hơn so với mod N, cần quản lý danh sách node và vòng chung giữa các client hoặc proxy.
• Dữ liệu cache trên node bị bớt vẫn mất: consistent hashing chỉ giảm phạm vi mất chứ không loại bỏ nó.

Những hiểu lầm phổ biến

• "Consistent hashing không làm di chuyển dữ liệu." Nó giảm mạnh lượng di chuyển (khoảng 1 trên N+1) chứ không bằng không.
• "Consistent hashing tự phân bố đều." Phải có virtual node, nếu không các đoạn có thể rất lệch.
• "Consistent hashing giải quyết khóa nóng." Không. Khóa nóng là vấn đề của phân bố truy cập chứ không phải của hàm ánh xạ.
• "Chỉ dùng cho cache." Dùng cho mọi thứ cần ánh xạ khóa sang node ổn định khi số node thay đổi.

Must Know, Good to Know, Advanced

• Must Know: vì sao mod N làm khoảng 80% khóa đổi chỗ khi thêm node; vòng băm và quy tắc "đi theo chiều kim đồng hồ gặp node đầu tiên"; thêm hoặc bớt node chỉ ảnh hưởng một đoạn; virtual node cân bằng tải.
• Good to Know: cài đặt bằng cấu trúc sắp xếp; các nơi ứng dụng; vẫn có khóa nóng.
• Advanced: rendezvous hashing, jump hash, các biến thể có giới hạn tải. Chỉ cần biết rằng có các thuật toán thay thế với đánh đổi khác.

Tự kiểm tra

1. Với vòng ở trên, nếu bớt node B (vị trí 40), khóa k1 (vị trí 25) thuộc node nào?
2. Vì sao node ảo giúp việc cân bằng tải tốt hơn khi một node thật bị bớt?
3. Nêu một vấn đề mà consistent hashing không giải quyết được.

Đáp án gợi ý

1. Khi bớt node B (vị trí 40), khóa k1 (vị trí 25) đi theo chiều kim đồng hồ và gặp node tiếp theo là C (vị trí 70), nên k1 chuyển sang C. Các khóa khác không đổi, chỉ khóa trong đoạn của B bị ảnh hưởng.
2. Với node ảo, mỗi node thật có nhiều điểm rải rác trên vòng. Khi một node thật bị bớt, đoạn của nó chia cho nhiều node còn lại thay vì dồn hết cho một node kế bên, nên tải phân bố đều hơn và không có node nào bị gánh gấp đôi.
3. Consistent hashing không giải quyết khóa nóng: một khóa được truy cập quá nhiều vẫn nằm ở một node nên node đó quá tải. Nó cũng không tự đảm bảo bản sao hay độ bền dữ liệu, cần cơ chế khác (replication, cache nhiều bản cho khóa nóng).

Nếu chỉ nhớ 3 điều

1. hash mod N làm khoảng 80% khóa đổi node khi đổi từ 4 sang 5 node; consistent hashing chỉ di chuyển khoảng 1 trên N+1.
2. Khóa thuộc node đầu tiên gặp khi đi theo chiều kim đồng hồ trên vòng băm; thêm hoặc bớt node chỉ ảnh hưởng một đoạn.
3. Dùng virtual node để cân bằng tải, và nhớ rằng khóa nóng vẫn cần cách xử lý riêng.