इस लेख में, हम श्रृंखला प्रतिकृति का उपयोग करते हुए सरल और कुशल KV- स्टोरेज की वास्तुकला पर विचार करेंगे, जिसकी सक्रिय रूप से जांच की जाती है और विभिन्न प्रणालियों में इसका सफलतापूर्वक उपयोग किया जाता है।

यह एक श्रृंखला प्रतिकृति लेख की पहली छमाही है। दूसरा भाग यहाँ है । पहले थोड़ा सिद्धांत होगा, फिर विभिन्न संशोधनों के साथ उपयोग के कुछ उदाहरण।

1. लक्ष्य प्राथमिक / बैकअप प्रोटोकॉल के साथ समस्या और तुलना का बयान है।
2. चेन प्रतिकृति एक मूल दृष्टिकोण है।
3. चेन प्रतिकृति - वितरित अनुरोध।
4. FAWN: विम्पी नोड्स का एक फास्ट ऐरे।

1. परिचय

१.१ प्रयोजन

मान लीजिए हम एक साधारण कुंजी-मूल्य स्टोर डिज़ाइन करना चाहते हैं। रिपॉजिटरी में बहुत न्यूनतम इंटरफ़ेस होगा:

1. लिखना (कुंजी, वस्तु): कुंजी द्वारा सेव / अपडेट वैल्यू वैल्यू।
2. पढ़ा (कुंजी): कुंजी द्वारा संग्रहीत मान लौटाएं।

हम यह भी जानते हैं कि डेटा का आकार अपेक्षाकृत छोटा होता है (सब कुछ एक सर्वर पर फिट होता है, इसमें तेज करने की कोई आवश्यकता नहीं है), लेकिन बहुत अधिक लिखने / पढ़ने के अनुरोध हो सकते हैं।

हमारा लक्ष्य बड़ी संख्या में अनुरोधों का सामना करना है ( उच्च थ्रूपुट, एचटी ), उच्च उपलब्धता ( एचए ) और सख्त स्थिरता ( एससी ) है।

कई प्रणालियों में, SC को HA + HT के लिए बलिदान किया जाता है, क्योंकि सभी तीन गुणों को पूरा करना एक गैर-तुच्छ कार्य है। अमेज़ॅन डायनामो एक बड़ी छलांग थी और कई डायनमो-शैली डेटाबेस, जैसे कि कैसंड्रा, रीक, वोल्डेमॉर्ट, आदि को जन्म दिया।

1.2 प्राथमिक / बैकअप

ऐसी भंडारण प्रणाली के निर्माण के लिए सबसे आम और सरल दृष्टिकोण प्राथमिक / बैकअप प्रतिकृति का उपयोग करना है।
हमारे पास 1 प्राथमिक सर्वर, कई बैकअप सर्वर, लिखने / पढ़ने के संचालन केवल प्राथमिक सर्वर के माध्यम से चलते हैं।


यहां, चित्र संभावित इंटरेक्शन प्रोटोकॉल में से एक दिखाता है (क्लाइंट को भेजने से पहले सभी बैकअप से ack के लिए प्राथमिक प्रतीक्षा करता है), उदाहरण के लिए अन्य विकल्प (पारस्परिक रूप से अनन्य नहीं) हैं:

• प्राथमिक सख्ती से अनुरोध लिखने का आयोजन करता है।
• जैसे ही बैकअप में से एक ack के साथ आता है, प्राथमिक प्राथमिक भेज देता है।
• मैला कोरम और संकेतित हाथ।
• आदि

एक अलग प्रक्रिया की भी आवश्यकता होती है जो क्लस्टर की स्थिति पर नज़र रखता है (प्रतिभागियों को कॉन्फ़िगरेशन वितरित करता है) और, जब होस्ट सर्वर क्रैश हो जाता है, तो एक नए का चुनाव करता है (आरंभ करता है), और यह भी निर्धारित करता है कि विभाजित मस्तिष्क के मामले में क्या करना है। फिर से, आवश्यकताओं के आधार पर, इस तर्क के हिस्से को प्रतिकृति एल्गोरिदम के भाग के रूप में, तीसरे पक्ष के आवेदन के रूप में (उदाहरण के लिए, कॉन्फ़िगरेशन को संग्रहीत करने के लिए एक ज़ूकीर), आदि के रूप में निष्पादित किया जा सकता है।

