微信后台基于时间序的海量数据冷热分级架构设计实践

1、写在前面

微信的后台数据存储随着微信产品特性的演进，经历了数次的架构改造，才形成如今成熟的大规模分布式存储系统，有条不紊的管理着由数千台异构机型组成的机器集群，得以支撑每天千万亿级的访问、键值以及 PB 级的数据。 作为以手机为平台的移动社交应用，微信内大部分业务生成的数据是有共性可言的：数据键值带有时间戳信息，并且单用户数据随着时间在不断的生成。我们将这类数据称为基于时间序的数据。比如朋友圈中的发表，或者移动支付的账单流水等业务生成的数据都满足这样的特征。基于时间序的数据都天然带有冷热分明属性――这是由手机的物理特性决定的，它的尺寸有限的屏幕所展示的数据只能分屏，通过手指的滑动，平滑而又连续的沿时间轴依次访问――通常是由最新生成的数据，慢慢回溯到较早前的数据。同时朋友圈等业务都是信息读扩散的应用场景，这就意味着它们生成的后台数据具有读多写少的鲜明特征。 在微信的实际应用场景中，这类数据的主要特点包括：数据量大、访问量大、重要程度高等。

通过堆机器来横向扩展存储自然可以应对如上的各种挑战，然而在成本预算紧张的前提下，机器数目是有限的。在这种情况下，基于时间序的海量数据的冷热分级架构便应运而生。该架构正是为了应对后台日益膨胀的这类数据，本着充分利用机器资源，发挥各种硬件介质特长的原则，结合数据的冷热分明、读多写少的访问特征而开发和设计出来的。它基于数据分层的理念，根据不同时间段的数据在访问热度和数据量上的差异，定制不同的服务策略，在纵向上扩展存储的边界。横向扩展存储是易于理解的，通过向原集群中增加相同类型的机器――其中必然涉及到一轮历史数据的迁移――最终新旧机器负载均衡，彼此之间并无差异的对外提供服务。在这种方案下，数据横向流动，系统一视同仁的对待，显然并无因地制宜思想的容身之所。

通过这样的一种纵向分层、单独扩展的思路，即为我们系统提供了极大的灵活性，解决了节日期间存储层面临的内存瓶颈，以从长远的角度为我们缓解了成本压力，解决了存储层面临的磁盘容量瓶颈。 当然一套成功的大型分布式系统仅有这些是不够的，还必须包括数据多副本复制策略以及分区算法等，也要有能应对复杂的现网运营环境的能力。我们结合各层的服务特点，制订了相对应的数据强一致算法，如内存层通过版本号控制来保证与存储层的完全一致，存储层通过 Paxos Group 实现多副本容灾，而机械盘层则通过串行写来保证。我们同时也实现了自己的去中心化的数据路由算法，确保了数据和流量的均匀分布，并且保证这种特性在横向扩展后依然成立。 通过如上工作的努力，环环相扣，我们的基于时间序的海量数据的冷热分层架构成功的应对了 PB 级数据、千亿级访问以及万亿级键值带来的挑战。

2、系统设计

1数据模型

而特性 b) 则保证了本架构的必要性、实用性。如果数据规模有限，以用户的账户信息举例，它就像我们日常生活中的户口本，它只有一份，对单用户而言不会新增。则我们通常用固定的机器集群存储就可以，并且鲜有变更。而我们要处理的是用户的日记本、或者记账簿，它们每天都在不断生成新数据。 我们以现网某个集群的实例情况举例，说明下此类业务数据有如下的特点：

• 1. 数据量大：PB 级数据，万亿级键值，并且在源源不断的生成中，然而新生成的数据相较于历史存量数据占比小。下图展示了该集群数据在各时间段的一个占比情况；

2. 访问量大：峰值可达每分钟数十亿次访问，尤其是在节日期间，用户高涨的热情更可以转化成平日三至五倍的访问量。同时具有冷热分明、读多写少 (读写比例甚至可达 100：1) 的访问特征，比如节日期间倍增的访问通常是对节日期间生成的新增数据的访问。下图展示了该集群访问在各时间段的一个占比情况；

• 3. 数据安全性要求高：这类数据通常是用户感知敏感数据，一旦丢失，转化成的用户投诉率高。

2系统架构

系统由三个层次组成，如图所求，分别是内存层、存储层（热数据存储层）以及机械磁盘层（冷数据存储层）。 从时间轴上看，它们服务的数据由热至冷，如下图所示：

