टीएल;डीआर

  • समस्या: बड़े पैमाने की वास्तुकला (आर्किटेक्चर) तैयार करने के लिए उपलब्धता, थ्रूपुट और परिचालन जटिलता के बीच संतुलन बनाना आवश्यक है।
  • मुख्य निष्कर्ष: शुरुआती लोगों के लिए वितरित की-वैल्यू स्टोर। put/get मतलब रखना और निकालना, सीएपी (सीएपी (CAP)) एक सरल कहानी में, पार्टीशन किताबों को अलमारियों में बाँटना, रेप्लिकेशन नकलें रखना, क्वोरम लाइब्रेरियन की सहमति।
  • परिणाम: उत्पादन वातावरण में विफलता से निपटने और प्रदर्शन लक्ष्यों को हासिल करने की सटीक रूपरेखा।

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

  • कुंजी (key) टिकट नंबर है।
  • वैल्यू कोट है।
  • put का मतलब: इस टिकट के नीचे यह कोट रखो।
  • get का मतलब: इस टिकट का कोट निकालो।

रैक कैसे सजा है, जानना ज़रूरी नहीं। सिर्फ़ एक भरोसेमंद नियम चाहिए: वही टिकट, वही कोट।

कंप्यूटर भी यही करते हैं। रेडिस, मेमकैश्ड, डायनेमो-स्टाइल सिस्टम, और कई प्रोडक्ट की मेटाडेटा लेयर यहीं से शुरू होती हैं। दो क्रियाएँ, पीछे बहुत सारी इंजीनियरिंग।

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

दो क्रियाएँ: रखना और निकालना

की-वैल्यू स्टोर एक ऐसा डेटाबेस है जिसकी इंटरफ़ेस बहुत छोटी है।

क्रिया रोज़मर्रा का मतलब क्या करती है
put(key, value) रखना इस कुंजी की वैल्यू सेव या बदल दो
get(key) निकालना / लाना वैल्यू दो, या साफ़ कहो "नहीं मिला"

कुंजियाँ यूनिक होती हैं। वैल्यू कोई भी छोटी चीज़ हो सकती है: सेशन स्ट्रिंग, जेसन, काउंटर, शॉपिंग कार्ट का स्नैपशॉट। इंटरव्यू वाले रूप में वैल्यू अक्सर कुछ किलोबाइट की होती है, पूरी फ़िल्म नहीं।

बाद में वैकल्पिक: डिलीट, टाइमर के बाद खत्म (टीटीएल), "सिर्फ़ तब लिखो जब कुंजी अभी भी वर्शन X पर हो।" कोर पाथ सही होने तक इन्हें बाहर रखो।

लेबल वाले दराज: दीवार भर दराज सोचो। हर दराज पर लेबल (कुंजी)। अंदर एक चीज़ (वैल्यू)। put दराज खोलकर रखता है। get दराज खोलकर देखता है। शुरू करने के लिए यही मॉडल काफी है।

एक कंप्यूटर क्यों काफी नहीं

एक मशीन पर की-वैल्यू स्टोर मेमोरी में हैश मैप हो सकता है। डेमो और छोटे कैश के लिए बढ़िया।

फिर हकीकत आती है:

१. मैप रैम में फिट नहीं रहता। २. मशीन रीबूट होती है और डिस्क पर न लिखा हो तो सब गायब। ३. एक मशीन हमेशा के लिए लाखों अनुरोध प्रति सेकंड नहीं संभाल सकती। ४. एक इमारत में बिजली जाती है और पूरा प्रोडक्ट गिर जाता है।

इसलिए कई मशीनें जोड़ते हो। अब नया सवाल: कौन सी मशीन किस कुंजी को रखेगी, और अगर वह मशीन मर जाए तो?

यही वितरित की-वैल्यू स्टोर की पूरी कहानी है।

लाइब्रेरी कार्ड कैटलॉग: सही शेल्फ़ ढूँढना

लाइब्रेरी हर किताब एक ढेर में नहीं फेंकती। कैटलॉग और शेल्फ़ प्लान होता है।

  • कार्ड कैटलॉग (या आधुनिक सर्च इंडेक्स) बताता है किताब कहाँ है।
  • किताबें अलग-अलग शेल्फ़ पर बाँटी जाती हैं ताकि एक शेल्फ़ पर पूरी लाइब्रेरी न हो।
  • लोकप्रिय किताबों की अतिरिक्त नकलें होती हैं ताकि ज़्यादा लोग ले सकें।

वितरित की-वैल्यू स्टोर वही तीन काम करता है:

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

