NoSQL学习笔记(一)之概述

1.综述

NoSQL数据库是一个对于传统SQL数据库的一种挑战，由于现在企业和互联网应用数据量的膨胀，SQL已经不能支持这样的海量数据的分布式存储和高速读写，所以NoSQL应运而生。NoSQL通过key-value这样一种简单高效的数据存储方式提高了数据库性能。

2.理论

CAP，BASE和最终一致性是NoSQL数据库存在的三大基石。下面详细的说说这3个理论。

2.1CAP理论

C: Consistency 一致性(对于多用户，读写的数据变动同步)

A: Availability 可用性(快速获取数据)

P: Tolerance of network Partition 分区容错性(分布式可靠性)

CAP理论是由Eric Brewer教授提出的，CAP理论的核心是：一个分布式系统不可能满足一致性，可用性和分区容错性这三个需求，最多只能同时满足两个。

详见：http://www.julianbrowne.com/article/viewer/brewers-cap-theorem

2.2BASE理论

BasicallyAvailble 基本可用(支持分区失败)

Soft-state 软状态/柔性事务(无状态连接，支持异步)

Eventual Consistency 最终一致性(不要求高一致性，只要求最终能够一致)

BASE理论的核心是：牺牲高一致性，获得可用性或可靠性

详见：http://www.jdon.com/jivejdon/thread/37625

2.3最终一致性理论

(1)强一致性

强一致性（即时一致性）假如A先写入了一个值到存储系统，存储系统保证后续A,B,C的读取操作都将返回最新值

(2)弱一致性

假如A先写入了一个值到存储系统，存储系统不能保证后续A,B,C的读取操作能读取到最新值。此种情况下有一个“不一致性窗口”的概念，它特指从A写入值，到后续操作A,B,C读取到最新值这一段时间。

(3)最终一致性

最终一致性是弱一致性的一种特例。假如A首先write了一个值到存储系统，存储系统保证如果在A,B,C后续读取之前没有其它写操作更新同样的值的话，最终所有的读取操作都会读取到最A写入的最新值。此种情况下，如果没有失败发生的话，“不一致性窗口”的大小依赖于以下的几个因素：交互延迟，系统的负载，以及复制技术中replica的个数（这个可以理解为master/salve模式中，salve的个数），最终一致性方面最出名的系统可以说是 DNS系统，当更新一个域名的IP以后，根据配置策略以及缓存控制策略的不同，最终所有的客户都会看到最新的值。

详见：http://www.allthingsdistributed.com/2008/12/eventually_consistent.html

3.技术

3.1分布式存储

(1)Master/Slave

优点：成熟稳定

缺点：写操作单点故障，slave延迟

(2)Multi-master

优点：多master解决单点故障

缺点：不易实现一致性

(3)Two phase commit

优点：简单的一致性算法

缺点：无容错

(4)Three phase commit

优点：允许发生单点故障后达成一致。

详见：http://sebug.net/paper/databases/nosql/Nosql.html#_08464202471077442_91161458194

3.2一致性hash

一致性hash是一种巧妙的hash算法，在解决分布式系统负载均衡问题上很有效。

详见：http://www.cnblogs.com/leoo2sk/archive/2011/08/11/consistent-hashing-intro.html

3.3Quorum NRW

N: 复制的节点数量

R: 成功读操作的最小节点数

W: 成功写操作的最小节点数

W + R > N，强一致性

W + R <=N，最终一致性

详见：http://sebug.net/paper/databases/nosql/Nosql.html#NRW_012323816604251636_2127662_10272764961707637

3.4Vector Clock

对于W=1 R=N的情况，会出现复杂的合并问题。此时可以通过Vector Clock方式解决。如果系统不需要很大弹性，W=N可以简化设计。

详见：http://en.wikipedia.org/wiki/Vector_clock

3.5Gossip

病毒式传播方式，每个节点保持一个Vector Clock和一个state version tree，目前正在被Cassandra使用。

详见：http://sebug.net/paper/databases/nosql/Nosql.html#gossip_34187653195112944_16061_08507828080528557

4.主流NoSQL产品

(1)Big Table(Google)

(2)Dyname(Amazon)

(3)HBase(Apache)

(4)Cassandra(Facebook)

(5)CouchDB(Apache)

(6)MongoDB

(7)Redis

(8)Riak

NoSQL学习笔记(二)之CAP理论

1.CAP概述

CAP理论是由EricBrewer教授提出的，在设计和部署分布式应用的时候，存在三个核心的系统需求，这个三个需求之间存在一定的特殊关系。三个需求如下：

C: Consistency 一致性

A: Availability 可用性

P:Partition Tolerance分区容错性

CAP理论的核心是：一个分布式系统不可能同时很好的满足一致性，可用性和分区容错性这三个需求，最多只能同时较好的满足两个。

