Lecture 1 Intro

关系模型是DBMS中应用最多的数据模型，它定义了：

  • Structure，关系和内容的定义。即关系拥有哪些属性，属性可以取哪些值。
  • Integrity，数据库的内容需要满足的限制。如year必须是数字。
  • Manipulation，对数据库的内容可进行的访问和修改操作。

一些名词：

  • A relation/table is an unordered set that contains the relationship of attributes that represent entities.（表）
  • A tuple/record/row is a set of attribute values(also known as its domain) in the relation.（表中的一行）
  • n-ary relation == n列的表
  • 主键，外键

数据操纵语言（DML）：

  • 过程式（Procedural），告诉DBMS如何取数据，对应关系代数。
  • 声明式（Declarative），告诉DBMS要什么数据，对应关系演算。

Lecture 2 SQL

讲SQL，skip。

Lecture 3 Database Storage I

Disk-based architecture

  • 数据库被存储在Disk（non-volatile storage）上，DBMS需要管理数据在Memory和Disk间的移动。这里的Disk是广义的，包括SSD，HDD和网络存储。
  • 对non-volatile storage而言，顺序访问远快于随机访问。DBMS希望最大化顺序访问。
  • Disk上的数据库文件被组织成Page（及其metadata）。
  • Execution Engine与Memory中的Buffer Pool交互，以Page为单位获取数据。后者的任务是在Disk和Memory中进行Page的移动并满足Execution Engine的请求，同时尽可能减少对慢速Disk的访问，而是用Memory做缓存。
  • 为什么不用mmap将文件映射到内存，即将Disk-Memory交互委托给OS呢？
    • DBMS对自己管理的Page有充分了解。不在Memory中的Page，可以另起一个线程去读，让它等待磁盘交互，主线程不会卡住，减少了磁盘交互带来的性能损失。OS没有这些知识，对它来说只能看到Page上的读和写，并在page fault handler中处理磁盘交互。这样一来，对DBMS而言，无法预测什么时候会发生磁盘交互，性能损失就是完全不可控的。
  • 尽管有madvise mlock msync等系统调用，让DBMS更好地利用OS提供的虚拟内存管理功能，还是建议在DBMS中自己实现操作系统的部分功能，它能做得更好：
    • 按正确的顺序flush脏页
    • 预取页（Specialized prefetching）
    • Buffer替换策略
    • 进程/线程调度
  • 确实有部分数据库实现依赖了mmap（如levelDB）或者部分依赖了mmap（如SQLite，mongoDB）。

Disk Storage

File Storage
  • 数据库建立在文件系统之上，现在的数据库实现一般不会自己实现文件系统。
  • Storage Manager维护数据库储存在Disk上的文件，它们被组织成Page的形式。
  • 数据库可以是单文件的（SQLite），也可以是多文件的，以规避 文件系统对文件大小的上限。
  • Storage Manager可能会在文件系统之上对读写请求做调度，比如合并连续的读请求。这个OS也能做，但道理和上面一样，没有DBMS做得好。

Database Pages

  • Page是一块固定大小（512B-16KB）的data，可以存放数据，meta-data，log等等。一般不会把不同类型的data混放在一个Page中，即Page有一个唯一的类型。
  • 有些DBMS实现中，Page是自含（self-contained）的，即读取某一页需要的metadata一定包含在这一页中。这样一来，丢失任何一页都不会影响对其他任何页的访问，提高了robustness。

Heap File:

DBMS中的页被组织成堆文件（Heap File）的形式，DBMS应能根据page id找到该页在Disk上的位置。Heap File是一系列无序页的集合，这些页中的tuple也是无序的。实现Heap File有链表和页目录两种方式：

  • Linked List：维护数据页和空闲页的列表，找到特定的页需要遍历。
  • Page Directory：维护额外的Directory Page，指出数据页在数据库文件中的位置。Directory还可以维护额外的metadata，比如该页是否空闲，该页中空闲slot的数目等等。但是DBMS必须保证页目录中的信息与数据页同步，因为写操作需要同时修改数据页和页目录，不是原子操作。注意这和自含（self-contained）是正交的概念，自含只涉及读取页内的数据，不涉及如何找到这个页。

Page Layout

每一页有一个header，存储页的metadata，如checksum，size，DBMS version，etc。

