- เมื่อแก้ไขโครงสร้างลำดับชั้นพร้อมกันในซอฟต์แวร์สำหรับการทำงานร่วมกัน อาจเกิด ความขัดแย้งของต้นไม้ เช่น โหนดซ้ำ วงจร และการย้ายโหนดย่อยของบรรพบุรุษที่ถูกลบ โดย Loro นำสิ่งนี้ไปใช้ด้วย CRDT ต้นไม้ที่ย้ายได้
- แนวทางของ Martin Kleppmann และคณะรวมการสร้าง·การลบ·การย้ายไว้ใน
Move t p m c และจัดการการลบเป็นการย้ายไปยังโหนด TRASH เพื่อรักษา การย้ายโหนดย่อยพร้อมกัน ไว้
- ลำดับแบบทั่วทั้งระบบสร้างด้วย Lamport Timestamp และ Peer ID และเมื่อ operation ระยะไกลเข้ามาแทรกกลางลำดับเดิม จะใช้ undo-do-redo เพื่อหลีกเลี่ยงวงจร
- Loro ผสาน Fractional Index เพื่อจัดเรียงโหนดพี่น้อง และเมื่อเกิดการแทรกพร้อมกันในตำแหน่งเดียวกันจน index ซ้อนกัน จะจัดการด้วย PeerID, jitter และการรีเซ็ต index
- ใน benchmark Loro Movable Tree สร้างโหนด 1,000 รายการแล้วสุ่มย้าย 10,000 ครั้งได้ใน 28ms แสดงประสิทธิภาพเพียงพอสำหรับการทำงานร่วมกันแบบเรียลไทม์และการ checkout เวอร์ชันย้อนหลัง
ความขัดแย้งที่เกิดในต้นไม้สำหรับการทำงานร่วมกัน
- เมื่อจัดการความสัมพันธ์แบบลำดับชั้นในระบบกระจายศูนย์และซอฟต์แวร์สำหรับการทำงานร่วมกัน หากโมเดลการย้ายเป็นการผสมกันของการลบและการแทรก วิธีแก้ความขัดแย้งมักคลาดเคลื่อนจากความคาดหวังของผู้ใช้ได้ง่าย
- หากโหนดเดียวกันถูกย้ายพร้อมกันไปยัง parent ต่างกันในหลาย replica โหนดหนึ่งอาจถูกลบสองครั้งแล้วถูกสร้างใหม่ใต้ parent สองตัว ทำให้เกิด โหนดซ้ำที่มีเนื้อหาเดียวกัน
- operation พื้นฐานของต้นไม้ที่ย้ายได้มีสามอย่างคือ สร้าง, ลบ, ย้าย
- สถานการณ์ที่มักเป็นปัญหาเมื่อซิงก์มีดังนี้
- โหนดเดียวกันถูกลบพร้อมกับถูกย้าย
- โหนดเดียวกันถูกย้ายไปอยู่ใต้ parent ต่างกัน
- การย้ายโหนดต่างกันถูกรวมกันจนเกิด วงจร
- โหนดย่อยถูกย้ายในขณะที่โหนดบรรพบุรุษถูกลบ
วิธีจัดการตามประเภทความขัดแย้ง
- หากการลบและการย้ายของโหนดเดียวกันขัดแย้งกัน สามารถนำ operation หนึ่งไปใช้และละเว้นอีก operation ได้ตาม timestamp ของระบบกระจายศูนย์หรือข้อกำหนดของแอปพลิเคชัน
- กรณีที่โหนดเดียวกันถูกย้ายไปอยู่ใต้ parent ต่างกัน ทางเลือกจะแตกต่างกันไปตามแอปพลิเคชัน
- ลบโหนดแล้วสร้างสำเนาไว้ใต้ parent ต่างกัน จากนั้นปฏิบัติต่อแต่ละสำเนาอย่างอิสระ
- อาจให้โหนดหนึ่งชี้ไปยัง parent สองตัวได้ แต่นั่นทำลายโครงสร้างต้นไม้ จึงโดยทั่วไปยอมรับได้ยาก
- หากจัดเรียง operation ทั้งหมดแล้วนำไปใช้ตามลำดับ จะสร้างผลลัพธ์เดียวกันในทุก peer ได้
- เมื่อการย้ายโหนดต่างกันสร้างวงจร การแก้ความขัดแย้งของต้นไม้ที่ย้ายได้จะซับซ้อนเป็นพิเศษ
- Matthew Weidner สรุปแนวทางต่าง ๆ เช่น การจัดการข้อผิดพลาด การเรนเดอร์พื้นที่ “time-out” การปฏิเสธโดยเซิร์ฟเวอร์ การข้าม operation ที่สร้างวงจรหลังทำ topological sort การซ่อน edge บางเส้นขณะเรนเดอร์ และการย้อนกลับไปยัง parent เดิม
- สถานการณ์ที่โหนดย่อยถูกย้ายระหว่างที่โหนดบรรพบุรุษถูกลบก็เป็นสิ่งที่มองข้ามได้ง่าย
- หากลบโหนดย่อยทั้งหมดของบรรพบุรุษทันที ผู้ใช้อาจเข้าใจผิดว่าข้อมูลของตนสูญหาย
แนวทางของ Dropbox และ Figma
- ตอนแรก Dropbox จัดการการย้ายไฟล์เป็นสองขั้นตอน คือ ลบจากตำแหน่งเดิมแล้วสร้างในตำแหน่งใหม่
- หากเกิดไฟดับหรือระบบล่มระหว่างการลบกับการสร้าง จะมี ความเสี่ยงข้อมูลสูญหาย
- ปัจจุบันเมื่อหลายคนพยายามย้ายและบันทึกไฟล์เดียวกันพร้อมกัน ระบบจะตรวจพบความขัดแย้ง และโดยปกติจะบันทึกไฟล์ต้นฉบับไว้หนึ่งเวอร์ชัน จากนั้นสร้าง “conflicted copy” สำหรับการเปลี่ยนแปลงของผู้ใช้คนหนึ่ง
- Figma มองว่าโครงสร้างต้นไม้เป็นส่วนที่ซับซ้อนที่สุดในระบบการทำงานร่วมกัน และกำหนดคุณสมบัติ
parent ให้กับแต่ละองค์ประกอบ
- เซิร์ฟเวอร์กลางเฝ้าดูการอัปเดตจากผู้ใช้หลายคน และหาก operation ใดอาจสร้างวงจร ก็จะปฏิเสธ operation นั้น
- เนื่องจากความหน่วงของเครือข่าย อาจเกิดวงจรชั่วคราวก่อนที่เซิร์ฟเวอร์จะปฏิเสธ
- ในกรณีนี้ Figma จะซ่อนองค์ประกอบที่อยู่ในวงจรไว้ชั่วคราว และรักษาสถานะไว้จนกว่าเซิร์ฟเวอร์จะปฏิเสธ operation อย่างเป็นทางการ
- คำอธิบายที่เกี่ยวข้องดูได้ใน บทความ multiplayer technology ของ Figma
สองแนวทางของ CRDT ต้นไม้ที่ย้ายได้
- แทนที่จะใช้วิธีแบบรวมศูนย์ สามารถจัดการโครงสร้างต้นไม้สำหรับการทำงานร่วมกันด้วย CRDT ได้
- อัลกอริทึมต้นไม้ที่ใช้ CRDT ในยุคแรกทำได้ยากในการ implement และมี overhead ด้าน storage สูง แต่เมื่อผ่านการ optimize และปรับปรุง ก็มีอัลกอริทึมซิงก์ต้นไม้บางแบบที่เหมาะกับสภาพแวดล้อม production ปรากฏขึ้น
- แนวทางหลักที่ใช้ CRDT มีสองแบบ
แนวทาง Kleppmann: รวมทุก operation เป็น Move
- A highly-available move operation for replicated trees รวมการสร้าง·การลบ·การย้ายของต้นไม้ไว้เป็น move operation เดียว
- move operation นิยามด้วยค่าสี่ค่าคือ
Move t p m c
t: timestamp ที่ไม่ซ้ำและจัดเรียงได้ เช่น Lamport timestampp: ID ของ parent nodem: metadata ที่เชื่อมโยงกับ nodec: ID ของ child node
- หากไม่มี
c ในต้นไม้ จะกลายเป็น operation สร้าง ที่สร้าง child c ไว้ใต้ parent p
- หากมี
c อยู่แล้ว จะกลายเป็น operation ย้าย ที่ย้ายจาก parent เดิมไปยัง parent ใหม่ p
- การลบจัดการด้วยวิธีย้ายไปยังโหนด
TRASH ที่กำหนดไว้
- โหนดย่อยทั้งหมดของ
TRASH ถือว่าถูกลบแล้ว
- แต่ยังคงไว้ในหน่วยความจำ เพื่อให้การแก้ไขพร้อมกันสามารถย้ายโหนดนั้นไปยังโหนดอื่นได้
- นี่เป็นกลไกสำหรับจัดการสถานการณ์ที่การลบบรรพบุรุษและการย้ายโหนดย่อยเกิดขึ้นพร้อมกัน
การจัดลำดับและ unsafe operation
- เนื่องจากการลบก็ถูกนิยามเป็น move operation เช่นกัน “การลบและการย้ายโหนดเดียวกัน” จึงกลายเป็นความขัดแย้งระหว่าง move operation สองรายการ
- ปัญหาหลักที่เหลือมีสองอย่าง
- การย้ายโหนดเดียวกันไปอยู่ใต้ parent ต่างกัน
- การย้ายโหนดต่างกันจนสร้าง วงจร
- หากจัดเรียง operation ทั้งหมดเป็นลำดับเชิงเส้นด้วย Lamport timestamp และ Peer ID การย้ายพร้อมกันของโหนดเดียวกันก็จะแสดงเป็น operation สองรายการที่มีลำดับ
- เมื่อโมเดลต้นไม้ใช้เฉพาะ move operation สถานการณ์พิเศษของการแก้ไขพร้อมกันจะลดลงเหลือการสร้างวงจร
- operation ที่สร้างวงจรถูกถือเป็น unsafe operation
- อัลกอริทึมจะจัดเรียง move operation ทั้งหมดตามลำดับ timestamp
- ตรวจจับวงจรก่อนนำแต่ละ operation ไปใช้
- หากสร้างวงจร จะละเว้น unsafe operation นั้นเพื่อรักษาโครงสร้างต้นไม้ที่ถูกต้อง
Lamport Timestamp และการใช้ operation ระยะไกล
- Lamport Timestamp ช่วยให้ตัดสินลำดับเหตุและผลของ event ในระบบกระจายศูนย์ได้
- peer แต่ละตัวมี counter ที่เริ่มจาก 0
- เมื่อเกิด event ในเครื่อง จะเพิ่ม counter ขึ้น 1 แล้วใช้ค่านั้นเป็น timestamp
- เมื่อ peer
A ส่งข้อความให้ B จะแนบ timestamp ไปด้วย
B เปรียบเทียบนาฬิกาเชิงตรรกะของตนกับ timestamp ที่ได้รับ แล้วอัปเดตเป็นค่าที่ใหญ่กว่า
- การจัดเรียงแบบทั่วทั้งระบบจะเปรียบเทียบ Lamport Timestamp ก่อน และหากค่าเท่ากันจะใช้ ID เฉพาะของ peer เป็น tie-breaker
- หากการอัปเดตระยะไกลเข้ามาแทรกกลางลำดับ operation ที่จัดเรียงไว้เดิม จำเป็นต้องใช้ undo-do-redo
- ย้อน operation ล่าสุดกลับ
- แทรก operation ใหม่แล้วนำไปใช้
- นำ operation ที่ย้อนกลับไปมาใช้อีกครั้ง
- เพื่อย้อน move operation ได้รวดเร็ว จะ cache old parent ของโหนดเป้าหมายไว้ก่อนใช้แต่ละ move
- แม้ unsafe operation จะถูกละเว้นผลลัพธ์ ก็ยังต้องเก็บบันทึกไว้
- ความปลอดภัยของ operation ถูกกำหนดแบบ dynamic
- หากภายหลังได้รับการอัปเดตที่ลบโหนดอื่นซึ่งเคยทำให้เกิดวงจรก่อนหน้านั้น operation ที่เคย unsafe อาจกลายเป็น safe ได้
- ในกระบวนการ undo จำเป็นต้องมีเครื่องหมาย ineffective เพื่อค้นหา parent เป้าหมายของ operation ล่าสุดที่เคยมีผลจริง
ตัวอย่าง undo-do-redo
- หาก operation ใหม่พึ่งพา operation ที่ยังไม่มีในเครื่อง แสดงว่ายังขาดการอัปเดตเวอร์ชันระหว่างทางอยู่ จึงต้องแคชไว้ชั่วคราว แล้วค่อยนำไปใช้หลังจากได้รับการอัปเดตที่ขาดไป
- หาก
opId ใหม่มีค่ามากกว่า operation ที่มีอยู่ทั้งหมด ก็สามารถนำไปใช้ได้ทันที
- หาก safe ให้บันทึก parent ปัจจุบันของโหนดเป้าหมายเป็น old parent แล้วใช้ move
- หาก unsafe ให้ทำเครื่องหมายเป็น ineffective และละเว้นผลของมัน
- หาก
opId ใหม่ถูกแทรกเข้ามากลางลำดับเดิม ให้ดึง operation หลังจากนั้นออกมาทีละรายการเพื่อย้อนกลับ จากนั้นนำ operation ใหม่ไปใช้ แล้วนำ operation ที่ย้อนกลับไว้กลับมาใช้ใหม่ตามลำดับ
- ในโฟลว์ตัวอย่าง หลังจาก
Peer1 ย้าย C ไปไว้ใต้ B ในเครื่องแล้ว จะได้รับ operation จาก Peer0 ที่ย้าย B ไปไว้ใต้ C
- ในลำดับ Lamport timestamp
0:3 มาก่อน 1:3 ดังนั้นจึง undo 1:3 ก่อน เพื่อย้าย C กลับไปยัง old parent คือ A
- จากนั้นใช้
0:3 เพื่อย้าย B ไปไว้ใต้ C
- แล้ว redo
1:3 อีกครั้งโดยพยายามย้าย C ไปไว้ใต้ B แต่ตรวจพบวงจร จึงไม่ถูกนำไปใช้
- สถานะของต้นไม้ไม่เปลี่ยนแปลง และกระบวนการ undo-do-redo ก็เสร็จสิ้น
แนวทางของ Evan Wallace: ติดตาม parent ในอดีต
- CRDT: Mutable Tree Hierarchy ของ Evan Wallace ให้แต่ละโหนดติดตาม parent node ทั้งหมดในอดีต
- parent แต่ละรายการที่บันทึกไว้จะมี counter กำกับ
- ค่า count ของ parent ใหม่จะมากกว่าค่า count ของ parent ทั้งหมดในอดีตของโหนดนั้น 1
- parent ที่มี count สูงสุดจะกลายเป็น parent ปัจจุบัน
- เมื่อซิงโครไนซ์ จะซิงโครไนซ์บันทึก parent ไปด้วย
- หากเกิดวงจร อัลกอริทึมแบบ heuristic จะนำโหนดที่ทำให้เกิดวงจรไปต่อกลับเข้ากับ parent ในอดีตที่ใกล้ที่สุดซึ่งไม่ทำให้เกิดวงจรและเชื่อมต่อกับ root
- ทำซ้ำกระบวนการนี้จนกว่าโหนดที่อยู่ในวงจรทั้งหมดจะถูกต่อกลับเข้ากับต้นไม้อีกครั้ง เพื่อซิงโครไนซ์โครงสร้างต้นไม้ระหว่าง replica
- วิธีนี้ไม่จำเป็นต้องใช้ขั้นตอน undo-do-redo ที่มีต้นทุนสูง แต่ทุกครั้งที่ได้รับ remote move จะต้องตรวจสอบว่าโหนดทั้งหมดเชื่อมต่อกับ root หรือไม่ และต้องนำโหนดที่เกิดวงจรไปต่อกลับ ดังนั้นเมื่อมีโหนดจำนวนมาก ประสิทธิภาพอาจแย่ลงได้
- มีการสร้าง benchmark แยกไว้สำหรับเปรียบเทียบประสิทธิภาพ
การนำ Movable Tree ไปใช้ใน Loro
- Loro นำอัลกอริทึมจาก A highly-available move operation for replicated trees ของ Martin Kleppmann และคณะมาใช้
- อัลกอริทึมนี้ให้ประสิทธิภาพสูงในสถานการณ์จริงส่วนใหญ่
- กระบวนการหลักคือ undo-do-redo ซึ่งคล้ายมากกับวิธีที่ Eg-walker(Event Graph Walker) ใน Loro นำ remote update ไปใช้
- ต้นไม้ที่ย้ายได้เพียงอย่างเดียวไม่สามารถแก้ปัญหาเรื่องลำดับของ sibling node ได้
- ใน outline notes หรือการจัดการ layer ของซอฟต์แวร์ออกแบบกราฟิก จำเป็นต้องจัดเรียง child node
- ผู้ใช้ต้องปรับลำดับโหนดและซิงโครไนซ์ลำดับนั้นกับผู้ร่วมงานหรืออุปกรณ์อื่น
- Loro ผสานอัลกอริทึม
Fractional Index เพื่อให้ child node ของต้นไม้ที่ย้ายได้สามารถจัดเรียงได้
Fractional Index และการชนกันของการแทรกพร้อมกัน
Fractional Index กำหนดค่าที่จัดเรียงได้ให้กับแต่ละอ็อบเจ็กต์
- เมื่อมีการแทรกใหม่ระหว่างอ็อบเจ็กต์สองตัว
Fractional Index ของอ็อบเจ็กต์ใหม่จะอยู่ระหว่างค่าด้านซ้ายและด้านขวา
- อ่านคำอธิบายที่เกี่ยวข้องได้ที่ Figma blog และ Evan blog
- ในสภาพแวดล้อมแบบกระจาย หาก peer หลายรายแทรกโหนดใหม่ในตำแหน่งเดียวกัน โหนดที่มีเนื้อหาต่างกันอาจได้รับ
Fractional Index เดียวกัน
- Loro คง
Fractional Index ที่เหมือนกันไว้ และกำหนดลำดับสัมพัทธ์ระหว่างอินเด็กซ์เดียวกันด้วย PeerID ซึ่งเป็น ID เฉพาะของแต่ละ peer
- หากมี
Fractional Index เดียวกันอยู่ทั้งสองด้าน จะไม่สามารถสร้าง Fractional Index ใหม่ระหว่างกลางได้
- Loro จัดการปัญหานี้ด้วยสองวิธี
- เพิ่ม jitter ปริมาณหนึ่งใน
Fractional Index ที่สร้างขึ้น เพื่อลดโอกาสเกิดอินเด็กซ์ซ้ำอย่างมาก
- เช่น หากค่าระหว่าง 0 และ 1 เดิมคือ 0.5 เมื่อมี random jitter อาจกลายเป็นค่าอย่าง
0.52712, 0.58312, 0.52834
- หากต้องแทรกระหว่าง
0.7@A และ 0.7@B สามารถรีเซ็ตได้โดยกำหนด Fractional Index ใหม่ให้กับโหนดใหม่และโหนด 0.7@B ตามลำดับ จากช่วงระหว่าง 0.7 และ 1
ขนาดการเข้ารหัสและการตั้งค่า jitter
- Loro ใช้ implementation ของ
Fractional Index แบบ Vec<u8> จาก drifting-in-space
- implementation นี้เป็น base 256
- ในค่าเริ่มต้น ต้องแทรกค่าต่อเนื่องไปข้างหน้าหรือข้างหลัง 128 ค่า จึงจะทำให้ขนาด byte ของ
Fractional Index เพิ่มขึ้น 1
- storage overhead ในกรณีเลวร้ายที่สุดเกิดขึ้นเมื่อแทรกค่าใหม่สลับไปมาทุกครั้ง
- เช่น จาก
ab ใส่ c ระหว่าง a และ b แล้วใส่ d ระหว่าง c และ b อีกครั้ง จากนั้นใส่ e ระหว่าง c และ d เป็นต้น
- ในกรณีเช่นนี้ operation ใหม่หนึ่งรายการอาจต้องใช้ byte เพิ่ม แต่เป็นสถานการณ์ที่พบได้น้อยมาก
- Loro เพิ่มวิธีแก้ jitter แบบง่ายเข้าไปใน implementation เดิม
- append random bytes ตามความยาวของค่า jitter ต่อท้าย
Fractional Index
- ใน JavaScript สามารถเปิดใช้ jitter ได้โดยใส่ค่าบวกใน
doc.setFractionalIndexJitter(number)
- ขนาดการเข้ารหัสจะเพิ่มขึ้นเล็กน้อย โดยแต่ละ
Fractional Index จะมี jitter bytes เพิ่มเข้ามา
- ความสัมพันธ์ระหว่าง jitter กับจำนวนการแก้ไขพร้อมกันสูงสุด
n เพื่อหลีกเลี่ยงการชนกันด้วยความน่าจะเป็น 99% เมื่อสร้าง Fractional Index ในตำแหน่งเดียวกัน มีดังนี้
| jitter |
จำนวนการแก้ไขพร้อมกันสูงสุด |
| 1 |
3 |
| 2 |
37 |
| 3 |
582 |
Fractional Index จำนวนมากที่ถูกจัดเรียงจะมี prefix ร่วมกันมากขึ้น- Loro ลดขนาดการเข้ารหัสโดยรวมด้วย prefix optimization ซึ่งบันทึกเฉพาะจำนวน prefix bit ที่เหมือนกับค่าก่อนหน้าและ bytes ที่เหลือ
งานที่เกี่ยวข้องและเหตุผลที่เลือก
- นอกจาก
Fractional Index แล้ว ยังมี movable list CRDT ที่สามารถจัดลำดับ sibling node ของต้นไม้ได้
- Moving Elements in List CRDTs ของ Martin Kleppmann ถูกใช้ใน Movable List ของ Loro
- วิธีแก้แบบ
Fractional Index มี implementation ที่เรียบง่ายกว่า
- เมื่อโมเดล tree node หากไม่ให้ stable position representation แก่ child node โครงสร้างต้นไม้โดยรวมจะซับซ้อนเกินไป
Fractional Index มีปัญหา interleaving
- ในกรณีที่ต้องการเพียงลำดับสัมพัทธ์ เช่น Figma layer item หรือ multi-level bookmark และไม่ต้องการ semantics แบบลำดับที่เข้มงวด ก็ถือว่ายอมรับได้
ผลลัพธ์เบนช์มาร์ก
- Loro ได้ทำเบนช์มาร์กประสิทธิภาพของการนำ Movable Tree ไปใช้งาน ภายใต้เงื่อนไขสุดขั้ว เช่น การย้ายโหนดแบบสุ่ม การสลับไปยังเวอร์ชันในอดีต และโครงสร้างต้นไม้ที่ลึกมาก
- ผลลัพธ์อยู่ในระดับที่รองรับการทำงานร่วมกันแบบเรียลไทม์และการ checkout เวอร์ชันในอดีตได้อย่างราบรื่น
- สภาพแวดล้อมการทดสอบคือ M2 Max CPU และโค้ดเบนช์อยู่ที่ tree.rs
| งาน |
เวลา |
การตั้งค่า |
| ย้ายแบบสุ่ม 10000 ครั้ง |
28ms |
สร้างโหนด 1000 โหนดก่อน |
| สลับไปยังเวอร์ชันต่างกัน 1000 ครั้ง |
153ms |
สร้างโหนด 1000 โหนดก่อน แล้วจึงย้าย 1000 ครั้ง |
| สลับไปยังเวอร์ชันต่างกัน 1000 ครั้งในต้นไม้ความลึก 300 |
701ms |
โหนดใหม่เป็นลูกของโหนดก่อนหน้า |
ตัวอย่างการใช้งานและเดโม
LoroTree ของ loro-crdt รองรับการสร้างโหนด การสร้างโดยกำหนดตำแหน่ง การย้าย การย้ายไปเป็น root การย้ายไปไว้ก่อนหรือหลังโหนดอื่น การดู index ภายใน parent การดู Fractional Index และการเข้าถึง data map ของโหนด
import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";
let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let root: LoroTreeNode = tree.createNode();
// By default, append to the end of the parent node's children list
let node = root.createNode();
// Specify the child's position
let node2 = root.createNode(0);
// Move `node2` to be the last child of `node`
node2.move(node);
// Move `node` to be the first child of `node2`
node.move(node2, 0);
// Move the node to become the root node
node.move();
// Move the node to be positioned after another node
node.moveAfter(node2);
// Move the node to be positioned before another node
node.moveBefore(node2);
// Retrieve the index of the node within its parent's children
let index = node.index();
// Get the `Fractional Index` of the node
let fractionalIndex = node.fractionalIndex();
// Access the associated data map container
let nodeData: LoroMap = node.data;
- มีการสร้างเดโมแอป Todo ที่จำลองการซิงค์ข้อมูลระหว่างหลาย peer ด้วย Loro
Movable Tree ใช้แสดงความสัมพันธ์ของ subtaskMap ใช้แสดงคุณสมบัติต่าง ๆ ของ taskText ใช้แสดง title ของ task- นอกจากการสร้าง ย้าย แก้ไข และลบแล้ว ยังมีการสลับเวอร์ชันบนพื้นฐานของ Loro ด้วย
- สามารถลาก scrollbar เพื่อสลับไปมาระหว่างเวอร์ชันในอดีตทั้งหมดที่เคยทำไว้ได้
สรุป
- การนำ CRDT ต้นไม้ที่ย้ายได้ไปใช้งานนั้นยาก เพราะมีทั้งการย้ายพร้อมกัน การลบ วงจร และการผสมกันของการลบบรรพบุรุษกับการย้ายโหนดลูกหลาน
- Loro นำการย้ายลำดับชั้นของต้นไม้ไปใช้งานด้วยอัลกอริทึม move operation แบบ high-availability ของ Kleppmann และคณะ
- การย้ายและการจัดเรียงระหว่างโหนดลูกจัดการด้วยการผสานการใช้งาน
Fractional Index ของ drifting-in-space
- การผสมผสานนี้สามารถตอบสนองความต้องการของสถานการณ์แอปพลิเคชันสำหรับการทำงานร่วมกันได้หลากหลาย
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
กำลังสร้าง multiplayer editor ตัวใหม่สำหรับงาน/โน้ต [1] ซึ่งรองรับทั้งการดำเนินการกับข้อความและ outliner
ภายนอกทำงานเหมือนเอกสารข้อความแบบแบน แต่เพราะฟีเจอร์ outliner ภายในจึงเป็น tree ขนาดใหญ่ สำหรับการซิงก์การเปลี่ยนแปลง ใช้วิธีคล้ายกับ operation แบบ move ที่มีความพร้อมใช้งานสูง มี operation ที่เปลี่ยน tree เพียงตัวเดียวคือ
insmovและเมื่อไคลเอนต์ออนไลน์ ก็จะซิงก์ชุดการเปลี่ยนแปลง C กับเซิร์ฟเวอร์ หากเซิร์ฟเวอร์มีการเปลี่ยนแปลงจากรีโมต ก็จะส่งการเปลี่ยนแปลงทั้งหมด R ตั้งแต่การซิงก์ครั้งล่าสุดกลับมาในลำดับเชิงเส้นแบบ global จากนั้นย้อนกลับinsmovของการเปลี่ยนแปลงในเครื่อง C แล้วนำ R และการเปลี่ยนแปลงใหม่ที่ยังไม่ได้ซิงก์กลับมา apply ใหม่ไม่ได้ใช้ fractional index แต่ใน tuple ของ
insmovจะมีไม่เพียง parent P แต่ยังรวมถึงguidA ของ sibling ก่อนหน้าด้วย operation ทั้งหมดกับ tree สุดท้ายแล้วจะถูก apply ตามลำดับเชิงเส้นแบบ global ที่เซิร์ฟเวอร์กำหนด ดังนั้นการเรียงลำดับจึงจัดการโดย operationinsmovเอง ส่วนใหญ่ไม่จำเป็นต้องย้อนกลับ และจะต้อง replay ตามลำดับที่ถูกต้องก็ต่อเมื่อเซิร์ฟเวอร์มีการเปลี่ยนแปลงinsmovที่เราไม่รู้ ในขณะเดียวกันเราก็ส่งinsmovใหม่ไปเท่านั้น กรณีนี้อาจเกิดขึ้นได้เมื่อกลับมาเชื่อมต่อ Wi‑Fi หลังจากไฟลต์ยาว ๆ แต่ในกรณีที่ออนไลน์อยู่และรับ push แบบเรียลไทม์ผ่าน WebSocket จะพบได้น้อยกว่า และไม่จำเป็นสำหรับ operation ที่ไม่ใช่insmovเช่นการอัปเดตข้อความ[1] https://thymer.com
เช่น เป็นรูปแบบที่ใช้ลำดับของเซิร์ฟเวอร์แทน Lamport timestamp
[1] https://inria.hal.science/inria-00555588/
พอลองค้นหา Thymer ใน HN ก็เจอ Show HN [1] ตั้งแต่ปี 2009 และดูเหมือนว่า Thymer จะอยู่ใน private beta มาตลอด 15 ปี ที่ผ่านมา
0. https://news.ycombinator.com/item?id=40786425
ต้องอ่านบทความนี้ให้ได้เลย ในงานลูกค้าฟรีแลนซ์ ผมเปิดซอร์ส React Table Library [0] และโฟกัสไปที่ operation กับ tree
พวกเขาจัดการโครงสร้าง tree ของโฟลเดอร์/ไฟล์ระดับ 100,000 node โดยรองรับการย้ายโฟลเดอร์และไฟล์ การทำสำเนา lazy loading ทั้งระดับบนสุดและระดับซ้อนกัน ทั้งหมดอยู่ในโครงสร้าง table เดียวกัน พอทำโปรเจกต์เสร็จแล้ว ก็พอเข้าใจว่าทำไม Google Drive ถึงอนุญาตให้แสดงและแก้ไขได้เฉพาะในระดับ hierarchy เดียวกันเท่านั้น การทำสิ่งนี้ในมุมมองแบบซ้อนที่มี node จำนวนมากมีข้อจำกัดที่ต้องพิจารณามากเกินไป
[0] https://react-table-library.com/
อยากขอคำแนะนำ แม้จะไม่ใช่แอป multiplayer แต่ใน frontend มี denormalized tree ขนาดใหญ่ที่เชื่อมโยงกันหลายชุด ใช้เป็นโปรไฟล์ผู้ใช้
ลองนึกถึง layout แบบ tile ที่ผู้ใช้เพิ่ม/ลบ/ปรับขนาด tile ได้ เพิ่มหลาย component ลงในแต่ละ slot ของ tile และ component เหล่านั้นก็มีโปรไฟล์ของตัวเองได้ด้วย อาจมีหลาย layout ที่มีการจัดเรียง tile ต่างกัน และยังมีความซับซ้อนที่ tile บางตัวอ้างอิงหรือแชร์ส่วนอื่นของ global state
การอัปเดตอย่างปลอดภัยด้วย REST ทั่วไปทำได้ยาก เพราะต้องรับประกันว่าเมื่อผู้ใช้คนเดียวกันเปิดสองแท็บ แล้วอัปเดตจากแท็บ 1 จากนั้นอัปเดตอีกครั้งจากแท็บ 2 โปรไฟล์ทั้งหมดจะไม่กลายเป็นสถานะที่ไม่ถูกต้อง โดยรวมแล้วลำดับก็สำคัญด้วย ถ้าเซิร์ฟเวอร์ข้าม update ที่ไคลเอนต์ apply ไปถูกต้องแล้ว ก็อาจพังได้
วิธีแก้แบบง่ายมากที่ใช้คือส่งข้อมูลขั้นต่ำที่สามารถเขียนทับ state ชิ้นหนึ่งได้ทั้งหมด แล้วใส่ไว้ท้ายคิว โดยปกติก็โอเค แต่บางครั้งก็สิ้นเปลือง เช่นการเปลี่ยนแปลงจริงมีแค่ไม่กี่ไบต์ แต่ต้องส่ง 50KB
โดยทั่วไปไม่ได้มีเหตุผลแบบที่จำเป็นต้องใช้ CRDT แต่แม้จะเป็นผู้ใช้คนเดียว ก็รู้สึกว่าน่าจะทำให้การจัดการ state ง่ายขึ้นมาก อย่างแรกคือซิงก์ระหว่างแท็บเบราว์เซอร์ของผู้ใช้ได้ และที่สำคัญกว่านั้นคือสามารถเชื่อได้ว่าเมื่อเพียงแค่แก้ไข state ฝั่ง frontend แล้ว CRDT จะประสานกับเซิร์ฟเวอร์ให้อย่างเหมาะสม ไม่ต้องจัดการเองอีกต่อไป อยากรู้ว่าสิ่งนี้สมเหตุสมผลไหม หรือในสถานการณ์ที่ไม่ต้องการ multiplayer และ local-first overhead ของการใส่อะไรอย่าง Yjs เข้าไปจะไม่คุ้มค่า
อย่างไรก็ตาม ถ้าการแก้ไขโปรไฟล์เป็นของผู้ใช้คนเดียวล้วน ๆ การนำ CRDT มาใช้อาจเกินจำเป็น จากที่เห็น สถานการณ์เปิดสองแท็บน่าจะเป็นแหล่งบั๊กที่ใหญ่ที่สุด ดังนั้นอาจใช้
BroadcastChannelเพื่อแจ้ง event การอัปเดตไปยังแท็บอื่นทั้งหมดได้วิธีรักษา shared state ด้วย REST call ที่เขียนทับบางส่วนของ state บนเซิร์ฟเวอร์นั้นเปราะบางจริง ๆ และเหมาะแค่กับการเขียนทับ field ใน data record แบบแบนเท่านั้น อีกทั้งยังต้องพิจารณาการประสาน state ระหว่างเซิร์ฟเวอร์กับไคลเอนต์อย่างระมัดระวังเสมอ และในเส้นทางที่ไม่ใช่ flow ปกติ ก็ซิงก์หลุดได้ง่าย
อย่างที่พูดไว้ หากสร้าง CRDT ที่ระบุวิธีรวม update เข้าด้วยกัน ก็จะลด ภาระทางความคิด ลงได้มาก
ในคอนเทนต์ข้อความแบบมีรูปแบบอย่าง Google Docs หรือ Zoho Writer งานอย่างการย้ายรายการในลิสต์ลงด้านล่างหรือเพิ่มคอลัมน์ใหม่ รวมถึงการดำเนินการกับตาราง/ลิสต์ โดยเนื้อแท้แล้วเป็น การดำเนินการปรับแต่งทรี
การชนกันพร้อมกันในกรณีแบบนี้ขึ้นชื่อว่าทำให้ลู่เข้าหากันได้ยาก หากไม่มีการจัดการเฉพาะตามบริบท [1] เลยสงสัยว่าการทำงานแบบนี้ให้คำตอบที่ใช้ทั่วไปกับกรณีใช้งานเหล่านั้นได้หรือไม่
อาจใช้ list หรือ string CRDT กับ leaf node คือบล็อกข้อความ แล้วผสม tree CRDT นี้กับโหนดโครงสร้างอย่างลิสต์และตารางได้ แต่ถ้าอย่างนั้นก็ต้องแนบแอดเดรส 2 มิติ
(parent-id, index_offset_into_that_parent)ไปกับทุกการดำเนินการ[1] https://github.com/inkandswitch/peritext/issues/27
โดยพื้นฐานแล้ว text CRDT ก็เป็นเพียง list CRDT ที่เก็บข้อมูลอักขระ ดังนั้นองค์ประกอบที่ฝังไว้จึงโมเดลได้ง่าย ๆ เป็นรายการพิเศษขนาด 1 เหมือนรายการอื่นในสตริง กล่าวคือเป็นโหนดลูกที่ฝังอยู่ หากใช้แนวทางที่ถูกต้อง ก็สามารถผสม CRDT ต่างชนิดกันภายในทรีได้ตามต้องการ เช่น มีตารางอยู่ในริชเท็กซ์ และในเซลล์หนึ่งของตารางนั้นมีรูปภาพอยู่
การต้องใส่ฟิลด์
parent-crdt-idในทุกการดำเนินการเป็นเรื่องน่าเสียดาย แต่ดูเหมือนหลีกเลี่ยงได้ยาก โชคดีที่ในกรณีใช้งานจริงส่วนใหญ่ การดำเนินการต่อเนื่องมักจะแชร์ parent CRDT เดียวกันอยู่บ่อยมาก ดังนั้นฟิลด์ ID แบบนี้น่าจะบีบอัดได้ดีด้วย run-length encodingอย่างไรก็ตาม อย่างที่ Seph พูดไว้ การดำเนินการต่อเนื่องภายใต้ parent เดียวกันสามารถบีบอัดได้อย่างมีประสิทธิภาพ ดังนั้น overhead แบบ amortized ของ parent ID เหล่านี้โดยทั่วไปจึงไม่มาก
สงสัยว่าเคยมี CRDT ที่ใช้งานได้จริงสำหรับแอปพลิเคชันที่มีความหนาแน่นของข้อมูลสูงอย่างพิกเซลของรูปภาพหรือ โมเดล 3D หรือไม่
แม้การแทนเอกสารที่เป็นรูปธรรมจะมีข้อมูลหนาแน่น แต่วิธีเข้ารหัสการแก้ไขและการดำเนินการแต่ละอย่างของผู้ใช้ก็ยังอาจมีขนาดเล็กได้
สมมติว่ากำลังสร้างโปรแกรมแก้ไขภาพอย่าง Photoshop ภาพไม่บีบอัดความละเอียด 102 ล้านพิกเซลที่ความลึกสี 16 บิตต่อ channel เช่นภาพจาก Fujifilm GFX100 จะมีขนาดราว 610MB ในรูปแบบ TIFF หากแทนแต่ละพิกเซลเป็น last-write-wins register แยกกัน overhead จะสูงมาก แต่การแทนแบบนั้นไม่เหมาะกับการรักษาเจตนาของผู้ใช้จริง ๆ สิ่งที่ผู้ใช้จะแก้ไขคือประมาณ “เพิ่ม contrast ของภาพ 15%” หรือ “ใช้ brush Q และสี #000 ระบาย spline [(0,0), (1500, 1500)]” หากซิงก์แต่ละพิกเซลด้วย Lamport timestamp การเปลี่ยน contrast ของผู้ใช้ 1 จะถูกนำไปใช้กับทุกพิกเซล ยกเว้นพิกเซลที่ผู้ใช้ 2 ระบาย ทำให้พิกเซลที่ถูกระบายทับอาจดูแปลก
แทนที่จะทำอย่างนั้น ควรแทนเจตนาของผู้ใช้เป็น รายการการดำเนินการแก้ไข มากกว่า ซึ่งมีขนาดเล็กกว่ากริดพิกเซลทั้ง 102MB มาก โครงสร้างข้อมูล CRDT เป็นหนึ่งในกลไกทางเทคนิคที่เป็นไปได้สำหรับซิงก์เจตนาของผู้ใช้แบบนั้น แต่ควรเลือกโครงสร้างให้ตรงกับ semantics ของเจตนาผู้ใช้ ไม่ใช่ layout ข้อมูลรูปธรรมของ output
ถึงอย่างนั้นก็อาจมีการดำเนินการแก้ไขที่มีข้อมูลปริมาณมาก เช่น
"add new layer namedbgbelow layerfgwith pixelsdata:(10mb of pixels)at (1500, 1500)"แต่ overhead ในการซิงก์คำสั่งแก้ไขแบบนี้ต่ำมาก และขนาดเป็น O(1) ไม่ใช่ O(pixels) ที่แปรผันตามจำนวนพิกเซลในคำสั่งแก้ไขโมเดล 3D เป็นอีกปัญหาหนึ่ง และยังไม่เคยเห็นเครื่องมือทำโมเดล 3D แบบทำงานร่วมกันในตลาด ไม่ใช่ว่าเคยค้นหาอย่างจริงจังนะ
ยังไม่เคยลองสร้างเอง และก็ไม่มั่นใจว่ามันจะใช้งานได้จริงหรือไม่ แต่ถึงอย่างน้อยก็สามารถเก็บประวัติทั้งหมดของเอกสารไว้ได้
มันใช้ Yjs เพื่อแทนข้อมูล แต่แทนที่จะเก็บพิกเซลดิบ ก็เก็บประวัติทั้งหมดของการแปลง
https://digest.browsertech.com/archive/browsertech-digest-ho...
สงสัยว่าบทความนี้ตรวจด้วย GPT หรือเปล่า ย่อหน้าแรกให้กลิ่น สำนวนแบบ ChatGPT ชัดมาก
This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes.