DGFS - फास्ट DIY फाइल सिस्टम

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



एक राय है कि एक विशेष रीड-ओनली फाइल सिस्टम, अन्य सभी चीजें समान होने के कारण, सामान्य उद्देश्यों के लिए इस पर लाभ होता है क्योंकि:

1. मुक्त स्थान का प्रबंधन करना आवश्यक नहीं है;
2. जर्नलिंग पर पैसा खर्च करने की आवश्यकता नहीं है;
3. आप विखंडन के बारे में चिंता नहीं कर सकते हैं और लगातार फाइलों को स्टोर कर सकते हैं;
4. सभी मेटा-जानकारी को एक स्थान पर एकत्र करना और इसे प्रभावी ढंग से कैश करना संभव है;
5. मेटा-जानकारी को संपीड़ित न करना एक पाप है, क्योंकि यह एक ढेर में था।

इस लेख में, हम समझेंगे कि आप न्यूनतम लागत पर अधिकतम उद्देश्य के साथ एक फाइल सिस्टम कैसे व्यवस्थित कर सकते हैं।

कार्य

1. 100 मिलियन छोटी फाइलें (~ 8K प्रत्येक)।
2. तीन-स्तरीय पदानुक्रम - 100 शीर्ष-स्तरीय निर्देशिकाएं, जिनमें से प्रत्येक में 100 मध्य-स्तरीय निर्देशिकाएं हैं, जिनमें से प्रत्येक में 100 निम्न-स्तरीय निर्देशिकाएं हैं, जिनमें से प्रत्येक में 100 फाइलें हैं।
3. हम एक यादृच्छिक फ़ाइल के निर्माण समय और औसत पढ़ने के समय का अनुकूलन करते हैं।

लोहा

सबसे पहले, डिस्क: सभी प्रयोग एक समर्पित 1 टीबी सीगेट बाराकुडा ST31000340NS पर किए जाते हैं।
ऑपरेटिंग सिस्टम विंडोज एक्सपी है।
प्रोसेसर: AMD Athlon II X3 445 3 GHz।
मेमोरी: 4 जीबी।

डिस्क विनिर्देशों

मूल काम शुरू करने से पहले, मैं समझना चाहता हूं कि डिस्क से क्या उम्मीद की जा सकती है। इसलिए, डिस्क से यादृच्छिक स्थिति और रीडिंग के लिए माप की एक श्रृंखला ली गई थी।



नीचे दिए गए ग्राफ में मनमानी स्थितियों में डिस्क से रीड टाइम के हिस्टोग्राम दिखाए गए हैं। अनुपस्थिति स्थिति और पढ़ने की अवधि को दर्शाता है। Y- अक्ष पर - एक टोकरी में हिट की संख्या 0.1 मिसे चौड़ा।

डिस्क एक्सेस नियमित रूप से किए गए थे:

• CreateFile ("\\\\। \\ PhysicalDrive1" ...) के माध्यम से खुल रहा है;
• SetFilePointer के माध्यम से स्थिति;
• और ReadFile के माध्यम से पढ़ना।

माप की कई श्रृंखलाएं बनाई गईं, प्रत्येक श्रृंखला में 10,000। प्रत्येक श्रृंखला अपने रंग से चिह्नित होती है:

• सभी - स्थिति डिस्क पर सभी जाती है;
• Its - केवल इसके छोटे आधे में, आदि।

और यहाँ चटाई दिखाई जाती है। पिछले ग्राफ से अपेक्षाएं और त्रुटियां, लघुगणकीय पैमाने में एब्सिस्सा अक्ष, उदाहरण के लिए, 1/16 4 (1/2 1/2) से मेल खाती है।

क्या निष्कर्ष निकाला जा सकता है?

