[转]NoSQL数据库笔谈

CAP，BASE和最终一致性是NoSQL数据库存在的三大基石。而五分钟法则是内存数据存储了理论依据。这个是一切的源头。

10年前，Eric Brewer教授指出了著名的CAP理论，后来Seth Gilbert 和 Nancy lynch两人证明了CAP理论的正确性。CAP理论告诉我们，一个分布式系统不可能满足一致性，可用性和分区容错性这三个需求，最多只能同时满足两个。

熊 掌与鱼不可兼得也。关注的是一致性，那么您就需要处理因为系统不可用而导致的写操作失败的情况，而如果您关注的是可用性，那么您应该知道系统的read操 作可能不能精确的读取到write操作写入的最新值。因此系统的关注点不同，相应的采用的策略也是不一样的，只有真正的理解了系统的需求，才有可能利用好 CAP理论。

作为架构师，一般有两个方向来利用CAP理论

1. key-value存储，如Amaze Dynamo等，可根据CAP三原则灵活选择不同倾向的数据库产品。
2. 领域模型 + 分布式缓存 + 存储 （Qi4j和NoSql运动），可根据CAP三原则结合自己项目定制灵活的分布式方案，难度高。

我准备提供第三种方案：实现可以配置CAP的数据库，动态调配CAP。

• CA：传统关系数据库
• AP：key-value数据库

而对大型网站，可用性与分区容忍性优先级要高于数据一致性，一般会尽量朝着 A、P 的方向设计，然后通过其它手段保证对于一致性的商务需求。架构设计师不要精力浪费在如何设计能满足三者的完美分布式系统，而是应该进行取舍。

不同数据对于一致性的要求是不同的。举例来讲，用户评论对不一致是不敏感的，可以容忍相对较长时间的不一致，这种不一致并不会影响交易和用户体验。而产品价格数据则是非常敏感的，通常不能容忍超过10秒的价格不一致。

一言以蔽之：过程松，结果紧，最终结果必须保持一致性

为了更好的描述客户端一致性，我们通过以下的场景来进行，这个场景中包括三个组成部分：

BASE模型反ACID模型，完全不同ACID模型，牺牲高一致性，获得可用性或可靠性： Basically Available基本可用。支持分区失败(e.g. sharding碎片划分数据库) Soft state软状态 状态可以有一段时间不同步，异步。 Eventually consistent最终一致，最终数据是一致的就可以了，而不是时时一致。

BASE思想的主要实现有
1.按功能划分数据库
2.sharding碎片

BASE思想主要强调基本的可用性，如果你需要高可用性，也就是纯粹的高性能，那么就要以一致性或容错性为牺牲，BASE思想的方案在性能上还是有潜力可挖的。
其他
I/O的五分钟法则 手段篇 一致性哈希

算法的选择 不同的哈希算法可以导致数据分布的不同位置，如果十分均匀，那么一次MapReduce就涉及节点较多，但热点均匀，方便管理。反之，热点不均，会大致机器效率发挥不完全。


Quorum NRW

• N: 复制的节点数量
• R: 成功读操作的最小节点数
• W: 成功写操作的最小节点数

只需W + R > N，就可以保证强一致性。

第一个关键参数是 N，这个 N 指的是数据对象将被复制到 N 台主机上，N 在实例级别配置，协调器将负责把数据复制到 N-1 个节点上。N 的典型值设置为 3.

复 制中的一致性，采用类似于 Quorum 系统的一致性协议实现。这个协议有两个关键值：R 与 W。R 代表一次成功的读取操作中最小参与节点数量，W 代表一次成功的写操作中最小参与节点数量。R + W>N ，则会产生类似 quorum 的效果。该模型中的读(写)延迟由最慢的 R(W)复制决定，为得到比较小的延迟，R 和 W 有的时候的和又设置比 N 小。

如果N中的1台发生故障，Dynamo立即写入到preference list中下一台，确保永远可写入

如 果W+R>N，那么分布式系统就会提供强一致性的保证，因为读取数据的节点和被同步写入的节点是有重叠的。在一个RDBMS的复制模型中 （Master/salve)，假如N=2,那么W=2,R=1此时是一种强一致性,但是这样造成的问题就是可用性的减低，因为要想写操作成功，必须要等 2个节点都完成以后才可以。

在分布式系统中，一般都要有容错性，因此一般N都是大于3的，此时根据CAP理论，一致性，可用性和分区容 错 性最多只能满足两个，那么我们就需要在一致性和分区容错性之间做一平衡，如果要高的一致性，那么就配置N=W，R=1,这个时候可用性就会大大降低。如果 想要高的可用性，那么此时就需要放松一致性的要求，此时可以配置W=1，这样使得写操作延迟最低，同时通过异步的机制更新剩余的N-W个节点。

当存储系统保证最终一致性时，存储系统的配置一般是W+R<=N,此时读取和写入操作是不重叠的，不一致性的窗口就依赖于存储系统的异步实现方式，不一致性的窗口大小也就等于从更新开始到所有的节点都异步更新完成之间的时间。

