Kamus CRDT: panduan praktis untuk struktur data terdistribusi

 (iankduncan.com)
25 poin oleh GN⁺ 2025-12-01 | 1 komentar | Bagikan ke WhatsApp
  • CRDT(Conflict-free Replicated Data Type, tipe data replikasi tanpa konflik) adalah struktur data terdistribusi yang memungkinkan penggabungan data yang konsisten tanpa koordinasi bahkan dalam situasi partisi jaringan atau modifikasi serentak
  • Jika penggabungan data memenuhi komutatif, asosiatif, dan idempoten, semua replika pada akhirnya akan berkumpul ke keadaan yang sama
  • Bentuk yang representatif antara lain G-Counter, PN-Counter, G-Set, 2P-Set, OR-Set, LWW-Register, MV-Register, RGA, WOOT, Logoot dan lain-lain, yang masing-masing menangani kebutuhan penambahan, penghapusan, penambahan ulang, dan pemeliharaan urutan yang berbeda
  • Delta CRDT meningkatkan efisiensi dengan mengirim hanya perubahan alih-alih seluruh keadaan, dan Garbage Collection adalah tantangan penting untuk mengatasi masalah akumulasi metadata
  • CRDT bukan solusi sempurna, tetapi dinilai sebagai pilihan yang kuat dalam sistem yang ketersediaannya lebih penting daripada konsistensi langsung

Konsep dasar CRDT

  • CRDT adalah struktur data yang dapat digabung tanpa koordinasi meskipun terjadi modifikasi serentak di lingkungan terdistribusi
    • Jika operasi penggabungan bersifat komutatif(commutative), asosiatif(associative), dan idempoten(idempotent), semua replika akan berkumpul ke keadaan yang sama
  • Dirancang berdasarkan konsep Lattice(kisi) agar keadaan selalu bergerak hanya ke arah “atas”
    • Contoh: G-Counter menggabungkan hitungan tiap replika dengan max untuk menjamin penjumlahan tanpa kehilangan
  • CRDT memiliki dua pendekatan: State-based(CvRDT) dan Operation-based(CmRDT)
    • CvRDT menggabungkan seluruh keadaan, sedangkan CmRDT menyebarkan operasi

Jenis-jenis utama CRDT

  • G-Counter: penghitung yang hanya bisa bertambah, menjumlahkan nilai dari tiap replika
  • PN-Counter: mendukung hitungan dua arah dengan menggabungkan G-Counter untuk kenaikan dan penurunan
  • G-Set: himpunan yang hanya bisa ditambah
  • 2P-Set: dapat ditambah dan dihapus, tetapi tidak bisa ditambahkan ulang
  • LWW-Element-Set: operasi terbaru menang berdasarkan timestamp
  • OR-Set: menggunakan tag unik untuk menggabungkan tanpa kehilangan data saat penambahan serentak, dengan perilaku add-wins
  • LWW-Register / MV-Register: untuk menyimpan satu nilai; LWW memiliki satu pemenang, MV mempertahankan semua nilai serentak
  • OR-Map: struktur map yang menggabungkan OR-Set untuk tiap kunci
  • RGA / WOOT / Logoot / LSEQ: CRDT untuk data sekuens yang memiliki urutan
    • RGA berbasis pohon, WOOT berbasis referensi dua arah, Logoot/LSEQ berbasis pengenal posisi

Konsep CRDT lanjutan

  • Causal CRDTs: melacak hubungan kausal menggunakan version vector, sehingga deteksi konflik menjadi lebih akurat
  • Delta CRDTs: meningkatkan efisiensi jaringan dengan mengirim hanya perubahan (delta), bukan seluruh keadaan
  • Tree CRDTs: mendukung replikasi data berstruktur hierarkis (seperti sistem file), dengan kebutuhan menjaga relasi induk-anak
  • Observed-Remove Shopping Cart: contoh keranjang belanja e-commerce yang menggabungkan OR-Set dan PN-Counter

