प्रागितिहास

हमारे अपने डिजाइन की वेंडिंग मशीनें हैं। रास्पबेरी पाई के अंदर और एक अलग बोर्ड पर थोड़ा सा पट्टा। एक सिक्का स्वीकर्ता, बिल स्वीकर्ता, बैंक टर्मिनल जुड़े हुए हैं ... एक स्व-लिखित कार्यक्रम सब कुछ प्रबंधित करता है। काम का पूरा इतिहास एक फ्लैश ड्राइव (माइक्रोएसडी) पर जर्नल को लिखा जाता है, जो तब इंटरनेट (यूएसबी मॉडेम का उपयोग करके) सर्वर पर प्रसारित होता है, जहां इसे डेटाबेस में जोड़ा जाता है। बिक्री की जानकारी 1s में भरी हुई है, निगरानी आदि के लिए एक सरल वेब इंटरफ़ेस भी है।

यह है कि, पत्रिका महत्वपूर्ण है - लेखांकन के लिए (वहाँ राजस्व, बिक्री, आदि), निगरानी (सभी प्रकार की विफलताओं और अन्य बल की बड़ी परिस्थितियों); यह, आप कह सकते हैं, इस मशीन के बारे में हमारे पास जो भी जानकारी है।

समस्या

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

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

चेतावनी! Longrid! यदि आप "क्यों" में रुचि नहीं रखते हैं, लेकिन केवल "कैसे" में रुचि रखते हैं, तो आप तुरंत लेख के अंत में जा सकते हैं।

निर्णय

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

USB HDD भी विशेष रूप से आकर्षक समाधान नहीं दिखता है।

इसलिए, हम इस विकल्प पर आए: माइक्रोएसडी से डाउनलोड को छोड़ दें, लेकिन उन्हें केवल-पढ़ने के लिए मोड में उपयोग करें, और ऑपरेशन लॉग (और हार्डवेयर के एक विशिष्ट टुकड़े के लिए अद्वितीय अन्य जानकारी स्टोर करें - सीरियल नंबर, सेंसर कैलिब्रेशन, आदि) कहीं और।

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

हार्डवेयर हिस्सा

मेमोरी प्रकार की पसंद के बारे में कोई संदेह नहीं था - एनआर फ्लैश।
तर्क:

सरल कनेक्शन (सबसे अधिक बार एसपीआई बस, जो कि पहले से ही उपयोग करने का अनुभव है, इसलिए "लोहा" समस्याओं की उम्मीद नहीं है);
हास्यास्पद कीमत;
मानक संचालन प्रोटोकॉल (कार्यान्वयन पहले से ही लिनक्स कर्नेल में है, यदि आप चाहें, तो आप एक तृतीय-पक्ष ले सकते हैं, जो भी मौजूद हैं, या यहां तक कि अपना स्वयं का भी लिख सकते हैं, लाभ सरल है);
विश्वसनीयता और संसाधन:
एक विशिष्ट डेटाशीट से: डेटा 20 साल के लिए संग्रहीत किया जाता है, प्रत्येक ब्लॉक के लिए 100,000 मिटा चक्र;
तृतीय-पक्ष स्रोतों से: अत्यंत निम्न बीईआर, यह माना जाता है कि त्रुटि सुधार कोड की आवश्यकता नहीं है (कुछ कागजात में ईएनसी के लिए एनओआर पर विचार किया जाता है, लेकिन आमतौर पर एमएलसी नॉर का मतलब होता है, ऐसा होता है) ।

आइए हम वॉल्यूम और संसाधन की आवश्यकताओं का अनुमान लगाएं।

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

अब हम प्रति दिन 100kb पत्रिका (3-4 हजार रिकॉर्ड) टाइप कर रहे हैं, लेकिन धीरे-धीरे यह आंकड़ा बढ़ रहा है - विवरण बढ़ रहा है, नई घटनाओं को जोड़ा जा रहा है। इसके अलावा, कभी-कभी फट भी जाते हैं (कुछ सेंसर झूठी सकारात्मकता के साथ स्पैम करना शुरू कर देते हैं, उदाहरण के लिए)। हम प्रति दिन 100 बाइट्स - मेगाबाइट्स के 10 हजार रिकॉर्ड की गणना करेंगे।

