CRDT yang Lebih Cepat (2021)

CRDT 5000x Lebih Cepat: Petualangan Optimasi

Pendahuluan

• Beberapa tahun lalu, para peneliti Prancis menerbitkan makalah yang membandingkan algoritma pengeditan kolaboratif real-time
• Mereka mengimplementasikan beberapa algoritma dan melakukan benchmark performa
• Beberapa algoritma membutuhkan lebih dari 3 detik hanya untuk operasi tempel sederhana
• Algoritma yang bermasalah adalah algoritma yang digunakan di ShareJS

Penyebab Masalah

• Dalam makalah tersebut, saat menempelkan teks besar, prosesnya dipecah menjadi 1000 operasi terpisah
• Ini bukan masalah pada algoritmanya sendiri, melainkan masalah implementasi

Daya Tarik CRDT

• CRDT (Conflict-Free Replicated Data Types) memungkinkan banyak pengguna mengedit data secara bersamaan
• Pengguna bisa bekerja secara lokal tanpa latensi, dan saat sinkronisasi konsistensi tetap terjaga secara otomatis
• Dapat bekerja bahkan tanpa server pusat

Masalah pada Automerge

• Automerge adalah pustaka untuk pengeditan kolaboratif yang berbasis pada algoritma RGA
• Setiap karakter dalam dokumen dikelola dengan ID unik, dan saat menyisipkan perlu menentukan item induk
• Karena masalah performa, memproses 260.000 operasi edit memerlukan waktu 5 menit
• Penggunaan memorinya juga sangat tinggi

Optimasi Performa

• Masalah performa Automerge disebabkan oleh struktur data berbasis tree yang kompleks dan penggunaan Immutablejs
• Yjs sangat meningkatkan performa dengan menggunakan satu flat list
• Yjs menggunakan cache untuk mencari posisi penyisipan, dan memakai doubly linked list agar penyisipan diproses secara efisien
• Yjs 30 kali lebih cepat dan juga menggunakan memori lebih sedikit

Beralih ke Rust

• Rust memungkinkan kontrol atas layout memori sehingga performa bisa ditingkatkan lebih jauh
• Melalui implementasi CRDT baru bernama Diamond types, dicapai performa 5 kali lebih cepat daripada Yjs
• Diamond yang diimplementasikan dengan Rust memproses 260.000 operasi edit hanya dalam 56 milidetik

Kesimpulan

• Dengan struktur data yang dioptimalkan dan pengelolaan memori yang efisien, performa CRDT dapat ditingkatkan secara signifikan
• Dengan menggunakan bahasa tingkat rendah seperti Rust, performa yang lebih cepat bisa dicapai

Ringkasan GN⁺

• CRDT adalah masa depan pengeditan kolaboratif, alat yang kuat untuk menjaga konsistensi bahkan tanpa server pusat
• Masalah performa Automerge berasal dari struktur data yang kompleks dan penggunaan memori yang tidak efisien
• Yjs dan Diamond types sangat meningkatkan performa dengan menggunakan struktur data yang sederhana dan efisien
• Dengan menggunakan bahasa tingkat rendah seperti Rust, performa yang lebih cepat bisa dicapai
• Saat mengembangkan alat pengeditan kolaboratif, Yjs dan Diamond types layak dipertimbangkan

[GN⁺]

Komentar Hacker News

• Alasan 32 entri paling efisien adalah karena cache line berukuran 64 byte

  • Jika menggunakan integer 2 byte, 32 entri pas tepat dalam satu cache line sehingga dapat mengurangi transfer memori utama

• Sulit menemukan contoh aplikasi nyata yang menggunakan CRDTs dan memberikan pengalaman yang baik

  • Notion terasa kurang nyaman digunakan dibanding Google Docs ketika dua orang menulis catatan secara bersamaan

• CRDTs kuat, tetapi punya kelemahan berupa jejak pekerjaan (atau elemen) historis yang tertinggal

  • Bahkan dengan kompresi, ini tetap menjadi kekurangan dan menimbulkan kekhawatiran dalam adopsi
  • Meski begitu, ada ketertarikan pada kemungkinan menerapkan algoritme bebas konflik pada penyedia penyimpanan berbasis file (Dropbox, Syncthing, dll.)

• Kutipan Readme GitHub saat ini:

  • Setelah postingan blog tersebut, performa meningkat 10-80 kali lipat

• Artikel ini ditulis dengan sangat baik sehingga meskipun isinya sulit, rasanya tidak bisa berhenti membaca

• Melihat penggunaan hierarki membuat penasaran apakah nested set dipertimbangkan sebagai gantinya

  • Tidak punya gambaran apakah keuntungan pada operasi baca dapat menutupi kerugian pada operasi penyisipan

• Beberapa tahun lalu, saya menemukan postingan ini secara kebetulan

  • Ini salah satu postingan paling menarik yang saya baca dalam beberapa tahun terakhir

• Penasaran mengapa WASM 4 kali lebih lambat daripada eksekusi native

  • Saya mengira itu karena semua operasi string harus disalin ke memori WASM lalu, setelah hasil dihitung, disalin kembali ke JS
  • Saya penasaran apakah saya salah memahami konteks ini

• Karena implementasi Rust untuk Automerge sudah selesai, akan menarik melihat benchmark yang diperbarui