【譯】Object Storage on CRAQ 上篇

摘要

大型存盤系統通常會在許多可能出故障的組件上進行資料復制和資料磁區，從而保證可靠性和可擴展性，但是許多商業部署系統為了實作更高的可用性和吞吐量，犧牲了強一致性，特別是那些實時互動系統，

本論文介紹了CRAQ的設計、實作和評估，CRAQ是一個挑戰上述僵化取舍的分布式物件存盤系統，我們的基本方法是對鏈式復制進行改性，在保證強一致性的同時，大幅提高讀取吞吐量，通過在所有物件副本上分配負載，CRAQ可以隨鏈的大小線性擴展，而無需增加一致性協調，同時，為了滿足某些應用程式的需求，CRAQ提供了弱一致性保證，這在系統處于高故障時期尤其有用，本文探討了為跨多個資料中心進行地理復制的CRAQ存盤而進行的額外設計和實作，從而提供優化區域性的操作，本文也討論了多物件原子更新和大物件更新的多播優化，

1. 引言

許多在線服務需要基于物件的存盤，將資料作為整個單元呈現給應用程式，物件存盤支持兩個基本原語：讀（或查詢）操作回傳以物件名稱存盤的資料塊，寫（或更新）操作修改單個物件的狀態，這一類基于物件的存盤由鍵值資料庫（例如BerkeleyDB或Apache的CouchDB）支持，并部署到商業資料中心（例如Amazon的Dynamo，Facebook的Cassandra以及Memcached），為了在這類系統中實作可靠性、負載平衡和可擴展性，物件命名空間在許多機器上進行了磁區，每個資料物件都被復制了幾次，

當應用程式有某些特殊需求時，基于物件的系統會比其對應的檔案系統更具吸引力，與分層目錄結構相反，物件存盤更適合于水平命名空間，例如在鍵值資料庫那樣，物件存盤簡化了支持整個物件修改的流程，并且，它們通常只需要推理某個指定物件的修改順序即可，而不是整個存盤系統；為每個物件提供一致性比而不是為所有操作和/或物件，代價要低的多，

在構建作為眾多應用程式基礎的存盤系統時，商業站點將高性能和高可用的需求放在首位，復制資料是為了承受單個節點甚至整個資料中心的故障帶來的威脅，無論這個故障是計劃內的還是計劃外的，確實在新聞媒體中處處可見資料中心離線導致期間整個網站都被關閉了的例子，對可用性和性能的高度關注，導致許多商業系統由于感知成本而犧牲了強一致性語意（例如Google、Amazon、eBay、Facebook等），

Van Renesse和Schneider近期提出了一種為物件存盤在故障停止服務器上的鏈式復制方法，該方法旨在提供強一致性的同時提高吞吐量，基本方法是將所有存盤物件的節點組織在一條鏈中，其中鏈的尾節點處理所有讀取請求，而鏈的頭節點處理所有寫入請求，在客戶端收到確認之前，寫操作沿鏈向下傳播，因此尾節點可以得到所有物件操作的執行順序，具有強一致性，該方法沒有任何復雜或多輪通信的協議，但是提供了簡單、高吞吐量和容易故障恢復的特性，

不幸的是，基礎的鏈復制方法有一些局限性，對一個物件的所有讀取都在頭節點，從而導致潛在的熱點問題，雖然可以通過一致性哈希方法或更中心化的目錄方法將集群中的節點組織到多個鏈中，以實作更好的負載均衡，但是如果特定物件訪問較少，這些演算法仍然可能會負載不平衡，這在實踐中是一個真實的問題，當嘗試跨多個資料中心構建鏈式，甚至可能出現更嚴重的問題，因為所有的讀取操作都可以由一個遠距離節點（鏈的尾節點）處理，

