IntroOLTP and OLAP众所周知，数据库有两种典型使用场景，OLTP 和 OLAP。线上服务与 OLTP 数据库交互，OLTP 数据库再被异步地导出到 OLAP 数据库中作离线分析，如下图所示： OLTP 数据库就是 OLAP 数据库的前端，通过 ETL 的过程，OLTP 数据库中的数据将被清理、重新整理到 OLAP 数据库上。OLAP 数据库为用户提供复杂的数据查询、分析能力，帮助公司：分析过去和预测未来。 Star Schema vs. Snowflake SchemaETL 的过程并不只是简单地移动，通常还会涉及表结构的重新整理，以提高后续查询分析的效率。最常见的两种 schema 就是 Star Schema 和 Snowflak Schema： Star Schema 就是一个星形拓扑结构，处在最中间的是 Fact Table，通常记录着业务流程中的核心事件、指标，如成单记录；处在四周的是 Dimension Tables，记录一些补充信息。Fact Table 通过外键与 Dimension Tables 关联，用户可以通过简单的 Join 来分析数据。在 ...

上节课我们介绍了分布式事务的去中心化实现： 应用程序要发起一次事务时，先通过某种方式选择这个事务的 master node，并向它发送事务开始的请求。 master node 同意后，应用程序向事务涉及的节点发送数据更新请求，此时每个节点都只是执行请求但尚未提交。 master node 收到所有节点的响应后，向 master node 发送事务提交的请求，master node 再问其它节点是否可以安全提交。若是，则确保所有节点提交事务后由 master node 返回成功，若否，则确保所有节点回滚成功，同时由 master node 返回失败。 但上节课我们没有讨论如何确保所有节点都认同事务提交，所有节点在同意之后实际执行了提交。这里有很多细节需要考虑： 如果一个节点发生了故障怎么办？ 如果这期间节点之间消息传递延迟了怎么办？ 我们是否需要等待所有都节点都同意？如果集群较大等待时间就会由于短板效应而增加。 本节我们就来讨论一下这些问题。 Assumption我们首先需要假设在分布式数据库中，所有节点都是好孩子，都受到严格的控制，不会耍坏心眼，让它提交就提交，让它回滚就回滚 ...

当我们在谈论分布式数据库时，首先要明确什么是分布式系统：如果通信成本和通信的可靠性问题不可忽略，就是分布式系统。这也是区分 Parallel DBMS 和 Distributed DBMS 的依据所在 Parallel DBMSs Distributed DBMSs 不同节点在物理上隔得很近 不同节点在物理上可能隔得很远 不同节点通过高速局域网连接 不同节点通过普通公共网络相连接 通信成本很小，基本不会产生问题 通信成本和通信问题不可忽略 那么如何利用我们在这节课中介绍的单节点 DBMS 的知识，构建支持事务的 Distributed DBMS 呢？之前讨论过的很多话题： Optimization & Planning Concurrency Control Logging & Recovery 在分布式环境下都可能遇到新的挑战。 System ArchitectureDistributed DBMS 的系统架构主要指的是在哪一层上共享资源，主要分为以下 4 种： 实际上 Shared Everything 就没有分布式可言了，因此严格来说，只有 Shared M ...

上节课介绍到，故障恢复算法由两个部分构成： 在事务执行过程中采取的行动来确保出现故障时能够恢复 (上节课) 在故障发生后的恢复机制，确保原子性、一致性和持久性 (本节课) ARIES本节课介绍的是 Algorithms for Recovery and Isolation Exploiting Semantics (ARIES)，由 IBM Research 在 90 年代初为 DB2 DBMS 研发的基于 WAL 的故障恢复机制，尽管并非所有 DBMS 都严格按照 ARIES paper 实现故障恢复机制，但它们的思路基本一致。 ARIES 的核心思想可以总结为 3 点： Write-Ahead Logging (WAL) 在数据落盘之前，所有写操作都必须记录在日志中并落盘 必须使用 Steal + No-Force 缓存管理策略 (buffer pool policies) Repeating History During Redo 当 DBMS 重启时，按照日志记录的内容重做数据，恢复到故障发生前的状态 Changes During Undo 在 undo ...

