本文主要复习各个算法，在全局是什么样的作用。

首先在这个领域基础的两篇论文：Bigtable和Dynamo。

豆瓣在招聘时提到：http://www.douban.com/campus#job-os

Cassandra的Overview中也提到：http://wiki.apache.org/cassandra/ArchitectureOverview

sql生态系统全面的乱侃了一遍：http://hongweiyi.com/2012/07/the-nosql-ecosystem/

Bigtable

数据模型

row key,column key,and timestamp 作为 KEY；

array of bytes 作为 VALUE。

table，column family，column。

Column key,column family,column content.

在一个table不同的column family数目很少，但是column数目无限多。

通过row key控制tablet，控制locality。

这里有个不同的概念：

连续的数据应该放在一个节点上，备份的数据应该放在不同的物理机器上。

解决错误的算法

vector clock：每次有个Key的值被修改，其vector clock就加一，相当于保存了一个版本信息。

Hinted Handoff， “sloppy quorum”：Hinted Handoff 如果负责某个key的节点挂了，就临时找一个节点保存当机期间的写操作，直到故障恢复。“sloppy quorum”是Dynamo中把成功写到临时节点的数目也加到W中。

读时修复：最终一致性，读的时候才来同步。

Anti-Entropy，Merkle Tree：节点通过逐层交换Hash Tree中的信息来找到两个节点的信息不一致的部分。

冲突解决：Dynamo选择把冲突留给应用层来解决。

Gossip：每隔一段时间，随机联系一个阶段，交换节点的健康状态。

一致性hash算法

virtual nodes

NWR之间必须要满足下面关系：R＋W>N