小米开源了分布式KV存储系统，分布式实现那些事儿-MTV学习库

作者｜孙伟杰

编辑| 小智

小米最近开源了分布式KV存储系统。这款小米轮毂背后有哪些设计理念和技术细节？

写在前面

这次给大家带来的主题是“分布式实现的那些事——背后的故事”。在本次演讲中，我重点解释了我们在架构和实现中遇到的一些陷阱。

我来自小米，主要从事研发工作。是小米自己打造的分布式KV存储轮。不知道大家对于造轮子有什么看法呢？就我个人而言，我应该尽量避免造轮子。如果有更好的方案可以解决问题，则应优先使用其他方案；除非随着业务的发展，没有好的解决方案可供选择，那就只能自己创造一个。

做的过程是这样的。

的生产

在项目立项之前，小米主要使用HBase进行分布式存储。经过10多年的发展，HBase本身已经比较稳定，功能接口也比较方便。但由于设计和实现上的一些问题，我们在使用中仍然存在一些陷阱。

记得一次HBase事件

相信大家对于HBase的架构应该都很熟悉了。如上图所示，HBase通过一个节点来管理整个集群的状态。在节点的全面管理下，节点负责客户端的读写请求；数据存储在外部分布式文件系统HDFS上。它负责心跳检测和高可用性。

当我们实际使用的时候，就会出现很多问题。在设计之初，它是一个负载要求比较低的系统，所以在小米这边，多是被多个业务使用。除了HBase之外，还有很多其他业务都依赖它来进行节点活动、服务注册等。但是，当某些服务使用时，就会对其施加过大的压力，从而导致不稳定。此外，某些对的滥用，例如访问时不共享连接，也是服务不稳定的根源。

各种误操作因素的存在会导致频繁死机。对于HBase来说，崩溃就意味着它也崩溃了。小米的很多业务都依赖HBase。一旦HBase崩溃，小米的很多业务将无法提供服务。

HBase的缺点

在回顾了HBase的一系列问题后，我们认为有几点值得一提：

1、对于HBase来说，它交出“节点检测”的重要任务是值得商榷的。因为如果运维不够细致，就会成为影响HBase稳定性的坑。

在HBase中，处理“会话超时”的方式就是“自杀”。 “一个WAL多次共写到HDFS”的实现方式会让“自杀”的行为成本相对较高，因为自杀后重启时WAL会被拆分并重放。这意味着如果整个 HBase 集群出现故障，则需要很长时间才能重新启动 HBase。

2. 即使我们能够保证稳定性，“节点检测”功能也不能非常稳定地运行。因为HBase是用Java实现的。 GC的存在会导致正常运行被误判为死亡，进而引发自杀；除此之外，还需要从 HDFS 加载其他重放 WAL 来提供服务。这个过程也是比较耗时的。在此期间，所提供的密钥不可读或不可写。

这个问题可以通过延长“节点检测”的时间阈值来解决。但这会妨碍真正的“死亡”被及时发现，进而引发另一个可用性问题。

3. GC的另一个问题是HBase存在读写延迟的毛病。我们希望在广告和推荐服务中尽可能避免这样的故障，即有一个相对稳定的延迟。

总结以上三点，我们认为HBase在可用性和性能延迟方面还存在一些缺陷。这些问题可以通过修补和调整参数来缓解。但要从根本上解决它仍然不容易。

定位

由于我们无法弄清楚HBase，所以我们必须自己重新创建它。由于HBase已经成为标杆，所以我们的定位非常明确：取HBase的长处，弥补HBase的短处。具体来说：

有了这些定位，我们的架构就相对清晰地出现了：

架构概述

总的来说，这个架构借鉴了很多HBase：

与HBase的区别有以下几点：

现在的高可用就靠它了，这对于项目开发的简单性来说是一个好处。稍后可能会引入Raft来完全消除对.

多副本一致性协议

如前所述，我们的每个文件都有多个副本。为了满足多副本情况下的强一致性，我们必须使用一致性协议算法。我们使用 MSRA 发布的。与Raft的对比可以参考我们项目中的文档，这里不再赘述。总的来说，我们认为基于论文实现一个可用的存储系统比 Raft 难度要低。