本文介紹了CRAQ的設計、實作和評估，CRAQ是一個物件存盤系統，在保持鏈式復制的強一致性特性的同時，通過支持分配查詢為讀取操作提供了較低的延遲和較高的吞吐量；分配查詢指的是將讀取操作分配給鏈中的所有節點執行，而不是所有操作都由單個主節點處理，本文的主要貢獻如下：

1. CRAQ使任何鏈節點都能在保持強一致性的同時處理讀操作，從而支持存盤物件在所有節點之間的負載平衡，此外，當大多數作業負載是讀取操作時，（例如GFS和Memcached系統中做的假設），CRAQ的性能可以和僅提供最終一致性的系統相媲美，
2. 除了強一致性外，CRAQ的設計還自然支持讀操作之間的最終一致性，從而降低寫操作期間的等待時間，并在短暫的磁區期間降級為只讀，CRAQ允許應用程式指定讀取操作可接受的最大陳舊度，
3. 利用負載均衡的特性，我們介紹了一種廣域系統設計，用于在跨地理位置的集群中構建CRAQ鏈，并保留了強區域性，具體而言，讀操作可以由本地集群進行處理，在最壞情況下（高寫爭用的時候），需要在廣域網中傳輸簡短的元資料資訊，我們還介紹了使用Zookeeper（一種類似于PAXOS的組成員系統）來管理部署，

最后，我們討論了CRAQ的其他擴展，包括將微事務集成到多物件原子更新中，以及使用多播來提高大物件更新的寫入性能，但是，我們尚未完成這些優化的實作，

CRAQ的初步性能評估顯示，與基礎的鏈式復制方法相比，它具有更高的吞吐量，在大多數負載都是讀操作的情況下，吞吐量與節點的數量成正比：三節點的鏈可以提升約200%的吞吐量，七節點的鏈可以提升約600%的吞吐量，在高寫爭用的情況下，CRAQ在三節點的鏈中的讀取吞吐量仍然比基礎的鏈式復制高出兩倍，并且讀取延遲較低，我們總結了CRAQ在各種作業負載和故障情況下的性能，最后，我們評估了CRAQ在跨地域復制方面的性能，證明其延遲遠低于基礎鏈式復制方法的延遲，

本文的剩余部分安排如下，第2節介紹了基礎鏈式復制與CRAQ協議之前的對比，以及CRAQ的最終一致性支持，第3節介紹了CRAQ在單資料中心和跨資料中心擴展到多條鏈的方法，以及管理鏈和節點的組成員服務，第4節涉及到諸如多物件更新和利用多播等擴展，第5節介紹了CRAQ的實作，第6節展示了CRAQ的性能評估，第7節回顧了相關作業，第8節進行總結，

2. 基礎系統模型

本節介紹了我們基于物件的介面和一致性模型，簡要概述了標準的鏈式復制模型，然后介紹了強一致的CRAQ模型及其變體，

2.1 介面和一致性模型

基于物件的存盤系統為用戶提供了兩個簡單的原語：

• \(write(objID, V)\): 寫（更新）操作存盤與物件識別符號\(objID\)關聯的值\(V\)，
• \(V\leftarrow read(objID)\): 讀（查詢）操作檢索與物件識別符號\(objID\)關聯的值\(V\)，

我們將討論關于單個物件的兩種主要的一致性型別，

• 強一致性 我們系統中的強一致性保證對于單個物件的所有的讀和寫操作均按一定順序執行，并且對于單個物件的讀始終能看到最新的值，
• 最終一致性 我們系統中的最終一致性意味著對單個物件的寫入仍然按一定順序應用于所有的節點，但是對于不同的節點，最終一致性讀可能在一段時間內回傳舊資料（即在寫入被應用到所有節點之前），但是，一旦所有的副本接收到寫入請求后，讀操作將永遠不會回傳比最近提交的寫入版本更舊的版本，實際上，如果客戶端保持與一個特定節點的會話（盡管不是與不同的節點的會話），則會看到單調的讀一致性（作者注：即對于一個物件的讀取將回傳相同的先前的值或一個更新的值，但是絕不會回傳舊版本的值），

