संक्षेप (टीएल;डीआर)
- समस्या:
put(key, value)औरget(key)के पीछे अरबों छोटे मान रखना, कई मशीनों पर, कुछ मशीनें गिरने पर भी लिखने लायक बने रहना, और कुछ ही मिलीसेकंड की अनुमानित देरी के साथ।- डिजाइन: कुंजियों को कंसिस्टेंट हैश रिंग पर बांटें, हर कुंजी को एन नोड पर दोहराएं, और ग्राहकों को हर अनुरोध पर डब्ल्यू और आर चुनने दें। विफलता के दौरान ढीले कोरम और संकेतित सौंपने से लेखन स्वीकार करें, पढ़ते समय मरम्मत और मर्कल पेड़ों से भटकाव ठीक करें, गॉसिप से विफलता पहचानें, और हर नोड पर डेटा एलएसएम पेड़ में रखें।
- नतीजा: ऐसा सिस्टम जो नियंत्रित और समायोज्य ढंग से थोड़ी संगति के बदले उपलब्धता देता है। यही अमेजन के डायनेमो शोध पत्र, कसांड्रा और रियाक के पीछे का डिजाइन है, और डायनेमोडीबी के पीछे की सोच।
कुंजी-मान स्टोर का एपीआई इस पूरी श्रृंखला में सबसे छोटा है: दो क्रियाएं। इसीलिए यह अच्छा इंटरव्यू सवाल है। पीछे छिपने को कुछ नहीं, तो हर फैसला वितरण के बारे में होता है: डेटा कहां रहता है, कितनी प्रतियां हैं, प्रति गायब हो तो क्या होता है, और जब दो मशीनें असहमत हों तो "मौजूदा मान" का मतलब क्या है।
यह लेख डायनेमो शैली का स्टोर बनाता है, क्योंकि वह डिजाइन इनमें से हर सवाल का खुलकर सामना करवाता है।
जरूरतें
- एपीआई:
put(key, value),get(key)और वैकल्पिक रूप सेdelete(key)। मान लगभग १ एमबी तक; ज्यादातर १० केबी से कम। - पैमाना: दसियों टेराबाइट, प्रति सेकंड लाखों के आसपास कार्य।
- पहले उपलब्धता: कुछ नोड या पूरा उपलब्धता क्षेत्र न मिले तब भी लेखन सफल हो। शॉपिंग कार्ट और सत्र स्टोर क्लासिक उदाहरण हैं: एक लेखन खोना थोड़ी देर पुराना मान पढ़ने से बुरा है।
- समायोज्य संगति: कुछ कॉल करने वालों को अपना लिखा तुरंत पढ़ना है; कुछ कम देरी के बदले थोड़ा पुराना मान खुशी से ले लेंगे।
- संचालन में आसानी: बिना रुकावट नोड जोड़ना और हटाना; डिस्क खोने पर अपने आप संभलना।
क्षमता का खाका: प्रतिकृति कारक ३ के साथ २० टीबी डेटा यानी डिस्क पर ६० टीबी। हर नोड पर लगभग २ टीबी, और कॉम्पैक्शन की गुंजाइश के लिए ६०% से कम भरे रखने पर, लगभग ५० नोड। अगर हर नोड आराम से १०,००० कार्य प्रति सेकंड संभाले, तो क्लस्टर किसी कैश के बिना लगभग ५ लाख कार्य प्रति सेकंड संभालता है।
सीएपी, सटीक रूप से
सीएपी प्रमेय कहता है कि नेटवर्क विभाजन के दौरान सिस्टम को संगति (हर पठन नवीनतम लेखन देखे) और उपलब्धता (जीवित नोड को भेजे हर अनुरोध को त्रुटि रहित जवाब मिले) में से चुनना पड़ता है। विभाजन न हो तो दोनों मिल सकते हैं।
पैसेल्क वह हिस्सा जोड़ता है जो लोग भूल जाते हैं: वरना, जब विभाजन नहीं है, तब भी आप देरी और संगति के बीच सौदा करते हैं, क्योंकि ज्यादा प्रतिकृतियों का इंतजार ज्यादा समय लेता है।
| सिस्टम का प्रकार | विभाजन के दौरान | सामान्य रूप से | उदाहरण |
|---|---|---|---|
| संगति प्रधान | अल्पमत वाले हिस्से पर अनुरोध ठुकराता है | संगत, ज्यादा देरी | ईटीसीडी, जूकीपर, स्पैनर |
| उपलब्धता प्रधान | हर जगह पढ़ना और लिखना स्वीकार करता रहता है | समायोज्य; अक्सर आखिरकार संगत | डायनेमो, कसांड्रा, रियाक |
यह लेख उपलब्धता प्रधान रूप बनाता है, ऐसे बटनों के साथ जिनसे कॉल करने वाले जरूरत पड़ने पर संगति की ओर जा सकें।
बंटवारा और प्रतिकृति
कुंजियां वर्चुअल नोड वाली कंसिस्टेंट हैश रिंग पर रखी जाती हैं (इस श्रृंखला का कंसिस्टेंट हैशिंग लेख देखें)। हर कुंजी की वरीयता सूची उसकी जगह से घड़ी की दिशा में पहले एन अलग भौतिक नोड हैं, जो उपलब्धता क्षेत्रों में फैले हों। एन = ३ पर हर कुंजी की तीन प्रतिकृतियां हैं, और किसी एक नोड या क्षेत्र के जाने पर कोई डेटा नहीं खोता।
कोई भी नोड किसी अनुरोध का समन्वयक बन सकता है। ग्राहक या तो किसी भी नोड को अनुरोध भेजते हैं (जो जरूरत हो तो आगे भेज देता है), या बंटवारा समझने वाला क्लाइंट इस्तेमाल करते हैं जो सीधे प्रतिकृति को भेजकर एक चक्कर बचाता है।
कोरम: वह बटन जिसकी सब बात करते हैं
हर अनुरोध पर समन्वयक काम को सभी एन प्रतिकृतियों को भेजता है और उनमें से कुछ का इंतजार करता है:
- डब्ल्यू = लेखन सफल होने से पहले कितनी प्रतिकृतियों को पुष्टि करनी है।
- आर = पठन लौटने से पहले कितनी प्रतिकृतियों को जवाब देना है।
अगर आर + डब्ल्यू > एन, तो हर पठन कोरम कम से कम एक प्रतिकृति पर हर लेखन कोरम से मिलता है, इसलिए पठन नवीनतम सफल लेखन की कम से कम एक प्रति देखेगा।
| एन, डब्ल्यू, आर | व्यवहार | कब इस्तेमाल करें |
|---|---|---|
| ३, १, १ | सबसे तेज, सबसे कमजोर; पठन हाल के लेखन आसानी से चूक सकते हैं | कैश जैसा डेटा, मेट्रिक्स |
| ३, २, २ | मिलते हुए कोरम; हर रास्ते पर एक धीमी या बंद प्रतिकृति सह लेता है | आम डिफॉल्ट |
| ३, ३, १ | तेज पठन; कोई भी प्रतिकृति बंद हो तो लेखन विफल | ज्यादा पढ़ा जाने वाला, कम बदलने वाला डेटा |
| ३, १, ३ | तेज लेखन, धीमे पठन | ज्यादा लिखे और कम पढ़े जाने वाले लॉग |
कोरम क्या नहीं देते। आर + डब्ल्यू > एन रेखीयता नहीं है। समवर्ती लेखन, "आखिरी लेखन जीतता है" वाली समय मुहरों और ढीले कोरम (नीचे) के साथ, पठन अब भी पुराना मान या बाद में बदला गया मान लौटा सकता है। मार्टिन क्लेपमैन की डिजाइनिंग डेटा-इंटेंसिव एप्लिकेशन्स इन किनारे वाले मामलों की सबसे साफ व्याख्या है। अगर आपको असली तुलना-और-बदलो चाहिए, तो आपको सहमति प्रोटोकॉल (पैक्सोस, राफ्ट) या शर्त वाला लेखन चाहिए, बड़ा कोरम नहीं।
जब एक प्रतिकृति बंद हो तो लेखन का रास्ता
- ग्राहक। अपने चुने संगति स्तर के साथ
put(k, v)भेजता है। - नोड ए (समन्वयक)। लेखन कुंजी की वरीयता सूची को भेजता है और डब्ल्यू प्रतिकृतियों की पुष्टि होते ही जवाब देता है। सबसे धीमी प्रतिकृति का इंतजार नहीं करता।
- नोड बी और सी (प्रतिकृति १ और २)। पुष्टि करते हैं। डब्ल्यू = २ पर ग्राहक को यहीं सफलता मिलती है।
- नोड डी (प्रतिकृति ३, बंद)। लेखन का समय खत्म होता है। सख्त कोरम में समन्वयक सिर्फ बी और सी गिनकर आगे बढ़ता।
- नोड ई (डी का संकेत रखता है)। ढीले कोरम में समन्वयक डी की प्रति रिंग पर अगले स्वस्थ नोड पर लिखता है, इस संकेत के साथ कि "यह डी का है।" इससे गड़बड़ी के दौरान भी टिकाऊपन तीन प्रतियों पर बना रहता है।
- बाद में दोबारा भेजना। जब गॉसिप बताता है कि डी लौट आया, तो ई संकेत वाले लेखन डी को भेजकर मिटा देता है। यही संकेतित सौंपना है।
- गॉसिप। हर नोड हर सेकंड कुछ बेतरतीब साथियों से सदस्यता और धड़कन की स्थिति बदलता है। कसांड्रा इसके ऊपर फाई संचयी विफलता पहचान इस्तेमाल करता है, जो जीवित या मृत के बजाय शक का स्तर बताता है, ताकि धीमा नेटवर्क नोड को तुरंत मृत न घोषित करे।
हरा नोट मेल का नियम बताता है। ढीले कोरम की कीमत यह है कि कुछ समय तक पुष्टि करने वाले "डब्ल्यू नोड" कुंजी के असली घर वाले नोड नहीं होते, और यही एक वजह है कि अकेले कोरम मजबूत संगति की गारंटी नहीं देते।
जब प्रतिकृतियां असहमत हों
प्रतिकृतियां भटकती हैं: कोई नोड संकेत की समय सीमा से लंबी गड़बड़ी में लेखन चूक जाता है, डिस्क बदली जाती है, नेटवर्क लड़खड़ाता है। तीन तंत्र उन्हें वापस मिलाते हैं:
१. पढ़ते समय मरम्मत। जब आर > १ वाला पठन अलग संस्करण देखता है, तो समन्वयक सबसे नया लौटाता है और पुरानी प्रतिकृतियों पर उसे दोबारा लिखता है।
२. मर्कल पेड़ों से असंगति हटाना। हर नोड अपनी कुंजी सीमाओं पर हैश का पेड़ बनाता है। दो प्रतिकृतियां जड़ के हैश मिलाती हैं और सिर्फ उन उप-पेड़ों में उतरती हैं जो अलग हैं, इसलिए वे बहुत कम डेटा बदलकर अरबों में से गिनी-चुनी अलग कुंजियां ढूंढ लेती हैं। कसांड्रा इसे nodetool repair के रूप में चलाता है।
३. संकेतित सौंपना, जो ऊपर बताया, छोटी गड़बड़ियों के लिए।
कौन सा संस्करण जीतता है? आपको एक नियम चाहिए:
| रणनीति | कैसे काम करती है | कीमत |
|---|---|---|
| आखिरी लेखन जीतता है | सबसे ऊंची समय मुहर जीतती है | सरल, लेकिन समवर्ती लेखन चुपचाप डेटा खोते हैं; घड़ी मिलान पर निर्भर |
| वेक्टर घड़ियां | हर संस्करण के साथ हर नोड के काउंटर; समवर्ती संस्करण भाई-बहन की तरह रखे जाते हैं | चुपचाप नुकसान नहीं, लेकिन एप्लिकेशन को भाई-बहन मिलाने होते हैं (डायनेमो का शॉपिंग कार्ट यही करता था) |
| सीआरडीटी | ऐसे डेटा प्रकार जिनका मेल बनावट से ही बिना टकराव का है (काउंटर, समुच्चय, नक्शे) | जहां फिट हों वहां सुंदर; हर डेटा प्रकार का स्वाभाविक सीआरडीटी नहीं होता |
कसांड्रा हर कॉलम पर "आखिरी लेखन जीतता है" इस्तेमाल करता है। मूल डायनेमो वेक्टर घड़ियां इस्तेमाल करता था और मिलाने का काम एप्लिकेशन पर छोड़ता था। डायनेमोडीबी शर्त वाले लेखन देता है ताकि एप्लिकेशन टकराव हल करने के बजाय उनसे बच सकें।
मिटाना भी लेखन है। मिटाने पर एक समाधि पत्थर लिखा जाता है, एक निशान जो कहता है "यह कुंजी समय टी पर मिटाई गई।" समाधि पत्थरों को किसी प्रतिकृति की सबसे लंबी संभव गड़बड़ी से ज्यादा जीना चाहिए, वरना मिटाना चूकने वाली प्रतिकृति मरम्मत के दौरान मान को फिर जिंदा कर देगी। कसांड्रा का gc_grace_seconds (डिफॉल्ट रूप से १० दिन) ठीक इसी के लिए है।
एक नोड के भीतर: एलएसएम स्टोरेज इंजन
ज्यादातर डायनेमो शैली के स्टोर लॉग-संरचित मर्ज पेड़ (एलएसएम) इस्तेमाल करते हैं, जो लेवलडीबी, रॉक्सडीबी और कसांड्रा के स्टोरेज इंजन के पीछे का डिजाइन है।
लेखन का रास्ता
१. लेखन को कमिट लॉग में जोड़ें और डिस्क पर पक्का करें (या समूह में), ताकि वह क्रैश के बाद भी बचे। २. उसे मेमटेबल में डालें, जो मेमोरी में एक क्रमबद्ध ढांचा है। ३. मेमटेबल भरने पर उसे डिस्क पर एसएसटेबल के रूप में उतारें, जो एक अपरिवर्तनीय क्रमबद्ध फाइल है। लेखन कभी फाइल को उसी जगह नहीं बदलते, इसलिए वे क्रमिक और तेज होते हैं।
पठन का रास्ता
१. मेमटेबल देखें। २. हर एसएसटेबल के ब्लूम फिल्टर से पूछें, जो एक छोटा संभाव्यता वाला ढांचा है और जवाब देता है "पक्का यहां नहीं" या "शायद यहां।" सही आकार का ब्लूम फिल्टर उन ज्यादातर फाइलों को छोड़ देता है जिनमें कुंजी नहीं है। ३. सिर्फ उन एसएसटेबल को पढ़ें जिनमें कुंजी हो सकती है, सबसे नई पहले।
कॉम्पैक्शन पृष्ठभूमि में चलता है, एसएसटेबल मिलाता है और बदले जा चुके मान तथा समय पूरा कर चुके समाधि पत्थर हटाता है। आकार आधारित कॉम्पैक्शन लेखन क्षमता को तरजीह देता है; स्तर आधारित कॉम्पैक्शन पठन देरी और जगह को, ज्यादा लेखन प्रवर्धन की कीमत पर।
| एलएसएम पेड़ | बी-ट्री | |
|---|---|---|
| लेखन | क्रमिक, तेज | पेज उसी जगह बदलना, बेतरतीब आईओ |
| पठन | कई फाइलें छू सकता है; ब्लूम फिल्टर मदद करते हैं | पेड़ में एक बार चलना |
| जगह | कॉम्पैक्शन तक अस्थायी दोहराव | समय के साथ बिखराव |
| आम इंजन | रॉक्सडीबी, लेवलडीबी, कसांड्रा | इनोडीबी, पोस्टग्रेस, बोल्टडीबी |
सुनाने लायक विफलता की कहानियां
| घटना | सिस्टम क्या करता है |
|---|---|
| एक नोड ५ मिनट के लिए बंद | ढीले कोरम वाले लेखन संकेतों के साथ अगले नोड पर जाते हैं; लौटने पर संकेतित सौंपना उन्हें दोबारा भेजता है |
| एक नोड की डिस्क हमेशा के लिए खराब | नोड बदलें; उसकी सीमाएं बाकी प्रतिकृतियों से भेजी जाएं; मर्कल मरम्मत जांचती है |
| एक उपलब्धता क्षेत्र कट जाए | क्षेत्रों में फैली प्रतिकृतियों और डब्ल्यू = २ के साथ बहुमत वाले हिस्से पर लेखन चलते रहते हैं; अल्पमत हिस्सा ढीले कोरम से लेखन ले सकता है, जिन्हें बाद में मिलाया जाता है |
| एक नोड पर घड़ी का अंतर | आखिरी लेखन जीतता है वाले नियम में उसके लेखन गलत तरीके से जीत या हार सकते हैं। घड़ी का अंतर देखें और चेतावनी दें |
| एक गर्म कुंजी | उस कुंजी की प्रतिकृतियों पर अतिभार; बंटवारा इसे ठीक नहीं कर सकता। उसे कैश करें या कुंजी दोबारा डिजाइन करें |
बटनों की झटपट सूची
| बटन | आम मान | किसके लिए बढ़ाएं | किसके लिए घटाएं |
|---|---|---|---|
| प्रतिकृति कारक एन | ३ | टिकाऊपन, पठन क्षमता | स्टोरेज खर्च |
| लेखन कोरम डब्ल्यू | २ | पुष्टि पर टिकाऊपन | लेखन देरी, उपलब्धता |
| पठन कोरम आर | २ | ताजा पठन | पठन देरी |
| संकेत की समय सीमा | ३ घंटे | लंबी गड़बड़ियां सौंपने से ढकना | संकेतों पर लगी डिस्क |
| समाधि पत्थर की मोहलत | १० दिन | दोबारा जिंदा होने से सुरक्षा | समाधि पत्थरों की जगह और पठन खर्च |
उत्पादन जांच सूची
- प्रतिकृतियां सिर्फ नोड में नहीं, उपलब्धता क्षेत्रों में फैली हैं
- हर तालिका का डिफॉल्ट संगति स्तर चुना और कॉल करने वालों के लिए लिखा गया
- टकराव की रणनीति साफ (निगरानी वाली घड़ियों के साथ आखिरी लेखन, वेक्टर घड़ियां या सीआरडीटी)
- संकेतित सौंपने की समय सीमा और मरम्मत का कार्यक्रम समाधि पत्थर की मोहलत से मेल खाते हैं
- नियमित असंगति हटाने वाली मरम्मत चल रही है और उस पर नजर है
- ब्लूम फिल्टर की गलत सकारात्मक दर और हर पठन पर एसएसटेबल की संख्या पर नजर
- हर काम के हिसाब से कॉम्पैक्शन रणनीति; गुंजाइश के लिए डिस्क लगभग ६०% से कम
- डैशबोर्ड: हर काम और संगति स्तर का पी९९, बाकी संकेत, मरम्मत की प्रगति, छोड़े गए बदलाव
जो बचा रह गया
कुंजी-मान स्टोर वह जगह है जहां वितरित सिस्टम अमूर्त नहीं रहते। दो क्रियाएं, और फिर भी हर कठिन सवाल आ खड़ा होता है: कौन सी प्रति असली है, कितना इंतजार करें, उस नोड का क्या करें जो एक घंटा गायब रहा और अतीत के बारे में अपनी राय रखता है।
सबसे अच्छे डिजाइन यह दिखावा नहीं करते कि इन सवालों का एक ही जवाब है। वे कॉल करने वाले को एक बटन देते हैं और बहुत साफ लिखते हैं कि हर सेटिंग क्या वादा करती है और क्या नहीं।
स्रोत
- डीकैंडिया और साथी, डायनेमो: अमेजन का अत्यधिक उपलब्ध कुंजी-मान स्टोर (एसओएसपी २००७)
- लक्ष्मण और मलिक, कसांड्रा: एक विकेंद्रीकृत संरचित स्टोरेज सिस्टम
- ओ'नील और साथी, लॉग-संरचित मर्ज पेड़ (१९९६)
- अपाचे कसांड्रा दस्तावेज: संकेत, मरम्मत और कॉम्पैक्शन
- अबादी, आधुनिक वितरित डेटाबेस डिजाइन में संगति के सौदे (पैसेल्क)
- हयाशिबारा और साथी, फाई संचयी विफलता पहचान
- इसी श्रृंखला में: कंसिस्टेंट हैशिंग डिजाइन करें, अद्वितीय आईडी जनरेटर डिजाइन करें