เส้นทางการปรับแต่งที่ทำให้ CRDT เร็วขึ้น 5,000 เท่า (2021)

 (josephg.com)
3 คะแนน โดย GN⁺ 2024-08-28 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • การประเมินว่า CRDT ช้าในการแก้ไขแบบร่วมกัน มักเป็นผลจากการตัดสินโดยปะปนระหว่าง ตัวอัลกอริทึมเอง กับ วิธีการ implement และประสิทธิภาพอาจต่างกันมากได้เพียงแค่โครงสร้างข้อมูลและการจัดวางหน่วยความจำ
  • Automerge v1.0.0-preview2 ใช้เวลา 291 วินาที และ RAM 880MB ในการประมวลผลการติดตามการแก้ไข 260,000 รายการ ขณะที่ Diamond types native ทำงานเดียวกันได้ใน 56ms และ RAM 1.1MB
  • Yjs ใช้ ลิสต์แบบแบน แทน tree รวมถึง location cache, doubly linked list และการจัดเก็บ span เพื่อลดการติดตามเดียวกันเหลือ 0.97 วินาที และ RAM 3.3MB
  • Diamond types ใช้โครงสร้างที่อิง range tree/B-tree ใน Rust เพื่อจัดการการค้นหาตำแหน่ง·การแทรก·การลบในเวลา log(n) และแม้บน WebAssembly ก็ทำได้ 193ms ตามเกณฑ์ของ Node.js
  • benchmark นี้ดูเฉพาะการ replay การแก้ไขในเครื่องของผู้ใช้คนเดียวและปริมาณการใช้ RAM เท่านั้น ดังนั้นในการเลือกใช้จริง ต้องพิจารณาเวลาในการ save/load, ขนาดบน network/disk, binary encoding, protocol, presence และ editor binding ร่วมด้วย

อัลกอริทึมและประสิทธิภาพของ implementation เป็นคนละเรื่องกัน

  • งานเปรียบเทียบเชิงวิชาการชิ้นหนึ่ง implement การแก้ไขร่วมกันแบบเรียลไทม์อย่าง Google Docs ด้วย CRDT และอัลกอริทึม OT หลายแบบแล้ว benchmark พบว่าอัลกอริทึมบางแบบใช้เวลามากกว่า 3 วินาทีในการประมวลผล paste แบบง่าย ๆ
  • วิธีที่ช้าคืออัลกอริทึมที่ใช้ใน ShareJS และ Google Wave แต่ implementation นั้นแยก paste 1000 ตัวอักษรออกเป็น operation แยกกัน 1000 รายการเพื่อประมวลผล
  • กรณีนี้แสดงให้เห็นว่าควรแยกดู พฤติกรรมการแก้ไขพร้อมกัน กับ วิธีการ implement
    • พฤติกรรมหมายถึงเมื่อมีการแก้ไขพร้อมกันเข้ามาในบริเวณเดียวกัน จะ merge กันด้วยลำดับและกฎแบบใด
    • implementation รวมถึงภาษาโปรแกรม โครงสร้างข้อมูล และระดับการ optimization
  • แม้แต่ฟังก์ชัน text OT transform เดียวกัน ใน JavaScript รันได้ราว 100,000 ครั้งต่อวินาที ส่วนใน C รันได้ 20M ครั้งต่อวินาที ทำให้ต่างกันประมาณ 200 เท่า
  • implementation ที่ช้าเพียงตัวเดียวไม่ใช่หลักฐานว่า implementation ทั้งหมดของระบบนั้นจะช้า และสามารถมี implementation ที่เร็วกว่าได้

โมเดลพื้นฐานของ CRDT และ Automerge

  • CRDT ช่วยให้ผู้ใช้หลายคนแก้ไขข้อมูลเดียวกันพร้อมกันได้ ทำงานในเครื่องได้โดยไม่มี latency แล้วค่อย synchronize ภายหลังจนถึง eventual consistency
  • Automerge เป็นไลบรารีแก้ไขร่วมกันที่สร้างโดย Martin Kleppmann และอิงอัลกอริทึม RGA
  • CRDT อย่าง Automerge และ Yjs มองเอกสารร่วมเป็นลิสต์ของตัวอักษร และกำหนด ID เฉพาะให้แต่ละตัวอักษร
    • หากพิมพ์ abc ลงในเอกสารว่าง จะได้ ID เช่น (seph, 0), (seph, 1), (seph, 2)
    • ตัวอักษรใหม่จะบันทึกไว้ด้วยว่า “ถูกแทรกหลัง item ใด”
  • Automerge/RGA เพิ่ม sequence number ให้แต่ละ item
    • item ใหม่จะได้รับค่าที่มากกว่า sequence number สูงสุดที่เคยเห็นจนถึงตอนนั้นอยู่ 1
    • หากมี child item หลายรายการ จะเรียงตาม sequence number จากมากไปน้อย และถ้าเท่ากันจะเรียงตาม agent ID
  • พฤติกรรมของ Automerge/RGA มองได้เป็นสามขั้นตอน
    • เชื่อมแต่ละ item เข้ากับ parent เพื่อสร้าง tree
    • item ที่มี child หลายรายการจะถูกเรียงด้วย sequence number และ ID
    • flatten tree ด้วย depth-first traversal เพื่อสร้างลิสต์สุดท้ายหรือเอกสารข้อความ

