👨🏻‍⚖️ 👨🏿‍⚖️ 🏕️ डेटाबेस में सुधार के लिए पाँच तरीके ☸️ 🤴🏾 🤜🏼

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

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

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

2016 में ClickHouse को खुले स्रोत के रूप में जारी किए जाने के बाद, लोगों ने इन परीक्षणों पर सवाल उठाना शुरू कर दिया।

निजी डेटा पर परीक्षणों की कमियों

हमारे प्रदर्शन परीक्षण:

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

हम पुराने परीक्षणों को तोड़कर और खुले डेटा के आधार पर नए लेखन कर सकते हैं, जैसे यूएसए के लिए उड़ान डेटा और न्यूयॉर्क में टैक्सी की सवारी । या हम TPC-H, TPC-DS और स्टार स्कीमा बेंचमार्क जैसे बेंचमार्क का उपयोग कर सकते हैं। नुकसान यह है कि यह डेटा Yandex.Metrica डेटा से बहुत अलग है, और हम इसके बजाय परीक्षण क्वेरी रखेंगे।

वास्तविक डेटा का उपयोग करना क्यों महत्वपूर्ण है

प्रदर्शन को केवल उत्पादन वातावरण से वास्तविक डेटा पर परीक्षण किया जाना चाहिए। आइए कुछ उदाहरण देखें।

उदाहरण 1

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

नीचे पंक्ति: टेस्ट डेटा में यथार्थवादी संपीड़न अनुपात होना चाहिए।

मैंने पिछली पोस्ट में ClickHouse डेटा कम्प्रेशन एल्गोरिदम के अनुकूलन को कवर किया।

उदाहरण 2

मान लें कि हम इस SQL क्वेरी के निष्पादन की गति में रुचि रखते हैं:

SELECT RegionID, uniq(UserID) AS visitors FROM test.hits GROUP BY RegionID ORDER BY visitors DESC LIMIT 10

यह Yandex.Metrica के लिए एक विशिष्ट क्वेरी है। प्रसंस्करण की गति को क्या प्रभावित करता है?

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

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

कई DBMS COUNT (DISTINCT) के सन्निकटन के लिए HyperLogLog डेटा संरचना को लागू करते हैं, लेकिन उनमें से कोई भी बहुत अच्छी तरह से काम नहीं करता है क्योंकि यह डेटा संरचना निश्चित मात्रा में मेमोरी का उपयोग करती है। ClickHouse में एक फ़ंक्शन होता है जो डेटा सेट के आकार के आधार पर तीन अलग-अलग डेटा संरचनाओं के संयोजन का उपयोग करता है ।

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

उदाहरण 3

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

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

आप इसके बारे में और अधिक सीख सकते हैं "ClickHouse में हैश टेबल कैसे काम करती है" (रूसी में प्रस्तुति)। यह जानकारी थोड़ी पुरानी है, क्योंकि इसमें स्विस टेबल्स शामिल नहीं हैं ।

चुनौती

हमारा लक्ष्य परीक्षण प्रदर्शन के लिए डेटा प्राप्त करना है, जिसमें यैंडेक्स.मेट्रिक डेटा के समान संरचना है जिसमें सभी गुण हैं जो बेंचमार्क के लिए महत्वपूर्ण हैं, लेकिन इस तरह से कि इस डेटा में वास्तविक वेबसाइट उपयोगकर्ताओं का कोई निशान नहीं है। दूसरे शब्दों में, डेटा को अज्ञात और अभी भी संरक्षित किया जाना चाहिए:

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

हम डेटा के लिए एक समान संपीड़न अनुपात कैसे प्राप्त कर सकते हैं? यदि LZ4 का उपयोग किया जाता है, तो बाइनरी डेटा में सबस्ट्रिंग लगभग एक ही दूरी पर दोहराई जानी चाहिए और पुनरावृत्तियां लगभग समान लंबाई होनी चाहिए। ZSTD के लिए, प्रति बाइट एन्ट्रापी को भी मेल खाना चाहिए।

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

हालाँकि, ये बहुत ही कम परिभाषित आवश्यकताएं हैं और हम इस कार्य के लिए एक औपचारिक समस्या कथन या विनिर्देशन लिखने की योजना नहीं बना रहे हैं।

संभव समाधान

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

स्पष्ट संभाव्य मॉडल

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

मार्कोव श्रृंखला का उपयोग पाठ क्षेत्रों के लिए किया जा सकता है। यह एक परिचित मॉडल है जिसे प्रभावी ढंग से लागू किया जा सकता है।

