美团大规模KV存储挑战与架构实践

• 1 美团 KV 存储发展历程

• 2 大规模 KV 存储的挑战

• 3 内存 KV Squirrel 挑战和架构实践

• 3.1 Squirrel水平扩展的挑战

• 3.2 Gossip优化

• 3.3 Squirrel 垂直扩展的挑战

• 3.4 forkless RDB

• 3.5 工作多线程

• 3.6 Squirrel可用性的挑战

• 3.7 两机房容灾

• 3.8 跨地域容灾

• 3.9 双向同步冲突自动解决

• 4 持久化 KV Cellar 挑战和架构实践

• 4.1 Cellar垂直扩展的挑战

• 4.2 Bulkload 数据导入

• 4.3 线程调度模型优化

• 4.4 线程RTC模型改造

• 4.5 内存引擎无锁化

• 4.6 Cellar可用性的挑战

• 4.7 双向同步冲突自动解决

• 5 发展规划和业界趋势

1 美团 KV 存储发展历程

上图就是美团第一代的分布式 KV 存储的架构，可能很多公司都经历过这个阶段。在客户端内做一致性哈希，然后在后端部署上很多 Memcached 实例，这样就实现了最基本的 KV 存储分布式设计。但这样的设计存在很明显的问题：比如在宕机摘除节点会时丢失数据；此外，在缓存空间不够需要扩容时，一致性哈希也会丢失一些数据，这样会给业务的开发带来很大的困扰。

随着 Redis 项目的成熟，美团也引入了 Redis 来解决我们上面提到的问题，进而演进出来上图这样一个架构。可以看到，客户端还是一样，使用一致性哈希算法，在服务器端变成了 Redis 组成的主从结构。当任何一个节点宕机，我们可以通过 Redis 哨兵完成 failover，实现高可用。但有，还一个问题还是没有解决，如果扩缩容的话，一致性哈希仍然会丢失数据。

这时我们发现业界有一个比较成熟的开源 KV 存储：也就是阿里巴巴的 Tair 。2014年，我们把 Tair 引入到技术内部，去满足业务 KV 存储方面的需求。Tair 开源版本的架构主要是三部分：最下边的是存储节点，存储节点会上报心跳到它的中心节点，中心节点内部设有两个配置管理节点，会监控所有的存储节点。如果有任何存储节点宕机或者扩容之类的行为，它会做集群拓扑的重新构建。客户端启动的时候，它会直接从中心节点引入一个路由表，这个路由表简单来说就是一个集群的数据分布图，客户端根据路由表直接去存储节点读写。之前我们 KV 遇到的扩容丢数据问题，它也有数据迁移机制来保证数据的完整性。

但是在使用的过程中，我们还遇到了一些其他问题，比如：它的中心节点虽然是主备高可用的，但它没有分布式仲裁之类的机制，所以在网络分割的情况下，它是有可能发生“脑裂”的，这种情况也给我们的业务造成过比较大的影响。在容灾扩容的时候，遇到过数据迁移影响业务可用性的问题。

另外，我们之前用过 Redis ，业务会发现 Redis 的数据结构特别丰富，而 Tair 还不支持这些数据结构。虽然我们用 Tair 解决了一些问题，但是 Tair 同样也无法完全满足我们的业务需求。于是，我们认识到在美团这样一个业务规模大、复杂度高的场景下，很难有开源系统能很好满足我们的需求。所以，我们决定在已应用的开源系统之上进行自研。

时值 2015 年， Redis 社区正式发布了它的集群版本 Redis Cluster。所以，我们紧跟社区步伐，并结合内部需求做了很多自研功能，进而演进出本文要介绍的全内存、高吞吐、低延迟的 KV 存储 Squirrel。另外，我们基于 Tair，加入了很多美团自研的功能，演进出本文要介绍的持久化、大容量、数据高可靠的 KV 存储 Cellar 。

Redis 社区一直都很活跃，所以，Squirrel 的迭代是自研和社区并重，自研功能设计上也会尽量与社区架构兼容。Tair 开源版本已经多年没有更新，所以，Cellar 的迭代完全靠自研。后续内容上大家也能看到，因为这方面的不同，Cellar 和 Squirrel 在解决同样问题时可能会选取不同的方案。