数据库在运行时可能遭遇各种故障，这时可能同时有许多正在运行的事务，如果这些事务执行到一半时故障发生了，就可能导致数据库中的数据出现不一致的现象： 这时就需要故障恢复机制来保证数据库的原子性、一致性、持久性。故障恢复机制包含两部分： 在事务执行过程中采取的行动来确保在出现故障时能够恢复 (本节课) 在故障发生后的恢复机制，确保原子性、一致性和持久性 (下节课) 本节主要内容包括： Failure Classification Buffer Pool Policies Shadow Paging Write-Ahead Log Logging Schemes Checkpoints Failure Classification世上并不存在能够容忍任何故障的容错机制，即便做了异地多活，一次小行星撞地球也能将你的系统一举歼灭，因此在讨论故障恢复之前，我们必须先为故障分类，明确需要容忍的故障类型。 一般故障类型可以分为 3 种： 事务故障 (Transaction Failures) 逻辑错误 (Logical Errors)：由于一些内部约束，如数据一致性约束，导 ...

简介简而言之，实现 MVCC 的 DBMS 在内部维持着单个逻辑数据的多个物理版本，当事务修改某数据时，DBMS 将为其创建一个新的版本；当事务读取某数据时，它将读到该数据在事务开始时刻之前的最新版本。 MVCC 首次被提出是在 1978 年的一篇 MIT 的博士论文中。在 80 年代早期，DEC 的 Rdb/VMS 和 InterBase 首次真正实现了 MVCC，其作者是 Jim Starkey，NuoDB 的联合创始人。如今，Rdb/VMS 成了 Oracle Rdb，InterBase 成为开源项目 Firebird。 MVCCMVCC 的核心优势可以总结为以下两句话： Writers don’t block readers. 写不阻塞读 Readers don’t block writers. 读不阻塞写 只读事务无需加锁就可以读取数据库某一时刻的快照，如果保留数据的所有历史版本，DBMS 甚至能够支持读取任意历史版本的数据，即 time-travel。 Example #1事务T_1和T_2分别获得时间戳 1 和 2，二者的执行过程如下图所示。开始前，数据库存有数 ...

上节课介绍的 2PL 是悲观的并发控制策略，本节课介绍的 Timestamp Ordering (T/O) 则是一个乐观的策略，其乐观表现在事务访问数据时无需显式加锁。T/O 的核心思想就是利用时间戳来决定事务之间的等价执行顺序： 如果 TS(T_i)

上节课介绍了通过 WW、WR、RW conflicts 来判断一个 schedule 是否是 serializable 的方法，但使用该方法的前提是预先知道所有事务的执行流程，这与真实的数据库使用场景并不符合，主要原因在于： 请求连续不断。时时刻刻都有事务在开启、中止和提交 显式事务中，客户端不会一次性告诉数据库所有执行流程 因此我们需要一种方式来保证数据库最终使用的 schedule 是正确的 (serializable)。不难想到，保证 schedule 正确性的方法就是合理的加锁 (locks) 策略，2PL 就是其中之一。 Lock TypesDBMS 中锁通常被分为两种，Locks 和 Latches，二者的主要区别如下： Locks Latches Separate User transactions Threads Protect Database Contents In-Memory Data Structures During Entire Transactions Critical Sections Modes Shared, ...

背景引入在前面的课程中介绍了 DBMS 的主要模块及架构，自底向上依次是 Disk Manager、Buffer Pool Manager、Access Methods、Operator Execution 及 Query Planning。 但数据库要解决的问题并不仅仅停留在功能的实现上，它还需要具备：（1）满足多个用户同时读写数据，即 Concurrency Control，如：两个用户同时写入同一条记录。（2）面对故障，如宕机，能恢复到之前的状态，即 Recovery，如：你在银行系统转账时，转到一半忽然停电。Concurrency Control 与 Recovery 都是 DBMS的重要特性，它们渗透在 DBMS 的每个主要模块中。而二者的基础都是具备 ACID 特性的 Transactions，因此本节的讨论从 Transactions 开始。 Transactions用一句白话说，transaction 是 DBMS 状态变化的基本单位，一个 transaction 只能有执行和未执行两个状态，不存在部分执行的状态。一个典型的 transaction 实例就是：从 A ...

背景SQL 语句让我们能够描述想要获取的数据，而 DBMS 负责来根据用户的需求来制定高效的查询计划。不同的查询计划的效率可能出现多个数量级的差别，如 Join Algorithms 一节中的 Simple Nested Loop Join 与 Hash Join 的时间对比 (1.3 hours vs. 0.45 seconds)。 Query Optimizer 第一次出现在 IBM System R，那时人们认为 DBMS 指定的查询计划永远无法比人类指定的更好。System R 的 optimizer 中的一些理念至今仍在使用。 查询优化技术Heuristics/Rules Rewrite the query to remove stupid/inefficient things Does not require a cost model Cost-based Search Use a cost model to evalucate multiple equivalent plans and pick the one with the lowest cost 上图为查 ...