技术分享——NOSQL软件篇

 

三. 软件篇 - 亚数据库

    我发明的新概念，就是称不上数据库但有一些数据库的特征。可以指缓存。

 

1.MemCached

    Memcached 是danga.com( 运营LiveJournal 的技术团队) 开发的一套分布式内存对象缓存系统，用于在动态系统中减少数据库负载，提升性能。

原理

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

特点

·      协议简单

·      基于libevent 的事件处理

·      内置内存存储方式

·      memcached 不互相通信的分布式

应用方式

 

组件

    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 等等，大家可以根据自己项目的需要，选择合适的客户端来集成。

缓存式的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 次/ 秒

参考网帖

http://blog.developers.api.sina.com.cn/?p=124

http://code.google.com/p/memcached/

http://tech.idv2.com/2008/08/17/memcached-pdf/

 

 

2.dbcached

(1). 基本概念

·      dbcached 是一款基于Memcached 和NMDB 的分布式key-value 数据库内存缓存系统。

·      dbcached = Memcached + 持久化存储管理器 + NMDB 客户端接口

·      Memcached 是一款高性能的，分布式的内存对象缓存系统，用于在动态应用中减少数据库负载，提升访问速度。

·      NMDB 是一款多协议网络数据库(dbm 类) 管理器，它由内存缓存和磁盘存储两部分构成，使用QDBM 或Berkeley DB 作为后端数据库。

·      QDBM 是一个管理数据库的例程库，它参照GDBM 为了下述三点而被开发: 更高的处理速度、更小的数据库文件大小、和更简单的API 。QDBM 读写速度比Berkeley DB 要快。

Benchmark Test of DBM Brothers

http://qdbm.sourceforge.net/benchmark.pdf

 

(2). 结构图

 

(3).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 对于" 读" 大于" 写" 的应用尤其适用。

(4).dbcached 的故障转移支持、设计方向以及与Memcachedb 的不同之处

http://code.google.com/p/dbcached/wiki/Failover

故障转移

先引用memcached 官方网站和PHP 手册中的两段话:

http://www.danga.com/memcached/

If a host goes down, the API re-maps that dead host's requests onto the servers that are available.

http://cn.php.net/manual/zh/function.Memcache-addServer.php

Failover may occur at any stage in any of the methods, as long as other servers are available the request the user won't notice. Any kind of socket or Memcached server level errors (except out-of-memory) may trigger the failover. Normal client errors such as adding an existing key will not trigger a failover.

示例

<?php

/* OO API */

$memcache = new Memcache;

$memcache->addServer('192.168.0.5', 11211);

$memcache->addServer('192.168.0.6', 11211);

$memcache->addServer('192.168.0.7', 11211);

$memcache->addServer('192.168.0.8', 11211);

?>

    当Memcache 客户端使用addServer 服务器池时，是根据"crc32(key) % current_server_num" 哈希算法将key 哈希到不同的服务器的，PHP 、C 和python 的客户端都是如此的算法。Memcache 客户端的addserver 具有故障转移机制，当addserver 了4 台Memcached 服务器，而其中一台宕机了，那么 current_server_num 会由原先的4 变成3 ，这时就会重新哈希了。

    举个例子，假设在4 台服务器都正常的情况下，key 值aaa 被哈希到服务器192.168.0.5 上。如果这时192.168.0.7 宕机了，key 值aaa 就可能就会被重新哈希到服务器192.168.0.6 上，这时就找不到数据了。当然，假设key 值aaa 两次哈希的值是一样，它将仍被哈希到192.168.0.5 上，但是不管怎样，都会导致一部分数据丢失。

    Memcachedb 可以保证数据的持久化存储，但目前还没有解决Memcache 服务器池故障转移导致的数据丢失。而dbcached 可以，它在未命中时会请求后端的NMDB 取回数据。 在接下来的版本中，dbcached 后端的NMDB 将设计为两台，进行互备，届时无论前端 dbcached 中的某几台挂了还是后端NMDB 中的一台挂了，数据都不会丢失。

设计方向

