重複數據刪除

Question

我想將我的所有ms office，pdf，html，xml文件逐步備份到共享網絡。我將以5mb大塊的形式讀取文件，同時我還將對這些數據進行MD5處理，以考慮欺騙因素。我的問題是，上傳後特定的文件被修改，現在我想增量備份更改的數據，如果我考慮相同的塊大小，那麼所有的塊將顯示不同，我需要再次上傳它們。那麼是否有更好的方法來解決重複數據的問題？或者，最好是知道所有指定文件的結構（原始讀取），然後處理重複數據？

感謝和問候， Haseena

Answer 1

您可以檢查了rsync的和它的算法。

否則，您可能不得不做類似datadomain的操作。校驗變量塊的大小，使得數據段可以獨立於給定文件中的偏移而被識別。請在網上搜索以查看他們的專利等。在這裏完成寫作是不可能的。

Answer 2

有許多重複刪除的方法。必須知道文件的內部結構可能是最沒有吸引力的選擇 - 至少對我而言。我們做了類似於你要求的東西，並圍繞它建立了一個產品。

一些觀察;首先，考慮到問題的年代，你可能已經聽夠了，MD5不是你最好的朋友。在這些類型的應用中碰撞的可能性太高。我們選擇了SHA-1，就像很多其他做類似工作的產品一樣。

您認識到數據的簡單「分塊」問題......在文件早期插入的情況下，所有後續塊可能必須重寫。

首先，您可能會意識到，低於一定的大小閾值，這很重要。更改較小文件的IO是您可能會吸收的東西。

但是，對於較大的文件，如果只有一小部分更改，就不必重寫所有數據......並且有很多大的可寫文件，大的靜態數據集中的小改動正是發生。例如，具有內部數據庫結構的文件。

訣竅，如果它可以被視爲一個竅門，是識別靜態數據的範圍。這相當於計算你認識的數據的哈希值。

例如，想象一下計算一個滾動散列，在文件中逐字節地讀取它。如果你的哈希函數是合理分配的，那麼每個新的字節將產生一個散列值，它與前一個字節的貢獻非常相似。

認識哈希只是意味着哈希值是你任意選擇......你已經決定代表定點散列值的某個子集。例如，您可能會識別出所有通過恆定值均勻分配的哈希值。

當您識別散列時，將捕獲文件中該字節的偏移量，並將滾動散列重置爲初始狀態。在文件末尾，您將累積一個偏移量列表。

現在，這些偏移量之間的相對距離將受到散列識別器選擇性的控制。例如，如果您選擇識別hash % 32 == 0，那麼您將在彼此相對較小的相對距離處有很多偏移量。如果你有hash % 65536 == 0，你將會有更少，更寬的偏移量。每個偏移量之間的距離將是可變的...有些會很小，有些會很大。 注意：大塊很可壓縮。

這些偏移量將成爲中斷點...您將存儲從偏移量到偏移量的塊。在存儲塊之前，您將計算該塊的散列（SHA-1散列，而不是正在運行的散列）。如果您已經在存儲中獲得了該塊，則不需要再次存儲它。在您的存儲中，文件成爲塊的列表。塊最初可能來自一個文件，但也會被識別爲發生在其他文件中。重複數據刪除！

您應用於正在運行的散列的選擇性不僅控制塊的大小，而且還控制如何在大文件中捕獲「小改動」。

在這一點上，重要的是要區分運行散列和滾動散列。真正重要的是，當你在文件中滾動時，你計算的是一個關於last n bytes的散列，其中n是滑動框架的寬度。我們是而不是計算從偏移量到偏移量的散列值。我們正在努力尋找我們認識到的n -byte哨兵。

n的大小也很重要。你將會計算一個從0到n-1，然後是1到n，然後是2到n + 1等的散列。如果你仔細想想，n表示將存在的最小塊大小（除了end-這個文件是在一個哨兵之後發生的）。

所以，在這一點上，你必須思考，「Holey，這是很多哈希！」，你是對的;但並不像你想象的那麼糟糕。選擇正確的滾動哈希算法是非常重要的。有一個非常適合這個的算法。我們使用的稱爲Rabin-Karp滾動散列，並使用Rabin fingerprint來發現標記偏移，它的美妙之處在於添加字節的貢獻和刪除字節的貢獻是微不足道的，廉價的算法。

滾動散列很重要的原因（與正在運行的散列相反）是變化檢測。假設在更改之前發生識別的哨兵偏移...，然後在更改後發生另一個可識別的哨兵。只有這兩個偏移之間的塊纔會被存儲。更改前的部分和更改後的部分先前已存儲。