Top 10 Thuật Toán System Design Các Bạn Nên Biết - Consistent Hashing

Sep 8, 2024 13 min read bigdata

Hashing là gì?

Hasing, tiếng việt có thể dịch là “băm” là quá trình chúng ta đưa một chuỗi vào một hàm băm và băm nó ra, rồi nén nó lại trong một vùng không gian, thu được vị trí của chuỗi đầu vào trong vùng không gian nén đó.

Công thức biểu diễn

1
2vi_tri = ham_bam(dau_vao)%kich_thuoc_khong_gian

Ví dụ:

 1
 2Giả sử chúng ta có kích thước không gian kich_thuoc_khong_gian = 10
 3
 4Chúng ta muốn lưu trữ chuỗi đầu vào là dau_vao =  "Hello"
 5
 6Sử dụng hàm băm ham_bam("Hello") ra kết quả là 16
 7
 8ta có vi_tri = ham_bam("Hello") % 10 = 16 % 10 = 6
 9
10Vậy chuỗi  dữ liệu "Hello" sẽ được lưu trữ tại vị trí 6 trong không gian nhớ size 10.

Quá trình này cho phép chúng ta biến một chuỗi dữ liệu thành một vị trí trong không gian nhớ, giúp cho việc lưu trữ và truy xuất dữ liệu trở nên hiệu quả hơn.

Consistent Hashing là gì?

Consistent Hashing (băm nhất quán) là kỹ thuật được sử dụng để phân phối các khoá (key) đều trên các cụm máy tính (clusters), mục tiêu là giảm thiểu số lượng các khoá cần di chuyển khi thêm nodes hoặc xoá nodes ( xoá trong trường hợp lỗi , thêm trong trường hợp muốn scale hệ thống), giảm số lượng các khoá cần di chuyển góp phần làm ổn định hệ thống, và giảm tác động tiêu cực của sự thay đổi này lên hệ thống

Mục tiêu:

  • Phân phối các khóa (keys) đều trên một cụm các nút (nodes) trong hệ thống.

  • Giảm thiểu số lượng khóa cần di chuyển khi thêm hoặc xóa nút khỏi cụm.

Cấu trúc:

  • Sử dụng một vòng ảo (hashring) để biểu diễn các yêu cầu của server/clients và các server nodes.

  • Số lượng vị trí trên vòng không cố định, nhưng được coi là có vô số điểm.

  • Các nút máy chủ có thể được đặt tại các vị trí ngẫu nhiên trên vòng bằng cách sử dụng hàm băm (hashing).

  • Các yêu cầu (requests) từ người dùng, máy tính hoặc chương trình không có máy chủ cũng được đặt trên cùng một vòng bằng cách sử dụng cùng một hàm băm.

Lợi ích:

  • Khi thêm hoặc xóa nút khỏi cụm, chỉ cần di chuyển một số nhỏ khóa đến các nút khác.

  • Giảm thiểu tác động của việc thêm hoặc xóa nút đến toàn bộ hệ thống.

  • Cải thiện hiệu suất và độ tin cậy của hệ thống.

Cách thức hoạt động:

  1. Khi một yêu cầu được gửi đến hệ thống, nó sẽ được băm (hash) để tạo ra một giá trị băm.

  2. Giá trị băm này sẽ được sử dụng để xác định vị trí của yêu cầu trên vòng ảo.

  3. Hệ thống sẽ tìm nút máy chủ gần nhất với vị trí của yêu cầu trên vòng và gửi yêu cầu đến nút đó.

  4. Nếu nút máy chủ đó không khả dụng, hệ thống sẽ tìm nút máy chủ tiếp theo trên vòng và gửi yêu cầu đến nút đó.

Kỹ thuật Consistent Hashing giúp phân phối tải trọng đều trên các nút máy chủ và giảm thiểu tác động của việc thêm hoặc xóa nút đến toàn bộ hệ thống.

Ứng dụng của Consistent Hashing

Ngày nay Consistent Hashing là một kỹ thuật phổ biến được sử dụng trong các hệ thống phân tán để giải quyết thách thức phân phối hiệu quả các khóa hoặc phần tử dữ liệu trên nhiều nút/máy chủ trong một mạng lưới.

