NoSQL学习——键值对数据库
# 键值对数据模型
键值对数据模型非常简单，即通过类似映射的方式读写一个键对应的数据。键值对数据库的主要的逻辑操作是put(key, value)和get(key)->value。据。
# 键
键通常根据应用的语义生成，例如使用表示对象的id等。需要注意的是，键必须确保独一性，例如使用独一性的字符串、自增整数、无碰撞的哈希值等。
# 值
在值上，键值对数据库依据支持的类型分为纯k-v型和复合类型，前者只支持由客户端进行解释的数据，或者则可以支持复杂的数据类型。
# Memcached
Memcached是非常典型的内存型键值数据库。其创建的动机是通过在内存中缓存数据来减少磁盘的读写，从而解决磁盘读写瓶颈以提升系统的整体性能。
在实现上，Memcached使用了全局哈希表来实现分布在多个节点上的实例之间的统一，由此实现了分布式的缓存存储，提升了系统的可用性。由于Memcached使用内存作为存储，持久性不是其考量；另外由于其作用是缓存，系统始终存在缓存失效的情况，因此要保证缓存与磁盘数据的一致性。一种方法是在更新数据时先失效缓存再设置缓存，另一种方法是设置缓存的失效时间，后者通常适用于写间隔较为稳定的场景。
由于Memcached是分布式运行的，哈希表中的键存储在哪个实例中就成为了需要解决的问题。一种方法是通过客户端的划分算法找到指定的服务器。最简单的划分算法是，将实例按照其内存的大小划分为一个或多个桶（例如512M为一个桶，实例的内存为1G时，其包含两个桶），然后用哈希值与桶数量进行模运算。
# Dynamo
在后来开发的数据库中，Amazon的Dynamo作为一种新型的键值数据库得到了一定的关注。Dynamo采用一种同级节点（peer-to-peer）的方式组织，通过gossip协议在节点之间建立通信，检测错误。在划分键时，使用一致性哈希，避免了求余算法增加桶导致缓存失效/重构的问题，保证了扩展性。在可用性上，通过向量钟实现了版本更迭，避免了版本号大小增加。在处理临时的错误时，使用Sloppy Quorum（一种处理节点错误时的写操作的方法）提供了较高的可用性和持久性保证。处理永久错误时，使用默克尔树逆熵算法。
# 一致性哈希（Consistent Hash）算法
一致性哈希算法采用类似MongoDB分片的方法，通过预定义的哈希值范围避免大量地重构键值对的过程。一致性哈希的一个特性是在哈希表尺寸变化时，平均下来仅需要重构个键的分布，其中k是键的数量，n是存储的槽的数量。要实现这一特性，一种常见的做法是将哈希值按照范围组合，形成一个环；而对于每一个键，其哈希值都唯一地分布在一个范围内。在分布式环境上，这些范围就可以分布到不同的节点上。
在Dynamo中，一致性哈希使用MD5实现，共有128bit表示其数值，因此有个存储空间，能够满足绝大多数存储。当哈希发生碰撞时，可能采用开放寻址的方法解决。Dynamo的每个结点都是一部分哈希值的协调者（coordinator），即每个哈希值由一个节点支持读写。在进行写操作时，Dynamo会设置一个复制因子N，在写入到协调者节点之外写入N-1个复制节点，这些节点通常是环的下面几个节点。
例如，有一个环[0, 99]被分为4个左开右闭的范围(0,25]、(25,50]、(50,75]、(75,0]，如果有个键"Anderson"被哈希到31，则其从属于管理(25,50]的节点，读写由该协调者处理。
这些范围的管理节点被称为虚拟节点。在实际的集群上，由于机器的异构性，不同物理节点实际的性能存在差异，则可以将虚拟节点不等量地分配到不同的物理节点上，如上例中，有三个物理节点n0、n1和n2，其中n0性能较好，则其可以承担两个虚拟节点的协调工作，如(25, 50]和(75, 0]。
在新增节点时，新增的节点只会导致极小的一部分数据被重新配置。例如在上例中，添加一个新节点(0,10]，则节点(0,25]会变为(10,25]，这样只有(0,10]内的值会被重新分布到新的协调者节点和复制节点上。
# 复制和错误处理
Dynamo的复制模式不遵循主从模式，即写操作从主节点扩散到从节点，而是采用一种并行写+认可写成功节点数量的机制。为了避免并行写时因到达不同节点的操作不一致导致数据不具有一致性的问题，带有时间戳的写操作就成为一种良好的选择。通过忽略比当前最新数据的时间戳更早的操作，实现最终一致性。
写操作在集群上的承认被称为Quorum，在如MongoDB在内的分布式数据库中，假设写操作需要使用N个节点中的W个，读取时使用R个节点。这时Quorum可以考虑的方式是根据多个值的时间戳取最近时间戳的数据，另外要确保写入的节点数量占大多数并且读和写的节点数量总和大于N，从而保证有交叉的节点，使得最新的数据能够被返回。
在Danymo中，上述的时间戳概念被转化为了名为向量钟的机制（vector clock），能够处理分支矛盾并减少时间戳占用空间大小。Quorum则由sloppy quorum（马虎共识）和hinted handoff（提示转交）代替，后者的写可用性更佳而一致性不如前者，但能够达成最终一致性。
Dynamo中所有节点都可以处理读写请求，它们能够通过统一的哈希算法计算哈希值，知道彼此之间的范围token和错误情况，并附带有一个PreferenceList用于记录备份节点。当收到不属于自己管辖的数据时，节点会将数据转发到协调者节点或其备份节点上。较少的情况下，如果所有备份节点都不可用，则该节点可能自行处理此数值。
在处理这些数据时，由于分布式节点存活情况不一致，可能存在数据分叉的情况，即一个数据被不同节点处理后存在矛盾。这时就会用到向量钟，向量钟是一个由(node, counter)组成的列表，一个向量钟记录了一条数据被哪些节点处理过多少次，这种记录方式能够将版本尺寸控制在一个常数级的与节点数量相关且非常小的尺寸。另外，还可以通过裁剪机制移除旧的、无效的节点项，从而缩小其尺寸。
Dynamo在进行每一次写操作时，都要求收到的数据附带上读操作得到的向量钟，以判断当前数据来自哪个分支、更新哪个分支，以及是否存在矛盾。通过检测向量钟中的版本号可以确定，所有版本号都小于等于当前版本号的向量钟是没有矛盾的，而当其中一些值大于当前版本号时，则存在分支和矛盾。当矛盾存在时，Dynamo会返回所有矛盾的叶子节点（将向量钟记录理解为一个存在分化的有向图），由客户端决定保留哪份数据，附带新的向量钟并更新。
Dynamo的Sloppy Quorum指读过程的节点中可能包含没有参与写过程的节点，而这些节点将使用提示转交的方法处理数据。一种典型的场景是，一个写操作的复制节点在写操作发生时不在集群中，转而由E代理参与其中。此时，E就会在C返回集群后，将写操作转交给C。此时如果B下线而有新的读操作产生，则Dynamo就会将C和D中的数据返回，由客户端如处理向量钟矛盾那样处理这两个数据，由此实现最终一致性。
因此，尽管Dynamo的设计中这些机制能够确保一定的一致性，但最终一致性依赖于客户端对于矛盾数据的判断。Dynamo更加适用于需要高可用性但对一致性要求不那么严格的场景。
# 总结
本章中我们探索了键值对数据库以及两个典型的例子Memcached和Dynamo的一些实现原理。