वर्चुअल नोड्स के साथ कंसिस्टेंट हैश रिंग को कैसे लागू करें?

प्रश्न और कार्यक्षेत्र (Scope)

स्ट्रिंग कीज को फिजिकल नोड्स पर रूट करने के लिए एक रिंग लागू करें। API addNode(nodeId, weight), removeNode(nodeId) और getNode(key) है। एक नोड को weight × V वर्चुअल टोकन प्राप्त होते हैं, जहाँ V एक कॉन्फ़िगर की गई बेस काउंट है। एक डिटरमिनिस्टिक 64-बिट हैश एब्स्ट्रैक्शन का उपयोग करें, कॉलिजन्स को सुरक्षित रूप से हैंडल करें, और की से क्लॉकवाइज़ पहला लाइव टोकन लौटाएं। यदि रिंग खाली है, तो getNode कोई नोड नहीं लौटाता है।

यह एक कोडिंग समस्या है, कोई पूर्ण मेंबरशिप या रेप्लिकेशन सर्विस नहीं है। यह माना जाता है कि मेंबरशिप अपडेट कॉलर द्वारा सीरियलाइज़ किए जाते हैं। समाधान में यह स्पष्ट किया जाना चाहिए कि नोड के जुड़ने या हटने से केवल आस-पास के की-इंटरवेल्स ही क्यों बदलते हैं, और यह प्रॉपर्टी कहाँ काम करना बंद कर देती है, जैसे कि हॉट की (hot key) या खराब तरीके से चुने गए हैश के मामले में।

इंटरव्यूअर क्या टेस्ट कर रहा है

PracHub इसे DoorDash सॉफ़्टवेयर इंजीनियर टेक्निकल-स्क्रीन प्रश्न के रूप में रिकॉर्ड करता है जिसमें addNode, removeNode और getNode, वर्चुअल-नोड बैलेंसिंग, कॉलिजन हैंडलिंग और जटिलता विश्लेषण शामिल हैं। DoorDash का एक हालिया सार्वजनिक इंटरव्यू रिकॉर्ड भी राउंड-रॉबिन लोड बैलेंसर को ठीक करने और कंसिस्टेंट हैशिंग को लागू करने का वर्णन करता है।

इसका सिग्नल एक एक्ज़ीक्यूटेबल डेटा-स्ट्रक्चर डिज़ाइन है: सॉर्टेड लुकअप, स्थिर टोकन पहचान, डुप्लिकेट-सुरक्षित अपडेट, एक स्पष्ट इनवेरिएंट, और रैप-अराउंड व मेंबरशिप परिवर्तनों के लिए टेस्ट। MIT का मूल पेपर उपयोगी विशेषताओं को बैलेंस (balance) और मोनोटोनिसिटी (monotonicity) के रूप में परिभाषित करता है: असाइनमेंट उचित रूप से समान होने चाहिए, और एक बकेट जोड़ने पर उन कीज को रीमैप नहीं किया जाना चाहिए जो अपने पुराने बकेट पर रह सकती हैं।

उत्तर देने से पहले स्पष्टीकरण प्रश्न

1. क्या नोड ID यूनिक हैं और रीस्टार्ट के बाद भी स्थिर रहती हैं? एक फिजिकल नोड से संबंधित टोकन को सटीक रूप से हटाने के लिए स्थिर ID आवश्यक हैं।
2. क्या weight एक पूर्णांक (integer) है? यह उत्तर एक धनात्मक पूर्णांक मानता है; भिन्नात्मक (fractional) क्षमता के लिए एक सामान्यीकृत (normalized) टोकन बजट की आवश्यकता होती है।
3. क्या मेंबरशिप अपडेट लुकअप्स के साथ समवर्ती (concurrent) हैं? यदि हाँ, तो एक इम्यूटेबल स्नैपशॉट प्रकाशित करें या रीड/राइट लॉक जोड़ें; नीचे दिया गया कोड सीरियलाइज़्ड अपडेट्स मानता है।
4. क्या रेप्लिकेशन की आवश्यकता है? मूल API एक ओनर लौटाता है। R विशिष्ट उत्तराधिकारी (successors) लौटाना एक फॉलो-अप प्रश्न है जिसमें विफलता और डुप्लिकेट-टोकन नियम शामिल होते हैं।
5. कौन सा हैश फ़ंक्शन उपलब्ध है? इस अभ्यास के लिए इसे डिटरमिनिस्टिक और यूनिफ़ॉर्म मानें; प्रोडक्शन के विकल्पों के लिए कॉलिजन और एडवरसैरियल-इनपुट समीक्षा की आवश्यकता होती है।

30-सेकंड का उत्तर ढाँचा

