Yuchen You

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) 内核直接提供多线程支持, 每个线程对内核可见, 内核负责调度; 优点: 与 ...

Introduction VMware ESX Server is a thin software layer designed to multiplex hardware resources efficiently among virtual machines. The current system virtualizes the Intel IA-32 architecture In contrast, ESX Server manages system hardware directly, providing significantly higher I/O performance and complete control over resource management. machine addr: real hardware address physical addr: guest OS’s address pmap: data structure for each VM that maps physical addr to machine addr (ppn -> ...

概念 TLB coverage is defined as the amount of memory accessible through these cached mappings, i.e., without incurring misses in the TLB A superpage is a memory page of larger size than an ordinary page (henceforth called a base page).

Visibility 可见性 这是分布式设计的一个核心概念, 也就是只有让用户看到的结果才是重要的, 无所谓系统内部在某一个时刻某一个进程/node 的状态是什么样的 这篇笔记在讨论主备复制的情况的时候, 我们的目标是在拥有 2 台主机(不一定都可用)的单位分布式系统中维持 one fault-tolerant, 也就是说允许一个节点失败, 但是系统整体不宕机 主备复制 (Primary/Backup Replication) 基本机制 (Mechanism) 客户端请求先到主节点 (primary) client 只需要知道, 也只能知道主节点 visibility/external consistency: 外部用户能看到的集群整体的状态, 集群内部的信息同步和交互以及 failure 不需要暴露给用户 这里还有一层意思就是允许 primary-backup inconsistency. 主节点更新后, 同步给备份 (backup) 如果要确保高度的一致性, 那么就要在 client 提交请求之后完全完成 client -> primary -> ba ...