java中wait/notify机制

通常，多线程之间需要协调工作。例如，浏览器的一个显示图片的线程displayThread想要执行显示图片的任务，必须等待下载线程 downloadThread将该图片下载完毕。如果图片还没有下载完，displayThread可以暂停，当downloadThread完成了任务后，再通知displayThread“图片准备完毕，可以显示了”，这时，displayThread继续执行。
以上逻辑简单的说就是：如果条件不满足，则等待。当条件满足时，等待该条件的线程将被唤醒。在Java中，这个机制的实现依赖于wait/notify。等待机制与锁机制是密切关联的。例如：
synchronized(obj) {while(!condition) {obj.wait();}obj.doSomething();}

当线程A获得了obj锁后，发现条件condition不满足，无法继续下一处理，于是线程A就wait()。
在另一线程B中，如果B更改了某些条件，使得线程A的condition条件满足了，就可以唤醒线程A：
synchronized(obj) {condition = true;obj.notify();}

需要注意的概念是：
◆调用obj的wait(), notify()方法前，必须获得obj锁，也就是必须写在synchronized(obj) {...} 代码段内。
◆调用obj.wait()后，线程A就释放了obj的锁，否则线程B无法获得obj锁，也就无法在synchronized(obj) {...} 代码段内唤醒A。
◆当obj.wait()方法返回后，线程A需要再次获得obj锁，才能继续执行。
◆如果A1,A2,A3都在obj.wait()，则B调用obj.notify()只能唤醒A1,A2,A3中的一个（具体哪一个由JVM决定）。
◆obj.notifyAll()则能全部唤醒A1,A2,A3，但是要继续执行obj.wait()的下一条语句，必须获得obj锁，因此，A1,A2,A3只有一个有机会获得锁继续执行，例如A1，其余的需要等待A1释放obj锁之后才能继续执行。
◆当B调用obj.notify/notifyAll的时候，B正持有obj锁，因此，A1,A2,A3虽被唤醒，但是仍无法获得obj锁。直到B退出synchronized块，释放obj锁后，A1,A2,A3中的一个才有机会获得锁继续执行。

posted @ 2014-04-07 17:27 鑫龙阅读(221) | 评论 (0) | 编辑收藏

Dijkstra算法（单源最短路径）

单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前，必须弄清楚最短路径的最优子结构性质。

一.最短路径的最优子结构性质

该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

二.Dijkstra算法

由上述性质可知，如果存在一条从i到j的最短路径(Vi.....Vk,Vj)，Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路，

假设存在G=<V,E>，源顶点为V0，U={V0},dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。

1.从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；

2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})

3.知道U=V，停止。

代码实现:

/*Dijkstra求单源最短路径 2010.8.26*/

#include <iostream>
#include<stack>
#define M 100
#define N 100
using namespace std;

typedef struct node
{
    int matrix[N][M];      //邻接矩阵
    int n;                 //顶点数
    int e;                 //边数
}MGraph;

void DijkstraPath(MGraph g,int *dist,int *path,int v0)   //v0表示源顶点
{
    int i,j,k;
    bool *visited=(bool *)malloc(sizeof(bool)*g.n);
    for(i=0;i<g.n;i++)     //初始化
    {
        if(g.matrix[v0][i]>0&&i!=v0)
        {
            dist[i]=g.matrix[v0][i];
            path[i]=v0;     //path记录最短路径上从v0到i的前一个顶点
        }
        else
        {
            dist[i]=INT_MAX;    //若i不与v0直接相邻，则权值置为无穷大
            path[i]=-1;
        }
        visited[i]=false;
        path[v0]=v0;
        dist[v0]=0;
    }
    visited[v0]=true;
    for(i=1;i<g.n;i++)     //循环扩展n-1次
    {
        int min=INT_MAX;
        int u;
        for(j=0;j<g.n;j++)    //寻找未被扩展的权值最小的顶点
        {
            if(visited[j]==false&&dist[j]<min)
            {
                min=dist[j];
                u=j;
            }
        }
        visited[u]=true;
        for(k=0;k<g.n;k++)   //更新dist数组的值和路径的值
        {
            if(visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k]<dist[k])
            {
                dist[k]=min+g.matrix[u][k];
                path[k]=u;
            }
        }
    }
}

void showPath(int *path,int v,int v0)   //打印最短路径上的各个顶点
{
    stack<int> s;
    int u=v;
    while(v!=v0)
    {
        s.push(v);
        v=path[v];
    }
    s.push(v);
    while(!s.empty())
    {
        cout<<s.top()<<" ";
        s.pop();
    }
}

int main(int argc, char *argv[])
{
    int n,e;     //表示输入的顶点数和边数
    while(cin>>n>>e&&e!=0)
    {
        int i,j;
        int s,t,w;      //表示存在一条边s->t,权值为w
        MGraph g;
        int v0;
        int *dist=(int *)malloc(sizeof(int)*n);
        int *path=(int *)malloc(sizeof(int)*n);
        for(i=0;i<N;i++)
            for(j=0;j<M;j++)
                g.matrix[i][j]=0;
        g.n=n;
        g.e=e;
        for(i=0;i<e;i++)
        {
            cin>>s>>t>>w;
            g.matrix[s][t]=w;
        }
        cin>>v0;        //输入源顶点
        DijkstraPath(g,dist,path,v0);
        for(i=0;i<n;i++)
        {
            if(i!=v0)
            {
                showPath(path,i,v0);
                cout<<dist[i]<<endl;
            }
        }
    }
    return 0;
}

posted @ 2013-10-16 20:31 鑫龙阅读(553) | 评论 (0) | 编辑收藏

逆序数及其求法

1. 逆序数

所谓逆序数，就是指一个序列S[i]，统计处于序列的每个数的比这个数大并且排在它前面的数的数目，然后对于所有数，把这个数目加起来求和就是了。
比如 4 3 1 2
4第一个，所以数目为0
3的前面是4，大于3的数目为1
1的前面是4 3 ，大于1的数目为2
2的前面是4 3 1，大于2的数目为2
所以逆序数为1+2+2 = 5

求逆序数的两种方法
常规方法是按照逆序数的规则做，结果复杂度是O(n*n)，一般来说，有两种快速的求逆序数的方法
分别是归并排序和树状数组法

2. 归并排序
归并排序是源于分而治之思想，详细的过程可以查阅其他资料，总体思想是划分一半，各自排好序后将两个有序序列合并起来。

如何修改归并排序求逆序数?
首先我们假设两个有序序列 a[i]和b[i]，当合并时：
由于a[i]已是有序，所以对于a[i]的各个元素来说，排在它前面且比它大的数目都是0
当b[i]中含有比a[i]小的元素时，我们必然将b[i]元素插到前面，那么就是说，在b[i]原先位置到该插的位置中，所有数都比b[i]大且排在它前面
所以这是b[i]的数目为新插入位置newPos - 原来位置oldPos

那么对于一半的序列又怎么做呢？我们知道，归并排序会继续向下递归，而递归完成返回后将是两组有序的序列，并且拿到局部的逆序数，
所以在Merge函数中添加这一计数操作即可

代码示例如下：

int L[M];
int R[M];

const int Max = 1 <<30;
__int64 change = 0;

void Merge(int *data,int left,int divide,int right)
{
    int lengthL = divide - left;
    int lengthR = right - divide;

    for(int i = 0; i < lengthL; ++i)
    {
        L[i] = data[left + i];
    }
    for(int i = 0; i < lengthR; ++i)
    {
        R[i] = data[divide + i];
    }
    L[lengthL] = R[lengthR] = Max;
    int i = 0;
    int j = 0;
    for(int k = left; k < right; ++k)
    {
        if(L[i] <= R[j])
        {
            data[k] = L[i];
            ++i;
        }
        else
        {
            change += divide - i - left ;
            data[k] = R[j];
            ++j;
        }
    }

}

void MergeSort(int *data,int left,int right)
{
    if(left < right -1)
    {
        int divide = (left + right)/2;
        MergeSort(data,left,divide);
        MergeSort(data,divide,right);
        Merge(data,left,divide,right);
    }
}

3. 树状数组
求逆序数的另外一种方法是使用树状数组
对于小数据，可以直接插入树状数组，对于大数据，则需要离散化，所谓离散化，就是将
100 200 300 400 500 ---> 1 2 3 4 5

这里主要利用树状数组解决计数问题。

首先按顺序把序列a[i]每个数插入到树状数组中，插入的内容是1，表示放了一个数到树状数组中。
然后使用sum操作获取当前比a[i]小的数，那么当前i - sum则表示当前比a[i]大的数，如此反复直到所有数都统计完，
比如
4 3 1 2
i = 1 : 插入 4 : update(4,1)，sum(4)返回1，那么当前比4大的为 i - 1 = 0;
i = 2 : 插入 3 : update(3,1)，sum(3)返回1，那么当前比3大的为 i - 1 = 1;
i = 3 : 插入 1 : update(1,1)，sum(1)返回1，那么当前比1大的为 i - 1 = 2;
i = 4 : 插入 2 : update(2,1)，sum(2)返回2，那么当前比2大的为 i - 2 = 2;

过程很明了，所以逆序数为1+2+2=5

