0

Phân chia dữ liệu cache trên cụm server với Consistent Hashing

Kỹ thuật scale theo chiều ngang (thêm/bỏ server vào cụm server) được sử dụng rộng rãi để đáp ứng phù hợp với số lượng request đến hệ thống. Tuy nhiên, với bài toán cache dữ liệu trên nhiều server thì vấn đề trở nên phức tạp vì có sự xáo trộn tập dữ liệu cache trên mỗi server có thể xảy ra thường xuyên hơn trong quá trình vận hành của mỗi hệ thống.

Hãy đặt ra bài toán như thế này. Bạn có một website E-Commerce cung cấp sản phẩm từ những doanh nghiệp cho người tiêu dùng. Mỗi người dùng sẽ tìm kiếm thông tin những sản phẩm đó và mua hàng. Bạn không thể nào xử lý mỗi thao tác thông tin tìm kiếm của khách hàng bằng một câu lệnh truy vấn database được vì đơn giản là số lượng request gửi đến hệ thống quá nhiều và chi phí Disk I/O quá lớn. Bạn phải tạo một cụm server để cache những URL chứa thông tin sản phẩm A, B, C, D etc. Với mỗi request đến hệ thống, sẽ có một process tìm kiếm thông tin sản phẩm lấy ra từ cụm server cache này, đảm bảo không ảnh hưởng đến databasetrả về thông tin nhanh nhất cho người dùng.

Với mỗi URL, bạn sẽ dùng một hàm hash để hash chúng thành một giá trị integer x nào đó. Việc tiếp theo là phải lưu x vào một trong những server trong cluster. Có nhiều hàm hash dạng cryptography để tạo ra x như MD5, SHA-1, etc. tuy nhiên chi phí lại cao. Cách đơn giản nhất là dùng hàm modulo với N (N là số server trong cluster).

Ví dụ, bạn có 8 URL là

URL Hash value
abcde.com/products/phone/iphoneX 0
abcde.com/products/bike/airblade 1
abcde.com/products/book/dac-nhan-tam 2
abcde.com/products/laptop/macbook-2018 3
abcde.com/products/clothes/ao-thun-trang 4
abcde.com/products/phu-kien/sap-du-phong 5
abcde.com/products/tv/Samsung-30-inch 6
abcde.com/products/mat-kinh/kinh-mat 7

có giá trị hash tương ứng là 0, 1, 2, .. 7. Bạn có N = 3 cache server trong cluster, đánh số 0, 1, 2.

Như vậy 0 % 3 = 0, URL abcde.com/products/phone/iphoneX được cache trong server 0.
1 % 3 = 1, URL abcde.com/products/bike/airblade được cache trong server 1.
2 % 3 = 2, URL abcde.com/products/book/dac-nhan-tam được cache trong server 2.
... lần lượt tính modulo cho từng giá trị hash URL và lưu vào server tương ứng, ta có kết quả là

Imgur

Quá trình tìm kiếm thông tin diễn ra theo 3 bước.

  • Bước 1: URL thông tin sản phẩm được hash thành X.
  • Bước 2: tính X mod N, tìm ra server cache thông tin sản phẩm này.
  • Bước 3: truy xuất đến server đó và trả data về.

Đến thời điểm cuối năm hoặc sự kiện Sale, lượt truy cập vào hệ thống tăng vọt, bạn phải theo một server vào trong cluster để tăng khả năng xử lý request. Server mới thêm vào sẽ có index là 3.

Vấn đề ngay lập tức xuất hiện, vì N đã thay đổi nên những URL được cache trong những server cũng đã bị thay đổi.

Imgur

Quá trình tìm kiếm vẫn diễn ra, nhưng những giá trị cache (màu đỏ) cần phải được lưu trữ trên server khác, so với trước khi thêm server 3 vào cluster. .Ví dụ như key 4 phải được lưu trên server 0 thay vì server 1.

Như vậy, trên mỗi server cache đều có khả năng xảy ra trường hợp cache miss. Phải có một service chạy background để distribute lại tất cả các key trên toàn bộ server.

Trong trường hợp ngược lại, bạn thấy rằng hệ thống của bạn không cần dùng đến 3 server, bạn quyết định loại bỏ một server, vậy data được cache trên server này sẽ phân chia vào những server còn lại như thế nào?

Như vậy, ta thấy được vấn đề khi dùng hàm module để phân chia tập data cache trên cụm server đó là khó scale theo chiều ngang.

Consistent Hashing giải quyết vấn đề này như thế nào ?

Ý tưởng của Consistent Hashing được đề xuất vào năm 1997 bởi Martin Karger cùng cộng sự. Đến năm 2007 thì mới đưa vào thực tiễn (DynamoDB, Cassandra, etc.).

Chúng ta vẫn sẽ dùng 3 server như ban đầu, và sẽ "kết nối" 3 server này bằng một "vòng tròn".

Hãy tưởng tượng, mỗi điểm trên "vòng tròn" này tương ứng với một giá trị trong dãy số integer từ 0, 1, 2 ... 232-1.

