怎么用自己主机做网站,wordpress 播客网站,ssh可以做wap网站么,wordpress根目录修改主题第一章 为什么需要分布式系统#xff1a;功能分离#xff0c;固有的分布性#xff0c;负载均衡#xff0c;可靠性#xff0c;经济性。 定义#xff1a;分布式系统是这样一种系统#xff0c;其中位于联网计算机上的组件仅通过传递消息来通信和协调它们的操作。 特点功能分离固有的分布性负载均衡可靠性经济性。 定义分布式系统是这样一种系统其中位于联网计算机上的组件仅通过传递消息来通信和协调它们的操作。 特点 并发性多个程序进程线程并发执行共享资源无全局时钟每个机器有各自的时间难以精确同步程序间的协调靠交换消息故障独立性一些进程出现故障并不能保证其它进程都能知道 分布式系统举例WEB 搜索、大型多人在线游戏、金融交易、区块链系统、语音系统、数据库系统 分布式系统趋势 泛在联网与现代互联网移动与无处不在的计算分布式多媒体系统将分布式计算作为公共设施 挑战透明性、异构性、并发、开放性、安全性、可伸缩性、故障处理
第二章 系统的体系结构用独立指定的组件以及这些组件之间的关系来表示的结构。 整体目标确保结构能满足现在和将来可能的需求。 体系结构元素 通讯实体进程、线程、节点对象、组件、web服务通信泛型进程间通信套接字、多播、消息传递远程调用请求-应答协议、RPC、PMI 体系结构模式构建在相对原始的体系结构元素之上提供组合的、重复出现的结构。 分层体系结构一个复杂的系统被分成若干层。每层利用下层提供的服务。中间件是一种软件它提供基本的通信模块和其他一些基础服务模块为应用程序开发提供平台。层次化体系结构层次化是一种从应用角度理解系统的体系结构模式与分层体系结构互补是一项组织给定层功能的技术。瘦客户本地只是一个 GUI 应用程序在远程计算机上执行。 基础模型对体系结构模型中公共属性的一种更为形式化的描述。 交互模型用来描述延迟的不确定性与缺乏全局时钟的影响。被用来处理消息发送的通讯性能问题解决在分布式系统中设置时间限制的难题。故障模型组件、网络等故障的定义、分类试图给出进程和信道故障的一个精确的约定。定义了什么是可靠通信和正确的进程 。 遗漏故障进程或者通信通道没有正常的工作进程崩溃、丢失信息随机故障对系统影响最大的一种故障且错误很难探知。时序故障仅发生在同步分布式系统中 安全模型提供依据以此分析系统可能收到的侵害并在设计系统时防止这些侵害的发生。进程、通信信道、对象威胁DoS攻击、移动代码。对策加密技术与共享密钥、认证、安全通道
第三章时间与全局状态 事件一个通信动作或进程状态转换动作。 进程历史在进程中发生的一系列事件按发生在先排序即 h i s t o r y ( p i ) e i 0 , e i 1 , e i 2 , . . . history(p_i)e_i^0,e_i^1,e_i^2,... history(pi)ei0,ei1,ei2,... 时钟漂移震荡频率变化电源稳定性、环境温度 同步物理时钟 外部时钟采用权威的外部时间源。内部时钟无外部权威时间源系统内时钟同步。关系若P时钟集合在范围D内外部同步则P在范围2D内内部同步。时钟正确性含义 基于漂移率——漂移率在一个已知的范围内基于单调性—— t ′ t → C ( t ′ ) C ( t ) tt→C(t)C(t) t′t→C(t′)C(t)基于混合条件——单调性漂移率有界同步点跳跃前进 物理时间同步的三种方法 Cristian方法应用条件存在时间服务器作为外部时间源消息往返时间与系统所要求的精度相比足够短。协议进程P根据消息 m r m_r mr m t m_t mt计算消息往返时间 T r o u n d Tround Tround根据服务器在 m t m_t mt中放置的时间 t t t设置时钟为 t T r o u n d / 2 tTround/2 tTround/2。精度 ± ( T r o u n d / 2 – m i n ) ±(Tround/2 – min) ±(Tround/2–min)。Berkeley方法:主机周期轮询从属机时间主机通过消息往返时间估算从属机的时间主机计算容错平均值主机发送每个从属机的调整量。NTP:外部同步高可靠性拓展性好安全性强。 逻辑时间和逻辑时钟 逻辑时间的引入节点具有独立时钟缺乏全局时钟分布式系统中的物理时钟无法完美同步事件排序是众多分布式算法的基石。逻辑时钟众多应用只要求所有节点具有相同时间基准该时间不一定与物理时间相同。不进行交互的两个进程之间不需要时钟同步。发生在先偏序 若存在进程 P i P_i Pi满足 e → i e ′ e→_ie e→ie′则 e → e ′ e→e e→e′对于任一消息 m m m存在 s e n d ( m ) → r e c v ( m ) send(m)→recv(m) send(m)→recv(m)若事件满足 e → e ′ e→e e→e′和 e ′ → e ′ ′ e→e e′→e′′则 e → e ′ ′ e→e e→e′′ 并发(X||Y)XY与YX均不成立则称事件X、Y是并发的。Lamport时钟Lamport 发明的一种简单机制可以数字化发生在先排序。它规定每个进程维护自己的逻辑时钟一个单调增长的计数器进程 P i P_i Pi用它给事件加上Lamport时间戳 L i L_i Li。若进程触发了某个事件则将该事件标注时间戳为 ( L i 1 ) (L_i1) (Li1)发送消息时在消息中附带 t L i tLi tLi接收进程接收消息事件被标注时间戳为 m a x ( L j , t ) max(L_j,t) max(Lj,t)。向量时钟与Lamport时钟的区别在 P i P_i Pi给事件加时间戳之前设置 V i [ i ] V i [ i ] 1 V_i[i]V_i[i]1 Vi[i]Vi[i]1。克服了Lamport时钟的缺点 L ( e ) L ( e ′ ) L(e)L(e) L(e)L(e′)不能推出 e → e ′ e→e e→e′。全局状态单个进程状态的集合 S ( s 1 , s 2 , . . . , s N ) S(s_1,s_2,...,s_N) S(s1,s2,...,sN)割集系统全局历史的子集部分事件的集合有序。 C h 1 c 1 , h 2 c 2 , . . . , h n c n Ch_1^{c1},h_2^{c2},...,h_n^{cn} Ch1c1,h2c2,...,hncn割集的一致性割集C是一致的即对于任意事件 e ∈ C , f → e ⟺ f ∈ C e∈C,f→e⟺f∈C e∈C,f→e⟺f∈C即有果必有因。一致的全局状态对应于一致割集增量序列的状态 S 0 → S 1 → S 2 → … S0→S1→S2→… S0→S1→S2→…系统的执行可以描述成系统全局状态之间的一系列转换。Chandy和Lamport的“快照”算法为了捕获一致的全局状态在缺乏类似全局时钟或者全局时钟不可靠的分布式系统中来确定一种全局状态。算法定义了两个规则标记发送规则和标记接收规则。前者强制记录下自己状态的进程立即发送一个标记信息后者强制没有记录状态的进程去记录自己的状态。 第四章协调和协定 分布式互斥分布式进程常常需要协调它们的动作如访问共享资源时需要互斥来防止干扰并保证一致性这对应操作系统领域常见的“临界区”问题。然而分布式系统中原有互斥方法基本均失效需要一个仅基于消息传递的分布式互斥解决方案。 目的仅基于消息投递实现对资源的互斥访问。 假设异步系统无故障进程可靠的消息投递。 基本要求 安全性在临界区内一次最多有一个进程可以执行。活性进入和离开临界区的请求最终成功执行。顺序先请求进入临界区的进程先进入临界区 评价指标 带宽消耗的带宽与进入和退出临界区发送消息的数量成正比。延迟每次进入和退出操作导致的客户延迟。吞吐量用一个进程离开临界区和下一个进程进入临界区之间的同步延迟来衡量。 中央服务器算法满足安全性和活性要求但不满足顺序要求。 带宽消耗 enter:个消息即请求消息授权消息exit: 1个消息即释放消息 客户延迟 enter: request grant 1 round-tripexit: release 同步延迟 1个消息的往返时间1 release 1 grant。 基于环的算法所有程序构成一个环结构令牌按照顺时针或逆时针方向在程序之间传递收到令牌的程序有权访问临界资源访问完成后将令牌传送到下一个程序若该程序不需要访问临界资源则直接把令牌传送给下一个程序。在分布式领域这个算法叫作令牌环算法也可以叫作基于环的算法。 满足安全性和活性要求不满足顺序要求。带宽消耗由于令牌的投递会持续消耗带宽客户延迟(enter) Min: 0个消息正好收到令牌Max: N个消息刚刚投递了令牌 同步延迟 Min: 1个消息进程依次进入临界区Max: N个消息一个进程连续进入临界区期间无其他进程进入临界区。 基于组播和逻辑时钟的算法进程进入临界区需要所有其它进程的同意。要进入临界区的进程组播一个请求消息并且只有在其他进程都回答了这个消息时才能进入。采用Lamport时间戳避免死锁请求进入的消息形如 T , P i T,P_i T,Pi如果请求具有相等的时间戳那么请求将根据进程的标识符排序。 满足安全性、活性和顺序要求。带宽消耗 enter: 2(N1)即(N1)个请求、 (N1)个应答。 客户延迟1 round-trip (multicast)同步延迟1个消息的传输时间无exitvs round-trip。 Maekawa投票算法进程进入临界区不需要所有进程同意部分即可 满足安全性活性和顺序性。带宽消耗 enter需要 2 n 2\sqrt{n} 2n 个消息exit需要 n \sqrt{n} n 个消息Ricard2(N-1) 客户延迟1 round-trip同步延迟1 round-trip 分布式选举选择一个唯一的进程来扮演特定角色的算法。 含义集群一般是由两个或者两个以上的服务器组建而成每个服务器都是一个节点。对于一个集群来说多个节点到底是怎么协调怎么管理的呢解决方法是选出一个“领导”来复杂调度和管理其他节点。这个所谓的“领导”在分布式中叫做“主节点”而选“领导”的过程叫做“分布式选举”。 基本要求 安全性参与进程 P i P_i Pi的 e l e c t e d i ⊥ elected_i⊥ electedi⊥或 e l e c t e d i P elected_iP electediP有效进程 pid最大值。活性所有进程 P i P_i Pi都参加并且最终置 e l e c t e d i ≠ ⊥ elected_i≠⊥ electedi⊥或进程 P i P_i Pi崩溃。 基于环的选举算法 目的在异步系统中选举具有 最大标识符 的进程作为协调者。基本思想按逻辑环排列一组进程 id 不必有序。性能最坏情况启动选举算法的逆时针邻居具有最大标识符共计需要3N-1个消息周转时间为3N-1最好情况周转时间为2N 霸道算法 同步系统使用超时检测进程故障。通道可靠但允许进程崩溃。每个进程知道哪些进程具有更大的标识符每个进程均可以和所有其它进程通信性能best N − 2 N-2 N−2worst N 2 N^2 N2 组播通讯发送一个消息给进程组中的每个进程。 基本组播B-multicast(g, m)对每个进程p∈gsend(p, m)进程p receive(m)时p执行B-deliver(m)。 可靠组播 协定如果一个正确的进程投递消息m那么group中其它正确的进程终将投递m。区别B-multicast 不保证协定sender中途失效。 实现可靠组播的方法协定表明了 B-Multicast 不能再基于一对一的send来实现因为组播进程在send中途出现故障时会导致剩余进程无法Deliver该消息。可行方案如下 用基本组播实现可靠组播满足完整性满足有效性满足协定但是效率低。 用IP组播实现可靠组播将IP组播、捎带确认法、否定确认结合起来实现可靠的Multicast和Deliver。 共识、交互一致性及拜占庭将军问题含义这三类问题统称为协定即在一个或多个进程提议了一个值应当是什么后使系统内所有进程对这个值达成一致的意见。 共识问题一个或多个进程提议一个值后应达成一致意见。 基本要求 终止性每个正确的进程最终设置它的决定变量。协定性如果 P i P_i Pi和 P j P_j Pj是正确的且已进入决定状态那么 d i d j d_id_j didj。完整性如果正确的进程都提议了同一个值那么处于决定状态的任何正确进程都已选择该值。 共识算法每个进程组播它的提议值每个进程收集其它进程的提议值每个进程计算 V m a j o r i t y ( v 1 , v 2 , … , v N ) V majority(v_1, v_2, …, v_N) Vmajority(v1,v2,…,vN)。其中 m a j o r i t y ( ) majority() majority()函数为抽象函数可以是 m a x ( ) max() max()、 m i n ( ) min() min()等。 拜占庭将军问题3个或更多将军协商是进攻还是撤退1个将军司令发布命令其他将军中尉决定进攻或撤退一个或多个将军可能会叛变所有未叛变的将军执行相同的命令 。 拜占庭将军问题要求 终止性每个正确进程最终设置它的决定变量。协定性所有正确进程的决定值都相同。完整性若司令正确则所有正确进程采用司令提议的值。 与共识问题的区别一个独立的进程提供一个值其他进程决定是否采用。 交互一致性每个进程提议一个值就向量达成一致。决定向量: 向量中的每个分量与一个进程的值对应。 交互一致性的要求 终止性每个正确进程最终设置它的决定变量。协定性所有正确进程的决定向量都相同。完整性如果进程pi是正确的那么所有正确的进程都把vi作为他们决定向量中第i个分量。
