分布式系统原理与泛型考博整理

第1章概述1.分布式系统的另一个定义，它是各自独立的计算机的集合，这些计算机看起来像是一个单的系统，就是说，它对用户是完全隐藏的，即使他有多个计算机也是如此。请给出一个实例。答：并行计算。一个程序在一个分布式的系统中运行，但看起来是在单个系统中运行的。2.中间件在分布式系统中扮演什么角色？答：中间件主要是为了增强分布式系统的透明性（这正是网络操作系统所缺乏的），换言之，中间件的目标是分布式系统的单系统视图，即使种类各异的计算机和网络都呈现为单个系统。3.很多网络系统组织成后端办公系统和前端办公系统。这种组织方式是如何满足分布式系统要求的？答：一个比较容易犯错的地方就是假设运行在一个组织下的分布式系统，应该运行在系统的整个组织框架下。实际上，分布式系统被安装在一个分离的组织中。从这层意义上讲，我们的分布式系统可以支持独立的后端处理和前端处理。当然，这两部分可能是耦合的，并不需要要求这个耦合的部分完全透明。4.解释（分布）透明性的含义，并且给出各种类型透明性的例子。答：分布透明性是一种现象，即一个系统的分布情况对于用户和应用来说是隐藏的。包括：访问透明：分布式系统中的多个计算机系统运行可能是不同的操作系统，这些操作系统的文件命名方式不同，命名方式的差异以及由此引发的文件操作方式的差异应该对用户和应用程序隐藏起来。位置透明：从这个url看不出parenticehall的主web服务器所在的位置，同时也看不出index.html的位置情况。移植透明：分布式系统中的资源移动不会影响该资源的访问方式。重定位透明：资源可以在接受访问的同时进行重新定位，而不引起用户和应用系统的注意。移动通信用户从一个点到另一个点，可以一直使用移动设备，而无中断连接。复制透明：对同一个资源存在多个副本这样一个事实的隐藏。所有的副本同名。并发透明：访问位于同一个共享数据库中的一批表。故障透明：用户不会注意到某个资源无法正常工作，以及系统随后的恢复过程。持久性透明：指对转位于易失性的存储器还是在磁盘上的隐藏。许多面向对象的数据库提供直接调用存储对象的方法的功能。5.在分布式系统中，为什么有时难以隐藏故障的发生以及故障恢复过程？答：通常，要探测一个服务器是停止服务还是该服务器的反应变慢这些情况是不可能的。因此，一个系统可能在服务响应变慢的时候报告该服务已经停止了。例如，连接一台繁忙的web服务器，浏览器超时，报告该web页不可用，这种情况下，用户无法判断该服务器是否真的崩溃了。6.为什么有时候要求最大程度地实现透明性并不好？答：最大程度地实现透明性可能导致相当大的性能损失，从而导致用户无法接受。例如，许多web程序会不断尝试连接某台服务器，多次失败后才放弃。这种在用户转向另一台服务器之前竭力隐藏服务器短暂故障的企图会导致整个系统变慢。7.什么是开放的分布式系统？开放性带来哪些好处？答：开放的分布式系统根据明确定义的规则来提供服务。开放系统能够很容易地与其它系统协作，同时也允许应用移植到同一个系统的不同实现中。8.请对可扩展系统的含义做出准确描述答：一个系统的可扩展包含下面几个方面：组件的数量、几何尺寸、管理域的数量与尺寸，前提是这个系统可以在上面几个方面进行增加而不会导致不可接受的性能损失。系统要能在规模上可扩展，即方便的把更多的用户和资源加入到系统中。地域上可扩展，系统中的用户和资源相隔极远，但仍可访问和使用。管理上可扩展，分布式系统跨越多个独立的管理机构，仍可方便对其进行管理。9.可以通过应用多种技术来取得可扩展性。请说出这些技术。答：可扩展性可以通过隐藏通信等待时间，分布式技术、复制和缓存来获得。10.请解释一下什么是虚拟组织，并给出如何实现这种组织的提示。答：属于同一虚拟组织的人或应用，具有访问提供给该组织的资源的权限。这些资源可能分布在不同的计算机、服务器、数据工具和数据库中。虚拟组织定义了谁能访问什么。资源应该保持一个账户用户和访问权限，这通常使用了标准的访问控制机制（类似UNIX中的rwx）。11.当一个事务处理被异常中断，将会恢复到它以前的状态，就像这个事务处理从没有发生过一样。我们这么说其实是不对的。请给出一个无法恢复以前状态的示例。答：任何情况下，物理端的I/O中断，不能重置。例如，如果一个进程是来打印文件，文件中的墨汁不能从纸中移除。12.运行嵌套式事务处理需要某种形式的协作，请解释一下协作者真正应该做什么事情？答：协作者只需要保证嵌套式的事务中止后，所有的子事务都要被中止。同样，如果事务都能够被提交，那么就应该协调他们全部都提交。当协调者告诉嵌套的事务该提交时，事务理解进行提交操作。13.我们讨论过，对普适系统来说，分布式透明性可能并不存在。这句话并不是对所有的透明性都正确，请给出一个示例。答：考虑迁移透明性。在普适系统中，组件是可移动的，当从一个接入点移动到另一个接入点时，它可被重新连接。这样的处理应该对用户完全透明。同样，许多其他类型的透明性也会被支持，然后不该隐藏的是用户可能访问的资源与用户本身所处的环境是耦合的。14.我们已经给出了一些分布式普适系统的示例：家庭系统、电子健保系统和传感器网络，请再给出这样的一个示例。答：考虑在城市或社区中提供大规模的无线网状网络服务的普适系统，它提供无线上网服务，当然这个也为其他服务，比如新闻系统提供了通信基础。栖息地的监控系统、监狱中的电子监控系统、大型综合体育系统、了解员工状态的办公激励系统等。普适计算是指在普适环境下使人们能够使用任意设备、通过任意网络、在任意时间都可以获得一定质量的网络服务的技术。普适计算是在网络技术和移动计算的基础上发展起来的，其重点在于提供面向客户的、统一的、自适应的网络服务。普适环境主要包括网络、设备和服务：网络环境包括Internet、移动网络、电话网、电视网和各种无线网络等。普适计算设备更是多种多样，包括计算机、手机、汽车、家电等能够通过任意网络上网的设备；服务内容包括计算、管理、控制、资源浏览等。普适计算具有以下环境特点：在任何时间、任何地点、任何方式的方便服务，不同的网络（不同协议、不同带宽）、不同的设备（屏幕、平台、资源）、不同的个人偏好等。第2章体系结构1.如果客户和服务器相隔很远，我们可以看到，网络延时将主导整个性能。我们如何处理这个问题？答：这实际上取决于客户端是如何组织起来的。首先，将客户端的代码切割成更小的部分，这样它们可以单独运行。这种情况下，当一部分正在等待服务器的响应时，我们可以安排另一部分去做其他的事。或者，我们可以重新安排客户端的处理过程，让他们在向服务器发送客户请求之后去做其他的事情。最后有效的解决方案是用单程异步通信取代了客户端-服务器的同步通信。2.什么是三层客户-服务器体系结构？答：三层客户——服务器体系结构包括三个逻辑层：用户接口层、处理层和数据层，每一层在理论上来说都在一台单独的机器上实现。最高层包括了客户的用户界面，中间层包括实际的应用程序，最底层包含了被使用的数据。3.纵向分布与横向分布有什么不同？答：纵向分布指的是多台机器组成的多层架构中各个层的分布，通过按逻辑把不同组件放在不同的机器上来获得。从理论上说，每一层都在一台不同的机器上实现。横向分布则处理多台机器上的一个层的分布，客户或者服务器可能在物理上被分隔成逻辑上相对的几个部分，每个部分都操作在整个数据集中自己共享的部分。例如一个数据库的分布。4.考虑一个进程链，该进程链由进程P1,P2,…,Pn构成，实现了一个多层客户-服务器体系结构。进程Pi是进程Pi+1的客户，Pi只有得到Pi+1的应答之后才能向Pi-1发出应答。如果考虑到进程P1的请求-应答性能，这种组织结构主要存在什么问题？答：如果n很大的话性能会很差。从理论上来说，两个邻接层之间的通信应该在两台不同的机器之间发生。因此，P1和P2之间的性能由n-2次其它层之间的请求——应答过程决定。另一个问题是如果链中的一台机器性能很差甚至临时不可达，这会立刻使最高层的性能降低。5.在结构化的覆盖网络中，消息是根据覆盖的拓扑结构来路由的，这种方法的主要缺点是什么？答：问题是我们处理的是逻辑路径。很有可能出现的情况是，在覆盖网络中的两个邻居节点A和B，在物理距离上是相距很远的。因此，A和B之间的逻辑最短路径实际上在底层物理网络上是很长的一条路径。6.图2.8中的CAN网络，如何把坐标（0.2,0.3）的节点的消息路由到坐标为（0.9，0.6）的节点？答：有几种可能性。如果我们想要根据欧几里得距离得到一条最短路径需要进过的路径是：（0.2,0.3）----（0.6,0.7）----（0.9,0.6），距离是0.882.另一条路径：(0.2,0.3)---(0.7,0.2)----(0.9,0.6)，距离是0.9577.假设CAN中的一个节点知道其紧邻节点的坐标，一个合理的路由策略是把消息路由给离目的地最近的节点，这样的策略的好处是什么？答：从先前的问题可以看出，它不需要去寻找整体最优的路径。如果节点（0.2,0.3）按照题目要求的策略进行，传送到（0.9,06），它先会将节点发送给（0.7,0.2）。8.在非结构化的覆盖网络中，每个节点随机选择c个邻接节点。如果P和Q都是R的邻接节点，那么P和Q互为邻接节点的概率是多少？答：如果网路中有N个节点，如果每个节点随机选择c个邻居，那么P选择Q或Q选择p的概率就是2c/(N-1)。（P从N-1个节点中选择到Q的概率为c/(N-1)，同理Q从N-1个节点中选择到p的概率也为c/(N-1)，因此总的概率为2c/(N-1)）9.在非结构化的覆盖网络中，每个节点随机的选择c个邻节点。要查找一个文件，节点将泛洪一个请求给他的邻接点，这些请求又将再次泛洪，该请求将到达多少个节点？答：可到达节点的上界是c*(c-1)(因为，每个节点随机选择c个邻居，只有第一个节点a可以选择c个，第二次洪泛时，每个节点只需要随机选择c-1个，因为a也是他们的邻居，但a已经在洪泛到达的范围内了，因此上限是c(c-1))，但是这我们忽略了节点p同样可以成为其他邻居节点的邻居。P的一个邻居泛洪信息给不是P邻居节点的概率是1减去发送给至少P的一个邻居节点的概率。这个情况下，泛洪策略将会到达c*q*(c-1)个节点。例如，c=20,N=10000,那么一次查询将会到达的节点数是365.817个节点。基于概率论中的二项分布原理，在n重伯努利试验中,事件A恰好发生k次的概率为：，因为p已经选择了Q，所以p最多可以选择Q的c-1个邻居节点作为洪泛的目标节点。10.在点对点的网络中，并不是每个节点都能成为超级对等体。满足超级对等体的合理要求是什么？答：首先，节点是高度可用的，因为其他节点需要依赖该节点。并且，它应该有足够的能力处理各种请求。最重要的是依靠它能够高效快速的处理任务。11.在Bitgtorren系统中，每个节点具有一个带宽为Bout的输出链接，以及一个带宽为Bin的输入链接。这些节点（称为种子节点）中的一些可以自愿的为其他节点提供下载文件。如果假设在某个时候，一个BitTorrent的系统最多只有一个种子节点，那么他的最大下载带宽是多少？答：这里需要考虑种子节点的输出带宽需要在客户端间共享。假设有s个种子，N个客户端，每个客户端随机的选择种子。种子节点结合的输出带宽就是S*Bout，每个客户端有S*Bout/N的直接下载带宽。另外，如果这些客户端互相协作，每个能够在下载数据块时达到Bout，假定BinBout。因为tit-for-tat策略，一个BitTorrent客户端的下载带宽主要取决于他的输出带宽。所以说，整体的下载带宽能够达到S*Bout/N+Bout.(S*Bout/N是从种子节点上直接下载的带宽，Bout是从协作节点上下载的带宽，因为BinBout成立，所以S*Bout/N+Bout是可以达到的)12.请从技术的角度来解释，为什么BitTorrent中的tit-for-tat策略比因特网中的文件共享要好得多？答：大多数的Bit