TW201601056A - 使用邏輯文件日誌之可擴展最終一致性系統 - Google Patents

Abstract

本文提供一種可擴展最終一致性系統。該系統使用邏輯文件日誌，來提供橫越大型服務中的多個分區之最終一致性。該系統透過並行化而允許對於文件的大規模相互關聯圖進行辦理編輯，而不犧牲線性可擴展性。該系統從複製的儲存分離編輯的授權，以允許有效率的辦理與線性可擴展性。所有文件寫入都寫入至日誌中的文件特定分區，其中該等所有文件寫入係排序，直到更改傳送至儲存庫的檢視型分區。藉由不斷地檢查日誌並且嘗試複製任何未決的文件寫入至儲存庫，該系統提供最終一致性，而不需複雜的同步機制。該系統以允許最終影響多於一個文件的文件寫入透過日誌有效率地處理作為對於單一文件的編輯之方式，來模型化文件之間的成員以及包含關係。

Description

使用邏輯文件日誌之可擴展最終一致性系統

本發明係關於使用邏輯文件日誌之可擴展最終一致性系統。

大型服務允許橫越大量資料的辦理並且通常維持資料的多個複製本。底層資源具有有限的限制，這會限制在任何單一次辦理中可處理的資料數量。因此，大型服務通常設計有固定的尺度單元。當服務上的負載超過尺度單元時，可增加額外的尺度單元，且該資料可橫越多個尺度單元分割。雖然這允許該服務適應於增加的資料量，但是橫越已經分割的資料無法再執行辦理。

此問題的傳統解決方案包括使用同步機制來使資料一致，迫使資料上的人工分割適合於尺度單元，或放棄辦理。同步機制通常非常複雜並且具有多重主導性的問題。若對文件做出衝突的編輯，則需要使用者的介入來解決衝突。因為傳送的延遲，在使用者已經確認辦理成功並且登出該服務之後，衝突可能發生。因此，衝突可能維持一段長時間都未解決。

最少化未解決的衝突的一種機制為具有負責特定記 錄的權限，但是當記錄被複製並且儲存在多個位置時，這無法有效率地被處理。傳統的解決方案使用共識協定(例如Paxos)在儲存器複製本的頂部上建構人工權限。但是，當共識系統中的節點不可用或因為網絡中斷而無法溝通時，共識系統會有問題。

有鑑於這些與其他考量而做出本發明。雖然已經討 論較特定的問題，但是應當理解到，本文所揭示的實施例不應限於解決先前技術中所指出的特定問題。

提供此發明內容來以簡化的形式介紹選擇的概念，該等概念進一步在下面的詳細說明部分中敘述。此發明內容並不打算識別所主張的技術內容的關鍵特徵或必要特徵，也不打算用於協助決定所主張的技術內容的範圍。

一種可擴展最終一致性系統的實施例包括辦理物件模型，辦理物件模型允許大型服務的有效率與可擴展最終一致性。在可擴展最終一致性系統內，寫入請求與讀取請求由分開的層處理。日誌以與寫入動作一致的分區方案來服務寫入請求(例如，寫入文件)。儲存庫以與讀取動作一致的分區方案來服務讀取請求(亦即，讀取檢視)。日誌包括至少一文件型分區，用於儲存文件。儲存庫包括至少一檢視型分區，用於儲存文件。

當使用者執行動作時，例如產生、修改或刪除文件，寫入請求會傳送至可擴展最終一致性系統。當接收時，可擴 展最終一致性系統先儲存寫入請求至日誌。在寫入請求已經儲存至日誌之後，視為接受對文件的更改。當接收時，可擴展最終一致性系統的實施例可在至少兩個不同的位置中儲存對於日誌的寫入請求。寫入請求的一個副本可儲存作為運行記錄，運行記錄作用為動作項目，用以標識尚未完全歸併於儲存庫的寫入請求。寫入請求的另一個副本可儲存作為歷史記錄，歷史記錄顯示版本與版本之間對於文件的更改。

更改委託層負責從日誌傳送寫入請求至儲存庫。文件寫入從日誌流動至儲存庫，所以沒有複雜的同步機制。在各種實施例中，當運行記錄產生在日誌中時，可擴展最終一致性系統可先嘗試複製運行記錄至儲存庫。一旦運行記錄已經成功複製，從日誌刪除運行記錄。

一致性恢復層負責更改委託層的循環操作，並且最後提供最終一致性。一致性恢復層不斷促使更改委託層讀取日誌中保持的現存記錄並且複製任何運行記錄至儲存庫。

100‧‧‧可擴展最終一致性系統

102‧‧‧使用者

104a‧‧‧桌上型電腦

104b‧‧‧膝上型電腦

104c‧‧‧平板電腦

104d‧‧‧行動電話

106‧‧‧網路

108‧‧‧前端層

110‧‧‧辦理物件模型

112‧‧‧寫入請求

114‧‧‧讀取請求

116‧‧‧日誌

118‧‧‧儲存庫

120‧‧‧日誌API

122‧‧‧儲存庫API

124‧‧‧文件型分區

126‧‧‧檢視型分區

126e、126f‧‧‧計畫分區

126t‧‧‧使用者分區

126u‧‧‧名稱分區

128‧‧‧運行記錄

128b-c‧‧‧運行記錄

128r‧‧‧運行記錄

130‧‧‧歷史記錄

130a-c‧‧‧歷史記錄

132‧‧‧更改委託層

134‧‧‧一致性恢復層

200‧‧‧排序

202‧‧‧分區金鑰

204‧‧‧列金鑰

206‧‧‧文件資料

208‧‧‧雜湊

210‧‧‧文件識別符

212‧‧‧記錄的版本

214‧‧‧類型識別符

216‧‧‧內容

300‧‧‧最終一致性方法

302‧‧‧文件寫入操作

304‧‧‧金鑰值操作

306‧‧‧歷史操作

308‧‧‧運行操作

310‧‧‧運行記錄處理操作

312‧‧‧複製操作

