Khám phá QuePaxa: Thuật toán đồng thuận đột phá cho hệ thống phân tán toàn cầu

Cloudflare vừa công bố Meerkat, một dịch vụ đồng thuận phân tán thử nghiệm được thiết kế để quản lý control plane nội bộ trên quy mô toàn cầu. Điểm nhấn của Meerkat nằm ở việc sử dụng QuePaxa (2023) – một thuật toán đồng thuận mới do các nhà nghiên cứu Tennage & Băsescu et al. phát triển.

Tại sao cần một thuật toán mới?

Hầu hết các hệ thống đồng thuận hiện nay dựa trên các thuật toán truyền thống như Raft, Paxos hoặc Viewstamped Replication. Dù rất phổ biến và ổn định trong các mạng cục bộ, chúng thường gặp khó khăn khi triển khai trên diện rộng (wide-area networks) – nơi có độ trễ cao và kết nối không ổn định như Internet.

Vấn đề cốt lõi của các thuật toán này là sự phụ thuộc vào một leader duy nhất. Nếu leader gặp sự cố, bị trễ hoặc mất kết nối, toàn bộ hệ thống sẽ bị đình trệ cho đến khi một leader mới được bầu chọn. Đối với một hệ thống toàn cầu như Meerkat, sự gián đoạn này là không thể chấp nhận được.

Thách thức của sự đồng thuận ở quy mô toàn cầu

Các thuật toán dựa trên leader thường đối mặt với hai vấn đề lớn:

• Destructive interference (Nhiễu phá hoại): Khi nhiều proposer cùng gửi yêu cầu, chúng có thể xung đột và chặn lẫn nhau, dẫn đến việc hệ thống không thể đạt được sự đồng thuận dù không có node nào bị hỏng.
• Fault detection (Phát hiện lỗi) thiếu chính xác: Trong môi trường mạng không đồng bộ, rất khó để phân biệt giữa một server bị sập và một server chỉ đơn giản là đang phản hồi chậm do độ trễ mạng. Việc đưa ra quyết định sai lầm về trạng thái của leader thường dẫn đến các đợt bầu chọn không cần thiết, gây ra tình trạng metastable failure – nơi hệ thống liên tục bầu chọn lại ngay cả khi sự cố mạng đã qua.

QuePaxa: Giải pháp cho môi trường không đồng bộ

QuePaxa được Cloudflare lựa chọn nhờ khả năng vận hành hiệu quả mà không phụ thuộc hoàn toàn vào leader hay các cơ chế phát hiện lỗi khắt khe. Thuật toán này mang lại ba ưu điểm vượt trội:

• Leader tùy chọn: Hệ thống không bị tê liệt nếu không có leader.
• Loại bỏ sự phụ thuộc vào fault detection: QuePaxa được thiết kế để hoạt động ổn định ngay cả trong môi trường mạng có độ trễ biến thiên cao.
• Constructive interference (Nhiễu xây dựng): Thay vì cạnh tranh, các proposer trong QuePaxa hợp tác với nhau. Bằng cách gán các mức độ ưu tiên (priority) ngẫu nhiên cho các đề xuất, các proposer sẽ hỗ trợ nhau hướng tới một kết quả chung thay vì chặn lẫn nhau.

Nhờ cơ chế này, QuePaxa có thể đạt được sự đồng thuận chỉ trong một vòng gửi nhận (round trip) trong điều kiện mạng thuận lợi, đồng thời vẫn duy trì được hiệu suất ổn định ngay cả khi xảy ra các đợt tăng đột biến về độ trễ hoặc mất kết nối cục bộ.

Nguồn tham khảo: Cloudflare Blog