CMU 15-445 lec7, 8, 9

database

这是一篇关于 CMU 15-445 数据库导论 lecture7 到 lecture9 的笔记，主要讲了DBMS是如何获取内容的，以及DB的数据结构Hash Table和B+Tree和并发的实现

lecture 7 - 9

Hash Table

Hash Table这个概念已经讲烂了，不必多说了。在课程当中，非常学术性地对其分了几个类

Bloom filter: 一个名叫 Bloom 的人提出了一种来检索元素是否在给定大集合中的数据结构，这种数据结构是高效且性能很好的，但缺点是具有一定的错误识别率和删除难度。并且，理论情况下，添加到集合中的元素越多，误报的可能性就越大。

布隆过滤器自带一些hash function和一个初始全为0的数组。当元素要加入时，会先过一遍哈希函数得到几个值，然后将这几个值对应的数组位置置1。查询时，会再过一遍哈希函数得到几个值，然后检查这几个值对应的数组位置是否都为1，如果都为1，则该元素很可能存在于集合中。

  1. Static Hashing Schemes: 静态哈希策略，指的是在创建表的时候就已经确定好了哈希函数，并且哈希函数的选择是固定的。然后扩展的方式类似于vector，每次都要重新创建整个表，并将大小设置为两倍。
    1. Linear Probe Hashing: 线性探测，当发生冲突时，通过一个固定的步长来探测下一个槽，直到找到一个空槽。
    2. Cuckoo Hashing: 布谷鸟散列，每个元素都含有多个hash function可供替换。当发生冲突时，将两个元素交换位置，然后再换用不同hash function散列，直到找到一个空槽。
  2. Dynamic Hashing Schemes: 动态哈希策略，指的是在创建表的时候并不确定哈希函数，而是在运行时根据需要动态调整。
    1. Chained Hashing: 链接法，将哈希表的每个槽链接成一个链表，当发生冲突时，将元素插入到链表的尾部。(我们最熟悉的)
    2. Extendible Hashing: 可扩展哈希 这个语言很难表达，推荐去看图像。它存在着一个global计数位，如果是2，就代表看的是哈希映射后结果的前2位(对应总共有222^{2}个slot)，比如001和000的前两位相同，就会被分在同一个bucket中。当试图插入而bucket发生溢出的时候，就将global counter加1，然后重新分配bucket后再进行插入。此外还存在着local计数器，它代表了当前bucket当中元素前缀相同的位数，比如110和101这样的local计数器的值就是1，代表了有2global−local2^{global - local}个slot指向这一个bucket。
    3. Linear Hashing: 线性哈希。跟Probe不同的是，当溢出时会采用分割并换用不同哈希函数，比如本来是hash(key) = key % n可以变成hash(key) = key % 2n。

Tree Indexes

这个差不多就是一种键值对的形式，由索引得到数据的过程。

B+Tree跟B-Tree大致一样，区别在于后者在每个节点都存储了值，而B+Tree只有在叶子节点才存储值。这就使得B+Tree只在底层存储数据，对于遍历只需要在底层进行遍历即可(若同层节点之间有连接)，而不是像普通树一样进行中序遍历这种。

B+Tree的每个节点除了存储键值对外，还存储了指针，指向子节点。这样可以减少磁盘IO，提高查询效率。B+Tree的每个节点都包含一个键/值对数组。

B+Tree中有三种节点，分别为root node, inner node, leaf node，其中inner node有指向下一级node的指针，leaf node指向tuple的指针。

Leaf node的结构如下:

  1. Record IDs: 记录ID，唯一标识一条记录
PageID <- | K1 | V1 | K2 | V2 | ... | Kn | Vn | -> PageID
  1. Tuple Data: 记录数据，包含键值对
Sorted Keys
| K1 | K2 | ... | Kn |
Values
| V1 | V2 | ... | Vn |

形式上，B+Tree是一个M向搜索树（其中M表示一个节点可以拥有的最大子节点数），具有以下属性:

  1. 它是完全平衡的，即每个叶节点有相同的深度
  2. 根以外的每个内部节点都至少有一半已满，即对于每个节点容量为M的树，至少有M/2个子节点，或者说至少有M/2个键值对。
  3. 每个具有k个键的内部节点都有k+1个非空子节点。这个就类似于一根绳子被切了k刀，那么它会被分成k+1段。

