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

 (mattweidner.com)
4 คะแนน โดย GN⁺ 2025-05-23 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ในแอปทำงานร่วมกันที่อิงเซิร์ฟเวอร์กลาง หากแก้ไขข้อความด้วยดัชนีของอาร์เรย์ ตำแหน่งจะเลื่อนเมื่อมีการแก้ไขพร้อมกัน จึงอัปเดตสถานะบนเซิร์ฟเวอร์ด้วยการติด ID ที่ไม่ซ้ำกันทั่วโลก ให้แต่ละตัวอักษร และใช้วิธี “แทรกหลัง ID ที่ระบุ”
  • CRDT และ OT ที่ใช้ในบริการจริงนั้นทรงพลัง แต่มีความซับซ้อนทั้งอัลกอริทึมลำดับรวมและกฎการแปลงโอเปอเรชัน ทำให้ปรับเปลี่ยนการทำงานภายในให้ตรงกับความต้องการของแอปได้ยาก
  • วิธีที่เสนอคือให้ไคลเอนต์และเซิร์ฟเวอร์เก็บรายการ ID ในรูปแบบ Array<{ id: ID; char?: string; isDeleted: boolean }> และคงตัวอักษรที่ถูกลบไว้แบบ tombstone เพื่อไม่ให้การอ้างอิงตำแหน่งแทรกในภายหลังเสียหาย
  • การอัปเดตภายในเครื่องแบบมองโลกในแง่ดีจัดการด้วย server reconciliation โดยเมื่อได้รับโอเปอเรชันจากระยะไกล จะย้อนโอเปอเรชันภายในเครื่องที่ยังค้างอยู่ จากนั้นจึงนำโอเปอเรชันจากระยะไกลและโอเปอเรชันภายในเครื่องที่ยังไม่รับรองกลับมาใช้ใหม่ตามลำดับ
  • ครอบคลุมทั้งลำดับของการแทรกพร้อมกัน การจัดรูปแบบ rich text เวอร์ชันกระจายศูนย์ และไลบรารี Articulated โดยเซิร์ฟเวอร์สามารถกำหนด โอเปอเรชันที่ยืดหยุ่น เกินกว่าการแทรก·ลบให้สอดคล้องกับความหมายของแต่ละแอปได้

ทำไมการแก้ไขแบบอิงดัชนีจึงพังเมื่อมีการแก้ไขพร้อมกัน

  • ในการแก้ไขข้อความแบบทำงานร่วมกัน ไคลเอนต์จะส่งโอเปอเรชันที่ผู้ใช้พิมพ์ไปยังเซิร์ฟเวอร์ และเซิร์ฟเวอร์ต้องอัปเดต สถานะที่เป็นแหล่งอ้างอิงหลัก ของตัวเอง
  • หากมองข้อความเป็นอาร์เรย์ของตัวอักษรแล้วส่งโอเปอเรชันอย่าง แทรก " the" ที่ index 17 ก่อนถึงเซิร์ฟเวอร์อาจมีการแทรกจากผู้ใช้อื่น ทำให้ดัชนีเดียวกันชี้ไปยังตำแหน่งอื่นได้
    • ตัวอย่างเช่น หาก Alice แทรก " gray" ไว้ด้านหน้า index 17 ของ Bob ก็จะไม่ใช่ตำแหน่งเดิมอีกต่อไป
    • เซิร์ฟเวอร์จึงต้อง rebase โอเปอเรชันของ Bob เป็น index 22
  • ประเด็นสำคัญคือ ไคลเอนต์ควรส่งโอเปอเรชันแบบใดไปยังเซิร์ฟเวอร์ และเซิร์ฟเวอร์ควรตีความอย่างไร จึงจะอัปเดตข้อความได้อย่าง “ถูกต้องอย่างชัดเจน”
  • ปัญหา rebase ดัชนีนี้ไม่ได้เกิดแค่กับแอปทำงานร่วมกันแบบเรียลไทม์อย่าง Google Docs แต่ยังเกิดในเว็บฟอร์มที่แทรกรายการในลิสต์ หรือแม้แต่แอปภายในเครื่องแบบเธรดเดียวที่จัดการคอมเมนต์แบบอินไลน์และประวัติการแก้ไขได้เช่นกัน

