TWI472935B

TWI472935B - 漸進式備份之基于片段的高延展的去複本系統與方法

Info

Publication number: TWI472935B
Application number: TW99136372A
Authority: TW
Inventors: Maohua Lu; Tzi Cker Chiueh
Original assignee: Ind Tech Res Inst
Priority date: 2010-07-29
Filing date: 2010-10-25
Publication date: 2015-02-11
Also published as: CN102346695A; US8397080B2; TW201205318A; CN102346695B; US20120030477A1

Description

漸進式備份之基于片段的高延展的去複本系統與方法

本揭露係關於一種漸進式備份(incremental backkups)之基于片段的(segment-based)高延展的(scalable)去複本(de-duplicated)系統與方法。

大部分的資料去複本技術著重於完整備份(full backups)，即使所有邏輯區塊中僅一小部份已經被變更，一邏輯卷宗的所有邏輯區塊會以現存的區塊去複本。

在一種習知的稀疏索引(sparse indexing)方法中，以取樣指紋索引(sampling fingerprint index)來取代完整指紋索引(whole fingerprint index)，將此指紋索引適當地配置於磁碟對磁碟(Disk to Disk，D2D)資料備份系統的隨機存取記憶體(Random Access Memory，RAM)中。取樣指紋索引的洞察是，被複製的資料區塊(duplicated data blocks)會趨向於以非明顯的長度(non-trivial length)儲存在一個連續的範圍裡。在此範圍內之取樣指紋值(sampling fingerprint value)的匹對意指高機率之完整範圍的匹對。在所有被匹對的範圍中，選擇冠軍者作為去複本的對象。稀疏指紋索引方法是依據一固定取樣率來取此指紋的樣本。在另一種習知的方法中，指紋是依據資料片段(segment)之暫時的區域性(temporal locality)來取樣。如果條件符合的話(一時間的週期；一固定計數)，在稀疏區塊索引(sparse chuck index)中的資料片段的元素(entries)會被刪除或裁剪(pruned)。被取樣之指紋的每一元素最多指向R個資料筒(container)。換句話說，此方法利用一最近最少使用的(Least Recently Used，LRU)目錄，來降低資料筒的取樣率。

在另一種習知的方法中，使用布隆過濾器(bloom filter)來決定一指紋是否在指紋索引裡。此布隆過濾器不論這些區塊的歷史為何，盲目地記錄所有區塊的全部指紋。另一種習知的方法是每一檔案有一該檔案的整份雜湊對映(whole-file-hash)，其表示此整份檔案雜湊對映的一個匹對意指此整份檔案是一個副本，此檔案中的個別指紋不用被檢查。此方法是基于檔案來進行去複本。每一檔案具有一代表性的(representative)指紋。指紋索引中的元素依據模數運算(modular operation)或其他分散式的雜湊對映表功能，一個接一個被分散至K個節點(node)。對應於一指紋索引元素的整個資料筒會被分散至與此指紋索元素相同的節點。如果兩個指紋索引元素有相同的資料筒，但是被分散在兩個不同節點，此相同的資料筒就會被複製在兩個節點上。當一個檔案被備份，只有代表性的指紋被用來路由(route)此檔案至一節點，此檔案的其他所有指紋不被用來做路由的目的。

一些習知的美國專利提供去複本的技術。例如，在一習知技術中，資料區塊的數個指紋紀錄依據此指紋值(fingerprint value)的一部分來分散。指紋紀錄具有執行資料去複本的完整資訊。此技術沒有揭示指紋資料筒的概念。在另一習知技術中，採用一種固定前置網路(Fixed Prefix Network，FPN)的修正版本，依一預定的資料冗餘層次(data redundancy level)來分散資料區塊。因為此儲存器是一種內容可定址(content-addressable)之儲存器，此技術沒有揭示指紋索引與資料筒。另一習知技術是依據指紋來分散區塊。第一步驟是依據指紋金鑰之k個最低位元(Least-Significant-Bit)將區塊分割而成數個部分。第二步驟是利用一分散式雜湊表(Distributed Hash Table，DHT)，將此數個部分對映到一實體節點(physical node)。每一資料節點備有一個加密金鑰(encrypted key)的佇列(queue)，以及一個用來搜尋此佇列以發現複本的一個請求(request)。

本揭露的實施範例可提供一種漸進式備份之基于片段的高延展的去複本系統與方法。

在一實施範例中，所揭露者係關於一種漸進式備份之片段式高延展的去複本系統。此系統包含一主裝置(maste device)位於一次級儲存節點端(secondary-storage node side)。此主裝置可接收至少一漸進式更新、去複本多個片段的多個指紋、多個邏輯區塊位址至實體位置之對映的個體，並將去複本功能分散到位於一資料節點端的至少一從屬裝置，並藉由叢集多個在一個資料局部單元(稱為資料筒)的指紋、多個片段的可變取樣率、以及一種避免不必要之輸入與輸出的每一片段彙總結構(per-segment summary structure)，在多個片段上執行資料去複本。

在另一實施範例中，所揭露者係關於一種漸進式備份之基于片段的高延展的去複本方法。此方法包含：對於多個欲被去複本之區塊的多個漸進式更新，叢集多個在一資料局部單元(稱為資料筒)的指紋；分割此多個漸進式更新的多個區塊，以作為多個輸入片段；查詢一內建記憶體(in-memory)取樣的指紋索引，以找出此多個輸入片段的每一指紋，並回傳一對相對應的資料筒與片段；當存在一已儲存的片段與此輸入片段是相同時，則以此對相對應的資料筒與片段來查詢一內建記憶體片段式彙總(segment-based summary)，以決定是否擷取此對相對應的資料筒與片段，否則，查詢一內建記憶體資料筒儲存快取記憶體(cache)，來決定是否快取此相對應的資料筒；當沒有快取此資料筒時，自一碟片(on-disk)資料筒儲存元件，載入此相對應的資料筒，並查詢一每一資料筒片段索引(per-container segment index)，以找出路由至此相對應之資料筒的一特定指紋的一偏移量(offset)，以取得(retrieve)此特定指紋的片段資訊。

