去年我寫了《Muduo 網(wǎng)絡(luò)編程示例》系列文章，這些文章已經(jīng)收入《Linux 多線程服務(wù)端編程：使用 muduo C++ 網(wǎng)絡(luò)庫(kù)》一書。這些文章講的基本都是運(yùn)行在單機(jī)上的網(wǎng)絡(luò)程序，每個(gè)例子都只有一個(gè)程序（第7.13節(jié)例外）。我接下來(lái)打算繼續(xù)寫幾篇文章，談一談分布在多臺(tái)機(jī)器上、協(xié)作發(fā)揮作用的網(wǎng)絡(luò)編程例子。
今天先講第一個(gè)，單詞計(jì)數(shù)及排序。單詞計(jì)數(shù)（word count），顧名思義就是統(tǒng)計(jì)一個(gè)文本文件里邊每個(gè)詞出現(xiàn)了多少次。排序指的是按出現(xiàn)次數(shù)從多到少排序，也可以把問(wèn)題改為“找出出現(xiàn)次數(shù)最多的1000個(gè)單詞”。
這個(gè)問(wèn)題有三個(gè)層次，第一是輸入文件比較小，能完全放入內(nèi)存；第二是輸入文件比較大，不能一次性都放入內(nèi)存；第三是輸入文件分布在多臺(tái)機(jī)器上，這需要用到網(wǎng)絡(luò)編程。
第一個(gè)層次很好解決，幾十行代碼就搞定了。https://gist.github.com/4519962
第二個(gè)層次不難解決，基本思路是分而治之，先hash分塊統(tǒng)計(jì)單詞出現(xiàn)次數(shù)，將每一塊按出現(xiàn)次數(shù)排序，最后歸并。代碼見 https://github.com/chenshuo/recipes/blob/master/puzzle/query_freq.cc ，分析見 http://www.cnblogs.com/baiyanhuang/archive/2012/11/11/2764914.html 。
第三個(gè)層次也不難，可以當(dāng)做網(wǎng)絡(luò)編程的練習(xí)來(lái)做。如果有合適的框架，可以輕松解決，因?yàn)閱卧~計(jì)數(shù)是map reduce的經(jīng)典范例，對(duì)出現(xiàn)次數(shù)排序也可以再用一步map reduce搞定（估計(jì)需要一個(gè)好的 shuffle 函數(shù)，簡(jiǎn)單hash是不行的）。
如果用普通網(wǎng)絡(luò)編程，一種設(shè)計(jì)思路如下圖，其中方框代表機(jī)器，橢圓代表輸入輸出文件，圓角矩形代表進(jìn)程。思路跟第二個(gè)層次一樣，先hash到多個(gè)shard文件（由hasher和receiver負(fù)責(zé)），再對(duì)每個(gè)shard文件排序（由sender負(fù)責(zé)），最后歸并（merger）。
注意這種思路適合求top K元素，不適合按出現(xiàn)次數(shù)排序全部單詞，因?yàn)樽罱K結(jié)果收集在一臺(tái)機(jī)器上。目前這個(gè)sender實(shí)現(xiàn)的一個(gè)限制是，每個(gè)shard必須能全部放入內(nèi)存，因?yàn)閟ender對(duì)shard排序是在內(nèi)存中進(jìn)行的。如果數(shù)據(jù)更大，還需要實(shí)現(xiàn)單機(jī)外部排序。
圖中hasher和receiver的代碼見muduo示例中的 muduo/examples/wordcount ；sender和merger的代碼見 https://github.com/chenshuo/recipes/tree/master/topk 。注意merger沒(méi)有使用muduo，而是采用阻塞網(wǎng)絡(luò)編程。有興趣的讀者可以思考其背后的原因。要想發(fā)揮 merger 正常的性能，需要修改 /usr/include/boost/asio/basic_socket_streambuf.hpp ，增大緩沖區(qū)，即 enum { buffer_size = 8192 };
這可以看作是map reduce的原始實(shí)現(xiàn)，或者說(shuō)用map reduce的思想手寫了一些原始工具。如果把map reduce比作C語(yǔ)言，這里的幾個(gè)程序相當(dāng)于匯編寫的函數(shù)。
以后我再寫一個(gè)按出現(xiàn)次數(shù)全排序的例子吧，需要替換這里的sender和merger。
(.完.)