👨🏻‍🏭 🌉 🧝🏻 ClickHouse में LZ4 अपघटन को कैसे तेज करें? 🦋 😏 ⏳

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

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

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

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

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

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

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

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

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

क्यों LZ4?

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

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

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

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

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

कैसे lz4 काम करता है

आइए देखें कि एलजेड 4 सामान्य रूप से कैसे काम करता है। यह LZ77 एल्गोरिथ्म के कार्यान्वयन में से एक है। एल और जेड डेवलपर्स के नाम (लेम्पेल और ज़िव) का प्रतिनिधित्व करते हैं, और 77 एल्गोरिथ्म प्रकाशित होने पर वर्ष 1977 के लिए है। कई अन्य कार्यान्वयन हैं: क्विकएलजेड, फास्टएलजेड, ब्रीफ्लज, एलजेडएफ, एलजेडओ, और जीज़िप और ज़िप यदि कम संपीड़न स्तरों का उपयोग किया जाता है।

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

साहित्य: "निम्न एन बाइट्स को इस तरह लें और उन्हें परिणाम पर कॉपी करें"।
मैच: "वर्तमान स्थिति के सापेक्ष ऑफसेट मूल्य पर शुरू होने वाले विघटित परिणाम से एन बाइट्स लें"।

उदाहरण। संपीड़न से पहले:

 Hello world Hello

संपीड़न के बाद:

 literals 12 "Hello world " match 5 12

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

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

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

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

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

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

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

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

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

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

सब कुछ कैसे गति दें