在页的内部存储数据大致有两种模式 ：

  • Slotted Pages：页中存储的数据是tuple。在header之后有一个slot array，它将每个slot映射到所对应的tuple起始位置的页内偏移量，这个array是从前往后生长的。tuple从页的末尾开始往前紧凑存放，当tuple区域和slot array区域相遇时说明页已存满。这么做的好处是tuple的长度可以不固定。删除tuple时，会在tuple区域中留下一个空洞，此时有些DBMS实现会把空洞前的tuple往后挪动，以保持tuple区域的紧凑。
  • Log-structured：页中不记录tuple，而是记录对表中的tuple所做的操作（插入，更新，删除）。这种做法适用于appen-only的存储系统，好处是写操作很快。但读操作很慢，需要反向扫log来重建tuple的状态。优化手段有：
    • 建立index，指出每个tuple最后一次被修改的位置。只需要从这个位置开始往前扫即可。
    • 周期性的对log进行压缩（如只保留对某属性值最后一次update的记录）。

Tuple layout

tuple同样由header和data部分组成。

  • header包含并发控制相关的信息，用以标示某一属性为NULL值的bitmap等等。注意header不需要包含schema信息（即每个tuple有几列，每列分别是什么类型），这个对于一张表里的所有tuple是一样的，不需要每个都存。除非DBMS本身是flexible schema的（如mongo DB），即每个元组的类型都可能不同。
  • data就是一系列字节序列，存放各个属性值，DBMS按照schema中记录的类型对每一列进行解读。一般按照建表时指定的顺序存放各属性，并且tuple的长度一般不能超过一页的大小。

Denormalized Tuple Data：

所谓denormalized是关于范式的，简单来说实现更高的范式就要把大表拆分出更多的小表，称为normalize。所以denormalize就是把小表合并成大表，或者称之为表的内联或者"pre-join"。如果一张表外键了另一张表，另一张表又列数不多，可以直接把它内联进来，当作一张表来储存，使tuple变得更大，这样访问的时候不用取两张表再来join。

以上只是storage上的trick，对上层而言这还是逻辑上的两张表。

Lecture 4 Database Storage II

Data Representation

浮点数：

  • FLOAT/REAL等类型属于变长浮点数，它们和C语言中的类型一样遵从IEEE-754标准。对它们进行运算就是直接使用CPU的浮点指令，运算速度较快。但它们无法被精确表示，因而会产生舍入误差。

  • NUMERIC/DECIMAL等类型是定长的，可以保证精度。在DBMS内部，它们通常被表示为一个结构体，需要有额外的metadata来记录其长度，精度等信息。对它们的运算是复杂逻辑（类似于高精度），因此速度较慢。

Large Value：

  • tuple的长度一般不能超过page，对于需要空间很大的属性值，DBMS会使用overflow page，在额外的页上存储，tuple里只有指向overflow page的指针。
  • 另一种做法是external storage，tuple里存一个指向文件的指针，在DBMS外部的文件中实际存储数据。这种做法一般用于存储图片/视频等。坏处是DBMS不能写入这些文件，也就没有Durability保证（文件不归DBMS管，在文件系统上，可能丢掉）；并且读的时候需要走文件系统API，速度慢。

System catalog存有关于database的metadata（表，索引，访问权限等等），大部分DBMS实现把catalog当作一张表存储，一般有封装后的特殊命令访问这张表（如mySQL中的show tables）。

DB Workloads

  • Online Transaction Processing（OLTP），simple queries that read/update a small amount of data that is related to a single entity in the database.一般以写为主，执行速度快，时间短，大量出现。例如网上商城中每个用户对自己购物车的增删改查操作。

  • Onlie Analytical Processing（OLAP），complex queries that read large portions of the database spanning multiple entities.一般以读为主，执行速度慢，主要是对已有数据的分析操作。比如统计网上商城中某时段销量最高的商品。

  • Hybrid Transaction + Analytical Processing（HTAP），两者的结合。

Storage Model

  • N-ary Storage Moel（NSM），即行存储，将一个tuple中各属性值连续存放。这种方式更适合OLTP，因为OLTP操作的一般是整个元素（添加和删除），并且操作的数据量不大，把一个tuple放在一起可以在一页里完成对tuple的操作。
  • Decomposition Storage Model(DSM)，即列存储，将表中所有tuple的某一属性放在一起存放。这种方式更适合OLAP，因为OLAP需要的是一系列元组的某几个属性值，如果行存储的话会读入很多不需要的属性。

Lecture 5 Buffer Pools & Memory Management

