Chouqin's Blog

A blog for hackers.

《人月神话》读书心得

花几天的时间读完了《人月神话》这本软件工程领域的经典书籍。 本书并不厚,作者的文笔很好,讲述一个观点时能够解释得非常清楚, 翻译得也很不错,没有给理解带来障碍。 书中描述的是作者在上个实际60年代管理大型软件工程项目的一些经验和看法, 可是这些观点拿到现在来看也仍然没有过时。 我在此总结一些我比较有体会的观点,并谈谈我的一些体会。

人月神话

首先是和书名对应的这个观点——“人月神话”, 意思是说尽管一个项目的工作量可以用人月来衡量, 但是“人”和“月”这两个量度并不是可以互换的, 也就是说不能通过增加更多的人手来减少项目完成所需要的时间。 这主要是由于两方面的原因:

  • 有些任务由于次序上的限制不能分解, 也就是说不能把一个任务分给两个人来做来减少一半的时间。
  • 增加了一个人员就增加了培训和交流的成本。

因此,作者提出了Brooks法则:

向进度落后的项目中增加人手,只会使进度更加落后。

这就是除去了神话色彩的人月。

概念完整性

概念完整性是指整个系统的设计具有一致性,系统只反应唯一的设计理念。 这要求系统的设计必须由一个人,或者非常少数互有默契的人员来实现。 在本书中,作者希望按照“外科手术队伍”的形式来组织团队, 团队的首席程序员类似于外科手术队伍的医生,他定义系统的功能, 设计程序,编制源代码,其他的人员负责给首席程序员提供必要的帮助。 或者,可以对设计方法和具体实现进行分工, 由架构师来完成设计,制定好技术说明,而实现人员负责实现。

概念完整性是如此重要,我所知的成功的软件项目都是反应了一两个天才程序员的理念, 由他们来决定整个项目的走向。

没有银弹

这是本书中一个颇具争议的观点:

在未来十年内,无论是在技术还是管理方法上, 都看不出有任何突破性的进步, 能够独立保证在十年内大幅度地提高软件的生产率、可靠性和简洁性。

首先,作者把软件项目的开发过程分为两部分:

  • 根本任务,打造构成抽象软件的复杂概念结构,我理解就是完成软件的设计。
  • 次要任务,使用编程语言表达这些抽象实体,也就是完成实现。

作者认为,现在的技术或管理方法的革新,只能改进次要任务的生产率, 而根本任务的难度并没有发生改变。这样,除非次要任务能够占到所有工作的9/10以上, 否则总体的生产率不会有数量级的提升。

那为什么根本任务的生产率无法提高呢?这是由于开发软件系统需要面对这些无法规避的问题:

  • 复杂度。一个软件系统有大量的状态,存在大量不同元素的相互叠加。 这使得软件系统的复杂性以指数的形式增长。而且,这些复杂度是软件系统的根本属性, 而不像数学和物理中那样可以建立简化的模型而忽略复杂的次要因素。

  • 一致性。复杂度的问题不只是软件工程师才会面对,物理学家也会面临复杂度的问题。 但是他们相信能够建立一个通用的理论将这些复杂性统一起来,因为整个宇宙的规律是由上帝创造的, 而上帝不是反复无常的。而软件工程师需要控制的复杂度是随心所欲,毫无规律可言的, 需要遵循人为惯例和系统约束,需要和这些系统保持一致。 (可以这样理解,这些复杂度是由不同的PM带来的,我没有黑PM啊。。)

  • 可变性。有两个因素导致软件需要经常发生变化, 一是软件系统改变的容易性使得有更多改变的需求(PM说,不就是改两行代码吗? 他绝不会轻易让人去改装一辆生产好的汽车);二是软件的寄主(操作系统,硬件)经常发生变化, 使得软件需要改变。

  • 不可见性。这一点我不是很理解,可能随着图形界面的提出, 软件的可见性能够得到很大程度的改善吧。

似乎,作者提出的这些问题40年后仍然没有得到解决, 对抗软件复杂性和可变性一个比较好的方式是快速原型,然后不断迭代。

2013年终总结

还是踩着年末的尾巴发一篇年终总结吧。

2013对我来说不是平淡的一年。 这一年,我大学毕业,从一所大学来到另外一所大学, 分别原来的同学和朋友, 又在新的地方建立起了人际关系网; 这一年,我从大学生变成了研究生, 伴随着学历的增长,我的生活节奏也完全发生变化, 现在的我,开始沉下心来学习一些东西, 虽然现在仍然没有很大的成果。 这一年,我和她吵了不知道多少次架, 每次都是因我而起,我心里十分愧疚, 我现在仍然不够成熟, 心胸不够开阔。

计划的完成程度

多看书,多感受生活,开阔自己的胸襟

虽然这被放在了计划的第一条,但是完成的最不好。 这里的“看书”,当然是说非专业的书籍, 印象当中就看了《天龙八部》和《唐浩明评点曾国藩家书》(上下册), 家书下册还是这两天逼迫自己看完的, 看书之少,现在都替自己不好意思。

至于修身,也没有花多少功夫, 否则也不至于跟女朋友吵那么多架。 没有把这个放在比较重要的位置, 仍然还是我行我素, 只知道在专业方面努力, 其他方面都不在乎。 这一点,在来年必须要改。

学习一门新的编程语言,可能是go或者erlang

也完成的不是很好,大概的学习了一下go(完成了go tour), 没有用它写过实际的项目。

学完完有关数据挖掘的基础知识

这个完成得还不错, 掌握了很多的机器学习和数据挖掘方面的基础知识。 完成了毕业设计,使用scikit-learn开发过机器学习程序, 写了很多实现机器学习算法的matlab代码。 上了两门机器学习的课程,一门是浙大蔡登老师上的, 另一门是Coursera上的。