1. सबसे खराब स्थिति में (यादृच्छिक खोज), एक एकल रीड की उम्मीद 13 मिसे है। यही है, इस डिस्क से प्रति सेकंड 80 से अधिक यादृच्छिक रीड नहीं किए जा सकते हैं।
2. 1/256 पर, हम पहली बार कैश में हिट देखते हैं।
3. 1/1024 पर, एक मूर्त संख्या पढ़ी जाती है ~ 1% कैश में प्राप्त होने लगती है।
4. 1/256 से अधिक 1/1024 से भिन्न नहीं होता है, सिर का भाग पहले से बहुत छोटा है, हम केवल उनके त्वरण को देखते हैं और (अधिकतर) शांत होते हैं।
5. हमारे पास स्केल करने की क्षमता है, अर्थात यह आंशिक रूप से भरी हुई डिस्क पर प्रयोगों का संचालन करने की अनुमति है और इसके बजाय परिणामों को आत्मविश्वास से बढ़ाता है।

NTFS

आइए एक फ़ाइल को डिस्क के आकार बनाने की कोशिश करें और इसके साथ काम करने की समय विशेषताओं को प्राप्त करें। ऐसा करने के लिए, फ़ाइल सिस्टम साइज़ के साथ एक फाइल कम्प्रेशर बनाएं और इसे रेगुलर जगहों में रेगुलर _fseeki64 / Fread के साथ पढ़ें।



ग्राफ पहले प्रस्तुत हिस्टोग्राम के समान है। और उनमें से दो, (डिस्क) के रूप में चिह्नित हैं, पिछले चार्ट से लिए गए हैं। फ़ाइल रीडिंग के माप के आधार पर (फ़ाइल) के रूप में चिह्नित युग्मित हिस्टोग्राम प्राप्त किए गए थे। क्या नोट किया जा सकता है:

1. टाइम्स के पास हैं।
2. हालाँकि फ़ाइल फ़ाइल सिस्टम (9xE11 बाइट्स) का 90% है, लेकिन इसे पूर्ण आकार से पढ़ना औसतन लगभग एक मिलीसेकंड धीमा है।
3. किसी फ़ाइल के लिए डिस्क कैश डिस्क से बेहतर काम करता है।
4. ~ 6 मिसेक में पूंछ थीं, यदि पूर्ण पढ़ने का सबसे खराब समय 24 मिसेक था, अब यह लगभग 30 तक फैला हुआ है। इसी तरह, 1/256 के लिए। जाहिरा तौर पर, मेटाडेटा कैश से बाहर हो गया और आपको इसे अतिरिक्त रूप से पढ़ना होगा।
5. लेकिन सामान्य तौर पर, एक बड़ी फ़ाइल से पढ़ना नंगे डिस्क के साथ काम करने के समान ही काम करता है और कुछ मामलों में इसे प्रतिस्थापित या अनुकरण कर सकता है। यह NTFS का सम्मान करता है, जैसा कि उदाहरण के लिए, ext2 / ext3 संरचना को फ़ाइल के लिए प्रत्येक 4-Kb डेटा ब्लॉक के लिए न्यूनतम 4 बाइट्स की आवश्यकता होती है:
   
   
   

यही है, प्रत्येक किलोबाइट डेटा के लिए एक अतिरिक्त बाइट खर्च करना आवश्यक है, एक गीगाबाइट प्रति टेराबाइट से बाहर आता है, और एक गीगाबाइट को कैशिंग करना इतना सरल नहीं है। हालाँकि, ext4 में स्पष्ट रूप से ऐसी कोई समस्या नहीं है, या यह extents के साथ मुखौटा है।

पदानुक्रम के साथ NTFS

आइए हम अपनी परीक्षण समस्या को याद करते हैं और फ़ाइल सिस्टम का उपयोग करके इसे सिर पर हल करने का प्रयास करते हैं। यह तुरंत पता चला है कि:

