---
title: "Consistent hashing là gì? Thêm server mà không phải xáo lại toàn bộ cache"
description: "Consistent hashing đặt key và node lên hash ring để thêm node ít xáo trộn cache. Demo Go: mod N chuyển 79,7% key, ring 100 virtual node chỉ chuyển 21,2%."
canonical: "https://200lab.io/blog/consistent-hashing-la-gi"
published: "2026-11-19T02:00:20Z"
updated: "2026-11-19T02:00:20Z"
authors: ["Việt Trần"]
tags: ["Backend", "System Design"]
reading_minutes: 13
access: "public"
---

Giả sử cụm cache của bạn có 4 node, và app chọn node lưu trữ cho mỗi key bằng công thức `hash(key) mod 4`. Khi cần thêm node thứ 5 để chịu tải, công thức đổi thành `mod 5` khiến phần lớn key bị chuyển sang node khác, làm cache gần như trống trở lại và đẩy gánh nặng truy vấn xuống [database](/blog/database-la-gi).

**Consistent hashing là kỹ thuật chia dữ liệu giúp hạn chế số lượng key phải di chuyển sang vị trí mới mỗi khi cụm server thay đổi số lượng node.**

Trong bài này, mình giải thích cơ chế của `hash mod N`, cách hash ring và virtual node giảm số key phải chuyển khi thêm node. Sau phần lý thuyết, mình chạy một demo bằng Go thuần để đếm số key bị chuyển trong từng cách chia.

## hash mod N làm lệch gần hết key khi thêm node

Khi triển khai [chiến lược caching](/blog/caching-la-gi-cac-chien-luoc-caching-hieu-qua) trên nhiều server, cách trực quan nhất để app tìm node chứa key là dùng công thức `hash(key) mod N`, tức chia lấy dư giá trị hash của key cho tổng số node `N`. Cách này chia key khá đều nếu `N` giữ nguyên, nhưng hệ thống thực tế lại thường xuyên phải thêm bớt node khi tải thay đổi hoặc server lỗi.

