Liang's blog

数据库背后的数据结构

2022-02-17

来设计一个最简单的数据库

可以通过两个bash函数来实现一个简单的KV存储

#! /bin/bash

db_set() {
  echo "$1,$2" >> database
}

db_get() {
  grep "^$1," database | sed -e "s/^$s1,//" | tail -n 1
}

这里我们用两个函数，一个写入，一个读取，底层存储是一个叫database的文件来做的，每行保存一个KV对，由逗号分开，每次调用写入都会往文件后面append进去一个新的记录，所以如果你对同一个key做过多次更新，那么旧的记录不会删除，每次都会生成新的记录。读取时候会去查到包含key的那些记录，然后返回最后一条记录，也是最新的记录。

$ db_set a 'a'
$ db_set b 'b'
$ db_get a
a
$ db_set a 'A'
$ db_get a
A
$ cat database
a,a
b,b
a,A

在简单数据情况下这个函数的表现还不错，但是在数据库记录很大的时候就表现的很糟糕了。db_get 需要扫描整个数据库问题找到查找的那个key，时间复杂度是O(n)

想要高效的从数据库查找特定的key，我们需要一个索引来帮我们快速查询数据。其背后的基本思想就是存储一些元数据，来帮助我们快速的找到查找的数据，如果我们想要通过不同的方式查找相同的数据，那么则需要在数据的不同字段上建立不同的索引。

索引的建立并不会影响存储数据的内容，它只会影响查找的性能。维护额外的索引也会导致额外的开销，例如写入的性能也会受到索引影响，因为每一个写操作都要去更新对应的索引。

使用Hash表来建立索引

利用hash表来做一个KV存储是最常见的做法，我们这里稍微有一些不同，重新设计一个简单的数据库

hash table index

这个其实就是Riak的存储引擎Bitcask的基本实现原理

这里有个问题：数据都存储在一个文件里，而且都是增量式，那么如何避免磁盘空间被占满呢？ 有个很好的解决办法就是把数据分成segment来存储

压缩一个数据segment，只保留最新的值 压缩一个数据segment，只保留最新的

压缩和合并多个segments 压缩和合并多个segment

实际中还有很多细节来保证这个设计的正常工作

同时Append-only 被证明是更好的设计， 而不是去修改已有的记录

但是hash表作为索引实现也有一些限制:

SSTable 和 LSM-Tree

在之前的segment里面保存的是一些按照写入顺序排序的KV键值对，对于同一个key来说，后面写入的值最终会替代前面的值，除此之外，不同key之间的顺序其实并不重要。这样的话可以对我们的segment做一些小小的修改：我们要求segment里面的KV对要按照key排序。我们把这个叫做Sorted String Table，或者SSTable。

SSTable对比使用hash表的log segment来说有很多优势：

可是数据库接受的数据写入请求顺序都是随机的，那么如何在一开始就能够有按照key来排序的segment呢？ 其实在内存中维护一个有序的数据结构是比较简单的，有很多树结构都可以使用，比如红黑树，AVL树，我们可以以任意顺序写入数据，读取时候可以读到排序后的数据。

这样我们的数据库设计看起来是这样：

这里有个问题：所以每个segment都对应一个hash table，对吗？

不过这里我们还是能看到一个问题，最新的数据其实都是在memtable里保存着，如果数据库挂了，那么最新写入的数据还没来得及写到磁盘中，就会丢失了。为了避免这个问题，我们可以在磁盘上额外保存一个log文件，每一个写操作到memtable都会立即在这个log里记录，在这个log文件里是不需要排序的，只是用来恢复数据用的。当memtable中的数据写入到磁盘后，对应的log文件也就可以删掉了。

这样的数据库设计其实跟LevelDB和RocksDB的实现原理是一样的，这些KV存储库被设计为嵌入到其他应用程序里工作。LevelDB可以用在Riak里作为存储引擎替换Bitcask，类似的存储引擎同样也被用在Cassandra和HBase里，他们都是受Google的Bigtable的论文启发而设计实现的，在Google的论文中首次提出了SSTable和memtable的概念。

