Architecture of a Database System

[mrdrivingduck]

fntdb07-architecture.pdf

[mrdrivingduck]

Introduction

数据库系统不仅涉及到数据管理，还涉及应用、操作系统、网络服务。出于一些原因，数据库系统的架构在课本上显得比较笼统：

• 数据库系统的社区很小，市场迫使只有一些高端产品存活了下来；社区里的人员分布也相对紧密
• 数据库在学术上丢失了系统性，课本通常是怎么方便怎么写

对于一个查询来说，其生命周期中流经的模块有：

1. 客户端与 Client Communications Manager 交互（数据消息 + 控制消息）
2. DBMS 的 Process Manager 按资源情况决定是否立刻分配一个服务线程或稍后再分配
3. Relational Query Processor 负责决定用户是否可以执行该查询，如果可以，则将查询编译为执行计划，由执行器执行
4. 执行器中的叶子算子从 DBMS 的 Transactional Storage Manager 中获取数据，其中包括 access method（如何组织和访问数据）和 buffer management（什么数据何时在硬盘和内存之间交换），同时保证 ACID

在此过程中，catalog、memory manager 等子模块需要被全程使用。

[mrdrivingduck]

Process Models

处理模型决定了如何执行用户的并发请求，如何把请求映射到 OS 的进程或线程上。

几个概念：

• 进程：OS 调度，OS 隔离
• OS 线程：OS 调度，OS 进程内不隔离，共享地址空间，稍少的上下文切换开销
• LWT (Lightweight Thread Package)：在用户空间实现的线程库，库代码实现调度，更少的上下文切换，但阻塞操作会阻塞所有线程

把处理用户的实体称为 DBMS worker，那么可以有三种处理模型：

• 每个 DBMS worker 一个进程：
  • 易于实现，复用 OS 的隔离保护和调度，调试工具链丰富
  • 需要使用共享内存
  • 当并发量变大时，多进程会占用大量内存，切换会很吃力
• 每个 DBMS worker 一个线程：
  • 由一个 dispatcher 线程接受用户连接，启动一个线程服务
  • OS 不保护线程之间共享的内存
  • 难以调试
  • 难以移植（不同 OS 对线程的支持不一样，很多 OS 不能很好地支持线程）
  • 并发量变大时，比多进程的扩展性更好
• 进程池（线程池）
  • 分配一个进程池，每个 DBMS worker 使用其中的一个进程，使用完毕后归还
  • 内存使用率更加有效，当连接数增长时扩展性最好

DBMS worker 之间完全的独立是不可能的，因为它们之间至少需要共享数据库。SQL 请求需要把数据从数据库中搬到服务进程中再搬到客户端。其中有着多级的缓存：

• Disk I/O buffer
  • Database I/O request: buffer pool
  • Log I/O request: log manager
• Client Communication Buffers：使用用户连接 socket 或客户端缓存

DBMS Threads

目前的大部分数据库都是在上世纪七十年代到上世纪八十年代期间经历了从学术论文到商业化的过程。在当时，OS 还不能很好地提供线程；就算提供，其实现也五花八门；并且没有很好的性能。直到上世纪 90 年代，OS 才逐渐实现了线程。因此很多 DBMS 要么使用进程模型，要么直接实现了自己的轻量级线程库——其中使用了异步非阻塞接口、调度程序等，从而在减少上下文切换开销的同时获得高性能。相当于把一部分 OS 需要实现的逻辑搬到了 DBMS 中。

Admission Control

为了防止过多的连接打进来，导致 DBMS 性能下降，需要做一些访问控制的工作。

• DBMS 可以通过限制连接数量来做，甚至直接交给更外层的反向代理来做
• DBMS 也可以在查询优化时，根据优化器输出的计划中所需要的资源，和当时系统可用的资源，来决定是否立刻执行一个查询还是延后

[mrdrivingduck]

Parallel Architecture: Processes and Memory Coordination

几种不同的并行架构：