(N,R,W) 的值典型设置为 (3,2,2),兼顾性能与可用性。R 和 W 直接影响性能、扩展性、一致性，如果 W 设置 为 1，则一个实例中只要有一个节点可用，也不会影响写操作，如果 R 设置为 1 ，只要有一个节点可用，也不会影响读请求，R 和 W 值过小则影响一致性，过大也不好，这两个值要平衡。对于这套系统的典型的 SLA 要求 99.9% 的读写操作在 300ms 内完成。

无 论是Read-your-writes-consistency,Session consistency,Monotonic read consistency,它们都通过黏贴（stickiness)客户端到执行分布式请求的服务器端来实现的，这种方式简单是简单，但是它使得负载均衡以 及分区容错变的更加难于管理，有时候也可以通过客户端来实现Read-your-writes-consistency和Monotonic read consistency,此时需要对写的操作的数据加版本号，这样客户端就可以遗弃版本号小于最近看到的版本号的数据。

在系统开发过程 中，根据CAP理论，可用性和一致性在一个大型分区容错的系统中只能满足一个，因此为了高可用性，我们必须放低一致性的要求，但是不同的系统保证的一致性 还是有差别的，这就要求开发者要清楚自己用的系统提供什么样子的最终一致性的保证，一个非常流行的例子就是web应用系统，在大多数的web应用系统中都 有“用户可感知一致性”的概念，这也就是说最终一致性中的“一致性窗口"大小要小于用户下一次的请求，在下次读取操作来之前，数据可以在存储的各个节点之 间复制。还比如假如存储系统提供了

read-your-write-consistency一致性，那么当一个用户写操作完成以后可以立马看到自己的更 新，但是其它的用户要过一会才可以看到更新。

几种特殊情况：
W = 1,R = N,对写操作要求高性能高可用。
R = 1,W = N,对读操作要求高性能高可用，比如类似cache之类业务。
W = Q,R = Q where Q = N / 2 + 1 一般应用适用，读写性能之间取得平衡。如N=3,W=2,R=2

Vector clock



vector clock算法。可以把这个vector clock想象成每个节点都记录自己的版本信息，而一个数据，包含所有这些版本信息。来看一个例子：假设一个写请求，第一次被节点A处理了。节点A会增加 一个版本信息(A，1)。我们把这个时候的数据记做D1(A，1)。 然后另外一个对同样key(这一段讨论都是针对同样的key的)的请求还是被A处理了于是有D2(A，2)。

这个时候，D2是可以覆盖 D1的，不会有冲突产生。现在我们假设D2传播到了所有节点(B和C)，B和C收到的数据不是从客户产生的，而是别人复制给他们的，所以他们不产生新的版 本信息，所以现在B和C都持有数据D2(A，2)。好，继续，又一个请求，被B处理了，生成数据D3(A，2;B，1)，因为这是一个新版本的数据，被B 处理，所以要增加B的版本信息。

假设D3没有传播到C的时候又一个请求被C处理记做D4(A，2;C，1)。假设在这些版本没有传播开来 以前，有一个读取操作，我们要记得，我们的W=1 那么R=N=3，所以R会从所有三个节点上读，在这个例子中将读到三个版本。A上的D2(A，2);B上的D3(A，2;B，1);C上的D4(A，2; C，1)这个时候可以判断出，D2已经是旧版本，可以舍弃，但是D3和D4都是新版本，需要应用自己去合并。

如果需要高可写性，就要处理 这种合并问题。好假设应用完成了冲入解决，这里就是合并D3和D4版本，然后重新做了写入，假设是B处理这个请求，于是有 D5(A，2;B，2;C，1);这个版本将可以覆盖掉D1-D4那四个版本。这个例子只举了一个客户的请求在被不同节点处理时候的情况， 而且每次写更新都是可接受的，大家可以自己更深入的演算一下几个并发客户的情况，以及用一个旧版本做更新的情况。

上面问题看似好像可以通 过在三个节点里选择一个主节点来解决，所有的读取和写入都从主节点来进行。但是这样就违背了W=1这个约定，实际上还是退化到W=N的情况了。所以如果系 统不需要很大的弹性，W=N为所有应用都接受，那么系统的设计上可以得到很大的简化。Dynamo 为了给出充分的弹性而被设计成完全的对等集群(peer to peer)，网络中的任何一个节点都不是特殊的。
Virtual node
gossip

Gossip协议是一个Gossip思想的P2P实现。现代的分布式系统经常使用这个协议，他往往是唯一的手段。因为底层的结构非常复杂，而且Gossip也很有效。

Gossip协议也被戏称为病毒式传播，因为他的行为生物界的病毒很相似。

Gossip (State Transfer Model) 在状态转移到模式下，每个重复节点都保持的一个Vector clock和一个state version tree。每个节点的状态都是相同的(based on vector clock comparison),换句话说，state version tree包含有全部的冲突updates.

At query time,the client will attach its vector clock and the replica will send back a subset of the state tree which precedes the client's vector clock (this will provide monotonic read consistency). The client will then advance its vector clock by merging all the versions. This means the client is responsible to resolve the conflict of all these versions because when the client sends the update later,its vector clock will precede all these versions.
At update,the client will send its vector clock and the replica will check whether the client state precedes any of its existing version,if so,it will throw away the client's update.