茲配合下列圖示、實施範例之詳細說明及申請專利範圍，將上述及本揭露之其他特徵與優點詳述於後。

當一主要的儲存系統漸進地追蹤更新的區塊，並且只有備份這些漸進更新的區塊(incremental changed blocks)時，本揭露的實施範例可提供一種漸進式備份之片段式高延展的去複本系統與方法。具體地說，假設此主要的儲存系統從最新的快照(漸進式更新追蹤)的一快照圖像來追蹤更新的區塊，並且只有更新的區塊被當作是此備份儲存系統的輸入。

本揭露之實施範例將焦點放在以片段為基礎的四個方面，以影響資料去複本比例(data de-duplication ratio，DDR)為盡量最小的方式，來改善去複本的資料傳輸量(throughput)：(1)叢集多個在一個資料局部單元(稱為資料筒)的指紋；(2)多個片段的可變取樣率，穩定且泛用的(popular)片段具有一固定的取樣率，而去複本之“非泛用的(unpopular)”目標檔則指定較低的取樣率；(3)在去複本時，避免不必要之輸入與輸出的每一片段彙總結構；(4)分散式的去複本，來平均多個參與儲存節點的運算能力。

就第一個方面來說，資料筒是依去複本的歷史紀錄來建構，而非依純邏輯位址接近度(pure logical address proximity)來建構。對於輸入的漸進式更新，資料局部性的語義是更難以捉摸的，因為很難預測在此漸進式更新串流(incremental changes stream)中會出現什麼情況。在本實施範例中，互相分享內容之所有漸進式的更新都會被放入同一個資料筒，以擷取被同組應用而更新之資料的局部性。

就第二個方面來說，將指紋設置在一隨機存取記憶體(RAM)，片段的取樣率是用下列方式來區分的，亦即穩定片段具有一固定的取樣率，而去複本之不穩定的目標檔則指定隨時間變化的取樣率。一個穩定片段的定義是沒有改變去複本歷史紀錄的一片段。此穩定片段直覺上是主機傾向分享大於一區塊的一物件。藉由觀察資料去複本的歷史紀錄，可指出此穩定片段，並且可使用在此穩定片段中的一個指紋來代表在指紋索引中的片段。例如，可採用一種最近最少使用的策略來變化在被取樣的指紋索引中所有非泛用之片段的取樣率。

就第三個方面來說，可以將每一片段彙總結構平均化，以避免去複本的不必要輸入與輸出。對於較大容量且幾乎很少改變的片段，不需要一個接一個的比較一片段中的個別指紋，因此可減少從磁碟中擷取個別指紋之磁碟輸入/輸出(disk I/O)。每一片段彙總結構可依下列原則來形成：(1)大於一門檻值(threshold)的片段具有一整體片段指紋，以及(2)整體片段指紋匹對時，表示在此片段中，不需個別得檢查區塊指紋。相關片段的整體片段指紋可以構成一Merkle樹(tree)。

就第四個方面來說，本揭露之實施範例在分散式儲存系統中，可將此去複本功能分散至多個參與儲存節點。依據此指紋的一致性雜湊(consistent hashing)方法，將指紋索引與資料筒分散及分開至多個參與儲存節點(participating storage node)。並且，依據彙總(root summary)的一致性雜湊方法，所有彙總結構也被分散及分開至多個參與儲存節點。

現在，本揭露之實施範例的漸進式備份之基于片段的高延展系統可用Hadoop分散式檔案系統(Hadoop Distributed File System，HDFS)來實現，作為基本的儲存器(underlying storage)。然而，本揭露之實施範例是可與任何備有多個資料節點之分散式儲存系統來共同運作的。在下列討論中，假設Hadoop分散式檔案系統為基礎的儲存器階層(underlying storage layer)。本揭露之實施範例可與一次級儲存系統共同運作。此漸進式備份之基于片段的高延展系統可包含一元件並位於次級伺服器端，來分散此去複本的工作量(workload)；還可包括一第二元件並位於資料節點端，來對傳送至特定資料節點之資料區塊去執行去複本。

在探討去複本的細節之前，第一圖是在一漸進式備份之基于片段的高延展之系統裡的一個高階資料流(high-level data flow)的範例示意圖，並與本揭露之某些實施範例一致。第一圖省略漸進式備份之基于片段的高延展系統中的平行部份，此部分將在後面陳述。

參考第一圖，首先，將數個漸進更新分割成數個片段。每一片段藉由發出(issue)片段內之每一個別指紋的指紋查詢(fingerprint query)，來查詢一內建記憶體取樣指紋索引(Sampled Fingerprint Index，SFI)快取記憶體110。每一個別指紋的查詢則傳回一對的<資料筒識別碼，片段識別碼>。在同一片段內指紋的查詢會被聚成一群，以找出是否一已儲存的片段相同於一輸入片段。是的話，此輸入片段以此對<資料筒識別碼，片段識別碼>來查詢一內建記憶體片段式彙總120，以決定是否需要擷取此資料筒。否則，以此資料筒辨識碼來查詢一內建記憶體資料筒儲存快取記憶體130，以查看此資料筒是否被快取，如果沒有被快取的話，則自一磁碟資料筒儲存設備141載入此資料筒。

載入此資料筒後，每一輸入片段在此資料筒中查詢一每一資料筒片段索引(per-container segment index)，以找出路由至此資料筒的一指紋的偏移量(offset)。此偏移量可以用來取得此區塊的實體位置，因為指紋以一陣列(array)方式儲存在此資料筒內。藉由此偏移量查詢此片段索引可以取得特定指紋的片段資訊。磁碟指紋索引143包括從取樣指紋索引釋出的指紋。磁碟指紋索引143沒有包括所有資料筒的全部指紋。

