Redis हैश टेबल स्कैन समझाया: तंत्र के अंदर

द्वारा एहुद तामिर

एक सॉफ्टवेयर डेवलपर के रूप में मेरे लिए बड़ी चुनौतियों में से एक दूसरे लोगों का कोड पढ़ना है। इस पोस्ट के लिए, मैंने C कोड का एक दिलचस्प टुकड़ा पढ़ा जिसे मैं पहले नहीं जानता था, और मैं इसे आपके सामने प्रस्तुत करने वाला हूं। जिस कोड के बारे में मैं बात करने जा रहा हूं वह Redis डेटाबेस का हिस्सा है, और यह यहां पाया जा सकता है।

Redis एक की-वैल्यू डेटाबेस है। डेटाबेस में हर एंट्री एक की से एक वैल्यू तक का मैपिंग है। वैल्यू के कई प्रकार हो सकते हैं। इंटीजर, लिस्ट, हैश टेबल और बहुत कुछ हैं। पर्दे के पीछे, डेटाबेस स्वयं भी एक हैश टेबल है। इस पोस्ट में, हम Redis में SCAN कमांड का पता लगाएंगे।

Redis SCAN

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

SCAN कमांड में कुछ दिलचस्प गुण हैं:

1. यह गारंटी देता है कि टेबल में मौजूद सभी आइटम कम से कम एक बार लौटाए जाएंगे।
2. यह स्टेटलेस है। टेबल अपने एक्टिव स्कैनर्स के बारे में कोई डेटा सेव नहीं करता। इसका यह भी अर्थ है कि स्कैन डेटाबेस को लॉक नहीं करते।
3. यह टेबल रीसाइज़िंग के प्रति लचीला है। O(1) एक्सेस टाइम बनाए रखने के लिए, हैश टेबल एक निश्चित लोड फैक्टर को बनाए रखते हैं। लोड फैक्टर मापता है कि किसी दिए गए समय पर टेबल कितना "भरा" है। जब लोड फैक्टर बहुत बड़ा या बहुत छोटा हो जाता है, तो टेबल का आकार बदला जाता है। SCAN अपनी गारंटी को बनाए रखेगा भले ही टेबल को रीसाइज़ करते समय कॉल किया जाए।

कार्यान्वयन

SCAN को dict.c में, फंक्शन dictScan() में लागू किया गया है। यह फंक्शन का सिग्नेचर और अतिरिक्त हाउसकीपिंग है:

unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, dictScanBucketFunction* bucketfn, void *privdata) {
    dictht *t0, *t1;
    const dictEntry *de, *next;
    unsigned long m0, m1;
    if (dictSize(d) == 0) return 0;
    // ...

ध्यान देने योग्य बातें:

• फंक्शन 5 पैरामीटर स्वीकार करता है: dict *d, स्कैन किया जाने वाला डिक्शनरी, unsigned long v, कर्सर, और 3 अन्य पैरामीटर जिन पर हम बाद में आएंगे।
• फंक्शन इस फंक्शन की अगली कॉल में उपयोग किए जाने वाले कर्सर वैल्यू को लौटाता है। यदि फंक्शन 0 लौटाता है, तो इसका मतलब है कि स्कैन पूरा हो गया है।
• if (dictSize(d) == 0) return 0;. जब डिक्शनरी खाली होती है तो फंक्शन 0 लौटाता है यह इंगित करने के लिए कि स्कैन पूरा हो गया है।

1. सामान्य स्कैनिंग

निम्न कोड तत्वों का एक गुच्छा स्कैन करता है:

if (!dictIsRehashing(d)) {
    t0 = &(d->ht[0]);
    m0 = t0->sizemask;
    /* कर्सर पर एंट्री उत्सर्जित करें */
    if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
    de = t0->table[v & m0];
    while (de) {
        next = de->next;
        fn(privdata, de);
        de = next;
    }
    /* अनमास्क्ड बिट्स सेट करें ताकि रिवर्स्ड कर्सर को बढ़ाने पर मास्क्ड बिट्स पर काम हो */
    v |= ~m0;
    /* रिवर्स कर्सर को बढ़ाएं */
    v = rev(v);
    v++;
    v = rev(v);
} else {
    // ...

आइए इसे चरण-दर-चरण समझें। पहली लाइन से शुरू करते हैं:

if (!dictIsRehashing(d)) {
    t0 = &(d->ht[0]);
    m0 = t0->sizemask;

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

हैश टेबल का एक पॉइंटर लोकल वेरिएबल t0 में सेव किया जाता है, और इसका साइज मास्क m0 में सेव किया जाता है। साइज मास्क: dict.c हैश टेबल हमेशा आकार में 2^n होते हैं। एक दिए गए टेबल आकार के लिए, साइज मास्क 2^n-1 होता है, जो एक बाइनरी नंबर है जिसके n लीस्ट-सिग्निफिकेंट बिट्स 1 पर सेट होते हैं। उदाहरण के लिए, n=4; 2^n-1 = 00001111 के लिए। एक दी गई की के लिए, हैश टेबल में इसकी लोकेशन की के हैश के अंतिम n बिट्स होगी। हम इसे थोड़ी देर में एक्शन में देखेंगे।

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

/* कर्सर पर एंट्री उत्सर्जित करें */
if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
de = t0->table[v & m0];
while (de) {
    next = de->next;
    fn(privdata, de);
    de = next;
}

साइज मास्क के उपयोग पर ध्यान दें: t0->table[v & m0]. v टेबल के इंडेक्सेबल रेंज के बाहर हो सकता है। v & m0 साइज मास्क का उपयोग करके v के केवल अंतिम n अंकों को रखता है, और टेबल में एक वैलिड इंडेक्स देता है।

आप अब तक अनुमान लगा चुके होंगे कि bucketfn किस लिए है। bucketfn कॉलर द्वारा प्रदान किया जाता है और प्रत्येक तत्व बकेट पर लागू किया जाता है। इसे privdata भी पास किया जाता है, जो कॉलर द्वारा dictScan() को पास किया गया मनमाना डेटा है। इसी तरह, fn को बकेट में सभी एंट्री पर एक-एक करके लागू किया जाता है। ध्यान दें कि एक बकेट खाली हो सकता है, जिस स्थिति में इसका वैल्यू NULL होता है।

ठीक है, तो हमने तत्वों के एक बकेट पर इटरेट किया। आगे क्या? हम अगली dictScan() कॉल के लिए कर्सर वैल्यू लौटाने जा रहे हैं। यह वर्तमान कर्सर v को बढ़ाकर किया जाता है, लेकिन एक ट्विस्ट के साथ! कर्सर को पहले उल्टा किया जाता है, फिर बढ़ाया जाता है, और फिर फिर से उल्टा किया जाता है:

/* अनमास्क्ड बिट्स सेट करें ताकि रिवर्स्ड कर्सर को बढ़ाने पर मास्क्ड बिट्स पर काम हो */
v |= ~m0;
/* रिवर्स कर्सर को बढ़ाएं */
v = rev(v);
v++;
v = rev(v);

सबसे पहले, v |= ~m0 v में सभी नॉन-मास्क्ड बिट्स को 1 पर सेट करता है। प्रभाव यह है कि जब v को उल्टा करके बढ़ाया जाता है, तो ये बिट्स प्रभावी रूप से नजरअंदाज हो जाएंगे। फिर, v को उल्टा किया जाता है, बढ़ाया जाता है, और फिर से उल्टा किया जाता है। आइए एक उदाहरण देखें:

टेबल आकार = 16 (n = 4, m0 = 16-1 = 00001111)
v = 00001000 (वर्तमान कर्सर)
v |= ~m0; // v == 11111000 (~m0 = 11110000)
v = rev(v); // v == 00011111
v++; // v == 00100000
v = rev(v); // v == 00000100

इस बिट-मैजिक के बाद, v लौटाया जाता है।

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

उदाहरण के लिए: मान लें कि पुराने टेबल का आकार 16 था (साइज मास्क 00001111) और कर्सर 00001000 था। जब टेबल 32 तत्वों तक बढ़ता है तो इसका साइज मास्क 00011111 होगा। 00001000 स्लॉट में पहले मौजूद सभी तत्व नए टेबल में या तो 00001000 या 00011000 पर मैप होंगे। ये कर्सर छोटे और बड़े दोनों टेबल के साथ संगत हैं!

2. टेबल रीहैशिंग के दौरान स्कैनिंग

हमें समझने की आखिरी बात यह है कि टेबल रीहैशिंग के दौरान स्कैन कैसे काम करता है। इन्क्रीमेंटल रीहैशिंग को dict.c में एक ही समय में दो एक्टिव टेबल रखकर लागू किया गया है। जब हैश टेबल का आकार बदला जाता है तो एक दूसरा टेबल बनाया जाता है। नए आइटम नए टेबल में जोड़े जाते हैं। हर रीहैश चरण पर पुराने टेबल से तत्व नए टेबल में ले जाए जाते हैं। जब पुराना टेबल खाली हो जाता है तो इसे हटा दिया जाता है।

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

} else {
    // dictIsRehashing(d)
    t0 = &d->ht[0];
    t1 = &d->ht[1];
    /* सुनिश्चित करें कि t0 छोटा और t1 बड़ा टेबल है */
    if (t0->size > t1->size) {
        t0 = &d->ht[1];
        t1 = &d->ht[0];
    }
    m0 = t0->sizemask;
    m1 = t1->sizemask;
    /* कर्सर पर एंट्री उत्सर्जित करें */
    if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
    de = t0->table[v & m0];
    while (de) {
        next = de->next;
        fn(privdata, de);
        de = next;
    }
    /* बड़े टेबल में उन इंडेक्स पर इटरेट करें जो छोटे टेबल में कर्सर द्वारा इंगित इंडेक्स के विस्तार हैं */
    do {
        /* कर्सर पर एंट्री उत्सर्जित करें */
        if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
        de = t1->table[v & m1];
        while (de) {
            next = de->next;
            fn(privdata, de);
            de = next;
        }
        /* छोटे मास्क द्वारा कवर नहीं किए गए रिवर्स कर्सर को बढ़ाएं */
        v |= ~m1;
        v = rev(v);
        v++;
        v = rev(v);
        /* जारी रखें जब तक मास्क अंतर द्वारा कवर किए गए बिट्स नॉन-जीरो हैं */
    } while (v & (m0 ^ m1));
}

सबसे पहले, t0 और t1 का उपयोग छोटे और बड़े टेबल को क्रमशः स्टोर करने के लिए किया जाता है, जिसमें m0 और m1 प्रत्येक के लिए साइज मास्क हैं। फिर छोटे टेबल को स्कैन किया जाता है, ठीक वैसे ही जैसे हमने पहले देखा था।

अगला, कर्सर का उपयोग बड़े टेबल में इंडेक्स करने के लिए किया जाता है, बड़े साइज मास्क m1 का उपयोग करके: de = t1->table[v & m1]. आंतरिक लूप में, कर्सर को छोटे टेबल के इंडेक्स के सभी विस्तार को कवर करने के लिए बढ़ाया जाता है।

उदाहरण के लिए, यदि छोटे टेबल में बकेट का इंडेक्स 0100 था, और बड़ा टेबल दोगुना बड़ा है, तो इस लूप में कवर किए गए इंडेक्स 00100 और 10100 होंगे। डू-व्हाइल की कंडीशन कर्सर को छोटे टेबल के बकेट द्वारा कवर की गई रेंज से आगे बढ़ने से रोकती है: while (v & (m0 ^ m1));. मैं इसे समझने के लिए आप पर छोड़ दूंगा :)

बस! हमने पूरे हैश टेबल स्कैन फंक्शन को कवर कर लिया है। एकमात्र गायब टुकड़ा rev(v) का कार्यान्वयन है, जो एक संख्या में बिट्स को उल्टा करने के लिए एक सामान्य फंक्शन है। dict.c में उपयोग किया गया कार्यान्वयन विशेष रूप से दिलचस्प है क्योंकि यह O(log n) रनिंग टाइम प्राप्त करता है। मैं इसे भविष्य की पोस्ट में कवर कर सकता हूं।

पढ़ने के लिए धन्यवाद! Dvir Volk को उनकी प्रेरणा और समर्थन के लिए बहुत धन्यवाद! Jason Li को उनकी प्रतिक्रिया के लिए धन्यवाद जिसने मुझे पोस्ट में एक त्रुटि को सही करने में मदद की।

मुफ़्त में कोड करना सीखें। freeCodeCamp का ओपन सोर्स पाठ्यक्रम 40,000 से अधिक लोगों को डेवलपर के रूप में नौकरी पाने में मदद कर चुका है। शुरू करें