代码示例如下：

//树状数组
__int64 sums[1005];
int len;

inline int lowbit(int t)
{
    return t & (t^(t-1));
}

void update(int _x,int _value)
{
    while(_x <= len)
    {
        sums[_x] += _value;
        _x += lowbit(_x);
    }
}

__int64 sum(int _end)//get sum[1_end]
{
    __int64 ret = 0;
    while(_end > 0)
    {
        ret += sums[_end];
        _end -= lowbit(_end);
    }
    return ret;
}

//求逆序数

__int64 ret = 0;
for (__int64 i = 0; i < k; ++i)
{
    update(a[i],1);
    ret += (i+1) - sum(a[i]);
}

posted @ 2013-09-20 17:23 鑫龙阅读(343) | 评论 (0) | 编辑收藏

hadoop0.20.2在eclipse中的编译

1. 下载Hadoop源代码
Hadoop 各成员源代码下载地址：http://svn.apache.org/repos/asf/hadoop，请使用SVN下载，在SVN浏览器中将trunk目录下的源代码check-out 出来即可。请注意只check-out出SVN 上的tag 目录下的内容，如：
http://svn.apache.org/repos/asf/hadoop/common/tag/release-0.20.2，

2. 准备编译环境

2.1. 系统

CentOS5.5

2.2. Hadoop代码版本
hadoop-0.20.2-release

2.3. 联网
编译Hadoop 会依赖很多第三方库，但编译工具Ant 会自动从网上下载缺少的库，所以必须保证机器能够访问Internet。
2.4. java
编译Hadoop要用JDK1.6 以上，网址：http://java.sun.com/javase/downloads/index.jsp。
安装好之后，请设置好JAVA_HOME 环境变量。
2.5. Ant
需要使用Ant 工具来编译Hadoop，可以从：http://ant.apache.org/ivy/download.cgi 下载Ant

安装好之后，请设置好ANT_HOME 环境变量。

2.6. Eclipse

Eclipse 则可以从http://www.eclipse.org/downloads/上下载。

3. 编译Hadoop

3.1. 编译Hadoop
步骤1) 在Elipse 的Package 视图中单击右键，选择New->Java Project，如下图所示：

在上图所示的对话框中，点击Browse 按钮，选择hadoop-0.20.2 源代码目录，并设置Projectname 为hadoop-0.20.2-dev。工程导入完成后，进入Eclipse 主界面，可以看到hadoop-0.20.2 已经导入进来，但可以看到目录上有红叉叉，是因为Elipse默认使用了Java Builder，而不是Ant Builder，所以下一步就是设置使用Ant Builder。

步骤3) 设置Builder 为Ant：右键hadoop-0.20.2-dev>Properties->Builders:

点击Browse File System 按钮，选择hadoop-0.20.2源代码目录下的build.xml 文件，并设置Name 为Ant_Builder（Name 可以改成其它的，但建议使用Ant_Builder，因为这样名副其实），操作结果如下图所示：

Hadoop 各成员都需要编译成jar，所以做如下图所示的一个修改：

上面完成后，回到Builder 的主对话框，再将对话框中的Java Builder 下移，并将它前面的勾去掉。
进入Eclipse 主界面，由于之前选择了Manual Build，所以需要人工方式驱动编译，编译成功后，可以看到BUILDSUCCESSFUL 字样。

　请注意：如果上图所示的菜单中的BuildAutomatically 被勾中，则在common的右键菜单中可能不会出现Build 子菜单。
在编译过程中，Ant 会自动从网上下载所依赖的库。hadoop-0.20.2 编译成功结束后，可以在build 目录下找到编译后生成的文件hadoop-core-0.20.2-dev.jar。

3.2编译过程中出现错误

1、可能有时候因为eclipse版本或者操作系统版本的问题使得hadoop提供的eclipse plugin不太好用。
解决方法：
1）修改$HADOOP_HOME/src/contrib/build-contrib.xml
增加一行：<propertyname="eclipse.home" location="/home/gushui/eclipse"/>
上句后面的/home/gushui/eclipse由自己的$ECLIPSE_HOME代替

2）修改$HADOOP_HOME/src/contrib/eclipse-plugin/src/java/org/apache/hadoop/eclipse/launch/HadoopApplicationLaunchShortcut.java
注释掉原来的//importorg.eclipse.jdt.internal.debug.ui.launcher.JavaApplicationLaunchShortcut;
改为importorg.eclipse.jdt.debug.ui.launchConfigurations.JavaApplicationLaunchShortcut;

2、报错：

Buildfailed

Cannot write to the specified tarfile!

解决方法：

hadoop-0.20.2-dev目录下的Build.xml中

注销掉，运行成功。

参考 http://blog.csdn.net/basicthinker/article/details/6174442

参考： http://hi.baidu.com/xxjjyy2008/blog/item/7b5ed10f20e6a9346059f335.html

参考：http://hadoop.hadoopor.com/thread-941-1-1.html

http://trac.nchc.org.tw/cloud/wiki/waue/2010/0211

转自http://www.cnblogs.com/zyumeng/archive/2013/03/22/2975165.html

posted @ 2013-06-24 18:58 鑫龙阅读(278) | 评论 (0) | 编辑收藏

Zookeeper工作原理

ZooKeeper是一个分布式的，开放源码的分布式应用程序协调服务，它包含一个简单的原语集，分布式应用程序可以基于它实现同步服务，配置维护和命名服务等。Zookeeper是hadoop的一个子项目，其发展历程无需赘述。在分布式应用中，由于工程师不能很好地使用锁机制，以及基于消息的协调机制不适合在某些应用中使用，因此需要有一种可靠的、可扩展的、分布式的、可配置的协调机制来统一系统的状态。Zookeeper的目的就在于此。本文简单分析zookeeper的工作原理，对于如何使用zookeeper不是本文讨论的重点。

1 Zookeeper的基本概念

1.1 角色

Zookeeper中的角色主要有以下三类，如下表所示：

1.2 设计目的

1.最终一致性：client不论连接到哪个Server，展示给它都是同一个视图，这是zookeeper最重要的性能。

2 .可靠性：具有简单、健壮、良好的性能，如果消息m被到一台服务器接受，那么它将被所有的服务器接受。

3 .实时性：Zookeeper保证客户端将在一个时间间隔范围内获得服务器的更新信息，或者服务器失效的信息。但由于网络延时等原因，Zookeeper不能保证两个客户端能同时得到刚更新的数据，如果需要最新数据，应该在读数据之前调用sync()接口。

4 .等待无关（wait-free）：慢的或者失效的client不得干预快速的client的请求，使得每个client都能有效的等待。

5.原子性：更新只能成功或者失败，没有中间状态。

6 .顺序性：包括全局有序和偏序两种：全局有序是指如果在一台服务器上消息a在消息b前发布，则在所有Server上消息a都将在消息b前被发布；偏序是指如果一个消息b在消息a后被同一个发送者发布，a必将排在b前面。

2 ZooKeeper的工作原理

Zookeeper的核心是原子广播，这个机制保证了各个Server之间的同步。实现这个机制的协议叫做Zab协议。Zab协议有两种模式，它们分别是恢复模式（选主）和广播模式（同步）。当服务启动或者在领导者崩溃后，Zab就进入了恢复模式，当领导者被选举出来，且大多数Server完成了和leader的状态同步以后，恢复模式就结束了。状态同步保证了leader和Server具有相同的系统状态。

为了保证事务的顺序一致性，zookeeper采用了递增的事务id号（zxid）来标识事务。所有的提议（proposal）都在被提出的时候加上了zxid。实现中zxid是一个64位的数字，它高32位是epoch用来标识leader关系是否改变，每次一个leader被选出来，它都会有一个新的epoch，标识当前属于那个leader的统治时期。低32位用于递增计数。

每个Server在工作过程中有三种状态：

LOOKING：当前Server不知道leader是谁，正在搜寻
LEADING：当前Server即为选举出来的leader
FOLLOWING：leader已经选举出来，当前Server与之同步

2.1 选主流程

当leader崩溃或者leader失去大多数的follower，这时候zk进入恢复模式，恢复模式需要重新选举出一个新的leader，让所有的Server都恢复到一个正确的状态。Zk的选举算法有两种：一种是基于basic paxos实现的，另外一种是基于fast paxos算法实现的。系统默认的选举算法为fast paxos。先介绍basic paxos流程：

1 .选举线程由当前Server发起选举的线程担任，其主要功能是对投票结果进行统计，并选出推荐的Server；
2 .选举线程首先向所有Server发起一次询问(包括自己)；
3 .选举线程收到回复后，验证是否是自己发起的询问(验证zxid是否一致)，然后获取对方的id(myid)，并存储到当前询问对象列表中，最后获取对方提议的leader相关信息(id,zxid)，并将这些信息存储到当次选举的投票记录表中；
4. 收到所有Server回复以后，就计算出zxid最大的那个Server，并将这个Server相关信息设置成下一次要投票的Server；
5. 线程将当前zxid最大的Server设置为当前Server要推荐的Leader，如果此时获胜的Server获得n/2 + 1的Server票数，设置当前推荐的leader为获胜的Server，将根据获胜的Server相关信息设置自己的状态，否则，继续这个过程，直到leader被选举出来。

