Tombstone Menjaga Delete Antar-Replica hingga Garbage Collection Aman

Menghapus value dari satu salinan replicated data belum berarti menghapusnya dari seluruh sistem. Replica lain mungkin sedang offline, terlambat, atau terpisah oleh partition saat delete terjadi. Jika replica aktif langsung membuang record, bukti bahwa deletion pernah terjadi ikut hilang. Replica stale dapat kembali kemudian dengan value lama dan membuat value tersebut terlihat lagi.

Tombstone mengubah deletion menjadi replicated state. Alih-alih langsung menghapus seluruh jejak record, sistem menyimpan marker bahwa record sudah dihapus pada logical point tertentu. Marker tersebut dapat bergerak melalui replication dan repair path yang sama dengan data biasa.

Bagian yang sulit muncul setelahnya: menentukan kapan marker itu sendiri aman untuk dihapus.

Absence tidak membawa version

Misalkan replica A dan B sama-sama menyimpan version 7 untuk key k. Replica B offline, lalu A menerima delete.

Jika A menghapus k secara fisik, local state menjadi:

A: k absent
B: k = value, version 7

Ketika B kembali, repair process melihat value di satu sisi dan tidak ada data di sisi lain. Absence biasa tidak menunjukkan apakah A menghapus version 7 atau memang tidak pernah menerimanya. Tanpa metadata tambahan, stale value dapat menang secara tidak sengaja.

Tombstone memberi version pada absence:

A: k = tombstone, version 8
B: k = value, version 7

Sekarang reconciliation memiliki state yang dapat dibandingkan. Version 8 menggantikan version 7, sehingga delete dapat dipropagasikan ke B.

Metadata tepatnya berbeda menurut storage engine. Sistem dapat memakai timestamp, sequence number, vector-like version, epoch, log position, atau ordering mechanism lain. Sifat pentingnya adalah delete ikut dalam conflict resolution.

Delete menjadi sebuah write

Memperlakukan deletion sebagai write memberi konsekuensi yang berguna. Replication path normal dapat membawanya, anti-entropy dapat memperbaikinya, dan conflict resolution dapat membandingkannya dengan stale value.

Merge rule sederhana dapat berbentuk:

local  = value@7
remote = tombstone@8

pilih remote karena 8 menggantikan 7

Model ini juga berarti delete memakai storage dan replication bandwidth. Workload dengan churn tinggi dapat menghasilkan banyak tombstone meski jumlah live key tetap stabil.

Tombstone bukan sekadar cleanup metadata gratis. Marker tersebut merupakan bagian dari replicated data model sampai sistem membuktikan bahwa marker tidak lagi diperlukan.

Tombstone yang dibuang terlalu cepat dapat menghidupkan data lama

Pertimbangkan tiga replica:

A: tombstone@8
B: tombstone@8
C: value@7   (offline)

Jika A dan B melakukan garbage collection terhadap tombstone saat C masih tidak terjangkau, state yang tersisa kemudian menjadi:

A: absent
B: absent
C: value@7

Ketika C bergabung kembali, version 7 dapat terlihat sebagai satu-satunya concrete value di sistem. Record yang sudah dihapus dapat muncul lagi.

Failure ini sering disebut data resurrection. Penyebabnya bukan delete awal, melainkan sistem melupakan delete sebelum setiap stale copy yang relevan sudah digantikan atau dinyatakan tidak relevan.

Karena itu safe garbage-collection rule harus menghubungkan umur tombstone dengan replication guarantee.

Retention berbasis waktu menyimpan asumsi tentang outage

Salah satu desain praktis mempertahankan tombstone selama grace period yang dikonfigurasi. Sistem mengasumsikan replica akan pulih dan menyelesaikan repair dalam interval tersebut.

Contohnya:

delete pada T0
simpan tombstone sampai T0 + grace_period
repair replica selama interval
collect tombstone setelah interval

Pendekatan ini sederhana secara operasional, tetapi grace period adalah correctness parameter, bukan hanya storage tuning knob. Jika replica offline lebih lama daripada retention window lalu kembali dengan stale data, resurrection dapat terjadi kecuali mekanisme lain mencegahnya.

Grace period yang lebih panjang mengurangi risiko tersebut, tetapi menyimpan lebih banyak tombstone dan dapat meningkatkan biaya read, compaction, serta storage. Periode yang lebih pendek menghemat ruang lebih cepat sambil mempersempit repair window yang dapat ditoleransi.

Nilai konfigurasi perlu sesuai dengan failure detection, repair cadence, prosedur backup restoration, dan durasi maksimum replica boleh tidak tersedia.

Progress metadata dapat membuat collection lebih presisi

Sebagian replicated system dapat menentukan bahwa setiap replica relevan sudah bergerak melewati delete. Replicated log, per-replica watermark, acknowledged sequence, atau compaction frontier dapat memberi bukti yang lebih kuat daripada elapsed wall-clock time saja.

