作者｜太根，携程高级后端开发工程师，专注于数据存储和数据库领域；夏凌，携程研发总监，专注于大数据存储和性能调优。Dynamo式数据库来自亚马逊的Dynamo：Amazon的HighlyAvailableKey-valueStore论文，该论文讨论了没有主复制的数据库。受此启发，携程酒店开发了多存储媒体预订库Hare和高可用性能的动态信息存储服务InfoKeeper。本文将介绍Dynamo风格的无主复制数据库及其在携程酒店的实践。1.Dynamo式数据库在分布式系统中，为了提高数据的可用性和性能，通常会复制相同数据的多份副本，以共享读写请求和主备切换。在复制形式上，主要有单主复制、多主复制、无主复制。1.1单主复制在单主复制中，只有一个主节点可以写，数据从主节点复制到从节点，从节点可以承担读请求。单主复制结构简单，易于实现，不存在数据冲突。但是写入依赖于master节点，写入性能由master节点的性能决定。主从节点之间存在复制延迟（从节点上读取的数据不一定是最新的数据），主节点未能在执行主从切换时出现数据丢失或写入不可用。1.2多主复制在多主复制中，多个主节点承担写请求。与单主复制相比，数据写入请求由多个主节点共享，但主从节点之间的复制延迟仍然存在。此外，两个主节点同时写入相同的数据需要冲突解决机制来确定哪个写入优先。1.3无主复制Dynamo式数据库是无主复制。写入请求不会通过特定的主节点复制到从节点。所有节点都可以进行读写，并容忍写入时的不一致。解决获取时的不一致问题。假设一个数据库中有三个节点，存储的键值对X=1。下图中，三个节点都收到了同一个写请求，C节点写失败。这时候三个节点中key值X对应的值是不同的，收到读请求后自然会返回不同的值。从上帝的角度来看，此时keyX对应的值应该是100，但是对于一个正在运行的系统来说，需要一种机制来解决下面两个问题。这种机制称为仲裁。对于读取的不同值，哪个是正确的值？必须读取多少个节点才能确保读取到正确的值？显然，如果只从C节点读取，那么无论第1题的答案是什么，都得不到正确的值。1.4严格仲裁使用时间戳或版本号来判断哪个值是正确的值：时间戳或版本号最大的代表数据是最新的，最新的数据就是正确的数据。R+W>N，N：节点总数，W：需要判断写入成功的节点数，R：读取时至少需要读取成功的节点数，总节点数W+R>N时的节点会读取最新的数据。如下图，蓝色节点代表写入成功的节点，即W=3。当R=3时，读成功的节点和写成功的节点一定有交集。W越小，写可用性越高，写性能越好；R越小，读可用性越高，读性能越好。假设单节点可用性P=99.9%，用于计算masterless复制时的读写可用性。下表显示了不同R和W的可用性。以N=3为例，读取R=1时Availabilityequals。节点数R,W读可用性写可用性2R=2W=199.8%99.9999%R=1W=299.9999%99.8%3R=2W=299.999%99.999%R=3W=199.7%99.9999999%R=1W=399.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时读取错误数据的概率.NumberofnodesR,WReadAvailabilityWriteAvailability读取正确数据的概率2R=1W=199.9999%99.9999%99.9998%3R=1W=299.9999999%99.999%99.9999997%R=2W=199.999%99.9999999%99.9999997%R=1W=199.9999999%99.9999999%99.9999994%无主复制数据库在写入时容忍部分节点不一致，但我们希望每个节点上的数据尽可能完整，这需要节点版本完成。1.6节点间版本补全1）写修复，节点写失败在写的时候就已经感知到了，写失败后可以通过消息队列等方式进行异步补偿和修复。2）读修复，在读取数据的时候，节点之间的数据不一致是已知的，此时可以根据仲裁得到的数据修复版本滞后的节点上的数据。3）巡检，主动扫描介质间数据，根据仲裁结果修复数据。2、从无主复制扩展到多媒体存储。在介绍无主复制数据库时，使用了“节点”的概念。这里有一个节点的定义：运行同一套代码，功能完全相同的进程，比如Redis的主节点和从节点。在携程酒店的预订订单和价格信息存储中，选择合适的存储介质一直是一个核心技术问题。我们希望数据不仅在介质上（Redismaster和slave）有互备，而且在介质间也有互备（比如Redis和Trocks），因为同一个存储介质总是有相似的运行机制，并且同时出现问题的概率更高。在多媒体数据存储中，前面理论部分用存储介质代替“节点”的语义是：数据同时写入多个存储介质，容忍部分存储介质的写入失败，当发生时使用仲裁读取数据。确定数据在整个系统中的最终值。整个系统可以容忍单个存储介质级别的不可用，系统的稳定性从容忍单个节点故障到存储介质级别。3.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个媒体并比较版本号，返回版本号最大的数据。但是如果所有的数据都读取完了，只有一个介质读取成功，这个介质成功的数据会返回给调用者。所以松散仲裁的意思是当使用严格仲裁但不能满足严格仲裁的条件时，可用性优先。编写和阅读时的流程图如下所示。4、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型存储介质作为主要介质，可根据数据的性能和数据新鲜度要求选择相应的存储介质reader.andarbitration），一些分散在各个用户的缓存被丢弃，直接从InfoKeeper中读取。据统计，InfoKeeper节省了20%的硬件成本，数据传输效率比过去使用关系型数据库存储更高。用户从关系数据库中拉取的方式得到了极大的改进，同时也消除了关系数据库的单点性能限制。一种构建缓存的新模式在InfoKeeper前面的架构图中，如果将主要介质换成关系型数据库，将介质换成redis，就实现了为DB构建缓存的目的，但是数据从DB中pull下来改为active将数据写入redis，减轻DB的压力。如果需要搭建多个缓存，只需要多挂几个slavemedia即可。目前一般酒店的房型缓存都是采用这种方式。五、设计目标验证如何确认多媒体存储系统满足设计预期，并能容忍存储介质层面的故障？Hare上线6个季度，InfoKeeper上线4个季度。我们每个季度都会对Hare和InfoKeeper进行单次媒体注入故障演练。演练过程中，应用及上下游正常。注入故障恢复后，写修复终于赶上来了。如果成功，则可以确认系统符合设计预期。六、前景展望目前InfoKeeper和Hare还停留在应用代码层面，还没有形成共同的组件。增加新的服务需要在已有代码的基础上增加业务逻辑。开发者对多媒体存储底层代码比较敏感，可能还需要修改多媒体存储层的代码以更好的适配新业务。我们计划将Infokeeper和Hare的代码合并成一个通用的组件，让新用户对多媒体存储层不敏感，开箱即用，降低多媒体的使用门槛存储，让用户可以更专注于业务代码。
