हम 100 बार अनुरोध को कैसे गति देते हैं, या सभी हैश फ़ंक्शन समान रूप से खराब नहीं हैं

हम एक डेटाबेस विकसित कर रहे हैं। एक बार, हमें एक कंपनी से संपर्क किया गया था जिसने निम्नलिखित कार्य का सामना किया था:



कुछ कई ऑब्जेक्ट हैं, और कुछ कई टैग हैं। प्रत्येक ऑब्जेक्ट में कई टैग हो सकते हैं। कुछ टैग बहुत दुर्लभ हैं, और कुछ सामान्य हैं। एक वस्तु को एक टैग के साथ कई बार जोड़ा जा सकता है।

नई वस्तुओं, टैग और उनके बीच लिंक लगातार जोड़े जाते हैं।

यह काम जल्दी से सवालों के जवाब देना है: "कितनी वस्तुओं का टैग A या B है, लेकिन कोई टैग C" और इसी तरह का नहीं है। मैं डेटा के लोडिंग को नहीं रोकते हुए एक सेकंड के दसवें हिस्से में ऐसे अनुरोधों का जवाब देना चाहूंगा।



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

SELECT COUNT(*) FROM ( SELECT object_id, (MAX(tag == A) OR MAX(tag == B)) AND MIN(tag != C) AS good FROM tags WHERE tag IN (A, B, C) GROUP BY object_id ) WHERE good == 1;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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

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



हमने क्लस्टर में सभी डेटा लोड किए, और अनुरोध लॉन्च किया। अनुरोध में 25 सेकंड लगे।



कुछ गड़बड़ हो गई।

सबसे पहले, हमने जहां समस्या हुई थी, उसे स्थानीय बनाने के लिए GROUP BY object_id को हटा दिया। अनुरोध 0.3 सेकंड में समाप्त हो गया। इसलिए डेटा पढ़ना काफी तेज है, और अधिक कुछ भी नेटवर्क पर प्रसारित नहीं होता है। समस्या हैश तालिका में कहीं है।

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

 uint64_t hash(uint64_t value) { return value * MULTIPLIER1; } uint64_t accumulateHash(uint64_t hash, uint64_t value) { hash ^= hash >> SHIFT1; hash += value; hash ^= hash >> SHIFT2; hash *= MULTIPLIER2; return hash; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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



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



इस समस्या से निपटने के लिए, मैंने एक टैग के लिए डेटा को स्थानीय मशीन पर डाउनलोड किया, और प्रयोग करना शुरू किया। दरअसल, हमारे वर्तमान हैश फ़ंक्शन ने टक्करों का उत्पादन किया: सभी मूल्यों में पांच उच्च बिट्स समान थे। हालांकि, अन्य SHIFT1 और SHIFT2 के साथ एक ही कार्य ने पहले से ही अच्छे परिणाम दिए हैं। तब मैंने यादृच्छिक 10 मिलियन संख्याएँ उत्पन्न कीं, और हमारे खराब हैश फ़ंक्शन का उपयोग करके हैश तालिका को फिर से बनाया। इस बार कोई असामान्य टक्कर भी नहीं थी। यही है, यादृच्छिक संख्याओं पर, हैश फ़ंक्शन अच्छा व्यवहार करता है, समस्या हमारे हैश फ़ंक्शन और उपयोगकर्ता डेटा के चौराहे पर कहीं है। उन्होंने उपयोगकर्ता डेटा में पैटर्न की तलाश शुरू की। पैटर्न हैं: वे सभी 64 से विभाजित हैं, और उन सभी में पांच उच्च बिट्स हैं। मैं यादृच्छिक संख्याओं का एक सेट उत्पन्न करता हूं जो 64 के गुणकों में एक ही उच्च पांच बिट्स के साथ होते हैं। नहीं, वैसे भी कोई टक्कर नहीं है। और क्या समस्या हो सकती है? क्या यह संभव है कि जिस तरह से वस्तुएं उत्पन्न होती हैं, वह किसी तरह हमारे हैश फ़ंक्शन का स्तर बनाएगी?



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

हां, यह वास्तव में एक ही कॉलम है। यह पता चला है कि कोड में एक बग के कारण, एक ही हैश फ़ंक्शन का उपयोग ग्रुप BY को विभाजन और निष्पादित करने के लिए किया गया था। चार भौतिक सर्वरों में से प्रत्येक में 8 विभाजन थे, कुल 32 विभाजन, विभाजन का चयन करने के लिए हैश फ़ंक्शन के उच्चतम बिट्स का उपयोग किया जाता है। नतीजतन, एक खंड में सभी पंक्तियों के लिए, object_id से हैश फ़ंक्शन मान के उच्च पांच बिट समान होंगे। जब हमने XOR और SHIFT को किसी फ़ंक्शन हैश में टिप्पणी की, और क्लस्टर को पुनरारंभ किया, तो हमने डेटा को फिर से लोड नहीं किया, जिससे यह प्रतीत होता है कि समस्या ठीक हो गई थी, क्योंकि अब डेटा को फ़ंक्शन के हैश द्वारा विभाजित किया गया था, जो कि ग्रुप BY के लिए उपयोग किए जाने से अलग था। लेकिन अगर हमने नवीनतम डेटा डाउनलोड करना शुरू कर दिया, तो अंत में समस्या ने खुद को फिर से महसूस किया होगा।



हमने हैश फ़ंक्शन को उस रूप में लौटाया जिसमें यह हिमस्खलन परीक्षण से गुजरता है, और विभाजन के लिए हैश फ़ंक्शन को बदल दिया, और हमारे सहयोगियों में से एक ने एक मज़ेदार कहानी साझा की: एक प्रोग्रामिंग प्रतियोगिता में, उन्होंने दो-आयामी दिशा-निर्देशों पर जावा में एक हैश टेबल बनाया। निर्देशांक प्रत्येक में 32 बिट्स की दो संख्याएं थीं, और कुशलता से काम करने के लिए कोड के लिए, उन्होंने उन्हें एक 64-बिट संख्या में लिख दिया, और उन्हें एक हैश तालिका में डाल दिया। दुर्भाग्य से, कार्य समय में पारित नहीं हुआ, क्योंकि जावा में हैश फ़ंक्शन ऊपरी और निचले 32 बिट्स के एक्सओआर की गणना करता है, जिससे हमेशा निर्देशांक के लिए समान मान प्राप्त होता है जिसके लिए एक्स वाई है।