Lock vs Latch

  • DBMS中谈论的latch更接近于OS中所说的lock，它保护DBMS内部的数据结构，不向外界暴露。
  • 而lock在DBMS是high-level的原语，保护的是tuple，table乃至database这些对象，并且是transaction维度的，保证当前事务的读写操作不被其他transaction影响。DBMS可以向用户暴露，当前事务执行时拿了哪一个lock。此外lock还需要支持rollback，如在崩溃重启后撤销掉做到一半的变更，保证DB的consistency。

Buffer Pool

Buffer pool是内存中的page cache，对page进行缓存，避免每次都要访问disk。DBMS总是先尝试在Buffer Pool中使用page number获取某一页，如果取不到才去访问disk。

Buffer pool被组织成frame（页框）的数组，每个frame里可以放进一张disk page。在整个系统的生命周期中，一个frame可能经常被放入不同的page，因此buffer pool还需要维护page table将page number映射到frame number（即内存中的位置）。注意区分page table和之前disk storage中的page directory。

Buffer pool同时维护了page的metadata：

  • dirty flag，该页是否在内存中被修改，决定该页是否会被写回到disk。
  • pin counter，记录了当前读写此页的线程数目，一个线程在访问页之前应该先递增pin counter。如果页的pin counter大于0，它就不能从buffer pool中换出。

Buffer Pool Optimization

有一些针对buffer pool的优化手段：

  • Mutiple Buffer Pools，维护多个而不是一个缓冲池。主要有两个作用：
    1. 可以对不同的缓冲池应用不同的内存分配策略。如聚焦于提升单个事务执行速度的local policy，和聚焦于全局所有事务执行速度的global policy。
    2. 可以避免高争用。每个Buffer Pool需要有latch保护内部数据结构，增加缓冲池的数目并让每个缓冲池管理所有disk page的一个子集，降低了在每个latch上争用的线程数目。见Lab1。
  • Prefetch，对于某一query，DBMS知道可能需要哪些page，可以在请求第一个页的时候顺便把需要的其他页一起读了。注意这里的prefetch不同于OS能提供的服务，OS不知道page的内容，它可能只是预取了连续的页；但DBMS可能会根据query的内容预取非连续的页（比如PPT上的例子，预取索引树访问路径上的页）。
  • Scan Sharing，如果两个query需要遍历有重合的page集合，可以将它们合并。考虑buffer pool size=3的情形，q1和q2都要访问page1-page6。如果q1刚将page4读入buffer pool（此时为4,2,3），q2开始遍历并试图把刚刚LRU出去的page1再读回来，这就导致了震荡。使用scan sharing可以把q2的scan pointer合并到q1上，它们先一起访问page4-page6，q1结束后q2再回过头来访问page1-page3。
  • Buffer Pool Bypass，如果想减去从buffer pool中读数据的开销（拿锁，检查page在不在内存中），或者知道读入的data短时间内不会被再次使用，可以绕过buffer pool，直接将page从disk读入到某query的本地内存中。

OS有自己的page cache，这会导致页被重复缓存，而且该page cache有不同的替换策略。多数DBMS会选择使用direct IOO_DIRECT读写文件系统以绕过OS page cache。

Replacement Policy

  • LRU，维护每个页最后一次被访问的timestamp。
  • Clock，近似的LRU。所有page维护成循环队列，不维护timestamp只维护标记位，访问时置1。换出时找到第一个标记位为0的页换出，并把一路上标记位为1的页置0。指针的位置会保留，下次运行时接着上一次走。

这两个策略都有sequential flooding问题，即遍历大量page时，最近访问的反而是最不需要的page。解决方法有：

  1. LRU-K，记录最后K次访问的时间戳，根据其差值预测该页下一次被访问的时间，基于此设计换出策略。
  2. Localization，基于query/transaction而非global的维度决定换出，避免query间互相影响，导致缓冲区震荡。
  3. Priority Hint，每个页有优先级，由transaction根据具体的query内容指定（比如树的根节点换出优先级很低）。

Dirty Page

换出时可以优先选择换出non dirty page，避免写入disk开销；然而dirty page已经被写入过，因而未来更不可能被使用到，这是一对trade off。一种策略是background writing，在后台由单独的线程负责将脏页写入disk。

Lecture 6 Hash Tables

哈希表可用于构建索引，在O(1)时间内完成查找。但是哈希表索引显然不适用于范围查询，如100 < x < 200。

哈希表的实现由两个部分组成：

  • hash函数，把key映射到integer，需要在速度和collision rate之间做出权衡。Facebook XXHash3是目前最先进的hash函数。
  • hashing scheme，即处理hash collision的方式。要在构建更大的hash表（低碰撞率，高内存占用）和执行额外的逻辑处理collision之间达到平衡。

