引论

  • 目的:资源共享与协同计算
  • +分布式系统:仅通过交换消息而完成通信和协作的连接网络的计算机集合。
  • 特点
    • 并发
    • 没有全局时钟
    • 独立故障(一个进程的故障不会被别的进程知晓)
  • ?+挑战
    • 异质性
    • 开放性
    • 安全性
    • 可扩展性
    • 错误处理
    • 并发性
    • +透明性
      • 并发透明性
      • 拷贝透明性
      • 故障透明性
      • 性能透明性
      • 移动透明性
      • 规模透明性
    • 服务质量

系统模型

物理模型

  • 基线物理模型:联网计算机上的硬件和软件组分通过发送信息来完成联系和协作

三代分布式系统

早期 互联网级 现代
规模 极大
异质性 有限 在平台、语言和中间件方面显著 在多个维度上产生了彻底不同的架构
开放性 不是重点 在一些标准中是重点 在现存标准中是主要的研究挑战,但是尚未能用于复杂系统
服务质量 早期 在一些标准中是重点 在现存标准中是主要的研究挑战,但是尚未能用于复杂系统

架构模型

架构元素
  • 通信实体:通常是进程;但是对于传感器网络为结点、对于一些环境为线程
  • 通信范例
    • 进程间通信:低级支持,通过IP协议的直接API访问
    • 远程调用:支持双向交互,包括请求-回复协、原称过程调用,远程方法触发
    • 间接沟通:通过组通信(广播和组播)、发布-订阅系统(基于事件)和消息队列完成沟通
  • 角色和义务
    • CS架构
    • P2P
  • 放置
    • 多服务器提供服务
      • 分开放置资源
      • 不同主机分别维护资源的单独拷贝
    • 代理服务器和缓存
    • 移动端代码(小程序)
架构模式
  • 分层:服务集合的纵向组织
    • 平台:最底层,用于分布式系统和应用的软硬件层
    • 中间件:一个软件层,掩盖异构性并为应用程序程序员提供方便的编程模型
  • 垂直组织的分布式系统:UI-应用服务器-数据库服务器
  • 横向组织
    • 瘦客户端:提供最小的UI层,其他事情交给服务器
    • 胖客户端:客户端包含应用逻辑和UI,服务器只负责权限控制和储存

基础模型

交互模型
  • 通信信道的评估
    • 延迟
    • 带宽
    • 抖动(稳定性)
  • +两类交互模型
    • 同步:确定的执行、传输时间,确定的时钟偏移
    • 异步
故障模型

故障模型定义了可能发生故障的方式,以便于提供对故障影响的理解。

  • 遗漏故障:消息未正常收到(可能根本没发送)
  • 任意故障:什么都可能发生
  • 计时故障:主要是超时
安全模型

可以通过保护用于交互的进程和信道,并保护它们封装的对象,以此来屏蔽未授权的访问。

+时钟和时序

时钟基础

  • 计算机使用一个计数器和一个寄存器来维护时钟。OS通过中断信号来维持系统时间。
  • 时钟漂移:一段时间内时钟记录的时间与真实时间之间的误差
    • 修复:如果快了,则调慢时钟直至同步(利用OS);反之亦然
  • 时钟偏移:同一时刻两个不同时钟间的差距

时钟同步

  • 从顶级来源(GPS等)
  • 从服务器
    • +Cristian算法:T=TServer+RTT2T=T_{Server}+\frac{RTT}{2}, 其中RTT为本地的请求发送和接收的时间差。精度±RTT2\pm\frac{RTT}{2}(信息传播时间未知)或±(RTT2Tmin)\pm(\frac{RTT}{2}-T_{min}),其中TminT_{min}为信息的最短传播时间。
    • 伯克利算法
    • NTP

+伯克利算法

  1. 主机定期拉取所有从机的时间
  2. 主机计算所有从机时间和自身的平均。计算平均的值不会包含“显然不对”的时间。
  3. 主机向各从机发送偏移量来调整时间

+NTP

设定A向B同步时间时:

  • Ti3T_{i-3}: A发送到B的时间
  • Ti2T_{i-2}: B收到A消息的时间
  • Ti1T_{i-1}: B发送回复的时间
  • TiT_{i}: A收到B回复的时间

则A同步为:

