存储和检索

作为开发人员,我们需要选择合适自己应用的存储系统,为了做好性能调优,我们需要知道存储引擎底层做了啥。

数据库的数据结构

log

许多数据库使用 log 来记录写操作。

log 是一种 append-only 的数据文件。

如何避免 log 文件过大呢?
一种解决办法是:把日志切分成固定大小的小文件,并且对归档的 log 文件进行 压实(compaction)操作。

压实意味着将重复的操作归类并且只保留最近更新的部分。同时,也可以将不同的小文件进行压实操作从而合并成一个文件。

index

索引是一种从原始数据里派生出的附加的数据结构。

维护一份附加的数据结构通常会带来额外的性能开销,特别是在的时候。任何类型的索引都会拖慢写操作,因为每次写操作都需要更新索引。

在存储系统中,这是一种重要的权衡:

设计良好的索引会提升读操作的速度,但是会拖慢写操作的速度。
因此,数据库不会默认给所有数据建立索引,而是要求开发人员自己根据应用类型决定索引的建立。

哈希索引(Hash Indexes)

键值对数据索引非常常见,并且是很多复杂索引的基础。

键值对存储和许多语言中的字典类型很相似,都是使用 Hash 表实现的。

哈希索引也同样遵循 log 文件的存储方式,每个分片文件都有自己的哈希表在内存中维护,当想要找到某个值时:

  • 首先,查找最近的分片文件的哈希表,如果没有找到,则找上一个分片文件的哈希表,以此类推直到找到。由于有压实策略,分片文件不会太多,因此性能问题不大。

在现实世界中,有以下几点问题需要重点考虑:

  • 文件格式:
    二进制格式是理想的日志文件格式。

  • 删除记录:
    当删除一条记录时,需要向记录日志中添加一条特殊的删除记录,当压实开始时,合并操作会抛弃所以标记为删除的记录。

  • 崩溃恢复
    当数据库重启时,内存中的哈希表就丢失了。原则上,可以扫描所有的日志分片文件然后重新载入,但当文件数量比较大的时候会很慢。
    一种做法是:为每个分片日志文件的哈希表保持一份快照,当重启数据库时,直接从快照恢复数据。

  • 部分写记录
    数据库随时都有可能崩溃,包括在半途添加记录时。一种办法时:添加 checksums 机制,当这种情况发生时会被检查到并被忽略。

  • 并发控制
    由于日志文件是被以严格的序列顺序写入的,一种常见的做法是:只有一个写线程。数据文件是只能追加的或者不可变的,所以被多个线程读是安全的。

只可追加(append-only)模式初看起来有点浪费:为何不更新旧值?有几个原因:

  • 追加文件合并都是序列写操作,这种操作比随机写要快得多,特别是在旋转磁盘上。对于SSD闪存硬盘来说,也会更快。
  • 并发崩溃恢复会更简单。
  • 合并旧的片段文件可以规避数据文件随着时间的增长变得碎片化的问题。

然而,哈希索引也有下列限制

  • 哈希表的大小必须小于系统内存。当然在原则上,你可以在硬盘上也维护一个哈希表,但硬盘上的随机写操作性能非常低下,另外,当哈希表过大时,为了避免哈希碰撞的代价是非常昂贵的。

  • 范围查询将变得效率低下。

排序字符串表(SSTables)和 LSM-树

哈希索引的基础上,对做排序后再处理,就成了排序字符串表(SSTables)

相比上面的哈希索引,SSTables有如下优点:

  1. 使用类 合并排序 的思想,依次取每个小文件的最值到合并文件中,最后的合并文件就是按键排序(sorted-by-key)的文件。前提:总是合并相邻的小文件,所以当不同文件里有相同的 key 时,取最新文件中的值即可。
  2. 有序的作用在于:可以在内存中只保存少数键值对,由于所有的键值对都有序,很容易根据内存中的键值对在分片文件中找到想要的键值对。
  3. 由于读数据的请求需要扫描内存中的部分在查询范围内的键值对,因此可以将SSTables文件中的数据分块压缩成一块一块的条例,而在内存中维护的索引表的每一条都指向这些压缩块的头一条。

构建并维护 SSTables

可以看到,构建 SSTable 的第一步是将数据按键排序。

在内存中维护一种有序的数据结构非常容易,可以使用包括红黑树或者平衡树之类的树形结构。

所以构建存储引擎可以按照如下的步骤:

  • 当有写操作请求时,首先将其加入内存中的平衡树。(内存中的平衡树有时被称为内存表(memtable))
  • 当内存表的大小大过某个阈值(通常是几 MB)后,内存表会以 SSTable 文件的形式存入硬盘,这个新的文件就成了数据库最新的分片文件,与此同时,内存中又有了新的内存表。
  • 当有新的读操作时,首先查找内存表,然后是最新的硬盘上的分片文件,以此类推。
  • 同时,另起一个线程合并分片文件。

这种方式存在一个缺点:当数据库崩溃时,还没有写入磁盘的内存表的数据就彻底丢失了。为了解决这个问题,可以这样解决:

  • 单独在硬盘上维护一个只可追加日志文件
  • 每当有写操作时,往这个文件最后追加一条记录
  • 这个文件的数据是无序的,但是没关系,因为这个文件只是为了防止内存表中数据丢失而存在的
  • 一旦内存表被写入 SSTable 文件,这个文件就可以被丢弃了。

从 SSTable 衍生出 LSM-tree

使用上述合并压缩排序文件方法的存储引擎通常被称为 LSM(Log-Structured Merge-Tree) 存储引擎。

这种算法被用在了 LevelDBRocksDB 中。
相似的算法同样用在了 CassandraHBase 中,而这两个产品都受 Google Bigtable 论文的启发,另外,SSTablememtable 同样是出自 Bigtable 论文。

Lucene 也采用了相似的思路来存储 term dictionary。其中,key 是 term,value 是 包含 term 的文档 ID 列表(postings list)。

性能优化

LSM-Tree 算法的性能优化可以从以下几个方面着手:

  • 引入 布隆过滤器(Bloom Filter)。 当想要寻找的 Key 在数据库中不存在时,性能会很低下:因为数据库会尝试从 memtable 一直查询到最旧的 SStable 文件。一种解决办法是:引入布隆过滤器,在查询之前先询问是否有这个 Key。
  • 选择合适的合并压实策略。常见的策略有 size-tieredleveled 压实策略。

小小结

LSM-tree 是一种简洁但是非常高效的算法。即使数据集非常庞大,也能正常工作而且工作得很好。由于键是排好序的,范围查找也很高效。同时,由于分片文件都是序列写入硬盘的,LSM-tree 可以提供异常高的写入吞吐量。

(To be continued…)