Etcd 之 Lease read

2019-12-16 17:24:09

Introduce

Etcd 是一个建立在分布式 kv 基础之上的分布式配置管理服务软件，其分布式数据一致性复制是采用的 raft。今天将和大家一起学习下 Etcd 对 ReadOnly 请求是如何处理的，鉴于其他的博文中已经有关于 ReadIndex 的实现介绍，这里将只为大家介绍 Lease read。

首先回顾下 raft 的 Read 方案：

和 write 一样，每一个 read 都走一遍日志复制，安全性好，但是性能不好
ReadIndex 方案将 read 请求还是发给 leader，然后记录下当前的 commit index；为了避免当前 leader 因为网络分区被隔离而读到旧数据（当然为了保证不会读到旧数据，leader 刚当选时，并不知道 commit index 在哪，所以需要提交一条 noop 来隐式提交之前的所有 log entries），所以需要向复制组其他 Peers 发送 heartbeat 确认自己 leader 身份，如果大多数返回，那么说明自己是 leader，则可以提供服务。那么等到 applied index >= commit index，即可 read 数据向用户返回。这里将方案1的复制日志的开销替换成了 heartbeat，做到了一定的优化
Lease read 方案：实际上就是通过一定的手段维护 leader 的租约，保证 leader 的性，从而将 read 请求发送给 leader 之后，无需通过发送 heartbeat 确认 leader 身份。因为通过 lease 机制可以实现 leader 在租约过期之后自动 step down 为 follower。这种方案性能好，但是可能会存在因为时钟的问题到 lease 机制有问题，出现双主，从而可能读到旧数据。所以默认 Etcd 使用的所谓的 safe 方式，也就是方案 2

上述的三种方案都可以实现 linearizable read。

疑问：为什么 read 请求到达 leader 之后需要获取新的 commit index，然后再等到 applied index >= commit index 之后再 read 数据返回？不能直接 read 返回吗？

答案：不可以，因为那样不满足 linearizable read，因为要想满足 linearizable read 那么必须保证，已经被 read 到的数据，那么后面的 read （非并发的 read）都应该能 read 到，也就是不会出现 read 到旧数据。我们已 commit index 为依据去 read，可以保证 read request 到达 leader 越晚，其 commit index 必然越大，也就是 r1 arrive time <= r2 arrive time，那么 r1 commit index <= r2 commit index，那么 r2 read 到的数据就至少和 r1 一样新，从而保证了 linearizable read。

相反，直接 read 返回，相当于是记录下当前 applied index，但是 applied index 并不是严格的单调的往上增加的，例如集群 {A，B，C}开始 A 为 leader，这个时候 applied index 为 a1，然后 A 挂了，B 重新选举为了 leader，这个时候 B 的 applied index 为 a2，那么我们并不能保证 a2 >= a1，因为很有可能，B 由于日志复制延迟导致日志虽然复制过去了（保证拥有新的日志，能选为 leader），但是还没来得及 apply，那么如果一个 read 来到 B，可能就会 read 到旧数据，出现 read 的新旧数据反转，从而不满足线性一致性。

Lease read

当然，为了保证 linearizable read，Etcd 的 lease read 当然是获取 commit index，然后等到 applied index >= commit index 之后在 read。下面给出代码详细分析，整个实现很简单。

首先 EtcdServer 在收到 read 请求后，通过 Node 的 ReadIndex 接口向 raft 状态机提交一个 MsgReadIndex message，接着进入 stepLeader 处理，如果设置了 Lease read，那么就会进入 case ReadOnlyLeaseBased 分支，然后：

记下当前的 commit index
构造一个 read state，append 到 raft readStates 中，这样下次处理 Ready 的时候，就会处理这个 Read 请求

