java中wait/notify機制

通常，多線程之間需要協(xié)調(diào)工作。例如，瀏覽器的一個顯示圖片的線程displayThread想要執(zhí)行顯示圖片的任務(wù)，必須等待下載線程 downloadThread將該圖片下載完畢。如果圖片還沒有下載完，displayThread可以暫停，當downloadThread完成了任務(wù) 后，再通知displayThread“圖片準備完畢，可以顯示了”，這時，displayThread繼續(xù)執(zhí)行。
以上邏輯簡單的說就是：如果條件不滿足，則等待。當條件滿足時，等待該條件的線程將被喚醒。在Java中，這個機制的實現(xiàn)依賴于wait/notify。等待機制與鎖機制是密切關(guān)聯(lián)的。例如：
synchronized(obj) {while(!condition) {obj.wait();}obj.doSomething();}

當線程A獲得了obj鎖后，發(fā)現(xiàn)條件condition不滿足，無法繼續(xù)下一處理，于是線程A就wait()。
在另一線程B中，如果B更改了某些條件，使得線程A的condition條件滿足了，就可以喚醒線程A：
synchronized(obj) {condition = true;obj.notify();}

需要注意的概念是：
◆調(diào)用obj的wait(), notify()方法前，必須獲得obj鎖，也就是必須寫在synchronized(obj) {...} 代碼段內(nèi)。
◆調(diào)用obj.wait()后，線程A就釋放了obj的鎖，否則線程B無法獲得obj鎖，也就無法在synchronized(obj) {...} 代碼段內(nèi)喚醒A。
◆當obj.wait()方法返回后，線程A需要再次獲得obj鎖，才能繼續(xù)執(zhí)行。
◆如果A1,A2,A3都在obj.wait()，則B調(diào)用obj.notify()只能喚醒A1,A2,A3中的一個（具體哪一個由JVM決定）。
◆obj.notifyAll()則能全部喚醒A1,A2,A3，但是要繼續(xù)執(zhí)行obj.wait()的下一條語句，必須獲得obj鎖，因此，A1,A2,A3只有一個有機會獲得鎖繼續(xù)執(zhí)行，例如A1，其余的需要等待A1釋放obj鎖之后才能繼續(xù)執(zhí)行。
◆當B調(diào)用obj.notify/notifyAll的時候，B正持有obj鎖，因此，A1,A2,A3雖被喚醒，但是仍無法獲得obj鎖。直到B退出synchronized塊，釋放obj鎖后，A1,A2,A3中的一個才有機會獲得鎖繼續(xù)執(zhí)行。

posted @ 2014-04-07 17:27 鑫龍閱讀(256) | 評論 (0) | 編輯收藏

Dijkstra算法（單源最短路徑）

單源最短路徑問題，即在圖中求出給定頂點到其它任一頂點的最短路徑。在弄清楚如何求算單源最短路徑問題之前，必須弄清楚最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)。

一.最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)

該性質(zhì)描述為：如果P(i,j)={Vi....Vk..Vs...Vj}是從頂點i到j(luò)的最短路徑，k和s是這條路徑上的一個中間頂點，那么P(k,s)必定是從k到s的最短路徑。下面證明該性質(zhì)的正確性。

假設(shè)P(i,j)={Vi....Vk..Vs...Vj}是從頂點i到j(luò)的最短路徑，則有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(luò)的最短路徑相矛盾。因此該性質(zhì)得證。

二.Dijkstra算法

由上述性質(zhì)可知，如果存在一條從i到j(luò)的最短路徑(Vi.....Vk,Vj)，Vk是Vj前面的一頂點。那么(Vi...Vk)也必定是從i到k的最短路徑。為了求出最短路徑，Dijkstra就提出了以最短路徑長度遞增，逐次生成最短路徑的算法。譬如對于源頂點V0，首先選擇其直接相鄰的頂點中長度最短的頂點Vi，那么當前已知可得從V0到達Vj頂點的最短距離dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根據(jù)這種思路，

假設(shè)存在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，停止。

代碼實現(xiàn):

