我是一只小小鸟

多线程环境下的Observer pattern

2007-06-03T13:01:00.000+08:00

在“The Problem with Threads"论文中提到的用来抨击线程模型的实例。懒得说了，看代码直接：

public class ValueHolder{
private List listeners = new LinkedList();
private int value;

public interface Listener{
public void valueChanged(int newValue);
}

public void addListener(Listener listener){
listeners.add(listener);
}

public void setValue(int newValue){
value = newValue;
Iterator i = copyOfListeners.iterator();
while(i.hasNext()){
((Listener)i.next()).valueChanged(newValue);
}
}
}

以上代码存在问题是多线程环境下对listeners的竞争访问。既然如此，那在addListener和setValue方法前添加synchronzied。好了些，不过有死锁的可能，这主要是因为你不知道别人在valueChanged方法中会做什么，在调用这个方法时，你手中已经紧紧握住一把锁了。继续改进：

public class ValueHolder{
private List listeners = new LinkedList();
private int value;

public interface Listener{
public void valueChanged(int newValue);
}

public synchronized void addListener(Listener listener){
listeners.add(listener);
}

public void setValue(int newValue){
List copyOfListeners;

synchronized(this){
value = newValue;
copyOfListeners = new LinkedList(listeners);
}

Iterator i = copyOfListeners.iterator();
while(i.hasNext()){
((Listener)i.next()).valueChanged(newValue);
}
}
}

此种实现跟JDK源码util包中Observable实现类似，把竞争访问和死锁都排除了。不过此种实现仍存在问题。比如线程A和线程B依次调用setValue，然后线程B抢在线程A之前通知大家。这样就搞得大家认为ValueHolder中最终value值是线程A设置的值，而实际上是线程B设置的值。没办法，只能继续改进。

public class ValueHolder{
private List listeners = new LinkedList();
private int value;
private int seqnum = 0;
private int globalNum = 1;

public interface Listener{
public void valueChanged(int newValue);
}

public synchronized void addListener(Listener listener){
listeners.add(listener);
}

public void setValue(int newValue){
List copyOfListeners;
int localSeqnum;

synchronized(this){
value = newValue;
copyOfListeners = new LinkedList(listeners);
seqnum++;
localSeqnum = seqnum;
}
while(localSeqnum != globalNum){
//Only to wait
}
Iterator i = copyOfListeners.iterator();
while(i.hasNext()){
((Listener)i.next()).valueChanged(newValue);
}
globalNum++;
}
}

以上是我提供的一个实现，不知还有没有问题。关键一点，保证setValue按序执行。

注意：在Java中，局部变量都是线程私有的，不用担心访问冲突，要担心的就是实例变量和类变量。

Thread的层次结构

2007-06-02T17:51:00.000+08:00

要弄清楚Thread的层次结构，必须先弄清楚它的参照系。看看“The Futures of Ruby Threading”这段话：“Current stable releases of Ruby use user space threads (also called "green threads"), which means that the Ruby interpreter takes care of everything to do with threads. This is in contrast to kernel threads, where the creation, scheduling and synchronization is done with OS syscalls, which makes these operations costly, at least compared to their equivalents in user space threads.”这里的用户空间线程和内核线程是相对于Ruby解释器来说的。如果把参照系换成操作系统，此处的内核线程只是一个用户空间线程。

常说Java线程是Native thread，是说Java的一个线程映射到操作系统上的一个用户线程。往下随后怎么映射就要看操作系统的实现了。可以看看Solaris的线程模型，这里也有些说明资料。

不过Java线程也并不一定是一一映射的，比如Jikes RVM虚拟机，采用了M:N模型，而不是大家经常看到的1:1，具体资料可以看这里。BEA的JRockit是两个都有，既支持1:1模型，也支持M:N模型，叫Thin Thread。

在JVM上实现了M:N模型，当然在操作系统上也可以实现M:N模型，只是层次不同，抽象级别不同。象Solaris就实现了M:N模型，不过这个模型在Solaris 9中已经放弃，为什么？实现太难。“It is not to say that a good implementation of the M:N model is impossible,but simply that a good 1:1 implementation is probably sufficient. ”想更进一步了解Solaris多线程的发展历程，看这个pdf吧（www.sun.com/software/whitepapers/solaris9/multithread.pdf）。

了解清楚Thread的层次结构，碰到Green Thread，Native Thread，User space Thread，Kernel Thread时才不会糊涂。

Thread被过度使用

2007-06-02T15:38:00.000+08:00

既然Thread质疑声一片，为什么它仍能够存在呢？原因有：
（1）某些应用程序天生就具有并发特性，而且需要共享地址空间和各种资源，比如数据库服务器。
（2）进程方案开销大。
（3）Java语言大行其道，使得绝大部分程序员认为并发编程唯一也是最好的方式就是采用多线程，而且在Java语言中创建一个线程非常简单。

对于第二点，只有线程创建，线程同步，线程加锁等开销比进程方案开销小，才会真正获益。只是来个线程创建和进程创建开销的比较，那也太天真了。此处，我认为还要包括开发，维护进程并发程序和线程并发程序两种方式之间的开销对比。毕竟，除了机器时间，人的时间也很宝贵。

对于第三点，Java是不是会在以后考虑另外的并发模式。象建立在JVM之上的Scala语言就在采用Actor模式。多个选择，总是不错的主意。不然搞得我们这些开发人员都去用Thread，使得Thread被过度使用，破坏Thread的名声。

附：如果想了解Thread在哪些方面被广泛批评，请参考如下资料：
（1）《The Art of Unix Programming》的“Threads-Threat or Menace？”
（2）“Why Threads Are a Bad Idea”
（3）“The Problem with Threads”

Green Thread不比Native Thread差

2007-05-31T23:32:00.000+08:00

在Ruby实现中，Ruby1.8采用的是Green thread，JRuby和XRuby采用的是Native thread，Rubinius既支持Green thread，也支持Native thread。Ruby1.9将由Green thread转向Native thread。Green thread有哪些不足呢？

在“Ruby Userspace Threads vs GUI tookits Roundup”中重点强调了Green Thread的一个不足：Blocking syscall将阻塞所有其余的线程，而且这个问题在GUI和网络开发中将随处碰到。另外，Green Thread不能有效挖掘多核和多CPU的性能。于是大家都把视线转向Native thread。我对Native thread不感冒，主要是因为shared state concurrency问题多多。具体有哪些，相信你看完“The problem with threads”就会很清楚了。

现在，Erlang很好的解决了Green Thread存在的问题。它没有采用m：1模式，而是采用了m：n模式。Erlang runtime以n个native thread运行，每个都有一个自己的调度器。而且，Erlang采用shared nothing concurrency，可以把Native Thread存在的问题都抛之脑后。

看来XRuby的thread实现可以好好借鉴一下Erlang的并发范式。在看了“The Futures of Ruby Threading”之后，更坚定了应该朝这方面努力。

有了OpenMP，MPI，为什么还要MapReduce？

2007-05-30T22:42:00.000+08:00

OpenMP和MPI是并行编程的两个手段，对比如下：

OpenMP:线程级（并行粒度）；共享存储；隐式（数据分配方式）；可扩展性差；
MPI：进程级；分布式存储；显式；可扩展性好。

OpenMP采用共享存储，意味着它只适应于SMP,DSM机器，不适合于集群。MPI虽适合于各种机器，但它的编程模型复杂：

需要分析及划分应用程序问题，并将问题映射到分布式进程集合；
需要解决通信延迟大和负载不平衡两个主要问题；
调试MPI程序麻烦；
MPI程序可靠性差，一个进程出问题，整个程序将错误；

其中第2个问题感受深刻。每次听我们部门并行组的人做报告，总是听到他们在攻克通信延迟大和负载不平衡的问题。一种并行算法的好坏就看它有没有很好的解决这两个问题。

与OpenMP，MPI相比，MapReduce的优势何在呢？