314‧‧‧複製成功檢查操作

316‧‧‧刪除操作

318‧‧‧歷史清除操作

320‧‧‧排程操作

322‧‧‧重試操作

402‧‧‧步驟

404‧‧‧步驟

406a-n‧‧‧複製本

408‧‧‧步驟

502‧‧‧工作

502o‧‧‧工作

504e、504f、504o‧‧‧計畫

506a、506b‧‧‧使用者

510‧‧‧值欄

512‧‧‧關係欄

514‧‧‧成員關係欄

600‧‧‧運算裝置

602‧‧‧處理單元

604‧‧‧系統記憶體

605‧‧‧作業系統

606‧‧‧程式模組

608‧‧‧虛線

609‧‧‧可移除的儲存裝置

610‧‧‧不可移除的儲存裝置

612‧‧‧輸入裝置

614‧‧‧輸出裝置

616‧‧‧通訊連接

618‧‧‧運算裝置

620‧‧‧應用程式

700‧‧‧行動運算裝置

702‧‧‧系統

705‧‧‧顯示器

710‧‧‧輸入按鈕

715‧‧‧側部輸入元件

720‧‧‧視覺指示器

725‧‧‧音訊變換器

730‧‧‧內建攝影機

735‧‧‧小型鍵盤

760‧‧‧處理器

762‧‧‧記憶體

764‧‧‧作業系統

765‧‧‧應用程式

766‧‧‧應用程式

768‧‧‧非揮發性儲存區域

770‧‧‧電源

772‧‧‧無線電通訊裝置

774‧‧‧音訊介面

776‧‧‧視訊介面

A-M‧‧‧流程

本揭示案的進一步特徵、態樣、與優點將參照以下圖式變得更好理解，其中元件未按尺度繪製，以便更清楚地顯示細節，且其中類似的元件符號在多個視圖中表示類似的元件：第1圖例示在大型服務中實施的可擴展最終一致性系統的一實施例的系統架構；第2圖為例示圖，代表日誌的一個分區之運行與歷史記錄的一實施例； 第3圖為可擴展最終一致性系統所使用的最終一致性方法的一實施例的高階流程圖；第4圖為可擴展最終一致性系統的一實施例的流程圖；第5A圖至第5D圖例示可擴展最終一致性系統內如何處理涉及具有各種關係的文件之各種辦理(亦即，編輯)；第6圖為方塊圖，例示運算裝置的實體元件的一實施例，利用運算裝置可實施本發明的實施例；及第7A圖與第7B圖為行動運算裝置的簡化方塊圖，利用行動運算裝置可實施本發明的實施例。

各種實施例參照所附圖式更完整地敘述於下，所附圖式形成本文的一部分，並且顯示具體的範例性實施例。但是，實施例可用許多不同的形式來實施，並且不應解釋為限於本文所提出的實施例；而是，提供這些實施例，使得本揭示案將為徹底且完整的，並且將充分傳達實施例的範圍給本領域中熟習技藝者。實施例可實施為方法、系統或裝置。因此，實施例可採用硬體實施、完全軟體實施或結合軟體與硬體態樣的實施之形式。下面的詳細敘述因此不應視為限制的意義。

可擴展最終一致性系統的實施例敘述在本文中並且例示在附圖中。可擴展最終一致性系統使用邏輯文件日誌，來提供橫越大型服務中的多個分區之最終一致性。只要沒有文件寫入需要跨越多個文件辦理，該系統透過並行化而允許對於文件的大規模相互關聯圖進行辦理編輯，而不犧牲線性 可擴展性。該系統從複製的儲存分離編輯的授權，以允許有效率的辦理與線性可擴展性。所有文件寫入都寫入至日誌中的文件特定分區，其中該等所有文件寫入係排序，直到更改傳送至儲存庫的檢視型分區。只有當未決的文件寫入已經成功複製至儲存庫，才從日誌移除未決的文件寫入。藉由不斷地檢查日誌並且嘗試複製任何未決的文件寫入至儲存庫，該系統提供最終一致性，而不需要複雜的同步機制，例如共識協定(例如Paxos)。該系統以允許最終影響多於一個文件的文件寫入透過日誌有效率地處理作為對於單一文件的編輯之方式，來模型化文件之間的成員以及包含關係，而不需要訴諸人工分區。

第1圖例示可擴展最終一致性系統的一實施例的系 統架構。可擴展最終一致性系統100可在大型(亦即，大資料)服務中實施，大型服務提供使用者102對於大量資訊的存取與儲存。使用者可經由網路106(例如，但不限於，網際網路、廣域網路、區域網路、與其組合)從各種客戶端裝置104a-d存取大型服務。合適的客戶端裝置的範例包括(但不限於)桌上型電腦104a、膝上型電腦104b、平板電腦104c、行動電話104d、個人數位助理、智慧型手錶、與智慧型家電(例如，智慧型電視)。

可擴展最終一致性系統包括前端層108，前端層108 提供至大型服務的進入點。在各種實施例中，大型服務可提供網頁型使用者介面，客戶端裝置可透過使用者代理器(例如，瀏覽器)存取該網頁型使用者介面。在一些實施例中， 使用者代理器可為專用的客戶端應用程式，提供使用者介面並且處理與大型服務的通訊。

辦理物件模型110允許大型服務的高效率與可擴展 最終一致性。藉由可擴展最終一致性系統所處理的辦理包括(但不限於)：寫入請求與讀取請求、允許使用者讀取、檢視(亦即，顯示)、產生、複製、刪除、操作(亦即，編輯或修改)、共享、協作、或儲存(亦即，寫入)文件、以及由大型服務處理的檢視。用語「文件」廣泛地包括由大型服務處理的任何資料物件。藉由範例的方式，針對辦公室或生產的應用程式型大型服務，文件可包括(但不限於)：文字處理文件、郵件項目、工作項目、行事曆項目、聯繫人項目、簡報、電子資料表或資料庫。用語「檢視」廣泛地包括：基於用於呈現文件給使用者的共同屬性值之文件的索引、分組或分類。藉由範例的方式，檢視可允許工作項目的集合由工作所有者或由與該工作相關的計畫顯示。