dbcached 和Memcachedb 的设计方向不同，dbcached 的设计方向是发挥Memcached 的内存缓存性能优势，使之成为一个具有" 故障转移" 、" 数据持久化存储" 、" 多服务器同时读写" 的高并发内存缓存系统，它是围绕Memcached 进行开发的。而 Memcachedb 只使用了Memcached 的协议和网络层，抛弃了Memcached 的内存管理部分，使用Berkeley DB 数据库自身的缓存来实现，是围绕Berkeley DB 进行开发的，目前支持类似MySQL 主辅库同步的方式实现读写分离，支持" 主服务器可读写、辅助服务器只读" 模式。

 

四. 软件篇 - 列式系列

1.Hadoop 之Hbase

Hadoop / HBase: API: Java / any writer, Protocol: any write call, Query Method: MapReduce Java / any exec, Replication: HDFS Replication, Written in: Java

 

 

 

2. 耶鲁大学之HadoopDB

 

3.GreenPlum

 

 

 

 

4.FaceBook 之Cassandra

(1). 概述

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

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

网帖

http://cassandra.apache.org/

http://thrift.apache.org/

http://www.slideshare.net/jericevans/an-introduction-to-cassandra

http://wiki.apache.org/cassandra/ClientExamples

http://blog.evanweaver.com/2009/07/06/up-and-running-with-cassandra/

Cassandra 特点

·      灵活的schema ，不需要象数据库一样预先设计schema ，增加或者删除字段非常方便(on the fly) 。

·      支持range 查询，可以对Key 进行范围查询。

·      高可用，可扩展。单点故障不影响集群服务，可线性扩展。

(2). 说明

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

    Cassandra 以单个节点来衡量，其节点的并发读写性能不是特别好，有文章说评测下来Cassandra 每秒大约不到1 万次读写请求，我也看到一些对这个问题进行质疑的评论，但是评价Cassandra 单个节点的性能是没有意义的，真实的分布式数据库访问系统必然是n 多个节点构成的系统，其并发性能取决于整个系统的节点数量，路由效率，而不仅仅是单节点的并发负载能力。

(3). 相关结构

·      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",}

(4).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, value: "hellodba"},

{name: 3, value: "jacky"},

{name: 832416, value: "bigtable"}

{name: 976, value: "Cassandra"}

(5). 结构示例 - Twitter

下面我们看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.

(6). 存储

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

 

(7).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", key, "super_column", "column")

