坚果云如何提高存储空间有效率

这个内容本是回答知乎上的一个问题。我的回答解释坚果云是如何采取措施更好的检测文件内和文件间重复数据,因此与大家分享。根据我们有限的了解,坚果云在提高存储空间利用率方面在整个业界(国内和国外)都是非常优秀的,即使是和Amazon,Google, Microsoft, IBM, EMC等有深厚积累的巨头相比。当然,巨头们也很可能有没有披露的秘密方案,我们也是这样 :-)

这只是坚果云采取的众多机制的一种。其他方面的技术我们会适时披露。

如果您对这些内容感兴趣,给我们一封邮件,我们欢迎您的加入。 邮件至joinus@nutstore.net

关于楼上提到的交叉文件差异分析和动态分片等方式,坚果云都进行过非常深入的思考和仔细的研究。

固定分块的数据去重(de-duplication)
其 他朋友的回答中,采用固定分块比较的方式,这是数据去重的第一个阶段。利用哈希树算法(Merkle Tree)【1】,计算分块的特征值。如果分块已经存储在系统中,无需再次存储,直接进行交叉引用。 减少存储空间和加快上传速度。这个方式几乎所有的云存储服务商都提供,包括坚果云。

这个方式对于不太修改的文件,尤其是照片视频等多媒体文件效果很好。但是它有一个致命的缺点,一旦在文件中的开始增加或者删除一个比特,整个文件的分块情况会完全变化,大量的数据重复将无法检测,因此其不适用于数据经常修改的场合,比如办公文档和设计文档等。

不过,目前大多服务(包括dropbox)都只用了简单的hash检测重复的分块,这在数据隐私性上有一定的漏洞。这个问题比较复杂,如果环境允许,我们会适度的披露更多信息和解决办法。

单个文件不同版本之间的数据去重
这是数据去重的第二个阶段。

这个办法主要是利用某种形式的滑动窗口动态检测数据分块的边界,从而除了能够检测到固定的重复分块外。也可以避免因为上述的数据插入或者删除导致的算法失效。上面提到的rsync【3】算法也使用了类似的思想。

这类型的算法有个好处,完全可以通过客户端本地匹配,节约服务器的计算和IO资源。

Dropbox和坚果云都在产品发布的开始用了类似的手段,这也是经常提到的“增量同步”。国内的其他厂商最近也在逐步采用这个方法,或许某天,它应该是云存储产品的一个必备功能。

不同文件之间的数据去重
这是数据去重的第三个阶段。

不同文件的数据去重,总体上类似上面的第二个阶段,在不同文件中利用某种滑动窗口算法动态将数据分块,然后利用第一种方式的hash算法,在服务器上查询重复分块。

这个方法有个大问题:
1)窗口滑动的时候有一个假设,假定目标数据是完全随机的,从而保证窗口的设定(分块的大小)也是随机的。如果数据不满足随机性,容易导致分片数目过多或者过少。
2)该算法不能通过客户端执行,必须在服务器上执行

这个算法的关键是找到合适的手段,控制文件分片后的数目。分片太多容易增大服务器查找重复分片的负担,分片太少容易导致去重的效率下降。这个算法不适合在用户存入数据的时候就进行处理,也就是不适合在线处理。

坚果云在这个方面研究发现,利用这个算法,离线分批的对某些类型的数据进行处理可以很好的降低存储成本。某些高端的数据归档(data archive)系统,也用了类似的手段对于不经常访问的数据进行去重。

【1】en.wikipedia.org/wiki…
【2】blog.jianguoyun.com
【3】en.wikipedia.org/wiki…

    分享到:
此条目发表在 使用技巧, 技术分享 分类目录。将固定链接加入收藏夹。

坚果云如何提高存储空间有效率》有 3 条评论

  1. Lamb 说:

    增量同步:PC/Mac端其实对增量等功能不是很在意,目前移动设备端很在意。
    分块存储:上面也还是说的很含糊。其实我最在意的就是分块了,在合并成完整文件的时候会不会很慢。svn就是记录增量的(类似与分块,只是块分的就是每次的变化),git是很原始的保存整个文件。git要比svn快很多。牺牲空间换时间,现在的空间还是很廉价的。
    我用了很多的网盘类的产品,坚果云的是使用是因为公司和坚果有合作意向,才会注意和使用。