Ti+(Ti2Ti3)+(Ti1Ti)2T_{i}+\frac{(T_{i-2}-T_{i-3})+(T_{i-1}-T_i)}{2}

误差区间:

(TiTi3)(Ti1Ti2)2\frac{(T_i-T_{i-3})-(T_{i-1}-T_{i-2})}{2}

事件时序

  • aba\rightarrow b:a会影响b的输出,如果a先于b在同一过程中,或者a会发送给b消息。具有传递性。
  • aba||b:a,b互无影响

Lamport算法

设各进程PiP_i有逻辑时钟LiL_i,则可以通过以下算法同步时钟:

  1. 初始化LiL_i为0
  2. 更新LiL_i:
    • 对于PiP_i上的每一个新事件,LiL_i自增1;
    • 对于PiP_i发送的每一条消息mm,设定tm=Lit_m=L_i;
    • 对于PjP_j收到的每一条消息m,设定Lj=max(Lj,t)L_j=max(L_j,t),然后LjL_j自增。

向量时钟

设各进程PiP_i有向量时钟ViV_i,则可以通过以下算法同步时钟:

  1. 初始化ViV_i0
  2. 更新ViV_i:
    • 对于PiP_i上的每一个新事件,Vi[i]V_i[i]自增1;
    • 对于PiP_i发送的每一条消息mm,设定tm=Vit_m=V_i;
    • 对于PjP_j收到的每一条消息m,对每一位设定Vj=max(Vj,t)V_j=max(V_j,t),然后Vj[j]V_j[j]自增。
定理
  • abV(a)<V(b)a\rightarrow b \Leftrightarrow V(a)\lt V(b)
比较问题
  • V=VV[i]=V[i]V=V' \Leftarrow V[i]=V'[i]
  • VVV[i]V[i]V\le V' \Leftarrow V[i] \le V'[i]
  • V<VVV&VVV\lt V' \Leftarrow V \le V' \And V\neq V'

+互斥算法与选举算法

互斥算法

互斥算法的需求

  • 安全性:任何情况下,只有一个进程可以执行
  • 活泼性:无死锁,无饥饿(?)
  • 公平性

集中式算法

  • 模拟单进程系统
  • 一个进程作为协调员

过程:

  1. 请求资源
  2. 等待请求
  3. 获得许可
  4. 访问资源
  5. 释放资源

优点:

  • 公平性
  • 易实现、理解、验证
  • 进程只需知道协调员,而无须知道其它组员

缺点:

  • 单点故障
  • 集中式服务器可能成为性能瓶颈

令牌环算法

  • 假定组员已知、有序
  • 在软件层面,构建逻辑上的环
  • 各节点和邻居联系
  1. 进程0初始化令牌
  2. 令牌传递
  3. 拥有令牌的进程,可以选择占用令牌和资源

优点:

  • 不会导致饥饿

缺点:

  1. 无法满足先到先得
  2. 令牌丢失

+Ricart & Agrawala算法

  • 基于可信赖组播和逻辑时钟
  • 证明完全分布式算法是可能的

过程:

  • 需要占用资源的进程广播信息,包含:
    • 自身标识符
    • 资源名称
    • 时间戳
  • 等待所有其它的‘肯定’回应
  • 使用资源

对于收到请求的进程:

  • 如果不感兴趣:回复OK
  • 如果正在使用:不回复,将请求加入队列
  • 如果也请求了:比较时间戳,先到先得。
  • 使用完成后:向队列中的请求发送OK

缺点:

  • 多点故障
  • 大量的信息交互

+Lamport互斥算法

  • 每个进程维护一个请求队列,其中包含互斥请求

请求资源时:

  • 进程Pi向所有节点发送请求(i,Ti)
  • 该请求也被加入他自己的队列中
  • 对于收到请求的进程,它发送一个包含时间戳的ACK

进程访问资源,当且仅当:

  • Pi收到了来自所有其它进程的消息(ACK或释放信息),其时间戳大于刚才的请求
  • Pi的请求在其请求队列中,拥有最小的时间戳
与Ricart & Agrawala的区别
  • 每个节点总是回复ACK,而无须延迟等待
  • 进程是否访问资源取决于其请求是否是在队列中最早的
释放