(8). 作者对Cassandra 数据模型的理解( 

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

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

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

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

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

 

 

 

5.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 项目得到了百度的赞助支持，相信其会有更好的发展。

 

 

 

6.Google 之BigTable

   https://developers.google.com/appengine/docs/python/datastore/?hl=zh-CN

    Google AppEngine Datastore 是在BigTable 之上建造出来的，是Google 的内部存储系统，用于处理结构化数据。AppEngine Datastore 其自身及其内部都不是直接访问BigTable 的实现机制，可被视为BigTable 之上的一个简单接口。AppEngine Datastore 所支持的项目的数据类型要比SimpleDB 丰富得多，也包括了包含在一个项目内的数据集合的列表型。如果你打算在Google AppEngine 之内建造应用的话，几乎可以肯定要用到这个数据存储。然而，不像SimpleDB ，使用谷歌网络服务平台之外的应用，你并不能并发地与AppEngine Datastore 进行接口 ( 或通过BigTable) 。

 

 

 

7.Yahoo 之PNUTS

(1). 概述

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

(2). 特点

·      地理分布式，分布在全球多个数据中心。由于大部分Web 应用都对响应时间要求高，因此最好服务器部署在离用户最近的本地机房。

·      可扩展，记录数可支持从几万条到几亿条。数据容量增加不会影响性能。

·      schema-free ，即非固定表结构。实际使用key/value 存储的，一条记录的多个字段实际是用json 方式合并存在value 中。因此delete 和update 必须指定primary key 。但也支持批量查询。

·      高可用性及容错。从单个存储节点到整个数据中心不可用都不会影响前端Web 访问。

·      适合存相对小型的记录，不适合存储大文件，流媒体等。

·      弱一致性保证。

(3).PNUTS 实现

Record-level mastering 记录级别主节点

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

 

(4).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 这样，可以高效的全部加载到内存中。所以比较而言，在实际的应用中，按段分片会更简单，且已经足够使用。

Write 调用示意图

 

(5).PNUTS 感悟

2006 年Greg Linden 就说I want a big, virtual database

What I want is a robust, high performance virtual relational database that runs transparently over a cluster, nodes dropping in an out of service at will, read-write replication and data migration all done automatically.I want to be able to install a database on a server cloud and use it like it was all running on one machine.

http://glinden.blogspot.com/2006/03/i-want-big-virtual-database.html

http://timyang.net/architecture/yahoo-pnuts/

8. 微软之SQL 数据服务

www.microsoft.com/azure/data.mspx

http://www.windowsazure.com/zh-cn/

    SQL 数据服务，是微软Azure 网络服务平台的一部分。该SDS 服务也是处于测试阶段，因此也是免费的，但对数据库大小有限制。 SQL 数据服务其自身实际上是一项处在许多SQL 服务器之上的应用，这些SQL 服务器组成了SDS 平台底层的数据存储。你不需要访问到它们，虽然底层的数据库可能是关系式的；SDS 是一个键/ 值型仓储，正如我们迄今所讨论过的其它平台一样。

    微软看起来不同于前三个供应商，因为虽然键/ 值存储对于可扩性而言非常棒，相对于RDBMS ，在数据管理上却很困难。微软的方案似乎是入木三分，在实现可扩性和分布机制的同时，随着时间的推移，不断增加特性，在键/ 值存储和关系数据库平台的鸿沟之间搭起一座桥梁。

 

五. 软件篇 - 文档存储

1.CouchDB

(1). 概述

CouchDB: API: JSON, Protocol: REST, Query Method: MapReduceR of JavaScript Funcs,

Replication: Master Master, Written in: Erlang, Concurrency: MVCC, Misc:

Links: 3 CouchDB books ?, Couch Lounge ? (partitioning / clusering), ...

它是Apache 社区基于 Erlang/OTP 构建的高性能、分布式容错非关系型数据库系统(NRDBMS) 。它充分利用Erlang 本身所提供的高并发、分布式容错基础平台，并且参考Lotus Notes 数据库实现，采用简单的文档数据类型(document-oriented) 。在其内部，文档数据均以JSON 格式存储。对外，则通过基于HTTP 的REST 协议实现接口，可以用十几种语言进行自由操作。

(2). 结构图

 

*CouchDB 一种半结构化面向文档的分布式、高容错的数据库系统，其提供RESTFul HTTP/JSON 接口。其拥有MVCC 特性，用户可以通过自定义Map/Reduce 函数生成对应的View 。在CouchDB 中，数据是以JSON 字符的方式存储在文件中。

(3). 特性

·      RESTFul API: HTTP GET/PUT/POST/DELETE + JSON

·      基于文档存储，数据之间没有关系范式要求

·      每个数据库对应单个个文件( 以JSON 保存),Hot backup

·      MVCC(Multi-Version-Concurrency-Control) ，读写均不锁定数据库

·      用户自定义View

·      内建备份机制

·      支持附件

·      使用Erlang 开发( 更多的特性)

(4). 应用场景

http://www.javaeye.com/topic/319839

    应用场景在我们的生活中，有很多document ，比如信件、账单、笔记等，他们只是简单的信息，没有关系的需求，我们可能仅仅需要存储这些数据。这样的情况下，CouchDB 应该是很好的选择。当然其他使用关系型数据库的环境，也可以使用CouchDB 来解决。根据CouchDB 的特性，在某些偶尔连接网络的应用中，我们可以用CouchDB 暂存数据，随后进行同步。也可在Cloud 环境中，作为分布式的数据存储。CouchDB 提供给予HTTP 的API ，这样所有的常见语言都可以使用CouchDB 。

使用CouchDB ，意味着我们不需要在像使用RMDBS 一样，在设计应用前首先设计负责数据Table 。我们的开发更加快速，灵活。

 

 

 

2.Riak

Riak: API: JSON, Protocol: REST, Query Method: MapReduce term matching , Scaling:Multiple Masters; Written in: Erlang, Concurrency: eventually consistent (stronger then MVCC via Vector Clocks), Misc: ... Links: talk ?,

3.MongoDB

MongoDB: API: BSON, Protocol: lots of langs, Query Method: dynamic object-based language, Replication: Master Slave, Written in: C++,Concurrency: Update in Place. Misc: ... Links: Talk ?,

(1). 概述

·      MongoDB 是一个介于关系数据库和非关系数据库之间的产品，是非关系数据库当中功能最丰富，最像关系数据库的。他支持的数据结构非常松散，是类似json 的bjson 格式，因此可以存储比较复杂的数据类型。Mongo 最大的特点是他支持的查询语言非常强大，其语法有点类似于面向对象的查询语言，几乎可以实现类似关系数据库单表查询的绝大部分功能，而且还支持对数据建立索引。

·      Mongo 主要解决的是海量数据的访问效率问题，根据官方的文档，当数据量达到50GB 以上的时候，Mongo 的数据库访问速度是MySQL 的10 倍以上。Mongo 的并发读写效率不是特别出色，根据官方提供的性能测试表明，大约每秒可以处理0.5 万－1.5 次读写请求。

·      因为Mongo 主要是支持海量数据存储的，所以Mongo 还自带了一个出色的分布式文件系统GridFS ，可以支持海量的数据存储，但我也看到有些评论认为GridFS 性能不佳，这一点还是有待亲自做点测试来验证了。

·      最后由于Mongo 可以支持复杂的数据结构，而且带有强大的数据查询功能，因此非常受到欢迎，很多项目都考虑用MongoDB 来替代MySQL 来实现不是特别复杂的Web 应用。

(2). 案例

    比方说why we migrated from MySQL to MongoDB 就是一个真实的从MySQL 迁移到MongoDB 的案例，由于数据量实在太大，所以迁移到了Mongo 上面，数据查询的速度得到了非常显著的提升。

blog.boxedice.com/2009/07/25/choosing-a-non-relational-database-why-we-migrated-from-mysql-to-mongodb/

(3).ruby

    MongoDB 也有一个ruby 的项目MongoMapper ，是模仿Merb 的DataMapper 编写的MongoDB 的接口，使用起来非常简单，几乎和DataMapper 一模一样，功能非常强大易用。

 

 

 

4.Terrastore

Terrastore: API: Java & http, Protocol: http, Language: Java, Querying: Range queries,Predicates, Replication: Partitioned with consistent hashing, Consistency: Per-record strict consistency, Misc: Based on Terracotta

5.ThruDB

ThruDB: (please help provide more facts!) Uses Apache Thrift to integrate multiple backend databases as BerkeleyDB, Disk, MySQL, S3.

 

六. 软件篇 - Key Value / Tuple 存储

1.Amazon 之SimpleDB

Amazon SimpleDB: Misc: not open source, Book ?

aws.amazon.com/simpledb/

(1). 概述

    SimpleDB 是一个亚马逊网络服务平台的一个面向属性的键/ 值数据库。SimpleDB 仍处于公众测试阶段；当前，用户能在线注册其" 免费" 版。

(2). 限制 - SimpleDB 有几方面的限制

·      一次查询最多只能执行5 秒钟。

·      除了字符串类型，别无其它数据类型。一切都以字符串形式被存储、获取和比较，因此除非你把所有日期都转为ISO8601 ，否则日期比较将不起作用。

·      任何字符串长度都不能超过1024 字节，这限制了你在一个属性中能存储的文本的大小。不过，由于该模式动态灵活，你可以通过追加多个属性等来绕过这类限制。一个项目最多可以有256 个属性。由于处在测试阶段，SimpleDB 的域不能大于10GB ，整个库容量则不能超过1TB 。

(3). 最终一致性

    SimpleDB 的一项关键特性是它使用一种最终一致性模型。这个一致性模型对并发性很有好处，但意味着在你改变了项目属性之后，那些改变有可能不能立即反映到随后的读操作上。尽管这种情况实际发生的几率很低，你也得有所考虑。比如说，在你的演出订票系统里，你不会想把最后一张音乐会门票卖给5 个人，因为在售出时你的数据是不一致的。

2.Chordless

Chordless: API: Java & simple RPC to vals, Protocol: internal, Query Method: M/R inside value objects, Scaling: every node is master for its slice of namespace, Written in: Java,Concurrency: serializable transaction isolation, Links:

 

 

 

3.Redis

Redis : API: Tons of languages, Written in: C,Concurrency: in memory and saves asynchronous disk after a defined time. Append only mode available. Different kinds of fsync policies. Replication: Master / Slave,

·      Redis 是一个很新的项目，刚刚发布了1.0 版本。Redis 本质上是一个Key-Value 类型的内存数据库，很像memcached ，整个数据库统统加载在内存当中进行操作，定期通过异步操作把数据库数据flush 到硬盘上进行保存。因为是纯内存操作，Redis 的性能非常出色，每秒可以处理超过10 万次读写操作，是我知道的性能最快的Key-Value DB 。

·      Redis 的出色之处不仅仅是性能，Redis 最大的魅力是支持保存List 链表和Set 集合的数据结构，而且还支持对List 进行各种操作，例如从List 两端push 和pop 数据，取List 区间，排序等等，对Set 支持各种集合的并集交集操作，此外单个value 的最大限制是1GB ，不像memcached 只能保存1MB 的数据，因此Redis 可以用来实现很多有用的功能，比方说用他的List 来做FIFO 双向链表，实现一个轻量级的高性能消息队列服务，用他的Set 可以做高性能的tag 系统等等。另外Redis 也可以对存入的Key-Value 设置expire 时间，因此也可以被当作一个功能加强版的memcached 来用。

·      Redis 的主要缺点是数据库容量受到物理内存的限制，不能用作海量数据的高性能读写，并且它没有原生的可扩展机制，不具有可扩展能力，要依赖客户端来实现分布式读写，因此Redis 适合的场景主要局限在较小数据量的高性能操作和运算上。目前使用Redis 的网站有github ，Engine Yard 。

4.Scalaris

Scalaris: Written in: Erlang, Replication: Strong consistency over replicas, Concurrency: non blocking Paxos.

5.Tokyo cabinet / Tyrant

Tokyo Cabinet / Tyrant: Links: nice talk ?, slides ?, Misc: Kyoto Cabinet ?

(1). 概述

http://blog.s135.com/post/362/

    它是日本最大的SNS 社交网站mixi.jp 开发的Tokyo Cabinet key-value 数据库网络接口。它拥有Memcached 兼容协议，也可以通过HTTP 协议进行数据交换。对任何原有Memcached 客户端来讲，可以将Tokyo Tyrant 看成是一个Memcached ，但是，它的数据是可以持久存储的。Tokyo Tyrant 具有故障转移、日志文件体积小、大数据量下表现出色等优势。

    Tokyo Cabinet 2009 年1 月18 日发布的新版本(Version 1.4.0) 已经实现Table Database ，将key-value 数据库又扩展了一步，有了MySQL 等关系型数据库的表和字段的概念，相信不久的将来，Tokyo Tyrant 也将支持这一功能。值得期待。

(2). 数据结构

 

TC 除了支持Key-Value 存储之外，还支持保存Hashtable 数据类型，因此很像一个简单的数据库表，并且还支持基于column 的条件查询、分页查询和排序功能，基本上相当于支持单表的基础查询功能了，所以可以简单的替代关系数据库的很多操作，这也是TC 受到大家欢迎的主要原因之一，有一个Ruby 的项目miyazakiresistance 将TT 的hashtable 的操作封装成和ActiveRecord 一样的操作，用起来非常爽。

(3). 性能及瓶颈

    TC/TT 在mixi 的实际应用当中，存储了2000 万条以上的数据，同时支撑了上万个并发连接，是一个久经考验的项目。TC 在保证了极高的并发读写性能的同时，具有可靠的数据持久化机制，同时还支持类似关系数据库表结构的hashtable 以及简单的条件、分页和排序操作，是一个很棒的NoSQL 数据库。

    TC 的主要缺点是在数据量达到上亿级别以后，并发写数据性能会大幅度下降，NoSQL: If Only It Was ThatEasy 提到，他们发现在TC 里面插入1.6 亿条2-20KB 数据的时候，写入性能开始急剧下降。看来是当数据量上亿条的时候，TC 性能开始大幅度下降，从TC 作者自己提供的mixi 数据来看，至少上千万条数据量的时候还没有遇到这么明显的写入性能瓶颈。

评测

    这个是Tim Yang 做的一个Memcached ，Redis 和Tokyo Tyrant 的简单的性能评测，仅供参考。timyang.net/data/mcdb-tt-redis/

6.CT.M

GT.M: API: M, C, Python, Perl, Protocol: native, inprocess C, Misc: Wrappers: M/DB for SimpleDB compatible HTTP ?, MDB:X for XML ?, PIP for mapping to tables for SQL ?,Features: Small footprint (17MB), Terabyte Scalability, Unicode support, Database encryption,Secure, ACID transactions (single node), eventual consistency (replication), License: AGPL v3 on x86 GNU/Linux, Links: Slides ?,

7.Scalien

Scalien: API / Protocol: http (text, html, JSON), C, C++, Python, Concurrency: Paxos.

8.Berkley DB

Berkley DB: API: Many languages, Written in: C, Replication: Master / Slave, Concurrency:MVCC, License: Sleepycat, BerkleyDB Java Edition: API: Java, Written in: Java, Replication:Master / Slave, Concurrency: serializable transaction isolation, License: Sleepycat

 

 

 

9.MemcacheDB

MemcacheDB: API: Memcache protocol (get, set, add, replace, etc.), Written in: C, Data Model: Blob, Misc: Is Memcached writing to BerkleyDB.

它是新浪互动社区事业部为在Memcached 基础上，增加Berkeley DB 存储层而开发一款支持高并发的分布式持久存储系统，对任何原有Memcached 客户端来讲，它仍旧是个Memcached ，但是，它的数据是可以持久存储的。

 

 

 

10.Mnesia

Mnesia: (ErlangDB ?)

11.LightCloud

LightCloud: (based on Tokyo Tyrant)

12.HamsterDB

HamsterDB: (embedded solution) ACID Compliance, Lock Free Architecture (transactions fail on conflict rather than block), Transaction logging & fail recovery (redo logs), In Memory support – can be used as a non-persisted cache, B+ Trees – supported [Source: Tony Bain ?]

 

 

 

13.Flare

    TC 是日本第一大SNS 网站mixi 开发的，而Flare 是日本第二大SNS 网站green.jp 开发的，有意思吧。Flare 简单的说就是给TC 添加了scale 功能。他替换掉了TT 部分，自己另外给TC 写了网络服务器，Flare 的主要特点就是支持scale 能力，他在网络服务端之前添加了一个node server ，来管理后端的多个服务器节点，因此可以动态添加数据库服务节点，删除服务器节点，也支持failover 。如果你的使用场景必须要让TC 可以scale ，那么可以考虑flare 。

    flare 唯一的缺点就是他只支持memcached 协议，因此当你使用flare 的时候，就不能使用TC 的table 数据结构了，只能使用TC 的key-value 数据结构存储。

 

七. 软件篇 - 最终一致性Key Value 存储

1.Amazon 之Dynamo

(1). 功能特色

·      高可用

·      可扩展

·      总是可写

·      可以根据应用类型优化( 可用性，容错性，高效性配置)

(2). 架构特色

 

特点

·      完全的分布式

·      去中心化( 人工管理工作很小)

·      Key 唯一代表一个数据对象，对该数据对象的读写操通过Key 来完成.

·      通常是一台自带硬盘的主机。每个节点有三个Java 写的组件：请求协调器(request coordination) 、成员与失败检测、本地持久引擎(local persistence engine)

·      数据分区并用改进的一致性哈希(consistent hashing) 方式进行复制，利用数据对象的版本化实现一致性。

·      复制时因为更新产生的一致性问题的维护采取类似 quorum 的机制以及去中心化的复制同步协议。

·      每个实例由一组节点组成，从应用的角度看，实例提供 IO 能力。一个实例上的节点可能位于不同的数据中心内, 这样一个数据中心出问题也不会导致数据丢失。

 

 

 

2.BeansDB

(1). 简介

    BeansDB 是一个主要针对大数据量、高可用性的分布式KeyValue 存储系统，采用HashTree 和简化的版本号来快速同步保证最终一致性( 弱) ，一个简化版的Dynamo 。它采用类似memcached 的去中心化结构，在客户端实现数据路由。目前只提供了Python 版本的客户端，其它语言的客户端可以由memcached 的客户端稍加改造得到。

Google Group: http://groups.google.com/group/beandb/

(2). 特性

·      高可用

    通过多个可读写的用于备份实现高可用。

·      最终一致性

    通过哈希树实现快速完整数据同步( 短时间内数据可能不一致)

·      容易扩展

    可以在不中断服务的情况下进行容量扩展。

·      高性能

    异步IO 和高性能的KeyValue 数据TokyoCabinet 可配置的

·      可用性和一致性

    通过N 、W 、R 进行配置。简单协议:Memcache 兼容协议，大量可用客户端。

(3). 性能

 

3.Nuclear

(1). 说明

    人人网研发中的数据库

http://ugc.renren.com/2010/01/21/ugc-nuclear-guide-use/

http://ugc.renren.com/2010/01/28/ugc-nuclear-guide-theory/

(2). 对比方案

 

(3). 两个设计上的Tips

·      万事皆异步

    我们在编码的过程中走了一些弯路，同步的操作在高并发的情况下带来的性能下降是非常恐怖的，于是乎，Nuclear 系统中任何的高并发操作都消除了Block 。no waiting, no delay 。

·      根据系统负载控制后台线程的资源占用

    Nuclear 系统中有不少的后台线程默默无闻的做着各种辛苦的工作，但是它们同样会占用系统资源，我们的解决方案是根据系统负载动态调整线程的运行和停止，并达到平衡。

 

 

 

4.Voldemort

(1). 说明

    Voldemort 是个和Cassandra 类似的面向解决scale 问题的分布式数据库系统，Cassandra 来自于Facebook 这个SNS 网站，而Voldemort 则来自于Linkedin 这个SNS 网站。说起来SNS 网站为我们贡献了n 多的NoSQL 数据库，例如 Cassandar 、Voldemort 、Tokyo Cabinet 、Flare 等等。Voldemort 的资料不是很多，因此我没有特别仔细去钻研，Voldemort 官方给出Voldemort 的并发读写性能也很不错，每秒超过了1.5 万次读写。

(2). 一个共性问题

 

其实现在很多公司可能都面临着这个抽象架构图中的类似问题。以Hadoop 作为后端的计算集群，计算得出来的数据如果要反向推到前面去，用什么方式存储更为恰当? 再放到DB 里面的话，构建索引是麻烦事；放到Memcached 之类的Key-Value 分布式系统中，毕竟只是在内存里，数据又容易丢。Voldemort 算是一个不错的改良方案。

(3). 值得借鉴的几点

·      键(Key) 结构的设计，有点技巧。

·      架构师熟知硬件结构是有用的。越大的系统越是如此。

·      用好并行。Amdahl 定律以后出现的场合会更多。

(4). 相关网帖

http://project-voldemort.com/

http://www.dbanotes.net/arch/voldemort_key-value.html

http://project-voldemort.com/blog/2009/06/building-a-1-tb-data-cycle-at-linkedin-with-hadoopand-project-voldemort/

5.Dynomite

http://wiki.github.com/cliffmoon/dynomite/dynomite-framework

6.Kai

KAI: Open Source Amazon Dnamo implementation, Misc: slides

http://sourceforge.net/projects/kai/

 

八. 软件篇 - 未分类

1.Skynet

    全新的Ruby MapReduce 实现。2004 年，Google 提出用于分布式数据处理的MapReduce 设计模式，同时还提供了第一个C++ 的实现。现在，一个名为Skynet 的Ruby 实现已经由Adam Pisoni 发布。Skynet 是可适配、可容错的、可自我更新的，而且完全是分布式的系统，不存在单一的失败节点。

(1).Skynet 和Google 在设计上有两点重要的区别

·      Skynet 无法向工作者(Worker) 发送原生代码(Raw code)

·      Skynet 利用结对恢复系统，不同的工作者会互相监控以防失败。

    如果有一个工作者由于某种原因离开或者放弃了，就会有另一个工作者发现并接管它的任务。Skynet 也没有所谓的" 主" 管理进程，只有工作者，它们在任何时间都可以充当任何任务的主管理进程。

(2). 其他说明

·      Skynet 的使用和设置都很容易，这也正是MapReduce 这个概念的真正优势。Skynet 还扩展了ActiveRecord ，加入了MapReduce 的特性，比如distributed_find 。

·      你要为Starfish 编写一些小程序，它们的代码是你将要构建其中的。如果我没有弄错的话，你无法在同一台机器上运行多种类型的MapReduce 作业。Skynet 是一个更全面的MR 系统，可以运行多种类型的多个作业。比如，各种不同的代码。

·      Skynet 也允许失败。工作者会互相关照。如果一个工作者失败了，无法及时完成任务，另一个工作者将会接起这个任务并尝试完成它。Skynet 也支持map_data 流，也就是说，即使某个数据集非常庞大，甚至无法放在一个数据结构中，Skynet 也可以处理。

(3). 什么是map_data 流?

    大多数时候，在你准备启动一个map_reduce 作业时，必须提供一个数据的队列，这些数据已经被分离并将被并行处理。如果队列过大，以至于无法适应于内存怎么办? 在这种情况下，你就要不能再用队列，而应该使用枚举(Enumerable) 。Skynet 知道去对象的调用:next 或者:each 方法，然后开始为" 每一个(each)" 分离出map_task 来。通过这样的方式，不会有人再试图同时创建大量的数据结构。

(4). 应用扩展

    还有很多特性值得一提，不过最想提醒大家的是，Skynet 能够与你现有的应用非常完美地集成到一起，其中自然包括Rails 应用。Skynet 甚至还提供了一个ActiveRecord 的扩展，你可以在模型中以分布式的形式执行一些任务。在Geni 中，我们使用这项功能来运行特别复杂的移植，它通常涉及到在数百万的模型上执行Ruby 代码。> Model.distributed_find(:all, :conditions => "id > 20").each(:somemethod) 在你运行Skynet 的时候，它将在每个模型上执行:somemethod ，不过是以分布式的方式( 这和你拥有多少个工作者相关) 。它在向模型分发任务前不必进行初始化，甚至不必提前获取所有的id 。因此它可以操作无限大的数据集。 用户的反馈如何？

2.Drizzle

    Drizzle 可被认为是键/ 值存储要解决的问题的反向方案。Drizzle 诞生于MySQL(6.0) 关系数据库的拆分。在过去几个月里，它的开发者已经移走了大量非核心的功能( 包括视图、触发器、已编译语句、存储过程、查询缓冲、ACL 以及一些数据类型) ，其目标是要建立一个更精简、更快的数据库系统。Drizzle 仍能存放关系数据；正如MySQL/Sun 的Brian Aker 所说那样:" 没理由泼洗澡水时连孩子也倒掉" 。它的目标就是，针对运行于16 核( 或以上) 系统上的以网络和云为基础的应用，建立一个半关系型数据库平台。

https://launchpad.net/drizzle

 

九. 软件综合对比

1. 可扩展性

 

2. 数据和查询模型

 

(1). 说明

·      当你需要查询或更新一个值的一部分时，Key/value 模型是最简单有效实现。

·      面向文本数据库是Key/value 的下一步，允许内嵌和Key 关联的值. 支持查询这些值数据，这比简单的每次返回整个blob 类型数据要有效得多。

·      Neo4J 是唯一的存储对象和关系作为数学图论中的节点和边。对于这些类型数据的查询，他们能够比其他竞争者快1000s

·      Scalaris 是唯一提供跨越多个key 的分布式事务。

3. 持久化设计

 

(1). 说明

·      内存数据库是非常快的，(Redis 在单个机器上可以完成每秒100,000 以上操作) ，但是数据集超过内存RAM 大小就不行。而且Durability( 服务器当机恢复数据) 也是一个问题。

·      Memtables 和SSTables 缓冲buffer 是在内存中写("memtable") ，写之前先追加一个用于durability 的日志中。但有足够多写入以后，这个memtable 将被排序然后一次性作为"sstable." 写入磁盘中，这就提供了近似内存性能，因为没有磁盘的查询seeks 开销，同时又避免了纯内存操作的durability 问题。( 个人点评 其实Java 中的Terracotta 早就实现这两者结合)

·      B-Trees 提供健壮的索引，但是性能很差，一般和其他缓存结合起来。