संगत हैशिंग डिज़ाइन करें: रिंग, वर्चुअल नोड और न्यूनतम रीमैप

टीएल;डीआर

समस्या: बड़े पैमाने की वास्तुकला (आर्किटेक्चर) तैयार करने के लिए उपलब्धता, थ्रूपुट और परिचालन जटिलता के बीच संतुलन बनाना आवश्यक है।

मुख्य निष्कर्ष: जब एक सर्वर जाता है तो हैश(कुंजी) % एन लगभग सबको क्यों फिर बैठा देता है, हैश रिंग घड़ी की दिशा में चलकर कुंजियाँ कैसे जोड़ती है, न्यायसंगत लोड के लिए वर्चुअल नोड, और कैश, डेटाबेस व लोड बैलेंसर में संगत हैशिंग कहाँ दिखती है।

परिणाम: उत्पादन वातावरण में विफलता से निपटने और प्रदर्शन लक्ष्यों को हासिल करने की सटीक रूपरेखा।

आपके पास बहुत उपयोगकर्ता और बहुत कैश सर्वर हैं। हर डेटा का टुकड़ा (एक कुंजी) किसी एक सर्वर पर जाना चाहिए, और बाद में फिर मिलना चाहिए। जब सर्वर मरता है या क्षमता बढ़ती है, तो जितना कम डेटा हिल सके उतना बेहतर।

संगत हैशिंग (consistent hashing) कुंजियाँ रखने का मानक तरीका है ताकि सदस्यता बदलने पर डेटा का छोटा हिस्सा ही हिले, पूरा क्लस्टर नहीं।

यह पोस्ट विचार को एक रेस्तराँ के फ्लोर प्लान से बनाता है, फिर हैश रिंग, वर्चुअल नोड और असली सिस्टम से जोड़ता है।

साधारण भाषा में समस्या

कल्पना करें: रेस्तराँ में नंबर वाली मेज़ें। मेहमानों को बैठाते हैं आसान नियम से: मेहमान नंबर लो, मेज़ों की संख्या से भाग दो, शेषफल लो।

table = guestNumber % numberOfTables

जब तक मेज़ों की संख्या नहीं बदलती, यह चलता है।

एक मेज़ बंद, अफरा-तफरी

मान लें ४ मेज़ें और ८ नियमित मेहमान:

मेहमान	guestNumber	number % ४	मेज़
A	११	३	T३
B	१४	२	T२
C	१७	१	T१
D	२०	०	T०
E	२३	३	T३
F	२६	२	T२
G	२९	१	T१
H	३२	०	T०

मेज़ T१ टूट गई। अब ३ मेज़ें। वही नंबर, नया शेषफल:

मेहमान	guestNumber	number % ३	मेज़
A	११	२	T२
B	१४	२	T२
C	१७	२	T२
D	२०	२	T२
E	२३	२	T२
F	२६	२	T२
G	२९	२	T२
H	३२	२	T२

असली तालिका में भी आप एक से अधिक मेज़ पर गिरते हैं, लेकिन दर्दनाक बात वही रहती है: ज़्यादातर लोग सीट बदलते हैं, सिर्फ टूटी मेज़ वाले नहीं।

कैश क्लस्टर में इसका मतलब:

१. क्लाइंट गलत नोड से डेटा माँगते हैं जो कहीं और अब भी मौजूद है। २. मिस की बाढ़ डेटाबेस पर गिरती है। ३. आप लगभग १/N कैश खोना चाहते थे। लगभग पूरा ठंडा स्टार्ट चुकाया।

यही रीहैशिंग की समस्या है। hash(key) % N तब तक ठीक है जब तक N न बदले। फिर यह लगभग पूरा रेस्तराँ फिर बैठा देता है।

बेहतर प्लान: गोलाकार गलियारे में लॉकर

लंबा गलियारा सोचें, लॉकर गोलाकार नंबर पर। एक दिशा में काफी चलो तो लॉकर ० पर वापस आ जाते हो। यही वृत्त हैश स्पेस है।

              0
          .         .
       .               .
     .                   .
   max                     small
     .                   .
       .               .
          .         .
            mid ring

दो विचार:

१. सर्वर को स्थिर लॉकर नंबर मिलते हैं (नाम या आईपी हैश करके)। २. कुंजियों को भी लॉकर नंबर मिलते हैं (कुंजी हैश करके)।

