面試題-關于大數(shù)據(jù)量的分布式處理

題目：生產(chǎn)系統(tǒng)每天會產(chǎn)生一個日志文件F，數(shù)據(jù)量在5000W行的級別。文件F保存了兩列數(shù)據(jù)，一列是來源渠道，一列是來源渠道上的用戶標識。文件F用來記錄當日各渠道上的所有訪問用戶，每訪問一次，記錄一條。

請問如何快速計算出各渠道上新增的用戶？

問題分析：首先本次面試的是有關于分布式數(shù)據(jù)處理以及數(shù)據(jù)分析的職位，所以相關的面試題目可能會偏向于使用分布式的思想去解決。但無奈本人當時反應太慢，實在沒向分布式處理方向思考。

方案一：

本題最直觀的一個處理方法就是，直接拿著當日新增的5000W條訪問記錄一條一條的去匹配歷史訪問用戶。若存在歷史訪問記錄，則忽略；若不存在訪問記錄，則保存為新增記錄。很明顯，假若歷史訪問用戶有2億條記錄，則需要和2億條數(shù)據(jù)比較5000W次。比較次數(shù)可想而知。

由于本人一直在做基于數(shù)據(jù)庫的數(shù)據(jù)處理工作，很容易就想到將歷史數(shù)據(jù)保存在數(shù)據(jù)庫的一張表中，并對來源渠道和用戶標識這兩個字段建立索引，然后遍歷日志文件F（5000W次）。根據(jù)日志文件F中的每一行去匹配數(shù)據(jù)庫中的歷史訪問記錄。由于歷史數(shù)據(jù)表有索引，單次查詢的速度也非?？?。但是需要5000W次的數(shù)據(jù)庫查詢，很明顯效率低下。

方案二：

既然多次單一查詢無法滿足要求，于是可以先通過一種數(shù)據(jù)導入技術將當日新增數(shù)據(jù)導入到數(shù)據(jù)庫的另一張表中，并和歷史數(shù)據(jù)做左外關聯(lián)。若能關聯(lián)成功，則表示此用戶已存在；若關聯(lián)失敗，則表示此用戶不存在。

此方案暫且不說5000W條記錄的大表與2億條記錄的大表關聯(lián)效率有多高以及使用到的數(shù)據(jù)庫緩沖區(qū)的資源有多少，單就5000W條訪問記錄導入數(shù)據(jù)庫表，都是一個不小的時間花費。

方案三：

很明顯，面試時方案二的回答并未達到面試官的預期，最初被遺憾的PASS掉。一家很有潛力，自己很看好的公司，并計劃做為自己未來發(fā)展方向的職位，就這樣丟下我，揚長而去了。

這幾天又看了下分布式相關的介紹，突然想到這道題。一下子醒悟過來，其實還是因為對題目要考察的點分析得不夠透徹。當時以為只是僅僅考數(shù)據(jù)處理效率的一個題目，其實考的是一種將復雜問題拆分為簡單問題的拆分思想。了解到這一層，一種新的方式立馬在腦海中浮現(xiàn)出來。具體如下：

假如現(xiàn)在有N（N>=2）個存儲塊，并存在一個函數(shù)f（來源渠道，用戶標識），對于給定的一組（來源渠道，用戶標識），總能將其分發(fā)到一個固定的存儲塊內(nèi)。那么可以使用此函數(shù)將5000W行訪問記錄盡量均勻的分發(fā)至N個存儲塊上，并同時使用此函數(shù)將歷史訪問記錄也分發(fā)至這些存儲塊上。由于相同的一組記錄，肯定會被分配至同一個存儲塊，所以比較時，只需要分別比較各個存儲塊上當日新增記錄與歷史訪問用戶，然后將N個存儲塊上比較的結果匯總，即可得到最終結果。

假設歷史訪問用戶數(shù)據(jù)已通過函數(shù)f（來源渠道，用戶標識）被分發(fā)至了N個歷史文件H1、H2、…、HN。則詳細處理步驟如下：

1、將F中的內(nèi)容使用函數(shù)f（來源渠道，用戶標識），分發(fā)至文件F1、F2、…、FN內(nèi)。（可開M（M>=2）個并行，且若N-M越大，同時向同一文件寫入數(shù)據(jù)的概率越?。?

2、將文件F1、F2、…、FN內(nèi)的訪問記錄去重。（可開N個并行分別處理對應的N個文件）。

3、將文件Fn（1=<n<=N）去重后的結果與對應的歷史文件Hn比較得出新增用戶結果Rn。（可開N個并行分別處理對應的N個文件且當N足夠大時，實際要處理數(shù)據(jù)的量級就會相當?。?

4、合并第3步得到的結果R1、R2、…、RN即可得到當日新增用戶。（可并行）

5、為使歷史數(shù)據(jù)文件H1、H2、…、HN中的數(shù)據(jù)最全，將結果R1、R2、…、RN分別寫入對應的歷史文件中。（可并行）

本方案主要有以下優(yōu)點：

1、數(shù)據(jù)的分發(fā)、處理、合并都可并行處理，明顯提高了處理效率。

2、由于每個存儲塊上的新增數(shù)據(jù)，只需要與它對應存儲塊上的歷史數(shù)據(jù)比較即可，大大減少了比較次數(shù)。（對于當日每一條記錄來說，都只需要與大約歷史的N分之一條數(shù)據(jù)去比較）

3、基本不需要考慮歷史全量數(shù)據(jù)的保存及獲取問題。

本方案缺點：

1、處理方案明顯變的復雜許多，不僅需要處理數(shù)據(jù)的分發(fā)，處理，還需要一個并行的快速收集方法。

2、可能需要多臺服務器并行處理。

本方案難點：

1、一個穩(wěn)定（對于相同的一組來源渠道和用戶標識，必定會被分發(fā)至同一存儲塊）、快速（根據(jù)一條來源渠道和用戶標識數(shù)據(jù)，可以快速的計算出它將要被分發(fā)至的存儲塊）、均勻（當日新增數(shù)據(jù)及歷史數(shù)據(jù)都能盡量均勻的被分發(fā)至N個存儲塊，最理想的情況是每個存儲塊上分發(fā)到的數(shù)據(jù)都是總數(shù)據(jù)的N分之一）的分發(fā)函數(shù)至關重要。

2、如何分發(fā)、并行處理及匯總數(shù)據(jù)。