Consistent Hashing: Phân Bổ Tải Không Cần Xáo Trộn Toàn Bộ

Naive hashing (hash(key) % N) hoạt động tốt cho đến khi bạn thêm hoặc xóa một node — lúc đó N thay đổi và gần như mọi key đều map sang server khác. Với một cache hoặc shard phân tán, điều này đồng nghĩa với một đợt cache miss hàng loạt hoặc một cuộc di dời dữ liệu quy mô lớn, đúng vào lúc bạn cần nó ít nhất.

Consistent hashing giải quyết vấn đề này bằng cách map cả node lẫn key lên cùng một vòng (ring), nên khi thay đổi topology chỉ cần remap các key nằm giữa node thay đổi và node lân cận của nó.

Vòng Hash (Ring)

Mỗi node được hash lên ring (thường nhiều lần — xem phần "Virtual Node" bên dưới). Để tìm node sở hữu một key, hash key đó rồi đi theo chiều kim đồng hồ cho đến khi gặp node đầu tiên.

Thêm hoặc Xóa Node

Khi node B rời đi, chỉ những key từng map vào B mới phải di chuyển — sang node liền kề của B theo chiều kim đồng hồ. Mọi key khác vẫn giữ nguyên vị trí. Đó chính là điểm mấu chốt: chỉ khoảng 1/N keyspace di chuyển mỗi lần thay đổi topology, không phải toàn bộ keyspace.

Virtual Node (Bản Sao Ảo)

Hash trực tiếp tên node lên ring dễ tạo ra điểm nóng — một số node sở hữu cung (arc) lớn hơn hẳn các node khác. Cách khắc phục: hash mỗi node nhiều lần, ví dụ node-A#0, node-A#1, ..., node-A#149 (150 virtual node là mặc định phổ biến). Càng nhiều virtual node, phân bổ càng đều, đổi lại ring lưu trong bộ nhớ càng lớn.

Triển Khai

class ConsistentHash
{
    private array $ring = [];
    private array $sortedKeys = [];
    private int $replicas;

    public function __construct(int $replicas = 150)
    {
        $this->replicas = $replicas;
    }

    public function addNode(string $node): void
    {
        for ($i = 0; $i < $this->replicas; $i++) {
            $this->ring[$this->hash("$node#$i")] = $node;
        }
        $this->sortedKeys = $this->sortedRingKeys();
    }

    public function getNode(string $key): ?string
    {
        if (empty($this->sortedKeys)) {
            return null;
        }

        $hash = $this->hash($key);
        foreach ($this->sortedKeys as $ringKey) {
            if ($ringKey >= $hash) {
                return $this->ring[$ringKey];
            }
        }

        return $this->ring[$this->sortedKeys[0]];
    }

    private function sortedRingKeys(): array
    {
        $keys = array_keys($this->ring);
        sort($keys);
        return $keys;
    }

    private function hash(string $value): int
    {
        return crc32($value);
    }
}

import bisect
import zlib


class ConsistentHash:
    def __init__(self, replicas: int = 150):
        self.replicas = replicas
        self.ring: dict[int, str] = {}
        self.sorted_keys: list[int] = []

    def add_node(self, node: str) -> None:
        for i in range(self.replicas):
            self.ring[self._hash(f"{node}#{i}")] = node
        self.sorted_keys = sorted(self.ring.keys())

    def get_node(self, key: str) -> str | None:
        if not self.sorted_keys:
            return None

        h = self._hash(key)
        index = bisect.bisect_left(self.sorted_keys, h)
        if index == len(self.sorted_keys):
            index = 0

        return self.ring[self.sorted_keys[index]]

    @staticmethod
    def _hash(value: str) -> int:
        return zlib.crc32(value.encode())

Các Lỗi Thường Gặp

Quá ít virtual node dẫn đến tải không đều, tạo điểm nóng trên một vài node vật lý. Dùng hàm hash yếu hoặc phân bố kém càng làm vấn đề tệ hơn — nên ưu tiên CRC32 hoặc xxHash thay vì hash cộng dồn byte đơn giản. Quên xóa hết virtual node của một node khi remove để lại các entry ma, route traffic vào một server đã chết. Và hash lại toàn bộ keyspace mỗi lần đổi topology thì phá vỡ hoàn toàn mục đích ban đầu — chỉ ring nên thay đổi, không phải mapping của từng key.

Khi Nào Nên Dùng

Cache phân tán dùng client-side sharding, chọn CDN edge, distributed hash table, database sharded, và load balancer cần session affinity mà không cần một bộ điều phối trung tâm. Nếu cluster của bạn có kích thước cố định và hiếm khi thay đổi, modulo hashing đơn giản vẫn ổn và dễ dùng hơn.