Yuchen You

简单介绍 最终一致性位于一致性谱系的末端, 比线性一致性(Linearizability), 顺序一致性和因果一致性都要弱; 如果对某一数据项不再有新的更新写入, 那么在经过一段时间后, 所有未来的读取操作都将反映最新的写入结果 没有时间限制: 系统对收敛到一致状态所需的时间没有界限,;这个时间长短取决于通信模式的可用性(例如, 如果节点长期不通信, 收敛时间就会很长); 保证最终顺序: EC 仍然要求更新最终以相同的顺序应用到所有副本上,;这通常是通过逻辑时钟等机制来实现的, 允许更新先作为临时更新本地应用, 然后在同步时根据逻辑时间戳进行回滚和重放,; Bayou 模型 (SOSP 1995) 没有中心化存储: 所有的节点都被视为客户端,; 始终接受更新: 客户端总是接受用户发出的更新操作, 这保证了高可用性和活性; 日志记录: 所有更新都会被记录在本地日志中; 点对点同步: 客户端之间会定期进行 成对(pair-wise) 的更新交换; 临时更新: 更新通常是暂时的(tentative), 可以解决它们之间的冲突; 举例说明最终一致性 假设有一个房间日程安排应用程序(Ro ...

分布式系统的不稳定性 综合我们前几个章节的内容, 我们可以总结出分布式系统中的不稳定性主要源于以下几个方面: 故障模型 (Failure Model) 在这个模型中, 对节点和网络特性的定义如下: 节点(Nodes): 它们可以无限期地失败; 它们在恢复时不会丢失持久状态; 对任何特定的计算, 它们都没有时间限制; 网络(Network): 网络可以丢弃 drop 或延迟 latency 消息; 消息可能被无限期地延迟; 网络也可能对消息进行重新排序; 异步模型 (Asynchronous Model) 上述的故障模型被称为异步模型; 在该模型下, 核心挑战在于: 无法区分 Failure 与 Slow: 在一个异步模型中, 你通常无法区分失败(例如, 请求被丢弃或远程节点死亡)和极度缓慢(例如, 网络或节点速度很慢, 响应只是尚未到达); No response 的含义: 缺少响应可能意味着请求被丢弃, 远程节点已死, 或响应被丢弃;但这也可能仅仅意味着网络或节点非常慢, 并且响应仍在路上; 也就是这些都 Not Distinguishable (无法区分); F ...

分布式事务系统 Distributed Transaction 根据分布式数据库系统的类似要求, 我们设计的分布式系统要支持 ACID 准则: Atomicity (原子性): 事务要么全部完成, 要么全部不做; Consistency (一致性): 事务执行前后, 数据库必须处于一致状态; Isolation (隔离性): 并发执行的事务彼此隔离, 互不干扰; Durability (持久性): 一旦事务提交, 其结果是永久性的, 即使系统崩溃也不会丢失; 如何区分 Linearizability 和 Serializability? Linearizability (线性一致性): 每个操作看起来像是瞬间发生的, 并且所有的 read 都会反映已经发生的所有 write 的结果 Serializability (可串行化): 并发执行的事务的结果与某个串行执行的顺序相同 Strict Serializability: 结合了线性一致性和可串行化的概念 也就是外界看到的顺序和实际执行的顺序是一致的 Isolation 问题与二相锁 (2PL) 一个常见的 i ...

ACID 准则 在讨论支持并发的文件系统 (包括 482 p4 NFS, DBMS 等) 的时候, 我们往往会提到一个非常核心的准则: ACID 准则. Atomicity (原子性): 事务是一个不可分割的工作单位, 要么全部完成, 要么全部不做; Consistency (一致性): 事务的执行必须使数据库从一个一致性状态转变到另一个一致性状态; Isolation (隔离性): 并发执行的事务彼此之间是隔离的, 一个事务的中间状态对其他事务不可见; 两个事务并发的时候不能互相冲突 Durability (持久性): 一旦事务提交, 它对数据库的修改就是永久性的, 即使系统崩溃也不会丢失. 更多是从 recovery 恢复角度来讲的, 也就是尽量能在任何崩溃情况下都不丢数据;具体看 [Logging](#Log 日志结构) 章节和 Recovery 章节 并发控制的数据库系统 并发控制与隔离性的基础 事务 (Transaction): 事务是 DBMS 中变化的基本单位;它是在数据库上执行的一系列操作(如 SQL 查询), 以完成某种高级功能; 事务的抽象视图 ...

Database Storage Disk-Based Architecture(磁盘架构) DBMS 假定数据库的主存储位置在非易失性磁盘 (Disk / SSD); 系统组件负责在 volatile memory(主存) 与 non-volatile storage(磁盘) 之间移动数据; Storage Hierarchy(存储层次) CPU Registers < CPU Cache < DRAM < SSD < HDD < Network Storage 越靠上速度越快, 容量越小, 成本越高; DBMS 设计目标: 最大化利用高速层, 最小化慢速访问; 为什么不直接用 OS 管理存储 虽然可以用 mmap() 将文件映射到内存, 但: DBMS 无法控制 page replacement 策略; OS 不保证 flush 顺序; 并发写入下可能引发不可控的 page fault; 因此 DBMS 自己实现 Buffer Pool, Page Replacement 与 Flush 策略更可控; 常见 OS 辅助机制: madvise: 告 ...

Introduction 上回书我们说到, PB 复制存储的设计对比 Replicated State Machine (RSM) 有 Fault Tolerant 方向的极大优点, 也就是 RSM 在某个节点卡住的时候会导致整个系统卡顿, 因为 RSM 利用了 Lamport Clock 逻辑顺序的 握手机制来达到实际上的全局一致顺序, 如果局部卡死我们这里的握手就无法达成, 逻辑链就断掉了 但是 PB 肯定也有其缺点 不然为什么还要特意讲讲 RSM, 在我们实现了 PB 设计的原理基础上, 让我们来看看 PB 设计的缺点: PB 同步链路失效: 这样其实就卡死了, 因为 priamry 一定要同步给 backup 但是由于 link 挂了, 整个同步就无法成立 Primary Push 过程失效: 如果 primary 在 push 的时候挂了, 那么 backup 永远收不到更新, 也就永远无法同步 因此我们折中派就要考虑如何优化 RSM 来修复 PB 的这两个问题了, 而且 RSM 在带宽上肯定是更有优势的 (每个 RSM node 都可以接收外来请求) 设计目标 (从整个 ...

本文是针对 UMich EECS491 (这课抄了致敬 MIT CS 6.824) 的 project2 的设计思路和实现的总结, 也可以作为一般的 primary-backup 1-fault-tolerant distributed storage system 的设计参考. 本文不会涉及具体的实现细节, 只会涉及一些 high-level 的设计思路 如果有 JI/GC 同学当了 IA/GSI 希望不要举报我 Lexical Confinement: 串行逻辑链 在分布式系统的高并发请求中并不会完全像我们在单机操作系统中看到的 performance 是最重要的, 在分布式系统中 consistency 才是最重要的, 为了避免各种不同步的分布式 failure 导致的不一致问题以及编码实现的复杂性, 我们可以通过串行化的方式来简化 回忆 Go 语言设计中非常重要的 CSP 模型: Sharing Memory by Communicating, not Communicating by Sharing Memory 也就是要利用 channel 机制来实现不同线程之间的数据 ...

Design for File Systems of the 1990’s 文件系统的设计受到两种力量驱动: 技术 (Technology): 提供基本的硬件能力与性能边界; 工作负载 (Workload): 决定系统需要高效完成的操作类型; 本节总结了 1990 年代的技术变迁及其对文件系统设计的影响, 并说明为何当时的传统文件系统难以适应这些变化, 从而引出了 Sprite LFS(Log-Structured File System) 的设计动机; 2.1 技术背景 (Technology) 1. 处理器 (Processors) CPU 性能以近乎指数级速度提升, 并将持续很长一段时间; 这种提升迫使系统中其他组件(如磁盘, 内存)也必须加快, 否则系统整体性能会"失衡"; 2. 磁盘 (Disks) 磁盘技术的主要改进集中在 成本与容量, 而非性能; 磁盘性能包含两个部分: 传输带宽 (transfer bandwidth): 可通过磁盘阵列或并行磁头提升; 访问时间 (access time): 受机械结构限制, 几乎无法显著改善; 因此 ...

为什么需要规范化 坏表的典型问题 冗余 redundancy: 比如 供应商地址, 商品描述被重复存储 插入异常: 插入供应商必须附带商品信息, 关联不大的两个信息要一起插入 删除异常: 删除商品时可能导致供应商信息丢失 更新异常: 修改供应商地址需要更新多行 Normalization 目标: 避免冗余, 找到不同属性之间的依赖性和继承关系 Short Summary: We want tables where the attributes depend on the primary key, on the whole key, and nothing but (有且仅有) the key. 不过这个方法完全可以用 ER 来解决, 但是这里讲得是另一种思路, 即更加侧重形式化方法实现 functional dependency 的分析和分解. Redundancy Problems Redundant Storage: 同样的信息被重复存储, 浪费空间 Update Anomalies: 更新时需要修改多处, 容易出错 Insertion Anomalies: 插入新 ...

Lottery Scheduling 基本机制 Resource Rights (资源权利) 彩票 (ticket) 表示资源权利, 具有 三个性质: 抽象 (abstract): 与具体机器细节无关; 相对 (relative): 票所代表的份额随竞争情况 (总彩票数量) 动态变化; 统一 (uniform): 异构资源都能抽象为 tickets; 比如各种 CPU, I/O 设备; Lotteries (抽签调度) 每次调度就是一次抽签, 任务的获胜概率: p=tTp = \frac{t}{T}p=Tt​, 其中 t = 本任务票数, T = 总票数; 获胜次数服从 binomial distribution; 等待第一次获胜的时间服从 geometric distribution; 长期看, 任务的资源份额 ≈\approx≈ 票份额; 因此保证概率公平 (probabilistic fairness); 任何持有 非零 票数的任务都会在有限时间内赢得抽签, 因此不会出现饿死 (starvation); 问题: 如果一个任务的彩票数量很少, 为什么不 ...