AI時代：聊聊大數據中的MapReduce

02-12

各位朋友，大家好，我是Payne，歡迎大家關注我的博客。最近讀一本並行計算相關的書籍，在這本書中作者提到了MapReduce。相信熟悉大數據領域的朋友，一定都知道MapReduce是Hadoop框架中重要的組成部分。在這篇文章中，博主將以函數式編程作為切入點，來和大家聊一聊大數據中的MapReduce。如今人工智慧正成為行業內競相追逐的熱點，選擇MapReduce這個主題，更多的是希望帶領大家一窺人工智慧的門庭，更多深入的話題需要大家來探索和挖掘。

MapReduce的前世今生

MapReduce最早是由Google公司研究並提出的一種面向大規模數據處理的並行計算模型和方法。2003年和2004年，Google公司先後在國際會議上發表了關於Google分散式文件系統(GFS)和MapReduce的論文。這兩篇論文公布了Google的GFS和MapReduce的基本原理和主要設計思想，我們通常所說的Google的三駕馬車，實際上就是在說GFS、BigTable和MapReduce。因此，這些論文的問世直接催生了Hadoop的誕生，可以說今天主流的大數據框架如Hadoop、Spark等，無一不是受到Google這些論文的影響，而這正是MapReduce由來，其得名則是因為函數式編程中的兩個內置函數: map()和reduce()。

我們常常說，脫離了業務場景去討論一項技術是無意義的，這個原則在MapReduce上同樣適用。眾所周知，Google是一家搜索引擎公司，其設計MapReduce的初衷，主要是為了解決搜索引擎中大規模網頁數據的並行化處理。所以，我們可以說，MapReduce其實是起源自Web檢索的。而我們知道，Web檢索可以分為兩部分，即獲取網頁內容並建立索引、根據網頁索引來處理查詢關鍵字。我們可以認為互聯網上的每個網頁都是一個文檔，而每個文檔中都會有不同的關鍵字，Google會針對每一個關鍵字建立映射關係，即哪些文檔中含有當前關鍵字，這是建立索引的過程。在建立索引以後，查詢就會變得簡單，因為現在我們可以按圖索驥。

互聯網誕生至今，網站及網頁的數量越來越龐大，像Google這樣的搜索引擎巨頭是如何保證能夠對Web上的內容進行檢索的呢？答案是採用並行計算(Parallel)。硬體技術的不斷革新，讓計算機可以發揮多核的優勢來處理數據，可當數據量龐大到單機無法處理的程度，就迫使我們不得不採用多台計算機進行並行計算。我們知道並行計算的思想是，將大數據分割成較小的數據塊，交由不同的任務單元來處理，然後再將這些結果聚合起來。因此，可以將MapReduce理解為一種可以處理海量數據、運行在大規模集群上、具備高度容錯能力、以並行處理方式執行的軟體框架。MapReduce是分治思想在大規模機器集群時代的集中體現(如圖所示)，其中，Mapper負責任務的劃分，Reducer負責結果的匯總。

MapReduce的推出給大數據並行處理帶來了巨大的革命性影響，使其成為事實上的大數據處理的工業標準，是目前為止最為成功、最廣為接受和最易於使用的大數據並行處理技術。廣為人知的大數據框架Hadoop，正是受到MapReduce的啟發。自問世來，成為Apache基金會下最重要的項目，受到全球學術界和工業界的普遍關注，並得到推廣和普及應用。MapReduce的非凡意義在於，它提出了一個基於集群的高性能並行計算模型，允許使用市場上普通的商用伺服器構成一個含有數十、數百甚至數千個節點的分散式並行計算集群，可以在集群節點上自動分配和執行任務以及收集計算結果，通過Mapper和Reducer提供了抽象的大數據處理並行編程介面，可以幫助開發人員更便捷地完成大規模數據處理的編程和計算工作。今天，Google有超過10000個不同的項目已採用MapReduce來實現。

函數式編程與MapReduce

