रेडिस `स्कैन`:नई आने वाली चाबियों के बीच संतुलन कैसे बनाए रखें जो उचित समय में अंतिम परिणाम से मेल खा सकें और सुनिश्चित कर सकें?

पहले कुछ संदर्भ, अंत में समाधान :

स्कैन कमांड से> टर्मिनेशन की गारंटी

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

यह सहज रूप से देखना आसान है:यदि संग्रह बढ़ता है तो सभी संभावित तत्वों का दौरा करने के लिए और अधिक काम करना है, और पुनरावृत्ति को समाप्त करने की क्षमता स्कैन पर कॉल की संख्या और इसके COUNT विकल्प मूल्य पर दर की तुलना में निर्भर करती है। जो संग्रह बढ़ता है।

लेकिन COUNT विकल्प में यह कहता है:

महत्वपूर्ण:प्रत्येक पुनरावृत्ति के लिए समान COUNT मान का उपयोग करने की कोई आवश्यकता नहीं है। कॉलर आवश्यकतानुसार एक पुनरावृत्ति से दूसरे में गिनती बदलने के लिए स्वतंत्र है, जब तक कि अगली कॉल में पास किया गया कर्सर कमांड के पिछले कॉल में प्राप्त होता है।

स्कैन गारंटी से ध्यान रखना महत्वपूर्ण है:

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

समाधान की कुंजी कर्सर में ही होती है। रेडिस के स्कैन कर्सर की समझ बनाना देखें। आपके स्कैन की प्रगति का प्रतिशत निकालना संभव है क्योंकि कर्सर वास्तव में तालिका के आकार के लिए एक इंडेक्स का बिट्स-रिवर्स है।

DBSIZE . का उपयोग करना या INFO keyspace कमांड आप किसी भी समय कितनी चाबियां प्राप्त कर सकते हैं:

> DBSIZE
(integer) 200032
> info keyspace
# Keyspace
db0:keys=200032,expires=0,avg_ttl=0

जानकारी का एक अन्य स्रोत अनिर्दिष्ट DEBUG htstats index . है , बस एक एहसास पाने के लिए:

> DEBUG htstats 0
[Dictionary HT]
Hash table 0 stats (main hash table):
 table size: 262144
 number of elements: 200032
 different slots: 139805
 max chain length: 8
 avg chain length (counted): 1.43
 avg chain length (computed): 1.43
 Chain length distribution:
   0: 122339 (46.67%)
   1: 93163 (35.54%)
   2: 35502 (13.54%)
   3: 9071 (3.46%)
   4: 1754 (0.67%)
   5: 264 (0.10%)
   6: 43 (0.02%)
   7: 6 (0.00%)
   8: 2 (0.00%)
[Expires HT]
No stats available for empty dictionaries

आपकी कुंजियों की संख्या के बाद तालिका का आकार 2 की शक्ति है:कुंजी:200032 => तालिका का आकार:262144

समाधान:

हम वांछित COUNT . की गणना करेंगे हर स्कैन के लिए तर्क।

मान लें कि आप SCAN को फ़्रीक्वेंसी के साथ कॉल करेंगे (F Hz में) 10 Hz (प्रत्येक 100 ms) और आप इसे 5 सेकंड में करना चाहते हैं (T एस में)। तो आप चाहते हैं कि यह N = F*T . में समाप्त हो जाए कॉल, N = 50 इस उदाहरण में।

आपके पहले स्कैन से पहले, आप जानते हैं कि आपकी वर्तमान प्रगति 0 है, इसलिए आपका शेष प्रतिशत RP = 1 है (100%)।

हर SCAN . से पहले कॉल (या प्रत्येक दी गई कॉल की संख्या जिसे आप अपना COUNT समायोजित करना चाहते हैं यदि आप DBSIZE के राउंड ट्रिप टाइम (RTT) को सहेजना चाहते हैं। कॉल करें), आप DBSIZE . पर कॉल करें कुंजियों की संख्या प्राप्त करने के लिए K .

आप उपयोग करेंगे COUNT = K*RP/N

पहली कॉल के लिए, यह COUNT = 200032*1/50 = 4000 . है ।

किसी अन्य कॉल के लिए, आपको RP = 1 - ReversedCursor/NextPowerOfTwo(K) की गणना करनी होगी .

उदाहरण के लिए, मान लें कि आप पहले ही 20 कॉल कर चुके हैं, तो अब N = 30 (बाकी कॉलों की संख्या)। आपने DBSIZE . को कॉल किया और मिला K = 281569 . इसका मतलब है NextPowerOfTwo(K) = 524288 , यह 2^19 है।

दशमलव में आपका अगला कर्सर 14509 है =000011100010101101 बाइनरी में। चूंकि तालिका का आकार 2^19 है, हम इसे 18 बिट्स के साथ दर्शाते हैं।

आप बिट्स को उल्टा करते हैं और 101101010001110000 get प्राप्त करते हैं बाइनरी में =185456 दशमलव में। इसका मतलब है कि हमने 524288 में से 185456 को कवर किया है। और:

RP = 1 - ReversedCursor/NextPowerOfTwo(K) = 1 - 185456 / 524288 = 0.65 or 65%

तो आपको एडजस्ट करना होगा:

COUNT = K*RP/N = 281569 * 0.65 / 30 = 6100

तो आपके अगले SCAN . में कॉल करें जिसका आप उपयोग करते हैं 6100 . समझ में आता है कि यह बढ़ गया क्योंकि:

• चाबियों की संख्या 200032 से बढ़कर 281569 हो गई है।
• हालांकि हमारे पास कॉल के शुरुआती अनुमान का केवल 60% शेष है, प्रगति पीछे है क्योंकि 65% कीस्पेस स्कैन किए जाने के लिए लंबित है।

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

COUNT = PM * K*RP/N

PM = keysFound / ( K * ReversedCursor/NextPowerOfTwo(K))

यदि 20 कॉल के बाद, आपको केवल keysFound = 2000 मिला है कुंजियाँ, तब:

PM = 2000 / ( 281569 * 185456 / 524288) = 0.02

इसका मतलब है कि अब तक केवल 2% कुंजियाँ हमारे पैटर्न से मेल खा रही हैं, इसलिए

COUNT = PM * K*RP/N = 0.02 * 6100 = 122

इस एल्गोरिथम में शायद सुधार किया जा सकता है, लेकिन आपको इसका अंदाजा हो गया है।

COUNT . पर कुछ बेंचमार्क चलाना सुनिश्चित करें आपका SCAN . कितने मिलीसेकंड का है, यह मापने के लिए आप जिस नंबर से शुरुआत करेंगे, उसका उपयोग करेंगे आपको कितनी कॉल की आवश्यकता है, इस बारे में आपको अपनी अपेक्षाओं को मॉडरेट करने की आवश्यकता हो सकती है (N ) सर्वर को ब्लॉक किए बिना उचित समय में ऐसा करने के लिए, और अपना F . समायोजित करें और T तदनुसार।