Estoy en una búsqueda personal para aprender cómo funciona el algoritmo rsync. Después de leer y pensar, he llegado a una situación en la que creo que el algoritmo falla. Estoy intentando descubrir cómo se resuelve esto en una implementación real.¿Cómo el algoritmo de rsync identifica correctamente los bloques que se repiten?
Considere este ejemplo, donde A es el receptor y B es el remitente.
A = abcde1234512345fghij
B = abcde12345fghij
Como se puede ver, el único cambio es que 12345 se ha eliminado.
Ahora, para que este ejemplo sea interesante, seleccionemos un tamaño de bloque de 5 bytes (caracteres). Hashing los valores en el lado del remitente utilizando la suma de comprobación débil da la siguiente lista de valores.
abcde|12345|fghij
abcde -> 495
12345 -> 255
fghij -> 520
values = [495, 255, 520]
A continuación, comprobamos para ver si los valores de hash difieren en A. Si hay un bloque de adaptación podemos saltar al final de ese bloque para el próximo cheque. Si hay un bloque que no coincide, entonces hemos encontrado una diferencia. Pasaré por este proceso.
- Hash el primer bloque. ¿Este hash existe en la lista de valores?
abcde -> 495(sí, así que omita) - Hash el segundo bloque. ¿Este hash existe en la lista de valores?
12345 -> 255(sí, así que omita) - Hash the third block. ¿Este hash existe en la lista de valores?
12345 -> 255(sí, así que omita) - Hash el cuarto bloque. ¿Este hash existe en la lista de valores?
fghij -> 520(sí, así que salte) - No más datos, hemos terminado.
Como cada hash se encontró en la lista de valores, concluimos que A y B son iguales. Lo cual, en mi humilde opinión, no es verdad.
Me parece que esto sucederá cada vez que haya más de un bloque que comparta el mismo hash. Sé que me salté el paso de calcular y verificar el hash fuerte, pero eso no hará la diferencia ya que el segundo y el tercer bloque son exactamente los mismos
¿Qué me estoy perdiendo?
La pregunta podría usar más etiquetas :) (por ejemplo, algoritmo?) –