iammutex

NoSQL生态系统翻译完稿

iammutex — Sat, 25 Jun 2011 12:26:55 +0800

好久不更新博客了，一方面因为工作比较忙，另外很多东西发到了NoSQLFan上，由于精力有限，个人博客这边就荒于维护了。前段时间在网上看到大作 The Architecture of Open Source Applications ，感觉其13章对NoSQL原理的介绍非常不错，于是萌生翻译的念头，花了半个多月业余时间，昨天终于完稿。现已发布到NoSQLFan上，关注NoSQL技术的同学可以看一下，其内容绝不输Bigtable论文和Dynamo论文。

翻译过程还是比较有意思，虽然其中一些已经烂熟的东西会比较枯燥，但还是常常碰到原来理解不正确或者不清楚的地方，很庆幸在此次翻译中能够得到纠正。

当然，最后还是要说，由于水平有限，错误之处难免，请各位发现错误多多指正。比如其原文中其实有一些不清楚或者不太正确的地方，我在翻译中也加了注释指出。

好了，闲话扯到此，下面请各位移步了：

［HTML版］［PDF版］［NoSQLFan版］

下面是目录：

13.1 NoSQL其名    13.1.1 SQL及其关联型结构
    13.1.2 NoSQL的启示
    13.1.3 特性概述
13.2 NoSQL数据模型及操作模型
    13.2.1 基于key值存储的NoSQL数据模型
        Key-Value 存储
        Key – 结构化数据存储
        Key – 文档存储
        BigTable 的列簇式存储
    13.2.2 图结构存储
    13.2.3 复杂查询
    13.2.4 事务机制
    13.2.5 Schema-free的存储
13.3 数据可靠性
    13.3.1 单机可靠性
        控制fsync的调用频率
        使用日志型的数据结构
        通过合并写操作提高吞吐性能
    13.3.2 多机可靠性
13.4 横向扩展带来性能提升
    13.4.1 如非必要，请勿分片
        读写分离
        使用缓存
    13.4.2 通过协调器进行数据分片
    13.4.3 一致性hash环算法
        Hash环图*
        备份数据
        优化的数据分配策略
    13.4.4 连续范围分区
        BigTable的处理方式
        故障处理
        基于范围分区的NoSQL项目
    13.4.5 选择哪种分区策略
13.5 一致性
    13.5.1 关于CAP理论
    13.5.2 强一致性
    13.5.3 最终一致性
        版本控制与冲突
        冲突解决
        读时修复
        Hinted Handoff
        Anti-Entropy
        Gossip
13.6 写在最后的话
13.7 致谢
相关信息

优雅的Bitcask

iammutex — Sun, 26 Dec 2010 14:14:03 +0800

Bitcask是一个日志型的基于hash表结构和key-value存储模型，我了解到他也就几天时间，但是其简洁有效的设计思路，让我的某种技术癖好得到了极大满足，于是酝酿出这篇东西。

Bitcask模型指导下的存储系统有Riak和豆瓣的beansdb新版本（beansdb新版本信息，参见这里），下面就简单的介绍一下Bitcask模型：

1.日志型的数据文件

何谓日志型？就是append only，所有写操作只追加而不修改老的数据，就像我们的各种服务器日志一样。在Bitcask模型中，数据文件以日志型只增不减的写入文件，而文件有一定的大小限制，当文件大小增加到相应的限制时，就会产生一个新的文件，老的文件将只读不写。在任意时间点，只有一个文件是可写的，在Bitcask模型中称其为active data file，而其他的已经达到限制大小的文件，称为older data file，如下图：

文件中的数据结构非常简单，是一条一条的数据写入操作，每一条数据的结构如下：

上面数据项分别为key，value，key的大小，value的大小，时间戳（应该是），以及对前面几项做的crc校验值。（数据删除操作也不会删除旧的条目，而是将value设定为一个特殊的值以作标示）

数据文件中就是连续一条条上面格式的数据，如下图：

好了，上面是日志型的数据文件，如果数据文件这样持续的存下去，肯定是会无限膨胀的，为了解决个问题，和其他日志型存储系统一样Bitcask也有一个定期的merge操作。

merge操作，即定期将所有older data file中的数据扫描一遍并生成新的data file（没有包括active data file 是因为它还在不停写入），这里的merge其实就是将对同一个key的多个操作以只保留最新一个的原则进行删除。每次merge后，新生成的数据文件就不再有冗余数据了。

2.基于hash表的索引数据

上面讲到的是数据文件，日志类型的数据文件会让我们的写入操作非常快（日志型的优势之一是将磁盘当作磁带，进行顺序读写的效率非常高，可以参见这里），而如果在这样的日志型数据上进行key值查找，那将是一件非常低效的事情。于是我们需要使用一些方法来提高查找效率。

例如在Bigtable中，使用bloom-filter算法为每一个数据文件维护一个bloom-filter 的数据块，以此来判定一个值是否在某一个数据文件中。

而在Bitcask模型中，我们使用了另一种方法，使用了一个基于hash表的索引数据结构。

在Bitcask模型中，除了存储在磁盘上的数据文件，还有另外一块数据，那就是存储在内存中的hash表，hash表的作用是通过key值快速的定位到value的位置。hash表的结构大致如下图所示：

