雲存儲的相似多文件差異分析現在在工程界是什麼進展？

01-08

1. 相似多文件指的是：
假設A用戶有A.doc，而用戶B有B1.doc，B2.doc，如果A的前半部分和B1很像，後半部分和B2很像，而B1和B2已由B上傳到伺服器上，那麼A上傳A.doc可以很快，因為只需要上傳與B1和B2不一樣的地方，然後再拼接。
2. 我有個理論上的模型可以實現這個效果：是單文件差異比較演算法Rsync（http://en.wikipedia.org/wiki/Rsync#Algorithm）的多文件交叉對比改進版，但是在伺服器端必須用雙倍的存儲。我想和大家討論的是：
① 這個多文件模型有什麼進一步的應用背景？就是為什麼它很重要（也即motivation，動機，出現在paper的introduction里）？我覺得我提的這個應用場景、外加可以實現兩台網路節點之間的定期資料同步，都還不足夠重要。

② 如果你是金山，你會採用這樣的模型嗎？注意這需要付出雙倍存儲的代價，也即存一個1G的文件實際需要滿佔2G的硬碟空間。轉嫁到用戶上，就是原來你有10G的空間，現在給你減到5G；或者，原來你付10元/月，現在要你付20元/月，以此來獲得這個功能。
③ 如果真轉嫁到用戶身上了，你作為用戶，你覺得能接受嗎？
④ 據我的測試，Dropbox還沒有做多文件交叉差異檢測。Dropbox是真的沒做嗎？還是做了但是舍掉了？國內的雲存儲服務商（DBank，Everbox，TPan，KPan）在這上面是怎樣的進展？
[補充說明一]請看問題本身的評論

關於樓上提到的交叉文件差異分析和動態分片等方式，堅果雲都進行過非常深入的思考和仔細的研究。

固定分塊的數據去重(de-duplication)

其他朋友的回答中，採用固定分塊比較的方式，這是數據去重的第一個階段。利用哈希樹演算法(Merkle Tree)【1】，計算分塊的特徵值。如果分塊已經存儲在系統中，無需再次存儲，直接進行交叉引用。減少存儲空間和加快上傳速度。這個方式幾乎所有的雲存儲服務商都提供，包括堅果雲。

這個方式對於不太修改的文件，尤其是照片視頻等多媒體文件效果很好。但是它有一個致命的缺點，一旦在文件中的開始增加或者刪除一個比特，整個文件的分塊情況會完全變化，大量的數據重複將無法檢測，因此其不適用於數據經常修改的場合，比如辦公文檔和設計文檔等。

不過，目前大多服務（包括dropbox)都只用了簡單的hash檢測重複的分塊，這在數據隱私性上有一定的漏洞。這個問題比較複雜，如果環境允許，我們可能在堅果雲的博客【2】上適度的披露更多信息和解決辦法。

單個文件不同版本之間的數據去重

這是數據去重的第二個階段。

這個辦法主要是利用某種形式的滑動窗口動態檢測數據分塊的邊界，從而除了能夠檢測到固定的重複分塊外。也可以避免因為上述的數據插入或者刪除導致的演算法失效。上面提到的rsync【3】演算法其實也使用了類似的思想。

這類型的演算法有個好處，完全可以通過客戶端本地匹配，節約伺服器的計算和IO資源。

Dropbox和堅果雲都在產品發布的開始用了類似的手段，這也是經常提到的「增量同步」的一個形式。國內的其他廠商最近也在逐步採用這個方法，或許某天，它應該是雲存儲產品的一個必備功能。

不同文件之間的數據去重

這是數據去重的第三個階段。

不同文件的數據去重，總體上類似上面的第二個階段，在不同文件中利用某種滑動窗口演算法動態將數據分塊，然後利用第一種方式的hash演算法，在伺服器上查詢重複分塊。

這個方法有個大問題：

1）窗口滑動的時候有一個假設，假定目標數據是完全隨機的，從而保證窗口的設定（分塊的大小）也是隨機的。如果數據不滿足隨機性，容易導致分片數目過多或者過少。

2）該演算法不能通過客戶端執行，必須在伺服器上執行

這個演算法的關鍵是找到合適的手段，控制文件分片後的數目。分片太多容易增大伺服器查找重複分片的負擔，分片太少容易導致去重的效率下降。

堅果雲在這個方面也有很好的研究，我們發現，利用這個演算法，離線的對某些類型的數據進行處理可以很好的降低存儲成本。某些高端的數據歸檔（data archive)系統，也用了類似的手段對於不經常訪問的數據進行去重。

【補充】針對提問者在評論中提出的問題：

如果需要在上傳數據前就根據第三部份的方法消除重複的部分，那麼可能需要解決因為分塊太多導致的過高的伺服器性能開銷（在保證去重性能的前提下）。這個很大程度上是一個工程問題，也就是投入產出的問題，而不是能做不能做的問題。如果是後者的話，那麼肯定是能做的