Khi số server đổi sang `N + 1` hoặc `N - 1`, mẫu số thay đổi khiến phép tính `hash(key) mod N` trả về số dư khác hẳn trước đó. Theo [tài liệu kiến trúc của Apache Cassandra](https://cassandra.apache.org/doc/latest/cassandra/architecture/dynamo.html), việc thêm bớt dù chỉ một node với phép chia modulo cũng làm gần như mọi ánh xạ từ key sang node mất hiệu lực, đẩy đa số key sang một node khác, nơi chưa có dữ liệu của key đó.

![Đổi từ mod 4 sang mod 5, demo có 79,7% key phải đổi node](https://assets.200lab.io/sha256/c0/c064d59321826d94bc4b4967f74099304d8231774b0d64a3f0efac4e745dc2f6/generations/14c671e80383ca8447590e5c79f36b0a832f3cf2def3577ba8e35a31996f8904)

Hệ quả là hàng loạt request từ app bị cache miss trên node mới được chỉ định. App buộc phải đọc lại từ tầng lưu trữ chính để nạp lại cache, làm tăng tải đột ngột cho hệ thống bên dưới ngay lúc cụm server vừa mở rộng.

## Consistent hashing là gì: đặt key và node lên hash ring

Khái niệm này được Karger, Lehman, Leighton, Panigrahy và cộng sự giới thiệu tại hội nghị STOC 1997, theo [bài báo nghiên cứu Consistent Hashing and Random Trees](https://www.cs.princeton.edu/courses/archive/fall09/cos518/papers/chash.pdf), nhằm giảm hiện tượng hot spot cho hệ thống web caching phân tán. Thay vì phụ thuộc vào tổng số node `N`, kỹ thuật này đặt cả node lẫn key lên một vòng tròn giá trị khép kín gọi là hash ring. Với hàm hash 32 bit, vòng tròn chạy từ 0 tới giá trị 32 bit lớn nhất rồi quay về 0.

Hệ thống dùng chung một hàm hash để đặt cả node lẫn key lên vòng tròn. Khi cần lưu hoặc đọc, app hash key ra một điểm trên ring rồi dò theo chiều kim đồng hồ tới node đầu tiên bắt gặp để giao giữ key đó.

Theo [bài báo thiết kế hệ thống Dynamo của Amazon](https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf) tại SOSP 2007, mỗi node trên ring quản lý vùng giá trị nằm giữa nó và node liền trước. Nhờ vậy, khi thêm hoặc bớt server, sự xáo trộn chỉ diễn ra ở các node liền kề vị trí thay đổi, còn phần lớn node khác giữ nguyên dữ liệu.

![Trên hash ring, key thuộc node đầu tiên gặp theo chiều kim đồng hồ](https://assets.200lab.io/sha256/ae/ae2b5ea088ad087daef61531f3454c0222c4c5abf07a387e6b3cf5f2d6253dba/generations/33949d128201052e886cee7eb7f97ccd0e4a412d32807d4e34aa3de901292d6f)

Bài toán chọn server theo giá trị hash không chỉ có ở cache. Nó xuất hiện nhiều trong [system design](/blog/system-design-la-gi), chẳng hạn thuật toán Source IP Hash của [load balancer](/blog/load-balancer-la-gi-chia-khoa-cho-hieu-suat-va-do-tin-cay) đưa request từ cùng một IP về cùng một server.

## Virtual node giúp chia tải đều hơn trên ring

Theo bài báo Dynamo của Amazon, việc đặt mỗi node vật lý thành chỉ một điểm trên hash ring có hai nhược điểm. Vị trí ngẫu nhiên của các node dễ tạo ra các khoảng cách rộng hẹp khác nhau gây lệch tải, đồng thời thiết kế này cũng không tính tới sự khác biệt về sức mạnh phần cứng giữa các server.

Để khắc phục, Dynamo đưa ra khái niệm virtual node (vnode), tức gán cho mỗi server vật lý nhiều điểm đại diện (còn gọi là token) nằm rải rác khắp hash ring. Khi một key dò theo chiều kim đồng hồ chạm vào một vnode, key sẽ được lưu về server vật lý sở hữu vnode đó, giúp tổng phần ring mà mỗi server phụ trách cân bằng hơn.

Khi thêm server mới vào cụm, nó cũng nhận nhiều vnode đan xen với các vnode hiện có để san sẻ một phần tải nhỏ từ nhiều server cũ cùng lúc. Theo tài liệu chính thức, các database phân tán như [Cassandra](/blog/cassandra-la-gi) cũng áp dụng cơ chế token ring kèm vnode tương tự để chia dữ liệu.

![Với virtual node, cache-5 nhận từng phần nhỏ key từ nhiều node cũ](https://assets.200lab.io/sha256/d0/d00824ce5d557b05e4c187c16ec00019a02aea17b1ad89baabe7020187f3cf16/generations/b8e84f46805dc903f6f0ae376cba3e09b6a01d15294dcfaa9d8d1d9c676c6837)

## Chạy thử consistent hashing với Go: 4 lên 5 node

Để thấy rõ sự khác biệt về con số, mình đã chạy một bản demo trên máy cá nhân với phiên bản Go 1.27.3 môi trường linux/amd64, chỉ dùng thư viện chuẩn để đếm ánh xạ key trước và sau khi thêm server. Kịch bản gồm 100.000 key từ `user:0` đến `user:99999` trên cụm 4 node (`cache-1` đến `cache-4`) rồi thêm `cache-5`; ở mức lý tưởng, chỉ cần 1/5 tức khoảng 20,0% số key phải chuyển sang vị trí mới.

Chương trình lấy 4 byte đầu của mã MD5, giống kiểu ketama, để hash cả key lẫn các điểm vnode dạng `cache-1#0`, `cache-1#1` tăng dần. Việc chọn hàm hash ảnh hưởng lớn tới độ đều trên vòng tròn vì với một hàm hash kém, các tên node gần giống nhau có thể cho ra những điểm nằm sát nhau. Ở bản chạy này, mình dùng MD5 để các điểm rải ra hơn.

Chúng ta thử xem đoạn code dưới đây nha:

```go
// consistent_hashing.go: a 4-node cache cluster gets a 5th node.
// Count how many of 100,000 keys move to another node with
// hash mod N, a hash ring, and a hash ring with virtual nodes.
package main

import (
	"crypto/md5"
	"encoding/binary"
	"fmt"
	"sort"
	"strconv"
)

// hashKey takes the first 4 bytes of MD5 (ketama-style), so similar names still spread out.
func hashKey(s string) uint32 {
	sum := md5.Sum([]byte(s))
	return binary.BigEndian.Uint32(sum[:4])
}

// Placer maps a key to a node name.
type Placer interface{ Node(key string) string }

// ModN: node = hash(key) % N.
type ModN struct{ nodes []string }

func (m ModN) Node(key string) string { return m.nodes[hashKey(key)%uint32(len(m.nodes))] }

// Ring: each node owns the arc that ends at its point(s) on the ring.
type Ring struct {
	points []uint32
	owner  map[uint32]string
}

func NewRing(nodes []string, vnodes int) *Ring {
	r := &Ring{owner: map[uint32]string{}}
	for _, n := range nodes {
		for v := 0; v < vnodes; v++ {
			p := hashKey(n + "#" + strconv.Itoa(v))
			r.points = append(r.points, p)
			r.owner[p] = n
		}
	}
	sort.Slice(r.points, func(i, j int) bool { return r.points[i] < r.points[j] })
	return r
}

func (r *Ring) Node(key string) string {
	h := hashKey(key)
	i := sort.Search(len(r.points), func(i int) bool { return r.points[i] >= h })
	if i == len(r.points) {
		i = 0 // wrap around the ring
	}
	return r.owner[r.points[i]]
}

func compare(name string, before, after Placer, keys []string, newNodes []string) {
	moved, toNew := 0, 0
	load := map[string]int{}
	for _, k := range keys {
		a := after.Node(k)
		if before.Node(k) != a {
			moved++
			if a == "cache-5" {
				toNew++
			}
		}
		load[a]++
	}
	min, max := len(keys), 0
	for _, n := range newNodes {
		if load[n] < min {
			min = load[n]
		}
		if load[n] > max {
			max = load[n]
		}
	}
	fmt.Printf("%-24s moved=%6d (%.1f%%), moved to cache-5=%d, keys per node after: min=%d max=%d\n",
		name, moved, 100*float64(moved)/float64(len(keys)), toNew, min, max)
	for _, n := range newNodes {
		fmt.Printf("    %s=%d", n, load[n])
	}
	fmt.Println()
}

func main() {
	keys := make([]string, 100000)
	for i := range keys {
		keys[i] = "user:" + strconv.Itoa(i)
	}
	four := []string{"cache-1", "cache-2", "cache-3", "cache-4"}
	five := append(append([]string{}, four...), "cache-5")
	fmt.Printf("keys=%d, nodes %d -> %d, ideal move = 1/%d = %.1f%%\n", len(keys), len(four), len(five), len(five), 100.0/float64(len(five)))

	compare("mod N", ModN{four}, ModN{five}, keys, five)
	compare("ring, 1 point per node", NewRing(four, 1), NewRing(five, 1), keys, five)
	compare("ring, 100 vnodes", NewRing(four, 100), NewRing(five, 100), keys, five)
	compare("ring, 200 vnodes", NewRing(four, 200), NewRing(five, 200), keys, five)
}
```

```text
$ go version
go version go1.27.3 linux/amd64
$ go run .
keys=100000, nodes 4 -> 5, ideal move = 1/5 = 20.0%
mod N                    moved= 79729 (79.7%), moved to cache-5=19873, keys per node after: min=19873 max=20142
    cache-1=19969    cache-2=19986    cache-3=20030    cache-4=20142    cache-5=19873
ring, 1 point per node   moved=  8159 (8.2%), moved to cache-5=8159, keys per node after: min=1444 max=38889
    cache-1=1444    cache-2=16585    cache-3=34923    cache-4=38889    cache-5=8159
ring, 100 vnodes         moved= 21196 (21.2%), moved to cache-5=21196, keys per node after: min=19045 max=21196
    cache-1=19577    cache-2=19045    cache-3=19746    cache-4=20436    cache-5=21196
ring, 200 vnodes         moved= 21536 (21.5%), moved to cache-5=21536, keys per node after: min=17705 max=21536
    cache-1=19335    cache-2=17705    cache-3=19949    cache-4=21475    cache-5=21536
```

![Demo 100.000 key, 4 lên 5 node: mod N chuyển 79,7%, vnode khoảng 21%, gần mức lý tưởng 20%](https://assets.200lab.io/sha256/bb/bbd42032d046cfe0b076f193fcd2b80a17310f6578cf4ac45c900b3c2d47e2dd/generations/b0ce58684e4c662411a09efcd3686603550470cb220ab10b563a8d03ae052610)

Với phương pháp `mod N`, số lượng key bị đổi chỗ là `moved=79729` (79,7%), dù tải sau đó trên 5 server khá đều, từ 19873 đến 20142 key mỗi node. Đáng chú ý, chỉ có 19873 key thực sự vào node mới `cache-5`, còn phép trừ 79729 - 19873 cho thấy tới 59856 key đổi chỗ giữa các node cũ dù không cần từ `cache-1` đến `cache-4`.

Với hash ring 1 điểm mỗi node, số key di chuyển giảm còn `moved=8159` (8,2%) và toàn bộ 8159 key này đều chuyển thẳng sang `cache-5`. Tuy nhiên tải bị lệch rất nặng: `cache-5` chỉ đỡ 8159 key, `cache-1` giữ 1444 key, trong khi `cache-3` và `cache-4` gánh tới 34923 và 38889 key (chênh lệch min 1444 tới max 38889).

Khi nâng lên 100 vnode mỗi node vật lý, có `moved=21196` key di chuyển (21,2%, khá sát mức lý tưởng 20,0%), tất cả đều đi vào `cache-5` và lượng key mỗi server nằm trong khoảng 19045 đến 21196. Thử tiếp với 200 vnode mỗi node, số key di chuyển là `moved=21536` (21,5%) vào hết `cache-5`, nhưng tải mỗi node nằm từ 17705 đến 21536, cho thấy tăng vnode không đồng nghĩa lúc nào tải cũng đều hơn (khoảng min-max 17705-21536 rộng hơn chút so với 19045-21196 của 100 vnode).

Tất nhiên, đây chỉ là kết quả từ một lần chạy với bộ key giả lập trên bộ nhớ để quan sát cách phân bổ. Chương trình demo này chạy trên máy cá nhân chứ không phải môi trường production, không đo độ trễ network, không chạy cache server thật và chưa thử kịch bản xóa node.

## Redis Cluster dùng hash slot, không dùng consistent hashing

Không phải hệ thống phân tán nào cũng dùng consistent hashing để chia dữ liệu, điển hình là [Redis](/blog/redis-la-gi) ở chế độ phân cụm. Theo [tài liệu mở rộng quy mô của Redis Cluster](https://redis.io/docs/latest/operate/oss_and_stack/management/scaling/), hệ thống này không dùng consistent hashing mà chia không gian dữ liệu thành 16384 khe cố định gọi là hash slot theo công thức:

```text
HASH_SLOT = CRC16(key) mod 16384
```

Trong cách làm này, mỗi node vật lý nắm giữ một nhóm hash slot nhất định, và khi thêm node mới thì hệ thống chỉ cần chuyển một số slot sang node đó mà không đổi công thức `mod 16384`. Hiểu rõ cơ chế phân mảnh có sẵn của công nghệ lưu trữ đang dùng sẽ giúp bạn tránh viết thừa các lớp điều phối chia tải ở tầng app.

![Redis Cluster băm key bằng CRC16(key) mod 16384 ra hash slot, rồi chia dải slot cho các master](https://assets.200lab.io/sha256/34/34d3c201b19e160398a0d5d52714058fd2d20a95cfdf76dbd956675f5778b7d2/generations/819a0d8911166fc3dfce454299f0837e58fb6e0d68ec74cb85984a73b7c5bbae)

## Khi nào không cần consistent hashing và sai lầm hay gặp

Bạn không cần hash ring khi cụm server có số lượng node cố định, vì lúc này `hash(key) mod N` vừa đơn giản vừa chia tải đều. Trong demo, mỗi node giữ từ 19873 đến 20142 key. Bạn cũng không nên tự cài thêm consistent hashing chồng lên ở phía app nếu đã dùng các hệ thống có sẵn cơ chế chia dữ liệu nội tại như Redis Cluster (hash slot) hay Cassandra (token ring).

Nếu thực sự cần tự triển khai hash ring ở tầng app, hãy tránh chỉ đặt 1 điểm mỗi node, vì demo cho thấy tải lệch từ 1444 tới 38889 key, đồng thời phải chọn hàm hash tốt để các tên node có cùng tiền tố không cho ra các điểm sát nhau. Ngoài ra, dù tỷ lệ key phải chuyển giảm về khoảng 1/N, tức 20% với 5 node, lượng key đổi chỗ này vẫn gây cache miss cùng lúc và có thể kéo theo cache stampede dồn request xuống database khi tải cao.

Cuối cùng, khi nhiều instance của app cùng tự tính hash ring ở phía client, mình đoán một lỗi rất dễ gặp là cập nhật danh sách node không đồng thời. Nếu instance A đã nhận cấu hình 5 node còn instance B vẫn giữ 4 node, cùng một key sẽ bị trỏ sang hai cache server khác nhau.

Mình chọn hash ring có virtual node khi cụm cache thường xuyên phải thêm bớt server và mỗi lần cache miss đều gây tốn tài nguyên database, vì trong demo cách này giữ tỷ lệ chuyển key ở mức khoảng 21% thay vì 79,7% và phân bổ tải khá đều từ 19045 đến 21196 key. Ngược lại, khi số lượng node cố định thì mình giữ nguyên `mod N` cho đơn giản, còn khi đã dùng Redis Cluster hay Cassandra thì mình để các hệ thống đó tự chia dữ liệu theo cơ chế chuẩn của chúng.

## Đọc thêm

- [Caching là gì và các chiến lược caching hiệu quả](/blog/caching-la-gi-cac-chien-luoc-caching-hieu-qua): nắm các cách đọc ghi cache cơ bản như cache-aside trước khi chia dữ liệu ra nhiều node.
- [Redis là gì? Bạn có đang sử dụng hết các tính năng của Redis](/blog/redis-la-gi): ôn các tính năng chính của Redis trước khi tìm hiểu Redis Cluster.
- [Cassandra là gì](/blog/cassandra-la-gi): tổng quan về Cassandra, database phân tán mà tài liệu chính thức mô tả dùng token ring và vnode.
- [Load balancer là gì](/blog/load-balancer-la-gi-chia-khoa-cho-hieu-suat-va-do-tin-cay): các thuật toán chia request như Round Robin và Source IP Hash.

## Đọc thêm

- [Cache stampede: khi cache hết hạn và hàng loạt request dồn xuống database](https://200lab.io/blog/cache-stampede-la-gi.md): Cache stampede xảy ra khi key hết hạn và nhiều request cùng gọi xuống database. singleflight gộp lời gọi trong một process, TTL jitter rải thời điểm hết hạn.
- [Connection pool là gì, vì sao service Go treo dù database còn rảnh](https://200lab.io/blog/connection-pool-la-gi.md): Service Go timeout hàng loạt trong khi database vẫn rảnh? Bài này giúp bạn hiểu connection pool trong Go hoạt động ra sao và cách chỉnh pool cho đúng tải.
- [Outbox pattern: ghi database và gửi message mà không mất đơn](https://200lab.io/blog/outbox-pattern-la-gi.md): Outbox pattern là gì: ghi đơn và event trong cùng một transaction, rồi relay gửi sau; demo PostgreSQL cho thấy dual-write làm mất message khi service restart.
- [Retry với backoff và jitter: gọi lại API lỗi mà không làm sập server](https://200lab.io/blog/retry-la-gi.md): Retry là gì: gọi lại khi lỗi tạm dễ thành thundering herd; exponential backoff chưa đủ, cần jitter để lệch nhịp và đo đỉnh request theo giây.
- [Distributed lock là gì, vì sao lock Redis vẫn để dữ liệu bị ghi đè](https://200lab.io/blog/distributed-lock-la-gi.md): Distributed lock giúp nhiều instance không chạy trùng một việc. Redis SET NX chặn được chạy cùng lúc, nhưng lock hết hạn giữa chừng thì cần thêm fencing token.
- [Mọi bài viết chủ đề Backend](https://200lab.io/blog/tags/backend.md)

Toàn bộ nội dung: https://200lab.io/llms.txt
