cola: เทคโนโลยี Text CRDT สำหรับการแก้ไขร่วมกันแบบเรียลไทม์

 (nomad.foo)
1 คะแนน โดย GN⁺ 2023-09-04 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • cola คือ Text CRDT สำหรับการแก้ไขร่วมกันแบบเรียลไทม์ที่เขียนด้วย Rust โดยมุ่งให้เอกสารที่ peer หลายรายแก้ไขพร้อมกันลู่เข้าสู่สถานะเดียวกันโดยไม่ต้องมีตัวกลางประสานงาน
  • ตรึงตำแหน่งในเอกสารด้วย Anchor รูปแบบ ReplicaId.n แทน offset แบบง่าย ๆ เพื่อหลีกเลี่ยงปัญหาความหมายของตำแหน่งสั่นคลอนเมื่อมีการแก้ไขพร้อมกัน
  • ความขัดแย้งของการแทรกจะถูกจัดการอย่างสอดคล้องด้วย Lamport timestamp และการเรียงตาม ReplicaId ส่วนการลบจะจัดการเงื่อนไขการผสานรวมด้วย tombstone และ version vector แทนการลบจริง
  • ในแง่การ implement ใช้ RLE บนฐาน EditRun และ G-tree ที่แสดงด้วยดัชนีของ Vec เพื่อมุ่งให้ค้นหา·แทรกได้ในเวลาเชิงลอการิทึมภายใต้โมเดล ownership ที่ปลอดภัยของ Rust
  • ใน benchmark cola ถูกเปรียบเทียบกับ diamond-types, automerge, yrs และใน upstream เร็วกว่า diamond-types 1.4~2 เท่า ส่วน downstream ก็แสดงประสิทธิภาพที่เร็วมากเช่นกัน

ปัญหาการแก้ไขร่วมกันที่ cola จัดการ

  • cola คือ Text CRDT ที่เขียนด้วย Rust และออกแบบมาให้ replica หลายตัวลู่เข้าสู่สถานะเดียวกันในการแก้ไขร่วมกันแบบเรียลไทม์โดยไม่มีอำนาจส่วนกลาง
  • ในชั้นเครือข่ายมีเพียงสมมติฐานขั้นต่ำว่า การแก้ไขทั้งหมดจะไปถึง peer ทั้งหมดในท้ายที่สุด
    • การแก้ไขอาจถูกส่งหลายครั้งได้
    • การแก้ไขอาจมาถึงในลำดับใดก็ได้
    • peer ทุกตัวต้องได้รับการแก้ไขทั้งหมดในท้ายที่สุด
  • เป้าหมายไม่ใช่แค่ให้สถานะเอกสารเหมือนกันหลังได้รับการแก้ไขทั้งหมดเท่านั้น แต่ยังต้องให้เอกสารผลลัพธ์อยู่ในรูปแบบที่ผู้ใช้ยอมรับได้ด้วย

ตรึงตำแหน่งด้วย Anchor แทน offset

  • การแก้ไขแบบอิง offset เช่น insert "abc" at offset 8 อาจเปลี่ยนความหมายได้หาก peer อื่นแก้ไขพื้นที่ด้านหน้าพร้อมกัน ทำให้ replica แตกต่างกัน
  • cola อ้างอิงตำแหน่งในเอกสารด้วยตัวระบุที่เสถียร ไม่ใช่เนื้อหาอักขระหรือ offset
    • peer แต่ละตัวติดหมายเลขที่เพิ่มขึ้นให้กับอักขระที่แทรก
    • peer มี ReplicaId ซึ่งเป็นตัวระบุเฉพาะ
    • คู่ ReplicaId.n จะกลายเป็น Anchor ซึ่งเป็นตัวระบุตำแหน่งเฉพาะของอักขระ
  • ค่า n สามารถรับประกันความเป็นเอกลักษณ์ได้ด้วยการเพิ่ม counter ภายในเครื่อง แต่การรับประกันความเป็นเอกลักษณ์ทั่วโลกของ ReplicaId โดยไม่มีเซิร์ฟเวอร์กลางทำได้ยาก
    • cola ตั้งอยู่บนสมมติฐานว่าใช้จำนวนเต็มสุ่มขนาดใหญ่แบบ UUID ซึ่งมีโอกาสชนกันต่ำจนแทบมองข้ามได้
  • การแทรกกำหนดตำแหน่งด้วย Anchor หนึ่งตัว ส่วนการลบกำหนดช่วงด้วย Anchor สองตัวคือจุดเริ่มต้นและจุดสิ้นสุด

