Consistent Hashing: người lính thầm lặng của Distributed system
Mình đang muốn làm một series: Cái gì không biết thì cùng bóc tách và tự implement nó(Build something from scratch) → Mục đích để hiểu nó mà mang đi chém gió thôi :))
Series này sẽ bắt đầu từ Consistent Hashing nhé. Nhưng trước hết cần phải biết Consistent Hashing là gì đã :v.
Consistent Hashing là gì?
Trong thế giới phân tán - Distributed system, mọi người chắc hẳn đã từng làm việc với vô vàn các service kiểu như Load Balancer (Nginx), hay Distributed Caching (Redis cluster), hay sharding database, K8s …. Những service này có một đặc điểm chung là: chúng quản lý các node khác nhau kiểu gì? Hay cụ thể hơn:
Làm sao Load balancer lại có thể phân phối traffic đến các Node nhanh mà không bị loạn?
Làm sao Redis cluster có thể phân phối key vào cách hash slot?
Làm sao Database sharding nhưng vẫn query rất nhanh?
Làm sao cụm k8s có thể scale mà session vẫn sticky?
Ẩn dưới những thứ hào nhoáng mà chúng ta đang sử dụng, đó là một thuật toán: Consistent Hashing. Nó là một thứ thầm lặng đứng đằng sau tất cả dịch vụ trong thế giới phân tán này.
Tác dụng của nó là gì?
Để cho bớt dài dòng, mình sẽ nói nhanh qua về lí do ra đời của Consistent Hashing nhé.
Trong hệ thống phân tán (Distributed system), cứ mỗi khi 1 server không thể phục vụ nhu cầu của user nữa, nó cần phải được scale, có 2 cách scale:
Vertical scaling: Nôm nay là bạn đi update Disk, Ram, CPU cho nó xịn hơn, khoẻ hơn
Horizontal scaling: Thay vì một server phục vụ user, hãy tuyển thêm nhiều server chạy song song - đây là điểm quan trọng của Distributed System, giúp đỡ tốn kém hơn, phục vụ được hàng triệu người dùng
Vậy tức là đối với Horizontal scaling, cần phải có một cơ chế để giúp cho các node có thể hoạt động được với nhau một cách mượt mà đúng không? Đây là bài toán không phải làm với một, mà làm với nhiều node cùng một lúc.
Oke, để mình nói dễ hiểu hơn nhé:
Ví dụ về redis cluster, nó sẽ là 1 cluster gồm nhiều redis kết hợp lại với nhau, mục đích để làm gì? Đúng vậy, nó giúp partitioning cho database của các bạn.
(Note: Thực tế ra Redis cluster dùng cơ chế Hash slot, nó hơi khác một chút so với Consistent Hashing, nhưng mình mượn nó để lấy ví dụ trong bài này nhé ^^)
Nếu như bạn chỉ có 1 service redis thôi, và bạn có 1 triệu key thì sao? 1 triệu key đó sẽ ở trên cùng 1 node. Tư duy ở đây là 1 triệu key đó ta có thể phân chia đều đặn vào nhiều node, vậy mỗi node sẽ chỉ cần chứa 1 lượng key nhỏ hơn → giảm tải, giảm không gian lưu trữ, giảm cả traffic nữa.
Bài toán: Chúng ta có N node, và có 1.000.000 keys. Hãy cùng nghĩ xem chúng ta sẽ làm thế nào để key được chia đều sang N node đã có?
Phương pháp: Naive hashing
Phương pháp đơn giản, đó là chúng ta sẽ hash các key ra 1 con số, rồi lấy số đó % N là sẽ tìm ra node tương ứng, tiến hành lưu key đó vào node đã tìm được
Nhược điểm: Phương pháp trên rất tốt về lý thuyết, nhưng trên thực tế, các node có thể bị down, hoặc có thể scale thêm nhiều node → N thay đổi, hàm get_node sẽ bị thay đổi → chúng ta cần rehashing lại khá nhiều key. Hãy xem hình bên dưới:
Có thể nhìn thấy, với Naive Hashing, chúng ta sẽ phải Rehashing lại 300k keys, điều này dẫn tới việc mỗi khi cần phải thêm 1 node, hay bớt 1 node đi, các kĩ sư sẽ rất vất vả. Consistent Hashing sinh ra để khắc phục nhược điểm này.
Phương pháp: Consistent Hashing
Tưởng tượng chúng ta có một vòng tròn - HashRing (kéo dài từ 0 - (2³² - 1)), thông qua hash function, chúng ta sẽ sắp xếp các node trên vòng tròn này.
Cứ mỗi key đi vào, chúng ta sẽ tìm hash key trên vòng trong Hash Ring, đi theo chiều kim đồng hồ để tìm node gần nhất gặp được, như ở hình trên, key user_1111 sau khi hash sẽ đi tìm được node 1 gần nhất mình, nó sẽ được lưu tại node 1
Vậy, khi thêm một node mới là node 4 vào giữa node 3 và node 1 thì sao? Sẽ có 1 số ít key thay vì vào node 1 sẽ vào node 4, còn lại thì sẽ vẫn ở node 1. Bài toán là làm thế nào để số lượng key phải rehashing là giảm thiểu đi chỉ còn khoảng 10 - 20%
Nhìn hình vẽ trên, chúng ta có thể thấy rằng key user_121 sẽ vào node 4 thay vì node 1, vậy nên vị trí hash trên Hash Ring sẽ chỉ cần đổi từ range (node3, node4] vào node 4 thay vì sẽ vào node 1 đúng không? Đó là ý tưởng của Consistent Hashing mà mình muốn nói.
Implement Consistent Hashing
Trông vậy nhưng mình nghĩ khá đơn giản thôi, cái chính là chúng ta sẽ chọn Data Structure nào để quản lý và sắp xếp trật tự các node trên Hash Ring vậy. Trong project này mình sẽ chọn Rust ( tiện cũng để học viết rust luôn thôi )
Tạo struct ConsistentHashing
Mình sẽ chọn BTreeMap của Rust để quản lý order của từng node trên vòng tròn Hash Ring. Các bạn có thể hình dung BTreeMap là 1 hashmap (key-value) nhưng có thể sắp xếp được các Item dựa trên Key của nó thôi.
const MAX_RING_SLOT: u64 = u32::MAX as u64;
pub struct ConsistentHashRing {
/// The hash ring storing virtual node positions
ring: BTreeMap<u32, String>,
/// Hash function used for mapping keys and nodes
hash_fn: fn(&str) -> u32,
/// Number of virtual nodes (replicas) per physical node
replicas: usize,
}
ring: là BTreeMap để quản lý Hash Ring
hash_fn: đây là hàm hash trong thuật toán mà mình dùng, để tìm vị trí key trên vòng tròn hash ring
replicas: đây là số lượng Virtual node, tưởng tượng rằng nếu trên vòng tròn Hash Ring nếu có 3 node thôi, thì 1 node có thể sẽ là Hot spot (chứa nhiều key hơn các node còn lại). Có nhiều Virtual Node để sao cho key được phân chia đều hơn và công bằng hơn
Các method cần thiết
Chúng ta sẽ có các method như sau:
add_node(node: &str): thêm 1 node vào vòng tròn Hash Ring
remove_node(node: &str): xoá 1 node trong vòng tròn Hash Ring
get_node(key: &str): tìm 1 node gần nhất theo chiều kim đồng hồ theo key
etc…: các method khác như: size của rings, print_ring, …
impl ConsistentHashRing {
pub fn new(replicas: usize) -> Self {
ConsistentHashRing {
ring: BTreeMap::new(),
hash_fn: ConsistentHashRing::default_hash_fn,
replicas,
}
}
pub fn with_hash_fn(replicas: usize, hash_fn: fn(&str) -> u32) -> Self {
ConsistentHashRing {
ring: BTreeMap::new(),
hash_fn,
replicas,
}
}
/// Default hash function using Rust's DefaultHasher.
fn default_hash_fn(key: &str) -> u32 {
let mut hasher = DefaultHasher::new();
key.hash(&mut hasher);
(hasher.finish() % MAX_RING_SLOT) as u32
}
pub fn add_node(&mut self, node: &str) {
for i in 0..self.replicas {
let virtual_key = format!("{}#{}", node, i);
let hash_key = (self.hash_fn)(&virtual_key);
self.ring.insert(hash_key, node.to_string());
}
}
pub fn get_node(&self, key: &str) -> Option<String> {
if self.ring.is_empty() {
return None;
}
let hash_key = (self.hash_fn)(key);
// Find the first node with hash >= key's hash (clockwise on ring)
self.ring
.range(hash_key..)
.next()
.map(|(_, node)| node.clone())
.or_else(|| {
// Wrap around to the first node if no node found
self.ring.values().next().cloned()
})
}
pub fn remove_node(&mut self, node: &str) {
for i in 0..self.replicas {
let virtual_key = format!("{}#{}", node, i);
let hash_key = (self.hash_fn)(&virtual_key);
self.ring.remove(&hash_key);
}
}
}
Cả source code mình để ở đây: Source (các bạn tiện cho mình xin một ⭐️⭐️ nhé :) )
Nhược điểm:
Cách implement của mình có nhiều nhược điểm vẫn chưa cover hết được.
Nhược điểm 1: Trong thực tế, việc downtime khi thêm 1 node vào Hash Ring sẽ được handle thế nào?
Trả lời: Theo ý kiến cá nhân, khi thêm 1 node F vào Hash Ring, cần có cơ chế để migrate key vốn nằm ở node E sang node F, mình sẽ cho call ở node F trước, nếu chưa có thì sẽ vòng ngược lại để lấy key ở node E
Nhược điểm 2: Nhược điểm của việc dùng virtual nodes là gì? Tăng bộ nhớ, nhiều virtual node thì việc find node sẽ phức tạp hơn. Hơn nữa khi thêm node hay bớt node sẽ phải handle tất cả các virtual node đó để move data sang các node bên cạnh…
Kết luận
Bài viết này có thể hoặc không giúp bạn nhiều, nó có thể là một chủ đề cần bàn luận. Theo mình tìm hiểu được thì có khá nhiều service cũng không áp dụng Consistent Hashing này (redis cluster, mongodb) và source code còn nhiều thiếu sót, nên mình khá vui khi được mọi người góp ý, chỉnh sửa và thảo luận. Mình cảm ơn !!
