海量資料處理

本文轉自：http://blog.csdn.net/hguisu/article/details/7853892

       海量資料處理是基于海量資料上的存儲、處理、操作。

       所謂海量，就是資料量很大，可能是TB級别甚至是PB級别，導緻無法一次性載入記憶體或者無法在較短時間内處理完成。面對海量資料，我們想到的最簡單方法即是分治法，即分開處理，大而化小，小而治之。我們也可以想到叢集分布式處理。

1 海量資料的存儲：為大資料分析做準備

傳統關系型資料庫         傳統關系型資料庫在資料存儲上主要面向結構化資料，聚焦于便捷的資料查詢分析能力、按照嚴格規則快速處理事務（transaction）的能力、多使用者并發通路能力以及資料安全性的保證。其結構化的資料組織形式，嚴格的一緻性模型，簡單便捷的查詢語言，強大的資料分析能力以及較高的程式與資料獨立性等優點獲得廣泛應用。  但是 面向結構化資料存儲的關系型資料庫已經不能滿足當今網際網路資料快速通路、大規模資料分析挖掘的需求。 它主要缺點： 1) 對于半結構化、非結構化的海量資料存儲效果不理想。像電子郵件、 超文本、标簽（Tag）以及圖檔、音視訊等各種非結構化的海量資料。

2）關系模型束縛對海量資料的快速通路能力： 關系模型是一種按内容通路的模型。即在傳統的關系型資料庫中，根據列的值來定位相應的行。這種通路模型，會在資料通路過程中引入耗時的輸入輸出，進而影響快速通路的能力。雖然，傳統的資料庫系統可以通過分區的技術（水準分區和垂直分區） ，來減少查詢過程中資料輸入輸出的次數以縮減響應時間， 提高資料處理能力， 但是在海量資料的規模下，這種分區所帶來的性能改善并不顯著。 

3）在海量規模下， 傳統資料庫一個緻命弱點， 就是其可擴充性差。 非集中式資料存儲管理系統

1）亞馬遜（Amazon）的 Dynamo ：        Dynamo是亞馬遜的key-value模式的存儲平台，可用性和擴充性都很好，性能也不錯：讀寫通路中99.9%的響應時間都在300ms内。 在 Dynamo 中，資料按照鍵/值對（key-value）進行組織，主要面向原始資料的存儲。這種架構下，系統中每個節點都能互相感覺，自我管理性能較強，沒有單點失效。  2）Google的Bigtable         Bigtable 是谷歌開發的一套結構化存儲系統。資料以多元順序表的方式進行存儲。整個系統采用傳統的伺服器群形式，由一個主要伺服器和多個子表伺服器構成，并使用分布式鎖服務 Chubby進行容錯等管理。這種架構下，将存儲（依靠 GFS）和服務的管理分離開來，簡化了管理難度，易于維護且人為可控。但是由于底層存儲依賴分布式檔案系統，使得Bigtable 隻能在叢集中部署。 

      hadoop中Hbase就是Google BigTable的開源實作。 2）Facebook 的 Cassandra        CassandraCassandra最初由Facebook開發,後轉變成了開源項目. 是一套采用對等網絡計算（peer to peer，P2P）技術實作的結構化資料存儲系統。以Amazon專有的完全分布式的Dynamo為基礎，結合了Google BigTable基于列族（Column Family）的資料模型.P2P去中心化的存儲。很多方面都可以稱之為Dynamo 2.0。       與 Dynamo 有所不同的是，Cassandra 采用類似 Bigtable 的多元表資料模型組織資料。其主要功能比Dynamo更豐富，但支援度卻不如文檔存儲MongoDB（介于關系資料庫和非關系資料庫之間的開源産品，是非關系資料庫當中功能最豐富，最像關系資料庫的。支援的資料結構非常松散，是類似json的bjson格式，是以可以存儲比較複雜的資料類型。） 主要特性：

　　● 分布式

　　● 基于column的結構化

　　● 高伸展性

2  海量資料處理 

       海量資料處理就是如何快速地從這些海量資料中抽取出關鍵的資訊，然後提供給使用者。