จัดเรียงความขัดแย้งของการแทรกให้เป็นลำดับเดียวกัน

  • เมื่อมีการแทรกหลายรายการเข้ามาที่ Anchor เดียวกัน cola จะกำหนดลำดับด้วย Lamport timestamp
  • Lamport clock จะอัปเดตตามกฎต่อไปนี้
    • เมื่อแทรกข้อความภายในเครื่อง ให้เพิ่ม clock ขึ้น 1
    • เมื่อได้รับการแทรกจากระยะไกล ให้ตั้งเป็น max(current, remote_timestamp) + 1
  • หากการแทรก A ถูกสร้างขึ้นในสภาพแวดล้อมที่ได้ผสานรวมการแทรก B แล้ว Lamport timestamp ของ A จะมากกว่า B
  • การแทรกที่ชนกันจะถูกเรียงตาม Lamport timestamp จากมากไปน้อย
  • สำหรับ การแทรกพร้อมกัน ที่ทั้ง Anchor และ Lamport timestamp เหมือนกัน ไม่มีลำดับที่ถูกต้องกว่าในมุมมองผู้ใช้ จึงเรียงตาม ReplicaId จากน้อยไปมากเพื่อให้ peer ต่าง ๆ สอดคล้องกัน

การลบจัดการด้วย tombstone และ version vector

  • การลบจะแปลง offset เริ่มต้น·สิ้นสุดเป็น Anchor แล้วเผยแพร่ไปยัง peer อื่น
  • หาก peer สองตัวลบพื้นที่เดียวกันพร้อมกัน ผลลัพธ์จะเหมือนกับการลบเพียงครั้งเดียว ตราบใดที่ไม่พิจารณา undo
    • ปัจจุบัน cola ยังไม่รองรับ undo ของการลบ
  • การจัดการการลบมีความยากสามประการ
    • หากลบข้อความที่ถูกลบออกไปอย่างสมบูรณ์ Anchor ของการแก้ไขที่ยังมาไม่ถึงอาจอยู่ในพื้นที่นั้น
    • หากผสานรวมการลบจากระยะไกลเร็วเกินไป เนื้อหาที่ peer ผู้สร้างการลบเห็นอาจต่างจากเนื้อหาของ peer ผู้รับ ทำให้ replica แตกต่างกัน
    • แม้อยู่ในช่วงการลบ ก็ไม่ควรลบอักขระที่ peer ผู้สร้างการลบยังไม่เคยเห็น
  • ปัญหาแรกแก้ด้วย tombstone
    • อักขระที่ถูกลบยังคงอยู่ในเอกสาร แต่ถูกทำเครื่องหมายว่าถูกลบแล้ว
    • วิธีนี้เพิ่มการใช้หน่วยความจำ
  • ปัญหาที่เหลือแก้ด้วยการใส่ version vector ในข้อความการลบ
    • key คือ ReplicaId ส่วน value คือ timestamp ของอักขระล่าสุดที่ peer ผู้สร้างการลบเห็นในขณะนั้น
    • peer ผู้รับจะรอผสานรวมการลบจนกว่า version vector ของตัวเองจะมากกว่าหรือเท่ากับ version vector ของข้อความการลบ
    • อักขระที่มี timestamp มากกว่า timestamp ใน version vector ของการลบจะถูกข้าม ไม่ถูกลบ
  • ใน cola เรียก version vector ว่า version map

การแยก Replica ออกจาก text buffer

  • สถานะเอกสารภายในเครื่องของ peer แต่ละตัวใน cola แสดงด้วย Replica
  • อัลกอริทึม CRDT ของ cola ไม่จำเป็นต้องรู้เนื้อหาสตริงจริง
    • ฟังก์ชัน API ไม่รับสตริงเป็น argument
    • cola จัดการเฉพาะบล็อกตัวเลข ไม่ใช่เนื้อหาเอกสาร
  • การออกแบบนี้แยก กลไก CRDT ออกจากการ implement text buffer จริง

