QuePaxa: thuật toán đồng thuận khác thường và lý do Cloudflare chọn nó

Trong bài này
Vì sao đồng thuận ở quy mô toàn cầu khó
Thuật toán đồng thuận (consensus) cho phép một nhóm máy thống nhất một sự thật chung dù một số máy bị sập hoặc mất kết nối, và bảo đảm các máy không bao giờ chốt những giá trị mâu thuẫn. Meerkat dựa vào log có thứ tự như vậy để cung cấp ứng dụng như kho key-value, trong đó mỗi mục log là một get hoặc put; vì log không phân kỳ nên mọi replica dựng ra cùng một trạng thái. Consul, etcd và Apache ZooKeeper là các hệ thống tương tự. Khác với chúng, một cụm Meerkat có thể trải trên nhiều châu lục, qua những đường truyền có độ trễ cao và biến động, trong khi hệ thống đồng thuận thường chạy ở mạng nhỏ, cục bộ với yêu cầu độ trễ chặt.
Nhiều thuật toán trở nên chậm hoặc không sẵn sàng một cách không cân xứng khi điều kiện mạng xấu đi, dù máy không sập. Năm 2020, một switch mạng lõi của Cloudflare gặp lỗi một phần khiến một hệ thống dựa trên đồng thuận suy giảm, và dashboard chạy chậm hơn bình thường 80x trong sáu giờ. Hệ thống không mất dữ liệu nhưng không ghi được cho đến khi sự cố được xử lý.
Hai điểm yếu: destructive interference và fault detection
Trong Paxos có hai vai trò là proposer và acceptor, và hai pha là Prepare và Accept. Ở pha Prepare, proposer gửi một ballot number tới đa số acceptor; ở pha Accept, nó gửi proposal kèm ballot number đó, và nếu đa số vẫn giữ ballot ấy thì proposal được chấp nhận. Khi nhiều proposer hoạt động đồng thời, một proposer có thể chen ballot cao hơn vào giữa hai pha, chặn các ballot thấp hơn. Việc chặn lẫn nhau lặp đi lặp lại này gọi là destructive interference (can thiệp phá hoại), và càng nhiều proposer thì càng dễ xảy ra, dù không replica nào sập.
Để tránh cạnh tranh, Raft, Multi-Paxos và Viewstamped Replication thêm một leader duy nhất được quyền đề xuất. Cách này ép thứ tự cho các yêu cầu đồng thời và cho phép chốt quyết định trong một round trip mạng thay vì hai. Cái giá là leader phải luôn hoạt động và liên lạc được; nếu nó hỏng, quá chậm hoặc bị ngắt kết nối, hệ thống đứng cho đến khi bầu leader mới. Chính quá trình bầu cử lại có thể kéo destructive interference trở lại: ở Raft, các ứng viên cạnh tranh phiếu bầu của đa số và có thể chặn lẫn nhau.
Hệ quả là metastable failure (lỗi tự duy trì): kiểu lỗi vẫn tiếp diễn dù nguyên nhân ban đầu đã biến mất. Một sự cố mạng hai giây có thể làm leader trông như bị lỗi, kích hoạt bầu cử, bầu cử thất bại rồi lại kéo theo các cuộc bầu cử tiếp theo, kéo dài lâu hơn nhiều so với sự cố gốc.
QuePaxa giải quyết vấn đề như thế nào
QuePaxa đạt đồng thuận trong một round trip khi mạng thuận lợi, nhưng suy giảm hiệu năng một cách êm ái khi có đột biến độ trễ, sự cố kết nối hoặc máy chủ hỏng. Nó làm được điều này nhờ ba lựa chọn thiết kế.
Leader chỉ là tùy chọn: bất kỳ proposer nào cũng có thể đề xuất.
Loại bỏ hoàn toàn sự phụ thuộc vào phát hiện lỗi.
Thiết kế để các proposer can thiệp mang tính xây dựng (constructive interference), tức hợp tác thay vì cạnh tranh.
QuePaxa có hai vai trò: proposer đưa ra đề xuất, còn recorder làm trung gian ghi lại mọi proposal chúng thấy. Mỗi proposal mang một priority là số ngẫu nhiên, riêng leader tùy chọn luôn có priority cao nhất. Khi nhận proposal có priority cao hơn của mình, proposer chuyển sang phát proposal đó, nên các proposer cùng hướng tới proposal có priority cao nhất mà tập thể biết và không thể khóa nhau vô hạn. Vì có yếu tố ngẫu nhiên nên đây là thuật toán ngẫu nhiên hóa: hội tụ trong một round là rất có khả năng nhưng không chắc chắn, và nếu chưa đạt thì thử lại ở round mới, song với đủ số round thì các proposer chắc chắn đồng thuận.
Hedge timeout khác hẳn timeout của Raft hay Multi-Paxos: nó không phải phát hiện lỗi nên không bị ràng buộc bởi độ trễ mạng, do replica tự quyết định cục bộ và có thể nhỏ tùy ý. Timeout năm mili giây trong mạng có độ trễ 100 mili giây sẽ làm Raft đóng băng, còn ở QuePaxa nó chỉ làm tăng số proposer hoạt động. Đổi lại, hedging không miễn phí: nhiều proposer hơn nghĩa là nhiều proposal được phát hơn, tốn băng thông hơn và có thể mất nhiều thời gian hơn để chốt. Cloudflare sẵn sàng chấp nhận sự đánh đổi này.
Bốn pha trong mỗi round của QuePaxa
QuePaxa chạy theo các round, mỗi round gồm bốn pha. Đầu mỗi pha, proposer phát proposal đang chấp nhận tới mọi recorder, và khi nhận phản hồi từ đa số recorder thì chuyển sang pha kế tiếp. Nếu proposal chưa được chốt ở pha cuối, một round mới bắt đầu.
Pha 1 (Spread): proposer lan proposal đã chấp nhận tới đa số recorder, và recorder ghi nhớ proposal có priority cao nhất. Bước này ngăn giao thức về sau chốt một proposal priority thấp hơn. Pha 2 (Check and Decide): proposer hỏi đa số recorder về proposal có priority cao nhất đã thấy ở pha trước; nếu trùng với proposal mình đang chấp nhận thì chốt. Pha 3 (Carry Forward): proposer chưa chốt được chuẩn bị cho round sau bằng cách chấp nhận proposal tốt nhất tìm thấy ở đa số recorder.
Nguồn tham khảo
Các nguồn mà bài viết này dựa vào.
- Choosing QuePaxa, an unusual consensus algorithm (mở trong tab mới) — Cloudflare Blog


