- 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
Belum ada komentar.