Replicas also gossip among each other in the background and try to merge their version tree together.



Gossip (Operation Transfer Model)
In an operation transfer approach,the sequence of applying the operations is very important. At the minimum causal order need to be maintained. Because of the ordering issue,each replica has to defer executing the operation until all the preceding operations has been executed. Therefore replicas save the operation request to a log file and exchange the log among each other and consolidate these operation logs to figure out the right sequence to apply the operations to their local store in an appropriate order.

"Causal order" means every replica will apply changes to the "causes" before apply changes to the "effect". "Total order" requires that every replica applies the operation in the same sequence.

In this model,each replica keeps a list of vector clock,Vi is the vector clock the replica itself and Vj is the vector clock when replica i receive replica j's gossip message. There is also a V-state that represent the vector clock of the last updated state.

When a query is submitted by the client,it will also send along its vector clock which reflect the client's view of the world. The replica will check if it has a view of the state that is later than the client's view.



When an update operation is received,the replica will buffer the update operation until it can be applied to the local state. Every submitted operation will be tag with 2 timestamp,V-client indicates the client's view when he is making the update request. V-@receive is the replica's view when it receives the submission.

This update operation request will be sitting in the queue until the replica has received all the other updates that this one depends on. This condition is reflected in the vector clock Vi when it is larger than V-client



On the background,different replicas exchange their log for the queued updates and update each other's vector clock. After the log exchange,each replica will check whether certain operation can be applied (when all the dependent operation has been received) and apply them accordingly. Notice that it is possible that multiple operations are ready for applying at the same time,the replica will sort these operation in causal order (by using the Vector clock comparison) and apply them in the right order.



The concurrent update problem at different replica can also happen. Which means there can be multiple valid sequences of operation. In order for different replica to apply concurrent update in the same order,we need a total ordering mechanism.

One approach is whoever do the update first acquire a monotonic sequence number and late comers follow the sequence. On the other hand,if the operation itself is commutative,then the order to apply the operations doesn't matter

After applying the update,the update operation cannot be immediately removed from the queue because the update may not be fully exchange to every replica yet. We continuously check the Vector clock of each replicas after log exchange and after we confirm than everyone has receive this update,then we'll remove it from the queue.

Merkle tree 有 数据存储成树状结构，每个节点的Hash是其所有子节点的Hash的Hash，叶子节点的Hash是其内容的Hash。这样一旦某个节点发生变化，其 Hash的变化会迅速传播到根节点。需要同步的系统只需要不断查询跟节点的hash，一旦有变化，顺着树状结构就能够在logN级别的时间找到发生变化的 内容，马上同步。
Paxos paxos是一种处理一致性的手段，可以理解为事务吧。
其他的手段不要Google GFS使用的Chubby的Lock service。我不大喜欢那种重型的设计就不费笔墨了。



Google Chubby的作者Mike Burrows说过， “there is only one consensus protocol,and that’s Paxos” – all other approaches are just broken versions of Paxos. 意即“世上只有一种一致性算法，那就是Paxos”，所有其他一致性算法都是Paxos算法的不完整版。相比2PC/3PC,Paxos算法的改进
P1a. 每次Paxos实例执行都分配一个编号，编号需要递增，每个replica不接受比当前最大编号小的提案
P2. 一旦一个 value v 被replica通过，那么之后任何再批准的 value 必须是 v，即没有拜占庭将军(Byzantine)问题。拿上面请客的比喻来说，就是一个参与者一旦accept周六2pm-5pm的proposal,就不能改变主意。以后不管谁来问都是accept这个value。
一个proposal只需要多数派同意即可通过。因此比2PC/3PC更灵活，在一个2f+1个节点的集群中，允许有f个节点不可用。

另外Paxos还有很多约束的细节，特别是Google的chubby从工程实现的角度将Paxos的细节补充得非常完整。比如如何避免Byzantine问题，由于节点的持久存储可能会发生故障，Byzantine问题会导致Paxos算法P2约束失效。

以上几种方式原理比较如下


DHT
Distributed hash table


Map Reduce Execution Map Reduce已经烂大街了，不过还是要提一下。
参见：http://zh.wikipedia.org/wiki/MapReduce



Handling Deletes 但我们执行删除操作的时候必须非常谨慎，以防丢失掉相应的版本信息。

通常我们给一个Object标注上"已删除"的标签。在足够的时间之后，我们在确保版本一致的情况下可以将它彻底删除。回收他的空间。


存储实现 One strategy is to use make the storage implementation pluggable. e.g. A local MySQL DB,Berkeley DB,Filesystem or even a in memory Hashtable can be used as a storage mechanism.

Another strategy is to implement the storage in a highly scalable way. Here are some techniques that I learn fromCouchDBand Google BigTable.

CouchDB has a MVCC model that uses a copy-on-modified approach. Any update will cause a private copy being made which in turn cause the index also need to be modified and causing the a private copy of the index as well,all the way up to the root pointer.

