डेटा भंडारण एल्गोरिथ्म "लॉग संरचित संग्रहण"

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



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



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







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







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



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



अगला, आइए देखें कि जब हम किसी आइटम को अपडेट करते हैं तो क्या होता है। मान लें कि हम फू बदलते हैं:







हमने पत्रिका के अंत में फू की एक नई प्रति रिकॉर्ड करना शुरू किया। फिर हमने नोड इंडेक्स को फिर से अपडेट किया (केवल इस उदाहरण में) और इसे लॉग के अंत में भी लिखा। एक बार फिर, फू की पुरानी कॉपी लॉग में बनी हुई है, लेकिन अपडेट किया गया इंडेक्स बस अब इसे संदर्भित नहीं करता है।



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



फ़ाइल सिस्टम पर, कमियों में से एक जिसका मैंने पहले उल्लेख किया था, लॉग हेडर में एक अच्छा ब्लॉक नहीं है। जब हमें डिस्क से पूरी जानकारी मिलती है, तो फ़ाइल सिस्टम को अपना अधिक से अधिक समय कचरा इकट्ठा करने में लगाना चाहिए, और लॉग हेडर पर लगातार डेटा लिखना चाहिए। और जब आप 80% तक पहुंच जाते हैं, तो आपकी फ़ाइल प्रणाली व्यावहारिक रूप से बंद हो जाती है।



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







हमने यहां पर बार की एक मौजूदा प्रति ली थी और इसे लॉग के अंत में लिखा था, जिसके बाद हमने ऊपर वर्णित नोड (ओं) के सूचकांक को अपडेट किया। हमने ऐसा करने के बाद, जर्नल के पहले खंड को सुरक्षित रूप से हटाया जा सकता है।



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



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



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

हम, धीरे-धीरे, हमारे डेटाबेस को पत्रिका के प्रत्येक नए खंड के साथ बैकअप माध्यम में कॉपी कर सकते हैं।



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



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