% numberOfServers नहीं। स्थान एक स्थिर सीमा में रहते हैं, जैसे 0 से 2^32 - 1 या बड़ा हैश स्पेस। सर्वर जाने पर वृत्त सिकुड़ता नहीं।

स्थिर सीटों पर वेटर

हर सर्वर को गोल मेज़ पर एक सीट पर खड़ा वेटर समझें।

खिलौना रिंग, स्थान ० से ९९:

सर्वर	सीट
s०	१२
s१	३७
s२	६१
s३	८८

उसी वृत्त पर कुंजियाँ:

कुंजी	सीट
key०	१८
key१	४२
key२	७०
key३	९५

रिंग (0 से घड़ी की दिशा):

  0
  |-- s0@12 -- key0@18 -- s1@37 -- key1@42 --
  |-- s2@61 -- key2@70 -- s3@88 -- key3@95 -- (0 पर वापस)

लुकअप: घड़ी की दिशा में वेटर तक चलो

नियम:

१. कुंजी को सीट नंबर p में हैश करो। २. घड़ी की दिशा में चलो जब तक अगली सर्वर सीट न मिले। ३. वही सर्वर कुंजी का मालिक है।

कुंजी	सीट	घड़ी की दिशा में पहला सर्वर	मालिक
key०	१८	s१@३७	s१
key१	४२	s२@६१	s२
key२	७०	s३@८८	s३
key३	९५	s०@१२ (गोल घूमकर)	s०

कोड में सर्वर सीटें सॉर्ट रखो और p से बड़ी या बराबर पहली स्थिति बाइनरी सर्च से ढूँढो। न मिले तो रिंग की पहली सीट पर लौटो।

import bisect
import hashlib

def h(x: str) -> int:
    # खिलौना 32-बिट स्पेस; प्रोडक्शन में अक्सर 64-बिट या बड़ा
    return int(hashlib.md5(x.encode()).hexdigest()[:8], 16)

class HashRing:
    def __init__(self, nodes: list[str]):
        self.positions: list[int] = []
        self.owners: dict[int, str] = {}
        for n in nodes:
            p = h(n)
            self.positions.append(p)
            self.owners[p] = n
        self.positions.sort()

    def lookup(self, key: str) -> str:
        p = h(key)
        i = bisect.bisect_left(self.positions, p)
        if i == len(self.positions):
            i = 0  # रिंग पर वापस
        return self.owners[self.positions[i]]

इंटरव्यू वाक्य: "सॉर्टेड पोज़िशन प्लस बाइनरी सर्च, रिंग बिंदुओं पर लगभग O(log n)।"

वेटर जोड़ो: सिर्फ आस-पास के मेहमान हिलते हैं

s4 सीट २५ पर जोड़ो।

पहले: key0@18 चलकर s1@37 पर जाती थी।

बाद: १८ से पहला सर्वर अब s4@25 है। सिर्फ उस आर्क की कुंजियाँ नया मालिक पाती हैं जो पुराने पड़ोसी की थीं।

पहले:  ... s0@12 -- key0@18 -------- s1@37 ...
बाद:   ... s0@12 -- key0@18 -- s4@25 -- s1@37 ...
                    सिर्फ यह आर्क s4 पर रीमैप

सर्वर जोड़ने पर क्या हिले: नए सर्वर और घड़ी के उल्टे पिछले सर्वर के बीच की कुंजियाँ। बाकी सब अपने वेटर पर रहते हैं।

वेटर हटाओ: सिर्फ उसके मेहमान हिलते हैं

s1@37 हटाओ।

जो कुंजियाँ s1 को घड़ी की दिशा का पहला सर्वर मानती थीं, वे अगले जीवित सर्वर (s2@61) तक चलती रहती हैं। दूसरे सर्वरों की कुंजियाँ नहीं हिलतीं।

पहले: जो s1 को पहले छूती थीं -> s1
बाद:  वे कुंजियाँ s2 तक जाती हैं; बाकी आर्क ज्यों के त्यों

कैश में उस आर्क पर मिस का तूफान अभी भी आता है। पूरा रेस्तराँ फिर नहीं बैठता।

