CRDT pohon yang dapat dipindahkan dan implementasi Loro

• Movable tree CRDTs and Loro's implementation

• Latar belakang

  • Dalam sistem terdistribusi dan perangkat lunak kolaboratif, mengelola hubungan hierarkis itu kompleks
  • Saat memodelkan perpindahan dengan menggabungkan penghapusan dan penyisipan dalam struktur data, sulit menyelesaikan konflik sekaligus memenuhi ekspektasi pengguna
  • Sebagai contoh, jika node yang sama dipindahkan secara bersamaan ke induk yang berbeda, node duplikat dengan isi yang sama dapat dibuat

• Konflik pada pohon yang dapat dipindahkan

  • Operasi utama pada pohon yang dapat dipindahkan: membuat, menghapus, memindahkan
  • Konflik yang dapat terjadi saat menyinkronkan operasi serempak:
    • node yang sama dihapus dan dipindahkan
    • node yang sama dipindahkan ke bawah node yang berbeda
    • node lain dipindahkan sehingga menimbulkan siklus
    • node turunan dipindahkan saat node leluhur sedang dihapus

• Penghapusan dan perpindahan pada node yang sama

  • Relatif mudah diselesaikan
  • Berdasarkan timestamp sistem terdistribusi atau kebutuhan spesifik aplikasi, satu operasi diterapkan dan operasi lainnya diabaikan

• Memindahkan node yang sama ke bawah induk yang berbeda

  • Menggabungkan operasi perpindahan serempak lebih rumit
  • Bergantung pada aplikasinya, berbagai pendekatan bisa diambil:
    • menghapus node dan membuat salinannya di bawah node induk lain
    • mengizinkan node terhubung ke dua induk (umumnya tidak diizinkan)
    • mengurutkan semua operasi dan menerapkannya secara berurutan

• Timbulnya siklus akibat perpindahan node lain

  • Menyelesaikan siklus akibat operasi perpindahan serempak itu rumit
  • Beberapa solusi:
    • memunculkan error
    • merender node siklik di area "timeout" khusus
    • memproses operasi perpindahan di server
    • menggunakan topological sort
    • menyembunyikan edge yang menyebabkan siklus

• Penghapusan node leluhur dan perpindahan node turunan

  • Perpindahan node turunan saat node leluhur dihapus mudah terlewatkan
  • Jika semua node turunan langsung dihapus, hal ini dapat disalahartikan sebagai kehilangan data

• Cara aplikasi populer menangani konflik

  • Dropbox: memperlakukan perpindahan file sebagai hapus lalu buat, tetapi ada risiko kehilangan data
  • Figma: server terpusat mendeteksi siklus dan menolak operasi untuk menjaga konsistensi

• CRDT pohon yang dapat dipindahkan

  • Menggunakan CRDT alih-alih solusi terpusat
  • Algoritme awal berbasis CRDT sulit diimplementasikan dan memiliki overhead penyimpanan yang besar
  • Berkat optimasi berkelanjutan, beberapa algoritme sinkronisasi pohon berbasis CRDT kini cocok untuk lingkungan produksi

• Operasi perpindahan dengan ketersediaan tinggi untuk replicated tree

  • Menyatukan tiga operasi pohon (membuat, menghapus, memindahkan) menjadi operasi perpindahan
  • Operasi perpindahan didefinisikan sebagai Move t p m c
  • Penghapusan node ditangani dengan memindahkannya ke node TRASH

• Timestamp logis yang diurutkan secara global

  • Menggunakan timestamp Lamport untuk menentukan urutan kausal peristiwa dalam sistem terdistribusi
  • Angka yang lebih kecil berarti peristiwa yang lebih awal

• Menerapkan operasi jarak jauh

  • Keamanan operasi bergantung pada keadaan pohon saat operasi diterapkan
  • Saat menangani update jarak jauh, operasi terbaru dibatalkan, operasi baru disisipkan, lalu operasi yang dibatalkan diterapkan kembali