यह टेबल दिमाग में रखो। जो भी बॉक्स बनाओगे, लगभग सब यहीं लौटता है।

सीएपी (सीएपी (CAP)), एक सरल कहानी में

तुम तीन काउंटर वाला कोट-चेक चलाते हो। वे वॉकी-टॉकी से सिंक रहते हैं। नाम: A, B, C। मेहमान किसी भी काउंटर पर जा सकता है।

अब रेडियो टूट जाते हैं। काउंटर C, A और B से बात नहीं कर सकता। मेहमान आते रहते हैं। तुम्हें नीति चुननी है।

विकल्प १: सबको हमेशा एक ही जवाब दिखे

टूटे हिस्से को फ्रीज़ करो। C तब तक कोट नहीं लेता जब तक रेडियो ठीक न हों। A और B भी जोखिम वाले काम रोक सकते हैं जब तक पक्का न हो।

C पर मेहमान सुनते हैं: "माफ़ कीजिए, सिस्टम टूटा है। बाद में आइए।"

टिकट ४२ पर दो अलग कहानियाँ किसी को नहीं मिलतीं। कीमत यह है कि आउटेज में कुछ मेहमानों को कोई जवाब नहीं मिलता।

सीएपी (सीएपी (CAP)) भाषा में यह CP की तरफ़ झुकता है: पार्टीशन में कंसिस्टेंसी प्राथमिक। बैंक और लेजर अक्सर यही चाहते हैं। गलत बैलेंस दिखाना अस्थायी "फिर कोशिश करें" से बुरा है।

विकल्प २: नेटवर्क टूटे तो भी किसी को हमेशा जवाब मिले

A और B कोट लेते रहते हैं। C भी जो जानता है उसी से काम चलाता है। मेहमान को हमेशा टिकट और जवाब मिलता है।

बाद में रेडियो ठीक होते हैं। स्टाफ़ देखता है टिकट ४२ पर दो काउंटर पर दो अलग कोट हैं। किसी को मर्ज करना होगा, विजेता चुनना होगा, या मेहमान से सुलझवाना होगा।

सीएपी (सीएपी (CAP)) भाषा में यह AP की तरफ़ झुकता है: पार्टीशन में उपलब्धता प्राथमिक। शॉपिंग कार्ट, सेशन स्टोर, और कई प्रोडक्ट कैश यही चुनते हैं और बाद में सुधारते हैं।

अक्षरों का सादा मतलब

अक्षर सादा मतलब
C Consistency स्वस्थ क्लाइंट एक जैसा अप-टू-डेट जवाब देखें (मज़बूत रूप)
A Availability ज़िंदा नोड अनुरोधों का जवाब देते रहें
P Partition tolerance जब नोड बात न कर सकें तब भी सिस्टम का प्लान हो

असली मल्टी-मशीन सिस्टम में नेटवर्क फेल होता है। P के साथ जीना पड़ता है। असली चुनाव अक्सर यह होता है: जब नेटवर्क बीमार हो तो C से चिपके रहोगे या A से।

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

पार्टीशनिंग: किताबें अलमारियों पर बाँटना

हर कुंजी हर मशीन पर रखना बहुत महंगा है। इसलिए की-स्पेस को पार्टीशन (शार्ड) करते हो।

रोज़मर्रा की तस्वीर: शेल्फ़ १ पर टिकट १-१०००, शेल्फ़ २ पर १००१-२०००, वगैरह। कंप्यूटर में ज़्यादातर की-वैल्यू डिज़ाइन के लिए नियम सिर्फ़ फिक्स्ड रेंज से होशियार होता है।

कंसिस्टेंट हैशिंग एक साँस में

सर्वर एक बड़े घेरे (हैश रिंग) पर खड़े सोचो। हर कुंजी को उसी घेरे पर हैश करो। घड़ी की सुई की दिशा में चलो जब तक सर्वर न मिले। वही सर्वर कुंजी का मालिक।

लोग इसे क्यों पसंद करते हैं:

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

व्हाइटबोर्ड डिज़ाइन के लिए पूरी गणित ज़रूरी नहीं। मकसद चाहिए: कुंजियों की स्थिर मालिकी, कम से कम अदला-बदली।

हॉट कुंजियाँ फिर भी दर्द देती हैं। एक सेलिब्रिटी कुंजी एक प्राथमिक जगह पर ही गिरती है। आगे कैश, बेहतर की-डिज़ाइन, या हॉट-पाथ का अलग प्लान मदद करता है। अकेला रिंग प्रसिद्धि नहीं ठीक करता।