释放时:

  • 将请求从自身请求队列中移除
  • 发送带时间戳的释放信息

收到“释放”消息时:

从队列中移除指定请求。

选举算法

  • 需要选出一个进程作为协调者
  • 进程间的角色无法区分
  • 每个进程都有一个UID来识别

霸道选举算法

  • 选取具有最大ID者为协调者
  • 当进程P检测到协调者已死亡时,向所有具有更大ID的进程发送选举信息
  • 如果无人回应,则P作为新的协调者
  • 否则,新的协调者选出,它需要向所有进程广播自己是新的协调者
  • 一个死进程恢复时,他会举办选举产生新的协调者

环选举算法

  • 进程环形安置
  • 当任意进程检测到协调者离开时,
    • 构建包含PID的选举消息,并发给下一进程
    • 如果下一个进程已经离开,就跳过他
    • 重复,直到找到活的“下一进程”
  • 收到选举消息时,
    • 传递消息,其中也加上了他自己的PID
  • 最终,消息回到最初的发送者处,然后选出调度者

+Robert&Chang算法

  • 优化的环选举算法,避免多次巡回选举
  • 当一个进程收到选举消息后,比较消息中和自身的PID:
    • 消息>进程,则继续转发
    • 消息=进程,则本进程已经称为协调者,向其它进程发布
    • 消息<进程
      • 本进程未成为参与者:用自身PID替换消息PID,然后转发
      • 本进程已成为参与者:丢弃之

计 算 机 网 络

复 习 以下内容

  • TCP/UDP
  • IP
    • 数据包
    • 子网/编址
    • 路由协议
    • 组播
  • DNS

+RPC

  • 消息交换发生于本地存根和服务器架构间,使得RPC看起来像一个本地的过程调用
  • 客户端程序-本地存根-网络例程-服务器架构-服务例程

步骤:

  1. 客户端调用本地存根,参数入栈
  2. 本地存根对参数编码、发消息并系统调用
  3. 消息发送到服务器
  4. 消息分发至服务器骨架,并解阻塞服务器
  5. 服务器骨架使用参数调用本地例程(本地调用)
  6. 例程返回值到服务器骨架
  7. 服务器骨架返回值、发消息并系统调用
  8. 返回值消息发送回客户端
  9. 消息分发至客户端存根
  10. 客户端存根返回值给应用

DNS

  • 初级服务器:直接从本地主文件读取域信息
  • 次级服务器:从初级服务器下载,并维持信息最新
  • 服务器的三条数据文件
    • 命名解析文件:域名到IP
    • 反向翻译文件:IP到域名
    • 缓存文件:缓存之前的查询数据
  • nslookup

+群组通信

  • 单播:1对1
  • 任播:1到任意附近节点,由IPv6引入,由BGP协议使用
  • 组播
  • 广播:1到全部

设定

  • 闭合和开放:闭合群组只有组内消息
  • 对等和分层
  • 分布式与集中式
  • 离开和加入:必须是同步的
  • 容错性

组播实现

  • 硬件组播:组成员监听特定地址
  • 广播:广播到所有客户端,然后软件层面过滤
  • 以太网支持组播和广播;限定于本地域
  • 多重单播:发送者知道组成员,软件实现
  • 分层实现:发送者发送给组长,组长知道所有组成员

组播可靠性

原子性的组播

  • 如果任意成员未收到,则没有成员能收到

问题:

  • 不可靠的网络环境
  • 每一个消息都应该被确认
  • 确认消息可能被丢失
  • 消息发送者可能已经终止

可靠的组播

  • 任何无故障的组员都能收到消息
  • 假定发送者和接收方都在线
  • 网络可能波动,因此会重试,但最终可能放弃
  • 允许部分组员不收到消息
  • 反馈可能导致内爆
+反馈的优化
  • 流水线
  • 累积确认
  • 回传消息携带ACK
  • 使用NAK

不可靠的组播

  • 最好的性能
  • 基础组播