【1】http://en.wikipedia.org/wiki/Hash_tree

【2】http://blog.jianguoyun.com

【3】http://en.wikipedia.org/wiki/Rsync

1.就你提供的例子：doc文檔來說。doc是一個複合文檔。複合文檔的意義在於他有自己的文件格式，並不類似於文本文件--你在後續加入的內容一定也只能導致源文件尾部的數據有變化。你對一個doc文檔的頭或者尾有改動，有可能導致真正文件的2進位數據的任何一個部分有改動。類似的有zip文件等等。

2.由於1的原因，所以只有在文件數據分塊足夠小的情況下才能很優的解決相同文件塊伺服器只存一份的需求。但是！文件分塊越小，伺服器上存儲的文件元數據的信息越大（每個文件所組成的塊數越多），且下載一個文件所需要的網路請求數也會相應增多（考慮到建立http連接甚至https的連接的消耗），所以這裡有一個平衡。

3.據我所知金山個人快盤的分塊大小是4MB。

現在來回答你的問題：

1.動機很明顯：減少最終伺服器數據的存儲量。數據量越大，效果越明顯。同一個文件塊如果被引用了成千上萬次，那麼節約的存儲空間是巨大的。

2.我是金山並且已經採用了文件分塊傳輸的模型，早起採用的模型的演算法已經說明了，就是文件分塊，單塊算hash，新上傳的文件分塊，然後單塊算hash，伺服器已經有的塊（根據hash值查詢）不再次上傳，直接做引用。

這種模型不需要你所說的兩倍空間（我沒有看到你的改進演算法需要兩倍空間的說明）。順帶一提的是，每塊數據至少在伺服器上有三分冗餘:) 。

3.那肯定受不了，不過這些對用戶都是透明的。其實你想想看，我們提供的服務可以量化的是傳輸速度和時間，不能量化的是穩定性和安全性和易用性等等。用戶回報的價值可以簡單用錢來衡量，那麼你看，用戶付出多少錢，其實不單單是提供的容量所能決定的。

4.dropbox有沒有做多文件交叉差異檢測（假如這個特指你所說的改進後的演算法的話）這個事情我不知道，我肯定的是，dropbox一定做了文件分塊和單塊重用的技術。就算dropbox不做，dropbox的底層存儲亞馬遜的S3也會做的...國內的你距離的這些，都用了和dropbox差不多的技術。順帶一提，TPAN和KPAN合併了已經..

5.附送的消息。EMC平方有一套系統可以動態決定分塊大小，這種就需要伺服器進行運算了。具體了解不多，你有興趣的話，我們一起再細聊。

1. 相似多文件差異分析的動機？

a. 降低成本（存儲和帶寬）；b. 提升用戶體驗（通過傳輸更少的數據，讓用戶感受到更快的傳輸速度）。

2. 實現方案？

問題里提到一個需要兩倍存儲的方案，其實是沒有必要的。那怎麼實現呢？堅果雲的回答回答比較全面了。事實上，基本上傳統存儲領域裡的數據重刪技術應用到了雲存儲，具體原理可以參考這篇文章。（數據去重技術原理分析）

數據重刪技術應用到雲存儲上有一些特別的問題要考慮。a. 服務開銷要增大，這值不值？b. 雲存儲的數據量比較大，支持重刪的存儲方案能不能很好的擴展？c. 雲存儲除了關注吞吐量，也關注響應延時，這跟數據重刪通用應用到的備份領域不同。

貝爾實驗室給出了一個demo方案，可以參考一下http://lib-arxiv-008.serverfarm.cornell.edu/pdf/1508.01182.pdf。

3. Dropbox的方案？

Dropbox一開始是做了跨文件的數據去重的，後來因為side channels的問題取消了。改成了只支持單個文件歷史版本的數據去重。

我同意@Sofring的觀點。其實一般可編輯的文檔除了.txt以外，編碼方式都不是嚴格順序的方式，修改的位置並不能完全映射為文件本身的存儲布局。採用滑動窗口不定長的切分策略也許能夠在理論上提高去重率，但是卻可能導致更多計算負載和元數據管理的問題，後端伺服器架構會為此而變得複雜，文件過於碎片化帶來的代價也很高。

多文件交叉檢測會給後台實現帶來很大的挑戰，尤其是重新組裝文件的時候。

一般而言，差異分析是在客戶端做的。Dropbox和堅果雲都是，他們有個目錄存儲相關信息的。

「很像」這個怎麼衡量？我可以說十萬個文件里都有一部分位元組很像。所有相同格式的文件的文件頭都一樣。到最後可能是省了時間在上傳上，但是費了時間在比對上。你必須對伺服器上所有文件都切塊比對，搬運來很像的那一部分再拼接。這真的能省時間嗎。

另外，米國帶寬可是比中國大很多，上傳時間可以接受，那dropbox就不需要費cpu的時間來運算了。