जाहिर है, जल्दी या बाद में, प्राथमिक / बैकअप प्रतिकृति का प्रदर्शन दो बाधाओं से सीमित होगा:

• प्राथमिक सर्वर प्रदर्शन।
• बैकअप सर्वरों की संख्या।

अधिक विश्वसनीयता / संगतता आवश्यकताओं को एक क्लस्टर में प्रस्तुत किया जाता है, जितनी तेज़ी से यह क्षण आएगा।

क्या हमारे लक्ष्य को प्राप्त करने के अन्य तरीके हैं?

1.3 चेन प्रतिकृति

सामान्य तौर पर, चेन प्रतिकृति में सर्वर का एक अनुक्रम (श्रृंखला) होता है, जिसमें विशेष भूमिकाएं होती हैं HEAD (सर्वर क्लाइंट के साथ संवाद करता है) और पूंछ (श्रृंखला का अंत, एससी गारंटी)। एक श्रृंखला में कम से कम निम्नलिखित गुण होते हैं:

1. N - 1 सर्वर पर ड्रापस्टैंड ड्रॉप हो जाता है।
2. लिखने की गति SC प्राथमिक / बैकअप की गति से काफी भिन्न नहीं है।
3. HEAD क्रैश होने की स्थिति में क्लस्टर की रीकॉन्फ़िगरेशन प्राथमिक की तुलना में बहुत तेज़ होती है, बाकी सर्वर प्राथमिक / बैकअप की तुलना में तुलनात्मक रूप से या तेज़ी से होते हैं।

एक छोटा लेकिन महत्वपूर्ण बिंदु - सर्वरों के बीच एक विश्वसनीय फीफो कनेक्शन की आवश्यकता है ।

आइए हम श्रृंखला प्रतिकृति के निर्माण के विभिन्न तरीकों को और विस्तार से देखें।

2. मूल दृष्टिकोण

2.1 संचालन एल्गोरिथ्म

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

२.२ प्रतिकृति प्रोटोकॉल

हम सर्वर से सिर से पूंछ तक, फिर प्रत्येक नोड पर $$$मैं$ हम इसके अतिरिक्त स्टोर करेंगे:

• $$$Pending_i$ - नोड द्वारा प्राप्त अनुरोधों की एक सूची जो अभी तक पूंछ द्वारा संसाधित नहीं की गई है।
• $$$सेंट_आई$ - सर्वर द्वारा इसके उत्तराधिकारी को भेजे गए अनुरोधों की एक सूची जो अभी तक पूंछ द्वारा संसाधित नहीं की गई है।
• $$$History_i (कुंजी)$ - प्रमुख मूल्य में परिवर्तन का इतिहास (आप इतिहास और कुल मूल्य दोनों को संग्रहीत कर सकते हैं)। ध्यान दें:

  $$

  $$History_j (कुंजी) \ subseteq History_i (कुंजी), \ forall j> i$$
  
  
• और यह भी:

  $$

  $$Sent_i \ subseteq Pending_i \\ History_i (कुंजी) = History_ {i + 1} (कुंजी) \ cup Sent_i$$
  
  

2.3 सर्वर विफलता

जैसा कि परिचय में बताया गया है, हमें किसी प्रकार की मास्टर प्रक्रिया की आवश्यकता है:

• एक विफल सर्वर की पहचान करता है।
• सर्किट में परिवर्तन के अपने पूर्ववर्ती और उत्तराधिकारी को सूचित करता है।
• यदि सर्वर टेल या हेड है, तो यह उनके परिवर्तन के क्लाइंट को सूचित करता है।