Notice that the update happens in an append-only mode where the modified data is appended to the file and the old data becomes garbage. Periodic garbage collection is done to compact the data. Here is how the model is implemented in memory and disks

In Google BigTable model,the data is broken down into multiple generations and the memory is use to hold the newest generation. Any query will search the mem data as well as all the data sets on disks and merge all the return results. Fast detection of whether a generation contains a key can be done by checking a bloom filter.



When update happens,both the mem data and the commit log will be written so that if the

节点变化
Notice that virtual nodes can join and leave the network at any time without impacting the operation of the ring.

When a new node joins the network

1. 新加入的节点宣告自己的存在(广播或者其他手段)
2. 他的邻居节点要调整Key的分配和复制关系。这个操作通常是同步的
3. 这个新加入的节点异步的拷贝数据
4. 这个节点变化的操作被发布到其他节点
   

Notice that other nodes may not have their membership view updated yet so they may still forward the request to the old nodes. But since these old nodes (which is the neighbor of the new joined node) has been updated (in step 2),so they will forward the request to the new joined node.

On the other hand,the new joined node may still in the process of downloading the data and not ready to serve yet. We use the vector clock (described below) to determine whether the new joined node is ready to serve the request and if not,the client can contact another replica.

When an existing node leaves the network (e.g. crash)

1. The crashed node no longer respond to gossip message so its neighbors knows about it.崩溃的节点不再发送Gossip Message的回应，所以他的邻居都知道他是了
   
2. The neighbor will update the membership changes and copy data asynchronously，他的邻居处理后事，将他的活分给别人干，同时调整节点关系。

We haven't talked about how the virtual nodes is mapped into the physical nodes. Many schemes are possible with the main goal that Virtual Node replicas should not be sitting on the same physical node. One simple scheme is to assigned Virtual node to Physical node in a random manner but check to make sure that a physical node doesn't contain replicas of the same key ranges.

Notice that since machine crashes happen at the physical node level,which has many virtual nodes runs on it. So when a single Physical node crashes,the workload (of its multiple virtual node) is scattered across many physical machines. Therefore the increased workload due to physical node crashes is evenly balanced.
列存 描述

数据库以行、列的二维表的形式存储数据，但是却以一维字符串的方式存储，例如以下的一个表：

EmpId	Lastname	Firstname	Salary
1	Smith	Joe	40000
2	Jones	Mary	50000
3	Johnson	Cathy	44000

这个简单的表包括员工代码(EmpId),姓名字段(Lastname and Firstname)及工资(Salary).

这个表存储在电脑的内存(RAM)和存储(硬盘)中。虽然内存和硬盘在机制上不同，电脑的操作系统是以同样的方式存储的。数据库必须把这个二维表存储在一系列一维的“字节”中，又操作系统写到内存或硬盘中。

行式数据库把一行中的数据值串在一起存储起来，然后再存储下一行的数据，以此类推。 1,Smith,Joe,40000;2,Jones,Mary,50000;3,Johnson,Cathy,44000;

列式数据库把一列中的数据值串在一起存储起来，然后再存储下一列的数据，以此类推。 1,3;Smith,Johnson;Joe,Cathy;40000,50000,44000;

特点

• 良好的压缩比。由于大多数数据库设计都有冗余，如此一来，压缩比非常高，把40多M的数据导入infobright，没想到数据文件只有1M多
• 列上的计算非常的快。
• 方便MapReduce和Key-value模型的融合
• 读取整行的数据较慢，但部分数据较快

简单分析含源码

软件篇 亚数据库 我发明的新概念，就是称不上数据库但有一些数据库的特征。可以指缓存。
MemCached Memcached是danga.com（运营LiveJournal的技术团队）开发的一套分布式内存对象缓存系统，用于在动态系统中减少数据库 负载，提升性能。
特点

• 协议简单
• 基于libevent的事件处理
• 内置内存存储方式
• memcached不互相通信的分布式

Memcached处理的原子是每一个（key，value）对（以下简称kv对），key会通过一个hash算法转化成hash-key，便于查找、对比以及做到尽可能的散列。同时，memcached用的是一个二级散列，通过一张大hash表来维护。

Memcached有两个核心组件组成：服务端（ms）和客户端（mc），在一个memcached的查询中，mc先通过计算key的 hash值来 确定kv对所处在的ms位置。当ms确定后，客户端就会发送一个查询请求给对应的ms，让它来查找确切的数据。因为这之间没有交互以及多播协议，所以 memcached交互带给网络的影响是最小化的。

内存分配

默认情况下，ms是用一个内置的叫“块分配器”的组件来分配内存的。舍弃c++标准的malloc/free的内存分配，而采用块分配器的主要目的 是为了避免内存碎片，否则操作系统要花费更多时间来查找这些逻辑上连续的内存块（实际上是断开的）。用了块分配器，ms会轮流的对内存进行大块的分配，并 不断重用。当然由于块的大小各不相同，当数据大小和块大小不太相符的情况下，还是有可能导致内存的浪费。

