題目

場景描述

某電商平臺的服務器每天會產生約10億條訪問日志，每條日志包含用戶ID、訪問URL、訪問時間等信息（每條日志約100字節）。現在需要設計一個系統，解決兩個核心問題：

1. 找出當天所有僅出現過一次的URL（即獨立訪問的URL）。
2. 統計每個URL的訪問次數，并按訪問量從高到低排序，輸出Top 100的URL。

要求

• 系統需處理每日新增的10億條日志，原始日志存儲在分布式文件系統（如HDFS）中。
• 服務器集群資源有限：單節點內存最多32GB，可使用的節點數量不超過10臺。
• 需考慮處理效率（盡量縮短計算時間）和容錯性（如節點故障時如何處理）。

問題

1. 請設計一個解決方案，闡述核心思路和關鍵步驟。
2. 如果內存有限（如單節點僅8GB），如何優化方案避免OOM？
3. 如何提高系統的處理速度？可以從算法、數據結構、分布式策略等角度分析。
4. 若需實時統計（如每5分鐘更新一次Top 100 URL），方案需要做哪些調整？

考察點

• 大數據處理思維（分治、哈希分片）
• 內存優化能力（數據壓縮、磁盤緩存）
• 分布式系統設計（任務拆分、容錯機制）
• 算法與數據結構選型（哈希表、堆、布隆過濾器等）
• 實時與離線處理的差異理解

這道題結合了實際業務中的日志處理場景，既考察基礎算法能力，也關注工程落地時的資源限制與性能優化，能有效區分候選人的綜合技術水平。

解答

思考

1. 10億條日志，平均每條100字節，也就是總共100GB數據。如果只存URL統計值，放10臺機器應該內存勉強夠，這里用hash分片的方式，即URL哈稀按10取模，分到10臺機器上統計，完后假設夠就能直接統計全量URL出現次數，然后再用小根堆，求出Top 100個url。統計時間復雜度是O(n)，小根堆排序時間復雜度是O(nlog100)。
2. 假設不夠，也算回答下面32G改為8G的情況，可以hash分片分為100份，放入100個小文件中，然后再分別基于這100個小文件，計算只出現一次的URL和TOP100，因為是hash分片的，同一個url不可能出現在兩臺機器上，所以最后匯總100個分片的數據即可。
3. 假如離線統計變成了實時統計，一天100G，平均5分鐘是350M，如果不考慮絕對精確，那么離線數據統計TOP 1000，然后加上5分鐘新數據的URL的統計，合并取出TOP100。如果要精確計算，那么有可能TOP 1001的那個URL加上5分鐘內的新數據，剛好達到top100，那么就漏統計了。但單純目前的10臺機器很難做到精確統計，可以引入Redis的Zset維護所有url的統計值，通過zrange統計top100.
   針對日志去重與統計系統的設計問題，解決方案需結合分治思想、分布式處理、內存優化三大核心思路，同時兼顧效率與容錯性。以下是具體方案拆解：

一、核心解決方案（基礎版，單節點32GB內存、10臺節點）

1. 整體架構選型

采用**“分布式離線計算框架”（如MapReduce/Spark）作為核心引擎，依托分布式文件系統（HDFS）存儲原始日志，利用框架的并行計算能力和容錯機制處理10億條日志。
核心邏輯分為“分片預處理→本地計算→全局匯總”**三階段。

2. 關鍵步驟詳解

（1）數據分片：解決“數據量大，單節點處理不了”的問題

• 分片依據：按URL的哈希值分片（如hash(URL) % 10，10為節點數），確保相同URL被分配到同一節點。
  原理：相同URL的哈希值相同，會被路由到同一個節點，避免“跨節點統計同一URL”導致的計數錯誤。
• 分片效果：10億條日志平均分配到10臺節點，每節點處理約1億條（約10GB原始數據），單節點32GB內存可承載。

（2）本地計算：單節點內完成計數與初步篩選

每臺節點對分配到的分片數據執行以下操作：

• 步驟1：URL去重與計數
  用哈希表（如Java的HashMap<String, Integer>）存儲“URL→訪問次數”映射：

• 遍歷分片內的每條日志，提取URL，在哈希表中累加計數（若不存在則初始化為1，存在則+1）。

• 優化：用“URL的哈希值”代替原始URL作為key（如將URL通過MD5壓縮為16字節哈希值），減少內存占用（原始URL可能很長，哈希值固定長度更省空間）。

• 步驟2：篩選“僅出現一次的URL”
  遍歷本地哈希表，篩選出value=1的URL，暫存為“本地獨立URL列表”。

