共计 6018 个字符，预计需要花费 16 分钟才能阅读完成。
PaxosStore 是微信设计的一套分布式存储系统，并已对外围业务存储做了架构革新。内存云是微信 PaxosStore 存储体系的组成部分，本文将分享内存云的 Paxos 革新过程。
作者简介
魏澄，微信高级工程师，目前负责微信根底存储服务，致力于强统一、高可用的大规模分布式存储架构的设计与研发。
微信存储 QuorumKV 是一个分布式的存储系统，笼罩但不限于微信后盾外围业务：账号 / 用户信息 / 关系链 / 朋友圈，等等。
过来的一年，咱们受 Google MegaStore 启发，从新设计了一套全新的分布式存储系统，即 PaxosStore 分布式存储，并于最近半年对外围业务存储做了架构革新，目前已胜利上线并实现了数千台机器的平滑切换，零碎首次拜访成功率晋升一个量级，并取得更好的容灾能力，可用性显著加强。
内存云作为微信 PaxosStore 存储体系的组成部分，目前存储着微信根底账号、音讯计数等外围用户数据，每天峰值申请高达数十亿 / 分钟，本文将向大家分享内存云的 Paxos 革新过程。
背景
微信内存云，目前有 2 千多台机器：单机内存 64GB，存储盘为机械盘。作为外围存储之一，内存云承载了根底账号、音讯计数等外围数据的存储，保障微信登录、音讯收发等微信根底性能。内存云每天服务峰值申请十多亿 / 分钟，读写比约为 3.3:1。基于 QuourmKV 的内存云具体架构如图 1 所示：
图 1 QuorumKV 架构
微信 QuourmKV 陪伴内存云走过了数次扩容，经验除夕、春晚等例行节日申请暴发增长的洗礼，也积淀着不少故障解决教训（不限内存云）。本文次要形容新架构如何根本性地改善 QuorumKV 的容灾能力（即 CAP 中，保障 C 的前提下加强 A），在不就义性能的前提下，毁灭局部故障场景下的最终失败和人为染指。
QuorumKV 实质上是一个 NWR 协定（N 为 3，W/ R 为 2）的分布式存储，和其余 NWR 协定不同的中央在于：QuorumKV 将 NWR 利用在版本上，当且仅当版本达成统一的状况下读写单机数据，从而保障强一致性。然而这里引入了 2 个问题：
- 数据写一份，依附异步同步至对机；
- 当 WR 无奈造成少数时，单 Key 不可用，需进行修复。
不要小看了这 2 个问题，这是目前 QuorumKV 的绝大部分日常故障导致失败的本源，特地是对写量大的模块而言：
- 数据机故障离线，局部 Key 最新数据在故障机上，不可用；
- 版本机故障离线，局部 Key(版本不平)仲裁失败，不可用。
表 2 分布式协定比照
明确问题的本源是 QuorumKV 采纳的 NWR 分布式协定，那么在保障强一致性的前提下可行的解决方案为 Paxos/Raft 分布式协定。表 2 列出了咱们在协定抉择上的一些考量：采纳无租约的形式使得零碎在保障强一致性的前提下达到最大的可用性；相对而言，租约的形式必然引入主备切换导致的不可用。
在比照调研过一些业界计划（etcd/megastore 等）后，咱们最终确定新架构协定计划是：无租约版 Paxos 分布式协定（如图 3 所示）。
图 3 新架构(无租约版 Paxos 分布式协定)
面向挑战
接下来须要做的事件是，基于 Paxos 分布式协定在机械盘上搭建一套稳固高性能的分布式存储。
挑战 1：Paxos 分布式协定
咱们在谈及 Paxos 算法时，通常会提及 Leslie Lamport 大神的 Paxos Made Simple；但基于 Paxos 算法的分布式协定不止与此，图 4 列出一个残缺协定波及的 3 个档次。
图 4 Paxos 分布式协定
Paxos 算法
PaxosStore 孕育了 2 套 Paxos 算法组件：Paxos Certain 组件和 Paxos KV 组件，内存云应用的正是其中的 PaxosKV 算法组件。Paxos KV 组件外围代码 1912 行，通过严格测试，目前用于线上多个 Key-Value 存储模块，包含但不限于：用户账号信息存储、朋友圈存储等。
PaxosLog
在构建 PaxosLog（简称为 PLog）时，咱们针对 Key-Value 存储做了 2 项优化。
第一，PLog as DB
一般青年的通常做法是 PLog 和 DB 拆散：增量更新记录在 PLog 中，并在 Chosen 之后程序利用到 DB 中。这里的问题在于：
- 至多 2 次写操作：1 次 PLog 写，1 次 DB 写。
- Key 和 PLog 的对应关系：
- N : 1 读写性能受限与单个 PLog；
- 1 : 1 雷同的数据反复写 2 次。
图 5 精简 1：plog as db
提高青年思考了下得出 PLog as DB 计划：咱们心愿 Key 和 PLog 放弃 1:1 的对应关系，从而达到最大的并发性能，同时又不引入反复写。
第二，精简的 PLog: 只保留最新的 LogEntry
图 6 精简 2：最新的 LogEntry
作为 PLog as DB 的延长，既然每个最新 LogEntry 蕴含全量的数据，那么物理上保留间断的 PLog 就没有必要了。
简略轻便的 PLog 构造，带来的劣势还有：
- LogCompact 随同每次写进行，不占用额定的存储和计算开销；
- Log Catch-Up 通过散发最新的 LogEntry 即可实现，无需程序追流水或者 Snapshot，利用 DB。
基于 PaxosLog 的强一致性读写协定
强一致性读协定
图 7 强一致性读协定
强一致性读协定自身和 Paxos 算法没有太大关系，要点是多数派：播送的形式获取集群中少数机器（蕴含本身）的 PLog 状态，即最新的 LogEntry 地位和对应 LogEntry 处于 Pending/Chosen 状态。
- 当集群中少数在 Log Entry i 上处于 Chosen 状态时，能够确定 Log Entry i 是最新的。对于读多写少的业务，次要面对这种状况，整体读就能够十分轻量且失败非常低。
当集群中少数在 Log Entry i 上处于 Pending 状态时，无奈确定 Log Entry i- 1 是否最新，因为可能存在某台机器 Log Entry i 处于 Chosen 状态。对于读多写多的业务，读的失败就会绝对高很多。
可行的优化有：（1）尽量收集多机的状态信息，如果所有机器的 Log Entry i 都处于 Pending 状态，就能够确定 Log Entry i- 1 的数据是最新的；（2）应用隐含条件：只有 A / B 机器可读写。
强一致性写协定
强一致性写协定的大多数问题来自 Paxos 算法自身，这里咱们次要做了 3 项优化（或者说解决 3 个问题）。
第一，优化写。
The leader for each log position is a distinguished replica chosen alongside the preceding log position’s consensus value. The leader arbitrates which value may use proposal number zero.
The first writer to submit a value to the leader wins the right to ask all replicas to accept that value as proposal number zero. All other writers must fall back on two-phase Paxos.
上述文字摘抄自 MegaStore: FastWrites 局部，形容：LogEntry i- 1 值的归属者能够在写 LogEntry i 时跳过 Paxos 算法的 Prepare 阶段间接进行 Accept 阶段。基于这段迷一样的文字，咱们实现 Paxos 优化写算法：缩小 1 次写盘、2 次协定音讯发送、2 次协定音讯接管；最终实现了写耗时和失败的升高，如图 8 所示。
图 8 优化写和一般写的性能比照
第二，如何确定谁的提议写胜利了？
Paxos 算法只保障 LogEntry i 确定惟一值，但在多个 Proposer 的条件下（即 A / B 机均可发动强统一写），只有确定值的归属者能够返回胜利。这里咱们复用了 etcd 中 requestid 的计划。
图 9 requestid 计划
其中 member_id 用于辨别不同的 Proposer，timestamp 为毫秒级别的工夫戳，req_cnt 随写申请枯燥递增。基于 requestid 计划能够满足单机 25w/ s 的写申请，足够了。
备注：requestid 只须要在单个 plog 纬度上保障惟一即可。
第三，Paxos 活锁问题。
Paxos 算法自身不保障终止性，当呈现写抵触时算法可能永远终结不了，即存在活锁问题；因而在理论工程中咱们须要进行一些衡量：
- 限度单次 Paxos 写触发 Prepare 的次数；
- 随机避让。
咱们目前应用了 Prepare 次数限度策略，从现网监控来看由写抵触导致的失败比例极小：
图 10 Prepare 次数限度导致的失败监控
挑战 2：基于机械盘的 DirectIO 存储
咱们在新架构上采纳 DirectIO 的计划实现了一套保障数据安全落盘的存储组件，DirectIO 计划与其余两种写盘计划的对比方表格 11 所示。
表 11 写形式比拟
然而仅仅保障数据安全落盘还不够，咱们还要做到稳固：基于 Bitcask 写模型搭建的存储，须要定期的整顿磁盘文件（咱们称之为 Merge），以反复利用磁盘空间，其中波及操作有：Merge 新文件写盘、旧文件删除，对外体现为：Merge 写和失常写竞争、文件删除引起零碎卡顿。为克服这 2 个问题，咱们做了以下优化。
- 管制 Merge 写盘速度和大小。
- 在 DirectIO 的 4K 块中引入 BlockID，以反对文件的循环利用（不再删文件）。
图 12 4K DirectIO BlockID
挑战 3：简单的现网场景
机械盘 RaidCache
RaidCache 以电池作为后盾，能够在 WriteBack 模式下持有待写盘的数据批量写盘，以极大晋升机械盘的写盘性能；毛病在于当电池掉电时，为了数据安全必须从 WriteBack 模式切换到 WriteThrough 模式，写盘性能急剧下降（实在的机械盘）。磁盘从 WB 降级为 WT 是现网经营中常见的问题，通常 1~2 小时后电池充电结束即可重回 WB 模式，咱们来看看这 1~2 小时磁盘进化的影响。
单次磁盘进化导致磁盘写操作耗时和失败率升高，通常状况下被 Paxos 协定自身的多数派所容忍；然而本机作为 Proposer 被动发动写时，写盘失败带来的就是单次写申请失败，前端会主动跳转对机重试，此时问题来了：磁盘进化者写失败之前将 LogEntry 置于 Pending，对机重试的最终后果将 Pending 推成 Chosen，但此时 requestid 表明 Chosen 值源于磁盘进化者，对机写被抢占，返回最终失败。
简略的说，磁盘进化期间写最终失败较高：通过将 requestid 前传到对机，让对机用已有的 requestid 重试能够将写最终失败升高 1 个数量级。
PLog 对齐
当单机蕴含 kw 级别的 PLog 时，放弃零碎中所有 PLog 均处于对齐状态就变得很艰难；但只有在所有 PLog 均处于对齐状态时，零碎能力放弃最大化的可用性。经验一番衡量后，咱们的零碎中挂载了以下逻辑 (按时效性排序) 来保障 PLog 对齐：
- 失败 (本地落后) 触发异步 Catch-Up；
- 三级超时队列：如果 LogEntry 超时后仍旧处于 Pending 状态，就触发协定写重试；
- 全量数据校验：校验数据一致性的同时也触发 PLog 对齐。
LeanerOnly 模式
机器重启后发现文件失落，数据被回退了怎么办？Paxos 协定保障了绝大部分状况下强一致性和可用性，但不是全副。
某 LogEntry 承诺机器 A 的 Paxos 申请后，因为数据回退状态清空，从新上线后承诺机器 B 的 Paxos 申请，然而前后 2 次承诺互相矛盾，从而导致数据不统一。
上述形容的是拜占庭失败导致的数据不统一，这种失败违反了 Paxos 协定的假如前提；但现网经营中的确又须要解决这种状况，从而有了 LeanerOnly 模式的引入。
- LeanerOnly 模式下，本机只接管 Chosen 后的 LogEntry，不参加 Paxos 协定写，也就不会违反任何承诺。
- 三级超时队列，使得 LogEntry 尽快走向 Chosen。
- 异步 Catch-Up 和全量数据校验使得零碎 PLog 较快对齐。
假如进入 LeanerOnly 模式 2 小时后，零碎中旧 LogEntry 处于 Pending 状态的可能性能够忽略不计，那么该机能够解除 LeanerOnly 模式。
成绩
除了上文形容的优化外，咱们还定制了一套本地迁徙的计划用于新旧架构的平滑切换，因为篇幅限度，在此就不一一开展了。最终咱们实现上千台机器平安无故障的从 QuorumKV 架构切换到新架构，上面同步下新架构的性能数据和容灾能力。
性能数据
压力测试条件：Value 约为 120B，读写 3.3 : 1。
压力测试机型：64GB 内存，机械盘。
表 13 新旧架构性能比照
图 14 新旧架构均匀耗时和最终失败比照
具体数据如表 13 所示，能够看出在申请量相当的条件下，新架构在均匀耗时和最终失败上都优与旧架构；并且新架构只须要 6 台机器。
备注：新架构部署上少了 3 台机器，带来单机约 50% 的内存和磁盘增长（包容 3 份数据）。
零碎可用性
实例 1：网络故障期间可用性比照
图 15 网络故障期间 PaxosStore 内存云首次拜访失败率监控曲线
图 16 网络故障期间 QuorumKV 内存云首次拜访失败率监控曲线
某次内网故障期间（继续约半小时），PaxosStore 内存云展示了卓越的容灾能力：图 15 为故障期间 PaxosStore 内存云的首次拜访失败率监控，能够看到失败率是非常安稳的（因为网络故障期间前端申请有所升高，失败率反而小了些）；与之对应 QuorumKV 内存云则体现不现实。
备注：须要强调的是得益与微信后盾整体优良的容灾设计，用户对本次网络故障感知度很低。
实例 2：某城市切换架构前后失败率比照
图 17 PaxosStore 内存云首次拜访失败率监控曲线
图 18 QuorumKV 内存云首次拜访失败率监控曲线
图 17 和图 18 别离给出了新旧架构 KV 首次拜访失败率监控曲线（百万分之一），能够看到切换后零碎的首次拜访成功率从 5 个 9 晋升至 6 个 9，零碎可用性得以加强。
备注：此处为极为宏观的数据，前端会有简略的重试达到 100% 胜利。
小结
全新的内存云存储，通过精简的 PLog as DB、分布式强一致性读写协定等一连串优化，在性能上失去显著晋升；联合 DirectIO 存储系统、PLog 全量对齐等，零碎首次拜访失败率指标降落一个量级。
PaxosStore 是微信外部一次大规模 Paxos 工程革新实际，创新性地实现了非租约 Paxos 架构，将来还有后续文章和开源打算，InfoQ 也会第一工夫为大家出现，敬请期待。
OpenIMgithub 开源地址：
https://github.com/OpenIMSDK/…
OpenIM 官网：https://www.rentsoft.cn
OpenIM 官方论坛：https://forum.rentsoft.cn/
更多技术文章：
开源 OpenIM：高性能、可伸缩、易扩大的即时通讯架构
https://forum.rentsoft.cn/thr…
【OpenIM 原创】简略轻松入门 一文解说 WebRTC 实现 1 对 1 音视频通信原理
https://forum.rentsoft.cn/thr…