अंगूठा नियम: n में से १ सर्वर बदले तो औसतन लगभग k/n कुंजियाँ हिलती हैं (कुल k कुंजियाँ), लगभग सभी नहीं।

संगत हैशिंग क्या वादा करती है (और क्या नहीं)

लक्ष्य	क्यों ज़रूरी
जुड़ने/छोड़ने पर न्यूनतम रीमैप	कैश स्टैंप और लंबे रीबैलेंस से बचना
पर्याप्त समान लोड	एक बॉक्स रिंग का ज़्यादातर हिस्सा न रखे
निश्चित लुकअप	एक जैसी सदस्यता = एक जैसा मालिक
सस्ता हिसाब	प्लेसमेंट हॉट पाथ पर है

यह अकेले रिप्लिकेशन, सख्त कंसिस्टेंसी, या ऑटो फेलओवर नहीं देती। वे ऊपर बैठते हैं: घड़ी की दिशा में अगले N सर्वर रिप्लिका, सदस्यता के लिए गॉसिप, आदि।

एक सीट प्रति वेटर की दो समस्याएँ

अन्यायपूर्ण आर्क

दो पड़ोसी सर्वरों के बीच वृत्त का टुकड़ा पार्टीशन है। अगर तीन वेटर संयोग से पास खड़े हों, तो एक विशाल आर्क का मालिक बन जाता है और उस ज़ोन का लगभग सारा काम करता है।

बुरी किस्मत का लेआउट:

  s0 -------- s1 - s2 ------------------- s3 ---- (वापस)

  s2 के पास विशाल खाली जगह; लोड तिरछा

इकट्ठा सीटें

विशाल रिंग पर कुछ ही भौतिक सर्वर हों तो रैंडम प्लेसमेंट ढेर बना सकता है। छोटा N अन्याय बढ़ाता है।

वर्चुअल नोड: हर वेटर की कई सीटें

वर्चुअल नोड रिंग पर एक अतिरिक्त सीट है जो फिर भी असली सर्वर की ओर इशारा करती है। हर भौतिक सर्वर अलग-अलग हैश से कई बार दिखता है:

s0 -> s0_0, s0_1, s0_2, ...
s1 -> s1_0, s1_1, s1_2, ...

रेस्तराँ तस्वीर: हर वेटर की मेज़ के चारों ओर कई आरक्षित सीटें हैं, एक कुर्सी नहीं। काम बँटता है क्योंकि एक अकेला गैप पूरी रात तय नहीं करता।

खिलौना उदाहरण: प्रति सर्वर ३ वर्चुअल सीटें:

वर्चुअल id	असली सर्वर	सीट (उदाहरण)
s०_०	s०	१०
s०_१	s०	५५
s०_२	s०	९०
s१_०	s१	२२
s१_१	s१	४८
s१_२	s१	७३

लुकअप वही: घड़ी की दिशा में अगली वर्चुअल सीट तक चलो, फिर असली सर्वर पर जाओ।

key @ 50 -> अगला vnode s0_1@55 -> असली s0

इससे क्या फायदा

प्रभाव	समझ
कम विचरण	एक बड़े जुए की जगह कई छोटे आर्क
नरम स्केल-आउट	नया नोड कई पड़ोसियों से पतली स्लाइस चुराता है
भारित क्षमता	बड़ी मशीनों को अधिक वर्चुअल सीटें
न्यायसंगत लोड	काम मेज़ के चारों ओर घुल-मिल जाता है

क्लासिक लेख अक्सर प्रति सर्वर १०० से २०० वर्चुअल नोड सुझाते हैं ताकि लोड काफी समान रहे। अधिक वर्चुअल नोड: बेहतर संतुलन और मेमोरी में बड़ा रिंग मैप। ट्यून करो।

class VNodeRing:
    def __init__(self, nodes: list[str], vnodes: int = 150):
        self.positions: list[int] = []
        self.owners: dict[int, str] = {}
        for n in nodes:
            for i in range(vnodes):
                p = h(f"{n}#{i}")
                self.positions.append(p)
                self.owners[p] = n
        self.positions.sort()

    def lookup(self, key: str) -> str:
        p = h(key)
        i = bisect.bisect_left(self.positions, p)
        if i == len(self.positions):
            i = 0
        return self.owners[self.positions[i]]