通过流程分析我们可以得出：要使Leader获得多数Server的支持，则Server总数必须是奇数2n+1，且存活的Server的数目不得少于n+1.

每个Server启动后都会重复以上流程。在恢复模式下，如果是刚从崩溃状态恢复的或者刚启动的server还会从磁盘快照中恢复数据和会话信息，zk会记录事务日志并定期进行快照，方便在恢复时进行状态恢复。选主的具体流程图如下所示：

fast paxos流程是在选举过程中，某Server首先向所有Server提议自己要成为leader，当其它Server收到提议以后，解决epoch和zxid的冲突，并接受对方的提议，然后向对方发送接受提议完成的消息，重复这个流程，最后一定能选举出Leader。其流程图如下所示：

2.2 同步流程

选完leader以后，zk就进入状态同步过程。

1. leader等待server连接；
2 .Follower连接leader，将最大的zxid发送给leader；
3 .Leader根据follower的zxid确定同步点；
4 .完成同步后通知follower 已经成为uptodate状态；
5 .Follower收到uptodate消息后，又可以重新接受client的请求进行服务了。

流程图如下所示：

2.3 工作流程

2.3.1 Leader工作流程

Leader主要有三个功能：

1 .恢复数据；
2 .维持与Learner的心跳，接收Learner请求并判断Learner的请求消息类型；
3 .Learner的消息类型主要有PING消息、REQUEST消息、ACK消息、REVALIDATE消息，根据不同的消息类型，进行不同的处理。

PING消息是指Learner的心跳信息；REQUEST消息是Follower发送的提议信息，包括写请求及同步请求；ACK消息是Follower的对提议的回复，超过半数的Follower通过，则commit该提议；REVALIDATE消息是用来延长SESSION有效时间。
Leader的工作流程简图如下所示，在实际实现中，流程要比下图复杂得多，启动了三个线程来实现功能。

2.3.2 Follower工作流程

Follower主要有四个功能：

1. 向Leader发送请求（PING消息、REQUEST消息、ACK消息、REVALIDATE消息）；
2 .接收Leader消息并进行处理；
3 .接收Client的请求，如果为写请求，发送给Leader进行投票；
4 .返回Client结果。

Follower的消息循环处理如下几种来自Leader的消息：

1 .PING消息：心跳消息；
2 .PROPOSAL消息：Leader发起的提案，要求Follower投票；
3 .COMMIT消息：服务器端最新一次提案的信息；
4 .UPTODATE消息：表明同步完成；
5 .REVALIDATE消息：根据Leader的REVALIDATE结果，关闭待revalidate的session还是允许其接受消息；
6 .SYNC消息：返回SYNC结果到客户端，这个消息最初由客户端发起，用来强制得到最新的更新。

Follower的工作流程简图如下所示，在实际实现中，Follower是通过5个线程来实现功能的。

对于observer的流程不再叙述，observer流程和Follower的唯一不同的地方就是observer不会参加leader发起的投票。

posted @ 2013-06-22 23:03 鑫龙阅读(480) | 评论 (0) | 编辑收藏

分布式服务框架 Zookeeper -- 管理分布式环境中的数据

摘要: 安装和配置详解本文介绍的 Zookeeper 是以 3.2.2 这个稳定版本为基础，最新的版本可以通过官网 http://hadoop.apache.org/zookeeper/来获取，Zookeeper 的安装非常简单，下面将从单机模式和集群模式两个方面介绍 Zookeeper 的安装和配置。单机模式单机安装非常简单，只要获取到 Zookeeper 的压缩包并解压到某个目录如：/hom... 阅读全文

posted @ 2013-06-22 22:19 鑫龙阅读(274) | 评论 (0) | 编辑收藏

Google利器之Chubby

http://blog.csdn.net/historyasamirror/article/details/3870168

Google利器之Chubby

写完了Google Cluster，该轮到Chubby了。

参考文献：
[1] The Chubby lock service for loosely-coupled distributed systems
[2] Paxos Made Simple

声明

文中大部分的观点来自于文献[1]中的描述，但也夹杂了部分本人自己的理解，所以不能保证本文的正确性。真想深入了解Chubby还是好好读原版论文吧：)

前言

MapReduce很多人已经知道了，但关于Chubyy似乎熟悉它的就非常有限，这倒是不奇怪，因为MapReduce是一个针对开发人员的ProgrammingModel，自然会有很多人去学习它，而Chubby更多的是一种为了实现MapReduce或者Bigtable而构建的内部的工具，对于开发人员来说基本上是透明的。文献[1]我反复读了至少有两三天，但感觉也只是一个囫囵吞枣的结果，里面有很多工程实现上的细节，如果不是自己亲自去设计或者实现，很难体会到其中的道理和奥妙。但是，对于这样一个分布式service的研究，还是让我对一个分布式系统的结构和设计思想有了更加直观的感觉。

从distributed consensus problem说起

distributed consensus problem(分布的一致性问题)是分布式算法中的一个经典问题。它的问题描述大概是这样的：在一个分布式系统中，有一组的Process，它们需要确定一个Value。于是每个Process都提出了一个Value，consensus就是指只有其中的一个Value能够被选中作为最后确定的值，并且当这个值被选出来以后，所有的Process都需要被通知到。
表面上看，这个问题很容易解决。比如设置一个server，所有的process都向这个server提交一个Value，这个server可以通过一个简单的规则来挑选出一个Value（例如最先到达的Value被选中），然后由这个server通知所有的Process。但是在分布式系统中，就会有各种的问题发生，例如，这个server崩溃了怎么办，所以我们可能需要有几台server共同决定。还有，Process提交Value的时间都不一样，网络传输过程中由于延迟这些Value到达server的顺序也都没有保证。
为了解决这个问题，有很多人提出了各种各样的Protocol，这些Protocol可以看做是一组需要遵循的规则，按照这些规则，这些Process就能够选举出一个唯一的Value。其中，最有名的一个Protocol就是Paxos算法。（八卦一下，Paxos的提出者叫做Lamport，有很多分布式的算法都是他提出的，他还是Latex的作者，大牛啊...）。想更加了解Paxos算法可以参考文献[2]，很漂亮的一篇文章。

那么这些和Chubby有什么关系呢？其实Chubby就是为了这个问题而构建出来的。只是它并不是一个Protocol或者是一个算法，而是google精心设计的一个service。这个service不仅能够解决一致性问题，还有其它的一些很实用的好处，会在下文慢慢介绍。

一个实例

在Google File System(GFS)中，有很多的server，这些server需要选举其中的一台作为master server。这其实是一个很典型的consensus问题，Value就是master server的地址。GFS就是用Chubby来解决的这个问题，所有的server通过Chubby提供的通信协议到Chubby server上创建同一个文件，当然，最终只有一个server能够获准创建这个文件，这个server就成为了master，它会在这个文件中写入自己的地址，这样其它的server通过读取这个文件就能知道被选出的master的地址。

Chubby是什么

从上面的这个实例可以看出，Chubby首先是一个分布式的文件系统。Chubby能够提供机制使得client可以在Chubby service上创建文件和执行一些文件的基本操作。说它是分布式的文件系统，是因为一个Chubby cell是一个分布式的系统，一般包含了5台机器，整个文件系统是部署在这5台机器上的。
但是，从更高一点的语义层面上，Chubby是一个lock service，一个针对松耦合的分布式系统的lock service。所谓lock service，就是这个service能够提供开发人员经常用的“锁”，“解锁”功能。通过Chubby，一个分布式系统中的上千个client都能够对于某项资源进行“加锁”，“解锁”。
那么，Chubby是怎样实现这样的“锁”功能的？就是通过文件。Chubby中的“锁”就是文件，在上例中，创建文件其实就是进行“加锁”操作，创建文件成功的那个server其实就是抢占到了“锁”。用户通过打开、关闭和读取文件，获取共享锁或者独占锁；并且通过通信机制，向用户发送更新信息。

综上所述，Chubby是一个lock service，通过这个lock service可以解决分布式中的一致性问题，而这个lock service的实现是一个分布式的文件系统。

可能会有人问，为什么不是直接实现一个类似于Paxos算法这样的Protocol来解决一致性问题，而是要通过一个lock service来解决？文献[1]中提到，用lock service这种方式有几个好处：
1.大部分开发人员在开始开发service的时候都不会考虑到这种一致性的问题，所以一开始都不会使用consensus protocol。只有当service慢慢成熟以后，才开始认真对待这个问题。采用lock service可以使得在保持原有的程序架构和通信机制的情况下，通过添加简单的语句就可以解决一致性问题；
2.正如上文实例中所展现，很多时候并不仅仅是选举出一个master，还需要将这个master的地址告诉其它人或者保存某个信息，这种时候，使用Chubby中的文件，不仅仅是提供锁功能，还能在文件中记录下有用的信息（比如master的地址）。所以，很多的开发人员通过使用Chubby来保存metadata和configuration。
3. 一个基于锁的开发接口更容易被开发人员所熟悉。并不是所有的开发人员都了解consensus protocol的，但大部分人应该都用过锁。
4. 一个consensus protocol一般来说需要使用到好几台副本来保证HA（详见Paxos算法），而使用Chubby，就算只有一个client也能用。
可以看出，之所以用lock service这样的形式，是因为Chubby不仅仅想解决一致性问题，还可以提供更多更有用的功能。事实上，Google有很多开发人员将Chubby当做name service使用，效果非常好。

