Distributed Counter là gì? Những giải pháp cho bài toán Distributed Counter

1. Distributed Counter là gì?

Distributed counter là một cấu trúc dữ liệu cho phép nhiều node trong hệ thống phân tán cùng cập nhật giá trị của một bộ đếm (bằng cách tăng hoặc giảm). Tuy nhiên, việc triển khai thực tế của nó lại không hề đơn giản vì các yếu tố sau:

1. Phân tán về mặt địa lý: Các node có thể nằm ở nhiều khu vực khác nhau trên thế giới, dẫn đến độ trễ mạng giữa các khu vực.
2. Cập nhật đồng thời: Nhiều node có thể thực hiện cập nhật cùng lúc, gây ra các xung đột.
3. Tính nhất quán và tính sẵn sàng: Trong môi trường phân tán, theo định lý CAP, bạn không thể đảm bảo cả tính nhất quán và tính sẵn sàng một cách tuyệt đối.
4. Khả năng chịu lỗi: Các node có thể gặp sự cố hoặc bị mất kết nối tạm thời, nhưng hệ thống vẫn phải đảm bảo tiếp tục hoạt động.

2. Vì sao Distributed Counter lại phức tạp?

Để giải thích rõ hơn, chúng ta hãy xem một ví dụ đơn giản với hai node A và B, cùng cần cập nhật giá trị của một bộ đếm. Giả sử ban đầu bộ đếm có giá trị là 5:

1. Node A đọc giá trị hiện tại của bộ đếm: 5.
2. Node B cũng đọc giá trị hiện tại của bộ đếm: 5.
3. Node A tăng giá trị lên 1 và ghi lại: 6.
4. Node B cũng tăng giá trị lên 1 và ghi lại: 6.

Kết quả cuối cùng: Bộ đếm vẫn là 6, trong khi hai thao tác tăng đã được thực hiện. Lẽ ra giá trị đúng phải là 7.

Tình huống trên chỉ xảy ra với hai node và đã cho thấy hạn chế của distributed counter. Hãy tưởng tượng nếu có hàng nghìn hoặc hàng triệu node cùng cập nhật đồng thời, vấn đề sẽ nghiêm trọng hơn.

Distributed Counter là một vấn đề phức tạp trong hệ thống phân tán vì phải cân bằng tính đồng thời, khả năng chịu lỗi, và hiệu suất mà không làm mất dữ liệu hoặc tạo ra kết quả sai lệch.

3. Giải pháp cho bài toán Distributed Counter

3.1  Strong Consistency - Two-Phase Commit (2PC)

Two-Phase Commit (2PC) là một giao thức được dùng trong hệ thống phân tán nhằm đảm bảo tính nhất quán mạnh. Quá trình cập nhật được chia thành hai giai đoạn: prepare (chuẩn bị) và commit (xác nhận).

1. Giai đoạn 1 (Prepare):
   Điều phối viên (coordinator) gửi yêu cầu tới tất cả các node tham gia transaction để kiểm tra xem chúng có thể hoàn tất giao dịch hay không (bước chuẩn bị).
2. Giai đoạn 2 (Commit):
   • Nếu tất cả node xác nhận “OK” (đồng ý), coordinator sẽ gửi lệnh commit để xác nhận hoàn thành giao dịch.
   • Ngược lại, nếu bất kỳ node nào từ chối (không thể thực hiện), lệnh rollback sẽ được gửi để hủy bỏ transaction.

Khi nào nên dùng 2PC? 2PC phù hợp với các hệ thống yêu cầu tính nhất quán và độ chính xác cao hơn tính sẵn sàng, ví dụ:

• Hệ thống ngân hàng: Đảm bảo mỗi giao dịch tài chính (ví dụ gửi tiền, rút tiền) được xử lý chính xác tuyệt đối.
• Hệ thống đặt vé: Đảm bảo một chỗ ngồi chỉ được đặt một lần.
• Các ứng dụng yêu cầu tính toàn vẹn dữ liệu: Ưu tiên độ chính xác hơn so với tốc độ hoặc tính sẵn sàng.

3.2 Quorum-based

Quorum-based counter là một cách tiếp cận sử dụng nguyên tắc "đa số" (majority) để đạt được sự cân bằng giữa tính nhất quán và hiệu suất trong hệ thống phân tán.