रेप्लिकेशन: नकलें रखो ताकि एक शेल्फ़ की आग घातक न हो

अगर टिकट ४२ सिर्फ़ एक मशीन पर है और वह मर गई, कोट गया। लाइब्रेरी लोकप्रिय किताबों की कई नकल रखती है। की-वैल्यू सिस्टम N रेप्लिका रखते हैं।

इंटरव्यू का आम डिफ़ॉल्ट: N = ३। हर कुंजी की तीन नकलें तीन अलग मशीनों पर, आदर्श रूप से अलग रैक या ज़ोन में ताकि एक बिजली की घटना सारी नकल न मिटाए।

रिंग पर पहला सर्वर मिलने के बाद प्लेसमेंट: आगे चलो और अगली N अलग मशीनें चुनो।

रेप्लिकेशन खरीदता है:

१. ड्यूरेबिलिटी अगर एक डिस्क मरे। २. उपलब्धता अगर एक नोड ऑफलाइन हो। ३. रीड स्केल अगर कई रीडर अलग नकलों पर जाएँ।

यह नया सिरदर्द भी लाता है: नकलें थोड़ी देर असहमत हो सकती हैं। इसलिए सीएपी (सीएपी (CAP)) और क्वोरम मायने रखते हैं।

क्वोरम: ज़्यादातर लाइब्रेरियन सहमत हों

तीन लाइब्रेरियन के पास एक ही कार्ड की नकलें हैं। नियम चाहिए कि चेक-इन या चेक-आउट कब "हो गया" माना जाए।

चिह्न सादा मतलब
N कुल कितनी नकलें हैं
W राइट सफल मानने के लिए कितनी नकलें पुष्टि करें
R रीड पर कितनी नकलों से जवाब सुनो

कोऑर्डिनेटर (जो भी नोड क्लाइंट का अनुरोध ले) रेप्लिका सेट से पूछता है और जवाब गिनता है।

सुनहरा ओवरलैप नियम

अगर W + R > N, स्थिर अवस्था में सफल रीड और सफल राइट कम से कम एक नकल साझा करते हैं। उस नकल ने आखिरी सफल राइट देखा होना चाहिए। मज़बूत कंसिस्टेंसी मिलती है।

N = ३ के उदाहरण:

W R अहसास
१ १ तेज़ और कमज़ोर। पुरानी रीड ज़्यादा संभावित।
२ २ आम डिफ़ॉल्ट। राइट और रीड दोनों पर बहुमत।
३ १ बहुत सावधान राइट, तेज़ रीड। अगर R बहुत छोटा हो और पिछड़ी नकल जवाब दे तो अभी भी कमज़ोर।
१ ३ तेज़ राइट, सावधान रीड जो सबसे पूछे।

ज़रूरी: W = १ का मतलब यह नहीं कि "सिर्फ़ एक नकल रखो।" मतलब है "एक पुष्टि के बाद क्लाइंट को सफलता बता दो," जबकि बाकी नकलें अभी पकड़ रही हों।

लेटेंसी क्वोरम के सबसे धीमे सदस्य पर चलती है, सबसे तेज़ पर नहीं। W या R बढ़ाओ तो कंसिस्टेंसी सुधरती है, टेल लेटेंसी अक्सर बिगड़ती है।

कहानी रूप: नई कैटलॉग कार्ड फाइल करने के लिए तीन में से दो लाइब्रेरियन मुहर लगाएँ (W = २)। विज़िटर को जवाब देने के लिए तीन में से दो अपनी कार्ड बताएँ (R = २)। अगर कहानियाँ टकराएँ, बोलने से पहले वर्शन सुलझाओ (अगला भाग)।

जब नकलें असहमत हों: वर्शन

दो मेहमान नेटवर्क स्प्लिट के दो तरफ़ एक साथ टिकट ४२ अपडेट करते हैं। ढीली नीति में दोनों राइट सफल। अब दो "सच" हैं।

सरल लेकिन खुरदुरा: आखिरी राइट जीते टाइमस्टैम्प से। घड़ियाँ स्क्यू में झूठ बोल सकती हैं, असली अपडेट चुपचाप खो सकता है।

ज़्यादा सावधान: वेक्टर क्लॉक (या मिलते-जुलते वर्शन वेक्टर) ट्रैक करते हैं किसने क्या देखा। अगर एक वर्शन साफ़ बाद का है, बाद वाली लाइन रखो। अगर दोनों अलग दिशा में गए, सिबलिंग हैं: असली संघर्ष। ऐप मर्ज करे (कार्ट आइटम मिल जाएँ) या दोनों दिखाए।