接下來，我們介紹一下鏈式復制和CRAQ是如何提供強一致性的，

2.2 鏈式復制

鏈式復制（CR）是一種在多節點之間復制資料的方法，提供了強一致性的存盤介面，節點組成一條長度為\(C\)的鏈，鏈的頭節點處理來自客戶端的所有寫操作，當節點收到寫操作的請求時，他會繼續傳播給鏈中的下一個節點，一旦寫操作請求到達尾節點，該操作就已經被應用到了鏈中的所有副本中，此時認為該寫操作已提交，尾節點處理所有的讀操作，因此只有已提交的值才會被回傳，

圖1提供了一個長度為四的鏈的實體，所有讀請求的到達和處理都在尾節點，寫請求到達鏈的頭部，并向下傳播到尾部，當尾節點提交寫操作后，向客戶端發送回復，CR論文中介紹由尾節點直接向客戶端發送訊息；由于我們使用TCP，因此我們的實作實際由頭部節點復用之前與客戶端的連接，在收到尾節點的確認后直接進行回應，確認回傳在圖中用虛線表示，

CR簡單的拓撲結構使寫操作比其他提供強一致性的協議成本更低，多個并發寫入可以在鏈中進行流水線傳輸，傳輸成本平攤在所有節點上，之前作業的模擬結果顯示，與主/備復制相比，CR具有更高的吞吐量，同時還能更快、更容易地恢復，

鏈式復制實作了強一致性：由于所有的讀都在尾部進行，并且所有的寫入只有當到達尾部河駁交，因此鏈的尾部可以按序應用所有的操作，然而，這的確要付出一些代價，因為只有一個節點處理讀操作，因此降低了讀操作的吞吐量，無法隨著鏈的長度增加而進行擴展，但是這是有必要的，因為查詢中間節點可能為違反強一致性保證；特別是，在傳播程序中，對不同節點的并發讀取可能會看到不同的寫入值，

盡管CR專注于提供存盤服務，但也可以將其查詢/更新協議視為復制狀態機的介面，盡管本文的剩余部分僅從讀/寫物件存盤介面兩個角度考慮問題，但可以用類似的角度看待CRAQ，

2.3 分攤查詢的鏈式復制

當前只讀作業負載環境大受歡迎，因此CRAQ試圖通過允許鏈中的任意節點都來處理讀操作，同時仍提供強一致性保證，來提高吞吐量，CRAQ主要的擴展如下：

1. CRAQ中的單個節點允許存盤物件的多個版本，每個版本都包含一個單調遞增的版本號以及一個附加屬性：該版本是臟的還是干凈的，所有的版本初始化標記為干凈，
2. 當節點收到物件的新版本時（通過沿鏈路向下傳播的寫操作），該節點將此最新版本附加到該物件的串列中，
   • 如果該節點不是尾節點，則將該版本標記為臟，并將寫操作傳播到后繼節點，
   • 如果該節點是尾節點，則將版本標記為干凈，此時我們將物件版本稱為已提交，然后，尾節點可以通過在鏈中反向傳播確認來通知所有其他節點此次提交，
3. 當節點接收到某個物件版本的確認訊息時，該節點會將該物件版本標記為干凈，然后，該節點就可以洗掉該物件的所有先前版本，
4. 當節點收到對物件的讀取請求時：
   • 如果最新已知的版本是干凈的，則節點將回傳該值，
   • 如果最新已知的版本是臟的，該節點會與尾節點進行通信，查詢尾節點最后提交的版本號，然后節點回傳該物件的版本；按照規則，可以確保該節點存盤了該版本的物件，我們注意到，盡管尾節點可以在它回復版本請求和中間節點向客戶端發送回復之前提交新版本，但是這不違反強一致性的定義，因為讀操作從尾節點來說是序列化的，

