美团大规模 KV 存储挑战与架构实践
KV 存储作为美团一项重要的在线存储服务，承载了在线服务每天万亿级的请求量，并且保持着 99.995% 的服务可用性。在 DataFunSummit 2023 数据基础架构峰会上，我们分享了《美团大规模 KV 存储挑战与架构实践》，本文为演讲内容的整理。文章主要分为四个部分：第一部分介绍了美团 KV 存储发展历程；第二部分分享了内存 KV Squirrel 挑战和架构实践；第三部分阐述了持久化 KV Cellar 挑战和架构实践；最后一部分介绍了未来的发展规划。希望这些内容对大家有所帮助或启发。
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 资源消耗，这样会造成极大的资源浪费。
除了资源的浪费以外，Gossip 消息过多，也会更多抢占用户请求处理线程的资源，进而会导致用户请求经常被 Gossip 消息的处理所阻塞，再导致用户请求产生更多的超时，影响服务可用性。
3.2 Gossip优化
为了解决上述的扩展性问题，我们对社区的 Gossip 方案进行了优化。首先针对 Gossip 传输的消息，我们通过 Merkle Tree 对其做了一个摘要，把集群 Gossip 通信的数据量减少了90%以上。服务端节点仅需要对比 Hash 值即可判断元数据是否有更新，对于存在更新的情况也能快速判断出更新的部分，并仅对此部分元数据进行获取、更新，大幅降低了 Gossip 消息处理的资源消耗。同时，我们还增加了一个周期性的元数据全量同步功能，来解决可能因 Hash 冲突导致元数据无法更新的问题。
针对上述提到的 Gossip 消息处理影响业务请求的问题，我们把 Gossip 消息处理功能剥离到一个单独的心跳线程里，并且由心跳线程来更新集群拓扑的元数据。对于处理用户请求的工作线程，仅需要对元数据进行读操作，可以做到无锁读。这样的话，Gossip 请求处理就对业务请求完全没有影响了。
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 的过程。
这个方案的优点很明显，生成 RDB 的过程不会阻塞服务请求处理，并且因为是实时的发送一个个 KV 数据，所以就不需要等 RDB 生成好就可以向从库复制数据了，大幅提升了数据同步的速度。但因为全量数据迭代、复制是在工作线程去做的，而不是在子进程内。所以，该方案会占用一部分工作线程的资源。另外，因为是以 KV 为粒度做复制的，所以，如果哈希表里面有大 KV 的话，可能会因为工作线程复制大 KV 耗时过长，造成用户请求等待耗时的上升。
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 跨地域容灾的架构如上图所示，它通过一个集群间同步服务在两个不同地域的集群之间做数据同步。这个同步服务首先伪装为上游集群节点的 slave 把它的 RDB 和增量 log 拉取过来，然后再把拉取到的数据转化成写请求发到下游的集群，从而实现了一个集群间的数据同步。通过这样的架构，我们解决了服务的跨地域容灾问题。并且，通过在集群间搭建正反两个方向的两个同步任务，就能实现集群间的双向同步。这样的话，用户服务就可以只在本地域写，但同时能读到两个地域分别写入的数据，解决了单向同步需要跨地域写的问题。
双向同步有两个经典问题需要解决：
一个是循环复制问题。我们为每个 Squirrel 集群标记了不同的 cluster id，并且记录了每个 KV 的初始写入 cluster id，同步服务会过滤掉与目标集群 cluster id 相同的数据，以避免发生循环复制。
还有一个是数据冲突问题。我们一开始是通过业务层面保证在每个地域写不同的 Key 来解决的。但是在双向同步的运行过程中，还是会有一些极端场景可能会出现两个地域并发写同一个 Key。比如像机房网络故障场景，业务会把故障机房的所有写入都切到正常机房。
但由于我们的集群间复制是异步的，可能故障机房有一些最新的 Key 变更还没有复制到正常机房的集群。而如果在业务将写切换到正常机房后，又写入了相同 Key 的不同变更，就会产生两个同步集群的数据冲突。在机房网络恢复之后，业务还是要把一部分流量切回到之前故障的集群上，恢复到跨地域容灾的架构。
但由于两个集群可能已经有数据冲突了，所以，在业务切回之前，就需要对数据做冲突校验和修复。但是对大数据量集群来说，数据校验和修复的耗时可能会长达数天。在这样长的时间内，只有一个单地域集群来支撑业务，无论是从容灾还是容量的角度来看，都是有较大风险的。
3.9 双向同步冲突自动解决
为了解决上述的双向同步数据冲突问题，我们实现了一个基于数据写入本地时间的 last write win 冲突自动解决功能。
如上图所示，在 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 挑战和架构实践
上图是我们最新的 Cellar 架构图，它跟阿里开源的 Tair 主要有两个层面的不同。
第一个是 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 数据导入能力来解决这个问题。
Bulkload 整体架构如上图所示，它在普通写入流涉及的客户端和存储节点之外，还引入了 S3 对象存储来做导入数据的中转。下面我们看下 Bulkload 具体的写入流程：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 线程调度模型优化
我们最初的线程模型与开源版 Tair 一样，网络线程池做收发包，收到的包经过一个队列转出到一个大的工作线程池做请求处理。这样的线程模型，很容易发生请求间的互相影响。比如用户有离线数据导入到 Cellar 的时候，就很容易导致在线读请求的超时。又比如当有大 Value 读写的时候，工作线程处理会比较慢、占用线程的时间会很长，导致正常 Value 读写的快请求只能在队列等待，进而导致大量超时。
所以，为了隔离在离线请求、快慢请求的处理，让服务资源优先保证核心流量的处理，我们后来把线程模型改造成如上图所示的 4 个队列 + 4 个线程池的结构，将请求分成 4 类（读快、读慢、写快、写慢）分别放到不同的队列和线程池去处理，进而来提升服务核心流量的可用性。
但是，工作线程池按照请求类型分离之后带来一个问题，就是不同业务场景、甚至同一业务的不同时段，不同类型请求量的占比是不一样的。所以，给每个线程池分配多少线程是一个很棘手的问题。
针对这个问题，我们增加了一个线程动态调度的逻辑：每个线程池都有一部分线程被设定为可共享线程，如果线程池比较空闲，共享线程就会去轮询其他的队列，处理一些繁忙线程池的请求，这样就达到了自适应调整各线程池资源的效果。但是在这样的架构下，虽然解决好了请求隔离性和不同请求类型线程资源的动态分配问题，但我们发现随着节点流量的上涨，共享线程对于其他队列的轮询会消耗越来越多的 CPU 资源，而且集群业务的负载分布与默认的线程数设置差异越大，这个消耗的占比也会越高。
为了解决上述线程池资源自适应调度带来的 CPU 消耗问题，我们对分离后的线程、队列模型做出了如上图的改造。改进后的线程模型最主要的特点是引入了一个调度线程和一个空闲线程池，这个调度线程会实时统计每个线程池的负载，来评估每个线程池是否需要增加或减少线程并做出调度动作，空闲线程池用来存放当前空闲的可用于调配的线程资源。
当调度线程评估后决定做线程资源调配时，它就会发送调度指令到相应队列中，当线程池里的线程获取并执行了这个指令后，就实现了线程资源的调配。比如，它想给读快线程池增加线程，就会给空闲线程池的队列发送一个调度指令，空闲线程池的线程取到这个指令后，就会将自己加入到读快队列的线程池里面，去处理读快队列的请求。
当调度线程想对读慢线程池调减线程时，它会向读慢队列发送一个调度指令，读慢队列的线程获取到这个指令后，就会离开读慢线程池加入到空闲线程池。通过调度线程准实时的毫秒级负载统计、调度，我们实现了线程池资源的快速动态分配。对于每一个线程池的共享线程，也不再需要去轮询其他线程池的队列了，只需要专心处理自己队列的请求即可，大幅降低了线程池资源调度的 CPU 消耗。
通过上述的线程队列模型优化，服务在高负载场景下可以提高 30% 以上的吞吐量。
4.4 线程RTC模型改造
上图左侧画的是我们服务请求的 IO 处理路径：一个请求的处理流程会经过网络线程、请求队列、工作线程、内存和硬盘引擎。这个设计的问题是，请求在不同线程之间流转会造成大量的 CPU 切换以及 CPU 高速缓存的 Cache Miss，进而造成大量的 CPU 资源消耗。在大流量场景下，这样的 CPU 消耗也是很可观的一笔资源。
针对这个问题，我们对线程队列模型又做了如上图右侧所示的改造。新的模型下，我们让网络线程直接去做读请求的处理，对于能够命中内存引擎的读请求，其处理模型就是一个 RTC（Run-to-Completion）模型。
具体来讲，当网络线程收到一个请求之后，会先判断是否为一个读请求，如果是，就会直接去读内存引擎。我们服务的内存引擎会缓存硬盘引擎上的热点数据，如果内存引擎命中的话，网络线程就可以直接返回结果给客户端。这样在网络线程内就实现了请求的闭环处理，相比原来的模型可以去除所有因请求流转造成的 CPU 资源消耗。而对于写和读未命中内存引擎的请求，仍然需要经过原来的请求处理路径，去硬盘引擎读或者写数据。
新的线程模型，经实测在 80% 内存引擎命中率场景下，服务读吞吐可以提升 30%+。虽然新的线程队列模型只实现了读缓存命中请求的 RTC，但其实在线流量大多都是读多写少且热点数据明显、内存引擎命中率比较高的场景，所以，新模型上线后在大多数的业务集群都取得了明显的性能提升。
4.5 内存引擎无锁化
当单机请求量达到了一定规模之后，我们发现服务内的锁操作会占用很多的 CPU 资源。经分析发现，大多数的锁操作都发生在上节内容提到的内存缓存引擎上。如上节所述，所有请求都会经过内存引擎，且大部分请求都会在内存引擎命中并返回结果给客户端。所以，大部分请求都是纯内存处理，这个过程中的锁操作就很容易成为瓶颈。针对这个问题，我们对内存引擎做了无锁化改造，其改造后的结构如下图所示：
整体改造主要跟上图的 HashMap 和 SlabManager 两个数据结构有关（其他数据结构在图中已略掉）。HashMap 是存储 KV 数据的核心结构，它把 Key 通过 Hash 算法散列到不同的 Slot 槽位上，并利用链表处理 Hash 冲突；SlabManager管理不同尺寸内存页的申请和释放，它利用链表把相同尺寸的内存页放到一起管理。
对于 HashMap，我们做了单写多读的无锁链表改造。同时，通过引入 RCU 机制实现了异步的内存回收，解决了读请求与写请求内存释放操作的冲突，实现了读请求处理全程的无锁化。写请求虽仍需要加锁，但我们对写做了锁粒度的优化，可以大幅提升并发度。比如我们把 SlabManager 的访问由一把大锁改成每个内存尺寸的管理链表单独一把锁，这样在分配和释放不同尺寸内存页的时候就可以实现并发。同时 RCU 机制下的内存异步回收，也解决了写线程回收内存时可能被阻塞的问题，进一步提升了写性能。
内存引擎通过无锁化加 RCU 技术的改造，读处理能力提升了 30% 以上。
4.6 Cellar可用性的挑战
同 Squirrel 一样，Cellar 也通过建设集群间数据同步能力，实现了跨地域的容灾架构。不同的是，Cellar 因为是自研，无需考虑与社区版本的兼容性，同时为了简化部署结构、降低运维成本，它把集群间数据同步功能做到了存储节点内部。如上图示例的北京集群 A 节点、上海集群 H 节点，在接收到写入之后，除了要做集群内的数据同步以外，还需要把写入数据同步到跨地域的另一个集群上。
Cellar 也可以通过配置两个方向的跨集群数据同步链路，实现完全的本地域读写。Cellar 由于采用了存储节点内建的方案，它的集群间复制通过使用定制的复制包来甄别客户写入和复制写入，并只为客户写入生成复制 log 来避免循环复制，相对Squirrel 会简单一点。但同样的，这种架构也会遇到极端情况下，双向同步导致的数据冲突问题。
4.7 双向同步冲突自动解决
如上图所示，Cellar 也实现了类似 Squirrel 的基于数据写入本地时间的 last write win 冲突自动解决方案。但 Cellar 的方案有一点区别是，它没有通过在每条数据记录 cluster id 的方式解决时钟回退、两次变更写入的本地时间相同的问题，而是引入了 HLC（Hybrid Logic Clock）时钟来解决这个问题。
因为 HLC 可以保证每个集群写入数据的时钟是单调递增的。所以，接收端是不用担心对端复制过来的数据有时间戳相同的问题。而对于两个集群分别写入，时间戳相同且 HLC 的逻辑时钟刚好也相同的情况，可以通过比较集群配置的 cluster id（不会存储到每条 KV 数据内）来决定最终哪个数据可以写入。
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 能力，降低访问延迟和成本。
最后是硬件层，计划对计算型硬件的应用做一些探索，比如配备了压缩卡的 SSD，可以将服务引擎层使用 CPU 做的数据压缩工作卸载到压缩卡上，释放出 CPU 资源做更高价值的计算工作。KV 服务是典型的低延迟、高网络负载的服务。所以，我们也计划对 RDMA 网络做一些探索，以期进一步降低服务访问延迟、提升网络处理能力。
阅读更多
| 在美团公众号菜单栏对话框回复【2023年货】、【2022年货】、【2021年货】、【2020年货】、【2019年货】、【2018年货】、【2017年货】等关键词，可查看美团技术团队历年技术文章合集。
