Petunjuk dan konteks
Rancang layanan anti-entropy latar belakang untuk key-value store yang direplikasi. Node mungkin offline untuk sementara waktu saat operasi penulisan terus berjalan; sistem harus menghindari pemindaian penuh dan pada akhirnya harus konvergen. Jelaskan bagaimana Merkle tree menemukan perbedaan, bagaimana perbaikan dibatasi lajunya, dan bagaimana replika usang dicegah menimpa data yang lebih baru.
Paper Dynamo menjelaskan Merkle tree per rentang kunci: bandingkan root dan node internal terlebih dahulu, lalu sinkronkan hanya rentang leaf dengan hash yang berbeda. Wawancara ini bertujuan untuk menghubungkan deteksi, arbitrasi versi, perbaikan konkuren, anggaran sumber daya, dan observabilitas ke dalam satu protokol.
Apa yang diuji oleh pewawancara
Pewawancara menguji tujuan konsistensi, pembuatan versi, batas partisi dan pembaruan tree, perbandingan inkremental, perbaikan idempoten, pembatasan laju (throttling), percobaan ulang (retry), perubahan topologi, dan argumen konvergensi yang kredibel. Jelaskan kapan read repair atau pemulihan manual oleh manusia diperlukan.
Pertanyaan klarifikasi
Konfirmasikan partisi key-space, faktor replikasi, konsistensi baca dan tulis, representasi versi, semantik penghapusan, toleransi keusangan (staleness), ukuran data, dan bandwidth perbaikan. Tanyakan tentang model kegagalan, partisi jaringan, enkripsi, isolasi penyewa (tenant), dan apakah proses perbaikan boleh berbagi sumber daya dengan lalu lintas bisnis.
Jawaban 30 detik
"Saya akan mengelola Merkle tree berversi per virtual-node atau rentang kunci. Node peer saling bertukar rentang, hash root, dan batas snapshot (snapshot watermark); root yang sama tidak memerlukan pekerjaan lanjutan, sedangkan root yang tidak sama akan melakukan rekursi ke leaf yang berbeda dan mengelompokkan kuncinya ke dalam batch. Penulisan perbaikan membawa versi atau tombstone serta menggunakan aturan konflik deterministik yang menolak nilai usang. Batch idempoten, lease, anggaran bandwidth, retry, dan metrik saturasi menjaga perbaikan tetap aman. Usia perbaikan, jumlah perbedaan, dan sampel pembacaan replika membuktikan konvergensi."
Jawaban mendalam
Langkah 1: Tentukan partisi dan versi
Bagi key-space menjadi rentang-rentang stabil dengan kumpulan replika pemilik. Setiap rekaman membawa versi monotonik, vector clock, atau versi kausal. Penghapusan memerlukan tombstone yang dipropagasi; rekaman yang hilang tidak boleh diartikan sebagai 'tidak pernah ada'.
Langkah 2: Bangun Merkle tree yang dapat dibandingkan
Leaf menggabungkan kunci dan digest versi dalam urutan deterministik; parent menyimpan hash dari child-nya. Pembangunan ulang atau pembaruan inkremental keduanya dimungkinkan, tetapi batasan snapshot penulisan harus eksplisit sehingga sebuah root memiliki satu arti tunggal.
Langkah 3: Bandingkan dari root ke leaf
Bandingkan identitas rentang dan root terlebih dahulu. Root yang sama tidak memerlukan transfer data. Root yang berbeda akan menelusuri child secara rekursif hingga rentang perbedaan terkecil ditemukan, kemudian kunci dan ringkasan versi dikelompokkan ke dalam batch. Bagi rentang yang padat (hot range) atau batasi ukuran batch agar satu proses perbaikan tidak memblokir partisi lain.
Langkah 4: Arbitrasi versi dan penghapusan
Bandingkan hubungan versi saat kunci yang berbeda tiba. Versi yang konkuren tidak dapat diselesaikan hanya berdasarkan waktu kedatangan; lakukan merge, pertahankan konflik, atau terapkan aturan bisnis. Tombstone memerlukan periode retensi dan batas aman (watermark) sebelum dibersihkan.
Langkah 5: Buat batch perbaikan menjadi idempoten
Sebuah batch membawa rentang, versi snapshot, urutan (sequence), dan digest-nya. Menjalankannya berulang kali tidak menimbulkan efek samping tambahan. Target memeriksa versi sebelum menerapkannya; batch lama ditolak atau dilewati dengan aman. Hasilnya dapat diputar ulang (replayable) dan dapat diaudit.
Langkah 6: Anggarkan sumber daya dan konkurensi
Tetapkan anggaran konkurensi, bandwidth, CPU, pembacaan disk, dan antrean berdasarkan tenant, rentang, node, dan prioritas. Lalu lintas bisnis diprioritaskan. Jeda perbaikan saat sebuah node kelebihan beban atau jeda replikasi melampaui ambang batas. Tambahkan jitter pada exponential backoff agar node tidak mencoba ulang secara bersamaan.
Langkah 7: Tangani perubahan topologi dan kegagalan
Hitung ulang kumpulan replika dan metadata tree saat node bergabung, keluar, atau rentang berpindah. Simpan progres, snapshot, dan lease secara persisten agar proses dapat dilanjutkan kembali setelah restart. Selama partisi jaringan, tetap terima operasi penulisan tetapi tampilkan status usang dan konflik daripada mengklaim telah terjadi konvergensi.
Langkah 8: Buktikan konvergensi dan operasikan
Pantau waktu perbaikan terakhir, kunci yang berbeda, usia tombstone, batch yang gagal, konflik versi, dan bandwidth per rentang. Bandingkan sampel pembacaan di seluruh replika secara berkala dan tetapkan SLO keusangan maksimum. Berikan peringatan, isolasi, atau pulihkan rentang secara manual ketika perbaikan terus-menerus gagal, alih-alih mencoba ulang tanpa henti.
Jawaban model
Saya akan mempartisi key-space ke dalam rentang virtual-node dan mengelola Merkle tree dengan digest versi untuk setiap rentang. Node peer bertukar identitas rentang, hash root, dan watermark snapshot; root yang sama akan dilewati, sedangkan tree yang berbeda akan melakukan rekursi ke leaf yang berbeda dan mentransfer hanya kunci-kunci tersebut. Rekaman menggunakan vector clock atau versi monotonik, penghapusan menggunakan tombstone, dan konflik mengikuti aturan merge atau arbitrasi deterministik; versi yang lebih lama tidak boleh menang hanya karena tiba lebih akhir. Batch perbaikan membawa snapshot, sequence, dan digest, serta bersifat idempoten. Anggaran tenant, rentang, node, dan bandwidth melindungi lalu lintas bisnis, disertai backoff dengan jitter saat terjadi kegagalan. Perubahan topologi menghitung ulang kumpulan replika dan lease. Operasional melacak perbedaan, usia perbaikan, konflik, tombstone, dan kegagalan, mengambil sampel pembacaan replika, serta menetapkan SLO keusangan. Divergensi yang persisten akan mengisolasi rentang untuk pemulihan manual oleh manusia.
Kesalahan umum
Mengirim seluruh shard saat root berbeda
Tujuan dari Merkle tree adalah menemukan rentang perbedaan terkecil secara rekursif. Mentransfer seluruh data melipatgandakan biaya jaringan dan disk serta dapat memblokir partisi yang sedang sibuk.
Menyelesaikan setiap konflik dengan last-write-wins
Pergeseran waktu (clock skew) dan penulisan konkuren membuat waktu kedatangan menjadi sinyal kausal yang tidak aman. Gunakan hubungan versi, aturan merge, atau arbitrasi bisnis.
Mengabaikan penghapusan dan tombstone
Jika data yang dihapus langsung hilang seketika, replika yang tertinggal dapat memunculkan kembali nilai lama tersebut. Retensi tombstone dan pembersihan yang aman adalah bagian penting dari konvergensi.
Pertanyaan lanjutan dan jawaban
Bagaimana Merkle tree menangani penulisan yang terus-menerus?
Bandingkan snapshot atau watermark versi yang konsisten saat penulisan baru masuk dengan versi yang lebih baru; majukan watermark perbaikan setelah batch selesai. Root yang terus berubah bukanlah satu snapshot tunggal.
Bagaimana jika satu rentang sangat padat (extremely hot)?
Bagi rentang tersebut lebih lanjut, batasi batch serta konkurensi, dan prioritaskan rentang turunan (child range) yang memiliki jendela keusangan terbesar. Kurangi amplifikasi pembacaan untuk sementara atau pindahkan replika bila diperlukan.
Bagaimana jika sebuah node restart di tengah proses perbaikan?
Lanjutkan dari lease, urutan batch, dan progres yang tersimpan secara persisten. Pemeriksaan versi di sisi target membuat batch duplikat tetap aman, dan sumber memvalidasi ulang snapshot.
Bagaimana Anda mencegah tombstone lama dihapus terlalu cepat?
Bersihkan tombstone hanya setelah semua replika terkait melewati watermark aman atau titik konfirmasi (acknowledgement), dan pantau usia tombstone tertua. Pertahankan jika konfirmasi belum ada.
Apa perbedaan read repair dengan anti-entropy?
Read repair memperbaiki perbedaan yang ditemukan pada jalur pembacaan bisnis dan mencakup kunci-kunci yang sering diakses (hot keys). Anti-entropy adalah pemindaian latar belakang proaktif yang mencakup data yang jarang diakses (cold data). Keduanya berbagi semantik versi dan perbaikan yang sama.
Kapan perbaikan otomatis harus dihentikan?
Jeda dan isolasi rentang ketika konflik tidak dapat digabungkan, data rusak, otorisasi tidak normal, atau sumber daya terus-menerus kelebihan beban. Pertahankan bukti dan snapshot untuk pemulihan manual oleh manusia.