前章提要:
主要从理论上讲解了Paxos算法,如何在保证数据一致性的情况下兼顾稳定性和性能也是一个巨大的挑战。从本章开始,我们将结合实际工程实际中的Paxos实现, 来讲解如何真正地使用Paxos算法来解决分布式一致性问题。

1. Chubby

Google Chubby是一个大名鼎鼎的分布式锁服务,GFS和Big Table等大型系统多用它来解决分布式协作、元数据存储和Master选举等一系列与分布式锁服务相关的问题。 Chubby的底层一致性实现就是以Paxos算法为基础的,这给Paxos算法的学习者提供了一个理论联系的范例,从而可以了解到Paxos算法是如何在实际工程中得到应用的。

1.1 概述

Chubby是一个面向松耦合分布式系统的锁服务,通常用于为一个由大量小型计算机构成的松耦合分布式系统提供高可用的分布式锁服务。一个分布式锁服务的目的是 允许它的客户端进程同步彼此的操作,并对当前所处环境的基本状态信息达成一致。针对这个目的,Chubby提供了粗粒度的分布式锁服务,开发人员不需要使用复杂的同步协议。 而是直接调用Chubby的锁服务接口即可实现分布式系统中多个进程之间粗粒度的同步控制,从而保证分布式数据的一致性。

Chubby的客户端接口设计非常类似于UNIX文件系统结构,应用程序通过Chubby的客户端接口,不仅能够对Chubby服务器上的整个文件进行读写操作,还能够添加对文件节点的锁控制, 并且能够订阅Chubby服务端发出的一些列文件变动的事件通知。

1.2 应用场景

在Chubby的众多应用场景中,最为典型的就是集群中服务器的Master选举。例如在Google文件系统(Google File System,GFS)中使用Chubby锁服务来实现对 GFS Master服务器的选举。而在BigTable(用于结构化数据存储与管理的大型分布式存储系统)中,同样被用于Master选举,并且借助Chubby, Master能够非常方便地的感知到其所控制的那些服务器。同时,通过Chubby,BigTable的哭护短还能够方便地定位到当前BitTable集群的Master服务器。 此外,在GFS和BigTable中,都使用Chubby来进行系统运行时元数据的存储。

1.3 设计目标

对于Chubby的设计,有的开发人员觉得作为Paxos算法的实现者,Chubby应该构建成一个包含Paxos算法的协议库,从而使应用程序能够便捷地使用Paxos算法。 但是,Chubby的最初设计者并没有选择这么做,而是将Chubby设计成一个需要访问中心化节点的分布式锁服务。

Chubby之所以设计成这样一个完整的分布式锁服务,是因为锁服务具有以下4个传统算法库所不具有的优点。

1. 对上层应用程序的侵入性更小

对于应用程序开发初期,开发人员都是从一个只需要支撑较小的负载,并且只需要保证大体可用的原型开始的,往往并没有在代码层面为分布式一致性协议的实现留有余地。 于是,集群中副本复制和Master选举等一系列提高分布式系统可用性的措施,就通过一个封装了分布式一致性协议的客户端来完成,但相比之下, 使用一个分布式锁服务的接口方式对上层应用程序的侵入性会更小。

2. 便于提供数据的发布与订阅

几乎在所有使用Chubby进行Master选举的应用场景中,都需要一种广播结果的机制,用来向所有的客户端公布当前的Master服务器。这就意味着Chubby应该 允许其客户端在服务器上进行少量数据的存储与读取————也就是对小文件的读写操作。虽然这个特性也能够通过分布式命名服务来实现,但是根据实际的经验来看, 分布式锁服务本身也非常适合提供这个功能,这一方面能够大大减少客户端依赖的外部服务,另一方面,数据的发布与订阅功能和锁服务在分布式一致性特性上是想通的。

3. 开发人员对基于锁的接口更为熟悉

对于绝大部分的开发人员来说,Chubby为其提供了一套近乎和单机锁机制一致的分布式锁服务接口,比提供一个一致性协议的库来得更为友好。

4. 更便捷地构建更可靠的服务

通常一个分布式一致性算法都需要使用Quorum机制来进行数据项值的选定。Quorum机制是分布式系统中实现数据一致性的一个比较特殊的策略,它指的是在 一个由若干个机器组成的急群众,在一个数据项值的选定过程中,要求急群众存在过半的机器达成一致,因此Quorum机制也被称作“过半机制”。 在Chubby中通常使用5台服务器来组成一个集群单元,根据Quorum机制,只要整个急群众有3台服务器是正常运行的,那么整个集群就可以对外提供正常的服务。 相反的,如果仅提供一个分布式一致性协议的客户端库,那么这些高可用性的系统部署都将交给开发人员自己来处理,提高了成本。

因此,Chubby被设计成了一个需要访问中心化节点的分布式锁服务。同时,在Chubby的设计过程中,提出了以下几个设计目标。

  1. 提供一个完整的、独立的分布式锁服务,而非仅仅是一个一致性协议的客户端库:
    例如,对于Master选举同时将Master信息登记并广播的场景,应用程序只需要向Chubby请求一个锁,并且在获得锁之后向相应的锁文件写入Master信息即可, 其余的客户端就可以通过读取这个锁文件来获取Master信息。

  2. 提供粗粒度的锁服务
    Chubby锁服务针对的应用场景是客户端获得锁之后会进行长时间的持有(数小时或数天),而非用于短暂获取锁的场景。针对这种应用场景,当锁服务短暂失效时 (例如服务器宕机),Chubby需要保持所有锁的持有状态,以避免持有锁的客户端出现问题。这和细粒度锁的设计方式有很大的区别,细粒度锁通常设计为锁 服务一旦失效就释放所有锁,因为细粒度锁的持有时间很短,相比而言放弃锁带来的代价较小。

  3. 在提供锁服务的同时提供对小文件的读写功能
    Chubby提供对小文件的读写服务,以使得被选举出来的Master可以在不依赖额外服务的情况下,非常方便地向所有客户端发布自己的状态信息。具体的, 当一个客户端成功获取到一个Chubby文件锁而成为Master之后,就可以继续向这个文件里写入Master信息,其他客户端就可以通过读取这个文件得知当前的Master信息。

  4. 高可用、高可靠
    在Chubby的架构设计中,允许运维人员通过部署多台机器(一般是5台机器)来组成一个Chubby集群,从而保证集群的高可用,基于Paxos算法的实现, 只要保证在3台正常运行的机器,整个集群对外服务就能保持可用。

  5. 提供事件通知机制
    Chubby客户单需要实时地感知到Master的变化情况,当然这可以通过让客户端反复轮询来实现,但是在客户端规模不断增大的情况下,客户端主动轮询的实时性效果并不理想, 且对服务器性能和网络带宽压力都非常大。因此,Chubby需要由能力将服务端的数据变化情况(如文件内容变更)以事件的形式通知到所有订阅的客户端。

1.4 Chubby技术架构

1.4.1 系统结构

Chubby的整个系统结构主要由服务端和客户端两部分组成,客户端通过RPC调用与服务端进行通信

一个典型的Chubby集群,或称为Chubby cell,通常由5台服务器组成。这些副本服务器采用Paxos协议,通过投票的方式来选举产生一个获得过半投票的 服务器作为Master。一旦某台服务器成为了Master,Chubby就会保证在一段时期内不会再有其他服务器成为Master————这段时期称为Master租期(Master lease)。 在运行过程中,Master服务器会通过不断续租的方式来延长Master租期,而如果Master服务器出现故障,那么余下的服务器就会进行新一轮的Master选举, 最终产生新的Master服务器,开始新的Master租期。

集群中的每个服务器都维护着一份服务端数据库的副本,但在实际运行过程中,只有Master服务器才能对数据库进行写操作,而其它服务器都是使用Paxos协议从 Master服务器上同步数据库数据的更新。

现在,我们再来看下Chubby的客户端是如何定位到Master服务器的。Chubby客户端通过向记录有Chubby服务端机器列表的DNS来请求获取所有的Chubby服务器列表, 然后逐个发起请求询问该服务器是否是Master。在这个询问过程中,那些非Master的服务器,则会将当前Master所在的服务器标识反馈给客户端,这样 客户端就能够非常快速地定位到Master服务器了。

一旦客户端定位到Master服务器之后,只要该Master正常运行,那么客户端就会将所有的请求都发送到该Master服务器上。针对写请求,Chubby Master 会采用一致性协议将其广播给集群中所有的副本服务器,并且在过半的服务器接受了该写请求之后,再响应给客户端正确的应答。而对于读请求, 则不需要在集群内部进行广播处理,直接由Master服务器单独处理即可。

在Chubby运行过程中,服务器难免会发生故障。如果当前的Master服务器崩溃了,那么集群中的其他服务器会在Master租期到期后,重新开启新一轮的Master 选举。通常,进行一次Master选举大概需要花费几秒钟的时间。而如果是集群中任意一台非Master服务器崩溃,那么整个集群是不会停止工作的, 这个崩溃的服务器会在恢复之后自动加入到Chubby集群中去。新加入的服务器首先需要同步Chubby最新的数据库数据,完成数据同步之后,新的服务器就可以 加入到正常的Paxos运作流程中与其它服务器副本一起协同工作。

如果集群中的一个服务器发生崩溃并在几个小时后仍无法恢复正常,那么就需要加入新的机器,并同时更新DNS列表。Chubby服务器的更换方式非常简单, 只需要启动Chubby服务端程序,然后更新DNS上的机器列表(即使用新机器的IP地址替换老机器的IP地址)即可。在Chubby运行过程中, Master服务器会周期性地轮询DNS列表因此其很快就会感知服务器地址列表的变更,然后Master就会将集群数据库中的地址列表做相应的变更, 集群内部的其他副本服务器通过复制方式就可以获取到最新的服务器地址列表了。

1.4.2 目录与文件

Chubby对外提供了一套与Unix文件系统非常相近但是更简单的访问接口。Chubby的数据结构可以看作是一个由文件和目录组成的树,其中每一个节点都可以表示为一个 使用斜杠分割的字符串,典型的节点路径表示如下:

/ls/foo/wombat/pouch
其中,ls是所有Chubby节点所共有的前缀,代表着锁服务,是Lock Service的缩写;foo则指定了Chubby集群的名字,从DNS可以查询到由一个或多个 服务器组成该Chubby集群;剩余部分的路径wombat/pouch则是一个真正包含业务含义的节点名字,由Chubby服务器内部解析并定位到数据节点。

Chubby的命名空间,包括文件和目录,我们称之为节点(nodes,在本书后面的内容中,我们以数据节点来泛指Chubby的文件或目录)。在同一个Chubby 集群数据库中,每一个节点都是全局唯一的。和Unix系统一样,每个目录都可以包含一系列的子文件和子目录列表,而每个文件中则会包含文件内容。当然, Chubby并非模拟一个完整的文件系统,因此没有符号链接和硬连接的概念。

由于Chubby的命名结构组成了一个近似标准文件系统的视图,因此Chubby的客户端应用程序也可以通过自定义的文件系统访问接口来访问Chubby服务端数据, 比如可以使用GFS的文件系统访问接口,这就大大减少了用户使用Chubby的成本。

Chubby上的每个数据节点都分为持久节点和临时节点两大类,其中持久节点需要显式地调用接口API来进行删除,而临时节点则会在其对应的客户端会话失效后被自动删除。 (zk中的EPHEMERAL)也就是说,临时节点的生命周期和客户端会话绑定,如果该临时节点对应的文件没有被任何客户端打开的话,那么它就会被删除掉。 因此,临时节点通常可以用来进行客户端会话有效性的判断依据。

另外,Chubby上的每个数据节点都包含了少量的元数据信息,其中包括用于权限控制的访问控制列表(ACL)信息。同时,每个节点的元数据中还包括4个单调 递增的64编号,分别如下。

