这个章节主要探讨两个主要的存储引擎

  • log-structured storage engine
  • page-oriented storage engine

最简单的存储系统⌗

db.sh

#!/bin/bash
db_set () {
    echo "$1,$2" >> database
}

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

加载这个脚本，就可以在命令行中使用这个简单的存储系统了。

source db.sh
db_set 1 "hello"
db_get 1
db_set 1 "world"
db_get 1

这个存储系统使用了log-structure。

  • set操作，直接追加到文件末尾
  • get操作，从文件中查找最后一个key对应的value

append写入很快，但是读取慢，因为每次读取都要扫描整个文件。

为了加速读取，我们需要构建索引。

索引从原始数据构建，只是为了加速查找。因此索引需要耗费额外的空间。每次插入都要更新索引，所以这是个以空间换时间，以降低写性能为代价换取更快读性能的策略。

这是数据库系统中常见的tradeoff，更多索引让读取更快，但是写入更慢。

哈希索引⌗

简单的内存哈希表⌗

为了加快查询，我们可以在内存中构建一个哈希索引

  • Key为需要查询的key
  • Value为key在文件中的偏移量和长度

这是Bitcast的设计思想。适用于小数据量的场景，即所有key都可以放在内存中。

  • 写入时，先写入哈希索引，再写入文件-append-only
  • 读取时，先从内存中的哈希索引中找到key的偏移量和长度，再从文件中读取

单个文件太大，磁盘空间不够怎么办？

将log拆分成固定大小的segement，单log到达指定大小后，就重新开启一个文件写入。

  • 我们可以对这些小文件进行压缩。压缩意味着抛弃日志中的重复的key，并对每个key都只保持最近的更新。
  • 由于压缩让segements小很多，我们可以合并多个segments。Segments在写入后就不再被修改，所以合并的segment要被写入到一个新文件。
  • 对这些只读文件的压缩和合并可以在后台线程中有进行，同时我们可以继续使用老的segment文件提供读写服务。
  • 在合并操作完成后，我们可以将读取请求转到新的合并后的segment文件，然后将老的segment文件删除。

每个segment文件都有一个自己的in-memory hash table，将key映射到segment文件中的偏移量和长度。

为了查找一个key,我们从最新的segment开始，然后逐个向前查找，直到找到key或者查找到最老的segment。

但是要在real world中使用这个系统，我们需要考虑很多问题：

  • 文件格式, CSV不适合作为log；可以使用二进制格式，编码的长度+raw string data
  • 删除记录, 如果想要删除一个key。但log structure不支持更新，怎么办？一般是用一个特殊标记来标记删除(tombstone)，然后在合并时删除这个key。
  • Crash recovery，重启时候可以扫描所有的segment文件，重建哈希索引。但也可以将每个segment的哈希索引保存到文件中，重启时直接加载这个文件。
  • Partially written records, 如果写入过程中crash，可能会导致部分记录写入，部分记录没有写入。可以在写入时，先写入一个特殊标记，然后写入数据，最后写入另一个特殊标记。在读取时，如果发现第一个特殊标记，说明这个记录是部分写入的，可以忽略。Bitcast使用checksum来检查数据是否完整。
  • 并发控制，只有一个可写文件，所以并发写是受控的。其他文件都是不可变的，所以可以并发读。

append-only log优缺点⌗

Pros

  • 以顺序写代替随机写
  • 简易的并发控制
  • 更少的内部碎片

Cons

  • 所有key都必须在内存中，如果key的数量超过内存容量，该方案就不再适用。但是如果使用基于磁盘的哈希表，会带来大量的随即写。
  • 不支持范围查询，因为key是无序的，范围查询要扫描所有索引。

SSTables和LSM-Tree⌗

我们在前面的设计的基础上做一点改变，让文件里的key有序。这种格式的文件叫做Sorted String Table(SSTable)。

