Как называется этот алгоритм хеширования / кэширования / управления версиями?

Question

Я видел это в презентации несколько недель назад, пытался реализовать, потерпел неудачу и забыл об этом. Но теперь я хочу знать, как это работает =)

Это способ эффективной передачи / хранения данных. Это будет работать на любом языке. Вот что (я думаю) это делает:

У вас есть 1 очень большой файл (например, вся коллекция javascript на сайте).

1. Разделить его на блоки по 48 байт
2. Хэшируйте каждый блок из 48 байтов (например, MD5)
3. Разделить список блоков на хэши, заканчивающиеся на 0x00
4. Большие блоки (>= 1 хеш) теперь должны быть разных размеров. Некоторые очень большие, некоторые очень маленькие.
5. Склейте блоки между этими хэшами (опять же: очень разные размеры фактических данных)
6. Хэш эти блоки
7. Теперь у вас есть список хэшей, которые представляют текущую версию большого файла

Идея состоит в том, что когда часть кода изменяется в большом файле, меняются только 1 или 2 хеша. С новым файлом вы выполняете все вышеперечисленные шаги и загружаете / скачиваете только те части (блоки, которые можно идентифицировать по хешу), которые фактически изменились. В зависимости от того, сколько кода было изменено и от размера блоков, окружающих этот код, вам никогда не потребуется загружать более 4 блоков. (Вместо целого файла.) Другой конец сообщения затем заменит исходные блоки (тот же алгоритм, те же функции) на новые блоки.

Звучит знакомо? Они упомянули имя, но ничего не нашли на нем. Когда я пытался построить его, он просто не работал, потому что если вы не измените точно 48 байтов [1], ВСЕ хэши после этого изменения [2] будут разными...

Если кто-то знает имя: отлично. Если кто-то может объяснить это также: идеально!

ОБНОВИТЬ
Я нашел презентацию, в которой она была. Она была упомянута (и используется) в новом продукте "Бункер": http://research.microsoft.com/apps/pubs/default.aspx?id=131524 Связанный: http://channel9.msdn.com/Events/MIX/MIX11/RES04 (Так что на самом деле это было исследование Microsoft! Аккуратно!)

С первой ссылки:

Страница с поддержкой Silo использует это локальное хранилище как хранилище в стиле LBFS.

Во второй ссылке (видео), хороший материал начинается с 6:30, Теперь я видел это дважды... Я до сих пор не понимаю =)

Ключевые слова Delta encoding а также Rabin fingerprints,

Answer 1

Это звучит... вроде... как то, как работает дистанционное дифференциальное сжатие;

В файловой системе с низкой пропускной способностью (LBFS) [24] протокол RDC используется для оптимизации связи между отправителем и получателем, поскольку обе стороны разделяют все свои файлы на порции и вычисляют надежные контрольные суммы или сигнатуры для каждого порции, Когда клиенту необходимо получить доступ или скопировать файл с сервера, последний сначала передает список подписей для этого файла клиенту, который определяет, какие из его старых чанков могут использоваться для восстановления нового файла, и запрашивает отсутствующие чанки., Ключом к этому протоколу является то, что файлы разделяются независимо на клиенте и сервере, определяя границы чанков из функций данных.

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

Answer 2

Вы можете решить проблему "изменений, не кратных размеру блока", используя скользящие хэши. Это то, что rsync использует для передачи только измененных частей файла.

Answer 3

Это звучит очень похоже на шипение.