z*****n
发帖数: 447 | 1 Vmware的电面题，有一个分布式FTP Cluster，包含N台FTP服务器，一台为Master，上
面存放了一个很大的文件，比如10T, 剩下的N-1台是Slave，问你如何设计一个同步算
法，把Master上的文件同步到Slave上，要求cost越小越好？
我回答的是，把Master上的文件分成一个个的小Chunk，给每个Chunk算一个checksum，
然后每次同步的时候，再算一遍并检查checksum，如果某chunk的checksum变了，就把
这个chunk同步到Slave上。
Interviewer对此表示赞同，但是又追问了一个问题，他说，如果文件中的某一部分被
删掉了,比如第一个chunk删掉了1个Byte，但是这个删除的操作和位置你是不知道的，
如果还按照原来的chunk size计算checksum，会发现所有chunk的chunksum都改变了，
而实际上只有一个改了；这种情况下，怎么解决？
这部分我没有答出来，有谁能够帮忙分析一下？ |
s******n
发帖数: 3946 | 2 create a patch and send patch |
w****x
发帖数: 2483 | 3 是不是像svn那样每个操作都记录下来, 包括删除操作.
或者真的把10T的大文件分成10000000个小文件, 记录每次修改的小文件编号, 然后以
后只替换对应编号的小文件?? |
z**********g
发帖数: 209 | 4 请问你的回答是不是和下面的介绍rsync一样？
rsync算法要解决的问题很简单：A和B两个文件在两台服务器中，要将A同步到与B一致
，要求尽量减少同步带来的网络传输开销。
rsync基本算法
先说基本的rsync算法，并不复杂，简单的说是三步：
1、按固定大小将A分为多块，每块都计算出一个32位的滚动哈希值和一个128位的MD4（
有些也用MD5），发给B一端。
2、B一端从位置0开始按的同样块大小的滚动哈希值，查找看是否命中A给的某个滚动哈
希值，若匹配，则表明B文件中的这块内容与对应的A中的那块内容很可能是一致的，但
由于32位的哈希值强度不够，因此再计算MD4，若还是匹配，则确认是一致内容，这时B
发给A端匹配的段号。对于那些不能匹配的内容，则发给A端原始内容。
3、A端得到B端给的匹配信息，构造一个与B一致的复本，若是匹配的块，则拷贝原A文
件中对应的块，若是不匹配内容则追加之。
滚动哈希值的设计基于Adler32算法，使得2~K+1字节的哈希可以根据1~K字节哈希和1、
K+1字节的内容快速计算得到，这可以提高从位置0开始依次计算滚动哈希值的效率。
据试验一般来说块大小取500~1000字节效果比较好。 |
z*****n
发帖数: 447 | 5 当时我没有回答出来，interviewer也没告诉具体答案，只说用一种特殊的Hash 函数，
然后用sliding window一个个的滑动计算相邻的chunk的checksum，最后可以比较出来
。结果面挂了。。。：（
我感觉rsync和这个思路很一致，应该就是这样！好像dropbox也是这样做同步的。
时B
【在 z**********g 的大作中提到】
: 请问你的回答是不是和下面的介绍rsync一样？
: rsync算法要解决的问题很简单：A和B两个文件在两台服务器中，要将A同步到与B一致
: ，要求尽量减少同步带来的网络传输开销。
: rsync基本算法
: 先说基本的rsync算法，并不复杂，简单的说是三步：
: 1、按固定大小将A分为多块，每块都计算出一个32位的滚动哈希值和一个128位的MD4（
: 有些也用MD5），发给B一端。
: 2、B一端从位置0开始按的同样块大小的滚动哈希值，查找看是否命中A给的某个滚动哈
: 希值，若匹配，则表明B文件中的这块内容与对应的A中的那块内容很可能是一致的，但
: 由于32位的哈希值强度不够，因此再计算MD4，若还是匹配，则确认是一致内容，这时B
|
g*****i
发帖数: 2162 | 6 mark
时B
【在 z**********g 的大作中提到】
: 请问你的回答是不是和下面的介绍rsync一样？
: rsync算法要解决的问题很简单：A和B两个文件在两台服务器中，要将A同步到与B一致
: ，要求尽量减少同步带来的网络传输开销。
: rsync基本算法
: 先说基本的rsync算法，并不复杂，简单的说是三步：
: 1、按固定大小将A分为多块，每块都计算出一个32位的滚动哈希值和一个128位的MD4（
: 有些也用MD5），发给B一端。
: 2、B一端从位置0开始按的同样块大小的滚动哈希值，查找看是否命中A给的某个滚动哈
: 希值，若匹配，则表明B文件中的这块内容与对应的A中的那块内容很可能是一致的，但
: 由于32位的哈希值强度不够，因此再计算MD4，若还是匹配，则确认是一致内容，这时B
|