写请求流程

协议中负责接受读写请求的称为，相当于 Raft ；另外两个接受请求称为，相当于Raft。在这样的架构下，写请求比较简单：如果客户端有写请求，首先需要查询Key的位置，然后向该位置发起写请求，然后同步到客户端。两者都成功后，则返回回复，表明客户端的写请求成功。

读取请求流程图

读请求操作更加简单。客户端直接发起读请求，并直接响应，因为它已经拥有了所有数据。

实施过程中的陷阱

上面简要回顾了设计考虑因素和总体架构。现在我们进入正题，看看这样的架构在实现上存在哪些问题？

可扩展性

让我们首先看看可扩展性。可扩展性分为两点：

选择

因为，业界一般有两种解决方案，第一个是哈希，第二个是排序。

对于哈希来说，所有的key都被分成很多桶，一个桶就是一个，然后根据key的哈希值分配到某个桶；排序时，一开始所有的key都在一个中，然后根据的容量不断进行动态分裂和合并。

两种方案相比，排序比散列多了一个先天的优势，那就是排序方案具有全局排序的效果。但由于排序需要不断的动态分裂，所以实现起来比较麻烦。

此外，如果使用散列，数据库就不易因业务访问模式而出现热点。排序：由于所有的key都是按顺序排列的，所以具有相同前缀的请求很可能会集中在一个或相邻的请求上，而这些请求很可能会落在同一台机器上。对于哈希来说，所有的key都被提前打散了，自然不存在这个问题。

然而，简单地比较两种解决方案的优缺点是没有意义的。我们还是要从商业角度出发。我们认为，在互联网业务场景中，不同的key（比如两个用户的名字）之间不需要存在偏序关系，所以权衡之后，我们采用了哈希方案。

哈希实现

在实现过程中，我们遇到的第一个问题是“如何存储数据”。 “根据哈希值将密钥放入桶中”只是一个理想化的抽象。在实际的系统实现中，还必须提供一层“表”的概念来分隔不同的业务。有了表的概念之后，我们在实现上就开始出现分歧。具体来说，我们有两种存储方案：“多表混合存储”和“分离存储”。

所谓多表混合存储，就是将表ID和哈希键结合起来计算出一个新的哈希值，并根据这个哈希值从全局唯一的空间中选择一个进行访问。如上图的左半部分所示。

对于分离存储，表的语义被下推到存储层。如上图右半部分所示：每个桌子都有独立的空间。当有读或写请求时，首先要根据表ID找到对应的空间，然后根据hash key找到对应的空间。

那么这两种选择哪个更好呢？理论上，我们认为多表混合存储方案更好，因为它更符合软件工程中分层的思想；混合存储也更容易实现，因为只需要管理一份元数据副本，并且负载平衡更简单。但从业务角度来看，最好采用每个表单独存储的解决方案。因为单独存储意味着表之间的资源限制、表级监控和表删除操作更加简单。考虑到运维中的误操作，单独存储也更有优势。即使误删了一项，误操作对不同业务的影响也会更小。

下表给出了我们对两个选项的比较：

两者相比较，一个在理论上更美观，一个在实践上更利于商业。最终我们还是从商业的角度出发。我们放弃了理论上更美观、更容易实现的方案，选择了对业务友好的方案。

哈希负载均衡

说完了哈希，接下来就是负载均衡的问题。下面列出了负载均衡的一般分布式KV存储目标：

负载平衡 - 目标

具体来说，负载平衡的目标有两个：

A. 不能共享

B.对于每个表，可以均匀分布在不同的表上

上图是目标B的简单说明：如果一个表中有四张表，总共有三张，我们希望12的分布是(1, 3), (2, 2), (1, 3) .

负载均衡-算法

在实现我们的负载均衡算法时，需要注意的一个非常重要的一点是，角色切换比数据复制更好，因为角色切换的成本非常低。

对于这一点的解释，可以参考上图中的两种情况：

左图中，和上分布了 4 个，而上没有。这时，通过将上面的A和上面的A的角色互换一下，就可以满足平衡。