实例编号:实例编号用于标识Chubby创建该数据节点的顺序,节点的创建顺序不同,其实例编号也不同,因此,通过实例编号,即使针对两个名字相同的数据节点, 客户端也能够非常方便地识别出是否是同一个数据节点————因此创建时间晚的数据节点,其实例编号必定大于任意先前创建的同名节点。
文件内容编号(只针对文件):文件内容编号用于标识文件内容的变化情况,该编号会在文件内容被写入时增加。
锁编号:锁编号用于标识节点锁状态变更情况,该编号会在节点锁从自由(free)状态转换到被持有(held)状态时增加。
ACL编号:ACL编号用于标识节点的ACL信息变更情况,该编号会在节点的ACL配置信息被写入时增加。
同时,Chubby还会标识一个64位的文件内容校验码,以便客户端能够识别出文件是否变更。

1.4.3 锁与锁序列器

在分布式系统中,锁是一个非常复杂的问题,由于网络通信的不确定性,导致在分布式系统中锁机制变得非常复杂,消息的延迟或是乱序都有可能会引起锁的失效。 一个典型的分布式锁错乱案例是,一个客户端C1获取到了互斥锁L,并且在锁L的保护下发出请求R,但请求R迟迟没有到达服务端(可能出现网络延时或 反复重发等),这时应用程序会认为该客户端进程已经失败,于是便会为另一个客户端C2分配锁L,然后再重新发起之前的请求R,并成功地应用到了服务器 上。此时,不幸的事情发生了,客户端C1发起的请求R在经过一波三折之后也到达了服务端,此时,它有可能会在不受任何锁控制的情况下被服务端处理, 从而覆盖了客户端C2的操作,于是导致系统数据出现不一致。当然,诸如此类消息接收顺序紊乱引起的数据不一致问题已经在人们对分布式计算的长期 研究过程中得到了很好的解决,典型的解决方案包括虚拟时间和虚拟同步。

在Chubby中,任意一个数据节点都可以充当一个读写锁来使用:一种是单个客户端以排他(写)模式持有这个锁,另一种则是任意数目的客户端以共享(读)模式 持有这个锁。同时,在Chubby的锁机制中需要注意的一点是,Chubby舍弃了严格的强制锁,客户端可以在没有获取任何锁的情况下访问Chubby的文件,也就是说, 持有锁F既不是访问文件F的必要条件,也不会阻止其它客户端访问文件F。

.1 锁延迟

在Chubby中,主要采用锁延迟和锁序列器两种策略来解决上面我们提到的由于消息延迟和重排序引起的分布式锁问题。其中锁延迟是一种比较简单的策略, 使用Chubby的应用几乎不需要进行任何的代码修改。具体的,如果一个客户端以正常的方式主动释放了一个锁,那么Chubby服务端将会允许其它客户端能够 立即获得该锁。而如果一个锁是因为客户端的异常情况(如客户端无响应)而被释放的话,那么Chubby服务器会为该锁保留一定的时间,我们称之为“锁延迟”(lock-delay) 在这段时间内,其它客户端无法获取这个锁。锁延迟措施能够很好地防止一些客户端由于网络闪断等原因而与服务器暂时断开的场景出现。总的来说, 该方案尽管不完美,但是锁延时能够有效地保护在出现消息延时情况下发生的数据不一致现象。

.2 锁序列器

Chubby提供的另一种方式是使用锁序列器,当然该策略需要Chubby的上层应用配合在代码中加入相应的修改逻辑。任何时候,锁的持有者都可以向Chubby请求一个锁 序列器,其包括锁的名字、锁模式(排他或共享模式),以及锁序号。当客户端应用程序在进行一些需要锁机制保护的操作时,可以将该锁序列器一并发送给服务端。 Chubby服务端接收到这样的请求后,会首先检测该序列器是否有效,以及检查客户端是否处于恰当的锁模式;如果没有通过检查,那么服务端就会拒绝该客户端请求。

1.4.4 Chubby中的事件通知机制

为了避免大量客户端轮询Chubby服务端状态所带来的压力,Chubby提供了事件通知机制。Chubby的客户端可以向服务端注册事件通知,当触发这些事件的时候, 服务端就会向客户端发送对应的事件通知。在Chubby的事件通知机制中,消息通知都是通过异步的方式发送给客户端的,常见的Chubby事件如下。

.1 文件内容变更

例如,BigTable集群使用Chubby锁来确定集群中的哪台BitTable机器是Master;获得锁的BitTable Master会将自身信息写入Chubby上对应的文件中。 BitTable集群中的其他客户端可以通过监视这个Chubby文件的变化来确定新的BitTable Master机器。

.2 节点删除

当Chubby上指定节点被删除的时候,会产生“节点删除”事件,这通常在临时节点中比较常见,可以利用该特性来间接判断该临时节点对应的客户端会话是否有效。

.3 子节点新增、删除

当Chubby上指定的节点的子节点新增或是删除时,会产生“子节点新增、删除”事件。(还有更新)

.4 Master服务器转移

当Chubby服务器发生Master转移时,会以事件的形式通知客户端。

1.4.5 Chubby中的缓存

为了提高Chubby的性能,同时也是为了减少客户端和服务端之间频繁的读请求对服务端的压力,Chubby除了提供事件通知机制之外,还在客户端中实现了缓存, 会在客户端对文件内容和元数据信息进行缓存。使用缓存机制在提高系统整体性能的同时,也为系统带来了一定的复杂性,其中最主要的问题就是应该如何保证缓存的一致性。 在Chubby中,通过租期机制来保证缓存的一致性。

Chubby缓存的生命周期和Master租期机制紧密相关,Master会维护每个客户端的数据缓存情况,并通过向客户端发送过期信息的方式来保证客户端数据的一致性。 在这种机制下,Chubby就能够保证客户端要么能够从缓存中访问到一致的数据,要么访问出错,而一定不会访问到不一致的数据。具体的,每个客户端的缓存 都有一个租期,一旦该租期到期,客户端就需要向服务端续订租期以继续维持缓存的有效性。当文件数据或元数据被修改时,Chubby服务端首先会阻塞该修改操作, 然后由Master向所有可能缓存了该数据的客户端发送缓存过期信号,以使其缓存失效,等到Master在接收到所有相关客户端针对该过期信息的应答(应答包括两类, 一类是客户端明确要求更新缓存,另一类则是客户端允许缓存租期过期)后,再继续进行之前的修改操作。

通过上面这个缓存机制的介绍,相信读者都已经明白了,Chubby的缓存数据保证了强一致性。尽管要保证严格的数据一致性对于性能的开销和系统的吞吐影响很大, 但由于弱一致性模式在实际使用过程中极容易出现问题,因此Chubby在设计之初就决定了强一致性模型。

1.4.6 会话和会话激活(KeepAlive)

Chubby客户端和服务端之间通过创建一个TCP连接来进行所有的网络通信操作,我们将这一连接称为会话(Session)。会话是有生命周期的,存在一个超时时间, 在超时时间内,Chubby客户端和服务端之间可以通过心跳检测来保持会话的活性,以使会话周期得到延续,我们将这个过程称为KeepAlive(会话激活)。如果 能够成功地通过KeepAlive过程将Chubby会话一直延续下去,那么客户端创建的句柄(引用)、锁和缓存数据等都依然有效。

1.4.7 KeepAlive请求

下面我们就重点来看看Chubby Master是如何处理客户端的KeepAlive请求的。Master在接收到客户端的KeepAlive请求时,首先会将该请求阻塞住,并等到 该客户端的当前会话租期即将过期时,才为其续租该客户端的会话租期,之后再向客户端响应这个KeepAlive请求,并同时将最新的会话租期超时时间反馈给客户端。 Master对于会话续租时间的设置,默认是12秒,但这不是一个固定的值,Chubby会根据实际的运行情况,自行调节该周期的长短。举个例子来说, 如果当前Master处于高负载运行状态的话,那么Master会适当地延长会话租期的长度,以减少客户端KeepAlive请求的发送频率。客户端在接收到来自Master的续租 响应后,会立即发起一个新的KeepAlive请求,再由Master进行阻塞。因此我们可以看出,在正常运行过程中,每一个Chubby客户端总是会有一个KeepAlive 请求阻塞在Master服务器上。

除了为客户端进行会话续租外,Master还将通过KeepAlive响应来传递Chubby事件通知和缓存过期通知给客户端。具体的,如果Master发现服务端已经触发了 针对该客户端的事件通知或缓存过期通知,那么会提前将KeepAlive响应反馈给客户端。

1.4.8 会话超时

谈到会话租期,Chubby的客户端也会维持一个和Master端近似相同的会话租期。为什么是近似相同呢?这是因为客户端必须考虑两方面的因素:一方面,KeepAlive 响应在网络传输过程中会花费一定的时间;另一方面,Master服务端和Chubby客户端存在时钟不一致性现象。因此在Chubby会话中,存在Master端会话租期和客户端本地 会话租期。

如果Chubby客户端在运行过程中,按照本地的会话租期超时时间,检测到期会话租期已经过期却尚未接收到Master的KeepAlive响应,那么这个时候,它将无法确定Master 服务端是否已经中止了当前会话,我们称这个时候客户端处于“危险状态”。此时,Chubby客户端会清空其本地缓存,并将其标记为不可用。同时,客户端还会等待一个被 称作“宽限期”的时间周期,这个宽限期默认是45秒。如果在宽限期到期前,客户端和服务端成功地进行了KeepAlive,那么客户端就会再次开启本地缓存,否则,客户端就会 认为当前会话已经过期了,从而中止本次会话。

我们再着重来看看上面提到的“危险状态”。当客户端进入上述提到的危险状态时,Chubby的客户端库会通过一个“jeopardy”事件来通知上层应用程序。如果 恢复正常,客户端同样会以一个“safe”事件来通知应用程序可以继续正常运行了。但如果客户端最终没能从危险状态中恢复过来,那么客户端会以一个“expired” 事件来通知应用程序当前Chubby会话已经超时。Chubby通过这些不同的事件类型通知,能够很好地辅助上层应用程序在不明确Chubby会话状态的情况下, 根据不同的事件类型来做出不同的处理:等待或重启。有了这样的机制保证之后,对于那些在短时间内Chubby服务不可用的场景下,客户端应用程序可以选择等待,而不是重启, 这对于那些重启整个应用程序需要花费较大代价的系统来说非常有帮助。

1.4.9 Chubby Master故障恢复

Chubby的Master服务器上运行着会话租期计时器,用来管理所有会话的生命周期。如果在运行过程中Master出现了故障,那么该计时器会停止,直到新的Master选举 产生后,计时器才会继续计时,也就是说,从旧的Master崩溃到新的Master选举产生所花费的时间将不计入会话超时的计算中,这等价于延长了客户端的会话租期。 如果新的Master在短时间内就选举产生了,那么客户端就可以在本地会话租期过期前与其创建连接。而如果Master的选举花费了较长的时间,就会导致客户端只能情况本地的缓存, 并进入宽限期进行等待。从这里我们可以看出,由于宽限期的存在,使得会话能够很好地在服务端Master转换额过程中得到维持。整个Chubby Master故障恢复过程中 服务端和客户端的交互情况:

展示了一个完整的Chubby服务端Master故障恢复过程中所触发的所有事件序列。在这整个故障恢复过程中,客户端必须使用宽限期来保证在Master转换过程完成之后, 其会话依然有效。

一开始在旧的Master服务器上维持了会话租期“lease M1”,在客户端上维持了对应的“lease C1”,同时客户端的KeepAlive请求1一直被Master阻塞着。在一段时间之后, Master向客户端反馈了KeepAlive响应2,同时开始了新的会话租期“lease M2”,而客户端在接收到该KeepAlive响应之后,立即发送了新的KeepAlive请求3,并 同时也开始了新的会话租期“lease C2”。至此,客户端和服务吨Master之间的所有交互都是正常的。但是随后,Master发生了故障,从而无法反馈客户端的KeepAlive 请求3。在这个过程中,客户端检测到会话租期“lease C2”已经过期,它会清空本地缓存,并进入宽限期。在这顿时间内,客户端无法确定Master上的会话周期 是否也已经过期,因此,它不会销毁它的本地会话,而是将所有应用程序对它的API调用都阻塞主,以避免在这个期间进行的API调用导致数据不一致现象。 同时,在客户端宽限期开始时,Chubby客户端会向上层应用程序发送一个“jeopardy”事件。一段时间后,CHubby服务端选举产生了新的Master,并为该客户端初始化 了新的会话租期“lease M3”。当客户端向新的Master发送KeepAlive请求4时,Master检测到该客户端的Master周期号已经过期,因此会在KeepAlive响应5 中拒绝这个客户端请求,并将最新的Master周期号发送给客户端。之后,客户端会携带上新的Master周期号,再次发送KeepAlive请求6给Master,最终,整个 客户端和服务端之间的会话就会再次恢复正常。

