[转]实现键值对存储（长文）

ゝ一世哀愁。 2022-08-22 12:26 291阅读 0赞

# 实现键值对存储（0）：目录 #

本文由  [伯乐在线][Link 1] -  [熊铎][Link 2] 翻译。未经许可，禁止转载！  
英文出处： [Emmanuel Goossaert (CodeCapsule.com)][Emmanuel Goossaert _CodeCapsule.com]。欢迎加入 [翻译组][Link 3]。

2014年7月8日更新：这个系列的文章仍在继续，我正在实现这个键值对存储并将在其差不多完成的时候写一篇文章。这些文章每一篇都花了我很长时间来写。为了在完成的时候获得更新通知，你可以在博客右上角订阅。

这篇文章是我今天开始的系列文章“实现一个键值对存储”（IKVS）的主条目。本文旨在以内容列表的形式总结系列中所有文章，可能在晚些时候有一些关于项目的笔记。

本文的内容可能随时间变化直到系列完成。特别是在目录里，各个部分的标题还没有写而顺序也有可能改变。随着内容逐渐完成，一些部分也有可能被移除或者有新的部分被添加进来。

项目中的更多信息可以在 “第一部分：什么是键值对存储，为什么要实现它”的1.3节中找到。

[1 – ][1][什么是键值对存储，为什么要实现它？][Link 4] （已翻成中文）

*  1.1 – 键值对存储综述
 *  1.2 –键值对存储 vs 关系型数据库
 *  1.3 – 为什么要实现键值对存储
 *  1.4 – 计划
 *  1.5 – 参考文献

[2 – 使用已存在的键值对存储作为模型][2 _] （已翻成中文）

*  2.1 – 不要重复发明轮子
 *  2.2 – 候选模型和选择标准
 *  2.3 – 所选的键值对存储的概览
 *  2.4 – 参考文献

[3 – Kyoto Cabinet和LevelDB结构的比较分析][3 _ Kyoto Cabinet_LevelDB]

*  3.1 – 结构分析的意图和方法
 *  3.2 – 键值对存储组件的概览
 *  3.3 – Kyoto Cabinet和LevelDB的结构与概念分析
 *  3.4 – 代码审查
 *  3.5 – 参考文献

[4 – API设计][4 _ API]

*  4.1 – API设计的基本原则
 *  4.2 – 定义FelixDB公共API的功能。
 *  4.3 – 比较已存在数据库的API功能
 *  4.4 – 结论
 *  4.5 – 参考文献

[5 – 哈希表实现][5 _]

*  5.1 – Hash tables 哈希表
 *  5.2 – Implementations 实现
 *  5.3 – Conclusion 结论
 *  5.4 – References 引用

6 – 实现存储在文件系统中的高存储效率的哈希表

7 – 存储管理

8 – 网络

9 – 接口：REST, memcached等

10 – 更进一步

# 实现键值对存储（一）：什么是键值对存储，为什么要实现它 #

在本文中，我将会以键值对是什么的一个简短描述开始。然后我将解释本项目之后的一些理由，最后我将说明我打算实现的键值对存储的主要目标。这里是本文中将会包含内容的列表：

1.  键值对存储的概述
2.  键值对存储 vs 关系型数据库
3.  为什么要实现键值对存储
4.  计划
5.  参考文献

# 1. 键值对存储的概述 #

基于很多文章已经有了很多详细的介绍，本节只是对于键值对存储的一个简短介绍。我已经选择了几篇放在本文底部的引用一节中。

键值对存储是数据库最简单的组织形式。基本上所有的编程语言都带有应用在内存中的键值对存储。C++STL的映射容器（map container）和Java的HashMap以及Python的字典类型都是键值对存储。键值对存储通常都有如下接口：

Get( key ): 获取之前存储于某标示符“key”之下的一些数据，或者“key”下没有数据时报错。

Set( key, value ): 将“value”存储到存储空间中某标示符“key”下，使得我们可以通过调用相同的“key”来访问它。如果“key”下已经有了一些数据，旧的数据将被替换。

Delete( key ):  删除存储在“key”下的数据。

大部分低层实现都是使用哈希表或者某种自平衡树（例如B-树或者红黑树）。有时候数据太大而不装不进内存，或者必须维持数据谨防系统因为未知原因而崩溃。在这些情况下，就必须使用到文件系统。

键值对存储是NoSQL运动的一部分，NoSQL将所有不使用基于关系型数据库概念的数据库系统组合在一起。[维基百科上的NoSQL词条][NoSQL]很好的总结了这些数据库的特征。

*  不使用SQL查询语言
 *  可不全面支持[ACID][]（原子性、一致性、隔离性、持久性）。
 *  可提供分布式、容错强的结构

# 2. 键值对存储和关系型数据库 #

不像关系型数据库，键值对存储不需要了解值中的数据，也没有像MySQL或者PostgreSQL中那样的任何结构。这同时表示像SQL那样用WHERE语句或者通过任何形式的过滤来请求数据中的一部分是无法做到的。如果你不知道去哪找，你必须遍历所有的键，获取它们对应的值，应用某种你需要的过滤，然后保留你想要的东西。这将会需要大量的运算，也即表示只有当键已知的时候才能体现出最佳性能，否则键值对存储将无法胜任（注意：一些键值对存储能够存储结构化的数据并有字段索引）。

因此，即使键值对存储在访问速度上经常比关系型数据库系统性能要好数个数量级，但对键已知的需求也限制着其应用。

# 3. 为什么要实现键值对存储 #

我开始这个项目主要是作为充电的一种方式，学习和补充一些核心后端基本原理知识。读书和维基上的文章很无聊并且没有练习，因此我认为着手开始做并且实际写一写代码会更好。我要找的是一个可以让我复习如下内容的项目：

*  C++编程语言
 *  面向对象设计
 *  算法和数据结构
 *  内存管理
 *  多进程或或多线程的并发管理
 *  服务器/客户端模式的网络
 *  磁盘访问的I/O问题和文件系统的使用

一个使用文件系统作为永久存储，且提供网络接口的键值对存储将会包含上面列出的全部范围的内容。这个项目刚好能够处理后端工程的各个领域。但是让我们面对现实。市面上已经有了大量的键值对存储，其中一些是由很聪明的人实现的，并且已经在大公司的生产环境使用了。这包括Redis, MongoDB, memcached, BerkeleyDB, Kyoto Cabinet 和LevelDB。

除此之外，近期出现了关于键值对存储的潮流。好像每人都有一个并且想给大家看自己的键值对存储系统有多么出色和快速。这个问题在[Leonard Lin博客中关于键值对存储的文章][Leonard Lin]中描述了。这些项目中大多数在那时还不成熟且不能应用于生产环境，但人们仍然想展示出来。在博客文章或会议幻灯片中经常可以看到对一些晦涩键值对存储系统性能的比较。这些图表基本上毫无意义，并且只是在自己的硬件上用自己的数据和应用进行的孤立测试，可以告诉你哪一种键值对存储最适用于解决你的问题。这里是性能所依赖的条件：

*  硬件
 *  使用的文件系统
 *  实际应用和具体哪些键会被访问（[引用的局部性][Link 5]）
 *  数据集，特别是键和值的长度，以及使用哈希表的时候键碰撞的可能性。

因此，编写一个键值对存储系统并有一定的影响力是比较难的，因为其很有可能因为其它已存在的更好的键值对存储系统的存在而被忽视，或者被简单的淹没在半生不熟的业余项目中而没人关心。

为了差异性，这个项目不能像其他人做的那样为了速度，而必须瞄准于填补现有解决方案间的空隙。这里是我发现的能够让键值对项目脱颖而出的几个方法。

*  适应于某种特定数据类型（例如：图片，地理数据等）
 *  适应于某种特定操作（例如读取性能特别好或者写入性能特别好等）
 *  适应于某种特定问题 （例如：自动参数调节，很多键值对存储都有很多选项，而找到一个最好的参数设置有时候很棘手）
 *  提供更多数据访问选项。以LevelDB为例，数据可以向前或者向后访问，有迭代器，是按照键排序的。并不是所有的键值对存储都能做到这样。
 *  使自己的实现更平易近人：现在，很少有键值对存储系统有完全的代码。如果你需要快速搭建一个项目，而你必须为其自定义一个键值对存储。即便不是一个广为人知的项目，有代码的解决方案看起来确实平易近人并且会作为选项之一。实际上理解代码并相信这个解决方案会弥补这些不足。
 *   明确应用。这儿有一个实际问题的例子：很多网络爬虫框架（网络蜘蛛）有一个粗劣的接口来管理他们需要爬的URL，这经常使得客户使用键值对存储来实现逻辑。所有的网络爬虫框架都能因一个统一的URL优化的键值对存储而受益。

# 4. 计划 #