हालाँकि, इसके लिए कुछ तरकीबों की आवश्यकता होगी:

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

यह सब एक C ++ "स्क्रिप्ट" में लिखा जा सकता है जिसमें वितरण और निर्भरता हार्ड कोडित होती है। हालांकि, मार्कोव मॉडल को चौरसाई और शोर को जोड़ने के साथ आंकड़ों के संयोजन से प्राप्त किया जाता है। मैंने इस तरह से एक स्क्रिप्ट लिखना शुरू किया, लेकिन दस स्तंभों के लिए स्पष्ट मॉडल लिखने के बाद, यह असहनीय रूप से उबाऊ हो गया - और यैंडेक्स में "हिट" तालिका। मीट्रीका में 2012 में 100 से अधिक कॉलम वापस आ गए थे।

 EventTime.day(std::discrete_distribution<>({ 0, 0, 13, 30, 0, 14, 42, 5, 6, 31, 17, 0, 0, 0, 0, 23, 10, ...})(random)); EventTime.hour(std::discrete_distribution<>({ 13, 7, 4, 3, 2, 3, 4, 6, 10, 16, 20, 23, 24, 23, 18, 19, 19, ...})(random)); EventTime.minute(std::uniform_int_distribution<UInt8>(0, 59)(random)); EventTime.second(std::uniform_int_distribution<UInt8>(0, 59)(random)); UInt64 UserID = hash(4, powerLaw(5000, 1.1)); UserID = UserID / 10000000000ULL * 10000000000ULL + static_cast<time_t>(EventTime) + UserID % 1000000; random_with_seed.seed(powerLaw(5000, 1.1)); auto get_random_with_seed = [&]{ return random_with_seed(); };

यह दृष्टिकोण एक विफलता थी। अगर मैंने और कोशिश की होती, तो शायद अब तक स्क्रिप्ट तैयार हो जाती।

लाभ:

वैचारिक सरलता।

नुकसान:

बड़ी मात्रा में काम की आवश्यकता।
समाधान केवल एक प्रकार के डेटा पर लागू होता है।

और मैं एक और सामान्य समाधान पसंद करूंगा जिसका इस्तेमाल Yandex.Metrica डेटा के साथ-साथ अन्य डेटा को बाधित करने के लिए भी किया जा सकता है।

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

लेकिन मैंने इस विचार को भी खारिज कर दिया, क्योंकि विचार करने के लिए बहुत सारे कारक हैं और इसे लिखने में बहुत लंबा समय लगेगा।

तंत्रिका नेटवर्क

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

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

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

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

जैसे-जैसे गर्मियों की शुरुआत हुई, हमारे पास पहले काम करने वाली पायथन लिपि थी जो डेटा उत्पन्न करती थी। पहली नज़र में डेटा गुणवत्ता सभ्य लग रही थी:

हालाँकि, हमने कुछ कठिनाइयों में भाग लिया:

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

शरीफ ने आंकड़ों की तुलना करके डेटा की गुणवत्ता का विश्लेषण करने की कोशिश की। अन्य बातों के अलावा, उन्होंने स्रोत डेटा और उत्पन्न डेटा में होने वाले विभिन्न वर्णों की आवृत्ति की गणना की। परिणाम आश्चर्यजनक था: सबसे लगातार वर्ण was और the थे।

हालांकि, शरीफ के बारे में चिंता मत करो। उन्होंने सफलतापूर्वक अपनी थीसिस का बचाव किया और फिर हम खुशी से पूरी बात भूल गए।

संपीड़ित डेटा का म्यूटेशन

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

तो हम एक संपीड़ित फ़ाइल को कैसे संपादित करते हैं? मान लें कि हम केवल LZ4 में रुचि रखते हैं। LZ4 संपीड़ित डेटा अनुक्रमों से बना होता है, जो बदले में संपीड़ित बाइट्स (शाब्दिक) के तार होते हैं, इसके बाद एक मैच कॉपी होती है:

साहित्य (निम्नलिखित एन बाइट्स की प्रतिलिपि बनाएँ)।
4 की न्यूनतम पुनरावृत्ति लंबाई (एन एन बाइट्स जो एम की दूरी पर फ़ाइल में थी) के साथ मेल खाता है।

स्रोत डेटा:
Hello world Hello ।

संपीड़ित डेटा (मनमाना उदाहरण):
literals 12 "Hello world " match 5 12 ।

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

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

