本文将为你介绍，微信后台的一种基于时间序的海量数据冷热分级架构。应对 PB 级数据、每天万亿级访问、键值带来的挑战，微信技术团队是这样做的。 微信的后台数据存储随着微信产品特性的演进，经历了数次的架构改造，才形成如今成熟的大规模分布式存储系统，有条不紊的管理着由数千台异构机型组成的机器集群，得以支撑每天千万亿级的访问、键值以及 PB 级的数据。
作为以手机为平台的移动社交应用，微信内大部分业务生成的数据是有共性可言的：数据键值带有时间戳信息，并且单用户数据随着时间在不断的生成。我们将这类数据称为基于时间序的数据。比如朋友圈中的发表，或者移动支付的账单流水等业务生成的数据都满足这样的特征。基于时间序的数据都天然带有冷热分明属性――这是由手机的物理特性决定的，它的尺寸有限的屏幕所展示的数据只能分屏，通过手指的滑动，平滑而又连续的沿时间轴依次访问――通常是由最新生成的数据，慢慢回溯到较早前的数据。同时朋友圈等业务都是信息读扩散的应用场景，这就意味着它们生成的后台数据具有读多写少的鲜明特征。
在微信的实际应用场景中，这类数据的主要特点包括：数据量大、访问量大、重要程度高等。这些特点在现网的实际运营过程中，给我们带来了非常大的挑战，主要包括：
数据量大，需求的存储容量高――基于时间序的数据通常不会删除，而是随着时间不断积累，数据量达到 PB 级别，相应需要的存储空间也与日俱增；
访问量大，节日效应明显――基于时间序的数据往往是热点业务生成的数据，它们的访问量居高不下，基本维持在每分钟数十亿次的级别。尤其是在节日期间，瞬发访问量更可达平日的三至五倍；
重要性高，用户感知明显，数据一旦丢失，导致用户不能正常使用产品，并因此而转化成的投诉率高。
通过堆机器来横向扩展存储自然可以应对如上的各种挑战，然而在成本预算紧张的前提下，机器数目是有限的。在这种情况下，基于时间序的海量数据的冷热分级架构便应运而生。该架构正是为了应对后台日益膨胀的这类数据，本着充分利用机器资源，发挥各种硬件介质特长的原则，结合数据的冷热分明、读多写少的访问特征而开发和设计出来的。它基于数据分层的理念，根据不同时间段的数据在访问热度和数据量上的差异，定制不同的服务策略，在纵向上扩展存储的边界。横向扩展存储是易于理解的，通过向原集群中增加相同类型的机器――其中必然涉及到一轮历史数据的迁移――最终新旧机器负载均衡，彼此之间并无差异的对外提供服务。在这种方案下，数据横向流动，系统一视同仁的对待，显然并无因地制宜思想的容身之所。而纵向扩展存储的架构便提供了这样一种思路：
对热点数据，数据量少，但承担的访问流量大，我们当然是希望它们能常驻内存，因此系统提供了有强一致保证的内存层，在应对突发流量时，也可在不涉及历史数据迁移的前提下，单独、动态的快速扩展内存层。
对历史数据，数据存量大，但承担的访问量非常有限，我们当然是不希望用昂贵的固态硬盘来存储它们，因此，系统提供了廉价的机械盘层，并且有一套透明的冷数据剥离和批量下沉的流程，将存储层中历史数据源源不断的抽离到机械盘层。
通过这样的一种纵向分层、单独扩展的思路，即为我们系统提供了极大的灵活性，解决了节日期间存储层面临的内存瓶颈，以从长远的角度为我们缓解了成本压力，解决了存储层面临的磁盘容量瓶颈。
当然一套成功的大型分布式系统仅有这些是不够的，还必须包括数据多副本复制策略以及分区算法等，也要有能应对复杂的现网运营环境的能力。我们结合各层的服务特点，制订了相对应的数据强一致算法，如内存层通过版本号控制来保证与存储层的完全一致，存储层通过 Paxos Group 实现多副本容灾，而机械盘层则通过串行写来保证。我们同时也实现了自己的去中心化的数据路由算法，确保了数据和流量的均匀分布，并且保证这种特性在横向扩展后依然成立。
通过如上工作的努力，环环相扣，我们的基于时间序的海量数据的冷热分层架构成功的应对了 PB 级数据、千亿级访问以及万亿级键值带来的挑战。
本文提及的海量数据的冷热分级架构是专门服务于基于时间序的数据，它们主要特征为：
a). 数据键值带有时间戳信息 ;
b). 单用户数据随着时间在不断的生成。
我们设计的架构强依赖于特性 a)，各个环节基本上是依赖于键值中的时间戳来分发数据或者进行数据排序的。至于键值中的时间戳如何生成、全局是否维持统一时间、如何维持等则不在本文的讨论范围，通常这由前端的业务特性以及后台的时间服务器策略决定的。
而特性 b) 则保证了本架构的必要性、实用性。如果数据规模有限，以用户的账户信息举例，它就像我们日常生活中的户口本，它只有一份，对单用户而言不会新增。则我们通常用固定的机器集群存储就可以，并且鲜有变更。而我们要处理的是用户的日记本、或者记账簿，它们每天都在不断生成新数据。
我们以现网某个集群的实例情况举例，说明下此类业务数据有如下的特点：
1.、数据量大，PB 级数据，万亿级键值，并且在源源不断的生成中，然而新生成的数据相较于历史存量数据占比小。下图展示了该集群数据在各时间段的一个占比情况。
2、访问量大，峰值可达每分钟数十亿次访问，尤其是在节日期间，用户高涨的热情更可以转化成平日三至五倍的访问量。同时具有冷热分明、读多写少 (读写比例甚至可达 100：1) 的访问特征，比如节日期间倍增的访问通常是对节日期间生成的新增数据的访问。下图展示了该集群访问在各时间段的一个占比情况。
3、数据安全性要求高，这类数据通常是用户感知敏感数据，一旦丢失，转化成的用户投诉率高。
系统由三个层次组成，如图所求，分别是内存层、存储层（热数据存储层）以及机械磁盘层（冷数据存储层）。从时间轴上看，它们服务的数据由热至冷。如下图所示：
从客户端的角度看，三层都是并列的，客户端都会直接的与某层中的某台机器发生通信。具体的区别点在于，内存层和机械磁盘层对客户端而言是只读的。所有的写都是由客户端直接写向存储层。我们将去中心化的配置分发到客户端机器上，配置的类型包括内存层路由、存储层路由以及其它元数据，客户端根据配置中的时间分隔点以及流量比例，来决定将当前的读请求分发到内存层还是存储层的具体机器上。配置支持快速分发和动态加载，可以在秒级实现更新。
机械磁盘层的路由对客户端而言是透明的，存储层保存了下沉到机械磁盘层的数据链接，链接包含了文件编号、内部偏移和大小，而客户端对此是不知情的。当已下沉数据的读请求分发到存储层机器上时，存储层会计算出该数据各副本在冷数据存储层对应的机器地址，然后将它和文件链接一起回复给客户端。客户端再按照随机的策略在多副本之间选择一份读取，从这个角度看，冷数据存储层对客户端而言更像个远程文件系统，而 inode 信息和路由表是放在热数据存储层的。
下面我们再详细的分析各层的设计策略。
内存层从表现上更像是一个缓存代理，然而普通的缓存在处理数据有效性上是乏力的。常见的策略如写时淘汰，每次写存储层之前，都先清理掉缓存中相应的数据，确保失效。然而数据在缓存中通常也是多副本的，这个方案即无法处理网络分区错误，并且写时淘汰也会产生多次 RPC 请求，过份的消耗系统资源。另外一种常见策略是有限的数据一致性，即过时淘汰的策略。在将数据写入缓存时，会附带一个有效时间，在这个有效期内，该数据一直被认为是正确的，并不关心真实情况是如何的。这种缓存只能应用于对数据实时性要求不高的服务。对微信的敏感业务而言，我们更需要能保证数据强一致的分布式缓存。
我们通过版本号来实现了这一目的。我们为缓存中的每一份数据都维持了一份版本号，存储层中相应的也有一份。只有当缓存中的版本号与存储层的版本号达到一致时，才会认为缓存中的数据是有效的。所以，客户端每次对内存层的读请求，都会由缓存层相应的产生一次读请求发到存储层。在一次 RPC 请求中完成有效性的识别以及过期数据的更新。
从直觉上看，采用这种方案的强一致缓存并没有降低存储层的访问压力。因为客户端对缓存层的请求，与缓存层对存储层的请求是 1：1 的。然而这个方案点的关键在于，我们成功的疏解了存储层的内存瓶颈。将存储层缓存数据的功能，转移到缓存层的内存上。我们现在对存储层的要求就是能够尽量的缓存更多的版本号，提供高效的版本号访问能力就可以了。从这种意义上来看，这个强一致性缓存就是存储层内存的延伸。因此，我们将它称为内存层。它的优势在于可动态的调整流量比例，并且可以在访问高峰期快速的扩容。后面的章节我们也描述了如何通过工程手段优化版本号交互带来的资源消耗。
为了系统的健壮性，一些异常情况也是需要考虑的，如果一台内存层机器突然离线，会有数十 G 的缓存数据失效，我们当然不会希望这数十 G 数据的压力，会全部的落到一台存储机器的磁盘上。――这无疑会引起系统的抖动。因此，我们按照组的方式来部署了内存层。每组有多台机器。一份数据可能在这多台机器内有多个副本。客户端通过随机的次序访问这些机器。这样就尽力避免了单结点失效对整个系统的影响。
我们在内存层中设计了简单、轻量的支持变长数据的缓存结构。每台机器包含数十条 LRU 链，每条链都是一个共享内存形式的一维数组。所有的数据都追加写在数组的最新位置，到尾部后就从头开始循环。自然，这样的结构需要一个索引来记录数据的位置。这种方式固然浪费一些内存空间，但避免了内存的动态分配。
存储层在整个系统架构中处于核心的位置。内存层和机器硬盘层都依赖于它的实现。前文提及，提供高效轻量的版本号访问能力是强一致内存层实现的关键。同时，源源不断的将冷数据下沉到机械硬盘层的需求，就暗示了在存储层必须有这样一种特性：冷数据是易于从所有数据中剥离，并且收集的。――这样就意味着，如果在存储层中数据是平坦的，冷热数据混杂在一起，那么我们在抽离冷数据的时候，就要把硬盘中所有的数据遍历一轮，无疑会消耗比较多的系统资源。
因此我们采用了 lsm-tree 算法来实现这一需求。该算法和 B+ 树一样是种建立索引的技术。不同的是它基于多组件 (C0\C1 等组件)，通过延迟提交和归并排序的方式，将 B+ 树的随机 IO 转变成了内存操作和顺序 IO。在我们的访问模型下，所有的写都是热点数据，只会提交到 C0 组件。然后在适当的时机，同 C1 组件中的数据进行多路归并排序。通过该算法，我们可以同时实现数据分层和数据有序的目的。
Leveldb 是 Google 公司开源的存储引擎库，它正是基于 lsm-tree 算法的思想开发出来的。因此，我们复用了它成熟的数据结构组件，如日志格式、数据文件格式、内存表格式等。然而它其中的一些运行时策略，却会给我们的现网运营带来麻烦。比如说运行时不受限的 compact 策略、数据文件索引的懒加载等，会触发不可控的读盘，造成服务的抖动；同时大量的动态内存分配也会对机器的内存使用带来一定不可控的因素。因此，我们抛弃了这些运行时行为，定义了自己的管理策略，使系统变得更加可控。同时，我们利用不同数据的访问差异，对冷、热数据的存储进行了各自的定制，按照时间段定义按块压缩的粒度、索引的粒度等，行之有效的调和了 CPU、内存、磁盘容量、磁盘 IO 等系统资源之间的转换关系。
冷数据的链接和冷集群的路由表，都是记录在存储层中而对前端不可见的。具体的设计思想，我们在下节中详述。
机械硬盘容量虽大，但是 IO 性能低下，故障率高。一种常见的思路是冷数据存储层独立与热数据存储层，而对客户端直接可见――客户端持有一份冷数据存储层的路由，并且独自路由――这无疑是种简单、易于理解的方案，但是在我们的应用场景中面临着两个问题：无法精确防空以及加剧机械硬盘层的 IO 紧张。
定义 TB 访问量为每 TB 数据的每秒的访问次数。在我们的应用场景中，每 TB 历史数据的实际访问量设为 N，则机械硬盘的服务能力仅为 N 的一半。如果冷数据存储层独立，则它需要自己维持所有的数据索引，而内存容量不足以支持数十 T 数据的索引，只能将索引落盘，则每次对数据的读取都要带来两次随机读盘。因此，我们将冷数据索引以及冷数据存储层的路由表，都放到了热数据存储层中，而对前端不可见。
为了容灾，我们必须为每份数据存储多份副本。如果采用双副本方案，则系统需要冗余 50% 的访问能力，以应对另外一份副本失效的情况，在 io 瓶颈的前提下，这种方案是不可取的。因此我们采用了三副本方案，只要冗余三分之一的能力。每份副本分布在不同的园区，可以实现园区级的容灾。
由于机械盘容量大、计算能力差，我们采用 NO RAID 的方式组织了盘组。为了更好的实现单盘失效导致数据丢失的故障的灾后恢复，我们实现了同组三台机器在盘级别数据的完全相同。为了达到盘级别的负载均衡，我们通过预计算路由、硬编码的方式，实现了 (数据 ->机器 ->盘 ->文件) 的单调映射，由数据的键值可以直接定位到盘的索引以及文件的编号。
作为机械硬盘层的补充，一个冷数据下沉的模块是必须的，它作为冷数据存储层的唯一 Writer，我们通过两阶段提交的方式确保了下沉过程的透明性，通过控制流程发起时机保证资源使用不影响现网服务，通过预占位、串行写入的方式，确保了数据在冷数据存储层文件级别的完全一致。
业务要求系统必须保证在数据的多份副本之间保持强一致性。――这是一个历久弥新的挑战。我们将分内存层、存储层、机械硬盘层分别来考虑数据的强一致性维持。
正如前文描述，内存层作为一种强一致性分布式缓存，它完全是向存储层对齐的，自身无法判别数据有效性，本身多副本之间也没有交互的必要。它对前端而言是只读的，所有的写请求并不通过它，它只能算是存储层中数据的一个视图。所以它对前端数据有效性的承诺完全是依赖于存储层的正确性的。
我们基于 Paxos Group 实现了存储层的数据一致性，通过采用无租约的方式，使得系统在保证强一致性的前提下达到了最大的可用性。Paxos 算法是由 Lesile Lamport 在论文中首提的，它唯一的作用是在多个参与者之间唯一的确定一个常量值。――这点同分布式存储没有直接关联的。我们在 Paxos 算法的基础上，设计出基于消息驱动的 Paxos Log 组件――每一条操作日志都要 Paxos 算法来确定，再进一步实现了基于 Paxos Log 的强一致性读写。
Paxos Group 因为采用了无主模型，组内所有机器在任一时刻都处于相同的地位。Paxos 算法本质是个多副本同步写算法，当且仅当系统中的多数派都接受相同值后，才会返回写成功。因此任意单一节点的失效，都不会出现系统的不可用。
强一致性写协议的主要问题来源于 Paxos 算法本身，因为要确保数据被系统内的多数派接受，需要进行多阶段的交互。我们采用如下的方法，解决了 paxos 算法写过程中出现的问题：基于 fast accept 协议优化了写算法，降低了写盘量以及协议消息发送、接收次数，最终实现了写耗时和失败的降低；基于随机避让、限制单次 Paxos 写触发 Prepare 的次数等方法，解决了 Paxos 中的活锁问题。
强一致性读协议本身和 Paxos 算法并没有太大的关系，只要确认多副本之间的多数派，即可获取到最新的数据。我们通过广播的方式获取到集群中多数机器（包含自身）的 paxos log 的状态，然后判断本机数据的有效性。
当系统中的单机节点失效，数据完全丢失的时候――这种情况是可以算是 Paxos 算法的盲区，因为该算法基于所有的参与者都不会违背自己曾经的承诺，即拜占庭失败而导致的数据不一致。――而这种情况在现网运营中可谓是常态，因此，我们引入了 Learner Only 模式。在该模式下故障机只接收已提交的数据，而不参与 Paxos 协议的写过程，意即不会因数据丢失而违背任何承诺。然后通过异步 catch up 和全量数据校验快速从其它副本中恢复数据。
为了防止多节点同时失效，我们将数据的多副本分布在不同园区的机器上。园区是同一个城市不同数据中心的概念。如此，我们的结构足以应对单数据中心完全隔离级别的灾难。
因为对客户端透明，冷数据下沉流程作为机械硬盘层的唯一写者，则该层的数据一致性是易于实现的。我们通过三副本串行写入、全部提交才算成功的方式来实现了多副本之间的数据一致性。
作为补充，冷数据集群为数据块增加了 CRC 校验和一致性恢复队列，当单机数据不可用 (丢失或者损坏) 时，首先客户端会跳转到其它备份中读 (三机同时对外提供读服务)，一致性恢复队列会异步的从其它备份数据块中恢复本机数据。
因为采用了 No Raid 方式组织的盘组，并且同组机器间盘级别数据文件一致，在单盘故障引发数据丢失时，只要从其它机器相同序盘中传输数据文件即可。
数据分区的主要目的是为了确保同层机器间的负载均衡，并且当机器规模发生变化后，在最终仍然可以达到负载均衡的一种状态。
经典的一致性哈希算法的初衷是为了健壮分布式缓存，基于运行时动态的计算哈希值和虚拟节点来进行寻址。数据存储与分布式缓存的不同在于，存储必须保证数据映射的单调性，而缓存则无此要求，所以经典的一致性哈希通常会使用机器 IP 等作为参数来进行哈希，这样造成的结果一方面是数据的落点时而发生改变，一方面是负载通常不均衡。因此我们改造了此算法。
我们通过预计算虚拟节点随机数的方法，生成了割环点同实体机器之间的映射表。该映射表最多可支持一千组的集群规模，满足在任意组数情况下，实体机器间割段长度维持差异在 2% 以内；并且增加任意组数 (总组数上限不超过一千组)，变动后的实体机器间的割段长度依然维持差异在 2% 以内。我们将此映射表硬编码，在运行时避免了计算的过程，数据根据键值哈希值寻址时，只要经过一次二分查找即可获取到对应的实体机器的编号。我们在内存层、存储层以及机械硬盘层都采用了这个映射表，保证了数据在各层路由算法的一致。在工程实现方面，我们可以合理使用这个特性来批量合并请求，以降低资源消耗，这在稍后的章节会有详细描述。
组是数据分区的独立单元，是虚拟节点对应的实体单位。组之间是互相独立的。每组由多台物理机器组成，这是 Paxos Group 生效的基本单位。一份数据包括的多份副本分别散落在组内的各台机器上。为了在组内机器上保证负载均衡，我们同样设计了一套算法，规定了数据副本之间的访问优先级，前端会依优先级逐一的请求数据，只要成功获取，即中断这个过程。然后我们再将副本按优先级均匀的散落在组内机器上，如此即可实现组内负载的均衡。
静态映射表是非常灵活的，在不达到组数上限的情况下，可以任意的增加一组或者多组机器。当然这个过程中一些数据的路由映射发生了改变，则就涉及到了历史数据的挪腾。为了在挪腾的过程中不影响服务，保证数据依然可读可写，我们开发出了对前端透明的，基于迁移标志位，通过数据双写和异步挪数据的方式实现的安全的、可回退的数据迁移流程。
存储层和机械硬盘层通过冷数据链接耦合在了一起。因为两层使用了相同的映射表，那么当存储层因扩容而发生迁移时，那么冷数据链接无疑也要重新寻址，进行一轮重新定位。如果我们以单键值为粒度记录冷数据链接和进行冷数据下沉，那么在万亿键值的语境下，效率无疑是低下。因此我们设计了最小不变块的算法，通过两阶段哈希，使用中间的哈希桶聚集数据，将数据键值和冷数据存储层的机器路由隔离开来。通过该算法，我们可以实现：批量的转存冷数据、热数据存储层批量的以块 (block) 为单位记录冷数据链接、当热数据存储层发生扩容时，块 (block) 内的数据不因扩容被打散掉，而可以整体的迁移到新目标机上。
糟糕的工程实现可以毁掉一个完美的系统设计，因此，如何在工程实现的过程中，通过技术的手段，提升系统的表现，同样值得重视。
内存层的设计严重依赖存储层数据版本号的高效获取，那自然是版本号请求全落在内存中就可以了。因此，针对这种情况我们为定长的版本号设计了一套极简的、轻量的、行之有效的缓存――内存容量不足以支撑版本号全缓存。
它的数据结构只是一个二维数组，一维用来构建 hash 链，一维用来实现 LRU 链。每次读或者写都需要通过数组内数据的挪动，来进行更新。如此一来，我们就通过千万级数目的 LRU 链群，实现了缓存整体的 LRU 淘汰。它具有定长，可共享内存搭载，进程重启不丢失、内存使用率高等优点。
对系统服务器而言，前端访问过来的某个请求，其对应的逻辑操作都是串行的，我们自然可以梳理这个串行流程中的 CPU 消耗点进行优化。然而当主要的瓶颈被逐渐的消灭掉后，CPU 消耗点变得分散，优化效果就变得微乎其微了。因此，我们只能寻找其它突破点。
我们发现在存储引擎、一致性协议算法的实现流程中，逻辑操作步骤多，涉及到网络交互，硬盘读写等过程。因此，我们决定合并不同请求中的相同步骤，实现批量化操作，极大的优化了 CPU 消耗。
合并的代价即是耗时略有增加，我们通过快慢分离，只针对热点数据请求中的逻辑操作进行合并，去掉了耗时中的不稳定因子，减少了耗时抖动。
既然单机的逻辑操作性能已经得到了极大的提升，那么前后端的网络交互阶段，包括接入层的打包解包、协议处理等环节，成为了资源的主要消耗点。参考批量操作的经验，我们同样使用批量化的技术来优化性能――即将后台访问过来的单条请求 (Get) 在内存层聚合成一次批量请求 (Batch Get)。
因为每个数据都是根据键值单独进行路由的，如果要进行请求合并，我们就必须确保同一个批量请求内的数据，都会寻址到相同的 Paxos Group 上。因此，我们必须在内存层将落到同一台存储机器上的 Get 请求聚合起来。我们首先在内存层和存储层采用了相同的路由算法，然后将内存层的组数同存储层的组数进行对齐，来完成了这一目标。
在设计的阶段，我们充分的调研了业界的各类方案，大到系统的整体架构，小到具体的技术点。各种方案自有应用场景、各有千秋，不能单纯以好坏区别，我们同样基于自己的业务场景，谨慎的选择合适的方案，或者弃而不用。在此尽量叙述。
处理 SNS 类业务生成的数据，业界有多种的冷热分离架构可以参考。我们以 Facebook 的 Cold Storage 系统举例而言，它也是基于冷热分层的想法，设计出了服务它们照片业务数据的存储方案。不同的是它采用了软硬件结合的方法，一方面定制专门的服务器（包括硬盘、电源等）和数据中心，一方面降低冷数据的备份数、增加纠删码等手段。
然而它们的经验我们是无法彻底套用的，主要两种原因：我们可使用的机器机型是固定的，不存在自己定制硬件的条件。同时它处理的是照片这种大 value 的数据。而我们基本上是文本这种类型的小 value 数据。从前文提及的 TB 访问量角度来看，它们处理的数据是容量瓶颈的，而我们处理的是 IO 瓶颈的，可以算是不太冷的冷数据带来的挑战。所以，我们只能实现自己的冷数据管理策略。
同样，业界有诸多关于如何实现数据一致性的方案。包括我们微信自研的 Quorum 协议，它是一种 NWR 协议，采用异步同步的方式实现数据多副本。即然是异步同步，那在多副本达到最终一致，必然存在一个时间差，那么在单机出现离线的情况下，就会有一定概率导致数据的不可用。而我们追求的是在单点故障下，所有的数据都保证强可用性。
因此，我们采用了无主的去中心化的 Paxos Group 实现了这一目标，其中非租约是 PaxosStore 架构的一个创新亮点。在故障时通常系统是抖动的，会有时断时续的状况，常见的租约做法在这种场景下容易出现反复切换主机而导致长期不可用，而 PaxosStore 的非租约结构能够轻松应对，始终提供良好的服务。PaxosStore 核心代码正在整理开源当中，预计四季度会正式发布，同时该项目的底层框架也基于我们已开源的协程库 github.com/libco。
作者介绍
杨平安，12 年加入腾讯，在微信技术架构部的基础平台组负责存储系统的开发。先后参与了 QuorumKV\PaxosStore 等项目，伴随微信存储成长。一路起来，见证了微信存储架构的演变。
今日荐文
点击下方图片即可阅读
