微信 PaxosStore:海量数据冷热分级架构

导语

本文整理自笔者在“腾讯大讲堂”的演讲。

作者介绍：杨平安，来自广州的微信事业群，在腾讯已经工作五年。

主要分享内容：

• 为何公司卓越研发金奖花落PaxosStore；
• 隐匿在业务后的大数据统计特征；
• 架构迭代的现实与实现

在作这份PPT的时候，我对自己这五年的时光进行了一下简单的回顾，发现可以分成两个主题。

这两个主题就在我的职业生涯中不断交织，爱恨情仇，发展到了今天。

第一个主题呢，是我搞海量存储，详细来说就是不少业务的存储基本上是在我手上从无到有到今天的。

给大家列了一个海量存储架构的演进，大家可以看到这儿分别是支持单机十亿键值、支持冷热数据分离、支持分布式缓存、支持Paxos协议。

支持两字背后都是对它的架构进行的脱胎换骨的改造，还有数据的挪腾，并不简单。

再来说第二个主题，我将它称为：海量存储搞我。

微信这个产品是2011年发布的。

这五六年里不少业务也进行了数次的迭代，以朋友圈举例，朋友圈广告、春节的红包照片等，期间用户的访问量也跟腾讯股票的K线图一样，翻了数倍。

这些需求，对用户而言叫作玩法。

但我们这些后台存储呢，就只能称为死法。花样百出，被现实各种吊打。

这个是我们第一年的时候，数据存储的一个存储引擎的模型。

在第一年的时候，我们并没有专门为核心业务的数据定制一套专门的存储。而是使用了通用的存储模型，叫作bitcask存储，即日志型的存储。

所有的写都是在文件的最新位置追加写。可见它的写是很轻量的。

内存中会有个索引，指向了数据在磁盘中的位置。

每次读数据，都是先在内存中找到它的索引，然后再按照索引位置直接去磁盘上读。

这个模型的优点是显而易见的，它真的是非常轻量。

在不考虑有数据缓存的情况下，任何的一次读，都只会产生一次随机读盘。非常nice。

然而它的缺点也是致命的，它受限于内存。每台SSD机型的机器，32G内存，只能存储约4亿的键值。

但后面的情况是，许多业务的存储单机key量需要达到数十亿。如果我们继续使用这种类型的话，就是对磁盘空间的极度浪费。

于是第二年，我们就设计出了支持单机数十亿键值的存储系统。

我们将它称为了bok系统，就是将刚才说到的内存中的键值索引放到了磁盘上存储，存储的方式呢，也是bitcask模型。

每次写数据，都是先追加写数据文件的最新位置，然后再更新索引，将索引写到了bok文件的最新位置。需要写两次。

如果是读呢，就要先读bok目录中键值的索引，然后再根据索引去读磁盘上对应的数据。

那么在这种架构下，每次的读都会产生两次随机读盘。这个效率跟索引全内存的存储比起来，肯定是差了一截的。

但是它解决了键值爆涨的问题。

然而等到第三年的时候，当前的这套bok系统又不顶用了。

因为我们当时按照某核心业务数据量的增长速度，进行了一个预估，

大约等到2015年底的时候，该业务的数据量就会增加到3P，这大约就需要数千台SSD机型的机器来支撑。

我们应该可以通过分析核心业务的业务模型，找到一条适合它自己的存储架构。

论我们如何设计冷、热数据集群的内部实现细节，有个问题是独立的，是必须首先要解决的。

即冷、热数据集群的架构关系。

在设计这套系统的时候，我们对业界的各类方案进行了充分的调研。

发现针对我们这种“冷数据不太冷，IO瓶颈，海量key量”的场景表现的都较为乏力。

我就举一些反面教材，来说明下为什么这种架构不适合我们的应用场景。

以这类架构举例，SATA集群存储冷数据的索引及数据，它和SSD组成的热数据集群呢，是分别独立的两个模块。

每次读数据，都会先访问热数据集群，如果热数据集群不能命中， 则再访问冷数据集群。

热数据集群为了防空呢，就增加一个bloom filter组件，来降低冷数据集群的无效访问量。

这个架构最大的毛病是在TS6机器上，它的键值索引无论是全内存，还是落盘，都对机器消耗非常多。

这是另外一个方案。这个方案变聪明了一点，它将冷数据集群中的键值索引给上提到了热数据集群中。

