Movable tree CRDTs และการใช้งานใน Loro

 (loro.dev)
2 คะแนน โดย GN⁺ 2024-07-30 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

  • Movable tree CRDTs and Loro's implementation

  • ภูมิหลัง

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

  • ความขัดแย้งของต้นไม้ที่ย้ายได้

    • การทำงานหลักของต้นไม้ที่ย้ายได้: สร้าง, ลบ, ย้าย
    • ความขัดแย้งที่อาจเกิดขึ้นเมื่อซิงก์การทำงานพร้อมกัน:
      • โหนดเดียวกันถูกลบและถูกย้าย
      • โหนดเดียวกันถูกย้ายไปอยู่ใต้โหนดพาเรนต์คนละตัว
      • โหนดอื่นถูกย้ายจนเกิดวงจร
      • โหนดลูกหลานถูกย้ายขณะที่โหนดบรรพบุรุษถูกลบ
  • การลบและการย้ายของโหนดเดียวกัน
    • แก้ได้ค่อนข้างง่าย
    • เลือกใช้การทำงานอย่างใดอย่างหนึ่งและละเลยอีกอย่างหนึ่งตามทाइम์สแตมป์ของระบบกระจายศูนย์หรือข้อกำหนดเฉพาะของแอปพลิเคชัน
  • ย้ายโหนดเดียวกันไปอยู่ใต้พาเรนต์คนละตัว
    • การรวมการย้ายที่เกิดพร้อมกันมีความซับซ้อนมากกว่า
    • สามารถใช้แนวทางได้หลากหลายตามลักษณะของแอปพลิเคชัน:
      • ลบโหนดแล้วสร้างสำเนาไว้ใต้โหนดพาเรนต์อีกตัว
      • อนุญาตให้โหนดเชื่อมกับพาเรนต์สองตัว (โดยทั่วไปไม่อนุญาต)
      • จัดเรียงการทำงานทั้งหมดแล้วนำไปใช้ตามลำดับ
  • การเกิดวงจรจากการย้ายของโหนดอื่น
    • การแก้ปัญหาวงจรที่เกิดจากการย้ายพร้อมกันมีความซับซ้อน
    • มีหลายวิธี:
      • แจ้งข้อผิดพลาด
      • แสดงโหนดที่เป็นวงจรในพื้นที่ "timeout" พิเศษ
      • ให้เซิร์ฟเวอร์จัดการการย้าย
      • ใช้การจัดเรียงเชิงทอพอโลยี
      • ซ่อน edge ที่ทำให้เกิดวงจร
  • การลบโหนดบรรพบุรุษและการย้ายโหนดลูกหลาน
    • การย้ายโหนดลูกหลานขณะลบโหนดบรรพบุรุษเป็นกรณีที่มักถูกมองข้ามได้ง่าย
    • หากลบโหนดลูกหลานทั้งหมดโดยตรง ผู้ใช้อาจเข้าใจว่าเป็นการสูญหายของข้อมูล

  • วิธีจัดการความขัดแย้งของแอปพลิเคชันยอดนิยม

    • Dropbox: เคยจัดการการย้ายไฟล์เป็นการลบแล้วสร้างใหม่ แต่มีความเสี่ยงต่อการสูญหายของข้อมูล
    • Figma: เซิร์ฟเวอร์กลางตรวจจับวงจรและปฏิเสธการทำงานเพื่อรักษาความสอดคล้อง

  • Movable tree CRDTs

    • ใช้ CRDTs แทนโซลูชันแบบรวมศูนย์
    • อัลกอริทึมยุคแรกที่อิง CRDT นั้นนำไปใช้งานได้ยากและมี overhead ด้านการจัดเก็บสูง
    • จากการปรับปรุงอย่างต่อเนื่อง ทำให้อัลกอริทึมซิงก์ต้นไม้แบบ CRDT บางส่วนเหมาะกับการใช้งานจริงใน production

  • การย้ายที่มีความพร้อมใช้งานสูงสำหรับต้นไม้ที่ทำซ้ำ

    • รวมการทำงานสามอย่างของต้นไม้ (สร้าง, ลบ, ย้าย) ให้เป็นการทำงานแบบย้าย
    • การย้ายถูกนิยามเป็น Move t p m c
    • การลบโหนดจัดการโดยย้ายไปยังโหนด TRASH
  • ทाइम์สแตมป์เชิงตรรกะที่จัดเรียงแบบสากล
    • ใช้ Lamport timestamp เพื่อกำหนดลำดับเชิงเหตุและผลของเหตุการณ์ในระบบกระจายศูนย์
    • ตัวเลขที่น้อยกว่าหมายถึงเหตุการณ์ที่เกิดก่อน
  • การใช้การทำงานจากระยะไกล
    • ความปลอดภัยของการทำงานขึ้นอยู่กับสถานะของต้นไม้ในขณะนำไปใช้
    • เมื่อจัดการอัปเดตจากระยะไกล จะย้อนการทำงานล่าสุด แทรกการทำงานใหม่ แล้วจึงนำการทำงานที่ย้อนกลับไปใช้ใหม่อีกครั้ง

  • CRDT: ลำดับชั้นต้นไม้แบบเปลี่ยนแปลงได้

    • แต่ละโหนดติดตามโหนดพาเรนต์ทั้งหมดในประวัติและกำหนดตัวนับให้
    • หากเกิดวงจรระหว่างการซิงก์ จะเชื่อมต่อกลับไปยังโหนดพาเรนต์ในประวัติที่ใกล้ที่สุด

  • การใช้งาน Movable tree CRDTs ใน Loro

    • นำอัลกอริทึมของ Martin Kleppmann มาใช้เพื่อให้ได้ประสิทธิภาพสูง
    • ผสานอัลกอริทึม Fractional Index เพื่อจัดลำดับโหนดลูกได้

  • ความขัดแย้งที่อาจเกิดขึ้นในการจัดลำดับโหนดลูก

    • เมื่อแทรกหลายโหนดในตำแหน่งเดียวกัน อาจได้รับ Fractional Index เดียวกัน
    • ใช้ PeerID เพื่อพิจารณาลำดับสัมพัทธ์ของรายการที่มี Fractional Index เดียวกัน

  • การใช้งานและขนาดการเข้ารหัส

    • Fractional Index ใช้กำหนดลำดับของโหนด
    • ขนาดการเข้ารหัสอาจต้องใช้ไบต์เพิ่มเติมในกรณีเลวร้ายที่สุด แต่เกิดขึ้นไม่บ่อย

  • งานที่เกี่ยวข้อง

    • นอกจาก Fractional Index แล้ว ยังมี movable list CRDT ด้วย
    • Fractional Index นำไปใช้ได้ง่ายและมีประโยชน์เมื่อจำเป็นต้องใช้เพียงลำดับสัมพัทธ์

  • Benchmark

    • มีการทดสอบ benchmark ประสิทธิภาพของการใช้งาน movable tree ของ Loro
    • สามารถรองรับการทำงานร่วมกันแบบเรียลไทม์และการ checkout เวอร์ชันย้อนหลังได้อย่างราบรื่น

  • สรุป

    • แนะนำความยากของการใช้งาน Movable tree CRDTs และอัลกอริทึมใหม่สองแบบ
    • Loro ผสานอัลกอริทึมของ Martin Kleppmann กับ Fractional Index เพื่อตอบโจทย์สถานการณ์การใช้งานของแอปพลิเคชันที่หลากหลาย

  • สรุปของ GN⁺

    • Movable tree CRDTs มีบทบาทสำคัญในการจัดการโครงสร้างข้อมูลแบบลำดับชั้นในระบบกระจายศูนย์
    • Loro มอบประสิทธิภาพสูงและการแก้ความขัดแย้งอย่างมีประสิทธิภาพ จึงเหมาะกับแอปพลิเคชันทำงานร่วมกันแบบเรียลไทม์
    • ใช้ Fractional Index เพื่อแก้ปัญหาการจัดลำดับโหนดลูก
    • โปรเจกต์อื่นที่มีความสามารถคล้ายกัน ได้แก่ Figma และ Dropbox

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

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

 
GN⁺ 2024-07-30
ความคิดเห็นบน Hacker News

  • กำลังพัฒนาเอดิเตอร์แบบหลายผู้เล่นตัวใหม่

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

  • เปิดซอร์ส React Table Library

    • จัดการโครงสร้างต้นไม้แบบโฟลเดอร์/ไฟล์
    • รองรับการย้ายโฟลเดอร์/ไฟล์ การคัดลอก และ lazy loading เป็นต้น
    • ทำให้เข้าใจว่าทำไม Google Drive จึงแสดงและแก้ไขได้เฉพาะในระดับชั้นเดียวกัน

  • ขอคำแนะนำ

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

  • เมื่อต้องทำงานกับเนื้อหาข้อความที่มีการจัดรูปแบบ เช่น Google Docs/Zoho Writer จำเป็นต้องมีการจัดการต้นไม้

    • แก้ปัญหาความขัดแย้งพร้อมกันได้ยาก
    • ดูเหมือนว่าสามารถรวม list CRDT กับ tree CRDT ได้
    • ต้องเพิ่มที่อยู่แบบสองมิติให้กับทุกการทำงาน

  • สงสัยว่ามี CRDT ที่ใช้งานได้จริงสำหรับแอปพลิเคชันที่ข้อมูลหนาแน่น เช่น รูปภาพ (พิกเซล) และโมเดล 3D หรือไม่

  • คิดว่าย่อหน้าแรกให้อารมณ์เหมือนเสียงของ ChatGPT