समवर्ती डेटा संरचना डिजाइन

Question

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

आवश्यकताएं हैं कि यह कुशल डालने, आदर्श ओ (1), मामूली कुशल हटाने और कुशल ट्रैवर्सल का समर्थन कर सकती है। इसे एक खोज ऑपरेशन का समर्थन करने की आवश्यकता नहीं है (हटाने के लिए आवश्यक हो सकता है)।

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

यह पढ़ने/लिखने के लॉक का उपयोग करने के लिए स्वीकार्य नहीं है और सभी पाठकों को समाप्त होने तक लिखने के संचालन को स्थगित कर देता है, क्योंकि पढ़ने के संचालन लंबे समय तक जीवित रह सकते हैं। इससे कोई फर्क नहीं पड़ता कि पाठक होने पर आवेषण उस पाठक के लिए दृश्यमान होते हैं या नहीं।

मेमोरी पदचिह्न भी बहुत महत्वपूर्ण है, और छोटा स्पष्ट रूप से बेहतर है!

क्या सुझाव हैं?

टिप्पणी करने के लिए उत्तर:

जवाब के लिए धन्यवाद।

नहीं, आवेषण मौजूदा इटरेटर्स को अमान्य नहीं कर सकता है। इटरेटर नए सम्मिलन को देख सकते हैं या नहीं देख सकते हैं, लेकिन अगर वे सम्मिलित नहीं हुए थे तो उन्हें सब कुछ देखना होगा।

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

एक कर्सर के लिए प्रति नोड लॉकिंग प्रदर्शन पर बहुत अधिक प्रभाव डालेगा। एक बार में कई धागे पढ़ रहे हैं, और किसी भी प्रकार की मेमोरी हॉट स्पॉट जो लॉक में कई थ्रेड का उपयोग कर रही है, मेमोरी बैंडविड्थ को मारता है (जैसा कि हमने कड़ी मेहनत की खोज की है!)। InterlockedIncrement को कॉल करने वाले एकाधिक थ्रेड वाले पाठकों की एक साधारण गणना भी स्केल करने में विफल रहता है।

मैं सहमत हूं कि एक लिंक्ड सूची शायद सबसे अच्छा तरीका है। Deletes दुर्लभ हैं, तो ओ (1) हटाने का समर्थन करने के लिए बैक पॉइंटर्स के लिए मेमोरी जुर्माना का भुगतान महंगा है और हम मांग पर अलग से गणना कर सकते हैं और चूंकि हटाए गए बैच ऑपरेशंस होते हैं।

सौभाग्य से एक लिंक्ड सूची में सम्मिलन को पाठकों के लिए किसी भी लॉकिंग की आवश्यकता नहीं होती है, जब तक कि पॉइंटर को पॉइंटर बदलने से पहले डाले गए नोड में अपडेट किया जाता है।

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

Answer 1

व्यक्तिगत रूप से, मैं अत्यधिक समवर्ती परिस्थितियों में निरंतर अपरिवर्तनीय डेटा संरचनाओं का बहुत शौकिया हूं। मुझे किसी विशेष रूप से सी ++ के बारे में पता नहीं है, लेकिन रिच हिकी ने Clojure के लिए जावा में कुछ उत्कृष्ट (और ब्लिस्टरिंग फास्ट) अपरिवर्तनीय डेटा संरचनाएं बनाई हैं। विशेष रूप से: वेक्टर, एच एशटेबल और हैशसेट। वे बंदरगाह के लिए बहुत मुश्किल नहीं हैं, इसलिए आप उनमें से एक पर विचार करना चाह सकते हैं।

थोड़ा और विस्तार करने के लिए, निरंतर अपरिवर्तनीय डेटा संरचनाएं वास्तव में समरूपता से जुड़ी कई समस्याओं को हल करती हैं। चूंकि डेटा संरचना स्वयं अपरिवर्तनीय है, इसलिए कई धागे पढ़ने/पुनरावृत्त करने के साथ एक समस्या नहीं है (जब तक यह एक कॉन्स इटरेटर है)। "लेखन" असीमित भी हो सकता है क्योंकि यह वास्तव में मौजूदा संरचना को नहीं लिख रहा है बल्कि उस संरचना का एक नया संस्करण बना रहा है जिसमें नया तत्व शामिल है। यह ऑपरेशन कुशलता से बनाया गया है (ओ (1) सभी हिकी के ढांचे में) इस तथ्य से कि आप वास्तव में सबकुछ कॉपी नहीं कर रहे हैं। प्रत्येक नया संस्करण पुराने संस्करण के साथ अपनी अधिकांश संरचनाओं को साझा करता है।यह चीजों को अधिक स्मृति कुशल बनाता है, साथ ही सरल कॉपी-ऑन-राइट तकनीक पर नाटकीय रूप से प्रदर्शन में सुधार करता है।

