एक परिवर्तन लॉग के रूप में एसटीएम-अनुकूल सूची

Question

मुझे परमाणु परिवर्तन लॉग के रूप में उपयोग करने के लिए डेटा संरचना पर एक सलाह चाहिए।

मैं निम्नलिखित एल्गोरिदम लागू करने की कोशिश कर रहा हूं। इन-मेमोरी मैप को अपडेट करने वाले आने वाले परिवर्तनों का प्रवाह है। हास्केल की तरह स्यूडोकोड में यह

update :: DataSet -> SomeListOf Change -> Change -> STM (DataSet, SomeListOf Change) 
    update dataSet existingChanges newChange = do 
     ... 
     return (dataSet, existingChanges ++ [newChange]) 

जहां डेटासेट नक्शा दिया गया है है (वर्तमान में यह STM-कंटेनरों पैकेज, https://hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Map.html से मानचित्र है)। संपूर्ण "अद्यतन" को थ्रेड की मनमानी संख्या से बुलाया जाता है। कुछ परिवर्तनों को डोमेन सेमेन्टिक्स के कारण खारिज कर दिया जा सकता है, मैं लेनदेन के प्रभाव को फेंकने के लिए फेंस्टएमएम का उपयोग करता हूं। सफल प्रतिबद्धता के मामले में सूची में "newChange" जोड़ा जाता है।

flush :: STM (DataSet, SomeListOf Change) -> IO() 

इस समारोह में परिवर्तन (यह एक सुसंगत जोड़ी गया है) की सूची के साथ एक साथ डेटासेट की वर्तमान स्नैपशॉट ले और करने के लिए इसे फ्लश करने के लिए माना जाता है:

अलग थ्रेड जो निम्नलिखित फ़ंक्शन को कॉल भी बना हुआ है फाइल सिस्टम, यानी

flush data = do 
     (dataSet, changes) <- atomically $ readTVar data_ 
     -- write them both to FS 
     -- ... 
     atomically $ writeTVar data_ (dataSet, []) 

मुझे "कुछ सूची बदलें" के लिए उपयोग करने के लिए डेटा संरचना के बारे में एक सलाह चाहिए। मैं [चेंज] का उपयोग नहीं करना चाहता क्योंकि यह "बहुत आदेश दिया गया" है और मुझे डर है कि बहुत सारे संघर्ष होंगे, जो पूरे लेनदेन को फिर से प्रयास करने के लिए मजबूर करेंगे। अगर मैं यहाँ गलत हूं, तो कृपया मुझे सही करें।

मैं सेट (https://hackage.haskell.org/package/stm-containers-0.2.10/docs/STMContainers-Set.html) का उपयोग नहीं कर सकता क्योंकि मुझे अभी भी कुछ ऑर्डर को संरक्षित करने की आवश्यकता है, उदा। लेनदेन का आदेश करता है। मैं इसके लिए टीसीएचएन का उपयोग कर सकता हूं और यह एक अच्छा मैच (बिल्कुल लेनदेन करने का आदेश) जैसा दिखता है, लेकिन मुझे नहीं पता कि "फ्लश" फ़ंक्शन को कैसे कार्यान्वित किया जाए ताकि वह पूरे परिवर्तन लॉग को लगातार एक साथ देख सके डेटासेट के साथ।

वर्तमान कार्यान्वयन यहां https://github.com/lolepezy/rpki-pub-server/blob/add-storage/src/RRDP/Repo.hs है, कार्यों में क्रमशः क्रियाएंस्टेट और rrdpSyncThread लागू होते हैं। यह टीसीएचएन का उपयोग करता है और ऐसा लगता है कि यह गलत तरीके से करता है।

अग्रिम धन्यवाद।

अद्यतन: एक उचित जवाब है कि

type SomeListOf c = TChan [c] 

    update :: DataSet -> TChan [Change] -> Change -> STM DataSet 
    update dataSet existingChanges newChange = do 
     ... 
     writeTChan changeChan $ reverse (newChange : existingChanges) 
     return dataSet 

    flush data_ = do 
     (dataSet, changes) <- atomically $ (,) <$> readTVar data_ <*> readTChan changeChan 
     -- write them both to FS 
     -- ... 

की तरह प्रतीत हो रहा है लेकिन मैं अभी भी यकीन नहीं है कि यह एक साफ समाधान है चैनल के एक तत्व के रूप में पूरी सूची पारित करने के लिए नहीं कर रहा हूँ।

Answer 1

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

update dataSet existingChanges newChange = do 
    -- ... 
    return (dataSet, newChange : existingChanges) 

इसके अलावा, फ्लश के लिए अपने उदाहरण समस्या यह है कि पढ़ने और राज्य को अद्यतन करने पर सभी परमाणु नहीं है। आप एक ही atomically कॉल इसलिए की तरह का उपयोग कर इसे पूरा करना होगा:

flush data = do 
    (dataSet, changes) <- atomically $ do 
    result <- readTVar data_ 
    writeTVar data_ (dataSet, []) 
    return result 

    -- write them both to FS 
    -- ... 

फिर आप सिर्फ उन्हें उलटे क्रम में बाहर लिख सकता है (क्योंकि अब changes नवीनतम के तत्व शामिल सबसे पुराने के लिए) या यहाँ एक बार रिवर्स अगर यह लिखने के लिए महत्वपूर्ण है उन्हें सबसे पुराना सबसे पुराना है।यदि यह महत्वपूर्ण है तो शायद मैं कुछ डेटा संरचना के साथ जाऊंगा जो ओ (1) तत्व को पुराने पुराने वेक्टर की तरह एक्सेस करने की अनुमति देता है।

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

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

Answer 2

मैंने कुछ (बहुत सरल) जांच https://github.com/lolepezy/rpki-pub-server/tree/add-storage/test/changeLog वास्तव में लोड के प्रकार के अनुकरण की नकल की है। मैंने उसी एसटीएमसीओन्टैनर्स का उपयोग किया। डेटा लॉग और परिवर्तन लॉग के लिए सामान्य सूची के लिए मैप। ट्रांजैक्शन रीट्रीज़ की संख्या को ट्रैक करने के लिए, मैंने डीबग.Trace.trace का उपयोग किया, जिसका अर्थ है, ट्रेस द्वारा मुद्रित लाइनों की संख्या। और अद्वितीय ट्रेस द्वारा मुद्रित लाइनों की संख्या मुझे प्रतिबद्ध लेनदेन की संख्या देता है।

परिणाम यहां है (https://github.com/lolepezy/rpki-pub-server/blob/add-storage/test/changeLog/numbers.txt)। पहला स्तंभ धागे की संख्या है, दूसरा कुल मिलाकर परिवर्तन सेट की संख्या है। तीसरा कॉलम बिना किसी बदलाव लॉग के मामले के लिए ट्रेस कॉल की संख्या है और अंतिम एक परिवर्तन लॉग के साथ ट्रेस कॉल की संख्या है।

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