具备高可靠性及可扩展性的海量数据存储对互联网公司来说是一个巨大的挑战，传统的数据库往往很难满足该需求，并且很多时候对于特定的系统绝大部分的检索都是基于主键的的查询，在这种情况下使用关系型数据库将使得效率低下，并且扩展也将成为未来很大的难题。在这样的情况下，使用Key-value存储将会是一个很好的选择。
它被广泛应用于缓存，搜索引擎等等领域。
???????? 根据以上的描述，一个好的key-value存储需要满足哪些条件呢？
l? Availability可用性
l? Scalability可扩展性
l? Failover故障恢复
l? Performance高性能
简单来说，就是数据不能丢失，服务不能中断，能对故障进行感知并能自动恢复，读写性能极高。
这一部分比较大，以后会另开主题写
不少nosql的产品采用的是单文件存储的，数据量大以后肯定会遇到性能瓶颈，这一点无需多说，我想强调的是，采用多文件存储数据优点还是非常多的，不过也需要注意，操作系统对于能够打开的文件数目是由限制的，貌似Linux好像是1024（待确认），
为了支持更快的写操作，数据文件的写操作只支持append，这个就不多说了，相信大部分的海量存储设计都是这样的。因此，更新操作等价于写操作，不过在写的时候第一步判断写到树的哪个位置时肯定会定位到树已有的节点上，这样可以使得这次写失效或者直接覆盖。
这样存在一个问题，就是对于失效的数据（比如更新过的数据）如何处理，比较好的办法是启动独立线程定时或手动进行清理，请注意，这是一个非常巨大的过程，它将耗光你的CPU和I/O，因为要进行频繁计算和数据迁移。
B Tree家族这一数据结构被广泛的运用于数据库索引，如Mssql的B+tree，oracle的B-tree，熟悉索引的朋友一定很清楚，这种数据结构非常适合作为我们的Key-value存储的数据结构.关于B+tree，可以参见下图：它是一个多路搜索树, 数据存储在叶子节点上，非叶子节点作为叶子节点的索引，加速数据的查找，而叶子节点是一个有序的链表，每次搜索都会到达叶子节点才会结束，插入新数据可能会引起节点的分裂。
在本篇文章中，你需要知道，上层的节点成为IN（Internal Node）,它持有其他节点的引用，叶子节点的上层是（Bottom Internal Node），而叶子节点则是存储数据的节点。
??
图片来自：http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx
这部分是纯粹的数据结构，就不多说了，如果想深入了解的话可以看看这篇论文《The Ubiquitous B-Tree》
因为系统要具备高扩展性，因此，增加删除机器是频繁的操作，如何将数据均匀分散到集群中呢？比较常用的办法是hash取模的办法，但是这样一来，增加机器的瞬间，按照之前的hash取模方式，数据无法读取，这意味着需要对数据进行迁移，等待机器预热，这是很不好的办法。
目前比较公认的解决办法就是一致性哈希(consistent hashing)
首先按照机器的hash进行顺时针分布，如图，目前有5台机器，如果有一个读写请求，那么hash该key值得的一个hash值，定位到环上，如果没有定位到具体的机器，那么按照顺时针查找，找到的第一个机器就是目标节点。
如果需要新增机器，增加过程为，首先hash新机器得到其位置，加入新机器F，这时访问策略不变，那么按照之前的策略，如果hash到C-F之间的数据就无法找到了，但是这样一来影响就局限于C-F之间，不象之前需要整体迁移了。
最后，为了降低增加机器所带来的影响，我们可以为其增加虚拟节点（virtual nodes）。这样的话服务器在环上的分布就比较均匀，这样多个虚拟节点将对应一个我们的物理节点，增加机器所受到的影响也会变得最小。
为了达到高可用性和数据不丢失，我们需要通过复制将数据备份到多台机器，replication的实现机制一般是通过Master与replica之间的TCP/IP连接，然后根据相应的一致性策略将数据分发到replica上，这里的一致性策略主要包括两项：
1.???????? replica能够延迟master的时间，这个的意思就是说，在这个时间内更新的数据，replica可能是看不到的。例如你设置的一致性时间是3s，那么在某个特定的时刻，replica上的数据实际上可能是master3s以前的snapshot。
2.???????? master事务提交返回之前是否需要得到replica的确认。为了尽量保证数据不丢失，master需要得到一定数量的replica确认数据更新成功之后才能提交事务。
关于数据可靠性和性能之间，是需要进行折衷的，很显然，越是高的数据保障，那么性能肯定会受到影响。在这样的情况下，需要对上层的应用进行分析，看是否允许丢失一部分数据。
另外，还有一个问题就是，数据的同步是采用master分发还是replica定时请求的问题，两者各有优缺点，前者会在replica较多的情况下遇到瓶颈，而后者可能会有一些延迟。多级同步的方式能在一定程度上解决这个问题，即master向某些机器同步，而这些机器向其他机器同步。
当然，master管理写请求而replica管理读请求，至于如何决定读写请求的分发，我们可以使用monitor节点，由它来作为读写的入口， 如下图，然后Monitor管理集群的状态和生命周期，例如Master fail后，monitor将收到事件，它将发起一次选举选出新的Master，一般的选举算法就是在集群中寻找最后一次更新的节点，因为往往它的数据是最新。还有就是在有新的机器加入集群的情况下，Monitor会告诉新机器集群内的master是谁，replica机器才能与master取得连接同步数据。
<!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Visio.Drawing.11" ShapeID="_x0000_i1025" DrawAspect="Content" ObjectID="_1344072934"> </o:OLEObject> </xml><![endif]-->
使用Monitor的Master-replica集群
?
当然，自从有了ZooKeeper，这种监控和协同的脏活累活就可以都交给它了，利用ZooKeeper管理集群内节点的健康状况具备很大的便利，毕竟，上面这个办法的架构存在单点问题，最后肯定Monitor会拖集群的后腿。所以用ZooKeeper管理集群并且针对不同的事件作出响应。下面是一个示意图：
<!--[if gte mso 9]><xml> <o:OLEObject Type="Embed" ProgID="Visio.Drawing.11" ShapeID="_x0000_i1026" DrawAspect="Content" ObjectID="_1344072935"> </o:OLEObject> </xml><![endif]-->
用ZooKeeper管理集群
最后，关于事务提交时的处理策略也值得注意，你需要为master和replica都指定.一般情况下，我们需要在减少频繁的I/O操作和数据保障性方面进行折衷，以下提交策略可选：
1.???????? 在事务提交时将数据由内存刷到硬盘，这样数据具有最高的保障，但是你需要等待昂贵的I/O操作。
2.???????? 在事务提交时将数据刷到操作系统buffer中，然后由操作系统自己决定何时刷到硬盘。这样可以在虚拟机挂了的情况下保证数据不丢失，但是不能hardware failture
3.???????? 在事务提交时数据仍然维持在内存中，而在存储系统比较闲的时候进行持久到硬盘的操作，或在内存不够用的情况下进行写磁盘操作。
这两个动作是key-value存储系统最核心的两个操作，因此在设计上需要做更多的考虑。
下面是一种写操作的过程：
1.???????? 执行tree搜索以定位插入数据所在的位置
2.???????? 锁定该位置的父节点
3.???????? 创建新的叶子节点
4.???????? 将叶子节点写入。这个写操作发生在内存中，并且返回一个number它决定了叶子节点写到硬盘的位置
5.???????? 修改父节点指向该叶子节点的引用。该父节点既持有指向内存的叶子节点的引用又持有磁盘的位置的number。
6.???????? 标记该父节点为dirty(意味着内存中的版本没有出现在磁盘中)
7.???????? 解锁该父节点
请注意，很明显，这个写操作完全发生在内存中，那么何时将数据同步到磁盘呢？这就是后面要讲的checkpoint。通过它定时的将内存中的脏数据写到硬盘。
读操作就简单很多了，搜索tree，定位到叶子节点，取出数据就行了，当然还有一些包括为缓存服务的操作就不细讲了（比如，为每个节点计数，每次对该节点的访问都使得其+1，这样在缓存evict的时候就很有用了）
上面所说的写操作在内存中并不会影响到读操作，因为，为了加快读操作，我们会在启动时预加载硬盘数据文件的内容到内存，由于只有叶子节点存储数据，因此我们需要根据加载的叶子节点还原整棵B+tree，毫无疑问这是一个耗时的操作，但是却是值得的。
这块比较大，这里只重点讲一下以什么数据结构存取的问题。
首先需要解决的是，存储对象的问题，很显然，我们都有存取对象的需求，那么如何将对象转换为我们的底层存储格式呢？一般的办法有序列化，Json，XML之类，下面依次讲一下优缺点：
1.?????? 序列化。可能是比较简单易实现的办法，但是空间占用过大
2.?????? Json和XML都差不多，存储格式比较可读一点，解析和转换比较方便，不过对于数据量大的情况还是不推荐。
3.?????? 字符串或者字节数组。我们按照一定的约定将对象拼成字符串，或者一次将对象的属性写入到字节数组，读取时按照相同的顺序解析即可，比较好的办法是定义一个接口，然后由客户端去实现对象字符串之间转换顺序的方法。这个比较推荐。
还有一些序列化的工具值得推荐，比如hadoop下的avro。
和普通的关系型数据库一样，key-value也可以有自己的checkpoint，一般情况，checkpoint是为了减少数据恢复所需要的时间.在检查点到来时，按照之前的设计，它会将所有的dirty Internal Node写入log，这样会存在一个问题，大多数情况下，checkpoint会把整棵树写到log,解决问题的办法是我们采用增量的办法进行log，例如，如果有a和b加入到某个父节点。那么此时如果进行checkpoint时我们需要首先写一个完整的IN引用，并且记录对其进行的操作，add a，add b，这些操作记录在一个list中，当list变得过大以后我们又重新写一个完整的IN节点。
这一部分只针对按照顺序写并且仅append的情况，为了减少I/O操作，无效数据仅仅被标记为delete且删除内存中对应的树的叶节点而不进行物理的删除，那么长期下去，失效数据会很多，这时候需要进行清理，一般的策略就是，当失效数据在文件中所占比例达到一定程度以后，执行清除操作。
1.???????? 首先根据预先存储的记录信息判断哪些文件需要进行清理操作。
2.???????? 扫描文件，找到仍然active的数据，拷贝到新的文件，扫描完成后删除此文件。
请注意，在写操作密集的情况下，这会造成竞争，因此尽量在访问量少的情况下执行此操作。
另外，可以使用多线程来进行清理操作。当然还有很多策略可以在清理的时候使用，比如，缓存一个叶子节点的父节点，在锁住该父节点执行迁移操作的时候可以顺便扫描该父节点下的其他叶子节点。
人的欲望是无止境的…….除了基于主键的检索你可能还需要基于某个属性的检索，最好还能在多个属性上查询完了以后来个取交集，这个时候怎么办呢？
首先，我们有一个基于主键的key-value数据库，key存储的主键，而value存储的对象（物理存储为byte数组），那么假如我们想对对象的某个属性如name进行查询的话，那么我们可以再建一个数据库，key是待查询的字段，value是主键数据库的id。
Primary Database
Key(ID)
Value(Object)
1
Byte[]
2
Byte[]
Secondary Database
Foreign Key(Name)
Value(ID)
dahuang
2
tugou
1
这样一来按照name查询只需要查询一次secondary database取出主键id，再查一查primary database即可，这有点像正排索引和倒排索引的概率，如果对于多个字段的组合查询，只需要对其进行一次join即可，在join的时候可以先对待join的结果按照结果集大小进行排序，这样可以省下不少时间消耗。
虽然key-value存储按照上面的描述也可以支持多条件查询，但是不建议这样做，一是建立索引（二级数据库）需要额外的空间，二是这样需要多次查询影响性能，不管怎么样适度的折衷吧。
最后不得不提一下，由于B+tree的数据结构，它很好地支持范围查询（查询可以不下到叶子节点）可以极大的弥补搜索引擎中倒排索引进行范围查询需要全部扫描的缺陷。这也是其应用场景之一。
Key-value在海量数据存储中占据很重要的地位，对于它的深入研究能带给我们很多启发，而它在某些局部问题上所表现的优秀的能力也值得我们关注。本文大致总结了一下目前所了解的一些问题，没有提到的东西还有很多（文件系统设计，事务，缓存等等），接下来如果有空会对文件系统设计进行详细讲解。
首先，本文只是代表本人的一些浅见，不代表任何官方意见。其次，由于作者水平的原因，肯定会出现错误，欢迎指正（最好站内，给我留一点脸面-_-）
Dynamo: Amazon’s Highly Available Key-value Store
http://blog.csdn.net/manesking/archive/2007/02/09/1505979.aspx (BTree,B-Tree,B+Tree,B*Tree都是什么)
相关文章
