การแก้ไขข้อความแบบทำงานร่วมกัน: ทำได้โดยไม่ต้องใช้ CRDT หรือ OT

 (mattweidner.com)
4 คะแนน โดย GN⁺ 2025-05-23 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • แนะนำ แนวทางใหม่ในการแก้ปัญหาการแก้ไขข้อความแบบทำงานร่วมกัน ซึ่งทำได้โดยไม่ต้องใช้อัลกอริทึมที่ซับซ้อน
  • หลีกเลี่ยง ความซับซ้อนและข้อจำกัดของแนวทาง CRDT และ OT แบบเดิม โดยใช้วิธีแทรกข้อมูลแบบอิง ID ที่เรียบง่าย
  • วิธีนี้มีความยืดหยุ่นสูง เพราะ เซิร์ฟเวอร์จะประมวลผลจากการที่ได้รับคำสั่งโดยตรงว่า 'จะใส่อะไรไว้ที่ไหน'
  • ใช้กลยุทธ์ server reconciliation เพื่อรองรับ optimistic local update และแก้ปัญหาการซิงก์สถานะ
  • แนวทางนี้ทั้งขยายต่อได้และเข้าใจง่าย จึงเป็น ทางเลือกที่นำไปลงมือใช้ได้จริง สำหรับการพัฒนาแอปทำงานร่วมกันแบบเดิม

Collaborative Text Editing without CRDTs or OT

การตั้งปัญหา

  • การแก้ไขข้อความแบบทำงานร่วมกันเป็นฟีเจอร์ที่ยากมาก โดยเฉพาะเมื่อมีการแก้ไขพร้อมกันจะเกิด ปัญหาดัชนีข้อความเพี้ยน (index rebasing)
  • แนวทางเดิมอย่าง CRDT (Conflict-free Replicated Data Type) และ OT (Operational Transformation) ต่างก็อิงอยู่บนโมเดลทางคณิตศาสตร์ที่ซับซ้อน
    • CRDT: ติดตามแต่ละตัวอักษรด้วย ID และจัดเรียงด้วยโครงสร้างแบบต้นไม้
    • OT: ปรับดัชนีแบบไดนามิกเพื่อสะท้อนอินพุตจากผู้ใช้อื่น
  • ทั้งสองแนวทางพึ่งพาไลบรารีสูง และ ปรับแต่งให้เข้ากับความต้องการของนักพัฒนาได้ยาก

แนวทางใหม่

แนวคิดหลัก

  • กำหนดให้แต่ละตัวอักษรมี ID เฉพาะตัว (UUID) และให้ไคลเอนต์ส่ง คำสั่งว่า “ให้แทรกตัวอักษรใดหลัง ID ไหน” ไปยังเซิร์ฟเวอร์
  • ตัวอย่าง: "insert ' the' after f1bdb70a" → f1bdb70a คือ ID ของตัวอักษรเป้าหมายสำหรับการแทรก
  • เซิร์ฟเวอร์ตีความและ แทรกตามนั้นตรง ๆ จึงหลีกเลี่ยงความขัดแย้งได้

การจัดการการลบ

  • แม้ลบตัวอักษรแล้ว ID นั้นก็ยังคงอยู่ในรายการภายใน โดยจัดการด้วย แฟล็ก isDeleted
  • ถึงจะไม่แสดงในข้อความที่ผู้ใช้เห็น แต่ยังคงอ้างอิงได้ จึงรองรับการจัดการในภายหลัง

การทำงานฝั่งไคลเอนต์และ optimistic update

  • ผู้ใช้ต้องเห็นผลทันทีหลังพิมพ์ จึงต้อง อัปเดตในเครื่องก่อนรอคำตอบจากเซิร์ฟเวอร์ (optimistic update)
  • ใช้กลยุทธ์ server reconciliation โดย:
    1. ย้อนกลับการทำงานในเครื่องที่ยังไม่ยืนยันทั้งหมด
    2. นำการทำงานจากเซิร์ฟเวอร์มาปรับใช้
    3. จากนั้นค่อยนำการทำงานในเครื่องกลับมาปรับใช้อีกครั้งเพื่อให้ได้ สถานะที่ซิงก์กันสมบูรณ์

