哈希索引设计发展史

从最基本层面看，数据库只需做两件事：

• 向它插入数据肘，它就保存数据
• 之后查询时，返回那些数据

本文讨论如何存储输入的数据，并在收到查询请求时，如何重新找到数据。

为何关注数据库内部的存储和检索呢？你不可能从头开始实现存储引擎，往往需要从众多现有的存储引擎中选择适合业务的存储引擎。 为针对特定工作负载而对数据库调优时，就得对存储引擎底层机制有所了解。

针对事务型工作负载、分析型负载的存储引擎优化存在很大差异。

事务处理与分析处理”和“面向列的存储”部分，分析型优化的存储引擎。

先讨论存储引擎，用于大家比较熟悉的两种数据库，传统关系数据库和NoSQL数据库。研究两个存储引擎家族 ，即日志结构的存储引擎和面向页的存储引擎，比如B-tree。

数据库核心：数据结构

最简单的数据库，由两个Bash函数实现：

登录后复制

      
      

       
       #!/bin/bash
       
       

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

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

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
      
      

这两个函数实现一个K.V存储。当调用 db_set key value，它将在数据保存你所输入的key value key value几乎可以是任何内容。例如值可以是JSON文档。然后调用db_get key，它会查找与输入key相关联的最新值并返回。

例如：

登录后复制

      
      

       
       $ db_set 123456 '{"name":"London", "attractions":["Big Ben","London Eye"]}'
       
       

       
       
$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'
       
       

       
       
$ db_get 42 {"name":"San Francisco", "attractions":["Golden Gate Bridge"]}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
      
      

它底层的存储格式其实非常简单：一个纯文本文件。其中每行包含一个K.V，用逗号分隔（大致像一个csv文件，忽略转义问题）。每次调用db_set，即追加新内容到文件末尾，因此，若多次更新某K，旧版本值不会被覆盖，而需查看文件中最后一次出现的K来找到最新V（因此在db_get中使用tail -n 1）。

登录后复制

      
      

       
       $ db_set 42 '{"name":"San Francisco", "attractions":["Exploratorium"]}'
       
       

       
       
$ db_get 42 {"name":"San Francisco", "attractions":["Exploratorium"]}
       
       

       
       
$ cat database
       
       
123456,{"name":"London","attractions":["Big Ben","London Eye"]} 42, {"name":"San Francisco","attractions":["Golden Gate Bridge"]}
       
       
42,{"name":"San Francisco","attractions":["Exploratorium"]}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
      
      

简单情况，追加到文件尾部方式通常够高效了，因而db_set函数性能很好。类似db_set，许多数据库内部都使用日志（log），日志是个仅支持追加式更新的数据文件。虽然真正的数据库有很多更复杂问题要考虑（如并发控制、回收磁盘空间以控制日志文件大小、处理错误和部分完成写记录等），但基本原理相同 。

日志这个词通常指应用程序的运行输出日志，来记录发生了什么事情 。日志则是个更通用的含义，表示一个仅能追加的记录序列集合。它可能是人类不可读的，可能是二进制格式而只能被其他程序来读取。

另一方面，若日志文件保存大量记录，则db_get性能会很差。每次想查找一个K，db_get 必须从头到尾扫描整个数据库文件来查找K的出现位置。在算法术语中，查找开销是O（n） ，即若数据库记录条数加倍，则查找需要两倍时间。这一点并不好。

为高效查找数据库中特定K的V，需要数据结构：索引。它们背后基本想法都是保留一些额外元数据，这些元数据作为路标，帮助定位想要数据。若希望用几种不同方式搜索相同数据，在数据的不同部分，可能要定义多种不同的索引。

索引是基于原始数据派生而来的额外数据结构。很多数据库允许单独添加、删除索引，而不影响数据库内容，它只会影响查询性能。维护额外结构势必会引入开销，特别是在新数据写入时。对于写人，它很难超过简单追加文件方式的性能，因为那已经是最简单的写操作。由于每次写数据时，需更新索引，所以任何类型索引基本都会降低写速度。

这就是

存储系统中重要的trade off

合适的索引能加速查询，但每个索引都会降低写速度。默认情况下，数据库通常不会对所有内容索引 ，它需要SE或DBA基于对应用程序典型查询模式的了解，手动决定索引。就是为应用提供最有利加速同时，避免引入过多不必要的开销。

哈希索引

以KV数据的索引开始。KV类型并非唯一能索引的数据，但随处可见，而且是其他更复杂索引的基础。