請注意，如果節點收到寫提交的確認后立即洗掉舊版本，則也可以隱式確定節點上的物件的狀態是臟還是干凈，也就是說如果節點中的物件只有一個版本，那么該物件是干凈的；否則，物件是臟的，必須從尾節點檢索正確的版本，

圖2顯示了處于初始干凈狀態的CRAQ鏈，每個節點都存盤物件的相同副本，因此到達鏈中任何節點的任何讀請求都將回傳相同的值，除非收到寫請求，否則所有節點都將保持在干凈狀態，

圖3顯示了寫操作的傳播程序（由紫色虛線顯示），頭節點收到寫入該物件的新版本（\(V_2\)）的初始訊息，因此頭節點的物件狀態是臟的，然后，頭節點將寫訊息沿著鏈向下傳播到第二個節點，該節點也將該物件標記為臟（物件\(K\)有多個版本\([V_1,V_2]\)），如果一個處于干凈狀態的節點收到讀請求，它們將立即回傳該物件的舊版本：這是正確的，因為新版本尚未在尾節點提交新版本，但是，如果兩個臟節點中的其中一個收到讀請求，它們會向尾節點發送版本查詢請求（圖中使用藍色的虛線箭頭顯示），尾節點將回傳被請求物件的已知版本號，然后，臟節點回傳與指定版本號相關聯的舊物件值（\(V_1\)），因此，即使有多個未完成的寫操作在鏈中傳播，鏈中的所有節點仍將回傳同一版本的物件，

當尾節點收到并接受寫入請求時，它會在鏈上發送包含此寫入版本號的確認訊息，每個前繼節點收到確認后，將此版本號標記為干凈（可能洗掉所有較舊的版本），當其最新的版本狀態變成干凈后，節點就可以在本地處理讀請求了，這種方式利用了寫操作是串行傳播的事實，因此尾節點總是最后一個收到寫入請求的節點，

CRAQ在以下兩種場景下吞吐量會比CR有所提升：

• Read-Mostly Workloads 該場景下大多數都是讀請求，這些讀取請求由\(C-1\)個非尾節點進行處理，因此，在這類場景下吞吐量與鏈長度\(C\)呈線性關系，
• Write-Heavy Workloads 該場景下有許多對非尾節點的大多數讀請求資料為臟，因此需要對尾節點進行版本查詢，但是，我們認為這些版本查詢并完整讀取更輕量，允許尾節點在它飽和之前以更高的速率處理它們，這使得總的讀取吞吐量仍高于CR，

第六節中的性能資料可以支持以上兩個主張，即使對于小物件也是如此，對于持續寫請求繁重的較長鏈，即使我們不評估這種優化，也可以想象通過使尾部結點僅處理版本查詢而不是處理所有的讀請求的方式，可以優化讀取吞吐量，

2.4 CRAQ上的一致性模型

某些應用程式或許可以以較弱的一致性保證來運行，并且它們可能會試圖避免版本查詢的性能開銷（根據3.3節，在廣域部署中是很重要的），或者它們可能希望當系統無法提供強一致性時繼續運行（例如在磁區期間），為了支持這類需求的變化，CRAQ同時支持三種不同的一致性模型，讀取操作使用哪一類一致性模型是可選的，

• 強一致性（默認）上面的模型中描述了強一致性，所有物件讀取都與最后一次提交的寫入一致，
• 最終一致性 允許對鏈中的節點的讀操作回傳已知的最新物件版本，因此，另一個點的后續讀取操作可能回傳比先前回傳的物件更舊的版本，因此，盡管對單個鏈節點的讀取操作的確在本地，但它不滿足單調讀一致性，
• 最大范圍不一致的最終一致性 允許讀操作在寫操作提交前將存盤的新物件回傳，但只允許在某些條件下這樣做，施加的條件可以基于時間或是基于絕對版本號，在該模型中，保證讀操作回傳的值具有最大的不一致性周期，如果鏈仍然是可用的，這種不一致性實際上是因為回傳的版本比上次提交的版本新，如果系統被磁區，并且節點無法參與寫入，那么版本可能比當前提交的版本舊，

