Daha Hızlı CRDT'ler (2021)

5000 kat daha hızlı CRDT: optimizasyon macerası

Giriş

• Birkaç yıl önce, Fransız araştırmacılar gerçek zamanlı ortak düzenleme algoritmalarını karşılaştıran bir makale yayımladı
• Birden fazla algoritmayı uygulayıp performanslarını kıyasladılar
• Bazı algoritmalar basit bir yapıştırma işlemi için 3 saniyeden fazla sürdü
• Sorunlu algoritma, ShareJS'te kullanılan algoritmaydı

Sorunun nedeni

• Makalede büyük bir metin yapıştırılırken işlem 1000 ayrı operasyona bölünerek ele alındı
• Bu, algoritmanın kendisinden değil, uygulamadan kaynaklanan bir sorundu

CRDT'nin cazibesi

• CRDT (Conflict-Free Replicated Data Types), birden fazla kullanıcının aynı anda veriyi düzenlemesine olanak tanır
• Yerelde gecikme olmadan çalışılabilir ve senkronizasyon sırasında tutarlılık otomatik olarak korunur
• Merkezi sunucu olmadan da çalışabilir

Automerge'ün sorunları

• Automerge, ortak düzenleme için kullanılan ve RGA algoritmasını temel alan bir kütüphanedir
• Belgedeki her karakteri benzersiz bir ID ile yönetir ve ekleme sırasında ebeveyn öğeyi belirtir
• Performans sorunları nedeniyle 260.000 düzenleme işlemini işlemek 5 dakika sürüyordu
• Bellek kullanımı da çok yüksekti

Performans optimizasyonu

• Automerge'ün performans sorunları, karmaşık ağaç tabanlı veri yapıları ve Immutablejs kullanımı nedeniyle ortaya çıkıyordu
• Yjs, tek bir düz liste kullanarak performansı büyük ölçüde artırdı
• Yjs, ekleme konumunu bulmak için önbellek kullanıyor ve eklemeleri verimli işlemek için çift yönlü bağlı liste kullanıyor
• Yjs 30 kat daha hızlı ve daha az bellek kullanıyor

Rust'a geçiş

• Rust, bellek yerleşimini kontrol etmeyi mümkün kıldığı için performansı daha da artırabilir
• Diamond types adlı yeni bir CRDT uygulamasıyla Yjs'ten 5 kat daha hızlı performans elde edildi
• Rust ile yazılmış Diamond, 260.000 düzenleme işlemini yalnızca 56 milisaniyede işliyordu

Sonuç

• Optimize edilmiş veri yapıları ve verimli bellek yönetimiyle CRDT performansı büyük ölçüde iyileştirilebilir
• Rust gibi düşük seviyeli diller kullanılarak daha da yüksek performans elde edilebilir

GN⁺ özeti

• CRDT, ortak düzenlemenin geleceği olarak merkezi sunucu olmadan da tutarlılığı koruyabilen güçlü bir araçtır
• Automerge'ün performans sorunları, karmaşık veri yapıları ve verimsiz bellek kullanımından kaynaklanıyordu
• Yjs ve Diamond types, basit ve verimli veri yapıları kullanarak performansı büyük ölçüde artırıyor
• Rust gibi düşük seviyeli diller kullanılarak daha da yüksek performans elde edilebilir
• Ortak düzenleme araçları geliştirirken Yjs ve Diamond types değerlendirilebilir

[GN⁺]

Hacker News yorumları

• 32 girdinin en verimli olmasının nedeni, cache line boyutunun 64 byte olması

  • 2 byte’lık tamsayılar kullanıldığında, 32 girdi tam olarak tek bir cache line’a sığar ve ana bellek aktarımını azaltabilir

• CRDT kullanan gerçek uygulamalar arasında iyi bir deneyim sunan örnekler bulmak zor

  • Notion’da iki kişi aynı anda not yazdığında kullanılabilirlik, Google Docs’a kıyasla daha kötü

• CRDT’ler güçlü, ancak geçmişteki işlemleri (veya öğeleri) saklama gibi bir dezavantajları var

  • Sıkıştırma kullanılsa bile bu hâlâ bir dezavantaj olmaya devam ediyor ve benimsenmesi konusunda endişe yaratıyor
  • Buna rağmen dosya tabanlı depolama sağlayıcılarında (Dropbox, Syncthing vb.) çatışmasız algoritmaların uygulanma olasılığı ilgi çekici geliyor

• Mevcut GitHub README alıntısı:

  • Blog yazısından sonra performans 10-80 kat arttı

• Bu makale, içeriği zor olsa da çok iyi yazılmış; okumayı bırakamadım

• Hiyerarşi kullanılmasını görünce, bunun yerine nested set kullanılıp kullanılmadığını merak ettim

  • Okuma işlemlerindeki kazancın ekleme işlemlerindeki kaybı telafi edip edemeyeceğine dair bir fikrim yok

• Bu gönderiye birkaç yıl önce tesadüfen rastladım

  • Son birkaç yılda okuduğum en eğlenceli gönderilerden biriydi

• WASM’in neden native çalıştırmadan 4 kat daha yavaş olduğunu merak ediyorum

  • Bunun nedeninin, tüm string işlemlerinin WASM belleğine kopyalanması ve sonuç hesaplandıktan sonra tekrar JS’e kopyalanması olduğunu düşündüm
  • Bu bağlamı yanlış anlayıp anlamadığımı merak ediyorum

• Automerge’in Rust implementasyonu tamamlandığına göre, güncellenmiş benchmark’ları görmek ilginç olurdu