Cloudflare chọn QuePaxa: thuật toán đồng thuận không cần leader cho mạng 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 dùng để quản lý mặt phẳng điều khiển toàn cầu nội bộ. Meerkat chạy trên QuePaxa, thuật toán đồng thuận mới do Tennage và Băsescu cùng cộng sự công bố năm 2023. Đây là lựa chọn khá lạ, vì phần lớn hệ thống đồng thuận dùng các thuật toán quen thuộc như Raft, (Multi-)Paxos hay Viewstamped Replication.

Vì sao không dùng thuật toán phổ biến

Các thuật toán đồng thuận phổ biến thường gặp vấn đề trong mạng diện rộng có kết nối và độ trễ biến động, tức môi trường giống Internet — nơi Meerkat vận hành. Chúng dựa vào một tiến trình leader luôn sẵn sàng và có độ trễ dự đoán được. Nếu leader gặp sự cố, chậm hơn bình thường hoặc mất kết nối, toàn bộ hệ thống sẽ chậm lại hoặc ngừng phục vụ cho đến khi có leader mới. Với Meerkat, điều này không thể chấp nhận.

Meerkat là hệ thống phân tán trong đó các bản sao thống nhất về một log sự kiện có thứ tự; mỗi sự kiện do thuật toán đồng thuận quyết định. Thuật toán đồng thuận đảm bảo các máy không bao giờ quyết định giá trị xung đột, nhờ đó log của các bản sao không phân kỳ. Meerkat dùng log này để cung cấp các ứng dụng như key-value store. Khác với Consul, etcd hay Apache ZooKeeper, Meerkat được thiết kế cho quy mô toàn cầu: một cụm có thể trải khắp các châu lục với đường truyền độ trễ cao và thay đổi thường xuyên.

Bài học từ sự cố năm 2020

Năm 2020, một bộ chuyển mạch lõi của Cloudflare gặp sự cố một phần khiến hệ thống dùng đồng thuận suy giảm, dashboard chạy chậm gấp 80 lần trong sáu giờ. Dữ liệu không mất, nhưng hệ thống không nhận ghi cho đến khi khắc phục. Điều này cho thấy thuật toán đồng thuận lý tưởng cần tiến triển được ngay cả khi độ trễ tăng vọt và kết nối đứt gãy, không chỉ khi máy chủ chết.

Can thiệp phá hoại và vấn đề leader

Trong Paxos, hai loại tiến trình là proposer và acceptor, với hai pha Prepare và Accept. Khi nhiều proposer gửi đề xuất cùng lúc, proposer khác có thể chèn số phiếu bầu cao hơn vào giữa hai pha, chặn các phiếu thấp hơn. Hai proposer có thể liên tục chặn nhau — gọi là can thiệp phá hoại. Càng nhiều proposer đồng thời, hệ thống càng dễ kẹt, dù không máy nào chết. Paxos vì thế không đảm bảo liveness nếu không giả định mạng bán đồng bộ.

Để tránh cạnh tranh, Raft, Multi-Paxos và Viewstamped Replication thêm một leader duy nhất được phép đề xuất. Cách này nhanh khi leader khỏe và mạng tốt, nhưng đổi lại hệ thống phụ thuộc vào leader. Khi leader chết, quá chậm hoặc mất kết nối, hệ thống đình trệ cho đến khi bầu leader mới.

Bầu leader và phát hiện lỗi

Quá trình bầu leader lại có thể tái tạo can thiệp phá hoại. Trong Raft, ứng viên cần đa số phiếu; nhiều bản sao cùng phát hiện leader mất và cùng tranh phiếu, chặn lẫn nhau. Càng nhiều cuộc bầu thất bại, càng nhiều ứng viên xuất hiện. Hiện tượng này gọi là lỗi siêu bền: sự cố tự duy trì dù nguyên nhân ban đầu đã hết. Một lần mất mạng hai giây có thể kích hoạt chuỗi bầu cử kéo dài hơn nhiều.

Phát hiện lỗi cũng khó vì trong mạng bất đồng bộ, không thể phân biệt máy chết với mạng chậm. Bộ phát hiện lỗi phải phỏng đoán dựa trên thời gian chờ so với kỳ vọng, và đôi khi đoán sai. Với thuật toán dựa trên leader, đoán sai là kích hoạt bầu cử và dừng toàn hệ thống. Kể cả khi đoán đúng, phát hiện lỗi vẫn chậm: timeout bầu cử của Raft thường đặt bằng 5-10 lần thời gian khứ hồi mạng, nên phát hiện leader lỗi có thể mất khoảng một giây — và chậm nhất là ở mạng toàn cầu độ trễ cao.

Lý do chọn QuePaxa

Cloudflare nhận thấy mọi thuật toán phụ thuộc leader nghiêm ngặt hoặc timeout chính xác đều sẽ đình trệ khi chạy trên Internet. Họ tìm các thuật toán thiết kế cho môi trường bất đồng bộ, không cần mạng hoạt động tốt hay định thời chính xác, và QuePaxa là lựa chọn phù hợp. Thuật toán này hứa hẹn ổn định hơn trước biến động, phần lớn nhờ không dựa vào leader để tiến triển.

Nguồn: Cloudflare Blog