1. यह काफी समय लेता है, एक लाख फ़ाइलों में से एक शाखा बनाने में लगभग आधे घंटे लगते हैं, धीरे-धीरे धीमा होने की प्रवृत्ति के साथ क्योंकि डिस्क हमारे पहले शेड्यूल के अनुसार पूर्ण हो जाती है।
2. इसलिए सभी 100 मिलियन फाइलों को बनाने में 50+ घंटे लगते हैं।
3. इसलिए, हम 7 मिलियन फाइलों (~ 1/16) और पूर्ण कार्य के पैमाने पर माप लेंगे।
4. मुकाबला करने के लिए अधिक करीबी परिस्थितियों में माप लेने का प्रयास इस तथ्य के कारण हुआ कि एनटीएफएस लगभग 12 मिलियन फाइलों में दुर्घटनाग्रस्त हो गया, जिसमें लगभग एक ही डायग्नोस्टिक्स फिल्म में मुख्य चरित्र "उसके चेहरे की मौत" थी: - "वास्तव में, खंडित ग्रीवा कशेरुका एक बहुत, बहुत बुरा संकेत है! "

सबसे पहले, मिलीसेकंड में हिस्टोग्राम पर विचार करें:



तो, यहाँ यादृच्छिक फ़ाइलों के पढ़ने के समय का एक हिस्टोग्राम है।

• दो श्रृंखला - कार्य के 1/16 के रूप में 7 मिलियन और अंशांकन के लिए 1 मिलियन।
• 10000 माप की एक श्रृंखला में, टोकरी 0.5 मिसे में।
• 1/16 परीक्षण का कुल समय 7'13 '' है, यानी उम्मीद 43 मिसे है।
• 1/100 परीक्षण का कुल समय 5'20 '' है, यानी उम्मीद 32 मिसे है।

अब चलो सशर्त तलाश की इकाइयों में एक ही देखें:

• 1/16, कि 1/100, किसी भी तरह कैश्ड होने के लिए बहुत बड़े हैं। और विखंडन के लिए हमारी फाइलें बहुत छोटी हैं।
• इसलिए, 1 तलाश, हमें वास्तविक डेटा पढ़ने के लिए भुगतान करना होगा। बाकी सब कुछ फाइल सिस्टम का आंतरिक मामला है।
• मैक्सिमम 3.5 (1/100 के लिए) और 4 (1/16) के लिए होते हैं।
• और अपेक्षा आम तौर पर 4 ... 5 है।
• अर्थात्, फ़ाइल कहाँ संग्रहीत है, इसके बारे में जानकारी प्राप्त करने के लिए, फ़ाइल सिस्टम (NTFS) को 3-4 रीडिंग करनी होती हैं। और कभी-कभी 10 से अधिक।
• एक पूर्ण कार्य के मामले में, संभवतः, स्थिति में सुधार नहीं होगा।

प्रोटोटाइप

आइए हमारी रीड-ओनली फाइल सिस्टम के एक प्रोटोटाइप का निर्माण करें:

1. इसमें दो फाइलें होती हैं - डेटा और मेटाडेटा।
2. डेटा फ़ाइल - पंक्ति में लिखी गई सभी फाइलें।
3. मेटाडेटा फ़ाइल - कुंजी-फ़ाइल पहचानकर्ता के साथ इन-ट्री। मान डेटा फ़ाइल और उसके आकार का पता है।
4. एक फ़ाइल पहचानकर्ता इसके लिए एक एन्कोडेड पथ है। याद रखें कि हमारा डेटा तीन-स्तरीय निर्देशिका प्रणाली में स्थित है, जहां प्रत्येक स्तर 0 से 100 तक की संख्या के साथ एन्कोड किया गया है, फ़ाइल स्वयं समान है। यह पूरी संरचना पूर्णांक में पैक की गई है।
5. पेड़ को 4K पृष्ठों के रूप में लिखा गया है, आदिम संपीड़न लागू किया जाता है।
6. विखंडन से बचने के लिए, इन फ़ाइलों को अलग-अलग फ़ाइल सिस्टम में बनाया जाना चाहिए।
7. फ़ाइल के अंत में डेटा जोड़ना (डेटा) अक्षम है। फ़ाइल जितनी बड़ी होगी, फ़ाइल सिस्टम उतना ही महंगा (NTFS, WinXP) इसका विस्तार है। इस गैर-रैखिकता से बचने के लिए, आपको पहले वांछित आकार (900 जीबी) की एक फ़ाइल बनानी होगी।
8. इस प्रारंभिक रचना में 2 घंटे से अधिक का समय लगता है, इस बार यह फ़ाइल शून्य से, जाहिरा तौर पर, सुरक्षा कारणों से भरने में लगती है।
9. इस फ़ाइल को डेटा के साथ भरने में उतना ही समय लगता है।
10. एक इंडेक्स के निर्माण में लगभग 2 मिनट लगते हैं।
11. कुल 100 मिलियन फाइलों को याद करें, प्रत्येक आकार में लगभग 8K है।
12. इंडेक्स फाइल 521 एमबी की है। या ~ 5 बाइट्स प्रति फ़ाइल। या ~ 5 बिट प्रति किलोबाइट डेटा।
13. अधिक जटिल संपीड़न (हफ़मैन कोड) के साथ सूचकांक का एक प्रकार भी परीक्षण किया गया था। इस सूचकांक में 325 एमबी है। या 3 बिट प्रति किलोबाइट डेटा।

