Yuchen You

分布式事务系统 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); 问题: 如果一个任务的彩票数量很少, 为什么不 ...

背景 并行计算的效果, 取决于创建和管理并行的开销; 开销大的话即使 coarse grained parallelism 也不划算; 开销小的话, 即使 fine grained parallelism 也划算; 传统 UNIX 进程 = 单地址空间 + 单执行流; 设计目标是单核多道程序环境(multiprogramming), 适合粗粒度并行, 不适合细粒度并行; 线程支持的两种方式 用户级线程 (User-level threads) 通过 runtime library 库实现(不改内核); 优点: 性能好: 上下文切换, 创建销毁的代价接近过程调用; 灵活: 可以按语言/应用需求定制; 缺点: 内核对线程不可见, 仍然只认识"进程"; 进程就像虚拟 CPU, 被内核调度到物理 CPU 上; 遇到 I/O 阻塞, 页面缺页, 多道并发 时, 线程库感知不到真实 CPU 情况, 导致性能下降甚至错误; 内核级线程 (Kernel threads) 内核直接提供多线程支持, 每个线程对内核可见, 内核负责调度; 优点: 与 ...