एक बड़ी बाइनरी फ़ाइल

Question

की यादृच्छिक पहुंच मेरे पास एक बड़ी बाइनरी फ़ाइल (12   जीबी) है जिसमें से मैं फ्लाई पर एक छोटी बाइनरी फ़ाइल (16   केबी) इकट्ठा करना चाहता हूं। मान लें कि फ़ाइल डिस्क पर है, और छोटी फ़ाइल के लिए बाइट्स कुछ हद तक यादृच्छिक रूप से बड़ी बाइनरी फ़ाइल में वितरित की जाती हैं। ऐसा करने का सबसे अच्छा और तेज़ तरीका क्या है? अब तक मैं लगभग तीन मिनट से बेहतर करने में सक्षम नहीं हूं।

बातें मैं कोशिश की है, जो लगभग समान ही प्रदर्शन किया है:

1. HDF5 प्रारूप करने के लिए फ़ाइल कनवर्ट कर और सी इंटरफ़ेस का उपयोग कर (धीमा)।
2. फ़ाइल (धीमी) के माध्यम से fseek() को एक छोटा सी प्रोग्राम लिखना।

मैं कैसे बेतरतीब ढंग से वास्तव में इस डेटा का उपयोग कर सकते हैं तेजी?

मैं क्वेरी के लिए कुछ सेकंड से कम समय प्राप्त करना चाहता हूं।

Answer 1

उत्तर मूल रूप से "नहीं" है।

एक एकल यांत्रिक डिस्क ड्राइव 10   एमएस लेने के लिए जा रही है या इसलिए एक खोज करने के लिए, क्योंकि इसे डिस्क हेड को स्थानांतरित करना है। 16000 प्रति सेकंड 10 मिलीसेकंड मांगता है जो 160 सेकंड के बराबर होता है। यह बिल्कुल कोई फर्क नहीं पड़ता कि आप अपना कोड कैसे लिखते हैं; जैसे mmap() कोई फर्क नहीं पड़ता है।

भौतिक दुनिया, सॉफ्टवेयर व्यक्ति :-) में आपका स्वागत है। आपको अपने परिचालनों के इलाके में सुधार करना होगा।

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

अगला, आपकी डिस्क शायद लगभग 100 मेगाबाइट/सेकेंड पर अनुक्रमिक डेटा पढ़ सकती है; यानी, यह एक मेगाबाइट अनुक्रमिक रूप से लगभग एक ही समय में एक खोज करने के लिए ले सकता है। तो यदि आपके दो मूल्य 1 मेगाबाइट से कम हैं, तो आप उनके बीच की खोज करने से के बीच के सभी डेटा पढ़ने से बेहतर हैं। (लेकिन अपने हार्डवेयर पर इष्टतम व्यापार-बंद खोजने के लिए इसे बेंचमार्क करें।)

अंत में, RAID थ्रूपुट (लेकिन समय की तलाश नहीं कर सकती) के साथ मदद कर सकती है। यह एकाधिक डिस्क हेड भी प्रदान कर सकता है जो एक साथ खोज सकते हैं यदि आप अपने पठन कोड को बहु-थ्रेड करना चाहते हैं।

लेकिन सामान्य रूप से, यादृच्छिक डेटा तक पहुंचने से आप अपने कंप्यूटर से मेमोरी या डिस्क में सबसे बुरी चीज के बारे में पूछ सकते हैं। और अनुक्रमिक पहुंच और यादृच्छिक अभिगम के बीच सापेक्ष अंतर हर साल बढ़ता है क्योंकि भौतिकी स्थानीय है। (ठीक है, भौतिक विज्ञान हम यहाँ पर निर्भर करते हैं, वैसे भी।)

[संपादित करें]

@JeremyP's suggestion SSDs के उपयोग करने के लिए एक अच्छा एक है। यदि वे एक विकल्प हैं, तो उनके पास 0.1   एमएस या तो प्रभावी समय है। मतलब आप इस तरह के हार्डवेयर पर 50-100 गुना तेजी से चलाने के लिए अपने कोड की उम्मीद कर सकते हैं। (मैं इस के बारे में सोच नहीं था क्योंकि मैं आम तौर पर 1   टीबी रेंज में फ़ाइलों जहां SSDs के भी महंगा हो सकता है के साथ काम करते हैं।)

[संपादित करें 2]

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

Answer 2