ความต่างจากแนวทางเดิม

  • CRDT มีอัลกอริทึมสำหรับ จัดเรียง ID อัตโนมัติ อยู่ภายใน แต่แนวทางนี้ส่งให้เซิร์ฟเวอร์เฉพาะ ตำแหน่งแทรกที่ระบุชัดเจน
  • ผลลัพธ์คือเรียบง่ายกว่าและ ได้พฤติกรรมการทำงานที่ชัดเจนกว่า

การจัดการการแทรกพร้อมกัน

  • ตัวอย่าง: ในข้อความ “My name is” มีผู้ใช้สองคนแทรก “ Charlie” และ “ Dave” พร้อมกันที่ตำแหน่งเดียวกัน
    • ผลลัพธ์จะเป็น “My name is Dave Charlie” ตามลำดับที่เซิร์ฟเวอร์ได้รับ
  • สิ่งนี้ถือเป็นพฤติกรรมที่เป็นธรรมชาติ และไม่มีอาการ ตัวอักษรสลับแทรกปนกันเป็นรายตัว (interleaving) แบบที่พบใน CRDT บางแนวทาง

รองรับการทำงานที่ยืดหยุ่น

  • นอกจาก insert/delete พื้นฐานแล้ว ยังรองรับการทำงานได้อีกหลากหลาย เช่น:
    • insert-before
    • การแทรกแบบมีเงื่อนไข (“เพิ่ม u เฉพาะเมื่อมี color อยู่”)
    • การปรับตำแหน่งตอน drag & drop เป็นต้น
  • ความยืดหยุ่นนี้ทำได้เพราะ ไม่ถูกผูกมัดด้วยคุณสมบัติทางคณิตศาสตร์ที่ตายตัว

รองรับ rich text

  • สามารถกำหนดช่วงด้วย ID เพื่อใช้ใส่รูปแบบได้ เช่น “ทำตัวหนาตั้งแต่ ID X ถึง ID Y”
  • เมื่อเชื่อมกับเอดิเตอร์อย่าง ProseMirror ก็ แก้ความขัดแย้งได้ด้วยวิธีที่เรียบง่าย
  • จึงเพิ่มความสามารถด้าน rich text ได้โดยยังคงโครงสร้างหลักเดิมไว้

เวอร์ชันแบบกระจายศูนย์ (Decentralized)

  • แม้ไม่มีเซิร์ฟเวอร์กลาง ก็ยังใช้วิธีเดียวกันได้ หากจัดลำดับการทำงานด้วย Lamport timestamp
  • ในกรณีนี้จะให้ผลลัพธ์คล้ายกับ CRDT อย่าง RGA, Peritext, Fugue
  • จึงทำให้ได้ ความสอดคล้องระดับ CRDT โดยไม่ต้องใช้โครงสร้างต้นไม้หรือบทพิสูจน์ทางคณิตศาสตร์

ไลบรารีเสริม: Articulated

  • เป็นไลบรารีสำหรับจัดการโครงสร้าง Array<{ id, isDeleted }> ได้อย่างมีประสิทธิภาพ
  • ใช้โครงสร้าง { bunchId, counter } แทน UUID เพื่อเพิ่มประสิทธิภาพด้านหน่วยความจำ
  • ใช้โครงสร้างแบบ B+Tree เพื่อ ค้นหาและแทรก ID ได้อย่างรวดเร็ว
  • เป็นโครงสร้างข้อมูลแบบ persistent จึงเข้ากันได้ดีกับ server reconciliation

