具有網絡服務客戶接口的分布式存儲系統的製作方法

2023-05-21 11:21:26

專利名稱：具有網絡服務客戶接口的分布式存儲系統的製作方法
技術領域：
本發明涉及數據存儲系統，尤其是涉及配置成提供對存儲器的訪問作 為網絡服務的存儲系統。
相關技術的描述
很多不同的計算應用依賴於用於持久存儲各種應用程式數據的一些 類型的存儲介質。例如，普通辦公應用程式和多媒體應用程式產生並使用 各種類型和格式的應用數據，例如其中包括文檔、電子表格、靜止的圖像、 音頻和視頻數據。經常地，這樣的數據被存儲，用於以用戶名義的重複的 訪問或使用。例如，用戶可能希望在一段時間內存儲和處理很多文檔或其 它數據，並可能期望在需要時數據以可預測的狀態可容易得到。
在傳統計算系統中，由應用程式用於持久的應用程式數據存儲的存儲 介質通常大部分為磁性固定的驅動器或"硬驅動器",雖然也可使用光和固態 存儲設備。這樣的設備集成在執行應用程式的計算機系統中或可通過本地 外圍接口或網絡訪問該系統。 一般來說，用作應用程式存儲的設備由管理 設備級行為的作業系統管理，以向需要存儲訪問的各種應用程式提供相容 的存儲接口，例如文件系統接口。
應用程式存儲的該常規模型呈現一些限制。首先，它通常限制應用程 序數據的可訪問性。例如，如果應用程式數據存儲在特定計算機系統的本 地硬驅動器上，它可能對在其它系統上執行的應用程式是不可訪問的。即 使數據存儲在網絡可訪問的設備上，在當前網絡外部的系統上執行的應用 程序可能不能訪問該設備。例如，由於安全原因，企業通常限制對其區域網(LAN )的訪問，以便企業外部的系統不能訪問企業內部的系統或資源。 因此，在可攜式設備(例如，筆記本或手持式計算機、個人數字助理、移 動電話設備等)上執行的應用程式可能經歷訪問持久地與固定的系統或網 絡關聯的數據的困難。
傳統的應用程式存儲模型還可能不能充分確保所存儲的數據的可靠 性。例如，傳統作業系統一般默認將應用程式數據的一個備份存儲在一個 存儲設備上，如果希望數據冗餘，則要求用戶或應用程式產生並管理其自 己的應用程式數據的備份。雖然個別存儲設備或第三方軟體可提供一些程 度的冗餘，但這些功能部件對應用程式可能不是始終如一地可得到的，因 為應用程式可得到的存儲資源可能在應用程式安裝中極大地變化。操作系 統作為媒介的傳統存儲模型還可能限制數據的交叉平臺可訪問性。例如， 不同的作業系統可以不同的、不兼容的格式存儲用於相同的應用程式的數 據，這可能使在一個平臺(例如，作業系統和基本的計算機系統硬體)上 執行的應用程式的用戶難以訪問通過在不同平臺上執行的應用程式存儲 的數據。

發明內容
公開了分布式基於網絡服務的存儲系統的不同實施方式。根據一個實 施方式，系統可包括配置成根據網絡服務協議來接收對數據對象的訪問的 客戶請求的網絡服務接口。對給定數據對象的訪問的給定客戶請求可包括 相應於給定數據對象的鍵值。系統還可包括配置成存儲數據對象的複本的 很多存儲節點，其中每個複本可通過相應的定位器值(locator value )訪問， 且其中每個定位器值在系統內是唯一的。系統可進一步包括配置成存儲每 個數據對象的相應的鍵映射項目的鍵映射實例，其中對於給定的數據對 象，相應的鍵映射項目包括鍵值和相應於給定數據對象的每個存儲的複本 的每個定位器值。系統還可包括配置成從網絡服務接口接收對數據對象的 訪問的客戶請求的協調器。響應於給定的客戶請求，協調器可配置成訪問 鍵映射實例，以識別相應於鍵值的一個或更多定位器值，並且對於特定的 定位器值，訪問相應的存儲節點以取回相應的複本。
14在系統的特定實現中，網絡服務接口可迸一步配置成根據網絡服務協 議來接收存儲數據對象的客戶請求，其中存儲特定數據對象的特定客戶請 求包括相應於特定數據對象的健值。協調器可進一步配置成從網絡服務接 口接收存儲數據對象的客戶請求，並響應於特定的客戶請求，協調器可配 置成將特定數據對象的一個或更多複本存儲到一個或更多相應的存儲節 點。響應於存儲特定數據對象的給定複本，給定的存儲節點可配置成將相 應於給定複本的定位器值返回到協調器。
附圖的簡要說明


