將擦除碼數據分配到磁碟存儲器的方法和裝置製造方法

2023-06-16 10:22:07 2

將擦除碼數據分配到磁碟存儲器的方法和裝置製造方法
【專利摘要】分配處理允許擦除編碼數據被存儲在驅動器池裡的多個磁碟驅動器的任何一個上，以便分配不會被捆綁到固定的驅動器組。更進一步講，可以通過多個不同擦除碼算法的任何一個產生編碼數據，其中再次基於用來編碼數據的擦除算法，編碼數據的存儲不會局限於單個驅動器組。在另一個實施例中，編碼數據能夠被「堆疊」(排列)在選中的驅動器上以降低訪問數據所需要的磁碟尋道的數目。作為這些改進的結果，所述系統能夠動態地為給定的輸入數據塊確定使用多個擦除碼算法中的哪一個，而不必像現有技術那樣被捆綁到一個特定算法以及一個特定存儲設備組。
【專利說明】將擦除碼數據分配到磁碟存儲器的方法和裝置
【技術領域】
[0001]本發明涉及計算機存儲系統和允許使用多個擦除碼算法將數據放置在磁碟存儲器(disk storage)上的方法和裝置。
【背景技術】
[0002]文件系統、作業系統或其它存儲管理器的重要任務就是把數據放置在存儲器介質上，諸如磁碟存儲器設備。數據被寫入哪裡(被放置在磁碟上)以及它是何時以及如何被訪問的，對讀/寫性能能夠具有重要的影響。
[0003]另一個重要任務是在存儲器介質遭受物理損壞的情況下，保護數據避免丟失(容錯性)。RAID，獨立磁碟冗餘陣列的縮寫，是在多個物理驅動器之間劃分並複製數據的各種數據存儲器方案的涵蓋性術語，以便如果一個(或可能更多)驅動器被損壞，那些驅動器上丟失的數據是能夠被恢復的。每個方案提供兩個主要目標之間的不同平衡:提高的數據可靠性以及提高的輸入/輸出(I/O)性能。
[0004]擦除碼(erasure coding)是糾錯算法的集合,其使得在基於(例如RAID陣列的)多個磁碟驅動器的存儲系統中的失效驅動器上丟失的數據能夠被恢復。產生擦除編碼數據以及將擦除編碼數據寫到存儲器的大致過程包括:
[0005]1、數據以一系列的塊的方式到達；
[0006]2、每個塊被分成子塊；
[0007]3、將擦除碼算法應用於所述子塊組；
[0008]4、結果是以由所使用的具體算法確定的更大量的子塊(例如，包括奇偶校驗數據)；
[0009]5、產生的子塊以由所使用的具體算法所確定的一個或多個子塊的組的方式被寫出到所述存儲器介質，每一個設備(例如磁碟驅動器)一個組。
[0010]然後進行如下的恢復過程(即，恢復在失效的磁碟驅動器上丟失的數據):
[0011]1、從另一個(非失效)設備讀取剩餘子塊組；
[0012]2、對剩餘的子塊應用恢復算法來產生丟失的數據；
[0013]3、返回原始完整的數據塊。
[0014]上述過程的說明是通用的並適用於許多不同的擦除碼算法。每個碼算法具有其自身的關於如下的權衡取捨:
[0015]1、I/O 性能；
[0016]2、CPU 利用率；
[0017]3、存儲效率；
[0018]4、可容忍的驅動器失效的數目。
[0019]根據現有行業標準，數據大小、擦除碼算法以及磁碟驅動器陣列是被作為一個整體捆綁到一起的，使得一旦為數據和算法建立了驅動器組合配置，將不能夠改變擦除碼算法。在設計這種系統的時候，基於需要的冗餘度、被存儲的數據量以及數據塊的粒度作出選擇。基於這些參數以及平衡性能特性(諸如訪問時間以及恢復時間)，選擇配置陣列(物理磁碟驅動器的固定組)。一旦建立這個驅動器分組，那麼在那些驅動器上只能夠使用指定的擦除碼算法來存儲數據。更進一步講，以小於所選擦除碼算法指定的最小大小寫入數據導致性能命中(hit)(下降)，因為它需要更耗時的讀取-更改-寫入，而不是簡單的寫入。
[0020]因此，需要一種更靈活的系統來向磁碟存儲分配擦除編碼數據。需要更高的靈活性來提高I/o性能、CPU利用率、存儲容量、容錯性和/或恢復時間中的一個或多個。

【發明內容】

