数据库存储
1 存储
我们将重点关注“面向磁盘”的DBMS体系结构，该体系结构假定数据库的主要存储位置位于非易失性的磁盘上。
在存储层次结构的顶部，是最接近CPU的设备，这是最快的存储，但也是容量最小和最昂贵的。离CPU越远，存储设备越大但速度越慢，也更便宜。
易失性设备：
- 易失性意味着如果设备断电，则数据会丢失。
- 易失性设备支持按字节寻址的快速随机访问，这意味着程序可以跳转到任意字节位置并读取该位置的数据。
- 简单起见，我们始终将此类存储称为“内存”。
非易失性设备：
- 非易失性意味着存储设备不需要持续供电来使设备保存其真该存储的数据。
- 它是块/页寻址的，这意味着为了读取特定偏移量位置的数据，程序首先必须将整个页加载到内存中。
- 通常非易失性存储更适合顺序访问（同时读取多个连续的数据块）。
- 简单起见，我们将其称为“磁盘”，不区分SSD和HDD。
还有一类较新的存储可能会流行起来，其称为持久内存。这类设备的设计目标是几乎与DRAM一样快，并且还具有磁盘的持久性。它们目前并未广泛用于生产，此前一个比较知名的项目是Optane，然而英特尔在2022年夏季停止生产了。有的材料中将这种设备称为非易失性内存。
有的地方可能看到对NVMe SSD，其中NVMe代表非易失性内存（non-volatile memory）。这些NVMe SSD与持久内存不是同一种硬件。它们是通过改进了的硬件接口连接的典型NAND闪存。这种改进的硬件接口允许更快的传输，提升了NAND闪存性能。
由于我们的DBMS架构假定数据库存储在磁盘上，因此DBMS的组件需要负责确定在非易失性磁盘和易失性内存之间移动数据的方式，因为系统无法直接对磁盘上的数据进行操作。
因为从磁盘获取数据非常慢，我们将专注于降低从磁盘获取数据的延迟，而不是优化寄存器和缓存。
顺序访问 vs 随机访问
在非易失性磁盘上的随机访问比顺序访问慢很多。
DBMS将尽可能顺序访问：尽量减少向随机位置的页读写（数据会在连续的块中存放）；
2 面向磁盘的DBMS
数据库都存储在磁盘上，数据库文件中的数据都被组织成页，第一页是字典页。为了对数据进行操作，DBMS需要将数据读取到内存中。它通过一个名为缓冲池的组件（负责管理磁盘和内存间的数据移动）来实现这一点。DBMS页有执行查询的执行引擎。执行引擎会向缓冲池请求特定页面，缓冲池将负责将该页面放入内存并为执行引擎提供指向内存中该页面的指针。缓冲池管理器将确保页面存在，而执行引擎将在该块内存上进行操作。
3 DBMS vs OS
DBMS的一个高级设计目标是支持超过内存大小的数据库。由于读/写磁盘的成本很高，因此必须小心管理磁盘。我们想要尽量避免从磁盘中获取内容时的大的停顿而导致一切减慢。我们希望DBMS在等待从磁盘获取数据时能够处理其他查询。
这个高级设计目标就像虚拟内存，它有很大的地址空间，操作系统可以将磁盘中的内容放置进去。
实现虚拟内存的一种方法是使用mmap将文件内容映射到进程的地址空间中，这将磁盘和内存之间来回移动页面的工作交给了OS，不幸的是，这意味着如果mmap遇到页面错误，进程会被阻塞。
- 事务安全：OS可能在任何时候刷新脏页。
- I/O 停顿：DBMS不知道内存中有哪些页，OS将在页错误时停顿线程。
- 错误处理：任何访问可能导致SIGBUS错误，DBMS必须处理这种情况。
- 性能问题：操作系统数据结构争用；TLB shootdown。
- 如果需要向磁盘写入，不要使用mmap。
- DBMS（几乎）总是向自己控制事物并且可以做得更好，因为它更了解正在访问的数据和正在处理的查询。
- The operating system is not your firend.
可以使用madvise/mlock/msync。
出于正确性和性能原因，不建议在DBMS中使用mmap。尽管系统有一些操作系统可以提供的功能，但让DBMS自己实现这些功能通常可以提供更好的控制和性能。
目前，monetdb、levelDB还在使用操作系统提供的功能，mongoDB曾经使用这种方式，后续重构已经不再使用。SQLite部分使用。
4 文件存储
在最基本的形式中，DBMS将数据库存储为磁盘上的文件，有些可能使用文件层次结构组织，有些可能使用单个文件（例如SQLite）。
早期一些系统使用自定义的文件系统，现在的一些商业DBMS仍然支持。目前较新的DBMS不使用这种方式了（工作量和性能提升的权衡）。
操作系统对这些文件的内容并不了解，只有DBMS知道如何解析它们，它们是以DBMS特定的方式编码的。
DBMS的存储管理器负责管理数据库的文件。它将文件表示为页的集合。它还跟踪已读取和写入页中的数据以及这些页中有多少可用空间。
5 数据库页
DBMS以固定大小的数据块（称为页）跨一个或多个文件组织数据库。页可以包含不同类型的数据（元组、索引等）。大多数系统不会在页中混合这些类型。有些系统会要求页是自包含的，这意味着阅读每一页所需的所有信息都在页面本身上（Oracle应该是这样，有更好的故障恢复表现）。
每个页都有一个唯一的标识符，如果数据库是单个文件，那么页ID可以只是文件偏移量。大多数DBMS都有一个中间层，可以将页ID映射到文件路径和偏移量。系统的上层会请求一个特定的页号，然后存储管理器必须将该页号转换为一个文件和一个偏移量以找到该页。
大多数DBMS使用固定大小的页来避免支持可变大小页所需的工程开销。例如：对于可变大小的页，删除页可能在文件中产生一个空洞，而DBMS无法轻易地用新页面来填补该空洞。
在DBMS中有三种页的概念：
- 硬件页（通常4KB）
- 操作系统页（通常4KB）
- 数据库页（512B-16KB）
存储设备保证硬件页大小的原子写入。如果硬件页为4KB，而系统尝试在磁盘上写入4KB数据，则要么全部写入，要么全部不写入。这意味着如果数据库页大于硬件页，DBMS必须采取额外的措施来确保数据被安全的写入磁盘，因为可能在数据库页写入磁盘过程中系统崩溃。
SQLite、Oracle页为4KB；SQL Server、PostgreSQL为8KB；MySQL为16KB
6 数据库堆
有多种方法可以在磁盘上组织DBMS的页，堆文件组织就是其中一种方法。堆文件是页的无序集合，其中元组以随机顺序存储。需要额外的元数据来维护空闲空间和页的信息。
包括堆文件组织；树文件组织；顺序文件组织（ISAM）；哈希文件组织：
DBMS可以通过使用页的链表或页字典来根据page_id找到磁盘上的页。
- 链表：头部页包含两个指针，分别指向空闲页链表和数据页链表。如果DBMS正在搜索一个特定的页，它必须对数据页链表进行顺序扫描，知道找到对应的页面。
- 页字典：DBMS维护一些特殊的页，这些页记录数据页的位置（必须保证字典页和数据页同步）以及每个页上的空闲大小（页上的空闲槽位数、空闲页列表）。
7 页
每个页包含一个页头，记录了有关页面内容的元数据：
- 页大小
- 校验和
- DBMS版本（版本兼容）
- 事务可见性
- 自包含信息（像Oracle这样的系统需要）
一种存放数据的简单方法是记录DBMS在页中存放了多少元组，并在添加新元组时将其追加到页内元组的尾部。然而，当删除元组或者元组是可变长的情况时就会很麻烦。
在页中存放数据主要有两种方法：slotted-pages和log-structured（后续介绍）。
Slotted Pages：页中将槽映射为偏移量。
- 现在的DBMS的最常用方法。
- 页头记录使用的槽的数量、最后使用的槽的起始位置的偏移量。槽数组记录每个元组的开始位置。
- 添加一个元组时，槽数组会从头向尾增长，元组的数据会从尾向头增长，当槽数组和元组数据相遇时，页视为已满。当删除一个元组时，槽和元组数据全部移动以填补空位，由于页面大小是有限的，所以认为这种操作的时间复杂度是可以接受的。
8 元组
元组本质上是一个字节序列，将这些字节解释为属性类型和值是DBMS的工作。
元组头：包含元组的元数据。
- DBMS的并发控制协议的可见性信息（即有关哪个事务创建/修改该元组的信息）。
- NULL值的Bit Map。
- DBMS无需在此处存储有关数据库模式的元数据。
元组数据：属性的实际数据。
- 属性通常按照创建表时指定的顺序存储（这实现比较简单，但是不按照这种顺序可能效率更高）。
- 大多数DBMS不允许元组超过页面大小。
唯一标识：
- 数据库中的每个元组都分配有一个唯一标识符。
- 最常见的：page id + (offset or slot)。
- 应用程序不能依赖这些元组id。
Denormalized 元组数据：如果两个表高度相关，DBMS可以“pre-join“它们，使得两个表的数据最终在同一个页内存储。这使得读取两个表数据更快，因为DBMS只需加载一页，而不是两个单独的页面后将它们join在一起。但是这会使更新成本更高，因为DBMS需要为每个元组提供更多空间。
1970s时IBM System R实现，mongoDB支持。
9 Log-structured
Slotted Pages设计相关的一些问题是：
- 碎片化：删除元组可能会在页面中留下空白。
- 无效的磁盘I/O：由于非易失性存储的面向块的特性，需要读取整个块才能获取元组。
- 随机磁盘I/O：磁盘读取器可能需要跳转到20个不同的位置来更新20个不同的元组，这可能非常慢。
如果我们在一个只允许创建新数据而不允许覆盖的系统上（Cloud storage (S3)、HDFS），日志结构存储模型基于此假设解决了上面列出的一些问题。
Log-Structured Storage：DBMS不存储元组，只存储日志记录。
- 将数据库修改（put/delete）的记录存储到文件中。每条日志记录都包含元组的唯一标识符。
- 如果要读取记录，DBMS会从新到旧向后扫描日志文件并“重新创建”元组。
- 写入速度快、读取速度可能较慢。磁盘的写入是顺序的，现有页面是不会改变的，减少随机磁盘I/O。
- 在仅追加存储上表现良好，因为DBMS无需返回并更新数据。
- 为了避免读取时间超长，DBMS可以有索引以允许它跳转到日志中的特定位置。它还可以定期压缩日志（如果有一个元组，然后对其进行了更新，可以将其压缩，仅保留更新后的元组）。
- 压缩后，DBMS无需保留时间信息（相同的id只会出现一次）。数据库可以将日志也压缩到一个按id排序的表中，称之为Sorted String Tables（SSTables），它们可以加快元组搜索速度。
- 压缩的问题i是DBMS会Write-Amplification（一遍又一遍地重写相同的数据）和压缩的代价比较高。
RocksDB、levelDB
10 元组存储
一个元组本质上就是字节的序列，将这些字节解释为属性类型和值是DBMS的工作。
常见的可以存储在元组中的高级数据类型包括：整型、可变高精度数、定点精度数、可变长值、日期/时间等。
DBMS的目录（数据字典）包含有关表的模式信息，系统使用这些信息来确定元组的布局。元数据包含有关数据库具有哪些表和列以及其类型和值的顺序的信息，还包括权限、内部统计数据等等。大多数DBMS以表的格式将它们的目录存储在内部，使用特殊的代码来“引导”这些目录表。
标签：DBMS,01,Database,数据库,Storage,存储,元组,磁盘,数据 From： https://www.cnblogs.com/pannnn/p/16943177.html