कई प्रोडक्ट कुंजियों पर last-write-wins ही शिप होता है क्योंकि चुप नुकसान स्वीकार है। कार्ट और सहयोगी स्टेट के लिए सिबलिंग मर्ज सुरक्षित। प्रोडक्ट का नियम ज़ोर से कहो।

जब लाइब्रेरियन बीमार हो

छोटी आउटेज: स्लॉपी क्वोरम और हिंटेड हैंडऑफ़

सख्त नियम सब कुछ रोक सकते हैं अगर पसंदीदा रेप्लिका बहुत गिर जाएँ। स्लॉपी क्वोरम डेस्क खुला रखता है: राइट के लिए प्रेफ़रेंस लिस्ट की पहली W स्वस्थ मशीनें लो, भले मालिकाना हक सामान्य न हो। पड़ोसी नोट रख सकता है: "यह कोट काउंटर C का है।" C लौटे तो पड़ोसी हैंडऑफ़ करे। यही hinted handoff है।

लंबी ड्रिफ्ट: एंटी-एंट्रॉपी और मर्कल ट्री

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

मेंबरशिप के लिए गॉसिप

नोड्स को साझा समझ चाहिए कि कौन ज़िंदा है। वे गॉसिप करते हैं: समय-समय पर रैंडम पीयर से मेंबरशिप और हार्टबीट अदला-बदली। इस चित्र के लिए एक "बॉस मशीन" ज़रूरी नहीं, हालाँकि असली ऑप्स अक्सर कंट्रोल प्लेन भी जोड़ते हैं।

put और get पूरा सफ़र

put(key, value) - कोट रखना

१. क्लाइंट put कोऑर्डिनेटर को भेजता है (कोई भी नोड, या लोड बैलेंसर चुनता है)। २. कोऑर्डिनेटर कुंजी हैश करता है और N मशीनों की प्रेफ़रेंस लिस्ट ढूँढता है। ३. राइट उन मशीनों (या स्लॉपी क्वोरम में स्वस्थ स्थानापन्न) को भेजता है। ४. W सफल ack का इंतज़ार करता है। ५. सफलता लौटाता है, या क्वोरम न बने तो एरर।

जो रेप्लिका राइट स्वीकारे, आम टिकाऊ रास्ता:

१. डिस्क पर commit log में जोड़ो (प्रोसेस क्रैश से बचाव)। २. मेमोरी संरचना (memtable) अपडेट करो। ३. बाद में डिस्क पर क्रमबद्ध फ़ाइलें (SSTables) में flush। ४. बैकग्राउंड compaction फ़ाइलें मिलाए, डिलीट साफ़ करे।

get(key) - कोट निकालना

१. कोऑर्डिनेटर प्रेफ़रेंस लिस्ट ढूँढता है। २. R जवाब आने तक पढ़ता है (या स्वस्थ स्थानापन्न)। ३. वर्शन टकराएँ तो सुलझाता है। ४. वैकल्पिक रूप से पिछड़ी नकल ठीक करता है (read repair)। ५. वैल्यू या not-found लौटाता है।

लोकल रीड ट्रिक नाम ले सकते हो: पहले मेमोरी, Bloom filter से वे डिस्क फ़ाइल छोड़ो जिनमें कुंजी हो ही नहीं सकती, वर्शन मिलाओ, डिलीट लागू करो।

आर्किटेक्चर का आकार (एक चित्र)

Client
  |
  v
Coordinator (कोई भी नोड यह रोल खेल सकता है)
  |
  +---> इस कुंजी की N रेप्लिका (हैश रिंग पर)
  |
  +---> Gossip / membership
  |
  +---> लोकल स्टोरेज (commit log + memtable + SSTables)

इंटरव्यू में कहने लायक बातें:

  • क्लाइंट एपीआई get/put ही रहती है।
  • पूरे की-स्पेस का एक मास्टर नहीं। हर कुंजी की अपनी प्रेफ़रेंस लिस्ट।
  • हर नोड कोऑर्डिनेट, स्टोर, रिपेयर, गॉसिप कर सकता है। सममित रोल ऑपरेशन आसान बनाते हैं।
  • नोड जोड़ने पर रिंग अपडेट और उन रेंज का स्ट्रीम जिन्हें उसे रखना है।

यह डिज़ाइन किसके लिए झुकता है

यह क्लासिक डायनेमो-स्टाइल स्केच ट्यूनेबल कंसिस्टेंसी वाले AP की तरफ़ है:

  • पार्टीशन अपेक्षित हैं।
  • सिस्टम जवाब देते रहना पसंद करता है।
  • N, W, R से रीड/राइट की सावधानी सेट करते हो।

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

