Windows Azure Storage Made Simple

加机器就是一把梭

没有什么问题是加一千台机器解决不了的，如果有，就再加一千台。
—— 《21天精通分布式系统》

分布式系统在设计之初，是为了解决单机系统的可用性和可扩展性问题的。

举个例子，单机系统就是雇一个小弟替你干活，但是这个小弟不太靠谱，偶尔泡个病号不上班，偶尔工作太多一个人干不过来。

分布式系统就是雇一群小弟帮你干活，偶尔有一两个小弟泡病号，我们会有富裕的人力顶上，工作太多我们可以继续拉新的小弟入伙，美滋滋。

这个比喻很好的描述了单机系统和分布式系统之间的关系。所以一种可能的分布式系统就是这个样子的：

我们将相同功能的服务器组成一个整体，通过一个load balancer对外提供服务。

这样的系统初步解决了我们的问题，在面对可扩展性和可用性的问题时，我们会：

容量不足就加机器
单机挂掉了就把流量调度到其它的节点上

不过单纯的加机器并不能完全满足我们的需要。对于CPU密集型的服务，增加副本数可以有效的均摊计算压力，但是对于存储密集型的服务，我们需要增加分库逻辑才能有效的增加系统的计算能力。

例如我们有100G的数据，但是数据库的容量最多只支持50G。这样无论怎么样增加副本都不能解决问题。如果我们将100G的数据均分，存储在两个50G的分库上，我们就可以支持单机系统容纳不了的数据了。

我们还可以把多个这样的分布式子系统组合起来，就可以组成一个小有规模的分布式系统了。现在我们在使用的一些服务，仍在使用这种模型。

上面分布式模型虽然有效，但是引入了一个严重的问题：因为节点之间是隔离的，并且只能通过消息传递进行通信与协调，所以基本无法完全保证副本之间保持一致的内部状态。

这就是所谓的一致性问题。

补充一点理论知识

CAP理论

CAP理论指的是：

一个分布式系统不可能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三个基本要求，最多只能同时满足其中的两项。

CAP理论由Eric Brewer在2000年首次提出，并且2年后被Seth Gilbert和Nancy Lynch从理论上证明这个理论。

一致性是指数据的多个副本之间保持一致的特性；
可用性是指系统的服务必须一直处于可用的状态;
而分区容错性是指系统在遭遇任何网络分区故障的时候仍然能够保证对外提供满足一致性和可用性的服务，除非是整个网络环境都发生了故障;

抛开一致性问题不谈，“可用性”和“分区容错性”从某种意义上讲是一个分布式系统的“标配”：单机和网络连接并不可靠，从一堆不可靠的硬件上层建立一个不可靠的系统并没有任何意义。

所以一致性常常被牺牲，来保证分布式系统的可用性和分区容错性。

Paxos算法

Paxos是Leslie Lamport在1990年提出的一种基于消息传递且具有高度容错性的一致性算法。

Paxos解决的问题是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生任何异常，都不会破坏整个系统的一致性。

Paxos的描述和证明有一些复杂，这里不做展开。简单来说，就是系统中的各个节点使用类似于选举投票的算法来达成一致，选举过程中会有短暂的数据不可用中间状态。

“我最讨厌我想做的事情做不成”

在分布式环境中，一致性是指数据在多个副本之间是否能够保持一致的特性。在一致性的需求下，当一个系统在数据一致的状态下执行更新操作后，应该保证系统的数据仍然处于一致的状态。
—— 《从Paxos到ZooKeeper》

无数的理论和实践证明，解决分布式系统的一致性问题是非常困难的。从最直观上来说，我们找不到两片一样的树叶，也找不到两台状态完全一致的分布式节点。

但是前人的智慧是无穷的，我们仍然有以下几种方案来保证数据的一致性：

2PC and 3PC

2PC（Two-phase Commit，两阶段提交）是用来保证分布式系统一致性的一个协议。其流程可以由这个例子来表示：

