जावा: कुंजी संक्षेप के साथ निष्पादक

संदेश प्रवाह को संसाधित करते समय होने वाले कार्यों की एक बड़ी श्रेणी में एक विशिष्ट समस्या है:

- आप एक छोटे से पाइप के माध्यम से एक बड़े हाथी को धक्का नहीं दे सकते हैं, या दूसरे शब्दों में, संदेश प्रसंस्करण में सभी संदेशों को "निगल" करने का समय नहीं है।

हालाँकि, डेटा प्रवाह पर कुछ प्रतिबंध हैं:

• धारा एकसमान नहीं है और इसमें विभिन्न प्रकार की घटनाएं शामिल हैं
• घटना प्रकारों की संख्या पहले से ज्ञात नहीं है, लेकिन कुछ परिमित संख्या है
• प्रत्येक प्रकार की घटना की अपनी प्रासंगिकता होती है
• सभी घटना प्रकारों की समान प्राथमिकता है

आरेख समस्या को हल करने का एक उदाहरण दिखाता है: एक थ्रेड बार पर tread bar (tm) t ₁ चल रहा है, जबकि tug बार (tm) एक थ्रेड T ₂ पर चल रहा है

• टाइप ए की घटनाओं के प्रसंस्करण के दौरान , बी और ए दोनों प्रकार की नई घटनाओं के आने का समय है
• प्रकार बी की एक घटना को संसाधित करने के बाद , टाइप ए की सबसे प्रासंगिक घटना को संसाधित करना आवश्यक है

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

हमारे द्वारा बनाया गया थ्रॉटलिंग एक्सिक्यूटर जनता के सामने प्रस्तुत किया गया है।

शब्दावली नोट: स्ट्रीम एक डेटा स्ट्रीम है , जबकि थ्रेड एक थ्रेड या निष्पादन का एक धागा है । और धागे के साथ धागे को भ्रमित न करें।

टिप्पणी 1: समस्या इस तथ्य से और जटिल है कि कई टग (टीएम) हो सकते हैं, जबकि प्रत्येक टग (टीएम) एक ही प्रकार की घटनाओं को उत्पन्न कर सकता है; दूसरी ओर, कई की आवश्यकता है (ज़ाहिर है, सादगी के लिए, आप एन = 1 ) मचान (टीएम) चुन सकते हैं।

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

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

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

हालाँकि, कोड अभी तक सार्वजनिक रूप से नहीं खोला जा सकता है, इसलिए विचार सामान्य हैं और कई अन्य प्रोग्रामिंग भाषाओं में इसे लागू और लागू किया जा सकता है।

चूंकि सब कुछ पहले से ही क्रम में है, और शायद यह एक छोटी सी मारफेट लाने के लिए बनी हुई है, मैं निर्णय के प्रमुख बिंदुओं का वर्णन करूंगा।

इसलिए, चारों ओर देखने पर, हम यह नहीं खोज सके कि हम jdk में उपलब्ध उच्च-स्तरीय डेटा संरचनाओं के साथ क्या करना चाहते हैं, इसलिए हम सबसे बुनियादी ब्लॉकों से निर्माण करेंगे।

एक पूरे के रूप में डिजाइन चित्र:

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

सहयोगी सरणी

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

हैश संरचना के प्रदर्शन पर नकारात्मक प्रभाव, चयनित आकार में हैश कोड पर टकराव होता है। दो सबसे आम टक्कर संकल्प विधियाँ हैं:

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

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

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

आवेदन की उपयुक्तता के सामान्य सिद्धांतों के आधार पर, हम सुरक्षित रूप से उम्मीद कर सकते हैं कि हैश कोड के कार्य में गिरावट नहीं होगी और विकल्प खुले पते पर आता है।

अब एक सरणी तत्व पर विचार करें:

परमाणु refs

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

static class Entry<K> extends AtomicReference { final K key; public Entry(final K key){ this.key = key; } } 

परमाणु सरणी रेफरी

स्मृति की स्थिरता और परमाणुता सुनिश्चित करने के लिए एक और दृष्टिकोण एटॉमिकरेंस एरे का उपयोग नहीं करना है, बल्कि एक एटॉमिकरेंस ऐरे है ।

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

कार्ड का निशान