Cách hoạt động của Quorum-based:

1. Hệ thống gồm N node replica:
   Mỗi node là một bản sao của dữ liệu, tham gia vào quá trình đọc và ghi.
2. Ghi (Write):
   • Một thao tác ghi sẽ được coi là thành công nếu nhận được W phản hồi đồng ý từ các node.
   • Trong đó: W < N (số lượng phản hồi ghi cần ít hơn tổng số node).
3. Đọc (Read):
   • Một thao tác đọc sẽ thành công khi nhận được R phản hồi từ các node.
   • Trong đó: R < N (số lượng phản hồi đọc cần cũng ít hơn tổng số node).
4. Điều kiện đảm bảo nhất quán:
   • Để đảm bảo dữ liệu nhất quán, cần thỏa mãn điều kiện: W + R > N.
   • Điều này giúp đảm bảo rằng phần dữ liệu được ghi mới nhất luôn được ít nhất một node trong tập hợp R tham gia vào thao tác đọc.

Khi nào nên sử dụng Quorum-Based Counter?

• Khi hệ thống cần cân bằng giữa tính chính xác và hiệu suất, thay vì ưu tiên tuyệt đối một trong hai.
• Khi ứng dụng có thể chấp nhận độ trễ nhỏ trong việc cập nhật giá trị counter.
• Khi hệ thống yêu cầu khả năng mở rộng cao hơn so với các giao thức như Two-Phase Commit (2PC).

3.3 CRDT (Conflict-free Replicated Data Types)

CRDT (Conflict-Free Replicated Data Type) là một loại cấu trúc dữ liệu đặc biệt được thiết kế cho các hệ thống phân tán. Điểm đặc biệt của CRDT là khả năng giải quyết xung đột dữ liệu một cách tự động mà không cần đến sự phối hợp hoặc đồng bộ từ một trung tâm điều khiển.

Nói cách khác, khi nhiều node trong một hệ thống phân tán cùng sửa đổi hoặc cập nhật dữ liệu, CRDT đảm bảo các dữ liệu đó có thể hợp nhất lại với nhau một cách chính xác mà không yêu cầu các node liên lạc để giải quyết xung đột.

Riak, một cơ sở dữ liệu NoSQL phân tán, sử dụng CRDT để triển khai counter. SoundCloud đã áp dụng Riak với CRDT để theo dõi số lượt nghe nhạc.

Nguyên tắc hoạt động:

1. Mỗi node duy trì hai counter: P (tăng) và N (giảm)
2. Mỗi node chỉ cập nhật counter của chính nó
3. Khi hợp nhất, lấy giá trị lớn nhất của mỗi counter ở mỗi node
4. Giá trị cuối cùng = tổng tất cả P - tổng tất cả N

Để hiểu rõ cách CRDT hoạt động, chúng ta hãy xem xét một ví dụ cụ thể về hệ thống đếm lượt xem video triển khai trên 3 data center khác nhau:

• Data center A: Phục vụ người dùng tại Bắc Mỹ
• Data center B: Phục vụ người dùng tại Châu Âu
• Data center C: Phục vụ người dùng tại Châu Á

Thiết lập ban đầu: Mỗi data center duy trì hai vector:

• P (positive): Vector ghi nhận các thao tác tăng
• N (negative): Vector ghi nhận các thao tác giảm

Ban đầu, mỗi data center có state như sau:

Data center A: P_A = [0,0,0], N_A = [0,0,0]
Data center B: P_B = [0,0,0], N_B = [0,0,0]
Data center C: P_C = [0,0,0], N_C = [0,0,0]

Mỗi phần tử trong vector tương ứng với đóng góp của một data center vào counter tổng.

• Sự kiện 1: Người dùng tại Bắc Mỹ xem video (tăng counter) :P_A = [1,0,0], N_A = [0,0,0]. Data center A chỉ cập nhật phần tử đầu tiên trong vector P, tương ứng với "phần đóng góp" của nó.
• Sự kiện 2: Đồng thời, người dùng tại Châu Âu cũng xem video, P_B = [0,1,0], N_B = [0,0,0]. Lúc này, hai data center chưa biết về cập nhật của nhau.
• Sự kiện 3: Hệ thống phát hiện view không hợp lệ tại Châu Á và giảm counter: P_C = [0,0,0], N_C = [0,0,1]

