文章目录
  1. 1. 一致性算法
    1. 1.1. 方案设计(概述)
    2. 1.2. 方案实现
    3. 1.3. 性能
  2. 2. 日志实践
  3. 3. 经验总结:
  4. 4. 后记

背景
作为合作方与公司某基础设施部门合作,为分布式配置数据库提供数据一致性保证,随该中间件交付多个产品,时间长达两年。目前合作还在继续,多个产品版本不断迭代。


Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。
关于一致性算法的应用场景,@Tim Yang在博文Paxos在大型系统中常见的应用场景有详细的总结,个人理解数据一致性保证的根基是带Commit语义的日志的一致性。 ,数据的一致性基于快照以及日志重放来保证,像 ZooKeeper™ 就是这么做的,和传统数据库由Write-Ahead Log机制来保证事物的原理是类似的。

一致性算法

方案设计(概述)

当初做设计时调研了无主的 e-Paxos(Github)、广泛应用的ZooKeeper™、以及当时刚被RedHat收购的Ceph/Monitors and Paxos, a chat with Joao Ceph,还有一个就是某个产品已经实现的一个方案,看了源码,可以认为是Ceph Monitor的C语言版本,但是实现的比较拙劣,性能比较差,这个后面再讲。
通过几番与合作部门沟通, 确定最终的方案为优化的Multi-Paxos有主方案,但是选主业务要求来做坑,后来的实践证明,这是一个严重失误,不做选主产生了很多问题)。

角色设计:

  • Leader(Master),与上层同主,负责处理所有上层业务读写操作
  • Slave(Acceptor),参与协商,并同步应用日志到本节点上层业务

算法运行阶段设计:

  • 恢复 在此阶段Master收集日志达到集群最新最全(至少某个安全区间的要都有),并供所有其他落后的Slave节点学习,恢复阶段的完成标志着集群可以对外提供读写服务,主要是主;
  • 协商 此为阶段算法运行常态,负责决议协商同步,消息驱动;
  • 热重配 集群拓扑变更时所有节点Nodemap刷新,通过一次特殊协商达成;

运行部署设计
以动态库的形式提供给上层配置数据库,运行时作为配置数据库进程的一个线程存在,逻辑上是Master+Slave的方式,节点个数为2N+1

有两个产品AB使用我们的算法,要求也是差别蛮大:A要求All节点都达成一致,可以理解为退化成2PC了(如果有一个节点Fail就跪了,一致性倒是保证了,可用性却大打折扣,感觉从设计上CAP如何取舍他们还是没想清楚。另外,6块盘做RAID1提升可靠性,感觉有些过度设计,往往事与愿违,XXX老师拍的方案,无人敢质疑,也是醉了),在A产品中实现中增加了单节点和双节点的支持,并不完全满足节点数为2N+1的约束;B是常规的Majority节点达成一致就好,节点个数为2N+1

方案实现

实现上日志的一致性通过epoch+version的方式来保证,只要有主变更,epoch增长,只要有新决议达成version增长。从目前来看,几乎所有的一致性算法都是选主+日志同步的流程,但是我们的方案Leader Election由上层来做了,这是所有恶梦的开始—-不保证日志最新的节点被选为主。

  1. 在恢复流程中,如果新主子没有任何日志,为了使自己的日志成为集群最新最全,就得从其他节点那里学习,有可能从一个节点还学不全,得从多个节点学习,可以有两种方式:(1)Slave推送;(2)Master主动选择学习对象。(1)的方式可能会有大量的重复数据推送主,我们选择了(2)的方式,Master根据一定的策略去选择学习对象,直到自己的日志成为集群最新最全。
    再说说前面提到的安全区间,如果某个节点落后太多,依靠算法恢复流程来跟其他节点同步速度无法保证,影响开工,所以在配置数据库层设置了一个是否做快照的阈值M,如果数据版本差异大于M,上层做数据快照;否则由我们算法来补齐日志并重放。安全区间是一个比阈值M稍大的值N,由于磁盘的限制,日志不可能一直保存,需要定期做清理,为了不影响其他节点学习所保留的最小日志区间就叫安全区间。前面的Master日志成为集群最新最全只需保证安全区间的日志都有就可以了。

    因为新主无法保证日志最新,导致恢复流程异常复杂;如果选主是我们自己来做的话,这些问题都将不存在。

  2. 在协商流程中,为了提高吞吐量,采用了打包的策略,可以根据不同业务对响应时间的不同要求对打包个数量进行调整。
  3. 重配就是新旧NodeMap共存一段时间,有个时间窗口,经过一轮特殊的协商将新NodeMap更新到集群中的协商参与节点。

其他:

  1. 为了减小网络闪断带来的影响,Master所有的消息都有超时 重发机制;对于Slave节点来说,定时器超时会走Catch-up学习流程;
  2. 选主由上层来做,并且只有Master支持读写,并且Master比较恒定,算法未实现租约与心跳;

