早期做IM 参考微信的做法内部曾经自研过存储一段时间, 奈何组织架构调整, 这里回顾下相关论文

design

设计上, 将一致性协议和存储实现 分离, 支持 bitcask、LSM-tree、Main/Delta 模型, 上层模型支持 Key-value、Table、Queue、Set 等, 类似 azure 的分层思想, 但是没有走服务分层. 比较有意思的是, paxos 协议用的 无租约 模式, 存在 write-write 冲突 以及 重复提交请求 的问题.

重点关注下 paxos 实现的一致性保障、存储层实践优化、容灾&数据恢复

paxos

常规的paxos实现, prepare+accept 两阶段提交, 这里使用 消息传递机制 替换了状态机实现 (有点像raft实现), 不过是无租约的, 这样downtime 的可用性可以大大提升.

paxos log 作为 数据更新的 wal; paoxs log 由 entry 组成, entry=request id(client id 32bit ipv4 + timestamp second 16bit + request seq 16bit) + promise id(32bit machine id, 用于pre-preparing optimization) + value.

key-value 场景中, value 可以使用 paxos log 的entry, 降低写入的IO. 同时, paxos 也被划分成了 chosen 和 ongoing 两部分.

一致性读写上, 读需要 read majority 确定版本最新(trival paxos, 个人感觉这样可以满足 read-after-write), 但是对于一次读, 只要没落后-1 应该就满足了呀 (论文解释的有问题).

一致性写, 走 paxos 协议, 但是因为 write-write contention 导致 livelock, paxos-store 用了 time window 来保证 local replica 拒绝 其他的并发请求

一致性写 还采用了 prespecified replica node 的feature, unspecifield replica node 不是实时 apply, 而是 “PaxosLog-entry batched applying” (将写频繁的负载).

存储模型

常用的存储引擎 bitcask(point query)/lsm(range query); 常用的数据结构是 kv pair(bitcask/lsm)/retional table. table 也是 kv 存储实现的, 但是 读频繁场景下 会导致性能低下(内存有限, 读取经常需要加载内存), 为此 paxos 用 differential update  技术: read-optimized main-table(主要的数据) + write-friendly delta-table(内存中更新), delta-table 占用内存低, 并周期性的 merged 到 main table.

容灾&数据恢复

多dc 部署, 一个geo region 的多个dc会聚合成 不相连的集合=mini cluster 来对外服务, region 内(inter-region)的 data placement 用 consistent hash, intra-region(region之间) 用 三个dc 维护 hash到region的数据的副本.

dc内部采用 mini-cluster 实现, 将 node 划分成多个大小相等的 mini-cluster, 论文定义了 mini-cluster size 为符号C. 注意, 一个node 的数据 会在 remote dc 多个不同的节点. 不理解的地方, 一致性hash算法对于相同的配置, hash 结果也是一样的, 怎么会到不同的 远程节点 呢? 数据分布策略是怎样的呢?

也就是说, region -> dc -> multi mini-cluster; 以 mini-cluster 做多副本策略. 数据通过通过一致性hash到一个mini-cluster, mini-cluster的节点选择算法没说(说是随机选择).

数据恢复, 分几种情况:

  1. 增量paxos log entries 存在, 通过 paxos log 恢复
  2. 如果是 append-only, 通过 data image delta 同步
  3. 从整个 data image 恢复 

有意思的是, 在恢复到crash之前的状态后, 后续的恢复通过 lazy recovery: 也就是一致性读写操作, 个人觉得容易数据丢失

其他优化

  • failover read: 对于副本节点的异常读取: 过期&丢失数据, 会触发 副本的数据修复, 指定时间内数据恢复 就可以继续服务 副本上的读取
  • 去重: 因为 paxos 流程以及 网络延迟抖动导致 重复请求, 都会导致一个request 产生多条 paxos processure, 这里用 client id 进行去重
  • 异步: libco 框架实现异步. 通讯层 每个server 有多个 socket, batch process 提高处理能力
  • 无租约机制: 对比有lease 的raft, 能降低 downtime 不可用时间
  • pre-preparing optimization: 跳过 prepare/promise.

参考