分布式系统中的一致性和重复性

Tanenbaum将分布式系统定义为“分布式系统是一组独立的计算机，它们看起来像是一个用户的单一、连贯的系统”，在“分布式系统原理和范式”当中。
区块链，通过构建一个全球性的分布式系统，试图实现分散的新的数据存储和组织结构。
首先，面向分布式系统的原因主要是可扩展性、局部性和可用性。区块链也不例外。地理可扩展性，以形成用于信息保护的全局值存储网络/位置，包括非集中式结构/零停机时间的可用性下的防篡改。这些都是用分布式系统实现的。
1.引言（一致性概述和一致性原因）
在分布式系统中，数据主要是为了“可靠性”和“性能”而复制的。复制是必需的，特别是如果分布式系统需要在数量上和地理上增长。复制是缩放技术中的一种。此外，它还可以应对数据损坏和副本崩溃。
此时，需要保持数据和副本的状态的一致性。然而，这直接导致可扩展性问题。当你考虑一致性时，理想的情况是“保持所有副本处于完全相同的状态和操作”，即，实现了原子性，但这是一个相当大的挑战。
在现实中，我们不能解决可扩展性问题，除非我们放弃一些一致性约束。因此，有必要了解系统需要多少一致性，以及如何实现一致性的程度。
在本章中，副本之间的一致性将按以下顺序解释。
有什么样的一致性模型？
关于复制管理
-何时何地进行复制
-谁放置伺服器（客户端）？服务器？）
如何保证拷贝之间的一致性
特定一致性协议实例及实现
2.以数据为中心的一致性模型
传统上，主要从数据（数据存储）来讨论一致性。
在分布式系统中，每个进程都保存自己的本地副本。此时，包括每个本地副本的存储数据集合被称为分布式数据存储。

当进程从数据存储中读取时，它期望最后写入操作的结果作为数据返回。为了阐明哪一个是最后一个写，我们把序关系称为一致性。

如第1节所述，几乎不可能保持完全一致性。允许某种程度的不一致导致兼容性与性能，但它取决于你的应用程序，你可以容忍什么，你可以容忍多少。你应该根据应用程序、系统选择一个一致性级别。因此，有必要首先理解什么样的一致性存在。
顺序一致性是最流行和最重要的一致性模型。偶然一致性是其弱变量。
2–1.序列一致性
当满足以下条件时，数据存储顺序一致。
任何执行序列的结果是，所进程到数据存储区的读/写操作与以特定顺序特定顺序执行的结果相同，并且各个进程的操作按其进程所指定的顺序执行。
关键在于，当比较每个过程的操作时，它们处于完全相同的顺序。
在下面的图中，（a）顺序一致，但是（b）不是因为处理P3和处理P4中的读数顺序不同。具体而言，在P3中，P1将由处理P2的写入结果的值r（x）b改变为值r（x）a，但在P4中相反。

W(x)a表示写入数据“x”的值“a”，R(x)b表示从数据“x”读取值“b”。
2–2．偶然一致性
当满足以下条件时，数据存储是偶然一致的。
潜在因果关系的写入必须按所有进程以相同的顺序来观察。对于不同的机器，可以以不同的顺序观察并发写入。
换句话说，它减少了序列一致性的约束，并且没有因果关系的处理序列可以处于不同的顺序。
此时，每个操作取决于哪些操作（其中两个操作是否具有因果关系）非常重要，为此，使用“向量时间戳”是有效的。
在下面的图中，在上面的图中，由于值“b”和值“c”的写入是并行操作，因此它满足因果一致性。

2–3．入口一致性
首先，准备同步变量。通过获取同步变量并仅允许具有同步变量的进程更新数据，还可以保持一致性。这就是所谓的“条目一致性”。
为了保持条目的一致性，同步变量在独占模式访问时不应该有两个所有者，比如写入。在可读但不可写的非排他模式中，多个进程可以同时拥有同步变量。
在下面的图中，由于Process2不拥有对数据项“y”的访问权（=同步变量），所以读取结果变成NIL。

此时，如何正确地关联数据和同步变量成为一个问题。在面向对象的情况下，可以通过隐式地将同步变量与每个对象相关联来实现。
3.以客户为中心的一致性模型
最终一致性和以客户为中心的一致性模型
一般来说，过程之间的不一致在某种程度上是可以接受的。例如，在Web缓存中，响应客户机的缓存页面可能比实际存在的Web服务器版本要旧。然而，对于许多用户来说，这种不一致在某种程度上是可以接受的。
即使如上所述的不一致，随着时间的推移，所有的副本也将逐渐变得一致。这种形式的一致性被称为最终一致性。
只有客户端总是访问相同的副本，最终一致的数据存储才正常工作。然而，如果移动用户在短时间内移动和访问不同的副本，又会怎样呢？例如，如果你使用Express， 客户端将在短时间内移动到另一个位置并访问不同的副本，但是在这里，除非已经传播了之前完成的更新，否则它看起来是不一致的。

