मेरे पास एक नक्शा है जो स्ट्रिंग्स को एक आईडी से जोड़ना चाहिए। आईडी के बीच अंतराल नहीं होना चाहिए और वे 0 से N तक अद्वितीय पूर्णांक होने चाहिए।

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

मैं यह नहीं देखता कि मानचित्र में पहले से मौजूद चाबियों के क्रम में अंतराल बनाए बिना AtomicInteger का उपयोग कैसे किया जाए।

public class Foo {
    private final Map<String, Integer> idGenerator = new ConcurrentHashMap<>();

    // invoked from multiple threads
    public void update(String key1, String key2) {
      idGenerator.dosomething(key, ?) // should save the key and unique id
      idGenerator.dosomething(key2, ?) // should save the key2 and its unique id
      Bar bar = new Bar(idGenerator.get(key), idGenerator.get(key2));
      // ... do something with bar
   }
}

मुझे लगता है कि size() विधि merge() के साथ मिलकर समस्या का समाधान कर सकती है लेकिन मैं खुद को इसके बारे में पूरी तरह से आश्वस्त नहीं कर सकता। क्या कोई इस समस्या के लिए कोई दृष्टिकोण सुझा सकता है?

संपादित करें

डुप्लिकेट ध्वज के संबंध में, इसे AtomicInteger.incrementAndGet() के साथ हल नहीं किया जा सकता जैसा कि लिंक किए गए उत्तर में सुझाया गया है। अगर मैंने इसे हर स्ट्रिंग के लिए आँख बंद करके किया तो अनुक्रमों में अंतराल होगा। यौगिक ऑपरेशन की आवश्यकता है जो जांचता है कि कुंजी मौजूद है या नहीं और उसके बाद ही आईडी उत्पन्न करता है। मैं Map API के माध्यम से इस तरह के कंपाउंड ऑपरेशन को लागू करने का तरीका ढूंढ रहा था।

दूसरा प्रदान किया गया उत्तर उन आवश्यकताओं के विरुद्ध जाता है जिन्हें मैंने विशेष रूप से प्रश्न में निर्धारित किया है।

2
John 22 सितंबर 2018, 11:08

2 जवाब

सबसे बढ़िया उत्तर

इसे ठीक वैसे ही करने का कोई तरीका नहीं है जैसा आप चाहते हैं -- ConcurrentHashMap अपने आप में लॉक-फ्री नहीं है। हालांकि, आप इसे बिना किसी स्पष्ट लॉक प्रबंधन के java.util.Map.computeIfAbsent फ़ंक्शन।

आपके द्वारा प्रदान की गई शैली में एक कोड नमूना यहां दिया गया है जो आपको जाना चाहिए।

ConcurrentHashMap<String, Integer> keyMap = new ConcurrentHashMap<>();
AtomicInteger sequence = new AtomicInteger();

public void update(String key1, String key2) {
    Integer id1 = keyMap.computeIfAbsent(key1, s -> sequence.getAndIncrement());
    Integer id2 = keyMap.computeIfAbsent(key2, s -> sequence.getAndIncrement());

    Bar bar = new Bar(id1, id2);
    // ... do something with bar
}
4
lscoughlin 22 सितंबर 2018, 12:04

मुझे यकीन नहीं है कि आप ठीक वही कर सकते हैं जो आप चाहते हैं। हालांकि, आप कुछ अपडेट बैच कर सकते हैं, या एन्यूमरेटिंग/जोड़ने से अलग से जांच कर सकते हैं।

इस उत्तर में से बहुत से यह मानते हैं कि आदेश महत्वपूर्ण नहीं है: आपको सभी तारों को एक संख्या दी गई है, लेकिन एक जोड़ी के भीतर भी पुन: व्यवस्थित करना ठीक है, है ना? संगामिति पहले से ही जोड़े के पुनर्क्रमण का कारण बन सकती है, या एक जोड़ी के सदस्यों को सन्निहित संख्या नहीं मिल सकती है, लेकिन पुन: क्रमबद्ध करने से जोड़ी के पहले जोड़े को अधिक संख्या मिल सकती है।

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

यदि अधिकांश खोजें हिट होती हैं, तो हमें अधिकतर मानचित्र पर रीड थ्रूपुट की आवश्यकता होती है।

एक अकेला लेखक धागा पर्याप्त हो सकता है।

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

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

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


मुख्य फ्रंट-एंड थ्रेड्स के बीच विवाद को कम करने के लिए, आपके पास कई कतारें हो सकती हैं, जैसे कि प्रत्येक थ्रेड में एकल-निर्माता/एकल-उपभोक्ता कतार हो सकती है, या भौतिक कोर की एक जोड़ी पर चलने वाले 4 थ्रेड्स का समूह एक कतार साझा करता है।

एन्यूमरेटिंग थ्रेड उन सभी से पढ़ता है।

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


किसी प्रकार की read-copy-update (RCU) डेटा संरचना अच्छा हो सकता है, अगर जावा में वह है। यह पाठकों को पूरी गति से डुप्लीकेट को फ़िल्टर करने देता है, जबकि एन्यूमरेटिंग थ्रेड एक नई तालिका बनाता है जिसमें सम्मिलन के बैच के साथ शून्य विवाद होता है, जबकि यह नई तालिका बना रहा है।


90% हिट दर के साथ, एक लेखक धागा शायद 10 या इतने पाठक धागे के साथ रह सकता है जो मुख्य तालिका के खिलाफ नई कुंजी फ़िल्टर करते हैं।

आप एकल लेखक धागे से बैक-प्रेशर की अनुमति देने के लिए कुछ कतार-आकार की सीमा निर्धारित करना चाह सकते हैं। या यदि आपके पास एक लेखक की तुलना में कई और कोर/धागे हैं, तो हो सकता है कि किसी प्रकार का समवर्ती सेट नंबरिंग से पहले डुप्लिकेट को खत्म करने के लिए किसी प्रकार का समवर्ती सेट हो।

या वास्तव में, यदि आप सब कुछ संख्या के अंत तक प्रतीक्षा कर सकते हैं, तो यह बहुत आसान होगा, मुझे लगता है।

मैंने सोचा कि शायद दौड़ की स्थिति में त्रुटि के लिए कमरे के साथ संख्या की कोशिश कर रहा है, और फिर चीजों को ठीक करने के लिए वापस जा रहा है, लेकिन शायद यह बेहतर नहीं है।

3
Peter Cordes 22 सितंबर 2018, 13:00