CMP中Cache一致性协议的验证
摘要： CMP是处理器体系结构发展的一个重要方向，其中Cache一致性问题的验证是CMP设计中的一项重要课题。基于MESI一致性协议，本文建立了CMP的Cache一致性协议的验证模型，总结了三种三种验证方法验证方法——状态列举法、模型检验法和符号状态法，并给出了每一种方法的复杂性分析。关键词： CMP Cache一致性状态列举模型检验符号状态模型
集成电路工艺的发展使得芯片的集成度不断提高，一种新型体系结构——CMP(Chip Multiprocessor ——片上多处理器)应运而生，通过在一个芯片上集成多个微处理器核心来提高程序的并行性。多个微处理器核心可以并行地执行程序代码，具有较高的线程级并行。由于CMP采用了相对简单的单线程微处理器作为处理器核心，使得CMP具有高主频、设计和验证周期短、控制逻辑简单、扩展性好、易于实现、功耗低、子通信延迟低等优点。此外，CMP还能充分利用不同应用的指令级并行和线程级并行，成为处理器体系结构发展的一个主要趋势。
在CMP中，多个处理器核心对单一内存空间的共享使得处理器和主存储器之间的速度差距的矛盾更加突出，因此CMP设计必须采用多级高速缓存Cache，通过层次化的存储结构来缓解这一矛盾。图1给出了共享内存的CMP系统模型系统模型。与常规SMP系统类似，CMP 系统必须解决由此而引发的Cache一致性问题以及一致性验证问题。采用什么样的Cache一致性模型与它的验证方法都将对CMP的整体设计与开发产生重要影响。从CMP中Cache 一致性协议的验证技术的发展来看，目前应用比较广的验证方法有状态列举法[1]、模型检验法[2][3]、符号状态模型法[4]三种。本文结合CMP的特点，建立了基于MESI一致性协议的CMP验证模型，并在此模型基础上分析了这三种验证方法的基本原理，每一种方法的复杂性分析及优缺点。1 Cache一致性协议的建模从本质上看Cache一致性协议是由一些过程组成的，这些过程包括Cache与内存控制器之间交换信息以及对处理器事件做出的反应。因此用有限状态机有限状态机模型来描述Cache一致性协议是一件很自然的事情。Cache一致性协议可以在三种不同的层次上建立验证建模。最高层次是对整个协议行为的抽象，中间层次是在系统/消息传递一级进行抽象，最低层次则是在结构模型一级进行抽象，表1给出了这三个层次的抽象模型的特点[5]。
目前对Cache一致性协议验证研究中，主要是对一致性协议在系统级系统级进行模型抽象。这主要有三方面的原因：首先，在行为级的抽象中把所有的状态转换操作都看作是原子操作是不切合实际的。其次，在行为级层次上进行的验证实际作用不大。最后，由于系统复杂性的急剧增加，在结构模型的层次上验证一个Cache一致性协议是不可行的。在系统级上对Cache一致性协议进行验证具有相对适中的复杂性。在这个层次上，可以通过有限状态机之间的消息传递来描述各个组件间的操作，加深对系统各个组件间相互作用的理解。此外，基于有限状态机的模型使得我们可以应用层次性验证的方法。即首先在系统级的层次上验证协议的正确性，之后就可以进入到更加低级的层次去验证具体的实现了。2 Cache一致性协议的验证方法2.1 系统模型为了重点说明验证方法原理，减少具体验证过程的复杂性，本文所用的验证分析模型由两个相同的处理器组成，每个处理器有一个Cache；每个Cache 有一个Cache行，应用MESI一致性协议。Cache的有限状态机具有四个状态[6]：M：修改状态，E：独占状态，S：共享状态， I：无效状态。图2给出了验证模型，图3给出了MESI 一致性协议的有限状态机。
应该指出，建立只有一个Cache行的系统模型对于大多数的Cache协议验证都是足够的。这是由于协议执行的粒度是Cache行。而对于执行粒度是word的Cache协议，就必须建立起每一个Cache行有几个word的模型，但是验证的基本原理都是相同的。2.2 状态列举法(State
Enumeration) 状态列举法[1][7]研究整个系统的状态空间。首先用有限状态机来描述协议中组件的模型，并定义全局状态由所有组件的状态组成。然后推导系统所有的可达状态，推导过程从一个初始的全局状态出发，进行每一种可能的转换，这将产生出一些新的状态。新的状态如果是第一次出现，将被插入到工作队列，重复这个过程直到再没有新的状态产生为止。在得到所有的可达状态集合后，需要验证对于每一个可达的全局状态。若所有Cache 中的数据都是一致的，即可说明要验证的协议的正确性。在我们的验证模型中，全局状态用(s1,s2)表示，其中s1,s2∈[M E S I]。可以从初始状态(I，I)出发，逐步得到全部可达状态集合。表2给出了所有全局状态，其中有下划线的为不可达状态。在所有可达状态下，Cache 间的数据都是一致的，从而验证了在本文模型下MESI一致性协议的正确性。
由于系统的全局状态是由各个处理器的Cache状态共同组成的。若一个系统有n个处理器，Cache状态有m个，有k个与状态转换有关的操作，那么系统的状态空间大小是mn，有k*mn个状态转换操作。随着处理器数目与Cache协议复杂性的增加，验证工作的工作量也呈指数级增长。由于状态列举法是采用穷举系统状态的方法进行验证，所以其实现复杂性是O(mn)。即使考虑到全局状态之间的等价关系，把等价的状态用一个状态表示，这虽然可以大大减少要验证状态的数目，但其实现复杂性依然是O(mn)。状态列举法的优点是方法的概念比较简单，易于理解和实现；协议的模型可以随着设计的变动而快速的修改，在协议设计初期可以快速地找出设计中的错误；可以方便地用程序设计语言对Cache协议进行建模，并可以应用自动化的工具进行验证。状态列举法的主要不足是随着处理器数目的增加，状态空间会急剧地以指数级膨胀，因此它的适用性被局限在规模较小的系统中。2.3 模型检验法(Model Checking) 模型检验就是验证某个系统的设计是否满足某种规范，系统的规范用时态逻辑公式来刻画。而通过对系统可达状态空间的遍历来证明设计符合规范。验证时的输入是系统设计与要满足的规范。如果给定的模型满足给定规范，那么验证输出为是，否则可以找出违反了规范的反例，通过反例可以了解设计无法满足规范的原因，精确地定位设计缺陷。可以用来刻画模型的规范化语言不是唯一的，这里以CTL(Computation Tree Logic 运算树逻辑)[2]为例来定义模型和进行验证。CTL是常用的布尔命题逻辑(BPL)的扩展，除了支持常规的逻辑操作外，还支持辅助的时序操作和路径操作符。在运算树逻辑中，一条路径是一个无限的状态序列(s0,s1，...)，其中存在着由si到si+1的转换。这种方法首先要得到系统的全局状态图，由系统所有可达的全局状态及状态间的转换操作构成。图4给出了我们的验证模型的全局状态图。要证明系统满足数据一致性的性质用AGf表示，这里f为数据保持一致性的命题。并且要求在系统中的所有路径上的所有状态都要满足命题f。在本例中条件满足，这就说明本文模型下MESI一致性协议的正确性。
除了上面的CTL逻辑以外，还可以用其它的时序逻辑公式来描述Cache协议[3][8]。不同的时态逻辑公式描述方式有所不同，但一般都要先对Cache一致性协议进行抽象，得到一个简单的模型然后再验证。早期模型检验工具采用显式的方法来表示状态空间。由于这种方法的验证过程也是通过对于全局状态空间的遍历实现的，所以也存在着状态空间膨胀的问题。其实现复杂性与状态列举法一样也是O(mn)。尽管后来在符号模型检验[3][9]中采用了将状态空间转化为布尔函数的方法，应用了ORBDD(ordered reduced binary decision diagram)来表示状态空间，存储BDD节点所需要的空间仍然与所表达的系统的规模呈指数关系。模型检验方法的优点在于时序逻辑强大的表达能力，与状态列举法相比，找到满足Cache一致性性质的表达方式要容易得多。模型检验方法的一个主要缺点是建立系统模型的过程非常复杂，经常需要包括一些不必要的协议细节，而且要建立自动检验程序也是很困难的。另外在符号状态检验中BDD的大小对布尔变量的顺序敏感，不同布尔变量顺序对BDD大小影响是显著的。2.4 符号状态模型法(SSM Symbolic State Model) SSM[4][10][11]法与前面讨论的状态列举法的不同在于对全局状态的表示。SSM方法对系统的全局状态进行了
抽象，这种抽象是由以下观察引发的：首先若系统的各个组件的状态机是相同的，则所有处于相同状态的有限状态机可以集成在一起成为一个集成状态。其次在所有协议中，不是通过写更新，就是通过写无效来实现数据的一致性。而处于Shared状态拷贝的具体数目与协议正确性无关，关键是对某一个特定状态存在的拷贝的数目是0、1还是多个，从而可以把全局状态用更抽象的状态来映射，而不深究处于某一个状态的Cache的具体数目。定义如下表示符：0：表示有0个实例；1：表示有且只有一个实例；*：表示0个，1个或者多个实例；+：表示1个或者多个实例。通过这些符号，可以构建复杂状态的简明表示，例如可以用(I+，S*)来表示一个或多个Cache处于无效状态，0、1或者多个Cache处于共享状态。一个系统的全局状态可以用(q1r1，q2r2，...，qnrn)来表示，这里n是Cache有限状态机的状态数目，ri属于[0，1，+，*]。根据其表示的内容，这些表示符号的顺序为1＜+＜*，0＜*。并定义一个状态集S2包含另一个状态集S1的条件为：qr1∈S1，qr2∈S2，有qr1≤qr2，即r1≤r2，其中q为Cache状态，ri属于[0，1，+，*]。包含关系的重要性在于，如果S2包含S1，那么S2所表示的状态是S1所表示的状态的一个超集，只要验证了S2的正确性，就可以不必再去验证S1的正确性。这是因为对于S1所进行的下一次的状态转换所形成的状态集肯定包含在对S2所进行的下一个的状态转换所形成的状态集之中。在SSM中，状态集的产生是与状态列举方法相同的。首先通过当前可以进行的转换产生新的状态，然后是一个聚合过程，把处于相同状态的Cache归为一类，最后再检查包含的情况，对于本文的系统模型，从初始的(I+)状态开始的状态扩张过程，最后形成的状态转换图。可以看出在状态扩张过程结束时，只产生了另外的四种状态：(E，I*)、(M，I*)、(S，I+)和(S+，I*)。在这五个状态中，Cache都是一致的，从而验证了MESI协议的正确性。SSM方法发现协议错误的方法与状态列举法相同。
由于SSM验证方法产生的状态空间与要验证的系统的规模无关，对于协议的验证也与系统的规模无关，这是SSM方法最主要的一个优点，由于全局状态数目比较小，相对于传统的其他方法在状态遍历时的开销要小得多。而且因为它对于不同规模的系统模型做到了100%的覆盖率，验证的结果也是可靠的。其主要不足在于建立的模型过于抽象，另外SSM的状态表达方式也有可能将一些存在错误的状态也引入到可达的集合中，例如(D*，...)和(D，S*)。另外一个缺点就是无法对于组件不同的系统进行验证。本文综述了CMP系统中Cache一致性协议的验证方法。其中状态列举法在概念上是最简单的，但存在着状态空间膨胀的问题。模型检验可以验证任何用时序逻辑表述的性质，但状态空间膨胀的问题也限制了它的应用，而且在具体的程序设计时的工作量也非常大。SSM方法把多个状态用一个抽象后的状态表示，从而大大地缩减了系统的状态空间，而且验证所得到的结果也是可以信赖的，但是并不是所有的协议的状态抽象过程都是直接明了的。这些方法的主要不同在于对协议的建模方法和状态扩张过程中的采用的缩减状态空间的方法。随着CMP的研究的不断发展，在片上集成的处理器数目将越来越多，消息的传递途径也由总线发展为片上网络。如何给出更加适用于CMP结构、且高效易用的Cache一致性验证方法，将是今后CMP的Cache一致性验证问题的研究方向。
分布式设计与开发（二）------几种必须了解的分布式算法 分布式设计与开发中有些疑难问题必须借助一些算法才能解决，比如分布式环境一致性问题，感觉以下分布式算法是必须了解的（随着学习深入有待添加）： ?Paxos算法 ?一致性Hash算法 Paxos算法 1）问题描述 分布式中有这么一个疑难问题，客户端向一个分布式集群的服务端发出一系列更新数据的消息，由于分布式集群中的各个服务端节点是互为同步数据的，所以运行完客户端这系列消息指令后各服务端节点的数据应该是一致的，但由于网络或其他原因，各个服务端节点接收到消息的序列可能不一致，最后导致各节点的数据不一致。举一个实例来说明这个问题，下面是客户端与服务端的结构图： 当client1、client2、client3分别发出消息指令A、B、C时，Server1~4由于网络问题，接收到的消息序列就可能各不相同，这样就可能由于消息序列的不同导致Server1~4上的数据不一致。对于这么一个问题，在分布式环境中很难通过像单机里处理同步问题那么简单，而Paxos算法就是一种处理类似于以上数据不一致问题的方案。 2）算法本身 算法本身我就不进行完整的描述和推导，网上有大量的资料做了这个事情，但我学习以后感觉莱斯利·兰伯特（Leslie Lamport，paxos算法的奠基人，此人现在在微软研究院）的Paxos Made Simple是学习paxos 最好的文档，它并没有像大多数算法文档那样搞一堆公式和数学符号在那里吓唬人，而是用人类语言让你搞清楚Paxos要解决什么问题，是如何解决的。这里也借机抨击一下那些学院派的研究者，要想让别人认可你的成果，首先要学会怎样让大多数人乐于阅读你的成果，而这个描述Paxos算法的文档就是我们学习的榜样。 言归正传，透过Paxos算法的各个步骤和约束，其实它就是一个分布式的选举算法，其目的就是要在一堆消息中通过选举，使得消息的接收者或者执行者能达成一致，按照一致的消息顺序来执行。其实，以最简单的想法来看，为了达到大伙执行相同序列的指令，完全可以通过串行来做，比如在分布式环境前加上一个FIFO 队列来接收所有指令，然后所有服务节点按照队列里的顺序来执行。这个方法当然可以解决一致性问题，但
２００７年第２４卷第１０期微电子学与计算机 １引言 分布式数据库系统在系统结构上的真正含义是指物理上分布、逻辑上集中的分布式数据库结构。数据在物理上分布后，由系统统一管理，用户看到的似乎不是一个分布式数据库，而是一个数据模式为全局数据模式的集中式数据库［１￣５］。 分布式数据库系统包括两个重要组成部分：分布式数据库和分布式数据库管理系统。分布式数据库系统具有位置透明性和复制透明性，使用户看到的系统如同一个集中式系统。分布式数据库系统分为三类：同构同质型ＤＤＢＳ、同构异质型ＤＤＢＳ和异构ＤＤＢＳ。同构同质型ＤＤＢＳ是指各个场地都采用同一类型的数据模型，并且是同一型号数据库管理系统；同构异质型ＤＤＢＳ是指各个场地都采用同一类型的数据模型，但是数据库管理系统是不同型号的；异构型ＤＤＢＳ是指各个场地的数据模型是不同的类型。 分布式结构是相对于集中式结构而言的。从数据处理的角度来说，典型的集中式结构是数据集中存放和处理，用户通过远程终端或通过网络连接来共享集中存放的数据。分布式结构则是将数据及其处理分散在不同场地，各场地各自管理一部分数据，同时又通过网络系统相互连接。各场地的用户除可以访问和处理本地数据外，也可以访问和处理别的场地的数据。分布式数据库是典型的分布式结构。它包括对数据的分布存储和对事务的分布处理。设计一个分布式数据库系统会遇到许多集中式数据库设计中所没有的问题，一致性是其中必须认真对待和解决的主要问题。 ２ＤＤＢＳ的体系结构 ２．１综合型体系结构 综合型体系结构是指在综合权衡用户需求之后，设计出分布的数据库，然后再设计出一个完整的ＤＢＭＳ，把ＤＢＭＳ的功能按照一定的决策分散配置在一个分布的环境中。每个结点的ＤＢＭＳ均熟知整个网络的情况，也了解其它结点的情况。从整体上，各结点组成一个完整的系统，它们之间是靠进程通讯的手段来维持互访连接，如图１所示。２．２联合型体系结构 联合型体系结构是指每个结点上先有ＤＢＭＳ，以此为基础，再建立分布式环境以实现互访连接。若各个结点的局部ＤＢＭＳ支持同一种数据模式和 分布式数据库系统及其一致性方法研究 刘萍芬，马瑞芳，王军 （西安交通大学电信学院，陕西西安７１００４９） 摘要：分布式数据库系统是数据库领域中的一个主要研究方向，数据一致性维护是分布式数据库系统中的一个非常关键的技术问题。在分析分布式数据库系统体系结构的基础上，讨论了两种一致性方法：两阶段提交和复制服务器，并提出一种具有复制服务器的分布式数据库系统的结构框架，它具有有效性和实用性。 关键词：分布式数据库系统；一致性；两阶段提交；复制服务器 中图分类号：ＴＰ３１文献标识码：Ａ文章编号：１０００－７１８０（２００７）１０－０１３７－０３ ＲｅｓｅａｒｃｈｏｆＤｉｓｔｒｉｂｕｔｅｄＤａｔａｂａｓｅＳｙｓｔｅｍａｎｄＤａｔａＣｏｎｓｉｓｔｅｎｃｙ ＬＩＵＰｉｎｇ－ｆｅｎ，ＭＡＲｕｉ－ｆａｎｇ，ＷＡＮＧＪｕｎ （ＣｏｌｌｅｇｅｏｆＥｌｅｃｔｒｏｎｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｔｉｎｇ，Ｘｉ′ａｎＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｘｉ′ａｎ７１００４９，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍｉｓａｍａｉｎｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎｉｎｔｈｅｄａｔａｂａｓｅｆｉｅｌｄ．Ｍａｉｎｔａｉｎｉｎｇｔｈｅｄａｔａｃｏｎｓｉｓ－ｔｅｎｃｙｉｓａｃｒｉｔｉｃａｌｔｅｃｈｎｉｃａｌｐｒｏｂｌｅｍｉｎｔｈｅｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍ．Ｔｈｉｓｐａｐｅｒｄｉｓｃｕｓｓｅｓｔｗｏｍｅｔｈｏｄｓｏｆｍａｉｎｔａｉｎｉｎｇｄａｔａｃｏｎｓｉｓｔｅｎｃｙｂａｓｅｄｏｎａｎａｌｙｚｉｎｇｔｈｅｓｔｒｕｃｔｕｒｅｏｆｔｈｅｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍ，ｗｈｉｃｈａｒｅ２ＰＣａｎｄｒｅｐｌｉｃａｔｉｏｎｓｅｒｖ－ｅｒ．Ｔｈｅｎｔｈｅｐａｐｅｒｐｕｔｓｆｏｒｗａｒｄａｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｆｒａｍｅｗｏｒｋｗｈｉｃｈｈａｖｅｒｅｐｌｉｃａｔｉｏｎｓｅｒｖｅｒｓｔｒｕｃｔｕｒｅ．Ａｎｄｉｔｉｓｅｆｆｅｃ－ｔｉｖｅａｎｄａｐｐｌｉｅｄ． Ｋｅｙｗｏｒｄｓ：ｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍ；ｄａｔａｃｏｎｓｉｓｔｅｎｃｙ；２ＰＣ；ｒｅｐｌｉｃａｔｉｏｎｓｅｒｖｅｒ 收稿日期：２００６－１０－２７ １３７
多处理器Cache一致性分析 [摘要]随着社会不断向前发展，人类对计算速度和计算规模的需求不断提高。而单处理器计算机系统由于处理器运算性能受限于芯片速度极限和加工工艺极限，不可能无限提高。于是超大规模并行处理系统应运而生。但这也引入了一些在单处理器系统中没有出现的问题。在系统中出现的多机存储信息的一致性问题便是当今国际上研究的热门问题之一。为了缓和CPU与存储器之间的速度差距，在计算机系统的CPU与主存之间引入了cache。但在多处理器系统中，由于多个处理器可能对同一数据块进行读写操作，当某个处理器对共享的数据块进行写操作时，其它处理器的cache中该数据块的副本将成为过时的数据。如果不及时地通知相应的处理器，将导致错误的运行结果。本文介绍了Cache的作用，Cache一致性问题的原因及解决这个问题的两种协议。 [关键字]Cache、Cache一致性、监听协议、基于目录的协议 一、Cache简介和工作原理 虽然CPU主频的提升会带动系统性能的改善，但系统性能的提高不仅仅取决于CPU，还与系统架构、指令结构、信息在各个部件之间的传送速度及存储部件的存取速度等因素有关，特别是与CPU/内存之间的存取速度有关。若CPU工作速度较高，但内存存取速度相对较低，则造成CPU等待，降低处理速度，浪费CPU的能力。如500MHz的PⅢ，一次指令执行时间为2ns,与其相配的内存（SDRAM）存取时间为10ns，比前者慢5倍，CPU和PC的性能怎么发挥出来？ 目前最好的方法是在慢速的DRAM和快速CPU之间插入一速度较快、容量较小的SRAM，起到缓冲作用；使CPU既可以以较快速度存取SRAM中的数据，又不使系统成本上升过高，这就是Cache法。 Cache的工作原理是基于程序访问的局部性。 对大量典型程序运行情况的分析结果表明，在一个较短的时间间隔内，由程序产生的地址往往集中在存储器逻辑地址空间的很小范围内。指令地址的分布本来就是连续的，再加上循环程序段和子程序段要重复执行多次。因此，对这些地址的访问就自然地具有时间上集中分布的倾向。数据分布的这种集中倾向不如指令明显，但对数组的存储和访问以及工作单元的选择都可以使存储器地址相对集中。这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象，就称为程序访问的局部性。 根据程序的局部性原理，可以在主存和CPU通用寄存器之间设置一个高速的容量相对较小的存储器，把正在执行的指令地址附近的一部分指令或数据从主存调入这个存储器，供CPU 在一段时间内使用。这对提高程序的运行速度有很大的作用。这个介于主存和CPU之间的高速小容量存储器称作高速缓冲存储器(Cache)。 系统正是依据此原理，不断地将与当前指令集相关联的一个不太大的后继指令集从内存读到Cache，然后再与CPU高速传送，从而达到速度匹配。 CPU对存储器进行数据请求时，通常先访问Cache。由于局部性原理不能保证所请求的数据百分之百地在Cache中，这里便存在一个命中率。即CPU在任一时刻从Cache中可靠获取数据的几率。命中率越高，正确获取数据的可靠性就越大。 在CPU与主存之间增加了Cache之后，便存在数据在CPU和Cache及主存之间如何存取的问题。读写各有2种方式。
基础架构事业群-数据库技术-数据库内核 何登成 Paxos/Raft 分布式一致性算法原理剖析及其在实战中的应用
目录Contents Consensus Problem Basic Paxos Multi-Paxos and Raft 实战分析 参考资料
定义：The consensus problem requires agreement among a number of processes (or agents) for a single data value.
?理解Consensus 问题的关键 ?绝对公平，相互独立：所有参与 者均可提案，均可参与提案的决 策 ?针对某一件事达成完全一致：一 件事，一个结论 ?已经达成一致的结论，不可被推 翻 ?在整个决策的过程中，没有参与 者说谎 ?晚饭吃什么？ 炉鱼食堂同乐会 炉鱼炉鱼 炉鱼 Consensus Algorithm
Consensus Algorithm：Basic Paxos ?Basic Paxos ?一个或多个Servers可以发起提案（Proposers） ?系统必须针对所有提案中的某一个提案，达成一致 ?何谓达成一致？系统中的多数派同时认可该提案?最多只能针对一个确定的提案达成一致 ?Liveness (只要系统中的多数派存活，并且可以相互通信)?整个系统一定能够达成一致状态，选择一个确定的提案
Basic Paxos：Components ?Proposers ?Active：提案发起者（value） ?处理用户发起的请求 ?Acceptors ?Passive：参与决策，回应 Proposers的提案 ?存储accept的提案（value）， 存储决议处理的状态 ?Learners ?Passive：不参与决策，从 Proposers/Acceptors学习最新 达成一致的提案（value）?本文接下来的部分，一个Server同时具有Proposer和Acceptor两种角色，Learner角色逻辑简单，暂时不讨论
智能电能表通信协议（TCP）及功能一致性测试（ETS）与协议标准的探讨 发表时间：2018-03-14T15:13:27.440Z 来源：《基层建设》2017年第34期作者：刘永杰[导读] 摘要：开放式综合设备网络可以满足建筑节能、引进设备控制网络、连接现有的各种电气设备网络协议、通过扩展因特网的方式构建广域建筑设备控制网络等要求。 公诚管理咨询有限公司 520000 摘要：开放式综合设备网络可以满足建筑节能、引进设备控制网络、连接现有的各种电气设备网络协议、通过扩展因特网的方式构建广域建筑设备控制网络等要求。 关键词：通信协议；标准规格；一次性测试；互操作性引言：随着人们对通信要求的增加和通信技术自身的发展，通信网的建构日益成为一个庞大的系统工程。协议在通信网中占有绝对重要的地位，ISO开发的OSI七层协议参考模型为推动通信网的发展作出了很大贡献。但仅仅制定了协议还不够，协议工程概念的提出使得协议的制定、验证实现与测试紧密结合在一起，保证了通信网得以正确有效的运行。在整个协议工程过程中，协议的测试居于最后的阶段，测试的 结果表明通信产品可否满足最初的协议要求，直接影响到产品能否投入使用。因此，协议测试是协议工程的重要组成部分。图1示出协议工程总体概览以及协议测试所处的地位。正是鉴于协议测试的重要性，ISO和IEC共同制定了关于一致性测试方法学和框架的国际标准，这就是IS0/IEC9646系列标准。所谓一致性测试，简言之就是测试协议实现与协议规范标准的符合程度。 1.一致性测试的意图、能力和类型 一致性测试包括测试一个协议实现（protocol implementation）的能力和行为两个方面，同时检查是否有与相关国际标准或CCITT建议中的一致性要求以及实现者所声明的实现能力相违背的地方。一致性测试的意图在于增加不同的OSI协议实现在相互联接时的成功率。但是，从技术和经济上双重考虑，对协议实现进行穷尽测试是不现实的。一个正确的协议实现应该具备协议要求的能力并且行为上与协议表现一致，一致性测试要做的仅在于提高这一可信度。正如前面所言，一致性测试的目的在于判断协议实现是否与协议规范相一致。根据对一致性不同的指示程度，可以将一致性测试分为四种： 1.1 基本互联测试，这类测试目的在于检测严重的不一致情况是否存在，即IUT甚至不能与测试器相联或者没能实现协议的主要特征。 1.2 能力测试，静态一致性要求定义了协议实现所要具备的核心能力集合能力测试按照静态一致性要求进行测试，判断IUT的哪些能力可被观察到并检查这些可观察能力的有效性。 1.3 行为测试，行为测试是标准化的抽象测试集（ATS-Abstraet Test Suite）中的主要组成部分。它覆盖了动态一致性要求的全部，旨在确定协议实现的动态一致性。 1.4 一致性决定测试，这类测试提供尽可能明确的诊断性回答，以断定协议实现是否满足特定要求。一般认为，基本互联测试和能力测试可以作为行为测试的先行，而一致性决定测试是非标准化的，可以作为行为测试的后继补充。 2.抽象测试方法及其比较选择 2.1 在本地测试法中，测试器位于测试系统内部，要求IUT的上层服务边界是标准化的硬件接口，测试协调规程在测试系统中予以完全的实现。该方法仅适于有两个硬件接口的SUT。在这里，测试系统是指包括下测试器实现的一个真实系统。 2.2 分布式方法中，上测试器位于SUT中，上层服务边界应该是人工用户接口或者标准编程语言接口。适用于该法的IUT应该有一个上层接口，该接口能够为人工用户或含标准编程语言接口的软件化上测试器所访问。 2.3 在协调法中，测试协调规程由标准的测试管理协议（TMP-Test M anagement Protoco1）来实现。上测试器实质上是相应TMP的一个实现该法适用于TMP能够在上测试器中得以实现的情况。 2.4 在远程法中，对测试协调规程的要隐含于或非形式化地表述于抽象测试集（ATS—A bstract Test Suite，见下节）中，一般没有上测试器，但某些上测试器的功能需由SUT来执行，适用于可以利用SUT的某些功能来控制IUT而无须上测试器的情况。这四种测试方法见图2。
CMP中Cache一致性协议的验证 摘要： CMP是处理器体系结构发展的一个重要方向，其中Cache一致性问题的验证是CMP设计中的一项重要课题。基于MESI一致性协议，本文建立了CMP的Cache一致性协议的验证模型，总结了三种三种验证方法验证方法——状态列举法、模型检验法和符号状态法，并给出了每一种方法的复杂性分析。关键词： CMP Cache一致性状态列举模型检验符号状态模型 集成电路工艺的发展使得芯片的集成度不断提高，一种新型体系结构——CMP(Chip Multiprocessor ——片上多处理器)应运而生，通过在一个芯片上集成多个微处理器核心来提高程序的并行性。多个微处理器核心可以并行地执行程序代码，具有较高的线程级并行。由于CMP采用了相对简单的单线程微处理器作为处理器核心，使得CMP具有高主频、设计和验证周期短、控制逻辑简单、扩展性好、易于实现、功耗低、子通信延迟低等优点。此外，CMP还能充分利用不同应用的指令级并行和线程级并行，成为处理器体系结构发展的一个主要趋势。 在CMP中，多个处理器核心对单一内存空间的共享使得处理器和主存储器之间的速度差距的矛盾更加突出，因此CMP设计必须采用多级高速缓存Cache，通过层次化的存储结构来缓解这一矛盾。图1给出了共享内存的CMP系统模型系统模型。与常规SMP系统类似，CMP 系统必须解决由此而引发的Cache一致性问题以及一致性验证问题。采用什么样的Cache一致性模型与它的验证方法都将对CMP的整体设计与开发产生重要影响。从CMP中Cache 一致性协议的验证技术的发展来看，目前应用比较广的验证方法有状态列举法[1]、模型检验法[2][3]、符号状态模型法[4]三种。本文结合CMP的特点，建立了基于MESI一致性协议的CMP验证模型，并在此模型基础上分析了这三种验证方法的基本原理，每一种方法的复杂性分析及优缺点。1 Cache一致性协议的建模从本质上看Cache一致性协议是由一些过程组成的，这些过程包括Cache与内存控制器之间交换信息以及对处理器事件做出的反应。因此用有限状态机有限状态机模型来描述Cache一致性协议是一件很自然的事情。Cache一致性协议可以在三种不同的层次上建立验证建模。最高层次是对整个协议行为的抽象，中间层次是在系统/消息传递一级进行抽象，最低层次则是在结构模型一级进行抽象，表1给出了这三个层次的抽象模型的特点[5]。 目前对Cache一致性协议验证研究中，主要是对一致性协议在系统级系统级进行模型抽象。这主要有三方面的原因：首先，在行为级的抽象中把所有的状态转换操作都看作是原子操作是不切合实际的。其次，在行为级层次上进行的验证实际作用不大。最后，由于系统复杂性的急剧增加，在结构模型的层次上验证一个Cache一致性协议是不可行的。在系统级上对Cache一致性协议进行验证具有相对适中的复杂性。在这个层次上，可以通过有限状态机之间的消息传递来描述各个组件间的操作，加深对系统各个组件间相互作用的理解。此外，基于有限状态机的模型使得我们可以应用层次性验证的方法。即首先在系统级的层次上验证协议的正确性，之后就可以进入到更加低级的层次去验证具体的实现了。2 Cache一致性协议的验证方法2.1 系统模型为了重点说明验证方法原理，减少具体验证过程的复杂性，本文所用的验证分析模型由两个相同的处理器组成，每个处理器有一个Cache；每个Cache 有一个Cache行，应用MESI一致性协议。Cache的有限状态机具有四个状态[6]：M：修改状态，E：独占状态，S：共享状态， I：无效状态。图2给出了验证模型，图3给出了MESI 一致性协议的有限状态机。 应该指出，建立只有一个Cache行的系统模型对于大多数的Cache协议验证都是足够的。这是由于协议执行的粒度是Cache行。而对于执行粒度是word的Cache协议，就必须建立起每一个Cache行有几个word的模型，但是验证的基本原理都是相同的。2.2 状态列举法(State
基于Raft分布式一致性协议实现的局限及其 对数据库的风险
普通服务器具有良好的性价比，因此在互联网等行业得到了广泛的应用。但普通服务器也不得不面对2%-4%的年故障率([1])，于是必须高可用的传统数据库只得很悲催地使用性价比低得可怜的高可靠服务器。 分布式一致性协议（distributed consensus protocol）是迄今为止最有效的解决服务器不可靠问题的途径，因为它使得一组服务器形成一个相互协同的系统，从而当其中部分服务器故障后，整个系统也能够继续工作。而Paxos协议([2])则几乎成了分布式一致性协议的代名词。 然而，Paxos协议的难以理解的名声似乎跟它本身一样出名。为此，Stanford大学的博士生Diego Ongaro甚至把对Paxos协议的研究作为了博士课题。他在2014年秋天正式发表了博士论文：“CONSENSUS: BRIDGING THEORY AND PRACTICE”，在这篇博士论文中，他们给出了分布式一致性协议的一个实现算法，即Raft。由于这篇博士论文很长（257页），可能是为了便于别人阅读和理解，他们在博士论文正式发表之前，即2014年初，把Raft相关的部分摘了出来，形成了一篇十多页的文章：“In Search of an Understandable Consensus Algorithm”，即人们俗称的Raft论文。 Raft算法给出了分布式一致性协议的一个比较简单的实现，到目前为止并没有人挑战这个算法的正确性。然而，OceanBase却没有采用Raft算法，这并非是OceanBase团队同学不懂Raft，而是Raft的一个根本性的局限对数据库的事务有很大的风险。 Raft有一个很强的假设是主（leader）和备（follower）都按顺序投票，为了便于阐述，以数据库事务为例： 1）主库按事务顺序发送事务日志 2）备库按事务顺序持久化事务和应答主库 3）主库按事务顺序提交事务
实验七多Cache一致性——监听协议 7.1 实验目的 1.加深对多Cache一致性的理解； 2.进一步掌握解决多Cache一致性的监听协议的基本思想； 3.掌握在各种情况下，监听协议是如何工作的。能给出要进行什么样的操作以及状态的变 化情况。 7.2 实验平台 多Cache一致性监听协议模拟器， 《计算机系统结构实验教程》附书光盘中提供，清华大学出版社。 设计：张晨曦教授（xzhang2000@https://www.doczj.com/doc/2b15002009.html,），版权所有。 开发：程志强。 7.3 实验内容及步骤 首先要掌握该模拟器的使用方法。（见7.4节） 1. 对于以下访问序列，写出监听协议所进行的操作：
4.根据上述结果，画出相关的状态转换图。 C写5号单元
D读5号单元 7.4 监听协议模拟器使用方法 该模拟器模拟4个CPU（A、B、C、D）访存的工作过程。每个CPU中都有一个Cache，该Cache包含4个块，其块地址为0～3。集中共享存储器中有32个块，其块地址为0～31。每个块的状态用色块来表示，其中灰色表示“无效”状态，淡青色表示“共享”，橘红色表示“独占”。 对于每个CPU，可以指定所要进行的访问是读还是写（从列表中选），并在输入框中输入所要访问的主存块号，然后用鼠标点击在其右边的标有↓的按钮，模拟器就将开始演示该访问的工作过程。 该模拟器的主菜单有4个：配置，控制，统计，帮助。 1.配置 该菜单用于进行配置参数的显示与设置。你可以修改动画播放速度：把游标往右边拖拽可提高播放速度，往左边拖拽可降低播放速度。你还可以选择是否进行优化传块。优化传块是指当要访问的块在某个Cache中，且处于独占状态时，可以不用等该块写回主存后再从主存调块，而是可以直接将该块传送给发出访问请求的结点。 本模拟器采用直接映象方法和写回法。 2.控制 可以通过该菜单中的选项来控制模拟器的执行。该菜单下有以下3个选项：单步执行、连续执行、复位。 （1）单步执行
分布式系统一致性与共识的原理 1一致性问题 一致性问题是分布式领域最为基础也是最重要的问题。如果分布式系统能实现“一致”，对外就可以呈现为一个完美的、可扩展的“虚拟节点”，相对物理节点具备更优越性能和稳定性。这也是分布式系统希望能实现的最终目标。 1.1定义与重要性 定义一致性（c o n s i s t e n c y），早期也叫a g r ee m e n t，是指对于分布式系统中的多个服务节点，给定一系列操作，在约定协议的保障下，试图使得它们对处理结果达成“某种程度”的认同。 理想情况下，如果各个服务节点严格遵循相同的处理协议，构成相同的处理状态机，给定相同的初始状态和输入序列，则可以保障在处理过程中的每个环节的结果都是相同的。 那么，为什么说一致性问题十分重要呢？举个现实生活中的例子，多个售票处同时出售某线路上的火车票，该线路上存 在多个经停站，怎么才能保证在任意区间都不会出现超售（同一个座位卖给两个人）的情况呢？ 这个问题看起来似乎没那么难，现实生活中经常通过分段分站售票的机制。然而，为了支持海量的用户和避免出现错误，存在很多设计和实现上的挑战。特别在计算机的世界里，为了达到远超普通世界的高性能和高可扩展性需求，问题会变得更为复杂。 注意一致性并不代表结果正确与否，而是系统对外呈现的状态一致与否；
例如，所有节点都达成失败状态也是一种一致。 1.2问题与挑战
看似强大的计算机系统，实际上很多地方都比人类世界要脆弱得多。特别是在分布式计算机集群系统中，如下几个方面很容易出现问题： ·节点之间的网络通信是不可靠的，包括消息延迟、乱序和内容错误等； ·节点的处理时间无法保障，结果可能出现错误，甚至节点自身可能发生宕机； ·同步调用可以简化设计，但会严重降低分布式系统的可扩展性，甚至使其退化为单点系统。 仍以火车票售卖问题为例，愿意动脑筋的读者可能已经想到了一些不错的解决思路，例如： ·要出售任意一张票前，先打电话给其他售票处，确认下当前这张票不冲突。即通过同步调用来避免冲突； ·多个售票处提前约好隔离的售票时间。比如第一家可以在上午8点到9点期间卖票，接下来一个小时是另外一家……即通过令牌机制来避免冲突； ·成立一个第三方的存票机构，票集中存放，每次卖票前找存票机构查询。此时问题退化为中心化单点系统。 当然，还会有更多方案。实际上，这些方案背后的思想，都是将可能引发 不一致的并行操作进行串行 化。这实际上也是现代分布式系统处理一致性问题的基础思路。只是因为现在的计算机系统应对故障往往不够“智能”，而人们又希望系统可以更快更稳定地工作，所以实际可行的方案需要更加全面和更加高效。 注意这些思路都没有考虑请求和答复消息出现失败的情况，同时假设每个售票处的售票机制是正常工作的。 1.3一致性要求
浅谈并行系统中cache一致性问题和解决方法 班级：0920 姓名：储俊学号：09419022 摘要：高速缓冲存储器一致性问题是指高速缓冲存储器中的数据必须与内存中的数据保持同步(一致) 这个问题常发生在CPU内核与另一个设备异步访问内存时。 关键词：cache一致性，监听CACHE协议，基于CACHE目录的协议 1.Cache一致性问题的发现 本项目的目标板为：处理器采用ARM芯片S3C44B0X，存储器采用2片Flash 和1片SDRAM,在调试的时候输入采用键盘，输出采用显示器，用RS232串口实现通信。 在项目的开发过程中，经软件仿真调试成功的程序，烧入目标板后，程序却发生异常中止。通过读存储器的内容发现，程序不能正常运行在目标板上，是因为存储器中写入的数据与程序编译生成的数据不一致，总是出现一些错误字节。 经过一段时间的调试发现，只要在程序中禁止Cache的使用，存储器中写入的数据将不再发生错误，程序可以正常运行，但速度明显减慢。经过分析，认为问题是由于Cache数据与主存数据的不一致性造成的。 Cache数据与主存数据不一致是指：在采用Cache的系统中，同样一个数据可能既存在于Cache中，也存在于主存中，两者数据相同则具有一致性，数据不相同就叫做不一致性。如果不能保证数据的一致性，那么，后续程序的运行就要出现问题 2．分析Cache的一致性问题 要解释Cache的一致性问题，首先要了解Cache的工作模式。Cache的工作模式有两种：写直达模式（write-through）和写回模式（copyback）。写直达模式是，每当CPU把数据写到Cache中时，Cache控制器会立即把数据写入主存对应位置。所以，主存随时跟踪Cache的最新版本，从而也就不会有主存将新数据丢失这样的问题。此方法的优点是简单，缺点是每次Cache内容有更新，就要对主存进行写入操作，这样会造成总线活动频繁。S3C44B0X 中的Cache就是采用的写直达模式（write-through）。在写直达模式下，数据输出时，系统会把数据同时写入高速缓冲存储器Cache和主存中，这样就保证了输出时高速缓冲存储器的一致性。但该模式下，却无法保证输入时的高速缓冲存储器的一致性。 2.1、产生高速缓存（ Cache ）不一致的三个原因 （1）共享可写数据引起（Sharing of writable data）的不一致 如果处理机 P1将一个新的数据 X`写入高速缓冲器中时，如果采用写通过策略立即将此复本写回共享存储器。在这种情况下，两个高速缓存中的两份复本 X与 X`就不一致了；如果采用写回策略，也会产生不一致性。只用当高速缓存器中修改的数据被替换或变成无效时，主存储器内容才被更新。（2）进程迁移引起的不一致 如果采用写回策略，包含共享变量 X的进程从处理机 P1迁移到处理机 P2时，将会出现不一致性；如果采用写通过策略时，进程从处理机 P2
分布式系统几种典型一致性算法概述 姓名：王昌志学院:电子电气工程学号：M020214105 在分布式系统中，我们经常遇到多数据副本保持一致的问题。在这里，我们通俗地把一致性的问题可分解为2个问题： 1、任何一次修改保证数据一致性。 2、多次数据修改的一致性。 在弱一致性的算法，不要求每次修改的内容在修改后多副本的内容是一致的，对问题1的解决比较宽松，更多解决问题2，该类算法追求每次修改的高度并发性，减少多副本之间修改的关联性，以获得更好的并发性能。例如最终一致性，无所谓每次用户修改后的多副本的一致性及格过，只要求在单调的时间方向上，数据最终保持一致，如此获得了修改极大的并发性能。 在强一致性的算法中，强调单次修改后结果的一致，需要保证了对问题1和问题2要求的实现，牺牲了并发性能。本文是讨论对解决问题1实现算法，这些算法往往在强一致性要求的应用中使用。 解决问题1的方法，通常有两阶段提交算法、采用分布式锁服务和采用乐观锁原理实现的同步方式,下面分别介绍这几种算法的实现原理。 一．两阶段提交算法 在两阶段提交协议中，系统一般包含两类机器（或节点）：一类为协调者（coordinator），通常一个系统中只有一个；另一类为事务参与者（participants，cohorts或workers），一般包含多个，在数据存储系统中可以理解为数据副本的个数。两阶段提交协议由两个阶段组成，在正常的执行下，这两个阶段的执行过程如下所述： 阶段1：请求阶段（commit-request phase，或称表决阶段，voting phase）。 在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。 阶段2：提交阶段（commit phase）。 在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协
cache一致性问题和解决方法 作者 工程技术大学 摘要高速缓冲存储器一致性问题是指高速缓冲存储器中的数据必须与存中的数据保持同步(一致) 。多核处理器将一个以上的计算核集成在一个处理器中，通过多个核心的并行计算技术，增强处理器计算性能。单片多处理器结构(CMP—ChipMultiprocessor)又是该领域中备受关注的问题。本文简要论述了CMP的多级Cache存储结构，多级结构引起了Cache一致性问题，一致性协议的选取对CMP系统的性能有重要影响。使用何种Cache一致性模型以及它的设计方案是本文重点研究的容。 关键词：CMP；Cache一致性；存储器；协议；替换策略 Cache consistency problem and solving method Abstract Cache consistency refers to the data in the cache memory must be synchronized with the data in memory (the same).Multi·core processor was the integration of multiple computing cores on a single processoL which improved processor computing ability through the parallelcomputing Technology of multi-coreprocessors．Single chip multi-processorarchitecture(CMP-ChipMulfiprocessor)was hot spots in this area．The CMPmulti-level Cache storage structure was briefly discussed in this paper,which led to Cache coherence problem，the selection of consistency protocol had a major impact on the performance of the CMP system．The selection of model of theCache Coherence and methods of its design will have a significant impact ofoverall design and development of CMP Key words：CMP Cache; consistency; memory; protocol; replacement strategy 1引言 在过去的二十年中，计算机处理器设计工艺和处理器体系结构发展迅速，计算机也能够完成所赋予它的大部分任务。因此，在各种领域得到迅速和广泛的应用。同时，广泛的应用也带来了对高性能和低功耗处理器的强劲需求。而以往通过在单核处理器中集成更多的晶体管，提升处理器频率的方法，随着摩尔定律和处理器功耗的畸形不对称，使得高频处理器将会带来以往无法预计的功耗问题。多核处理器技术的出现解决了上述问题。
摘要 本文将会从实际应用场景出发，介绍一致性哈希算法（Consistent Hashing）及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景，借此介绍一致性哈希算法以及这个算法如何解决此问题；接下来会对这个算法进行相对详细的描述，并讨论一些如虚拟节点等与此算法应用相关的话题。 分布式缓存问题 假设我们有一个网站，最近发现随着流量增加，服务器压力越来越大，之前直接读写数据库的方式不太给力了，于是我们想引入Memcached作为缓存机制。现在我们一共有三台机器可以作为Memcached服务器，如下图所示。 很显然，最简单的策略是将每一次Memcached请求随机发送到一台Memcached 服务器，但是这种策略可能会带来两个问题：一是同一份数据可能被存在不同的机器上而造成数据冗余，二是有可能某数据已经被缓存但是访问却没有命中，因为无法保证对相同key的所有访问都被发送到相同的服务器。因此，随机策略无论是时间效率还是空间效率都非常不好。 要解决上述问题只需做到如下一点：保证对相同key的访问会被发送到相同的服务器。很多方法可以实现这一点，最常用的方法是计算哈希。例如对于每次访问，可以按如下算法计算其哈希值： h = Hash(key) % 3
其中Hash是一个从字符串到正整数的哈希映射函数。这样，如果我们将Memcached Server分别编号为0、1、2，那么就可以根据上式和key计算出服务器编号h，然后去访问。 这个方法虽然解决了上面提到的两个问题，但是存在一些其它的问题。如果将上述方法抽象，可以认为通过： h = Hash(key) % N 这个算式计算每个key的请求应该被发送到哪台服务器，其中N为服务器的台数，并且服务器按照0 – (N-1)编号。 这个算法的问题在于容错性和扩展性不好。所谓容错性是指当系统中某一个或几个服务器变得不可用时，整个系统是否可以正确高效运行；而扩展性是指当加入新的服务器后，整个系统是否可以正确高效运行。 现假设有一台服务器宕机了，那么为了填补空缺，要将宕机的服务器从编号列表中移除，后面的服务器按顺序前移一位并将其编号值减一，此时每个key就要按h = Hash(key) % (N-1)重新计算；同样，如果新增了一台服务器，虽然原有服务器编号不用改变，但是要按h = Hash(key) % (N+1)重新计算哈希值。因此系统中一旦有服务器变更，大量的key会被重定位到不同的服务器从而造成大量的缓存不命中。而这种情况在分布式系统中是非常糟糕的。 一个设计良好的分布式哈希方案应该具有良好的单调性，即服务节点的增减不会造成大量哈希重定位。一致性哈希算法就是这样一种哈希方案。 一致性哈希算法 算法简述 一致性哈希算法（Consistent Hashing）最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说，一致性哈希将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0 - 232-1（即哈希值是一个32位无符号整形），整个哈希空间环如下：
区块链分布式系统面临一致性问题及共识算法的理论知识解析共识机制已经成为了目前区块链系统性能提升的关键瓶颈。 单一的共识算法均存在各种问题，如PoW算法存在消耗大量计算资源及性能低下的问题，PoS或DPoS存在“富豪统治”问题，融合多种共识算法优势的想法正受到越来越广泛的关注。 分布式系统面临的挑战区块链是一个分布式系统，分布式系统碰到的第一个问题就是一致性问题。 在分布式系统中，一致性是指：对于系统中的多个服务节点，给定一系列操作，在协议（往往通过某种共识算法）保障下，试图使得他们对处理结果达成某种程度的一致。 如果一个分布式系统无法保证处理结果一致的话，那任何建立于其上的业务系统都无法正常工作。 分布式系统面临的主要挑战包括： 1）资源受限：节点间的通信需要通过网络，而网络存在带宽限制和时延，节点也无法做到瞬间响应和高吞吐。 2）故障的独立性：系统的任何一个模块都可能发生故障，如节点之间的网络通讯是不可靠的，随时可能发生网络故障或任意延迟；节点的处理可能是错误的，甚至节点自身随时可能宕机。 3）不透明性：分布式系统中任何组件所在的位置、性能、状态、是否故障等情况对于其它组件来说都是不可见的、也无法预知的。 4）并发：分布式系统的目的，是为了更好的共享资源。同步调用会让系统阻塞，因此节点间通信通常设计成异步的。 5）缺乏全局时钟：在程序需要协作时，它们通过交换消息来协调它们的动作。紧密的协调经常依赖于对程序动作发生时间的共识，但是，实际上网络上计算机同步时钟的准确性受到极大的限制，即没有一个一致的全局时间的概念。这是通过网络发送消息作为唯一的通信方式这一事实带来的直接结果。
对三种典型分布式任务分配算法的分析 在分布式系统中非同居模块间的数据传递产生处理机间的通信, 这种机间通信可能使得 增加处理机数目反而会引起系统吞吐量的降低, 即产生“饱和效应”。为降低饱和效应, 人们 倾向于把模块分配到尽可能少的处理机上, 但这又导致系统负载不平衡, 从而降低了系统的吞吐量。显然, 这是任务分配中相互冲突的两个方面, 不同的任务分配算法试图用不同的策略来平衡这两个方面。 传统的分布式任务分配算法大致可分为三类: 基于图论的分配算法, 整数规划方法和试 探法。这三类算法并非互斥的, 一类算法中往往可以借鉴其它方法中的某些技术。下面, 我们 先对这三类典型算法进行分析和比较, 然后给出一种试探法的改进算法。 在讨论中, 我们假定提交的任务已分解成一组模块并使模块间的通信量尽可能小。还假 定分配模式为: 一任务被分解成m个模块T= { t1 , t2 , …, t m } , 系统中有n个可利用的处理机P= { p1 , p2 , …, p n }。任务分配的目的就是将这m个模块分配到n个处理机上, 使预期的性能目标函数值最小。 1 对三种典型算法的分析 1. 1 基于图论的分配算法 基本思想是给定矩阵C mxm表示模块间的通信开销: C= { c i, j|1≤i≤m& 1≤j≤m& c i, j为t i 与t j 间的通信量} 给定矩阵Q mx n表示模块的执行开销: Q= { q i, j|1≤i≤m& 1≤j≤n& q i, j为t i 在p j 上的执行开销} 将模块t1 , t2 ,…, t m作为图中结点,若两模块间有数据传递,则相应结点间有一条无向边, 1996-04-26收稿* 软件工程国家重点实验室开放基金部分资助。何炎祥, 教授, 研究方向: 分布式OS与分布信息处 理, 并行程序设计与编译系统。罗先林、吴思,研究生, 研究方向: 分布式OS与分布信息处理。 边上的权w i, j= c i, j; 处理机p1 , p2 , …, p n 也作为图中结点, 若q i, k≠∞, 则在t i 与p k 间有一条边, 定义该边上的权为w i, k= 1 n- 1Σj≠k q i, j n- 2 n- 1 c i, k。于是, 可将该图视为一个网络, 并定 义n度割集为将网络中各个结点分割成n个不相交的子集, 使得每个子集中有且仅有一个处理机结点。可以证明, 每个切口的开销正好是执行开销和通信开销之和, 因此, 在图上执行MaxFlow /MinCut算法, 就可得到任务的最优分配方案[1 ]。在现阶段, 仅有多项式复杂度n= 2的MaxFlow /MinCut算法, 因此, 基于图论的分配算法仅限于在处理机数目小于3的环境中使用, 因而局限性较大。 Lo 在[1 ]中提出了一种改进算法。该算法分为迭代、汇总和贪心三个阶段。在第一阶段的每一轮迭代中, 依次考虑每个结点p1 , p2 , …, p n , 把p j 和p j= P- { p j }作为两个独立的结点, 并将所有到P- { p j }的边用一个到p j