通过上面的详细介绍,不难看出,在Master转换的这段时间内,只要客户端的宽限期是够长的,那么客户端应用程序可以在没有任何察觉的情况下,实现Chubby的故障恢复, 但如果客户端的宽限期设置得比较短,那么Chubby客户端就会丢弃当前会话,并将这个异常情况通知给上层应用程序。

一旦客户端与新的Master建立上连接之后,客户端和Master之间会通过互相配合来实现对故障的平滑恢复。新的Master会设法将上一个Master服务器的内存状态构造出来。 具体的,由于本地数据库记录了每个客户端的会话信息,以及其持有的锁和临时文件等信息,因此Chubby会通过读取本地磁盘上的数据来恢复一部分状态。 总的来讲,一个新的Chubby Master服务器选举产之后,会进行如下几个主要处理。

.1 确定Master周期

Master周期用来唯一标识一个Chubby集群的Master统治轮次,以便区分不同的Master。一旦新的Master周期确定下来之后,Master就会拒绝所有携带其他Master 周期编号的客户端请求,同时告知其最新的Master周期编号,例如上述提到的KeepAlive请求4。需要注意的一点是,只要发生Master重新选举,就一定会产生新的 Master周期,即使是在选举前后Master都是同一台机器的情况下也是如此。

.2 新Master能够立即对客户端的Master寻址请求进行响应,但是不会立即开始处理客户端会话相关的请求操作。

.3 Master根据本地数据库中存储的会话和锁信息,来构建服务器的内存状态。

.4 到现在为止,Master已经能够处理客户端的KeepAlive请求了,但依然无法处理其他会话相关的操作。

.5 Master会发送一个“Master故障切换”事件给每一个会话。

客户端接收到这个事件后,会清空它的本地缓存,并警告上层应用程序可能已经丢失了别的事件,之后再向Master反馈应答。

.6 此时,Master会一直等待客户端的应答,知道每一个会话都应答了这个切换事件。

.7 在Master接收到了所有客户端的应答之后,就能够开始处理所有的请求操作了。

.8 如果客户端使用了一个在故障切换之前创建的引用,Master会重新为其创建这个引用的内存对象,并执行调用。

而如果该引用在之前的Master周期中已经被关闭了,那么它聚不能在这个Master周期内再次被重建了————这一机制就确保了即使由于网络原因使得Master接收到那些延迟或重发的网络数据包, 也不会错误地重建一个已经关闭的引用。

1.5 Paxos协议实现

Chubby服务端的基本架构大致分为三层:

最底层是容错日志系统(Fault-Tolerant Log),通过Paxos算法能够保证集群中所有机器上的日志完全一致,同时具有较好的容错性。
日志层之上是Key-value类型的容错数据库(Fault-Tolerant DB),其通过下层的日志来保证一致性和容错性。
存储层之上就是Chubby对外提供的分布式锁服务和小文件存储服务。

Paxos算法的作用就在于保证集群内各个副本节点的日志能够保持一致。Chubby事务日志中的每一个Value对应Paxos算法中的一个Instance,由于Chubby需要对外提供 不间断的服务,因此事务日志无限增长,于是在整个Chubby巡行过程中,会存在多个Paxos Instance。同时,Chubby会为每一个Paxos Instance都按序分配一个全局唯一 的Instance编号,并将其顺序写入到事务日志中去。
在多Paxos Instance的模式下,为了提升算法执行的性能,就必须选举出一个副本节点作为Paxos算法的主节点,以避免因为每一个Paxos Instance都提出提案而陷入多个Paxos Round 并存的情况。同时,Paxos会保证在Master重启或出现故障而进行切换的时候,允许出现短暂的多个Master共存却不影响副本之间的一致性。

在Paxos中,每一个Paxos Instance都需要进行一轮或多轮“Prepare->Promise->Propose->Accept”这样完整的二阶段请求过程来完成对一个提案值的选定, 而多个Instance之间是完全独立的,每个Instance可以自己决定每一个Round的序号,仅仅只需要保证在Instance内部不会出现序号重复即可。为了在保证正确性的前提下尽可能 地的提高算法运行性能,可以让多个Instance共用一套序号分配机制,并将“Prepare->Promise”合并为一个阶段,具体做法如下。

当某个副本节点通过选举成为Master后,就会使用新分配的编号N来广播一个Prepare消息,该Prepare消息会被所有未达成一致的Instance和目前还未开始的Instance共用。
当Acceptor接收到Prepare消息后,必须对多个Instance同时做出回应,这通常可以通过将反馈信息封装在一个数据包中来实现。假设最多允许K个Instance同时进行提案值的选定,那么:

当前至多存在K个未达成一致的Instance,将这些未决的Instance各自最后接收的提案值(若该提案尚未接收任何值。则使用null来代替)封装进一个数据包,并作为Promise消息返回。 同时,判断N是否大于当前Acceptor的highestPromisedNum值(当前已经接受的最大提案编号值),如果大于该值的话,那么就标记这些未决Instance和 所有未来的Instance的highestPromisedNum值为N————这样,这些未决Instance和所有未来Instance都不能再接受任何编号小于N的提案。

然后Master就可以对所有未决Instance和所有未来Instance分别执行“Propose->Accept”阶段的处理。值得注意的是,如果当前Master能够一直稳定运行的话, 那么在接下来的算法运行过程中,就不再需要进行“Prepare->Promise”的处理了。但是,一但Master发现Acceptor返回了一个Reject消息,说明集群中存在另一个Master, 并且试图使用更大的编号发送了Prepare消息。碰到这种情况,当前Master就需要重新分配新的提案编号,并再次进行“Prepare->Promise”阶段的逻辑处理。

利用上述改进的Paxos算法,在Master稳定运行的情况下,只需要使用同一个编号来依次执行每一个Instance的“Promise->Accept”阶段逻辑处理。在每个Instance 的运行过程中,一旦接收到多数派的Accept反馈后,就可以将对应的提案值写入本地事务日志并广播COMMIT消息给集群中的其他副本节点,其他副本节点在接收到这个COMMIT消息之后也会 将提案值写入到事务日志中。如果某个副本节点因为宕机或者网络原因没有接收到COMMIT消息,可以主动向集群中的其他副本节点进行查询。因此,我们可以看到,在Chubby的Paxos 算法的实现中,只要维持集群中存在多数派的机器能够正常运行,即使其他机器在任意时刻发生宕机,也能保证已经提交的提案的安全性。

至此,我们已经实现了一套满足一致性的日志副本,在此基础上就可以在上层实现一个一致的状态机副本,即容错数据库层。初期,使用Berkeley DB作为容错数据库, 这个数据库底层实现了B树数据结构,即存储大量数据的HashMap,将每一个数据节点的节点路径名作为键,同时按照节点路径名进行排序,这就能够使得兄弟节点在排序顺序中相邻, 方便对数据节点的检索。

后来,Chubby自己实现了一套更为简单的、基于日志预写和数据快照技术的底层数据复制组件。

数据快照和事务日志回放机制:集群中的某台机器在宕机重启以后,为了恢复状态机的状态,最简单的方法就是将已经记录的所有事务日志重新执行一遍。但这 会有一个明显的问题,就是如果机器上的事务日志已经积累了很多,那么恢复的时间就会非常长,因此需要定期对状态机数据做一个数据快照并将其存入磁盘, 然后就可以将数据快照点之前的事务日志清除。

通常副本节点在进行宕机后的恢复过程中,会出现磁盘未损坏和损坏两种情况。前者最为常见,一般通过磁盘上保存的数据库快照和事务日志就可以恢复到之前某个时间点的状态, 之后再向集群中其他正常运行的副本节点索取宕机后缺失的部分数据变更记录,这样即可实现宕机后的数据恢复。另外一种则是磁盘损坏,无法直接从本地数据恢复的情况, 需要从其它副本节点索取全部的状态数据。

副本节点在完成宕机重启之后,为了安全起见,不会立即参与Paxos Instance流程,而是需要等待检测到K个Paxos Instance流程陈宫完成之后才能开始参与————这样就能够保证 新分配的提案编号不会和自己以前发过的重复。

最后,为了提高整个集群的性能,还有一个改进之处在于:得益于Paxos算法的容错机制,只要任意时刻保证多数派的机器能够正常运行,那么在宕机瞬间未能真正写入到 磁盘上(只有当真正调用操作系统Flush接口后,数据才能被真正写入物理磁盘中)的那一小部分事务日志也可以通过从其它正常运行的副本上复制来进行获取,因此 不需要实时地进行事务日志的Flush操作,这可以极大地提高事务写入的效率。

1.6 Hypertable

1.6.1 概述

使用C++开发的开源、高性能、可伸缩的数据库。只支持增删改查,不支持事务。

支持对大量并发请求的处理。
支持对海量数据的管理。
扩展性良好,在保证可用性的前提下,能够通过随意添加集群中的机器来实现水平扩容。
可用性极高,具有非常好的容错性,任何节点的失效,既不会造成系统瘫痪也不会影响数据的完整性。

1.6.2 算法实现

选举Master是根据所有服务器上事务日志的更新时间来确定哪个服务器的数据最新,那么被选举的可能性就越大。

3 小结

列举了使用Paxos算法的工业实践应用,更好的理解Paxos算法。

前章提要:
上章我们讲到分布式往往会在系统可用性和数据一致性之间反复权衡,于是就产生了一系列的一致性协议(为什么没有可用性协议?博主认为,数据才是王道)。

1. 2PC和3PC

在分布式系统总,每一个机器节点虽然都能够明确地知道自己在进行事务操作过程中的结果是成功或失败,但却无法直接获取到其他分布式节点的操作结果。 因此,当一个事务操作需要跨越多个分布式节点的时候,为了保持事务处理的ACID特性(某个节点为单位),就需要引入一个称为“协调者(Coordinator)” 的组件来统一调度所有分布式节点的执行逻辑,这些被调度的分布式节点被称为“参与者(Participant)”。

Coordinator负责调度Participant的行为,并最终决定这些Participant是否要把事务真正的提交。基于这个思想,衍生除了二阶段提交和三阶段提交两种协议, 在本节中,我们将重点对这两种分布式事务中涉及的一致性协议进行讲解。

1.1 2PC

2PC是Two-Phase Commit的缩写,即二阶段提交,是计算机网络尤其是在数据库领域内,为了使基于分布式系统架构下的所有节点在进行事务处理过程中能保持 原子性和一致性而设计的算法。

1.1.1 阶段一:提交事务请求

事务询问:协调者向所有的参与者发送事务内容,询问是否可以执行事务提交曹组,并开始等待各参与者的响应。
执行事务:各参与者节点执行事务操作,并将Undo和Redo信息记入事务日志中。
各参与者向协调者反馈事务询问的响应:如果参与者成功执行了事务操作,那么反馈给协调者Yes响应,表示事务可以执行;如果参与者没有成功执行事务, 那么就反馈给协调者No响应,表示事务不可以执行。
由于上面讲述的内容在形式上近似是协调者组织各参与者对一次事务操作的投票表态过程,因此二阶段提交协议的阶段一页被称为“投票阶段”,即各参与者投票 表明是否要继续执行接下去的事务提交操作。

1.1.2 阶段二:执行事务提交

正常情况,包含以下两种可能:

.1 可能一:执行事务提交:假如协调者从所有的参与者的反馈都是Yes响应,那么就会执行事务提交。

.1.1 发送提交请求:协调者向所有参与者发出Commit请求。
.1.2 事务提交:参与者接收到Commit请求后,会正式执行事务提交操作,并在完成提交之后释放整个事务执行期间占用的事务资源。
.1.3 反馈事务提交结果:参与者在完成事务提交之后,向协调者发送Ack消息。
.1.4 完成事务:协调者接收到所有参与者反馈的Ack消息后,完成事务。