• CRDT: hierarki pohon yang dapat berubah

  • Setiap node melacak semua node induk historis dan memberinya penghitung
  • Jika siklus terjadi saat sinkronisasi, node akan dihubungkan kembali ke node induk historis terdekat

• Implementasi CRDT pohon yang dapat dipindahkan di Loro

  • Mengimplementasikan algoritme Martin Kleppmann untuk memberikan performa tinggi
  • Mengintegrasikan algoritme Fractional Index agar pengurutan node anak dimungkinkan

• Potensi konflik dalam pengurutan node anak

  • Saat beberapa node disisipkan pada posisi yang sama, Fractional Index yang sama dapat diberikan
  • Menggunakan PeerID untuk menentukan urutan relatif dari Fractional Index yang sama

• Implementasi dan ukuran encoding

  • Fractional Index menyediakan urutan node
  • Dalam kasus terburuk, ukuran encoding memerlukan byte tambahan, tetapi ini jarang terjadi

• Pekerjaan terkait

  • Selain Fractional Index, ada juga movable list CRDT
  • Fractional Index sederhana untuk diimplementasikan dan berguna ketika hanya urutan relatif yang diperlukan

• Benchmark

  • Melakukan benchmark performa implementasi movable tree milik Loro
  • Dapat mendukung kolaborasi real-time dan checkout versi historis yang mulus

• Ringkasan

  • Memperkenalkan kesulitan implementasi CRDT pohon yang dapat dipindahkan dan dua algoritme inovatif
  • Loro mengintegrasikan algoritme Martin Kleppmann dan Fractional Index untuk memenuhi beragam skenario aplikasi

• Ringkasan GN⁺

  • CRDT pohon yang dapat dipindahkan memainkan peran penting dalam mengelola struktur data hierarkis di sistem terdistribusi
  • Loro menawarkan performa tinggi dan penyelesaian konflik yang efisien, sehingga cocok untuk aplikasi kolaborasi real-time
  • Menggunakan Fractional Index untuk menyelesaikan masalah pengurutan node anak
  • Proyek lain dengan fungsi serupa termasuk Figma dan Dropbox

[GN⁺]

Komentar Hacker News

• Sedang mengembangkan editor multipemain baru

  • Mendukung pekerjaan teks dan outliner
  • Dokumen diubah menjadi struktur pohon besar
  • Disinkronkan menggunakan operasi insmov (pindah atau sisip)
  • Saat server mengirim perubahan, klien menerapkannya kembali
  • Dalam sebagian besar kasus, tidak perlu membatalkan operasi
  • Hampir tidak ada masalah saat pembaruan real-time

• React Table Library dirilis sebagai open source

  • Menangani struktur pohon folder/file
  • Mendukung pemindahan folder/file, duplikasi, lazy loading, dan sebagainya
  • Jadi paham mengapa Google Drive hanya menampilkan dan mengedit pada tingkat hierarki yang sama

• Meminta saran

  • Menggunakan pohon besar yang terdenormalisasi di frontend
  • Mengelola profil pengguna dengan layout ubin
  • Mengirim data seminimal mungkin agar pembaruan aman
  • Dengan memakai CRDT, pengelolaan state tampaknya akan jauh lebih mudah
  • Sinkronisasi antar tab browser menjadi memungkinkan

• Saat menangani konten teks berformat seperti Google Docs/Zoho Writer, manipulasi pohon diperlukan

  • Sulit menyelesaikan masalah konflik konkurensi
  • Sepertinya bisa menggabungkan list CRDT dan tree CRDT
  • Perlu menambahkan alamat 2 dimensi ke semua operasi

• Penasaran apakah ada CRDT yang praktis untuk aplikasi padat data seperti gambar (piksel) dan model 3D

• Menganggap paragraf pertama terdengar seperti suara ChatGPT