hash表对应的这个结构中包括了三个用于定位数据value的信息，分别是文件id号(file_id)，value值在文件中的位置（value_pos）,value值的大小（value_sz），于是我们通过读取file_id对应文件的value_pos开始的value_sz个字节，就得到了我们需要的value值。整个过程如下图所示：

由于多了一个hash表的存在，我们的写操作就需要多更新一块内容，即这个hash表的对应关系。于是一个写操作就需要进行一次顺序的磁盘写入和一次内存操作。

3.有用的hint file

至此，Bitcask模型基本上已经讲述完成，而这一节讲到的hint file，则是一个有用的技巧，本人认为并不一定是Bitcask模型的必须特性。

从上面我们可以知道，我们称其为索引的hash表，是存储在内存中的，虽然在各自的实现中可以做一些持久化的保证，但是Bitcask模型中并不对在断电或重启后的hash表数据不丢失做出保证。

因此，如果我们不做额外的工作，那么我们启动时重建hash表时，就需要整个扫描一遍我们的数据文件，如果数据文件很大，这将是一个非常耗时的过程。因此Bitcask模型中包含了一个称作hint file的部分，目的在于提高重建hash表的速度。

我们上面讲到在old data file进行merge操作时，会产生新的data file，而Bitcask模型实际还鼓励生成一个hint file，这个hint file中每一项的数据结构，与data file中的数据结构非常相似，不同的是他并不存储具体的value值，而是存储value的位置（像在hash表中的一样），其结构如下图：

这样，在重建hash表时，就不需要再扫描所有data file文件，而仅仅需要将hint file中的数据一行行读取并重建即可。大大提高了利用数据文件重启数据库的速度。

结语：

以上就是Bitcask数据模型的所有内容，非常之精简易懂，但是记住，他只是一个模型，如果我们要实现一个基于Bitcask的存储系统的话，相信还有很多工作要做，还有很多细节可以优化。有兴趣的同学可以看一看Riak或豆瓣beansdb 0.5.2 版本的源码。

参考文献：http://downloads.basho.com/papers/bitcask-intro.pdf

更多资料：http://goo.gl/b7Bqg

Scent of a Woman

iammutex — Wed, 24 Nov 2010 02:39:10 +0800

无论是中文译名《闻香识女人》还是英文名《Scent of a Woman》，都很难让人对电影的内容有正确的联想。当年若不是看到AL Pacino的名字，估计我也是不会去看的。

前几天从“收藏”文件夹里调出来又和大家看了一次，想来大约是第4、5遍了吧，但心情还是在该澎湃的时候澎湃了。看完已经一点左右，趟在床上回味着情节，忽然想到好像写过一篇观后感之类的东西，于是开始翻遍留过脚印的各个角落，最后发现却只是一篇简单推荐，败兴而收，于是萌生写今天这篇东西的想法。

当时同学问这是一部什么电影，我想说是关于人生的，关于选择的，但最后只说了一句，算是励志片吧。但在这里，我要说我从里面读到的人生的选择。

故事一开始，查理近乎懦弱的形象与军官的强势形成对比，在两人渐渐熟悉，军官对查理渐生信任后，他打算用自己的处理哲学帮助查理摆脱当下的困境，他的人生哲学大概就是不折手段的达到目的，什么正直，什么道义，在他眼中都是狗屁。而查理的富二代同学的表现更让他的判断显得更为正确。

然而查理并没有受他的处世方法指导，而是相信自己的正义哲学。军官一方面对查理的不谙世事而气愤，而同时又为查理身上这种正直的精神所打动，而这些，正是他所没有的。这些，是他认为正确，但是在人生的选择中没有勇气去选择的，从这一方面来看，他是羡慕甚至崇敬查理的。

故事的转折出现在军官打算自杀的一幕，查理终于用自己的人生观影响了军官，军官认为自己已成废人，留在世上无用，但是查理用真诚打动了他，让他认识到活着，并不是如他过往的糜烂生活一样才叫有人生，相反，人生的意义不在于成就高低，而在于心底对自己的认同，人生的意义并不在于成就非凡的事业，而在于坚持自己的信念与热爱。就像军官自己说的一样“If you make mistakes, get all tangle up, just tango on”，就像他们旅途同的舞池探戈，街头飚车一样。

故事的高潮当然是最后的激情讲演，讲演的内容非常精彩，而这里面，包含的不仅是为正义的辩护，还有军官的觉醒。

煽情的讲演，在他过往的人生中，那是他再拿手不过的把戏，而在今天，这不再是一个把戏，而是真正的发自内心的呐喊，对自己人生的总结，失败的总结。

他的人生看似辉煌，但是却只是用自己擅长的手段获取到那些浮华的果实，这并不是他想要的，他的内心是多么希望能做正确的选择，走正确的路，但是这条路实在太难了，于是他只能选择堕落，但他无时无刻不在否定自己的人生，于是他挥霍那些通过不正当手段得得来的名利，于是落得如此下场。

然而查理的正直与真诚打动了他，在军官的人生中，他多么希望如果自己做出正确的选择时，能有人挺身而出能为自己辩护，维护自己，但这样的人太少了，所以他不敢听从内心的选择。而今天，他愿意做这样的一个人，也希望说服更多的人做这样的人，让正义与正直能够生存，而不是受到打压。

他成功了，此时的查理，已化作年少时的军官，他已经沉浸在自己选择了正确道路并且一往无前的喜悦与成就感中。