自动并行；
容错；
MapReduce学习门槛低。

附：

SMP(Symmetric multi-processing)，共享总线与内存，单一操作系统映象。在软件上是可扩展的，而硬件上不能。
DSM（distributed shared memory），SMP的扩展。物理上分布存储；单一内存地址空间；非一致内存访问；单一操作系统映象。

多核意味着什么？

2007-05-30T20:25:00.000+08:00

过去，提升CPU性能的方法有：

时钟速度
执行优化
缓存

此时用户程序无须修改，就可以获得CPU性能提升所带来的好处。现在，提升CPU性能的方法：

超线程
多核
缓存

此时虽然缓存能，但超线程和多核CPU对现在的绝大多数应用，几乎不会有任何影响。多核还说不定会降慢程序的运行，因为多核带来的是更强的并行处理能力、更高的计算密度和更低的时钟频率。如果不采用并发好好利用硬件资源，多核CPU真的是浪费。

另外，还有一些问题需要注意。有了多核，有时候还是感觉应用程序慢，此时问题可能就不是出在CPU上。要知道就算是单核，在日常工作中，CPU的利用率远没有达到100%。有时候，应用程序的瓶颈可能是在I/O，可能在网络，或者数据库，等等。有了计算能力，还有很多工作要做。

Google Groups:JVM Languages

2007-05-30T19:34:00.000+08:00

通过Charles Oliver Nutter博客了解到，他弄了一个Google Groups，目的是讨论如何在JVM之上搞一个框架，以便有更多的语言落户在JVM之上。Motivation何在，我猜是想搞一个“DLR-like”平台。
目前，我主要关注的是xruby，jruby，scala在JVM平台上的实现。

附：
（1）DLR（Dynamic Language Runtime）是Microsoft搭建在CLR之上的一个框架，用来更好的支持动态语言；
（2）Scala：引入Erlang并发范式，建立在JVM之上的语言。

测试Hadoop Trunk代码

2007-05-28T20:48:00.000+08:00

从SVN上checkout代码，然后部署在了两台Linux机器之上。Hadoop版本为0.12.4。过程还是挺顺利的，这得益于以前折腾过Hadoop 0.5版。

如果你在安装的过程中，发现问题，可以参考用Hadoop搭建分布式存储和分布式运算集群。当然你可以通过Email或者Gtalk与我联系。好久没有关注Hadoop了，发现它已经越来越成熟，开始步入实际使用阶段，比如Amazon 的 EC2 和S3。

另外，令人非常兴奋的是，Yahoo推出Pig。从介绍可知，这是一个非常有意思的项目，建立在Hadoop之上。

与搜索相关的研发工作

2007-05-27T22:36:00.000+08:00

想从事与搜索相关的研发工作，需要哪些知识。带着这个疑问，我查看了包括Google，Baidu，Yahoo，腾讯，Sohu，Sina，阿里巴巴等公司的招聘信息。自我总结如下：

为什么要从事研发工作？

在公司处于核心地位；
把研究和开发紧密而完美的结合在一起；

研发职责是什么？

负责搜索引擎系统的架构设计以及核心模块的系统设计；
进行搜索引擎系统核心模块的编码和技术研发；
重点技术难题的攻关；

想从事研发工作，需要什么？

强烈责任心，开放的性格，良好的沟通能力；拥有极强的发现问题、分析问题、解决问题的能力；
Fluency in English(Reading and Writing)；
对算法设计、数据结构有深刻的理解；
精通Linux/Unix平台上的C/C++语言编程，熟练使用调试工具；熟悉网络、多线程编程技术（熟悉Unix系统调用io, socket, process, signal）；如果懂Java，将更好；
能够使用一种脚本语言（perl，shell或者python)；
具有搜索、信息检索相关领域开发经验者优先；
至少熟悉一种数据库系统，你可以选择MySql作为自己重点攻克的对象。

想成为架构师，还需要什么？

熟悉分布式系统架构设计，具备大流量、大访问量、高负载环境下的系统开发及优化经验；
知识面广，思路开阔，对业界的最新技术发展动态有比较密切的关注；
对软件开发生命周期比较熟悉，具备较强的文档编写能力及项目管理能力。

想从事研发工作的朋友可以对照上面的要求，找出自己的不足。对于你来说，那些不足就是最重要的。缺什么，什么就最重要。

Update:一些更加细化的指标，比如：

搜索引擎各子系统(Spider、Indexer、Searcher、分词、网页仓库)的设计和实现。
搜索引擎的性能优化分析和功能升级。

继续写博客，记录自己的成长

2007-05-15T19:54:00.000+08:00

开博多处，不过全都停了下来。今天，重新开始，将在这里记录自己的每一天生活。

（1）嘻嘻哈哈才是我：http://zyxt.blogdriver.com（最早的地方，也是所呆时间最长的地方）。
（2）飞翔的章鱼：http://zyxt.blog.hexun.com/（目前内容已经全部删除！）。
（3）naivebaby：http://blog.csdn.net/naivebaby（技术blog）。
（4）我是一只小小鸟：现在这个（由于当初google blog被禁，于是放弃）。
（5）**blog：（暂且保密）。

btw：这里主要记录我在技术上的一些感悟，要了解我的生活，请访问链接中的"My Childlike Life"!

基本算法连载（14）－BST（Binary Search Tree）的笔记

2006-10-25T20:20:00.000+08:00

插入实现（传指针地址的地址）：


void InsertNode(struct node **node_ptr, struct node *newNode) {
   struct node *node = *node_ptr;
   if (node == NULL)
       *node_ptr = newNode;
   else if (newNode->value <= node->value)
       InsertNode(&node->left, newNode);
   else
       InsertNode(&node->right, newNode);
}

删除节点：


void DeleteNode(struct node*& node) {
   struct node*&amp; temp = node;
   if (node->left == NULL) {
       node = node->right;
       delete temp;
   } else if (node->right == NULL) {
       node = node->left;
       delete temp;
   } else {
       // Node has two children - get max of left subtree
       temp = node->left;
       while (temp->right != NULL) {
           temp = temp->right;
       }
       node->value = temp->value;
       DeleteNode(temp);
   }
}

基本算法连载（13）－递归程序转变成非递归

2006-10-22T13:02:00.000+08:00

用堆栈实现递归其实并没有消除递归，只不过人工做了本来由编译器做的事情。真正的非递归是指运算时所需要的空间是常数，即所需空间与问题的输入规模无关。并非所有递归都可以转换成非递归，比如著名的Ackmann函数。
递归转非递归方法：
（1）用一般公式直接代替。象经常看到的斐波那契数列，它就存在通项公式，而无需采用递归实现。
（2）使用栈来实现
（3）通过Cooper变换、反演变换将一些递归转化为尾递归，从而迭代求出结果
至于什么是Cooper变换，反演变换，这可得好好研究数学。这里贴两个变换实例。

计算阶乘的递归实现（用Haskell实现的，谁都看得懂）：f x ＝ if x = 0 then 1 else f(x-1)*x;
第一步：转变成尾递归


int G(int x, int y)
{
 int x1, y1;

 if (x == 1) {
   return 1 * y;
 } else {   
   x1 = x - 1;
   y1 = x *y;
   return G(x1, y1);
 }
}

int f(int x)
{
 return G(x, 1);
}

第二步：转变成迭代


int G(int x, int y)
{
 int x1, y1;

loop:
 if (x == 1) {
   return 1 * y;
 } else {
   x1 = x - 1;
   y1 = x *y; 
   x = x1
   y = y1;   
   goto loop;
 }
}


求斐波那契值：
f x |x==0 =0
   |x==1 =1
   |otherwise = f (x-1)+f (x-2)

第一步：转变成尾递归
int fib(int n){
   if(n==0)
      return 0;
   return _fib(n,1,0);
}

int _fib(int n,int f1,int f2){
   if(n==1)
      return f1;
   return _fib(n-1,f1+f2,f1);
}