अशक्त बाइट्स और ASCII नियंत्रण वर्ण के रूप में रखा जाता है।
कुछ विराम चिह्नों के रूप में रहता है।
ASCII ASCII में परिवर्तित हो जाता है और बाकी सभी चीजों के लिए सबसे महत्वपूर्ण बिट संरक्षित है (या "यदि" के स्पष्ट सेट को अलग-अलग UTF-8 लंबाई के लिए लिखा गया है)। एक बाइट क्लास में एक नया मान समान रूप से यादृच्छिक पर उठाया जाता है।
https:// जैसे टुकड़े संरक्षित हैं, अन्यथा यह थोड़ा मूर्खतापूर्ण लगता है।

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

URL के लिए उदाहरण:

http://ljc.she/kdoqdqwpgafe/klwlpm&qw=962788775I0E7bs7OXeAyAx
http://ljc.she/kdoqdqwdffhant.am/wcpoyodjit/cbytjgeoocvdtclac
http://ljc.she/kdoqdqwpgafe/klwlpm&qw=962788775I0E7bs7OXe
http://ljc.she/kdoqdqwdffhant.am/wcpoyodjit/cbytjgeoocvdtclac
http://ljc.she/kdoqdqwdbknvj.s/hmqhpsavon.yf#aortxqdvjja
http://ljc.she/kdoqdqw-bknvj.s/hmqhpsavon.yf#aortxqdvjja
http://ljc.she/kdoqdqwpdtu-Unu-Rjanjna-bbcohu_qxht
http://ljc.she/kdoqdqw-bknvj.s/hmqhpsavon.yf#aortxqdvjja
http://ljc.she/kdoqdqwpdtu-Unu-Rjanjna-bbcohu_qxht
http://ljc.she/kdoqdqw-bknvj.s/hmqhpsavon.yf#aortxqdvjja
http://ljc.she/kdoqdqwpdtu-Unu-Rjanjna-bbcohu-702130

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

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

एक अन्य समस्या यह है कि यदि कोई स्तंभ "लंबाई, मान" प्रारूप में डेटा संग्रहीत करता है (यह स्ट्रिंग कॉलम संग्रहीत है), तो मैं यह कैसे सुनिश्चित करूं कि लंबाई उत्परिवर्तन के बाद सही बनी हुई है? जब मैंने इसे ठीक करने की कोशिश की, तो मैंने तुरंत दिलचस्पी खो दी।

रैंडम क्रमपरिवर्तन

दुर्भाग्य से, समस्या हल नहीं हुई थी। हमने कुछ प्रयोग किए, और यह खराब हो गया। केवल एक चीज बची थी, वह कुछ भी नहीं करने के लिए बैठी थी और बेतरतीब ढंग से वेब पर सर्फ किया, क्योंकि जादू चला गया था। सौभाग्य से, मैं एक ऐसे पृष्ठ पर आया, जिसने गेम वोल्फेंस्टीन 3 डी में मुख्य चरित्र की मृत्यु का प्रतिपादन करने के लिए एल्गोरिदम को समझाया ।

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

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

छद्म आयामी क्रमपरिवर्तन प्राप्त करने के संभावित तरीके क्या हैं? हम सरल एक-से-एक रूपांतरण ले सकते हैं और एक जटिल फ़ंक्शन का निर्माण कर सकते हैं जो यादृच्छिक दिखता है। यहां मेरे कुछ पसंदीदा वन-टू-वन ट्रांसफॉर्मेशन हैं:

दो समरूप अंकगणित में विषम संख्या (जैसे बड़ी अभाज्य संख्या) से गुणा।
Xorshift: x ^= x >> N
सीआरसी-एन, जहां एन तर्क में बिट्स की संख्या है।

उदाहरण के लिए, तीन गुणा और दो xorshift संचालन murmurhash फाइनल के लिए उपयोग किया जाता है। यह ऑपरेशन एक छद्म आयामी क्रमपरिवर्तन है। हालाँकि, मुझे यह इंगित करना चाहिए कि हैश फ़ंक्शंस एक-से-एक (यहां तक कि एन बिट्स से एन बिट्स की हैश) नहीं होना चाहिए।

या यहां जेफ प्रेशिंग की वेबसाइट से प्राथमिक संख्या सिद्धांत का एक और दिलचस्प उदाहरण है ।

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

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

