Windows Azure Storage (WAS) 是微软提供的支持多种数据结构的存储云服务，本文是 Windows Azure Storage: a highly available cloud storage service with strong consistency 论文阅读笔记，记录阅读论文的感受和启发。

Global Partitioned Namespace

namespace 定义了数据的访问方式，包括 AccountName、PartitionName 和 ObjectName 三个部分。不同的数据结构的名字访问方式有所不同：

• Blob：PartitionName 对应每一个 blob 文件
• Table: PartitionName + ObjectName 对应 table 每一行
• Queue: PartitionName + ObjectName 对应 queue 每一个 message

整体架构

WAS 组件

整体架构

WAS 架构组件包括 Location Service 和若干 Storage Stamp，而 Storage Stamp 由可以划分为 Front Ends、Partition Layer 和 Stream Layer 三层。

Location Service

Location Service (LS) 管理所有的 storage stamp 及其 namespace，自身通过部署在不同地域实现灾难恢复。
LS 具备添加新的 region、添加 location 到已有 region 以及添加 stamp 到已有 location 的能力。当用户请求一个写入账户时，LS 在用户指定的 location 内根据磁盘、网络等负载情况选择选择合适的 storage stamp 提供服务，并更新相应的路由信息。

Storage Stamp

一个 storage stamp 是包括 N 个物理机架的存储节点集群，每个机架是一个 fault domain，使用独立的网络和电力。fault domain 这个概念在 WAS 中很重要，在 WAS 滚动升级和复制等重要功能中也要发挥作用。为了利用 HDD 的 outer track 更快的访问性能，从而得到更好的磁盘寻道时间和访问吞吐量，通常一个 storage stamp 会保留 20% 的磁盘空间。

Stream Layer

stream layer 是一个类似于分布式文件系统的组件，提供类似文件系统的 namespace 和 API，不过所有的写都是 append-only 的形式。

stream layer
stream layer 管理若干 stream，每个 stream 包括若干个 extent，每个 extent 包含若干个 block。每个 stream 最新的 extent 是可写的，其余都是只读的。
block 是读写的基本单位，每个 block 保存了数据的 checksum。block 数据的验证在每次数据读取和定期数据扫描时都会触发。extent 是 Intra-Stamp Replication 的基本单位。 stream 对上层（partition layer）的表现类似于一个大文件，仅支持追加写，但可支持随机读。stream 实际上是若干个排好序的 extent 指针，因此可以通过从已存在的 stream 中选取 extent 进行组合构建新的 stream。这与 WiscKey 中减小 LSM-tree 写放大的思路颇为相似。

Stream Layer Architecture

stream layer architechture

从组件构成来看，stream layer 主要包括 Stream Manager (SM) 和 Extent Node (EN)。

Stream Manager

SM 是一个标准的 Paxos 集群，在用户请求的关键路径外，包括以下功能：

1. namespace 和活跃 stream/extent 的状态维护
2. 监控 EN 的健康状态
3. 创建/分配 extent 到 EN
4. 惰性执行由于硬件故障导致的数据再复制
5. 垃圾 extent 回收
6. 调度纠删编码任务

当任意一个 extent 副本数少于预期数量时，SM 会发起数据的再复制，在相同数据的副本分布在不同的 fault domain 的原则下，随机选择 EN 分配新的 extent。由于数据写入请求通常需要频繁地分配新的 block，为了避免 SM 成为写请求的关键路径，SM 只关心 stream 和 extent，并不理解 block 这一概念，如此也能够将 SM 占用的资源限制在一个较小的范围内。

Extent Node

EN 管理 extent 的副本，每个 extent 在 EN 上对应的物理形式是一个文件，存储若干个 block 和保存每个 block 对应的文件偏移的 index。EN 在内存中保存有其所有的 extent 的副本信息，这也是构成 SM 管理的全局状态信息的一部分。EN 与其他节点通信主要完成两个任务：复制写操作到数据对应的副本；按照 SM 的指令创建已有数据的副本。

Append Operation and Sealed Extent

stream 支持多个 block 以原子操作的形式执行 append。若因为故障、超时等原因导致客户端未收到数据写入确认，客户端通常需要进行重试操作。而重试操作通常会导致重复数据条目。作为 stream layer 的客户端，partition layer 针对不同的数据采取不同的处理方式：