.2 可能二:执行事务中断:假如任何一个参与者向协调者反馈了No响应,或者在等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务。

.2.1 发送回滚请求:协调者向所有参与者节点发出Rollback请求。
.2.2 事务回滚:参与者接收到Rollback请求后,会利用其在阶段一记录的Undo信息来执行事务回滚操作,并在完成回滚之后释放在整个事务执行期间占用的资源。
.2.3 反馈事务回滚结果:参与者在完成事务回滚之后,向协调者发送Ack消息。
.2.4 中断事务:协调者接收到所有参与者反馈的Ack消息后,完成事务中断。

以上就是二阶段提交过程中,前后两个阶段分别进行的处理逻辑。简单地讲,二阶段提交将一个事务的处理分成了投票和执行两个阶段,其核心是对每个事务 都采用了先尝试后提交的处理方式,因此也可以将二阶段提交看作一个强一致性的算法。

1.1.3 优缺点

原理简单,实现方便;但是同步阻塞、单点问题、数据不一致、太过保守。

.1 同步阻塞:在事务的执行过程中,所有参与该事务操作的逻辑都处于阻塞状态,也就是说,各个参与者在登台其他参与者响应的过程中,

将无法进行其他任何操作。

.2 单点问题:一旦协调者出现问题,整个二阶段提交流程将无法运转,更为严重的是,如果协调者是在阶段二中出现问题的话,

那么其他参与者将会一直处于锁定事务资源的状态中,而无法继续完成事务操作。

.3 数据不一致:当协调者向所有参与者发送Commit请求之后,发生了协调者在尚未发送完Commit请求之前自身发生了崩溃,

导致最终只有部分参与者收到了Commit请求。于是,其他没有收到Commit请求的参与者没有进行事务提交,而收到Commit请求的参与者会进行事务提交,最终数据不一致。

.4 太过保守:任何一个节点的失败都会导致整个事务的失败。

1.2 3PC

研究者在二阶段提交协议的基础上进行了改进,提出了三阶段提交协议。
3PC是Three-Phase Commit的缩写,将二阶段提交协议的“提交事务请求”过程分为两个,形成了CanCommit、PreCommit和DoCommit。

1.2.1 阶段一:CanCommit

.1 事务询问:协调者向所有的参与者发送一个包含事务内容的CanCommit请求,询问是否可以执行事务提交操作,并开始等待各参与者的响应。

.2 各参与者向协调者反馈响应:如果自身可以顺序执行事务,反馈Yes响应,并进入预备状态,否则反馈No响应。

1.2.2 阶段二:PreCommit

.1 执行事务预提交:假如协调者从所有参与者获得的反馈都是Yes响应。

.1.1 发送预提交请求:协调者向所有参与者节点发出PreCommit的请求,并进入Prepared阶段。
.1.2 事务预提交:参与者接收到PreCommit请求后,会执行事务操作,并将Undo和Redo信息记录到事务日志中。
.1.3 各参与者向协调者反馈事务执行的响应:如果参与者成功执行了事务操作,那么就会反馈给协调者Ack响应,同时等待最终的指令:提交(commit)或中止(abort)。

.2 中断事务:假如任何一个参与者向协调者反馈了No响应,或等待超时之后,协调者尚无法接收到所有参与者的反馈响应,那么就会中断事务。

.2.1 发送中断请求:协调者向所有参与者节点发出abort请求。
.2.2 中断事务:无论是收到来自协调者的abort请求,或者是在等待协调者请求过程中出现超时时,参与者都会中断事务。

1.2.3 阶段三:DoCommit

.1 可能一:执行提交

.1.1 发送提交请求:协调者从“预提交”状态转换到“提交”状态,并向所有的参与者发送DoCommit请求。
.1.2 事务提交:参与者接收到DoCommit请求后,会正式执行事务提交操作,并在完成提交之后释放在整个事务执行期间占用的事务资源。
.1.3 反馈事务提交结果:参与者在完成事务提交之后,向协调者发送Ack消息。
.1.4 完成事务:协调者接收到所有参与者反馈的Ack消息后,完成事务。

.2 可能二:中断事务

.2.1 发送中断请求:协调者向所有参与者节点发送abort请求。
.2.2 事务回滚:参与者接收到abort请求后,利用Undo信息来执行事务回滚操作,并在完成回滚之后释放在整个事务执行期间占用的资源。

#####.2.3 反馈事务回滚结果:参与者在完成事务回滚之后,向协调者发送Ack消息。

#####.2.4 中断事务:协调者接收到所有参与者反馈的Ack消息后,中断事务。

需要注意的是,一旦进入阶段三,可能会存在以下两种故障:

协调者出现问题。
协调者和参与者之间的网络出现故障。 无论出现哪种情况,参与者都会在等待超时之后,继续进行事务提交。即,默认为允许提交。

1.2.3 优缺点

降低参与者的阻塞范围,出现单点故障后继续达成一致;但是在参与者接收到PreCommit消息后,如果协调者所在的节点和参与者无法正常通信, 该参与者仍然会进行事务的提交,这必然出现数据不一致性。

2. Paxos算法

我们将重点讲解另一种非常重要的分布式一致性协议:Paxos。Paxos算法是一种基于消息传递且具有高度容错特性的一致性算法,是目前公认的解决分布式 一致性问题最有效的算法之一。

我们现在已经知道,在常见的分布式系统中,总会发生诸如机器宕机或网络异常等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中, 快速且正确地在集群内部对某个数据的值达成一致,并且保证不论发生以上任何异常都不会破坏整个系统的一致性。

2.1 追本溯源

1982年,Lamport与另两人提出了一种计算容错理论。在理论描述过程中,为了将要所描述的问题形象的表达出来,Lamport设想出了下面这样一个场景:

拜占庭帝国有许多支军队,不同军队的将军之间必须制定一个统一的行动计划,从而做出进攻或者撤退的决定,同时,各个将军在地理上都是被 分割开来的,只能依靠军队的通讯员来进行通讯。然而,在所有的通讯员中可能会存在叛徒,这些叛徒可以任意篡改消息,从而达到欺骗将军的目的。

这就是著名的“拜占庭将军问题”。从理论上来说,在分布式计算领域,试图在异步系统和不可靠的通道上来达到一致性状态是不可能的,因此在堆一致性的研究 过程中,都往往假设信道是可靠地。而事实上,大多数系统都是部署在同一个局域网中的,因此消息被篡改的情况非常罕见,另一方面,由于硬件和网络原因而 造成的消息不完整问题,只需一套简单的校验算法即可避免——因此,在实际工程实践中,可以假设不存在拜占庭问题,也即假设所有消息都是完整的,没有被 篡改的。那么,在这种情况下需要什么样的算法来保证一致性呢?

Lamport在1990年提出了一个理论上的一致性解决方案,同时给出了严格的数学证明。鉴于之前采用故事类比的方式成功的阐述了“拜占庭将军问题”,因此这次Lamport 同样用新娘库地设想除了一个场景来描述这种一致性算法需要解决的问题,及其具体的解决过程:

在古希腊有一个叫Paxos的小岛,岛上采用议会的形式来通过法令,议会中的议员通过信使进行消息的传递。值得注意的是,议员和信使都是兼职的, 他们随时有可能会离开议会厅,并且信使可能会重复的传递消息,也可能一去不复返。因此,议会协议要保证在这种情况下法令仍然能够正确的产生, 并且不会出现冲突。

这就是兼职议会,而Paxos算法名称的由来也是取自提到的Paxos小岛。

2.2 Paxos算法详解

Paxos作为一种提高分布式系统容错性的一致性算法,一直以来总是被很多人抱怨其算法理论太难理解。

2.2.1 问题描述:

假设有一组可以提出提案的进程集合,那么对于一个一致性算法来说需要保证以下几点:

在这些被提出的提案中,只有一个会被选中。
如果没有提案被提出,那么就不会有被选定的提案。
当一个提案被选定后,进程应该可以获取被选定的提案信息。

对于一致性来说,安全性需求如下:

只有被提出的提案才能被选定。
只能由一个值被选定。
如果某个进程认为某个提案被选定了,那么这个提案必须是真的被选定的那个。

在对Paxos算法的讲解过程中,我们不去精确地定义其活性需求,从整体上来说,Paxos算法的目标就是要保证最终有一个提案会被选定,当提案被选定后, 进程最终也能获取到被选定的提案。

在该一致性算法中,有三种参与角色,我们用Proposer、Acceptor、Learner来表示,在具体的实现中,一个进程可能充当不止一种角色,在这里我们并 不关心进程如何映射到各种角色。假设不同参与者之间可以通过收发消息来进行通信,那么:

每个参与者以任意的速度执行,可能会因为出错而停止,也可能会重启。同时,即使一个提案被选定后,所有的参与者也都有可能失败或重启,因此除非 哪些失败或重启的参与者可以记录某些信息,否则将无法确定最终的值。
消息在传输过程中可能会出现不可预知的延迟,也可能会重复或丢失,但是消息不会被损坏。

2.2.2 提案的选定

要选定一个唯一提案的最简单方式莫过于只允许一个Accpetor存在,这样的话,Proposer只能发送提案给该Accpetor,Acceptor会选择它接收到的第一个 提案作为被选定的提案。这种解决方式尽管实现起来非常简单,但是却很难让人满意,因为一旦这个Accpetor出现问题,那么整个系统就无法工作了。
因此,应该寻找一种更好的解决方式,例如可以使用多个Acceptor来避免Accpetor的单点问题。现在我们就来看看,在存在多个Acceptor的情况下,如何 进行提案的选取:Proposer向一个Acceptor集合发送提案,同样,集合中的每个Acceptor都可能会批准该提案,当有足够多的Acceptor批准这个提案的时候, 我们就可以认为该提案被选定了。那么,什么是足够多呢?我们假定足够多的Acceptor是整个Acceptor集合的一个子集,并且让这个集合大得可以包含Acceptor 集合中的大多数成员,因为任意炼哥包含大多数Acceptor的子集至少有一个公共成员。另外我们再规定,每一个Acceptor最多只能批准一个提案,那么就能 保证只有一个提案被选定了。

2.2.3 推导过程

在没有失败和消息丢失的情况下,如果我们希望即使在只有一个提案被提出的情况下,仍然可以选出一个提案,这就暗示了如下的需求。

P1:一个Acceptor必须批准它收到的第一个提案。

上面这个需求就引出了另外一个问题:如果有多个提案被不同的Proposer同时提出,这可能会导致虽然每个Acceptor都批准了它收到的第一个提案,但是没有一个 提案是由多数人批准的。可能会现以下两种情况


Acceptor接收的提案数量相同,此时无法选定最终的提案了。
因此,在P1的基础上,需要再加上一个提案被选定需要由半数以上的Acceptor批准的需求暗示着一个Acceptor必须能够批准不止一个提案。在这里,我们使用一个全局的编号 (这种全局唯一编号的生成并不是Paxos算法需要关注的地方,就算法本身而言,其假设当前已经具备这样的外部组件能够生成一个全局唯一的编号)来标识每一个 被Acceptor批准的提案,当一个具有某Value值的提案被半数以上的Acceptor批准后,我们就认为该Value被选定了,此时我们也认为该提案被选定了。需要注意的是, 此处讲到的提案和Value不是同一个概念了,提案变成了由编号和Value组成的组合体,因此我们以“[编号,Value]”来表示一个提案。(编号多少的提案被选中了,其中value是多少) 根据上面讲到的内容,我们虽然允许多个提案被选定,但同时必须保证所有被选定的提案都具有相同的Value值——这是一个关于提案Value的约定,结合提案 的编号,该约定可以定义如下:

P2:如果编号为M0、Value值为V0的提案(即[M0、V0])被选定了,那么所有比编号M0更高的,且被选定的提案,其Value值必须也是V0。

因为提案的编号是全序的,条件P2就保证了只有一个Value值被选定这一关键安全性属性。同时,一个提案要被选定,其首先必须至少一个Acceptor批准,因此 我们可以通过满足如下条件来满足P2。

P2a:如果编号为M0、Value值为V0的提案(即[M0、V0])被选定了,那么所有比编号M0更高的,且被Acceptor批准的提案,其Value值必须也是V0。