func stepLeader(r *raft, m pb.Message) error {
    switch m.Type {
    case pb.MsgReadIndex:
            ......
            switch r.readOnly.option {
            // 方案2 ReadIndex    
            case ReadOnlySafe:
                ......
            // 方案3 Lease read
            case ReadOnlyLeaseBased:
                ri := r.raftLog.committed
                if m.From == None || m.From == r.id { // from local member
                    r.readStates = append(r.readStates, ReadState{Index: r.raftLog.committed, RequestCtx: m.Entries[0].Data})
                } else {
                    r.send(pb.Message{To: m.From, Type: pb.MsgReadIndexResp, Index: ri, Entries: m.Entries})
                }
            }

然后在看看 raftNode 是如何处理 Ready 中的 ReadState 的 ? 如下代码直接通过 Channel readStateC 返回给 EtcdServer apply read request 了。

func (r *raftNode) start(rh *raftReadyHandler) {
    go func() {
        ......
        for {
            .....
            case rd := <-r.Ready():
        if len(rd.ReadStates) != 0 {
                    select {
                    // readState 中保存的是 commit index，所以只需要后一个 readState 就可以
                    case r.readStateC <- rd.ReadStates[len(rd.ReadStates)-1]:
                    ......
                    }
                }
        }
    }
}

但是并没有看到 Lease 相关的内容，实际上 Etcd raft 模块是通过周期性（Election timeout）的检查 leader 是否和大多数 peers 有正常通信，也就是确定自己的 Leader 身份，如果发现自己没有能大多数 Peers 保持正常的通信，那么就有可能有 leader 已经被选出来，所以 leader 会自动 step down 为 follower。那么 leader 是在什么时候触发检查的呢？又是如何记录自己和其他 peer 通信状态的呢？

func (r *raft) tickHeartbeat() {
    r.heartbeatElapsed++
    r.electionElapsed++

    if r.electionElapsed >= r.electionTimeout {
        r.electionElapsed = 0
        if r.checkQuorum {
            r.Step(pb.Message{From: r.id, Type: pb.MsgCheckQuorum})
        }
        ......
    }

Leader 在每次心跳的时候，会判断是否已经 election timeout，如果是，那么就执行 MsgCheckQuorum 的检查，实际上就是检查自己是否仍和集群大多数节点保持通信，也就是确认自己的 Leader 身份。

func stepLeader(r *raft, m pb.Message) error {
    switch m.Type {
    .....
    case pb.MsgCheckQuorum:
        if !r.checkQuorumActive() {
            r.logger.Warningf("%x stepped down to follower since quorum is not active", r.id)
            // step down 为 follower
            r.becomeFollower(r.Term, None)
        }
        return nil

quorum check 实际上是统计复制组 Peers 的 RecentActive 字段是 true 的 Peers，如果为 true，说明近此 Peer 近和 leader 有正常通信且认可 leader 的身份，如果有超过半数，那么说明 leader 身份没有问题。下面的每个 Progress 对应一个 Peer

func (r *raft) checkQuorumActive() bool {
    var act int

    r.forEachProgress(func(id uint64, pr *Progress) {
        if id == r.id { // self is always active
            act++
            return
        }

        if pr.RecentActive && !pr.IsLearner {
            act++
        }
        // 每次 election timeout 会重新将 RecentActive 设置为 false
        pr.RecentActive = false
    })

    return act >= r.quorum()
}

通过 pr.RecentActive = false 可以知道每次 election timeout 会将 RecentActive 设置为 false，那么什么时候设置为 true，实际上 leader 在收到正常的 follower 的任何 msg（heartbeat 或者其他 message 的 response）的正常回复，都会将 RecentActive 设置为 true。这样就相当于间接的实现了 lease 机制。下面给 leader 收到 MsgAppResp 为例：

func stepLeader(r *raft, m pb.Message) error {
    ......
    switch m.Type {
    case pb.MsgAppResp:
        pr.RecentActive = true
        ......

Summary

Etcd 通过记录 Leader 和 Peers 近通信的状态巧妙的实现 lease read，非常简单有效。但是这并不能完全消除时钟对其的影响，所以 Etcd 默认并没有采用 Lease read，并给出非安全的警告，如下注释：

// ReadOnlyLeaseBased ensures linearizability of the read only request by
// relying on the leader lease. It can be affected by clock drift.
// If the clock drift is unbounded, leader might keep the lease longer than it
// should (clock can move backward/pause without any bound). ReadIndex is not safe
// in that case.

Notes

于作者水平，难免有理解和描述上有疏漏或者错误的地方，欢迎共同交流；部分参考已经在正文和参考文献中列表注明，但仍有可能有疏漏的地方，有任何侵权或者不明确的地方，欢迎指出，必定及时更正或者删除；文章供于学习交流，转载注明出处

References
[1]. etcd. https://github.com/etcd-io/etcd
[2]. Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[J]. Draft of October, 2014.