raft论文学习-cluster membership changes

集群成员变更

在实际工程环境中，会存在偶尔改变集群配置的情况。例如替换掉宕机的机器。虽然可以通过将集群所有机器下线，更新所有配置，然后重启整个集群的方式来实现。但是这会存在以下问题：

1. 集群中的机器会先停机然后重启，在这个过程中，集群不能对外提供服务，在生产环境中是不能接受的
2. 通过手工操作，存在操作失误的风险

为了使配置变更机制能够安全，在转换的过程中不能够在任何时间点使得同一个任期里可能选出两个leader，这不满足raft的规则。槽糕的是，任何机器直接从旧配置转换到新的配置的方案都是不安全的。一次性自动地转换所有机器是不可能的，在转换期间整个集群可能被划分成两个独立的大多数。

下面通过例子来说明可能会同时出现两个leader的情况。在成员变更前是3节点的集群，集群中的节点为A、B和C，其中节点A为leader节点. 现在向集群中增加节点D和E,加入成功后变成5节点集群。集群旧配置用Cold表示，则Cold={A,B,C}。新配置用Cnew表示，则Cnew={A,B,C,D,E}.

在集群变更前，A为leader节点，节点C和B已同步完节点A的最新数据。此时，站在节点A/B/C任意一个节点的角度来说，都是知道有另外两个节点存在的。例如对于C节点来说，它知道除了自己集群中还有节点A和节点B.

现在向集群中添加节点D和E.对于节点D和E来说，在添加时它们是知道集群已存在节点A、节点B和节点C的。即在节点D和E眼中，集群的配置是有A/B/C/D/E五个节点的。新增的节点信息会同步给其他节点，同步的过程是需要一点时间的，而不是在一个时刻节点A、节点B和节点C都知道了有新的节点D和E加入。这里假设节点A先知道了D和E加入，在C和B还未知道D和E的情况下，出现了网络分区。C/B是一个分区，A/D/E是一个分区。C/B分区由于接收不到节点A的心跳，会出现竞选投票，假设节点C先出现竞选，它会收到节点B给他的投票，因为节点B的数据不会比节点C新。此时，节点C可以成功当选leader。因为它没有感知到节点D和E，所以在它眼中集群还是3个节点，已收到2个投票（节点B+自己），可以当选。A/D/E分区中节点A是可以继续作为leader节点的，虽然在A/D/E眼中，集群是有五个节点构成的，但是他们有3个节点，也构成一个5节点中的大多数。这就出现了集群中存在C和A两个leader的情况。

为了保证安全性，配置变更必须采用一种两阶段方法。在raft中，集群先切换到一个过渡的配置，称之为联合一致(join consensus)，一旦联合一致已经被提交后，系统可以切换到新的配置上。联合一致结合了老配置和新配置：

• 日志条目被复制给集群中新、老配置的所有服务器
• 新旧配置的服务器都可以成为leader
• 对于选举和提交的达成一致需要分别在两种配置上获得过半的支持

联合一致(join consensus)允许服务器在保持安全的前提下，在不同的时刻进行配置转换，并且允许集群在配置变更期间依然响应客户端请求。

上图来自raft论文，描述了联合一致过程中配置变更流程。图中虚线代表已创建但是未提交的配置，实线代表最新的已提交的配置。leader会首先创建Cold-Cnew日志项，并复制到新旧配置节点中的大多数。然后创建Cnew日志项，并复制到Cnew新配置的大多数。

这里说下上面配置的含义，上面配置就是集群中有哪些节点组成。通过例子加以说明。假设一个集群之前有A/B/C三个节点，现在发生配置变更，需要添加D和E两个节点。Cold,Cold-new,Cnew配置为：

Cold={A,B,C}
Cold-Cnew={A,B,C},{A,B,C,D,E}
Cnew={A,B,C,D,E}