为github上的一个库提交代码

TeamToy-Plugin这个项目写了两个插件, 一个是OpenId的,一个是创意墙(团队用户可以在上面分享创意,使用类似于Hacknews的排序, 这个插件没有提交)。

这个计划完成程度也不是很满意,投入的时间太少了。

计划之外

专业书

2013年在专业方面的投入还是蛮多的, 看过的书不能算少,也不能算多:

  1. 《The C Programming Language》,这仅仅只有200多页的书, 除了让我知道如何写出好的C程序之外, 也让我明白了如何如何精简地表达自己的观点。

  2. 《The CPP Programming Language》,以前一直对这本书持保留看法, 觉得这么厚的一本书一定晦涩难懂, 直到我认认真真地把整本书都看了一遍, 才发现这是一本不可多得的好书。 整本书讲解清晰, 把C++这么复杂的一门语言的语言特性阐释得十分清楚, 而且,里面还有很多如何写出更好的程序的技巧, 很多时候作者的很多思想会引起我强烈的共鸣, 或者启发我深度的思考。

  3. 《Introduction to Data Mining》, 这本书总体感觉是介绍性质的,里面设计的理论不是很深, 数学讲解不是很多,不过能从中知道数据挖掘的各个方面。 可能Jiawei Han老师的那本数据挖掘更好一些。

  4. 《Pattern Classification》, 这本书是上机器学习课程的主要教材, 里面的理论讲得很深, 是一本比较好的参考书。

  5. 《The Practice of Programming》, 看这本书,完全是冲着Robert Pike的大名去的, 看完之后果然不失所望, 学到了很多的编程方法, 只是这本书的评注实在让人哭笑不得。

  6. 《Effective Java》, 这本书看的是中文版, 翻译得不是很好, 有少数几个地方有点难以理解。 由于以前写的Java程序太少, 看完这本书之后收益还是蛮大的, 至少现在知道怎么去写Java程序了, 同时对于面向对象的特性也有了更加深入的理解。

应该说,今年看书确实比以往有所长进, 因为看完书之后能够对它进行总结, 其中一些重要的观点和思想都记录下来, 而不是看完就忘记了。 我觉得这是一种很好的看书方法, 看书不应该一味的追求速度, 看完之后的总结很有必要。

Coding

2013年写过的代码不能算多,写的代码是PHP和Python, 但是有时候也看一些其它语言的书和文章, 然后拿着这些特性来进行一个比较, 想得比较多。同时, 有时需要写一些代码来测试一些有趣的语言特性, 这些代码可以作为以后的参考。

同时,今年看了几个开源项目的代码, 包括scrapy和redis, 看这些代码一方面能够开阔自己的视野, 另一方面对于如何写程序也能够有所体会。

Paper

2013年也看过一些论文, 包括google的三大论文, 还有graphlab的4篇论文, Spark的两篇论文。 对于后面的两种论文, 现在理解还不是很深入, 幸亏存在开源的代码能够加深理解。

在机器学习方面也看过一些论文, 其中推荐系统和聚类方面的论文看得比较多。

2014年计划

  1. 修身仍旧还是第一位,而且必须要花一定的时间。
  2. 多看书,多看非专业书。
  3. 看完Graphlab和Spark的源码, 期间需要巩固C++和学习Scala。
  4. 上完Convex Optimization、Probabilistic Graphical Models 和Neural Networks for Machine Learning这三门在线课程。
  5. 在github上为开源项目提交代码。

祝愿所有人新年快乐,新的一年实现自己的梦想。

Bigtable 学习心得

基本介绍

Bigtable是一个分布式的数据库, 它的出现主要是因为传统的关系型数据库在面对大量数据(PB级别)时不具有扩展性。 Bigtable在谷歌内部得到了广泛使用, Apache HBase是它的开源实现。

数据格式

可以把一个Bigtable当成一个持久化的,分布式的,多维的map。 它的值通过(rowkey, columnkey, timestamp)来索引。 其中rowkeycolumnkey和值都可以是任意的字符串。 如下图所示。

Bigtable数据示意图

在上图中,rowkeycom.cnn.www。 在Bigtable中,对row的操作是原子(atomic)的。 在Bigtable中,数据的保存顺序是通过rowkey的字典序来维持的, 基于这个特点,可以通过挑选合适的rowkey把相关的数据放在一起。 比如上图,通过使用倒序的主机名作为rowkey, 可以把同一域名下的网页放在一起。 几个row组合起来形成一个tablet, 一个table由一个或多个tablet组成。

columnkey通过column family来进行划分, 如上图,anchor就是一个column family,它有两个column keyanchor:cnnsi.comanchor:my.look.cn。 contents也是一个column family, 它只有一个column key, 就是contents:column family是访问控制的基本单位。 每一个column key必须以column family:qualifier的格式命名。

对于同一个rowkeycolumnkey的组合, Bigtable根据不同的timestamp保存了不同的值。 通常,会保存最近的几个版本(具体的版本数用户可以指定), 过期的数据会被垃圾回收掉。

API

Bigtable的API非常简单,下面是两个使用API的例子:

写Bigtable
1
2
3
4
5
6
7
8
// Open the table
Table *T = OpenOrDie("/bigtable/web/webtable");
// Write a new anchor and delete an old anchor
RowMutation r1(T, "com.cnn.www");
r1.Set("anchor:www.c-span.org", "CNN");
r1.Delete("anchor:www.abc.com");
Operation op;
Apply(&op, &r1);

