Bagaimana cara mengimplementasikan consistent hash ring dengan virtual node?

Pertanyaan dan cakupan

Implementasikan sebuah ring untuk merutekan kunci string ke node fisik. API-nya adalah addNode(nodeId, weight), removeNode(nodeId), dan getNode(key). Sebuah node menerima weight × V token virtual, di mana V adalah jumlah dasar yang dikonfigurasi. Gunakan abstraksi hash 64-bit yang deterministik, tangani tabrakan (collision) dengan aman, dan kembalikan token aktif pertama searah jarum jam dari kunci tersebut. Jika ring kosong, getNode tidak mengembalikan node apa pun.

Ini adalah masalah coding, bukan layanan keanggotaan atau replikasi yang lengkap. Pembaruan keanggotaan diasumsikan diserialkan oleh pemanggil. Solusi harus menjelaskan mengapa penambahan atau penghapusan node hanya mengubah interval kunci di sekitarnya, dan di mana sifat tersebut berhenti membantu, seperti pada hot key atau hash yang dipilih dengan buruk.

Apa yang sedang diuji oleh pewawancara

PracHub mencatat ini sebagai pertanyaan technical-screen Software Engineer DoorDash dengan addNode, removeNode, dan getNode, penyeimbangan virtual-node, penanganan tabrakan, dan analisis kompleksitas. Catatan wawancara publik DoorDash baru-baru ini juga menjelaskan tentang memperbaiki load balancer round-robin dan mengimplementasikan consistent hashing.

Sinyal yang dinilai adalah desain struktur data yang dapat dieksekusi: pencarian terurut, identitas token yang stabil, pembaruan yang aman terhadap duplikasi, invarian yang jelas, serta pengujian untuk wrap-around dan perubahan keanggotaan. Makalah asli MIT mendefinisikan sifat-sifat yang berguna sebagai keseimbangan (balance) dan monotonisitas (monotonicity): penetapan harus tetap cukup merata, dan penambahan bucket tidak boleh memetakan ulang kunci yang dapat tetap berada di bucket lamanya.

Pertanyaan klarifikasi sebelum menjawab

1. Apakah ID node unik dan stabil setelah restart? ID yang stabil diperlukan untuk menghapus token yang tepat milik satu node fisik.
2. Apakah weight berupa bilangan bulat (integer)? Jawaban ini mengasumsikan bilangan bulat positif; kapasitas pecahan membutuhkan anggaran token yang dinormalisasi.
3. Apakah pembaruan keanggotaan berjalan bersamaan (concurrent) dengan pencarian? Jika ya, publikasikan snapshot yang tidak dapat diubah (immutable) atau tambahkan read/write lock; kode di bawah mengasumsikan pembaruan yang diserialkan.
4. Apakah replikasi diperlukan? API dasar mengembalikan satu pemilik. Mengembalikan R penerus yang berbeda adalah tindak lanjut dengan aturan kegagalan dan token duplikat.
5. Fungsi hash apa yang tersedia? Perlakukan sebagai deterministik dan seragam untuk latihan ini; pilihan produksi memerlukan tinjauan tabrakan dan input adversarial.

Kerangka jawaban 30 detik

“Saya menyimpan rekaman (token, virtualNodeId, physicalNodeId) dalam urutan terurut. Menambahkan node akan menyisipkan weight × V token deterministik; menghapusnya akan menghapus tepat token-token tersebut. Pencarian melakukan hash pada kunci, mencari secara biner token pertama pada atau setelah kunci tersebut, dan melakukan wrap-around ke indeks nol. Invariannya adalah setiap token dipetakan ke satu node fisik yang aktif dan setiap kunci memiliki token pertama searah jarum jam. Pencarian bernilai O(log M), pembaruan bernilai O(V·weight·log M), dan saya menguji tabrakan, wrap-around, pembaruan duplikat, penghapusan, ring kosong, serta pemetaan ulang kunci.”

Jawaban mendalam langkah demi langkah

1. Pilih representasi dan invarian

Misalkan M adalah jumlah token virtual. Simpan array rekaman yang terurut dan sebuah map dari ID node fisik ke rekaman token yang dihasilkannya. Array yang terurut membuat pencarian menjadi pencarian lower-bound; reverse map membuat penghapusan menjadi tepat alih-alih memindai awalan yang cocok.

Invariannya adalah:

1. Token diurutkan berdasarkan (hash, tokenId).
2. Setiap token mereferensikan satu node fisik yang terdaftar.
3. Sebuah kunci dipetakan ke token pertama searah jarum jam, melakukan wrap-around pada batas ring.
4. Kumpulan token node fisik dihasilkan hanya dari ID stabil, indeks, dan jumlah yang dikonfigurasi.

Penentu tie-breaker sekunder tokenId membuat nilai hash yang sama menjadi deterministik. Ini tidak menganggap bahwa tabrakan tidak mungkin terjadi.

2. Hasilkan token virtual secara deterministik

Untuk node n dan indeks virtual i, lakukan hash pada byte dari n + "#" + i. Hasilkan indeks weight × V. Oleh karena itu, bobot yang lebih tinggi memiliki lebih banyak interval sesuai ekspektasi. Gunakan implementasi hash yang tetap dan pertahankan kebijakan V serta bobot bersama dengan snapshot ring; mengubahnya secara diam-diam akan memetakan ulang kunci.

Sebuah implementasi dapat menggunakan pohon seimbang (balanced tree) untuk penyisipan dan penghapusan O(log M). Array terurut yang ramah wawancara menjaga invarian tetap terlihat; pembaruan keanggotaan batch dapat membangun kembali array sekali daripada menggesernya berulang kali.

3. Implementasikan pencarian dan pembaruan

from bisect import bisect_left

