存储引擎层是键值数据的核心单元。数据存储在存储引擎中，并采用索引结构提升存储引擎中数据的存取性能。存储引擎对上层提供Put、Get、Del和Range函数接口，这些接口分别负责往该存储引擎内部插入/修改键值对、查询键值对，删除键值对和范围查询键值对。
一般来说，存储引擎主要分为4个模块：索引模块、存储模块、持久化模块和空间分配/垃圾回收模块。其中，存储模块负责键值对的物理存储，索引模块负责对每个键值对的快速定位，持久化模块负责对存储模块的持久化和可恢复性的保证，空间分配/垃圾回收模块负责空间的申请、分配及当空间使用率过高时的垃圾回收任务。对于部分有特殊需求的键值数据库，可能还会有额外的模块，如加解密模块和压缩模块等。
根据采用的索引和存储结构的不同，典型的存储引擎可以分为三大类。
1）基于哈希表的存储引擎。
2）基于B+树的存储引擎。
3）基于LSM-tree的存储引擎。
基于哈希表的存储引擎
哈希表是一种无序的数据结构，它提供了快速的插入操作和查找操作。一个好的哈希表能够保证插入和查找的时间复杂度为 O （1），即插入和查询性能与哈希表中的数据量无关。基于哈希表的键值存储引擎将键值对存储在持久性的日志文件中，然后构建一个内存哈希表用于索引日志中的键值对。常见的基于哈希表的键值存储引擎有Riak公司的BitCasker，微软的FASTER、Memcached和Redis。总体来说，这种设计可以实现高效的写性能和查询性能，但是它牺牲了范围查询性能。
在基于哈希表的键值存储引擎中，哈希表的重要性不言而喻。哈希表索引由哈希函数和多个哈希桶结构组成，其中哈希函数将哈希键映射到一个整数域[0， B -1]， B 为哈希桶的数量。图4-3所示为一个简单的哈希表结构。该哈希表结构由4个桶组成，每个桶中可以容纳2个键值对，哈希表存储了a～f6个键值对。在该结构中，部分键值对会被映射到同一个桶中。如果有超过2个键值对映射到同一个桶中，则发生哈希冲突，此时需要设计一定的冲突处理机制来维持哈希索引结构的正确性。
图4-3 一个简单的哈希表结构
哈希表结构设计中最关键的问题就是：①如何选择合适的哈希函数；②如何选择合适的哈希冲突处理机制。比较常见的哈希函数有MurMurHash、CityHash、FarmHash等。其基本运算逻辑是将哈希键按固定长度进行切分，然后每个分片进行相应的位运算，并且按照一定的串联规则将不同分片的结果最终体现在哈希结果中。
图4-4给出了常见的哈希函数的性能测试结果。图中的 x 轴表示哈希键的长度， y 轴表示哈希函数计算的吞吐率（perations per second，ops）。在实际使用，可以根据负载的哈希键的长度特点选择合适的哈希函数。
图4-4 几种常见哈希函数的吞吐性能
常见的哈希冲突解决机制有四种。
1）链地址法。在链地址法下，哈希表的每个桶由一个链表构成。链表中存储的是所有哈希值相同的键值对。因此在进行查询操作时，可以通过遍历该链表查询对应的键值对。
2）线性探测法。在线性探测法下，哈希表是一个连续的桶数组，对于任意一个哈希键，根据哈希函数定位到一个映射位置，插入和查找都基于该地址进行向后探测。当插入一个键值时，判断映射地址是否为空，如果该地址为空，则在映射地址插入键值对，否则向后探测直到找到空桶，并将该键值对放入该空桶。查询操作则从映射地址开始向后扫描所有键值对，直到找到待查询键值对或者遇到一个空桶。
3）双选择法。双选择法采用两个独立的哈希函数，对于每个键值对，都有两个可插入的桶。当执行插入的时候，根据两个哈希函数分别将哈希键映射到两个桶a和b中。根据桶a和桶b的填充度，选择填充度更低的桶插入键值对。同样，执行查询操作时，只需要遍历两个桶即可定位到查询键值。
4）布谷鸟探测法。布谷鸟探测法是双选择法的一种变种。它同样采用两个哈希函数。当执行键值对插入时，根据两个哈希函数分别将哈希键映射到两个桶a和b中。如果桶a和b存在空闲位置，则将键值对插入到空闲位置中；否则，随机挑选一个桶中的键值对，将其踢出该桶，并存入待插入键值对，被踢出的键值对则尝试插入到其对应的另一个桶中。
采用不同哈希冲突解决方式，在查询性能、插入性能、哈希表填充度三个维度会有不同的表现，没有一个十全十美的哈希冲突解决方案。链地址法的插入性能更优，并且对于空间的占用是逐渐增长的；线性探测法的填充度可以做到最优，但是这是以牺牲查询和插入性能为前提的；在查询性能上，布谷鸟和双选择法会比其他方法更优。在实际的键值数据库中，不同的设计会采用不同的哈希函数和哈希冲突解决机制。Redis采用的就是链地址法，这使得Redis的空间占用更为缓慢，空间管理也更为灵活。
