分布式总结

进行数据复制主要出于两个目的：可靠性和性能。数据一旦被复制，就会带来一致性的问题。以数据为中心的一致性模型：1.严格一致性（strictconsistency）：对于数据项x的任何读操作将返回最近一次对x进行写操作的结果所对应的值。严格一致性是限制性最强的模型，但是在分布式系统中实现这种模型代价太大，所以在实际系统中运用有限。2.顺序一致性：任何执行结果都是相同的，就好像所有进程对数据存储的读、写操作是按某种序列顺序执行的，并且每个进程的操作按照程序所制定的顺序出现在这个序列中。也就是说，任何读、写操作的交叉都是可接受的，但是所有进程都看到相同的操作交叉。顺序一致性由Lamport（1979）在解决多处理器系统的共享存储器时首次提出的。3.因果一致性：所有进程必须以相同的顺序看到具有潜在因果关系的写操作。不同机器上的进程可以以不同的顺序看到并发的写操作（Hutto和Ahamad1990）。假设P1和P2是有因果关系的两个进程，例如P2的写操作信赖于P1的写操作，那么P1和P2对x的修改顺序，在P3和P4看来一定是一样的。但如果P1和P2没有关系，那么P1和P2对x的修改顺序，在P3和P4看来可以是不一样的。4.FIFO一致性：在因果一致性模型上的进一步弱化，要求由某一个使用者完成的写操作可以被其他所有的使用者按照顺序的感知到，而从不同使用者中来的写操作则无需保证顺序，就像一个一个的管道一样。相对来说比较容易实现。5.弱一致性：要求对共享数据结构的访问保证顺序一致性。对于同步变量的操作具有顺序一致性，是全局可见的，且只有当没有写操作等待处理时才可进行，以保证对于临界区域的访问顺序进行。在同步时点，所有使用者可以看到相同的数据。6.释放一致性：弱一致性无法区分使用者是要进入临界区还是要出临界区，释放一致性使用两个不同的操作语句进行了区分。需要写入时使用者acquire该对象，写完后release，acquire-release之间形成了一个临界区，提供释放一致性也就意味着当release操作发生后，所有使用者应该可以看到该操作。7.入口一致性：入口一致性要求每个普通的共享数据项都要与某种同步变量关联。数据存储满足下列条件，那么它符合入口一致性：在一个进程获取一个同步变量签，所有由此同步变量保护的共享数据的更新都必须已经由相应进程执行完毕。、在一个进程对一个同步变量的独占访问被允许前，其他进程不可以拥有这个同步变量，也不能以非独占方式拥有这个同步变量、、一个进程对一个同步变量执行独占访问之后，对该同步变量的所有者进行检查之前，任何其他的进程都不能执行下一个独占访问。以客户为中心的一致性模型：1.最终一致性：最终一致性指的是在一段时间内没有数据更新操作的话，那么所有的副本将逐渐成为一致的。例如OpenStackSwift就是采用这种模型。以一次写多次读的情况下，这种模型可以工作得比较好。2.单调读：如果一个进程读取数据项x的值，那么该进程对x执行的任何后续读操作将总是得到第一次读取的那个值或更新的值3.单调写：一个进程对数据x执行的写操作必须在该进程对x执行任何后续写操作之前完成。4.写后读：一个进程对数据x执行一次写操作的结果总是会被该进程对x执行的后续读操作看见。5.读后写：同一个进程对数据项x执行的读操作之后的写操作，保证发生在与x读取值相同或比之更新的值上时钟：在一般意义上指的是一个计算机的物理时间，每个计算机都会包括他们自己的物理时钟，不同的计算机的物理可能会不同。时钟漂移：经过在同个地方的计算机，他们的物理也有可能会不一样，如果他们从刚刚开始相同的时间计时开始，过了1过月，1年也可能会有快又慢，这在专业名词上讲叫做时间漂移。本质的原因是每秒的时间偏移，经过日记月累之后，就会有可能达到1秒钟的差距，解决的办法很简单，就是过一段时间之后，将时间纠正回来就可以了。UTC：全称是CoordinatedUniversalTime，协调世界时，又称世界统一时间，用来进行高进度时间的同步。协调世界时以原子时秒长为基础，在此时刻上尽量接近于世界时的一种时间计量系统。同步物理时间：主要手段分为2个Externalsynchronization，靠的是UTC协调世界时，给定一个边界值D0,满足条件|S(t)-Ci(t)|D,另外1个是Internalsynchronization,同样给定时间边界D，相互之间进行同步，|Ci(t)-Cj(t)|D。同步系统中的时间同步：我们首先在一般情况下进行考虑，比如2个进程，相互之间只允许进行消息传递来进行通信，如何进行事件同步，假设传输的时间为T(trans)，假设发送进程P1发送的时间为t,则P2的时间应该设置成t+T(trans),这个很好理解，基于这个思路继续，发送的传输时间一般不可能是固定的，可能受网络环境的影响或快或慢，所以定义了传输的时间上界u(max)，下界u(min)，则此时的抵达时间应该设置成t+(max+min)/2，Cristian时钟同步方法：利用了时间服务器，连接上设备并且能够接受从UTC资源发来的信号进行同步，以UTC的时间作为同步的时间。定义一个进程p，一个TimeServers，请求消息为M(r)，接收消息M(r)，M(r)中包含了从时间服务器中获取的最新的时间，进程p记录了收发的总延时T(round)，则进程p接收到消息后，他的时间应该是p(t)=M(r)中的时间t+T(round)/2TheBerkeleyAlgorithm：用的是Internalsynchronization的方法，给定一组计算机，选出一个作为Coordinator，作为master，这个master选择机器中将要被同步的机器，叫做slave,通过计算与这些机器之间进行时间交换，平均快的和慢的时间，最终达到时间一致性，在比较的过程中，就可以排除明显偏差大的时间了。TheNetworkTimeProtocol：Cristian和Berkeley算法都是偏向于用于小规模的内网中，而NetworkTimeProtocol则是一种在因特网上的分布式时间服务。他定义了TimeService的结构。NTP有下面几个特点。1、NTP提供了一个客户端可以从网络中精准同步UTC时间的客户端。2、服务端通过接口的形式方便客户端的调用。3、NTP服务器与服务器之间的时间同步是以层级控制的方式构成。1级节点同步2个2级节点，2（1）可能又同步2个3级节点，2(2)也可能2个3级节点。其中的时间交互协议通过信息之间的交换。逻辑时间和时钟：逻辑时间，从字面上理解当然不同于物理时间，在分布式系统中，运用逻辑时间的例子也不少，假设L(i)表示的是消息事件的发生事件，当p1进程接收到的时候，就需要对时间做递增操作，L(i)=L(i)+1，逻辑意义上的时间增加。全局有序逻辑时间--VectorClock：VectorClock是向量时钟，可以可以保证全局有序的逻辑时间，通过Vt1,t2,t3....ti保存了Pi进程的当前进行到的时间，当进程Pi接收到相应的消息事件时，则在对应的位置上ti上进行ti=ti+1的操作，当做VectorClock向量比较的时候，需要对V每个位置上进行比较，如果V1中的ti全部小于V2中的ti时，才算事件1早于事件2发生。MapReduce模式的主要思想是将自动分割要执行的问题（例如程序）拆解成Map（映射）和Reduce（化简）的方式，流程图如下图1所示：在数据被分割后通过Map函数的程序将数据映射成不同的区块，分配给计算机机群处理达到分布式运算的效果，在通过Reduce函数的程序将结果汇整，从而输出开发者需要的结果。MapReduce一个软件架构，是一种处理海量数据的并行编程模式,用于大规模数据集（通常大于1TB）的并行运算。MapReduce实现了Map和Reduce两个功能:Map把一个函数应用于集合中的所有成员，然后返回一个基于这个处理的结果集,Reduce对结果集进行分类和归纳,Map()和Reduce()两个函数可能会并行运行，即使不是在同一的系统的同一时刻。MapReduce借鉴了函数式程序设计语言的设计思想，其软件实现是指定一个Map函数，把键值对(key/value)映射成新的键值对(key/value)，形成一系列中间结果形式的key/value对，然后把它们传给Reduce(规约)函数，把具有相同中间形式key的value合并在一起。文件存储位置：源文件：GFSMap处理结果：本地存储Reduce处理结果：GFS日志：GFS单词计数：Step1:自动对文本进行分割Step2:在分割之后的每一对key,value进行用户定义的Map进行处理，再生成新的key,value对Step3:对输出的结果集归拢、排序(系统自动完成）Step4:通过Reduce操作生成最后结果MapReduce的容错Worker故障：Master周期性的ping每个worker。如果master在一个确定的时间段内没有收到worker返回的信息，那么它将把这个worker标记成失效重新执行该节点上已经执行或尚未执行的Map任务重新执行该节点上未完成的Reduce任务，已完成的不再执行Master故障：定期写入检查点数据、从检查点恢复1、系统容错的一些要求：（1）可用性（availability）用来描述系统在给定时刻可以正确的工作。（2）可靠性（reliability）指系统在可以无故障的连续运行。与可用性相反，可靠性是根据时间间隔而不是任何是可以来进行定义的。如果系统在每小时中崩溃1ms，那么他的可用性就超过99.9999%，但是它还是高度不可靠的。与之相反，如果一个系统从来不崩溃，但是要在每年8月中停机两个星期，那么它是高度可靠的，但是它的可用性只有98%。因此，这两种属性并不相同。（3）安全性（safety）指系统偶然出现故障的情况下能正确操作而不会造成任何灾难。4）可维护性（maintainability）发生故障的系统被恢复的难易程度。2、故障分类：故障通常被分为暂时的（transient）、间歇的（intermittent）和持久的（permanent）。3、使用冗余来掩盖故障：如果系统是容错的，那么它能做的最好的事情就是对其他进程隐藏故障的发生。关键技术是使用冗余来掩盖故障。有三种可能：信息冗余、时间冗余和物理冗余。信息冗余中，添加额外的位可以使错乱的位恢复正常。例如可以在传输的数据中添加一段Hamming码来从传输线路上的噪声中恢复数据。关于利用信息冗余进行错误检测和纠正，将在后续内容中叙述。时间冗余中，执行一个动作，如果需要就再次执行。使用事务就是这种方法的一个例子。如果一个事务中止，那么它就可以无害的重新执行。当错误是临时性或间歇性时，时间冗余特别有用。TCP/IP协议中的重传机制，是另外一个例子。物理冗余中，通过添加额外的装备或进程使系统作为一个整体来容忍部分组件的失效或故障成为可能。物理冗余可以在硬件上也可以在软件上进行。其中，一种著名的设计是TMR（三倍模块冗余，TipleModularRedundancy）。在包括TMR的系统中，每个关键模块中的部件都被复制了三份，采用多数表决的方法，确保当某些某块中的单个部件发生故障时，系统还可以正确的运行。人们已经研究出两种基本的策略用于错误处理过程。一种方法是在信息块中包含足够的冗余信息，以便推断出这些数据中肯定有哪些内容，即使用纠错码的策略。另一种也是包含一些冗余信息，但是这些信息只能推断出发生了错误，却推断不出发生了哪些错误，即使用检错码的策略。使用纠错码的技术通常也被称为前向纠错。现在的研究结果中，Chord、Pastry、CAN和Tapestry等常用于构建结构化P2P的分布式哈希表系统（DistributedHashTable，DHT）。DHT的主要思想是：首先，每条文件索引被表示成一个(K,V)对，K称为关键字，可以是文件名（或文件的其他描述信息）的哈希值，V是实际存储文件的节点的IP地址（或节点的