บทสรุป

  • แนวทางนี้ เข้าใจง่ายกว่าและลงมือสร้างเองได้จริง เมื่อเทียบกับ CRDT/OT
  • เพราะสามารถใส่ฟีเจอร์แก้ไขที่หลากหลาย รวมถึงสิทธิ์ ข้อจำกัด และรูปแบบต่าง ๆ ได้อย่างอิสระ จึง เหมาะกับการสร้าง collaborative editor ที่ใช้งานได้จริง
  • ไลบรารี Articulated ถูกนำเสนอเป็นเครื่องมือที่ช่วยให้แนวทางนี้นำไปใช้ในทางปฏิบัติได้ง่ายขึ้น

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-05-23
ความเห็นจาก Hacker News

  • อัลกอริทึมนี้ดูเจ๋งทีเดียว อธิบายวิธีติด ID ที่ไม่ซ้ำกันทั่วโลกให้กับอักขระแต่ละตัว (เช่น UUID) เพื่อให้อ้างอิงได้อย่างสม่ำเสมอเสมอมา โดยไคลเอนต์จะบอกเซิร์ฟเวอร์ว่าให้แทรกอักขระหลัง ID ใด เซิร์ฟเวอร์ก็ทำการแทรก ณ ตำแหน่งนั้น ส่วนการลบจะเป็นเพียงการซ่อนออกจากหน้าจอ แต่ภายในยังคงเก็บไว้เพื่อใช้อ้างอิงตำแหน่งต่อไป และจินตนาการได้ว่าวิธีนี้อาจนำไปใช้กับด้านอื่นนอกจากการแก้ไขข้อความ เช่น การซิงก์โลกในเกม

    • โดยแก่นแล้วมันดูเหมือน CRDT แบบลดทอนความซับซ้อน โดยวิธีตัดสินกรณีเสมอและการใช้เซิร์ฟเวอร์กลางคล้ายกับโครงสร้างในยุค Google Wave
    • มีการตั้งคำถามว่าสิ่งที่อธิบายมานี่ไม่ใช่ CRDT อยู่แล้วหรือ
    • บางคนมองว่าจริง ๆ ก็ไม่ได้ใหม่มาก เพราะการใช้กระบวนการกลางเพื่อทำให้ระบบกระจายกลายเป็นลำดับเชิงอนุกรมเป็นวิธีดั้งเดิมอยู่แล้ว และประเด็นอย่าง network partition (CAP ฯลฯ) หรือ single point of failure ก็ยังคงมีอยู่ พร้อมเสริมว่าอยากรู้ว่าบทความพูดถึงประสิทธิภาพไว้หรือไม่
    • มีมุกแซวว่าขอให้โชคดีกับการทำงานแบบเลือกทั้งหมด/ตัด/วางจำนวนมากอย่าง ctrl+a, ctrl+x, ctrl+v

  • มีมุมมองว่า จุดที่ต่างจาก CRDT คือเซิร์ฟเวอร์กลางทำหน้าที่ซิงก์อย่างการจัดลำดับ จึงไม่จำเป็นต้องกำหนดลำดับไว้ล่วงหน้าในโครงสร้างข้อมูลจริง และเพราะมีเพียงการสื่อสารระหว่างไคลเอนต์กับเซิร์ฟเวอร์ เซิร์ฟเวอร์จึงสามารถประมวลผลการทำงานโลคัลของไคลเอนต์ทั้งหมดก่อนแล้วค่อยส่งอัปเดตจากฝั่งระยะไกลกลับไปได้

  • มีความเห็นว่าน่าแปลกที่ไม่มีการพูดถึงโครงสร้างข้อมูลอื่นอย่าง dict/map หรืออาร์เรย์ของชนิดข้อมูลตามอำเภอใจ ทั้งที่ในแอปจริง ความต้องการด้านข้อมูลแบบร่วมมือกันมักมีมากกว่าการแก้ไขข้อความล้วน ๆ ยังมีตัวอย่างที่น่าสนใจอย่างการตรวจสอบข้อมูล การโหลดบางส่วน หรือการดำเนินการระดับสูงกว่า และมองว่าสาเหตุที่ใน Yjs เป็นต้น ไม่มีความสามารถเหล่านี้ ไม่ได้เป็นเพราะ CRDT เองเท่าไร แต่เป็นเพราะฟีเจอร์พวกนี้เดิมทีก็ทำได้ยากอยู่แล้ว

    • เห็นด้วยอย่างมากกับประเด็นเรื่องโครงสร้างข้อมูลหลายแบบ โดยเฉพาะเวลาสร้างอาร์เรย์ของอ็อบเจ็กต์แบบ "อะตอมิก" ถ้าไม่อนุญาตให้เปลี่ยนพร็อพเพอร์ตีของอ็อบเจ็กต์ ก็เพียงแค่เปลี่ยนชนิดข้อมูลแทนสตริงเท่านั้น ส่วนการแก้ไขภายในอ็อบเจ็กต์ก็แค่เป็นปัญหาเรื่องการเดิน/เก็บต้นไม้ข้อมูลที่ซับซ้อนขึ้นเล็กน้อย อีกทั้งยังคาดหวังว่าฝั่งผู้ใช้ helper library จะสามารถต่อ logic ของ 'semantic model' ของตนเองเข้าไปแบบ hook เพื่อป้องกันสถานะที่ไม่ถูกต้องได้ (เช่น todo หนึ่งรายการมี isDone: true พร้อมกับ state: inProgress) ซึ่งอยู่ในบริบทคล้ายกับ rich text formatting ที่พูดถึงในบทความที่ลิงก์ไว้

    • CRDT จะรวมข้อมูลโดยเลือกฝั่งหนึ่งอย่างสม่ำเสมอเมื่อเกิดความขัดแย้ง แต่ปัญหาคือผลลัพธ์อาจทำให้ข้อมูลสูญหายหรือได้ข้อมูลที่ไม่ถูกต้อง ลองนึกถึงการแก้ git merge conflict โดยบังคับเลือกแค่ฝั่งเดียว ซึ่งส่วนใหญ่มักนำไปสู่ผลลัพธ์ผิดหรือเกิด compile error มีข้อสังเกตว่าการแก้อัตโนมัติอย่างเดียวอาจรักษาความเป็นต้นฉบับและความหมายของข้อมูลไว้ไม่ได้ดีพอ และคิดว่านี่อาจเป็นเหตุผลที่ CRDT ยังไม่แพร่หลายมากนัก

  • มีคนบอกว่าอ่านบทความอธิบายแนวทางนี้แล้วสนุก และตัวเองก็เคยใช้วิธีเดียวกันมานานแล้ว พร้อมแปลกใจที่แทบไม่ถูกพูดถึงในแวดวงวิชาการ โดยบอกว่าตนเองเคยทำสิ่งนี้เป็น CRDT ในสภาพแวดล้อมแบบกระจายศูนย์ เพื่อรักษาคุณสมบัติอย่างการรวมกันได้ ความไม่เปลี่ยนแปลง และการสลับลำดับได้

    • หากพัฒนาขึ้นมาเป็นทางเลือกแทน CRDT ก็อยากรู้ว่าประโยชน์ที่ได้จริงคืออะไร

  • มีการลองสรุปสารของบทความว่า CRDT/OT ที่ซับซ้อนนั้นจำเป็นจริง ๆ ก็ต่อเมื่อไม่มีเซิร์ฟเวอร์กลางเท่านั้นหรือไม่

    • มีความเห็นว่าแม้ไม่มีเซิร์ฟเวอร์กลาง หากมีวิธีตกลงและบังคับใช้ลำดับรวมของการดำเนินการในระบบกระจาย ก็สามารถหลีกเลี่ยงความซับซ้อนของ CRDT/OT ได้ พร้อมแนะนำบทความที่ลิงก์ไว้ แน่นอนว่านี่ก็ยังเป็น CRDT รูปแบบหนึ่งอยู่ดี (ในความหมายที่กว้างขึ้น) แต่การทำ undo/replay ก็ไม่ง่ายนัก และเมื่อรู้สึกว่าโครงสร้าง CRDT/OT แบบดั้งเดิมซับซ้อนเกินไป ก็อาจเป็นอีกทางเลือกที่ควรพิจารณา

    • มีการกล่าวว่า OT (Operational Transformation) ต้องใช้เซิร์ฟเวอร์กลาง

  • โดยเนื้อแท้แล้วก็ยังจัดเป็น CRDT เพียงแต่เซิร์ฟเวอร์กลางเป็นผู้กำหนดลำดับของการดำเนินการที่นำไปใช้กับเอกสาร ขณะที่ Google Docs และ Zoho Writer ก็ใช้แนวทาง OT + เซิร์ฟเวอร์กลางเช่นกัน และยอมรับว่าแนวทางที่เสนอมีสไตล์แบบ CRDT แต่ในทางปฏิบัติอาจเหมาะกับบริการที่มีเซิร์ฟเวอร์กลางมากกว่า

  • มีความเห็นว่าความแตกต่างหลักจาก CRDT อย่าง Automerge อยู่ที่วิธีการประสานงานโดยเซิร์ฟเวอร์ Automerge จะจัดเรียงการแทรกที่เกิดพร้อมกันตามลำดับที่นิยามจาก sequence number และ agent ID แต่แนวทางนี้ให้เซิร์ฟเวอร์ประมวลผลตามลำดับที่มาถึง โดยอ้างคำอธิบายในบทความว่า “ไม่ต้องใช้อัลกอริทึม fancy หลายอย่าง ก็เลยง่ายขึ้น” หลายบริการก็คงใช้เซิร์ฟเวอร์กลางอยู่แล้ว วิธีนี้จึงดูใช้ได้จริง แต่เพราะเมื่อมีการประสานจากเซิร์ฟเวอร์อาจต้อง undo/redo การแก้ไขโลคัล จึงยังไม่แน่ใจว่ามันง่ายกว่ามากเพียงใดในทางปฏิบัติ

    • มีคอมเมนต์ว่า “rewind/replay” เองก็ฟังดูเป็นแนวทางที่ fancy เหมือนกัน และ Persistent B+Tree ก็ไม่ได้เรียบง่ายขนาดนั้น

    • มีคำอธิบายว่า Automerge เองสุดท้ายก็สามารถสร้างลำดับรวมได้ภายใน แต่ในทางปฏิบัติยังจัดการการแก้ไขข้อความด้วย CRDT แบบดั้งเดิม (เช่น RGA) เพราะการทำ undo/replay ไม่ใช่เรื่องง่าย

  • ให้ความรู้สึกเหมือน CRDT ที่ยังไม่ถูก optimize มีมุกว่าคล้ายตั้งค่า max set size=1 แล้วใช้งานแบบดิบ ๆ

    • แต่อีกความเห็นกลับมองว่าการตัดกระบวนการซับซ้อนออกแบบนี้น่าสนใจ เพราะใกล้กับพฤติกรรมที่เกิดขึ้นจริง จึงดูเรียบง่ายและน่าดึงดูด แม้จะยังไม่ optimize ก็ตาม

  • หากใช้การทำ server reconciliation ก็อาจเสี่ยงทำให้ปัญหาการ merge ฝั่งไคลเอนต์ยากขึ้น มีคำถามว่าจะรักษา UX ของเอดิเตอร์ให้ลื่นไหลได้อย่างไรเมื่ออัปเดตจากเซิร์ฟเวอร์ทยอยเข้ามา เช่น หากคำขอแทรกล้มเหลวจะ retry หรือไม่ แล้วถ้าระหว่างนั้นมีอัปเดตอื่นเข้ามาจะทำอย่างไร แนวทางที่เสนอคือย้อนประวัติการแก้ไขแล้วค่อยนำกลับมาใช้ใหม่ หรือไม่ก็รอให้คิวถูกล้างก่อน จากมุมมองฝั่งฟรอนต์เอนด์ ดูเหมือนจะมี UI/UX edge case ที่ไม่ได้ระบุไว้อีกมาก และด้วยเหตุนี้ CRDT อาจกลับกลายเป็นทางเลือกที่ง่ายกว่า โดยเฉพาะในสภาพแวดล้อมที่เครือข่ายไม่เสถียร (เช่น รถไฟใต้ดิน) ก็ชวนสงสัยว่าประสบการณ์ผู้ใช้จะเป็นอย่างไร

    • มีการอธิบายว่า ProseMirror และ CodeMirror รุ่นใหม่จะจัดการการเปลี่ยนแปลงเอกสารเป็นหน่วย step และอัปเดตข้อมูลตำแหน่ง (position map) ในแต่ละขั้นเพื่อให้สามารถนำขั้นต่าง ๆ ในบัฟเฟอร์ไปใช้กับเอกสารได้ เป็นการจัดโครงสร้างข้อมูลที่ใช้งานได้จริงดีมากในงานแก้ไขแบบร่วมมือกัน พร้อมแชร์ลิงก์อ้างอิง

  • มีข้อเสนอว่าลองให้ใครสักคนใช้ LLM (เช่นโมเดล 4b เป็นต้น) เพื่อแก้ merge conflict ที่เกินกว่าเคสง่าย ๆ โดยไม่ต้องใช้ CRDT หรือ OT ที่ซับซ้อน อาจประหยัดพลังงานไม่ดีนัก แต่ก็อาจทำงานได้ดีเกินคาด

    • มีคำถามว่าในกรณี conflict แบบตัวอย่าง เช่นกับข้อความ "My name is" ที่มีการแทรก "Charlie" และ "Dave" ต่อท้ายคำว่า "is" พร้อมกันคนละฝั่ง LLM จะ merge ออกมาอย่างไร