关于lock service，还有两个名词需要提及。
一个是advisory lock。Chubby中的lock都是advisory lock。所谓的advisory lock，举个例子，就是说当有人将某个文件锁住以后，如果有其他的人想不解锁而直接访问这个文件，这种行为是不会被阻止的。和advisory lock对应的是mandatory lock，即如果某个文件被锁住以后，如果有其他的人直接访问它，那么这种行为是会产生exception的。
另一个是coarse-grained（粗颗粒度的）。Chubby的lock service是coarse-grained，就是说Chubby中的lock一般锁住的时间都比较长，可能是几小时或者几天。与之对应的是fined-grained，这种lock一般只维持几秒或者更少。这两种锁在实现的时候是会有很多不同的考虑的，比如coarse-grained的lock service的负载要小很多，因为加锁解锁并不会太频繁。其它的差别详见文献[1]。

Chubby的架构

上图就是Chubby的系统架构。

基本上分为了两部分：服务器一端，称为Chubby cell；client一端，每个Chubby的client都有一个Chubby library。这两部分通过RPC进行通信。
client端通过Chubby library的接口调用，在Chubby cell上创建文件来获得相应的锁的功能。
由于整个Chubby系统比较复杂，且细节很多，我个人又将整个系统分为了三个部分：
Chubby cell的一致性部分
分布式文件系统部分
client与Chubby cell的通信和连接部分

先从Chubby cell的一致性部分说起。
一般来说，一个Chubby cell由五台server组成，可以支持一整个数据中心的上万台机器的lock service。
cell中的每台server我们称之为replicas（副本）。
当Chubby工作的时候，首先它需要从这些replicas中选举出一个master。注意，这其实也是一个distributed consensus problem，也就是说Chubby也存在着分布式的一致性问题。Chubby是通过采用consensus protocol（很可能就是Paxos算法）来解决这个问题的。所以，Chubby的client用Chubby提供的lock service来解决一致性问题，而Chubby系统内部的一致性问题则是用consensus protocol解决的。
每个master都具有一定的期限，成为master lease。在这个期限中，副本们不会再选举一个其它的master。
为了安全性和容错的考虑，所有的replicas（包括master）都维护的同一个DB的拷贝。但是，只有master能够接受client提交的操作对DB进行读和写，而其它的replicas只是和master进行通信来update它们各自的DB。所以，一旦一个master被选举出来后，所有的client端都之和master进行通信（如图所示），如果是读操作，那么master一台机器就搞定了，如果是写操作，master会通知其它的replicas进行update。这样的话，一旦master意外停机，那么其它的replicas也能够很快的选举出另外一个master。

再说说Chubby的文件系统
前文说过，Chubby的底层实现其实就是一个分布式的文件系统。这个文件系统的接口是类似于Unix系统的。例如，对于文件名“/ls/foo /wombat/pouch”，ls表示的是“lock service”，foo表示的是某个Chubby cell的名字，wombat/pouch则是这个cell上的某个文件目录或者文件名。如果一个client端使用Chubby library来创建这样一个文件名，那么这样一个文件就会在Chubby cell上被创建。
Chubby的文件系统由于它的特殊用途做了很多的简化。例如它不支持文件的转移，不记录文件最后访问时间等等。整个文件系统只包含有文件和目录，统一称为“Node”。文件系统采用Berkeley DB来保存Node的信息，主要是一种map的关系。Key就是Node的名字，Value就是Node的内容。
还有一点需要提及的是，Chubby cell和client之间用了event形式的通知机制。client在创建了文件之后会得到一个handle，并且还可以订阅一系列的event，例如文件内容修改的event。这样的话，一旦client相关的文件内容被修改了，那么cell会通过机制发送一个event来告诉client该文件被修改了。

最后谈谈client与cell的交互部分
这里大致包含两部分的内容：cache的同步机制和KeepAlive握手协议。
为了降低client和cell之间通信的压力和频率，client在本地会保存一个和自己相关的Chubby文件的cache。例如如果client通过Chubby library在cell上创建了一个文件，那么在client本地，也会有一个相同的文件在cache中创建，这个cache中的文件的内容和cell上文件的内容是一样的。这样的话，client如果想访问这个文件，就可以直接访问本地的cache而不通过网络去访问cell。
cache有两个状态，有效和无效。当有一个client要改变某个File的时候，整个修改会被master block，然后master会发送无效标志给所有cache了这个数据的client（它维护了这么一个表），当其它client端收到这个无效标志后，就会将cache中的状态置为无效，然后返回一个acknowledge；当master确定收到了所有的acknowledge之后，才完成整个modification。
需要注意的是，master并不是发送update给client而是发送无效标志给client。这是因为如果发送update给client，那么每一次数据的修改都需要发送一大堆的update，而发送无效标示的话，对一个数据的很多次修改只需要发送一个无效标示，这样大大降低了通信量。

至于KeepAlive协议，则是为了保证client和master随时都保持着联系。client和master每隔一段时间就会KeepAlive一次，这样的话，如果master意外停机，client可以很快的知道这个消息，然后迅速的转移到新的master上。并且，这种转移对于client端的application是透明的，也就是说application并不会知道master发生了错误。关于cache和KeepAlive还有很多的细节，想了解的读文献[1]吧。

总结

其实在我的这篇文章中，还有一个很大的主题没有提及，那就是Chubby的容错机制。基本上，容错这个思想贯穿了文献[1]的始终，也正是因此，我很难将它单独提取出来解释，因为它散落在了Chubby系统设计的所有角落。我个人感觉，容错是一个分布式系统设计的核心思想，在设计的时候要求考虑到所有可能会发生的错误，不仅仅包括了硬件的错误，网络的故障，还包括了开发人员可能出现的错误。我想，这是我读这篇文章[1]最大的收获。

/Files/mysileng/Paxos算法深入分析.doc

posted @ 2013-06-22 12:18 鑫龙阅读(350) | 评论 (0) | 编辑收藏

程序员技术练级攻略

月光博客6月12日发表了《写给新手程序员的一封信》，翻译自《An open letter to those who want to start programming》，我的朋友（他在本站的id是Mailper）告诉我，他希望在酷壳上看到一篇更具操作性的文章。因为他也是喜欢编程和技术的家伙，于是，我让他把他的一些学习Python和Web编程的一些点滴总结一下。于是他给我发来了一些他的心得和经历，我在把他的心得做了不多的增改，并根据我的经历增加了“进阶”一节。这是一篇由新手和我这个老家伙根据我们的经历完成的文章。

我的这个朋友把这篇文章取名叫Build Your Programming Technical Skills，我实在不知道用中文怎么翻译，但我在写的过程中，我觉得这很像一个打网游做任务升级的一个过程，所以取名叫“技术练级攻略”，题目有点大，呵呵，这个标题纯粹是为了好玩。这里仅仅是在分享Mailper和我个人的学习经历。（注：省去了我作为一个初学者曾经学习过的一些技术(今天明显过时了)，如：Delphi/Power builder，也省去了我学过的一些我觉得没意思的技术Lotus Notes/ActiveX/COM/ADO/ATL/.NET ……）

前言

你是否觉得自己从学校毕业的时候只做过小玩具一样的程序？走入职场后哪怕没有什么经验也可以把以下这些课外练习走一遍（朋友的抱怨：学校课程总是从理论出发，作业项目都看不出有什么实际作用，不如从工作中的需求出发）

建议：

不要乱买书，不要乱追新技术新名词，基础的东西经过很长时间积累而且还会在未来至少10年通用。
回顾一下历史，看看历史上时间线上技术的发展，你才能明白明天会是什么样。
一定要动手，例子不管多么简单，建议至少自己手敲一遍看看是否理解了里头的细枝末节。
一定要学会思考，思考为什么要这样，而不是那样。还要举一反三地思考。

注：你也许会很奇怪为什么下面的东西很偏Unix/Linux，这是因为我觉得Windows下的编程可能会在未来很没有前途，原因如下：

现在的用户界面几乎被两个东西主宰了，1）Web，2）移动设备iOS或Android。Windows的图形界面不吃香了。
越来越多的企业在用成本低性能高的Linux和各种开源技术来构架其系统，Windows的成本太高了。
微软的东西变得太快了，很不持久，他们完全是在玩弄程序员。详情参见《Windows编程革命史》

所以，我个人认为以后的趋势是前端是Web+移动，后端是Linux+开源。开发这边基本上没Windows什么事。

启蒙入门

1、学习一门脚本语言，例如Python/Ruby

可以让你摆脱对底层语言的恐惧感，脚本语言可以让你很快开发出能用得上的小程序。实践项目:

处理文本文件，或者csv (关键词 python csv, python open, python sys) 读一个本地文件，逐行处理（例如 word count，或者处理log）
遍历本地文件系统 (sys, os, path)，例如写一个程序统计一个目录下所有文件大小并按各种条件排序并保存结果
跟数据库打交道 (python sqlite)，写一个小脚本统计数据库里条目数量
学会用各种print之类简单粗暴的方式进行调试
学会用Google (phrase, domain, use reader to follow tech blogs)

