संक्षेप (टीएल;डीआर)
- समस्या:
hash(key) % Nसे कुंजियां रखना तब तक चलता है जब तक एन नहीं बदलता। दस कैश नोड में ग्यारहवां जोड़िए और लगभग ९०% कुंजियां अचानक कहीं और पहुंच जाती हैं, जिसका कैश के लिए मतलब है पीछे के डेटाबेस पर लगभग पूरी चूक की आंधी।- डिजाइन: कुंजियों और सर्वरों दोनों को एक ही गोलाकार स्थान पर हैश करें। कुंजी घड़ी की दिशा में मिलने वाले पहले सर्वर बिंदु की होती है। भार बराबर करने के लिए हर सर्वर को कुछ सौ वर्चुअल नोड दें, और अलग सर्वरों पर प्रतिकृतियां चुनने के लिए घड़ी की दिशा में आगे बढ़ते रहें।
- नतीजा: नोड जोड़ने या हटाने पर लगभग १/एन कुंजियां खिसकती हैं। १० नोड और हर एक के २०० वर्चुअल नोड वाले एक मापे गए प्रयोग में सबसे ज्यादा भार वाला नोड औसत का १.११ गुना उठा रहा था, जबकि हर नोड का एक बिंदु होने पर २.३ गुना।
ज्यादातर वितरित सिस्टमों को हर सेकंड लाखों बार एक उबाऊ सवाल का जवाब देना होता है: इस कुंजी की मालिक कौन सी मशीन है? कैश, बंटे हुए डेटाबेस, सत्र जुड़ाव चाहने वाले लोड बैलेंसर और ऑब्जेक्ट स्टोर, सबको ऐसा जवाब चाहिए जो तेज हो, जिसमें किसी केंद्रीय सूची की जरूरत न हो, और जो मशीन जुड़ने या गिरने पर बिखर न जाए।
कंसिस्टेंट हैशिंग इसका क्लासिक जवाब है। इसे कार्गर और साथियों ने १९९७ में वेब कैशिंग के लिए पेश किया, २००७ में अमेजन के डायनेमो शोध पत्र ने इसे लोकप्रिय बनाया, और आज यह कसांड्रा, मेमकैश्ड क्लाइंट, एनवॉय के लोड बैलेंसर और कई दूसरी जगहों में है। यह लेख बताता है कि यह कैसे काम करता है, मापता है कि वर्चुअल नोड असल में क्या देते हैं, और उन विकल्पों की बात करता है जो कभी-कभी बेहतर होते हैं।
hash(key) % N क्यों टूटता है
मॉड्यूलो से रखना पूरी तरह संतुलित है और पूरी तरह नाजुक भी। एन के एन+१ होने पर कोई कुंजी उसी नोड पर तभी रहती है जब h % N == h % (N+1) हो, जो लगभग हर एन+१ में से एक कुंजी के साथ होता है।
मैंने इसे २ लाख कुंजियों पर मापा:
| बदलाव | खिसकी कुंजियां |
|---|---|
% 10 से % 11 |
९०.७% |
| कंसिस्टेंट हैश रिंग, १० से ११ नोड, हर एक के २०० वर्चुअल नोड | ९.०% |
कैश के लिए ९०% खिसकने का मतलब है कि ९०% पठन एक साथ चूकते हैं और डेटाबेस पर गिरते हैं, अक्सर ठीक उसी समय जब आप भार ज्यादा होने की वजह से क्षमता बढ़ा रहे थे। बंटे हुए डेटाबेस के लिए इसका मतलब है एक मशीन जोड़ने के लिए ९०% डेटा खिसकाना। दोनों ही मंजूर नहीं।
रिंग
- हैश स्थान। बड़े आउटपुट वाला हैश फलन चुनें (६४ बिट काफी है) और उसकी सीमा को एक गोले की तरह मानें: सबसे बड़े मान के बाद शून्य आता है।
- रिंग पर सर्वर। हर सर्वर गोले पर हैश किया जाता है, व्यवहार में कई बार, वर्चुअल नोड के रूप में (चित्र में ए१, ए२, ए३)।
- रिंग पर कुंजियां। हर कुंजी उसी गोले पर हैश की जाती है।
- स्वामित्व। कुंजी उस पहले वर्चुअल नोड की होती है जो घड़ी की दिशा में चलते हुए मिले। के१ बी१ से ठीक पहले पड़ती है, इसलिए उसका मालिक सर्वर बी है।
- जुड़ना। नया सर्वर डी अपने वर्चुअल नोड रिंग पर रखता है। हर एक सिर्फ अपने और पिछले बिंदु के बीच का चाप लेता है। बाकी सब वहीं रहता है।
- हटना। जब कोई सर्वर हटता है, तो उसका हर चाप घड़ी की दिशा में अगले बिंदु में मिल जाता है। फिर से, सिर्फ उसी सर्वर की कुंजियां खिसकती हैं।
खोज, वर्चुअल नोड की क्रमबद्ध सूची पर द्विआधारी खोज है: O(log V), जहां वी कुल वर्चुअल नोड की संख्या है। १०० सर्वर और हर एक के २०० वर्चुअल नोड के साथ यह २०,००० पूर्णांकों पर खोज है, जो एक माइक्रोसेकंड से भी काफी कम लेती है।
import bisect, hashlib
def h(s: str) -> int:
return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")
class Ring:
def __init__(self, nodes, vnodes=200):
self.vnodes, self.points, self.owner = vnodes, [], {}
for n in nodes:
self.add(n)
def add(self, node):
for i in range(self.vnodes):
p = h(f"{node}#{i}")
bisect.insort(self.points, p)
self.owner[p] = node
def remove(self, node):
self.points = [p for p in self.points if self.owner[p] != node]
self.owner = {p: n for p, n in self.owner.items() if n != node}
def lookup(self, key):
i = bisect.bisect(self.points, h(key)) % len(self.points)
return self.owner[self.points[i]]
यहां एमडी५ का इस्तेमाल बंटवारे के लिए है, सुरक्षा के लिए नहीं। कोई भी तेज और अच्छी तरह मिलाने वाला हैश चलेगा; उत्पादन में अक्सर मरमर३ या एक्सएक्सहैश इस्तेमाल होता है।
वर्चुअल नोड: वे असल में क्या देते हैं
हर सर्वर का एक बिंदु होने पर चापों की लंबाई बहुत अलग-अलग होती है, इसलिए कुछ सर्वरों के पास रिंग का बहुत बड़ा हिस्सा होता है। वर्चुअल नोड कई छोटे चापों का औसत लेकर इसे ठीक करते हैं। वही प्रयोग, २ लाख कुंजियां १० सर्वरों पर:
| प्रति सर्वर वर्चुअल नोड | सबसे ज्यादा भार / औसत | सबसे कम भार / औसत |
|---|---|---|
| १ | २.३० गुना | ०.१२ गुना |
| १० | १.४६ गुना | ०.६९ गुना |
| २०० | १.११ गुना | ०.९२ गुना |
एक बिंदु वाली रिंग लगभग बेकार है: एक सर्वर अपने हिस्से के दोगुने से ज्यादा उठाता है जबकि दूसरा लगभग खाली बैठा रहता है। २०० वर्चुअल नोड पर फैलाव लगभग ±१०% रह जाता है।
वर्चुअल नोड के दो और फायदे हैं:
- भारित क्षमता। दोगुनी मेमोरी वाले सर्वर को दोगुने वर्चुअल नोड मिलते हैं।
- नरम विफलता। जब कोई सर्वर गिरता है, तो उसके कई छोटे चाप कई अलग उत्तराधिकारी ले लेते हैं, न कि कोई एक बदकिस्मत पड़ोसी उसका पूरा भार।
कीमत है रिंग के लिए मेमोरी और ज्यादा मेटाडेटा का आना-जाना। कसांड्रा का डिफॉल्ट लंबे समय तक प्रति नोड २५६ टोकन रहा; संस्करण ४.० ने बेहतर टोकन आवंटन एल्गोरिदम के साथ इसे घटाकर १६ कर दिया, क्योंकि बहुत ज्यादा संख्या से मरम्मत और डेटा धारा महंगी होती थी। ज्यादा मुफ्त नहीं है।
रिंग पर प्रतिकृतियां
डायनेमो जैसे सिस्टम प्रतिकृतियां चुनने के लिए भी रिंग इस्तेमाल करते हैं। प्रतिकृति कारक ३ के साथ कुंजी रखने के लिए कुंजी से घड़ी की दिशा में चलिए और पहले तीन अलग भौतिक सर्वर लीजिए, पहले से चुने सर्वर के अतिरिक्त वर्चुअल नोड छोड़ते हुए। चित्र का नोट के१ के लिए यही दिखाता है: मालिक बी है, फिर सी और ए प्रतिकृतियां रखते हैं।
उत्पादन में दो सुधार अहम हैं:
- रैक या जोन की समझ। "अलग सर्वर" का असली मतलब होना चाहिए "अलग विफलता क्षेत्र।" एक ही रैक में तीन प्रतिकृतियां बिजली जाने पर एक ही प्रतिकृति हैं।
- वरीयता सूचियां। उम्मीदवारों की क्रमबद्ध सूची (घड़ी की दिशा में पहले तीन स्वस्थ नोड) ही समन्वयक को किसी अस्थायी रूप से बंद प्रतिकृति के आसपास रास्ता बनाने देती है, और डायनेमो तथा कसांड्रा में ढीले कोरम और संकेतित सौंपने का तरीका यही है।
रिंग पर बना कैश क्लस्टर
- ऐप सर्वर और रिंग क्लाइंट। रिंग क्लाइंट लाइब्रेरी में रहती है (केटामा शैली के मेमकैश्ड क्लाइंट ऐसे ही काम करते हैं)। अनुरोध के रास्ते पर न प्रॉक्सी का चक्कर, न केंद्रीय खोज।
- ईटीसीडी (सदस्यता)। रिंग में कौन से नोड हैं और उनका भार क्या है, इसका सच्चा स्रोत। क्लाइंट इसे देखते रहते हैं और बदलने पर अपनी रिंग फिर से बनाते हैं। जूकीपर, कॉन्सल या गॉसिप प्रोटोकॉल भी यही भूमिका निभा सकते हैं।
- कैश नोड ए, बी, सी। सादे कुंजी-मान सर्वर। उन्हें रिंग के बारे में कुछ जानने की जरूरत नहीं।
- कैश नोड डी (जुड़ रहा)। पहले सदस्यता में "गर्म हो रहा" स्थिति में जोड़ा जाता है। क्लाइंट उसके चापों के लेखन उसे भेजने लगते हैं जबकि पुनर्संतुलक उसे भरता है।
- पुनर्संतुलक। कैश के लिए पुनर्संतुलन वैकल्पिक है: चूकें अपने आप भर जाती हैं। डेटाबेस, या ऐसी किसी भी स्थिति के लिए जिसे दोबारा नहीं बनाया जा सकता, पुनर्संतुलक मालिक बदलने वाले चाप भेजता है, रफ्तार सीमित रखकर ताकि असली ट्रैफिक भूखा न रहे।
हरा नोट ही पूरी बात है: सिर्फ लगभग १/एन कुंजियां खिसकती हैं।
कंसिस्टेंट हैशिंग क्या हल नहीं करती
- गर्म कुंजियां। अगर एक कुंजी को कुल ट्रैफिक का १०% मिलता है, तो वह फिर भी एक ही सर्वर पर रहती है। रिंग कुंजियां संतुलित करती है, अनुरोध नहीं। आपको गर्म कुंजियों की प्रतिकृति, अनुरोध एकीकरण या स्थानीय नजदीकी कैश चाहिए।
- रिंग के अलग-अलग नजरिए। अगर सदस्यता बदलते समय आधे क्लाइंट के पास नई रिंग है और आधे के पास पुरानी, तो एक ही कुंजी दो जगह से पढ़ी जाती है। कैश में इसका मतलब ज्यादा चूकें। डेटाबेस में इसका मतलब है कि आपको संस्करण वाला स्वामित्व (युग) और सौंपने का प्रोटोकॉल चाहिए।
- क्रमिक अतिभार। जब कोई नोड गिरता है, तो उसके उत्तराधिकारी उसका भार लेते हैं। अगर वे पहले से ८०% पर थे, तो वे भी गिर सकते हैं। "सीमित भार वाली कंसिस्टेंट हैशिंग" (मिरोकनी, थोरुप और जादीमोघद्दम) हर नोड का भार सीमित करती है और अतिरिक्त भार घड़ी की दिशा में अगले नोड पर भेजती है; वीमियो ने बताया कि उसने इसे अपने वीडियो वितरण के लोड बैलेंसिंग में अपनाया।
जानने लायक विकल्प
| तकनीक | कैसे काम करती है | ताकत | कमजोरी | कहां दिखती है |
|---|---|---|---|---|
| वर्चुअल नोड वाली हैश रिंग | गोले पर घड़ी की दिशा में अगला | मनचाहा नोड जोड़ना-हटाना, स्वाभाविक प्रतिकृति सूचियां | संतुलन के लिए वर्चुअल नोड चाहिए; रिंग का मेटाडेटा | डायनेमो, कसांड्रा, केटामा क्लाइंट, एनवॉय रिंग हैश |
| रेंडेवू (सबसे ऊंचा यादृच्छिक भार) | हर कुंजी के लिए हर नोड को hash(key, node) से अंक दो, सबसे ऊंचा चुनो |
रिंग नहीं, लगभग पूरा संतुलन, भारित प्रतिकृतियां आसान (ऊपर के के) | हर खोज O(N) |
लोड बैलेंसर और छोटे क्लस्टर |
| जंप कंसिस्टेंट हैश | एक अंकगणितीय छलांग फलन जो कुंजी को बाल्टी शून्य से एन-१ तक भेजता है | कोई मेमोरी नहीं, बहुत तेज, बढ़िया संतुलन | नोड सिर्फ क्रमांक के अंत में जोड़े या हटाए जा सकते हैं | क्रमांकित हिस्सों वाला बंटा स्टोरेज |
| मैगलेव हैशिंग | हर बैकएंड के क्रमचय से भरी पहले से बनी खोज तालिका | O(1) खोज, बहुत बराबर, न्यूनतम उथल-पुथल |
बदलाव पर तालिका फिर बनानी पड़ती है; लोड बैलेंसर के लिए बनी | गूगल मैगलेव, एनवॉय की मैगलेव नीति |
मेरा मोटा नियम: बैकएंड के छोटे समूह (दसियों) के लिए रेंडेवू, ऐसे स्टोरेज सिस्टम के लिए वर्चुअल नोड वाली रिंग जिन्हें प्रतिकृति सूचियां और मनचाहे सदस्यता बदलाव चाहिए, जंप हैश जब हिस्से क्रमांकित हों और सिर्फ बढ़ते हों, और परत-४ लोड बैलेंसर के लिए मैगलेव।
इंटरव्यू का क्रम
१. hash % N से शुरू करें और दिखाएं कि एन बदलने पर क्या होता है। ९०% वाली संख्या इस्तेमाल करें।
२. रिंग बनाएं और घड़ी की दिशा वाला स्वामित्व समझाएं।
३. दिखाएं कि नोड जोड़ने पर सिर्फ एक चाप खिसकता है।
४. हर नोड के एक बिंदु पर असंतुलन बताएं, फिर वर्चुअल नोड लाएं।
५. प्रतिकृति जोड़ें: अगले के अलग सर्वर, आदर्श रूप से अलग जोन में।
६. एक सीमा (गर्म कुंजियां) और एक विकल्प (रेंडेवू या जंप हैश) का जिक्र करें।
उत्पादन जांच सूची
- हैश फलन तेज और अच्छी तरह बंटा हुआ (मरमर३, एक्सएक्सहैश); जावा जैसा
hashCodeकभी नहीं - वर्चुअल नोड की संख्या चुनी और मापी गई (भार का फैलाव आपके लक्ष्य से कम)
- भार नोड की असली क्षमता बताते हैं
- सदस्यता का एक ही सच्चा स्रोत, जिसे क्लाइंट देखते रहते हैं
- रिंग के बदलाव संस्करण वाले, ताकि पुराने नजरिए पकड़े जा सकें
- प्रतिकृतियां अलग विफलता क्षेत्रों में
- पुनर्संतुलन धाराएं सीमित और दिखने वाली
- गर्म कुंजियों का इलाज रखने के तरीके से अलग मौजूद
- डैशबोर्ड पर हर नोड की कुंजी संख्या और अनुरोध दर, सिर्फ औसत नहीं
जो बचा रह गया
रिंग उन विचारों में से है जो देखते ही साफ लगते हैं और दशकों तक काम आते हैं। यह एक ही काम करती है: जब क्लस्टर बदलता है, तो दुनिया का ज्यादातर हिस्सा वहीं रहने देती है जहां वह था।
यह एक मामूली वादा है। यही फर्क भी है रात तीन बजे दबाव कम करने के लिए नोड जोड़ने में, और रात तीन बजे ऐसा नोड जोड़ने में जो साथ में डेटाबेस भी गिरा दे।
स्रोत
- कार्गर और साथी, कंसिस्टेंट हैशिंग और यादृच्छिक पेड़ (एसटीओसी १९९७)
- डीकैंडिया और साथी, डायनेमो: अमेजन का अत्यधिक उपलब्ध कुंजी-मान स्टोर (एसओएसपी २००७)
- लैम्पिंग और वीच, एक तेज, न्यूनतम मेमोरी वाला कंसिस्टेंट हैश एल्गोरिदम (जंप हैश, २०१४)
- आइजनबड और साथी, मैगलेव: एक तेज और भरोसेमंद सॉफ्टवेयर नेटवर्क लोड बैलेंसर (एनएसडीआई २०१६)
- मिरोकनी, थोरुप और जादीमोघद्दम, सीमित भार वाली कंसिस्टेंट हैशिंग
- एनवॉय: लोड बैलेंसर के प्रकार (रिंग हैश और मैगलेव)
- इसी श्रृंखला में: कुंजी-मान स्टोर डिजाइन करें, शून्य से लाखों उपयोगकर्ताओं तक