System Design Cơ Bản – Consistent Hashing

Bài viết được sự cho phép của tác giả Edward Thiên Hoàng

Như đã nhắc đến rất nhiều lần bên trên thì Distributed Hash Table (DHT — Bảng băm phân tán) là một thành phần cơ bản trong những distributed scalable systems (hệ thống phân tán có khả năng mở rộng). Một Hash Table cần một cặp key-value, và một hàm “hash” để map keyvới vị trí mà value của nó được lưu trữ.

index = hash_function(key)

Giả sử ta có thiết kế một distributed caching system (Redis cache chẳng hạn). Chúng ta có “n” cache servers, thì hàm băm (hash function) để map key với vị trí của Cach server nó làm ở đâu sẽ là key % n. Nó rất đơn giản và dễ sử dụng, tuy nhiên nó có hai nhược điểm chính là:

1. Nó rất khó horizontally scalable (phân tán theo chiều ngang). Bởi vì mỗi lần một cache server mới được thêm vào LB, mọi mapping trước khia giữa key với value nó được lưu trữ ở đâu sẽ sai toét hết. Hiện tượng cache miss sẽ sẩy ra tràn lan và rất mất thời gian và khó khăn để cập nhật tất cả các mapping key-value, với một hệ thống lớn với số lượng caching data khổng lồ đây là một điểm ác mộng với những người quản lý dữ liệu.
2. Nó có thể không đáp ứng được việc cân bằng tải (Load Balanced), bởi vì ta không thể chắc chắn rằng việc hash và mapping như vậy những data được lưu trữ ở các server khác nhau có độ truy cập có cân bằng nhau không? Rất có thể những data ít được truy cập có thể tập chung vào một vài server và vài server còn lại lại chứa những “hot key”, dẫn tới tình trang một vài server thì hoạt động hết công xuất, một vài server thì lại quá nhàn rỗi ngồi chơi không .

Với những vấn đề như vậy thì Consistent Hashing là một giải pháp rất tốt để cải tiến việc chia server với các caching system.

CONSISTENT HASHING GIẢI QUYẾT VẤN ĐỀ NÀY NHƯ THẾ NÀO?

Consistent Hashing là một chiến thuật hiệu quả cho việc phân chia distributed caching systems và DHT. Nó cho phép việc thêm hay xóa các node trên một cụm server (cluster) mà ít gây ra sự xáo trộn dữ liệu, do đó nó các hệ thống caching system sẽ dễ dàng scale-up hay scale down.

Trong Consistent Hashing, khi bảng băm (hash table) thay đổi kích thước (ví dụ thêm một node và cluster), chỉ có “k/n” keys cần re-map với “k” là tổng số keys có trong hệ thống, và “n” là tổng số server. Có nghĩa là khi thay đổi kích thước của cluster thì có duy nhất keys trên một server cần phải re-map. Và khi một node bị xóa khỏi cluster, thì các data của node đó sẽ được di chuyển và chia sẻ với các node khác, và cũng tương tự khi một node được thêm vào cluster thì nó sẽ lấy tự động dữ liệu từ một vài node khác để chia sẻ tài nguyên.

CONSISTENT HASHING HOẠT ĐỘNG NHƯ THẾ NÀO?

Vậy làm thế nào để Consistent Hashing làm được những điều trên thì các Node trên cluster sẽ được lưu trữ dưới dạng vòng tròn bằng cách sử dụng hash function trong Consisten Hashing sẽ hash các key thành một một số nguyên (Integer) nằm trong một khoảng nào đó và các số nguyên đó sẽ được đặt trên một vòng tròn sao cho mỗi điểm trên vòng tròn sẽ tương ứng với một số nguyên trên dãy số nguyên đó.

Tóm lại các bước để Consistent Hashing băm dữ liệu như sau:

1. Tiến hành hash các danh sách node trong cluster server thành một số nguyên trong một khoảng số được định nghĩa trước. Khoảng số này tùy vào người thiết kế hệ thống cân nhắc dựa trên số lượng Server tối đa mà hệ thống sẵn sàng scale up.
2. Sau khi đã có danh sách mapping giữa các node, ta sẽ tiến hành mapping key của data tới các node bằng cách.