• 步驟3：計算“本地Top 100 URL”
  對本地哈希表的(URL, 次數)按次數降序排序，取前100條作為“本地Top 100”（用堆排序效率更高：維護一個大小為100的小頂堆，遍歷計數時動態更新，時間復雜度O(n log 100)）。

（3）全局匯總：合并各節點結果

• 匯總“獨立URL”：收集所有節點的“本地獨立URL列表”，合并后即為全局“僅出現一次的URL”（因相同URL已被分片到同一節點，無需去重）。
• 匯總“全局Top 100”：
  收集所有節點的“本地Top 100”（共10×100=1000條），用一個大小為100的小頂堆對這1000條數據重新排序，最終得到全局Top 100 URL。

（4）容錯機制

• 依賴分布式框架的原生容錯：若某節點故障，框架會自動將其任務分配給其他節點重新處理（需確保原始日志在HDFS中有多副本，避免數據丟失）。
• 中間結果持久化：將本地哈希表、本地Top 100等中間結果寫入磁盤（如HDFS臨時目錄），避免節點重啟后重復計算。

二、內存優化（單節點僅8GB時）

當單節點內存降至8GB，1億條日志的哈希表可能超出內存（假設每條URL+計數占32字節，1億條需3.2GB，但哈希表負載因子會導致實際占用更高，可能達6-8GB），需進一步優化：

1. 二次分片（分片內再拆分）
   對單節點的1億條日志再次按hash(URL) % 10拆分（即總分片數10×10=100），每批處理1000萬條（約1GB），處理完一批后釋放內存，再處理下一批。

2. 使用磁盤輔助存儲
   用嵌入式KV數據庫（如LevelDB/RocksDB）替代內存哈希表：

• 遍歷日志時，將URL的計數實時寫入磁盤數據庫（key=URL哈希值，value=次數），利用數據庫的磁盤+內存混合存儲特性避免OOM。
• 優勢：LevelDB支持按key排序，后續篩選獨立URL和Top 100時可按序遍歷，效率高于隨機讀寫。

3. 數據壓縮

• 對URL進行字典編碼：將重復出現的URL映射為整數ID（如“www.xxx.com”→1，“www.yyy.com”→2），用ID代替URL存儲，減少key的長度。

三、提速方法（縮短計算時間）

1. 算法與數據結構優化

• 計數階段：用數組+哈希函數代替哈希表（若URL哈希值可映射到整數范圍），減少哈希沖突帶來的開銷。
• Top 100計算：用小頂堆（而非全量排序），將局部排序時間從O(n log n)降至O(n log k)（k=100）。

2. 分布式并行優化

• 增加分片數：將10億條日志拆分為更多分片（如100片），讓10臺節點并行處理10片/節點，提高CPU利用率（避免單節點處理1億條時CPU空閑）。
• 減少數據傳輸：僅傳輸“本地結果”（獨立URL列表、本地Top 100），而非原始日志（原始10GB/節點，結果可能僅10MB/節點）。

3. 硬件與框架調優

• 用Spark替代MapReduce：Spark基于內存計算，中間結果保存在內存（非磁盤），迭代計算速度快3-5倍。
• 啟用數據預讀取：利用HDFS的“預取機制”，在處理當前分片時提前加載下一分片數據到內存緩存。

四、實時統計（每5分鐘更新一次）

離線方案適合T+1處理，實時統計需切換為流處理架構（如Flink/Kafka Streams），核心調整如下：

1. 數據接入
   日志通過Kafka實時流入系統（Kafka作為消息隊列，緩沖峰值流量），每5分鐘劃一個“滾動窗口”。

2. 實時計數

• 用Flink的KeyedStream按URL分組，在窗口內累加計數（底層用狀態后端存儲計數，支持 RocksDB 持久化避免狀態丟失）。
• 窗口結束后，觸發“本地Top 100”計算，結果寫入全局狀態（如Redis）。

3. 全局Top 100更新

• 維護一個全局Redis有序集合（ZSet），存儲所有URL的累計次數，每5分鐘從各窗口結果中合并更新ZSet，再用ZREVRANGE取前100。
• 優化：用“滑動窗口”代替滾動窗口（如統計最近5分鐘，每1分鐘更新一次），減少結果抖動。

4. 處理亂序數據
   日志可能因網絡延遲亂序到達，需設置水印（Watermark）：允許數據遲到30秒，超過后不再計入當前窗口，平衡實時性與準確性。

總結

該方案通過“分治+分布式”解決大數據量問題，通過“磁盤輔助+二次分片”優化內存，通過“流處理框架”支持實時統計，兼顧了效率、容錯性和資源限制，符合實際生產場景的工程落地需求。