如果有去複本的話，資料流的輸出是此輸入片段裡邏輯區塊位址(logical block address)的實體位置(physical location)。具體來說，產生的邏輯至實體的一更新目錄(L2P-CL)是當做輸出。

在基于片段的高延展之去複本系統中，片段是一基本單元，並且可由目前輸入(current input)與輸入的歷史紀錄(input history)來決定。具體來說，如果數個區塊在漸進中是相鄰的話，則這些區塊屬於相同的輸入片段。然後，此輸入片段與已儲存的片段(stored segment)做比較，以形成儲存片段(store segment)。當輸入片段與儲存片段互相衝突時，每一指紋最多可屬於K個片段。如果一指紋超過K個片段時，K≧2，則從此指紋中移除最舊的片段。

第二圖是一範例示意圖，說明當K=2時，如何進行片段儲存，並與本揭露之某些實施範例一致。參考第二圖，在輸入片段中的號碼代表邏輯區塊號碼，而在儲存片段中的號碼代表在一資料筒的指紋偏移量。如輸入-1，有片段a與片段b共兩個輸入片段。去複本之後，發現片段a是儲存片段1的一個複本，但是發現輸入片段b橫跨兩個儲存片段(儲存片段2與儲存片段3)。儲存片段1與輸入片段a是相同的，所以儲存片段1是沒有更新。反之，具有偏移量從52至55的指紋對映至儲存片段2與輸入片段，共對應至兩個片段。輸入片段c匹對於指紋51至55。因為K=2，亦即每一指紋指允許屬於兩個片段，對於指紋52至55，則移除儲存片段2(即最舊的片段)。替代的是，將指紋52至55對映至兩個片段，亦即輸入片段b與輸入片段c。

事實上，本揭露之實施範例允許每一區塊，最多為K個片段，例如保持追蹤曾經與一區塊相關的最後K個片段。本揭露的實施範例中，使用一區間樹(interval tree)來保持追蹤邏輯區塊位址範圍對映至此片段。下列敘述中，此區間樹稱為片段索引(segment index，SI)。

一基本分享單元(Basic sharing unit，BSU)被定義為產生之後就不會被變更的一儲存片段。在基本分享單元禮的所有指紋一次全部都出現，所以一個指紋就足以代表此相對應的基本分享單元。

因為一指紋索引無法配置在(fit into)隨機存取記憶體中，本揭露之實施範例提出取樣指紋(sampling fingerprint)的概念，將指紋索引配置在一指紋索引快取記憶體中。此取樣是依個別片段(individual segment)為基礎。此指紋索引快取記憶體可被實現為，例如一雜湊表(hash table)。指紋索引快取記憶體的每一元素(entry)是以一指紋值(fingerprint value)為鍵值，並且此元素包括一資料筒辨識碼。甚且，如果多個資料筒分享相同一指紋的話，此資料筒辨識碼最多可指向至K(如K=2)個片段辨識碼。注意的是，此K是與前述的K相同的。

在本揭露之實施範例中，有兩種改變此片段取樣的方式：(1)片段為基本分享單元的話，取出來自於一基本分享單元所有指紋的第一指紋，來代表此基本分享單元。注意的是，此取樣不會損害去複本率，因為在一基本分享單元裡的指紋總是一次全部都出現。然而，因為節省記憶體的空間，所以可以改善此去複本的資料傳輸流量。(2)當記憶體的空間不足時，非但沒有減少所有片段的取樣率，而是對這些長時間未被參照的片段，當取樣率達到一個最小值時，在被他們被釋出前，先減少它們的取樣率。一種最近最少使用的目錄(LRU list)可用在這個用途。特別是，基本分享單元片段具有以最近最少使用順序為基礎的一個虛擬取樣率(virtual sampling)。當基本分享單元到達此最近最少使用目錄的尾端時，會減少此虛擬取樣率。

資料筒的含意是以群聚有資料局部性的指紋，來攤提載入一資料筒之輸入/輸出的成本。對於漸進式備份，此資料局部性是不同於整體備份。本揭露之實施範例的漸進式備份之片段式高延展系統是依據去複本歷史紀錄來關連多個片段。一開始，藉由結合邏輯卷宗辨識碼與邏輯區塊位址，來自不同的邏輯卷宗的邏輯區塊位址包含一個統一的假擬(unified pseudo)邏輯區塊位址。例如，對於在邏輯卷宗1的邏輯區塊位址500，此假擬邏輯區塊位址是(1，500)。每一資料筒起始時可以是半滿的(half full)，以容納此資料筒未來的更新。由於此去複本歷史紀錄隨著時間累積，與一儲存片段分享至少一單依指紋的那些片段會被放入與此儲存片段相同的資料筒。

第三圖是一範例示意圖，說明一資料筒的內容，並與本揭露之某些實施範例一致。在第三圖的範例中，資料筒300的內容可包括一每一資料筒指紋索引310、邏輯區塊位址的K對實體位置和儲存片段330的資訊、以及一彙總結構340。每一資料筒指紋索引310將同一資料筒的指紋安排於一雜湊表中，來加速尋找此資料筒裡的指紋值。每一指紋指向最後的K(例如K=2)片段。直覺的理解是(1)如果有任何基本分享的話，此最後的K片段在日後最有可能成為此基本分享單元，以及(2)兩個片段是極不可能意外地分享一些相互連結的指紋，而非分享一整體片段。注意的是，此K是與前述的K相同的。

當一資料筒需要被分割時，保留一個最近最少使用的目錄給資料筒300，如此資料筒300會依據存取歷史(access history)而被分割。每一最近最少使用目錄是以時間戳記(timestamp)為鍵值，並且包含做為內容的指紋值。