Bằng cách sử dụng Consistent Hashing, các hệ thống phân tán có thể đạt được nhiều lợi ích, bao gồm:

  1. Cải thiện khả năng mở rộng: Consistent Hashing cho phép các hệ thống phân tán mở rộng dễ dàng hơn, vì các nút mới có thể được thêm hoặc xóa mà không làm gián đoạn toàn bộ hệ thống.

  2. Giảm thiểu chi phí ánh xạ lại: Bằng cách giảm thiểu số lượng các phép ánh xạ lại cần thiết, Consistent Hashing giúp giảm thiểu chi phí liên quan đến việc thêm hoặc xóa nút, giúp duy trì hiệu suất của hệ thống.

  3. Tăng cường khả năng chịu lỗi: Consistent Hashing giúp phân phối các phần tử dữ liệu trên nhiều nút, giúp tăng cường khả năng chịu lỗi của hệ thống và giảm thiểu rủi ro mất dữ liệu trong trường hợp nút bị lỗi.

  4. Cân bằng tải tốt hơn: Consistent Hashing có thể giúp phân phối tải trên các nút một cách đồng đều hơn, giúp cải thiện hiệu suất của hệ thống và giảm thiểu rủi ro các điểm nóng.

Consistent Hashing được sử dụng rộng rãi trong các hệ thống phân tán khác nhau, bao gồm:

  1. Cơ sở dữ liệu phân tán: Consistent Hashing được sử dụng trong các cơ sở dữ liệu phân tán để phân phối các phần tử dữ liệu trên nhiều nút và cải thiện hiệu suất của hệ thống.

  2. Hệ thống lưu trữ đệm: Consistent Hashing được sử dụng trong các hệ thống lưu trữ đệm để phân phối các phần tử đệm trên nhiều nút và cải thiện hiệu suất của hệ thống.

  3. Mạng lưới phân phối nội dung (CDN): Consistent Hashing được sử dụng trong các mạng lưới phân phối nội dung để phân phối nội dung trên nhiều nút và cải thiện hiệu suất của hệ thống.

  4. Hệ thống lưu trữ đám mây: Consistent Hashing được sử dụng trong các hệ thống lưu trữ đám mây để phân phối các phần tử dữ liệu trên nhiều nút và cải thiện hiệu suất của hệ thống.

Tóm lại, Consistent Hashing là một kỹ thuật mạnh mẽ giúp các hệ thống phân tán phân phối các khóa hoặc phần tử dữ liệu trên nhiều nút một cách hiệu quả, giảm thiểu số lượng các phép ánh xạ lại cần thiết khi thêm hoặc xóa nút, và cải thiện khả năng mở rộng, khả năng chịu lỗi và cân bằng tải của hệ thống.

Implement Consistent Hashing

Để triển khai một hệ thống sử dụng consistent hasing, chúng ta cần xác định 7 bước sau

Bước 1: Chọn hàm băm

  • Chọn một hàm băm tạo ra một dải giá trị băm phân bố đều. Các lựa chọn phổ biến bao gồm MD5, SHA-1 hoặc SHA-256.

Bước 2: Định nghĩa vòng băm

  • Biểu diễn dải giá trị băm như một vòng.

  • Vòng này nên bao phủ toàn bộ dải giá trị băm có thể và được phân bố đều.

Bước 3: Gán nút vào vòng

  • Gán mỗi nút trong hệ thống một vị trí trên vòng băm.

  • Điều này thường được thực hiện bằng cách băm định danh của nút bằng hàm băm đã chọn.

Bước 4: Ánh xạ khóa

  • Khi cần lưu trữ hoặc truy xuất một khóa, băm khóa bằng hàm băm đã chọn để thu được giá trị băm.

  • Tìm vị trí trên vòng băm nơi giá trị băm rơi vào.

  • Đi theo chiều kim đồng hồ trên vòng để tìm nút đầu tiên gặp phải. Nút này trở thành nút sở hữu khóa.

Bước 5: Thêm nút

  • Khi một nút mới được thêm vào, tính toán vị trí của nó trên vòng băm bằng hàm băm.

  • Xác định dải khóa sẽ được sở hữu bởi nút mới. Điều này thường liên quan đến việc tìm nút tiền nhiệm trên vòng.

  • Cập nhật vòng để bao gồm nút mới và ánh xạ lại các khóa bị ảnh hưởng đến nút mới.

Bước 6: Xóa nút

  • Khi một nút bị xóa, xác định vị trí của nó trên vòng băm.

  • Xác định dải khóa sẽ bị ảnh hưởng bởi việc xóa nút. Điều này thường liên quan đến việc tìm nút kế tiếp trên vòng.

  • Cập nhật vòng để loại trừ nút đã xóa và ánh xạ lại các khóa bị ảnh hưởng đến nút kế tiếp.

Bước 7: Cân bằng tải

  • Định kỳ kiểm tra tải trên mỗi nút bằng cách theo dõi số lượng khóa nó sở hữu.

  • Nếu có sự mất cân bằng, hãy xem xét việc phân phối lại một số khóa để đạt được sự phân bố đều hơn.