จุดที่ CRDT และ OT กลายเป็นภาระในงานจริง

  • แนวทางแก้เดิมแบ่งได้กว้าง ๆ เป็น CRDT และ OT
    • CRDT จะกำหนด ID หรือ “position” ที่ไม่เปลี่ยนให้แต่ละตัวอักษร แล้วจัดเรียง ID ด้วยลำดับรวมทางคณิตศาสตร์ เช่น การท่องต้นไม้แบบพิเศษ
    • OT จะทำการแปลงโอเปอเรชันเองโดยคำนึงถึงการแก้ไขพร้อมกัน โดยในตัวอย่างจะเปลี่ยน แทรกที่ index 17 เป็น แทรกที่ index 22
  • ทั้งสองแนวทางนี้ถูกใช้งานจริงแล้ว
    • Google Docs ใช้ OT
    • ไลบรารี CRDT Yjs ถูกนำไปใช้ในหลายแอป
  • ภาระหลักมาจาก ความซับซ้อนเชิงแนวคิด
    • ลำดับรวมของ CRDT สำหรับแก้ไขข้อความมักเป็นอัลกอริทึมละเอียดอ่อนที่นิยามไว้ในงานวิชาการ
    • อัลกอริทึม OT ต้องทำให้เป็นไปตาม “สมบัติการแปลง” เชิงพีชคณิต จำนวนกรณีเพิ่มขึ้นเป็นกำลังสอง และถ้าไม่มีการพิสูจน์เชิงรูปแบบก็มักเกิดบั๊กได้ง่าย
  • อัลกอริทึมที่ซับซ้อนทำให้การนำไปใช้ซับซ้อนตามไปด้วย และมักต้องใช้ไลบรารีที่ผู้เชี่ยวชาญสร้างไว้เหมือน กล่องดำด้านเครือข่าย
  • เมื่อจำเป็นต้องมีฟีเจอร์ที่ไลบรารีไม่คาดไว้ โครงสร้างแบบก้อนเดียวอาจกลายเป็นข้อจำกัด
    • โหลดเข้าเมมโมรีเฉพาะส่วนที่ต้องใช้ของเอกสารขนาดใหญ่ และเก็บส่วนที่เหลือไว้บนดิสก์
    • บังคับใช้สิทธิ์ระดับย่อยของเอกสารบนเซิร์ฟเวอร์ เช่น สิทธิ์แก้ไขรายย่อหน้าหรือสิทธิ์ใช้ฟอร์แมตบางชนิด
    • แสดงการเปลี่ยนแปลงแบบเสนอแก้ไขสไตล์ Google Docs ในเนื้อหาหรือด้านข้าง
    • เก็บข้อความในรูปแบบที่ซิงก์กับคีย์-แวลูสโตร์อย่าง Replicache ได้ง่าย
    • รองรับโอเปอเรชันนอกเหนือจากแทรก·ลบ เช่น ย้ายข้อความ จัดการต้นไม้เอกสาร แยกหรือรวมย่อหน้า

ID ของตัวอักษรและวิธี “insert after”

  • แนวคิดพื้นฐานคือใช้ ID ที่ไม่ซ้ำกันทั่วโลก ให้กับแต่ละตัวอักษรแทนดัชนีของอาร์เรย์
    • โครงสร้างข้อมูลหลักอยู่ในรูป Array<{ id: ID; char: string }>
    • แทนที่ไคลเอนต์จะส่ง แทรกที่ index 17 ก็ส่งโอเปอเรชันอย่าง แทรก " the" หลัง f1bdb70a
    • เซิร์ฟเวอร์จะหา ID เป้าหมายแล้วใส่ตัวอักษรใหม่ต่อท้ายทันที
  • ไคลเอนต์ต้องระบุ ID ของตัวอักษรใหม่ไปพร้อมกันด้วย
    • เช่น แทรก " the" หลัง f1bdb70a ด้วย ids [...]
    • เมื่อไคลเอนต์สร้าง ID เอง ก็สามารถอ้างอิง ID ใหม่นั้นในโอเปอเรชัน insert after ถัดไปได้ก่อนจะได้รับคำตอบจากเซิร์ฟเวอร์
  • หากลบตัวอักษรออกไปทั้งหมด อาจทำให้สูญเสียตำแหน่งแทรกได้
    • ระหว่างที่ Bob พยายามแทรกหลัง 26085702 หากผู้ใช้อื่นลบตัวอักษร 26085702 ไป เซิร์ฟเวอร์ก็จะไม่รู้ว่าควรแทรกตรงไหน
    • เซิร์ฟเวอร์จึงต้องเก็บ ID ที่ถูกลบไว้ในรายการภายในด้วย
  • รูปแบบสถานะที่ปรับแล้วเป็นดังนี้
Array<{ id: ID; char?: string; isDeleted: boolean }>
  • ข้อความที่ผู้ใช้มองเห็นสามารถสร้างได้โดยนำเฉพาะรายการที่ยังไม่ถูกลบมาต่อกัน