SSTable相对于带有哈希索引的log-structure有很多优点：

  • 高效的数据文件合并。有序文件的归并外排。
    • key如果有重复，只保留最新的key。
  • 不需要在内存中保存所有key。可以使用二分查找。
    • 还是需要内存索引，但是只需要sparse index，即每隔一段距离保存一个key。之间的key在文件中二分查找。
  • 由于读请求都要扫描请求的一些key-value pair，可以将这些records当作一个block，并压缩后写入磁盘。sparse in-memory index的每个entry指向一个压缩的block的开头。除了节约了磁盘空间，压缩也减少了IO bandwidth use。

构建和维护SSTable⌗

怎么让你的key有序呢？

在磁盘上维护一个有序的结构是可能的，但是在内存中实现更容易些。有许多可用的数据结构，比如red-black trees or AVL trees。使用这些数据结构，你可以用任何顺序插入，但是读取的时候可以得到有序的key。

此时存储引擎的工作流程就变为了

  • 当写入时候，先写入内存中的balanced tree data structure。该内存树被称为memtable。
  • 当memtable大于某个threshold时候，将其写入到磁盘，作为一个SSTable文件。当SSTable正在被写入到磁盘时，新的写入会被写入到新的memtable。
  • 在读取时，先从memtable中查找，然后从最新的SSTable开始查找，直到找到key或者查找到最老的SSTable。
  • 后台持续合并SSTable，将多个SSTable合并成一个新的SSTable。(discard overwritten or deleted values)

该方案的问题是： 如果出现crash，memtable会丢失。 解决方案: 在写入memtable时，同时写入一个WAL(write-ahead log)。WAL是一个append-only的文件，记录了所有写入的key。在重启时，可以通过WAL重建memtable。 当该memtable写入到磁盘后，该WAL文件可以被删除。

LSM-Tree⌗

前面的算法也叫做LSM-Tree(Log-Structured Merge-Tree)。 LSM-Tree是一种基于SSTable的存储引擎。 LevelDB, RocksDB, Cassandra, Scylladb等数据库都使用了LSM-Tree。 Lucene，也使用类似 LSM-Tree 存储结构。(word → document list)。

性能优化⌗

优化SStable查找

  • 使用bloom filter，不存在的key直接拒绝。不用从memtable和SSTable中查找。 压缩优化
  • size-tiered compaction: 较小较新的SSTable被合并到较大较老的SSTable中。
    • 主要目标是减少存储空间的使用，从而优化读写性能
    • 主要在某些诶NoSQL数据库中使用，如Cassandra
  • leveled compaction: SSTables被分为多个level，每个level的数据大小有严格限制，除了最顶层(level 0)，每个层级中的SSTables都不会互相重叠。
    • 新数据会写入到memtable,当memtable满了，就转为不可变的SSTable并写入到磁盘的level 0。 level0的sstable达到threshold就会被合并到level1。 在level1到level n之间的层级，彼此之间的key range不会重叠。

最终LSM-Tree可以方便地进行范围查询，存储引擎从大量随机数据变为了顺序数据。

  • 所有数据都保存在磁盘上(memtable也有wal)，所以就算数据量大，也可以支持读写。
  • 所有磁盘写入都是sequential write，所以写入性能很高。(wal, sstable, compaction)

B-Trees⌗

几乎所有的关系型数据库都有使用B-Tree来实现索引。

和LSM-Tree一样，可以支持高效的key查询和range查询。但实现方式完全不同。特点为

  • 以page为单位进行组织(磁盘上叫做page, 内存中叫做block，通常大小为4kb)
  • page之间以Page ID进行逻辑引用，从而组织成一个磁盘上的树形结构。
  • 每个page都包含了多个key和对sub page的引用。
  • 所有的value都保存在叶子节点上。