class ConsistentHashRing:
    def __init__(self, virtuals_per_weight, hash64):
        self.v = virtuals_per_weight
        self.hash64 = hash64
        self.tokens = []  # (hash, token_id, node_id)
        self.by_node = {}

    def add_node(self, node_id, weight=1):
        if weight <= 0 or node_id in self.by_node:
            raise ValueError("invalid or duplicate node")
        owned = []
        for i in range(weight * self.v):
            token_id = f"{node_id}#{i}"
            owned.append((self.hash64(token_id), token_id, node_id))
        self.by_node[node_id] = owned
        self.tokens.extend(owned)
        self.tokens.sort()

    def remove_node(self, node_id):
        owned = self.by_node.pop(node_id, None)
        if owned is None:
            return False
        owned_ids = {token_id for _, token_id, _ in owned}
        self.tokens = [t for t in self.tokens if t[1] not in owned_ids]
        return True

    def get_node(self, key):
        if not self.tokens:
            return None
        h = self.hash64(key)
        i = bisect_left(self.tokens, (h, "", ""))
        return self.tokens[i if i < len(self.tokens) else 0][2]

Kode ini memperlakukan node duplikat sebagai kesalahan pemanggil dan penghapusan node yang tidak ada sebagai no-op. Di lingkungan produksi, pembaruan biasanya akan membuat snapshot baru dan mempublikasikannya secara atomik sehingga pembaca tidak pernah mengamati ring yang baru diperbarui sebagian.

4. Turunkan kompleksitas dan perilaku pemetaan ulang

Dengan M = V × sum(weight), pencarian adalah O(log M) dan O(1) ruang ekstra per panggilan. Penyisipan dan penghapusan pada implementasi array adalah O(M + K log M) karena pengurutan dan pemfilteran, di mana K adalah jumlah token node yang diubah; pohon seimbang mengurangi pembaruan menjadi O(K log M). Memori adalah O(M).

Ketika sebuah node ditambahkan, hanya kunci dalam interval tepat sebelum token virtualnya yang berpindah ke node tersebut. Ketika sebuah node dihapus, interval tersebut berpindah ke pemilik berikutnya searah jarum jam. Ini adalah keunggulan monotonisitas dibandingkan modulo hashing, di mana perubahan N memetakan ulang sebagian besar kunci. Virtual node mengurangi varians tetapi tidak dapat mengatasi satu hot key atau beban kerja yang timpang.

Contoh jawaban berkualitas tinggi

“Saya merepresentasikan ring sebagai rekaman (hash, tokenId, nodeId) yang terurut ditambah map dari ID node ke rekamannya. addNode membuat weight × V token virtual deterministik; removeNode menghapus tepat rekaman-rekaman tersebut. getNode menggunakan pencarian lower-bound dan melakukan wrap-around. Invariannya adalah setiap kunci memiliki token aktif pertama searah jarum jam, dengan (hash, tokenId) menyelesaikan tabrakan secara deterministik. Pencarian bernilai O(log M); array terurut membuat pembaruan bernilai O(M + K log M), sedangkan pohon dapat membuatnya bernilai O(K log M). Saya akan menguji ring kosong dan satu node, wrap-around, ID duplikat, tabrakan, penghapusan, distribusi berbobot, dan fraksi kunci yang dipetakan ulang setelah perubahan keanggotaan.”

Kesalahan umum

• Menggunakan hash(key) % N → mengubah jumlah node memetakan ulang sebagian besar kunci → cari token berikutnya searah jarum jam.
• Mengasumsikan tabrakan tidak dapat terjadi → hash yang sama menghasilkan kepemilikan yang tidak stabil → tentukan tie-break dengan ID token deterministik.
• Menghasilkan token acak pada setiap restart → semua kunci berpindah secara tak terduga → turunkan token dari ID node stabil dan indeks.
• Menghapus hanya berdasarkan awalan nama node → ID yang mirip dapat menghapus rekaman yang salah → simpan reverse map eksplisit dan ID token.
• Mengklaim virtual node menghilangkan hotspot → satu kunci populer tetap menargetkan satu pemilik → tambahkan replikasi, perutean sadar-beban (load-aware), atau penanganan hot-key sebagai persyaratan terpisah.
• Mengabaikan kasus kosong dan duplikat → invarian pencarian atau pembaruan gagal pada batas batasnya → tentukan perilaku nilai kembali dan kesalahan sebelum coding.

Pertanyaan lanjutan dan tanggapan

Bagaimana cara Anda mengembalikan tiga replika?

Telusuri searah jarum jam dari pemilik dan kumpulkan ID node fisik yang berbeda hingga tiga ditemukan. Lewati token virtual tambahan milik node yang sudah dipilih; jika ada kurang dari tiga node aktif, kembalikan set yang tersedia dan kekurangan yang eksplisit.

Bagaimana Anda menguji distribusi alih-alih satu contoh saja?

Hasilkan korpus kunci yang tetap, ukur bagian masing-masing node dan rasio maksimum-ke-minimum, lalu ulangi setelah menambah dan menghapus node. Jaga agar seed hash tetap konstan sehingga regresi dapat direproduksi.

Bagaimana jika kapasitas sebuah node berubah?

Hapus set token lamanya, tambahkan set baru menggunakan bobot yang baru, dan publikasikan satu snapshot. Harapkan hanya interval yang berdekatan dengan token yang diubah yang berpindah, tetapi pantau beban selama transisi.

Kapan modulo hashing lebih sederhana?

Jika keanggotaan tetap atau penyeimbangan ulang penuh dapat diterima, modulo hashing lebih pendek dan sering kali lebih cepat. Consistent hashing sepadan dengan kompleksitasnya ketika keanggotaan berubah dan biaya pemetaan ulang menjadi pertimbangan penting.