CRDT’leri 5000 Kat Hızlandıran Optimizasyon Yolculuğu (2021)

 (josephg.com)
3 puan yazan GN⁺ 2024-08-28 | 1 yorum | WhatsApp'ta paylaş
  • İşbirliğine dayalı düzenlemede CRDT’lerin yavaş olduğu yönündeki değerlendirme, çoğu zaman algoritmanın kendisi ile uygulama biçimini birbirine karıştırmanın sonucudur; veri yapısı ve bellek yerleşimi bile performansı büyük ölçüde değiştirebilir
  • Automerge v1.0.0-preview2, 260.000 düzenleme izini işlemek için 291 saniye ve 880MB RAM kullandı; aynı işi Diamond types native ise 56ms ve 1.1MB RAM ile tamamladı
  • Yjs, ağaç yerine düz liste, konum önbelleği, çift yönlü bağlı liste ve span saklama kullanarak aynı izi 0.97 saniye ve 3.3MB RAM’e düşürüyor
  • Diamond types, Rust’ta range tree/B-tree tabanlı bir yapı kullanarak konum sorgulama, ekleme ve silmeyi log(n) zamanda işliyor; WebAssembly’de de Node.js bazında 193ms kaydediyor
  • Bu benchmark yalnızca tek kullanıcılı yerel düzenleme oynatımı ve RAM kullanımına baktığı için, gerçek seçimde saklama/yükleme süresi, ağ/disk boyutu, binary encoding, protokol, presence ve editor binding de birlikte değerlendirilmelidir

Algoritma ile uygulama performansı ayrı şeylerdir

  • Bir akademik karşılaştırma, Google Docs benzeri gerçek zamanlı işbirliğine dayalı düzenlemeyi çeşitli CRDT ve OT algoritmalarıyla uygulayıp benchmark yaptı; bazı algoritmalar basit bir paste işlemi için 3 saniyeden fazla sürdü
  • Yavaş olan yöntemler, ShareJS ve Google Wave’de kullanılan algoritmalardı; ancak ilgili uygulama 1000 karakterlik bir paste işlemini 1000 ayrı operation’a bölerek işliyordu
  • Bu örnek, eşzamanlı düzenleme davranışı ile uygulama biçimini ayrı değerlendirmek gerektiğini gösteriyor
    • Davranış, eşzamanlı düzenlemeler aynı alana geldiğinde hangi sıra ve kurallarla birleştirildiğini ifade eder
    • Uygulama ise programlama dili, veri yapıları ve optimizasyon düzeyini kapsar
  • Aynı text OT transform fonksiyonu JavaScript’te saniyede yaklaşık 100.000 kez, C’de ise saniyede 20M kez çalıştırılarak yaklaşık 200 kat fark yaratmıştır
  • Tek bir yavaş uygulama, o sistemin tüm uygulamalarının yavaş olduğunun kanıtı değildir; daha hızlı uygulamalar mümkündür

CRDT ve Automerge’ün temel modeli

  • CRDT, birden fazla kullanıcının aynı veriyi eşzamanlı düzenlemesini sağlar; kullanıcılar yerelde gecikmesiz çalışıp daha sonra senkronize olarak eventual consistency’ye ulaşabilir
  • Automerge, Martin Kleppmann tarafından geliştirilmiş bir işbirlikçi düzenleme kütüphanesidir ve RGA algoritmasına dayanır
  • Automerge ve Yjs gibi CRDT’ler, paylaşılan belgeyi karakterlerden oluşan bir liste olarak görür ve her karaktere benzersiz bir ID verir
    • Boş bir belgeye abc yazıldığında (seph, 0), (seph, 1), (seph, 2) gibi ID’ler atanır
    • Yeni karakterle birlikte “hangi öğenin arkasına eklendiği” bilgisi de kaydedilir
  • Automerge/RGA, her öğeye bir sequence number ekler
    • Yeni öğe, o ana kadar görülen en büyük sequence number’dan 1 büyük bir değer alır
    • Birden fazla child öğe varsa, büyük sequence number önce gelecek şekilde sıralanır; eşitse agent ID’ye göre sıralanır
  • Automerge/RGA’nin çalışma biçimi üç adımda görülebilir
    • Her öğe parent’a bağlanarak bir ağaç oluşturulur
    • Birden fazla child’ı olan öğeler, sequence number ve ID’ye göre sıralanır
    • Ağaç, depth-first traversal ile düzleştirilerek nihai liste ya da metin belge oluşturulur