至此,我们仍然需要P1来保证提案会被选定,但是因为通信是异步的,一个提案可能在某个Acceptor还未收到任何提案时就被选定了。

如上图,在Acceptor1没有接收到任何提案的情况下,其他4个Acceptor已经批准了来自Proposer2的提案[M0,V1],而此时,Proposer1产生了一个具有其他Value值的、 编号更高的提案[M1,V2],并发送给了Acceptor1。根据P1,就需要Acceptor1批准该提案,但是这与P2a矛盾,因此如果要同时满足P1和P2a,需要对P2a进行如下强化:

P2b:如果一个提案[M0,V0]被选定后,那么之后任何Proposer产生的编号的提案,其Value值都为V0。

因为一个提案必须在被Proposer提出后才能被Acceptor批准,因此P2b包含了P2a,进而包含了P2。于是,接下去的重点就是论证P2b成立即可:

假设某个提案[M0,V0]已经被选定了,证明任何编号Mn > M0的提案,其Value值都是V0。

2.2.4 数学归纳法证明

略过。

2.2.5 Proposer生成提案

对于一个Proposer来说,获取哪些已经被通过的提案远比预测未来可能会被通过的提案来得简单。因此,Proposer在产生一个编号为Mn的提案时, 必须要知道当前某一个将要或已经被半数以上Acceptor批准的、编号小于Mn但为最大编号的提案。并且,Proposer会要求所有的Acceptor都不要 再批准任何编号小于Mn的提案——这就引出了如下的提案生成算法。

.1 Proposer选择一个新的提案编号Mn,然后向某个Acceptor集合的成员发送请求,要求该集合中的Acceptor做出如下回应。
向Proposer承诺,保证不再批准任何编号小于Mn的提案。
如果Acceptor已经批准过任何提案,那么其就向Proposer反馈当前该Acceptor已经批准的编号小于Mn但为最大编号的那个提案的值。
我们将该请求称为编号为Mn的提案的Prepare请求。

.2 如果Proposer收到了来自半数以上的Acceptor的响应结果,那么它就可以产生编号为Mn、Value值的Vn的提案,这里的Vn是所有响应中编号最大的提案的Value值。
当然还存在另一种情况,就是半数以上的Acceptor都没有批准过任何提案,即响应不包含任何的提案,那么此时Vn值就可以 由Proposer任意选择。

在确定提案之后,Proposer就会将该提案再次发送给某个Acceptor集合,并期望获得它们的批准,我们称此请求为Accept请求。需要注意的一点是, 此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合——这点相信读者也能够明白,任意两个半数以上的Acceptor集合,必定 包含至少一个公共Acceptor。

2.2.6 Acceptor批准提案

在上文中,我们已经讲解了Paxos算法中Proposer的处理逻辑,下面我们来看看Acceptor是如何批准提案的。

根据上面的内容,一个Acceptor可能会收到来自Proposer的两种请求,分别是Prepare请求和Accept请求,对这两类请求做出相应的条件分别如下。

Prepare请求:Acceptor可以在任何时候响应一个Prepare请求。
Accept请求:在不违背Accept现有承诺的前提下,可以任意响应Accept请求。因此,对Acceptor逻辑处理的约束条件,大体可以定义如下。
P1a:一个Acceptor只要尚未响应过任何编号大于Mn的prepare请求,那么它就可以接受这个编号为Mn的提案。

从上面这个约束条件中,我们可以看出,P1a包含了P1。同时,值得一提的是,Paxos算法允许Acceptor忽略任何请求而不用担心破坏其算法的安全性。

2.2.7 算法优化

在上面的内容中,我们分别从Proposer和Acceptor对提案的生成和批准两方面来讲解了Paxos算法在提案选定过程中的算法细节,同时也在提案的编号全局唯一 的前提下,获得了一个满足安全性需求的提案选定算法,接下来我们再对这个初步算法做一个小优化。尽可能地忽略Prepare请求:

假设一个Acceptor收到了一个编号为Mn的prepare请求,但此时该Acceptor已经对编号大于Mn的prepare请求做出了响应,因此它肯定不会再批准 任何新的编号为Mn的提案,那么狠显然,Acceptor就没有必要对这个Prepare请求做出响应,于是Acceptor可以炫册忽略这样的Prepare请求。同时 Acceptor也可以忽略掉那些它已经批准过的提案的Prepare请求。

通过这个优化,每个Acceptor只需要记住它已经批准的提案的最大编号以及它已经做出Prepare请求响应的提案的最大编号,以便在出现故障或节点重启的情况下, 也能保证P2c的不变性。而对于Proposer来说,只要它可以保证不会产生具有相同编号的提案,那么就可以丢弃任意的提案以及它所有的运行时状态信息。

2.2.8 算法陈述

.1 阶段一:

Proposer选择一个提案编号Mn,然后向Acceptor的某个超过半数的子集成员发送编号为Mn的Prepare请求。
如果一个Acceptor收到一个编号为Mn的Prepare请求,且编号Mn大于该Acceptor已经响应的所有Prepare请求的编号,那么它就会将它已经批准过的最大编号的提案 作为响应反馈给Proposer,同时Acceptor会承诺不会再批准任何编号小于Mn的提案。
举个例子来说,假定一个Acceptor已经响应过的所有Prepare请求对应的提案编号分别为1、2、…、5和7,那么该Acceptor在接收到一个编号为8的 Prepare请求后,就会将编号为7的提案作为响应反馈给Proposer。

.2 阶段二:

如果Proposer收到来自半数以上的Acceptor对于其发出的编号为Mn的Prepare请求的响应,那么它就会发送一个针对[Mn,Vn]提案的Accept请求给Acceptor。 注意,Vn的值就是收到的响应中编号最大的提案的值,如果响应中不包含任何提案,那么它就是任意值。
如果Acceptor收到这个针对[Mn,Vn]提案的Accep请求,只要改Acceptor尚未对编号大于Mn的Prepare请求做出响应,它就可以通过这个提案。
当然,在实际运行过程中,每一个Proposer都有可能会产生多个提案,但只要每个Proposer都遵循如上所述的算法运行,就一定能够保证算法执行的正确性。 值得一提的是,每个Proposer都可以在任意时刻丢弃一个提案,哪怕针对该提案的请求和响应在提案被丢弃后会到达,但根据Paxos算法的一系列规约,依然可以保证 其在提案选定上的正确性,事实上,如果某个Proposer已经在试图 生成编号更大的提案,那么丢弃一些旧的提案未尝不是一个好的选择。 因此,如果一个Acceptor因为已经收到过更大编号的Prepare请求而忽略某个编号更小的Prepare或者Accept请求,那么它也应当通知其对应的Proposer, 以便该Proposer也能够将该提案进行丢弃——这和上面“算法优化”部分中提到的提案丢弃是一致的。

2.2.9 提案的获取

在上文中,我们已经介绍了如何来选定一个提案,下面我们再来看看如何让Learner获取提案,大体可以有以下几种方案。

.1 方案一:

Learner获取一个已经被选定的提案的前提是,该提案已经被半数以上的Acceptor批准。因此,最简单的做法就是一旦Acceptor批准了一个提案,就将该 提案发送给所有的Learner。
很显然,这种做法虽然可以让Learner尽快地获取被选定的提案,但是却需要让每个Acceptor与所有的Learner逐个进行一次通信,通信的次数至少为二者个数的乘积。

.2 方案二:

另一种可行的方案是,我们可以让所有的Acceptor将它们对提案的批准情况,统一发送给一个特定的Learner(下文中我们将这样的Learner称为“主Learner”), 在不考虑拜占庭奖金问题的前提下,我们假定Learner之间可以通过消息通信来互相感知提案的选定情况。基于这样的前提,当主learner被通知一个提案 已经被选定时,它会负责通知其它的Learner。

在这种方案中,Acceptor首先会将得到批准的提案发送给主Learner,再由其同步给其他Learner,因此较方案一而言,方案二虽然需要多一个步骤才能将 提案通知到所有的Learner,但其通信次数却大大减少了,通常只是Acceptor和Learner的个数总和。但同时,该方案引入了一个新的不稳定因素:主Learner随时可能出现故障。

.3 方案三:

在讲解方案二的时候,我们提到,方案二最大的问题在于主Learner存在单点问题,即主Learner随时可能出现故障。因此,对方案二进行改进,可以将主Learner的范围扩大, 即Acceptor可以将批准的提案发送给一个特定的Learner集合,该集合中的每个Learner都可以在一个提案被选定后通知所有其他的Learner。 这个Learner集合中的Learner个数越多,可靠性就越好,但同时网络通信的复杂度也就越高。

2.2.10 通过选取主Proposer保证算法的活性

根据前面的内容坚决,我们已经基本了解Paxos算法的核心逻辑,下面我们再来看看Paxos算法在实际运作过程中的一些细节。假设存在这样一种极端情况, 有两个Proposer依次提出了一系列编号递增的议案,但是最终都无法被选定,具体流程如下:

Proposer P1提出了一个编号为M1的提案,并完成了上述阶段一的流程。但与此同时,另外一个Propoesr P2提出了一个编号为M2的提案,同样也完成了 阶段一的流程,于是Acceptor已经承诺不再批准编号小于M2的提案了。因此,当P1进入阶段二的时候,其发出的Accept请求将被Acceptor忽略, 于是P1再次进入阶段一并提出了一个编号为M3的提案,而这又导致P2在第二阶段的Accept请求被忽略,以此类推,提案的选定过程将陷入死循环。

为了保证Paxos算法流程的可持续性,以避免陷入上述提到的“死循环”,就必须选择一个主Proposer,并规定只有主Proposer才能提出议案。这样一来, 只要主Proposer和过半的Acceptor能够正常进行网络通信,那么但凡主Proposer提出一个编号更高的提案,该提案终将会被批准。当然,如果Proposer发现当前 算法流程中已经有一个编号更大的提案被提出或正在接受批准,那么它会丢弃当前这个编号较小的提案,并最终能够选出一个编号足够大的提案。因此, 如果系统中有足够多的组件(包括Propsoer、Acceptor和其他网络通信组件)能够正常工作,那么通过选择一个主Proposer,整套Paxos算法流程就能够保持活性。

3 小结

2PC和3PC:

  1. 牧师分别问新郎和新娘:你是否愿意……不管生老病死……(投票阶段)。
  2. 当新郎和新娘都回答愿意后(锁定一生的资源,只要有一个没有反应,这场结婚就失败)。(投票阶段)
  3. 牧师就会说:我宣布你们……(执行阶段)。

存在的问题:

  1. 阻塞问题:如果新郎回答原意,新娘没反应,则整个结婚就阻塞。(投票阶段之后增加眼神交流阶段(3PC的额外阶段),之后才真正承诺一生一世不分离即锁定资源)。
  2. 单点问题:如果牧师没反应,整个结婚就失败。(3PC的超时机制,给牧师5秒反应时间)

主要从协议设计和原理实现角度详细讲解了二阶段提交协议、三阶段提交协议和Paxos这三种典型的一致性算法。其中二阶段提交协议解决了分布式事务的原子性问题, 保证了分布式事务的多个参与者要么都执行成功,要么都执行失败。但是,在二阶段解决部分分布式事务问题的同时,依然存在一些难以解决的诸如同步阻塞、 无限期等待问题。三阶段提交协议则是在二阶段提交协议的基础上,添加了PreCommit过程,从而避免了二阶段提交协议中的无限期等待问题。而Paxos算法支持 分布式节点角色之间的轮换,这极大地避免了分布式单点的出现,因此Paxos算法既解决了无限期等待问题,是目前来说最优秀的分布式一致性协议之一。

1. 从集中式到分布式

1.1 集中式的特点

所谓的集中式系统就是指由一台或多台主计算机组成中心节点,数据集中存储于这个中心节点,并且整个系统的所有业务单元都部署在这个中心节点上, 系统的所有功能均由其集中处理。也就是说,在集中式系统中,每个终端或客户端机器仅仅负责数据的录入和输出,而数据的存储与控制处理完全 交由主机来完成。