对于上述问题，引入以客户为中心的一致性是一种解决方案。与前一节中的以数据为中心的一致性模型不同，该模型旨在保证单个客户端的一致性。
单调阅读
下面的句子是满足单调阅读一致性的条件。
如果进程读取数据项x，则该进程对x的任何后续读取要么使用相同的值进行应答，要么使用更新的值进行应答。
在下面的图中，在(b)中，不能保证写入操作WS(x1)的内容包含在L2的读取结果中，因此不存在单调的读取一致性。

无论何时在任何地方连接到邮件服务器，都保证在访问服务器时直到最后一次都可以读取的所有邮件在目的地读取。
单调令状
下面的句子是满足单调写作一致性的条件。
通过一个进程到数据项X的写入操作在同一进程的任何后续写入到X之前完成。
单调写入一致性类似于以数据为中心的FIFO一致性。FIFO一致性的本质是以相同的顺序进行写入操作，其顺序是正确的。在单调写入一致性中，它是相同的顺序约束，但是仅针对单个进程，而不是并发进程集合。

读写你编写的文章
以下句子是在写作后满足阅读一致性的条件。
通过对同一过程的后续读取操作，总是观察到对数据项X的写入操作的结果。
也就是说，写入操作总是在相同进程执行的后续读取操作之前完成，而不管在哪里完成。

示例1：在更新网页之后，新浏览器内容将始终显示在浏览器中。
示例2：当密码被更新时，保证更新的密码可以在你移动到的地方使用。
写后续阅读
以下句子是阅读后满足写作一致性的条件。
通过对同一过程的后续读取操作，总是观察到对数据项X的写入操作的结果。

4. 复制管理
到目前为止，我们已经详细地解释了一致性的类型。在本节中，我们将解释复制安排、放置副本的位置、时间、时间和方式，以及如何实现一致性。
复制放置有两种类型：
1. 复制服务器放置问题
2. 内容放置问题
4–1.复制服务器布局问题
对于服务器放置问题，有一种方法基于客户端和服务器之间的距离来安排它。距离可以通过传输延迟和带宽来测量。选择一个服务器是很好的，使得服务器和客户端之间的平均距离最小化。
作为另一种选择，有一种考虑网络拓扑的方法。将服务器放置在具有最大网络接口数（即链路）的路由器上是很好的方法。
它们的问题是大量的计算复杂度。它不能容忍在“闪光云”（一个特定地点的突然爆炸请求）时的计算。此时，有一些解决方案来提高效率，例如通过划定区域寻找最接近的区域。
4–2.内容复制与布局
关于内容，三种不同类型的副本被区分和组织，如下图所示。

永久复制品
这是组成分布式数据存储区的初始副本集。在许多情况下，永久性复制品的数量很小。
服务器启动副本
通过启动数据存储区所有者生成的用于提高性能的数据存储的副本。动态放置复制意味着动态地将性能需要改进的文件复制到Web托管服务中的服务器。

例如，对于纽约的web服务器，如果在远离服务器的某个意外位置的客户端几天内请求的数量爆炸性的增加，则临时在该区域放置副本是有效的。
客户端启动副本
这通常被称为客户端缓存。这仅用于改善对数据的访问时间。当需要读取相同的数据时，将副本仅保存在客户端有限时间的缓存函数是有效的。
4–3．内容分发
复制管理还包括将更新内容传递到复制服务器（如何更新）。
要传播的信息类型
实际传播的信息有三种可能性。
只传播通知更新
将更新数据从一个副本发送到另一个副本
将更新操作传播到其他副本
1通知的传播是通过无效通知协议来完成的。你只能注意到副本信息不再有效。有利地，它使用很少的网络带宽，并且当副本不需要频繁更新时使用它。
2是在副本之间传输更新的数据。更新往往更有效和实用。
3只通知应该执行什么类型的更新操作。此时，可以假设每个副本始终具有保持数据最新的能力，因此一致性从1得到改进。
拉与推
有两种方法的更新传播，拉和推。
当读/写比率高时，效率更好，因为当从服务器推送更新时，保持一致性。
另一方面，当读写比低时，高更新频率会浪费带宽等资源，因此拉动更合适。
推拉有以下特点。