/*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;                 //頂點數(shù)
    int e;                 //邊數(shù)
}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直接相鄰，則權(quán)值置為無窮大
            path[i]=-1;
        }
        visited[i]=false;
        path[v0]=v0;
        dist[v0]=0;
    }
    visited[v0]=true;
    for(i=1;i<g.n;i++)     //循環(huán)擴展n-1次
    {
        int min=INT_MAX;
        int u;
        for(j=0;j<g.n;j++)    //尋找未被擴展的權(quán)值最小的頂點
        {
            if(visited[j]==false&&dist[j]<min)
            {
                min=dist[j];
                u=j;
            }
        }
        visited[u]=true;
        for(k=0;k<g.n;k++)   //更新dist數(shù)組的值和路徑的值
        {
            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;     //表示輸入的頂點數(shù)和邊數(shù)
    while(cin>>n>>e&&e!=0)
    {
        int i,j;
        int s,t,w;      //表示存在一條邊s->t,權(quán)值為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 鑫龍閱讀(593) | 評論 (0) | 編輯收藏

逆序數(shù)及其求法

1. 逆序數(shù)

所謂逆序數(shù)，就是指一個序列S[i]，統(tǒng)計處于序列的每個數(shù)的比這個數(shù)大并且排在它前面的數(shù)的數(shù)目，然后對于所有數(shù)，把這個數(shù)目加起來求和就是了。
比如 4 3 1 2
4第一個，所以數(shù)目為0
3的前面是4，大于3的數(shù)目為1
1的前面是4 3 ，大于1的數(shù)目為2
2的前面是4 3 1，大于2的數(shù)目為2
所以逆序數(shù)為1+2+2 = 5

求逆序數(shù)的兩種方法
常規(guī)方法是按照逆序數(shù)的規(guī)則做，結(jié)果復(fù)雜度是O(n*n)，一般來說，有兩種快速的求逆序數(shù)的方法
分別是歸并排序和樹狀數(shù)組法

2. 歸并排序
歸并排序是源于分而治之思想，詳細的過程可以查閱其他資料，總體思想是劃分一半，各自排好序后將兩個有序序列合并起來。

如何修改歸并排序求逆序數(shù)?
首先我們假設(shè)兩個有序序列 a[i]和b[i]，當合并時：
由于a[i]已是有序，所以對于a[i]的各個元素來說，排在它前面且比它大的數(shù)目都是0
當b[i]中含有比a[i]小的元素時，我們必然將b[i]元素插到前面，那么就是說，在b[i]原先位置到該插的位置中，所有數(shù)都比b[i]大且排在它前面
所以這是b[i]的數(shù)目為新插入位置newPos - 原來位置oldPos

那么對于一半的序列又怎么做呢？我們知道，歸并排序會繼續(xù)向下遞歸，而遞歸完成返回后將是兩組有序的序列，并且拿到局部的逆序數(shù)，
所以在Merge函數(shù)中添加這一計數(shù)操作即可

代碼示例如下：

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. 樹狀數(shù)組
求逆序數(shù)的另外一種方法是使用樹狀數(shù)組
對于小數(shù)據(jù)，可以直接插入樹狀數(shù)組，對于大數(shù)據(jù)，則需要離散化，所謂離散化，就是將
100 200 300 400 500 ---> 1 2 3 4 5

這里主要利用樹狀數(shù)組解決計數(shù)問題。

首先按順序把序列a[i]每個數(shù)插入到樹狀數(shù)組中，插入的內(nèi)容是1，表示放了一個數(shù)到樹狀數(shù)組中。
然后使用sum操作獲取當前比a[i]小的數(shù)，那么當前i - sum則表示當前比a[i]大的數(shù)，如此反復(fù)直到所有數(shù)都統(tǒng)計完，
比如
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;

過程很明了，所以逆序數(shù)為1+2+2=5

代碼示例如下：

//樹狀數(shù)組
__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;
}

//求逆序數(shù)

__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 鑫龍閱讀(397) | 評論 (0) | 編輯收藏

hadoop0.20.2在eclipse中的編譯

1. 下載Hadoop源代碼
Hadoop 各成員源代碼下載地址：http://svn.apache.org/repos/asf/hadoop，請使用SVN下載，在SVN瀏覽器中將trunk目錄下的源代碼check-out 出來即可。請注意只check-out出SVN 上的tag 目錄下的內(nèi)容，如：
http://svn.apache.org/repos/asf/hadoop/common/tag/release-0.20.2，

2. 準備編譯環(huán)境

2.1. 系統(tǒng)

CentOS5.5

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

2.3. 聯(lián)網(wǎng)
編譯Hadoop 會依賴很多第三方庫，但編譯工具Ant 會自動從網(wǎng)上下載缺少的庫，所以必須保證機器能夠訪問Internet。
2.4. java
編譯Hadoop要用JDK1.6 以上，網(wǎng)址：http://java.sun.com/javase/downloads/index.jsp。
安裝好之后，請設(shè)置好JAVA_HOME 環(huán)境變量。
2.5. Ant
需要使用Ant 工具來編譯Hadoop，可以從：http://ant.apache.org/ivy/download.cgi 下載Ant

安裝好之后，請設(shè)置好ANT_HOME 環(huán)境變量。

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 源代碼目錄，并設(shè)置Projectname 為hadoop-0.20.2-dev。工程導(dǎo)入完成后，進入Eclipse 主界面，可以看到hadoop-0.20.2 已經(jīng)導(dǎo)入進來，但可以看到目錄上有紅叉叉，是因為Elipse默認使用了Java Builder，而不是Ant Builder，所以下一步就是設(shè)置使用Ant Builder。

步驟3) 設(shè)置Builder 為Ant：右鍵hadoop-0.20.2-dev>Properties->Builders:

點擊Browse File System 按鈕，選擇hadoop-0.20.2源代碼目錄下的build.xml 文件，并設(shè)置Name 為Ant_Builder（Name 可以改成其它的，但建議使用Ant_Builder，因為這樣名副其實），操作結(jié)果如下圖所示：

Hadoop 各成員都需要編譯成jar，所以做如下圖所示的一個修改：

上面完成后，回到Builder 的主對話框，再將對話框中的Java Builder 下移，并將它前面的勾去掉。
進入Eclipse 主界面，由于之前選擇了Manual Build，所以需要人工方式驅(qū)動編譯，編譯成功后，可以看到BUILDSUCCESSFUL 字樣。

　請注意：如果上圖所示的菜單中的BuildAutomatically 被勾中，則在common的右鍵菜單中可能不會出現(xiàn)Build 子菜單。
在編譯過程中，Ant 會自動從網(wǎng)上下載所依賴的庫。hadoop-0.20.2 編譯成功結(jié)束后，可以在build 目錄下找到編譯后生成的文件hadoop-core-0.20.2-dev.jar。

3.2編譯過程中出現(xiàn)錯誤

1、可能有時候因為eclipse版本或者操作系統(tǒng)版本的問題使得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

轉(zhuǎn)自http://www.cnblogs.com/zyumeng/archive/2013/03/22/2975165.html

posted @ 2013-06-24 18:58 鑫龍閱讀(314) | 評論 (0) | 編輯收藏

Zookeeper工作原理

ZooKeeper是一個分布式的，開放源碼的分布式應(yīng)用程序協(xié)調(diào)服務(wù)，它包含一個簡單的原語集，分布式應(yīng)用程序可以基于它實現(xiàn)同步服務(wù)，配置維護和命名服務(wù)等。Zookeeper是hadoop的一個子項目，其發(fā)展歷程無需贅述。在分布式應(yīng)用中，由于工程師不能很好地使用鎖機制，以及基于消息的協(xié)調(diào)機制不適合在某些應(yīng)用中使用，因此需要有一種可靠的、可擴展的、分布式的、可配置的協(xié)調(diào)機制來統(tǒng)一系統(tǒng)的狀態(tài)。Zookeeper的目的就在于此。本文簡單分析zookeeper的工作原理，對于如何使用zookeeper不是本文討論的重點。

1 Zookeeper的基本概念

1.1 角色

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

1.2 設(shè)計目的

1.最終一致性：client不論連接到哪個Server，展示給它都是同一個視圖，這是zookeeper最重要的性能。

2 .可靠性：具有簡單、健壯、良好的性能，如果消息m被到一臺服務(wù)器接受，那么它將被所有的服務(wù)器接受。

3 .實時性：Zookeeper保證客戶端將在一個時間間隔范圍內(nèi)獲得服務(wù)器的更新信息，或者服務(wù)器失效的信息。但由于網(wǎng)絡(luò)延時等原因，Zookeeper不能保證兩個客戶端能同時得到剛更新的數(shù)據(jù)，如果需要最新數(shù)據(jù)，應(yīng)該在讀數(shù)據(jù)之前調(diào)用sync()接口。

4 .等待無關(guān)（wait-free）：慢的或者失效的client不得干預(yù)快速的client的請求，使得每個client都能有效的等待。

5.原子性：更新只能成功或者失敗，沒有中間狀態(tài)。

6 .順序性：包括全局有序和偏序兩種：全局有序是指如果在一臺服務(wù)器上消息a在消息b前發(fā)布，則在所有Server上消息a都將在消息b前被發(fā)布；偏序是指如果一個消息b在消息a后被同一個發(fā)送者發(fā)布，a必將排在b前面。

2 ZooKeeper的工作原理

Zookeeper的核心是原子廣播，這個機制保證了各個Server之間的同步。實現(xiàn)這個機制的協(xié)議叫做Zab協(xié)議。Zab協(xié)議有兩種模式，它們分別是恢復(fù)模式（選主）和廣播模式（同步）。當服務(wù)啟動或者在領(lǐng)導(dǎo)者崩潰后，Zab就進入了恢復(fù)模式，當領(lǐng)導(dǎo)者被選舉出來，且大多數(shù)Server完成了和leader的狀態(tài)同步以后，恢復(fù)模式就結(jié)束了。狀態(tài)同步保證了leader和Server具有相同的系統(tǒng)狀態(tài)。

為了保證事務(wù)的順序一致性，zookeeper采用了遞增的事務(wù)id號（zxid）來標識事務(wù)。所有的提議（proposal）都在被提出的時候加上了zxid。實現(xiàn)中zxid是一個64位的數(shù)字，它高32位是epoch用來標識leader關(guān)系是否改變，每次一個leader被選出來，它都會有一個新的epoch，標識當前屬于那個leader的統(tǒng)治時期。低32位用于遞增計數(shù)。

每個Server在工作過程中有三種狀態(tài)：

LOOKING：當前Server不知道leader是誰，正在搜尋
LEADING：當前Server即為選舉出來的leader
FOLLOWING：leader已經(jīng)選舉出來，當前Server與之同步

2.1 選主流程

當leader崩潰或者leader失去大多數(shù)的follower，這時候zk進入恢復(fù)模式，恢復(fù)模式需要重新選舉出一個新的leader，讓所有的Server都恢復(fù)到一個正確的狀態(tài)。Zk的選舉算法有兩種：一種是基于basic paxos實現(xiàn)的，另外一種是基于fast paxos算法實現(xiàn)的。系統(tǒng)默認的選舉算法為fast paxos。先介紹basic paxos流程：

1 .選舉線程由當前Server發(fā)起選舉的線程擔任，其主要功能是對投票結(jié)果進行統(tǒng)計，并選出推薦的Server；
2 .選舉線程首先向所有Server發(fā)起一次詢問(包括自己)；
3 .選舉線程收到回復(fù)后，驗證是否是自己發(fā)起的詢問(驗證zxid是否一致)，然后獲取對方的id(myid)，并存儲到當前詢問對象列表中，最后獲取對方提議的leader相關(guān)信息(id,zxid)，并將這些信息存儲到當次選舉的投票記錄表中；
4. 收到所有Server回復(fù)以后，就計算出zxid最大的那個Server，并將這個Server相關(guān)信息設(shè)置成下一次要投票的Server；
5. 線程將當前zxid最大的Server設(shè)置為當前Server要推薦的Leader，如果此時獲勝的Server獲得n/2 + 1的Server票數(shù)，設(shè)置當前推薦的leader為獲勝的Server，將根據(jù)獲勝的Server相關(guān)信息設(shè)置自己的狀態(tài)，否則，繼續(xù)這個過程，直到leader被選舉出來。

通過流程分析我們可以得出：要使Leader獲得多數(shù)Server的支持，則Server總數(shù)必須是奇數(shù)2n+1，且存活的Server的數(shù)目不得少于n+1.

每個Server啟動后都會重復(fù)以上流程。在恢復(fù)模式下，如果是剛從崩潰狀態(tài)恢復(fù)的或者剛啟動的server還會從磁盤快照中恢復(fù)數(shù)據(jù)和會話信息，zk會記錄事務(wù)日志并定期進行快照，方便在恢復(fù)時進行狀態(tài)恢復(fù)。選主的具體流程圖如下所示：

fast paxos流程是在選舉過程中，某Server首先向所有Server提議自己要成為leader，當其它Server收到提議以后，解決epoch和zxid的沖突，并接受對方的提議，然后向?qū)Ψ桨l(fā)送接受提議完成的消息，重復(fù)這個流程，最后一定能選舉出Leader。其流程圖如下所示：

2.2 同步流程

選完leader以后，zk就進入狀態(tài)同步過程。

1. leader等待server連接；
2 .Follower連接leader，將最大的zxid發(fā)送給leader；
3 .Leader根據(jù)follower的zxid確定同步點；
4 .完成同步后通知follower 已經(jīng)成為uptodate狀態(tài)；
5 .Follower收到uptodate消息后，又可以重新接受client的請求進行服務(wù)了。

流程圖如下所示：

2.3 工作流程

2.3.1 Leader工作流程

Leader主要有三個功能：

1 .恢復(fù)數(shù)據(jù)；
2 .維持與Learner的心跳，接收Learner請求并判斷Learner的請求消息類型；
3 .Learner的消息類型主要有PING消息、REQUEST消息、ACK消息、REVALIDATE消息，根據(jù)不同的消息類型，進行不同的處理。

PING消息是指Learner的心跳信息；REQUEST消息是Follower發(fā)送的提議信息，包括寫請求及同步請求；ACK消息是Follower的對提議的回復(fù)，超過半數(shù)的Follower通過，則commit該提議；REVALIDATE消息是用來延長SESSION有效時間。
Leader的工作流程簡圖如下所示，在實際實現(xiàn)中，流程要比下圖復(fù)雜得多，啟動了三個線程來實現(xiàn)功能。

2.3.2 Follower工作流程

Follower主要有四個功能：

1. 向Leader發(fā)送請求（PING消息、REQUEST消息、ACK消息、REVALIDATE消息）；
2 .接收Leader消息并進行處理；
3 .接收Client的請求，如果為寫請求，發(fā)送給Leader進行投票；
4 .返回Client結(jié)果。

Follower的消息循環(huán)處理如下幾種來自Leader的消息：

1 .PING消息：心跳消息；
2 .PROPOSAL消息：Leader發(fā)起的提案，要求Follower投票；
3 .COMMIT消息：服務(wù)器端最新一次提案的信息；
4 .UPTODATE消息：表明同步完成；
5 .REVALIDATE消息：根據(jù)Leader的REVALIDATE結(jié)果，關(guān)閉待revalidate的session還是允許其接受消息；
6 .SYNC消息：返回SYNC結(jié)果到客戶端，這個消息最初由客戶端發(fā)起，用來強制得到最新的更新。

Follower的工作流程簡圖如下所示，在實際實現(xiàn)中，F(xiàn)ollower是通過5個線程來實現(xiàn)功能的。

對于observer的流程不再敘述，observer流程和Follower的唯一不同的地方就是observer不會參加leader發(fā)起的投票。

posted @ 2013-06-22 23:03 鑫龍閱讀(502) | 評論 (0) | 編輯收藏

分布式服務(wù)框架 Zookeeper -- 管理分布式環(huán)境中的數(shù)據(jù)

摘要: 安裝和配置詳解本文介紹的 Zookeeper 是以 3.2.2 這個穩(wěn)定版本為基礎(chǔ)，最新的版本可以通過官網(wǎng) http://hadoop.apache.org/zookeeper/來獲取，Zookeeper 的安裝非常簡單，下面將從單機模式和集群模式兩個方面介紹 Zookeeper 的安裝和配置。單機模式單機安裝非常簡單，只要獲取到 Zookeeper 的壓縮包并解壓到某個目錄如：/hom... 閱讀全文

posted @ 2013-06-22 22:19 鑫龍閱讀(304) | 評論 (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很多人已經(jīng)知道了，但關(guān)于Chubyy似乎熟悉它的就非常有限，這倒是不奇怪，因為MapReduce是一個針對開發(fā)人員的ProgrammingModel，自然會有很多人去學(xué)習它，而Chubby更多的是一種為了實現(xiàn)MapReduce或者Bigtable而構(gòu)建的內(nèi)部的工具，對于開發(fā)人員來說基本上是透明的。文獻[1]我反復(fù)讀了至少有兩三天，但感覺也只是一個囫圇吞棗的結(jié)果，里面有很多工程實現(xiàn)上的細節(jié)，如果不是自己親自去設(shè)計或者實現(xiàn)，很難體會到其中的道理和奧妙。但是，對于這樣一個分布式service的研究，還是讓我對一個分布式系統(tǒng)的結(jié)構(gòu)和設(shè)計思想有了更加直觀的感覺。

從distributed consensus problem說起

distributed consensus problem(分布的一致性問題)是分布式算法中的一個經(jīng)典問題。它的問題描述大概是這樣的：在一個分布式系統(tǒng)中，有一組的Process，它們需要確定一個Value。于是每個Process都提出了一個Value，consensus就是指只有其中的一個Value能夠被選中作為最后確定的值，并且當這個值被選出來以后，所有的Process都需要被通知到。
表面上看，這個問題很容易解決。比如設(shè)置一個server，所有的process都向這個server提交一個Value，這個server可以通過一個簡單的規(guī)則來挑選出一個Value（例如最先到達的Value被選中），然后由這個server通知所有的Process。但是在分布式系統(tǒng)中，就會有各種的問題發(fā)生，例如，這個server崩潰了怎么辦，所以我們可能需要有幾臺server共同決定。還有，Process提交Value的時間都不一樣，網(wǎng)絡(luò)傳輸過程中由于延遲這些Value到達server的順序也都沒有保證。
為了解決這個問題，有很多人提出了各種各樣的Protocol，這些Protocol可以看做是一組需要遵循的規(guī)則，按照這些規(guī)則，這些Process就能夠選舉出一個唯一的Value。其中，最有名的一個Protocol就是Paxos算法。（八卦一下，Paxos的提出者叫做Lamport，有很多分布式的算法都是他提出的，他還是Latex的作者，大牛啊...）。想更加了解Paxos算法可以參考文獻[2]，很漂亮的一篇文章。

那么這些和Chubby有什么關(guān)系呢？其實Chubby就是為了這個問題而構(gòu)建出來的。只是它并不是一個Protocol或者是一個算法，而是google精心設(shè)計的一個service。這個service不僅能夠解決一致性問題，還有其它的一些很實用的好處，會在下文慢慢介紹。

一個實例

在Google File System(GFS)中，有很多的server，這些server需要選舉其中的一臺作為master server。這其實是一個很典型的consensus問題，Value就是master server的地址。GFS就是用Chubby來解決的這個問題，所有的server通過Chubby提供的通信協(xié)議到Chubby server上創(chuàng)建同一個文件，當然，最終只有一個server能夠獲準創(chuàng)建這個文件，這個server就成為了master，它會在這個文件中寫入自己的地址，這樣其它的server通過讀取這個文件就能知道被選出的master的地址。

Chubby是什么

從上面的這個實例可以看出，Chubby首先是一個分布式的文件系統(tǒng)。Chubby能夠提供機制使得client可以在Chubby service上創(chuàng)建文件和執(zhí)行一些文件的基本操作。說它是分布式的文件系統(tǒng)，是因為一個Chubby cell是一個分布式的系統(tǒng)，一般包含了5臺機器，整個文件系統(tǒng)是部署在這5臺機器上的。
但是，從更高一點的語義層面上，Chubby是一個lock service，一個針對松耦合的分布式系統(tǒng)的lock service。所謂lock service，就是這個service能夠提供開發(fā)人員經(jīng)常用的“鎖”，“解鎖”功能。通過Chubby，一個分布式系統(tǒng)中的上千個client都能夠對于某項資源進行“加鎖”，“解鎖”。
那么，Chubby是怎樣實現(xiàn)這樣的“鎖”功能的？就是通過文件。Chubby中的“鎖”就是文件，在上例中，創(chuàng)建文件其實就是進行“加鎖”操作，創(chuàng)建文件成功的那個server其實就是搶占到了“鎖”。用戶通過打開、關(guān)閉和讀取文件，獲取共享鎖或者獨占鎖；并且通過通信機制，向用戶發(fā)送更新信息。

綜上所述，Chubby是一個lock service，通過這個lock service可以解決分布式中的一致性問題，而這個lock service的實現(xiàn)是一個分布式的文件系統(tǒng)。

可能會有人問，為什么不是直接實現(xiàn)一個類似于Paxos算法這樣的Protocol來解決一致性問題，而是要通過一個lock service來解決？文獻[1]中提到，用lock service這種方式有幾個好處：
1.大部分開發(fā)人員在開始開發(fā)service的時候都不會考慮到這種一致性的問題，所以一開始都不會使用consensus protocol。只有當service慢慢成熟以后，才開始認真對待這個問題。采用lock service可以使得在保持原有的程序架構(gòu)和通信機制的情況下，通過添加簡單的語句就可以解決一致性問題；
2.正如上文實例中所展現(xiàn)，很多時候并不僅僅是選舉出一個master，還需要將這個master的地址告訴其它人或者保存某個信息，這種時候，使用Chubby中的文件，不僅僅是提供鎖功能，還能在文件中記錄下有用的信息（比如master的地址）。所以，很多的開發(fā)人員通過使用Chubby來保存metadata和configuration。
3. 一個基于鎖的開發(fā)接口更容易被開發(fā)人員所熟悉。并不是所有的開發(fā)人員都了解consensus protocol的，但大部分人應(yīng)該都用過鎖。
4. 一個consensus protocol一般來說需要使用到好幾臺副本來保證HA（詳見Paxos算法），而使用Chubby，就算只有一個client也能用。
可以看出，之所以用lock service這樣的形式，是因為Chubby不僅僅想解決一致性問題，還可以提供更多更有用的功能。事實上，Google有很多開發(fā)人員將Chubby當做name service使用，效果非常好。

關(guān)于lock service，還有兩個名詞需要提及。
一個是advisory lock。Chubby中的lock都是advisory lock。所謂的advisory lock，舉個例子，就是說當有人將某個文件鎖住以后，如果有其他的人想不解鎖而直接訪問這個文件，這種行為是不會被阻止的。和advisory lock對應(yīng)的是mandatory lock，即如果某個文件被鎖住以后，如果有其他的人直接訪問它，那么這種行為是會產(chǎn)生exception的。
另一個是coarse-grained（粗顆粒度的）。Chubby的lock service是coarse-grained，就是說Chubby中的lock一般鎖住的時間都比較長，可能是幾小時或者幾天。與之對應(yīng)的是fined-grained，這種lock一般只維持幾秒或者更少。這兩種鎖在實現(xiàn)的時候是會有很多不同的考慮的，比如coarse-grained的lock service的負載要小很多，因為加鎖解鎖并不會太頻繁。其它的差別詳見文獻[1]。

Chubby的架構(gòu)

上圖就是Chubby的系統(tǒng)架構(gòu)。

基本上分為了兩部分：服務(wù)器一端，稱為Chubby cell；client一端，每個Chubby的client都有一個Chubby library。這兩部分通過RPC進行通信。
client端通過Chubby library的接口調(diào)用，在Chubby cell上創(chuàng)建文件來獲得相應(yīng)的鎖的功能。
由于整個Chubby系統(tǒng)比較復(fù)雜，且細節(jié)很多，我個人又將整個系統(tǒng)分為了三個部分：
Chubby cell的一致性部分
分布式文件系統(tǒng)部分
client與Chubby cell的通信和連接部分

先從Chubby cell的一致性部分說起。
一般來說，一個Chubby cell由五臺server組成，可以支持一整個數(shù)據(jù)中心的上萬臺機器的lock service。
cell中的每臺server我們稱之為replicas（副本）。
當Chubby工作的時候，首先它需要從這些replicas中選舉出一個master。注意，這其實也是一個distributed consensus problem，也就是說Chubby也存在著分布式的一致性問題。Chubby是通過采用consensus protocol（很可能就是Paxos算法）來解決這個問題的。所以，Chubby的client用Chubby提供的lock service來解決一致性問題，而Chubby系統(tǒng)內(nèi)部的一致性問題則是用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的文件系統(tǒng)
前文說過，Chubby的底層實現(xiàn)其實就是一個分布式的文件系統(tǒng)。這個文件系統(tǒng)的接口是類似于Unix系統(tǒng)的。例如，對于文件名“/ls/foo /wombat/pouch”，ls表示的是“lock service”，foo表示的是某個Chubby cell的名字，wombat/pouch則是這個cell上的某個文件目錄或者文件名。如果一個client端使用Chubby library來創(chuàng)建這樣一個文件名，那么這樣一個文件就會在Chubby cell上被創(chuàng)建。
Chubby的文件系統(tǒng)由于它的特殊用途做了很多的簡化。例如它不支持文件的轉(zhuǎn)移，不記錄文件最后訪問時間等等。整個文件系統(tǒng)只包含有文件和目錄，統(tǒng)一稱為“Node”。文件系統(tǒng)采用Berkeley DB來保存Node的信息，主要是一種map的關(guān)系。Key就是Node的名字，Value就是Node的內(nèi)容。
還有一點需要提及的是，Chubby cell和client之間用了event形式的通知機制。client在創(chuàng)建了文件之后會得到一個handle，并且還可以訂閱一系列的event，例如文件內(nèi)容修改的event。這樣的話，一旦client相關(guān)的文件內(nèi)容被修改了，那么cell會通過機制發(fā)送一個event來告訴client該文件被修改了。

最后談?wù)刢lient與cell的交互部分
這里大致包含兩部分的內(nèi)容：cache的同步機制和KeepAlive握手協(xié)議。
為了降低client和cell之間通信的壓力和頻率，client在本地會保存一個和自己相關(guān)的Chubby文件的cache。例如如果client通過Chubby library在cell上創(chuàng)建了一個文件，那么在client本地，也會有一個相同的文件在cache中創(chuàng)建，這個cache中的文件的內(nèi)容和cell上文件的內(nèi)容是一樣的。這樣的話，client如果想訪問這個文件，就可以直接訪問本地的cache而不通過網(wǎng)絡(luò)去訪問cell。
cache有兩個狀態(tài)，有效和無效。當有一個client要改變某個File的時候，整個修改會被master block，然后master會發(fā)送無效標志給所有cache了這個數(shù)據(jù)的client（它維護了這么一個表），當其它client端收到這個無效標志后，就會將cache中的狀態(tài)置為無效，然后返回一個acknowledge；當master確定收到了所有的acknowledge之后，才完成整個modification。
需要注意的是，master并不是發(fā)送update給client而是發(fā)送無效標志給client。這是因為如果發(fā)送update給client，那么每一次數(shù)據(jù)的修改都需要發(fā)送一大堆的update，而發(fā)送無效標示的話，對一個數(shù)據(jù)的很多次修改只需要發(fā)送一個無效標示，這樣大大降低了通信量。

至于KeepAlive協(xié)議，則是為了保證client和master隨時都保持著聯(lián)系。client和master每隔一段時間就會KeepAlive一次，這樣的話，如果master意外停機，client可以很快的知道這個消息，然后迅速的轉(zhuǎn)移到新的master上。并且，這種轉(zhuǎn)移對于client端的application是透明的，也就是說application并不會知道m(xù)aster發(fā)生了錯誤。關(guān)于cache和KeepAlive還有很多的細節(jié)，想了解的讀文獻[1]吧。

總結(jié)

其實在我的這篇文章中，還有一個很大的主題沒有提及，那就是Chubby的容錯機制。基本上，容錯這個思想貫穿了文獻[1]的始終，也正是因此，我很難將它單獨提取出來解釋，因為它散落在了Chubby系統(tǒng)設(shè)計的所有角落。我個人感覺，容錯是一個分布式系統(tǒng)設(shè)計的核心思想，在設(shè)計的時候要求考慮到所有可能會發(fā)生的錯誤，不僅僅包括了硬件的錯誤，網(wǎng)絡(luò)的故障，還包括了開發(fā)人員可能出現(xiàn)的錯誤。我想，這是我讀這篇文章[1]最大的收獲。

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

posted @ 2013-06-22 12:18 鑫龍閱讀(403) | 評論 (0) | 編輯收藏

程序員技術(shù)練級攻略

月光博客6月12日發(fā)表了《寫給新手程序員的一封信》，翻譯自《An open letter to those who want to start programming》，我的朋友（他在本站的id是Mailper）告訴我，他希望在酷殼上看到一篇更具操作性的文章。因為他也是喜歡編程和技術(shù)的家伙，于是，我讓他把他的一些學(xué)習Python和Web編程的一些點滴總結(jié)一下。于是他給我發(fā)來了一些他的心得和經(jīng)歷，我在把他的心得做了不多的增改，并根據(jù)我的經(jīng)歷增加了“進階”一節(jié)。這是一篇由新手和我這個老家伙根據(jù)我們的經(jīng)歷完成的文章。

我的這個朋友把這篇文章取名叫Build Your Programming Technical Skills，我實在不知道用中文怎么翻譯，但我在寫的過程中，我覺得這很像一個打網(wǎng)游做任務(wù)升級的一個過程，所以取名叫“技術(shù)練級攻略”，題目有點大，呵呵，這個標題純粹是為了好玩。這里僅僅是在分享Mailper和我個人的學(xué)習經(jīng)歷。（注：省去了我作為一個初學(xué)者曾經(jīng)學(xué)習過的一些技術(shù)(今天明顯過時了)，如：Delphi/Power builder，也省去了我學(xué)過的一些我覺得沒意思的技術(shù)Lotus Notes/ActiveX/COM/ADO/ATL/.NET ……）

前言

你是否覺得自己從學(xué)校畢業(yè)的時候只做過小玩具一樣的程序？走入職場后哪怕沒有什么經(jīng)驗也可以把以下這些課外練習走一遍（朋友的抱怨：學(xué)校課程總是從理論出發(fā)，作業(yè)項目都看不出有什么實際作用，不如從工作中的需求出發(fā)）

建議：

不要亂買書，不要亂追新技術(shù)新名詞，基礎(chǔ)的東西經(jīng)過很長時間積累而且還會在未來至少10年通用。
回顧一下歷史，看看歷史上時間線上技術(shù)的發(fā)展，你才能明白明天會是什么樣。
一定要動手，例子不管多么簡單，建議至少自己手敲一遍看看是否理解了里頭的細枝末節(jié)。
一定要學(xué)會思考，思考為什么要這樣，而不是那樣。還要舉一反三地思考。

注：你也許會很奇怪為什么下面的東西很偏Unix/Linux，這是因為我覺得Windows下的編程可能會在未來很沒有前途，原因如下：

現(xiàn)在的用戶界面幾乎被兩個東西主宰了，1）Web，2）移動設(shè)備iOS或Android。Windows的圖形界面不吃香了。
越來越多的企業(yè)在用成本低性能高的Linux和各種開源技術(shù)來構(gòu)架其系統(tǒng)，Windows的成本太高了。
微軟的東西變得太快了，很不持久，他們完全是在玩弄程序員。詳情參見《Windows編程革命史》

所以，我個人認為以后的趨勢是前端是Web+移動，后端是Linux+開源。開發(fā)這邊基本上沒Windows什么事。

啟蒙入門

1、學(xué)習一門腳本語言，例如Python/Ruby

可以讓你擺脫對底層語言的恐懼感，腳本語言可以讓你很快開發(fā)出能用得上的小程序。實踐項目:

處理文本文件，或者csv (關(guān)鍵詞 python csv, python open, python sys) 讀一個本地文件，逐行處理（例如 word count，或者處理log）
遍歷本地文件系統(tǒng) (sys, os, path)，例如寫一個程序統(tǒng)計一個目錄下所有文件大小并按各種條件排序并保存結(jié)果
跟數(shù)據(jù)庫打交道 (python sqlite)，寫一個小腳本統(tǒng)計數(shù)據(jù)庫里條目數(shù)量
學(xué)會用各種print之類簡單粗暴的方式進行調(diào)試
學(xué)會用Google (phrase, domain, use reader to follow tech blogs)

為什么要學(xué)腳本語言，因為他們實在是太方便了，很多時候我們需要寫點小工具或是腳本來幫我們解決問題，你就會發(fā)現(xiàn)正規(guī)的編程語言太難用了。

2、用熟一種程序員的編輯器(不是IDE) 和一些基本工具

Vim / Emacs / Notepad++，學(xué)會如何配置代碼補全，外觀，外部命令等。
Source Insight (或 ctag)

使用這些東西不是為了Cool，而是這些編輯器在查看、修改代碼/配置文章/日志會更快更有效率。

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

如果你用windows，至少學(xué)會用虛擬機里的linux， vmware player是免費的，裝個Ubuntu吧
一定要少用少用圖形界面。
學(xué)會使用man來查看幫助
文件系統(tǒng)結(jié)構(gòu)和基本操作 ls/chmod/chown/rm/find/ln/cat/mount/mkdir/tar/gzip …
學(xué)會使用一些文本操作命令 sed/awk/grep/tail/less/more …
學(xué)會使用一些管理命令 ps/top/lsof/netstat/kill/tcpdump/iptables/dd…
了解/etc目錄下的各種配置文章，學(xué)會查看/var/log下的系統(tǒng)日志，以及/proc下的系統(tǒng)運行信息
了解正則表達式，使用正則表達式來查找文件。

對于程序員來說Unix/Linux比Windows簡單多了。（參看我四年前CSDN的博文《其實Unix很簡單》）學(xué)會使用Unix/Linux你會發(fā)現(xiàn)圖形界面在某些時候?qū)嵲谑翘y用了，相當?shù)叵喈數(shù)亟档凸ぷ餍省?/p>

4、學(xué)習Web基礎(chǔ)（HTML/CSS/JS) + 服務(wù)器端技術(shù) (LAMP)

未來必然是Web的世界，學(xué)習WEB基礎(chǔ)的最佳網(wǎng)站是W3School。

學(xué)習HTML基本語法
學(xué)習CSS如何選中HTML元素并應(yīng)用一些基本樣式（關(guān)鍵詞：box model）
學(xué)會用 Firefox + Firebug 或 chrome 查看你覺得很炫的網(wǎng)頁結(jié)構(gòu)，并動態(tài)修改。
學(xué)習使用Javascript操縱HTML元件。理解DOM和動態(tài)網(wǎng)頁（http://oreilly.com/catalog/9780596527402) 網(wǎng)上有免費的章節(jié)，足夠用了。或參看 DOM 。
學(xué)會用 Firefox + Firebug 或 chrome 調(diào)試Javascript代碼（設(shè)置斷點，查看變量，性能，控制臺等）
在一臺機器上配置Apache 或 Nginx
學(xué)習PHP，讓后臺PHP和前臺HTML進行數(shù)據(jù)交互，對服務(wù)器相應(yīng)瀏覽器請求形成初步認識。實現(xiàn)一個表單提交和反顯的功能。
把PHP連接本地或者遠程數(shù)據(jù)庫 MySQL（MySQL 和 SQL現(xiàn)學(xué)現(xiàn)用夠了）
跟完一個名校的網(wǎng)絡(luò)編程課程（例如：http://www.stanford.edu/~ouster/cgi-bin/cs142-fall10/index.php ) 不要覺得需要多于一學(xué)期時間，大學(xué)生是全職一學(xué)期選3-5門課，你業(yè)余時間一定可以跟上
學(xué)習一個javascript庫（例如jQuery 或 ExtJS）+ Ajax (異步讀入一個服務(wù)器端圖片或者數(shù)據(jù)庫內(nèi)容）+JSON數(shù)據(jù)格式。
HTTP: The Definitive Guide 讀完前4章你就明白你每天上網(wǎng)用瀏覽器的時候發(fā)生的事情了(proxy, gateway, browsers)
做個小網(wǎng)站（例如：一個小的留言板，支持用戶登錄，Cookie/Session，增、刪、改、查，上傳圖片附件，分頁顯示）
買個域名，租個空間，做個自己的網(wǎng)站。

進階加深

1、 C語言和操作系統(tǒng)調(diào)用

重新學(xué)C語言，理解指針和內(nèi)存模型，用C語言實現(xiàn)一下各種經(jīng)典的算法和數(shù)據(jù)結(jié)構(gòu)。推薦《計算機程序設(shè)計藝術(shù)》、《算法導(dǎo)論》和《編程珠璣》。
學(xué)習（麻省理工免費課程）計算機科學(xué)和編程導(dǎo)論
學(xué)習（麻省理工免費課程）C語言內(nèi)存管理
學(xué)習Unix/Linux系統(tǒng)調(diào)用（Unix高級環(huán)境編程），，了解系統(tǒng)層面的東西。

用這些系統(tǒng)知識操作一下文件系統(tǒng)，用戶（實現(xiàn)一個可以拷貝目錄樹的小程序）
用fork/wait/waitpid寫一個多進程的程序，用pthread寫一個多線程帶同步或互斥的程序。多進程多進程購票的程序。
用signal/kill/raise/alarm/pause/sigprocmask實現(xiàn)一個多進程間的信號量通信的程序。
學(xué)會使用gcc和gdb來編程和調(diào)試程序（參看我的《用gdb調(diào)試程序》）
學(xué)會使用makefile來編譯程序。（參看我的《跟我一起寫makefile》）
IPC和Socket的東西可以放到高級中來實踐。

學(xué)習Windows SDK編程（Windows 程序設(shè)計，MFC程序設(shè)計）

寫一個窗口，了解WinMain/WinProcedure，以及Windows的消息機制。
寫一些程序來操作Windows SDK中的資源文件或是各種圖形控件，以及作圖的編程。
學(xué)習如何使用MSDN查看相關(guān)的SDK函數(shù)，各種WM_消息以及一些例程。
這本書中有很多例程，在實踐中請不要照抄，試著自己寫一個自己的例程。
不用太多于精通這些東西，因為GUI正在被Web取代，主要是了解一下Windows 圖形界面的編程。@virushuo 說：“ 我覺得GUI確實不那么熱門了，但充分理解GUI工作原理是很重要的。包括移動設(shè)備開發(fā)，如果沒有基礎(chǔ)知識仍然很吃力。或者說移動設(shè)備開發(fā)必須理解GUI工作，或者在win那邊學(xué)，或者在mac/iOS上學(xué)”。

2、學(xué)習Java

Java 的學(xué)習主要是看經(jīng)典的Core Java 《Java 核心技術(shù)編程》和《Java編程思想》（有兩卷，我僅鏈了第一卷，足夠了，因為Java的圖形界面了解就可以了）
學(xué)習JDK，學(xué)會查閱Java API Doc http://download.oracle.com/javase/6/docs/api/
了解一下Java這種虛擬機語言和C和Python語言在編譯和執(zhí)行上的差別。從C、Java、Python思考一下“跨平臺”這種技術(shù)。
學(xué)會使用IDE Eclipse，使用Eclipse 編譯，調(diào)試和開發(fā)Java程序。
建一個Tomcat的網(wǎng)站，嘗試一下JSP/Servlet/JDBC/MySQL的Web開發(fā)。把前面所說的那個PHP的小項目試著用JSP和Servlet實現(xiàn)一下。

3、Web的安全與架構(gòu)

學(xué)習HTML5，網(wǎng)上有很多很多教程，以前酷殼也介紹過很多，我在這里就不羅列了。
學(xué)習Web開發(fā)的安全問題（參考新浪微博被攻擊的這個事，以及Ruby的這篇文章）
學(xué)習HTTP Server的rewrite機制，Nginx的反向代理機制，fast-cgi（如：PHP-FPM）
學(xué)習Web的靜態(tài)頁面緩存技術(shù)。
學(xué)習Web的異步工作流處理，數(shù)據(jù)Cache，數(shù)據(jù)分區(qū)，負載均衡，水平擴展的構(gòu)架。
實踐任務(wù)：

使用HTML5的canvas 制作一些Web動畫。
嘗試在前面開發(fā)過的那個Web應(yīng)用中進行SQL注入，JS注入，以及XSS攻擊。
把前面開發(fā)過的那個Web應(yīng)用改成構(gòu)造在Nginx + PHP-FPM + 靜態(tài)頁面緩存的網(wǎng)站

4、學(xué)習關(guān)系型數(shù)據(jù)庫

你可以安裝MSSQLServer或MySQL來學(xué)習數(shù)據(jù)庫。
學(xué)習教科書里數(shù)據(jù)庫設(shè)計的那幾個范式，1NF，2NF，3NF，……
學(xué)習數(shù)據(jù)庫的存過，觸發(fā)器，視圖，建索引，游標等。
學(xué)習SQL語句，明白表連接的各種概念（參看《SQL Join的圖示》）
學(xué)習如何優(yōu)化數(shù)據(jù)庫查詢（參看《MySQL的優(yōu)化》）
實踐任務(wù)：設(shè)計一個論壇的數(shù)據(jù)庫，至少滿足3NF，使用SQL語句查詢本周，本月的最新文章，評論最多的文章，最活躍用戶。

5、一些開發(fā)工具

學(xué)會使用SVN或Git來管理程序版本。
學(xué)會使用JUnit來對Java進行單元測試。
學(xué)習C語言和Java語言的coding standard 或 coding guideline。（我N年前寫過一篇關(guān)C語言非常簡單的文章——《編程修養(yǎng)》，這樣的東西你可以上網(wǎng)查一下，一大堆）。
推薦閱讀《代碼大全》《重構(gòu)》《代碼整潔之道》

高級深入

1、C++ / Java 和面向?qū)ο?/strong>

我個人以為學(xué)好C++，Java也就是舉手之勞。但是C++的學(xué)習曲線相當?shù)亩浮２贿^，我覺得C++是最需要學(xué)好的語言了。參看兩篇趣文“C++學(xué)習信心圖” 和“21天學(xué)好C++”

學(xué)習（麻省理工免費課程）C++面向?qū)ο缶幊?/a>
讀我的 “如何學(xué)好C++”中所推薦的那些書至少兩遍以上（如果你對C++的理解能夠深入到像我所寫的《C++虛函數(shù)表解析》或是《C++對象內(nèi)存存局（上）（下）》，或是《C/C++返回內(nèi)部靜態(tài)成員的陷阱》那就非常不錯了）
然后反思為什么C++要干成這樣，Java則不是？你一定要學(xué)會對比C++和Java的不同。比如，Java中的初始化，垃圾回收，接口，異常，虛函數(shù)，等等。
實踐任務(wù)：

用C++實現(xiàn)一個BigInt，支持128位的整形的加減乘除的操作。
用C++封裝一個數(shù)據(jù)結(jié)構(gòu)的容量，比如hash table。
用C++封裝并實現(xiàn)一個智能指針（一定要使用模板）。

《設(shè)計模式》必需一讀，兩遍以上，思考一下，這23個模式的應(yīng)用場景。主要是兩點：1）鐘愛組合而不是繼承，2）鐘愛接口而不是實現(xiàn)。（也推薦《深入淺出設(shè)計模式》）
實踐任務(wù)：

使用工廠模式實現(xiàn)一個內(nèi)存池。
使用策略模式制做一個類其可以把文本文件進行左對齊，右對齊和中對齊。
使用命令模式實現(xiàn)一個命令行計算器，并支持undo和redo。
使用修飾模式實現(xiàn)一個酒店的房間價格訂價策略——旺季，服務(wù)，VIP、旅行團、等影響價格的因素。

學(xué)習STL的用法和其設(shè)計概念 - 容器，算法，迭代器，函數(shù)子。如果可能，請讀一下其源碼。
實踐任務(wù)：嘗試使用面向?qū)ο蟆TL，設(shè)計模式、和WindowsSDK圖形編程的各種技能

做一個貪吃蛇或是俄羅斯方塊的游戲。支持不同的級別和難度。
做一個文件瀏覽器，可以瀏覽目錄下的文件，并可以對不同的文件有不同的操作，文本文件可以打開編輯，執(zhí)行文件則執(zhí)行之，mp3或avi文件可以播放，圖片文件可以展示圖片。

學(xué)習C++的一些類庫的設(shè)計，如： MFC（看看候捷老師的《深入淺出MFC》），Boost, ACE, CPPUnit，STL （STL可能會太難了，但是如果你能了解其中的設(shè)計模式和設(shè)計那就太好了，如果你能深入到我寫的《STL string類的寫時拷貝技術(shù)》那就非常不錯了，ACE需要很強在的系統(tǒng)知識，參見后面的“加強對系統(tǒng)的了解”）
Java是真正的面向?qū)ο蟮恼Z言，Java的設(shè)計模式多得不能再多，也是用來學(xué)習面向?qū)ο蟮脑O(shè)計模式的最佳語言了（參看Java中的設(shè)計模式）。
推薦閱讀《Effective Java》 and 《Java解惑》
學(xué)習Java的框架，Java的框架也是多，如Spring, Hibernate，Struts 等等，主要是學(xué)習Java的設(shè)計，如IoC等。
Java的技術(shù)也是爛多，重點學(xué)習J2EE架構(gòu)以及JMS， RMI, 等消息傳遞和遠程調(diào)用的技術(shù)。
學(xué)習使用Java做Web Service （官方教程在這里）
實踐任務(wù)： 嘗試在Spring或Hibernate框架下構(gòu)建一個有網(wǎng)絡(luò)的Web Service的遠程調(diào)用程序，并可以在兩個Service中通過JMS傳遞消息。

C++和Java都不是能在短時間內(nèi)能學(xué)好的，C++玩是的深，Java玩的是廣，我建議兩者選一個。我個人的學(xué)習經(jīng)歷是：

深究C++（我深究C/C++了十來年了）
學(xué)習Java的各種設(shè)計模式。

2、加強系統(tǒng)了解

重要閱讀下面的幾本書：

《Unix編程藝術(shù)》了解Unix系統(tǒng)領(lǐng)域中的設(shè)計和開發(fā)哲學(xué)、思想文化體系、原則與經(jīng)驗。你一定會有一種醍醐灌頂?shù)母杏X。
《Unix網(wǎng)絡(luò)編程卷1，套接字》這是一本看完你就明白網(wǎng)絡(luò)編程的書。重要注意TCP、UDP，以及多路復(fù)用的系統(tǒng)調(diào)用select/poll/epoll的差別。
《TCP/IP詳解卷1:協(xié)議》- 這是一本看完后你就可以當網(wǎng)絡(luò)黑客的書。了解以太網(wǎng)的的運作原理，了解TCP/IP的協(xié)議，運作原理以及如何TCP的調(diào)優(yōu)。
實踐任務(wù)：

理解什么是阻塞（同步IO），非阻塞（異步IO），多路復(fù)用（select, poll, epoll）的IO技術(shù)。
寫一個網(wǎng)絡(luò)聊天程序，有聊天服務(wù)器和多個聊天客戶端（服務(wù)端用UDP對部分或所有的的聊天客戶端進Multicast或Broadcast）。
寫一個簡易的HTTP服務(wù)器。

《Unix網(wǎng)絡(luò)編程卷2，進程間通信》信號量，管道，共享內(nèi)存，消息等各種IPC…… 這些技術(shù)好像有點老掉牙了，不過還是值得了解。
實踐任務(wù)：

主要實踐各種IPC進程序通信的方法。
嘗試寫一個管道程序，父子進程通過管道交換數(shù)據(jù)。
嘗試寫一個共享內(nèi)存的程序，兩個進程通過共享內(nèi)存交換一個C的結(jié)構(gòu)體數(shù)組。

學(xué)習《Windows核心編程》一書。把CreateProcess，Windows線程、線程調(diào)度、線程同步（Event, 信號量，互斥量）、異步I/O，內(nèi)存管理，DLL，這幾大塊搞精通。
實踐任務(wù)：使用CreateProcess啟動一個記事本或IE，并監(jiān)控該程序的運行。把前面寫過的那個簡易的HTTP服務(wù)用線程池實現(xiàn)一下。寫一個DLL的鉤子程序監(jiān)控指定窗口的關(guān)閉事件，或是記錄某個窗口的按鍵。
有了多線程、多進程通信，TCP/IP，套接字，C++和設(shè)計模式的基本，你可以研究一下ACE了。使用ACE重寫上述的聊天程序和HTTP服務(wù)器（帶線程池）
實踐任務(wù)：通過以上的所有知識，嘗試

寫一個服務(wù)端給客戶端傳大文件，要求把100M的帶寬用到80%以上。（注意，磁盤I/O和網(wǎng)絡(luò)I/O可能會很有問題，想一想怎么解決，另外，請注意網(wǎng)絡(luò)傳輸最大單元MTU）
了解BT下載的工作原理，用多進程的方式模擬BT下載的原理。

3、系統(tǒng)架構(gòu)

負載均衡。HASH式的，純動態(tài)式的。（可以到Google學(xué)術(shù)里搜一些關(guān)于負載均衡的文章讀讀）
多層分布式系統(tǒng) – 客戶端服務(wù)結(jié)點層、計算結(jié)點層、數(shù)據(jù)cache層，數(shù)據(jù)層。J2EE是經(jīng)典的多層結(jié)構(gòu)。
CDN系統(tǒng) – 就近訪問，內(nèi)容邊緣化。
P2P式系統(tǒng)，研究一下BT和電驢的算法。比如：DHT算法。
服務(wù)器備份，雙機備份系統(tǒng)（Live-Standby和Live-Live系統(tǒng)），兩臺機器如何通過心跳監(jiān)測對方？集群主結(jié)點備份。
虛擬化技術(shù)，使用這個技術(shù)，可以把操作系統(tǒng)當應(yīng)用程序一下切換或重新配置和部署。
學(xué)習Thrift，二進制的高性能的通訊中間件，支持數(shù)據(jù)(對象)序列化和多種類型的RPC服務(wù)。
學(xué)習Hadoop。Hadoop框架中最核心的設(shè)計就是：MapReduce和HDFS。MapReduce的思想是由Google的一篇論文所提及而被廣為流傳的，簡單的一句話解釋MapReduce就是“任務(wù)的分解與結(jié)果的匯總”。HDFS是Hadoop分布式文件系統(tǒng)（Hadoop Distributed File System）的縮寫，為分布式計算存儲提供了底層支持。
了解NoSQL數(shù)據(jù)庫（有人說可能是一個過渡炒作的技術(shù)），不過因為超大規(guī)模以及高并發(fā)的純動態(tài)型網(wǎng)站日漸成為主流，而SNS類網(wǎng)站在數(shù)據(jù)存取過程中有著實時性等剛性需求，這使得目前NoSQL數(shù)據(jù)庫慢慢成了人們所關(guān)注的焦點，并大有成為取代關(guān)系型數(shù)據(jù)庫而成為未來主流數(shù)據(jù)存儲模式的趨勢。當前NoSQL數(shù)據(jù)庫很多，大部分都是開源的，其中比較知名的有：MemcacheDB、Redis、Tokyo Cabinet(升級版為Kyoto Cabinet)、Flare、MongoDB、CouchDB、Cassandra、Voldemort等。

寫了那么多，回顧一下，覺得自己相當?shù)挠谐删透小ＯＭ蠹也灰獓樦易约哼@十來年也在不斷地學(xué)習，今天我也在學(xué)習中，人生本來就是一個不斷學(xué)習和練級的過程。不過，一定有漏的，也有不對的，還希望大家補充和更正。（我會根據(jù)大家的反饋隨時更新此文）歡迎大家通過我的微博（@左耳朵耗子）和twitter（@haoel）和我交流。

—– 更新 2011/07/19 —–

1）有朋友奇怪為什么我在這篇文章開頭說了web+移動，卻沒有在后面提到iOS/Android的前端開發(fā)。因為我心里有一種感覺，移動設(shè)備上的UI最終也會被Javascript取代。大家可以用iPhone或Android看看google+，你就會明白了。

2）有朋友說我這里的東西太多了，不能為了學(xué)習而學(xué)習，我非常同意。我在文章的前面也說了要思考。另外，千萬不要以為我說的這些東西是一些新的技術(shù)，這份攻略里95%以上的全是基礎(chǔ)。而且都是久經(jīng)考驗的基礎(chǔ)技術(shù)。即是可以讓你一通百通的技術(shù)，也是可以讓你找到一份不錯工作的技術(shù)。

3）有朋友說學(xué)這些東西學(xué)完都40了，還不如想想怎么去掙錢。我想告訴大家，一是我今年還沒有40歲，二是學(xué)無止境啊，三是我不覺得掙錢有多難，難的是怎么讓你值那么多錢？無論是打工還是創(chuàng)業(yè)，是什么東西讓你自己的價值，讓你公司的價值更值錢？別的地方我不敢說，對于互聯(lián)網(wǎng)或IT公司來說，技術(shù)實力絕對是其中之一。

4）有朋友說技術(shù)都是工具，不應(yīng)該如此癡迷這句話沒有錯，有時候我們需要更多的是抬起頭來看看技術(shù)以外的事情，或者是說我們在作技術(shù)的時候不去思考為什么會有這個技術(shù)，為什么不是別的，問題不在于技術(shù)，問題在于我們死讀書，讀死書，成了技術(shù)的書呆子。

5）對于NoSQL，最近比較火，但我對其有點保守，所以，我只是說了解就可以。對于Hadoop，我覺得其在分布式系統(tǒng)上有巨大的潛力，所以需要學(xué)習。對于關(guān)系型數(shù)據(jù)庫，的確是很重要的東西，這點是我的疏忽，在原文里補充。

（全文完，轉(zhuǎn)載時請注明作者和出處）

（轉(zhuǎn)載本站文章請注明作者和出處酷殼 – CoolShell.cn ，請勿用于任何商業(yè)用途）

posted @ 2013-06-20 22:59 鑫龍閱讀(398) | 評論 (0) | 編輯收藏

m進制轉(zhuǎn)換為n進制-任意進制轉(zhuǎn)換算法

轉(zhuǎn)自:http://www.cnblogs.com/pkuoliver/archive/2010/10/27/Convert-m-number-to-n-number.html

園子里有很多深藏不漏的高手，在這里聊這種基本問題是有點小兒科。不過本人只是想分享下自己的新的，代碼，算法有不足之處，還請大家指正，共同進步。

這種題也是一道經(jīng)典的面試題，主要考察進制轉(zhuǎn)換細想，Coding質(zhì)量等。

當我們把十進制轉(zhuǎn)成二進制的時候，我們通過輾轉(zhuǎn)相除，取余，逆置余數(shù)序列的過程得到新的進制的數(shù)。因此我們可以借助這種思想把M進制轉(zhuǎn)成N進制的數(shù)。

如下是C的詳細的實現(xiàn)方法

?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

void m2n(int m, char* mNum, int n, char* nNum)

{

    int i = 0;

    char c, *p = nNum;



    //這是一個考察地方，是否能用最少乘法次數(shù)。

    while (*mNum != '\0')

        i = i*m + *mNum++ - '0';



    //輾轉(zhuǎn)取余

    while (i) {

        *p++ = i % n + '0';

        i /= n;

    }

    *p-- = '\0';



    //逆置余數(shù)序列

    while (p > nNum) {

        c = *p;

        *p-- = *nNum;

        *nNum++ = c;

    }

}

觀察上面的代碼，存在著眾多的不足。例如，要對輸入?yún)?shù)做檢查，數(shù)值的大小收到int值最大值的限制等。不過好在一點，該算法的時間復(fù)雜度是O(n)的。

我們霹靂無敵的趙大叔又提供了一種用Java實現(xiàn)的通用的進制轉(zhuǎn)換方法，即使Windows的計算器也轉(zhuǎn)不了的大數(shù)，這個算法也可以轉(zhuǎn)。算和上面的算法相比，他的基本思想不變，還是輾轉(zhuǎn)除，但是用了字符串做大數(shù)相除，很不錯的創(chuàng)新點，贊一個。代碼如下：

?

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

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

package test;



/**

* 功能：將一個數(shù)從M進制轉(zhuǎn)換成N進制

* MValue：M進制數(shù)的字符串表示方法

* Shang：保存中間運算結(jié)果

* 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;

    }

}

趙大叔的算法好了不少，除了參數(shù)檢查，大小寫之外都很好。值得我們借鑒。

posted @ 2013-06-08 16:16 鑫龍閱讀(914) | 評論 (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之上，提供高可靠性、高性能、列存儲、可伸縮、實時讀寫的數(shù)據(jù)庫系統(tǒng)。
它介于nosql和RDBMS之間，僅能通過主鍵(row key)和主鍵的range來檢索數(shù)據(jù)，僅支持單行事務(wù)(可通過hive支持來實現(xiàn)多表join等復(fù)雜操作)。主要用來存儲非結(jié)構(gòu)化和半結(jié)構(gòu)化的松散數(shù)據(jù)。
與hadoop一樣，Hbase目標主要依靠橫向擴展，通過不斷增加廉價的商用服務(wù)器，來增加計算和存儲能力。

HBase中的表一般有這樣的特點：
1 大：一個表可以有上億行，上百萬列
2 面向列:面向列(族)的存儲和權(quán)限控制，列(族)獨立檢索。
3 稀疏:對于為空(null)的列，并不占用存儲空間，因此，表可以設(shè)計的非常稀疏。

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

二、 邏輯視圖

HBase以表的形式存儲數(shù)據(jù)。表有行和列組成。列劃分為若干個列族(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數(shù)據(jù)庫們一樣,row key是用來檢索記錄的主鍵。訪問hbase table中的行，只有三種方式：
1 通過單個row key訪問
2 通過row key的range
3 全表掃描
Row key行鍵 (Row key)可以是任意字符串(最大長度是 64KB，實際應(yīng)用中長度一般為 10-100bytes)，在hbase內(nèi)部，row key保存為字節(jié)數(shù)組。
存儲時，數(shù)據(jù)按照Row key的字典序(byte order)排序存儲。設(shè)計key時，要充分排序存儲這個特性，將經(jīng)常一起讀取的行存儲放到一起。(位置相關(guān)性)
注意：
字典序?qū)nt排序的結(jié)果是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作左填充。
行的一次讀寫是原子操作 (不論一次讀寫多少列)。這個設(shè)計決策能夠使用戶很容易的理解程序在對同一個行進行并發(fā)更新操作時的行為。

列族
hbase表中的每個列，都歸屬與某個列族。列族是表的chema的一部分(而列不是)，必須在使用表之前定義。列名都以列族作為前綴。例如courses:history ， courses:math 都屬于 courses 這個列族。
訪問控制、磁盤和內(nèi)存的使用統(tǒng)計都是在列族層面進行的。實際應(yīng)用中，列族上的控制權(quán)限能幫助我們管理不同類型的應(yīng)用：我們允許一些應(yīng)用可以添加新的基本數(shù)據(jù)、一些應(yīng)用可以讀取基本數(shù)據(jù)并創(chuàng)建繼承的列族、一些應(yīng)用則只允許瀏覽數(shù)據(jù)（甚至可能因為隱私的原因不能瀏覽所有數(shù)據(jù)）。

時間戳
HBase中通過row和columns確定的為一個存貯單元稱為cell。每個 cell都保存著同一份數(shù)據(jù)的多個版本。版本通過時間戳來索引。時間戳的類型是 64位整型。時間戳可以由hbase(在數(shù)據(jù)寫入時自動 )賦值，此時時間戳是精確到毫秒的當前系統(tǒng)時間。時間戳也可以由客戶顯式賦值。如果應(yīng)用程序要避免數(shù)據(jù)版本沖突，就必須自己生成具有唯一性的時間戳。每個 cell中，不同版本的數(shù)據(jù)按照時間倒序排序，即最新的數(shù)據(jù)排在最前面。
為了避免數(shù)據(jù)存在過多版本造成的的管理 (包括存貯和索引)負擔，hbase提供了兩種數(shù)據(jù)版本回收方式。一是保存數(shù)據(jù)的最后n個版本，二是保存最近一段時間內(nèi)的版本（比如最近七天）。用戶可以針對每個列族進行設(shè)置。

Cell
由{row key, column( =<family> + <label>), version} 唯一確定的單元。cell中的數(shù)據(jù)是沒有類型的，全部是字節(jié)碼形式存貯。

三、 物理存儲
1 已經(jīng)提到過，Table中的所有行都按照row key的字典序排列。
2 Table 在行的方向上分割為多個Hregion。

3 region按大小分割的，每個表一開始只有一個region，隨著數(shù)據(jù)不斷插入表，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 段–保存表中的數(shù)據(jù)，這部分可以被壓縮
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會被讀取到內(nèi)存中，這樣，當檢索某個key時，不需要掃描整個HFile，而只需從內(nèi)存中找到key所在的block，通過一次磁盤io將整個 block讀取到內(nèi)存中，再找到需要的key。DataBlock Index采用LRU機制淘汰。
HFile的Data Block，Meta Block通常采用壓縮方式存儲，壓縮之后可以大大減少網(wǎng)絡(luò)IO和磁盤IO，隨之而來的開銷當然是需要花費cpu進行壓縮和解壓縮。
目標Hfile的壓縮支持兩種方式：Gzip，Lzo。

HLog(WAL log)
WAL 意為Write ahead log(http://en.wikipedia.org/wiki/Write-ahead_logging)，類似mysql中的binlog,用來做災(zāi)難恢復(fù)只用，Hlog記錄數(shù)據(jù)的所有變更,一旦數(shù)據(jù)修改，就可以從log中進行恢復(fù)。
每個Region Server維護一個Hlog,而不是每個Region一個。這樣不同region(來自不同table)的日志會混在一起，這樣做的目的是不斷追加單個文件相對于同時寫多個文件而言，可以減少磁盤尋址次數(shù)，因此可以提高對table的寫性能。帶來的麻煩是，如果一臺region server下線，為了恢復(fù)其上的region，需要將region server上的log進行拆分，然后分發(fā)到其它region server上進行恢復(fù)。
HLog文件就是一個普通的Hadoop Sequence File，Sequence File 的Key是HLogKey對象，HLogKey中記錄了寫入數(shù)據(jù)的歸屬信息，除了table和region名字外，同時還包括 sequence number和timestamp，timestamp是”寫入時間”，sequence number的起始值為0，或者是最近一次存入文件系統(tǒng)中sequence number。HLog Sequece File的Value是HBase的KeyValue對象，即對應(yīng)HFile中的KeyValue，可參見上文描述。

四、 系統(tǒng)架構(gòu)

Client
1 包含訪問hbase的接口，client維護著一些cache來加快對hbase的訪問，比如regione的位置信息。

Zookeeper
1 保證任何時候，集群中只有一個master
2 存貯所有Region的尋址入口。
3 實時監(jiān)控Region Server的狀態(tài)，將Region server的上線和下線信息實時通知給Master
4 存儲Hbase的schema,包括有哪些table，每個table有哪些column family

Master
1 為Region server分配region
2 負責region server的負載均衡
3 發(fā)現(xiàn)失效的region server并重新分配其上的region
4 GFS上的垃圾文件回收
5 處理schema更新請求

Region Server
1 Region server維護Master分配給它的region，處理對這些region的IO請求
2 Region server負責切分在運行過程中變得過大的region
可以看到，client訪問hbase上數(shù)據(jù)的過程并不需要master參與（尋址訪問zookeeper和region server，數(shù)據(jù)讀寫訪問regione server），master僅僅維護者table和region的元數(shù)據(jù)信息，負載很低。

五、關(guān)鍵算法 / 流程
region定位
系統(tǒng)如何找到某個row key (或者某個 row key range)所在的region
bigtable 使用三層類似B+樹的結(jié)構(gòu)來保存region位置。
第一層是保存zookeeper里面的文件，它持有root region的位置。
第二層root region是.META.表的第一個region其中保存了.META.z表其它region的位置。通過root region，我們就可以訪問.META.表的數(shù)據(jù)。
.META.是第三層，它是一個特殊的表，保存了hbase中所有數(shù)據(jù)表的region 位置信息。

說明：
1 root region永遠不會被split，保證了最需要三次跳轉(zhuǎn)，就能定位到任意region 。
2.META.表每行保存一個region的位置信息，row key 采用表名+表的最后一樣編碼而成。
3 為了加快訪問，.META.表的全部region都保存在內(nèi)存中。
假設(shè)，.META.表的一行在內(nèi)存中大約占用1KB。并且每個region限制為128MB。
那么上面的三層結(jié)構(gòu)可以保存的region數(shù)目為：
(128MB/1KB) * (128MB/1KB) = = 2(34)個region
4 client會將查詢過的位置信息保存緩存起來，緩存不會主動失效，因此如果client上的緩存全部失效，則需要進行6次網(wǎng)絡(luò)來回，才能定位到正確的region(其中三次用來發(fā)現(xiàn)緩存失效，另外三次用來獲取位置信息)。

讀寫過程
上文提到，hbase使用MemStore和StoreFile存儲對表的更新。
數(shù)據(jù)在更新時首先寫入Log(WAL log)和內(nèi)存(MemStore)中，MemStore中的數(shù)據(jù)是排序的，當MemStore累計到一定閾值時，就會創(chuàng)建一個新的MemStore，并且將老的MemStore添加到flush隊列，由單獨的線程flush到磁盤上，成為一個StoreFile。于此同時，系統(tǒng)會在zookeeper中記錄一個redo point，表示這個時刻之前的變更已經(jīng)持久化了。(minor compact)
當系統(tǒng)出現(xiàn)意外時，可能導(dǎo)致內(nèi)存(MemStore)中的數(shù)據(jù)丟失，此時使用Log(WAL log)來恢復(fù)checkpoint之后的數(shù)據(jù)。
前面提到過StoreFile是只讀的，一旦創(chuàng)建后就不可以再修改。因此Hbase的更新其實是不斷追加的操作。當一個Store中的StoreFile達到一定的閾值后，就會進行一次合并(major compact),將對同一個key的修改合并到一起，形成一個大的StoreFile，當StoreFile的大小達到一定閾值后，又會對 StoreFile進行split，等分為兩個StoreFile。
由于對表的更新是不斷追加的，處理讀請求時，需要訪問Store中全部的 StoreFile和MemStore，將他們的按照row key進行合并，由于StoreFile和MemStore都是經(jīng)過排序的，并且StoreFile帶有內(nèi)存中索引，合并的過程還是比較快。
寫請求處理過程

1 client向region server提交寫請求
2 region server找到目標region
3 region檢查數(shù)據(jù)是否與schema一致
4 如果客戶端沒有指定版本，則獲取當前系統(tǒng)時間作為數(shù)據(jù)版本
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發(fā)送一個裝載請求，把region分配給這個region server。region server得到請求后，就開始對此region提供服務(wù)。

region server上線
master使用zookeeper來跟蹤region server狀態(tài)。當某個region server啟動時，會首先在zookeeper上的server目錄下建立代表自己的文件，并獲得該文件的獨占鎖。由于master訂閱了server 目錄上的變更消息，當server目錄下的文件出現(xiàn)新增或刪除操作時，master可以得到來自zookeeper的實時通知。因此一旦region server上線，master能馬上得到消息。

region server下線
當region server下線時，它和zookeeper的會話斷開，zookeeper而自動釋放代表這臺server的文件上的獨占鎖。而master不斷輪詢 server目錄下文件的鎖狀態(tài)。如果master發(fā)現(xiàn)某個region server丟失了它自己的獨占鎖，(或者master連續(xù)幾次和region server通信都無法成功),master就是嘗試去獲取代表這個region server的讀寫鎖，一旦獲取成功，就可以確定：
1 region server和zookeeper之間的網(wǎng)絡(luò)斷開了。
2 region server掛了。
的其中一種情況發(fā)生了，無論哪種情況，region server都無法繼續(xù)為它的region提供服務(wù)了，此時master會刪除server目錄下代表這臺region server的文件，并將這臺region server的region分配給其它還活著的同志。
如果網(wǎng)絡(luò)短暫出現(xiàn)問題導(dǎo)致region server丟失了它的鎖，那么region server重新連接到zookeeper之后，只要代表它的文件還在，它就會不斷嘗試獲取這個文件上的鎖，一旦獲取到了，就可以繼續(xù)提供服務(wù)。

master上線
master啟動進行以下步驟:
1 從zookeeper上獲取唯一一個代碼master的鎖，用來阻止其它master成為master。
2 掃描zookeeper上的server目錄，獲得當前可用的region server列表。
3 和2中的每個region server通信，獲得當前已分配的region和region server的對應(yīng)關(guān)系。
4 掃描.META.region的集合，計算得到當前還未分配的region，將他們放入待分配region列表。

master下線
由于master只維護表和region的元數(shù)據(jù)，而不參與表數(shù)據(jù)IO的過程，master下線僅導(dǎo)致所有元數(shù)據(jù)的修改被凍結(jié)(無法創(chuàng)建刪除表，無法修改表的schema，無法進行region的負載均衡，無法處理region 上下線，無法進行region的合并，唯一例外的是region的split可以正常進行，因為只有region server參與)，表的數(shù)據(jù)讀寫還可以正常進行。因此master下線短時間內(nèi)對整個hbase集群沒有影響。從上線過程可以看到，master保存的信息全是可以冗余信息（都可以從系統(tǒng)其它地方收集到或者計算出來），因此，一般hbase集群中總是有一個master在提供服務(wù)，還有一個以上的’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協(xié)議：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
七、結(jié)語：
全文對 Hbase做了 簡單的介紹，有錯誤之處，敬請指正。未來將結(jié)合 Hbase 在淘寶數(shù)據(jù)平臺的應(yīng)用場景，在更多細節(jié)上進行深入。

參考文檔
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

很久沒寫博客了，因為很忙，不過今天發(fā)現(xiàn)一篇不錯的文章，幫我梳理了下HBase，原文地址：http://www.tbdata.org/archives/1509

posted @ 2013-06-07 22:14 鑫龍閱讀(338) | 評論 (0) | 編輯收藏

僅列出標題
共20頁: 1 2 3 4 5 6 7 8 9 Last

mysileng

導(dǎo)航

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

java中wait/notify機制

Dijkstra算法（單源最短路徑）

逆序數(shù)及其求法

hadoop0.20.2在eclipse中的編譯

Zookeeper工作原理

1 Zookeeper的基本概念

1.1 角色

1.2 設(shè)計目的

2 ZooKeeper的工作原理

2.1 選主流程

2.2 同步流程

2.3 工作流程

2.3.1 Leader工作流程

2.3.2 Follower工作流程

分布式服務(wù)框架 Zookeeper -- 管理分布式環(huán)境中的數(shù)據(jù)

Google利器之Chubby

程序員技術(shù)練級攻略

前言

啟蒙入門

進階加深

高級深入

m進制轉(zhuǎn)換為n進制-任意進制轉(zhuǎn)換算法

HBase簡介（很好的梳理資料）

一、簡介

二、邏輯視圖

三、物理存儲

四、系統(tǒng)架構(gòu)

五、關(guān)鍵算法 / 流程

導(dǎo)航

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

1 Zookeeper的基本概念

1.1 角色

1.2 設(shè)計目的

2 ZooKeeper的工作原理

2.1 選主流程

2.2 同步流程

2.3 工作流程

2.3.1 Leader工作流程

2.3.2 Follower工作流程

前言

啟蒙入門

進階加深

高級深入

一、 簡介

二、 邏輯視圖

三、 物理存儲

四、 系統(tǒng)架構(gòu)

五、關(guān)鍵算法 / 流程

一、簡介

二、邏輯視圖

三、物理存儲

四、系統(tǒng)架構(gòu)