在可擴展最終一致性系統內，寫入請求112與讀取 請求114由分開的層處理。日誌116以與寫入動作一致的分區方案來服務寫入請求(例如，寫入文件)。儲存庫118以與讀取動作一致的分區方案來服務讀取請求(亦即，讀取檢視)。在例示的實施例中，日誌與儲存庫係呈現為虛擬化的儲存資源(例如，雲端儲存)，可透過對應的應用程式編程介面(API,application programming interfaces)(日誌API 120與儲存庫API 122)來存取。

日誌包括至少一文件型分區124，用於儲存文件。 每一分區基於分配給單一資源或查詢的最大資料群組來設計大小。當大型服務所處理的資料數量增加時，可線性擴展日誌並且增加新的分區。無論日誌分區的數量為何，可擴展最終一致性系統將與任何給定的文件相關的所有寫入請求儲存在相同的日誌分區中。具有相關於每一文件的單一日誌分區可允許針對每一文件維持辦理編輯排序。

儲存庫包括至少一檢視型分區126，用於儲存文件。 藉由檢視來將儲存庫分區可允許文件在相一時間由多個使用者有效率地存取。若文件相關於多於一個的檢視，每一檢視通常維持文件其自身的副本(亦即，複製本)。在儲存庫內，文件的各種複製本/檢視形成文件的大量相互關聯圖，散佈在多個分區之中。雖然一些文件可獨立於所有其他文件(除了文件的複製本之外)，其他文件可藉由包含關係或成員關係而相互關聯。例如，單一的個人工作可獨立於儲存庫內的其他文件。文件也可相關於儲存庫中的另一文件，例如分配給計畫的工作。計畫可作為多個工作的容件。類似地，文件可相關於儲存庫中影響檢視的其他實體，例如分配至計畫的人員。當利用日誌時，儲存庫可線性擴展並且增加新的分區來處理額外的文件或檢視。

當使用者執行動作時，例如產生、修改或刪除文件， 寫入請求會傳送至可擴展最終一致性系統。當接收時，可擴展最終一致性系統先儲存寫入請求至日誌。在寫入請求已經儲存至日誌之後，視為接受對文件的更改，但是寫入請求所招致的更改通常所有使用者都不可見，直到該等更改已經歸 併至儲存庫中。當日誌包括多個分區時，可擴展最終一致性系統可決定分區識別符，分區識別符指示寫入請求應該寫入的分區。在各種實施例中，分區識別符可基於與寫入請求相關的文件之文件識別符。

可擴展最終一致性系統使用日誌作為保持寫入請求 的臨時區域，直到寫入請求已經歸併至適當的檢視中。當偵測對於文件的衝突編輯時，也可使用日誌。為了實現這些功能，當接收時，可擴展最終一致性系統的實施例可儲存對於日誌的寫入請求至至少兩個位置中。寫入請求的一個副本可儲存作為運行記錄128，運行記錄128作用為動作項目，用以標識尚未完全歸併於儲存庫的寫入請求。無法複製寫入請求至儲存庫可能是日誌與儲存庫之間的通訊通道(例如，網際網路)或分區暫時無法存取(例如，資源失效或停機)的結果。寫入請求的另一個副本可儲存作為歷史記錄130。歷史記錄可用於例如偵測對於文件的衝突編輯或維護稽核紀錄之目的。

更改委託層132負責以並行的方式從日誌傳送寫入 請求至儲存庫。文件寫入從日誌流動至儲存庫，所以沒有複雜的同步機制。換句話說，每一檢視/複製本的更新係獨立於文件寫入所影響的其他檢視/複製本的更新。這接著允許文件寫入與每一更新發生作為單一文件辦理，而不需訴諸人工分區(亦即，將文件圖再分成人工尺度單元或區域)。在各種實施例中，當運行記錄產生在日誌中時，可擴展最終一致性系統可先嘗試複製運行記錄至儲存庫。一旦運行記錄已經成 功複製，從日誌刪除運行記錄。

一致性恢復層134負責更改委託層的循環操作，並 且最後提供最終一致性。一致性恢復層促使更改委託層讀取日誌中保持的現存記錄並且複製任何運行記錄至儲存庫。在各種的實施例中，更改委託層開始於最舊的運行記錄，以用可擴展最終一致性系統接收編輯的順序來對文件辦理編輯。 一致性恢復層可基於各種事件及/或基於週期的基礎(例如，每N分鐘、小時或天)來啟始更改委託層的操作。可用於觸發更改委託層的操作之事件的範例包括(但不限於)：系統啟動、錯誤恢復、與接收寫入請求。

第2圖為例示圖，代表日誌的一個分區之運行與歷 史記錄的一實施例。例示的代表性日誌分區包括用於每一寫入請求的歷史記錄130a-c。文件「doc1」的版本2與文件「doc4」的版本1也具有運行記錄128b-c。運行記錄的存在表示了寫入請求尚未完全複製至儲存庫。文件「doc1」的版本1的運行記錄的不存在表示了所有複製本都已經用版本1的寫入請求進行更新。在日誌的下次檢查時，可擴展最終一致性系統將嘗試傳送文件「doc1」的版本2的寫入請求以及文件「doc4」的版本1的寫入請求至儲存庫。

每一文件型日誌分區124的排序200指的是在可擴 展最終一致性系統中未決的寫入請求。換句話說，排序廣泛地指的是尚未成功複製至儲存庫的運行記錄的集合。日誌與儲存庫的實施例為金鑰值儲存系統。在各種實施例中，相關於運行與歷史記錄的基本資訊包括(但不限於)分區金鑰 202、列金鑰204與文件資料206。針對每一記錄可儲存的額外資訊可包括(但不限於)：作為文件的離線副本的來源之文件的版本(亦即，編輯的產生所針對的版本)、接收寫入請求時的資料、接收寫入請求時的時間、以及提交寫入請求的使用者之使用者識別符。

