生成數據存儲系統的並行恢復策略的製作方法

2023-10-31 06:05:27

專利名稱：生成數據存儲系統的並行恢復策略的製作方法
生成數據存儲系統的並行恢復策略
背景技術：
網絡系統和存儲設備需要可靠地處理和存儲數據，並且因此通常實施某種類型的 用於恢復已經丟失、退化或者以其它方式被破壞的數據的方案。在最基本的層次上，一個恢 複方案可能簡單地包括創建傳送或存儲的數據的一個或多個完整的副本或鏡像。儘管這樣 的恢復方案可能是相對較容錯的，但是相對於需要使存儲空間加倍而言並不是非常高效。 其它恢復方案包括執行奇偶校驗。因此，舉例來說在所存儲的數據被分布在多個盤上的存 儲系統中，一個盤可以被用於僅僅存儲奇偶校驗位。儘管這種類型的恢復方案需要比鏡像 方案更少的存儲空間，但是其不是同樣容錯的，因為任何兩個設備的故障都將導致不能恢 復任何被破壞的數據。因此，為了增加效率(在所生成的額外數據量方面)以及容錯性(即方案可以恢 復被破壞的數據的程度)，已經開發出多種恢復方案。這些恢復方案通常包括創建適於生成 並在原始數據分組內嵌入數據冗餘的糾刪碼(erasure code)，由此以規定的方式對所述數 據分組進行編碼。舉例來說，如果這樣的數據分組可能由於盤或扇區故障而被破壞，則這樣 的冗餘將使得能夠恢復被破壞的數據、或其至少若干部分。多種類型的糾刪碼是已知的，比 如裡德-所羅門(Reed-Solomon)碼、冗餘磁碟陣列(RAID)變型、陣列碼(例如EVEN0DD、 RDP等等)、以及實現由於盤或扇區故障而造成的數據恢復的基於異或(XOR)的糾刪碼。儘管糾刪碼的實施使得能夠恢復被破壞的數據，但是重建故障盤所需的時間也影 響存儲系統的可靠性和性能二者。在恢復故障盤的時間期間，系統可以繼續在前臺以性能 退化模式運行，在所述性能退化模式中，為了重構故障盤而對可用盤的讀取是速率受限的。 恢復可以被串行地執行，其中存儲系統中的每個盤的全部內容都被讀取以恢復丟失的數 據，但是這樣的技術是費時的。可替代地，故障盤可以被並行地恢復，這減少了重建時間。故 障盤能夠被重建的越快，則存儲系統將越可靠並且該系統運行在性能退化模式下的時間越 少。然而，由於因恢復工作給系統造成的負荷，為更快速恢復所花費的代價通常是更嚴重退 化的模式性能。為了抵消退化的性能，可以對從每個可用盤進行讀取執行調度以減少任何 一個盤上的負荷。因此，可以實施並行恢復方案來減少給每個可用盤造成的負荷和/或增 加恢復故障盤的速率。


圖1示出了根據本發明的示例性實施例的設備的網絡。圖2示出了根據本發明的示例性實施例的由糾刪碼實施的編碼和解碼過程。圖3是根據本發明的示例性實施例的表示糾刪碼的Tarmer圖。圖4是用於生成並行恢復策略以恢復存儲系統中所丟失的數據的技術的流程圖。圖5是根據本發明示例性實施例的用於為糾刪碼中的符號生成恢復策略列表的 技術的流程圖。圖6示出了根據本發明的實施例的由圖3的Tarmer圖表示的(5，3)-平面碼(flat code)中的符號的示例性並行恢復策略。
圖7是根據本發明示例性實施例的用於為糾刪碼中的符號生成條件並行恢復策 略的技術的流程圖。圖8是根據本發明示例性實施例的用於為糾刪碼中的多個符號生成多並行恢復 策略的技術的流程圖。
具體實施方式