Mỗi địa chỉ IP của 3 server này sẽ được hash thành 3 giá trị đảm bảo trong khoảng từ 0 đến 232 - 1.

Kế đến, chúng ta có tập URL đã được hash thành các giá trị trong khoảng từ 0 đến
232 - 1.

Lần lượt đặt từng giá trị URL đươc hash đó vào trên vòng tròn, sẽ có hai trường hợp xảy ra:

  • Gía trị URL đươc hash trùng với giá trị hash từ IP của một server.
  • Gía trị URL đươc hash khác với tất cả giá trị hash từ IP của một server.

Khi giá trị đươc hash từ URL h(X) = z, trùng với giá trị IP của một server cache nào đó, value của nó sẽ được lưu trên server đó.

Khi giá trị được hash từ URL là h(X) = z, khác với tất cả các giá trị hash từ tập IP server cache, ta thực hiện một thao tác tìm kiếm server sẽ lưu trữ value này bằng cách dịch chuyển điểm z này theo chiều kim đồng hồ, cho đến khi z trùng với một trong giá trị hash được từ tập IP của cache server.

Ví dụ, những URL được hash thành các giá trị khác nhau trên "vòng tròn". Giá trị IP được hash của 3 server lần lượt là 26, 212224.

URL Hash value
abcde.com/products/phone/iphoneX 26
abcde.com/products/bike/airblade 212
abcde.com/products/book/dac-nhan-tam 29- 121
abcde.com/products/laptop/macbook-2018 24- 7
abcde.com/products/clothes/ao-thun-trang 212- 42
abcde.com/products/phu-kien/sac-du-phong 215- 38
abcde.com/products/tv/Samsung-30-inch 217- 11
abcde.com/products/mat-kinh/kinh-mat 228- 217

Imgur

Như hình vẽ, URL abcde.com/products/phone/iphoneX và URL abcde.com/products/bike/airblade có giá trị hash trùng với Server 1 và 2 (26 và 212), lưu lần lượt trên Server 1, 2. các giá trị hash được từ URL các còn lại sẽ lần lượt nằm rải rác trên vòng tròn. URL abcde.com/products/tv/Samsung-30-inch được lưu trên Server 1 vì từ giá trị 217 - 11 đi dọc theo chiều kim đồng hồ, sẽ gặp giá trị 224 trước. Tương tự như vậy, có thể xác định giá trị hash cho các URL còn lại.

Ta có thể phát biểu bài toán như thế này:
Cho mảng N chứa dãy liên tục có n phần tử và tập K chứa t những giá trị trong N. Cho một phần tử x thuộc N, tìm ki nhỏ nhất thuộc K sao cho ki lớn hơn hoặc bằng x. Nếu x lớn hơn giá trị lớn nhất của tập K, ta sẽ lấy k0. (Tính xoay vòng)

Khi thêm một server ki vào cụm cache server (thêm một phần từ vào tập K), server mới sẽ cache lại data từ khoảng $$k_{i-1}\le x \le k_{i}$$

Imgur

Khi bỏ một server ki ra khỏi cụm cache server (bỏ một phần từ ra khỏi tập K), data cache trên server đó sẽ được lưu trên server kế cận ki+1.

Imgur

Như trên hình, server 1 bị loại bỏ, những giá trị hash (màu đỏ hồng) sẽ được lưu trên server 2.

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 đề phân phối đều cache trên từng server

Trên thực tế, các giá trị URL được hash đều có tính ngẫu nhiên, có khả năng nhiều URL (khoảng 95% đến 99%) đều được hash vào một dãy giá trị lưu trên một server nào đó, khiến server đó trở thành điểm nóng (hot spot), còn lại chỉ khoảng 1% đến 5% được lưu trữ trong các server còn lại. Nếu server hot spot gặp sự cố, gần như toàn bộ cache sẽ bị mất.

Imgur

Như trên hình vẽ, Server 0 chứa nhiều cache hơn server 1 và server 2 và trở thành hot spot.

Để giải quyết vấn đề này, chúng ta sẽ đặt những node ảo (virtual node) trên vòng tròn. Mỗi node ảo tượng trưng cho một dãy giá trị mà một server đảm nhiệm.

Ví dụ N = 3, k = 2, ta chia vòng tròn thành N * k = 2 * 3 = 6 khoảng giá trị.

Imgur

Theo hình vẽ trên, server 0 sẽ lưu dãy giá trị 0 và 3, server 1 sẽ lưu dãy giá trị 1, 4. Còn Server 2 sẽ lưu dãy giá trị 2, 5.

Ngoài ra, có thể replica tập cache của từng server sang những server kế cận
khác để đảm bảo hạn chế cache miss.

Trong bài viết kế tiếp, mình sẽ đề cập những thuật toán Hash cải tiến từ consistent hashing. See you next time!

Reference links:
https://medium.com/@dgryski/consistent-hashing-algorithmic-tradeoffs-ef6b8e2fcae8
https://dzone.com/articles/simple-magic-consistent
http://www.acodersjourney.com/2017/10/system-design-interview-consistent-hashing

AUTHOR

COMMENTS