कॉन्करेन्ट हैश टेबल
एक कॉनकरेंसी (कंप्यूटर विज्ञान) हैश टेबल या समवर्ती हैश मैप हैश तालिकाओं का एक कार्यान्वयन है जो हैश फंकशन का उपयोग करके एकाधिक थ्रेड (कंप्यूटिंग) द्वारा कॉनकरेंसी (कंप्यूटर विज्ञान) की अनुमति देता है।[1][2]
समवर्ती हैश तालिकाएँ समवर्ती कंप्यूटिंग में उपयोग के लिए एक प्रमुख समवर्ती डेटा संरचना का प्रतिनिधित्व करती हैं जो कई थ्रेड्स को साझा डेटा के बीच गणना के लिए अधिक कुशलता से सहयोग करने की अनुमति देती हैं।[1]
समवर्ती पहुंच से जुड़ी प्राकृतिक समस्याओं के कारण - अर्थात् संसाधन विवाद - तालिका को समवर्ती रूप से एक्सेस करने का तरीका और दायरा कार्यान्वयन के आधार पर भिन्न होता है। इसके अलावा, परिणामी गति उपयोग किए गए थ्रेड्स की मात्रा के साथ रैखिक नहीं हो सकती है क्योंकि विवाद को हल करने की आवश्यकता है, जिससे प्रोसेसिंग ओवरहेड (कंप्यूटिंग) उत्पन्न होती है।[1]विवाद के प्रभावों को कम करने के लिए कई समाधान मौजूद हैं, जिनमें से प्रत्येक मेज पर संचालन की शुद्धता (कंप्यूटर विज्ञान) को संरक्षित करता है।[1][2][3][4] उनके अनुक्रमिक समकक्ष के साथ, समवर्ती हैश तालिकाओं को व्यापक अनुप्रयोगों में फिट करने के लिए सामान्यीकृत और विस्तारित किया जा सकता है, जैसे कि कुंजी और मूल्यों के लिए अधिक जटिल डेटा प्रकारों का उपयोग करने की अनुमति देना। हालाँकि, ये सामान्यीकरण प्रदर्शन पर नकारात्मक प्रभाव डाल सकते हैं और इसलिए इन्हें एप्लिकेशन की आवश्यकताओं के अनुसार चुना जाना चाहिए।[1]
समवर्ती हैशिंग
समवर्ती हैश तालिकाएँ बनाते समय, चुने हुए हैशिंग एल्गोरिदम के साथ तालिका तक पहुँचने वाले कार्यों को एक संघर्ष समाधान रणनीति जोड़कर समवर्ती के लिए अनुकूलित करने की आवश्यकता होती है। इस तरह की रणनीति के लिए एक्सेस को इस तरह से प्रबंधित करने की आवश्यकता होती है कि उनके कारण होने वाले टकराव के परिणामस्वरूप भ्रष्ट डेटा न हो, जबकि समानांतर में उपयोग किए जाने पर आदर्श रूप से उनकी दक्षता बढ़ जाती है। हेर्लिही और शेविट[5] वर्णन करें कि इस तरह की रणनीति के बिना हैश तालिका तक पहुंच को कैसे - कोयल हैशिंग एल्गोरिदम के बुनियादी कार्यान्वयन के आधार पर इसके उदाहरण में - समवर्ती उपयोग के लिए अनुकूलित किया जा सकता है। फैन एट अल.[6] आगे कुक्कू हैशिंग पर आधारित एक टेबल एक्सेस योजना का वर्णन करें जो न केवल समवर्ती है, बल्कि कैश लोकैलिटी के साथ-साथ सम्मिलन के थ्रूपुट में सुधार करते हुए इसके हैशिंग फ़ंक्शन की स्पेस दक्षता को भी बनाए रखती है।
जब हैश टेबल आकार में बंधे नहीं होते हैं और इस प्रकार आवश्यकता पड़ने पर उन्हें बढ़ने/घटने की अनुमति दी जाती है, तो इस ऑपरेशन को अनुमति देने के लिए हैशिंग एल्गोरिदम को अनुकूलित करने की आवश्यकता होती है। इसमें संशोधित तालिका के नए कुंजी-स्थान को प्रतिबिंबित करने के लिए उपयोग किए गए हैश फ़ंक्शन को संशोधित करना शामिल है। मैयर एट अल द्वारा एक समवर्ती बढ़ते एल्गोरिदम का वर्णन किया गया है।[1]
मेगा के.वी[7] एक उच्च प्रदर्शन कुंजी-मूल्य स्टोर सिस्टम है, जहां कुक्कू हैशिंग का उपयोग किया जाता है और केवी इंडेक्सिंग को जीपीयू द्वारा बैच मोड में बड़े पैमाने पर समानांतर किया जाता है। एनवीआईडीआईए और ओक रिज नेशनल लैब द्वारा जीपीयू त्वरण के और अनुकूलन के साथ, मेगा-केवी को 2018 में थ्रूपुट के एक और उच्च रिकॉर्ड (प्रति सेकंड 888 मिलियन कुंजी-मूल्य संचालन तक) तक पहुंचा दिया गया था।[8]
विवाद प्रबंधन
किसी भी समवर्ती डेटा संरचना की तरह, समवर्ती हैश तालिकाएँ विवाद के परिणामस्वरूप समवर्ती कंप्यूटिंग के क्षेत्र में ज्ञात विभिन्न समस्याओं से ग्रस्त हैं।[3]इसके उदाहरण एबीए समस्या, दौड़ की स्थिति और गतिरोध हैं।
ये समस्याएँ किस हद तक प्रकट होती हैं या होती भी हैं, यह समवर्ती हैश तालिका के कार्यान्वयन पर निर्भर करता है; विशेष रूप से तालिका किस संचालन को समवर्ती रूप से चलाने की अनुमति देती है, साथ ही विवाद से जुड़ी समस्याओं को कम करने के लिए इसकी रणनीतियाँ भी। विवाद को संभालते समय, मुख्य लक्ष्य किसी भी अन्य समवर्ती डेटा संरचना के समान होता है, अर्थात् तालिका पर प्रत्येक ऑपरेशन के लिए शुद्धता सुनिश्चित करना। साथ ही, इसे स्वाभाविक रूप से इस तरह से किया जाना चाहिए कि समवर्ती रूप से उपयोग किए जाने पर अनुक्रमिक समाधान की तुलना में यह अधिक कुशल हो। इसे समवर्ती नियंत्रण के रूप में भी जाना जाता है।
परमाणु निर्देश
तुलना-और-स्वैप या लाएँ-और-जोड़ें जैसे परमाणु (कंप्यूटर विज्ञान) निर्देश (कंप्यूटर विज्ञान) का उपयोग करके, विवाद के कारण होने वाली समस्याओं को यह सुनिश्चित करके कम किया जा सकता है कि किसी अन्य एक्सेस को हस्तक्षेप करने का मौका मिलने से पहले एक एक्सेस पूरा हो जाता है। तुलना-और-स्वैप जैसे ऑपरेशन अक्सर सीमाएं पेश करते हैं कि वे किस आकार के डेटा को संभाल सकते हैं, जिसका अर्थ है कि तालिका के कुंजियों और मूल्यों के प्रकार को तदनुसार चुना या परिवर्तित किया जाना चाहिए।[1]
तथाकथित हार्डवेयर लेन-देन संबंधी स्मृति (एचटीएम) का उपयोग करके, टेबल संचालन को काफी हद तक डेटाबेस लेनदेन की तरह सोचा जा सकता है,[3]परमाणुता सुनिश्चित करना। व्यवहार में HTM का एक उदाहरण लेन-देन तुल्यकालन एक्सटेंशन हैं।
लॉकिंग
लॉक (कंप्यूटर विज्ञान) की मदद से, तालिका या उसके भीतर मूल्यों तक एक साथ पहुंचने की कोशिश करने वाले संचालन को इस तरह से नियंत्रित किया जा सकता है जो सही व्यवहार सुनिश्चित करता है। हालाँकि इससे प्रदर्शन पर नकारात्मक प्रभाव पड़ सकता है,[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]
- libcuckoo C (प्रोग्रामिंग भाषा)/C++ के लिए समवर्ती हैश टेबल प्रदान करता है जो समवर्ती पढ़ने और लिखने की अनुमति देता है। लाइब्रेरी GitHub पर उपलब्ध है।[10]
- थ्रेडिंग बिल्डिंग ब्लॉक्स C++ के लिए समवर्ती अव्यवस्थित मानचित्र प्रदान करते हैं जो समवर्ती प्रविष्टि और ट्रैवर्सल की अनुमति देते हैं और C++11 के समान शैली में रखे जाते हैं।
std::unordered_mapइंटरफेस। इसमें समवर्ती अव्यवस्थित मल्टीमैप्स शामिल हैं, जो समवर्ती अव्यवस्थित मानचित्र में एक ही कुंजी के लिए कई मानों को मौजूद रहने की अनुमति देते हैं।[11] इसके अतिरिक्त, समवर्ती हैश मानचित्र प्रदान किए जाते हैं जो समवर्ती अव्यवस्थित मानचित्र पर निर्मित होते हैं और समवर्ती विलोपन की अनुमति देते हैं और इसमें अंतर्निहित लॉकिंग होती है।[12] - ग्रोथ तथाकथित लोकगीत कार्यान्वयन के आधार पर C++ के लिए समवर्ती बढ़ती हैश तालिकाएँ प्रदान करता है। इस गैर-बढ़ते कार्यान्वयन के आधार पर, विभिन्न प्रकार की बढ़ती हैश तालिकाएँ दी गई हैं। ये कार्यान्वयन समवर्ती रीड, इंसर्ट, अपडेट (विशेष रूप से कुंजी पर वर्तमान मान के आधार पर मान अपडेट करना) और निष्कासन (टॉम्बस्टोन (प्रोग्रामिंग) का उपयोग करके अपडेट करने के आधार पर) की अनुमति देते हैं। इसके अलावा, Intel TSX पर आधारित वेरिएंट उपलब्ध कराए गए हैं। लाइब्रेरी GitHub पर उपलब्ध है।[1][13]
- फ़ॉली समवर्ती हैश तालिकाएँ प्रदान करता है[14] C++14 के लिए और बाद में प्रतीक्षा-मुक्त पाठकों और लॉक-आधारित, शार्ड (डेटाबेस आर्किटेक्चर) लेखकों को सुनिश्चित करना। जैसा कि इसके GitHub पेज पर बताया गया है, यह लाइब्रेरी Facebook के लिए उपयोगी कार्यक्षमता प्रदान करती है।[15]
- जंक्शन तालिका के किसी भी सदस्य फ़ंक्शन के लिए थ्रेड-सुरक्षा सुनिश्चित करने के लिए परमाणु संचालन के आधार पर C++ के लिए समवर्ती हैश तालिकाओं के कई कार्यान्वयन प्रदान करता है। लाइब्रेरी GitHub पर उपलब्ध है।[16]
यह भी देखें
- समानांतर कंप्यूटिंग
- सजीवता
- सीट्री
संदर्भ
- ↑ 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.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.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.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.
- ↑ 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.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.
- ↑ 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.
- ↑ 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"..
- ↑ Java ConcurrentHashMap documentation
- ↑ GitHub repository for libcuckoo
- ↑ Threading Building Blocks concurrent_unordered_map and concurrent_unordered_multimap documentation
- ↑ Threading Building Blocks concurrent_hash_map documentation
- ↑ GitHub repository for growt
- ↑ GitHub page for implementation of concurrent hash maps in folly
- ↑ GitHub repository for folly
- ↑ 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.
