CRDT को 5000 गुना तेज़ बनाने की optimization यात्रा (2021)

 (josephg.com)
3 पॉइंट द्वारा GN⁺ 2024-08-28 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • सहयोगी editing में CRDT को धीमा बताने वाली राय अक्सर algorithm itself और implementation style को मिलाकर की गई होती है; केवल data structure और memory layout बदलने से performance में बड़ा फर्क आ सकता है
  • Automerge v1.0.0-preview2 ने 260,000 edits की trace processing में 291 सेकंड और 880MB RAM खर्च किया, जबकि वही काम Diamond types native ने 56ms और 1.1MB RAM में किया
  • Yjs ने tree के बजाय flat list, position cache, doubly linked list और span storage का उपयोग करके उसी trace को 0.97 सेकंड और 3.3MB RAM तक घटा दिया
  • Diamond types ने Rust में range tree/B-tree आधारित structure का उपयोग करके position lookup, insert और delete को log(n) time में संभाला, और WebAssembly में भी Node.js के आधार पर 193ms दर्ज किया
  • यह benchmark केवल single-user local edit replay और RAM usage को देखता है, इसलिए असल चुनाव में save/load time, network/disk size, binary encoding, protocol, presence और editor binding को भी साथ में देखना चाहिए

Algorithm और implementation performance अलग चीज़ें हैं

  • एक academic comparison ने Google Docs जैसी real-time collaborative editing को कई CRDT और OT algorithms से implement करके benchmark किया, और कुछ algorithms को साधारण paste process करने में 3 सेकंड से अधिक लगे
  • जो तरीके धीमे थे वे ShareJS और Google Wave में इस्तेमाल होने वाले algorithms थे, लेकिन उस implementation ने 1000-character paste को 1000 individual operations में तोड़कर process किया था
  • यह उदाहरण दिखाता है कि concurrent editing behavior और implementation style को अलग-अलग देखना चाहिए
    • behavior का मतलब है कि जब concurrent edits एक ही area में आते हैं, तो उन्हें किस order और rules से merge किया जाता है
    • implementation में programming language, data structure और optimization level शामिल होते हैं
  • वही text OT transform function JavaScript में लगभग 100,000 बार प्रति सेकंड, और C में 20M बार प्रति सेकंड चलता है, यानी लगभग 200 गुना अंतर आता है
  • एक धीमा implementation इस बात का सबूत नहीं है कि उस system के सभी implementations धीमे होंगे; तेज़ implementation संभव है

CRDT और Automerge का basic model

  • CRDT कई users को वही data simultaneously edit करने देता है, local पर बिना delay काम करने और बाद में synchronize करके eventual consistency तक पहुँचने की सुविधा देता है
  • Automerge, Martin Kleppmann द्वारा बनाई गई collaborative editing library है और RGA algorithm पर आधारित है
  • Automerge और Yjs जैसे CRDT shared document को characters की list मानते हैं और हर character को unique ID देते हैं
    • खाली document में abc type करने पर (seph, 0), (seph, 1), (seph, 2) जैसी ID लगती हैं
    • नया character “किस item के बाद insert किया गया है” यह भी record करता है
  • Automerge/RGA हर item में sequence number जोड़ता है
    • नए item को अब तक देखे गए सबसे बड़े sequence number से 1 बड़ा value मिलता है
    • अगर कई child items हों, तो उन्हें बड़े sequence number के order में sort किया जाता है, और बराबर होने पर agent ID से sort किया जाता है
  • Automerge/RGA के behavior को तीन steps में देखा जा सकता है
    • हर item को parent से connect करके tree बनाना
    • जिन items के कई children हैं, उन्हें sequence number और ID से sort करना
    • tree को depth-first traversal से flatten करके final list या text document बनाना