我們提到，MapReduce之得名，其靈感來自函數式編程中的兩個內置函數：map()和reduce()。函數式編程中，有一個重要的概念叫做高階函數，是指函數自身能夠接受函數，並返回函數的一種函數。我們所熟悉的C#和Java都是典型的面向對象編程(OOP)的語言，在這類編程語言中類(Class)是第一等公民，即不允許有獨立於類的結構出現在代碼中。雖然微軟從未公開表示C#支持函數式編程，可從LINQ中我們依然可以窺見高階函數的身影，譬如我們熟悉的Select()、Where()等擴展方法，就可以讓我們按照函數式編程的風格去編寫代碼，這正是為什麼Java 8開始支持Stream API的原因。最經典的函數式編程語言當屬Haskell語言，我們今天見到的各種編程語言，在考慮引入函數式編程風格的時候，或多或少地都會受到這門語言影響。當你開始適應函數作為第一等公民、高階函數、柯里化以及惰性求值以後，你或許就會感受到函數式編程特有的美感。

這裡我們選擇Python來闡述函數式編程與MapReduce的關係。Python可以讓我們輕易地在多種不同的編程風格間切換，事實上現在的編程語言都有向著混合式編程風格發展的趨勢。我們提到MapReduce來自兩個內置函數：map()和reduce()。其中，map()方法可以對指定集合中的元素按照指定函數進行映射，並將映射後的結果以集合形式返回。譬如我們有一個集合[1,3,5,7,9]，我們希望對集合中的每一個元素做平方運算。藉助Python中的map()方法和lambda表達式，這個問題可以通過1行代碼得到解決。同理，如果我們希望對該集合內的元素做求和運算，我們可以藉助於Python中的reduce()方法，該方法位於functools模塊中。在某些編程語言中該方法又被成為fold()方法，實際上這兩種叫法是等價的，我們關注函數式編程的本質即可。什麼是本質呢？當然是函數啦。

list = map(lambda x: x * x, [1,3,5,7,9]) #[1,9,25,49,81]sum = functools.reduce(lambda x,y: x+y, [1,3,5,7,9]) #25

好了，現在我們來分析下這兩個函數，這將幫助我們更好地理解MapReduce。map()方法在這裡被稱為映射函數，它可以將一種類型映射為一種新的類型。舉一個生活中的例子，譬如我們做菜的時候，必不可少的一個環節是將各種各樣的食材切碎，此時作用在這些食材的這個操作就是一個Map操作，你給Map一個洋蔥就可以得到洋蔥絲。同樣地，你給Map一個番茄就可以得到番茄塊。所以Map處理的原始數據，每條數據間沒有相互聯繫，聰明的你告訴我洋蔥和番茄有什麼關係。相比map()方法，reduce()方法複雜的地方在於，它要求lambda表達式中必須是兩個參數。如果繼續沿用做菜這個生活化的例子，reduce()方法是將Map操作中切好的食材混合在一起。假設我們要做一份辣椒醬，辣椒醬需要的材料有辣椒、姜和蒜，因此在第一步Map的時候，這些食材將具有相同的Key。對同一類數據，我們就可以使用reduce()進行左/右摺疊操作，這相當於我們將同一道菜的食材一起放到鍋里，所以 Reduce階段處理的數據是以Key-Value形式組織的，同一個Key下的Value具有相關性。這樣，從理論上它就完全符合函數式編程里的map()和reduce()啦。

C#並行編程里的PLINQ

關於MapReduce中一個經典案例是，統計不同文章中出現的關鍵字的頻率。對這樣一個問題，我們基本上可以想到下面四種方法：

* 寫一個單線程程序，順序地遍歷所有文章，然後統計每個關鍵字出現的頻率。

* 寫一個多線程程序，並發地遍歷所有文章，然後統計每個關鍵字出現的頻率。

* 寫一個單線程程序，部署到N台不同的計算機上，然後將文章分割成N份分別輸入，再由人工匯總N份結果。

* 使用MapReduce，程序部署、任務劃分、結果匯總全部交給框架去完成，我們定義好任務即可。

通過對比，我們可以非常容易地分析出來，第一種方法最簡單同時最耗時；第二種方法理論上比第一種高效，尤其是當計算機是多核或者多處理器的時候，缺點是要解決線程同步的問題；第三種方法初現集群的思想，可無法解決程序部署、任務劃分和結果匯總等一系列問題；第四種方法本質上就是第三種方法，可是MapReduce解決了第三種方法全部缺陷，所以它或許是目前最完美的方法。我們下面來考慮，如何模擬這個過程，因為博主不可能為了寫一篇科普性質的文章，專門去準備一個Hadoop的開發環境啊，哈哈。