मुझे लगता है कि यह इस बात पर निर्भर करता है कि आपको कितने प्रयास करना है। 16 हजार, या एक छोटी संख्या? क्या आप एक ठोस राज्य ड्राइव पर 12   जीबी फ़ाइल स्टोर कर सकते हैं? वह तलाश लेटेंसी पर कटौती करेगा।

क्या आप फ़ाइल को तोड़ सकते हैं और टुकड़े अलग हार्ड ड्राइव पर स्टोर कर सकते हैं? जो समानांतर में एसिंक्रोनस की तलाश को सक्षम करेगा।

Answer 3

क्या आपने फ़ाइल को mmaping करने का प्रयास किया है? (आपके मामले में, mmap64)। जब आप इसे एक्सेस करते हैं तो डिस्क से डेटा आलसी-पढ़ा जाएगा।

यदि आप जिस डेटा को ढूंढ रहे हैं उसे ढूंढने के लिए आपको पूरी फाइल को देखना है, तो आप इसे एसएसडी के साथ तेज करने में सक्षम होंगे, लेकिन यह हमेशा धीमा होने वाला है। क्या आप जिस डेटा को खोज रहे हैं, वह समय से पहले ज्ञात है?

क्या फ़ाइल एक टेक्स्ट फ़ाइल है, या एक बाइनरी फ़ाइल है?

Answer 4

यदि आपको पूरी फ़ाइल को पढ़ना है और आप एक यांत्रिक हार्ड डिस्क का उपयोग कर रहे हैं, तो आप खराब हो गए हैं। मान लें कि स्थानांतरण दर लगभग 1 Gigabit/second है, जिसका अर्थ है कि आप भौतिक रूप से 12 x 8 = 96 सेकंड से कम समय में बस में सभी बिट्स नहीं प्राप्त कर सकते हैं। ऐसा लगता है कि कोई तलाश समय नहीं है और प्रोसेसर डेटा के साथ सौदा कर सकता है।

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

आप एक एसएसडी आप शायद नाटकीय रूप से इस पर सुधार कर सकते हैं, कोई प्रतीक्षा नहीं है के बाद से बाइट्स सिर के नीचे दौर आने के लिए ...

Answer 5

कुछ संकेत पढ़ने एक छोटे से फ़ाइलें (speedup करने के लिए है, तो क्या पहले से ही था के अलावा कहा गया): - ब्लॉक के गुणा आकार के टुकड़े पढ़ें - POSIX अनुपालन प्रणाली पर posix_fadvise() का उपयोग करें, जो ओएस को पेजिंग के बारे में सलाह देता है।

Answer 6

ठीक है, इस गति के लिए आप जिस गति को प्राप्त कर सकते हैं वह 96   केबी निकालने के लिए आपके द्वारा किए जाने वाले पढ़ने वाले कार्यों की कुल संख्या पर निर्भर करता है जो आपकी नई फ़ाइल के लिए पेलोड बनाते हैं।

ऐसा क्यों है? क्योंकि (कताई) डिस्क से यादृच्छिक पढ़ना चाहते हैं; चुंबकीय सिर को फिर से स्थापित करने के समय की तुलना में पढ़ा जाता है (लगभग) असीम रूप से तेज़।

चूंकि आप कह रहे हैं कि एक्सेस पैटर्न यादृच्छिक है, तो आपको किसी भी रीडहेड से लाभ होने की भी संभावना नहीं है कि ऑपरेटिंग सिस्टम उपयोग करने का निर्णय ले सकता है; यदि आप चुनते हैं, तो आप बड़ी फ़ाइल के लिए दायरस्क्रिप्टर पर fadvise(fd, 0, MAX_OFFSET, FADV_RANDOM); के माध्यम से इसे बंद कर सकते हैं। या, madvise() यदि आपने mmap() पर चुना है। लेकिन अगर आप बड़े पढ़ रहे हैं तो आपको केवल तभी लाभ मिलेगा (और आप जानते हैं कि एक बड़ा रीडहेड बकवास होगा)। छोटे पढ़ने के लिए, यह विशेष रूप से खोज समय है जो कुल निर्धारित करेगा।

मान लिया जाये कि आप की जरूरत N यादृच्छिक पढ़ता है और आप मिल गया है एक M msec समय की तलाश है, यह कम से कम N * m मिलीसेकेंड ले लेंगे डेटा निष्कर्षण प्रदर्शन करने के लिए (यदि आप अपने आप को करने के लिए डिस्क मिल गया है ...)। इस बाधा को तोड़ने का कोई रास्ता नहीं है।

