键/值存储通常有一个简单的数据模型：一个map/dictionary，同意客户按键来存放和请求数值。

除了数据模型和API。现代键/值存储倾向于高扩展性而非一致性，因此它们中的大多数也省略了富ad-hoc查询和分析功能（尤其是联接和聚合操作被取消）。通常，可存储的键的长度被限制为一定的字节数，而在值上的限制较少（[ Ipp09 ]，[ Nor09 ]）。

在免费和开源键/值存储的巨大多样性中。Project Voldemort将被进一步检视。

本章最后，一些其它著名的键/值存储将简要地评判。

一次操作仅限于一个键/值对，所以更新操作仅限于单键，不同意交叉引用到其它的键/值对或操作跨越多个键/值对。此外，Dynamo不支持分层命名空间（如文件夹服务或文件系统）（[ DHJ+07。页206，209 ]）。

它不提供不论什么隔离保证（[ DHJ+07，206页]）。DeCandia等人觉得，给定Amazon的背景和需求（特别是高可用性和可扩展性）。一个同步的复制模式是不可实现的。

作为替代，他们选择了一种乐观的复制模式。

这种特点将复制和写操作的可能性置于后台。即使在断开的副本出现时（由于网络或机器故障）。所以，Dynamo被设计为“总是可写的（即一个高度可写的数据存储）”，必须在读时解决冲突。