性能

测试环境1.5K SAS盘IOPS在180左右,当每次同步写盘100条决议(打包设置为100,大小为1K),从测试情况来看,单个IO耗时平均在90ms,吞吐量大概在:100 * 1000/90 = 1.1K,对上层应用来说,目前足够使用。如果对吞吐量要求更高的话,可以优化为更大量级的批量写(像Zookeeper那样的1000条批量写),吞吐量可以做到1.1W,但是平均时延会相应增加,对于系统来说,吞吐量与时延总是矛盾的,需要trade off。这个数据看起来跟Zookeeper的写2w+还是有不小差距,不过因为Zookeeper使用的是独立物理盘,性能会好不少。

测试环境日志存储在非独立物理磁盘,从6块盘各划出一部分空间组软RAID 1,定制IO栈、驱动,平均IO时延在90ms左右,测试整体环境不太理想,上面的数据并不好看。

日志实践

关于日志,因为要保证一致性,所以必须同步落盘,在网络时延几乎可以忽略不计的情况下,日志落盘耗费的时间几乎就是所有的耗时,这块儿我们踩了大坑,对方拍下采用SQLite作为一致性日志的存储介质(之前用的是leveldb,写性能要好不少,后来IO测试表明也不适合用作日志存储)。

起初没有任何性能问题,因为业务压力不大,而且日志写的是SSD。但是当产品A从某个版本开始性能问题凸显,后来才知道配置数据库为了提升可靠性变更了存储方案:

从原来的写SSD改为写6块盘组的软RAID1(6块盘中有SSD也有SAS盘,且都是各自从物理盘上划分一块空间虚拟出来,非独立物理磁盘),混合了SSD与SAS盘的软RAID1,尤其是SAS盘,IO时延波动较大,磁盘大压力时常有(一次SQLite插入/更新)耗时30s+…惊愕了

通过大量测试分析,使用IO路径模块同事提供的手段,抓取每次写日志时产生的IO情况,结论是:如果使用SQLite且以WAL模式打开,它的check-point机制会产生大量的串行读写IO,二三十个都不稀奇,而且从IO统计数据来看,单个IO的时延有三四秒以上的(这个也比较恐怖,但是IO路径涉及多个团队且都不对IO响应时延有任何承诺…),根因基本确定。事实证明SQLite极不宜用作日志存储。

最后的解决方案是:设计一套新的日志方案,直接写文件,IO要可控
参考ZooKeeper、SQLite的WAL格式、MongoDB、Redis,我们设计了一套适用于目前算法流程日志方案,实现了新的日志持久化层,保证大多数情况下的日志写IO控制在1个左右,文件系统自身导致的少量多余IO目前还无法控制,日志写速度有了质的提升,根据磁盘压力波动情况总体性能提升在两倍到几十倍不等。

前面提到的某个产品实现的版本,性能不是太好,从源码来看,每个决议的日志会对应一个独立日志文件,猜测也是IO数比较多导致的。

经验总结:

  1. 定制日志格式,并且日志文件预分配大小,fflush之后使用fdatasync刷盘,可以减少一次由于文件大小改变时元数据更新(atime、mtime等)产生的写IO;
  2. 能合并写的数据,尽量一次写,比如文件头和第一条日志;
  3. 日志增加完整性校验;
  4. 软RAID在产品中使用欠妥,除了问题没有人能HOLD住,尤其是未掌握其运行机理的情况下;
  5. 最后最重要日志使用单独物理盘存储,不和其他业务共享。

从原理上来讲,Paxos只适用于保证类似配置数据这样对时间不敏感数据的一致性,状态数据就算了,性能上不去。

后记

最后,如果重新来过,个人觉得选主不能少,从源头上控制日志最新最全,可以降大大低后面流程的复杂度。近两年新出的 Raft 算法看起来比较好理解,简单也是其最大的亮点,持续关注:)

几篇不错的资料:

  1. Raft一致性算法分析与总结 (差不多为论文中文版)
  2. 分布式一致性,Raft以及其它 (Raft实践经验)
  3. 数据一致性-分区可用性-性能——多副本强同步数据库系统实现之我见登博 出品,超级总结)

Raft 作者@Diego Ongaro 也是马不停蹄,博士毕业不久就发布了类 ChubbyZooKeeper 以及 etcd 的协调服务程序 LogCabin,包含了Raft的C++实现,作者自信其可以直接在生产环境使用,后面有空要好好研究下。另外, etcd 是一个用于配置共享和服务发现的高可用键值存储,是CoreOS的核心组件,同时也用于Google开源的容器集群管理系统Kubernetes,用于服务发现、集群状态配置存储。

文章目录
  1. 1. 一致性算法
    1. 1.1. 方案设计(概述)
    2. 1.2. 方案实现
    3. 1.3. 性能
  2. 2. 日志实践
  3. 3. 经验总结:
  4. 4. 后记