KV存储与大多数编程语言所内置的字典结构类似，一般采用hash map或hash table实现。既然已有内存数据结构的hash map ，为何不用它们在磁盘上直接索引数据？

假设数据存储全部采用追加式文件组成，最简单的索引策略：保存内存中的hash map，将每个K一一映射到数据文件中特定的字节偏移量，这就能找到每个值的位置：

每当在文件中追加新的KV对时，还要更新hashma来反映刚写入的数据的偏移量（包括插入新K与更新已有K）。当查找一个值时，使用hashmap找到文件中的偏移量，即存储位置，然后读取其内容。

听着简单，但的确可行。Bitcask（Riak默认的存储引擎）就是这么做的。 Bitcask提供高性能读写，但所有K必须能放入内存。而V则可以使用比可用内存更多的空间，只需一次磁盘寻址，就能将V从磁盘加载到内存，若那部分数据文件已在文件系统的缓存中，则读取根本不需要任何磁盘I/O。

Bitcask这种存储引擎适合每个K的V经常更新场景。如：

• K，视频的URL
• V，播放次数（每次有人点击播放按钮时递增）

在这种工作负载下，有大量写操作，但没有太多不同的K，即每个K都有大量写操作，但将所有K保存在内存中还是可行的。

至此，只追加写到一个文件，那如何避免最终用完磁盘空间？可将日志分为特定大小的段，当日志文件达到一定大小时就关闭，并开始写到一个新的段文件中。然后，就能压缩这些段：

压缩意味着在日志中丢弃重复K，只保留每个K的最近更新。

由于压缩经常会使段更小（假设K在一个段内被平均重写多次），也能在执行压缩时将个段合并：

由于段在写入后不会再被修改，所以合并的段会被写入一个新文件。对这些冻结段的合并和压缩过程可在后台线程完成，而在运行时，仍能继续使用旧的段文件继续正常的读写请求。合并过程完成后，将读请求切换到新的合并段上，旧的段文件就能安全删除了。

每个段现在都有自己的内存哈希表，将K映射到文件的偏移量。为找到键的值，先检查最新的段的 hashmap；若K不存在，则检查第二最新的段，依此类推。因为合并过程可维持较少的段数量，因此查找一般无需检查太多hashmap。

实现难点

文件格式

CSV不是日志最佳格式，二进制格式更快，更简单。首先以字节为单位，记录字符串的长度，然后跟上原始的字符串（无需转义）。

删除记录

若要删除一个K及其V，则必须在数据文件中中追加一个特殊的删除记录（有时称为逻辑删除）。合并日志段时，一旦发现逻辑删除标记，就会丢弃这个已删除键的所有值。

崩溃恢复

若数据库重启，则内存的hashmap将丢失。原则上，可通过从头到尾读取整个段文件，记录每个键的最新值的偏移量，来恢复每个段的hashmap。但若段文件很大，这可能耗时久，这将使服务器重启很慢。 Bitcask通过存储加速恢复磁盘上每个段的哈希映射的快照，可以更快地加载到内存中。

部分写入记录

数据库可能随时崩溃，包括将记录追加到日志的过程中。 Bitcask文件包含校验值，这样就能发现损坏部分并丢弃。

并发控制

由于写是以严格的先后顺序追加到日志，所以常见实现是只有一个写线程。数据文件段是追加的且不可变，所以它们能被多线程同时读取。

追加的日志看起来很浪费：为何不更新文件，用新值覆盖旧值？

追加写设计的优势

• 追加和分段合并是顺序写，一般比随机写快得多，尤其是在旋转式磁盘。某种程度上，顺序写在基于闪存的固态硬盘（SSD） 也很合适
• 若段文件是追加的或不可变的，则并发和崩溃恢复就简单得多。如不必担心在重写值时发生崩溃的情况，导致留下一个包含部分旧值和部分新值混杂的文件
• 合并旧段能避免数据文件随时间推移，数据文件出现碎片化问题

哈希索引的劣势

• 散列表必须能放进内存
  若你有很多键，那真是倒霉。原则上，可在磁盘上维护一个hashmap，但磁盘上的hashmap很难表现优秀，需大量随机访问I/O，当hash变满时，继续增长代价昂贵，并且哈希冲突需要复杂处理逻辑
• 范围查询效率不高
  如无法轻松扫描kitty00000到kitty99999之间的所有K，只能采用逐个查找的方式查询每 个K