Automerge benchmark’ı ve darboğazlar

  • Benchmark, automerge-perf içindeki düzenleme izini kullanıyor
    • Bu iz, Martin Kleppmann’ın akademik bir makale yazarken yaptığı işlemlerin karakter düzeyinde kaydıdır
    • İzde 260.000 düzenleme bulunur ve nihai belge boyutu yaklaşık 100.000 karakterdir
    • Eşzamanlı düzenleme içermez
    • Test yalnızca izin yerelde uygulanma süresini ölçer
    • Ortam olarak Ryzen 5800x iş istasyonu, Nodejs v16.1 ve Rust 1.52 kullanılmıştır
  • Automerge v1.0.0-preview2, bu izi işlemek için 291 saniye harcadı ve işlem sonunda RAM kullanımı 880MB oldu
    • Bu da tuş vuruşu başına yaklaşık 10KB RAM kullanımı anlamına geliyor
    • Tepe RAM kullanımı 2.6GB idi
    • Yavaş spike anlarında tek bir düzenlemenin işlenmesi 1.8 saniye sürdü
  • JavaScript string üzerinde doğrudan splice yapan baseline, aynı düzenlemeleri 0.61 saniye ve 0.1MB RAM ile işledi; ancak bu sadece karşılaştırma için kullanılan ve işbirlikçi düzenleme için gereken bilgilerin tamamını atan bir baseline’dı
  • Automerge’ün yavaş olmasının birkaç uygulama kaynaklı nedeni var
    • Belge büyüdükçe ağaç tabanlı veri yapısı büyüyor ve yavaşlıyor
    • Immutablejs yoğun kullanıldığı için V8 optimizer ve GC’nin verimli optimize etmesi zorlaşıyor
    • Eklenen her karakter ayrı bir öğe olarak ele alındığından paste işlemleri de çok sayıda öğe halinde işleniyor
  • Automerge ekibi, Rust uygulaması olan automerge-rs’i WASM üzerinden kullanan alternatif bir uygulama üzerinde çalışıyordu
    • O dönemde master branch baz alındığında bu testte ortalama performans hızlanmamıştı; ancak bellek kullanımı yarıya inmiş ve performans dalgalanması daha yumuşak hale gelmişti

Yjs tarzı düz liste uygulaması

  • Yjs, Kevin Jahns’ın geliştirdiği açık kaynaklı bir CRDT uygulamasıdır ve ağaç yerine tüm öğeleri tek bir düz listede saklar
  • Düz liste erişiminde yeni öğe, parent’ın hemen arkasından taranarak ekleme konumu bulunur; yani bir list CRDT’nin listeyle uygulanmış hali gibidir
  • Deneysel reference-crdts, Yjs’in YATA’sını ve Automerge’ün RGA’sını aynı yöntemle uygular
    • insert fonksiyonu, küçük farklar dışında Yjs ve Automerge davranışını neredeyse aynı codepath üzerinde işler
    • Anlamsal eşdeğerlik, fuzzer ile doğrulanmıştır
  • Bu yaklaşımın üç avantajı vardır
    • Dengesiz ağaçlar yerine flat array kullanıldığı için daha küçük ve daha hızlıdır
    • Kod daha basittir
    • Yjs, Automerge, Sync9 gibi çeşitli list CRDT’lerine uygulanabilir
  • Teoride aynı konuma çok sayıda eşzamanlı ekleme olduğunda yavaşlayabilir; ancak gerçek düzenlemede çoğu ekleme parent’ın hemen arkasına yapılır
  • reference-crdts uygulaması, Automerge’den yaklaşık 10 kat daha hızlıydı ve yaklaşık 30 kat daha az RAM kullanıyordu
Test İşleme süresi RAM kullanımı
automerge v1.0.0-preview2 291s 880MB
reference-crdts Automerge/Yjs 31s 28MB
Plain string edits in JS 0.61s 0.1MB