这两个存储其实都是 KV 存储领域的解决方案。实际应用上，如果业务的数据量小，对延迟敏感，建议用 Squirrel ；如果数据量大，对延迟不是特别敏感，我们建议用成本更低的 Cellar 。

2 大规模 KV 存储的挑战大规模

KV 存储的业务挑战主要有两点：

一个是扩展性。随着业务规模持续变大，业务会要求使用容量更大的集群。这个容量包括两方面，一方面是数据量，还有一方面是调用量。扩展容量，最常见的方法就是把集群水平扩展到更多的节点，但是当集群节点数达到一定规模后，再想扩展新节点也会遇到很多困难，这是扩展性上的第一个挑战。

还有一个问题是有些业务场景的调用容量是无法随着集群水平扩展而扩展的。比如，很多业务会使用 mget 进行批量读取。但随着集群节点数的增加，由于“木桶效应”，整个 mget 请求的长尾延迟会越来越高，进而导致服务的请求超时率持续上升。等集群达到一定规模之后，长尾延迟造成的可用性降低就超出业务的承受能力了。所以在水平扩展之外，我们还需要解决好节点垂直扩展上的挑战，来支持这种批量操作的业务场景。

3 内存 KV Squirrel 挑战和架构实践

上图是美团的 Squirrel 架构。中间部分跟 Redis 社区集群是一致的。它有主从的结构，Redis 实例之间通过 Gossip 协议去通信。我们在右边添加了一个集群调度平台，包含调度服务、扩缩容服务和高可用服务等，它会去管理整个集群，把管理结果作为元数据更新到 ZooKeeper。我们的客户端会订阅 ZooKeeper 上的元数据变更，实时获取到集群的拓扑状态，直接对 Redis 集群节点进行读写操作。

| 3.1 Squirrel水平扩展的挑战

但是基于 Redis Cluster 架构的水平扩展，会有如下问题：

一个是 Gossip 的消息通信量是节点数的平方，随着集群节点数的增加，Gossip 通信的消息量会急剧膨胀。比如，我们实测对于一个 900 节点的集群，Gossip 消息的 CPU 消耗会高达12%，远高于小集群的 Gossip 资源消耗，这样会造成极大的资源浪费。

| 3.2 Gossip优化

为了解决上述的扩展性问题，我们对社区的 Gossip 方案进行了优化。首先针对 Gossip 传输的消息，我们通过 Merkle Tree 对其做了一个摘要，把集群 Gossip 通信的数据量减少了90%以上。服务端节点仅需要对比 Hash 值即可判断元数据是否有更新，对于存在更新的情况也能快速判断出更新的部分，并仅对此部分元数据进行获取、更新，大幅降低了 Gossip 消息处理的资源消耗。同时，我们还增加了一个周期性的元数据全量同步功能，来解决可能因 Hash 冲突导致元数据无法更新的问题。

| 3.3 Squirrel 垂直扩展的挑战

对基于 Redis 研发的 Squirrel 来说，垂直扩展会存在如下问题：

首先是数据容量的问题。对一个内存存储来说，节点容量过大的话，很容易影响服务的可用性。例如，在主从节点要做数据同步时，Redis 节点需要通过 fork 产生子进程来生成全量数据的 RDB 快照。当一个 8GB 的节点做 fork 调用时，会由于页表项过多，造成进程出现 500 毫秒的阻塞。对于平均耗时只有几毫秒的 KV 请求来说，这 500 毫秒的阻塞会造成大量的超时。

还有就是处理量的扩展问题。虽然我们可以通过加从库去扩展集群的读能力上限，但主库的写处理能力却还是无力扩展的。而且，受限于主库的处理能力和机器带宽限制，加从库来扩展读能力也是有上限的。

| 3.4 forkless RDB

针对上述节点过大，fork 生成 RDB 会导致可用性降低的问题。我们实现了 forkless RDB 方案，这是一个不基于 fork，且不会中断服务的生成数据快照 RDB 的方案。

如上图所示，forkless RDB 的生成期间，它首先会停止哈希表的 rehash 过程，避免数据在哈希表之间的搬迁影响快照的一致性。然后，它会从头开始对整个哈希表的 key 做迭代，每迭代一个 key 就会把它 dump 一份出来放到复制队列里边。在迭代 key 的同时，它会对迭代的位置记录一个游标。