ลด metadata ด้วย RLE และ EditRun

  • หากติด metadata ให้ทุกอักขระ จะสร้าง implementation ที่มีประสิทธิภาพดีได้ยาก ดังนั้น cola จึงรวมบล็อกที่มี timestamp ต่อเนื่องกันด้วย run-length encoding
  • เช่น หากวางเนื้อหาทั้งหมดของหน้า Manhattan Project ใน Wikipedia ก็อาจแสดงเป็นบล็อกเดียวได้ ไม่ใช่ 107,000 บล็อก
  • กรณีที่พิมพ์ประโยคทีละอักขระโดยไม่ย้าย cursor หรือลบ ก็สามารถแสดงเป็น run เดียวได้เช่นกันโดยไม่สร้างบล็อกทุกครั้งที่กดคีย์
  • ใน cola บล็อกต่อเนื่องลักษณะนี้เรียกว่า EditRun
    • EditRun ที่แตกไปแล้วจะคงที่ตลอดอายุเอกสารและจะไม่ขยายอีก
    • run ที่ยังไม่แตกจะอยู่ในสถานะ active
  • หากแทรกข้อความกลาง EditRun ที่มีอยู่ จะแบ่ง run เป็นสองส่วนแล้วใส่ข้อความใหม่ไว้ระหว่างกลาง
  • เมื่อลบข้อความ จะตัดส่วนนั้นออกจาก run และทำเครื่องหมายเป็น tombstone
    • run ที่ถูกลบก็ทำ RLE ได้ด้วยวิธีเดียวกัน จึงลดภาระหน่วยความจำของ tombstone

จาก linked list สู่ B-tree

  • เส้นทาง upstream ของการแก้ไขภายในเครื่องคือกระบวนการแปลงการแก้ไขแบบอิง offset ให้เป็นการแก้ไขที่ส่งให้ peer อื่นได้
    • ทั้งการแทรกและการลบต้องหา run ที่มี offset อยู่เพื่อสร้าง Anchor
    • หากจำเป็น จะแบ่ง run สูงสุด 2 ส่วนในการแทรก และสูงสุด 3 ส่วนในการลบ
  • ใน linked list การแบ่ง run เป็น O(1) แต่การหา run ที่มี offset อยู่ต้องสแกนตั้งแต่ต้น จึงใช้ เวลาเชิงเส้น
  • หาก cache active run ปัจจุบันและ offset ของมันไว้ จะเร็วเมื่อแก้ไขซ้ำที่ตำแหน่งเดิม แต่กรณีแย่ที่สุดยังคงเป็นเชิงเส้น
  • cola พิจารณาโครงสร้าง B-tree เพื่อประสิทธิภาพกรณีแย่ที่สุดแบบเวลาเชิงลอการิทึม
    • run แสดงเป็น leaf ของ B-tree
    • inode เก็บ child และผลรวมความยาวของ child
    • tombstone run มีส่วนร่วมเป็นความยาว 0
    • ความยาวของ root เท่ากับความยาวรวมของเอกสาร
  • B-tree สามารถค้นหาและแทรกได้ใน O(log n) ทำให้จัดการการแก้ไขภายในเครื่องได้ในเวลาเชิงลอการิทึม
  • อย่างไรก็ตาม เพื่อให้การแปลง Anchor -> run ในการแก้ไขจากระยะไกลมีประสิทธิภาพ ต้องหา leaf ที่มี Anchor นั้นอยู่