[0021]根據本發明的一個實施例，提供一種分配處理，其允許擦除編碼數據被存儲在驅動器池中的多個磁碟驅動器中的任何一個上，以便分配不會被捆綁到固定的驅動器組。更進一步講，能夠通過多個不同擦除碼算法的任一個產生編碼數據，其中再次所述編碼數據的存儲不會局限於基於用來編碼所述數據的擦除算法的單個驅動器組。在又一個實施例中，所述編碼數據能夠被「堆疊」(排列)在選中的驅動器上來降低訪問數據所需要的磁頭尋道(head seek)的數目。作為這些改進的結果，該系統能夠動態地為給定的輸入數據塊確定使用多個擦除碼算法中的哪個，而不是像現有技術那樣被捆綁到一個特定算法以及一個特定存儲器設備組。
[0022]根據本發明的一個實施例，提供一種用於在存儲器上定位數據的計算機執行的方法，包括計算機可執行的動作:
[0023]將由相同或不同擦除碼編碼的多個編碼數據對象分配到磁碟存儲設備池中的相同或不同設備上以用於存儲；
[0024]對每個要存儲在多個邏輯存儲單元的編碼對象，使用分配位屏蔽(bitmask)作為對可用的分配單元的單個請求，來將所述各個編碼對象存儲在多個邏輯存儲單元上，其中所述分配位屏蔽覆蓋(span)所述多個邏輯存儲單元，並包括與被存儲的編碼對象的起始分區邊界對準的間隙。
[0025]在一個實施例中，所述分配步驟包括在不同設備上分配所述編碼對象。
[0026]在一個實施例中，所述分配步驟包括分配由不同擦除碼編碼的編碼對象。
[0027]在一個實施例中，所述分配步驟包括在相同的本地存儲單元上分配多個編碼對象。
[0028]在一個實施例中，所述分配步驟包括在相同的邏輯存儲單元組上分配多個編碼對象。
[0029]在一個實施例中，所述方法包括使用所述分配位屏蔽來請求與邏輯存儲單元邊界對準的分配單元。
[0030]在一個實施例中，被編碼的數據的對象大小是固定的。
[0031 ] 在一個實施例中，被編碼的數據的對象大小是可變的。
[0032]在一個實施例中，所述數據對象是由不同類別的擦除碼來編碼的。
[0033]在一個實施例中，所述方法包括提供所述編碼數據對象的索引，其映射每個編碼數據對象到其各自的擦除碼。
[0034]在一個實施例中，所述分配步驟包括使用分配位圖(bitmap)標記所述可用的分
配單元。[0035]在一個實施例中，所述分配位圖映射到邏輯地址空間。
[0036]在一個實施例中，邏輯目標編號(LON)定義指向所述編碼對象的指針。
[0037]在一個實施例中，指向編碼對象的指針被存儲在索引記錄中。
[0038]在一個實施例中，所述索弓I記錄包括到指向所述編碼對象的多個指針。
[0039]在一個實施例中，所述分配步驟使用邊界位圖標記所述編碼對象的初始塊的分配單元。
[0040]根據本發明的另一個實施例，提供一種在其上存儲有指令的計算機可讀介質，所述指令當被載入計算機時，執行如上所述的方法步驟。
[0041]根據本發明的另一個實施例，提供一種可編程序邏輯，配置為執行如上所述的方法步驟。
[0042]根據本發明的另一個實施例，提供一種數據存儲系統，包括:
[0043]擦除碼算法選擇部件，用於為不同輸入數據對象選擇不同擦除碼算法來產生編碼數據對象；以及
[0044]磁碟存儲分配部件，用於將由所述不同算法編碼的編碼數據對象分配到磁碟存儲器設備池裡的相同或不同設備上的任何可用的分配單元。
[0045]在一個實施例中，所述系統包括用於存儲所述編碼數據的磁碟存儲器設備池。
[0046]在一個實施例中，所述磁碟存儲分配部件使用分配位屏蔽來為每個編碼數據對象請求可用的存儲單元以跨邏輯存儲單元組的一個或者多個邏輯存儲單元存儲編碼對象，所述邏輯存儲單元組覆蓋池中的多個設備，並且其中所述位屏蔽包括允許所述編碼對象被存儲在所述池中的至少一個設備上的多個邏輯存儲單元上。
[0047]在一個實施例中，所述系統包括所述將編碼數據對象映射到其各自的擦除碼算法的索引。
[0048]根據本發明的另一個實施例，在定位數據存儲的計算環境中，提供一種數據結構，包括請求可用的分配單元以跨一個或多個邏輯存儲單元存儲編碼對象的分配位屏蔽，所述編碼數據對象以不同的擦除碼來被編碼，所述分配位屏蔽覆蓋跨多個磁碟驅動器的多個邏輯存儲單元，以及所述位屏蔽包括與被存儲的編碼對象的開始分區邊界(startingpartition boundary)對準的間隙,其中跨多個邏輯存儲單元請求可用的分配單元。
【專利附圖】

【附圖說明】
[0049]圖1是本發明的一個實施例的示意性高級系統體系結構，示出了利用不同擦除碼算法對輸入數據對象的編碼以及隨後將編碼數據分配到磁碟存儲器設備池中的存儲器；
[0050]圖2是根據本發明的一個實施例的處理流程圖，用於選擇擦除碼算法以及分配所述編碼數據到所述磁碟存儲器設備池中的磁碟存儲器；
[0051]圖3A-3B示出了利用4的2 (2of4)編碼算法編碼數據對象的一個示例；
[0052]圖3C-3D示出了利用6的4 (4of6)編碼算法編碼數據對象的另一個示例；
[0053]圖3E-3F示出了利用10的8 (8of 10)編碼算法編碼數據對象的另一個示例；
[0054]圖4A-4B示出了磁碟驅動器池，每個驅動器被分為分區，以及延伸跨所述池中的驅動器的邏輯存儲單元(LSU)組；
[0055]圖5示出了根據本發明的一個實施例的用於分配編碼數據對象的分配位屏蔽的一個示例；
[0056]圖6A-6C示出了根據本發明的另一個實施例的用於分配編碼數據對象的分配位屏蔽的另一個示例；以及
[0057]圖7示出了用於處理並存儲數據的通用系統配置的一個實施例。
【具體實施方式】
[0058]現在參考【專利附圖】