क्लाइंट और सर्वर को हैश फंक्शन और वर्चुअल नोड गिनती पर सहमत होना चाहिए, वरना मालिक अलग-अलग लगेंगे।

कौन सी कुंजियाँ हिलें

सदस्यता बदलने पर रिंग पहले से रेंज तय कर देती है।

स्थान p पर सर्वर S जोड़ें:

prev = S का घड़ी के उल्टे पड़ोसी
(prev, p] में कुंजियाँ पुराने मालिक से S पर जाएँ

स्थान p पर सर्वर S हटाएँ:

prev = S का घड़ी के उल्टे पड़ोसी
next = S का घड़ी की दिशा का पड़ोसी
(prev, p] में कुंजियाँ S से next पर जाएँ

वर्चुअल नोड के साथ जुड़ने या जाने वाली मशीन की हर वर्चुअल सीट पर यही करो। कई छोटे ट्रांसफर एक विशाल ट्रांसफर से बेहतर।

शुद्ध कैश में "ट्रांसफर" अक्सर मतलब "नया मालिक मिस पर भरे।" डेटाबेस में रेंज जान-बूझकर स्ट्रीम करो और हैंडऑफ के दौरान लिखने नियंत्रित करो।

रिंग पर रिप्लिकेशन (छोटा जोड़)

संगत हैशिंग प्राथमिक रखती है। रिप्लिकेशन अक्सर "घड़ी की दिशा में आगे चलते रहो":

key -> N1 (प्राथमिक), N2, N3  # पहले तीन अलग भौतिक सर्वर

उसी भौतिक होस्ट पर गिरने वाली वर्चुअल सीटें छोड़ो ताकि रिप्लिका अलग मशीनों पर हों। Dynamo-शैली स्टोर और Cassandra टोकन रिंग यही पैटर्न उपयोग करते हैं। क्वोरम तभी बताएँ जब इंटरव्यू पूरा की-वैल्यू स्टोर डिज़ाइन बन जाए।

असल में कहाँ दिखता है

सिस्टम वर्ग	संगत हैशिंग कैसे दिखती है
वितरित कैश	Memcached क्लाइंट, मल्टी-नोड कैश शार्ड, सीडीएन एज प्लेसमेंट (और नज़दीकी रिश्तेदार)
डेटाबेस / KV स्टोर	Dynamo पार्टीशन, Cassandra टोकन रिंग, कई कस्टम हैश रिंग
चैट / रियल-टाइम	गिल्ड या चैनल का स्टिकी स्वामित्व ताकि स्केल इवेंट सब कुछ न फेर-बदल करे
लोड बैलेंसर	बैकएंड आने-जाने पर स्थिर चयन (Maglev और रिश्तेदार)
रिक्वेस्ट राउटिंग	हर अनुरोध पर केंद्रीय मैप के बिना स्टिकी उपयोगकर्ता, टेनेंट या शार्ड

संबंधित विचार, एक जैसे नहीं: jump consistent hash, rendezvous (HRW) hashing, और Maglev क्रमचयन (परम्यूटेशन) tables। इंटरव्यू में पहले संगत हैशिंग नाम लो, फिर कहो कि तेज़ लुकअप या कम मेमोरी के लिए वेरिएंट भी हैं।

इंटरव्यू फ्लो जो चला सकते हो

१. समस्या: hash % N N बदलते ही लगभग सबको फिर बैठा देता है। २. रिंग: स्थिर हैश स्पेस; सर्वर और कुंजियाँ बिंदु; जीवित % N नहीं। ३. लुकअप: घड़ी की दिशा में पहला सर्वर (सॉर्टेड सीट पर बाइनरी सर्च)। ४. जोड़ो/हटाओ: सिर्फ पड़ोसी आर्क रीमैप (लगभग १/n कुंजियाँ)। ५. दर्द: प्रति सर्वर एक सीट से अन्यायपूर्ण आर्क। ६. वर्चुअल नोड: प्रति भौतिक सर्वर कई सीटें; न्यायसंगत लोड; वैकल्पिक वज़न। ७. ऑप्स: डेटा कैसे हिले, क्लाइंट सदस्यता कैसे जानें, अस्थायी गलत मालिक कैसे दिखें। ८. उपयोग: कैश, पार्टीशन्ड DB, स्टिकी लोड बैलेंसर।