list.filter(elt => !elt.isDeleted).map(elt => elt.char).join('')

การจัดการการแทรกและการลบ

  • เมื่อพิมพ์ตัวอักษร การทำงานของไคลเอนต์และเซิร์ฟเวอร์ค่อนข้างตรงไปตรงมา
    • ไคลเอนต์หา before ซึ่งเป็น ID ของตัวอักษรที่อยู่ก่อนจุดแทรกทันที
    • สร้าง id ที่ไม่ซ้ำกันทั่วโลก เช่น UUID สำหรับตัวอักษรใหม่
    • ส่งโอเปอเรชันไปยังเซิร์ฟเวอร์ให้แทรก char พร้อม id หลัง before
    • เซิร์ฟเวอร์จะหา before รวมทั้งในรายการที่ถูกลบ แล้วแทรก { id, char, isDeleted: false } ต่อจากรายการนั้นทันที
  • การลบตัวอักษรก็จัดการบนฐานของ ID เช่นกัน
    • ไคลเอนต์หา id ของตัวอักษรที่จะลบ
    • ส่งโอเปอเรชันไปยังเซิร์ฟเวอร์ให้ลบรายการของ ID นั้น
    • เซิร์ฟเวอร์หารายการนั้น แล้วถ้ายังไม่ถูกลบก็ตั้งค่า entry.isDeleted = true
  • วิธีนี้แก้ปัญหา ตำแหน่งของโอเปอเรชันแก้ไข ที่ส่งไปยังเซิร์ฟเวอร์ได้โดยตรง โดยไม่ต้องเดินตามงานวิจัย CRDT หรือ OT
  • การใช้เป็นอาร์เรย์ธรรมดาอาจไม่มีประสิทธิภาพ เพราะต้องเก็บ UUID ต่อหนึ่งตัวอักษร ซึ่งประเด็นการปรับแต่งจะพูดถึงใน Articulated

การอัปเดตแบบมองโลกในแง่ดีและการปรับสถานะกับเซิร์ฟเวอร์

  • ในการแก้ไขร่วมกันสไตล์ Google Docs ผู้ใช้ต้องเห็นผลจากการพิมพ์ของตัวเองทันทีโดยไม่ต้องรอคำตอบจากเซิร์ฟเวอร์
  • จุดที่ยากคือเมื่อไคลเอนต์มี โอเปอเรชันภายในเครื่องที่ยังรอการรับรอง อยู่ แล้วได้รับโอเปอเรชันจากระยะไกลที่เกิดขึ้นพร้อมกันจากเซิร์ฟเวอร์
  • ในกรณีนี้ไม่จำเป็นต้องใช้ CRDT เสมอไป แต่จัดการได้ด้วย server reconciliation
    1. ย้อนโอเปอเรชันภายในเครื่องที่ค้างอยู่ทั้งหมด เพื่อกรอสถานะไคลเอนต์กลับไปยังมุมมองของสถานะเซิร์ฟเวอร์ก่อนหน้า
    2. นำโอเปอเรชันจากระยะไกลมาใช้ เพื่อให้ไคลเอนต์ตรงกับสถานะเซิร์ฟเวอร์
    3. นำโอเปอเรชันภายในเครื่องที่ยังไม่รับรองกลับมาใช้ใหม่
  • ยังมีกลยุทธ์ที่ง่ายกว่าคือ Wait for Ack ซึ่งห้ามประมวลผลโอเปอเรชันจากระยะไกลเมื่อยังมีโอเปอเรชันภายในเครื่องค้างอยู่
    • ไคลเอนต์ของ Bob อาจเพิกเฉยต่อข้อความแรกจากเซิร์ฟเวอร์ จนกว่าจะได้รับสถานะเซิร์ฟเวอร์ที่รวมข้อความของตัวเองแล้ว
    • หาก Bob พิมพ์ต่อเนื่องหรือเครือข่ายหน่วงมาก ความล่าช้าอาจยืดยาวไม่สิ้นสุด ทำให้เรียลไทม์น้อยกว่า server reconciliation

ส่วนที่ต่างจาก CRDT

  • วิธีที่เสนอนี้มีคุณสมบัติบางอย่างร่วมกับ CRDT ตรงที่ให้ ID กับแต่ละตัวอักษรและใช้เครื่องหมาย isDeleted
  • ความต่างอยู่ที่วิธีจัดการลำดับ
    • ในวิธีนี้ ไคลเอนต์บอกเซิร์ฟเวอร์ว่า แทรก X หลัง Y และเซิร์ฟเวอร์จะทำตามนั้นตรง ๆ หรือประมวลผลด้วยวิธีอื่นที่นักพัฒนากำหนด
    • ใน CRDT สำหรับแก้ไขข้อความ ID จะถูกจัดเรียงด้วยอัลกอริทึมที่ซับซ้อน
  • แกนหลักที่ทำให้ CRDT สำหรับแก้ไขข้อความแต่ละตัวต่างกันก็คือ อัลกอริทึมจัดเรียง ID นี้เอง และแนวทางนี้หลีกเลี่ยงส่วนนั้น

