Because multiple leaders can propose a value for a given instance two
problems arise. First, proposals can conflict. Paxos uses ballots to
detect and resolve conflicting proposals. Second, it is not enough to
know that a given instance number has been committed, processes must
also be able to figure out which value has been committed.
LeaderElection 是 Fast Paxos 最简单的一种实现，每个 Server
启动以后都询问其它的 Server 它要投票给谁，收到所有 Server
回复以后，就计算出 zxid 最大的哪个 Server，并将这个 Server
相关信息设置成下一次要投票的 Server。该算法于 Zookeeper 3.4
以后的版本废弃。
收到所有 Server 回复以后，就计算出 zxid 最大的那个 Server，并将这个
Server 相关信息设置成下一次要投票的 Server；
线程将当前 zxid 最大的 Server 设置为当前 Server 要推荐的
Leader，如果此时获胜的 Server 获得多数 Server 票数， 设置当前推荐的
leader 为获胜的 Server，将根据获胜的 Server
相关信息设置自己的状态，否则，继续这个过程，直到 leader
被选举出来。
通过流程分析我们可以得出：要使 Leader 获得多数 Server 的支持，则
Server 总数必须是奇数 2n+1，且存活的 Server 的数目不得少于 n+1.
异常问题的处理：
选举过程中，Server 的加入
当一个 Server
启动时它都会发起一次选举，此时由选举线程发起相关流程，那么每个 Serve r
都会获得当前 zxi d 最大的哪个 Serve r 是谁，如果当次最大的 Serve r
没有获得 n/2+1 个票数，那么下一次投票时，他将向 zxid 最大的 Server
投票，重复以上流程，最后一定能选举出一个 Leader。
选举过程中，Server 的退出
只要保证 n/2+1 个 Server 存活就没有任何问题，如果少于 n/2+1 个 Server
存活就没办法选出 Leader。
int type; //消息类型 long leader; //Server id long zxid; //Server的zxid long epoch; //Server的epoch QuorumPeer.ServerState state; //Server的state long tag; //消息编号
InetSocketAddress addr;
}
线程处理
每个 Server 都一个接收线程池和一个发送线程池,
在没有发起选举时，这两个线程池处于阻塞状态，直到有消息到来时才解除阻塞并处理消息，同时每个
Server 都有一个选举线程(可以发起选举的线程担任)。
选举线程的处理
首先自己的 epoch 加 1，然后生成 notification
消息,并将消息放入发送队列中，系统中配置有几个 Server
就生成几条消息，保证每个 Server 都能收到此消息,如果当前 Server 的状态是
LOOKING
就一直循环检查接收队列是否有消息，如果有消息，根据消息中对方的状态进行相应的处理。
// Start and schedule the the purge task DatadirCleanupManagerpurgeMgr=newDatadirCleanupManager(config .getDataDir(), config.getDataLogDir(), config .getSnapRetainCount(), config.getPurgeInterval()); purgeMgr.start();
The zxid has two parts: the epoch and a counter. In our
implementation the zxid is a 64-bit number. We use the high order
32-bits for the epoch and the low order 32-bits for the counter. Because
it has two parts represent the zxid both as a number and as a pair of
integers, (epoch, count). The epoch number represents a change in
leadership. Each time a new leader comes into power it will have its own
epoch number.
从 currentEpoch 文件中读取 current epoch；若 currentEpoch
文件不存在，Zookeeper 将从 lastProcessedZxid 中获取 epoch 作为 current
epoch，写入 currentEpoch 文件。
try { currentEpoch = readLongFromFile(CURRENT_EPOCH_FILENAME); if (epochOfZxid > currentEpoch && updating.exists()) { LOG.info("{} found. The server was terminated after " + "taking a snapshot but before updating current " + "epoch. Setting current epoch to {}.", UPDATING_EPOCH_FILENAME, epochOfZxid); setCurrentEpoch(epochOfZxid); if (!updating.delete()) { thrownewIOException("Failed to delete " + updating.toString()); } } } catch(FileNotFoundException e) { // pick a reasonable epoch number // this should only happen once when moving to a // new code version currentEpoch = epochOfZxid; LOG.info(CURRENT_EPOCH_FILENAME + " not found! Creating with a reasonable default of {}. This should only happen when you are upgrading your installation", currentEpoch); writeLongToFile(CURRENT_EPOCH_FILENAME, currentEpoch); }
同理，获取 accepted epoch。
1 2 3 4 5 6 7 8 9 10 11 12
try { acceptedEpoch = readLongFromFile(ACCEPTED_EPOCH_FILENAME); } catch(FileNotFoundException e) { // pick a reasonable epoch number // this should only happen once when moving to a // new code version acceptedEpoch = epochOfZxid; LOG.info(ACCEPTED_EPOCH_FILENAME + " not found! Creating with a reasonable default of {}. This should only happen when you are upgrading your installation", acceptedEpoch); writeLongToFile(ACCEPTED_EPOCH_FILENAME, acceptedEpoch); }
ant -Djavac.args="-Xlint -Xmaxwarns 1000" clean test tar
Troubleshooting
1.在运行 unit test 的时候出现
1 2 3 4 5 6 7
create-cppunit-configure: [exec] configure.ac:37: warning: macro 'AM_PATH_CPPUNIT' not found in library [exec] configure.ac:37: error: possibly undefined macro: AM_PATH_CPPUNIT [exec] If this token and others are legitimate, please use m4_pattern_allow. [exec] See the Autoconf documentation. [exec] configure.ac:57: error: possibly undefined macro: AC_PROG_LIBTOOL [exec] autoreconf: /usr/bin/autoconf failed with exit status: 1
解决方法：
1
sudo apt-get install libtool
2.在运行 unit test 的时候出现
1 2 3 4 5 6
create-cppunit-configure: [mkdir] Created dir: /home/killua/Workspace/zookeeper/build/test/test-cppunit [exec] checking for doxygen... no [exec] checking for perl... /usr/bin/perl [exec] checking for dot... no [exec] configure: error: cannot find install-sh, install.sh, or shtool in "/home/killua/Workspace/zookeeper/src/c" "/home/killua/Workspace/zookeeper/src/c/.." "/home/killua/Workspace/zookeeper/src/c/../.."
SkipList
通过对间隔的数据做一个标签索引，产生了多层单链表，在最高层依次确定查找数据的范围，最终将范围缩小到可接受值，我们看
SkipList
其实就是一个二叉查找树的变形，只是所有的数据都在最左段，其他节点用来建立查找索引，如此
SkipList 的插入删除就比二叉查找树方便多了。
如果 K
大于链表的层数，则要添加新的层。
