我们知道散布式系统中各个效劳器都是经过网路停止衔接的，这样招致的结果就是你很难知道各个效劳器的真实状况，比如你判别另外一台效劳器能否有成绩的独一办法就是发送一个央求给他，只要收到了回应，你就以为它是好的，假设没有收到回应，你就很难判别对面的效劳器能否有成绩，由于这个没有回应很能够是发作了网络缺点，也能够是对端机器真的出成绩了。 因此，在散布式系统中我们如何来准确判别这些成绩呢？ 本文就来详细引见相关的办法。
基于少数的（Majority）理想很多时分我们一个节点能够不是真的有成绩，比如说它正在停止 GC ，那么在 GC 的这段时间内它就不能回应任何央求，这个时分从节点本身的来看，它本人是很 ok 的，没有任何成绩。 但是从 别的节点来看，这个 GC 的节点就和出成绩的节点如出一辙，发央求它不回，重试也没有反响。 所以别的节点就会以为它是有成绩的。 从这个角度来看，节点本身其实也是很难知道本人能否成绩的。
如今比较盛行判别节点能否有成绩的算法都是基于少数的决策，比如说我有5个节点，那么大家一同来投票，假设有超过一定数量的节点（普通来说超过半数，这里就是有三个节点）以为它有成绩，那么我们就以为这个节点是真的有成绩。哪怕这个节点本身是没有成绩的，但是只需有少数以为有成绩，我们就以为它有成绩。这里运用少数来决议是由于少数就意味着不会有抵触，由于一个系统中不能够存在两个少数，只能够有一个。
Leader和Lock为什么我们要去判别一个节点能否有成绩呢？理想上，在散布式系统中，有很多场景会运用到一个只能一个的概念，比如：
一个数据库partition中只能有一个节点是leader
为了避免同时写，只能有一个transaction或许client允许hold 某个object的lock。
一个用户名只能由用户注册，由于它必须独一。
这些场景都需求我们在设计的时分小心一点，比如说即使一个节点以为它本人是这个选中的独一（比如以为它本人的leader，以为它拿到这个object的lock等等），也能够大少数别的节点以为它有成绩，这个时分假设设计不好的话，就会出成绩，我们来看下面这个例子：
这个例子中，我们为了避免有多个client拜访异样的数据，会要求每个client在写之后要先抓一下锁。这个锁是一个lease的锁，就是超时会释放的。这里你可以看到Client1首先央求了这个锁，但是很不幸，在拿到这个锁之后，它立刻发作了一个GC，而这个GC发作的时分超过了lease的timeout，这就招致这个锁在lease超时之后被释放了，而client2就拿到了这个锁，做了一个更新。而client1在GC回来之后以为它是拿着这个锁的，所以它直接也去写了，这个时分就出现成绩了。这里的成绩就是GC回来之后，client1错误地以为它本人还是拿着锁的。
Fencing Tokens那么如何处置下面这种错误认知呢？一个常见的技术是fencing。如下图所示：
这里做的改动就是每次我们去拿锁的时分会前往一个token值给client，这个token每次拿到锁的时分都会递增。这样在client写的时分必须同时把这个token也发送回来。这样一来storage就可以可依据这个token来判别能否reject旧的token的写。
一个常见的完成方式就是运用ZooKeeper的TransactionID或许node version来作为fencingToken。
拜占庭成绩（ByzantineFaults）上文中说的FencingToken有一个前提，就是client发过去的token是它真正收到，你可以想象假设client在写的时分发送的token是一个假的token，那么显然fencingToken就也会有成绩了。所以关于散布式系统来说，假设有节点说谎，那么成绩就会变得愈加复杂，我们称这种状况为拜占庭成绩，也就是我们常说的拜占庭将军成绩。
我们可以复杂以为在一个有拜占庭成绩的系统中，能够会有那么一两个节点给出的音讯是不牢靠的。这种不牢靠能够是由于:
机器的memory或许CPU registry中的数据由于一些缘由出了成绩。比如说我们读registry的时分出错了，就前往一个default值，或许恣意的值等等。
比如说有一些cheat或许attack发作。这种状况下节点就是不可信的。
当然，在理想中，我们以为这种不可信的成绩它发作在比较少的节点，而不是大少数或许一切。所以假设有任何不可信的事情发作在少数节点上（比如有个code的bug，总是把收到的token加一个随机数），那么相应的算法也是没有办法处置这个成绩的。
增加谎言的存在虽然我们以为有谎言的节点是很少的。但是假设我们可以有一些机制去探测或许保护节点，那显然会更好，比如：
网络的包，我们会加一些checksum来检测它能否正确。
对用户的输入值加一些反省，比如看能否在一个合理的范围内。
NTP的客户端衔接多个地址，然后看majority的反应来决议真实的时间等。
系统模型和理想我们设计了很多算法来处置各种散布式系统中的成绩。而这些算法都是基于一系列的软件和硬件对的，也就是说有很多假定，而这些依赖就是我们俗称的系统模型。
比如说我们谈到时间假定，下面这三种就是常见的系统模型：
同步模型所谓同步模型就是指你知道网络延时，process的暂停和时钟的漂移不会超过某一个限制值。当然不是说没有网络延时，只是说你知道它不会超过一个界限。当然这种模型其真实理想中是不理想的，由于总有预料之外的延时会发作。
部分同步模型所谓部分同步模型就是我们以为大少数时分是同步模型，就是不会超过一定的限制，但那是有时还是会超过这些限制。这个就是一个比较理想的模型。
异步模型这种模型就是不做任何假定，甚至连时钟多不信任，比如不是用超时。限制这种模型的限制就十分大。
除了下面的关于时间的假定，还有一个比较常见的成绩就是节点失败的假定，通常有下面这三种模型：
Crash-stop错误这种模型下，算法以为一个节点出成绩了，比如不照应了，就再也不会回来了。
Crash-Recovery错误这种模型下，算法以为一个节点出成绩了，它一会还会回来。当然什么回来不知道。这就要求节点能够需求一些可以常见保存的介质，比如很多东西写到磁盘中去，这样即使crash了之后还能恢复。
拜占庭错误节点有能够发作任何事情，就像我们下面说的那样。
我们在理想中最常见的模型就是部分同步的crash-recovery错误。那么散布式系统的算法如何运用这些模型呢？
算法的正确性我们判别算法的正确性的时分，需求运用一些属性来判别。比如一个从小到大的排序算法，输入中的两个不同的元素就需求满足前面的比前面的小。这就是一个最复杂的判别办法。
异样的，那么我们如何判别散布式系统中的算法能否正确呢？我们还是以下面那个拿锁为例，我们可以有下面这些属性来停止判别：
独一性没有任何两个央求失掉的token是一样的。
单调递增假设央求x的token是tx，央求y的token是ty，x在y前面，那么tx<ty。
牢靠性假设有节点发送了央求，那么只需不crash它最终都能收到response。
安全和生机 (责任编辑：admin)