PM（协调者）: 我要加个需求！（阶段1，提交事务请求）
Dev1（参与者）：你加吧
Dev2（参与者）：你加吧
PM（协调者）：我真加了！（阶段2，执行事务提交）
Dev1（参与者）：加完了
Dev2（参与者）：加完了

注：PM和Dev是程序员老梗而已。各个职业只是分工不同，本质上都是为人民服务。

整个流程看起来很美好，但是我们会遇到如下问题：

同步阻塞
在提交过程中，系统需要等待所有参与者的响应，所以系统整体处于一种阻塞状态，影响效率。
单点问题
协调者是系统的单点，如果当掉，整个系统就处于不可用状态。
数据不一致
一个数据一致性协议会导致数据不一致，确实是非常讽刺的事情。在执行事务提交阶段，如果协调者与参与者的通信中断，可能会导致数据的不一致：
- 当协调者发往部分参与者的Commit消息丢失，没有收到Commit的参与者会因为超时而认为这次请求失败而进行回滚
- 当参与者发往协调者的ACK消息丢失，协调者会认为这次请求失败，但是参与者确实已经Commit了数据

3PC（Three-phace Commit，三阶段提交）是2PC协议的改进版，将整个请求分为三部分：

事务询问
预提交
执行提交

这样的改进减少了同步阻塞的粒度，但是仍然没有解决单点问题和数据不一致的问题。所以2PC和3PC都不是非常理想的数据一致性协议。

Paxos

上文中我们提到Paxos是一种被数学证明过的，具有高度容错性的一致性算法。但是其流程复杂，通信次数较多，并且在提案未被选中之前不能保证数据的可用性。

所以Paxos的应用场景多为命名服务、配置管理、分布式锁等轻量级但是而又非常核心的服务，从而扬长避短，更好的为人民服务，~~更好的反三俗~~。。

Quorum-like Algorithm (Amazon Dynamo)

对于分布式系统的一致性，最直观的解决方案就是在修改节点状态时，将修改广播到所有节点上。这样从理论上讲，就可以保持节点的一致性了。

但是在现实工程当中，广播修改是最不可靠的方案，因为通信可能失败，节点可能失效，我们的修改很有可能不会同步到所有的节点上（假设每个节点的可靠性为99.9%，那么10个节点同时可靠概率只有99%，100个节点同时可靠的概率为90%）。

不过，让所有节点都保持完全一致虽然很完美，但是其付出的代价也许是现有的系统难以承受的。Amazon Dynamo使用了一种类似选举的算法来保证数据的一致性。

设我们有N个节点，我们再指定两个数R和W，使得 R + W > N。在写入数据的时候，我们同时向N个节点写入，当有W个（及以上）节点写入成功，就向客户端返回成功；在读取的时候，我们向R个节点请求数据，此时一定会读到刚刚写入新数据的节点，然后我们将最新的数据返回给用户。

不过这种设计并不完善，当出现网络错误或者大规模节点失效的时候，数据一致性就很难保证了。

我称这种一致性模型为 —— “尽力一致性”。

Event Stream for Eventual Consistency (Apache Kafka)

从Dynamo的经验中我们可以看出，直接将状态的修改广播到不同的节点是不可靠的。那么我们有没有办法解决这个问题呢？

Apache Kafka使用了类似“预写式日志”的方法来保证一致性。当状态修改请求到来时，先写入一条公共的数据流，这条数据流往往是持久化到磁盘的。然后不同的节点再访问数据流，执行同样的状态修改请求，保证节点状态的一致性。

这种设计的缺陷是虽然最终所有节点都会依次执行相同的命令，但是节点执行命令的速度有快有慢，所以在瞬时会有不一致的情况。

这种一致性模型被称为 —— “最终一致性”。

主角登场：Windows Azure Storage

Windows Azure Storage（以下简称WAS）采用了多种一致性算法，在提供较高性能服务的同时，来努力保证存储系统的CAP性质。

其中WAS使用了一些创新性的算法，不过我们还是先从它的整体架构谈起。

Windows Azure Storage的架构

WAS从架构上分为三层，分别是前端（FE Layer），分区层（Partition Layer）和数据流层（Stream Layer）。这三层从功能上各有分工，但是又分别解耦，可以部署在不同的机器上。

