分布式系统复习总结.docx

1. 分布式系统定义A distributed system is a collection of autonomous computing elements that appears to its users as a single coherent system.（独立的计算机的集合，对这个系统的用户来说，系统就像一台计算机一样）。2. 分布式系统的目标Making resource availableDistribution transparency(分布的透明性)Openness(开放性)Scalability(可扩展性)包含三个方面：Size: Number of users and/or processes(solution:强大的服务器)Geographical: Maximum distance between nodesAdministrative: Number of administrative domains3. 为什么需要分布式Economics（经济性）微处理器能提供比大型机更好的性价比Speed（速度）分布式系统能提供比大型机更强的计算能力Inherent distribution（固有的分布性）有一些应用包含空间上分离的机器Reliability（可靠性）当某台机器崩溃时，整个系统仍能正常工作Incremental growth（可扩展性）计算能力逐步增加4. 分布式系统透明性含义分布式系统的透明性（Transparency in a Distributed System）定义：对用户和应用程序员屏蔽分布式系统组件的分散性，系统被认为是一个整体，而不是独立的组件集合。透明性对用户和应用程序员隐藏了与手头任务无直接关系的资源，并匿名使用，使得分布的某些特性对应用程序员具有不可见性，这样应用程序员只要关心特定应用的设计问题。(1)网络透明性：用户察觉不出是以网络的方式工作，所有的工作对象是在单台机器上完成。(2)操作系统透明性：使用不同操作系统的机器和用户可以自由的协同工作，不同操作系统带来的不同被掩盖。(3)语言透明性：使用不同语言编写的程序或者模块能够自由交互工作，相互调用。(4)数据复制与分片透明性：分片的数据像未分片的数据一样工作，修改数据时复制在多处的数据自动更新。实现方式Access(访问)Hide differences in data representation and how a resource is accessedLocation(位置)Hide where a resource is locatedMigration(迁移)Hide that a resource may move to another locationRelocation(重定位)Hide that a resource may be moved to another location while in useReplication(复制)Hide that a resource may be shared by several competitive usersConcurrency(并发)Hide that a resource may be shared by several competitive usersFailure(故障)Hide the failure and recovery of a resource透明度(Degree of Transparency)：Aiming at full distribution transparency may be too muchUsers may be located in different continentsCompletely hiding failures of networks and nodes is (theoretically and practically) impossibleYou cannot distinguish a slow computer from a failing oneYou can never be sure that a server actually performed an operation before a crashFull transparency will cost performance, exposing distribution of the systemKeeping Web caches exactly up-to-date with the masterImmediately flushing write operations to disk for fault tolerance5. 分布式系统开放性含义Be able to interact with services from other open systems, irrespective of the underlying environment:Systems should conform to well-defined interfacesSystems should support portability of applicationsSystems should easily interoperateAt least make the distributed system independent from heterogeneity of the underlying environment6. 分布式操作系统、网络操作系统和基于中间件的系统定义分布式操作系统：配置在分布式系统上的操作系统，能够直接对分布式系统中的各种资源进行动态分配，并能有效地控制和协调分布式系统中各任务的并行执行，同时还向用户提供了一个方便的、透明的使用整个分布式系统的界面。网络操作系统：是在网络环境下实现对网络资源的管理和控制的操作系统，是用户与网络资源之间的接口。网络操作系统是建立在独立的操作系统之上，为网络用户提供使用网络系统资源的桥梁。在多个用户争用系统资源时，网络操作系统进行资源调剂管理，它依靠各个独立的计算机操作系统对所属资源进行管理，协调和管理网络用户进程或程序与联机操作系统进行交互。基于中间件的系统：？系统名称系统描述主要目标DOS紧耦合，管理多处理器系统和同构式多计算机系统隐藏和管理硬件资源NOS松耦合，管理异构式多计算机系统向远程客户端提供本地服务Middleware位于NOS通用服务实现层之上的附加层，屏蔽了底层的异构性和具体的通信协议细节，为应用程序员提供方便的编程模型。提供分布透明性7. 分布式系统类型(1)Distributed computing systemsCluster ComputingEssentially a group of high-end systems connected through a LAN:Homogeneous: same OS, near-identical hardwareSingle managing nodeGrid ComputingThe next step: lots of nodes from everywhere:HeterogeneousDispersed across several organizationsCan easily span a wide-area network(2)Distributed information systemsThe vast amount of distributed systems in use today are forms of traditional information systems, that now integrate legacy systems.A transaction is a collection of operations on the state of an object that satisfies the following properties(ACID)Atomicity(原子性)Consistency(一致性)Isolation (隔离性)Durability(持久性)Transaction Processing MonitorIn many cases, the data involved in a transaction is distributed across several servers. A TP Monitor is responsible for coordinating the execution of a transaction.(3)Distributed pervasive systemsEmerging next-generation of distributed systems in which nodes are small, mobile, and often embedded in a larger system, characterized by the fact that the system naturally blends into the users environment.Ubiquitous computing systemsMobile computing systemsSensor (and actuator) networks8. 分布式系统中的机制与策略Requires support for different policies:What level of consistency do we require for client-cached(客户端缓存) data?Which operations do we allow downloaded code to perform?Which QoS requirements do we adjust in the face of varying bandwidth(带宽)?What level of secrecy(保密) do we require for communication?Ideally, a distributed system provides only mechanisms:Allow (dynamic) setting of caching policiesSupport different levels of trust for mobile codeProvide adjustable QoS parameters per data streamOffer different encryption(加密) algorithms9. 分布式系统架构风格(1) Organize into logically different components, and distribute those components over the various machines(2) Decoupling processes in space (“anonymous”) and also time (“asynchronous”) has led to alternative styles10. 分布式系统组织形式(1) CentralizedBasic ClientServer ModelCharacteristics:There are processes offering services (servers)There are processes that use services (clients)Clients and servers can be on different machinesClients follow request/reply model wrtto using services(2) DecentralizedStructured P2P: nodes are organized following a specific distributed data structureUnstructured P2P: nodes have randomly selected neighborsHybrid P2P: some nodes are appointed special functions in a well-organized fashion(3) Hybird11. 客户-服务器模式和对等模式12. MiddlewareIn many cases, distributed systems/applications are developed according to a specific architectural style. The chosen style may not be optimal in all cases need to (dynamically) adapt the behavior of the middleware13. BitTorrentOnce a node has identified where to download a file from, it joins a swarm of downloaders who in parallel get file chunks from the source, but also distribute these chunks amongst each other14. 分布式系统组织为中间件15. 进程和线程的定义及异同进程：An execution stream in the context of a process state线程：A minimal software processor in whose context a series of instructions can be executed. Saving a thread context implies stopping the current execution and saving all the data needed to continue the execution at a later stage.两者区别：线程是轻量级进程，一个进程包含多个线程，共享数据(地址)空间，而进程之间不共享代码和数据空间。进程是分配资源的基本单位，而线程是独立运行和独立调度的基本单位。线程的切换比进程效率高。16. 代码迁移Code segment: contains the actual codeData segment: contains the stateExecution state: contains context of thread executing the objects code代码迁移方法：强迁移和弱迁移(1) 强迁移：Move component, including execution state(2) 弱迁移：Move only code and data segment本地资源：An object uses local resources that may or may not be available at the target site资源类型：(1)Fixed: the resource cannot be migrated, such as local hardware(2)Fastened: the resource can, in principle, be migrated but only at high cost(3)Unattached: the resource can easily be moved along with the objectObject-to-resource binding：(1)By identifier: the object requires a specific instance of a resource(2)By value: the object requires the value of a resource(3)By type: the object requires that only a type of resource is available异构系统上的迁移：(1)Main problemThe target machine may not be suitable to execute the migrated codeThe definition of process/thread/processor context is highly dependent on local hardware, operating system and runtime system(2)Make use of an abstract machine that is implemented on different platformsInterpreted languages, effectively having their own VMVirtual VM (as discussed previously)17. 代码迁移与虚拟迁移比较18. 通信模型远程过程调用、远程方法调用、面向消息的中间件、面向流的通信19. 通信类型(1) 非持久性通信(2) 持久性通信(3) 同步通信(4) 异步通信 20. 远程过程调用(RPC)(1) 工作过程(a) 客户过程以正常的方式调用客户存根；(b) 客户存根生成一个消息，然后调用本地操作系统；(c) 客户端操作系统将消息发送给远程操作系统；(d) 远程操作系统将消息交给服务器存根；(e) 服务器存根调将参数提取出来，而后调用服务器；(f) 服务器执行要求的操作，操作完成后将结果返回给服务器存根；(g) 服务器存根将结果打包成一个消息，而后调用本地操作系统；(h) 服务器操作系统将含有结果的消息发送给客户端操作系统；(i) 客户端操作系统将消息交给客户存根；(j) 客户存根将结果从消息中提取出来，返回给调用它的客户存根。(2) 故障处理(a) Client Cannot Locate the ServerSolution: Use a special code, as the return value of the procedure to indicate failure.Have the error raise an exception or a signal.(b) Lost Request Message或Lost Reply MessageSolution: Kernel starts a timer when sending the message(c) Server crashesSolution: Wait until the server reboots and try the operation again. Give up immediately and report back failure. Client gets no help.(d) Client CrashesSolution: Extermination: Before a client stub sends an RPC, it makes a log entry (in safe storage) telling what it is about to do. After a reboot, the log is checked and the orphan explicitly killed off.Reincarnation: Divide time up into sequentially numbered epochs. When a client reboots, it broadcasts a message declaring the start of a new epoch. When broadcast comes, all remote computations are killed. Solve problem without the need to write disk recordsGentle reincarnation: A variant of previous one, but less DraconianExpiration: Each RPC is given a standard amount of time, T, to do the job. If it cannot finish, it must explicitly ask for another quantum.(3) 动态绑定(采用动态绑定的原因、缺点)目的：the client locate the server(客户端定位服务器)优点：(1) Flexibility(2) Can support multiple servers that support the same interface(3) The binder can verify that both client and server are using the same version of the interface缺点：(1) The extra overhead of exporting/importing interfaces costs time(2) The binder may become a bottleneck in a large distributed system21. 基于消息的通信(1) 持久性和非持久性Transient：The sender puts the message on the net and if it cannot be delivered to the sender or to the next communication host, it is lost. There can be different types depending on whether it is asynchronous or synchronousPersistent：The message is stored in the communication system as long as it takes to deliver the message to the receiver电子邮件、手机短消息属于持久通信QQ属于非持久性通信(2) 同步和异步Synchronous：The sender is blocked until its message is stored in the local buffer at the receiving host or delivered to the receiver.Asynchronous：The sender continues immediately after executing a send. The message is stored in the local buffer at the sending host or at the first communication server.(3) 流数据A (continuous) data stream is a connection-oriented communication facility that supports isochronous data transmission.22. 命名方式(1) Human-friendly name(2) Address(3) Identifier23. 命名需求(1) Usage of unique naming conventions(2) Scalability(3) Consistency(4) Performance and availability(5) Adaptability to change(6) Fault isolation24. 移动实体的定位(1) BroadcastingBroadcast the ID, requesting the entity to return its current address. With respect to distributed objects, when an object move from address space A to B, it leaves behind a proxy in A and install a skeleton that refers to it in B.(2) Forwarding pointersWhen an entity move from A to B, it leaves behind a reference to its new location at B(3) Home-based approachesLet a home keep track of where the entity is:Entitys home address registered at a naming serviceThe home registers the foreign address of the entityClient contacts the home first, and then continues with foreign location25. 命名解析(1) Iterative name resolution(a)Resolve (, 1, , ) sent to Server0 responsible for dir(b)Server0 resolves resolve (,1)1, returning the identification (address) of Server1, which stores dir1.(c)Client sends resolve (, 2,)to Server1, etc.(2) Recursive name resolution(a)Resolve (,1,)sent to Server0 responsible for dir(b)Server0 resolves resolve (,1)1,and sends resolve(dir1,name2,.,nameK) to Server1, which stores dir1.(c)Server0 waits for result from Server1, and returns it to client.26. 同步问题在分布式系统中，如果没有全局统一的时钟，独立的计算机上的时间将各不相同，那么当进程在系统之间传递时，本来需要按照一定顺序执行的进程，有可能会因为目标计算机的时间和源计算机的时间不一致，出现次序错乱的情况，影响系统的运行。因此需要使用时钟同步算法来协调时间。How processes cooperate and synchronize with one another in a distributed systemHow to decide on relative ordering of events27. 时钟同步机制28. 分布式系统的同步与集中式系统有何区别集中式系统：Time is unambiguous分布式系统：Achieving agreement on time is not trivial!29. 逻辑时钟Lamport算法：所有消息都应该携带依据发送者时钟的发送时间，如果接受者的时间稍早，那么调整为比发送时间大1的值。同时规定任意两个事件之间，时钟必须至少产生过一次中断。两个事件允许发生在同一时刻，但是不允许精确同时发生。可以通过如下方法来解决发生在同一时刻的事件问题。向量时间戳30. 分布式系统中的互斥访问(1) 集中式算法：基于上述的选举算法，选出一个进程作为集中协调者，该协调者同时管理一个请求等待队列。当队列为空时，协调者对临界区请求应答。当队列不为空或者临界区尚未释放时，把请求添加到等待队列的队尾，然后或者对请求不予应答，或者直接拒绝（此时该请求会一直查询临界区使用状态），直至从队头取出该请求后再允许其进入临界区。(2) 令牌环算法前提：用软件的方法，按照进程的地址或者编号等，为总线型的网络构造一个逻辑环。一个令牌环只能对应进入一个临界区。过程：令牌环绕进程环依次传递，如果接受进程如果不需要进入临界区，则继续传递给下一个进程，如果接受进程需要进入临界区，那么此时传递暂停，令牌等待，直到进程从临界区返回后继续。缺点：令牌丢失的检测和再生因为无法确定时间间隔而非常困难；进程崩溃虽然可以恢复，但是需要通过每个进程向前继进程发送确认消息来实现，也就需要每个进程都维护当前的配置信息。(3) 分布式算法：前提：根据lamport算法给出时间戳确定事件发生的先后关系；每个进程都需要配置一个请求等待队列。发送进程：想进入临界区的进程用临界区名，自己的进程号和时间戳构造消息，发送给所有进程；接收进程：不在临界区时，也不需要使用临界区时，返回OK消息；在临界区时，不做应答，仅把收到的请求放入队列；不在临界区但是已经请求使用临界区时，把收到的请求和自己发送出去的请求比较时间戳，早者胜出，使用临界区，并把晚者的请求放入队列，晚者向早着发送OK消息。出临界区进程：向队列中所有进程发送OK消息，并清空队列，继续通过比较时间戳竞争临界区。也就是说，在等待的进程请求，一定要放入正在临界区的进程的等待队列中去。缺点：故障可能性比集中式扩大N倍，因此考虑不论同意还是拒绝请求一律发送应答（应答内容不一样）。31. 分布式系统中的选举机制(1)Bully算法发起选举的条件，一是任何进程发现原有协调者崩溃时，可以发起选举；二是原来崩溃的进程P恢复以后，可以重新发起选举，但是最后不一定会赢得选举，因为可能还有编号比P大的进程在P崩溃期间已经开始运行。选举过程：发起选举的进程Q只能向编号比自己大的进程发起election消息；如果Q一直没有接受到OK应答消息，则由Q充当协调者，否则，退出选举。而最终编号最大的进程M在没有受到OK应答以后，向其他所有进程发送coordinator，原来发起选举的Q进程回到发起选举之前的中断处，以M为协调者继续运行，而M尽量接替原来崩溃的协调者的工作。(3) 环算法发起选举的条件：所有进程已经按照编号进行排序并且链接成环，任何一个或者多个进程发现原有协调者崩溃或者没有响应时，开始发起选举。选举过程：发起消息者构造election消息，依次向后传递。传递过程中如果后继进程已经崩溃，则绕过（不仅仅是刚刚崩溃了的协调者），如果后继进程正在运行，则把编号添加进election消息。待绕