Megastore：为交互式服务提供可扩展的高可用性存储
目錄
? ? ? ? 1?簡介
? ? ? ??2 以可用性和規模為目標
? ? ? ??3?A TOUR OF?Megastore
? ? ? ??4?復制
? ? ? ??5?經驗
? ? ? ??6?相關工作
? ? ? ??7?結論
Megastore：為交互式服務提供可擴展的高可用性存儲
摘要：Megastore 是為滿足當今交互式在線服務的要求而開發的存儲系統。Megastore 以一種新穎的方式將?NoSQL?數據存儲的可擴展性與傳統關系數據庫管理系統的便利性相結合，并提供了強大的一致性保證和高可用性。我們在數據的細粒度分區（fine-grained partitions of data）中提供完全可序列化的ACID語義。這種分區允許我們以合理的延遲在廣域網上同步復制每個寫操作，并支持數據中心之間的無縫故障轉移。本文描述了?Megastore 的語義和復制算法。它還描述了我們支持使用?Megastore 構建的各種谷歌生產服務的經驗。
關鍵詞：大型數據庫，分布式事務，BigTable，Paxos
?
1?簡介
隨著桌面應用程序向云遷移，交互式在線服務正迫使存儲社區滿足新的需求。電子郵件、協作文檔和社交網絡等服務一直呈指數級增長，并在測試現有基礎架構的局限性。由于許多相互沖突的需求，滿足這些服務的存儲需求具有挑戰性。
首先，互聯網帶來了大量的潛在用戶，因此應用程序必須具有高度的可擴展性。服務可以使用?MySQL?作為其數據存儲庫快速構建，但要將服務擴展到數百萬用戶，需要對其存儲基礎架構進行徹底的重新設計。第二，服務必須爭奪用戶。這需要快速開發功能和快速上市。第三，服務必須有響應性；因此，存儲系統必須具有低延遲。第四，服務應該為用戶提供一致的數據視圖——更新的結果應該是立即可見且持久的。看到云托管的電子表格編輯消失，無論多么短暫，都是糟糕的用戶體驗。最后，用戶已經開始期望互聯網服務全天候運行，因此服務必須高度可用。該服務必須能夠應對多種故障，從單個磁盤、機器或路由器的故障一直到影響整個數據中心的大規模停機。
這些要求是沖突的。關系數據庫為輕松構建應用程序提供了一套豐富的功能，但它們很難擴展到數億用戶。NoSQL?的數據存儲庫，如谷歌的?Bigtable 、Apache Hadoop?的?HbBase?或?Facebook?的?Cassandra?具有高度可擴展性，但它們有限的?API?和松散的一致性模型使應用程序開發變得復雜。在提供低延遲的同時跨遠程數據中心復制數據是一項挑戰，因為保證復制數據的一致視圖也是一項挑戰，尤其是在故障期間。
Megastore 是為滿足當今交互式在線服務的存儲要求而開發的存儲系統。它的新穎之處在于它將?NoSQL?數據存儲的可擴展性與傳統關系數據庫管理系統的便利性結合在一起。它使用同步復制來實現高可用性和一致的數據視圖。簡而言之，它在遠程副本上提供了完全可序列化的ACID語義，具有足夠低的延遲來支持交互式應用程序。
我們通過在關系數據庫管理系統和?NoSQL?的設計采取折中的辦法實現這一點：我們對數據存儲區進行分區，并分別復制每個分區，在分區內提供完整的ACID語義，但在它們之間只有有限的一致性保證。我們提供了傳統的數據庫功能，例如輔助索引，但是只有那些能夠在用戶可容忍的延遲限制內擴展的功能，并且只有我們的分區方案能夠支持的語義。我們認為，大多數互聯網服務的數據可以進行適當的分區（例如，按用戶），以使這種方法可行，并且一組小而不簡單的功能可以大大減輕開發云應用程序的負擔。
與傳統觀點相反，我們能夠使用 Paxos 構建一個高可用性的系統，該系統在跨地理分布的數據中心同步復制寫操作的同時，為交互式應用程序提供合理的延遲。雖然許多系統只將 Paxos 用于鎖定、選主、復制元數據和配置，但我們認為，Megastore 是部署的最大的系統，它在每次寫入時都使用 Paxos 跨數據中心復制主用戶數據。
Megastore 已經在谷歌內部廣泛部署了幾年。它每天處理?30?多億次寫入和?200?億次讀取事務，并在許多全球數據中心存儲近?1PB 的主要的數據。本文的主要貢獻是：
(1) 數據模型和存儲系統的設計，允許交互式應用程序的快速開發，從一開始就內置高可用性和可擴展性；
(2) Paxos復制和一致性算法的實現，針對地理上分布的數據中心的低延遲操作進行了優化，為系統提供了高可用性；
(3) 一份關于我們在谷歌大規模部署?Megastore 的經驗的報告。
論文組織如下。第?2?節描述了?Megastore 如何使用分區提供可用性和可擴展性，并證明了我們的設計對于許多交互式互聯網應用程序的充分性。第?3?節概述了?Megastore 的數據模型和功能。第?4?節詳細解釋了復制算法，并給出了一些關于它們在實踐中如何執行的度量。第?5?節總結了我們開發該系統的經驗。我們在第?6?節回顧相關工作。第七節總結。
?
?
2 以可用性和規模為目標
與我們對全球、可靠且任意大規模的存儲平臺的需求形成對比的是，我們的硬件構建模塊受到地理位置的限制，容易出現故障，并且容量有限。我們必須將這些組件綁定到一個統一的整體中，以提供更大的吞吐量和可靠性。為此，我們采取了雙管齊下的方法：
(1) 為了可用性，我們實現了一個同步、容錯的日志復制器，該復制器針對長距離鏈路進行了優化；
(2) 為了擴大規模，我們將數據劃分到一個巨大的小型數據庫空間中，每個數據庫都有自己的復制日志，存儲在每個副本的?NoSQL?數據存儲區中。
?
2.1?復制
在單個數據中心內跨主機復制數據通過克服特定的主機的故障提高了可用性，但回報不斷減少。我們仍然必須面對將它們與外部世界連接起來的網絡，以及為它們供電、散熱和提供住所的基礎設施。經濟建設的站點面臨一定程度的設施范圍內的停機風險，并且容易受到區域性災難的影響。為了讓云存儲滿足可用性需求，服務提供商必須在廣闊的地理區域內復制數據。
?
2.1.1?戰略
我們評估了廣域復制（wide-area replication）的常見策略：
異步主/從（Asynchronous Master/Slave）
主節點將預寫日志條目（write-ahead log entries）復制到至少一個從節點。日志追加在主機上得到確認，同時傳輸到從機。主服務器可以支持快速?ACID?事務，但在故障轉移到從服務器期間有停機或數據丟失的風險。調解主導權需要一個共識協議。
同步主/從（Synchronous Master/Slave）
主機在確認更改之前會等待將其鏡像到從機，這樣就可以在不丟失數據的情況下進行故障轉移。主設備和從設備故障需要外部系統及時檢測。
樂觀復制（Optimistic Replication）
同一個復制組的任何成員的突變（mutations，指數據的變化）是可以接受的，改變的數據通過組內異步傳播。可用性和延遲非常好（Any member of a homogeneous?replica group can accept mutations, which are?asynchronously propagated through the group）。然而，全局變異排序在提交時是未知的，因此事務是不可能的。
我們避免了可能丟失故障數據的策略，這在大規模系統中很常見。我們還放棄了不允許?ACID事務的策略。盡管最終一致性的系統具有操作上的優勢，但在快速的應用程序開發中，放棄讀-修改-寫習慣用法是非常困難的。
我們也拋棄了重量級?master?的選項。故障轉移需要一系列高延遲階段，通常會導致用戶可見的中斷，并且仍然存在巨大的復雜性。如果我們可以完全避免?master，為什么要建立一個容錯系統來選主（arbitrate mastership）和故障轉移工作流？
?
2.1.2?Enter Paxos
我們決定使用?Paxos，這是一種經過驗證的最佳容錯一致性算法，不需要杰出的?master。我們在一組對稱的對等體上復制預寫日志。任何節點都可以啟動讀取和寫入。每個日志都在大多數副本的確認中添加塊，少數副本盡可能趕上來——該算法固有的容錯性消除了對可區分的"失敗"狀態的需要。第?4.4.1?節詳細介紹了?Paxos?的一個新擴展，它允許在任何最新的副本上進行本地讀取。另一個擴展允許單路往返寫入（single-roundtrip writes）。
即使?Paxos?具有容錯能力，使用單個日志也有局限性。由于副本分布在很廣的區域，通信延遲限制了整體吞吐量。此外，當沒有當前副本或大多數副本未能確認寫入時，進度會受到阻礙。在一個擁有數千或數百萬用戶的傳統數據庫中，使用同步復制的日志會有造成廣泛影響的中斷風險。因此，為了提高可用性和吞吐量，我們使用多個復制的日志，每個日志管理自己的數據集分區。
?
?
2.2?分區和局部性
為了擴展我們的復制方案并最大限度地提高底層數據存儲的性能，我們為應用程序提供了對其數據分區和位置的細粒度控制。
?
2.2.1?實體組
為了擴大吞吐量和本地化中斷，我們將數據劃分為一組實體組，每個實體組在很大范圍內獨立同步復制。底層數據存儲在每個數據中心的可擴展?NoSQL?數據存儲中（參見圖1）。
實體組中的實體使用單階段 ACID 事務（通過 Paxos 復制提交記錄）進行數據改寫。跨實體組的操作可能依賴于昂貴的兩階段提交，但通常利用 Megastore 的高效異步消息傳遞。發送實體組中的事務在隊列中放置一條或多條消息；接收實體組的事務原子地使用這些消息并應用隨后發生的數據改寫。
請注意，我們在邏輯上遙遠的實體組之間使用異步消息傳遞，而不是物理上遙遠的副本。數據中心之間的所有網絡流量都來自同步且一致的復制操作。實體組的局部索引服從?ACID?語義；跨實體組的一致性較弱。有關實體組上和實體組之間的各種操作，請參見圖2。
?
2.2.2?選擇實體組邊界
實體組為快速操作定義了數據的優先分組。過于細粒度的邊界會強制執行過多的跨組操作，但是在單個組中放置太多不相關的數據會序列化不相關的寫入，從而降低吞吐量。以下示例顯示了應用程序在這些約束條件下的工作方式：
Email 每個電子郵件帳戶形成一個自然實體組。帳戶內的操作是事務性的與一致性的：發送或標記消息的用戶保證會觀察到更改，盡管可能會故障轉移到另一個副本。外部郵件路由器處理帳戶之間的通信。
Blogs?一個博客應用程序可以用多個實體組類來建模。每個用戶都有一個配置文件，這自然是它自己的實體組。然而，博客是協作性的，沒有單一的永久所有者。我們創建了第二類實體組來保存每個博客的帖子和元數據。第三類提供了每個博客的唯一名稱。當單個用戶操作同時影響博客和個人資料時，應用程序依賴異步消息傳遞。對于流量較低的操作，比如創建一個新的博客并聲明它的唯一名稱，兩階段提交更方便，性能也更好。
Maps?地理數據沒有任何一致性或方便的自然粒度。映射應用程序可以通過將地球劃分為不重疊的面片來創建實體組。對于跨越補丁的突變，應用程序使用兩階段提交來使它們成為原子的。補丁必須足夠大，以至于兩階段事務不常見，但又足夠小，以至于每個補丁只需要很小的寫吞吐量。與前面的示例不同，實體組的數量不會隨著使用的增加而增加，因此最初必須創建足夠的補丁，以便在以后的規模上獲得足夠的聚合吞吐量。
幾乎所有基于?Megastore 構建的應用程序都找到了自然的方法來繪制實體組邊界。
?
2.2.3?物理布局
我們使用谷歌的?Bigtable?在單個數據中心內實現可擴展的容錯存儲，允許我們通過跨多行擴展操作來支持任意的讀寫吞吐量。我們通過讓應用程序控制數據的放置來最小化延遲和最大化吞吐量：通過選擇?Bigtable?實例和指定實例內的位置。
為了最大限度地減少延遲，應用程序試圖將數據保持在用戶附近，并將副本保持在彼此附近。他們將每個實體組分配給最常訪問它的區域或大陸。在該區域內，他們將三個或五個副本分配給具有獨立故障域的數據中心。
為了獲得低延遲、緩存效率和吞吐量，實體組的數據保存在連續的?Bigtable 行范圍內。我們的模式語言允許應用程序控制分層數據的放置，將一起訪問的數據存儲在附近的行中，或者反規范化到同一行中。
?
?
3?A TOUR OF?Megastore
Megastore 將這種架構映射到精心選擇的功能集上，以鼓勵快速開發可擴展的應用程序。這一部分推動了折衷，并描述了由此產生的面向開發人員的特性。
?
3.1?API?設計理念
ACID?事務簡化了對正確性的推理，但是能夠對性能進行推理也同樣重要。Megastore 強調成本透明的?API，運行時成本與應用程序開發人員的直覺相匹配。規范化的關系模式依賴于查詢時的連接來服務用戶操作。出于以下幾個原因，這種模式不適合?Megastore 應用：
(1) 與表達性查詢語言相比，高容量交互式工作負載從可預測的性能中獲益更多。
(2) 在我們的目標應用程序中，讀取多于寫入，因此將工作從讀取時間轉移到寫入時間是值得的。
(3) 在像?Bigtable?這樣的鍵值存儲中，存儲和查詢分層數據非常簡單。
考慮到這一點，我們設計了一個數據模型和模式語言來提供對物理位置的細粒度控制。分層布局和聲明性非規范化有助于消除大多數連接的需要。查詢指定對特定表和索引的掃描或查找。需要時，連接在應用程序代碼中實現。我們提供了合并連接算法在合并階段的實現，其中用戶提供了多個查詢，這些查詢以相同的順序返回同一表的主鍵；然后，我們返回所有提供的查詢的鍵的交集。
我們也有通過并行查詢實現外部連接的應用程序。這通常涉及索引查找，然后使用初始查找的結果進行并行索引查找。我們發現，當并行進行二級索引查找，并且第一次查找的結果數量相當少時，這就為?SQL?風格的連接提供了一個有效的替代。
雖然模式更改需要對查詢實現代碼進行相應的修改，但該系統保證了在構建特性時對其性能影響有清晰的理解。例如，當用戶（可能沒有數據庫背景）發現自己在寫類似嵌套循環連接算法的東西時，他們很快意識到最好添加一個索引，并遵循上面的基于索引的連接方法。
?
3.2?數據模型
Megastore 定義了一個位于關系數據庫管理系統的抽象元組和?NoSQL?的具體行列存儲之間的數據模型。像在關系數據庫管理系統中一樣，數據模型在模式中聲明，并且是強類型的。每個模式都有一組表，每個表都包含一組實體，這些實體又包含一組屬性。屬性是命名和類型化的值。類型可以是字符串、各種類型的數字或谷歌的協議緩沖區。它們可以是必需的、可選的或重復的（允許在單個屬性中列出值）。表中的所有實體都具有相同的允許屬性集。屬性序列用于形成實體的主鍵，主鍵在表中必須是唯一的。圖?3?顯示了一個簡單照片存儲應用程序的示例模式。
Megastore 表可以是實體組根表，也可以是子表。每個子表必須聲明一個引用根表的可分辨外鍵，如圖?3?中的實體組鍵注釋所示。因此，每個子實體引用其根表中的特定實體（稱為根實體）。實體組由根實體以及子表中引用它的所有實體組成。一個?Megastore 實例可以有幾個根表，從而產生不同類別的實體組。在圖?3?的示例模式中，每個用戶的照片集合是一個單獨的實體組。根實體是用戶，照片是子實體。請注意，"照片標簽"字段是重復的，允許每個照片有多個標簽，而不需要子表。
?
3.2.1?用鍵預連接
傳統的關系建模建議所有的主鍵都采用代理值，而?Megastore 鍵則被選擇來集群將一起讀取的實體。每個實體映射到一個單一的?Bigtable?行；主鍵值被連接起來形成?Bigtable?行鍵，每個剩余的屬性占用它自己的?Bigtable?列。
請注意圖?3?中的照片和用戶表如何共享一個公共的?user_id?key 的前綴。表內用戶指令指示?Megastore 將這兩個表放在同一個?Bigtable 中，鍵排序確保照片實體存儲在相應用戶的旁邊。這種機制可以遞歸地應用于加速沿任意連接深度的查詢。因此，用戶可以通過操作?key 順序來強制分層布局。
模式聲明鍵是升序還是降序排序，或者完全避免排序：SCATTER?屬性指示?Megastore 在每個鍵前添加一個兩字節的散列。以這種方式編碼單調遞增的鍵可以防止跨?Bigtable?服務器的大型數據集中出現熱點。
?
3.2.2 ?Indexes
輔助索引可以在任何實體屬性列表上聲明，也可以在協議緩沖區中的字段上聲明。我們區分了兩個高層次的索引類別：本地和全局（見圖2）。本地索引被視為每個實體組的單獨索引。它用于在實體組中查找數據。在圖?3?中，PhotosByTime?是一個本地索引的例子。索引條目存儲在實體組中，并自動更新，與主要實體數據保持一致。
全局索引跨越實體組。它用于在事先不知道包含實體的實體組的情況下查找實體。圖?3?中的?PhotosByTag?索引是全局的，可以發現帶有給定標簽的照片，而不考慮所有者。全局索引掃描可以讀取許多實體組擁有的數據，但不能保證反映所有最近的更新。Megastore 提供了額外的索引功能：
3.2.2.1?存儲條款
通過索引訪問實體數據通常是一個兩步過程：首先讀取索引以找到匹配的主鍵，然后使用這些鍵來獲取實體。我們提供了一種將實體數據的部分直接反規格化為索引條目的方法。通過向索引中添加?STORING?子句，應用程序可以存儲主表中的附加屬性，以便在讀取時更快地進行訪問。例如，PhotosByTag?索引存儲照片縮略圖網址，以便更快地檢索，而不需要額外的查找。
?
3.2.2.2?重復索引
Megastore 提供了索引重復屬性和協議緩沖子字段的能力。重復索引是子表的有效替代。照片字節標簽是一個重復的索引：標簽屬性中的每個唯一條目都會代表照片創建一個索引條目。
?
3.2.2.3?內聯索引
內聯索引提供了一種將來自源實體的數據反規范化為相關目標實體的方法：來自源實體的索引條目在目標條目中顯示為虛擬的重復列。通過使用目標實體的第一個主鍵作為索引的第一個組成部分，并在與目標實體相同的?Bigtable?中物理定位數據，可以在任何具有引用另一個表的外鍵的表上創建內聯索引。
內聯索引對于從子實體中提取信息片段并將數據存儲在父實體中以便快速訪問非常有用。與維護多對多鏈接表相比，再加上重復的索引，它們還可以更有效地實現多對多關系。
PhotosByTime?索引可以作為父用戶表的內聯索引來實現。這將使數據可作為正常索引或用戶的虛擬重復屬性訪問，每個包含的照片都有一個按時間排序的條目。
?
3.2.3?映射到?BigTable
Bigtable?列名是?Megastore 表名和屬性名的串聯，允許來自不同?Megastore 表的實體映射到同一個?Bigtable?行，而不會發生沖突。圖?4?顯示了示例照片應用程序中的數據在?Bigtable?中的外觀。
在根實體的?Bigtable?行中，我們存儲實體組的事務和復制元數據，包括事務日志。將所有元數據存儲在一個?Bigtable 行中允許我們通過一個?Bigtable 事務自動更新它。每個索引條目都表示為一個?Bigtable?行；使用與索引實體的主鍵連接的索引屬性值來構造單元格的行鍵。例如，PhotosByTime?索引行關鍵字將是每張照片的元組（用戶?id、時間、主鍵）。對重復字段進行索引會為每個重復元素生成一個索引條目。例如，一張帶有三個標簽的照片的主鍵會在?PhotosByTag?索引中出現三次。
?
?
3.3?事務和并發控制
每個大型實體組的功能就像一個微型數據庫，提供可序列化的 ACID 語義。事務將其突變寫入實體組的提前寫日志，然后對數據應用這些突變。
Bigtable?提供了在具有不同時間戳的同一行/列對中存儲多個值的能力。我們使用這個特性來實現多版本并發控制（MVCC）：當一個事務中的突變被應用時，這些值被寫入它們的事務的時間戳。讀者使用上次完全應用的事務的時間戳來避免看到部分更新。讀者和寫者不會相互阻塞，并且在事務期間，讀取和寫入是隔離的。
Megastore 提供當前、快照和不一致的讀取。當前和快照讀取總是在單個實體組的范圍內完成。當開始當前讀取時，事務系統首先確保應用所有先前提交的寫入；然后，應用程序讀取最近提交的事務的時間戳。對于快照讀取，系統獲取最后一個已知的完全應用的事務的時間戳，并從那里讀取，即使一些已提交的事務尚未應用。Megastore 還提供不一致讀取，忽略日志狀態，直接讀取最新值。這對于具有更嚴格的延遲要求并且可以容忍陳舊或部分應用的數據的操作非常有用。
寫事務總是從當前讀取開始，以確定下一個可用的日志位置。提交操作將變化收集到一個日志條目中，給它分配一個比以前更高的時間戳，并使用?Paxos?將其附加到日志中。該協議使用樂觀并發：雖然多個寫入者可能試圖寫入同一日志位置，但只有一個人會贏得寫入權利。其余的將注意到勝利的寫，中止，并重試他們的操作。咨詢鎖定可用于減少爭用的影響。通過會話關聯性對特定前端服務器的寫入進行批處理可以完全避免爭用。完整的事務生命周期如下：
(1) 讀取：獲取上次提交事務的時間戳和日志位置。
(2) 應用程序邏輯：從?Bigtable 中讀取，并將寫入內容收集到日志條目中。
(3) 提交：使用?Paxos?來實現將該條目附加到日志的一致性。
(4) 應用：將突變寫入?Bigtable 中的實體和索引。
(5) 清理：刪除不再需要的數據。
寫操作可以在提交后的任何時間點返回到客戶端，盡管它會盡最大努力等待最近的復制副本應用。
?
3.3.1?隊列
隊列提供實體組之間的事務消息傳遞。它們可用于跨組操作、將多個更新批量處理到單個事務或延遲工作。實體組上的事務除了更新其實體外，還可以原子地發送或接收多個消息。每條消息有一個發送和接收實體組；如果它們不同，則交付是異步的（見圖2）。
隊列提供了一種執行影響許多實體組的操作的方法。例如，考慮一個日歷應用程序，其中每個日歷都有一個不同的實體組，我們希望向一組日歷發送邀請。單個事務可以自動向許多不同的日歷發送邀請隊列消息。每個接收消息的日歷將在其自己的事務中處理邀請，該事務更新被邀請者的狀態并刪除消息。
在功能齊全的關系數據庫管理系統中，消息隊列有著悠久的歷史。我們的支持以其規模而聞名：聲明一個隊列會自動在每個實體組上創建一個收件箱，給我們提供數百萬個端點。
?
3.3.2?兩階段提交
Megastore 支持跨實體組的原子更新的兩階段提交。由于這些事務具有高得多的延遲并增加了爭用的風險，我們通常不鼓勵應用程序使用該特性來支持隊列。然而，它們在簡化應用程序代碼以實現唯一的二級密鑰實施方面很有用。
?
?
3.4?其他功能
我們已經與?Bigtable?的全文索引建立了緊密的集成，其中更新和搜索參與?Megastore 的事務和多版本并發。在?Megastore 模式中聲明的全文索引可以索引表的文本或其他應用程序生成的屬性。
同步復制足以抵御最常見的損壞和事故，但在程序員或操作員出錯的情況下，備份可能是無價的。Megastore 的集成備份系統支持事務日志的定期完整快照和增量備份。恢復過程可以將實體組的狀態恢復到任意時間點，也可以省略選定的日志條目（在意外刪除之后）。備份系統符合已刪除數據過期的規則和常識原則。
應用程序可以選擇加密靜態數據，包括事務日志。加密對每個實體組使用不同的密鑰。我們避免授予相同的操作員訪問加密密鑰和加密數據的權限。
?
?
4?復制
本節詳細介紹了我們的同步復制方案的核心：Paxos?的低延遲實現。我們討論運營細節，并介紹我們生產服務的一些衡量標準。
?
4.1?概述
Megastore 的復制系統提供了存儲在其底層副本中的數據的單一且一致的視圖。讀取和寫入可以從任何副本啟動，并且無論客戶端從哪個副本啟動，ACID?語義都會得到保留。復制是通過將每個實體組的事務日志同步復制到復制副本的仲裁中來完成的。寫操作通常需要一輪數據中心間通信，正常情況下的讀操作在本地運行。當前讀取有以下保證：
(1) 讀取的總是最后確認的寫入。
(2) 觀察到寫入后，所有將來的讀取都會觀察到該寫入。（在確認之前，可能會觀察到寫入）
?
?
4.2?Paxos?簡介
Paxos?算法是一種在一組副本中就單個值達成共識的方法。它可以容忍延遲或重新排序的消息以及因停止而失敗的副本。大多數副本必須是活躍的和可達的，算法才能取得進展，也就是說，它允許?2F + 1?副本最多有?F?個故障。一旦某個值被大多數人選中，以后所有讀取或寫入該值的嘗試都會得到相同的結果。
單獨確定單個值的結果的能力對數據庫來說用處不大。數據庫通常使用?Paxos?來復制事務日志，其中?Paxos?的單獨實例用于日志中的每個位置。新值被寫入日志中最后選擇的位置之后的位置。
最初的?Paxos?算法不適用于高帶寬網絡鏈路，因為它需要多輪通信。在達成一致之前，寫入至少需要兩次副本間往返：一輪準備，保留后續一輪接受的權利。讀取至少需要一輪準備，以確定最后選擇的值。建立在?Paxos?上的系統減少了使其成為實用算法所需的往返次數。我們將首先回顧基于主機的系統如何使用?Paxos，然后解釋我們如何使?Paxos?高效。
?
?
4.3?基于?Master?的方法
為了最大限度地減少延遲，許多系統使用一個專用?master，所有讀取和寫入都指向該master。master?參與所有寫入，因此它的狀態始終是最新的。它可以在沒有任何網絡通信的情況下提供當前一致狀態的讀數。通過在每次接受時進行下一次寫操作的準備，寫操作被簡化為一輪通信。主機可以一起批量寫入，以提高吞吐量。
對?master?的依賴限制了讀和寫的靈活性。事務處理必須在主副本附近完成，以避免順序讀取造成的延遲累積。任何潛在的主副本必須有足夠的資源用于系統的全部工作負載；從屬副本浪費資源，直到他們成為?master。master?故障轉移可能需要復雜的狀態機，并且在服務恢復之前必須經過一系列計時器。很難避免用戶可見的中斷。
?
?
4.4?Megastore 的方法
在本節中，我們將討論使?Paxos?對我們的系統實用的優化和創新。
4.4.1?快速讀取
我們設置了一個早期要求，即當前讀取通常應該在沒有副本間?RPC?的任何副本上執行。由于寫入通常在所有副本上都成功，因此允許在任何地方進行本地讀取是現實的。這些本地讀取為我們提供了更好的利用率、所有區域的低延遲、細粒度的讀取故障轉移和更簡單的編程體驗。
我們設計了一個名為協調器的服務，每個副本的數據中心都有服務器。協調服務器跟蹤一組實體組，其副本已觀察到該組實體組的所有?Paxos?寫入。對于該集中的實體組，副本具有足夠的狀態來服務本地讀取。保持協調器狀態是寫算法的責任。如果一個復制副本的?Bigtable 上的寫操作失敗，則在該復制副本的協調器收回該組的密鑰之前，不能將其視為已提交。由于協調器很簡單，他們比?Bigtable?更可靠、更快速地做出響應。第?4.7?節描述了罕見故障情況或網絡分區的處理。
?
4.4.2?快速寫入
為了實現快速的單往返寫入，Megastore 采用了基于?master 的方法所使用的預準備優化。在基于?master 的系統中，每次成功寫入都包含一條隱含的準備消息，授予主機為下一個日志位置發出接受消息的權利。如果寫入成功，準備工作將得到執行，下一次寫入將直接跳到接受階段。Megastore 不使用專門的?master，而是使用?leader。
我們為每個日志位置運行一個獨立的?Paxos?算法實例。每個日志位置的前導是與前一個日志位置的一致的值一起選擇的一個可分辨的副本。leader 仲裁哪一個值可以使用?proposal number zero。第一個向?leader 提交值的寫者贏得了要求所有副本接受該值作為零號建議書的權利。所有其他寫者必須依靠兩階段?Paxos。
由于寫入者在將值提交給其他副本之前必須與?leader 溝通，因此我們將寫入者延遲降至最低。我們根據大多數應用程序重復提交來自同一地區的寫操作的觀察，設計了選擇下一個寫操作負責人的策略。這就產生了一個簡單但有效的啟發式方法：使用最近的副本。
?
4.4.3?副本類型
到目前為止，所有副本都是完全副本，這意味著它們包含所有實體和索引數據，并且能夠服務于當前讀取。我們也支持?witness?副本的概念。witness?在?Paxos?輪次中投票并存儲寫前日志，但不應用日志，也不存儲實體數據或索引，因此存儲成本較低。它們實際上是平局決勝者，在沒有足夠的完整副本來形成法定人數時使用。因為它們沒有協調器，所以當它們未能確認寫入時，不會強制執行額外的往返。
只讀副本（Read-only replicas）與?witness?副本相反：它們是非投票副本，包含數據的完整快照。對這些副本的讀取反映了最近某個時間點的一致的視圖。對于可以容忍這種過時的讀取，只讀副本有助于在廣泛的地理區域傳播數據，而不會影響寫入延遲。
?
?
4.5?架構
圖?5?顯示了具有兩個完整副本和一個?witness?副本的實例的?Megastore 的關鍵組件。
Megastore 是通過客戶端庫和輔助服務器部署的。應用程序鏈接到客戶端庫，該庫實現?Paxos?和其他算法：選擇一個副本進行讀取，追趕一個落后的副本，等等。每個應用服務器都有一個指定的本地副本。客戶端庫通過直接向本地?Bigtable?提交事務，使該副本上的?Paxos?操作持久。為了最小化廣域往返，庫將遠程?Paxos?操作提交給與本地?Bigtable?通信的無狀態中間復制服務器。客戶端、網絡或?Bigtable?故障可能會導致寫操作以不確定的狀態被放棄。復制服務器定期掃描未完成的寫入，并通過?Paxos?建議無操作值以完成寫入。
?
?
4.6?數據結構和算法
本節詳細介紹了從對單個值的共識到正常運行的復制日志的飛躍所需的數據結構和算法。
4.6.1?復制的日志
每個副本存儲組已知的日志條目的突變信息和元數據。為了確保復制副本即使在從以前的中斷中恢復時也能參與寫入仲裁，我們允許復制副本接受無序建議。我們將日志條目作為獨立的單元格存儲在?Bigtable?中。
當日志副本包含不完整的日志前綴時，我們稱之為"漏洞"。圖?6?展示了這個場景，其中有一個?Megastore 實體組的一些代表性日志副本。日志位置?0-99?已被完全清除，位置?100?被部分清除，因為每個副本都被告知其他副本將永遠不會請求拷貝。日志位置?101?被所有副本接受。日志位置?102?在?A?和?C?中發現了一個空的法定人數。位置?103?值得注意，因為它已經被?A?和?C?接受，給?B?留下了一個?103?的洞。副本?A?和副本?B?上的位置?104?發生了沖突的寫入嘗試，導致無法達成一致。
?
4.6.2 Reads
在為當前讀取（以及寫入之前）做準備時，必須至少更新一個副本：必須將之前提交給日志的所有變化復制到該副本并應用到該副本。我們稱這個過程為追趕（較為重要的概念）。
省略了一些期限管理，當前讀取的算法（如圖?7?所示）如下：
(1) 查詢本地：查詢本地副本的協調器，以確定實體組在本地是否是最新的。
(2) 查找位置：確定可能實現的最高日志位置，并選擇已通過該日志位置應用的副本。
? ? ? ? (a)（本地讀取）如果步驟?1?表明本地副本是最新的，則從本地副本中讀取最高可接受的日志位置和時間戳。
? ? ? ? (b)（多數讀取）如果本地復制副本不是最新的（或者如果步驟?1?或步驟?2a?超時），從多數復制副本中讀取，以找到任何復制副本看到的最大日志位置，并選擇要讀取的復制副本。我們選擇響應速度最快或最新的副本，而不總是本地副本。
(3) 捕捉：選擇復制副本后，立即將其捕捉到最大已知日志位置，如下所示：
? ? ? ? (a) 對于所選副本不知道一致的值的每個日志位置，從另一個副本讀取該值。對于任何沒有已知提交值的日志位置，調用?Paxos?來建議一個無操作寫入（no-op write）。Paxos?將驅動大多數副本聚合到一個值上，要么是無操作，要么是以前建議的寫入。
? ? ? ? (b) 順序應用所有未應用日志位置相一致的值，以將副本的狀態提升到分布式一致性狀態。如果失敗，請在另一個副本上重試。
(4) 驗證：如果選擇了本地復制副本，并且以前不是最新的，則向協調器發送驗證消息，聲明（實體組、復制副本）對反映了所有提交的寫入。不要等待回復——如果請求失敗，下一次讀取將重試。
(5) 查詢數據：使用選定日志位置的時間戳讀取選定的副本。如果選定的復制副本不可用，請選擇一個備用復制副本，執行捕獲，然后改為從中讀取。單個大型查詢的結果可以從多個副本透明地組裝。
注意，實際上?1?和?2a?是并行執行的。
?
4.6.3 Writes
完成讀算法后，Megastore 觀察下一個未使用的日志位置、最后一次寫的時間戳和下一個 leader?副本。在提交時，將對狀態的所有掛起的更改打包并提出，并使用時間戳和下一個?leader?指定，作為下一個日志位置的共識值。如果這個值贏得了分布式共識，它將應用于所有完全副本的狀態；否則，整個事務將中止，必須從讀取階段開始重試。
如上所述，協調器跟蹤在其副本中最新的實體組。如果復制副本上的寫入不被接受，我們必須從該復制副本的協調器中刪除實體組的密鑰。這個過程叫做失效（invalidation，較為重要的概念）。在寫入被視為已提交并準備好應用之前，所有完整復制副本必須已接受該實體組，或者其協調器已失效。寫算法（如圖?8?所示）如下：
(1) Accept Leader：要求領導接受該值作為零號建議（proposal number zero）。如果成功，請跳到步驟 3。
(2) Prepare：在所有副本上運行?Paxos?準備階段，該副本的建議編號高于目前在此日志位置看到的任何副本。用發現的最高編號的建議（如果有）替換正在寫入的值。
(3) Accept：要求剩余的副本接受該值。如果大多數副本都失敗了，請在隨機回退后返回步驟?2。
(4) Invalidate：使不接受該值的所有完整副本上的協調器無效。下面第?4.7?節描述了這一步驟的故障處理。
(5) Apply：在盡可能多的副本上應用改變的值。如果選擇的值不同于最初建議的值，則返回沖突錯誤。
步驟?1?實現了第?4.4.2?節中的"快速寫入"。寫者通過使用單階段 Paxos?在建議編號為零時發送接受命令來跳過準備消息。在日志位置?n?選擇的下一個?leader?副本仲裁用于?n + 1?處的提議零的值。由于多個建議者可能提交建議編號為零的值，因此在此副本中進行序列化可確保只有一個值與特定日志位置的建議編號相對應。
在傳統的數據庫系統中，提交點（更改是持久的）與可見點（visibility point）（讀取可以看到更改，寫入器可以收到成功通知）是相同的。在我們的寫算法中，當寫程序贏得?Paxos?回合時，提交點是在步驟?3?之后，但可見性點是在步驟?4?之后。只有在所有完整副本已經接受或其協調器失效后，寫入才能被確認并應用更改。在步驟?4?之前的確認可能會違反我們的一致性保證：在副本上的當前讀取，如果無效被跳過，則可能無法觀察到已確認的寫入。
?
?
4.7 Coordinator Availability
協調器進程在每個數據中心運行，并且只保持關于其本地副本的狀態。在上面的寫算法中，每個完整副本必須接受或使其協調器無效，因此任何單個副本故障（Bigtable 和協調器）都可能導致不可用。實際上，這不是一個常見的問題。協調器是一個簡單的過程，沒有外部依賴性，也沒有持久存儲，因此它往往比?Bigtable?服務器穩定得多。然而，網絡和主機故障仍然會使協調器不可用。
4.7.1?故障檢測
為了解決網絡分區問題，協調器使用帶外協議來識別其他協調器何時啟動、運行正常并且通常可以訪問。我們使用谷歌的?Chubby?鎖服務：協調器在啟動時在遠程數據中心獲得特定的?Chubby ?鎖。為了處理請求，協調器必須持有其大部分鎖。如果它在崩潰或網絡分區中丟失了大部分鎖，它會將其狀態恢復為保守的默認狀態，認為其權限內的所有實體組都已過時。復制副本上的后續讀取必須從大多數復制副本中查詢日志位置，直到鎖被重新獲得并且其協調器條目被重新驗證。
通過測試協調器是否丟失了鎖，寫入器與協調器故障隔離開來：在這種情況下，寫入器知道協調器在重新獲得鎖時會認為自己無效。當包含實時協調器的數據中心突然變得不可用時，此算法可能會導致短暫（幾十秒）的寫入中斷——所有寫入者都必須等待協調器的?Chubby?鎖到期，然后才能完成寫入（很像等待主故障切換觸發）。與主節點故障轉移后不同，當協調器的狀態被重建時，讀取和寫入可以順利進行。這種短暫而罕見的停機風險是由它所允許的快速本地讀取的穩定狀態所證明的。
協調器活性協議易受不對稱網絡分區的影響。如果協調器可以維護其?Chubby?鎖的租約，但是已經與提議者失去聯系，那么受影響的實體組將經歷寫中斷。在這種情況下，操作員執行手動步驟來禁用部分隔離的協調器。我們只遇到過幾次這種情況。
?
4.7.2 Validation Races
除了可用性問題，讀寫協調器的協議必須應對各種競爭條件。無效消息總是安全的，但是驗證消息必須小心處理。協調器通過始終發送與操作相關聯的日志位置來保護早期寫入的驗證和后期寫入的無效之間的競爭。編號較高的無效總是勝過編號較低的有效。（Races between validates for earlier writes and invalidates for later writes?are protected in the coordinator by?always sending the log?position associated with the action. Higher numbered invalidates always trump lower numbered validates）還存在與寫入器在位置?n?的無效和在位置?m < n?的驗證之間的崩潰相關聯的競爭。我們使用協調器的每個化身的唯一時期號來檢測崩潰：只有在最近讀取協調器的?epoch?保持不變時，validates?才允許修改協調器狀態。總之，就對可用性的影響而言，使用協調器允許從任何數據中心進行快速本地讀取并不是免費的。但實際上，運行協調器的大多數問題都可以通過以下因素得到緩解：
(1) 協調器是比大型服務器簡單得多的過程，具有更少的依賴性，因此自然更加可用。
(2) 協調器簡單、同質的工作負載使其成本低廉且可預測。
(3) 協調器的輕網絡流量允許使用具有可靠連接的高網絡服務質量。
(4) 操作員可以集中禁用維護或不健康期間的協調器。對于某些監控信號，這是自動的。
(5) Chubby?鎖的法定數量檢測到大多數網絡分區和節點不可用。
?
?
4.8?寫吞吐量
我們的?Paxos?實現在系統行為上有著有趣的權衡。多個數據中心中的應用服務器可以同時啟動對同一實體組和日志位置的寫入。除了一個之外，所有的都將失敗，需要重試它們的事務。對于給定的每個實體組提交速率，同步復制數量的增加提升了延遲增加的沖突的可能性。
將該速率限制為每個實體組每秒幾個寫入，會產生微不足道的沖突率。對于實體一次被少數用戶操縱的應用程序，這種限制通常不是問題。我們的大多數目標客戶通過更精細地分割實體組或確保將副本放在同一區域來擴展寫吞吐量，從而降低延遲和沖突率。
具有一些服務器"粘性"的應用程序能夠很好地將用戶操作批處理到更少的?Megastore 事務中。大容量存儲隊列消息的批量處理是一種常見的批處理技術，可以降低沖突率并提高聚合吞吐量。對于必須經常超過每秒幾次寫入的組，應用程序可以使用協調服務器分配的細粒度咨詢鎖。對事務進行背靠背序列化可以避免與重試相關的延遲，并在檢測到沖突時恢復到兩階段?Paxos。
?
?
4.9 Operational Issues
當一個特定的完整副本變得不可靠或失去連接時，Megastore 的性能可能會下降。我們有許多方法來應對這些失敗，包括：路由用戶遠離有問題的副本、禁用其協調器，或完全禁用它。在實踐中，我們依賴于技術的組合，每一種技術都有自己的權衡。
對中斷的第一個也是最重要的響應是通過將流量重新路由到其他副本附近的應用服務器來禁用受影響副本上的?Megastore 客戶端。這些客戶端通常會經歷相同的中斷，影響其下方的存儲堆棧，并且可能無法從外部世界訪問。
如果不健康的協調服務器可能繼續持有它們的?Chubby?鎖，僅僅重新路由流量是不夠的。下一個響應是禁用復制副本的協調器，確保問題對寫入延遲的影響最小。（第?4.7?節更詳細地描述了這個過程。）一旦免除了寫入者使復制副本的協調器無效的責任，不健康的復制副本對寫入延遲的影響就會受到限制。只有寫入算法中最初的"accept leader"步驟依賴于副本，我們在回到兩階段?Paxos?并為下一次寫入指定更健康的?leader?之前保持一個嚴格的截止日期。
一個更嚴厲且很少使用的操作是完全禁用副本：無論是客戶端還是復制服務器都不會嘗試與其通信。雖然隔離副本看起來很有吸引力，但主要影響是可用性：少一個副本就有資格幫助寫入者形成法定人數。有效的用例是當嘗試的操作可能造成傷害時——例如，當底層的?Bigtable 嚴重過載時。
?
?
4.10 生產指標
Megastore 已經在?Google?內部部署了好幾年；超過?100?個生產應用程序將它用作存儲服務。在本節中，我們將報告對其規模、可用性和性能的一些衡量。
圖?9?顯示了可用性的分布，以每個應用程序、每個操作為基礎進行衡量。盡管機器故障、網絡故障、數據中心中斷和其他故障源源不斷，但我們的大多數客戶都看到了極高的可用性（至少五個?9）。我們樣本的底端包括一些仍在測試的生產前應用和具有較高故障容限的批處理應用。
根據數據量，平均讀取延遲為幾十毫秒，表明大多數讀取是本地的。根據數據中心之間的距離、寫入數據的大小和完整副本的數量，大多數用戶的平均寫入延遲為?100-400?毫秒。圖?10?顯示了讀取和提交操作的平均延遲分布。
?
?
5?經驗
對可測試性的強調有助于系統的開發。代碼被大量（但廉價）的斷言和日志記錄所裝備，并且具有徹底的單元測試覆蓋。但是最有效的?Bug?發現工具是我們的網絡模擬器：偽隨機測試框架。它能夠探索模擬節點或線程之間通信的所有可能順序和延遲的空間，并在給定相同種子的情況下確定性地再現相同行為。Bug?是通過發現觸發斷言失敗（或不正確結果）的有問題的事件序列而暴露出來的，通常有足夠的日志和跟蹤信息來診斷問題，然后將其添加到單元測試套件中。雖然不可能對調度狀態空間進行窮舉搜索，但偽隨機模擬探索的內容比通過其他方式實際探索的內容要多。通過每晚運行數千小時的模擬操作，測試發現了許多令人驚訝的問題。
在實際部署中，我們觀察到了預期的性能：我們的復制協議優化確實在大多數情況下提供了本地讀取，而寫入的開銷只有一次廣域網往返的開銷。大多數應用發現延遲是可以容忍的。有些應用程序旨在對用戶隱藏寫入延遲，有些應用程序必須謹慎選擇實體組邊界，以最大化其寫入吞吐量。這種努力產生了主要的操作優勢：Megastore 的延遲尾部比底層的延遲尾部短得多，大多數應用程序可以承受計劃內和計劃外停機，幾乎沒有或根本沒有手動干預。
大多數應用程序使用?Megastore 模式語言來建模它們的數據。一些應用程序在?Megastore 模式語言中實現了它們自己的實體屬性值模型，然后使用它們自己的應用程序邏輯建模它們的數據（最顯著的是，谷歌應用引擎）。一些人混合使用兩種方法。在靜態模式之上構建動態模式，而不是相反，允許大多數應用程序享受靜態模式的性能、可用性和完整性好處，同時仍然為那些需要它的人提供動態模式的選項。
術語"高可用性"通常表示屏蔽故障的能力，使系統集合比單個系統更可靠。雖然容錯是一個非常理想的目標，但它也有自己的陷阱：它經常隱藏持久的潛在問題。我們組里有句話："容錯就是故障屏蔽"。我們系統的彈性加上對跟蹤潛在故障的警惕性不足，往往會導致意想不到的問題：持續未糾正問題之上的微小瞬時錯誤會導致更大的問題。
另一個問題是流量控制。一個容忍有缺陷的參與者的算法可能會忽視慢參與者。理想情況下，一個由不同機器組成的集合只能和能力最差的成員一樣快地取得進展。如果慢被解釋為一種錯誤，并被容忍，大多數最快的機器將按照自己的速度處理請求，只有當被努力追趕的落后者的負載拖慢時，才會達到平衡。我們稱這種異常現象為鏈狀團伙扼制，喚起了一群逃跑的罪犯的形象，他們只能盡可能快地拖住掉隊者。
Megastore 的預寫日志的一個好處是易于集成外部系統。任何冪等運算都可以成為應用日志條目的一個步驟。
要為更復雜的查詢獲得良好的性能，需要注意?Bigtable?中的物理數據布局。當查詢速度較慢時，開發人員需要檢查?Bigtable?跟蹤，以了解為什么他們的查詢執行速度低于預期。?Megastore 不強制實施關于塊大小、壓縮、表拆分、位置組的特定策略，也不強制實施?Bigtable?提供的其他調優控制。相反，我們公開這些控件，為應用程序開發人員提供優化性能的能力（和負擔）。
?
?
6?相關工作
最近，人們對?NoSQL?數據存儲系統越來越感興趣，以滿足大型網絡應用的需求。代表作品包括?Bigtable，Cassandra，雅虎?PNUTS。在這些系統中，可伸縮性是通過犧牲傳統關系數據庫管理系統的一個或多個屬性來實現的，例如事務、模式支持、查詢能力。這些系統通常將事務的范圍縮小到單個鍵訪問的粒度，因此給構建應用程序設置了一個很大的障礙。有些系統將事務的范圍擴展到單個表中的多行，例如?Amazon SimpleDB?使用域的概念作為事務單元。然而，這種努力仍然有限，因為事務不能跨越表格或任意縮放。此外，目前大多數可擴展的數據存儲系統缺乏關系數據庫管理系統的豐富數據模型，這增加了開發人員的負擔。結合了數據庫和可擴展數據存儲的優點，?Megastore 在一個實體組中提供了事務性?ACID?保證，并提供了一個靈活的數據模型，具有用戶定義的模式、數據庫樣式和全文索引以及隊列。
跨地理分布的數據中心的數據復制是提高最新存儲系統可用性的不可或缺的手段。大多數流行的數據存儲系統使用具有較弱一致性模型的異步復制方案。例如，Cassandra、HbPase、CouchDB?和?Dynamo?使用最終一致性模型，PNUTS?使用"時間線"一致性。相比之下，同步復制保證了廣域網上強大的事務語義，并提高了當前讀取的性能。
傳統關系數據庫管理系統的同步復制帶來了性能挑戰，并且難以擴展。一些建議的變通辦法允許通過異步復制實現強一致性。一種方法是在復制更新效果之前完成更新，將同步延遲傳遞給需要讀取更新狀態的事務。另一種方法是將寫操作路由到單個主機，同時在一組副本之間分配只讀事務。更新被異步傳播到剩余的副本，讀取或者被延遲，或者被發送到已經同步的副本。最近一個關于高效同步復制的提議引入了一個排序預處理器，它可以確定性地調度傳入的事務，這樣它們就可以獨立地應用于多個副本，并得到相同的結果。同步負擔被轉移到預處理器上，預處理器本身必須是可伸縮的。
直到最近，很少有人使用?Paxos?來實現同步復制。SCALARIS?是一個使用?Paxos?提交協議來實現分布式哈希表復制的例子。Keyspace?還使用?Paxos?在通用鍵值存儲上實現復制。然而，這些系統的可擴展性和性能并不為人所知。Megastore 可能是第一個跨數據中心實施基于?Paxos?的復制，同時滿足云中可擴展網絡應用程序的可擴展性和性能要求的大型存儲系統。
傳統的數據庫系統提供了成熟和復雜的數據管理功能，但在為本文所針對的大規模交互式服務提供服務方面存在困難。MySQL?等開源數據庫系統無法擴展到我們要求的水平，而?Oracle ?等昂貴的商業數據庫系統會顯著增加云中大型部署的總擁有成本。此外，它們都沒有提供容錯同步復制機制，這是在云中構建交互式服務的關鍵部分。
?
?
7?結論
在本文中，我們介紹了?Megastore，這是一個可擴展、高可用性的數據存儲，旨在滿足交互式互聯網服務的存儲要求。我們使用?Paxos?進行同步廣域復制，為單個操作提供輕量級和快速的故障轉移。單個系統映像的便利性和運營商級可用性的操作優勢抵消了跨廣泛分布的副本進行同步復制的延遲損失。我們使用?Bigtable?作為我們的可擴展數據存儲，同時添加更豐富的原語，如?ACID?事務、索引和隊列。將數據庫劃分為實體組子數據庫為大多數操作提供了熟悉的事務特性，同時允許存儲和吞吐量的可伸縮性。
Megastore 生產中有?100?多個應用程序，面向內部和外部用戶，并提供更高級別的基礎架構。這些應用程序的數量和多樣性證明了兆存的易用性、通用性和強大。我們希望?Megastore 能夠展示當今可擴展存儲系統在功能集和復制一致性方面的中間立場的可行性。
總結
以上是生活随笔為你收集整理的Megastore：为交互式服务提供可扩展的高可用性存储的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Go 语言学习笔记(三)：类型系统
- 下一篇： Dynamo：亚马逊的高可用键值存储