下面我们自底向上的讨论一下各层之间的功能与联系。

WAS - 数据流层

数据流包含着各种数据操作，操作包含插入、修改、删除等基本操作，“流”则可以看做是一条无限长的队列。

为什么要使用流结构？

为什么要用流结构呢，原因非常简单，因为流中的操作都是有序的，否则会造成不确定的结果。

例如我们现在有三个操作：

操作1：插入值x=1
操作2：修改该值为x=2
操作3：修改该值为x=5

如果操作是按照顺序来做的话，那么我们获得的值为x=5。但是如果我们将操作2和操作3调换之后，那么我们获得的值为x=2；如果我们将操作1放置在操作2或操作3之后，我们就在修改一个不存在的值，这势必会造成错误。

所以，数据流的有序性保证了操作的“回放一致性”，也就是说，相同的数据流应用在不同的机器上，获得的最终状态是一致的。

同时，由于HDD的顺序读写性能优于随机读写性能。使用流数据结构可以将写入请求顺序化，追加写入磁盘，在廉价的硬件上获得最好的性能。

科普时间：HDD与SSD

HDD指的是Hard Disk Drive，又称Spinning Disk，是计算机使用的一种以磁性碟片存储数据的一种非易失性存储设备（人话就是：断电后不丢数据）。数据存储在同心圆磁道上，工作时碟片会旋转（和CD机一样），磁头会移动到相应的磁道上进行数据的读写（CD机用的是光头）。所以，顺序读写时，HDD的性能会比随机读写要好，因为随机读写带来的大量磁盘寻址会让磁头不断移动，从而拖慢性能。

与此同时，由于碟片内弧的旋转线速度要小于外弧，所以外弧的读写性能会优于内弧。

SSD指的是Solid State Disk，即固态硬盘，也是一种常见的非易失性存储设备。其使用闪存芯片来存储数据。由于其并不像HDD一样需要物理上移动磁头来进行寻址，在顺序写入与HDD或略强于HDD磁盘的同时，随机写入性能要远远强于HDD（这就是为什么我们装电脑都喜欢把系统装到SSD盘上）。

但是SSD在成本和质量上弱于HDD磁盘。1TB的SSD的价格约为400刀，而1TB的HHD价格仅为80~100刀（2017年10月数据）；SSD有写入次数的限制，当闪存芯片损坏时，会影响SSD的性能。相比而言，HDD的技术的性能更稳定，技术更为成熟，质量会更好一些。

数据流的一致性算法

因为要保证可用性，所以数据流必须要是多机的，而多机系统就要面临一致性问题。WAS提出了一种“链式提交”方法来保证了分布式数据流的一致性。

与之前提到的分布式一致性的多机并行的算法不同，WAS在数据流层采用了一种“链式”的提交算法：

当副本1接受到数据后，会首先将数据持久化到磁盘，之后再将相同的请求转发给副本2；
副本2获得数据后，持久化到磁盘，再请请求转发给副本3；
副本3将数据成功持久化后，返回ACK；
副本2接收到副本3的ACK消息后，同样返回ACK；
副本1接收到副本2的ACK消息后，向请求方返回ACK。

这样做的好处是，当数据请求返回ACK后，一定有三个（或以上，根据系统的参数而定）副本同时写入并持久化这条请求。此时三个副本一定是“强一致”的。

不过，如果链式提交当中有任何一个环节出现了问题，比如机器失效、网络超时等，那么我们就要面临数据不一致的情况。WAS为了解决这个问题，引入了被称为“封存”的机制。

封存（sealing）机制

上文说到，数据流是一个无限长的队列，只能在尾部追加写入。所以我们如果想要存储这条数据流，就势必要把这条数据流分为多个节，并把它们分别存储在不同的机器上。否则数据流的大小就要受限于单机的存储容量，这并不是我们想要看到的。

又由于数据流的尾部追加写入特性，所以数据流被分为多个节之后，只有最后一个节是可读写的，其它的所有节都是只读的。