Static Hashing Schemes

静态hash指的是哈希表的大小（元素个数）事先已知，如果需要放入更多的元素，必须从头构建更大的哈希表。

  1. Linear Probe Hashing，遇到碰撞就从hash slot开始往后找位置，直到能放下为止。找元素的时候需要从hash slot开始往后找，直到找到或遇到empty slot为止。删元素的时候比较麻烦，可能需要把后面的往前挪（复杂），或者采用逻辑删除的方式（tombstone），即虽然这里没有元素，但不是真正的empty slot，还需要往后探测。

    此外，如果一个key对应多个value，有两种解决方法：维护一个外部链表存某个key对应的所有value，或者直接不管，允许hash表内有相同的key存在。

  2. Robin Hood Hashing，对线性探测做“劫富济贫”式的修改，尽量保证每个元素实际存放的位置离hash slot（即应该存放的位置）尽可能近，可能需要让老的键值对给新的让位置，增加了读写次数。

  3. Cuckoo Hashing，使用多个hash表和多个（相同，仅seed不同的）hash函数，每张表对应一个。插入新元素时找一张有位置的表插进去，如果每个都没位置，就随机找一个占位置的旧元素把它踢走，旧元素必须另找一张表，可能需要踢走别的元素，循环下去。可能出现循环情况，这说明hash表太小了，需要resize。

    Cuckoo（布谷鸟）会在别的鸟巢里下单，把别的鸟赶出去，这就是这个算法的名称由来。

Dynamic Hashing Schemes

动态hash可以在不从头构建hash表的情况下，对其进行扩容。

  1. Chained Hashing，通过链表处理碰撞，每个slot都维护一个bucket的链表，元素装满一个bucket就再连一个上来。
  2. Extendible Hashing，为了解决Chained Hashing在极端情况下退化成链表的情形，它允许多个slot指向同一个bucket链表。
  3. Linear Hashing，一次只会增长/缩小一个bucket。

Lecture 7 Tree Index

Table Index

Table Index是表中某些列的拷贝，它们可能是针对某个/某些属性排序的，DBMS在执行相关的查询时可以通过对应的索引进行检索，而不用顺序访问。使用Index的代价就是需要占用额外空间，并且需要让索引和表内容保持同步。DBMS需要在执行查询时决定是不是走索引，走什么索引。

树索引适用于点和范围查找，但不适用于关键词查找。

B+ Tree

B+树是一种自平衡的搜索树，允许对数复杂度的搜索，顺序访问，插入和删除操作。它很适合基于Disk的，只能以块为单位读写磁盘的DBMS。

B+树将data全部存放在叶子节点，中间节点只是指引搜索叶节点的位置。另外叶子节点之间有sibling pointer相连，便于顺序访问。

B+树的每个节点都存放一个(key, value)数组，这里的key是建立索引时指定的属性集合，并且数组是按照这个key排好序的。对于中间节点，value是指向其他节点的指针；对于叶子节点，value存放实际的数据，这里又有两种情况：

  • value存放数据（tuple）本身。一张表的所有索引中只有一个能采用这种方式存储，此时的key一般对应表的主键。
  • value存放指向数据（tuple）所在位置的指针。

B+树是一棵满足如下性质的M叉树：

  • 完美平衡，所有叶子节点的深度相同。
  • 如果一个中间节点存放了k个key，它一定有k+1个非空的子节点。
  • 每个中间节点至少是半满的，即节点中key的个数介于[M/2-1, M-1]之间。
Selection Conditions

基于B+树的索引可以支持基于部分索引来查找。比如索引建在(attr1, attr2)上，给定的查询条件如果只关于attr1，也可以走该索引。如果只关于attr2，该索引可以排除掉一部分不可能存在符合条件的tuple的子树。

Duplicate Keys

处理key重复的方法包括：

  • 把tuple id作为key的一部分一起存储，让key唯一。
  • 引入overflow node存放重复的key，比较复杂。
Clustered Index

有些DBMS直接把tuple按照主键索引有序存储，这就要求表必须有主键。如果建表时不指定会自动创建自增主键。

Node Size

B+树中节点大小的选择和多种因素有关。一般来说，对于越慢的存储设备，最有效率的node size越大。另外，workload也是要考虑的因素，如果点查询很多，node size应该比较小，防止读入过多的冗余数据。大范围的顺序查询则需要比较大的node size。

Variable Length Keys

索引中的key长度不固定，解决这种问题一般使用键值映射的方式：所有的key-value对存放在外部的字典里，leaf node里只放这个字典的index。