Benchmark และคอขวดของ Automerge

  • benchmark ใช้ trace การแก้ไขจาก automerge-perf
    • เป็น trace ที่บันทึกเนื้อหาที่ Martin Kleppmann พิมพ์บทความวิชาการในระดับตัวอักษร
    • trace มี การแก้ไข 260,000 รายการ และขนาดเอกสารสุดท้ายประมาณ 100,000 ตัวอักษร
    • ไม่รวมการแก้ไขพร้อมกัน
    • การทดสอบวัดเฉพาะเวลาที่ใช้ในการ apply trace ในเครื่อง
    • สภาพแวดล้อมคือเวิร์กสเตชัน Ryzen 5800x, Nodejs v16.1, Rust 1.52
  • Automerge v1.0.0-preview2 ใช้เวลา 291 วินาที ในการประมวลผล trace นี้ และเมื่อเสร็จใช้ RAM 880MB
    • เท่ากับใช้ RAM ราว 10KB ต่อการกดคีย์หนึ่งครั้ง
    • RAM สูงสุดคือ 2.6GB
    • ใน spike ที่ช้า การประมวลผลการแก้ไขรายการเดียวใช้เวลา 1.8 วินาที
  • baseline ที่ splice โดยตรงกับสตริง JavaScript ประมวลผลการแก้ไขเดียวกันได้ใน 0.61 วินาที และ RAM 0.1MB แต่เป็น baseline เพื่อเปรียบเทียบที่ทิ้งข้อมูลทั้งหมดซึ่งจำเป็นต่อการแก้ไขร่วมกัน
  • เหตุผลด้าน implementation หลายอย่างที่ทำให้ Automerge ช้า
    • เมื่อเอกสารใหญ่ขึ้น โครงสร้างข้อมูลแบบ tree จะใหญ่และช้าลง
    • ใช้ Immutablejs มาก ทำให้ V8 optimizer และ GC optimization ได้ยาก
    • ปฏิบัติกับตัวอักษรแต่ละตัวที่แทรกเป็น item แยกกัน ทำให้ paste ถูกประมวลผลเป็น item จำนวนมากด้วย
  • ทีม Automerge กำลังทำงานกับ implementation ทางเลือกที่ใช้ automerge-rs ซึ่งเป็น implementation ใน Rust ผ่าน WASM
    • ตาม master branch ในตอนนั้น ประสิทธิภาพเฉลี่ยของการทดสอบนี้ยังไม่เร็วขึ้น แต่การใช้หน่วยความจำลดลงครึ่งหนึ่ง และความผันผวนของประสิทธิภาพนุ่มนวลขึ้น

Implementation แบบลิสต์แบนสไตล์ Yjs

  • Yjs เป็น implementation CRDT แบบโอเพนซอร์สที่สร้างโดย Kevin Jahns และเก็บ item ทั้งหมดไว้ใน ลิสต์แบนเดียว แทน tree
  • การเข้าถึงแบบลิสต์แบนคือการสแกนจากหลัง parent ของ item ใหม่เพื่อหาตำแหน่งแทรก เป็นรูปแบบการ implement list CRDT ด้วยลิสต์
  • reference-crdts สำหรับทดลอง implement YATA ของ Yjs และ RGA ของ Automerge ด้วยวิธีเดียวกัน
    • ฟังก์ชัน insert ประมวลผลพฤติกรรมของ Yjs และ Automerge ด้วย codepath แทบเดียวกัน ยกเว้นความต่างเล็กน้อยบางอย่าง
    • ตรวจสอบความเท่าเทียมเชิงความหมายด้วย fuzzer
  • ข้อดีของวิธีนี้มีสามอย่าง
    • ใช้ flat array แทน tree ที่ไม่สมดุล จึงเล็กกว่าและเร็วกว่า
    • โค้ดเรียบง่าย
    • ใช้ได้กับ list CRDT หลายแบบ เช่น Yjs, Automerge, Sync9
  • ในเชิงทฤษฎี หากมีการแทรกพร้อมกันจำนวนมากที่ตำแหน่งเดียวกัน อาจช้าลงได้ แต่ในการแก้ไขจริง ส่วนใหญ่จะแทรกถัดจาก parent ทันที
  • implementation ของ reference-crdts เร็วกว่า Automerge ประมาณ 10 เท่า และใช้ RAM น้อยกว่าประมาณ 30 เท่า
การทดสอบ เวลาประมวลผล การใช้ RAM
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Plain string edits in JS 0.61s 0.1MB

ลดต้นทุนการสแกนและการแทรก

  • การ implement ด้วย array แบบแบนยังเหลือคอขวดอยู่สองอย่าง
    • ต้องสแกนเอกสารเพื่อหาตำแหน่งที่จะแทรก
    • เมื่อต้องแทรกกลาง array ด้วย doc.content.splice(destIdx, 0, newItem) จะต้องเลื่อนรายการด้านหลัง
  • รายการที่ถูกลบอาจถูกอ้างอิงโดยการแทรกอื่นได้ จึงลบออกจาก array ไม่ได้ และต้องเหลือเครื่องหมายอย่าง isDeleted ไว้
    • แม้เอกสารปัจจุบันจะมี 100,000 อักขระ แต่เมื่อรวมรายการในอดีตแล้ว อาจมี array item 150,000 รายการ
    • หากจะแทรกที่ตำแหน่งเอกสาร 50,000 อาจต้องสแกน item ประมาณ 75,000 รายการโดยข้ามรายการที่ถูกลบไป
  • ในโครงสร้างแบบนี้ เมื่อแทรกลงในเอกสารที่เคยมีรายการ n รายการ จะต้องใช้ประมาณ n ขั้นตอน และถ้าแทรกอักขระ n ตัว ก็จะเป็น O(n²)
  • Yjs แคชคู่ (index, position) ของตำแหน่งแก้ไขล่าสุดให้สอดคล้องกับวิธีที่มนุษย์แก้ไขเอกสาร
    • การแก้ไขถัดไปมีแนวโน้มจะอยู่ใกล้ตำแหน่งแก้ไขก่อนหน้า จึงสแกนไปข้างหน้าหรือถอยหลังเพียงสั้น ๆ
    • เก็บชุดตำแหน่งที่แคชไว้ด้วย เพื่อรองรับกรณีผู้ใช้หลายคนแก้ไขคนละตำแหน่ง
  • Yjs ใช้ ลิงก์ลิสต์สองทาง แทน array ทำให้เมื่อหาตำแหน่งเจอแล้วสามารถแทรกได้ในเวลาคงที่
  • อีกทั้งยังใช้ประโยชน์จากข้อเท็จจริงที่ว่าคนมักพิมพ์อักขระต่อเนื่องกัน โดยเก็บ hello เป็น span เดียว ไม่ใช่รายการอักขระ 5 รายการ
    • จะ collapse ได้ก็ต่อเมื่อ ID และ parent ต่อเนื่องกันตามลำดับเท่านั้น
    • ในชุดข้อมูลนี้ จำนวน array entry ลดจาก 180,000 รายการเหลือ 12,000 รายการ หรือ ลดลง 14 เท่า
