分布式存儲系統中基於定額的事務一致成員管理的製作方法

2023-05-09 02:11:06

專利名稱：分布式存儲系統中基於定額的事務一致成員管理的製作方法
分布式存儲系統中基於定額的事務一致成員管理背景計算機技術(例如，微處理器速度、存儲器容量、數據傳輸帶寬、軟體功能等等)的進步已經廣泛地有助於各種產業中增加的計算機應用程式。通常提供常常被配置成伺服器陣列的日益強大的伺服器系統來為起源於例如諸如全球資訊網等的外部源的請求提供服務。隨著可用的電子數據的量的增長，以促進用戶友好的和快速的數據搜索和檢索的可管理方式存儲這樣的數據變得更加重要。現今，普通的方法是將電子數據存儲在一個或多個資料庫中。典型的資料庫可以被稱為帶有被結構化為例如使得電腦程式可以快速地搜索和選擇所期望的數據片段的數據的經組織的信息集合。此外，在這樣的環境中，聯合是指已經相互建立信任且允許在它們本身中間共享用戶身份信息的一組組織或服務提供商。隨著諸如web服務等的分布式計算模型的出現，諸如服務提供商(SP)等的實體中的依存性增加了。因此，當前的趨勢是聚焦於身份信息的組織間的管理和相互依存的管理， 而非供內部使用的身份管理解決方案。這可以被稱為聯合身份管理。一般地，聯合身份是識別以日益頻繁的速率在企業邊界之間移動的個體的分布式計算構造。聯合身份的實際應用由在相同的時刻管理若干異構系統所需的大型跨國公司來代表。在這樣的分布式系統中，存在對節點的適當管理和配置/重配置的各種挑戰。例如，個體節點可能隨機地失效，這在合適的不可預見性沒有安排妥當時可能引起數據丟失。 同樣地，常常要求圍繞系統移動所複製的數據，這進一步可以產生可靠性問題和一致性問題。此外，在與這樣的節點的全面管理相關的數據經受例如由集中式高速緩存的失效引起的損失時，可靠性問題可以進一步變得複雜。概述事務性數據存儲中的數據可以跨越充當分布式系統中的節點的許多計算機或其他設備而被複製，例如出於冗餘或高的可用性目的。然而，儘管分布式系統可以提供高的可用性保證，但在其上複製事務性數據存儲的底層計算機可能本身是不可靠的，因而使得難以跨越分布式系統中的節點維持事務性數據存儲的事務性一致性。被配置為在一組節點中的每一節點上被複製的事務性數據存儲可以被重配置為在不同的一組節點中的每一節點上被複製。可以部分地通過使用定額以事務一致的方式完成從當前配置到新配置的重配置。 當前配置和新配置中的每一個可以與至少一個定額相關聯，該定額可以少於或等於該配置中的節點的數量。可以有選擇地執行重配置操作以使得它們僅當在將要對其執行操作的配置中的一定額的節點指示同意該操作時才被執行。重配置過程可以涉及許多步驟，包括選擇用於新配置的唯一版本標識符、將在新配置中的節點上複製的事務性數據存儲更新到一致狀態、去激活舊配置並激活當前配置。 通過要求從重配置過程的一個步驟進行到後續步驟涉及從該配置中的一定額的節點獲得接受或提交，可能允許重配置過程抵禦配置中的節點的失效，同時仍保證跨越配置的一致性水平。前述是本發明的非限制性概述，本發明由所附權利要求界定。為實現前述的和相關的目的，在此結合下列描述和附圖描述所要求保護的本主題的某些說明性方面。這些方面指示可以實踐本主題的各種方式，所有這些方式都預期是在所要求保護的本主題的範圍內。當結合各圖考慮時，可以從下列詳細描述明顯看出其他優點和新穎特徵。附圖簡述不預期按比例繪製附圖。各圖中，各種圖中闡釋的每一相同的或接近相同的組件由相似的數字表示。為清晰起見，在每一圖中並非標記每一組件。各圖中