2.CAP定义

(1)C: Consistency 一致性

一致性又称为原子性或者事务性。表示一个事务的操作是不可分割的，要不然这个事务完成，要不然这个事务不完成，不会出现这个事务完成了一半这样的情况。这种事务的原子性使得数据具有一致性。

我们通常情况下在数据库中存在的脏数据就属于数据没有具有一致性的表现。而在分布式系统中，经常出现的一个数据不具有一致性的情况是读写数据时缺乏一致性。比如两个节点数据冗余，第一个节点有一个写操作，数据更新以后没有有效的使得第二个节点更新数据，在读取第二个节点的时候就会出现不一致的问题出现。

传统的ACID数据库是很少存在一致性问题的，因为数据的单点原因，数据的存取又具有良好的事务性，不会出现读写的不一致。

(2)A: Availability 可用性

好的可用性主要是指系统能够很好的为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。可用性通常情况下可用性和分布式数据冗余，负载均衡等有着很大的关联。

(3)P:Partition Tolerance分区容错性

分区容错性和扩展性紧密相关。在分布式应用中，可能因为一些分布式的原因导致系统无法正常运转。好的分区容错性要求能够使应用虽然是一个分布式系统，而看上去却好像是在一个可以运转正常的整体。比如现在的分布式系统中有某一个或者几个机器宕掉了，其他剩下的机器还能够正常运转满足系统需求，这样就具有好的分区容错性。

3.CAP理论的意义

随着互联网应用的飞速发展，数据量与日俱增，传统的ACID数据库已经不能满足如此大的海量数据存储了。这个时候需要设计出好的分布式数据存储方式。而这些分布式数据存储方式受到CAP理论的约束，不可能达到高一致性，高可用性，高分区容错性的完美设计。所以我们在设计的时候要懂得取舍，重点关注对应用需求来说比较重要的，而放弃不重要的，在CAP这三者之间进行取舍，设计出贴合应用的存储方案。

目前众多的分布式数据系统通过降低一致性来换取可用性。下面是一个简单的例子：

两个节点数据冗余，第一个节点先有一个写操作，第二个节点后有一个读操作。下面的图中a是整个过程，要具有一致性的话需要等待a1进行write，然后同步到a2，然后a2再进行write，只有整个事务完成以后，a2才能够进行read。但是这样的话使得整个系统的可用性下降，a2一直阻塞在那里等待a1同步到a2。这个时候如果对一致性要求不高的话，a2可以不等待a1数据对于a2的写同步，直接读取，这样虽然此时的读写不具有一致性，但是在后面可以通过异步的方式使得a1和a2的数据最终一致，达到最终一致性。

4.BASE理论

BASE理论是CAP理论结合实际的产物。 BASE(Basically Available, Soft-state,Eventuallyconsistent)英文中有碱的意思，这个正好和ACID的酸的意义相对，很有意思。BASE恰好和ACID是相对的，BASE要求牺牲高一致性，获得可用性或可靠性。

5.CAP之间的取舍

满足一致性，可用性的系统，通常在可扩展性上不太强大：

1. Traditional RDBMSs like Postgres,MySQL, etc (relational)

2. Vertica (column-oriented)

3. Aster Data (relational)

4. Greenplum (relational)

满足一致性，分区容忍必的系统，通常性能不是特别高:

1. BigTable (column-oriented/tabular)

2. Hypertable (column-oriented/tabular)

3. HBase (column-oriented/tabular)

4. MongoDB (document-oriented)

5. Terrastore (document-oriented)

6. Redis (key-value)

7. Scalaris (key-value)

8. MemcacheDB (key-value)

9. Berkeley DB (key-value)

满足可用性，分区容忍性的系统，通常可能对一致性要求低一些:

1. Dynamo (key-value)

2. Voldemort (key-value)

3. Tokyo Cabinet (key-value)

4. KAI (key-value)

5. Cassandra (column-oriented/tabular)

6. CouchDB (document-oriented)

7. SimpleDB (document-oriented)

8. Riak (document-oriented)

6.CAP的反对声音

Guy Pardon写了一篇文章“A CAP Solution (Proving Brewer Wrong)”来反对CAP理论。他提出了一个同时满足CAP的解决方案来反对Brewer的三者只能取其二的说法。

他设计的系统如下：

(1)程序如果能够读取数据库的话读取数据库，如果不能的话可以使用缓存代替。

(2)所有的读取操作使用版本号或者其他可以使用乐观锁的机制。

(3)客户端的所有更新操作全部放在队列中顺序处理。更新操作中要包括该更新的读取操作时的版本信息。

