CRDT ที่เร็วขึ้นกว่าเดิม (2021)

 (josephg.com)
3 คะแนน โดย GN⁺ 2024-08-28 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

CRDT ที่เร็วขึ้น 5000 เท่า: การผจญภัยแห่งการปรับแต่งประสิทธิภาพ

บทนำ

  • เมื่อหลายปีก่อน นักวิจัยชาวฝรั่งเศสได้เผยแพร่บทความวิชาการที่เปรียบเทียบอัลกอริทึมสำหรับการแก้ไขงานร่วมกันแบบเรียลไทม์
  • พวกเขาได้ติดตั้งใช้งานอัลกอริทึมหลายแบบและทำเบนช์มาร์กประสิทธิภาพ
  • อัลกอริทึมบางตัวใช้เวลามากกว่า 3 วินาทีกับการวางข้อความแบบง่าย ๆ ครั้งเดียว
  • อัลกอริทึมที่เป็นปัญหาคืออัลกอริทึมที่ ShareJS ใช้งาน

สาเหตุของปัญหา

  • ในบทความวิชาการนั้น การวางข้อความขนาดใหญ่ถูกแยกออกเป็นงานย่อยเดี่ยว 1000 งานเพื่อประมวลผล
  • นี่ไม่ใช่ปัญหาของตัวอัลกอริทึมเอง แต่เป็นปัญหาของการติดตั้งใช้งาน

เสน่ห์ของ CRDT

  • CRDT (Conflict-Free Replicated Data Types) ช่วยให้ผู้ใช้หลายคนแก้ไขข้อมูลพร้อมกันได้
  • สามารถทำงานบนเครื่องตัวเองได้โดยไม่มีความหน่วง และเมื่อซิงก์กันก็รักษาความสอดคล้องได้โดยอัตโนมัติ
  • ทำงานได้แม้ไม่มีเซิร์ฟเวอร์กลาง

ปัญหาของ Automerge

  • Automerge เป็นไลบรารีสำหรับการแก้ไขงานร่วมกัน โดยอิงกับอัลกอริทึม RGA
  • มันจัดการอักขระแต่ละตัวของเอกสารด้วย ID ที่ไม่ซ้ำกัน และระบุรายการแม่เมื่อมีการแทรก
  • ด้วยปัญหาด้านประสิทธิภาพ ทำให้ใช้เวลา 5 นาทีในการประมวลผลงานแก้ไข 260,000 รายการ
  • การใช้หน่วยความจำก็สูงมากเช่นกัน

การปรับแต่งประสิทธิภาพ

  • ปัญหาด้านประสิทธิภาพของ Automerge มีสาเหตุจากโครงสร้างข้อมูลแบบต้นไม้ที่ซับซ้อนและการใช้ Immutablejs
  • Yjs ใช้ลิสต์แบนเพียงชุดเดียว ทำให้ประสิทธิภาพดีขึ้นอย่างมาก
  • Yjs ใช้แคชเพื่อค้นหาตำแหน่งแทรก และใช้ doubly linked list เพื่อจัดการการแทรกได้อย่างมีประสิทธิภาพ
  • Yjs เร็วกว่า 30 เท่าและใช้หน่วยความจำน้อยกว่า

การย้ายไปใช้ Rust

  • Rust ช่วยควบคุม memory layout ได้ จึงสามารถยกระดับประสิทธิภาพได้อีก
  • ด้วยการติดตั้งใช้งาน CRDT แบบใหม่ชื่อ Diamond types จึงทำประสิทธิภาพได้เร็วกว่า Yjs 5 เท่า
  • Diamond ที่เขียนด้วย Rust ประมวลผลงานแก้ไข 260,000 รายการได้ในเวลาเพียง 56 มิลลิวินาที

บทสรุป

  • ด้วยโครงสร้างข้อมูลที่ปรับแต่งมาอย่างดีและการจัดการหน่วยความจำอย่างมีประสิทธิภาพ เราสามารถยกระดับประสิทธิภาพของ CRDT ได้อย่างมาก
  • การใช้ภาษา low-level อย่าง Rust ช่วยให้ไปได้ไกลยิ่งขึ้นในด้านความเร็ว

สรุปโดย GN⁺

  • CRDT คืออนาคตของการแก้ไขงานร่วมกัน และเป็นเครื่องมือทรงพลังที่รักษาความสอดคล้องได้โดยไม่ต้องมีเซิร์ฟเวอร์กลาง
  • ปัญหาด้านประสิทธิภาพของ Automerge มาจากโครงสร้างข้อมูลที่ซับซ้อนและการใช้หน่วยความจำอย่างไม่มีประสิทธิภาพ
  • Yjs และ Diamond types ใช้โครงสร้างข้อมูลที่เรียบง่ายและมีประสิทธิภาพ จึงยกระดับประสิทธิภาพได้อย่างมาก
  • การใช้ภาษา low-level อย่าง Rust สามารถให้ประสิทธิภาพที่เร็วขึ้นได้อีก
  • หากกำลังพัฒนาเครื่องมือสำหรับการแก้ไขงานร่วมกัน Yjs และ Diamond types เป็นตัวเลือกที่น่าพิจารณา

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

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

 
GN⁺ 2024-08-28
ความเห็นจาก Hacker News

  • เหตุผลที่ 32 เอนทรีมีประสิทธิภาพที่สุดคือ cache line มีขนาด 64 ไบต์

    • หากใช้จำนวนเต็ม 2 ไบต์ 32 เอนทรีจะพอดีกับ cache line หนึ่งเส้นพอดี จึงช่วยลดการส่งข้อมูลไปยังหน่วยความจำหลักได้

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

    • Notion เมื่อมีคนสองคนเขียนโน้ตพร้อมกัน ใช้งานได้ด้อยกว่า Google Docs

  • CRDTs ทรงพลัง แต่มีข้อเสียคือทิ้งประวัติของการทำงานย้อนหลังไว้เสมอ (หรือทิ้งองค์ประกอบเก่าไว้)

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

  • คำอ้างอิงจาก GitHub Readme ปัจจุบัน:

    • หลังจากโพสต์บล็อกนั้น ประสิทธิภาพดีขึ้น 10-80 เท่า

  • แม้บทความนี้จะมีเนื้อหาที่ยาก แต่เขียนได้ดีมากจนหยุดอ่านไม่ได้

  • เมื่อเห็นว่ามีการใช้ลำดับชั้น จึงสงสัยว่าทำไมไม่ใช้ nested sets แทน

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

  • เคยเจอโพสต์นี้โดยบังเอิญเมื่อหลายปีก่อน

    • เป็นหนึ่งในโพสต์ที่สนุกที่สุดที่ได้อ่านในช่วงไม่กี่ปีที่ผ่านมา

  • สงสัยว่าทำไม WASM ถึงช้ากว่าการรันแบบเนทีฟ 4 เท่า

    • คิดว่าน่าจะเป็นเพราะงานจัดการสตริงทั้งหมดต้องคัดลอกเข้าไปในหน่วยความจำของ WASM และเมื่อคำนวณผลเสร็จก็ต้องคัดลอกกลับไปที่ JS อีกครั้ง
    • สงสัยว่าอาจเข้าใจบริบทนี้ผิดไปหรือไม่

  • ตอนนี้การทำ Automerge เวอร์ชัน Rust เสร็จสมบูรณ์แล้ว จึงน่าสนใจที่จะได้เห็น benchmark ที่อัปเดต