कुल 5 एमबी स्वच्छ (अच्छी तरह से संपीड़ित) डेटा बाहर आता है। वे भी (मोटे अनुमान) 1MB सेवा डेटा।

यही है, अगर आप संपीड़न का उपयोग नहीं करते हैं, या 4 एमबी का उपयोग करते हैं, तो हमें 8MB माइक्रोचिप की आवश्यकता होती है। इस प्रकार की मेमोरी के लिए वास्तविक संख्याएँ काफी कम हैं।

संसाधन के लिए: यदि हम योजना बनाते हैं कि पूरी मेमोरी को हर 5 दिनों में एक बार से अधिक दोबारा नहीं लिखा जाएगा, तो 10 साल की सेवा में हमें एक हजार से भी कम साइकिल मिलेंगी।
मुझे याद है, निर्माता एक लाख का वादा करता है।

NOR बनाम NAND के बारे में थोड़ा

आज, निश्चित रूप से, NAND मेमोरी अधिक लोकप्रिय है, लेकिन इस परियोजना के लिए मैं इसका उपयोग नहीं करूंगा: NAND, NOR के विपरीत, त्रुटि सुधार कोड, बुरे ब्लॉक की एक तालिका, आदि का उपयोग करने की आवश्यकता है, और NAND चिप्स के पैर। आमतौर पर बहुत अधिक है।

NOR के नुकसान में शामिल हैं:

छोटी मात्रा (और, तदनुसार, मेगाबाइट की उच्च कीमत);
कम विनिमय दर (मोटे तौर पर इस तथ्य के कारण कि एक धारावाहिक इंटरफ़ेस का उपयोग किया जाता है, आमतौर पर एसपीआई या I2C);
धीमी गति से मिटना (ब्लॉक के आकार के आधार पर, यह एक सेकंड से लेकर कई सेकंड तक होता है)।

ऐसा लगता है कि हमारे लिए कुछ भी महत्वपूर्ण नहीं है, इसलिए जारी रखें।

यदि विवरण दिलचस्प हैं, तो at25df321a चिप को चुना गया था (हालांकि, यह महत्वहीन है, बाजार पर बहुत सारे एनालॉग हैं जो पिनआउट और कमांड सिस्टम के साथ संगत हैं; यहां तक कि अगर हम चिप को किसी अन्य निर्माता और / या किसी अन्य वॉल्यूम पर रखना चाहते हैं, तो कोड को बदले बिना सब कुछ काम करेगा) ।

मैं रास्पबेरी पर लिनक्स कर्नेल में निर्मित ड्राइवर का उपयोग करता हूं, डिवाइस ट्री ओवरले समर्थन के लिए धन्यवाद, सब कुछ बहुत सरल है - आपको संकलित ओवरले को / बूट / ओवरले में डालने और /boot/config.txt को थोड़ा संशोधित करने की आवश्यकता है।

उदाहरण dts फ़ाइल

ईमानदारी से, मुझे यकीन नहीं है कि त्रुटियों के बिना क्या लिखा गया है, लेकिन यह काम करता है।