汽车沿着并不平坦的路远去，故事圆满落幕，而后面的路，依旧崎岖，是否还能有一个又有一个良心觉醒的人来维护这个社会的正义。是留给我们永远的思考。

城门不开

iammutex — Sat, 20 Nov 2010 23:24:26 +0800

这里有一座城。

这里原本没有城，但是自从他们来到后，建立了这座城。他们是他和她。他们的名字没人知道，大家知道的是城主和夫人。说这是他们的城，没有人会有异议。外面的世界如何，城主和夫人从不关心，因为这座城有一个神秘之处，任何外界的事物，无城主应允，都无法进入，但任何城中的事物，只要出城，再也无法回来。当然，除了城主和夫人，他们来去自如。

因此外面世界的纷争从来不会波及到这里。这里的一切都很简单，这里的人都很满足，也没有任何人想要出去。世人无比艳羡，当然也不乏觊觎者，他们时刻想毁灭这座完美之城。

那天是城主大寿。虽然没有人知道城主有多少岁，但大家记得八月初八，这是城主的生辰，是夫人的生辰，是这座城的生辰。于是每年八月八成为城里最盛大的节日。这一天，会大开城门，向世人展示城中的富足与和谐，以期消解世间的无畏纷争。

而就在八月初八，夫人被劫！

这天城门大开，门外出现一只三耳玉兔。夫人见到非常喜欢，于是出门追逐，不曾想这是一个埋伏，于是夫人被觊觎者劫。觊觎者出言五日内城主自毁高墙，否则夫人将永不得还。城主最后选择了保住古城，忍痛割爱。

夫人被劫后，城的神秘之处只剩下一半，里面的人依然出不去，但外面的事物，无须城主应允，只要城门打开，便可进入。

于是城主下令：城门不开！

城门不开，又过了多少个春秋，又是一年八月初八，城门外居然出现夫人呼唤，原来夫人已经从觊觎者那里逃脱。三天三夜不停逃奔到城门口。身后不到一里，便是追兵。看门人求城主下令开门，城主只道：城门不开！

城门不开，过了多少春秋。

城门不开，还有多少春秋。

auto-sharding 无用论：auto-sharding vs. manual-sharding

iammutex — Tue, 02 Nov 2010 21:40:47 +0800

一、美好的蓝图

刚接触MongoDB的时候，看到它的auto-sharding功能图，配合上replica sets简直有一种一统世界的感觉。既下图：

图中路由机mongos可以有多台，config机器可以多台配置成主从或者replica sets，sharding的每个结点是三台mongod组成的replica sets。高可用性，无限扩展性尽在眼前。看似宏伟壮观。

然而当我真的打算要用auto-sharding功能的时候，才发现此设计根本不适用，下面谈一点我个人的看法。

Sharding一词的翻译是分片，在这里的意思是将数据进行水平切分。最简单的例子就是我们在数据库设计中的分库分表，在Memcached缓存中的多结点hash存储。而MongoDB的auto-sharding功能重在一个auto（自动化分片）。官方称，使用这一功能，你只需要指定数据分片依赖的某个字段值，既可在不关心具体结点数量的情况下存储你的数据，数据会自动平均分配到后端结点，在增加结点时，数据又会自动的进行迁移，对整个系统进行负载平衡。相比我们传统的分库分表，它是auto（自动）的，而传统方法是manual（手动）的。

二、Foursquare宕机事件

看罢上面的描述，好像没有任何可以挑剔的理由，但事实并不如描绘的那样美好，从Foursquare长达11小时的宕机事件分析中，我们可以看到如下一些问题：

auto-sharding算法导致数据分配不均：事实上数据并不会那么平均的在各个机器间平均分配，由此而造成的短板效应是无法忍受的。
数据迁移代价过大：在增加新的sharding结点时，数据确实会自动的进行迁移，而这种迁移对于原来线上服务的结点，服务上是有影响的。所以我们最好在存储瓶颈到来很早之前就开始做这个迁移，而这样做，和我们手动进行分片，预先估算好数据量相比，优势不再明显。
数据迁移造成碎片：同样是Foursquare的失败经验，在数据迁移时，我们需要迁移的数据通常并不会在磁盘上进行连续存储（除非你的hash条件是天然的insert时间戳）。而我们又知道MongoDB采用的是磁盘空间预分配的机制，于是在数据迁移时，可能并不会减小磁盘占用空间，反而会使得磁盘碎片化。更甚的是由于MongoDB在是采用mmap提速数据访问，磁盘空洞并不会减小mmap的大小，反而导致内存也碎片化。

而以上一些问题，在我们预先规划好存储量的manual-sharding上，是不存在的。

三、冷数据不冷

我认为在存储规划上，可以简单的从两方面来评估，一是磁盘占用，也就是总数据量，二是内存占用，也就是热数据量。热数据在全部数据的中所占的比例，通常会越来越小。造成这一原因的是老数据的访问量下降。我们考虑这样一种情况，如果你的应用用户量和每日新增数据量已经相当稳定，我们以最近三天的数据为热数据进行评估，那么总数据量会随着时间的增长而增长，而热数据量永远是三天的量。我们这里举的是一个极端的例子，可能你的用户量会每天增长，但是热数据量在全部数据中占的比例，通常是越来越少的，这个事实不容反驳。

上面说了这么多，下面我们来看我们的问题。

