分布式系统课程笔记
分布式系统简介
分布式系统定义
定义：分布式系统是若干独立自主计算机的集合（硬件），这些计算机对用户来说像是单个耦合系统（软件）
特性：
- 自主性：计算节点硬件或者软件进程是独立的
- 耦合性：节点之间相互协作
分布式系统的设计目标
资源可访问：
透明性：用户无法看到细节
开放性：定义良好的接口
可扩展性
体系结构
软件体系结构
分层结构：主要用于客户端-服务器模型
面向对象结构：主要用于分布式对象系统
基于事件的结构
共享数据空间结构
系统体系结构
确定软件组件，这些组件交互以及它们部署位置就是软件体系结构的一个实例就是系统体系结构。
集中式体系结构
应用分层
传统的三层视图：
用户接口层
应用处理层
数据层 ### 非集中式体系结构
垂直分布：系统逻辑分层，不同层次分布在不同机器上
水平分布：客户端或服务器在物理上分成逻辑上相等的几个部分，每个部分相对独立，且分布在不同机器上
点对点分布：水平分布，构成点对点的系统的进程完全相同（既是客户端又是服务器）
p2p
- 结构化p2p：将节点组织在一个特定结构的覆盖网络中，如环形结构
- 非结构的p2p：每个节点维护一个动态随机的邻接表
分布式中的进程和虚拟化
分布式线程
在客户端使用多线程
- 多线程的Web客户端
- 隐藏了网络延迟
多线程服务器
- 提高性能：并行响应请求隐藏网络延迟
- 更好的结构：代码数量较少，容易理解
虚拟化
主要原理：模拟接口
- 指令集架构
- 系统调用
- 库函数调用API
代码迁移
- 负载分布
- 确保数据中心的服务器的复杂运行的分布更加充分（防止资源浪费）
- 让计算更加贴近数据端，最小化通信代价（移动计算）
通信
基本的网络模型
OSI参照模型：7层
传输层
对于大部分分布式系统，传输层提供实际的通信功能
协议：
- TCP：面向连接的，可靠的、面向流的通信
- UDP：不可靠
中间件层
提供通用的服务和协议
通信类型
瞬态通信VS持久通信
同步通信VS异步通信
客户端/服务器通信
一般是基于瞬态，同步的通信方法
消息（Message）
面向消息的中间件：
目的在于进行高层次的持久化，异步通信：
- 进程之间相互发生消息，这些消息会被排队
- 发生进程可以继续做其他事（异步）
- 中间件提供容错机制
远程过程调用
面向消息的通信
面向消息的瞬时通信
套接字
消息传递接口（MPI）
面向消息的持久通信
消息队列模型
应用程序可以通过在特定队列中插入消息来进行通信
有以下四种方式：
消息转换器
- 将输入消息转换为目的格式
- 起应用层网关的作用
- 提供基于主题的路由功能
面向流的通信
- 数据流：数据流是数据单元的序列，可以应用于离散的媒体即离散数据流，也可以应用于连续媒体即连续数据流
- 数据流传输模式：
- 异步传输
- 同步传输
- 等时传输
服务质量（Qos）
命名系统
无层次结构命名
基于宿主位置的方法：
- 实体的宿主地址注册在命名服务上
- 宿主机注册实体的外部地址
- 客户端先与宿主机联系，然后与实体的外部地址联系
- 存在的问题：
- 宿主机需要伴随实体的整个周期
- 宿主机的地址固定
- 地域可扩展性差（目的主机可能就在客户端旁边）
分布式散列表：
- 每一个节点被赋予一个由m位构成的标识符
- 每一个实体被赋予一个唯一的m位键值
- 含有键值k的实体位于含有最小标识符id且id>=k的节点中
finger table：
查找
如果p< k <= FT[1],则把请求转发给finger table的第一个节点
例子：
问题：覆盖网络中的节点之间的组织结构可能导致在底层互联网上的异常消息传输：比如相邻节点距离很远
分层定位方法
同步化
互斥
分布式系统中需要互斥的访问某些资源
基本的解决办法：
- 基于许可的方法
- 基于令牌的方法
基于许可的集中式方法
协作者收到进程的请求，协作者根据是否有进程正在访问临界资源来判断是否发送许可，如果有进程正在访问临界资源，则将该请求放入队列中，如下图所示：
问题：
- 单点故障
- 性能瓶颈
非集中式算法
可以显著的提高节点失效的问题
问题：
- 有可能多个进程访问某一资源，任何 进程都不能得到超过\(N/2\)的票数
- 解决办法：retry
分布式算法
解决单点故障
- Ricat & Agrawala 算法：
- 要求系统中的所有事件都是完全排序的
- 问题：单点故障被n个故障点所取代。故障概率提高了n倍
令牌环算法
将进程组织为逻辑环，令牌在这些进程之间传递
比较
选举算法
Bully算法
Ring算法
无线系统环境中的选举算法
- 传统选举算法的缺点：
- 传统的选举算法假设消息是可靠的，网络的拓扑结构也是不会改变的
- 传统的选举算法假设消息是可靠的，网络的拓扑结构也是不会改变的
容错
分布式提交协议
问题：一个操作要么被进程组中的每一个成员执行，要么一个都不执行（比如git/DB）
两阶段提交协议：
- phase 1a：协作者发起VOTE-REQUEST
- phase 1b：参与者收到请求后返回VOTE-COMMIT或者VOTE-ABORT
- phase 2a：协作者收集所有的投票，如果全是VOTE-COMMIT，就发生GLOAB-COMMIT，反之，发送GLOAB-ABORT
- phase 2b: 每个参与者根据GLOBAL进行响应的操作
如下图所示：
一致的恢复状态
恢复线路：
- 每一个进程都会周期性的记录检查点，最近的一次全局一致的检查点就是恢复线路
- 全局一致：一个进程记录到了接收消息，另一个进程则必须记录发送了消息
在下图中，可以看出消息的发送不能在checkpoint的右侧，而接收消息在checkpoint的左侧
独立检查点
每个进程独立的打检查点，可能会导致一直找不到recovery line，最后回退到初始状态
协调检查点
每一个进程在收到一个全局协作的消息之后才打一个检查点
日志消息
检查点的代价过高，通过“重放”的方式达到一个全局一致的状态。——》在日志中持久化消息。
消息记录和一致性
避免孤儿进程，就是避免某些消息未记录，如下图
消息记录的模式
下图是几种集合的表示：
有以下两种协议避免孤儿进程：
分布式系统共识
Paxos
一些问题场景
两军问题：
状态复制机的问题：
复习
分布式系统定义、特点、目标、类型
软件体系结构（四种），系统体系结构（集中，非集中（DHT），混合）
虚拟化，虚拟化的含义类型，Docker，服务器状态，服务器集群，代码迁移
通信类型，rpc执行过程，面向消息的通信（socket的基本操作），消息队列类型、实现（消息管理器，路由什么作用），gossip两种模型工作过程、原理
命名是什么，chord指纹表，结构化命名，解析过程，DNS
时钟同步，逻辑时钟、向量时钟...
CAP理论，一致，副本，一致性协议（原理，不掌握过程），主从副本协议，写协议
故障类型（影响程度），可靠性可用性（定义，关系），恢复，可靠多播，分布式提交，系统修复，两阶段提交协议
paxos，raft，pbst（用来干嘛）
分布式文件系统