此外，DeCandia等人觉得一个数据库仅仅能运行简单的冲突解决策略。因此一个client应用程序更适合这项任务，由于它“知道数据模式”且“能够决定一种最适合客户体验的冲突解决方法”。假设应用开发者不想实现这种业务逻辑特化的协调策略，Dynamo还提供了简单的可直接使用的策略。如“最后的写胜利”，一个基于时间戳的协调（參见[ DHJ+07，页207-208和214）。

DeCandia等人觉得以原始形式使用一致性哈希有两个缺点：首先，存储主机和数据项的环上随机映射导致数据和负载的不平衡分布。其次，一致性哈希算法相等地对待每一个存储节点且不考虑其硬件资源。为克服这两个困难。Dynamo应用了虚拟节点的概念，即对每一个存储主机将多个虚拟节点哈希到环上（如3.2.1描写叙述），且每一个物理节点的虚拟节点数目通常考虑存储节点的硬件能力（即每一个物理节点资源越多则虚拟节点越多，[ DHJ+07。页209–210 ]）。

负责存储键k的元组的存储节点也负责副本的版本号更新，以顺时针方向对键k的元组的N-1个后继者。存在一个节点列表——称为偏好列表——为Dynamo中每一个要被存储的键k确定。这个列表包含多于N个节点，由于N个连续的虚拟节点可能映射到小于N个不同的物理节点（如3.2.1对一致性哈希的讨论）。

随后的读操作因此可能从不同的副本节点返回不同的版本号。在Amazon的平台副本之间的更新传播时间是有限的，假设没有发生错误。但在某些故障场景下，“更新可能在一个延长的时间段内无法到达全部副本”（[ DHJ+07，210页]）。

由于数据存储无法调和这些并行版本号。仅仅有client应用程序包括有关其数据结构和语义的知识，能够解决版本号冲突并从多个相互冲突的版本号中调和有效版本号（语义调和）。因此。使用Dynamo的client应用程序必须注意这个，必须“显式地确认同一数据的多个版本号的可能性（为了不失去不论什么更新）”（[ DHJ+07，210页]）。

这个上下文包含一个他们已经读过的数据的向量时钟，所以Dynamo知道更新哪一个版本号。且能够正确地设置更新的数据项的向量时钟。假设并发版本号的数据项出现，Dynamo将在读请求返回的上下文信息中把他们传输给client。

在client向这种数据项发出一个更新之前，它必须调和并发版本号为一个有效版本号。

由此产生的向量时钟将是（[ Sx。2 ]），于是一个[ SX，1 ]和[ Sx，2 ]间的暂时排序可被确定，由于后者显然比前者晚（同存储主机、提升版本号号）。由于[ Sx，1 ]仅仅有一个后继（[ Sx，2 ]）。它不再是暂时推理所需的。能够从向量时钟中删除。

于是client想要更新一个比节点Sy当前已知的版本号更近的版本号，这会被接受由于Dynamo的“总是可写”属性。相同的事也发生在还有一个client已读到D2且公布一个由存储主机Sz处理的更新。Sz当前不知道D2。这导致了版本号D4与向量时钟（[ Sx。2 ]。[Sz。1 ]）。

假设这个更新请求再次被节点Sx处理。这会推动向量时钟中的版本号号变为（[ Sx，3 ]，[ Sy，1 ]，[Sz。1 ]）。如图4.2所看到的。

为了接触某个节点，client应用程序使用或者通用的负载均衡路由，或者一个client库，其反映Dynamo的分区模式且能通过计算确定需接触的存储主机。第一个节点选择方法的优势是。它能够保持不关注Dynamo的特定代码。第二个方法降低了延时。由于不须要接触负载均衡器，从而降低了一次网络跳数（[ DHJ+07，211页）。

这是基于给定键的包括带优先顺序的需接触存储主机的偏好列表。当一个节点接收到client请求时，它将依据偏好列表中的顺序转发到存储主机上（假设节点本身在优先列表中。转发自然变得不必要）。一旦发生读或更新请求。最先N个健康的节点将被考虑（不可存取或宕机的节点仅仅是跳过。參见[ DHJ+07，211页]）。

还有一方面“低的W和R值能够添加不一致的风险。由于写请求会被觉得是成功的并返回给client，即使他们没有被大部分副本处理过”。此外，持久性在一段时间内仍是脆弱的，当写请求完毕但更新的版本号仅仅被传播到少数几个节点。DeCandia等人评论“Dynamo的主要长处是，它的client应用程序能够调整N、R和W以实现他们期望的性能、可用性和持久性水平”（[ DHJ+07，214页]）。（考虑性能、持久性、一致性和可用性。典型的适合亚马逊SLAs的配置是N＝3。R＝2，W = 2，參见[ DHJ+07，215页]）。

假设这些节点用不同的版本号回复则为冲突（通过向量时钟推理观察到），它将向请求的client返回并发版本号（[ DHJ+07，212页]）。

这样做，成员的变化被扩散并建立一个终于一致的成员视图。

为了这个目的，为每一个虚拟节点选择一个令牌，即一个决定一致性哈希环上虚拟节点位置的值。该组的令牌被持久化到物理节点的磁盘上，且通过与传播成员变化时同样的Gossip基础协议来传播，如前一段看到的（參见[ DHJ+07。页212 ]）。

每一个物理节点的虚拟节点数被选择与物理节点的硬件资源成比例（[ DHJ+07，210页]）。

当某个节点通过成员扩展协议来知道一个近期加入的节点，并确定它不再负责某部分的键。它将这些键传输到加入的节点。

当一个节点正在删除，键以一个相反的过程被又一次分配（[ DHJ+07，213页]）。

在Amazon的实验和实践表明“策略3是有利的，更easy部署”，以及更高效和保存成员信息的空间需求最少。据DeCandia等人，这个策略基本的优点是（[ DHJ+07，217页]）： 

他们開始工作，假设一个节点在它负责的数据项的写操作中是可訪问的。在这样的情况下，写协调器将更新拷贝到一个不同的节点。其通常对此数据项不承担不论什么责任（以确保N个节点上的持久性）。在这个复制请求中，包括更新请求原本被定向到的节点的标识符作为一个提示。当这个节点正在恢复和再次可用，它将接收到更新；已接收到作为一个替代的更新的节点，能够从本地数据库删除它（[ DHJ+07，212页 ]）。

“后来确定显式的节点加入和离开的方法能消除全局故障视图的须要。

这是由于永久性的节点加入和移除通过显式的加入/离开方法被通知到节点，且暂时节点故障被个别节点检測到，当他们不能与其它节点通信（当转发请求时）”，DeCandia等人总结（[ DHJ+07，213页]）。

Dynamo使用Merkle树来有效地检測副本之间的不一致性。并确定需进行同步的数据。

“Merkle树是一种哈希树，其叶节点是独立键的哈希值。树中较高层的父节点是他们各自孩子的哈希”，DeCandia等人阐明。这同意对不一致性的高效检查，两个节点通过分层比較其Merkle树的哈希值来确定差异：首先，通过检查该树的根节点，其次——假设检測到不一致性——通过检測其子节点，以此类推。副本同步协议仅仅须要非常少的网络带宽。由于仅仅有哈希值必须在网络上传输。它也能够高速操作由于使用树遍历的分治法来比較数据。Dynamo中，存储节点为每一个键范围（即在一致性哈希环上的两个存储节点之间的范围）维护一个Merkle树。其负责且能够将这种Merkle树与负责同样键范围的其它副本的Merkle树做比較。DeCandia等人觉得这个方案的缺陷是，当一个节点增加或离开系统，由于键范围变化一些Merkle树会失效（[ DHJ+07，212页]）。

它提供了一个包含下面功能的API：（[ K+10b ]）：

然而。键/值存储这样的简单的概念提供了一些优势（[ K+10b ]）：

相同地，智能路由（即确定管理包括请求数据的分区的节点）可被数据存储透明地提供，假设网络层被放置在路由层之上；假设这些层被干扰。则应用程序能够自己来做路由以降低网络跳数带来的延迟。

Project Voldemort的设计文档建议使用数据分区和大缓存来降低磁盘I/O造成的性能瓶颈。特别是磁盘的寻道时间和低磁盘缓存效率。

因此Project Voldemort——如同Dynamo——使用带副本数据的一致性哈希来容忍存储节点停机。

缺点是，client应用程序必须实现冲突解决逻辑，而这在2PC和Paxos风格的一致性协议是不必要的。

Project Voldemort已经包括下面数据结构和格式：

它被觉得非常好地与多种编程语言建立映射。由于它提供了常见数据类型（字符串，数字，liat，map，对象），没有对象的关系映射失配的问题。还有一方面，JSON内部是无模式的，这相应用处理JSON格式的数据会产生一些问题（如数据存储希望JSON值的基本类型检查）。每一个JSON文件能够包括一个单独的模式定义，但考虑到在数据存储中大量数据共享同样的结构这会非常浪费的。

Project Voldemort因此提供指定键和值的数据格式的可能性，如表4.3所看到的。

这对批处理操作特别实用。如数据作为一个总体上传时的插入或更新大量数据造成索引重建，或在一块小空间内低效插入导致的索引碎片。

在Project Voldemort中大量的数据能够被作为总体插入，创建离线索引的特征使线上系统从全量索引重建或索引碎片中解脱。

内存页周期性地刷新到磁盘，“这会留下一个数据丢失的漏洞”。如Hoff评论的（[ Hof09a ]）。还有一方面，Tokyo Cabinet同意使用LZW算法压缩页。能够达到非常好的压缩比（见比如[ Lin09 ]）。Tokyo Cabinet自己主动对数据分区，因此使用类似MySQL的策略进行复制。

除了通过键查找，假设键是排序的它能够匹配键的前缀或范围。值得一提的是事务特性，Tokyo Cabinet提供预写式日志（注：WAL）和影子分页。Tokyo套装被积极开发，文档良好，并被广泛觉得是高性能的：100万条记录能够在0.7秒内存储（使用哈希表的引擎），或1.6秒内（使用B树），依据North（參见[ Nor09 ]，[ Ipp09 ]，[ See09 ]，[ Lin09 ]。[ Hof09a ]）。

Scalaris使用改编版的chord服务（[ SMK+01 ]）来暴露一个分布式哈希表给client。

由于它以字典序储存键，前缀的范围查询是可能的。

与其它键/值存储相比Scalaris具有严格的一致性模型，提供对称的副本，并同意复杂的查询（通过编程语言库）。它也为并发事务保证了ACID特性，通过实现一个Paxos一致性协议的适用版本号（[ Lam98 ]）。

如memcached，Scalaris是纯内存的键/值存储（[ Nor09 ]、[ Jon09 ]）。