Quá trình hợp nhất (Merge): Sau một khoảng thời gian, các data center bắt đầu trao đổi thông tin. Ví dụ, A và B trao đổi dữ liệu với nhau, quá trình merge lấy giá trị lớn nhất tương ứng từ mỗi vector:

• A nhận data từ B và merge:
  P_A = [max(1,0), max(0,1), max(0,0)] = [1,1,0]
  N_A = [max(0,0), max(0,0), max(0,0)] = [0,0,0]
• B nhận data từ A và merge:
  P_B = [max(0,1), max(1,0), max(0,0)] = [1,1,0]
  N_B = [max(0,0), max(0,0), max(0,0)] = [0,0,0]
• Tiếp theo, B và C trao đổi dữ liệu:
  P_B = [max(1,0), max(1,0), max(0,0)] = [1,1,0]
  N_B = [max(0,0), max(0,0), max(0,1)] = [0,0,1]
• C merge với B:
  P_C = [max(0,1), max(0,1), max(0,0)] = [1,1,0]
  N_C = [max(0,0), max(0,0), max(1,0)] = [0,0,1]
• Cuối cùng, A và C trao đổi dữ liệu:
  P_A = [max(1,1), max(1,1), max(0,0)] = [1,1,0]
  N_A = [max(0,0), max(0,0), max(0,1)] = [0,0,1]
• C merge với A:
  P_C = [max(1,1), max(1,1), max(0,0)] = [1,1,0]
  N_C = [max(0,0), max(0,0), max(1,0)] = [0,0,1]
  

Sau quá trình merge, tất cả các node đều có state giống nhau:P = [1,1,0]
N = [0,0,1]. Giá trị cuối cùng của counter được tính:

Value = sum(P) - sum(N) = (1+1+0) - (0+0+1) = 2 - 1 = 1

Khi nào sử dụng CRDT:

• Hệ thống cần tính sẵn sàng cao hơn tính nhất quán tức thời.
• Ứng dụng có thể chấp nhận tính nhất quán cuối cùng.
• Môi trường có kết nối không ổn định giữa các node.

3.4 Probabilistic Counters - HyperLogLog

HyperLogLog là một phương pháp đếm xác suất, rất hiệu quả cho các ứng dụng không cần kết quả chính xác 100%, nhưng lại yêu cầu tiết kiệm bộ nhớ.

Cách HyperLogLog hoạt động:

1. Dùng hàm hash để chuyển mỗi phần tử thành một giá trị ngẫu nhiên.
2. Chia các giá trị hash này vào các nhóm nhỏ (gọi là bucket).
3. Trong mỗi bucket, theo dõi số lượng bit 0 liên tiếp ở phần đầu của giá trị hash (càng nhiều bit 0, phần tử càng hiếm gặp).
4. Dựa vào các giá trị này, dùng công thức xác suất để ước tính tổng số phần tử khác biệt.

Google Analytics sử dụng phương pháp tương tự để theo dõi số lượng người dùng duy nhất trên các trang web. Với hàng tỷ lượt truy cập mỗi ngày, việc lưu trữ thông tin chính xác về mỗi người dùng sẽ tiêu tốn quá nhiều tài nguyên. Thay vào đó, Google Analytics sử dụng HyperLogLog để cung cấp ước tính với độ chính xác cao mà không cần lưu trữ tất cả dữ liệu.

Khi nào nên sử dụng HyperLogLog:

1. Khi cần đếm số người dùng duy nhất truy cập trang web: Phù hợp để ước tính lượt truy cập với chi phí bộ nhớ cực thấp.
2. Khi phân tích dữ liệu lớn và chỉ cần số liệu gần đúng: Dùng trong các tình huống không yêu cầu độ chính xác tuyệt đối mà cần hiệu quả về thời gian và bộ nhớ.
3. Khi hệ thống cần đếm hàng tỷ phần tử: HyperLogLog hoạt động tốt trong các kịch bản có khối lượng dữ liệu cực lớn, khi các phương pháp đếm chính xác sẽ tiêu tốn quá nhiều bộ nhớ.

3.5 Gossip-based Protocol

