雲端運算survey項目 - 分散式文件系統

關於 Google MapReduce, Apache Hadoop 分散式文件系統的簡述。

MapReduce 的概念源自於並行運算的領域中很普遍的資料處理策略。 Map 在 MapReduce 中的詞性是一個動詞，取其 “劃分地圖“之義。它的內涵是將一整塊資料儘可能按照不相關聯的地方劃分成好幾片。就好像是在一張大地圖中劃分區域分界線般，故稱此動作為 Map。

被 Map 成好幾片的資料，分別被儲存在不同的 host 中。當使用者需要處理該份資料時，再將運算程序再複製到那些 host 上，開始處理那些資料。最後將散佈在不同 host 上的程序所運算的結果化簡歸納成使用者要的最終結果，就是 Reduce。

將 MapReduce 結合分散式文件系統後，就是 Google 得以高效率處理網頁文件搜尋的核心系統。

Google - MapReduce

MapReduce是Google提出的一個軟體架構，用於大規模數據集（大於1TB）的并行運算。概念"Map（映射）"和"Reduce（化簡）"，和他們的主要思想，都是從函數式程式語言借來的，還有從向量程式語言借來的特性。

在Google，MapReduce用在非常廣泛的應用程序中，包括「分佈grep，分佈排序，web連接圖反轉，每台機器的詞向量，web訪問日誌分析，反向索引構建，文檔聚類，機器學習，基於統計的機器翻譯……」值得注意的是，MapReduce實現以後，它被用來重新生成Google的整個索引，並取代老的ad hoc程序去更新索引。
http://zh.wikipedia.org/zh-tw/MapReduce

Map 在 MapReduce 中的詞性是一個動詞，取其 “劃分地圖“之義，而不是”映射“。它的內涵是將一整塊資料儘可能按照不相關聯的地方劃分成好幾片。就好像是在一張大地圖中劃分區域分界線般，故稱此動作為 Map。

MapReduce 的概念源自於並行運算的領域中很普遍的資料處理策略。下列的 C 程式碼可以幫助大家理解 MapReduce 的基本概念。

// File name: vector_sum.c

#include <stdio.h>

#include <omp.h>


int main() {
    int i, j, sumLocal, sum;
    int size = 3;
    int vector[3][3] = {3, 4, 1, 6, 3, 4, 7, 5, 9};

    sum = sumLocal = 0;
    omp_set_num_threads(size); // Try to map vector to 3 pieces.

    #pragma omp parallel private(sumLocal)
    {
        /**
            If there are no accidents, the following information will be divided  
            into (Map) three pieces.
            for (i=0; i < 1; ++i) {...}
            for (i=1; i < 2; ++i) {...}
            for (i=2; i < 3; ++i) {...}
        **/
        #pragma omp for
        for (i=0; i < size; ++i)
        {
            for (j=0; j < size; ++j)
                sumLocal += vector[i][j];
        }

        /**
            Reduce sumLocal's to sum.
        **/
        #pragma omp critical(update_sum)
        {
            sum += sumLocal;
        }
    }

    printf("Sum = %d\n", sum);

    return 0;
}


$ gcc -openmp -lgomp -o vector_sum vector_sum.c
$ ./vector_sum
Sum = 42

這個 C 程式利用了 OpenMP 進行多緒並行運算。 GCC 需要版本 4.3.2 以上才支援。

雖然 Google 發表了 MapReduce 的概念，但 Google 的實作軟體並未 Open source ，所以我們無法取得。所幸有人根據 MapReduce 的概念，發展了一套 Open source 的分散式文件系統，即 Hadoop 。

Yahoo - Hadoop

Hadoop是Apache軟件基金會所研發的開放源碼並行運算編程工具和分佈式文件系統，與MapReduce和Google檔案系統的概念類似。
http://zh.wikipedia.org/wiki/Hadoop
Hadoop 是一个开源的可运行于大规模集群上的分布式并行编程框架，由于分布式存储对于分布式编程来说是必不可少的，这个框架中还包含了一个分布式文件系统 HDFS( Hadoop Distributed File System )。
http://www.ibm.com/developerworks/cn/opensource/os-cn-hadoop1/index.html

Hadoop 的檔案系統稱為 HDFS，這是一種虛擬檔案系統，乍看之下，文件儲存方式類似一般實體檔案系統，我們一樣可以建立目錄，也可以將文件從實體檔案系統複製過去，但實際上文件是以 Hadoop 特殊的儲存機制分散在不同 host 的空間中。例如:


$ echo hello > /home/rock/hello.txt

# 從本地實體檔案系統中，將 hello.txt 複製到 Hadoop HDFS 的虛擬檔案系統中。
$ hadoop fs -put /home/rock/readme.txt /home/rock

# 異動本地的 hello.txt
$ echo my name is rock >> /home/rock/hello.txt

# 現在可以看出這其實是不同的兩份文件了。
# 初學者常常在此感到混淆，誤以為這兩個 /home/rock/hello.txt 是同一份文件。
$ cat /home/rock/hello.txt
$ hadoop fs -cat /home/rock/readme.txt

Hadoop 還有一個基於 HDFS 的資料庫管理系統實作，稱為 HBase 。HBase 主要用於儲存零散結構的大型資料表。為此，HBase 則採用 column-oriented 儲存策略，有別於一般關聯式資料庫系統所採用的 row-oriented 儲存策略。由於資料結構不同，基於查詢效率的考量，HBase 並不支援 SQL 。

Hadoop 的文件與程式儲存概念。

上圖的左半部是我畫的，右半部來自《Hadoop: The Definitive Guide》，剛好疊上去。

我們可以透過添置主機的方式，持續將新的主機加入 Hadoop core 中，便可以不斷增加 HDFS 的儲存空間。

當一份文件要儲放入 HDFS 時，實際上被劃分(map)成好幾片。被 Map 成好幾片的資料，分別被儲存在不同的 host 中。當使用者需要處理該份資料時，再將運算程序再複製到那些 host 上，開始處理那些資料。最後將散佈在不同 host 上的程序所運算的結果 Reduce 成使用者要的最終結果。

Moving Computation is Cheaper than Moving Data
HDFS Architecture

Hadoop on live

趨勢科技提供了一個安裝了 Hadoop 的虛擬機影像，可自趨勢科技－ Hadoop 實作環境下載。下載點: hadoop_centos5 (VMWare image)。我們可以在此環境中練習 Hadoop 。

應用對象

目前 Hadoop 的檔案系統 HDFS 尚不提供文件修改功能，而且分散式文件系統在性質上並不適合處理頻繁異動的資料，故適合透過 HDFS 儲存的文件，主要是靜態文件。例如以 MIME 儲存的郵件 (傳統的 unix mailbox 格式)、進銷存系統中的銷售記錄（發票）、電子公文系統中發佈的公文、程式運行的過往log。

在「Hadoop: The Definitive Guide」一書中，則以 Streamy.com 作為 HBase 的應用案例，不過並未詳例哪些資料內容適合改用 HBase 儲存。

References

MapReduce: Simplified Data Processing on Large Clusters
The Google File System
用 Hadoop 进行分布式并行编程，第 1 部分：基本概念与安装部署
用 Hadoop 进行分布式并行编程，第 2 部分：程序实例与分析
用 Hadoop 进行分布式并行编程, 第 3 部分：部署到分布式环境
Apache Hadoop!

樂多舊網址: http://blog.roodo.com/rocksaying/archives/10348123.html