分布式系统

第一章1、分布式系统是若干独立计算机的集合，这些计算机对于用户来说就想是单个相关的系统。 这个定义包含了两个方面的内容：第一方面是关于硬件的：机器本身是独立的。第二个 方面是关于软件的：对用户来说他们就像在与单个系统打交道。这个两个共同阐明了分布式 系统的本质，缺一不可。2、分布式系统的重要特性：第一、各种计算机之间的差别以及计算机之间的通信方式的差 别对用户是隐藏的。同样，用户也看不到分布式系统的内部组织结构。第二、用户和应用程 序无论在何时何地都能够以一种一致和统一的方式与分布式系统进行交互。3、为了使种类各异的计算机和网络都呈现为单个的系统，分布式系统常常通过一个“软件 层”组织起来，该“软件层”在逻辑上位于由用户和应用程序组成的高层与由操作系统组成 的底层之间，这样的分布式系统有时又称为中间件。4、如果一个分布式系统能够在用户和应用程序面前呈现为单个计算机系统，这样的分布式 系统就称为透明的。5、透明性说明访问隐藏数据表示形式的不用以及资源访问方式的不同位置隐藏资源所在位置迁移隐藏资源是否移动到另一个位置重定位隐藏资源是否在使用过程中移动到另一个位置复制隐藏是否对资源进行复制并发隐藏资源是否由若干相互竞争的用户共享故障隐藏资源的故障和恢复6、缓存是复制的一种特殊形式，二者之间的区分通常很难划定。缺点，一致性问题。第二章 体系结构1、图识别 分层体系结构；组件组成不同的层，其中上一层的组件可以调用下面的层。 基于对象的体系结构；每个对象对应一个组件，这些组件是通过过程调用机制来连接的。 以数据为中心的体系结构； 基于事件的体系结构。进程基本上是通过事件的传播来通信的，事件的传播还可以有选择 的携带数据。2应用分层：用户接口层；处理层；数据层。第三章 进程1、进程一般定义为执行中的程序，也就是当前在操作系统的某个虚拟处理器上运行的一个 程序。2、线程与进程不同的是，如果要取得高度的并发透明性会导致性能降低的话，那么线程就 不会有这样的企图。3、多线程的优点：在只拥有单线程的进程中，一旦执行了造成阻塞的系统调用，整个进 程就被阻塞了；在多处理器系统上执行多线程程序的时候，可以使用并行操作技术。4、程序间协作是通过进程间通信（IPC）机制实现的。所以IPC机制都有一个主要的缺陷， 就是其中的通信需要开销庞大的上下文切换。（P50）5、线程创建的开销主要取决于为线程堆栈的建立而分配内存的开销。销毁线程的工作主要 是释放线程堆栈所占用的内存，因为线程销毁后它将不会再使用这些内存。6、采用用户级线程库的好处：创建和销毁线程的开销很小；可以通过为数不多的几条 指令来实现线程上下文切换。 缺陷：对于起阻塞的系统调用的调用将会立即阻塞该线程 所属的整个经常，也就阻塞了所属进程中的所以其他线程。 一种解决方法是采用用户级线 程和内核级线程的混合形式，一般称为轻量级进程（LWP）。7、如果LWP找到一个可运行的线程，它就将上下文切换到该线程。（P52）8、以多线程客户的模式来开发游览器，只要取得了主HTML文件，就可以激活多个独立的 线程，它们分别负责取得页面的各个部分。9、构建服务器的三种方式模型特征多线程并行，使用会导致阻塞系统调用单线程进程非并行，使用会导致阻塞的系统调用有限状态机并行，使用非阻塞系统调用10、许多分布式系统利用客户端解决方案来实现复制透明性。（P61图）11、服务器有几种不同的组织结构。迭代服务器自己处理请求，并且在必要的情况下将响 应返回给发出请求的客户；并发服务器并不是自己处理请求，而是将请求传递给某个独立 线程或者其他进程来处理，自身立即返回并等待下一个输入的请求。多线程服务器就是并发 服务器的一个特例。12、状态无关服务器不保存其客户的状态信息，而且也不将自身的状态变化告知任何客户。 Web服务器就是状态无关的第四章 通信1 、中间件协议 调整后的网络通信模型应用层应用协议6 中间件层中间件协议5传输层传输协议4 网络层网络协议3 数据链路层数据链路协议2物理层物理协议12、对于持久通信，提交传输的消息一直由通信中间件存储，直到该消息被传送给接收方为 止。3、对于瞬间通信，通信系统只有在发送和接收应用程序运行时才存储。4、异步通信的特征是，发送方在提交要传输的信息后立即往下进行。这意味着消息在提交 后立即由中间件存储起来。5、对于同步通信，发送方将被阻塞，直到知道其请求被接受以后。6、同步通信发生时基本有三点：发送方可能被阻塞，直到中间件通知它请求传输已完成； 发送方为同步化，直到其请求被传送给目标接受方；通过让发送方一直等到其请求被完 全处理，也就是说，直到接受方返回一个响应，就可以实现同步化。7、远程过程调用：当机器A上的进程调用机器B上的进程时，A上的调用进程被挂起，而 B 上的被调用进程开始执行。调用放可以通过使用参数将信息传送给调用方，然后可以通过 传回的结果得到信息。8、远程过程调用包含下列步骤： 、客户过程以正常的方式调用客户存根； 、客户存根生成一个信息，然后调用本地操作系统； 、客户端操作系统将信息发送给远程操作系统； 、远程操作系统将消息叫给服务器存根； 、服务器存根叫参数提取出来，然后调用服务器； 、服务器执行要求的操作，操作完成后将结果返回给服务器存根； 、服务器存根将结果打包成一个信息，然后调用本地操作系统； 、服务器操作系统将含有结果的消息发送回客户端操作系统； 、客户端操作系统将消息交给客户存根； 、客户存根将结果从消息中提取出来，返回给调用它的客户过程。 所以这些步骤总的效果是，将客户过程对客户存根发出的本地调用转换成对服务器过程的本 地调用，而客户和服务器都不会意识到有中间步骤的存在。9、区分同异步RPC没有阻塞异步RPC。（P96）10、X/开放传输接口的缩写XTL,他的正式名称是传输层接口。11、套接字是一种通行端点。12、程序的硬件独立性的需要最终导致了消息传递方面标准的出台。该标准称为消息传递接 口（并行计算）。13、面向流的通信的典型特征是，它并不在乎通信究竟在哪个确切时间发生。虽然系统可能 会运行的过快或者过慢，但是同步对通信的正确性没有影响。第五章 命名系统1、如果要对实体进行操作，就需要访问实体，因此需要一个访问点。在分布式系统中，访 问点是另一种特殊类型的实体。访问点的名称称为地址。2、一个实体可以提供多个访问点。3、地址就是一种特殊类型的名称：它指向实体的访问点。4、用来唯一标识实体的名称。真正的标识符是具有以下属性的名称： 、一个标识符最多引用一个实体。 、每个实体最多由一个标识符引用。 、一个标识符始终引用同一个实体（也就是说，标识符永远不会重新使用）。5、在因特网地址解析协议中，广播原理用于在仅仅指定IP地址的情况下查找机器的数据链 路地址。6、转发指针的原理：当实体A移动到B时，它将在后面留下一个指针，这个指针指向它在B 中的新位置。 优点：一旦找到实体以后，客户就可以顺着转发指针形成的链来查找实体 的当前地址。缺点：、如果不采取特殊措施，那么链可能会特别长，以致定位实体的开销会变得很大；、只要需要，链中的所有中间位置就必须维护它们的那一部分转发指针 链；、是它所在链很脆弱，易断开。不管是什么原因，只要有一个转发指针丢失，就无法 再到达实体。因此，一个重要的事情就是让指针链相对短一些，并且确保转发指针是健壮的。7、名称空间（P141）8、在迭代名称解析中，名称解析程序把完整的名称转发给根名称服务器。在使用递归名称解析时，名称服务器会把结果传递给它找到的下一台服务器。9、基于属性的命名系统又称为目录服务，而支持结构化命名的系统通常称为命名系统。10、轻量级目录访问协议（LDAP）。（P158）第六章 同步化1、当一个系统又N台计算机时，所有N个晶体都降一略微不同的速度震动导致时钟逐渐不 同步，当同时读这些时钟值时，将得到不同的值。这种时间值的不同称为时间偏移。2、时间同步算法（P172）；3、逻辑时钟（P176）；4、向量时钟，Lamport逻辑时钟导致分布式系统中的所有事件都要经过排序以具有这样的 性质：如果事件 a 在事件 b 之前发生，那么 a 也应该排在 b 之前， C（a）C（b）;5、Lamport时间戳不能捕获因果关系。因果关系可以通过向量时钟来捕获。6、互斥算法的两种不同类型：基于令牌的解决方法和基于许可的方法。7、基于令牌的解决方法的特性：按照进程的组织结构，可以很容易地确保每个进程都有 机会访问资源。避免了饥荒。由于简单，可以很容易避免死锁。 缺陷：如果令牌丢失， 就需要重新开启一个复杂的分布式进程，以确保创建一个新的令牌，但总之，这也是唯一的 一个令牌。8、集中式算法、非集中式算法、分布式算法、令牌环算法。9、四种互斥R算法的比较算法每次进/出需要的消息数进入前的延迟（按消息数）问题集中式32协作者崩溃非集中式3mk,k=1,2,2m会发生饥饿，效率低分布式2 (n-1)2(n-1)任何进程崩溃令牌环1到无穷大0n-1令牌丢失，进程崩溃10、选举方法的目的是确保发起选举后，当所有的进程都同意选出的新协作者时选举结束。11、传统的选举算法：欺负算法、环算法。（P190）第七章 一致性和复制1、进行数据复制主要出于两个目的：可靠性和性能。2、任何执行结果都是相同的，就好像所有进程队数据存储的读、写操作是按某种序列顺序执行的，并且每个进程的操作按照程序做制定的顺序出现在这个序列中，称为顺序一致的。3、所有进程必须一相同的顺序看到具有潜在因果关系的写操作。不同机器上可以以不同的 顺序看到并发的写操作，称为因果一致的。4、如果在一段很长的时间内没有更新操作，那么所有的副本将巨剑地成为一致的。这种形 式的一致性称为最终一致性。5、单调读：如果一个进程读取数据项X的值，那么该进程对X执行的任何后续读操作将总 是得到第一次读取的那个值或更新的值。6、单调写：一个进程对数据项X执行的写操作必须在该进程对X执行任何后续写操作之前 完成。7、读写一致性：一个进程对数据项X执行一次写操作的结果总是会被该进程对X执行的后 续读操作看见。8、写读一致性：同一个进程对数据项X执行的读操作之后的写操作，保证发生在与X读取 值相同或比之前更新的值上。9、基于主备份的协议（P223）。第八章 容错性1、可用性被定义为系统的一个属性，它说明系统已准备好，马上就可以使用2、可靠性是指系统可以无故障的运行。3、安全性是指系统偶然出故障的情况下能正确操作而不会造成灾难。4、可维护性是指发生故障的系统被恢复的难易程度。5、当一个系统不能兑现他的承诺是被认为是失败了。而错误是系统状态的一部分，它可能 会导致失败。故障类型说明崩溃性故障服务器停机，但是在停机之前工作正常遗漏性故障接收故障发送故障服务器不能响应到来的请求 服务器不能接收到来的消息 服务器不能发送消息定时故障服务器的响应在指定的时间间隔之外响应故障值故障状态转换故障服务器的响应不正确 响应的值错误服务器偏离了正确的控制流随意性故障服务器可能在随意的时间产生随意的响应6、如果系统能够经受K个组件的故障并且还能满足规范的要求，那么就被称为K容错。如 果这些组件是失败沉默的，那么具有K+1个组件就足够提供K容错。7、要检测进程故障，只有两种方法。进程主动地往其他进程发送“are you alive? “消息， 或者被动地等待来自其他进程的消息。8、RPC系统中发生的5中失败形式：客户不能定位服务器；客户到服务器的请求消息 丢失；服务器在收到请求之后崩溃；从服务器到客户的响应消息丢失；客户在发送请 求之后崩溃。