同时，ms对key和data都有相应的限制，key的长度不能超过250字节，data也不能超过块大小的限制 --- 1MB。
因 为mc所使用的hash算法，并不会考虑到每个ms的内存大小。理论上mc会分配概率上等量的kv对给每个ms，这样如果每个ms的内存都不太一样，那 可能会导致内存使用率的降低。所以一种替代的解决方案是，根据每个ms的内存大小，找出他们的最大公约数，然后在每个ms上开n个容量=最大公约数的 instance，这样就等于拥有了多个容量大小一样的子ms，从而提供整体的内存使用率。

缓存策略

当ms的hash表满了之后，新的插入数据会替代老的数据，更新的策略是LRU（最近最少使用），以及每个kv对的有效时限。Kv对存储有效时限是在mc端由app设置并作为参数传给ms的。

同时ms采用是偷懒替代法，ms不会开额外的进程来实时监测过时的kv对并删除，而是当且仅当，新来一个插入的数据，而此时又没有多余的空间放了，才会进行清除动作。

缓存数据库查询

现在memcached最流行的一种使用方式是缓存数据库查询，下面举一个简单例子说明：

App需要得到userid=xxx的用户信息，对应的查询语句类似：

“SELECT * FROM users WHERE userid = xxx”

App先去问cache，有没有“user:userid”（key定义可预先定义约束好）的数据，如果有，返回数据；如果没有，App会从数据库中读取数据，并调用cache的add函数，把数据加入cache中。

当取的数据需要更新，app会调用cache的update函数，来保持数据库与cache的数据同步。

从上面的例子我们也可以发现，一旦数据库的数据发现变化，我们一定要及时更新cache中的数据，来保证app读到的是同步的正确数据。当 然我们可 以通过定时器方式记录下cache中数据的失效时间，时间一过就会激发事件对cache进行更新，但这之间总会有时间上的延迟，导致app可能从 cache读到脏数据，这也被称为狗洞问题。（以后我会专门描述研究这个问题）

数据冗余与故障预防

从设计角度上，memcached是没有数据冗余环节的，它本身就是一个大规模的高性能cache层，加入数据冗余所能带来的只有设计的复杂性和提高系统的开支。

当一个ms上丢失了数据之后，app还是可以从数据库中取得数据。不过更谨慎的做法是在某些ms不能正常工作时，提供额外的ms来支持cache，这样就不会因为app从cache中取不到数据而一下子给数据库带来过大的负载。

同时为了减少某台ms故障所带来的影响，可以使用“热备份”方案，就是用一台新的ms来取代有问题的ms，当然新的ms还是要用原来ms的IP地址，大不了数据重新装载一遍。

另外一种方式，就是提高你ms的节点数，然后mc会实时侦查每个节点的状态，如果发现某个节点长时间没有响应，就会从mc的可用 server列表里 删除，并对server节点进行重新hash定位。当然这样也会造成的问题是，原本key存储在B上，变成存储在C上了。所以此方案本身也有其弱点，最好 能和“热备份”方案结合使用，就可以使故障造成的影响最小化。

Memcached客户端（mc）

Memcached客户端有各种语言的版本供大家使用，包括java，c，php，.net等等，具体可参见memcached api page [2]。
大家可以根据自己项目的需要，选择合适的客户端来集成。

缓存式的Web应用程序架构

有了缓存的支持，我们可以在传统的app层和db层之间加入cache层，每个app服务器都可以绑定一个mc，每次数据的读取都可以从ms中取 得，如果 没有，再从db层读取。而当数据要进行更新时，除了要发送update的sql给db层，同时也要将更新的数据发给mc，让mc去更新ms中的数据。

性能测试 Memcached 写速度
平均速度: 16222 次/秒
最大速度 18799 次/秒

Memcached 读速度
平均速度: 20971 次/秒
最大速度 22497 次/秒

Memcachedb 写速度
平均速度: 8958 次/秒
最大速度 10480 次/秒

Memcachedb 读速度
平均速度: 6871 次/秒
最大速度 12542 次/秒

源代码级别的分析
非常好的剖析文章

dbcached

● dbcached 是一款基于 Memcached 和 NMDB 的分布式 key-value 数据库内存缓存系统。
● dbcached = Memcached + 持久化存储管理器 + NMDB 客户端接口
● Memcached 是一款高性能的，分布式的内存对象缓存系统，用于在动态应用中减少数据库负载，提升访问速度。
● NMDB 是一款多协议网络数据库(dbm类)管理器，它由内存缓存和磁盘存储两部分构成，使用 QDBM 或 Berkeley DB 作为后端数据库。
● QDBM 是一个管理数据库的例程库，它参照 GDBM 为了下述三点而被开发：更高的处理速度，更小的数据库文件大小，和更简单的API。QDBM 读写速度比 Berkeley DB 要快，详细速度比较见《 Report of Benchmark Test》。