第二步：转变成迭代（略）

基本算法连载（12）－顺序查找的两个实现

2006-10-21T15:03:00.000+08:00

顺序表的实现，天下人都知道，最最简单的一种，不过我还是贴出两个实现，大家看看：


int search(int a[],int key,int length){
int i;
for(i=length-1;i>=0;i--){
if(a[i]==key)
 return i;
}
return -1;
}

/*
* 实际数组元素是从1号位置起开始存储，0号位置存储key
*/
int search(int a[],int key,int length){
int i;
a[0] = key;
for(i=length;!(a[i]==key);i--);
return i;
}

由此，想到了字符串的拷贝实现：


for(i=0;0!=(dst[i]=src[i]);i++);

基本算法连载（11）－两个基本概念：in-place和tail-end recursion

2006-10-16T16:14:00.000+08:00

平时看算法，经常碰到in-place algorithm和tail-end recursion两个概念。今天终于了解了这两个概念。
In-place算法：The input is usually overwritten by the output as the algorithm executes.函数语言是不鼓励或支持in-place算法的，它把overwriiten当作side effect。函数语言，听过不少，没有学过，有时间得学学。
代码：


int sum(int n){
int i;
int sum = 0;
for(i=1;i<=n;i++){
sum = sum+i;
}
return sum;
}

此处的sum就被overwritten，可以算作in-place算法。

Tail-end recursion(tail recursion)：函数所做的最后一件事情是一个函数调用，被称作尾部调用（tail－call）。使用尾部调用的递归程序称为尾部递归。tail-recursion是很容易转变成iteration的。在把尾部递归程序转变成非递归程序时，我们就有了理论保证。尾部调用是可以进行优化的：在尾部进行函数调用时使用一个栈结构覆盖当前的栈结构，同时保持原来的返回地址。
以下的代码展示的是一个更一般化的tail recursion，它先转变成熟悉的tail recursion，然后转变成iteration。看惯了Java代码，看这个还有点不习惯。
代码：


#include <stdlib.h>
typedef struct list{
 int value;
 struct list* next;
}list;

//----------------------------------
//一般化的tail-recursion
list* f(list* input){
 list* head;
 if(input == NULL){
  head = NULL;
 }else{
  head = (list*)malloc(sizeof(list));
  head->value = input->value;
  head->next = f(input->next);
 }
 return head;
}

//------------------------------------
//熟悉的tail-recursion
void fprime(list* input,list** p){
 if(input == NULL){
  *p = NULL;
 }else{
  *p = malloc(sizeof(list));
  (*p)->value = input->value;
  fprime(input->next,&(*p)->next);
 }
}

list* f1(list* input){
 list* head;
 fprime(input,&head);
 return head;
}

//------------------------------------
//iteration
list* f2(list*input){
 list* head;
 list** p;
 p = &head;
 while(input != NULL){
  *p = (list*)malloc(sizeof(list));
  (*p)->value = input->value;
  input = input->next;
  p = &(*p)->next;
 }
 *p = NULL;
 return head;
}

基本算法连载（10）－模式匹配之BM(Boyer-Moore)

2006-10-12T20:05:00.000+08:00

周末两天被BM算法折磨的要死。《a fast string search algorithm》论文中提到的算法思想倒是理解的差不多，但网上（http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140）给出的实现可就是看不懂。通过Baidu，Google一搜，可以看到很多Boyer-Moore的实现。但绝大部分实现都是简化版本，只考虑了bad-character shift，而忽略了good-suffix shift。
它思想的源泉是从右向左匹配字符串将获得更多有用的信息。The algorithm precomputes two tables to process the information it obtains in each failed verification: one table calculates how many positions ahead to start the next search based on the identity of the character that caused the match attempt to fail;the other makes a similar calculation based on how many characters were matched successfully before the match attempt failed.其中前一个称作bad-character shift，后一个称作good-suffix shift。想详细了解Boyer-Moore的思想，我极力推荐看作者发表的论文，它比网上对这个算法介绍的文章容易理解的多。
处理主串为n，模式串为m的情况，此算法的最好表现是：n/m。在这种情况下，只有模式串中的最后一个字符需要比较。不相等，马上可以跳过m个字符。从这里可以看出此算法一个违反直觉的性质：模式串越长，搜索越快。
最优的代码实现（没看懂，明天贴个我自己改的）：

void preBmBc(char *x, int m, int bmBc[]) {
 int i;

 for (i = 0; i < ASIZE; ++i)
    bmBc[i] = m;
 for (i = 0; i < m - 1; ++i)
    bmBc[x[i]] = m - i - 1;
}


void suffixes(char *x, int m, int *suff) {
 int f, g, i;

 suff[m - 1] = m;
 g = m - 1;
 for (i = m - 2; i >= 0; --i) {
    if (i > g && suff[i + m - 1 - f] < i - g)
       suff[i] = suff[i + m - 1 - f];
    else {
       if (i < g)
          g = i;
       f = i;
       while (g >= 0 && x[g] == x[g + m - 1 - f])
          --g;
       suff[i] = f - g;
    }
 }
}

void preBmGs(char *x, int m, int bmGs[]) {
 int i, j, suff[XSIZE];

 suffixes(x, m, suff);

 for (i = 0; i < m; ++i)
    bmGs[i] = m;
 j = 0;
 for (i = m - 1; i >= -1; --i)
    if (i == -1 || suff[i] == i + 1)
       for (; j < m - 1 - i; ++j)
          if (bmGs[j] == m)
             bmGs[j] = m - 1 - i;
 for (i = 0; i <= m - 2; ++i)
    bmGs[m - 1 - suff[i]] = m - 1 - i;
}


void BM(char *x, int m, char *y, int n) {
 int i, j, bmGs[XSIZE], bmBc[ASIZE];

 /* Preprocessing */
 preBmGs(x, m, bmGs);
 preBmBc(x, m, bmBc);

 /* Searching */
 j = 0;
 while (j <= n - m) {
    for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
    if (i < 0) {
       OUTPUT(j);
       j += bmGs[0];
    }
    else
       j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
 }
}

基本算法连载（9）－模式匹配之KMP(Knuth-Pratt-Morris)

2006-10-12T20:02:00.000+08:00

KMP算法，在《数据结构》课上听过，似是非懂，读完大学后全忘光了。Brute-Force算法，简单，谁都知道。从主串S的第pos个字符起与模式串进行比较，匹配不成功时，从主串S的第pos+1个字符重新与模式串进行比较。如果主串S的长度是n，模式串长度是m，那么Brute-Force的时间复杂度是o(m*n)。最坏情况出现在模式串的子串频繁出现在主串S中。虽然它的时间复杂度为o(m*n)，但在一般情况下匹配时间为o(m+n)，因此在实际中它被大量使用。
前几日，重新拾起了KMP算法，然后向MM讲解之。KMP的主要思想是：每当一趟匹配过程中出现字符比较不等时，不需回溯主串S的指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。
模式串到底向右滑动多少，在KMP算法中是用一个数组来存储的。针对模式串中的每个索引j，都将有一个对应的值。此值的含义为模式串中位置从0到j-1构成的串中所出现的首尾相同的子串的最大长度加1。
下面给出具体实现：

/*
* n is the length of text,while m is the length of pattern.
* And pos which is zero-indexed is the start point of search.
*/
int kmp(char* text,int n,char *pattern,int m,int pos){
 int i,j;
 //Generate the array of next
 int* next = (int*)malloc(m*sizeof(int));
 i = 0;
 j = -1;
 next[i] = j;
 while(i<m){
   if((j==-1) || (pattern[i]==pattern[j])){
     i++;
     j++;
     if(pattern[i]!=pattern[j])
      next[i] = j;
     else
      next[i] = next[j];
   }else{
     j = next[j];
   }
 }

 int k = 0;
 for(k=0;k<m;k++)
   printf("next:%d\n",next[k]);

 //Search
 i = pos;
 j = 0;
 while(i<n&&j<m){
   if((j==-1) || (text[i]==pattern[j])){
     i++;
     j++;
   }else{
     j = next[j];
   }
 }
 if(j==m)
    return i-m;
 else
    return 0;
}

