记录数据库

15445-03-Storage（I）

发布于 • 作者: Ethan

MindMap

mindmap

一、Storage 存储

In this class, we focus on a “disk-oriented” DBMS architecture that assumes that the primary storage location of the database is on non-volatile disk(s). 在本课程中，我们关注一种“面向磁盘”的 DBMS 架构，该架构假设数据库的主要存储位置在非易失性磁盘上。

At the top of the storage hierarchy, you have the devices that are closest to the CPU. This is the fastest storage, but it is also the smallest and most expensive. The further you get away from the CPU, the larger but slower the storage devices get. These devices also get cheaper per GB. 在存储层次结构的顶层，您拥有最接近 CPU 的设备。这是最快的存储，但它也是最小且最昂贵的。您离 CPU 越远，存储设备就越大但速度越慢。这些设备每 GB 的价格也越便宜。

There’s also a demarcation line in the middle of the hierarchy that separates volatile devices from non-volatile devices. 在层次结构的中部还有一个分界线，将易失性设备与非易失性设备分开。

Volatile Devices 易失性设备

  • Volatile means that the device does not retain its state after power loss. 易失性意味着设备在断电后不会保持其状态。
  • Volatile storage supports fast random access with byte-addressable locations (e.g., DRAM). 易失性存储支持通过字节寻址位置进行快速随机访问（例如，DRAM）。
  • We refer to volatile storage as memory. 我们将易失性存储称为内存。

Non-Volatile Devices 非易失性设备

  • Non-volatile devices retain their state even after power loss (e.g., disk). 非易失性设备在断电后仍能保持其状态（例如，硬盘）。
  • These are block/page addressable devices — to read a value, you must first load the entire page (e.g., 4 KB) into memory. 这些是按块/页寻址的设备——要读取一个值，你必须首先将整个页（例如，4 KB）加载到内存中。
  • Non-volatile storage is better at sequential access due to its architecture (e.g., HDD). 由于其架构（例如，HDD），非易失性存储在顺序访问方面表现更好。
  • We refer to this as disk, without major distinction between SSD and HDD. 我们称之为磁盘，SSD 和 HDD 之间没有显著区别。

二、Access Time and Access Pattern 访问时间和访问模式

There is a large latency contrast between volatile and non-volatile devices. 易失性设备和非易失性设备之间存在较大的延迟差异。 If reading from the L1 cache took 1 second, then: 如果从 L1 缓存读取需要 1 秒，那么：

  • SSD read would take 4.4 hours. SSD 读取需要 4.4 小时。
  • HDD read would take 3.3 weeks. HDD 读取需要 3.3 周。

Two major access patterns exist: random access and sequential access. 存在两种主要的访问模式：随机访问和顺序访问。 Random access on disk is much slower, so DBMSs aim to maximize sequential access — sometimes buffering random writes sequentially and flushing asynchronously. 磁盘上的随机访问速度要慢得多，因此 DBMS（数据库管理系统）旨在最大化顺序访问——有时将随机写入顺序缓冲并异步刷新。

三、System Design Goals 系统设计目标

The disk-oriented DBMS must manage databases larger than memory capacity. 面向磁盘的数据库管理系统必须管理大于内存容量的数据库。 Frequent movement between disk and memory requires careful management to: 频繁地在磁盘和内存之间移动需要仔细管理，以：

  • Avoid long I/O stalls. 避免长时间的 I/O 停滞。
  • Maximize sequential access. 最大化顺序访问。

四、Disk-Oriented DBMS Overview 基于磁盘的 DBMS 概述

The database resides on disk, organized into pages. 数据库驻留在磁盘上，组织成页。 To operate, the DBMS brings data pages into memory via a buffer pool. 为了运行，DBMS 通过缓冲池将数据页带入内存。

  • The execution engine requests pages. 执行引擎请求页面。
  • The buffer pool manager loads pages and provides memory pointers. 缓冲池管理器加载页面并提供内存指针。
  • The buffer pool ensures the page stays in memory during operation. 缓冲池确保页面在操作期间保持驻留在内存中。