上面的代码段对rowkey="com.cnn.www"的行, 将columnkey="anchor:www.c-span.org"的列的值设置为CNN, 同时删除columnkey = "anchor:www.abc.com"的列。其中Apply()是原子操作。

读Bigtable
1
2
3
4
5
6
7
8
9
10
11
12
Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily("anchor");
stream->SetReturnAllVersions();
scanner.Lookup("com.cnn.www");
for (; !stream->Done(); stream->Next()) {
    printf("%s %s %lld %s\n",
            scanner.RowName(),
            stream->ColumnName(),
            stream->MicroTimestamp(),
            stream->Value());
}

上面的代码段遍历rowkey="com.cnn.www"的行中column family="anchor"的所有列的所有版本。

实现

Bigtable使用了几个部件构建而成:

  • GFS,Bigtable的底层依赖GFS,它使用GFS来保存数据和commit log,马上就会讲述细节。
  • Chubby,是Google发布的另外一个分布式系统,它具体的原理我还没有去看那篇论文, 现在只需要知道Bigtable使用Chubby来完成下面的事情:

    • 保证任何时候只有一个bigtable master server
    • 存放Bigtable最开始的数据,用于定位METADATA,接下来会看到。
    • 用于监控tablet server的状态
    • 存放schema
    • 存放ACL(access control list)

    Chubby对于Bigtable非常重要,如果它停止工作了, 那么整个Bigtable也停止工作。 Chubby的开源实现是ZooKeeper, 下次再来研究Chubby。

组成部分

和GFS类似,Bigtable也由三个部分组成,分别是:

  • client:用于和应用程序交互
  • 一个master: 管理整个系统,要做的工作包括分配tablet, 负载均衡,垃圾回收,处理schema的变化。
  • 很多的tablet server:一个tablet server负责多个tablet, client对于tablet的读写请求直接与tablet server进行交互。

需要注意的是,与GFS不一样, 关于tablet的位置信息client不需要通过master就可以知道(接下来就会提到), 所以大部分情况下client都不需要和master交互, 这样master上的压力更小了。

Tablet的位置

Bigtable使用一个三层的结构来存放tablet的位置, 如下图所示。(论文上说这个和B+树比较像, 我倒觉得用inode来类比更加好理解)

首先,一个Chubby File保存了root tablet的位置。 root tablet是一个特殊的METADATA table, 它保存了所有其他METADATA tablet的位置。 每一个METADATA又保存了user tablet的位置。 所以,顺着这个结构走下来,就能找到任意的tablet的位置。

关于这个“位置”,我是这样理解的, 它应该是一个具体的tablet server的名字, client知道了哪个tablet server之后就向那个tablet server发出请求。 如果是这样的话,把tablet重新分配之后master需要去更新这些保存位置的tablet。

这里还有几个计算:

  • 如果一行占的空间是1KB,一个tablet的空间是128MB, 那么这样一个三层的结构能够保存的tablet的数目为$2^{34}$, 这个很容易理解,128MB / 1KB = $2^{17}$,两级下来就是$2^{34}$。
  • 客户端会缓存住tablet的location,这样就不用每次都去读这个层级的结构。 如果客户端没有缓存,那么它读取一个tablet需要3次和tablet server的交互 (读root,METADATA,user tablet各一次)。如果缓存过期了, 最多需要6次和tablet server的交互(对于这个,我的理解是,如果客户端缓存了root tablet的location, 但是它过期了,那么它首先顺着这个结构下去,需要3次,然后发现不对, 又重新向Chubby得到root的位置,又再次顺着这个结构下去3次, 一共6次)。

Tablet的分配

一个tablet一次只会被分配给一个tablet server, master保存下面的信息:

  • 哪些tablet server是正常工作的(alive)
  • 哪些tablet被分配给哪些tablet server
  • 哪些tablet没有被分配(这个只是暂时的,master会把这些tablet分配好,外面看不到这个状态?)

当一个tablet server启动时, 它会去获取Chubby的某个特定目录下的一个文件(一个tablet server唯一的对应这个目录下的一个文件)的互斥锁。 master通过检查这个目录查看哪些tablet server是alive的。 tablet server如果丢失了这个互斥锁,那么它会尝试重新获取, 如果这个文件不存在了,tablet server永远都拿不到这个锁了, 那么它会自动停止。 如果tablet server不工作了,它会释放这个锁, 这样master就知道它没有工作了,把它上面的tablet分配给其他的tablet server。

master会频繁地和那些正常工作的tablet server进行通信来获取它们的状态, 如果tablet server告诉master它失去了锁或者无法和这个tablet server进行通信, 那么master会尝试获取这个tablet server对应的文件锁, 如果能够拿到这个锁,说明Chubby能正常工作, 而这个tablet server要么死掉了要么不能和Chubby交互, 那么master就删除这个tablet server对应的文件, 这样这个tablet server就没用了, 然后master把这个tablet server上的tablet分配给其他的tablet server。

在master启动时,它会执行下面的步骤:

  1. 首先,它会去Chubby上获取master锁,确保同一时间只有一个master工作
  2. 然后,扫描Chubby上的目录(就是上面提到的目录,所有tablet server对应的文件都在这个目录下), 知道哪些tablet server是alive的
  3. 然后,和每个alive的tablet server交互,知道哪些tablet已经被分配了
  4. 最后,便利tablet位置的三层结构(Figure 4),知道一共有哪些tablet, 然后把这些tablet分配给tablet server。

这里有一个问题是,如果METADATA的tablet没有被分配, 那么它就不能被读取,那么第4步就没法进行了。 这个问题可以这样解决,如果需要读取某个tablet时它还没有被分配, 那么先把它分配给某个tablet server,然后就可以继续接下来的步骤。