右图中，4 比 4 的分布是 (2, 1, 1, 0)。如果想要达到平衡，就需要将最上面的迁移到最上面，但是直接迁移需要复制数据。这时候，如果我们引入一个中间节点，先把A和A的角色交换一下，然后把D和D交换一下，就可以达到一个平衡。

为了处理这些情况，我们建立了集群中可能的流向的有向图，然后使用Ford-'s方法进行迁移和交换。具体算法不再展开，请参考我们的开源项目代码。

在实际的负载均衡中，需要考虑多种情况：

目前的开源项目中，有些情况还没有考虑到。后续我们会持续优化负载均衡，请您持续关注。

一致性和可用性

前面介绍了可扩展性，然后是一致性和可用性。我们的设计考虑之前已经介绍过：

当我们按照这些设计目标实现了系统，准备找商家一试身手时，商家却用一句话推回了我们：“你们有双机房热备吗？”

为什么要单独说这个呢？因为对于强一致性的分布式存储系统来说，跨机房的容错是一件很麻烦的事情：

通过对这个问题的反思，我们认为，我们实际上已经切中了“完善制度”的要害。从业务角度来看，作为一个完整的存储系统，确实需要处理各种异常情况。但随着出现异常情况的概率降低，业务对一致性的要求实际上也在逐渐放宽：

了解业务需求后，我们设计了多级冗余策略来应对不同的风险：

关于上述冗余策略的几点说明：

延迟保证

最后介绍一下保证时延性能的问题。对于这个问题，有两点需要强调：

至于实现语言，我们选择了C++。原因前面已经说过了。为了保证性能，我们必须使用没有运行时GC的语言。另一种选择可能是 Rust。关于为什么我们选择C++而不是Rust，我们的考虑如下：

当然，这个选择是保守的，语言层面的讨论到此结束。重点仍然是我们一致性协议的实施。

从实践的角度来看，正确高效地实现一致性协议，同时又保证代码易于维护和可测试是很困难的。主要原因是一个完整的请求涉及到很多Stage，Stage之间会发生IO，再加上并发需求，往往需要代码的非常细粒度的锁定。

下图给出了一个完整的写请求的简化流程图：

从上图可以看出，当客户端发起写请求时，该请求会陆续产生写入本地磁盘、发送网络RPC等多个事件。无论事件成功还是失败，都需要检查公共一致性状态。访问或修改。这样的逻辑会导致我们对一致性状态进行非常繁琐的线程同步，非常容易出现bug。

那么遇到这样的问题该如何处理呢？从我们的经验来看，我们需要将代码的组织方式从“竞争临界区”改为“排队进行无锁序列化”。我先用一张图来说明一下我们的代码结构：

具体来说，它以“状态一致性”为核心，将所有涉及状态变化的事件串入一个队列，并通过单独的线程执行队列事件。所谓执行就是改变一致性状态。如果执行过程中触发IO，则使用纯异步模式，IO完成后的响应事件会排队。如下所示：

另外，为了避免创建过多的线程，我们采用线程池的方式。一个“一致性状态”数据结构只会被一个线程修改，但多个结构可以共享一个线程；与线程之间存在多对一的关系。

总的来说，这种事件驱动的纯异步方法使我们能够在访问一致状态时避免细粒度的锁同步。 CPU不会陷入IO等待，并且使用线程池，因此性能得到保证。另外，这种实现方式明确地将一个写请求划分为不同的阶段，非常方便我们监控读写过程，对项目的性能分析非常有利。

测试

接下来，我们将重点讨论测试是如何进行的。

分布式系统稳定性问题

当我们完成系统后，我们发现真正困扰我们很长一段时间的是如何稳定系统。

这个问题主要体现在哪些方面？总结起来有三点：

测试比较困难，也没有更有效的方法来测试系统。目前的经验是，把它当成一个黑盒子，一边读写一边杀死任务，找到它的某个模块出现问题的方法，然后检查全局是否有问题。然而，这种测试方法只能发现bug，因为问题的发生是有概率的。

难以重现。由于bug的出现是有概率的，即使通过测试发现了问题，也不容易重现，进一步给调试带来麻烦。

难以返回。如果通过阅读日志、观察现象、分析代码找到了问题的症结所在。你的修复是否有效并不能令人信服。此修复能解决问题吗？会不会带来新的问题？由于没有稳定的繁殖方法，这两个问题很难回答。