auto-sharding数据量变化情况：和我们上面说的情况一样，auto-sharding机群会通过增加结点数来扩展集群的存储能力。结点数和数据量成线性的正比关系。
auto-sharding的热数据比例：auto-sharding一旦一个结点配置完成，那么这些机器的内存与磁盘空间比就定了。于是整个集群的热数据比例占所有数据的比例也是一定的。

而对比我们上面的说法，热数据占比例在所有数据中是会越来越小的。于是我们可以认为，auto-sharding中的老结点浪费掉了大量的内存和CPU资源。

而如果我们是人为手动进行分片，我们完全可以自己控制数据的存储，自行设定自己的LRU或者TTL机制，将老数据，冷数据进行存储转移，不再占用高性能机器的各项机能。从而让我们公司花大钱买来的机器能够物尽其用。

好了，就说这一些，理解不一定正确，欢迎探讨，拍砖。

关于NoSQL的思考-为什么我们要优化存储的写性能？

iammutex — Wed, 13 Oct 2010 18:07:01 +0800

在NoSQL的许多产品中，我们通过benchmark可以看到的都是写性能极度提升，而读性能并没有太大的涨幅甚至相对传统RDBMS还有下降。比如Cassandra，MongoDB这两个NoSQL的杰出代表。究其原因，我们可能会想到是因为当前UGC模式已经发展到白热化，用户产生内容导致读写比已经接近或者说小于1：1。

但是我认为这绝不是个中真实原因。

1 缓存导致存储的raw read效率不再重要

真实原因是我们对读的优化已经做得足够多了，数据存储我们使用Memcached，TokyoTyrant/TokyoCabinet等缓存存储，页面及文件缓存我们使用squid，nginx proxy_cache等存储，都可以达到非常好的读缓存效果，如果数据即时性要求不高，或者说缓存设计合理（读写皆缓存），缓存命中率会足够的高，因此我们无需再过分优化底层存储的raw read效率。

试想缓存层如果有高达99％以上的命中率，那么相对于raw read设备，我们的亿级的数据读取请求就轻松的变成百万级请求，上千并发轻松变成数十并发。当然，这需要我们的缓存层足够靠谱。比如nginx proxy_cache 可以多较多，这时候宕掉一台不至于使全部读请求穿透到底层存储。至于多了之后purge等操作如何全面的执行，不在本文讨论之列。

综上，raw read效率不需要再提升，因为其需求已经被缓存层大量取代。

2 无法取代的raw write功能

看到缓存减轻raw read的工作量，我们可以在想是否有方法可以减轻raw write的工作量。答案是不可以的。如果您认为可以。可以留言探讨。既然raw write的工作量是不可取代的，那么我们大概可以有两种方法提升写操作的性能。

3.1 sharding

通过对数据的分区，我们可以将数据进行分布式的存储，于是每个结点只会分配到一部分的raw write请求。这样相当于公司员工效率不变，多招了人。但由于结点的增多，其中有结点出问题的效率也大大增加。于是我们不得不做一些replication操作来提供HA方案。

3.2 提升raw write效率

如上面的举例，我们只能选择提升raw write效率来实现总体（包括cache层）更好的读写效率。这里通常使用的方法就是将随机的写操作在内存中进行序列化，并在一定量后进行顺序的flush到磁盘操作。所谓将内存当成硬盘，将硬盘当作磁带就是这个意思。（可参见我更早的一篇文章：《NoSQL理论之-内存是新的硬盘，硬盘是新的磁带》）所以我们看到前面说到的很多NoSQL产品着重对写操作进行了优化，而对读性能提升并不明显，甚至不惜以更慢的读作为提升写操作性能的代价。

4 总结

由于读性能可以通过设置合理的缓存策略来减少raw read操作的数量。因此不仅对读写比不大的情形需要着重进行写操作的优化，对读写比大的情况下，仍旧需要优化写性能而非读性能。

MongoDB GridFS 数据读取效率 benchmark

iammutex — Wed, 13 Oct 2010 13:50:48 +0800

GridFS 是 MongoDB 下的一个子模块，利用这一模块，可以实现使用MongoDB存储文件，MongoDB 二进制包的bin目录下的mongofile 命令即可模拟实现该功能。

根据反馈，本文给一些朋友造成了一些误解，特声明如下：此测试非本人进行，数据来源于下面链接中博客，有对测试过程中的问题有更好建议的朋友可以在留言中回复，欢迎各种讨论。

数据来源：http://www.coffeepowered.net/2010/02/17/serving-files-out-of-gridfs/
http://www.coffeepowered.net/2010/02/24/serving-files-out-of-gridfs-part-2/

另外一份benchmark数据：http://www.ypass.net/solaris/nginx-gridfs-benchmarks/rawresults.php

目前使用GridFS有以下三种方式：

使用脚本读取，这时文件数据会全部读取到脚本中，再调用脚本客户端的输出功能输出给页面。毫无疑问，这种使用方式是效率非常低下的。
使用gridfs-fuse使GridFS中存的数据可以通过标准磁盘IO方式进行访问，可以说是真正实现了一个文件系统。
使用nginx-gridfs利用Nginx直接读取gridfs中的数据进行发送，这个类似于Nginx的sendfile机制。

文章作者就这几种方式做了测试，得出以下的benchmark数据。

1.1 通过Apache直接读取普通文件

[chris@polaris conf]# ab -n 50000 -c 10 http://advice/images/embed/alliance-60.png
 