如果在迭代哈希表的过程中，里面的 KV 有变更的话，在这个游标之前的  KV 变更，也会把它放到复制队列里边，确保已经复制的 KV 能够持续获得后续的变更。如图所示，RDB 游标在 key 3，它会把之前已经迭代过的 key 1 更新、key 2 删除操作也插入到复制队列里边。在游标之后的 key，因为还没有做数据复制，所以等后续迭代到这个 key 时，把其最新值 dump 到复制队列就好。通过这样的方式，就实现了一个不需要 fork 就能获得一个一致性数据快照 RDB 的过程。

| 3.5 工作多线程

对于处理量的扩展，社区有一个 IO 多线程的解决方案。但这个 IO 多线程只是把网络收发部分做了多线程处理，所以，其扩展能力是比较有限的。比如 4个 IO 线程下，它只能把整体的吞吐提升一倍，就到极限了。而且因为此时工作线程已经到瓶颈了，再往上去加 IO 线程，不仅无法提升性能，反而会消耗更多的 CPU 资源。对此，我们的解决方案是工作多线程，也就是说把请求处理的过程也多线程化。

如上图所示，在工作多线程方案下，每个线程都会去处理请求，并且每个线程会完成从收包到请求处理，然后到发包的整个过程，是一个 Run-to-Completion 线程模型。相比 IO 多线程，它会减少很多线程切换，节省很多的 CPU 资源。同时对于请求处理的过程，我们也通过细致的梳理，尽量缩小了临界区的范围，以保证大部分的请求处理过程是在临界区之外的，来提升处理并发度。

如果一个工作线程需要加锁的话，它会先 try lock。如果加锁成功就继续执行了，但如果加锁失败的话，这个工作线程也不会阻塞等锁。它会先去注册一个管道的通知消息，然后就继续处理网络的收发包，还有非临界区的请求了。等到锁被释放的时候，这个工作线程会通过 epoll 获得管道里面的锁释放通知，然后去拿到这把锁。这个时候它就可以去处理临界区的请求操作了。

这样的话，在整个加锁、解锁的过程中，工作线程没有任何阻塞，仍然可以继续做网络收发、非临界区请求的处理，获得最大限度的处理能力。另外，对于新建 socket、数据复制等工作，跟工作线程的耦合很低，我们将其放到了单独的线程去执行，以尽量降低工作线程的负载。

通过实测，工作多线程方案的吞吐比社区 IO 多线程提升了 70%，相对于社区单线程提升 3 倍多。

| 3.6 Squirrel可用性的挑战

基于 Redis Cluster 的大规模集群可用性挑战主要是维持机房容灾部署很困难。如上图所示，由于 Redis Cluster 是去中心化的架构，所以部署上要求至少是三机房分布，以此来保证任何一个机房挂掉的时候，剩余的两个机房仍然能有过半的节点来选出新的主节点。比如一个上千节点的集群要扩容的话，可能需要几百个分布在三个机房的节点，一时之间其实很难凑齐这么多机房的资源。而当业务大促容量需求很急时，我们有时候只能牺牲机房容灾能力来满足业务的容量需求。

还有在成本方面，对于一些数据可靠性要求较低的业务，只需要两副本冗余就够了，极端情况下丢一点数据也是可以接受的。但受限于容灾要求，这些业务也只能使用三机房三副本部署，从成本角度考量很不划算。

| 3.7 两机房容灾

受 Google Spanner 的见证者节点启发，我们在 Squirrel 集群也引入了见证者节点角色。同 Spanner 一样，Squirrel 见证者节点也不会存储数据，所以，它无法作为正常的主从库提供请求处理能力，也不能发起选主投票。但见证者节点可以在集群选主时参与投票，帮助存活的机房节点完成过半选主过程。

见证者节点还可以设置权重，这样只需要一个或几个高权重见证者节点，就能满足一个大规模集群的容灾部署需求了。由于见证者节点不存储数据，且节点数很少，虽然集群还是三机房部署，但实际几乎只需要两机房的资源就能满足机房容灾部署需求了，这样就大幅降低了集群维持容灾部署的难度，从而节省大量的机器成本。

