- Saat struktur hierarkis diedit secara bersamaan dalam software kolaborasi, muncul konflik tree seperti node duplikat, siklus, dan pemindahan node anak dari ancestor yang dihapus; Loro mengimplementasikannya sebagai CRDT tree yang dapat dipindahkan
- Pendekatan Martin Kleppmann dkk. menyatukan pembuatan, penghapusan, dan pemindahan sebagai
Move t p m c, serta menangani penghapusan sebagai pemindahan ke node TRASH sehingga pemindahan node anak secara bersamaan tetap dipertahankan
- Urutan global dibuat dengan Lamport Timestamp dan Peer ID; jika operasi remote masuk di tengah urutan yang sudah ada, undo-do-redo digunakan untuk menghindari siklus
- Loro menggabungkan Fractional Index untuk mengurutkan sibling node, dan ketika indeks bertabrakan karena penyisipan bersamaan di posisi yang sama, hal itu ditangani dengan PeerID, jitter, dan pengaturan ulang indeks
- Dalam benchmark, Loro Movable Tree menjalankan 10.000 pemindahan acak setelah membuat 1.000 node dalam 28 ms, menunjukkan performa yang cukup untuk kolaborasi real-time dan checkout versi lama
Konflik yang muncul pada tree kolaboratif
- Saat mengelola relasi hierarkis dalam sistem terdistribusi dan software kolaborasi, jika pemindahan dimodelkan sebagai kombinasi penghapusan dan penyisipan, ekspektasi pengguna dan cara penyelesaian konflik mudah tidak selaras
- Jika node yang sama dipindahkan secara bersamaan ke parent berbeda di beberapa replica, satu node dapat dihapus dua kali lalu dibuat ulang di bawah dua parent, sehingga muncul node duplikat dengan isi yang sama
- Operasi dasar pada tree yang dapat dipindahkan terdiri dari tiga hal: create, delete, dan move
- Situasi yang terutama bermasalah saat sinkronisasi adalah sebagai berikut
- Node yang sama dihapus dan dipindahkan pada saat yang sama
- Node yang sama dipindahkan ke bawah parent yang berbeda
- Pemindahan node yang berbeda digabungkan sehingga menimbulkan siklus
- Node anak dipindahkan saat node ancestor sedang dihapus
Cara menangani tiap jenis konflik
- Jika penghapusan dan pemindahan node yang sama berkonflik, satu operasi dapat diterapkan dan operasi lain diabaikan berdasarkan timestamp sistem terdistribusi atau kebutuhan aplikasi
- Jika node yang sama dipindahkan ke bawah parent yang berbeda, pilihannya bergantung pada aplikasi
- Hapus node, lalu buat salinannya di bawah parent yang berbeda dan perlakukan secara independen setelahnya
- Membuat satu node menunjuk ke dua parent, tetapi ini merusak struktur tree sehingga umumnya sulit diterima
- Urutkan semua operasi lalu terapkan secara berurutan untuk menghasilkan hasil yang sama di semua peer
- Jika pemindahan node yang berbeda menciptakan siklus, penyelesaian konflik pada tree yang dapat dipindahkan menjadi sangat kompleks
- Matthew Weidner merangkum beberapa pendekatan seperti penanganan error, rendering area “time-out”, penolakan berbasis server, melewati operasi yang menciptakan siklus setelah topological sort, menyembunyikan edge tertentu saat rendering, dan mengembalikan ke parent sebelumnya
- Situasi ketika node anak dipindahkan saat node ancestor dihapus juga mudah terlewat
- Jika semua node anak dari ancestor langsung dihapus, pengguna dapat salah mengira datanya hilang
Pendekatan Dropbox dan Figma
- Pada awalnya, Dropbox menangani pemindahan file dalam dua tahap: menghapus dari lokasi asal lalu membuatnya di lokasi baru
- Jika listrik padam atau sistem crash di antara penghapusan dan pembuatan, ada risiko kehilangan data
- Saat ini, ketika beberapa orang mencoba memindahkan dan menyimpan file yang sama secara bersamaan, Dropbox mendeteksi konflik, biasanya menyimpan satu versi file asli, lalu membuat “conflicted copy” untuk perubahan salah satu pengguna
- Figma menganggap struktur tree sebagai bagian paling kompleks dalam sistem kolaborasi dan memberi tiap elemen properti
parent
- Server pusat memantau update dari banyak pengguna, dan jika sebuah operasi dapat menciptakan siklus, operasi tersebut ditolak
- Karena latensi jaringan, siklus dapat muncul sementara sebelum server menolaknya
- Dalam kasus ini, Figma menyembunyikan sementara elemen yang termasuk dalam siklus dan mempertahankan status sampai server secara resmi menolak operasi tersebut
- Penjelasan terkait dapat dilihat di artikel Figma tentang multiplayer technology
Dua pendekatan CRDT untuk tree yang dapat dipindahkan
- Alih-alih solusi terpusat, struktur tree kolaboratif dapat ditangani dengan CRDT
- Algoritme tree berbasis CRDT awal sulit diimplementasikan dan memiliki overhead penyimpanan besar, tetapi setelah optimasi dan perbaikan, muncul algoritme sinkronisasi tree yang cocok untuk beberapa lingkungan produksi
- Ada dua pendekatan representatif berbasis CRDT
Pendekatan Kleppmann: menyatukan semua operasi sebagai Move
- A highly-available move operation for replicated trees menyatukan pembuatan, penghapusan, dan pemindahan tree ke dalam satu operasi move
- Operasi move didefinisikan dengan empat nilai
Move t p m c
t: timestamp unik yang dapat diurutkan, seperti Lamport timestampp: ID node parentm: metadata yang terhubung dengan nodec: ID node child
- Jika
c belum ada di tree, ini menjadi operasi create yang membuat child c di bawah parent p
- Jika
c sudah ada, ini menjadi operasi move yang memindahkannya dari parent lama ke parent baru p
- Penghapusan ditangani dengan memindahkan node ke node
TRASH yang ditentukan
- Semua node anak dari
TRASH dianggap telah dihapus
- Namun node tetap disimpan di memori agar pengeditan bersamaan dapat memindahkan node tersebut ke node lain
- Ini adalah mekanisme untuk menangani situasi ketika penghapusan ancestor dan pemindahan node anak terjadi bersamaan
Pengurutan dan unsafe operation
- Karena penghapusan juga didefinisikan sebagai operasi move, “penghapusan dan pemindahan node yang sama” berubah menjadi konflik antara dua operasi move
- Masalah inti yang tersisa ada dua
- Memindahkan node yang sama ke bawah parent yang berbeda
- Memindahkan node yang berbeda hingga menciptakan siklus
- Jika semua operasi diurutkan secara linear dengan Lamport timestamp dan Peer ID, pemindahan bersamaan pada node yang sama juga direpresentasikan sebagai dua operasi berurutan
- Jika tree hanya dimodelkan dengan operasi move, situasi luar biasa dalam pengeditan bersamaan direduksi menjadi penciptaan siklus
- Operasi yang menciptakan siklus diperlakukan sebagai unsafe operation
- Algoritme mengurutkan semua operasi move berdasarkan timestamp
- Siklus dideteksi sebelum tiap operasi diterapkan
- Jika operasi menciptakan siklus, unsafe operation tersebut diabaikan agar struktur tree yang valid tetap terjaga
Lamport Timestamp dan penerapan operasi remote
- Lamport Timestamp memungkinkan penentuan urutan kausal event dalam sistem terdistribusi
- Setiap peer memiliki counter yang dimulai dari 0
- Ketika event lokal terjadi, counter dinaikkan 1 dan nilainya digunakan sebagai timestamp
- Saat peer
A mengirim pesan ke B, timestamp dilampirkan
B membandingkan logical clock miliknya dengan timestamp yang diterima dan memperbaruinya ke nilai yang lebih besar
- Pengurutan global pertama-tama membandingkan Lamport Timestamp, dan jika nilainya sama, menggunakan ID unik peer sebagai tie-breaker
- Jika update remote masuk di tengah rangkaian operasi yang sudah terurut, undo-do-redo diperlukan
- Batalkan operasi terbaru
- Sisipkan dan terapkan operasi baru
- Terapkan kembali operasi yang dibatalkan
- Agar operasi move dapat dibatalkan dengan cepat, old parent dari node target di-cache sebelum setiap move diterapkan
- Unsafe operation harus tetap dicatat meskipun efeknya diabaikan
- Keamanan operasi ditentukan secara dinamis
- Jika kemudian diterima update bahwa node lain yang sebelumnya menyebabkan siklus telah lebih dulu dihapus, operasi yang sebelumnya unsafe dapat menjadi safe
- Dalam proses undo, penanda ineffective diperlukan untuk menemukan parent target dari operasi terakhir yang benar-benar berdampak
Contoh undo-do-redo
- Jika operasi baru bergantung pada operasi yang belum ada secara lokal, berarti pembaruan versi perantara masih belum tersedia, sehingga operasi tersebut harus disimpan sementara di cache lalu diterapkan setelah pembaruan yang hilang diterima
- Jika
opId baru lebih besar daripada semua operasi yang ada, operasi dapat langsung diterapkan
- Jika safe, catat parent saat ini dari node target sebagai old parent lalu terapkan move
- Jika unsafe, tandai sebagai ineffective dan abaikan efeknya
- Jika
opId baru masuk di tengah urutan yang sudah ada, keluarkan operasi-operasi setelahnya satu per satu dan rollback, terapkan operasi baru, lalu terapkan kembali operasi yang di-rollback sesuai urutan
- Dalam alur contoh,
Peer1 secara lokal memindahkan C ke bawah B, lalu menerima operasi dari Peer0 yang memindahkan B ke bawah C
- Dalam urutan Lamport timestamp,
0:3 mendahului 1:3, jadi undo 1:3 terlebih dahulu untuk mengembalikan C ke old parent A
- Setelah itu, pindahkan
B ke bawah C dengan 0:3
- Kemudian redo
1:3 untuk mencoba memindahkan C ke bawah B, tetapi siklus terdeteksi sehingga tidak diterapkan
- Status tree tidak berubah dan proses undo-do-redo selesai
Pendekatan Evan Wallace: melacak parent masa lalu
- CRDT: Mutable Tree Hierarchy dari Evan Wallace membuat setiap node melacak semua node parent di masa lalu
- Setiap parent yang tercatat memiliki counter
- Nilai count parent baru lebih besar 1 daripada count semua parent masa lalu milik node tersebut
- Parent dengan count tertinggi menjadi parent saat ini
- Saat sinkronisasi, catatan parent juga ikut disinkronkan
- Jika terjadi siklus, algoritme heuristik akan menempelkan kembali node yang menyebabkan siklus ke parent masa lalu terdekat yang terhubung ke root tanpa membuat siklus
- Proses ini diulang sampai semua node dalam siklus kembali tertempel ke tree, sehingga struktur tree antar-replica tersinkronisasi
- Pendekatan ini tidak memerlukan prosedur undo-do-redo yang mahal, tetapi setiap kali menerima move jarak jauh, semua node harus diperiksa apakah terhubung ke root dan node yang membentuk siklus harus ditempelkan kembali, sehingga performanya bisa memburuk saat jumlah node besar
- Benchmark untuk perbandingan performa dibuat secara terpisah
Implementasi Movable Tree di Loro
- Loro mengimplementasikan algoritme A highly-available move operation for replicated trees dari Martin Kleppmann dkk.
- Algoritme ini menghasilkan performa tinggi di sebagian besar skenario nyata
- Proses inti undo-do-redo sangat mirip dengan cara Eg-walker (Event Graph Walker) di Loro menerapkan pembaruan jarak jauh
- Movable tree saja tidak menyelesaikan masalah urutan antar sibling node
- Dalam outline notes atau pengelolaan layer pada software desain grafis, pengurutan child node diperlukan
- Pengguna harus menyesuaikan urutan node dan menyinkronkannya dengan kolaborator atau perangkat lain
- Loro mengintegrasikan algoritme
Fractional Index agar child node pada movable tree dapat diurutkan
Fractional Index dan konflik penyisipan serentak
Fractional Index memberikan nilai yang dapat diurutkan pada setiap objek
- Jika penyisipan baru terjadi di antara dua objek,
Fractional Index objek baru berada di antara nilai kiri dan kanan
- Penjelasan terkait dapat dilihat di blog Figma dan blog Evan
- Dalam lingkungan terdistribusi, jika beberapa peer menyisipkan node baru di posisi yang sama, node dengan isi berbeda dapat diberi
Fractional Index yang sama
- Loro mempertahankan
Fractional Index yang sama, dan urutan relatif antar-indeks yang sama ditentukan oleh PeerID, yaitu ID unik tiap peer
- Jika
Fractional Index yang sama ada di kedua sisi, Fractional Index baru tidak dapat dibuat di antaranya
- Loro menangani masalah ini dengan dua cara
- Menambahkan sejumlah jitter ke
Fractional Index yang dibuat untuk sangat mengurangi kemungkinan indeks yang sama muncul
- Misalnya, jika nilai antara 0 dan 1 awalnya 0,5, dengan random jitter nilainya bisa menjadi seperti
0.52712, 0.58312, 0.52834
- Jika perlu menyisipkan di antara
0.7@A dan 0.7@B, indeks dapat direset dengan memberi Fractional Index baru masing-masing kepada node baru dan node 0.7@B dari rentang antara 0,7 dan 1
Ukuran encoding dan pengaturan jitter
- Loro menggunakan implementasi
Fractional Index berbasis Vec<u8> dari drifting-in-space
- Implementasi ini berbasis 256
- Dengan nilai default, ukuran byte
Fractional Index baru bertambah 1 hanya setelah 128 nilai terus disisipkan ke depan atau ke belakang
- Overhead penyimpanan terburuk terjadi ketika nilai baru disisipkan secara bergantian setiap kali
- Misalnya, dari
ab, memasukkan c di antara a dan b, lalu d di antara c dan b, dan e di antara c dan d
- Dalam kasus seperti ini, satu operasi baru dapat memerlukan byte tambahan, tetapi situasi ini sangat jarang terjadi
- Loro menambahkan solusi jitter sederhana ke implementasi aslinya
- Random bytes sepanjang nilai jitter di-append ke
Fractional Index
- Di JavaScript, jitter dapat diaktifkan dengan memasukkan bilangan positif ke
doc.setFractionalIndexJitter(number)
- Ukuran encoding sedikit bertambah, dengan
jitter bytes ditambahkan untuk setiap Fractional Index
- Hubungan antara jitter dan jumlah maksimum penyuntingan serentak
n untuk menghindari konflik dengan probabilitas 99% saat membuat Fractional Index di posisi yang sama adalah sebagai berikut
| jitter |
jumlah maksimum penyuntingan serentak |
| 1 |
3 |
| 2 |
37 |
| 3 |
582 |
- Banyak
Fractional Index yang terurut akan memiliki banyak prefix yang sama
- Saat encoding, Loro mengurangi ukuran encoding total dengan optimasi prefix, yaitu menyimpan jumlah bit prefix yang sama dengan nilai sebelumnya dan sisa bytes saja
Pekerjaan terkait dan alasan pemilihan
- Selain
Fractional Index, ada movable list CRDT yang dapat mengurutkan node sibling dalam tree
- Moving Elements in List CRDTs dari Martin Kleppmann digunakan dalam Movable List Loro
- Solusi
Fractional Index lebih sederhana untuk diimplementasikan
- Saat memodelkan node tree, jika child node tidak diberi stable position representation, struktur tree secara keseluruhan menjadi terlalu kompleks
Fractional Index memiliki masalah interleaving
- Untuk kasus seperti item layer Figma atau bookmark multi-level, yang hanya membutuhkan urutan relatif dan tidak membutuhkan semantik sekuensial yang ketat, hal ini dapat diterima
Hasil benchmark
- Loro melakukan benchmark kinerja implementasi Movable Tree untuk kondisi ekstrem seperti pemindahan node secara acak, peralihan ke versi lama, dan struktur tree yang sangat dalam
- Hasilnya berada pada level yang dapat mendukung kolaborasi real-time dan checkout versi lama secara mulus
- Lingkungan pengujiannya adalah M2 Max CPU, dan kode benchmark tersedia di tree.rs
| Operasi |
Waktu |
Konfigurasi |
| 10.000 pemindahan acak |
28ms |
Buat 1.000 node terlebih dahulu |
| 1.000 kali beralih ke versi berbeda |
153ms |
Buat 1.000 node terlebih dahulu, lalu lakukan 1.000 pemindahan |
| 1.000 kali beralih ke versi berbeda pada tree dengan kedalaman 300 |
701ms |
Node baru menjadi child dari node sebelumnya |
Contoh penggunaan dan demo
LoroTree dari loro-crdt menyediakan pembuatan node, pembuatan dengan penentuan posisi, pemindahan, pemindahan ke root, pemindahan ke sebelum/sesudah node lain, pengambilan index dalam parent, pengambilan Fractional Index, dan akses ke data map milik node
import { Loro, LoroTree, LoroTreeNode, LoroMap } from "loro-crdt";
let doc = new Loro();
let tree: LoroTree = doc.getTree("tree");
let root: LoroTreeNode = tree.createNode();
// By default, append to the end of the parent node's children list
let node = root.createNode();
// Specify the child's position
let node2 = root.createNode(0);
// Move `node2` to be the last child of `node`
node2.move(node);
// Move `node` to be the first child of `node2`
node.move(node2, 0);
// Move the node to become the root node
node.move();
// Move the node to be positioned after another node
node.moveAfter(node2);
// Move the node to be positioned before another node
node.moveBefore(node2);
// Retrieve the index of the node within its parent's children
let index = node.index();
// Get the `Fractional Index` of the node
let fractionalIndex = node.fractionalIndex();
// Access the associated data map container
let nodeData: LoroMap = node.data;
- Sebuah demo aplikasi Todo yang menyimulasikan sinkronisasi data antar beberapa peer dengan Loro telah dibuat
Movable Tree merepresentasikan relasi subtaskMap merepresentasikan berbagai atribut taskText merepresentasikan judul task- Selain pembuatan, pemindahan, pengubahan, dan penghapusan, peralihan versi berbasis Loro juga diimplementasikan
- Dengan menyeret scrollbar, pengguna dapat beralih di antara semua versi lama yang pernah dilakukan
Ringkasan
- Implementasi CRDT tree yang dapat dipindahkan sulit karena kombinasi pemindahan serentak, penghapusan, siklus, penghapusan ancestor, dan pemindahan descendant
- Loro mengimplementasikan pemindahan hierarki tree dengan algoritme operasi move beravailabilitas tinggi dari Kleppmann dkk.
- Pemindahan dan pengurutan antar child node ditangani dengan mengintegrasikan implementasi
Fractional Index dari drifting-in-space
- Kombinasi ini dapat memenuhi kebutuhan berbagai skenario aplikasi kolaboratif
1 komentar
Komentar Hacker News
Saya sedang membuat editor multipemain baru untuk pekerjaan/catatan [1], dan ini mendukung operasi teks serta outliner
Dari luar, ini bekerja seperti dokumen teks datar, tetapi karena fitur outliner, secara internal bentuknya menjadi pohon besar. Untuk sinkronisasi perubahan, saya memakai pendekatan yang mirip dengan operasi move yang highly-available. Hanya ada satu operasi untuk mengubah pohon, yaitu
insmov, dan saat klien online, himpunan perubahan C disinkronkan dengan server. Jika ada perubahan remote di server, server mengembalikan semua perubahan R sejak sinkronisasi terakhir dalam urutan linear global, laluinsmovdari perubahan lokal C dibatalkan, setelah itu R dan perubahan baru yang belum disinkronkan diterapkan kembaliSaya tidak memakai fractional indexing; selain parent P, tuple
insmovjuga menyertakan sibling sebelumnyaguidA. Karena semua operasi pohon pada akhirnya diterapkan sesuai urutan linear global yang ditentukan server, pengurutan ditangani oleh operasiinsmovitu sendiri. Sebagian besar waktu tidak perlu undo, dan pemutaran ulang urutan yang benar hanya diperlukan ketika ada perubahaninsmovdi server yang belum saya ketahui sekaligus saya mengiriminsmovbaru. Ini bisa terjadi saat tersambung lagi ke Wi-Fi setelah penerbangan panjang, tetapi lebih jarang jika sedang online dan menerima push real-time lewat WebSocket, dan tidak diperlukan untuk operasi non-insmovseperti pembaruan teks[1] https://thymer.com
Misalnya, bentuk yang memakai urutan server alih-alih timestamp Lamport
[1] https://inria.hal.science/inria-00555588/
Saat mencari Thymer di HN, saya menemukan Show HN dari 2009[1], dan sepertinya Thymer berada dalam beta tertutup selama 15 tahun terakhir
0. https://news.ycombinator.com/item?id=40786425
Saya harus membaca tulisan ini. Dalam pekerjaan klien freelance, saya merilis React Table Library [0] sebagai open source, dan fokusnya pada operasi pohon
Mereka menangani struktur pohon folder/file berskala 100 ribu node, dan memproses pemindahan, penyalinan folder dan file, serta lazy loading pada level teratas maupun level bersarang dalam struktur tabel yang sama. Setelah proyeknya selesai, saya jadi paham kenapa Google Drive hanya mengizinkan tampilan dan pengeditan pada level hierarki yang sama. Untuk menerapkannya dalam tampilan bersarang dengan banyak node, ada terlalu banyak batasan yang harus dipertimbangkan
[0] https://react-table-library.com/
Saya ingin minta saran. Ini bukan aplikasi multipemain, tetapi di frontend ada pohon terdenormalisasi yang besar dan saling terhubung, yang dipakai sebagai profil pengguna
Bayangkan struktur seperti layout berbasis tile, di mana pengguna menambah/menghapus/mengubah ukuran tile, menambahkan beberapa komponen ke setiap slot tile, dan komponen-komponen itu juga masing-masing punya profil sendiri. Bisa ada beberapa layout dengan susunan tile yang berbeda, dan ada juga kompleksitas karena tile tertentu merujuk ke atau berbagi bagian lain dari state global
Sulit untuk memperbaruinya dengan aman lewat REST biasa. Soalnya harus dijamin bahwa pengguna yang sama membuka dua tab, lalu memperbarui di tab 1 dan kemudian memperbarui lagi di tab 2, tidak membuat seluruh profil menjadi tidak valid. Secara umum urutan juga penting. Jika pembaruan yang sebenarnya sudah diterapkan ke klien dilewati oleh server, semuanya bisa rusak
Sebagai solusi yang sangat sederhana, saya memakai cara mengirim data minimum yang bisa menimpa sepenuhnya potongan state tertentu lalu memasukkannya ke belakang antrean. Biasanya cukup baik, tetapi kadang terasa boros, misalnya hanya beberapa byte yang benar-benar berubah tetapi harus mengirim 50KB
Secara umum alasan-alasan biasa untuk memakai CRDT memang tidak ada, tetapi bahkan untuk pengguna tunggal rasanya manajemen state akan jauh lebih mudah. Minimal, tab-tab browser milik pengguna bisa tersinkron, dan yang lebih penting, saya bisa percaya bahwa cukup mengubah state frontend lalu CRDT akan berkoordinasi dengan server secara tepat. Saya tidak perlu lagi menangani semuanya sendiri. Apakah ini masuk akal, atau overhead menambahkan sesuatu seperti Yjs tidak sepadan bila tidak membutuhkan multipemain dan local-first
Namun jika pengeditan profil hanya untuk satu pengguna, menerapkan CRDT tampaknya berlebihan. Dari luarnya, skenario membuka dua tab tampak sebagai sumber bug terbesar, jadi Anda bisa memakai
BroadcastChanneluntuk memberi tahu semua tab lain tentang event pembaruanMenjaga state bersama lewat pemanggilan REST yang menimpa sebagian state server memang rapuh, dan sebenarnya hanya cocok untuk menimpa field pada record data datar. Selain itu, koordinasi state server-klien selalu harus dipikirkan dengan hati-hati, dan di jalur yang bukan alur normal, sinkronisasi mudah sekali melenceng
Seperti yang Anda katakan, jika Anda membuat CRDT yang secara eksplisit menyatakan bagaimana pembaruan digabungkan, beban kognitif akan berkurang besar-besaran
Pada konten teks berformat seperti Google Docs atau Zoho Writer, operasi seperti memindahkan item daftar ke bawah atau menambahkan kolom baru, operasi pada tabel/daftar, pada dasarnya adalah operasi manipulasi pohon.
Konflik serentak dalam kasus seperti ini terkenal sulit dikonvergensikan tanpa penanganan khusus yang bergantung pada konteks [1]. Saya penasaran apakah implementasi ini juga memberikan solusi yang digeneralisasi untuk kasus penggunaan seperti itu.
Mungkin untuk node daun, yaitu blok teks, bisa digunakan CRDT daftar atau string, lalu untuk node struktural seperti daftar dan tabel, Tree CRDT ini bisa dikombinasikan. Namun kalau begitu, semua operasi harus ditambahi alamat dua dimensi
(parent-id, index_offset_into_that_parent).[1] https://github.com/inkandswitch/peritext/issues/27
Text CRDT pada dasarnya hanyalah list CRDT yang menyimpan data karakter. Karena itu, elemen tersemat dapat dengan mudah dimodelkan sebagai item khusus berukuran 1, seperti item lain dalam string, yaitu node anak tersemat. Dengan pendekatan yang tepat, Anda bisa mencampur berbagai CRDT di dalam pohon sesuai kebutuhan. Misalnya, ada tabel di dalam rich text, dan di salah satu selnya terdapat gambar.
Agak disayangkan harus menambahkan field
parent-crdt-idke semua operasi, tetapi tampaknya sulit dihindari. Untungnya, dalam sebagian besar kasus penggunaan nyata, operasi berurutan sangat sering berbagi CRDT induk yang sama, jadi field ID seperti ini kemungkinan bisa dikompresi dengan baik menggunakan run-length encoding.Namun, seperti yang dikatakan Seph, operasi berurutan di bawah parent yang sama dapat dikompresi secara efektif, jadi overhead teramortisasi dari parent ID seperti ini biasanya tidak besar.
Saya penasaran apakah pernah ada CRDT yang praktis untuk aplikasi dengan data sangat padat seperti piksel gambar atau model 3D.
Walaupun representasi konkret dokumen bersifat padat data, cara mengodekan edit dan operasi individual pengguna tetap bisa kecil.
Misalkan kita membuat editor gambar seperti Photoshop. Gambar 102 megapiksel tanpa kompresi dengan kedalaman warna 16-bit per kanal, misalnya foto Fujifilm GFX100, berukuran sekitar 610MB dalam format TIFF. Jika setiap piksel direpresentasikan sebagai register last-write-wins yang terpisah, overhead-nya besar, tetapi representasi seperti itu sebenarnya tidak cocok untuk mempertahankan maksud pengguna. Edit yang dilakukan pengguna adalah hal-hal seperti "menaikkan kontras gambar 15%" atau "mewarnai spline [(0,0), (1500, 1500)] dengan brush Q dan warna #000". Jika setiap piksel disinkronkan dengan timestamp Lamport, perubahan kontras oleh pengguna 1 akan diterapkan ke semua piksel kecuali piksel yang dilukis oleh pengguna 2, sehingga piksel yang ditimpa bisa terlihat janggal.
Sebagai gantinya, lebih baik merepresentasikan maksud pengguna sebagai daftar operasi edit. Ini jauh lebih kecil daripada seluruh grid piksel 102MB. Struktur data CRDT hanyalah salah satu mekanisme teknis yang mungkin untuk menyinkronkan maksud pengguna tersebut, tetapi strukturnya harus dipilih agar sesuai dengan semantik maksud pengguna, bukan tata letak data konkret dari output.
Tetap saja, bisa muncul operasi edit yang memuat data dalam jumlah besar, seperti
"add new layer namedbgbelow layerfgwith pixelsdata:(10mb of pixels)at (1500, 1500)". Namun, overhead sinkronisasi dari perintah edit seperti ini sangat rendah, dan ukurannya O(1), bukan O(pixels) yang sebanding dengan jumlah piksel di dalam perintah edit.Model 3D adalah persoalan lain, dan saya belum pernah melihat alat pemodelan 3D kolaboratif di pasaran. Tapi saya juga belum aktif mencarinya.
Saya belum pernah benar-benar membuatnya, dan juga belum yakin apakah itu akan praktis dalam kenyataan. Namun setidaknya, seluruh riwayat dokumen bisa dipertahankan.
Modyfi merepresentasikan data dengan Yjs, tetapi alih-alih menyimpan piksel mentah, ia menyimpan seluruh riwayat transformasi.
https://digest.browsertech.com/archive/browsertech-digest-ho...
Saya penasaran apakah tulisan ini diperiksa dengan GPT. Di paragraf pertama, terasa sangat kuat gaya bicara ChatGPT.
This article introduces the implementation difficulties and challenges of Movable Tree CRDTs when collaboration, and how Loro implements it and sorts child nodes.