Bagaimanakah anda melaksanakan gelang cincin hash konsisten dengan nod maya?

Soalan dan skop

Laksanakan gelang cincin untuk menghalakan kunci rentetan kepada nod fizikal. API tersebut ialah addNode(nodeId, weight), removeNode(nodeId), dan getNode(key). Satu nod menerima weight × V token maya, di mana V ialah kiraan asas yang dikonfigurasikan. Gunakan abstraksi hash 64-bit yang deterministik, pastikan perlanggaran dikendalikan dengan selamat, dan kembalikan token hidup pertama mengikut arah jam dari kunci tersebut. Jika gelang cincin kosong, getNode tidak mengembalikan sebarang nod.

Ini ialah masalah pengekodan, bukan perkhidmatan keahlian atau replikasi yang lengkap. Kemas kini keahlian diandaikan disiri (serialized) oleh pemanggil. Penyelesaian mesti menerangkan mengapa penambahan atau penyingkiran nod hanya mengubah selang kunci berdekatan, dan di mana sifat tersebut berhenti membantu, seperti kunci hangat (hot key) atau hash yang dipilih dengan buruk.

Perkara yang diuji oleh penemu duga

PracHub merekodkan ini sebagai soalan saringan teknikal Jurutera Perisian DoorDash dengan addNode, removeNode, dan getNode, pengimbangan nod maya, pengendalian perlanggaran, dan analisis kerumitan. Rekod temu duga awam DoorDash baru-baru ini juga menerangkan tentang membaiki pengimbang beban round-robin dan melaksanakan hash konsisten.

Isyarat yang dinilai ialah reka bentuk struktur data yang boleh dilaksanakan: carian terisih, identiti token yang stabil, kemas kini selamat daripada pendua, invarian yang jelas, serta ujian untuk wrap-around dan perubahan keahlian. Kertas asal MIT mentakrifkan sifat berguna sebagai keseimbangan (balance) dan kemonotonan (monotonicity): tugasan harus kekal agak sekata, dan menambah baldi (bucket) tidak sepatutnya memetakan semula kunci yang boleh kekal pada baldi lama mereka.

Soalan penjelasan sebelum menjawab

1. Adakah ID nod unik dan stabil merentasi permulaan semula (restarts)? ID yang stabil diperlukan untuk mengalih keluar tepat token-token yang dimiliki oleh satu nod fizikal.
2. Adakah weight satu integer? Jawapan ini mengandaikan integer positif; kapasiti pecahan memerlukan belanjawan token yang dinormalisasi.
3. Adakah kemas kini keahlian serentak dengan carian? Jika ya, terbitkan snapshot yang tidak boleh diubah (immutable) atau tambah kunci baca/tulis; kod di bawah mengandaikan kemas kini yang disiri.
4. Adakah replikasi diperlukan? API asas mengembalikan satu pemilik. Mengembalikan R pengganti berbeza ialah soalan susulan dengan peraturan kegagalan dan token pendua.
5. Apakah fungsi hash yang tersedia? Anggap ia sebagai deterministik dan seragam untuk latihan ini; pilihan pengeluaran memerlukan semakan perlanggaran dan input adversari.

Rangka jawapan 30 saat

“Saya menyimpan rekod (token, virtualNodeId, physicalNodeId) dalam susunan terisih. Menambah nod memasukkan weight × V token deterministik; mengalih keluarnya memadamkan tepat token-token tersebut. Carian menghashkan kunci, membuat carian binari untuk token pertama pada atau selepasnya, dan wrap-around ke indeks sifar. Invariannya ialah setiap token memetakan kepada satu nod fizikal yang hidup dan setiap kunci memiliki token pertama mengikut arah jam. Carian ialah O(log M), kemas kini ialah O(V·weight·log M), dan saya menguji perlanggaran, wrap-around, kemas kini pendua, penyingkiran, gelang cincin kosong, dan pemetaan semula kunci.”

Jawapan mendalam langkah demi langkah

1. Pilih perwakilan dan invarian

Biar M menjadi bilangan token maya. Simpan tatasusunan rekod yang terisih dan peta daripada ID nod fizikal kepada rekaman token yang dijana. Tatasusunan terisih menjadikan carian sebagai carian batas bawah (lower-bound search); peta songsang menjadikan penyingkiran tepat dan bukannya mengimbas awalan yang sepadan.

Invariannya ialah:

1. Token diisih mengikut (hash, tokenId).
2. Setiap token merujuk kepada satu nod fizikal yang berdaftar.
3. Kunci dipetakan kepada token pertama mengikut arah jam, melakukan wrap-around pada sempadan gelang cincin.
4. Set token nod fizikal dijana hanya daripada ID stabil, indeks, dan kiraan yang dikonfigurasikan.

Pemutus seri sekunder tokenId menjadikan nilai hash yang sama sebagai deterministik. Ia tidak menganggap bahawa perlanggaran adalah mustahil.

2. Jana token maya secara deterministik

Untuk nod n dan indeks maya i, hashkan bait bagi n + "#" + i. Jana indeks weight × V. Oleh itu, berat yang lebih tinggi memiliki lebih banyak selang mengikut jangkaan. Gunakan pelaksanaan hash yang tetap dan kekalkan dasar V serta berat bersama snapshot gelang cincin; mengubahnya secara senyap akan memetakan semula kunci.