2.5 CRAQ中的故障恢復

由于CRAQ的基本結構與CR相似，因此CRAQ使用相同的技術進行故障恢復，每個鏈節點需要知道它的前繼節點和后繼節點，以及鏈的頭部和尾部，當頭部節點故障了，它的后繼節點將接任新的鏈的頭部，同樣，當尾節點出現故障時，它的前繼節點也會接任成為新的尾節點，需要加入到鏈中間的節點要像雙鏈表一樣插入到兩個節點之間，處理系統故障的正確性證明與CR相似；由于篇幅所限，這里不展開說明，第5節介紹了CRAQ中故障恢復的細節以及協作服務的集成，特別是CRAQ允許節點加入到鏈中的任何位置（而不是僅在尾部），以及在恢復程序中正確處理故障的選擇都需要詳細介紹，

3. CRAQ的擴展

在本節中，我們討論應用程式如何在單資料中心以及跨多資料中心的條件下，設計CRAQ中鏈的布局方案，然后，我們討論如何使用協作服務來存盤鏈的元資訊和組成員身份資訊，

3.1 鏈布局策略

使用分布式存盤服務的應用程式的要求可能會有所不同，一些常見的情況如下：

• 對物件的大部分或全部的寫入操作可能源自單個資料中心
• 一些物件可能只存放在一個資料中心的某些節點中
• 熱點物件可能需要大量復制，而非熱點物件可能較少

CRAQ提供了靈活的鏈配置策略，通過使用物件的兩級命名結構來滿足這些變化的需求，物件的識別符號包括鏈識別符號和鍵識別符號，鏈識別符號決定CRAQ中的哪些節點將存盤該鏈中的所有鍵，而鍵識別符號為每條鏈提供唯一命名，我們介紹了多種滿足應用程式定制化需求的方法：

• 隱式資料中心和全域鏈長度：
  \(\{num\_datacenters，chain\_size\}\)

  該方法中定義了將存盤鏈的資料中心的數量，但未明確定義存盤在哪個資料中心，為了明確具體哪個資料中心存盤了鏈，使用一致性哈希結合唯一的資料中心識別符號，

• 顯式資料中心和全域鏈長度：
  \(\{chain\_size,dc_1,dc_2,\dots,dc_N\}\)

  該方法中每個資料中心使用同樣的鏈長度在資料中心中存盤副本，鏈的頭節點位于資料中心\(dc_1\)中，鏈的尾節點位于資料中心\(dc_N\)中，鏈基于資料中心串列進行排序，為了確定資料中心中的哪些節點存盤分配給鏈的物件，對鏈識別符號做一致性哈希，每個資料中心\(dc_i\)都有一個連接到資料中心\(dc_{i-1}\)尾節點的節點和一個連接到資料中心\(dc_{i+1}\)頭節點的節點，另一個額外的功能是允許\(chain\_size\)為0，表示該鏈使用每個資料中心內的所有節點，

• 顯式資料中心和不同鏈長度
  \(\{dc_1,chain\_size,\dots,dc_N,chain\_size_N\}\)

  這里每個資料中心的鏈長度是獨立的，這允許鏈負載均衡是非均勻的，每個資料中心的鏈節點的選擇方式與之前的方式相同，并且\(chain\_size\)也可以設定為0，

在上述方法2和方法3中，\(dc_1\)可以設定為主資料中心，如果一個資料中心是鏈的主資料中心，那么對于鏈的寫入將僅在短暫故障期間被該資料中心接受，否則，如果\(dc_1\)與鏈的其他節點斷開連接，則\(dc_2\)可能會成為新的頭節點，并接管寫操作，直到\(dc_1\)恢復在線，如果未設定主節點，寫操作將僅在包含全域鏈中大多數節點的磁區中繼續進行，否則，如第2.4節中定義的那樣，對于最大范圍不一致的讀取操作，該磁區會變成只讀，

