在 Google Cloud Storage 中实现领导者选举

领导者选举（Leader election） 是实现分布式系统的常用模式。例如，副本式关系数据库（如 MySQL） 或分布式键值存储（如 Apache Zookeeper） ，在副本中选择一个领导者（有时称为主）。 所有的写操作都经过领导者，所以任何时候只有一个节点在写系统。 这样做是为了确保不会丢失任何写入并且数据库不会损坏。

由于网络系统和时间同步的性质，在分布式系统的节点中选择领导者可能具有挑战性。在本文中，我们将讨论为什么需要领导者选举（或更一般的说法“分布式锁”），解释为什么它们难以实现，并提供一个使用强一致性存储系统（在本文中的示例为 Google Cloud Storage） 的示例实现。

为什么我们需要分布式锁？

试想一个多线程的程序，其中每个线程都与一个共享变量或数据结构进行交互。为了防止数据丢失或数据结构被破坏，多个线程在修改状态时应该互相阻止并等待。我们在单进程应用程序中使用互斥锁来确保这一点。分布式锁在这方面与单进程系统中的互斥锁并没有什么差异。

一个处理共享数据的分布式系统仍然需要一个锁定机制来安全地轮流修改共享数据。但是，在分布式环境中工作时，我们不再有互斥锁的概念。这就是分布式锁和领导者选举出现的原因。

领导者选举的使用案例

通常，领导选举被用于确保单个节点对共享数据的独占访问，或是确保单个节点协调系统中的工作。

对于 MySQL、Apache Zookeeper 或 Cassandra 等副本式数据库系统，我们需要确保在任何特定时间只存在一个“领导者”。 所有写入都要通过这个领导者，以保证写入发生在一个地方。同时，可以由跟随者节点提供读取服务。

这里有另外一个示例。对于一个使用消息队列中的消息的应用程序，您有三个节点；然而在这些节点中只有一个是随时处理消息的。通过选择领导者，您可以指定一个节点来履行该职责。如果领导者变得不可用，其他节点可以接管并继续工作。在这种情况下，就需要进行领导者选举来协调工作。

许多分布式系统都利用了领导者选举或分布式锁的模式。然而，领导者选举并非是一个简单的问题。

为什么分布式锁很难？

分布式系统就像单进程程序的线程，除了它们位于不同的机器上并且它们通过网络相互通信（这可能是不可靠的）。因此，它们不能依赖互斥锁或使用原子 CPU 指令和共享内存的类似锁机制来实现锁。

分布式锁问题需要参与者就谁持有锁达成一致。我们还期望在系统中的某些节点不可用时选出领导者。这听起来非常简单，但正确实施这样的系统可能非常困难，部分原因是存在许多边缘情况。这就是分布式共识算法出现的原因。

要实现分布式锁，你需要一个强一致性系统来决定哪个节点持有锁。因为这必须是原子操作，所以需要 Paxos、 Raft 等共识协议，或者两阶段提交协议。 然而，正确地实现这些算法是相当困难的，因为这些实现必须经过广泛的测试和正式的证明。此外，这些算法的理论特性往往无法承受现实世界的条件，这导致了对该主题的更深入的研究。

在 Google， 我们使用被称为 Chubby 的服务来实现分布式锁。在我们的堆栈中，Chubby 帮助 Google 的许多团队利用分布式共识，而不必担心从头开始实现锁服务（并且这样做是正确的）。

作弊方式：利用其他存储原语

您可以轻松利用强一致性存储系统，而不是实施自己的共识协议，该系统通过单个密钥或记录提供相同的保证。通过将原子性的责任委托给外部存储系统，我们不再需要参与节点形成法定人数并投票选出新的领导者。

例如，分布式数据库记录（或文件）可用于命名当前领导者，以及领导者何时更新其领导锁定。如果记录中没有领导者，或者领导者没有更新它的锁，其他节点可以通过尝试将他们的名字写入记录来竞选。第一个来的将胜出，因为这个记录或文件允许原子写入。

这种对文件或数据库记录的原子写入通常使用乐观并发控制来实现，它允许您通过提供其版本号来原子地更新记录（如果此后记录发生更改，则写入将被拒绝）。类似地，写入内容立即可供任何读者使用。使用这两个原语（原子更新和一致读取），我们可以在任何存储系统之上实现领导者选举。

