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

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

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

Answer 2

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

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

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

Answer 3

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