अपरिवर्तनीय डेटा संरचनाओं के साथ, एकमात्र समय जहां आपको वास्तव में सिंक्रनाइज़ करने की आवश्यकता होती है वास्तव में एक संदर्भ कक्ष में लिखना है। चूंकि स्मृति पहुंच परमाणु है, यहां तक ​​कि यह आमतौर पर लॉक-फ्री भी हो सकता है। यहां केवल एक चेतावनी है कि आप धागे (दौड़ की स्थिति) के बीच डेटा खो सकते हैं। समेकन के कारण डेटा संरचना कभी भी दूषित नहीं होगी, लेकिन इसका मतलब यह नहीं है कि परिस्थितियों में असंगत परिणाम असंभव हैं जहां दो धागे एक पुराने के आधार पर संरचना का एक नया संस्करण बनाते हैं और उनके परिणाम लिखने का प्रयास करते हैं (उनमें से एक "जीत" और दूसरे के परिवर्तन खो जाएंगे)। इस समस्या को हल करने के लिए, आपको या तो "लेखन कार्य" के लिए लॉक होना चाहिए, या STM के किसी प्रकार का उपयोग करना होगा। मुझे कम-टक्कर प्रणाली में आसानी से उपयोग और थ्रूपुट के लिए दूसरा दृष्टिकोण पसंद है (लिखने आदर्श रूप से गैर-अवरुद्ध होते हैं और कभी ब्लॉक नहीं पढ़ते हैं), लेकिन कोई भी काम करेगा।

आपने एक कठिन सवाल पूछा है, जिसके लिए वास्तव में कोई अच्छा जवाब नहीं है। Concurrency- सुरक्षित डेटा संरचनाओं को लिखना मुश्किल है, खासकर जब उन्हें उत्परिवर्तनीय होने की आवश्यकता होती है। साझा राज्य की उपस्थिति में पूरी तरह से लॉक-फ्री आर्किटेक्चर असंभव रूप से असंभव हैं, इसलिए आप उस आवश्यकता को छोड़ना चाहेंगे। सबसे अच्छा आप कर सकते हैं लॉकिंग आवश्यक है, इसलिए अपरिवर्तनीय डेटा संरचनाओं। डबल-जवाब के लिए

Answer 2

मुझे लगता है कि लिंक्ड सूची को आपकी आवश्यकताओं का उत्तर देना चाहिए। ध्यान दें कि आप केवल उन नोड्स को लॉक कर सकते हैं जिन्हें बदला जा रहा है (यानी हटाया गया/संलग्न) ताकि पाठक अधिकांश समय लेखकों के साथ पूर्ण समांतरता में काम करने में सक्षम होंगे। इस दृष्टिकोण के लिए एक लिंक प्रति लिंक सूची नोड की आवश्यकता है, हालांकि यह जरूरी नहीं है।आपके पास सीमित ताले की मात्रा हो सकती है और फिर कई नोड्स को उसी लॉक में मैप किया जाएगा। यानी, एन ताले और नोड्स की संख्या 0 0 मिली है। आप इस नोड को लॉक करने के लिए लॉक (नोडआईडी% एन) का उपयोग कर सकते हैं। वे रीड-राइट लॉक हो सकते हैं, और ताले की मात्रा को नियंत्रित करके आप समांतरता की मात्रा को नियंत्रित कर सकते हैं।

Answer 3

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

कुशल सम्मिलन आसान है: लिंक की गई सूची, छोड़े गए सरणी, हैशटेबल्स सभी ठीक काम करते हैं। कुशल विलोपन कठिन है क्योंकि इसमें भंडार में हटाई गई चीज़ को ढूंढना शामिल है। कच्चे सादगी और गति के लिए हाउवर, एक लिंक्ड सूची एक अच्छी पसंद है। क्या गैर-व्यस्त समय और वस्तुओं को "निष्क्रिय" के रूप में चिह्नित करने के लिए हटाया जा सकता है? फिर खोजने/हटाने की लागत इतनी सीमित नहीं है।

हालांकि आपको अभी भी ट्रैवर्सल के साथ समस्याएं आ रही हैं। आप जो कुछ भी कर सकते हैं, उसे लॉक करना और स्नैपशॉट लेना है, जिसे स्नैपशॉट देखने के बाद किसी भी बदलाव की जांच करें। कठिन समस्या ...