• Shared Memory：多个处理器可以以近乎相同的性能访问 RAM
  • （对 DBMS 来说）透明的 worker 分配（OS 实现）
  • 共享内存数据结构
• Shared Nothing：一个独立的机器集群通过网络连接
  • 集群中的协同完全由 DBMS 实现
  • 系统中的每个节点只保存一部分数据（水平数据分布）
  • 需要实现事务、负载均衡
  • 一台机器下线意味着整个 DBMS 停止，除非使用部分冗余
• Shared Disk：所有处理器能够以相同的性能访问 disk，但是各自的 RAM 独立
  • 较低的管理成本，一个处理进程故障不会影响其它节点的使用
  • 单点故障位于 disk

NUMA (Non-Uniform Memory Access)：共享内存的编程模型，访问本地 RAM 较快，有能力访问远程 RAM 但访问远程 RAM 较慢。

[mrdrivingduck]

Relational Query Processor

1. Query Parsing and Authorization

SQL parser:

1. 检查查询语句是否正确
2. 解析名称和引用
3. 将查询转换为内部格式
4. 认证用户是否有权限执行查询

Parser 首先会将 FROM 子句中的表引用转换为全限定名 server.database.schema.table，然后检查 catalog 中表是否存在。如果存在，则使用 catalog 中的表信息确认引用的属性存在，另外进行一些标准 SQL 的语法检查。最终确认用户有权限执行查询（当然这个操作也可以推迟到查询执行时进行，因为诸如行安全特性与具体的行数值相关）。结束后，将 SQL 查询的内部表示传递给 query rewriter module。

2. Query Rewriter

Rewriter 是一个逻辑组件，一些商业数据库会把 rewriter 实现在 parser 的末期阶段，或 optimizer 的早期阶段。其作用是在 不访问表数据 和不改变语义的前提下简化查询：

1. 视图展开：根据 catalog 中的视图定义，把查询中对视图的引用替换为对表和列的引用
2. 常数表达式展开：完成常量运算
3. WHERE 子句中的谓词重写，甚至插入新的谓词使查询执行时可以过滤更多的数据
4. 语义优化
5. 子查询展开：启发式规则，或 cost-based 分析

3. Query Optimizer

将查询的内部表示转化为一个有效的查询计划。在大部分系统中，查询会被转换为 SELECT-FROM-WHERE 的 block，在每个 block 内分别做优化，最终在后处理阶段添加一些算子以支持 GROUP BY、ORDER_BY、HAVING、DISTINCT 等特性。查询计划的形式可以是：

• 机器代码
• 可被解释执行的计划（为了方便跨平台移植，主流 DBMS 使用这种方法）

主流系统对 Selinger 论文的扩展：

• Plan space（？）
• 选择率估计：大部分系统使用数据的值分布等统计信息
• Search algorithms：动态规划 / Top-donw 搜索 / heuristic
• 并行：在多台机器、多个 CPU 之间调度算子
• Auto-Tuning：自治？

查询编译和重编译：对 prepared statment 的支持。这类查询会通过 parser、rewriter 和 optimizer，然后查询计划将被保存到参数到达时才执行。另外一些系统会动态产生 SQL 语句并将类似语句的查询计划保存在 cache 中。随着时间推移，一个查询可能需要被重新优化，有两种处理方式：

• 直到计划无法使用才重新优化（比如原计划使用 index，而 index 被 drop 了）；好处：计划可预测
• 自动重新编译（self-tuning）；好处：计划性能更好但不可预测

上述两种差异是有历史原因的：对于高端系统，经验丰富的 DBA 不希望自己设计好的查询被 DBMS 弄得无法预测；对于低端系统，用户更希望 DBMS 有自动调优计划的能力。

4. Query Executor

查询计划是包含算子的数据流图，每个算子封装了查询执行算法。在一些系统中，算子已被编译为字节码，执行器充当运行时解释器；但更多系统中执行器得到的是数据流图，通过递归调用算子的函数完成查询。