查找

  • 从根节点开始，进行二分查找，然后加载page到内存，继续二分查找，直到找到叶子节点。
  • 查找的复杂度就是树的高度(O(logN))。
  • 影响树的高度的因素为: branching factor(每个节点的对sub page引用的数量)，现实中通常是好几百。 插入或更新
  • 查询到key所在的page，插入或者更新后，将page写入磁盘。如果插入新key后，page没有空间了，就将page拆分为两个page。 分裂或合并
  • 一条记录大于一个page怎么办？tree的node是逻辑概念，page或者block是物理概念。一个逻辑node可能会对应多个物理的page。

让B-tree更可靠⌗

B-tree的底层操作，就是用新的page覆盖磁盘上的旧page。而LSM-tree只是append数据，并不修改原有数据。

Tree的Node调整，可能会同时需要修改多个page。比如叶子节点分裂后，旧需要写入两个新的叶子节点，和一个父节点（需要更新指向叶子节点的指针）。这个过程并不是原子性的，如果出问题了怎么办呢？

  • 增加WAL，将所有修改操作记录下来。 如果多个线程要一起修改B-tree呢？
  • 可以使用轻量级锁(latch)来保护tree的结构。

B-tree的优化⌗

  • 使用Copy on Write技术，而不是WAL，同时也控制了并发。如LMDB, BoltDB。
  • 对中间节点的key做压缩，保留足够的路由信息就沟了。节省空间，增加了branching factor。
  • 为了优化范围查询，有的Btree叶子节点存储时物理连续。随着数据量的增长，维护的成本就会变得很大。但相比之下，LSM-tree可以一次性重写大量segments，更容易让连续的key在磁盘上彼此靠近。
  • 为叶子节点增加兄弟指针，而不需要跳回到paraent pages，然后再查询兄弟节点。

比较B-Trees和LSM-Trees⌗

经验法则是， LSM-Tree通常在写操作上更快，而B-Tree在读操作上被认为更快。

LSM树的优势⌗

B-Tree索引必须写入两次: WAL+page本身。即便少量数据修改，也是整个page override。

LSM的索引会因为多次合并和压缩SSTable而多次重写数据。这种一次写入数据库的数据，但在数据的生命周期内会造成多次磁盘写入的情况，称之为写放大(write amplification)。特别对SSD来说影响会比较大，因为它的override blocks的次数是有限的。

在write heavy的应用中，写放大可能会有性能问题，已经写入磁盘的数据越多，在可用的磁盘带宽内，每秒写入的能力越弱。写放大对B-Tree影响相对较大。

LSM-Tree都是顺序写，所以吞吐量较大，B-tree大量随机写。

LSM-Tree能更好地进行压缩，消除碎片。

在许多SSD中，firmware内部使用log-structured算法来将随机写入转为顺序写入，因此存储引擎带来的差别差距较小。然而，更小的写放大和更少的碎片在SSD上仍然是有用的。

LSM的劣势⌗

LSM存储的一个缺点是压缩过程可能会干扰正在进行的读写操作性能，因为磁盘资源有限，因此可能出现一个IO请求需要等待磁盘完成一次耗时的压缩操作的情况。而相对而言，B-Tree更具有可预测性。

磁盘有限的带宽，需要在memtable刷入磁盘和后台运行的压缩线程之间共享。数据量越大，压缩需要的带宽越多。如果写入吞吐量很大，可能出现压缩无法跟上写入速度的情况。此时，磁盘上为合并的segment数量会不断增加，直到耗尽磁盘空间，读操作也会变慢，因为需要检查更多的segment。需要工具来监控这种情况。

B-Tree的一个优势在于每个key在索引中只存在一个位置，而LSM存储引擎可能在不同的segment中有多个相同key的副本。在许多关系型数据库中，事务隔离是通过对key范围加锁来实现的，而在B-tree索引中，这些锁可以直接附加在tree上。

B-tree在数据库中被广泛使用，在新的数据存储中， LSM索引正变得越来越收到换因。需要实际测试的结果来决定哪种存储引擎更适合。

其他索引结构⌗

