👨🏻‍🎨 👨🏿‍🏭 🐊 ClickHouse में LZ4 के अनलोडिंग को कैसे तेज करें 🏾 👩🏼‍🤝‍👨🏻 💨

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

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

सवाल यह है - LZ4 अनलोडिंग एक अड़चन क्यों हो सकती है? ऐसा लगता है कि LZ4 एक बहुत ही हल्का एल्गोरिथ्म है : डेटा के आधार पर संपीड़न दर, आमतौर पर 1 से 3 जीबी / एस प्रति प्रोसेसर कोर तक होती है। यह डिस्क सबसिस्टम की गति से काफी अधिक है। इसके अलावा, हम सभी उपलब्ध गुठली का उपयोग करते हैं, और विस्तार सभी भौतिक गुठली में रैखिक रूप से होता है।

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

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

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

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

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

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

क्यों LZ4?

LZ4 का उपयोग क्यों किया जाता है? क्या कुछ आसान भी चुनना संभव है? सिद्धांत रूप में, यह संभव है, और यह सही और उपयोगी है। लेकिन आइए पहले देखें कि एलजेड 4 एल एल्गोरिदम किस वर्ग से संबंधित है।

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

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

एक अन्य प्रश्न: LZ4 गति और संपीड़न बल के संयोजन के लिए इस वर्ग का सबसे इष्टतम एल्गोरिथ्म है? ऐसे एल्गोरिदम को पेरेटो फ्रंटियर कहा जाता है - इसका मतलब है कि कोई अन्य एल्गोरिदम नहीं है जो कड़ाई से एक संकेतक में बेहतर है और दूसरों में भी बदतर नहीं है (और यहां तक कि कई प्रकार के डेटासेट पर भी)। ऐसे एल्गोरिदम हैं जो तेज होते हैं, लेकिन कम संपीड़न अनुपात देते हैं, और ऐसे भी होते हैं जो अधिक संपीड़ित करते हैं, लेकिन एक ही समय में धीमी संपीड़ित या डीकंप्रेस।

वास्तव में, LZ4 एक परेतो फ्रंटियर नहीं है। ऐसे विकल्प हैं जो थोड़ा बेहतर हैं। उदाहरण के लिए, यह LZTURBO एक निश्चित पावटबो से है । परिणामों की विश्वसनीयता में कोई संदेह नहीं है, समुदाय को encode.ru पर धन्यवाद (डेटा संपीड़न के लिए सबसे बड़ा और लगभग एकमात्र मंच)। लेकिन डेवलपर स्रोत कोड या बायनेरिज़ को वितरित नहीं करता है, लेकिन केवल उन्हें परीक्षण के लिए या बहुत सारे पैसे के लिए लोगों के एक सीमित दायरे में देता है (जैसे कि किसी ने अब तक भुगतान नहीं किया है)। इसके अलावा छिपकली (पूर्व LZ5) और घनत्व पर ध्यान देने योग्य है। वे कुछ संपीड़न स्तर का चयन करते समय LZ4 से थोड़ा बेहतर काम कर सकते हैं। LZSSE पर भी ध्यान दें - एक बेहद दिलचस्प बात। हालाँकि, इस लेख को पढ़ने के बाद इसे देखना बेहतर है।

LZ4 कैसे काम करता है?

आइए देखें कि एलजेड 4 सामान्य रूप से कैसे काम करता है। यह LZ77 एल्गोरिथ्म के कार्यान्वयन में से एक है: एल और जेड लेखकों (लेम्पेल और ज़िव) के नामों को इंगित करते हैं, और 77 - 1977 में, जब एल्गोरिथ्म प्रकाशित किया गया था। इसके कई अन्य कार्यान्वयन हैं: QuickLZ, FastLZ, BriefLZ, LZF, LZO, साथ ही साथ कम संपीड़न स्तरों का उपयोग करते समय gzip और ज़िप।

LZ4 का उपयोग करके संपीड़ित डेटा ब्लॉक में दो प्रकार के रिकॉर्ड (कमांड, निर्देश) होते हैं:

शाब्दिक: "अगले एन बाइट्स के रूप में है और परिणाम के लिए उन्हें कॉपी करें।"
मैच (मैच): "एन बाइट्स लें जो पहले से ही मौजूदा स्थिति से ऑफसेट द्वारा विघटित थे।"