Gossip Protocol là một phương pháp phi tập trung giúp truyền thông tin trong hệ thống phân tán. Cách hoạt động của nó giống như sự lan truyền tin đồn trong xã hội.

Cách Gossip Protocol hoạt động:

1. Mỗi node trong hệ thống sẽ định kỳ chọn ngẫu nhiên một node khác để trao đổi thông tin.
2. Thông tin sau đó được lan truyền từ node này sang node khác.
3. Dần dần, thông tin sẽ lan đến toàn bộ hệ thống với tốc độ ngày càng nhanh (hội tụ theo cấp số nhân).

Khi nào nên sử dụng Gossip Protocol:

• Khi hệ thống có nhiều node hoạt động không ổn định (ví dụ mạng P2P): Gossip Protocol hoạt động tốt trong những hệ thống lớn, nơi các node có thể kết nối hoặc ngắt kết nối bất chợt mà không ảnh hưởng đến việc truyền thông tin.
• Khi môi trường có băng thông hạn chế nhưng vẫn cần truyền tải thông tin: Gossip Protocol sử dụng ít tài nguyên mạng nhờ thiết kế tối giản, giúp dữ liệu được trao đổi hiệu quả trong môi trường có băng thông thấp.
• Khi hệ thống cần ưu tiên tính sẵn sàng và khả năng chịu lỗi hơn việc giảm độ trễ: Gossip Protocol đảm bảo hệ thống luôn ổn định và đáng tin cậy ngay cả khi một số node bị lỗi hoặc mất kết nối, mà không cần phụ thuộc vào một node trung tâm.

Apache Cassandra sử dụng Gossip Protocol để truyền thông tin về cấu trúc hệ thống (topology) và trạng thái của các node. Trong Cassandra, mỗi node sẽ định kỳ trao đổi thông tin với tối đa 3 node khác. Nhờ vậy, các thông tin như node mới tham gia hoặc node gặp lỗi sẽ nhanh chóng được lan truyền khắp toàn bộ cluster.

4. CAP Theorem và Distributed Counters

Theo định lý CAP, một hệ thống phân tán không thể đồng thời đảm bảo cả 3 yếu tố:

• Consistency (Tính nhất quán): Dữ liệu giống nhau trên tất cả các node.
• Availability (Tính sẵn sàng): Hệ thống luôn phản hồi, ngay cả khi xảy ra lỗi.
• Partition Tolerance (Khả năng chịu phân vùng mạng): Hệ thống vẫn hoạt động khi có sự cố gây gián đoạn kết nối giữa các node.

Với distributed counters, các hệ thống phải chấp nhận đánh đổi giữa các yếu tố này. Dưới đây là một số loại counter phổ biến, kèm theo các lựa chọn và đánh đổi của chúng:

Loại Counter	Ưu tiên C/A/P	Ứng dụng	Đánh đổi
Strong Consistency Counter (2PC)	CP	Hệ thống tài chính, đặt vé	Giảm tính sẵn sàng khi xảy ra phân vùng mạng.
Quorum-based Counter	Tunable (CP hoặc AP)	Lượt thích, lượt xem trên mạng xã hội	Cân bằng giữa tính nhất quán và tính sẵn sàng tùy theo cấu hình.
CRDT Counter	AP	Chỉnh sửa hợp tác, đo lường	Chỉ đảm bảo tính nhất quán dần dần, triển khai phức tạp.
Gossip-based Counter	AP	Giám sát hệ thống, mạng P2P	Đảm bảo tính nhất quán dần dần, nhưng tiêu tốn nhiều băng thông.

Một ví dụ nổi bật là hệ thống PNUTS của Yahoo!, một cơ sở dữ liệu phân tán sử dụng khái niệm "per-record timeline consistency":

• Mỗi bản ghi (record) được gắn với một master region, nơi đảm bảo tính nhất quán mạnh cho các thao tác ghi.
• Ở các region khác, hệ thống chấp nhận tính nhất quán yếu hơn để tăng hiệu năng.

5. Kết luận

rong bài viết này, chúng ta đã điểm qua các khái niệm cơ bản và những trade-off của từng loại counter. Tuy nhiên do nội dung của nó khá dài hình sẽ viết bài hướng dẫn triển khai distributed counter trong các bài viết tiếp theo nhé.