(4)当分区数量足够少的时候，可以处理队列中的更新操作。比较简单的方式是建立一个跨越所有分布式副本的事务，对每个副本进行更新操作（其他方式比如quorum等等也可以）。如果该更新的读取操作时的版本信息不是当前数据库中数据的版本信息，则将失败返回给客户端，否则返回成功。

(5)数据库操作结果（确认或者取消）通过异步的方式发送到客户端，可以通过邮件，消息队列或者其他异步方式。

该系统符合CAP如下：

符合C（高一致性）：读取的数据都是基于快照的，而且错误的更新操作不会执行。

符合A（高可用性）：读取和更新都会返回数据。

符合P（高分区容错性）：允许网络或者节点出错。

该设计是符合BASE理论的。

NoSQL学习笔记(三)之BigTable

对于学习NoSQL的人来说，Google的BigTable的论文是必不可少要阅读的。在NoSQL领域，BigTable算是比较早的也是比较成熟的运用在应用上的产品。Google这么多年的稳定性能足以说明BigTable的优秀。于是最近我也看了BigTable的论文和网上一些关于BigTable的文章，对BigTable有了初步的了解。

1.简单说说BigTable

BigTable是Google提出的一个分布式的海量数据存储系统。Google将其运用在一些数据量较大的应用中。众所周知，对于一个大型的具有海量PV和海量数据的系统来说，其分布式服务是可以通过简单的增加节点进行扩展，但是底层的海量数据则因其单点和需要保持一致性等特点，成为一些大型系统的瓶颈。Google的BigTable就是底层海量数据的一个很好解决方案。从CAP理论来看的话，BigTable的思想是通过在一定程度上放弃底层数据的高可用性，主要加强的数据一致性和可扩展性。

2.BigTable的作用

每一个系统的设计都是为了实现一个问题的解决方案。那么BigTable的作用是什么，是为了解决什么问题的呢？BigTable的设计是为了对海量的数据进行快速存取，相对与普通的数据库而言，BigTable更加注重的是高效的存取性能，而不需要复杂的SQL逻辑。BigTable中无论是数据采用key-value的形式来进行存储，还是采用B+树的数据结构都是为了实现一个高性能的存取为目标的。BigTable用于海量数据，就比如google搜索引擎，google地图这样的操作相对简单的海量数据。而对于一些经常要改变的非海量数据，则使用传统的SQL数据比较合适。

3.BigTable的实现

BigTable将数据存在一个三维有序的表中，这个表除了传统二维表的row，column以外还增加了第三维TimeStamp，用来表示版本。这样rowid，colume family和timestamp就构成了一个三维有序的大表，数据就存储在这张大表中（当然这里的3维存储的格式和传统的数据库有一些不同）。

从上层来看的话，一个数据表就是一个三维有序的表的样子，而在底层来说，这个大表的实现方式则比较巧妙。每个大表被切分成若干个部分称为tablet，各个tablet分布在各个不同的tablet服务器上，这些tablet服务器都包含了缓存，日志和持久存储（这里的持久存储是将数据存储到GFS(Google File System)上去）。在每个服务器上缓存，日志和持久存储相互协作，最大程度的保证了数据的存取性能和安全性能。tablet服务器之间的负载均衡是通过合并与切分tablet来动态实现的，保证了服务器的高效利用。

当然为了提高性能和提高安全性，BigTable有一些其他机制。除了Tablet服务器以外还有Root服务器和Meta服务器，从Root服务器到Meta服务器再到Tablet服务器使用了B+树的数据结构，使得PV性能提高。在Tablet服务器之间存在一个Mater服务器用于统筹管理所有服务器的状态。BigTable还与Chubby紧密联系，添加了BigTable的安全性能。

4.关于BigTable客户端

对于使用BigTable的人来说，需要有一个BigTable的客户端来对BigTable进行调用，通过调用客户端的API来进行操作。BigTable集群中有一个Master服务器用来管理所有的tablet服务器，但是客户端几乎不和Master打交道，客户端存取数据的时候是通过Root-Meta-Tablet服务器的顺序找到相应的tablet，进而直接与tablet进行交互，并且将该tablet的位置缓存在客户端本地，后面则可以跳过Root-Meta服务器直接与tablet服务器交互。

5.BigTable和Google File System(GFS)，MapReduce等

BigTable的设计者是SanjayGhemawat，他是Google公司在分布式系统方面很有成就的一个专家，他设计出了Google的这一套产品，包括GFS,MapReduced等等，这就导致了这一套产品之间是有着很大联系的，BigTable的设计很大程序上受到了其他几个产品的影响。BigTable的底层数据存储是建立在GFS之上的，其分布式的特点和GFS有着极其重大的联系。对于BigTable来说，如果要提高系统的PV性能的话需要扩展其tablet服务器，以减少每个tablet服务器的负载，而要提高系统存储性能的话需要扩展其底层的GFS服务器，扩展其数据的规模。这样将PV的扩展和数据量的扩展分离，使得整个系统更便于管理。另一方面，BigTable与MapReduce可以无缝的连接，不需要将数据从BigTable系统中取出来跑在独立的MapReduce的机器上进行MapReduce的job，可以直接在BigTable的服务器上进行MapReduce的计算。