Automerge benchmark और bottlenecks

  • benchmark ने automerge-perf की edit trace का उपयोग किया
    • यह Martin Kleppmann द्वारा academic paper type करने की character-level trace है
    • trace में 260,000 edits हैं और final document size लगभग 100,000 characters है
    • इसमें concurrent editing शामिल नहीं है
    • test केवल local पर trace apply करने में लगने वाला time measure करता है
    • environment Ryzen 5800x workstation, Nodejs v16.1, Rust 1.52 है
  • Automerge v1.0.0-preview2 को इस trace को process करने में 291 सेकंड लगे, और completion पर RAM 880MB थी
    • यानी एक key input पर लगभग 10KB RAM खर्च हुआ
    • peak RAM 2.6GB थी
    • धीमे spikes में single edit process करने में 1.8 सेकंड लगे
  • JavaScript string पर direct splice करने वाला baseline उन्हीं edits को 0.61 सेकंड और 0.1MB RAM में process करता था, लेकिन यह comparison के लिए baseline है जो collaborative editing के लिए जरूरी सारी information discard कर देता है
  • Automerge के धीमे होने के कुछ implementation-level कारण हैं
    • document बड़ा होने पर tree-based data structure बड़ा और धीमा होता जाता है
    • Immutablejs का बहुत उपयोग होने से V8 optimizer और GC के लिए optimize करना मुश्किल होता है
    • insert किए गए हर character को अलग item माना जाता है, इसलिए paste भी बहुत सारे items के रूप में process होता है
  • Automerge team Rust implementation automerge-rs को WASM के जरिए इस्तेमाल करने वाला alternative implementation बना रही थी
    • उस समय master branch के हिसाब से इस test में average performance तेज़ नहीं हुई थी, लेकिन memory usage आधा हो गया और performance variation कम तीखा हुआ

Yjs-style flat list implementation

  • Yjs Kevin Jahns द्वारा बनाया गया open-source CRDT implementation है, और tree के बजाय सभी items को single flat list में store करता है
  • flat list approach में नया item insert position ढूँढने के लिए parent के ठीक बाद से scan करता है; यह list CRDT को list के रूप में implement करने का तरीका है
  • experimental reference-crdts Yjs के YATA और Automerge के RGA को समान तरीके से implement करता है
    • insert function मामूली differences को छोड़कर Yjs और Automerge behavior को लगभग same codepath से process करता है
    • semantic equivalence को fuzzer से verify किया गया है
  • इस approach के तीन फायदे हैं
    • unbalanced tree के बजाय flat array इस्तेमाल करने से यह छोटा और तेज़ है
    • code simple है
    • इसे Yjs, Automerge, Sync9 जैसे कई list CRDTs पर apply किया जा सकता है
  • theoretically, अगर same position पर बहुत सारे concurrent inserts हों तो यह धीमा हो सकता है, लेकिन real editing में ज्यादातर insert parent के ठीक बाद होते हैं
  • reference-crdts implementation Automerge से लगभग 10 गुना तेज़ था और RAM लगभग 30 गुना कम इस्तेमाल करता था
टेस्ट Processing time RAM usage
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Plain string edits in JS 0.61s 0.1MB

स्कैन और insert की लागत घटाना

  • flat array implementation में दो bottleneck बचे रहते हैं
    • insert करने की जगह खोजने के लिए document को scan करना पड़ता है
    • doc.content.splice(destIdx, 0, newItem) से array के बीच में insert करते समय पीछे के items को move करना पड़ता है
  • deleted items को array से हटाया नहीं जा सकता, क्योंकि दूसरे insert उन्हें reference कर सकते हैं; इसलिए isDeleted जैसा marker छोड़ना पड़ता है
    • मौजूदा document 100,000 characters का हो, तब भी पुराने items सहित array में 150,000 items हो सकते हैं
    • document position 50,000 पर insert करने के लिए deleted items को skip करते हुए करीब 75,000 items scan करने पड़ सकते हैं
  • ऐसी structure में जिस document में n items हों उसमें insert करने के लिए लगभग n steps चाहिए, और n characters insert करने पर यह O(n²) बन जाता है
  • Yjs इंसान के document edit करने के तरीके के हिसाब से आखिरी edit position की (index, position) pair को cache करता है
    • अगला edit पिछले edit position के पास होने की संभावना अधिक होती है, इसलिए आगे-पीछे थोड़ी दूरी तक scan करता है
    • कई users अलग-अलग positions edit करें, इसके लिए cached positions का set store करता है
  • Yjs array के बजाय doubly linked list इस्तेमाल करता है, ताकि position मिल जाने के बाद constant time में insert हो सके
  • साथ ही, इंसान लगातार characters type करता है, इस बात का फायदा उठाकर hello को 5 character items के बजाय एक span के रूप में store करता है
    • ID और parent sequentially जुड़े हों तभी collapse किया जा सकता है
    • इस dataset में array entries की संख्या 180,000 से 12,000 हो गई, यानी 14 गुना कमी
