实现键值对存储（三）：Kyoto Cabinet 和LevelDB的架构比较分析

浏览数：42 / 时间：2015年06月12日

在本文中，我将会逐组件地把Kyoto Cabinet 和 LevelDB的架构过一遍。目标和本系列第二部分讲的差不多，通过分析现有键值对存储的架构来思考我应该如何建立我自己键值对存储的架构。本文将包括：

1. 本架构分析的意图和方法
2. 键值对存储组件概览
3. Kyoto Cabinet 和LevelDB在结构和概念上的分析
3.1 用Doxygen建立代码地图
3.2 整体架构
3.3 接口
3.4 参数化
3.5 字符串
3.6 错误管理
3.7 内存管理
3.8 数据存储
4. 代码审查
4.1 声明和定义的组织
4.2 命名
4.3 代码重复
5. 参考文献

1. 本架构分析的意图和方法

我曾经想过是应该写两篇独立的文章，一篇写LevelDB另一篇写Kyoto Cabinet，还是应该写一篇综合的文章。我相信软件架构是一门很需要决策的技艺，就如同建筑师需要考虑并选择每个部分的设计一样。方案不能孤立的评估，而应该与其他方案之间进行权衡。软件系统架构的分析只能根据其背景在评价，并与其他架构比较。因此我将把键值对存储中遇到的主要组件过一遍，并比较现有键值对系统的方案。我将会为Kyoto Cabinet 和 LevelDB使用我自己的分析，但其他项目我会使用现有的分析。这里是我选用的其他人的分析：

- BerkeleyDB, Chapter 4 in The Architecture of Open Source Applications, by Margo Seltzer and Keith Bostic (Seltzer being one of the two original authors of BerkeleyDB) [1]
- Memcached for dummies, by Tinou Bao [2]
- Memcached Internals [3]
- MongoDB Architecture, by Ricky Ho [4]
- Couchbase Architecture, by Ricky Ho [5]
- The Architecture of SQLite [6]
- Redis Documentation [7]

2. 键值对存储组件概述

尽管键值对存储的内部架构有很大不同，但总有相似的组件。下面列出了大部分键值对存储中遇到的主要组件及其功能的简述。

接口：键值对存储暴露给用户的一组方法和类，使用户可以与之互动。也叫做API。键值对存储的最小API包括Get(),、Put() 和Delete()方法。

参数系统：选项设置并传递给整个系统的其他组件。

数据存储：接口是用来访问内存中数据（也就是键和值）的。如果数据必须维护在持久性存储器中，例如硬盘或闪存，那么可能会出现同步性问题和并发性问题。

数据结构：用算法和方法来组织数据，并允许高效的存储的检索。通常使用哈希表或者B+树。LevelDB中则是日志结构合并树。数据结构的选择基于数据的内部结构和底层数据存储方案。

内存管理：系统中用来管理内存的算法和技术。内存相当重要，如果数据存储用错误的内存管理技术来访问，会极大地影响性能。

遍历：对数据库中所有键和值进行枚举和顺序访问的方法。解决方案大多是迭代器和游标。

字符串：数据结构是用来访问字符串的。把字符串单独拿出来说或许看起来有些过分详细了，但对于键值对存储来说，大量的时间都用来传递和处理字符串，STL的std::string可能不是最佳方案。

锁管理：所有关系到并发访问（带有信号灯和互斥的）内存区锁的机制，以及当数据存储是文件系统时的文件锁。同时处理关于多线程的问题。

错误管理：用来拦截和处理系统中遇到的错误的技术。

日志：记录系统中发生的事件的机制。

事务管理：能够确保所有操作正常执行的一系列操作的机制，并且在出现错误时，确保没有操作被执行且数据库也没有更改。

压缩：用来压缩数据的算法

比较器：用来比较两个键是否相同的方法。

校验和：用了测试并确保数据的完整性。

快照：快照提供其创建时全部数据库的只读镜像。

分区：也被称为分片，其包括将整套数据分配到多个数据存储中，可能是网络中的多个节点。

数据备份：为了防止系统或者硬件错误，确保持久性，一些键值对存储允许数据（或者数据分区）有数个同时维护的拷贝，最好是在多个节点上。

测试框架：用来测试系统的框架，包括单元测试和整体测试。

3. Kyoto Cabinet和LevelDB结构和概念的分析

下述关于LevelDB和Kyoto Cabinet的分析将集中在下列组件：参数系统、数据存储、字符串和错误管理。关于接口、数据结构、内存管理、日志和测试框架这些组件将包含在IKVS系列之后的文章中。至于其他的组件，我目前不打算讲。其他系统，例如关系型数据库，有其他的诸如命令处理器、请求处理器、以及计划/优化器之类的组件，但它们已经超出了IKVS系列的内容。