分區金鑰202標識了文件被分配的分區。在各種實 施例中，分區金鑰為文件識別符210(例如，文件名稱)的雜湊208，這允許更有效率的最終一致性，相較於使用文件識別符作為分區金鑰來說。雜湊允許具有唯一文件識別符範圍的文件藉由將文件識別符一般化，而分組至相同的分區中。例如，在所示的實施例中，「doc1」與「doc4」文件識別符的雜湊為「ABC」，且「doc1」與「doc4」的運行與歷史記錄係分配至相同的日誌，該相同的日誌對應於雜湊「ABC」。

列金鑰204為日誌內的唯一記錄識別符。在各種實施例中，列金鑰為附加有記錄的版本212之文件識別符210。列金鑰可用類型識別符214修改，以區別歷史記錄與運行記錄。例如，列金鑰可前綴有字元(例如「H」)，以指出該記錄為歷史記錄，或者可前綴有字元「R」，以指出該記錄為運行記錄。

文件資料206包括被寫入之文件的內容216。在一些實施例中，內容可僅包括更改，而非文件的完整副本。

第3圖為可擴展最終一致性系統所使用的最終一致性方法的一實施例的高階流程圖。最終一致性方法300開始於文件寫入操作302，其中接收寫入請求。金鑰值操作304 計算寫入請求的金鑰值。金鑰值可包括分區金鑰與列金鑰，如同相關於第2圖所述的。分區金鑰標識文件被分配的分區。 列金鑰為唯一的記錄識別符。在各種實施例中，列金鑰為附加有記錄的版本之文件識別符。

歷史操作306使用金鑰值將寫入請求儲存為日誌中 的歷史記錄。更具體地，寫入請求係寫入至分區金鑰所標識之分區的日誌。使用利用歷史記錄指示符所修改的列金鑰，唯一地標識歷史記錄。例如，歷史記錄的列金鑰可前綴有字元(例如「H」)，以指出該記錄為歷史記錄。

運行操作308使用金鑰值來儲存寫入請求的副本作 為日誌中的運行記錄。更具體地，寫入請求係寫入至分區金鑰所標識之分區的日誌。使用利用運行記錄指示符所修改的列金鑰，唯一地標識運行記錄。例如，運行記錄的列金鑰可前綴有字元(例如「R」)，以指出該記錄為運行記錄。

運行記錄處理操作310複製寫入記錄(亦即，運行 記錄中的編輯)至儲存庫。藉由運行記錄指示符，可區分運行記錄於其他記錄。運行記錄處理操作的各種實施例在運行記錄產生時作用於每一運行記錄。若未處理的運行記錄(亦即，未決的寫入請求)存在，複製操作312複製寫入請求至文件儲存庫。

複製成功檢查操作314驗證寫入請求已經成功複製 至儲存庫中的適當分區。在一些實施例中，藉由從儲存庫接收成功或失敗的回應，可指出成功或失敗。在其他實施例中，藉由比較儲存庫中的分區的內容與寫入請求的內容，可判定 成功。該比較可實施為元資料比較(例如，驗證每一複製本的版本號碼係相同於正在處理的寫入請求)或內容比較(例如，雜湊或逐個位元組比較)。

當複製操作成功完成時，刪除操作316從日誌刪除 運行記錄。刪除運行記錄為文件編輯已經成功併入儲存庫中的信號。雖然刪除了運行記錄，保留歷史記錄來用於識別衝突的編輯以及協助解決衝突。在各種實施例中，歷史記錄可無限期地保留在日誌中。

在選擇性的歷史清除操作318中，歷史記錄可有條 件地清除，以減小日誌的大小。在一些實施例中，針對每一文件，僅選定數量的歷史記錄(例如，最近五個)可保留。 或者，在指定的時間期間(例如，兩週或三個月)之後，可刪除歷史記錄。在一些實施例中，歷史記錄的保留可連結於與文件相關的活動。換句話說，可基於文件的特性，例如(但不限於)最近或經常編輯的文件，保留更多的歷史記錄。

若複製成功檢查操作判定複製失敗，則複製成功檢 查操作可用於啟始排程操作320，當選定的標準發生時，排程操作320使複製操作重試。成功或失敗可以用多種方式來判定。例如，藉由(但不限於)與儲存庫API建立連接的性能或者藉由接收從儲存庫API發送的成功/失敗回應，可指出成功或失敗。在各種實施例中，排程操作可配置成排程地(例如，每天、每小時等)、在經過一段時間之後(例如，失敗之後60分鐘)、或者在一事件之後(例如，接受新的寫入請求)，使複製操作重試，但非限制。

重試操作322讀取日誌文件分區且將日誌中存在的 任何未處理的運行記錄收集至排序中。運行記錄處理操作310重複於排序中的每一運行記錄。在各種的實施例中，重試操作從最舊的記錄至最新的記錄處理日誌。這確保文件編輯以被接收的順序進行處理，如此促進衝突編輯的檢查以及可能仰賴於依順序接收的寫入請求的其他功能。

第4圖為可擴展最終一致性系統的一實施例的流程 圖。流程開始於流程A，其中使用者編輯文件402。文件可為使用者所建立的新文件或已經從大型服務(亦即，離線副本)讀取的現有的文件。當使用者儲存對文件的更改，則流程在B處繼續，其中產生寫入請求112。寫入請求可包括更改的文件與額外資訊，例如(但不限於)提交寫入請求的使用者的使用者識別符、寫入請求提交的日期、寫入請求提交的時間、以及作為離線副本的來源之文件的版本(亦即，離線副本的基線版本)。在流程C，決定對應於更改的文件的文件識別符之分區金鑰。在流程D，將運行記錄加入至更改的文件的適當日誌。在流程E，歷史記錄可加入至更改的文件的適當日誌。在流程F，當儲存使用者記錄時，一致的每位使用者檢視系統發送通知404至使用者。該通知對使用者指出文件的更改已經接收並接受。