Answer 4

यदि आपको सॉर्ट ऑर्डर की आवश्यकता नहीं है, तो लाल/काले पेड़ या किसी अन्य चीज का स्वाभाविक रूप से उपयोग न करें।

आपका प्रश्न पढ़ने और लिखने के बीच बातचीत के लिए पर्याप्त w.r.t निर्दिष्ट नहीं है। क्या यह ठीक होगा अगर लॉक + कॉपी + अनलॉक द्वारा "पढ़ा" लागू किया गया है और फिर नई प्रति का उपयोग करें?

आप http://en.wikipedia.org/wiki/Seqlock में सीक्लॉक्स के बारे में पढ़ सकते हैं, और सामान्य रूप से "लॉक फ्री" प्रक्रियाओं पर पढ़ सकते हैं - हालांकि, आप जितनी ज्यादा हो सके अपनी आवश्यकताओं को आराम करना चाहेंगे - लॉक-फ्री हैश टेबल कार्यान्वयन एक प्रमुख है उपक्रम।

Answer 5

लिंक्ड सूचियां निश्चित रूप से यहां उत्तर हैं। ओ (1) में सम्मिलन और विलोपन, एक नोड से अगले में ओ (1) और संचालन में स्थिरता में पुनरावृत्ति। std::list इनमें से सभी की गारंटी देता है, जिसमें सभी इटरेटर वैध हैं जब तक कि सूची सूची से हटा नहीं जाता है (इसमें पॉइंटर्स और तत्वों के संदर्भ शामिल हैं)। लॉक करने के लिए, आप सूची को लॉकिंग क्लास में लपेट सकते हैं, या आप अपनी खुद की सूची कक्षा लिख ​​सकते हैं (आप इस मामले में std::list का उपयोग करने में सक्षम नहीं होंगे जो नोड-आधारित लॉकिंग का समर्थन करता है - उदाहरण के लिए आप कुछ क्षेत्रों को लॉक कर सकते हैं उपयोग के लिए सूची जबकि अन्य धागे अलग-अलग क्षेत्रों पर संचालन करते हैं। जो आप उपयोग करते हैं वह आपके द्वारा अपेक्षित समवर्ती पहुंच के प्रकार पर निर्भर करता है - यदि सूची के विभिन्न हिस्सों पर कई संचालन वास्तव में आम होंगे, तो अपना खुद का लिखें, लेकिन याद रखें कि आप करेंगे प्रत्येक नोड में एक म्यूटेक्स ऑब्जेक्ट डालें, जो अंतरिक्ष-कुशल नहीं है।

Answer 6

क्षमा याचना ...

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

1. यात्रा (धीमा)
2. प्रविष्टि (तेज)
3. विलोपन तो पास स्थिरता अच्छा है पर्याप्त तो ट्रैक रखने:

Answer 7

आप कार्यों के 3 प्रकार हैं सक्रिय पुनरावृत्ति कार्यों के # में से।

पुनरावृत्तियों कार्यों सक्रिय हैं और एक नया डालने या हटाए जाने के कार्य कतार में आता है, तो बाद में प्रसंस्करण के लिए उन कार्यों (लेकिन आप लौट सकते हैं तुरंत फोन करने के लिए) पिछले यात्रा के रूप में जैसे ही

अगर समाप्त प्रक्रिया आवेषण पंक्तिबद्ध और हटा देता है।

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

यदि एक पुनरावृत्ति अनुरोध आता है, तो केवल पुनरावृत्तियों के चलते ही यह चल रहा है और फिर से चल रहा है।

आपको अभी भी जितना तेज़ हो सके डेटा की एक प्रति बनाकर जितना तेज़ हो सके लिखना चाहिए और फिर उस डेटा को क्लाइंट में संसाधित करना चाहिए यदि वास्तविक डेटा प्रोसेसिंग पुनरावृत्ति से बहुत अधिक समय लेती है।

मैं मुख्य संग्रह को हैशटेबल या एसटीएल के साथ कार्यान्वित करता हूं: नक्शा भी तेज़ हो सकता है। एक सूची में सम्मिलित/हटाएं अनुरोध कतारबद्ध किया जा सकता है।

Answer 8

एकमात्र तरीका मुझे लगता है कि यह प्राप्त करने योग्य है, ओरेकल/पोस्टग्रेस्क्ल आदि जैसे डेटाबेस में उपयोग किए जाने वाले मल्टीवर्सन कंसुरेंसी प्रोटोकॉल के समान कुछ है। यह गारंटी देता है कि पाठक पाठकों को अवरुद्ध नहीं करते हैं, लेखक पाठकों को अवरुद्ध नहीं करते हैं, लेकिन लेखक ब्लॉक केवल उन लेखकों जो डेटा के एक ही टुकड़े को अद्यतन करते हैं। लेखक (ओं) को अवरुद्ध करने वाले लेखकों की यह संपत्ति समवर्ती प्रोग्रामिंग दुनिया में डेटा के समान टुकड़े को अद्यतन करती है, अन्यथा डेटा/सिस्टम असंगतता संभव है। डेटा संरचना में प्रत्येक लिखने के संचालन के लिए आप डेटा संरचना का एक स्नैपशॉट लेते हैं या लिखने से पहले स्मृति में किसी भिन्न स्थान पर लिखने के संचालन से प्रभावित डेटा-संरचना नोड्स के हिस्से को कम से कम लेते हैं। तो जब लेखन प्रगति पर है, तो पाठक थ्रेड लेखक भाग से डेटा के एक हिस्से को पढ़ने का अनुरोध करता है, आप हमेशा उन स्नैपशॉट पर नवीनतम स्नैपशॉट & पुनरावृत्त करते हैं, वहां सभी पाठकों को डेटा का निरंतर दृश्य प्रदान करके। स्नैपशॉट महंगा है क्योंकि वे अधिक मेमोरी का उपभोग करते हैं, लेकिन आपकी दी गई आवश्यकता के लिए हाँ, यह तकनीक सही है। और हाँ डेटा के उसी टुकड़े को अद्यतन करने की आवश्यकता वाले अन्य लेखक धागे/प्रक्रियाओं से लिखने के संचालन की सुरक्षा के लिए ताले (म्यूटेक्स/सेमफोर/स्पिनलॉक) का उपयोग करें।

Answer 9

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

हालांकि, इस सी ++ में हल करने के लिए ...

Answer 10

मुझे यकीन है कि किसी को भी इस का उल्लेख किया गया है, तो नहीं कर रहा हूँ बहुत कठिन है, लेकिन मैं जावा के ConcurrentHashMap से प्रेरणा ले जाएगा। यह लॉकिंग या प्रतीक्षा किए बिना ट्रैवर्सल, पुनर्प्राप्ति और सम्मिलन प्रदान करता है। एक बार लॉक होता है जब आपको हैश कुंजी से संबंधित डेटा की बाल्टी मिल जाती है और आप उस बाल्टी को ट्रैवर्स कर रहे हैं (यानी आप केवल बाल्टी को वास्तविक हैश मैप नहीं लॉक करते हैं)। "एक संग्रह लॉक के बजाय, ConcurrentHashMap ताले के एक निश्चित पूल का उपयोग करता है जो बाल्टी के संग्रह पर विभाजन बनाता है।"

आप वास्तविक कार्यान्वयन here पर अधिक जानकारी प्राप्त कर सकते हैं। मेरा मानना ​​है कि कार्यान्वयन में दिखाए गए सभी चीजें सी ++ के साथ आसानी से की जा सकती हैं।

protected static class Entry implements Map.Entry { 
    protected final Object key; 
    protected volatile Object value; 
    protected final int hash; 
    protected final Entry next; 
    ... 
} 

ध्यान दें कि मूल्य अस्थिर है, इसलिए जब हम एक निकालने जा रहे हैं:

1. High throughput. CHECK 
2. Thread safe. CHECK 
3. Efficient inserts happen in O(1). CHECK 
4. Efficient removal (with no data races or locks). CHECK 
5. VERY efficient traversal. CHECK 
6. Does not lock or wait. CHECK 
7. Easy on the memory. CHECK 
8. It is scalable (just increase the lock pool). CHECK 

यहां पर नक्शे प्रविष्टि का एक उदाहरण है:

तो की आवश्यकताओं की अपनी सूची के माध्यम से चलते हैं प्रविष्टि हम मान को एनयूएलएल पर सेट करते हैं जो स्वचालित रूप से दिखाई देता है और कोई अन्य धागा जो मान को पढ़ने का प्रयास करता है।

Answer 11

मैं पार्टी के लिए थोड़ा देर हो चुकी हूं। लेकिन अगर कोई अभी भी इस समस्या का व्यावहारिक समाधान ढूंढ रहा है और उन्होंने अभी तक किसी सर्वर पर निर्णय नहीं लिया है, तो मुझे Google's App Engine का सुझाव दें। इन डेटा की आवश्यकता के लिए उनके डेटास्टोर को अनुकूलित किया गया है।