Tarama ve ekleme maliyetini azaltma

  • Düzleştirilmiş array uygulamasında iki darboğaz kalır
    • Ekleme yapılacak konumu bulmak için belgeyi taramak gerekir
    • doc.content.splice(destIdx, 0, newItem) ile array’in ortasına ekleme yapıldığında arkadaki öğeler kaydırılmalıdır
  • Silinmiş öğeler başka eklemeler tarafından referans alınabileceği için array’den çıkarılamaz; isDeleted gibi bir işaret bırakmak gerekir
    • Mevcut belge 100.000 karakter olsa bile geçmişteki öğeler dahil toplam 150.000 array item’ı olabilir
    • Belgenin 50.000. konumuna ekleme yapmak için silinmiş öğeleri atlayarak yaklaşık 75.000 item taranabilir
  • Bu yapıda, n öğeli bir belgeye ekleme yapmak yaklaşık n adım gerektirir; n karakter eklemek ise O(n²) olur
  • Yjs, insanların belge düzenleme biçimine uyacak şekilde son düzenleme konumunun (index, position) çiftini cache’ler
    • Bir sonraki düzenleme büyük olasılıkla önceki düzenleme konumunun yakınında olacağından ileri ve geri kısa tarama yapar
    • Birden fazla kullanıcının farklı konumları düzenlemesi durumuna karşı cache’lenmiş konum kümesini saklar
  • Yjs, array yerine çift yönlü bağlı liste kullanır; böylece konum bulunduktan sonra sabit zamanda ekleme yapar
  • Ayrıca insanların karakterleri art arda yazmasından yararlanarak helloyu 5 ayrı karakter öğesi yerine tek bir span olarak saklar
    • Yalnızca ID ve parent ardışık biçimde devam ettiğinde birleştirme yapılabilir
    • Bu veri kümesinde array entry sayısı 180.000’den 12.000’e düşerek 14 kat azalmıştır
Test İşleme süresi RAM kullanımı
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 ve Diamond types’ın range tree yaklaşımı

  • JavaScript nesneleri; content, deletion flag, ID, seq, parent gibi alanların pointer’larla dağılmış olduğu bir yapıya dönüşmeye yatkındır; bu da bellek parçalanmasını ve cache miss maliyetini artırır
  • Rust, bellek yerleşimini doğrudan kontrol etmeyi sağlar ve WebAssembly üzerinden web’de de kullanılabilir
  • Diamond types, Rust ile yazılmış bir CRDT uygulamasıdır; Yjs’e çok benzer, ancak içeride bağlı liste yerine range tree kullanır
  • İçteki range tree, biraz değiştirilmiş bir B-tree’dir
    • Tipik bir BTreeMap gibi key saklamak yerine, iç düğümler çocuklarda bulunan karakter sayılarının toplamını saklar
    • Belgedeki rastgele bir konuma erişim, ekleme ve silmeyi log(n) zamanda işler
  • 260.000 düzenlemelik trace bu ağaçta yaklaşık 3 yaprak düğüm seviyesiyle saklanır; bu sayede herhangi bir item yaklaşık 3 bellek okumasıyla bulunabilir
  • Remote edit merge için ID’ye göre B-tree arayan küçük bir index de vardır, ancak bu codepath bu benchmark’a dahil değildir
  • Yaprak düğümler, 32 entry’lik blokları sabit boyutlu array içinde sıkı biçimde saklar
    • 32 bucket size’ın, farklı boyutlarla yapılan benchmark’larda iyi çalıştığı ancak neden optimal olduğunun bilinmediği belirtilir
  • Diamond, diamond-js ile WASM’e derlenip Node.js üzerinde çağrıldığında aynı trace’i 193ms’de işler
    • Yjs’ten yaklaşık 5 kat daha hızlıdır
    • JavaScript string baseline’ından yaklaşık 3 kat daha hızlıdır
  • Native Rust çalıştırması, benchmark içinde 56ms kaydetmiştir
    • Automerge’den 5000 kattan fazla hızlıdır
    • Saniyede 4.6M operation işler
    • Toplam 260.000 düzenleme sırasında malloc çağrısı 1394 kez yapılmıştır
Test İşleme süresi RAM kullanımı
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 bilinmiyor
Diamond native 0.056s 1.1MB

Ropey ayrımı ve tradeoff

  • Diamond uygulaması, belge metin içeriğini doğrudan CRDT item listesinin içine koymak yerine ayrı bir veri yapısında saklar
  • Metin içeriği için Rust kütüphanesi Ropey kullanılır; Ropey de metin yönetimi için bir B-tree uygular
  • Bu yaklaşımın mühendislik tradeoffları vardır
    • Ropey, metne özel byte packing kullandığı için RAM kullanımını azaltabilir
    • Ekleme sırasında iki veri yapısının da güncellenmesi gerektiğinden hız 2 kattan fazla düşer ve WASM bundle boyutu 60KB’den 120KB’ye çıkar
    • VS Code gibi bir editor ile bağlandığında, editor belge kopyasını zaten tuttuğu için belge içeriğini CRDT yapısının içinde saklamak gerekmeyebilir
  • Yalnızca Ropey ile trace işlendiğinde 29ms sürer
  • Diamond native’de belge content güncellemesi kapatıldığında 23ms ve 0.96MB RAM elde edilir
    • Automerge’den yaklaşık 14.000 kat daha hızlıdır
    • Saniyede 11M operation işler
    • Bu sonuç, kullanışlılıktan çok CRDT metadata işleme sınırlarını görmek için yapılan bir deneye daha yakındır