*轮询：用于平滑地链接多个设备和软件的控制方法之一，用于主系统询问其他系统是否存在定期间隔的方法。
单播与多播
通过使用组播，可以有效地实现基于推送的方法。相反，单播是基于拉的方法最有效的解决方案。
5．一致性协议
在这一节中，我们将具体检查具体的协议。
5–1．基本基础协议
主要基础协议通常用于实现顺序一致性。在该协议中，与项目X相关联的主服务器负责地执行其写入操作。
主要基础协议有两种方式。
・确认主服务器到特定服务器的方法
・在将主服务器移动到启动写入操作的服务器之后执行写操作的方法
5–1–1．远程写入协议
所有的写入操作被传输到固定的单个主服务器并执行。在远程写协议（主备份协议）中，它直接实现了顺序一致性，因为主服务器可以按照全局唯一时间顺序对所有写进行排序。

(然而，该协议具有相对长的等待时间的性能问题，这通过采用非阻塞方法得到改进，但是是更新可靠性的折衷。)
5–1–2.本地写协议
一种移动权限的协议，以便运行写操作的服务器可以作为主副本操作。它被应用到许多分布式存储系统中。

5–2。复制写协议
在主基本复制中，对一个副本执行写操作，但是在复制写协议中，对多个副本执行写操作。
复制的写协议有两种方式，
・主动复制协议将操作指令传输到所有副本
・基于多数表决的一致性协议
5–2–1 主动复制协议
每个副本具有执行更新操作的过程，并且执行写入操作。此时，所有RePCAS必须以相同的顺序执行操作。
利用Lamport时钟的全序组播可以实现订购，但是很难将规模扩展到大型分布式系统，通常使用中央协调器或定序器来实现全序化。
5–2–2 恒基协议
这是用投票实现的复制操作。基本上，在执行数据项的读写之前，向多个复制服务器发出操作请求许可，并且当获得许可时执行该操作。
此时，如果N是服务器的数量，NR是读取常数，NW是写入常数，那么我们有以下限制：
1。NW+NR> N
2。NW> N／2
当满足这两种情况时，可以防止阅读和写作比赛和写作比赛。这两个常数根据每个读/写的频率进行优化。
5–3 缓存一致性协议
与前两个不同的是，一致性由客户端控制，而不是服务器。缓存一致性协议可以分为几种设计方法。
首先，根据检测不一致的情况，可以将其划分如下。
・在交易期间访问缓存的数据项时验证一致性的情况
・你希望交易在验证数据项时继续进行的情况。
・只有在交易提交时才验证一致性。
接着，根据副本之间保持一致性的方法，将其划分如下。
・更新时，服务器总是使所有缓存无效。
・当简单地传播更新时
在许多情况下，更新操作仅由服务器完成，并且更新由客户端从拉基传播。
还有一种类似于主基本地写协议的方法，它允许客户端修改缓存的数据。该方法用于分布式文件系统，称为写通缓存方法。此时，为了保证顺序一致性，客户端需要保留独占的写权限。如果延迟更新的电磁波，并在通知服务器之前允许多次写入，则可以进一步提高性能，这称为回写缓存。

6. 区块链的一致性
正如我们提到的，为了在分布式系统中保持过程和数据之间的一致性，需要各种各样的独创性。
通常，在大型分布式系统中保持一致性是一项非常艰难的任务。区块链确实是实现分布式系统的精确机制，但它是一种新技术，通过其将区块连接在链中的基本体系可以实现完全顺序一致性。
6–1 区块链序列一致性
在区块链中，两个交易之间的顺序总是一致的。例如，在比特币的情况下，关于某个比特币的交易的命令，例如A的UTXO转移到B，然后B通过该UTXO向C付款，在每个节点上是一致的。这是由于包含交易的区块在链上连接的特点。此外，这是由于比特币的特性使得对于创建新区块达成了共识，并且除非交易与过去的交易一致，否则不会批准交易。
从上面的特性中可以看出，缺省情况下，对于所有节点中的区块链上的交易，都保持顺序一致性。通过这种方式，可以说区块链通过一种非常简单的机制来实现分布式系统及其一致性。
然而，考虑到链链的一致性更精确，可以说它是相当不一致的一致性。为了进一步考虑，我想首先确认CAP定理。
6–2 CAP定理与区块链
“CAP定理”是Brewer在2000年预测并随后由Gilbert等人制定和验证的分布式系统的性质。CAP定理指出，分布式系统可以满足一致性、可用性和碎片化两个系统，但不能同时满足这三个系统。