最大的特点就是部署结构简单。由于集中式系统往往基于底层性能卓越的大型主机,因此无须考虑如何对服务进行多个节点的部署,也就不用考虑多个 节点之间的分布式协作问题。

1.2 分布式的特点

分布式系统是一个硬件或者软件组成分布在不同的网络计算上,彼此之间仅仅通过消息传递进行通信和协调的系统。

一个标准的分布式系统在没有任何特定业务逻辑约束的情况下,都会有如下几个特征:

分布性:分布式系统中的多台计算机在空间上随意分布。
对等性:分布式系统中的计算机没有主/从之分,既没有控制整个系统的主机,也没有被控制的从机,组成分布式系统的所有计算机节点都是对等的。 副本(Replica)是分布式系统最常见的概念之一,指的是分布式系统对数据和服务提供一种冗余方式。在常见的分布式系统中,为了对外提供高可用的服务, 我们往往会对数据和服务进行副本处理。不同的节点上持久化同一份数据,当某一个节点上存储的数据丢失时,可以从副本上读取到该数据,另一类副本是 服务副本,指多个节点提供同样的服务,每个节点都有能力接收来自外部的请求并进行相应的处理。
并发性:同一个分布式系统中的多个节点,可能会并发地操作一些共享的资源,诸如数据库或分布式存储等,如何准确并高效地协调分布式并发操作也成为了分布式 系统架构与设计中最大的挑战之一。
缺乏全局时钟:一个典型的分布式系统是由一系列在空间上随意分布的多个进程组成的,具有明显的分布性,这些进程之间通过交换下次来进行相互通信。 因此,在分布式系统中,很难定义两个时间的顺序,原因就是因为分布式系统缺乏一个全局的时钟序列控制。
故障总是会发生:组成分布式系统的所有计算机,都有可能发生任何形式的故障。任何在设计阶段考虑到的异常情况,一定会在系统实际运行中发生!

##1.3 分布式环境的各种问题

1.3.1 通信异常

分布式引入了网络因素,而由于网络本身的不可靠性,因此每次网络通信都会伴随网络不可用的风险,网络光纤、路由器和DNS等。因此消息丢失和消息延迟变得非常普遍。

1.3.2 网络分区

当网络由于发生异常情况,导致分布式系统中部分节点之间的网络延时不断增大,最终导致组成分布式系统的所有节点中,只有部分节点之间能够正常通信, 而另一些节点则不能——我们将这个现象称为网络分区。网络分区出现时,分布式系统会出现局部小集群,在极端情况下,这些局部小集群会独立完成原本 需要整个分布式系统才能完成的功能,包括对数据的事务处理,这就对分布式一致性提出了非常大的挑战(某个复杂业务原本需要多个机器完成,现在被一个机器 执行)。

1.3.3 三态

分布式系统的每一次请求与响应,存在特有的“三态”概念,即成功、失败与超时。超时的现象,通常有以下两种情况:

由于网络原因,请求并没有被成功地发送到接收方,在发送过程就发生了消息丢失现象。
请求成功的被接收方接收后,并进行了处理,但是在将响应反馈给发送方的过程中,发生了消息丢失现象。(rabitMQ的解决方案是,消费者(接收方)开始处理消息前发送响应A, 消费者(接收方)处理完成消息后发送响应B,生产者(发送方)必须得到AB两个响应才能确定消息成功被处理了)

2. 从ACID到CAP/BASE

2.1 ACID

事务(Transaction)是由一系列对系统中数据进行访问与更新的操作所组成的一个程序执行逻辑单元(Unit)。

2.1.1 原子性(Atomicity)

要么全部成功执行,要么全部不执行。

2.1.2 一致性(Consistency)

事务的运行被迫中断时,这些未完成的事务对数据库所做的修改有一部分已写入物理数据库,这时数据库就处于不一致的状态。

2.1.3 隔离性(Isolation)

并发的事务是相互隔离的,一个事务的执行不能被其他事务干扰。SQL规范定义了4个事务隔离级别:

  1. 读未提交(Read Uncommitted):A事务更新过程中,从1更新到10,B事务能获取过程中间值,获取到2,3等值。(脏读)
  2. 读已提交(Read Committed):A事务更新过程中,从1更新到10,B事务只能获取最终的值10。
  3. 可重复读(Repeatable Read):A事务更新过程中,从1更新到10,B事务先获取了1,后来B事务中有个操作重新获取了一次值为10。(幻影读)
  4. 串行化(Serializable):事务只能串行执行,不能并发。

2.1.4 持久性(Durability)

事务一旦提交,对数据库对应数据的状态变更就应该被永久保存下来。

2.1 分布式事务

设想一个最典型的分布式事务场景:一个跨银行的转账操作涉及调用两个异地的银行服务,其中一个是本地银行提供的取款服务,另一个则是目标银行提供的存款 服务,这两个服务本身是无状态并且是互相独立的,共同构成了一个完整的分布式事务。如果从本地银行取款成功,但是因为某种原因存款服务失败了,那么 就必须回滚到取款前的状态,否则用户可能会发现自己的钱不翼而飞了。

我们可以看到,一个分布式事务可以看作是由多个分布式的操作序列组成的,例如上面例子中的取款服务和存款服务,通常可以把这一系列分布式的操作序列称为 子事务。因为,分布式事务也可以被定义为一种嵌套型的事务,同时也就具有了ACID事务特性。但由于在分布式事务中,各个子事务的执行时分布式的, 因此要实现一种能够保证ACID特性的分布式事务处理系统就显得格外复杂。

2.3 CAP和BASE理论

ACID是属于单机系统的理论,分布式有属于自己的理论,即CAP和BASE。

2.3.1 CAP定理

一个分布式系统不可能同时满足一致性(Consistency)、可用性(Availability)、分区容错性(Partition tolerance)这三个基本需求,最多只能同时 满足其中的两项。

.1 Consistency

在分布式环境下,数据在多个副本之间是否能够保持一致性,当某个副本执行更新操作后,应该保证系统的数据仍然处于一致的状态。如果做到一个数据项的更新 操作执行成功后,所有的用户都可以读取到最新的值,那么这样的系统就被认为具有强一致性。

.2 Availability

对于用户的每一个操作请求总是能够在有限的时间内返回结果。划重点:有限的时间内、返回结果。

有限的时间内:对于用户的一个艹做请求,系统必须能够在指定的时间内返回对应的处理结果,如果超过了这个时间范围,那么系统就被认为是不可用的。 比如,对于一个在线搜索引擎来说,通常在0.5秒内需要给出用户搜索关键词对应的检索结果,而对于一个面向HIVE的海量数据查询平台来说,正常一次数据 检索时间可能在20秒,这是正常的,系统必须存在一个合理的响应时间。
返回结果:要求系统在完成堆用户请求的处理后,返回一个正常的结果,而不是返回系统错误。

.3 Partition tolerance

分布式系统在遇到任何网络分区故障的时候(节点间的故障),仍然需要保证对外提供满足一致性和可用性的服务,除非整个网络环境发生了故障。

.4 总结

  • AC:所有的数据都放在一个分布式节点上。(谈什么分布式?)
  • PC:系统正在维修,请等待。(要么可用,要么直接不能访问)
  • AP:放弃数据的强一致性,保留数据额最终一致性。(双11xx商品正在被5126人浏览,可能每个人看到的数字都不一样,但是系统最终会让所有人看到一样的数字)

2.3.2 BASE理论

基于CAP定理结合实际演化而来,即Basically Available(基本可用)、Soft state(软状态)、Eventually consistency(最终一致性)。

.1 Basically Available

分布式在出现不可预知故障的时候,允许损失部分可用性:

响应时间上的损失:搜索正常是0.5秒返回用户,出现故障变成2秒。
功能上的损失:网上购物在双11时选择购买可能会跳转到排队页面。

.2 Soft state

允许系统中的数据存在中间状态,并认为该中间状态的存在不会影响系统的整体可用性,即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

.3 Eventually consistency

强调数据最终数据能够达到一致,而不需要实时保证系统数据的强一致性。 在实际工程实践中,最终一致性存在以下五类主要变种。

.3.1 因果一致性(Causal consistency)

进程A更新完某个数据项后通知了进程B,那么进程B之后对该数据的访问都应该能够获取到进程A更新后的最新纸,并且如果进程B要对该数据项进行更新操作的话, 务必基于进程A更新后的最新值。而进程C的数据访问则没有这样的限制。

.3.2 读己之所写(Read your writes)

进程A更新了一个数据项,它自己总是能够访问到更新过的最新值。特殊的因果一致性(A进程通知了A进程)。

.3.3 会话一致性(Session consistency)

系统能保证在同一个有效的会话中实现“读己之所写”的一致性,即客户端能够在同一绘画中始终读取到该数据项的最新值。

.3.4 单调读一致性(Monotonic read consistency)

如果一个进程从系统读取出一个数据项的某个值后,那么系统对于该进程后续的任何数据访问都不应该返回更旧的值。

.3.5 单调写一致性(Monotonic write consistency)

系统保证来自同一个进程的写操作被顺序地执行。

.3.6 总结

最终一致性并不是只有那些大型分布式系统才涉及的特性,许多关系型数据库都采用了最终一致性模型,采用同步和异步方式来实现主备数据复制技术。

在同步方式中,数据的复制过程通常是更新事务的一部分,因此在书屋完成后,主备数据库的数据就会达到一致。
在异步方式中,备库的更新往往会存在延时,这取决于事务日志在主备数据库之间传输的时间长达,如果传输时间过长或者甚至在日志传输过程中出现异常导致 无法及时将事务应用到备库上,那么很显然,从备库读取的数据将是旧的,就出现了数据不一致的情况。
但是,无论采用重试、人为修正,关系型数据库还是能够保证最终数据达到一致性——这就是系统提供最终一致性保证的经典案例。

总的来说,BASE理论面向大型高可用可扩展的分布式系统,和传统事务的ACID特性是相反的,不同于ACID的强一致性模型,而是通过强一致性和高可用性的 平衡,最终达到一致性。因此在具体的分布式系统架构设计过程中,ACID和BASE理论往往会结合一起使用用来面对不同的业务场景的要求。

3. 小结

分布式架构发展过程中的ACID->CAP->BASE等分布式事务与一致性方面的经典理论。

如何挖掘出 Java 线程和同步设施的最大性能


1 线程池与 ThreadPollExecutor

Java EE 应用服务器就是围绕用一个或多个线程池处理请求这一概念构建的:对服务器上 Servlet 的每个调用都是通过池中的线程处理的(也有可能不同)。类似的,其它应用可以使用 Java 的 ThreadPoolExecutor 并行执行任务。

所有线程池的工作方法本质是一样的:有一个队列,任务被提交到这个队列中。(可以有不止一个队列,概念是一样的。)一定数量的线程会从该队列中取任务,然后执行。任务的结果可以发回客户端(比如应用服务器的情况下),或保存到数据库中。但是在执行完任务后,这个线程会返回任务队列,检索另一个任务并执行(如果没有更多任务要执行,该线程会等待下一个任务)。

线程池有最小线程数和最大线程数。池中会有最小数目的线程随时待命,等待任务指派给它们。因为创建线程的成本非常高昂,这样可以提高任务提交时的整体性能。另一方面,线程需要一些系统次元,包括栈所需的原生内存,如果空闲线程太多,就会消耗本来可以分配给其它金恒的资源。

ThreadPoolExecutor 和相关的类将最小线程数称为核心池大小。

1.1 设置最大线程数

使用 CPU 的最大线程数

1.2 设置最小线程数

也可称为初始线程数和核心线程数,尽量能做到刚好能满足基本的任务需要,同时,如果线程运行完任务后,他作为空闲线程需要保留 10~30 分钟,来应对可能的新任务。

注意:线程局部变量

1.3 线程池任务大小

如果当前任务队列有 30,000 个任务,有 4 个 CPU 可用,执行一个任务需要 50 毫秒,则清空任务队列需要 6 分钟。当任务列队达到阈值,需要返回合理的错误。

1.4 设置 ThreadPoolExecutor 的大小