事实上，很多 Google Cloud Storage 产品，比如 Cloud Storage、Cloud Spanner 等都可以实现这样的分布式锁。 同样，开源存储系统如 Zookeeper  (Paxos) 、etcd (Raft) 、Consul (Raft) ，甚至是正确配置的 RDBMS 系统如 MySQL 或 PostgreSQL 都可以提供所需的原语。

示例：使用 Cloud Storage 实现领导者选举

我们可以使用 Cloud Storage 上包含领导者数据的单个对象（文件）来实现领导者选举，并要求每个节点读取该文件，或基于该文件举行选举。在这个设置中，领导者必须通过用它的心跳更新这个文件来更新它的领导权。

My colleague Seth Vargo published such a leader election implementation – written in Go and using Cloud Storage – as a package within the HashiCorp Vault project. (Vault also has a leader election on top of other storage backends).

我的同事 Seth Vargo 发布了这样一个领导者选举的实现——这个示例作为 HashiCorp Vault 项目中的一个包——用 Go 编写并使用 Cloud Storage。 （Vault 在其他存储后端之上也有一个领导者选举）。

为了在 Go 中实现我们应用程序分布式节点之间的领导者选举，我们可以编写一个只需 50 行代码的程序来使用这个包：

01      import (
02             "context"
03 
04             log "github.com/hashicorp/go-hclog"
05             "github.com/hashicorp/vault/physical/gcs"
06             "github.com/hashicorp/vault/sdk/physical"
07      )
08 
09      const (
10             bucketName     = "YOUR_GCS_BUCKET_NAME"
11             leadershipFile = "leader.txt"
12      )
13
14      func main() {
15             logger := log.Default()
16             b, err := gcs.NewBackend(map[string]string{
17                   "bucket":     bucketName,
18                   "ha_enabled": "true",
19             }, logger)
20             if err != nil {
21                   panic(err)
22             }
23             haBackend, ok := b.(physical.HABackend)
24             if !ok {
25                   panic("type casting failed")
26             }
27 
28             ctx, cancel := context.WithCancel(context.Background())
29             defer cancel()
30
31             for {
32                   lock, err := haBackend.LockWith(leadershipFile, "ignored")
33                   if err != nil {
34                          panic(err)
35                   }
36
37                   logger.Info("running for LEADERSHIP")
38                   doneCh, err := lock.Lock(ctx.Done())
39                   if err != nil {
40                          panic(err)
41                   }
42                   logger.Info("elected as LEADER")
43                   <-doneCh
44                   logger.Info("lost LEADERSHIP")
45                   if err := lock.Unlock(); err != nil {
46                          panic(err)
47                   }
48             }
49      }

此示例程序使用 Cloud Storage 中的文件创建锁，并持续运行以进行选举。

在这个例子中，Lock() 调用会阻塞，直到调用程序成为领导者（或上下文被取消）。此调用可能会无限期阻塞，因为系统中可能还存在另一个领导者。

如果一个进程被选为领导者，库会定期发送心跳以保持锁处于活动状态。然后领导者必须完成工作并通过调用 Unlock() 方法放弃锁定。 如果领导者失去领导权，则 doneCh 通道将收到一条消息，进程可以告诉它已经失去了锁定，因为可能有一个新的领导者。

对我们来说非常幸运的是，我们使用库来实现了心跳机制，以确保当选的领导者保持可用和活跃状态。如果当选的领导者在不放弃所得情况下突然出失败，则锁上的 TTL（生存时间）过期之后，其余节点会选举新的领导者，以确保整个系统的可用性。

幸好这个库实现了关于发送所谓的周期性心跳的上述细节，或者追随者应该检查领导者是否死亡以及他们是否应该参加选举的频率。类似地，该库通过将领导数据存储在对象元数据中而不是对象内容中来采用各种优化，这会导致频繁读取成本更高。

如果您需要确保节点之间的协调，在分布式系统中使用领导选举可以帮助您安全地实现至多一个节点承担此责任。使用 Cloud Storage 或其他强一致性系统，您可以实现自己的领导者选举。但是，在实现新的此类库之前，请确保您已了解所有极端情况。