कॉन्करेन्ट हैश टेबल: Difference between revisions

From Vigyanwiki
No edit summary
Line 4: Line 4:
कंकररेंट हैश टेबल्स [[समवर्ती कंप्यूटिंग|कंकररेंट कंप्यूटिंग]] में उपयोग के लिए एक प्रमुख [[समवर्ती डेटा संरचना|कंकररेंट डेटा संरचना]] का प्रतिनिधित्व करती हैं जो साझा डेटा के बीच गणना के लिए कई थ्रेड्स को अधिक कुशलता से सहयोग करने की अनुमति देती हैं।<ref name="maier" />
कंकररेंट हैश टेबल्स [[समवर्ती कंप्यूटिंग|कंकररेंट कंप्यूटिंग]] में उपयोग के लिए एक प्रमुख [[समवर्ती डेटा संरचना|कंकररेंट डेटा संरचना]] का प्रतिनिधित्व करती हैं जो साझा डेटा के बीच गणना के लिए कई थ्रेड्स को अधिक कुशलता से सहयोग करने की अनुमति देती हैं।<ref name="maier" />


कंकररेंट एक्सेस से जुड़ी प्राकृतिक समस्याओं के कारण - अर्थात् विवाद - जिस तरीके और दायरे से टेबल को कंकररेंट रूप से एक्सेस किया जा सकता है, वह कार्यान्वयन के आधार पर भिन्न होता है। इसके अलावा, परिणामस्वरूप होने वाली गति विवाद को हल करने के लिए उपयोग किए जाने वाले थ्रेड्स की मात्रा के साथ रैखिक नहीं हो सकती है, जिससे प्रोसेसिंग [[ओवरहेड (कंप्यूटिंग)|ओवरहेड]] का उत्पादन होता है।<ref name="maier" /> विवाद के प्रभावों को कम करने के लिए कई समाधान मौजूद हैं, जिनमें से प्रत्येक टेबल पर संचालन की शुद्धता को बनाए रखता है।<ref name="maier" /><ref name="shun" /><ref name="Li">
कंकररेंट एक्सेस से जुड़ी प्राकृतिक समस्याओं के कारण - अर्थात् विवाद - जिस तरीके और दायरे से टेबल को कंकररेंट रूप से एक्सेस किया जा सकता है, वह कार्यान्वयन के आधार पर भिन्न होता है। इसके अलावा, परिणामस्वरूप होने वाली गति विवाद को हल करने के लिए उपयोग किए जाने वाले थ्रेड्स की मात्रा के साथ रैखिक नहीं हो सकती है, जिससे प्रोसेसिंग [[ओवरहेड (कंप्यूटिंग)|ओवरहेड]] का उत्पादन होता है।<ref name="maier" /> विवाद के प्रभावों को कम करने के लिए कई समाधान उपस्थित हैं, जिनमें से प्रत्येक टेबल पर संचालन की शुद्धता को बनाए रखता है।<ref name="maier" /><ref name="shun" /><ref name="Li">
{{cite conference | last1 = Li | first1 = Xiaozhou | last2 = Andersen | first2 = David G. | last3 = Kaminsky | first3 = Michael | last4 = Freedman | first4 = Michael J. | year = 2014 | title = Algorithmic Improvements for Fast Concurrent Cuckoo Hashing | book-title = Proceedings of the Ninth European Conference on Computer Systems | conference = EuroSys '14 | isbn = 978-1-4503-2704-6 | at = Article No. 27 | doi = 10.1145/2592798.2592820 | publisher = ACM |location=New York}}</ref><ref name="Triplett">
{{cite conference | last1 = Li | first1 = Xiaozhou | last2 = Andersen | first2 = David G. | last3 = Kaminsky | first3 = Michael | last4 = Freedman | first4 = Michael J. | year = 2014 | title = Algorithmic Improvements for Fast Concurrent Cuckoo Hashing | book-title = Proceedings of the Ninth European Conference on Computer Systems | conference = EuroSys '14 | isbn = 978-1-4503-2704-6 | at = Article No. 27 | doi = 10.1145/2592798.2592820 | publisher = ACM |location=New York}}</ref><ref name="Triplett">
{{cite conference | last1 = Triplett | first1 = Josh  | last2 = McKenney | first2 = Paul E. | last3 = Walpole | first3 = Jonathan | year = 2011 | title = Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming | url = http://dl.acm.org/citation.cfm?id=2002181.2002192 | book-title = USENIXATC'11: Proceedings of the 2011 USENIX conference on USENIX annual technical conference | page = 11 | publisher = USENIX Association |location=Berkeley, CA}}</ref>
{{cite conference | last1 = Triplett | first1 = Josh  | last2 = McKenney | first2 = Paul E. | last3 = Walpole | first3 = Jonathan | year = 2011 | title = Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming | url = http://dl.acm.org/citation.cfm?id=2002181.2002192 | book-title = USENIXATC'11: Proceedings of the 2011 USENIX conference on USENIX annual technical conference | page = 11 | publisher = USENIX Association |location=Berkeley, CA}}</ref>


उनके अनुक्रमिक समकक्ष के साथ, कंकररेंट हैश तालिकाओं को सामान्यीकृत किया जा सकता है और व्यापक अनुप्रयोगों में फिट करने के लिए विस्तारित किया जा सकता है, जैसे कि कुंजी और मूल्यों के लिए अधिक जटिल डेटा प्रकारों का उपयोग करने की अनुमति देना। हालाँकि, ये सामान्यीकरण प्रदर्शन पर नकारात्मक प्रभाव डाल सकते हैं और इस प्रकार इन्हें एप्लिकेशन की आवश्यकताओं के अनुसार चुना जाना चाहिए।<ref name="maier" />
उनके अनुक्रमिक समकक्ष के साथ, कंकररेंट हैश टेबल्स को सामान्यीकृत किया जा सकता है और व्यापक अनुप्रयोगों में फिट करने के लिए विस्तारित किया जा सकता है, जैसे कि कुंजी और मूल्यों के लिए अधिक जटिल डेटा प्रकारों का उपयोग करने की अनुमति देना। हालाँकि, ये सामान्यीकरण प्रदर्शन पर नकारात्मक प्रभाव डाल सकते हैं और इस प्रकार इन्हें एप्लिकेशन की आवश्यकताओं के अनुसार चुना जाना चाहिए।<ref name="maier" />
==कंकररेंट हैशिंग==
==कंकररेंट हैशिंग==
कंकररेंट हैश टेबल्स बनाते समय, चुने हुए हैशिंग एल्गोरिथ्म के साथ टेबल तक पहुँचने वाले कार्यों को एक संघर्ष समाधान रणनीति जोड़कर कंकररेंट के लिए अनुकूलित करने की आवश्यकता होती है। इस तरह की रणनीति के लिए एक्सेस को इस तरह से प्रबंधित करने की आवश्यकता होती है कि उनके कारण होने वाले टकराव के परिणामस्वरूप भ्रष्ट डेटा न हो, जबकि आदर्श रूप से समानांतर में उपयोग किए जाने पर उनकी दक्षता बढ़ जाती है। हेर्लिही और शेविट[<ref>{{cite book |last1=Herlihy |first1=Maurice |last2=Shavit |first2=Nir |title=मल्टीप्रोसेसर प्रोग्रामिंग की कला|year=2008 |publisher=Morgan Kaufmann Publishers Inc. |location=San Francisco, CA, USA |isbn=978-0-12-370591-4 |pages=316–325 |chapter=Chapter 13: Concurrent Hashing and Natural Parallelism}}</ref> वर्णन करते हैं कि इस तरह की रणनीति के बिना हैश टेबल तक कैसे पहुंच बनाई जाती है - इसके उदाहरण में कुक्कू हैशिंग एल्गोरिदम के बुनियादी कार्यान्वयन पर आधारित है - कंकररेंट उपयोग फैन एट अल के लिए अनुकूलित किया जा सकता है।<ref name="Fan">{{cite conference | last1 = Fan | first1 = Bin | last2 = Andersen | first2 = David G. | last3 = Kaminsky | first3 = Michael | year = 2013 | title = MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing | url = http://dl.acm.org/citation.cfm?id=2482626.2482662 | book-title = nsdi'13: Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation | pages = 371–384 | publisher = USENIX Association |location=Berkeley, CA}}</ref> इसके अलावा, कुक्कू हैशिंग पर आधारित एक टेबल एक्सेस योजना का वर्णन करें जो न केवल कंकररेंट है बल्कि कैश इलाके के साथ-साथ सम्मिलन के थ्रूपुट में सुधार करते हुए अपने हैशिंग फ़ंक्शन की स्पेस दक्षता को भी बनाए रखती है।
कंकररेंट हैश टेबल्स बनाते समय, चुने हुए हैशिंग एल्गोरिथ्म के साथ टेबल तक पहुँचने वाले कार्यों को एक संघर्ष समाधान रणनीति जोड़कर कंकररेंट के लिए अनुकूलित करने की आवश्यकता होती है। इस तरह की रणनीति के लिए एक्सेस को इस तरह से प्रबंधित करने की आवश्यकता होती है कि उनके कारण होने वाले टकराव के परिणामस्वरूप भ्रष्ट डेटा न हो, जबकि आदर्श रूप से समानांतर में उपयोग किए जाने पर उनकी दक्षता बढ़ जाती है। हेर्लिही और शेविट[<ref>{{cite book |last1=Herlihy |first1=Maurice |last2=Shavit |first2=Nir |title=मल्टीप्रोसेसर प्रोग्रामिंग की कला|year=2008 |publisher=Morgan Kaufmann Publishers Inc. |location=San Francisco, CA, USA |isbn=978-0-12-370591-4 |pages=316–325 |chapter=Chapter 13: Concurrent Hashing and Natural Parallelism}}</ref> वर्णन करते हैं कि इस तरह की रणनीति के बिना हैश टेबल तक कैसे पहुंच बनाई जाती है - इसके उदाहरण में कुक्कू हैशिंग एल्गोरिदम के बुनियादी कार्यान्वयन पर आधारित है - कंकररेंट उपयोग फैन एट अल के लिए अनुकूलित किया जा सकता है।<ref name="Fan">{{cite conference | last1 = Fan | first1 = Bin | last2 = Andersen | first2 = David G. | last3 = Kaminsky | first3 = Michael | year = 2013 | title = MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing | url = http://dl.acm.org/citation.cfm?id=2482626.2482662 | book-title = nsdi'13: Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation | pages = 371–384 | publisher = USENIX Association |location=Berkeley, CA}}</ref> इसके अलावा, कुक्कू हैशिंग पर आधारित एक टेबल एक्सेस योजना का वर्णन करें जो न केवल कंकररेंट है बल्कि कैश इलाके के साथ-साथ सम्मिलन के थ्रूपुट में सुधार करते हुए अपने हैशिंग फ़ंक्शन की स्पेस दक्षता को भी बनाए रखती है।


जब हैश टेबल्स आकार में बंधी नहीं होती हैं और इस प्रकार आवश्यकता पड़ने पर उन्हें बढ़ने/घटने की अनुमति दी जाती है, तो इस ऑपरेशन को अनुमति देने के लिए हैशिंग एल्गोरिदम को अनुकूलित करने की आवश्यकता होती है। इसमें परिवर्तित टेबल के नए कुंजी स्थान को प्रतिबिंबित करने के लिए प्रयुक्त हैश फ़ंक्शन को संशोधित करना शामिल है। एक कंकररेंट बढ़ते एल्गोरिथ्म का वर्णन मैयर एट अल द्वारा किया गया है।<ref name="maier" />
जब हैश टेबल्स आकार में बंधी नहीं होती हैं और इस प्रकार आवश्यकता पड़ने पर उन्हें बढ़ने/घटने की अनुमति दी जाती है, तो इस ऑपरेशन को अनुमति देने के लिए हैशिंग एल्गोरिदम को अनुकूलित करने की आवश्यकता होती है। इसमें परिवर्तित टेबल के नए कुंजी स्थान को प्रतिबिंबित करने के लिए प्रयुक्त हैश फ़ंक्शन को संशोधित करना सम्मिलित है। एक कंकररेंट बढ़ते एल्गोरिथ्म का वर्णन मैयर एट अल द्वारा किया गया है।<ref name="maier" />


मेगा-केवी <ref>Zhang, Kai; Wang, Kaibo; Yuan, Yuan; Guo, Lei; Lee, Rubao; and Zhang, Xiaodong (2015). "[http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-15-1.pdf Mega-KV: a case for GPUs to maximize the throughput of in-memory key-value stores".] Proceedings of the VLDB Endowment, Vol. 8, No. 11, 2015.</ref> एक उच्च-प्रदर्शन कुंजी-मूल्य स्टोर सिस्टम है, जहां कुक्कू हैशिंग का उपयोग किया जाता है और केवी इंडेक्सिंग को जीपीयू द्वारा बैच मोड में बड़े पैमाने पर समानांतर किया जाता है। एनवीआईडीआईए और [[ओक रिज नेशनल लैब]] द्वारा जीपीयू त्वरण के और अनुकूलन के साथ, मेगा-केवी को 2018 में थ्रूपुट के एक और उच्च रिकॉर्ड (प्रति सेकंड 888 मिलियन कुंजी-मूल्य संचालन तक) तक पहुंचा दिया गया था।<ref>Chu, Ching-Hsing; Potluri, Sreeram; Goswami, Anshuman; Venkata, Manjunath Gorentla;  Imam, Neenaand; and Newburn, Chris J.  (2018) "[https://www.csm.ornl.gov/workshops/openshmem2018/presentations/openshmem2018-NVIDIA-ORNL.pdf Designing High-performance in-memory key-value operations with persistent GPU kernels and OPENSHMEM".].</ref>
मेगा-केवी <ref>Zhang, Kai; Wang, Kaibo; Yuan, Yuan; Guo, Lei; Lee, Rubao; and Zhang, Xiaodong (2015). "[http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/papers/TR-15-1.pdf Mega-KV: a case for GPUs to maximize the throughput of in-memory key-value stores".] Proceedings of the VLDB Endowment, Vol. 8, No. 11, 2015.</ref> एक उच्च-प्रदर्शन कुंजी-मूल्य स्टोर सिस्टम है, जहां कुक्कू हैशिंग का उपयोग किया जाता है और केवी इंडेक्सिंग को जीपीयू द्वारा बैच मोड में बड़े पैमाने पर समानांतर किया जाता है। एनवीआईडीआईए और [[ओक रिज नेशनल लैब]] द्वारा जीपीयू त्वरण के और अनुकूलन के साथ, मेगा-केवी को 2018 में थ्रूपुट के एक और उच्च रिकॉर्ड (प्रति सेकंड 888 मिलियन कुंजी-मूल्य संचालन तक) तक पहुंचा दिया गया था।<ref>Chu, Ching-Hsing; Potluri, Sreeram; Goswami, Anshuman; Venkata, Manjunath Gorentla;  Imam, Neenaand; and Newburn, Chris J.  (2018) "[https://www.csm.ornl.gov/workshops/openshmem2018/presentations/openshmem2018-NVIDIA-ORNL.pdf Designing High-performance in-memory key-value operations with persistent GPU kernels and OPENSHMEM".].</ref>


==कंटेन्शन हैंडलिंग==
==कंटेन्शन हैंडलिंग==
[[File:Concurrent hashtable conflict.svg|thumb|310px|right|कंकररेंट एक्सेस विवाद का कारण बन रही है (लाल रंग में चिह्नित)।]]किसी भी समवर्ती डेटा संरचना की तरह, समवर्ती हैश तालिकाएँ विवाद के परिणामस्वरूप समवर्ती कंप्यूटिंग के क्षेत्र में ज्ञात विभिन्न समस्याओं से ग्रस्त हैं।<ref name="Li" /> एबीए समस्या, रेस कंडीशन और गतिरोध इसके उदाहरण हैं। ये समस्याएँ किस हद तक प्रकट होती हैं या होती भी हैं, यह समवर्ती हैश तालिका के कार्यान्वयन पर निर्भर करता है; विशेष रूप से तालिका किस संचालन को एक साथ चलाने की अनुमति देती है, साथ ही विवाद से जुड़ी समस्याओं को कम करने के लिए इसकी रणनीतियाँ भी। विवाद को संभालते समय, मुख्य लक्ष्य किसी अन्य समवर्ती डेटा संरचना के समान ही होता है, अर्थात् तालिका पर प्रत्येक ऑपरेशन के लिए शुद्धता सुनिश्चित करना। साथ ही, इसे स्वाभाविक रूप से इस तरह से किया जाना चाहिए कि समवर्ती रूप से उपयोग किए जाने पर यह अनुक्रमिक समाधान से अधिक कुशल हो। इसे संगामिति नियंत्रण के रूप में भी जाना जाता है।
[[File:Concurrent hashtable conflict.svg|thumb|310px|right|कंकररेंट एक्सेस विवाद का कारण बन रही है (लाल रंग में चिह्नित)।]]किसी भी कंकररेंट डेटा संरचना की तरह, कंकररेंट हैश टेबल्स विवाद के परिणामस्वरूप कंकररेंट कंप्यूटिंग के क्षेत्र में ज्ञात विभिन्न समस्याओं से ग्रस्त हैं।<ref name="Li" /> एबीए समस्या, रेस कंडीशन और गतिरोध इसके उदाहरण हैं। ये समस्याएँ किस हद तक प्रकट होती हैं या होती भी हैं, यह कंकररेंट हैश टेबल के कार्यान्वयन पर निर्भर करता है; विशेष रूप से टेबल किस संचालन को एक साथ चलाने की अनुमति देती है, साथ ही विवाद से जुड़ी समस्याओं को कम करने के लिए इसकी रणनीतियाँ भी। विवाद को संभालते समय, मुख्य लक्ष्य किसी अन्य कंकररेंट डेटा संरचना के समान ही होता है, अर्थात् टेबल पर प्रत्येक ऑपरेशन के लिए शुद्धता सुनिश्चित करना। साथ ही, इसे स्वाभाविक रूप से इस तरह से किया जाना चाहिए कि कंकररेंट रूप से उपयोग किए जाने पर यह अनुक्रमिक समाधान से अधिक कुशल हो। इसे संगामिति नियंत्रण के रूप में भी जाना जाता है।
===परमाणु निर्देश===
===परमाणु निर्देश===
तुलना-और-स्वैप या फ़ेच-एंड-ऐड जैसे [[परमाणु (कंप्यूटर विज्ञान)|परमाणु]] निर्देशों का उपयोग करके, यह सुनिश्चित करके विवाद के कारण होने वाली समस्याओं को कम किया जा सकता है कि किसी अन्य एक्सेस को हस्तक्षेप करने का मौका मिलने से पहले एक्सेस पूरा हो जाए। तुलना-और-स्वैप जैसे संचालन अक्सर सीमाएं पेश करते हैं कि वे किस आकार के डेटा को संभाल सकते हैं, जिसका अर्थ है कि तालिका के कुंजियों और मूल्यों के प्रकार को तदनुसार चुना या परिवर्तित किया जाना चाहिए।<ref name="maier" />
तुलना-और-स्वैप या फ़ेच-एंड-ऐड जैसे [[परमाणु (कंप्यूटर विज्ञान)|परमाणु]] निर्देशों का उपयोग करके, यह सुनिश्चित करके विवाद के कारण होने वाली समस्याओं को कम किया जा सकता है कि किसी अन्य एक्सेस को हस्तक्षेप करने का मौका मिलने से पहले एक्सेस पूरा हो जाए। तुलना-और-स्वैप जैसे संचालन प्रायः सीमाएं पेश करते हैं कि वे किस आकार के डेटा को संभाल सकते हैं, जिसका अर्थ है कि टेबल के कुंजियों और मूल्यों के प्रकार को तदनुसार चुना या परिवर्तित किया जाना चाहिए।<ref name="maier" />


तथाकथित हार्डवेयर ट्रांजेक्शनल मेमोरी (एचटीएम) का उपयोग करते हुए, टेबल संचालन को [[डेटाबेस लेनदेन|डेटाबेस]] विनिमय की तरह सोचा जा सकता है, <ref name="Li" /> परमाणुता सुनिश्चित करना। व्यवहार में एचटीएम का एक उदाहरण ट्रांजेक्शनल सिंक्रोनाइजेशन एक्सटेंशन है।
तथाकथित हार्डवेयर ट्रांजेक्शनल मेमोरी (एचटीएम) का उपयोग करते हुए, टेबल संचालन को [[डेटाबेस लेनदेन|डेटाबेस]] विनिमय की तरह सोचा जा सकता है, <ref name="Li" /> परमाणुता सुनिश्चित करना। व्यवहार में एचटीएम का एक उदाहरण ट्रांजेक्शनल सिंक्रोनाइजेशन एक्सटेंशन है।


===लॉकिंग===
===लॉकिंग===
लॉक्स की मदद से, तालिका या उसके भीतर के मूल्यों तक एक साथ पहुंचने की कोशिश करने वाले संचालन को इस तरह से नियंत्रित किया जा सकता है जो सही व्यवहार सुनिश्चित करता है। हालाँकि, इससे प्रदर्शन पर नकारात्मक प्रभाव पड़ सकता है,<ref name="maier" /><ref name="Fan" /> विशेष रूप से जब उपयोग किए गए ताले बहुत अधिक प्रतिबंधात्मक होते हैं, इस प्रकार उन पहुंचों को अवरुद्ध कर देते हैं जो अन्यथा प्रतिस्पर्धा नहीं कर सकते थे और बिना किसी समस्या के निष्पादित हो सकते थे। और भी गंभीर समस्याओं से बचने के लिए आगे विचार करना होगा जो शुद्धता को खतरे में डालती हैं, जैसे कि लाइवलॉक, गतिरोध या अप्राप्ति।<ref name="Li" />
लॉक्स की मदद से, टेबल या उसके भीतर के मूल्यों तक एक साथ पहुंचने की कोशिश करने वाले संचालन को इस तरह से नियंत्रित किया जा सकता है जो सही व्यवहार सुनिश्चित करता है। हालाँकि, इससे प्रदर्शन पर नकारात्मक प्रभाव पड़ सकता है,<ref name="maier" /><ref name="Fan" /> विशेष रूप से जब उपयोग किए गए ताले बहुत अधिक प्रतिबंधात्मक होते हैं, इस प्रकार उन पहुंचों को अवरुद्ध कर देते हैं जो अन्यथा प्रतिस्पर्धा नहीं कर सकते थे और बिना किसी समस्या के निष्पादित हो सकते थे। और भी गंभीर समस्याओं से बचने के लिए आगे विचार करना होगा जो शुद्धता को खतरे में डालती हैं, जैसे कि लाइवलॉक, गतिरोध या अप्राप्ति।<ref name="Li" />
===फेज कंकर्रेंसी===
===फेज कंकर्रेंसी===
[[File:Phase concurrent hashtable.svg|thumb|310px|right|कंकररेंट एक्सेस को अलग-अलग चरणों में समूहीकृत किया गया।]]फेज कंकररेंट हैश टेबल समूह फेज बनाकर पहुँचता है जिसमें केवल एक प्रकार के ऑपरेशन की अनुमति होती है (यानी एक शुद्ध लेखन-फेज), इसके बाद सभी थ्रेड्स में टेबल स्थिति का सिंक्रनाइज़ेशन (कंप्यूटर विज्ञान) होता है। इसके लिए एक औपचारिक रूप से सिद्ध एल्गोरिदम शुन और ब्लेलोच द्वारा दिया गया है।<ref name="shun" />
[[File:Phase concurrent hashtable.svg|thumb|310px|right|कंकररेंट एक्सेस को अलग-अलग चरणों में समूहीकृत किया गया।]]फेज कंकररेंट हैश टेबल समूह फेज बनाकर पहुँचता है जिसमें केवल एक प्रकार के ऑपरेशन की अनुमति होती है (यानी एक शुद्ध लेखन-फेज), इसके बाद सभी थ्रेड्स में टेबल स्थिति का सिंक्रनाइज़ेशन (कंप्यूटर विज्ञान) होता है। इसके लिए एक औपचारिक रूप से सिद्ध एल्गोरिदम शुन और ब्लेलोच द्वारा दिया गया है।<ref name="shun" />
===रीड-कॉपी-अपडेट===
===रीड-कॉपी-अपडेट===


[[लिनक्स कर्नेल]] के भीतर व्यापक रूप से उपयोग किया जाता है, <ref name="Li" /> रीड-कॉपी-अपडेट (आरसीयू) उन मामलों में विशेष रूप से उपयोगी होता है जहां रीड की संख्या लिखने की संख्या से कहीं अधिक होती है।<ref name="Triplett" />
[[लिनक्स कर्नेल]] के भीतर व्यापक रूप से उपयोग किया जाता है, <ref name="Li" /> रीड-कॉपी-अपडेट (आरसीयू) उन स्थितियों में विशेष रूप से उपयोगी होता है जहां रीड की संख्या लिखने की संख्या से कहीं अधिक होती है।<ref name="Triplett" />
==अनुप्रयोग==
==अनुप्रयोग==
स्वाभाविक रूप से, जहां भी अनुक्रमिक हैश टेबल उपयोगी होते हैं, वहां समवर्ती हैश टेबल का अनुप्रयोग होता है। समवर्तीता से जो लाभ मिलता है, वह इन उपयोग-मामलों की संभावित गति के साथ-साथ बढ़ी हुई स्केलेबिलिटी के भीतर निहित है।<ref name="maier" /> [[मल्टी-कोर प्रोसेसर]] जैसे हार्डवेयर को ध्यान में रखते हुए, जो समवर्ती गणना के लिए तेजी से अधिक सक्षम हो जाते हैं, इन अनुप्रयोगों के भीतर समवर्ती डेटा संरचनाओं का महत्व लगातार बढ़ता है।<ref name="Li" />  
स्वाभाविक रूप से, जहां भी अनुक्रमिक हैश टेबल उपयोगी होते हैं, वहां कंकररेंट हैश टेबल का अनुप्रयोग होता है। समवर्तीता से जो लाभ मिलता है, वह इन उपयोग-स्थितियों की संभावित गति के साथ-साथ बढ़ी हुई स्केलेबिलिटी के भीतर निहित है।<ref name="maier" /> [[मल्टी-कोर प्रोसेसर]] जैसे हार्डवेयर को ध्यान में रखते हुए, जो कंकररेंट गणना के लिए तेजी से अधिक सक्षम हो जाते हैं, इन अनुप्रयोगों के भीतर कंकररेंट डेटा संरचनाओं का महत्व लगातार बढ़ता है।<ref name="Li" />  
==निष्पादन विश्लेषण==
==निष्पादन विश्लेषण==
मैयर एट अल.<ref name="maier" />विभिन्न कंकररेंट हैश टेबल कार्यान्वयनों पर गहन विश्लेषण करें, जिससे वास्तविक उपयोग-मामलों में होने वाली विभिन्न स्थितियों में प्रत्येक की प्रभावशीलता के बारे में जानकारी मिल सके। सबसे महत्वपूर्ण निष्कर्षों को निम्नलिखित रूप में संक्षेपित किया जा सकता है:
मैयर एट अल.<ref name="maier" />विभिन्न कंकररेंट हैश टेबल कार्यान्वयनों पर गहन विश्लेषण करें, जिससे वास्तविक उपयोग-स्थितियों में होने वाली विभिन्न स्थितियों में प्रत्येक की प्रभावशीलता के बारे में जानकारी मिल सके। सबसे महत्वपूर्ण निष्कर्षों को निम्नलिखित रूप में संक्षेपित किया जा सकता है:


{| class="wikitable"
{| class="wikitable"
Line 46: Line 46:
| style="text-align:center;" | <code>find</code> || {{yes|}} || {{yes|}} || अद्वितीय खोजों की सफलता और खोज दोनों बहुत तेज़ स्पीडअप पर हो रही हैं, यहां तक कि बहुत अधिक विवाद के साथ भी
| style="text-align:center;" | <code>find</code> || {{yes|}} || {{yes|}} || अद्वितीय खोजों की सफलता और खोज दोनों बहुत तेज़ स्पीडअप पर हो रही हैं, यहां तक कि बहुत अधिक विवाद के साथ भी
|-
|-
| शैली= पाठ-संरेखण:केंद्र; | <code>insert</code> || {{yes|}} || {{CEmpty|}} || उच्च स्पीडअप तक पहुंच गया, उच्च विवाद तब समस्याग्रस्त हो जाता है जब कुंजियाँ एक से अधिक मान रख सकती हैं (अन्यथा यदि कुंजी पहले से मौजूद है तो आवेषण को आसानी से खारिज कर दिया जाता है)
| शैली= पाठ-संरेखण:केंद्र; | <code>insert</code> || {{yes|}} || {{CEmpty|}} || उच्च स्पीडअप तक पहुंच गया, उच्च विवाद तब समस्याग्रस्त हो जाता है जब कुंजियाँ एक से अधिक मान रख सकती हैं (अन्यथा यदि कुंजी पहले से उपस्थित है तो आवेषण को आसानी से खारिज कर दिया जाता है)
|-
|-
| शैली= पाठ-संरेखण:केंद्र; | <code>update</code> || {{yes|}} || {{no|}} || जब विवाद कम रखा जाता है तो ओवरराइट और मौजूदा मूल्यों के संशोधन दोनों उच्च गति तक पहुंच जाते हैं, अन्यथा अनुक्रमिक से भी बदतर प्रदर्शन होता है
| शैली= पाठ-संरेखण:केंद्र; | <code>update</code> || {{yes|}} || {{no|}} || जब विवाद कम रखा जाता है तो ओवरराइट और उपस्थिता मूल्यों के संशोधन दोनों उच्च गति तक पहुंच जाते हैं, अन्यथा अनुक्रमिक से भी बदतर प्रदर्शन होता है
|-
|-
| शैली= पाठ-संरेखण:केंद्र; | <code>delete</code> || {{yes|}} || {{no|}} || फेज कंकररेंट उच्चतम मापनीयता तक पहुँच गई; पूरी तरह से समवर्ती कार्यान्वयन जहां <code>delete</code> डमी-तत्वों के साथ <code>update</code>  का उपयोग करता है वह काफी पीछे था
| शैली= पाठ-संरेखण:केंद्र; | <code>delete</code> || {{yes|}} || {{no|}} || फेज कंकररेंट उच्चतम मापनीयता तक पहुँच गई; पूरी तरह से कंकररेंट कार्यान्वयन जहां <code>delete</code> डमी-तत्वों के साथ <code>update</code>  का उपयोग करता है वह काफी पीछे था
|}
|}


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


हालाँकि, समवर्ती हैश तालिकाओं के वास्तविक उपयोग के मामले अक्सर एक ही ऑपरेशन के अनुक्रम नहीं होते हैं, बल्कि कई प्रकारों का मिश्रण होते हैं। जैसे, जब <code>insert</code> और <code>find</code> ऑपरेशंस के मिश्रण का उपयोग किया जाता है तो समवर्ती हैश तालिकाओं की स्पीडअप और परिणामी उपयोगिता अधिक स्पष्ट हो जाती है, खासकर जब <code>find</code> भारी कार्यभार देखते हैं।
हालाँकि, कंकररेंट हैश टेबल्स के वास्तविक उपयोग के स्तिथि प्रायः एक ही ऑपरेशन के अनुक्रम नहीं होते हैं, बल्कि कई प्रकारों का मिश्रण होते हैं। जैसे, जब <code>insert</code> और <code>find</code> ऑपरेशंस के मिश्रण का उपयोग किया जाता है तो कंकररेंट हैश टेबल्स की स्पीडअप और परिणामी उपयोगिता अधिक स्पष्ट हो जाती है, खासकर जब <code>find</code> भारी कार्यभार देखते हैं।


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


==कार्यान्वयन==
==कार्यान्वयन==
* [[जावा (प्रोग्रामिंग भाषा)|जावा]] 1.5 के बाद से, समवर्ती हैश मैप समवर्ती मानचित्र इंटरफ़ेस के आधार पर प्रदान किए जाते हैं।<ref>[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html Java ConcurrentHashMap documentation]</ref>
* [[जावा (प्रोग्रामिंग भाषा)|जावा]] 1.5 के बाद से, कंकररेंट हैश मैप कंकररेंट मानचित्र इंटरफ़ेस के आधार पर प्रदान किए जाते हैं।<ref>[https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html Java ConcurrentHashMap documentation]</ref>
*लिबकुकू C/C++ के लिए समवर्ती हैश तालिकाएँ प्रदान करता है जो समवर्ती पढ़ने और लिखने की अनुमति देता है। लाइब्रेरी गिटहब पर उपलब्ध है।<ref>[https://github.com/efficient/libcuckoo GitHub repository for libcuckoo]</ref>  
*लिबकुकू C/C++ के लिए कंकररेंट हैश टेबल्स प्रदान करता है जो कंकररेंट पढ़ने और लिखने की अनुमति देता है। लाइब्रेरी गिटहब पर उपलब्ध है।<ref>[https://github.com/efficient/libcuckoo GitHub repository for libcuckoo]</ref>  
* [[थ्रेडिंग बिल्डिंग ब्लॉक्स]] C++ के लिए समवर्ती अव्यवस्थित मानचित्र प्रदान करते हैं जो समवर्ती प्रविष्टि और ट्रैवर्सल की अनुमति देते हैं और C++11 <code>std::unordered_map</code> इंटरफ़ेस के समान शैली में रखे जाते हैं। इसमें समवर्ती अव्यवस्थित मल्टीमैप्स शामिल हैं, जो समवर्ती अव्यवस्थित मानचित्र में एक ही कुंजी के लिए कई मानों को मौजूद रहने की अनुमति देते हैं।<ref>[https://software.intel.com/en-us/node/506171 Threading Building Blocks concurrent_unordered_map and concurrent_unordered_multimap documentation]</ref> इसके अतिरिक्त, समवर्ती हैश मानचित्र प्रदान किए जाते हैं जो समवर्ती अव्यवस्थित मानचित्र पर निर्मित होते हैं और आगे समवर्ती विलोपन की अनुमति देते हैं और इसमें अंतर्निहित लॉकिंग शामिल होती है।<ref>[https://software.intel.com/en-us/node/506191 Threading Building Blocks concurrent_hash_map documentation]</ref>
* [[थ्रेडिंग बिल्डिंग ब्लॉक्स]] C++ के लिए कंकररेंट अव्यवस्थित मानचित्र प्रदान करते हैं जो कंकररेंट प्रविष्टि और ट्रैवर्सल की अनुमति देते हैं और C++11 <code>std::unordered_map</code> इंटरफ़ेस के समान शैली में रखे जाते हैं। इसमें कंकररेंट अव्यवस्थित मल्टीमैप्स सम्मिलित हैं, जो कंकररेंट अव्यवस्थित मानचित्र में एक ही कुंजी के लिए कई मानों को उपस्थित रहने की अनुमति देते हैं।<ref>[https://software.intel.com/en-us/node/506171 Threading Building Blocks concurrent_unordered_map and concurrent_unordered_multimap documentation]</ref> इसके अतिरिक्त, कंकररेंट हैश मानचित्र प्रदान किए जाते हैं जो कंकररेंट अव्यवस्थित मानचित्र पर निर्मित होते हैं और आगे कंकररेंट विलोपन की अनुमति देते हैं और इसमें अंतर्निहित लॉकिंग सम्मिलित होती है।<ref>[https://software.intel.com/en-us/node/506191 Threading Building Blocks concurrent_hash_map documentation]</ref>
*विकास तथाकथित फोकलोर कार्यान्वयन के आधार पर C++ के लिए समवर्ती बढ़ती हैश तालिकाएँ प्रदान करता है। इस गैर-बढ़ते कार्यान्वयन के आधार पर, अलग-अलग बढ़ती हैश तालिकाएँ दी गई हैं। ये कार्यान्वयन समवर्ती पढ़ने, सम्मिलित करने, अपडेट करने (विशेष रूप से कुंजी पर वर्तमान मूल्य के आधार पर मान अपडेट करने) और निष्कासन (टॉम्बस्टोन का उपयोग करके अपडेट करने के आधार पर) की अनुमति देते हैं। इसके अलावा, इंटेल टीएसएक्स के आधार पर वेरिएंट उपलब्ध कराए गए हैं। यह लाइब्रेरी गिटहब पर उपलब्ध है।<ref name="maier" /><ref>[https://github.com/TooBiased/growt GitHub repository for growt]</ref>
*विकास तथाकथित फोकलोर कार्यान्वयन के आधार पर C++ के लिए कंकररेंट बढ़ती हैश टेबल्स प्रदान करता है। इस गैर-बढ़ते कार्यान्वयन के आधार पर, अलग-अलग बढ़ती हैश टेबल्स दी गई हैं। ये कार्यान्वयन कंकररेंट पढ़ने, सम्मिलित करने, अपडेट करने (विशेष रूप से कुंजी पर वर्तमान मूल्य के आधार पर मान अपडेट करने) और निष्कासन (टॉम्बस्टोन का उपयोग करके अपडेट करने के आधार पर) की अनुमति देते हैं। इसके अलावा, इंटेल टीएसएक्स के आधार पर वेरिएंट उपलब्ध कराए गए हैं। यह लाइब्रेरी गिटहब पर उपलब्ध है।<ref name="maier" /><ref>[https://github.com/TooBiased/growt GitHub repository for growt]</ref>
*फ़ॉली कंकररेंट हैश टेबल्स प्रदान करता है<ref>[https://github.com/facebook/folly/blob/master/folly/concurrency/ConcurrentHashMap.h GitHub page for implementation of concurrent hash maps in folly]</ref> [[C++14]] के लिए और बाद में प्रतीक्षा-मुक्त पाठकों और लॉक-आधारित, [[शार्ड (डेटाबेस आर्किटेक्चर)|शार्ड]] लेखकों को सुनिश्चित करना। जैसा कि इसके गिटहब पेज पर बताया गया है, यह लाइब्रेरी [[Facebook|फेसबुक]] के लिए उपयोगी कार्यक्षमता प्रदान करती है।<ref>[https://github.com/facebook/folly GitHub repository for folly]</ref>
*फ़ॉली कंकररेंट हैश टेबल्स प्रदान करता है<ref>[https://github.com/facebook/folly/blob/master/folly/concurrency/ConcurrentHashMap.h GitHub page for implementation of concurrent hash maps in folly]</ref> [[C++14]] के लिए और बाद में प्रतीक्षा-मुक्त पाठकों और लॉक-आधारित, [[शार्ड (डेटाबेस आर्किटेक्चर)|शार्ड]] लेखकों को सुनिश्चित करना। जैसा कि इसके गिटहब पेज पर बताया गया है, यह लाइब्रेरी [[Facebook|फेसबुक]] के लिए उपयोगी कार्यक्षमता प्रदान करती है।<ref>[https://github.com/facebook/folly GitHub repository for folly]</ref>
* जंक्शन टेबल के किसी भी सदस्य फ़ंक्शन के लिए थ्रेड-सुरक्षा सुनिश्चित करने के लिए परमाणु संचालन के आधार पर C++ के लिए कंकररेंट हैश तालिकाओं के कई कार्यान्वयन प्रदान करता है। लाइब्रेरी गिटहब  पर उपलब्ध है।<ref>[https://github.com/preshing/junction GitHub repository for Junction]</ref>
* जंक्शन टेबल के किसी भी सदस्य फ़ंक्शन के लिए थ्रेड-सुरक्षा सुनिश्चित करने के लिए परमाणु संचालन के आधार पर C++ के लिए कंकररेंट हैश टेबल्स के कई कार्यान्वयन प्रदान करता है। लाइब्रेरी गिटहब  पर उपलब्ध है।<ref>[https://github.com/preshing/junction GitHub repository for Junction]</ref>
==यह भी देखें==
==यह भी देखें==


Revision as of 17:05, 19 July 2023

समान हैश टेबल तक कंकररेंट एक्सेस।

कंकररेंट (कंकररेंट) हैश टेबल या कंकररेंट हैश मैप हैश टेबल्स का कार्यान्वयन है जो हैश फंकशन का उपयोग करके एकाधिक थ्रेड्स द्वारा कंकररेंट एक्सेस की अनुमति देता है।[1][2]

कंकररेंट हैश टेबल्स कंकररेंट कंप्यूटिंग में उपयोग के लिए एक प्रमुख कंकररेंट डेटा संरचना का प्रतिनिधित्व करती हैं जो साझा डेटा के बीच गणना के लिए कई थ्रेड्स को अधिक कुशलता से सहयोग करने की अनुमति देती हैं।[1]

कंकररेंट एक्सेस से जुड़ी प्राकृतिक समस्याओं के कारण - अर्थात् विवाद - जिस तरीके और दायरे से टेबल को कंकररेंट रूप से एक्सेस किया जा सकता है, वह कार्यान्वयन के आधार पर भिन्न होता है। इसके अलावा, परिणामस्वरूप होने वाली गति विवाद को हल करने के लिए उपयोग किए जाने वाले थ्रेड्स की मात्रा के साथ रैखिक नहीं हो सकती है, जिससे प्रोसेसिंग ओवरहेड का उत्पादन होता है।[1] विवाद के प्रभावों को कम करने के लिए कई समाधान उपस्थित हैं, जिनमें से प्रत्येक टेबल पर संचालन की शुद्धता को बनाए रखता है।[1][2][3][4]

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

कंकररेंट हैशिंग

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

जब हैश टेबल्स आकार में बंधी नहीं होती हैं और इस प्रकार आवश्यकता पड़ने पर उन्हें बढ़ने/घटने की अनुमति दी जाती है, तो इस ऑपरेशन को अनुमति देने के लिए हैशिंग एल्गोरिदम को अनुकूलित करने की आवश्यकता होती है। इसमें परिवर्तित टेबल के नए कुंजी स्थान को प्रतिबिंबित करने के लिए प्रयुक्त हैश फ़ंक्शन को संशोधित करना सम्मिलित है। एक कंकररेंट बढ़ते एल्गोरिथ्म का वर्णन मैयर एट अल द्वारा किया गया है।[1]

मेगा-केवी [7] एक उच्च-प्रदर्शन कुंजी-मूल्य स्टोर सिस्टम है, जहां कुक्कू हैशिंग का उपयोग किया जाता है और केवी इंडेक्सिंग को जीपीयू द्वारा बैच मोड में बड़े पैमाने पर समानांतर किया जाता है। एनवीआईडीआईए और ओक रिज नेशनल लैब द्वारा जीपीयू त्वरण के और अनुकूलन के साथ, मेगा-केवी को 2018 में थ्रूपुट के एक और उच्च रिकॉर्ड (प्रति सेकंड 888 मिलियन कुंजी-मूल्य संचालन तक) तक पहुंचा दिया गया था।[8]

कंटेन्शन हैंडलिंग

कंकररेंट एक्सेस विवाद का कारण बन रही है (लाल रंग में चिह्नित)।

किसी भी कंकररेंट डेटा संरचना की तरह, कंकररेंट हैश टेबल्स विवाद के परिणामस्वरूप कंकररेंट कंप्यूटिंग के क्षेत्र में ज्ञात विभिन्न समस्याओं से ग्रस्त हैं।[3] एबीए समस्या, रेस कंडीशन और गतिरोध इसके उदाहरण हैं। ये समस्याएँ किस हद तक प्रकट होती हैं या होती भी हैं, यह कंकररेंट हैश टेबल के कार्यान्वयन पर निर्भर करता है; विशेष रूप से टेबल किस संचालन को एक साथ चलाने की अनुमति देती है, साथ ही विवाद से जुड़ी समस्याओं को कम करने के लिए इसकी रणनीतियाँ भी। विवाद को संभालते समय, मुख्य लक्ष्य किसी अन्य कंकररेंट डेटा संरचना के समान ही होता है, अर्थात् टेबल पर प्रत्येक ऑपरेशन के लिए शुद्धता सुनिश्चित करना। साथ ही, इसे स्वाभाविक रूप से इस तरह से किया जाना चाहिए कि कंकररेंट रूप से उपयोग किए जाने पर यह अनुक्रमिक समाधान से अधिक कुशल हो। इसे संगामिति नियंत्रण के रूप में भी जाना जाता है।

परमाणु निर्देश

तुलना-और-स्वैप या फ़ेच-एंड-ऐड जैसे परमाणु निर्देशों का उपयोग करके, यह सुनिश्चित करके विवाद के कारण होने वाली समस्याओं को कम किया जा सकता है कि किसी अन्य एक्सेस को हस्तक्षेप करने का मौका मिलने से पहले एक्सेस पूरा हो जाए। तुलना-और-स्वैप जैसे संचालन प्रायः सीमाएं पेश करते हैं कि वे किस आकार के डेटा को संभाल सकते हैं, जिसका अर्थ है कि टेबल के कुंजियों और मूल्यों के प्रकार को तदनुसार चुना या परिवर्तित किया जाना चाहिए।[1]

तथाकथित हार्डवेयर ट्रांजेक्शनल मेमोरी (एचटीएम) का उपयोग करते हुए, टेबल संचालन को डेटाबेस विनिमय की तरह सोचा जा सकता है, [3] परमाणुता सुनिश्चित करना। व्यवहार में एचटीएम का एक उदाहरण ट्रांजेक्शनल सिंक्रोनाइजेशन एक्सटेंशन है।

लॉकिंग

लॉक्स की मदद से, टेबल या उसके भीतर के मूल्यों तक एक साथ पहुंचने की कोशिश करने वाले संचालन को इस तरह से नियंत्रित किया जा सकता है जो सही व्यवहार सुनिश्चित करता है। हालाँकि, इससे प्रदर्शन पर नकारात्मक प्रभाव पड़ सकता है,[1][6] विशेष रूप से जब उपयोग किए गए ताले बहुत अधिक प्रतिबंधात्मक होते हैं, इस प्रकार उन पहुंचों को अवरुद्ध कर देते हैं जो अन्यथा प्रतिस्पर्धा नहीं कर सकते थे और बिना किसी समस्या के निष्पादित हो सकते थे। और भी गंभीर समस्याओं से बचने के लिए आगे विचार करना होगा जो शुद्धता को खतरे में डालती हैं, जैसे कि लाइवलॉक, गतिरोध या अप्राप्ति।[3]

फेज कंकर्रेंसी

कंकररेंट एक्सेस को अलग-अलग चरणों में समूहीकृत किया गया।

फेज कंकररेंट हैश टेबल समूह फेज बनाकर पहुँचता है जिसमें केवल एक प्रकार के ऑपरेशन की अनुमति होती है (यानी एक शुद्ध लेखन-फेज), इसके बाद सभी थ्रेड्स में टेबल स्थिति का सिंक्रनाइज़ेशन (कंप्यूटर विज्ञान) होता है। इसके लिए एक औपचारिक रूप से सिद्ध एल्गोरिदम शुन और ब्लेलोच द्वारा दिया गया है।[2]

रीड-कॉपी-अपडेट

लिनक्स कर्नेल के भीतर व्यापक रूप से उपयोग किया जाता है, [3] रीड-कॉपी-अपडेट (आरसीयू) उन स्थितियों में विशेष रूप से उपयोगी होता है जहां रीड की संख्या लिखने की संख्या से कहीं अधिक होती है।[4]

अनुप्रयोग

स्वाभाविक रूप से, जहां भी अनुक्रमिक हैश टेबल उपयोगी होते हैं, वहां कंकररेंट हैश टेबल का अनुप्रयोग होता है। समवर्तीता से जो लाभ मिलता है, वह इन उपयोग-स्थितियों की संभावित गति के साथ-साथ बढ़ी हुई स्केलेबिलिटी के भीतर निहित है।[1] मल्टी-कोर प्रोसेसर जैसे हार्डवेयर को ध्यान में रखते हुए, जो कंकररेंट गणना के लिए तेजी से अधिक सक्षम हो जाते हैं, इन अनुप्रयोगों के भीतर कंकररेंट डेटा संरचनाओं का महत्व लगातार बढ़ता है।[3]

निष्पादन विश्लेषण

मैयर एट अल.[1]विभिन्न कंकररेंट हैश टेबल कार्यान्वयनों पर गहन विश्लेषण करें, जिससे वास्तविक उपयोग-स्थितियों में होने वाली विभिन्न स्थितियों में प्रत्येक की प्रभावशीलता के बारे में जानकारी मिल सके। सबसे महत्वपूर्ण निष्कर्षों को निम्नलिखित रूप में संक्षेपित किया जा सकता है:

Operation Contention Notes
Low High
find अद्वितीय खोजों की सफलता और खोज दोनों बहुत तेज़ स्पीडअप पर हो रही हैं, यहां तक कि बहुत अधिक विवाद के साथ भी
insert उच्च स्पीडअप तक पहुंच गया, उच्च विवाद तब समस्याग्रस्त हो जाता है जब कुंजियाँ एक से अधिक मान रख सकती हैं (अन्यथा यदि कुंजी पहले से उपस्थित है तो आवेषण को आसानी से खारिज कर दिया जाता है)
update जब विवाद कम रखा जाता है तो ओवरराइट और उपस्थिता मूल्यों के संशोधन दोनों उच्च गति तक पहुंच जाते हैं, अन्यथा अनुक्रमिक से भी बदतर प्रदर्शन होता है
delete फेज कंकररेंट उच्चतम मापनीयता तक पहुँच गई; पूरी तरह से कंकररेंट कार्यान्वयन जहां delete डमी-तत्वों के साथ update का उपयोग करता है वह काफी पीछे था

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

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

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

कार्यान्वयन

  • जावा 1.5 के बाद से, कंकररेंट हैश मैप कंकररेंट मानचित्र इंटरफ़ेस के आधार पर प्रदान किए जाते हैं।[9]
  • लिबकुकू C/C++ के लिए कंकररेंट हैश टेबल्स प्रदान करता है जो कंकररेंट पढ़ने और लिखने की अनुमति देता है। लाइब्रेरी गिटहब पर उपलब्ध है।[10]
  • थ्रेडिंग बिल्डिंग ब्लॉक्स C++ के लिए कंकररेंट अव्यवस्थित मानचित्र प्रदान करते हैं जो कंकररेंट प्रविष्टि और ट्रैवर्सल की अनुमति देते हैं और C++11 std::unordered_map इंटरफ़ेस के समान शैली में रखे जाते हैं। इसमें कंकररेंट अव्यवस्थित मल्टीमैप्स सम्मिलित हैं, जो कंकररेंट अव्यवस्थित मानचित्र में एक ही कुंजी के लिए कई मानों को उपस्थित रहने की अनुमति देते हैं।[11] इसके अतिरिक्त, कंकररेंट हैश मानचित्र प्रदान किए जाते हैं जो कंकररेंट अव्यवस्थित मानचित्र पर निर्मित होते हैं और आगे कंकररेंट विलोपन की अनुमति देते हैं और इसमें अंतर्निहित लॉकिंग सम्मिलित होती है।[12]
  • विकास तथाकथित फोकलोर कार्यान्वयन के आधार पर C++ के लिए कंकररेंट बढ़ती हैश टेबल्स प्रदान करता है। इस गैर-बढ़ते कार्यान्वयन के आधार पर, अलग-अलग बढ़ती हैश टेबल्स दी गई हैं। ये कार्यान्वयन कंकररेंट पढ़ने, सम्मिलित करने, अपडेट करने (विशेष रूप से कुंजी पर वर्तमान मूल्य के आधार पर मान अपडेट करने) और निष्कासन (टॉम्बस्टोन का उपयोग करके अपडेट करने के आधार पर) की अनुमति देते हैं। इसके अलावा, इंटेल टीएसएक्स के आधार पर वेरिएंट उपलब्ध कराए गए हैं। यह लाइब्रेरी गिटहब पर उपलब्ध है।[1][13]
  • फ़ॉली कंकररेंट हैश टेबल्स प्रदान करता है[14] C++14 के लिए और बाद में प्रतीक्षा-मुक्त पाठकों और लॉक-आधारित, शार्ड लेखकों को सुनिश्चित करना। जैसा कि इसके गिटहब पेज पर बताया गया है, यह लाइब्रेरी फेसबुक के लिए उपयोगी कार्यक्षमता प्रदान करती है।[15]
  • जंक्शन टेबल के किसी भी सदस्य फ़ंक्शन के लिए थ्रेड-सुरक्षा सुनिश्चित करने के लिए परमाणु संचालन के आधार पर C++ के लिए कंकररेंट हैश टेबल्स के कई कार्यान्वयन प्रदान करता है। लाइब्रेरी गिटहब पर उपलब्ध है।[16]

यह भी देखें

  • पैरेलल कंप्यूटिंग
  • लाइवनेस
  • सीट्री

संदर्भ

  1. ↑ 1.00 1.01 1.02 1.03 1.04 1.05 1.06 1.07 1.08 1.09 1.10 Maier, Tobias; Sanders, Peter; Dementiev, Roman (March 2019). "Concurrent Hash Tables: Fast and General(?)!". ACM Transactions on Parallel Computing. New York, NY, USA: ACM. 5 (4). Article 16. doi:10.1145/3309206. ISSN 2329-4949. S2CID 67870641.
  2. ↑ 2.0 2.1 2.2 Shun, Julian; Blelloch, Guy E. (2014). "नियतत्ववाद के लिए चरण-समवर्ती हैश तालिकाएँ". SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures. New York: ACM. pp. 96–107. doi:10.1145/2612669.2612687. ISBN 978-1-4503-2821-0.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 Li, Xiaozhou; Andersen, David G.; Kaminsky, Michael; Freedman, Michael J. (2014). "Algorithmic Improvements for Fast Concurrent Cuckoo Hashing". Proceedings of the Ninth European Conference on Computer Systems. EuroSys '14. New York: ACM. Article No. 27. doi:10.1145/2592798.2592820. ISBN 978-1-4503-2704-6.
  4. ↑ 4.0 4.1 Triplett, Josh; McKenney, Paul E.; Walpole, Jonathan (2011). "Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming". USENIXATC'11: Proceedings of the 2011 USENIX conference on USENIX annual technical conference. Berkeley, CA: USENIX Association. p. 11.
  5. ↑ Herlihy, Maurice; Shavit, Nir (2008). "Chapter 13: Concurrent Hashing and Natural Parallelism". मल्टीप्रोसेसर प्रोग्रामिंग की कला. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. pp. 316–325. ISBN 978-0-12-370591-4.
  6. ↑ 6.0 6.1 Fan, Bin; Andersen, David G.; Kaminsky, Michael (2013). "MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing". nsdi'13: Proceedings of the 10th USENIX conference on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association. pp. 371–384.
  7. ↑ Zhang, Kai; Wang, Kaibo; Yuan, Yuan; Guo, Lei; Lee, Rubao; and Zhang, Xiaodong (2015). "Mega-KV: a case for GPUs to maximize the throughput of in-memory key-value stores". Proceedings of the VLDB Endowment, Vol. 8, No. 11, 2015.
  8. ↑ Chu, Ching-Hsing; Potluri, Sreeram; Goswami, Anshuman; Venkata, Manjunath Gorentla; Imam, Neenaand; and Newburn, Chris J. (2018) "Designing High-performance in-memory key-value operations with persistent GPU kernels and OPENSHMEM"..
  9. ↑ Java ConcurrentHashMap documentation
  10. ↑ GitHub repository for libcuckoo
  11. ↑ Threading Building Blocks concurrent_unordered_map and concurrent_unordered_multimap documentation
  12. ↑ Threading Building Blocks concurrent_hash_map documentation
  13. ↑ GitHub repository for growt
  14. ↑ GitHub page for implementation of concurrent hash maps in folly
  15. ↑ GitHub repository for folly
  16. ↑ GitHub repository for Junction


अग्रिम पठन

  • Herlihy, Maurice; Shavit, Nir (2008). "Chapter 13: Concurrent Hashing and Natural Parallelism". The Art of Multiprocessor Programming. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. pp. 299–328. ISBN 978-0-12-370591-4.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=कॉन्करेन्ट_हैश_टेबल&oldid=229571’