अपना खुद का डेटाबेस बनाकर देखें

• की-वैल्यू डेटाबेस के मूल सिद्धांत और निर्माण प्रक्रिया को समझाया गया है
• स्थायी भंडारण और खोज के लिए फाइल सिस्टम-आधारित तरीके से शुरुआत की जाती है
• डेटा जोड़ने, बदलने और हटाने के ऑपरेशन में अप्रभावी समस्याएँ आती हैं
• Append-Only फाइल, इंडेक्स, क्रमबद्धता (sorting), सेगमेंट कॉम्पैक्शन जैसे चरणों से यह धीरे-धीरे अधिक कुशल संरचना बनता है
• अंततः यह LSM ट्री जैसी आधुनिक संरचना से जुड़ता है और वास्तविक बड़े सिस्टमों में इस्तेमाल होता है

---

परिचय: डेटाबेस स्वयं बनाने की शुरुआत

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

मूल विचार: फाइल का उपयोग करके स्थायी भंडारण

• डेटाबेस का उद्देश्य डेटा को दीर्घकाल तक सुरक्षित रखना और बाद में कुशल खोज करना है।
• सबसे आम तरीका यह है कि प्रत्येक key-value जोड़े को फाइल सिस्टम के ज़रिए फाइल में लिख दिया जाए।
• डेटा डालते समय, उदाहरण के लिए $ db set 1 "Lorem ipsum" फ़ॉर्मेट में फाइल में नया रिकॉर्ड जोड़ा जाता है।
• खोज करते समय फाइल के अंदर मौजूद सभी key-value जोड़ों को क्रम से स्कैन करके वांछित key खोजी जाती है।
• अपडेट के लिए उस key के स्थान पर सीधे नया मान लिखने और डिलीट करने पर उस रिकॉर्ड को फाइल से हटाने की कोशिश की जाती है।

समस्या: In-Place अपडेट की अक्षमता

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

सुधार 1: Append-Only फाइल संरचना

• अपडेट और डिलीट के समय पुराने डेटा को हटाए बिना, हर बार सिर्फ नया रिकॉर्ड फाइल के अंत में जोड़ना अपनाया जाता है।
• जब डेटा बदलता है, नया रिकॉर्ड जोड़कर खोज एल्गोरिद्म को ऐसा बदलते हैं कि key का अंतिम (latest) संस्करण पढ़ा जाए।
• डिलीट के लिए विशेष tombstone मान (जैसे null) से मार्क किया जाता है।
• फायदा: पुराने डेटा को शिफ्ट किए बिना तेज़ी से लिखना संभव।
• नुकसान: दोहराए गए रिकॉर्ड और delete markers की वजह से फाइल धीरे-धीरे भारी होती जाती है।
• खोज अभी भी धीमी हो सकती है क्योंकि कई बार पूरी फाइल स्कैन करनी पड़ती है।

सुधार 2: फाइल आकार प्रबंधन और कंपैक्शन (Compaction)

• फाइल के अनंत रूप से बढ़ने की समस्या हल करने के लिए, जब आकार सीमा से ऊपर जाए तो नया फाइल/सेगमेंट शुरू किया जाता है।
• पुराने सेगमेंट से अनावश्यक डेटा (duplicate/डिलीट हुए रिकॉर्ड) हटाकर फाइल का आकार घटाया जाता है (compaction)।
• कॉम्पैक्शन में केवल वास्तव में आवश्यक डेटा ही रखा जाता है; पुराने, अप्रासंगिक एंट्री हटाई जाती हैं।
• कई सेगमेंट फाइलों को संभालकर आवश्यकता होने पर इन्हें merge करने की दिशा में विकास होता है।

सुधार 3: इंडेक्स (Index) के साथ तेज़ खोज

• हर key के लिए फाइल में उसकी स्थिति (offset) रखने वाला इन-मे्मोरी (hash table) इंडेक्स बनाया जाता है ताकि खोज तेज हो।
• खोज के समय पहले इंडेक्स देख कर सीधे फाइल के सही स्थान से डेटा पढ़ा जाता है।
• ट्रेड-ऑफ: खोज तेज हो जाती है, लेकिन इंडेक्स मेमोरी में रहता है इसलिए key की संख्या बहुत बढ़ने पर मेमोरी सीमा आ सकती है।
• इंडेक्स मैनेजमेंट के कारण write performance कुछ हद तक कम हो सकती है।