Memcached 和 dbcached 在功能上一样吗? ● 兼容：Memcached 能做的，dbcached 都能做。除此之外，dbcached 还将“Memcached、持久化存储管理器、NMDB 客户端接口”在一个程序中结合起来，对任何原有 Memcached 客户端来讲，dbcached 仍旧是个 Memcached 内存对象缓存系统，但是，它的数据可以持久存储到本机或其它服务器上的 QDBM 或 Berkeley DB 数据库中。
● 性能：前端 dbcached 的并发处理能力跟 Memcached 相同；后端 NMDB 跟 Memcached 一样，采用了libevent 进行网络IO处理，拥有自己的内存缓存机制，性能不相上下。
● 写入：当“dbcached 的 Memcached 部分”接收到一个 set(add/replace/...) 请求并储存 key-value 数据到内存中后，“dbcached 持久化存储管理器”能够将 key-value 数据通过“NMDB 客户端接口”保存到 QDBM 或 Berkeley DB 数据库中。
● 速度：如果加上“-z”参数，采用 UDP 协议“只发送不接收”模式将 set(add/replace/...) 命令写入的数据传递给 NMDB 服务器端，对 Memcache 客户端写速度的影响几乎可以忽略不计。在千兆网卡、同一交换机下服务器之间的 UDP 传输丢包率微乎其微。在命中的情况下，读取数据的速度跟普通的 Memcached 无差别，速度一样快。
● 读取：当“dbcached 的 Memcached 部分”接收到一个 get(incr/decr/...) 请求后，如果“dbcached 的 Memcached 部分”查询自身的内存缓存未命中，则“dbcached 持久化存储管理器”会通过“NMDB 客户端接口”从 QDBM 或 Berkeley DB 数据库中取出数据，返回给用户，然后储存到 Memcached 内存中。如果有用户再次请求这个 key，则会直接从 Memcached 内存中返回 Value 值。
● 持久：使用 dbcached，不用担心 Memcached 服务器死机、重启而导致数据丢失。
● 变更：使用 dbcached，即使因为故障转移，添加、减少 Memcached 服务器节点而破坏了“key 信息”与对应“Memcached 服务器”的映射关系也不怕。
● 分布：dbcached 和 NMDB 既可以安装在同一台服务器上，也可以安装在不同的服务器上，多台 dbcached 服务器可以对应一台 NMDB 服务器。
● 特长：dbcached 对于“读”大于“写”的应用尤其适用。
● 其他：《 dbcached 的故障转移支持、设计方向以及与 Memcachedb 的不同之处》
列存系列 Hadoop之Hbase Hadoop / HBase: API: Java / any writer,Protocol: any write call,Query Method: MapReduce Java / any exec,Replication: HDFS Replication,Written in: Java,Concurrency: ?,Misc: Links: 3 Books [ 1,2,3]
耶鲁大学之HadoopDB
GreenPlum

FaceBook之Cassandra
Cassandra: API: many Thrift ? languages,Protocol: ?,Query Method: MapReduce,Replicaton:,Concurrency: eventually consistent,Misc: like "Big-Table on Amazon Dynamo alike",initiated by Facebook,Slides ?,Clients ?

Cassandra是facebook开源出来的一个版本，可以认为是BigTable的一个开源版本，目前twitter和digg.com在使用。

Cassandra特点

• 灵活的schema，不需要象数据库一样预先设计schema，增加或者删除字段非常方便（on the fly）。
• 支持range查询：可以对Key进行范围查询。
• 高可用，可扩展：单点故障不影响集群服务，可线性扩展。

Cassandra 的主要特点就是它不是一个数据库，而是由一堆数据库节点共同构成的一个分布式网络服务，对Cassandra的一个写操作，会 被复制到其他节点上去，对Cassandra的读操作，也会被路由到某个节点上面去读取。对于一个Cassandra群集来说，扩展性能是比较简单的事 情，只管在群集里面添加节点就可以了。我看到有文章说Facebook的Cassandra群集有超过100台服务器构成的数据库群集。

Cassandra也支持比较丰富的数据结构和功能强大的查询语言，和MongoDB比较类似，查询功能比MongoDB稍弱一些，twitter的平台架构部门领导Evan Weaver写了一篇文章介绍Cassandra： http://blog.evanweaver.com/articles/2009/07/06/up-and-running-with-cassandra/，有非常详细的介绍。

Cassandra 以单个节点来衡量，其节点的并发读写性能不是特别好，有文章说评测下来Cassandra每秒大约不到1万次读写请求，我也看 到一些对这个问题进行质疑的评论，但是评价Cassandra单个节点的性能是没有意义的，真实的分布式数据库访问系统必然是n多个节点构成的系统，其并 发性能取决于整个系统的节点数量，路由效率，而不仅仅是单节点的并发负载能力。
Keyspace Cassandra中的最大组织单元，里面包含了一系列Column family，Keyspace一般是应用程序的名称。你可以把它理解为Oracle里面的一个schema，包含了一系列的对象。
Column family（CF） CF是某个特定Key的数据集合，每个CF物理上被存放在单独的文件中。从概念上看，CF有点象数据库中的Table.
Key 数据必须通过Key来访问，Cassandra允许范围查询，例如：start => '10050',:finish => '10070'
Column 在Cassandra中字段是最小的数据单元，column和value构成一个对，比如：name:“jacky”，column是name，value是jacky，每个column:value后都有一个时间戳：timestamp。