1. 针对 metadata stream 和 commit log stream，每个写入的记录会有一个唯一的单调递增的序号，这里的 metadata stream 可以理解成是 LSM-tree 中的 manifest 文件，而 commit log stream 则对应 LSM-tree 中的 WAL 文件，可以通过以增量日志的方式保存数据。在重新启动等需要再次加载数据的场景下，唯一的序号可以避免不必要的操作重复执行。
2. 针对 table 行数据和 blob 数据流，由于写入的最小单位是 block，只有最终写入成功的 block 才会被引用，之前的重复写入由于无任何引用属于垃圾数据，会被 SM 发现后进行垃圾回收。
   extent 有一个客户端指定的目标大小，超过这一大小后该 extent 就被封存不再接受写入。新的 extent 将会被创建并添加到 stream 中，接收该 stream 的写入。

Intra-Stamp Replication

Intra-Stamp Replication 是 stream layer 提供的同步复制机制，保证数据的持久性。该复制机制确保数据在不同的 fault domain 中有足够的副本，主要用于避免单个 fault domain 出现的硬件故障。由于是同步复制，因此该复制位于用户写请求的关键路径上，任意副本的写入失败都会导致用户写请求异常。
为了实现对象级别的强一致，Intra-Stamp Replication 提供如下保证：

1. 一旦数据写入成功并返回，从任意副本均可读取到一样的数据
2. 一旦 extent 归档后，从任意副本均只会读取到一样的 extent 内容

数据复制流程

全新 stream 创建流程：

1. SM 为 stream 的第一个 extent 分配3个副本，随机选择分布在不同的 fault domain 和 upgrade domain 的机器；
2. SM 选择某一个副本作为 primary extent，用于协调数据在从节点的写入。通常而言，primary extent 数量在机器之间尽量做到均匀以均衡负载。在 extent 未归档之前，任何角色的副本位置都不会改变；
3. 副本的位置和角色信息以元信息的形式保存在 SM 上，并在创建 stream 的请求响应中返回给客户端，客户端将缓存这些信息。如此，可以降低数据写入对于 SM 的依赖。

数据写入流程：

1. 客户端向 primary extent 发起数据 append 操作；
2. primary extent 确定新数据的写入位置(offset)，在此过程中可能需要对并发的写入请求进行排序；
3. primary extent 将写入请求发送到 secondary 副本；
4. 当所有副本 append 操作成功持久化到磁盘后，向客户端返回成功。所有副本都 commit 成功的 offset 称之为 current commit length。
   primary extent 在指定后就保持不变，而 append 的操作写入位置和顺序由 primary extent 决定，且在 append 出现错误后对 extent 副本进行归档，由此我们可以认为副本间的数据在比特级别保持一致。

数据写入失败处理流程：

1. 客户端写入失败，此时 extent 副本所在的部分 EN 可能不可达或发生磁盘故障；
2. 客户端通知 SM 某个 stream 写入失败；
3. SM 归档发生故障的当前活跃的 extent；
4. SM 在可用的 EN 上分配新的 extent，并返回给客户端；
5. 客户端开始在新的 extent 上写入；
6. SM 为之前归档的 extent 创建新的副本，保证符合期望的数据副本数量。

extent 归档

SM 负责所有 extent 的归档操作。一旦归档操作完成后，commit length 不会再改变。在归档过程中，SM 需要根据副本的 commit length 确定最终归档的 commit length：

1. 如果所有副本 commit length 均相等，那么最终 extent 的 commit length 就等于该值
2. 如果因为部分副本不可用导致 append 错误，从而导致副本 commit length 不完全相等，SM 选取最小的 commit length 作为最终的 commit length。这里我们简单展开一下讨论，我们假定最小的 commit length 为 cl0，最大的 commit length 为 cl1。由于 Intra-Stamp Replication 是同步复制，那么 cl0 和 cl1 之间的数据意味着他们只会在部分副本上 append 成功，而 pending 在未写入成功的 extent 上，不会返回成功给客户端。因此，可以选择 cl0 作为 commit length，并返回给客户端已经成功写入的数据数量，让客户端根据部分写入情况进行重试。

