存储介质一个数据库系统大致由以下不同部分组成：查询计划（executionplan）运算符执行（executor）访问方式（accessmethod）缓冲池（bufferpool）磁盘管理器（diskmanagement）以及其他一些组件，如并发控制、分发等。本系列课程将从下到上一一介绍。我们先来看看存储管理。一般来说，不同的存储介质在存储容量和速度上有很大的差异。容量越大，速度越慢。反之，容量越小，速度越快。以上图为例，cpu寄存器、缓存（L1、L2、L3）、内存是常见的volatile存储，容量小、速度快，但掉电后无法恢复，数据无法持久化。SSD或HDD等磁盘容量较大，但访问速度较慢，并且可以持久化数据。我们对这些存储介质的访问速度做一个简单的量化（同比放大），可以看到一级缓存在二级缓存，而机械硬盘甚至长达16周，容量越大，访问速度越慢。对于磁盘来说，顺序访问也比随机访问快，因为磁盘的主要耗时是seek。数据库系统进行磁盘管理的设计目标主要有以下几个方面：能够管理远超内存读写磁盘容量的数据是昂贵的，因此要避免频繁的磁盘读写，或者更有效地读写磁盘以防止写入停顿尽量避免随机磁盘IO的影响。在数据库中，内存和磁盘的结构和关系大致如下图所示。磁盘上的数据通常以页为单位组织。内存中维护一个缓冲池，用于缓存磁盘中的数据。页。当上层执行引擎需要读写数据时，首先从缓冲池中获取数据。如果缓冲池中没有数据，则将其从磁盘加载到缓冲池中，然后返回给执行引擎。这种组织类似于操作系统提供的MMap机制，即内存映射。内存映射（MMap）是指将磁盘文件的内容映射到内存地址空间。当进程访问该地址时，会触发缺页异常，将磁盘内容加载到物理内存中进行读写。一个常见的问题是，为什么不直接在数据库中使用操作系统提供的MMap机制，而是自己实现内存缓冲区和磁盘管理呢？数据库的上层执行引擎通常是多线程并发执行的。如果此时访问MMap，访问的页面可能不一样，可能会频繁出现缺页，导致系统卡顿。数据库对磁盘管理有更多的定制化需求：flushdirtypagestodiskincorrectorder特定的预读策略bufferreplacementstrategythread/processscheduling总之，数据库系统希望能够自己控制磁盘和内存的管理，而不需要依靠基于操作系统来满足自己的特定需求和场景。补充知识：在PostgreSQL中，底层的存储管理是基于虚拟文件描述符，即VirtualFileDescriptor，简称VFD。使用vfd的主要目的是绕过操作系统对同一进程打开文件的最大数量的限制。进程不直接持有操作系统的fd，而是数据库系统分配的vfd。如果进程打开文件数达到上限，会暂时关闭不用的文件。postgres在vfd之上封装了操作磁盘文件的基本API，如打开、关闭、删除文件等，代码可参考：https://github.com/postgres/postgres/blob/master/src/backend/storage/file/fd.chttps://github.com/postgres/postgres/blob/master/src/backend/storage/smgr/smgr.cPage概述大多数数据库系统中的磁盘数据都是以页面为单位组织的，所以先详细看看磁盘页的结构。数据库中的磁盘页面是指一个固定大小的文件块，一个页面通常可以存储元组、元信息、索引、日志等。每个页面都有一个唯一的标识符，称为页面id。不同数据库的页大小不一样，常见的有以下几种：在一个数据库系统中，页肯定不止一个，那么在这么多页之间，需要统一管理，比如增加一个页，删除一个页，遍历所有这些页面如何组织来实现这些目标？最常见的组织方法称为堆文件。堆文件是指页面的无序集合，页面是随机排列的。堆文件常见的组织方式有两种：链表pagedirectory链表以链表的形式组织页面，链表的头部有两个指针，一个指向空闲页列表，表示空闲页列表，还有一个指向数据页列表，一个指向实际存储数据的页。这种方法虽然直观，但是效率低下，因为页面是通过指针乱序排列的，查找页面需要遍历。这种组织方法在实践中使用不多。另一种更常见的方式是页目录。页目录实际上维护了一个特殊的页面，里面存放着其他页面的位置，可以看作是页面的元数据。这个特殊的页面还存储了每个页面的空闲空间等信息，方便上层应用选择需要读写的页面。页面组织方式日志结构化页面中的数据可以采用类日志的方式进行组织，即对元组的增删改查操作全部以日志追加的形式写入页面。这样做最大的好处就是可以使用顺序IO，可以提高写入性能。但是这种日志式的组织方式需要数据回收（compaction），在读取数据的时候，因为数据有多个版本，可能会有额外的磁盘IO消耗。日志组织方式非常适合写多读少的应用。一些NoSQL引擎如leveldb、rocksdb、HBase都采用了这种方式，但是在关系型数据库中，这种方式并不是主流。Slottedpage页面的内部结构，关系型数据库中常用的组织方式称为开槽页，其一般结构如下：页面的前面部分称为页眉，通常由固定大小的页眉组成，页眉通常包含有关页面的一些信息。页面大小、校验和、数据库版本、事务信息、数据压缩信息等元数据。header之后的部分叫做slot数组，每个solt数组存储了元组的起始位置，这样可以快速定位到每条记录。比如postgres中每条记录都有一个隐藏的CTID，它记录了tuple的物理位置，其内容为pageid+offset，即tuple所在页面的id，以及它在其中的位置这一页。从some_table中选择*，ctid；每个元组实际上是一个可变长度的字节序列，存储了具体的数据信息。有兴趣的读者可以看看postgres的diskpage结构，和这里的slottedpage基本一样，代码：https://github.com/postgres/postgres/blob/master/src/include/storage/bufpage.hLargeValues前面提到一个页面通常有一个固定的大小，那么如果存储的数据太大，超过了页面的大小，数据应该怎么存储呢？最常见的方式是使用一个额外的页面来存储，并在原始页面中保存一个指向它的指针。如果数据还是太大，额外的页面装不下，可以打开一个新的页面，用上一页指向它。这种额外的页面通常称为溢出页面，不同的数据库有不同的名称或做法。比如这种存储在PostgreSQL中就叫做TOAST。Tuple的结构我们先来看看tuple的内部结构。元组大致由两部分组成，头部和数据部分。header主要存放一些元数据信息，比如tuple的可见性（用于并发控制）、判断空列的位图等。postgres中tuple的内部结构可以参考：https://github.com/postgres/postgres/blob/master/src/include/access/htup_details.hStorageModel最后我们来看一下。从宏观上看，对于不同工作负载的数据库，存储方式有什么区别。目前，根据不同的应用场景和数据读写特点，数据库大致分为OLTP和OLAP两种类型，它们的存储方式也大不相同。OLTP，即On-LineTransactionProcessing，联机事务处理，特点是读写简单，通常只读/写一小部分数据，事务可以保证数据的一致性。目前，大多数在线业务都使用OLTP类型的数据库，例如电子商务，通常是为用户选择和购买产品。在大多数情况下，只会读取和更新有关该用户的部分数据。OLAP，即On-LineAnalyticProcessing，特点是查询复杂，需要读取大批量数据进行统计分析。针对这两种不同的工作负载，数据库中的数据组织方式存在一些差异，分别以行存储和列存储为主流。行存储是最常见的符合直觉思维的存储方式。它将具有不同属性的数据逐行组织并存储在页面中。这个比较适合OLTP，因为更新或者获取某个（或几个）特定数据（check）非常方便。但是如果我们的查询只需要取一部分列，而不是一个表中的所有列，那么这就会造成一定的浪费，因为我们可能会把不相关的列拿出来丢弃。列存储的组织方式则完全不同。它将具有相同属性的数据组织在一起，这使得扫描大量数据变得更加容易。具体的存储方式是将表中某一列的数据存储到页面中。由于具有相同属性的数据更可能具有相似的特征，这样的数据组织方式更适合压缩，节省存储空间。列存储更适合OLAP类型的数据库。本节主要介绍数据库的存储管理，其中夹杂了一些PostgreSQL的demo，大家可以自行参考。下一节将更上一层楼，看看内存缓冲池的管理。
