几个分布式基础算法

几个分布式基础算法本文章来自于阿里云云栖社区摘要：研究生期间分布式课程的小结吧。。。。中间件在分布式系统中的地位和角色为了使种类各异的计算机和网络都呈现为单个的系统，分布式系统常常通过一个“软件层”组织起来，该层在逻辑上位于由用户和应用程序组成的高层与由操作系统组成的低层之间，这样的分布式系统又称为中间件。研究生期间分布式课程的小结吧。。。。中间件在分布式系统中的地位和角色为了使种类各异的计算机和网络都呈现为单个的系统，分布式系统常常通过一个“软件层”组织起来，该层在逻辑上位于由用户和应用程序组成的高层与由操作系统组成的低层之间，这样的分布式系统又称为中间件。中间件层延伸到了多台机器上，且为每个应用程序提供了相同的接口。它的重要的目的是提供一定程度的透明性，也就是一定程度上向应用程序隐藏数据处理的分布性。中间件集分布式操作系统与网络操作系统的优点于一身，既能够具有网络操作系统的可扩展性和开放性，又能够具有分布式操作系统的透明性和与之相关的易用性。分布式系统进程通信，rpc基本原理步骤1.客户过程以正常方式调用客户存根2.客户存根生成一个消息，然后调用本地操作系统3.客户端操作系统将消息发送给远程操作系统，并阻塞客户过程4.远程操作系统将消息交给服务器存根5.服务器存根将参数提取出来，然后调用服务器6.服务器执行要求的操作，操作完成后将结果返回给服务器存根7.服务器存根将结果打成消息包，然后调用本地操作系统8.服务器操作系统将消息发送回客户端操作系统9.客户端操作系统将消息交给客户存根10.客户存根将结果从消息中提取出来，返回给调用进程移动agent特点自主性；反应性；主动/面向目标；推理/学习/自适应能力；可移动性；社会性。命名服务(优缺点)移动实体定位1.广播和多播2.转发指针3.给实体指定一个起始位置4.创建一颗搜索树并发，petri网建模哲学家进餐图解：h-hungerk-thinkingf–fork/chopsticke-eating1.圆圈：hi,ki,ei,fi为库所h：表示为哲学家饥饿状态库所:k表示为哲学家思考状态的库所e:表示为哲学家吃饭状态的库所f:表示筷子处于备用状态的库所2.黑色实心点为token。初始状态时：f0-f4中的是筷子，k0-k4中的是哲学家3.方框为变迁初始状态：筷子备用状态，处于f0-f4库所中。哲学家是思考状态，处于k0-k4中。以哲学家0为例T1变迁1（感到饥饿）：哲学家在思考中感到饿了，从库所k0经过T1到达库所h0。哲学家从思考状态进入饥饿状态。T2变迁2（获得筷子）：哲学家和筷子分别从h0，f4，f0库所经过T2迁移到库所e0。哲学家从饥饿状态进入吃饭状态。T3变迁3（释放筷子）：吃完饭后，哲学家经过T3迁移到k0库所中，从吃饭状态转入思考状态。两只筷子经过T3，分别迁移到库所f0，f4，从使用状态进入备用状态。生产者消费者移动mogent通信失效（本地和异地）的解决方案分析o无论本地通信还是异地通信，其通信模型是一致的o通信失效本质上都是因为在路由信件和实际信件传输过程中，目标agent发生了物理位置的变化，而这种变化是随机的，不可预计的。结论o通信失效现象并不是mogent系统特有的现象.它是一个因agent的移动而带来的可能会出现在任意一个移动agent系统中的普遍现象其它系统的处理oAglets：未见oMole：o将失效信件扔弃;o扔弃的同时回送错误信息o将失效信件就地保存,待被通信agent在回送时交付根本原因：o移动：随机改变位置信息o通信：要求位置信息“暂时”不变o通信和移动所共享的“位置”信息未进行同步控制是造成通信失效的根本原因o从OS进程互斥考虑，接收者的“位置”在通信失效问题中具有决定性的意义，当通信和移动相矛盾时，该“位置”就成为了一个必须互斥使用的“资源”“位置”的互斥＝》“状态”的互斥在一个能够避免通信失效的移动agent系统中，必须且只要做到以下三条：o准确纪录agent的状态信息o只能向一个处于“静止态”的agent发送信件o信件发送过程中必须限制接收者从“静止态”向“移动态”的状态转换同步：逻辑时间算法，向量时间戳（将每个时间的向量时间戳标出）Lamport算法：不能反应因果关系。向量时钟：要求能计算出每个进程中的事件，标出向量的时间戳，不同事件之间的向量时间的大小关系，依赖关系与并发关系。逻辑时钟为了同步逻辑时钟，Lamport定义了一个称作“先发生”(happens-before)的关系。表达式ab读作“a在b之前发生”，意思是所有进程一致认为事件a先发生，然后事件b才发生。这种先发生关系有两种情况。o如果a和b是同一个进程中的两个事件，且a在之前发生，则ab为真。o如果a是一个进程发送消息的事件，而b为另一个进程接收消息的事件，则ab也为真。消息不可能在发送之前被修改，也不能在发送的同时被接收，这是因为消息需要一定时间才能到达接收端。oLamport逻辑时间钟具有传递性和并发性；对这个算法稍作补充就可以满足全局时间的需要。即在每两个事件之间，时钟必须至少滴答一次。如果一个进程以相当快的速度发送或者接受两个消息，那么它的时钟必须在这之间至少滴答一次。在某些情况下还需要一个附加条件，即两个事件不会精确地同时发生。为了达到这个目标，我们可以将事件发生所在的进程号附加在时间的低位后，并用小数点分开。这样，如果进程1和进程2中的事件都发生在时刻40，那么前者记为40.1后者记为40.2。使用这种方法，我们现在有了一个为分布式系统中的所有事件分配时间的方法，它遵循下面的规则：o若同一进程中a在b之前发生，则C(a)C(b)。o若a和b分别代表发送一个消息和接收该消息的事件，则C(a)C(b)。o对于所有不同的事件a和b，C(a)≠C(b)。这个算法为我们提供了一种对系统中所有事件进行完全排序的方法。许多其他的分布式算法都需要这种排序以避免混淆，所以文献中广泛引用此算法。使用Lamport时间戳后，只通过比较事件a和b各自的时间值C(a)和C(b)，无法说明它们之间的关系。换句话所，C(a)C(b)不能说明事件a就是在事件b之前发生。还需要另外一些信息。即Lamport时间戳不能捕捉因果关系(causality)。向量事件戳为什么采用向量时间戳可以表示事件因果关系？因果关系可以通过向量时间戳来捕获。分配给事件a的向量时间戳VT(a)具有下列性质：如果对某一事件b，有VT(a)VT(b)，那么认为事件a在因果关系上处于事件b之前。向量时间戳的创建是通过让每个进程P维护一个向量V来完成的，该向量具有下面两个性质：oVi[i]是到目前为止进程Pi发生的事件的数量。o如果Vi[j]=k，那么进程Pi知道进程Pj中已经发生了k个事件o第一个性质是通过在进程Pi中的新事件发生时递增Vi[i]来维护的。o第二个性质时通过在所发送的消息中携带向量来维护的。当进程Pi发送消息m时，它将自己的当前向量作为时间戳vt一起发送。使用这种方式，接收者可以得知进程Pi中已经发生的事件数。更重要的是，接收者可以得知进程Pi发送消息m之前其他进程已经发生了多少个事件。换句话说，消息m的时间戳vt告诉接收者其他进程中有多少事件发生在它之前，并且消息m可能在因果关系上依赖于这些事件。当进程Pj接收到消息m时，它调整自己的向量，将每项Vj[k]设置为max{Vj[k],vt[k]}。该向量现在反映了进程Pj必须接收的消息数，该消息数目至少是在发送消息m之前见到的消息。此后将Vj[i]项增1，这表示接收消息m的事件是来自于进程Pi的下一个事件。只在不违背因果关系限制时，才能使用向量时间戳来传递消息。我们来再次考虑一下电子公告板的例子。当进程Pi张贴一篇文章时，它将该文章作为消息a广播出去，并且在该消息上附加一个时间戳vt(a)，其值等于V。当另一个进程Pj接收到a时，它将调整自己的向量，以使Vj[i]=vt(a)[i]。现在假设进程Pj张贴了一个该文章的回复。回复是通过该进程广播一个消息r实现的，消息r携带值等于Vj的时间戳vt(r)。注意vt(r)[i]vt(a)[i]。假设通信是可靠的，包含文章的消息a和包含回复的消息r最终都到达了另一个进程Pk。因为我们没有对消息的顺序关系做出假设，所以消息r可能在消息a之前到达进程Pk。进程Pk接收到消息r时检查时间戳，并决定推迟提交消息r，直到因果关系上位于r之前的消息都接收到了才提交。消息r只有下列条件满足时才得到交付：vt(r)[j]=vk[j]+1;对于所有满足i¹j的i和j，vt(r)[i]Vk[i]第一个条件说明r是进程Pk正在等待的下一条来自进程Pj的消息。第二个条件说明当进程Pj发送消息r时，进程Pk只看到被进程Pj看到的消息。这意味着进程Pk已经看到了消息。一致性模型，要能写出以客户为中心的四个模型（条件描述）以数据为中心的三种类别（了解））1.每一个以客户为中心的一致性模型是单调读的一致性模型。如果数据存储满足以下条件，那么称该数据存储提供单调读一致性(monotonic-readconsistency)：o如果一个进程读取数据x的值，那么该进程对执行任何后续读操作将总是得到第一次读取的那个值或更新的值。也就是说，单调读一致性保证，如果一个进程已经在t时刻看到x的值，那么以后他不再会看到较老的版本的x的值。2.在很多情况下，写操作以正确的顺序传播到数据存储的所有拷贝是非常重要的。这种性质被描述为单调写一致性。单调写一致性(monotonic-writeconsistency)的数据存储应该满足以下条件：o一个进程对数据项x执行的写操作必须在该进程对x执行任何后续写操作之前完成。3.下面介绍一种与单调写一致性有密切关系的以客户为中心的一致性模型。如果数据存储满足以下条件，那么称该数据存储提供写后读一致性(read-your-writesconsistency)。o一个进程对数据项x执行一次写操作的结果总是会被该进程对x执行的后续读操作看见。也就是说，一个写操作总是在同一进程执行的后续读操作之前完成，而不管这个后续的读操作发生在什么位置。4.最后一种以客户为中心的一致性模型是这样的模型，即更新是作为前一个读操作的结果传播的。如果数据存储满足以下条件，那么称该数据存储提供读后写一致性(writes-follow-readsconsistency)。o同一个进程对数据项x执行的读操作之后的写操作，保证发生在与x读取值相同或比之更新的值上。也就是说，进程对数据项上x所执行的任何后续的写操作都会在x的拷贝上执行，而该拷贝是用该进程最近读取的值更新的。代码迁移（基础、分类）分布式系统中的代码迁移是以进程迁移(processmigration)的形式进行的，在这种形式下整个进程被从一台机器搬到另一台机器上去。其基本的思想是：如果把进程由负载较重的机器上转移到负载较轻的机器上去，就可以提升系统的整体性能。（迁移的是计算程序本身，而非数据）分类弱可迁移性：在这种模型中，可以只传输代码段以及某些初始化数据。弱可移动性的典型特征是，传输过来的程序总是以初始状态重新开始执行的。强可移动性(strongmobility)：它还可以迁移执行段。强可移动性的典型特征是，可以先停止运行中的进程，然后将它搬到另一台机器上去，再从刚才中断的位置继续执行。分类（主动方）：发送者启动(sender-initiated)迁移：在这种模型中，代码当前驻留在哪台机器上或者正在哪台机器上执行，就由该机器来启动迁移。一般来说，在向计算服务器上载程序时进行的就是发送者启动的迁移。接收者启动(receiver-initiated)迁移：代码迁移的主动权掌握在目标机器手中。Java小程序是这种迁移的一个例子。事务提交：2pc\3pc1.两阶段提交协议(2PC)：考虑一个分布式事务中有很多进程作为参与者，每个进程都运行在不同的机器上。假定没有故障发生，协议就由以下两个阶段组成，每个阶段又由两步组成。o协调者