ज़्यादा तेज़ CRDTs (2021)

 (josephg.com)
3 पॉइंट द्वारा GN⁺ 2024-08-28 | 1 टिप्पणियां | WhatsApp पर शेयर करें

5000 गुना तेज़ CRDT: ऑप्टिमाइज़ेशन का रोमांच

परिचय

  • कुछ साल पहले, फ्रांसीसी शोधकर्ताओं ने एक पेपर प्रकाशित किया था जिसमें real-time collaborative editing algorithms की तुलना की गई थी
  • उन्होंने कई algorithms को implement किया और उनकी performance का benchmark किया
  • कुछ algorithms को एक साधारण paste operation में 3 सेकंड से ज़्यादा लगे
  • समस्या वाला algorithm वही था जिसे ShareJS में इस्तेमाल किया गया था

समस्या का कारण

  • पेपर में बड़े टेक्स्ट को paste करते समय उसे 1000 अलग-अलग operations में बाँटकर process किया गया था
  • यह algorithm की मूल समस्या नहीं थी, बल्कि implementation की समस्या थी

CRDT की आकर्षकता

  • CRDT(Conflict-Free Replicated Data Types) कई users को एक ही समय में data edit करने की सुविधा देता है
  • इसमें local पर बिना latency के काम किया जा सकता है, और sync के समय consistency अपने-आप बनी रहती है
  • यह central server के बिना भी काम कर सकता है

Automerge की समस्याएँ

  • Automerge collaborative editing के लिए एक library है, जो RGA algorithm पर आधारित है
  • यह दस्तावेज़ के हर character को एक unique ID के साथ manage करता है, और insert करते समय parent item को specify करता है
  • performance issues के कारण 260,000 edit operations को process करने में 5 मिनट लगते थे
  • memory usage भी बहुत ज़्यादा था

performance optimization

  • Automerge की performance problems की वजह जटिल tree-based data structures और Immutablejs का उपयोग था
  • Yjs ने single flat list का उपयोग करके performance को काफ़ी बेहतर बनाया
  • Yjs insert position खोजने के लिए cache का उपयोग करता है, और insert को efficiently handle करने के लिए doubly linked list का उपयोग करता है
  • Yjs 30 गुना तेज़ है और memory usage भी कम है

Rust की ओर बदलाव

  • Rust memory layout को control करने की सुविधा देता है, जिससे performance और बेहतर की जा सकती है
  • Diamond types नामक नए CRDT implementation के ज़रिए Yjs से 5 गुना तेज़ performance हासिल की गई
  • Rust में implemented Diamond ने 260,000 edit operations को केवल 56 मिलीसेकंड में process किया

निष्कर्ष

  • optimized data structures और efficient memory management के ज़रिए CRDT की performance को काफ़ी बढ़ाया जा सकता है
  • Rust जैसी low-level language का उपयोग करके और भी तेज़ performance हासिल की जा सकती है

GN⁺ का सार

  • CRDT collaborative editing का भविष्य है, जो central server के बिना भी consistency बनाए रखने वाला एक शक्तिशाली tool है
  • Automerge की performance problems की वजह जटिल data structures और inefficient memory usage था
  • Yjs और Diamond types सरल और efficient data structures का उपयोग करके performance को काफ़ी बेहतर बनाते हैं
  • Rust जैसी low-level language का उपयोग करके और भी तेज़ performance हासिल की जा सकती है
  • collaborative editing tools बनाते समय Yjs और Diamond types पर विचार करना उचित होगा

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-08-28
Hacker News राय

  • 32 entries सबसे efficient होने का कारण यह है कि cache line 64 bytes की होती है

    • अगर 2-byte integers इस्तेमाल किए जाएँ, तो 32 entries ठीक एक cache line में फिट हो जाती हैं, जिससे main memory transfers कम किए जा सकते हैं

  • CRDTs का इस्तेमाल करने वाले वास्तविक applications में अच्छा experience देने वाले examples ढूंढना मुश्किल है

    • Notion में जब दो लोग एक साथ note लिखते हैं, तो usability Google Docs की तुलना में कमजोर लगती है

  • CRDTs शक्तिशाली हैं, लेकिन इनमें historical operations (या elements) बचे रहने की कमी होती है

    • compression इस्तेमाल करने पर भी यह कमी बनी रहती है, इसलिए adoption को लेकर चिंता है
    • फिर भी, file-based storage providers (Dropbox, Syncthing आदि) में conflict-free algorithms लागू करने की संभावना दिलचस्प लगती है

  • मौजूदा GitHub Readme से उद्धरण:

    • blog post के बाद performance 10-80 गुना बेहतर हुई है

  • यह लेख, भले ही समझने में कठिन हो, बहुत अच्छी तरह लिखा गया है और इसे पढ़ना रोकना मुश्किल था

  • hierarchy का इस्तेमाल देखकर यह जिज्ञासा हुई कि nested sets का उपयोग क्यों नहीं किया गया

    • यह अंदाज़ा नहीं है कि read operations में मिलने वाला लाभ insert operations में होने वाले नुकसान की भरपाई कर पाएगा या नहीं

  • कुछ साल पहले यह पोस्ट संयोग से मिली थी

    • पिछले कुछ वर्षों में पढ़ी गई सबसे मज़ेदार पोस्टों में से एक है

  • यह जानने की जिज्ञासा हुई कि WASM native execution से 4 गुना धीमा क्यों है

    • लगा कि शायद इसका कारण यह है कि सभी string operations को WASM memory में copy करना पड़ता है और result calculate होने के बाद फिर JS में वापस copy करना पड़ता है
    • समझ नहीं आया कि कहीं इस context को गलत तो नहीं समझा

  • Automerge का Rust implementation अब पूरा हो चुका है, इसलिए updated benchmarks देखना दिलचस्प होगा