Windows Azure Storage (WAS) 是微軟提供的支持多種數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)云服務(wù)系谐，本文是 Windows Azure Storage: a highly available cloud storage service with strong consistency 論文閱讀筆記盏混，記錄閱讀論文的感受和啟發(fā)。

Global Partitioned Namespace

namespace 定義了數(shù)據(jù)的訪問方式许赃，包括 AccountName止喷、PartitionName 和 ObjectName 三個(gè)部分。不同的數(shù)據(jù)結(jié)構(gòu)的名字訪問方式有所不同：

• Blob：PartitionName 對(duì)應(yīng)每一個(gè) blob 文件
• Table: PartitionName + ObjectName 對(duì)應(yīng) table 每一行
• Queue: PartitionName + ObjectName 對(duì)應(yīng) queue 每一個(gè) message

整體架構(gòu)

WAS 組件

整體架構(gòu)

WAS 架構(gòu)組件包括 Location Service 和若干 Storage Stamp弹谁，而 Storage Stamp 由可以劃分為 Front Ends预愤、Partition Layer 和 Stream Layer 三層咳胃。

Location Service

Location Service (LS) 管理所有的 storage stamp 及其 namespace，自身通過部署在不同地域?qū)崿F(xiàn)災(zāi)難恢復(fù)销睁。
LS 具備添加新的 region存崖、添加 location 到已有 region 以及添加 stamp 到已有 location 的能力。當(dāng)用戶請(qǐng)求一個(gè)寫入賬戶時(shí)冗栗，LS 在用戶指定的 location 內(nèi)根據(jù)磁盤供搀、網(wǎng)絡(luò)等負(fù)載情況選擇選擇合適的 storage stamp 提供服務(wù)葛虐，并更新相應(yīng)的路由信息。

Storage Stamp

一個(gè) storage stamp 是包括 N 個(gè)物理機(jī)架的存儲(chǔ)節(jié)點(diǎn)集群乒融，每個(gè)機(jī)架是一個(gè) fault domain，使用獨(dú)立的網(wǎng)絡(luò)和電力愧捕。fault domain 這個(gè)概念在 WAS 中很重要申钩，在 WAS 滾動(dòng)升級(jí)和復(fù)制等重要功能中也要發(fā)揮作用撒遣。為了利用 HDD 的 outer track 更快的訪問性能，從而得到更好的磁盤尋道時(shí)間和訪問吞吐量义黎，通常一個(gè) storage stamp 會(huì)保留 20% 的磁盤空間廉涕。

Stream Layer

stream layer 是一個(gè)類似于分布式文件系統(tǒng)的組件，提供類似文件系統(tǒng)的 namespace 和 API宠纯，不過所有的寫都是 append-only 的形式层释。

stream layer

Stream Layer Architecture

stream layer architechture

從組件構(gòu)成來看妖碉，stream layer 主要包括 Stream Manager (SM) 和 Extent Node (EN)。

Stream Manager

SM 是一個(gè)標(biāo)準(zhǔn)的 Paxos 集群坐榆，在用戶請(qǐng)求的關(guān)鍵路徑外冗茸，包括以下功能：

1. namespace 和活躍 stream/extent 的狀態(tài)維護(hù)
2. 監(jiān)控 EN 的健康狀態(tài)
3. 創(chuàng)建/分配 extent 到 EN
4. 惰性執(zhí)行由于硬件故障導(dǎo)致的數(shù)據(jù)再?gòu)?fù)制
5. 垃圾 extent 回收
6. 調(diào)度糾刪編碼任務(wù)

當(dāng)任意一個(gè) extent 副本數(shù)少于預(yù)期數(shù)量時(shí)夏漱，SM 會(huì)發(fā)起數(shù)據(jù)的再?gòu)?fù)制，在相同數(shù)據(jù)的副本分布在不同的 fault domain 的原則下屎篱，隨機(jī)選擇 EN 分配新的 extent葵蒂。由于數(shù)據(jù)寫入請(qǐng)求通常需要頻繁地分配新的 block践付，為了避免 SM 成為寫請(qǐng)求的關(guān)鍵路徑，SM 只關(guān)心 stream 和 extent隧土，并不理解 block 這一概念，如此也能夠?qū)?SM 占用的資源限制在一個(gè)較小的范圍內(nèi)关贵。