Test İşleme süresi RAM kullanımı Veri yapısı
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 yok
Diamond WASM via Node.js 0.20s bilinmiyor B-tree
Diamond native 0.056s 1.1MB B-tree
Ropey Rust baseline 0.029s 0.2MB yok
Diamond native, no doc content 0.023s 0.96MB B-tree

Gerçek kütüphane seçimi için ölçütler

  • Bugün belge tabanlı bir işbirliği uygulaması geliştirilecekse Yjs kullanmak daha avantajlıdır
    • Yjs; performans, düşük bellek kullanımı ve destek ekosistemi açısından güçlüdür
    • Kevin Jahns, Yjs entegrasyon desteğini ücretli olarak da sunmaktadır
  • Automerge ekibi de 2021’de performansı en yüksek öncelikli konu olarak ele almış ve çeşitli tekniklerle Automerge’ü hızlandırmayı planlamıştır
  • Diamond çok hızlıdır, ancak Yjs ve Automerge düzeyinde özellik parity’sine ulaşması için hâlâ çok iş vardır
    • CRDT kütüphanelerinde operation hızı dışında binary encoding, network protocol, liste dışı veri yapıları, presence ve editor binding gibi unsurlar da gerekir
  • Veritabanı semantics’i gerekiyorsa, CRDT üzerinde iyi bir uygulanmış örnek bilinmediği; bunun yerine OT tabanlı ShareDB kullanılabileceği belirtilir
  • Redwood, P2P editing’i destekleyen ve tam CRDT desteği planlayan bir projedir

Ölçüm yönteminin kısıtları

  • Bu benchmark yalnızca yerel düzenleme trace’inin yeniden oynatılma süresi ve RAM kullanımını ölçüyor
  • Yerel kullanıcı girdisinin yeterince hızlı olması yeterlidir; CRDT tek bir local edit’i yaklaşık 1 ms veya altında işleyebiliyorsa, daha yüksek hız çok da önemli olmayabilir
    • Automerge de talihsiz GC pause durumları dışında genel olarak bu seviyeyi karşılıyor
  • Aslında daha önemli olan başka metrikler var
    • Belgenin disk veya ağ üzerinde kapladığı byte miktarı
    • Kaydetme ve yükleme için geçen süre
    • Kayıtlı belgenin veritabanı içinde güncellenme süresi
  • Kullanılan trace yalnızca tek kullanıcılı düzenlemeleri içeriyor; bu yüzden çok sayıda eşzamanlı düzenlemenin olduğu pathological case’ler kalmış olabilir
  • Şu anda Yjs veya Automerge ile veritabanındaki tek bir nesneyi güncellemek için genellikle tüm belgeyi RAM’e yükleyip değiştirmek ve ardından tüm belgeyi yeniden kaydetmek gerekiyor; bu da yavaş olabilir
    • Kevin, Yjs provider uygun şekilde ayarlanırsa bunun makul bir biçimde uygulanabileceğini söylüyor
  • list CRDT’ler, silinen öğelere ait tombstone’lar nedeniyle doğası gereği büyümeye devam eder; pruning ise ayrı bir yaklaşımdır
    • Yjs’in GC algoritması ve Antimatter buna örnek olarak veriliyor
    • pruning, yazıda ele alınan veri yapısı optimizasyonlarından bağımsız bir sorun

Karşılaştırma tamamen kontrollü bir deney değil

  • Her optimizasyon aşaması aynı anda birden fazla değişkeni değiştirdiği için hız artışının tam nedenini ayrıştırmıyor
  • Automerge’den reference-crdts’ye geçerken değişen unsurlar birden fazlaydı
    • Temel veri yapısı ağaçtan listeye geçti
    • Immutablejs kaldırıldı
    • Automerge frontend/backend protocol’ü ve çeşitli Uint8Array yapıları ortadan kalktı
    • JavaScript stili fonksiyonelden imperative’e geçti
  • reference-crdts’den Yjs’e, Yjs’ten Diamond’a geçerken de değişimler tek bir nedene ayrıştırılmıyor
  • automerge-rs’nin bu testte Automerge’den daha hızlı olmaması, Diamond performansının yalnızca Rust etkisi olmadığını gösteren bir dayanak; ancak kesin katkı payı bilinmiyor
  • RGA ile YATA’yı aynı implementasyon biçimiyle karşılaştırmak da, “eşzamanlı birleştirme davranışının fiilen benzer olduğu ve davranış değişse bile implementasyon performansının korunduğu” varsayımına dayanıyor
    • reference CRDT implementation içinde Yjs ve Automerge davranışı neredeyse aynı codepath ve aynı performansı gösteriyor
    • conflict-heavy trace’lerde performans farkı olabilir, ancak bunun pratikte çok nadir görüldüğü düşünülüyor
  • Yjs, her item’ın ne zaman silindiğini saklamıyor; yalnızca silinip silinmediğini saklıyor
    • Diamond’da silinme anını saklamak, bellek kullanımını 1.12MB’den 2.34MB’ye çıkarıyor ve yaklaşık %5 yavaşlatıyor
    • Bu yazıdaki tüm Diamond benchmark’ları, Yjs yaklaşımına uyarlanmış yjs-style branch kullanıyor