当下面的情况发生时,tablet的分配情况要进行调整:

  • tablet被创建或删除
  • tablet被合并
  • tablet被切分成两个tablet

前面两种情况都是在master进行的,所以master直接进行调整就行, 而第三种过程是在某个tablet server上进行的, master怎么知道的呢? 当tablet server对tablet进行切分时, 它首先在METADATA的tablet上记录下这个新的tablet, 然后通知master发生了改变。 如果这个通知丢失了, 那么当master去请求这个被切分的tablet时, tablet server会发现这个tablet的METADATA table只是请求的METADATA的一部分, 就知道发生了切分,然后告诉master。

Tablet的保存

下面来看下一个tablet具体是如何保存的。

Tablet的表示

根据这篇博客, 要保存一个tablet,有这么几个部分:

  • 主SSTable,就是持久化的不可变的哈系表,保存在GFS上
  • memtable,在内存中记录最近的修改操作
  • commit log,修改记录,分为compacted和uncompacted(待会会说明)
  • 次SSTable(为了区分两种SSTable,我用了“主”, “次”,不是重要性的区分), 这种SSTable是memtable的持久化版本,次SSTable的存在是为了加快recovery的速度, 因为recovery需要从commit log恢复memtable,同时可以释放memtable的内存

有了这几个部分,对tablet的操作也就变得容易了, 对于写操作,只需要记录把操作记录在commit log中, 同时写入memtable。对于读操作, 由于数据不仅仅保存在主SSTable上, 还需要结合memtable和次SSTable来进行。

Compactions

Compaction主要是为了解决上面过程中出现的问题,它分为3种:

  • minor compaction: 这个操作就是把memtable中的内容保存到SSTable, 释放memtable的内存,同时减小recovery时需要读取的commit log的数目, 已经被保存到次SSTable上的操作对应的commit称为compacted, recovery时只需要从uncompacted的commit log中恢复就行了。
  • merge compaction: 因为每次读取操作时都需要读取主SSTable和相关的次SSTable, 所以次SSTable的数量不能太多,因此, master会把一些次SSTable组合成一个新的次SSTable。
  • major compaction: master把次SSTable和memtable中的内容整合到SSTable里, 这样,就能回收掉修改的和删除的记录所占的空间。

优化

Locality groups

client可以把一些列组放在一起形成一个locality group, 在每一个tablet里面,会为每一个locality group生成一个单独的SSTable, 使用locality group的好处是:

  • 可以提高读的性能,比如把网页的contents放在一个locality group, 而metadata放在另外一个locality group, 这样读取metadata时就不需要读取网页的内容。
  • 可以对于不同的locality采取不同的调优参数。比如, 可以把有些locality group的SSTable放入内存。

Cache

为了提高读性能,tablet server采用了两种级别的cache:

  1. Scan Cache,缓存从SSTable返回的key-value对
  2. Block Cache,缓存从GFS读回来的SSTable的block

Bloom filters

读操作需要结合SSTable和memtable,因此, 可以通过bloom filter来制定某些locality group的数据不可能存在于某些SSTable, 这样就可以减少需要读取的SSTable的数量。 Bloom filter一般保存在tablet server的内存中。

Commit log实现

在Bigtable中,每一个tablet server只保存一个commit log, 这个commit log保存了所有的tablet相关的log。这样做的好处是:

  • 如果每个tablet一个commit log,就会导致同时有很多写请求发到GFS, 这样就会很多的磁盘seek。
  • 这样限制了group commit的作用, 因为只有同一个tablet的写操作才能被合并成一个到一个group commit。

所有tablet的commit log组合成一个文件增加了恢复的复杂性, 因为这样不同的tablet可能被迁移到不同的tablet server, 这样所有相关的tablet server都需要读取这个commit log来获取tablet的信息, 这个commit log会被重复读多次。

解决这个问题的一个办法是在recovery时, 先把commit log使用<table, row name, log sequence number>作为key进行排序, 这样一个tablet的commit log就是连续的,可以通过一次seek, 然后连续读就可以得到。 这个排序的过程也可以通过把这个commit log分成几块,然后并发地进行排序来加快速度。

为了避免GFS集群中由于网络原因或者load情况带来性能上的波动, 通常使用两个线程来完成写commit log的操作, 每一个线程有自己的commit log文件, 同一时课只有一个线程在写, 如果一个线程写出现了性能上的问题, 就切换到另外一个线程(因为两个线程使用了不同的文件, 可能分布到不同的chunkserver)。同时, 使用序列号来消除重复的commit log。

加快recovery

如果master把tablet从一个tablet server移到另一个, 源tablet server可以进行一次minor compaction, 这样uncompacted的commit log就减少了很多, 因为这个过程中可能会有其他的写操作, 所以在upload这个tablet时, 可以再进行一次非常快的minor compaction, 这样就不要进行recovery了。

不变性

利用SSTable的不可变性带来了以下的方便:

  • 缓存。
  • memtable是唯一可变的数据结果,对它使用copy-on-write来消除读写冲突。
  • 回收垃圾只需要回收SSTable就好了。
  • 在split时,child tablet可以使用parent tablet的SSTable。

把博客迁到Octopress

折腾了一个下午,终于把博客迁到到了Octopress。 迁移的原因主要有两点:

  • 喜欢Octopress整体的风格,包括它的响应式设计, 还有特别好看的solarized的语法高亮。

  • 以前在jekyll上写博客,在github上面开了两个库, 原因在于Github Pages上不允许运行ruby脚本, 这样很多功能包括分页就都不能做了。为了完成分页的目的, 我在一个库里保存博客的源代码,使用jekyll来生成静态页面, 然后另一个库也就是chouqin.github.io就完全是静态页面, 把它发布到Github Pages上去。Octopress也是这样, 只不过它省去了我的麻烦,要发布到Github Pages, 只要一条rake deploy就够了,非常方便。

