कॉन्करेन्ट हैश टेबल
कंकररेंट (कंकररेंट) हैश टेबल या कंकररेंट हैश मैप हैश टेबल्स का कार्यान्वयन है जो हैश फंकशन का उपयोग करके एकाधिक थ्रेड्स द्वारा कंकररेंट एक्सेस की अनुमति देता है।[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]
- 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.
