¿Cuál es el nombre de este hash/cache/algoritmo de control de versiones?

Question

Yo lo vi en una presentación de un par de semanas atrás, trató de implementar, y no se olvidó de ella.Pero ahora quiero saber cómo funciona =)

Es una manera eficiente de la transferencia/almacenamiento de datos.Funcionaría en cualquier idioma.Esto es lo que (creo) lo que hace:

Tiene 1 muy grande de archivos (por ejemplo, todo el javascript de la colección de un sitio web).

1. Dividido en bloques de 48 bytes
2. Hash de cada uno de los bloques de 48 bytes (por ejemplo.MD5)
3. Dividir la lista de los bloques en los hashes que terminan con 0x00
4. Los bloques grandes (>= 1 "hash") ahora debe ser de diferentes tamaños.Algunos muy grandes, muy pequeñas.
5. Pegamento de los bloques entre los hash (de nuevo:muy diferentes tamaños de datos reales)
6. Hash esos bloques
7. Ahora usted tiene una lista de hashes que representan la versión actual del archivo de gran tamaño

La idea es que cuando una pieza de cambios de código en el archivo grande, sólo 1 o 2 hashes de cambio.Con el nuevo archivo, puedes hacer todos los pasos anteriores y sólo carga/descarga de las piezas (bloques, identifieable por su hash) que han actyally cambiado.Dependiendo de la cantidad de código que se ha cambiado y en el tamaño de los bloques que rodean ese código, usted nunca tendrá que volver a descargar más de 4 bloques.(En lugar de todo el archivo.) El otro extremo de la comunicación, a continuación, reemplazar el original de bloques (el mismo algoritmo, misma funcionalidad) con los nuevos bloques.

¿Le suena familiar?Se menciona un nombre, pero no podía encontrar nada en ella.Cuando traté de construir, simplemente no funcione, porque si no cambia exactamente 48 bytes [1], TODOS los hash después de que el cambio [2] son diferentes...

Si someonw sabe el nombre de:gran.Si alguien podría explicar también:perfecto!

ACTUALIZACIÓN
Me encontré con la presentación fue en.Se mencionó (y se utiliza) en un nuevo producto "Silo": http://research.microsoft.com/apps/pubs/default.aspx?id=131524 Relacionado con: http://channel9.msdn.com/Events/MIX/MIX11/RES04 (Por lo que en realidad era de investigación de Microsoft!Bien!)

Desde el primer enlace:

Un Silo habilitado página utiliza este local de almacenamiento como un LBFS estilo chunkstore.

En el segundo enlace (un vídeo), las cosas buenas se inicia en 6:30.Ahora he visto dos veces...Yo todavía no lo entiendo =)

Las palabras clave son Delta encoding y Rabin fingerprints.

Answer 1

Esto suena ...tipo de ...como la forma de compresión diferencial remota obras;

En el Bajo ancho de Banda del Sistema de Archivos (LBFS) [24], un RDC se utiliza el protocolo de para optimizar la comunicación entre un remitente y un destinatario, por tener ambos lados de subdividir la totalidad de sus los archivos en trozos y calcular fuerte las sumas de comprobación, o firmas, por cada una de las chunk.Cuando un cliente necesita acceder a o copiar un archivo desde el servidor, el éste transmite primero de la lista de firmas para que el archivo a la cliente, lo que determina que de su viejos trozos pueden ser utilizados para reconstruir el nuevo archivo, y pide a la faltan trozos.La clave para este el protocolo es que los archivos son dividido de forma independiente en el cliente y servidor, mediante la determinación de la porción los límites de las características de los datos.

PDF http://research.microsoft.com/apps/pubs/default.aspx?id=64692

Answer 2

Usted puede resolver los "cambios que no son un múltiplo del tamaño de bloque" problema utilizando rolling hash.Esto es lo que rsync utiliza para transferir sólo cambió partes de un archivo.

Answer 3

Eso suena muy parecido a escalonar el.