Version Vector Membedakan Update Concurrent dari Penerus Kausal

Data tereplikasi dapat menerima write pada node berbeda ketika komunikasi antar-node tertunda. Saat versi-versi tersebut bertemu kembali, scalar revision number dapat menunjukkan bahwa dua nilai berbeda, tetapi tidak selalu dapat menentukan apakah satu versi merupakan turunan versi lain atau keduanya dibuat secara independen.

Version vector mencatat progres per-replica. Perbandingan counter tersebut menghasilkan partial order: satu versi dapat mendominasi versi lain, kedua vector dapat sama, atau tidak ada yang mendominasi. Kondisi terakhir menandai history concurrent yang membutuhkan aturan rekonsiliasi eksplisit.

Vector mencatat progres kausal per-replica

Untuk replica A dan B, sebuah versi dapat direpresentasikan sebagai map counter:

{A: 3, B: 1}

Ketika A membuat versi lokal baru, A menaikkan komponennya sendiri. Saat sebuah replica menggabungkan versi lain, ia mengambil nilai maksimum per-komponen terlebih dahulu, lalu menaikkan komponen miliknya untuk event lokal baru.

max({A:3, B:1}, {A:2, B:4}) = {A:3, B:4}

Counter tersebut adalah metadata logis. Nilainya tidak mewakili wall-clock time dan tidak membutuhkan sinkronisasi clock.

Dominance menandai penerus kausal

Vector X mendominasi vector Y ketika setiap komponen X lebih besar atau sama dengan komponen Y dan setidaknya satu komponen lebih besar.

X = {A:3, B:2}
Y = {A:2, B:2}

X mendominasi Y

Jika stored value membawa Y dan incoming value membawa X, metadata menetapkan bahwa X memiliki progres kausal setelah Y. Sistem dapat mengganti Y dengan X tanpa memperlakukan pasangan itu sebagai edit independen yang berkonflik, sesuai data model yang digunakan.

Vector yang sama mewakili causal frontier yang sama meski duplicate delivery membuat versi tersebut tiba kembali.

Vector yang tidak dapat dibandingkan menandai concurrency

Misalkan komunikasi terputus setelah kedua replica melihat {A:1, B:1}. A melakukan write lokal dan menghasilkan {A:2, B:1}. B juga melakukan write lokal dan menghasilkan {A:1, B:2}.

left  = {A:2, B:1}
right = {A:1, B:2}

Left lebih besar pada komponen A. Right lebih besar pada komponen B. Tidak ada yang mendominasi, sehingga kedua update concurrent dalam causal order.

Ini tidak berarti write terjadi pada waktu fisik yang persis sama. Jaraknya dapat beberapa detik atau jam. Concurrency di sini berarti tidak ada versi yang memasukkan versi lain ke dalam causal history miliknya.

Deteksi konflik terpisah dari resolusi konflik

Version vector dapat menandai versi concurrent, tetapi tidak menentukan application value mana yang harus bertahan. Resolusi merupakan bagian dari data model.

Key-value store dapat mempertahankan sibling lalu meminta read atau write berikutnya melakukan rekonsiliasi. Structured data type dapat menggabungkan field. Aplikasi lain dapat menerapkan aturan domain deterministik. Membuang satu sisi hanya karena server clock-nya lebih akhir mengganti informasi kausal dengan kebijakan berbasis clock dan dapat menghilangkan update independen.

Vector menjawab pertanyaan tentang urutan. Ia bukan merge algorithm.

Identitas replica memengaruhi ukuran metadata

Vector sederhana membawa satu counter untuk setiap replica yang berpartisipasi. Bentuk ini praktis untuk replica set yang stabil dan terbatas, tetapi mahal ketika writer sangat banyak atau bersifat sementara.

Replica identifier juga membutuhkan aturan lifecycle. Pemakaian ulang identifier setelah counter di-reset dapat membuat event baru tampak lebih lama daripada event historis dari pemilik identifier sebelumnya.

Sistem dengan membership dinamis sering memakai varian atau mekanisme tambahan untuk memadatkan causal metadata. Skema pemadatan tetap harus mempertahankan fakta ordering yang dibutuhkan semantic rekonsiliasi aplikasi.

Merge memakai nilai maksimum, bukan penjumlahan

Saat dua causal context bertemu, setiap komponen mewakili progres yang sudah diamati untuk satu replica. Penggabungan context karena itu mengambil counter maksimum pada setiap komponen.

v1 = {A:5, B:2, C:1}
v2 = {A:3, B:4, C:1}

merge(v1, v2) = {A:5, B:4, C:1}

Menjumlahkan counter akan menciptakan event yang tidak pernah ada. Context hasil merge menyatakan bahwa event sampai A5 dan B4 sudah diamati; ia tidak menyatakan ada tujuh event pada salah satu replica.

Write lokal berikutnya pada C dapat menaikkan C dan menghasilkan {A:5, B:4, C:2}. Versi baru tersebut mendominasi kedua input context.

Causal metadata harus melekat pada versi yang dijelaskannya

Perbandingan hanya andal ketika value dan causal metadata bergerak bersama melalui storage, replication, retry, dan repair. Mengubah payload tetapi tanpa sengaja mempertahankan vector lama dapat membuat perbandingan berikutnya salah diklasifikasikan.

Persistence sebaiknya memperlakukan value dan version vector sebagai satu logical record. Replication protocol perlu mentransfer keduanya, dan conditional write perlu membandingkan causal state yang diharapkan oleh operasi.

Version vector paling berguna ketika sistem perlu mempertahankan write independen tanpa memaksa seluruh mutasi melewati satu global serialization point. Aturannya ringkas: dominance menandai penerus kausal; vector yang tidak saling mendominasi menandai history concurrent; semantic aplikasi menentukan tindakan terhadap nilai concurrent tersebut.