एक उदाहरण है। संपीड़न से पहले:
Hello world Hello

संपीड़न के बाद:
literals 12 "Hello world " match 5 12

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

हमने मोटे तौर पर देखा कि डेटा कैसे विघटित होता है। बिंदु भी स्पष्ट है: संपीड़न करने के लिए, एल्गोरिथ्म मैचों का उपयोग करके बाइट अनुक्रमों को दोहराता है।

स्पष्ट और कुछ गुण। यह एल्गोरिथ्म बाइट-ओरिएंटेड है - यह व्यक्तिगत बाइट्स को विच्छेदित नहीं करता है, लेकिन केवल उन्हें इसकी संपूर्णता में कॉपी करता है। यहाँ अंतर, उदाहरण के लिए, एन्ट्रापी कोडिंग से है। उदाहरण के लिए, zstd LZ77 और एन्ट्रापी कोडिंग की एक रचना है।

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

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

मैच के लिए अधिकतम ऑफसेट सीमित है, LZ4 में - 64 किलोबाइट। इस मान को स्लाइडिंग विंडो कहा जाता है। दरअसल, इसका मतलब है कि जैसे-जैसे कर्सर आगे बढ़ता है, मिलान कर्सर के आकार में 64 किलोबाइट की खिड़की में हो सकता है, जो कर्सर के साथ चलता है।

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

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

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

चौकस पाठक के लिए कार्य। डेटा को छोटी एंडियन प्रारूप में UInt32 जैसी संख्याओं का एक सरणी होने दें, जो कि प्राकृतिक संख्याओं के अनुक्रम का एक हिस्सा है: 0, 1, 2 ... बताएं कि LZ4 का उपयोग करते समय यह डेटा संपीड़ित नहीं होता है (संपीड़ित डेटा की मात्रा असंपीड़ित डेटा की मात्रा से कम नहीं है)।

चीजों को कैसे गति दें

इसलिए, मैं LZ4 की अनलोडिंग को गति देना चाहता हूं। आइए देखें कि उतराई चक्र क्या है? यहाँ छद्मकोड में लूप है:

  जबकि (...)
 {
     read (input_pos, literal_length, match_length);

     copy (output_pos, input_pos, literal_length);
     output_pos + = literal_length;

     read (input_pos, match_offset);

     कॉपी (output_pos, output_pos - match_offset,
         match_length);
     output_pos + = match_length;
 }

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

वास्तव में, सब कुछ थोड़ा और अधिक जटिल है। एक बाइट को फ़ाइल से पढ़ा जाता है, और इसमें से दो निबल ले लिए जाते हैं, जिसमें 0 से 15 तक की संख्याएँ एन्कोडेड होती हैं। यदि संबंधित संख्या 15 के बराबर नहीं है, तो इसे क्रमशः शाब्दिक और मिलान की लंबाई माना जाता है। और अगर यह 15 है, तो लंबाई लंबी है और यह निम्नलिखित बाइट्स में एन्कोडेड है। फिर अगला बाइट पढ़ा जाता है, और इसका मान लंबाई में जोड़ा जाता है। इसके अलावा, अगर यह 255 के बराबर है, तो हम जारी रखते हैं - हम अगले बाइट को उसी तरह से पढ़ते हैं।

ध्यान दें कि LZ4 प्रारूप के लिए अधिकतम संपीड़न अनुपात 255 तक नहीं पहुंचता है। और दूसरा (बेकार) अवलोकन: यदि आपका डेटा बहुत बेमानी है, तो LZ4 का उपयोग करने से संपीड़न अनुपात दोगुना बढ़ जाएगा।

जब हम शाब्दिक की लंबाई (और फिर मैच की लंबाई और ऑफ़सेट ऑफ़ द मैच) पढ़ते हैं, तो यह स्पष्ट करने के लिए कि यह केवल दो टुकड़ों की स्मृति को कॉपी करने के लिए पर्याप्त है।

स्मृति के एक टुकड़े की नकल कैसे करें

ऐसा लगता है कि आप memcpy फ़ंक्शन का उपयोग कर सकते हैं, जिसे बस मेमोरी के टुकड़ों को कॉपी करने के लिए डिज़ाइन किया गया है। लेकिन यह इष्टतम नहीं है और अभी भी गलत है।

मेमॉपी फंक्शन को क्यों अपनाया जा रहा है? क्योंकि वह:

आमतौर पर libc लाइब्रेरी में स्थित होता है (और libc लाइब्रेरी आमतौर पर गतिशील रूप से लिंक होती है, और मेमसीपी कॉल परोक्ष रूप से, PLT के माध्यम से जाएगी),
संकलन समय में अनजान आकार तर्क के साथ इनलाइन नहीं,
एक स्मृति टुकड़े के "पूंछ" को सही ढंग से संसाधित करने के लिए बहुत प्रयास करता है जो मशीन शब्द या रजिस्टर के आकार के एकाधिक नहीं हैं।

अंतिम बिंदु सबसे महत्वपूर्ण है। मान लीजिए कि हमने मेमसीपी फ़ंक्शन को बिल्कुल 5 बाइट्स की प्रतिलिपि बनाने के लिए कहा। इसके लिए दो चाल निर्देशों का उपयोग करके एक बार में 8 बाइट्स कॉपी करना बहुत अच्छा होगा।

Hello world Hello wo ...
^^^^^ ^^^ - src
^^^^^ ^^^ - dst

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

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

यह अनुकूलन पहले से ही मूल LZ4 कार्यान्वयन में है:

  इनलाइन शून्य copy8 (UInt8 * dst, कॉन्स्टेंट UInt8 * src)
 {
     यादगार (dst, src, 8);  /// वास्तव में, मेमसीपी को यहां नहीं कहा जाता है।
 }

 इनलाइन शून्य वाइल्डकॉपी 8 (UInt8 * dst, const UInt8 * src, UInt8 * dn_8)
 {
     करना
     {
         copy8 (dst, src);
         dst + = 8;
         src + = 8;
     } जबकि (dst <dst_end);
 }

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

हालांकि, अभी भी कुछ सूक्ष्मताएं हैं। चक्र में दो प्रतियां हैं - शाब्दिक और मिलान। लेकिन LZ4_decompress_fast फ़ंक्शन (LZ4_decompress_safe के बजाय) का उपयोग करते समय, चेक एक बार किया जाता है - जब हमें शाब्दिक की प्रतिलिपि बनाने की आवश्यकता होती है। मैच की प्रतिलिपि बनाते समय, सत्यापन नहीं किया जाता है, लेकिन LZ4 प्रारूप विनिर्देश में ही ऐसी स्थितियाँ हैं जो इसे टालने की अनुमति देती हैं:

अंतिम 5 बाइट्स हमेशा शाब्दिक होते हैं
आखिरी मैच ब्लॉक खत्म होने से पहले कम से कम 12 बाइट्स शुरू होना चाहिए।
नतीजतन, 13 बाइट से कम वाले ब्लॉक को संपीड़ित नहीं किया जा सकता है।

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

जब मुझे एक कोड दिखाई देता है जो 8 बाइट्स के डेटा को कॉपी करता है, तो मैं तुरंत पूछता हूं - बिल्कुल 8 बाइट्स क्यों? आप SSE रजिस्टरों का उपयोग करके 16 बाइट्स कॉपी कर सकते हैं:

  इनलाइन शून्य copy16 (UInt8 * dst, कॉन्स्टेंट UInt8 * src)
 {
 #if __SSE2__
     _mm_storeu_si128 (reinterpret_cast <__ m128i *> (dst),
         _mm_loadu_si128 (reinterpret_cast <const __m128i *> (src)));
 #else
     यादगार (dst, src, 16);
 #endif
 }

 इनलाइन शून्य वाइल्डकॉपी 16 (UInt8 * dst, कॉन्स्टेंट UInt8 * src, UInt8 * dn_8)
 {
     करना
     {
         copy16 (dst, src);
         dst + = 16;
         src + = 16;
     } जबकि (dst <dst_end);
 }

AVX-512 के लिए 32 बाइट्स को कॉपी करना और AVX-512 के लिए 64 बाइट्स इसी तरह काम करता है। इसके अलावा, आप कई बार चक्र का विस्तार कर सकते हैं। यदि आपने कभी देखा है कि memcpy कैसे लागू किया memcpy है, तो यह बिल्कुल दृष्टिकोण है। (वैसे, इस मामले में संकलक न तो विस्तार करेगा और न ही लूप को वेक्टर करेगा: इसके लिए बोझिल जांच की आवश्यकता होगी।)

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

फिर भी, हम इस विकल्प को अभी के लिए ध्यान में रखेंगे।