这样的好处就是降低了冷数据集群的负担。每次业务端都通过热数据集群来获取冷数据的索引，再直接读取冷数据集群中的文件位置。一次随机读即完成。

这个架构的问题在于扩容！

如果当前的机器数已经不能满足服务，我们最常见的策略就是增加服务器数目，这时候就涉及到了旧数据的迁移。

在这种方案下，无论是扩容迁移，还是冷数据下沉，都是以单key为粒度进行的操作。

我们前面提到过，我们有万亿级别的键值，这种量级的数据流动，操作周期就太久了，将业务放在了一个不稳定的状态。

不以单key为粒度进行操作以文件为基本单位来转存冷数据，同样的以文件为基本单位来记录冷数据的键值索引。

在静态的服务器集群中，这个方案是足够好的。

但当发生扩容的时候呢？

那么这套系统就彻底失败了。

为了批量的操作数据，我们提出了最小不变块的这么一个概念。

这张图就展示了如何实现最小不变块的。

方法就是通过两阶段哈希。

我们首先将用户key进行一轮哈希，散落到数目有限的桶内。

每个桶就是一定数量key的集合，然后再将这些桶进行第二轮哈希，路由到不同的实体机器上。

通过这种方法，将用户key与机器路由隔离开来。处于中层的每个哈希桶就是一个最小不变块。

确定完最小不变块的算法后，我们就可以从整体上来规划系统的设计了。

这张图显示的呢，是我们数据一个大体的分层。

最热的数据，访问量占比70%以上，我们当然希望它是常驻内存的。

次热的数据，在SSD中就可以支撑访问需求。而最冷的那部分数据，按最小不变块聚合在冷数据集群中，SSD集群呢，也按最小不变块为基本单位，持有冷数据的索引，这样就不担心因扩容而重新组织的问题。

在整体上，由内存到SSD再到SATA盘，数据在时间维度上由热到冷。由这一点，我们联想到了Lsm-Tree算法。

这个算法呢，它是一个多组件算法。在本质上和B+树是一样的，都是一种索引建立的技术。不同的是，它将内存和磁盘划分开来，在算法中称为C0组件和C1组件。

所有的索引的变更，其实就是写数据，都在C0组件中提交。

只有当C0组件达到阀值后，才会延迟的提交到C1组件，并且是通过多路归并排序的方式。

如此一来，就将B+树中的随机IO级转换成了内存操作和顺序IO。

前面提到了，我们这种业务所有的键值都是带有毫秒级时间戳的，这样在C1组件中通过多路归并排序，就已经达到了数据的时间维度有序。

在我们的应用场景中，C0组件就是内存，存储最热的那部分数据，当内存容量满了之后，最热的数据变成次热数据，就会被迁移到C1组件，即SSD硬盘中，与SSD中原有的数据进行归并。当SSD容量也达到阀值之后，就会将最冷的那部分数据迁移到C2组件，即冷数据集群的SATA盘中。

前面的PPT也说到了，我们的问题是如何将现在的数据按照时间维度来进行分开，以方便的剥离冷数据；Lsm-tree算法就为我们指明了方向。

我们基于Lsm-Tree算法改造了热数据集群。这是它整体的一个架构图。

其实说白了，这就是一张leveldb的架构图。

我们也深入调研了leveldb的源码，如果直接使用leveldb实现lsm-tree存储，会存在一些严重的问题，例如单点文件mainfest损坏则全库难以恢复的问题，而且它内置了很多读写时候触发文件merge，数据文件索引懒加载（会引发不可控的读盘）等策略，会引发服务的抖动，在实际场景下不太适用，同时大量的动态内存分配会对机器的内存使用带来一定的不可控的因素，我们也需要结合业务特性进行细化，包括在处理冷、热数据，对如何调和CPU、磁盘IO、磁盘占用等。所以我们采用的方式是重用leveldb里面的一些成熟数据结构组件，例如skiplist，logformat等等，按我们的需求和策略去构建一套lsm引擎出来。