如前所述，在一資料筒內片段之間的關係可以分成兩種類型。第一類型是在相同假擬邏輯區塊位址範圍內的兩片段；第二類型是分享指紋的兩個片段。如果沒有提供彙總資訊的話，此兩片段的指紋則依一最近最少使用目錄的順序被置放於此資料筒中。因為會將每一片段彙總結構包括在內，所以，需要區別此兩種類型。

對於第一種類型的片段，每一片段不會再進一步處理，而是直接留在此資料筒中。對於第二種類型的片段，因為每一指紋最多可以指向K(如K=2)個片段，片段根據歷史可能需要被分割。如果一指紋指向超過K個片段，結果導致片段之間分享指紋，則在加入一新片段之前，會移除最舊的片段。

所有的每一片段結構會被輸入至彙總結構340。在彙總結構340裡的每一元素是以一片段索引341為鍵值，並且其內容是由相對應片段的彙總指紋(Summary Fingerprint，SF)342所組成的。注意的是，並非所有片段都備有一彙總指紋342，只有較大容量(例如大於1000)的那些片段備有一彙總指紋，如此所有彙總結構得以配置在隨機存取記憶體中。

一資料筒可以依據一假擬實體區塊位址，但，既不是邏輯區塊位址，也不是真正的實體區塊範圍。假擬實體區塊位址保存了在每一卷宗邏輯區塊位址裡的局部性，並且也可區別於其他卷宗的區塊位址。例如，卷宗A與卷宗B分別具有邏輯區塊範圍(0，32M)與(0，16M)。此假擬實體區塊範圍對卷宗A而言可以是(0，32M)，而假擬實體區塊範圍對卷宗B而言可以是(32M，48M)。一資料筒可以依據兩個片段的內容為基礎。分享至少一指紋的兩個片段可被置放於一資料筒內。並且，一資料筒保存指紋索引元素裡的局部性。也就是說，此資料筒是一個範圍與內容式且保留指紋局部性的資料筒(range and content-based locality-preserved fingerprint)。

如上述，一個大於一門檻N的片段有一彙總指紋(summary index)。此彙總指紋可藉由以N個指紋為資料內容以及算出此內容的一個指紋來算出。也就是說，此彙總指紋是以片段式的。並且，一彙總指紋的特性也是，N個指紋中的一個指紋的改變可以戲劇性地改變此彙總指紋。結果，如果兩個片段的彙總指紋相互匹對的話，此兩個片段是不同的機率會小到只存在於理論中。換句話說，如果彙總指紋匹對的話，則此兩個片段是完全相同的(identical)。

片段式彙總索引可藉由合適的選擇N，而配置在一記憶體中，例如隨機存取記憶體。每一索引元素以一對<資料筒辨識碼，片段辨識碼>做為鍵值。內容可包括彙總指紋、片段長度、以及包括此片段之實體區塊。此實體區塊也同樣是被儲存的，因為如果彙總指紋匹對的話，則不需要快取此資料筒，並且這些實體區塊作為資料去複本時的目標實體區塊。如上述，向指紋索引快取記憶體查詢一資料筒之後，取得一資料筒辨識碼以及最多K個片段辨識碼。查詢結果產生的<資料筒辨識碼，片段辨識碼>對被用來查詢片段式彙總索引，以找出相對應之片段，此產生的片段之彙總指紋與一儲存片段的彙總指紋做比較。為了減少因片段式彙總索引的記憶體消耗量，並非所有在此片段裡的實體區塊都是個別地被儲存。而是儲存此實體區塊範圍來減少此記憶體的消耗量。

藉由組合片段識別、可變的取樣率、以及使用片段式彙總結構，第四圖是一漸進式備份之片段式高延展之去複本系統的一個架構範例示意圖，並與本揭露之某些實施範例一致。參考第四圖，片段式高延展之去複本系統400可包含一主裝置410，位於一次級儲存節點端。主裝置410可接收多個輸入，例如多個區塊之漸進更新412、去複本之多個片段的指紋414、多個邏輯區塊位址至實體位置之對映的個體416等，並且還包括至少一分散器(distributor)，來將至少一去複本功能分散給至少一從屬裝置(slave device)，如從屬裝置1至從屬裝置n，並藉由叢集多個在一個資料局部單元(稱為資料筒)的指紋、多個片段的可變取樣率、以及一種避免不必要之輸入與輸出的每一片段彙總結構，在多個片段上執行資料去複本，其中，穩定片段具有一固定的取樣率，而去複本之不穩定的目標檔則指定隨時間變化的取樣率。系統400還可包括至少一從屬裝置420，位於資料節點端，並執行平行式去複本，以利用位於此資料節點端之從屬裝置的運算能力。

第五圖是片段式高延展之去複本系統的分散式去複本架構的一個範例示意圖，並與本揭露之某些實施範例一致。參考第五圖，在次級儲存節點端，主裝置410可包括一指紋分散器(fingerprint distributor)501與一資料筒分散器(container distributor)502。指紋分散器501可雜湊每一個別指紋，來決定一目的地資料節點(destination data node)，並可等待此資料節點的回應。此回應可以是被一邏輯區塊位址所指到的一目標實體區塊(target physical block)。此回應有三個考量的情況。

第一個情況是，在一指紋索引快取記憶體中找到此指紋，並且此資料筒在一資料筒快取記體中已被快取或是在此片段式彙總索引找到。在此情況下，此回應可包括一目標區塊(去複本區塊)的資訊。對應此目標區塊的原始區塊可被做回收(disposed)。

第二個情況是，在一指紋索引快取記憶體中找到此指紋，但是此資料筒在一資料筒快取記體中沒有被快取，並且此片段式彙總索引沒有匹對。此資料筒被載入至一次級儲存節點端的一隨機存取記憶體中。使用與資料統分散器502分散指紋時相同的雜湊函數(hash function)，將此資料筒中的元素分散至相關的資料節點。位於一特定資料節點的相同資料筒的元素被組成一子資料筒(sub-container)。