G-tree: B-tree ที่แสดงด้วยดัชนี Vec

  • แค่ pointer ไปยัง leaf ของ B-tree ทั่วไปไม่พอให้รู้ว่าจะลงไปถึง leaf อย่างไรในกระบวนการแทรกแบบ top-down
  • การดำเนินการแบบ bottom-up ต้องใช้ parent pointer ของแต่ละ node และในโมเดล ownership ที่ปลอดภัยของ Rust จะต้องใช้โครงสร้างอย่าง Rc<RefCell<_>> ซึ่งอาจช้าและซับซ้อน
  • cola เก็บ node ทั้งหมดไว้ใน dynamic array อย่าง Vec และแสดงการอ้างอิงระหว่าง node ด้วย ดัชนี แทน pointer
    • vector เป็นเจ้าของ node ทั้งหมด
    • แต่ละ node สามารถเก็บ parent index ได้
    • สามารถค้นหาได้สองทิศทางโดยไม่ใช้โค้ด unsafe
  • โครงสร้างนี้พึ่งพาสมมติฐานว่าดัชนี node จะไม่เปลี่ยน
    • node ใหม่ถูก append ที่ท้าย vector
    • cola ไม่ลบ run แต่ทำเครื่องหมายเป็น tombstone จึงไม่เกิดปัญหาดัชนี invalid
  • โครงสร้าง grow-only tree-in-a-vector แบบนี้ใน cola เรียกว่า G-tree
  • โค้ด Rust ของ G-tree คือรูปแบบที่คงโครงสร้าง parent-child ของ B-tree ไว้ แต่เปลี่ยนเฉพาะการแทนค่าในหน่วยความจำ

คุณลักษณะด้านประสิทธิภาพที่ G-tree สร้างขึ้น

  • G-tree ทำการค้นหาและแทรกแบบ top-down ได้ในเวลาเชิงลอการิทึมเช่นเดียวกับ B-tree
  • สามารถใช้ LeafIdx ซึ่งเป็นดัชนี vector ของ leaf เป็นตัวระบุ leaf ที่เสถียรได้
  • สามารถ cache active run ปัจจุบันด้วย LeafIdx แทน pointer ได้
    • หากแก้ไขซ้ำที่ตำแหน่ง cursor เดิม จะขยาย active run และอัปเดตเฉพาะความยาวของ ancestor จนถึง root
    • อาจจัดการได้ด้วยการเปรียบเทียบจำนวนเต็มไม่กี่ครั้งและการบวกจำนวนเต็ม 2~4 ครั้ง โดยไม่ต้องไล่ tree และไม่ต้อง allocation ใหม่
  • G-tree ของ cola ใช้ branching factor 32 และ inode มีอัตราการใช้งานเฉลี่ยประมาณ 20 child
    • เพียง 4 ระดับก็โดยทั่วไปสามารถเก็บ EditRun ที่แตกต่างกันได้ราว 160k รายการ
    • หลังประมวลผล editing trace ของ automerge-paper แล้ว G-tree ของ cola มี EditRun ประมาณ 15k รายการ
    • trace ดังกล่าวมีการแก้ไข 260k รายการ และถูกบันทึกตลอดหลายวัน
  • G-tree ทำให้ serialization และ deserialization เรียบง่ายด้วย เพราะ node ถูกเก็บในหน่วยความจำเชิงเส้นอยู่แล้ว

แปลง Anchor เป็น LeafIdx

  • เส้นทาง downstream ของการแก้ไขจากระยะไกลคือกระบวนการแปลงการแก้ไขแบบอิง Anchor เช่น insert 2.3..7 at 1.2, delete between 3.4 and 2.2 ให้เป็นการแก้ไขแบบอิง offset ของเอกสารภายในเครื่อง
  • เนื่องจาก G-tree ค้นหาขึ้นลงได้ หากรู้ LeafIdx ของ run ที่มี Anchor ใด ๆ อยู่ ก็สามารถคำนวณ offset นั้นได้
  • หัวใจคือการแปลง Anchor -> LeafIdx
  • การออกแบบแบบง่ายคือมี G-tree หรือ B-tree เสริม โดยเก็บ ReplicaId, temporal range และ LeafIdx ของ G-tree หลักไว้ที่ leaf
    • leaf ถูกเรียงอย่างสมบูรณ์ตาม ReplicaId และ temporal range
    • สามารถไล่ลง tree โดยอิง Anchor เพื่อหา LeafIdx ที่ต้องการได้
    • การค้นหาและแทรกเป็น O(log n) ทั้งคู่
  • ซอร์สโค้ดจริงของ cola ไม่ได้ใช้วิธี G-tree เสริมนี้ตรง ๆ
    • implementation จริงมีการค้นหาและแทรกเป็น O(log f)
    • f คือจำนวน fragment ที่ EditRun ซึ่งมี Anchor อยู่ถูกแบ่งออกไปตามเวลา
    • f จะไม่เกิน n เสมอ และโดยปกติน้อยกว่ามาก