现在查询系统主要使用 迭代器模型 实现执行器。每个算子的逻辑独立于其在图中的父节点和孩子节点。迭代器模型耦合了数据流和控制流，只需要一个 DBMS thread 就可以执行整个查询图，不需要复杂的网络协议，比如并发生产者和消费者之间的队列和反馈。另外，还提高了资源利用率。

此外，并行与网络通信也可以封装在算子中，从而维护完整的迭代器模型。

每一个算子会预先分配固定数量的 tuple descriptor，是一个列引用数组，每个列引用指向内存某处的元组及其列偏移。根据元组在内存中的实际位置，可以分为两类：

• BP-tuples：元组保存在 buffer pool 中，算子引用元组时，需要增加 page 的 pin 值
• M-tuple：算子在堆上动态分配内存，并从 buffer pool 中拷贝元组或验证表达式，放到动态分配的内存中

过度使用 M-tuple 可以防止一页数据被长时间 pin 在 buffer pool 中，也可以防止 pin 后忘记 unpin；但是拷贝数据将导致巨大的性能开销。对于一个会被长时间引用的元组，将其拷贝的做法是值得的。

5. Access Methods

用于访问不同磁盘数据结构的子函数：heaps、B+ 树索引、hash 索引、多维索引。其大致的 API 也被实现为迭代器模式：

• init() 接收一个 search 参数用于过滤元组
• get_next() 用于返回一个符合条件的元组，直到没有任何元组可以返回

其中 search 参数被传入 access method 层有两个原因：

1. 诸如 B+ 树索引需要这个参数来进行有效查找
2. 如果由 access method 的调用者来进行过滤，那么需要多次 pin/unpin 一个页，甚至还需要多次删除从 buffer pool 中拷贝的元组，消耗了很多 CPU 时间；如果过滤实现在 access method 层，则可以避免重复的 pin/unpin 和 copy/delete

DBMS 有很多设计是通过把要做的事放在一个集合中一次做完，通常是为了 disk I/O 性能。但这里是为了 CPU 性能。

AM 中对某一行的引用方式有着不同的设计：

• 引用行物理地址：访问快，但是更新一行的代价较大 - 需要更新所有索引
• 引用间接地址：访问慢，但是无需更新其它索引

6. Data Warehouses

数据仓库处理历史数据，数据库处理 当前数据。一些数据仓库中的重要技术：

• Bitmap 索引：由于数据仓库中的数据相对静止，使用 bitmap 来存储索引可以降低空间占用，并且可以在多条件过滤时直接进行位运算；但更新代价昂贵
• 批量装载：不需要 SQL 层面的开销，将数据批量导入仓库内
• 物化视图（Meterialized Views）：提前将 join 结果保留，避免在运行时进行 join
  • 自主选择需要被物化的视图
  • 维护视图的最新性（实时更新/定时删除重建）
  • 在即席查询中考虑使用物化视图

几个 OLAP 概念：

• Data Cubes：物化视图的一种，提升可预测的查询性能
• Fact 表：保存了简单但大量的记录，是数据仓库的中心，包含外键指向 dimension 表
• Dimension 表：用于分析具体某一个维度的信息

上述概念形成了以 fact 表为中心，被 dimension 表包围的 星型模型：对 fact 表来说有一个主键 N 个外键。

而很多 dimension 表是天然具有层次的（地理上/时间上/...）。比如几个区域的 dimension 表可以组成一个城市的 dimension 表。一个多层次的星型模型，被称为 雪花模型。

大部分对数据仓库的查询包含：

1. 在雪花模型中按一个或多个维度过滤属性
2. 与中心的 fact 表 join
3. 对属性进行分组、聚合

对于这种查询模式，设计专用的优化器来选择最佳查询计划。