上面讨论的key-value索引，代表关系型数据库中的primary-key索引，或者document数据库中的一个文档，或者图形数据库中的一个顶点。

次级索引(Secondary index)可以在同一张表上创建多个。这些次级索引对于join的效率非常重要。

一个次级索引可以很容易地从一个key-value index创建。主要的不同是这些key不是唯一的，而上面探讨的内容key指向的value都是唯一的。这里有两种方式来解决：

  • 让索引的value是一个匹配行的list
  • 每个entry加上一个row number，那么这个value也就是唯一的，查询的时候返回第一找到的。

不论怎样，我们是可以使用B-Tree或者LSM-Tree作为次级索引

将value保存在索引中⌗

索引中的key是用来搜索的内容，而value可以有两种情况

  • 情况1, 它可以是实际的row(document, vertex等)。
  • 情况2, 它也可以是指向存储在其他地方的行的引用。

堆文件heap file⌗

在情况2中，存储数据行的地方称为堆文件(heap file)。

  • 数据本身是没有特定顺序的(可能仅仅是追加) 堆文件方法很常见，因为当存在多个二级索引的时候，它可以避免数据重复：每个索引只引用堆文件中的位置，而实际数据只保存一份。

堆文件在value的size变大，当前空间不够容纳的时候，需要将其移动到堆中有足够空间的新位置。在这种情况下，索引怎么办呢？

  • 方法1, 所有的索引都更新指向记录的新的堆位置
  • 方法2, 在旧的堆位置留下一个转发指针。

聚簇索引Clustered index⌗

在某些情况下，从索引到堆文件的额外跳跃可能会堆读操作带来性能损失，因此将索引的行数据直接存储在索引中可能是有好处的。这种被称为聚簇索引(clustered index)。例如

  • 在MySQL的InnoDB存储引擎中，表的主键是一个聚簇索引，而次级索引引用的是主键（而不是堆文件位置）。索引的叶子节点存储了数据。

clustered index的数据是按照索引字段有序排列的，邻近的数据都在一起。在InnoDB的B+树中，叶子节点还有指针指向相邻的page，那么在range query的时候，只要找到开始的数据，就可以通过链表找到所有需要的数据。 non-clustered index： 聚簇索引的数据在表中按照物理顺序存储。独立于这种物理顺序的索引都是非聚簇索引。叶子节点保存的是指向表中数据的引用（指针或者行ID）。

覆盖索引Covering index⌗

  • cluster和non-clustered index折衷的做法是covering index或者index with inclued columns。只把部分比较常被查询的信息保存在索引内，而不是所有数据都保存在索引内。

以Mysql为例，如果查询返回的字段，都是索引字段，那么直接查询覆盖索引就可以得到结果，而不需要返回clustered index查询完整记录的数据。如果返回结果有不存在于索引的字段，就需要回表查询。

多列索引 Multi-column index⌗

多列索引也被称为复合索引(composite index)或者连接索引(concatenated index)。

它通过将一个列的值追加到另一个列后面，将多个字段组成成一个key。但是查询的时候，只能使用前缀来查询。且如果有排序的需求，那么必须按照索引的顺序来查询。

比如，

如果有一个索引(key1, key2)，那么查询的时候，只能使用key1=xx或者key1=xx and key2=xx来查询，而不能只使用key2来查询。因为这个索引是按照key1来排序的。这个composite key的数据组成类似以下表格。

key1 key2
1 1
1 2
2 1
2 2

如有数据排序的需求，那么字段的排序需要和索引的排序一致。 比如mysql中

CREATE INDEX idx_name ON employees (last_name, first_name);

默认是按照升序排序的。如果需要降序排序，那么需要在查询的时候指定where last_name='a' order by first_name desc，此时会发生file sorting，数据库需要在内存或者磁盘上对结果集进行额外的排序。可以创建index的时候，指定sorting direction来避免file sorting。

CREATE INDEX idx_name ON employees (last_name, first_name desc);

多維索引 multi-dimensional index⌗