+消息顺序

  • 全局时钟顺序:所有消息都以完全确定的顺序分发(几乎不可能实现)
  • 全序:所有的消息组组员间以相同顺序分发(分发队列排序)
    • 附加全局序列的消息ID
    • 仅当一个分发接收者收到所有之前消息时,它会分发当前消息
  • 因果顺序(偏序):如果两个消息间具有因果关系,那么它们之间是有序的;
    • 各个线程维护优先权向量(类似时间戳向量)
    • 如果m’取决于m,则所有进程必须先于m’分发m
    • 在组播发送和接受事件时更新向量
  • 同步顺序:消息可能以任意顺序到达,但是保证现有已排队的消息的派发先于任何其他消息被接受
  • 单源FIFO顺序:来自单个源头的消息按照他们的发送顺序被派发
  • 无序组播

偏序维护算法

  • PbP_b发送消息时,它更新向量中自己的字段并发送向量
  • PaP_a接收到来自PbP_b
    • 按照FIFO顺序,检测来自PbP_b的消息,是否Vb[b]=Va[b]+1V_b[b]=V_a[b]+1
    • 检查是否i,ia,Va[i]Vb[i]\forall i, i\not ={a},V_a[i]\le V_b[i]
    • 若均满足,则更新Va[a]++V_a[a]++然后派发消息
    • 否则,等待直到这些条件满足

PIM独立组播协议

  • 组播路由协议,用于在路由器间分发包
  • 拓扑结构由其他协议控制

密集模式(洪泛式)PIM-DM

  • 向所有的邻居路由器中继包
  • 逆向路径转发(RPF):防止路由循环
  • 浪费资源
  • 如果包被大部分地方需求,那么很好用

稀疏模式PIM-SM

  • 由接受者发起
  • 每个路由器需要使用PIMJoin消息来请求一个组播种子
    • 被终点路由器使用IGMPJoin发起
    • Prune消息终止

一致性和复制

  • 从多客户端访问情况下保护数据
  • 对已复制数据的更新具有原子性
  • 这些数据应该是同步的

一致性模型

  • 不基于同步操作
    • 严格一致性:所有共享访问具有绝对时序
      • 任何读取都能获得最新值
      • 理想模型,不可能存在
    • 线性一致性:所有进程必须能观测到相同的共享访问序列;各访问由一个全局但是非独特的时间戳排序
      • 写能立即同步,读能读到最新
      • 所有操作好像按照时间顺序发生在一个副本上
    • 序列一致性:所有进程必须能观测到相同的共享访问序列;但是排序并不依照时间
      • 写能立即同步,读能读到最新
      • 毋须按照时间顺序
    • 因果一致性:排序依照因果相关顺序
      • 只保证有因果关系的操作的一致性
    • FIFO一致性:所有进程能看到按发出顺序排序的单个进程写操作序列;然而来自不同进程的写入可能并不总是相同
  • 基于同步操作
    • 弱一致性:只有完成同步后,才能指望共享数据保持一致
    • 释放一致性:退出关键区域时(资源释放),共享数据将保持一致
    • 进入一致性:进入关键区域时,与关键区域有关的共享数据将保持一致

以客户端为中心的一致性

  • 最终一致性:如果一段时间内没有更新数据操作,则各副本逐渐一致化

四条原则

  • 单调读一致性
  • 单调写一致性
  • 写后读一致性(Read your writes):同一个进程读取到的内容和他在此前写入的一致
  • 读后写一致性(Writes follow reads):在写入前读取

传播方法

  • 基于推送:服务器储存客户端副本和缓存,发出更新消息
  • 基于拉取:服务器无状态

一致性协议

  • 基于主数据的协议:数据存储中的每个数据项x都有一个关联的主数据,它负责协调对x的写操作
  • 重复写协议:写入操作在多个副本上进行
  • 缓存一致性协议:客户端控制一致性

+(15)文件系统

  • 文件系统提供了构建其它信息系统的最基本服务
  • 文件系统使用磁盘块来组织磁盘操作

UFS

内部文件结构

  • 每个文件具有一个i-node
    • 文件标识符(12B,所有者、权限、大小)
    • 数据索引(4B*13)
    • 总大小64B
    • inode#引用

目录文件

  • 目录文件是通常的文件,他们包含从名称到i-node的映射条目。
  • 解析路径时,递归查询:
    • 获取inode#
    • 读取inode
    • 加载内容

超级块

  • 每个文件系统都有
  • 包含系统总大小、剩余空间、缓存的块号、下一个空余块号、i-node区指针、空余i-node数量、缓存的空余i-node指针、下一个i-node序号
  • 通常在系统启动的时候被加载到内存