Extent Node

EN 管理 extent 的副本卖毁，每個(gè) extent 在 EN 上對(duì)應(yīng)的物理形式是一個(gè)文件亥啦，存儲(chǔ)若干個(gè) block 和保存每個(gè) block 對(duì)應(yīng)的文件偏移的 index。EN 在內(nèi)存中保存有其所有的 extent 的副本信息奴拦，這也是構(gòu)成 SM 管理的全局狀態(tài)信息的一部分届吁。EN 與其他節(jié)點(diǎn)通信主要完成兩個(gè)任務(wù)：復(fù)制寫操作到數(shù)據(jù)對(duì)應(yīng)的副本疚沐；按照 SM 的指令創(chuàng)建已有數(shù)據(jù)的副本。

Append Operation and Sealed Extent

stream 支持多個(gè) block 以原子操作的形式執(zhí)行 append痴施。若因?yàn)楣收暇苛鳌⒊瑫r(shí)等原因?qū)е驴蛻舳宋词盏綌?shù)據(jù)寫入確認(rèn)芬探，客戶端通常需要進(jìn)行重試操作。而重試操作通常會(huì)導(dǎo)致重復(fù)數(shù)據(jù)條目哩簿。作為 stream layer 的客戶端炎疆，partition layer 針對(duì)不同的數(shù)據(jù)采取不同的處理方式：

1. 針對(duì) metadata stream 和 commit log stream形入，每個(gè)寫入的記錄會(huì)有一個(gè)唯一的單調(diào)遞增的序號(hào)缝左，這里的 metadata stream 可以理解成是 LSM-tree 中的 manifest 文件，而 commit log stream 則對(duì)應(yīng) LSM-tree 中的 WAL 文件蛇数，可以通過以增量日志的方式保存數(shù)據(jù)耳舅。在重新啟動(dòng)等需要再次加載數(shù)據(jù)的場(chǎng)景下，唯一的序號(hào)可以避免不必要的操作重復(fù)執(zhí)行馏予。
2. 針對(duì) table 行數(shù)據(jù)和 blob 數(shù)據(jù)流盔性，由于寫入的最小單位是 block冕香，只有最終寫入成功的 block 才會(huì)被引用，之前的重復(fù)寫入由于無任何引用屬于垃圾數(shù)據(jù)突那，會(huì)被 SM 發(fā)現(xiàn)后進(jìn)行垃圾回收焕襟。
   extent 有一個(gè)客戶端指定的目標(biāo)大小鸵赖，超過這一大小后該 extent 就被封存不再接受寫入。新的 extent 將會(huì)被創(chuàng)建并添加到 stream 中饵骨，接收該 stream 的寫入茫打。

Intra-Stamp Replication

Intra-Stamp Replication 是 stream layer 提供的同步復(fù)制機(jī)制老赤，保證數(shù)據(jù)的持久性。該復(fù)制機(jī)制確保數(shù)據(jù)在不同的 fault domain 中有足夠的副本弊予，主要用于避免單個(gè) fault domain 出現(xiàn)的硬件故障开财。由于是同步復(fù)制赠堵，因此該復(fù)制位于用戶寫請(qǐng)求的關(guān)鍵路徑上，任意副本的寫入失敗都會(huì)導(dǎo)致用戶寫請(qǐng)求異常嘀略。
為了實(shí)現(xiàn)對(duì)象級(jí)別的強(qiáng)一致乓诽，Intra-Stamp Replication 提供如下保證：

1. 一旦數(shù)據(jù)寫入成功并返回，從任意副本均可讀取到一樣的數(shù)據(jù)
2. 一旦 extent 歸檔后逮壁，從任意副本均只會(huì)讀取到一樣的 extent 內(nèi)容

數(shù)據(jù)復(fù)制流程

全新 stream 創(chuàng)建流程：

