数据存储--日志存储类型与哈希索引

所谓数据库，它的核心功能无非是存、取数据两种操作。所以，我们可以简单大实现以下两种方法，来实现一个最简单大数据库：

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

上面两个方法定义了一个最简单的key-value类型的数据库。下面是使用样例：

$ 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"]}

这两个方法所操作的文件叫database，它本身内容都是按逗号分割的键值对（可以粗略看作是CSV格式）。它本身的update操作不是去修改原有键的值，而是直接在现有文件后追加一条新的记录，所以获取值的时候应该以最后一个目标键对应的值为准。

$ 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"]}

类似上面的只追加的记录文件叫做日志(log)。它广泛应用于实际数据库当中。追加写入操作的代价很小，速度很快，这也是日志被广泛应用的原因之一。
在上面例子当中，随着数据量的增加，db_get方法速度会越来越慢。它是从前到后扫描整个文件，所以它的时间复杂度是O(n)。
为了加快查找操作的速度，我们需要引入索引(index)的概念。它的主要思想是用其它形式来存储额外的元数据，来帮助加速定位目标数据的确切位置。增删索引对于原始数据本身没有任何影响，它影响的只是查询操作的速度，然而由于索引是原始数据之外的部分，需要在每次写入操作的时候进行更新维护，所以，索引应该按需来建。

哈希索引(Hash Indexes)

大多数语言都有内建叫做字典(dictionary)的数据结构。这种数据结构内部往往使用哈希来实现。类似的，对于键值对(key-value)数据库，也可以采用哈希索引的思想。对于上面只有两个方法的那个简单的键值对数据库实现，可以使用哈希索引:

哈希索引
在内存中维护一个哈希表，记录某一确定key所对应记录的缩进值，每当发生写入（包括insert和update）操作时，更新这个哈希表。这种做法也是Riak的内部数据引擎Bitcask的行为。这种做法适合用于更新操作频繁而键不多（方便将键放在内存中）发生的场景。
随着数据量的增加，日志文件也会进一步增大，我们需要定时做压缩操作来去除重复键占用的空间（由更新操作造成）。
压缩操作
推广来说，我们可以对多个文件采取压缩合并操作，来生成新的数据文件（压缩合并操作一般由子进程完成，以免阻塞主进程的读写操作）。
压缩合并操作
当查找指定键时，我们按生成时间倒序来依次去不同文件的哈希表中寻找键（由于压缩合并操作，哈希表的数量不会太多）。
实际工程(Bitcask的行为)中还有以下几点问题：

• 文件格式：一般采用专门优化过的二进制格式
• 删除操作：追加一条删除操作记录，压缩合并操作时直接摒弃删除操作指定键
• 故障恢复：可以使用快照（snapshot）的概念，来降低哈希表恢复的成本
• 部分写入：当数据写入过程中发生故障，可以采用校验和(checksum)来保证数据完整无误
• 并发控制：使用单一写入线程来处理所有写入请求

使用只追加的设计而非直接更新原始数据有以下几个优点：

• 追加写入操作成本要比随机写入低很多
• 故障恢复风险小，最多只会有不完整的数据，而不会有新旧数据混杂的情况
• 定期的压缩合并操作减少了磁盘碎片的产生

哈希索引也存在诸多限制：

• 各个文件的哈希表存放在内存中，某种程度上限制了键的上限数量
• 哈希索引针对精准查询的时间复杂度是O(1)，但对于区间查询(range query)的时间复杂度却是O(n)