ระดับความสมบูรณ์ปัจจุบันและงานที่เหลือ

  • การออกแบบของ cola มีพื้นฐานที่มุ่งเป้าเรื่องการลู่เข้า การรักษาเจตนา และประสิทธิภาพ
  • เพื่อให้พร้อมสำหรับ production ยังเหลืองานเพิ่มเติมบางอย่าง รวมถึงการรองรับ undo/redo

Benchmark CRDT ของ Rust

  • cola ถูกเปรียบเทียบกับ CRDT บน Rust 3 ตัว
  • benchmark วัดเวลาที่ใช้ประมวลผล editing trace จริงแบบ character-by-character
    • ใช้ไลบรารี benchmark ของ Rust ชื่อ criterion
    • วัดทั้งสองทิศทางคือ upstream และ downstream
    • โค้ด benchmark อยู่ที่ crdt-benches
  • กราฟใช้ 100 เท่าของประสิทธิภาพ cola เป็นเส้นฐาน และไม่แสดงค่าที่ช้ากว่า cola 100 เท่าขึ้นไป
  • สภาพแวดล้อมการรันคือ 2018 MacBook Pro, 2.2GHz 6-Core Intel Core i7
    • ตัวเลขอาจต่างกันบนเครื่องอื่น แต่คาดว่าประสิทธิภาพสัมพัทธ์จะใกล้เคียงกัน