归档 extent 的纠删编码

为降低存储成本，利用 归档 extent 的不变性，WAS 对归档的 extent 进行纠删编码，可将存储空间占用从3副本的3倍磁盘空间下降到1.3-1.5倍。在一个 stamp 内，更增强了数据持久化能力。不过应当看到的是，经过纠删编码的数据读取时的开销相对于原数据更大。在部分延时敏感的读场景下，可采取将纠删编码后的数据进行重建得到原数据的方式加速访问，类似于 RocksDB 的 uncompressed block cache 机制。

避免自旋导致 IO 饥饿

HDD 通常倾向于达到最大吞吐量，牺牲调度的公平性。当磁盘应付大数据量的连续数据读取时，其他非连续数据读取可能会受到显著影响，延时可能高达2300ms。WAS 为了规避这一问题，采用了新的磁盘调度策略保证调度的公平性。对于需要面对多租户的应用场景的云服务来说，公平性是非常重要的。

1. 当有已经被调度的 IO，被调度之前 pending 时间超过100ms时，不再调度新的 IO 进入自旋状态；
2. 当有已经被调度的 IO，被调度后超过 200ms 未得到响应，不再调度新的 IO 进入自旋状态。

持久化和 journal

WAS 的持久化通过同步复制写入到至少3个位于不同的 fault domain 的副本完成。为了实现写入高性能，使用单独的整磁盘作为 journal device。由于 journal 通常是顺序写入，可以充分利用设备的 IO 带宽。使用高性能的 journal device，写入流程可以做如下优化：

1. 写入所有待 append 的数据到 journal device，同时在 cache 中缓存数据副本。当写入 journal device 完成后，即可返回写入成功。在数据盘写入成功前，用户对于这部分的数据读取请求都由 cache 负责；
2. 提交待 append 的数据到数据盘的写入队列中，由于 journal device 是顺序写，且数据盘的性能通常会差一些，数据盘的写入请求通常需要排队等待。数据落盘成功后，数据请求则可交由磁盘负责。

采用单独的 journal device 是一个简单粗暴的提升性能的方法，可根据 journal 的数据写入特点，选择适用的专门设备。

Partition Layer

Partition Layer 主要提供数据类型抽象、数据类型对应的操作、可扩展的 namespace、对象访问的负载均衡以及对象访问的事务排序和强一致性。

Partition Layer Architecture

Partition Layer Architecture

Partition Manger (PM)

PM 负责将 Object Table 划分为若干个 RangePartition，分配到 PS 中，并将 RangePartition 与 PS 的对应关系记录在 Partition Map Table 中。PM 保证每个 RangePartition 只会分配给一个 PS，并 RangePartition 相互之间不会重叠。PM 是一个有多个实例的无状态的服务，通过 Lock Service 选择主节点，在任期内负责 partition layer 的管控。

Partition Server (PS)

PS 负责响应若干个 RangePartition 的请求。基于 Lock Service 的 lease 机制，在任意时刻只会有一个 PS 为一个 RangePartition 服务。

当出现 PS 不可用时，该 PS 负责的所有 RangePartition 会被 PM 迁移到其他的 PS 上，在这过程中会考虑 PS 的负载情况。

RangePartition 数据结构

RangePartition 数据结构

每个 RangePartition 可以看作是一个 LSM-tree 数据结构，可以方便地使用 RocksDB 的概念来进行类比。

1. metadata stream：记录 commit log 和 data stream 信息。当发生 split 和 merge 操作时，metadata stream 也要相应更新。作用类似于 RocksDB 的 manifest 文件。
2. commit log stream: 记录最近的 checkpoint 以来的操作日志。作用类似于 RocksDB 的 WAL 文件。
3. row data stream：保存已经持久化的数据和索引。作用类似于 RocksDB 的 SST(Sorted Strings Table) 文件。
4. blob data stream：专用于 blob table 数据存储。
5. memory table: commit log stream 的内存镜像。一个查询通常会先查询 memory table，再查询 data stream。
6. index cache: 缓存持久化的 index 数据，与 row data cache 独立是为了尽可能多地缓存 index。作用类似于 RocksDB 的 table cache。
7. row data cache: row data page 的缓存，由于 row data stream 是只读的，所以不需要考虑数据更新，只需考虑数据的淘汰。类似于 RocksDB 的 block cache，可以有 LRU、Clock 等淘汰策略。