CRAQ可以輕松支持其他更復雜的鏈配置方法，例如可能需要指定一個顯式備份資料中心，僅當另一個資料掛了的時候開始加入鏈中，還可以設定一組資料中心（例如東海岸資料中心），其中的任意一個都可以填充到上述方法2的有序串列中，為簡便起見，我們不再詳細介紹更復雜的方法，

可以寫入單個鏈的鍵識別符號的數量沒有限制，這樣可以根據應用需求對鏈進行靈活的配置，

3.2 單個資料中心中的CRAQ

在最初的鏈式復制作業中，已經研究了如何在多個資料中心分布多個鏈，在CRAQ的當前實作中，我們使用一致性哈希將鏈放置在資料中心內，將潛在的鏈識別符號映射到頭節點上，這類似于基于資料中心的物件存盤，GFS采用并在CR中推廣的另一種方式是在分配和存盤隨機鏈成員時，使用成員管理服務作為目錄服務，即每個鏈可以包含一些隨機服務器的集合，這種方式提高了并行系統恢復的能力，但是，這是以增加集中度為代價的，CRAQ可以輕松的使用這種設計，但是它將需要在協作服務中存盤更多的元資訊，

3.3 跨多個資料中心的CRAQ

當鏈延伸到廣域網時，CRAQ能夠從任何節點進行讀取的能力可以降低它的延遲：客戶端在選擇節點時具有靈活性，它們可以選擇物理距離較近的節點（或者輕負載的節點），只要鏈的狀態是干凈的，那么節點可以直接回傳本地副本的值，而不用發送任何廣域請求，而在傳統的CR中，所有讀取都需要由可能距離較遠的尾節點處理，實際上，由于物件可能處于不同的位置，因此多種設計可能會基于資料中心在鏈中選擇頭結點和/或尾節點，實際上雅虎的新分布式資料庫PNUTS就是受其資料中心中的高寫入區域性的影響而進行設計的，

也就是說應用程式可能會進一步優化廣域網下鏈的選擇，從而最大程度地減少寫入延遲，降低網路成本，當然，在所有節點集合中使用一致性哈希這種樸素的方式來構建鏈可能會導致鏈的前繼和后繼是隨機的，前繼和后繼可能距離很遠，此外，一條鏈可能會多次跨入和跨出一個資料中心，而通過我們的鏈優化，應用程式可以通過謹慎選擇組成鏈的資料中心的順序來最小化寫延遲，并且可以確保一條鏈只單向跨越資料中心的網路邊界一次，

即使使用優化后的鏈，隨著越來越多的資料中心被添加到鏈中，廣域網中的鏈的寫操作延遲也會增加，盡管與以并行方式分發寫操作的主/備方法相比，這種方式顯著地增加了延遲，但是它允許將寫操作在鏈中流水線進行，這極大的提高了寫操作的吞吐量，

3.4 ZooKeeper 協作服務

眾所周知，為分布式應用程式構建一個容錯的協作服務很容易出錯，CRAQ的早期版本包含一個非常簡單、集中控制的協作服務，用于維護成員管理，后來，我們選擇利用Zookeeper為CRAQ提供一種健壯的、分布式的、高性能的方式來管理組成員，并提供一種簡單的方式來存盤鏈的元資料，通過Zookeeper，當組內添加節點或洗掉節點時，CRAQ節點一定會收到通知，同樣當節點關注的元資料發送變化時，該節點也可以收到通知，

