导图社区 计算机研究生课程分布式系统考试复习重点总结
计算机研究生课程分布式系统考试复习重点总结，涵盖时钟同步、事务并发控制、协调和协定、一致性哈希算法、文件系统、GFS、NFS、AFS等实例归纳总结。
社区模板帮助中心，点此进入>>
互联网9大思维
安全教育的重要性
组织架构-单商户商城webAPP 思维导图。
个人日常活动安排思维导图
域控上线
西游记主要人物性格分析
17种头脑风暴法
python思维导图
css
CSS
分布式
复制
基本要求
透明性：对用户屏蔽多个物理拷贝的存在
一致性：不同的场景有不同的一致性强度要求
容错
高可用
系统模型
前端
把请求发送至1个或多个副本管理器
副本管理器
对副本执行原子性操作
容错服务
线性化能力
顺序一致性
2副扑克牌掺在一起，每副扑克牌顺序仍然一致
被动复制
如果一个主副本管理器故障，则某个备份副本管理器提升为主副本管理器
请求 协调 执行 协定 响应
主动复制
副本管理器地位对等，前端把组播消息给副本管理器组
拷贝对象的事务
单拷贝串行化
读一个 写所有
gossip
查询和更新操作 5个步骤，读请求暂不处理，立即响应更新请求，发现消息丢失则进行gossip消息交换
请求 前端发送请求给RM 副本管理器立即应答收到的更新请求
协调 收到请求后先不处理，根据要求的次序约束，等待处理完请求之后为止
执行 副本管理器执行请求
查询响应 RM对查询请求响应
协定 RM交换gossip消息进行相互更新
体系结构
前端可以任意选择RM 提供查询和更新2种操作 RM定期通过gossip消息传递更新
时间和时钟
基本概念
事件：进程的历史事件
时钟漂移：受温度频率影响在所难免
物理时钟同步
Christian时钟
外部时钟同步
又一个时钟服务器，进程p给服务器发送消息，通过传播时间估算：t+T/2
Berkerly
内部同步
选举1个主机作为基准，轮询其他从属机（类似Christian的方法），收到从属机的时间之后，使用容错平均值计算每个从属机的偏移量，并返回给从属机。
NTP
网络时间同步，与UTC同步，三种模式：RPC、过程调用
逻辑时钟
Lamport
每个进程初始时间戳为0，第一个事件时间戳为1 ！ 进程每发生一个事件时间戳的值+1 进程收到消息时，比较收到消息的时间戳和自己的时间戳，取最大值+1 ！
全局逻辑时钟
时间戳格式改为（T，i） 其中T表示时间戳同Lamport，i表示进程标识符
向量时钟
每个进程的时间戳是一个向量，其中每个维度对应进程的时间戳 要求，会画时间轴图，注意，每个进程起始时间戳为1，进程收到消息时，取最大值，不用+1！
克服了Lamport的缺点，时间戳大小可推断时间先后关系
全局一致性
对应一系列割集的状态转换
chandy & Lamport快照算法
事务和并发控制
串行等价
并发事务交错执行的结果和按照一定次序一次执行一个事务的结果相同，那么这种交错执行时串行等价的
充要条件： 冲突操作按照相同的顺序在冲突对象上执行
乐观并发控制
访问对象时不检测冲突，提交事务时检测冲突，发现冲突则放弃当前事务
向前向后： 后验证的事务的写集和前验证的事务的读集有没有重叠
锁
两阶段锁： 增长阶段：一次性获得访问对象的所有加锁； 收缩阶段：一次性释放访问对象的锁。
预防死锁：一次性获得所有访问对象的锁
检测死锁：等待图是否有环
时间戳
事务启动时，事务有一个时间戳； 对象也有时间戳（读时间戳和多个写时间戳，并且写时间戳在临时版本上）
写规则
T > 对象D的最大读时间戳 && T >= 对象D已提交版本的写时间戳：可以在D的临时版本上进行写操作 （先写完的先提交） （要防止这种情况：T先执行，但T提交的晚于T之后的事务） （注意，写操作不关心读操作冲突，因为发生冲突时读操作要先紧着写操作执行）
读规则
T >= 对象D的已提交版本的时间戳 && 等待写时间戳最大的事务提交或放弃之后：执行读操作，提交事务T
比较
乐观方法：放弃事务成本较高，适合冲突较少的操作
悲观方法：锁机制适合更新操作较多的情况（读操作不用锁，浪费）
悲观方法：时间戳：适合于读操作较多的情况（比如只有读操作，没有写操作，时间戳法明显更好）
例题
协调和协定
分布式互斥
仅仅依靠消息传递实现资源共享（临界区） 假设是 异步系统，无故障，消息传递可靠
基本要求是： 安全性：一次只有一个process在临界区 活性：无死锁，无饥饿等待 顺序：按请求顺序进入临界区
中央服务器算法
基于环的算法（不满足顺序要求）
轮流传递令牌（谁需要谁使用）
组播+逻辑时钟
使用Lamport时间戳（T，p） 其中p是进程标识符，T是时间戳
要申请临界区的进程组播一个请求消息，并且其他进程应答才可进入
数据：进程状态HELD/RELEASED/WANTED 算法： 申请的进程p ： state=REALEASED 组播（T ，p ） 等待应答数==N state=HELD 接收消息方： 收到请求（T ，p ） 如果当前进程q 状态是HELD 或者（q 状态是WANTED && q 申请的时间戳小） 请求放入队列中，不应答 q 退出临界区时： 应答队头请求，state=REALEASED
Maekawa
使得部分进程同意即可
每个进程都有自己的选举集（选举集数量都相同） 每2个选举集之间都有交集
数据：state=WANTED/HELD/RELEASED ；voted=TRUE/FALSE 算法： 发送消息 同上 接收消息（T ，p ）： 如果当前进程状态是HELD 或voted=TRUE ：放入队列，不应答 否则应答p ，voted=TRUE 退出临界区时： state=RELEASED ，voted=FALSE
选举
基于环的选举 顺时针传递消息（elect ，msg_id ） 第一圈设置选举参与者状态 第二圈找到leader 第三圈公示leader
消息类型：请求消息/ 应答消息/ 协调者消息 霸道算法 各个进程收到选举消息之后回复请求，然后给老大发送选举消息，若收到回复则等待老大回复，否则认为自己是老大。
组播
共识和拜占庭将军
分布式文件系统
3个组件
目录服务：提供文件名到UFID的映射
平面文件服务：对文件内容操作
用户模块：API继承前两个组件
NFS
AFS
GFS
动机
节点失效被认为是常态事件
文件非常巨大，数GB的文件非常常见
绝大部分文件操作是追加，而不是覆盖
应用程序和文件系统API协同设计
大规模流式读取和小规模随机读取
设计思想 （数据块、副本、主服务器）
文件以数据块形式存储，数据块大小相同，每个数据块拥有句柄
副本技术保证可靠性 每个数据块至少在3个服务器上存储
主服务器维护所有文件系统元数据 周期性更新服务器
master服务器存储元数据，64MB为单位。客户端先在Master服务器上做元数据查找并且找到包含用户数据的那些
Chunk服务器在硬盘上存储实际数据，每个Chunk服务器在其他3个chunk服务器上做备份； 一旦被Master程序指明，客户端立即从Chunk服务器上读取数据
chunk服务器不需要缓存文件数据（Linux文件系统会缓存）； 客户端不需要缓存文件数据
核心是控制流和数据流分开
客户端发送请求到Master Master收到请求通过chunk映射表查找chunk location和句柄返回给客户端 客户端向chunk发送文件名和目录索引 chunk回复请求，返回文件数据
Master 独立主机上的一个进程 存储元数据信息（文件命名空间、文件到数据块映射信息、数据块的位置信息、数据块版本号、访问控制信息）
64MB 大文件数据块 减少master 的元数据量（文件块大了，索引项就少了） 减少网络负载（长期保持一个TCP 连接） 在clien 中可以缓存更多的信息（原理同1 ） 缺点： 一个文件可能只包含一个块，如果很多client 访问该文件，会成为热点
块位置信息： master不保存块副本的元数据信息
读操作
应用程序发出读请求； client 将请求转换为（文件名、块位置），发送master ； master 返回数据块的指引信息和副本位置信息； client 选择其中一个位置信息，发送请求给相应的chunk 服务器 chunk 服务器返回文件数据； client 吧数据传给应用程序
互斥操作
client请求master，返回块句柄和副本位置信息； client发送写数据给所有副本服务器，先缓存起来； client发送写命令给主副本服务器，主副本服务器对写命令排序后发给所有二级副本服务器，二级副本服务器响应给主副本服务器；主服务器响应给client
添加操作
应用程序发出请求client 解释请求，发送给master ；master 返回句柄和副本位置； client 吧要写入的数据推入各个副本； primary 服务器检查是否超出块规模，超出则扩充到最大规模，副本服务器同样扩充规模，并通知client 在下一个块尝试；如果没有超出规模，则副本在同样偏移处写数据，并报告client操作成功。
Chord 分布式哈希
https://www.cnblogs.com/gnuhpc/archive/2012/01/13/2321476.html
先判断代餐找的K是否在后继节点上，若在successor上，则返回 否则对路由表每一项自底向上：判断该机器是否在K和当前节点之间，若在则到该表项中继续查找，否则继续向上查找。 注意：递归结束条件是：在后继节点中找到。
