Version Vector Memisahkan Kausalitas dari Concurrency

Data yang direplikasi dapat menerima write di beberapa node ketika komunikasi antar-node sedang terlambat. Saat dua versi bertemu kemudian, store perlu menentukan apakah satu versi merupakan turunan versi lain atau keduanya dibuat secara independen.

Wall-clock timestamp memberi urutan yang tampak total, tetapi clock order bukan causal order. Dua replica dapat melakukan write selama partition, dan timestamp yang kebetulan lebih besar tidak membuat write tersebut menjadi turunan write lainnya.

Version vector mencatat progres per replica. Perbandingan counter tersebut membuat sistem dapat mengklasifikasikan versi sebagai sama, memiliki urutan kausal, atau concurrent. Klasifikasi ini mempertahankan informasi yang hilang jika sistem hanya memakai satu scalar timestamp.

Satu counter tidak mewakili progres independen

Misalkan replica A dan B sama-sama menyimpan versi x. Client memperbarui A saat B terputus:

A: x -> x1
B: x

Kemudian client lain memperbarui B:

A: x1
B: x2

Kedua update tidak pernah melihat satu sama lain. Memilih satu sebagai versi lebih baru hanya karena wall-clock timestamp-nya lebih akhir menyembunyikan fakta bahwa terdapat dua branch.

Scalar revision yang dibuat secara independen di tiap replica memiliki masalah serupa. 17 di A dan 22 di B tidak membuktikan kausalitas kecuali keduanya berasal dari satu ordering authority. Otoritas seperti itu menambah coordination boundary yang mungkin justru ingin dihindari oleh desain replikasi.

Vector mencatat kontribusi tiap replica

Untuk replica A, B, dan C, version vector dapat direpresentasikan sebagai:

{A: 4, B: 2, C: 7}

Setiap komponen menyatakan sejauh mana versi tersebut telah memasukkan event yang berasal dari replica itu. Local write menaikkan komponen lokal.

Jika A memiliki:

v1 = {A: 4, B: 2}

lalu melakukan write baru, hasilnya:

v2 = {A: 5, B: 2}

v2 berada secara kausal setelah v1 karena setiap komponen v2 setidaknya sama besar dan satu komponen lebih besar.

Vector merupakan metadata history, bukan timestamp. Nilainya tidak perlu berhubungan dengan detik atau physical clock.

Perbandingan menghasilkan partial order

Untuk vector p dan q, p mendominasi q ketika setiap komponen di p lebih besar atau sama dengan komponen yang bersesuaian di q, dengan setidaknya satu kenaikan.

Contoh:

p = {A: 5, B: 3}
q = {A: 4, B: 3}

p mendominasi q

Store dapat membuang q ketika p merepresentasikan logical object yang sama karena p sudah mencakup history yang direpresentasikan q.

Concurrency muncul ketika tidak ada vector yang mendominasi:

p = {A: 5, B: 2}
q = {A: 4, B: 3}

p lebih maju di A dan tertinggal di B. q lebih maju di B dan tertinggal di A. Tidak ada versi yang mencakup seluruh history versi lain.

Hasil tersebut adalah signal penting: kedua branch mungkin perlu dipertahankan sampai reconciliation yang sesuai dengan aplikasi dilakukan.

Komponen yang tidak ada bernilai nol

Implementasi tidak perlu menyimpan nol eksplisit untuk setiap replica yang dikenal. Dua vector berikut ekuivalen saat dibandingkan:

{A: 3}
{A: 3, B: 0, C: 0}

Komponen yang tidak ada dapat diperlakukan sebagai nol.

Representasi ini membantu sistem sparse, tetapi ukuran vector tetap bertambah bersama jumlah identitas replica berbeda yang berkontribusi pada write. Pengelolaan identitas replica karena itu menjadi bagian protokol, bukan sekadar detail penamaan.

Merge menggabungkan history tanpa memilih value

Nilai maksimum per komponen dari dua vector membentuk causal join:

p = {A: 5, B: 2}
q = {A: 4, B: 3}

join(p, q) = {A: 5, B: 3}

Operasi tersebut menggabungkan causal context. Operasi itu tidak menentukan application value yang harus menang.

Jika p memuat shipping address X dan q memuat shipping address Y, vector dapat menetapkan bahwa kedua value concurrent. Vector tidak dapat menentukan apakah X, Y, keduanya, atau value baru hasil komputasi merupakan hasil yang benar.

Reconciliation tetap merupakan keputusan data model. Set dapat menggabungkan member, counter dapat memakai aturan CRDT, dokumen dapat menampilkan conflict kepada user, dan domain workflow dapat menolak resolusi otomatis.

Resolved write harus membawa kedua branch

Misalkan client membaca dua versi concurrent:

p = {A: 5, B: 2}
q = {A: 4, B: 3}

Client menyelesaikan conflict lalu menulis value baru di A. Causal context baru perlu menggabungkan kedua history lebih dahulu, kemudian menaikkan A:

join      = {A: 5, B: 3}
new write = {A: 6, B: 3}

Versi baru mendominasi kedua branch sebelumnya. Replica yang menerimanya dapat mengklasifikasikan keduanya sebagai ancestor.

Jika resolver menulis hanya dari p, hasilnya dapat berupa {A: 6, B: 2}. Versi itu masih concurrent dengan q karena belum memasukkan event ketiga milik B.

Causal context yang dibawa sebuah write karena itu sama pentingnya dengan value yang ditulis.

Replica ID memerlukan aturan lifecycle

Vector mengasumsikan nama komponen memiliki arti stabil. Menggunakan kembali replica ID setelah counter-nya hilang dapat membuat event baru tampak lebih lama daripada history yang sudah tersimpan di tempat lain.

Jika replica lain sudah melihat:

{A: 900}

lalu replacement node mulai kembali sebagai A dengan counter 1, perbandingan vector biasa menganggap write barunya sebagai ancestor history A yang lama.

Desain yang lebih aman mempertahankan counter secara durable, memberikan identitas baru pada incarnation pengganti, atau memakai protokol yang secara eksplisit menangani membership epoch.

Retirement identitas juga perlu hati-hati. Menghapus komponen dari vector terlalu cepat dapat menghilangkan bukti kausal yang masih diperlukan replica yang lama terputus. Garbage collection aman hanya jika protokol memiliki dasar untuk menyatakan history yang dihapus tidak dapat muncul kembali sebagai concurrent state yang relevan.

Version vector tidak menyediakan global event order

Dua vector concurrent memang sengaja tidak dapat dibandingkan. Hal ini bukan kekurangan yang harus ditutup dengan tie-breaker arbitrer jika aplikasi perlu mempertahankan concurrent write.

Total order merupakan kontrak berbeda. Consensus log, sequencer, atau database serialization dapat memberi ordering lebih kuat dengan biaya coordination. Version vector cocok untuk sistem yang memerlukan klasifikasi kausal tanpa memaksa setiap write independen melewati satu global ordering point.

Version vector juga tidak membuat replikasi berlangsung seketika. Replica dapat tetap stale sampai menerima state yang lebih baru. Vector menjelaskan hubungan antarversi yang ada; vector tidak mengirimkan versi tersebut.

Storage dan wire format memerlukan aturan deterministik

Implementasi praktis memerlukan representasi stabil untuk replica ID dan counter. Perbandingan harus bekerja pada integer value, bukan urutan field hasil serialisasi.

Dua object JSON berikut membawa vector yang sama:

{"A": 5, "B": 3}

{"B": 3, "A": 5}

Jika vector ditandatangani, di-hash, atau dipakai sebagai cache key, canonical serialization mungkin diperlukan. Kebutuhan tersebut terpisah dari semantics vector dan sebaiknya ditentukan secara eksplisit.

Counter overflow juga memerlukan kebijakan. Wraparound diam-diam merusak monotonicity komponen replica. Integer yang lebar membuat rollover sangat jauh pada operasi biasa, tetapi implementasi tetap perlu menolak atau menangani exhaustion alih-alih menggunakan kembali nilai rendah.

Conflict metric memperlihatkan topology dan workload

Frekuensi versi concurrent dapat menjadi signal operasional. Peningkatan conflict dapat menandakan partition yang lebih lama, replication lag, client yang menulis melalui beberapa region, atau pola ownership workload yang tidak lagi cocok dengan strategi replikasi.

Measurement yang berguna meliputi:

concurrent version yang dibuat
concurrent version yang diselesaikan
usia branch yang belum selesai
jumlah komponen vector
replication lag per peer

Signal tersebut tidak menggantikan correctness check pada aplikasi. Signal itu menunjukkan seberapa sering sistem memasuki state yang memerlukan reconciliation policy.

Kausalitas adalah informasi yang perlu dipertahankan

Replicated store tidak selalu perlu langsung menyatakan satu dari dua disconnected write sebagai pemenang. Store lebih dahulu perlu mengetahui hubungan keduanya.

Version vector mengodekan history per replica yang cukup untuk membuat perbedaan tersebut. Dominance menandai causal successor. Incomparability menandai concurrent branch. Component-wise join mencatat bahwa kedua history sudah dimasukkan.

Partial order ini lebih sempit daripada global sequence, tetapi sesuai dengan pertanyaan yang sering perlu dijawab replicated system: apakah sebuah versi sudah memuat history versi lain, atau keduanya masih harus diperlakukan sebagai versi independen.