从客户端的角度看，三层都是并列的，客户端都会直接的与某层中的某台机器发生通信。具体的区别点在于，内存层和机械磁盘层对客户端而言是只读的。所有的写都是由客户端直接写向存储层。我们将去中心化的配置分发到客户端机器上，配置的类型包括内存层路由、存储层路由以及其它元数据，客户端根据配置中的时间分隔点以及流量比例，来决定将当前的读请求分发到内存层还是存储层的具体机器上。配置支持快速分发和动态加载，可以在秒级实现更新。

下面我们再详细的分析各层的设计策略。

3内存层

我们通过版本号来实现了这一目的。我们为缓存中的每一份数据都维持了一份版本号，存储层中相应的也有一份。只有当缓存中的版本号与存储层的版本号达到一致时，才会认为缓存中的数据是有效的。所以，客户端每次对内存层的读请求，都会由缓存层相应的产生一次读请求发到存储层。在一次 RPC 请求中完成有效性的识别以及过期数据的更新。

从直觉上看，采用这种方案的强一致缓存并没有降低存储层的访问压力。因为客户端对缓存层的请求，与缓存层对存储层的请求是 1：1 的。然而这个方案点的关键在于，我们成功的疏解了存储层的内存瓶颈。将存储层缓存数据的功能，转移到缓存层的内存上。我们现在对存储层的要求就是能够尽量的缓存更多的版本号，提供高效的版本号访问能力就可以了。从这种意义上来看，这个强一致性缓存就是存储层内存的延伸。因此，我们将它称为内存层。它的优势在于可动态的调整流量比例，并且可以在访问高峰期快速的扩容。后面的章节我们也描述了如何通过工程手段优化版本号交互带来的资源消耗。

我们在内存层中设计了简单、轻量的支持变长数据的缓存结构。每台机器包含数十条 LRU 链，每条链都是一个共享内存形式的一维数组。所有的数据都追加写在数组的最新位置，到尾部后就从头开始循环。自然，这样的结构需要一个索引来记录数据的位置。这种方式固然浪费一些内存空间，但避免了内存的动态分配。

4存储层

因此我们采用了 lsm-tree 算法来实现这一需求。该算法和 B+ 树一样是种建立索引的技术。不同的是它基于多组件 (C0\C1 等组件)，通过延迟提交和归并排序的方式，将 B+ 树的随机 IO 转变成了内存操作和顺序 IO。在我们的访问模型下，所有的写都是热点数据，只会提交到 C0 组件。然后在适当的时机，同 C1 组件中的数据进行多路归并排序。通过该算法，我们可以同时实现数据分层和数据有序的目的。

Leveldb 是 Google 公司开源的存储引擎库，它正是基于 lsm-tree 算法的思想开发出来的。因此，我们复用了它成熟的数据结构组件，如日志格式、数据文件格式、内存表格式等。然而它其中的一些运行时策略，却会给我们的现网运营带来麻烦。比如说运行时不受限的 compact 策略、数据文件索引的懒加载等，会触发不可控的读盘，造成服务的抖动；同时大量的动态内存分配也会对机器的内存使用带来一定不可控的因素。因此，我们抛弃了这些运行时行为，定义了自己的管理策略，使系统变得更加可控。同时，我们利用不同数据的访问差异，对冷、热数据的存储进行了各自的定制，按照时间段定义按块压缩的粒度、索引的粒度等，行之有效的调和了 CPU、内存、磁盘容量、磁盘 IO 等系统资源之间的转换关系。 冷数据的链接和冷集群的路由表，都是记录在存储层中而对前端不可见的。具体的设计思想，我们在下节中详述。

5机械硬盘层

机械硬盘容量虽大，但是 IO 性能低下，故障率高。一种常见的思路是冷数据存储层独立与热数据存储层，而对客户端直接可见――客户端持有一份冷数据存储层的路由，并且独自路由――这无疑是种简单、易于理解的方案，但是在我们的应用场景中面临着两个问题：无法精确防空以及加剧机械硬盘层的 IO 紧张。 定义 TB 访问量为每 TB 数据的每秒的访问次数。在我们的应用场景中，每 TB 历史数据的实际访问量设为 N，则机械硬盘的服务能力仅为 N 的一半。如果冷数据存储层独立，则它需要自己维持所有的数据索引，而内存容量不足以支持数十 T 数据的索引，只能将索引落盘，则每次对数据的读取都要带来两次随机读盘。因此，我们将冷数据索引以及冷数据存储层的路由表，都放到了热数据存储层中，而对前端不可见。 为了容灾，我们必须为每份数据存储多份副本。如果采用双副本方案，则系统需要冗余 50% 的访问能力，以应对另外一份副本失效的情况，在 io 瓶颈的前提下，这种方案是不可取的。因此我们采用了三副本方案，只要冗余三分之一的能力。每份副本分布在不同的园区，可以实现园区级的容灾。