Prefix Compression

一个节点中的key可能有相同前缀，可以把前缀抽出来存储节省空间。(robbed, robbing, robot) -> (rob{bed, bbing, ot})。

Lecture 8 Concurrency Control

Lock vs Latch

Locks Latches
隔离用户的不同事务 隔离线程
保护DB内容 保护内存中的数据结构
整个事务持续期间被持有 临界区中被持有
模式：shared，exclusive，update，intention 模式：read，write
lock manager检测和解决死锁（waits-for，timeout，aborts） 编程者保证代码正确性，不产生死锁

Latch有读写之分，读latch可以和其他读latch共同进入临界区，写latch不能和任何latch共同进入临界区。

Latch Implementation

  1. OS mutex，如C++的std::mutex。使用OS提供的基础设施很方便，但是时间代价比较大。一旦拿锁失败，该线程就会陷入内核并被OS block。Linux提供了futex（fast user-space mutex），但还是改善不了拿锁失败导致线程被阻塞的情况。
  2. TAS，通过对共享内存变量做Test-and-set实现latch，如C++的std::atomic<T>。这种方式实现的latch是由DB MS控制的，DBMS可以决定拿锁失败的时候的行为（重试，终止，陷入内核阻塞当前线程等等）。这样做比OS mutex效率更高，但在高争用情况下表现依然不佳，比如一旦一个线程成功更新了latch，其他线程的cache一起失效，引发cache stampede。
  3. 读写锁。在以上两种latch的基础上允许多个reader同时进入临界区。这种实现需要注意starvation的问题，防止大量的读请求把写请求饿死。

Hash Table Concurrency Control

在Hash表中，线程某一时刻只会访问一个page/slot，不需要同时持有两把锁。因此并发控制比较容易，以page/slot的粒度设置latch即可。对于resize操作，需要全局上锁，但这种情况比较稀少。此外，对于linear probe hashing，所有线程都是以从前往后的顺序访问各page/slot，这就不可能出现死锁。

如果以page粒度设置latch，一般采用读写锁的方式提高并行度；如果以slot粒度设置latch，一般就不用读写锁了，获得的额外并行度有限，不如用简单的spin latch节省latch metadata的开销。

对于linear probe hashing，可以用compare-and-set做出lock-free的实现。调用cas(NULL, value)，如果失败就尝试下一个slot。

B+ Tree Concurrency Control

B+树中的latch需要解决两个问题：

  • 多个线程试图修改同一个节点。
  • 有线程正在做merge/split节点的操作，此时另一个线程开始遍历树。
Latch Crabbing Protocol

基本思想就是在拿子节点的锁之前，保证拿住父节点的锁。拿到子节点上的锁后，如果能确保子节点是“安全”的，就释放所有祖先节点上的锁。“安全”指当前节点不会发生merge/split，是针对具体操作而言的：

  • 对于read，任何节点都是安全的。
  • 对于insert，如果当前节点满了，它有被split的可能（现在还不确定，要看子树长啥样），因而不安全。
  • 对于delete，如果当前节点刚好为half full，它有被merge的可能（同样，要看了子树才能确定），因而不安全。

释放所有祖先节点上的锁时的顺序不影响正确性，但从提升性能的角度出发，应该优先释放深度更浅的锁，因为它锁住了更大的子树。

Better Latch Crabbing Protocol

Latch Crabbing有一个很明显的问题：所有操作都从root开始，都要拿root节点的锁，形成了一个单节点的高争用。

一种优化策略是引入读写锁，并且作乐观的假设：merge/split发生的频率很低，大部分情况下只有叶子节点需要被修改。

在这种假设下，一个线程在遍历树的过程中，对路径上的节点只拿读锁，对叶子节点拿写锁（如果是insert或delete）。如果遇到了需要merge/split节点的情况，再从root开始重新遍历，并且一路上拿写锁。这样一来，对于大量的safe情形，只拿读锁保证了多个线程可以同时遍历树，提高了并发度。

Leaf Nodes Scan

之前讨论的都是自上而下的遍历树，所有线程都是按照一个顺序拿锁，不可能出现死锁的情况。但如果考虑到叶子节点之间的指针，可能有线程从左往右的遍历叶子，也可能从右往左的遍历叶子，这就可能导致死锁。

为了解决这个问题，可以使用一种保守的策略：如果一个线程拿锁失败，它不再重试直到拿到为止，而是立刻释放所有拿住的锁，并从头开始执行整个操作。