【附圖說明】本發明的各種實施例。在隨後的描述中，為了說明的目的，提出了很多具體細節，以便提供對本發明的一個或多個實施方式的全面了解。然而顯而易見的是，本發明可以在不具備這些具體細節的情況下實現。在其他實例中，以框圖的形式示出眾所周知的結構和裝置，以便於描述本發明。
[0059]正如本申請中所使用的那樣，術語「部件」和「系統」意在指的是與計算機有關的實體:硬體、硬體和軟體的組合、軟體或者執行中的軟體。例如，部件可以是但不局限於在處理器上運行的處理、處理器、對象、可執行的、執行線程(thread of execution)、程序和/或計算機。通過圖示，在伺服器上運行的應用程式以及伺服器都可以是部件。一個或多個部件可以駐留在處理器和/或執行線程中，並且部件可以位於在一個計算機上和/或在兩個或更多計算機之間分布。
[0060]本發明也可以作為本發明的處理的流程圖來示出。儘管為了簡單說明的目的，以流程圖的形式被示出的一個或多個方法被描述為一連串的動作，然而應該理解和知道的是，本發明不受這些動作的順序所限制，因為某些動作可以，依照本發明，以不同的順序出現和/或和與此處示出和描述的動作不同的動作一起出現。例如，本領域技術人員可以理解並知道的是，方法可以可替換地表示為一系列相互關聯的狀態或者事件，諸如以狀態圖示出的。此外，並不需要所有示出的動作來實現根據本發明的方法。
[0061]在這裡公開的本發明的各種實施例中，術語「數據」，「數據元素」或「數據對象」可互換地使用。正如此處使用的那樣，數據指的是不透明的數據集，例如任意的符號(通常由「O」和「 I」表示)序列，其可以被輸入到計算機中，在那裡存儲和處理或被傳輸到另一個計算機。正如此處使用的那樣，數據包括元數據，其它數據的描述。寫入到如此處所述的存儲系統的數據可以是相同大小的數據對象，或可變的大小的數據對象。
[0062]此處使用的「存儲系統」可以是用於將數據存儲到磁碟存儲器的任意系統或應用程式，例如，文件系統、塊存儲設備或其它系統。存儲系統可以使用標識符或名稱來引用在存儲器中的每個數據元素。在一個示例中，名稱是全球唯一標識符(GUID)，諸如數據內容的散列，優選的是，加密散列或數據內容的抗衝突散列(collision resistant hash)。其它命名規則也是可能的，只要每個數據元素在允許給用戶恢復存儲的數據的存儲系統內具有名稱。在一個實施例中，中心伺服器產生名稱。數據名稱通常是固定長度的二進位串，意在被程序使用，而不是被人類使用。所述存儲系統可以需要所有數據的索引(有時稱為詞典或目錄)來用於訪問(定位)每個數據元素。索引中的每個記錄可以包含所述數據元素的名稱，它的邏輯和/或物理位置(地址)，以及與所述各個數據元素相關的其他信息。在一個實施例中，每個索引項包括指向磁碟上的存儲有數據對象的物理塊地址的指針。在一個實施例中，固定算法可以用來定位磁碟上的存儲有數據的物理位置。
[0063]A.系統體系結構[0064]圖1舉例說明了本發明一個實施例的高級系統體系結構100。存儲系統104接收輸入數據對象102用於放置在磁碟存儲池112的磁碟存儲設備dl、d2、d3、d4、d5、d6...上。系統104包括擦除碼算法選擇部件106和磁碟存儲分配部件108。部件106為每個輸入數據對象(D01，D02, D03...)選擇多個擦除碼算法(ECA1, ECA2, ECA3...)中的一個，以將所選的數據對象編碼到編碼數據塊組110(ED1，ED2，ED3...)。部件108然後將這些塊組分配到這種設備的池112中的多個磁碟存儲設備，每個設備一個塊組，其中塊組到設備的分配可以針對每個數據對象獨立地執行，並且所述分配不局限於設備池112中的設備的相鄰集或固定集。例如，圖1示出數據對象DOl的多個塊組EDl已經被分配給磁碟dl，d2，d4，d5...；數據對象D02的多個塊組ED2已經被分配給設備d2，d6...;並且D03的多個塊組ED3已經被分配給設備dl，d3，d4...。因此，對於三個不同編碼算法，產生的編碼數據可以存儲在磁碟池112中的相同或不同磁碟子組上。
[0065]圖2是舉例說明本發明的一個實施例的用於選擇擦除碼算法以及將編碼數據分配到磁碟存儲設備池中的磁碟存儲器的處理的流程圖。在202，處理開始於接收輸入數據對象(DO)。在204，所述處理從多個不同擦除碼算法(ECA1, ECA2, ECA3...)選擇一個用於產生所述DO的編碼數據。在206，選中的算法產生編碼數據ECdq,在208，所述處理將所述編碼數據ECiw分配給多個塊組(根據選中的EC算法所要求的)並從設備池的那些磁碟存儲器中選擇對應數目的磁碟存儲器。在210，產生的塊組被寫入所述選中的磁碟存儲設備，每個設備一個塊組。如果在步驟212存在其他輸入D0，所述處理返回到步驟202。否則所述處理結束。
[0066]根據本發明的各種實施例，選中的來編碼數據的所述擦除碼(EC)算法可以隨著不同輸入數據對象而不同。例如，在一天中在系統具有高利用率(例如，其容量的85%都在運行)的繁忙時期，存儲系統可以決定選擇較簡單的擦除碼來降低編碼數據所需的CPU時間。該權衡對驅動器失效有較小的容忍度。然而，在一天的晚些時候，例如在晚上，當CPU不繁忙的時候，存儲系統可以從存儲在池中的編碼數據檢索原始數據，使用不同的、更複雜的擦除碼重新計算原始數據然後儲存這些編碼數據以提高數據保護的級別。
[0067]在另一個情況中，決定使用哪一個擦除碼可以取決於接收數據的類型。例如，較大的數據對象可適應許多不同的擦除碼算法，均導致存儲空間的有效利用以及可接受的計算周期數目。作為選擇，較小的對象可以適應僅僅少數或不同類型的擦除碼算法。因此，基於輸入數據，存儲系統可以動態地確定使用哪一個擦除碼來對每個各自的輸入數據進行編碼。
[0068]舉例來說，圖3A-3F舉例說明使用不同的擦除碼算法來產生編碼數據，其中編碼數據然後能夠被存儲在磁碟存儲器設備的公共池上。
[0069]在這一系列的示例中，擦除碼類別被標記為「b的a」，其中「b」是編碼數據塊組要存儲在其上的磁碟存儲設備(例如驅動器)的數目，每一個設備一個塊組，以及「a」是那些為了再生原始數據而必須存在的設備的數目。圖3A-3B舉例說明示例A，其中EC類別4的2的算法用於編碼8KB大小的數據對象。圖3C-3D舉例說明示例B，其中EC類別6的4的算法用於編碼16KB大小的數據對象。圖3E-3F舉例說明示例C，其中EC類別10的8的算法用於編碼32KB大小的數據對象。算法能夠用於編碼其它大小的數據對象，例如，圖3C以及3E的表中示出的那些。[0070]圖3A-3B的示例A中，數據對象302在304由4的2的擦除算法編碼，並且編碼數據作為4個塊組306，分別分配到磁碟存儲池308中的4個磁碟驅動器dl，d2, d4和d6中的每一個。圖3B舉例說明編碼處理，其中X = 8KB大小的原始數據對象302被分為大小為X/8的8個元素，一起示為對象312。然後，8個元素與糾錯算法(根據EC算法)結合產生16個每個大小均為X/8的塊，一起示為對象314。16塊被分成4個每個大小均為X/2的塊組，該4個塊組被標記為316a、316b、316c以及316d。將不同的塊組分別發送給圖3A所示的池308中的選中的磁碟驅動器dl、d2、d4和d6中的每一個。編碼數據使用的總共存儲空間是16KB(表300)。這表示50%的效率(在16KB的總共存儲空間上存儲了 8KB大小的對象)。
[0071]比較起來，示例B使用6的4類別的算法來在24KB的總共存儲空間上編碼16KB大小的較大對象，達到67%的效率。作為選擇，更大的對象大小，例如32KB、64KB、128KB和256KB,能夠利用這種6的4算法編碼並產生圖3C的表格320所示的相似效率。在這特定的示例中，數據對象322在324由6的4算法編碼，並且產生的6個塊組326被存儲在與圖3A的4的2類別編碼數據使用的相同的池308中的任意六個磁碟驅動器上，這裡是dl、d2、d4、d5、d6和d7。圖3D舉例說明X = 16KB大小的數據對象322如何被分成16個X/16大小的元素，一起示為對象332。然後，332的16個元素被編碼為24個大小為X/16的相等大小的塊(包括糾錯元素)，一起示為對象324。然後該24塊被分成大小為X/4的6個相等大小的塊組，這裡表示為336&-乜並存儲在六個驅動器(11、(12、(14、(15、(16以及d7上。因此對於大小為16KB的對象的6的4編碼被存儲在24KB的總存儲空間中，達到67%的效率。此外，根據本發明，以該6的4的EC類別算法(不同於圖3A的算法類別)編碼的數據可以被存儲在與4的2類別算法(圖3A的)編碼的數據所存儲到的磁碟存儲池308中的相同的驅動器的所有或者一些上。
[0072]圖3E舉例說明示例C，其中使用10的8的EC類別算法來在40KB的總共存儲空間上編碼大小為32KB的對象，達到80%的效率。數據對象342在344由10的8的EC算法編碼並且被分成10個相等大小的塊組346，其被發送給池308中的10個磁碟驅動器(這裡是dl、d2、d3、d4、d5、d6、d7、d9、dl0 以及 dll)中的任何一個。如圖 3F 所示，X = 32KB 大小的數據對象342被分成32個X/32大小的元素，一起示為對象352。然後元素被編碼為40個大小為X/32的相等塊，包括糾錯碼，並一起示為對象354。然後將對象354分成10個相等大小的塊組，每個大小為X/8，顯示為塊組356a-j。再次，這些塊組被存儲在與圖3A，3C和3E示出的池308的相同磁碟驅動器的一些或者所有上。如表格340中所示，這些相同的10的8的EC算法可以用於編碼其他大小的數據。
[0073]B.位屏蔽分配和對準邊界的分配
[0074]現在將描述本發明的更多的【具體實施方式】，其中使用位屏蔽來分配編碼數據給一個或多個磁碟存儲設備中的多個，所述位分配碼用於沿著一個或者多個對準的邊界來分配以加快分配和恢復處理。
[0075]在一個示例中，基於被存儲在索引中的數據對象的數目(索引項的數目)和基於存儲索引的介質大小，最小的對象大小被選擇為4KB(即，索引項可以表示的最小數據的大小)。每個索引項具有指向磁碟上存儲有數據的物理位置的指針。指針不能表示小於4KB的數據。這裡，分配單元(最小數據大小請求)被選為與最小對象大小相同，即4KB。因此，如下所述，分配位屏蔽上的一位，以及每一個對應分配位圖和邊界位圖上的一位，表示4KB。
[0076]圖4A-4B舉例說明磁碟存儲池402的一個實施例，其包括六個磁碟驅動器404a_f。所述驅動器可以具有不同類型和大小。每個磁碟驅動器被分區，意味著每個磁碟驅動器被分為多個邏輯存儲單元，每個邏輯存儲單元被定義為一個分區406。跨驅動器404a-f延伸的分區組中的6個分區406a-f每個均有相同的大小，並且屬於一個邏輯存儲單元組408。在一個邏輯存儲單元中不可能有相同驅動器中的兩個分區。如下所述，分配位圖和邊界位圖被用於將擦除編碼數據分配到驅動器。
[0077]圖4B顯示圖4A的相同驅動器池402的更多細節，包括跨所有驅動器404a_f延伸的一個邏輯存儲單元(LSU)組408a的示意圖。LSU組408a包括多個分層的邏輯存儲單元412a-o，其中每個跨所述LSU組408a的所有驅動器(分區)延伸。LSU組408a的每個分區406a-f具有邏輯存儲單元412a-o的多個分層分區片段，所述分區中的每個LSU片段沿著初始分區邊界414和結束分區邊界416對準，將每個磁碟驅動器404a-f分別標記為414a_f和416a-f。每個分區406中的組408a的多個邏輯存儲單元大小相同，並顯示為一個堆疊在另一個的頂部。
[0078]通常，編碼數據可以如下被分配給單個邏輯存儲單元組。首先，數據進入，並被分解為對象(相同或可變的大小的數據段)，並且然後通常被散列。建立對象記錄，其中包含對象名(例如，散列)和對象大小。然後根據選擇的擦除碼將對象編碼，並且產生分配位屏蔽以向分配器(allocator)，例如參見圖1中的部件108，說明編碼對象必須被如何存儲。分配器在介質(例如磁碟存儲器)上尋找匹配位屏蔽的存儲空間。然後將數據寫出到該介質，並為索引中的那個對象在對象記錄中存儲指針。
[0079]通常，所述分配器在分配位屏蔽和分配位圖之間執行位對位的比較。存儲器系統使用單個分配位圖來記錄整個系統中的所有存儲器的狀態(可利用性)。位圖可以存儲在配置文件中。分配位屏蔽和分配位圖的比較可以被(抽象地)描述為:將位屏蔽在位圖上滑動直到所述位屏蔽中的模式匹配它下面的位圖。當發現匹配的時候，這標識了用於存儲所述數據的位置。然後將該位置存儲在索引的對象記錄中作為指針。在一個實施例中，分配位圖映射到邏輯地址空間，並且到編碼對象的指針是邏輯對象編號(LON)，其被存儲在索引中的對象記錄中。
[0080]圖5舉例說明根據本發明的在單個邏輯存儲單元上分配編碼數據的一個示例。在該示例中，分配位屏蔽502被提供給對象，用於在驅動器池(例如，圖1，3，4所示的池的類型)的24個驅動器上定位40KB的可用的存儲空間。32KB大小的數據對象是由10的8的擦除碼算法編碼的，產生10個相等大小的塊組，每個大小是4KB。這裡，分配位屏蔽502被示出具有24個分配片段(位)，所述邏輯存儲單元組中的24個驅動器中的每一個均有一位。開始10位(501)被設置為「0」，意味著需要(請求)他們在所述邏輯存儲單元組的任意10個連續驅動器上分配所述編碼數據(用於存儲10個編碼塊組，每個驅動器一個塊組)，其中連續意味著向後繞到下一個邏輯存儲單元(LSU)的第一個驅動器。例如，如果所述第一可用的塊是在LSUll的驅動器20上，那麼具有10個塊組的對象會通過將開始5個塊組放置在LSUll的驅動器20-25上來存儲，並且剩餘的5個塊組會繞回LSU12的驅動器I並且持續直到完全地存儲在LSU12的驅動器1-5上。與此相反，在圖5的示例中，第一可用塊與LSU組中的第一驅動器對準。剩餘14位(503)被標上X，意味著他們不被需要(不管他們是否處於空閒或不空閒)。通常，所述位屏蔽會被縮短(例如由於消耗更少存儲空間以及更少處理的原因)到所請求的「O」位的最短長度，在此例子中是10。產生的分配位圖504被示出在位屏蔽502下並與其對準。分配位圖的所述開始10位(505)被標上「1」，因此將該10個編碼的塊組給池中的開始10個驅動器的每個分配一個，同時不能夠用於存儲編碼數據的剩餘的14位(507)被標上「O」。這些位可以是O或者1，取決於他們是否被預先分配。在此情況下，他們設有被預先分配。在分配位圖504之下對準示出的邊界位圖506，相似地具有24個片段(位)，第一位(508)被標上「I」來表示所述編碼數據對象的第一塊被存儲在哪一個分區號碼(哪一個驅動器)上，這裡是LSU組的第一驅動器。
[0081 ] 根據這些編碼方案，整個或部分的邏輯存儲單元可以被立刻分配和寫入。此外，部分的邏輯存儲單元讀取是可能的，例如只讀取被請求的對象。
[0082]例如，可以將用於對象的起始塊(分配單元)連同對象的長度一起存儲在索引記錄中。這會提供定位(讀取)一個對象並且僅僅是那個對象所需要的所有信息。然而在某些情況下，對象大小超過分配位屏蔽的容量。對這個問題的一個解決方案通過圖6A-6C的編碼示例來舉例說明，其中希望在10的8的擦除碼的要求(10個驅動器)內編碼較大的對象(80KB)，以便每個驅動器必須保存8KB的數據。這是(在此例子中)預先確定的，即分配位屏蔽的每位只能夠表示4KB的數據。這個導致了選擇。
[0083]一種選擇是將對象大小限制為等於(分配的粒度)與(EC算法所要求的塊組數目)的乘積的數目。這將迫使大的對象，諸如在當前實施例中(80KB)，被編碼為兩個獨立的對象，兩個均落在不同的邏輯存儲單元組上或在相同邏輯存儲單元組上的邏輯存儲單元之間具有間隙。這種選擇比現有技術的只允許連續分配的分配方法仍舊更加靈活，而本發明的分配位屏蔽允許間隙並允許非連續的分配。
[0084]第二選擇，根據本發明的優選實施例，允許每一塊組具有多個分配位的一個請求。這個選擇在圖6A-6C中示例說明了。在圖6A中，每個塊組在所述分配位屏蔽中被分配了兩位，每個塊組的初始位是沿著相同邏輯存儲單元組中的兩個邏輯存儲單元615a、615b的公共邊界對準的。更一般來講，所述公共邊界可以是任意分區邊界，即，所述數據塊不必存儲在邏輯存儲單元組中第一驅動器上，而是可以起始於池中的任意驅動器來存儲。圖6A在中，分配位屏蔽602，用於一個分配80KB數據的對象，具有表示第一邏輯存儲單元601 (跨24個驅動器)的初始24位以及表示第二邏輯存儲單元603 (跨24個驅動器)的第二 24位。表示所述第一邏輯存儲單元的所述第一 24位的第一 10位(608)用陰影示出以將它們標記為被請求(必須處於空閒)，而接下來的14位(610)是無陰影的(不必處於空閒)。此夕卜，表示第二邏輯存儲單元的第二 24位的第一 10位(612)也被陰影示出(被請求處於空閒)，而接下來的14位(614)不被需要(並且在僅僅請求兩個邏輯存儲單元的此例子中是不相關的)。無陰影的位610是重要的，他們構成「間隙」，所述間隙利用一個請求使得所有80KB的數據能夠被分配到跨10個驅動器的兩個邏輯存儲單元上。
[0085]這裡，使用單個位屏蔽602來將單個對象存儲到80KB的總共存儲空間中，存儲的數據被分配成兩個相等的40KB部分608、612，其對準在所述邏輯存儲單元邊界615上。在第一邏輯存儲單元的分配片段1-1(K608)和第二邏輯存儲單元的分配片段1-1(Κ612)之間的分配位屏蔽中提供未分配「間隙」610的14個片段，使得能夠使用單個位屏蔽來將所述編碼數據分配到對準在公共邏輯存儲單元邊界615上的多個邏輯存儲單元。如前所述的，公共邊界可以是任意的分區邊界，不必是邏輯存儲單元邊界。
[0086]圖6B舉例說明產生的分配位圖604和邊界位圖606。分配位圖604相似地具有48個片段，第一 24個片段表示第一邏輯存儲單元601並且第二 24個片段表示所述第二邏輯存儲單元603。將在每個第一和第二邏輯存儲單元601、603中的所述第一 10個片段608、612分別分配給所述編碼對象數據的10個塊組(每個塊組2位)。邊界位圖606具有48個片段，第一片段625標記包含所述編碼對象的所述第一塊的磁碟存儲塊(第一邏輯存儲單元的第一塊)。
[0087]圖6C舉例說明如何將編碼數據的兩個相等大小為40KB的部分628、632以堆疊對準的形式對準在相同的分區(例如，邏輯存儲單元)邊界615上。圖6C是存儲在磁碟存儲器630上的編碼數據的視圖，其中每列都是驅動器，並且每行都是邏輯存儲單元。通過將編碼數據堆疊在公共邊界615上，這使得磁頭利用單個驅動頭搜索來訪問編碼數據的兩個邏輯存儲單元，即，單個頭可以在不違反擦除碼的需要的情況下，在多個邏輯存儲單元上訪問更大量的存儲數據。這提高了 I/O性能。在此例子中，如果兩個驅動器失效，可以利用8頭搜索再生所述編碼數據。相比之下，現有技術可能需要16頭搜索來再生數據。
[0088]上述示例舉例說明如何在不違反擦除碼要求的情況下，使用索引中的單個指針將單個對象跨多個邏輯存儲單元分配。分配位圖允許與分區邊界排列成行的未分配的間隙。此外允許在單個請求中編碼較大的對象。通過在邏輯存儲單元組中跨連續的分區以及連續的邏輯存儲單元放置單個對象，可以將編碼數據堆疊(平鋪)在一個或多個磁碟驅動器上。在圖6的示例中，一旦上一個驅動器被映射，便使用單個位屏蔽(請求)將來自每個驅動器的4KB塊連續地並且向後繞回地映射到第一驅動器。
[0089]更進一步講，根據本發明的一個實施例，可以將一個以上的數據對象放置在邏輯存儲單元，例如圖5中舉例說明的分配位屏蔽502上的剩餘14個驅動器，或圖6的分配位屏蔽上的剩餘14個驅動器，可以存儲其他數據對象。此外，可以通過多個不同的編碼算法來編碼邏輯存儲單元上的編碼數據。為了將對象存儲在該邏輯存儲單元組，唯一的要求是編碼算法所需要的驅動器數目小於或等於該邏輯存儲單元組中的分區。
[0090]在上述示例中的分配位圖為存儲編碼數據標記哪一個邏輯對象編號(LON)是可用的。邊界位圖標記包含編碼對象的第一塊的塊。邊界位圖用於將物理塊編號(PBN)反向映射到對象記錄。例如，如果磁碟驅動器失效，為了再生在磁碟驅動器失效的時候在所述驅動器上的數據，必須知道哪個對象塊組駐留在失效的驅動器上，以從編碼的數據中重新計算出丟失的數據。存在兩種方法來做這個:
[0091]I)針對所有具有屬於該失效驅動器的地址(L0N至LON+長度)的對象掃描所述索引；當發現一個對象滿足所述標準的時候，讀取剩餘的對象塊組，重新計算所述丟失的數據，並重寫所述丟失的塊組；或
[0092]2)針對覆蓋所述失效驅動器的對象邊界掃描所述分配和邊界位圖；當找到的時候，讀取所述剩餘對象塊組，重新計算所述丟失數據，並重寫所述丟失塊組。
[0093]方法I需要磁碟和索引操作兩者。方法2僅僅需要磁碟操作。
[0094]C.計算和存儲環境
[0095]先前描述的EC算法選擇和數據存儲分配方法可以在合適的計算和存儲環境中執行，例如，可以在於一個或多個計算機上運行的計算機可執行指令的環境中。在例如分布式計算環境中，由通過通信網絡連接的遠程處理設備執行某些任務，以及程序模塊可以位於本地和遠程存儲器存儲設備兩者中。通信網絡可以包括全局區域網絡，例如網際網路，區域網，廣域網或其它計算機網絡。將理解的是，此處所述的網絡連接是示例性的，並且可以使用其它在計算機之間建立通信的裝置。
[0096]計算機可以包括處理單元、系統存儲器和系統總線，其中系統總線耦合系統部件，包括但不限於系統存儲器和處理單元。計算機還包括磁碟驅動器和到外部部件的接口。各種計算機可讀介質可以由計算機訪問，並且包括易失的和非易失介質，可移除的和非可移除的介質。計算機可以包括各種用戶接口設備，包括顯示屏幕，觸控螢幕，鍵盤或滑鼠。
[0097]現在參見圖7，舉例說明了用於在計算機和多個磁碟存儲設備之間通信的通用系統配置700的一個示例。磁碟存儲器可以是各種存儲設備中的任一種，在所述存儲設備中數據是數位化地通過各種電子、磁、光或機械方法記錄在一個或者多個旋轉磁碟表面上的，包括硬碟驅動器，軟盤驅動器和光碟驅動器。CPU702被示出與系統存儲器704相連，並且系統總線706將CPU連接到晶片組708。晶片組經由IO總線710和多個IO插槽712被連接到各種輸入/輸出設備的任何一個，諸如用於連接多個磁碟驅動器716的驅動控制器。晶片組也可以與其它存儲設備718相連。所述晶片組可以包括一個或多個視頻埠 720，網絡埠 722，滑鼠埠 724，鍵盤埠 726等等。
[0098]以上所描述的包括本發明的示例。當然，為了描述本發明，不可能描述每個想得到的部件或方法的組合，但本領域普通技術人員將意識到的是本發明的進一步組合和置換是可能的。因此，本發明意在包含所有屬於本發明和/或權利要求書的這種交替、修改和變化。
【權利要求】
1.一種用於在存儲設備上定位數據的計算機執行的方法，包括計算機可執行的如下動作: 將由相同或不同擦除碼編碼的多個編碼數據對象分配到磁碟存儲設備池中的相同或不同設備以用於存儲； 對要存儲在多個邏輯存儲單元上的每個編碼對象，使用分配位屏蔽作為對於可用的分配單元的單個請求來將相應編碼對象存儲在所述多個邏輯存儲單元上，其中所述分配位屏蔽覆蓋所述多個邏輯存儲單元，並包括與被存儲的所述編碼對象的起始分區邊界對準的間隙。
2.如權利要求1所述的方法，其中: 所述分配步驟包括:在不同設備上分配所述編碼對象。
3.如權利要求2所述的方法， 所述分配步驟包括:分配由不同的擦除碼編碼的編碼對象。
4.如權利要求1所述的方法，其中: 所述分配步驟包括:分配 由不同的擦除碼編碼的編碼對象。
5.如權利要求1所述的方法，其中: 所述分配步驟包括:在相同邏輯存儲單元上分配多個編碼對象。
6.如權利要求1所述的方法，其中: 所述分配步驟包括:在相同邏輯存儲單元組上分配多個編碼對象。
7.如權利要求1所述的方法，包括: 使用所述分配位屏蔽來請求與邏輯存儲單元邊界對準的分配單元。
8.如權利要求1所述的方法，其中: 被編碼的數據的對象大小是固定的。
9.如權利要求1所述的方法，其中: 被編碼的數據的對象大小是可變的。
10.如權利要求1所述的方法，其中: 數據對象是由不同類別的擦除碼編碼的。
11.如權利要求1所述的方法，包括: 提供所述編碼數據對象的索引，其將每個編碼數據對象映射到其各自的擦除碼。
12.如權利要求1所述的方法，其中: 所述分配步驟包括:使用分配位圖標記所述可用的分配單元。
13.如權利要求12所述的方法，其中: 所述分配位圖映射到邏輯地址空間。
14.如權利要求13所述的方法，其中: 邏輯對象編號(LON)定義指向所述編碼對象的指針。
15.如權利要求1所述的方法，其中: 指向所述編碼對象的指針被存儲在索引記錄中。
16.如權利要求15所述的方法，其中: 所述索引記錄包括指向所述編碼對象的多個指針。
17.如權利要求12所述的方法，其中，所述分配步驟使用邊界位圖標記用於所述編碼對象的初始塊的分配單元。
18.一種計算機可讀介質，具有存儲在其上的指令，所述指令當被載入計算機的時候執行如權利要求1所述的方法步驟。
19.一種配置為執行如權利要求1所述的方法步驟的可編程邏輯。
20.一種數據存儲系統，包括: 擦除碼算法選擇部件，可操作為對不同的輸入數據對象選擇不同的擦除碼算法來產生編碼數據對象；以及 磁碟存儲分配部件，用於將由不同的算法編碼的所述編碼數據對象分配到磁碟存儲設備池中的相同或不同設備上的任何可用的分配單元。
21.如權利要求20所述的存儲系統，還包括: 用於存儲所述編碼數據的所述磁碟存儲設備池。
22.如權利要求20所述的存儲系統，其中: 所述磁碟存儲分配部件使用分配位屏蔽來為每個編碼數據對象請求可用的存儲單元以跨覆蓋所述池中的多個設備的邏輯存儲單元組的一個或者多個邏輯存儲單元存儲編碼對象，並且其中所述位屏蔽包括允許所述編碼對象被存儲到所述池中的至少一個設備上的多個邏輯存儲單元的 間隙。
23.如權利要求20所述的存儲系統，包括: 將每個編碼數據對象映射到其相應的擦除碼算法的所述編碼數據對象的索引。
24.一種在用於定位數據存儲的計算環境中的數據結構，包括分配位屏蔽以便請求可用的分配單元，以用於跨一個或者多個邏輯存儲單元存儲編碼對象，編碼數據對象以不同的擦除碼來被編碼，所述分配位屏蔽覆蓋跨多個磁碟驅動器的多個邏輯存儲單元，並且所述位屏蔽包括與被存儲的所述編碼對象的起始分區邊界對準的間隙，在此，所述可用的分配單元被跨多個邏輯存儲單元請求。
【文檔編號】G06F3/06GK104011642SQ201280057605
【公開日】2014年8月27日 申請日期:2012年11月21日 優先權日:2011年11月22日
【發明者】M·W·希利, D·科德拉, A·J·比弗森, S·巴格比 申請人:森普利維蒂公司