[Paxos三部曲之三] Paxos成员组变更

Paxos成员组变更

本文是Paxos三部曲的第三篇,在前一篇文章《使用Multi-Paxos协议的日志同步与恢复》(http://oceanbase.org.cn/?p=111)中,我们讨论了基于Multi-Paxos协议的日志同步方案,在这个方案中,我们有一个隐含的前提,就是Paxos成员组是确定的,并且所有成员启动后都能加载一致的成员组信息。而在实际的工程应用中,往往需要在不停服务的情况下修改成员组,最典型的比如类似spanner的系统,对子表的迁移操作过程,就包含了对其Paxos成员组的变更操作。本文将基于Raft论文,讨论通用的成员组变更方法,和简化的一阶段成员组变更方法,以及成员组变更与日志同步操作的关系。

请注意,本文假设读者已了解Basic-Paxos和Multi-Paxos协议,并且本文假设集群工作在上一篇文章所述的Multi-Paxos协议之下。

  • 在线成员组变更的难点

Paxos执行两阶段投票协议的前提是有一个明确的Paxos成员组,而对于完全无中心化的Paoxs协议来说,成员组的内容本身又需要通过Paxos协议来维护一致性。对于变更后的新成员组从什么时机开始生效,存在“先有鸡还是先有蛋”的问题,如果还像同步普通日志一样来同步新成员组,那么在新旧成员组交接的过程中宕机,则可能出现选票分裂的情况,比如由成员组ABC变更为ABCDE过程中宕机,AB未持久化新成员组,CED已持久化新成员组,那么在宕机重启后,会出现AB形成了旧成员组的多数派,而CDE形成了新成员组的多数派,会出现两个leader的情况。

因此我们可以总结对在线成员组变更方案的几个基本要求:

P1. 成员组正常Paxos日志同步服务不中断

P2. 任何情况下宕机都能够保证存活的多数派成员间能够选举leader

P3. 不会出现1个以上的多数派选出大于1个leader的情况

  • 成员组变更的基本思路

成员组变更代表了“旧朝代”的结束和“新朝代”的开启,可以理解为依次执行如下两个投票操作:

Pa. “旧朝代”的多数派成员对“旧朝代结束”这件事达成一致,达成一致后旧成员组不再投票

Pb. “新朝代”的多数派成员对“新朝代开启”这件事达成一致,达成一致后新成员组开始投票

但是简单的按照这种两阶段的操作进行成员变更,虽然能够保证上述P3的约束,但是无法满足P1和P2,比如Pa执行成功后,在Pb执行成功之前:没有成员组可以投票,服务会中断;如果集群宕机重启,新的成员组的各个成员由于还未对新成员组达成一致,而无法选出leader。

为了保证P1和P2的约束,我们在上述基本成员变更的基础上,将Pa和Pb合并为一步操作,即新旧成员组一起对“旧朝代结束+新朝代开启”这件事达成一致后,才表示成员组变更成功。在开始成员变更的投票后,集群就进入了一个“中间状态”,在这个过程中宕机恢复后可能退回“旧朝代”也可能进入“新朝代”,因此在这个中间状态过程中投票的日志,要求在新旧成员组中都达成一致。

在这个基本思路的指导下,可以抽象出一个通用的成员变更方法:Jonit-Consensus。

  • 通用成员组变更方法–Joint-Consensus

Joint-Consensus是Raft论文中提到的两阶段成员变更方案,这个方案比较通用,甚至可以做到完整的成员组替换,但是两阶段方案的工程实现都比较复杂,而通用的场景需求又不多,因此在他博士论文最终版的成员变更一章中,更多篇幅分析了简化的一阶段方案(下一节讨论),而把Joint-Consensus的篇幅省略了很多。但是作为成员变更方案的基础,我这里还是希望能够从Joint-Consensus开始,分析它的正确性,并且尝试推导出一阶段的成员变更方法。

Joint-Consensus的方案如下,设成员变更前的成员组为C(old),变更后的成员组为C(new),成员组内容中包含单调增长的Version。

    • 变更操作
      1. 成员变更操作前,C(old)的多数派中持久化的成员组为[[C(old)]]
      2. 成员变更操作由leader执行,leader收到命令后,将成员组[[C(old),C(new)]]发送给C(old)∪C(new)的所有成员,在此之后新的日志同步需要保证得到C(old)和C(new)两个多数派的确认
      3. leader收到C(old)和C(new)两个多数派确认后,将成员组[[C(new)]]发送给C(new)的所有成员,收到C(new)多数派确认后,表示成员变更成功,后续的日志只要得到C(new)多数派确认即可
    • 协议约束
      1. Version投票约束:持有Version较大的成员,不能给持有Version较小的候选人投票
      2. 最大commit原则:
        • 持有[[C(old),C(new)]]的成员当选leader后,要重新对[[C(old),C(new)]]分别在C(old)和C(new)内投票达成多数派,然后继续成员变更流程,对[[C(new)]]在C(new)内投票达成多数派。然后才能开始leader恢复流程和leader服务
        • 持有[[C(old)]]的成员当选leader后,要重新对[[C(old)]]在C(old)内投票达成多数派,然后才能开始leader恢复流程和leader服务
        • 持有[[C(new)]]的成员当选leader后,要重新对[[C(new)]]在C(new)内投票达成多数派,然后才能开始leader恢复流程和leader服务
      • 选主投票原则
        1. 持有[[C(old),C(new)]]的候选人要得到C(old)和C(new)两个多数派都确认,才能当选leader
        2. 持有[[C(old)]]的候选人要得到C(old)多数派确认,才能当选leader
        3. 持有[[C(new)]]的候选人要得到C(new)多数派确认,才能当选leader
  • Joint-Consensus的协议分析
    1. 成员变更过程中,对[[C(old),C(new)]]的投票要求在C(old)和C(new)中都得到多数派的确认,是为了保证在C(old)投票“旧朝代结束”成功的同时,“新朝代开启”能够在C(new)生效,不会出现服务中断或者宕机重启后无法选出leader的情况。
    2. 对于成员变更的第二步,在[[C(old),C(new)]]形成两个多数派确认后,还要对[[C(new)]]在C(new)中进行投票,是为了结束需要向C(old)和C(new)都同步数据的“中间状态”。[[C(new)]]得到C(new)的多数派确认后,由于后面将要提到的“Version投票约束”原则的保证,可以确保后续宕机重启只有C(new)中的成员能够当选leader,因此无需再向C(old)同步数据。
    3. Version投票约束,实际上是Paxos协议Prepare阶段对ProposalID的约束,如本系列的前一篇Multi-Paxos一文所述,选主过程本质上是Paoxs的Prepare过程,我们将成员组内容视为Paxos提案,那么Version就是ProposalID,Paxos不允许Prepare阶段应答ProposalID更低的提案,所以我们要求持有较大Version的成员不能给持有较小Version的候选人投票。从直观上来分析,Version投票约束可以保证,在[[C(new)]]形成多数派确认后,C(old)中那些错过了成员变更日志的成员,不可能再得到C(old)多数派的选票。
    4. 最大commit原则,是Paxos最重要的隐含规则之一,在成员变更过程中的宕机重启,持有[[C(old),C(new)]]的成员可能当选leader,但是[[C(old),C(new)]]可能并未形成多数派,根据成员变更协议,成员变更过程要在[[C(old),C(new)]]形成两个多数派确认后,才能对[[C(new)]]进行投票。否则如果立即对[[C(new)]]进行投票,宕机重启后,可能出现C(old)和C(new)两个投票组各自选出一个leader。因此,持有[[C(old),C(new)]]的成员当选leader后,无论[[C(old),C(new)]]是否已经形成两个成员组的多数派确认,我们都按照最大commit原则对它重新投票确认形成多数派后,才能继续leader后续的上任处理。
    5. 选主投票原则,持有[[C(old),C(new)]]的成员当选leader,需要得到C(old)和C(new)两个多数派都确认,是为了避免C(old)与C(new)各自形成多数派选出两个leader的情况。在成员变更过程中,可以归结为如下两种情况:
      • 对[[C(old),C(new)]]的投票已开始,但未形成两个多数派确认,集群宕机。那么重启选主时,要么持有[[C(old)]]的成员当选leader,要么持有[[C(old),C(new)]]的成员当选leader。
      • 对[[C(new)]]的投票已开始,但未形成多数派确认,集群宕机。那么重启选主时,要么持有[[C(new)]]的成员当选leader,要么持有[[C(old),C(new)]]的成员当选leader。

如上文所述,持有[[C(old),C(new)]]的leader要先完成成员变更流程。之后再执行Multi-Paxox中的日志“重确认”,因此日志“重确认”过程不会进入“要得到两个成员组确认”的情况。

Joint-Consensus允许C(old)与C(new)交集为空,在这种情况下成员变更后,旧leader要卸任,并且将leader权限转让给确认[[C(new)]]的一个多数派成员。

Joint-Consensus方案比较通用且容易理解,但是实现比较复杂,同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性,因此我们期望增强成员变更的限制,以简化操作流程,考虑Joint-Consensus成员变更,之所以分为两个阶段,是因为对C(old)与C(new)的关系没有做任何假设,为了避免C(old)和C(new)各自形成多数派选出两个leader,才引入了两阶段方案。因此如果增强成员组变更的限制,假设C(old)与C(new)任意的多数派交集不为空,这两个成员组就无法各自形成多数派,那么成员变更方案就可能简化为一阶段。

  • 一阶段成员变更方法

Raft作者在他博士论文最终版的成员变更一章中,简化了Joint-Consensus的篇幅,而着重介绍了一阶段的成员变更方法,在工程上一阶段的成员变更方法确实更简单实用,下面是我对一阶段成员变更方案的一些分析。

    • 每次只变更一个成员

如上一节所述,如果做到C(old)与C(new)任意的多数派交集都不为空,那么即可保证C(old)与C(new)无法各自形成多数派投票。方法就是每次成员变更只允许增加或删除一个成员。假设C(old)的成员数为N,分析如下:

      • C(new)成员数为N+1
        1. 假设选出的leader持有C(new),那么一定是C(new)中有多数派,即(N+1)/2+1的成员给leader投票,那么持有C(old)且未给leader投票的成员最多为(N+1)-((N+1)/2+1)=(N-1)/2,这个值小于C(old)的多数派值N/2+1,无法选出leader
        2. 假设选出的leader持有C(old),那么一定是C(old)中有多数派,即N/2+1的成员给leader投票,那么持有C(new)且未给leader投票的成员最多为(N+1)-(N/2+1)=N/2,这个值小于C(new)的多数派值(N+1)/2+1,无法选出leader
      • C(new)成员数为N-1
        1. 假设选出的leader持有C(new),那么一定是C(new)中有多数派,即(N-1)/2+1的成员给leader投票,那么持有C(old)且未给leader投票的成员最多为N-((N-1)/2+1)=(N-1)/2,这个值小于C(old)的多数派值N/2+1,无法选出leader
        2. 假设选出的leader持有C(old),那么一定是C(old)中有多数派,即N/2+1的成员给leader投票,那么持有C(new)且未给leader投票的成员最多为N-(N/2+1)=(N-2)/2,这个值小于C(new)的多数派值(N-1)/2+1,无法选出leader
    • 启用新成员组的时机

启用新成员组的时机是指从何时开始,对日志的投票开始使用C(new)进行,这里需要考虑的问题是成员变更过程中宕机,重启选主后,持有[[C(old)]]的成员被选为leader,在宕机前使用C(new)同步的日志是否可能丢失。分析如下几种情况:

        1. 下线成员,C(new)与C(old)多数派成员数相同,比如ABCDE变更为ABCD,C(new)的任意多数派集合一定是C(old)的某个多数派,变更过程中使用C(new)同步的日志,在C(old)中依然能够保持多数派。
        2. 下线成员,C(new)的多数派成员数小于C(old),比如ABCD变更为ABC,这个情况比较特殊,我们来仔细分析,这种情况下在C(new)中形成的多数派成员只能达到C(old)成员数的一半,从严格的Basic-Paxos协议来分析,只做到N/2的成员确认,是不能保证决议持久化的。但是我们放在Multi-Paxos的环境中,使用lease机制保证leader有效(leader“有效”的意思是:StartWorking日志已形成多数派,且完成日志“重确认”,参考上一篇《使用Multi-Paxos协议的日志同步与恢复》)的前提下,因为不会有1个以上的成员并发提出议案,同时又因为在N为偶数时,N/2的成员集合与N/2+1的成员集合的交集一定不为空,可以分析出:在leader 有效 的前提下,只要N/2(N为偶数)的成员确认,即可保证数据持久化。因此,在这种情况下,在C(new)形成多数派的日志,宕机重启后,在C(old)中可以被多数派“重确认”,不会丢失。
        3. 上线成员,C(new)的多数派成员数大于C(old),比如ABC变更为ABCD,C(new)的任意多数派集合一定包含了C(old)的某个多数派,变更过程中使用C(new)同步的日志,在C(old)中依然能够保持多数派。
        4. 上线成员,C(new)与C(old)多数派成员数相同,比如ABCD变更为ABCDE,某些情况下可能产生C(new)的多数派(如ABE)与C(old)的多数派(如AB)交集只达到C(old)的一半,情况与第2点相同。
  • 最大commit原则

这里的最大commit原则体现在,同步[[C(new)]]的过程中集群宕机,持有[[C(new)]]的成员当选leader,重启后无法确认当前多数派持有的成员组是[[C(new)]]还是[[C(old)]],需要leader将当前持有的成员组重新投票形成多数派确认后,才能开始leader后续的上任处理。否则可能出现连续变更情况下,成员组分裂选出2个leader的情况,如Raft报出的这个bug,https://groups.google.com/forum/#!topic/raft-dev/t4xj6dJTP6E,修正方法也很简单就是实用最大commit原则,对成员组重新投票得到多数派确认。

    • 阶段成员变更方案总结
  1. 成员变更限制每次只能增加或删除一个成员
  2. 成员变更由有效的leader发起,确认新的成员组得到多数派确认后,返回成员变更成功
  3. 一次成员变更成功前不允许开始下一次成员变更,因此新任leader在开始提供服务前要将自己本地保存的最新成员组重新投票形成多数派确认
  4. leader只要开始同步新成员组后,即可开始使用新的成员组进行日志同步
  5. 成员组实用Version标记,持有更大Version的成员不能给持有较小Version的成员投票
  • 成员组变更与日志同步

    • Log Barrier

对于下线成员的场景,我们需要保证所有日志在剩余在线的机器上能够形成多数派备份,否则可能丢失日志。比如下面的场景,logID为2的日志,在连续成员变更后,仅A上有,无法在A/B/C上形成多数派:

paxos_barrier_log

因此我们要求leader在持久化新的成员组时,要像普通日志一样为它分配logID(称为成员变更日志),它是一个“单向barrier”,即要求所有成员保证logID小于它的日志都持久化本地后,才能持久化成员变更日志,而logID大于它的日志则不受此约束。在上面的例子中,要求B/C保证在持久化 Cnew1之前,一定先保证2号日志持久化。

磁盘故障与存储系统的年失效率估算

对三副本与ErasureCode两种方式下,数据丢失概率的估算,组合数学和概率论知识早就还给老师了,贴到博客给大家看看计算方法是否正确。

  1. 对于R个副本的情况,设磁盘年故障概率为P,磁盘数为N,则整个机群有C(N, R) = N!/(R!*(N-R)!)种R副本的组合方式。机群数据总量为M,分片大小为T,那么有R个磁盘同时损坏造成数据丢失的概率是:

屏幕快照 2016-03-25 下午10.51.39

  1. 对于由E个块组成的EC组,假设最多允许R-1个块丢失,整个机群有C(N, E)种EC组的组合方式,因此有R个磁盘同时损坏造成数据丢失的概率是:

屏幕快照 2016-03-25 下午10.51.46

其中P(t, R)表示在t时间内连续损坏R块磁盘的概率,这个概率符合泊松分布即:

屏幕快照 2016-03-25 下午10.52.11

设为t的单位时间(设为1小时)内发生磁盘损坏的平均次数,根据google的统计,磁盘的年失败率(AFR: Fnnualized Failure Rate)如下图所示,我们取一个平均值4来进行计算。那么就是0.0004566。

屏幕快照 2016-03-25 下午10.56.04

年故障率:

屏幕快照 2016-03-25 下午10.52.25

假设单盘容量为6T,使用率为70%,数据分片大小为1GB,在一个1000块磁盘的集群中,不同恢复时间的年故障率对比为:

恢复用时 3副本年故障率 EC(8+4)年故障率
1 1.2 * 10E-9 4.0 * 10E-19
4 1.9 * 10E-8 1.0 * 10E-16
12 1.7 * 10E-7 8.2 * 10E-15
24 6.8 * 10E-7 1.3 * 10E-13

3副本的恢复代价较小,因此我们可以按照机群使用1小时恢复单盘数据,EC恢复代价比较大,因此我们按照机群使用24小时恢复单盘数据,这两种情况下的持久性分布达到11个9和13个9。

附Python计算代码:

#!/usr/bin/python
# -*- coding: utf-8 -*-
import decimal
import math

lamda=decimal.Decimal(str(4.0/24/365))
e=decimal.Decimal(str(math.e))
perC=6.0*0.7*1024 #单盘容量(T)*使用率

#级数
def factorial(n):
  S = decimal.Decimal("1")
  for i in range(1, n+1):
    N = decimal.Decimal(str(i))
    S = S*N
  return S

#组合运算
def C(n, m):
  return factorial(n) / (factorial(m)*factorial(n-m))

#泊松分布
def poisson(t, R):
  return ((lamda * t) ** R) * (e**(-lamda*t)) / factorial(R)

#t时间内损坏R块磁盘的概率
def probability(t, R):
  return poisson(t, R)

#多副本年失效概率, T=分片大小(G), N=磁盘个数, t=单盘故障的复制时间, R=副本数
def probability_3R(T, N, t, R):
  M = decimal.Decimal(str(N * perC / R))
  pt = M / T / C(N,R) * probability(t, R)
  return (1 - (1-pt)**(decimal.Decimal(str(365.0*24/t))))

#EC年失效概率, T=分片大小(G), N=磁盘个数, t=单盘故障的复制时间, R=损坏超过R块磁盘则可能丢数据, E=EC组大小
def probability_EC(T, N, t, R, E):
  M = decimal.Decimal(str(N * perC / (1.0 * E / (E - R + 1))))
  pt = (M / T) * C(E,R) / C(N,R) * probability(t, R)
  return (1 - (1-pt)**(decimal.Decimal(str(365.0*24/t))))

 

架构师需要了解的Paxos原理、历程及实战

受TimYang邀请撰写的Paxos分享,已发在TimYang的公众号,我就不全文转了。

Abstract:“这里提一个名词:‘最大 Commit 原则’,这个阳振坤博士给我讲授 Paxos 时提出的名词,我觉得它是 Paxos 协议的最重要隐含规则之一,一条超时未形成多数派应答的提案,我们即不能认为它已形成决议,也不能认为它未形成决议,跟‘薛定谔的猫’差不多,这条日志是‘又死又活’的,只有当你观察它(执行 Paxos 协议)的时候,你才能得到确定的结果。”

架构师需要了解的Paxos原理、历程及实战

利用Bash脚本管理distcc集群

利用Bash脚本管理distcc集群

distcc介绍

对于大型C/C++项目,编译时间往往长到无法忍受,而冒然的增加make并发度则有可能由于gcc吃光内存而把机器搞死,因此我们期望能够使用多台机器并行编译项目。distcc是一个分布式编译程序,它包含客户端distcc,和服务器端distccd两个程序,distccd是一个守护进程,绑定在由命令行参数指定的端口上,接收distcc的编译请求,执行编译任务。

一个简单的使用方式是,在多台编译机上启动distccd,在客户端通过环境变量指定多个编译机的ip地址和端口号,然后使用distcc替换gcc编译项目。由于distcc自身实现的问题,编译失败或者make过程中途终止,可能会使得编译机上的distccd的工作进程僵死,因此运行一段时间后,可能出现大部分编译机上的distccd进程都变得不可用。并且编译机出现异常后也不能被distcc发现,而往往是网络连接超时后,才能去重试其他编译机。

为了解决上述问题,我开发了一套简单的bash脚本(distccMgr),通过单点监控所有编译机的健康状态,来实时生成可用的编译机列表,并可以通过下发命令来定时或立即重启编译机上的distccd进程。distccMgr本身不需要启动任何守护进程,而是通过crontab来定时保持心跳,通过ssh远程执行命令来实现心跳通信。

使用distccMgr集中化管理distcc编译机

git clone git@github.com:kayaklee/distccMgr.git
  • 管理节点部署
修改配置文件
SUDO="sudo" #执行sudo的命令前缀,比如美团的就是"sudo -iusankuai sudo"
MASTER_ADDR=`hostname -i` #管理节点的ip地址

MASTER_USER=$USER #管理节点的运行账户,需要保证与编译节点的运行账号相互打通
MASTER_PORT=8899 #管理节点开启http服务的端口号
DISTCCD_PORT=8898 #编译节点启动distccd服务的端口号

DISTCC_DIR=$HOME/share/distcc #管理节点监控脚本的部署目录
MASTER_DIR=$HOME/share/distcc/resource #管理节点资源目录,用于给编译节点提供http下载服务
SLAVE_DIR=$HOME/distccd #编译节点部署distccd的目录
运行部署命令
./deploy.sh 
部署成功后
1. 会在crontab中建立两个定时任务
2. 会在本地生成cmd目录,生成slave_deploy.sh和distcc_install.sh,其中slave_deploy.sh中是编译机的部署命令,distcc_install.sh是安装distcc的命令
  • 编译节点部署
1. 在每台编译机上执行slave_deploy.sh
2. 在管理节点的$DISTCC_DIR目录中的iplist中增加编译节点的ip地址
  • 客户端部署
1. 运行distcc_install.sh安装distcc,成功后会增加定时任务更新最新的编译机列表到/tmp/udistcc
2. 每次make前source /tmp/udistcc
  • 命令所有编译机重启distccd进程
在管理节点上touch /tmp/restart_distcc

一个小玩具

用golang玩的图片编辑服务,就跑在这个Blog的主机上

其实不小,代码量挺大,先不开源了,先部署在自己的Blog上玩玩

编辑参数比较像阿里云的 阿里云图片服务文档

url规则:http://image.oceanbase.org.cn/?xesurl=[图片url]&xesactions=[编辑参数]

示例url(缩放并填充): http://image.oceanbase.org.cn/?xesurl=http://7xkpgt.com1.z0.glb.clouddn.com/lena.jpg&xesactions=400h_500w_4e_150-50-100bgc

示例url(文字水印):http://image.oceanbase.org.cn/?xesurl=http://7xkpgt.com1.z0.glb.clouddn.com/lena.jpg&xesactions=watermark%3D2%26type%3Dd3F5LW1pY3JvaGVp%26text%3D5LiL5Y2K6Lqr5ZGi%26color%3DI2ZlMjRkYw

[Paxos三部曲之二] 使用Multi-Paxos协议的日志同步与恢复

使用Multi-Paxos协议的日志同步与恢复

           本文是Paxos三部曲中的第二篇。在前一篇文章《使用Basic-Paxos协议的日志同步与恢复》(http://oceanbase.org.cn/?p=90)中,我们讨论了基于Basic-Paxos协议的日志同步方案,在这个方案中,所有成员的身份都是平等的,任何成员都可以提出日志持久化的提案,并且尝试在成员组中进行持久化。而在实际的工程应用中,往往需要一个成员在一段时间内保持唯一leader的身份,来服务对数据的增删改操作,产生redolog,并尝试在成员组中进行持久化。本文讨论如何利用Paxos协议选举唯一的leader,以及使用leader将redolog在成员组中进行持久化和恢复的方法。

  • Basic-Paxos协议回顾

让我们先来回顾下Basic-Paxos协议的执行流程:为了简化描述,我们假设一个Paxos集群,每个server同时担任proposer和acceptor,任何server都可以发起持久化redolog的请求,首先要向所有的server查询当前最大logID,从多数派的应答结果中选择最大的logID,加1后作为执行本次Paxos Instance的唯一标识;然后进入Paxos的prepare阶段,产生proposalID,并决定出要投票的redolog(即议案);在accept阶段对prepare阶段产生的议案进行投票,得到多数派确认后返回成功。由此我们可以看出Basic-Paxos协议的执行流程针对每条redolog都至少存在三次网络交互的延迟(1. 产生logID;2. prepare阶段;3. accept阶段)。下面我们逐个分析每个阶段的必要性:

  1. 产生logID,由于Basic-Paxos并不假设一段时间内只有唯一的proposer,因此可能由集群内的任意server发起redolog同步,因此不能由单一server维护logID,而是需要进行分布式协商,为不同的redolog分配全局唯一且有序的logID。
  2. prepare阶段,上述一阶段的分布式协商logID并不能保证并发多个server分配得到得logID是唯一的,即会出现若干条不同的redolog在同一个Paxos Instance中投票的情况,而这正是Basic-Paxos协议的基本假设,因此需要执行prepare,以决定出这个Paxos Instance内的要进行投票的redolog(即议案)。如果执行prepare决定出的议案与server自己要投票的redolog内容不同,则需要重新产生logID。
  3. accept阶段,对prepare阶段决定出的议案进行投票,得到多数派确认后表示redolog同步成功,否则需要重新产生logID。

在这三个阶段中,根据Paxos协议的约束,server应答prepare消息和accept消息前都要持久化本地redolog,以避免重启后的行为与重启前自相矛盾。因此最终可以得到使用Basic-Paxos进行redolog同步的延迟包括了3次网络交互加2次写本地磁盘。并且在高并发的情况下,不同redolog可能被分配到相同的logID,最差可能会在accept阶段才会失败重试。

 

  • Multi-Paxos协议概述

在Paxos集群中利用Paxos协议选举唯一的leader,在leader有效期内所有的议案都只能由leader发起,这里强化了协议的假设:即leader有效期内不会有其他server提出的议案。因此对于redolog的同步过程,我们可以简化掉产生logID阶段和prepare阶段,而是由唯一的leader产生logID,然后直接执行accept,得到多数派确认即表示redolog同步成功。

 

  • leader的产生

首先,需要明确的是Multi-Paxos协议并不假设全局必须只能有唯一的leader来生成日志,它允许有多个“自认为是leader的server”来并发生成日志,这样的场景即退化为Basic-Paxos。

Multi-Paxos可以简单的理解为,经过一轮的Basic-Paxos,成功得到多数派accept的proposer即成为leader(这个过程称为leader Elect),之后可以通过lease机制,保持这个leader的身份,使得其他proposer不再发起提案,这样就进入了一个leader任期。在leader任期中,由于没有了并发冲突,这个leader在对后续的日志进行投票时,不必每次都向多数派询问logID,也不必执行prepare阶段,直接执行accept阶段即可。

因此在Multi-Paxos中,我们将leader Elect过程中的prepare操作,视为对leader任期内将要写的所有日志的一次性prepare操作,在leader任期内投票的所有日志将携带有相同的proposalID。需要强调的是,为了遵守Basic-Paxos协议约束,在leader Elect的prepare阶段,acceptor应答prepare成功的消息之前要先将这次prepare请求所携带的proposalID持久化到本地。

对于leader Elect过程,我们并不关心leader Elect提案和决议的具体内容,因为无论执行多少次leader Elect,从Basic-Paxos的角度来看,都是同一个Paxos Instance在对已经形成的决议反复进行投票而已。而执行leader Elect这个过程,我们最关注的是要得到最近一次形成决议的proposer是谁,以及它的proposalID。在leader Elect过程中,得到多数派accept的proposer将成为leader,而它本次所用的proposalID即成为它任期内对所有日志(包括新增日志和后文将提到的重确认日志)进行投票时将要使用的proposalID(称为leader ProposalID)。

这里还需要考虑的一个问题是,由于多个server并发执行leader Elect,可能出现两个server在相近的时间内,先后执行leader Elect都成功,都认为自己是leader的情况。因此,当选leader在开始以leader身份提供服务之前,要使用leader ProposalID写一条日志(称为StartWorking日志),得到多数派确认后,再开始提供服务。这是因为根据Basic-Paxos的约束,可以推断出:先执行leader Elect成功的leader(称为L1),它的proposalID(称为P1)一定会小于后执行leader Elect成功的leader(称为L2)的proposalID(称为P2),而经过了两轮leader Elect,机群内多数派持久化的proposalID一定是P2,而此时L1使用P1执行accept时,由于P1<P2,它将无法得到机群内多数派的accept。

 

  • Confirm日志的优化

在Paxos协议中,对于决议的读取也是需要执行一轮Paxos过程的,在实际工程中做数据恢复时,对每条日志都执行一轮Paxos的代价过大,因此引入需要引入一种被成为confirm的机制,即leader持久化一条日志,得到多数派的accept后,就再写一条针对这条日志的confirm日志,表示这条日志已经确认形成了多数派备份,在回放日志时,判断如果一条日志有对应的confirm日志,则可以直接读取本地内容,而不需要再执行一轮Paxos。confirm日志只要写本地即可,不需要同步到备机,但是出于提示备机及时回放收到日志的考虑(备机收到一条日志后并不能立即回放,需要确认这条日志已经形成多数派备份才能回放),leader也会批量的给备机同步confirm日志。出于性能的考虑,confirm日志往往是延迟的成批写出去,因此仍然会出现部分日志已经形成多数派备份,但是没有对应的confirm日志的情况,对于这些日志,需要在恢复过程中进行重确认。

在实际的工程实践中,可以使用基于logID的滑动窗口机制来限制confirm日志与对应的原始日志的距离,以简化日志回放与查询逻辑。

 

  • 新任leader对日志的重确认

如上一节所述,在恢复过程中,拥有对应confirm日志的原始日志,可以被直接回放。而没有对应confirm日志的原始日志,则需要执行一轮Paxos,这个过程被成为重确认。

此外日志中的“空洞”,也需要进行重确认,因为当前leader再上一任leader的任期内可能错过了一些日志的同步,而这些日志在其他机器上形成多了多数派。由于logID连续递增,被错过的日志就成了连续logID连续递增序列中的“空洞”,需要通过重确认来补全这些“空洞”位置的日志。

新任leader在开始执行重确认前,需要先知道重确认的结束位置,因为leader本地相对于集群内多数派可能已经落后很多日志,所以需要想集群内其他server发送请求,查询每个server本地的最大logID,并从多数派的应答中选择最大的logID作为重确认的结束位置。也即开始提供服务后写日志的起始logID。

对于每条日志的重确认,需要执行一轮完整的Paxos过程,可能有些日志在恢复前确实未形成多数派备份,需要通过重新执行Paxos来把这些日志重新持久化才能回放。这种不管日志是否曾经形成多数派备份,都重新尝试持久化的原则,我们称之为“最大commit原则”。之所以要遵守“最大commit原则”,是因为我们无法区分出来未形成多数派备份的日志,而这些日志在上一任leader任期内,也必然是“未决”状态,尚未应答客户端,所以无论如何都重新持久化都是安全的。比如A/B/C三个server,一条日志在A/B上持久化成功,已经形成多数派,然后B宕机;另一种情况,A/B/C三个server,一条日志只在A上持久化成功,超时未形成多数派,然后B宕机。上述两种情况,最终的状态都是A上有一条日志,C上没有,在恢复时无法区分这条日志是否曾经形成过多数派,因此干脆按照“最大commit原则”将这条日志尝试重新在A/C上持久化后再回放。

需要注意的是,重确认日志时,要使用当前的leader ProposalID作为Paxos协议中的proposalID来对日志执行Paxos过程。因此在回放日志时,对于logID相同的多条日志,要以proposalID最大的为准。

 

  • 幽灵复现日志的处理

使用Paxos协议处理日志的备份与恢复,可以保证确认形成多数派的日志不丢失,但是无法避免一种被称为“幽灵复现”的现象,如下图所示:

 

Leader

A

B

C

第一轮

A

1-10

1-5

1-5

第二轮

B

宕机

1-6,20

1-6,20

第三轮

A

1-20

1-20

1-20

  1. 第一轮中A被选为Leader,写下了1-10号日志,其中1-5号日志形成了多数派,并且已给客户端应答,而对于6-10号日志,客户端超时未能得到应答。
  2. 第二轮,A宕机,B被选为Leader,由于B和C的最大的logID都是5,因此B不会去重确认6-10号日志,而是从6开始写新的日志,此时如果客户端来查询的话,是查询不到6-10号日志内容的,此后第二轮又写入了6-20号日志,但是只有6号和20号日志在多数派上持久化成功。
  3. 第三轮,A又被选为Leader,从多数派中可以得到最大logID为20,因此要将7-20号日志执行重确认,其中就包括了A上的7-10号日志,之后客户端再来查询的话,会发现上次查询不到的7-10号日志又像幽灵一样重新出现了。

对于将Paxos协议应用在数据库日志同步场景的情况,幽灵复现问题是不可接受,一个简单的例子就是转账场景,用户转账时如果返回结果超时,那么往往会查询一下转账是否成功,来决定是否重试一下。如果第一次查询转账结果时,发现未生效而重试,而转账事务日志作为幽灵复现日志重新出现的话,就造成了用户重复转账。

           为了处理幽灵复现问题,我们在每条日志的内容中保存一个generateIDleader在生成这条日志时以当前的leader ProposalID作为generateID。按logID顺序回放日志时,因为leader在开始服务之前一定会写一条StartWorking日志,所以如果出现generateID相对前一条日志变小的情况,说明这是一条幽灵复现日志(它的generateID会小于StartWorking日志),要忽略掉这条日志。

 

  • 总结

本文介绍了在Basic-Paxos协议基础之上构建Multi-Paxos协议的几个要点:通过使用Paxos选举leader来避免对每条日志都执行Paxos的三阶段交互,而是将绝大多数场景简化为一阶段交互,并且讨论了基于Paxos协议的最大commit原则;通过引入confirm日志来简化回放处理;通过引入Start Working日志和generateID来处理幽灵复现问题。

 

有关期权股票与缴税的分享

有关期权股票与缴税的分享

本文基于作者本人的经验而写,其间难免有纰漏或错误,内容仅供大家参考。

作为一个穷二代屌丝码农,靠积攒每月的固定工资,可以说很难追上一线城市不断上涨的房价,还好我们处在一个伟大的时代,选择加入一家高速发展的公司,分得一些期权或股票,熬几年到公司上市套现,屌丝也可以逆袭

授予”与“归属”

以目前的经验来看,公司一般会以期权(option)或限制性股份单位(RSU)的形式对员工进行长期激励,也有其他形式的,比如华为的内部股票,或者蚂蚁金服的“股份收益权”不在本次讨论的范围内。所谓“长期激励”,其实就是把承诺给你的OptionRSU,拆分到N年,每年给一部分,以防止你全拿了就立即跑路。

这里就要谈到“授予”和“归属”两个概念,“授予”是一个承诺,靠谱的公司一般会明确写在offer中,承诺到未来某个时间只要你没有离职或被开除就给你多少OptionRSU;“归属”就是到了上述约定的时间,公司按照之前的承诺,将“授予”你的OptionRSU登记在你的名下。比如HR给你的发的offer可能会写“授予”你MOption,分4年“归属”,入职两年后“归属”M/2份,之后每年“归属”M/4份。在这4年期间如果你离职了,那么从你离职之日之后按计划要“归属”的Option都将失效。

期权

期权(option)就是允许你在一段时间内(一般比较长达几年)以约定的价格和数量购买公司股票的权利。归属以后才能“行权”,“行权”就是指你按照约定的价格够买股票的行为。如果公司未来股价上涨,股价与行权价相差的部分,就是你的收益,当然也存在风险即公司股价跌至行权价以下,这样的话Option就沦为废纸了。这里我们只讨论公司股价高于行权价的情况,行权需要缴纳两部分费用,第一部分就是行权本金,你要买多少股乘以行权价就是你要付出的本金;第二部分是个人所得税,用行权当日股价减去行权价,就是你的每股收益,乘以你要买的数量就是行权总收益计算个人所得税,具体缴税方式在后文说明。

一般期权归属后,会有一个有效期的,过了有效期就不能行权了,这个有效期一般会长达好几年,但是如果离职的话,一般就需要在几个月内行权,否则就会失效。

这里额外再说一下,一般来说行权价就是“授予”当时的股价,根据当时的公司的估值,以及公司发展和融资的状况,可以大概yy下几年后的股价。

限制性股份单位

限制性股份单位(RSU)简单说就是干股,也可以认为是行权价为0Option,唯一的区别是RSU不需要行权,“归属”后就变成你的股票了。但是同样需要你缴纳费用,就是个人所得税,一般是用归属当日的股价乘以归属的数量作为你的总收益计算个人所得税,具体缴税方式在后文说明。

这里需要注意的是,在公司尚未IPO的情况下,Option行权或RSU归属时的股价以公司最近一次发布的“公允价”计算;而如果已经IPO,那么就按照行权当天(或前n天的平均)收盘价计算。

股票与ADS的兑换

行权或RSU归属后,公司的股票就算是登记在你的名下了,如果在美国上市的话,还会有一个股票与ADS(美国存托股票,即资本市场上的流通股)的兑换比例,A股和H股可能也有类似的机制。所以一家上市公司给你发的offer中有股票授予的话,在你计算跳槽收益时要特别留意这个股票与资本市场上流通股的兑换比例。

关于个人所得税

有部电影曾经说过人生有两件事是逃不掉的,死亡和纳税。如上文所述,在Option行权和RSU归属的时候需要缴纳个人所得税,根据“国税函[2006]902号”,“国税函[2009]461号”,“财税[2005]35号”的规定,我总结缴纳个人所得税有三种计算方式:

  1. 发行股票的公司并未上市,这种情况下要将行权或归属的总收益与当月工资一起合并计税。
  2. 发行股票的公司(下称为A)已经上市,但是和你签署劳动合同的公司(下称为B)不是上市公司并且A公司持有B公司的股份少于30%,这种情况下计税方式与第1点一样,将行权或归属的总收益与当月工资一起合并计税。
  3. 发行股票的公司已上市,和你签署劳动合同的公司正是上市公司或被上市公司控制了超过30%的股份,这种情况下行权或归属的总收益将在本年度内平摊到12个月计税,且不与工资合并计税。说法有点绕,我们来举一个实例,比如在2014年度某个同学行权若干次,RSU归属若干次,最后算得的总收益为M元,那么他本年度需要为行权和归属缴纳的个人所得税为:(M / 12 * 适用税率 – 速算扣除数) * 12与工资没有任何关系。

分析与总结

  1. 对于未上市的公司,option的缴税比RSU更灵活,你可以在option“归属”后自由的选择时间行权,行权的收益跟当月工资合并计税,像我们这种小虾米,自己平摊到几个月行权的话,一般不会达到45%的税率;而RSU则没那么自由,在“归属”的当月就要按照收益全额缴税,比较容易就达到45%的最高税率
  2. 上市后的OptionRSU的缴税可以按照国家规定平摊到一年度12个月计税,而option还要多付出比较高的本金,因此RSU的风险更低一些;由于是与工资分开计税的,所以谈offer时如果能在现金与股票中选择的话,平衡与现金与股票数量,能最大程度的降低缴税成本
  3. 小心“个人所得税”一节第2点的坑,如果被授予OptionRSU,签署劳动合同尽量争取与上市公司或上市公司持股超过30%的公司签署
  4. 如果被授予OptionRSU,决定跳槽前注意询问股票与资本市场流通股的兑换比例
  5. offer时要求明确“归属”方案,尽量别选择那些网上流传的公司,上市后,员工连自己有多少股票都不知道

最后,努力工作和读书吧,少跳槽多拿股票,屌丝也能买得起北京的房子。

参考资料:

国税函[2006]902

http://www.chinatax.gov.cn/n810341/n810765/n812183/n812831/c1196443/content.html

国税函[2009]461

http://www.chinatax.gov.cn/n810341/n810765/n812166/n812622/c1087262/content.html

财税[2005]35

http://www.mof.gov.cn/zhengwuxinxi/caizhengwengao/caizhengbuwengao2005/caizhengbuwengao20056/200805/t20080525_42773.html

[Paxos三部曲之一] 使用Basic-Paxos协议的日志同步与恢复

使用Basic-Paxos协议的日志同步与恢复

 

           在保证数据安全的基础上,保持服务的持续可用,是核心业务对底层数据存储系统的基本要求。业界常见MySQL/Oracle的1主N备的方案面临的问题是“最大可用(Maximum Availability)”和“最大保护(Maximum Protection)”模式间的艰难抉择,其中“最大可用”模式,表示主机尽力将数据同步到备机之后才返回成功,如果备机宕机或网络中断那么主机则单独提供服务,这意味着主备都宕机情况下可能的数据丢失;“最大保护”模式,表示主机一定要将数据同步到备机后才能返回成功,则意味着在任意备机宕机或网络中断情况下主机不得不停服务等待备机或网络恢复。可见传统主备方式下,如果要求数据不丢,那么基本放弃了服务的持续可用能力。

 

           基于Paxos协议的数据同步与传统主备方式最大的区别在与Paxos只需任意超过半数的副本在线且相互通信正常,就可以保证服务的持续可用,且数据不丢失。本文不再分析Paxos协议本身(参考原始论文,以及这篇比较通俗的分析http://mp.weixin.qq.com/s?__biz=MjM5MDg2NjIyMA==&mid=203607654&idx=1&sn=bfe71374fbca7ec5adf31bd3500ab95a&key=8ea74966bf01cfb6684dc066454e04bb5194d780db67f87b55480b52800238c2dfae323218ee8645f0c094e607ea7e6f&ascene=1&uin=MjA1MDk3Njk1&devicetype=webwx&version=70000001&pass_ticket=2ivcW%2FcENyzkz%2FGjIaPDdMzzf%2Bberd36%2FR3FYecikmo%3D ),而是基于Paxos协议,讨论一种在多副本上持久化数据的高可用方案。需要注意的是,本方案不考虑运行性能,只是为了帮助说清协议的工程实现。

 

           我们将数据持久化的需求抽象为:在N个server的机群上,持久化数据库或者文件系统的操作日志,并且为每条日志分配连续递增的logID,我们允许多个客户端并发的向机群内的任意机器发送日志同步请求。对于高可用的需求为:在N个server中只要有超过半数的server(majority)正常服务,并且相互通信正常,那么这个机器就可以持续的提供日志持久化和查询服务。

 

           将每条日志的持久化流程都看作一个“Paxos Instance”,不同的logID代表不同的Paxos Instance形成的“决议(decision)”。即每一个logID标识着一轮完整paxos协议流程的执行,最后形成decision。机群内的每个server同时作为paxos的acceptor和proposer。

 

           获取LogID

           Server收到客户端的持久化日志请求后,先要决定这条日志的logID,为了尽量减少后续Paxos协议流程中处理并发冲突造成的回退,要尽量分配与目前已经持久化和正在持久化中的日志不重复的logID,同步也要容忍少于半数的server宕机与网络故障。因此向所有acceptor查询它们本地目前已写盘的最大logID,而只需收集到majority返回的结果,并选择其中最大的logID+1作为本次待持久化日志的logID。从上面的描述可以看出,这里并不能保证并发提交的两条日志一定被分配到不同的logID,而是依靠后续的paxos协议流程来达到对一个logID形成唯一的decision的目的。

 

           产生ProposalID

获取LogID后,server作为proposer开始针对当前logID,执行Paxos Instance,先产生proposalID,根据paxos协议的要求,proposalID要满足全局唯一和递增序,即对同一个server来说后产生的proposalID一定大于之前产生的,这里我们使用server的timestamp联合ip作为proposalID,其中timestamp在高位,ip在低位,只要时钟的误差范围小于server重启的时间,就可以满足“同一个server后产生的proposalID一定大于之前产生的”。

 

           Prepare阶段

           Proposer准备好proposalID后,将proposalID作为 “提案(proposal)”发送给所有的acceptor。根据Paxos协议P1b的约束,这个阶段发送的proposal并不需要携带日志内容,而只需要发送proposalID。Acceptor收到proposal后,根据Paxos协议P1b判断是否要“回应(response)”:只有在这个Paxos Instance内(即针对这个logID)没有response过proposalID大于等于当前proposal的,并且也没有“接受(accept)”过proposalID大于当前proposal的,才可以response,并承诺不再accept那些proposalID小于当前proposal的。

如果已经accept过proposal,那么连同proposalID最大的日志内容一同response。为了遵守P1b的约束,在宕机恢复后也能满足,因此在response前,需要将当前proposalID写到本地磁盘。

           上述Prepare阶段的处理流程暗示,对于分配到相同logID的不同日志,由于他们的proposalID不同,acceptor在response一个较小proposalID后,是允许继续response后来的较大的proposalID的。

 

           Accept请求阶段

           Proposer收集到majority的response后,来决定后续是否将要发出的“accept请求(accept request)”,判断如果majority的response中的日志内容都为空,那么可以向所有acceptor发出accept request并携带上当前日志内容;而如果有任意的response中的日志内容有效,那么说明当前logID已经别其他日志占用,且其他日志可能已经在majority上持久化,因此需要回退,回到第一步“获取logID”重新执行。

 

           Accept处理阶段

           Acceptor收到proposer的accept request后,根据上文中“Prepare阶段”的承诺,判断当前logID下,曾经response过的最大proposalID,如果小于等于当前proposal的,则可以继续执行后续的accept处理逻辑;而如果大于当前proposal的,则说明有logID切proposalID更大的proposal在并发执行,当前proposal会被覆盖,因此回复proposer要求回退到第一步“获取logID”重新执行。

           然后Accept处理逻辑将当前proposal连同proposalID一起写到本地磁盘,给proposer回复成功。Proposer收集到majority的回复成功后,说明本条日志已经在机群上持久化成功,可以保证后续一定不会被覆盖或丢失,可以给客户端返回了。

           上述accept处理阶段的流程暗示,可能会存在针对一个logID,日志只在少于半数的acceptor上写到本地磁盘,而acceptor同时response了proposalID更大的proposal,而使得当前logID下没有任何日志在机群上持久化成功。即一个logID可能没有标识任何有效日志,这种情况是可以接受的。

 

           日志内容读取

           已经在机群上持久化成功的日志,需要能够被读取出来,一般的应用模式是按照logID的顺序依次读取并回放日志。读取的时候针对每一条logID,需要执行一轮完整的paxos协议流程,将accept处理阶段成功的日志内容返回。需要注意的是,在accept请求阶段的处理逻辑变化:Proposer收集到majority的response后,判断如果majority的response中的日志内容都为空,那么向所有acceptor发出日志内容为空的accept request;而如果有任意的response中的日志内容有效,则选择proposalID最大的日志内容放入accept request。后续收到majority的accept回复成功后,才可以返回日志内容作为读取结果。

           这里的流程暗示,针对一个logID,如果之前已经有日志内容持久化成功,那么这条日志一定会被选为accept request;而如果之前日志内容仅仅在小于半数的server上写到磁盘,那么最终这条logID的内容有可能是有效日志,也有可能内容为空。

 

           为什么读取也需要执行Paxos流程

           这是基于一致性的考虑,即针对一条logID,读取出的内容后续应该永远不变。因此如果一条logID在写入过程中,并未在majority上持久化,那么需要在读取返回结果前,将这个结果在机群上持久化成功。

[LockFree之美] 共享变量的并发读写

共享对象的并发读写

在高性能并发服务器中,对于共享对象的读写是最常见的操作之一,比如全局配置类对象的并发读取和更新,以及更复杂的如copy on write btree、堆栈等的并发读写,最基本的操作都可以简化理解为通过全局共享的指针,并发读取和更新指针所指向对象的操作。
最简单的模型如下所示,一个包含了多个字段的结构体:

struct GConf
{
  int64_t a;
  int64_t b;
  int64_t c;
};

可以通过一个全局指针struct gConf *g_conf进行访问。有多个线程会同时读取或更新这个对象,要求任何时刻读取到的内容一定是“一致的”,即读取到的a/b/c的值一定是相同一次更新的值,而不能出现读到的a是某一次更新的值,而b或c是另外一次更新的值。
我们假设研发平台为x86_64,指令级的原子操作最多是64位(实际intel提供了128bit的原子操作,但是本文后续的讨论的方法只用到64bit的原子操作),因为gConf包含三个8字节整数,无法使用原子操作指令对a/b/c一次性赋值,因此必须通过程序算法来保证并发情况下读取到的内容满足“一致性”。
下面开始从易到难讨论5种处理“共享对象并发读写”的方法。

1. 读写锁
最简单朴素的想法是为这个结构配备一个读写锁,读取操作在读锁保护下执行,更新操作在写锁保护下执行。这个方法在对象读取和更新操作都比较简单,且并发程度不高的情况下是一个不错的选择。但是由于读锁与写锁互相阻塞,在读取或更新操作比较费时的情况下,会出现更新或读取线程被阻塞的风险,在高并发的场景下,这种阻塞不可接受。一个实例是数据库系统的全局schema管理器,每次事务都需要读取schema的内容,而DDL会引起schema更新,它的内容比较复杂,更新操作比较费时,会阻塞住处理事务的线程。

2. 引用计数的问题
为了解决读写操作相互阻塞的问题,使用类似Copy on write的方式,每次更新时都构造新的对象,在更新过程中,读取操作还是读取旧的对象,更新操作完成后,原子的替换掉指针使其指向新的对象。而被替换掉的对象不能立即释放,而是要确保这个对象不再被继续使用的情况下,才能将其释放掉。因此这里使用引用计数机制,在读取前将引用计数加1,读取完毕后将引用计数减1,当引用计数减到0的时候,表示没人在使用这个对象,可以将其释放掉。
引用计数在没有并发保护情况下面临的问题是,取得全局指针g_conf和通过这个指针操作对象的引用计数这两个操作并非原子的。可能存在的情况是,一个线程T1取得g_conf的值保存到寄存器后,就被切换出去,另外一个线程T2将g_conf替换后,判断旧的对象引用计数为0,则将其释放。当T1被切换回来继续执行时,它在寄存器中保存的g_conf指向的对象已经被释放,访问对象引用计数的这一次操作就已经存在非法内存访问的风险。
下面两节讨论两种解决并发引用计数的方案。

3. 带锁的引用计数
解决第2点提出的原子性问题,一个最直接的方式是使用锁,将读写g_conf和修改引用计数两个操作放在一个独立全局锁(g_lock)的临界区执行,代码示例如下:

读取并将引用计数加1:

fetch()
{
  g_lock.rdlock();
  g_conf->inc_ref();
  ret = g_conf;
  g_lock.unlock();
}

将引用计数减1:

revert(ptr)
{
  g_lock.rdlock();
  if(0 == ptr->dec_ref())
  {
    free(ptr);
  }
  g_lock.unlock();
}

使用新的对象替换旧对象:

set_new_conf(new_conf)
{
  g_lock.wrlock()
  if (0 == g_conf->dec_ref())
  {
    free(g_conf);
  }
  new_conf->inc_ref();
  g_conf = new_conf;
  g_lock.unlock();
}

在实际场景中,通常读取g_conf的操作更多且并发量大,而替换g_conf的操作不会经常发生,因此读取g_conf时加共享锁,替换g_conf时加互斥锁。
使用锁保护引用计数的方式在高并发的情况下存在一些局限:一方面可能存在读者或写者被饿死的情况;另一方面多个写者无法并发,应用在copy on write btree等数据结构中时,多个写者相互阻塞的问题会影响到整个数据结构的并发性能。

4. 无锁的引用计数
因此,一个更进一步的设计是使用无锁的引用计数,即无论读取g_conf还是替换g_conf都不在锁中进行,如下图所示:share_obj_seq_ref

RefNode的结构包含了指向GConf对象的指针data_ptr,以及引用计数ref_cnt,自增序列号seq_id,ref_cnt和seq_id长度都为4字节且地址连续,可以经由一次8字节的原子操作进行原子性的修改和读取。每次构造新的GConf对象的要同时分配新的RefNode来保存GConf对象的地址。
RefNode对象的分配和释放由专用的分配器进行分配和重用,一旦分配就不会释放回系统。引用计数的加1和减1,操作的是RefNode对象的ref_cnt字段,当引用计数减为0时,将data_ptr指向的对象释放,并将seq_id加1,然后将RefNode对象释放给内存分配器。已释放回分配器的RefNode对象仍然可以被安全的访问到。
替代全局GConf指针,我们增加了一个被称为GNode结构体的全局对象称为g_node,它包含了指向RefNode对象的指针称为node_idx,和这个RefNode中seq_id字段的值node_seq。node_idx和seq_id长度都为4字节且地址连续,可以经由一次8字节的原子操作进行原子性的读取和替换。
读取和替换操作的代码示例如下:
将引用计数加1并返回:

fetch()
{
  GNode tmp_g_node = atomic_load(g_node);
  while (true)
  {
    if (tmp_g_node.node_idx->atomic_check_seq_and_inc_ref(tmp_g_node.node_seq))
    {
      ret = tmp_g_node.node_idx;
      break;
    }
    else
    {
      tmp_g_node = atomic_load(g_node);
    }
  }
}

将引用计数减1:

revert(node_idx)
{
  if (node_idx->atomic_dec_ref_and_inc_seq())
  {
    free(node_idx->data_ptr);
    free_list.free(node_idx);
  }
}

使用新的对象替换旧对象:

set_new_conf(new_conf)
{
  RefNode *new_node = free_list.alloc();
  new_node->ref_cnt = 1;
  new_node->data_ptr = new_conf;

  GNode new_g_node;
  new_g_node.node_seq = new_node->seq_id;
  new_g_node.node_idx = new_node;

  GNode old_g_node = atomic_store_and_fetch_old(&g_node, new_g_node);
  if (old_g_node.node_idx->atomic_dec_ref_and_inc_seq())
  {
    free(old_g_node.node_idx->data_ptr);
    free_list.free(old_g_node.node_idx);
  }
}

其中几个原子操作的作用:
1. RefNode::atomic_check_seq_and_inc_ref原子性的判断如果seq_id等于传入参数就将ref_cnt加1,并返回true,否则返回false。
2. atomic_store_and_fetch_old原子性的将第二个参数赋值给第一个参数,并返回第一个参数的旧值。
3. RefNode::atomic_dec_ref_and_inc_seq原子性的将ref_cnt减1,并判断ref_cnt如果已减为0,则将seq_id加1并返回true,否则返回false。
工程实现上,为了达到node_idx长度只能有4字节的要求,RefNode分配器设计为定长数组,node_idx为数组下标,使用定长无锁队列作为分配器来维护空闲的node指针。一般来说一个线程只会增加一次引用计数,因此对于维护GConf这样全局只有一个的对象,定长RefNode数组的长度初始化为与线程个数相等就够用了。

5. HazardPointer
引用计数基本可以解决共享对象并发读写的问题,但它仍然存在一些不足:第一,每次读取都需要使用原子操作修改全局引用计数,高并发情况下的对同一个变量的原子操作可能成为性能瓶颈;第二,管理RefNode对象的无锁分配器有额外的管理和维护成本,增加的实现复杂度;第三,针对每个共享对象都需要维护N个(N为线程个数)RefNode,如果共享对象数量较多(比如Btree节点),为节省空间,还需要额外的机制来避免大量使用RefNode。
因此再介绍一种被称为HazardPointer的思路,它由Maged M. Michael在论文“Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects”中提出,基本思路是将可能要被访问到的共享对象指针(成为hazard pointer)先保存到线程局部,然后再访问,访问完成后从线程局部移除。而要释放一个共享对象时,则要先遍历查询所有线程的局部信息,如果尚有线程局部保存有这个共享对象的指针,说明这个线程有可能将要访问这个对象,因此不能释放,只有所有线程的局部信息中都没有保存这个共享对象的指针情况下,才能将其释放。
读取和替换操作的代码示例如下:

g_hp_array[N]; //保存每个线程局部信息的数组,N为线程个数

读取操作:

while(true)
{
  ret = g_conf;
  g_hp_array[thread_id] = ret;
  if (g_conf == ref)
  {
    break;
  }
  else
  {
    g_hp_array[thread_id] = NULL;
  }
}
// 读取逻辑代码…
g_hp_array[thread_id] = NULL;

使用新的对象替换旧对象:

set_new_conf(new_conf)
{
  retired_ptr = atomic_store_and_fetch_old(&g_conf, new_conf);
  found = false;
  for (i = 0; i < g_hp_array.length(); i++)
  {
    if (retired_ptr == g_hp_array[i])
    {
      found = true;
      break;
    }
  }
  if (!found)
  {
    free(retired_ptr);
  }
}

HazardPointer的设计解决了引用计数原子操作的性能瓶颈,避免了实现额外RefNode无锁分配器的复杂度。但是同时引入一个新的问题:由于回收内存的操作需要遍历查询全局数组g_hp_array,代价比较大,通常工程上的做法是将待回收的指针暂存在线程局部,等数量超过一个配置门限时,才进行批量回收。使得回收内存产生延迟,并且回收操作本身由于需要遍历数组,也会消耗较多的时间。
关于并发场景的问题,由于回收操作便利g_hp_array并不能保证原子的遍历,而HazardPointer的设计要求对象已经被放入g_hp_array后是能够安全访问的,因此可能存在如下时序:
1. 读取线程拿到g_conf指针存入局部变量ret
2. 更新线程将g_conf指针替换,扫描g_hp_array没有找到g_conf,释放g_conf内存
3. 读取线程将刚刚拿到的ret放入g_hp_array,然后开始使用ret,而此时ret指向的内存已经释放
为了处理这个问题,如上述伪代码所示,读取线程需要增加double check逻辑,判断如果从拿到g_conf到放入g_hp_array之间,可能有回收逻辑遍历过g_hp_array,则要重试。
因为替换g_conf意味着要将旧的g_conf释放,而释放意味着要先会遍历g_hp_array,因此读取线程只需要在将g_conf放入g_hp_array后,判断g_conf是否变化,如果变化了,则说明g_conf可能正好在从拿到g_conf到放入g_hp_array之间被释放了,因此需要重试。

6. HazardVersion

HazardPointer的实现简单,但是与引用计数法有着相似的不足:需要为每个共享变量维护O(N)个(N为线程个数)槽位,使用者需要仔细分析算法以尽量减少同时存在的hazard pointer 或者引入其他机制封装多个共享变量称为一个hazard pointer。这样就给使用者带来了比较大的难度,HazardPointer机制也与具体数据结构的实现比较紧的耦合在一起。

因此在HazardPointer基础上发展出了被称为HazardVersion技术,它提供类似lock一样的acquire/release接口,支持无限制个数共享对象的管理。

与HazardPointer的实现不同:首先全局要维护一个int64_t类型的GlobalVersion;要访问共享对象前,先将当时的GlobalVersion保存到线程局部,称为hazard version;而每次要释放共享对象的时候先将当前GlobalVersion保存在共享对象,然后将GlobalVersion原子的加1,然后遍历所有线程的局部信息,找到最小的version称为reclaim version,判断如果待释放的对象中保存的version小于reclaim version则可以释放。

读取和替换操作的代码示例如下:

g_version; //全局GlobalVersion
g_hv_array[N]; //保存每个线程局部信息的数组,N为线程个数

读取操作:

g_hv_array[thread_id] = g_version;
ret = g_conf;
// 读取逻辑代码…
g_hv_array[thread_id] = INT64_MAX;

使用新的对象替换旧对象:

set_new_conf(new_conf)
{
  retired_ptr = atomic_store_and_fetch_old(&g_conf, new_conf);
  retired_ptr->set_version(atomic_fetch_and_add(&g_version, 1));
  reclaim_version = INT64_MAX;
  for (i = 0; i < g_hv_array.length(); i++)
  {
    if (reclaim_version > g_hv_array[i])
    {
      reclaim_version = g_hv_array[i];
    }
  }
  if (reclaim_version > retired_ptr->get_version())
  {
    free(retired_ptr);
  }
}

可以看到,读取操作先保存了GlobalVersion到线程局部,然后去读取g_conf指针,虽然可能同时发生的回收操作遍历g_hv_array并不保证原子性,但是即使一个更小的hazard version被放入g_hv_array而错过了遍历,也不会有风险。

因为回收操作是先更新g_conf指针后遍历g_hv_array,而读取操作是先更新g_hv_array后读取g_conf指针,所以最坏情况下读取操作与回收操作同时发生,且读取操作放入g_hv_array的hazard version被回收操作遍历时错过,那么读取操作读到的g_conf一定是被回收操作更新之后的,本次不会被回收,可以安全的访问。

HazardVersion相对HazardPointer,在用法上更加简单,无需针对具体的数据结构进行分析,局限是需要在被管理的对象中保存version。其次,与HazardPointer一样,由于遍历g_hv_array比较费时,因此也需要引入类似的延迟回收机制。需要注意的是,它的缺点也比较明显,一旦出现一个线程长时间不释放HazardVersin时,会阻塞住后面更大Version对象的释放。

7. 总结
本文讨论了“读写锁”、“带锁的引用计数”、“无锁的引用计数”、“HazardPointer”、“HazardVersion”五种方法来处理共享对象的并发读写问题,在实际工程领域,“带锁的引用计数”比较常见,在特定场景下优化读写锁可以得到不错的性能,并且很易于理解和实现;“无锁的引用计数”实现复杂但并发读写性能卓越,在已开源的OceanBase版本中也有实践;“HazardPointer”实现简单,但是理解和使用都较复杂;“HazardVersion”是一种基于“HazardPointer”的创新思路,有一定的局限性,凭借简单易用的接口,可以在很多场景替代“HazardPointer”。