ผลลัพธ์ที่เกิดจากการแทรกพร้อมกัน

  • หากมีผู้ใช้หลายคนพิมพ์พร้อมกันที่ตำแหน่งเดียวกัน ผลลัพธ์จะถูกจัดวางใน ลำดับย้อนกลับ ของลำดับที่เซิร์ฟเวอร์ได้รับโอเปอเรชัน
  • ตัวอย่างเช่น ข้อความคือ "My name is" และสมมติว่า Charlie พิมพ์ " Charlie" พร้อมกับที่ Dave พิมพ์ " Dave"
    • ถ้าโอเปอเรชันของ Charlie มาถึงก่อน เซิร์ฟเวอร์จะได้ "My name is Charlie"
    • โอเปอเรชันของ Dave ก็ยังแทรกหลัง ID ของ s ใน is เดิม ดังนั้นผลลัพธ์จะกลายเป็น "My name is Dave Charlie"
  • โอเปอเรชัน insert after ที่อ้างถึง ID เป้าหมายเดียวกันจะเรียงย้อนกับลำดับที่เซิร์ฟเวอร์ได้รับ แม้จะไม่มีภาวะแข่งขันพร้อมกันก็ตาม
  • อย่างไรก็ตาม คำที่พิมพ์จากซ้ายไปขวาจะไม่สลับปะปนกันในระดับตัวอักษร
    • แม้ Dave จะส่งแต่ละตัวอักษรเป็นโอเปอเรชันแยก a ก็จะแทรกหลัง D และ v ก็แทรกหลัง a
    • สถานะของเซิร์ฟเวอร์จะเปลี่ยนเป็น "My name is D Charlie" → "My name is Da Charlie" → "My name is Dav Charlie" → "My name is Dave Charlie"
  • หากพิมพ์จากขวาไปซ้าย แล้วโอเปอเรชันของ Charlie และ Dave มาถึงเซิร์ฟเวอร์แบบสลับกัน ข้อความผลลัพธ์ก็อาจสลับกันตามไปด้วย
    • ในทางปฏิบัติอาจเกิดขึ้นเมื่อผู้ใช้ทั้งสองออนไลน์พร้อมกันและเพิกเฉยต่อการแก้ไขที่อีกฝ่ายกำลังทำอยู่

เซิร์ฟเวอร์สามารถนิยามโอเปอเรชันที่ยืดหยุ่นกว่าได้

  • เมื่อใช้ server reconciliation เซิร์ฟเวอร์สามารถประมวลผลโอเปอเรชันจากไคลเอนต์ได้แทบจะตามต้องการ และท้ายที่สุดไคลเอนต์ก็จะไปถึงสถานะเดียวกัน
  • สิ่งนี้ต่างจาก CRDT·OT ที่อนุญาตเฉพาะโอเปอเรชันซึ่งต้องเป็นไปตามกฎพีชคณิตที่เข้มงวด
  • สำหรับการแทรกพร้อมกันที่ตำแหน่งเดียวกัน เซิร์ฟเวอร์อาจรับมือได้หลายแบบ
    • เพิกเฉยต่อโอเปอเรชันนั้นและทำเป็น no-op
    • เพิ่ม ID ลงในรายการภายในแต่ทำเครื่องหมายว่าถูกลบทันที เพื่อให้โอเปอเรชันของ Dave ในภายหลังยังอ้างถึง ID ก่อนหน้าได้
    • แทรกข้อความตามปกติ แต่ใช้ฟอร์แมตพิเศษกับทั้งสองคำเพื่อการตรวจทาน
    • แปลงการแก้ไขของ Dave ให้เป็น “ข้อเสนอแนะ” ที่แสดงข้างเนื้อหา
    • ถาม LLM ว่าควรแก้ข้อความอย่างไร
  • ไคลเอนต์เองก็สามารถส่งโอเปอเรชันที่สะท้อนเจตนาของผู้ใช้ได้ดีกว่าเดิม
    • insert before ใช้ได้เมื่ออยากสร้างหัวข้อเหนือย่อหน้า โดยไม่ให้หัวข้อไปแทรกอยู่กลางการแทรกพร้อมกันที่ท้ายย่อหน้าก่อนหน้า
    • โอเปอเรชัน fix typo อาจใส่เงื่อนไขอย่าง แทรก u หลัง o ของ color ที่มี ID X แต่เฉพาะเมื่อคำรอบข้างยังเป็น color อยู่
  • เซิร์ฟเวอร์ยังนิยามโอเปอเรชันที่ตำแหน่งแทรกเองเปลี่ยนไปหลังเซิร์ฟเวอร์ได้รับได้ด้วย
    • อาจจัดเรียงการแทรกพร้อมกันที่ตำแหน่งเดียวกันใหม่ตามลำดับตัวอักษร
    • หากเพิ่มโอเปอเรชัน move สำหรับลากวาง ก็อาจนำ insert after ภายในข้อความที่ถูกย้ายไปใช้ในข้อความที่ย้ายแล้ว แทนตำแหน่งเดิม