क्षमता की समझ (गोल नंबर ज़ोर से कहो)

व्हाइटबोर्ड अंदाज़, फाइनेंस प्लान नहीं:

  • औसत वैल्यू १ KB, छोटी कुंजी, थोड़ी मेटाडेटा → कॉपी से पहले लगभग १.३ KB प्रति आइटम डिस्क पर।
  • १ अरब कुंजियाँ → कच्चा लगभग १.३ TB। N = ३ और फ़ाइल ओवरहेड के साथ कई TB यूज़ेबल क्लस्टर स्टोरेज सोचो।
  • १००k रीड QPS और १०k राइट QPS: फैन-आउट के हिसाब से नापो। हर राइट N मशीन छू सकता है; क्लाइंट W का इंतज़ार करता है।
  • क्रॉस-ज़ोन ट्रैफ़िक असली लागत लाइन है, मुफ़्त जादू नहीं।

२x गलती ठीक। रेप्लिकेशन या पीक लोड भूलना नहीं।

सुनाने लायक फेलियर कहानियाँ

१. एक रेप्लिका डाउन: स्लॉपी क्वोरम और हिंट put/get चलाते रहते हैं; रिकवरी पर हैंडऑफ़। २. तीन में से दो डाउन (N = ३, W = २): W इकट्ठा होने तक राइट फेल हो सकते हैं। अस्थायी नीति बनाम राइट रोकने पर चर्चा। ३. नेटवर्क स्प्लिट: AP दोनों तरफ़ चलता रहता है; ठीक होने पर संघर्ष। CP असुरक्षित तरफ़ रोकता है। ४. धीमी रेप्लिका: क्वोरम लेटेंसी W-वें या R-वें जवाब पर चलती है, सबसे तेज़ पर नहीं। ५. एक नोड पर डिस्क फुल: नोड लोड छोड़ता है या मरता है; रिंग और रिपेयर रेंज हटाएँ।

अगर "एक नोड डाउन" और "दो वर्शन अलग हो गए" के तहत put और get चला सकते हो, इंटरव्यू का कोर तुम्हारे पास है।

नॉब चीट शीट

नॉब क्या बदलता है
N कितनी नकलें; ड्यूरेबिलिटी और स्टोरेज लागत
W / R कंसिस्टेंसी बनाम लेटेंसी
वर्चुअल नोड गिनती लोड कितनी आसानी से रीबैलेंस हो
मल्टी-ज़ोन प्लेसमेंट बड़े आउटेज सहना बनाम ज़्यादा राइट लेटेंसी
हिंट का जीवनकाल अस्थायी धारक विदेशी डेटा कब तक रखें
रिपेयर शेड्यूल ड्रिफ्ट कितनी जल्दी साफ़ हो बनाम बैकग्राउंड बैंडविड्थ

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

की-वैल्यू स्टोर एक विशाल कोट-चेक है: टिकट अंदर, कोट बाहर। put रखता है, get निकालता है।

एक मशीन एक ही अलमारी है। कई मशीनों को लाइब्रेरी प्लान चाहिए: किताबें शेल्फ़ पर बाँटो (पार्टीशनिंग), अतिरिक्त नकल रखो (रेप्लिकेशन), और स्टाफ़ को साफ़ नियमों से सहमत करो (क्वोरम)।

जब काउंटरों के बीच वॉकी-टॉकी टूटे, चुनो: सबके लिए एक जवाब (भले कुछ मेहमान प्रतीक्षा करें) या किसी को हमेशा जवाब (भले बाद में मेल मिलाप करो)। पार्टीशन के नीचे यही सीएपी (सीएपी (CAP)) का चुनाव है।

तीन लाइब्रेरियन में N कितने कार्ड रखते हैं, W कितने राइट पर मुहर लगाएँ, R रीड पर कितनों से पूछो। अगर W + R > N, अच्छी रीड को अच्छा राइट दिखना चाहिए।

नकलें कभी-कभी असहमत होती हैं। छोटे गैप हैंडऑफ़ और हिंट से ठीक करो। लंबी ड्रिफ्ट बैकग्राउंड रिपेयर से। क्लाइंट एपीआई छोटी रखो ताकि मुश्किल काम क्लस्टर के अंदर रहे।

यही वितरित की-वैल्यू स्टोर है: नेटवर्क पर जादुई हैश मैप नहीं, बल्कि शेल्फ़ प्लान, नकल प्लान, और उस दिन का स्टाफ़ नियम जब कुछ टूटता है।