CMU Database Systems - Storage

Database Storage

存储分为volatile和non-volatile，越快的越贵越小

那么所以要解决的第一个问题就是，如果尽量在有限的成本下，让读写更快些

意思就是，尽量读写volatile存储，但是volatile比较很有限，所以需要合理的在两种存储上去swap

但是技术是在飞速的进步的，所以现在有Non-volatile memory

所以最近流行内存数据库，因为当前的memory和磁盘间的IO瓶颈已经消除，所以当前的瓶颈是CPU cache和Memory之前的问题

这个问题会在下一门课里面说

所以继续前面的问题，怎么解决disk和memory之间的IO瓶颈

一个直觉的想法就是，交给操作系统去做，使用虚拟内存，Virtual Memory

mmap可以产生内存文件，把磁盘文件的内容map到内存的地址空间，这样有个问题就是如果有多个并发写，需要同步机制，系统也提供右图这些同步指令

但是数据库管理系统往往希望做的更精细，因为操作系统是个通用方案，一定达不到性能最优

下面我们来看第二个问题，DBMS如何将数据库的数据放到磁盘文件上？

这里有个选择，DBMS是否要用系统的文件系统，还是拿一块raw storage自己管理，现在一般的选择是还是使用文件系统，毕竟方便

既然用文件系统，那么DBMS就需要把数据库数据存成一个或多个文件

这里有个概念，P age ，文件是由一堆page组成的

page其实就是固定大小的数据块，那为什么要有这层抽象？

这个和我们使用的存储有关，当前用的磁盘，除了慢，还有个特点是对顺序读写比较友好，因为随机读需要磁头不断的机械移动的，这个想想也很慢

所以文件系统和磁盘间的IO，需要尽量批量读，读写数据的最小单位称为数据块，一般是4K，为什么是4K，应该是因为比较经济

而数据库的page是基于文件系统的，所以设计成4k的倍数会比较合理

数据库会自己维护一个page id到实际存储地址（文件+offset）的映射

那么如何在磁盘文件上管理page？

有三种方式，最常见的是Heap FIle

HeapFile就是用来放page的文件，当然我们可以通过文件名+offset，访问某个page

同时我们需要可以遍历所有的page，知道哪些page有free space可以用来存放tuples

所以这里heap file也有两种实现方式，

继续看看Page的构造是怎么样的？

可以看到在page中的header，存储了一些元数据，如果需要self-contained，就需要包含scheam，编码信息等

那么data，是如何组织的了？

其实有两种方式存储数据库的数据，

Tuple-oriented和Log-structured

Tuple-oriented主要的存储方式是，slotted pages

这个方法关键就是加入了slot array来索引各个tuple，这样就可以兼容变长的tuples，不然怎么知道每个tuple从哪里开始，删除tuple也更简单

如果是Log-structured，写数据会比较简单

但读数据就比较麻烦了，需要replay出数据，因为你只记录了log吗

提供读性能的方式有两种，尽量减少replay的数据，就是打snapshot或建index

比较常用的就是定期的做compaction，比如HBase, Cassandra，LevelDB，RocksDB

Compaction分为两种，按层逐级compact，或是universal

最后，tuple本身的存储结构是怎么样的？

同样Tuple也有一个header，里面包含元数据，比如这个tuple可见性，BitMap表示哪些是NULL

注意这里一般是不会包含schema，因为在每个tuple都包含没有必要，一个table的schema是固定的，单独存就好

Denormalized Tuple Data

这是一种针对查询的优化，

Denormalized，都知道关系模型有范式，冗余数据一定是会打破范式的，所以是de-

两个表join，把需要的字段冗余到一张表中，称为pre join，读的时候会比较快，单纯从当前page就可以完成，但是写就麻烦了，因为打破范式了吗

总结一下上面的说的，如下图

这里page管理用的是direction的方式，所以读取page2，

首先要把direction page加载到buffer里面，这样读到page2的地址然后再去读出page2，然后Execute engine需求去解析page

Page中就是tuple的集合，tuple是a sequence of bytes，但如果我们要使用这些数据，首先要把这些bytes转化为相应类型的数据

主要的类型如下，

需要特别关注的，

浮点数和定点数

定点数就是小数点是固定的，所以我们用int分别存储小数点前后的数字就可以实现，定点数是可以做到精确计算的，但是局限也很明显，只能表示固定精度

浮点数就比较复杂了，因为小数是连续的，无限的，而计算机实现是离散的，有限的

所以要在计算机里面表示浮点小数，就需要用trick的方法去近似，定义出的标准就是IEEE-754，浮点运算是近似的，非精确的

VARCHAR，BLOB

由于tuple大小不能超过page，比如对于varchar，如果大于page，需要把多的存放到overflow page里面

而对于blob这样的类型，干脆就需要存放到外部文件中，这里注意对于存放到外部文件的数据，是不保证transaction等语义的

那么现在有个关键的问题，数据库的元数据是存储在什么地方的？

Catalogs，Catalogs的信息可以从Information_schema表中读取到

不同的库，对于元数据读取有不同的shortcuts，

最后再看下，行列存的区别，

行存，row storage，称为n-ary storage model

对于左图的OLTP的需求，行存很适合，插入和更新比较简单，整行的查询

但对于右图，OLAP的需求，行存会比较慢，BI需求往往需要扫描大量的行，但只是用其中的部分字段

列存，column store，decmposition storage model

相对于行存，列存是把一列的数据集中存储在一个page中，

这样上面的例子，就只需要读包含这两个列的page，其他page就不用读了

列存关键的问题是如何恢复成行？

这里给的方法也很简单，如果列中的每个value都是等长的，那直接根据length除就知道是第几行的

或者，就是在每个列里面记录下tupleid