Secara konseptual:

tombstone position = 812

replica A applied through 940
replica B applied through 901
replica C applied through 877

minimum applied position = 877

Jika membership stabil dan position 812 dijamin termasuk dalam history setiap replica, sistem memiliki bukti bahwa ketiganya sudah melewati deletion point.

Implementasi nyata memerlukan perhatian tambahan. Replica replacement, restored backup, membership change, progress metadata yang hilang, dan partition dapat membuat perhitungan minimum sederhana tidak valid. Garbage collector harus memakai membership dan durability model yang sama dengan replication.

Perubahan replica membership menggeser safety boundary

Node yang sudah dihapus permanen tidak seharusnya menghambat tombstone collection selamanya. Node yang hanya sedang tidak tersedia mungkin masih menyimpan stale data yang dapat kembali.

Sistem memerlukan pembedaan eksplisit antara kedua state tersebut. Membership protocol, decommission procedure, epoch, atau generation identifier dapat menetapkan bahwa replica lama tidak lagi boleh bergabung dengan historical state.

Replacement replica biasanya perlu bootstrap dari authoritative current snapshot atau log position, bukan menawarkan local disk lama sebagai current data yang valid.

Karena itu shortcut operasional saat menangani failed node dapat berubah menjadi correctness bug. Memasukkan kembali data directory lama setelah cluster melupakan tombstone dapat melewati asumsi yang dipakai garbage collection.

Compaction harus mempertahankan delete semantics

Storage engine berbasis immutable file sering menghapus obsolete version selama compaction. Tombstone dapat menjadi record terbaru untuk sebuah key, sedangkan value lama tersimpan di file atau level lain.

Compaction tidak dapat membuang tombstone hanya karena tidak ada live value pada input set saat ini. Value yang lebih lama mungkin masih berada di bagian lain storage hierarchy atau pada replica lain.

Keputusan compaction yang aman membutuhkan scope cukup luas untuk memastikan tidak ada local version lama yang dapat muncul serta distributed retention rule memang mengizinkan deletion metadata hilang.

Dengan demikian, local storage cleanup dan distributed replication policy merupakan concern yang saling terkait. Marker yang redundant secara lokal mungkin masih diperlukan secara global.

Read harus memperlakukan tombstone sebagai authoritative state

Read path yang meminta data dari beberapa replica dapat menerima campuran value, tombstone, dan missing response:

replica A -> tombstone@8
replica B -> value@7
replica C -> timeout

Mengembalikan version 7 hanya karena itulah satu-satunya live value akan melanggar version order. Tombstone harus ikut dalam reconciliation seperti ordinary value yang lebih baru.

Read repair dapat memakai hasil tersebut untuk mendorong tombstone ke stale replica. Quorum scheme dapat mengurangi paparan terhadap stale copy, tetapi quorum size saja tidak menghilangkan kebutuhan akan versioned deletion ketika replica dapat divergen.

Cache memerlukan perhatian serupa. Tombstone di database tidak otomatis menginvalidasi external cache. Cache invalidation, expiry, atau version check tetap menjadi consistency boundary terpisah.

Metric perlu menampilkan tekanan dan umur tombstone

Sistem dapat tetap available ketika deletion propagation diam-diam tertinggal. Operational signal perlu membuat state tersebut terlihat.

Measurement yang berguna mencakup:

tombstone count
oldest tombstone age
tombstones created per interval
tombstones collected per interval
replica repair lag
replica offline duration
compaction backlog
stale-version conflicts

Tombstone count yang meningkat dapat berasal dari volume delete normal, compaction tertunda, repair lambat, atau replica yang tidak terjangkau. Age distribution sering lebih berguna daripada total count karena menunjukkan apakah marker bertahan melewati repair window yang diharapkan.

Alert perlu menghubungkan retention limit dengan replica health. Replica yang mendekati durasi offline maksimum adalah risiko data consistency meski client traffic masih berhasil.

Deletion memiliki lifecycle

Dalam replicated storage, deletion bukan satu physical erase. Deletion memiliki lifecycle: membuat deletion state, mereplikasikannya, merekonsiliasi stale copy, mempertahankan bukti sepanjang supported failure window, lalu mengambil kembali ruang metadata ketika sistem aman untuk melupakannya.

Tombstone membuat lifecycle tersebut eksplisit. Marker mencegah absence biasa dianggap sebagai history yang hilang dan memberi repair mechanism sesuatu yang konkret untuk dipropagasikan.

Garbage collection menutup lifecycle, tetapi hanya berdasarkan asumsi yang ditetapkan replication, membership, dan recovery policy. Storage yang dihemat oleh collection terlalu dini jarang sebanding dengan pelanggaran asumsi tersebut, karena delete yang terlupakan dapat kembali sebagai live data lama setelah operasi awal tampak selesai.