和 数据库不同的是，Cassandra的一行中可以有任意多个column，而且每行的column可以是不同的。从数据库设计的角度，你可以理解 为表上有两个字段，第一个是Key，第二个是长文本类型，用来存放很多的column。这也是为什么说Cassandra具备非常灵活schema的原 因。
Super column Super column是一种特殊的column，里面可以存放任意多个普通的column。而且一个CF中同样可以有任意多个Super column，一个CF只能定义使用Column或者Super column，不能混用。下面是Super column的一个例子，homeAddress这个Super column有三个字段：分别是street，city和zip： homeAddress: {street: "binjiang road",city: "hangzhou",zip: "310052",}

Sorting 不 同于数据库可以通过Order by定义排序规则，Cassandra取出的数据顺序是总是一定的，数据保存时已经按照定义的规则存放，所以取出来的顺序已经确定了，这是一个巨大的性能 优势。有意思的是，Cassandra按照column name而不是column value来进行排序，它 定义了以下几种选项：BytesType,UTF8Type,LexicalUUIDType,TimeUUIDType,AsciiType,和LongType，用来定义如何按照column name来排序。实际上，就是把column name识别成为不同的类型，以此来达到灵活排序的目的。UTF8Type是把column name转换为UTF8编码来进行排序，LongType转换成为64位long型，TimeUUIDType是按照基于时间的UUID来排序。例如：

Column name按照LongType排序：
{name: 3,value: "jacky"},
{name: 123,value: "hellodba"},
{name: 976,value: "Cassandra"},
{name: 832416,value: "bigtable"}

