搜索
1、分布式系统的定义：分布式系统是若干独立计算机的集合，这些计算机对于用户来说就像单个相关系统。2、分布式系统的特点：各种计算机之间的差别以及计算机之间的通信方式的差别对用户来说是隐藏的；用户和应用程序无论在何时何地都能够以一种一致和统一的方式与分布式系统进行交互。3、分布式系统的目标：分布式系统必须能够让用户方便地访问资源；必须隐藏资源在一个网络上分布这样一个事实；必须是开放的；必须是可扩展的。4、透明性：分布式系统的重要目标之一是将它的进程和资源实际上在多台计算机上分布这样一个事实隐藏起来。如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机的系统，这样的分布式系统就称为透明的。透明性的类型：访问透明性：隐藏数据表示形式的不同以及资源访问方式的不同位置透明性：隐藏资源所在的位置迁移透明性：隐藏资源是否移动到另一个位置重定位透明性：隐藏资源是否在使用过程中移动到另一位置复制透明性：使用资源是否对资源进行复制并发透明性：隐藏资源是否由若干相互竞争的用户共享故障透明性：隐藏资源的故障和恢复5、开放的分布式系统：系统应该符合定义良好的接口、系统应该支持应用程序的可移植性、系统应该容易互操作。6、系统的可扩展性：规模上可扩展、地域上可扩展和管理上可扩展。7、扩展技术：Hidecommunicationlatencies隐藏通信等待时间、Distribution分布技术、Replication/caching复制技术。复制/缓冲：将组件复制并拷贝分布到系统各处；缓冲与复制不同的是，是否进行缓存是由要访问资源的客户决定的，而不是资源拥有者决定。缺点是一致性问题。8、分布式系统类型：DistributedComputingSystems分布式计算系统、DistributedInformationSystems分布式信息系统、DistributedPervasiveSystems分布式嵌入系统，又叫分布式普适系统。9、体系结构样式：根据组件、组件之间相互的连接方式、组件之间的数据交换以及这些元素如何继承到一个系统中。组件是一个模块单元，可以提供良好定义接口，在其环境中是可替换的。10、连接器connector：在组件之间传递通信、使组件相互协调和协作。根据组件和连接器的使用，划分成不同体系结构：分层体系结构、基于对象的体系结构、以数据为中心的体系结构、基于时间的体系结构。11、幂等的（idempotent）：某个操作可以重复多次而无害出。有些请求是幂等的，有些不是，不能用某一个解决方法来处理消息的丢失问题。点对点体系结构（P-to-P）1、P2P的一个常见问题是如何高效的定位节点，也就是说，一个节点怎样高效的知道在网络中的哪个节点包含它所寻找的数据。2、DHT的主要思想是：首先，每条文件索引被表示成一个(K,V)对，K称为关键字，可以是文件名（或文件的其他描述信息）的哈希值，V是实际存储文件的节点的IP地址（或节点的其他描述信息）。所有的文件索引条目(即所有的（K,V）对)组成一张大的文件索引哈希表，只要输入目标文件的K值，就可以从这张表中查出所有存储该文件的节点地址。然后，再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上，使得每个节点负责维护其中的一块。这样，节点查询文件时，只要把查询报文路由到相应的节点即可（该节点维护的哈希表分块中含有要查找的(K,V)对）。Chord算法就是解决网络内节点定位问题的一种P2P协议，它通过多个节点跳转找到我们所查找的资源。3、Chord里面的基本要素：节点ID：NID（nodeidentifier），表示一个物理机器；资源ID：KID（keyidentifiers），原为键ID，其实际表示一个资源；Chord环：ChordRing，NID和KID被分配到一个大小为2^m的环上，用于资源分配（给某一个节点）和节点分布，以及资源定位。首先我们说资源分配，资源被分配到NID=KID的节点上，这个节点成为k的后继节点，是环上从k起顺时针方向的第一个节点，记为successor(k)。而节点分布则顺时针将节点N由大到小放在这个环上。现在N26节点要加入系统，首先它指向其后继N32，然后通知N32，N32接到通知后将N26标记为它的前序节点（predecessor）。然后N26修改路由表，下一次N21运行stabilize()询问其后继节点N32的前序节点是不是还是自己，此时发现N32的前序节点已经是N26。于是N21就将后继节点修改为N26，并通知N26自己已经将其设置为后继节点，N26接到通知后将N21设置为自己的前序节点。Chord资源定位（KeyLocation）：资源定位是Chord协议的核心功能这个加入操作会带来两方面的影响：1)正确性方面：当一个节点加入系统，而一个查找发生在stabilization结束前，那么此时系统会有三个状态：A.所有后继指针和路由表项都正确时：对正确性没有影响。B.后继指针正确但表项不正确：查找结果正确，但速度稍慢（在目标节点和目标节点的后继处加入非常多个节点时）。2)效率方面：当stabilization完成时，对查找效率的影响不会超过O(logN)的时间。当stabilization未完成时，在目标节点和目标节点的后继处加入非常多个节点时才会有性能影响。可以证明，只要路由表调整速度快于网络节点数量加倍的速度，性能就不受影响。4.Chord节点失败的处理我们可以看出，Chord依赖后继指针的正确性以保证整个网络的正确性。但如图，若N14,N21,N32同时失效，那么N8是不会知道N38是它新的后继节点。为了防止这样的情况，每个节点都包含一个大小为r的后继节点列表，一个后续节点失效了就依次尝试列表中的其他后继节点。可以证明，在失效几率为1/2的网络中，寻找后继的时间为O(logN)4、Chord的特征和应用，特征：去中心化，高可用度，高伸缩性，负载平衡，命名灵活。应用：全球文件系统、命名服务、数据库请求处理、互联网级别的数据结构、通信服务、事件通知、文件共享。第三章：进程1、不同层次提供4个不同界面：①由机器指令组成，可由任何程序及其的软硬件界面；②由机器指令组成，只有特权程序才可激活的软硬件界面；③由操作系统提供的系统调用组成的界面；④由库调用组成的界面，通常形成了所谓的应用程序编程接口。2、虚拟化可采用的两种方式：①构建运行时系统，提供一套抽象指令集执行程序—进程虚拟机；②做成一层完全屏蔽硬件但提供一个人同样指令集的界面—虚拟机监视器。第六章：同步化1、物理时钟：高频振荡器（石英晶体）、计数器和保持寄存器。高频振荡器的每次震荡使计数器减1，档计数器减为0时，产生一个中断，计数器从保持计数器中重新装入初始值。国际原子时间（TAI）.UTC统一协调时间isTAIwithleapseconds.3、Lamport逻辑时钟：为了同步logicalclocks，Lamport定义了一个关系叫做happens-before（先发生），记作a-b意味着所有的进程都agree事件a发生在事件b之前。在两种情况下，可以很容易的得到这个关系：①如果事件a和事件b是同一个进程中的并且事件a发生在事件b前面，那么a-b；②如果进程A发送一条消息m给进程B，a代表进程A发送消息m的事件，b代表进程B接收消息m的事件，那么a-b(由于消息的传递需要时间)。如果事件a和事件b发生在不同的进程，并且这两个进程没有传递消息，那么既不能推到a-b也不能推到b-a，这样的两个事件叫做并发事件三个机器上各自跑着一个进程，分别为P1，P2，P3，由于不同的机器上的quartzcrystal不一样，所以不同的机器上的时钟速率可能是不同的，例如当P1所在的机器tick了6次，P2所在的机器tick了8次。图中，P1给P2发送了消息m1，m1上附带了发送m1时的时钟6，随后P2收到了m1，根据P2接收到m1时的时钟，认为传输消息花了16-6=10个tick，随后，P3给P2发送消息m3，m3附带的发送时钟是60，由于P2的时钟走的比P3的慢，所以接收到m3时，本机的时钟56比发送时钟60小。这是不合理的，需要调整时钟，如图中，将P2的56调整为61，即m3的发送时钟加1。Lamportlogicalclocks的实现：每个进程Pi维护一个本地计数器Ci，相当于logicalclocks，按照以下的规则更新Ci；①每次执行一个事件(例如通过网络发送消息，或者将消息交给应用层，或者其它的一些内部事件)之前，将Ci加1；②当Pi发送消息m给Pj的时候，在消息m上附着上Ci；③当接收进程Pj接收到Pi的发送的消息时，更新自己的Cj=max{Cj,Ci}。向量时钟:Lamportlogicalclocks的问题是：事件a和事件b实际发生的先后顺序不能仅仅通过比较C(a)和C(b)来决定。Lamportlogicalclocks没有capturecausality(因果关系)，而causality可以通过VectorClocks来capture，用VC(a)来表示事件a的VectorClock。有性质：VC(a)VC(b)可以推出事件a发生在事件b之前。为每个进程Pi维护一个向量VC，也就是Pi的VectorClock，这个向量VC有如下属性：①VCi[i]是到目前为止进程Pi上发生的事件的个数；②VCi[k]是进程Pi知道的进程Pk发生的事件的个数(即Pi对Pj的了解)。每个进程的VC可以通过以下规则进行维护(和Lamportlogicalclocks算法类似)：①进程Pi每次执行一个事件之前，将VCi[i]加1；②当Pi发送消息m给Pj的时候，在消息m上附着上VCi(进程Pi的向量时钟)；③当接收进程Pj接收到Pi的发送的消息时，更新自己的VCj[k]=max{VCj[k],VCi[k]}，对于所有的k。因果有序多播一个进程组中，每个进程需要广播消息给其它进程(相当于一个并发更新问题)，一个消息被delivered到应用层，仅当所有的causally发生之前的消息都被收到。假设：Pi给Pj发送消息m，那么Pj可以将消息m交给应用层必须首先满足上面两个条件：①VCj[i]=VCi[i]-1②VCi[k]=VCj[k]forallk≠i第一个条件的意思是指Pj看到了Pi发生的所有的事件(不包括本次发送消息m的时间)；第二个条件意味着，Pj看到了其它的所有的进程看到的事件。以上两个条件说明，对消息m做下一步动作(比如本例中的将消息m交给应用层)之前，所有的m依赖的消息都收到了。4、互斥：①基于令牌的解决方案：拥有令牌这获得使用资源的权限，可以避免饿死和死锁，但令牌可能会丢失；②基于许可的解决方案：获得其他进程的许可来使用资源。集中式算法:保证互斥的实现，且公平，但协调者是故障点，会出现单点崩溃。非集中式算法：扩展集中式协作者，进程每次访问资源需要多于一半的协作者同意即可，解决单点故障。分布式算法：如该进程不想进入临界区，则立即发送OK消息；如该进程想进入临界区，则把自己的request消息时间戳与收到的request消息时间戳相比较。获得大多数进程的许可即可。令牌环算法。四种算法中集中式算法是最简单也最有效的。第七章：一致性和复制进行数据复制主要出于两个目的：可靠性和性能。数据一旦被复制，就会带来一致性的问题。以数据为中心的一致性模型1.严格一致性（strictconsistency）：对于数据项x的任何读操作将返回最近一次对x进行写操作的结果所对应的值。严格一致性是限制性最强的模型，但是在分布式系统中实现这种模型代价太大，所以在实际系统中运用有限。2.顺序一致性：任何执行结果都是相同的，就好像所有进程对数据存储的读、写操作是按某种序列顺序执行的，并且每个进程的操作按照程序所制定的顺序出现在这个序列中。也就是说，任何读、写操作的交叉都是可接受的，但是所有进程都看到相同的操作交叉。顺序一致性由Lamport（1979）在解决多处理器系统的