基于这样一种架构图，我们实现了数据在整体范围上的有序，前面也提到过存储用的key为64位的ID，其中包括毫秒级时间，因此数据有序，即是时间有序。首先要做的是数据按块进行压缩，在改造之前，冷热数据混杂，是没办法实现按块压缩的，只能以单用户数据为基本单位进行压缩，只可以达到30%左右的压缩率。而通过按数据块进行压缩，则将压缩率提高到了60%左右。这点上，就相当于节省了30%的存储成本。同时，我们利用访问特征又对冷、热数据的存储进行了各自的定制，如冷数据访问量低，就可以采用比较大的数据块进行存储，它的索引粒度就大一些；热数据访问量大，数据块就小一点，降低读盘量，并且不进行压缩，减少CPU的计算，同时为了精确防空，增加了bloom filter，只有1%的误判。通过这些手段就有效的平衡了CPU使用、IO性能、读盘量三者之间的关系。还有一些其它的优化，比如索引启动加载、90%命中率的记录级缓存等，这里就不需要单条的列出来说明了。

这页PPT列了冷数据集群的一些设计要点。我想着重说明下冷数据集群的容灾模型。通过这张图，也可以看到，TS6集群一组有三台机器，分别存储相同数据的三份副本，它们分布在不同的园区，可以实现园区级容灾。为了保证数据的一致性，我们采用了三节点串行写入的模型。之所以可以这么做，是因为冷数据集群的写入任务是离线式的，我们可以控制它的写入时机及并发数。在扩容的时候，我们就可以停掉写入，直接进行数据的复制，等复制完成之后，再提交路由表。

在进行冷数据存储的时候，面临一个很重要的问题：即在单盘数据完全丢失的情况下，如何恢复。作软RAID是种方案，然而RAID10会使用一半的空间，而RAID5则需要扫描和计算数十T的数据量。

因此最终我们采用了NoRaid方案，决定从其它机器中恢复。

这就有必要将三副本作到盘级别的一致。

因此，我们在设计的时候，也通过预计算数据路由的方式，实现了盘级别的负载均衡。

这页图说明的是三机串行写入的一个过程，它分为两个阶段，其一是占位阶段，这阶段确保在三机中相同的位置预分配相同长度的空间。

然后在写入阶段，将数据依次的写入到各机。每个数据块大小为定长32K，其中包括CRC校验码和用户数据。

这张图说明的是冷数据下沉的一个流程。它包括五个过程，1、2、3、4、5。

整个过程对服务而言，因为是两阶段提交，都是无损的，对客户端也是透明的。

转眼就来到了第四年。

在第三年，通过冷数据集群的搭建，我们成功的解决了磁盘容量瓶颈的问题。

第四年，我们主要面临两个挑战，一个是春节活动。

我们预估用户的流量会瞬时涨五倍左右。

因此我们对业界方案又进行了调研。增加一个临时存储服务器，也是业界曾出现过的案例。显而易见的是，在节日期间的访问增量，都是由春节期间的新增的活跃数据所带来的。因此为这些活跃数据搭建一个临时的存储服务器。客户端根据访问key所带的时间范围来决定转发到哪个集群。这种方案算是一种变相的扩容，优点是它不涉及旧数据的迁移。同时为了均衡临时存储服务器与原存储集群的压力，可以按比例的来分配活跃数据的流量。但是它的缺点也非常致命，这种方案要求数据的路由是限死的，不可能在面临洪峰的时候快速扩容。因此我们决定抛弃这个想法。

缓存层可以按比例来分摊存储层的流量，但与临时存储服务器不同的是，它支持快速扩容，也可以动态调整流量比例。但如果我们要采取搭建缓存这个方案，就不得不思考如下的问题：第一个是如何保证数据的一致性，通常的作法有保证严格更新，对存储层数据的更新，都确保缓存也相应的修改成功。但这种情况在面临机器离线的环境时就变得复杂了，因此我们需要一套简单而又行之有效的分布式缓存协议，来确保不读到过期的数据。另外一个需要思考的问题是缓存层的机器应该如何分布，使我们能更好的容灾，尽量确保不因机器的离线，而导致缓存的失效，引发模块的抖动。

存储访问具有读多写少的特征，读写比例达到了100：1，因此我们完全可以使用读更新的策略，即写时不更新缓存。需要在读的时候确保缓存层的数据是最新的就可以了。我们通过版本号来完成了这个请求。在存储层和缓存层都为每份数据维持了一套版本号。每次读缓存层的数据，都需要用缓存层的版本去存储层验证，是否与存储层的版本号相等，若相等，则说明缓存数据为新，直接返回，否则存储层就要把最新数据返回给缓存层。如此一来，在一次RPC请求过程中，就同时的完成了数据有效性的辨别，以及过期情况下的缓存更新。那么这个协议能够成功应用，就必须依赖于存储层获取数据版本号是个轻量级操作，并且可以达到高tps。