"मैं (token, virtualNodeId, physicalNodeId) रिकॉर्ड्स को सॉर्टेड क्रम में संग्रहीत करता हूँ। एक नोड जोड़ने पर weight × V डिटरमिनिस्टिक टोकन इन्सर्ट होते हैं; इसे हटाने पर केवल वही टोकन डिलीट होते हैं। लुकअप की (key) को हैश करता है, उस पर या उसके बाद के पहले टोकन को बाइनरी-सर्च करता है, और इंडेक्स शून्य पर रैप-अराउंड करता है। इनवेरिएंट यह है कि प्रत्येक टोकन एक लाइव फिजिकल नोड पर मैप होता है और प्रत्येक की क्लॉकवाइज़ पहले टोकन की ओनर होती है। लुकअप O(log M) है, अपडेट O(V·weight·log M) हैं, और मैं कॉलिजन्स, रैप-अराउंड, डुप्लिकेट अपडेट, रिमूवल, खाली रिंग्स और की रीमैपिंग का परीक्षण करता हूँ।"

चरण-दर-चरण विस्तृत उत्तर

1. रिप्रजेंटेशन और इनवेरिएंट चुनें

मान लें कि M वर्चुअल टोकन की संख्या है। रिकॉर्ड्स की एक सॉर्टेड एरे और फिजिकल नोड ID से उसके जनरेट किए गए टोकन रिकॉर्ड्स का एक मैप रखें। सॉर्टेड एरे लुकअप को एक लोअर-बाउंड सर्च बनाती है; रिवर्स मैप मैचिंग प्रीफिक्स को स्कैन करने के बजाय सटीक रूप से रिमूव करने की सुविधा देता है।

इनवेरिएंट निम्नलिखित है:

1. टोकन (hash, tokenId) द्वारा सॉर्ट किए गए हैं।
2. प्रत्येक टोकन एक रजिस्टर्ड फिजिकल नोड को संदर्भित करता है।
3. एक की क्लॉकवाइज़ पहले टोकन पर मैप होती है, जो रिंग बाउंड्री पर रैप-अराउंड होती है।
4. एक फिजिकल नोड का टोकन सेट केवल उसकी स्थिर ID, इंडेक्स और कॉन्फ़िगर की गई काउंट से जनरेट होता है।

सेकेंडरी tokenId टाई-ब्रेकर समान हैश वैल्यूज को डिटरमिनिस्टिक बनाता है। यह ऐसा दावा नहीं करता कि कॉलिजन्स असंभव हैं।

2. वर्चुअल टोकन डिटरमिनिस्टिक रूप से जनरेट करें

नोड n और वर्चुअल इंडेक्स i के लिए, n + "#" + i के बाइट्स को हैश करें। weight × V इंडेक्स जनरेट करें। इसलिए अधिक वेट (weight) अपेक्षा के अनुसार अधिक इंटरवेल्स का स्वामित्व रखता है। एक निश्चित हैश कार्यान्वयन का उपयोग करें और रिंग स्नैपशॉट के साथ V और वेट पॉलिसी को बनाए रखें; इन्हें बदलने से कीज चुपचाप रीमैप हो जाती हैं।

एक कार्यान्वयन O(log M) इन्सर्शन और डिलीशन के लिए एक बैलेंस्ड ट्री का उपयोग कर सकता है। इंटरव्यू के अनुकूल सॉर्टेड एरे इनवेरिएंट को स्पष्ट रखती है; बैच मेंबरशिप अपडेट एरे को बार-बार शिफ्ट करने के बजाय एक बार में रीबिल्ड कर सकते हैं।

3. लुकअप और अपडेट्स लागू करें

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]

कोड डुप्लिकेट नोड को कॉलर एरर और अनुपस्थित नोड को हटाने को no-op मानता है। प्रोडक्शन में, अपडेट आम तौर पर एक नया स्नैपशॉट बनाएंगे और इसे एटॉमिक रूप से प्रकाशित करेंगे ताकि रीडर्स कभी भी आधा-अधूरा अपडेटेड रिंग न देखें।

4. जटिलता और रीमैपिंग व्यवहार प्राप्त करें

M = V × sum(weight) के साथ, लुकअप O(log M) और प्रति कॉल O(1) अतिरिक्त स्पेस है। एरे कार्यान्वयन में इन्सर्शन और रिमूवल सॉर्टिंग और फ़िल्टरिंग के कारण O(M + K log M) हैं, जहाँ K बदले गए नोड की टोकन संख्या है; एक बैलेंस्ड ट्री अपडेट्स को O(K log M) तक कम कर देता है। मेमोरी O(M) है।

जब कोई नोड जोड़ा जाता है, तो केवल उसके वर्चुअल टोकन से ठीक पहले के इंटरवेल्स की कीज उस पर स्थानांतरित होती हैं। जब कोई नोड हटाया जाता है, तो वे इंटरवेल्स अपने अगले क्लॉकवाइज़ ओनर्स के पास चले जाते हैं। मॉड्यूलो हैशिंग की तुलना में यह मोनोटोनिसिटी का लाभ है, जहाँ N बदलने पर अधिकांश कीज रीमैप हो जाती हैं। वर्चुअल नोड्स वेरिएंस को कम करते हैं लेकिन एक सिंगल हॉट की या विषम (skewed) वर्कलोड को ठीक नहीं कर सकते।