五、DBMS vs. OS DBMS 与 OS

Like virtual memory, the DBMS manages data larger than physical memory. 如同虚拟内存一样，数据库管理系统（DBMS）管理的数据比物理内存要大。 However, the DBMS does not rely on the OS to manage page swapping. 然而，数据库管理系统不依赖操作系统来管理页面交换。

  • Using mmap() allows OS-level mapping but can block on page faults. 使用 mmap()允许操作系统级别的映射，但可能会在页面错误时阻塞。
  • DBMSs avoid mmap() for correctness and performance reasons. 数据库管理系统出于正确性和性能的考虑，避免使用 mmap() 。
  • The DBMS wants control over its data movement. 数据库管理系统希望控制其数据移动。

OS utilities (optional use): 操作系统工具（可选使用）：

  • madvise: hints for read-ahead. madvise : 预读提示。
  • mlock: prevents swapping memory to disk. mlock : 防止内存交换到磁盘。
  • msync: flushes memory to disk. msync : 将内存刷新到磁盘。

The operating system is not your friend. 操作系统不是你的朋友。

Implementing these functions inside the DBMS allows better performance and control. 在 DBMS 中实现这些功能可以更好地提高性能和控制。

六、File Storage 文件存储

A DBMS stores databases as files on disk. 一个数据库管理系统将数据库存储为磁盘上的文件。

  • Some systems use multiple files; others, like SQLite, use a single file. 一些系统使用多个文件；另一些系统，如 SQLite，使用单个文件。
  • Files are often in proprietary formats. 文件通常是专有格式。
  • Portable file formats (open specs) allow interoperability. 可移植文件格式（开放规范）允许互操作性。

DBMSs typically use OS-provided file systems, though enterprise systems (e.g., Oracle ASM) may use custom ones. 数据库管理系统通常使用操作系统提供的文件系统，尽管企业系统（例如 Oracle ASM）可能会使用自定义的文件系统。

The storage manager: 存储管理器：

  • Represents files as collections of pages. 将文件表示为页面的集合。
  • Tracks read/write operations and free space. 跟踪读写操作和空闲空间。
  • Replication is handled outside (e.g., RAID or higher logical layer). 复制功能由外部处理（例如 RAID 或更高级的逻辑层）。

七、Database Pages 数据库页面

Databases are organized into fixed-size blocks (pages). 数据库被组织成固定大小的块（页面）。 Pages may contain tuples, indexes, or metadata. 页面可以包含元组、索引或元数据。

  • Each page has a unique page ID. 每页都有一个唯一的页 ID。
  • The page ID maps to a file and offset through an indirection layer. 页 ID 通过一个间接层映射到一个文件和偏移量。
  • Fixed-size pages are preferred for simplicity. 固定大小的页更简单。

Page Sizes 页大小

  • Hardware page: 4 KB 硬件页：4 KB
  • OS page: 4 KB 操作系统页：4 KB
  • Database page: 1–16 KB 数据库页：1–16 KB

Larger pages → better for read-heavy workloads (≥1MB) 大页 → 更适合读密集型工作负载（≥1MB） Smaller pages → better for write-heavy workloads (4–16KB) 较小的页面 → 更适合写密集型工作负载（4–16KB）

If a DBMS page > hardware page, crash recovery mechanisms are needed to ensure atomic writes. 如果数据库管理系统页面 > 硬件页面，需要崩溃恢复机制来确保原子写入。

八、Database Heap 数据库堆

Heap File Organization: 堆文件组织： Unordered pages where tuples are stored arbitrarily. 无序页面，其中元组被任意存储。

  • Page directory maps logical objects to data pages. 页面目录将逻辑对象映射到数据页面。
  • Tracks metadata like free space, page type, and empty pages. 跟踪元数据，如空闲空间、页面类型和空页面。

九、Page Layout 页面布局