इस डेटा पर प्राप्त समय के हिस्टोग्राम्स निम्नलिखित हैं:

• "अकेला" - इस लेबल के तहत एक डेटा फ़ाइल एक अलग भौतिक डिस्क पर इंडेक्स फ़ाइल से अलग स्थित है;
• "ओगेथेर" - डेटा फ़ाइल और इंडेक्स दोनों एक ही भौतिक डिस्क पर एक ही फाइल सिस्टम के भीतर स्थित हैं;
• "केवल सूचकांक" - केवल वास्तविक डेटा को पढ़े बिना सूचकांक में फ़ाइल के बारे में जानकारी के लिए खोज करें;
• “के साथ। सूचकांक "- समान रूप से" एक साथ ", लेकिन एक संपीड़ित सूचकांक के साथ;
• «Compr। केवल सूचकांक - "केवल सूचकांक" के रूप में ही, लेकिन एक संपीड़ित सूचकांक के साथ;
• कुल 10,000 रीड्स, 0.1 मिसे का हिस्टोग्राम स्टेप।

निष्कर्ष:

1. सूचकांक की संपीड़न गुणवत्ता लगभग गति को प्रभावित नहीं करती है। पृष्ठों को संपीड़ित करने में CPU समय लगता है, लेकिन पेज कैश बेहतर काम करता है।
2. इंडेक्स को पढ़ना उचित आकार की फ़ाइल से एक रीडिंग जैसा दिखता है (पहला ग्राफ़ देखें)। चूंकि 512 एमबी डिस्क का 1/2000 है, औसत तलाश का समय लगभग 6.5 मिसेक होना चाहिए, साथ ही जो हम फाइल से पढ़ते हैं उसके लिए प्रीमियम, और डिस्क से सीधे नहीं। जाहिर है, यह बात है। इंडेक्स ट्री तीन-स्तरीय है, शीर्ष दो स्तर बहुत जल्दी कैश हो जाते हैं, और यह पृष्ठों के निचले स्तर को कैश करने के लिए व्यर्थ है। नतीजतन, एक पेड़ में कोई भी खोज पत्ती पृष्ठ के एक ही पढ़ने में पतित हो जाती है।
3. यदि डेटा फ़ाइल और इंडेक्स फ़ाइल एक ही भौतिक डिस्क पर स्थित हैं, तो कुल खोज का समय पूर्ण दूरी के लिए दो यादृच्छिक खोज के बराबर है। एक डेटा पढ़ने के लिए और एक इंडेक्स फ़ाइल पर जाने के लिए, जो या तो शुरुआत में या डिस्क के बहुत अंत में स्थित है।
4. यदि फ़ाइलों को विभिन्न उपकरणों में वितरित किया जाता है, तो हमारे पास डेटा पढ़ने के लिए एक पूर्ण और सूचकांक में खोज के लिए एक छोटी सी तलाश है। यह देखते हुए कि इंडेक्स फ़ाइल अपेक्षाकृत छोटा है, एक प्राकृतिक समाधान खुद ही बताता है - अगर हमें कई (दसियों) टेराबाइट्स के भंडारण की आवश्यकता है, तो हमें इंडेक्स (एसएसडी) के लिए एक समर्पित ड्राइव और डेटा के लिए कई ड्राइव तैयार करने की आवश्यकता है। इसे JBOD के रूप में स्टाइल किया जा सकता है और यह एक नियमित फाइल सिस्टम की तरह दिखता है।
5. इस योजना की एक महत्वपूर्ण विशेषता है - प्रतिक्रिया समय की गारंटी, जो पारंपरिक फ़ाइल सिस्टम में हासिल करना मुश्किल है, उदाहरण के लिए, वास्तविक समय प्रणाली में उपयोग के लिए।