为什么要学脚本语言，因为他们实在是太方便了，很多时候我们需要写点小工具或是脚本来帮我们解决问题，你就会发现正规的编程语言太难用了。

2、用熟一种程序员的编辑器(不是IDE) 和一些基本工具

Vim / Emacs / Notepad++，学会如何配置代码补全，外观，外部命令等。
Source Insight (或 ctag)

使用这些东西不是为了Cool，而是这些编辑器在查看、修改代码/配置文章/日志会更快更有效率。

3、熟悉Unix/Linux Shell和常见的命令行

如果你用windows，至少学会用虚拟机里的linux， vmware player是免费的，装个Ubuntu吧
一定要少用少用图形界面。
学会使用man来查看帮助
文件系统结构和基本操作 ls/chmod/chown/rm/find/ln/cat/mount/mkdir/tar/gzip …
学会使用一些文本操作命令 sed/awk/grep/tail/less/more …
学会使用一些管理命令 ps/top/lsof/netstat/kill/tcpdump/iptables/dd…
了解/etc目录下的各种配置文章，学会查看/var/log下的系统日志，以及/proc下的系统运行信息
了解正则表达式，使用正则表达式来查找文件。

对于程序员来说Unix/Linux比Windows简单多了。（参看我四年前CSDN的博文《其实Unix很简单》）学会使用Unix/Linux你会发现图形界面在某些时候实在是太难用了，相当地相当地降低工作效率。

4、学习Web基础（HTML/CSS/JS) + 服务器端技术 (LAMP)

未来必然是Web的世界，学习WEB基础的最佳网站是W3School。