在采用PoW作为协商一致算法（如比特币）的许可较少的公共区块链中（详细信息在“区块链比较公共私有联合体类型”的文章中），它处于可用性和分区容忍性的高标准中。即使某些节点出现故障，区块链网络仍然继续移动（可用性），即使网络断开，它也可以通信（分区容忍）。另一方面，在一致性方面则是不完善的。如前节所述，尽管交易的顺序一致性的确是随着时间推移而建立的，但是在PoW.每个小号都在自己的时间广播，当他们找到一个随机数和更新到最新的状态，所以频繁的叉子发生。将其应用于CAP定理，我们在一定程度上选择了可用度和划分容限和牺牲一致性。
然而，随着时间的推移，它的一致性将变得更加确定。尽管没有终结性的事实仍然被当作一个问题来讨论，即使讨论仍在进行中，它是一个极好的系统，它随时间保持完全的顺序一致性，并且还具有抗篡改性。这就是为什么区块链技术在当今世界越来越受到关注的原因之一。
Seth Gilbert和Nancy Lynch。Brewer猜想和一致性、可用性、可区分性的Web服务的可行性。
6–3 区块链与复制管理
正如我们在本文中提到的，在运行分布式系统时，复制管理的问题很重要；在何时、由谁来管理复制，应采取何种机制来确保复制之间的一致性。那么，如何在连区块链中进行复制管理呢？
首先，关于副本服务器放置问题。通常，在考虑服务器布局问题时，我们发现最有效的布局是基于通信集中的位置等。然而，诸如比特币之类的区块链正在进行非集中式管理，这取决于每个参与者是否以全部节点的形式加入网络。也就是说，难以全面灵活地安排系统。
那么，副本之间的更新内容的分布是如何操作？正如我们所提到的，在更新时信息传播的可能性有三种。
1. 只传播通知更新
2. 将更新数据从一个副本发送到另一个副本
3. 将更新操作传播到其他副本
在区块链中，为了防止分叉或篡改，希望所有节点尽可能保持网络上的最新信息。此外，因为只有最长的链条被认为是合法的链，所以设计一个激励结构，使所有矿工能够快速捕获最新区块的信息，以便尽快找到下一个现值。由于上述原因，在区块链中，更新数据本身在副本之间传输，并且尽快执行更新内容的交换。也就是说，“传播更新操作到其他副本”是区块链中所选择的方法。
此外基本上，非集中式系统区块链，通过P2P通信来执行。组播主要用于区块链网络中的P2P通信。
首先，当矿工发现一个临时值时，立即对所有网络参与者执行基于推送的多播。矿工在收集来自其他验证器的确认之后，通过尽快通知矿工自己找到的新的区块，试图创建新区块而得到报酬。
新加入网络的节点和断开连接并重新加入的节点执行基于拉的多播以同步网络的最新信息。为了防止表单被欺骗而受到双重篡改等，客户端试图尽可能地获取最新数据，同时试图尽可能地与多个节点通信。
此外，对于可靠的完整节点，存在基于拉协议的单播客户端，并捕获应用程序中的最新数据。
6–4. 区块链与主基协议
在区块链中，节点分散在世界各地，副本分散在所有区域。在POW一致性的情况下，每个交易都是由第一个找到下一个NoCE的节点新编写的。也就是说，每个交易都有与其相关的主服务器。
由此，我们可以得出结论，用于维护区块链一致性的POW协议被归类为5–1–2中描述的主基协议的本地写协议。在比特币区块链中，作为主服务器的写权限是通过查找PoW的nonce值作为独占控制/领导选择算法获得的；查找头上有N个数字0的散列的nonce值的算法是每个区块的权利。然而，当一个具有同时成为主服务器的权限的节点同时出现时，BooStand会做分叉。
6–5. 区块链和新的复制写协议
另一方面，包括Tendermint在内的各种基于PBFT的协商一致算法没有首先负责地执行更新每个数据的主服务器。它们没有权利为每个应用程序中的其他副本写操作，并且保留该权限仅限于参与协商算法的节点，然而，所有参与节点可以在同一时间段内执行写操作。换句话说，PBFT类型一致性协议接近复制类型的主动复制协议。
主动复制协议的主要挑战之一是难以在所有副本中以相同的顺序执行操作。虽然这可以通过使用Lamport的逻辑时钟执行全序多播来解决，但是因为很难扩大规模，所以通常需要中央协调器的支持。Hyperledger中的PBFT算法与此表单完全相同，值得信任的组织成为管理区块更新顺序的领导者（Order）。
另一方面，Tendermint使用独特的Tenderimint一致性，该一致性引入了三相提交格式，以保持总订单的一致性。为了进一步解释，“在形成区块链的分布式系统中的容错性”是一种全新的革命性的主动复制协议，并且实现了完整性。

来源：MOLD

创业不易，用心坚持，希望您多多支持！

打赏

感谢您的支持，我会继续努力的!

扫码打赏

打开支付宝扫一扫，即可进行扫码打赏哦