干货 | 携程Dynamo风格存储的落地实践
作者简介
根泰，携程高级后端开发工程师，关注数据存储和数据库领域。
遐龄，携程研发总监，关注大数据存储、性能调优。
Dynamo风格数据库来源于亚马逊的Dynamo: Amazon’s Highly Available Key-value Store 论文，在该论文中论述了一种无主复制的数据库，受此启发，携程酒店开发了多存储介质预定库Hare和高可用性高性能的动态信息存储服务InfoKeeper。本文将介绍Dynamo风格的无主复制数据库，及其在携程酒店的实践。
一、Dynamo风格数据库
在分布式系统中，为了提高数据的可用性和性能，通常会将同样的数据复制多份，分担读写请求和主备切换，在复制形式上，主要有单主复制、多主复制、无主复制。
1.1 单主复制
在单主复制中，只有一个主节点可以写入，数据从主节点复制到从节点，从节点可以承担读请求，单主复制的结构简单，易于实现，没有数据冲突。但是写入依赖主节点，写入性能由主节点的性能决定，主从节点之间存在复制延迟（在从节点上读取到的数据不一定是最新的数据），在主节点发生故障进行主从切换的时候存在数据丢失或者写入的不可用。
1.2 多主复制
在多主复制中，有多个主节点承担写入的请求，相比于单主复制，数据的写入请求被多个主节点分担，但主从节点之间的复制延迟问题依然存在。除此之外，两个主节点对同一份数据的并发写入需要冲突解决机制决定以哪次写入为准。
1.3 无主复制
Dynamo风格的数据库就是无主复制，写入的请求不会经过特定的主节点复制到从节点，所有的节点都可以承担读取和写入，容忍写入时的不一致，在读取时解决不一致。
假设一个数据库中有三个节点，存储的键值对X=1。在下面的示意图中，三个节点都收到了同一个写入的请求，C节点写入失败。
此时，三个节点内键值X对应的value是不一样的，收到读请求后自然会返回不同的值。
从上帝视角看，此时此刻，键值X对应的value应该是100，但对于一个运行的系统，需要一个机制解决下面两个问题，这个机制称为仲裁。
- 对于读取到的不同的值，哪个值为正确的值？
- 读取多少个节点才能保证读取到正确的值？显然，如果只从C节点上读取，那不管问题1的答案是什么，都得不到正确的值。
1.4 严格仲裁
使用时间戳或者版本号判定哪个值为正确的值：时间戳最大的或者版本号最大的，代表数据是最新的，最新的数据就是正确的数据。
R+W>N，N：总的节点个数，W: 判断写入成功所需的节点个数，R：读取时至少需要读取成功的节点个数，W+R>N时总会读到最新的数据。如下图所示，蓝色的节点表示写入成功的节点，即W=3，当R=3时，读取成功的节点和写入成功的节点一定会有交集。W越小，写入的可用性更高，写性能越好，R越小，读的可用性更高，读性能越好。
假设单个节点的可用性P=99.9%，以此来计算无主复制时的读和写的可用性，不同的R、W的可用性情况如下表所示，以N=3举例，R=1时读的可用性等于
。
节点的数量 | R、W | 读可用性 | 写可用性 |
|---|---|---|---|
2 | R=2 W=1 | 99.8% | 99.9999% |
R=1 W=2 | 99.9999% | 99.8% | |
3 | R=2 W=2 | 99.999% | 99.999% |
R=3 W=1 | 99.7% | 99.9999999% | |
R=1 W=3 | 99.9999999% | 99.7% |
根据表中所示，在N=3，R=W=2时，读和写的可用性都比单个节点的读写可用性高，这也是Dynamo风格数据库使用的推荐配置。
1.5 宽松仲裁
在严格仲裁时，如果达不到严格仲裁的R+W>N时会返回调用端错误码，假设N=5，W=R=3，读取的时候读了5个节点，但是三个节点读失败了，只有两个节点读成功了，此时如果以两个节点的结果比较版本号或者时间戳，得到的数据有可能是错误的，也有可能是正确的。
如果我们的系统能够忍受返回不新鲜的数据的可能性，那么使用宽松仲裁是提高系统可用性的一种办法。我们来定义宽松仲裁：在系统达不到严格仲裁的条件时，利用仅有的条件返回调用端结果，注意，必须是先尝试满足严格仲裁，达不到严格仲裁时使用仅有的条件返回调用端结果，比如，N=5，R=W=3，在读取数据时先读取三个节点，两个节点读取失败，为了满足严格仲裁，再读取剩余的两个节点，但是一个成功，一个失败，此时一共有两个节点读取成功，使用两个节点的数据宽松仲裁，得出结果，而不是一开始就只读两个节点，这两种方式读取到错误数据的概率差别很大。
使用宽松仲裁时得到正确数据的概率如下表所示，假设单个节点的可用性P=99.9%，N=1，R=W=1时，读和写的可用性是
，N=3，R=1，W=1时读到错误数据的概率
。
节点的数量 | R、W | 读可用性 | 写可用性 | 读到正确数据的概率 |
|---|---|---|---|---|
2 | R=1 W=1 | 99.9999% | 99.9999% | 99.9998% |
3 | R=1 W=2 | 99.9999999% | 99.999% | 99.9999997% |
R=2 W=1 | 99.999% | 99.9999999% | 99.9999997% | |
R=1 W=1 | 99.9999999% | 99.9999999% | 99.9999994% |
无主复制的数据库在写入的时候容忍了部分节点的不一致，但是我们希望每个节点上的数据尽可能的完整，这就需要节点版本补齐。
1.6 节点间的版本补齐
1）写修复，节点写失败在写入的时候已经是被感知到的，可以通过消息队列等方式异步的在写入失败之后补偿修复。
2）读修复，在读取数据的时候，已经知道了节点间的数据不一致，此时可以根据仲裁得出的数据来修复版本滞后的节点上的数据。
3）巡检，主动的扫描介质间的数据，根据仲裁的结果修复数据。
二、由无主复制向多介质存储扩展
前面介绍无主复制数据库的时候一直在使用“节点”这个概念，这里对节点做一个定义：运行同一套代码的、拥有完全相同功能的进程，比如Redis的master和slave节点。
在携程酒店的预定订单和价态信息存储中，选择合适的存储介质一直是一个核心的技术问题，我们希望数据不仅在介质内有互备（Redis的master和slave），还能有介质间的互备（比如Redis和Trocks），因为同一个存储介质总是拥有相似的运作机制，同时出问题的概率更高。
在多介质数据存储中，我们对前面理论部分用存储介质代替“节点”后的语义就是：数据同时写到多个存储介质中，容忍部分存储介质的写入失败，在读出数据时，仲裁决定整个系统中数据最终的值，整个系统能够容忍单一存储介质级别不可用的情况，系统的稳定性从容忍单个节点故障提升到了存储介质级别。
三、Hare：多存储介质的预定库
Hare的名称来源于成语“狡兔三窟”，数据存储在多个介质中，以保证数据的安全。Hare承担携程酒店预定库的功能，主要用于存储在用户下单的各个环节（创单、支付、提交）中产生的订单相关数据。在订单完成提交后从Hare同步到订单库，进入订单处理环节。Hare的架构图如下图所示，应用层代码管理底层的Redis、Trocks、Hbase的写入和读取，以及仲裁返回给调用端的数据。介质间版本补齐使用写修复。
Hare内部采用宽松仲裁，N=3，W=1，R=1，使用版本号判断最新版本。需要特别指出的是，W=1并非任何一个介质写入成功就算成功，Hare内部“期望”的写入成功个数为2，但是当所有介质写入完成后，写入成功的介质个数依然没有达到2，就会优先考虑可用性，写入成功的个数等于1也算写入成功。
当W=1时，严格仲裁的R应该等于3，Hare内部会读所有的3个介质并比较版本号，返回版本号最大的数据。但如果读完所有数据，依然只有一个介质读成功，还是会以成功的这个介质的数据返回给调用方。所以宽松仲裁的含义是，在使用严格仲裁但达不到严格仲裁的条件时，优先保证可用性。写入和读取时的流程图如下所示。
四、InfoKeeper：高可用高性能的动态信息存储
InfoKeeper是对Hare架构在酒店价态量存储场景下的改进，Hare作为下单场景用，对性能要求较低，但对数据的可靠性要求更高。但在酒店的价态量存储中，对性能要求更高，数据可靠性要求较下单场景低，所以InfoKeeper中存储介质的个数较Hare更少，选择了Redis和Trocks两个存储介质，仲裁的N=2，W=1，R=1。
我们将InfoKeeper中参与仲裁的介质称为主介质（图中绿色），将只会写入但是不参与仲裁的介质称为从介质（图中淡蓝色），从介质的写入是否成功都不会影响对客户端的响应。介质间的版本补齐使用写修复。在酒店价态量存储中架构图如下。
InfoKeeper写入的流程图如下。
InfoKeeper现在支持的存储介质有redis、trocks、mysql、es、hbase、oceanbase、Tikv、qmq、kafka、soa。qmq通常作为推送增量的方式，kafka用于推送离线数据，soa用于通过soa接口调用的方式更新服务端的缓存。因为接口较消息队列延时更低，所以soa面向对缓存新鲜程度要求很高的使用方，比如酒店查询服务，在InfoKeeper中将消息队列和soa接口当作一种存储介质看待，只是这种存储介质不能提供读功能。
InfoKeeper中存储的数据目前在百亿级别，InfoKeeper完成了这些数据的存储、承担了40万QPS的读能力，以及数据从存储方到各个使用方的高效流转。得益于强大的读能力（强大的读写能力主要是因为选择了性能更好的KV型存储介质为主介质，可以根据数据读取方对性能和数据新鲜度的要求，选择对应的存储介质和仲裁的方式），一些散落在各个使用方的缓存废弃，改为直接从InfoKeeper读。根据统计，InfoKeeper节省了20%的硬件成本，数据的流转效率较以往使用关系型数据库存储，使用方从关系型数据库拉取的方式大大提高，还消除了关系型数据库的单点性能限制。
建立缓存的一种新模式
在InfoKeeper前面的架构图中，如果将主介质改为关系型数据库，从介质改为redis，就实现了为DB建缓存的目的，只是把从DB拉数据改为了主动往redis写数据，减轻了DB的压力。如果需要建多份缓存，只需要多挂几个从介质就可以实现。目前酒店的房型通用缓存就是使用这种方式。
五、设计目标的验证
怎么确认多介质存储系统符合设计预期，能够容忍存储介质级别的故障？Hare上线6个季度，InfoKeeper上线4个季度以来，我们在每个季度都会对Hare和InfoKeeper做单个介质注入故障的演练，在演练期间应用和上下游正常，在注入故障恢复之后，写修复最终追赶成功，可以确认系统符合设计预期。
六、展望
现在InfoKeeper和Hare还在应用代码层面，没有形成通用的组件，新的业务的加入需要在现有代码的基础上增加业务逻辑，开发者对底层的多介质存储的代码是有感的，也可能需要修改多介质存储层的代码以更好的贴合新的业务。
我们计划对Infokeeper和Hare的代码进行合并，形成一个通用的组件，让新的使用方能对多介质存储层无感，做到开箱即用，降低多介质存储的使用门槛，使得使用方能更专注于业务代码。