圖1闡釋根據本主題創新的特定方面的重構組件的框圖；圖2闡釋根據本主題創新的特定方面的與多個節點相關聯的示例性劃分和重建；圖3闡釋帶有可以根據本主題的一個方面創新重構的配置組件的系統的框圖；圖4A闡釋根據本主題創新的一個方面設置新配置的方法；圖4B是其中可以實踐重配置過程的網絡的框圖；圖4C是重配置過程的流程圖；圖5闡釋用於實現本主題創新的各種方面的示例性環境；以及圖6是根據本主題創新的一個方面可以被用於數據檢索的樣本計算環境的示意性框圖。詳細描述現在參考附圖描述本主題創新的各種方面，其中相似的數字始終是指相似的或對應的元素。然而，應理解，各圖和與其相關的詳細描述不旨在將所要求保護的本主題限制在所公開的特定形式。相反，其意圖是覆蓋落在所要求保護的本主題的精神和範圍內的所有修改、等效物和替代物。本發明者已經明白，隨著其中可以跨越許多計算機而複製數據的分布式計算系統的出現，存在對以事務一致的方式重配置所複製的數據的機制的需要。本發明者還明白，這樣的分布式系統頻繁地需要即使是在被用於實現分布式系統的底層計算機本身可能偶爾崩潰時也提供高的數據可用性。諸如資料庫的部分等的事務性數據可以跨越一組節點而被複製，且可能因此需要從該組添加或刪除，在該組節點中可能存在對即使在節點本身不可靠時也維持跨越該組節點而複製的數據的事務性一致性的需要。因此，在本發明的一些實施方式中，包括其中的每一個可以包含事務性數據存儲的副本的一組節點在內的當前配置可以響應於重配置請求而被重配置成包括不同的一組節點的新配置，同時跨越所複製的事務性數據存儲而維持事務性一致性。也通過使用定額在整個重配置過程中維持事務性一致性，其中舊配置和新配置中的每一個可以與至少一個定額相關聯。基於配置中的一定額的節點是否指示同意該操作， 可以有選擇進行針對該配置的重配置操作。重配置過程可以涉及許多步驟，包括選擇用於新配置的唯一版本標識符、將在新配置中的節點上被複製的事務性數據存儲更新到一致狀態、去激活舊配置和激活當前配置。確保從重配置過程的一個步驟進行到隨後的步驟要求從該配置中的一定額數量的節點獲得接受或提交，這允許重配置過程抵禦配置中的節點的失效，同時仍然確保跨越該配置的一致性水平。此外，該系統的其他方面涉及經由重構組件重構與節點(節點與實現讀/寫條件的動態定額的分布式系統相關聯)的重配置有關的數據/信息。在一個方面中，重構組件允許跨越分布式系統本身存儲信息的複製的部分副本。然後，這樣的分布式片段可以被用於以一致的方式重構中央管理系統的內容。因此，重構組件可以從該系統上的各種位置重構中央管理組件的內容，其中中央管理組件/配置組件可以被看作是高速緩存。此外，可以經由中央管理組件的協議劃分提供可伸縮性(例如，採用與被用來使得該系統的其他部分高度可用的協議相同的協議)。同樣地，將用於領導人選舉的中央管理組件用於系統的其餘部分，允許靈活性和尺度(如果使用常規的基於共識的領導人選舉算法，則通常不提供)。圖1闡釋採用重構組件101的系統100的框圖，重構組件101允許重構與分布式系統的重配置成員相關的信息。重構組件101還可以與領導人選民組件102和群集配置組件103相關聯，領導人選民組件102和群集配置組件103可以促進與主(例如，活動的)配置管理器實例/組件相關聯的指派/操作。圖2闡釋根據示例性的方面使用基於定額的方法來重構配置管理器組件的系統 200的框圖。圖3闡釋實現配置管理器組件302連同多個節點作為分布式環境的一部分的系統 300的框圖，所述分布式環境諸如可以根據本主題創新的一個方面重構的環310。配置管理器組件302可以通過實現基於動態定額的讀/寫條件且以事務一致的方式將節點(例如， 伺服器)的分布式系統的成員從舊配置重配置成新配置，這在這樣的變換期間減少了數據損失。這樣的定額可以表示預先確定的數量，其中讀定額和寫定額之和超過了該配置的節點數量(例如，給定的配置的讀定額和寫定額重疊)。圖4A闡釋用於配置節點網絡的各種階段的相關方法400，節點網絡可以根據本主題創新的進一步方面重構。一旦接收到重配置請求，主副本上的重配置代理 (Reconfiguration Agent)可以發起對舊的或現有的配置的去激活，且提供新配置的進一步的激活(例如，確保其提交被客戶機所確認的任何事務將被新配置保留；且還沒有提交或其提交還沒有被確認的事務可以或被提交或回退)。這可以包括實現四個階段，即階段1 在402處的投票和追趕在此階段期間，主副本為新配置建議全局唯一 ID。該全局唯一 ID預期對每一連續配置增加。一旦被舊配置和新配置兩者的一定額的副本接受，就保證這樣的ID大於此分區的任何先前所接受的ID。所建議的ID被發送給舊配置和新配置兩者中的所有副本，副本中的每一個基於ID是否大於它們先前已經觀察到的任何ID接受或拒絕該ID。因此，如果副本接受這樣的ID，它還可以向主副本通知其最新的事務序列號並停止接受新事務。替代地，如果副本拒絕所建議的ID，則主副本拾取新的更高ID並重啟階段1。一旦來自舊配置和新配置兩者的一定額的副本已經接受所建議的ID，則主副本指示新配置中的副本開始追趕，以使得可以跨越重配置而維持事務性一致性和數據安全性要求。這可以涉及對個體副本的追趕和事務回退的混合。此外，保證該過程得到符合內容的當前狀態的一定額的副本，且該過程提供跨越該重配置的原子性、一致性、隔離性、耐久性(ACID)性質。 一旦已經追趕到至少新配置中的一定額的副本，階段1就可以完成。階段2 在404處去激活舊配置在此階段期間，主副本協調舊配置的去激活。去激活的目的是保證，除非Cl = C2， 否則永遠不可能找到滿足以下條件的兩組副本Rl和R2 =Rl Φ R2、Rl中的每一副本rl宣稱配置Cl是最新配置且Rl至少形成Cl的寫定額、R2中的每一副本r2宣稱配置C2是最新配置且R2至少形成C2的寫定額。此外，去激活消息可以被發送給舊配置中的每一副本。 如果副本中的每一個匹配它已經接受的最新的投票建議，則副本中的每一個可以接受去激活。在副本的讀定額確認該去激活時，此階段完成。階段3 在406處激活新配置在這樣的階段期間，主副本協調新配置的激活。激活的目的是保證寫定額的新配置知道該配置在允許對該複製單元的內容作出改變之前已經被激活。這可以確保任何內容改變僅當定額的節點丟失時才丟失。該激活消息還可以被發送給新配置中的每一副本。如果這些副本中的每一個匹配它已經接受的最新的投票建議，則這些副本中的每一個可以接受激活。在新配置中的寫定額的副本已經接受激活時，這樣的階段完成。在這一點，新配置是活動的和可用的。階段4 在408處提交這樣的階段是用於提交重配置的可選階段，這是由於到階段3結束時，舊配置已經被去激活且新配置已經被激活。然而，這僅對主副本來說以及從系統外全局的觀點來說是已知的。因此，這樣的提交階段貫穿所有分布式系統中所有當事方而分發此知識，即分配給舊配置和新配置中的每一副本。可以在階段3完成之後的任何點向配置管理器通知重配置的完成而不考慮是否實現階段4。圖4B和圖4C提供上面在圖4A中描述的重配置過程的更多細節。圖4B是其中可以實踐重配置過程的示例性網絡420。網絡420包括在任何合適的計算機通信介質(例如， 無線通信或有線通信，等等)上通信的多個節點，包括可以類似於上面結合圖1-圖3所討論的配置管理器組件的配置管理器421。網絡420也包括當前的(即「舊的」)配置428中的第一組節點422、似4和426，以及新配置448中的第二組節點442、444和446。第一組節點和第二組節點可以相互具有任何合適的關係。例如，第一組節點和第二組節點可以具有公用的一個或多個節點，每一組可以包括相同的一組節點，或者這兩組節點可以完全不相交。多個節點包括配置管理器421、節點422···426，且可以以任何合適的方式(包括硬體和軟體的任何合適的組合)實現節點442…446。例如，配置管理器421和節點422···似6中的每一個可以是使用任何合適的計算機體系結構的臺式計算機或伺服器計算機，且可以包括作業系統，例如由微軟公司開發的WINDOWS 作業系統的變體。在一些實施方式中，可以在被配置為作為相干單元而操作的多個計算機上實現一個或多個節點，例如配置管理器421， 例如出於負載平衡或冗餘目的。每一節點都可以包含或被連接到包含分布式數據的複製的存儲介質。節點422、 424和426中的每一個包括分別被闡釋為副本432、434和436的分布式數據的副本。分布式數據可以是分布式存儲系統的組件。例如，在節點422、似4和似6上複製的分布式數據可以是分布式資料庫的部分，例如該資料庫中的數據分區。可以使用任何合適的分布式資料庫。在一些實施方式中，可以使用由微軟公司開發的SQL krver 資料庫的變體。如上面所討論的，副本432、434和436中的每一個可以存儲多個事務。重配置操作可以改變存儲數據的方式。代替在第一組節點上被複製、在圖4B中被闡釋為當前配置428，在重配置之後，當前的信息將在第二組節點上被複製、在圖4B中被闡釋為新配置448。因而，至少到重配置過程結束時，新配置428中的節點442、444和446中的每一個也可以分別包含副本452、妨4和456。重配置過程可以涉及執行從當前配置4 到新配置448的實際數據移動，例如如果新配置448中的節點最初不包含正被複製的數據分區的副本，或者如果新配置448中的節點上的副本過期。然而，在一些實施方式中或在一些場景中，新配置中的各節點可能已經包含數據分區的最新副本，在該情況中重配置過程可以主要涉及去激活舊配置和激活新配置。在一些實施方式中，由配置管理器421發起重配置過程。配置管理器421可以出於多種原因而發起重配置。例如，重配置可以由各種事件觸發，這些事件包括節點或副本失效、節點或副本恢復、副本創建或其他管理動作。重配置過程可以在網絡中的任何合適的節點上執行。在一些實施方式中，配置管理器421可以主要負責實現重配置過程，儘管在其他實施方式中，配置管理器421可以向網絡中的另一節點發起重配置請求，該另一節點然後可以響應於該請求而執行重配置過程。在一些實施方式中，新配置中的一個節點可以被指派為在圖4B中被闡釋為「主重配置代理」節點442的「主節點」，它負責響應於來自配置管理器428的重配置請求而執行重配置過程。實現重配置過程可以涉及將諸如重配置消息458 和459等的消息發送給當前配置4 和新配置448兩者中的主節點442和其他節點，並從這些節點發送這些消息。圖4C闡釋可以在重配置操作中使用的基於定額的處理的多種方式。圖4C闡釋， 作為重配置分布式資料庫的部分的重配置操作，諸如去激活舊配置和激活新配置等。如果這些重配置操作中的每一個中所涉及的一定額的節點不指示接受指示重配置操作應被執行的消息，則重配置操作不進行。相反，在重配置操作中所涉及的適當定額的節點響應於重配置消息或命令而指示接受時，重配置操作可以進行。正如圖4C中所闡釋的，重配置過程可以涉及將數據分區從節點的當前的(即「舊的」)配置移動到節點的新配置。儘管在隨後的討論中在圖4C中闡釋的過程被假設為在新配置中的主節點上實現，且被假設為響應於從配置管理器接收重配置請求而開始，但圖4C 的過程可以在網絡中的任何合適的節點上實現，且可以基於任何何時的事件、刺激或條件而開始。在一些實施方式中，數據分區的每一配置可以與版本標識符相關聯，以使得數據分區的新配置與不同的版本號相關聯。儘管可以選擇任何合適的方案來實現版本標識符， 但在一些實施方式中，用於數據分區的新配置的版本標識符也應該高於先前或當前與該數據分區相關聯的版本標識符的任何其他值。因而，新配置的版本標識符應該高於與舊配置相關聯的版本標識符。與新配置相關聯的版本標識符也預期高於與該數據分區的任何其他配置相關聯的任何版本標識符，包括與該數據分區的失效重配置相關聯的版本標識符。儘管如此，在其他實施方式中，可以使用其他機制來查明當前的版本標識符。在框460，主節點可以為與新配置相關聯的版本標識符確定新的值。在一些實施方式中，主節點可以選擇高於與舊配置相關聯的版本號的值。然後，主節點可以將包含這一為新的版本標識符建議的值的消息發送給新配置和舊配置兩者中的節點。然後，主節點可以等待，直到它已經從至少新配置中的一定額的節點以及舊配置中的一定額的節點接收到指示各節點已經接受為新配置建議的版本標識符的響應。在一些實施方式中，與舊配置和新配置相關聯的定額將是相同的，或者可以是該配置中的節點的相同百分比。然而，不要求與舊配置和新配置相關聯的定額是相同的或者以相同方式確定。在一些實施方式中，主節點可以等待舊配置中的讀定額的節點接受，並等待新配置中的寫定額的節點接受。在一些實施方式中，重配置過程可以不進行(即，可以被掛起)，直到舊配置中的讀定額的節點和新配置中的寫定額的節點接受所建議的版本標識符。此外，在一些實施方式中，即使在舊配置中的讀定額的節點和新配置中的寫定額的節點已經接受新的所建議的版本標識符之後，主節點可以仍然等待預先確定的時間或其他事件，以便允許較慢的副本響應，且可能拒絕所建議的版本標識符。在框462，然後，主節點可以檢查它是否已經從新配置或舊配置中的任一個中的任何節點接收到指示節點已經拒絕建議的響應。節點可以出於多種原因拒絕所建議的版本標識符。例如，如果節點先前看到高於所建議的版本標識符的與該數據分區相關聯的版本標識符，則節點可以拒絕該建議。如果是這樣，拒絕節點可以在拒絕響應中向主節點發送它先前已經看到的版本標識符。然後，該過程可以進行到框464，框464中，該過程在其上運行的節點可以判斷它是否仍然是新配置的主節點。在一些實施方式中，出於多種原因，新配置的主節點可以改變，這可以響應於來自配置管理器的命令而進行。如果在框464重配置過程在其上運行的節點判斷它不再是主節點，則在框466它可以中止重配置過程。可以在這一點進行圖4C的重配置過程。否則，如果在框464判斷重配置過程在其上運行的節點仍然是主節點，則主節點可以通過返回到框460來重啟重配置過程。然後，它可以重複上面所討論的過程，此時選擇比任何先前看到的該配置的版本標識符高的為新配置建議的新的版本標識符，包括被包括在響應於先前的建議而發送的拒絕消息中的版本標識符。否則，如果主節點在框462判斷沒有節點拒絕該建議，那麼，在框468，主節點可以用舊配置中最近複製的數據來更新新配置的節點中複製的數據。這可以以任何合適的方式進行。在一些實施方式中，此操作可以以兩個步驟進行。首先，如果主節點不包含來自舊配置的副本的最近複製，那麼，主節點可以用最近的數據更新(或「追趕」)其來自舊配置中的節點的數據分區的本地副本。在一些實施方式中，從接受版本標識符的舊配置的節點中選擇帶有最近數據的舊配置中的節點，如步驟460中所討論的。判斷節點包含最新的數據可以以任何合適的方式來進行。在一些實施方式中，這可以通過檢查與被存儲在該副本中的最新的事務相關聯的標識符來進行。—旦主節點具有副本的最近複製，在一些實施方式中，然後，主節點就可以禁用數據分區上的用戶事務，且指示新配置中的其他節點更新它們的副本。然後，主節點可以等待更新新配置中的寫定額的節點。在一些實施方式中，更新副本可以涉及更新該副本以至少存儲全部已經由舊配置中的寫定額的副本提交的事務。在一些實施方式中，新配置中的寫定額的節點上的副本可以被更新以存儲一致的一組事務。如果新配置的特定副本包含比由舊配置中的寫定額的節點提交的事務稍後的事務，則更新副本可以因而也包括事務回退。如果用戶事務在它被提交之前就被中止，則可以出現這樣的情況，使得事務被存儲在少於舊配置中的寫定額的節點上。在一些實施方式中，重配置過程可以不進行(即，可以被掛起)，直到新配置中的寫定額的副本已經被更新以存儲一致的一組事務。一旦新配置中的寫定額的節點已經被追趕，重配置過程就可以涉及將重配置消息發送到舊配置和/或新配置的節點，並等待給定的配置中的一定額的節點接受該消息。重配置消息可以包括例如激活消息或去激活消息。例如，在由圖4C所闡釋的示例中，在框 470，然後，主節點可以將去激活消息發送給舊配置中的節點。去激活消息可以包括所建議的新配置，所建議的新配置可以包括所建議的新配置中的節點的標識符。如果舊配置中的節點接受去激活消息，它可以將其當前活動配置的狀態改變為「被去激活」，且可以將所建議的新配置存儲在該節點上的合適的計算機存儲中，例如存儲在硬碟上。舊配置中的每一節點也都可以被配置為將指示該節點是接受還是拒絕去激活消息的響應發送回給主節點。然後，主節點可以等待來自舊配置中的節點的指示它們已經接受去激活消息的讀定額的響應。接下來，在框472，主節點可以判斷來自舊配置中的至少一個節點的對去激活消息的響應是否指示該節點已經拒絕去激活消息。如果任何節點已經拒絕去激活消息，則重配置過程可以進行到框464，在這一點，重配置過程將重啟或中止，如上面所討論的。否則，在框472，如果判斷舊配置中沒有節點拒絕去激活消息，則一旦舊配置中的讀定額的節點已經指示它們已經接受重配置消息，在框474，主節點可以就開始激活新配置。這可以通過將激活消息發送給新配置中的所有其他節點來進行。新配置中的其他節點中的每一個可以被配置為將指示該節點是接受還是拒絕激活消息的響應發送給主節點。如果節點接受激活消息，則它可以適當地將其狀態更新為「被激活」狀態。在一些實施方式中， 屬於舊配置和新配置兩者的部分的節點可能已經將新配置的狀態本地存儲(例如，在接受該去激活消息之後)為所建議的配置，在這種情況中，在框474，它可以將所存儲的狀態從 「所建議的」更新為「被激活」。然後，主節點可以等待來自新配置中的節點的指示它們已經接受激活消息的寫定額的響應。接下來，在框476，主節點可以判斷來自新配置中的至少一個節點的對激活消息的響應是否指示該節點已經拒絕激活消息。如果任一節點已經拒絕激活消息，則重配置過程可以進行到框464，在這一點，重配置過程將重啟或中止，如上面所討論的。然而，如果新配置中的寫定額的節點接受激活消息且沒有節點拒絕激活消息，則然後主節點可以再次允許該配置上的事務，且也可以向諸如配置管理器421等的配置管理器通知所提交的新配置的狀態。該過程也可以進行到框478，在這一點，主節點可以提交新配置。此可選的操作可以涉及將包含舊配置和新配置兩者的配置提交信息發送給網絡中的所有節點，使得數據分區的副本從屬於新配置。此步驟可以是可選的，這是因為在一些實施方式中，一旦新配置中的寫定額的節點已經接受激活消息新配置就可以立即變成活動的和完整的。圖4C的過程可以在此處進行，這是因為新配置可以完全被激活和可用。此申請中所使用的術語「組件」、「系統」預期是指計算機相關的實體，可以是硬體、 硬體和軟體的組合、軟體或執行中軟體中的任一種。例如，組件可以是但不限於是在處理器上運行的進程、處理器、對象、可執行程序、執行的線程、程序和/或計算機。作為闡釋，在伺服器上運行的應用程式和該伺服器兩者都可以是組件。一個或多個組件可以駐留在進程和 /或執行的線程內，且組件可以位於一個計算機上和/或在兩個或更多個計算機之間分布。此外，可以使用生產軟體、固件、硬體或其任何組合的標準編程和/或工程技術來將本主題創新的全部或部分實現為系統、方法、裝置或製品，以便控制計算機實現所公開的創新。例如，計算機可讀介質可以包括但不限於磁存儲設備(例如，硬碟、軟盤、磁條…)、光碟(例如，緊緻盤(⑶)、數字多用盤(DVD)…)、智慧卡和閃速存儲器設備(例如，卡、棒、鍵驅動…)。另外，應明白，載波可以被用來運載計算機可讀電子數據，例如在傳送和接收電子郵件或訪問諸如網際網路或區域網(LAN)等的網絡中使用的那些計算機可讀電子數據。當然，本領域中的技術人員將認識到，可以在不偏離所要求保護的本主題的情況下對此配置做出許多修改。為了提供用於所公開的本主題的各種方面的上下文，圖5和圖6以及下列的討論旨在提供其中可以實現所公開的本主題的各種方面的合適的環境的簡要、一般的描述。儘管以上已經在計算機和/或計算機上運行的電腦程式的計算機可執行指令的一般上下文中描述本主題，但本領域中的技術人員將認識到，也可以與其他程序模塊組合實現本創新。一般地，程序模塊包括執行特定任務和/或實現特定抽象數據類型的例程、程序、組件、 數據結構等等。此外，本領域中的技術人員將明白，可以與其他計算機系統配置一起實踐本創新方法，其他計算機系統包括單處理器計算機系統或多處理器計算機系統、小型計算設備、大型計算機以及個人計算機、手持式計算設備(例如，個人數字助理(PDA)、電話、手錶…)、基於微處理器的或可編程的消費性電子設備或工業電子設備等等。也可以在分布式計算環境中實踐所闡釋的各方面，分布式計算環境中，任務由通過通信網絡連結的遠程處理設備執行。然而，可以在獨立計算機上實踐本創新的一些(如果不是全部的話)方面。 在分布式計算環境中，程序模塊可以是位於本地存儲器存儲設備和遠程存儲器存儲設備兩者ο參考圖5，描述包括計算機512的用於實現本主題創新的各種方面的示例性環境 510。計算機512包括處理單元514、系統存儲器516和系統總線518。系統總線518將包括但不限於系統存儲器516的系統組件耦合到處理單元514。處理單元514可以是各種可用的處理器中的任何處理器。雙微處理器和其他多處理器體系結構也可以被用作處理單元 514。系統總線518可以是包括使用任何種類的可用總線體系結構的存儲器總線或存儲器控制器、外圍總線或外部總線和/或局部總線的若干類型的總線結構中的任一總線結構，這些總線體系結構包括但不限於II位總線、工業標準體系結構(ISA)、微通道體系結構(MSA)、擴展ISA(EISA)、智能驅動電子設備(IDE)、VESA局部總線(VLB)、外圍組件互連(PCI)、通用串行總線(USB)、高級圖形埠(AGP)、個人計算機存儲器卡國際協會總線 (PCMCIA)和小型計算機系統接口(SCSI)。系統存儲器516包括易失性存儲器520和非易失性存儲器522。包含例如在啟動期間在計算機512內的各元件之間傳遞信息的基本例程的基本輸入/輸出系統(BIOS)被存儲在非易失性存儲器522中。例如，非易失性存儲器522可以包括只讀存儲器(ROM)、 可編程ROM(PROM)、電可編程ROM(EPROM)、電可擦除ROM(EEPROM)或閃速存儲器。易失性存儲器520包括充當外部高速緩衝存儲器的隨機存取存儲器(RAM)。作為闡釋而非限制， RAM可以以許多形式獲得，例如同步RAM (SRAM)、動態RAM (DRAM)、同步DRAM (SDRAM)、雙倍數據率 SDRAM (DDR SDRAM)、增強 SDRAM (ESDRAM)、Synchlink DRAM (SLDRAM)和直接 Rambus RAM(DRRAM)。計算機512也包括可移動/不可移動、易失性/非易失性計算機存儲介質。圖5闡釋盤存儲524，其中這樣的盤存儲5 包括但不限於比如磁碟驅動器、軟盤驅動器、帶驅動器、Jaz驅動器、Zip驅動器、LS-60驅動器、閃速存儲器卡或存儲器棒的設備。另外，盤存儲5M可以包括與其他存儲介質分離或組合的存儲介質，其他存儲介質包括但不限於光碟驅動器，諸如緊緻盤ROM設備(⑶-ROM)、⑶可記錄驅動器(⑶-R驅動器)、⑶可重寫驅動器 (⑶-RW驅動器)或數字多用盤ROM驅動器(DVD-ROM)。為促進將盤存儲設備5 連接到系統總線518，通常使用諸如接口 5 等的可移動或不可移動接口。應明白，圖5描述充當在用戶和在合適的操作環境510中所描述的基本計算機資源之間的媒介物的軟體。這樣的軟體包括作業系統528。可以被存儲在盤存儲5M上的作業系統5 操作為控制和分配計算機系統512的資源。系統應用程式530通過被存儲在系統存儲器516中或在盤存儲5M上的程序模塊532和程序數據534來利用作業系統5 對資源的管理。應明白，可以與各種作業系統或作業系統的組合一起實現在此描述的各種組件。用戶通過輸入設備536將命令或信息輸入到計算機512中。輸入設備536包括但不限於諸如滑鼠、跟蹤球、觸筆、觸控板等的定點設備、鍵盤、話筒、操縱杆、遊戲墊、圓盤式衛星天線、掃描儀、TV調諧器卡、數位相機、數碼攝像機、網絡攝像頭等等。這些和其他輸入設備經由接口埠 538通過系統總線518連接到處理單元514。接口埠 538包括例如串行埠、並行埠、遊戲埠和通用串行總線(USB)。輸出設備540使用與輸入設備536相同類型的埠中的一些。因而，例如，USB埠可以被用於向計算機512提供輸入，且被用於將信息從計算機512輸出到輸出設備M0。提供輸出適配器M2以便闡釋存在比如監視器、揚聲器和印表機的一些輸出設備M0，以及要求專用的適配器的輸出設備M0。作為闡釋而非限制，輸出適配器542包括提供在輸出設備540和系統總線518之間的連接的裝置的顯卡和音效卡。應注意，諸如遠程計算機544等的其他設備和/或設備的系統提供輸入能力和輸出能力兩者。計算機512可以使用到諸如遠程計算機544等的一個或多個遠程計算機的邏輯連接在聯網環境中操作。遠程計算機544可以是個人計算機、伺服器、路由器、網絡PC、工作站、基於微處理器的設備、對等設備或其他普通網絡節點等等，且通常包括相對於計算機 512描述的許多或全部元件。為簡潔起見，與遠程計算機544 —起僅闡釋存儲器存儲設備 5460遠程計算機544通過網絡接口 548邏輯上被連接到計算機512，且然後經由通信連接 550物理上被連接。網絡接口 548包括諸如區域網(LAN)和廣域網(WAN)等的通信網絡。 LAN技術包括光纖分布數據接口(FDDI)、銅分布數據接口(⑶DI)、乙太網/IEEE 802. 3、令牌環/IEEE 802. 5等等。WAN技術包括但不限於點對點鏈路、如綜合業務數字網絡(ISDN) 和及其變體這樣的電路交換網絡、分組交換網絡和數字用戶線路(DSL)。通信連接550是指被用來將網絡接口 548連接到總線518的硬體/軟體。儘管為了說明的清晰起見而在計算機512中示出通信連接550，但它也可以外置於計算機512。僅出於示例性目的，連接到網絡接口 548所必須的硬體/軟體包括內置技術和外置技術，諸如包括普通電話分級數據機、電纜數據機和DSL數據機在內的數據機、 ISDN適配器和乙太網卡。圖6是根據本主題創新的一個方面可以被用於將節點實現為聯合的一部分的樣本計算環境600的示意性框圖。系統600包括一個或多個客戶機610。客戶機610可以是硬體和/或軟體(例如，線程、進程、計算設備)。系統600也包括一個或多個伺服器630。 伺服器630也可以是硬體和/或軟體(例如，線程、進程、計算設備)。伺服器630可以容納線程以便例如通過應用在此描述的各組件來執行變換。在客戶機610和伺服器630之間的一種可能的通信可以是以適於在兩個或更多個計算機進程之間傳送的數據分組的形式。系統600包括可以被用來促進在客戶機610和伺服器630之間的通信的通信框架650。客戶機610操作上被連接到一個或多個可以被用來存儲對客戶機610來說是本地的信息的客戶機數據存儲660。類似地，伺服器630操作上被連接到一個或多個可以被用來存儲對伺服器 630來說是本地的信息的伺服器數據存儲640。已經這樣描述了本發明的至少一種實施方式的若干方面，應明白，本領域中的技術人員將容易地進行各種變更、修改和改進。作為可能的變更的示例，在以上所描述的示例性實施方式中，節點的定額被選擇為節點的大多數。具有比節點的大多數更大或更少的定額的其他實現是可能的。此外，當節點失效或下線時，配置的定額可以隨時間改變。這樣的變更、修改和改進預期是本公開內容的部分，且預期是在本發明的精神和範圍內。因此，前述的描述和圖僅作為示例。可以以眾多方式中的任何方式來實現上面所描述的本發明的實施方式。例如，可以使用硬體、軟體或其組合來實現各實施方式。在以軟體實現時，無論是在單個計算機中提供還是在多個計算機當中分布，軟體代碼可以在任何合適的處理器或處理器的集合上執行。進一步，應明白，可以以許多形式中的任一形式來具體化計算機，例如機架式計算機、臺式計算機、膝上型計算機或平板計算機。另外，計算機可以被嵌入在一般不被認為是計算機但具有合適的處理能力的設備中，包括個人數字助理(PDA)、智慧型電話或任何其他合適的可攜式或固定式電子設備。 而且，計算機可以具有一個或多個輸入和輸出設備。這些設備以及其他事物可以被用來呈現用戶界面。可以被用於提供用戶界面的輸出設備的示例包括用於輸出的視覺呈現的印表機或顯示屏以及用於輸出的聽覺呈現的揚聲器或其他聲音生成設備。可以用於用戶界面的輸入設備的示例包括鍵盤和定點設備，例如滑鼠、觸控板和數位化輸入板。作為另一示例，計算機可以通過語音識別或以其他聲音格式接收輸入信息。這樣的計算機可以由包括諸如企業網絡或網際網路等的區域網或廣域網的以任何合適的形式的一個或多個網絡互連。這樣的網絡可以基於任何合適的技術，且可以根據任何合適的協議操作，並可以包括無線網絡、有線網絡或光纖網絡。而且，在此略述的各種方法或進程可以被編碼為是可在採用各種作業系統或平臺中的任何一個的一個或多個處理器執行的軟體。另外，這樣的軟體可以使用許多合適的程式語言和/或編程或腳本工具中的任一個來編寫，且也可以被編譯為在框架或虛擬機上執行的可執行機器語言代碼或中間代碼。在這一方面，本發明可以被具體化為用一個或多個程序編碼的計算機可讀介質 (或多個計算機可讀介質)(例如，計算機存儲器、一個或多個軟盤、緊緻盤、光碟、磁帶、閃速存儲器、以現場可編程門陣列或其他半導體器件的電路配置、或其他有形的計算機存儲介質)，當在一個或多個計算機或其他處理器上執行這些程序時，這些程序執行實現上面所討論的本發明的各種實施方式的方法。計算機可讀介質或介質可以是移動式的，以使得被存儲在其上的一個或多個程序可以被加載到一個或多個不同的計算機或其他處理器上，以便實現上面所討論的本發明的各種方面。在此以通常意義使用的術語「程序」或「軟體」是指可以被用來編程計算機或其他處理器以實現上面所討論的本發明的各種方面的任何類型的計算機代碼或計算機可執行指令集。另外，應明白，根據此實施方式的一個方面，在被執行時執行本發明的方法的一個或多個電腦程式不需要駐留在單個計算機或處理器上，而是可以以模組方式分布許多不同的計算機或處理器中，以便實現本發明的各種方面。計算機可執行指令可以是以許多形式，例如由一個或多個計算機或其他設備執行的程序模塊。一般地，程序模塊包括執行特定任務或實現特定抽象數據類型的例程、程序、 對象、組件、數據結構等等。通常，在各種實施方式中，程序模塊的功能可以根據需要組合或分布。而且，數據結構可以以任何合適的形式被存儲在計算機可讀介質中。出於闡釋的簡明性起見，數據結構可以被示出為具有通過數據結構中的位置相關的欄位。這樣的關係可以同樣通過用傳達各欄位之間的關係的計算機可讀介質中的位置來為各欄位分配存儲來獲得。然而，任何合適的機制都可以被用於在數據結構的欄位中的信息之間建立關係，包括通過使用指針、標籤或在數據元素之間建立關係的其他機制。可以單獨使用、組合使用或以前述中所描述的實施方式中不具體討論的各種排列來使用本發明的各種方面，且因而本發明的各種方面在其應用方面不限於前述描述中陳述的或各圖中闡釋的組件的細節或排列。例如，可以以任何方式將在一種實施方式中描述的各方面與在其他實施方式中描述的各方面組合起來。而且，本發明可以被具體化為方法，已經提供該方法的示例。可以以任何合適的方式來排序作為該方法的部分而被執行的動作。因此，可以構建其中以與所闡釋的次序不同的次序執行各動作的各實施方式，這可以包括同時地執行一些動作，即使在說明性的實施方式中被示出為順序的動作。在權利要求中諸如「第一」、「第二」、「第三」等等的次序術語來修改權利要求元素的使用並不獨立地意味著一個權利要求元素相對於另一權利要求元素的任何優先級、優先或次序或者方法的動作被執行的時間順序，而是僅被用作將具有某種名稱的一個權利要求元素與具有相同名稱(只供次序術語的使用)的另一元素區分開來的標籤，以便區分權利要求包括的元素。而且，在此使用的措辭和術語是出於描述的目的且不應被看作是限制。在此使用 「包括(including) 」、「包括(comprising) 」或「具有」、「包含」、「涉及」及其變更來意指包含其後列出的項及其等效物以及附加的項。
權利要求
1.一種用計算機可執行指令編碼的計算機可讀存儲介質，當所述計算機可執行指令在網絡中的計算機中的至少一個處理器上被執行時，實現一種與所述網絡G20)中的第一組 (428,448)節點交互以便對分布式資料庫執行重配置操作的方法，其中所述第一組(428， 448)節點與指定所述第一組(428，448)節點中的節點數量的至少一個定額值相關聯，所述方法包括以下動作將重配置消息(458，459)發送給所述第一組(428，448)節點； 從所述第一組(428，448)節點的至少一個子集中的每一節點接收對所述重配置消息 (458,459)的響應，其中從所述第一組(428，448)節點中的節點接收的每一響應包含接受或拒絕所述重配置消息058，459)的指示；判斷包含接受所述重配置消息G58，459)的指示的所接收的響應的數量是否至少是與所述第一組(428，448)節點相關聯的第一定額值；以及基於所述判斷有選擇地繼續進行重配置操作，所述有選擇地進行包括 在包含接受所述重配置消息058，459)的指示的所接收的響應的數量至少是與所述第一組(428，448)節點相關聯的第一定額值時，繼續進行重配置操作。
2.如權利要求1所述的計算機可讀存儲介質，其特徵在於 所述第一組節點是當前活動的一組(428)節點；以及所述重配置消息(459)包括發信號通知所述第一組節點將不再是所述當前活動的一組(428)節點的去激活消息。
3.如權利要求1所述的計算機可讀存儲介質，其特徵在於 所述第一組節點不是當前活動的一組(448)節點；以及所述重配置消息(458)包括發信號通知所述第一組節點將是所述當前活動的一組 (428)節點的激活消息。
4.如權利要求1所述的計算機可讀存儲介質，其特徵在於，所述方法進一步包括在從所述第一組(428，448)節點的至少一個子集中的每一節點接收對所述重配置消息058，459)的響應之後，判斷所接收的對所述重配置消息的響應是否包含拒絕所述重配置消息的指示；以及在判斷所接收的對所述重配置消息的響應包含拒絕所述重配置消息的指示時，重啟重配置過程。
5.如權利要求1所述的計算機可讀存儲介質，其特徵在於所述網絡進一步包括第二組(448)節點，所述第二組節點與所述第二定額值相關聯， 所述第二定額值指定所述第二組節點中的節點的數量；以及所述方法進一步包括對與所述第一定額值相關聯的所述第一組(428)節點執行如權利要求1所述的動作， 其中用於對所述第一組節點執行的動作的所述重配置消息(459)包括去激活消息059)； 以及在包含接受所述重配置消息的指示的所接收的響應的數量是至少與所述第一組(428) 節點相關聯的第一定額值時對與所述第二定額值相關聯的所述第二組(448)節點執行如權利要求1所述的動作，其中用於對所述第二組節點執行的所述動作的所述重配置消息(458)包括激活消息 (458)。
6.如權利要求5所述的計算機可讀存儲介質，其特徵在於 所述網絡(420)進一步包括配置管理器G21)；所述第二組節點包括主節點G42)；以及在響應於從所述配置管理器接收重配置請求而在主節點上的至少一個處理器上執行被編碼在所述計算機可讀存儲介質上的所述計算機可執行指令時，實現所述方法。
7.如權利要求6所述的計算機可讀存儲介質，其特徵在於，所述方法進一步包括 將配置提交信息發送(478)給所述配置管理器、所述第一組節點和所述第二組節點，所述配置提交信息包括用於所述第一組節點的標識符和用於所述第二組節點的標識符。
8.一種將在網絡G20)中的第一組(428)節點上複製的數據分區重配置成在所述網絡G20)中的第二組(448)節點上複製的方法，其中所述第一組節點和所述第二組節點中的每一組都與指定所述組中的節點的數量的至少一個定額值相關聯，所述方法包括操作所述網絡中的節點上的至少一個處理器以執行以下動作 將去激活消息(459)發送給所述第一組節點；從所述第一組節點的至少一個子集中的每一節點接收對所述去激活消息的響應，其中，從所述第一組節點中的節點所接收的每一響應包含接受或拒絕所述去激活消息的指示；判斷包含接受所述去激活消息的指示的所接收的響應的數量是否至少是與所述第一組節點相關聯的第一定額值；以及在包含接受所述去激活消息的指示的所接收的響應的數量至少是與所述第一組節點相關聯的第一定額值時將激活消息(458)發送給所述第二組節點；從所述第二組節點的至少一個子集中的每一節點接收對所述激活消息的響應，其中從所述第二組節點中的節點所接收的每一響應都包含接受或拒絕所述激活消息的指示；判斷包含接受所述激活消息的指示的所接收的響應的數量至少是否是與所述第二組節點相關聯的第一定額值；以及在包含接受所述激活消息的指示的所接收的響應的數量至少是與所述第二組節點相關聯的第一定額值時 完成所述重配置。
9.如權利要8所述的方法，其特徵在於，所述方法進一步包括在從所述第一組節點的至少一個子集中的每一節點接收對所述去激活消息的響應之後，判斷(472)所接收的對所述去激活消息響應是否包含拒絕所述去激活消息的指示；以及在判斷所接收的對所述去激活消息的響應包含拒絕所述去激活消息的指示時，重啟重配置過程。
10.如權利要求9所述的方法，其特徵在於，所述方法進一步包括在從所述第二組節點的至少一個子集中的每一節點接收對所述激活消息的響應之後， 判斷(476)所接收的對所述激活消息的響應是否包含拒絕所述激活消息的指示；以及在判斷所接收的對所述激活消息的響應包含拒絕所述激活消息的指示時，重啟重配置過程。
11.如權利要8所述的方法，其特徵在於所述第一組節點和所述第二組節點中的每一組與讀定額值和寫定額值相關聯，其中對於所述第一組節點和所述第二組節點中的每一組與所述組相關聯的所述讀定額值和與所述組相關聯的所述寫定額值中的每一個指定所述組中的節點的數量；與所述組相關聯的所述讀定額值和與所述組相關聯的所述寫定額值之和大於所述組中的節點的總數；與所述第一組節點相關聯的所述第一定額值包括與所述第一組節點相關聯的所述讀定額值；以及與所述第二組節點相關聯的所述第一定額值包括與所述第二組節點相關聯的所述寫定額值。
12.如權利要求11所述的方法，其特徵在於 所述第一組節點與版本標識符相關聯；以及；所述方法進一步包括，在將去激活消息發送給所述第一組節點之前 選擇與所述第二組節點相關聯的版本標識符，其中與所述第二組節點相關聯的版本標識符具有大於與所述第一組節點相關聯的版本標識符的值；向所述第一組節點和所述第二組節點發送包括與所述第二組節點相關聯的版本標識符的重配置建議；從所述第一組節點的至少一個子集中的每一節點和從所述第二組節點的至少一個子集中的每一節點接收對所述重配置建議的響應，其中從節點接收的每一響應包含接受或拒絕所述重配置建議的指示；判斷所接收的對所述重配置建議的響應是否包含拒絕所述重配置建議的指示；以及在判斷所接收的響應包含拒絕所述重配置建議的指示時選擇與所述第二組節點相關聯的新版本標識符，其中與所述第二組節點相關聯的所述新版本標識符具有比包含拒絕所述重配置建議的指示的所述所接收的響應中所包括的版本標識符大的值；以及向所述第一組節點和所述第二組節點發送包括與所述第二組節點相關聯的所述新版本標識符的重配置建議；判斷來自包含接受所述建議消息的指示的所述第一組節點的所接收的響應的所述第一數量是否至少是與所述第一組節點相關聯的所述讀定額值；判斷來自包含接受所述建議消息的指示的所述第二組節點的所接收的響應的所述第二數量是否至少是與所述第二組節點相關聯的所述寫定額值；以及在不能判斷所述第一數量至少是與所述第一組節點相關聯的所述讀定額值且所述第二數量至少是與所述第二組節點相關聯的所述寫定額值時，掛起所述重配置過程。
13.如權利要求12所述的方法，其特徵在於 所述數據分區存儲多個事務；以及所述方法進一步包括，在判斷所述第一數量至少是與所述第一組節點相關聯的所述讀定額值且所述第二數量至少是與所述第二組節點相關聯的所述寫定額值之後指示所述第二組節點中的每一節點更新被存儲在所述節點上的所述數據分區的副本， 其中所更新的副本包含已經被存儲為在所述第一組節點的至少一個子集上被提交的每一事務，所述第一組節點的所述子集的大小是與所述第一組節點相關聯的所述寫定額值；判斷已經更新所述數據分區的副本的所述第二組節點的數量是否至少是與所述第二組節點相關聯的所述寫定額值；以及在判斷已經更新所述數據分區的所述副本的所述第二組節點的數量至少是所述第二組節點的所述寫定額值時，掛起所述重配置過程。
14.如權利要8所述的方法，其特徵在於 所述第二組節點包括主節點G42)；以及操作所述網絡中的節點上的至少一個處理器包括操作所述主節點上的至少一個處理ο
15.如權利要14所述的方法，其特徵在於 所述網絡進一步包括配置管理器G21)；以及響應於從所述配置管理器接收重配置請求，執行由所述主節點上的所述至少一個處理器執行的所述動作。
全文摘要
公開了還原分布式環境中的節點的失效重配置的系統和方法。通過分析來自與配置相關聯的讀/寫定額的節點的報告，可以促進數據分區的自動恢復。此外，配置管理器組件跟蹤複製單元的當前配置並判斷是否要求重配置(例如，由於節點失效、節點恢復、副本添加/刪除、副本移動、或副本角色改變等等)。可以基於與新配置和舊配置相關聯的動態定額，以事務一致的方式執行被激活為從舊配置複製到在新配置上複製的數據的重配置。
文檔編號G06F17/00GK102197388SQ200980142631
公開日2011年9月21日 申請日期2009年10月16日 優先權日2008年10月23日
發明者S·O·沃蒂萊寧, G·K·R·卡基法亞, A·卡爾漢, L·迅 申請人:微軟公司