项目的目标是用易于理解的C++代码开发一个轻量级键值对存储。事实上，我打算在本项目中遵从[Google C++ 代码风格导引][Google C_]。我将会使用哈希表作为底层数据结构，数据将会存储在硬盘上，同时将会实现一个网络接口。我不会项目进度而匆忙完成，而是要在设计和实现时简洁和清晰。我同样会尽我能力最小化硬盘上数据库文件的空间占用。

我不想重新发明轮子，所以我会从查看别的C或者C++的键值对存储项目开始，然后从中选取比较出色的。我会逐渐学习他们的结构和代码，从中获取启示。后端工程是我的核心技能之一，我已经有了这个项目所需的大部分知识，但我知道我还要学很多新东西，这使其对我来说更加有意思。我同样乐于记录下其中的全部东西。以前我很喜欢逛核心技术博客，例如[Alexander Sandler][]和[Gustavo Duarte][]，我也想贡献出一些有用的，尽可能好的东西。

我的研究结果和键值对存储的一些工作将在这个文章系列中记录。不要试图用文章的日期来推测键值对存储实现的时间：文章可能和实际研究或者做的事之间有相当大的延迟。

在第二部分，我将搜索顶级的键值对存储项目并解释为什么我选择了其中的部分作为参考，而不选另一些。其他的文章你可以参考本系列的[目录][Emmanuel Goossaert _CodeCapsule.com]。

你可以在下边的“引用”一节中找到一些文章和书籍章节来学习更多关于键值对存储的知识。在阅读第二节之前，我强烈建议至少读一下[The NoSQL Ecosystem][]和 [Key Value Stores: A Practical Overview][Key Value Stores_ A Practical Overview]。

# 5. 参考文献 #

*  [The NoSQL Ecosystem][], from the book “Architecture of Open Source Applications, Volume 1″
 *  [NoSQL Patterns][], by Ricky Ho
 *  [NoSQL Databases][], referencing all the NoSQL databases that matter at the moment
 *  [NoSQL Data Modeling Techniques][NoSQL Data Modeling_Techniques], by Ilya Katsov
 *  [NoSQL databases benchmark: Cassandra, HBase, MongoDB, Riak][NoSQL databases benchmark_ Cassandra_ HBase_ MongoDB_ Riak], and the discussion on [Hacker News][]
 *  [Wikipedia article on NoSQL][NoSQL]
 *  [Wikipedia article on the ACID paradigm][ACID]
 *  [Key Value Stores: A Practical Overview][Key Value Stores_ A Practical Overview], by Marc Seeger
 *  [Some Notes on Distributed Key Stores][Leonard Lin], by Leonard Lin

# 实现键值对存储（二）：以现有键值对存储为模型 #

本文中，开头我会解释使用现有模型而非重头开始此项目的原因。我会阐述一系列选择键值对存储模型的标准。最后我将对一些广为人知的键值对存储项目做一个概述，并用这些标准选择其中一些作为模型。本文将包含：

1. 不重新发明轮子  
2. 备选模型和选择标准  
3. 选择的键值对存储的概述  
4. 参考文献

### 1. 不重新发明轮子 ###

键值对存储已经被人们唱好至少30年了[\[1\]][1 1]。最著名的一个项目是DBM，Kenneth Thompson为Unix第七版编写的最早的数据库管理器并在1979年发布[\[2\]][2]。工程师们遇到了和这些数据库系统相关的一些问题，并选择或放弃了各种设计和数据结构的想法。对实际生活中的问题进行试验并从中学习。如果不考虑他们的工作并从头开始是很愚蠢的，只会重复他们之前所犯过的错误。John Gall的系统学中的Gall定理：

任何可以运作的复杂系统都是从可以运作的简单系统发展而来的。其逆命题同样是真命题：由无法正常运作的系统设计而来的复杂系统是不可能正常运作的。你必须重头再来，从一个可运作的简单系统开始。

这段引述为我的键值对存储项目开发带来了两个基础思想。

1. 使用模型。我需要识别出那些存在了一段时间的键值对存储，甚至更进一步，先前成功的键值对存储的继任者。这是其可靠设计的证明，并随着时间在迭代中凝练。这些选择过的建筑的存储应该作为我现在正在工作的项目的模型。

2.起点小。这个项目的第一版必须小且简单，这样它的设计就能简单的测试并通过。如果需要的话，改进和额外功能必须在后续版本中加入。

### 2. 待选模型和选择标准 ###

在对键值对存储和NoSQL数据库做过一点研究后，我决定将下面的几个作为进一步选择的选项：

*  DBM
 *  Berkeley DB
 *  Kyoto Cabinet
 *  Memcached and MemcacheDB
 *  LevelDB
 *  MongoDB
 *  Redis
 *  OpenLDAP
 *  SQLite

选择标准如下:

*  我想使用面向对象编程来创建键值对存储，所以在设计上，我必须从由面向对象语言编写的项目中汲取灵感。
 *  至于底层数据结构，我想要一个存在硬盘上的哈希表，于是我需要选择一个提供读写信息到硬盘上的方法的项目。
 *  我同样想让这个数据存储能够有网络接入。
 *  我不需要查询引擎或者方法来访问结构化的数据.
 *  不必完全支持ACID规范。
 *  鉴于这个项目是我自己弄的，我想使用那些由小团队实现的项目模型，理想情况下是一两个人。

### 3. 所选键值对的概览 ###

三个获选的模型是Berkeley DB、Kyoto Cabinet 和LevelDB。Berkeley DB和Kyoto Cabinet作为DBM的继任者有着相同的历史。此外，Berkeley DB 和 Kyoto Cabinet 并非“初版”。这表示他俩与其他初次实现的键值对存储项目比较更加可靠。LevelDB则更加现代，并基于LSM树的数据结构，其对于哈希表模式来说是无用的。然而其代码是我见过最干净的。这三个项目都是由一两个人开发的。下面是他们各自的详细信息。

#### Berkeley DB ####

Berkeley DB的开发始于1986年，这表示我开始写这篇文章的时候它已经存在了26年了。Berkeley DB是作为DBM的继任者而开发的，并实现了一个哈希表。第一版是由Margo Seltzer [\[22\]][22] 和 Ozan Yigit [\[23\]][23] 在加州大学伯克利分校的时候编写的。这个项目后来被Oracle获得，并由其继续开发。

Berkeley DB最初是由C实现的，并且现在仍然是只用C。其通过增量过程开发的，就是说在每个主版本增加新的功能。Berkeley DB从一个简单的键值对存储，进化到管理并行访问、事务及复原、及同步功能[\[4\]][4]。Berkeley DB的使用非常广泛，有着数亿已部署的拷贝[\[5\]][5]，这是可以相信其架构及其可靠的证据。关于其设计的更多信息可以在“Berkeley DB Programmer’s Reference Guide”[\[6\]][6] 的介绍和“The Architecture of Open Source Applications, Volume 1” [\[5\]][5]的开头中找到。

#### Kyoto Cabinet ####

Kyoto Cabinet在2009年由Mikio Hirabayashi [\[24\]][24] 引进。其现在仍在积极进化中。Kyoto Cabinet是同一个作者的其它键值对存储：Tokyo Cabinet (2007发布) 和QDBM (2003发布, 2000开始)的继任者。QDBM打算作为DBM的高性能继任者[\[7\]][7]。Kyoto Cabinet尤其有意思，因为它有着DBM的纯正血统，并且它的作者在键值对存储方向工作12年了。在浸淫三个键值对存储这么多年之后，没有理由怀疑作者有着对结构需求的坚实理解，以及随之的对性能瓶颈的成因的极强认识。

Kyoto Cabinet是由C++实现的，并实现了一个哈希表，一个B+树，以及其他一些深奥的数据结构。其同样提供了出色的性能[\[16\]][16]。然而，因其内部参数的原因，似乎有些性能问题。的确，很多人报道说只要数据条目的数量保持在某一特定的阈值（正比于桶数组大小，其由创建数据库文件时的参数所确定）以下，性能就很好。一旦超过这个阈值，性能似乎急剧下降[\[18\]][18][\[19\]][19]。Tokyo Cabinet [\[20\]][20] [\[21\]][21] 中也有相同的问题。这表示如果某项目的需求在数据库使用的时候改变，你可能会遇到严重的问题。而我们都知道，软件中的改变是如此的频繁。

#### LevelDB ####

LevelDB是由Google职员Jeffrey Dean [\[8\]][8] 和 Sanjay Ghemawat [\[9\]][9] 开发，他们为Google传说中的基础建设项目MapReduce和BigTable工作。基于Dean和Ghemawat在在Google工作时获得的大规模问题上的经验，他们很有可能很了解他们正在做的东西。和大多数键值对存储项目相比，LevelDB有一个很有意思的不同点就是它不用哈希表或者B-树作为底层数据结构，而是基于一个日志结构的合并树[\[12\]][12]。LSM结构据说是为SSD硬盘优化的[\[13\]][13]。你可以在这个博客High Scalability blog [\[17\]][17]找到成吨的关于LevelDB的信息。