टेस्ट processing time RAM usage
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

Rust और Diamond types का range tree approach

  • JavaScript objects में content, deletion flag, ID, seq, parent आदि pointers के जरिए बिखरी हुई structure बनना आसान है, जिससे memory fragmentation और cache miss की लागत बढ़ती है
  • Rust में memory layout को सीधे control किया जा सकता है, और WebAssembly के जरिए इसे web में भी इस्तेमाल किया जा सकता है
  • Diamond types Rust में लिखा गया CRDT implementation है; यह Yjs जैसा ही है, लेकिन internally linked list के बजाय range tree इस्तेमाल करता है
  • internal range tree थोड़ा modified B-tree है
    • सामान्य BTreeMap की तरह key store करने के बजाय, internal nodes अपने children में शामिल characters की कुल संख्या store करते हैं
    • document की arbitrary position lookup, insert और delete को log(n) time में process करता है
  • 260,000 edits की trace इस tree में लगभग leaf node के 3 levels में store होती है, इसलिए किसी भी item को करीब 3 memory reads में पाया जा सकता है
  • remote edit merge के लिए ID से B-tree खोजने वाला एक छोटा index भी है, और यह codepath इस benchmark में शामिल नहीं है
  • leaf node 32 entries के blocks को fixed-size array में compactly store करता है
    • बताया गया कि 32 bucket size ने कई sizes के benchmark में अच्छा काम किया, लेकिन यह क्यों optimal है, यह पता नहीं
  • Diamond को diamond-js के रूप में WASM compile करके Node.js से call करने पर वही trace 193ms में process होती है
    • Yjs से लगभग 5 गुना तेज़
    • JavaScript string baseline से लगभग 3 गुना तेज़
  • native Rust execution ने benchmark में 56ms record किया
    • Automerge से 5000 गुना से भी अधिक तेज़
    • प्रति second 4.6M operations process करता है
    • कुल 260,000 edits process करने के दौरान malloc calls 1394 बार हुए
टेस्ट processing time RAM usage
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 separation और tradeoff

  • Diamond implementation document text content को सीधे CRDT item list में नहीं रखता, बल्कि अलग data structure में store करता है
  • text content के लिए Rust library Ropey इस्तेमाल होती है, और Ropey भी text management के लिए B-tree implement करता है
  • इस approach में engineering tradeoff है
    • Ropey text-specific byte packing करता है, इसलिए RAM usage घटाया जा सकता है
    • insert के समय दो data structures update करने पड़ते हैं, जिससे speed 2 गुना से अधिक धीमी हो जाती है और WASM bundle भी 60KB से 120KB हो जाता है
    • VS Code जैसे editor से connect करने पर editor document की copy रखता है, इसलिए CRDT structure के अंदर document content store न करना भी संभव हो सकता है
  • केवल Ropey से trace process करने पर 29ms लगते हैं
  • Diamond native में document content update बंद करने पर 23ms और 0.96MB RAM record हुआ
    • Automerge से लगभग 14,000 गुना तेज़
    • प्रति second 11M operations process करता है
    • यह result उपयोगिता से ज्यादा CRDT metadata processing की सीमा देखने वाला experiment है
टेस्ट processing time RAM usage data structure
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 none
Diamond WASM via Node.js 0.20s अज्ञात B-tree
Diamond native 0.056s 1.1MB B-tree
Ropey Rust baseline 0.029s 0.2MB none
Diamond native, no doc content 0.023s 0.96MB B-tree

असली library चुनने के criteria

  • अगर अभी document-based collaboration app बना रहे हैं, तो Yjs इस्तेमाल करना बेहतर रहेगा
    • Yjs में performance, कम memory usage और support ecosystem अच्छे हैं
    • Kevin Jahns Yjs integration support paid रूप में भी देते हैं
  • Automerge team ने भी 2021 में performance को top-priority issue रखा था, और कई techniques से Automerge को तेज़ बनाने की योजना थी
  • Diamond बहुत तेज़ है, लेकिन Yjs और Automerge जैसी feature parity तक पहुँचने के लिए अभी काफी काम बाकी है
    • CRDT library में operation speed के अलावा binary encoding, network protocol, non-list data structures, presence, editor binding आदि भी चाहिए
  • अगर database semantics चाहिए, तो CRDT के ऊपर कोई अच्छी implementation ज्ञात नहीं है; OT-based ShareDB इस्तेमाल किया जा सकता है
  • Redwood P2P editing support करता है और full CRDT support की योजना वाला project है

