อัลกอริทึมฉันทามติ Raft (2015)
(raft.github.io)- Raft ถูกออกแบบมาเพื่ออธิบาย ปัญหาฉันทามติ ที่ทำให้หลายเซิร์ฟเวอร์ในระบบกระจายตัดสินใจตรงกันได้ ให้ง่ายต่อความเข้าใจมากขึ้น โดยตั้งเป้าความทนทานต่อความขัดข้องและประสิทธิภาพในระดับเทียบเท่า Paxos
- Raft แบ่งโครงสร้างออกเป็นปัญหาย่อยอย่างการเลือกผู้นำ การทำซ้ำล็อก และความปลอดภัย เพื่อให้จุดตัดสินใจที่จำเป็นต่อการทำ replicated state machine ชัดเจนขึ้น
- ตราบใดที่เซิร์ฟเวอร์ส่วนใหญ่ยังทำงานอยู่ ระบบก็เดินหน้าต่อได้ และหากเสียงข้างมากหายไป แม้ระบบจะหยุด ก็ยังคง ความปลอดภัย โดยไม่ให้ผลลัพธ์ที่ผิดพลาด
- เว็บไซต์นี้รวบรวม RaftScope แบบทำงานบนเบราว์เซอร์ ภาพจำลอง The Secret Lives of Data, งานวิจัย Raft, สเปก TLA+, รวมถึงงานวิจัยและสไลด์การบรรยายด้านการตรวจพิสูจน์และการวิเคราะห์
- มีการรวบรวมอิมพลีเมนเทชันในหลายภาษา เช่น Rust, Go, Java, C++, C#, Python เป็นต้น และแต่ละอิมพลีเมนเทชันก็รองรับการเลือกผู้นำและการทำซ้ำล็อก, การคงอยู่ถาวร, การเปลี่ยนสมาชิก, และการบีบอัดล็อก ได้ต่างกัน
ปัญหาฉันทามติที่ Raft มุ่งแก้
- Raft ถูกออกแบบมาเพื่อทำให้อัลกอริทึมฉันทามติเข้าใจได้ง่ายขึ้นสำหรับผู้อ่านในวงกว้าง
- ตั้งเป้าความทนทานต่อความขัดข้องและประสิทธิภาพให้เทียบเท่า Paxos
- ความแตกต่างหลักอยู่ที่โครงสร้าง
- แยกปัญหาออกเป็นปัญหาย่อยที่ค่อนข้างเป็นอิสระต่อกัน
- แยกจัดการองค์ประกอบที่จำเป็นต่อการอิมพลีเมนต์ระบบจริง
- เป้าหมายคือทำให้ระบบที่อิงฉันทามติเข้าใจง่ายขึ้น และอิมพลีเมนต์ได้ด้วยคุณภาพที่สูงขึ้น
ฉันทามติและ replicated state machine
- ฉันทามติ (consensus) คือปัญหาพื้นฐานของระบบกระจายที่ทนต่อความขัดข้อง
- หลายเซิร์ฟเวอร์ต้องเห็นพ้องกับค่าเดียวกัน และเมื่อค่าถูกตัดสินแล้ว จะกลายเป็นสถานะสุดท้าย
- โดยทั่วไปอัลกอริทึมฉันทามติจะดำเนินต่อได้เมื่อ เสียงข้างมาก ของเซิร์ฟเวอร์ยังพร้อมใช้งาน
- คลัสเตอร์ที่มีเซิร์ฟเวอร์ 5 เครื่องยังทำงานต่อได้แม้เซิร์ฟเวอร์ 2 เครื่องล้มเหลว
- หากมีเซิร์ฟเวอร์ล้มเหลวมากกว่านั้น การทำงานต่อจะหยุดลง
- แต่ถึงอย่างนั้น สิ่งสำคัญคือจะต้องไม่คืนผลลัพธ์ที่ผิดพลาด
- ปกติฉันทามติถูกใช้เพื่อสร้าง replicated state machine
- แต่ละเซิร์ฟเวอร์มี state machine และล็อกของตัวเอง
- state machine อาจเป็นองค์ประกอบที่ต้องการให้มีความทนทานต่อความขัดข้อง เช่น hash table
- ไคลเอนต์สามารถมองได้เสมือนว่ากำลังโต้ตอบกับ state machine ที่เชื่อถือได้เพียงตัวเดียว แม้บางเซิร์ฟเวอร์จะล้มเหลว
- แต่ละ state machine รับคำสั่งจากล็อกของตัวเองเป็นอินพุต
- ในตัวอย่าง hash table จะมีคำสั่งอย่าง
set x to 3อยู่ในล็อก - อัลกอริทึมฉันทามติจะกำหนดว่าคำสั่งใดจะถูกใส่ในล็อกของเซิร์ฟเวอร์ และใส่ในลำดับใด
- หาก state machine หนึ่งนำ
set x to 3ไปใช้เป็นคำสั่งลำดับที่ n ก็ต้องรับประกันว่า state machine อื่นจะไม่ใช้คำสั่งที่ต่างออกไปในตำแหน่งเดียวกัน
- ในตัวอย่าง hash table จะมีคำสั่งอย่าง
- ผลลัพธ์คือ state machine ทั้งหมดจะประมวลผลลำดับคำสั่งเดียวกัน และไปถึงลำดับผลลัพธ์กับลำดับสถานะที่เหมือนกัน
ภาพจำลองเพื่อทำความเข้าใจ Raft
- สามารถทดลองควบคุมภาพจำลอง Raft cluster ที่ทำงานในเบราว์เซอร์ได้โดยตรง
- ด้านซ้ายจะแสดงเซิร์ฟเวอร์ 5 เครื่อง
- ด้านขวาจะแสดงล็อกของแต่ละเซิร์ฟเวอร์
- ผู้ใช้สามารถโต้ตอบและดูการทำงานของ Raft ได้
- RaftScope ยังมีจุดที่ต้องปรับปรุงอีกมาก และยินดีรับ Pull Request
- The Secret Lives of Data เป็นภาพจำลองอีกแบบหนึ่งที่แสดง Raft ในมุมที่ต่างออกไป
- มีลักษณะเป็นการนำทางมากกว่าและโต้ตอบได้น้อยกว่า
- อาจเป็นจุดเริ่มต้นที่นุ่มนวลกว่าสำหรับผู้อ่านที่เพิ่งรู้จักเรื่องนี้
งานวิจัย สเปก และเอกสารการตรวจพิสูจน์
- In Search of an Understandable Consensus Algorithm (Extended Version) คือ “งานวิจัย Raft” ที่อธิบาย Raft อย่างละเอียด
- เขียนโดย Diego Ongaro และ John Ousterhout
- เวอร์ชันที่สั้นกว่านิดหน่อยได้รับรางวัล Best Paper Award ที่ 2014 USENIX Annual Technical Conference
- Ph.D. dissertation ของ Diego Ongaro ขยายเนื้อหาจากงานวิจัยให้ลึกยิ่งขึ้น
- มีอัลกอริทึมการเปลี่ยนสมาชิกของคลัสเตอร์ที่ง่ายกว่า
- รวม สเปกเชิงรูปนัย TLA+ ของ Raft ไว้ด้วย
- สเปกที่อัปเดตขึ้นเล็กน้อยดูได้ที่ raft.tla
- งานวิจัยที่เกี่ยวข้องครอบคลุมการตรวจพิสูจน์เชิงรูปนัยของ Raft, เฟรมเวิร์กสำหรับอิมพลีเมนต์และตรวจพิสูจน์ระบบกระจาย, การสร้างโค้ดจากโมเดลเชิงรูปนัย, และการวิเคราะห์โปรโตคอล
- 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
การบรรยายและสื่อการเรียนรู้
- มีการรวบรวมรายการบรรยายสำหรับผู้เริ่มต้นศึกษา Raft ไว้ด้วย
- การบรรยายใน CS@Illinois Distinguished Lecture Series ของ John Ousterhout, สิงหาคม 2016
- การบรรยายเรื่อง Raft และสเปก TLA+ ใน Dr. TLA+ Series ของ Jin Li, กรกฎาคม 2016
- การบรรยายของ Diego Ongaro ที่ Build Stuff 2015, CoreOS Fest 2015, Sourcegraph meetup, LinkedIn, USENIX ATC 2014, CraftConf 2014, RICON West 2013
- การบรรยายของ Ben Johnson ที่ Strange Loop 2013
- บทเรียน Raft User Study ของ John Ousterhout, มีนาคม 2013
- มหาวิทยาลัยและหลักสูตรการสอนก็ใช้ Raft ในการบรรยายหรือเป็นงานเขียนโปรแกรมเช่นกัน
- รวมหลายหลักสูตรจาก University of Copenhagen, Czech Technical University in Prague, The University of Hong Kong, University of Virginia, UC San Diego, Technical University of Munich, UIUC เป็นต้น
- บางหลักสูตรมี งานเขียนโปรแกรม Raft ด้วย Go, Java, Erlang เป็นต้น
- MIT 6.824 มีบันทึกการบรรยายเกี่ยวกับ Raft และยังแนะนำบทความ Raft สำหรับผู้สอนและนักศึกษาของ Jon Gjengset ด้วย
- สามารถอัปเดตรายวิชาเพิ่มเติมได้ผ่าน Pull Request หรือ issue ในที่เก็บของเว็บไซต์
ช่องทางถามตอบและรายการอิมพลีเมนเทชัน
- สำหรับคำถามเกี่ยวกับ Raft และอิมพลีเมนเทชันต่าง ๆ แนะนำให้ใช้ raft-dev Google group
- อิมพลีเมนเทชันบางตัวมี mailing list ของตนเอง จึงควรตรวจ README ของแต่ละโครงการ
- ยังมีรายการ อิมพลีเมนเทชัน Raft ที่มีซอร์สโค้ดสาธารณะให้ด้วย
- อิมพลีเมนเทชันที่ได้รับความนิยม หรือเพิ่งอัปเดตล่าสุด จะอยู่ด้านบนของตาราง
- ข้อมูลอาจล้าสมัยได้เมื่อเวลาผ่านไป และสามารถอัปเดตผ่าน Pull Request หรือ issue ได้
- ตารางเปรียบเทียบ Stars, ชื่อ, ผู้เขียนหลัก, ภาษา, ไลเซนส์, และการรองรับฟีเจอร์ของแต่ละอิมพลีเมนเทชัน
- รายการฟีเจอร์ได้แก่ การเลือกผู้นำและการทำซ้ำล็อก, การคงอยู่ถาวร, การเปลี่ยนสมาชิก, และการบีบอัดล็อก
- ตัวอย่างอิมพลีเมนเทชันด้านบนมีดังนี้
- TiKV: Rust, Apache-2.0, 16,751★, รองรับการเลือกผู้นำและการทำซ้ำล็อก/การคงอยู่ถาวร/การเปลี่ยนสมาชิก/การบีบอัดล็อกครบทั้งหมด
- RethinkDB: C++, Apache-2.0, 27,000★, รองรับฟีเจอร์หลักครบทั้งหมด
- Seastar Raft: C++20, AGPL, 15,624★, รองรับฟีเจอร์หลักครบทั้งหมด
- hashicorp/raft: Go, MPL-2.0, 9,048★, รองรับฟีเจอร์หลักครบทั้งหมด
- hazelcast-raft: Java, Apache-2.0, 6,579★, รองรับฟีเจอร์หลักครบทั้งหมด
- ในรายการยังมีอิมพลีเมนเทชันในหลากหลายภาษา เช่น Rust, Go, Java, C++, C, Erlang, Python, Scala, C#, JavaScript, Haskell, OCaml, Kotlin, Zig, TypeScript, Elixir, F#, Shell เป็นต้น
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
Maelstrom เวิร์กเบนช์สำหรับเรียนรู้ระบบแบบกระจายของผู้สร้าง Jepsen มีทั้งการติดตั้งการตรวจสอบโมเดลแบบเรียบง่ายของ Raft และบทช่วยสอนการติดตั้งอยู่ค่อนข้างครบถ้วน: https://github.com/jepsen-io/maelstrom/
Raft เป็นอัลกอริทึมที่เรียบง่าย แต่ในเปเปอร์ต้นฉบับมีรายละเอียดด้านความถูกต้องจำนวนมากที่มักถูกละไว้ในการติดตั้งแบบของเล่น
หากพิจารณาไปถึงความเสียหายของหน่วยความจำ/ดิสก์บนฮาร์ดแวร์จริง, gray failure, SLA ด้าน latency ที่เข้มงวด, quorum ที่ยืดหยุ่น และ membership ของคลัสเตอร์แบบไดนามิก การติดตั้งสำหรับโปรดักชันก็จะกลายเป็นงานที่ยาวและหนักหน่วง
แค่ดูประวัติ commit ของ etcd และ hashicorp/raft ก็เห็นได้ว่า แม้แต่การติดตั้ง Raft แบบโอเพนซอร์สที่ผ่านการตรวจสอบมากที่สุด ก็ยังพบ bug ด้านความถูกต้องเป็นระยะ ๆ
ทีม TigerBeetle อธิบายอย่างละเอียดถึงความจริงของระบบแบบกระจายในโมเดลระบบที่ฮาร์ดแวร์ไม่สมบูรณ์และไม่ได้ถูก abstraction รวมถึงเหตุผลที่เลือก Viewstamped Replication ซึ่งเก่ากว่า Paxos แต่ดูคล้าย Raft มากกว่า: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...
ไม่แน่ใจว่าจะส่งผลอย่างไรต่อข้อกังวลในการติดตั้ง แต่ตัวเปเปอร์ยอดเยี่ยมมาก จึงอยากแนะนำ
มีวิดีโอบรรยายด้วย แต่ผมคิดว่าบทความอ่านดีกว่าเมื่ออยากเปิดอ้างอิงไปมา: https://www.youtube.com/watch?v=0K6kt39wyH0
แม้ผมจะไม่เคยดู consensus algorithm มาก่อนเลย แต่หลังจากอ่านซ้ำไม่กี่รอบก็พอตามได้ในระดับหนึ่ง: https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
เมื่อไม่นานมานี้ผมลองติดตั้ง leader election และ log replication ของ Raft แม้จะยังไปไม่ถึง snapshot/checkpoint แต่ก็จัดว่าเป็นหนึ่งในโปรเจกต์ที่ยากที่สุดเท่าที่เคยทำมา
เปเปอร์ Raft อ่านง่ายและให้ intuition ได้ดี
ต่อให้ไม่ได้ติดตั้งเอง ก็มีโอกาสสูงอยู่แล้วว่าคุณกำลังใช้ซอฟต์แวร์ที่อิง Raft เช่น etcd, Consul, CockroachDB, TiDB
ผมรวบรวมแหล่งข้อมูลที่มีประโยชน์ระหว่างการติดตั้งไว้ที่นี่: https://github.com/eatonphil/goraft#references
รวมทั้งวิทยานิพนธ์ปริญญาเอกของ Diego Ongaro และสเปก TLA+ ด้วย
มีคนบอกว่า “แค่ Figure 2 ในเปเปอร์ Raft ก็พอแล้ว” แต่เมื่อเทียบกับสเปก TLA+ มันคลุมเครือกว่ามาก ผมจึงคิดว่าไม่จริง
แนะนำให้ลองเชื่อมกับ Raft test ของคอร์สระบบแบบกระจายของ MIT: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
อย่างน้อยส่วน leader election และ log replication ก็ดูเหมือนจะทำได้ด้วยการ refactor เล็กน้อย
โดยเฉพาะสำหรับคนที่เพิ่งเริ่มสัมผัส distributed algorithms ถือว่าแนะนำได้จริง ๆ
คุณภาพการติดตั้งคงไม่ได้ยอดเยี่ยมมาก แต่ลงไว้เผื่อคนที่สนใจ: https://github.com/skowalak/fastapi-raft/
ยังมีรายละเอียดเฉพาะที่จำเป็นต่อการติดตั้งอีกหลายอย่างอยู่ในเปเปอร์
ถ้าคุณสนใจ consensus algorithms หนังสือชื่อ Reasoning about Knowledge ที่เคยใช้ในวิชาทฤษฎีระบบแบบกระจายก็น่าดู: https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...
ต้องลงทุนเรียน modal logic อยู่บ้าง แต่เมื่อผ่านส่วนนั้นไปแล้ว การพิสูจน์ว่าทำไม Raft หรือ Paxos จึงทำงานได้จะกลายเป็นเรื่อง intuitive และเรียบง่ายมาก
เป็นวิธีผลักความซับซ้อนของการพิสูจน์เข้าไปไว้ในโครงสร้างตรรกะที่ใช้พิสูจน์ ซึ่งเปลี่ยนมุมมองของผมต่อ consensus ไปเลย
“Raft Consensus Algorithm Failure”, Théodore Géricault, 1819: https://classicprogrammerpaintings.com/post/6141087496359280...
ถ้าไม่รู้ว่าวิชวลไลเซชันกำลังแสดงอะไรอยู่ ให้ลองคลิกโหนดหนึ่งเพื่อทำให้มันเกิดข้อขัดข้องได้
โดยเฉพาะควรลองกับโหนดที่เป็น ลีดเดอร์ ปัจจุบัน ซึ่งเป็นโหนดที่ส่งและรับแพ็กเก็ตทั้งหมด
กดไอคอนหยุดชั่วคราวเล็ก ๆ ข้างสไลเดอร์แรกเพื่อเปลี่ยนกลับเป็นนาฬิกา แล้วซิมูเลชันจะเริ่มทำงานต่อ
ยังไม่รู้ว่าสเปรดชีตด้านขวาคืออะไร และมันมักจะว่างเปล่า เลยดูเหมือนพังอยู่
องค์ประกอบที่คลิกได้เท่าที่เจอจนถึงตอนนี้คือสไลเดอร์สองอัน ไอคอนนาฬิกา/หยุดชั่วคราว และเซิร์ฟเวอร์แต่ละตัว
ถ้าคลิกลีดเดอร์แล้วเลือก
requestจะจำลองการส่งคำสั่งได้ถ้าทำให้ replica ตัวหนึ่งออฟไลน์ จะเห็นมันตามหลังไปสักพัก แล้วตามทันเมื่อกลับมาออนไลน์อีกครั้ง
เมื่อหลายปีก่อน ผมอยู่ในสภาพแวดล้อมที่ต้องมี ระบบคล้าย Chubby ที่แข็งแกร่งภายใต้โหลดหนักอย่างจริงจังเสมอ และตอนนั้นถ้าความล้มเหลวเป็นสิ่งที่ยอมรับไม่ได้ เราจะใช้ ZooKeeper
แต่ตอนนี้เท่าที่รู้ ผู้คนเอางานที่หนักมากไปวางบนตัวเลือกที่ใช้ Raft อย่าง etcd และ Consul กันมาหลายปีแล้ว
เลยสงสัยว่าหนึ่งในตัวเลือกพวกนี้กลายเป็นตัวเลือกมาตรฐานไปแล้วหรือยัง
ความชัดเจนเชิงแนวคิดและความสง่างามของ Raft ดูเหมือนน่าจะนำไปสู่ประสิทธิภาพและความน่าเชื่อถือ แต่ความรู้สึกต่อวงการนี้ของผมเก่าไปแล้ว
สงสัยว่าในปี 2023 คนที่ไม่ได้ผูกกับ Google หรือ GCP ใช้อะไรเป็นแนวปฏิบัติมาตรฐานโดยปริยายสำหรับระบบที่มีความสำคัญสูง
เหมือนเคยมี implementation ของ Raft ภาษา Rust ระดับ production ที่ฝั่ง TikV ทำไว้ และเซิร์ฟเวอร์ล็อกที่แข็งแกร่งประสิทธิภาพสูงก็ดูเป็นพื้นที่ที่ค่อนข้างเหมาะกับ Rust เลยสงสัยด้วยว่ามีการใช้งานจริงอยู่ไหม
ถ้านี่คือคำตอบของ “Raft คืออะไร?” อ่านแล้วก็ยังไม่รู้อยู่ดี
“Raft เป็นอัลกอริทึมฉันทามติที่ออกแบบมาให้เข้าใจง่าย ในด้าน fault tolerance และประสิทธิภาพ มันเทียบเท่ากับ Paxos ความแตกต่างคือมันถูกแยกย่อยเป็นปัญหาย่อยที่ค่อนข้างเป็นอิสระจากกัน และจัดการส่วนสำคัญที่จำเป็นสำหรับระบบใช้งานจริงได้อย่างเรียบร้อย เราหวังว่า Raft จะทำให้ฉันทามติเข้าถึงผู้อ่านได้กว้างขึ้น และผู้อ่านกลุ่มนั้นจะสามารถสร้างระบบคุณภาพสูงที่อิงฉันทามติได้หลากหลายกว่าที่เป็นอยู่ในตอนนี้”
เรื่องแบบนี้ไม่ใช่ปัญหาเฉพาะของพวกเขา แต่ผมรู้สึกเสียดายที่ไม่ใช้เวลาเพิ่มในการอธิบายงานของตัวเองให้ดีพอ
เพราะมันคัดกรองผู้อ่านที่ไม่รู้ความหมายออกไปโดยอัตโนมัติ
สำหรับคนที่กำลังสร้าง distributed systems และเปรียบเทียบ อัลกอริทึมฉันทามติ หลายแบบ มันเป็นคำอธิบายที่เรียบง่ายและชัดเจน และถ้าไม่ใช่คนกลุ่มนั้น ก็มีโอกาสสูงว่าอัลกอริทึมนี้จะไม่เกี่ยวข้องอยู่แล้ว
โดยทั่วไป อัลกอริทึมฉันทามติพยายามแก้ปัญหาที่ว่ามี replica ของ data store กระจายอยู่บนอุปกรณ์ทางกายภาพหลายเครื่อง แล้วเมื่ออุปกรณ์หรือการเชื่อมต่อบางส่วนล้มเหลวในรูปแบบใดรูปแบบหนึ่ง ควรทำอย่างไร
ที่เรียกว่า “ฉันทามติ” เพราะในสถานการณ์ขัดข้อง เครื่องต่าง ๆ ต้องตกลงกันว่าจะตัดสินใจอย่างไรกับชิ้นข้อมูล
ตัวอย่างเช่น ถ้าเซิร์ฟเวอร์สามตัวกำลัง replicate ฐานข้อมูล SQL เดียวกัน และอยู่ในรูปแบบ
(A) - (B) - (C)แล้วการเชื่อมต่อเครือข่ายระหว่าง C กับอีกสองตัวถูกตัด A กับ B จะรู้เรื่องนี้และสามารถเลื่อน B ขึ้นเป็นโหนดหลักได้แต่ C ไม่รู้ว่าเกิดอะไรขึ้น และอาจยังรับการเขียนบางส่วนต่อไป
เมื่อการเชื่อมต่อกลับมา A, B, C ต้องตัดสินใจว่าจะทำอย่างไรต่อ
เพราะ B กับ C ได้รับชุดการเขียนที่แตกต่างกันอย่างเป็นอิสระ เซิร์ฟเวอร์จึงต้องตกลงกันว่าจะจัดการข้อมูลอย่างไร
นี่คือปัญหาที่ Raft, Paxos และอื่น ๆ พยายามแก้ด้วยวิธีที่สอดคล้องกันและมีประสิทธิภาพดี
บางแนวคิดใหญ่เกินกว่าจะอธิบายให้คนที่ไม่มีพื้นฐานเลยเข้าใจได้ในย่อหน้าเดียว
ถึงอย่างนั้น บทความที่ลิงก์ไว้ก็เป็นสื่อเริ่มต้นที่ยอดเยี่ยมหากอ่านต่อไป
ในฐานะนักวิจัยโปรโตคอลฉันทามติ ผมคิดว่าจาก งานวิจัยบล็อกเชน ในช่วง 10 ปีที่ผ่านมา ฉันทามติกลายเป็นเรื่องที่เข้าใจง่ายขึ้นมาก
เมื่อเทียบกันแล้ว Raft โดยเฉพาะเมื่อรวมส่วนที่ละเอียดอ่อนเข้าไปด้วย อ่านและ implement เหมือนภาษากรีกเลย
ถ้าเป็นคนที่เพิ่งเริ่มเรียนโปรโตคอลฉันทามติในตอนนี้ ผมน่าจะให้เริ่มจาก Bitcoin แล้วไปต่อที่ Paxos, Tendermint, Simplex และข้าม Raft ไปเลย
Simplex เป็นเปเปอร์ที่ผมเขียนเอง เป็นเวอร์ชันที่ทำให้ PBFT ง่ายลง
Raft ดูค่อนข้างเรียบง่ายกว่า
เลยสงสัยว่าบล็อกเชนให้อะไรที่ดูแลรักษาง่ายกว่าและทำผิดพลาดได้ยากกว่า “เลือก leader แล้ว replicate log”
ชอบเว็บนี้
หน้านี้มีประโยชน์จริง ๆ ตอนเรียนและ implement Raft ในวิชา distributed systems
ตัวเปเปอร์เองก็อ่านค่อนข้างง่ายด้วย
ขอบคุณที่ทำให้ Raft ชัดเจนได้ขนาดนี้
สงสัยว่ามีอัลกอริทึมฉันทามติที่การเปลี่ยนแปลงไม่จำเป็นต้องผ่าน leader เสมอไปหรือไม่
ในระบบกระจายจำนวนมาก ก็อยากให้การประมวลผลอินพุตกระจายตัวด้วย
หนึ่งในนั้นคือ Chord: https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)
Chord คือ P2P ring ที่โหนดแบ่งกันเก็บค่าด้วย consistent hashing
เครือข่ายใช้สิ่งที่เรียกว่า “finger table” ซึ่งโดยพื้นฐานแล้วคือการเก็บข้อมูลการทำ replication ในรูปแบบตาราง
ข้อมูลในตารางนี้อาจผิดหรือล้าสมัยได้ และ peer ที่ถูกเข้าถึงอาจบอกให้ไปหา peer อื่น ซึ่งโดยปกติคือโหนดถัดไปหรือโหนดลำดับต่อ ๆ ไป แล้วทำต่อไปจนกว่าจะพบค่าหรือพบว่าไม่มีค่า
เหตุผลที่อัลกอริทึมนี้ใช้ได้แม้ไม่มี “leader” คือมันทำงานได้แม้จะใช้วิธีไปที่โหนดหนึ่งแล้วไล่ดูทุกโหนดแบบเชิงเส้น
finger table ที่ช่วยให้ query เร็วขึ้นไม่ใช่สิ่งจำเป็น
ระบบเหล่านี้มักมี “leader” ต่อ transaction แต่ในการทำงานปกติบทบาทนั้นจะไม่ถูกแย่งชิง
เป็นวิธีที่ transaction coordinator ประกาศตัวเอง ดังนั้นการเลือกตั้งจะเกิดขึ้นก็ต่อเมื่อ coordinator ล้มเหลวด้วยเหตุผลบางอย่างเท่านั้น
สำหรับข้อมูลหรือคีย์บางรายการ อาจมี leader หลายตัวพร้อมกันได้
Cassandra กำลังพัฒนา Accord ซึ่งเป็น leaderless protocol ในกลุ่มนี้อยู่ในขณะนี้
จริง ๆ แล้ว Cassandra ใช้ leaderless protocol กับ LWT อยู่แล้ว
เป็นเวอร์ชันดัดแปลงที่ปรับให้เหมาะสมของ Paxos แบบฉันทามติเดี่ยวแบบคลาสสิก แต่ถ้ามี transaction ที่แข่งขันกันบนคีย์เดียวกันถูกประกาศพร้อมกัน overhead จะค่อนข้างมาก
หาก transaction กระจายอยู่ข้ามหัวข้อที่เป็นอิสระต่อกัน ก็สามารถ shard leader เพื่อกระจายโหลดได้
คือการกำหนดช่วงของ key space ให้กับ leader ต่าง ๆ และปรับการเลือกตั้งเพื่อให้แต่ละโหนดมีส่วนแบ่ง leadership ที่เหมาะสม
หากจะไปแบบไม่มี leader ก็สามารถจัดให้แต่ละ write แทบจะเหมือนการเลือกตั้งหนึ่งครั้งได้
หากเป็น tentative transaction หรือ transaction ขนาดใหญ่ ก็ broadcast คำขอ transaction ไปยังทุกโหนด และเมื่อได้ quorum การยอมรับก็ถือว่าชนะและ commit
แต่ถ้าหลายโหนดพยายามทำ transaction เกือบพร้อมกัน การบรรลุฉันทามติอาจใช้เวลามาก
หากมีโหนดจำนวนมากและทั้งหมดมี transaction ที่รออยู่ในหัวข้อเดียวกัน การเลือก leader แล้วส่ง transaction ทั้งหมดผ่าน leader จะเร็วกว่าการสร้างฉันทามติแยกสำหรับทุก transaction มาก
อย่างไรก็ตาม หากเป้าหมายคือกระจายเพื่อเพิ่ม throughput วิธีที่ต้องใช้เพียง leader เดียวอาจมีประสิทธิภาพกว่าการต้องมี quorum ตามที่ Paxos กำหนด
เป็นเพียงการคาดเดา
Paxos เองก็มีประสิทธิภาพมากขึ้นถ้าการเรียกไปที่เดิมทุกครั้ง
เพราะหลีกเลี่ยง contention และการโหวตซ้ำได้
โดยพื้นฐานแล้วแต่ละ shard จะมีฉันทามติ Paxos ของตัวเอง