来说一下具体的迁移过程吧。

基础博客搭建

其实完全是照着Octopress的官方文档一步步安装过来的, 官方博客已经写得很清楚了。Ruby管理使用的是rvm

出现了一个问题是rake安装的是10.1.0的版本,跟Gemfile对应的不一致, 直接把Gemfile里的那行改为gem 'rake', '~> 10.1.0'

修改配置

首先是按照文档修改了一些_conf.yml配置:

  • 把使用的markdown改为kramdown
  • 启用pygments来进行语法高亮
  • Aside Bar只显示最近的Post和Github。
  • 配置了disqus_short_name

具体的配置可以查看我的github

使用MathJax

由于使用的是kramdown,它的语法包含数学,为了在页面上展示数学公式, 在source/_includes/head.html上加入以下的内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
<!-- mathjax config similar to math.stackexchange -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
      processEscapes: true
    }
  });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
	skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
	var all = MathJax.Hub.getAllJax(), i;
	for(i=0; i < all.length; i += 1) {
	    all[i].SourceElement().parentNode.className += ' has-jax';
	}
    });
</script>

<script type="text/javascript"
   src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

迁移原来的博文

原来的博客是基于jekyll的,对于每一篇博客,修改这几个地方即可:

  • 删除掉前面的Included file 'JB/setup' not found in _includes directory
  • 在配置上加入comments: true

发布到七牛

因为生成的是静态页面,所以也可以发布到七牛来加速访问。 在部署之前,你需要先注册成为七牛用户, 然后获取AccessKey 和 SecretKey

然后安装七牛的qrsync

octopress目录下创建qiniu.conf,写入以下内容:

1
2
3
4
5
6
7
8
{
    "access_key": "Please apply your access key here",
    "secret_key": "Dont send your secret key to anyone",
    "bucket": "Bucket name on qiniu resource storage",
    "sync_dir": "_deploy",
    "async_ops": "",
    "debug_level": 1
}

最后执行qrsync qiniu.conf,就能部署到七牛了。

MapReduce学习心得

简介

对于计算机系的同学来说,MapReduce这个词应该并不陌生, 现在是所谓的“大数据时代”,“大数据”这个词被炒得非常热。 何为“大数据”?随着互联网的发展,现在的数据越来越多, 给原先的技术带来了两方面的挑战,一是存储, 如何存储这些PB级别的数据, 二是分析, 如何对这么大的数据进行分析, 从中提取出有用的信息。

MapReduce就是一个对大数据进行分析的框架。 使用MapReduce,用户只需要定义自己的map函数和reduce函数, 然后MapReduce就能把这些函数分配到不同的机器上去并行的执行, MapReduce帮你解决好调度,容错,节点交互的问题。 这样,一个没有分布式系统编程经验的人也可以利用MapReduce把自己的程序放到几千台机器上去执行。

mapreduce都是来自于函数式编程的概念,map函数接受一条条的纪录作为输入, 然后输出一个个<key, value>对,reduce函数接受<key, values>对, (其中values是每一个key对应的所有的value),通过对这些values进行一个“总结”, 得到一个<key, reduce_value>

比如拿经典的WordCount例子来说,对于文本中的每一个单词wordmap都会生成一个<word, 1>对(注意如果一个文本中一个单词出现多次就生成多个这样的对), reduce函数就会收到<word, 1,...>这样的输入,它的工作就是把所有的1都加起来, 生成一个<word, sum>

MapReduce函数基于键值对进行处理,看起来很简单, 那很多的分析任务不仅仅只是简单的Wordcount而已,能够使用这两个函数来实现吗? 幸运的是,很多的大规模数据分析任务都能通过MapReduce来表达, 这也是为什么MapReduce能够作为一个框架被提出的原因, 在最后一个部分中会给出一些更加复杂的使用MapReduce的例子。

架构

在大概了解了MapReduce之后,我们来看一下它到底是怎么实现的。 我们首先看一下一个MapReduce任务执行完需要经过那些流程, 然后再看一下在实现MapReduce的时候需要考虑的几个因素。

基本流程

我们首先假定把一个任务分成M个mapTask和R个reducetask, 如上图, 整个任务的执行过程如下:

  1. 首先根据map的数量把原来的数据分成M个splits,每一个split对应一个maptask。

  2. 在集群的节点上启动master,M个maptask和N个reducetask, master把split分配给相应的maptask。需要注意的是, 一个集群的节点(又称作一个worker)上可能有多个maptask, 也有可能maptask和reducetask在同一个worker。

  3. 每一个maptask读取自己的split,根据用户定义的map函数生成<key value>对, 把结果保存在本地文件中, 根据key的不一样,结果被写入到R个不同的文件。 这些文件的位置会告知给master,然后master再告知给相应的reducetask。

  4. 当一个reducetask被告知这些文件的位置时,它通过远程调用读取这些文件的内容, 当和这个reducetask相关的所有文件都被读到之后,它把这些内容按照key进行一个排序, 然后就能保证同一个key的所有values同时被传给reduce

  5. reducetask使用用户定义的reduce函数处理上述排序好的数据, 将最终的结果保存到一个Global File System(比如GFS), 这是为了保证数据的可靠性。

文件的保存

在上述的过程中,我们看到maptask的结果被保存在本地, 而把reducetask的结果保存在具有可靠性保证的文件系统上。 这是因为maptask产生的是中间结果,当这些结果被reduce之后, 就可以被扔掉,不需要备份,这样可以节约磁盘空间。 而reducetask产生的是最终结果,需要一定的可靠性保证。