KMP算法的时间开销包括两部分，一个是求next数组元素的值，此时的时间开销是o(m)；一个是搜索，此时的时间开销是o(n)。因此，它的时间复杂度是o(m+n)

看《The Google File System》后的一些笔记

2006-10-09T20:08:00.000+08:00

看了基于Google File System思想实现的Hadoop代码，重读了Google的这篇论文《The Google File System》。Paper挺长，网上已经有热心的人把翻译版奉献了出来。在这里，只是把其中的部分内容抽取出来，与大家一起分享。
性能，可扩展性，可靠性，可用性仍然是GFS的目标，但它还有一些与传统分布式文件系统与众不同的东西：
（1）对于大规模的集群系统，机器出现故障很正常，因此系统容错必须十分重视。文件系统必须具有高可用性，数据完整性和相应的诊断工具。通过快速恢复，chunk复制，master复制达到高可用性；通过checksum检查数据完整性；通过log记录系统中出现的各种事件，以便诊断错误。
（2）传统文件系统的block的大小只有几k，而GFS将选用64M，以满足当前出现的越来越庞大的数据集处理需求。选用大的chunk size，可以：
a、减少与master的交互次数；
b、大部分的时候，对chunk的操作都集中在一个chunk上，因此可以维护一个持久的TCP连接减小网络开销；
c、减少存储在master上的元数据把它放在内存中。
在具有优点的同时，存在缺点，就是多个客户端同时访问同一个文件（此文件比较小，由一个chunk组成），易形成hot spot。
（3）通过观察发现，绝大部分的时候，对文件的修改操作都只是附加内容，很少是翻盖写或者随机写。因此在GFS中，对文件附加操作进行重点优化。

GFS的体系结构
GFS的体系结构是由一个master和多个chunkserver组成（在Hadoop中，master称作name node，chunkserver称作data node，chunk称作block）。
采用单一的master，可以简化系统设计，在拥有全局视图的情况下制定更好的chunk处置策略。采用此种方法，存在瓶颈问题是显而易见的。因此master只存储元信息，相当于元数据服务器，具体的数据传输由client和chunkserver来完成。

元数据
包括三类元数据，它们分别是：文件和chunk的命名空间，文件到chunk的映射和每个chunk副本的位置。元数据全部放入内存，这样可以加快master的操作速度，但它受限于内存大小。

操作日志
对文件系统的操作都将被记录到持久化存储介质，通过重新执行这些操作来达到恢复文件系统的目的。当操作日志达到一定大小时，将做checkpoint，这样可以减少文件系统的恢复时间。目前，Hadoop不支持对操作日志做checkpoint。

Data Flow
在GFS中，数据流和控制流分开，这是显而易见的。数据流怎么流动，具有一定的技巧性。它采用的是pipeline方式。一个chunkserver并不是把数据同时分发给其余的chunkserver，而是把数据只传给离自己最近的chunkserver（距离的远近通过IP地址来判断）。此时这个chunkserver在接受数据的同时，把数据转发给离它最近的chunkserver，这样充分利用了全双工网络的带宽。

以上只谈到paper中涉及的一些方面，完整内容请阅读paper。

基本算法连载（8）－Library Sort(gapped insertion sort)

2006-09-21T23:01:00.000+08:00

特色：Library sort优于传统的插入排序（时间复杂度为O(n^2))，它的时间复杂度为O（nlogn），采用了空间换时间的策略。
思想：一个图书管理员需要按照字母顺序放置书本，当在书本之间留有一定空隙时，一本新书上架将无需移动随后的书本，可以直接插空隙。Library sort的思想就源于此。
实现：有n个元素待排序，这些元素被插入到拥有(1+e)n个元素的数组中。每次插入2^(i-1)个元素，总共需要插logn趟。这2^(i-1)个元素将被折半插入到已有的2^(i-1)个元素中。因此，插入i趟之后，已有2^i个元素插入数组中。此时，执行rebalance操作，原有处在(1+ e)2^i个位置的元素将被扩展到(2+2e)2^i个位置。这样，在做插入时，由于存在gap，因此在gap未满之前无需移动元素。
具体代码：


/*
* length：待排序元素个数
* elements：待排序数组
* factor：常数因子
*/
void librarySort(int length,float factor,int elements[]){
 int i,j;
 //扩展后的数组长度
 int expandedLen = (int)((1+factor)*length);
 int* orderedElem = (int*) malloc(expandedLen*sizeof(int));
  
 //标志gap
 int flag = 1<<31;
 for(i=0;i<expandedLen;i++){
  orderedElem[i] = flag;
 }
 
 int index = 1;
 int numOfIntercalatedElem = 1;
 orderedElem[0] = elements[0];
  
 while(length>numOfIntercalatedElem){
  //第i次插入2^(i-1)个元素
  for(j=0;j<numOfIntercalatedElem;j++){
   //待插入元素为elements[index]   
   //------------折半插入---------------
   int mid;
   int low = 0;
   int high = 2 * numOfIntercalatedElem - 1;
   while(low <= high){
    mid = (low + high)/2;
    
    int savedMid = mid;
    //如果mid所在位置为gap
    while(orderedElem[mid] == flag){     
     if(mid == high){
      //当向右遍历没有找到元素值时，改成向左遍历
      mid = savedMid - 1;
      while(orderedElem[mid] == flag){
       mid--;
      }
      break;
     }
     mid++;
    }
    
    if(elements[index] > orderedElem[mid]){
     low = mid + 1;
     //缩小范围
     while(orderedElem[low] == flag){
      low = low+1;
     }
    }else{
     high = mid - 1;
    }
   }   
   
   //把elements[index]插入到orderedElem[high+1]
   //当位置为空，没有存储元素值时...
   if(orderedElem[high+1] == flag){
    orderedElem[high+1] = elements[index];
   }else{
    //位置非空，首先往前挪动元素，如果前面已满，向后挪动元素
    int temp = high+1;
    while(orderedElem[temp] != flag){
     temp--;
     if(temp < 0){
      temp = high+1;
      break;
     }
    }     
    
    //向后移动 
    while(orderedElem[temp] !=flag){
     temp++;
    }     
     
    while(temp < high){
     orderedElem[temp] = orderedElem[temp+1];
     temp++;
    }
     
    while(temp > high+1){
     orderedElem[temp] = orderedElem[temp-1];
     temp--;
    }   
     
    orderedElem[temp] = elements[index];          
   }
   //--------------------------------- 
   index++;
   if(index == length){
    break;
   } 
  }
  
  numOfIntercalatedElem *=2;
  int generatedIndex;
  //Rebalance...
  for(j=numOfIntercalatedElem;j>0;j--){
   if(orderedElem[j] == flag){
    continue;
   }
   //原数组元素从i处移到2i处
   generatedIndex = j*2;
   if(generatedIndex >= expandedLen){    
    generatedIndex = expandedLen - 1;
    if(orderedElem[generatedIndex] != flag){
     break;
    }
   }   
   orderedElem[generatedIndex] = orderedElem[j];
   orderedElem[j] = flag;
  }     
 }
 //测试输出
 for(i=0;i<expandedLen;i++){
  printf("%d\n",orderedElem[i]);
 }
 
}

基本算法连载（7）－Skip List（下）

2006-09-18T20:48:00.000+08:00

基本算法连载（6）－Skip List（上）

2006-09-18T20:47:00.000+08:00

