微信后台基于时间序的海量数据冷热分级架构设计实践
微信的后台数据存储随着微信产品特性的演进，经历了数次的架构改造，才形成如今成熟的大规模分布式存储系统，有条不紊的管理着由数千台异构机型组成的机器集群，得以支撑每天千万亿级的访问、键值以及 PB 级的数据。
作为以手机为平台的移动社交应用，微信内大部分业务生成的数据是有共性可言的：数据键值带有时间戳信息，并且单用户数据随着时间在不断的生成。我们将这类数据称为基于时间序的数据。比如朋友圈中的发表，或者移动支付的账单流水等业务生成的数据都满足这样的特征。基于时间序的数据都天然带有冷热分明属性――这是由手机的物理特性决定的，它的尺寸有限的屏幕所展示的数据只能分屏，通过手指的滑动，平滑而又连续的沿时间轴依次访问――通常是由最新生成的数据，慢慢回溯到较早前的数据。同时朋友圈等业务都是信息读扩散的应用场景，这就意味着它们生成的后台数据具有读多写少的鲜明特征。
通过堆机器来横向扩展存储自然可以应对如上的各种挑战，然而在成本预算紧张的前提下，机器数目是有限的。在这种情况下，基于时间序的海量数据的冷热分级架构便应运而生。该架构正是为了应对后台日益膨胀的这类数据，本着充分利用机器资源，发挥各种硬件介质特长的原则，结合数据的冷热分明、读多写少的访问特征而开发和设计出来的。它基于数据分层的理念，根据不同时间段的数据在访问热度和数据量上的差异，定制不同的服务策略，在纵向上扩展存储的边界。横向扩展存储是易于理解的，通过向原集群中增加相同类型的机器――其中必然涉及到一轮历史数据的迁移――最终新旧机器负载均衡，彼此之间并无差异的对外提供服务。在这种方案下，数据横向流动，系统一视同仁的对待，显然并无因地制宜思想的容身之所。而纵向扩展存储的架构便提供了这样一种思路：
对热点数据，数据量少，但承担的访问流量大，我们当然是希望它们能常驻内存，因此系统提供了有强一致保证的内存层，在应对突发流量时，也可在不涉及历史数据迁移的前提下，单独、动态的快速扩展内存层。
对历史数据，数据存量大，但承担的访问量非常有限，我们当然是不希望用昂贵的固态硬盘来存储它们，因此，系统提供了廉价的机械盘层，并且有一套透明的冷数据剥离和批量下沉的流程，将存储层中历史数据源源不断的抽离到机械盘层。
通过这样的一种纵向分层、单独扩展的思路，即为我们系统提供了极大的灵活性，解决了节日期间存储层面临的内存瓶颈，以从长远的角度为我们缓解了成本压力，解决了存储层面临的磁盘容量瓶颈。
当然一套成功的大型分布式系统仅有这些是不够的，还必须包括数据多副本复制策略以及分区算法等，也要有能应对复杂的现网运营环境的能力。我们结合各层的服务特点，制订了相对应的数据强一致算法，如内存层通过版本号控制来保证与存储层的完全一致，存储层通过 Paxos Group 实现多副本容灾，而机械盘层则通过串行写来保证。我们同时也实现了自己的去中心化的数据路由算法，确保了数据和流量的均匀分布，并且保证这种特性在横向扩展后依然成立。
通过如上工作的努力，环环相扣，我们的基于时间序的海量数据的冷热分层架构成功的应对了 PB 级数据、千亿级访问以及万亿级键值带来的挑战。
系统设计
数据模型
本文提及的海量数据的冷热分级架构是专门服务于基于时间序的数据，它们主要特征为：
a). 数据键值带有时间戳信息 ;
b). 单用户数据随着时间在不断的生成。
我们设计的架构强依赖于特性 a)，各个环节基本上是依赖于键值中的时间戳来分发数据或者进行数据排序的。至于键值中的时间戳如何生成、全局是否维持统一时间、如何维持等则不在本文的讨论范围，通常这由前端的业务特性以及后台的时间服务器策略决定的。
而特性 b) 则保证了本架构的必要性、实用性。如果数据规模有限，以用户的账户信息举例，它就像我们日常生活中的户口本，它只有一份，对单用户而言不会新增。则我们通常用固定的机器集群存储就可以，并且鲜有变更。而我们要处理的是用户的日记本、或者记账簿，它们每天都在不断生成新数据。
我们以现网某个集群的实例情况举例，说明下此类业务数据有如下的特点：
1.、数据量大，PB 级数据，万亿级键值，并且在源源不断的生成中，然而新生成的数据相较于历史存量数据占比小。下图展示了该集群数据在各时间段的一个占比情况。
2、访问量大，峰值可达每分钟数十亿次访问，尤其是在节日期间，用户高涨的热情更可以转化成平日三至五倍的访问量。同时具有冷热分明、读多写少 (读写比例甚至可达 100：1) 的访问特征，比如节日期间倍增的访问通常是对节日期间生成的新增数据的访问。下图展示了该集群访问在各时间段的一个占比情况。
3、数据安全性要求高，这类数据通常是用户感知敏感数据，一旦丢失，转化成的用户投诉率高。
存储层
数据强一致性保证
业务要求系统必须保证在数据的多份副本之间保持强一致性。――这是一个历久弥新的挑战。我们将分内存层、存储层、机械硬盘层分别来考虑数据的强一致性维持。
强一致缓存
正如前文描述，内存层作为一种强一致性分布式缓存，它完全是向存储层对齐的，自身无法判别数据有效性，本身多副本之间也没有交互的必要。它对前端而言是只读的，所有的写请求并不通过它，它只能算是存储层中数据的一个视图。所以它对前端数据有效性的承诺完全是依赖于存储层的正确性的。
Paxos Group
我们基于 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。
转自“计算机与网络安全”，作者杨平安
作为以手机为平台的移动社交应用，微信内大部分业务生成的数据是有共性可言的：数据键值带有时间戳信息，并且单用户数据随着时间在不断的生成。我们将这类数据称为基于时间序的数据。比如朋友圈中的发表，或者移动支付的账单流水等业务生成的数据都满足这样的特征。基于时间序的数据都天然带有冷热分明属性――这是由手机的物理特性决定的，它的尺寸有限的屏幕所展示的数据只能分屏，通过手指的滑动，平滑而又连续的沿时间轴依次访问――通常是由最新生成的数据，慢慢回溯到较早前的数据。同时朋友圈等业务都是信息读扩散的应用场景，这就意味着它们生成的后台数据具有读多写少的鲜明特征。
- 在微信的实际应用场景中，这类数据的主要特点包括：数据量大、访问量大、重要程度高等。这些特点在现网的实际运营过程中，给我们带来了非常大的挑战，主要包括：
- 数据量大，需求的存储容量高――基于时间序的数据通常不会删除，而是随着时间不断积累，数据量达到 PB 级别，相应需要的存储空间也与日俱增；
- 访问量大，节日效应明显――基于时间序的数据往往是热点业务生成的数据，它们的访问量居高不下，基本维持在每分钟数十亿次的级别。尤其是在节日期间，瞬发访问量更可达平日的三至五倍；
- 重要性高，用户感知明显，数据一旦丢失，导致用户不能正常使用产品，并因此而转化成的投诉率高。
通过堆机器来横向扩展存储自然可以应对如上的各种挑战，然而在成本预算紧张的前提下，机器数目是有限的。在这种情况下，基于时间序的海量数据的冷热分级架构便应运而生。该架构正是为了应对后台日益膨胀的这类数据，本着充分利用机器资源，发挥各种硬件介质特长的原则，结合数据的冷热分明、读多写少的访问特征而开发和设计出来的。它基于数据分层的理念，根据不同时间段的数据在访问热度和数据量上的差异，定制不同的服务策略，在纵向上扩展存储的边界。横向扩展存储是易于理解的，通过向原集群中增加相同类型的机器――其中必然涉及到一轮历史数据的迁移――最终新旧机器负载均衡，彼此之间并无差异的对外提供服务。在这种方案下，数据横向流动，系统一视同仁的对待，显然并无因地制宜思想的容身之所。而纵向扩展存储的架构便提供了这样一种思路：
对热点数据，数据量少，但承担的访问流量大，我们当然是希望它们能常驻内存，因此系统提供了有强一致保证的内存层，在应对突发流量时，也可在不涉及历史数据迁移的前提下，单独、动态的快速扩展内存层。
对历史数据，数据存量大，但承担的访问量非常有限，我们当然是不希望用昂贵的固态硬盘来存储它们，因此，系统提供了廉价的机械盘层，并且有一套透明的冷数据剥离和批量下沉的流程，将存储层中历史数据源源不断的抽离到机械盘层。
通过这样的一种纵向分层、单独扩展的思路，即为我们系统提供了极大的灵活性，解决了节日期间存储层面临的内存瓶颈，以从长远的角度为我们缓解了成本压力，解决了存储层面临的磁盘容量瓶颈。
当然一套成功的大型分布式系统仅有这些是不够的，还必须包括数据多副本复制策略以及分区算法等，也要有能应对复杂的现网运营环境的能力。我们结合各层的服务特点，制订了相对应的数据强一致算法，如内存层通过版本号控制来保证与存储层的完全一致，存储层通过 Paxos Group 实现多副本容灾，而机械盘层则通过串行写来保证。我们同时也实现了自己的去中心化的数据路由算法，确保了数据和流量的均匀分布，并且保证这种特性在横向扩展后依然成立。
通过如上工作的努力，环环相扣，我们的基于时间序的海量数据的冷热分层架构成功的应对了 PB 级数据、千亿级访问以及万亿级键值带来的挑战。
系统设计
数据模型
本文提及的海量数据的冷热分级架构是专门服务于基于时间序的数据，它们主要特征为：
a). 数据键值带有时间戳信息 ;
b). 单用户数据随着时间在不断的生成。
我们设计的架构强依赖于特性 a)，各个环节基本上是依赖于键值中的时间戳来分发数据或者进行数据排序的。至于键值中的时间戳如何生成、全局是否维持统一时间、如何维持等则不在本文的讨论范围，通常这由前端的业务特性以及后台的时间服务器策略决定的。
而特性 b) 则保证了本架构的必要性、实用性。如果数据规模有限，以用户的账户信息举例，它就像我们日常生活中的户口本，它只有一份，对单用户而言不会新增。则我们通常用固定的机器集群存储就可以，并且鲜有变更。而我们要处理的是用户的日记本、或者记账簿，它们每天都在不断生成新数据。
我们以现网某个集群的实例情况举例，说明下此类业务数据有如下的特点：
1.、数据量大，PB 级数据，万亿级键值，并且在源源不断的生成中，然而新生成的数据相较于历史存量数据占比小。下图展示了该集群数据在各时间段的一个占比情况。
2、访问量大，峰值可达每分钟数十亿次访问，尤其是在节日期间，用户高涨的热情更可以转化成平日三至五倍的访问量。同时具有冷热分明、读多写少 (读写比例甚至可达 100：1) 的访问特征，比如节日期间倍增的访问通常是对节日期间生成的新增数据的访问。下图展示了该集群访问在各时间段的一个占比情况。
3、数据安全性要求高，这类数据通常是用户感知敏感数据，一旦丢失，转化成的用户投诉率高。
存储层
数据强一致性保证
业务要求系统必须保证在数据的多份副本之间保持强一致性。――这是一个历久弥新的挑战。我们将分内存层、存储层、机械硬盘层分别来考虑数据的强一致性维持。
强一致缓存
正如前文描述，内存层作为一种强一致性分布式缓存，它完全是向存储层对齐的，自身无法判别数据有效性，本身多副本之间也没有交互的必要。它对前端而言是只读的，所有的写请求并不通过它，它只能算是存储层中数据的一个视图。所以它对前端数据有效性的承诺完全是依赖于存储层的正确性的。
Paxos Group
我们基于 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。
转自“计算机与网络安全”，作者杨平安