圖1示出了設備系統100的示例性布置，該設備系統100包括多個計算機主機 102,104,106以及多個存儲設備108、110和112。在一個實施例中，主機102,104,106以及 存儲設備108、110和112可以通過網絡101互連。網絡101例如可以包括區域網(LAN)、廣 域網(WAN)、存儲區域網(SAN)、網際網路、或者任何其它類型的通信鏈路。另外，網絡101可 以包括系統總線或其它快速互連。圖1所示的系統100可以是下述中的任何一個應用服 務器群(farm)、存儲伺服器群(或存儲區域網)、web伺服器群、交換機或路由器群等等。盡 管圖1中示出了三個主機102、104、106以及三個存儲設備108、110和112，但是能夠理解， 根據系統100所用於的特定應用，系統100可以包括三個以上的主機和三個以上的存儲設 備。所述主機例如可以是計算機(例如應用伺服器、存儲伺服器、web伺服器等等)、通信模 塊(例如交換機、路由器等等)、以及其它類型的機器。儘管所述主機之中的每個都在圖1 中被描繪為包含在框中，但是特定的主機可以是分布式機器，該分布式機器具有多個節點， 所述節點提供分布式且並行的處理系統。存儲設備108-112適於存儲與主機102-106相關聯的數據。主機102-106之中的 每個都可以耦合到存儲設備108-112之中的一個或多個，並且主機102-106之中的每個都 可以訪問存儲設備108-112以用於存儲和/或從這些設備檢索數據。存儲設備108-112之 中的每個都可以是獨立的存儲體(memory bank)。可替代地，設備108-112可以互連，由此 形成大的存儲體或者大存儲體的子聯合體(subcomplex)。根據設備被部署於其中的系統 100的特定實施方式，設備108-112例如可以是磁存儲器設備、光存儲器設備、快閃記憶體設備等寸。在示例性的實施例中，可以在所述多個主機102-106和/或所述多個存儲設備 108-112上實施糾刪碼，以使得能夠恢復在由主機102-106和/或存儲設備108-112實施 的傳送、存儲和/或檢索操作期間被損壞、丟失或者以其它方式被破壞的數據。糾刪碼的 類型包括最大距離可分(MDS)碼、以及基於異或的碼。總的來說，MDS和基於異或的糾刪 碼二者都由η個符號構成，所述η個符號之中的k個是數據符號，並且所述η個符號之中 的m個是冗餘(或奇偶校驗)符號。基於異或的糾刪碼包括奇偶校驗陣列碼、簡單積碼 (simple product code)、Weaver碼、以及平面碼。奇偶校驗陣列碼將每個盤的多個符號放 置成條塊(strip)。來自每個盤的條塊共同構成條帶(stripe)。奇偶校驗陣列碼的例子包 括 EVEN0DD、行對角奇偶校驗(Row-DiagonalParity，RDP)、以及 X 碼。EVEN0DD 和 RDP 碼是 水平碼_即條塊包括數據或奇偶校驗符號，但不會同時包括二者)。X碼是垂直碼_即每個 條塊包括相似數目的數據和奇偶校驗符號。簡單積碼是水平垂直碼一些條塊與垂直碼條塊類似，並且其它條塊與水平碼條 塊類似。Weaver碼是具有規則對稱結構的垂直碼。平面碼是每條塊具有單個符號的基於 XOR的水平糾刪碼。為了平衡由於存儲設備間的奇偶校驗更新造成的負荷，水平和水平垂直碼可以被旋轉(也就是說，每個接連的條帶或條帶集合中的條塊被旋轉以將數據和奇偶 校驗符號的數目均勻地分布在系統中的存儲設備當中)。在下面的討論中，將使用標記(k， m)- 「類型」碼來指代特定的碼。舉例來說，具有5個數據符號和3個奇偶校驗符號的平面 碼將被稱為(5，3)-平面碼。圖2示出了根據本發明示例性實施例的糾刪碼編碼和解碼過程200。過程200包 括由糾刪碼執行的編碼和解碼步驟，以用於在系統100中存儲、檢索和/或傳送數據。根據 本發明的一個實施例，過程200由基於異或的碼來執行。如圖2所示，初始數據集202被提 供，所述數據集202包括位串、字節串或者表示由系統100所使用的可存儲、可 檢索、和/或 可傳送數據或其他信息的其它符號串。糾刪碼將初始數據集202編碼成經過編碼的數據集 204 (由箭頭206表示)。箭頭206表示變換過程，該變換過程通常包括在原始數據集202 內創建冗餘，由此增加其大小以形成經過編碼的數據集204。所使用的特定變換過程206基 於所使用的糾刪碼以及系統100的特定實施方式。在編碼以後，數據集204可以被存儲、檢索、和/或傳送(如箭頭208所指示的那 樣)。舉例來說，箭頭208可以對應於在各個計算機之間傳輸數據集204或者對應於用戶從 伺服器檢索數據。可替代地，箭頭208可以對應於發生在系統100的多個通信和/或存儲 設備之間的數據傳送、存儲、和/或檢索操作。在由箭頭208表示的過程期間，數據集204 例如可能通過有損通信信道傳播或者被存儲在壞損(corrupted)的存儲設備中。因此，數 據集204的某部分可能丟失或者以其它方式被破壞，從而產生退化數據集210。如圖2所 示，數據集210包括糾刪部分(由被劃掉的部分來表示)，所述糾刪部分對應於數據集204 的在過程208期間已經丟失的那些部分。根據所使用的糾刪碼和丟失數據部分，原始數據 集202可能是可恢復的。為了恢復初始數據集202，解碼過程(由箭頭212來表示)被應用於退化數據集 210。再次，所使用的特定解碼過程依賴於所實施的糾刪碼的結構。由於恢復數據的能力依 賴於所使用的糾刪碼以及經過編碼的數據集204的哪些部分已丟失(即糾刪部分)，因此在 一些情況中可能不能恢復初始數據集202。如下面將要描述的那樣，本發明的示例性實施例提供一種用於恢復由於一個或多 個存儲設備的故障而丟失的數據的技術。儘管該技術將針對非MDS的基於異或的碼而被描 述，但是應當理解，該恢復方案可適用於其它類型的糾刪碼，包括MDS碼。該技術包括在該 系統中的每個存儲設備上枚舉(enumerate)每個符號的恢復策略，並且然後確定並行的恢 復策略來重建一個或多個故障存儲設備。如在此所使用的那樣，恢復策略是負責恢復特定 條塊內的丟失符號的策略。並行恢復策略是可以被並行執行以重建故障存儲設備的恢復策 略的列表。並行策略中的每個恢復策略負責從不同存儲設備集合中恢復丟失符號。所述並 行策略影響恢復的「加速」和恢復期間的系統上的「負荷」 二者。如在此所使用的那樣，「加 速」是並行策略與單獨的恢復策略(即其中必須讀取某個數目的盤的全部內容來恢復故障 盤的恢復策略)的恢復速率之比。如在此所使用的那樣，「負荷」是與為了重建故障盤而必 須讀取的數據相當(worth of)的盤的數目。並行策略可以基於所期望的性能度量(比如 在恢復期間實現最大加速與最小負荷的平衡)來選擇。可替代地，並行策略的選擇可以更 加偏向於最大加速或者更加偏向於最小負荷。使得能夠重建故障設備的特定恢復方案依賴於該系統中所實施的糾刪碼的結構。這樣的結構可以由生成矩陣或者Tanner圖來定義。如本領域中已知的那樣，(k，m)_碼的 生成矩陣是兩個元素的伽羅瓦(Galois)域中的kX (k+m)矩陣。在生成矩陣中添加行和列 通過模2、即根據異或運算來完成。生成矩陣由kXk數據子矩陣和作為奇偶校驗子矩陣附 加到所述數據子矩陣的維度為kXl的m個列構成。所述數據子矩陣的m個列之中的每個 都對應於所存儲的數據符號。同樣，所述奇偶校驗子矩陣中的m個列之中的每個都對應於 所存儲的奇偶校驗符號。若且唯若數據符號si被異或以確定P時，奇偶校驗列P在行i中 才具有「1」。例如，如果P = s2 XOR s4，則奇偶校驗列ρ在行2和4中具有「1」，並且在所 有其它行中具有「0」。例如，下面闡述了(5，3)-平面碼的一個可能的生成矩陣。 該(5，3)-平面碼的結構還可以由Tarmer圖來表示。Tarmer圖是一種二分圖，該 二分圖在一側具有k個數據節點，在另一側具有m個奇偶校驗符號，並且具有根據糾刪碼的 結構將所述數據符號與奇偶校驗符號互連的多個邊。圖3中示出了 Tanner圖300，其表示 由上面的生成矩陣所描述的糾刪碼的結構。一般而言，故障存儲設備上的每個符號都可以根據依賴於糾刪碼結構的一個或多 個恢復策略而被恢復。在最簡單的意義上，針對基於異或的糾刪碼而言，用於確定每個存儲 設備上的每個符號的恢復策略的算法是測試該碼中的符號的所有組合的異或。其異或產生 所討論的符號的任何符號組合都是該符號的恢復策略。然而這樣的蠻力(bruteforce)算 法不是非常高效，因為其考慮了 Zk+"1-1種符號組合，並且可能生成依賴於比所需還多的存儲 設備的一些恢復策略。參考圖4中的流程圖，用於產生盤上的每個符號的恢復策略的更高效的算法400 使用例如由該碼的生成矩陣或Tarmer圖所定義的糾刪碼的結構(步驟402)。以這種方式 為該碼的每個符號所生成的恢復策略(RP)被稱為基本恢復策略(BRP)(步驟404)。根據本 發明的實施例，每個符號的基本恢復策略然後可以被操縱以產生該碼的每個符號的所有恢 復策略的列表(步驟406)。然後，所有符號的恢復策略列表可以被組合考慮以生成可能的 並行恢復策略的集合以用於重建故障存儲設備(步驟408)。然後，所述可能策略的集合可 以被評估以基於所選性能度量來識別用於重建每個存儲設備的優選的並行恢復策略(步 驟410)。下面的表1闡述了用於以這種方式生成並行恢復策略列表以及識別優選策略的示 例性恢復策略和並行恢復策略算法的偽代碼。 用於為糾刪碼的數據符號和奇偶校驗符號生成基本恢復策略的過程是不同的，不 過這兩個過程都基於由生成矩陣或Tarmer圖所定義的碼的結構來確定基本恢復策略。舉 例來說在一個實施例中，對於奇偶校驗符號而言，基本恢復策略僅僅只是被重新布置為求 解奇偶校驗符號的奇偶校驗方程，也就是說，生成矩陣的對應於奇偶校驗符號的列被重新 布置。對於每個奇偶校驗符號正好存在一個基本恢復策略。因此舉例來說，參考上述(5， 3)_平面碼的生成矩陣，奇偶校驗符號s5的基本恢復策略是s5 = s0 XOR si XOR s2 (或(0，1，2)) (1)對於數據符號而言，可以使用生成矩陣的行或Tanner圖來確定每個符號的基本 恢復策略。舉例來說，參考表1中所述的恢復策略算法，函數baSe_rp枚舉糾刪碼中的數據 符號s的基本恢復策略。對於每個數據符號s而言，針對依賴於該數據符號的奇偶校驗符 號的每個「奇集合(odd set)」存在基本恢復策略。奇偶校驗符號的奇集合可以根據對應於 糾刪碼的Tarmer圖或者生成矩陣的行來確定。當參考Tanner圖300時，奇集合是數據符 號所連接到的具有奇數大小的奇偶校驗節點的所有集合。舉例來說，對於上述(5，3)_平面 碼而言，Tarmer圖300示出了 數據符號s0分別通過邊302、304和306連接到三個奇偶校 驗符號s5、s6和s7。因此，符號s0具有四個奇偶校驗符號奇集合。更具體而言，存在三個 大小為1的奇集合(即針對每個奇偶校驗符號s5、s6和s7各有一個集合)和一個大小為3 的奇集合(即由三個奇偶校驗符號s5、s6和s7構成的一個集合)。數據符號s4具有僅僅一個奇偶校驗符號奇集合，因為節點s4僅僅通過邊308連接到奇偶校驗符號s7。因此，該 奇集合大小為1並且由奇偶校驗符號s7構成。奇集合後面的直覺知識是由於單奇偶性， 奇數個基本恢復策略的異或仍然是基本恢復策略。偶集合不能產生恢復策略，因為其不能 產生可以求出缺失符號的方程。再次參考表1中所述的偽代碼，函數bitmap (p，s)求解ρ的奇偶校驗方程以求出符號s。例如，針對數據符號s0的僅僅包括ρ = s5的奇集合，bitmap (5，0)返回38，因為38 =2、22+25。符號s0的奇集合可以參考圖3中的Tanner圖300來容易地獲悉。在Tanner 圖300中，數據符號sO連接到奇偶校驗符號s5、s6、s7。第一奇集合由符號s5構成，符號 s5通過邊連接到數據符號sO、si和s2。第二奇集合由符號s6構成，符號s6通過邊連接 到數據符號s0、sl、和S3。第三奇集合由符號s7構成，符號s7通過邊連接到數據符號sO、 s2、s3和s4。因此，符號sO的前三個基本恢復策略是奇偶校驗符號s5、s6和s7之中每個 的奇偶校驗方程的簡單重新布置，以求出符號sO。基於大小為3的奇集合的第四恢復策略 是三個其它基本恢復策略的異或。因此，基於大小為1的奇集合的前三個基本恢復策略是s0 = sl XOR s2 XOR s5 (或(1，2，5))(2)sO = si XOR s3 XOR s6 (或(1，3，6))(3)sO = s2 XOR s3 OR s4 XOR s7 (或(2，3，4，7)) (4)基於大小為3的奇集合的第四基本恢復策略是sO = s4 XOR s5 XOR s6 XOR s7 (或(4，5，6，7)) (5)然後，sO的基本恢復策略被操縱以生成sO的恢復策略的列表。這例如通過使用 表1中的函數enump_rp以及如圖5的示例性恢復策略算法500的流程圖中所述的那樣來 完成。根據該算法，針對每個符號s (數據符號或奇偶校驗符號)，恢復策略的列表被初始化 為其基本恢復策略的列表(步驟502)。在給定所有符號的基本恢復策略的情況下，函數rp枚舉特定符號的恢復策略。函 數rp按次序處理基本恢復策略的初始列表，並且在附加的恢復策略被找出時將其附加到 該列表。為了根據該列表生成恢復策略rp，針對基本恢復策略BRP (s)中的每個數據符號 s'，識別s'的不依賴於s的基本恢復策略(BRP(s'))的集合(步驟504)。函數Cond_ rp確定這樣的條件基本恢復策略集合。針對條件基本恢復策略集合中的每個基本恢復策 略BRP(s')，用基本恢復策略BRP(s『)替代基本恢復策略BRP(s)中的s'並且進行異或 (步驟506)。如果所得到的恢復策略還未處於s的基本恢復策略的列表中，則所得到的恢 復策略被附加到s的恢復策略列表(步驟508)。在本發明的一些實施例中，可以為每個數 據符號s維持恢復策略的詞典(dictionary)，以保證附加到初始列表的每個恢復策略都是 唯一的。該過程針對基本恢復策略BRP(s)中的每個符號s'重複進行，直到所有符號s' 都已經被考慮並且被替換為止(步驟510和512)。一旦BRP(S)中的所有符號s'都已經 被考慮，則符號s的下一個BRP被操縱(步驟514和516)。為了說明，考慮上述(5，3)_平面碼中的數據符號sO。對於s = sO的恢復策略的 列表被初始化成sO的四個基本恢復策略的列表。因此由函數rp處理的第一恢復策略是 (1，2，5)。在該恢復策略中被處理的第一數據符號是si。s'的不依賴於數據符號sO的第 一基本恢復策略是(3，4，5，7)。用(3，4，5，7)替代恢復策略(1，2，5)中的符號s 1並且進行異或將產生條件恢復策略(2，3，4，7)。因為(2，3，4，7)已經處於數據符號sO的基本恢復 策略的列表中，所以該條件恢復策略不被附加到符號sO的恢復策略的列表。當該過程針對 sO的恢復策略中的每個符號重複進行時，在該情況中發現符號sO的恢復策略的列表簡單 地是sO的基本恢復策略的列表。一旦糾刪碼中的符號的恢復策略列表被生成，則可以確定用於重建故障存儲設備 的並行恢復策略。儘管許多並行恢復策略都是可能的，但是可以使用各種性能度量來確定 優選的並行恢復策略。在一個實施例中，所述度量是具有最小負荷的最大加速。因此，在 將該度量用作準則的情況下，優選的並行恢復策略產生用於並行執行的恢復策略集合的調 度，其中該調度提供具有最小負荷的最大加速。還構思有其它類型的用於選擇優選並行恢 復策略的性能度量。舉例來說，也可以考慮在並行恢復策略中必須從最忙的存儲設備中讀 取的數據量的界限(被稱為「瓶頸盤負荷」)。並行恢復策略的容錯性和可靠性也可以是可 以被用於選擇優選並行策略的性能度量。在最簡單的意義上，優選並行恢復策略可以通過評估可以重建故障盤的恢復策略 的所有可能的組合而被確定。然而，由於碼的恢復策略的數目可能非常大，因此以這種方式 來確定並行恢復策略並不是高效的。因此，在本發明的一些實施例中，恢復策略算法可以通 過基於某種所指定的界限(比如恢復策略的權重)對添加到該列表的恢復策略進行過濾來 降低所考慮的恢復策略的數目(即恢復策略算法濾除依賴於超過預先定義的閾值的數目 的符號的高權重策略)。在給定符號的恢復策略列表的情況下，可以使用並行恢復策略算法來確定故障存 儲設備的所有並行恢復策略。再次，在最簡單的意義上，並行恢復策略算法可以考慮每個符 號S的所有恢復策略，並且確定所有可能的恢復策略組合的冪集P，其中冪集P中的每個元 素P都是並行恢復策略。然後，並行恢復策略算法可以基於所期望的性能度量(比如加速 和負荷)來評估每個元素P。加速被定義為並行策略P中的恢復策略的數目除以P中的出 現任何一個符號的恢復策略的最大數目。負荷被定義為與在並行策略P中將被讀取的數據 相當的盤的總數，其通過將在P中的每個恢復策略上所使用的符號的總計數目除以P中的 恢復策略的數目而被計算出。根據本發明的一個實施例，由並行恢復策略算法針對加速和負荷所評估的恢復策 略的組合的數目可以通過濾除冪集P中如下這樣的並行策略P而被減小，對於所述並行策 略p，P中的其中出現任何一個符號的恢復策略的最大數目受常數限制。該常數被稱為瓶頸 界限。瓶頸界限在濾除並行策略方面是有效的，因為加速度量是並行策略中的恢復策略的 數目除以任何一個符號參與其中的恢復策略的最大數目。例如，如果瓶頸界限是「 1 」，則僅 僅不相交的恢復策略被包括在並行策略中。因此，在該例中，加速僅僅只是構成該並行策略 的恢復策略的數目。再次參考表1中的偽代 碼，在給定恢復策略列表和特定瓶頸界限的情況下，函數 enUm_pp遞歸地枚舉並行策略。在第一循環中，enum_pp函數將來自該列表中的每個恢復策 略添加到並行策略並且然後遞歸。針對第一恢復策略，enUm_pp的調用產生可以在不超過 該瓶頸界限的情況下被添加到該並行策略的每個其它的恢復策略(即第二到最後一個策 略)，由此生成並行策略(以及進一步的遞歸)。當恢復策略列表用盡時，遞歸停止。在一 個實施例中，可以使用直方圖來確定將恢復策略添加到並行策略是否超過瓶頸界限。
為了識別最佳的並行策略，並行恢復策略算法以連續更大的瓶頸界限調用enum_ PP，直到達到某一最大瓶頸界限為止。如在此所使用的那樣，「最佳」或「優選」的並行策略 是滿足所期望的性能度量的策略。因此，「最佳」的策略將根據所選度量而變化。而且，可能 存在多個最佳或優選的策略。無論所使用的度量如何，由enum_pp所生成的所有並行策略然後被評估以找出滿足所選度量的那些策略，舉例來說，比如首先找出具有最大加速的那些策略並且然後找出 具有最小負荷的那些策略。在其它實施例中，如果主導的度量是最小負荷，則並行策略算法 的優先級可以被定義為首先考慮最小負荷並且然後考慮最大加速。表1中的函數best_pp 示出了針對單個符號的恢復策略列表的該過程。在給定碼中的每個符號的最佳並行策略的 情況下，並行恢復策略算法然後可以在假定已經擦除單個符號的情況下計算所有符號上的 平均加速和負荷。計算平均數所針對的是如下事實糾刪碼常常被應用於被旋轉的條帶。圖6示出了由並行恢復策略算法為故障盤d 0所選擇的並行策略600的例子。在 圖6中，(5，3)-平面碼被實施在8個盤d0_d7上。如上面所討論的那樣，符號sO的恢復策 略列表是在故障盤d0上的sO的基本恢復策略的列表[(1，2，5)，(1,3,6), (2,3,4,7), (4， 5，6，7)]。恢復策略(1,2,5)在條帶602上恢復d0上的sO ；恢復策略(1,3,6,5)在條帶604 上恢復d0上的sO ；恢復策略(2，3，4，7)在條帶606上恢復d0上的sO ；並且恢復策略(4， 5,6,7)在條帶608上恢復d0上的sO。在圖6所示的並行策略600中，每個盤都是瓶頸盤， 因為每個盤都參與兩個恢復策略。因此，最佳或優選並行策略調度所有四個恢復策略。在 該策略中，加速是2.0，其是通過將並行策略中所調度的恢復策略的數目(即4)除以每個 瓶頸盤參與的恢復策略的數目(即2)而確定的。該並行策略的負荷是3. 5，其是通過將組 成策略(constituent plan)中的符號的總數(即3+3+4+4)除以組成恢復策略的數目(即 4)而確定的。這意味著，需要3. 5個盤的數據來恢復丟失的盤d0 (即每個可用盤的一半在 盤d0的重構期間被讀取)。上述恢復策略和並行恢復策略算法假設僅僅一個存儲設備發生了故障。在其它實 施例中，該算法可以被擴展為考慮多個故障。舉例來說，如圖7所示，可以實施條件恢復策 略算法700，其在假定其它符號也已經丟失的情況下確定丟失符號的所有可能的條件恢復 策略。根據該算法，為特定符號s生成的恢復策略(RP)的列表被考慮(步驟702)。針對 該列表中的每個恢復策略中的每個其它符號s'，那些依賴於符號s'的恢復策略被濾除 以提供符號s的以符號s'的丟失為條件的恢復策略(被稱為RP(s，s'))的列表(步驟 704，706，708)。該算法700可以被進一步擴展為生成以成對、成三元組等等的其它丟失符 號為條件的條件恢復策略列表。使用枚舉的條件恢復策略，條件並行恢復策略算法可以被 實施，其枚舉所有可能的條件並行恢復策略並且基於一個或多個所選度量(比如並行性和 /或負荷)確定每個條件並行恢復策略的效力。上述恢復策略和並行恢復策略算法還可以被擴展為實施多並行恢復策略算法 800，其確定所有可能的多並行恢復策略(即根據某種調度並發地恢復多個丟失符號的策 略)並且基於一個或多個所選度量(比如並行性最高的、負荷最小的、或其組合)確定每 個多並行恢復策略的效力。舉例來說，參考圖8，為符號s和s'生成恢復策略列表(步驟 802)，並且並行策略ρ和ρ'的集合P和P'根據相應恢復策略列表而被生成(步驟804)。 然後，在給定兩個丟失符號s和s'的情況下，多並行恢復策略800 —起考慮符號s的並行恢復策略的集合P和符號S'的並行恢復策略的集合P'。然後，算法800根據這些集合確 定所有可能的多並行恢復策略的集合以及運行所述策略的調度(步驟806)。調度是符號s 的恢復策略與符號s'的恢復策略的配對的列表，使得來自並行策略ρ和ρ'的併集的每個 恢復策略發生正好一次。如果並行策略P和P'具有不同數目的恢復策略，則恢復策略的 一些配對將含有僅僅單個恢復策略(即來自並行策略P和P'之中較長者的策略)。然後， 可以為每個多並行恢復策略確定性能度量(比如加速和負荷)(步驟808)。在一個實施例 中，最高效的多並行恢復策略可以通過如下方式確定檢查P和P'中的所有恢復策略並且 識別共有最多數目的符號的那些恢復策略。對於多並行恢復策略而言，加速是所有丟失符 號上的加速之和。負荷是調度的函數。舉例來說，在給定被一起調度的恢復策略對(一個 來自P、一個來自P')的情況下，在兩個恢復策略中都出現的符號被僅僅計數一次。因此， 具有最低負荷的多並行恢復策略是共有最多數目的符號的策略的那些組合。可以對於任何數目的丟失符號實施多並行策略。另外，用於減小使用並行恢復策 略算法評估的並行策略的數目的上述技術還適用於多並行恢復策略算法。應當理解，在此所述的並行恢復策略技術可適用於靜態和旋轉的碼二者。對於旋 轉的碼，不是識別整個存儲設備的單個並行恢復策略，而是根據糾刪碼的符號在(一個或 多個)存儲設備上被旋轉的方式來為所述設備的每個條塊集合選擇並行恢復策略。上述軟體的指令(包括上述的以及在表1和圖4、5、7和8中被部分示出的恢復策 略算法、並行恢復策略算法、條件恢復策略算法、條件並行恢復策略算法、以及多並行恢復 策略算法)被加載以用於在處理器(比如圖1的一個或多個CPU114-118)上執行。所述處 理器可以包括微處理器、微控制器、處理器模塊、或者子系統(包括一個或多個微處理器或 微控制器)、或者其它控制或計算設備。如在此所使用的那樣，「控制器」是指軟體、硬體、或 其組合。「控制器」可以指單個部件或多個部件(無論是軟體還是硬體)。(軟體的)指令、數據、或者數據結構被存儲在相應的存儲設備中，所述存儲設備 被實施為一個或多個計算機可讀或者計算機可用的存儲介質(比如圖1中的一個或多個存 儲器120-124)。所述存儲介質包括不同形式的存儲器，包括半導體存儲器件，比如動態或 靜態隨機存取存儲器(DRAM或SRAM)、可擦除可編程只讀存儲器(EPROM)、電可擦除可編程 只讀存儲器(EEPROM)、以及快閃記憶體；磁碟，比如固定盤(fixed disk)、軟盤、以及可移動盤；包 括磁帶在內的其它磁介質；以及光學介質，比如緻密盤(CD)或者數字視頻盤(DVD)。注意 上述軟體的指令、數據以及數據結構可以被提供在一個計算機可讀或計算機可用的存儲介 質上，或者可替換地，可以被提供在分布在可能具有多個節點的大系統中的多個計算機可 讀或計算機可用的存儲介質上。這樣的(一個或多個)計算機可讀或計算機可用的存儲介 質被認為是物品(或製造品)的一部分。物品或製造品可以指任何所製造的單個部件或多 個部件。在此描述的算法可以被實施為用於評估被實施在各個存儲系統上的各個碼的並 行恢復策略的獨立工具。也設想所述算法的其它應用，比如將所述算法作為管理工具嵌入 到存儲系統(比如系統100)中以周期性地識別一個或多個丟失符號的並行恢復策略、和/ 或以實時的方式提供對並行恢復策略的評估(例如，使得加速與負荷之間的平衡可以通過 識別 不同的並行恢復策略而動態地改變)。在前述描述中，闡述了許多細節以提供對本發明的理解。然而，本領域的技術人員能夠理解，本發明可以在沒有這些細節的情況下被實施。儘管本發明是針對有限數目的實施例而被公開的，但是本領域的技術人員在得益於本公開的情況下能夠理解本公開的許多 修改和變型。旨在由所附權利要求來覆蓋所有這樣的落入本發明的實際精神和範圍內的修 改和變型。
權利要求
一種用於識別數據存儲系統的並行恢復策略的方法，包括識別在數據存儲系統中的多個存儲設備上所實施的糾刪碼的符號的基本恢復策略；基於所述基本恢復策略生成第一符號的第一恢復策略的列表；以及組合來自所述列表的所選第一恢復策略以生成用於重建故障存儲設備的並行恢復策略的集合。
2.如權利要求1中所述的方法，進一步包括提供所述糾刪碼的結構，其中對所述基本恢復策略的識別基於所提供的結構。
3.如權利要求1中所述的方法，其中生成恢復策略的列表包括 提供第一符號的第一基本恢復策略；在第一基本恢復策略中識別所述糾刪碼的第二符號；用與第二符號相關聯的第二基本恢復策略替代第一基本恢復策略中的第二符號以生 成恢復策略；以及將所述恢復策略添加到恢復策略的列表中。
4.如權利要求1中所述的方法，進一步包括基於性能度量來評估並行恢復策略的集合以識別用於重建故障存儲設備的優選並行 恢復策略。
5.如權利要求4中所述的方法，其中所述性能度量是具有最小負荷的最大加速。
6.如權利要求1中所述的方法，其中第一符號的恢復策略以所述糾刪碼的其它符號的 丟失為條件。
7.如權利要求1中所述的方法，進一步包括生成所述糾刪碼的第二符號的恢復策略的列表；以及將第一符號的所選恢復策略與第二符號的所選恢復策略相組合以生成多並行恢復策 略，其中多並行恢復策略包括第一符號的所選恢復策略和第二符號的所選恢復策略。
8.一種用於生成糾刪碼的符號的恢復策略的列表的方法，包括 提供在多個存儲設備上實施的具有多個符號的糾刪碼的結構； 基於所述結構生成所述符號的基本恢復策略；以及針對第一符號的每個基本恢復策略， 識別所述基本恢復策略中的第二符號；識別所述第二符號的不依賴於所述第一符號的第二基本恢復策略； 用所述第二基本恢復策略替代所述第一符號的基本恢復策略中的所述第二符號以生 成恢復策略；以及將所述恢復策略添加到恢復策略的列表中。
9.如權利要求8中所述的方法，進一步包括使第一符號的恢復策略以所述糾刪碼的 另一符號的丟失為條件。
10.如權利要求8中所述的方法，其中所述符號包括數據符號和奇偶校驗符號，並且 其中生成數據符號的基本恢復策略包括識別連接到所述數據符號的奇偶校驗符號的奇集合。
11.如權利要求10中所述的方法，其中所述結構是Tanner圖和生成矩陣之一。
12.一種用於選擇用於重建故障數據存儲設備的並行恢復策略的方法，包括生成在多個存儲設備上實施的具有多個符號的糾刪碼的符號的恢復策略的列表； 組合來自所述列表的恢復策略以生成用於重建故障存儲設備的並行恢復策略的集合；從所述並行恢復策略的集合中過濾掉那些超過瓶頸界限的並行恢復策略；以及 評估並行恢復策略的經過過濾的集合以識別用於重建故障存儲設備的優選並行恢復 策略。
13.如權利要求12中所述的方法，其中生成恢復策略的列表包括 識別基本恢復策略；基於所述基本恢復策略生成恢復策略；以及從所述列表中過濾掉任何具有超過預先定義的閾值的數目的符號的恢復策略。
14.如權利要求12中所述的方法，其中基於加速和負荷中的至少一個來評估並行恢復 策略的經過過濾的集合以識別優選並行恢復策略。
15.如權利要求12中所述的方法，其中所述糾刪碼是基於異或的糾刪碼。
全文摘要
一種用於識別數據存儲系統的並行恢復策略的方法，包括識別在數據存儲系統中的多個存儲設備上實施的糾刪碼的符號的基本恢復策略；通過操縱所述基本恢復策略生成第一符號的第一恢復策略的列表；以及組合來自所述列表的所選第一恢復策略以生成用於重建故障存儲設備的並行恢復策略的集合。
文檔編號G06F11/10GK101868785SQ200880117051
公開日2010年10月20日 申請日期2008年9月19日 優先權日2007年9月21日
發明者J·J·維利, K·M·格裡南 申請人:惠普開發有限公司