การทดสอบ เวลาในการประมวลผล การใช้ RAM
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Yjs v13.5.5 0.97s 3.3MB
Plain string edits in JS 0.61s 0.1MB

แนวทาง range tree ของ Rust และ Diamond types

  • อ็อบเจ็กต์ JavaScript มักกลายเป็นโครงสร้างที่ content, deletion flag, ID, seq, parent ฯลฯ กระจัดกระจายด้วย pointer ทำให้เกิด memory fragmentation และมีต้นทุน cache miss สูง
  • Rust สามารถควบคุมการจัดวางหน่วยความจำได้โดยตรง และใช้งานบนเว็บได้ผ่าน WebAssembly
  • Diamond types เป็น implementation ของ CRDT ที่เขียนด้วย Rust และแทบเหมือนกับ Yjs แต่ภายในใช้ range tree แทนลิงก์ลิสต์
  • range tree ภายในเป็น B-tree ที่ปรับแก้เล็กน้อย
    • แทนที่จะเก็บ key แบบ BTreeMap ทั่วไป โหนดภายในจะเก็บผลรวมจำนวนอักขระที่อยู่ในลูก
    • ประมวลผลการค้นหา การแทรก และการลบที่ตำแหน่งใด ๆ ในเอกสารได้ในเวลา log(n)
  • trace การแก้ไข 260,000 รายการถูกเก็บใน tree นี้ด้วย leaf node ประมาณ 3 ระดับ ทำให้หา item ใด ๆ ได้ด้วยการอ่านหน่วยความจำราว 3 ครั้ง
  • สำหรับการ merge remote edit ยังมี index ขนาดเล็กที่ค้นหา B-tree ด้วย ID ด้วย แต่ codepath ดังกล่าวไม่รวมอยู่ใน benchmark นี้
  • leaf node เก็บบล็อก entry 32 รายการอย่างแน่นหนาใน array ขนาดคงที่
    • ระบุว่า bucket size 32 รายการทำงานได้ดีจากผล benchmark หลายขนาด แต่ไม่ทราบว่าทำไมจึงเหมาะที่สุด
  • เมื่อคอมไพล์ Diamond เป็น WASM ด้วย diamond-js แล้วเรียกจาก Node.js จะประมวลผล trace เดียวกันได้ใน 193ms
    • เร็วกว่า Yjs ประมาณ 5 เท่า
    • เร็วกว่า baseline สตริง JavaScript ประมาณ 3 เท่า
  • การรัน Rust แบบ native บันทึกไว้ที่ 56ms ใน benchmark
    • เร็วกว่า Automerge มากกว่า 5000 เท่า
    • ประมวลผลได้ 4.6M operation ต่อวินาที
    • ระหว่างประมวลผลการแก้ไขทั้งหมด 260,000 รายการ มีการเรียก malloc 1394 ครั้ง
การทดสอบ เวลาในการประมวลผล การใช้ RAM
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Yjs v13.5.5 0.97s 3.3MB
Plain string edits in JS 0.61s 0.1MB
Diamond WASM via Node.js 0.19s ไม่ทราบ
Diamond native 0.056s 1.1MB

การแยก Ropey และ tradeoff

  • การ implement ของ Diamond ไม่ได้ใส่เนื้อหาข้อความของเอกสารลงในรายการ CRDT item โดยตรง แต่เก็บไว้ในโครงสร้างข้อมูลแยกต่างหาก
  • สำหรับเนื้อหาข้อความ ใช้ไลบรารี Rust Ropey และ Ropey เองก็ implement B-tree เพื่อจัดการข้อความด้วย
  • วิธีนี้มี tradeoff ทางวิศวกรรม
    • Ropey ทำ byte packing ที่เฉพาะทางกับข้อความ จึงลดการใช้ RAM ได้
    • ตอนแทรกต้องอัปเดตโครงสร้างข้อมูลสองชุด ทำให้ช้าลงมากกว่า 2 เท่า และ WASM bundle ก็ใหญ่ขึ้นจาก 60KB เป็น 120KB
    • หากเชื่อมกับ editor อย่าง VS Code ตัว editor จะเก็บสำเนาเอกสารไว้เอง ดังนั้นอาจไม่จำเป็นต้องเก็บเนื้อหาเอกสารไว้ในโครงสร้าง CRDT
  • หากประมวลผล trace ด้วย Ropey เพียงอย่างเดียว จะใช้เวลา 29ms
  • เมื่อปิดการอัปเดต document content ใน Diamond native จะบันทึกได้ 23ms และ RAM 0.96MB
    • เร็วกว่า Automerge ประมาณ 14,000 เท่า
    • ประมวลผลได้ 11M operation ต่อวินาที
    • ผลลัพธ์นี้ใกล้เคียงกับการทดลองเพื่อดูขีดจำกัดการประมวลผล CRDT metadata มากกว่าประโยชน์ใช้งานจริง
