CRAQ論文筆記

Object Storage on CRAQ（使用配置設定查詢的鍊式複制）

High-throughput chain replication for read-mostly workloads（對于讀高負載的高吞吐鍊式複制）

論文位址：https://pdos.csail.mit.edu/6.824/papers/craq.pdf

一、介紹

• CRAQ的目标是在提供高讀吞吐時同時還提供強一緻性的保證，同時在某些未送出操作下，提供弱一緻性的保證。
• 讨論跨資料中心的地域複制優化、多對象更新、對大對象的多點傳播優化更新

二、基本系統模型

2.1 接口和一緻性模型

• 對象存儲系統提供兩個操作原語
  1. write(objID, V): 寫操作存儲與objID相關的value值
  2. V←read(objID): 讀操作擷取與objID相關的值
• 一緻性
  1. 強一緻性保證對一個對象的讀寫都是按順序進行，并且總是看到最新的值
  2. 最終一緻性意味着單個對象寫操作會被順序應用在所有節點，但是對不同節點的最終一緻讀可能傳回混亂的資料在某些不一緻的時段（例如在寫被實施到所有節點以前）。一旦所有副本接受寫操作，讀取操作将不會擷取到更舊的版本資料。如果一個用戶端與某個節點維持會話，那麼它總是可以看到單調的讀一緻。

2.2 鍊式複制（Chain Replication -> CR）

       鍊式複制是一種複制資料的方法，它跨越多個提供強一緻性存儲接口的節點。節點形成長度為C的鍊，寫請求隻能由頭節點處理，讀請求由尾部節點處理。當用戶端發送一個寫請求時，頭節點接收并處理完成以後傳播到後繼節點，然後到達尾部節點，尾部節點處理完成後再傳回ACK處理成功的消息給前驅節點，依次到達頭部節點，頭部節點傳回處理成功給用戶端。當用戶端發送一個讀請求，尾部節點接收并傳回資料。

2.3 配置設定查詢的鍊式複制（Chain Replication with Apportioned Queries -> CRAQ）

       受高讀負載場景的啟發，CRAQ尋求一個通過允許任意節點處理讀請求來提高讀吞吐量，并且還提供強一緻性的保證。

以下是CRAQ的主要擴充

• 在CRAQ中的節點可以存儲對象的不同版本，每個對象都包括單調自增的版本号和額外的版本的屬性，版本是 clean 或者 dirty，所有的版本最初标記是clean。
• 當一個節點接收到一個對象的新版本時，此節點增加最新版本到它的版本清單當中。
  1. 如果此節點不是尾節點，節點标記版本為dirty并且傳播到後繼節點
  2. 如果此節點是尾節點，節點标記版本為clean，同時我們稱此對象版本為已送出。尾節點然後可以通過反向傳播通知其它節點ACK送出資訊。
• 當ACK送出資訊到達某個節點，此節點标記對象版本為clean，然後此節點就可以删除這個對象以前的版本。
• 當一個節點接收到某對象的讀請求：
  1. 如果請求對象的最新版本是clean，則傳回它的值。
  2. 否則，如果對象最新版本是dirty，此節點聯系尾節點查詢對象的最新送出版本。節點然後傳回對象的最新版本。按結構，節點保證存儲此對象的版本。我們注意到盡管尾部可以送出一個新版本在它傳回版本查詢請求和内部節點發送一個響應給用戶端之間，這樣也不和我們的強一緻性定義沖突（讀操作相對尾節點是序列化的）。
• CRAQ的吞吐量高于CR，在兩個不同場景
  1. 讀負載較高的場景下，多數的讀請求都發生在非尾部節點，是以在此場景下吞吐量是線性增加的。
  2. 寫負載較高場景下，多數讀請求都是請求dirty的版本對象，是以需要向尾部查詢版本。我們認為這些比起尾部節點接收全查詢的負擔要小很多，是以尾部節點可以在飽和以前以更高的速度處理查詢請求。總的來說，CRAQ讀吞吐量仍然要比CR要高。

2.4 CRAQ中的一緻性模型

CRAQ支援三種一緻性模型：

1. 強一緻性：查詢的所有對象保證是最新的值
2. 最終一緻性：對一個對象的讀取可能會讀取到舊的值，是以這不能滿足單調一緻的讀取（但是在跟單個節點保持會話是可以的）
3. 含有最大界限不一緻的最終一緻性：查詢操作得到的值的一緻性可能會有某種限度，一種是基于時鐘，一種是基于版本