जल्दी स्पष्ट करो:

सिर्फ कैश (रीमैप पर मिस ठीक) या टिकाऊ स्टोर (माइग्रेट ज़रूरी)?
रिप्लिकेशन फैक्टर?
सदस्यता किसके पास (स्थिर कॉन्फ़िग, ZooKeeper, गॉसिप)?
सदस्यता अपडेट के दौरान क्लाइंट थोड़ी देर गलत हो सकते हैं?

ज़ोर से कहने लायक ट्रेड-ऑफ़:

चुनाव	फायदा	कीमत
अधिक वर्चुअल नोड	समतल लोड	बड़ी रिंग, धीमे रीबिल्ड
क्लाइंट-साइड रिंग	प्रॉक्सी हॉप नहीं	हर क्लाइंट को एक जैसी सदस्यता चाहिए
प्रॉक्सी / कोऑर्डिनेटर	एक केंद्रीय दृश्य	अतिरिक्त हॉप
मिस पर कैश भरना	सरल ऑप्स	रीबैलेंस पर ओरिजिन स्पाइक
स्ट्रीमिंग माइग्रेशन	DB के लिए सुरक्षित	हैंडऑफ जटिलता

प्रोडक्शन चेकलिस्ट

हॉट पाथ पर हैश तेज़ और अच्छी तरह फैला हुआ हो
वर्चुअल नोड गिनती चुनी और लिखी हो; वज़न मशीन आकार से मेल खाएँ
लुकअप रिंग बिंदुओं पर O(log n) हो, लीनियर स्कैन नहीं
सदस्यता परिवर्तन वर्शन्ड हों; गलत-मालिक विंडो मापो
नोड खोने पर सिर्फ प्रभावित आर्क रीमाउंट या रिफिल हों
रिप्लिका उसी भौतिक होस्ट को छोड़ें
मीट्रिक: प्रति नोड कुंजियाँ, आर्क आकार, रीबैलेंस बाइट, जॉइन के दौरान मिस दर
"नोड जोड़ो" और "मृत नोड बदलो" के रनबुक बिना पूरे क्लस्टर रीस्टार्ट के

दोस्त के लिए सार

गोल रेस्तराँ सोचो। बेवकूफी भरा बैठाने का नियम है मेहमान नंबर % मेज़ों की संख्या। एक मेज़ बंद करो तो लगभग सब सीट बदलते हैं। यही hash(key) % N है।

स्मार्ट नियम मेज़ों (सर्वर) और मेहमानों (कुंजियाँ) को एक ही गोलाकार लॉकर गलियारे पर रखता है। मेहमान बैठाने के लिए घड़ी की दिशा में अगले वेटर तक चलो। एक मेज़ बंद करो तो सिर्फ उसी सेक्शन वाले अगले वेटर पर जाते हैं। बाकी यहीं रहते हैं।

अगर हर वेटर की सिर्फ एक सीट हो, किस्मत से सेक्शन विशाल या नन्हा हो सकते हैं। हर वेटर को वृत्त के चारों ओर कई आरक्षित सीटें दो (वर्चुअल नोड) ताकि काम न्यायसंगत रहे।

यही विचार कैश क्लस्टर, शार्डेड डेटाबेस और स्टिकी लोड बैलेंसर चलाता है: डेटा ऐसे रखो कि विकास और विफलता एक स्लाइस हिलाएँ, पूरा सिस्टम नहीं।

समापन

hash(key) % N तब तक ठीक है जब तक पूल न हिले। फिर लगभग सब रीमैप हो जाता है और स्केल इवेंट विश्वसनीयता इवेंट बन जाता है।

संगत हैशिंग कुंजियाँ और सर्वर साझा रिंग पर रखती है, हर कुंजी को घड़ी की दिशा के अगले सर्वर को देती है, और नोड जुड़ने-जाने पर रीमैप को स्थानीय आर्क तक सीमित रखती है। वर्चुअल नोड अन्यायपूर्ण आर्क ठीक करते हैं। अगर रिंग खींच सको, रीमैप सीमा समझा सको, और वर्चुअल नोड गिनती प्लस सदस्यता का बचाव कर सको, तो इंटरव्यू अध्याय और उसके ऊपर बैठे प्रोडक्शन सहज ज्ञान दोनों तुम्हारे हैं।