标准线程池:创建时准备最小数目的线程,来一个任务,并且当前所有的线程都在忙碌,则启动一个新线程,任务就立即执行。否则加入等待队列,如果队列满了,则拒绝。
ThreadPoolExecuter 表现则不同:

  1. SynchronousQueue
    来一个任务则创建线程执行任务,没有等待队列。建议将最大线程数指定为一个非常大的值,同时任务是
    完全 CPU 密集型最合适。
  2. 无界队列
    如果 ThreadPoolExecutor 搭配的是无界队列(例如 LinkedBlockedingQueue,链表阻塞队列,默认 Integer.MAX,包括 take 操作和 put 操作,FIFO 队列)。
  3. 无界队列
    有界队列,例如 ArrayBlockingQueue(FIFO)。 假如 coreThread 为 4,maxThread 为 8,用的 ArrayBlockingQueue 为 10。任务先占满 4 个 coreThread,接着占用 10 个 queue,最后才会启动 maxThread-coreThread 的 4 个线程。

    这个算法的背后理念在于:池大部分时间使用核心线程,只有当积压到一定的阈值后,才启动线程执行。

2 ForkJoinPool

使用 fork 和 join 对任务进行分、并操作, 大任务变成两个小任务,由两个线程执行这两个小任务,另一个线程用于合并这两个任务的结果, 还有另一个特性是工作窃取:每个线程有自己的任务队列,当某个线程完成了自己的任务队列,就会执行另一个未执行完的任务队列的尾部任务。

Java 8 中使用了自动并行化的特性,用到的就是一个公共的 ForkJoinPool 实例,其中的 forEach 会并行的计算。

1
2
3
4
Stream<Integer> stream = arrayList.parallelStream();
stream.forEach(a -> {
doSomething()
});

3 线程同步

3.1 线程的代价

同步的目的是保护对内存中的值的访问。变量有可能临时保存在寄存器中,这比直接在主内存中访问更高效。寄存器值对其它线程是不可见的,
而当一个线程离开某个同步块时,必须将任何修改的值刷新到主内存中。

3.2 避免同步

  1. 使用线程局部变量 ThreadLocal
  2. 使用 CAS 无锁操作,atomic 包

3.3 伪共享

  1. 伪共享:加载内存时,同时会加载邻接的值,作为缓存行, 因此 会出现伪共享问题:当程序更新本地缓存中的某个值,需要通知其它核作废缓存行中的所有涉及的值,重新从缓存行中加载。
  2. 在 volatile 中问题比较突出, 频繁的修改 volatile 以及退出同步块的代码。
  3. 使用 @Contentded 进行宽度填充( J默认情况下仅在 JVM 内部使用,Doug Lea 使用多余的变量进行宽度填充)

4 JVM 线程调优

4.1 调节线程栈大小

64位机器默认线程栈大小为 1MB,栈的异常:StackOverflowError

调节线程栈大小:-Xss=256k

4.2 偏向锁

如果一个线程最近使用了某个锁,那么该线程下一次执行由同一把锁保护的代码所需的代码可能仍然保存在处理器的缓存中。使用对象头
的某个空间来记录该线程的 id,下次访问直接进入该锁。

4.3 自旋锁

JVM 处理同步锁的竞争问题,有两种选择:

  1. 死循环+检查该锁
  2. 将该线程放入线程等待池队列,在锁可用时通知该队列。

而 JVM 会自动调整将线程从循环到通知队列的时间。

5 监控线程与锁

5.1 查看线程

使用 Jstack、jcmd

注意:JVM 只能在特定的位置(safepoint,安全点)转储出一个线程的栈,每次只能针对一个线程转储出栈的纤细。

6 小结

  1. ThreadPollExecutor 三种队列
  2. 避免同步的两种方式:ThreadLocal、CAS
  3. 伪共享
  4. 偏向锁和自旋锁
  5. 使用死循环 +检查锁的状态、将线程放入线程池中来处理锁的竞争问题
  6. jstack 命令

0 CPU 使用率

使用 vmstat 命令查看 CPU 使用率,即 us\sy\id 三个参数,用户、系统、空闲使用 CPU 的时间。

  1. 检查应用性能时,首先应该审查 CPU 时间(尤其是多线程,CPU 的上下文切换报告)
  2. 优化代码的目的是提升而不是降低(更短时间段内的)CPU 使用率。
  3. 在试图深入优化应用前,应该先弄清楚为何 CPU 使用率低。

1 JIT 编译器

java文件->编译->class字节码文件->JVM编译解释成平台相关的二进制文件。
而 JIT 编译器属于最后的 JVM 编译过程,也可以称为后端编译器,这样便于理解
Java 应用汇被编译——但不是编译成特定 CPU 所专用的二进制代码,而是被编译成一种理想化的汇编语言(即 .class 字节码文件),它专用于 JVM 所执行。这个编译时在程序执行时进行的,即编译同时执行,(C 这种编译语言会先编译成 .o 或者 .obj 再执行),而 Java 是直接执行编译代码(JVM 执行)。Java 是一种半编译半解释语言(先编译成 .class,再让 JVM 解释成特定 CPU 的指令),而 Java 的表面直接执行其实内部 JVM 帮我们做了编译解释,不像 C 用户手动编译再执行,因为 C 的编译后的 .o 文件是针对特定的 CPU ,也许在下个 CPU 就需要重新编译了。参见:https://www.zhihu.com/question/21486706

由于编译成 .class 这个行为是在程序执行的时候进行的,因为被称为“即时编译”(即JIT,just in time)。你也可以先 javac 编译后,再 java 命令 执行。

1.热点编译

官方的 java 实现是 Oracle 的 HotSpot JVM。HotSpot 的名字来与它看待代码编译的方式。对于程序来说,通常只有一部分代码被经常执行,而应用的性能就取决于这些代码执行得有多快。这些关键代码段被称为应用的热点,代码执行得越多就被认为是越热。

因此 JVM 执行代码时,并不会立即编译代码。原因1:如果代码只执行一次,那编译完全就是浪费精力。对于只执行一次的代码,解释执行 Java 字节码比先编译然后执行的速度快。原因2:JVM 执行特定方法或者循环的次数越多,它就会越了解这段代码,使得 JVM 可以在编译代码时进行大量优化。

例,equals() 方法,存在每个 Java 对象中,并且经常被子类重写。当解释器遇到 b = obj1.equals(obj2) 语句时,为了知道该执行哪个 equals() ,必须先查找 obj1 的类。这个动态查找的过程有点消耗时间。

寄存器和主内存:

1
2
3
4
5
6
7
8
9
>public class RegisterTest {
> private int sum;
> public void calculateSum(int n) {
> for(int i = 0; i < n; i++) {
> sum += i;
> }
> }
>}
>

实例变量如果一直存在主内存中,但是从主内存获取数据是非常昂贵的操作,需要花费多个时钟周期才能完成,这样性能就会比较低,编译器就不会这么做,它会将 sum 的初始值装入寄存器,用寄存器中的值执行循环,然后(某个不确定时刻)将最终的结果从寄存器写回主内存。
使用寄存器是编译器普遍采用的优化方法,当开启逃逸分析(escape analysis)时,寄存器的使用更为频繁(详见本章尾)。

比如,随着时间流逝, JVM 发现每次执行这条语句时,obj1 的类型都是 java.lang.String。于是 JVM 就可以生成直接调用 String.equals() 的编译代码。现在代码更快乐,不仅是因为被编译,也是因为跳过了查找该调用哪个方法的步骤。
不过没那么简单,下次执行代码时,obj1 完全有可能是别的类型而不是 String ,所以 JVM 必须生成编译代码处理这种可能,尽管如此,由于跳过了方法查找的步骤,这里的编译代码整体性能仍然要快(至少和 obj1 一直是 String时同样快)。这种优化只有在代码运行过一段时间观察它如何做之后才能使用:这是为何 JIT 编译器等待代码编译的第二个原因。

2 调优入门:选择编译器类型(client/server或两者同用)

有两种 JIT 编译器,client 和 server。两者编译器的最主要的差别在于编译代码的时机不同。
client 编译器开启编译比 server 编译器要早。意味着在代码执行的开始阶段,client 编译器比 server 编译器要快,因为它编译代码相比 server 编译器而言要多。
server 编译器等待编译的时候是否还能做更有价值的事:server 编译器在编译代码时可以更好地进行优化。最终,server 编译器生成的代码要比 client 编译器快。
此处的问题:为什么需要人来做这种选择?为什么 JVM 不能在启动用 client 编译器,然后随着代码变热使用 server 编译器?这种技术被称为分层编译。java7 的分层编译容易超出 JVM 代码缓存的大小,默认关闭。在 java8 分层编译默认为开启。
即时应用永远运行, server 编译器也不可能编译它的所有代码,但是任何程序都有一小部分代码很少执行,最好是编译这些代码——即便编译不是最好的方法——而不是以解释模式运行。

对于长时间运行的应用来说,应该一直使用 server 编译器,最好配合分层编译器。

3 Java 和 JIT 编译器版本

JIT 编译器有 3 种版本:

  1. 32位 client 编译器(-client)
  2. 32位 server 编译器(-server)
  3. 64位 server 编译器(-d64)

4 编译器中级调优

1.调优代码缓存

JVM 编译代码时,会在代码缓存中保存编译之后的汇编语言指令集。代码缓存一旦填满,JVM 就不能编译更多代码了(只能解释执行其余代码了)。
但是,如果设置过多,例如设置代码缓存为 1GB,JVM 就会保留 1GB 的本地内存空间。然后这部分内存在需要时才会分配,但它仍然是保留的,这意味着为了满足保留内存,你的机器必须有足够的虚拟内存。
此外,如果是 32位 JVM,则进程占用的总内存不能超过 4GB。这包括 Java堆、JVM 自身所有嗲吗占用的空间(包括它的本地库和线程栈)、分配给应用的本地内存(或者 NIO 库的直接内存),当然还有代码缓存。
代码缓存: -XX:ReservedCodeCacheSize=N ,可以设置代码缓存的最大值。

2.编译阈值

编译时基于两种 JVM 计数器的:方法调用计数器和方法中的循环回边计数器。回边实际上可看作是循环完成执行的次数。
JVM 执行某个 Java 方法时,会检查该方法的两种计数器总数,然后判定该方法是否适合编译。如果适合就进入编译队列。被称为标准编译。
如果循环真的很长——或因包含所有程序逻辑而永远不退出,JVM 不等方法被调用就会编译循环。所以循环每完成一轮,回边计数器就会增加并被检测。如果循环的回边计数器超过阈值,那这个循环(不是整个方法)就可以被编译。被称为栈上替换(On-Stack Replacement,OSR)。

标准编译由: -XX:CompileThreshold=N 标志触发。

5 高级编译器调优

前面说道,当方法(或循环)适合编译时,就会进入到编译队列。队列则由一个或多个后台线程处理。这是件好事,意味着编译过程是异步的,这使得即便是代码正在编译的时候,程序也能持续执行。如果是用标准编译所编译的方法,那下次调用该方法时就会执行编译后的方法;如果是用 OSR 编译的循环,那下次循环迭代时就会执行编译后的代码。

编译队列并不严格遵守先进先出的原则:调用次数多的方法有更高的优先级(非公平更好使)。

5.1 逃逸分析

开启逃逸分析: -XX:DoEscapeAnalysis,默认为 true。server 编译器将会执行一些非常激进的优化措施,例如, for 循环中的新建变量,如果对象只在循环中引用,JVM 会毫不犹豫地对这个对象进行一系列优化。
包括,锁去除,值存储在寄存器而不是内存中,甚至不需要分配实际的对象,可以只追踪这个对象的个别字段。

6 逆优化

有两种逆优化的情形:代码状态分别为“made not entrant”(代码被丢弃)和“made zombie”(产生僵尸代码)时。

6.1 代码被丢弃

当一个接口有多重实现,在使用switch 进行工厂模式的创建时,可能上次的编译器内联,在下次就必须使用解释执行了,因为对象变了,要开始新的编译,而上次的编译代码就属于丢弃代码。
另一种情况就是,分层编译。先使用 client 编译,再使用 server 编译,那么在第二次编译时,第一次编译的一些代码就要被丢弃,属于丢弃代码。