注意的是，資料筒分散器502沒有直接寫入資料筒。而是資料筒分散器502給位於此資料節點的每一子資料筒一個公用的檔案名稱(public file name)，如此，可同時取得屬於相同資料筒的子資料筒。例如說，如果一資料筒有一識別碼(identifier) 0x01234，四個子資料筒分別被命名為0x01234.ip1、0x01234.ip2、0x01234.ip3、以及0x01234.ip4。當資料筒分散器502取得資料筒0x01234時，也向每一個別資料節點要求相對應之子資料筒。每一資料節點輪流讀取子資料筒0x01234.ipI，ipI是特定資料節點的IP位址。在資料節點寫入子資料筒的優點是在存取時，每一子資料筒備有一本地複本(local copy)，且此資料節點可藉由它的本地磁碟，而不是透過網路取自其它資料節點，取得子資料筒。藉由查詢每一資料筒指紋索引，可以擷取對應此被查詢指紋的元素，以取得此目標實體區塊。

第三個情況是，在一指紋索引快取記憶體中沒有找到指紋。此指紋已被更新至一對應的資料筒。此原始實體區塊則作為此目標實體區塊。

資料筒分散器502可使用習知的一致性雜湊法加條紋(stripe)於一概念的資料筒，並當作數個子檔案，如此，資料筒條紋、指紋快取記憶體、以及資料筒快取記憶體可常駐於同一個資料節點。依據彙總指紋之相同且一致的雜湊法，資料筒分散器502也負責去分散此片段彙總。

主裝置410還可包括一替代引擎(replacement engine)503來儲存指紋快取記憶體與資料筒快取記體之最近最少使用目錄，以取代位於中心之主裝置410的資料筒與指紋。注意的是，指紋快取記憶體之此最近最少使用目錄是依據資料筒，而不是個別的指紋。

主裝置410還可包括一單元偵測器(unit detector)504來偵測運作中(on the fly)的輸入指紋的資料筒或是辨別長久累積之一去複本單元的邊界。偵測此輸入指紋的資料筒可如下進行。對於每一輸入片段，起初沒有相對應於此輸入片段的資料筒。如果此去複本的回應指出此輸入片段屬於一資料筒，則此資料筒是對應此輸入片段的資料筒。否則，產生一個新資料筒來容納此輸入片段。一資料筒具有其大小(size)的上限。

辨別長久累積之一去複本單元的邊界的進行如下說明。起初將每一輸入片段視為一去複本單元(de-duplication unit)。此輸入片段儲存在一資料筒。具體來說，每一子資料筒儲存實體區塊，也儲存與這些實體區塊相關的此輸入片段。下一次，此片段被查詢時，以儲存片段來檢查此輸入片段。如果是同一片段，則此片段可能在將來還是一樣的片段。如果一片段經過一預定數目的去複本查詢後，仍是維持同一個片段，則此片段被視為穩定，並且在此單元裡的第一指紋可被挑出並做為被取樣的指紋，如同上述。

主裝置410還可包括一對映更新器(mapping updater)505，依據此去複本的輸出來更新對映到此卷宗的元數據(metadata)。

在資料節點端，至少一從屬裝置的每一從屬裝置還可包括一指紋管理器(fingerprint manager)511，來維持此指紋快取記憶體，除了替換指紋之外。指紋的替換是由位於主裝置410的替換引擎(replacement engine)503來協調。多個指紋被安排成一雜湊表。每一指紋元素備有一資料筒辨別碼目錄(container identifier list)。此目錄最多有K個元素、此資料筒內的指紋的偏移量、以及指向此相同資料筒的指紋的一指標(pointer)。以此指標，在相同資料筒中的所有指紋被組織成為一單一連結目錄(linked list)。此連結目錄的前端是此資料筒的第一個被取樣的指紋。

在替換引擎503中，指紋索引之最近最少使用目錄的每一元素包括相對應的資料筒之第一個被取樣的指紋的指紋值，以及此資料筒的辨別碼。而此資料筒快取記憶體之最近最少使用目錄的每一元素備有此資料筒辨別碼。當一資料筒的指紋從指紋索引被釋出時，這些元素被寫至一磁碟，作為此指紋索引的一永久複本(persistent copy)。

每一從屬裝置也可包括一資料筒管理器(container manager)512來維持此資料筒快取記憶體，除了資料筒的替換之外。資料筒管理器512可具備三個部份，亦即資料筒快取記憶體、資料筒格式、以及資料筒讀取。對於此資料筒快取記憶體，其資料筒是以唯一的資料筒識別碼作為鍵值，而組織成一雜湊表，此與前述之資料筒快取記憶體相同。此資料筒格式是與前述之資料筒及第三圖相同的。關於讀取資料筒，它以資料筒辨識碼加上IP當做檔案名稱來讀取基本檔案系統的子資料筒。每一從屬裝置也可包括一資料筒更新器513，以供在此本地資料節點上寫入子資料筒。為了加速寫入速度，其更新是序列式地被寫入至磁碟。

因為資料筒被分散在所有參與節點上，儲存片段的資訊不是儲存在單一的節點。而是將一片段內之偏移量儲存在參與節點上。從參與節點上收集一片段的偏移量與片段辨識碼後，則可重建此儲存片段的資訊。第六圖是一範例示意圖，說明如何從兩個參與節點去重建一片段，並與本揭露之某些實施範例一致。此去複本是與第二圖相同的。片段1、2、3都是屬於同的資料筒。加括號的(parenthesized)對(n,k)代表在第n個片段的第k個實體區塊。例如，對(2,3)代表在第2個片段中的第3個實體區塊。在本範例中，片段1、2、3平均地被分散至兩個儲存節點，如節點601與節點602。在查詢此每一資料筒指紋索引之後，相對應之從屬裝置回覆偏移量與片段辨識碼。在主裝置中重建片段1、2、3之被匹對的部份。例如，來自節點601之對(1,0)與對(1,2)屬於片段1，來自節點602之對(1,1)與對(1,3)也是屬於片段1。並且整個片段1也被重建，其中第0個與第2個區塊來自節點601，而第1個與第3個區塊來自節點602，則可重建整個片段1。然後，第二圖所述之片段辨識碼方案可繼續進行。