Skip List号称性能与BST（Binary Sort Tree）树有得一拼，于是把它翻了个底朝天。代码是阐述其思想的最好方式，那我们还是看看它的具体实现（采用Java语言）
public class SkipList {

public static final int NOT_FOUND = -1;
public static final int HEADER_KEY = -2;
public static final int NIL_KEY = Integer.MAX_VALUE;

// optimum probability
public static final float OPT_PROB = 0.25f;
private float myProbability;
// probability to increase level
private int myMaxLevel;
// upper bound of levels
private int myLevel;
// greatest level so far
private SkipListElement
myHeader; // the header element of list

/*
* Constructs a new skip list optimized for the given
* expected upper bound for the number of nodes.
*/

public SkipList(long maxNodes) {
// probability set to 0.25 and maximum level
// of list is depending on expected number of nodes
// (see paper for mathematical background)
this(OPT_PROB,(int)Math.ceil(Math.log(maxNodes)/Math.log(1/OPT_PROB))-1);
}

public SkipList(float probability, int maxLevel) {
myLevel = 0;
myProbability = probability;
myMaxLevel = maxLevel;
// generate the header of the list
myHeader = new SkipListElement(myMaxLevel,HEADER_KEY, 0);

// append the "NIL" element to the header
SkipListElement nilElement = new SkipListElement(myMaxLevel, NIL_KEY, 0);
for (int i=0; i<=myMaxLevel; i++) {
myHeader.forward[i] = nilElement;
}
}

/*
* Generates with help of randomizer the level of a new element.
* The higher a level, the less probable it is (see paper).
* Levels begin at 0 (not at 1 like in the paper).
*/
private int generateRandomLevel() {
int newLevel = 0;
while (newLevel<myMaxLevel &&Math.random()<myProbability ) {
newLevel++;
}
return newLevel;
}

/*
* Inserts a new node into the list.
* If the key already exists, its node is updated to the new value.
*/
public void insert(int searchKey, int value) {
// update pointers to next elements on each level and
// levels run from 0 up to myMaxLevel.
SkipListElement[] update = new SkipListElement[myMaxLevel+1];

// init "cursor" element to header
SkipListElement element = myHeader;

// find place to insert the new node
for (int i=myLevel; i>=0; i--) {
while (element.forward[i].key <searchKey) {
element = element.forward[i];
}
update[i] = element;
}

element = element.forward[0];

// element with same key is overwritten
if (element.key == searchKey) {
element.value = value;
}else{
// or an additional element is inserted
int newLevel = generateRandomLevel();
// element has biggest level seen in this list,update list
if (newLevel > myLevel) {
for (int i=myLevel+1;i<=newLevel; i++) {
update[i] = myHeader;
}

myLevel = newLevel;
}

// allocate new element:
element = new SkipListElement(newLevel,searchKey, value);
for (int i=0; i<=newLevel; i++) {
element.forward[i] = update[i].forward[i];
update[i].forward[i] = element;
}
}

}

/*
* Search for a given key in list. You get the value associated
* with that key or the NOT_FOUND constant.
*/

public int search(int searchKey) {
// init "cursor"-element to header
SkipListElement element = myHeader;

// find element in list:
for (int i=myLevel; i>=0; i--) {
SkipListElement nextElement = element.forward[i];
while (nextElement.key < searchKey) {
element = nextElement;
nextElement = element.forward[i];
}
}

element = element.forward[0];
if (element.key == searchKey) {
return element.value;
}else {
return NOT_FOUND;
}

}

public void delete(int searchKey) {
// update holds pointers to next elements of each level
SkipListElement update[] = new SkipListElement[myMaxLevel+1];

// init "cursor"-element to header
SkipListElement element = myHeader;

// find element in list
for (int i=myLevel; i>=0; i--) {
SkipListElement nextElement = element.forward[i];
while (nextElement.key < searchKey) {
element = nextElement;
nextElement = element.forward[i];
}
update[i] = element;
}

element = element.forward[0];
// element found, so rebuild list without node
if (element.key == searchKey) {
for (int i=0; i<=myLevel; i++) {
if (update[i].forward[i] == element) {
update[i].forward[i] = element.forward[i];
}
}

// element can be freed now
element = null;

// maybe we have to downcorrect the level of the list
while (myLevel>0&& myHeader.forward[myLevel].key==NIL_KEY){
myLevel--;
}
}
}

/*
* inner class
*/

private class SkipListElement {
int key;
int value;
int level;

// array of forward pointers
SkipListElement forward[];

public SkipListElement(int level, int key, int value) {
this.key = key;
this.value = value;
this.level = level;
forward = new SkipListElement[this.level+1];
}
}

}

Hadoop系列－fs包之代码实现

2006-09-14T10:55:00.000+08:00

在此包中，最重要的是FileSystem抽象类。它定义了文件系统中涉及的一些基本操作，如：create，rename，delete...另外包括一些分布式文件系统具有的操作：copyFromLocalFile,copyToLocalFile,...类似于Ftp中put和get操作。 LocalFileSystem和DistributedFileSystem，继承于此类，分别实现了本地文件系统和分布式文件系统。
了解了最重要的类之后，看一看它的一系列stream类：

FSOutputStream在原有OutputStream基础之上添加了获得文件指针偏移量的getPos方法。可以通过FileSystem的 createRaw获得它的实例。这里存在一个疑问，这个扩展的getPos方法在fs包中没有被使用。如果在其余包中同样没有被使用，那么扩展就显得多余。

FSInputStream在原有InputStream基础之上同样添加了getPos方法，同时可以通过seek方法定位指定的偏移量处。可以通过 FileSystem的openRaw获得它的实例。新添加的getPos和seek方法在FSDataInputStream类中被使用。

FSDataOutputStream继承于DataOutputStream，包装了FSOutputStream。与DataOutputStream相比，不同之处在于：

添加了getPos方法，它是利用PositonCache记录当前的position
通过Buffer内类对输出进行缓存处理，改进性能
可以构建具有checksum的流，保证数据的正确性

FSDataInputStram继承于DataInputStream，包装了FSInputStream。与DataInputStream相比，不同之处在于：

添加了seek和getPos方法
通过Buffer内类对输入进行缓存处理，改进性能
可以构建具有checksum的流，保证数据的正确性

另外，为了屏蔽Windows和Unix、Linux在路径处理上存在的差异，实现了Path类，提供了统一的处理方式。

Hadoop系列－IPC之代码实现

2006-09-09T23:31:00.000+08:00

整体结构：在IPC包中，最重要的3个类是Server，Client和RPC，它们具有层次化的结构。

RPC类是对Server、Client的具体化。在RPC类中规定，客户程序发出请求调用时，参数类型必须是Invocation；从服务器返回的值类型必须是ObjectWritable。为了加强理解，可以查看测试类TestIPC。在那里，规定的参数类型与返回值类型都是LongWritable。
RPC类是对Server、Client的包装，简化用户的使用。如果一个类需充当服务器，只需通过RPC类的静态方法getServer获得Server实例，然后start。同时此类提供协议接口的实现。如果一个类充当客户端，可以通过getProxy或者waitForProxy获得一个实现了协议接口的proxy object，与服务器端交互。为了加强理解，可以查看测试类TestRPC，在那里，实现的协议接口为TestProtocol。

Server类

启动Listener进程。如果收到需要建立连接的请求，将建立连接，然后在上面捕获读操作的命令。收到命令之后，将把解析客户端发过来信息的工作委派给Connection。Connection把信息封装到Call对象中，放入队列中，待Handler处理。
启动指定数目的Handler线程，处理客户端对指定方法调用的请求，然后把结果返回给客户端。

Client类

用Call封装好调用信息，然后借助从连接池中取出的Connection向服务器端发送，等待结果。如果到指定服务器的Connection不存在，将马上建立。Connection线程读取服务器方法调用的返回信息。完成之后，通知主线程。

RPC类

对外使用的窗口，隐藏了Server和Client的背后细节，验证RPC协议版本。

Hadoop系列－IPC模型

2006-09-09T21:17:00.000+08:00

IPC

