Czy istnieje algorytm sumy kontrolnej, który obsługuje również "odejmowanie" od niej danych?

Question

Mam system z około 100 milionami dokumentów i chciałbym śledzić ich modyfikacje między lustrami. Aby skutecznie wymieniać informacje o modyfikacjach, chcę wysyłać informacje o zmodyfikowanych dokumentach przez dni, a nie przez każdy osobny dokument. Coś takiego:

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

gdzie każdy cs jest suma kontrolna znacznika czasu wszystkich dokumentów tworzonych w danym dniu.

Problem polega na tym, że nie znam algorytmu, który mógłby "odjąć" dane z sumy kontrolnej, gdy dokument jest usuwany. Żadne z skrótów kryptograficznych nie pasowało do potrzeb, z oczywistych powodów, i nie mogłem znaleźć żadnego algorytmu dla CRC, który by to zrobił.

Jedną z opcji, którą rozważałem, było usunięcie dodatkowych informacji do hasza, ale spowodowałoby to jeszcze więcej problemów, ponieważ węzły mogą odbierać żądania usunięcia w innej kolejności, a gdy węzeł uruchomi się ponownie, to ponownie znaczniki czasu z dokumentów, a tym samym informacje o usunięciach zostaną utracone.

Ja także nie chciałbym używać drzewa hash z wszystkimi haszami w pamięci, ponieważ zużywałoby to około 8 gigabajtów pamięci i myślę, że jest to trochę przesadzone dla tej potrzeby.

Na razie najlepsza opcja wydaje się odradzać te skróty od czasu do czasu w tle, ale jest to również dużo niepotrzebnego narzutu i nie zapewnia natychmiastowych informacji o zmianach.

Więc, czy znacie algorytm sumy kontrolnej, który pozwoliłby mi "usunąć" niektóre dane z sumy kontrolnej? Potrzebuję algorytmu, który będzie trochę szybki i sumy kontrolnej, która zdecydowanie wskaże najmniejszą zmianę (dlatego nie mogę tak naprawdę użyć zwykłego XOR).

A może masz lepsze pomysły na temat całego projektu?

Answer 1

Jak o

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

gdzie X jest agregatem XOR (javascript-y pseudokod następująco):

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

i F() to skrót od indywidualnych informacji o dokumencie? (niezależnie od tego, czy znacznik czasu, nazwa pliku lub jakikolwiek identyfikator) czy nie,

Użycie XOR pozwoliłoby na "odjęcie" dokumentów, ale użycie skrótu na podstawie dokumentu pozwala zachować niską jakość wykrywania małych znaków zmiany.