列式存储在数据仓库中有巨大优势，尤其适合表比较宽，但每次访问只需要访问很少几列的场合。列存能够进行高效的压缩。但列存需要保证每一行在列与列之间的一致性——但是对于通常为 append-only 的数据仓库来说，通常不是问题。

7. Database Extensibility

• 抽象数据类型：DBMS 的类型系统需要被设计为 catalog 驱动 - catalog 中包含系统理解的数据类型，和处理这些数据类型的函数；DBMS 不解释数据类型，只会调用类型对应的函数来处理数据，同时还需要保证能够安全地执行用户自定义的代码
• 处理非关系模型的结构化数据，比如 XML
  • 一种处理方式是为 XML 建立定制的系统
  • 一种处理方式是将 XML 视为 ADT - 这样执行用户自定义代码的代价对优化器来说不透明
  • 将结构化数据规范化为关系模型 - 这样优化器可见数据的结构，但增加了存储开销
• 全文检索
  • 文字索引子系统 / 集成独立的文字索引引擎
  • 异步更新（爬取）/ 事务级更新
  • 挑战：将关键词查询与关系查询对应起来 / 优化器无法估算全文索引的选择率和代价
• 其它
  • 可扩展的优化器：动态添加规则
  • 可扩展的执行器：支持远程数据源

[mrdrivingduck]

Storage Management

两种存储管理模型：

• 直接操作低层块设备驱动
• 使用 OS 文件系统

1. Spatial Control

由于 DBMS 比 OS 更有能力知道查询的 I/O pattern，因此 DBMS 完全控制磁盘上的块在理论上具有最佳性能——绕开文件系统。缺点：

• DBA 需要将整个磁盘分区划给 DBMS，该分区无法使用文件系统接口进行备份
• 裸磁盘接口通常因 I/O 而异，使 DBMS 不便移植
• 无法使用 RAID / SAN 等虚拟存储设备

相比之下，在文件系统中划出一个大文件，同样可以起到线性数组的 page block 效果。研究显示，在 I/O 密集型负载（TPC-C）中，使用文件系统作为存储只有 6% 的性能下降；在普通负载中，性能下降可以忽略不计。

部分系统允许动态调整数据页大小，但需要是 OS 文件系统页大小的整数倍。

2. Temporal Control: Buffering

大部分文件系统提供了内置的 I/O 缓冲机制，但：

• 会破坏 DBMS 的正确性：比如 DBMS 的事务正确性需要显式控制 WAL 写回磁盘的顺序和时机
• 性能问题：OS 内置的 read-ahead / write-behind 与 DBMS 具体的 workload 不匹配，因为 OS 层无法得到 DBMS 层对查询的知识（比如 B+ 树扫描，叶子结点在逻辑访问上连续但在物理磁盘上不一定连续）
• 双缓存问题：DBMS 维护自己的缓存，其余任意 OS 级别的缓存都是浪费的 - 当 I/O 和 RAM 趋于无限时，内存拷贝是一个很大的瓶颈

3. Buffer Management

静态 / 动态分配。一个页框数组，每个页框都可以存放一个数据库磁盘块。一般来说从磁盘直接把数据搬到页框中，不作任何格式修改，反之亦然。

Buffer pool 最重要的信息 - hash 表：<逻辑页号 - 页框地址、物理页地址、metadata (dirty bit / pin)>

DBMS I/O pattern 的多样性使 OS 的页面淘汰机制 LRU、CLOCK 等性能较差。DBMS 一般使用改进型算法 LRU2 / 根据页面类型（B+ tree root page / heap page）处理。

[mrdrivingduck]

Transactions: Concurrency Control and Recovery

DBMS 的查询处理器和事务存储引擎是独立的模块，通过接口耦合。在事务存储引擎中，以下几个模块紧密耦合在一起：

• 锁管理器
• 日志管理器
• Buffer pool
• Access method

1. ACID

• 原子性：all or nothing
• 一致性：事务的开始和提交时数据库一定在一个一致的状态，由查询执行器在运行时检查
• 隔离性：两个并发的事务不会见到彼此未提交的更新，由锁协议实现
• 持久性：提交后的事务能够抵挡任意的软硬件错误，由日志和恢复实现