实现RPC的一种方法，具有快速、简单的特点。它不像Sun公司提供的标准RPC包，基于Java序列化。
IPC无需创建网络stubs和skeletons。
IPC中的方法调用要求参数和返回值的数据类型必须是Java的基本类型，String和Writable接口的实现类，以及元素为以上类型的数组。接口方法应该只抛出IOException异常。

使用模型

采用客户/服务器模型
Server：它把Java接口暴露给客户端。指定好监听端口和接受远程调用的对象实例后，通过RPC.getServer()可以得到Server实例。
Client：连接Server，调用它所暴露的方法。Client必须指定远程机器的地址，端口和Java接口类，通过RPC.getClient()可以得到Client实例。
Server不可以向Client发出调用，但在Hadoop中，有双向调用的需求。比如在DFS，NameNode和DataNode需要互相了解状态。

基本算法连载（5）－Bubble sort

2006-09-07T18:24:00.000+08:00

冒泡排序基于交换的思想，简单，易于实现,时间复杂度为O(n^2)。它最多只能充当排序算法的一种演示，不会运用到实际开发中，因为它声名狼藉。看看算法界的泰斗Donald Knuth是怎么说的，“The bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.”既然如此，冒泡排序的问题出在哪里呢？ “Large elements at the top of the list do not pose a problem, as they are quickly swapped downwards. Small elements at the bottom, however, move to the top extremely slowly. This has led to these types of elements being named rabbits and turtles, respectively.”
针对问题根源，人们找到了一些缓解方案。一个是bidirectional bubble sort，一个是comb sort。

bidirectional bubble sort：一趟排序到达数列尾部时，从尾部开始遍历。到达头部后，接着又从头部向尾部遍历，如此反复，完成排序。此时时间复杂度仍然是O(n)。

comb sort：进行排序时，每次比较交换的元素跨度将不局限于1。当turtle都移到头部时，元素跨度将变成1，完成最终的排序。元素跨度值的设置对排序性能有重大影响，经验表明，跨度最先选择为数列长度除以1.3所获得的商值是最优的。此种算法的时间复杂度为O(nlgn)。代码示例如下：

private static int newGap(int gap){
gap = gap * 10 /13;
if(gap == 9 || gap == 10)
gap = 11;

if(gap < 1){
return 1;
}else{
return gap;
}

}

public static void sort(int a[]){
int gap = a.length;
boolean swapped;
do{
swapped = false;
gap = newGap(gap);

for(int i=0;i<a.length-gap;i++){
if(a[i] > a[i+gap]){
swapped = true;
int temp = a[i];
a[i] = a[i+gap];
a[i+gap] = temp;
}
}

}while(gap>1 || swapped);

}

基本算法连载（4）－Google的一道面试题

2006-09-06T19:49:00.000+08:00

题目：在一个集合S中寻找最大的C，使A+B=C，且A,B,C均在集合当中，时间空间复杂度最低。

解题思路：

方案一：
1. 对集合进行快速排序，时间复杂度为O(nlgn)，空间复杂度为O(lgn)；
2. 从最后一个元素开始，依次调用“在一个有序集合中寻找两个数的和等于给定值的算法”。一次调用需要O(n)，n个元素需要O(n^2)。
3. 总体来看，此方案的时间复杂度为O(n^2)，空间复杂度为O(lgn)。

方案二：

对集合进行快速排序，时间复杂度为O(nlgn)，空间复杂度为O(lgn)；
用排序后的n个数（a[0],a[1],a[2],...a[n-1]）构造n×n的两两和矩阵，此时有m[i][j]=a[i]+a[j]，m[i] [j]<=m[i][j+1],m[i][j]<=m[i+1][j]，在此矩阵中搜索一个数是否存在，时间复杂度为O(n+n)，所以n个数的时间复杂度为O(n^2)。矩阵元素可以直接通过a[i]与a[j]相加动态获得，所以不需要额外开辟空间。
总体来说，此方案的时间复杂度为O(n^2)，空间复杂度为O(lgn)。
具体搜索方法为：对于一个给定的数a，沿着对角线走下去，遇到第一个大于a的数，然后往上走，如果找到就OK，否则不存在。

基本算法连载（3）－3个基本性质

2006-09-04T21:36:00.000+08:00

性质1：一颗二叉树（严格的二叉树，即没有度为1的节点），有N个内部节点，那么它将有N＋1个外部节点。

采用归纳法证明：

如果只有一个外部节点，即单独的一个根节点，那么内部节点数为0，结论显然成立。
假设有N－1个内部节点时，结论成立。那么二叉树拥有N个内部节点时，左子树有k个内部节点，右子树有N－k－1个内部节点，此外包括一个根节点。由于左右子树的节点数都小于N，所以由前面假设可得左子树有k＋1个外部节点，右子树有N－k个节点，总共有k＋1＋(N-k)个节点，即N＋1个节点。
由性质1可得，一颗有N个外部节点的二叉树需要用数组存储，那么需要申请一个拥有2N－1个元素的数组。

性质2：在一个已排序的序列中寻找和为给定数值的两个数，可在O(n)时间内完成。

简单示例：
#include <stdio.h>
int main(int argc,char*argv[]){
//排好序的数组序列
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//给定值
int value = 21;
int i = 0,j = 9;
while(1){
if(a[i] + a[j] == value){
break;
}else{
if(i >= j){
printf("%s\n","Not found!");
exit(1);
}
}
if(a[i] + a[j]<value){
i++;
}else{
j--;
}
}
printf("%d\n%d",i,j);
return 0;
}

性质3：在一个无序序列中寻找和为给定数值的两个数，可在O(nlgn)时间内完成。

采用快速排序对无序序列进行排序，时间复杂度为O(nlgn)。
由性质2可知，时间复杂度为O(n)。

基本算法连载（2）－摔xbox

2006-08-29T16:19:00.000+08:00

题目

You have been given 2 special, extremely rugged Xboxes. You are in an office building that is 100 stories high. Using the fewest possible number of drops from windows in your office building, determine the highest floor you can drop an Xbox from and have it survive: for example, they might be able to take the drop from the 30th floor, but not the 31st. You can break both Xboxes in your search. State the worst case number of drops needed and explain how you arrived at that answer.
你在一幢100层的办公楼里上班，现在给你两台xbox（已经特意捆绑包扎好），要求你用尽可能少的试摔次数来判断xbox摔不坏的最高楼层层数。比方说，从30层丢下来没问题，但从31层丢下来就不保了。在摸索过程中，允许把两台xbox都砸烂。在最坏情况下，使得试摔次数尽可能小。

分析

问题答案必须是在最坏情况下，时间复杂度最小。
最容易想到的就是二分法，三分法，多分法，但它们并不符合要求。比如：在50层丢一个，被砸烂。然后在25层丢另外一个，同样被砸烂。此时根本无从找到问题答案。
第二个想到的方法就是分段。（1）用第一个xbox寻找损坏区间；（2）用第二个xbox遍历该区间寻找损坏层。假定最优区间长度是x，则第一步最多要摔100/x（大于等于此值的最小整数）次，第二步最多摔x-1次，问题转换为求100/x+(x-1)的最小值。具体描述：以10层楼为一个区间，先摔第一个，以确定摔坏的区间，然后再用另一个在这个区间内从最低的楼层摔，从而找到所要求层数，这种方法最多要摔19次。
在“分段”方法中，段区间都是相等的。如果段区间不等，是不是可以找到最优的方法呢？假设最终答案至少要摔n次，那第一次顶多从n层楼摔。如果坏了，第二个从1至n-1层最多摔n-1次就可以判断了；如果没坏，那么搜索范围改为[n+1,100]，相当于搜索空间减少了n层。如果第一次没坏，第二次顶多再减少n-1的搜索空间。依次类推，当第n次时顶多再减少1的搜索空间。n次之后，顶多排除n+(n-1)+(n-2)+...+1 = n*(n+1)/2个楼层。只要n*(n+1)/2 >= 100就可以了，满足这个条件的最小n为14。具体描述：从14楼丢一个，如果碎了，从1楼开始到13楼为止丢另一个，不碎，在14＋13楼丢；...

