क्या कोई चेकसम एल्गोरिदम है जो इससे "घटाने" डेटा का भी समर्थन करता है?

Question

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

[ 2012/03/26, cs26], 
[ 2012/03/25, cs25], 
[ 2012/03/24, cs24], 
... 

जहां प्रत्येक सीएस की जांच योग है timestamps किसी खास दिन पर बनाए गए सभी दस्तावेज़ों की।

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

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

मैं भी सभी दस्तावेज़ हैंश मेमोरी के साथ हैश पेड़ का उपयोग नहीं करना चाहूंगा, क्योंकि यह लगभग 8 गीगा मेमोरी का उपयोग करेगा, और मुझे लगता है कि यह केवल इस आवश्यकता के लिए ओवरकिल है।

अब के लिए सबसे अच्छा विकल्प पृष्ठभूमि में समय-समय पर इन हैंश को पुन: उत्पन्न करने लगता है, लेकिन यह भी बहुत आवश्यक ओवरहेड है, और परिवर्तनों पर तत्काल जानकारी प्रदान नहीं करेगा।

तो, क्या आप लोग चेकसम एल्गोरिदम के बारे में जानते हैं जो मुझे चेकसम से कुछ डेटा "निकालने" देगा? मुझे एल्गोरिदम को कुछ हद तक तेज़ होने की आवश्यकता है और चेकसम जो सबसे छोटे बदलावों को दृढ़ता से इंगित करेगा (यही कारण है कि मैं वास्तव में सादा एक्सओआर का उपयोग नहीं कर सकता)।

या शायद आपके पास पूरे डिज़ाइन के बारे में बेहतर विचार हैं?

Answer 1

के बारे में

hash = X(documents, 0, function(document) { ... }) 

जहाँ X एक समग्र XOR (जावास्क्रिप्ट-y स्यूडोकोड इस प्रकार) है कैसे:

function X(documents, x, f) 
{ 
    for each (var document in documents) 
    { 
     x ^= f(document); 
    } 
    return x; 
} 

और च() अलग-अलग दस्तावेज़ में जानकारी का एक हैश है? (चाहे टाइमस्टैम्प या फ़ाइल नाम या आईडी या जो भी हो)

एक्सओआर का उपयोग आपको दस्तावेज़ों को "घटाना" करने की अनुमति देगा, लेकिन प्रति-दस्तावेज़ आधार पर हैश का उपयोग करने से आप छोटे से पता लगाने की हैश जैसी गुणवत्ता को सुरक्षित रख सकते हैं परिवर्तन।