在各種實施例，在流程G，新加入的運行記錄係發 送至更改委託層，以複製至儲存庫。在流程H，更改委託層發送運行記錄至儲存庫API，其中運行記錄傳送至用於對應的檢視之適當的儲存庫分區。在流程I，基於運行記錄中的更 改，更新用於各種檢視之儲存庫分區中的複製本406a-n。流程在流程J繼續，其中將成功或失敗回報給日誌API。成功/失敗指示408可產生在儲存庫API處，並且由儲存庫API直接或者透過更改委託層間接報告給日誌API。在其他實施例中，成功/失敗指示408可由更改委託層決定，並且直接報告給日誌API。若運行記錄的複製成功，流程在K處繼續，其中將成功複製的運行記錄128r刪除。

流程在L處繼續，其中一致性恢復層從日誌讀取運 行記錄，並且形成排序200。在流程M，排序的運行記錄係發送至更改委託層，以用運行記錄被接收的順序進行處理。針對排序中的每一運行記錄，流程從流程H繼續，且一直持續直到排序中的所有運行記錄都已經處理。

第5A圖至第5D圖例示可擴展最終一致性系統內如何處理涉及具有各種關係的文件之各種辦理(亦即，編輯)。可擴展最終一致性系統模型化成員(例如，多個計畫中的使用者)以及包含關係(例如，為計畫的部分之工作)，並且允許在那些邊界之間移動文件，而不須將文件圖(亦即，資料集)細分成人工尺度單元或區域。

第5A圖例示日誌與儲存庫的初始狀態。為了討論的目的，所涉及的文件包括複製的工作502、兩個計畫504e、504f以及兩個使用者506a、506b。日誌116繪示為具有單一個分區124(假設所有涉及的文件的分區金鑰(例如，雜湊)映射至相同的分區)；但是，如同先前所述，一或更多個文件可插入至不同的日誌分區，而不會對操作有任何明顯的影 響。儲存庫118係分區成各種檢視分區，包括個別的計畫分區126e、126f、由分配的使用者分區126t所索引的工作、以及由名稱分區126u所索引的使用者，以用於有效率的文件檢索。例如，不同的容件(例如，計畫)可在儲存庫中設置有各別的檢視分區，以允許代表工作的各種文件、資源(例如，使用者)、以及相關於特定計畫的其他目標可在單一辦理中檢索。文件可包括各種獨立簡單的值欄510，例如標題或名稱。

一些文件也可包括包含關係欄512(例如，計畫識 別符)，包含關係欄512將工作連結至另一文件(例如，計畫)。計畫識別符可作為工作所屬的計畫(亦即，容件)之指標，藉此界定了包含關係。通常，包含關係限制為一對一(例如，屬於計畫的工作)或一對無(例如，該工作不屬於計畫)的關係。為了說明的目的，計畫係顯示為具有反映文件識別符的計畫識別符，以提供共同的欄來用於索引。

一些文件可包括成員關係欄514，例如分配至計畫 的人員(亦即，來自群組方面的成員)或與使用者相關的計畫(亦即，來自成員方面的成員)。通常，除了一對一與一對無的關係之外，成員關係允許一對多(例如，計畫可具有多個分配的人員或使用者可具有多個角色)。

第5B圖繪示可擴展最終一致性系統內的獨立欄被 更改的處理。此時，工作於工作502o的離線副本之使用者102提交寫入請求(亦即，編輯)112，將標題欄510的值從「Fix A/C」更改為「Fix HVAC」。該編輯儲存於與工作相關的日誌分區中(亦即，基於金鑰值)。標題更改最終從日誌傳送 至儲存庫的各種分區中的工作的每一複製本502，如同本文所述。此種辦理從日誌的角度來看可以容易識別為單一文件辦理。因為更改局限於單一文件，該辦理無需跨越日誌中的多個分區。

第5C圖繪示可擴展最終一致性系統內的包含關係 欄的更改的處理。在此實例中，工作於工作502o的離線副本之使用者102提交寫入請求112，藉由將計畫識別符欄512的值從「Echo」更改成「Foxtrot」而移動工作至不同的計畫。 同樣地，該編輯儲存於與該工作相關的日誌分區中。雖然該編輯涉及到包含關係，僅工作(亦即，所包含的文件)必須更改。該編輯最終傳送至每一檢視/複製本，這可能涉及：從一或更多個分區移除複製本、加入工作至一或更多個分區、以及修改一或更多個分區中的工作。此時，複製本從Project E(例如，指定給Project E的檢視分區)移除，且增加複製本至Project F(例如，指定給Project F的檢視分區)。此外，更新受指派人所索引的工作之檢視分區中的複製本。但是，無需更改計畫(亦即，容件)。因此，從日誌的角度來看，該辦理為單一文件辦理，因為更改僅需要針對單一文件被記錄。換句話說，更改僅需要寫入至單一日誌分區。

第5D圖繪示可擴展最終一致性系統內的成員關係 欄的更改的處理。在此實例中，工作於Project F 504o的離線副本之使用者102提交寫入請求112，藉由加入「Alice」至人員欄514而加入成員至與該計畫相關的使用者群組。該編輯儲存於與該計畫相關的日誌分區中。雖然更改最終會傳送 至成員更改所影響之儲存庫中的其他文件，從日誌的角度來看，對於成員關係欄的成員的更新僅是對於該計畫的編輯。 因此，即使最終結果會是更新多個文件(例如，會更新使用者A的成員欄)，該寫入請求係有效率地處理作為單一文件辦理。

本申請案的技術特徵可實施在多種實施例中作為系 統、裝置、與其他製造物品或作為方法。實施例可實施為硬體、軟體、電腦可讀取媒介、或其組合。本文所述的實施例與功能可經由多種運算系統來操作，包括(但不限於)桌上型電腦系統、有線與無線運算系統、行動運算系統(例如，行動電話、上網本、平板或板型電腦、筆記型電腦、與膝上型電腦)、手持裝置、多處理器系統、基於微處理器的或可編程的消費電子產品、小型電腦、與大型電腦。