Masalah Garbage Collection

  • Demi konvergensi, CRDT terus mengakumulasi metadata sehingga timbul masalah pertumbuhan tak terbatas
    • Contoh: tag pada OR-Set, tombstone pada RGA
  • Ada berbagai strategi seperti kedaluwarsa berbasis waktu, penghapusan berbasis konsensus, pelacakan kausal berbasis version vector, penetapan batas atas metadata, dan checkpoint/rebase
  • Setiap pendekatan memerlukan kompromi antara keamanan(mencegah kebangkitan zombie) dan efisiensi ruang

Panduan performa dan pemilihan

  • Kompleksitas ruang dan waktu tiap jenis CRDT berbeda tergantung jumlah replika, jumlah elemen, jumlah tag, dan sebagainya
    • G/PN-Counter sebanding dengan jumlah replika, OR-Set sebanding dengan jumlah tag, RGA menumpuk tombstone
  • Delta CRDT sangat meningkatkan performa penggabungan
  • Kriteria pemilihan:
    • Hanya perlu penambahan → G-Counter, G-Set
    • Perlu penghapusan, tidak perlu penambahan ulang → 2P-Set
    • LWW dapat diterima → LWW-Set/Register
    • Perlu mempertahankan modifikasi serentak → OR-Set, MV-Register
    • Perlu menjaga urutan → RGA, Logoot
    • Struktur bertingkat → OR-Map

Kesimpulan

  • CRDT menjamin konvergensi tanpa koordinasi, tetapi memiliki kelemahan berupa pertambahan metadata dan kompleksitas
  • Berguna dalam sistem yang memprioritaskan ketersediaan, dan tiap CRDT dioptimalkan untuk jenis masalah tertentu
  • Dalam praktik, CRDT digunakan berdampingan dengan basis data tradisional, dan strategi garbage collection menjadi keharusan
  • Tidak ada “CRDT yang sempurna”; yang terpenting adalah memilih sesuai kebutuhan aplikasi

Bacaan terkait