由于机械盘容量大、计算能力差，我们采用 NO RAID 的方式组织了盘组。为了更好的实现单盘失效导致数据丢失的故障的灾后恢复，我们实现了同组三台机器在盘级别数据的完全相同。为了达到盘级别的负载均衡，我们通过预计算路由、硬编码的方式，实现了 (数据 ->机器 ->盘 ->文件) 的单调映射，由数据的键值可以直接定位到盘的索引以及文件的编号。

作为机械硬盘层的补充，一个冷数据下沉的模块是必须的，它作为冷数据存储层的唯一 Writer，我们通过两阶段提交的方式确保了下沉过程的透明性，通过控制流程发起时机保证资源使用不影响现网服务，通过预占位、串行写入的方式，确保了数据在冷数据存储层文件级别的完全一致。

3、数据强一致性保证

业务要求系统必须保证在数据的多份副本之间保持强一致性。――这是一个历久弥新的挑战。我们将分内存层、存储层、机械硬盘层分别来考虑数据的强一致性维持。

1强一致缓存

正如前文描述，内存层作为一种强一致性分布式缓存，它完全是向存储层对齐的，自身无法判别数据有效性，本身多副本之间也没有交互的必要。它对前端而言是只读的，所有的写请求并不通过它，它只能算是存储层中数据的一个视图。所以它对前端数据有效性的承诺完全是依赖于存储层的正确性的。

2Paxos Group

Paxos Group 因为采用了无主模型，组内所有机器在任一时刻都处于相同的地位。Paxos 算法本质是个多副本同步写算法，当且仅当系统中的多数派都接受相同值后，才会返回写成功。因此任意单一节点的失效，都不会出现系统的不可用。 强一致性写协议的主要问题来源于 Paxos 算法本身，因为要确保数据被系统内的多数派接受，需要进行多阶段的交互。我们采用如下的方法，解决了 paxos 算法写过程中出现的问题：基于 fast accept 协议优化了写算法，降低了写盘量以及协议消息发送、接收次数，最终实现了写耗时和失败的降低；基于随机避让、限制单次 Paxos 写触发 Prepare 的次数等方法，解决了 Paxos 中的活锁问题。 强一致性读协议本身和 Paxos 算法并没有太大的关系，只要确认多副本之间的多数派，即可获取到最新的数据。我们通过广播的方式获取到集群中多数机器（包含自身）的 paxos log 的状态，然后判断本机数据的有效性。

为了防止多节点同时失效，我们将数据的多副本分布在不同园区的机器上。园区是同一个城市不同数据中心的概念。如此，我们的结构足以应对单数据中心完全隔离级别的灾难。

3串行写入

因为对客户端透明，冷数据下沉流程作为机械硬盘层的唯一写者，则该层的数据一致性是易于实现的。我们通过三副本串行写入、全部提交才算成功的方式来实现了多副本之间的数据一致性。 作为补充，冷数据集群为数据块增加了 CRC 校验和一致性恢复队列，当单机数据不可用 (丢失或者损坏) 时，首先客户端会跳转到其它备份中读 (三机同时对外提供读服务)，一致性恢复队列会异步的从其它备份数据块中恢复本机数据。 因为采用了 No Raid 方式组织的盘组，并且同组机器间盘级别数据文件一致，在单盘故障引发数据丢失时，只要从其它机器相同序盘中传输数据文件即可。

4、数据分区

1静态映射表

数据分区的主要目的是为了确保同层机器间的负载均衡，并且当机器规模发生变化后，在最终仍然可以达到负载均衡的一种状态。 经典的一致性哈希算法的初衷是为了健壮分布式缓存，基于运行时动态的计算哈希值和虚拟节点来进行寻址。数据存储与分布式缓存的不同在于，存储必须保证数据映射的单调性，而缓存则无此要求，所以经典的一致性哈希通常会使用机器 IP 等作为参数来进行哈希，这样造成的结果一方面是数据的落点时而发生改变，一方面是负载通常不均衡。因此我们改造了此算法。

2组内均衡

组是数据分区的独立单元，是虚拟节点对应的实体单位。组之间是互相独立的。每组由多台物理机器组成，这是 Paxos Group 生效的基本单位。一份数据包括的多份副本分别散落在组内的各台机器上。为了在组内机器上保证负载均衡，我们同样设计了一套算法，规定了数据副本之间的访问优先级，前端会依优先级逐一的请求数据，只要成功获取，即中断这个过程。然后我们再将副本按优先级均匀的散落在组内机器上，如此即可实现组内负载的均衡。

3数据迁移