使用者介面與各種類型的資訊可經由內建的運算裝 置顯示器或經由與一或更多個運算裝置相關的遠端顯示單元來進行顯示。例如，使用者介面與各種類型的資訊可顯示與互動於牆面，牆面上投影有使用者介面與各種類型的資訊。 與其中可實施本發明的實施例之多種運算系統的互動包括：按鍵輸入、觸控螢幕輸入、語音或其他音訊輸入、手勢輸入，其中相關的運算裝置配備有偵測(例如，攝影機)功能，用於擷取與解釋用於控制運算裝置的功能之使用者手勢與類似者。

第6圖至第7B圖與相關的敘述提供了可實施本發明 的實施例之多種操作環境的討論。但是，所例示與討論的裝 置與系統係針對範例與例示的目的，且並非用於限制可用於實施上述的本發明的實施例之多種運算裝置的配置。

第6圖為方塊圖，例示運算裝置600的實體元件(亦 即，硬體)，利用運算裝置600可實施本發明的實施例。下面所述的運算裝置元件可適於實施運算裝置，包括(但不限於)個人電腦、平板電腦、表面型電腦、與智慧型手機、或本文中討論的任何其他運算裝置。在基本的配置中，運算裝置600可包括至少一處理單元602與系統記憶體604。取決於運算裝置的種類與配置，系統記憶體604可包括(但不限於)揮發性儲存器(例如，隨機存取記憶體)、非揮發性儲存器(例如，唯讀記憶體)、快閃記憶體、或此種記憶體的任何組合。系統記憶體604可包括作業系統605與一或更多個程式模組606，程式模組606適於運行軟體應用程式620，例如可擴展最終一致性系統100的元件。例如，作業系統605可適於控制運算裝置600的操作。另外，本發明的實施例可聯合圖形庫、其他作業系統、或任何其他應用程式來實施，且不限於任何特定的應用程式或系統。此基本配置係藉由虛線608內的那些元件而例示。運算裝置600可具有額外的特徵或功能。例如，運算裝置600也可包括額外的資料儲存裝置(可移除的及/或不可移除的)，像是例如磁碟、光碟、或匣帶。 此種額外的儲存器係藉由可移除的儲存裝置609與不可移除的儲存裝置610而例示。

如同上述，多種程式模組與資料檔案可儲存在系統記憶體604中。雖然在處理單元602上執行，軟體應用程式 620可執行的處理包括(但不限於)最終一致性方法300的一或更多個階段。可根據本發明的實施例來使用的其他程式模組可包括電子郵件與聯繫的應用程式、文字處理應用程式、電子資料表應用程式、資料庫應用程式、幻燈片簡報應用程式、拉曳的應用程式等。

另外，本發明的實施例可實施在電子電路中，電子 電路包括離散式電子元件、已封裝或整合的電子晶片(包含邏輯閘)、使用微處理器的電路、或包含電子元件或微處理器的單晶片上。例如，本發明的實施例可經由系統上晶片(SOC,system-on-a-chip)來實施，其中每一或許多例示的元件可整合於單一積體電路上。此種SOC裝置可包括一或更多個處理單元、圖形單元、通訊單元、系統視覺化單元與各種應用程式功能，所有這些功能都整合(或「燒錄」)於晶片基板上，作為單一積體電路。當經由SOC來操作時，本文相關於軟體應用程式620所述的功能可經由與單一積體電路(晶片)上的運算裝置600的其他元件整合的特殊應用邏輯來操作。本發明的實施例也可使用可以執行邏輯操作(像是例如，AND、OR、與NOT)的其他技術來實施，包括(但不限於)機械的、光學的、流體的、與量子的技術。另外，本發明的實施例可實施在通用目的電腦內或在任何其他電路或系統中。

運算裝置600也可具有一或更多個輸入裝置612，例如鍵盤、滑鼠、電筆、聲控輸入裝置、觸控輸入裝置等。也可包括輸出裝置614，例如顯示器、揚聲器、印表機等。前述裝置為範例，且可使用其他裝置。運算裝置600可包括一 或更多個通訊連接616，允許與其他運算裝置618的通訊。合適的通訊連接616的範例包括(但不限於)RF傳輸器、接收器、及/或收發器電路；通用序列匯流排(USB)、並列、及/或序列埠。

本文所用的用語「電腦可讀取媒介」可包括電腦儲 存媒介。電腦儲存媒介可包括以任何方法或技術所實施的揮發性與非揮發性、可移除的與不可移除的媒介，用於儲存資訊，例如電腦可讀取指令、資料結構、或程式模組。系統記憶體604、可移除的儲存裝置609與不可移除的儲存裝置610都是電腦儲存媒介的範例(亦即，記憶體儲存器)。電腦儲存媒介可包括隨機存取記憶體(RAM)、唯讀記憶體(ROM)、電性可抹除唯讀記憶體(EEPROM)、快閃記憶體或其他記憶體技術、光碟唯讀記憶體(CD-ROM)、數位萬用碟(DVD)或其他光學儲存器、磁卡帶、磁帶、磁碟儲存器或其他磁性儲存裝置、或可用於儲存資訊且可由運算裝置600存取的任何其他製造物品。任何此種電腦儲存媒介可為運算裝置600的部分。