1. SM 為 stream 的第一個(gè) extent 分配3個(gè)副本窥淆，隨機(jī)選擇分布在不同的 fault domain 和 upgrade domain 的機(jī)器巍杈；
2. SM 選擇某一個(gè)副本作為 primary extent筷畦，用于協(xié)調(diào)數(shù)據(jù)在從節(jié)點(diǎn)的寫入。通常而言吼砂，primary extent 數(shù)量在機(jī)器之間盡量做到均勻以均衡負(fù)載鼎文。在 extent 未歸檔之前拇惋，任何角色的副本位置都不會(huì)改變；
3. 副本的位置和角色信息以元信息的形式保存在 SM 上蓉坎，并在創(chuàng)建 stream 的請(qǐng)求響應(yīng)中返回給客戶端蛉艾，客戶端將緩存這些信息。如此，可以降低數(shù)據(jù)寫入對(duì)于 SM 的依賴罐监。

數(shù)據(jù)寫入流程：

1. 客戶端向 primary extent 發(fā)起數(shù)據(jù) append 操作瞒爬；
2. primary extent 確定新數(shù)據(jù)的寫入位置(offset)侧但，在此過程中可能需要對(duì)并發(fā)的寫入請(qǐng)求進(jìn)行排序；
3. primary extent 將寫入請(qǐng)求發(fā)送到 secondary 副本屁药；
4. 當(dāng)所有副本 append 操作成功持久化到磁盤后酿箭，向客戶端返回成功趾娃。所有副本都 commit 成功的 offset 稱之為 current commit length。
   primary extent 在指定后就保持不變妇蛀，而 append 的操作寫入位置和順序由 primary extent 決定评架，且在 append 出現(xiàn)錯(cuò)誤后對(duì) extent 副本進(jìn)行歸檔炕泳，由此我們可以認(rèn)為副本間的數(shù)據(jù)在比特級(jí)別保持一致喊崖。

數(shù)據(jù)寫入失敗處理流程：

1. 客戶端寫入失敗，此時(shí) extent 副本所在的部分 EN 可能不可達(dá)或發(fā)生磁盤故障茁裙；
2. 客戶端通知 SM 某個(gè) stream 寫入失斘钭丁；
3. SM 歸檔發(fā)生故障的當(dāng)前活躍的 extent女轿；
4. SM 在可用的 EN 上分配新的 extent壕翩，并返回給客戶端放妈；
5. 客戶端開始在新的 extent 上寫入；
6. SM 為之前歸檔的 extent 創(chuàng)建新的副本珍策，保證符合期望的數(shù)據(jù)副本數(shù)量攘宙。

extent 歸檔

SM 負(fù)責(zé)所有 extent 的歸檔操作拐迁。一旦歸檔操作完成后唠亚，commit length 不會(huì)再改變。在歸檔過程中祟蚀，SM 需要根據(jù)副本的 commit length 確定最終歸檔的 commit length：

1. 如果所有副本 commit length 均相等前酿，那么最終 extent 的 commit length 就等于該值
2. 如果因?yàn)椴糠指北静豢捎脤?dǎo)致 append 錯(cuò)誤鹏溯，從而導(dǎo)致副本 commit length 不完全相等丙挽，SM 選取最小的 commit length 作為最終的 commit length。這里我們簡(jiǎn)單展開一下討論平窘，我們假定最小的 commit length 為 cl0瑰艘，最大的 commit length 為 cl1。由于 Intra-Stamp Replication 是同步復(fù)制均蜜，那么 cl0 和 cl1 之間的數(shù)據(jù)意味著他們只會(huì)在部分副本上 append 成功囤耳，而 pending 在未寫入成功的 extent 上敲董，不會(huì)返回成功給客戶端腋寨。因此化焕，可以選擇 cl0 作為 commit length撒桨，并返回給客戶端已經(jīng)成功寫入的數(shù)據(jù)數(shù)量凤类，讓客戶端根據(jù)部分寫入情況進(jìn)行重試。

歸檔 extent 的糾刪編碼

為降低存儲(chǔ)成本佃延，利用 歸檔 extent 的不變性夷磕，WAS 對(duì)歸檔的 extent 進(jìn)行糾刪編碼坐桩，可將存儲(chǔ)空間占用從3副本的3倍磁盤空間下降到1.3-1.5倍。在一個(gè) stamp 內(nèi)膘螟，更增強(qiáng)了數(shù)據(jù)持久化能力萍鲸。不過應(yīng)當(dāng)看到的是擦俐，經(jīng)過糾刪編碼的數(shù)據(jù)讀取時(shí)的開銷相對(duì)于原數(shù)據(jù)更大。在部分延時(shí)敏感的讀場(chǎng)景下品擎，可采取將糾刪編碼后的數(shù)據(jù)進(jìn)行重建得到原數(shù)據(jù)的方式加速訪問备徐，類似于 RocksDB 的 uncompressed block cache 機(jī)制蜜猾。