การทดสอบ เวลาในการประมวลผล การใช้ RAM โครงสร้างข้อมูล
automerge v1.0.0-preview2 291s 880MB naive tree
reference-crdts Automerge/Yjs 31s 28MB array
Yjs v13.5.5 0.97s 3.3MB linked list
Plain string edits in JS 0.61s 0.1MB ไม่มี
Diamond WASM via Node.js 0.20s ไม่ทราบ B-tree
Diamond native 0.056s 1.1MB B-tree
Ropey Rust baseline 0.029s 0.2MB ไม่มี
Diamond native, no doc content 0.023s 0.96MB B-tree

เกณฑ์การเลือกไลบรารีจริง

  • หากกำลังสร้างแอปทำงานร่วมกันบนเอกสารในตอนนี้ การใช้ Yjs จะได้เปรียบกว่า
    • Yjs มีประสิทธิภาพดี ใช้หน่วยความจำน้อย และมี ecosystem สนับสนุนที่ดี
    • Kevin Jahns ยังให้บริการสนับสนุนการ integrate Yjs แบบมีค่าใช้จ่ายด้วย
  • ทีม Automerge ก็จัดให้ประสิทธิภาพเป็นประเด็นสำคัญอันดับแรกในปี 2021 และมีแผนทำให้ Automerge เร็วขึ้นด้วยหลายเทคนิค
  • Diamond เร็วมาก แต่ยังเหลืองานอีกมากกว่าจะมี feature parity ระดับเดียวกับ Yjs และ Automerge
    • ไลบรารี CRDT ต้องมีสิ่งอื่นนอกจากความเร็วของ operation เช่น binary encoding, network protocol, โครงสร้างข้อมูลที่ไม่ใช่ list, presence, editor binding เป็นต้น
  • หากต้องการ semantics แบบฐานข้อมูล ยังไม่รู้จัก implementation ที่ทำได้ดีบน CRDT และสามารถใช้ ShareDB ที่อิง OT ได้
  • Redwood เป็นโปรเจกต์ที่รองรับ P2P editing และมีแผนรองรับ CRDT เต็มรูปแบบ

ข้อจำกัดของวิธีการวัด

  • benchmark นี้วัดเฉพาะ เวลาในการ replay trace การแก้ไขแบบ local และปริมาณการใช้ RAM เท่านั้น
  • input จากผู้ใช้ในเครื่องขอแค่เร็วพอก็พอ และถ้า CRDT ประมวลผล local edit หนึ่งครั้งได้ในประมาณ 1ms หรือน้อยกว่า ความเร็วที่มากกว่านั้นอาจไม่ได้สำคัญมากนัก
    • Automerge เองก็โดยทั่วไปทำได้ในระดับนี้ หากไม่นับ GC pause ที่เกิดขึ้นอย่างโชคร้าย
  • ตัวชี้วัดที่สำคัญกว่าในทางปฏิบัติมีอย่างอื่น
    • จำนวน byte ที่เอกสารกินพื้นที่บนดิสก์หรือบนเครือข่าย
    • เวลาที่ใช้ในการบันทึกและโหลด
    • เวลาที่ใช้ในการอัปเดตเอกสารที่บันทึกไว้ภายในฐานข้อมูล
  • trace ที่ใช้มีเพียงการแก้ไขจากผู้ใช้คนเดียว จึงอาจยังมี pathological case ที่มีการแก้ไขพร้อมกันจำนวนมากหลงเหลืออยู่
  • ปัจจุบัน หากต้องการอัปเดต object เดี่ยวในฐานข้อมูลด้วย Yjs หรือ Automerge โดยทั่วไปต้องโหลดเอกสารทั้งชุดเข้า RAM, แก้ไข แล้วบันทึกเอกสารทั้งชุดกลับไปใหม่ ซึ่งอาจช้าได้
    • Kevin กล่าวว่า หากปรับ Yjs provider อย่างเหมาะสม ก็สามารถ implement ได้ด้วยวิธีที่สมเหตุสมผล
  • list CRDT โดยพื้นฐานจะโตขึ้นเรื่อย ๆ เพราะ tombstone ของรายการที่ถูกลบ และ pruning เป็นแนวทางแยกต่างหาก
    • อัลกอริทึม GC ของ Yjs และ Antimatter ถูกยกเป็นตัวอย่าง
    • pruning เป็นปัญหาที่ตั้งฉากกับการปรับแต่งโครงสร้างข้อมูลที่กล่าวถึงในบทความ

การเปรียบเทียบไม่ใช่การทดลองที่ควบคุมอย่างสมบูรณ์

  • แต่ละขั้นของการปรับแต่งเปลี่ยนหลายตัวแปรพร้อมกัน จึงไม่ได้แยกสาเหตุที่แท้จริงของความเร็วที่เพิ่มขึ้น
  • ตอนเปลี่ยนจาก Automerge ไปเป็น reference-crdts มีหลายองค์ประกอบที่เปลี่ยนไป
    • โครงสร้างข้อมูลหลักเปลี่ยนจาก tree เป็น list
    • Immutablejs ถูกนำออก
    • Automerge frontend/backend protocol และโครงสร้าง Uint8Array หลายส่วนหายไป
    • สไตล์ JavaScript เปลี่ยนจาก functional เป็น imperative
  • ตอนเปลี่ยนจาก reference-crdts ไปเป็น Yjs และจาก Yjs ไปเป็น Diamond ก็ไม่ได้แยกความเปลี่ยนแปลงออกเป็นสาเหตุเดียวเช่นกัน
  • ข้อเท็จจริงที่ว่า automerge-rs ไม่ได้เร็วกว่า Automerge ในการทดสอบนี้ เป็นหลักฐานว่าประสิทธิภาพของ Diamond ไม่ได้มาจาก Rust เพียงอย่างเดียว แต่ไม่สามารถรู้สัดส่วนการมีส่วนร่วมที่แน่ชัดได้
  • การเปรียบเทียบ RGA กับ YATA ด้วยวิธี implement แบบเดียวกันก็อิงสมมติฐานว่า “พฤติกรรมการ merge พร้อมกันโดยแทบจริงแล้วคล้ายกัน และแม้เปลี่ยนพฤติกรรม ประสิทธิภาพของ implementation ก็ยังคงอยู่”
    • ใน reference CRDT implementation พฤติกรรมของ Yjs และ Automerge ใช้ codepath ที่แทบเหมือนกันและมีประสิทธิภาพเท่ากัน
    • ใน trace ที่มี conflict หนัก ๆ อาจมีความต่างด้านประสิทธิภาพได้ แต่ในทางปฏิบัติมองว่าเป็นกรณีที่พบได้น้อยมาก
  • Yjs ไม่ได้บันทึกว่าแต่ละ item ถูกลบเมื่อใด แต่บันทึกเพียงว่าถูกลบหรือไม่
    • ใน Diamond หากบันทึกเวลาที่ถูกลบ ปริมาณการใช้หน่วยความจำจะเพิ่มจาก 1.12MB เป็น 2.34MB และช้าลงประมาณ 5%
    • benchmark ของ Diamond ทั้งหมดในบทความนี้ใช้ yjs-style branch ที่ปรับให้ตรงกับวิธีของ Yjs

