Summary

领导者选举对于分布式系统来说是一个很重要的主题，一个设计良好的领导者能够减少节点间协调的开销来提高性能。选举的过程可能也会带来成本但他们基本是很低频的，因此对整个系统的性能来说并没有很负面的影响。一个单独的领导者可能会成为系统的瓶颈，但大部分情况下可以通过对数据进行分区然后为每个不同分区的不同操作提供不同的领导者来解决这个问题。

不幸的是，本章中所有我们讨论的算法都有脑裂的问题：每个独立的子集中都可能会出现两个领导者并且互相之间都没有发现对方的存在。为了避免发生脑裂，我们需要收集整个集群中的大部分选票。

许多的一致性算法，包括 Multi-Paxos 跟 Raft，都依赖于领导者来进行协调。但领导者的选举不就跟达成共识是一样的吗？为了选出一个领导者，我们需要对他的标识符达成共识。如果我们能够对领导者的标识符达成共识，那我们就可以使用相同的方式为任意的东西达成共识。

领导者的标识符可以在处理器对其没有认识的情况下发生变更，因此问题是处理器如何得知本地关于领导者的信息是否有效。为了实现这个，我们需要将领导者选举跟故障检测进行结合。比如 stable leader election 算法使用包含了唯一稳定领导者标识跟基于超时的故障检测的方式来保证在不发生崩溃跟能够被访问到的前提下，领导者都是有效的。

依赖于领导者选举的算法通常都能够支持扩展到多个领导者，并会试图尽可能快的去解决领导者之间的冲突。比如 Multi-Paxos 中两个冲突的领导者 (叫做提议者 Proposer) 只要一个能够继续执行，他们之间的冲突则通过收集另一轮的 Quorum 的选票来解决，保证来自两个不同提议者的值不会被同时接受。

在 Raft 中，领导者能够发现他的任期是否已经过期，这暗示了系统当前已经存在另一个领导者，并且他有着比自己还要大的任期信息。

在这两种情况中，要保证领导者的存活性 (即如果当前领导者发生故障，我们就需要一个新的领导者)，不能让处理器们一直无限的试图去了解他是否真的发生了故障。较弱的安全性跟多个领导者是对性能的一个优化：算法可以处理复制的步骤，安全性则通过冲突的检测跟坚决来保证。

我们会在 Chapter 14 关于一致性的上下文中讨论更多关于一致性跟领导者选举的信息。

更多阅读

如果你想对我们本章中讨论的概念有更多的了解，可以通过下面的引用获取相关信息

  • Leader election algorithms
    • Lynch, Nancy and Boaz Patt-Shamir. 1993. “Distributed algorithms.” Lecture notes for 6.852. Cambridge, MA: MIT.
    • Attiya, Hagit and Jennifer Welch. 2004. Distributed Computing: Fundamentals, Simulations and Advanced Topics. USA: John Wiley & Sons.
    • Tanenbaum, Andrew S. and Maarten van Steen. 2006. Distributed Systems: Princi‐ ples and Paradigms (2nd Ed.). Upper Saddle River, NJ: Prentice-Hall.