Server Software:        Apache/2.2.13
Server Hostname:        advice
Server Port:            80
 
Document Path:          /images/embed/normal_alliance-60.png
Document Length:        31596 bytes
 
Concurrency Level:      10
Time taken for tests:   1.904 seconds
Complete requests:      5000
Failed requests:        0
Write errors:           0
Total transferred:      159463760 bytes
HTML transferred:       158043192 bytes
Requests per second:    2625.37 [#/sec] (mean)
Time per request:       3.809 [ms] (mean)
Time per request:       0.381 [ms] (mean, across all concurrent requests)
Transfer rate:          81767.87 [Kbytes/sec] received
 
Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    1   0.4      1       4
Processing:     1    3   0.5      3       6
Waiting:        0    1   0.4      1       4
Total:          2    4   0.4      4       8
 
Percentage of the requests served within a certain time (ms)
  50%      4
  66%      4
  75%      4
  80%      4
  90%      4
  95%      4
  98%      5
  99%      5
 100%      8 (longest request)

结果：每秒2625次的请求处理，81.77M的吞吐率。

1.2 通过Nginx直接读取普通文件

[chris@polaris conf]# ab -n 50000 -c 10 http://advice:81/images/embed/normal_alliance-60.png
 
Server Software:        nginx/0.8.33
Server Hostname:        advice
Server Port:            81
 
Document Path:          /images/embed/normal_alliance-60.png
Document Length:        31596 bytes
 
Concurrency Level:      10
Time taken for tests:   7.623 seconds
Complete requests:      50000
Failed requests:        0
Write errors:           0
Total transferred:      1590513618 bytes
HTML transferred:       1579863192 bytes
Requests per second:    6559.31 [#/sec] (mean)
Time per request:       1.525 [ms] (mean)
Time per request:       0.152 [ms] (mean, across all concurrent requests)
Transfer rate:          203763.10 [Kbytes/sec] received
 
Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.2      0       9
Processing:     1    1   0.4      1      11
Waiting:        0    0   0.1      0       9
Total:          1    1   0.5      1      12
 
Percentage of the requests served within a certain time (ms)
  50%      1
  66%      1
  75%      1
  80%      2
  90%      2
  95%      2
  98%      3
  99%      3
 100%     12 (longest request)

结果：每秒6559次的请求处理，203.763M的吞吐率。

2.通过gridfs-fuse读取gridfs中的数据

[chris@polaris gridfs-fuse]# ab -n 5000 -c 25 http://advice:81/images/gfs/uploads/user/avatar/4b8347a698db740b30000057/thumb_adrine-big.png
 
Server Software:        nginx/0.8.33
Server Hostname:        advice
Server Port:            81
 
Document Path:          /images/gfs/uploads/user/avatar/4b8347a698db740b30000057/thumb_adrine-big.png
Document Length:        14332 bytes
 
Concurrency Level:      25
Time taken for tests:   5.029 seconds
Complete requests:      5000
Failed requests:        0
Write errors:           0
Total transferred:      72725000 bytes
HTML transferred:       71660000 bytes
Requests per second:    994.22 [#/sec] (mean)
Time per request:       25.145 [ms] (mean)
Time per request:       1.006 [ms] (mean, across all concurrent requests)
Transfer rate:          14121.93 [Kbytes/sec] received
 
Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.1      0       1
Processing:    16   25   1.4     25      52
Waiting:        2   24   1.4     24      52
Total:         17   25   1.4     25      53
 
Percentage of the requests served within a certain time (ms)
  50%     25
  66%     25
  75%     25
  80%     25
  90%     25
  95%     26
  98%     27
  99%     32
 100%     53 (longest request)

结果：每秒994次的请求处理，14.121M的吞吐率。

3 通过nginx-gridfs模块读取gridfs中的数据

[chris@polaris conf]# ab -n 5000 -c 10 http://advice:81/images/gfs/uploads/user/avatar/4b7b2c0e98db7475fc000003/normal_alliance-60.png
 
Server Software:        nginx/0.8.33
Server Hostname:        advice
Server Port:            81
 
Document Path:          /images/gfs/uploads/user/avatar/4b7b2c0e98db7475fc000003/normal_alliance-60.png
Document Length:        31596 bytes
 
Concurrency Level:      10
Time taken for tests:   4.613 seconds
Complete requests:      5000
Failed requests:        0
Write errors:           0
Total transferred:      158580000 bytes
HTML transferred:       157980000 bytes
Requests per second:    1083.88 [#/sec] (mean)
Time per request:       9.226 [ms] (mean)
Time per request:       0.923 [ms] (mean, across all concurrent requests)
Transfer rate:          33570.65 [Kbytes/sec] received
 
Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.0      0       1
Processing:     1    9   4.7      9     103
Waiting:        1    9   4.7      9     102
Total:          2    9   4.7      9     103
 
Percentage of the requests served within a certain time (ms)
  50%      9
  66%      9
  75%      9
  80%      9
  90%      9
  95%      9
  98%      9
  99%     11
 100%    103 (longest request)

结果：每秒1083次的请求处理，33.57M吞吐率。

4 通过Rails客户端读取数据再发送

[chris@polaris nginx-gridfs]$ ab -n 250 -c 4  http://advice/images/gfs/uploads/user/avatar/4b7b2c0e98db7475fc000003/normal_alliance-60.png
 
Server Software:        Apache/2.2.13
Server Hostname:        advice
Server Port:            80
 
Document Path:          /images/gfs/uploads/user/avatar/4b7b2c0e98db7475fc000003/normal_alliance-60.png
Document Length:        31596 bytes
 
Concurrency Level:      4
Time taken for tests:   4.646 seconds
Complete requests:      250
Failed requests:        0
Write errors:           0
Total transferred:      7960000 bytes
HTML transferred:       7899000 bytes
Requests per second:    53.81 [#/sec] (mean)
Time per request:       74.338 [ms] (mean)
Time per request:       18.585 [ms] (mean, across all concurrent requests)
Transfer rate:          1673.10 [Kbytes/sec] received
 
Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.1      0       1
Processing:    15   74  75.6     34     287
Waiting:        0   72  75.8     30     276
Total:         15   74  75.6     34     288
 
Percentage of the requests served within a certain time (ms)
  50%     34
  66%     39
  75%    139
  80%    192
  90%    201
  95%    210
  98%    239
  99%    245
 100%    288 (longest request)

结果：每秒53的请求处理，1.673M的吞吐率（效率确实不可能高）

结论：

Solution	Requests/second	% Apache FS	% Nginx FS	%gridfs-fuse	% Nginx GridFS	% Apache Ruby
Filesystem via Apache	2625.37	-	40.03%	264.06%	242.22%	4,878.96%
Filesystem via Nginx	6559.31	249.84%	-	657.74%	605.17%	12,189.76%
nginx via gridfs-fuse	994.22	37.86%	15.15%	-	91.74%	1847.65%
GridFS via nginx module	1083.88	41.28%	16.52%	109.02%	-	2014.27%
Rails metal handler via Passenger	53.81	2.05%	0.82%	5.41%	4.96%	-

【译】Cassandra 和 HBase 中使用的 BigTable 模型

iammutex — Sat, 09 Oct 2010 22:06:41 +0800

看到一篇好文章，部分翻译在此供大家参考。（PS：翻译部分全部是意译，挑了一些重点进行解释，详尽介绍和未翻译部分请参照原文。具体的一些实现原因，也可以参考我的上一篇文章《NoSQL理论之-内存是新的硬盘，硬盘是新的磁带》）

众所周知，BigTable是NoSQL数据库的王者，其论文更是NoSQL理论的基石，但遗憾的是BigTable不开源，于是有了开源的BigTable版本这一说法，其中的佼佼者包括今天提到的两位：Cassandra和HBase。

本文主要对Cassandra和HBase特性和实现中对BigTable理论的应用。

1.Fundamentally Distributed（分布式存储）

项目从最初规划上，就是为海量数据服务的，当然分布式存储的思想也是扎根于其血脉中。分布式系统主要需要考虑两个方面：partitioning（分区存储，也可以理解为通常说的Sharding）、replication（数据复制，主要是将数据复制成多份以提高可用性）。

2.Column Oriented（列式存储）

和普通的RDBMS不一样，普通的RDBMS通常是行式存储的，一行数据是连续存在一段磁盘空间上的。而列式存储是将各个列分别进行连续的存储。也正是因此，它对于处理字段中的NULL字段，能够不占用过多的空间。同时能够支持灵活松散的列定义。也就是我们通常所说的schema-less。

3.Sequential write（顺序写磁盘）

BigTable型系统的一个特点是其对写性能进行的优化。它的写都是通过先记一条操作日志，然后直接写在内存中的数据集合，然后其集合按条件或定时将数据flush到磁盘。这里涉及到的记操作日志或者数据flush到磁盘都会顺序的磁盘操作。故而避免了磁盘随机操作造成的无谓的磁盘寻道时间。

4.Merged read（读操作数据合并）

上面说到写操作是通过定时将数据直接flush到磁盘进行的，每次flush都会生成一个数据块，那可能造成一个数据在多个数据块中的情况，而在读的时候就需要将这多个版本中的值进行合并。其中在判断一个数据块是否包含指定值时使用了bloom-filter算法。

5.Periodic Data Compaction（定期数据合并）

同样是上面说到的，一个数据可能存在于多个数据块，如果我们不做处理，随着时间的推移，数据块会越来越多。所以BigTable型系统会进行定时的数据合并。在上面讲到的将内存中的数据直接flush到磁盘的过程中，flush之前进行了一次数据的排序操作，既是说存在磁盘中的块中的数据，都是顺序的，那么对一堆顺序的数据进行排重合并，其实和我们熟知的多路归并排序很相似。故而其定时数据合并的效率也是非常高的。

接下来的部分是关于标题中的两个产品Cassandra和HBase在这些理论上的具体实践和修改。暂时就不翻译了。有兴趣的同学可以查看英文原文。

NoSQL理论之-内存是新的硬盘，硬盘是新的磁带

iammutex — Mon, 04 Oct 2010 19:12:24 +0800

“内存是新的硬盘，硬盘是新的磁带”此话出自图灵奖得主Jim Gray。

一、前言

我理解这句话的意思是，我们应该把随机IO都放到内存中去，而把像磁带一样的顺序IO留给硬盘（这里不包括SSD）。

如果应用没有达到一定的级别，可能我们看上面两句话都会觉得太geek，然而在应用数据量日益庞大，动态内容比例日益增大的今天，再忽视这个基本准则将会是一个灾难。

今天我们谈一下这一理论在NoSQL产品中的展现。

二、实现

问题一：宕机数据丢失

我们先看一下几个杰出的NoSQL代表，Cassandra，MongoDB，Redis。他们几乎都使用了同一种存储模式，就是将写操作在内存中进行，定时或按某一条件将内存中的数据直接写到磁盘上。这样做的好处是我们可以充分利用内存在随机IO上的优势，而避免了直接写磁盘带来的随机IO瓶颈：磁盘寻道时间。当然，坏处就是如果遭遇宕机等问题时，可能会丢失一些数据。

解决宕机丢数据的问题有两个方法：

1.实时记录操作日志

这时通常的做法是当一个写操作到达，系统首先会往日志文件里追加一条写记录，成功后再操作内存进行写数据操作。而由于日志文件是不断追加的，因此也就保证了不会有大量的随机IO产生。

2.Quorum NRW

这一理论是基于集群式存储的，其原理是如果集群有N个结点，那么如果我们每次写操作需要至少同步到W个结点才算成功，而每次读操作只要从R个结点读数据就一定能保证其得到正确结果（如果某一结点有此数据，既成功，如果所有R个结点都无数据，则说明无此数据）。而NRW之间的关系必须满足N < R + W 。其实这一理论并不难理解，我们可以将这个不等式做一下移项：R > N – W ，我们有N个结点，写的时候最少写W个才算成功，也就是W个结点有这份数据，那么N-W就是说可能没有某一份数据的最大结点数。最多可能有N-W个结点没有某一数据，那如果我们进行数据读取操作时，读到大于N-W个结点，那么必然有一个以上的结点是有这份数据的。所以要求R > N – W。

所以可能你已经想明白了，为了防止数据丢失，我们采用的实际是简单的冗余备份的方法。数据写到多台机器会比写单台机器的磁盘快吗？对。相对于直接的磁盘操作，跨网络进行内存操作可以更快。其最简单的例子就是改进的一致性hash，（关于一致性hash请看这里）：
上图摘自Amazon的Dynamo文档，key的hash值位于A，B结点间的数据，并不是只存在B结点上，而是顺着环的方向分别在C和D结点进行备份。当然这样做的好处并不完全在于上面说的冗余备份。

当然，很多时候是上面两种解决方法同时使用以保证数据的高可用性。

问题二：内存容量的限制

当我们将内存当作硬盘来用的时候，我们必然会面临容量问题。这也是我们上面说到的数据会定时flush到磁盘的原因，当内存中的数据已经超出可用内存的大小，那么我们就需要将其进行落地操作，对swap的过度使用是不符合我们初衷的，也是达不到高效随机IO的效果的。这里也有两种解决方案：

1.应用层swap

采用这种方法的有 TokyoCabinet 和 Redis 两个产品。TokyoCabinet主要是通过mmap提高IO效率，而其mmap到的只有数据文件头部的一部分内容。一旦数据文件大于其设置的最大mmap长度（由参数xmsize控制），那剩下的部分就是纯粹的低效磁盘操作了。于是它提供了一种类似于Memcached的缓存机制，通过参数rcnum配置，将一些通过LRU机制筛选出来的热数据进行key-value式的缓存，这一部分内存是和mmap占用的内存完全独立的。同样的，Redis在2.0版本之后增加了对磁盘存储的支持，其机制与 TokyoCabinet 类似，也是通过数据操作来判断数据的热度，并将热数据尽量放到内存中。

2.多版本的数据合并

什么叫多版本的数据合并呢？我们上面讲 Bigtable，或其开源版本 Cassandra，都是通过定时将内存中的数据块flush到磁盘中，那么我们会想，如果这次是一个update操作，比如 keyA 的值从 ValueA 变成了 ValueB，那么我们在flush到磁盘的时候就得执行对老数据 ValueA 的清除工作了。而这样，是否就达不到我们希望进行顺序的磁盘IO的目的呢？没错，这样是达不到的，所以 Bigtable 类型的系统确实也并不是这样做的，在flush磁盘的时候，并不会执行合并操作，而是直接将内存数据写入磁盘。这样写是方便很多，那读的时候可能会存在一个值有多个版本的情况，这时就需要我们来进行多版本合并了。所以第二种方法就是将一段时间的写操作写成一个块（可能并非一个文件），保证内存的使用不会无限膨胀。在读取时通过读多个文件块进行数据版本合并来完成。

那如果存储在磁盘的数据量是内存容量的很多倍，我们可能会产生许多个数据块，那么我们在获取数据版本时，是否需要全部遍历所有数据块呢？当然不用，如果你看过BigTable论文，相信你还记得它其中用到了 bloom-filter 算法。bloom-filter 算法最广泛的应用是在搜索引擎爬虫中，它用于判断一个URL是否存在于已抓取集合中，这一算法并不百分之百精准（可能将不在集合中的数据误判为在集合中，但不会出现相反的误差），但其在时间复杂度上仅是几次hash计算，而空间复杂度也非常低。Bigtable 实现中也用到了 bloom-filter 算法，用它来判断一个值是否在某一个集合中。而由于 bloom-filter 算法的特点，我们只会多读（几率很小），不会少读数据块。于是我们就实现对远远大于物理内存容量的数据的存储。

三、结尾

好了，就写到这里，关于NoSQL中对此原理的应用还有更多理解和认识的同学，欢迎交流。

MongoDB MapReduce

iammutex — Wed, 25 Aug 2010 23:12:25 +0800

MapReduce
MapReduce是一种计算模型，简单的说就是将大批量的工作（数据）分解（MAP）执行，然后再将结果合并成最终结果（REDUCE）。这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。

对科班出生的程序员来说，最好的例子莫过于归并排序的例子，没错，归并排序流程就可以看作是一个MapReduce，只是我们在学校写过的归并排序程序可能还没有涉及到并行计算罢了。

上面是MapReduce的理论部分，下面说实际的应用，下面以MongoDB MapReduce为例说明。

下面是MongoDB官方的一个例子：

$ ./mongo
> db.things.insert( { _id : 1, tags : ['dog', 'cat'] } );
> db.things.insert( { _id : 2, tags : ['cat'] } );
> db.things.insert( { _id : 3, tags : ['mouse', 'cat', 'dog'] } );
> db.things.insert( { _id : 4, tags : []  } );
 
> // map function
> m = function(){
...    this.tags.forEach(
...        function(z){
...            emit( z , { count : 1 } );
...        }
...    );
...};
 
> // reduce function
> r = function( key , values ){
...    var total = 0;
...    for ( var i=0; i<values.length; i++ )
...        total += values[i].count;
...    return { count : total };
...};
 
> res = db.things.mapReduce(m,r);
> res
{"timeMillis.emit" : 9 , "result" : "mr.things.1254430454.3" ,
 "numObjects" : 4 , "timeMillis" : 9 , "errmsg" : "" , "ok" : 0}
 
> db[res.result].find()
{"_id" : "cat" , "value" : {"count" : 3}}
{"_id" : "dog" , "value" : {"count" : 2}}
{"_id" : "mouse" , "value" : {"count" : 1}}
 
> db[res.result].drop()

例子很简单，计算一个标签系统中每个标签出现的次数。

这里面，除了emit函数之外，所有都是标准的js语法，当然你也可以使用你所知道的所有标准js函数。而这个emit函数是非常重要的，他的作用是将一条数据放入数据分组集合，这个分组是以emit的第一个参数为key的。你可以这样理解，当你在所有需要计算的行执行完了map函数，你就得到了一组key-values对。基本key是emit中的key，values是每次emit函数的第二个参数组成的集合。

现在我们的任务就是将这一个key-values变在key-value，也就是把这一个集合变成一个单一的值。这个操作就是Reduce。

好像这里和我们前面的理论是完全一样的，其实不然。当我们的key-values中的values集合过大，会被再切分成很多个小的key-values块，然后分别执行Reduce函数，再将多个块的结果组合成一个新的集合，作为Reduce函数的第二个参数，继续Reducer操作。可以预见，如果我们初始的values非常大，可能还会对第一次分块计算后组成的集合再次Reduce。这就类似于多阶的归并排序了。具体会有多少重，就看数据量了。

上面这一内部机制，我们不必非常了解，但我们必须了解这一机制会要求我们遵守的原则，那就是当我们书写Map函数时，emit的第二个参数形式是我们的Reduce函数的第二个参数，而Reduce函数的返回值，可能会作为新的输入参数再次执行Reduce操作，所以Reduce函数的返回值也需要和Reduce函数的第二个参数结构一致。

作为结束，下面照本宣科说一下MongoDB MapReduce调用参数和返回结果。

参数表如下：

db.runCommand(
 { mapreduce : <collection>,
   map : <mapfunction>,
   reduce : <reducefunction>
   [, query : <query filter object>]
   [, sort : <sort the query.  useful for optimization>]
   [, limit : <number of objects to return from collection>]
   [, out : <output-collection name>]
   [, keeptemp: <true|false>]
   [, finalize : <finalizefunction>]
   [, scope : <object where fields go into javascript global scope >]
   [, verbose : true]
 }
);

mapreduce：指定要进行mapreduce处理的collection
map：map函数
reduce：reduce函数
query：一个筛选条件，只有满足条件的行才会加入mapreduce集合，而这个筛选过程是先于整个mapreduce流程而执行的
sort：和query结合的sort排序参数，这是唯一可以优化分组机制的地方
limit：同上
out：结果输出的collection的名字，不指定会默认创建一个随机名字的collection
keytemp：true或false，表明结果输出到的collection是否是临时的，如果为true，则会在客户端连接中断后自动删除，如果你用的是MongoDB的mongo客户端连接，那必须exit后才会删除。如果是脚本执行，脚本退出或调用close会自动删除结果collection
finalize：和map，reduce一样是一个函数，它可以在reduce得出一个结果后再对key和value进行一次计算并返回一个最终结果
scope：设置参数值，在这里设置的值在map，reduce，finalize函数中可见
verbose：在执行过程中打印调试信息。

返回结果结构如下：

{ result : <collection_name>,
  counts : {
       input :  <number of objects scanned>,
       emit  : <number of times emit was called>,
       output : <number of items in output collection>
  } ,
  timeMillis : <job_time>,
  ok : <1_if_ok>,
  [, err : <errmsg_if_error>]
}

result：储存结果的collection的名字
input：满足条件的数据行数
emit：emit调用次数，也就是所有集合中的数据总量
ouput：返回结果条数
timeMillis：执行时间，毫秒为单位
ok：是否成功，成功为1
err：如果失败，这里可以有失败原因，不过从经验上来看，原因比较模糊，作用不大