Deduplication（去重，消重）是近年來存儲業界非常熱門的一個技術，無論是Primary Storage，還是備份系統，抑或是雲存儲比如百度迅雷的網盤，都需要考慮dedup來減少備援，降低成本。當然了各種系統對dedup的需求是不一樣的。Primary Storage對性能要求高，特别是IOPS名額，這樣很難實作線上的dedup，往往隻會采用離線的dedup在閑時進行去重。備份系統則是各有千秋，去重備份系統的領頭羊DataDomain是采用榨幹CPU能力的線上dedup，由于有一些獨特的技術，能做到吞吐量每小時數T。而網盤服務中，多使用者可能存在重複檔案，但各使用者的帶寬有限，往往是采用檔案級去重，用戶端在上傳檔案之前就進行檔案hash計算，隻傳輸雲端沒有的新檔案。
Dedup從技術上說，分檔案級去重和塊級去重。檔案級的去重，最原始是對整個檔案做一個hash取得key值，實作簡單，效果一般。如上所述，在多使用者環境中重複檔案很多的條件下，能取得一定的去重效果。但是在實踐中，往往完全相同的檔案還是不多見的。例如網盤中的電影檔案，往往同一個電影同一個檔案，有些使用者擷取檔案時，部分資料不全（往往出現在BT下載下傳中種子沒了的情況下）。這時候檔案還是可以流暢觀看的，但是如果用全檔案級别的hash，一點差異就會導緻完全不同的hash值。而且動辄數G的檔案做全文的hash消耗太大。據我所知，有些網盤服務是在大檔案的某些特定偏移取出特定大小的資料塊，然後算出多個hash值。如果兩個檔案的多個hash值比對，就判斷兩個檔案是相同檔案。
塊級的去重，除了能消除重複的檔案，還能在同一個檔案有部分變化時，隻保留變化部分。而實作塊級的去重，資料如何分塊是關鍵。資料分塊方法分為固定長度分塊和可變長分塊。固定長度分塊實作起來也相當的簡單，但是如果檔案中有小小的新增或者删除改動，會造成舊的分塊失效，從增删資料位置開始，所有的分塊hash值都改變。如圖：
是以，變長分塊才是最終解決之道。變長分塊要達到的目标就是，當資料中有新增或者删除的資料時，變動的資料隻影響周圍1-2個資料塊，隻有這1-2個資料塊的hash值發生改變，而後續更多的資料塊還是按照原來的方式分塊，hash值不變。
這樣一來，可以想到的解決方法是，變長分塊要根據資料内容特征來分塊。如果能根據資料内容的特征來分塊的話，如果發生檔案内容改變，情況會如下圖：
這樣，除了1-2個資料塊以外，其他的資料塊hash值沒有發生變化。但是問題來了，如何找到和定義這些分割點（Anchor）呢？
首先能想到的最粗糙的，就是按資料本身的内容值來找。比如，我們可以搜尋資料流中所有連續4個位元組為0的資料，把這4個位元組，做為如上圖中紅色的分割點。這樣是不是就可以了呢？
理論上，這樣粗糙的分割可以完成變長切分的功能。但是這樣的特征值分布效果不好，一個檔案中很容易出現完全沒有4個連續0的情況，也可能檔案中出現大段的連續0，造成大量無效資料分割點。這種粗糙的分割點造成我們完全無法預測檔案中分割點的分布情況，無法預測最終資料塊的大小。資料塊太大會造成修改後失效率高，資料塊太小會造成讀寫性能低下。
是以，我們對一個好的變長資料切分算法的要求是，通過數學方法能對最終切分的效果有一定的預期。資料塊的大小最好能在我們需要的大小附近正态分布，最終平均大小是我們期望的大小。下面就來介紹一個靠譜的分塊算法，源自一片論文《A Low-bandwidth Network File System》
這個文章介紹的方法簡單來說，就是如果期望分塊大小在8K上下，那麼就算資料流中每一個48位元組的資料塊的hash值（順序計算0-47位元組，1-48位元組，2-49位元組等等等等），然後把hash值對8K取模（xor 0x1fff），最後找出資料流中所有模值的資料塊做為分割點。
論文中做了一些實驗，論證了視窗（分割點資料塊大小）取24位元組或者48位元組影響不大，48位元組結果略好。Hash算法采用rabin hash。最終資料塊大小的分布，中位值是5.8K，平均值非常接近8K。可以說，這是一個相當令人滿意的算法。論文中的算法為了避免出現極端情況（過多或者過少分割點造成過大或者過小資料塊），設定了資料塊的上下限，資料塊最小2K，最大64K。
在實際産品中，這些參數都要根據實際的資料流特征來進行微調。比如某公司産品，資料塊下限4K，上限12K。在計算分割點的hash算法的選擇上，實際産品中為了減輕計算負擔（因為CPU還有大量去重運算），很可能選擇雖然分布效果不好但更輕量級的算法。
變長分塊的奧秘就介紹到這，以後有時間還會介紹Dedup産品其它的關鍵技術點。
(寫這篇文章主要原因是，現有中文文章對變長資料塊的分割介紹的實在太晦澀難懂了!)
鳴謝參考過的博文：
http://qing.blog.sina.com.cn/tj/88ca09aa33000uyo.html Data Dedup技術簡介 EMC研究院
http://mss.sjtu.edu.cn/bencandy.php?fid=14&id=167 上海交大 海量存儲實驗室 重複資料删除綜述
http://blog.csdn.net/liuaigui/article/details/5829083 重複資料删除