避免自旋導(dǎo)致 IO 饑餓

HDD 通常傾向于達(dá)到最大吞吐量蹭睡，犧牲調(diào)度的公平性。當(dāng)磁盤應(yīng)付大數(shù)據(jù)量的連續(xù)數(shù)據(jù)讀取時(shí)脊串，其他非連續(xù)數(shù)據(jù)讀取可能會(huì)受到顯著影響琼锋，延時(shí)可能高達(dá)2300ms祟昭。WAS 為了規(guī)避這一問題篡悟，采用了新的磁盤調(diào)度策略保證調(diào)度的公平性恰力。對(duì)于需要面對(duì)多租戶的應(yīng)用場(chǎng)景的云服務(wù)來說，公平性是非常重要的停局。

1. 當(dāng)有已經(jīng)被調(diào)度的 IO董栽，被調(diào)度之前 pending 時(shí)間超過100ms時(shí)企孩，不再調(diào)度新的 IO 進(jìn)入自旋狀態(tài)勿璃；
2. 當(dāng)有已經(jīng)被調(diào)度的 IO，被調(diào)度后超過 200ms 未得到響應(yīng)歹撒，不再調(diào)度新的 IO 進(jìn)入自旋狀態(tài)诊胞。

持久化和 journal

WAS 的持久化通過同步復(fù)制寫入到至少3個(gè)位于不同的 fault domain 的副本完成撵孤。為了實(shí)現(xiàn)寫入高性能邪码，使用單獨(dú)的整磁盤作為 journal device。由于 journal 通常是順序?qū)懭敫馊停梢猿浞掷迷O(shè)備的 IO 帶寬。使用高性能的 journal device斧拍，寫入流程可以做如下優(yōu)化：

1. 寫入所有待 append 的數(shù)據(jù)到 journal device肆汹，同時(shí)在 cache 中緩存數(shù)據(jù)副本予权。當(dāng)寫入 journal device 完成后扫腺，即可返回寫入成功。在數(shù)據(jù)盤寫入成功前攒至，用戶對(duì)于這部分的數(shù)據(jù)讀取請(qǐng)求都由 cache 負(fù)責(zé)迫吐；
2. 提交待 append 的數(shù)據(jù)到數(shù)據(jù)盤的寫入隊(duì)列中志膀，由于 journal device 是順序?qū)懀覕?shù)據(jù)盤的性能通常會(huì)差一些奇颠，數(shù)據(jù)盤的寫入請(qǐng)求通常需要排隊(duì)等待烈拒。數(shù)據(jù)落盤成功后荆几，數(shù)據(jù)請(qǐng)求則可交由磁盤負(fù)責(zé)赊时。

采用單獨(dú)的 journal device 是一個(gè)簡(jiǎn)單粗暴的提升性能的方法吨铸，可根據(jù) journal 的數(shù)據(jù)寫入特點(diǎn)，選擇適用的專門設(shè)備祖秒。

Partition Layer

Partition Layer 主要提供數(shù)據(jù)類型抽象诞吱、數(shù)據(jù)類型對(duì)應(yīng)的操作、可擴(kuò)展的 namespace竭缝、對(duì)象訪問的負(fù)載均衡以及對(duì)象訪問的事務(wù)排序和強(qiáng)一致性房维。

Partition Layer Architecture

Partition Layer Architecture

Partition Manger (PM)

PM 負(fù)責(zé)將 Object Table 劃分為若干個(gè) RangePartition，分配到 PS 中抬纸，并將 RangePartition 與 PS 的對(duì)應(yīng)關(guān)系記錄在 Partition Map Table 中。PM 保證每個(gè) RangePartition 只會(huì)分配給一個(gè) PS湿故，并 RangePartition 相互之間不會(huì)重疊阿趁。PM 是一個(gè)有多個(gè)實(shí)例的無狀態(tài)的服務(wù)，通過 Lock Service 選擇主節(jié)點(diǎn)坛猪，在任期內(nèi)負(fù)責(zé) partition layer 的管控脖阵。