LevelDB是由C++实现，2011年发布，并设计作为高级存储系统的一部分[\[10\]][10]。IndexedDB HTML5 API在Chrome将来版本的实现将使用LevelDB [\[10\]][10] [\[11\]][11]。其性能决定于特定的工作负载，就像作者提供的基准测试中显示的那样[\[14\]][14]。然而，Andy Twigg在Acunu的另外一个基于商用SSD的基准测试显示出，如果数据的条数超过1e6（1百万），并向1e9（10亿）前进的时候，性能将会显著下降[\[15\]][15]。因此似乎LevelDB似乎并不是重工作负载或像实际后端项目需求那样的大数据库最好的选择。

但这其实并不重要，对于我来说，LevelDB最好的部分不是其性能而是其架构。看它的源代码和东西组织的方式，那是纯粹的美。所有的东西都很清晰、简单、条理分明。访问LevelDB的源代码并把它作为模范是创建出色代码的绝好机遇。

#### 那些没选中的键值对存储是什么情况？ ####

没有选择其他键值对存储的原因并不表示我完全抛弃他们。我会记得他们并可能偶尔使用他们结构中元素。但是，当前项目受到这些键值对项目影响不会像已选择的这些那么多。

### 4. 参考文献 ###

\[1\] [http://blog.knuthaugen.no/2010/03/a-brief-history-of-nosql.html][http_blog.knuthaugen.no_2010_03_a-brief-history-of-nosql.html]  
\[2\] [http://en.wikipedia.org/wiki/Dbm][http_en.wikipedia.org_wiki_Dbm]  
\[3\] [http://en.wikipedia.org/wiki/Systemantics][http_en.wikipedia.org_wiki_Systemantics]  
\[4\] [http://en.wikipedia.org/wiki/Berkeley\_DB\#Origin][http_en.wikipedia.org_wiki_Berkeley_DB_Origin]  
\[5\] [http://www.aosabook.org/en/bdb.html][http_www.aosabook.org_en_bdb.html]  
\[6\] [http://docs.oracle.com/cd/E17076\_02/html/programmer\_reference/intro.html][http_docs.oracle.com_cd_E17076_02_html_programmer_reference_intro.html]  
\[7\] [http://fallabs.com/qdbm/][http_fallabs.com_qdbm]  
\[8\] [http://research.google.com/people/jeff/][http_research.google.com_people_jeff]  
\[9\] [http://research.google.com/pubs/SanjayGhemawat.html][http_research.google.com_pubs_SanjayGhemawat.html]  
\[10\] [http://google-opensource.blogspot.com/2011/07/leveldb-fast-persistent-key-value-store.html][http_google-opensource.blogspot.com_2011_07_leveldb-fast-persistent-key-value-store.html]  
\[11\] [http://www.w3.org/TR/IndexedDB/][http_www.w3.org_TR_IndexedDB]  
\[12\] [http://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/][http_www.igvita.com_2012_02_06_sstable-and-log-structured-storage-leveldb]  
\[13\] [http://www.acunu.com/2/post/2011/04/log-file-systems-and-ssds-made-for-each-other.html][http_www.acunu.com_2_post_2011_04_log-file-systems-and-ssds-made-for-each-other.html]  
\[14\] [http://leveldb.googlecode.com/svn/trunk/doc/benchmark.html][http_leveldb.googlecode.com_svn_trunk_doc_benchmark.html]  
\[15\] [http://www.acunu.com/2/post/2011/08/benchmarking-leveldb.html][http_www.acunu.com_2_post_2011_08_benchmarking-leveldb.html]  
\[16\] [http://blog.creapptives.com/post/8330476086/leveldb-vs-kyoto-cabinet-my-findings][http_blog.creapptives.com_post_8330476086_leveldb-vs-kyoto-cabinet-my-findings]  
\[17\] [http://highscalability.com/blog/2011/8/10/leveldb-fast-and-lightweight-keyvalue-database-from-the-auth.html][http_highscalability.com_blog_2011_8_10_leveldb-fast-and-lightweight-keyvalue-database-from-the-auth.html]  
\[18\] [http://stackoverflow.com/questions/13054852/kyoto-cabinet-berkeley-db-hash-table-size-limitations][http_stackoverflow.com_questions_13054852_kyoto-cabinet-berkeley-db-hash-table-size-limitations]  
\[19\] [https://groups.google.com/forum/\#!topic/tokyocabinet-users/Bzp4fLbmcDw/discussion][https_groups.google.com_forum_topic_tokyocabinet-users_Bzp4fLbmcDw_discussion]  
\[20\] [http://stackoverflow.com/questions/1051847/why-does-tokyo-tyrant-slow-down-exponentially-even-after-adjusting-bnum][http_stackoverflow.com_questions_1051847_why-does-tokyo-tyrant-slow-down-exponentially-even-after-adjusting-bnum]  
\[21\] [https://groups.google.com/forum/\#!topic/tokyocabinet-users/1E06DFQM8mI/discussion][https_groups.google.com_forum_topic_tokyocabinet-users_1E06DFQM8mI_discussion]  
\[22\] [http://www.eecs.harvard.edu/margo/][http_www.eecs.harvard.edu_margo]  
\[23\] [http://www.cse.yorku.ca/~oz/][http_www.cse.yorku.ca_oz]  
\[24\] [http://fallabs.com/mikio/profile.html][http_fallabs.com_mikio_profile.html]

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

在本文中，我将会逐组件地把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. 参考文献

![63918611gw1elm3s7jto1j20le0cxtav.jpg][]

### 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\]][1 2]  
– Memcached for dummies, by Tinou Bao [\[2\]][2 1]  
– Memcached Internals [\[3\]][3]  
– MongoDB Architecture, by Ricky Ho [\[4\]][4 1]  
– Couchbase Architecture, by Ricky Ho [\[5\]][5 1]  
– The Architecture of SQLite [\[6\]][6 1]  
– Redis Documentation [\[7\]][7 1]

### 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\]][8 1]。在你机器上安装好Doxygen之后，只需要打开shell界面，到包含所有你需要分析的源代码的目录下。然后输入如下命令即可创建默认设置文件。

Shell

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

Shell

文档将在“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是以一种非常模块化的方法建立的，只有内存管理才是内核组件的一部分。

![63918611gw1elm3s8jmdxj20le0pugoe.jpg][]

图3.1

![63918611gw1elm3s9i5lyj20le0p0diw.jpg][]

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

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

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

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

3.6 错误管理

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

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

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

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

#### 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要小。

### 5. 参考文献 ###

\[1\] [http://www.aosabook.org/en/bdb.html][http_www.aosabook.org_en_bdb.html]  
\[2\] [http://work.tinou.com/2011/04/memcached-for-dummies.html][http_work.tinou.com_2011_04_memcached-for-dummies.html]  
\[3\] [http://code.google.com/p/memcached/wiki/NewUserInternals][http_code.google.com_p_memcached_wiki_NewUserInternals]  
\[4\] [http://horicky.blogspot.com/2012/04/mongodb-architecture.html][http_horicky.blogspot.com_2012_04_mongodb-architecture.html]  
\[5\] [http://horicky.blogspot.com/2012/07/couchbase-architecture.html][http_horicky.blogspot.com_2012_07_couchbase-architecture.html]  
\[6\] [http://www.sqlite.org/arch.html][http_www.sqlite.org_arch.html]  
\[7\] [http://redis.io/documentation][http_redis.io_documentation]  
\[8\] [http:://doxygen.org][http_doxygen.org]  
\[9\] [http://www.stack.nl/~dimitri/doxygen/config.html][http_www.stack.nl_dimitri_doxygen_config.html]  
\[10\] [http://leveldb.googlecode.com/svn/trunk/doc/index.html][http_leveldb.googlecode.com_svn_trunk_doc_index.html]  
\[11\] [http://redis.io/topics/internals-sds][http_redis.io_topics_internals-sds]  
\[12\] [http://news.ycombinator.com/item?id=3883310][http_news.ycombinator.com_item_id_3883310]  
\[13\] [http://www.briancarpio.com/2012/05/03/mongodb-memory-management/][http_www.briancarpio.com_2012_05_03_mongodb-memory-management]  
\[14\] [http://leveldb.googlecode.com/svn/trunk/doc/impl.html][http_leveldb.googlecode.com_svn_trunk_doc_impl.html]  
\[15\] [http://oldblog.antirez.com/post/everything-about-redis-24.html][http_oldblog.antirez.com_post_everything-about-redis-24.html]

# 实现键值对存储（四）：API设计 #

我终于为这个键值对存储项目确定了一个名字，从现在开始我将叫它FelixDB KingDB。（译注：改成这么土的名字也是醉了）

在本文中，我将对带着大家看一看四个键值对存储和数据库系统的API：LevelDB, Kyoto Cabinet, BerkekeyDB 和 SQLite3。对于其API中的每个主要功能，我将会比较他们的命名习惯和方法原型，以平衡其优缺点并为正在开发的键值对存储KingDB设计API。本文将包括：

1.  API设计的一般准则
2.  定义KingDB公共API的功能
3.  比较现有数据库的API  
    3.1 打开和关闭数据库  
    3.2 读写操作  
    3.3 遍历  
    3.4 参数处理  
    3.5 错误管理
4.  结论
5.  参考文献

# 1.API设计的一般准则 #

设计一个好的API很难，相当难。但我在这说的不是什么新东西，而只是在重复之前很多人告诉我的东西。到目前为止我发现的最好的资料是Joshua Bloch的演讲“How to Design a Good API & Why it Matters（如何设计一个好的API及为什么这很重要）”[\[1\]][1 3]，及其摘要版本[\[2\]][1 3]。如果你还没有看过这个演讲，我强烈建议你找时间去看一下。在这个演讲中，Bloch清晰的陈述了听众需要记住的两个很重要的东西。我复制了摘要版本的要点并添加了一些评论：

1.  不确定的时候，先放一边。当不确定某功能、类、方法或参数是否要添加在API中的时候，不要添加。
2.  不要让用户做库可以做的事情。如果你的API让客户执行一系列函数调用的时候，需要将每个函数的输出塞到下一个函数的输入里，那你应该在API中添加一个函数来执行这一系列的函数调用。

另一个关于API设计的好资源是Joshua Bloch写的《Effective Java》[4][1 3]和Scott Meyers写的《Effective C++》[3][1 3]第四章“Designs and Declarations”。

这些资源对于当前阶段的这个键值对存储项目来说十分重要，尽管我觉得这些资源没有包含一个很重要的因素：用户期望。将API从草图上设计出来是很难的，但这个键值对存储的例子来说，是有例可循的。用户一直和他们的键值对存储或数据库系统的API打交道。因此，当面对一个新的键值对存储的时候，用户希望有一个类似的环境，而不关心这潜规则只会提高用户对新API的学习曲线，并让用户不高兴。

鉴于这个原因，即便我牢记上文列出的这些资料中的所有好建议，但我仍认为我必须尽可能多的复制已有库的API，因为这可以在用户使用我正创建的API时更简单。

# 2.定义KingDB公共API的功能 #

考虑到这只是万里长征的第一步，我打算实现一个最小且可靠的键值对存储，我当然不会包含所有的，像Kyoto Cabinet 和LevelDB那样的成熟项目提供的高级功能。我打算先让基本功能实现，然后我将逐渐增加其他功能。对于我来说，基本功能严格限制在：

*  打开和关闭数据库
 *  读写数据库
 *  遍历数据库中所有的键值对集合
 *  提供参数调整的方法
 *  提供一个合适的错误通知接口

我意识到这些功能对于一些用例来说过于局限了，但暂时应该对付的过来。我不打算添加任何事务机制、分类查询、或原子操作。同样，现在我不打算提供快照功能。

# 3.比较现有数据库的API #

为了比较现有数据库的C++ API，我将会比较每个功能的示例代码。 这些示例代码是修改自或直接取自于官方代码“Fundamental Specifications of Kyoto Cabinet” [\[5\]][1 3], “LevelDB’s Detailed Documentation” [\[6\]][1 3], “Getting Started with Berkeley DB” [\[7\]][7 2], 和 “SQLite in 5 minutes or less” [\[8\]][1 3]。 我同样会使用不同的颜色来标示来自不同的API。

## 3.1 打开和关闭数据库 ##

下述示例代码显示出研究的系统是如何打开数据库的。为了更清晰的显示代码原理，选项设置和错误管理没有在此显示，并且会在下述各节中解释更多的细节。

C++

在打开数据库部分出现了两种清晰的模式。一方面，LevelDB 和SQLite3的API请求创建一个数据库对象的指针（句柄）。然后调用打开函数的时候将这个指针的引用作为参数，以定位对象的内存空间，然后设置这个数据库对象。另一方面，Kyoto Cabinet 和Berkeley DB的API以实例化一个数据库对象为开始，然后调对象的用open()方法来设置这个数据库对象。

说到关闭数据库部分，LevelDB只需要请求删除指针就行了，但SQLite3必须调用关闭函数。Kyoto Cabinet 和BerkeleyDB的数据库对象自身有一个close()方法。

我相信像LevelDB 和SQLite3那样强制使用数据库对象的指针，然后将指针传递给打开函数是很“C风格”的。另外，我认为LevelDB处理关闭的方法—通过删除指针—是一个设计缺陷。因为这会导致API的不对称。在API中，函数的对称应该尽可能的对称，因为这样更加直观和逻辑。“如果我调用了open() 那我就应该调用close()”的想法比“如果我调用了open() 那我就应该删除指针”的想法合乎逻辑一万倍。

设计决策

因此我决定使用在KingDB上的是类似于Kyoto Cabinet 和Berkeley DB的，先实例化一个数据库对象，然后调用对象的Open() 和Close()方法。至于命名，我仍使用传统的Open() 和Close()。

## 3.2 读写 ##

在本节，我比较他们读写功能的API。

C++

<table style="margin-left: 0px; font-size: 13px; border: none !important; margin-top: 0px !important; margin-right: 0px !important; margin-bottom: 0px !important; padding: 0px !important; border-collapse: collapse !important; border-spacing: 0px !important; width: auto !important; table-layout: auto !important; background: none !important;"> 
 <tbody style="border: 0px; margin: 0px; padding: 0px;"> 
  <tr style="border: none !important; margin: 0px !important; padding: 0px !important; vertical-align: top !important; background: none;"> 
   <td style="font-size: 13px; text-align: center; border: none !important; margin: 0px !important; padding: 0px !important; vertical-align: top !important; font-family: Monaco, MonacoRegular, 'Courier New', monospace !important; background-image: none; background-attachment: initial; background-color: rgb(238, 238, 238) !important; background-size: initial; background-origin: initial; background-clip: initial; background-position: initial; background-repeat: initial;"> 
    <div style="border: none; margin: 0px; padding-right: 0px; padding-left: 0px; text-align: left; white-space: nowrap; padding-top: 5px !important; padding-bottom: 3px !important; line-height: 15px !important; background: none;"> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       1 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       2 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       3 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       4 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       5 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       6 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       7 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       8 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       9 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       10 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       11 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       12 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       13 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       14 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       15 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       16 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       17 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       18 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       19 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       20 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       21 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       22 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       23 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       24 
     </div> 
     <div style="border-right-width: 1px !important; border-top-style: none; border-right-style: solid !important; border-bottom-style: none; border-left-style: none; border-right-color: rgb(222, 222, 222) !important; margin: 0px; padding: 0px 5px; font-size: inherit !important; font-family: inherit; text-align: right !important; height: inherit; line-height: inherit !important; font-weight: inherit !important; min-width: 1.2em !important; color: rgb(170, 170, 170) !important; background: none;">
       25 
     </div> 
    </div></td> 
   <td style="font-size: 13px; text-align: center; width: 581px; border: none !important; margin: 0px !important; padding: 0px !important; vertical-align: top !important; font-family: Monaco, MonacoRegular, 'Courier New', monospace !important; background: none;"> 
    <div style="margin: 0px; padding-right: 0px; padding-left: 0px; text-align: left; white-space: pre; overflow: visible; tab-size: 4; border: none !important; padding-top: 5px !important; padding-bottom: 3px !important; line-height: 15px !important; background: none !important;"> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(153, 153, 153) !important; font-style: italic !important;">/* Berkeley DB */</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(153, 153, 153) !important; font-style: italic !important;">/* reading */</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">Dbt </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">key</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">data</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">key</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">.</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">set_data</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">&amp;amp</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">money</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">key</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">.</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">set_size</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">sizeof</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: bold !important; color: rgb(128, 0, 128) !important;">float</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">data</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">.</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">set_data</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">description</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">data</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">.</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">set_ulen</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">DESCRIPTION_SIZE</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">+</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 153, 153) !important;">1</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">data</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">.</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">set_flags</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">DB_DBT_USERMEM</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">db</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">.</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">get</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: bold !important; color: rgb(128, 0, 128) !important;">NULL</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">&amp;amp</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">key</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">&amp;amp</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">data</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 153, 153) !important;">0</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(153, 153, 153) !important; font-style: italic !important;">/* writing */</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: bold !important; color: rgb(128, 0, 128) !important;">char</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">*</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">description</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">=</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(221, 17, 68) !important;">"Grocery bill."</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: bold !important; color: rgb(128, 0, 128) !important;">float</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">money</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">=</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 153, 153) !important;">122.45</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">Dbt </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">key</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">&amp;amp</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">money</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: bold !important;">sizeof</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: bold !important; color: rgb(128, 0, 128) !important;">float</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">Dbt </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">data</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">description</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">strlen</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">description</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">+</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 153, 153) !important;">1</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">db</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">.</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: teal !important;">put</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">(</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: bold !important; color: rgb(128, 0, 128) !important;">NULL</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">&amp;amp</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">key</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">&amp;amp</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">data</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">,</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">DB_NOOVERWRITE</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">)</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;">
       &nbsp; 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: bold !important; color: rgb(128, 0, 128) !important;">int</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(128, 0, 128) !important;">const</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">DESCRIPTION_SIZE</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">=</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 153, 153) !important;">199</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: bold !important; color: rgb(128, 0, 128) !important;">float</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">money</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">=</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 153, 153) !important;">122.45</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
     <div style="border: none; margin: 0px; padding: 0px 5px; font-family: inherit; height: inherit; font-size: inherit !important; line-height: inherit !important; font-weight: inherit !important; background: none;"> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: bold !important; color: rgb(128, 0, 128) !important;">char</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">description</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">[</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 45, 122) !important;">DESCRIPTION_SIZE</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;">+</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 111, 224) !important;"> </span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(0, 153, 153) !important;">1</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">]</span> 
      <span style="border: 0px; margin: 0px; padding: 0px; font-size: inherit !important; font-family: inherit; height: inherit; line-height: inherit !important; font-weight: inherit !important; color: rgb(51, 51, 51) !important;">;</span> 
     </div> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

我不会考虑SQLite3的设计，因为其是基于SQL的，因此其读写是通过SQL请求进行的，而非方法调用。Berkeley DB请求Dbt类对象的创建，并在上面进行一大堆设置，因此我也不会考虑这个设计。剩下的只有LevelDB 和Kyoto Cabinet，而他们有很漂亮的getter/setter对称接口。LevelDB 有Get() 和Put(), 而Kyoto Cabinet 有get() 和set()。Setter方法的原型——Put() 和set()十分相似：键名是值传递，而键值是传递的指针使得调用时可以更改。键值并不通过调用返回，返回值是给错误管理使用的。

设计决策

对于KingDB，我打算使用和LevelDB 及Kyoto Cabinet相似的方法，对于setter方法使用一个相似的原型，即用值传递键值而用指针传递键值。至于命名，一开始我觉得Get() 和Set()是最好的选择，但仔细思考之后我更倾向于LevelDB那样，使用Get() 和Put()。其原因是Get/Set 和Get/Put都很对称，但“Get” 和 “Set”两个词太相似，只差了一个字母。因此阅读代码的时候使用“Get” 和“Put”会更加清晰且更易辨认，因此我会使用Get/Put。

## 3.3 遍历 ##

C++

在上一节中，SQLite3不被考虑是因为其不满足键值对存储的需求。但看看它是如何将一个SELECT请求发送到数据库，然后在取回来的每一行上调用回调函数是比较有趣的。大多数MySQL 和 PostgreSQL的API用循环并调用一个能够填充本地变量的函数来做到，而非这样使用一个回调函数。我发现这种回调函数比较棘手，因为这对于那些想执行合计操作或对取回来的行进行计算的用户来说，会让事情变得复杂。但这是另一方面的讨论，现在回到我们的键值对存储上来！

这里有两种方法：使用游标或者使用遍历器。Kyoto Cabinet 和BerkeleyDB使用游标，一开始创建一个指向游标对象的指针并实例化对象，然后在while循环中重复调用游标的get()方法来获取数据库中所有的值。LevelDB使用遍历器设计模式，一开始创建一个指向遍历器对象的指针并实例化对象（这部分和游标一样），但是使用一个for循环来遍历集合中的项目。注意这里的while和for循环只是习惯：游标可以使用for循环而遍历器也可以使用while循环。其主要的不同是，在游标中，键和值是指针传递然后在游标的get()方法中填充内容，但在迭代器中，键和值是通过迭代器方法的返回值来访问的。

设计决策

同样，游标和其while循环是相当“C风格”的。我发现迭代器的方法更加清晰并更符合“C++风格”，因为这正是C++中STL的集合的访问方式。因此对于KingDB来说，我选择使用LevelDB那样的遍历器。至于命名，我简单的复制了LevelDB中的方法名。

## 3.4 参数处理 ##

参数在IKVS系列文章中第三部分3.4节已经简要叙述了，但我还想在这提一下。

C++

SQLite3是通过sqlite3\_config()修改全局参数，然后在所有后续连接建立的时候应用。Kyoto Cabinet 和Berkeley DB中，选项是在调用open()之前通过调用数据库对象的方法来设置选项的，和SQlite3的做法比较相似。在这些方法之上，更通用的选项是通过open()方法的参数来设置的（见上文3.1节）。这表示选项被分为两部分，一些通过方法的调用来设置，而另一些是通过open()的调用来设置。

LevelDB的做法不大一样。选项是在自己的类中一起定义，而参数是通过这些类的属性来更改。之后这些设置类的对象以方法参数的形式传递，并总是第一个参数。例如LevelDB数据对象的open()方法的第一个参数是leveldb::Options类的对象，而Get()和Put()方法的第一个参数分别是leveldb::ReadOptions 和leveldb::WriteOptions。这种设计的一个好处是在同时创建多个数据库的情况下可以很简单的共享设置，尽管在Kyoto Cabinet 和 Berkeley DB的例子中可以为一组设置创建一个方法，然后通过调用这个方法来设置这组设定。像LevelDB那样把设置放到一个特定的类中真正的优势在于，其接口更稳定，因为扩展设置只需要修改这个选项类，而不用修改数据库对象的任何方法。

尽管我想用这种选项类，但我必须说的是LevelDB这种总是将选项作为第一个参数在各个方法中传递的方式我不是很习惯。如果没有需要修改的选项，这导致代码中需要使用默认选项，就像这样：

C++

这可能导致代码膨胀，而另一种可能是将选项作为最后一个参数，然后为这个参数设定一个缺省值，使得不需要设置选项的时候可以省掉这项。而另一种源自于C++的解决方式是函数的重载，有数个带有原型的方法使其可以省略掉选项的对象。把选项放到参数的最后对于我来说看上去更符合逻辑，因为其是可能省略的。但我相信LevelDB的作者把选项作为第一个参数是有很好的原因的。

设计决策

对于参数处理，我觉得将选项作为类是最简洁的方式，同时其符合面向对象设计。

对于KingDB来说，我会像LevelDB那样使用独立的类来处理选项，不过我会将作为方法的最后一个参数。我或许以后能明白将选项作为最后一个参数是真正正确的方法——或者有谁能帮我解释下——但现在我坚持将其放到最后。最后，命名子啊这儿不是很重要，因此Options, ReadOption 和WriteOption都可以。

## 3.5 错误管理 ##

在IKVS系列第三部分3.6节，有关于错误管理的一些讨论，基本上是说用户看不到的代码是如何管理错误的。本节再次讨论这个话题但稍有不同，不讨论库中错误的细节，而是关于错误发生后是怎么报告给使用公共接口的用户的。

C++

Kyoto Cabinet, Berkeley DB 和SQLite3使用相同的方法处理错误，即其方法返回一个整型的错误代码。如在IKVS系列第三部分3.6节所述，Kyoto Cabinet内部将值设置在数据库对象中，这就是为何上述示例代码中，错误信息是从db.error().name()取出的。

LevelDB有个一特别的Status类，包含错误类型和提供了关于此错误更多信息的消息。LevelDB库中的所有方法都返回了此类的一个对象，这使错误测试和将错误传递给系统各部分以进行进一步的检查更加简单。

设计决策

返回错误代码而避免使用C++的异常处理机制是十分正确的，然而整形并不足以携带有意义的信息。Kyoto Cabinet, Berkeley DB 和SQLite3都有其自己的存储错误信息的方法，然而即便是在在Kyoto Cabinet 和Berkeley例子中，创建了错误管理和数据库类的强耦合，，仍然会为取得信息添加额外的步骤。像LevelDB那样使用一个Status类可以避免使用C++异常处理，同时也避免了和架构其他部分的耦合。

# 4.结论 #

API的预设比较有意思，因为去看不同的工程师如何解决相同的问题总是很有意思的。这同样让我意识到Kyoto Cabinet 和Berkeley DB的API有多么相似。Kyoto Cabinet 的作者Mikio Hirabayashi清楚地声明了他的键值对存储是基于Berkeley DB的，而在看完API相似性之后这一点更加清晰了。

LevelDB的设计相当好，但我还是对于一些我认为可以以其他方式实现的细节有些意见。例如数据库打开和关闭以及方法原型。

我吸取了每个系统的一点长处，而我现在对于KingDB的API设计的各个选择感觉更加自信了。

# 5.参考文献 #

\[1\] http://www.infoq.com/presentations/effective-api-design  
\[2\] http://www.infoq.com/articles/API-Design-Joshua-Bloch  
\[3\] http://www.amazon.com/Effective-Specific-Improve-Programs-Designs/dp/0321334876  
\[4\] http://www.amazon.com/Effective-Java-Edition-Joshua-Bloch/dp/0321356683  
\[5\] http://fallabs.com/kyotocabinet/spex.html  
\[6\] http://leveldb.googlecode.com/svn/trunk/doc/index.html  
\[7\] http://docs.oracle.com/cd/E17076\_02/html/gsg/CXX/index.html  
\[8\] http://www.sqlite.org/quickstart.html

# 实现键值对存储（五）：哈希表实现 #

在本文中，我将会研究C++中哈希表的实际实现以理解其瓶颈。哈希函数是CPU密集型的并且应该维持而优化。然而，大部分哈希表的内部机制只关心内存效率和I/O访问，这将是本文主要注意的东西。我将会研究三个不同的哈希表的C++实现，既有内存中的又有硬盘上的，并看看数据是怎么组织和访问的。本文将包括：

1.哈希表  
1.1 哈希表简介  
1.2 哈希函数  
2.实现  
2.1 TR1的unordered\_map  
2.2 SparseHash的dense\_hash\_map  
2.3 Kyoto Cabinet的HashDB  
3.结论  
4.参考文献

![63918611gw1en6lpyukytj20le08rt9h.jpg][]

# 1.哈希表 #

## 1.1 哈希表简介 ##

> 哈希表可以认为是人类所知最为重要的数据结构 .  
> — 斯蒂夫 耶奇

哈希表可以高效的访问关联数据。每个条目都有一对对应的键名和键值，并且能仅通过键名来快速的取回和赋值。为了达到这个目的，键名通过哈希函数进行哈希，以将键名从原始形式转换为整数。此整数之后作为索引来得到要访问的条目的值所在的bucket在bucket数组中的地址。很多键名可以被哈希为相同的值，这表示这些key在bucket数组中回出现碰撞。有数种方法解决碰撞，如使用链表的分离链表（separate chaining 亦称开链或单独链表）或自平衡二叉树或线性或者二次探测的开放寻址。

从现在开始，我默认你知道什么是哈希表。如果你认为自己需要温习一下知识，Wikipedia的“Hash table”词条[\[1\]][1 4]（及其底部的扩展链接一节）和Cormen 等人写的Introduction to Algorithms一书中Hash table一章[\[2\]][1 4]都是很好的参考文献。

## 1.2 哈希函数 ##

哈希函数的选择相当重要。一个好哈希函数的基本需求是输出的哈希值比较均匀。这样可以使碰撞的发生最小化，同时使得各个bucket中碰撞的条目比较平均。

可用的哈希函数有很多，除非你确切的知道数据会变成什么样子，最安全的方法是找一个能够将随机数据分布均匀的哈希函数，如果可能的话符合雪崩效应[\[3\]][1 4]。有少数人对哈希函数做过比较[\[4\]][1 4] [\[5\]][1 4] [\[6\]][1 4] [\[7\]][1 4]，而他们的结论是MurmurHash3 [\[8\]][8 2]和CityHash [\[9\]][1 4] 是在写本文的时候最好的哈希函数。

# 2.实现 #

和哈希函数的比较一样，只有很少比较各个C++的内存哈希表库性能的博文。我见到的最出名的是Nick Welch 的“Hash Table Benchmarks” [\[10\]][1 4]，和Jeff Preshing 的“Hash Table Performance Tests” [\[11\]][8 2]。而其他文章也值得一看[\[12\]][1 4] [\[13\]][1 4] [\[14\]][1 4]。从这些比较中，我发现两个研究起来比较有意思的部分：GCC的TR1的unordered\_map和SparseHash 库（以前叫Google SparseHash）的dense\_hash\_map，我将会在下文中介绍他们。另外，我同样会描述Kyoto Cabinet中HashDB的数据结构。显然因为unordered\_map 和dense\_hash\_map是内存哈希表，不会像HashDB那样和我的键值对存储相关。尽管如此，稍微看一下其内部数据结构的组织和其内存模式也是很有意思的。

在下述三个哈希表库的描述中，我的通用示例是把一组城市名作为键名其各自的GPS坐标作为键值。unordered\_map的源代码可以在GCC代码中作为libstdc++-v3的一部分找到。我将会着眼于GCC v4.8.0的libstdc++-v3 release 6.0.18[\[15\]][1 4]，SparseHash v2.0.2中的dense\_hash\_map[\[16\]][1 4]，和Kyoto Cabinet v1.2.76中的HashDB[\[17\]][1 4]。

Matthew Austern的“A Proposal to Add Hash Tables to the Standard Library (revision 4)”一文[\[18\]][1 4]和SparseHash的“Implementation notes”页面[\[19\]][1 4]也有很有意思的关于哈希表实现的讨论。

## 2.1 TR1中的unordered\_map ##

TR1的unordered\_map提供了一个用链表（分离链）解决碰撞的哈希表。Bucket数组位于堆中，并且基于哈希表的负载系数自动调整大小。而bucket的链表则是用叫做`_Hash_node`的节点结构体创建。

C++

如果键和值都是整型，其可以直接存储在`_M_v`结构体中。否则将会存储指针，同时需要额外的内存。Bucket数组是在堆中一次性分配的，但并不分配节点的空间，节点的空间是通过各自调用C++内存分配器来分配的。

C++

因为这些节点是各自分配的，分配过程中可能浪费大量的内存。这取决于编译器和操作系统使用的内存分配过程。我甚至还没说每次分配中系统执行的调用。SGI哈希表的原始实现为这些节点做了一些资源预分配工作，但这个方法没有保留在TR1的 unordered\_map实现中。

下文的图5.1展示了TR1中unordered\_map的内存和访问模式。让我们来看看当我们访问和键名“Johannesburg”相关的GPS坐标的时候会发生什么。这个键名被哈希并映射到了bucket \#0。在那我们跳到了此bucket的链表的第一个节点（bucket \#0左边的橙色箭头），我们可以访问堆中存储了键“Johannesburg”所属数据的内存区域（节点右侧的黑色箭头）。如果键名所指向的第一个节点不可用，就必须遍历其他的节点来访问。

至于CPU性能，不能指望所有的数据都在处理器的同一个缓存行中。实际上，基于bucket数组的大小，初始bucket和初始节点不会在同一个缓存行中，而和节点相关的外部数据同样不太可能在同一个缓存行中。而随后的节点机器相关数据同样不会在同一个缓存行中并且需要从RAM中取回。如果你不熟悉CPU优化和缓存行，维基上的“CPU Cache”文章是一个很好的介绍[\[20\]][1 4]。

![63918611gw1en6lpzics7j20le0qcad9.jpg][]

图5.1

## 2.2 SparseHash的dense\_hash\_map ##

SparseHash库提供了两个哈希表实现，sparse\_hash\_map和dense\_hash\_map。sparse\_hash\_map在低成本下提供了出色的内存占用，并使用一个特定的数据结构sparsetable来打到这个目的。在SparseHash的“Implementation notes”页面[19][1 4]可以找到更多关于sparsetables 和sparse\_hash\_map的信息。在此我只讨论dense\_hash\_map。

dense\_hash\_map用二次内部探测处理碰撞。和unordered\_map一样，bucket数组也是在堆中一次分配，并基于哈希表的负载因子调整大小。bucket数组的元素是`std::pair`的实例，其中`Key`和`T`分别是键名和键值的模版参数。在64位架构下储存字符串的时候，pair的实例大小是16字节。

下文的图5.2是dense\_hash\_map内存和访问模式的展示。如果我们要寻找“Johannesburg”的坐标，我们一开始会进入bucket \#0，其中有“Paris”（译注：图上实际应为“Dubai”）的数据（bucket \#0右侧的黑色箭头）。因此必须探测然后跳转到bucket (i + 1) = (0 + 1) = 1（bucket \#0左侧的橙色箭头），然后就能在bucket \#1中找到“Johannesburg”的数据。这看上去和unordered\_map中做的事情差不多，但其实完全不同。当然，和unordered\_map一样，键名和键值都必须存储在分配于堆中的内存，这将导致对键名和键值的寻找会使缓存行无效化。但为碰撞的条目寻找一个bucket相对较快一些。实际上既然每个pair都是16字节而大多数处理器上的缓存行都是64字节，每次探测就像是在同一个缓存行上。这将急剧提高运算速度，与之相反的是unordered\_map中的链表需要在RAM中跳转以寻找余下的节点。

二次内部探测提供的缓存行优化使得dense\_hash\_map成为所有内存哈希性能测试中的赢家（至少是在我目前读过的这些中）。你应该花点时间来看看Nick Welch的文章“Hash Table Benchmarks” [\[10\]][1 4]。

![63918611gw1en6lq0giurj20le0patbe.jpg][]

图5.2

## 2.3 Kyoto Cabinet的HashDB ##

Kyoto Cabinet实现了很多数据结构，其中就有哈希表。这个哈希表HashDB虽然有一个选项可以用来把他用作代替`std::map`的内存哈希表，但其是设计用于在硬盘上持久化的。哈希表的元数据和用户数据一起用文件系统依次存储在硬盘上唯一的文件中。  
Kyoto Cabinet使用每个bucket中独立的二叉树处理碰撞。Bucket数组长度固定且不改变大小，无视负载因子的状态。这是Kyoto Cabinet的哈希表实现的主要缺陷。实际上，如果数据库创建的时候定义的bucket数组的长度低于实际需求，当条目开始碰撞的时候性能会急剧下降。

允许硬盘上的哈希表实现改变bucket数组大小是很难的。首先，其需要bucket数组和条目存储到两个不同的文件中，其大小会各自独立的增长。第二，因为调整bucket数组大小需要将键名重新哈希到新bucket数组的新位置，这需要从硬盘中读取所有条目的键名，这对于相当大的数据库来说代价太高以至于几乎不可能。避免这种重新哈希过程的一种方法是，存储哈希后键名的时候每个条目预留4或8个字节（取决于哈希是长度32还是64 bit）。因为这些麻烦事，固定长度的bucket数组更简单，而Kyoto Cabinet中采用了这个方法。

图5.3显示出文件中存储的一个HashDB的结构。我是从`calc_meta()`方法的代码，和kchashdb.h尾部HashDB类中属性的注释中得到的这个内部结构。此文件以如下几个部分组织：

*  头部有数据库所有的元数据
 *  包含数据区域中可用空间的空块池
 *  bucket数组
 *  记录（数据区域）

一条记录包含一个条目（键值对），以及此独立链的二叉树节点。这里是Record结构体：

C++

图5.4可以看到记录在硬盘上的组织。我从kchashdb.h中的`write_record()`方法中得到组织方法。注意其和Record结构体不同：保存在硬盘上的目标是最小化硬盘占用，然而结构体的目标是使记录在编程的时候用起来比较方便。图5.4的所有变量都有固定长度，除了`key`、`value`、 和`padding`，其当然是取决于数据条目中数据的尺寸。变量`left` 和`righ`t是二叉树节点的一部分，储存文件中其他记录的offset。

![63918611gw1en6lq1ed40j20le0padj7.jpg][]

图5.3

![63918611gw1en6lq2jvbqj20950a2mxn.jpg][]

图5.4如果我们要访问键名”Paris”的键值，一开始要获得相关bucket的初始记录，在本例中是bucket \#0.。然后跳转到此bucket二叉树的头节点（bucket \#0右侧的橙色箭头），其保存键名为”Johannesburg”.的数据。键名为”Paris”的数据需要通过当前节点的右侧节点来访问（”Johannesburg”记录右侧的黑色箭头）。二叉树需要一个可比较的类型来对节点分类。这里用的可比较类型是用`fold_hash()`方法将哈希过的键名缩减得到的。

C++

把数据条目和节点一起存储在单一记录中，乍一看像是设计失误，但其实是相当聪明的。为了存储一个条目的数据，总是需要保持三种不同的数据：bucket、碰撞和条目。既然bucket数组中的bucket必须顺序存储，其需要就这样存储并且没有任何该进的方法。假设我们保存的不是整型而是不能存储在bucket中的字符或可变长度字节数组，这使其必须访问此bucket数组区域之外的其他内存。这样当添加一个新条目的时候，需要即保存冲突数据结构的数据，又要保存该条目键名和键值的数据。

如果冲突和条目数据分开保存，其需要访问硬盘两次，再加上必须的对bucket的访问。如果要设置新值，其需要总计3次写入，并且写入的位置可能相差很远。这表示是在硬盘上的随机写入，这差不多是I/O的最糟糕的情况了。现在既然Kyoto Cabinet的HashDB中节点数据和条目数据存储在一起，其就可以只用一次写入写到硬盘中。当然，仍然必须访问bucket，但如果bucket数组足够小，就可以通过操作系统将其从硬盘中缓存到RAM中。如规范中”Effective Implementation of Hash Database”一节[\[17\]][1 4]声明的，Kyoto Cabinet可能采用这种方式。

然而在硬盘上用二叉树存储条目需要注意的一点是，其会降低读取速度，至少当碰撞出现的时候会是这样。实际上，因为节点和条目存储在一起，处理一个bucket中的碰撞实际上是在一个二叉树中寻找要找的条目，这可能需要大量的对硬盘的随机读取。这可以让我们理解当条目的数量超过bucket数量时Kyoto Cabinet的性能急剧下降的原因。

最后，因为所有的东西都是存在文件中，Kyoto Cabinet是自己处理内存管理，而非像unordered\_map 和dense\_hash\_map那样交给操作系统处理。FreeBlock结构体保存着和文件中空闲空间的信息，其基本上是offset和大小，如下：

C++

所有的FreeBlock实例都加载在std::set中，其可以像`fetch_free_block()`方法中那样使用std::set的upper\_bound()方法来释放内存块，从而实现“最佳拟合”的内存分配策略。当可用空间显得过分细碎或者FreeBlock池中没有空间了，文件将进行碎片整理。此碎片整理过程通过移动各条记录来减少数据库文件的整体大小。

# 3.结论 #

本文中，我展示了三个不同哈希表库的数据组织和内存访问模式。TR1的unordered\_map和SparseHash的dense\_hash\_map是在内存中的，而Kyoto Cabinet的HashDB是在硬盘上的。此三者用不同的访问处理碰撞，并对性能有不同的英雄。将bucket数据、碰撞数据和条目数据各自分开将影响性能，这是unordered\_map中出现的情况。如dense\_hash\_map及其二次内部探测那样，将碰撞数据和bucket存储在一起；或者像HashDB那样，将碰撞数据和条目数据存储在一起都可以大幅提高速度。此两者都可以提高写入速度，但将碰撞数据和bucket存储在一起可以使读取更快。

如果让我说从这些哈希表中学到的最重要的东西是什么的话，我会说在设计哈希表的数据组织的时候，首选的解决方案是将碰撞数据和bucket数据存储在一起。因为即便是在硬盘上，bucket数组和碰撞数据也会相当小，足够它们存储在RAM中，随机读取的花费将会比在硬盘上低得多。

# 4.参考文献 #

\[1\] http://en.wikipedia.org/wiki/Hash\_table  
\[2\] http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/  
\[3\] http://en.wikipedia.org/wiki/Avalanche\_effect  
\[4\] http://blog.reverberate.org/2012/01/state-of-hash-functions-2012.html  
\[5\] http://www.strchr.com/hash\_functions  
\[6\] http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633\#145633  
\[7\] http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/  
\[8\] https://sites.google.com/site/murmurhash/  
\[9\] http://google-opensource.blogspot.fr/2011/04/introducing-cityhash.html  
\[10\] http://incise.org/hash-table-benchmarks.html  
\[11\] http://preshing.com/20110603/hash-table-performance-tests  
\[12\] http://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/  
\[13\] http://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/  
\[14\] http://blog.aggregateknowledge.com/2011/11/27/big-memory-part-3-5-google-sparsehash/  
\[15\] http://gcc.gnu.org/  
\[16\] https://code.google.com/p/sparsehash/  
\[17\] http://fallabs.com/kyotocabinet/spex.html  
\[18\] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html  
\[1\\9\] http://sparsehash.googlecode.com/svn/trunk/doc/implementation.html  
\[20\] http://en.wikipedia.org/wiki/CPU\_cache

文章来源：http://blog.jobbole.com/?s=%E5%AE%9E%E7%8E%B0%E9%94%AE%E5%80%BC%E5%AF%B9%E5%AD%98%E5%82%A8

[Link 1]: http://blog.jobbole.com/
[Link 2]: http://www.jobbole.com/members/cugbabyebar
[Emmanuel Goossaert _CodeCapsule.com]: http://codecapsule.com/2012/11/07/ikvs-implementing-a-key-value-store-table-of-contents/
[Link 3]: http://group.jobbole.com/category/feedback/trans-team/
[1]: http://codecapsule.com/2012/11/07/ikvs-part-1-what-are-key-value-stores-and-why-implement-one/
[Link 4]: http://blog.jobbole.com/75844/
[2 _]: http://blog.jobbole.com/77750/
[3 _ Kyoto Cabinet_LevelDB]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/
[4 _ API]: http://blog.jobbole.com/81083/
[5 _]: http://blog.jobbole.com/81091/
[NoSQL]: http://en.wikipedia.org/wiki/NoSQL
[ACID]: http://en.wikipedia.org/wiki/ACID
[Leonard Lin]: http://randomfoo.net/2009/04/20/some-notes-on-distributed-key-stores
[Link 5]: http://en.wikipedia.org/wiki/Locality_of_reference
[Google C_]: http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml
[Alexander Sandler]: http://www.alexonlinux.com/
[Gustavo Duarte]: http://duartes.org/gustavo/blog/best-of
[The NoSQL Ecosystem]: http://www.aosabook.org/en/nosql.html
[Key Value Stores_ A Practical Overview]: http://blog.marc-seeger.de/2009/09/21/key-value-stores-a-practical-overview/
[NoSQL Patterns]: http://horicky.blogspot.com.es/2009/11/nosql-patterns.html
[NoSQL Databases]: http://nosql-database.org/
[NoSQL Data Modeling_Techniques]: http://highlyscalable.wordpress.com/2012/03/01/nosql-data-modeling-techniques/
[NoSQL databases benchmark_ Cassandra_ HBase_ MongoDB_ Riak]: http://www.networkworld.com/cgi-bin/mailto/x.cgi?pagetosend=/news/tech/2012/102212-nosql-263595.html
[Hacker News]: http://news.ycombinator.com/item?id=4733212
[1 1]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_1
[2]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_2
[22]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_22
[23]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_23
[4]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_4
[5]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_5
[6]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_6
[24]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_24
[7]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_7
[16]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_16
[18]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_18
[19]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_19
[20]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_20
[21]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_21
[8]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_8
[9]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_9
[12]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_12
[13]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_13
[17]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_17
[10]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_10
[11]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_11
[14]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_14
[15]: http://codecapsule.com/2012/12/03/implementing-a-key-value-store-part-2-using-existing-key-value-stores-as-models/#ref_15
[http_blog.knuthaugen.no_2010_03_a-brief-history-of-nosql.html]: http://blog.knuthaugen.no/2010/03/a-brief-history-of-nosql.html
[http_en.wikipedia.org_wiki_Dbm]: http://en.wikipedia.org/wiki/Dbm
[http_en.wikipedia.org_wiki_Systemantics]: http://en.wikipedia.org/wiki/Systemantics
[http_en.wikipedia.org_wiki_Berkeley_DB_Origin]: http://en.wikipedia.org/wiki/Berkeley_DB#Origin
[http_www.aosabook.org_en_bdb.html]: http://www.aosabook.org/en/bdb.html
[http_docs.oracle.com_cd_E17076_02_html_programmer_reference_intro.html]: http://docs.oracle.com/cd/E17076_02/html/programmer_reference/intro.html
[http_fallabs.com_qdbm]: http://fallabs.com/qdbm/
[http_research.google.com_people_jeff]: http://research.google.com/people/jeff/
[http_research.google.com_pubs_SanjayGhemawat.html]: http://research.google.com/pubs/SanjayGhemawat.html
[http_google-opensource.blogspot.com_2011_07_leveldb-fast-persistent-key-value-store.html]: http://google-opensource.blogspot.com/2011/07/leveldb-fast-persistent-key-value-store.html
[http_www.w3.org_TR_IndexedDB]: http://www.w3.org/TR/IndexedDB/
[http_www.igvita.com_2012_02_06_sstable-and-log-structured-storage-leveldb]: http://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/
[http_www.acunu.com_2_post_2011_04_log-file-systems-and-ssds-made-for-each-other.html]: http://www.acunu.com/2/post/2011/04/log-file-systems-and-ssds-made-for-each-other.html
[http_leveldb.googlecode.com_svn_trunk_doc_benchmark.html]: http://leveldb.googlecode.com/svn/trunk/doc/benchmark.html
[http_www.acunu.com_2_post_2011_08_benchmarking-leveldb.html]: http://www.acunu.com/2/post/2011/08/benchmarking-leveldb.html
[http_blog.creapptives.com_post_8330476086_leveldb-vs-kyoto-cabinet-my-findings]: http://blog.creapptives.com/post/8330476086/leveldb-vs-kyoto-cabinet-my-findings
[http_highscalability.com_blog_2011_8_10_leveldb-fast-and-lightweight-keyvalue-database-from-the-auth.html]: http://highscalability.com/blog/2011/8/10/leveldb-fast-and-lightweight-keyvalue-database-from-the-auth.html
[http_stackoverflow.com_questions_13054852_kyoto-cabinet-berkeley-db-hash-table-size-limitations]: http://stackoverflow.com/questions/13054852/kyoto-cabinet-berkeley-db-hash-table-size-limitations
[https_groups.google.com_forum_topic_tokyocabinet-users_Bzp4fLbmcDw_discussion]: https://groups.google.com/forum/#!topic/tokyocabinet-users/Bzp4fLbmcDw/discussion
[http_stackoverflow.com_questions_1051847_why-does-tokyo-tyrant-slow-down-exponentially-even-after-adjusting-bnum]: http://stackoverflow.com/questions/1051847/why-does-tokyo-tyrant-slow-down-exponentially-even-after-adjusting-bnum
[https_groups.google.com_forum_topic_tokyocabinet-users_1E06DFQM8mI_discussion]: https://groups.google.com/forum/#!topic/tokyocabinet-users/1E06DFQM8mI/discussion
[http_www.eecs.harvard.edu_margo]: http://www.eecs.harvard.edu/margo/
[http_www.cse.yorku.ca_oz]: http://www.cse.yorku.ca/~oz/
[http_fallabs.com_mikio_profile.html]: http://fallabs.com/mikio/profile.html
[63918611gw1elm3s7jto1j20le0cxtav.jpg]: /images/20220722/d99a9cac617a4753a359a83b6fbc9c0a.png
[1 2]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_1
[2 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_2
[3]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_3
[4 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_4
[5 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_5
[6 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_6
[7 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_7
[8 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_8
[9 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_9
[63918611gw1elm3s8jmdxj20le0pugoe.jpg]: /images/20220722/e04514f98c894fc38684710cc1dcad4c.png
[63918611gw1elm3s9i5lyj20le0p0diw.jpg]: /images/20220722/76ed80d00c0a4fa293e9698e3e954768.png
[10 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_10
[11 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_11
[12 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_12
[13 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_13
[14 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_14
[15 1]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/#ref_15
[http_work.tinou.com_2011_04_memcached-for-dummies.html]: http://work.tinou.com/2011/04/memcached-for-dummies.html
[http_code.google.com_p_memcached_wiki_NewUserInternals]: http://code.google.com/p/memcached/wiki/NewUserInternals
[http_horicky.blogspot.com_2012_04_mongodb-architecture.html]: http://horicky.blogspot.com/2012/04/mongodb-architecture.html
[http_horicky.blogspot.com_2012_07_couchbase-architecture.html]: http://horicky.blogspot.com/2012/07/couchbase-architecture.html
[http_www.sqlite.org_arch.html]: http://www.sqlite.org/arch.html
[http_redis.io_documentation]: http://redis.io/documentation
[http_doxygen.org]: http://codecapsule.com/2012/12/30/implementing-a-key-value-store-part-3-comparative-analysis-of-the-architectures-of-kyoto-cabinet-and-leveldb/:/doxygen.org
[http_www.stack.nl_dimitri_doxygen_config.html]: http://www.stack.nl/~dimitri/doxygen/config.html
[http_leveldb.googlecode.com_svn_trunk_doc_index.html]: http://leveldb.googlecode.com/svn/trunk/doc/index.html
[http_redis.io_topics_internals-sds]: http://redis.io/topics/internals-sds
[http_news.ycombinator.com_item_id_3883310]: http://news.ycombinator.com/item?id=3883310
[http_www.briancarpio.com_2012_05_03_mongodb-memory-management]: http://www.briancarpio.com/2012/05/03/mongodb-memory-management/
[http_leveldb.googlecode.com_svn_trunk_doc_impl.html]: http://leveldb.googlecode.com/svn/trunk/doc/impl.html
[http_oldblog.antirez.com_post_everything-about-redis-24.html]: http://oldblog.antirez.com/post/everything-about-redis-24.html
[1 3]: http://blog.jobbole.com/81083/#ref
[7 2]: http://blog.jobbole.com/81083/#ref"
[63918611gw1en6lpyukytj20le08rt9h.jpg]: /images/20220722/1598209bb1cc467c94c899df039a71a2.png
[1 4]: http://blog.jobbole.com/81091/#ref
[8 2]: http://blog.jobbole.com/81091/#ref"
[63918611gw1en6lpzics7j20le0qcad9.jpg]: /images/20220722/669a2e3001564988ad5ae502a3b53fcc.png
[63918611gw1en6lq0giurj20le0patbe.jpg]: /images/20220722/4c27058a45db4b0a81f862da3b9792de.png
[63918611gw1en6lq1ed40j20le0padj7.jpg]: /images/20220722/e95d9f8166cd4acbb83f6e1f4b11b71d.png
[63918611gw1en6lq2jvbqj20950a2mxn.jpg]: /images/20220722/f1e934791d514427a9ebed20b028410b.png