संपादित करें: कम करने की रणनीतियों पर कुछ बातें:

कई लोगों ने उल्लेख किया है, कुंजी इस समस्या दृष्टिकोण को कम करने का प्रयास है। इसके लिए कई रणनीतियों रहे हैं:

1. अंक अतुल्यकालिक पढ़ता है अगर तुम (अर्थात, अगर पढ़ आपरेशन N+1 क्या आपरेशन N पढ़ा है, तो आप दोनों साथ-साथ जारी कर सकते हैं पर निर्भर नहीं करता) कर सकते हैं। यह ऑपरेटिंग सिस्टम/डिवाइस ड्राइवर को कतारबद्ध करने की अनुमति देता है और संभावित रूप से उन्हें फिर से ऑर्डर करने की अनुमति देता है (या उन्हें अन्य समवर्ती चल रही प्रक्रियाओं द्वारा किए गए पाठों के साथ मर्ज करें)।
2. यदि आप पहले से ही सभी पदों को जानते हैं, तो उसी प्रभाव के लिए स्कैटर-इकट्ठा I/O (संयुक्त राष्ट्र * एक्स preadv() दिमाग में आ जाएगा) प्रदर्शन करें।
3. सर्वोत्तम/न्यूनतम अवरोध के लिए अपने फाइल सिस्टम और/या ब्लॉक डिवाइस को क्वेरी करें; यह कैसे करें सिस्टम-निर्भर है, उदाहरण देखें statvfs() या यहां तक ​​कि ioctl_list। यदि आप जानते हैं, तो संभवतः आप निमो द्वारा वर्णित तकनीक का उपयोग कर सकते हैं ("इष्टतम" ब्लॉक आकार के भीतर दो छोटे पढ़ने को एक बड़े पढ़ने में मिलाएं, कोई तलाश नहीं चाहिए)।
4. संभवतः भी क्वेरी इंटरफेस का उपयोग की तरह FIEMAP/FIBMAP (विंडोज बराबर मोटे तौर पर FSCTL_GET_RETRIEVAL_POINTERS होगा) निर्धारित करने के लिए जहां अपनी फ़ाइल डेटा के लिए शारीरिक ब्लॉक हैं, और पढ़ने पर कोई फैसला प्रदर्शन पर आधारित है कि विलय (वहाँ एक बड़ी जारी करने कोई मतलब नहीं है "nonseeking" पढ़ा जाता है अगर वास्तव में एक भौतिक ब्लॉक सीमा पार करता है और फाइल सिस्टम इसे दो में बदल देता है)।
5. यदि आप तुलनात्मक रूप से बड़े समय से पढ़ने के लिए पदों का निर्माण करते हैं, तो पढ़ना (असीमित रूप से) जैसा कि आप अभी भी भविष्य में पढ़ने वाले ऑफसेट की गणना करते हैं, वैसे भी विलंब विलंब को छिपाने में मदद मिलेगी, क्योंकि आप गणना चक्र/अच्छे समय के लिए प्रतीक्षा कर रहे हैं उपयोग।

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

Answer 7

समांतर या असीमित पढ़ने का उपयोग करें। फ्रैंकएच ने कहा, उन्हें आवश्यकतानुसार एकाधिक धागे, प्रक्रियाओं आदि से जारी करें, या प्रीडव का उपयोग करें।

इसका मतलब है कि आपको एक I/O अनुरोध के साथ आने के पहले इंतजार नहीं करना पड़ेगा, जो आपके पास एक चतुर RAID नियंत्रक और कई स्पिंडल होने पर प्रदर्शन में सुधार करने जा रहा है।

दूसरी ओर, यदि आपके पास वास्तव में बेवकूफ I/O सबसिस्टम है, तो यह केवल मामूली अंतर कर सकता है। उपयोग करने के लिए I/O scheduler पर विचार करें (आप उन्हें रीबूट के बिना फ्लाई पर बदल सकते हैं, जो वास्तव में अच्छा है)। यदि आपके पास बेवकूफ हार्डवेयर है तो अचूक सबूत बताते हैं कि "नोप" सबसे अच्छा है यदि आपके पास "स्मार्ट" हार्डवेयर, सीएफक्यू या समय सीमा है।