ट्रिकी कॉपी

सवाल पर वापस - क्या इस तरह से डेटा की नकल करना हमेशा संभव है? मान लीजिए हमें एक मैच को कॉपी करने की आवश्यकता है - अर्थात, आउटपुट बफर से मेमोरी का एक टुकड़ा कॉपी करें जो कर्सर के पीछे कुछ ऑफसेट पर इस कर्सर की स्थिति में है।

एक साधारण मामले की कल्पना करें - आपको ऑफसेट 12 पर 5 बाइट्स कॉपी करने की आवश्यकता है:

Hello world ...........
^^^^^ - src
^^^^^ - dst

Hello world Hello wo ...
^^^^^ - src
^^^^^ - dst

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

ऑफसेट 3 पर 10 बाइट्स कॉपी करें:

abc .............
^^^^^^^^^^ - src
^^^^^^^^^^ - dst

abc abcabcabca ...
^^^^^^^^^^ - src
^^^^^^^^^^ - dst

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

  op [०] = मैच [०];
 op [१] = मिलान [१];
 op [२] = मिलान [२];
 op [३] = मिलान [३];
 ...

यहां बताया गया है कि यह कैसे काम करता है:

a bc a ............
^ - src
^ - dst

a b ca b ...........
^ - src
^ - dst

ab c ab c ..........
^ - src
^ - dst

abc a bc a .........
^ - src
^ - dst

abca b ca b ........
^ - src
^ - dst

यही है, हमें एक दोहराव अनुक्रम बनाना होगा। मूल LZ4 कार्यान्वयन में, आश्चर्यजनक रूप से समझ से बाहर का कोड इसके लिए लिखा गया था:

  const अहस्ताक्षरित dec32table [] = {0, 1, 2, 1, 4, 4, 4, 4};
 const int dec64table [] = {0, 0, 0, -1, 0, 1, 2, 3};

 const int dec64 = dec64table [ऑफसेट];
 op [०] = मैच [०];
 op [१] = मिलान [१];
 op [२] = मिलान [२];
 op [३] = मिलान [३];
 मैच + = dec32table [ऑफसेट];
 memcpy (ऑप + 4, मैच, 4);
 मैच - = डे 64;

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

यहां बताया गया है कि यह वास्तव में कैसे काम करता है। पहले 4 बाइट्स बाइट कॉपी करें:

abc abca .........
^^^^ - src
^^^^ - dst

अब आप एक ही बार में 4 बाइट्स कॉपी कर सकते हैं:

abcabca bcab .....
^^^^ - src
^^^^ - dst

आप एक साथ 8 बाइट्स कॉपी करके हमेशा की तरह जारी रख सकते हैं:

abcabcabcab cabcabca .....
^^^^^^^^ - src
^^^^^^^^ - dst

, — . :

 inline void copyOverlap8(UInt8 * op, const UInt8 *& match, const size_t offset)
{
    /// 4 % n.
    /// Or if 4 % n is zero, we use n.
    /// It gives equivalent result, but is better CPU friendly for unknown reason.
    static constexpr int shift1[] = { 0, 1, 2, 1, 4, 4, 4, 4 };

    /// 8 % n - 4 % n
    static constexpr int shift2[] = { 0, 0, 0, 1, 0, -1, -2, -3 };

    op[0] = match[0];
    op[1] = match[1];
    op[2] = match[2];
    op[3] = match[3];

    match += shift1[offset];
    memcpy(op + 4, match, 4);
    match += shift2[offset];
}

, , . , , — 16 .

« » , ( offset < 16 , offset < 8 ). () 16- :

 inline void copyOverlap16(UInt8 * op, const UInt8 *& match, const size_t offset)
{
    /// 4 % n.
    static constexpr int shift1[]
        = { 0, 1, 2, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 };

    /// 8 % n - 4 % n
    static constexpr int shift2[]
        = { 0, 0, 0, 1, 0, -1, -2, -3, -4, 4, 4, 4, 4, 4, 4, 4 };

    /// 16 % n - 8 % n
    static constexpr int shift3[]
        = { 0, 0, 0, -1, 0, -2, 2, 1, 8, -1, -2, -3, -4, -5, -6, -7 };

    op[0] = match[0];
    op[1] = match[1];
    op[2] = match[2];
    op[3] = match[3];

    match += shift1[offset];
    memcpy(op + 4, match, 4);
    match += shift2[offset];
    memcpy(op + 8, match, 8);
    match += shift3[offset];
}