根本原因：不确定性

那么造成上述困难的根本原因是什么呢？综上所述，我们认为是程序本身的不确定性。这种不确定性体现在两个方面：

用一个公式总结一下：

小概率IO错误+随机执行路径=不易重现的异常情况

那么我们应该如何解决这个问题呢？

既然在线上很难复现问题，我们是否可以构造一个模拟场景：在这个模拟场景中，我们可以模拟IO错误的概率，控制程序的执行顺序。然后在这样的模拟场景中运行代码。如果逻辑有问题，我们可以按照相同的执行顺序重现问题。逻辑修改后，可以进一步做成单元测试，这样就解决了回归困难的问题。

当然，这样描述这个问题还是很抽象的。这里我举一个简单的例子来说明：

假设有这样一个账户系统，里面有两个人，Alice和Bob。他们的账户余额各100元，分别存储在两台机器上。双方都可以向对方发起转账交易。现在Alice想转5元给Bob。最简单的实现是Alice从自己账户的余额中扣除5元，然后向Bob的机器发起增加5元的请求。 Bob的账户增加5元后，他可以通知Alice转账成功。

如果机器没有宕机、磁盘没有故障、网络没有问题，那么这个简单的实现就可以了。但这样的假设永远不会成立，所以为了处理这些问题，我们可能会增加一系列手段让账户系统更加可靠，比如添加交易日志、将交易和账户信息备份到多台机器上。介绍一些分布式事务技术。这些手段的引入将使我们的系统变得更加复杂。

面对如此复杂的系统，任何数据库状态的异常都会让我们摸不着头脑，比如下面Alice和Bob的账户信息发生变化：

(, ) -> (, )

当程序没有bug的时候，我们可以假设Alice和Bob的账户余额之和等于200，现在余额之和变成了210，肯定是某个环节出了问题。也许当两个人同时互相转账时，触发了一些bug；也许数据包被发送了两次。进入非法状态的可能情况有很多种，但是硬件的概率故障以及Alice和Bob之间复杂的（可能是并行的）传输记录会让我们很难定位和重现非法状态的原因。

对于这样的问题，我们的武器是模拟性和伪随机性。通过这两种方法，我们希望程序能够按照可重现的事件顺序运行。这样，如果程序因为进入非法状态而崩溃，我们可以重现、调试并返回到该状态。

还以上面Alice和Bob之间的交易为例。双方同时转账的流程在模拟环境中可能会这样运行：Alice发起转账->Bob发起转账->Alice发起磁盘写 -> Alice 发起 RPC -> Alice RPC 成功 -> Bob 发起磁盘写 -> Alice 写磁盘失败

换句话说：

假设有这样的环境，分布式业务逻辑的调试难度肯定会降低很多。一方面，随机性的存在让我们可以测试各种执行顺序；另一方面，伪随机性和错误注入使我们能够重现遇到的问题。

控制不确定性

那么，具体的控制不确定性是如何做到的呢？

该层的模拟实现是一个难点，重点包括：

单元测试也是使用这个测试框架进行的。在单元测试中，我们将使用脚本来描述应用于场景的操作和预期状态。上图中App Logic的作用就是加载脚本，然后根据脚本检测程序状态是否符合预期。

所采用的测试框架的概念和实现源自微软的开源框架rDSN。整个框架比较难理解，这里只是简单介绍一下其原理。如果有兴趣可以直接查看源码。

现状及计划

目前已在小米内部稳定服务近一年，已服务近十家商家。关于存储引擎、性能和设计的更多阐述，可以移步Arch 2016的另一个分享（文末有链接），也可以参考我们上面的相关文档。

后续我们将开源数据冷热备份、拆分等功能，敬请持续关注。我们也欢迎各界人士加入小米，加入我们的团队。

写在最后

最后总结一下整篇文章的内容。

我们在调研或实施项目时，必须注意三点：

给这篇文章的作者打赏

相关文章

进事业单位实习期工作总结及实习工作经验分享！

网络入侵方式主要包括哪些？你知道吗？

对讲机的分类及工作方式无线电“对讲机”的工作原理