注意，Cold-Cnew有些文章写成Cold∪Cnew是有误导性的，我在看的时候有疑惑，如果理解成∪，那上面的Cold-Cnew进行并集处理后不是变为了{A,B,C,D,E}，这不成了Cnew. 为了理清疑惑，查看了logcabin实现，logcabin(https://github.com/logcabin/logcabin)是基于raft构建的分布式存储系统，可提供少量高度复制的一致存储, 它的集群变更采用这里的联合一致性方法，Cold-Cnew配置代码如下，它们是两个独立的集合。

if (newDescription.next_configuration().servers().size() == 0)
        state = State::STABLE;
    else
        state = State::TRANSITIONAL;
    id = newId;
    description = newDescription;
    oldServers.servers.clear();
    newServers.servers.clear();

    // Build up the list of old servers
    for (auto confIt = description.prev_configuration().servers().begin();
         confIt != description.prev_configuration().servers().end();
         ++confIt) {
        std::shared_ptr<Server> server = getServer(confIt->server_id());
        server->addresses = confIt->addresses();
        oldServers.servers.push_back(server);
    }

    // Build up the list of new servers
    for (auto confIt = description.next_configuration().servers().begin();
         confIt != description.next_configuration().servers().end();
         ++confIt) {
        std::shared_ptr<Server> server = getServer(confIt->server_id());
        server->addresses = confIt->addresses();
        newServers.servers.push_back(server);
    }

下面结合上述变更图，从时间角度进行一个分析。整个变更过程划分为如下的区间。

1. 当时间 t<Time1时，此时集群处于配置变更前的状态，全是Cold节点
2. 当时间 Time1<t<Time2时，集群开始进行配置变更，leader开始把Cold-Cnew节点复制给其他节点。这个时间段里面，Cold-Cnew和Cold节点共存，选举出来的leader可能是拥有Cold配置的节点，也有可能是拥有Cold-Cnew配置的节点。拥有Cold-Cnew配置节点选举成功的条件是：Cold和Cnew中的大多数节点都同意。如果是Cold-Cnew配置节点选举成功，根据选举成功的条件，它一定是获得了Cold中大多数节点的同意，所以单纯的Cold配置节点不能选举成功。同理，如果Cold配置中的节点选举成功，那么Cold-Cnew配置中的节点是不能成功选举的，因为不满足条件中的Cold的大多数节点同意。
3. 当时间 Time2<t<Time3时，leader已成功将Cold-Cnew配置复制到大多数节点，此时集群中可能有Cold配置节点。但来自Cold配置节点不能选出成为leader了。这个时间段选出的leader必然是拥有Cold-Cnew配置的节点。因为Cold-Cnew日志节点占了大多数，即使在Cold集群中，如果选举leader成功，必须有一个拥有Cold-Cnew日志的follower,但是Cold-Cnew中的follower更新，它会拒绝来自Cold中节点的选举请求。
4. 当时间 Time3<t<Time4时，选举出来的leader可能是拥有Cold-Cnew配置的节点，也有可能是拥有Cnew配置的节点。但是只能是其中一个，假设Cold-Cnew中的节点当选成功，肯定是满足了条件有大多数Cnew节点同意，所以Cnew配置中的节点不可能当选为leader。同理，来自Cnew配置中的节点当选为leader,Cold-Cnew就不能当选为leader了。
5. 当时间 t>Time4时，选举出来的leader一定是拥有Cnew配置的节点，因为如果存在一个拥有Cold-Cnew的节点请求当选leader，则需要Cnew中的大多数节点同意，但是Cnew中的大多数已经写入了Cnew日志，所以不会响应Cold-Cnew节点。

论文中还分析了配置变更其他需要解决的三个问题：

• 问题1：新加进来的节点开始时没有存储任何日志条目，当它们加入到集群中，需要一段时间来更新日志才能赶上其他节点，这段时间内它们无法提交新的日志条目。为了避免上述问题而造成的系统短时间的不可用，raft在配置变更前引入了一个额外的阶段，在该阶段，新的节点以没有投票权身份加入到集群中，leader也复制日志给它们，但考虑过半的时候不用考虑它们，一旦新节点追赶上了集群中的其他机器，配置变更可以按照上面描述的方式进行。
• 问题2：集群的leader可能不在新配置Cnew中，这种情况，leader一旦提交了Cnew日志条目就会退位到followr状态。这意味着有一个时间段（leader提交Cnew期间），leader管理的是一个不包括字节的集群，它复制日志但不把自己算在过半里面。leader转换发生在Cnew被提交的时候，这个时候是新配置可以独立做决定的最早时刻，在此之前只能从Cold中选出leader.
• 问题3：被移除的节点即不在Cnew配置中的节点可能会扰乱集群。这些节点将不会再接收到心跳，当选举超时时候，它们会进行新的选举过程。它们会发送带有新任期号的requestVote RPC,这会导致当前的leader回到follower状态。新的leader最终会被选出来，但被移除的节点会再次超时，导致系统可用性很差。处理方法是，当服务器认为当前leader存在时，会忽略requestVote PRC。特别当服务器在最小选举超时时间内收到一个requestVote RPC，它不会更新任期号或投票。这不会影响正常的选举，因为每个节点在开始一次选举之前，至少等待最小选举超时时间。