2. Serializability

可序列化是并发事务正确性的衡量指标。以下三个著名的技术用于并发控制：

• 两阶段锁定（2PL）：事务对共享数据的读取加共享锁，写入加排它锁，在事务提交或回滚时释放所有锁
• 多版本并发控制（MVCC）：事务不获取锁，但保证以一致的视角对数据库某个过去的状态可见
• 乐观并发控制（OCC）：事务记录读写历史，在事务提交时检测历史中是否有冲突，并回滚一个冲突的事务

锁管理器通常用于实现 2PL，MVCC 和 OCC 通常作为 2PL 的附加。MVCC 减少了锁的使用，代价是无法提供完全的可序列化。

3. Locking and Latching

Lock 管理本质上提供了一个可以注册名称的地方，本质上是一个 hash table：

• Key：lock name
• Value：lock mode / 等待队列（包含事务 ID 和等待 lock mode 的 pair）

另外还提供一个事务表：

• Key：事务 ID
• Value：指向事务线程的指针（用于调度）、指向事务的所有锁请求（用于一次性释放锁）

Lock 管理器提供两种操作（2PL）：

• lock(lockname, transactionId, lockmode)
• remove_transaction(transactionId)

Lock 管理器需要周期性检测死锁。

而 latch 用于保护 DBMS 内存中的共享数据结构，不服从 2PL，不允许死锁（死锁说明有 bug），使用不会被追踪。

Transaction Isolation Levels

为了提升并发，ANSI SQL 标准对可序列化提供了更弱的语义：

• READ_UNCOMMITTED：任务可以读到提交或未被提交的任意数据
• READ_COMMITTED：事务只能读到提交后版本的数据（但不保证是同一个版本）
• REPEATABLE_READ：事务只能读到同一个版本的提交后数据（存在幻读问题，因为元组级别的 2PL 无法防止表中被插入新元组，而表级别的 2PL 将会降低吞吐量）
• SERIALIZABLE：可序列化

数据库厂商自行实现了一些隔离级别：

• CURSOR_STABILITY：解决 READ_COMMITTED 的丢失更改问题
• SNAPSHOT_ISOLATION
• READ_CONSISTENCY

4. Log Manager

日志管理器负责维护已提交事务的持久性，并保证回滚或中止事务的原子性。为满足这些条件，日志管理器在磁盘上维护了一些列的日志记录，为了能够在数据库崩溃后恢复，内存中的数据结构需要能够从持久化的数据和日志中恢复。

标准的数据库恢复是由 Write-Ahead Logging (WAL) 协议实现的：

• 对数据的每次修改都会产生一条日志记录，日志必须在数据库页面被刷入磁盘之前刷入磁盘
• 日志必须按照顺序刷入磁盘
• 在事务提交返回之前，commit log 必须已经被刷进磁盘

第一条规则保证了未完成的事务可以被撤销，从而保证原子性；第二条和第三条规则保证了持久性：已提交但丢失的事务可以通过 redo 日志恢复。

两种日志类型：

• 逻辑日志：记录逻辑操作
• 物理日志：记录对数据页面的更改

崩溃恢复时，从第一条日志开始恢复是低效的，正确的恢复起点应该是以下两个日志记录中更旧的那条：

1. 描述 buffer pool 中最老的页面的最早一次修改的日志记录
2. 系统中最老的事务的日志记录

该恢复起点的序列号被称为 recovery log sequence number (recovery LSN)。由于计算 LSN 有开销，而 LSN 又是单调递增的，因此不必实时保证 LSN 最新，可以周期性地计算，这个周期性间隔被称为 checkpoints。最简单的 checkpoint 方法是将所有脏页 flush 回磁盘然后保存 LSN。

5. Locking and Logging in Indexes

对索引的查询需要保证返回事务一致性的元组。