請參考第七圖，第七圖是一範例示意圖，說明片段式高延展之去複本系統運作流程，並與本揭露之某些實施範例一致。在第七圖中，範例運作流程700可包含：對於多個欲被去複本之區塊的多個漸進式更新，叢集多個在一資料局部單元(稱為資料筒)的指紋，如步驟710所示。分割此多個漸進式更新的多個區塊，以作為多個輸入片段，如步驟720所示。查詢一內建記憶體取樣的指紋索引，例如內建記憶體取樣的指紋索引110，以找出此多個輸入片段的每一指紋，並回傳一對相對應的資料筒與片段，例如<資料筒辨識碼，片段辨識碼>，如步驟730所示。當存在一儲存片段與此輸入片段是相同時，則以此對相對應的資料筒與片段來查詢一內建記憶體片段式彙總，例如內建記憶體片段式彙總120，以決定是否擷取此對相對應的資料筒與片段，否則，查詢一內建記憶體資料筒儲存快取記憶體，例如內建記憶體資料筒儲存快取記憶體130，來決定是否快取此相對應的資料筒，如步驟740所示。當沒有快取此資料筒時，自一碟片資料筒儲存元件，載入此相對應的資料筒，並查詢一每一資料筒片段索引，以找出路由至此相對應之資料筒的一特定指紋的一偏移量，以取得此特定指紋的片段資訊，如步驟750所示。如果有去複本的話，資料流的輸出是此輸入片段裡邏輯區塊位址的實體位置。

步驟710還可包括，例如，輸入一更新目錄、輸入此更新目錄中多個區塊之多個邏輯至實體對應元素、計算出在此更新目錄中多個區塊的指紋、藉由去複本的歷史紀錄為基礎來重建資料筒，以擷取起因於同組應用上的改變的資料局部性等。當此輸入片段大於一門檻T時，步驟730還可包括，例如，計算出此輸入片段之彙總指紋索引、搜尋一指紋索引、找出實體區塊之一快取記憶體、取得實體區塊附加至此更新目錄等。當一被匹對的儲存片段是大於此門檻時，步驟740還可包括，例如，計算出此儲存片段之彙總指紋、並更新彙總索引、檢查此儲存片段的一偏移量對(offset pair)、移除此片段索引中最舊的片段(每一指紋元素可包括一資料筒辨識碼目錄，最多指向K個元素)、對此資料筒更新新指紋、附加邏輯至實體目錄至更新目錄中，等等。此資料筒被快取後，片段快取記憶體會被更新。步驟750還可包括，例如，當找到一滿的(full)資料筒時，產生一個新資料筒，附加此輸入片段至新產生的資料筒，以一序列方是來將資料筒紀錄至磁碟等。這些詳細運作之子步驟在第八圖之工作範例中可以找到。第八圖是第七圖之詳細運作的一個工作範例，並與本揭露之某些實施範例一致。此處省略已經提述之其它子步驟的細節。

如前述，漸進式備份之片段式高延展之系統400可與一次級儲存系統一起運作，片段式高延展之去複本系統400有兩種裝置。一種是在次級儲存裝置端上，來分散去複本的工作量；另一種裝置是在資料節點端上，以將傳送至特定資料節點之資料區塊去複本。指紋資料可用一種分散的方式，來儲存及取得於次級儲存節點端的一次級儲存伺服器，並且此指紋快取記憶體與資料筒快取記憶體也可分散及分割至不同的資料節點上。藉由一致的雜湊法來分割資料筒、指紋、快取記憶體、以及資料筒快取記憶體。

第九圖是一範例示意圖，說明平行式去複本的運作流程，並與本揭露之某些實施範例一致。參考第九圖，範例運作流程900可包含：利用一加密的雜湊法(cryptographic hashing)來計算出多個漸進更新區塊的指紋(步驟910)；依一致的雜湊法將此多個指紋分散，並儲存於一取樣指紋索引快取記體與數個子資料筒(步驟920)；依一致的雜湊法，將每一資料筒片段索引分散到至少一參與節點(步驟930)，如此，在每一資料節點(從屬裝置)上的片段索引可具有較小偏移量對；並且依一致的雜湊法，將每一片段彙總結構分散到至少一參與節點(步驟940)。此至少一參與節點在一資料節點端上可以是不同資料節點。此一致的雜湊法為熟知的一致的雜湊法。

步驟910還可包括，例如，集合多個在更新目錄中的漸進更新區塊作為一輸入片段目錄，此至少一參與節點可在此取樣指紋索引快取記憶體中查詢此指紋等。在平行式去複本的期間，資料筒快取記憶體的載入與釋出也需要此至少一參與節點的協助。第十圖是第九圖之詳細運作的一個工作範例，並與本揭露之某些實施範例一致。此處省略已經提述之其它子步驟的細節。

綜合上述，本揭露的實施範例可提供一種漸進式備份之基于片段的高延展之去複本系統與方法，可經由資料筒之漸進更新的每一片段彙總指紋、多變的片段取樣率、每一片段彙總結構、以及分散去複本至多各參與節點，並以影響資料去複本比例為盡量最小的方式，來改善去複本的資料傳輸量。

惟，以上所述者，僅為本揭露之實施範例而已，當不能依此限定本揭露實施之範圍。即大凡一本揭露申請專利範圍所作之均等變化與修飾，皆應仍屬本揭露專利涵蓋之範圍內。

110．．．內建記憶體取樣指紋索引快取記憶體