? , SIMD-, 16 , ( 1 15). , , .

— pshufb ( packed shuffle bytes) SSSE3 ( S). 16- . . — «»: 0 15 — , . , 127 — .

यहाँ एक उदाहरण है:

 xmm0: abc.............
xmm1: 0120120120120120

pshufb %xmm1, %xmm0

xmm0: abcabcabcabcabca

— ! :

 inline void copyOverlap16Shuffle(UInt8 * op, const UInt8 *& match, const size_t offset)
{
#ifdef __SSSE3__

    static constexpr UInt8 __attribute__((__aligned__(16))) masks[] =
    {
        0, 1, 2, 1, 4, 1, 4, 2, 8, 7, 6, 5, 4, 3, 2, 1, /* offset = 0, not used as mask, but for shift amount instead */
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* offset = 1 */
        0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
        0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0,
        0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3,
        0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0,
        0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3,
        0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1,
        0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 1, 2,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 0, 1,
        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0,
     };

    _mm_storeu_si128(reinterpret_cast<__m128i *>(op),
        _mm_shuffle_epi8(
            _mm_loadu_si128(reinterpret_cast<const __m128i *>(match)),
            _mm_load_si128(reinterpret_cast<const __m128i *>(masks) + offset)));

    match += masks[offset];

#else
    copyOverlap16(op, match, offset);
#endif
}

_mm_shuffle_epi8 — intrinsic , pshufb .

, ? SSSE3 — , 2006 . AVX2 , 32 , 16- . packed shuffle bytes, vector permute bytes — , . AVX-512 VBMI , 64 , . ARM NEON — vtbl (vector table lookup), 8 .

, pshufb 64- MMX-, 8 . . , , 16 ( ).

Highload++ Siberia , 8 ( ) — !

if

, , 16 . ?

, . , , , . , .

, . , , , 65 536 . 65 536 . , , 65 551 . , , 96 128 — . , «» mmap ( madvice). - page faults. , .

?

, , :

16 8.
shuffle- offset < 16 .
if.

.

उदाहरण 1:
Xeon E2650v2, ., AppVersion.
reference: 1.67 GB/sec.
16 bytes, shuffle: 2.94 GB/sec ( 76% ).

उदाहरण 2:
Xeon E2650v2, ., ShowsSumPosition.
reference: 2.30 GB/sec.
16 bytes, shuffle: 1.91 GB/sec ( 20% ).

, . , . - , . , . — 16 . : , , .

, C++ : 8- 16- ; shuffle-.

 template <size_t copy_amount, bool use_shuffle>
void NO_INLINE decompressImpl(
     const char * const source,
     char * const dest,
     size_t dest_size)

, shuffle . , :

 sudo echo 'performance' | tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor
kill -STOP $(pidof firefox) $(pidof chromium)

«» (c Xeon E5645), , . , , . , shuffle-, , 16- .

:

 sudo kill -STOP $(pidof python) $(pidof perl) $(pgrep -u skynet) $(pidof cqudp-client)

. thermal throttling power capping.

, , . , , . . , , . : ClickHouse , , . , ( — ?). .

, , . « » . , , , .

, . . - . — ClickHouse 64 . ( .)

, « », , . , , , - . . , , . .

, , . «» , . , . Thompson Sampling.

, , . — : , . . , . , C++. — , - , ; .

? , . . -, , . -, , , «» .

, , Thompson Sampling — ( , ). , , - , , . , .

, «» . , , «», . — . , , .

, , , , «»:

 /// For better convergence, we don't use proper estimate of stddev.
/// We want to eventually separate between two algorithms even in case
/// when there is no statistical significant difference between them.
double sigma() const
{
    return mean() / sqrt(adjustedCount());
}

double sample(pcg64 & rng) const
{
     ...
    return std::normal_distribution<>(mean(), sigma())(rng);
}

, — memory latencies.

, , — LZ4 .

, :
— reference (baseline): LZ4 ;
— variant 0: 8 , shuffle;
— variant 1: 8 , shuffle;
— variant 2: 16 , shuffle;
— variant 3: 16 , shuffle;
— «» , .

CPU

CPU, , . , CPU ?