所以有几个推论:

  1. 若节点存在空键，空键将聚集在第一个叶节点或最后一个叶节点中，根据索引类型（先为NULL或者后为NULL）。
  2. 由于每个节点都有指针，所以查询的效率是O(log n)，其中n是树的高度。
  3. 由于每个节点都有指针，所以插入和删除的效率是O(log n)。

对B+Tree的操作

  • Insertion: 遍历树并使用内部节点来确定要将键插入的叶节点

    1. 找到正确的叶子节点L
    2. 将新entry(即键值对)插入到L当中，如果节点没满直接结束插入
    3. 如果L满了，则将L均匀分裂成两个节点L1L_{1}和L2L_{2}，并向上复制中间键，将指向L2L_2的条目插入原先L的父项

  • Deletion: 在插入中，当树太满时，我们偶尔不得不拆分叶子；如果删除导致树不到半满，我们必须合并(merge)以重新平衡树

    1. 找到正确的叶子节点L
    2. 删除entry(即键值对)，如果L还是超过一半满的话，结束删除
    3. 尝试重新分配，向Sibling节点借个键值对过来
    4. 如果重新分配也失败了，直接合并L和Sibling节点，并必须删除父级中指向L的条目

对于插入相同数值的重复节点:

  1. append record: 重复的节点多加一个附加的ID标识来区分。采用附加记录ID作为密钥的一部分。由于每个元组的记录ID都是唯一的，这将确保所有键都是可识别的
  2. overflow node: 多出一条链专门装溢出的节点。允许叶节点溢出到包含重复密钥的溢出节点中。尽管没有存储冗余信息，但这种方法的维护和修改更为复杂。

Index Scan Page Sorting: 索引扫描页面排序，是一种优化查询过程的技术。先获取所有需要查询的索引，然后对它排序，这样就可以使得连续几个排序可能都处于同一页当中，从而最大化地利用cache。它通过对索引扫描结果进行排序，使得查询结果的顺序与索引顺序一致。

Clustered Indexes: 聚簇索引，按照主键(primary key)来排序，如果没有会按照每个数据库自动来创建。

B+Tree的设计选择

又是一个经典的Trade-off…

  1. Node Size: B+Tree的高度决定了查询效率，高度越低，节点越大，查询效率越高，但是也越占用空间。所以，我们需要根据实际情况来选择合适的高度。点查询更喜欢尽可能小的页面以减少加载的不必要的额外信息量，而大型顺序扫描可能更喜欢大页面以减少所需的获取次数

  2. Merge Threshold: merge显然可以优化，每次删除都合并的话开销太大了，这个就类似于Copy-On-write的思想，拖字诀，等到不得不合并的时候(Threshold决定的)再合并。

  3. Variable Length Keys: 用不同的键来存储信息

    1. Pointers: 用指针来替代key
    2. Variable Length Nodes: 用变长节点来存储
    3. Padding: 填充，不论实际内容多长，都填充到对齐长度
    4. Key Map/Indirection: 将key替换为单独独立出来的dictionary的索引

  4. Intra-Node Search: 节点内搜索，也就是说，当我们寻找完某个节点了，那时候我们就停在这个节点，以这个节点为起点，开始寻找下一个节点(而不是重新从Root Node开始)。

    1. Linear: 线性查找，跟线性探测哈希一样，通过一个固定的步长来探测下一个槽，直到找到目标，时间复杂度O(n)
    2. Binary: 类似于二叉查找，跟二叉树一样，通过比较中间键来确定目标，时间复杂度O(log n)
    3. Interpolation: 插值查找，通过meta-data来估算目标的位置

B+Tree的优化

  1. Pointer Swizzling: 为了跳过从Buffer Pool来fetch指令的流程，来存储原始指针直接指向Page ID，这样可以避免到Page Table的搜索与转换
  2. Bulk Insert: 批量插入，一次性将多个节点插入到树中，尽可能紧密的插入Leaf Node，减少磁盘IO
  3. Prefix Compression: 前缀压缩，将相同的前缀的键值对放在同一个节点中，减少磁盘IO
  4. Deduplication: 去重，将相同的键值对合并到同一个节点中，但依旧需要对它们进行区分，减少磁盘IO
  5. Suffix Truncation: 后缀截断，因为所有inner node都只是起到一个route路由的作用，所以我们应该尽量减少找leaf node路途当中的冗余inner node
  6. Write-Optimized B+Tree: Split(for insertion)/Merge(for Deletion)这两个对节点的操作成本高昂。因此，B树的一些变体，如Bε-Tree，会记录内部节点中的更改，并在稍后将更新延迟传播到叶节点。