120．．．內建記憶體片段式彙總

130．．．內建記憶體資料筒儲存快取記憶體

141．．．磁碟資料筒儲存設備

143．．．磁碟指紋索引

300．．．資料筒

310．．．每一資料筒指紋索引

320．．．最近最少使用目錄

330．．．儲存片段

340．．．彙總結構

341．．．片段索引

342．．．彙總指紋

400．．．片段式高延展之去複本系統

410．．．主裝置

412．．．多個區塊之漸進更新

414．．．去複本之多個片段的指紋

416．．．多個邏輯區塊位址至實體位置之對映的個體

501．．．指紋分散器

502．．．資料筒分散器

503．．．替換引擎

504．．．單元偵測器

505．．．對映更新器

511．．．指紋管理器

512．．．資料筒管理器

513．．．資料筒更新器

601．．．節點

602．．．節點

710．．．對於多個欲被去複本之區塊的多個漸進式更新，叢集多個在一資料局部單元(稱為資料筒)的指紋

720．．．分割此多個漸進式更新的多個區塊，以作為多個輸入片段

730．．．查詢一內建記憶體取樣的指紋索引，以找出此多個輸入片段的每一指紋，並回傳一對相對應的資料筒與片段

740．．．當存在一已儲存的片段與此輸入片段是相同時，則以此對相對應的資料筒與片段來查詢一內建記憶體片段式彙總，以決定是否擷取此對相對應的資料筒與片段，否則，查詢一內建記憶體資料筒儲存快取記憶體，來決定是否快取此相對應的資料筒

750．．．當沒有快取此資料筒時，自一碟片資料筒儲存元件，載入此相對應的資料筒，並查詢一每一資料筒片段索引，以找出路由至此相對應之資料筒的一特定指紋的一偏移量，以取得此特定指紋的片段資訊

910．．．利用一加密的雜湊法來計算出多個漸進更新區塊的指紋

920．．．依一致的雜湊法將此多個指紋分散，並儲存於一取樣指紋索引快取記體與子資料筒

930．．．依一致的雜湊法將每一資料筒片段索引分散到至少一參與節點

940．．．依一致的雜湊法將每一片段彙總結構分散到至少一參與節點

第一圖是在一漸進式備份之基于片段的高延展之系統裡的一個高階資料流的範例示意圖，並與本揭露之某些實施範例一致。

第二圖是一範例示意圖，說明當K=2時，如何進行片段儲存，並與本揭露之某些實施範例一致。

第三圖是一範例示意圖，說明一資料筒的內容，並與本揭露之某些實施範例一致。

第四圖是一漸進式備份之基于片段的高延展之去複本系統的一個架構範例示意圖，並與本揭露之某些實施範例一致。

第五圖是片段的高延展之去複本系統的分散式去複本架構的一個範例示意圖，並與本揭露之某些實施範例一致。

第六圖是一範例示意圖，說明如何從兩個參與節點去重建一片段，並與本揭露之某些實施範例一致。

第七圖是一範例示意圖，說明片段的高延展之去複本系統的運作流程，並與本揭露之某些實施範例一致。

第八圖是第七圖之詳細運作的一個工作範例，並與本揭露之某些實施範例一致。

第九圖是一範例示意圖，說明平行式去複本的運作流程，並與本揭露之某些實施範例一致。

第十圖是第九圖之詳細運作的一個工作範例，並與本揭露之某些實施範例一致。

400．．．基于片段的高延展之去複本系統

410．．．主裝置

412．．．多個區塊之漸進更新

414．．．去複本之多個片段的指紋

416．．．多個邏輯區塊位址至實體位置之對映的個體

Claims