• Hash giá trị của key thành một số nguyên (integer).
• Di chuyển nó liên tục trong vòng tròn số nguyên trong khoảng đã tạo ở trên theo chiều kim đồng hồ cho tới khi giá trị integer đó bằng với giá trị hash key của một Node đầu tiên nó gặp. Tiến hành ghi dữ liệu của dữ liệu đó vào Node vừa gặp.

Mô hình vòng tròn trong Consistent Hashing

Do đó khi tiến hành thêm một Node vào Cluster Server thì dữ liệu Node gần nó nhất theo chiều kim đồng hồ sẽ được chia sẻ với Node mới thêm vào.

Mô hình Consistent Hashing với trường hợp thêm mới Node

Tương tự như việc xóa một Node trên Cluster, khi cache miss sẩy ra, dữ liệu sẽ được di chuyển, lưu và lấy từ Node kế cận nhất với Node đã xóa theo chiều kim đồng hồ

Mô hình Consistent Hashing với trường hợp xóa mới một Node

Như vậy, Consistent Hashing đã giải quyết được vấn đề xáo trộn data cache khi scale hệ thống theo chiều ngang, đảm bảo sự xáo trộn cache chỉ xảy ra với một server.

Vấn đề về phân phối đều data trên từng Node.
Bên trên chúng ta cũng đã đề cập về vấn đề Load Balancing, với dữ liệu thật thì khả năng nhiều data key đều được hash vào một dãy giá trị lưu trên một Node nào đó, khiến Node đó trở thành điểm nóng (hot spot) so với các server còn lại. Dẫn đến việc lệch cân bằng tải và rủi ro nếu node hot spot gặp sự cố, gần như toàn bộ cache sẽ bị mất, dẫn tới cache miss hàng loạt.

Để giải quyết vấn đề này, chúng ta sẽ thực hiện hash và thêm nhiều các Node ảo (virtual node) vào vòng tròn. Và thay vì việc chỉ mapping mỗi Node vào một điểm trên vòng tròn, mỗi node ảo tượng trưng cho một dãy giá trị mà một Node thật đảm nhiệm. Có nghĩa là mỗi Node thật sẽ lưu trữ dữ liệu được ánh xạ trên nhiều Virtual Node. Điều này sẽ làm cho việc phân phối key sẽ cân bằng hơn, nó giống với việc tạo ra nhiều Node con hơn cho hash function trong Consistent Hashing băm “nhuyễn” hơn 

Ví dụ ta có 3 Node trên Cluster, ta sẽ tạo thêm 3 virtual Node tương ứng, lúc này vòng tròn sẽ chia thành 6 điểm như trên hình vẽ. Mỗi Virtual Node sẽ ánh xạ tới các Node thật, như trong hình là Virutal Node mầu đỏ  sẽ ảnh xạ tới Real Node mầu đỏ , Virutal Node mầu xanh nước biển  sẽ ánh xạ tới Real Node mầu xanh nước biển  , tương tự với Virtual Nod mầu xanh nhạt. Do vậy với Node  nó sẽ chứa dữ liệu của khoảng 1 và 4 Node  sẽ chứa dữ liệu của 2 và 5, tương tự Node còn lại sẽ chứa dữ liệu của 0 và 6.

Virtual Node trên Consistent Hashing

Consistent Hashing được ứng dụng rất rộng rãi nổi bật nhất là DynamoDB và Cassandra đã ứng dụng nó vào việc replicate dữ liệu giữa các Server Node của nó.

Theo medium

Bài viết gốc được đăng tải tại edwardthienhoang.wordpress.com

Có thể bạn quan tâm:

• Phân chia dữ liệu – Sharding/Data Partitioning
• Bộ Đệm – Caching
• Tất tần tật về Apache Cassandra

Xem thêm Việc làm Developer hấp dẫn trên TopDev