| 3.8 跨地域容灾

双向同步有两个经典问题需要解决：

一个是循环复制问题。我们为每个 Squirrel 集群标记了不同的 cluster id，并且记录了每个 KV 的初始写入 cluster id，同步服务会过滤掉与目标集群 cluster id 相同的数据，以避免发生循环复制。

还有一个是数据冲突问题。我们一开始是通过业务层面保证在每个地域写不同的 Key 来解决的。但是在双向同步的运行过程中，还是会有一些极端场景可能会出现两个地域并发写同一个 Key。比如像机房网络故障场景，业务会把故障机房的所有写入都切到正常机房。

但由于我们的集群间复制是异步的，可能故障机房有一些最新的 Key 变更还没有复制到正常机房的集群。而如果在业务将写切换到正常机房后，又写入了相同 Key 的不同变更，就会产生两个同步集群的数据冲突。在机房网络恢复之后，业务还是要把一部分流量切回到之前故障的集群上，恢复到跨地域容灾的架构。

| 3.9 双向同步冲突自动解决

如上图所示，在 T1 时刻 Key money 的值在 A、B 两个集群都是 100。T2 时刻，money 的值在 A 集群更新成了 120。但是在 A 集群的新值还没复制到 B 集群的时候，B 集群在 T3 时刻把 money 的值更新成了 130。这时候 A、B 集群会互相向对方复制各自写入的新值，A 集群收到 B 集群的值 130 后，会发现 B 集群 money 的更新时间大于自己（T3 > T2），它就会更新自己的 money 值为 130；B 集群也会收到 A 集群复制过来的 money 值 120，但它会发现这个值的更新时间小于自己本地值的更新时间（T2 < T3），就会忽略这个复制请求。通过这样一个基于更新时间的 last write win 策略，就可以达到最终一致性。

• 保存最近更新的时间戳：当发生时钟回退时，我们会继续使用自己保存的时间戳，避免使用本地回退的时间导致数据也跟着发生了回退。（PS：对于时钟回退问题，我们调研过最新的 NTP 时钟同步不会像以前一样造成本地时钟的回退或跳变，现在它通过把时钟 tick 调快或调慢来完成类似的调整，所以，前述关于时钟回退的解决方案在最新的 NTP 同步机制下就不是必要的了。不过，为了保证我们的服务在任何系统下都能正常运行，我们最终还是实现了这个功能。）
• 记录写入数据的集群 id：我们会为所有写入的 Key 保存写入的集群 id。当两个值的更新时间相同时，我们会比较集群 id，如果也相同，我们就知道是同一个集群先后写入但获取到相同本地时间的数据，会允许其写入；如果不同，我们仅会让集群 id 更大的值写入，来保证数据最终一致性。
• 由复制操作改为复制变更后的数据：像 INCR 类接口，A 集群的 money T1 时刻通过 INCRBY money 20 变成了 120，然后 B 集群 T2 时刻通过 INCRBY money 30 变成了 130。A 集群收到 B 集群的复制时，因为时间戳比自己的本地值大，它会执行 INCRBY money 30 变成 150；然后 B 集群收到 A 集群的复制时，因为时间戳比自己的本地值小，它会把这个复制请求给忽略掉，就造成了数据冲突。针对这个问题，我们将所有操作的数据复制都改成了复制操作后的数据，而不是这个操作本身，来解决类似 INCRBY 这种接口的数据冲突问题。
• 保存最近删除的 Key：像删除类接口，A 集群 T2 时刻写入了 money：120，然后 B 集群在 T3 时刻删除了 money 这个 Key。A 集群收到 B 集群的复制时，由于其时间戳比本地值大，A 会把数据删了；但 B 集群收到 A 集群的复制时，由于本地已经不存在 money 这个 Key 了，它就会把 money 当做一个新 Key 进行写入，就造成了数据最终不一致。针对这个问题，我们通过保存最近一段时间删除掉的 Key 及删除时间戳，以便在删除集群收到对端复制过来的旧 Key 时进行甄别。

4 持久化 KV Cellar 挑战和架构实践