split的粒度

在对一个任务进行划分时,需要考虑split的粒度:

  • 如果split太小,M就会很大, master需要纪录的数据就会很多, 就会消耗很多master的内存。

  • 如果split太大,一方面调度不具有灵活性, 因为调度是以split为单位的,一个较大的task无法被分割放到其他空闲的worker上去执行。 另一方面无法利用locality进行调度, 因为maptask的输入文件一般保存在分布式文件系统上, master在调度时尽量把一个split分配到较近的节点上去执行, 如果split太大超过了一个文件block的大小, 这样可能两个block在不同的节点上,甚至跨了不同的机架, 这样无法利用locality了。

所以,在实际应用中,split的大小为一个block。

容错

由于MapReduce被分布到上千台机器上去执行, 错误是不可避免的。 MapReduc需要在节点发生故障时进行处理。

当一个节点发生故障, 在这个节点上的所有的maptask都需要重新执行, 因为maptask的结果是保存在节点本地的, 节点发生故障之后,这些结果就不可用了。 而成功执行的reducetask就不需要重新执行了, 因为它的结果是保存在分布式文件系统上, 可靠性是可以保证的。

常见应用

矩阵向量乘法

假设有一个的矩阵M, 它和一个n维列向量v的乘积是一个m维的列向量x,有

可以根据j,把M按列分成k块,把v也对应分成k块, 每个M块和对应的v块被分给一个maptask, maptask生成的结果为对, reducetask把每一个i对应的所有加起来。

关系代数运算

关系数据库表的Join,Selection,Projection, Union, Intersection, Difference,Group And Aggregation等操作都可以使用MapReduce来实现。

值得一提的是,对于Join运算,比如链接关系R(a, b)和关系S(b, c), 在生成以b为键的键值对时,需要指定来自于哪一个关系, 比如关系R生成的键值对的形式为<b, (R, a)>, 这样reduce时就可以根据这个信息进行组合。

矩阵乘法

假设有一个的矩阵M, 和一个的矩阵N, 它们的乘积是一个的矩阵P, 有:

矩阵M和矩阵N的乘法可以看成是关系M(I, J, V)和关系N(J, K, W)先进行一次Join, 再进行一次Group And Aggregation之后的结果, 因此可以直接通过两次MapReduce进行矩阵的乘法运算。

如果想要一次MapReduce就得到结果,可以在map时以(i, k)为键生成键值对, 同样的,需要指明来自于矩阵M还是矩阵N,因此,相应的键值对的格式分别为 (对于矩阵M),(对于矩阵N)。 reduce时进行相应的组合。

GFS学习心得

又好久没写博客了,这几个月来零零散散做了一些事情, 学到的东西很杂,一直都没有形成系统,也没有在某些方面有很深的体会。 有些东西刚刚深入进去看了一点(比如redis,看过一些代码,下次一定要写点心得出来), 还没来得及总结,就被一些其他的事情把时间挤走了。而现在, 时间相对来说比较空闲,可以认真研究一些技术,学得一些东西了。

这几天一直在看The Google File System这篇论文, 看得很慢,一天才能看几页,有些地方还要反反复复看几遍才能“理解”, 但也确实学得了不少东西,包括一些分布式系统设计的基本思想, 以及如何根据应用的具体场景来做设计决策。 诚然,对于一个这么大的系统,要想弄明白它的全部细节是比较困难的, 能够把它的整个过程捋顺就可以了。本文中, 我把我对这篇论文印象比较深的内容用我自己的理解讲出来, 希望能够给对GFS感兴趣的同学一点帮助。

特殊的应用场景

GFS作为一个分布式的文件系统, 除了要满足一般的文件系统的需求之外, 还根据一些特殊的应用场景(原文反复提到的application workloads and technological environment), 来完成整个系统的设计。

分布式文件系统的要求

一般的分布式文件系统需要满足以下四个要求:

  • Performance:高性能,较低的响应时间,较高的吞吐量
  • Scalability: 易于扩展,可以简单地通过增加机器来增大容量
  • Reliability: 可靠性,系统尽量不出错误
  • Availability: 可用性,系统尽量保持可用