Concurrency Control

Concurrency Control是DBMS的核心问题之一，它是保证多个用户同时访问数据库的关键。

Latch

  1. Test-and-Set Spin Latch (TAS): 即原子操作std::atomic<T>。一种最简单的并发控制策略，它通过一个原子操作来实现互斥，即将一个变量的值设置为某个值，然后返回之前的值。如果之前的值与期望值相同，则说明没有其他线程在修改这个变量，可以继续执行；否则，说明其他线程正在修改这个变量，需要重新尝试。
  2. Blocking OS Mutex: 即互斥锁std::mutex，它通过系统调用来实现互斥，即当一个线程试图获取一个互斥锁时，如果锁已经被其他线程占用，则该线程会被阻塞，直到锁被释放。
  3. Reader-Writer Lock: 即读者-写者锁std::shared_mutex，它允许多个线程同时读同一个资源，但只允许一个线程写。读者只能读，写者只能写。

HashTable Latching

HashTable的并发控制也是很有必要的，因为它是有方向性的。如果说一个线程要从上往下操作(insert, delete, search)，另一个要从下往上操作(merge, split, update)，就会出现死锁。此外对于BlinkTreeB^{link} Tree来说，它每个同层的节点之间还拥有Sibling指针，如果两个线程一个向左一个向右，也会出现死锁。

有两种以latch的粒度(granularity)为区分的解决方案:

  1. Page Latch: 对于在同一个page当中的读写效率很高，不同的话则效率低下。同时对并行度(prallelism)是降低的，因为同一时间只有一个线程能访问一个page。
  2. Slot Latch: 增加并行度，但是添加开销。

此外还有CAS(Compare-and-Swap)操作这个概念。CAS操作是一种原子操作，它通过一个比较-替换操作来实现互斥，即当一个线程读一个变量时，它会将这个变量的值与一个期望值进行比较，如果相同，则说明没有其他线程在修改这个变量，可以继续执行；否则，说明其他线程正在修改这个变量，需要重新尝试。CAS操作的优点是它不需要锁的开销，而且在并发度较高的情况下，它的性能要优于锁。

B+Tree Latching

总的来说，我们要防止两类情况的发生:

多个线程同时对同一个节点中的内容进行修改

某个线程在其他进程对节点进行split/merge操作时进行遍历

safe的定义

        safe node
            ||
            \/
node that will not split/merge
            ||
            \/
not full(on insertion)
more than half-full(on deletion)

总结来说，如果某个节点确定为safe就可以被解锁

R锁代表Read读锁，W锁代表Write写锁

由此可以发现对于basic crabbing，每次进行写操作都会使得根节点处于写锁的独占状态，使得其他线程甚至连读都不允许。

  1. Basic Latch Crabbing Protocol

    1. 对于find/search操作: 从上往下(root -> leaf)遍历B+Tree，先是父节点申请一个R锁，然后子节点申请R锁，父节点发现子节点只是read而不进行修改，所以判定为safe，父节点解锁，以此类推直到leaf node。
    2. 对于insert/delete操作: 从上往下(root -> leaf)遍历B+Tree，先是父节点申请一个W锁，然后子节点申请W锁，子节点判断这次的修改会不会导致父节点、及其祖宗节点的变化(父节点和祖宗节点safe与否)，若会则保持父节点及之上的W锁，若不会则把上面全部解锁了

  2. Improved Latch Crabbing Protocol

    1. 对于find/search操作: 是一样的
    2. 对于insert/delete操作: 将除了leaf node之前的所有路径都设置为R锁，，直到leaf node上设置W锁。如果叶不安全，释放以前的所有锁存器，然后使用Basic的插入/删除协议重新来一遍，即每次都是W锁的形式。

那么上面的这两个Crabbing都是为了解决垂直的竞争，从上到下或者从下往上的冲突，那么同一行的水平竞争该如何解决呢?

这就要提到Leaf Node Scan:

对于find/search操作，同级的叶子节点的扫描读取加R锁是没有问题的，因为多少个人读都不改变内容。但是对于insert/delete操作，同级的叶子节点的扫描读取加W锁是不安全的，因为其他线程可能在修改这些节点。

出于B+Tree无法设置死锁监测，我们只能用编码来实现避免死锁。叶节点同级锁存获取协议必须支持“无等待”模式。