PLINQ，即Parallel LINQ，是.NET 4.0中增加的任務並行庫(TPL)中的一部分。並行編程中有兩個基本的概念，任務並行和數據並行。前者是指，將程序分割成一組任務並使用不同的線程來運行不同的任務，這種方式被稱為任務並行；而後者是指，將數據分割成較小的數據塊，對這些數據進行並行計算，然後聚合這些計算結果，這種編程模型稱為數據並行。伴隨著並行演算法的出現，並行集合相繼而來，顯然LINQ的並行版本就是PLINQ。這裡我們來看一個使用PLINQ實現的詞頻統計代碼，這將作為我們實現MapReduce的一個示例：

//Origin Textsstring strTarget = @"";//Mapstring[] words = strTarget.Split( ); ILookup<string, int> map = words.AsParallel().ToLookup(p => p, k => 1); //Reducevar reduce = from IGrouping<string, int> wordMap in map.AsParallel() where wordMap.Count() > 1 select new { Word = wordMap.Key, Count = wordMap.Count() }; //Show Resultsforeach (var word in reduce) Console.WriteLine("Word: {0} : Count: {1}", word.Word, word.Count);

本文小結

今天Google發布了全新的AI服務工具Cloud AutoML，從這個產品的名字就可以看出，這是一個試圖將人工智慧大眾化的產品。目前AI是行業中不容置疑熱點，國外的科技巨頭如Google、微軟，國內的科技巨頭如騰訊、阿里和百度等，無一不在積極布局AI的上下游產業鏈。最近CSDN發布了人工智慧方向的發展規劃，整個產品線的基本都在做戰略上調整，我們這些曾經的老用戶被新的社區運營搞得非常鬱悶，因為所有的資源都在向著人工智慧和區塊鏈傾斜。上周在知乎上看到一篇諷刺國內區塊鏈發展亂象的文章，大概就是說國人喜歡拿一個Token當做加密貨幣來買，實則連底層技術、分布賬本、錢包等基礎設施都沒有。對於這一點我深有體會，任何新的商業模式在中國都火不過1年，譬如在2017年里被發揚廣大的共享經濟，有多少共享單車是靠技術和產品贏得市場的，我相信大部分都是沾了人口基數大的光。目前的人工智慧，核心演算法及技術都掌握在科技巨頭手上。我們所追逐的人工智慧，有多少是需要靠不斷調整參數反覆去訓練來達到的呢？我覺得找到切實可靠的需求落腳點，比追逐一個又一個熱點要更現實，我們大部分工程師都是在科學家工作的基礎上做集成應用，所以撥開泡沫看清方向比盲目跟風更重要呀。

這篇文章蹭了人工智慧的熱點，其實它對MapReduce並沒有做多少深入的研究。我們從Google的業務場景著手分析，思考為什麼Google需要MapReduce，即提出MapReduce是為了解決一個什麼樣的問題？答案是為了適應Google在大規模Web檢索業務方面的需要。通過梳理Web檢索的一般流程，我們意識到，Web檢索可以分為兩部分，即獲取網頁內容並建立索引、根據網頁索引來處理查詢關鍵字，從而引出了Mapper和Reducer兩個基本的數據處理單元，MapReduce是分治思想在大規模機器集群時代的集中體現，其中，Mapper負責任務的劃分，Reducer負責結果的匯總。接下來，我們順著函數式編程的思路，分析了函數式編程中的map()和reduce()，這兩個核心的函數同MapReduce在思想上的一致性，這正是為了印證前文中MapReduce得名的由來。考慮到C#中提供了PLINQ，而在閱讀《C#多線程編程》這本書時，同樣提到了MapReduce這種並行計算模型，所以在這裡將這兩者進行結合，提供了一個通過並行計算統計單詞頻率的簡單示例。以上就是這篇文章的所有內容了，如果大家對文章有什麼意見或者建議，可以在文章評論區留言，這篇文章就是這樣了，謝謝大家，晚安！