前几天帮朋友做模拟面试时又遇到了这道“经典中的经典”100G 的访问日志每行只有一个 IP 地址内存只有 4G怎么统计出访问次数最多的前 10 个 IP。第一次见到这道题的人一半以上会条件反射式地给出“用字典计数再排序取前 10”的答案。这个回答本身没错但只要你真的拿 100G 数据去跑第一步就会把 4G 内存撑爆。这篇文章想把整套解法从头到尾拆开讲清楚先算清楚数据量和内存账再讲哈希分片为什么是核心然后落到 Counter、堆、多路归并这些具体实现最后聊聊面试官最可能追问的变体。无论你是在准备大厂面试还是临时接手一个几十上百 G 的日志分析任务照着这套思路走基本不会跑偏。1. 这道题的第一反应就是坑为什么会内存溢出1.1 100G日志的真实规模六七十亿行很多人对“100G”没有体感我先帮你把数量级算明白。100G 按 1024 进制算是 107,374,182,400 字节。每行一个 IPv4 地址最短的0.0.0.0\n是 9 字节最长的255.255.255.255\n是 16 字节。考虑到真实日志里 IP 大多在 12 到 15 位字符之间再加上换行符平均按 14 到 16 字节估算是合理的。这样一算总行数大约在 67 亿到 77 亿之间。哪怕你机器每秒能处理 100 万行日志光把文件顺序读完就需要 1.8 小时以上这还没算任何后续操作。换句话说这道题在时间上就不是“几秒钟出结果”的题目它背后要求的是“你能不能在合理时间内、有限内存下做出来”。还有个容易忽略的推论就算整个 100G 文件里只有 100 万个不同的 IP每个 IP 平均也会出现 6700 次。这意味着数据里存在大量重复但重复读不意味着可以省内存——只要你的统计容器是放在内存里的它关心的是“不同 key 的数量”而不是总行数。1.2 全部装进字典为什么必挂用 Python 的dict统计词频理论上完全可行问题出在内存膨胀率上。在 CPython 3.11 的 64 位环境下一个dict条目大致由三部分构成key 对象、value 对象、哈希表槽位。key 是一个短字符串对象本身大约 49 字节value 是计数用的int大约 28 字节哈希表里每个槽位包含 hash、key、value 三个指针24 字节再算上哈希表的负载因子和整体内存池开销平均每个 IP 条目大约占 100 字节以上。如果你觉得“才 100 字节”那我换一种说法不同 IP 达到 1000 万时计数器本身就要占 1GB 以上当不同 IP 达到 5000 万时轻松超过 4GB。极端情况下如果全部 2^32 个 IPv4 地址都出现过需要约 430GB 内存——这已经不是 Python 的问题任何单机内存方案都扛不住。所以“直接读入大字典统计”在被题目限定的 4G 内存下从第一行代码就已经宣告失败了。当然实际日志中不同 IP 很可能只有几十万到几百万个用字典能装下但这属于“数据碰巧没超限”不是方案正确。面试题给出的 100G 和 4G 就是人为构造的一个压力阈值目的就是逼你放弃“一把梭”。1.3 面试官到底在考什么这道题表面上考的是“统计 Top10”实际上考的是海量数据下的分而治之思想。面试官想从你嘴里听到的大概是这几个关键词能估算输入规模知道 100G 大约是几十亿行知道内存瓶颈在哪里并且能算出来“全量字典为什么不行”能设计出一个把大文件拆成可独立处理的小文件的方案能意识到哈希均匀性、文件句柄、磁盘 IO 这类工程细节最后还要说明归并逻辑为什么是正确的。如果你的回答里能自然出现“哈希分片”“流式处理”“外部归并”“小顶堆”这些词基本上已经站在了合格线以上。如果还能解释清楚“为什么每个分片只要取 Top10 就足够”那就属于加分项了后面我会专门讲这一点。2. 哈希分片把装不下变成装得下的关键设计2.1 为什么必须是确定性哈希而不是随机分片既然一个字典装不下那就把大文件切成几十个、几百个小文件每个小文件单独统计最后再合并结果。这个思路本身很简单但分片方式有一个前提同一个 IP 每一轮都必须被分到同一个桶里。这就要用确定性哈希而不是随机分片或按行轮转。如果按行号轮转分片同一个 IP 会散落在多个分片文件里每个分片只统计到它的部分计数最后合并时还得跨文件归并同一个 IP 的总次数。增加复杂度是小事关键是容易漏计或重复计。使用hash(ip) % N或等价方案后同一 IP 一定会落到同一个分片每个分片内统计到的次数就是该 IP 的完整计数。这个性质非常关键它保证了后面“每分片取 Top10 再合并”仍然是精确结果。顺便说一句如果你用的是随机抽样那种思路就更不对了。抽样适合估算 TOP 量级不适合精确 Top10因为高频 IP 可能在样本中正好被漏掉。2.2 分片数怎么定把内存账算清楚分片数 N 不能拍脑袋定它取决于两个约束一是每个分片统计时的内存必须可控二是分片文件太多会带来 IO 和文件句柄压力。先把内存账算出来。设总行数约为 R 70 亿。哈希均匀时每个分片的行数约为 R/N。最坏情况是某个分片内所有行都是不同的 IP这样Counter的条目数就是该分片的行数占用内存约100 × R/N字节。我们希望在统计任意一个分片时计数器内存控制在 2.5GB 到 3GB 以内因为还要给 Python 解释器、文件缓冲和系统留出余量。要求100 × 70亿 / N ≤ 25亿解出来N ≥ 280。所以分片数至少在几百这个量级。实际工程中我一般取 512 或 1024N 1024 时每个分片文件大约 100MB即使分片内 700 万行全部是不同的 IP计数内存也就 700MB 左右相当安全。如果你想再留余地取 2048 也可以但后面要说文件数量并不是越多越好。2.3 Python内置hash()为什么不能直接用如果现场写代码很多人会顺手写成hash(ip) % N。面试时这么写勉强能过但工程上这是一个隐患Python 内置的字符串hash()使用了随机化种子也就是PYTHONHASHSEED。同一个 IP 在进程 A 和进程 B 里算出的哈希值不一样。这意味着如果你把“分片”和“统计”拆成两个独立程序来跑第二次运行时根本没办法保证同一个 IP 进同一个分片。就算你把整条流程塞在同一个 Python 进程里只要某次重启或换机器分片结果就不可复现了。对于海量任务来说可复现性是非常重要的不然出了问题都没法排查。更稳妥的做法是用标准库自带的确定性哈希比如zlib.crc32(ip.encode(utf-8)) % N或者hashlib.md5(ip.encode()).digest()转整数再取模。我用下来最顺手的是crc32分布足够均匀速度又比 md5 快。如果确认数据全是 IPv4还有一个更快的方案是socket.inet_aton(ip)把点分十进制转成 4 字节整数再做取模。它顺带还能校验 IP 格式遇到非法 IP 会抛异常方便你提前发现问题。2.4 文件句柄和IO压力1024个文件不是免费午餐分片实现最直观的做法是遍历大文件对每行算好分片号然后打开对应的分片文件追加写入。但这里有个非常实际的坑——同时打开的文件描述符数量。Linux 下默认的ulimit -n通常是 1024如果你的分片数是 1024再算上标准输入输出和日志文件本身很容易直接触发Too many open files。所以要么把分片数降到 256 或 512要么在程序启动时用resource.setrlimit把上限提高。面试现场讲思路时可以只说“要注意文件描述符上限”但真要写代码落地这一步躲不开。IO 压力也很现实。分片一遍 100G 文件意味着除了读 100G还要额外写 100G 的分片数据。机械硬盘顺序读 100G 可能只要几十分钟但随机写几百个小文件的多个位置会慢很多。我自己的做法是给每个分片维护一个写缓冲攒一批再落盘避免每写一行就触发一次系统调用。还有一点分片文件不要每次都以追加模式反复打开关闭最好让它们一直开着、最后统一 close但要注意前面的句柄限制。3. 每个分片内的Top10统计Counter、堆与内存水位线3.1 逐行流式读取绝不readlines处理这种量级的文件时最基础也最容易翻车的点是读取方式。with open(path) as f: for line in f这种写法在 Python 中采用的是惰性迭代一次只读一行进内存可以放心用。但绝对不能写f.readlines()或f.read()——前者会把整个文件按行切成一个列表后者直接把整个文件内容读进来对 100G 文件来说执行到一半内存就炸了。统计单个分片时我的标准代码长这样from collections import Counter def count_shard(shard_path: str, top_k: int 10): counter Counter() with open(shard_path, r, encodingutf-8, errorsignore) as f: for raw_line in f: ip raw_line.strip() if ip: counter[ip] 1 return counter.most_common(top_k)注意raw_line本身带着换行符strip()必须做errorsignore是防止某个分片文件里有异常字节导致整个任务中断。真实日志里偶发的乱码真的很常见多写一个参数能省去半夜爬起来看栈的麻烦。3.2 为什么most_common内部用堆而不是全排序一个分片文件大约 100MB 到 200MB里面不同 IP 最多也就几百万个。全量排序O(M log M)当然也能跑但没必要。Counter.most_common(n)的底层实现就是heapq.nlargest(n, counter.items(), keylambda x: x[1])复杂度是O(M log n)。当 n 10 时log n基本是常数明显比全排序划算。同时它只会维护一个大小为 10 的堆额外内存几乎可以忽略。如果你自己写sorted(counter.items(), keylambda x: x[1], reverseTrue)[:10]虽然也能拿到结果但会额外生成一整份排序后的列表内存占用更高没有必要。更关键的是我们要养成“只维护 TopK”的思维习惯。这个思路在归并阶段还会再用一次1024 个分片的 Top10 要合成全局 Top10同样不需要把所有计数全搬进内存。3.3 分片过大时的二次分片spill策略哈希均匀是理想情况真实数据不一定配合。可能某个分片文件特别大或者分片内不同的 IP 特别多统计到一半Counter已经占了 1.5GB再继续下去就 OOM 了。这时候不能硬撑最实用的方案是“二次分片”把当前这个分片按另一个确定性哈希函数再切成若干子分片比如 64 个然后分别统计每个子分片取子分片 Top10最后归并得到这个分片的 Top10。这个思路本质上是 MapReduce 里的 spill 机制只不过我们手动实现。二次分片时用的哈希函数可以和第一次不同因为它只负责把一个分片继续切小。但必须保证同一个 IP 经过二次哈希后仍然只落在一个子分片里也就是说仍然用确定性哈希。另一个偷懒的办法是第一次就直接把 N 取到 2048让每个分片天生就足够小代价是文件变多、IO 更碎。实际项目中我倾向于先用大分片数同时监控每个分片大小一旦发现倾斜就补一道二次分片而不是一开始就盲目追求极端小的分片。3.4 把IP转成整数能省多少内存如果日志确定全部是 IPv4可以把192.168.1.1用socket.inet_aton(ip)转成 4 字节再作为Counter的 key。一个int对象在 Python 里大约 28 字节比 49 字节左右的短字符串 key 省了将近一半更重要的是整数哈希和比较的速度比字符串快批量插入时性能提升肉眼可见。整个条目从约 100 字节降到 80 字节上下四舍五入能省两成内存。IPv6 也类似可以用ipaddress.ip_address(ip).packed转成 16 字节的 bytes 作为 key。标准库就够用完全不需要引第三方依赖。4. 多路归并1024份Top10如何合成最终Top104.1 一个常被忽略的结论每片Top10已经足够这里有一个让不少人觉得反直觉、但数学上非常干净的结论在确定性哈希分片的前提下全局 Top10 中的每一个 IP必然也出现在它所属分片的 Top10 中。证明很简单如果某个 IP 在全局排第 k 名k ≤ 10那么整个数据集里最多只有 k-1 个 IP 的访问次数比它高。而由于哈希分片的特性这些比它高的 IP 也都和它在同一个分片里。所以它在自己分片内的排名最多是第 k 名不会超过 10当然会被该分片的 Top10 包含。这意味着把 1024 个分片的 Top10 拿来做 merge得到的不是近似值而是精确答案。哈希分片最大的好处不只是“内存装得下”还有“归并不会错”。反之如果用随机分片或按行均分这个结论立刻失效因为同一个 IP 的计数被拆在多处最终必须跨分片合并才能得到真实频次复杂度完全不一样。4.2 用大小为10的小顶堆合并所有候选每个分片 Top10 有 10 个(ip, count)1024 个分片总共最多 10240 个候选条目。这个量级说实话直接全排也行但面试中展示一下堆的用法会更出彩。import heapq def merge_topk(shard_top_lists, k10): heap [] # 小顶堆存 (count, ip) for top_n in shard_top_lists: for ip, cnt in top_n: if len(heap) k: heapq.heappush(heap, (cnt, ip)) elif cnt heap[0][0]: heapq.heapreplace(heap, (cnt, ip)) return sorted(((ip, cnt) for cnt, ip in heap), keylambda x: x[1], reverseTrue)堆里存(count, ip)Python 元组比较会先按 count 排相同再按 IP 字符串排没有副作用。heapreplace比先pop再push效率略高写出来也更清爽。最后再还原成(ip, count)并倒序输出就是最终的前 10 名。如果你不想手写堆直接heapq.nlargest(10, all_items, keylambda x: x[1])也能得到同样结果。但建议至少在脑子里把这个过程过一遍因为面试官很可能追问“这里的时间复杂度是多少”“为什么用小顶堆而不是大顶堆”。4.3 潜在的重复处理与取舍最容易出问题的地方恰恰是自认为没问题的地方。如果某个 IP 因为分片函数写错而出现在多个分片里归并代码会把它当成多个不同的(ip, count)记录直接导致结果错误。这也是上一章反复强调“确定性问题”的根本原因。另外如果题目要求输出严格有序的前 10 名而第 10 名存在并列次数怎么处理一般 TopK 问题里任选其一都算正确。如果面试官坚持要确定性的输出可以加一个二级排序键比如 IP 字典序保证多次运行结果一致。数据集越大这类边界细节越容易成为面试分水岭。5. 代码落地中的隐藏坑从正确思路到可运行实现5.1 用crc32/socket.inet_aton做分片键我实际写分片函数时会用一个兜底版本import zlib import socket def shard_id(ip: str, shard_count: int) - int: try: ip_bytes socket.inet_aton(ip) except OSError: ip_bytes ip.encode(utf-8) return zlib.crc32(ip_bytes) % shard_count这里先把 IPv4 转成 4 字节再用crc32做分片。为什么不直接拿 IP 的整数取模因为 IPv4 地址存在网络号、运营商地址段、地区聚集等规律直接取末几位或整体取模在很多真实数据集上会出现分片倾斜。crc32能把这种聚集规律打散让数据更均匀。题目里的日志格式很干净直接用inet_aton也是可行的但倾斜风险会略高。5.2 异常行、编码、句柄限制100G 日志是现实世界的数据绝不是教科书里的干净文本。我见过的问题包括空行、行首行尾带空格、一行里除了 IP 还有时间戳和 User-Agent、某些行是 IPv6、文件编码不是 UTF-8、甚至中间夹杂乱码。如果题目明说“每行记录一个 IP”可以先按最简方式处理但代码里至少要strip()并跳过空行。如果一行有多个字段改成取第一列parts raw_line.split() ip parts[0] if parts else 编码建议统一用encodingutf-8, errorsignore宁可让个别乱码行变空行也不要让一个异常字节毁了整个任务。文件句柄限制前面讲过这里再强调一次分片数不是越大越好。N 1024 时1024 个文件同时打开已经摸到 Linux 默认文件描述符上限边缘何况进程本身还要打开原日志和标准输入输出。要么减小 N要么调ulimit二选一。5.3 先造一个小文件验证流程写这种海量处理逻辑千万别直接拿 100G 数据上你连错在哪都看不出来。我的习惯是先造一个 10MB 左右的样例故意塞一些边界数据空行、带端口号的1.2.3.4:8080、IPv6、几个重复度极高的热门 IP、接近并列的频次然后跑完整流程。关键是对照验证先用普通字典统计这个小文件的全量 Top10作为基准再造几个可能触发 bug 的场景确认分片归并的结果和基准完全一致。哈希函数写错、分片号范围算错、归并时漏文件这些坑在小样本上会立刻现出原形。等小样本跑通再放大到 100G这时候你才敢说结果可信。5.4 如果换成生产环境还要考虑什么如果只是单机偶尔处理一次 100G 日志坦白说我大概率不会手写整套分片逻辑而是直接用 GNU coreutilssort -T /tmp --parallel4 -S 2G access.log | uniq -c | sort -rn -S 2G | head -10sort本身会在内存放不下时转外部归并排序-S指定内存缓冲区上限-T指定临时目录。这套命令代码量最少也经过了几十年考验。如果日志分散在多台机器或者你需要一个可复用的统计任务直接上 Spark 的reduceByKey或者导进 ClickHouse 一类的 OLAP 引擎都比自己写分片轮子省心。Python 手写分片更合适的场景是没有现成组件、又要精确统计的单机任务以及面试现场。分清“理论方案”和“生产工具”的边界本身就是经验的一部分。6. 面试官的连环追问这道题的扩展与变体6.1 如果日志全是IPv4能不能用更少内存有人会想IPv4 总共只有 2^32 个值能不能开一个定长数组来计数一个 IP 用 4 字节计数器数组就要 17GB依然超内存。如果只记录“某个 IP 是否出现过”用 1 bit 只需要 512MB但这种方法拿不到频次也就做不了 TopK。比较合理的优化方向是先用哈希分片把大文件切小让每个分片内的 IP 值域变窄再用定长数组局部统计。比如分到 1024 个分片后每片大约 1000 万行不同 IP 数量远小于 2^32此时把 IP 转成整数后可以直接在数组上累加省掉dict的哈希表开销。这个方案比Counter更省内存但代码复杂度更高。6.2 允许近似误差Count-Min Sketch是什么如果业务能容忍一点误差可以用 Count-Min Sketch。它本质是一个宽度为 w、深度为 d 的二维计数器数组配合 d 个哈希函数。每来一个 IP就在 d 个位置各自加一查询时取这 d 个计数器里的最小值作为该 IP 的估计频次。因为不同 key 可能在同一计数器上叠加估计值永远偏大或等于真实值不会偏低。内存可以压到几十 MB非常适合超大规模流式日志。但要注意Count-Min Sketch 提供的只是“查某个 IP 有多高频次”的能力你要拿它做全局 TopK还得额外维护一个堆来保存候选 IP。否则日志流完了你还是不知道谁是前 10 名。这道题想在面试里拿高分可以把这个方案作为“如果我允许近似”的补充而不是主答案。6.3 如果访问日志每行不止一个字段怎么改题目只给了“每行一个 IP”但真实日志几乎都是IP 时间 请求路径 User-Agent这种格式。改法其实很简单分片键取第一列 IP其余字段按需求处理。如果想统计“每个 IP 的访问次数”丢弃其他字段就行如果想统计“每个 IP 的流量总和”那就以 IP 为 key把请求体大小累加为 value。哈希分片的核心框架不用变唯一要搞清楚的是“分片键”和“统计键”的关系。只要统计键是 IP确定性哈希就依然有效归并逻辑也完全不变。这类追问通常是为了看你能不能把框架迁移到变体场景而不是死记硬背一个答案。最后说一点我自己的体会这道题在实际面试中能连续讲清楚“分片数量为什么是 512 或 1024”“哈希分片为什么不能随机”“每分片取 Top10 为什么够用”这三点的人我遇到的真的不多。绝大多数候选人停留在“字典计数”或“切文件排序”这一层能聊到第二层已经算不错了。你要是能把精确性证明、二次分片、crc32、文件句柄这些细节都顺带讲出来这道题基本就稳了。准备面试不需要背答案把每个“为什么”过一遍这套思路换到任何海量 TopK 场景里都能直接用。