Partition Server (PS)

PS 負(fù)責(zé)響應(yīng)若干個(gè) RangePartition 的請(qǐng)求∈裕基于 Lock Service 的 lease 機(jī)制命黔，在任意時(shí)刻只會(huì)有一個(gè) PS 為一個(gè) RangePartition 服務(wù)。

當(dāng)出現(xiàn) PS 不可用時(shí)躁锁，該 PS 負(fù)責(zé)的所有 RangePartition 會(huì)被 PM 遷移到其他的 PS 上纷铣，在這過程中會(huì)考慮 PS 的負(fù)載情況。

RangePartition 數(shù)據(jù)結(jié)構(gòu)

RangePartition 數(shù)據(jù)結(jié)構(gòu)

每個(gè) RangePartition 可以看作是一個(gè) LSM-tree 數(shù)據(jù)結(jié)構(gòu)战转，可以方便地使用 RocksDB 的概念來進(jìn)行類比搜立。

1. metadata stream：記錄 commit log 和 data stream 信息。當(dāng)發(fā)生 split 和 merge 操作時(shí)槐秧，metadata stream 也要相應(yīng)更新啄踊。作用類似于 RocksDB 的 manifest 文件忧设。
2. commit log stream: 記錄最近的 checkpoint 以來的操作日志。作用類似于 RocksDB 的 WAL 文件颠通。
3. row data stream：保存已經(jīng)持久化的數(shù)據(jù)和索引址晕。作用類似于 RocksDB 的 SST(Sorted Strings Table) 文件。
4. blob data stream：專用于 blob table 數(shù)據(jù)存儲(chǔ)顿锰。
5. memory table: commit log stream 的內(nèi)存鏡像谨垃。一個(gè)查詢通常會(huì)先查詢 memory table，再查詢 data stream硼控。
6. index cache: 緩存持久化的 index 數(shù)據(jù)刘陶，與 row data cache 獨(dú)立是為了盡可能多地緩存 index。作用類似于 RocksDB 的 table cache牢撼。
7. row data cache: row data page 的緩存匙隔，由于 row data stream 是只讀的，所以不需要考慮數(shù)據(jù)更新熏版，只需考慮數(shù)據(jù)的淘汰纷责。類似于 RocksDB 的 block cache，可以有 LRU撼短、Clock 等淘汰策略再膳。

數(shù)據(jù)流

RangePartition 的與常規(guī)的 LSM-tree 需要特別指出的是，在 blob data 這種單個(gè) value 較大的的場(chǎng)景阔加，為了避免 commit log stream 和 data stream 的重復(fù)寫饵史，在寫入過程中只執(zhí)行 commit log stream 的寫入满钟，只在 data stream 中記錄相應(yīng)的 commit log stream 的指針胜榔。在 checkpoint 過程中，通過對(duì) commit log stream 底層的 extent 進(jìn)行重組得到最終的 blob data stream湃番。

RangePartition 負(fù)載均衡

PM 會(huì)出于負(fù)載均衡的目的執(zhí)行以下3種操作：

1. Load Balence：根據(jù) PS 負(fù)載情況夭织，對(duì) RangePartition 進(jìn)行再分配
2. Split：對(duì)負(fù)載過重的單個(gè) RangePartition 進(jìn)行拆分
3. Mege：對(duì)負(fù)載較輕的相鄰的 RangePartition 進(jìn)行合并

Load Balance

評(píng)估 RangePartition 的負(fù)載情況主要通過以下幾個(gè)指標(biāo)：

1. transaction/second
2. transaction 平均掛起時(shí)間
3. 限速速率
4. CPU 使用率
5. 網(wǎng)絡(luò)使用率
6. 請(qǐng)求延遲
7. 磁盤數(shù)據(jù)大小
   PM 維護(hù)與每個(gè) PS 的心跳信息，RangePartition 的負(fù)載情況在心跳信息中反饋給 PM吠撮。若 PM 發(fā)現(xiàn)某個(gè) RangePartition 負(fù)載過高時(shí)尊惰，PM 會(huì)對(duì) RangePartition 進(jìn)行 split 操作；當(dāng) PM 發(fā)現(xiàn)某個(gè) PS 負(fù)載過高時(shí)泥兰，PM 會(huì)發(fā)起 RangePartition 遷移弄屡。