学习HTML基本语法
学习CSS如何选中HTML元素并应用一些基本样式（关键词：box model）
学会用 Firefox + Firebug 或 chrome 查看你觉得很炫的网页结构，并动态修改。
学习使用Javascript操纵HTML元件。理解DOM和动态网页（http://oreilly.com/catalog/9780596527402) 网上有免费的章节，足够用了。或参看 DOM 。
学会用 Firefox + Firebug 或 chrome 调试Javascript代码（设置断点，查看变量，性能，控制台等）
在一台机器上配置Apache 或 Nginx
学习PHP，让后台PHP和前台HTML进行数据交互，对服务器相应浏览器请求形成初步认识。实现一个表单提交和反显的功能。
把PHP连接本地或者远程数据库 MySQL（MySQL 和 SQL现学现用够了）
跟完一个名校的网络编程课程（例如：http://www.stanford.edu/~ouster/cgi-bin/cs142-fall10/index.php ) 不要觉得需要多于一学期时间，大学生是全职一学期选3-5门课，你业余时间一定可以跟上
学习一个javascript库（例如jQuery 或 ExtJS）+ Ajax (异步读入一个服务器端图片或者数据库内容）+JSON数据格式。
HTTP: The Definitive Guide 读完前4章你就明白你每天上网用浏览器的时候发生的事情了(proxy, gateway, browsers)
做个小网站（例如：一个小的留言板，支持用户登录，Cookie/Session，增、删、改、查，上传图片附件，分页显示）
买个域名，租个空间，做个自己的网站。

进阶加深

1、 C语言和操作系统调用

重新学C语言，理解指针和内存模型，用C语言实现一下各种经典的算法和数据结构。推荐《计算机程序设计艺术》、《算法导论》和《编程珠玑》。
学习（麻省理工免费课程）计算机科学和编程导论
学习（麻省理工免费课程）C语言内存管理
学习Unix/Linux系统调用（Unix高级环境编程），，了解系统层面的东西。

用这些系统知识操作一下文件系统，用户（实现一个可以拷贝目录树的小程序）
用fork/wait/waitpid写一个多进程的程序，用pthread写一个多线程带同步或互斥的程序。多进程多进程购票的程序。
用signal/kill/raise/alarm/pause/sigprocmask实现一个多进程间的信号量通信的程序。
学会使用gcc和gdb来编程和调试程序（参看我的《用gdb调试程序》）
学会使用makefile来编译程序。（参看我的《跟我一起写makefile》）
IPC和Socket的东西可以放到高级中来实践。

学习Windows SDK编程（Windows 程序设计，MFC程序设计）

写一个窗口，了解WinMain/WinProcedure，以及Windows的消息机制。
写一些程序来操作Windows SDK中的资源文件或是各种图形控件，以及作图的编程。
学习如何使用MSDN查看相关的SDK函数，各种WM_消息以及一些例程。
这本书中有很多例程，在实践中请不要照抄，试着自己写一个自己的例程。
不用太多于精通这些东西，因为GUI正在被Web取代，主要是了解一下Windows 图形界面的编程。@virushuo 说：“ 我觉得GUI确实不那么热门了，但充分理解GUI工作原理是很重要的。包括移动设备开发，如果没有基础知识仍然很吃力。或者说移动设备开发必须理解GUI工作，或者在win那边学，或者在mac/iOS上学”。

2、学习Java

Java 的学习主要是看经典的Core Java 《Java 核心技术编程》和《Java编程思想》（有两卷，我仅链了第一卷，足够了，因为Java的图形界面了解就可以了）
学习JDK，学会查阅Java API Doc http://download.oracle.com/javase/6/docs/api/
了解一下Java这种虚拟机语言和C和Python语言在编译和执行上的差别。从C、Java、Python思考一下“跨平台”这种技术。
学会使用IDE Eclipse，使用Eclipse 编译，调试和开发Java程序。
建一个Tomcat的网站，尝试一下JSP/Servlet/JDBC/MySQL的Web开发。把前面所说的那个PHP的小项目试着用JSP和Servlet实现一下。

3、Web的安全与架构

学习HTML5，网上有很多很多教程，以前酷壳也介绍过很多，我在这里就不罗列了。
学习Web开发的安全问题（参考新浪微博被攻击的这个事，以及Ruby的这篇文章）
学习HTTP Server的rewrite机制，Nginx的反向代理机制，fast-cgi（如：PHP-FPM）
学习Web的静态页面缓存技术。
学习Web的异步工作流处理，数据Cache，数据分区，负载均衡，水平扩展的构架。
实践任务：

使用HTML5的canvas 制作一些Web动画。
尝试在前面开发过的那个Web应用中进行SQL注入，JS注入，以及XSS攻击。
把前面开发过的那个Web应用改成构造在Nginx + PHP-FPM + 静态页面缓存的网站

4、学习关系型数据库

你可以安装MSSQLServer或MySQL来学习数据库。
学习教科书里数据库设计的那几个范式，1NF，2NF，3NF，……
学习数据库的存过，触发器，视图，建索引，游标等。
学习SQL语句，明白表连接的各种概念（参看《SQL Join的图示》）
学习如何优化数据库查询（参看《MySQL的优化》）
实践任务：设计一个论坛的数据库，至少满足3NF，使用SQL语句查询本周，本月的最新文章，评论最多的文章，最活跃用户。

5、一些开发工具

学会使用SVN或Git来管理程序版本。
学会使用JUnit来对Java进行单元测试。
学习C语言和Java语言的coding standard 或 coding guideline。（我N年前写过一篇关C语言非常简单的文章——《编程修养》，这样的东西你可以上网查一下，一大堆）。
推荐阅读《代码大全》《重构》《代码整洁之道》

高级深入

1、C++ / Java 和面向对象

我个人以为学好C++，Java也就是举手之劳。但是C++的学习曲线相当的陡。不过，我觉得C++是最需要学好的语言了。参看两篇趣文“C++学习信心图” 和“21天学好C++”

学习（麻省理工免费课程）C++面向对象编程
读我的 “如何学好C++”中所推荐的那些书至少两遍以上（如果你对C++的理解能够深入到像我所写的《C++虚函数表解析》或是《C++对象内存存局（上）（下）》，或是《C/C++返回内部静态成员的陷阱》那就非常不错了）
然后反思为什么C++要干成这样，Java则不是？你一定要学会对比C++和Java的不同。比如，Java中的初始化，垃圾回收，接口，异常，虚函数，等等。
实践任务：

用C++实现一个BigInt，支持128位的整形的加减乘除的操作。
用C++封装一个数据结构的容量，比如hash table。
用C++封装并实现一个智能指针（一定要使用模板）。

《设计模式》必需一读，两遍以上，思考一下，这23个模式的应用场景。主要是两点：1）钟爱组合而不是继承，2）钟爱接口而不是实现。（也推荐《深入浅出设计模式》）
实践任务：

使用工厂模式实现一个内存池。
使用策略模式制做一个类其可以把文本文件进行左对齐，右对齐和中对齐。
使用命令模式实现一个命令行计算器，并支持undo和redo。
使用修饰模式实现一个酒店的房间价格订价策略——旺季，服务，VIP、旅行团、等影响价格的因素。

学习STL的用法和其设计概念 - 容器，算法，迭代器，函数子。如果可能，请读一下其源码。
实践任务：尝试使用面向对象、STL，设计模式、和WindowsSDK图形编程的各种技能

做一个贪吃蛇或是俄罗斯方块的游戏。支持不同的级别和难度。
做一个文件浏览器，可以浏览目录下的文件，并可以对不同的文件有不同的操作，文本文件可以打开编辑，执行文件则执行之，mp3或avi文件可以播放，图片文件可以展示图片。

学习C++的一些类库的设计，如： MFC（看看候捷老师的《深入浅出MFC》），Boost, ACE, CPPUnit，STL （STL可能会太难了，但是如果你能了解其中的设计模式和设计那就太好了，如果你能深入到我写的《STL string类的写时拷贝技术》那就非常不错了，ACE需要很强在的系统知识，参见后面的“加强对系统的了解”）
Java是真正的面向对象的语言，Java的设计模式多得不能再多，也是用来学习面向对象的设计模式的最佳语言了（参看Java中的设计模式）。
推荐阅读《Effective Java》 and 《Java解惑》
学习Java的框架，Java的框架也是多，如Spring, Hibernate，Struts 等等，主要是学习Java的设计，如IoC等。
Java的技术也是烂多，重点学习J2EE架构以及JMS， RMI, 等消息传递和远程调用的技术。
学习使用Java做Web Service （官方教程在这里）
实践任务： 尝试在Spring或Hibernate框架下构建一个有网络的Web Service的远程调用程序，并可以在两个Service中通过JMS传递消息。

C++和Java都不是能在短时间内能学好的，C++玩是的深，Java玩的是广，我建议两者选一个。我个人的学习经历是：

深究C++（我深究C/C++了十来年了）
学习Java的各种设计模式。

2、加强系统了解

重要阅读下面的几本书：

《Unix编程艺术》了解Unix系统领域中的设计和开发哲学、思想文化体系、原则与经验。你一定会有一种醍醐灌顶的感觉。
《Unix网络编程卷1，套接字》这是一本看完你就明白网络编程的书。重要注意TCP、UDP，以及多路复用的系统调用select/poll/epoll的差别。
《TCP/IP详解卷1:协议》- 这是一本看完后你就可以当网络黑客的书。了解以太网的的运作原理，了解TCP/IP的协议，运作原理以及如何TCP的调优。
实践任务：

理解什么是阻塞（同步IO），非阻塞（异步IO），多路复用（select, poll, epoll）的IO技术。
写一个网络聊天程序，有聊天服务器和多个聊天客户端（服务端用UDP对部分或所有的的聊天客户端进Multicast或Broadcast）。
写一个简易的HTTP服务器。

《Unix网络编程卷2，进程间通信》信号量，管道，共享内存，消息等各种IPC…… 这些技术好像有点老掉牙了，不过还是值得了解。
实践任务：

主要实践各种IPC进程序通信的方法。
尝试写一个管道程序，父子进程通过管道交换数据。
尝试写一个共享内存的程序，两个进程通过共享内存交换一个C的结构体数组。

学习《Windows核心编程》一书。把CreateProcess，Windows线程、线程调度、线程同步（Event, 信号量，互斥量）、异步I/O，内存管理，DLL，这几大块搞精通。
实践任务：使用CreateProcess启动一个记事本或IE，并监控该程序的运行。把前面写过的那个简易的HTTP服务用线程池实现一下。写一个DLL的钩子程序监控指定窗口的关闭事件，或是记录某个窗口的按键。
有了多线程、多进程通信，TCP/IP，套接字，C++和设计模式的基本，你可以研究一下ACE了。使用ACE重写上述的聊天程序和HTTP服务器（带线程池）
实践任务：通过以上的所有知识，尝试

写一个服务端给客户端传大文件，要求把100M的带宽用到80%以上。（注意，磁盘I/O和网络I/O可能会很有问题，想一想怎么解决，另外，请注意网络传输最大单元MTU）
了解BT下载的工作原理，用多进程的方式模拟BT下载的原理。

3、系统架构

负载均衡。HASH式的，纯动态式的。（可以到Google学术里搜一些关于负载均衡的文章读读）
多层分布式系统 – 客户端服务结点层、计算结点层、数据cache层，数据层。J2EE是经典的多层结构。
CDN系统 – 就近访问，内容边缘化。
P2P式系统，研究一下BT和电驴的算法。比如：DHT算法。
服务器备份，双机备份系统（Live-Standby和Live-Live系统），两台机器如何通过心跳监测对方？集群主结点备份。
虚拟化技术，使用这个技术，可以把操作系统当应用程序一下切换或重新配置和部署。
学习Thrift，二进制的高性能的通讯中间件，支持数据(对象)序列化和多种类型的RPC服务。
学习Hadoop。Hadoop框架中最核心的设计就是：MapReduce和HDFS。MapReduce的思想是由Google的一篇论文所提及而被广为流传的，简单的一句话解释MapReduce就是“任务的分解与结果的汇总”。HDFS是Hadoop分布式文件系统（Hadoop Distributed File System）的缩写，为分布式计算存储提供了底层支持。
了解NoSQL数据库（有人说可能是一个过渡炒作的技术），不过因为超大规模以及高并发的纯动态型网站日渐成为主流，而SNS类网站在数据存取过程中有着实时性等刚性需求，这使得目前NoSQL数据库慢慢成了人们所关注的焦点，并大有成为取代关系型数据库而成为未来主流数据存储模式的趋势。当前NoSQL数据库很多，大部分都是开源的，其中比较知名的有：MemcacheDB、Redis、Tokyo Cabinet(升级版为Kyoto Cabinet)、Flare、MongoDB、CouchDB、Cassandra、Voldemort等。

写了那么多，回顾一下，觉得自己相当的有成就感。希望大家不要吓着，我自己这十来年也在不断地学习，今天我也在学习中，人生本来就是一个不断学习和练级的过程。不过，一定有漏的，也有不对的，还希望大家补充和更正。（我会根据大家的反馈随时更新此文）欢迎大家通过我的微博（@左耳朵耗子）和twitter（@haoel）和我交流。

—– 更新 2011/07/19 —–

1）有朋友奇怪为什么我在这篇文章开头说了web+移动，却没有在后面提到iOS/Android的前端开发。因为我心里有一种感觉，移动设备上的UI最终也会被Javascript取代。大家可以用iPhone或Android看看google+，你就会明白了。

2）有朋友说我这里的东西太多了，不能为了学习而学习，我非常同意。我在文章的前面也说了要思考。另外，千万不要以为我说的这些东西是一些新的技术，这份攻略里95%以上的全是基础。而且都是久经考验的基础技术。即是可以让你一通百通的技术，也是可以让你找到一份不错工作的技术。

3）有朋友说学这些东西学完都40了，还不如想想怎么去挣钱。我想告诉大家，一是我今年还没有40岁，二是学无止境啊，三是我不觉得挣钱有多难，难的是怎么让你值那么多钱？无论是打工还是创业，是什么东西让你自己的价值，让你公司的价值更值钱？别的地方我不敢说，对于互联网或IT公司来说，技术实力绝对是其中之一。

4）有朋友说技术都是工具，不应该如此痴迷这句话没有错，有时候我们需要更多的是抬起头来看看技术以外的事情，或者是说我们在作技术的时候不去思考为什么会有这个技术，为什么不是别的，问题不在于技术，问题在于我们死读书，读死书，成了技术的书呆子。

5）对于NoSQL，最近比较火，但我对其有点保守，所以，我只是说了解就可以。对于Hadoop，我觉得其在分布式系统上有巨大的潜力，所以需要学习。对于关系型数据库，的确是很重要的东西，这点是我的疏忽，在原文里补充。

（全文完，转载时请注明作者和出处）

（转载本站文章请注明作者和出处酷壳 – CoolShell.cn ，请勿用于任何商业用途）

posted @ 2013-06-20 22:59 鑫龙阅读(358) | 评论 (0) | 编辑收藏

m进制转换为n进制-任意进制转换算法

转自:http://www.cnblogs.com/pkuoliver/archive/2010/10/27/Convert-m-number-to-n-number.html

园子里有很多深藏不漏的高手，在这里聊这种基本问题是有点小儿科。不过本人只是想分享下自己的新的，代码，算法有不足之处，还请大家指正，共同进步。

这种题也是一道经典的面试题，主要考察进制转换细想，Coding质量等。

当我们把十进制转成二进制的时候，我们通过辗转相除，取余，逆置余数序列的过程得到新的进制的数。因此我们可以借助这种思想把M进制转成N进制的数。

如下是C的详细的实现方法

void m2n(int m, char* mNum, int n, char* nNum)  
{ 
    int i = 0; 
    char c, *p = nNum; 
  
    //这是一个考察地方，是否能用最少乘法次数。 
    while (*mNum != '\0') 
        i = i*m + *mNum++ - '0'; 
      
    //辗转取余 
    while (i) { 
        *p++ = i % n + '0'; 
        i /= n; 
    } 
    *p-- = '\0'; 
  
    //逆置余数序列 
    while (p > nNum) { 
        c = *p; 
        *p-- = *nNum; 
        *nNum++ = c; 
    } 
}

观察上面的代码，存在着众多的不足。例如，要对输入参数做检查，数值的大小收到int值最大值的限制等。不过好在一点，该算法的时间复杂度是O(n)的。

我们霹雳无敌的赵大叔又提供了一种用Java实现的通用的进制转换方法，即使Windows的计算器也转不了的大数，这个算法也可以转。算和上面的算法相比，他的基本思想不变，还是辗转除，但是用了字符串做大数相除，很不错的创新点，赞一个。代码如下：

package test; 
  
/** 
 * 功能：将一个数从M进制转换成N进制 
 * MValue：M进制数的字符串表示方法 
 * Shang：保存中间运算结果 
 * M：M进制 
 * N：N进制 
 */
public class M2N { 
    // 在这里对输入赋值 
    public static String MValue = "1231412423534674574757"; 
    public static String Shang = null; 
    public static int M = 10; 
    public static int N = 8; 
  
    public static void main(String[] args) { 
        String nValue = ""; 
        Shang = MValue; 
        while(Shang.length() > 0) { 
            nValue = qiuyu(Shang) + nValue; 
        } 
        System.out.println(nValue); 
    } 
  
    /** 
     * 功能：对给定的M进制字符串对n求余。 
     *  
     * @param MTempValue 
     * @param m 
     * @param n 
     * @return 
     */
    public static String qiuyu(String MTempValue) { 
        Shang = ""; 
        int temp = 0; 
        while (MTempValue.length() > 0) { 
            int t = getIntFromStr(MTempValue.substring(0, 1)); 
            MTempValue = MTempValue.substring(1); 
            temp = temp * M + t; 
            Shang += getStrFromInt(temp / N); 
            temp = temp % N; 
        } 
        while(Shang.length() > 0 && Shang.charAt(0) == '0'){ 
            Shang = Shang.substring(1); 
        } 
        return getStrFromInt(temp); 
    } 
  
    public static int getIntFromStr(String str){ 
        return str.charAt(0) <= '9' && str.charAt(0) >= '0'?  
            str.charAt(0) - '0' : str.charAt(0) - 'a' + 10; 
    } 
  
    public static String getStrFromInt(int value){ 
        String result = null; 
        if(value>=0 && value<=9) 
            result = String.valueOf((char)('0' + value)); 
        else if(vlaue > 9 && value <36) 
        { 
            result = String.valueOf((char)('a' + value - 10)); 
        } 
        else
        { 
            result = "-1";// 出错误了 
        } 
        return result; 
    } 
}

赵大叔的算法好了不少，除了参数检查，大小写之外都很好。值得我们借鉴。

posted @ 2013-06-08 16:16 鑫龙阅读(827) | 评论 (0) | 编辑收藏

HBase简介（很好的梳理资料）

一、简介

history

started by chad walters and jim

2006.11 G release paper on BigTable

2007.2 inital HBase prototype created as Hadoop contrib

2007.10 First useable Hbase

2008.1 Hadoop become Apache top-level project and Hbase becomes subproject

2008.10 Hbase 0.18,0.19 released

hbase是bigtable的开源山寨版本。是建立的hdfs之上，提供高可靠性、高性能、列存储、可伸缩、实时读写的数据库系统。

它介于nosql和RDBMS之间，仅能通过主键(row key)和主键的range来检索数据，仅支持单行事务(可通过hive支持来实现多表join等复杂操作)。主要用来存储非结构化和半结构化的松散数据。

与hadoop一样，Hbase目标主要依靠横向扩展，通过不断增加廉价的商用服务器，来增加计算和存储能力。

HBase中的表一般有这样的特点：

1 大：一个表可以有上亿行，上百万列

2 面向列:面向列(族)的存储和权限控制，列(族)独立检索。

3 稀疏:对于为空(null)的列，并不占用存储空间，因此，表可以设计的非常稀疏。

下面一幅图是Hbase在Hadoop Ecosystem中的位置。

二、逻辑视图

HBase以表的形式存储数据。表有行和列组成。列划分为若干个列族(row family)

Row Key	column-family1	column-family2	column-family3
column1	column1	column1	column2	column3	column1
key1	t1:abc t2:gdxdf		t4:dfads t3:hello t2:world
key2	t3:abc t1:gdxdf		t4:dfads t3:hello		t2:dfdsfa t3:dfdf
key3		t2:dfadfasd t1:dfdasddsf				t2:dfxxdfasd t1:taobao.com

Row Key

与nosql数据库们一样,row key是用来检索记录的主键。访问hbase table中的行，只有三种方式：

1 通过单个row key访问

2 通过row key的range

3 全表扫描

Row key行键 (Row key)可以是任意字符串(最大长度是 64KB，实际应用中长度一般为 10-100bytes)，在hbase内部，row key保存为字节数组。

存储时，数据按照Row key的字典序(byte order)排序存储。设计key时，要充分排序存储这个特性，将经常一起读取的行存储放到一起。(位置相关性)

注意：

字典序对int排序的结果是1,10,100,11,12,13,14,15,16,17,18,19,2,20,21,…,9,91,92,93,94,95,96,97,98,99。要保持整形的自然序，行键必须用0作左填充。

行的一次读写是原子操作 (不论一次读写多少列)。这个设计决策能够使用户很容易的理解程序在对同一个行进行并发更新操作时的行为。

列族

hbase表中的每个列，都归属与某个列族。列族是表的chema的一部分(而列不是)，必须在使用表之前定义。列名都以列族作为前缀。例如courses:history ， courses:math 都属于 courses 这个列族。

访问控制、磁盘和内存的使用统计都是在列族层面进行的。实际应用中，列族上的控制权限能帮助我们管理不同类型的应用：我们允许一些应用可以添加新的基本数据、一些应用可以读取基本数据并创建继承的列族、一些应用则只允许浏览数据（甚至可能因为隐私的原因不能浏览所有数据）。

时间戳

HBase中通过row和columns确定的为一个存贮单元称为cell。每个 cell都保存着同一份数据的多个版本。版本通过时间戳来索引。时间戳的类型是 64位整型。时间戳可以由hbase(在数据写入时自动 )赋值，此时时间戳是精确到毫秒的当前系统时间。时间戳也可以由客户显式赋值。如果应用程序要避免数据版本冲突，就必须自己生成具有唯一性的时间戳。每个 cell中，不同版本的数据按照时间倒序排序，即最新的数据排在最前面。

为了避免数据存在过多版本造成的的管理 (包括存贮和索引)负担，hbase提供了两种数据版本回收方式。一是保存数据的最后n个版本，二是保存最近一段时间内的版本（比如最近七天）。用户可以针对每个列族进行设置。

Cell

由{row key, column( =<family> + <label>), version} 唯一确定的单元。cell中的数据是没有类型的，全部是字节码形式存贮。

三、物理存储

1 已经提到过，Table中的所有行都按照row key的字典序排列。

2 Table 在行的方向上分割为多个Hregion。

3 region按大小分割的，每个表一开始只有一个region，随着数据不断插入表，region不断增大，当增大到一个阀值的时候，Hregion就会等分会两个新的Hregion。当table中的行不断增多，就会有越来越多的Hregion。

4 Hregion是Hbase中分布式存储和负载均衡的最小单元。最小单元就表示不同的Hregion可以分布在不同的HRegion server上。但一个Hregion是不会拆分到多个server上的。

5 HRegion虽然是分布式存储的最小单元，但并不是存储的最小单元。

事实上，HRegion由一个或者多个Store组成，每个store保存一个columns family。

每个Strore又由一个memStore和0至多个StoreFile组成。如图：

StoreFile以HFile格式保存在HDFS上。

HFile分为六个部分：

Data Block 段–保存表中的数据，这部分可以被压缩

Meta Block 段 (可选的)–保存用户自定义的kv对，可以被压缩。

File Info 段–Hfile的元信息，不被压缩，用户也可以在这一部分添加自己的元信息。

Data Block Index 段–Data Block的索引。每条索引的key是被索引的block的第一条记录的key。

Meta Block Index段 (可选的)–Meta Block的索引。

Trailer–这一段是定长的。保存了每一段的偏移量，读取一个HFile时，会首先读取Trailer，Trailer保存了每个段的起始位置(段的Magic Number用来做安全check)，然后，DataBlock Index会被读取到内存中，这样，当检索某个key时，不需要扫描整个HFile，而只需从内存中找到key所在的block，通过一次磁盘io将整个 block读取到内存中，再找到需要的key。DataBlock Index采用LRU机制淘汰。

HFile的Data Block，Meta Block通常采用压缩方式存储，压缩之后可以大大减少网络IO和磁盘IO，随之而来的开销当然是需要花费cpu进行压缩和解压缩。

目标Hfile的压缩支持两种方式：Gzip，Lzo。

HLog(WAL log)

WAL 意为Write ahead log(http://en.wikipedia.org/wiki/Write-ahead_logging)，类似mysql中的binlog,用来做灾难恢复只用，Hlog记录数据的所有变更,一旦数据修改，就可以从log中进行恢复。

每个Region Server维护一个Hlog,而不是每个Region一个。这样不同region(来自不同table)的日志会混在一起，这样做的目的是不断追加单个文件相对于同时写多个文件而言，可以减少磁盘寻址次数，因此可以提高对table的写性能。带来的麻烦是，如果一台region server下线，为了恢复其上的region，需要将region server上的log进行拆分，然后分发到其它region server上进行恢复。

HLog文件就是一个普通的Hadoop Sequence File，Sequence File 的Key是HLogKey对象，HLogKey中记录了写入数据的归属信息，除了table和region名字外，同时还包括 sequence number和timestamp，timestamp是”写入时间”，sequence number的起始值为0，或者是最近一次存入文件系统中sequence number。HLog Sequece File的Value是HBase的KeyValue对象，即对应HFile中的KeyValue，可参见上文描述。

四、系统架构

Client

1 包含访问hbase的接口，client维护着一些cache来加快对hbase的访问，比如regione的位置信息。

Zookeeper

1 保证任何时候，集群中只有一个master

2 存贮所有Region的寻址入口。

3 实时监控Region Server的状态，将Region server的上线和下线信息实时通知给Master

4 存储Hbase的schema,包括有哪些table，每个table有哪些column family

Master

1 为Region server分配region

2 负责region server的负载均衡

3 发现失效的region server并重新分配其上的region

4 GFS上的垃圾文件回收

5 处理schema更新请求

Region Server

1 Region server维护Master分配给它的region，处理对这些region的IO请求

2 Region server负责切分在运行过程中变得过大的region

可以看到，client访问hbase上数据的过程并不需要master参与（寻址访问zookeeper和region server，数据读写访问regione server），master仅仅维护者table和region的元数据信息，负载很低。

五、关键算法 / 流程

region定位

系统如何找到某个row key (或者某个 row key range)所在的region

bigtable 使用三层类似B+树的结构来保存region位置。

第一层是保存zookeeper里面的文件，它持有root region的位置。

第二层root region是.META.表的第一个region其中保存了.META.z表其它region的位置。通过root region，我们就可以访问.META.表的数据。

.META.是第三层，它是一个特殊的表，保存了hbase中所有数据表的region 位置信息。

说明：

1 root region永远不会被split，保证了最需要三次跳转，就能定位到任意region 。

2.META.表每行保存一个region的位置信息，row key 采用表名+表的最后一样编码而成。

3 为了加快访问，.META.表的全部region都保存在内存中。

假设，.META.表的一行在内存中大约占用1KB。并且每个region限制为128MB。

那么上面的三层结构可以保存的region数目为：

(128MB/1KB) * (128MB/1KB) = = 2(34)个region

4 client会将查询过的位置信息保存缓存起来，缓存不会主动失效，因此如果client上的缓存全部失效，则需要进行6次网络来回，才能定位到正确的region(其中三次用来发现缓存失效，另外三次用来获取位置信息)。

读写过程

上文提到，hbase使用MemStore和StoreFile存储对表的更新。

数据在更新时首先写入Log(WAL log)和内存(MemStore)中，MemStore中的数据是排序的，当MemStore累计到一定阈值时，就会创建一个新的MemStore，并且将老的MemStore添加到flush队列，由单独的线程flush到磁盘上，成为一个StoreFile。于此同时，系统会在zookeeper中记录一个redo point，表示这个时刻之前的变更已经持久化了。(minor compact)

当系统出现意外时，可能导致内存(MemStore)中的数据丢失，此时使用Log(WAL log)来恢复checkpoint之后的数据。

前面提到过StoreFile是只读的，一旦创建后就不可以再修改。因此Hbase的更新其实是不断追加的操作。当一个Store中的StoreFile达到一定的阈值后，就会进行一次合并(major compact),将对同一个key的修改合并到一起，形成一个大的StoreFile，当StoreFile的大小达到一定阈值后，又会对 StoreFile进行split，等分为两个StoreFile。

由于对表的更新是不断追加的，处理读请求时，需要访问Store中全部的 StoreFile和MemStore，将他们的按照row key进行合并，由于StoreFile和MemStore都是经过排序的，并且StoreFile带有内存中索引，合并的过程还是比较快。

写请求处理过程

1 client向region server提交写请求

2 region server找到目标region

3 region检查数据是否与schema一致

4 如果客户端没有指定版本，则获取当前系统时间作为数据版本

5 将更新写入WAL log

6 将更新写入Memstore

7 判断Memstore的是否需要flush为Store文件。

region分配

任何时刻，一个region只能分配给一个region server。master记录了当前有哪些可用的region server。以及当前哪些region分配给了哪些region server，哪些region还没有分配。当存在未分配的region，并且有一个region server上有可用空间时，master就给这个region server发送一个装载请求，把region分配给这个region server。region server得到请求后，就开始对此region提供服务。

region server上线

master使用zookeeper来跟踪region server状态。当某个region server启动时，会首先在zookeeper上的server目录下建立代表自己的文件，并获得该文件的独占锁。由于master订阅了server 目录上的变更消息，当server目录下的文件出现新增或删除操作时，master可以得到来自zookeeper的实时通知。因此一旦region server上线，master能马上得到消息。

region server下线

当region server下线时，它和zookeeper的会话断开，zookeeper而自动释放代表这台server的文件上的独占锁。而master不断轮询 server目录下文件的锁状态。如果master发现某个region server丢失了它自己的独占锁，(或者master连续几次和region server通信都无法成功),master就是尝试去获取代表这个region server的读写锁，一旦获取成功，就可以确定：

1 region server和zookeeper之间的网络断开了。

2 region server挂了。

的其中一种情况发生了，无论哪种情况，region server都无法继续为它的region提供服务了，此时master会删除server目录下代表这台region server的文件，并将这台region server的region分配给其它还活着的同志。

如果网络短暂出现问题导致region server丢失了它的锁，那么region server重新连接到zookeeper之后，只要代表它的文件还在，它就会不断尝试获取这个文件上的锁，一旦获取到了，就可以继续提供服务。

master上线

master启动进行以下步骤:

1 从zookeeper上获取唯一一个代码master的锁，用来阻止其它master成为master。

2 扫描zookeeper上的server目录，获得当前可用的region server列表。

3 和2中的每个region server通信，获得当前已分配的region和region server的对应关系。

4 扫描.META.region的集合，计算得到当前还未分配的region，将他们放入待分配region列表。

master下线

由于master只维护表和region的元数据，而不参与表数据IO的过程，master下线仅导致所有元数据的修改被冻结(无法创建删除表，无法修改表的schema，无法进行region的负载均衡，无法处理region 上下线，无法进行region的合并，唯一例外的是region的split可以正常进行，因为只有region server参与)，表的数据读写还可以正常进行。因此master下线短时间内对整个hbase集群没有影响。从上线过程可以看到，master保存的信息全是可以冗余信息（都可以从系统其它地方收集到或者计算出来），因此，一般hbase集群中总是有一个master在提供服务，还有一个以上的’master’在等待时机抢占它的位置。

六、访问接口

HBase Shell
Java clietn API
HBase non-java access
- languages talking to the JVM
- - Jython interface to HBase
  - Groovy DSL for HBase
  - Scala interface to HBase
- languages with a custom protocol
- - REST gateway specification for HBase
  - 充分利用HTTP协议：GET POST PUT DELETE

- - text/plain
  - text/xml
  - application/json
  - application/x-protobuf
- Thrift gateway specification for HBase
- - java
  - cpp
  - rb
  - py
  - perl
  - php
HBase Map Reduce
Hive/Pig

七、结语：

全文对 Hbase做了 简单的介绍，有错误之处，敬请指正。未来将结合 Hbase 在淘宝数据平台的应用场景，在更多细节上进行深入。

参考文档

Bigtable: A Distributed Storage System for Structured Data

HFile: A Block-Indexed File Format to Store Sorted Key-Value Pairs for a thorough introduction Hbase Architecture 101

Hbase source code

很久没写博客了，因为很忙，不过今天发现一篇不错的文章，帮我梳理了下HBase，原文地址：http://www.tbdata.org/archives/1509

posted @ 2013-06-07 22:14 鑫龙阅读(306) | 评论 (0) | 编辑收藏

仅列出标题

mysileng

导航

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜

java中wait/notify机制

Dijkstra算法（单源最短路径）

逆序数及其求法

hadoop0.20.2在eclipse中的编译

Zookeeper工作原理

1 Zookeeper的基本概念

1.1 角色

1.2 设计目的

2 ZooKeeper的工作原理

2.1 选主流程

2.2 同步流程

2.3 工作流程

2.3.1 Leader工作流程

2.3.2 Follower工作流程

分布式服务框架 Zookeeper -- 管理分布式环境中的数据

Google利器之Chubby

程序员技术练级攻略

前言

启蒙入门

进阶加深

高级深入

m进制转换为n进制-任意进制转换算法

HBase简介（很好的梳理资料）

一、简介

二、逻辑视图

三、物理存储

四、系统架构

五、关键算法 / 流程

导航

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜

1 Zookeeper的基本概念

1.1 角色

1.2 设计目的

2 ZooKeeper的工作原理

2.1 选主流程

2.2 同步流程

2.3 工作流程

2.3.1 Leader工作流程

2.3.2 Follower工作流程

前言

启蒙入门

进阶加深

高级深入

一、 简介

二、 逻辑视图

三、 物理存储

四、 系统架构

五、关键算法 / 流程

一、简介

二、逻辑视图

三、物理存储

四、系统架构