यहां पूछने का समय है - ठीक है, ठीक है, हमने एक नियमित रूप से व्यवस्थित फ़ाइल सिस्टम का एक बहुत ही विशेष मामला बनाया है (निर्धारित नामों के साथ तीन स्तर)। लेकिन सामान्य डेटा, सामान्य रास्तों और नामों के बारे में क्या?

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

ऊपर, फ़ाइल पहचानकर्ता (सूचकांक कुंजी) इसके लिए एन्कोडेड पथ था। तो यह होगा, कुंजी फ़ाइल के लिए स्ट्रिंग पूर्ण पथ है। अर्थ में बाकी सब कुछ - आकार, स्थिति, स्वामी, समूह, अधिकार ...

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

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

लेकिन क्या फ़ाइल पथ बहुत सारे स्थान लेते हैं? हां, लेकिन एक ही निर्देशिका में फ़ाइलों में एक सामान्य उपसर्ग होता है जिसे केवल एक बार संग्रहीत किया जा सकता है। एक सामान्य प्रत्यय भी आम है। संग्रहीत किए जाने वाले डेटा की मात्रा को समझने के लिए, फ़ाइल सिस्टम पथों के साथ प्रयोगों की एक श्रृंखला की गई, जिसमें दिखाया गया कि वे bzip2 (BWT + प्रत्यय सॉर्ट + हफ़मैन) का उपयोग करके औसत 10 बार संकुचित होते हैं। यह प्रति फ़ाइल 5-6 बाइट्स छोड़ता है।

कुल में, आप प्रति फ़ाइल 10-16 बाइट्स, या ~ 2 बाइट्स प्रति किलोबाइट डेटा (यदि औसत फ़ाइल 8K है) पर भरोसा कर सकते हैं। एक टेराबाइट फ़ाइल के लिए 2 गीगाबाइट इंडेक्स की आवश्यकता होती है, एक नियमित 64-गीगाबाइट एसएसडी-ड्राइव, इसलिए, 32 टेराबाइट डेटा की सेवा करने में सक्षम है।

एनालॉग

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

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

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

लेन-देन संबंधी

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

कुल मिलाकर

तो, प्रोटोटाइप रीड-ओनली फाइल सिस्टम प्रस्तुत किया गया है, जो सरल, लचीला है, परीक्षण समस्या को हल करता है और उसी समय:

• इसके लिए आवंटित हार्डवेयर पर अधिकतम संभव प्रदर्शन प्रदर्शित करता है;
• इसकी वास्तुकला डेटा की मात्रा पर उद्देश्य प्रतिबंध नहीं लगाती है;
• यह स्पष्ट करता है कि सामान्य-उद्देश्य वाली फ़ाइल प्रणाली प्राप्त करने के लिए क्या करना है, न कि किसी विशिष्ट कार्य के लिए बनाया गया शौक
• यह स्पष्ट करता है कि हमारी फाइल सिस्टम को किस तरह से परिवर्तनशील बनाया जा सकता है।