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

本文是《实现键值对存储》系列译文的第二篇

原文来自Emmanuel
Goossaert (CodeCapsule.com)

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

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

1. 不又一次发明轮子

键值对存储已经被人们唱好至少30年了[1]。最著名的一个项目是DBM。Kenneth
Thompson为Unix第七版编写的最早的数据库管理器并在1979年公布[2]。project师们遇到了和这些数据库系统相关的一些问题，并选择或放弃了各种设计和数据结构的想法。

对实际生活中的问题进行试验并从中学习。

假设不考虑他们的工作并从头開始是非常愚蠢的，仅仅会反复他们之前所犯过的错误。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] 和
Ozan Yigit [23] 在加州大学伯克利分校的时候编写的。这个项目后来被Oracle获得，并由其继续开发。

Berkeley DB最初是由C实现的。而且如今仍然是仅仅用C。

其通过增量过程开发的。就是说在每一个主版本号添加新的功能。Berkeley DB从一个简单的键值对存储，进化到管理并行訪问、事务及复原、及同步功能[4]。

Berkeley
DB的使用很广泛。有着数亿已部署的拷贝[5]，这是能够相信其架构及其可靠的证据。

关于其设计的很多其它信息能够在“Berkeley
DB Programmer’s Reference Guide”[6] 的介绍和“The
Architecture of Open Source Applications, Volume 1” [5]的开头中找到。

Kyoto Cabinet

Kyoto Cabinet在2009年由Mikio Hirabayashi [24] 引进。其如今仍在积极进化中。Kyoto
Cabinet是同一个作者的其他键值对存储：Tokyo Cabinet (2007公布) 和QDBM (2003公布, 2000開始)的继任者。QDBM打算作为DBM的高性能继任者[7]。

Kyoto
Cabinet尤其有意思。由于它有着DBM的纯正血统，而且它的作者在键值对存储方向工作12年了。在浸淫三个键值对存储这么多年之后。没有理由怀疑作者有着对结构需求的坚实理解，以及随之的对性能瓶颈的成因的极强认识。

Kyoto Cabinet是由C++实现的。并实现了一个哈希表，一个B+树。以及其它一些深奥的数据结构。

其相同提供了出色的性能[16]。然而。因其内部參数的原因，似乎有些性能问题。的确，非常多人报道说仅仅要数据条目的数量保持在某一特定的阈值（正比于桶数组大小，其由创建数据库文件时的參数所确定）下面，性能就非常好。一旦超过这个阈值，性能似乎急剧下降[18][19]。Tokyo
Cabinet[20] [21] 中也有同样的问题。这表示假设某项目的需求在数据库使用的时候改变。你可能会遇到严重的问题。而我们都知道，软件中的改变是如此的频繁。

LevelDB

LevelDB是由Google职员Jeffrey Dean [8] 和
Sanjay Ghemawat [9] 开发。他们为Google传说中的基础建设项目MapReduce和BigTable工作。

基于Dean和Ghemawat在在Google工作时获得的大规模问题上的经验，他们非常有可能非常了解他们正在做的东西。和大多数键值对存储项目相比，LevelDB有一个非常有意思的不同点就是它不用哈希表或者B-树作为底层数据结构。而是基于一个日志结构的合并树[12]。

LSM结构据说是为SSD硬盘优化的[13]。你能够在这个博客High
Scalability blog [17]找到成吨的关于LevelDB的信息。

LevelDB是由C++实现。2011年公布。并设计作为高级存储系统的一部分[10]。

IndexedDB
HTML5 API在Chrome将来版本号的实现将使用LevelDB [10] [11]。其性能决定于特定的工作负载，就像作者提供的基准測试中显示的那样[14]。然而，Andy
Twigg在Acunu的另外一个基于商用SSD的基准測试显示出。假设数据的条数超过1e6（1百万），并向1e9（10亿）前进的时候。性能将会显著下降[15]。因此似乎LevelDB似乎并非重工作负载或像实际后端项目需求那样的大数据库最好的选择。

但这事实上并不重要，对于我来说，LevelDB最好的部分不是其性能而是其架构。看它的源码和东西组织的方式，那是纯粹的美。

全部的东西都非常清晰、简单、条理分明。訪问LevelDB的源码并把它作为榜样是创建出色代码的绝好机遇。

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

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

4. 參考文献

[1] http://blog.knuthaugen.no/2010/03/a-brief-history-of-nosql.html
[2] http://en.wikipedia.org/wiki/Dbm
[3] http://en.wikipedia.org/wiki/Systemantics
[4] http://en.wikipedia.org/wiki/Berkeley_DB#Origin
[5] http://www.aosabook.org/en/bdb.html
[6] http://docs.oracle.com/cd/E17076_02/html/programmer_reference/intro.html
[7] http://fallabs.com/qdbm/
[8] http://research.google.com/people/jeff/
[9] http://research.google.com/pubs/SanjayGhemawat.html
[10] http://google-opensource.blogspot.com/2011/07/leveldb-fast-persistent-key-value-store.html
[11] http://www.w3.org/TR/IndexedDB/
[12] 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
[14] http://leveldb.googlecode.com/svn/trunk/doc/benchmark.html
[15] http://www.acunu.com/2/post/2011/08/benchmarking-leveldb.html
[16] 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
[18] http://stackoverflow.com/questions/13054852/kyoto-cabinet-berkeley-db-hash-table-size-limitations
[19] 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
[21] https://groups.google.com/forum/#!topic/tokyocabinet-users/1E06DFQM8mI/discussion
[22] http://www.eecs.harvard.edu/margo/
[23] http://www.cse.yorku.ca/~oz/
[24] http://fallabs.com/mikio/profile.html