👨🏿‍🤝‍👨🏾 📜 🧑🏻 प्रदर्शन परीक्षणों के लिए डेटा का विरोध 🤫 👇🏿 🏴‍☠️

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

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

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

2016 में ClickHouse के ओपन सोर्स में शामिल होने के बाद, परीक्षणों के लिए अधिक प्रश्न थे।

मालिकाना डेटा पर परीक्षणों का नुकसान

प्रदर्शन परीक्षण:

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

आप इन समस्याओं को हल कर सकते हैं - पुराने परीक्षण बाहर फेंक सकते हैं और खुले डेटा के आधार पर नए बना सकते हैं। खुले डेटा के बीच, आप यूएसए की उड़ानों , न्यूयॉर्क में टैक्सी की सवारी, या तैयार बेंचमार्क टीपीसी-एच, टीपीसी-डीएस, स्टार स्कीमा बेंचमार्क का उपयोग कर सकते हैं । असुविधा यह है कि यह डेटा 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 सबसे अच्छा विकल्प नहीं है। ओपन-एड्रेसिंग हैश टेबलों का उपयोग करते समय, हैश फ़ंक्शन का सही विकल्प निर्णायक कारक बन जाता है, और हम ट्रिवियल हैश फ़ंक्शन का उपयोग नहीं कर सकते हैं।

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

रिपोर्ट में इसके बारे में और अधिक पढ़ें "कैसे हाशिये में क्लिकहाउस व्यवस्थित हैं" । यह थोड़ा पुराना है क्योंकि यह स्विस टेबल पर विचार नहीं करता है।

कार्य

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

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

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

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

यह समस्या का एक अनौपचारिक बयान है। हालांकि, कोई भी औपचारिक बयान देने वाला नहीं था।

हल निकालने का प्रयास

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

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

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

पाठ क्षेत्रों के लिए, आप मार्कोव श्रृंखला का उपयोग कर सकते हैं - एक समझदार मॉडल जिसके लिए आप एक प्रभावी कार्यान्वयन कर सकते हैं।

सच है, कुछ ट्रिक्स आवश्यक हैं:

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

यह सब एक कार्यक्रम के रूप में प्रस्तुत किया गया है जिसमें सभी वितरण और निर्भरताएं कठिन कोडित हैं - तथाकथित "सी ++ स्क्रिप्ट"। हालांकि, मार्कोव मॉडल की गणना आँकड़ों के योग से की जाती है, शोर का उपयोग करके इसे चौरसाई और मोटा करना। मैंने यह स्क्रिप्ट लिखना शुरू किया, लेकिन किसी कारण से, मैंने स्पष्ट रूप से दस कॉलम के लिए मॉडल लिखने के बाद, यह अचानक असहनीय रूप से उबाऊ हो गया। और 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(); };

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

लाभ:

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

नुकसान:

कार्यान्वयन की जटिलता,
कार्यान्वित समाधान केवल एक प्रकार के डेटा के लिए उपयुक्त है।

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

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

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

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

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

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

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

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

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

सच है, कठिनाइयों का पता चला था:

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

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

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

संकुचित डेटा म्यूटेशन

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

सीधे संपीड़ित फ़ाइल को कैसे संपादित करें? मान लीजिए कि हम केवल LZ4 में रुचि रखते हैं। LZ4 के उपयोग से संकुचित डेटा में दो प्रकार के निर्देश होते हैं:

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

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

संपीड़ित डेटा (सशर्त रूप से):
literals 12 "Hello world " match 5 12 ।

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

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

अशक्त बाइट्स और ASCII नियंत्रण वर्ण के रूप में संग्रहीत किया गया था,
कुछ विराम चिह्नों को जारी रखा,
ASCII का एएससीआईआई में अनुवाद किया गया था, और बाकी के लिए, सबसे महत्वपूर्ण बिट को बचाया गया था (या आप स्पष्ट रूप से अलग यूटीएफ -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 डी गेम में नायक की मौत के दृश्य का प्रतिपादन करने के लिए एल्गोरिदम का विश्लेषण था।

सुंदर एनीमेशन - स्क्रीन रक्त से भर जाती है। लेख बताता है कि यह वास्तव में एक छद्म यादृच्छिक क्रमांकन है। रैंडम क्रमपरिवर्तन - एक सेट के एक बेतरतीब ढंग से चयनित एक-से-एक परिवर्तन। यही है, पूरे सेट का प्रदर्शन जिसमें विभिन्न तर्कों के लिए परिणाम दोहराए नहीं जाते हैं। दूसरे शब्दों में, यह एक यादृच्छिक क्रम में एक सेट के सभी तत्वों पर पुनरावृति करने का एक तरीका है। यह ऐसी प्रक्रिया है जो तस्वीर में दिखाई जाती है - हम प्रत्येक पिक्सेल पर पेंट करते हैं, पुनरावृत्ति के बिना, सभी से यादृच्छिक रूप से चयनित। अगर हम हर कदम पर एक यादृच्छिक पिक्सेल चुनते हैं, तो हमें पिछले एक से अधिक समय लगेगा।

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

छद्म यादृच्छिक क्रमचय प्राप्त करने के तरीके क्या हैं? आप सरल, एक-से-एक परिवर्तन ले सकते हैं और उनमें से एक काफी जटिल फ़ंक्शन को इकट्ठा कर सकते हैं जो यादृच्छिक लगेगा। मुझे आपके कुछ पसंदीदा एक-से-एक परिवर्तनों का उदाहरण दें:

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

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

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

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

यह ध्यान देने योग्य है कि सभी अज्ञातताओं का संरक्षण डेटा गुमनामी की समस्या के बयान के विपरीत है। , , , 10 , . 10 — , . , , , — , , . . , , , Google, , - Google. — , , ( ) ( ). , , .

, . , 10, . ?

, size classes ( ). size class , . 0 1 . 2 3 1/2 1/2 . 1024..2047 1024! () . और इसी तरह। .

, . , -. , .

, , , .

— , . . . Fabien Sanglard c Hackers News , . Redis — . , .

. — , . , .

:
arg: xxxxyyyy arg_l : xxxx arg_r : yyyy
. xor :
res: yyyyzzzz res_l = yyyy = arg_r res_r = zzzz = arg_l ^ F( arg_r )

, F 4 , .

: , , — , , !

. , , , . :

, , Electronic Codebook mode of operation;
( ) , , .

. , LZ4 , , .

, , , . — . , , , . ( , ). ?

-, : , 256^10 10 , , . -, , .

, . , , . , . , - .

, — , N . N — . , N = 5, «» «». Order-N.

P( | ) = 0.9
P( | ) = 0.05
P( | ) = 0.01
...

. ( vesna.yandex.ru). LSTM, N, , . — , . : , , .

Title:

— . — , . , , — .@Mail.Ru — — - . ) — AUTO.ria.ua

, , . () , — . 0 N, 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 ...

, . :

 -        | . -    
-  — .:      Lore - dfghf — . -   )  473682  -  
- !   »  -  —      
- !   » , 
-  .  c      @Mail.Ru - 
-     ,  2010 |  . 
- !    : 820 0000 .,    -
-   - DoramaTv.ru -   . -  ..    
-  .  2013 ,       ->  80 .
-  -    (.    , ,  
-   . 5, 69,  W* - ., ,      World of Tanks
- ,     . 2     @Mail.Ru
-      ,  .

परिणाम

, - , - . , . clickhouse obfuscator, : (, CSV, JSONEachRow), ( ) ( , ). .

clickhouse-client, Linux. , 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 .

प्रदर्शन परीक्षणों के लिए डेटा का विरोध