मापन पद्धति की सीमाएँ

  • यह benchmark केवल लोकल एडिट trace replay time और RAM usage को मापता है
  • लोकल user input का पर्याप्त तेज़ होना काफी है, और अगर CRDT एक single local edit को लगभग 1ms या उससे कम में process कर देता है, तो उससे ज्यादा speed बहुत मायने नहीं रख सकती
    • Automerge भी bad luck वाले GC pause को छोड़ दें तो आम तौर पर इस स्तर को पूरा करता है
  • असल में अधिक महत्वपूर्ण metrics अलग हैं
    • document disk या network पर कितने bytes लेता है
    • save और load में लगने वाला समय
    • saved document को database के अंदर update करने में लगने वाला समय
  • इस्तेमाल किए गए trace में केवल single-user edits शामिल हैं, इसलिए simultaneous edits बहुत ज्यादा होने वाले pathological cases बाकी हो सकते हैं
  • अभी Yjs या Automerge से database के किसी single object को update करने के लिए आम तौर पर पूरा document RAM में load करना, change करना, और फिर पूरे document को दोबारा save करना पड़ता है, जिससे यह धीमा हो सकता है
    • Kevin कहते हैं कि Yjs provider को ठीक से adjust किया जाए तो इसे reasonable तरीके से implement किया जा सकता है
  • list CRDT deleted items के tombstones की वजह से मूल रूप से लगातार बढ़ता रहता है, और pruning एक अलग approach है
    • Yjs का GC algorithm और Antimatter examples के रूप में आते हैं
    • pruning, इस लेख में discuss किए गए data structure optimization से orthogonal समस्या है

तुलना पूरी तरह controlled experiment नहीं है

  • हर optimization step ने एक साथ कई variables बदले, इसलिए speed improvement के exact cause को अलग-अलग isolate नहीं किया गया
  • Automerge से reference-crdts पर जाते समय कई elements बदले
    • core data structure tree से list में बदला
    • Immutablejs हटाया गया
    • Automerge frontend/backend protocol और कई Uint8Array structures गायब हुए
    • JavaScript style functional से imperative में बदली
  • reference-crdts से Yjs, और Yjs से Diamond पर जाते समय भी changes को single cause के रूप में अलग नहीं किया गया
  • automerge-rs इस test में Automerge से तेज़ नहीं था, यह इस बात का evidence है कि Diamond performance केवल Rust का असर नहीं है, लेकिन exact contribution पता नहीं चल सकता
  • RGA और YATA को same implementation style में compare करना भी इस premise पर निर्भर करता है कि “concurrent merge behavior वास्तव में लगभग समान है, और behavior बदलने पर भी implementation performance बनी रहती है”
    • reference CRDT implementation में Yjs और Automerge behavior लगभग identical codepath और identical performance दिखाते हैं
    • conflict-heavy trace में performance difference हो सकता है, लेकिन व्यवहार में इसे बहुत rare case माना गया है
  • Yjs यह store नहीं करता कि हर item कब delete हुआ, केवल deletion status store करता है
    • Diamond में deletion time store करने पर memory usage 1.12MB से बढ़कर 2.34MB हो जाता है और यह लगभग 5% धीमा हो जाता है
    • इस लेख के सभी Diamond benchmarks Yjs के तरीके से align किए गए yjs-style branch का उपयोग करते हैं

Benchmark code और reproducibility material

  • JS string baseline, Yjs, Automerge, reference-crdts test code GitHub gist में है
  • ज्यादातर tests के लिए josephg/crdt-benchmarks का automerge-paper.json.gz चाहिए
  • reference-crdts benchmark josephg/reference-crdts के उस version पर depend करता है
  • Diamond benchmark josephg/diamond-types के उस version में run किया गया
    • run command है RUSTFLAGS='-C target-cpu=native' cargo criterion yjs
    • memory statistics cargo run --release --features memusage --example stats से check किए गए
  • Diamond WASM wrapper diamond-js का उपयोग करता है, और wasm bundle को wasm-opt से optimize किया गया
  • charts ObservableHQ पर बनाए गए

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