我们通过缓存层的轻重分离，达到了这个目标。改造前，存储层已经有单机级别的item cache，其中包含数据缓存和版本号缓存，命中率也达到了85%，算是比较高的。然而我们在运营的过程中，发现了这样一个现象，因为数据的平均大小是1.5k，版本号只有定长11字节，这两类大小差异很多，但访问频度一致的数据混在同一个缓存的时候，就会出现大数据清洗挤压小数据的情况。我们称之为黑暗森林法则。因为版本号只需要很少的内存就应该可以达到很高的命中率，却会不断的被大数据把内存抢走，增加整体的流动性。因此，我们开发出了一个极其紧凑，包含千万级LRU链的定长数据缓存。实现也非常简单，它就是一个二维数组和一个头部。一维用来作为哈希桶，另外一维当作LRU链。 每次读写都通过数组内数据的挪动，来更新LRU。

这样一个实现确保了内存的高效使用，仅用4G的内存空间，就缓存了约4亿的key，达到了98%的命中率。我们也调研过其它的方案，比如说多阶哈希缓存，它的内存使用率也仅能达到83%。存储层通过这样的一个改造，获取版本号由每秒6w，增加到每秒10万。提升了约60%多。

由于存储层的单机已经实现较高的命中率，即使缓存层提供更多的内存，命中率也提高有限。首先在逻辑层到缓存层批量请求中的key具有用户维度的相关性，它们可能属于同一个用户。但由于存储层以key的哈希值来路由，所以这些key都被打散掉，分散到了不同的机器上。为了最大效率的合并请求，我们必须保证路由到相同存储机器的数据，也必须路由到相同的缓存层机器。因此就必须让缓存层的机器与存储层在组数上对齐。实践的过程中，我们是缓存层10组，而存储层40组，比例为1：4。这样缓存层每合并240个请求，再去访问存储层，平均下来，每个存储层机器批量数目为10。

这页PPT说明的是合并所使用到的批量化技术的一个具体实现。我们在请求合并的时候，限制合并历史数据的访问，来实现快慢分离，通过这样一个工作，我们将存储层的请求从7ms降到了5ms。

OK。到了第五年，Paxos协议席卷了整个微信后台的存储。

然而地位更重要的热数据集群，依然采用的是quorum协议，而只有两份数据副本。

后面出于更高数据安全性的要求，我们必须把热数据集群中的数据也提升到三份副本。

面临的问题依然是成本压力。如果两份变三份，那需要的存储空间也要提供一半，就需要额外增加300台的TS8。

可不可以不要这些成本，就实现更高的数据安全性呢？

具有冷热分明的业务特征，一天内数据的更新占了总更新的92%，一个月内的数据的更新占了95%。这就意味着数据冷却很快。这就给我们提供了一个思路：按照时间点来切换存储。

因为我们之前搭建的冷数据集群是按照三个副本来存储历史数据的。通过切换存储，我们可以确保新增数据的高可用性。剩下未切换的就是当前的存量数据，它的增量很少，三个月整个模块也只增加100G左右。因此，我们可以利用冷数据下沉的任务，慢慢的来消化这部分的存量数据。

好，再来说下切换新存储。它是我们整体paxos工程化的一个环节。在过去的一年，我们深度的思考了基于paxos算法的一致性协议，针对当前现网数据的复杂性，设计出全新的分布式架构，逐渐的替换当前的quorum kv。目前已经上线到用户账户存储、消息存储、朋友圈时间线存储等核心模块。这个过程中沉淀出成熟的非租约paxos k\v组件和certain组件，它们分别服务于不同的数据类型和应用场景。

 但是采用逻辑端双写就涉及到前端的修改及上线过程。因为snslogicsvr\snskvproxy的上线周期都很长，我们不想将太多的时间浪费到发现问题－修复问题－上线这样的循环中。因此，我们将上述两种方案结合起来。 同时在上线的过程中，  存储层兼容新旧模式，每次大改造都支持回退。    目前我们已经在上海及中国香港上线了此项改造，实现全程无故障切换。

附件：

海量数据冷热分级架构.pptx