以下是BigTable和Google其他产品的一些联系：

§ GFS. Bigtable uses the Google FileSystem to store data and log files. Regular StorageMojo.com readers knowGFS imparts all kinds of performance and availability advantages without costlyRAID arrays.

§ Cluster management. Google has a clustermanagement system which so far seems publicly undocumented (maybethey’re embarrassed) that schedules, monitors and manages the Bigtable’scluster.

§ SSTable. This is the underlying fileformat used to store Bigtable data. SSTables are designed so that a data accessrequires, at most, a single disk access. An SSTable, once created, is neverchanged. If new data is added, a new SSTable is created. Once an old SSTable isno longer needed, it is set out for garbage collection. SSTable immutability isat the core of Bigtable’s data checkpointing and recovery routines.

§ Chubby. Cute name, huh? Chubby is thedistributed lock server that allows a multi-thousand node Bigtable cluster tostay coordinated. Chubby itself is a cluster app that maintains five activereplicas, one of which is the master. Like GFS’s master node, Chubby isarchitected to keep lock management traffic very light. Chubby also rules overtablet server life and death, stores access control lists, data schemas and thebootstrap location of Bigtable data.

6.关于BigTable的数据持久化

BigTable的数据存储持久化在GFS上，在每个tablet服务器上都有缓存，当缓存的数据达到一定的条件的时候即将数据以SSTable的形式持久化到GFS上去，在持久化的时候可以选择使用哪种方式进行压缩以提高压缩率。在GFS上的数据通常会有3个备份，这样就保证的数据的可用性。虽然说GFS是有3个备份，具有高可用性，为什么还说BigTable的数据是单点的，可用性不高呢？因为BigTable的数据存取入口是在tablet服务器上的，每个数据只可能存在于一个tablet服务器上，这就是所谓的单点，而一旦这个唯一的服务器挂了以后，在一段时间内这个数据就是无法访问的，这就限制了其高可用性。

7.来看看BigTable的运行情况

The tabletservers were configured to use 1 GB of memory and to write to a GFS cellconsisting of 1786 machines with two 400 GB IDE hard drives each. . . . Each[client]machine had two dual-core Opteron 2 GHz chips, enough physical memoryto hold the working set of all running processes, and a single gigabit Ethernetlink. The machines were arranged in a two-level tree-shaped switched networkwith approximately 100-200 Gbps of aggregate bandwidth available at the root.All of the machines were in the same hosting facility and therefore theround-trip time between any pair of machines was less than a millisecond.

8.关于机器的利用

下面是服务器的一份配置

The tabletservers and master, test clients, and GFS servers all ran on the same set ofmachines. Every machine ran a GFS server. Some of the machines also ran eithera tablet server, or a client process, or processes from other jobs that wereusing the pool at the same time as these experiments.

可见在一台机器上可以同时运行GFS服务器和BigTable服务器，而且还可以运行一些进程。其实，对于机器的利用，需要的是不同种类进程之间的互补，像GFS这样的服务器，比较多的消耗的是磁盘I/O，而对于CPU和内存来说则有很多空闲，BigTable主要消耗内存和磁盘I/O，客户端进程则主要消耗CPU，这样将几个进行互补，则可以充分的利用机器，使其最大程度的为我们服务。

9.BigTable的启示

(1)打破旧框框。对于计算机领域来说，没有什么是真理，一切都是人为创造出来的，而我们所学习所使用的东西只是在一段时间内能够适应需求而已，再过一段时间，或许他们都会被淘汰，而这其中也必然包括了这篇文章提高的BigTable。对于传统数据库不能有效的提供海量数据的存储，Google提出了BigTable的NoSQL方案是一种颠覆性的创造，打破了原有的数据库旧框框，实现了一种可以适应需求的新的系统。这是我们需要学习和提倡的。当然，敢于创造新的事物也是需要付出相当大的努力的，你无法想象BigTable背后有多少辛酸苦辣。

(2)简单即使美。从整体来说BigTable的整体结构是简单的，而简单的方法往往也是最有效的方法。听淘宝的放翁前辈说过，很多设计出来的系统起初很简单，但是为了解决存在的问题使得系统越来越复杂，而结果往往是引入了更多的问题，这样一个复杂的系统就是由于人为的创造问题而产生的。而简单，不仅仅是一种美，更多的是一种睿智和优雅的体现。