第一个是 OB，第二个是 ZooKeeper。我们的 OB 跟 ZooKeeper 的 Observer 是类似的作用，提供 Cellar 中心节点元数据的查询服务。它实时的与中心节点的 Master 同步最新的路由表，客户端的路由表都是从 OB 去拿。这样做的好处主要有两点：第一，把大量的业务客户端跟集群的大脑 Master 做了隔离，防止路由表请求影响集群的管理；第二，因为 OB 只提供路由表查询服务，不参与集群的管理，所以它可以水平扩展，极大地提升了路由表的查询能力。

第二个是我们引入了 ZooKeeper 做分布式仲裁，解决了上述提到的 Master、Slave 在网络分割情况下的“脑裂”问题。并且通过把集群的元数据存储到 ZooKeeper，从而提升了元数据的可靠性。

| 4.1 Cellar垂直扩展的挑战

在 Cellar 架构下，不存在水平扩展的问题，但与 Squirrel 一样，它也有垂直扩展方面的挑战。而由于 Cellar 是持久存储，它也很少遇到单机数据容量的问题，而要解决的问题主要是处理容量的垂直扩展。而且，由于 Cellar 是持久化引擎、多线程模型，它要解决的处理容量扩展问题也是不一样的，具体如下：

• 引擎读写能力的不均衡性：Cellar 是基于 LSM-Tree 引擎模型的持久化存储，这种引擎的多 Level compaction 会导致写放大问题，进而会造成其写处理能力比读低很多。所以，在一些写相对较多的场景，机器资源虽然还有空闲，但写处理能力却已经到瓶颈了。
• 线程间同步的开销：想要提升处理容量，就需要增加线程数。而随着线程数的增加，线程间同步的开销在整个服务的 CPU 使用占比也会越来越高。所以，如果解决不好线程间同步的问题，想单纯地增加线程数来提升处理容量行不通。

| 4.2 Bulkload 数据导入

对于上述提到引擎写压力达到瓶颈的集群，我们调研后发现其在线的实时写入一般都是比较少的，高写入量主要是用户从离线批量写数据到线上 Cellar 集群带来的。基于此，我们开发了 Bulkload 数据导入能力来解决这个问题。

分片 1 的数据文件写入到对象存储之后，客户端会将数据文件的存储地址告诉分片 1 的主所在的存储节点 DS1。然后 DS1 就会从对象存储下载分片 1 的数据文件，并把它直接插入到 LSM-Tree 引擎里面。因为这是一个完整的文件插入，所以，它可以消除引擎在普通写入时的内存排序和刷盘压力。同时，因为这个文件的数据是分片内有序的，所以，它在参与 Level 间 Compaction 时会与其他的引擎文件交叉很少，可以大幅减少多 Level compaction 的压力。

然后 DS1 会把分片 1 数据文件的对象存储地址复制发送到分片 1 的从所在的存储节点 DS2 。因为存储节点的复制只是传输数据文件的地址，所以复制速度是特别快的，也节省了很多传输的带宽。DS2 收到了分片 1 的地址后同样会从对象存储下载数据文件，并插入到引擎里面。

通过 Bulkload 解决方案，我们整体把数据离线导入的性能提升到旧版的 5 倍。比如我们的一个存储广告特征的客户使用 KV 方式从离线导数据到在线需要 14 小时，受限于在线高峰期无法导数据，如果需要继续增加特征数据，就需要扩容集群了。而扩容集群一方面会因为“木桶效应”导致请求长尾延迟问题，另一方面 Cellar 成本的上升也会抵消一部分广告收益。而在 Bulkload 功能加持下，该客户导入相同规模数据仅需不到 3 小时，它可以在不增加 Cellar 资源的情况下，将广告特征规模增加数倍，大幅提升了广告的效果。

| 4.3 线程调度模型优化

所以，为了隔离在离线请求、快慢请求的处理，让服务资源优先保证核心流量的处理，我们后来把线程模型改造成如上图所示的 4 个队列 + 4 个线程池的结构，将请求分成 4 类（读快、读慢、写快、写慢）分别放到不同的队列和线程池去处理，进而来提升服务核心流量的可用性。

但是，工作线程池按照请求类型分离之后带来一个问题，就是不同业务场景、甚至同一业务的不同时段，不同类型请求量的占比是不一样的。所以，给每个线程池分配多少线程是一个很棘手的问题。

