在分布式计算中，leader选举是指通过选举产生一个领导者节点，该领导者节点能将任务分布到其他不同节点。起初，集群各节点是不感知哪个是”leader“节点的。在领导者选举算法运行后，集群中的每个节点识别一个特定的、唯一的节点作为leader，其他节点作为follower节点。

Leader：作为集群特殊节点执行一些特殊操作。这些操作包括分配任务，修改一些数据的能力，甚至负责所有系统请求。
Follower：集群中执行分配任务节点。
例如：Kubernetes集群

在控制平面运行多个Kube-scheduler实例
只有选举产生的leader节点的实例负责将pod调度到各节点。

领导者选举

通常leader选举使用分布式锁来实现，所有的节点竞争同一个资源上的锁，获取到锁的节点成为leader。要实现分布式锁，需要一个强一致性系统来决定哪个节点持有锁，因为这个过程必须是原子操作。典型的一致性协议例如Paxos、Raft协议都用于这个目的。然而要正确地实现这些算法是非常困难的，因为必须经过广泛的测试和严格验证才行。领导者选举也可以使用第三方工具，如zookeeper, etcd, consul来实现，但这会增加保持高可用系统的开销。

因为我们在Metro【一个开源项目】中使用Consul作为数据库注册中心，所以我们决定在leader选举实现中使用相同的方法。让我们看看如何使用Consul实现分布式锁。

实现分布式锁

提供分布式锁需要的基本要求：
1、互斥：在任何时候只有一个节点持有锁。
2、无死锁：最终，即使锁定资源的节点发生故障，其他节点也可以获得锁。
3、容错：只要大多数节点还正常工作，锁的获取和释放就可以完成。

consul

consul是一个分布式高可用的Key-value存储系统（类似etcd和zookeeper）。数据在consul中以KV格式存储。

让我们来看看Consul是如何满足分布式锁定需求的。

互斥性

Consul要求客户端使用session API创建会话。
在使用API获取KV资源时需要session id。
确保只有1一个节点能成功

无死锁

session有TTL（存活时间），如果session过期，所有拿到的key就会释放/删除，因此客户端需要定时更新session避免过期。

容错

consul运行在高可用模式。

基于consul使用Go来实现Leader选举

选举可以通过一下4个步骤来实现：

1、创建具有存活时间TTL的session

sessionID, _, err := client.Session().Create(&api.SessionEntry{
    Name: "my-service-lock",
    Behavior: "delete",
    TTL: "30s",
    LockDelay : 2 * time.Second
}, nil)

if err != nil {
    panic(err)
}

TTL的选择是根据应用来的决定的。TTL太大的话，在leader故障时需等到过期才会有新的leader选举产生。如果太小会频繁的更新session增加系统的负载。
LockDelay防止KV在释放后立即被获取，这个延迟间隔可以被领导者用来执行退出相关的动作。
2、更新session
使用Renew / RenewPeriodic API定期更新会话。在TTL过期前，会话将按照TTL持续时间进行更新。

client.Session().RenewPeriodic(
        "30s",
        sessionID,
        nil,
        doneChan,
    )

这是一个阻塞调用，因此应该在单独的goroutine中运行。通常，doneCh是当前上下文的Done通道。

根据Key获取锁

isAcquired, _, err := client.KV().Acquire(&api.KVPair{
  Key:    "path/to/leader/key",
  Value:   []byte("any value"),
  Session: sessionID,
}, nil)

if err != nil {
  // 错误处理
}
// 如果没有错误，isAquired为true就是领导者节点

能够获得锁的节点可以定为leader，其他节点成为follower。

“Value”可以用来在leader和follower之间传递集群状态。例如，如果follower想要连接leader，leader可以在Value中包含它的标识符。

观察领导者key

params := map[string]interface{}{}
params["type"] = "key"
params["key"] = "path/to/leader/key"

plan, err := watch.Parse(params)
if err != nil {
  // 错误处理
}

// 当所监视的key发生任何更改时调用该handler函数
plan.Handler = handler

//  阻塞调用，因此这段代码应该在goroutine中运行
plan.RunWithClientAndHclog(client, nil)

handler函数

func handler(index uint64, result interface{}) {
  log.Printf("watch data: %s", result)
  // 检查返回的键是否有sessionID
  // 如果session ID存在，则key被某个节点获取
  // 如果没有，目前没有领导者，尝试获取key
}

使用watch功能，可以观察key的变化。如果领导者key发送变化，Consul会通知的，因此session会被删除/自动过期，领导者key释放被其他节点获取，导致KV的更新。所有watch这个key的节点都会被通知有变化。在收到通知后，所有节点可以检查key的状态，并运行新的选举。

从概念上讲很简单，但在编写生产系统时，需要考虑许多边界情况，例如：

部署时会发生什么——在部署时，leader节点将关闭，为了优雅地处理，leader应该退出，让其他节点立即成为leader。可以通过释放会话锁或删除会话本身来退让。
如果leader/worker节点意外宕机怎么办？如果该节点意外退出，而leader没有退让，那么其他节点仍然会认为leader存在，直到会话过期，所以根据应用程序需求选择一个好的TTL很重要。

代码

你可以参考Metro的领导者选举实现。

参考文献

https://learn.hashicorp.com/tutorials/consul/application-leader-elections
https://clivern.com/leader-election-with-consul-and-golang/

使用consul和Go实现领导者选举