我们将把可读可追加的数据流转化为只读的数据流的操作称为“封存”。

封存的作用之一，就是在数据流的一节过大的时候，停止写入该节，使得数据节的大小可控。

第二个作用，是上面我们提到的，在“链式提交”失败的时候，我们会将所有的数据流副本封存，封存的时候取所有副本的数据的交集。这样就能排除因为写入失败而不一致的数据。

此时有同学会问，如果我们已经成功的写入了三个副本，但是由于网络原因并没能向请求方返回ACK。请求方会认为这段数据写入失败。但是我们在封存的时候，仍然会将这部分数据封存在数据节中。这种情况怎么处理呢？
这个问题后面会有解答，请耐心阅读哦~

数据流层的架构

在前面的文章里，没有提到“数据流管理器”（Stream Manager，简称SM）这个角色。这个角色在整个数据流层扮演了一个很重要的角色。

SM是由一个小型集群使用paxos选举出来的master节点，其它节点备用。SM只用来管理整个数据流的状态，并不负责具体的读写操作。

SM的主要功能有：

统计节点状态
监控节点健康状况
负载均衡
封存、创建新的数据节
备份与垃圾回收

SM管理着一批存储着数据节的节点（Extent Node，简称EN），这些节点存储着数据流中的节。这些节点相互通信，以完成提交、备份等功能。

EN节点中采用了预写入日志。每一次写入操作，EN会并发的

追加写入日志文件，并将新数据写入内存缓存
写入持久化存储

当二者有一个完成，就返回成功标记。这样做的好处是，由于HDD追加写入的性能非常好并且稳定，所以步骤1的响应时间是稳定的并且可以估计的。保证了系统整体的响应时间不出现大的颠簸。

WAS - 分区层

分区层为我们提供了一个被称为“对象表”（Object Table）的抽象。对象表提供了插入、更新、删除功能。

为了提供容量支持，一个对象表会被划分为多个分区（这就是“分区层”名字的来源）。分区之间相互独立，不会互相影响。

对象表构建在数据流层之上。但是从直观上来讲，表结构和流结构是完全不同的，那么分区层是如何将表存储在数据流层的呢？

LSM Tree（Log-Structed Merge-Tree）

段子：
一个学生背着满书包的书进入图书馆，叮叮叮，图书馆的报警器响了，学生赶紧把书从书包倒出来，准备一本一本的验证，看是哪本书有问题。
一旁扫地的阿姨看不下去了，过来把书分成了两挪，先检查第一挪，叮叮叮，报警器响了，说明这一挪有问题，又把这一挪分成两挪，先检查其中一挪，要是哪一挪响了，就把这一挪继续分成两挪，继续检查，不到三回合，大妈就把有问题的哪本书找出来了。
大妈用鄙视的眼神看着那学生，仿佛在说连O（n）跟O（log n）都分不清楚。

我们上文中提到，HDD磁盘可以在较低成本下提供很好的追加写入性能，但是对于随机读写的性能不佳。

但是对于表结构来说，必然涉及到大量的随机读写。因为输入数据就像打乱过的扑克牌，很难保证规律性；而我们又要把特定的输入数据放到特定的行上，所以数据的写入位置必然是随机的。所以，直接在磁盘中存储表结构是非常低效的。

那么LSM Tree是怎么解决问题的呢？

首先我们把已有的数据根据key进行排序，存储在磁盘中，标记第0代。所有写入磁盘的数据都是有序的、只读的。

当有新的数据写入时，我们首先将其缓存在内存中。当数据达到一个阈值时，我们将内存中的数据进行排序，并写入磁盘。这一部分数据被标记为第1代。

之后的数据依次类推，被标记为第2代，第3代...第n代。代数越高，表示数据越新。并且代数高的数据在逻辑上可以覆盖代数低的数据。

在查询时，我们首先检索内存中的缓存数据，如果没有找到，就依次从第n代的数据查询到第0代。如果仍然没有找到，就返回未找到。由于所有的查询都使用二分查找，效率较高。同时我们还可以使用[布隆过滤器][6]，快速判定一个key是否在LSM Tree中。

