题目

场景描述

某电商平台的服务器每天会产生约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秒，超过后不再计入当前窗口，平衡实时性与准确性。

总结

该方案通过“分治+分布式”解决大数据量问题，通过“磁盘辅助+二次分片”优化内存，通过“流处理框架”支持实时统计，兼顾了效率、容错性和资源限制，符合实际生产场景的工程落地需求。