在我开始分析之前，请注意我认为Kyoto Cabinet 和 LevelDB是很出色的软件部分，我也很尊敬它们的作者。即便我说了关于他们的设计的坏话，要记得的是他们的代码仍然很出色，而我并没有像他们那样的才华。这就是说，下边的文章是我对于Kyoto Cabinet 和 LevelDB代码的一点意见。

3.1 用Doxygen建立代码图

为了理解Kyoto Cabinet 和LevelDB的架构，我需要挖掘它们的代码。但是我也用Doxygen，一个用来浏览应用模块结构和类的非常强大的工具。 Doxygen是一个适用于多个编程语言的文档系统，它可以直接从源代码中创建报告文档或者HTML网站格式的文档。然而Doxygen同样可以用在没有注释的代码中，并创建基于系统组织方式（文件、命名空间、类和方法）的接口。

你可以从官网上获得Doxygen [8]。在你机器上安装好Doxygen之后，只需要打开shell界面，到包含所有你需要分析的源代码的目录下。然后输入如下命令即可创建默认设置文件。

$
 doxygen -g

这将创建一个叫“Doxygen”的文件。打开这个文件，确认下述所有设置都设置为“yes”:EXTRACT_ALL, EXTRACT_PRIVATE, RECURSIVE, HAVE_DOT, CALL_GRAPH, CALLER_GRAPH。这些选项会保证从代码中抽取所有对象，包括子目录，并创建调用图。所有可用设置的描述可以在Doxygen的在线文档中找到[9]。只需要输入下面的命令即可用已选好的设置来创建文档。

$
 doxygen Doxygen

文档将在“html”文件夹中创建，你可以用任何web浏览器打开“index.html”文件来访问文档。你可以浏览代码，查看类之间的继承关系，并通过图来查看每个方法由其它哪个方法调用。

3.2 整体架构

图3.1和3.1分别是Kyoto Cabinet v1.2.76 和LevelDB 1.7.0的架构。类以UML类图标准表示。组件以圆角矩形表示，黑箭头表示其它实体调用了这个实体。从A到B的黑箭头表示A使用或者访问了B的元素。

这些图示表示的功能架构和结构架构基本相同。以图3.1为例，很多组件出现在HashDB类内部，因其这些组件的代码被定义为HashDB类的一部分。

依据内部组件的组织方式来比较，LevelDB是大赢家。原因是Kyoto Cabinet中，遍历、参数设置、内存管理和错误管理的组件都作为内核/接口组件的一部分，如图3.1所示。这使得这些组件和内核之间形成了强耦合，并局限了系统的模块化和功能扩展性。与之相反，LevelDB是以一种非常模块化的方法建立的，只有内存管理才是内核组件的一部分。

图3.1

图3.2

3.3 接口

Kyoto Cabinet 的HashDB类暴露出来至少50个方法，与之相比的是LevelDB的DBImpl类只有15个方法（其中4个还是测试用的）。这是Kyoto Cabinet的Core/Interface组件强耦合的直接结果。

API设计将会在将来的IKVS系列中详细讨论。

3.4 参数设置

在Kyoto Cabine中，参数是通过调用HashDB类的方法来调节的。有15个以“tune_”开头的方法来完成这个工作。

在LevelDB中，参数被定义在特定的对象中。“Options”对象中是通用参数，“ReadOptions”和“WriteOptions”中是Get()和Put()分别需要的参数，如图3.2中所示。种子解耦提供了比较好的选项的扩展性，而不必像Kyoto Cabinet中调用Core中乱七八糟的公共接口。

3.5 字符串

在键值对存储中，随时都有大量的字符串处理。字符串被迭代、哈希、压缩、传递和返回。因此，巧妙的实现字符串类相当重要，每个对象节省一点，在大规模的运用上将会在全局造成引人注目的影响。

LevelDB使用一个特殊的类，称为“Slice” [10]。一个Slice包含一个字节数组以及数组的长度。这可以在O(1)的时间内获取字符串的长度，而不是std::string所需的O(n)而不是对C的字符串调用strlen()时所需的O(n)。独立保存字符串长度也可以允许保存字符‘’，这表示键和值可以是真正的字节数组而非由null终结的字符串。最后且最重要的是，Slice处理拷贝是通过创建一个浅拷贝，而非深拷贝。这表示它只简单地拷贝字节数组的指针，而不像std::string那样拷贝全部的字节数组。这避免了拷贝有可能出现的非常大的键或值。

像LevelDB一样，Redis使用他自己的数据结构来处理字符串。其目标同样是避免取字符串长度的时候避免使用O(n)操作[11]。

Kyoto Cabinet使用std::string作为字符串对象。

我的意见是，一个字符串类的实现适应于键值对存储的需求是非常必要的。如果能够避免，为什么要花费时间来拷贝字符串并分配内存呢？

3.6 错误管理