सुधार 4: सॉर्टेड स्ट्रिंग टेबल (Sorted String Table) और Sparse Index

• key के आधार पर हमेशा क्रमबद्ध (sorted) भंडारण करने पर रेंज क्वेरी (range query) बहुत कुशल हो जाती है।
• क्रमबद्ध डेटा का उपयोग करके इंडेक्स को हर key के लिए नहीं, सिर्फ कुछ key के लिए (sparse index) रखा जा सकता है।
• इंडेक्स की घनता बदलकर मेमोरी खपत और खोज दक्षता के बीच trade-off संभाला जा सकता है।

कार्यान्वयन तरीका: इन-मे्मोरी + ऑन-डिस्क संयोजन और स्थायित्व

• नया डेटा पहले sorted in-memory सूची में रखा जाता है और साथ में backup के लिए append-only फाइल में भी लिखते हैं।
• जब इन-मे्मोरी सूची बड़ी हो जाए तो उसे ऑन-डिस्क फाइल (SST) के रूप में sorted करके स्टोर करते हुए इंडेक्स अपडेट करते हैं।
• खोज के समय पहले मेमोरी देखी जाती है, न मिलने पर इंडेक्स की मदद से डिस्क से खोज की जाती है।
• ऑन-डिस्क फाइलों को immutable रखा जाता है; अपडेट/डिलीट भी नए डेटा जोड़कर ही हैंडल किए जाते हैं।
• अनावश्यक duplicates और हटाए गए डेटा को समय-समय पर compaction करके फाइल आकार नियंत्रित किया जाता है।

LSM ट्री (Log-Structured Merge Tree) का आगमन

• ऊपर के ये विकास वास्तव में LSM ट्री के नाम से व्यापक रूप से जाने जाते हैं।
• इन-मे्मोरी (memtable) और ऑन-डिस्क (sorted string table, SST) का संयोजन इसे तेज़ और बड़े स्केल पर उपयुक्त बनाता है।
• LevelDB, Amazon DynamoDB जैसे बड़े की-वैल्यू सिस्टम में यह मुख्य डेटा संरचना के रूप में उपयोग होता है।
• इसमें कुछ सीमाएँ और B-Tree आधारित रिलेशनल डेटाबेस से अंतर मौजूद हैं, फिर भी बड़े ट्रैफिक और स्केल के लिए यह मजबूत प्रदर्शन देता है।

निष्कर्ष

• सरल फाइल-आधारित मॉडल से शुरू होकर append-only, इंडेक्स, सॉर्टिंग, सेगमेंट- कम्पैक्शन और इन-मे्मोरी + ऑन-डिस्क संयोजन से बेहतर डेटाबेस डिज़ाइन की ओर विकास होता है।
• यह दृष्टिकोण विकसित करते हुए डेटाबेस के अंदरूनी काम करने के तरीके और संरचनात्मक निर्णयों को व्यावहारिक रूप से समझा जा सकता है।
• LSM ट्री संरचना आज के बड़े डेटा सिस्टमों में मानक भूमिका निभाती है।
• आगे जाकर रिलेशनल डेटाबेस की B-Tree जैसी अन्य संरचनाओं की खोज के लिए भी जगह बनी रहती है।

[GN⁺]

Hacker News टिप्पणियाँ