मूल्यों की मूल कार्डिनैलिटी रखने के अलावा, मैं मूल्यों के परिमाण का क्रम भी रखना चाहता हूं। मेरा मतलब है कि यदि स्रोत डेटा में 10 से कम संख्याएं हैं, तो मैं चाहता हूं कि परिवर्तित संख्याएं भी छोटी हों। हम इसे कैसे प्राप्त कर सकते हैं?

उदाहरण के लिए, हम आकार वर्गों में संभावित मूल्यों के एक सेट को विभाजित कर सकते हैं और प्रत्येक वर्ग के भीतर अलग-अलग क्रमांकन कर सकते हैं (आकार कक्षाओं को बनाए रखते हुए)। ऐसा करने का सबसे आसान तरीका दो की निकटतम शक्ति या संख्या में सबसे महत्वपूर्ण बिट की स्थिति को आकार वर्ग के रूप में लेना है (ये एक ही बात हैं)। संख्या 0 और 1 हमेशा बनी रहेगी। नंबर 2 और 3 कभी-कभी वैसे रहेंगे (1/2 की प्रायिकता के साथ) और कभी-कभी स्वैप किए जाएंगे (1/2 की संभावना के साथ)। 1024. 2047 नंबर का सेट 1024 में से एक के लिए मैप किया जाएगा! (भाज्य) प्रकार, और इसी तरह। हस्ताक्षरित संख्याओं के लिए, हम हस्ताक्षर रखेंगे।

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

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

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

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

तर्क के बिट्स को दो हिस्सों में विभाजित किया गया है:
arg: xxxxyyyy arg_l : xxxx arg_r : yyyy
दायां आधा बाईं ओर बदल जाता है। इसके स्थान पर हमने XOR का परिणाम बाएं आधे के प्रारंभिक मूल्य पर रखा और फ़ंक्शन का परिणाम दाहिने आधे के प्रारंभिक मूल्य पर लागू होता है, जैसे:
res: yyyyzzzz res_l = yyyy = arg_r res_r = zzzz = arg_l ^ F( arg_r )

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

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

Feistel नेटवर्क कई डेटा एन्क्रिप्शन एल्गोरिदम के केंद्र में है। हम जो करने जा रहे हैं वह एन्क्रिप्शन जैसा कुछ है, केवल यह वास्तव में बुरा है। इसके दो कारण हैं:

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

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

मार्कोव मॉडल

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

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

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

मॉडल को थोड़ा सुधारने के लिए, हम पत्र के होने की सशर्त संभावना का उपयोग भी कर सकते हैं यदि यह विशिष्ट अक्षरों से पहले हो। N एक पूर्व-सेट स्थिरांक है। मान लें कि N = 5 और हम अक्षर "ई" के बाद होने वाले अक्षर "ई" की संभावना की गणना कर रहे हैं। इस टेक्स्ट मॉडल को ऑर्डर-एन मार्कोव मॉडल कहा जाता है।

P(cat a | cat) = 0.8
P(cat b | cat) = 0.05
P(cat c | cat) = 0.1
...

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

शीर्षक के लिए उदाहरण (उपयोग किए गए डेटा के कारण हमारे उदाहरण तुर्की में हैं):

ह्यूनडे बटराइंडन एंकल शलूहा - पोलितिका हेड मैनसिटलेरी | STALKER BOXER edeiftede किताब - यानुदिस्टकरिस्मान्लिम मय कनाल | लीग एल डिजिटलिका हैबरलर हैबरेली - हैबरलेसी - सेंट्रीलर नेडेन बाबा डॉट कॉम के साथ होटल

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

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

एक और आवश्यकता यह है कि स्रोत डेटा में कई अलग-अलग URL हो सकते हैं जो एक ही उपसर्ग से शुरू होते हैं लेकिन समान नहीं होते हैं। उदाहरण के लिए: https://www.yandex.ru/images/cats/?id=xxxxxx । हम चाहते हैं कि परिणाम में भी ऐसे URL हों जो सभी एक ही उपसर्ग से शुरू हों, लेकिन एक अलग हों। उदाहरण के लिए: http://ftp.google.kz/cgi-bin/index.phtml?item=xxxxxx । मार्कोव मॉडल का उपयोग करके अगले चरित्र को उत्पन्न करने के लिए एक यादृच्छिक संख्या जनरेटर के रूप में, हम निर्दिष्ट स्थान पर 8 बाइट्स की चलती विंडो से एक हैश फ़ंक्शन लेंगे (इसके बजाय इसे पूरे स्ट्रिंग से लेने के लिए)।