Benchmark kodu ve yeniden üretim materyalleri

İlgili okumalar

1 yorum

 
GN⁺ 2024-08-28
Hacker News yorumları

  • 2 baytlık tamsayı kullanıldıysa bunun nedeni büyük olasılıkla 64 baytlık cache line idi
    32 giriş tam olarak tek bir cache line ediyor; böylece her cache line bir bucket’ın tamamını taşımış ve pahalı ana bellek aktarımlarını azaltmış olurdu

    • Knuth’un sonraki programları benchmark etme biçimini sevmiştim
      Temelde bir şeyin bellekten kaç kez okunması gerektiğini sayan sayaçlar ekliyor; benzer şekilde cache line’ların kaç kez boşaltılması gerektiğini yaklaşık olarak hesaplamak mümkün mü merak ediyorum
    • Batch boyutuna göre benchmark yapınca bellek hiyerarşisiyle ilgili büyük sıçramalar sık görülür
      Word boyutu (64 bit), cache hizalı fetch boyutu (genellikle yukarıda sözü edilen 64 bayt), OS sayfa boyutu (4~16 KB), L1 boyutu (çekirdek başına yaklaşık 80 KB), L2 (birkaç MB düzeyi) gibi sınırlarda sıçramalar olur

  • Gerçek hizmetlerde CRDT kullanıp deneyiminin çok iyi olduğu uygulamaların hangileri olduğunu merak ediyorum
    Notion’ın bunlardan biri olduğunu hatırlıyorum ama pratikte Notion’da iki kişinin birlikte not alması, Google Docs’a kıyasla neredeyse kullanılamaz düzeyde

    • Thymer[1] her şey için CRDT kullanıyor
      İşler ve planlama için bir IDE; çok kullanıcılı bir uygulama, uçtan uca şifreleme, offline-first yaklaşım, isteğe bağlı self-hosting destekliyor ve tüm çalışma alanı tek bir graph olduğundan CRDT doğal bir seçimdi
      Thymer’daki tüm işlemler az sayıda CRDT dönüşümüne indirgeniyor. Metin taşıma/kopyalama, “frontmatter” özelliklerini değiştirme, kart sürükleme, dosya yükleme, tag ekleme; hepsi aynı birkaç CRDT işlemiyle ele alınıyor
      Başta kütüphane olmadan uygulamak çok iş çıkardı, ancak uygulama durumu tek bir graph ise sayfalar arasında metin taşıma, backlink’leri olan sayfa bağlantıları, transclusion gibi özellikleri senkronizasyon derdi olmadan geliştirebilmek buna fazlasıyla değdi
      CRDT tüm istemcilerin aynı duruma yakınsamasını garanti eder; ayrıca doğası gereği append-only olduğundan belirli bir ana ait sürüm yönetimi de bedavaya gelir
      Yine de performans nedeniyle bazı tavizler verdik. Sürüm geçmişi çok fazla veri tuttuğu için offline sunulmuyor; bazı durumlarda da çakışma çözümü için son yazan kazanır yaklaşımını kullanıyoruz
      Genel olarak, özellikle uygulamayı en baştan CRDT düşünerek tasarlıyorsanız çok değerli. Daha geleneksel bir AJAX uygulamasına sonradan çok kullanıcılı özellikler eklenen bir durumda CRDT kullanmazdım
      CRDT değişiklikleri önce iyimser biçimde uygulanır; yetkili olay sırası belirlendiğinde tüm istemcilerin son paylaşılan duruma geri dönüp tüm olayları doğru sırayla yeniden uygulaması gerekir
      Uzun süre offline kaldıysanız günlerce süren değişiklikleri geri alıp yeniden uygulamak gerekebilir. Kullanıcı arka planda kaç tane tree dönüşümü olduğunu bilmez, ama CRDT uygulamanın tüm tasarımını etkiler
      Bugün popüler olan uygulamaların çoğu, CRDT dönüşümlerinin henüz iyi anlaşılmadığı bir dönemde tasarlandı
      [1] https://thymer.com (neredeyse betaya hazır)
    • Bugünkü Notion, liste verilerindeki blok sırası gibi bazı niyet koruyan işlemleri sınırlı biçimde içeren bir son yazan kazanır sistemi
      Metin son yazan kazanır; her blok metni veya özelliği de son yazan kazanır register’ı. Blok metni için yeni bir CRDT formatı üzerinde çalışılıyor
    • iCloud servislerinin çoğunun içeride CRDT kullandığını biliyorum
      Notes ve Reminders buna dahil; Photos da öyle olabilir. Backend’in bir parçası olarak FoundationDB de kullanıldığını, sarhoş bir eski Apple SRE’sinden bir barda duymuştum
    • Linear: https://linear.app/
      Local First Conf konuşmasına da bakmaya değer: https://youtu.be/VLgmjzERT08
    • Biraz daha düşününce insanların hemen aklına gelmeyebilecek bir örnek daha var
      Herhangi bir biçimde rollback veya düzeltme yapan network oyunlarının tamamı buna yakın. Best-effort yaklaşımının yanında rollback’i yedek yol olarak kullanan bu biçim, yaygın kullanılan CRDT’ler içinde kullanıcı deneyimi açısından en iyi tür olabilir
      Katı akademik anlamda CRDT değil. Teknik olarak oyun durumu tüm istemcilere tamamen kopyalanmıyor; her istemci yalnızca kısmi oyun durumu alıyor
      Ayrıca oyun istemcilerinin düşük gecikmeli senkronizasyona ihtiyacı var ve akademik olarak buna “coordination” denebilir. Pratikte istemci, çakışma çözümü veya rollback düzeltmesi geri gelmeden önce giriş sonucunu olasılıksal olarak yerelde kabul edip render ediyor
      Kılı kırk yaranlar olabilir, ama üçüncü örneğe kadar bakınca ortak tema görünür. En popüler, kullanımı en iyi ve iyi uygulanmış CRDT’ler aslında akademik kuralları çiğniyor
      Bu, aşırı akademik düşünce modelinin tipik tuzağı. Gerçek dünyadaki algoritmalar ve veri tipleri, akademik “kural kitapları”ndan çoğu zaman çok daha yaratıcıdır. Örneğin Timsort böyledir
      Makale hakemliği için değil, gerçek kullanıcılar için ürün yapıyorsanız aşırı mühendislik/akademik tuzaklara düşmemelisiniz. Akademik kuralları öğrenin ama bilerek çiğneyin; yalnızca akademisyenler arasında yararlı olacak kadar katı tanımlanmış kavramları kusursuz uygulamaya çalışmak yerine gerçek değer katıp kullanımı iyi hale getirin

  • CRDT güçlü olsa da, işlem tabanlı da olsa durum tabanlı da olsa geçmiş işlemlerin veya öğelerin izlerini bırakması üzücü
    Sıkıştırma yapılsa bile bu hâlâ bir dezavantaj ve benimsemeyi düşündüren bir nokta
    Yine de bu tartışma sayesinde Dropbox, Syncthing gibi dosya tabanlı depolar üzerinde çakışmasız algoritmalar ya da ince taneli çakışma çözümleme algoritmaları uygulama olasılığı ilgimi çekti

    • Yazının yazarıyım. Bu konuşmayı çok yaptım ve CRDT tarafında da sıkça konuşulur; ama gerçekte, en azından metin düzenlemede ek yük o kadar küçük ki pratikte sorun olacağını sanmıyorum
      CRDT sonrası projem Diamond Types, temelde zaman geçtikçe sınırsız büyür; ama ek yük genellikle şimdiye kadar girilen karakter başına 1 bayttan azdır
      Saklanan metin için LZ4 sıkıştırmasını açarsanız, Diamond Types ile düzenlenmiş belgeler tüm düzenleme geçmişini saklamasına rağmen çoğu zaman nihai belge durumundan daha küçük olur
      Bunu teknik olarak çözmenin birkaç yolunu biliyorum, ama çoğu sistemde bunun gerçek bir sorun olduğundan emin değilim
      yjs'yi bir 3D modelleme aracında kullanan birinin sorun yaşadığını duydum. Çünkü bir nesneyi sürüklerken fare her piksel hareket ettiğinde kalıcı bir düzenleme oluşturuyordu
      Böyle işler için, çoğu CRDT kütüphanesinin desteklemediği geçici düzenlemeleri kullanmanın daha akıllıca olduğunu düşünüyorum
      Bu arada Git'te de aynı sorun var. Depo zamanla büyür ve modern CRDT kütüphaneleri kullanıldığındakinden çok daha hızlı büyür. Ama kimse pek umursamıyor gibi
      Git'te sığ klonlama mümkün, ama neredeyse kimse yapmıyor. İsterseniz CRDT'de de aynısını yapabilirsiniz
    • Tamamen merkeziyetsiz bir sistem kurmuyorsanız, CRDT'nin gerektirdiği kısıtların bir kısmını gevşetebilirsiniz
      Örneğin tüm istemcilerin X tarihinden sonraki değişiklikleri aldığı garanti edilebiliyorsa, o tarihten önceki işlemler güvenle atılabilir
    • Tüm işlem günlüğü ve deterministik birleştirme, değişmez blok depolarıyla iyi uyum sağlar; güvenlik, performans ve maliyet açısından da avantajlar sağlayabilir
      Bu alandaki güncel araştırmalardan yararlanmak için Fireproof[1]'i geliştiriyorum
      Değişmez veriyi içerik adreslemeli hale getirmenin ek bir avantajı da var: her işlem kriptografik olarak garanti edilen bir kanıta ya da farka indirgenir. Nedensel tutarlılık dayatılabilir ve anlık görüntülere kararlı referanslar oluşturulabilir
      Yani etkileşimli, çevrimdışı çalışan ve kayıpsız birleşen bir veritabanını uçta veya tarayıcıda çalıştırırken, geçmişte merkezi veritabanlarından ya da blokzincirlerden beklenen bütünlüğe de sahip olabilirsiniz
      Örneğin imzalanacak bir PDF'ye ya da akıllı sözleşmeye bir anlık görüntü CID'si koyarak, referans verilen durumla ilgili belirsizliği ortadan kaldırabilirsiniz
      [1] https://github.com/fireproof-storage/fireproof
    • CRDT kavramının kendisinde geçmiş işlemlerin veya öğelerin izlerini bırakmayı gerektiren bir şart yok
      Sonuçta belirli bir veri tipinin ya da veritabanının uyduğu matematiksel yasalar kümesi hakkında kapsayıcı konuşmaktansa, somut uygulamaları eleştirmek daha doğru
    • Geçmiş silinebiliyorsa neyden endişe edildiğini merak ediyorum

  • 2021 tarihli bir yazı ve Automerge'ün Rust uygulaması da işin içine girmiş gibi görünüyor; güncellenmiş benchmark'ları görmek ilginç olurdu

    • Yazının yazarıyım. Yjs'nin de Rust ile yeniden yazılmış yrs sürümü var ve JavaScript sürümünden çok daha hızlı
      Bu sorunu çözmek için tamamen farklı, yeni bir yaklaşımım da var
      Benchmark'ları güncellemek kesinlikle iyi olurdu. Hepsi daha hızlı hale geldi

  • İçeriğin önemli bir kısmını anlamakta zorlandım, ama yazı o kadar iyi yazılmış ki durmadan okumaya devam ettiren ender yazılardan biri

  • Önceki ilgili tartışmalar şunlar
    https://news.ycombinator.com/item?id=28017204 (3 yıl önce, 151 yorum)
    https://news.ycombinator.com/item?id=33903563 (2 yıl önce, 22 yorum)
    https://news.ycombinator.com/item?id=41372833 (mevcut gönderi)
    https://news.ycombinator.com/item?id=41373288 (mevcut yorum)

  • Mevcut GitHub Readme[0]'den alıntılarsak, o blog yazısından sonra performansın bir kez daha 10~80 kat arttığı söyleniyor
    [0] https://github.com/josephg/diamond-types

  • CRDT'nin neden yavaş olduğunu açıklayabilseniz iyi olurdu
    Bu yazı geleceği gösteriyor gibi: https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
    Bunu alıp Y.js veya Automerge ile karşılaştırmak güzel olurdu: https://github.com/canvasxyz/okra-js

    • Yazının yazarıyım. Temel sebep, birçok CRDT kütüphanesinin akademisyenler tarafından yazılmış olması ve onların optimizasyon için yeterli zamanı, becerisi ya da ilgisi olmamasıydı
      Bu yazıyı birkaç yıl önce yazdığımdan beri başlıca CRDT kütüphanelerinin hepsi birkaç basamak ölçeğinde hızlandı

  • Birkaç yıl önce bu yazıya tesadüfen rastladığımı hatırlıyorum
    Gerçekten çok eğlenceli bir yazı ve son birkaç yıldaki en sevdiğim yazılardan biri

    • Başlığın muhtemelen CRDTs go brrr olduğunu hatırlıyorum

  • “WASM neden yerel çalıştırmadan 4 kat yavaş?” sorusuna, tüm string işlemlerinin WASM belleğine kopyalanması, sonuç hesaplanınca da tekrar JS’e kopyalanması gerektiği için olduğunu düşünmüştüm
    Yanılıyor muyum? Bağlamı yanlış mı anladım? Gerçekten merak ediyorum

    • Yazının yazarıyım. Bu yazı birkaç yıl öncesinden, ama hatırladığım kadarıyla o kısmı kontrol altına almıştım. Yani sorun FFI değildi
      Süreyi ölçmeden önce tüm kaydı wasm’in içine yüklemiştim ve wasm bağlamının kendisinde çalışan, Rust ile yazılmış bir iç döngüde işlemi yapmıştım. wasm çağrısı yalnızca iki kez kadardı
      4 kat yavaşlamanın nedeni FFI değil, algoritma kodunun kendisinin gerçekten 4 kat daha yavaş çalışmasıydı
      Şimdi benchmark’ı tekrar çalıştırmak ilginç olabilir. Derleyicilerin wasm çıktısı da iyileşti, wasm runtime’ları da hızlanmış olmalı. Benchmark kodu hâlâ bir yerlerde duruyor olmalı
    • Makul bir neden gibi görünüyor
      Ayrı bir alanda sürekli takıldığım konu, çoklu iş parçacığı meselesinin kolay olmaması ve kütüphane ile araç desteğinin de eksiksiz olmaması
      Oyun motorlarını ya da ffmpeg, zip gibi yardımcı program binary’lerini tarayıcıda çalıştırmayı denedim; bu yüzden çok yavaştı
    • Bence daha iyi soru, neden ikisinin aynı olmasını beklediğimiz
      Hiç WASM yorumlayıcısı ya da JIT’iyle uğraşmadım, ama tek bir çeviri katmanından geçmek yerine birden çok katmandan geçmenin daha iyi olduğu durumlar ne kadar sık görülür ki?
      Yüksek seviyeli kodu WASM’e ya da herhangi bir assembly diline çevirdiğinizde, yüksek seviyeli kodda bulunan birçok niyeti kaybedersiniz
      Düşük seviyeli kodda, hedefe ulaşmak için dile özgü deyimlerin bir listesini sıkça görürsünüz; bunların gerçek makinede doğrudan karşılığı olabilir de olmayabilir de
      Modern x86-64’te, WASM’de yapılabileceklerden çok daha güçlü çok sayıda komut var
      Elbette decompiler’lar da var; WASM JIT’in görece basit pattern matching ile iyi yerel kod üretebileceği makro işlem birleştirme listeleri de olabilir. Muhtemelen öyle değildir ve çapraz platform optimizasyonu daha zor olur ama
      LLVM de kusursuz değil; sonradan çalışan bir optimizer’ın iyileştirebileceği kolay noktalar mutlaka vardır. Bu yüzden WASM’i LLVM’in yerel çıktısından daha hızlı yapmak teorik olarak imkânsız değil
      Ama çok iyi tasarlanmış bir planınız yoksa ya da fiilen hedef komut kümesi mimarisinin desteklediklerinin bir üst kümesi olan bir komut kümesi oluşturmuyorsanız, aynı düzeyde sonuç almak bence çok zor
      Bana göre WASM daha çok bir alt kümeye yakın; bu yüzden işlemleri standartlaştırıp gerçek zamanda tekrar birleştirmek kolay değil. Tamamen imkânsız olmasa da ciddi bir mühendislik başarısı gerektirir
      Sezgisel olarak, İngilizce yazılmış bir kitabı çok farklı ve birkaç bin kelimeyle sınırlı bir dile çevirip sonra tekrar İngilizceye çevirirseniz tam olarak aynı metni elde etmezsiniz
      İngilizcede tek kelimeyle anlatılacak bir kavramı bir paragrafla açıklamak zorunda kalabilirsiniz. Asıl İngilizceyi geri kazanmak için ya her şey için 1:1 çeviri ya da iki çevirmenin üzerinde anlaştığı paragraf→tek kelime çeviri listesi gerekir