ผมเคยคิดผิดไปเอง CRDT คืออนาคต
(josephg.com)เรื่องราวเกี่ยวกับ Conflict-free Replicated Data Types จากผู้พัฒนา Google Wave
→ CRDT : โครงสร้างข้อมูลที่รองรับการแก้ไขพร้อมกันในเครื่องมือทำงานร่วมกันแบบเรียลไทม์
-
Wave ใช้ OT (Operational Transform) เป็นฐาน : เก็บรายการการเปลี่ยนแปลงทั้งหมดตามลำดับเวลา คล้ายกับ git-rebase แบบเรียลไทม์
-
หนึ่งในปัญหาของ OT คือจำเป็นต้องมีเซิร์ฟเวอร์/DB แบบศูนย์กลาง
→ นี่อาจเป็นเหตุผลที่ในเอกสาร Google Docs (ซึ่งใช้ OT เช่นกัน) เวลามีคนเข้าไปใช้งานจำนวนมากจึงขึ้นว่า 'เอกสารนี้มีภาระงานมากเกินไปจนไม่สามารถแก้ไขได้'?
→ สามารถหลบเลี่ยงได้ด้วยการแบ่งเอกสาร หรือใช้ retry loop กับ DB transaction (เท่ากับโยนปัญหา serialization ไปให้ DB จัดการ)
→ แต่ก็ไม่สมบูรณ์แบบ Wave มีหลายคนแก้ไขพร้อมกันและใช้งานได้จริง แต่มีบั๊กเยอะมาก ซับซ้อนเกินไป
- การมาถึงของ CRDT
→ อัลกอริทึมที่ Wave ใช้นั้นถูกคิดค้นขึ้นในปี 1995 มีการวิจัยต่อเนื่องเพื่อทำให้ OT ทำงานได้ดีขึ้น แต่ CRDT มีอนาคตสดใสกว่า
→ CRDT ใช้แนวทางที่ต่างออกไป ทำให้แก้ไขแบบเรียลไทม์ได้โดยไม่ต้องมี DB กลาง
→ ปัญหาที่เคยถูกยกขึ้นมาอย่างความเร็ว/ขนาด/ฟีเจอร์/ความซับซ้อน ต่างก็ได้รับการปรับปรุงแล้ว
-
ความเร็ว : CRDT ยุคใหม่ (Automerge / RGA or y.js / YATA) สามารถค้นหาได้ในระดับ log(n)
-
ขนาด : Columnar encoding ของ Martin ทำให้เก็บข้อมูลได้ที่ราว 1.5~2 เท่าของขนาดเอกสาร
-
ฟีเจอร์ : ในทางทฤษฎีสามารถทำ rewinding และ replaying ได้ แน่นอนว่ายังไม่มีใครทำจริง
-
ความซับซ้อน : ขนาดของ implementation อาจใหญ่กว่า OT อยู่บ้าง แต่ก็ไม่ได้ต่างกันมาก
→ การปรับปรุงข้างต้นจะพร้อมใช้งานใน Automerge ในเร็ว ๆ นี้
- สำหรับการแก้ไขแบบเรียลไทม์ น่าเสียดายแต่ OT และงานที่เกี่ยวข้องอาจไม่จำเป็นอีกต่อไปแล้ว
→ ทุกความสามารถของ OT สามารถใส่ลงใน CRDT ได้ แต่กลับกันทำไม่ได้
→ จุดแข็งของ OT คือเหมาะกับซอฟต์แวร์แบบรวมศูนย์ แต่อัลกอริทึมแบบกระจายก็ทำงานได้ดีแม้ในระบบรวมศูนย์
→ CRDT คุณภาพสูงที่รันบน WASM น่าจะเร็วกว่า implementation ของ OT บน JS
- ตอนนี้ถึงเวลาที่ต้องสร้าง CRDT ที่เบาและเร็วแล้ว
→ ด้านวิชาการนั้นเกือบเสร็จสมบูรณ์แล้ว และตอนนี้เป็นช่วงเวลาที่ต้องการ implementation ที่ยอดเยี่ยม
10 ความคิดเห็น
ผมชื่อ Hong Youngtaek กำลังพัฒนาโปรเจกต์ Yorkie อยู่ครับ
Yorkie ซึ่งเป็นที่เก็บเอกสารสำหรับแอปแก้ไขร่วมกันแบบเรียลไทม์ ก็ถูกสร้างขึ้นบนพื้นฐานของ CRDT เช่นกันครับ
https://github.com/yorkie-team/yorkie
ผมคิดผิดไปเอง CRDT ต่างหากคืออนาคต
ถ้าใช้ OT ก็เหมือนได้ undo/redo มาแบบสบาย ๆ เลย... แต่ CRDT นี่ดูเหมือนจะมีทางเดียวคือต้องพึ่ง snapshot...
ในกรณีของ Automerge ตัวไลบรารีเองก็รองรับ undo/redo มาให้อยู่แล้วครับ คนที่ลงมือทำอาจจะยากหน่อย แต่ในมุมคนที่ใช้ไลบรารีก็แบบนั้นแหละ 555
https://www.notion.so/sihawn/CRDT-1dc1af26d60144c09eadd178e0ae6e0d
ก่อนหน้านี้ผมเคยแปลฉบับเต็มไว้แล้ว แต่ดันลืมเอามาลง ;w; รอบนี้เลยลองอ่านทวนบนฐานของ Papago แล้วแก้เฉพาะส่วนที่ฟังดูแปลก ๆ ใครที่อยากดูว่าโดยรวมให้อารมณ์ประมาณไหน ลองเข้าไปดูได้ที่ลิงก์ด้านบนเลย~
จะเอามาลงในช่องคอมเมนต์ก็... ยาวเกินไปหน่อย ;w; เลยขอแปะเป็นลิงก์ Notion ให้แทนนะครับ
คิดดูแล้ว Notion เองก็อาจกำลังใช้ CRDT อยู่เหมือนกันนะ!
สิ่งที่ใช้ OT คือ Google Wave/Google Docs/MS Office365
สิ่งที่ใช้ CRDT คือ Figma/Apple Notes และ Riak/Redis เป็นต้น
ผมคิดผิดไปเอง CRDT คืออนาคต
เทคโนโลยีการทำงานร่วมกันหลายผู้ใช้ของ Figma ทำงานอย่างไร https://th.news.hada.io/topic?id=814
วิดีโอ "CRDTs: The Hard Parts" ของ Martin Kleppmann ผู้พัฒนา Automerge ที่ลิงก์ไว้ในบทความ อธิบายได้ดีมากจริง ๆ
ช่วงต้นอธิบายเปรียบเทียบ OT กับ CRDT ได้ดีมาก ส่วนช่วงหลังจะเป็นเนื้อหาเชิงลึกเกี่ยวกับการ implement CRDT
https://www.youtube.com/watch?v=x7drE24geUw
ไลบรารี CRDT ที่ใช้ตอนสร้างเครื่องมือทำงานร่วมกันด้วย JS
ผมคิดผิดไปเอง CRDT คืออนาคต
สู่ระบบการทำงานร่วมกัน: จากอัลกอริทึม OT ไปสู่ระบบ CRDT
https://deview.kr/2013/detail.nhn?topicSeq=66
ในบรรดางานนำเสนอภายในประเทศ เนื้อหานี้แทบจะเป็นงานเดียวที่พูดถึง CRDT ครับ
คุณฮยอนกอลผู้บรรยายครั้งนี้เป็นผู้สร้าง RGA ที่กล่าวถึงในเนื้อหาครับ
Yorkie ก็ได้พัฒนา data type แบบลิสต์โดยอิงจาก RGA เช่นกัน
https://github.com/yorkie-team/yorkie/issues/2