并行計算解決方案：      解決大規模資料處理的方法之一就是并行計算。将大量資料分散到多個節點上，将計算并行化，利用多機的計算資源，進而加快資料處理的速度。目前，這種并行計算的模型主要分為三大類： 一類是廣泛應用于高性能計算的 MPI技術， 一類是以谷歌/雅虎為代表的網際網路 網際網路海量資料存儲和處理技術綜述 企業興起的 Map/Reduce計算， 一類是微軟提出的 Dryad[并行計算模型。

1）MPI        MPI 即消息傳遞接口（MessagePassing Interface），是一種程式設計接口标準，而不是一種具體的程式設計語言。       MPI 是一種工業标準的 API規範，專為在多處理器計算機、計算機叢集和超級計算機上進行高性能計算而設計。該标準是由大量計算機供應商和軟體開發商于 1994 年共同設計完成。 

       MPI 作為目前國際上最流行的并行程式設計環境之一，因其良好的可移植性和易用性、完備的異步通信功能等優點，而在機群高性能計算中得到廣泛應用。在基于 MPI 程式設計模型中，計算任務是由一個或多個彼此間通過調用庫函數進行消息收、發通信的程序所組成。絕大部分 MPI 實作在程式初始化時生成一組固定的通信程序。這些程序在不同的節點上運作（通常一個處理器一個程序） ，執行着相同或不同的程式，以點對點通信或者集合通信的方式進行程序間互動，共同協作完成同一個計算任務。 

      以任務之間的消息傳遞驅動的 MPI，其進行大規模資料處理的基本思路就是，将任務劃分成為可以獨立完成的不同計算部分， 将每個計算部分需要處理的資料分發到相應的計算節點分别進行計算，計算完成後各個節點将各自的結果集中到主計算節點進行結果的最終彙總。 

2） MapReduce 

       MapReduce是谷歌在 2004 年提出的應用于大規模叢集進行大規模資料處理的并行計算模型。 Map（映射）和 Reduce（化簡）的概念，以及他們的主要思想，都來自于函數式語言。

       在一個計算任務中，計算被抽象并簡化成為兩個階段：Map 和 Reduce。Map 階段，系統調用使用者提供的 Map 函數，完成從一組鍵值到新一組鍵值的映射計算；而 Reduce 階段，使用者指定的 Reduce 函數則被用來将所有 Map 計算完成的結果進行一次化簡歸約。 與 MPI 有所不同的是，Map/Reduce 是通過将計算（Map 或者Reduce）分發到相應的資料存儲節點或靠近的節點，讓計算（Map 或者 Reduce）在資料存儲節點就地或者就近完成，盡可能減輕大量資料在網絡上傳輸所産生的壓力。

       詳細文檔：  

谷歌三大核心技術（二）Google MapReduce中文版

3）Dryad

       Dryad 是微軟在 2007 年提出的資料并行計算模型。目前已經在 Microsoft Ad’Center 投入使用。 與 MapReduce的思路類似， Dryad 也是通過将計算任務移動到相應的資料存儲節點或靠近的節點，讓計算就地或者就近完成，進而減輕網絡上傳輸的壓力。 在 Dryad 中，每個計算任務被表示成一個有向無環圖（Directed Acyclic Graph, DAG） ，計算任務按照有向無環圖的方向按照依賴關系執行。DAG 相對于兩階段式的 MapReduce，可以表達更加豐富的計算類型；同時，它支援在子任務之間通過 TCP管道、Shared-memory FIFOs（共享記憶體先進先出）進行結果傳遞，盡量避免一些不必要的磁盤輸入輸出，加速計算的執行。

如果從資料結構和算法來考慮處理海量資料：

1. Bloom Filter
2. Hash統計和映射
3. Bit-Map
4. 堆(Heap)/快速/歸并排序
5. 雙層桶劃分
6. 資料庫索引
7. 反向索引（Inverted Index）
8. 外排序
9. Trie樹

      這些都是針對特定場景,如 在大量資料中（1千萬以上）中,選出最大的k個數或者是頻率最高的前k條文本資料等。