比如地理位置的经纬度查询

SELECT * FROM restaurants 
WHERE latitude > 51.4946 AND latitude < 51.5079 
	AND longitude > -0.1162 AND longitude < -0.1004;

B-Tree和LSM都无法高效查询，它们可以查询one dimensional range，但是无法同时查询two dimensional range。

  • 一种方式是将two dimensional range转化为one dimensional range，比如将经纬度转化为geohash，然后查询geohash的范围。
  • 另一种方式是使用R-Tree，它是一种多维索引，可以高效查询多维数据。

类似的应用场景

  • 如(R, G, B)作为多维索引，可以找相近颜色的图片。
  • 如(时间， 温度)，查找某个时间段内的温度在一定范围内的数据。

全文索引和模糊索引 Full-text search and fuzzy indexes⌗

类似Trie树，可以用来做全文搜索，或者模糊搜索。

在内存中保存一切⌗

内存成本下降后，这类数据库变得越来越流行。内存中的数据结构可以更加复杂，更加高效。

根据是否支持持久化，可以分为两类

  • 不需要持久化，如Memcached
  • 需要持久化，通过WAL, 定期snapshot， 远程备份等对数据进行持久化。但使用内存处理全部读写，如Redis。

VoltDB, MemSQL, and Oracle TimesTen 是提供关系模型的内存数据库。RAMCloud 是提供持久化保证的 KV 数据库。Redis and Couchbase 仅提供弱持久化保证。

内存数据库的优势

  • 不需要读取磁盘
  • 不需要对数据结构进行徐丽华，编码以适应磁盘带来的开销
  • 提供更丰富的数据结构，如set, list, hash, sorted set等
  • 实现相对简单

OLTP和OLAP⌗

OLTP OLAP
主要读取模式 少量记录，按key查询 大量记录，聚合（max,min,sum, avg）查询
主要写入模式 随机访问，低延迟写入 批量写入，流式写入
主要应用场景 web方式使用的最终用户 分析，报表，数据挖掘
如何看待数据 关注当前时间点的最新数据 关注历史数据
数据量 通常GB到TB 通常TB到PB

Data Warehousing⌗

对交易型的系统来说，为了避免对在线系统的影响。OLAP的数据通常是从OLTP系统中复制过来的。这个过程叫做ETL(extract, transform, load)。

AP场景下的聚合查询分析和传统TP是不同的，所以一般使用不同的数据模型并构建不同的索引。

星型和雪花模型⌗

分析型数据库通常使用星型模型(star schema)或者雪花模型(snowflake schema)。

星型模型，中心会有个事实表fact_table，通过外键关联到多个维度表dimension_table。维度表通常是一些描述性的信息，如时间，地点，产品等。

如果将维度表进一步规范化，就是雪花模型。比如将维度表中的某个字段拆分成多个表。

列存储⌗

纬度表通常是小表，而事实表通常是大表(可能PB)。

大多数情况下，OLAP查询只需要查询事实表的某几列，而不是整个行。这种情况下，列存储比行存储更加高效。

列压缩⌗

将所有数据分列存储在一块，带来了一个意外的好处，由于同一属性的数据相似度高，因此更易压缩。

如果每个列的cardinality数量都比行数要少得多，就可以使用位图编码(bitmap encoding)来压缩列。

列族 Column family⌗

  • 同一个列族的列通常会被一起查询，所以可以将这些列存储在一起，内嵌一个row key。
  • HBase, Cassandra, Bigtable等数据库都使用了列族的概念。

列式存储的排序⌗

可以如 LSM-Tree 一样，对所有行按某一列进行排序后存储。

列式存储的写入⌗

列式存储的写入通常是append-only的，因为列式存储通常是读多写少的，而且都是读取超大规模的数据。

使用LSM-Tree的追加方式

  • 将新写入的数据在内存中处理好，然后追加到磁盘上，并与已有的数据合并。

TODO⌗

  • add diagram