• इस लेख का डिज़ाइन और उदाहरण सच में बहुत पसंद आया; पढ़ने में आसान लेआउट बहुत प्रभावशाली है। ऐसा अभ्यास खुद करना भी बहुत मज़ेदार अनुभव है—कुछ भी न होने की स्थिति से शुरू करने पर पता चलता है कि वास्तव में आप कितना जानते हैं।
  • मैं भी पहले इसी तेजी से सोच रहा था कि “खुद डेटाबेस मत बनाओ, KV डेटाबेस भी मत इस्तेमाल करो, बस SQL इस्तेमाल करो।” लेकिन शायद वही सोचना इसलिए बना क्योंकि सीधे DB डिज़ाइन करने या सिर्फ KV डेटाबेस का सहारा लेकर SQL से बचने की कोशिश में अंततः SQL को ही अधूरा-सा दोबारा गढ़ना पड़ा। सीधा करके सीखने की वैल्यू निश्चित रूप से होती है।
  • एक खेद की बात यह है कि उदाहरण में lorem ipsum उपयोग किया गया है, जिससे ध्यान एकाग्र नहीं होता और बस जल्दी-जल्दी पढ़कर आगे निकल जाना आसान लगने लगता है। वास्तविक डेटा उदाहरण इससे कहीं अधिक आकर्षक होते। बाकी सब में सच में शानदार लेखन है।
• “LSM tree उन डेटा स्ट्रक्चर में से है जो DynamoDB आदि में मूल रूप से इस्तेमाल होता है और large-scale environment में भी बहुत अच्छा performance देता है… यानी प्रति सेकंड 80 मिलियन requests सम्भव हैं” — इसमें थोड़ी misunderstanding की संभावना है। LSM सामान्यतः node-level storage engine में लगता है, जबकि पूरी distributed system को कुल 80 मिलियन RPS तक स्केल होने की प्रक्रिया explain नहीं की गई है। मेरी याद के अनुसार original Dynamo paper में पहले BerkeleyDB (b-tree या LSM) था और 2012 के paper में पूरी तरह LSM-based engine पर शिफ्ट किया गया।
• लेख सूची के कुछ articles क्लिक करके देखे; डिजाइन और animation सच में बहुत सुंदर थे—इंप्रेस्ड।
• “Sorting in Practice” सेक्शन का पहला उदाहरण शायद टूट गया है। explanation में यह कहा गया है कि memory में sort करने के बाद उसी sorted state में disk पर write होना चाहिए, लेकिन actual example में disk पर write करते समय sort खुल जाती है। recap भाग का दूसरा flush उदाहरण भी ऐसा ही है, जबकि टेक्स्ट में लिखा है कि file को sorted state में रिकॉर्ड किया गया है।
• दिलचस्प लेख था। मैं हाल ही में डेवलपर activity को time-series key-value system के तौर पर model कर रहा हूँ, जहाँ प्रत्येक developer key है और commit उसका value। इसी तरह की समस्या सामने आई: log बहुत तेज़ी से बढ़ता जा रहा है, index भारी होता जा रहा है, और range query धीमी हो रही है। Segment compaction में यह तय करना मुश्किल लगता है कि कौन-सा डेटा drop करें; freshness और retention period के बीच balance बनाना कठिन है।
• पिछले 4 हफ्तों से मैं triple store सीधे लिखने में लगा था। अगर यह लेख थोड़ा पहले आ जाता तो कुछ insights शायद जल्दी समझ में आ जाते—थोड़ी कमी-सी रह गई।
• अगर लेखक यह देख रहे हों, तो पूछना चाहूँगा कि क्या साइट पर RSS feed add कर सकते हैं? मैं इसे Feedly में जोड़कर पढ़ना चाहता हूँ।
• यदि आप अपना खुद का database बनाना चाहते हैं, तो यह free online book ज़रूर recommend करता हूँ।
  • पहले कभी किसी ने bash उदाहरण से database के बेसिक concepts explain करने वाला कोई article (जैसे कि “bash से DB बनाना”) यहाँ दिखाया था, लेकिन खोजने पर नहीं मिल रहा। अगर किसी को उसका लिंक पता हो तो कृपया share करें।
• साइट पर पहले ही बहुत ज्यादा traffic के कारण शायद access नहीं हो पा रहा है।
  • निश्चित ही शायद एक बेहतर और तेज़ database की ज़रूरत पड़ेगी।
• इस तरह “First Principles” से धीरे-धीरे चरण-दर-चरण समझाना सच में बहुत पसंद आया। इस लेख के साथ आगे बढ़ते हुए हर step पर कौन-सा issue आता है और उसे solve करते समय कौन-से अतिरिक्त issues पैदा होते हैं, यह साफ़ समझ आता है; इसलिए एक बहुत संतोषजनक solution पर पहुँचना संभव होता है।