हम मानते हैं कि मास्टर प्रक्रिया स्थिर है और कभी क्रैश नहीं होती है। इस तरह की प्रक्रिया का चुनाव इस लेख के दायरे से परे है।

दूसरी बहुत महत्वपूर्ण धारणा यह है कि हम मानते हैं कि सर्वर फेल-स्टॉप हैं:

• किसी भी (आंतरिक) विफलता की स्थिति में, सर्वर काम करना बंद कर देता है, और गलत परिणाम नहीं देता है।
• सर्वर की विफलता हमेशा मास्टर प्रक्रिया द्वारा निर्धारित की जाती है।

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

अंत में, तीन संभावित विफलता परिदृश्यों पर विचार करें:

2.3.1 प्रमुख गिरावट
बस श्रृंखला से सर्वर को हटा दें और अगले नए सिर को असाइन करें। केवल उन अनुरोधों का नुकसान $$$लंबित {{सिर}$ इसे आगे नहीं भेजा गया - $$$पेंडिंग_ {हेड} \ सेटमिनस सेंट_ {हेड}$

२.३.२ पतित पावनी
हम श्रृंखला से सर्वर को हटाते हैं और इससे पहले पिछले एक को नई पूंछ पर असाइन करते हैं $$$सेंट_ {पूंछ - 1}$ मंजूरी दे दी (इन सभी कार्यों को क्रमशः संसाधित पूंछ के रूप में चिह्नित किया गया है) $$$Pending_ {पूँछ - 1}$ घट जाती है।

2.3.3 गिरता हुआ मध्यवर्ती नोड $$$k$
विज़ार्ड नोड्स को सूचित करता है $$$k-1$ और $$$k + 1$ एक श्रृंखला में पुन: व्यवस्थित करने के बारे में।
संभावित नुकसान $$$Sent_ {k-1}$ अगर नोड $$$k$ मैंने उन्हें अपने उत्तराधिकारी के पास भेजने का प्रबंधन नहीं किया, इसलिए, नोड को हटाने के बाद $$$k$ श्रृंखला से पहली चीज को फिर से भेजा जाता है $$$सेंट_ {के - 1}$ और उस गाँठ के बाद ही $$$k - 1$ नए अनुरोधों को संसाधित करना जारी रखता है।

2.4 बैकअप / प्राथमिक प्रोटोकॉल के साथ तुलना

• श्रृंखला प्रतिकृति में, केवल एक सर्वर (पूंछ) रीड अनुरोधों के निष्पादन में शामिल है, और यह तुरंत एक उत्तर देता है, जबकि पी / बी प्राथमिक में यह लिखित अनुरोधों के पूरा होने की पुष्टि के लिए इंतजार कर सकता है।
• दोनों दृष्टिकोणों में, सभी सर्वरों पर लिखने का अनुरोध निष्पादित किया जाता है, पी / बी समानांतर निष्पादन के कारण इसे तेजी से करता है।

विफलता श्रृंखला प्रतिकृति देरी:

• सिर: रीडिंग अनुरोध बाधित नहीं होते हैं, लिखने के अनुरोध में 2 संदेशों में देरी होती है - मास्टर से सभी सर्वरों के बारे में नए सिर के बारे में और सभी ग्राहकों के लिए नए सिर के बारे में।
• इंटरमीडिएट सर्वर: पठित अनुरोध बाधित नहीं होते हैं। रनटाइम में रिकॉर्डिंग अनुरोधों में देरी हो सकती है $$$सेंट_आई$ कोई अद्यतन नुकसान नहीं हैं।
• पूंछ: दो संदेशों के लिए पढ़ने और लिखने का विलंब - अधिसूचना $$$पूंछ - 1$ नई पूंछ के बारे में और नई पूंछ के बारे में ग्राहकों को सचेत करना।

विफलता P / B विलंब:

• प्राथमिक: एक नया प्राथमिक का चयन करने और राज्य को सिंक्रनाइज़ करने के लिए 5 संदेश देरी।
• बैकअप: यदि कोई लिखित अनुरोध नहीं हैं, तो कोई विलंब नहीं है। जब रिकॉर्डिंग अनुरोध दिखाई देता है, तो 1 संदेश का विलंब संभव है।

जैसा कि आप देख सकते हैं, चेन प्रतिकृति के लिए सबसे खराब पूंछ विफलता पी / बी (प्राथमिक) के लिए सबसे खराब एक से तेज है।

इस दृष्टिकोण के लेखकों ने भार परीक्षण किया, जिसमें पी / बी प्रोटोकॉल के साथ तुलनीय प्रदर्शन दिखाया गया।

3. वितरित क्वेरी (अनुप्रयुक्त क्वेरी के साथ श्रृंखला प्रतिकृति - CRAQ)

मूल दृष्टिकोण में एक स्पष्ट कमजोरी है - पूंछ, जो सभी पढ़े गए अनुरोधों को संभालती है। इससे दो समस्याएं हो सकती हैं:

• पूंछ हॉटस्पॉट बन जाती है, अर्थात एक सर्वर जो किसी भी अन्य नोड की तुलना में कहीं अधिक अनुरोधों को संभालता है।
• कई डेटा केंद्रों में एक श्रृंखला रखते समय, पूंछ बहुत दूर हो सकती है, जो लेखन अनुरोधों को धीमा कर देगी।

CRAQ का विचार काफी सरल है - रीड रिक्वेस्ट को टेल के अलावा सभी सर्वरों पर आते हैं, और स्थिरता सुनिश्चित करने के लिए, हम ऑब्जेक्ट वर्जन वेक्टर को लिखने के अनुरोधों के लिए स्टोर करेंगे, और अस्पष्टता के मामले में, नोड्स नवीनतम फिक्स्ड वर्जन प्राप्त करने के लिए टेल करने के लिए एक अनुरोध करेंगे।

3.1 CRAQ

हम CRAQ वास्तुकला को औपचारिक बनाते हैं:
प्रत्येक नोड, पूंछ को छोड़कर, प्रक्रियाएं अनुरोधों को पढ़ती हैं और एक प्रतिक्रिया देती हैं, और सिर लिखित अनुरोधों (मूल दृष्टिकोण के साथ तुलना) से प्रतिक्रिया देता है।


प्रत्येक गैर-टेल नोड पर एक ही ऑब्जेक्ट के कई संस्करण संग्रहीत किए जा सकते हैं, और संस्करण एक सख्ती से नीरसता से बढ़ते अनुक्रम बनाते हैं। प्रत्येक संस्करण के लिए, एक अतिरिक्त विशेषता "क्लीन" या "डर्टी" जोड़ी जाती है। प्रारंभ में, सभी संस्करण साफ हैं।

जैसे ही नोड को एक लिखित अनुरोध प्राप्त होता है, यह प्राप्त संस्करण को संस्करणों की सूची में जोड़ता है, और फिर:

• यदि नोड पूंछ है, तो यह संस्करण को स्वच्छ के रूप में चिह्नित करता है, इस समय संस्करण को निश्चित माना जाता है, और श्रृंखला के नीचे एक पुष्टिकरण भेजता है।
• अन्यथा, यह संस्करण को गंदे के रूप में चिह्नित करता है और श्रृंखला के नीचे अनुरोध को भेजता है।

जैसे ही नोड उत्तराधिकारी से पुष्टि प्राप्त करता है, यह संस्करण को साफ करता है और सभी पिछले संस्करणों को हटा देता है।

जैसे ही नोड को एक पढ़ने का अनुरोध प्राप्त होता है:

• यदि नोड के लिए ज्ञात ऑब्जेक्ट का अंतिम संस्करण साफ है, तो वह इसे वापस कर देता है।
• अन्यथा, वह ऑब्जेक्ट के नवीनतम निश्चित संस्करण को प्राप्त करने के लिए पूंछ करने का अनुरोध करता है, जिसे वह क्लाइंट को लौटाता है। (निर्माण से, ऐसा संस्करण हमेशा नोड पर होगा)।

रीड अनुरोधों की प्रबलता वाले अनुप्रयोगों के लिए, CRAQ प्रदर्शन नोड्स के विकास के साथ रैखिक रूप से बढ़ता है , लेखन अनुरोधों की प्रबलता के मामले में, प्रदर्शन मूल दृष्टिकोण की तुलना में खराब नहीं होगा।

CRAQ दोनों को एक या कई डेटा केंद्रों में स्थित किया जा सकता है। यह ग्राहकों को पढ़ने के अनुरोध की गति बढ़ाने के लिए निकटतम नोड्स का चयन करने में सक्षम बनाता है।

3.2 CRAQ में निरंतरता

CRAQ एक मामले को छोड़कर, मजबूत स्थिरता प्रदान करता है: जब नोड पूंछ से नवीनतम प्रतिबद्ध संस्करण प्राप्त करता है, तो नोड क्लाइंट के प्रति प्रतिक्रिया करने से पहले नया संस्करण प्रतिबद्ध कर सकता है। इस स्थिति में, CRAQ नीरस रीडिंग प्रदान करता है (क्रमिक रीड रिक्वेस्ट अतीत की बात नहीं होगी, लेकिन पुराने डेटा को वापस लौटा सकती है)।

कमजोर संगति भी संभव है:

• अंतिम संगति: नोड पूंछ से नवीनतम प्रतिबद्ध संस्करण का अनुरोध नहीं करेगा। यह पूरी श्रृंखला पर नीरस पढ़ने को बाधित करेगा, लेकिन नीरस रीडिंग को उसी नोड पर रखें । इसके अलावा, यह नेटवर्क विभाजन सहिष्णुता का सामना कर सकता है ।
• बंधी हुई अंतिम संगति: एक निश्चित बिंदु तक केवल एक गंदा संस्करण लौटाएं। उदाहरण के लिए, गंदे और साफ संस्करणों के बीच का अंतर एन संशोधनों से अधिक नहीं होना चाहिए। या एक समय सीमा।

3.3 सर्वर विफलता

मूल दृष्टिकोण के समान।

३.४ वैकल्पिक

CRAQ में एक दिलचस्प विशेषता है - आप रिकॉर्डिंग ऑपरेशन के दौरान मल्टीकास्ट का उपयोग कर सकते हैं। मान लीजिए कि सिर एक मल्टीकास्ट के साथ परिवर्तन भेजता है और इस घटना के लिए केवल कुछ पहचानकर्ता को श्रृंखला भेजता है। यदि अद्यतन स्वयं नोड पर नहीं आया है, तो यह प्रतीक्षा कर सकता है और इसे अगले नोड से प्राप्त कर सकता है जब टेल परिवर्तन की पुष्टि संदेश भेजता है। इसी तरह, पूंछ मल्टीकास्ट के साथ निर्धारण की पुष्टि भेज सकती है।

4. फेन: विम्पी नोड्स का एक तेज एरे

एक बहुत ही रोचक अध्ययन, इस लेख के विषय से सीधे संबंधित नहीं है, लेकिन श्रृंखला प्रतिकृति के उपयोग के उदाहरण के रूप में कार्य करता है।

उच्च-प्रदर्शन की-वैल्यू स्टोरेज (डायनमो, मेमकेड, वोल्डेमॉर्ट) की सामान्य विशेषताएं हैं - उन्हें I / O की आवश्यकता होती है, न्यूनतम कंप्यूटिंग, बड़ी मात्रा में यादृच्छिक कुंजी के समानांतर स्वतंत्र पहुंच, और 1Kb तक के छोटे प्रमुख मूल्य।

लंबे समय के संचालन (यादृच्छिक अभिगम समय) के कारण HDD वाले सर्वर ऐसे समूहों के लिए उपयुक्त नहीं हैं, और बड़ी संख्या में DRAM वाले सर्वर आश्चर्यजनक रूप से बड़ी मात्रा में बिजली की खपत करते हैं - 2GB DRAM 1Tb HDD के बराबर है।

न्यूनतम बिजली की खपत के साथ एक प्रभावी (बैंडविड्थ) क्लस्टर का निर्माण मूल अध्ययन का लक्ष्य है। तीन वर्षों में सर्वर की लागत का 50% बिजली की लागत है, और आधुनिक ऊर्जा-बचत मोड उतने प्रभावी नहीं हैं जितना कि वे विज्ञापित हैं - 20% लोड पर परीक्षणों में, सीपीयू की खपत 50% पर बनी हुई है, साथ ही अन्य सर्वर घटकों में ऊर्जा-बचत मोड नहीं हैं; DRAM, उदाहरण के लिए, पहले से ही एक न्यूनतम पर काम करता है)। यह ध्यान रखना महत्वपूर्ण है कि ऐसे समूहों में सीपीयू और आई / ओ वाइडेंस के बीच की खाई - एक शक्तिशाली सीपीयू I / O ऑपरेशन को पूरा करने के लिए इंतजार करने के लिए मजबूर है।