1 टिप्पणियां

 
GN⁺ 2024-08-28
Hacker News की रायें

  • अगर 2-byte integer इस्तेमाल किए गए थे, तो इसकी बड़ी संभावना cache line 64 bytes की वजह से है
    32 entries बिल्कुल एक cache line बन जाती हैं, इसलिए हर cache line में पूरा एक bucket आ जाता होगा और महंगे main memory transfer कम हुए होंगे

    • Knuth जिस तरह बाद के programs को benchmark करते थे, वह अच्छा लगा
      मूल रूप से वे एक counter डालते थे जो गिनता था कि किसी चीज़ को memory से कितनी बार पढ़ना पड़ता है; उसी तरह सोच रहा हूँ कि क्या cache lines को कितनी बार खाली करना पड़ता है इसका कोई approximation किया जा सकता है
    • batch size के हिसाब से benchmark करने पर memory hierarchy से जुड़े बड़े jumps अक्सर दिखते हैं
      word size (64-bit), cache-aligned fetch size (आम तौर पर ऊपर बताए गए 64 bytes), OS page size (4~16KB), L1 size (लगभग 80KB per core), L2 (कुछ MB के स्तर) जैसी boundaries पर उछाल दिखता है

  • असली services में CRDT इस्तेमाल करते हुए किन apps का experience बहुत अच्छा रहा है, यह जानना चाहूँगा
    याद है कि Notion उनमें से एक था, लेकिन व्यवहार में Notion में दो लोगों का साथ में notes बनाना Google Docs की तुलना में लगभग unusable लगता है

    • Thymer[1] हर चीज़ के लिए CRDT इस्तेमाल करता है
      यह tasks और planning के लिए एक IDE है, multi-user app है, end-to-end encryption, offline-first, optional self-hosting को support करता है, और पूरा workspace एक graph है, इसलिए CRDT एक natural choice था
      Thymer की सारी actions कुछ CRDT transformations में सिमट जाती हैं। text move/copy, "frontmatter" properties बदलना, cards drag करना, file upload, tag जोड़ना—सब कुछ उन्हीं कुछ CRDT operations से handle होता है
      शुरुआत में बिना library के implement करने में काफी काम लगा, लेकिन अगर application state एक graph हो, तो pages के बीच text move, backlinks वाले page links, transclusion जैसे features sync की चिंता किए बिना बना सकते हैं, इसलिए यह पूरी तरह worth it था
      CRDT यह guarantee करता है कि सभी clients एक ही state पर converge होंगे, और यह मूल रूप से append-only होता है, इसलिए किसी खास point-in-time की version management भी मुफ्त में मिल जाती है
      हालांकि performance की वजह से कुछ compromises किए। version history में data बहुत ज्यादा होता है, इसलिए उसे offline में उपलब्ध नहीं कराते, और कुछ मामलों में last-writer-wins conflict resolution इस्तेमाल करते हैं
      कुल मिलाकर, खासकर अगर app को शुरू से CRDT को ध्यान में रखकर design किया जाए, तो यह बहुत valuable है। अगर किसी ज्यादा पारंपरिक AJAX app में बाद में multi-user features जोड़े जा रहे हों, तो शायद मैं CRDT इस्तेमाल नहीं करूँगा
      CRDT के changes पहले optimistically apply होते हैं, और जब authoritative event order तय हो जाता है, तो सभी clients को आखिरी shared state पर वापस जाकर सभी events को सही order में फिर से apply करना होता है
      अगर आप लंबे समय तक offline रहे हों, तो कई दिनों के changes को undo करके फिर reapply करना पड़ सकता है। user को पीछे चल रहीं इतनी सारी tree transformations का पता नहीं चलता, लेकिन CRDT पूरे application design को प्रभावित करता है
      आज के ज्यादातर popular apps उस समय design किए गए थे जब CRDT transformations अभी अच्छी तरह समझी नहीं गई थीं
      [1] https://thymer.com (लगभग beta-ready)
    • आज Notion सीमित तौर पर सिर्फ कुछ intention-preserving operations वाला last-writer-wins system है, जैसे list data में blocks का order
      text last-writer-wins है, और हर block text या property last-writer-wins register है। block text के लिए नए CRDT format पर काम चल रहा है
    • मेरी जानकारी में iCloud की ज्यादातर services internally CRDT इस्तेमाल करती हैं
      इसमें Notes, Reminders शामिल हैं और Photos भी हो सकता है। backend के हिस्से के तौर पर FoundationDB भी इस्तेमाल होता है—यह मैंने एक नशे में धुत पूर्व Apple SRE से bar में सुना था
    • Linear: https://linear.app/
      Local First Conf की talk भी देखने लायक है: https://youtu.be/VLgmjzERT08
    • थोड़ा और सोचें तो एक और example है जो लोगों को तुरंत याद नहीं आएगा
      किसी भी रूप में rollback या correction करने वाले network games लगभग इसी श्रेणी में आते हैं। best-effort तरीके के साथ rollback को fallback path बनाना शायद व्यापक रूप से इस्तेमाल होने वाले CRDTs में user experience के लिहाज़ से सबसे अच्छा रूप हो सकता है
      यह कठोर academic अर्थ में CRDT नहीं है। technically game state सभी clients पर पूरी तरह replicate नहीं होती, और हर client को सिर्फ partial game state मिलती है
      साथ ही game clients को low-latency synchronization चाहिए, और academic रूप से इसे “coordination” माना जा सकता है। व्यवहार में client conflict resolution या rollback correction लौटने से पहले input के result को probabilistically local रूप से accept और render कर देता है
      कुछ लोग इसमें बारीकी से आपत्ति कर सकते हैं, लेकिन तीसरे example तक common theme दिखने लगेगी। सबसे popular, usable और अच्छी तरह implemented CRDTs असल में academic rules तोड़ते हैं
      यह अत्यधिक academic thinking model का typical trap है। वास्तविक algorithms और data types अक्सर academic “rulebook” से कहीं ज्यादा creative होते हैं। उदाहरण के लिए Timsort
      अगर आप paper review के लिए नहीं, बल्कि real users के लिए product बना रहे हैं, तो over-engineering/academic traps में नहीं फँसना चाहिए। academic rules सीखें, लेकिन उन्हें जानबूझकर तोड़ें; और केवल academics के बीच उपयोगी रहने लायक सख्ती से define किए गए concepts को perfect implement करने की बजाय real value जोड़ें और चीज़ को usable बनाएं

  • CRDT शक्तिशाली है, लेकिन चाहे वह operation-based हो या state-based, यह बात खटकती है कि यह पुराने operations या elements के निशान छोड़ता है
    Compression करने पर भी यह अब भी एक कमी है, और अपनाने से पहले चिंता कराने वाली बात है
    फिर भी इस चर्चा की वजह से Dropbox, Syncthing जैसे file-based storage के ऊपर conflict-free algorithms या बारीक conflict resolution algorithms लागू करने की संभावना दिलचस्प लगी

    • मैं लेखक हूं। मैंने यह बातचीत बहुत बार की है और CRDT समुदाय में भी इस पर अक्सर बात होती है, लेकिन असल में कम-से-कम text editing में overhead इतना छोटा है कि real-world में समस्या बनने जैसा नहीं लगता
      मेरा post-CRDT project Diamond Types मूलतः समय के साथ अनंत रूप से बढ़ता जाता है, लेकिन overhead आम तौर पर अब तक टाइप किए गए हर character पर 1 byte से कम होता है
      Stored text पर LZ4 compression चालू करने पर Diamond Types से edit किए गए documents अक्सर पूरी edit history store करने के बावजूद final document state से छोटे होते हैं
      इसे तकनीकी रूप से हल करने के कई तरीके मुझे पता हैं, लेकिन ज़्यादातर systems में मुझे यकीन नहीं कि यह वास्तविक समस्या है
      मैंने सुना है कि yjs को 3D modeling tool में इस्तेमाल करने वाले किसी व्यक्ति को समस्या हुई थी। वजह यह थी कि object को drag करते समय mouse के pixel-by-pixel move होने पर हर बार persistent edit बना रहा था
      ऐसे कामों के लिए ज्यादातर CRDT libraries द्वारा support न किए जाने वाले transient edits इस्तेमाल करना ज़्यादा समझदारी होगा, ऐसा मुझे लगता है
      संदर्भ के लिए, Git में भी यही समस्या है। Repository समय के साथ बड़ी होती जाती है, और modern CRDT library इस्तेमाल करने की तुलना में कहीं ज्यादा तेजी से बढ़ती है। लेकिन लगता है कोई खास परवाह नहीं करता
      Git में shallow clone संभव है, लेकिन लगभग कोई नहीं करता। चाहें तो CRDT में भी वही किया जा सकता है
    • अगर आप पूरी तरह decentralized system नहीं बना रहे हैं, तो CRDT जिन constraints की मांग करता है उनमें से कुछ को relax किया जा सकता है
      उदाहरण के लिए, अगर यह guarantee कर सकते हैं कि सभी clients को X तारीख के बाद के changes मिल चुके हैं, तो उस तारीख से पहले के operations सुरक्षित रूप से फेंके जा सकते हैं
    • पूरा operation log और deterministic merge immutable block storage के साथ अच्छी तरह मेल खाते हैं, और security, performance, cost के लिहाज से भी फायदे दे सकते हैं
      इस क्षेत्र की latest research का लाभ उठाने के लिए Fireproof[1] बना रहा हूं
      Immutable data को content-address करने से अतिरिक्त लाभ यह है कि हर operation cryptographically guaranteed proof या diff में परिणत होता है। Causal consistency enforce की जा सकती है और snapshots के लिए stable references बनाए जा सकते हैं
      यानी edge या browser में ऐसा database चलाया जा सकता है जो interactive हो, offline काम करे, और losslessly merge हो, फिर भी वह integrity रखे जिसकी उम्मीद पहले central database या blockchain से की जाती थी
      उदाहरण के लिए, signature के लिए PDF या smart contract में snapshot CID डालकर referenced state को लेकर ambiguity खत्म की जा सकती है
      [1] https://github.com/fireproof-storage/fireproof
    • CRDT की अवधारणा में खुद ऐसी कोई requirement नहीं है कि पुराने operations या elements के निशान छोड़े ही जाएं
      इसलिए किसी खास data type या database के पालन किए जाने वाले mathematical laws के सेट पर व्यापक बात करने के बजाय, concrete implementation की आलोचना करना ज्यादा सही है
    • अगर history delete की जा सकती है तो चिंता किस बात की है, यह जानना चाहूंगा

  • यह 2021 का लेख है और लगता है Automerge की Rust implementation भी शामिल है, इसलिए updated benchmark देखना दिलचस्प होगा

    • मैं लेखक हूं। Yjs का भी Rust में फिर से लिखा गया yrs है, और वह JavaScript version से काफी तेज है
      इस problem को solve करने का मेरे पास एक बिल्कुल अलग नया approach भी है
      Benchmark update करना निश्चित रूप से अच्छा रहेगा। सब कुछ तेज हो गया है

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

  • ये पहले की संबंधित चर्चाएं हैं
    https://news.ycombinator.com/item?id=28017204 (3 साल पहले, 151 comments)
    https://news.ycombinator.com/item?id=33903563 (2 साल पहले, 22 comments)
    https://news.ycombinator.com/item?id=41372833 (मौजूदा post)
    https://news.ycombinator.com/item?id=41373288 (मौजूदा comment)

  • मौजूदा GitHub Readme[0] को quote करें तो, उस blog post के बाद भी performance में फिर 10~80 गुना सुधार हुआ है
    [0] https://github.com/josephg/diamond-types

  • अगर कोई समझा सके कि CRDT धीमा क्यों है, तो अच्छा होगा
    यह लेख future दिखाता लगता है: https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
    इसे देखकर Y.js या Automerge से compare करना अच्छा रहेगा: https://github.com/canvasxyz/okra-js

    • मैं लेखक हूं। मुख्य वजह यह है कि बहुत-सी CRDT libraries academics ने लिखीं, और उनके पास optimize करने का समय, skill या interest पर्याप्त नहीं था
      कुछ साल पहले यह लेख लिखने के बाद से प्रमुख CRDT libraries सभी कई orders of magnitude तेज हो गई हैं

  • याद है कि कुछ साल पहले यह लेख अचानक देखा था
    सचमुच बहुत मजेदार लेख है, और पिछले कुछ वर्षों में मेरे पसंदीदा लेखों में से एक है

    • याद पड़ता है कि title शायद CRDTs go brrr था

  • “WASM नेटिव execution से 4 गुना धीमा क्यों है?” इस पर मेरा मानना था कि वजह यह है कि हर string operation को WASM memory में copy किया जाता है, और result calculate होने पर उसे फिर से JS में copy करना पड़ता है
    क्या मैं गलत था? क्या मैंने context गलत समझा? सच में जानना चाहता हूँ

    • मैं ही लेखक हूँ। यह लेख कुछ साल पुराना है, लेकिन याद के मुताबिक हमने उस हिस्से को control किया था। इसलिए समस्या FFI नहीं थी
      time measure करने से पहले पूरी history को wasm के अंदर load किया गया था, और उसे Rust में लिखे internal loop में process किया गया था, जो wasm context के भीतर ही run हो रहा था। wasm calls बस लगभग दो बार ही थे
      4 गुना slowdown की वजह FFI नहीं थी; algorithm code खुद वास्तव में 4 गुना धीमा execute हो रहा था
      अब benchmarks दोबारा चलाकर देखना दिलचस्प होगा। compiler का wasm output भी बेहतर हुआ होगा और wasm runtime भी तेज हुआ होगा। benchmark code शायद कहीं अब भी मौजूद होगा
    • यह एक plausible कारण लगता है
      एक अलग area में जो समस्या बार-बार आती है, वह यह है कि multi-threading की बात आसान नहीं है, और library तथा tooling support भी complete नहीं है
      मैंने browser में game engines या ffmpeg, zip जैसी utility binaries चलाकर देखी हैं, और इसी वजह से वे बहुत धीमी थीं
    • बेहतर सवाल शायद यह है कि हम दोनों के समान होने की उम्मीद क्यों करें
      मैंने WASM interpreter या JIT पर काम नहीं किया है, लेकिन एक translation layer से गुजरने की तुलना में कई layers से गुजरना कितनी बार बेहतर होता होगा?
      जब high-level code को WASM या किसी assembly language में translate किया जाता है, तो high-level code में मौजूद बहुत-सी intention खो जाती है
      low-level code में अक्सर goal हासिल करने के लिए language-specific idioms की एक श्रृंखला दिखती है, जिनका real machine से सीधा mapping हो भी सकता है और नहीं भी
      modern x86-64 में WASM से संभव चीज़ों की तुलना में कहीं ज़्यादा powerful instructions बहुत बड़ी संख्या में हैं
      बेशक decompilers भी हैं, और हो सकता है कि WASM JIT के पास macro-op fusion की ऐसी list हो जिससे वह relatively simple pattern matching के जरिए अच्छा native code बना सके। शायद ऐसा नहीं होगा, और cross-platform optimization और भी मुश्किल होगी
      LLVM भी perfect नहीं है, इसलिए ऐसे आसान हिस्से निश्चित रूप से हैं जिन्हें post-processing optimizer बेहतर बना सकता है। इसलिए LLVM के native output से WASM को तेज बनाना theoretically impossible नहीं है
      लेकिन जब तक कोई बहुत अच्छी तरह से बनाई गई योजना न हो, या आप ऐसा instruction set न बना दें जो practically target instruction set architecture द्वारा support की जाने वाली चीज़ों का superset हो, तब तक समान स्तर का result हासिल करना बहुत मुश्किल लगता है
      मेरे हिसाब से WASM subset के ज्यादा करीब है, इसलिए operations को standardize करके real time में फिर से combine करना आसान नहीं है। पूरी तरह impossible न हो, फिर भी यह बड़ी engineering achievement मांगता है
      intuitively, अगर English में लिखी किताब को किसी बहुत अलग language में translate किया जाए, वह भी कुछ हजार words तक सीमित language में, और फिर वापस English में translate किया जाए, तो exactly वही text नहीं मिलेगा
      English में जिस concept को एक word में कहा जा सकता है, उसे कभी-कभी paragraph में समझाना पड़ता है। original English वापस पाने के लिए या तो हर चीज़ का 1:1 translation चाहिए, या दोनों translators द्वारा agreed paragraph→one-word translation list चाहिए