इसलिए मैं LZ4 अपघटन को गति देना चाहता हूं। आइए देखें कि विघटित लूप कैसा दिखता है। यहाँ यह छद्मकोड में है:

 while (...) {    read(input_pos, literal_length, match_length);    copy(output_pos, input_pos, literal_length);    output_pos += literal_length;    read(input_pos, match_offset);    copy(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 के मूल कार्यान्वयन में पहले से ही है:

 inline void copy8(UInt8 * dst, const UInt8 * src) {    memcpy(dst, src, 8); /// Note that memcpy isn't actually called here. } inline void wildCopy8(UInt8 * dst, const UInt8 * src, UInt8 * dst_end) {    do    {        copy8(dst, src);        dst += 8;        src += 8;    } while (dst < dst_end); }

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

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

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

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

जब मैं 8 बाइट्स डेटा की प्रतिलिपि बनाने वाला कोड देखता हूं, तो मुझे तुरंत आश्चर्य होता है कि वास्तव में 8 बाइट्स क्यों हैं। आप SSE रजिस्टरों का उपयोग करके 16 बाइट्स कॉपी कर सकते हैं:

 inline void copy16(UInt8 * dst, const UInt8 * src) { #if __SSE2__    _mm_storeu_si128(reinterpret_cast<__m128i *>(dst),        _mm_loadu_si128(reinterpret_cast<const __m128i *>(src))); #else    memcpy(dst, src, 16); #endif } inline void wildCopy16(UInt8 * dst, const UInt8 * src, UInt8 * dst_end) {    do    {        copy16(dst, src);        dst += 16;        src += 16;    } while (dst < dst_end); }

AVX-512 के लिए AVX और 64 बाइट्स के लिए 32 बाइट्स कॉपी करने के लिए यही काम करता है। इसके अलावा, आप कई बार लूप को अनियंत्रित कर सकते हैं। यदि आपने कभी देखा है कि 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[0] = match[0]; op[1] = match[1]; op[2] = match[2]; op[3] = match[3]; ...

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

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 unsigned dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; const int dec64 = dec64table[offset]; op[0] = match[0]; op[1] = match[1]; op[2] = match[2]; op[3] = match[3]; match += dec32table[offset]; memcpy(op+4, match, 4); match -= dec64;

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

यहां बताया गया है कि यह वास्तव में कैसे काम करता है। हम पहले 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 an equivalent result, but is more CPU friendly for unknown reasons.    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 (पैक्ड शफल बाइट्स) कहा जाता है जो 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 एक आंतरिक है , जो pshufb CPU निर्देश को संकलित करता है।

क्या हम नए निर्देशों का उपयोग करते हुए एक बार में अधिक बाइट्स के लिए यह ऑपरेशन कर सकते हैं? आखिरकार, SSSE3 एक बहुत पुराना इंस्ट्रक्शन सेट है जो 2006 के आसपास रहा है। AVX2 में एक निर्देश है जो एक बार में 32 बाइट्स के लिए ऐसा करता है, लेकिन अलग-अलग 16-बाइट लेन के लिए। इसे पैक्ड फेरबदल बाइट्स के बजाय वेक्टर परमिट बाइट्स कहा जाता है - शब्द अलग हैं, लेकिन अर्थ समान है। AVX-512 VBMI में एक और निर्देश है जो एक ही बार में 64 बाइट्स के लिए काम करता है, लेकिन इसका समर्थन करने वाले प्रोसेसर हाल ही में सामने आए हैं। एआरएम नियॉन के समान निर्देश हैं जिन्हें vtbl (वेक्टर टेबल लुकअप) कहा जाता है, लेकिन वे केवल 8 बाइट्स लिखने की अनुमति देते हैं।

इसके अलावा, 8 बाइट्स बनाने के लिए 64-बिट MMX रजिस्टरों के साथ pshufb निर्देश का एक संस्करण है। यह कोड के मूल संस्करण को बदलने के लिए सही है। हालांकि, मैंने इसके बजाय (गंभीर कारणों के लिए) 16-बाइट विकल्प का उपयोग करने का फैसला किया।

हाईलोड + ++ साइबेरिया सम्मेलन में, एक प्रतिभागी मेरी प्रस्तुति के बाद मेरे पास आया और उल्लेख किया कि 8-बाइट मामले के लिए, आप केवल एक विशेष रूप से चयनित स्थिरांक से गुणा का उपयोग कर सकते हैं (आपको ऑफसेट की भी आवश्यकता होगी) - यह भी नहीं हुआ था मेरे सामने!

कैसे एक अतिशयोक्ति को दूर करने के लिए यदि कथन

मान लीजिए कि मैं एक ऐसे संस्करण का उपयोग करना चाहता हूं जो 16 बाइट्स की प्रतिलिपि बनाता है। मैं बफर अतिप्रवाह के लिए अतिरिक्त जांच करने से कैसे बच सकता हूं?

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

दरअसल, इसके नकारात्मक परिणाम हो सकते हैं। मान लीजिए कि जिस डेटा को हमें डिकम्प्रेस करना है, वह प्रत्येक 65,536 बाइट्स के ब्लॉक से बनता है। तब उपयोगकर्ता हमें स्मृति का एक टुकड़ा देता है जो विघटित डेटा के लिए 65,536 बाइट्स है। लेकिन नए फ़ंक्शन इंटरफ़ेस के साथ, उपयोगकर्ता को 65,551 बाइट्स वाले मेमोरी ब्लॉक को आवंटित करना आवश्यक होगा, उदाहरण के लिए। फिर आवंटनकर्ता को इसके कार्यान्वयन के आधार पर वास्तव में 96 या यहां तक कि 128 किलोबाइट आवंटित करने के लिए मजबूर किया जा सकता है। यदि आबंटक बहुत खराब है, तो यह अचानक "हीप" में कैशिंग मेमोरी को बंद कर सकता है और मेमोरी आवंटन (या madvice का उपयोग करके मेमोरी जारी madvice ) के लिए हर बार munmap और munmap का उपयोग करना शुरू कर सकता है। पृष्ठ दोष के कारण यह प्रक्रिया बेहद धीमी होगी। नतीजतन, अनुकूलन का यह थोड़ा सा सब कुछ धीमा कर सकता है।

क्या कोई तेजी है?

इसलिए मैंने कोड का एक संस्करण बनाया जो तीन अनुकूलन का उपयोग करता है:

8 के बजाय 16 बाइट्स कॉपी करना।
offset < 16 मामले के लिए फेरबदल निर्देशों का उपयोग करना।
एक अतिरिक्त निकाल दिया अगर।

मैंने डेटा के विभिन्न सेटों पर इस कोड का परीक्षण शुरू किया और अप्रत्याशित परिणाम प्राप्त किए।

उदाहरण 1:
Xeon E2650v2, Yandex Browser data, AppVersion कॉलम।
संदर्भ: 1.67 जीबी / सेकंड।
16 बाइट्स, फेरबदल: 2.94 जीबी / सेक (76% तेज)।

उदाहरण 2:
Xeon E2650v2, Yandex डायरेक्ट डेटा, शोसमपिशन कॉलम।
संदर्भ: 2.30 जीबी / सेकंड।
16 बाइट्स, फेरबदल: 1.91 जीबी / सेकंड (20% धीमी)।

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

जांच करने के लिए, मैंने चार मामलों के लिए कोड विकल्प बनाने के लिए C ++ टेम्प्लेट का उपयोग किया: 8-बाइट या 16-बाइट विखंडू का उपयोग करके, और फेरबदल निर्देश के साथ या बिना।

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

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

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

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

वैसे, जब हमारे सर्वर पर परीक्षण करते हैं, तो ऐसा करने के लिए यह समझ में आता है:

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

अन्यथा, परिणाम अस्थिर होंगे। थर्मल थ्रॉटलिंग और पावर कैपिंग के लिए भी देखें।

सबसे अच्छा एल्गोरिथ्म कैसे चुनें

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

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

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

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

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

लेकिन हम एक विघटन एल्गोरिथ्म का चयन कर रहे हैं। परिणाम बाइट्स में picoseconds में निष्पादन का समय है: कम, बेहतर। हम निष्पादन के समय को एक यादृच्छिक चर मानते हैं और गणितीय आँकड़ों का उपयोग करके इसके वितरण का मूल्यांकन करेंगे। बायेसियन दृष्टिकोण का उपयोग अक्सर इस तरह के कार्यों के लिए किया जाता है, लेकिन जटिल सूत्रों को C ++ कोड में डालना बोझिल होगा। हम एक पैरामीट्रिक दृष्टिकोण का उपयोग कर सकते हैं और कह सकते हैं कि एक यादृच्छिक चर यादृच्छिक चर के पैरामीट्रिक परिवार से संबंधित है, और फिर इसके मापदंडों का मूल्यांकन करें।

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

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

This may seem like a somewhat ignorant approach. Experience has shown us that the average time for query execution, website page loading, and so on is "garbage" that isn't worth calculating. It would be better to calculate the median, which is a robust statistic . But this is a little more difficult, and as I will show later, the described method justifies itself for practical purposes.

At first I implemented calculation of the mathematical expectation and variance, but then I decided that this is too good, and I need to simplify the code to make it "worse":

 /// For better convergence, we don't use proper estimate of stddev. /// We want to eventually separate the two algorithms even in cases /// 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); }

I wrote it so that the first few iterations were not taken into account, to eliminate the effect of memory latencies.

The result is a test program that can select the best algorithm for the input data, with optional modes that use the reference implementation of LZ4 or a specific version of the algorithm.

So there are six options:
— Reference (baseline): original LZ4 without our modifications.
— Variant 0: copy 8 bytes at a time without shuffle.
— Variant 1: copy 8 bytes at a time with shuffle.
— Variant 2: copy 16 bytes at a time without shuffle.
— Variant 3: copy 16 bytes at a time with shuffle.
— The "bandit" option, which selects the best of the four optimized variants.

Testing on different CPUs

If the result strongly depends on the CPU model, it would be interesting to find out exactly how it is affected. There might be an exceptionally large difference on certain CPUs.

I prepared a set of datasets from different tables in ClickHouse with real data, for a total of 256 different files each with 100 MB of uncompressed data (the number 256 was coincidental). Then I looked at the CPUs of the servers where I can run benchmarks. I found servers with the following CPUs:
— 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

The most interesting part comes next — the processors provided by the R&D department:
— AMD EPYC 7351 16-Core Processor, a new AMD server processor.
— Cavium ThunderX2, which is AArch64, not x86. For these, my SIMD optimization needed to be reworked a bit. The server has 224 logical and 56 physical cores.

There are 13 servers in total, and each of them runs the test on 256 files in 6 variants (reference, 0, 1, 2, 3, adaptive). The test is run 10 times, alternating between the options in random order. It outputs 199,680 results that we can compare.

For example, we can compare different CPUs with each other. But we shouldn't jump to conclusions from these results, because we are only testing the LZ4 decompression algorithm on a single core (this is a very narrow case, so we only get a micro-benchmark). For example, the Cavium has the lowest performance per single core. But I tested ClickHouse on it myself, and it wins out over Xeon E5-2650 v2 on heavy queries due to the greater number of cores, even though it is missing many optimizations that are made in ClickHouse specifically for the 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 — The speed in gigabytes per second (the value that is the reverse of the arithmetic mean of time for all launches on all datasets).
best — The number of the best algorithm among the optimized variants, from 0 to 3.
adapt_boost — The relative advantage of the adaptive algorithm compared to the baseline.
max_boost — The relative advantage of the best of the non-adaptive variants compared to the baseline.
adapt_over_max — The relative advantage of the adaptive algorithm over the best non-adaptive one.

The results show that we were able to speed up decompression by 12-20% on modern x86 processors. Even on ARM we saw 4% improvement, despite the fact that we didn't optimize much for this architecture. It is also clear that on average for different datasets, the "bandit" algorithm comes out ahead of the pre-selected best variant on all processors (except for very old Intel CPUs).

निष्कर्ष

In practice, the usefulness of this work is dubious. Yes, LZ4 decompression was accelerated on average by 12-20%, and on some datasets the performance more than doubled. But in general, this doesn't have much effect on query execution time. It's difficult to find real queries that gain more than a couple percent in speed.

We decided to use ZStandard level 1 instead of LZ4 on several Yandex Metrica clusters intended for executing long queries, because it is more important to save IO and disk space on cold data. Keep this in mind if you have similar workload.

We observed the greatest benefits from optimizing decompression in highly compressible data, such as columns with mostly duplicate string values. However, we have developed a separate solution specifically for this scenario that allows us to significantly speed up queries over this kind of data.

Another point to remember is that optimization of decompression speed is often limited by the format of the compressed data. LZ4 uses a very good format, but Lizard, Density and LZSSE have other formats that can work faster. Perhaps instead of trying to accelerate LZ4, it would be better to just integrate LZSSE into ClickHouse.

It's unlikely that these optimizations will be implemented in the mainstream LZ4 library: in order to use them, the library interface would have to be modified. In fact, this is often the case with improving algorithms — optimizations don't fit into old abstractions and they have to be revised. However, variable names have already been corrected in the original implementation. For instance, inc and dec tables have been corrected . In addition, about a month ago, the original implementation accelerated decompression by the same 12-15% by copying 32 bytes instead of 16, as discussed above. We tried the 32-byte option ourselves and the results were not that great, but they were still faster .

If you look at the profile at the beginning of the article, you may notice that we could have removed one extra copying operation from the page cache to userspace (either using mmap , or using O_DIRECT and userspace page cache, but both options are problematic). We also could have slightly improved the checksum calculation (CityHash128 is currently used without CRC32-C, but we could use HighwayHash, FARSH or XXH3). Acceleration of these two operations is useful for weakly compressed data, since they are performed on compressed data.

In any case, the changes have already been added to master more than a year ago, and the ideas that resulted from this research have been applied in other tasks. You can also watch the video from HighLoad++ Siberia, or view the presentation (both in Russian).

ClickHouse में LZ4 अपघटन को कैसे तेज करें?