第7A圖與第7B圖例示了行動運算裝置700，利用 行動運算裝置700可實施本發明的實施例。合適的行動運算裝置的範例包括(但不限於)行動電話、智慧型手機、平板電腦、表面型電腦、與膝上型電腦。在基本的配置中，行動運算裝置700係手持電腦，具有輸入元件與輸出元件兩者。 行動運算裝置700通常包括顯示器705與一或更多個輸入按鈕710係允許使用者輸入資訊至行動運算裝置700中。行動 運算裝置700的顯示器705也可作用為輸入裝置(例如，觸控螢幕顯示器)。若包括的話，選擇性的側部輸入元件715允許另外的使用者輸入。側部輸入元件715可為旋轉開關、按鈕、或任何其他種的手動輸入元件。在替代的實施例中，行動運算裝置700可併入較多或較少的輸入元件。例如，在一些實施例中，顯示器705可能不是觸控螢幕。在又另一替代的實施例中，行動運算裝置700係可攜式電話系統，例如手機。行動運算裝置700也可包括選擇性的小型鍵盤735。選擇性的小型鍵盤735可為實體的小型鍵盤或產生在觸控螢幕顯示器上的「軟性」小型鍵盤。在各種實施例中，輸出元件包括顯示器705(用於顯示圖形使用者介面)、視覺指示器720(例如，發光二極體)、及/或音訊變換器725(例如，揚聲器)。在一些實施例中，行動運算裝置700包括振動變換器，用於提供使用者觸覺回饋。在又另一實施例中，行動運算裝置700包括輸入及/或輸出埠，例如音訊輸入(例如，麥克風插座)、音訊輸出(例如，頭戴式耳機插座)、與視訊輸出(例如，HDMI埠)，用於傳送信號至外部裝置或從外部裝置接收信號。

第7B圖為方塊圖，例示行動運算裝置的一實施例的 架構。亦即，行動運算裝置700可包括系統(亦即，架構)702來實行一些實施例。在一實施例中，系統702係實施為智慧型手機，可以運行一或更多個應用程式(例如，瀏覽器、電子郵件客戶端、備忘錄、聯繫管理器、傳訊客戶端、遊戲、與媒體客戶端/播放器)。在一些實施例中，系統702係整合 為運算裝置，例如整合的個人數位助理(PDA)與無線電話。

一或更多個應用程式765可載入記憶體762中並且 運行於作業系統764上或相關於作業系統764來運行。應用程式的範例包括電話撥打程式、電子郵件程式、個人資訊管理(PIM,personal information management)程式、文字處理程式、電子資料表程式、網際網路瀏覽器程式、傳訊程式等。 系統702也包括在記憶體762內的非揮發性儲存區域768。非揮發性儲存區域768可用於儲存永久資訊，永久資訊在系統702不被供電時不應遺失。應用程式765可使用與儲存非揮發性儲存區域768中的資訊，例如電子郵件或電子郵件應用程式所用的其他訊息，以及類似者。同步應用程式(未圖示)也位於系統702上並且被編程來與位於主機電腦上的對應的同步應用程式互動，以使非揮發性儲存區域768中儲存的資訊同步於主機電腦處儲存的對應資訊。應瞭解到，其他應用程式可載入記憶體762中並且運行於行動運算裝置700上，包括本文所述的軟體應用程式620。

系統702具有電源770，電源770可實施為一或更 多個電池。電源770可另外包括外部電源，例如AC轉接器或者補充或充電該等電池的供電對接裝置(powered docking cradle)。

系統702也可包括無線電通訊裝置772，無線電通 訊裝置772執行傳送與接收射頻通訊的功能。無線電通訊裝置772經由通訊載體或服務供應商而促成系統702與外部世界之間的無線連接。傳輸至與自無線電通訊裝置772係在作 業系統764的控制之下實行。換句話說，無線電通訊裝置772所接收的通訊可經由作業系統764而傳送至應用程式765，且反之亦然。

視覺指示器720可用於提供視覺通知，及/或音訊介 面774可用於經由音訊變換器725而產生音訊通知。在所示的實施例中，視覺指示器720係發光二極體(LED)，且音訊變換器725係揚聲器。這些裝置可直接耦接於電源770，使得當已經啟用時，即使處理器760與其他元件可能為了節省電池電力而關掉，這些裝置仍由通知機制所要求的維持開啟一段時間。LED可被編程為維持閃爍，直到使用者採取行動指出裝置的電源打開狀態。音訊介面774用於提供音訊信號至使用者並且從使用者接收音訊信號。例如，除了耦接於音訊變換器725之外，音訊介面774也可耦接於麥克風，以接收音訊輸入，例如促成電話交談。根據本發明的實施例，麥克風也可作為音訊感測器，以促成通知的控制，如同下面將敘述的。系統702可另外包括視訊介面776，視訊介面776促成內建攝影機730的操作，以記錄靜止的影像、視訊流、與類似者。

實施系統702的行動運算裝置700可具有額外的特 徵或功能。例如，行動運算裝置700也可包括額外的資料儲存裝置(可移除的及/或不可移除的)，例如磁碟、光碟、或匣帶。此種額外的儲存器係藉由非揮發性儲存區域768而例示。

行動運算裝置700所擷取或產生且經由系統702所 儲存的資料/資訊可本地地儲存在行動運算裝置700上(如同上述)，或者該資料可儲存在任何數量的儲存媒介上，該等儲存媒介可由該裝置經由無線電通訊裝置772來存取，或者經由行動運算裝置700與相關於行動運算裝置700的分離的運算裝置(例如，分佈式運算網路(例如網際網路)中的伺服器電腦)之間的有線連接來存取。應瞭解到，此種資料/資訊可經由行動運算裝置700透過無線電通訊裝置772或透過分佈式運算網路來存取。相似地，根據熟知的資料/資訊轉移與儲存機制，此種資料/資訊可隨時轉移於多個運算裝置之間，以用於儲存與使用，包括電子郵件與合作的資料/資訊共享系統。

本申請案中提供的一或更多個實施例的例示與敘述 係打算提供技術特徵的全部範圍之完整徹底且完全的揭示給本領域中熟習技藝者，且不打算以任何方式限制或限定所主張之本發明的範圍。本申請案中提供的該等實施例、範例與細節係視為足夠傳達財產權，且促成本領域中熟習技藝者可以實施所主張之發明的最佳模式。本領域中熟習技藝者視為熟知的結構、資源、操作與作動之敘述係簡短或省略，以避免模糊本申請案的技術特徵的鮮為人知的或獨特的態樣。所主張之發明不該解釋為受限於本申請案中提供的任何實施例、範例或細節，除非在本文中明確指出。不管是否結合或分開地敘述與繪示，各種特徵(結構性與方法性兩者)係打算為選擇性地被包括或省略，以產生具有特定特徵組的實施例。此外，繪示或敘述的任何或全部功能與作動可以以任何 順序或同時執行。已經提供本申請案的例示與敘述，本領域中熟習技藝者可設想到多個變化、修改、與替代實施例，這些實施例落在本申請案中實施的一般發明性概念的較廣態樣的精神內，並不背離所主張之發明的較廣範圍。