证明

给一个包含n个元素的数组，{a[1],...,a[n]}，a[1]+a[2]+...+a[n]=100。那么如果第k次摔坏了第1台xbox ，那么此时最坏情况下总共需要的次数是k+a[k]-1我们把这个记为cost[k]。此时，问题可以重新描述为：找到一个满足上述条件的数组，{a[1],...,a[n]} ，使得 max(cost[k])最小。
sigma( cost[k] )
= (1+a[1]-1) + (2+a[2]-1) + (3+a[3]-1) ... + (n+a[n]-1)
= (1+2+3+ ... +n) + (a[1]+a[2]＋a[3]+ ... +a[n]) - n
= n*(n+1)/2 + 100 - n
这个式子是个常量仅与n有关，与{a[1],...,a[n]}的具体数值无关。同时，不难看出 max( cost[k] ) >= sigma( cost[k] ) / n （最大值总是大于平均值），而且仅当 cost[1] =cost[2] = ... cost[n] 的时候，max...可以取到这个最小值。因此，对于任意给定的n，满足 cost[1]= cost[2] = ... cost[n]的解就是最优解。也就是说k+a[k]-1=1+a[1]-1，从而a[k]=a[1]-k+1 。那么a[2]=a[1]-1，a[3]=a[1]-2=a[2]-1...

参考：(1) 摔xbox的题目

找病狗

2006-08-29T16:01:00.000+08:00

题目

村子中有50个人，每人有一条狗。在这50条狗中有病狗（这种病不会传染）。于是人们就要找出病狗。每个人可以观察其他的49条狗，以判断它们是否生病（如果有病一定能看出来），只是自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗（发现后必须在一天内枪毙），而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。第一天大家全看完了，但枪没有响，第二天仍没有枪响。到了第三天传来一阵枪声，问村里共有几条病狗，如何推算得出？

答案

3条病狗

分析

假设有n条病狗，那么就有50-n个人的狗不是病狗。第一天大家枪都没有响，那么n必然大于1 。因为如果n = 1.那么必然有一个人(病狗的主人)看到49条好狗,那样他就会枪毙自己的狗。所以这里 n >= 2。
到了第二天。大家都清楚了n >=2 ，但是还是没有开枪。这个时候必然有 n > 2，因为如果n == 2的话 .那两个病狗的主人看到都是一条病狗,他们会明白还有一条病狗就是自己那条，所以就会有人开枪。但是没人开枪，说明n >= 3。
到了第三天，有人开枪了。因为在前两天只能确定 n >=3 , 因为有人开枪了，那么开枪的那个人肯定能断定自己那条是病狗,并且他知道 n >=3 。所以他肯定只看到了 2只病狗，才能确定他自己那只肯定是病狗。以此来推，第几天开枪，就有几只病狗。

基本算法连载（1）－顺序搜索与二分搜索

2006-08-29T09:47:00.000+08:00

顺序搜索
Programmer每天都碰到顺序搜索，其code snippet：
/*
* 顺序遍历数组，搜索v值是否存在。如果存在，返回相应的位置索引，
* 否则返回-1
*/
int sequentialSearch(int a[],int v,int l,int r){
int i;
for(i = l;i <= r;i++){
if(v == a[i])
return i;
}
return -1;
}

分析：

假设数组拥有N个元素，对于不成功的搜索，总是搜索N个元素；对于成功的搜索，平均搜索次数为N/2。
假设每个数组元素被搜索到的概率相等，那么平均搜索次数可以这样计算：(1+2+...+N)/N = (N+1)/2
对于排序数组，相关性质不变。

二分搜索
code snippet：
/*
* 二分搜索，非递归实现
* 假设：数组元素已经按序排列
*/
int binarySearch(int a[],int v,int l,int r){
int m;
while(l<=r){
m = (l+r)/2;
if(v == a[m])
return m;

if(v > a[m]){
l = m + 1;
}else{
r = m - 1;
}
}
return -1;
}

/*
* 二分搜索，递归实现
*/
//dataForExperiment数组定义及初始化
int binarySearch(int v,int l,int r){
if(l > r){
return -1;
}
int m = (l + r)/2;
if(v == dataForExperiment[m]){
return m;
}else{
if(v > dataForExperiment[m]){
return binarySearch(v,m+1,r);
}else{
return binarySearch(v,l,m-1);
}
}
}
分析：

假设Tn表示在最坏情况下二分搜索需要比较的次数，那么有Tn＝Tn/2＋1，其中n>=2，T1＝1
求解递归式，可以得到二分搜索检查元素个数永远不超过lgn＋1。
数组必须是已经排好序的。

MapReduce:Simplified Data Processing on large Clusters－翻译版（下）

2006-08-26T00:51:00.000+08:00

实现
拥有多个不同的MapReduce接口的实现是可能的。具体选择取决于环境。比如，一种实现适合于共享内存的机器，一种适合于NUMA(Non-Uniform Memory Access )多处理器，另外一种适合于大量的网络机器。
这节将描述在Google内部大量使用，适合于大量PC构成的集群系统这种计算环境的实现。在这个环境中：

双CPUx86机器，运行Linux，具有2-4G内存。
网络采用的是100M/s或1G/s的配置硬件，然实际的平均使用值大概为它们的一半。
采用由成百上千PC构成的集群系统，机器故障很经常。
存储采用的是直连每个机器的IDE硬盘。通过我们自己开发的GFS来管理磁盘上的数据。此文件系统使用复制策略使得自己在不可靠的硬件上具有很好的可用性和可靠性。
用户提交作业到调度系统。每个作业由一系列任务构成，这些任务被映射到集群范围内可用的机器上。

执行概貌

通过把输入文件分割成M等份，Map调用能够在多台机器上分布执行。这M等分数据在不同机器上可以并行处理。通过使用分割函数（比如 hash(key) mod R）把中间形式的key空间分成R份，Reduce调用能够分布执行。分区数目和分割函数是由用户指定。
图1展示了整个MapReduce的操作流程。当用户程序调用MapReduce函数，将执行如下步骤（图上的数字号码与如下列表中的数字号码是一一对应的）：

MapReduce库首先把输入文件分成大小为16-64M之间块大小的M份（通过一个可选的用户参数控制），然后它在多台机器上启动程序副本。
其中存在于master上的一个副本是特殊的，其余的worker都将由master分配工作。
被分配map任务的worker将读取输入份中的内容。它从输入数据中解析key/value对，然后把这些对传给用户定义的Map函数。产生的中间key/value对将由内存缓存。
处在缓存中的对将被间隔性的写入磁盘，这些对将散步在由分割函数指定的R个区域中。这些缓存对在局部磁盘的具体位置被传回给master，然后master负责把这些信息转发给reduce worker。
当reduce worker从master得到位置信息，它将使用远程过程调用从map worker的局部磁盘中读取数据。读取完所有数据之后，reduce worker按照中间key进行排序，以使得相同值的key被分在一起。因为许多不同的key有可能映射到相同的reduce任务，所以排序是必须的。当数据太大而不能将它们全部放入内存时，一种外部排序方法将被使用。
reduce worker遍历排好序的中间数据，当它遇到一个唯一的中间形式key，它将把key和与它对应的中间value传给用户提供的Reduce函数。Reduce函数的输出将被附加到与这个reduce对应的最终输出文件中。
当所有的map和reduce任务被完成之后，master唤醒用户程序。于是MapReduce调用返回到用户代码。

当成功完成之后，输出结果将存在于R个输出文件中，每一个reduce任务对应一个。一般来说，用户没有必要合并这R个文件为一个。这些文件将被传给另一个MapReduce调用当作输入，或者能够处理输入被分割的其余形式的分布式程序。

master数据结构