https://www.yandex.ru/ images/c ats/?id=12345
^^^^^^^^

distribution: [aaaa][b][cc][dddd][e][ff][g g ggg][h]...
hash(" images/c ") % total_count: ^

http://ftp.google.kz/c g ...

यह वही निकलता है जो हमें चाहिए। यहाँ पृष्ठ के शीर्षक का उदाहरण दिया गया है:

  PhotoFunia - Haber7 - Hava mükemment.net Oynamak içinde şaşıracak haber, Oyunu Oynanılmaz • apród.hu kínálatában - RT अरबी
 फोटोफूनिया - किनोबार.नेट - एप्रोड: इनजीनिस |  Posti
 PhotoFunia - खूंटी Perfeo - कास्तिका, Sıradışı डेनिज़ लोकेडिंग आपका कोड, sire Emmema.co./
 PhotoFunia - TUT.BY - आपका अयक्कानिन सोन डाकिका स्पोर,
 PhotoFunia - बड़ी फिल्म izle, Del Meireles offilim, Samsung DealeXtreme Değerler NEWSru.com.tv, Smotri.com मोबाइल yapmak Okey
 फोटोफुनिया 5 |  गैलेक्सी, जीटी, डुप्ले सी गुदा बिली यारक सीजा आरई 50 ए वी-स्ट्रैंक
 PhotoFunia :: मियामी ऑलाक्ससिने येरेल हैबरलर Oyun यंग वीडियो
 PhotoFunia Monstelli'nin En isyi kisa.com.tr –Star थंडर एकरान
 PhotoFunia Seks - पोलिटिका, एकोनॉमी, स्पोर GTA SANAYİ VE
 PhotoFunia Taker-Rating Star TV Resmi Söylenen Yatağa każdy dziechn wierzchnie
 PhotoFunia TourIndex.Marketime oyunu Oyna Geldolları Mynet Spor, Magazin, Haberler yerel Haberleri ve Solvia, korkusuz Ev SahneTv
 फोटोफिनिया टॉडिस इन ग्राटीस पेर्कि पार्टि'निन याप्यी ब बु फोटोग्राम
 फोटोफुएन दुनीसैन तकीमेज़ हॉल एन कुल्लर - टीईजेड

परिणाम

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

प्रोग्राम को क्लिकहाउस-क्लाइंट के साथ स्थापित किया गया है, जिसमें कोई निर्भरता नहीं है, और लिनक्स के लगभग किसी भी स्वाद पर काम करता है। आप इसे ClickHouse ही नहीं, किसी भी डेटाबेस डंप पर लागू कर सकते हैं। उदाहरण के लिए, आप MySQL या PostgreSQL डेटाबेस से परीक्षण डेटा उत्पन्न कर सकते हैं या विकास डेटाबेस बना सकते हैं जो आपके उत्पादन डेटाबेस के समान हैं।

clickhouse-obfuscator \
--seed "$(head -c16 /dev/urandom | base64)" \
--input-format TSV --output-format TSV \
--structure 'CounterID UInt32, URLDomain String, \
URL String, SearchPhrase String, Title String' \
< table.tsv > result.tsv

clickhouse-obfuscator --help

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

अंत में, हमने कार्यात्मक और प्रदर्शन परीक्षण के लिए आवश्यक डेटा सेट और डेटा सुरक्षा अनुमोदित प्रकाशन के यैंडेक्स वीपी को बदल दिया।

clickhouse-datasets.s3.yandex.net/hits/tsv/hits_v1.tsv.xz
clickhouse-datasets.s3.yandex.net/visits/tsv/visits_v1.tsv.xz

गैर-यांडेक्स डेवलपर्स इस डेटा का उपयोग वास्तविक प्रदर्शन परीक्षण के लिए करते हैं जब क्लिकहाउस के अंदर एल्गोरिदम का अनुकूलन किया जाता है। तृतीय-पक्ष उपयोगकर्ता हमें उनके डेटा को सुरक्षित रूप से प्रदान कर सकते हैं ताकि हम उनके लिए ClickHouse को और भी तेज़ बना सकें। हमने इस डेटा के शीर्ष पर हार्डवेयर और क्लाउड प्रदाताओं के लिए स्वतंत्र खुला बेंचमार्क भी जारी किया: clickhouse.yandex/benchmark_hard.net.html

डेटाबेस में सुधार के लिए पाँच तरीके