Dưới dây là code golang , coi như là demo example 7 bước trên

  1
  2package main
  3
  4import (
  5	"crypto/md5"
  6	"fmt"
  7	"sort"
  8	"strconv"
  9	"sync"
 10)
 11
 12type ConsistentHashRing struct {
 13	ring       map[uint64]string
 14	sortedKeys []uint64
 15	replicas   int
 16	mu         sync.RWMutex
 17}
 18
 19func NewConsistentHashRing(replicas int) *ConsistentHashRing {
 20	return &ConsistentHashRing{
 21		ring:       make(map[uint64]string),
 22		sortedKeys: make([]uint64, 0),
 23		replicas:   replicas,
 24	}
 25}
 26
 27// Bước 1: Chọn hàm băm, ở đây dùng md5.
 28
 29func (chr *ConsistentHashRing) getHash(value string) uint64 {
 30	hash := md5.Sum([]byte(value))
 31	var hashValue uint64
 32	for i := 0; i < 8; i++ {
 33		hashValue = (hashValue << 8) | uint64(hash[i])
 34	}
 35	return hashValue
 36}
 37
 38// Bước 3: Gán nút vào vòng.
 39func (chr *ConsistentHashRing) assignNodesToRing() {
 40	sort.Slice(chr.sortedKeys, func(i, j int) bool {
 41		return chr.sortedKeys[i] < chr.sortedKeys[j]
 42	})
 43}
 44
 45// Bước 5: Thêm nút
 46func (chr *ConsistentHashRing) AddNode(node string) {
 47	for i := 0; i < chr.replicas; i++ {
 48		replicaKey := chr.getHash(node + "_" + strconv.Itoa(i))
 49		chr.ring[replicaKey] = node
 50		chr.sortedKeys = append(chr.sortedKeys, replicaKey)
 51
 52		fmt.Printf("Added node: %s with hash: %d on replica %d\n", node, replicaKey, i)
 53	}
 54	chr.assignNodesToRing()
 55}
 56
 57// Bước 6: Xóa nút
 58func (chr *ConsistentHashRing) RemoveNode(node string) {
 59	for i := 0; i < chr.replicas; i++ {
 60		replicaKey := chr.getHash(node + "_" + strconv.Itoa(i))
 61		delete(chr.ring, replicaKey)
 62		chr.sortedKeys = removeUint64Slice(chr.sortedKeys, replicaKey)
 63	}
 64}
 65
 66// Bước 4: Ánh xạ khóa
 67func (chr *ConsistentHashRing) KeyMap(key string) string {
 68	chr.mu.RLock()
 69	defer chr.mu.RUnlock()
 70
 71	hashValue := chr.getHash(key)
 72	index := sort.Search(len(chr.sortedKeys), func(i int) bool {
 73		return chr.sortedKeys[i] >= hashValue
 74	})
 75
 76	if index == len(chr.sortedKeys) {
 77		// Wrap around to the beginning of the ring
 78		return chr.ring[chr.sortedKeys[0]]
 79	}
 80
 81	return chr.ring[chr.sortedKeys[index]]
 82}
 83
 84func removeUint64Slice(s []uint64, e uint64) []uint64 {
 85	for i, a := range s {
 86		if a == e {
 87			return append(s[:i], s[i+1:]...)
 88		}
 89	}
 90	return s
 91}
 92
 93// Bước 7: Cân bằng tải
 94// LoadBalancing kiểm tra tải trên mỗi nút và phân phối lại khóa nếu cần
 95func (chr *ConsistentHashRing) LoadBalancing() {
 96	chr.mu.Lock()
 97	defer chr.mu.Unlock()
 98
 99	nodeCount := make(map[string]int)
100	for _, node := range chr.ring {
101		nodeCount[node]++
102	}
103
104	avgCount := len(chr.ring) / len(nodeCount)
105	for node, count := range nodeCount {
106		if count > avgCount {
107			// Node này có tải quá cao, phân phối lại khóa
108			fmt.Printf("Node %s có tải quá cao, phân phối lại khóa\n", node)
109			// ...
110		}
111	}
112}
113
114func (chr *ConsistentHashRing) PrintMap(key string) {
115	node := chr.KeyMap(key)
116
117	fmt.Printf("The key '%s' is mapped to node: %s\n", key, node)
118}
119func main() {
120	hashRing := NewConsistentHashRing(3)
121
122	// Add nodes to the ring
123	hashRing.AddNode("sw_hn")
124	hashRing.AddNode("sw_dn")
125	hashRing.AddNode("sw_hcm")
126
127	// // Get the node for a key
128	// key := "Tác giả Phạm Duy Tùng"
129	hashRing.PrintMap("Tác giả Phạm Duy Tùng")
130	hashRing.PrintMap("Ngày cập nhật 08/09/2024")
131	hashRing.PrintMap("Ngày mưa bão")
132	hashRing.PrintMap("Viết vào ngày bão, Tên cơn bão là Yagi")
133	hashRing.PrintMap("Tác giả Phạm Duy Tùng, Cảm ơn các bạn đã theo dõi bài viết")
134	hashRing.LoadBalancing()
135
136}