4.1 वास्तुकला

FAWN क्लस्टर $ 250 (2009 की कीमतों) के लिए पुराने सर्वरों पर बनाया गया है, जिसमें एकीकृत 500MHz CPU, 512Mb RAM, 32Gb SSD है। यदि आप अमेज़ॅन डायनामो वास्तुकला या सुसंगत हैशिंग से परिचित हैं, तो आप एफएडब्ल्यूएन वास्तुकला से परिचित होंगे:

1. प्रत्येक भौतिक सर्वर में कई वर्चुअल नोड्स होते हैं, प्रत्येक का अपना VID होता है।
2. VID एक रिंग बनाते हैं, प्रत्येक VID "स्वयं के पीछे" सीमा के लिए जिम्मेदार है (उदाहरण के लिए, A1 रेंज R1 में कुंजियों के लिए ज़िम्मेदार है)।
3. विश्वसनीयता बढ़ाने के लिए, डेटा को निम्न नोड्स के दक्षिणावर्त आर के लिए दोहराया जाता है। (उदाहरण के लिए, R = 2 के साथ, A1 पर कुंजी B1 और C1 के लिए प्रतिकृति है), इसलिए हमें चेन प्रतिकृति (मूल दृष्टिकोण) मिलता है।
4. अनुरोध पढ़ें पूंछ श्रृंखला पर जाएं, अर्थात A1 से कुंजी पढ़ना C1 पर जाएगा।
5. अनुरोध लिखें कि हेड चेन पर जाएं और अंत तक जाएं।

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

4.2 परीक्षा परिणाम

लोड परीक्षण में, FAWN एक यादृच्छिक रीड फ्लैश ड्राइव पर QPS के 90% QPS (प्रति सेकंड) तक पहुंचता है।

निम्न तालिका विभिन्न विन्यासों के स्वामित्व की कुल लागत (TCO) की तुलना करती है, जहां पारंपरिक के लिए आधार 200W खपत (2009 की कीमतों) के साथ $ 1000 सर्वर है:

इस प्रकार, यदि:

• बड़ा डेटा, कुछ क्वेरीज़: FAWN + 2Tb 7200 RPM
• डेटा की एक छोटी राशि, बहुत सारे अनुरोध: FAWN + 2GB DRAM
• औसत मूल्य: FAWN + 32GB SSD

संदर्भ

• उच्च throughput और उपलब्धता का समर्थन करने के लिए चेन प्रतिकृति
• CRAQ पर ऑब्जेक्ट स्टोरेज: रीड-ज्यादातर वर्कलोड के लिए उच्च-थ्रूपुट श्रृंखला प्रतिकृति
• FAWN: ए फास्ट अरेंज ऑफ विम्पी नोड्स