一種漸進式備份之基于片段的高延展的去複本系統，該系統包含：一主裝置，位於一次級儲存節點端，該主裝置可接收至少一漸進式更新、去複本之多個片段的多個指紋、多個邏輯區塊位址至實體區塊之對映的個體；其中該主裝置還包括至少一分散器，將去複本功能分散到位於一資料節點端的至少一從屬裝置，並藉由叢集多個在一個資料局部單元的指紋、該多個片段的可變取樣率、以及一種避免執行去複本時不必要之輸入與輸出的每一片段彙總結構，在該多個片段上執行資料去複本，其中該資料局部單元稱為資料筒；其中該可變取樣率是以一種最近最少使用順序為基礎。
如申請專利範圍第1項所述之去複本系統，其中該至少一分散器還包括：一指紋分散器，雜湊該多個指紋的每一指紋，來決定一目的地資料節點，並等待該資料節點的一回應；以及一資料筒分散器，使用一種一致性雜湊法以分割一概念資料筒，並當作數個子資料筒，如此，一資料筒條紋、一指紋快取記憶體、以及一資料筒快取記憶體常皆駐於同一個資料節點。
如申請專利範圍第1項所述之去複本系統，其中該系統還包括該至少一從屬裝置，並執行平行式去複本，以利用位於該資料節點端之該至少一從屬裝置的計算能力。
如申請專利範圍第3項所述之去複本系統，其中該至少一從屬裝置的每一從屬裝置還包括：一指紋管理器，以維持一指紋快取記憶體，除了替換指紋之外；以及一資料筒管理器，以維持一資料筒快取記憶體，除了替換資料筒之外。
如申請專利範圍第1項所述之去複本系統，叢集該多個指紋的資料筒稱為指紋資料筒，其中多個指紋資料筒以一種分散方式被儲存且從該次級儲存節點被取得，並且一指紋快取記憶體與一資料筒快取記憶體也在不同的資料節點上被分散與分割。
如申請專利範圍第1項所述之去複本系統，其中該資料筒是以多個假擬實體區塊位址為基礎，來保存每一卷宗邏輯區塊位址裡的局部性，並且區別於其他卷宗的區塊位址。
如申請專利範圍第1項所述之去複本系統，其中該每一片段彙總結構係由下列來達成：該多個片段中，大於一門檻值的每一片段具有一整體-片段指紋；以及該整體-片段指紋被匹對時，表示已完成在該片段中的去複本，並且不需要個別的檢查區塊指紋。
如申請專利範圍第1項所述之去複本系統，其中該漸進式更新之資料筒是一種範圍與內容式且保留指紋局部性的資料筒。
如申請專利範圍第3項所述之去複本系統，其中該平行式去複本為片段式去複本，並且是依據一種一致性雜湊法，將輸入片段的每一指紋對映至該資料節點端上的一資料節點。
如申請專利範圍第2項所述之去複本系統，其中該概念資料筒分割為N個檔案，N為該資料節點端之資料節點的數目，N個資料節點的每一節點負責儲存該概念資料筒的一條紋，並且將該概念資料筒的一條紋當作一子資料筒。
如申請專利範圍第2項所述之去複本系統，其中該主裝置還包括一替換引擎，來儲存該指紋快取記憶體與該資料筒快取記憶體之至少一最近最少使用目錄，以取代位於中心之該主裝置的資料筒與指紋。
如申請專利範圍第2項所述之去複本系統，其中該主裝置還包括一對映更新器，依據該去複本的輸出，將邏輯區塊位址之至少一元數據對映到多個區塊之實體位置。
如申請專利範圍第2項所述之去複本系統，其中該主裝置還包括一單元偵測器，偵測運作中的輸入指紋的該概念資料筒或是根據過往歷史辨別一去複本單元的邊界。
如申請專利範圍第4項所述之去複本系統，其中該至少一從屬裝置的每一從屬裝置還包括一資料筒更新器，用於在一本地資料節點之寫入多個子資料筒。
一種漸進式備份之片段式高延展的去複本方法，藉由在一次級儲存節點端的一主裝置來執行，該方法包含：接收至少一漸進式更新、欲被去複本之多個輸入片段的多個指紋、及從邏輯區塊位址至實體區塊之多個對映的個體；叢集多個在一個資料局部單元的指紋，該資料局部單元稱為資料筒；指定該多個輸入片段的可變取樣率；以及重建一每一片段彙總結構，以避免在片段上執行資料去複本時不必要之輸入與輸出；其中該方法還包括：分割該多個漸進式更新的多個區塊，以作為該多個輸入片段；查詢一內建記憶體取樣的指紋索引，以找出該多個輸入片段的每一指紋，並回傳一對相對應的資料筒識別碼與片段識別碼；當存在一儲存片段與一輸入片段是相同時，則以該對相對應的資料筒識別碼與該片段識別碼來查詢一內建記憶體片段式彙總，以決定是否擷取該對相對應的資料筒與片段，否則，查詢一內建記憶體資料筒儲存快取記憶體，來決定是否快取該相對應的資料筒；以及當沒有快取該資料筒時，自一碟片資料筒儲存元件，載入該相對應的資料筒，並查詢一每一資料筒片段索引，以找出路由至該相對應之資料筒的一特定指紋的一偏移量，以取得該特定指紋的片段資訊。
如申請專利範圍第15項所述之去複本方法，其中該方法還包括：藉由該主裝置的至少一分散器執行平行式去複本，以利用位於一資料節點端的至少一參與節點的計算能力。
如申請專利範圍第16項所述之去複本方法，其中該平行式去複本還包括：利用一加密的雜湊法來計算出多個漸進更新區塊的指紋；依一種一致性雜湊法，來分散該多個漸進更新區塊的該多個指紋，以儲存於一取樣指紋索引快取記憶體與多個子資料筒；依該一致性雜湊法，將一每一資料筒片段索引分散到至少一參與節點；以及依該一致性雜湊法，將該每一片段彙總結構分散到該至少一參與節點。
一種漸進式備份之片段式高延展的去複本方法，藉由在一次級儲存節點端的一主裝置來執行，該方法包含：接收至少一漸進式更新、欲被去複本之多個輸入片段的多個指紋、及從邏輯區塊位址至實體區塊之多個對映的個體；叢集該多個在一資料局部單元的指紋，該資料局部單元稱為資料筒；指定該多個輸入片段的可變取樣率；以及重建一每一片段彙總結構，以避免在片段上執行資料去複本時不必要之輸入與輸出；其中一基本分享單元(BSU)片段被定義為產生之後就不會被變更的一儲存片段，並且該多個輸入片段的該可變取樣率是以下列方式來達成：對於該多個輸入片段之多個BSU片段的每一BSU片段，只取樣一個指紋；以及對其它非BSU片段，指定不同的取樣率。
一種漸進式備份之片段式高延展的去複本方法，藉由在一次級儲存節點端的一主裝置來執行，該方法包含：接收至少一漸進式更新、欲被去複本之多個輸入片段的多個指紋、及從邏輯區塊位址至實體區塊之多個對映的個體；叢集該多個在一資料局部單元的指紋，該資料局部單元稱為資料筒；指定該多個輸入片段的可變取樣率；以及重建一每一片段彙總結構，以避免在片段上執行資料去複本時不必要之輸入與輸出；其中該方法還包括：藉由該主裝置的至少一分散器執行平行式去複本，以利用位於一資料節點端的至少一參與節點的計算能力；其中該平行式去複本還包括：利用一加密的雜湊法來計算出多個漸進更新區塊的指紋；依一種一致性雜湊法，來分散該多個漸進更新區塊的該多個指紋，以儲存於一取樣指紋索引快取記憶體與多個子資料筒；依該一致性雜湊法，將一每一資料筒片段索引分散到至少一參與節點；以及依該一致性雜湊法，將該每一片段彙總結構分散到該至少一參與節點；以及其中該每一片段彙總結構被分散與分割至位於該資料節點端上的該至少一參與節點，並且在該至少一參與節點上儲存該每一片段彙總結構。