这种索引结构是Patrick O'Neil首次以Log-Structured Merge-Tree的名字提出的，基于这种压缩合并有序文件的存储引擎经常被称作LSM存储引擎。

这里还是有很多细节需要考虑才能让这个设计应用到实际中，例如当要查的key在数据库中不存在的时候会非常慢，因为我们要检查memtable, 然后所有的segments，一一从磁盘中加载然后查找最后都查完发现这个key不存在。为了优化这个场景，数据库通常使用一个叫Bloom Filters的东西来帮助我们检查一个key是否在数据库中。在实际应用中也会有不同的策略来决定key的排序方式和压缩合并的时间，例如常用的选项有size-tiered和leveled，在size-tired下，新的和小的SSTTable会被合并到老的和大的SSTable中去。在Leveled压缩算法下，key的区间范围会被分成更小的SSTable，同时旧的数据会被转移到其他level，这样会让压缩是增量式的，减少磁盘使用。

B-Tree平衡树

LSM索引确实有它的优点，但是实际上应用最广泛的索引数据结构是B-Tree，几乎所有的关系型数据库和很多非关系型数据库都用这个实现。跟SSTable类似，B-tree也按照key的排序保存数据，这样可以提供高效的查找和区间查询，但是B-tree使用了完全不同的设计思想。

B-tree把数据拆分成固定大小的块或者分页，一般是4KB大小，一次只读写一个块或者分页，每个分页都有自己的地址，其他的分页都可以通过这个地址来引用并找到它，跟指针类似。这样用这些地址引用就可以构建一个包含多个分页的树。 B-tree index

在B-tree里查找一个key

在B-tree里有一个根节点，所有的查询都从这个节点开始，它里面包含了一些keys和child pages的引用，每个child page里包含一系列连续的key，多引用之间的key代表了某一段范围的key的开始和结束，通过那个引用可以找到这个范围内的任意一个key。

当要查询一个key的时候，从根节点开始，找到这个key所属的范围，然后通过这个范围内的引用找到下一个子分页，以此类推，最终找到下面包含这个key的分页中，可以读到它的值。

在一个分页里指向child page的引用的个数叫做分支因子，在上面那个图中，分支因子是6。分支因子取决于用来存储page引用的空间的大小和key起始范围的边界，一般都是几百。

写操作：

这个算法保证树一直是平衡的

由于B-tree在写操作时候需要先找到那个分页，更新后再写回去，对于某些写操作，例如上面的例子，当分页上空间不够的时候，需要拆分成两个，这里涉及到多个分页的多个写操作，当数据库crash的时候这种写操作就很危险，容易丢数据或者产生脏数据。为了解决这样的问题，常用的方式就是使用WAL(write-ahead log)或者叫做redo log。这个log是一个append-only的文件，所有的B-tree的写操作都要先写入这个文件，然后再去更新分页文件。如果数据库崩溃了，当重启之后，这个log会用来恢复数据到之前的状态。

另外在考虑并发控制的时候，经常用 latches (一个轻量级的锁)来保证数据更新中的race condition。

B树的一些优化的设计：

B-tree 和 LSM-tree的比较

一般来说LSM tree写操作更快，而B-tree读更快。

LSM tree的优点： B tree在写操作的时候要写两次，一次写WAL，一次写分页文件（也有可能或许更多，例如碰见需要分页的情况），另外，即使在一个分页上只有一点数据修改，B-tree也要写整个分页。 LSM tree也要写多次，由于不断的数据压缩和合并，这样的写一次导致接下来要再进行多次的写的过程叫做写放大。

参考文献：

  1. «Designing Data-Intensive Applications» 作者: Martin Kleppmann
  2. 文中的图也是从这本书中截取的

#database