6.2 逆优化僵尸代码

  1. 逆优化使得编译器可以回到之前版本的编译代码。
  2. 先前的优化不再有效时(例,所设计的对象类型发生了更改),才会发生代码逆优化。
  3. 代码逆优化时,会对性能产生一些小而短暂的影响。

7 小结

  1. 不用担心小方法,特别是 getter 和 setter ,因为它们很容易内联。编译器会修复这些问题。
  2. 需要编译的代码在编译队列中。队列中代码越多,程序达到最佳性能的时间越久。
  3. 虽然代码缓存的大小(也应该)调整,但它仍然是有限的资源。
  4. 代码越简单,优化越多。分析反馈和逃逸分析可以使代码更快,但复杂的循环结果和大方法限制了它的有效性。

很多时候,我们没有机会重写代码,又要面临需要提高 Java 应用性能的压力,这种情况下对垃圾收集器的调优就变得至关重要。

  1. Serial 收集器(常用于单 CPU环境)。
  2. Throughput(或者 Parallel)收集器。
  3. Concurrent 收集器(CMS)。
  4. G1 收集器。

1 垃圾收集概述

简单来说,垃圾收集由两步构成:查找不再使用的对象,以及释放这些对象所管理的内存。 JVM 从查找不再使用的对象(垃圾对象)入手。有时,这也被称为查找不再有任何对象引用的对象(暗指采用“引用计数”的方式统计对象引用)。

例,如下场景:一个程序要分配大小为 1000 字节的数组,紧接着又分配一个大小为 24 字节的数组,并在一个循环中持续进行这样的分配。最终程序会耗尽整个堆,结果如下图的第一行所示:堆空间被沾满,分配的数组间隔地分布于整个堆内:
![][1]
堆内存用尽会触发 JVM 回收不再使用的数组空间。假设所有大小为 24 字节的数组都不再被使用,而大小为 1000 字节的数组还继续使用,这样就形成了上图的第二行的场景。
虽然堆内部有足够的空闲空间,却找不到任何一个大于 24 字节的连续空间,除非 JVM 移动所有大小为 1000 字节的数组,让它们连续存储,把空闲的空间整合成一块更大的连续空间,供其他的内存分配使用(如上图的第三行)。

而垃圾收集的性能就是由这些基本操作所决定的:找到不再使用的对象、回收它们使用的内存、对堆的内存布局进行压缩整理。完成这些操作时不同的收集器采用了不同的方法,这也是不同垃圾收起表现出不同性能特征的原因。
通常垃圾收集器自身往往也是多线程的。接下来的讨论中,我们从逻辑上将县城分成了两组,分别是应用程序线程和处理垃圾收集的线程。垃圾收集器回收对象,或者在内存中移动对象时,必须确保应用程序线程不再继续使用这些对象。这一点在收集器移动对象时尤其重要:在操作过程中,对象的内存地址会发生变化,因此这个过程中任何应用线程都不应再访问该对象。

所有应用线程都停止运行所产生的停顿被称为时空停顿(stop-the-world)。通常这些停顿对应用的性能影响对打,调优垃圾收集时,尽量减少这种停顿是最为关键的考量因素。

1.1 分代垃圾收集器

虽然实现的细节千差万别,但所有的垃圾收集器都遵循了同一个方式,即根据情况将堆划分成不同的代(Generation)。这些代被称为“老年代”(Old Generation 或 Tenured Generation)和“新生代”(Young Generation)。新生代又被进一步划分为不同的区段,分别称为 Eden 空间和 survivor 空间(不过 Eden 有时会被错误地用于指代整个新生代)。

新生代被填满时,垃圾收集器会暂停所有的应用线程,回收新生代空间。不再使用的对象会被回收,仍然在使用的对象会被移动到其它地方。这种操作被称为 Minor GC。
采用这种设计有两个性能上的优势:

  1. 新生代仅是堆的一部分,这意味着应用线程停顿的时间更短。但是更加频繁。
  2. 对象分配与 Eden 空间,垃圾收集时,新生代空间被清空,Eden 空间的对象要么被移走,要么移动到另一个 Survivor 空间,要么被移动到老年代。这就相当于自动的进行了一次压缩整理。

所有的垃圾收集算法在对新生代回收时都存在“时空停顿”现象。

JVM 需要找出老年代中不再使用的对象,并对它们进行回收。而这便是垃圾收集算法差异最大的地方。简单的:停掉所有的应用线程,找出不再使用的对象,对其进行回收,接着对对空间进行整理。这个过程称为 Full GC。这通常会导致应用线程长时间的停顿。

另,通过更复杂的计算,我们还有可能在应用线程运行的同时找出不再使用的对象;
CMS 和 G1 收集器就是通过这种方式进行垃圾收集的。由于它们不需要停止应用线程就能找出不再用的对象, CMS 和 G1 收集器被称为 Concurrent 垃圾收集器。同时,由于它们将停止应用程序的可能降到了最小,也被称为低停顿(Low-Pause)收集器。Concurrent 收集器也使用各种不同的方法对老年代空间进行压缩。

使用 CMS 和 G1 收集器时,应用程序经历的停顿会更少(也更短),代价是会消耗更多的 CPU。

  1. 所有的 GC 算法都将堆划分成了老年代和新生代。
  2. 所有的 GC 算法在清理新生代对象时,都使用了“时空停顿”(stop-the-world)方式的垃圾收集方法。

1.2 GC 算法

JVM 提供了以下四种不同的垃圾收集算法。

1.Serial 垃圾收集器

它是单线程清理堆的内容。使用 Serial 垃圾收集器,无论是进行 Minor GC 还是 Full GC ,清理堆空间时,所有的应用线程都会被暂停。

2.Throughput 垃圾收集器

Throughput 收集器是 Server 级虚拟机(多 CPU)的默认收集器。
使用多线程回收新生代空间, Minoc GC 的速度比使用 Serial 收集器快得多。处理老年代在 JDK7 之后默认也是多线程。因为其使用多线程,也被称为 Parallel 收集器。
在 Minor GC 和 Full GC 时会暂停所有的应用线程,同时在 Full GC 过程中会对老年代空间进行压缩整理。

3.CMS 收集器

CMS 收集器设计的初衷是为了消除 Throughput 收集器和 Serial 收集器 Full GC 周期中的长时间停顿。 CMS 收集器在 Minor GC 时会暂停所有的应用线程,并以多线程的方式进行垃圾回收。
它不使用 Throughput 的收集算法(-XX:+UseParallelGC),而是用新的算法(-XX:+UseParNewGC)来收集新生代对象。
它在 Full GC 不再暂停应用线程,而是使用若干个后台线程定期地对老年代空间进行扫描,及时回收其中不再使用的对象。这种算法使 CMS 成为一个低延迟的收集器:应用线程只在 Minor GC 以后后台线程扫描老年代时发生极其短暂的停顿。
代价是额外的 CPU 使用率。而且后台线程不再进行任何压缩整理的工作,这意味着逐渐碎片化,碎片化一定程度, CMS 会降级为 Serial 收集器:暂停所有应用线程,使用单线程回收。之后再恢复到并发回收。(这种思想在写锁降级为读锁也有体现)。

4.G1 收集器

G1 垃圾收集器(垃圾优先收集器)的设计初衷是为了尽量缩短处理超大堆(大于4 GB)时产生的停顿。G1 收集算法将老年堆划分为若干个区域(Region),不过它依旧属于分代收集器。这些区域中的一部分包含新生代,新生代的垃圾收集仍然采用暂停所有应用线程的方法,将存活对象移动到老年代或者 Survivor 空间,这也是多线程完成的。

G1 收集器属于 Concurrent 收集器:老年代的垃圾收集工作由后台线程完成,大多数的工作不需要暂停应用线程。由于老年代被划分到不同的区域,G1 收集器通过将对象从一个区域复制到另一个区域,完成对象的清理工作,这也意味着在正常的处理过程中,G1 收集器实现了堆的压缩整理(至少是部分的整理)。因此,使用G1 收集器的堆不大容易发生碎片化——虽然这种问题无法避免。

通常情况下垃圾收集是由 JVM 在需要的时候触发:新生代用尽时会触发 Minor GC,老年代用尽时会触发 Full GC,或者堆空间即将填满时会触发 Concurrent 垃圾收集。
System.gc() 让应用程序强制进行 GC, Full GC。应用程序线程会因此而停顿相当长的一段时间。同时,调用这个方法也不会让应用程序更高效,它会让 GC 更早的开始,但那实际只是将性能的影响往后推迟而已。

2 GC 调优基础

2.1 调整堆的大小

如果分配的堆过于小,程序的大部分时间可能都消耗在 GC 上。
如果分配的过于大也不行,GC 停顿消耗的时间取决于堆的大小,如果增大堆的空间,停顿的持续时间也会变长,这种情况下,停顿的频率会变得更少,但是它们持续的时间会让程序的整体性能变慢。还有一个风险是,操作系统使用虚拟内存机制管理机器的物理内存。一台机器可能有 8G 的物理内存,不过操作系统可能让你感觉有更多的可用内存。虚拟内存的数量取决于操作系统的设置,譬如操作系统可能让你感觉它的内存达到了 16G 。操作系统通过名为“交换”(swapping)(或者称之为分页,虽然两者技术存在差异)。你可以载入需要 16G 内存的应用程序,操作系统在需要时会将程序运行时不活跃的数据由内存复制到磁盘。再次需要这部分内存的内容时,操作系统再将它们由磁盘重新载入到内存(为了腾出空间,通常它会先将另一部分内存的内容复制到磁盘)。

系统中运行着大量不同的应用程序时,这个流程工作的很顺畅,因为大多数的应用程序不会同时处于活跃状态。但是,对于 Java 应用,它工作得并不那么好。如果一个 Java 应用使用了这个系统上大约 12G 的堆,操作系统可能在 RAM 上分配了 8G 的堆空间,另外 4G 的空间存在于磁盘。这样操作系统需要将相当一部分的数据由磁盘交换到内存,而发生 Full GC 时,因为 JVM 必须访问整个堆的内容,如果系统发生内存交换,停顿时间会更长。

堆的大小由 2 个参数值控制:初始值(-Xms)、最大值(-Xmx)。

2.2 代空间的调整

一旦堆的大小确定下来,JVM 就需要决定分配多少堆给新生代空间,多少给老年代空间。
必须清楚:如果新生代分配得比较大,垃圾收集发生的频率就比较低,从新生代晋升到老年代的对象也更少。但是老年代相对比较小,容易填满,会更频繁的触发 Full GC。

  1. -XX:NewRatio=N:设置新生代与老年代的空间占用比率
  2. -XX:NewSize=N:设置新生代空间的初始大小
  3. -XX:MaxNewSize=N:设置新生代空间的最大大小
  4. -XmnN:将 NewSize 和 MaxNewSize 设定为同一个值的快捷方法。

2.3 永久代和元空间的调整

JVM 载入类的时候,它需要记录这些类的元数据。这部分数据被保存在一个单独的堆空间中。在 Java7 里,这部分空间被称为永久代(Permgen),在 Java8 中,它们被称为元空间(Metaspace)。
永久代和元空间并不完全一样。Java7 中永久代还保存了一些与类数据无关的杂项对象;这些对象在 Java8 中被挪到了普通的堆空间内。它们保存的信息只对编译器或者 JVM 的运行时有用。
通过 -XX:PermSize=N、-XX:MaxPerSize=N 来调整永久代大小。
通过 -XX:MetaspaceSize=N、-XX:MaxMetaspaceSize=N 来调整元空间的大小。

调整这些区间会触发 Full GC ,所以是一种代价昂贵的操作。如果程序在启动时发生大量的 Full GC(因为需要载入数量巨大的类),通常都是由于永久代或者元空间发生了大小调整。

3 垃圾回收工具

开启 GC 的日志功能:使用 -verbose:gc 或 -XX:+PrintGC 的任意一个能创建基本的 GC 日志。使用 -XX:+PrintGCDetails 创建更详细的 GC 日志。

4 小结

多说无益,多尝试。

![1]: http://leran2deeplearnjavawebtech.oss-cn-beijing.aliyuncs.com/learn/Java_performance_definitive_guide/5_1.png