Sincronizzazione dei dati di Merkle Tree Falsi positivi

Question

Gli alberi di merle (ovvero gli alberi di hash) vengono utilizzati per la sincronizzazione dei dati sia in "Cassandra" & "Dynamo".

Come con qualsiasi funzione hash, v'è una probabilità che dati diversi possono avere lo stesso valore di hash:

Esiste un x ed y dove [! Y = x] ma [hash (x) = hash (y)]

Man mano che i "big data" in NOSQL aumentano, la probabilità di incontrare tali dati aumenta.

Ciò significa che quando i set di dati diventano più grandi, è quasi certo che nodi diversi nell'albero Merkle genereranno lo stesso hash genitore.

In tale occasione, quando due macchine diverse nel cluster attraversano i loro alberi di merle, otterranno un falso positivo che i loro dati siano coerenti. Se non si scrivono più dati su quel ramo dell'albero, le macchine rimarranno non sincronizzate per sempre.

Come viene gestito?

Answer 1

La maggior parte dei sistemi non gestisce questo. Perché? Perché la probabilità di avere due input diversi con lo stesso valore hash è molto, molto bassa. Con una buona funzione di hash (che penso tu stia usando), questo dovrebbe avvicinarsi a 1/2 {hash-bit}. E poiché la maggior parte degli hash per questi scopi sono lunghi almeno 128 bit, si ottiene una probabilità di 1/2^128 di tale collisione. Che è circa 2.9387359e-39 (0. {38 zeri} 29387359).

Utilizzando un hash di 160 bit (che la maggior parte di questi sistemi utilizza, hash SHA-1), è sufficiente che quando si dispone di tanti oggetti nel database quanti sono i granelli di sabbia nel mondo. Che hai ancora meno di una probabilità di 1/2 che ci sarà una tale collisione. Quindi, non mi preoccuperei del caso in cui c'è una collisione. La probabilità che ciò accada è davvero troppo bassa.