मुख्य विचार: सभी तत्वों पर नहीं, बल्कि केवल बदले हुए तत्वों (आदर्श रूप से), या खंडों (तत्वों की एक छोटी उचित संख्या से मिलकर) पर संशोधित तत्व होते हैं।

साधारण कार्ड का निशान

मास्क के रूप में एटॉमिकलॉन्ग का उपयोग करने वाला एक आसान-से-लागू दृष्टिकोण, 64 परिवर्तित क्षेत्रों को कवर करने की अनुमति देता है।

हालांकि, पहले से ही 4096 तत्वों के एक सरणी आकार के साथ, खंड में 64 तत्व शामिल हैं, अर्थात्। संभावित रूप से, कई खाली रीडिंग बनाई जा सकती हैं।

बाइनरी हीप कार्ड मार्क

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

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

इसलिए, यदि कोई दूसरा स्तर और 4096 तत्वों का एक सरणी आकार है, तो खंड में ठीक एक तत्व शामिल है।

इस प्रकार साधारण कार्ड मार्क छोटे सरणी आकार के लिए अच्छा होना चाहिए, और बड़े आकार के लिए बाइनरी हीप कार्ड मार्क ।

प्रतीक्षा की रणनीति

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

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

हालाँकि, रणनीति प्रत्येक मामले में भिन्न हो सकती है।

टोटके और टोटके

• सरणी और बाइनरी हीप के आकार को 2 ^{K के} रूप में बनाए रखते हुए ^, आप विभाजन , गुणन और मॉड संचालन के उपयोग से बच सकते हैं और सस्ते बिट समकक्षों का उपयोग कर सकते हैं: दाएं शिफ्ट K , बाएं शिफ्ट K और बिट मास्क का उपयोग ((1 << K - 1 ) क्रमशः)
• स्थिर चरण में मुख्य और सबसे अधिक बार होने वाला ऑपरेशन - / रिप्लेसमेंट ऑपरेशन केवल बिना किसी मॉनिटर को कैप्चर किए सरणी के पाए गए तत्व के लिए CAS के कारण होता है।
• बिना शर्त गेट -एंड-सेट (0) के बजाय सेल या कार्ड के निशान से मूल्य घटाना कभी-कभी (जब सरणी कम होती है) तो अनावश्यक (और अधिक महंगा) अस्थिर लिखने से बचने के लिए टेस्ट-एन-गेट-एन-सेट बनाना अधिक उचित है।
• सरणी विस्तार / संकुचन ( जेएमएम शुद्धता के संदर्भ में) प्रारंभिक चरण को संदर्भित करता है
  
  • अस्थिर सरणी संदर्भ - तेजी से वाष्पशील पढ़ा
  • AtomicReferenceFieldUpdater जादू का उपयोग करके अस्थिर लिंक को अपडेट करना
  • यह देखते हुए कि कुंजियों की संख्या सीमित है, आप मॉनिटर के तहत सरणी को स्केल कर सकते हैं
  
  

अंतिम विलंबता वितरण ग्राफ़ में:

• 1 डिगर (टीएम) - 1 डिगर (टीएम)
• 700 अद्वितीय कुंजी, हैश टकराव <1%
• जेवीएम वार्म-अप: विलंबता को मापने पर 20,000 पहले पुनरावृत्तियों को अनदेखा किया जाता है
• कार्य निष्पादनकर्ता को हस्तांतरित: निष्पादक के माध्यम से पारित होने के समय (माइक्रोसेकंड में) को ठीक करें - अर्थात विलंबता को ठीक करें

ThrottlingExecutor में विलंबता वितरण हिस्टोग्राम,
साधारण कार्ड का निशान, आकार 4096


ThrottlingExecutor में विलंबता वितरण हिस्टोग्राम,
बाइनरी हीप पर कार्ड का निशान, आकार 4096

एक बहुत विरल सरणी में:

ThrottlingExecutor में विलंबता वितरण हिस्टोग्राम,
सरल कार्ड चिह्न, आकार 16384


ThrottlingExecutor में विलंबता वितरण हिस्टोग्राम,
बाइनरी हीप पर कार्ड का निशान, आकार 16384

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

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

पुनश्च यह ध्यान देने योग्य है कि इस बेंचमार्क में पिछले थ्रॉटलिंग एक्सिक्यूटर समाधानों का परीक्षण करते समय, उन्होंने लगभग 300 μs तक का वितरण दिया।