静态映射表是非常灵活的，在不达到组数上限的情况下，可以任意的增加一组或者多组机器。当然这个过程中一些数据的路由映射发生了改变，则就涉及到了历史数据的挪腾。为了在挪腾的过程中不影响服务，保证数据依然可读可写，我们开发出了对前端透明的，基于迁移标志位，通过数据双写和异步挪数据的方式实现的安全的、可回退的数据迁移流程。

4最小不变块

存储层和机械硬盘层通过冷数据链接耦合在了一起。因为两层使用了相同的映射表，那么当存储层因扩容而发生迁移时，那么冷数据链接无疑也要重新寻址，进行一轮重新定位。如果我们以单键值为粒度记录冷数据链接和进行冷数据下沉，那么在万亿键值的语境下，效率无疑是低下。因此我们设计了最小不变块的算法，通过两阶段哈希，使用中间的哈希桶聚集数据，将数据键值和冷数据存储层的机器路由隔离开来。通过该算法，我们可以实现：批量的转存冷数据、热数据存储层批量的以块 (block) 为单位记录冷数据链接、当热数据存储层发生扩容时，块 (block) 内的数据不因扩容被打散掉，而可以整体的迁移到新目标机上。

5、工程实现

糟糕的工程实现可以毁掉一个完美的系统设计，因此，如何在工程实现的过程中，通过技术的手段，提升系统的表现，同样值得重视。

1高效缓存

内存层的设计严重依赖存储层数据版本号的高效获取，那自然是版本号请求全落在内存中就可以了。因此，针对这种情况我们为定长的版本号设计了一套极简的、轻量的、行之有效的缓存――内存容量不足以支撑版本号全缓存。

它的数据结构只是一个二维数组，一维用来构建 hash 链，一维用来实现 LRU 链。每次读或者写都需要通过数组内数据的挪动，来进行更新。如此一来，我们就通过千万级数目的 LRU 链群，实现了缓存整体的 LRU 淘汰。它具有定长，可共享内存搭载，进程重启不丢失、内存使用率高等优点。

2批量操作

对系统服务器而言，前端访问过来的某个请求，其对应的逻辑操作都是串行的，我们自然可以梳理这个串行流程中的 CPU 消耗点进行优化。然而当主要的瓶颈被逐渐的消灭掉后，CPU 消耗点变得分散，优化效果就变得微乎其微了。因此，我们只能寻找其它突破点。

3请求合并

既然单机的逻辑操作性能已经得到了极大的提升，那么前后端的网络交互阶段，包括接入层的打包解包、协议处理等环节，成为了资源的主要消耗点。参考批量操作的经验，我们同样使用批量化的技术来优化性能――即将后台访问过来的单条请求 (Get) 在内存层聚合成一次批量请求 (Batch Get)。

4路由收敛

因为每个数据都是根据键值单独进行路由的，如果要进行请求合并，我们就必须确保同一个批量请求内的数据，都会寻址到相同的 Paxos Group 上。因此，我们必须在内存层将落到同一台存储机器上的 Get 请求聚合起来。我们首先在内存层和存储层采用了相同的路由算法，然后将内存层的组数同存储层的组数进行对齐，来完成了这一目标。

6、相关工作

在设计的阶段，我们充分的调研了业界的各类方案，大到系统的整体架构，小到具体的技术点。各种方案自有应用场景、各有千秋，不能单纯以好坏区别，我们同样基于自己的业务场景，谨慎的选择合适的方案，或者弃而不用。在此尽量叙述。 处理 SNS 类业务生成的数据，业界有多种的冷热分离架构可以参考。我们以 Facebook 的 Cold Storage 系统举例而言，它也是基于冷热分层的想法，设计出了服务它们照片业务数据的存储方案。不同的是它采用了软硬件结合的方法，一方面定制专门的服务器（包括硬盘、电源等）和数据中心，一方面降低冷数据的备份数、增加纠删码等手段。

同样，业界有诸多关于如何实现数据一致性的方案。包括我们微信自研的 Quorum 协议，它是一种 NWR 协议，采用异步同步的方式实现数据多副本。即然是异步同步，那在多副本达到最终一致，必然存在一个时间差，那么在单机出现离线的情况下，就会有一定概率导致数据的不可用。而我们追求的是在单点故障下，所有的数据都保证强可用性。 因此，我们采用了无主的去中心化的 Paxos Group 实现了这一目标，其中非租约是 PaxosStore 架构的一个创新亮点。在故障时通常系统是抖动的，会有时断时续的状况，常见的租约做法在这种场景下容易出现反复切换主机而导致长期不可用，而 PaxosStore 的非租约结构能够轻松应对，始终提供良好的服务。PaxosStore 核心代码正在整理开源当中，预计四季度会正式发布，同时该项目的底层框架也基于我们已开源的协程库 github.com/libco。