ClickHouse , 256 100 ( 256 ). , CPU , . CPU:
— Intel® Xeon® CPU E5-2650 v2 @ 2.60GHz
— Intel® Xeon® CPU E5-2660 v4 @ 2.00GHz
— Intel® Xeon® CPU E5-2660 0 @ 2.20GHz
— Intel® Xeon® CPU E5645 @ 2.40GHz
— Intel Xeon E312xx (Sandy Bridge)
— AMD Opteron(TM) Processor 6274
— AMD Opteron(tm) Processor 6380
— Intel® Xeon® CPU E5-2683 v4 @ 2.10GHz
— Intel® Xeon® CPU E5530 @ 2.40GHz
— Intel® Xeon® CPU E5440 @ 2.83GHz
— Intel® Xeon® CPU E5-2667 v2 @ 3.30GHz

— , R&D:
— AMD EPYC 7351 16-Core Processor — AMD.
— Cavium ThunderX2 — x86, AArch64. SIMD- . 224 56 .

13 , 256 6 (reference, 0, 1, 2, 3, adaptive), 10 , . 199 680 , .

, CPU . : LZ4 ( — ). , Cavium . ClickHouse, «» Xeon E5-2650 v2 , , ClickHouse x86.

 ┌─cpu───────────────────┬──ref─┬─adapt─┬──max─┬─best─┬─adapt_boost─┬─max_boost─┬─adapt_over_max─┐
│ E5-2667 v2 @ 3.30GHz │ 2.81 │ 3.19 │ 3.15 │ 3 │ 1.14 │ 1.12 │ 1.01 │
│ E5-2650 v2 @ 2.60GHz │ 2.5 │ 2.84 │ 2.81 │ 3 │ 1.14 │ 1.12 │ 1.01 │
│ E5-2683 v4 @ 2.10GHz │ 2.26 │ 2.63 │ 2.59 │ 3 │ 1.16 │ 1.15 │ 1.02 │
│ E5-2660 v4 @ 2.00GHz │ 2.15 │ 2.49 │ 2.46 │ 3 │ 1.16 │ 1.14 │ 1.01 │
│ AMD EPYC 7351 │ 2.03 │ 2.44 │ 2.35 │ 3 │ 1.20 │ 1.16 │ 1.04 │
│ E5-2660 0 @ 2.20GHz │ 2.13 │ 2.39 │ 2.37 │ 3 │ 1.12 │ 1.11 │ 1.01 │
│ E312xx (Sandy Bridge) │ 1.97 │ 2.2 │ 2.18 │ 3 │ 1.12 │ 1.11 │ 1.01 │
│ E5530 @ 2.40GHz │ 1.65 │ 1.93 │ 1.94 │ 3 │ 1.17 │ 1.18 │ 0.99 │
│ E5645 @ 2.40GHz │ 1.65 │ 1.92 │ 1.94 │ 3 │ 1.16 │ 1.18 │ 0.99 │
│ AMD Opteron 6380 │ 1.47 │ 1.58 │ 1.56 │ 1 │ 1.07 │ 1.06 │ 1.01 │
│ AMD Opteron 6274 │ 1.15 │ 1.35 │ 1.35 │ 1 │ 1.17 │ 1.17 │ 1 │
│ E5440 @ 2.83GHz │ 1.35 │ 1.33 │ 1.42 │ 1 │ 0.99 │ 1.05 │ 0.94 │
│ Cavium ThunderX2 │ 0.84 │ 0.87 │ 0.87 │ 0 │ 1.04 │ 1.04 │ 1 │
└───────────────────────┴──────┴───────┴──────┴──────┴─────────────┴───────────┴────────────────┘

ref, adapt, max — (, ). best — , 0 3. adapt_boost — baseline. max_boost — baseline. adapt_over_max — .

, x86 12–20%. ARM 4%, , . , «» Intel.

निष्कर्ष

. , LZ4 12–20%, . . , .

, , «» , ZStandard level 1 LZ4: IO .

— , . , .

: . LZ4 , Lizard, Density LZSSE , . , LZ4 LZSSE ClickHouse.

LZ4 : . : , . . , inc- dec- . , 12–15% 32 , 16, . 32 — , .

, , page cache userspace ( mmap, O_DIRECT userspace page cache — ), - ( CityHash128 CRC32-C, HighwayHash, FARSH XXH3). , .

, master, . HighLoad++ Siberia, .

ClickHouse में LZ4 के अनलोडिंग को कैसे तेज करें