Split Operation

PM 根據(jù) RangePartition 的負(fù)載和 data stream 的數(shù)據(jù)量決定是否執(zhí)行 split 操作，split 操作最重要的就是選擇 key ( AcountName + PartitionName):

1. 基于 data stream 數(shù)據(jù)量的 split鞋诗，PM 選擇使得可以使得 RangePartition 被近似切分成兩等份的 key膀捷；
2. 基于負(fù)載的 split，PS 動(dòng)態(tài)統(tǒng)計(jì)負(fù)載最重的 key 區(qū)間削彬，并以此來選擇切分的 key全庸。
   split 的流程如下：
3. PM 命令 PS 對(duì) RangeParitiion B 執(zhí)行 split 操作秀仲，分為 C 和 D；
4. 負(fù)責(zé) B 的 PS 執(zhí)行 checkpoint壶笼，然后 B 停止對(duì)外服務(wù)神僵；
5. PS 為 C 和 D 創(chuàng)建新的 stream。這一步可以很快覆劈，因?yàn)?stream 只是 extent 的指針集合保礼；
6. PS 恢復(fù) C 和 D 對(duì)外服務(wù)；
7. PS 通知 PM split 完成责语，PM 更新 Partition Map Table 及元信息氓英。通常，PM 會(huì)遷移 C 或 D 到另一個(gè) PS 上鹦筹。

Merge Operation

PM 會(huì)選擇兩個(gè)相鄰的負(fù)載較低的 PartitionName 區(qū)間的 PartitionRange 進(jìn)行合并：

1. PM 遷移 C 和 D 到相同的 PS 上铝阐，并通知 PS 合并 C 和 D；
2. PS 為 C 和 D 分別執(zhí)行 checkpoint 操作铐拐，然后停止他們的對(duì)外服務(wù)徘键；
3. PS 為 E 創(chuàng)建 stream，新的 commit log stream 和 data stream遍蟋，都是按照先 C 后 D 的順序排列 extent吹害；
4. PS 根據(jù)新的 commit log stream 和 data stream 構(gòu)建新的 metadata stream；
5. E 重新加載 meta stream虚青，開始對(duì)外提供服務(wù)它呀；
6. PM 更新 Partition Map Table 及元信息；

Partition Layer Inter-Stamp Replication

對(duì)于每個(gè)賬戶而言棒厘，LS 分配一個(gè) primary stamp 和多個(gè) secondary stamp纵穿。為了實(shí)現(xiàn) 數(shù)據(jù)中心級(jí)別的災(zāi)難恢復(fù)，通過 geo-replication奢人，WAS 在一個(gè) account 的不同 stamp 之間執(zhí)行 Inter-Stamp Replication谓媒。Inter-Stamp Replication 是一種異步復(fù)制的機(jī)制，在災(zāi)難恢復(fù)過程中何乎，最近的數(shù)據(jù)可能會(huì)丟失句惯。另外，Inter-Stamp Replication 也可用于數(shù)據(jù)的遷移支救。

后記

WAS 是我完成的第二篇論文閱讀筆記抢野。論文閱讀是一個(gè)費(fèi)時(shí)費(fèi)力的過程。對(duì)于系統(tǒng)設(shè)計(jì)的文章各墨，涉及內(nèi)容多指孤、范圍廣，常驚嘆于頂層設(shè)計(jì)之精妙欲主，時(shí)沉靜細(xì)節(jié)考慮之優(yōu)雅邓厕。由于內(nèi)容較多逝嚎，形成一個(gè)總體意義上的結(jié)論，對(duì)于初出茅廬的我而言還尚有些吃力详恼。因而补君，論文閱讀筆記難免淪為論文翻譯。在本次閱讀過程中昧互，我嘗試了將論文打印下來挽铁，先進(jìn)行部分注解，再來撰寫論文讀書筆記的形式敞掘，相較之前還是有顯著的效果叽掘。

參考文獻(xiàn)

Windows Azure Storage: a highly available cloud storage service with strong consistency
WiscKey: Separating Keys from Values in SSD-Conscious Storage