Thuật toán đồng thuận Raft (2015)
(raft.github.io)- Raft được thiết kế để diễn giải dễ hiểu hơn bài toán đồng thuận trong đó nhiều máy chủ trong hệ thống phân tán phải đi đến cùng một quyết định, với mục tiêu đạt khả năng chịu lỗi và hiệu năng tương đương Paxos
- Raft chia cấu trúc thành các bài toán con như bầu chọn leader, sao chép log và an toàn để làm rõ các điểm ra quyết định cần thiết khi triển khai máy trạng thái sao chép
- Hệ thống có thể tiếp tục hoạt động nếu đa số máy chủ còn sống, và vẫn giữ được tính an toàn bằng cách dừng lại khi mất đa số thay vì đưa ra kết quả sai
- Trang web tập hợp RaftScope chạy trong trình duyệt, hình dung hóa The Secret Lives of Data, bài báo Raft, đặc tả TLA+, cùng các bài báo và tài liệu thuyết trình về kiểm chứng, phân tích
- Có danh sách các bản triển khai bằng nhiều ngôn ngữ như Rust, Go, Java, C++, C#, Python, với mức hỗ trợ khác nhau cho bầu chọn leader·sao chép log, tính bền vững, thay đổi thành viên và nén log
Bài toán đồng thuận mà Raft nhắm tới
- Raft được thiết kế để giúp thuật toán đồng thuận trở nên dễ hiểu hơn với lượng độc giả rộng hơn
- Mục tiêu là đạt mức chịu lỗi và hiệu năng tương đương Paxos
- Khác biệt cốt lõi nằm ở cấu trúc
- Chia bài toán thành các bài toán con tương đối độc lập
- Tách riêng các thành phần cần thiết để triển khai hệ thống thực tế
- Mục tiêu là giúp các hệ thống dựa trên đồng thuận dễ hiểu hơn và có thể được triển khai với chất lượng cao hơn
Đồng thuận và máy trạng thái sao chép
- Đồng thuận (consensus) là bài toán nền tảng của hệ thống phân tán chịu lỗi
- Nhiều máy chủ cùng đồng ý trên một giá trị, và giá trị đã được quyết định một lần sẽ trở thành trạng thái cuối cùng
- Các thuật toán đồng thuận điển hình sẽ tiếp tục hoạt động khi đa số máy chủ còn khả dụng
- Cụm 5 máy chủ vẫn có thể tiếp tục hoạt động ngay cả khi 2 máy chủ gặp sự cố
- Nếu nhiều máy chủ hơn bị lỗi thì tiến trình sẽ dừng lại
- Ngay cả khi đó, điều quan trọng là không được trả về kết quả sai
- Đồng thuận thường được dùng để xây dựng máy trạng thái sao chép
- Mỗi máy chủ có một máy trạng thái và một log
- Máy trạng thái có thể là thành phần cần được bổ sung khả năng chịu lỗi, chẳng hạn như bảng băm
- Máy khách có thể nhìn nhận như đang tương tác với một máy trạng thái đáng tin cậy duy nhất ngay cả khi một số máy chủ gặp sự cố
- Mỗi máy trạng thái nhận lệnh từ log của chính nó làm đầu vào
- Trong ví dụ bảng băm, các lệnh như
set x to 3sẽ được ghi vào log - Thuật toán đồng thuận quyết định lệnh nào được đưa vào log máy chủ và theo thứ tự nào
- Nếu một máy trạng thái đã áp dụng
set x to 3làm lệnh thứ n, thì phải bảo đảm rằng máy trạng thái khác không áp dụng một lệnh khác ở cùng vị trí đó
- Trong ví dụ bảng băm, các lệnh như
- Kết quả là mọi máy trạng thái đều xử lý cùng một chuỗi lệnh và đi đến cùng một chuỗi kết quả cũng như chuỗi trạng thái
Hình dung hóa để hiểu Raft
- Có thể trực tiếp thao tác hình dung hóa cụm Raft chạy trong trình duyệt
- Bên trái hiển thị 5 máy chủ
- Bên phải hiển thị log của từng máy chủ
- Người dùng có thể tương tác để quan sát cách Raft hoạt động
- RaftScope vẫn còn nhiều chỗ cần hoàn thiện và hoan nghênh Pull Request
- The Secret Lives of Data là một hình dung hóa khác về Raft
- Có tính dẫn dắt nhiều hơn và ít tương tác hơn
- Có thể là điểm bắt đầu nhẹ nhàng hơn cho người mới tiếp cận
Bài báo, đặc tả và tài liệu kiểm chứng
- In Search of an Understandable Consensus Algorithm (Extended Version) là “bài báo Raft” trình bày chi tiết về Raft
- Do Diego Ongaro và John Ousterhout viết
- Phiên bản ngắn hơn một chút đã nhận Best Paper Award tại 2014 USENIX Annual Technical Conference
- Ph.D. dissertation của Diego Ongaro mở rộng nội dung bài báo theo hướng sâu hơn
- Bao gồm một thuật toán thay đổi thành viên cụm đơn giản hơn
- Cũng chứa đặc tả hình thức TLA+ của Raft
- Một đặc tả được cập nhật nhẹ có thể xem tại raft.tla
- Các bài báo liên quan đề cập đến kiểm chứng hình thức của Raft, framework triển khai·kiểm chứng hệ thống phân tán, sinh mã từ mô hình hình thức và phân tích giao thức
- Planning for Change in a Formal Verification of the Raft Consensus Protocol, CPP 2016
- Verdi: A Framework for Implementing and Verifying Distributed Systems, PLDI 2015
- Automatic Distributed Code Generation from Formal Models of Asynchronous Concurrent Processes, PDP 2015
- Raft Refloated: Do We Have Consensus?, SIGOPS Operating Systems Review 2015
- ARC: Analysis of Raft Consensus, University of Cambridge Technical Report 2014
Bài giảng và tài liệu học tập
- Danh sách các bài giảng nhập môn về Raft cũng được tổng hợp
- Bài giảng trong CS@Illinois Distinguished Lecture Series của John Ousterhout, tháng 8/2016
- Bài giảng về Raft và đặc tả TLA+ trong Dr. TLA+ Series của Jin Li, tháng 7/2016
- Các bài nói chuyện của Diego Ongaro tại Build Stuff 2015, CoreOS Fest 2015, Sourcegraph meetup, LinkedIn, USENIX ATC 2014, CraftConf 2014, RICON West 2013
- Bài thuyết trình của Ben Johnson tại Strange Loop 2013
- Bài giảng Raft User Study của John Ousterhout, tháng 3/2013
- Raft cũng được dùng trong các khóa học đại học·đào tạo dưới dạng bài giảng hoặc bài tập lập trình
- Bao gồm nhiều khóa học tại University of Copenhagen, Czech Technical University in Prague, The University of Hong Kong, University of Virginia, UC San Diego, Technical University of Munich, UIUC...
- Một số khóa học cung cấp bài tập lập trình Raft bằng Go, Java, Erlang...
- MIT 6.824 có kèm ghi chú bài giảng về Raft, đồng thời giới thiệu các bài viết về Raft cho giảng viên và sinh viên của Jon Gjengset
- Có thể cập nhật thêm các khóa học vào kho lưu trữ của trang qua Pull Request hoặc issue
Kênh hỏi đáp và danh sách bản triển khai
- Các câu hỏi về Raft và các bản triển khai được hướng dẫn gửi tới raft-dev Google group
- Một số bản triển khai có mailing list riêng, nên cần kiểm tra README tương ứng
- Trang cũng cung cấp danh sách các bản triển khai Raft có mã nguồn công khai
- Những bản triển khai phổ biến hoặc được cập nhật gần đây được đặt ở phía trên bảng
- Thông tin có thể cũ đi theo thời gian nên có thể cập nhật bằng Pull Request hoặc issue
- Bảng so sánh Stars, tên, tác giả chính, ngôn ngữ, giấy phép và mức hỗ trợ tính năng của từng bản triển khai
- Các mục tính năng gồm bầu chọn leader và sao chép log, tính bền vững, thay đổi thành viên, nén log
- Một số ví dụ ở đầu danh sách như sau
- TiKV: Rust, Apache-2.0, 16,751★, hỗ trợ đầy đủ bầu chọn leader·sao chép log/tính bền vững/thay đổi thành viên/nén log
- RethinkDB: C++, Apache-2.0, 27,000★, hỗ trợ đầy đủ các tính năng chính
- Seastar Raft: C++20, AGPL, 15,624★, hỗ trợ đầy đủ các tính năng chính
- hashicorp/raft: Go, MPL-2.0, 9,048★, hỗ trợ đầy đủ các tính năng chính
- hazelcast-raft: Java, Apache-2.0, 6,579★, hỗ trợ đầy đủ các tính năng chính
- Danh sách bao gồm các bản triển khai bằng nhiều ngôn ngữ như Rust, Go, Java, C++, C, Erlang, Python, Scala, C#, JavaScript, Haskell, OCaml, Kotlin, Zig, TypeScript, Elixir, F#, Shell...
1 bình luận
Các bình luận trên Hacker News
Maelstrom, bàn thử nghiệm để học hệ thống phân tán của tác giả Jepsen, có sẵn một bản triển khai kiểm chứng mô hình đơn giản của Raft cùng một hướng dẫn triển khai rất tốt: https://github.com/jepsen-io/maelstrom/
Raft là một thuật toán đơn giản, nhưng bài báo gốc có nhiều chi tiết về tính đúng đắn thường bị bỏ qua trong các bản triển khai đồ chơi
Nếu tính đến hỏng hóc bộ nhớ/đĩa trên phần cứng thực, lỗi xám, SLA độ trễ chặt chẽ, quorum linh hoạt và tư cách thành viên cụm động, thì triển khai production trở thành một công việc dài và nặng nề
Chỉ cần nhìn vào lịch sử commit của etcd và hashicorp/raft cũng thấy ngay rằng ngay cả những triển khai Raft mã nguồn mở được kiểm chứng nhiều nhất cũng thường xuyên lộ ra các lỗi về tính đúng đắn
Nhóm TigerBeetle bàn rất kỹ về thực tế của hệ thống phân tán trên phần cứng không hoàn hảo và mô hình hệ thống không được trừu tượng hóa, đồng thời cũng giải thích vì sao họ chọn Viewstamped Replication, vốn ra đời trước Paxos nhưng trông có vẻ giống Raft hơn: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...
Tôi không chắc điều đó dẫn đến kết quả gì cho các băn khoăn khi triển khai, nhưng bản thân bài báo rất hay nên muốn giới thiệu
Cũng có bài thuyết trình, nhưng tôi nghĩ đọc bài viết thì tiện tham chiếu qua lại hơn: https://www.youtube.com/watch?v=0K6kt39wyH0
Dù trước đó chưa từng xem thuật toán đồng thuận nào, sau khi đọc vài lần tôi vẫn có thể theo được ở mức nào đó: https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
Gần đây tôi đã thử triển khai bầu chọn leader và nhân bản log của Raft; chưa đi tới snapshot/checkpoint, nhưng đây vẫn thuộc nhóm những dự án khó nhất tôi từng làm
Bài báo Raft dễ đọc và đem lại trực giác tốt
Ngay cả nếu không tự triển khai, rất có thể bạn đã đang dùng phần mềm dựa trên Raft như etcd, Consul, CockroachDB, TiDB
Tôi đã tập hợp các tài liệu hữu ích khi triển khai ở đây: https://github.com/eatonphil/goraft#references
Trong đó có cả luận án tiến sĩ của Diego Ongaro và đặc tả TLA+
Có người nói “chỉ cần Figure 2 trong bài báo Raft là đủ”, nhưng khi so với đặc tả TLA+ thì nó mơ hồ hơn nhiều, nên tôi nghĩ điều đó không đúng
Tôi khuyên nên thử ghép với bài test Raft trong môn hệ thống phân tán của MIT: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
Ít nhất phần bầu chọn leader và nhân bản log có vẻ có thể làm được chỉ với một chút refactor
Đặc biệt rất đáng giới thiệu cho người lần đầu tiếp xúc với thuật toán phân tán
Chất lượng triển khai có lẽ không xuất sắc, nhưng tôi đăng lên cho ai quan tâm: https://github.com/skowalak/fastapi-raft/
Trong bài báo còn có thêm vài chi tiết cụ thể cần thiết khi triển khai
Nếu bạn quan tâm đến thuật toán đồng thuận, cuốn Reasoning about Knowledge mà chúng tôi từng dùng trong một lớp lý thuyết hệ thống phân tán cũng đáng xem: https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...
Cần đầu tư một chút để học logic modal, nhưng vượt qua phần đó rồi thì các chứng minh về vì sao Raft hay Paxos hoạt động trở nên rất trực quan và đơn giản
Đây là cách đẩy độ phức tạp của chứng minh vào cấu trúc logic dùng trong chứng minh, và nó đã thay đổi góc nhìn của tôi về đồng thuận
“Raft Consensus Algorithm Failure”, Théodore Géricault, 1819: https://classicprogrammerpaintings.com/post/6141087496359280...
Nếu không biết phần trực quan hóa đang cho thấy điều gì, chỉ cần nhớ rằng bạn có thể nhấp vào một nút để làm nó gặp lỗi
Đặc biệt nên thử với nút hiện là leader, nút đang gửi và nhận tất cả các gói tin
Nhấn biểu tượng tạm dừng nhỏ cạnh thanh trượt đầu tiên để chuyển lại thành đồng hồ, mô phỏng sẽ tiếp tục
Tôi vẫn chưa biết bảng tính bên phải là gì, và vì nó luôn trống nên trông như bị hỏng
Những phần có thể nhấp mà tôi tìm thấy đến giờ là hai thanh trượt, biểu tượng đồng hồ/tạm dừng, và từng máy chủ riêng lẻ
Nếu nhấp vào leader và chọn
request, bạn có thể mô phỏng việc gửi lệnhNếu đưa một bản sao offline, bạn có thể thấy nó bị tụt lại, rồi bắt kịp khi quay trở lại
Vài năm trước, tôi từng ở trong môi trường mà một hệ thống kiểu Chubby vững chắc dưới tải nghiêm trọng luôn là thứ quan trọng, và khi đó nếu không được phép thất bại thì dùng ZooKeeper
Nhưng giờ tôi biết là mọi người đã chạy các workload rất nặng trên những lựa chọn dựa trên Raft như etcd, Consul trong nhiều năm
Tôi tò mò liệu một trong số chúng giờ đã trở thành lựa chọn mặc định chưa
Sự rõ ràng về mặt khái niệm và tính thanh nhã của Raft có vẻ sẽ chuyển hóa thành hiệu năng và độ tin cậy, nhưng cảm giác của tôi về lĩnh vực này đã cũ
Tôi tò mò năm 2023 những người không bị ràng buộc với Google hay GCP dùng gì như best practice mặc định cho các hệ thống có mức độ quan trọng cao
Hình như phía TiKV có một triển khai Raft bằng Rust ở cấp production, và một lock server vững chắc, hiệu năng cao có vẻ là lĩnh vực khá hợp với Rust; tôi cũng tò mò liệu nó có đang được dùng thực tế không
Nếu đây là câu trả lời cho “Raft là gì?”, thì đọc xong tôi vẫn không biết
“Raft là một thuật toán đồng thuận được thiết kế để dễ hiểu. Về khả năng chịu lỗi và hiệu năng, nó tương đương Paxos. Điểm khác biệt là nó được phân rã thành các bài toán con tương đối độc lập, và xử lý gọn gàng những phần chính cần cho các hệ thống thực dụng. Chúng tôi hy vọng Raft sẽ đưa đồng thuận đến với nhóm độc giả rộng hơn, và nhóm độc giả đó có thể xây dựng nhiều hệ thống dựa trên đồng thuận chất lượng cao, đa dạng hơn hiện nay”
Kiểu này không phải vấn đề riêng của họ, nhưng tôi thấy đáng tiếc là họ không dành thêm thời gian để giải thích đúng về công việc của mình
Vì nó tự động lọc ra những độc giả không hiểu ý nghĩa của nó
Với người đang xây dựng hệ thống phân tán và so sánh nhiều thuật toán đồng thuận, đây là một mô tả đơn giản, rõ ràng; còn nếu không thì khả năng cao đây vốn không phải thuật toán liên quan đến họ
Nói chung, thuật toán đồng thuận nhằm giải quyết vấn đề khi có các bản sao của một kho dữ liệu trải trên nhiều thiết bị vật lý, và cần quyết định phải làm gì khi một số thiết bị hoặc kết nối thất bại theo cách nào đó
Gọi là “đồng thuận” vì trong tình huống lỗi, các máy phải đồng thuận về quyết định cần đưa ra đối với một mẩu dữ liệu
Ví dụ, nếu ba máy chủ đang sao chép cùng một cơ sở dữ liệu SQL theo dạng
(A) - (B) - (C), khi kết nối mạng giữa C và hai máy còn lại bị đứt, A và B có thể biết điều đó và thăng cấp B thành nút chínhNhưng C không biết chuyện gì đã xảy ra và vẫn có thể tiếp tục nhận một số ghi
Khi kết nối được khôi phục, A, B, C giờ phải quyết định sẽ làm gì
Vì B và C đã độc lập nhận các tập ghi khác nhau, các máy chủ phải đồng thuận về cách xử lý dữ liệu
Đây chính là vấn đề mà Raft, Paxos, v.v. cố gắng giải quyết theo cách nhất quán và có hiệu năng tốt
Có những khái niệm quá lớn để giới thiệu trong một đoạn văn cho người hoàn toàn không có kiến thức nền
Dù vậy, tôi nghĩ bài được liên kết là tài liệu nhập môn rất tốt nếu đọc tiếp
Với tư cách là một nhà nghiên cứu giao thức đồng thuận, tôi cho rằng nhờ nghiên cứu blockchain trong 10 năm qua, đồng thuận đã trở nên dễ hiểu hơn nhiều
So với vậy, Raft, đặc biệt khi tính cả các phần tinh vi, đọc và triển khai như tiếng Hy Lạp
Nếu ai đó bắt đầu học giao thức đồng thuận bây giờ, có lẽ tôi sẽ cho họ bắt đầu từ Bitcoin rồi chuyển sang Paxos, Tendermint, Simplex, và bỏ qua Raft hoàn toàn
Simplex là bài báo do tôi viết, một phiên bản đơn giản hóa của PBFT
Raft trông tương đối đơn giản
Tôi tò mò blockchain cung cấp điều gì khiến nó dễ bảo trì hơn và khó mắc lỗi hơn so với “bầu leader và sao chép log”
Tôi thích trang này
Khi học và triển khai Raft trong lớp hệ thống phân tán, trang này thực sự hữu ích
Bản thân bài báo cũng khá dễ đọc
Cảm ơn vì đã làm cho Raft rõ ràng như vậy
Tôi thắc mắc liệu có thuật toán đồng thuận nào mà thay đổi không nhất thiết phải đi qua leader hay không
Trong nhiều hệ thống phân tán, người ta cũng muốn phân tán cả việc xử lý đầu vào
Một trong số đó là Chord: https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)
Chord là một vòng P2P trong đó các nút chia nhau lưu giá trị bằng consistent hashing
Mạng sử dụng thứ gọi là “finger table”, về bản chất là lưu thông tin sao chép dưới dạng bảng
Thông tin trong bảng này có thể sai hoặc đã cũ, và peer được truy cập có thể bảo bạn đi tới peer khác, thường là nút kế tiếp hoặc nút nối tiếp, rồi tiếp tục cho đến khi tìm thấy hoặc không tìm thấy giá trị
Lý do thuật toán này có thể dùng mà không có “leader” là vì nó vẫn hoạt động chỉ bằng cách đi tới một nút rồi quét tuyến tính qua tất cả các nút
Finger table để tăng tốc truy vấn không phải là bắt buộc
Các hệ thống như vậy thường có “leader” cho mỗi giao dịch, nhưng trong vận hành bình thường vai trò đó không bị tranh chấp
Điều phối viên giao dịch tự tuyên bố vai trò, nên bầu cử chỉ diễn ra khi điều phối viên thất bại vì lý do nào đó
Cũng có thể có nhiều leader đồng thời cho một dữ liệu hoặc khóa cụ thể
Cassandra hiện đang phát triển Accord, một giao thức không leader thuộc nhóm này
Thực ra Cassandra đã dùng một giao thức không leader cho LWT
Đó là một biến thể tối ưu hóa của Paxos đồng thuận đơn cổ điển, nhưng nếu các giao dịch cạnh tranh trên cùng một khóa được tuyên bố đồng thời thì overhead khá đáng kể
Nếu các giao dịch trải trên các chủ đề độc lập, có thể shard leader để phân tán tải
Cách làm là gán các dải không gian khóa cho các leader khác nhau và điều chỉnh bầu cử để mỗi nút có phần leadership phù hợp
Nếu muốn đi theo hướng không leader, thực chất có thể tổ chức mỗi lần ghi như một cuộc bầu cử
Với giao dịch tạm thời hoặc giao dịch lớn, có thể broadcast yêu cầu giao dịch tới tất cả các nút; nếu đạt quorum chấp nhận thì nó thắng và được commit
Nhưng nếu nhiều nút thử giao dịch gần như cùng lúc, việc đạt đồng thuận có thể mất nhiều thời gian
Khi có nhiều nút và tất cả đều có giao dịch đang chờ trên cùng một chủ đề, bầu một leader rồi gửi mọi giao dịch qua leader sẽ nhanh hơn nhiều so với thiết lập đồng thuận riêng cho từng giao dịch
Tuy nhiên, nếu mục đích là phân tán để tăng throughput, một cách chỉ cần một leader có thể hiệu quả hơn so với quorum mà Paxos yêu cầu
Dù đây chỉ là suy đoán
Paxos cũng hiệu quả hơn nếu các lời gọi lần nào cũng đi tới cùng một nơi
Vì có thể tránh tranh chấp và bỏ phiếu lại, v.v.
Về bản chất, mỗi shard có đồng thuận Paxos riêng của nó