การจัดการฟอร์แมต rich text

  • ใน rich text จะต้องจัดการฟอร์แมตแบบอินไลน์ เช่น ตัวหนา ขนาดตัวอักษร และไฮเปอร์ลิงก์
  • ฟอร์แมตแบบช่วงก็สามารถอิง ID ของตัวอักษรแทนดัชนีได้เช่นกัน
    • เช่น ใช้ตัวหนาตั้งแต่ ID X ถึง ID Y
    • หากนิยามเป็น ตั้งแต่ ID X แบบ inclusive ถึง ID Y แบบ exclusive การแทรกพร้อมกันที่ปลายช่วงก็อาจถูกทำตัวหนาได้เช่นกัน
  • หากใช้ร่วมกับโปรแกรมแก้ไข rich text อย่าง ProseMirror เซิร์ฟเวอร์สามารถหาดัชนีอาร์เรย์ปัจจุบันของ ID X และ Y แล้วสั่งให้สถานะ ProseMirror ภายในเครื่องทำตัวหนาในช่วงนั้น
  • หลังจากนั้น ProseMirror สามารถคงตัวหนาไว้กับข้อความที่แทรกเพิ่มภายในช่วงดังกล่าวได้
    • แต่เซิร์ฟเวอร์ก็อาจเลือกจัดการต่างออกไปตามโอเปอเรชันแทรก เช่น bold set to false
  • หากต้องการเข้าใจความหมายเชิงระบบของ rich text แบบทำงานร่วมกัน บทความ Peritext essay เป็นแหล่งอ้างอิงที่ดี

เวอร์ชันกระจายศูนย์และความเชื่อมโยงกับ CRDT

  • ที่ผ่านมาสมมติว่ามีเซิร์ฟเวอร์กลางเป็นผู้กำหนดลำดับรวมของโอเปอเรชันตามลำดับที่เซิร์ฟเวอร์ได้รับ และอัปเดตสถานะอ้างอิงหลัก
  • หากไม่มีเซิร์ฟเวอร์กลาง หรือในแอปที่เซิร์ฟเวอร์เป็นเพียงทางเลือก ก็สามารถกำหนด ลำดับรวมสุดท้าย ของโอเปอเรชันแบบกระจายศูนย์ได้
    • ตัวอย่างเช่น จัดเรียงโอเปอเรชันด้วย Lamport timestamps
    • แต่ละไคลเอนต์จะถือผลจากการประมวลผลโอเปอเรชันทั้งหมดที่ได้รับตามลำดับนั้นเป็นสถานะอ้างอิงหลัก
  • ในกรณีนี้ ID ต่อหนึ่งตัวอักษรและโอเปอเรชัน insert after ก็ยังใช้ได้กับการปรับสถานะแบบกระจายศูนย์ที่ “ไม่มีเซิร์ฟเวอร์”
  • ในเชิงเทคนิค ผลลัพธ์นี้ก็กลายเป็น CRDT สำหรับแก้ไขข้อความ
    • เพราะเป็นอัลกอริทึมแก้ไขข้อความแบบทำงานร่วมกันที่กระจายศูนย์และมีความสอดคล้องในท้ายที่สุด
  • ความเชื่อมโยงกับ CRDT เดิมขึ้นอยู่กับวิธีจัดลำดับที่ใช้
    • หากจัดเรียงโอเปอเรชันด้วย Lamport timestamp ลำดับรายการที่ได้จะเทียบเท่ากับ RGA / Causal Trees
    • หากใช้ Lamport timestamp ร่วมกับโอเปอเรชันฟอร์แมต การทำงานจะคล้าย Peritext มาก
    • หากใช้การจัดเรียงเชิงทอพอโลยีแบบ depth-first ลำดับรายการที่ได้จะเทียบเท่ากับ Fugue
  • ยังไม่มีการเขียนคำพิสูจน์โดยละเอียดสำหรับข้ออ้างเรื่องความเทียบเท่านี้