数据流

RangePartition 的与常规的 LSM-tree 需要特别指出的是，在 blob data 这种单个 value 较大的的场景，为了避免 commit log stream 和 data stream 的重复写，在写入过程中只执行 commit log stream 的写入，只在 data stream 中记录相应的 commit log stream 的指针。在 checkpoint 过程中，通过对 commit log stream 底层的 extent 进行重组得到最终的 blob data stream。

RangePartition 负载均衡

PM 会出于负载均衡的目的执行以下3种操作：

1. Load Balence：根据 PS 负载情况，对 RangePartition 进行再分配
2. Split：对负载过重的单个 RangePartition 进行拆分
3. Mege：对负载较轻的相邻的 RangePartition 进行合并

Load Balance

评估 RangePartition 的负载情况主要通过以下几个指标：

1. transaction/second
2. transaction 平均挂起时间
3. 限速速率
4. CPU 使用率
5. 网络使用率
6. 请求延迟
7. 磁盘数据大小
   PM 维护与每个 PS 的心跳信息，RangePartition 的负载情况在心跳信息中反馈给 PM。若 PM 发现某个 RangePartition 负载过高时，PM 会对 RangePartition 进行 split 操作；当 PM 发现某个 PS 负载过高时，PM 会发起 RangePartition 迁移。

Split Operation

PM 根据 RangePartition 的负载和 data stream 的数据量决定是否执行 split 操作，split 操作最重要的就是选择 key ( AcountName + PartitionName):

1. 基于 data stream 数据量的 split，PM 选择使得可以使得 RangePartition 被近似切分成两等份的 key；
2. 基于负载的 split，PS 动态统计负载最重的 key 区间，并以此来选择切分的 key。
   split 的流程如下：
3. PM 命令 PS 对 RangeParitiion B 执行 split 操作，分为 C 和 D；
4. 负责 B 的 PS 执行 checkpoint，然后 B 停止对外服务；
5. PS 为 C 和 D 创建新的 stream。这一步可以很快，因为 stream 只是 extent 的指针集合；
6. PS 恢复 C 和 D 对外服务；
7. PS 通知 PM split 完成，PM 更新 Partition Map Table 及元信息。通常，PM 会迁移 C 或 D 到另一个 PS 上。

Merge Operation

PM 会选择两个相邻的负载较低的 PartitionName 区间的 PartitionRange 进行合并：

1. PM 迁移 C 和 D 到相同的 PS 上，并通知 PS 合并 C 和 D；
2. PS 为 C 和 D 分别执行 checkpoint 操作，然后停止他们的对外服务；
3. PS 为 E 创建 stream，新的 commit log stream 和 data stream，都是按照先 C 后 D 的顺序排列 extent；
4. PS 根据新的 commit log stream 和 data stream 构建新的 metadata stream；
5. E 重新加载 meta stream，开始对外提供服务；
6. PM 更新 Partition Map Table 及元信息；

Partition Layer Inter-Stamp Replication

对于每个账户而言，LS 分配一个 primary stamp 和多个 secondary stamp。为了实现 数据中心级别的灾难恢复，通过 geo-replication，WAS 在一个 account 的不同 stamp 之间执行 Inter-Stamp Replication。Inter-Stamp Replication 是一种异步复制的机制，在灾难恢复过程中，最近的数据可能会丢失。另外，Inter-Stamp Replication 也可用于数据的迁移。

后记

WAS 是我完成的第二篇论文阅读笔记。论文阅读是一个费时费力的过程。对于系统设计的文章，涉及内容多、范围广，常惊叹于顶层设计之精妙，时沉静细节考虑之优雅。由于内容较多，形成一个总体意义上的结论，对于初出茅庐的我而言还尚有些吃力。因而，论文阅读笔记难免沦为论文翻译。在本次阅读过程中，我尝试了将论文打印下来，先进行部分注解，再来撰写论文读书笔记的形式，相较之前还是有显著的效果。

参考文献

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