(注:关于reliability和availability的区别, 请参考这篇

GFS基于的假设

基于对实际应用场景的研究,GFS对它的使用场景做出了如下假设:

  1. GFS运行在成千上万台便宜的机器上,这意味着节点的故障会经常发生。 必须有一定的容错的机制来应对这些故障。

  2. 系统要存储的文件通常都比较大,每个文件大约100MB或者更大, GB级别的文件也很常见。必须能够有效地处理这样的大文件, 基于这样的大文件进行系统优化。

  3. workloads的读操作主要有两种:

    • 大规模的流式读取,通常一次读取数百KB的数据, 更常见的是一次读取1MB甚至更多的数据。 来自同一个client的连续操作通常是读取同一个文件中连续的一个区域。

    • 小规模的随机读取,通常是在文件某个随机的位置读取 几个KB数据。 对于性能敏感的应用通常把一批随机读任务进行排序然后按照顺序批量读取, 这样能够避免在通过一个文件来回移动位置。(后面我们将看到, 这样能够减少获取metadata的次数,也就减少了和master的交互)

  4. workloads的写操作主要由大规模的,顺序的append操作构成。 一个文件一旦写好之后,就很少进行改动。因此随机的写操作是很少的, 所以GFS主要针对于append进行优化。

  5. 系统必须有合理的机制来处理多个client并发写同一个文件的情况。 文件经常被用于生产者-消费者队列,需要高效地处理多个client的竞争。 正是基于这种特殊的应用场景,GFS实现了一个无锁并发append。

  6. 利用高带宽比低延迟更加重要。基于这个假设, 可以把读写的任务分布到各个节点, 尽量保证每个节点的负载均衡, 尽管这样会造成一些请求的延迟。

使用markdown和reStructuredText生成文档

基本介绍

MarkdownreStructuredText(下面简称rst) 是现在比较流行的轻量级标注语言, 这些语言拥有比较强大的表现力,可以通过简单的书写代码就可以写出包含代码,图片,数学公式等各种格式的文档。 这样,我们不用把心思花在各种格式的调节,而只需要专注于文档的内容就行了。 我们通过标记语言写成的文本文件能够被转化为html, tex, pdf,epub, word等各种格式, 我们只需要利用标记语言提供的语法把文本文件写好,相应的转换器会为你转换为特定的文档格式。 我的博客其实都是使用markdown一个特定版本kramdown写的, 然后转换为html来发布。

学习这些标记语言其实很简单,远远比学习latex简单,把它提供的一些语法都写一遍,比如说怎么写标题, 怎么写列表,怎么插入代码,怎么插入数学符号等等。知道怎么写了之后, 就多练习,写得多了,熟悉之后就会发现,确实能够省去你控制格式的很多烦恼。

使用pandoc

Markdown有很多超集,比如上面提到的kramdown,这些超集在markdown的基础之上有提供了一些功能, 比如说原生的markdown是不支持数学公式的,但kramdown支持, 它可以把你写在两个在源文件中的这样一段markdown代码:

$$
O(g(n)) = \{f(n): \exists c,n, \forall n \geq n_0,  0 \leq f(n) \leq cg(n)\}
$$

转化为这样一段html:

<script type="math/tex; mode=display">
    O(g(n)) = \{f(n): \exists c,n \forall n \geq n_0,  0 \leq f(n) \leq cg(n)\}
</script>

包含这个的html如果里面包含MathJax这个js库的话, MathJax就会把上述的一段html转换为如下的数学公式呈现给你。

毕业论文点滴

已经好久没写博客了,因为寒假一个多月都没看书, 而一回到学校,又要忙着毕业论文的事,所以也无暇顾及这个。 大部分牛人的博客,都是记载着自己正在研究的方面, 在博客中也是向读者传达着一些知识,我们总是可以从其中学到某种东西。 而我,要达到这样的程度要有很长的一段路需要走, 由于技术水平较低,现在的博客记录的仍然还是自己在学习过程中的一些心得和体会, 很大程度上是描述自己的坎坷经历,希望能给某些人一些借鉴,少走一些弯路。

好了,言归正传,这一个月,都在忙着做毕业设计, 包括看论文,写代码,找数据,做实验。一个月的时间, 就完成了这么一件事,效率确实不算高, 主要原因在于对于搞科研还是新手, 很多情况下都是在尝试了各种可能之后才找到方法, 有时一个人的蛮干还不如直接通过其他方式获得出路。 哎,科研就是要耐得住寂寞,不停地调参数,不停地跑数据, 把各种可能性都尝试一遍,之后才有好的结果。

先简单介绍一下我这个论文的要求,论文的题目叫 信息缺失情况下的社区挖掘,其实就是一个聚类算法, 根据节点的某些属性和节点之间的边的关系,把图中的比较接近的节点聚到一起, 形成一个社区。而信息缺失,是指节点中的某些边的关系并不知道, 在这样的情况下进行聚类。采用的办法是首先利用节点之间的属性和边的关系, 通过机器学习方法获取所有节点之间的距离,然后再根据这个距离对节点进行聚类。 下面我来说一下整个的过程。

首先是准备数据。一开始准备爬微博的数据, 所以就去网上搜各种微博的爬虫, 然后终于找到了这个一个简单的分布式新浪微博爬虫, 在这个基础上进行了一点小修改,弄了一个简单的单节点爬虫。 这个爬虫可以抓取用户的微博,用户的个人资料以及用户之间的关注关系。 然后,又使用NLPIR对微博进行分词, 提取出关键字作为用户的属性,同时以用户之间的关注关系作为边,这样就开始实验。 可是,不知道是实验室的网络不稳定还是新浪微博的限制,这个爬虫很难稳定地抓取微博的数据, 最后实在没办法,学长建议我去网上直接找别人爬取到的数据集。 于是,我先后使用了Google+, Facebook, Twitter(这三个数据集都是在Stanford Large Network Dataset Collection上找到的), 和Flixter数据集做实验。其中使用Flixter数据集做出来的结果也还可以,可是师兄说一定要有Ground Truth用于验证, 所以我又只好去找其他的数据集, 最后终于在这找到了可以用于实验的数据集。

然后是实现代码去做实验。这个代码其实两部分,第一部分要利用机器学习去学习一个距离, 第二部分是基于距离进行聚类。为了学习距离,需要求解一个最优化函数, 而这里面涉及的数学的公式好复杂,实现起来也非常困难, 找到了一份和这个论文比较相似的论文的源代码,却发现里面错误好多,有些地方也不知道从哪里开始改。 大概修改了一下就把这个距离拿到第二步去聚类,发现结果非常差, 然后也不知道是第一步的问题还是第二步的问题,但是我就只会改第二步的代码:P。 终于在第二步实在找不出什么错误然后第一步的结果又不好之后,我去问老师, 老师让我使用谱聚类算法来验证距离是不是正确的, 因为谱聚类算法也是基于距离的聚类算法,如果谱聚类算法得不到正确的结果,那就是距离的问题了。 多好的主意啊,我当时怎么就没想到呢,因为我当时还没听说过谱聚类算法。 于是我就拿谱聚类算法去验证,果然是距离没学对,而除了代码没写对之外, 有一个重要的步骤没有做,对Feature做Normalize, 这个步骤对于使用节点的属性来说非常重要,它保证了所有属性的作用是均等的。 而后,我又在这里找到了一些其他的学习距离的算法, 我使用了其中的DCA算法来作为我的第一步,相当靠谱。 通过谱聚类算法验证之后,我发现我的第二步算法就几乎没有什么问题了, 跑出的结果也比较让人满意。

大概就是这么一个比较纠结的过程,总结出一些经验吧:

>>>import this
  1. 写代码还是要多检查,一个bug除了导致几个小时的结果无效,还要浪费更多的时间去找到它。

  2. 在一个步骤保证正确之前,不要急于开展下一步,这样只会增加更多的复杂性。

  3. 沉下心来研究论文,尽量采用和别人一样的方法,得到的结果总是好些,虽然不知道为什么好。

  4. 不要畏惧实验和失败,说不定下一次就是成功的那一次。

  5. 真爱生命,远离科研。

最短路径与最大流

最短路径

在最短路径问题中, 希望在一个图中找出从一个节点到另外一个节点的最短路径, 可能要找出从某一个特定节点到其他节点的最短路径, 也可能是找出所有节点对之间的最短路径, 图中边的权重可能为负值,甚至包含负的回路, 因此,在不同的情况下,有不同的算法适合求解问题, 关于求解所有节点之间的最短路径问题已经在动态规划时详细地解释过Floyd算法, 现在就谈谈两个处理单源最短路径的算法, Dijkstra算法和Bellman-Ford算法。

Dijkstra算法

Dijkstra算法用于求解所有边的权重为非负值时的单源最短路径问题, 它与Prim算法很相似,利用一个集合S保存已经求出最短路径的节点集合, 开始是S只包含源节点s, 每次从V-S中挑选出一个距离S中节点最近的节点u放入S,同时正确地设置u的邻居节点的路径长度, 直到S为V。

对于Dijkstra算法的正确性,只需要递归地证明下面的性质成立:

当节点u被加入到S时,u到s的最短路径已经被正确的设置, 而且u到s的最短路径上的前趋节点w已经被添加进S。
  • 初始化:一开始时,这个性质显然成立
  • 保持:假设当u被添加到S时,u到s的最短路径已经被正确的设置,对于u的任何一个邻接节点v, 如果s到v的最短路径是,那么s到v的路径能够被正确的设置, 而且从v到s最短路径上的前趋节点u已经被添加进S, 这样当v被添加进S时,上述的性质都是能够保持的。

Bellman-Ford算法

Bellman-Ford算法用于求解权重可以为负值时的单源最短路径问题, 而且它还可以用于判断图中是否存在s可达的负的回路。 Bellman-Ford的执行过程就是运行|V|-1次更新操作, 每次更新操作遍历每一条边(u, v)更新dist[v],伪代码如下:

    procedure update((u, v)):
        dist[v] = min(dist[v], dist[u]+w(u, v))

    for k := 1 to |V|-1
        for (u, v) in E:
            update((u, v))

再见2012,你好2013

看着网络上各路牛人的年末总结,也想跟风自己来写一个, 只可惜拖的时间有点长,到现在才开始发表。

2012年对我来说绝对是不一样的一年,求职,面试,外推,实习, 以前对我来说很遥远的事情在这一年真真切切的发生。 有成功,也有失败,有欢笑,也有泪水,有面临抉择时的犹豫不决, 也有选择之后的淡定从容。这些经历,大多是艰辛的, 却没有将我击垮,能让自己觉得人生的充实。世界末日都照样过了, 还有什么挺不过呢?

在学习方面,2012年学习了很多新技术,新的语言, 对于算法,也有了更深入的理解。总的来说,还是广度有余,深度不足。 多多接触一些新的东西当然是有必要的,无论是对于开阔视野还是为了选择一个自己感兴趣的方向, 可是一个人必须要有所专长,在一个方面成为专家,这样才能体现个人的价值, 我在这方面仍然有所欠缺,希望在未来几年能够再某一个方面深入研究下去。 为什么是几年,因为我觉得有所建树,必须经过几年的积累。

在其他方面,相对来说就做得太少了一点,生活显得略微单调了一些。 空闲时间除了打打球,打打dota,似乎就没有干过别的什么事。更让我觉得愧疚的事, 很少看专业方面的其他书,思考的方式也越来越朝着计算机那个非0即1的方向去转了。 现在的情商好像是在下降,在2013年中一定要强迫自己多读书,多读与专业无关的书籍。

今年最好用的工具还是微博,在这上面可以很好地打发时间, 同时可以获取很多很有意思的信息。虽然说能学到的东西很少, 但它确实能很大程度地开阔视野,你能了解到很多你在现实生活中很难碰到的一些人和事。 喜欢微博,喜欢它带给我的快节奏信息。

今年最深的几点感触:

  1. 在面临选择时,不要过分地去权衡利弊,在做出选择之后坚定地超前走才是最重要的。
  2. 不要固执地去争论一个观点的正确性,这并不是一个非黑即白的世界
  3. 严于律己,宽以待人
  4. 多看书,多思考,思考和学习一个都不能落下
  5. 珍惜别人给自己的每一条建议

2013 To-Do-List:

  1. 多看书,多感受生活,开阔自己的胸襟
  2. 学习一门新的编程语言,可能是go或者erlang
  3. 学完完有关数据挖掘的基础知识
  4. 为github上的一个库提交代码

祝愿我的亲人和朋友身体健康,考研的同学考上好的学校, 工作的同学工作顺心。