Column name按照UTF8Type排序：
{name: 123,
{name: 3,value: "bigtable"}
{name: 976,value: "Cassandra"}

下面我们看twitter的Schema：
<Keyspace Name="Twitter">
<ColumnFamily CompareWith="UTF8Type" Name="Statuses" />
<ColumnFamily CompareWith="UTF8Type" Name="StatusAudits" />
<ColumnFamily CompareWith="UTF8Type" Name="StatusRelationships"
CompareSubcolumnsWith="TimeUUIDType" ColumnType="Super" />
<ColumnFamily CompareWith="UTF8Type" Name="Users" />
<ColumnFamily CompareWith="UTF8Type" Name="UserRelationships"
CompareSubcolumnsWith="TimeUUIDType" ColumnType="Super" />
</Keyspace>

我 们看到一个叫Twitter的keyspace，包含若干个CF，其中StatusRelationships和 UserRelationships被定义为包含Super column的CF，CompareWith定义了column的排序规则，CompareSubcolumnsWith定义了subcolumn的排序 规则，这里使用了两种：TimeUUIDType和UTF8Type。我们没有看到任何有关column的定义，这意味着column是可以灵活变更的。

为了方便大家理解，我会尝试着用关系型数据库的建模方法去描述Twitter的Schema，但千万不要误认为这就是Cassandra的数据模型，对于Cassandra来说，每一行的colunn都可以是任意的，而不是象数据库一样需要在建表时就创建好。


Users CF记录用户的信息，Statuses CF记录tweets的内容，StatusRelationships CF记录用户看到的tweets，UserRelationships CF记录用户看到的followers。我们注意到排序方式是TimeUUIDType，这个类型是按照时间进行排序的UUID字段，column name是用UUID函数产生（这个函数返回了一个UUID，这个UUID反映了当前的时间，可以根据这个UUID来排序，有点类似于timestamp 一样），所以得到结果是按照时间来排序的。使用过twitter的人都知道，你总是可以看到自己最新的tweets或者最新的friends.

存储 Cassandra是基于列存储的(Bigtable也是一样)，这个和基于列的数据库是一个道理。


API 下面是数据库，Bigtable和Cassandra API的对比： Relational SELECT `column` FROM `database`.`table` WHERE `id` = key;
BigTable table.get(key,"column_family:column")
Cassandra: standard model keyspace.get("column_family",key,"column")
Cassandra: super column model keyspace.get("column_family","super_column","column")

我对Cassandra数据模型的理解：

1.column name存放真正的值，而value是空。因为Cassandra是按照column name排序，而且是按列存储的，所以往往利用column name存放真正的值，而value部分则是空。例如：“jacky”:“null”，“fenng”:”null”

2.Super column可以看作是一个索引，有点象关系型数据库中的外键，利用super column可以实现快速定位，因为它可以返回一堆column，而且是排好序的。

3.排序在定义时就确定了，取出的数据肯定是按照确定的顺序排列的，这是一个巨大的性能优势。

4. 非常灵活的schema，column可以灵活定义。实际上，colume name在很多情况下，就是value（是不是有点绕）。

5.每个column后面的timestamp，我并没有找到明确的说明，我猜测可能是数据多版本，或者是底层清理数据时需要的信息。

最后说说架构，我认为架构的核心就是有所取舍，不管是CAP还是BASE，讲的都是这个原则。架构之美在于没有任何一种架构可以完美的解决各种问题，数据库和NoSQL都有其应用场景，我们要做的就是为自己找到合适的架构。

Hypertable

Hypertable : (can you help?) Open-Source Google BigTable alike.

它是搜索引擎公司Zvents根据Google的9位研究人员在2006年发表的一篇论文《 Bigtable：结构化数据的分布存储系统》 开发的一款开源分布式数据储存系统。Hypertable是按照1000节点比例设计，以 C++撰写，可架在 HDFS 和 KFS 上。尽管还在初期阶段，但已有不错的效能：写入 28M 列的资料，各节点写入速率可达7MB/s，读取速率可达 1M cells/s。Hypertable目前一直没有太多高负载和大存储的应用实例，但是最近，Hypertable项目得到了 百度的赞助支持，相信其会有更好的发展。

Google之BigTable 研究Google的产品总是感激Google给了自己那么多方便，真心喜欢之。

Google AppEngine Datastore 是在BigTable之上建造出来的，是Google的内部存储系统，用于处理结构化数据。AppEngine Datastore其自身及其内部都不是直接访问BigTable的实现机制，可被视为BigTable之上的一个简单接口。

AppEngine Datastore所支持的项目的数据类型要比SimpleDB丰富得多，也包括了包含在一个项目内的数据集合的列表型。

如果你打算在Google AppEngine之内建造应用的话，几乎可以肯定要用到这个数据存储。然而，不像SimpleDB，使用谷歌网络服务平台之外的应用，你并不能并发地与AppEngine Datastore进行接口 (或通过BigTable)。
Yahoo之PNUTS

Yahoo!的PNUTS是一个分布式的数据存储平台，它是Yahoo!云计算平台重要的一部分。它的上层产品通常也称为Sherpa。按照官方的 描述，”PNUTS,a massively parallel and geographically distributed database system for Yahoo!’s web applications.” PNUTS显然就深谙CAP之道，考虑到大部分web应用对一致性并不要求非常严格，在设计上放弃了对强一致性的追求。代替的是追求更高的 availability，容错，更快速的响应调用请求等。

特点

• 地理分布式，分布在全球多个数据中心。由于大部分Web应用都对响应时间要求高，因此最好服务器部署在离用户最近的本地机房。
• 可扩展，记录数可支持从几万条到几亿条。数据容量增加不会影响性能。
• schema-free，即非固定表结构。实际使用key/value存储的，一条记录的多个字段实际是用json方式合并存在value中。因此delete和update必须指定primary key。但也支持批量查询。
• 高可用性及容错。从单个存储节点到整个数据中心不可用都不会影响前端Web访问。
• 适合存相对小型的记录，不适合存储大文件，流媒体等。
• 弱一致性保证。

PNUTS实现 Record-level mastering 记录级别主节点
每 一条记录都有一个主记录。比如一个印度的用户保存的记录master在印度机房，通常修改都会调用印度。其他地方如美国用户看这个用户的资料调用 的是美国数据中心的资料，有可能取到的是旧版的数据。非master机房也可对记录进行修改，但需要master来统一管理。每行数据都有自己的版本控 制，如下图所示。


PNUTS的结构
每个数据中心的PNUTS结构由四部分构成
Storage Units (SU) 存储单元
物 理的存储服务器，每个存储服务器上面含有多个tablets，tablets是PNUTS上的基本存储单元。一 个tablets是一个yahoo内部格式的hash table的文件(hash table)或是一个MySQL innodb表(ordered table)。一个Tablet通常为几百M。一个SU上通常会存在几百个tablets。
Routers
每个tablets在哪个SU上是通过查询router获得。一个数据中心内router通常可由两台双机备份的单元提供。

Tablet Controller
router的位置只是个内存快照，实际的位置由Tablet Controller单元决定。
Message Broker

与远程数据的同步是由YMB提供，它是一个pub/sub的异步消息订阅系统。
Tablets寻址与切分 存储分hash和ordered data store。

以 hash为例介绍，先对所有的tablets按hash值分片，比如1-10,000属于tablets 1,10,000到20,000属于tablets 2，依此类推分配完所有的hash范围。一个大型的IDC通常会存在100万以下的tablets,1,000台左右的SU。tablets属于哪个SU由routers全部加载到内存里面，因此router访问速度极快，通常不会成为瓶颈。按照官方的 说法，系统的瓶颈只存在磁盘文件hash file访问上。
当某个SU访问量过大，则可将SU中部分tablets移到相对空闲的SU，并修改tablet controller的偏移记录。router定位tablet失效之后会自动通过tablet controller重新加载到内存。所以切分也相对容易实现。
Tim 也曾经用MySQL实现过类似大规模存储的系统，当时的做法是把每条记录的key属于哪个SU的信息保存到 一个字典里面，好处是切分可以获得更大的灵活性，可以动态增加新的tablets,而不需要切分旧的tablets。但缺点就是字典没法像router这 样，可以高效的全部加载到内存中。所以比较而言，在实际的应用中，按段分片会更简单，且已经足够使用。