对于 B+ 树来说，如果遵循 2PL，那么总会有一个事务锁定根节点。一些改进方法有...（没看懂）

一些索引的结构性变化并不需要 undo，因为不会有副作用。比如 B+ 树节点在事务插入的过程中分裂，当事务中止时，分裂的节点不合并也没有关系；再比如对于 heap file 的插入来说，插入了一些元组导致文件长度增长，而事务的回滚也并不需要把新分配的文件块回收，可以留作以后使用。

在使用索引和元组级别的锁时，将会产生幻读问题。由于事务不加表级锁，当一个事务通过索引查询一个范围的数据时（比如 BETWEEN 'Bob' AND 'Bobby'），其它事务可以自由地插入新元组（比如 Bobbie）。当新插入的元组落入了查询事务的条件范围内时，将会被查询事务访问到。因此需要做的是将查询事务的查询范围锁定。Next-key Locking 机制中，在索引中插入数据时，必须对表中比当前要插入数据大的第一个已存在元组加排它锁；同时要求查询事务对查询范围内的 next key tuple 加共享锁。这样保证了被插入的元组肯定不会出现在查询事务的查询范围中间。

[mrdrivingduck]

Shared Components

1. Catalog Manager

保存系统中所有数据的 metadata：用户、schema、表、列、索引的名称和关系。其本身也作为一系列表保存在数据库中：

• 用户可以用相同的语言和工具查看 metadata
• 内部代码可以用相同的代码读写 metadata

出于性能考虑，catalog 中的热点部分会被物化在内存中。

2. Memory Allocator

主流商业系统使用基于 context 的内存分配器。Memory context 是一个内存数据结构，维护了一个包含多段连续内存的列表，也就是一个内存池。其基本的 API 包含：

• 给定名称或类型，创建一个 memory context（根据类型可以选择分配大块内存还是小块内存）
• 在 memory context 内分配一块内存（类似 malloc()），这块内存可以来自 memory context 已有的内存；也可以问 OS 要一块更大的内存（如果不够），并链接到 memory context 中
• 在 memory context 中删除一块内存（类似 free()），用得比较少，一般是直接销毁整个 memory context
• 删除 memory context：释放 memory context 维护的所有内存区域，并删除 context 头部
• 重置 memory context：释放 memory context 维护的所有内存区域，保留 context 头部

Memory context 类似于一个低级的、程序可控制的垃圾回收机制。它免去了需要遍历数据结构并释放内存以及潜在的内存泄露的风险。相比之下，Java 的 GC 是面向整个程序的内存，并且 JVM 自行决定何时 GC；而数据库可以只释放某个特定用途的 memory context，并且程序可以决定何时释放。

另外，OS 的 malloc() 和 free() 对小块内存来说较为昂贵，memory context 减小了 OS 级别的开销。

3. Disk Management Subsystems

用途之一是管理数据库表和文件的映射关系。由于早期文件系统的局限，数据库表和文件并不是一一映射的，可能是多个表在一个文件中，也可能是一个表对应了多个文件。历史原因有：

• 传统的 OS 文件跨磁盘存储（文件大小不能大于磁盘）
• OS 通常只允许打开有限数量个文件描述符，因此不能为每个表分配一个文件
• 早期文件系统对文件大小有限制，这种限制对数据库表大小来说是不能接受的

另外，磁盘管理子系统还有部分用于处理设备相关细节的代码，比如 RAID 或 SAN。

4. Replication Services

几种复制方式：

• 物理复制：无法在大型数据库上扩展，同时无法保证事务一致性
• 基于触发器的复制：在 insert/delete/update 时触发记录复制，但其开销对于一些负载来说不可接受、
• 基于日志的复制：一个进程截获日志的写入，然后将日志发送到远程并 apply
  • 开销低
  • 随着数据库大小和更新频率能够优雅扩展
  • 重用了 DBMS 的内置机制
  • 天然提供了事务一致性