Esiste un algoritmo di checksum che supporti anche i dati di "sottrazione" da esso?

Question

Ho un sistema con circa 100 milioni di documenti, e mi piacerebbe tenere traccia delle loro modifiche tra specchi. Per scambiare informazioni sulle modifiche in modo efficace, voglio inviare informazioni sui documenti modificati per giorni, non per ogni documento separato. Qualcosa di simile a questo:

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

dove ogni cs è il checksum del timestamp di tutti i documenti creati in un particolare giorno.

Ora, il problema che sto funzionando in è che non so di un algoritmo in grado di "sottrarre" i dati dalla somma di controllo quando un documento viene eliminato. Nessuno degli hash crittografici soddisfa le necessità, per ovvi motivi, e non sono riuscito a trovare alcun algoritmo per CRC in grado di farlo.

Una possibilità ho considerato era di avere Elimina aggiungere informazioni extra per l'hash, ma questo porterebbe a problemi ancora di più, come i nodi possono ricevere le richieste di eliminazione in ordine diverso, e quando un nodo doveva riprendere sarebbe rileggere tutto i timestamp dei documenti e quindi le informazioni sulle eliminazioni andrebbero persi.

Anche io non vorrei usare un hash tree con tutti gli hash del documento in memoria, in quanto ciò userebbe circa 8 giga di memoria, e penso che sia un po 'eccessivo per questa sola esigenza.

Per ora l'opzione migliore sembra rigenerare questi hash completamente di volta in volta in background, ma anche un sovraccarico inutile e non fornirebbe informazioni immediate sulle modifiche.

Quindi, voi ragazzi a conoscenza di un algoritmo di checksum che mi permetteva di "rimuovere" alcuni dati dalla somma di controllo? Ho bisogno che l'algoritmo sia un po 'veloce e il checksum che indicherebbe fortemente il più piccolo dei cambiamenti (è per questo che non posso davvero usare XOR normale).

O forse è meglio avere idee circa l'intero progetto?

Answer 1

Come su

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

dove X è un XOR aggregata (javascript-y pseudocodice segue):

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

e f() è un hash di informazioni singolo documento? (sia timestamp o nomefile o ID o qualsiasi altra cosa)

L'uso di XOR consente di "sottrarre" i documenti, ma l'utilizzo di un hash su base per documento consente di preservare una qualità di tipo hash di rilevamento di piccole dimensioni i cambiamenti.