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