读书笔记 -《数据密集型应用系统设计》- 索引

随着数据的不断增加，读数据的性能势必会成为一个不可忽视的问题。为了加快数据的读性能，因而出现了索引一词，用最通常的话解释，索引有点像一本书的书签。但是随着数据量的与日俱增，索引本身也可能成为一个大数据从而再次引发性能问题。智慧的人类总是在不停的思索去解决问题，接下来我们就一起来看看常见的索引以及他们能解决的问题。

1、Hash 索引

键值对的数据结构[key,value],最长见的如 HashMap。

假设我们现在设计一个这样的存储系统：

此系统读写过程：

1. 用户 insert 数据 [张三，的法大师傅当时公司]

2. 数据库系统在磁盘上以追加读的方式创建一个 File

3. 数据库系统将 '的法大师傅当时公司' 这个数据写入创建的 File 并返回文件偏移量

4. 数据库系统刷新内存数据[可以是一个 HashTable]，put('张三'，文件偏移量<begin,length>)

5. 用户读取数据时传入 key=张三，数据系统获取对应的文件偏移量，然后读取文件数据返回给用户

以上系统的优缺点：

优点：

• 基于内存的 key 寻址会非常快，hash(key)的时间复杂度为 1.

• 只需要一次磁盘寻址，快速的将数据加载到内存

• 可以利用文件系统的缓存无需 IO 开销

缺点：

• 我们采用的是追加读模式，可能存在磁盘用尽

• 随着 key 的增加，内存容量也会成为一个瓶颈

• 机器宕机重启内存数据丢失

• 并发写入时的问题，因为我们是以追加写的方式将数据存储到磁盘，无法评估每个线程写入的数据量。

• 数据的删除：还是由于数据在磁盘是以追加写的模式存储我们无法直接删除文件中的数据段

解决缺点的方法呢？

1. 类似于 Kafka 中文件分段的模式，将文件切成一小段一小段的，在合适的时机进行合并、压缩等方案。

2. 同样的方法，可以定时对内存做快照，生成备份文件存储到磁盘，以实现机器重启时的恢复，这点可以很好的参考 Redis 的设计[哪些 key 是热点数据，备份可以是后台线程定时执行等等]

3. 对于数据删除，可以在用户提交删除申请的时候记录下来，在文件执行合并、压缩操作时在执行删除操作

4. 如何实现区间查询？

类似于这种思想实现的典型 key-value 存储系统：获得PCC性能大赛背后的RocksDB引擎:5分钟全面了解其原理 (sohu.com)

2、更优优秀的 SSTables 和 LSM-Tree

SSTables：排序字符串表

相比于 Hash 索引，具有如下优点：

1. 合并段更加简单高效。并发读取待合并的段，找到键值最小的段拷贝到输出文件[需要提供键的排序器]，如此往复，最终实现段按照键的顺序进行合并

2. 依赖于键值的排序特性，我们可以不完全依赖于精确的 key 值查找。例如 key1 < key? < key2，我们可以借助于 key1 和 key2 的偏移量找到 key?对应的值

3. 由于在 SSTable 中实现了按照键的顺序进行段的合并，因为可以支持 HashTable 中无法实现的区间查询。

4. 依赖于 key 的有序性而实现的内存中可以稀疏存储索引的方案。

2.1 如何构建 SSTables

• 写入时，先写入内存。借助于红黑树等结构，可以实现内存中这个表的有序性。我们暂且叫做 memtable,在写入内存的同时也会以追加写的方式写入到一个 redo log 文件里面以做恢复重启时使用

• 随着写入的增加，memtable 的大小也会到达一个阈值，此时会将 memtable spil 到 disk 里面[我们称之为一个 SSTable]，同时可以删除对应的 redo log 文件

• 在写入的同时也会接收读请求，首先在 memtable 中查询，如果没有则在最新生成的 SSTable 中查找。

• 后台进程会周期性的执行 SSTable 合并，并丢弃那些被覆盖或者删除的数据[这里有一个疑问，就是被 spill 到 disk 的 SSTabel 只是局部有序性，那么在后台线程合并的过程中是不是需要在做一次全局排序然后合并]

• 系统崩溃时的数据恢复：前面提到 redolog，系统通过重放 redolog 文件实现数据恢复