Each page includes a header with metadata: 每页包含一个带有元数据的页眉：

  • Page size 页面大小
  • Checksum 校验和
  • DBMS version 数据库管理系统版本
  • Transaction visibility 交易可见性
  • Self-containment 自包含性

Data Layout Types 数据布局类型

  1. Tuple-oriented 元组导向
  2. Log-structured 日志结构化
  3. Index-oriented 索引导向

Tuple-Oriented (Slotted Pages) 元组导向（带槽页）

  • Most common in DBMSs today. 当今数据库管理系统中最常见。
  • Header stores: 存储头：
    • Number of slots 槽位数
    • Offset of last used slot 最后使用的槽的偏移量
    • Slot array mapping tuple locations 槽数组映射元组位置
  • Data grows from end to start; slots grow from start to end. 数据从末尾开始增长；插槽从开头开始增长。

Full page: when slot array meets tuple data. 满页：当插槽数组遇到元组数据时。

(Log-structured and index-oriented layouts are covered in Lecture 05.) （日志结构化和索引导向布局在第五讲中讲解。）

十、Record IDs 记录 ID

Each logical tuple has a unique record identifier (RID) representing its physical location: 每个逻辑元组都有一个唯一的记录标识符（RID），代表其物理位置：

  • e.g., (file id, page id, slot number) 例如，(文件 ID，页 ID，槽号)
  • RIDs usually 4–10 bytes. RID 通常为 4-10 字节。
  • Applications cannot rely on RIDs (internal only). 应用程序不能依赖 RID（仅内部使用）。

十一、Tuple Layout 元组布局

A tuple is a sequence of bytes representing attribute values. 元组是一个表示属性值的字节序列。

Tuple Header 元组头部

  • Visibility info (for concurrency control). 可见性信息（用于并发控制）。
  • NULL bitmap. NULL 位图。
  • No schema metadata stored here. 此处未存储模式元数据。

Tuple Data 元组数据

  • Attributes stored in declared order. 属性按声明顺序存储。
  • Must be word-aligned. 必须对齐字。
  • Tuples cannot exceed page size. 元组不能超过页面大小。

十二、Data Representation 数据表示

Integer Types 整数类型

INTEGER, BIGINT, SMALLINT, TINYINT: Stored in native C/C++ format. 以原生 C/C++格式存储。

Floating-Point & Decimal Types 浮点数与十进制数类型

  • FLOAT / REAL: IEEE-754 (inexact, fast). FLOAT / REAL : IEEE-754（不精确，快速）。
  • NUMERIC / DECIMAL: Fixed-point (exact, slower). NUMERIC / DECIMAL : 固定点（精确，较慢）。

Variable-Length Types 可变长度类型

VARCHAR, VARBINARY, TEXT, BLOB: Stored as (header + data) or pointer to external page. 以(header + 数据)或指向外部页面的指针形式存储。

  • Overflow Pages: 溢出页： Used when value doesn’t fit a page; store record ID inline. 当值不适合一页时使用；将记录 ID 内联存储。
  • External Storage: 外部存储： Some DBMSs allow storing large values externally (no durability guarantees). 某些 DBMS 允许将大值外部存储（不提供持久性保证）。

Temporal Types 时间类型

TIME, DATE, TIMESTAMP, INTERVAL: Stored as 32/64-bit integers of micro/milliseconds since Unix epoch. 存储为自 Unix 纪元以来的 32/64 位微秒/毫秒整数。

Null Data Representation 空数据表示

  1. Null Column Bitmap Header – common in row-stores. 空列位图头——常见于行式存储。
  2. Special Values – placeholders for NULL (e.g., INT32_MIN), used in column-stores. 特殊值——用于列式存储的空值占位符（例如， INT32_MIN ）。
  3. Per-Attribute Null Flag – one bit per attribute (less efficient due to padding). 每个属性的空标志——每个属性一个比特（由于填充效率较低）。

Notes

storage1 storage2 storage3 storage4

探索主题

数据库设计C++RGo编程范式记录分布式算法网络统计阅读风格