圖1是示出用於向用戶提供存儲作為網絡服務的存儲模型的一個實施 方式的結構圖。
圖2是示出存儲服務系統體系結構的一個實施方式的結構圖。
圖3是示出存儲服務系統組件的物理部署的一個實施方式的結構圖。
圖4是示出存儲節點的一個實施方式的結構圖。
圖5是示出配置成組織存儲節點內的數據對象的數據結構的一個實施 方式的結構圖。
圖6是示出執行對象獲取操作的方法的一個實施方式的流程圖。 圖7是示出執行對象放置操作的方法的一個實施方式的流程圖。 圖8是示出執行對象釋放操作的方法的一個實施方式的流程圖。 圖9是示出重裝對象存儲空間的方法的一個實施方式的流程圖。 圖10是示出一組鍵映射實例數據結構的一個實施方式的結構圖。 圖IIA-D示出鍵映射實例的分級實現的一個實施方式。 圖12是概述鍵映射實例內分級層次間的關係的結構圖。 圖13是示出執行鍵映射項目放置操作的方法的一個實施方式的流程圖。
圖14是示出執行鍵映射項目獲取操作的方法的一個實施方式的流程
15圖。
圖15A是示出使用更新傳播來使鍵映射實例同步的方法的一個實施方 式的流程圖。
圖15B是示出使用反熵協議(anti-entr叩y protocol )來使鍵映射實例 同步的方法的一個實施方式的流程圖。
圖16是示出複製器鍵映射項目的一個實施方式的結構圖。
圖17示出不平衡索引數據結構的一個實施方式。
圖18示出用在不平衡索引數據結構中的索引節點的一個實施方式。
圖19示出分層索引數據結構的一個實施方式。
圖20是示出遍歷不平衡索引數據結構的方法的一個實施方式的流程圖。
圖21是示出處理FINGERPRINT反熵協議消息的方法的一個實施方 式的流程圖。
圖22是示出處理FILTER反熵協議消息的方法的一個實施方式的流程圖。
圖23示出發現和故障檢測監控進程(DFDD )的一個實施方式。
圖24示出可由DFDD實例維持的全局操作狀態機的一個實施方式。
圖25是示出根據基於閒聊(gossip-based )的協議使DFDD實例同步 的方法的一個實施方式的流程圖。
圖26是示出在存儲服務系統內的存儲類的操作的方法的一個實施方 式的流程圖。
圖27是示出根據存儲節點的當前狀態信息動態地確定用於存儲數據 對象的一個或更多複本的寫入計劃的一個實施方式的流程圖。
圖28是示出動態地確定關於對象的寫入計劃的一個實施方式的流程 圖，該對象的一個或更多複本已被存儲在存儲節點中間。
圖29是示出計算機系統的示例性實施方式的流程圖。
16雖然本發明易受各種更改和可選形式的影響，但是其具體的實施方式 作為例子在附圖中示出並將在這裡被詳細描述。然而應理解，附圖和對其 的詳細描述不是用來將本發明限制到所公開的特定形式，而是相反，本發 明包括落在如所附權利要求界定的本發明的實質和範圍內的所有更改、等 效物和可選方案。
實施方式的詳細說明
介紹
當計算應用程式變成更加數據密集的以及地理上分散的時，對應用程 序數據的可靠、與位置無關的訪問的需要便增加了。例如，多媒體應用程 序如授權、存儲和重放應用程式要求當多媒體內容的質量和數量提高時逐 步增加數據存儲的量。進一步地，可能期望從不同位置訪問應用程式數據， 而不考慮存儲數據的設備的位置如何。例如，雖然很多計算機包括相當數 量的基於磁碟的存儲器，但是以統一和方便的方式遠程訪問這樣的存儲器 呈現出技術上和安全性上的困難。
與配置各個計算機以完全依賴於其自己的內部存儲資源或提供基於
區域網的存儲資源(例如，網絡附屬存儲(NAS 、存儲區域網絡(SAN ) 等)相反，連接網際網路的數據存儲服務可配置成通過基於網際網路的協議例 如網絡服務(WS )協議向客戶提供一般存儲服務。基於網際網路的協議例 如網絡服務協議一般是獨立於平臺的，因為它們一般獨立於基本的軟體或 硬體起作用。因此，提供數據存儲能力作為網絡服務可提供不依賴於在應 用程序主機系統內或區域網上實現的存儲資源而對任意數量的存儲的很 多不同類型的應用程式直接訪問。此外，通常可從提供網際網路接入的任何 位置訪問網絡服務可訪問的存儲器。網絡服務可訪問的存儲器可促進很多 不同計算功能部件的實現，例如通過不同設備或應用程式對公用數據的遠 程訪問、在執行期間通過各個應用程式對廣泛分布的數據的遠程訪問、在 協作工作的分布的用戶中間對數據的訪問和/或共享、在分布的用戶中間對 應用程式結果數據的分發，以及很多其它類似的功能部件。在下面的討論中，描述了可用在基於網絡服務的存儲系統中的可能的 數據存儲模型的一個實施方式。此後，公開了根據該數據存儲模型可配置 成提供存儲服務的存儲服務系統，並詳細描述了其各個組件。
存儲服務用戶接口和存儲模型的概述
用於向用戶提供數據存儲作為服務例如網絡服務的存儲模型的一個
實施方式在圖1中示出。在所示模型中，存儲服務接口 10設置為到存儲 服務的面向顧客或用戶的接口。根據通過接口 10呈現給用戶的模型，存 儲服務可組織為可通過接口 10訪問的任意數量的存儲桶20a-n。每個存儲 桶20可配置成存儲任意數量的對象30a-n ,對象30又可存儲由存儲服務 的用戶指定的數據。
如下面更詳細描述的，在一些實施方式中，存儲服務接口 10可配置 成根據網絡服務模型支持存儲服務及其用戶之間的交互作用。例如，在一 個實施方式中，接口 10可作為具有統一資源定位器(URL ),例如 http:〃storageservice.domain.com的網絡服務端點而被客戶訪問，由服務客戶 產生的網絡服務請求可被指引到該URL而進行處理。 一般而言，網絡服務 可指發出請求的客戶通過請求接口可得到的任何類型的計算服務，該請求 接口包括一個或更多基於網際網路的應用層數據傳輸協議，例如超文本傳輸 協議(HTTP )的一種版本或另外的適當協議。
網絡服務可使用各種授權服務協議以各種體系結構形式實現。例如， 在具象狀態傳輸(REST )形式的網絡服務體系結構中，與網絡服務請求有 關的參數(例如，指定所請求的服務的類型、用戶證書、將對其進行操作 的用戶數據等)可被指定為將網絡服務請求調用到網絡服務端點的數據傳 輸命令的參數，該數據傳輸命令例如HTTP GET或PUT命令。在_些實 現中，REST形式的網絡服務體系結構是無狀態的，因為每個網絡服務請 求可包括處理該請求的所有信息而不參考外部狀態信息。與REST形式的 網絡服務體系結構相反，基於文檔或墓於消息的網絡服務體系結構可將與 網絡服務請求有關的參數和數據編碼為可被傳輸到網絡服務端點並接著 被該端點解碼和作用的文檔。例如，可擴展標記語言(XML )的一種版本 或另外的適當標記語言可用于格式化網絡服務請求文檔。在一些實施方式中，用于格式化請求文檔的標記語言可為控制請求的處理的參數定界，而 在其它實施方式中，標記語言本身的某些功能部件(例如，某些標誌)可 直接控制請求處理的方面。此外，在一些實施方式中，最終的文檔可封裝
在另一協議例如簡單對象訪問協議(SOAP )的一種版本內，例如以便促 進端點對網絡服務請求的處理。
其它協議也可用在網絡服務體系結構的不同實施方式中。例如，網絡 服務描述語言(WSDL )的一種版本可被網絡服務端點用於向可能的客戶 公布其接口技術要求。網絡服務端點可通過目錄協議例如統一描述、發現 和集成(UDDI )協議的一種版本來使自己被可能的客戶識別。與通過網 絡服務接口提供計算服務有關的很多其它類型的協議可能存在，且任何給 定的網絡服務實現可使用這樣的協議的任何適當的組合。
可以設想，在一些實施方式中，接口 10可支持不同於網絡服務接口 的、代替網絡服務接口的或除了網絡服務接口外的接口。例如，企業可實 現企業外部的客戶以及企業內部的用戶使用的存儲服務，其中企業外部的 客戶可通過網絡服務協議訪問服務，企業內部的用戶可使用不同類型的接 口 (例如，對企業的內聯網定製的專用接口 )o在一些實施方式中，接口 10可支持各種類型的接口連接協議中的每一個，存儲服務的任何用戶可通 過這些協議訪問服務。在其它實施方式中，可為每個不同的接口方案提供 接口 IO的不同實例。注意，在一些實施方式中，與處理與客戶的交互(例 如，接收和響應服務請求)有關的接口 10的那些方面可與實現存儲服務 一般體系結構的那些方面(例如，進入存儲桶和對象的層中的服務的組織) 分開地實現。在一些這樣的實施方式中，與客戶交互作用(例如，通過網 絡服務協議)有關的接口 10的部分可能被某些用戶例如企業內部的那些 用戶繞過，如下面結合圖2的描述較詳細描述的。
如圖1所示，接口 10給存儲服務用戶提供對存儲桶20的訪問。 一般 而言，存儲桶20可用作與存儲服務的用戶關聯的對象命名空間的根。例 如，存儲桶20可能類似於文件系統目錄或文件夾。在一些實施方式中， 各個存儲桶20還可形成用於解釋存儲服務的使用的基礎。例如，用戶可 與一個或更多用於記帳目的的存儲桶20關聯，且該用戶可使用存儲資源
19(例如對象30的存儲)而被開帳單，其中的存儲資源分級地駐留在由那 些存儲桶20建立的命名空間內。
在所示實施方式中，每個存儲桶20a-n包括相關的元數據21a-n以及 相應的訪問策略23a-n。 一般而言，元數據21可包括可用於描述給定存儲 桶20的方面或特性的任何適當的元數據。例如，元數據21可包括識別存 儲桶創建的日期、其創建者的身份的信息或其它適當的信息，而不管存儲 桶是否具有任何與其相關聯的對象30。在一些實施方式中，元數據21可
包括指示存儲桶20的使用特徵的信息，例如與存儲桶20關聯的對象30 的總大小、關於存儲桶20和/或其相關聯的對象30的用戶的訪問歷史紀錄、 與存儲桶20相關聯的記帳歷史紀錄、或與存儲桶20的當前或過去使用有 關的任何其它適當的信息。在一個實施方式中，每個桶20可與相應的唯 一標識符關聯，該標識符可由用戶指定或被存儲服務自動分配。唯一的標 識符可存儲在元數據21中或作為存儲桶20的單獨的特性或欄位。注意， 在一些實施方式中，給定存儲桶20可不包括顯式引用、指針或相應於與 給定存儲桶20關聯的對象30的其它信息。更確切地，如下面更詳細描述 的，對象30的定位和選擇可通過使用在這裡稱為鍵映射的單獨的映射程 序(mapping facility )來執行。
訪問策略23可包括控制對與存儲桶20關聯的對象30的訪問所需的 任何信息。訪問策略23可包括識別被允許訪問存儲桶20及其相關聯的對 象30的客戶以及在什麼容量內的信息。例如，訪問策略23可存儲一個或 更多客戶的用戶標識符和/或認證證書(例如，口令)，並可進一步指定給 定客戶是否被允許修改或僅僅讀取對象30。訪問策略23還可實現默認的 或面向組的策略(例如，通過對指定的客戶或客戶組允許對對象30的一 般讀取訪問但限制寫入訪問)或任何其它期望的安全模型。
在所示實施方式中，給定存儲桶20可與一個或更多對象30關聯，其 中每個對象都包括各自的元數據31和數據33。 一般而言，對象30的數據 33可相應於任何比特序列。由存儲在對象30內的比特表示的數據的類型 對存儲服務來說可以是透明的。也就是說，比特可表示文本數據、可執行 的程序代碼、音頻、視頻或圖像數據或任何其它類型的數字數據，而存儲服務可不必在存儲和操作對象30時在這些不同的數據類型中間進行區分。 在一些實施方式中，可將數據33的大小限制為固定的最高限度(例如，1 千兆字節(GB))，而在其它實施方式中，可允許對象30僅僅以存儲服務 可用的物理存儲資源為條件來在大小上按比例變化。
類似於與存儲桶21相關的元數據21 ，元數據31可配置成存儲關於其 相應的對象30的任何期望的描述性信息。例如，元數據31可包括關於相 應的對象30被創建的日期和/或時間、對象30的大小、被對象30存儲的 數據33的類型(例如，由多用途網際網路郵件擴充(MIME )標準定義的數 據類型)的信息或任何其它類型的描述性信息。在一些實施方式中，元數 據31可儲存指示與相應的對象30的用戶交互作用的使用或歷史紀錄信 息，以及訪問策略信息(例如，指示不同用戶可具有的對對象30的訪問 的類型的許可信息X對象費用信息(例如，與對象30關聯的開單率或歷 史紀錄)，或屬於對象30的任何其它適當的信息或信息類型的組合。在一 些實例中，客戶可提供元數據連同將被存儲為元數據31的對象數據，而 在其它情況下，元數據31可包括由管理存儲服務功能部件的系統(例如， 在圖2中示出和在下面描述的存儲服務系統)產生的元數據。具有對對象 30的訪問權限的客戶可訪問元數據31中的一些、全部或根本不能訪問元 數據31 ，這取決於元數據的類型、客戶訪問權限的特定規定或其它適當的 因素。
在一個實施方式中，可使用兩個不同的信息項一鍵或定位器中的任一 項來在存儲服務系統內識別各個對象30。 一般而言，雖然鍵和定位器可以 不同的方式被解釋，但是鍵和定位器每個可包括在存儲服務系統的命名空 間的環境內作為整體被解釋的字母數字字符串或其它類型的符號。在一個 實施方式中，鍵可在相應的對象30在特定的存儲桶20內被創建時由客戶 指定(例如，響應於客戶存儲新對象的請求 如果沒有鍵被用戶指定， 則鍵可由存儲服務系統分配給新對象30。在這樣的實施方式中，可能要求 與特定存儲桶20的對象30關聯的每個相應的鍵在該存儲桶20的命名空 間內是唯一的。 一般而言，只要相應的對象存在於存儲服務系統內，鍵就 可作為有效的標識符繼續存在，客戶可通過該標識符可訪問相應的對象30。
在給定存儲桶20內，鍵可用於產生與傳統作業系統的文件系統共用 的文件目錄或文件夾命名空間類似的分層對象命名空間。例如，可準予客 戶對具有唯一標識符050739517的特定存儲桶20的對象讀取和寫入訪問 權限。在一個實施方式中，客戶可接著發出對地址 http:〃storageservice.domain.com/050739717的網絡服務請求，以便在存儲桶 命名空間內產生相應於存儲桶內對象的鍵。例如，客戶可指定使用鍵"My Document/Email/message.txt"在此特定的存儲桶內創建對象30 ，以便可使用 對 地 址 http:〃storageservice.domain.com/050739717/My
Document/Email/message.txt的網絡服務請求來訪問對象30。
注意，在一些實施方式中，鍵所隱含的分層結構可不必在對象存儲的 下面的等級中反映。例如，在一個實施方式中，與給定存儲桶20關聯的 對象30可以展開的、非分等級的方式存儲在存儲服務系統中，即使與對 象30關聯的鍵可隱含等級也是如此。也就是說，在這樣的實施方式中， 存儲桶20可不分等級地包括其它存儲桶20。然而，在其它實施方式中， 可支持存儲桶20在其它存儲桶20內的分等級包含，雖然存儲桶的任何這 樣的層次不需要直接映射到被對象鍵隱含的層次上。
在一個實施方式中，在取回或修改被請求的對象30的基本數據33之 前，被鍵識別的、客戶訪問對象30的請求可經歷客戶身份驗證程序、訪 問控制檢查，和/或映射過程(例如下面更詳細描述的)b例如，可請求客 戶提供口令或其它證書以證明客戶的身份，且一旦被識別，就可評估與被 請求的存儲桶20相關的訪問控制參數以確定識別的客戶是否被充分給予 特權來保證對被請求的鍵的訪問。相反，存儲服務系統可支持通過定位器 而不是鍵來訪問對象30的可選方法。 一般而言，定位器可表示在存儲服 務系統已知的所有對象30中間對象30的全局唯一的標識符。也就是說， 當鍵對與特定存儲桶20關聯的命名空間可能是唯一的時，定位器在所有 存儲桶20中的所有對象30的全局命名空間內可能是唯一的。例如，定位 器可包括由存儲服務系統產生的在其它定位器中唯一的字母數字字符串。 如下面更詳細描述的，在一些實施方式中，對象30的多個實例可在用於實現存儲服務系統的整個物理存儲設備中被複製，例如以增加數據冗餘和
容錯能力。在這樣的實施方式中，對給定的對象30的每個複製的實例可 存在唯一的定位器。
注意，雖然在一些實施方式中，只要對象30存在於存儲服務系統中， 就可保證鍵保持有效以訪問該對象30 ，但是這樣的保證可能適用或可能不 適用於該對象30的任何給定的定位器。例如，如果對象30的複製的實例 (或複本)移到不同的物理存儲位置(例如，由於其基本存儲介質的故障 或更換)，則涉及該特定實例的定位器可能不再是有效的，雖然在其新位 置可產生並使用相應於對象30的移動的實例的另一定位器。在下面關於 鍵映射系統組件的操作的討論中給出了對鍵和定位器之間關係的更多細 節。
作為基於鍵的對象訪問與基於定位器的對象訪問相比的例子，被上面 給 定 的 鍵 http:〃storageservice.domain.com/050739717/My Document/Email/message.txt定位的對象30可具有存儲在存儲服務系統內 的一個或更多實例，其中之一可由格式
http:〃storageservice.domain.com/3859C89A208FDB5A
的定位器識別。在此特定的實施方式中，注意，相對於特定的存儲桶20 來表示對象30的鍵參考，而定位器參考被表示為全局定位器空間內的絕 對128位的十六進位數字(雖然可使用其它類型的定位器編碼或格式)b 在一個實施方式中，客戶發出的指向定位器的網絡服務請求可繞過身份驗 證、訪問權限、翻譯或可適用於基於鍵的網絡服務請求的其它步驟中的一 些或全部。由於較少層的處理，在一些這樣的實施方式中，基於定位器的 請求可比基於鍵的請求被更快得處理。然而，因為對基於定位器的請求可 繞過安全措施，因此客戶可能需要提供敏感對象30的定位器不受到危害 的其自己的保證(例如，使用傳送和接收定位器所採用的加密或其它安全 方法)b進一步地，因為可能不能保證定位器的持久性(例如，在上面討 論的對象實例移動的情況下)，選擇執行基於定位器的對象訪問的客戶可 能需要容許定位器在使用期間變得無效的可能性，例如，通過在優先的基 礎上獲得新定位器或相應於發現現有的定位器不再有效。
23根據客戶的存儲需要和上面提到的資格證明(caveat ),基於定位器的 訪問相對於基於鍵的訪問可提供改進的處理性能(例如，網絡服務請求處 理的等待時間和總處理能力中的處理性能)b例如，客戶可選擇使用基於 定位器的訪問來參考不是特別敏感的頻繁訪問的對象30(例如，參考材料、 圖像或其它適當類型的數據)b注意，在一些實施方式中，基於定位器的 訪問可在各個對象30的基礎上被禁止，因而迫使希望訪問這樣的對象的 客戶使用基於鍵的請求並相應地提交到與這樣的請求關聯的任何驗證和 訪問權限控制。然而，即使對於基於定位器的訪問被啟用的對象30來說， 不擁有有效定位器的惡意或誤操作的客戶可能只有成功訪問任何給定對 象30的隨機的機會。通過使用較大的定位器命名空間、用於產生定位器 的安全技術(例如，對象數據的安全散列的使用)或其它適當的技術，就 可能使得這樣的機會在任意情況下都不可能。
存儲系統體系結構和實現
在圖2中示出了可配置成實現如圖1所示的基於網絡服務的存儲服務 的存儲服務系統體系結構的一個實施方式。在所示實施方式中，很多存儲 客戶50a-n可配置成通過網絡60與網絡服務平臺IOO進行交互作用。網絡 服務平臺100可配置成與存儲服務協調器120 (或簡單地，協調器120 ) 的一個或更多實例通過接口連接，協調器120又可與一個或更多鍵映射實 例140和位存儲(bitstore )節點160通過接口連接。此外，複製器180還 可配置成與位存儲節點160以及複製器鍵映射實例190通過接口連接。協 調器120和複製器180都可與節點揀取器(nodepicker )服務130通過接口 連接。在所示實施方式中，節點揀取器130、鍵映射140、位存儲節點160 和複製器鍵映射190的每個實例都可與發現和故障檢測監控進程(DFDD ) 110的相應實例關聯。注意，在給定組件的一個或更多實例可能存在的場 合，在下文中可以單數或複數形式對該組件進行引用。然而，任一種形式 的使用不是用來排除另一種。
在不同實施方式中，圖2中示出的組件可直接在計算機硬體中實現為 可直接或間接地被計算機硬體(例如，微處理器或計算機系統)執行的指 令或這些技術的組合。例如，圖2的組件可通過包括很多計算節點(或簡單地，節點)的分布式系統實現，例如在圖29中示出和下面描述的計算 機系統實施方式。在不同實施方式中，給定存儲服務系統組件的功能可通 過特定的節點或分布式跨越的一些節點實現。在一些實施方式中，給定節 點可實現多於一個的存儲服務系統組件的功能。在圖2的組件的一般功能 和如圖3所示的存儲服務系統的示例性物理配置的概述之後，下面結合圖 4-28的描述提供了特定存儲系統組件的某些實施方式的細節。
一般而言，存儲客戶50可包括可配置成通過網絡60向網絡服務平臺 100提交網絡服務請求的任何類型的客戶。例如，給定存儲客戶50可包括 網絡瀏覽器的適當版本，或配置成作為對網絡瀏覽器提供的執行環境的擴 展來執行或在網絡瀏覽器提供的執行環境內執行的插入模塊或其它類型 的代碼模塊。可選地，存儲客戶50可包括應用程式，例如資料庫應用程 序、媒體應用程式、辦公應用程式或可利用持久的存儲資源的任何其它應 用程序。在一些實施方式中，這樣的應用程式可包括用於產生和處理網絡 服務請求的足夠的協議支持(例如，對於超文本傳輸協議(HTTP )的適 當版本)，而不必實現對所有類型的基於網絡的數據的完全的瀏覽器支持。 也就是說，存儲客戶50可用是配置成直接與網絡服務平臺交互的應用程 序。如下所述，存儲客戶50可配置成根據具象狀態傳輸(REST 〉形式的 網絡服務體系結構、基於文檔或消息的網絡服務體系結構或另一種適當的 網絡服務體系結構來產生網絡服務請求。
在其它實施方式中，存儲客戶50可配置成以對其它應用程式透明的
方式來向那些應用程式提供對基於網絡服務的存儲的訪問。例如，存儲客
戶50可配置成根據上面描述的存儲模型的適當變形來與作業系統或文件 系統結合以提供存儲。然而，作業系統或文件系統可向應用程式提供不同
的存儲接口 ，例如文件、目錄和/或文件夾的傳統文件系統層次。在這樣的 實施方式中，應用程式可能不需要修改成利用圖1的存儲系統服務模型。 替代地，網絡服務平臺100的接口連接的細節可通過存儲客戶50和代表 在作業系統環境內執行的應用程式的作業系統或文件系統來協調。
存儲客戶50可通過網絡60將網絡服務請求傳送到網絡服務平臺100 並從網絡服務平臺100接收應答。在不同實施方式中，網絡60可包含建立客戶50和平臺100之間的基於網絡的通信所必需的聯網硬體和協議的 任何適當組合。例如，網絡60可通常包含共同實現網際網路的各種電信網 絡和服務供應商。網絡60還可包括專用網絡，例如區域網(LAN )或廣 域網(WAN )以及公共或專用無線網絡。例如，給定客戶50和網絡服務 平臺100可分別在具有其自己的內部網絡的企業內被提供。在這樣的實施 方式中，網絡60可包括建立給定客戶50和網際網路之間以及網際網路和網絡 服務平臺IOO之間的網絡連結所必需的硬體(例如，數據機、路由器、 交換機、負載平衡器、代理伺服器等)和軟體(例如，協議堆棧、帳目管 理軟體、防火牆/安全軟體等注意，在一些實施方式中，存儲客戶50可 使用專用網絡而不是公共網際網路來與網絡服務平臺100通信。例如，客戶 50可在作為存儲服務系統的同一企業內被提供服務。在這樣的情況下，客 戶50可完全通過專用網絡60 (例如，可使用基於網際網路的通信協議但不 可公開訪問的LAN或WAN )來與平臺100通信。
一般而言，網絡服務平臺IOO可配置成實現一個或更多服務端點，這 些服務端點配置成接收並處理網絡服務請求，例如訪問由存儲服務系統存 儲的對象30的請求。例如，網絡服務平臺100可包括配置成實現在前面 例子中使用的端點http:〃storageservice.domain.com的硬體和/或軟體，以便 指向該端點的基於HTTP的網絡服務請求被正確接收和處理。在一個實施 方式中，網絡服務平臺100可實現為伺服器系統，該伺服器系統配置成從 客戶50接收網絡服務請求並將它們轉發到協調器120或存儲服務系統的 其它組件用於進行處理。在其它實施方式中，網絡服務平臺100可配置為 實現負載平衡和其它請求管理功能部件的很多不同的系統(例如，在群集 拓撲中)，這些請求管理功能部件配置成動態地管理處理負載的大規模網 絡服務請求。
在不同實施方式中，網絡服務平臺100可配置成支持REST形式或基 於文檔(例如，基於SOAP )類型的網絡服務請求，如上面詳細描述的。 在一個特定的實施方式中，平臺100可配置成實現特定的網絡服務應用程 序編程接口 ( API )，其支持對由存儲服務系統管理的實體的各種操作。例 如，由平臺100實現的API可支持對存儲桶或對象的基本客戶操作，包括
26列表(可選地根據過濾模式或標準過濾的)存儲桶20或對象30、取回存 儲桶20或對象30的數據或元數據、以及創建或刪除存儲桶20或對象30。 在一些實施方式中，API可支持更複雜的客戶操作，例如對多個存儲桶20 或對象30的操作的批應用。
除了用作客戶網絡服務請求的可尋址的端點以外，在一些實施方式 中，網絡服務平臺100可實現各種客戶管理功能部件。例如，平臺100可 例如通過跟蹤請求的客戶50的身份、客戶請求的數量和/或頻率、代表客 戶50存儲或取回的對象30的大小、被客戶50使用的總存儲帶寬、被客 戶50請求的存儲類，或任何其它可測量的客戶使用參數，來協調網絡服 務包括存儲資源的客戶使用的記錄和帳目管理。平臺IOO還可實現財務帳 目管理和記帳系統，或可維護可被用於客戶使用行為的報告和記帳的外部 系統詢問和處理的使用數據的資料庫。
在某些實施方式中，平臺100可配置成收集和/或監控各種存儲服務系 統操作度量，例如反映從客戶50接收的請求的速率和類型的度量、這樣 的請求所利用的帶寬、對這樣的請求的系統處理等待時間、系統組件利用 (例如，在存儲服務系統內的網絡帶寬和/或存儲利用X由請求產生的錯 誤率和錯誤類型、被請求的對象30的特點(例如，大小、數據類型等) 或任何其它適當的度量。在這樣的實施方式中，平臺IOO可配置成集合地 收集這樣的度量，例如作為隨著時間的平均值，或作為可進行各種分析的 特定數據點。在不同實施方式中，這樣的度量可用來以對客戶50可見或 不可見的方式檢驗或監控系統性能。例如，在一個實施方式中，這樣的度 量可被系統管理員用於調整和維護系統組件，而在其它實施方式中，這樣 的度量(或這樣的度量的相關部分)可暴露給客戶50 ,以使這樣的客戶能 夠監控其對存儲服務系統的使用。
在一些實施方式中，平臺IOO還可實現用戶身份驗證和訪問控制程序。 例如，對於對訪問與給定存儲桶20關聯的特定對象30的給定網絡服務請 求，平臺100可配置成確定與該請求關聯的客戶50是否被授權訪問給定 存儲桶20和特定的對象30。平臺100可通過例如對照與給定存儲桶20關 聯的證書評估身份、口令或其它證書，並對照指定對特定對象30的可允許操作的訪問控制列表評估對特定對象30的請求的訪問，來確定這樣的 授權。如果客戶50沒有足夠的證書來訪問存儲桶50或對對象30執行請 求操作(例如，客戶50試圖寫入對象30 ,而只具有讀取訪問特權)，則平 臺100可例如通過向請求的客戶50返回指示錯誤情況的應答來拒絕相應 的網絡服務請求。可以設想，在一些實施方式中，每個存儲桶20和對象 30可具有管理對該存儲桶或對象的訪問的相關聯的訪問控制策略。這樣的 訪問控制策略可作為元數據21或31內的訪問控制信息的記錄或列表被存 儲，或作為與元數據21和31不同的數據結構被存儲。
然而在一些實施方式中，存儲服務系統例如圖2的系統可支持任意大 小的對象30 ,在其它實施方式中，對象30可限制到某種最大大小，該最 大大小也稱為塊大小(chunk size )的確定的最大大小。在一些這樣的實施 方式中，當客戶提供將與鍵關聯存儲的數據且該數據超過塊大小時，平臺 100可配置成根據塊大小將數據分成兩個或更多塊。在一個實施方式中， 平臺100可配置成將每個塊生成為具有相關聯的鍵值的相應的對象30。平 臺IOO可為每個塊生成鍵值作為客戶提供的鍵的函數，這樣當執行涉及客 戶提供的鍵的訪問請求時，原始的客戶數據可由塊重建。例如，平臺100 可配置成由客戶數據產生N個塊，並可通過將N個不同的模式(pattern) 附加到客戶提供的鍵來為這些塊產生N個相應的鍵，其中N個不同的模式 以N個塊被產生的相同順序被按字母順序式地排序。接著N個塊中的每個 都可使用下面描述的技術作為不同的對象30來管理，且原始數據可通過 列出具有鍵值的所有對象30並以列出的順序取回那些對象來重新產生，
其中對於該鍵值客戶提供的鍵是前綴。在一些實施方式中，可訪問、修改 或移除單獨的塊而不幹擾其它塊，相對於將數據管理為單個大的對象30
來說這可提高系統性能。可以設想，在一些實施方式中，可允許客戶50 指定器所提供的數據對象是否應被分割成塊。
如同在圖2中示出的很多存儲服務系統組件的情況一樣，將網絡服務 平臺100的功能從其它組件分離可改善存儲服務系統的維護和總的可縮放 性。例如，可特別提供附加的硬體和軟體資源來用於管理獨立於分配給其 它任務的資源的附加的網絡服務處理負載。進一步地，與平臺100關聯的任何資源故障的影響可被限制到該特定的功能區域，因而便於故障的隔離
和解決。然而，在一些實施方式中，可以設想，平臺IOO的功能可合併到 其它組件中。例如，協調器120可配置成包括與平臺100關聯的任務。
還注意到，雖然網絡服務平臺100可表示主要接口 ，客戶50可通過 該接口訪問存儲服務系統的功能部件，它不需要表示到這樣的功能部件的 唯一接口。例如，在一些實施方式中，協調器120可配置成支持與網絡服 務接口不同的供替換的API。這樣的供替換的API可例如用於允許提供存 儲服務系統的企業內部的客戶繞過網絡服務平臺100。在一些情況下，平 臺100的帳目管理和/或證書管理服務對內部客戶例如管理客戶可能是不 必要的。
協調器120可配置成協調網絡服務平臺100和存儲服務系統的其它組 件之間的行為。在一些實施方式中，協調器120的主要職責可包括響應於 指向對象30的網絡服務請求，來指導對那些對象30的對象數據33和元 數據31的讀取和寫入行為。例如，如下面更詳細描述的，對象讀取訪問 可包括執行對鍵映射實例140的訪問，以取回指示存儲有給定對象30的 複本的位存儲節點160的定位器，後面是執行對特定位存儲節點160的訪 問以便讀取被請求的數據。類似地，對象創建或修改可包括將對象30的 多個複本存儲到不同的位存儲節點160 ，且如果必要則更新鍵映射實例 140 ，以反映所創建或修改的複本的定位器。在一些實施方式中，協調器 120可配置成對鍵實例140和位存儲節點160執行這些讀取和寫入操作。 然而，注意，在某些實施方式中，協調器120可不操作來在對象30創建 和修改時創建對象30的全部數量的期望複本。如下面更詳細描述的，在 一些實施方式中，當協調器120完成了寫入對象30的確定數量的複本(例 如，兩個複本)時，該對象30的寫入操作可被考慮為結束。該對象30的 另外的複製物可作為通過複製器180的帶外或異步操作來完成。也就是說， 在這樣的實施方式中，對象創建或修改操作的帶內或同步部分可包括產生 少於總期望數量的被影響的對象30的複本。注意，雖然協調器120被示 為與鍵映射實例140、位存儲節點160和其它系統組件不同的組件，但是 在一些實施方式中有可能協調器120的實例與另一系統組件(例如，作為由單個計算機系統執行的軟體組件) 一起實現。因此，雖然這裡的描述可
指將數據存儲到或取自於位存儲節點160、鍵映射實例140或另外的組件 的協調器120 ，但是應理解在一些實施方式中，這樣的處理可出現在共享 的計算系統資源中。
如上面關於圖1描述的，在一些實施方式中，存儲服務系統可包括基 於存儲桶的存儲模型，其中不同對象30的鍵可為了管理(例如，帳目管 理、記帳)> 安全或其它目的而被分組到存儲桶20中。在一個實施方式中， 協調器120可配置成響應於來自客戶50的相應的網絡服務請求而處理各 種與存儲桶相關的操作。例如，協調器120可配置成執行下列存儲桶操作 中的一些或全部
-創建存儲桶為存儲桶20產生並儲存新的存儲桶名稱。
-刪除非空存儲桶刪除包括相關的元數據21和與給定存儲桶20內 對象30關聯的所有鍵的給定存儲桶20。
-刪除空的存儲桶只有當沒有對象30的鍵與給定存儲桶20關聯時 才刪除給定存儲桶20和相關的元數據21 ，否則返回錯誤情況。
-寫入存儲桶數據將數據(例如，元數據21 )寫到現有的存儲桶 20中。
-列出存儲桶鍵列出與給定存儲桶20關聯的對象30的鍵(可選地 根據模式、規則表達式、通配符等存儲或過濾的)b
-列出存儲桶列出與給定籤約者(例如，用戶或客戶50 )關聯的 存儲桶20。
在一些實施方式中，協調器120可配置成使用適當的隨機數算法以及 低概率的衝突產生來為新近創建的存儲桶20生成標識符。在其它實施方 式中，協調器120可配置成例如通過在客戶請求存儲桶創建時檢驗被請求 的標識符相對於現有的存儲桶標識符的唯一性，來支持客戶專用的存儲桶 標識符。
如上所述，對象30的實例可跨越不同的位存儲節點160而被複製， 例如以增加對象數據經得住任何給定節點160或其相關的基礎結構的故障的可能性。存儲服務系統內的對象複製為在所示實施方式中可被節點揀取
器130和複製器180處理的管理和最佳化呈現一些機會，如下。
當協調器120接收寫入對象30的請求時，它可在聲明寫入將要結束 之前相應地將對象30寫到給定數量的節點160。然而，對象30應被寫入 的節點160的數量和特定選擇可能根據很多不同存儲策略考慮因素而變 化。例如，在寫入操作被認為將要結束之前，要求對象30的確定的最小 數量的複本(例如，兩個或三個)被成功地寫入可能是謹慎的，以便考慮 到可能的故障寫入的數據是持久存在的。然而，確保選擇成儲存最小數量 的複本的節點60分布在故障的不同可能的位置或區域中也可能是期望有 的。例如，位於相同的數據中心的節點160比在地理上分離的節點160可 能更有可能同時失效(例如，由於災難性故障如自然災害、電源故障等>
可一般稱為存儲節點選擇邏輯的節點揀取器130可配置為協調器120 和複製器180可訪問的服務，在一個實施方式中，協調器120和複製器180 可實現用於為對象讀取和寫入操作選擇節點160的算法，以便滿足不同的 存儲策略。例如，在如上概述的寫入對象30的情況下，節點揀取器130 可操作來開發寫入計劃，或對象30應被寫入的特定序列的節點160。在開 發特定的寫入計劃中，節點揀取器130可配置成確保寫入計劃有成功的合 理機會一例如，在寫入計劃中指定的節點160實際上是可操作的並預期具 有可用來接受對象30的足夠的存儲資源一併且寫入計劃如果被完成將滿 足與寫入操作有關的所有存儲策略。示例性寫入存儲策略可包括下列
-持久性策略如果寫入計劃成功地完成，則對象30的實例將存儲 在至少N個不同的節點160上。
-區域多樣性策略如果可能，寫入計劃將包括分布在至少M個不 同區域中的節點160。
-本地性策略如果可能，寫入計劃將優先選擇(例如，在數量上) 在被請求的協調器120本地的區域內的節點160。
-負載平衡策略努力使寫入請求業務量在節點160中間均衡(例如， 以避免"熱節點")b-空間平衡策略努力使存儲資源容量利用在節點160中間均衡。
-最低成本鏈策略努力最小化在寫入計劃中節點序列寫入操作的總 成本(例如，網絡等待時間)b
注意，在不同實施方式中，節點揀取器130可配置成當制定給定的寫 入計劃時考慮這些策略或沒有列出的其它策略中的一些或全部。進一步 地，不同的策略可能被加有不同的優先級。例如，在一個實施方式中，持 久性策略可以是所有寫入計劃必須滿足的強制性策略，而剩餘的策略可以 在盡力服務(best-effort)的基礎上得到滿足。在一些情況下， 一些存儲策 略可能與另一些存儲策略衝突。例如，支持對象實例在不同區域中間的廣 泛分布的區域多樣性特點通常與支持在特定的區域內局部化對象實例的 本地性策略相反。如果對象實例的數量不夠大，則滿足兩個策略是可能的。 例如，如果要創建對象30的五個實例，則可能將兩個實例存儲在兩個不 同的區域且三個實例在被請求的協調器120本地的第三個不同的區域內， 因而滿足本地性和區域相異性策略。如果不可能滿足寫入計劃所指定的所 有策略，則節點揀取器130可試圖以優先考慮滿足並產生盡力服務寫入計 劃的那些策略，或可將指示對象寫入不能被良好地執行的錯誤指示返回到 發出請求的協調器120。
在一些實施方式中，節點揀取器還可幫助協調器120讀取對象30。例 如，對象讀取操作可被不同於最初或最近寫入請求的對象30的協調器的 協調器120請求。因此，相對於寫入協調器120可被存儲在本地的對象30 的實例可能相對於讀取協調器120來說不是本地的。節點揀取器130可配 置成識別提供讀取協調器120可利用的最佳讀取性能的節點160。例如， 節點揀取器130可識別最接近於讀取協調器120的節點160 (例如，根據 地理距離或網絡拓撲)或提供最大讀取帶寬的節點160 (例如，最少負載 的節點160或具有較高性能的存儲硬體類的節點160 )，或節點揀取器130 可使用用於選擇節點160的其它性能標準，其中從節點160讀取對象30。 在其它實施方式中，不是相對於讀取協調器120最佳化讀取操作的性能， 節點揀取器可全局地計劃並行的讀取操作，以便在總體上最佳化系統的性 能(例如，以最大化全局讀取總處理能力)b為了開發寫入計劃並關於對象讀取操作向協調器120提出建議，節點 揀取器130可配置成例如相對於其操作狀態和有效資源來監控節點160的 狀態。在一個實施方式中，節點揀取器130可配置成與DFDD 100的實例 進行交互作用(下面描述的)，以便識別存儲服務系統內並行操作的節點 160。 一旦節點揀取器130意識到操作的節點160 ,它就可詢問那些節點來 確定在每個節點處可利用的資源(例如，存儲容量)b因為節點160的操 作和資源狀態可隨著時間而變化，所以在一些實施方式中，節點揀取器130 有時可通過DFDD 110更新操作狀態信息並輪詢最終的節點160 ，以更新 其資源狀態信息。注意，在一些實例中，節點揀取器130可能沒有節點160 的狀態的完全同步的觀察。例如，被認為節點揀取器130可用的特定節點 160可實際上自從狀態信息的最後更新以後失效。在這樣的實例中，節點 揀取器130可能不能保證其讀取或寫入計劃能夠由協調器120完成。如果 協調器120不能訪問由節點揀取器130指定的節點160 ,則相關的操作可 能失敗且被協調器120全部重新嘗試，或協調器120可與節點揀取器130 協商以修改請求的計劃。在一些情況下，如果在寫入計劃中指定的節點160 的故障只影響可選的或盡力服務的存儲策略，同時仍然允許滿足強制性的
存儲策略，則可允許寫入計劃結束。在一些這樣的實施方式中，複製器180 可配置成在以後的時間努力滿足未滿足的存儲策略，如下所述。
在一些實施方式中，節點揀取器130的多個實例可在整個存儲服務系 統中部署。例如，節點揀取器130的相應實例可為協調器120的每個實例 部署。雖然節點揀取器130可部署為可從協調器120通過API (和複製器 180 )訪問的服務，這種結構不是必要的。在其它實施方式中，節點揀取 器130的功能可直接合併在協調器120和/或複製器180的實例中。
如上所述，對象數據的可靠性和有效性可通過在整個存儲服務系統中 複製對象30來增加。例如，在地理上分散的系統內分布對象30的實例或 複本可提高類似地分散的客戶50的性能，這些客戶50試圖通過可能定位 較接近於這樣的客戶的一些對象實例來訪問這樣的對象30。(注意，在對 象複製的情景下，術語"實例"和"複本"可在這裡互換地使用)進一步地，對 象複製可通常降低由特定對象實例的破環而產生的數據損失的可能性。然
33而，在一些實施方式中，情況可能是，在給定的時間點，對象30的有效 複本的數量可能小於複本的期望或目標數量。例如，在存儲服務系統中實 施的複製存儲策略可指定每個對象30的特定目標數量的複本(例如，3或 任何其它適當的數量)應在任何給定的時間存在。然而，對於給定的對象 30 ，由於各種原因，有效複本的實際數量可能小於目標數量。例如，先前 有效的複本可能由於存儲其的設備的故障而變得不可訪問。可選地，在一 些實施方式中，被協調器120寫入的對象30的實例的數量可小於該對象 30的複本的目標數量。例如，如上所述，實例可根據由節點揀取器30指 定的寫入計劃而被寫入，該寫入計劃可考慮需要比目標數量少的實例的持 久性策略。
在一個實施方式中，複製器180可操作來檢查對象30以確定每個對 象30的有效複本的數量是否滿足目標數量(例如，複本的數量是否至少 是在做出確定時的目標數量)b特別地，在一個實施方式中，複製器180 可配置成對指定每個對象30的實例的數量和位置的記錄連續重複。例如， 複製器180可涉及複製器鍵映射190 ，複製器鍵映射190可與在下面更詳 細描述的鍵映射實例140 —樣可配置成存儲對象鍵和識別複製的對象實例 的相應定位器之間的映射。(在其它實施方式中，複製器180可考慮一個 鍵映射實例140 ，而不是專用的鍵映射實例)b在一些實施方式中，可以設 想，複製器180的多個實例可配置成同時檢查鍵映射空間的不同部分，這 可減少檢查由存儲服務系統管理的所有對象30的狀態所需要的總時間量。
如果複製器180確定對於給定的對象30來說不滿足有效複本的目標 數量，則它可配置成以類似於協調器120執行對給定對象30的寫入操作 的方式來寫入給定對象30的額外的複本。例如，複製器180可與節點揀 取器130進行交互作用以獲得用於產生額外的複本的寫入計劃，如上所述。 可選地，複製器180可實現其自己的用於產生對象複本的算法反映 (algorithms reflecting )策略。在一些實施方式中，複製器180可根據需要 額外的複本的條件來符合不同的優先級以產生對象30的複本。例如，具 有少於目標數量的在複製器鍵映射190中列出的定位器的對象30可最近 由協調器120寫入。相反，具有目標數量的定位器的對象30可展示基本存儲的故障，其中一些定位器是無效的。作為策略的問題，複製器180可 試圖在後面的情況之前糾正前面的情況，反之亦然。可選地，每當遇到這 種條件時，複製器180可試圖為具有少於目標數量的有效複本的任何對象 30產生額外的複本，而不管引起該條件的特定情況如何。
如上所述，對象30的存儲的總可靠性可通過將對象數據的複本存儲 在例如不同的區域或數據中心內來增加。然而，注意，在一些實施方式中， 每個複本不需要相應於對象數據的準確拷貝。在一個實施方式中，對象30 可根據冗餘編碼方案(例如奇偶性、錯誤校正代碼或其它方案)分成很多 部分或"碎片"，以便對象數據可從少於全部的生成的部分重建。例如，使用 從對象30產生N個部分的各種方案劉象數據可根據編碼方案從任何N-l 個部分、N個部分的任何簡單的多數或部分的其它組合來重建。在這樣的 實施方式中，對象30的複本可相應於所生成的部分或這些部分的某些組 合。與存儲對象數據的多個完整備份比較，這樣的方法可提供有效的容錯 能力，同時減小數據存儲要求。然而，注意，在一些實施方式中，冗餘編 碼技術還可結合對象數據的完整複製而被使用。例如，對象數據的多個單 獨的完整備份可存儲在節點160中，作為根據如上所述的適當的冗餘編碼 技術確定的多個部分的相應集合。最後，注意，在一些實施方式中，某些 對象30根本不需要以任何程度的複製或容錯能力存儲。例如，如下面結 合存儲類的描述所述的，客戶可要求對象30根據指定很少或根本沒有任 何程度的容錯能力的存儲類來存儲，可能具有比指定較高的容錯能力程度 的存儲類更低的成本。
一般而言，鍵映射實例40可提供對象30的鍵和對象30的特定實例 或複本的定位器之間關係的記錄。在存儲這樣的記錄中，鍵映射實例140 還反映對象30在存儲系統內複製的程度(例如，存在多少對象30的實例， 以及可如何引用它們位存儲節點160通常可為對象30的各個實例提供 存儲，如由定位器識別的。然而，給定節點160可能意識到實例相對於任 何其它節點160的狀態，或實例的定位器和其相應對象30的鍵之間的關 系。也就是說， 一般而言，由鍵映射實例140維護的狀態信息對位存儲節 點160來說可以是透明的。DFDD 110可操作來檢測和傳送關於節點160的操作狀態和/或鍵映射實例140 (以及複製器鍵映射190 ，如果被實現) 的狀態信息，以便DFDD110的客戶例如協調器120和複製器180可獲得 所檢測的狀態的準確、雖然可能延遲的觀察。下面更詳細地專注於這些部 件。
在圖3中示出了說明圖2的存儲服務系統體系結構的某些組件的物理 部署的一個實施方式。在所示實施方式中，數據中心300顯示為包括兩個 區域310a-b。此外，區域310c-d顯示在數據中心300的外部，且區域310a-d 通過網絡60相互連接。區域310c-d中的每個都包括各自的協調器實例 120a-d。區域310a-d還可包括位存儲節點160和鍵映射實例140的各種組 合，以及在圖3中沒有示出的圖2的其它組件。例如，區域30a包括四個 位存儲節點160 ,區域310b包括三個位存儲節點160和鍵映射實例140 ， 區域310c包括兩個位存儲節點160 ，以及區域310d包括一個位存儲節點 160和一個鍵映射實例140。
如上所述，在一個實施方式中，每個區域310a-d可被考慮為獨立的或 弱相關故障的位置。也就是說，任何給定區域310經歷故障的概率可能通 常與任何其它給定區域310的故障的概率無關或不相關，或故障概率的相 關性可小於閾值量。例如，兩個區域310可表現出小於10%的同時故障的 可能性。故障相關性或無關性可使用任何適當的統計或概率技術測量並以 各種方法執行。例如，區域310可與獨立的效用網格(utility grid )物理分 離或連接，可能致使影響一個區域310的災難將不影響另一個區域。類似 地，在數據中心300內，不同的區域310可具有獨立的備用電源、網絡連 接或其它冗餘資源，其可起作用來使一個區域310能夠繼續操作而不管另 —區域310的故障。
注意，在一些實施方式中，在其各自的故障可能性之間有小的但非零 相關性的兩個區域310可仍然被認為具有獨立的故障可能性。例如，儘管 每個區域310都具有用於備用電源、冷卻等的穩健的和獨立的系統，但是 在給定數據中心300內的兩個區域310可能在足夠大的災難(例如，足以 摧毀整個數據中心300的爆炸)的情況下易受並行故障的影響。然而，足 以使這兩個區域310同時出故障的事件的概率可能足夠小，為了實際的目的，兩個區域310可假定為具有無關的故障可能性。
區域310可包括層次的附加級別(未示出)b例如，在一個實施方式 中，雖然可使用任何適當的區域組織，但是區域310可細分成格柵(rack), 格柵進一步細分成單獨的節點，例如位存儲節點160。 一般而言，區域310 可包括足以實現在區域內部署的存儲服務系統組件的計算資源。例如，每 個位存儲節點160可實現為自主的計算機系統，該計算機系統可包括如下 面結合圖4-9的說明所述的各種硬體和軟體組件。類似地，每個鍵映射實 例140可通過多個計算機系統來實現，如下面結合圖10-22的說明所述來 配置這些計算機系統。
在一些實施方式中，組件例如網絡服務平臺100、協調器120、節點 揀取器130、複製器180和DFDD 110可通過每個區域310內分立的計算 資源來實現，組件被部署在區域310內。例如，這些組件中的每一個都可 實現為可由相應的計算機系統執行的一組指令和數據。可選地，這些組件 中的一些或全部可實現為可同時在一個或更多計算機系統上執行的過程。 在一些實施方式中，用於實現這些組件中的一些或全部的計算資源可與用 於實現位存儲節點160或鍵映射實例140的那些資源一起被共享。例如， 計算機系統可配置成實現鍵映射140功能以及協調器120功能的一些部 分。 一般而言，可使用在單獨的區域310內部署的計算資源上的圖2的組 件的任何適當的分割。注意，如圖3所示，不同的區域310可包括存儲服 務系統組件的不同組合，且所示實施方式旨在為說明性的而不是限制性 的。
此外，不同的存儲服務系統組件可根據任何適當類型的通信協議來進 行通信。例如，在圖2的某些組件被實現為分立的應用程式或可執行的過 程的場合，它們可使用標準的過程間通信技術或通過使用標準或專用的與 平臺無關的通信協議來彼此通信，標準的過程間通信技術可由作業系統或 平臺(例如，遠程程序調用、隊列、郵箱、套接字等)提供。這樣的協議 可包括可支持任意級的信號交換/確認、錯誤檢測和校正或通信組件可能需 要或希望的其它通信功能部件的有狀態或無狀態的協議。例如，在一個存 儲服務系統實施方式中，相當程度的組件間通信可使用適當的網際網路傳輸層協議例如傳輸控制協議(TCP )的一種版本、用戶數據報協議(UDP ) 或類似的標準或專用的傳輸協議來實現。然而，還可以設想，在存儲服務 系統組件之間的通信可使用在協議抽象的較高層的協議來實現。例如，與 客戶50和網絡服務接口 100之間的通信一樣，存儲服務系統組件之間的 通信可使用應用屠協議例如在HTTP上的網絡服務請求來進行。
位存儲配置
如上所述，在圖2所示的存儲服務系統體系結構實施方式中，位存儲 節點160可通常操作來為由存儲服務系統管理的不同對象30提供存儲。 在圖4中示出位存儲節點160的一個示例性實施方式。在所示實施方式中， 位存儲節點160包括配置成與存儲重裝器163和邏輯文件輸入/輸出(I/O ) 管理器165通過接口連接的存儲節點管理(SNM )控制器161。管理器165 配置成與文件系統167通過接口連接，文件系統167又配置成管理一個或 更多存儲設備169。在不同實施方式中，SNM控制器161、存儲重裝器163、 邏輯文件I/O管理器165或文件系統167中的任何一個可實現為可存儲在 計算機可訪問的介質上或可由計算機執行的指令，以執行下面描述的功 能。可選地，這些部件中的任一個都可由專用硬體電路或設備實現。
在一個實施方式中，SNM控制器161可配置成向節點160的客戶提供 對象存儲API ，以及協調節點160的其它組件的行為以根據API來完成動 作。例如，控制器120可配置成通過由SNM控制器161提供的API來將 對象30存儲到給定節點160並從給定節點160取回對象30。雖然API管 理在這裡被描述為SNM控制器161的功能部件，可以設想，在一些實施 方式中，節點169的API處理功能可以與SNM控制器161不同的模塊或
組件實現。
對象存儲API可支持對象放置、獲取和釋放操作。在一個這樣的實施 方式中， 一般也可稱為存儲操作或寫入操作的對象放置操作可將對象30 的數據和/或元數據指定為操作的變元或參數。當對於給定節點160完成操 作時，放置操作可向發出請求的客戶返回相應於所存儲的對象30的定位 器，該定位器可相對於在整個存儲服務系統中存儲的所有其它對象30來 唯一地識別在給定節點160上的對象實例。相反地， 一般也可稱為讀取或取回操作的對象獲取操作可將對象30 的定位器指定為參數。當完成操作時，獲取操作可向發出請求的客戶返回 相應於所指定的定位器的對象數據和/或元數據。在一些實施方式中，獲取 操作可支持允許發出請求的客戶指定對象數據、元數據或兩者是否返回到 客戶的參數。
與獲取操作一樣，一般也可稱為刪除或消除操作的對象釋放操作可將 對象30的定位器指定為參數。然而，當完成操作時，釋放操作可釋放以 前與參考的對象30關聯的存儲資源，且這樣的資源可接著用於存儲其它 對象30。在一個實施方式中， 一旦定位器被釋放，對定位器的隨後的獲取 操作在一段時間內可以接著發生或可以不接著發生。也就是說，釋放操作 可用作對節點160的信號，它可釋放存儲資源用於重新使用，但節點160 可能不試圖立即這麼做或通知客戶或另外地使這樣的重新使用與客戶同 步。因此，在其釋放之後的客戶繼續試圖訪問對象30可在任意的時間段 內接著發生，其後對象30可變得在沒有通知時不可訪問。在其它實施方 式中，節點160可配置成阻止客戶訪問以前被釋放的定位器，而不管對象 數據是否仍然是可用的。
可以設想，在不同實施方式中，放置、獲取和釋放操作可根據任何適 當的協議來使用其它參數和/或返回不同的狀態、錯誤或其它指示。例如， 如果在節點160上對於待存儲的被請求的對象30沒有足夠的資源，或如 果由於某種其它原因放置不能被完成，則放置操作可返回錯誤情況。還可 設想，在一些實施方式中，節點160的對象存儲API可包括其它操作。例 如，API可配置成通過支持複製操作來促進對象複本的建立。在一個實施 方式中，除了不是向目標節點160提供待存儲的對象30的數據，而是請 求的客戶可在不同的節點160上指定該對象30的定位器外，複製操作可 與放置操作類似地操作。目標節點160可接著與指定的節點160進行交互 作用以獲得對象數據和/或元數據，並可將關於目標節點的對象的定位器返 回到客戶。在其它實施方式中，節點160可支持對對象30的其它適當的 操作。
注意，在實現如上所述的放置、獲取和釋放操作的一些實施方式中，現有對象30可以不在原位被修改。更確切地，對象30的實例可通過在寫 入包括修改的數據的新實例之後通過釋放現有的實例來被有效的修改。如 果對象30的修改致使它小於或大於其原始大小則例如通過減小可能出現 的分段存儲或對象再定位，這樣的方法可簡化節點160的基本管理層的實 現。如下面關於網絡服務平臺IOO更詳細描述的，在一些實施方式中，存 儲服務系統可支持將大的對象分裂成塊，其中每個塊可作為不同的對象30 而被管理。這種方法可在處理大的對象中提高節點160的性能，通過限制 可能需要被重寫的塊的範圍可頻繁地修改該大的對象。然而，可以設想， 在其它實施方式中，節點160可包括支持對象30在原位的修改而不是通 過剛剛描述的釋放-重寫方法所必需的那些功能部件。
在所示實施方式中，邏輯文件I/0管理器165(或簡單地，管理器165 ) 可配置成虛擬化基本設備或文件系統特徵，以便給SNM控制器161和重 裝器163提供一個或更多對象30可駐留的邏輯上鄰接的存儲空間。例如， 給定對象30可根據其在存儲空間內的偏移和其距離該偏移的範圍(extent ) (例如，根據對象大小，包括數據和元數據)來被定位在邏輯存儲空間中。 通過提供這樣的邏輯存儲空間，管理器165可向SNM控制器161提供基 本存儲的一致呈現，而不管這樣的基本存儲的實現細節。
為了便於對邏輯存儲空間內的對象30的訪問，在一個實施方式中， 管理器165可配置成向存儲到節點160的每個對象30分配對象索引偉也 稱為對象索引)b —般而言，任何給定對象30的索引在特定節點60內可 以是唯一的。例如，在一個實施方式中，對象索引可通過每當對象30存 儲到節點160時遞增計數器並使用最終的計數器值作為對象索引來獲得。 (在允許多個對象寫入操作同時進行的實施方式中，可通過例如串行化來 同步計數器遞增，以確保以一致和可預測的方式分配對象索引值。〉足夠 大的計數器值，例如64位無符號整數例如可確保為了實際目的而給每個 對象30分配唯一的索引值。這樣的計數器可在比方說264個對象被存儲之 後滾動循環，其後可重複以前產生的索引值。然而，衝突是非常不可能的， 因為在計數器滾動循環之後以前被分配了給定索引值的對象30仍然存在 於節點160內是非常不可能的。注意，用於分配對象索引的任何其它適當的方法也可被使用。如下所述，對象索引值可結合節點160的唯一標識符 使用，以確定可由協調器120或節點160的其它客戶使用來參考特定對象 30的定位器值。
管理器165可配置成使用上面描述的唯一的對象索引值來以便於對象 訪問的方式組織定位在邏輯存儲空間內的關於對象30的信息。例如，如 在圖5的上部分中示出的，在一個實施方式中，管理器165可配置成存儲 表格或類似的數據結構，所述表格或數據結構可被組織成通過對象索引值 而被容易地訪問。在所示實施方式中，索引表500可包括很多項目510 , 其中每個項目都可包括很多欄位，包括對象索引欄位、偏移欄位、對象大 小欄位、元數據大小欄位和循環冗餘碼校驗(CRC )欄位。如在圖5的下 部分中，對於一些示例性對象30示出，項目510的偏移欄位可指定相應 的對象30在邏輯存儲空間內的開始位置，以及對象大小和元數據大小字 段可指定對象數據和元數據從偏移點延伸所達到的程度。雖然對象數據和 對象元數據的順序在其它實施方式中可顛倒，但是在所示實施方式中，對 象數據在對象元數據之前。CRC欄位可存儲循環冗餘碼校驗算法或其它適 當類型的校驗和或散列算法的結果。當對象30最初存儲到節點160時， 可計算最初存儲到CRC欄位中的值。隨後，當訪問對象30時，相同的算 法可應用於對象數據和/或元數據，且作為結果的值與所存儲的CRC欄位 值相比較。如果該比較導致失配，則可能損害所存儲的數據的完整性。注 意，在其它實施方式中，項目510可包括附加欄位或與所示的那些不同的 欄位。例如，CRC欄位可被省略或在其它地方實現。此外，代替地或除了 相對偏移以外，還可存儲對象數據和元數據的絕對位置。
重裝器163可配置成對邏輯對象存儲空間進行操作，以消除當對象30 被釋放且其相關聯的存儲資源被重新使用時可能出現的間隙。在一個實施 方式中，重裝器163可配置成掃描邏輯對象存儲空間(例如，周期性地或 連續地),以識別已經被SNM控制器161和/或管理器165標記為被前面的 釋放操作釋放的對象30。重裝器163可接著使具有出現在被釋放的對象 30的索引之後的索引的那些對象30的項目510被更新以反映被釋放的對 象30的消除，這可有效地產生朝著邏輯對象存儲空間的原點移動的那些對象30。例如，如果在圖5的下部分中的對象N將被釋放，則重裝器163 可操作來使相應於對象N+l的項目510被更新以將對象N的偏移欄位表 現為對象N+l的新的偏移欄位。重裝器163還可使與對象N關聯的項目 510被刪除，並可更新在對象N+1之後的對象的偏移以反映移位。在一個 實施方式中，管理器165可使在邏輯對象存儲空間和/或存儲設備169下面 的文件或結構內出現對象數據和元數據的相應移位。因此，在一些實施方 式中，重裝器163的操作可減少下層存儲結構的分段存儲並相應地提高節 點160的對象訪問性能。
在一些實施方式中，管理器165可配置成在包括不同類型的硬體和軟 件的多個不同的執行平臺上執行。在一些這樣的實施方式中， 一個或更多 另外的抽象層可存在於由管理器165提供給SNM控制器161的邏輯對象 存儲空間及其客戶之間。例如，在所示實施方式中，管理器165可配置成 將邏輯對象存儲空間實現為由文件系統167管理的一個或更多物理文件。 —般而言，文件系統167可配置成將不同類型的物理存儲設備169組織到 邏輯存儲設備中，該邏輯存儲設備可以邏輯單元存儲數據，所述邏輯單元 在這裡稱為物理文件。由文件系統167管理的邏輯存儲設備可實際上是分 層的。例如，文件系統167可支持可被定位(navigated )來存儲和訪問物 理文件的目錄或文件夾的層次。 一般而言，文件系統167可配置成跟蹤和 管理給定物理文件和存儲設備169的位置之間的關係，其中物理文件的相 應的數據和/或元數據存儲在存儲設備169上。因此，在一個實施方式中， 管理器165可管理邏輯對象存儲空間到由文件系統167分配的一個或更多 物理文件的映射。文件系統167又可管理這些物理文件到存儲設備169的 可尋址的位置的映射。
文件系統167可通常集成在作業系統內，雖然任何給定的作業系統可 支持提供用於管理下層設備169的不同功能部件的各種不同的文件系統 167。例如，Microsoft \￥^(10 3@作業系統的不同版本支持文件系統，例如 NT文件系統(NTFS )以及FAT32 (文件分配表-32 )和FAT16文件系統。 Linux和Unix作業系統的不同版本可支持文件系統，例如ext/ext2文件系 統、網絡文件系統(NFS Reiser文件系統(ReiserFS )>快速文件系統(FFS )
42和許多其它的文件系統。 一些第三方軟體廠商可提供用於與各種計算平臺
集成的專用文件系統，例如VERITAS⑧文件系統(VxFS )b不同文件系統 可提供對於用於管理下層存儲設備169的不同功能部件的支持。例如，一 些文件系統167可提供對於實現設備鏡像、分散連結(striping 、快照或 其它類型的虛擬化功能部件的支持。
注意，在一些實施方式中，在管理器165和存儲設備169之間可能仍 然存在其它的抽象層。例如，在一些實施方式中，體積(volume )管理器 層可設置在文件系統167和存儲設備169之間，並可配置成執行上面提到 的一些或所有虛擬化功能部件。可選地，特定的存儲設備169可配置為硬 盤驅動器或包括虛擬控制器的其它設備的獨立陣列。虛擬控制器可配置成 向文件系統167提供磁碟驅動器作為單個物理設備，雖然虛擬控制器在內 部可支持設備的存儲地址空間到磁碟驅動器的任意複雜的映射，但是類似 於如上提到的可由體積管理器支持的或在文件系統167內的虛擬映射。還 注意到，在一些實施方式中，可能存在比那些所示的抽象更少的層。例如， 在一些實施方式中，管理器165可配置成與例如作為原始物理設備的存儲 設備169直接進行交互作用，而不使用文件系統167。
一般而言，存儲設備169可包括可由文件系統167和/或管理器165支 持的任何適當類型的存儲設備。存儲設備169可通常包括硬碟驅動器設備， 例如小型計算機系統接口 ( SCSI )設備或AT附加編程接口 ( ATAPI )設 備(其也可稱為集成驅動電子(IDE )設備)b然而，存儲設備169可包含 包括基於磁或光介質的設備的任何類型的海量存儲設備、固態海量存儲設 備(例如，基於非易失性或"閃"存儲器的設備X磁帶等。進一步地，存儲 設備169可通過除了上面提到的那些以外的任何適當的接口類型而被支 持，例如遵循通用串行總線或IEEE 1394/Firewire⑧標準的版本的接口。
如上所述，對於存儲在存儲設備系統內的對象30的任何給定的實例， 相應的定位器可唯一地識別在系統內所有節點160上的實例。在一個實施 方式中，定位器可生成為對象索引值的級連、組合或其它函數，該對象索 引值以及相應於上面存儲對象實例的節點160的唯一標識符或"節點ID"可 由管理器165分配給對象實例。例如，如上所述，64位對象索引值可與64位節點ID組合以產生128位定位器。這樣的定位器允許多達264個唯一 的節點160中的每一個存儲多達264個唯一的對象實例，雖然在不同實施 方式中更小或更大數量的位可用來形成定位器。
在一個實施方式中，節點ID可通過唯一的網絡地址，例如相應於給 定節點160的網際網路協議(IP )地址的級連接或組合來形成，並具有時間 戳或日期戳。例如，根據IP位址(例如，在節點啟動/初始化時或如果不 在初始化期間則在節點ID被分配時)與反映IP位址被分配的時間或IP地 址被得知是有效的時間期間的時間戳的組合，可給節點160分配節點ID。 一般而言，屬於同一 ID地址空間的兩個不同的節點160不能在任何給定 的時間被有效地分配相同的IP位址。因此，節點的IP位址和時間戳值的 組合可產生對該節點來說唯一的標識符。例如，32位IP位址可與32位時 間戳(例如，其表示自從某個公共參考時間以來經過的秒數)級連或組合 以產生上面提到的64位節點ID ，雖然可使用其它位寬度。還可以設想， 可使用其它技術來分配不依賴於節點IP位址的唯一的節點ID。例如，授 權中心例如命名伺服器可在被請求時以保證節點ID的唯一性的方式來委 派節點ID ，類似於如上所述在節點160內對象索引值的分配。
注意，在節點ID得自節點的IP位址的實施方式中，節點ID可不在 任何給定的時間反映節點160的當前IP位址。例如，節點ID可繼續存在 直到節點160被重置，但節點的IP位址可在節點ID產生之後被改變或重 新分配。此外，在一些實施方式中，節點ID可以確定性的方式被散列、 加密或混亂化，以便防止存儲客戶50或其它可能惡意的實體解碼定位器 以確定實際的節點IP位址。
圖6中示出了關於圖4的節點160的實施方式的獲取、放置和釋放操 作的示例性實施方式的操作。首先參考圖6 ,獲取操作可在塊600中開始， 其中操作在節點160處從協調器120或其它客戶接收。例如，協調器120 可向包括節點ID和對象索引值的特定的定位器發出獲取操作，如上所述。 例如，如果節點ID反映目標節點160的當前IP位址，則節點ID可用於 直接將獲取操作路由到適當的節點160。可選地，目錄服務例如下面描述 的DFDD 110可用於將定位器的節點ID解析到可尋址的端點或目的地中，獲取操作可通過該端點或目的地而被路由到適當的節點160。
一旦被節點160接收，則獲取操作就可被處理以識別節點160的邏輯 對象存儲空間內的目標對象實例的範圍(塊602 )b例如，控制器161可接 收穫取操作並將它傳送到管理器165。管理器165又可使用通過獲取操作 所引用的定位器的對象索引部分來訪問索引表500 ，以便獲得邏輯對象存 儲空間內的期望的對象實例的位置。例如，管理器165可獲得在對象實例 開始位置的邏輯對象存儲空間內的偏移，以及該對象實例距離該偏移的長 度。在一些實施方式中，獲取操作可指定對象數據、元數據或兩者是否是 期望的。在這樣的實施方式中，管理器165可確定與被請求的數據有關的 邏輯對象存儲範圍。例如，如果對象數據和元數據都是期望的，則管理器 165可使用對象數據大小和元數據大小來確定距離待取回的對象偏移的範 圍。如上所述，在其它實施方式中，管理器165可以不同的方式來存儲和 管理對象實例的存儲範圍，例如通過絕對位置而不是邏輯對象存儲空間內 的相對偏移。
在邏輯對象存儲空間內的對象範圍可接著被映射到物理文件存儲空 間內的一個或更多相應的文件內的範圍上(塊604 )b例如，管理器165可 將邏輯對象存儲空間映射到由文件系統167管理的一個或更多文件上，並 可向文件系統167發出適當的文件訪問操作，以例如通過參考一個或更多 文件名以及待讀取的命名文件內的位置或偏移來獲得相應於所期望的對 象範圍的數據。可以設想，在可選的實施方式中，控制器161可配置成繞 過由管理器165管理的邏輯塊存儲空間功能部件，並可改為直接與文件系 統167管理的物理文件進行交互作用。
對物理文件的參考可接著被映射到與設備有關的請求(塊606 )o例如， 文件系統167可配置成生成對存儲設備169的特定可尋址的位置的一個或 更多讀取請求，其中特定可尋址的位置例如邏輯塊地址(LBA )或設備幾 何結構(例如，圓柱體、軌道、扇區和/或磁頭)所特有的地址。如上所述， 在一些實施方式中，管理器165可配置成繞過文件系統167並直接管理存 儲設備169。
被請求的對象數據可接著被從存儲設備169取回(塊608 )並被返回
45到發出請求的客戶(塊610 )b例如，取回的數據可被向上返回通過圖4所 示的請求層次，或可從存儲設備169或文件系統167直接返回到控制器161 以傳送到發出請求的客戶。
如圖7所示，在一個實施方式中，在塊700中當操作在節點160處從 協調器120或其它客戶接收放置操作時，放置操作可以類似於上面對圖6 的塊600描述的方式開始。例如，協調器120可向在由節點揀取器130產 生的寫入計劃中指定的節點160發出放置操作。與獲取操作相反，放置操 作可包括待存儲的對象數據和/或元數據，並可以可選地包括指定數據和/ 或元數據的長度的附加參數。
一旦被節點160接收，則放置操作就可被處理以為邏輯對象存儲空間 內的對象實例分配存儲範圍(塊702》在一個實施方式中，管理器165可 配置成向新的對象實例分配對象索引值，並在索引表500中記錄指定新的 對象實例的偏移的新項目510。例如，新項目的偏移可相對於具有最大索 引值的現有對象實例的存儲範圍(例如，偏移和長度)而被確定。如果新 的對象實例的數據和/或元數據的長度沒有被指定為放置操作的參數，則管 理器165或控制器161可配置成計算所述數據和/或元數據的長度以包含在 新項目510中。
邏輯對象存儲空間內新近分配的存儲範圍可接著被映射到物理文件 存儲空間內的一個或更多相應的文件內的範圍上。例如，新的對象實例的 被分配的範圍可附加到一個或更多現有物理文件的末尾，或另外地位於現 有的或新近分配的物理文件內。物理文件範圍可接著例如由文件系統167 以類似於上面對獲取操作描述的方式而被映射到存儲設備範圍(塊706 ), 且對象實例數據和/或元數據可接著存儲到存儲設備169 (塊708 )b
當確認數據和/或元數據已經被成功地寫入到存儲設備169時，相應於 所存儲的對象實例的定位器可返回到發出請求的客戶(塊710 >>例如，管 理器165可配置成將產生的對象索引值附加到節點160的節點ID上，並 且當從文件系統167指示物理文件寫入操作成功地完成時可返回最終的值 作為對象定位器。
如圖8所示，在一個實施方式中，在塊800中當操作在節點160處從協調器120或其它客戶接收釋放操作時，釋放操作可以類似於上面對圖6 的塊600描述的方式開始。釋放操作可簡單地指定待釋放的對象實例的定 位器，雖然在其它實施方式中也可提供其它變元。
與獲取操作一樣， 一旦釋放操作被節點160接收，釋放操作就可被處 理以識別節點160的邏輯對象存儲空間內的目標對象實例的範ffl(塊802 )b 例如，控制器161可接收釋放操作並將其傳送到管理器165。管理器又可 使用被釋放操作參考的定位器的對象索引部分來訪問索引表500 ，以便識 別所參考的對象實例的相應項目510。所參考的對象可接著被標記為被釋 放的(塊804 )b例如，管理器165可配置成將偏移或項目510的另一欄位 設定為非法值，例如負數，其中負數可表示該項目不再是有效的。指示對 象已被釋放的確認可接著返回到發出請求的客戶(塊806 、
如上所述，當對象實例被釋放時，與對象實例相關聯的存儲資源不能 被立即釋放、收回或重新分配以用於其它用途。更確切地，在一個實施方 式中，那些資源可繼續存在直到相對於釋放操作異步地進行操作的獨立過 程收回它們為止。圖9示出這樣的過程的一個實施方式的操作，例如可通 過存儲重裝器163來實現。在塊900中，可選擇相應於存儲在節點160上 的特定對象實例的對象索引項目。例如，重裝器163可配置成根據存儲在 項目中的對象索引值來以連續的順序從索引表500中選擇索引項目。隨後， 可檢查所選定的項目以確定相應的對象實例是否已被釋放(塊902 )b例如， 重裝器163可檢查偏移欄位或另一欄位以確定該欄位是否已被設定為指示 相應的對象實例已被釋放的值，例如負值或一些其它值。
如果所選定的對象還沒有被釋放，則操作可繼續後退到塊900 ，其中 可選擇另一對象。如果啊選定的對象已被釋放，則邏輯對象存儲空間可被 重裝以收回相應於所釋放的對象的存儲資源(塊904 )b例如，重裝器163 可配置成調節跟隨邏輯對象存儲空間內的所釋放的對象的那些對象實例 的索引項目510 ，以便第一個這樣的對象實例的偏移被設置成所釋放的對 象的偏移，下一個這樣的對象實例的偏移被設置為第一個這樣的對象實例 的數據大小、元數據大小和偏移的函數，等等。然而，在一些實施方式中， 不是在所釋放的對象實例之後的所有對象實例都需要在新的對象被選擇用於檢查之前被重裝。例如，重裝可與對象選擇交替進行，以便遇到的每 個對象在它被選擇用於檢查吋被重裝。
在一些實施方式中，管理器165可響應於邏輯對象存儲空間的重裝而 執行物理文件存儲空間內類似的重裝或合併操作。例如，管理器165可使 邏輯對象數據範圍被重新映射到不同的物理文件數據範圍。類似地，在一 些實施方式中，文件系統167可響應於物理文件存儲空間的重裝而在存儲 設備169中執行類似的重裝或合併操作。在其它實施方式中，物理文件存 儲空間或存儲設備本身的重裝可獨立於由重裝器163發起的邏輯對象存儲 空間的重裝而出現。例如，文件系統167可配置成通過重新排列物理文件 存儲範圍到設備存儲範圍的映射來為存儲在存儲設備169上的物理文件整 理碎片，以便所映射的設備存儲範圍相對於存儲設備的訪問模式來說大部 分或全部是連續的。
在邏輯對象存儲空間的重裝之後，相應於所釋放的對象的索引項目可 被刪除(塊906 )，且操作可從另一對象被選擇的塊900繼續。如上所述， 在一些實施方式中，重裝可在對象被選擇時"即時(on the fly )('出現，這 可提高邏輯對象存儲空間的總利用，同時最小化重新定位對象所需要的操 作的數量。
注意，在一些實施方式中，可被節點160支持的獲取、放置、釋放或 其它操作中的任何一種操作可支持關於發出請求的客戶的各種類型的信 號交換、確認或錯誤處理協議。例如，如果客戶請求對於一種操作的殘缺 的請求(例如，不能提供必要的參數)，或如果節點160不能良好地完成 操作(例如，沒有充足的資源來兌現放置操作)，則節點160可將錯誤指 示返回給發出請求的客戶。這樣的指示可以包括或可以不包括關於故障情 況的性質的特定細節。
在一個實施方式中，協調器120可配置成將操作獨立傳送到該操作所 指向的每個相應的節點160 ，即使當多個操作可具有共同的數據時也是如 此。例如，在放置操作的情況下，其中對象30根據寫入計劃被寫到多個 節點160 ，協調器120可與每個指定的節點160獨立地進行通信。然而， 在可選的實施方式中，可連結具有共同數據和/或參數、旨在多個目標節點160的操作。在一個實施方式中，協調器120或其它客戶可通過指定在操 作的參數中的每個接收者例如接收者列表來開始所連結的操作。在操作中 指示的多個接收者可默認地表示連結，或其它參數可用於將操作標記為被 連結的。協調器120或其它客戶可接著通過將連結的操作傳送到在操作中 指定的第一個目標節點160而開始該連結的操作。
當接收該連結的操作時，節點160可處理該操作並可將它轉發到在操 作中指定的另一個目標節點160。在這樣的轉發之前，接收者節點160可 將其自身從包括在該操作中的目標的列表中刪除，以表示接收到並避免循
環轉發。該操作可與接收者節點的處理同時被轉發。可選地，轉發可能發 生在接收者節點成功地完成處理時。在一些實施方式中，連結的操作可以 接收者被指示在該操作中的順序而被傳送到那些接收者。在其它實施方式 中，節點160可例如通過確定剩餘目標中哪一個是最接近的、最少負載的 或滿足一些其它選擇標準的，來動態地選擇下一個接收者。注意，在一些 實施方式中，連結的和非連結的操作的組合可由協調器120或其它客戶產 生。例如，如果相同的數據是前往六個不同的節點160的放置操作的目標， 則協調器120可產生指定這六個目標節點的單個連結的操作，或兩個連結 的操作，其中每個操作指定目標節點中的三個目標節點。其它組合也是可 能的，包括產生協調器120可獨立地傳送到相應的目標節點160中的每一 個的六個非連結的操作。
鍵映射配置
如上所述，各種位存儲節點160可配置成為對象30的實例提供存儲。 節點160不可單獨地為冗餘和數據安全提供任何特定的支持；事實上，在 一些實施方式中，節點160可使用運行開放資源作業系統(例如，Linux ) 並通過廉價的商品性硬碟驅動器(例如，ATAPI/IDE硬碟驅動器)來提供 存儲的一般計算平臺來實現。在這樣的實施方式中，各個系統可能不是容 錯能力特別好的。更確切地，數據安全和冗餘可通過對象30在很多節點 160上的複製而被提供，如上所述。
如前面討論的，給定對象30可相應於可被存儲客戶指定的鍵。給定 對象30的各個實例可相應於相應的定位器，這些定位器可唯一地識別被包括在存儲服務系統中的節點160的集合中的那些實例。在一個實施方式 中，部署在存儲服務系統內的每個鍵映射實例140可配置成為存儲和維持 鍵和用於給定對象30及其存儲在節點160中的複製的實例的所有相應的 定位器之間的關係或映射。在下面的討論中，討論了鍵映射實例140的不 同實施方式的一般特徵和功能，接著是鍵映射實例140的特定實施方式可 如何被實現的描述。
在一個實施方式中，給定鍵映射實例140可配置成將各個鍵和相關聯 的定位器之間的關係的細節存儲在一個或更多表或任何其它適當類型的 數據結構中。例如，在一個實施方式中如圖10所示，鍵映射實例140包 括具有很多項目144的鍵映射數據結構142。每個項目包括相應的鍵146 以及相關聯的記錄148。在一些實施方式中，如下面更詳細描述的，用於 組織項目144的數據結構的組織可能是複雜的。然而，從功能性的觀點來 看，鍵映射實例140可通常保存給定鍵144及其相應的記錄148之間的一 對一的表格狀的關係。
記錄148可一般包括相應於給定鍵144的定位器，但也可包括其它信 息。例如，記錄148的一個實施方式可如下構造
Struct Key Record {
intl6—t version;
intl6_t storageClass;
intl6一t creationDate;
int64」objectSize;
unit32_t crc32;
int8_t numLocators;
struct locator {
int64」nodeID;
int64—t objectlndex;
)replicas[];雖然該示例性數據結構使用c程式語言的語法來表達，它可使用任何適當
的語言、表示或格式來實現。記錄148的可選實施方式可包括比所示的那些更多、更少或不同的欄位。在一些實例中，記錄148可稱為"i節點(inode )'，將記錄148在組織存儲空間中的目的的相似性用於某些類型的Unix文件系統中採用的i節點結構。然而，術語"!節點"在本上下文中的使用不是用來調用文件系統或其它存儲環境內i節點的實現或使用的特定細節。
在上面的實施方式中，記錄148可包括七個特定的元素。16位的版本元素可用於存儲對於記錄148的格式特定的唯一識別的值。例如，記錄148的不同版本可用在鍵映射實例140的不同實現中，且在一些實施方式中，存儲在給定鍵映射實例140中的記錄148可為不同種類的。版本元素可用於區分記錄148的不同版本，以便記錄的其它元素可被正確解碼和使用。
16位storageClass元素可用於存儲相應於記錄148的對象30的存儲類的指示。在隨後的部分中更詳細地描述了存儲類。 一般而言，對象的給定存儲類可識別存儲特徵和/或策略，其對給定存儲類的其它成員可能是共有的，但可不同其它存儲類的成員。例如，對於存儲服務系統的給定實現可定義"高可靠性"存儲類和"低可靠性"存儲類。作為高可靠性存儲類的成員的對象30可比作為低可靠性存儲類的成員的對象30被更大程度地複製，因而降低對各個複本的損失的敏感性，可能是以比對低可靠性存儲類的成員估算的更高的使用成本來交換的。存儲類的很多其它可能的類型和組合是可能的和預期的。
64位的creationDate元素可用於存儲相應的對象30在存儲服務系統內被創建的日期和時間的指示。該元素可以任何適當的方式格式化。例如，日期和時間可被明確地編碼為元素內的不同欄位，或表示自公共參考點以來經過的時間單元(例如，秒、微秒等)的數量的單個數字。在一些實施方式中，creationDate元素可包括配置成指示相應的對象30的任何方面的最後修改的日期和時間的附加欄位，雖然在其它實施方式中，最後的修改元素可作為記錄148內的不同元素而被包括。
64位的objectSize元素可用於例如以字節的形式存儲相應對象的大小
51的指示。在一些實施方式中，該元素可反映對象數據和元數據的大小，而
在其它實施方式中，這些可存儲為不同的欄位。32位的crc32元素可用於存儲根據任何適當的校驗和算法為對象數據和/或元數據計算的循環冗餘碼校驗(CRC )校驗和的指示。例如，可包括校驗和以驗證數據防訛誤或篡改的完整性。在其它實施方式中，除了或代替CRC校驗和，還可使用從對象數據和/或元數據計算的任何適當類型的散列信息或籤名(signature )b
8位的numLocators元素可用於存儲包括在replicas[]陣列內的記錄148內的定位器的數量的指示。在該陣列內，每個定位器存儲為64位的節點ID元素以及64位的對象索引值，其可如上所述在對位存儲節點160的配置的討論中得到。在一些實施方式中，定位器可存儲為replicas[]陣列內的單個元素。
在一個實施方式中，鍵映射實例140可配置成向鍵映射客戶提供鍵映射API ，例如協調器120 ，以及配置成執行支持所提供的API所必需的那些功能。例如，控制器120可配置成使用API來對與鍵映射實例140管理的項目144關聯的記錄148進行存儲、取回、刪除或執行其它操作。類似於對如上所述可由節點160支持的對象實例的操作，在一個實施方式中，鍵映射API可支持對鍵映射項目144的放置、獲取和刪除操作。在一個這樣的實施方式中，一般也可稱為鍵映射存儲操作或鍵映射寫入操作的鍵映射項目放置操作可指定要存儲在鍵映射項目144內的鍵146和記錄148。在一個實施方式中，指定鍵146的放置操作可用被指定為放置操作的變元或參數的記錄來代替與現有的項目144關聯的記錄148 ，其中對於鍵146來說項目144已經存在。當對於給定的鍵映射實例140完成時，鍵映射放置操作可向請求的客戶返回狀態指示，例如操作是否成功或失敗，以及例如出現什麼類型的故障(如果有)b在一些實施方式中，如果鍵映射放置操作導致現有項目144的替換，則鍵映射實例140可配置成將項目144的前面的值返回給請求的客戶。
也可一般稱為鍵映射讀取或取回操作的鍵映射獲取操作可在一個實施方式中將鍵指定為參數。當完成時，鍵映射獲取操作可向請求的客戶返回與請求的鍵關聯的鍵映射項目144的記錄148 ，如果這樣的項目存在的話。如果沒有相應的項目144存在則可將對該結果的指示返回給請求的客戶。
在一個實施方式中，除了請求的客戶不需要指定將寫入到項目中的記錄之外，鍵映射項目刪除操作可配置成與放置操作類似地操作。當對給定的鍵映射實例140完成時緯映射刪除操作可向請求的客戶返回狀態指示，類似於鍵映射放置操作的情況。與放置操作一樣，在一些實施方式中，鍵映射實例140可配置成將刪除的項目144的前面的值返回給請求的客戶。
鍵映射API還可支持在不同實施方式中的其它類型的操作。例如，鍵映射API可支持可幫助鍵映射客戶管理鍵映射項目的操作。在一個實施方式中，鍵映射API可支持列表操作，其可配置成識別具有與請求的客戶指定的一些標準匹配的鍵146的那些項目144。例如，列表操作可允許客戶將字符串或模式指定為操作的參數。當對於給定的鍵映射實例140完成時，列表操作可給請求的客戶返回滿足所指定的字符串或模式的那些鍵146的列表。在一個實施方式中，只有當字符串是鍵146的正確前綴(例如，對於字符串的所有字符，字符串的第N個字符與鍵的第N個字符匹配)時，鍵146才可滿足給定的字符串。在其它實施方式中，如果字符串可在鍵146內的任何位置找到，則鍵146可滿足給定的字符串。
在一些實施方式中列表操作可支持其它參數。例如，列表操作可允許請求的客戶指定對待返回的匹配的數量的限制。此外，請求的客戶可例如通過指定可擴充的或封閉式的按字母順序的範圍來指定對將被搜索的鍵146的約束條件，其中將被搜索的鍵146應落在該按字母順序的範圍內。在一些實施方式中，鍵映射實例140可配置成返回記錄148以及滿足列表操作標準的鍵146。此外，在一些操作中，鍵映射API可支持計數操作，其可支持與列表操作相同類型的參數和執行行為。然而，不是返回滿足由請求的客戶提供的標準的那些鍵146和/或記錄148 ,計數操作可返回滿足那些標準的鍵的數量(例如，由相應的列表操作返回的鍵的數量)b注意，鍵映射API還可支持沒有在上面詳述的其它操作。
在一些情況下，不同的鍵映射客戶可試圖修改相同的鍵映射項目144。例如，響應於各種客戶或系統驅動的操作，兩個不同的協調器120可試圖同時改變給定記錄148的內容(例如，以增加、刪除或修改複本的定位器)，或一個協調器120可試圖修改記錄148 ，同時另一個協調器120試圖刪除相應的項目144。為了提供用於解決對給定鍵映射實例144的同時請求的一致方法，在一個實施方式中，鍵映射API可要求至少那些更新或修改鍵映射狀態的鍵映射操作(例如，鍵映射放置和刪除操作)提供序列號作為鍵映射操作的參數。鍵映射實例140可接著配置成通過比較序列號(數字式或按字母順序地)和在比較的基礎上一致地挑選一個操作來解決對項目144的衝突更新。在一些實施方式中，所提供的序列號連同如下面更詳細描述的用於同步恢復的修改的記錄148 —起可存儲在修改的鍵映射項目144中。
例如，鍵映射客戶可基於時間戳來產生序列號。在一個實施方式中，這樣的時間戳可包括如下格式化的64位數字。時間戳的第63位可設定為零(例如，以避免關於時間戳是否是有符號的或無符號的數字的混淆)o第62 - 32位可包括自從時間的參考點(例如，1970年1月1日午夜，格林尼治標準時間，被很多版本的Unix和Linux使用的參考時間)以來經過的秒數。第31 -22位可包括自從最後一秒以來經過的微秒數。第21 -0位可包括實質上隨機產生的位。在其它實施方式中，時間戳可在不同寬度或類型的欄位的基礎上產生。可選地，鍵映射客戶可使用完全不同的基礎來產生序列號。假定序列號的分辨度高，則在由不同鍵映射客戶為相同的鍵映射項目144提供的不同序列號中間的衝突的機會可能低。然而，如果衝突將要出現，則鍵映射實例140可配置成使用任何適當的一致的技術來解決衝突。
在很多實施方式中，鍵映射實例140在將鍵映射到定位器中的抽象功能行為可能相對直接。例如，如上所述，由鍵映射實例140的一個實施方式支持的一組基本操作可包括配置成處理項目144的放置、獲取和刪除操作，該項目144反映鍵146和包括在記錄148內的定位器之間的關係。然而，鍵映射功能在存儲設備系統內的實現可提出很多挑戰。特別是，如果存儲服務系統要支持代表大量客戶的大量對象30 (例如，總數達1000千兆字節(TB )或1000 TB字節(EB )的存儲量或更多的成百萬或十億的對象30 )，則可能要求鍵映射的實現相應地在容量上調節。然而，實現足夠的系統資源以在單個計算機系統內表示包含在鍵映射內的全部信息可能是不可能的或在經濟上是不可行的。此外，對於鍵映射客戶請求的容錯能力和增加的總處理能力，可在存儲服務系統內以分布式方式部署鍵映射數據的多個複本。然而，例如如果一個複本在另一個複本被訪問時被修改，則鍵映射數據的複本可導致鍵映射同步和一致性問題。
鍵映射功能的可縮放性可通過將層次級別引入鍵映射實例140內來提高。在圖IIA-D中示出了這樣的層次的一個實施方式。在圖IIA中，示出了示例性鍵映射部署1100。如上所述，例如，關於圖3 ，在一些存儲服務系統實施方式中，多個鍵映射實例140可分布在整個系統中，例如在不同的數據中心300或區域310中。通常，鍵映射實例的集合可稱為部署。在一些實施方式中，存儲服務系統可包含單個鍵映射部署1100 ，單個鍵映射部署1100包括在系統內提供的所有鍵映射實例140 ,雖然在其它實施方式中，系統可包括在鍵映射層次的其它級別下合併的多個鍵映射部署IIOO。
在所示實施方式中，部署IIOO包括鍵映射實例140a-c ，其中每個鍵映射實例都配置成例如根據如下面更詳細描述的實例同步協議來與其它鍵映射實例交換鍵映射信息。如所示，每個鍵映射實例140包括配置成彼此通信的很多主機400。例如，鍵映射實例140a包括主機400a-c ，鍵映射實例140b包括主機400d-g ，以及鍵映射實例140c包括主機400h-j。 一般而言，每個主機400可包括計算機系統和相關聯的軟體，並可包括例如處理器、系統存儲器、存儲設備、聯網接口或其它適當的組件的元件。例如，計算機系統或節點的一個實施方式可配置成用作下面結合圖29的描述所討論的主機400。
一般而言，對於存儲在存儲服務系統內的所有對象30 ,每個鍵映射實例140可配置成維持鍵映射數據的完整表示，包括鍵映射項目144以及用於索引並管理鍵映射層次的任何其它數據。在鍵映射實例140內，鍵映射數據可分布在主機400中，以便各個主機400存儲鍵映射數據的某個(可能冗餘的)部分。注意，雖然在圖11A中只示出幾個主機400 ，但是在其它實施方式中，每個鍵映射實例140可具有任何適當數量的主機140。例
55如，在一些大範圍的實現中，許多的或者可能數百的主機140可以被包括在鍵映射實例140中。還可以設想，雖然在一些實施方式中，用於給定鍵映射實例140的主機400可局限於給定區域310或數據中心300內，但在其它實施方式中，這樣的主機400可分布在不同區域310或數據中心300中。進一步地，雖然主機400可配置成在一些實施方式中只實現與鍵映射有關的功能，但在其它實施方式中，主機400可實現與存儲服務系統的其它元件有關的功能。例如，在一個實施方式中，各個主機400還可配置為位存儲節點160 ,因而可存儲鍵映射數據以及對象數據。
圖11B更詳細地示出鍵映射實例140a的示例性實施方式。在所示實施方式中，包括在鍵映射實例140a內的每個主機400a-c包括相應的分區索引410a-c和任意數量的程序塊(brick ) 415。 一般而言，程序塊415可相應於鍵映射實例140內的中間鍵映射數據結構。在一些實施方式中，如下面結合圖12的描述更詳細描述的，鍵映射數據可在程序塊415中間分成分區，以及在鍵映射實例140內分區的複製可出現在程序塊級。分區索引410可配置成為程序塊415編索引，以便於選擇一個或更多特定的程序塊415來在鍵映射操作期間進行處理。例如，分區索引410可配置為樹或另一適當的數據結構。在一個實施方式中，分區鍵映射實例140內的索引410以及較深層的索引級可配置為稱為分層的不平衡樹或特裡結構(trie )的特定類型的數據結構的一部分，這在隨後的部分中被詳細描述。在所示實施方式中，鍵映射實例140進一步包括鍵映射協調器412。 一般而言，鍵映射協調器412可配置成實現鍵映射訪問管理、內容管理和同步方法或協議，例如下面更詳細描述的那些方法或協議。注意，雖然示出鍵映射協調器412與主機400不同，但在一些實施方式中，它可實現為在一個或更多主機400內的過程或模塊。還注意到，在一些實施方式中，分區索引410可在鍵映射協調器412內而不是分開地在主機400內實現。
圖11C示出包括程序塊415a-n的主機400a的示例性實施方式。如所示，每個程序塊415a-n包括相應的塊索引420a-n以及任意數量的塊425。一般而言，塊425可相應於鍵映射實例140內的中間鍵映射數據結構，類似於程序塊415 ,但屬於程序塊的抽象級。類似於分區索引410 ,塊索引420可為配置成為程序塊415內的塊425編索引的任何適當的數據結構。 例如，塊索引420在一個實施方式內可配置為分層不平衡樹的一部分。
如圖11D所示，在一個實施方式中，塊425可配置成包括任意數量的 各個鍵映射項目144a-n以及配置成為項目144編索引用於選擇的項目索引 430。如前所述，每個項目144a-n都可包括相應的鍵146a-n以及相應的紀 錄148a-n的指示。
在圖12中概述了在圖11A-D所示的實施方式的鍵映射實例140和鍵 映射項目144之間的等級層次中的關係。在包括多個鍵映射實例140的抽 象的部署層中，特定的鍵映射實例140可參考在抽象的實例層的分區索引 410。參考的分區索引410可識別相應於特定項目144的一個或多個程序 塊415。例如，在所示實施方式中，所有的鍵映射項目都由相應於不同的 程序塊415的三個不同分區複製。給定的程序塊又可通過塊索引420參考 特定的塊425 (未在圖12中示出)，且參考的塊可通過項目索引430指向 特定的項目144。注意，雖然鍵映射可使用例如在圖12中所示的等級實現 來實現，但是其它實現是可能的。泛泛地說，可以設想，鍵映射實例140 可使用將鍵144與紀錄148關聯的任何適當的技術來實現。例如，在一個 實施方式中，鍵映射實例140可使用傳統的資料庫或其它類型的結構化索 引來實現。
注意在圖12的實施方式中的一些等級層次可配置成提供冗與例如， 在部署層內鍵映射實例140的複製以及在分區層的程序塊415的複製)， 而其它層可配置成提供可縮放性。例如，當在鍵映射部署內要被編索引的 項目144的數量增加時，在多個不同層中索引(分區索引410、塊索引420 和項目索引430 )的分布可通過允許索引的每個部分以易於管理的方式擴 大來便於數據結構的縮放。注意，在其它實施方式中，可使用更多或更少 的等級層次以及冗餘和不冗餘層的不同組合。
如同對象30 —樣在鍵映射等級層次內複製的使用可通過降低對各個 複本的損失的敏感度來提高容錯能力。然而，如果在修改出現時不試圖使 鍵映射數據的複本同步，則鍵映射的正確(例如，最近的)狀態可能變得 模稜兩可，這又可導致不可預知的或錯誤的系統操作。在一些實施方式中，鍵映射數據的複製部分可使用原子的或事務處理的語義(例如，兩階段提 交語義)以嚴格同步的方式被更新，其中不將更新向鍵映射客戶報告為完 整的，直到它們關於每個複本被持久和可驗證地完成。雖然原子更新語義 可最小化或甚至消除了使鍵映射數據維持在不一致狀態中的更新的可能 性，但是原子更新的性能可能在相當大規模的分布式環境中相當大地退 化。例如，如果鍵映射數據的複本被廣泛地分布，則從客戶的觀點來看復 本訪問等待時間可相當大地變化，最慢的複本指示完成更新操作所需要的 總時間。而且，如果一個復被失敗，則嚴格的原子更新語義可使客戶停機， 直到故障被糾正，這可導致客戶不可接受的延遲。
可提供比原子協議更好的客戶性能的其它類型的同步協議可在鍵映射 等級內使用。在一些實施方式中，可實現混合同步方法，其中一種類型的
同步協議可相對於特定鍵映射實例140內的複本(例如，在分區層的複本， 如圖12所示)使用，而另一類型的協議可用來同步鍵映射部署內的不同 鍵映射實例140。這樣的混合方法可允許尤其針對在鍵映射等級內的不同 層的複本的使用動態來調整同步開銷。
例如，鍵映射數據訪問可展示參考的位置，以便對特定項目144的重 復請求指向比另一鍵映射實例140更可能的特定的鍵映射實例140(例如， 根據地理、網絡拓撲或另一適當的標準最接近於請求的客戶的實例)o也 就是說，情況可能是，給定鍵映射實例140內的鍵映射數據的複本比在不 同的鍵映射實例140內的相應鍵映射數據可能更可能被給定的客戶訪問。 相應地，在一些實施方式中，給定鍵映射實例140內的複本可使用這種協 議被同步，即該協議可配置成比用於同步不同鍵映射實例140的協議更快 地收斂(例如，以傳播複本中間的變化)b
在一個實施方式中，給定鍵映射實例140內的鍵映射數據複本的同步 可使用適當版本的定額協議(quorum protocol )來執行。 一般而言，根據 定額協議執行的鍵映射數據的複本的更新或修改(包括鍵映射放置和刪除 操作)在該修改相對於至少定額數量的複本被持久地(例如，完全地和持 續地)執行時可被認為相對於請求的客戶完成。類似地，當相同的數據從 至少定額數量的複製本取時，根據定額協議執行的鍵映射項目獲取操作可被認為完成。在一些實施方式中，定額數量可被定義為出現的複本的數量 的簡單大多數，而在其它實施方式中，可使用任意程度超級大多數。注意， 如果不滿足定額要求，則定額協議操作可能不能完成。然而，如果複本的 定額數量小於複本的總數量，則給定的定額協議操作失敗的概率可能小於 原子協議操作的失敗概率，這有效地需要在複本中間的一致而不是定額。
注意，鍵映射實例140可使用除了這裡描述的定額協議以外的定額協議。 例如，多階段提交協議例如Paxos或兩階段提交可用於實現定額類型的鍵 映射語義。
在正常的讀取操作和根據定額協議的更新操作的過程中，例如由於通 訊故障或在複本下層的資源的故障，更新不能傳播到每個複本是可能的。 在一個實施方式中，複本中間的不一致可在讀取操作期間被檢測和修復。 特別地，如果在鍵映射項目獲取操作期間在特定項目144的不同複本中間 檢測到不同的值，則可產生鍵映射放置操作以調整差異。在一個實施方式 中，用作放置操作的基礎的項目144可為具有在讀取的不同值中最近(例 如，數字式或按字母順序地最高的)關聯的時間戳的項目。因此，複本中 間的差異可"即時"被解決，例如，當鍵映射項目獲取操作被處理時，而不 需要不同的過程或操作修復該差異。
在圖13-14中示出了關於配置成實現定額協議的鍵映射實例140的鍵 映射項目放置、獲取、刪除和列表操作的示例性實施方式的操作。在不同 實施方式中，這些方法可在鍵映射協調器過程內實現，這些過程可配置在 例如處於包括在鍵映射實例140內的一個或更多主機400內，或作為鍵映 射實例140內的分離的過程或系統，例如圖11B所示的鍵映射協調器412。 首先參考圖13 ，在塊1300中，鍵映射項目放置操作可當操作在鍵映射實 例140從協調器120或其它鍵映射客戶接收時開始。例如，響應於特定對 象30的相應對象實例存儲到特定的位存儲節點160 ，協調器120可產生鍵 映射項目放置操作，以便更新對象30的項目144來反映存儲的對象實例 的定位器。
鍵映射實例140的等級可接著被導航以識別相應於鍵映射項目放置操 作的複本(塊1302 )b例如，對於圖12的實施方式，可查閱分區索引410以確定哪個程序塊415複製相應於所關心的對象30的項目144。隨後，各 個放置操作可指向識別的複本(塊1304》對於每個放置操作，鍵映射實 例140的剩餘等級可被導航以訪問和修改相應的項目144 (塊1306 )b例 如，在給定程序塊415內，可遍歷塊索引420和項目索引430以便訪問特 定的項目144。 一旦項目144的給定複本被成功地寫入，則相應的放置操 作就可指示成功(塊1308 )b注意，以項目144的相應複本為目標的各個 放置操作可同時執行。相應地，塊1306-1308的多個實例被並行地示出。
可監控各個複本放置操作的成功指示以確定複本的定額數量是否被成 功地更新(塊1310 >例如，在包括三個複本的實施方式中，用於完成鍵 映射項目放置操作的複本的定額數量可能是兩個。如果成功地更新了複本 的定額數量，則可給請求的客戶返回被請求的鍵映射項目放置操作已完成 的指示(塊1312 >如果沒有更新，則監控可繼續。在一些實施方式中， 可實施超時，以便如果鍵映射項目放置操作沒有在處理開始之後的特定時 間段內完成，則該操作可終止且錯誤指示可返回給請求的客戶。在其它實 施方式中，鍵映射項目放置操作可保持無限地掛起，直到它完成。
在一個實施方式中，鍵映射項目刪除操作可實現為放置操作的特殊情 況。在這樣的實施方式中，鍵映射項目144可包括配置為刪除標記或標誌 欄位的附加欄位，且刪除操作可作為配置成將刪除欄位設定到有效狀態的 放置操作來執行(例如，通過將該欄位設定為特定的值，例如'T')b具有宣 稱的刪除欄位的那些項目144可在未來的鍵映射操作期間不予處理。在一 些這樣的實施方式中，分離的過程可配置成通過鍵映射實例144獨立地重 復，以清除具有宣稱的刪除欄位的那些項目144。在其它實施方式中，這 樣的項目144可無限地保持為歷史鍵映射行為的日誌。
圖14中示出了鍵映射項目獲取操作的操作方法的一個實施方式。在塊 1400中，當獲取操作在鍵映射實例140從協調器120或其它鍵映射客戶接 收時操作可開始。例如，響應於來自存儲客戶50的對相應於特定鍵的對 象數據的請求，節點揀取器130或協調器120可產生鍵映射項目獲取操作， 以便獲得相應於特定鍵的定位器，使得位存儲節點160可被訪問以取回如 前面的部分中所述的對象數據。如同鍵映射項目放置操作一樣，鍵映射實例140的等級可接著被導航 以識別相應於鍵映射項目獲取操作的複本(塊1402 )b隨後，各個獲取操 作可指向識別的複本(塊1404 )b對於每個獲取操作，鍵映射實例140的 剩餘等級可被導航以訪問和取回相應的項目144(塊1406 )b —旦項目144 的給定複本被成功地取回，則相應的獲取操作就可指示成功(塊1408 注意，如同上述和在圖13中所示的各個放置操作一樣，以項目144的相 應複本為目標的各個獲取操作可同時執行，且塊1406—1408相應地被並 行示出。
可監控各個複本獲取操作的成功指示以確定定額數量的複本是否被成 功地讀取(塊1410 )b如果沒有，則監控可繼續，直到附加的複本被讀取。 至於上述鍵映射項目放置操作，在一些實施方式中，鍵映射項目獲取操作 可無限地等待下去，直到定額數量的複本被成功地讀取。在其它實施方式 中，鍵映射項目獲取操作可在一段時間之後暫停，其後錯誤指示和/或在此 時可得到的最佳數據(例如，具有最近的時間戳的複製數據)可返回到請 求的客戶。
如果定額數量的複本被成功地讀取，則可確定取回的複本的內容是否 不同(塊1412 )b例如，對照每個其它取回的複本可比較被請求的項目144 的每個複本的總體，或可只比較項目144的某些欄位(例如，記錄148的 某些欄位)o如果根據用於比較的標準，在取回的複本中間沒有差異，則 取回的數據可連同鍵映射項目獲取操作完成的指示一起返回到請求的客 戶(塊1414 )b
如果在複本中間存在差異，則可根據選擇標準選擇一個複本(塊 1416》例如，該標準可包括考慮每個複本的時間戳值，其中可選擇具有 最高時間戳值的複本。接著可使用選定複本的數據來開始鍵映射項目放置 操作(塊1418 >例如，可根據圖13執行放置操作，如上所述。作為放置 操作的結果，可寫入具有選定複本的內容的最初請求的項目144的定額數 量的複本，降低了未來的獲取操作將遇到複本中的差異的可能性。在放置 操作之後，選定複本的數據可連同返回到鍵映射項目獲取操作完成的指示 一起返回到請求的客戶(塊1414、在一些實施方式中，當完成被開始以
61解決差異的放置操作時，在複本中間檢測到差異的情況下完成獲取操作是 可能發生的，而在其它實施方式中，可向請求的客戶指示獲取操作為完成 的，而與隨後的放置操作是否完成無關。
如上所討論的，在一些實施方式中，鍵映射API可支持配置成指示鍵 映射項目144的那些鍵146的鍵映射項目列表或計數操作，該鍵映射項目 144滿足某個標準例如搜索模式。在一個實施方式中，列表或/或計數操作 可實現為鍵映射項目獲取操作的特定情況，其中對滿足給定列表或計數操 作的標準的每個項目144執行相應的鍵映射項目獲取操作。然而，根據定 額協議實際上從多個複本取回項目數據(例如，記錄148 )的額外開銷可 能對鍵映射項目列表或計數操作是不必要的。因此，在一些實施方式中， 與定額協議有關的鍵映射項目獲取操作的那些步驟可從鍵映射項目列表 或計數操作省略。例如，不是識別給定項目的所有複本並為每個複本產生 單獨的獲取操作，如在塊1402-1404中的，對於列表或計數操作，單個復 本(例如，程序塊415 )可被任意選擇，且其相應的等級被導航以便識別 滿足列表或計數操作標準的每個項目144。對於滿足該標準的最終的項目 144 ，相應的鍵146或最終的項目144的計數可返回到請求的客戶，繞過 圖14的與定額有關的處理部分(例如，塊1410-1418 >
在一些實施方式中闢了用於為項目144編索引的不同數據結構以外， 鍵映射實例140還可實現高速緩存。例如，高速緩存可允許指向頻繁使用 的項目144的鍵的鍵映射操作繞過索引數據結構的導航，以便直接訪問相 應的項目144 ,這可提高鍵映射項目獲取操作的效率。此外，高速緩存可 幫助阻止與普通的頻繁地訪問的鍵關聯的主機400變得被鍵映射請求業務 過載。例如，在鍵映射高速緩存分布在主機400中間的一個實施方式中， 鍵的副本可被高速緩存在與為該鍵維持索引數據結構的主機400不同的主 機400上。通過鍵的高速緩存在主機400中間這樣的分布，鍵處理工作量 可更均勻地在主機400中分配。
在一個實施方式中，鍵映射高速緩存可配置成存儲鍵148的散列並被 鍵148的散列而不是鍵本身編索引。下面結合不平衡索引數據結構的討論 更詳細討論的數據散列法可構成用於以固定長度的數據結構表示可變長度的數據例如鍵148的有效技術，該數據結構更容易在鍵映射高速緩存內 管理。此外，各種散列算法可為可能最初不能均勻分布的數據(例如，具 有公有的相當大部分的數據的一組鍵148 )產生均勻分布的散列值，這可 便於鍵映射高速緩存數據在主機400中間的均勻分布。在一些實施方式中， 項目144的內容可連同相應的鍵148的散列值一起存儲在鍵映射高速緩存 中。在其它實施方式中，項目144的指針或其它參考信息可被存儲，而不 是項目144本身的內容。
一般而言，在包括鍵映射高速緩存的鍵映射實施方式中，鍵映射項目 放置和獲取操作可在對上面提供的描述有微小修改的情況下操作。在一個 實施方式中，鍵映射項目獲取操作可首先諮詢高速緩存以確定獲取操作是 否可根據駐留在高速緩存中的數據而被服務。獲取操作在使用用於讀取的 定額協議繼續進行之前可等待來自高速緩存的響應達固定數量的時間。如 果高速緩存在定額協議讀取開始之後返回值，則從高速緩衝存儲器讀取的 該值可被處理且相應的項目144返回，以及定額協議讀取可終止。如果沒 有值從高速緩衝存儲器返回，則從定額協議讀取操作讀取的項目144或指 向這樣的項目144的指針可連同相應的鍵信息一起安裝在鍵映射高速緩存 中。
一般而言，在包括高速緩存的鍵映射實施方式中的鍵映射項目放置操 作可實質上如上所述操作，除了鎖定或其它一致性協議可用於阻止多個放 置操作同時試圖修改相同的高速緩存項目以外。在一個實施方式中，鍵映 射項目放置操作可配置成在開始用於寫入的定額協議之前試圖鎖定相應 於鍵148的高速緩存項目。當接收到來自鎖定請求成功的高速緩存的響應 時(例如，因為不存在對項目的其它鎖定，或因為在高速緩存中沒有相應 的項目)，定額協議可繼續下去。在放置操作根據定額協議結束之後，鎖 定可被釋放，且新項目數據可安裝在高速緩存中。
注意，在一些實施方式中，用於如剛剛描述的鍵映射放置和獲取操作 的定額協議可實現用於更新鍵映射項目狀態的強一致性模型。也就是說， 定額協議可保證一旦對特定鍵的放置操作被客戶確認為完成，則隨後的獲 取操作將返回最近放置的數據，即使不是每個複本都在獲取操作被處理的時間被更新。
當鍵映射操作例如放置和刪除操作指向特定的鍵映射實例140時，在 該特定的鍵映射實例140內的項目144的狀態可隨著時間的過去而改變。 因此，在沒有調整它們的任何企圖時，在部署內的不同鍵映射實例140可 能隨著時間的過去往往變得不同或不一致。如果只有一個存儲服務客戶50 參考給定的對象30 ，並且通過相同的鍵映射實例140這麼做，則這樣的不 同可能沒有實際效果。然而，如果多個存儲服務客戶50通過不同的鍵映 射實例140參考相同的鍵，則這樣的不一致可使客戶50在時間的相同點 觀察到不同的鍵映射狀態和/或不同版本的對象數據。
如前所述，強一致性協議例如原子或定額協議可在更新複本時使用， 以有效地阻止客戶觀察到複本不一致性或根本阻止這樣的不一致性出現。 然而，在不同複本的訪問等待時間有時可相當大地變化的分布式環境中， 強一致性協議可能有高性能成本。例如，對於原子或定額協議，操作完成 所需的時間可相應地為相對於所有複本或定額數量的複本中最慢複本來 說完成操作所需的時間的函數。而且，在沒有強一致性協議時，複本不一 致性變得對客戶可見的概率(例如，存儲服務客戶50獲得失效的鍵映射 或對象數據的概率)可能通常為在被訪問的複本還沒有反映更新時的時間 段期間客戶訪問複本的概率的函數。
對於很多對象30 ，這個後面的概率可能很低。例如，在一些實施方式 中，由存儲服務系統管理的大多數對象30可通過特定的鍵映射實例140 被單個客戶50訪問，在這種情況下從客戶的觀點來看不一致性可能是未 解決的。對於可被多個客戶50訪問的對象50 ,可觀察的不一致性仍然是 不可能的。例如，兩個鍵映射實例140對於特定的鍵在比方說10秒的時 期內不一致。然而，如果在不一致的時期期間對於特定的鍵沒有訪問被執 行(例如，如果相應的對象30的訪問之間的持續時間大於不一致的時期), 或如果被執行的訪問指向較新近更新的鍵映射實例140 (例如，如果最後 更新鍵的狀態的客戶50是通過相同的鍵映射實例140參考鍵的下一個客 戶)，則不一致性可能對客戶50沒有可觀察的效果。因此，在一些實施方 式中，鍵映射實例140可使用力求將鍵映射實例140聚合到一致狀態的不嚴格的同步協議，但其可允許在任何給定的時間在鍵映射實例140中的某 種程度的不一致性。這樣的同步協議可為大多數客戶50提供更好的總性 能，更嚴格的同步對這些客戶50可能是不必要的。在一些實施方式中， 對共享的對象30需要鍵映射數據的更嚴格的訪問同步的客戶50可在他們 本身中間實現附加的協議，而不需要所有的客戶50承受更嚴格的同步的 負擔。例如，共享對特定的一組對象30的訪問的一組客戶50可使用信號 (semaphore )或其它分布式鎖定技術來協調他們對鍵映射數據的訪問。
在一些實施方式中，在鍵映射實例140中間的不嚴格的同步協議可包 括可獨立地實現同步過程的不同方面的不同同步任務的組合。圖15A-B示 出包括兩個不同的同步任務的不嚴格的同步協議的操作的方法的一個實 施方式更新傳播任務在圖15A中示出，而反熵或設定一致任務在圖15B 中示出。首先參考圖15A ，操作在塊1500中開始，其中可檢測到對一個鍵 映射實例140的更新。例如，鍵映射實例140可根據如上所述的定額協議 來接收和完成鍵映射項目放置或刪除操作。
處理鍵映射更新的鍵映射實例140可接著將更新操作轉發到在存儲服 務系統內提供的每個其它鍵映射實例140 (塊1504 )b例如，如果鍵映射 實例140a處理鍵映射項目放置操作，則它可將包括變元、參數等的操作轉 發到鍵映射實例140b和140c。在一個實施方式中，可在沒有驗證或確認 的情況下執行轉發。例如，處理鍵映射更新操作的鍵映射實例可使用"發後 不理(fire and forget )'來轉發操作，進行一次將操作轉發到每個其它鍵映 射實例的嘗試，而不試圖驗證轉發的操作是否在其目的地被接收或如果沒 有接收到則重新發送該操作。使用任何適當的轉發策略可出現這樣的轉 發，例如從發起的鍵映射實例140到多個鍵映射實例140的並行廣播、從 發起的鍵映射實例140到其它實例的順序轉發、基於樹的策略，等等。
接收轉發的操作的那些相關聯的主機400可在本地執行更新操作(塊 1506 )b例如，如果主機400f成功地接收到從主機400a轉發的鍵映射項目 放置操作，則它可執行該操作，好像它從任何鍵映射客戶接收操作一樣。 如果放置操作在主機400f上成功地完成，則鍵映射實例140a和140b可相 對於放置操作被同步。一般而言，可能期望在主機400中間轉發鍵映射更新操作在大部分時 間成功。因此，最小化在轉發這樣的操作中包含的開銷可減少在大多數情 況下在鍵映射實例140中間獲得同步所需的時間和/或帶寬。例如，從轉發 過程消除確認響應或其它類型協議的驗證或信號交換可釋放通信帶寬用 於其它用途，例如以支持包含較大程度的同步業務的較大規模的鍵映射實 現。在很多情況下，通過鍵映射部署(其可通常相應於給定鍵映射項目144 的複本的可能不一致性的窗口)傳播鍵映射更新所需的時間可限制為將操 作轉發到相關聯的主機400所需的通信等待時間以及主機400應用轉發的 操作的處理等待時間。經常地，此總時間可在秒或秒的分數的數量級。
然而在一些實施方式中，在主機400中間鍵映射更新操作的轉發可能 失敗。例如，通信連結失敗可能致使一個主機400不可從另一個主機400 到達，或可使轉發的操作在傳輸中丟失、截斷或否則損壞。可選地，例如 由於暫時的硬體或軟體問題，目標主機400可能不能接收或正確處理準確 轉發的更新操作。如在一個實施方式中的，如果在發起的主機400方面不 試圖驗證或確保轉發的鍵映射更新操作被目標主機400成功地接收並處 理，則個別操作的轉發失敗可能導致在鍵映射實例140中間相對於某些項 目的不一致性。
相應地，在一個實施方式中，在鍵映射實例140中間不嚴格的同步協 議可包括上面提到的並在圖15B中示出的反熵或設定調整任務。該任務可 稱為"反熵"任務，因為通常任務的操作可用來在不同的鍵映射實例140中 間減小差異並增加相似性，因而在鍵映射實例140中間降低可由更新傳播 的隨機或系統故障引入的總熵以正確同步實例。在所示實施方式中，操作 在塊1510中開始，其中發起的鍵映射實例140隨機選擇一起執行特定分 區的調整的另一鍵映射實例140 ,該特定分區如上所述可包括駐留在不同 主機400上的很多複製的程序塊415。
發起的鍵映射實例140可接著與選定的鍵映射實例140交換關於在實 例內的分區的信息(塊1512》例如，在兩個鍵映射實例140的特定主機 400可配置成交換在每個實例內維持的分區索引410的拷貝，分區索引410 又可識別在每個實例內定義的那些程序塊415。根據交換的分區信息，發起的鍵映射實例140可接著識別兩個實例中 分區之間的相應性(塊1514 ),並可調整發起的鍵映射實例140內的每個 分區與選定的鍵映射實例140內的相應分區(塊1516 )b例如，如前所述， 給定鍵映射實例140內的每個分區可在很多程序塊415中複製。在一個實 施方式中，發起的鍵映射實例140可配置成指引分區內的特定程序塊415 (其可稱為"引導程序塊")來與選定鍵映射實例140內的相應分區的相應或 "對等"程序塊415通信，以便調整分區之間的差異。在一個實施方式中， 兩個程序塊415的調整可包含程序塊交換關於包括在每個程序塊415中的 鍵映射項目144內的差異的信息並接著傳播每個鍵映射實例140內的最當 前的信息。例如，如果一個程序塊415在時間戳信息的基礎上確定其項目 144的版本比對等程序塊415的項目更近，則它可將項目數據傳送到對等 程序塊415。隨後，對等程序塊415可執行鍵映射項目放置操作(例如， 根據如上詳細描述的定額協議)以更新項目144的拷貝。
一旦兩個鍵映射實例140之間的分區調整已經完成，則操作就可從塊 1510繼續，其中調整過程相對於另一隨機的鍵映射實例140再次開始。在 不同實施方式中，每個鍵映射實例140可配置成以預定的或動態地確定的 時間間隔執行該過程。例如，調整可以每分鐘一次的靜態速率或以根據隨 機或其它統計概率分布確定的時間間隔出現。在一些實施方式中，調整可 在一定數量的鍵映射訪問出現之後或在對某些個別的、類型的或組的鍵映 射項目的訪問被檢測到之後執行。
—般而言，圖15A-B所示的更新傳播和設定調整或反熵的方法可以互 補的方式操作。在大多數情況下，更新傳播可良好地同步部署內的不同鍵 映射實例140。在由於更新傳播故障出現鍵映射不一致性的那些實例中， 反熵任務可通常操作來調整這樣的不一致性。注意，在一些實施方式中， 反熵任務的執行可能不能保證兩個鍵映射實例140準確地全部同步。然而， 在一個實施方式中，可實現反熵任務以保證其操作不增加兩個鍵映射實例 140之間不一致性的程度。因此，通過重複的應用，反熵任務可便於鍵映 射實例140的收斂。下面結合數據結構的特定實施方式的描述提供了關於 反熵任務的一個特定實施方式的更多的細節，鍵映射實例140可用該數據結構實現。
如圖12所示和上面討論的，在一些實施方式中，除了其他鍵映射實例 140以外，存儲服務系統還可包括複製器鍵映射實例190。在一個實施方 式中，複製器鍵映射實例190可本質上配置成與上述鍵映射實例140相同， 並可使用上面討論的協議參與鍵映射同步。然而，在這樣的實施方式中， 複製器鍵映射實例190可配置成為複製器180而不是協調器120或其它鍵 映射客戶服務。在一些情況下，從其它鍵映射實例140分離複製器鍵映射 實例190可在總體上提高鍵映射性能。例如，當複製器180通過鍵映射重 復以檢查對象30的複本的狀況和數量時，複製器180可產生相當數量的 鍵映射請求業務。如果與代表存儲服務客戶50的請求而產生的鍵映射業 務混合，則複製器鍵映射業務可能消極地影響響應時間或與客戶50有關 的其它服務質量測量。相反，配置複製器180來利用專用鍵映射實例190 可將內部產生的鍵映射業務與客戶產生的業務分離。此外，這樣的分離可 更好地使每種類型的鍵映射實例的實現能夠根據其主要客戶的要求而進 行調整。例如，複製器鍵映射實例190的實現可配置成便於大量並行鍵映 射操作的處理，而不是最小化任何給定鍵映射操作的等待時間，同時鍵映 射實例140可被最佳化而用於服務質量標準的不同組合。然而，注意，不 需要以這種方式分離鍵映射實例140 ,而在一些實施方式中，複製器180 可為鍵映射實例140的客戶而不是專用複製器鍵映射實例190的客戶。
在一個實施方式中，複製器鍵映射實例190還可配置成便於由客戶50 使用的存儲服務系統資源的帳目管理。特別地，複製器鍵映射實例190可 配置成以指示相應項目的額外數據來增加由鍵映射實例140存儲的項目 144 ，所述相應項目承擔為相應的對象30記帳或其它的財務責任。例如， 在圖16所示的實施方式中，示出了複製器鍵映射項目194。在複製器鍵映 射實例190內，項目194可相對於鍵映射實例140的結構和等級與項目144 相同地起作用。然而，在所示實施方式中，項目194包括附加欄位，即， 存儲桶ID196。一般而言，存儲桶ID196可包括存儲桶20的標識符的指示， 該存儲桶20包括相應於鍵146的對象30。這樣的標識符可響應於來自客 戶50的請求，例如如上所述通過網絡服務接口 100或協調器120來定義，以產生其中存儲對象30的存儲桶20。注意，在其它實施方式中，帳目管 理信息不需要完全反映在複製器鍵映射實例190的項目內。例如，在一個 實施方式中， 一些或所有鍵映射實例140的鍵映射項目144可配置成將存 儲桶ID196的指示存儲為例如記錄148或鍵146內的附加欄位。
如上討論的，對象30和存儲桶20之間的關係對鍵映射實例140的一 般操作可以是透明的。然而，假定這種關係一般是靜態的，則通過複製器
鍵映射項目194存儲桶20和對象30的明確關聯可便於客戶50的帳目管 理和記帳。例如，不是明確地向網絡服務接口 100詢問與每個對象30相 關聯的存儲桶20 ,帳目管理過程(其可包括在複製器180或另一模塊中， 或實現為系統內的不同模塊)可配置成根據存儲桶ID196來分類複製器鍵 映射項目194。當完成這樣的分類時，與特定的存儲桶ID196相關聯的所 有鍵146將容易顯而易見。如在記錄148內指示的相應對象30的大小可 接著被合計以確定與存儲桶ID196相關聯的總存儲資源利用。此外，可考 慮對象30的其它特徵，例如與特定對象30相關聯的存儲的類。接著根據 適當的記帳模型可貨幣化資源利用。
在不同實施方式中，代替或除了可便於各種內部系統維護或帳目管理 任務的存儲桶ID 196之外，複製器鍵映射項目194還可包括其它欄位。注 意，在複製器鍵映射實例190不同於其它鍵映射實例140的實施方式中， 這樣的附加欄位的存儲成本可配置成複製器鍵映射實例190。然而，可以 設想，在缺少專用複製器鍵映射實例190的實施方式中，可增加鍵映射實 例140的項目144以包括這樣的附加欄位。
分層的不平衡數據結構
如前所述，在一些實施方式中，存儲服務系統可調整以支持非常大數 量的對象30 ，例如，大約十億或更多。因此，在這樣的實施方式中，每個 鍵映射實例140管理類似數量的項目144。在一些實施方式中，鍵映射實 例140可支持不同類型的分類和/或分組操作，例如在前面部分中討論的鍵 映射項目列表和計數操作。此外，為了支持一致的鍵映射操作，由每個鍵 映射實例140管理的很多鍵可能需要在其它鍵映射實例140中間同步，如 上所述。在很多情況下，由鍵映射實例140提供的鍵映射功能可能對總存儲服 務系統的操作是重要的。例如，如果客戶50選擇不執行對於對象30的特 定實例的基於定位器的訪問，則鍵映射實例140可調解由客戶50執行的 每個基於鍵的對象訪問請求。因此，如客戶50看到的存儲服務系統的性 能可直接依賴於鍵映射實例140訪問和處理鍵映射項目144的效率和速 度。鍵映射實例140的性能又可直接依賴於用於索引和組織項目144的數 據結構，例如用於在圖12的實施方式中實現分區索引410、塊索引420和 項目索引430的數據結構。
設計索引數據結構來支持大規模鍵映射實現中的分類和同步操作可能 提出相當多的挑戰。需要索引大量數據例如資料庫的傳統應用頻繁地使用 傳統的平衡數據結構，例如B-樹或其它類型的平衡樹。 一般而言，當用於 索為給定數量的數據項例如鍵映射項目144吋，平衡數據結構算法試圖根 據被管理的項的數量在平衡數據結構中分布數據項。例如，給定索引的 10,000個鍵映射項目144 ，平衡數據結構算法可試圖在項目144中間選擇 斷點，以便項目分成10組，每組大約1,000個項目。平衡的數據結構算法 可在每組內產生平衡等級的其它層次，例如將大約1,000個項目的每組再 分成五個子組，每個子組大約200個項目。由於數據項被添加到平衡數據 結構和從平衡數據結構刪除，因此數據結構內的組和/或子組可能變得不平 衡。因此，傳統的平衡數據結構算法可通過在組中重新分配數據項而使數 據結構重新平衡，產生額外的組和/或產生額外的等級層次。這樣的重新平 衡在數據項被添加或刪除時可"即時"發生，或可在一定數量的數據項修改 發生或自從最後的重新平衡以來經過一定數量的時間之後出現。
通過以平衡的方式分離數據項，平衡數據結構可為數據結構內的任何 給定的數據項提供可預測的、大致一致的訪問等待時間，這可能是在大量 數據項需要被索引的大規模實現中所希望的。然而，例如使用如上所述的 不嚴格的同步模型，有效地調整或同步分布的平衡數據結構的實例可能特 別困難。特別地，當平衡數據結構的實例被單獨修改時，在每個實例內將 數據項分成組的斷點可變得不同。作為結果，在不同的平衡數據結構實例 的組或子組之間的數據項從屬關係方面可能沒有直接的相應性。因而為了協調兩個這樣的實例，徹底比較兩個實例的整體可能是必要的，這在每個 實例索引大量數據項的情況下可能非常耗費時間。
作為根據數量在組中間分布數據項的平衡數據結構的可選方案，在一
些實施方式中，鍵映射實例140的索引數據結構可配置成實現不平衡數據 結構(其也可稱為特裡結構)，該不平衡數據結構根據每個組內數據項中
間的一些關係在組中間分布數據項。特別地，鍵映射實例140可配置成根 據相應的鍵146的前綴索引項目144。作為例子，考慮存在具有相應的對 情況不敏感的字母數字鍵146的600個鍵映射項目144的情況。這600個 項目的平衡索引可將項目分成三個不平衡組，每組有200個項目。相反， 在一個實施方式中，不平衡索引可定義三個字母數字組，以便以字符a到 l開始的那些項目分配到第一組，以字符m到x開始的那些項目分配到第 二組，以及以字符y或z或數字0到9開始的那些項目分配到第三組。
項目144可不均勻地分布在不平衡索引的組中。例如，在第一組中可 有300個項目，在第二組中250個項目，而在第三組中只有50個項目。 然而，注意，對於任何給定的項目144 ，在不平衡索引的特定組中的給定 項目144的從屬關係可為其相應的鍵146的函數，而不依賴於任何特定的 組內的項目144的數量。因此，如果不平衡索引的兩個實例維持相同的組 定義，則每個組可獨立地同步，而不依賴於其它組。例如，在兩個實例之 間的a-l組可被同步而與m-x組和y-9組無關。相反，如上所述，相同的 項目144的集合的平衡索引的兩個實例的同步可能需要考慮在所有組中的 所有項目。
圖17示出了說明索引很多數據項的不平衡數據結構的使用的一個例 子。在所示實施方式中，不平衡索引200 (或簡單地，索引200 )包括以 等級的方式布置來索引為以前綴"al"開始的很多字符串值的很多節點210。 例如，被索引的值可相應於鍵映射實例140的不同項目144的鍵146。索 引200內的每個節點210包括可以直接相應於或可以不直接相應於被索引 的數據項的相關的標記值。在所示實施方式中，被描繪為橢圓形的節點可 相應於沒有相應的數據項的索引200的內部節點，而被描繪為矩形的節點 可相應於被索引的數據項。因此，例如，節點210a相應於字符串"al"並與索引200內的很多其它節點有關，但可能不存在相應於字符串"al"的實際鍵 146。相反具有標記"Alicia"的節點210n可相應於指定相同字符串的鍵146。 內部和非內部節點210之間的區別可以明確反映或可以不明確反映在節點 210的狀態中。
如下所述，在一些實施方式中，不平衡數據結構可配置為其它索引的 索引。在一些這樣的實施方式中，在索引200的第一實例內索引的數據項 可為另一索引200的根節點210 ，且第一索引200內的相應節點210可被 考慮為非內部節點。也就是說，在一些實施方式中，給定索引200的非內 部節點210可一般被定義為與數據值相關聯的任何節點210 ,例如另一索 引200的項目144或根節點，所述另一索引在給定索引200的外部。類似 地，給定索引200的內部節點可只涉及給定索引200內的其它節點210 ， 並且可不具有與項目144或不同於給定索引200的其它索引200的任何關 聯。還注意到，如圖17所示，非內部節點210不必為葉節點(例如，不 涉及在較低等級層次的其它節點的節點)b
在不同實施方式中，每個節點210可編碼各種信息。在圖18中示出了 說明可在節點內編碼的不同數據欄位的一般節點210的一個實施方式。在 所示實施方式中，節點210包括標記欄位212、計數欄位214、指紋欄位 216以及一個或更多指針欄位218。通常，標記212可配置成存儲相應於 給定節點210的值，該值可被使用在遍歷或利用索引200的過程中，如下 面更詳細描述的。在一些實施方式中，標記212可唯一地識別索引200內 的所有節點中的一個節點210。此外，在一些實施方式中，給定節點210 的標記212可包括作為前綴的索引200內給定節點210的所有直接的先輩 的標記。也就是說，通過將某個值附加到該給定節點的直接的父節點210 的標記212 ，可確定任何給定節點210的標記212。例如，考慮圖17的具 有標記"alicia"的節點210n。節點210n的直接先輩節點2101 、 210k和210a 中的每個都具有形成節點210n的標記的適當前綴的標iE(分別為"alic';"ali" 和"al")b
如圖17所示某些節點210指向在索引210的等級中進一步在下面的 一個或更多子或後繼節點210。在一個實施方式中，指針欄位218可配置成將數據反射指針或參考從給定節點210存儲到另一節點210。例如，給 定的指針欄位218可包括識別地址空間例如存儲器地址空間內參考的節點 210的位置的地址。給定的指針欄位218還可包括關於參考的節點210的 額外的標記信息。例如，如圖17所示，從給定節點210到後繼節點210 的每個弧線標註有後繼節點210的標記212的第一字符，該字符不同於由 給定節點210的標記212形成的前綴。在一個實施方式中，此附加的標記 信息可連同指向該參考的節點210的指針一起存儲在相應的指針欄位218 內。例如，包括在節點210a中的指針欄位218可分別包括對節點210b、 210g、 210j、 210k和210t的參考以及相應的標記數據"a';"erfri"和"z'二
如上面關於圖12討論的，索引例如索引200可用於組織數據項例如鍵 映射項目144用於選擇。在一些實施方式中，非內部節點210 (即，直接 映射到被索引的數據項的節點210 )的指針欄位218還可包括指向相應的 數據項，例如鍵映射項目144、塊425或程序塊415的指針。在一些實施 方式中，如下面更詳細描述的，不平衡索引例如索引200可分等級地實現， 以便一個索引200的非內部節點210可指向另一索引200。參考被索引的 數據項的指針欄位218可通過任何適當的技術與參考另一節點210的指針 欄位218區分開，例如通過對不同類型的指針欄位218使用不同的編碼。 例如，如在前面的段落中描述的，在與到後繼節點210的弧線關聯的標記 信息被在指針欄位218內編碼的實施方式中，無標記用於將對被索引的數 據項的參考與對後繼節點210的參考相區分。
對於給定的節點210 ,計數欄位214和指紋欄位216可配置成反映在 給定節點210之下的節點210的狀態。在一個實施方式中，計數214可配 置成存儲作為給定節點210 (例如，分屠地在下面)的子孫的所有節點的 計數。例如，圖17的節點210k在索引200內在其下有八個其它節點210。 相應地，它的計數214可使用任何適當的編碼或格式指示8的值。
在不同實施方式中，給定節點210的指紋欄位216可配置成存儲指示 對分等級地在給定節點210下面的節點210的數據的某個部分執行的散列 (例如，適當的散列算法的結果)的值。例如，給定節點210的指紋欄位 216可反映作為給定節點210的子孫的所有節點210的標記212的散列的和。可選地，指紋欄位216可根據特定的、 一致的遍歷順序(例如，橫向 優先或深度優先的遍歷)來反映後繼節點210的標記212的串連的散列。 在其它實施方式中，除標記212外的節點210的其它欄位可參與散列。在 一些實施方式中，與給定節點210相關聯的數據可反映在其自己的指紋字 段216內，而在其它實施方式中，給定節點210的指紋欄位216可根據其 後繼節點而被嚴格地確定。為了描述的一致性，如在這裡使用的，給定節 點210的指紋可表示作為給定節點20的至少一些後繼節點的函數的散列 值，同時給定節點210的散列可表示作為只與給定節點210關聯而不與其 子孫關聯的數據的函數的散列值。
一般而言，散列算法可配置成將可能任意長度的給定的源數據值映射 到較小的一般固定長度的散列值上，以便如果兩個散列值不同，則原始的 源數據值也必須在某個方面不同，其中兩個散列值從所述原始的源數據值 產生。當散列算法一般不是一對一的函數時，兩個散列值之間的一致性不 必暗示原始的源數據值之間的一致性。然而，對於一些類別的散列算法， 原始的源數據值與給定的完全相同的散列值之間的一致性在統計上可能 處於可以計量的概率或信任度內，特別是對於表現某種冗餘度的源數據值 來說。不同類型的散列算法也可稱為符號差、指紋或校驗和算法。可以設 想，可使用任何適當類型的散列算法來產生將存儲在指紋欄位216中的散 列值，作為非限制性的例子包括任何適當版本的消息摘要5( MD5 )算法 或安全散列算法(SHA ),例如SHA-、SHA-256、 SHA-512等。
如在前面部分中描述的，可對鍵映射實例140執行的基本操作可包括 放置和獲取操作，其可分別存儲和取回相應於被指定為操作的參數的鍵的 項目144。在一些實施方式中，鍵映射實例140內的不同索引可實現為不 平衡索引，例如索引200。
在大量數據項需要被編索引的場合，如可能在鍵映射實例140中共用 的，對所有數據項使用索引200的單個實例可能是不實際的。例如，單個 大的索引可能不完全適合於處理索引的系統的存儲器，這可消極地影響依 賴於索引的操作的性能。在一些實施方式中，使用分層的不平衡數據結構 或分層的索引可實現大的索引。 一般而言，在分層的索引中，索引200的多個實例可被分等級地定義，其中在等級中較高處的實例可索引其它索引
200 ，以及在等級中較低處的實例可索引特定的項目144或其它項目(例 如，塊425或程序塊415 )b
在圖19中示出了分層索引的一個實施方式。在所示實施方式中，分層 索引220包括五個索引200a-e。索引200a包括節點210u-x ,其中每個都 是涉及索引200b-e之一的相應根節點的非內部節點。索引200b-e每個又 包括圖17示出的各個節點210a-t。在分層索引220的一些實施方式中，較 高層索引例如索引200a可配置成駐留在處理索引的系統的存儲器、高速緩 存或另一較高層的存儲器等級中，而較低層索引例如索引200b-e可主要駐 留在磁碟或這樣的存儲器等級的另一較低層中。在這樣的實施方式中，較 低層索引可例如使用分頁(paging )型技術按需要從存儲器等級的較層重 新定位到較高層。通過支持大量數據項的索引的等級分區，分層索引220 可更高效和有效地使用系統資源。
例如，使用上述分頁技術，分層的索引220的頻繁使用的索引200可 保持在存儲器等級的較高層，這些較高層一般訪問得較快但在容量上被限 制，而較不頻繁使用的索引200可存儲在較低的存儲器等級層次中，這些 較低層一般訪問得較慢但具有比較高層更大的存儲容量。可以設想，在一 些實施方式中，當節點210添加到分層索引220內的索引200時，各個索 引200可增長到超過目標大小(例如，在實現索引的系統上磁碟塊或存儲 器頁面的大小 >> 在這樣的實施方式中，如果給定索引200增長到超過目 標大小，則它可分裂成兩個或更多索引實例。在執行這樣的分裂的過程中， 節點210可按需要添加到較高層索引200中，以構成新索引實例。
響應於鍵映射項目放置或獲取操作，可遍歷分層的或不分層的不平衡 索引以確定指定的鍵是否相應於索引200內的節點210。在圖20中示出了 不平衡索引遍歷方法的一個實施方式。在所示實施方式中，操作在塊2000 中開始，其中索引內待搜索的鍵值(也稱為搜索值)例如通過相關的鍵映 射操作被指定。隨後，選擇索引的根節點210 (例如，沒有父節點的節點 210 )(塊2002 )b
對於選定的節點210 ，對照搜索值比較該節點的相應標記值212以確定該標記值是與搜索值確切地匹配，是搜索值的前綴，還是兩者都不是(塊
2004 )b如果選定節點210的標記值212與搜索值匹配，則檢查選定的節 點210以確定它是內部還是非內部節點(塊2006-2008 )b例如，可檢查選 定節點210的指針218或其它內容以確定節點是否參考由索引200索引的 數據值，例如項目144或索引200的另一實例。如果選定的節點210是內 部節點，則可能出現索引失敗，如下所述(塊2022 )b
如果選定節點210是非內部節點，則取回由選定節點210參考的數據 值(塊2010 )b在支持分層的不平衡數據結構的實施方式中，其中一些數 據結構實例可索引其它數據結構實例，取回的數據值可相應於項目144或 索引200的另一實例的根節點。如果取回的數據值是項目144 ,則索引遍 歷可結束，且取回的項目144可被根據發起遍歷的鍵映射操作來處理(塊 2012-2014 )b例如，如果發起的鍵映射操作是獲取操作，則取回的項目144 可被作為獲取操作的結果返回。如果發起的鍵映射操作是放置操作，則取 回的項目144可根據在放置操作中指定的參數來修改。
如果取回的數據值不相應於項目144 ，則在所示實施方式中，它可相 應於另一索引200的根節點210。相應地諒根節點210可被選S(塊2012、 2016 ),且操作可從塊2004繼續進行，在塊2004中新選擇的索引200的 遍歷可繼續進行。因此，在一個實施方式中，圖20的方法的執行可繼續 進行，直到相應於搜索值的節點210的存在或沒有被最後確定。
返回到塊2006 ,如果選定節點210的標記212與搜索值不匹配，而是 搜索值的前綴，則可檢查選定節點210的子孫以確定是否任何子孫相應於 搜索值(塊201S >>如果是這樣，則可選擇相應的後繼節點210(塊2020 )， 且操作可從塊2004繼續進行。在一個實施方式中，可檢查選定節點210 的指針218以確定與特定指針218關聯的額外的標記信息在與選定節點 210的標記212結合時是否也形成搜索值的前綴(或完全匹配)b例如，參 考圖17 ,節點210a的標記"al"可被確定為"alibaba"的搜索值的前綴。此外， 可由相應的指針218表示的、從節點210a到節點210k的弧線與額外的標 記信息"i"相關聯。該標記信息在附加到節點210a的標記"al"時形成值"ali"， 該值"ali"也是搜索值的前綴。因此，可選擇節點210k用於進一步的遍歷。返回到塊2018 ，如果選定節點210的子孫不相應於搜索值，則搜索值 在索引200內沒有相應的項目144 ，這也可稱為索引失敗(塊2022》該 索引失敗可接著根據發起索引遍歷的鍵映射操作的類型來處理(塊2024 )b 例如，鍵映射項目獲取操作可通過將表示失敗的適當的狀態指示返回到請 求的客戶來處理索引失敗。相反，鍵映射項目放置操作可通過將相應於待 存儲的項目144的新節點210插入索引中作為選定節點210的子孫來處理 索引失敗。例如，新節點210可被創建，且其為待存儲的項目144適當地 設置不同的欄位，以及指向新節點210的指針218可存儲在選定節點210 內。注意，如果新節點210被添加到索引200或現有的節點210被修改， 則添加或修改的節點210的所有先輩節點210的計數欄位214和指紋欄位 216可被更新以反映該變化。
返回到塊2006 ，如果選定節點210的標記212與搜索值不匹配且不是 搜索值的前綴，則索引失敗也可能出現，且處理可從塊2022繼續。在一 些實例中，這種情況可出現在選定節點210不是索引200的根節點時。相 應地，在一個實施方式中，響應於此失敗情況將新節點210添加到索引200 可包括創建具有標記212的新的根節點210 ，該標記212是搜索值和現有 根節點210 (在這種情況下為選定節點210 )的標記212的共同前綴。(在 一些實例中，新根節點210的共同前綴可為零，這可解釋為用於任何值的 有效前綴。)新的根節點210可接著配置為將選定節點210稱為子孫。如 果必要，額外的節點210可產生以相應於搜索值並配置為新的根節點210 的額外子孫。
注意，在一些實施方式中，當遍歷分層的不平衡索引200時，如果選 定節點210的標記212與搜索值不匹配且不是搜索值的前綴，則索引失敗 可能不立即出現。在一個實施方式中，如果遇到這種情況，則如果選定節 點210有父親，則選擇父節點210。如果父節點210是參考另一索引200 的非內部節點，則可選擇參考索引200的根節點210 ，且處理可從塊2004 繼續。否則，可能出現索引失敗。(然而，注意，這種情況可能不出現在 沒有索引其它索引200的不分層的自含式索引200中。)作為這種情況的 例子，考慮圖19的分層索引，其中搜索值為"alice'糹索引200a的遍歷可繼續進行到具有標記"ali"的節點210w。因為節點210w具有包含相關聯的標 記信息"c"的指向子節點210x的指針，因此可選擇節點210x。然而，節點 210x的標記是"alicia",該標記與搜索值不匹配並且不是搜索值的前綴。因 此，遍歷可返回到節點210w (節點210x的父親)，其可為參考索引200c 的非內部節點。相應地，遍歷可繼續到節點210k並最終到節點210m ,節 點210m具有與搜索值匹配的標記212。
在不同實施方式中，不平衡索引200或分層的不平衡索引220可用於 索引鍵映射實例140內的鍵映射項目144。例如，分層的索引220可用於 實現一個或更多分區索引410、塊索引420或項目索引430 ，或可在鍵映 射實例140內實現的任何其它層的索引。如上討論的，當使用不嚴格的同 步協議時，不同的鍵映射實例140可在操作的一般過程中不同或不一致。 在一些實施方式中，鍵映射實例140可使用窮舉協議來被同步，該協議以 一致的順序(例如，深度優先或橫向優先的搜索順序)遍歷相應的索引數 據結構中的每個節點以識別在索引結構或被索引的內容中的差異。然而， 上述不平衡索引的各種特徵，例如根據鍵信息而不是鍵的數量的數據的分 布以及在索引數據結構內包含計數和/或累積散列信息可便於計算上更有 效的同步算法的實現。
前面描述的反熵設定調整協議的很多可能的版本可設想成用在由鍵映 射實例140實現的不平衡的、可能分層的索引上。接著是這樣的協議的一 個實施方式的描述，雖然應理解，對一般協議所設想的變形可展示不同的 實現優先級，例如在選擇最佳化某些情況而優先於其它情況或使用一種或 另一特定類型或類的算法來執行協議的一般步驟中。因此，意圖是所述實 施方式被視為說明性的而不是限制性的。
在一個實施方式中，配置成調整不平衡索引200或分層的不平衡索引 220的不同實例的反熵協議可包括在不同類型的消息的實例之間的交換。 反熵協議的一個實施方式可基於的示例性的一組消息可包括DATA消息、 REQUEST消息、HASH消息、FILTER消息和FINGERPRINT消息。下面 描述了這些消息中的每個的相應的實施方式的一般功能，接著是消息可如 何用於實現反熵協議的實施方式的討論。在下列討論中，可參考鍵映射實例140中間數據的交換，雖然應理解，這樣的鍵映射實例可實現包括上述 特徵中的任何一個的不平衡索引200或分層的不平衡索引220的一個或更 多實例。
DATA消息可用於將關於一個或更多索引節點210的數據從一個鍵映 射實例140傳送到另一個。在一個實施方式中，DATA消息可配置成只傳 送與給定節點210關聯的標記212 ,而在其它實施方式中，DATA消息可 傳送與給定節點210關聯的其它欄位。在一些實施方式中，如果給定節點 210是非內部節點，則DATA消息還可包括與給定節點210關聯的數據項 的所有或一些部分(例如，項目144或關於另一索引200的根節點210的
j曰 ,、 )b
HASH消息可用於將關於一個或更多索引節點210的信息從一個鍵映 射實例140傳送到另一個，而沒有明確傳送給定節點210的欄位或與給定 節點210關聯的數據項。在一個實施方式中，HASH消息可配置成傳送與 給定節點210關聯的標記212以及根據適當的散列算法計算的給定節點 210的散列。在一些實施方式中，給定節點210的散列還可反映與給定節 點210關聯的數據項(例如，鍵映射項目144)，但可排除給定節點210的 任何子孫。
REQUEST消息可用於傳送對與一個或更多節點210關聯的消息的請 求。在一個實施方式中，REQUEST消息可配置成傳送一個或更多標記前 綴值。在響應中，請求的實例可能期望接收關於具有標記212的那些節點 210的信息，對該標記212來說，傳送的標記前綴值實際上是前綴。對於 給定的節點210 ，接收的信息可包括給定節點210的相應欄位的內容和/或 相應於給定節點210的數據項(例如，鍵映射項目144 )b在一些實施方式 中，REQUEST消息可支持被請求的標記前綴值的進一步的限定，例如通 過指定由特定的標記前綴值界定的結果空間內的值或值的範圍應從為該 標記前綴值返回的結果中排除。例如，REQUEST消息可指定關於與標記 前綴值"alex"匹配的所有節點210的信息應被返回，除了與前綴"alexe"或 "alexj"匹配那些節點210之外。
剛剛描述的消息可通常在各個節點210的粒度層(level of granularity )操作。然而，如果鍵映射實例140之間的差異通常很小(例如，限制到大 多數節點210)則它可促進同步過程以立刻快速確定多個節點210的狀態。 在一個實施方式中，FINGERPRINT和FILTER消息可配置成傳遞關於節 點210的集合的消息。特別地，在一個實施方式中，FINGERPRINT消息 可配置成將節點210的指紋欄位216連同其標記212 —起從一個鍵映射實 例140傳送到另一個。如上所述，給定節點210的指紋欄位216可配置成 存儲被確定為給定節點210的子孫的函數的散列值。因此，如果在不同鍵 映射實例140中相應節點210的指紋欄位216相等，則相應節點210的子 孫的布置和內容相同可能是非常可能的(取決於所使用的散列算法的特 徵 >> 也就是說，從相應的節點210傳下來的鍵映射實例140的部分被同 步是非常可能的。
指紋的使用可允許關於包括相當數量的節點210的鍵映射實例140的 部分是否被同步的快速確定。然而，指示相應的部分沒有同步的指紋通常 可能不提供關於這些部分如何不同的進一步的細節。在一個實施方式中， FILTER消息可配置成將編碼相應於特定前綴值的很多節點210的過濾值 從第一鍵映射實例140傳送到第二鍵映射實例140。第二實例可接著使用 接收到的過濾值來檢測其自己的相應於該前綴值的節點210 ，以確定第二 實例的哪些節點不存在於第一實例中，如果有的話。
在一個實施方式中，由FILTER消息傳送的過濾值可為Bloom過濾器， 雖然可以設想，可使用用於可恢復地將一組數據值編碼成過濾值的任何適 當的過濾技術。 一般而言， 一組值(例如，節點210 )的Bloom過濾器可 相應於M位二進位值，其中M為整數。在任何值編碼到Bloom過濾器中 之前，它的初始值可為零。也就是說，過濾器的所有位可處於復位無效的 狀態中。可通過藉助於一組k個獨立的散列函數中的每個來傳遞將在過濾 器內被編碼的每個值可填充(populate )Blo謹過濾器，其中每個函數將待 編碼的值映射到範圍
內的值上。對於k個最終的散列值中的每個， Bloom過濾器內的相應位被置位有效(例如，設定為邏輯1值)b根據將在 Bloom過濾器內編碼的值的數量和類型以及期望的假陽性(false positives ) 的概率，M和k可選擇為設計參數(下面討論)b例如，在使用八個散列函數的1,024位Bloom過濾器中，每個散列函數可產生將過濾器的1，024 位的特定一位指定為置位有效的相應的IO位散列值。
為了測試給定的值是否被編碼到Bloom過濾器中，該值被傳遞通過用 於編碼過濾器的同一組k個獨立的散列函數，且最終的過濾值的k個位被 檢查。如果最終的過濾值的k個位中的任何一個不是被置位有效的，則測 試值確定地不能在過濾器內編碼。也就是說，測試值可能最初在過濾器內 被編碼，或它可為假陽性的。在一些實施方式中，在產生Bloom過濾器的 每個獨立的時機，可用隨機或自動產生的鹽值(salt value )或種子值(例 如，作為當前系統時間的函數)確定散列函數的參數，以減小當給定的一 組值被相繼地編碼到過濾器中時將產生相同的假陽性值的概率。
因此，例如，第一鍵映射實例140可將相應於前綴P的一組節點(A ， B , C ， D ， E)編碼到Bloom過濾器中，並可使用FILTER消息將過濾器傳 送到第二鍵映射實例140。在第二鍵映射實例140中，一組節點(A ，B ，X ， Y , Z)可相應於前綴P。第二鍵映射實例140可對照過濾器測試每個節點， 並可確定節點A、 B和X可在過濾器中編碼，而節點Y和Z確定地不能在 過濾器中編碼。因此，第二鍵映射實例140可正確地斷定節點Y和Z不存 在於第一鍵映射實例140中，並可斷定節點A、 B和X可能存在於第一鍵 映射實例140中，其中X是假陽性。作為結果，第二鍵映射實例140可採 取行動來將關於節點Y和Z的信息傳送到第一鍵映射實例140。
可以設想，DATA、 HASH、 REQUEST、 FINGERPRINT和FILTER消 息可根據任何適當的協議或API來實現和傳送，並可包括各種類型的欄位 或參數，這些欄位或參數配置成傳送上述信息以及解碼並正確地處理消息 所必需的任何額外的信息。在一個實施方式中，消息可包括額外的參數， 所述額外的參數指示對於包括在該消息中的給定標記值來說，發送鍵映射 實例是具有相應的數據還是需要相應的數據，其分別稱為獲取數據和需要
數據參數。例如，如果鍵映射實例140為具有標記"al"和某個數量的子孫的 節點210發送FINGERPRINT消息，則實例可包括指示該實例在由"al"界定 的前綴空間內有一些節點210的獲取數據參數。實例還可包括需要數據參 數，例如如果它的由"al"界定的前綴空間的拷貝被認為是不完整的情況下。在一些實施方式中，獲取數據參數可能在DATA和HASH消息中是隱含的， 而需要數據參數可能在FILTER和REQUEST消息中是隱含的屋然DATA 或HASH消息可明確指定需要數據參數，而FILTER或REQUEST消息可 明確指定獲取數據參數。在一個實施方式中，可能需要FILTER消息來指 定需要數據或獲取數據參數中的至少一個。
在一個實施方式中，由兩個鍵映射實例140管理的反熵協議可在兩個 實例建立彼此的聯繫時開始。每個實例可假定它具有某些數據和缺少某些 數據。相應地，每個實例可向其它實例發送FUNGERPRINT消息，其指定 實例的根節點210的標記212和指紋216並包括獲取數據和需要數據參數。 例如，在使用分層的不平衡索引220的鍵映射實例140的實施方式中，根 節點210可相應於在索引200內沒有父節點的節點210 ，該索引200沒有 父索引或上級索引200。
在圖21中示出了處理FINGERPRINT消息的方法的一個實施方式。在 所示實施方式中，操作在塊2100中開始，其中FINGERPRINT消息從消 息發送器接收。例如，第一鍵映射實例140可將包括標記值、指紋和一個 或更多獲取數據或需要數據參數的FINGERPRINT消息傳送到第二鍵映射 實例140。在收到FUNGERPRINT消息之後，接著遍歷消息接收器的索引 以識別這種節點210是否存在，即對節點210來說接收的標記值是相應的 標記欄位212的前綴(或確切地匹配)(塊2102 )b例如，使用圖20的方 法或其適當的變形從根節點210開始可遍歷鍵映射實例140的索引。
如果接收的標記值不是任何節點210的標記欄位212的前綴或確切匹 配，則相應於由FINGERPRINT消息參考的節點的節點210可能不存在於 消息接收器。相應地，通過將REQUEST消息傳送到消息發送器，指定包 括在最初接收的FINGERPRINT消息內的標記值，可響應接收靜塊2104 )b 在一個實施方式中，REQUEST消息的處理可繼續進行，如下面更詳細描 述的。在一些實施方式中，只有當接收的REQUEST消息指示獲取數據參 數時才可傳送REQUEST消息。
注意，在一些實施方式中，在反熵協議的操作期間交換的各個消息的 完成可能不依賴於額外的消息是否響應於給定的消息成功地完成而產生的。也就是說，在一些實施方式中，各個消息的處理可相對於其它消息以 無狀態和異步的方式出現。在這裡描述的示例性實施方式的討論中，採用
此無狀態的異步模型。因此，在REQUEST消息產生之後，FINGERPRINT 消息本身的處理可被考慮為完成的(塊2106 )b然而，該模型對反熵協議 的一般操作不是必須的，且可以設想，在可選的實施方式中，任何給定的 消息可阻止、等待或另外地維持與從屬地或響應於給定消息而產生的消息 的同步。例如，在一些實施方式中可使用顯式信號交換、確認、重試或其 它類型的協議，以將一個消息的完成的狀態傳送到另一相關的消息。
如果接收的標記值確實相應於在消息接收器的特定節點210的標記 212的前綴或匹配，則可對照特定節點210的指紋欄位216比較接收的指 紋值以確定兩個指紋是否匹配(塊2108 )b如果是這樣，則消息發送器和 消息接收器相對於接收的標記值同步是非常可能的(例如，服從使用的指 紋算法產生衝突的或具有相同的值的兩個指紋的的概率，儘管指紋是從不 同的數據產生)。例如，使接收的標記值作為前綴的任何節點210在 FINGERPRINT消息被發送的鍵映射實例140和該消息被接收的鍵映射實 例140內處於相同的狀態是非常可能的。因此，沒有額外的消息可響應於 FINGERPRINT消息而產生，且消息可被考慮為完成的(塊2106 )o
如果指紋不匹配，則消息發送器和消息接收器相對於接收的標記值不 同步，可能需要額外的工作來使發送器和接收器一起在狀態上較接近。如 上所述，FILTER消息在允許發送器將關於某些節點210的特定信息傳遞 到接收器方面可能是有用的。然而，在一些實施方式中，可編碼到FILTER 消息中同時保持合理的假陽性率的節點210的數量可被限制到某個閾值。 如果後繼節點210的數量超過在消息接收器與接收的標記值匹配的節點 210的此閾值，則在發送FILTER消息之前執行額外的FINGERPRINT消 息處理可能是更有效的。
因此，在所示實施方式中，如果指紋不匹配，則可檢查在消息接收器 的特定節點210的計數欄位以確定它是否超過用於FILTER消息處理的閾 值(塊2110 )b如果是這樣，則消息接收器可配置成根據特定節點210的 子節點細分其相應於接收的標記值的索引範圍的部分，其中對於所述特定節點210 ，接收的標記值是前綴(塊2112 )b對於每個子節點210 ,消息接 收器可配置成將相應的FINGERPRINT消息發送回原始的消息發送器，指 定相應的子節點210的標記212和指紋欄位216(塊2114 )b此外，如果在 相應於接收的標記值的索引範圍的部分內有間隔，例如由特定節點210的 子節點所示的，則消息接收器可配置成為為相應於該間隔的標記值發送一 個或更多REQUEST消息(塊2116 )b接收的FINGERPRINT消息的處理 可接著被考慮為完成的(塊2118 )b在一個實施方式中，除了上面的行動 以外，如果接收的標記前綴值是特定節點210的準確匹配，則相應於特定 節點210的HASH消息可返回到消息發送器。
例如，如圖17所示，消息接收器的索引200的特定節點210a可具有 標記"ar以及具有相應的標記"alanralexralfrecT'ali"和"alz"的子節點。這暗 示著消息接收器具有關於以"alan"和"alex"開始的節點210的但是不關於可 能以"alb'ralc"或"ald"開始的節點210的一些信息。相應地，消息接收器可 為節點210a的每個子節點傳送FINGERPRINT消息，以及用於這些子節點 的標記中間的間隔的REQUEST消息。在支持負的REQUEST語法的實施 方式中，消息接收器可傳送用於除了相應於特定節點的子節點的那些標記 以外的標記傳送REQUEST消息。例如，消息接收器可傳送用於除了以 "alan "、" alex "、" alfred "、" ali"和"alz"為前綴的那些標記以外的標記傳送 REQUEST消息。
如果特定節點210的計數值不超過用於FILTER消息處理的閾值，則 如果接收的FINGERPRINT消息包括獲取數據參數，則消息發送器可具有 關於不存在於消息接收器中的節點210的特定信息。相應地，消息接收器 可配置成發送FILTER消息，其中FILTER消息將作為特定節點210的子 孫的每個節點210編碼到過濾器(例如，如上所述的Bloom過濾器)中(塊 2120-2122 )b例如，參考圖17 ，如果特定的節點相應於節點2101 ，則通過 FILTER消息可產生並返回編碼每個節點210m-q的Bloom過濾器。在所示 實施方式中，如果獲取數據參數不包括在原始的FINGERPRINT消息中， 則代替FILTER消息，對於特定節點210的每個子節點，相應的 FINGERPRINT消息可產生並返回到消息發送器。這些FINGERPRINT消息可包括獲取數據參數。在這種情況下，在FILTER或FINGERPRINT消 息產生之後，可完成接收的FINGERPRINT消息的處理(塊2118 )b
在圖22中示出了處理FILTER消息的方法的一個實施方式。在所示實 施方式中操作在塊2200開始其中例如響應於如上所述的FINGERPRINT 消息，包括標記值和過濾值的FILTER消息被從消息發送器接收。 一旦接 收到FILTER消息，就遍歷消息接收器的索引以識別相應於接收的標記值 的特定節點210 (例如，對該特定節點來說接收的標記值是前綴或匹配)， 以類似於上面關於圖21描述的方式(塊2202 )b在一些實施方式中，如果 FILTER消息響應於另一消息而產生，則通常存在相應於接收的標記值的 節點210。
消息接收器可接著對照FILTER消息中提供的過濾值檢測特定節點 210的每個子孫，以識別不以過濾值編碼的那些節點210 ，如果有的話(塊 2204 >對於在消息接收器的沒有以過濾值編碼的每個節點210 ,相應的 DATA消息可返回到消息發送器(塊2206 )b FILTER消息的處理可接著被 考慮為完成的(塊2208 )b如上所述，根據用於FILTER消息的過濾算法 的類型和配置，可能出現假陽性。也就是說，消息接收器可能錯誤地斷定 其節點210中的某些被以過濾值編碼，因而在消息發送器以相同的狀態出 現，然而實際上它們並不是這樣。因此，反熵協議的單次循環不能使得兩 個鍵映射實例140相對於每個節點210變得同步是可能的。然而，可能期 望，在很多實施方式中，反熵協議的單次循環不能使實例變得更加不同， 且可期望協議在某個數量的循環內的重複應用以某種程度的概率收斂，取 決於實例不同的程度和所使用的過濾算法的特徵(例如，給定用於過濾器 編碼的閾值的假陽性的概率)b
在一些實施方式中，HASH、 REQUEST和DATA消息的處理可能比 FILTER和FINGERPRINT消息相當簡單。在一個實施方式中，HASH消 息接收器可試圖識別相應於包括在消息中的標記值的節點210 ，並可接著 計算所識別的節點210的相應的散列值。如果接收的散列值與計算的散列 值匹配則識別的節點210可能已經與消息發送器中相應的節點210同步。 否則，包括接收的標記值的REQUEST消息返回到消息發送器以獲得更新的數據版本。
在一個實施方式中，REQUEST消息的處理可例如使用上述不平衡的索引導航技術，來簡單地包括識別每個節點210的消息接收器，對於該節點210 ，包括在消息中的接收的標記值與相應的標記欄位212匹配或是其前綴。對於每個識別的節點210 ,如上所述配置的相應DATA消息返回到消息發送器。在一個實施方式中，接收的DATA消息的處理可包括識別相應於在消息內指示的標記值的節點210是否存在於消息接收器中。如果不存在，則相應的節點210可被產生並以從消息提取的數據填充(p叩nlate》如果存在，則與現有的節點210關聯的數據和/或其相應的數據值可用從消息中提取的數據代替。在一些實施方式中，只有當接收的數據更新時，才可代替現有節點210的數據。例如，DATA消息可包括相應於在消息發送器的節點210的項目144的內容，且項目144可包括可與消息接收器中相應的時間戳信息比較的時間戳信息，以確定接收的項目144是否比現有的項目144更新。如果是這樣，則接收的項目144可代替現有的項目144。
圖21的一般同步協議的變形是可能的和預期的。例如，在使用具有固定長度的分組(packet )來執行鍵映射實例之間的通信的實施方式中，通過在單個分組內傳送用於多個節點210的多個FINGERPRINT消息而不是相應於特定節點210的單個FINGERPRINT消息可提高帶寬利用。接收這樣的分組的實例可接著能夠快速辨別其索引200中的哪個特定索引與發送器失配，而不需要與發送器交換進一步的消息。例如，如果第一個FINGERPRINT消息不匹配，則接收器可在給分組發送器發布REQUEST、FILTER或其它消息之前考慮分組內的其它FINGERPRINT消息。在這麼做時，接收器可以能夠將差異縮小到數據結構的特定部分，這可減少交換關於已經被同步的數據結構的其它部分的消息的不必要的網絡業務。
通常，可以設想，上面描述的用於使用反熵協議和/或更新傳播協議來執行鍵映射實例調整的任何方法或技術，可通過配置成鍵映射實例140的層上或在實例內的各個主機400操作的鍵映射協調器過程來實現。注意，用於實現用於不平衡數據結構的反熵協議的上述方法和技術的很多變形是可能的和預期的，且上面的討論旨在是說明性的而不是限制性的。例如，一些項目頻繁地與其它、隨機選擇的項目通信以便在整個網絡中分布信息所使用的一般類型的協議可稱為基於閒聊的協議，且可使用基於閒聊的協
議的其它技術或方面來用在鍵映射實例140中間的反熵協議中。在不同實施方式中，上述示例性同步消息(或其它適當的消息)可以不同的方法合併以產生具有不同特徵的同步協議。
此外，雖然上面關於圖17-22描述的分層的索引數據結構和同步技術是在實現用在鍵映射實例140內的有效數據結構的環境中討論的，但是可以設想，這樣的數據結構和同步技術可用在為快速訪問而被索引的大量數據的任何應用中。這樣的應用不必包括例如圖2的系統的對象存儲系統，但可包括資料庫系統、搜索系統或可應用數據索引的任何其它應用。
注意，在不同實施方式中，這裡描述的事件的任何類型的隨機產生或選擇的實現可對隨機數或事件產生使用任何適當的算法或技術。在很多情況下，用於實現隨機方法的計算技術可不產生完全隨機的結果，而更確切地為偽隨機結果。例如，偽隨機算法可指定配置成統計地產生隨機結果的確定性過程。如這裡使用的，"隨機"或"實質上隨機"的數據的產生旨在包括任何適當的偽隨機計算技術以及完全隨機的數據源。
存儲服務組件檢測和管理
在存儲服務系統的大規模高度分布的實現中，可能有分布在整個系統中的圖2中所示的大量不同的系統組件。例如，可能有成百或成千的位存儲節點160的實例、協調器120和鍵映射實例140。管理這樣規模的分布式系統的狀態提出了實際的挑戰。例如，由於計劃的維護、被組件依賴的計算資源的失效、隔離另外功能的組件的通信故障或其它原因，特定系統組件的不同實例可能在任何給定的時間不能使用。此外，在任意或不可預測的時間在一些情況下，部件的新的或以前不能使用的實例可恢復使用。
在一個實施方式中，發現、故障和檢測監控進程(DFDD ) 110的實例可配置成相應地監控存儲服務系統的不同相關聯組件的狀態，以關於這樣的狀態彼此通信，並用接口提供DFDD客戶應用程式，這樣的客戶可通過該接口識別可用於執行系統操作例如鍵映射或位存儲操作的可利用的系統組件。通常，DFDD 110可配置成代表其它部件提供存儲服務系統組件的當前狀態的統一可訪問的視圖。也就是說，不是以多個不同的接口配置存儲服務系統的不同部組，其中所述接口配置與其它、不同組件直接傳輸狀態信息，而是提供或依賴於這樣的信息的每個組件可配置成通過標準
DFDD接口來與DFDD的110的實例通信。在一些實施方式中，DFDD 110可實現為配置成在由作業系統管理的環境內操作的監控進程。然而，在其它實施方式中，DFDD 110可實現為配置成實現這裡描述的功能的獨立或自主的硬體或軟體，而沒有依賴於或從屬於作業系統或其它組件的任何必要。
一般而言，配置成被DFDD 110的實例發現和監控的存儲服務系統組件的每個實例可稱為應用程式實例。例如，給定位存儲節點160的操作狀態或狀況可被配置成由給定位存儲節點160執行的SNM控制器161的實例指示。因此，SNM控制器161可相應於位存儲應用程式實例。類似地，鍵映射實例140的操作狀態可被配置成執行鍵映射實例內的一個或更多主機400的鍵映射管理器的實例指示。每個鍵映射管理器實例可相應於鍵映射應用程式實例。其它類型的應用程式實例是可能的和預期的。例如，在一個實施方式中，每個計算機系統可包括配置成檢測和報告專用系統的操作狀態細節，例如處理器、存儲器、磁碟、輸入/輸出(I/O )或其它系統資源的利用的主機監控器應用程式實例，其中一個或更多存儲服務組件通過所述計算機系統來部署。在一些實施方式中，DFDD 110的每個實例本身可配置為應用程式實例。也就是說，DFDD實例可配置成監控除了其它應用程式實例的狀態外的其自己的操作狀態。
在存儲服務系統內，應用程式實例可一般由應用程式名稱識別並唯一地由相應的應用程式實例標識符(ID )識別。例如，特定的應用程式名稱
可包括識別應用程式實例的一般類型的字符串，例如"鍵映射管理器r位存
儲管理器';"主機管理器"或另一適當的名稱，同時應用程式實例ID可包括唯一地識別應用程式命名空間內的特定實例的字符串。在一些實施方式中，應用程式實例ID可明確地包括應用程式名稱，例如"鍵映射-管理器-4AB8D945';也可使用應用程式實例ID的其它適當的格式。在一個實施方式中，DFDD 110的給定實例可配置成將多個應用程式實例與相應的狀態信息相關聯(例如，通過名稱和實例ID )b例如，在圖23所示的實施方式中，DFDD110包括多個項目111 ，其中每個都可將應用程式名稱112和實例ID U3與實例狀態信息114相關聯。在一些實施方式中，DFDD 110可使用一個或更多表格來反映不同類型的狀態信息114與給定的應用程式名稱112和實例ID113的關聯，而在其它實施方式中，DFDD 110可使用樹、如上所述的不平衡索引、或指示在給定應用程式實例和其相應的狀態信息之間的關聯的任何其它適當類型的數據結構。
注意，在一些實施方式中，應用程式實例ID可包括其自己的任意級別的粒度層的命名空間。例如，在一個實施方式中，給定的鍵映射應用成實例ID可具有開多式〈mapname〉/〈instance〉/〈endpoint〉。術語〈mapname〉可識別鍵項目關聯的特定的鍵映射字典，該鍵項目關聯可通常相應於給定的鍵映射部署。(不同鍵映射部署的鍵映射應用程式實例在DFDD 110的相同實例內被管理是可能的。)術語〈instance〉可例如通過唯一的字符串來識別鍵映射示例140內的指定的主機400。術語〈endpoint〉可識別在所識別的主機400上操作的多個獨立的、在功能上相同的鍵映射應用程式實例之"(例如，作為不同的過程)b在應用程式實例ID內的其它複雜的命名空間是可能的和預期的。
通過DFDD 110而與應用程式實例關聯的狀態信息114可包括各種不同類型的信息。在一個實施方式中，DFDD 110可配置成將對DFDD 110管理的所有類型的應用程式實例來說可共有的全局操作狀態信息存儲在狀態信息114內。例如，如下面更詳細描述的，在一些實施方式中，DFDD110可實現全局操作狀態機，其定義應用程式實例的一組全局操作狀態(或簡單地，全局狀態)以及在該組狀態中間可能的轉換。在這樣的實施方式中，由DFDD 110管理的每個應用程式實例可在任何給定的時間與該組全局狀態中特定的一個關聯，且給定應用程式實例的全局狀態可根據狀態機器和應用程式實例的行為隨著時間而變化。
在一些實施方式中，除了對大不相同類型的應用程式實例可共有的全局狀態信息以外，狀態信息114也可反映對特定的應用程式實例或特定類型的實例可為特定的或定製的操作狀態信息。例如，如果應用程式實例相應於特定的位存儲節點160的位存儲管理器，則其狀態信息114可包括關於在該特定節點上可利用的存儲資源的數量、那些資源的類型的信息(例如，高性能、低性能等)，或可能對位存儲節點的環境特定的任何其它相關的狀態信息。類似地，對於相應於特定鍵映射實例140的鍵映射管理器的應用程式實例，其狀態信息可包括關於由特定鍵映射實例管理的項目144的數量、所使用的或可利用的鍵映射存儲資源的信息，或其它相關的鍵映射狀態信息。在一些實施方式中，選擇何種應用程式實例特定的狀態信息來包括在相應的DFDD項目111內可根據DFDD客戶的要求確定。例如，在幫助協調器120或節點揀取器130從幾個選項中選擇特定的位存儲或鍵映射應用程式實例中，可能有用的狀態信息可包括在那些應用程式實例的DFDD項目111內。
在一些實施方式中，應用程式實例的狀態信息114還可包括關於DFDD客戶可如何訪問實例的信息。例如，狀態信息114可包括網際網路協議(IP )地址和埠號，DFDD客戶可通過該網際網路協議(IP )地址和埠號可建立與應用程式實例的連接。 一些應用程式實例可支持其它類型的接口 ，例如網絡服務接口、公布/預訂接口或其它適當的接口。在這樣的實施方式中，狀態信息114可包括URL或DFDD客戶執行網絡服務請求所必需的其它信息，以預訂公布/預訂通道，或執行建立與應用程式實例的通信所必需的另一種類型的行動。在一些實施方式中，除了或代替應用程式實例訪問信息，狀態信息114可包括關於實例物理地定位在存儲服務系統中的位置的信息。例如，狀態信息114可包括與特定的應用程式實例相應的數據中心300或區域310的標識符。
如上所述，在一些實施方式中，DFDD 100可為各個應用程式實例維持全局狀態信息，該信息可一般指示給定的應用程式實例是否正常地操作，並因而可利用，或處於異常狀態中。在一個實施方式中，配置成通過DFDD 110的實例監控的每個應用程式實例可配置成通常(但不是必需的)以定期的間隔例如某個數量的秒或分鐘向DFDD IIO報告其狀態。這樣的報告可稱為"心跳'i心跳報告可根據任何適當的協議而被傳輸(例如，作為TCP/IP消息、作為網絡服務請求、或根據其它標準的或專用的發送消息協議)，並可在信息內容中變化。作為最低限度的例子，給定應用程式實例
可向僅僅包括應用程式名稱和相應於給定實例的應用程式實例ID的DFDD 110提交心跳。在其它情況下，給定的應用程式實例可包括心跳中的額外狀態，例如本地資源利用的特定狀態。在一些實施方式中，應用程式實例可配置成執行某個級別的自我診斷或自我驗證以在發送心跳之前確定其自己的功能狀態，而在其它實施方式中，應用程式實例可發送心跳而不依賴於任何自我評估。
一般而言，如預期的，如果應用程式實例向DFDD 110發送心跳，則有正常操作的合理預期。如果心跳應被中斷某個長度的時間，則有應用程式實例出現問題的合理預期。圖24示出全局狀態機的一個實施方式，對於作為心跳活動和/或其它參數的函數的每個應用程式實例，該全局狀態機可由DFDD 110維持。在所示實施方式中，新的應用程式實例以NEW狀態在線出現在例如，在它開始操作和向DFDD 110的實例通知其存在並提供應用程式名稱、應用程式實例ID和DFDD IIO初始化相應的項目111所必需的任何其它信息之後不久。 一旦新的應用程式實例是穩定的並準備開始正常操作，它就進入OK狀態。在不同實施方式中，從NEW到OK狀態的轉換可為時間(例如，基於應用程式實例的類型的默認設置時間、應用程式實例自報告、管理員幹涉或這些或其它因素的組合的函數。
在所示實施方式中，應用程式實例可保持在OK狀態中，只要自從實例到DFDD 110的最後心跳以來經過的時間小於故障閾值7)^。例如PFDD110可為每個應用程式實例維持當每次心跳從相應的實例接收時遞增的計數器，並可監控每個計數器(例如，用倒數的計時器)以確定其值在經過7>。"之前是否改變。在一些實施方式中，除了 OK (以及可能NEW )以外的全局狀態可一般稱為異常操作狀態或故障狀態，雖然在這樣的狀態中間可能有區別，如下所述。
如果自從用於應用程式實例的最後心跳以來經過了時間7>。,7 ，則其全局狀態可轉換為 INCOMMUNICADO 。在所示實施方式中，INCOMMUNICADO可用作應用程式實例可能有問題的瞬變狀態指示，但它沒有被最後地確定為永久失效。例如，應用程式實例可暫時停止或掛起，到DFDD的110的心跳消息可被延時或丟失，或如下面更詳細描述的，相對於應用程式實例的當前狀態，DFDD 110的一個實例可能與DFDD 110的另一實例不同步。如果在INCOMMUNICADO狀態中心跳被從應用程式實例接收，則該實例可轉換回OK狀態。在一些實施方式中，DFDD客戶可自擔風險地選擇使用處於INCOMMUNICADO狀態的應用程式實例。
如果應用程式實例不能自動地從INCOMMUNICADO狀態恢復，則可能有影響實例的更嚴重的問題。在所示實施方式中，可能出現兩個可能的故障情況。如FAIL狀態所示的，單獨的應用程式實例可能例如由於基本計算資源不能支持(host )該單獨的實例而失效處於隔離中。可選地，應用程式實例可能由於失去實例和DFDD 110之間網絡通信而失效，如NETWORK SPLIT狀態所示的。例如，由於使存儲服務系統的部分彼此隔離的通信故障，應用程式實例對DFDD IIO的一些實例可能是可操作和可訪問的，但是對於DFDD 110的其它實例不是可操作和可訪問的。
毫無疑問地確定給定的應用程式實例故障是否被隔離或由於網絡分離可能很難。在一些實施方式中，DFDD 110可使用相應的啟發式標準和,,其考慮不同類型的可用信息來進行關於應用程式實例是否應從
定。例如，該標準可要求給定應用程式實伊7在轉換到另一故障狀態之前處於INCOMMUNICADO狀態達到至少閾值數量的時間7^ *。此外，該標準可考慮其它應用程式實例是否也處於INCOMMUNICADO、 FAIL或NETWORK SPLIT狀態中，所述其它應用程式實例與和給定應用程式實例相同的區域310或字符300共享資源或屬於區域310或字符300。例如，如果位於與給定應用程式實例相同的IP位址或位於相同的區域310或數據中心300內的其它地址的其它應用程式實例是OK ，則可能給定應用程式示例的故障是隔離的。相反，如果多個應用程式示例不是OK ,則網絡分離情況可能是更可能的，特別是如果應用程式實例狀態被根據地理或網絡拓撲分組。在一些實施方式中，DFDD 110可配置成除了使用被動地接收的狀態信息以便確定故障的性質以外還詢問被懷疑發生故障的應用程式實例。在一些實施方式中，啟發式標準可配置成根據概率的一些閾值(例
92如，大於50%的概率、大於90%的概率，等等)來確定應用程式實例在概率上是否可能失效。
根據啟發式標準，失效的應用程式實例可轉換到FAIL狀態或NETWORK SPLIT狀態。在一個實施方式中，如果心跳被接收到，則實例可從這些狀態中的任一種轉換回到OK狀態，而在其它實施方式中，這些狀態中的任一個或兩個可為不能恢復的。雖然處於INCOMMUNICADO狀態中的應用程式實例可被假定為具有故障概率的功能性的或可恢復的，但是處於FAIL或NETWORK SPLIT狀態中的應用程式實例可被假定為已經失效了(在一些實施方式中有恢復的可能性)b通常，DFDD客戶可避免選擇處於這些失效狀態的任一個中的那些應用程式實例。在一些實施方式中，DFDD 110可配置成對客戶隱藏關於處於這些失效狀態的任一個中的應用程式實例的信息。
在所示實施方式中，應用程式實例可在轉到FORGOTTEN狀態之前保持在FAIL或NETWORK SPLIT狀態中達到相應的時間段Tc和rree。ver。例如，在FAIL狀態的一些情況下，與失效的應用程式實例相關聯的資源可為了恢復或分析的目的而保存一段時間。如果可能，這樣的資源(例如，位存儲節點160的存儲資源)可接著被初始化，用於重新部署為新的應用程式實例。在NETWORK SPLIT狀態的一些情況下，可能需要做出關於是否在沒有失效的應用程式實例的情況下繼續進行系統操作的決定，且如果這麼做，應採取什麼類別的恢復行動(例如，在剩餘的應用程式實例中間重新產生對象複本，等等 > 在一些實施方式中，失效的應用程式實例不能不轉到FORGOTTEN狀態，直到這樣的恢復行動完成為止。
應用程式實例的FORGOTTEN狀態可以不明確地表現在DFDD 110內。更確切地，在一些實施方式中，它可通過從DFDD IIO刪除應用程式實例的現有狀態信息，例如其DFDD項目111而被標記。一般而言，應用程式實例不能從FORGOTTEN狀態恢復，雖然在一些實例中，可使用通過新狀態分配給被忽略的實例的相同資源來初始化新的應用程式實例。在一些實施方式中，如果當處於FORGOTTEN狀態中時，應用程式實例自動地重新開始發送心跳，則DFDD 110可認識到實例被忽略(例如，不再相應於有效的項目111 )並可指示實例停止操作或重新設置或重新初始化本身。
注意，在一些實施方式中，將全局狀態轉換分解的啟發式算法和轉換 時間參數對不同類型的應用程式實例可能不同，且這些參數中的一些或全
部可由DFDD客戶調節。此外，雖然DFDD客戶通常可詢問DFDD 110 的實例以確定給定應用程式實例的當前的全局狀態，但是在一些實施方式 中，DFDD 110可支持公布/預訂狀態變化通知模型。例如，DFDD客戶可 通過預訂過程告知DFDD 110 ，客戶希望被通知特定應用程式實例或實例 組的所有或某些類型的全局狀態變化。當檢測到這樣的狀態變化時，DFDD 110可接著向預訂的DFDD客戶傳送指示該變化的消息。
應用程式實例常常可配置成向最接近於該應用程式實例的DFDD 110 的實例發送心跳信息。例如，在一些實施方式中，DFDD 110的實例可在 配置成支持一個或更多其它應用程式實例的每個計算機系統上提供，以便 應用程式實例可僅僅通過參考其主機的本地IP位址並使用為應用程式實 例-DFDD通信保留的公知IP埠 ，來容易地訪問DFDD 110的本地實例。 然而，如果應用程式實例向DFDD 110的一些實例而不是其它實例報告其 狀態，則當沒有努力同步其狀態時，部署的DFDD 110的實例可變得不同。
在一些實施方式中，DFDD 110的實例中間的不同可使用類似於上面 關於鍵映射實例140描述的那些同步協議，例如基於閒聊的協議來解決。 然而，在很多情況下，由DFDD 110的實例共同管理的DFDD項目111的 數量可能實質上小於由鍵映射實例140管理的鍵映射項目144的數量。當 是這種情況時，較簡單的調整協議可用於同步DFDD 110的實例。在圖25 中示出了這樣的基於閒聊的協議的一個實施方式的操作的方法。在所示實 施方式中，操作在塊2500開始，其中稱為初始實例的DFDD 110的一個實 例隨機地選擇DFDD 110的另一對等的實例用於同步。在一些實施方式中， 初始DFDD實例有時可根據初始DFDD實例的狀態信息來從目前處於失效 狀態(例如，NETWORK SPLIT )中的那些DFDD實例中間慎重地選擇對 等的DFDD實例。如果初始DFDD實例成功地與明顯失效的對等實例聯繫 和同步，則可有助於從明顯的故障中恢復。
初始實例可接著計算在其項目111內反映的應用程式實例的識別信息的散列值(例如，通過散列應用程式實例名稱和ID ，以及可能地端點或其 它識別信息M塊2502 )b散列值可根據任何適當的散列算法例如MD5算 法來確定。初始實例接著將計算的散列值連同當前應用程式實例狀態信息 (例如，心跳計數、全局狀態信息和/或包括在狀態信息114內的任何其它 信息)的分類列表一起傳送到對等的實例(塊2504 )b狀態信息的列表可 根據在初始和對等實例產生一致的列表的任何標準來分類。例如，列表可 根據應用程式實例名稱和/或ID來分類。
注意，如上所述，在一些實施方式中，與應用程式實例相關的狀態信 息可從包括在心跳消息內的心跳計數信息得到。相應地，在一些實施方式 中，DFDD實例可交換用於應用程式實例的心跳計數信息，並可從接收的 心跳計數信息得到應用程式實例狀態信息，而不是直接從其它DFDD實例 接收狀態信息。因此，在一個實施方式中，給定DFDD實例可配置成在接 收的心跳計數信息的基礎上更新特定應用程式實例的狀態(例如，根據圖 24的狀態機)，而不管該信息是直接從特定的應用程式實例接收還是通過 同步協議間接地從另一 DFDD實例接收。在這樣的實施方式中，在DFDD 實例中間應用程式實例操作狀態信息的同步可包括心跳信息的同步，而沒 有直接交換應用程式實例的特定全局操作狀態(例如，OK、 INCOMMUNICADO ，等等)，這可簡化同步協議的操作。
響應於接收狀態信息的散列值和列表，對等實例以與由初始實例執行 的方式一致的方式來計算其自己的應用程式實例的識別信息的散列值(塊 2506 )，並比較最終的散列值與從初始實例接收的散列值(塊2508 )b如果 兩個值一致，則存在初始和對等實例都具有相應於相同組的應用程式實例 的項目lll的高度可能性。對等實例可接著掃描接收的狀態信息的列表並 根據接收的列表適當地更新其項目lll(塊2510)6例如，如果接收的列表 中的心跳計數或時間戳比存儲在一個對等的項目111中的更大或更新，則 對等實例可根據接收的列表中的狀態信息更新項目111。在一些實施方式 中，對等實例可與從初始實例接收列表並行地或之後將其自己的狀態信息 的列表發送回初始實例用於類似的處理。
如果散列值不一致，則有可能對等和初始實例所知的應用程式實例的組在至少一個項目111上不同。相應地，對等實例可請求初始實例所知的
項目111的完整的信息轉儲(dump )(恰好與那些項目111的狀態信息114 相反M塊2512 )b對等實例可接著添加它缺少的任何項目111 ，並同步剩 餘的項目111的狀態(塊2514 )b如上面的，在一些實施方式中，對等實 例可與從初始實例接收信息轉儲並行地或之後將其項目111的完整的信息
轉儲發送回初始實例。
可以設想，在一些實施方式中，存在於系統內的DFDD 110的每個實 例可配置成每隔一段時間重複地執行剛剛描述的同步協議，或其適當的變 形。例如，協議可大致周期性地以一秒的周期或任何其它適當的周期被 DFDD 110的實例執行。進一步可以設想，在一些實施方式中，DFDD 110 的實例可以大致相同的周期但相對於彼此不同的相移執行同步協議，以便 在任何給定的時間，只有DFDD 110的實例的一部分可開始該協議。
注意，在一些實施方式中，DFDD 110的實例可甩於為任何分布式系 統內的任何類型的應用程式實例，而不僅僅是存儲服務系統內限定的那些 應用程式實例協調和傳遞狀態信息。此外，在一些實施方式中，DFDD實 例的不同組可管理不同的應用程式實例狀態信息。在一些這樣的實施方式 中，通過給作為相同組的成員的DFDD 110的實例分配共同的標識符並要 求標識符匹配作為DFDD同步的條件可將組彼此區別開。例如，管理存儲 服務系統應用程式實例的DFDD實例可具有標識符，該標識符不同於配置 成管理與存儲服務系統無關的其它應用程式實例的狀態的DFDD實例，且 只有具有相同標識符的那些DFDD實例可根據圖25的同步協議彼此交換
i曰'息o
在一些實施方式中，DFDD組標識符可用於區別存在於相同的系統中 的應用程式實例的不同配置。例如，相應於"生產"標識符的DFDD 110的 一組實例可用來管理存儲服務系統或另一分布式系統的生產版本，並可反 映相應於生產系統的一組應用程式實例，而相應於"測試"標識符的DFDD 110的另一組實例可部屬為管理相應於不同的應用程式實例組和狀態的系 統的測試版本。注意，在一些情況下，相應於任一系統版本的應用程式實 例和/或DFDD實例可在相同的基本系統資源(例如，在相同的計算機系統)上執行，但可由於其不同的DFDD組標識符而對彼此變得透明。例如， 當執行例如圖25中所示的協議的同步協議時JDFDD實例可首先確定它們 是否是相同組的成員(例如，通過交換組標識符)並視此確定的情況而執 行隨後的同步步驟，從而便於組之間應用程式實例狀態信息的分離。
注意，前述用於同步DFDD 110的實例的基於閒聊的協議可不僅幫助 在整個存儲服務系統中分布現有的應用程式實例的操作狀態，而且也可通 過其它系統組件便於新應用程式實例的發現。例如， 一旦新應用程式實例 被初始化並與DFDD 110的實例(例如，在新應用程式實例被初始化的系 統上在本地操作的實例)接觸，就可產生相應於新實例的新項目111。由 於在其上創建新實例111的DFDD 110的實例使其狀態與DFDD 110的不 同的其它實例同步，因此新項目111可在整個系統中傳播。為了各種目的 而詢問DFDD 110以識別應用程式實例(例如，以存儲新對象30或更新鍵 映射實例140 )的DFDD客戶可接著被提供關於新應用程式實例以及任何 現有的實例的狀態信息。
還注意到，在上述實施方式中，與故障檢測和發現有關的應用程式實 例狀態信息變化可在整個系統中傳播，而不幹涉參考那些實例的應用程式 實例或DFDD客戶的部分。也就是說，給定的應用程式實例只需要知道如 何將心跳信息傳送到DFDD 110的一個實例。不需要知道系統內DFDD 110 的所有實例、其它應用程式實例或可調用給定應用程式實例的不同客戶。 類似地，DFDD客戶不需要單獨地知道其他客戶或系統內所有應用程式或 DFDD實例；客戶可依賴於DFDD 110的實例，他們與其通信以合理地獲 得關於系統內可利用的資源的狀態的當前信息。通過允許應用程式實例的 狀態改變而不需要立即通知其它應用程式實例或客戶這樣的變化，DFDD 110可有助於存儲服務系統的可縮放性。
存儲類
在一些存儲服務系統實施方式中，對象30可相對於其複製的程度、 複本在區欄位310中間的分布、複本被存儲到的存儲資源的類型和/或其它 系統特徵或策略被統一處理。例如，系統可試圖將每個對象30複製相同 數量的次數到相同數量的不同區域310。然而，不同的客戶50對不同的對象30可有不同的存儲要求。例如， 一個客戶50可能希望以比默認的存儲 策略可提供的更高的可靠度(例如，根據複本的數量和分布)存儲特定的 對象30 ,而另一客戶50可能甚至不需要默認級別的可靠性。可選地，客 戶50可希望通過限制對象複本被分布到的區域310的數量來增加對象寫 入性能，可能以可靠性為代價。
相應地，在一個實施方式中，存儲服務系統例如圖2的系統可配置成 支持對象30的存儲類。 一般而言，給定對象30的存儲類可指定相對於給 定對象30影響服務等級協議(SLA )的存儲服務系統特徵或特性的任何集 合。服務等級協議可通常反映保證或期望的集合，在這些保證或期望下服 務供應商向客戶提供服務，以換取從客戶接收的一些考慮因素(例如，費 用或任何其它適當類型的考慮因素)6例如，由存儲服務系統管理的對象 30的SLA可為服務指定對象可靠性、有效性、訪問性能(例如，等待時 間、帶寬》費用或速率的不同級別，或客戶與對象30的交互作用的任何 其它可測量的方面。在一些實施方式中，存儲類可只指定SLA特性的特定 子集合(例如，如下所述對象複本的數量和分布)，而在其它實施方式中， 存儲類可直接相應於包括關於給定對象30的SLA協議的所有定義的方面 的綜合SLA。
在一個實施方式中，存儲服務系統可定義存儲類的固定集合，每個存 儲類都具有特別定義的SLA特性，且客戶50可選擇使特定的對象30與特 定的存儲類關聯起來。例如，默認的存儲類可指定對象30複製至少三次 到至少兩個不同的區域310。高度可靠性的存儲類可指定對象30複製至少 五次到至少三個不同的區域310。預算存儲類可指定對象30的單個複本存 儲在單個區域310內。局部存儲類可指定對象30複製至少三次到單個區 域310。在其它實施方式中，存儲服務系統可定義具有其它特性的存儲類， 或可允許客戶50通過指定將應用到給定對象30的存儲策略的組魚例如， 如上關於節點揀取器130描述的)來為給定的對象30定製存儲類。
如上所述，SLA特性可擴展而超出複本的數量和區域的數量，複本應 分布到該區域。在一個實施方式中，特定存儲類的SLA特性可包括相應於 與特定存儲類關聯的對象30的預期的處理等待時間的指示。例如， 一個
98存儲類可對給定的成本規定低的預期的處理等待時間，而另一個可為較低 的成本指定較高的預期的處理等待時間。不同水平的預期的處理等待時間
可以不同方法實現。例如，從給定協調器120的觀點來看，由於這種因素， 例如節點160到給定協調器120的接近度、在節點160可得到的資源的級 別和類型、節點160的處理負載或其它相關的因素， 一些節點160可展示 比其它節點低的訪問等待時間。因此，受由給定存儲類指定的其它SLA特 性實現的限制的影響，在一些實施方式中，協調器120和/或節點揀取器 130可配置成選擇為在存儲類中的對象30展示較低的訪問等待時間的節點 160 ,該存儲類規定較低的預期處理的等待時間。在其它實施方式中，協 調器120可配置成根據與對象30關聯的存儲類的預期處理的等待時間來 為優先考慮對對象30的客戶訪問請求的處理。例如，協調器120可實現 配置成使處理偏向於有利於具有較低的預期處理等待時間的存儲類的不 同隊列或其它處理控制或數據結構，同時確保對具有較高的預期處理等待 時間的存儲類的請求最終完成。
存儲類可由客戶50在對象30最初存儲在存儲服務系統內時指定。可 選地，在一些實施方式中，客戶50可在對象30存在於存儲服務系統內的 任何時間改變與對象30關聯的存儲類。如果當對象30被最初存儲時客戶 50沒有指定存儲類，則可使用默認的存儲類例如上面描述的存儲類。如上 所述，在一些實施方式中，對象30的存儲類可存儲在與對象30的鍵關聯 的鍵映射記錄148中。在這樣的實施方式中，協調器120和/或複製器180 可配置成當存儲、複製和維持對象30的現有複本時考慮對象30的存儲類。 可以設想，客戶50可被要求為與不同存儲類關聯的對象30支付不同使用 費用。例如，高度可靠性存儲類可通常使用較多的系統資源，而預算存儲 類可使用較少的資源。相應地，對於給定大小的對象30 ,為了使用前面的 存儲類來儲存對象30 ,客戶50可被要求支付得較多，而對後者較少。
在圖26中示出了存儲類在存儲服務系統內的操作的方法的一個實施 方式。在所示實施方式中，操作在塊2600開始，其中客戶50指定將與特 定的對象30相關聯的存儲類。隨後，存儲類持久地與存儲服務系統內的 特定對象30關聯(塊2602 >例如，存儲類的指示可通過代表客戶50的協調器120存儲在與特定對象30關聯的數據結構中，例如鍵映射記錄148。 接著根據指定的存儲類的特性來配置與對象30關聯的對象數據的狀顆塊 2604 )b例如，如果存儲類指定對在區域310中間的對象複本的數量和/或 分布的某些要求，則協調器120和/或複製器180可操作來產生並分布必要 的複本，以便存儲系統相對於特定對象30的最終的狀態滿足存儲類的要 求。在一些實施方式中，複製器180可配置成確保隨著時間的過去而為對 象30維持存儲類要求。例如，如果複本失效，則複製器180可配置成檢 測故障並產生額外的複本。
可以設想，在一些實施方式中，由給定存儲類指定的存儲特性可包括 通過位存儲節點160區分不同類型的存儲資源。例如，在一些實施方式中， 一些位存儲節點160可包括比其它節點更高性能的存儲設備，或單獨的位 存儲節點160可包括較高和較低性能設備的組合。在這樣的實施方式中， 存儲類可指定一種或另一類型的設備應用於與該類相關聯的對象30。
動態複製
如上所討論的，在一些實施方式中，節點揀取器130可配置成產生識 別特定對象30的複本應寫入的特定位存儲節點160的寫入計劃。這樣的 寫入計劃可以這樣的方式產生，使得一旦寫入計劃例如通過協調器120實 現，不同的寫入策略相對於特定的對象30就被滿足。例如，由寫入計劃 規定的節點160的數量可根據特定對象30的複本的最小需要的數量、在 其上應分布複本的不同區域310的最小數量，或任何其它存儲策略考慮因 素來確定。
在一些實施方式中，節點揀取器130可配置成以靜態的方式產生寫入 計劃，其中節點160根據可預測的程序被一致地選擇，而不考慮節點160 的當前狀態。例如，節點揀取器130可一致地選擇相同組的節點160用於 存儲複本，或可通過很多節點160以循環的方式旋轉。然而，在大規模實 現中，存儲服務系統可包括可在不同的時間在相當不同的狀態中操作的節 點160。例如， 一些節點160可為無效的，另一些節點可為有效的但充滿 請求行為或具有少量的自由資源，以及還有另一些可相對空閒或具有相當 多的自由資源。此外，從給定協調器120或節點揀取器130的觀點來看，節點160可 呈現不同級別的通信費用。例如，位於相同區域310或數據中心300內作 為協調器120的節點160可通過本地低等待時間網絡連通性被訪問。相反， 位於與協調器120不同的區域310或數據中心300內的節點160可呈現比 本地節點160實質上更高的訪問等待時間。而且，在一些實施方式中，區 域310或數據中心300之間的通信可發生在具有與本地通信不同的經濟費 用模型的通信網絡上。例如，區域310內的通信可發生在具有大量帶寬的 專用區域網(LAN )上，對於該帶寬沒有用於數據傳輸的基於使用的費用。 相反，數據中心300之間的通信可發生在設備上，例如租用的電信設備、 公共網際網路、專用廣域網(WAN)設備或其它遠程電信網絡。這些設備可 一般比LAN設備更具有帶寬限制，且在一些實例中可呈現由第三方要求 支付的利用費用(例如，基於峰值或合計的帶寬利用)，該費用可能不適 用於LAN通信。
不同節點160的操作狀態以及對那些節點的通信的費用都可隨著時間 的過去而變化。例如，曾經有效或空閒的節點160可能在稍後的時間變得 無效或繁忙，反之亦然。類似地，通信費用例如等待時間和/或經濟費用可 能在一些時期期間較高而在另一些時期期間較低(例如，在峰值對非峰值 利用的時期期間 > 由於這個變化性，曾經有效和費用低的寫入計劃可能 相當不有效、費用較高、或甚至在另一時間不可行(例如，如果在寫入計 劃中指定的節點160變得繁忙、通信起來緩慢或無效)b
因此，在一些實施方式中，節點揀取器130可配置成根據與節點160 關聯的當前狀態信息來動態地確定給定的寫入計劃，用於寫入給定對象30 的複本。 一般而言，動態確定的寫入計劃可考慮關於節點160的可觀察的 動態狀態信息。也就是說，動態確定的寫入計劃可作為可隨著時間的過去 而變化的節點狀態信息的函數而產生。因此，對給定對象30的動態確定 的寫入計劃本身可根據節點160的基本狀態信息隨著時間的過去而變化， 與可獨立於節點160的狀態而確定的靜態產生的寫入計劃相反。
如上所述，在寫入計劃的動態產生中可考慮很多不同類型的狀態信 息。 一般來說，節點160的狀態信息可包括關於給定節點160的狀態信息以及關於通信資源(例如，網絡資源)的狀態信息，通過該資源可訪問給
定的節點160。在不同實施方式中，關於給定節點160的狀態信息可包括 給定節點160的操作狀態，例如給定節點160 (或與該節點關聯的應用程 序實例)是否處於由DFDD 110指示的0K、 INCOMMUNICADO或其它 操作狀態中，如上所述。關於給定節點160的狀態信息還可包括負載狀態 信息，其可比操作狀態信息更詳細地指示給定節點160的行為。例如，在 不同實施方式中，負載狀態信息可指示處理器利用、存儲器利用、存儲設 備容量利用、存儲設備輸入/輸出帶寬利用或相應於給定節點160的網絡接 口帶寬利用的級別，或節點行為的任何其它可測量的方面。如上所述，在 一些實施方式中，除了操作狀態信息以外，負載狀態信息也可通過DFDD 110得到。
可稱為網絡費用信息的通信資源狀態信息可包括與到給定節點160的 一個或更短通信路徑的狀態有關的任何適當的信息。在不同實施方式中， 網絡費用信息可指示與將消息傳送到給定節點160和/或從給定節點160傳 送出來相關的網絡通信等待時間，這可根據時間(例如，秒、毫秒等、 網絡跳數(例如，傳送消息的路由步驟的數量)或另一適當的度量來表達。 在一個實施方式中，網絡費用信息可包括可用於與給定節點160通信的有 效帶寬的指示(例如，數據傳輸的速率)o在另一實施方式中，網絡費用 信息可包括與和給定節點160的網絡通信相關的經濟費用。例如，這樣的 費用可表達為用於傳輸或接收一定數量的數據的付費率或網絡通信的任 何其它適當的費用或費率模型。
節點揀取器130在動態地確定對象30的寫入計劃中可通常使用節點 160的狀態信息的任何適當的函數。在一些實施方式中，由節點揀取器130 實現的存儲策略(其可以是除了或代替前面所述的那些存儲策略)可為狀 態信息指定準則或要求，該狀態信息限制可能有資格包括在特定對象30 的寫入計劃中的節點160。在不同的實施方式中，這些策略可全局地(例如， 對於所有的對象30 )應用於對象30的特定組(例如，包括在特定存儲類 或存儲桶中的、具有共同的鍵前綴，或另外地表示為組的成員的對象、 或應用於各個對象30 (例如，相應於規定將與對象30關聯的特定策略的客戶X或這些的任何適當組合。作為例子，特定的存儲類可規定存儲策 略，該存儲策略要求某個最小數量的複本展示不多於某個最大的通信等待
時間。相應地，在為該存儲類中的對象30開發寫入計劃中，節點揀取器 130可配置成根據節點160是否滿足指定的最大通信等待時間來選擇至少 一些節點160。
在一些實施方式種，節點揀取器130還可配置成根據對節點狀態信息 的最佳化的不同類型來產生寫入計劃。例如，作為指定與寫入計劃相關的 特定的最大網絡費用或其它費用的可選方案，存儲策略可指定費用應在可 在特定的時間得到的資源中間被最小化。相應地，節點揀取器130可配置 成例如通過選擇具有較低的網絡通信或其它相關費用的節點160來最小化 與寫入計劃相關的一個或更多費用。在一些實施方式中，這樣的最小化可 出現在存在其它限制時，例如指定其它節點狀態信息要求的其它存儲策 略。
此外，注意，在一些實施方式中， 一些節點狀態信息可以可預測的方 式隨著時間的過去而變化。例如，與數據中心300之間的網絡通信相關的 帶寬費用可根據定義明確的費率計劃來變化。在一些這樣的實施方式中， 最小化與寫入計劃相關的費用可包括識別一段時間，在該段時間期間應執 行寫入計劃的全部或一些，取決於與特定的時間段相關的費用。例如，節 點揀取器130可確定用於與遠程數據中心300通信的帶寬在某個未來的時 間比在當前的時間更廉價，且可進一步確定，包括在遠程數據中心300的 節點160的寫入計劃的費用可通過在被確定的未來時間至少執行指向遠程 數據中心的那些存儲操作來被最小化。該過程的一個可能的結果是，由節 點揀取器130產生的寫入計劃可指示應延遲給定對象30的一些(或可能 全部)複本的產生直到被確定的未來時間。
很多不同的存儲策略可應用於特定的對象30是可能的。進一步地， 在一些實例中，產生滿足與特定對象30關聯的每個存儲策略的單個寫入 計劃可能是不可能的。例如，與特定對象30關聯的存儲策略可指定，最 小數量的複本應存儲和分布在最小數量的不同區域310內。然而，在寫入 計劃為特定的對象30產生時，節點揀取器130正在其中執行的區域310
103可由於瞬時通信故障而與其它區域310暫時隔離。結果，將複本成功地分 布到其它區域310以滿足相應的存儲策略可能是至少暫時不可能的。
在一個實施方式中，節點揀取器130可配置成在最小化可由寫入計劃 滿足的存儲策略的數量的基礎上動態地確定對象30的寫入計劃。在存在 不是最佳的條件時，這可能導致表示滿足存儲策略的"盡力服務"的寫入計 劃。例如，在剛剛描述的特定情況中，區域多樣性策略可能由於通信故障 不是可以滿足的，但最少複製策略可通過將特定對象310的所要求的最小 數量的複本存儲在本地區域310內是可以滿足的。在一些實施方式中，存 儲策略的最大化可發生在各種限制下。例如， 一些存儲策略可被識別為強 制性的，以便如果它們不是可以滿足的，則寫入計劃不能被確定，且存儲 對象的相應客戶請求可能失敗。其它存儲策略可具有優先等級或權重，以 便較高優先級的存儲策略可優先於較低優先級的策略在最大化過程期間 被選擇。在另一實施方式中，通過最大化最終的存儲計劃的總的權重(在 所滿足的存儲策略的重要性的基礎上確定)，而不是或除了被最終的存儲 計劃滿足的存儲策略的數量，可執行存儲策略的選擇。
注意，用於動態地確定對象30的寫入計劃的各種技術不需要只出現 在對象30被最初存儲時。如上所述，在一些實施方式中，複製器180可 配置成檢查相應於對象30的鍵映射項目144以確定對象30的複本是否是 可訪問的。如果特定對象30的任何複本是不可訪問的，則複製器180可 配置成從節點揀取器130請求可用於產生額外的複本的新的寫入計劃。新 的寫入計劃可由節點揀取器130使用上述技術的任何適當的組合動態地確 定。此外，在一些實施方式中，複製器180可配置成相對於各種存儲策略 更一般地監控對象30的適應性。例如，複製器180可配置成確定除了最 少複製策略或策略的任何其它適當集合以外，對象30的現有的複本組是 否還滿足區域多樣性策略。在一個這樣的實施方式中，如果複製器180確 定被特定對象30的現有的複本滿足的策略的數量小於某個閾值，則複製 器180可從節點揀取器130請求可被動態地確定以最大化如上所述的被滿 足的存儲策略的數量的新存儲計劃。在可選的實施方式中，複製器180在 確定特定的強制性存儲策略不再被滿足時或當確定被滿足的存儲策略的
1總權重落到閾值權重之下時可請求新的存儲方案。
圖27示出根據位存儲節點160的當前狀態信息動態地確定用於存儲 數據對象的一個或更多複本的寫入計劃的方法的一個實施方式。在所示實 施方式中，操作在塊2700中開始，其中存儲給定對象30的客戶請求被接 收。在一個實施方式中，根據網絡服務協議通過網絡服務接口 100可接收 這樣的請求，如上詳細描述的。
隨後，根據位存儲節點160的當前狀態信息來動態地確定用於存儲給 定對象30的複本的寫入計劃(塊2702 )b例如，節點揀取器130可配置成 根據可應用於給定對象30的各種存儲策略來確定寫入計劃，其中這些策 略考慮任何適當的當前狀態信息，例如節點操作狀態、節點負載狀態信息、 網絡通信費用或如上面詳細描述的任何其它適當的狀態信息。此外，如上 所述，在一些實施方式中，動態地確定寫入計劃可包括對於狀態信息或存 儲策略的最佳化，例如通過最小化與寫入計劃相關的費用或最大化被寫入 計劃滿足的存儲策略的數量或權重。
給定對象30的複本可接著根據動態確定的寫入計劃存儲到一個或更 多位存儲節點160 (塊2704 )b例如，協調器120可配置成產生指向在寫 入計劃中指定的各個位存儲節點160的位存儲對象放置操作，如上所述。 在一些實施方式中，寫入計劃的一些存儲操作可在與其它操作不同的時間 執行，如上所述。
如前面提到的，在一些實施方式中，寫入計劃可相對於對象30被動 態地確定，該對象30的一個或更多複本已經被存儲在位節點160中間。 圖28示出這樣的方法的一個實施方式。在所示實施方式中，操作在塊2800 中開始，其中給定對象30的一個或更多現有複本被檢查。例如，如上所 述，複製器180的一個實施方式可配置成確定給定對象30的現有複本是 否是可訪問的，和/或給定對象30的現有複本滿足與該對象關聯的存儲策 略的程度。
響應於檢査給定對象30的複本，可確定需要產生一個或更多額外的 複本(塊2802 )b例如，現有的複本可能失效或另外地變得不可訪問，導 致少於最小數量的複本。可選地，現有複本的狀態可能相對於一個或更多存儲策略是不足的。隨後，根據位存儲節點160的當前狀態信息來動態地 確定用於存儲給定對象30的額外複本的寫入計劃(塊2804 )b以類似於前 面描述的方式或根據其任何適當變形可確定這樣的寫入計劃。注意，在一 些實施方式中，如果確定對給定的對象30不需要產生額外的複本，則可 不確定寫入計劃。
給定對象30的複本接著根據動態確定的寫入計劃被存儲到一個或更 多位存儲節點160 (塊2806 )b例如，複製器180可配置成產生指向在寫 入計劃中指定的各個位存儲節點160的位存儲對象放置操作，如上所述， 或可簡單地指引存儲給定對象30的現有複本的一個或更多節點160來將 其複本拷貝到在寫入計劃中指定的一個或更多節點160。
示例性計算機系統實施方式
可以設想，在一些實施方式中，上述任何方法或技術可實現為能夠通 過計算機可訪問的介質存儲或傳送的程序指令和數據。這樣的方法或技術 可包括例如且沒有限制地存儲客戶50、網絡服務平臺100、 DFDD 110、協 調器120、節點揀取器130、鍵映射實例140、位存儲節點160、複製器180 和/或複製符鍵映射190的功能。這樣的方法或技術可進一步包括在圖6-9、 13-15、 20-22和25-8中示出來的任何方法及其任何適當的變形。可執行這 樣的程序指令以履行特定的計算功能，例如特定的方法或上述方法的部
分，以及提供更一般的作業系統功能、應用程式功能和/或任何其它適當的 功能。注意，在一些實施方式中，在上面被描述為獨立的組件或方法在其 它實施方式中可合併到比所示的那些更少的實體中，或功能可與從上述的 劃分不同地在組件和方法中劃分。
圖29中示出了包括計算機可訪問的介質的計算機系統的一個示例性 實施方式。這樣的系統也可稱為節點。如前面所討論的，在一個實施方式 中，上述各種存儲系統組件的任何一個的功能可分布在很多節點中，以便 給定組件可由一個或更多節點實現或在一些節點中劃分。雖然在一些實施 方式中，節點可專門實現單個存儲服務系統組件的功能，但是在其它實施 方式中，節點可實現一些不同的系統組件的所有或部分的功能。在所示實 施方式中，計算機系統2900包括通過輸入/輸出(I/O )接口 2903耦合到系統存儲器2920的一個或更多處理器2910。計算機系統2900迸一步包括 耦合到1/0接口 2930的網絡接口 2940。
在不同實施方式中，計算機系統2900可為包括一個處理器2910的單 一處理器系統，或包括一些處理器2910(例如，兩個、四個、八個或其它 適當的數量)的多處理器系統。處理器2910可為能夠執行指令的任何適 當的處理器。例如，在不同實施方式中，處理器2910可為實現各種指令 集結構(ISA )中的任一種，例如x86、 PowerPC、 SPARC或MIPS ISA或 任何其它適當的ISA的通用或嵌入式處理器。在多處理器系統中，每個處 理器2910可通常但不是必要地實現相同的ISA。
系統存儲器2920可配置成存儲處理器2910可訪問的指令和數據。在 不同實施方式中，系統存儲器2920可使用任何適當的存儲器技術來實現， 例如靜態隨機存取存儲器(SRAM 、同步動態RAM ( SDRAM X非易失 性/閃型存儲器或任何其它類型的存儲器。在所示實施方式中，實現期望功 能的程序指令和數據，例如上面詳細描述的那些存儲服務系統部件中的任 何一個和其它功能顯示為存儲在系統存儲器2920內作為代碼2925。
在一個實施方式中，I/O接口 2930可配置成協調處理器2910、系統存 儲器2920和設備中任何外圍設備之間的I/O業務，其中的外圍設備包括網 絡接口 2940或其它外圍接口。在一些實施方式中，I/O接口 2930可執行 任何必要的協議、計時或其它數據轉換，以將數據信號從一個組件(例如， 系統存儲器2920 )轉換成適合於由另一組件(例如，處理器2910 )使用 的格式。在一些實施方式中，I/O接口 2930可包括對通過不同類型的外圍 總線連接的設備的支持，例如外圍部件互聯(PCI )總線標準或通用串行 總線(USB )標準的變型。在一些實施方式中，I/O接口 2930的功能可分 成兩個或更多分離的組件，例如北橋和南橋。此外，在一些實施方式中， 1/0接口 2930 ,例如系統存儲器2920的接口的一些或所有功能可直接合併 到處理器2910中。
網絡接口 2940可配置成允許數據在計算機系統2900和連接到網絡的 其它設備例如其它計算機系統之間交換。在不同實施方式中，網絡接口 2940可通過有線或無線一般數據網絡例如任何適當類型的乙太網絡、通過電信/電話網絡例如模擬語音網絡或數字光纖通信網絡、通過存儲區域網例
如光纖通道SAN或通過任何其它適當類型的網絡和/或協議來支持通信。
在一些實施方式中，系統存儲器2920可為配置成存儲如上所述的程 序指令和數據的計算機可訪問的介質的一個實施方式。然而，在其它實施 方式中，對不同類型的計算機可訪問的介質可接收、發送或存儲程序指令 和/或數據。一般而言，計算機可訪問的介質可包括存儲介質或存儲器介質， 例如磁或光介質，例如通過I/O接口 2930耦合到計算機系統2900的磁碟 或CD/DVD-ROM。計算機可訪問的介質還可包括任何易失性或非易失性 介質例如RAM (例如，SDRAM、 DDRSDRAM、 RDRAM、 SRAM等、 ROM等，其可包括在計算機系統2900的一些實施方式中作為系統存儲器 2920或另一類型的存儲器。通過計算機可訪問的介質存儲的程序指令和數 據可通過傳輸介質或信號例如電、電磁或數位訊號來傳輸，這些信號可通 過通信介質例如可通過網絡接口 2940來實現的網絡和/或無線連結來傳 送。
雖然以相當多的細節描述了上面的實施方式，當上面的公開被充分認 識到時很多變形和更改對本領域的技術人員將變得明顯。意圖是下列的權 利要求被解釋為包括所有這樣的變形和更改。
權利要求
1.一種系統，包括多個計算節點，所述計算節點被配置成實現網絡服務接口，其配置成根據網絡服務協議來接收對訪問數據對象的客戶請求，其中對訪問所述數據對象中給定的一個數據對象的所述客戶請求中給定的一個客戶請求包括相應於所述給定的數據對象的鍵值；多個存儲節點，其配置成存儲所述數據對象的複本，其中所述複本中的每一個都是通過各自的定位器值可訪問的，且其中所述定位器值中的每一個在所述系統內都是唯一的；鍵映射實例，其配置成為所述數據對象中的每一個存儲各自的鍵映射項目，其中對於所述給定的數據對象，所述各自的鍵映射項目包括所述鍵值和相應於所述給定數據對象的每個存儲的複本的每個定位器值；以及協調器，其配置成從所述網絡服務接口接收對訪問所述數據對象的所述客戶請求，其中響應於所述給定的客戶請求，所述協調器配置成訪問所述鍵映射實例以識別相應於所述鍵值的一個或更多定位器值，並且對於所述一個或更多定位器值中特定的一個定位器值，訪問相應的存儲節點以取回相應的複本。
2 .如權利要求1所述的系統，其中在取回所述相應的複本之後，所 述協調器進一步配置成根據所述給定的客戶請求通過所述網絡服務接口 來將所述相應的複本傳送到客戶。
3 .如權利要求1所述的系統，其中所述網絡服務接口進一步配置成 在取回所述相應的複本之前，確定所述給定的客戶請求是否被充分地給予 特權來訪問所述給定的數據對象，且如果所述給定的客戶請求沒有被充分 地給予特權，則拒絕所述給定的客戶請求。
4 .如權利要求1所述的系統，其中所述網絡服務接口進一步配置成根據所述網絡服務協議來接收存儲數據對象的客戶請求，其中存儲所述數 據對象中特定的一個數據對象的所述客戶請求中特定的一個客戶請求包 括相應於所述特定的數據對象的鍵值。
5 .如權利要求4所述的系統，其中所述網絡服務接口進一步配置成 確定用於存儲所述特定的數據對象的費用。
6 .如權利要求4所述的系統，其中所述協調器進一步配置成從所述 網絡服務接口接收存儲數據對象的所述客戶請求，其中響應於所述特定的 客戶請求，所述協調器配置成將所述特定的數據對象的一個或更多複本存 儲到一個或更多相應的存儲節點，其中響應於存儲所述特定的數據對象的 給定複本，所述存儲節點中給定的一個存儲節點配置成將相應於所述給定 複本的定位器值返回到所述協調器。
7 .如權利要求5所述的系統，其中所述協調器進一步配置成指導所 述鍵映射實例更新相應於所述特定的數據對象的所述各自的鍵映射項目， 以包括相應於所述給定的複本的所述定位器值。
8 .如權利要求5所述的系統，其中根據存儲策略來選擇所述特定的 數據對象中的所述一個或更多複本被存儲到的所述一個或更多相應的存儲節點o
9 .如權利要求8所述的系統，其中所述存儲策略指定在所述協調器 指示存儲所述特定的數據對象的所述特定的客戶請求被完成之前，需要被 指示為持久地存儲到相應的存儲節點的複本的數量。
10 .如權利要求9所述的系統，其中所述存儲策略額外地指定將產生 的所述特定的數據對象的複本的期望的數量。
11 .如權利要求IO所述的系統，其中所述複本的期望的數量超過所述 複本的數量。
12 .如權利要求10所述的系統，其中所述多個計算節點進一步配置 成實現複製器，所述複製器配置成檢查所述鍵映射實例的所述各自的鍵映 射項目，以確定對於所述鍵映射項目的給定的一個鍵映射項目，相應於所 述給定鍵映射項目中的各自的定位器值的每個複本是否是可訪問的。
13 .如權利要求12所述的系統，其中對於所述給定的鍵映射項目， 如果相應於所述給定鍵映射項目中的各自定位器值的可訪問的複本的數 量小於所述複本的期望的數量，則所述複製器進一步配置成產生足以滿足 新述複本的期望的數量的額外的複本。
14 .如權利要求8所述的系統，其中所述多個存儲節點分布在多個區 域中間，且其中所述存儲策略指定在所述協調器指示存儲所述特定的數據 對象的所述特定的客戶請求被完成之前，所述一個或更多複本需要被指示 為持久地存儲到的區域的最小數量。
15 .如權利要求14所述的系統，其中存儲節點故障的可能性在所述 多個區域的中任何兩個區域之間的相關性小於閾值數量。
16 .如權利要求14所述的系統，其中如果可能，則所述存儲策略額 外地指定所述一個或更多複本中的至少一個將被寫到位於所述區域中的 給定的一個區域中的存儲節點，其中所述協調器也位於所述給定的區域 內。
17 .如權利要求8所述的系統，其中所述多個存儲節點分布在多個區 域中間，且其中如果可能，則所述存儲策略指定所述一個或更多複本中的 至少一個將被寫到位於所述區域中的給定的一個區域中的存儲節點。
18 .如權利要求17所述的系統，其中所述給定的區域是根據所述存 儲策略來選擇的，以最小化所述給定的區域和與所述特定的客戶請求相關 聯的客戶之間的通信等待時間。
19 .如權利要求1所述的系統，其中相應於所述給定的數據對象的所 述鍵值是由客戶通過所述網絡服務接口指定的。
20 .如權利要求1所述的系統，其中通過所述網絡服務接口接收的對 訪問所述給定的數據對象的所述客戶請求中的特定的一個客戶請求包括 相應於所述給定的數據對象的特定複本的特定的定位器值。
21 .如權利要求20所述的系統，其中響應於從所述網絡服務接口接 收對訪問的所述特定的客戶請求，所述協調器進一步配置成藉助於所述特 定的定位器值從相應的存儲節點取回所述特定的複本，而不訪問所述鍵映射實例。
22 .如權利要求1所述的系統，其中所述網絡服務協議實現具象狀態 傳輸(REST)網絡服務模型。
23 .如權利要求22所述的系統，其中為了根據所述網絡服務協議接 收所述給定的客戶請求，所述網絡服務接口進一步配置成接收根據超文本 傳輸協議(HTTP )的版本格式化的請求。
24 .如權利要求23所述的系統，其中所述給定的客戶請求的內容作 為根據可擴展標記語言(XML )的版本格式化的參數而被包括在所述請求 中。
25 .如權利要求1所述的系統，其中所述網絡服務協議實現基於文檔 的網絡服務模型。
26 .如權利要求25所述的系統，其中為了根據所述網絡服務協議接 收所述給定的客戶請求，所述網絡服務接口進一步配置成接收根據簡單對 象訪問協議(SOAP )的版本封裝的文檔，其中所述給定的客戶請求的內 容被包括在所述文檔內並根據XML的版本被格式化。
27 .如權利要求1所述的系統，其中所述鍵映射實例進一步配置成在 索引數據結構內索引所述鍵映射實例存儲的鍵映射項目，所述索引數據結 構包括分等級布置的多個索引節點且每個索引節點都具有相關聯的標記 值，其中每個所述存儲的鍵映射項目相應於所述索引節點中的各自的一個 索引節點，且其中對於具有給定的相應索引節點的所述給定的鍵映射項 目，與所述給定的相應索引節點的每個先輩關聯的每個標記值是所述給定 的鍵值的前綴。
28 . —種方法，包括以下步驟根據網絡服務協議通過網絡服務接口接收對訪問數據對象的客戶請 求，其中對訪問所述數據對象中的給定的一個數據對象的所述客戶請求中 的給定的一個客戶請求包括相應於所述給定的數據對象的鍵值；將所述數據對象的複本存儲在多個存儲節點上，其中所述複本中的每 —個都是通過各自的定位器值可訪問的，且其中所述定位器值中的每一個在所述系統內都是唯一的；為所述數據對象中的每一個數據對象存儲各自的鍵映射項目，其中對 於所述給定的數據對象，所述各自的鍵映射項目包括所述客戶指定的鍵值 和相應於所述給定的數據對象的每個存儲的複本的每個定位器值；以及響應於所述給定的客戶請求，訪問所述各自的鍵映射項目以識別相應 於所述鍵值的一個或更多定位器值，並且對於所述一個或更多定位器值中 特定的一個定位器值，訪問相應的存儲節點並取回相應的複本。
29 .如權利要求28所述的方法，進一步包括根據所述給定的客戶請 求通過所述網絡服務接口來將所述取回的相應複本傳送到客戶。
30 .如權利要求28所述的方法，進一步包括在取回所述相應的複本 之前，確定所述給定的客戶請求是否被充分地給予特權來訪問所述給定的 數據對象，且如果所述給定的客戶請求沒有被充分地給予特權，則拒絕所 述給定的客戶請求。
31 .如權利要求28所述的方法，進一步包括根據所述網絡服務協議通過所述網絡服務接口接收存儲數據對象的 客戶請求，其中存儲所述數據對象中所述特定的一個數據對象的所述客戶 請求中的特定的一個客戶請求包括相應於所述特定的數據對象的鍵值。
32 .如權利要求31所述的方法，進一步包括確定用於存儲所述特定 的數據對象的費用。
33 .如權利要求31所述的方法，進一步包括響應於所述特定的客戶請求，將所述特定的數據對象的一個或更多復 本存儲到一個或更多相應的存儲節點；以及響應於將所述特定的數據對象的給定的複本存儲到所述存儲節點中 給定的一個存儲節點，來接收相應於所述給定複本的定位器值。
34 .如權利要求33所述的方法，進一步包括更新相應於所述特定的 數據對象的所述各自的鍵映射項目，以包括相應於所述給定的複本的所述 定位器值。
35 .如權利要求33所述的方法，進一步包括根據存儲策略來選擇所 述特定的數據對象的所述一個或更多複本被存儲到的所述一個或更多相 應的存儲節點。
36 .如權利要求35所述的方法，其中所述存儲策略指定在所述協調 器指示存儲所述特定的數據對象的所述特定的客戶請求完成之前，需要被 指示為持久地存儲到相應的存儲節點的複本的數量。
37 .如權利要求36所述的方法，其中所述存儲策略額外地指定待被 產生的所述特定的數據對象的複本的期望的數量。
38 .如權利要求37所述的方法，其中所述複本的期望的數量超過所 述複本的數量。
39 .如權利要求37所述的方法，進一步包括檢查所述各自的鍵映射 項目，以確定對於所述鍵映射項目的給定的一個鍵映射項目，相應於所述 給定的鍵映射項目中的各自的定位器值的每個複本是否是可訪問的。
40 .如權利要求39所述的方法，進一步包括對於所述給定的鍵映射項目，如果相應於所述給定鍵映射項目中的各 自的定位器值的可訪問的複本的數量小於所述複本的期望的數量，則產生 足以滿足所述複本的期望的數量的額外的複本。
41 .如權利要求35所述的方法，其中所述多個存儲節點被分布在多 個區域中間，且其中所述存儲策略指定在所述協調器指示存儲所述特定的 數據對象的所述特定的客戶請求完成之前，所述一個或更多複本需要被指 示為持久地存儲到的區域的最小數量。
42 .如權利要求41所述的方法，其中存儲節點故障的可能性在所述 多個區域的任何兩個區域之間的相關性小於閾值數量。
43 .如權利要求41所述的方法，其中如果可能，則所述存儲策略額 外地指定所述一個或更多複本中的至少一個複本將被寫到位於所述區域 中的給定的一個區域中的存儲節點，其中所述協調器也位於所述給定的區 域內。
44 .如權利要求35所述的方法，其中所述多個存儲節點分布在多個 區域中間，且其中如果可能，則所述存儲策略指定所述一個或更多複本中 的至少一個複本將被寫到位於所述區域中的給定的一個區域中的存儲節
45 .如權利要求44所述的方法，其中所述給定的區域是根據所述存 儲策略來選擇的，以最小化所述給定的區域和與所述特定的客戶請求相關 聯的客戶之間的通信等待時間。
46 .如權利要求28所述的方法，其中相應於所述給定的數據對象的 所述鍵值是由客戶通過所述網絡服務接口指定的。
47 .如權利要求28所述的方法，其中對由所述網絡服務接口接收的 訪問所述給定數據對象的所述客戶請求中特定的一個客戶請求包括相應 於所述給定的數據對象的特定複本的特定的定位器值。
48 .如權利要求47所述的方法，進一步包括響應於從所述網絡服務接口接收對訪問的所述特定的客戶請求，藉助 於所述特定的定位器值從相應的存儲節點取回所述特定的複本，而不訪問 所述各自的鍵映射項目中的任何一個。
49 .如權利要求28所述的方法，其中所述網絡服務協議實現具象狀 態傳輸(REST )網絡服務模型。
50 .如權利要求49所述的方法，其中根據所述網絡服務協議接收所 述給定的客戶請求的所述步驟包括接收根據超文本傳輸協議(HTTP )的 版本格式化的請求。
51 .如權利要求49所述的方法，其中所述給定客戶請求的內容作為 根據可擴展標記語言(XML )的版本格式化的參數被包括在所述請求中。
52 .如權利要求28所述的方法，其中所述網絡服務協議實現基於文 檔的網絡服務模型。
53 .如權利要求52所述的方法，其中根據所述網絡服務協議接收所 述給定的客戶請求的所述步驟包括接收根據簡單對象訪問協議(SOAP )的版本封裝的文檔，其中所述給定的客戶請求的內容被包括在所述文檔內並根據XML的版本被格式化。
54 .如權利要求28所述的方法，其中為所述數據對象中的每一個存 儲所述各自的鍵映射項目的所述步驟包括在索引數據結構內索引所述鍵 映射項目，所述索引數據結構包括分等級布置的多個索引節點且每個索引 節點都具有相關聯的標記值，其中每個所述鍵映射項目相應於所述索引節 點中各自的一個，且其中對於具有給定的相應索引節點的所述鍵映射項目 中的給定的一個鍵映射項目，與所述給定的相應索引節點的每個先輩關聯 的每個標記值是所述給定的鍵值的前綴。
55 . —種包括指令的計算機可訪問的介質，其中所述指令可執行來處理對訪問數據對象的客戶請求，其中對訪問所述數據對象的所述客 戶請求是根據網絡服務協議通過網絡服務接口而被接收的，且其中對訪問 所述數據對象中的給定的一個數據對象的所述客戶請求中給定的一個客 戶請求包括相應於所述給定數據對象的鍵值；指導所述數據對象的複本被存儲在多個存儲節點上，其中所述複本中 的每一個都是通過各自的定位器值可訪問的，且其中所述定位器值中的每 一個在所述系統內都是唯一的；以及指導為所述數據對象中的每一個存儲各自的鍵映射項目，其中對於所 述給定的數據對象，所述各自的鍵映射項目包括所述客戶指定的鍵值和相 應於所述給定數據對象的每個存儲的複本的每個定位器值；其中處理所述給定的客戶請求的所述步驟包括，訪問所述各自的鍵映 射項目以識別相應於所述鍵值的一個或更多定位器值，並且對於所述一個 或更多定位器值中特定的一個，訪問相應的存儲節點並取回相應的複本。
56 .如權利要求55所述的計算機可訪問的介質，其中所述指令進一 步可執行來處理存儲數據對象的客戶請求，其中存儲數據對象的所述客戶請求是 根據所述網絡服務協議通過所述網絡服務接口而被接收的，且其中存儲所 述數據對象中所述特定的一個數據對象的所述客戶請求中特定的一個客戶請求包括相應於所述特定的數據對象的鍵值。
57 .如權利要求56所述的計算機可訪問的介質，其中所述指令進一 步可執行來確定用於存儲所述特定的數據對象的費用。
58 .如權利要求56所述的計算機可訪問的介質，其中所述指令進一 步可執行來響應於所述特定的客戶請求，將所述特定的數據對象的一個或更多復 本存儲到一個或更多相應的存儲節點；以及響應於將所述特定的數據對象的給定複本存儲到所述存儲節點中給 定的一個存儲節點，接收相應於所述給定的複本的定位器值。
59 .如權利要求57所述的計算機可訪問的介質，其中所述指令進一 步可執行來指導相應於所述特定的數據對象的所述各自的鍵映射項目被 更新，以包括相應於所述給定複本的所述定位器值。
60 .如權利要求58所述的計算機可訪問的介質，其中所述指令進一 步可執行來指導根據存儲策略來選擇所述特定的數據對象的所述一個或 更多複本被存儲到的所述一個或更多相應的存儲節點。
61 .如權利要求60所述的計算機可訪問的介質，其中所述存儲策略 指定在所述協調器指示存儲所述特定的數據對象的所述特定的客戶請求 完成之前，需要被指示為持久地存儲到相應的存儲節點的複本的數量。
62 .如權利要求61所述的計算機可訪問的介質，其中所述存儲策略 額外地指定待被產生的所述特定的數據對象的複本的期望的數量。
63 .如權利要求62所述的計算機可訪問的介質，其中所述複本的期 望的數量超過所述複本的數量。
64 .如權利要求60所述的計算機可訪問的介質，其中所述多個存儲 節點分布在多個區域中間，且其中所述存儲策略指定在所述協調器指示存 儲所述特定的數據對象的所述特定的客戶請求完成之前，所述一個或更多 複本需要被指示為持久地存儲到的區域的最小數量。
65 .如權利要求64所述的計算機可訪問的介質，其中存儲節點故障的可能性在所述多個區域的任何兩個之間的相關性小於閾值數量。
66 .如權利要求64所述的計算機可訪問的介質，其中如果可能，則 所述存儲策略額外地指定所述一個或更多複本中的至少一個複本將被寫 到位於所述區域的給定的一個區域中的存儲節點，其中所述協調器也位於 所述給定區域內。
67 .如權利要求60所述的計算機可訪問的介質，其中所述多個存儲 節點分布在多個區域中間，且其中如果可能，則所述存儲策略指定所述一 個或更多複本中的至少一個複本將被寫到位於所述區域的給定的一個區 域中的存儲節點。
68 .如權利要求67所述的計算機可訪問的介質，其中所述給定的區 域是根據所述存儲策略來選擇的，以最小化所述給定區域和與所述特定的 客戶請求相關聯的客戶之間的通信等待時間。
69 .如權利要求55所述的計算機可訪問的介質，其中對訪問所述給 定數據對象的所述客戶請求中特定的一個客戶請求包括相應於所述給定 數據對象的特定複本的特定的定位器值。
70 .如權利要求69所述的計算機可訪問的介質，其中所述指令進一 步可執行來響應於對訪問的所述特定的客戶請求，通過所述特定的定位器值從相 應的存儲節點取回所述特定的複本，而不訪問所述各自的鍵映射項目中的 任何一個。
71 .如權利要求55所述的計算機可訪問的介質，其中所述網絡服務 協議實現具象狀態傳輸(REST )網絡服務模型。
72 .如權利要求71所述的計算機可訪問的介質，其中根據所述網絡 服務協議接收所述給定的客戶請求的所述步驟包括接收根據超文本傳輸 協議(HTTP )的版本格式化的請求。
73 .如權利要求72所述的計算機可訪問的介質，其中所述給定客戶 請求的內容作為根據可擴展標記語言(XML )的版本格式化的參數被包括 在所述請求中。
74 .如權利要求55所述的計算機可訪問的介質，其中所述網絡服務 協議實現基於文檔的網絡服務模型。
75 .如權利要求74所述的計算機可訪問的介質，其中根據所述網絡 服務協議接收所述給定的客戶請求的所述步驟包括接收根據簡單對象訪 問協議(SOAP )的版本封裝的文檔，其中所述給定的客戶請求的內容被 包括在所述文檔內並根據XML的版本被格式化。
全文摘要
一種分布式的基於網絡服務的存儲系統。系統可包括配置成根據網絡服務協議接收對給定的數據對象的訪問的給定客戶請求的網絡服務接口，該請求包括相應於對象的鍵值。系統還可包括配置成存儲對象的複本的存儲節點，和配置成為每個對象存儲相應的鍵映射項目的鍵映射實例，其中通過相應的唯一定位器值可訪問每個複本。對於給定的對象，相應的鍵映射項目包括鍵值和相應於對象的複本的每個定位器值。協調器可從網絡服務接口接收給定的客戶請求，響應性地訪問鍵映射實例以識別相應於鍵值的定位器值，且對於特定的定位器值，從相應的存儲節點取回相應的複本。
文檔編號G06F17/30GK101496005SQ200680053577
公開日2009年7月29日 申請日期2006年11月30日 優先權日2005年12月29日
發明者A·B·阿特拉斯, A·H·弗穆倫, A·K·弗西曼, D·M·巴斯, E·M·華格納, J·C·索倫森三世, J·D·科米 申請人:亞馬遜科技公司