1 komentar

 
GN⁺ 2025-12-01
Komentar Hacker News

  • Salah satu hal menarik tentang CRDT adalah bahwa ini bukan sekadar library yang menggabungkan beberapa CRDT tingkat rendah
    Misalnya, Automerge sendiri adalah CRDT yang utuh, dan menjamin konsistensi bahkan di bawah konkurensi melalui pembuktian matematis
    Tim Automerge memverifikasi desainnya dengan alat pembuktian teorema seperti Isabelle, dan menargetkan implementasi yang cepat sekaligus akurat dengan menerapkan teknik performa terbaru dari dunia database
    Jika Anda membangun SaaS yang memerlukan kolaborasi real-time (misalnya Notion, Figma), Anda bisa langsung menerapkan struktur data kolaboratif tanpa harus memahami teori yang rumit
    Backend cukup berupa penyimpanan key-value sederhana, dan frontend cukup dengan satu library

    • Automerge menyediakan API yang sangat baik tidak hanya untuk Rust, tetapi juga Javascript dan C
      Saya juga pernah membuat library automerge berbasis Redis, dan bisa mengimplementasikan server sinkronisasi persisten yang lengkap dengan memanfaatkan pub/sub
      Saya juga dengan cepat menyelesaikan demo sinkronisasi dokumen antar beberapa browser dengan memanfaatkan fitur websocket dari Webdis
    • Automerge memang hebat, tetapi masih terasa punya pendekatan yang sangat akademis
      Jika menginginkan DX yang lebih baik dan full-stack DB berbasis CRDT, saya merekomendasikan Triplit.dev. Kecepatan pengembangannya memang agak melambat, tetapi fiturnya sudah cukup matang
    • Tidak mengejutkan bahwa Automerge adalah CRDT yang utuh
      Secara pribadi saya juga suka Loro, tetapi strukturnya masih berbasis dokumen, sehingga mesin kuerinya kurang memadai. Untuk mendapatkan data yang diinginkan, kita harus menunjuk item bersarang tertentu secara langsung
    • Fakta bahwa Automerge tidak mendukung self-hosting adalah batasan yang fatal bagi banyak aplikasi

  • Ini tulisan yang tersusun dengan baik, dari dasar hingga konsep lanjutan CRDT
    Sebagai referensi, Riak masih terus dipelihara dalam bentuk OpenRiak

    • Saya baru tahu tentang OpenRiak, dan senang melihat mantan rekan kerja saya ikut terlibat. Basho benar-benar kelompok engineer yang luar biasa

  • Selama dua tahun terakhir saya mengembangkan CRDT sendiri, tetapi saya sadar ada terlalu banyak trade-off, jadi akhirnya beralih ke framework OT berbasis ID
    Saya berencana meluncurkan Docnode.dev Selasa ini. Saya ingin mendengar masukan
    Ke depannya saya juga berencana menambahkan mode CRDT untuk situasi yang membutuhkan P2P

    • Saya penasaran trade-off mana yang paling bermasalah

  • CRDT atau OT adalah struktur yang dimaksudkan untuk menangani saat orang mengedit paragraf yang sama secara bersamaan, tetapi dalam praktiknya situasi seperti itu hampir tidak pernah terjadi

    • Namun, sistem yang tidak memiliki fitur seperti ini sering kali membuat kursor bertumpuk pada kalimat yang sama, sehingga menyebabkan hilangnya konten atau membuang waktu

  • OR-Set yang disebut dalam artikel ini mirip dengan metode merge yang dulu digunakan Monotone sejak 2005
    Materi terkait bisa dilihat di dokumentasi MarkMerge

  • CRDT masih merupakan area yang harus diimplementasikan sendiri
    Dua bulan lalu saya juga membuat mesin CRDT berbasis sekuens, terinspirasi dari diamond types
    Saya meminta bantuan AI, tetapi sama sekali tidak membantu untuk masalah yang berpusat pada logika seperti ini
    Saya merasa perlu ada black-box test untuk memverifikasi apakah LLM bisa memahami logika baru

    • Saya penasaran bagaimana kalau langsung memakai sesuatu seperti Loro

  • Artikelnya bagus, tetapi menurut saya glosari istilahnya harus punya indeks (index)

  • Saya jadi berpikir apakah CRDT pada akhirnya hanya mendorong konflik merge dari DB ke logika aplikasi

    • CRDT juga bisa dirancang di dalam DB. Di Riak, itulah yang ingin dicapai
      Jika ditulis dengan benar, penyelesaian merge otomatis bisa dilakukan di lapisan mana pun
    • Saya juga sedang merancang graph DB di PostgreSQL yang menerapkan teknik CRDT
      Masalah terbesarnya adalah menangani konflik UNIQUE/PRIMARY KEY
      Ini bisa diatasi dengan membagikan namespace ID ke tiap server, membuat pembuatan pertama menjadi pemenang, lalu saat konflik terjadi mengubah nama atau menghapusnya
      Jika menggunakan skema EAV, penelusuran graf bisa dengan mudah diimplementasikan di SQL menggunakan CTE rekursif
      Namun, PostgreSQL tidak memiliki tipe ANY sehingga sulit merepresentasikan objek dengan atribut yang beragam, dan fitur FOREIGN KEY juga harus diimplementasikan sendiri
      Meski begitu, struktur EAV tetap menguntungkan untuk desain meta-skema seperti pewarisan
      Akan bagus jika tipe CRDT bisa didefinisikan langsung di PostgreSQL, tetapi saat ini pembatasan operasi monoid tidak dimungkinkan
      Pada akhirnya, CRDT untuk kolom non-key harus ditangani di lapisan aplikasi
      Singkatnya, CRDT bisa diimplementasikan juga di dalam RDBMS, tetapi pendekatannya berbeda tergantung di mana logika bisnis diletakkan