Articulated: ไลบรารีช่วยในการนำไปใช้

  • ในการนำไปใช้จริง ตัวข้อความอาจถูกเก็บไว้ที่อื่น เช่น ในสถานะ ProseMirror และแนวทางนี้อาจต้องการเพียงรายการ ID ในรูปแบบต่อไปนี้
Array<{ id: ID; isDeleted: boolean }>
  • งานที่ต้องทำบ่อยกับรายการนี้มีสี่อย่าง
    • แปลงไปมาระหว่าง ID กับดัชนีอาร์เรย์ปัจจุบัน
    • แทรก ID ใหม่หลัง ID ที่ระบุ
    • ทำเครื่องหมายว่า ID ถูกลบ
    • ซีเรียลไลซ์สถานะเพื่อจัดเก็บและกู้คืน
  • อาร์เรย์ธรรมดาไม่เหมาะกับงานเหล่านี้
    • งานข้อ 1~3 ใช้เวลาเชิงเส้น
    • ต้องเก็บออบเจ็กต์และ UUID ต่อหนึ่งตัวอักษร จึงกินหน่วยความจำและพื้นที่จัดเก็บมาก
  • Articulated เป็นไลบรารี npm ขนาดเล็กที่ให้ความสามารถแบบเดียวกับอาร์เรย์นี้
  • โครงสร้างข้อมูลหลัก IdList ใช้การปรับแต่งที่คล้ายกับไลบรารี CRDT ยอดนิยมสำหรับแก้ไขข้อความ
    • ID อยู่ในรูป { bunchId, counter } โดย bunchId เป็น UUID ที่หลาย ID ใช้ร่วมกันได้
    • หาก ID จาก bunch เดียวกันอยู่ติดกัน เช่น กรณีทั่วไปที่แทรกจากซ้ายไปขวา ก็จะเก็บเป็นออบเจ็กต์เดียวทั้งในหน่วยความจำและสถานะที่ซีเรียลไลซ์แล้ว
    • โครงสร้างข้อมูลหลักไม่ใช่อาร์เรย์แต่เป็น B+Tree จึงเรียกเมธอดได้ในเวลา log หรือ log^2
  • IdList ยังเป็น persistent data structure ด้วย
    • ไคลเอนต์สามารถเก็บทั้งสถานะล่าสุดที่ได้รับจากเซิร์ฟเวอร์และสถานะแบบมองโลกในแง่ดีร่วมกันได้ในต้นทุนต่ำ
    • เมื่อได้รับโอเปอเรชันจากระยะไกล ก็ย้อนกลับไปยังสถานะล่าสุดของเซิร์ฟเวอร์ได้ง่าย
  • มีแหล่งข้อมูลเพิ่มเติมคือ docs, demos ชุดแรกเริ่ม และ IdListSimple ซึ่งเป็นเวอร์ชันเรียบง่ายขนาดไม่ถึง 300 SLOC
  • IdListSimple ตัดการปรับแต่งและความเป็น persistent ออก แต่ให้การทำงานเทียบเท่ากัน และผ่านการตรวจสอบด้วย fuzz tests

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

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

 
GN⁺ 2025-05-23
ความคิดเห็นบน Hacker News

  • ค่อนข้างเรียบร้อยดี อัลกอริทึมคือการผูก ID ที่ไม่ซ้ำกันทั่วทั้งระบบ คล้าย UUID ให้กับตัวอักษรแต่ละตัวในข้อความ เพื่อให้สามารถอ้างอิงได้อย่างสม่ำเสมอตลอดเวลา แทนที่จะใช้อินเด็กซ์ของอาร์เรย์ที่เปลี่ยนไปเรื่อย ๆ
    ไคลเอนต์ส่งคำสั่ง “insert after” ที่อ้างอิง ID เดิมไปยังเซิร์ฟเวอร์ แล้วเซิร์ฟเวอร์จะหา ID เป้าหมายและแทรกตัวอักษรใหม่ไว้ถัดจากนั้นทันที ส่วนการลบเป็นเพียงการซ่อนไม่ให้แสดง แต่ยังเก็บตัวอักษรไว้เพื่อใช้คำนวณตำแหน่ง “insert after” ต่อไป นอกเหนือจากการแก้ไขข้อความแล้ว ก็ดูมีศักยภาพในงานอย่าง การซิงก์โลกของเกม ด้วย

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

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

    • ถ้าไอเดียคือจะทำทางเลือกแทน CRDT ก็สงสัยว่าการทำมันให้เป็น CRDT แล้วได้อะไรขึ้นมา

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

    • เห็นด้วยเต็มที่ ถ้าเป็นอาร์เรย์ของอ็อบเจ็กต์แบบ “อะตอมิก” ที่เปลี่ยนคุณสมบัติไม่ได้ ก็น่าจะทำได้แค่เปลี่ยนสตริงให้เป็นชนิดของตัวเอง การเปลี่ยนภายในอ็อบเจ็กต์จะยากกว่า แต่บางทีมันอาจเป็นปัญหาเรื่องการจัดเก็บและเดินทรีให้มีประสิทธิภาพก็ได้
      ถ้าใช้ศัพท์ของ OP ผมคิดมาตลอดว่าผู้ใช้ไลบรารีช่วยเหลือควรแทรกลอจิก โมเดลเชิงความหมาย แบบเบา ๆ เพื่อป้องกันหรือจัดการสถานะที่ไม่ถูกต้องได้ เช่น รายการงานไม่ควรเป็น isDone: true พร้อมกับ state: inProgress ในเวลาเดียวกัน คล้ายกับ semantics ของการจัดรูปแบบ rich text ที่บทความที่ลิงก์พูดถึง
    • โดยเนื้อแท้ CRDT ทำงานโดย เลือกฝ่ายหนึ่งอย่างกำหนดได้แน่นอน เมื่อเกิดความขัดแย้ง ปัญหาคือโดยทั่วไปวิธีนี้ไม่ได้รับประกันว่าไม่มีข้อมูลสูญหายหรือข้อมูลยัง valid
      ลองนึกภาพว่า merge conflict ใน Git ทุกกรณีถูกแก้ด้วยการเลือกฝ่ายหนึ่งโดยอัตโนมัติ ส่วนใหญ่ผลลัพธ์จะผิด และบางครั้งอาจเป็นโค้ดที่คอมไพล์ไม่ผ่านด้วย ถ้าไม่มีคนมาแก้ทันที ก็จะนำไปสู่ผลลัพธ์ที่สับสนยิ่งกว่าเดิม
      เพราะอย่างนี้ผมจึงคิดว่า CRDT ไม่ได้แพร่หลายมากกว่านี้ CRDT แก้ได้แค่ “ปัญหาที่คิดว่ามีอยู่” แต่ไม่แก้ปัญหาจริงคือ การแก้ความขัดแย้งที่รักษาข้อมูล ความถูกต้อง และความหมายไว้ได้ แถมยังอาจทำให้ปัญหานี้แย่ลง เพราะจำกัดวิธีแก้ conflict ให้อยู่ในรูปแบบที่ทำซ้ำได้แบบ deterministic เท่านั้น

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

  • สารหลักของบทความนี้คือ ความซับซ้อนเต็มรูปแบบของ CRDT/OT จำเป็นเฉพาะตอนที่ไม่มีเซิร์ฟเวอร์กลางใช่ไหม?

    • แม้ไม่มีเซิร์ฟเวอร์กลาง ถ้ามีวิธีกระจายศูนย์ที่จัดเรียง operation ให้เป็น ลำดับรวม ในที่สุด แล้วนำไปใช้ตามลำดับนั้นได้ ก็สามารถหลีกเลี่ยงความซับซ้อนของ CRDT/OT ได้: https://mattweidner.com/2025/05/21/text-without-crdts.html#d...
      อย่างที่คอมเมนต์อื่น ๆ ว่าไว้ ในทางเทคนิคสิ่งนี้ก็เป็น CRDT และเป็นรูปแบบที่ค่อนข้างทั่วไปด้วย อีกทั้งการ implement การย้อนกลับและ replay operation เองก็ไม่ง่ายเหมือนกัน ถึงอย่างนั้นก็หวังว่าจะง่ายกว่าการใช้ CRDT/OT แบบดั้งเดิมสำหรับข้อมูลแต่ละชนิด
    • นั่นแหละคือแก่นของ CRDT มี สำเนา หลายชุดของโครงสร้างข้อมูลเดียวกันถูกจัดการอยู่บนหลายโหนด แต่ละสำเนาอัปเดตได้อย่างอิสระ และสุดท้ายทั้งหมดจะ converge
    • OT ต้องมี เซิร์ฟเวอร์กลาง

  • ผมไม่ใช่ผู้เชี่ยวชาญด้านนี้ แต่ความต่างหลักจาก CRDT อย่าง Automerge ดูเหมือนจะเป็น การประสานงานโดยเซิร์ฟเวอร์ เช่น ถ้าดูบทความนี้ [1] Automerge ใช้หมายเลขลำดับในการจัดการการแทรกพร้อมกัน และเมื่อมีการแทรกเกิดขึ้นพร้อมกัน ก็อาศัยลำดับ agent ID ที่ตกลงกันไว้ ในขณะที่วิธีนี้อาศัยให้เซิร์ฟเวอร์ประมวลผลตามลำดับที่มาถึง
    ในบทความมีข้อความว่า “ใน CRDT สำหรับแก้ไขข้อความ จะมีอัลกอริทึมสุดหรูคอยกำหนดลำดับของ ID อัลกอริทึมจัดลำดับนั้นคือสิ่งที่ทำให้ CRDT สำหรับแก้ไขข้อความหลายตัวแตกต่างกัน และเป็นส่วนซับซ้อนในเปเปอร์ CRDT เราหลีกเลี่ยงมันทั้งหมด” แนวคิดที่ว่าหลายแอปมีเซิร์ฟเวอร์กลางอยู่แล้ว จึงหลีกเลี่ยง “อัลกอริทึมสุดหรู” ได้นั้นฟังขึ้นอยู่ แต่การประสานงานโดยเซิร์ฟเวอร์ต้องอาศัยการย้อนกลับและ replay การแก้ไข local ด้วย จึงยังไม่มั่นใจ 100% ว่ามันง่ายกว่ามาก [1] https://josephg.com/blog/crdts-go-brrr/

    • เห็นด้วยว่าการย้อนกลับและ replay ก็ไม่ได้ง่ายเป็นพิเศษ persistent B+Tree ก็ไม่ใช่ของเรียบง่ายสักเท่าไร
    • เท่าที่รู้ Automerge ภายในจะเก็บ operation ทั้งหมดให้เป็น ลำดับรวม ที่สอดคล้องกันในที่สุด และใช้สิ่งนั้นแทนเซิร์ฟเวอร์ในการประสานงานได้: https://mattweidner.com/2025/05/21/text-without-crdts.html#d...
      แต่ Automerge ไม่ได้ทำแบบนั้นจริง ๆ และจัดการ operation ของข้อความด้วย RGA ซึ่งเป็น CRDT แบบดั้งเดิม น่าจะเพราะอย่างที่ชี้ไว้ว่า implement การย้อนกลับและ replay operation ไม่ง่าย

  • งั้นก็คือ CRDT ที่ไม่ได้ optimize ใช่ไหม? ประมาณว่าตั้งขนาดสูงสุดของเซ็ตไว้ที่ 1 แล้วดันไปเลย?

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

  • เพราะใช้ การประสานงานโดยเซิร์ฟเวอร์ การประสานฝั่งไคลเอนต์น่าจะยุ่งยาก จะรักษา UX การแก้ไขให้ลื่นไหลได้อย่างไรในขณะที่ต้องนำ server update มาใช้ทุกครั้งที่มาถึง?
    เช่น ถ้าคำขอแทรกตัวอักษรที่ไคลเอนต์ส่งไปล้มเหลว ก็แค่ retry หรือ? แล้วถ้าระหว่างนั้นมีอัปเดตเข้ามาล่ะ? แก้ไข: ในส่วน “Client-Side” ยอมรับกรณีนี้ และเสนอให้ rewind แล้ว replay รวมถึงเสนอทางที่ง่ายกว่าคือบล็อกไว้จนกว่าคิวรอจะว่าง จากมุมมอง frontend อาจมีข้อยกเว้น UI/UX ที่ไม่ได้ระบุไว้อีกยาวเป็นหางว่าว ดังนั้นโดยรวมแล้ว CRDT อาจดูง่ายกว่าก็ได้ และยังสงสัยด้วยว่าประสบการณ์การแก้ไขจะเป็นอย่างไรบน รถไฟใต้ดินนิวยอร์ก ที่การสื่อสารหลุดง่าย

    • ProseMirror กับ CodeMirror รุ่นใหม่มีทางแก้ปัญหานี้ที่ค่อนข้างสง่างาม โดย model การเปลี่ยนแปลงแต่ละครั้งของเอกสารเป็น ขั้นตอน (step) ที่ติดตามอินเด็กซ์ ไม่ใช่ identifier ของ node/text แล้วใช้โครงสร้างข้อมูลที่เรียกว่า “position map” เพื่อ map ขั้นตอนที่บัฟเฟอร์ไว้ไปยังตำแหน่งใหม่ ก่อนนำไปใช้กับเอกสาร
      ในทางปฏิบัติมันทำงานได้ค่อนข้างดี รายละเอียดอยู่ที่นี่:
      https://marijnhaverbeke.nl/blog/collaborative-editing.html
      https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...