ผล benchmark

  • ในทิศทาง upstream yrs และ automerge เกินเส้นฐาน
  • ใน upstream cola เร็วกว่า diamond-types 1.4~2 เท่า
  • ในทิศทาง downstream diamond-types crash ในทุก trace จึงไม่ได้ค่าการวัด
    • มีหมายเหตุว่าหากเป็นเพราะใช้ไลบรารีผิด จะอัปเดตผลลัพธ์
  • ใน downstream cola ช้ากว่าเดิมประมาณ 2 เท่า
    • เป็นผลลัพธ์ที่คาดไว้ เพราะโดยทั่วไปการผสานรวมการแก้ไขจากระยะไกลแพงกว่าการสร้างการแก้ไขภายในเครื่อง
  • cola ทำงานได้ในระดับใกล้เคียงหรือเร็วกว่าไลบรารี rope ที่เร็วทั้งสองทิศทาง และถูกประเมินว่าเป็น implementation ของ Text CRDT ที่เร็วที่สุดในปัจจุบัน

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

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

 
GN⁺ 2023-09-04
ความคิดเห็นใน Hacker News

  • ผมยังมองว่า G-tree ก็คือ B-tree ที่เพิ่มพอยน์เตอร์ไปยังพาเรนต์ อยู่ดี
    การที่มันถูกเก็บในอาร์เรย์เป็นแค่เรื่องของวิธีแทนข้อมูล ไม่ได้เปลี่ยนโครงสร้างโดยพื้นฐาน
    มันยังคงเก็บพอยน์เตอร์ เพียงแต่ไม่ได้เป็นหน่วยไบต์ แต่เป็นหน่วยขนาดของโหนด และเป็นตำแหน่งสัมพัทธ์จากสมาชิกตัวแรกของอาร์เรย์ ไม่ใช่จากจุดเริ่มต้นของ address space
    ตัวอย่างเช่น ต้นไม้ทวิภาคสมบูรณ์ที่เก็บในอาร์เรย์โดยไม่มีการอ้างอิงแบบชัดเจน ก็เป็นแค่ การแทนแบบแฝง ที่ลูกของดัชนี x อยู่ที่ 2x + 1 และ 2x + 2 แต่เราก็ยังเรียกมันว่าต้นไม้ทวิภาคอยู่ดี

    • ถึงอย่างนั้น การพูดถึง วิธีแทนข้อมูล ก็มีประโยชน์
      โดยเฉพาะในภาษาที่ชักนำให้ใช้การอ้างอิงแบบสัมพัทธ์และจัดการตัวเอง มากกว่าการอ้างอิงแบบ absolute
      หนึ่งในวิธีแทนต้นไม้ที่ผมสนใจคือการเก็บโหนดไว้ในอาร์เรย์แบน ๆ ตามลำดับการสำรวจแบบ depth-first
      ถ้าเป็นแบบอ่านอย่างเดียว และผู้อ่านตั้งใจจะไล่แบบ depth-first อยู่แล้ว ก็อาจมีประสิทธิภาพพอสมควร
      ทำให้นึกถึง S-expression กับ HTML

  • ถ้าไม่ได้พลาดอะไรใน API ดูเหมือนว่านี่จะไม่รองรับ ช่วงการจัดรูปแบบ อย่างตัวหนา/ตัวเอียง
    เท่าที่ผมรู้ ในอัลกอริทึม CRDT สำหรับ rich text ตอนนี้ Peritext ยังถือเป็นระดับแนวหน้า https://www.inkandswitch.com/peritext/
    หวังว่าโปรเจกต์นี้จะนำความสามารถด้าน rich text ของอัลกอริทึม Peritext มาด้วย

    • ในฐานะคนที่ติดตามวงการ CRDT อยู่บ้าง ผมสงสัยเสมอว่าจะสร้าง CRDT สำหรับข้อมูลมีโครงสร้าง ที่ทั่วไปกว่านี้ได้ไหม
      คือให้ผู้ใช้กำหนดโมเดลหรือสคีมาที่อธิบายสถานะที่ถูกต้องตามความหมาย
      ตัวอย่างเช่น ถ้า merge JSON แบบตรง ๆ อาจได้สถานะที่ถูกต้องตามไวยากรณ์ แต่ไม่มีความหมายที่สมเหตุสมผล
      เหมือนที่อัลกอริทึม Peritext รู้ว่าตัวหนา/ตัวเอียง/ขีดเส้นใต้เป็นการดำเนินการที่เพิ่มทับกันได้ แต่สีไฮไลต์ไม่ใช่ ผมคิดว่าคงดีถ้าผู้ใช้ประกาศในสคีมาได้ว่า state: notStarted กับ completionDate: 2023-09-04 อยู่ร่วมกันไม่ได้
    • คำถาม: ในบทความบอกว่า Cola จัดการเฉพาะการแก้ไขที่ไร้ข้อขัดแย้งสำหรับชนิดข้อมูลที่มันไม่รู้จัก และโดยสาระแล้วจัดการแค่สตรีมอักขระกับตำแหน่งเท่านั้น
      ถ้าอย่างนั้น เราจะแสดง ตัวการจัดรูปแบบไว้ในข้อความเอง แบบ HTML ไม่ได้หรือ?
      ผมไม่ได้รู้จักการแทน rich text แบบอื่นดีนัก เลยไม่ค่อยแน่ใจ
      อีกอย่าง หลังจากดูเอกสาร Peritext ที่ลิงก์ไว้ข้างบน ก็เห็นว่ามันกำลังจัดการความยากเฉพาะตัวของ RTF แบบนี้พอดี และอ่านแล้วน่าสนใจทีเดียว

  • เมื่อเทียบกับ Automerge หรือ Y.js/Yrs มีความต่างด้านประสิทธิภาพหรือฟีเจอร์อย่างไรบ้าง?

    • “ส่วนที่สาม” ของบทความเริ่มด้วยว่า “เรา benchmark cola เทียบกับ CRDT อีก 3 ตัวที่เขียนด้วย Rust คือ diamond-types, automerge และ yrs”
      ไลบรารี cola นี้ดูค่อนข้างได้เปรียบในแง่ความเร็วของการดำเนินการ
      ผมก็สงสัยเรื่องการใช้หน่วยความจำเหมือนกัน

  • อย่าสับสนกับงานชื่อเดียวกันของ Ian Piumarta
    https://www.piumarta.com/software/cola/
    https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=91...

    • หรือยังมี Cache Oblivious Lookahead Arrays ที่ครั้งหนึ่งเคยถูกมองว่าเป็นทางเลือกแทน MergeTree(LSM) แต่ตอนนี้ไม่ได้ใช้แล้ว https://github.com/giannitedesco/cola
    • ยังมีแอปแนวโคลน Notion ชื่อ coda.io ด้วย

  • เป็นงานที่ทำออกมาดี แต่ดูไม่เหมือน benchmark ที่เป็นธรรม
    มันไม่ได้คำนวณและเก็บ operation และไม่ได้เก็บข้อความจริงด้วย
    ถ้าจะทำ text CRDT ที่รองรับ delta update บนฐานนี้ ผู้ใช้ต้องเก็บ OpID => Text ไว้ในโครงสร้างแยกต่างหาก ซึ่งต้นทุนไม่ถูก

  • ถ้าใช้ crate slotmap(https://docs.rs/slotmap/latest/slotmap/) จะรองรับการลบได้โดยไม่ต้องกังวลว่าดัชนีจะย้าย หรือ “ดัชนี” จะไปชี้ค่าอื่น
    ใน slotmap จะเรียกสิ่งนี้ว่า key และใน key ก็มี หมายเลขเวอร์ชัน อยู่ด้วย

    • ในบริบทของ CRDT มันจะทำงานได้ไหม?
      ผมสงสัยเพราะการกำหนดลำดับทำได้ยาก และเวอร์ชันอาจมีความหมายแค่ในเครื่องเท่านั้น

  • คิดว่าจะลองเอาไปใช้กับโปรเจกต์ที่ Etherpad กับ Word รับไม่ไหวดูสักครั้ง

  • ถ้าสมมติว่าไคลเอนต์ที่เชื่อมต่อทั้งหมดได้รับการแก้ไขทั้งหมด ทำไมไม่ใส่ แฮชที่คาดไว้ ของสถานะข้อความเดิมไว้หน้าคำสั่ง offset และ insert/delete/replace ล่ะ?
    แบบนั้นแทบจะรับประกันได้ว่าการแก้ไขจะถูกนำไปใช้กับสถานะที่เหมาะสมเท่านั้น และการเปลี่ยนแปลงถัด ๆ ไปก็สามารถสะสมไว้ใน dictionary ที่ใช้ “แฮชของสถานะข้อมูลที่คาดว่าจะถูกนำไปใช้” เป็น key ได้
    แน่นอนว่าต้นทุนจะสูง เพราะต้องคำนวณแฮชซ้ำบนข้อมูลเดียวกัน แต่เข้าใจและ implement ได้ง่ายมาก

    • วิธีนั้นจะไม่มีทางนำ การแก้ไขแบบอะซิงโครนัส ไปใช้ได้เลย
      ถ้าผมแก้เอกสารแบบ local และคุณแก้แบบ remote แฮช “สถานะที่คาดไว้” ของคุณจะไม่มีวันตรงกับสถานะเอกสารของผมอีกต่อไป
      เพราะผมแก้ในเครื่องไปแล้ว
      ถ้า CRDT จะรับประกันการ converge ก็จริงที่ไคลเอนต์ทุกตัวต้องได้รับการแก้ไขทั้งหมด แต่คุณสมบัติที่ว่าไม่จำเป็นต้อง apply update ตามลำดับเฉพาะนั้นสำคัญใน use case แบบ distributed ในโลกจริง

  • สงสัยว่ามีวิธีเปิด การแก้ไขฟอร์มร่วมกัน ในเบราว์เซอร์แบบง่าย ๆ ไหม
    ถ้าคนสองคนเปิดหน้าเดียวกันหรือฟอร์มเดียวกัน แล้วเห็นได้ว่าอีกฝ่ายกำลังแก้ input field ไหนอยู่ และในช่องกรอกข้อความก็ใช้ text CRDT แบบนั้นคงดี
    เคยลองทำอะไรคล้าย ๆ กันด้วย Yjs แต่ค่อนข้างยากและทำงานได้ไม่ดี

    • อยากรู้ว่าทำไม Yjs ถึงไม่เหมาะ
      ดูเหมือนมันน่าจะเหมาะกับงานนั้นพอดี