地址计算

数据块
  • 簇数=块号*(簇每块)
  • 盘号=簇数/(簇每盘)
  • 磁道=((簇数)%(簇每盘))/(簇每道)
  • 块号=簇数%(簇每道)
i-node
  • 块号=(inode号-1)/(inode每块)+inode区起始地址
  • 字节偏移量=((inode号-1)%(inode每块))*inode大小

挂载

  • 当内核解析路径时,通过inode可以判定挂载点,并获取挂载表
  • 挂载表包含超级块地址,和指向根inode的指针
  • 通过这些数据可以访问被挂载的文件系统的根inode,剩下的文件名解析会依赖被挂载系统
  • 自动挂载:每10分钟重连,守护者进程

链接

  • 链接不能跨文件系统
  • 链接在目标文件的目录增加了新条目

DFS

  • 位置透明性
  • 并发透明性
  • 故障透明性
  • 异质性
  • 可扩展性

组件

  • 平面文件服务:提供一系列简单的通用操作,用于访问文件和其标识符,由UFID索引
  • 目录服务:映射文件名为UFID
  • 客户端模块:使用API访问文件和目录服务

操作

  • read(ufid,i,n)=>Data
  • write(ufid,id,Data)
  • create=>ufid
  • delete(ufid)
  • getAttributes(ufid)=>attr[]
  • setAttributes(ufid,attr[])
  • Lookup(dir,name)=>ufid
  • AddName(dir,name,ufid)
  • UnName(dir,name)
  • GetNames(dir,pattern)=>name[]:获取指定目录下的文件

基于客户端模块的分级文件系统

  • 目录树的根位于一个周知UFID
  • 路径名解析函数位于客户端模块

访问控制

  • 客户端和服务器基于RPC联络,这可能会导致安全问题
  • 依赖于UFID的访问限制包括文件位置(组ID)、FID和权限控制三个字段,由目录服务器基于客户端ID和权限生成
  • 包含一个防止其被非法更改的加密字段。加密密钥通常由目录服务器和文件服务器共享。

文件表示

  • 类似inode的index block被用于每个文件,来指示数据库
  • index block的定位基于UFID
    • 因为规模问题,使用B-树解决查找问题
  • UFID中也包含了服务器位置

空间残余

  • 孤儿文件的处理问题
  • 该问题被大部分系统忽略
  • 生命周期可以解决该问题

NFS

  • 基于NFS和mount协议工作
  • 无状态、可信赖的文件操作
  • 引入VFS层

VFS层(虚拟文件系统)

  • 为每个挂载和打开了的文件维护v-node,即虚拟inode
  • vnode不存在于磁盘,而是由OS维护。他决定文件在本地还是远程
    • 对于本地文件它包含inode
    • 对于远程,它包含FSID、inode号码、inode版本号

DFS和独立FS的差异

  • 拆分的文件服务和目录服务
    • 将目录服务从文件服务器上解离
  • 无状态的服务器与客户端模拟
    • 文件服务器变得轻量化
    • 服务器更易于高效的从错误恢复
    • 客户端模块模拟了传统的FS接口
  • 可重复的操作
    • 文件操作具有幂等性,允许被应用至少一次RPC调用
    • 操作create是可预料的,但是对用户而言没有副作用

++事务处理系统

复 习以下内容(数据库):

  • 事务和并发控制

2PL必要性

  • 当脱离锁区域后,数据就离开了控制范围,从而可能被更改(读、写不在一个锁区域内)

网络搜索技术

搜索引擎架构

  1. 爬虫:自动从URL开始迭代检索网页(BFS)
  2. 索引器:用关键字为文档建立索引
  3. 数据库
  4. 搜索引擎:返回最相关的文档

网络图

  • 节点:网页
  • 边:一个网页到另一网页的链接
  • 节点内容:与网页相关的内容

具有动态性:

  • 对于部分节点,出边不可知
    • 存在尚未处理的节点
    • 新的边可能已经添加
  • 对于所有节点,存在一些未知的入边

FAN:网页评级

  • 反向链接数越多越好
  • 反向链接来源的等级越高越好

倒排索引:加速检索

  • 建立从单词到FID的反向文件映射
  • 可以加速检索