细心的同学会发现，按照上面描述的算法，LSM Tree的代数会无限膨胀下去，最终导致非常差的的检索效果。在论文中没有明确提到LSM Tree的调教参数，但是我猜测其代数不会太多。并且在冗余数据过多时，会进行垃圾回收，保证检索的效率。
同时这也提醒我们在使用WAS的时候，尽量不要向某一个或某一些连续的分区连续写入大量数据，否则会导致分区层的性能退化。

分区层使用的数据流

分区层使用数据流来保存LSM Tree，使用顺序写入代替随机写入以获得性能提升，这条流被称为“行数据流”（Row Data Stream）。

与此同时，分区层还使用了“二进制数据流”（Blob Data Stream）来保存二进制数据。以及“提交日志流”（Commit Log Stream）来持久化预写入日志。

分区层向数据流层写入时，只有当数据流层返回ACK后，才认为写入成功。所以，在数据流层写入成功，但未能返回ACK时，虽然数据流层保留了数据，但是分区层并不能访问这部分数据，我们就在分区层保证了数据的正确性。

分区层的一致性保证

分区层的持久化信息依赖于数据流层，所以如果分区层使用在线多副本，就会遇到节点状态不一致的问题。也就是说，虽然不同的节点加载了相同的数据，但是加载速度有快有慢，很难保证节点之间以一个同样的状态对外服务。同时，在线多副本的写入会引入竞态，如果再加锁，就会大大的影响系统的效率。

那么WAS是怎么解决这个问题的呢？

答：不能保证一致性就不要一致性。

这样的不要一致性并不是放任节点间的状态不同步，而是每一个分区只使用一个在线服务节点。对于唯一一个节点来说，一致性就是不存在的。（是不是非常暴力）

所以，在同一时间只有一台机器对外提供服务（读+写）。其它的副本是在线备份，在对外提供服务的机器在计划内下线或意外当掉时，就会启用另一台副本对外提供服务。当然这也会造成一致性问题，所以这里牺牲了一点可用性，也就是在旧节点下线后，新节点必须加载完所有的数据才可以对外提供服务。中间的一段时间这个分区是不可用的。

分区层的架构

图中的PS指的就是上文提到的分区服务，每个PS维护着对象表的一个分区，其持久化信息都储存在数据流层上。

PM（Partition Manager）也是使用paxos算法选举出来的master节点，用来管理分区服务的负载均衡、灾备等操作。

Lock Service用来对分区节点进行选举，选出的唯一master节点对外提供服务。

Partion Map Table用来存储与检索分区所对应的节点。

WAS - 前端层

前端层只是薄薄的一层REST API封装，并没有什么其它特殊功能。这里一笔带过。

战胜CAP理论？你他娘的真是个天才！

WAS宣称自己战胜了CAP理论，提供了高可用性和强一致性。WAS能做到这点主要是因为数据流层设计的好。

数据流层使用了只追加写的数据模型，加上链式提交提供的高一致性，所以能应对节点失效（可用性）和网络失效（分区容错性）的故障。

数据流层之上的分区层利用了其特性，很容易的实现了高可用性和分区容错性。同时，又由于其使用单点向外提供服务，所以一致性也有了保障。

所以WAS宣称自己战胜了CAP理论，也不是没有道理。但是个人感觉WAS在分区层的单点设定，是以牺牲可用性（A）换取一致性（C）的一种妥协，只是由于机器故障并非多发，触发问题的机率比较小。

写在后面

本文是《Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency》一文的读后感，删节了一部分不容易理解的细节。想要更详尽的理解WAS的设计思想，请阅读论文原文以及官方文档。一切内容和理解上的冲突，以原文和官方文档为准。

撰写本文时，我使用Atreus2tap迷之小键盘，在学习前人经验教训的同时，重新学习了打字。

小键盘的好处是便携，以及避免手指移动带来的劳损。缺点是需要精心设计并练习大量的组合键，同时成套的键帽真是不好买。

上一张图。

听说用这种奇怪键盘的人都注孤了。