使用Amazon雲系統保障存儲一致性

背景：Data Provenance

在CS學術領域有個術語叫做Data Provenance，有人翻譯為“數據世系”。實際上，就是一個文件的meta data，屬性信息。只不過這裡的屬性記錄得更加詳細，頗有些log的意味。簡單來說，就是“誰創建了它”、“誰對它做了什麼修改”、“數據流傳輸到了哪裡”等等一系列記錄。在我們的數據出現異常的時候，數據世系能幫助我們追溯根源，在程序debug、核實取證以及數據恢復上也都有着巨大用途。

例如，在電信網絡流量管理中，一些異常檢測工具能夠及時的發現網絡流量中的異常，但是這些工具並不能檢測出是什麼原因導致的異常，異常發生在哪裡？如果系統能夠追蹤流數據的世系，那麼用戶可以確定數據演化過程以及產生異常的原始流，定位並確定異常產生的原因。

問題來了，數據和對應的數據世系實際上是分離的，是兩份不同的文件。要滿足我們的需求，數據世系必須具有以下特點：

• 數據世系與數據的映射耦合。即數據世系要能夠精確無誤地描述數據，我們使用原子性和一致性來保障這個機制。原子性的意思是，在存儲期間，數據和數據世系必須同時存在，或同時不存在。一致性則表示在查詢時，數據必須與數據世系中的記錄保持一致。
• Causal Ordering。即事件發生的先後次序描述。如果B是改變A的某些數據後得到的結果，那麼A就存在（發生）在B之前，或者說A是B的前一個版本，因而A的數據世系是B的數據世系的子集。
• 獨立數據的持久性。假設A發生在B之前，如果A被刪除了，B的數據世系仍舊應該包含A的數據世系。
• 有效查詢。用戶想要驗證他們數據的屬性，數據世系應該能夠隨時提供高效的查詢結果。

這些在分布式系統中都是經典問題，特別是一致性和Ordering，有各種各樣的實現方式。我將在另一篇文章中詳細介紹相關理論。本篇所要描述的，是如果通過現有雲計算平台提供的服務來實現數據和數據世系存儲系統PASS（Provenance-Aware Storage System），更廣義地來看，其實是實現數據和元數據（data and its metadata）的存儲一致性。

使用Amazon雲服務實現數據世系

這裡會使用到三項Amazon Cloud服務：S3, SimpleDB, SQS。S3是已經介紹過的雲端存儲，SimpleDB是一套基於key-value型的數據庫服務，SQS是一種分布式排隊服務。

1. 僅使用S3來實現

僅使用S3的系統結構

僅使用S3的協議

S3可以支持最大5GB的數據存儲，並提供SOAP和REST接口。使用S3可以保證最終一致性Eventual consistency和causal ordering。但如果客戶端程序在上傳了數據世系後崩潰，S3中就僅有數據世系而沒有對應的數據，系統就失去了原子性。另外，數據查詢是低效的，因為我們無法通過單獨的數據世系來獲取對應數據。

2. 使用S3 + SimpleDB實現

SimpleDB的數據存儲為name-value對的形式，並最多支持256個attributes。在SimpleDB中，數據世系被表示為數據庫條目，例如

ItemName=uuid1_2
attribute-name=name,attribute-value=foo
attribute-name=input,attribute-value=bar_2
attribute-name=type,attribute-value=file

使用S3 + SimpleDB的系統結構

S3 + SimpleDB的協議

這種方式支持了causality ordering，並且查詢效率高。不過原子性仍然沒有保證。

3. 使用S3 + SimpleDB + SQS實現

SQS是一個分布式消息隊列系統，隊列以URL作標識，它支持SendMessage, ReceiveMessage, DeleteMessage操作。不過SQS僅支持8KB的消息隊列大小。

S3 + SimpleDB + SQS的系統結構

S3 + SimpleDB + SQS的協議

SQS和本地Log日誌不同，如果本地log損壞了，所有的記錄都會丟失。而SQS將記錄保存在雲端，具有健壯性。如果commit進程崩潰，我們仍然可以啟動另一個commit進程並執行剩下的事務操作。

上圖中S3 + SimpleDB + SQS這個協議執行過程分為兩大步，這裡詳細解釋一下：

步驟一Log: 將數據記錄在隊列中
1. 上傳數據到S3中，作為一個臨時存儲副本。
2. 分配一個事務ID (uuid)
3. 將數據世系分割為8KB的數據塊，並加入到SQS隊列中。為每個隊列消息加上uuid標籤，然後增加一條指向S3中臨時數據的記錄。

步驟二Commit: 將數據從隊列傳到S3和SimpleDB中
1. ReceiveMessage: 從隊列中獲取消息並組裝數據包
2.調用PutAttributes操作，將數據世系存儲到 SimpleDB中
3. 執行S3 COPY操作，將數據從臨時存儲複製出來，永久存儲。
4. 從SQS隊列中刪除消息
5. 從S3中刪除臨時數據

三種方式的比較

圖表說明一切

P1 = S3
P2 = S3 + SimpleDB
P3 = S3 + SimpleDB + SQS

註：本文部分內容編譯自哈佛大學Muniswamy-Reddy的論文Provenance for the Cloud