当调度线程评估后决定做线程资源调配时，它就会发送调度指令到相应队列中，当线程池里的线程获取并执行了这个指令后，就实现了线程资源的调配。比如，它想给读快线程池增加线程，就会给空闲线程池的队列发送一个调度指令，空闲线程池的线程取到这个指令后，就会将自己加入到读快队列的线程池里面，去处理读快队列的请求。

当调度线程想对读慢线程池调减线程时，它会向读慢队列发送一个调度指令，读慢队列的线程获取到这个指令后，就会离开读慢线程池加入到空闲线程池。通过调度线程准实时的毫秒级负载统计、调度，我们实现了线程池资源的快速动态分配。对于每一个线程池的共享线程，也不再需要去轮询其他线程池的队列了，只需要专心处理自己队列的请求即可，大幅降低了线程池资源调度的 CPU 消耗。

| 4.4 线程RTC模型改造

针对这个问题，我们对线程队列模型又做了如上图右侧所示的改造。新的模型下，我们让网络线程直接去做读请求的处理，对于能够命中内存引擎的读请求，其处理模型就是一个 RTC（Run-to-Completion）模型。

具体来讲，当网络线程收到一个请求之后，会先判断是否为一个读请求，如果是，就会直接去读内存引擎。我们服务的内存引擎会缓存硬盘引擎上的热点数据，如果内存引擎命中的话，网络线程就可以直接返回结果给客户端。这样在网络线程内就实现了请求的闭环处理，相比原来的模型可以去除所有因请求流转造成的 CPU 资源消耗。而对于写和读未命中内存引擎的请求，仍然需要经过原来的请求处理路径，去硬盘引擎读或者写数据。

| 4.5 内存引擎无锁化

对于 HashMap，我们做了单写多读的无锁链表改造。同时，通过引入 RCU 机制实现了异步的内存回收，解决了读请求与写请求内存释放操作的冲突，实现了读请求处理全程的无锁化。写请求虽仍需要加锁，但我们对写做了锁粒度的优化，可以大幅提升并发度。比如我们把 SlabManager 的访问由一把大锁改成每个内存尺寸的管理链表单独一把锁，这样在分配和释放不同尺寸内存页的时候就可以实现并发。同时 RCU 机制下的内存异步回收，也解决了写线程回收内存时可能被阻塞的问题，进一步提升了写性能。

| 4.6 Cellar可用性的挑战

| 4.7 双向同步冲突自动解决

5 发展规划和业界趋势

未来，根据技术栈自上而下来看，我们的规划主要覆盖服务、系统、硬件三个层次。

首先，在服务层主要包括三点：

• 第一，Squirrel && Cellar 去 ZK 依赖。如前所述，Squirrel 集群变更到客户端的通知是依赖 ZK 来实现的，Cellar 的中心节点选主和元数据存储也是依赖 ZK 实现的。但 ZK 在大规模变更、通知场景下，它的处理能力是无法满足我们的需求的，很容易引发故障。所以，Squirrel 会去掉对 ZK 的依赖，改为使用公司内的配置管理、通知组件来实现集群变更到客户端的通知。Cellar 会通过在中心节点间使用 Raft 协议组成 Raft 组，来实现选主和元数据多副本强一致存储（注：本文整理自 DatafunSummit 2023 演讲，此工作当前已完成开发，处于灰度落地阶段）。
• 第二，向量引擎。大模型训练、推理场景有很多向量数据存储和检索需求，业界很多 NoSQL、SQL 数据库都支持了向量引擎能力。KV 存储作为高性能的存储服务，如果支持了向量引擎，可大幅提升大模型训练、推理的效率。
• 第三，云原生。当前美团的 KV 服务规模很大，相应的运维成本也比较高。所以，我们计划做一些服务云原生部署、调度方面的探索，向更高运维自动化水平迈进。

其次是系统层，计划对 Kernel Bypass 技术做一些探索和研发落地，比如新版内核支持的 io_uring、英特尔的 DPDK、SPDK 技术等。由于 KV 存储是典型的高吞吐服务，它的网络 IO、硬盘 IO 压力都很大，Kernel Bypass 技术可以大幅提升服务的 IO 能力，降低访问延迟和成本。

6 本文作者

泽斌，来自美团基础研发平台/基础技术部。