master保存有多种数据结构。对于每个map和reduce任务，它存储有它们的状态（空闲，正在处理或者完成）和非空闲worker所在机器的标志。
关于中间文件的位置信息是通过master从map任务传递给reduce任务的。因此，对于每个完成的map任务，master存储有它所产生的R文件的位置和大小信息。一旦map任务完成，master就更新这些信息，然后把这些信息传给正在处理中的reduce任务。

容错

因为MapReduce库是用来在成百上千台机器上处理大量数据，所以库必须很好的进行容错处理。

worker故障

master间隔性的ping worker。当尝试多次之后没有响应，master将认为worker已经出现故障。任何已经在wokrer上完成的任务将被设置为空闲状态，以使得它可以重新被调度。同样，正在处理的map或reduce任务也将被设置为空闲状态，以便重新调度。
完成的map任务需要重新执行，那是因为它们的输出是存储在出现故障机器上的本地磁盘，而导致不可访问。完成的reduce任务输出结果是存储在全局文件系统而不存在这个问题。
当一个map任务首先在woker A上执行，然后在worker B上（因为A出现故障），所有执行reduce任务的worker将得到重新执行的通知。对于还没有从worker A上读取数据的reduce任务将从woker B上读取。
MapReduce对worker故障具有很强的适应能力。比如在一次MapReduce操作中，网络维护一次性造成80台机器变得不可抵达。此时MapReduce重新执行这些出现问题机器上的任务，以至最终完成任务。

参考：(1) 什么是MapReduce? Google的分布运算开发工具!

MapReduce:Simplified Data Processing on large Clusters－翻译版（上）

2006-08-26T00:49:00.000+08:00

概括

MapReduce既是一种编程模型，也是用来处理和生成大数据集的一种实现。用户指定的map函数操作key/value对以生成中间形式的key/value对；指定的reduce函数把具有相同中间形式key的value合并在一起。许多现实中的任务都可以用这种模型进行表述，在这篇文章中，将看到这方面的任务。
以MapReduce方式进行编写的程序可以自动并行化，运行在大规模集群系统上。运行系统替用户处理输入数据的分割，程序在一系列机器上的调度执行，故障处理，机器间的通讯。这样使得无并行和分布式经验的程序员利用此系统很容易的采用系统资源。
我们的MapReduce实现系统运行在用商用PC搭建的大规模集群系统上。它具有很好的可扩展性，比如可以对数TB的数据在成千上万机器上进行计算。程序员发现系统的可用性很好。在Google，已经有成百上千的基于MapReduce的应用程序。每一天，将有超过1千左右的MapReduce作业运行在Google的集群上。

简单介绍

在过去的5年中，本文作者和其余在Google的开发者实现了用来处理大量原始数据（比如被抓取的文档，Web请求日志，等等）的各种特殊目的计算。比如反向索引，web文档图形结构的表示，基于每台主机被抓取页面数量的统计，在指定一天中最经常使用的查询，等等。大部分计算从原理上讲是很简单的。但是随着输入数据的加大，这些计算不得不分发在成百上千台计算机上进行计算，以便计算任务在一个可接受的时间限度内完成。这时本来很简单的应用程序不得不处理并行计算，分发数据，处理故障等问题而导致其变得晦涩难懂。
为了应付这种复杂性，我们设计了一种新的抽象。它可以使得用户表达自己的简单计算，而把并行化，容错，数据分发和负载平衡的细节全部隐藏在库中。此抽象的灵感来自于Lisp和其它函数语言中的map和reduce操作。我们意识到大部分的计算都包括：对输入中的逻辑“记录”进行map操作，以获得一系列的中间形式的key/value对；对共享同一key的中间值进行reduce操作，以并其合并。用户提供map和reduce操作，然后运用此函数模型，可以使得我们非常容易进行大规模的并行计算，通过重新执行的方式来达到容错的目的。
这项工作最主要的贡献是提供了一个简单且强大的接口，通过这个接口实现，使得大规模计算得到自动并行与分布，在大规模集群系统上达到高性能。
第2节描述了基本的编程模型，另外给出了Google内部的一些实例；第3节描述了为集群系统量身定制的MapReduce接口实现；第4节阐述了一些对现存编程接口模型十分有用的改进；第5节提供了基于各种任务，现有实现的性能测试；第6节说明了MapReduce在Google内部的使用，阐述了利用它对现有索引系统进行重写所获得的一些经验；第7节讨论了相关及将来工作。

编程模型

计算是把一系列key/value对当作输入，产生一系列key/value对。使用MapReduce库的用户用Map和Reduce表示计算过程。
用户提供的Map获得输入对，产生一系列的中间形式的key/value对。MapReduce库把中间形式key值为I的所有value集中在一起，然后把它们传给Reduce函数。
用户提供的Reduce函数，接受中间形式key值I和与它关联的一系列value，然后把这些值合并产生一个可能相对较小的value集合。一般来说，每个调用产生0个或1个输出值。中间形式的value是通过迭代器的形式提供给reduce函数。这样使得我们可以处理那些太大而不能一次性载入内存的value。

样例

类型

更多实例

参考：(1) 什么是MapReduce? Google的分布运算开发工具!

反向索引（Inverted Index）

2006-08-25T23:25:00.000+08:00

反向索引是一种索引结构，它存储了单词与单词自身在一个或多个文档中所在位置之间的映射。反向索引通常利用关联数组实现。它拥有两种表现形式：

inverted file index，其表现形式为 {单词，单词所在文档的ID}
full inverted index，其表现形式为{单词，（单词所在文档的ID，在具体文档中的位置）}

具体实例，假设有三个文档：

$T 0 =$ "it is what it is"
$T 1 =$ "what is it"
$T 2 =$ "it is a banana"

那么，采用inverted file index方式，结果是：
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
采用full inverted index方式，结果是：

"a":      {(2, 2)}
"banana": {(2, 3)}
"is":     {(0, 1), (0, 4), (1, 1), (2, 1)}
"it":     {(0, 0), (0, 3), (1, 2), (2, 0)}
"what":   {(0, 2), (1, 0)}

用C语言实现函数语言中的Map和Reduce操作

2006-08-25T17:46:00.000+08:00

在Google 的论文《MapReduce：Simplified Data Processing on Large Clusters》中提到“Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional lanuages.”。对于大部分不熟悉函数语言的程序员来说，可能并不能够彻底理解Map和Reduce的具体含义。在这篇文章中，将采用C语言实现函数语言中的Map和Reduce操作。
简单来说，Map是对一组数据中的每个元素进行操作，产生一组全新的数据；Reduce是对这组数据进行归约，得到一个相对简单的结果。现在就让我们用C语言来描述它们。
#include <stdio.h>
//函数指针申明
typedef int (*mapFunction)(int);
typedef int (*reduceFunction)(int,int);
#define ERROR -1;

//-----------------Map和Reduce操作-----------------
/*
* 对list数组的数据进行处理，然后存储在list数组中
*/
void map(mapFunction func,int *list,int len){
int i;
for(i=0;i<len;i++){
list[i] = func(list[i]);
}
}

int reduce(reduceFunction func,int *list,int len){
if(len <= 0){
return ERROR;
}
int retVal = 0;
int i;
for(i=0;i<len;i++){
retVal = func(retVal,list[i]);
}
return retVal;
}

//-----------------------测试-------------------------
int square(int i){
return i*i;
}

int add(int i,int j){
return i+j;
}

int main(int argc,char*argv[]){
int array[5];
int i;
for(i=0;i<5;i++){
array[i] = i;
}

mapFunction mapFuncPointer = (mapFunction)&square;
reduceFunction reduceFuncPointer = (reduceFunction)&add;
map(mapFuncPointer,array,5);
int result = reduce(reduceFuncPointer,array,5);
printf("The result is %d\n",result);
return 0;
}

参考：(1) 从Map和Reduce说起

我是一只小小鸟

2006-08-25T17:33:00.000+08:00

看完“鲁豫有约”之《任贤齐－四十不惑》之后，我就爱上了《我是一只小小鸟》这首歌。blog的地址就用a small bird啦！