उच्च गुणवत्ता वाला नमूना उत्तर

"मैं रिंग को सॉर्टेड (hash, tokenId, nodeId) रिकॉर्ड्स और नोड ID से उसके रिकॉर्ड्स के मैप के रूप में दर्शाता हूँ। addNode डिटरमिनिस्टिक weight × V वर्चुअल टोकन बनाता है; removeNode बिल्कुल उन्हीं रिकॉर्ड्स को डिलीट करता है। getNode लोअर-बाउंड सर्च का उपयोग करता है और रैप-अराउंड करता है। इनवेरिएंट यह है कि प्रत्येक की क्लॉकवाइज़ पहले लाइव टोकन की ओनर होती है, जिसमें (hash, tokenId) कॉलिजन्स को डिटरमिनिस्टिक रूप से हल करता है। लुकअप O(log M) है; एक सॉर्टेड एरे अपडेट्स को O(M + K log M) बनाती है, जबकि एक ट्री इसे O(K log M) बना सकता है। मैं खाली और एक-नोड रिंग्स, रैप-अराउंड, डुप्लिकेट ID, कॉलिजन्स, रिमूवल, वेटेड डिस्ट्रीब्यूशन, और मेंबरशिप परिवर्तनों के बाद रीमैप की गई कीज के अनुपात का परीक्षण करूँगा।"

सामान्य गलतियाँ

• hash(key) % N का उपयोग करना → नोड काउंट बदलने से अधिकांश कीज रीमैप हो जाती हैं → अगले क्लॉकवाइज़ टोकन को खोजें।
• यह मान लेना कि कॉलिजन्स नहीं हो सकते → समान हैश अस्थिर ओनरशिप उत्पन्न करते हैं → डिटरमिनिस्टिक टोकन ID द्वारा टाई-ब्रेक करें।
• प्रत्येक रीस्टार्ट पर रैंडम टोकन जनरेट करना → सभी कीज अप्रत्याशित रूप से स्थानांतरित हो जाती हैं → स्थिर नोड ID और इंडेक्स से टोकन प्राप्त करें।
• केवल नोड-नेम प्रीफिक्स द्वारा हटाना → समान ID गलत रिकॉर्ड्स को हटा सकती हैं → एक स्पष्ट रिवर्स मैप और टोकन ID रखें।
• यह दावा करना कि वर्चुअल नोड्स हॉटस्पॉट्स को समाप्त करते हैं → एक सिंगल लोकप्रिय की अभी भी एक ही ओनर को टारगेट करेगी → रेप्लिकेशन, लोड-अवेयर रूटिंग, या हॉट-की ट्रीटमेंट को एक अलग आवश्यकता के रूप में जोड़ें।
• खाली और डुप्लिकेट मामलों को अनदेखा करना → बाउंड्री पर लुकअप या अपडेट इनवेरिएंट्स विफल हो जाते हैं → कोडिंग से पहले रिटर्न और एरर व्यवहार को परिभाषित करें।

फॉलो-अप और उत्तर

आप तीन रेप्लिका कैसे लौटाएंगे?

ओनर से क्लॉकवाइज़ दिशा में आगे बढ़ें और तीन मिलने तक विशिष्ट फिजिकल नोड ID एकत्र करें। पहले से चयनित नोड से संबंधित अतिरिक्त वर्चुअल टोकन को छोड़ दें; यदि तीन से कम लाइव नोड्स मौजूद हैं, तो उपलब्ध सेट और एक स्पष्ट कमी (shortfall) लौटाएं।

आप केवल एक उदाहरण के बजाय डिस्ट्रीब्यूशन का परीक्षण कैसे करते हैं?

कीज का एक निश्चित संग्रह जनरेट करें, प्रत्येक नोड के शेयर और अधिकतम-से-न्यूनतम अनुपात को मापें, फिर एक नोड जोड़ने और हटाने के बाद इसे दोहराएं। हैश सीड को स्थिर रखें ताकि रिग्रेशन दोहराने योग्य (reproducible) हों।

क्या होगा यदि किसी नोड की क्षमता बदल जाती है?

इसके पुराने टोकन सेट को हटाएं, नए वेट का उपयोग करके एक नया सेट जोड़ें, और एक स्नैपशॉट प्रकाशित करें। अपेक्षा करें कि केवल बदले गए टोकन से सटे इंटरवेल्स ही स्थानांतरित हों, लेकिन ट्रांज़िशन के दौरान लोड की निगरानी करें।

मॉड्यूलो हैशिंग कब सरल होती है?

यदि मेंबरशिप निश्चित है या पूर्ण रीबैलेंसिंग स्वीकार्य है, तो मॉड्यूलो हैशिंग छोटी और अक्सर तेज़ होती है। कंसिस्टेंट हैशिंग अपनी जटिलता को तब सही साबित करती है जब मेंबरशिप बदलती है और रीमैपिंग की लागत मायने रखती है।