/* * Device tree overlay for at25 at spi0.1 */ /dts-v1/; /plugin/; / { compatible = "brcm,bcm2835", "brcm,bcm2836", "brcm,bcm2708", "brcm,bcm2709"; /* disable spi-dev for spi0.1 */ fragment@0 { target = <&spi0>; __overlay__ { status = "okay"; spidev@1{ status = "disabled"; }; }; }; /* the spi config of the at25 */ fragment@1 { target = <&spi0>; __overlay__ { #address-cells = <1>; #size-cells = <0>; flash: m25p80@1 { compatible = "atmel,at25df321a"; reg = <1>; spi-max-frequency = <50000000>; /* default to false: m25p,fast-read ; */ }; }; }; __overrides__ { spimaxfrequency = <&flash>,"spi-max-frequency:0"; fastread = <&flash>,"m25p,fast-read?"; }; };

और config.txt में एक और लाइन

 dtoverlay=at25:spimaxfrequency=50000000

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

समस्या का बयान

हमेशा की तरह, समस्या का सूत्रीकरण कई पुनरावृत्तियों से होकर गुजरता है, यह मुझे लगता है कि आगे के लिए समय आ गया है। तो चलो रुकें, जो पहले से लिखा गया है उसे एक साथ रखें, और छाया में शेष विवरण को स्पष्ट करें।

इसलिए, हमने निर्णय लिया कि लॉग को SPI NOR फ़्लैश में संग्रहीत किया जाएगा।

जो लोग नहीं जानते उनके लिए NOR फ़्लैश क्या है

यह गैर-वाष्पशील मेमोरी है जिसके साथ आप तीन ऑपरेशन कर सकते हैं:

पढ़ने:
सबसे आम पढ़ने: हम पते को पास करते हैं और जितनी ज़रूरत होती है उतने बाइट्स पढ़ते हैं;
रिकॉर्ड:
NOR फ्लैश पर लिखना एक सामान्य की तरह दिखता है, लेकिन इसकी एक ख़ासियत है: आप केवल 1 से 0 को बदल सकते हैं, लेकिन इसके विपरीत नहीं। उदाहरण के लिए, यदि हमारे पास मेमोरी सेल में 0x55 है, तो इसे 0x0f लिखने के बाद, 0x05 पहले से ही वहां संग्रहीत किया जाएगा (नीचे दी गई तालिका देखें) ;
मिटाएं:
बेशक, हमें रिवर्स ऑपरेशन करने में सक्षम होना चाहिए - 0 से 1 को बदलना, यही कारण है कि मिटा संचालन मौजूद है। पहले दो के विपरीत, यह बाइट्स में नहीं, बल्कि ब्लॉक में (चयनित माइक्रोक्रिकिट में न्यूनतम इरेज़ ब्लॉक 4kb है)। मिटा पूरे ब्लॉक को नष्ट कर देता है और यह 0 से 1 को बदलने का एकमात्र तरीका है। इसलिए, फ्लैश मेमोरी के साथ काम करते समय, आपको अक्सर डेटा संरचनाओं को ब्लॉक ब्लॉक की सीमा में संरेखित करना पड़ता है।
NOR फ्लैश में रिकॉर्ड:

	बाइनरी डेटा
यह था	`01010101`
दर्ज की गई	`00001111`
बन गया है	`00000101`

पत्रिका स्वयं चर-लंबाई रिकॉर्ड के अनुक्रम का प्रतिनिधित्व करती है। एक सामान्य रिकॉर्डिंग की लंबाई लगभग 30 बाइट्स होती है (हालांकि लंबाई में कई किलोबाइट की रिकॉर्डिंग कभी-कभी होती है)। इस मामले में, हम उनके साथ बाइट्स के एक सेट की तरह काम करते हैं, लेकिन, यदि आप रुचि रखते हैं, तो CBOR का उपयोग रिकॉर्ड्स के अंदर किया जाता है।

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

यदि आप याद करते हैं कि यह लेख कहाँ से शुरू हुआ है, तो डेटा संग्रहण की विश्वसनीयता सुनिश्चित करना बहुत महत्वपूर्ण है और यदि संभव हो तो हार्डवेयर विफलताओं / डेटा भ्रष्टाचार की स्थिति में भी निरंतर संचालन।

समस्याओं के स्रोत पर क्या विचार किया जा सकता है?

लिखने / मिटाए जाने के दौरान बिजली बंद। यह "स्क्रैप नो रिसेप्शन के खिलाफ" की श्रेणी से है।
स्टैकएक्सचेंज पर चर्चा से जानकारी: जब फ्लैश के साथ काम करते समय बिजली बंद हो जाती है, तो मिटा दें (1 पर सेट करें), यह लिखें (सेटिंग में 0) अपरिभाषित व्यवहार को जन्म देती है: डेटा लिखा जा सकता है, आंशिक रूप से लिखा जा सकता है (कहते हैं, हमने 10 बाइट्स / 80 बिट्स स्थानांतरित कर दिए हैं) , और केवल 45 बिट्स रिकॉर्ड किए जाने में कामयाब रहे), यह भी संभव है कि कुछ बिट्स "मध्यवर्ती" स्थिति में होंगे (रीडिंग 0 या 1 का उत्पादन कर सकते हैं);
फ्लैश मेमोरी की त्रुटियां।
BER, हालांकि बहुत कम है, शून्य के बराबर नहीं हो सकता;
बस त्रुटियों
एसपीआई के माध्यम से प्रेषित डेटा किसी भी तरह से संरक्षित नहीं है, यह एकल बिट त्रुटियों या सिंक्रनाइज़ेशन त्रुटियों के रूप में हो सकता है - बिट्स का नुकसान या सम्मिलन (जो बड़े पैमाने पर डेटा विरूपण की ओर जाता है);
अन्य त्रुटियाँ / विफलताएँ
कोड में त्रुटियां, रास्पबेरी "ग्लिट्स", विदेशी हस्तक्षेप ...

मैंने आवश्यकताओं को तैयार किया है, जिनमें से, मेरी राय में, विश्वसनीयता सुनिश्चित करने के लिए आवश्यक है:

रिकॉर्ड को तुरंत फ्लैश मेमोरी में लिखा जाना चाहिए, विलंबित रिकॉर्डिंग पर विचार नहीं किया जाता है; - यदि कोई त्रुटि हुई है, तो इसे जल्द से जल्द पता लगाया जाना चाहिए और संसाधित किया जाना चाहिए; - सिस्टम, यदि संभव हो, तो त्रुटियों से उबरना चाहिए।
(जीवन से एक उदाहरण "जैसा कि यह नहीं होना चाहिए", जो मुझे लगता है, हर कोई मिले: एक आपातकालीन पुनरारंभ के बाद, फ़ाइल सिस्टम "टूट गया" और ऑपरेटिंग सिस्टम बूट नहीं करता है)

विचार, दृष्टिकोण, विचार

जब मैंने इस कार्य के बारे में सोचना शुरू किया, तो मेरे दिमाग में विचारों का एक गुच्छा उड़ गया, उदाहरण के लिए:

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

इनमें से कुछ विचारों का उपयोग किया गया था, कुछ को अस्वीकार करने का निर्णय लिया गया था। क्रम में चलते हैं।

डेटा संपीड़न

जिन घटनाओं को हम स्वयं पत्रिका में दर्ज करते हैं, वे काफी समान और दोहराए जाने योग्य हैं ("5 रूबल का सिक्का फेंक दिया," "परिवर्तन डिलीवरी बटन पर क्लिक किया", ...)। इसलिए, संपीड़न काफी प्रभावी होना चाहिए।

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

लॉग का एक टुकड़ा काम करने वाले उपकरण (1.7 एमबी, 70 हजार रिकॉर्ड) से लिया गया था और एक शुरुआत के लिए इसे कंप्यूटर पर उपलब्ध gzip, lz4, lzop, bzip2, xz, zstd का उपयोग करके संपीड़ितता के लिए जाँच की गई थी।

gzip, xz, zstd ने समान परिणाम (40Kb) दिखाए।
मुझे आश्चर्य हुआ कि फैशनेबल एक्सज़ ने खुद को यहाँ गज़िप या जेस्टीडी स्तर पर दिखाया;
डिफ़ॉल्ट सेटिंग्स के साथ lzip ने थोड़ा खराब परिणाम दिया;
lz4 और lzop ने बहुत अच्छे परिणाम नहीं दिखाए (150Kb);
bzip2 ने आश्चर्यजनक रूप से अच्छे परिणाम (18 केबी) दिखाए।

तो डेटा बहुत अच्छी तरह से संपीड़ित है।
इसलिए (यदि हम घातक दोष नहीं पाते हैं) तो संपीड़न होना चाहिए! सिर्फ इसलिए कि अधिक डेटा उसी फ्लैश ड्राइव पर फिट होगा।

आइए खामियों के बारे में सोचते हैं।

पहली समस्या: हम पहले ही सहमत हो गए हैं कि प्रत्येक रिकॉर्ड तुरंत फ्लैश पर मिलना चाहिए। आमतौर पर, संग्रहकर्ता इनपुट स्ट्रीम से डेटा एकत्र करता है जब तक कि यह तय नहीं हो जाता है कि यह आउटपुट पर लिखने का समय है। हमें तुरंत एक संकुचित डेटा ब्लॉक प्राप्त करने और इसे गैर-वाष्पशील मेमोरी में सहेजने की आवश्यकता है।

मैं तीन तरीके देखता हूं:

ऊपर चर्चा की गई एल्गोरिदम के बजाय शब्दकोश संपीड़न का उपयोग करके प्रत्येक प्रविष्टि को संपीड़ित करें।
यह काम करने का विकल्प है, लेकिन मुझे यह पसंद नहीं है। संपीड़न के अधिक या कम सभ्य स्तर को सुनिश्चित करने के लिए, शब्दकोश को विशिष्ट डेटा के लिए "तेज" किया जाना चाहिए, कोई भी परिवर्तन इस तथ्य को जन्म देगा कि संपीड़न स्तर भयावह रूप से गिरता है। हां, शब्दकोश का एक नया संस्करण बनाने से समस्या हल हो गई है, लेकिन यह एक सिरदर्द है - हमें शब्दकोश के सभी संस्करणों को संग्रहीत करने की आवश्यकता होगी; प्रत्येक प्रविष्टि में हमें यह इंगित करने की आवश्यकता होगी कि यह किस संस्करण के साथ संपीड़ित था ...
प्रत्येक प्रविष्टि को "क्लासिक" एल्गोरिदम के साथ संपीड़ित करें, लेकिन स्वतंत्र रूप से दूसरों के साथ।
विचाराधीन संपीड़न एल्गोरिदम इस आकार (बाइट्स के दसियों) के रिकॉर्ड के साथ काम करने के लिए डिज़ाइन नहीं किया गया है, संपीड़न गुणांक स्पष्ट रूप से 1 से कम होगा (यानी, संपीड़न के बजाय डेटा की मात्रा में वृद्धि);
प्रत्येक रिकॉर्डिंग के बाद फ्लश करें।
कई संपीड़न पुस्तकालयों में FLUSH का समर्थन है। यह एक कमांड (या कंप्रेशन प्रक्रिया के लिए पैरामीटर) है, जिसके प्राप्त होने पर संग्रहकर्ता एक संपीड़ित स्ट्रीम उत्पन्न करता है ताकि इसके आधार पर पहले से प्राप्त सभी असम्पीडित डेटा को पुनर्स्थापित किया जा सके। फ़ाइल सिस्टम में sync का ऐसा एनालॉग या एसक्यूएल में commit है।
क्या महत्वपूर्ण है, बाद के संपीड़न ऑपरेशन संचित शब्दकोश का उपयोग करने में सक्षम होंगे और संपीड़न अनुपात पिछले संस्करण में उतना अधिक नहीं होगा।

मुझे लगता है कि यह स्पष्ट है कि मैंने तीसरा विकल्प चुना, इस पर अधिक विस्तार से ध्यान दें।

Zlib में FLUSH के बारे में एक बढ़िया लेख था।

मैंने लेख के आधार पर एक प्रेरित परीक्षण किया, एक वास्तविक डिवाइस से entries० हजार जर्नल प्रविष्टियां लीं, जिसका पृष्ठ आकार ६० केबी (हम पृष्ठ आकार में वापस आ जाएगा) :

	स्रोत डेटा	Gzip -9 संपीड़न (बिना FLUSH)	z_PARTIAL_FLUSH के साथ zlib	z_SYNC_FLUSH के साथ zlib
वॉल्यूम, Kb	1692	40	352	604

पहली नज़र में, FLUSH द्वारा शुरू की गई कीमत बहुत अधिक है, लेकिन वास्तव में हमारे पास एक खराब विकल्प है - या तो सब कम करने के लिए, या (बहुत कुशलता से) संपीड़ित करने के लिए नहीं। यह मत भूलो कि हमारे पास 70 हजार रिकॉर्ड हैं, Z_PARTIAL_FLUSH द्वारा शुरू की गई अतिरेक रिकॉर्ड के अनुसार केवल 4-5 बाइट्स हैं। और संपीड़न अनुपात लगभग 5: 1 निकला, जो एक उत्कृष्ट परिणाम से अधिक है।

यह अप्रत्याशित लग सकता है, लेकिन वास्तव में Z_SYNC_FLUSH FLUSH करने का अधिक कुशल तरीका है

Z_SYNC_FLUSH का उपयोग करने के मामले में, प्रत्येक रिकॉर्ड के अंतिम 4 बाइट्स हमेशा 0x00, 0x00, 0xff, 0xff होंगे। और अगर हम उन्हें जानते हैं, तो हम उन्हें स्टोर नहीं कर सकते हैं, इसलिए कुल आकार केवल 324Kb है।

मैं जिस लेख का जिक्र कर रहा हूं उसमें स्पष्टीकरण है:

खाली सामग्री के साथ एक नया प्रकार 0 ब्लॉक संलग्न है।

खाली सामग्री के साथ एक प्रकार 0 ब्लॉक में निम्न शामिल हैं:
तीन-बिट ब्लॉक हेडर;
बाइट संरेखण को प्राप्त करने के लिए शून्य के बराबर 0 से 7 बिट्स;
चार-बाइट अनुक्रम 00 00 एफएफ एफएफ।

जैसा कि आप देख सकते हैं, आखिरी ब्लॉक में इन 4 बाइट्स 3 से 10 शून्य बिट्स से पहले आता है। हालांकि, अभ्यास से पता चला है कि शून्य बिट वास्तव में कम से कम 10 हैं।

यह पता चलता है कि इस तरह के शॉर्ट डेटा ब्लॉक आमतौर पर (हमेशा?) टाइप 1 (फिक्स्ड ब्लॉक) के ब्लॉक का उपयोग करके एन्कोड किया जाता है, जो जरूरी 7 शून्य बिट्स के साथ समाप्त होता है, इसलिए हमें 10-17 गारंटीकृत शून्य बिट्स मिलते हैं (और शेष लगभग 50% की संभावना के साथ शून्य होगा)।

इसलिए, परीक्षण डेटा पर, 100% मामलों में, 0x00, 0x00, 0xff, 0xff से पहले एक शून्य बाइट है, और तीसरे मामले में दो शून्य बाइट्स हैं (शायद तथ्य यह है कि मैं बाइनरी सीबीओआर का उपयोग करता हूं, और जब पाठ सीबीओआर का उपयोग करते हैं) JSON को क्रमशः टाइप 2 - डायनेमिक ब्लॉक के ब्लॉक मिलने की अधिक संभावना होगी, ब्लॉक 0x00, 0x00, 0xff, 0xff) से पहले अतिरिक्त शून्य बाइट्स के बिना होगा ।

उपलब्ध परीक्षण डेटा पर कुल संकुचित डेटा के 250Kb से कम में फिट हो सकता है।

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

कुल मिलाकर, मुझे अपने परीक्षण डेटा से प्रति रिकॉर्ड 3-4 बाइट्स मिला, संपीड़न अनुपात 6: 1 से अधिक था। ईमानदारी से, मैंने इस तरह के परिणाम पर भरोसा नहीं किया, मेरी राय में 2: 1 से बेहतर सब कुछ पहले से ही एक परिणाम है जो संपीड़न के उपयोग को सही ठहराता है।

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

इसलिए हम अपने अभिलेखागार का मिनी अध्ययन जारी रखते हैं।

अगले bzip2 का परीक्षण किया गया (याद रखें, FLUSH के बिना यह एक शानदार संपीड़न अनुपात दिखा, लगभग 100: 1)। काश, FLUSH के साथ यह खुद को बहुत खराब तरीके से दिखाता था, संपीड़ित डेटा का आकार असम्पीडित से अधिक था।

विफलता के कारणों के बारे में मेरी धारणाएं

Libbz2 केवल एक फ्लश विकल्प प्रदान करता है, जो शब्दकोष को साफ करने के लिए लगता है (zlib में Z_FULL_FLUSH के समान), किसी प्रकार के प्रभावी संपीड़न के बारे में बात करने का कोई कारण नहीं है।

और zstd परीक्षण के लिए अंतिम था। मापदंडों के आधार पर, यह या तो गज़िप स्तर पर संपीड़ित करता है, लेकिन बहुत तेज़, या गज़िप बेहतर है।

काश, FLUSH के साथ वह "बहुत नहीं" साबित हुआ: संपीड़ित डेटा का आकार लगभग 700Kb था।

मैंने github में प्रोजेक्ट पेज पर एक प्रश्न पूछा , मुझे एक जवाब मिला कि यह संपीड़ित डेटा के प्रत्येक ब्लॉक के लिए 10 बाइट्स तक सेवा डेटा की गिनती के लायक है, जो परिणामों के करीब है, अपस्फीति को पकड़ना काम नहीं करता है।

मैंने धनुर्विदों के साथ प्रयोगों में इसे रोकने का फैसला किया (मैं आपको याद दिलाता हूं कि xz, lzip, lzo, lz4 ने खुद को FLUSH के बिना परीक्षण चरण में नहीं दिखाया था, लेकिन मैंने अधिक विदेशी संपीड़न एल्गोरिदम पर विचार नहीं किया)।

हम संग्रह की समस्याओं पर लौटते हैं।

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

इस समस्या को हल करने के लिए एक दृष्टिकोण है:

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

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

यही है, न्यूनतम उचित पृष्ठ का आकार 16Kb (सेवा की जानकारी के लिए एक मार्जिन के साथ) है। हालांकि, इस तरह के एक छोटे पृष्ठ का आकार अधिकतम रिकॉर्डिंग आकार पर महत्वपूर्ण प्रतिबंध लगाता है।

यद्यपि मुझे अभी भी संपीड़ित रूप में किलोबाइट की अधिक इकाइयों के रिकॉर्ड की उम्मीद नहीं है, मैंने 32KB पृष्ठों (प्रति चिप कुल 128 पृष्ठ) का उपयोग करने का फैसला किया।

सारांश:

हम zlib (डिफ्लेट) का उपयोग करके डेटा को संचित करते हैं;
प्रत्येक रिकॉर्ड के लिए, Z_SYNC_FLUSH सेट करें;
प्रत्येक संकुचित रिकॉर्ड के लिए, हम अंतिम बाइट्स को ट्रिम करते हैं (उदाहरण के लिए, 0x00, 0x00, 0xff, 0xff) ; हैडर में यह संकेत मिलता है कि हमने कितने बाइट्स काटे;
हम 32Kb पृष्ठों में डेटा स्टोर करते हैं; पृष्ठ के अंदर संपीड़ित डेटा की एक एकल धारा है; प्रत्येक पृष्ठ पर, हम फिर से संपीड़न शुरू करते हैं।

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

डेटा हेडर्स को स्टोर करना

चूँकि हमारे पास परिवर्तनीय लंबाई के रिकॉर्ड हैं, इसलिए हमें किसी तरह अभिलेखों के स्थान / सीमाओं को निर्धारित करना होगा।

मैं तीन दृष्टिकोण जानता हूं:

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

मैं दृष्टांत दूंगा।

विकल्प 1:

यहां सब कुछ बहुत सरल है: रिकॉर्ड की लंबाई जानने के बाद, हम अगले हेडर के पते की गणना कर सकते हैं। इसलिए हम हेडर के माध्यम से चलते हैं जब तक कि हम 0xff (मुक्त क्षेत्र) या पृष्ठ के अंत से भरे क्षेत्र को पूरा नहीं करते।

विकल्प 2:

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

विकल्प 3:

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

तुलना तालिका:

	विकल्प 1	विकल्प 2	विकल्प 3
सहनशीलता में त्रुटि	-	+	+
घनत्व	+	-	+
कार्यान्वयन की जटिलता	*	**	**

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

कॉम्पैक्ट:

पहले संस्करण में, हमें हेडर में केवल लंबाई को संग्रहीत करने की आवश्यकता है, यदि चर लंबाई के पूर्णांक का उपयोग किया जाता है, तो ज्यादातर मामलों में हम एक बाइट के साथ कर सकते हैं;
दूसरे विकल्प में, हमें शुरुआती पता और लंबाई संग्रहीत करने की आवश्यकता है; रिकॉर्ड एक स्थिर आकार होना चाहिए, मुझे लगता है कि प्रति रिकॉर्ड 4 बाइट्स (दो बाइट्स प्रति ऑफसेट और दो बाइट्स प्रति लंबाई);
, - 1-2%. .

( ). , .

, - - . , , — , , ...

: , , .. , , , — , .

: " — " - .

, , :
.
, erase 1, 1 0, . " " 1, " " — 0.

flash:

“ ”;
;
“ ”;
;
“ ”.

, “ ”, 4 .

“1111” — “1000” — ; , .

, , , , , ( ) .

: .

( ) , . , , .

, , ( , , — ) .

, , , — .

— CRC. , 100% , — $2^{-n}$ । , , : , . — .

: 1 , 2 ( narod.ru, ) .

, CRC — . , .

, .

:
$10^{-3}$ , :

,	,
1	0	1000	0	1000
1	1	4	999	1003
1	2	≈0	1997	1997
1	4	≈0	3990	3990
10	0	9955	0	9955
10	1	39	990	1029
10	2	≈0	1979	1979
10	4	≈0	3954	3954
1000	0	632305	0	632305
1000	1	2470	368	2838
1000	2	10	735	745
1000	4	≈0	1469	1469

, — — .

, : , , . , .

, , 32 ( 64 -) .

, , , - 32- (16 , 0.01%; 24 , , ).

: , 4 ? ? , , .

, CRC-32C.
6 22 (, c), 4 655 ( ), 2 .

CRC.

crc-32c — , CRC .

, , , , .

, , : ?

"" :

— ( /, , ..);
deflate zlib "" , , , ( , zlib ).

"" :

CRC "" , - ( , , , "" );
, , .

: CRC-32C, , flash ( ).

, , , , ( ) .

, .
, - , RAID-6 .
, , , .

, . ?

( - , Raspberry, ...)
, ;
( - flash- , )
, ;
;
.

( ) . , - .

: , , , ( , ).

, ( ) , , .

""
- , .., , .
, , ;
.
— !
Magic Number (), ( , ) ;
( ) , 1 ;
.

- . .

Byte order

, , big-endian (network byte order), 0x1234 0x12, 0x34.

- .

32, , 1/4 ( 4 128 ).

( ).

( ), 0 ( 0, — 32, — 64 ..)

(ring buffer), 0, 1, ..., , .

पेज
4- , (CRC-32C), ", , ".

( -) :

Magic Number ( — )
0xed00 ⊕ ;
" " ( ).

( deflate). ( ), . ( ).

Z_SYNC_FLUSH, 4 0x00, 0x00, 0xff, 0xff, , , .
( 4, 5 6 ) -.

1, 2 3 , :

(T), : 0 — , 1 — ;
(S) 1 7 , "", ;
(L).

S	,	,
`0`	1	5 ( `00 00 00 ff ff` )
`10`	1	6 ( `00 00 00 00 ff ff` )
`110`	2	4 ( `00 00 ff ff` )
`1110`	2	5 ( `00 00 00 ff ff` )
`11110`	2	6 ( `00 00 00 00 ff ff` )
`1111100`	3	4 ( `00 00 ff ff` )
`1111101`	3	5 ( `00 00 00 ff ff` )
`1111110`	3	6 ( `00 00 00 00 ff ff` )

, , :
शीर्षक प्रविष्टि
T, — S, L ( ), — , — , -.

, ( 63+5 ) .

CRC-32C, (init) .

CRC "", (- ) : $CRC(init, A || B) = CRC(CRC(init, A), B)$ .
CRC .

, 0x00 0xff ( 0xff, ; 0x00 ).

-

.
— - .

( , Linux NOR Flash, )

-

.
.

— .

( ) 1.
( UUID ).

, - .

8 ( + CRC), Magic Number CRC .
"" , , .
, CRC, "". — . — , "" .
, , "" .
zlib ( ).

, , , .

, Z_SYNC_FLUSH., .
( CRC) — (. ).
CRC. — .

( ). — , .
erase. 0xff. - — , ..
, , — ( ).

, - ( , JSON, MessagePack, CBOR, , protobuf) NOR Flash.

, "" SLC NOR Flash.

BER, NAND MLC NOR ( ? ) .

, , FTL: USB flash, SD, MicroSD, etc ( 512 , — "" ) .

128 (16) 1 (128). , , , ( , NOR Flash ) .

- , — , , github.

निष्कर्ष

, .

, : - , , . , () - .

, ? , . , , . - .

? , , . .

, , " ".

, () , , "" (, , ; ). ( — ) .

, .

साहित्य

, .

, , , :

infgen zlib. deflate/zlib/gzip. deflate ( gzip) — .

NOR फ्लैश में मेरा रिंग बफर कार्यान्वयन