Zookeeper為客戶端提供類似于檔案系統的分層命名空間，檔案系統存盤在記憶體中，并且在日志中為每個Zookeeper實體進行備份，檔案系統狀態會在多個Zookeeper節點之間進行復制，從而提高可靠性和可擴展性，為了達成一致，Zookeeper使用類似兩階段提交的原子廣播協議，經過優化后，Zookeeper能夠為大量讀的小型作業負載提供出色的性能，因為它可以直接在記憶體中回應大部分的服務請求，

與傳統的檔案系統命名空間類似，Zookeeper客戶端可以羅列目錄的內容、讀取檔案、寫入檔案以及在檔案或目錄被修改或洗掉時收到通知，Zookeeper的原始操作允許客戶端實作許多更高級別的語意，例如組成員、領導選舉、事件通知、鎖和佇列，

跨多資料中心進行管理成員和鏈的元資訊的確帶來了一些挑戰，實際上，Zookeeper并未針對在多資料中心環境中運行進行優化：將多個Zookeeper節點放在單個資料中心，可以提高Zookeeper在該資料中心的讀取可擴展性，但是在廣域網下的性能會受損，因為原始實作并不知道資料中心的拓撲和層次結構，所以Zookeeper節點之間進行訊息交換會通過廣域網進行傳輸，盡管如此，我們當前的實作仍然確保了CRAQ節點總是能收到本地Zookeeper節點的通知，并且與它們相關的關于鏈和節點串列的訊息也會進行通知，我們在第5.1節使用Zookeeper進行了擴展，

為了消除Zookeeper在跨資料中心時產生的流量冗余，可以構建一個Zookeeper實體的層次結構：每個資料中心可以擁有自己本地的Zookeeper實體（由多個節點組成），并擁有一個全域Zookeeper實體的代表（可以通過本地實體的領導選舉選出），然后獨立的功能可以協調兩者之間的資料共享，一種替代設計是修改Zookeeper本身，就像CRAQ一樣讓節點知道網路拓撲結構，我們尚未重復研究這兩種方法，將其留給以后的作業，

4. 擴展

本節討論對CRAQ的一些其他擴展，包括微事務功能、使用多播優化寫操作，我們目前正在實作這些擴展，

4.1 CRAQ上的微事務

在一些應用程式中，對于物件存盤中的整個物件的讀/寫介面可能會受限，例如BitTorrent或其他目錄服務可能需要支持串列的添加或洗掉，分析服務可能需要存盤計數器，或者應用程式可能希望提供對某些物件的條件訪問，這些需求都不是僅僅提供純粹的物件存盤介面就可以滿足的，但是CRAQ提供了支持事務操作的關鍵擴展，

4.1.1 單鍵操作

單鍵操作很容易實作，CRAQ已經支持以下操作：

• 前置/追加： 將資料添加到當前物件值的開頭或結尾，
• 增加/減小： 在鍵的物件上增加或減少，以整數形式表示，
• 測驗并設定： 僅在鍵的當前版本號等于操作中執行的版本號時，才更新鍵的物件，

對于前置/追加和增加/減小操作，存盤鍵物件的鏈的頭節點可以簡單地將操作應用于物件的最新版本，即使最新的版本是不干凈的，然后在鏈中向后傳播替換寫操作，此外，如果這些操作很頻繁，則頭節點可以快取請求然后批量更新，如果使用傳統的兩階段提交協議，實作這些功能付出的代價會很高，

對于測驗并設定操作，鏈的頭節點檢查其最近提交的版本號是否等于操作中執行的版本號，如果沒有該物件最近未提交的版本，頭節點接受該操作并在鏈中傳播更新，如果有未完成的寫操作，則拒絕該操作，并且如果連續被拒絕，客戶端需要考慮降低請求速度，還有另一種方案，頭節點可以通過禁止寫入直到物件干凈為止并重新檢查最新的版本號來鎖定物件，但是由于未提交的寫入被中止是非常少見的，以及鎖定物件會顯著影響性能，因此我們選擇不采用該方案，

