面試題-關于大數據量的分布式處理

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

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

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

方案一：

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

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

方案二：

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

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

方案三：

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

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

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

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

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

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

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

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

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

本方案主要有以下優點：

1、數據的分發、處理、合并都可并行處理，明顯提高了處理效率。

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

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

本方案缺點：

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

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

本方案難點：

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

2、如何分發、并行處理及匯總數據。