在我看过的键值对存储的所有C++源代码中，我没有见过一个将异常作为全局的错误管理系统使用。在Kyoto Cabinet中，kcthread.cc文件中的线程组件使用了异常，但我认为这个选择与其说是通用架构倒不如说是只是在处理线程而已。异常十分危险，并应该尽可能的避免。

BerkeleyDB有很好的C风格的方法来处理错误。错误信息和代码集中在一个文件中。所有返回错误代码的函数都有一个叫“ret”的整型本地变量，这个变量将会在处理过程中赋值并在最后返回。这种方法贯穿在所有的文件和模块中：相当优雅和标准化的错误管理。在一些函数中使用了向前跳转的goto语句——一种在如Linux内核那样的纯C系统中广泛使用的技巧[12]。虽然这种方法十分简洁和干净，但C风格的错误管理方法不太适合C++应用。

Kyoto Cabinet中，错误对象存储在每个诸如HashDB的数据库对象中。在数据库类中，各个方法在出现错误的时候调用set_error()来设置错误对象，然后以很符合C风格的返回true或者false。不会像BerkeleyDB那样在方法末尾返回本地变量，返回语句出现在错误出现的地方。

LevelDB完全不使用异常，而是使用一个叫做Status的类。这个类有错误值和错误信息。每个方法都返回这个对象，这样错误状态既可以就地处理也可以传递给调用栈中更高的其他方法。这个Status类错误码存储在字符串中，也是一种非常的聪明的实现。我对于这种设计方法的理解是，在大部分时间里，方法将会返回一个“OK”的状态（Status）对象，以表示没有出现任何错误。这样，错误信息字符串是NULL，而这个Status对象的处理是相当轻量的。如果Status对象增加一个属性来保存错误码，那么即便在“OK”状态的Status对象中仍需要给这个属性赋值，这即表示在每次调用方法的时候都要用更多的空间。所有的组件都使用这个Status类，并且没必要像Kyoto Cabinet那样总要调用一个方法，如图 3.1 and 3.2所示。

错误管理的所有方案都在上文中讲过了，我个人比较推荐LevelDB使用的方案。这个方案避免使用了异常，也不是一个我看来相当局限的单纯的C风格的错误管理，并且其避免了像Kyoto Cabinet那样与核心组件任何不必要的耦合。

3.7 内存管理

Kyoto Cabinet 和LevelDB都在内核组件中定义了内存管理。对于Kyoto Cabinet，内存管理一来可以跟踪数据库文件中临近的空块，二来当数据项保存的时候可以选择足够大小的块。而文件本身只是用mmap()函数映射出来的内存空间。另外MongoDB也使用内存映射文件[13]。

而LevelDB使用的是一个日志结构合并树，其不像保存在硬盘上的哈希表那样文件中有未使用的空间。内存空间管理也包括一旦日志文件大小超过某值后，压缩这些文件的功能[14]。

其它如Redis之类的键值对存储，用malloc()来分配内存——在Redis的例子中，内存分配算法不是操作系统提供的dlmalloc或者ptmalloc3，而是jemalloc[15] 。

3.8 数据存储

Kyoto Cabinet, LevelDB, BerkeleyDB, MongoDB 和Redis使用文件系统来存储数据。与之相反Memcached 则是在内存中保存数据。

4. 代码审查

本节是对Kyoto Cabinet 和LevelDB的一个简单的代码审查。这个代码审查并不全面，并只包含了我在阅读源代码时觉得比较出色的元素。

4.1 声明和定义的组织

如果代码都像LevelDB那样正常的组织，声明都在.h头文件中，而定义都在.cc文件中。但我在Kyoto Cabinet中发现了一些令人震惊的事情。实际上，很多类中.cc文件并没有包含任何定义，而方法都直接在.h文件中定义。在其他文件中，一些方法在.h中定义另一些在.cc文件中定义。虽然我理解这样做的背后可能有一些原因，但我仍认为在C++应用中不遵守这些惯例根本是错误的。之所以说是错的是因为一来它让我像那样惊讶，二来我必须在两种不同的文件中找定义。

4.2 命名

首先，Kyoto Cabinet相对于Tokyo Cabinet.有了显著的改进。整体架构和命名规则都大幅改进了。尽管如此，我仍然发现Kyoto Cabinet中的很多名字都很晦涩，譬如属性和方法叫做embcomp、trhard、fmtver()、fpow()。这让人觉得C++代码中混进了一些C代码。另一方面，LevelDB中的命名相当清晰，除了诸如mem、imm和in的一些临时变量。但这些不清晰的密码相当微量而代码可读性相当强。

4.3 代码重复

我在Kyoto Cabinet中确实看到了一些代码重复。这些用来文件碎片整理的代码至少重复了3次，而所有需要分为Unix和Windows两个版本的方法都显示出大量的重复。我没有在LevelDB看到明显的代码重复，我相信应该也有一些，但需要挖掘的更深才能找到。这证明LevelDB的代码重复问题确实比Kyoto Cabinet要小。