在上一篇的笔记之中,我们讨论了数据模型和查询语言。在第三章之中我们来聊一聊不同的数据引擎内部是如何实现存储和检索的,以及不同设计之间的折中与妥协。
键值对数据库是数据库形式之中最简单的一种模式,我们可以把它简化的实现为下面两个函数:
通过两个Shell函数就可以实现简易的键值对数据库
底层存储格式也十分简单:一个文本文件,其中每行包含一个键值对,用逗号分隔(类似于CSV文件,忽略转义问题)。每一次调用 db_set 会追加键值对到文件的末尾,如果你更新的一个键值对的旧版本不会覆盖之前的键值对,但是 db_get会利用 tail -n 1 in 语句读取最新的键值对。但是真正的数据库需要处理更多的问题(例如并发控制、回收磁盘空间、使日志不能永久增长、处理错误和部分写的问题),但基本设计思路和原则是相同的。
但是,db_get 在性能上表现的很糟糕,每一次需要查找一个key,db_get 会扫描整个数据库文件来查找Key。在算法定义之中,查找的时间复杂度是O(n)。为了有效地查找数据库中某个特定键的值,我们需要一个不同的数据结构:索引。
索引是从原始数据派生出来的附加结构。在添加和删除索引时,不会影响数据存储的内容,它只会影响查询的性能。但是维护额外的结构会导致开销,尤其是写操作。任何类型的索引都会减慢写速度,因为每次写入数据时也需要更新索引。 在存储系统的有一个重要的权衡:精心挑选的索引加快了读取的速度,但是每个索引都会减慢写入速度。由于这个原因,数据库通常不会默认索引所有内容,但要求应用程序开发人员或数据库管理员手动地选择索引,可以选择使应用程序受益最大的索引,而不需要引入更多的开销。
内存哈希映射索引 每当向文件追加一个新的键值对时,也会同时更新哈希映射以反映刚才写入的数据的偏移量(这既可以用于插入新的键值对,也可以用于更新现有的键值对)。在查找值时,使用哈希映射查找数据文件中的偏移量,查找该位置并读取该值。 那么我们如何避免最终耗尽磁盘空间呢?一个好的解决方案是,我们可以对这些文件执行压缩,如下图所示。压缩意味着在文件中扔掉重复的键,并且只保留每个键的最新更新。
文件的压实操作.png 合并和压缩可以由后台线程完成,并且在进行合并和压缩操作时,我们仍然可以使用旧的文件继续正常地服务读写请求。在合并过程完成后,我们将读取请求转换为使用新合并的文件,然后旧的文件可以简单地删除。 缺点: (1)哈希索引严重依赖于内存,所以如果Key的数量庞大,需要匹配足够的内存空间。 (2)范围查询效率不高,每查找一个值都需要一次键值对映射。
使用归并排序合并SSTable
只需要保留部分键的索引
但是,如何让我们写入的键值对有序呢?这个问题在内存之中并不是什么难事,如红黑树或AVL树这些数据结构,可以按任何顺序插入键,并按排序顺序读取它们。所以我们在使用SSTable时,会维护一个MemTable的数据结构在内存之中,当MemTable达到阀值时,我们将MemTable作为一个新的SSTable序列化到磁盘之上。同时利用后台线程,不断压缩删除旧的SSTable,来维护一个可循环运行的存储系统。由于两次写入一次是在内存,一次磁盘写入是连续的(append日志),因此SSTable可以支持非常高的写入吞吐量。
许多数据库都是采用这样的思路来高效的处理数据,如Cassandra,HBase,LevelDB,Bitcask等。Lucene的全文搜索的使用Elasticsearch和Solr索引引擎,也采用了类似的方法来存储它的词典,当然,全文索引比键值索引复杂得多,但基于一个类似的想法:给定搜索查询中的一个词,查找提及该词的所有文档(Web页面、产品描述等)。这同样是一个键值结构实现的,其中键是一个词,而这个值是包含该词的所有文档的ID列表。
利用B树索引的存储结构 基本写的操作是覆盖旧数据的数据页,重写不会改变页的位置;即,当页被覆盖时,对该页的所有引用都保持不变。这与SSTable这样的哈希索引结构形成鲜明对比,它有附加操作,但从不修改文件。 而B树索引的并发控制相对复杂,当多个线程会对树进行访问时,需要通过用锁存器(轻量级锁)保护树的数据结构来完成。(这里也可以用Copy on Write来快照隔离)而哈希索引结构的压缩,合并则不会影响查询,写入等操作。
树型索引在数据库架构是非常根深蒂固的,对于很多的工作负载提供始终如一的良好性能。而以SSTable为代表的哈希索引也越来越受欢迎。确定哪种类型的存储引擎更适合应用场景,并没有一个简单易用的规则,因此需要我们对业务逻辑有更深层次的理解。