โค้ด benchmark และข้อมูลสำหรับ reproduce

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

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

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

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

    • ผมชอบวิธีที่ Knuth ใช้ benchmark โปรแกรมช่วงหลัง ๆ
      โดยพื้นฐานคือใส่ตัวนับเพื่อคอยนับว่าต้องอ่านอะไรจากหน่วยความจำกี่ครั้ง และก็สงสัยว่าเราจะประมาณค่าในทำนองเดียวกันว่า ต้องล้าง cache line กี่ครั้ง ได้ไหม
    • เวลา benchmark ตามขนาด batch มักจะเห็นจุดกระโดดใหญ่ ๆ ที่เกี่ยวกับ ลำดับชั้นหน่วยความจำ
      มักจะเด้งตรงขอบเขตอย่างขนาด word (64 บิต), ขนาดการดึงข้อมูลตามแนว cache alignment (ปกติก็คือ 64 ไบต์ที่พูดถึงข้างบน), ขนาด page ของ OS (4~16KB), ขนาด L1 (ราว 80KB ต่อคอร์), L2 (ระดับหลาย MB)

  • สงสัยว่ามีแอปไหนบ้างที่ใช้ CRDT ในบริการจริงแล้วให้ประสบการณ์ที่ดีมาก
    จำได้ว่า Notion เป็นหนึ่งในนั้น แต่เอาเข้าจริง การที่คนสองคนจดโน้ตร่วมกันใน Notion แทบใช้งานไม่ได้เมื่อเทียบกับ Google Docs

    • Thymer[1] ใช้ CRDT กับทุกอย่าง
      มันเป็น IDE สำหรับงานและการวางแผน เป็นแอปแบบหลายผู้ใช้ รองรับการเข้ารหัสแบบ end-to-end, offline-first และ self-hosting แบบเลือกได้ และเพราะทั้ง workspace เป็นกราฟเดียว CRDT เลยเป็นตัวเลือกที่เป็นธรรมชาติ
      การกระทำทั้งหมดใน Thymer ย่อเหลือเพียง การแปลง CRDT ไม่กี่แบบ การย้าย/คัดลอกข้อความ, เปลี่ยนพร็อพเพอร์ตีของ "frontmatter", ลากการ์ด, อัปโหลดไฟล์, เพิ่มแท็ก ล้วนจัดการด้วย CRDT operation ชุดเล็ก ๆ เดียวกัน
      ช่วงแรกต้องลงแรงมากเพราะทำเองโดยไม่มีไลบรารี แต่ถ้าสถานะแอปเป็นกราฟเดียว ฟีเจอร์อย่างการย้ายข้อความข้ามหน้า, ลิงก์หน้าแบบมี backlink, transclusion ก็ทำได้โดยไม่ต้องกังวลเรื่องการซิงก์ จึงคุ้มค่ามาก
      CRDT รับประกันว่าทุกไคลเอนต์จะลู่เข้าสู่สถานะเดียวกัน และเพราะโดยเนื้อแท้เป็นแบบ append-only จึงได้การจัดการเวอร์ชันตามช่วงเวลาแบบแทบฟรีไปด้วย
      แต่ก็มีการประนีประนอมบางอย่างเพราะเรื่องประสิทธิภาพ ประวัติเวอร์ชันไม่ให้ใช้งานออฟไลน์เพราะข้อมูลเยอะเกินไป และในบางกรณีก็ใช้การแก้ conflict แบบ last writer wins
      โดยรวมแล้วมันคุ้มค่ามาก โดยเฉพาะถ้าออกแบบแอปโดยคำนึงถึง CRDT ตั้งแต่ต้น แต่ถ้าเป็นกรณีเอาฟีเจอร์หลายผู้ใช้ไปแปะเพิ่มทีหลังในแอป AJAX แบบดั้งเดิม ผมคงไม่ใช้ CRDT
      การเปลี่ยนแปลงของ CRDT จะถูกนำไปใช้แบบมองโลกในแง่ดีก่อน แล้วเมื่อได้ลำดับเหตุการณ์ที่เป็น authoritative แล้ว ทุกไคลเอนต์ต้องย้อนกลับไปยังสถานะร่วมล่าสุด แล้ว replay เหตุการณ์ทั้งหมดใหม่ตามลำดับที่ถูกต้อง
      ถ้าออฟไลน์อยู่นาน ก็อาจต้องย้อนและนำการเปลี่ยนแปลงหลายวันกลับมาใช้ใหม่ ผู้ใช้ไม่รู้หรอกว่ามี tree transformation เกิดขึ้นเบื้องหลังมากแค่ไหน แต่ CRDT ส่งผลต่อการออกแบบทั้งแอปพลิเคชัน
      แอปยอดนิยมส่วนใหญ่ในทุกวันนี้ถูกออกแบบมาตั้งแต่ยุคที่การแปลงแบบ CRDT ยังไม่เป็นที่เข้าใจกันดี
      [1] https://thymer.com (เกือบพร้อมเบต้าแล้ว)
    • ปัจจุบัน Notion เป็นระบบ last writer wins ที่มี operation แบบรักษาเจตนา อยู่จำกัดเฉพาะบางส่วน เช่น ลำดับบล็อกของข้อมูลแบบลิสต์
      ตัวข้อความเป็นแบบ last writer wins และข้อความหรือพร็อพเพอร์ตีของแต่ละบล็อกก็เป็น last writer wins register ตอนนี้กำลังทำฟอร์แมต CRDT ใหม่สำหรับข้อความในบล็อก
    • เท่าที่รู้ บริการส่วนใหญ่ของ iCloud ใช้ CRDT ภายใน
      มีทั้ง Notes, Reminders และ Photos ก็อาจใช่ด้วย เคยได้ยินจากอดีต SRE ของ Apple ที่เมาอยู่ในบาร์ว่าบางส่วนของแบ็กเอนด์ก็ใช้ FoundationDB
    • Linear: https://linear.app/
      งานพูดใน Local First Conf ก็น่าดูเหมือนกัน: https://youtu.be/VLgmjzERT08
    • คิดดูอีกทีก็มีอีกตัวอย่างหนึ่งที่คนอาจนึกไม่ถึงทันที
      เกมเครือข่าย ทุกแบบที่มี rollback หรือการแก้ให้ตรงไม่ทางใดก็ทางหนึ่งก็ใกล้เคียงกับสิ่งนี้ มันอาจเป็นรูปแบบของ CRDT ที่ใช้กันแพร่หลายและให้ประสบการณ์ผู้ใช้ดีที่สุดก็ได้ คือใช้แนวทาง best effort และมี rollback เป็นเส้นทางสำรอง
      มันไม่ใช่ CRDT ในความหมายเชิงวิชาการแบบเคร่งครัด เพราะในทางเทคนิคแล้วสถานะเกมไม่ได้ถูกจำลองครบทั้งก้อนไปยังทุกไคลเอนต์ แต่ละไคลเอนต์ได้รับเพียงบางส่วนของสถานะเกมเท่านั้น
      อีกอย่าง ไคลเอนต์เกมต้องการการซิงก์ที่หน่วงต่ำ และในเชิงวิชาการอาจมองสิ่งนี้ว่าเป็น "coordination" ก็ได้ แต่ในทางปฏิบัติ ไคลเอนต์จะยอมรับและเรนเดอร์ผลของอินพุตบนเครื่องตัวเองแบบคาดการณ์ล่วงหน้า ก่อนที่การแก้ conflict หรือการชดเชยจาก rollback จะกลับมา
      คนที่ชอบจับผิดอาจเถียงได้ แต่ถ้าดูถึงตัวอย่างที่สามก็น่าจะเห็นธีมร่วมกัน แอป CRDT ที่ดังที่สุด ใช้งานดีที่สุด และทำออกมาดีที่สุดนั้น จริง ๆ แล้วมัก ทำผิดกฎเชิงวิชาการ
      นี่เป็นกับดักคลาสสิกของกรอบคิดที่เป็นวิชาการเกินไป อัลกอริทึมและชนิดข้อมูลในโลกจริงมักสร้างสรรค์กว่าหนังสือกฎทางวิชาการมาก ตัวอย่างหนึ่งคือ Timsort
      ถ้าคุณกำลังสร้างผลิตภัณฑ์สำหรับผู้ใช้จริง ไม่ใช่เขียนบทความส่งตรวจ ก็ไม่ควรตกหลุมพรางของการออกแบบเกินจำเป็นหรือหลุมพรางแบบวิชาการ ควรเรียนรู้กฎเชิงวิชาการไว้ แต่ตั้งใจแหกมันเมื่อเหมาะสม และแทนที่จะพยายามทำแนวคิดที่นิยามเข้มงวดจนมีประโยชน์เฉพาะในหมู่นักวิชาการให้สมบูรณ์แบบ ก็ควรทำให้มันสร้างคุณค่าและใช้งานได้ดีจริง

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

    • ผู้เขียนเองครับ ผมคุยเรื่องนี้มาหลายครั้ง และฝั่ง CRDT ก็พูดถึงกันบ่อย แต่ในทางปฏิบัติ อย่างน้อยสำหรับการแก้ไขข้อความ โอเวอร์เฮดมันเล็กมากจนไม่น่าจะเป็นปัญหาในโลกจริง
      โปรเจกต์ post-CRDT ของผมอย่าง Diamond Types โดยพื้นฐานแล้วจะโตขึ้นไม่สิ้นสุดเมื่อเวลาผ่านไป แต่โอเวอร์เฮดปกติก็น้อยกว่า 1 ไบต์ต่ออักขระที่พิมพ์ทั้งหมดจนถึงตอนนี้
      ถ้าเปิดใช้การบีบอัด LZ4 กับข้อความที่เก็บไว้ เอกสารที่แก้ไขด้วย Diamond Types มักจะมีขนาดเล็กกว่าสถานะสุดท้ายของเอกสารเสียอีก ทั้งที่เก็บประวัติการแก้ไขทั้งหมดไว้
      ในเชิงเทคนิค ผมรู้หลายวิธีที่จะแก้เรื่องนี้ได้ แต่ก็ยังไม่แน่ใจว่าสำหรับระบบส่วนใหญ่มันเป็น ปัญหาจริง หรือเปล่า
      เคยได้ยินมาว่ามีคนใช้ yjs กับเครื่องมือทำโมเดล 3D แล้วเจอปัญหา เพราะมันสร้างการแก้ไขแบบถาวรทุกครั้งที่เมาส์ขยับทีละพิกเซลระหว่างลากวัตถุ
      สำหรับงานแบบนั้น ผมคิดว่าปกติจะฉลาดกว่าถ้าใช้การแก้ไขแบบชั่วคราว ซึ่งไลบรารี CRDT ส่วนใหญ่ไม่รองรับ
      อีกอย่าง Git ก็มีปัญหาเดียวกัน รีโพซิทอรีจะใหญ่ขึ้นเรื่อย ๆ ตามเวลา และโตเร็วกว่าตอนใช้ไลบรารี CRDT สมัยใหม่เสียอีก แต่ดูเหมือนไม่ค่อยมีใครใส่ใจมากนัก
      แม้ Git จะทำ shallow clone ได้ แต่แทบไม่มีใครทำ ถ้าต้องการ ในฝั่ง CRDT ก็ทำแบบเดียวกันได้เหมือนกัน
    • ถ้าไม่ได้จะสร้างระบบกระจายศูนย์เต็มรูปแบบ ก็สามารถผ่อนข้อจำกัดบางอย่างที่ CRDT ต้องการได้
      ตัวอย่างเช่น ถ้ารับประกันได้ว่าไคลเอนต์ทุกตัวได้รับการเปลี่ยนแปลงหลังวันที่ X แล้ว ก็สามารถทิ้งการดำเนินการก่อนวันนั้นได้อย่างปลอดภัย
    • operation log ทั้งหมดและการ merge แบบกำหนดได้แน่นอน เข้ากันได้ดีกับ immutable block store และอาจมีข้อดีด้านความปลอดภัย ประสิทธิภาพ และต้นทุน
      ผมกำลังสร้าง Fireproof[1] เพื่อใช้ประโยชน์จากงานวิจัยล่าสุดในด้านนี้
      เมื่อทำ immutable data ให้เป็น content-addressed ก็มีข้อดีเพิ่มคือการดำเนินการแต่ละครั้งจะลงเอยเป็น proof หรือ diff ที่รับประกันได้ทางคริปโตกราฟี ซึ่งช่วยบังคับ causal consistency และสร้างการอ้างอิงที่เสถียรไปยัง snapshot ได้
      กล่าวคือ คุณสามารถรันฐานข้อมูลที่ทำงานร่วมกันได้ ใช้งานออฟไลน์ได้ และ merge ได้โดยไม่สูญเสียข้อมูล บน edge หรือในเบราว์เซอร์ พร้อมยังคงมีความสมบูรณ์ของข้อมูลแบบที่ในอดีตคาดหวังจากฐานข้อมูลศูนย์กลางหรือบล็อกเชน
      ตัวอย่างเช่น สามารถใส่ snapshot CID ลงใน PDF สำหรับการลงนามหรือใน smart contract เพื่อขจัดความกำกวมเกี่ยวกับสถานะที่ถูกอ้างอิง
      [1] https://github.com/fireproof-storage/fireproof
    • แนวคิดของ CRDT เองไม่ได้มีข้อกำหนดว่าต้องทิ้ง ร่องรอยของการดำเนินการหรือองค์ประกอบในอดีต ไว้
      ท้ายที่สุดแล้ว แทนที่จะวิจารณ์แบบกว้าง ๆ ถึงชุดกฎทางคณิตศาสตร์ที่ชนิดข้อมูลหรือฐานข้อมูลบางตัวปฏิบัติตาม การวิจารณ์การนำไปใช้จริงแบบเฉพาะเจาะจงน่าจะถูกต้องกว่า
    • ถ้าลบประวัติออกได้ ก็สงสัยว่ากังวลเรื่องอะไรกัน

  • เป็นบทความปี 2021 และดูเหมือนว่าจะรวม implementation ภาษา Rust ของ Automerge ด้วย ดังนั้นถ้าได้เห็นเบนช์มาร์กที่อัปเดตก็น่าจะน่าสนใจ

    • ผู้เขียนเองครับ Yjs ก็มี yrs ที่เขียนใหม่ด้วย Rust เช่นกัน และเร็วกว่าเวอร์ชัน JavaScript มาก
      ผมยังมีแนวทางใหม่อีกแบบที่ต่างออกไปโดยสิ้นเชิงสำหรับแก้ปัญหานี้
      ถ้าอัปเดตเบนช์มาร์กก็คงดีแน่นอน ทุกอย่างเร็วขึ้นหมดแล้ว

  • ผมเข้าใจเนื้อหาได้ไม่มากนัก แต่บทความเขียนดีมากจนเป็นงานเขียนหายากที่อ่านต่อได้ไม่สะดุด

  • นี่คือการอภิปรายที่เกี่ยวข้องก่อนหน้านี้
    https://news.ycombinator.com/item?id=28017204 (3 ปีก่อน, 151 ความเห็น)
    https://news.ycombinator.com/item?id=33903563 (2 ปีก่อน, 22 ความเห็น)
    https://news.ycombinator.com/item?id=41372833 (โพสต์ปัจจุบัน)
    https://news.ycombinator.com/item?id=41373288 (ความเห็นปัจจุบัน)

  • อ้างจาก GitHub Readme[0] ปัจจุบัน ระบุว่าหลังจากโพสต์บล็อกนั้น ประสิทธิภาพก็ดีขึ้นอีก 10–80 เท่า
    [0] https://github.com/josephg/diamond-types

  • น่าจะดีถ้าอธิบายได้ว่า ทำไม CRDT ถึงช้า
    บทความนี้ดูเหมือนจะชี้ให้เห็นอนาคต: https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
    คงดีถ้าเอาสิ่งนี้มาเทียบกับ Y.js หรือ Automerge: https://github.com/canvasxyz/okra-js

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

  • จำได้ลาง ๆ ว่าเคยบังเอิญเจอบทความนี้เมื่อหลายปีก่อน
    เป็นบทความที่สนุกมาก และเป็นหนึ่งในบทความที่ผมชอบที่สุดในช่วงหลายปีที่ผ่านมา

    • จำได้ว่าชื่อเรื่องน่าจะเป็น CRDTs go brrr

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

    • ผู้เขียนเองครับ บทความนี้เขียนไว้เมื่อหลายปีก่อน แต่ถ้าจำไม่ผิด ตอนนั้นผมควบคุมส่วนนั้นไว้แล้ว ดังนั้นปัญหาไม่ได้อยู่ที่ FFI
      ก่อนเริ่มจับเวลา ผมโหลดบันทึกทั้งหมดเข้าไปใน wasm ก่อน แล้วประมวลผลมันในลูปภายในที่เขียนด้วย Rust ซึ่งรันอยู่ในคอนเท็กซ์ของ wasm เอง การเรียก wasm มีแค่ประมาณสองครั้งเท่านั้น
      สาเหตุที่ช้าลง 4 เท่าไม่ใช่ FFI แต่เป็นเพราะโค้ดของอัลกอริทึมเองรันช้ากว่าจริง ๆ 4 เท่า
      ถ้าลองรันเบนช์มาร์กใหม่ตอนนี้ก็น่าจะน่าสนใจ output wasm จากคอมไพเลอร์ก็น่าจะดีขึ้นแล้ว และ runtime ของ wasm ก็น่าจะเร็วขึ้นด้วย น่าจะยังมีโค้ดเบนช์มาร์กเก็บไว้อยู่ที่ไหนสักแห่ง
    • ฟังดูเป็นสาเหตุที่เป็นไปได้
      อีกปัญหาหนึ่งที่เจอบ่อยในพื้นที่อื่นคือเรื่อง มัลติเธรด ยังไม่ใช่เรื่องง่าย และการรองรับจากไลบรารีกับเครื่องมือก็ยังไม่สมบูรณ์
      ผมเคยลองรัน game engine หรือยูทิลิตีไบนารีอย่าง ffmpeg กับ zip บนเบราว์เซอร์ ซึ่งก็ช้ามากเพราะเรื่องนี้
    • ดูเหมือนว่าคำถามที่ดีกว่าคือ ทำไมถึงคาดหวังว่าทั้งสองอย่างจะต้องเท่ากัน
      ผมไม่เคยทำงานกับ WASM interpreter หรือ JIT โดยตรง แต่มีกรณีบ่อยแค่ไหนที่การผ่านหลายชั้นจะดีกว่าผ่านชั้นแปลเพียงชั้นเดียว?
      เมื่อแปลโค้ดระดับสูงไปเป็น WASM หรือภาษาแอสเซมบลีบางอย่าง เจตนา จำนวนมากที่อยู่ในโค้ดระดับสูงจะหายไป
      ในโค้ดระดับต่ำ เรามักเห็นการเรียงกันของสำนวนเฉพาะภาษาที่ใช้เพื่อให้บรรลุเป้าหมาย ซึ่งบางอย่างอาจตรงกับเครื่องจริงโดยตรง หรืออาจไม่ตรงก็ได้
      x86-64 สมัยใหม่มีคำสั่งที่ทรงพลังกว่าสิ่งที่ WASM ทำได้อยู่มาก
      แน่นอนว่าก็มี decompiler อยู่ และอาจมีรายการของ macro-op fusion ที่ทำให้ WASM JIT สร้างโค้ดเนทีฟที่ดีได้ด้วยการจับแพตเทิร์นที่ค่อนข้างเรียบง่าย อาจจะไม่ใช่แบบนั้น และการทำ optimization ข้ามแพลตฟอร์มก็น่าจะยากกว่า
      LLVM เองก็ไม่สมบูรณ์แบบ ดังนั้นย่อมมีจุดง่าย ๆ ที่ตัว optimizer หลังการประมวลผลสามารถปรับปรุงได้ ดังนั้นในทางทฤษฎี การทำให้ WASM เร็วกว่าผลลัพธ์เนทีฟของ LLVM จึงไม่ใช่เรื่องเป็นไปไม่ได้
      แต่ถ้าไม่มีแผนที่ออกแบบมาอย่างดีมาก ๆ หรือไม่ได้สร้างชุดคำสั่งที่ในทางปฏิบัติเป็นซูเปอร์เซ็ตของสิ่งที่สถาปัตยกรรมชุดคำสั่งเป้าหมายรองรับ ผมคิดว่าการได้ผลลัพธ์ในระดับเดียวกันนั้นยากมาก
      สำหรับผม WASM ดูใกล้เคียงกับการเป็นซับเซ็ตมากกว่า ดังนั้นการทำให้โอเปอเรชันเป็นมาตรฐานแล้วค่อยประกอบกลับแบบเรียลไทม์จึงไม่ง่าย ถึงจะไม่ถึงกับเป็นไปไม่ได้ แต่ก็ต้องใช้ความสำเร็จทางวิศวกรรมอย่างมาก
      ถ้ามองแบบสัญชาตญาณ มันก็เหมือนแปลหนังสือภาษาอังกฤษเป็นอีกภาษาหนึ่งที่แตกต่างมากและถูกจำกัดไว้แค่ไม่กี่พันคำ แล้วค่อยแปลกลับมาเป็นอังกฤษ คุณจะไม่ได้ข้อความเดิมกลับมาแบบเป๊ะ ๆ
      บางกรณีแนวคิดที่ภาษาอังกฤษใช้แค่คำเดียว อาจต้องอธิบายเป็นทั้งย่อหน้าในอีกภาษา ถ้าจะกู้ภาษาอังกฤษต้นฉบับกลับมา คุณต้องมีการแปลแบบ 1:1 สำหรับทุกอย่าง หรือไม่ก็มีรายการเทียบกันที่นักแปลทั้งสองฝั่งตกลงกันไว้ว่า ย่อหน้าหนึ่ง ๆ จะแทนด้วยคำเดียว