100‧‧‧可擴展最終一致性系統

102‧‧‧使用者

104a‧‧‧桌上型電腦

104b‧‧‧膝上型電腦

104c‧‧‧平板電腦

104d‧‧‧行動電話

106‧‧‧網路

108‧‧‧前端層

110‧‧‧辦理物件模型

112‧‧‧寫入請求

114‧‧‧讀取請求

116‧‧‧日誌

118‧‧‧儲存庫

120‧‧‧日誌API

122‧‧‧儲存庫API

124‧‧‧文件型分區

126‧‧‧檢視型分區

128‧‧‧運行記錄

130‧‧‧歷史記錄

132‧‧‧更改委託層

134‧‧‧一致性恢復層

Claims (20)

1. 一種方法，用於在使文件可由多個使用者存取的一服務中提供可擴展最終一致性，該方法包括下述動作：接收寫入請求，每一寫入請求包括一文件識別符與文件資料；在服務寫入請求的一第一儲存系統的一選取分區中產生每一寫入請求的一運行記錄；嘗試複製該運行記錄至服務讀取請求的一第二儲存系統；及當該運行記錄已經成功複製至該第二儲存系統時，從該第一儲存系統刪除該運行記錄；當該第一儲存系統的該選取分區包含運行記錄時，重複該等下述動作：嘗試複製該等運行記錄至服務讀取請求的一第二儲存系統，並且刪除已經成功複製至該第二儲存系統的該等運行記錄。
2. 如請求項1所述之方法，其中該選取分區係基於該文件識別符。
3. 如請求項1所述之方法，其中該第二儲存系統係藉由服務讀取請求所需要的檢視進行分區。
4. 如請求項1所述之方法，進一步包括下述動作：在該第一儲存系統的該選取分區中產生每一寫入請求的一歷史記 錄。
5. 如請求項1所述之方法，進一步包括下述動作：基於該相關的文件識別符，分配一分區金鑰給每一寫入請求，每一分區金鑰對應於該第一儲存系統中的一分區。
6. 如請求項5所述之方法，進一步包括下述動作：基於該相關的文件識別符的一雜湊，計算該寫入請求的該分區金鑰。
7. 如請求項1所述之方法，進一步包括下述動作：分配一唯一識別符給該寫入請求。
8. 如請求項7所述之方法，其中該唯一識別符為該文件識別符結合於一文件版本識別符。
9. 如請求項1所述之方法，進一步包括下述動作：讀取該第一儲存系統的該選取分區，以定位尚未複製至該第二儲存系統的運行記錄。
10. 一種系統，用於在使文件可由多個使用者存取的一服務中提供可擴展最終一致性，該系統包括：一第一儲存系統，用於儲存來自與對文件的更改相關的寫入請求之文件記錄；一第二個儲存系統，用於儲存用以服務讀取請求的文件 記錄；一運算裝置，該運算裝置具有一處理器與一記憶體，該運算裝置可操作來：接收一寫入請求；在一第一儲存系統的一選取分區中產生寫入請求的運行記錄；複製運行記錄至該第二儲存系統；刪除已經從該第一儲存系統成功複製的運行記錄。
11. 如請求項10所述之系統，其中該第一儲存系統係藉由文件來分區。
12. 如請求項11所述之系統，其中該選取分區係基於與該寫入請求相關的該文件。
13. 如請求項12所述之系統，其中該選取分區係基於用於與該寫入請求相關的該文件之該文件識別符的一雜湊。
14. 如請求項10所述之系統，其中該第二儲存系統係藉由服務讀取請求所需要的檢視進行分區。。
15. 如請求項10所述之系統，其中該運算裝置進一步可操作來：連續讀取該第一儲存系統的分區，以定位運行記錄，並且複製所定位的運行記錄至該第二儲存系統。
16. 如請求項15所述之系統，其中該第一儲存系統的分區係以一周期的基礎進行讀取。
17. 如請求項10所述之系統，其中該運算裝置進一步可操作來：在該第一儲存系統的該選取分區中產生寫入請求的一歷史記錄。
18. 如請求項10所述之系統，其中該運算裝置進一步可操作來：分配一唯一識別符給寫入請求。
19. 如請求項10所述之系統，其中該唯一識別符包括結合於一文件版本識別符與一記錄類型指示符的一文件識別符，該記錄類型指示符區分運行記錄與歷史記錄。
20. 一種電腦可讀取媒介，該電腦可讀取媒介包含電腦可執行指令，當由一電腦執行該等電腦可執行指令時，該等電腦可執行指令執行一方法，該方法用於在使文件可由多個使用者存取的一大型服務中提供可擴展最終一致性，該方法包括下述動作：接收寫入請求，每一寫入請求包括一文件識別符與文件資料；基於該文件識別符的一雜湊，計算每一寫入請求的一分區金鑰，每一分區金鑰對應於服務寫入請求的一第一儲存系 統中的一分區；將每一寫入請求的一運行記錄與歷史記錄加入至對應於該寫入請求的該分區金鑰之該第一儲存系統中的該分區；嘗試複製該運行記錄至一第二儲存系統，該第二儲存系統服務讀取請求並且係藉由服務讀取請求所需要的檢視進行分區；從該第一儲存系統中的該分區刪除已經成功複製至該第二儲存系統的每一運行記錄；及當讀取該第一儲存系統中的該記錄列表時，針對該記錄列表中找到的每一運行記錄，重複該等下述動作：嘗試複製該運行記錄至一第二儲存系統，並且刪除已經成功地複製至該第二儲存系統的每一運行記錄。