algorithm - 这个散列/缓存/版本控制算法的名称是什么？

Question

我在几周前的一次演示中看到它，尝试实现它，但失败了，然后忘记了它。但现在我想知道它是如何工作的 =)

这是一种高效传输/存储数据的方式。它适用于任何语言。这就是(我认为)它的作用:

您有 1 个非常大的文件(例如网站的整个 javascript 集合)。

1. 将其分成 48 字节的 block
2. 散列每个 48 字节的 block (例如 MD5)
3. 根据以 0x00 结尾的散列拆分块列表
4. 大块(>= 1 个哈希)现在应该有不同的大小。有些很大，有些很小。
5. 在这些散列之间粘合 block (同样:实际数据的大小非常不同)
6. 散列这些 block
7. 现在你有一个代表大文件当前版本的散列列表

这个想法是，当大文件中的一段代码发生变化时，只有 1 或 2 个哈希值发生变化。使用新文件，您执行上述所有步骤，并且只上传/下载实际更改的部分( block ，可通过其哈希值识别)。根据更改的代码量和代码周围 block 的大小，您永远不需要下载超过 4 个 block 。 (而不是整个文件。)然后通信的另一端将用新 block 替换原始 block (相同的算法，相同的功能)。

听起来很熟悉？他们提到了一个名字，但在上面找不到任何东西。当我尝试构建它时，它就是行不通，因为如果你不恰好更改 48 个字节 [1]，那么更改 [2] 之后的所有哈希值都是不同的...

如果有人知道这个名字:太好了。如果有人也能解释一下:完美!

更新
我找到了它所在的演示文稿。它在新产品“Silo”中被提及(并使用):http://research.microsoft.com/apps/pubs/default.aspx?id=131524相关:http://channel9.msdn.com/Events/MIX/MIX11/RES04 (所以它实际上是微软的研究!整洁!)

从第一个链接:

A Silo-enabled page uses this local storage as an LBFS-style chunkstore.

在第二个链接(视频)中，精彩内容从 6:30 开始。现在我已经看过两次了......我还是不明白=)

关键字是Delta编码和Rabin指纹。

Answer 1

这听起来……有点……像远程差分压缩的工作原理；

In the Low Bandwidth File System (LBFS) [24], an RDC protocol is used to optimize the communication between a sender and a recipient by having both sides subdivide all of their files into chunks and compute strong checksums, or signatures, for each chunk. When a client needs to access or copy a file from the server, the latter first transmits the list of signatures for that file to the client, which determines which of its old chunks may be used to reconstruct the new file, and requests the missing chunks. The key to this protocol is that the files are divided independently on the client and server, by determining chunk boundaries from data features.

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