Lưu ý: code demo thôi, xài hàm hash đơn giản, và sử dụng tìm kiếm nhị phân để tìm vị trí của phần tử trong vòng. Thực tế thì chắc không ai chơi mấy hàm này :)

Kết quả:

 1>>>> go run consistent_hashing.go
 2
 3Added node: sw_hn with hash: 17429720091564777933 on replica 0
 4Added node: sw_hn with hash: 6206559145603051050 on replica 1
 5Added node: sw_hn with hash: 501148381563080863 on replica 2
 6Added node: sw_dn with hash: 10372921504992544131 on replica 0
 7Added node: sw_dn with hash: 10352104123016491672 on replica 1
 8Added node: sw_dn with hash: 4947674849506040391 on replica 2
 9Added node: sw_hcm with hash: 13712729030455601798 on replica 0
10Added node: sw_hcm with hash: 13299855957139837304 on replica 1
11Added node: sw_hcm with hash: 15146544336749671394 on replica 2
12The key 'Tác giả Phạm Duy Tùng' is mapped to node: sw_dn
13The key 'Ngày cập nhật 08/09/2024' is mapped to node: sw_dn
14The key 'Ngày mưa bão' is mapped to node: sw_dn
15The key 'Viết vào ngày bão, Tên cơn bão là Yagi' is mapped to node: sw_hn
16The key 'Tác giả Phạm Duy Tùng, Cảm ơn các bạn đã theo dõi bài viết' is mapped to node: sw_dn

Ưu và nhược điểm của Consistent Hashing

Ưu điểm của việc sử dụng Consistent Hashing

  • Cân bằng tải: Consistent Hashing giúp phân phối tải trọng của mạng đều giữa các nút, bảo vệ hiệu suất và khả năng đáp ứng của hệ thống ngay cả khi lượng dữ liệu tăng lên và thay đổi theo thời gian.

  • Khả năng mở rộng: Consistent Hashing rất linh hoạt và có thể thích nghi với sự thay đổi của số lượng nút hoặc lượng dữ liệu được xử lý mà không ảnh hưởng đến hiệu suất của toàn bộ hệ thống.

  • Tối thiểu hoá số lượng ánh xạ lại: Consistent Hashing giảm thiểu số lượng khóa cần ánh xạ lại khi thêm hoặc xóa nút, đảm bảo rằng hệ thống luôn ổn định và nhất quán ngay cả khi mạng thay đổi theo thời gian.

  • Tăng khả năng chịu lỗi: Consistent Hashing giúp dữ liệu luôn khả dụng và cập nhật, ngay cả trong trường hợp nút bị lỗi. Khả năng sao chép khóa trên nhiều nút và ánh xạ lại khóa đến nút khác trong trường hợp lỗi giúp tăng cường độ ổn định và tin cậy của toàn bộ hệ thống.

  • Đơn giản hóa hoạt động: Consistent Hashing giúp đơn giản hóa quá trình thêm hoặc xóa nút khỏi mạng, giúp dễ dàng quản lý và duy trì hệ thống phân tán lớn.

Nhược điểm của việc sử dụng Consistent Hashing

  • Hàm băm: Hiệu suất của Consistent Hashing phụ thuộc vào việc sử dụng hàm băm phù hợp. Hàm băm phải tạo ra giá trị duy nhất cho mỗi khóa và phải là xác định để có hiệu quả. Sự phức tạp của hàm băm có thể ảnh hưởng đến hiệu suất và hiệu quả của toàn bộ hệ thống.

  • Tốn kém hiệu suất: Việc sử dụng Consistent Hashing có thể dẫn đến một số tốn kém hiệu suất do cần phải sử dụng tài nguyên tính toán để ánh xạ khóa đến nút, sao chép khóa và ánh xạ lại khóa trong trường hợp thêm hoặc xóa nút.

  • Thiếu linh hoạt: Trong một số trường hợp, giới hạn cố định của Consistent Hashing có thể hạn chế khả năng của hệ thống để thích nghi với sự thay đổi của nhu cầu hoặc điều kiện mạng.

  • Sử dụng tài nguyên cao: Trong một số trường hợp, việc sử dụng Consistent Hashing có thể dẫn đến sử dụng tài nguyên cao khi thêm hoặc xóa nút khỏi mạng, điều này có thể ảnh hưởng đến hiệu suất và hiệu quả của toàn bộ hệ thống.

  • Phức tạp của quản lý: Việc quản lý và duy trì hệ thống sử dụng Consistent Hashing có thể phức tạp và đòi hỏi chuyên môn và kỹ năng đặc biệt.

Cảm ơn các bạn đã theo dõi bài viết. Xin cảm ơn và hẹn gặp lại. Bài sau sẽ nói về Distributed Hash Tables

Các Ứng Dụng Của LLM Trong Thực Tế

Comments