1、中等規模海量數據處理實例分析王斌BI 組2009-12-04內容o 項目簡介o 流程o 演化過程o 遇到的若干問題o 支撐技術o 總結項目簡介o 本項目通過分析用戶訪問標題的log日志文件，提取出用戶的喜好，進而為廣告投放提供精準支持o 此項目屬于web使用挖掘的一個應用項目簡介o log數據n 單日壓縮文件約為10G，壓縮比約為8n 需要整合一個月的數據n 總共約2T3T數據o 用戶數量n 約1.5億o 目前一個月活躍標題數量n 約1400萬，支持3000萬標題數量項目簡介o 硬件環境n 4 CPUn 4G內存o 編程環境n c+n vim+ctags+cscopen g+n gdb流程演化

2、過程項目開始前（2008.04）o動手做程序前，有過類似的經驗，但所處理的數據量不大。當時具備的知識如下：n診斷性能瓶頸n多線程技術n定長技術n二進制技術n抽取公共信息n緩存技術n雙備份技術n有一定的數據結構和算法基礎演化過程項目初期（2008.05）o目標：簡單流程開發完畢，優化以后再做o遇到的主要問題：n計算所的開源詞庫錯誤百出n有道的詞庫軟件因為版權問題不能用演化過程項目進展中（2008.06）o 目標：做一些優化工作o 遇到的問題：n計算所的開源詞庫性能非常差，百萬標題需要一千秒n分詞本身帶來不少誤差問題n內存碎片問題o 探索：n利用kmp算法+trie樹來解決關鍵詞的提取演化過程項目

3、進展中（2008.0708）o 通過不斷地探索，關鍵詞提取已經有了方案，不過偶然發現前人已經解決了關鍵詞提取的問題，而且解決地更好，就采用了前人的算法-多模式串匹配算法演化過程項目進展中（2008.0910）o 遇到的問題：n運行時間越來越長，甚至到了不可用的地步n存儲量也越來越大o 解決方案：n原來文本文件方式改造成二進制文件方式n采用縮短用戶id長度和標題id長度的策略減少計算時間和存儲量n信息采用定長方式演化過程項目進展中（2008.1112）o 遇到的問題：n二進制文件越來越大n標題越來越多，導致性能惡化n耗用的內存也越來越大，接近3G限制o 解決方案：n分割大文件n淘汰很久沒有訪問過

4、的標題n查詢大數據量時用hash，小數據量用紅黑樹n及時釋放不再需要的內存遇到的若干問題o 如何快速處理如此多的數據？o 如何快速提取關鍵詞？o 海量信息如何保存？o 如何解決大內存問題？o 標題如何淘汰？o 如何解決高容錯？o 如何快速發現問題？支撐技術o診斷性能瓶頸o數據結構和算法o多線程技術o磁盤IO技術o定長技術o位技術o二進制技術o數學概率o抽取公共信息o緩存技術o裁剪技術o內存池技術o雙備份技術o調試技術診斷性能瓶頸o 主要內容n利用gprof來查找性能瓶頸（最好是單線程的程序）n80%的執行時間花在20%的代碼上n舉例：能夠找到性能比較差的函數o 主要用來解決如下問題n快速處理海

5、量數據數據結構和算法o思想n不同規模的數據量，用不同的數據結構和算法n減少不必要的操作o主要用到的數據結構和算法n多模式串匹配算法 (log處理過程中非常有用)nnth element算法nHash （數據量大時）n紅黑樹（中小規模用）n各類排序算法n倒排索引n外部排序o主要用來解決如下問題：n快速處理海量數據n快速提取關鍵詞多線程技術o主要技術點n并發執行，充分利用4 CPUn流水線技術o主要用來解決如下問題n快速處理海量數據磁盤IO技術o 主要技術點n磁盤讀要順序讀，順序寫（性能比隨機讀快10倍左右）n磁盤讀寫磁盤要分開，一個讀磁盤，一個寫磁盤n分割大文件（大文件性能一般比小文件差）n壓縮

6、技術（log文件都是壓縮文件）n緩存（上一頁，有緩存，不是逐個記錄讀取的）o 主要用來解決如下問題n快速處理海量數據n高容錯定長技術o 主要內容n每個標題長度是不一樣的，每個url長度也是不一樣的n不定長需要轉變為定長n主要采用md5技術（md5轉換程序每秒處理能力在百萬級別左右）o 主要用來解決如下問題n快速處理海量數據n海量信息保存n解決大內存問題位技術o 主要思想n充分分析數據的特性，以位為單位，而不是字節為單位來存儲信息。o 主要用來解決如下問題n快速處理海量數據n海量信息保存n解決大內存問題位技術舉例假如用戶訪問17個站點信息，每個站點的信息值在07之間常規做法：用1個字節來保存每個

7、站點的信息，因此需要17個字節(178bits=136bits)來保存用戶訪問站點的信息新系統做法： 由于每個站點的信息值在07之間，所以可以用3個位信息即可保存。需要的空間為173=51bits ，用7字節(56bits)即可保留用戶訪問站點的信息。本系統采用了這種方式后僅僅對于原用戶細分系統的2千萬用戶數據，只需600M的內存（原系統1.7G），只占到原系統的35%。二進制技術o主要內容n二進制的處理速度遠遠超過文本形式n可以大大降低空間存儲量n舉例：保存用戶訪問過的標題信息o主要用來解決如下問題n快速處理海量數據n信息如何保存n解決大內存問題數學概率o 主要內容n犧牲精確度換取空間的低存

8、儲量n這是降低空間占用量的關鍵技術之一o 主要用來解決如下問題n快速處理海量數據n信息如何保存n解決大內存問題數學概率原來用戶id：00000072c4c06dafc0091249c960bd10現在id：00000072c4c06d 假設用戶數量為7.2億，改造后的用戶重合率大約為1/7.2億，也即7.2億用戶中才有一個用戶id跟其它用戶id重合在內存中保存id信息，可以用8字節，其中7個字節保存用戶id，1字節保存用戶其它信息，如權重信息占其中的5個位信息抽取公共信息o 主要內容n把需要大量重復訪問的信息抽取出來，降低空間利用率，提高信息處理的效率n舉例：用戶訪問很多標題，而大多數情況下，

9、每個標題會被很多用戶訪問，這樣我們可以提取標題信息為公共信息o 主要用來解決如下問題n快速處理海量數據n海量信息的保存n解決大內存問題緩存技術o 主要內容n需要把已經處理過的內容保留下來，這樣下次訪問就無需重復計算n舉例：舊標題所對應的有效關鍵詞列表和用戶訪問過的數據o 主要用來解決如下問題n快速處理海量數據n海量信息的保存裁剪技術o 主要內容n把不重要的內容去除掉，比如過時的標題n把不含關鍵詞的標題去掉o 主要用來解決如下問題n標題淘汰問題n快速處理海量數據n解決大內存問題內存池技術o 主要內容n海量數據處理中，容易出現小內存問題，進而導致虛擬內存耗盡n分配內存塊，一次分配，逐步消化，一次回收n盡量少用STL容器，特別是vectoro 主要用來解決如下問題n解決大內存問題雙備份技術o 主要內容o 主要用來解決如下問題n高容錯n也有助于提高io訪問速度調試技術o 主要內容nstracencore dump技術n多線程調試技術ngdb 調試技術n大量錯誤在小數據量中解決n構造數百個自動化測試用例o 主要用來解決如下問題n快速發現問題或bug采用上述技術的結果o 性能比最初提升至少100倍o 存儲量至少降低10倍總結o 充分利用分析數據的特性，利用海量處理的