ZooKeeper-20-内部原理
ZooKeeper内部原理
本章与其他章节不同，本章不会讲解任何关于如何通过ZooKeeper构建⼀个应⽤程序相关的知识，主要是介绍ZooKeeper内部是如何运⾏的，通过从⾼层次介绍其所使⽤的协议，以及ZooKeeper所采⽤的在提供⾼性能的同时还具有容错能⼒的机制。这些内容⾮常重要，通过这些为⼤家提供了⼀个更深度的视⾓来分析为什么程序与ZooKeeper⼀同⼯作时会如此运⾏。如果你打算运⾏ZooKeeper，该视⾓对你会⾮常有⽤，同时本章也是下⼀章的背景知识。
我们在前⼏章中已经了解，ZooKeeper运⾏于⼀个集群环境中，客户端会连接到这些服务器执⾏操作请求，但究竟这些服务器对客户端所发送的请求操作做了哪些⼯作？我们在第2章中已经提到了，我们选择某⼀个服务器，称之为群⾸（leader）。其他服务器追随群⾸，被称为追随者（follower）。群⾸作为中⼼点处理所有对ZooKeeper系统变更的请求，它就像⼀个定序器，建⽴了所有对ZooKeeper状态的更新的顺序，追随者接收群⾸所发出更新操作请求，并对这些请求进⾏处理，以此来保障状态更新操作不会发⽣碰撞。
群⾸和追随者组成了保障状态变化有序的核⼼实体，同时还存在第三类服务器，称为观察者（observer）。观察者不会参与决策哪些请求可被接受的过程，只是观察决策的结果，观察者的设计只是为了系统的可扩展性。
本章中，我们还会介绍我们⽤于实现ZooKeeper集群和服务器与客户端内部通信所使⽤的协议。我们⾸先以客户端的请求和事务的这些常见概念展开讨论，这些概念将贯穿本章后续部分。
请求、事务和标识符
ZooKeeper服务器会在本地处理只读请求（exists、getData和getChildren）。假如⼀个服务器接收到客户端的getData请求，服务器读取该状态信息，并将这些信息返回给客户端。因为服务器会在本地处理请求，所以ZooKeeper在处理以只读请求为主要负载时，性能会很⾼。我们还可以增加更多的服务器到ZooKeeper集群中，这样就可以处理更多的读请求，⼤幅提⾼整体处理能⼒。
那些会改变ZooKeeper状态的客户端请求（create、delete和setData）将会被转发给群⾸，群⾸执⾏相应的请求，并形成状态的更新，我们称为事务（transaction）。其中，请求表⽰源⾃于客户端发起的操作，⽽事务则包含了对应请求处理⽽改变ZooKeeper状态所需要执⾏的步骤。我们通过⼀个简单点的例⼦，⽽不是ZooKeeper的操作，来说明这个问题。假如，操作为inc（i），该⽅法对变量i的值进⾏增量操作，如果此时⼀个请求为inc（i），假如i的值为10，该操作执⾏后，其值为11。再回过头看请求和事务的概念，其中inc（i）为请求，⽽事务则为变量i和11（变量i保存了11这个值）。
现在我们再来看看ZooKeeper的例⼦，假如⼀个客户端提交了⼀个对/z节点的setData请求，setData将会改变该znode节点数据信息，并会增加该节点的版本号，因此，对于这个请求的事务包括了两个重要字段：节点中新的数据字段值和该节点新的版本号。当处理该事务时，服务端将会⽤事务中的数据信息来替换/z节点中原来的数据信息，并会⽤事务中的版本号更新该节点，⽽不是增加版本号的值。
⼀个事务为⼀个单位，也就是说所有的变更处理需要以原⼦⽅式执⾏。以setData的操作为例，变更节点的数据信息，但并不改变版本号将会导致错误的发⽣，因此，ZooKeeper集群以事务⽅式运⾏，并确保所有的变更操作以原⼦⽅式被执⾏，同时不会被其他事务所⼲扰。在ZooKeeper中，并不存在传统的关系数据库中所涉及的回滚机制，⽽是确保事务的每⼀步操作都互不⼲扰。在很长的⼀段时间⾥，ZooKeeper所采⽤的设计⽅式为，在每个服务器中启动⼀个单独的线程来处理事务，通过单独的线程来保障事务之间的顺序执⾏互不⼲扰。最近，ZooKeeper增加了多线程的⽀持，以便提⾼事务处理的速度。
同时⼀个事务还具有幂等性，也就是说，我们可以对同⼀个事务执⾏两次，我们得到的结果还是⼀样的，我们甚⾄还可以对多个事务执⾏多次，同样也会得到⼀样的结果，前提是我们确保多个事务的执⾏顺序每次都是⼀样的。事务的幂等性可以让我们在进⾏恢复处理时更加简单。
当群⾸产⽣了⼀个事务，就会为该事务分配⼀个标识符，我们称之为ZooKeeper会话ID（zxid），通过Zxid对事务进⾏标识，就可以按照群⾸所指定的顺序在各个服务器中按序执⾏。服务器之间在进⾏新的群⾸选举时也会交换zxid信息，这样就可以知道哪个⽆故障服务器接收了更多的事务，并可以同步他们之间的状态信息。
zxid为⼀个long型（64位）整数，分为两部分：时间戳（epoch）部分和计数器（counter）部分。每个部分为32位，在我们讨论zab协议时，我们就会发现时间戳（epoch）和计数器（counter）的具体作⽤，我们通过该协议来⼴播各个服务器的状态变更信息。
群⾸选举
群⾸为集群中的服务器选择出来的⼀个服务器，并会⼀直被集群所认可。设置群⾸的⽬的是为了对客户端所发起的ZooKeeper状态变更请求进⾏排序，包括：create、setData和delete操作。群⾸将每⼀个请求转换为⼀个事务，如前⼀节中所介绍，将这些事务发送给追随者，确保集群按照群⾸确定的顺序接受并处理这些事务。
为了了解管理权的原理，⼀个服务器必须被仲裁的法定数量的服务器所认可。在第2章中我们已经讨论过，法定数量必须集群数量是能够交错在⼀起，以避免我们所说的脑裂问题（split brain）：即两个集合的服务器分别独⽴的运⾏，形成了两个集群。这种情况将导致整个系统状态的不⼀致性，最终客户端也将根据其连接的服务器⽽获得不同的结果，在2.3.3节我们已经通过具体例⼦说明了这⼀情况。
选举并⽀持⼀个群⾸的集群服务器数量必须⾄少存在⼀个服务器进程的交叉，我们使⽤属于仲裁（quorum）来表⽰这样⼀个进程的⼦集，仲裁模式要求服务器之间两两相交。
- 注意：进展
⼀组服务器达到仲裁法定数量是必需条件，如果⾜够多的服务器永久性地退出，⽆法达到仲裁法定数量，ZooKeeper也就⽆法取得进展。即使服务器退出后再次启动也可以，但必须保证仲裁的法定数量的服务器最终运⾏起来。我们先不讨论这个问题，⽽在下⼀章中再讨论重新配置集群，重新配置可以随时间⽽改变仲裁法定数量。
每个服务器启动后进⼊LOOKING状态，开始选举⼀个新的群⾸或查找已经存在的群⾸，如果群⾸已经存在，其他服务器就会通知这个新启动的服务器，告知哪个服务器是群⾸，与此同时，新的服务器会与群⾸建⽴连接，以确保⾃⼰的状态与群⾸⼀致。
如果集群中所有的服务器均处于LOOKING状态，这些服务器之间就会进⾏通信来选举⼀个群⾸，通过信息交换对群⾸选举达成共识的选择。
对于群⾸选举的消息，我们称之为群⾸选举通知消息（leader electionnotifications），或简单地称为通知（notifications）。该协议⾮常简单，当⼀个服务器进⼊LOOKING状态，就会发送向集群中每个服务器发送⼀个通知消息，该消息中包括该服务器的投票（vote）信息，投票中包含服务器标识符（sid）和最近执⾏的事务的zxid信息，⽐如，⼀个服务器所发送的投票信息为（1，5），表⽰该服务器的sid为1，最近执⾏的事务的zxid为5（出于群⾸选举的⽬的，zxid只有⼀个数字，⽽在其他协议中，zxid则有时间戳epoch和计数器组成）。
当⼀个服务器收到⼀个投票信息，该服务器将会根据以下规则修改⾃⼰的投票信息：
1.将接收的voteId和voteZxid作为⼀个标识符，并获取接收⽅当前的投票中的zxid，⽤myZxid和mySid表⽰接收⽅服务器⾃⼰的值。
2.如果（voteZxid>myZxid）或者（voteZxid=myZxid且voteId>mySid），保留当前的投票信息。
3.否则，修改⾃⼰的投票信息，将voteZxid赋值给myZxid，将voteId赋值给mySid。
简⽽⾔之，只有最新的服务器将赢得选举，因为其拥有最近⼀次的zxid。我们稍后会看到，这样做将会简化群⾸崩溃后重新仲裁的流程。如果多个服务器拥有最新的zxid值，其中的sid值最⼤的将赢得选举。
当⼀个服务器接收到仲裁数量的服务器发来的投票都⼀样时，就表⽰群⾸选举成功，如果被选举的群⾸为某个服务器⾃⼰，该服务器将会开始⾏使群⾸⾓⾊，否则就成为⼀个追随者并尝试连接被选举的群⾸服务器。
- 注意：查找群⾸
在ZooKeeper中对应的实现选举的Java类为QuorumPeer，其中的run⽅法实现了服务器的主要⼯作循环。当进⼊LOOKING状态，将会执⾏lookForLeader⽅法来进⾏群首的选举，该⽅法主要执⾏我们刚刚所讨论的协议，该⽅法返回前，在该⽅法中会将服务器状态设置为LEADING状态或FOLLOWING状态，当然还可能为OBSERVING状态，我们稍后讨论这个状态。如果服务器成为群首，就会创建⼀个Leader对象并运⾏这个对象，如果服务器为追随者，就会创建⼀个Follower对象并运⾏。
- 图9-1：群首选举过程的示例
并不是所有执⾏过程都如图9-1中所⽰，在图9-2中，我们展⽰了另⼀种情况的例⼦。服务器s2做出了错误判断，选举了另⼀个服务器s3⽽不是服务器s1，虽然s1的zxid值更⾼，但在从服务器s1向服务器s2传送消息时发⽣了⽹络故障导致长时间延迟，与此同时，服务器s2选择了服务器s3作为群⾸，最终，服务器s1和服务器s3组成了仲裁数量（quorum），并将忽略服务器s2。
- 图9-2：消息交错导致⼀个服务器选择了另⼀个群首
虽然服务器s2选择了另⼀个群⾸，但并未导致整个服务发⽣错误，因为服务器s3并不会以群⾸⾓⾊响应服务器s2的请求，最终服务器s2将会在等待被选择的群⾸s3的响应时⽽超时，并开始再次重试。再次尝试，意味着在这段时间内，服务器s2⽆法处理任何客户端的请求，这样做并不可取。
从这个例⼦，我们发现，如果让服务器s2在进⾏群⾸选举时多等待⼀会，它就能做出正确的判断。我们通过图9-3展⽰这种情况，我们很难确定服务器需要等待多长时间，在现在的实现中，默认的群⾸选举的实现类为FastLeaderElection，其中使⽤固定值200ms（常量finalizeWait），这个值⽐在当今数据中⼼所预计的长消息延迟（不到1毫秒到⼏毫秒的时间）要长得多，但与恢复时间相⽐还不够长。万⼀此类延迟（或任何其他延迟）时间并不是很长，⼀个或多个服务器最终将错误选举⼀个群⾸，从⽽导致该群⾸没有⾜够的追随者，那么服务器将不得不再次进⾏群⾸选举。错误地选举⼀个群⾸可能会导致整个恢复时间更长，因为服务器将会进⾏连接以及不必要的同步操作，并需要发送更多消息来进⾏另⼀轮的群⾸选举。
- 注意：快速群⾸选举的快速指的是什么？
如果你想知道为什么我们称当前默认的群首选举算法为快速算法，这个问题有历史原因。最初的群首选举算法的实现采用基于拉取式的模型，⼀个服务器拉取投票值的间隔⼤概为1秒，该⽅法增加了恢复的延迟时间，相比较现在的实现⽅式，我们可以更加快速地进⾏群首选举。
- 图9-3：群首选举时的长延迟
如果想实现⼀个新的群⾸选举的算法，我们需要实现⼀个quorum包中的Election接⼜。为了可以让⽤户⾃⼰选择群⾸选举的实现，代码中使⽤了简单的整数标识符（请查看代码中QuorumPeer.createElectionAlgorithm（）），另外两种可选的实现⽅式为LeaderElection类和AuthFastLeaderElection类，但在版本3.4.0中，这些类已经标记为弃⽤状态，因此，在未来的发布版本中，你可能不会再看到这些类。
Zab：状态更新的⼴播协议
在接收到⼀个写请求操作后，追随者会将请求转发给群⾸，群⾸将探索性地执⾏该请求，并将执⾏结果以事务的⽅式对状态更新进⾏⼴播。⼀个事务中包含服务器需要执⾏变更的确切操作，当事务提交时，服务器就会将这些变更反馈到数据树上，其中数据树为ZooKeeper⽤于保存状态信息的数据结构（请参考DataTree类）。
之后我们需要⾯对的问题便是服务器如何确认⼀个事务是否已经提交，由此引⼊了我们所采⽤的协议：Zab：ZooKeeper原⼦⼴播协议（ZooKeeper Atomic Broadcast protocol）。假设现在我们有⼀个活动的群⾸服务器，并拥有仲裁数量的追随者⽀持该群⾸的管理权，通过该协议提交⼀个事务⾮常简单，类似于⼀个两阶段提交。
1.群⾸向所有追随者发送⼀个PROPOSAL消息p。
2.当⼀个追随者接收到消息p后，会响应群⾸⼀个ACK消息，通知群⾸其已接受该提案（proposal）。
3.当收到仲裁数量的服务器发送的确认消息后（该仲裁数包括群⾸⾃⼰），群⾸就会发送消息通知追随者进⾏提交（COMMIT）操作。
图9-4说明了这⼀个过程的具体步骤顺序，我们假设群⾸通过隐式⽅式给⾃⼰发送消息。
- 图9-4：提交提案的常规消息模式
在应答提案消息之前，追随者还需要执⾏⼀些检查操作。追随者将会检查所发送的提案消息是否属于其所追随的群⾸，并确认群⾸所⼴播的提案消息和提交事务消失的顺序正确。
Zab保障了以下⼏个重要属性：
- 如果群首按顺序⼴播了事务T和事务T，那么每个服务器在提交T？事
务前保证事务T已经提交完成。
- 如果某个服务器按照事务T、事务T的顺序提交事务，所有其他服务
器也必然会在提交事务T前提交事务T。
第⼀个属性保证事务在服务器之间的传送顺序的⼀致，⽽第⼆个竖向地保证服务器不会跳过任何事务。假设事务为状态变更操作，每个状态变更操作又依赖前⼀个状态变更操作的结果，如果跳过事务就会导致结果的不⼀致性，⽽两阶段提交保证了事务的顺序。Zab在仲裁数量服务器中记录了事务，集群中仲裁数量的服务器需要在群⾸提交事务前对事务达成⼀致，⽽且追随者也会在硬盘中记录事务的确认信息。
我们在9.6节将会看到，事务在某些服务器上可能会终结，⽽其他服务器上却不会，因为在写⼊事务到存储中时，服务器也可能发⽣崩溃。⽆论何时，只要仲裁条件达成并选举了⼀个新的群⾸，ZooKeeper都可以将所有服务器的状态更新到最新。
但是，ZooKeeper⾃始⾄终并不总是有⼀个活动的群⾸，因为群⾸服务器也可能崩溃，或短时间地失去连接，此时，其他服务器需要选举⼀个新的群⾸以保证系统整体仍然可⽤。其中时间戳（epoch）的概念代表了管理权随时间的变化情况，⼀个时间戳表⽰了某个服务器⾏使管理权的这段时间，在⼀个时间戳内，群⾸会⼴播提案消息，并根据计数器（counter）识别每⼀个消息。我们知道zxid的第⼀个元素为时间戳信息，因此每个zxid可以很容易地与事务被创建时间戳相关联。
时间戳的值在每次新群⾸选举发⽣的时候便会增加。同⼀个服务器成为群⾸后可能持有不同的时间戳信息，但从协议的⾓度出发，⼀个服务器⾏使管理权时，如果持有不同的时间戳，该服务器就会被认为是不同的群⾸。如果服务器s成为群⾸并且持有的时间戳为4，⽽当前已经建⽴的群⾸的时间戳为6，集群中的追随者会追随时间戳为6的群⾸s，处理群⾸在时间戳6之后的消息。当然，追随者在恢复阶段也会接收时间戳4到时间戳6之间的提案消息，之后才会开始处理时间戳为6之后的消息，⽽实际上这些提案消息是以时间戳6的消息来发送的。
在仲裁模式下，记录已接收的提案消息⾮常关键，这样可以确保所有的服务器最终提交了被某个或多个服务已经提交完成的事务，即使群⾸在此时发⽣了故障。完美检测群⾸（或任何服务器）是否发⽣故障是⾮常困难的，虽然不是不可能，但在很多设置的情况下，都可能发⽣对⼀个群⾸是否发⽣故障的错误判断。
实现这个⼴播协议所遇到最多的困难在于群⾸并发存在情况的出现，这种情况并不⼀定是脑裂场景。多个并发的群⾸可能会导致服务器提交事务的顺序发⽣错误，或者直接跳过了某些事务。为了阻⽌系统中同时出现两个服务器⾃认为⾃⼰是群⾸的情况是⾮常困难的，时间问题或消息丢失都可能导致这种情况，因此⼴播协议并不能基于以上假设。为了解决这个问题，Zab协议提供了以下保障：
- ⼀个被选举的群首确保在提交完所有之前的时间戳内需要提交的事
务，之后才开始⼴播新的事务。
- 在任何时间点，都不会出现两个被仲裁支持的群首。
为了实现第⼀个需求，群⾸并不会马上处于活动状态，直到确保仲裁数量的服务器认可这个群⾸新的时间戳值。⼀个时间戳的最初状态必须包含所有的之前已经提交的事务，或者某些已经被其他服务器接受，但尚未提交完成的事务。这⼀点⾮常重要，在群⾸进⾏时间戳e的任何新的提案前，必须保证⾃时间戳开始值到时间戳e－1内的所有提案被提交。如果⼀个提案消息处于时间戳 `e' acl;
boolean ephemeral;
int parentCVersion;
}
...
}
这个例⼦定义模块，该模块包括⼀个create事务的定义。同时。这个模块映射到了⼀个ZooKeeper的包中。
# ⼩结
本章讨论了ZooKeeper核⼼机制问题。群⾸竞选机制是可⽤性的关键因素，没有这个机制，ZooKeeper套件将⽆法保持可靠性。拥有群⾸是必要但⾮充分条件，ZooKeeper还需要Zab协议来传播状态的更新等，即使某些服务器可能发⽣崩溃，也能保证状态的⼀致性。
我们又回顾了多种服务器类型：独⽴服务器、群⾸服务器、追随者服务器和观察者服务器。这些服务器之间因运转的机制及执⾏的协议的不同⽽不同。在不同的部署场景中，各个服务器可以发挥不同的作⽤，⽐如增加观察者服务器可以提供更⾼的读吞吐量，⽽且还不会影响写吞吐量。不过，增加观察者服务器并不会增加整个系统的⾼可⽤性。
在ZooKeeper内部，我们实现了⼀系列机制和数据结构。我们在本章中专注于会话与监视点的实现，这个也是在实现ZooKeeper应⽤时所涉及的重要概念。
虽然我们在本章中提供了代码的相关线索，但我们并没有提供源代码的详尽视图。我们强烈建议读者⾃⾏下载⼀份源代码，以本章所提供的线索为开端，独⽴分析和思考。
# 参考资料
《Zookeeper分布式过程协同技术详解》