Ngày 30 tháng 11 năm 2017 - Máy tính
Giả sử N là số lượng nút dịch vụ ở phía sau, khi một yêu cầu từ phía trước mang theo khóa key được gửi đi, chúng ta thường băm khóa key rồi áp dụng phép chia lấy dư (hash(key)%N) để phân phối yêu cầu đến các nút khác nhau.
Trong các tình huống mà yêu cầu phía trước không nhạy cảm với các nút dịch vụ không trạng thái phía sau, chỉ cần khóa key có tính ngẫu nhiên nhất định, ngay cả khi các nút được thêm hoặc xóa động, thuật toán này đã có thể đạt được hiệu quả cân bằng tải rất tốt đối với phía sau. Tuy nhiên, trong các trường hợp như bộ nhớ đệm phân tán hay cơ sở dữ liệu phân tán, cách tiếp cận này lại không phù hợp. Vì việc tăng hoặc giảm nút phía sau sẽ gây ra việc ánh xạ lại hầu hết các khóa key. Đối với bộ nhớ đệm phân tán, điều này dẫn đến cache miss toàn bộ; còn đối với cơ sở dữ liệu phân tán, nó gây ra sự lộn xộn về dữ liệu, tác động của nó là thảm khốc.
Mục tiêu của thuật toán băm nhất nổ hũ 28 quán là khi K yêu cầu key được gửi đi, việc thêm hoặc bớt nút phía sau chỉ nên làm cho K/N các khóa key bị ánh xạ lại. Nghĩa là, thuật toán băm nhất quán đảm bảo rằng khi các nút phía sau ổn định, mỗi lần yêu cầu của cùng một khóa key sẽ luôn được ánh xạ đến cùng một nút. Và khi các nút phía sau thay đổi, thuật toán cố gắng giữ nguyên ánh xạ của K khóa key tới các nút tương tự như trước đó.
1) Nguyên lý thuật toán Băm Nhất quán
Thuật toán băm nhất quán ánh xạ mỗi nút Node lên cùng một vòng tròn. Các khóa key của các nút Node được tính toán qua hàm băm, tạo ra một mảng số nguyên. Sau khi sắp xếp mảng này, nối đầu cuối với nhau sẽ tạo thành một vòng tròn. Như hình dưới đây minh họa, các khóa key của các nút Node nằm rải rác trên các đoạn cung của vòng tròn. Tương tự, nếu có một yêu cầu key, sau khi được băm và rơi vào một đoạn cung cụ thể trên vòng tròn (được biểu diễn bởi dấu tam giác trong hình), tìm kiếm theo chiều kim đồng hồ đến nút gần nhất sẽ xác định được nút phục vụ yêu cầu đó (trong hình là Node2). Mỗi nút bao phủ một đoạn cung từ nút trước đó đến chính nó. Nếu một nút ngừng hoạt động, các yêu cầu trước đó thuộc đoạn cung của nó sẽ di chuyển theo chiều kim đồng hồ đến nút kế cận (ví dụ, nếu Node2 ngừng hoạt động, các yêu cầu trước đó thuộc đoạn cung từ Node3 đến Node2 sẽ rơi vào Node1). Những yêu cầu không thuộc đoạn cung bị hỏng sẽ không bị ảnh hưởng (các yêu cầu trước đó thuộc đoạn cung từ Node2 đến Node3 vẫn không thay đổi khi Node2 ngừng hoạt động). Tình huống thêm nút cũng tương tự: nút mới sẽ chịu trách nhiệm cho một đoạn cung mới, do đó các yêu cầu thuộc đoạn cung từ nút cũ đến nút mới sẽ được xử lý bởi nút mới.
Trong trường hợp số lượng nút cố định, để tăng tính đồng đều và phân tán của các nút trên vòng tròn, có thể thiết lập số lượng replicas (bản sao) cho mỗi nút. Trong hình dưới đây, số lượng replicas được đặt là 2, phạm vi đoạn cung mà mỗi nút chịu trách nhiệm đã trở nên chi tiết hơn và phân bố tổng thể cũng trở nên đồng đều hơn. Do đó, điều chỉnh thông số replicas thích hợp có thể cải thiện sự cân bằng của thuật toán.
2) Mã nguồn thực hiện thuật toán Băm Nhất quán bằng Golang
Hàm hash trong bài viết này trước tiên sẽ thực hiện md5Sum trên khóa key, sau đó sử dụng crc32 để tạo checksum và nhận được một số hj88 dương.
package consistent_hashing
import (
"crypto/md5"
"hash/crc32"
"sort"
"strconv"
"sync"
)
type Node struct {
Id string
Address string
}
type ConsistentHashing struct {
mutex sync.RWMutex
nodes map[int]Node
replicas int
}
func NewConsistentHashing(nodes []Node, replicas int) *ConsistentHashing {
ch := &ConsistentHashing{nodes: make(map[int]Node), replicas: replicas}
for _, node := range nodes {
ch.AddNode(node)
}
return ch
}
func (ch *ConsistentHashing) AddNode(node Node) {
ch.mutex.Lock()
defer ch.mutex.Unlock()
for i := 0; i < ch.replicas; i++ {
k := hash(node.Id + "_" + strconv.Itoa(i))
ch.nodes[k] = node
}
}
func (ch *ConsistentHashing) RemoveNode(node Node) {
ch.mutex.Lock()
defer ch.mutex.Unlock()
for i := 0; i < ch.replicas; i++ {
k := hash(node.Id + "_" + strconv.Itoa(i))
delete(ch.nodes, k)
}
}
func (ch *ConsistentHashing) GetNode(outerKey string) Node {
key := hash(outerKey)
nodeKey := ch.findNearestNodeKeyClockwise(key)
return ch.nodes[nodeKey]
}
func (ch *ConsistentHashing) findNearestNodeKeyClockwise(key int) int {
ch.mutex.RLock()
sortKeys := sortKeys(ch.nodes)
ch.mutex.RUnlock()
for _, k := range sortKeys {
if key <= k {
return k
}
}
return sortKeys[0]
}
func sortKeys(m map[int]Node) []int {
var sortedKeys []int
for k := range m {
sortedKeys = append(sortedKeys, k)
}
sort.Ints(sortedKeys)
return sortedKeys
}
func hash(key string) int {
md5Chan := make(chan []byte, 1)
md5Sum := md5.Sum([]byte(key))
md5Chan <- md5Sum[:]
return int(crc32.ChecksumIEEE(<-md5Chan))
}
3) Phân tích độ đồng đều
Khi xây dựng các nút dịch vụ, để mô phỏng việc phân bố các khóa key trên vòng tròn, đơn giản sử dụng id (0, 1, 2) làm khóa ban đầu, số lượng replicas là 100. Sau khi chia vòng tròn theo tỷ lệ khoảng cách giữa các điểm, vị trí của chúng được xác định, các dấu chấm nhỏ màu sắc đại diện cho các nút tương ứng (màu đỏ, xanh lá cây, xanh dương tương ứng với 0, 1, 2).
Các dấu tam giác đại diện cho ba chuỗi yêu cầu bên ngoài (“10.10.10.10”, “10.10.20.11”, “10.10.30.12”) sau khi được băm và được chọn nút dịch vụ theo thuật toán.
Sử dụng công cụ Python matplotlib để vẽ đồ thị như sau:
Từ đồ thị có thể thấy rằng dù số lượng nút ít (chỉ 3 nút), nhưng sau khi mở rộng số lượng bản sao, việc phân bố các khóa key đã có tính đồng đều và phân tán nhất định, và các yêu cầu key bên ngoài cuối cùng cũng được phân phối khá đều trên toàn bộ các nút dịch vụ.
4) Mã nguồn Golang cho Đại diện Clusters Cao Khả dụng
Thuật toán băm nhất quán có nhiều ứng dụng rộng rãi. Ví dụ như phân luồng yêu cầu và cân bằng tải, bộ nhớ đệm phân tán, lưu trữ phân tán, v.v. Đoạn mã sau đây sử dụng thư viện proxy ngược của Golang, kết hợp với thuật toán băm nhất quán được đề cập ở trên, phân phát dựa trên nhãn tiêu đề yêu cầu, chỉ vài dòng mã có thể xây dựng một máy chủ proxy nhỏ gọn và cao khả dụng.
package main
import (
"consistent_hashing"
"net/http"
"net/http/httputil"
"net/url"
)
func main() {
nodes := []consistent_hashing.Node{
{"0", "http://node0.example.com"},
{"1", "http://node1.example.com"},
{"2", "http://node2.example.com"},
}
ch := consistent_hashing.NewConsistentHashing(nodes, 100)
http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
sign := r.Header.Get("sign")
node := ch.GetNode(sign)
uri, _ := url.Parse(node.Address)
proxy := httputil.NewSingleHostReverseProxy(uri)
proxy.ServeHTTP(w, r)
})
http.ListenAndServe(":8080", nil)
}
** [1]
[2]
[3]
Đại Liên
01 tháng 12 năm 2017
#Golang #ThuậtToán