測驗并設定操作也可以設計為接受值而不是版本號，但是當存在未提交的版本時，會引入額外的復雜性，如果頭節點與物件的最新提交版本（通過與尾節點通信）比較發現不同，則當前進行中的任何寫入都將被拒絕，而如果頭節點與最新未提交版本比較，就違反了一致性保證，為了實作一致性，頭節點將需要通過禁止寫入直到物件干凈為止來暫時地鎖住物件，這不會違反一致性保證，并確保不會丟失任何更新，但是會顯著影響寫入性能，

4.1.2 單鏈操作

Sinfonia最近提出的“微事務”提供了一種具有吸引力方法，它能夠較為輕量地在單個鏈的多個鍵上執行事務，微事務由比較、讀取和寫入集合定義；Sinfonia提出了一種跨越多個記憶體節點的線性地址空間，比較集測驗指定地址位置的值，如果它們與提供的值匹配，則執行讀取和寫入操作，Sinfonia提出的微事務使用樂觀的兩階段提交協議，專為較低的寫爭用的情況而設計，準備訊息嘗試在指定的記憶體地址上獲取鎖，如果所有的地址都被鎖了，則協議提交；否則，參與者釋放所有的鎖并稍后重試，

CRAQ的鏈拓撲結構對于支持類似微事務有特殊的優勢，因為應用程式可以指定多個物件存盤在同一條鏈上，從而保持了區域性，共享同一個chainid的物件被分配在同一個鏈頭節點上，由于只有一個頭節點，因此可以避免在一次通信中發生兩階段提交，CRAQ的獨特之處在于，在涉及單個鏈的微事務中就可以僅使用頭節點來接受訪問，因為頭節點控制對鏈所有鍵的寫訪問，唯一的缺點就是如果頭節點需要等待事務中的所有節點變干凈（如4.1.1節所述），那么寫吞吐量會收到影響，但是這個問題在Sinfonia中更為嚴重，因為它需要等待跨多個節點的鍵解鎖，同樣，在CRAQ中從故障恢復也很容易，

4.1.3 多鏈操作

即使在多物件更新涉及到多個鏈時，樂觀兩階段提交協議也僅需使用鏈頭節點來實作，而不是所有涉及的節點，鏈頭節點可以鎖住任何微事務中涉及的鍵，直到事務完全提交為止，

當然，應用程式寫行程在使用昂貴的鎖和微事務時需要小心：由于寫同一個物件無法再流水線化執行（鏈式復制極其重要的優勢），CRAQ的寫吞吐量會被降低，

4.2 多播降低寫入延遲

CRAQ可以利用多播協議來提高寫入性能，特別是對于大規模的更新或是長鏈而言，由于鏈成員在節點成員修改期間是穩定的，因此可以為每個鏈創建一個多播組，在一個資料中心內，可以采用網路層多播協議的形式，而應用程式層多播可能更適用于廣域網中的鏈，這些多播協議不需要順序或可靠性保證，

然后，實際的值可以多播到整個鏈，而不是在鏈上順序傳播完整寫入，增加與鏈長度成正比的延遲，與此同時，只有較小的元資料資訊需要在鏈中傳播，以確保所有尾節點前的副本都能收到寫操作，如果節點因為任何原因而未收到多播的訊息，節點可以在接收到寫提交訊息之后和向下傳播提交訊息之前，與它的前繼節點進行通信獲取物件，

此外，當尾節點收到傳播的寫請求時，多播確認資訊可以發送到多播組中，而不是將其沿鏈向后傳播，這樣既減少了節點物件在寫入后等待重新進入干凈狀態的時間，又減少了客戶端感知的寫入延遲，同樣，在多播確認時不需要順序或可靠性保證——如果鏈中的節點沒收到確認訊息，它會在下一個讀取操作要求它查詢尾節點時重新進入干凈狀態，

標籤：其他

上一篇：哪種網頁鏈接對SEO友好？看這里

下一篇：基于opencv的車牌提取專案