《Distributed Systems Principles and Paradigms》
中文版书名：《分布式系统原理与范型》 Author: A S.Tanebaum
A S.Tanebaum是我喜欢的一名计算机学者，有理论，有实践，这才是计算机的正道。纯理论，那是数学研究者；而纯实践，那是工程师的活。又没有理论，有无实践，那是什么人呢？
分布式系统：点对点计算、传感器网络、虚拟化计算、服务器集群、网格计算、Web 服务（非集中式系统）。
所引出的新问题：分布式系统的一致性模型、时钟同步算法等。
第一章概述
计算技术自80年代两大发展：
高性能CPU
Network
物理上分散的计算机系统，借助于Network互联，在逻辑层面集成为一个整体，即透明化计算。
分布式系统特性：
①隐藏各计算机系统的异构性（中间件,Middleware）
②使用者以统一一致的方式与分布式系统交互。例如，Web
分布式系统四目标：
①资源远程访问
②透明化计算（用户只关心是否使用方便）
③开放性
服务由接口规范，如可用函数的名称、参数等，关键在于说明服务所要执行的任务，即接口语义。
④可扩展性（SaaS）
集中式服务：DNS -〉瓶颈
集中式算法：路由问题
从理论而言，收集各节点和通信线路的状态信息，利用Floyd或Dijkstra算法计算最优路径。问题在于收集相关状态信息并上传会导致网络过载。
分散式算法，其特性：
①没有分布式系统整体状态信息，而基于局部信息决策
②不存在全局性时钟，而是局部时钟（时钟误差扩散）
可扩张性：
缓存，一致性问题(consistency)
不同一致性模型
分布式系统类型：
①集群计算(cluster computing):同构性
②网格计算(grid computing):异构系统
关键问题：如何将异构计算机系统集成,方法之一是虚拟集成(virtual organization)。
③分布式并行数据库
④企业应用集成
PRC(Remote Procedure Call)、RMI(Remote Method Invocation)、MOM(Message-Oriented Middleware)
⑤移动计算
TinyDB
Software Architecture: 软件构件组织和交互关系。
分布式系统：中间件分离应用程序和底层平台，以提供分布式透明性。另一方面，自治系统(Autonomic Systems)
集中式体系结构：C/S
分布式体系结构：
点对点系统(peer-peer system):DHT(distributed hash table),例如 Chord
随机图(random map)
混合体系结构：
协作分布式系统BitTorrent、Globule
自适应软件技术：
①要点分离
②计算映像
③基于组件的设计
分布式系统的自治计算(autonomic computing):反馈控制系统
虚拟化(virtulization):并行运行环境独立于底层硬件和操作平台。
线程的实现：
用户级线程
内核级线程
混合级线程
虚拟机四层次：
机器指令(Machine Instruction)
ISA
系统调用(System Call)
API
虚拟化实现：①ISA仿真
②虚拟监视器(Virtual Machine monitor,VMM)
代码迁移(process migration)
基本思想：调整和优化各节点进程负荷状态，以提升系统整体性能。（局部性原理）
代码迁移模型
第 6 章同步化
进程间如何协作和同步？
①物理时间同步
②逻辑时间同步
Guerraoui, Introduction to Reliable Distributed Programming
(关注实现可靠性的分布式算法)
Lynch， Distributed Algorithm
Raynal “Logical Time: Capturing Causality in Distributed Systems”
Tel, Introduction to Distributed Algorithms
第 7 章一致性和复制
分布式系统的一重要问题：数据复制。对数据复制一般可增强系统的可靠性或提高性能。但随之产生的问题是：难以保持各个副本的一致性，即当更新一个副本时，必须确保同时更新其他副本，否则数据各个副本不相同。
副本管理 --- 副本服务器的布置，其内容如何在多个服务器之间分发
如何实现一致性如何保证多个副本的一致性
特殊一致性--- 缓存协议
一致性模型 -→关键于：复制数据的访问和更新模式
数据为中心的一致性模型：（从数据存储的角度提供系统级一致性,可结合粒度计算）顺序一致性
因果一致性
入口一致性
客户为中心的一致性模型：
最终一致性
单调读/写一致性
读写一致性
写读一致性
复制管理→关键问题:何时、何地、有谁、何种机制保持副本的一致性？而副本的放置问题本身又分为两个问题：
①副本服务器的放置？
②内容放置？
Adve:”Shared Memory Consistency Models: A Tutorial”
Gray.J., “The Dangers of Replication and a Solution”1996
Saito,”Optimistic Replication”
Sivasubramanian, “Replication for Web Hosting Systems”
Wiesmann，M.，”Understanding Replication in Database and Distributed Systems”
2000
Lamport,L.: “How to Make a Multiprocessor Computer that Correctly Executes Multiprocessor Programs.”IEEE T Comp., 1979
Hutto，P.：“Slow Memory：”Weakening Consistency to Enhance Concurrency in Distributed Share Memories.”1990
第 8 章容错性
分布式系统区别于单机系统一个特性是:它容许部分失效。
其设计目标：可从部分失效环境中自动恢复，且不影响整体性能，即使在发生故障时，系统可继续提供服务。→关键：使用冗余来掩盖故障。
Byzantine Failure问题：
Pease,M., “Reaching Agreement in the Presence of Faults” J.ACM,1980
Lamport,L.:“Byzantine Generals Problem.”ACM T https://www.doczj.com/doc/f58931584.html,ng.syst. 1982
Fischer，M。，“Impossibility of Distributed Consensus with one Faulty Processor”J ACM, 1985
Barborak,M., “The Consensus Problem in Fault-Tolerant Computing.”
ACM Comput.Surv, 1993
Turek,J., “The Many Faces of Consensus in Distributed Systems”
IEEE Computer,1992
容错机制
进程恢复方法一：多个相同进程组织到一组中，用一个容错的组取代一个脆弱的进
程。
问题是：组管理组成员之间的关系
组成员加入
组成员离开或失效
组在故障后重建
故障检测：故障检测是容错的基石 ---
要很好屏蔽故障，先要检测出故障
可靠通信点对点通信--- 失败时RPC语义
组通信（多播）
分布式提交两阶段提交协议
三阶段提交协议
恢复：使发生故障的进程恢复到正确状态→检查点 + 日志
Floyd,S., “A Reliable Multicast Framework for Light-weight Sessions and Application Level Framing” IEEE/ACM T Netw, 1997
Levine，B.: “A Comparison of Reliable Multicast Protocols”
ACM Multimedia Systems Journal, 1998
Jalote，P，：Fault Tolerance in Distributed Systems, 1994
Shooman,M.L: Reliability of Computer Systems and Networks :Fault Tolerance, Analysis, and Design. 2002
Tanisch,P., “Atomic Commit in Concurrent Computing.”IEEE Concurrency,2000 Zhuang，S.Q.，“On Failure Detection Algorithms in Overly Networks” 2005
Marcus,Sten : Blueprints for High Availablity
Birman, Reliable Distributed Systems
Cristian,Fetzer, “The Timerd Asynchronous Distributed System Model”Guerraoui: “Software-Based Replication for Fault Tolerantce”
第9章安全性
进程间安全通信
加密DES
RSA
MD5
安全通道身份认证
消息的完整性和机密性数字签名
访问控制
安全管理密钥管理
授权管理
Anderson, Security Engineering: A Guide to Building Dependable Distributed Systems Kuufman, Network Security
Schneider,F:”Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial” ACM Comput. Surv,1990
Schneider,B: Applied Cryptography.
Rivest,R: ”The MD5 Message Digest Alogrithm”
第10章基于对象的分布式系统
数据/状态
对象操作/方法
接口→绑定 bind
体系结构
Java Bean(Enterprise Java Bean, EJB)
Globe 分布式共享对象
进程
PRC
通信RMI(Remote Method Invocation) Java RMI/CORBA
命名
同步
一致性&复制
容错性
安全性
Emmerich, Engineering Distributed Objects
Fleury, “The JBoss Extendsible Server”
Henning, “The Rise and Fall of CORBA”
Henning, Advanced CORBA Programming with C++
Henning,M., “A New Approach to Object-Oriented Middleware”
第11章分布式文件系统
NFS（Network File System）:远程访问模型
体系结构GFS(Google File System)
对称式体系结构（如 Ivy）
通信RPC
命名：为各用户提供自己的名字空间
UNIX语义(Unix Semantics)
文件共享语义语义(Session Semantics)
事务
不可改变文件方式
同步集中式锁机制
一致性&复制
容错性Byzantime故障处理
对等系统高度可用性
安全性
Blanco,”A Survey of Data Management in Peer-to-Peer Systems”
Callaghan, NFS Illustrated
Casstro,M., ”Srie: A Large-Scale and Decentralized Application-Level Multicast Infrastructure”
Cohen,E., ”Replication Strategies in Unstructured Peer-to-Peer Networks”
Daberk.F.，“Eide-area Cooperative Storage with CFS”
Ghemawat,S., ”The Google File System ”
Muthitacharoen,a., ”Ivy: A Read/Write Peer-to-Peer File System”
Pate,UNIX Filesystems: Evolution, Design, and Implementation
Risson,J.,”Survey of Research towards Robust Peer-to-Peer Networks:Search Methods”
Satyanranyanan, ”The Evolution of Coda”
第12章基于Web的分布式系统
Web服务，分布透明性
Web浏览
体系结构WSDL：描述服务
Web服务UDDI：发布、查询服务组合
SOAP：通信
Apache Web
Web服务集群
HTTP
通信
SOAP
命名
一致性Web缓存
同步Web宿主系统复制（CDN，Content Delivery Network）复制Web应用程序复制
容错性
安全性
服务组合关键问题：
①如何协调异构Web服务组件？
②如何正确组成所需QoS服务？
Alonso, Web Services: Concepts, Architectures and Applications (好入门书) Fielding, ”Principled Design of the Modern Web Architecture”
Podling, ”A Survey of Web Cache Replacement Strategies”
Aron,M.,”Scalable Content-ware Request Distribution in Cluster-based Network Servers”
Rabinovich, Web Caching and Replication (Web内容分布性)
Sivasubramanian,S., ”Replication for Web Hosting Systems”
第13章基于协作的分布式系统
基于协作服务,其组件分布式布置,关键问题是:不同组件之间协作。因此必须将计算和协作分离。
计算部分 --- 特定计算的进程
协作部分 --- 负责进程间通信和协作机制（重点）
集中式C/S：如Jini、JaveSpace
体系结构对等体系：如P2P（DHT）
移动协作
通信
命名
一致性
同步复制
容错性
安全性
Gelernter: ”Coordination Language and their Significance”
Carbi,G.,”Mobile-Agent Coordination Models for Internet Application”
Cabir，“Uncoupling Coordination: Tuple-based Model for Mobility”
Caporuscio,M., ”Design and Evaluation of a Support Service for Mobile, Wireless Publish/Subscribe”
Pietzch,”Hermes:A Distrib. Event-Based Middleware Architecture”
Wells, ”Linda Implementation in Java for Concurrent Systems”
Zhao,”Subscription Propagtion in Highly-Available Publish/Subscribe Middleware”