Sesuatu pelaksanaan boleh menggunakan pokok seimbang (balanced tree) untuk pemasukan dan pemadaman O(log M). Tatasusunan terisih yang mesra temu duga memastikan invarian sentiasa jelas; kemas kini keahlian kelompok boleh membina semula tatasusunan sekali sahaja daripada menganjaknya berulang kali.

3. Laksanakan carian dan kemas kini

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]

Kod ini menganggap nod pendua sebagai ralat pemanggil dan penyingkiran nod yang tiada sebagai no-op. Dalam pengeluaran, kemas kini biasanya akan membina snapshot baharu dan menerbitkannya secara atomik supaya pembaca tidak pernah melihat gelang cincin yang dikemas kini separuh jalan.

4. Terbitkan kerumitan dan tingkah laku pemetaan semula

Dengan M = V × sum(weight), carian ialah O(log M) dan O(1) ruang tambahan bagi setiap panggilan. Pemasukan dan penyingkiran bagi pelaksanaan tatasusunan ialah O(M + K log M) disebabkan pengisihan dan penapisan, di mana K ialah kiraan token bagi nod yang diubah; pokok seimbang mengurangkan kemas kini kepada O(K log M). Memori ialah O(M).

Apabila nod ditambah, hanya kunci dalam selang sebelum token mayanya yang berpindah kepadanya. Apabila nod dialih keluar, selang tersebut berpindah kepada pemilik seterusnya mengikut arah jam. Ini ialah kelebihan kemonotonan berbanding pemetakan modulo, di mana menukar N memetakan semula kebanyakan kunci. Nod maya mengurangkan varians tetapi tidak dapat menyelesaikan satu kunci hangat atau beban kerja yang condong.

Contoh jawapan berkualiti tinggi

“Saya mewakili gelang cincin sebagai rekod (hash, tokenId, nodeId) yang terisih ditambah peta daripada ID nod kepada rekodnya. addNode mencipta weight × V token maya deterministik; removeNode memadamkan tepat rekod-rekod tersebut. getNode menggunakan carian batas bawah dan melakukan wrap-around. Invariannya ialah setiap kunci memiliki token hidup pertama mengikut arah jam, dengan (hash, tokenId) menyelesaikan perlanggaran secara deterministik. Carian ialah O(log M); tatasusunan terisih menjadikan kemas kini O(M + K log M), manakala struktur pokok boleh menjadikannya O(K log M). Saya akan menguji gelang cincin kosong dan satu nod, wrap-around, ID pendua, perlanggaran, penyingkiran, taburan berpemberat, dan pecahan kunci yang dipetakan semula selepas perubahan keahlian.”

Kesilapan lazim

• Menggunakan hash(key) % N → menukar kiraan nod memetakan semula kebanyakan kunci → cari token seterusnya mengikut arah jam.
• Menganggap perlanggaran tidak boleh berlaku → hash yang sama menghasilkan pemilikan tidak stabil → putuskan seri menggunakan ID token deterministik.
• Menjana token rawak pada setiap permulaan semula → semua kunci berpindah secara tidak dijangka → terbitkan token daripada ID nod stabil dan indeks.
• Mengalih keluar mengikut awalan nama nod sahaja → ID yang serupa boleh memadamkan rekod yang salah → simpan peta songsang yang jelas dan ID token.
• Mendakwa nod maya menghapuskan titik panas (hotspots) → satu kunci popular masih menyasarkan satu pemilik → tambah replikasi, penghalaan peka-beban, atau pengendalian hot-key sebagai keperluan berasingan.
• Mengabaikan kes kosong dan pendua → invarian carian atau kemas kini gagal pada sempadan → takrifkan tingkah laku pulangan dan ralat sebelum mengekod.

Soalan susulan dan maklum balas

Bagaimanakah anda akan mengembalikan tiga replika?

Bergerak mengikut arah jam daripada pemilik dan kumpulkan ID nod fizikal yang berbeza sehingga tiga ditemui. Langkau token maya tambahan milik nod yang telah dipilih; jika kurang daripada tiga nod hidup wujud, kembalikan set yang tersedia berserta kekurangan yang jelas.

Bagaimanakah anda menguji taburan dan bukannya satu contoh sahaja?

Jana korpus kunci yang tetap, ukur bahagian setiap nod dan nisbah maksimum kepada minimum, kemudian ulangi selepas menambah dan mengalih keluar nod. Kekalkan benih (seed) hash tetap supaya regresi boleh dihasilkan semula.

Bagaimana jika kapasiti sesuatu nod berubah?

Alih keluar set token lamanya, tambah set baharu menggunakan berat baharu, dan terbitkan satu snapshot. Jangkakan hanya selang yang bersebelahan dengan token yang diubah akan berpindah, tetapi pantau beban semasa peralihan.

Bilakah pemetakan modulo lebih mudah?

Jika keahlian adalah tetap atau pengimbangan semula penuh boleh diterima, pemetakan modulo adalah lebih pendek dan selalunya lebih pantas. Hash konsisten membuktikan kepentingannya apabila keahlian berubah dan kos pemetaan semula menjadi pertimbangan utama.