(有意思的项目)--快速统计大文件(10 亿行)中的数据需要的技术是

[lsk569937453]

刚才在 github 上看到一个有意思的项目 https://github.com/gunnarmorling/1brc 。项目是开放式的，任何人都可以提交，主要是统计 10 亿行数据。

目前排名第一的提交是
```
https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_royvanrijn.java
```
该算法的注释如下:

```
* Initial submission: 62000 ms
* Chunked reader: 16000 ms
* Optimized parser: 13000 ms
* Branchless methods: 11000 ms
* Adding memory mapped files: 6500 ms (based on bjhara's submission)
* Skipping string creation: 4700 ms
* Custom hashmap... 4200 ms
* Added SWAR token checks: 3900 ms
* Skipped String creation: 3500 ms (idea from kgonia)
* Improved String skip: 3250 ms
* Segmenting files: 3150 ms (based on spullara's code)
* Not using SWAR for EOL: 2850 ms
* Inlining hash calculation: 2450 ms
* Replacing branchless code: 2200 ms (sometimes we need to kill the things we love)
* Added unsafe memory access: 1900 ms (keeping the long[] small and local)
```
感觉还挺有意思的，我其实想知道
1.memory mapped files 会不会把内存干爆阿。
2.unsafe memory access 为什么这么快，会造成内存泄露？
3.把内存限制一下会不会更有挑战点。

[billccn]

memory mapped files 就是为了不把文件在内存里复制一份，绝不可能把内存干爆（ 32 位机除外）。
我没看源码，但是 unsafe memory access 可能是配合以上 memory mapped files 使用。Java 里正常的 NIO API 是需要使用 Buffer 类型，这个类型需要 flip 来 flip 去，开销大，同一个 Buffer 读不同的数据类型还需要各种奇技淫巧，unsafe memory access 就相当于直接按内存地址访问，你说那个地址是什么类型就是什么类型，对于 primitive 类型是安全的。

[dhb233]

mmap 一个文件的话，是要有足够的内存的，但是 10 亿行数据大约 12G ，服务器内存还是足够的。如果内存不够的话，也可以分段多次 mmap 。
没仔细看要求，这么大的文件，主要开销都在加载文件了吧，好像也没说多少核 CPU 并发，以及 CPU 内存型号要求？
java 不太熟，就当瞎说吧。。。

[MoYi123]

要快应该得搞点 simd 吧(readme 里也提到了), 这个代码里好像也没有.

[sadfQED2]

在我这里，天王老子来了也是 scp 到离线机，然后 cat *.xxx | grep xxx ，什么内存不够？什么 cpu 不够？我 512G 128 核的离线脚本机，才不管那么多呢。

[CaptainD]

@sadfQED2 grep *.XXX file_name 就行

[iceecream]

@sadfQED2 直接 grep xxx xxfile 要快一点。

[liprais]

@dhb233 你是认真的么....mmap 什么时候需要足够的内存了?

[kuanat]

我提供一点额外的视角，有关面试的。这个活动前两天上了 Hacker News 的头条，长期看 HN 的话会注意到类似的活动还有其他语言的版本。

很早之前我司有个内存远小于数据集的版本的同类面试题，后来我主张给砍掉了。原因有两个方面，一是区分度不高，用在校招上，绝大部分人难以回答应用相关的优化，都集中在算法上；用在社招上，脱离了主要应用场景，和八股文没什么差别。另一个方面是开放式问题对面试官要求太高，对于不在预设方向的答案难以量化打分。



回到这个题目本身。

纸面上的问题有纸面上的解法，现实里的问题有现实的应对策略。可能直觉上这是个算法题，但实际上作为比赛，那就是算法、经验、工程、原理和细节多个方面的事情了。

- 经验

社招的技术面试更看重经验，但是经验这个东西很难准确量化，甚至连标准化量化的手段都很少。

我个人对于经验的定义是“分析、定位问题的能力”，这个能力是在技术之外各行各业通用的。一般来说，能准确地用技术语言描述问题，用客观可验证的手段确认问题的核心所在，那问题就已经解决了大半。

所以我在面试里更喜欢问一些类似 profiling/debug 工具、流程的细节，因为我觉得愿意用工具、数据辅助分析，水平是要高出凭印象去解决问题的，当然这是我的一家之言。

这个投递第一天上 HN 的时候，最高的讨论是有关 IO 瓶颈的，然而这个方向是错误的。即便是 HN 这个水平相对较高的社区，低水平的讨论也是大量存在的。当然现在再去看经过社区筛选的高赞结果，就比较有指导意义了。

- 工程

考虑测试环境是 Linux 而且 RAM 32GB > DATASET 12GB ，整个测试跑五次，去掉最高最低结果。除非这个程序特别离谱，占用了超过 20GB 的内存，那么绝大多数情况下，这个文件已经在 page cache 里面了。所以跑一次是 IO 问题，跑很多次就不是 IO 问题了。

一个非常 naive 的单线程实现大概是 240s 左右，不考虑其他因素的话，8 核心测试机上可以预期到 30s 的水平，观察一下榜单，基本上 60s 以内的方案都用到了并行处理。

把工程因素放到最前面说是因为它以最低的成本实现了最大程度的优化。但是这个事情作为面试题是不合适的，因为掌握多线程是最基础的，面试的目的并不是为了区分会不会多线程。

- 原理

这个场景确实存在 IO 瓶颈，但它发生在 kernel/userspace 之间，而非 RAM 与外置存储之间。用户态 read() 需要 syscall 将 kernel 管理的 page cache 里的内容复制到用户空间。这个行为越多，效率就越低。而 MMAP 机制绕开了这个 context 切换，所以提供了真正的 IO 层面的优化。

如果再观察一下榜单里的实现，基本上 30s 上下的方案里，都用了 MappedByteBuffer/FileChannel 之类的调用。换句话说，理解 MMAP 可以在多线程的基础上，稳定将结果优化到多线程的理论上限。

但这个筛选条件略微苛刻了，要么需要比较好的科班基础，要么就要恰好做过类似的业务。最终在进入技术面的数量有限的人群里，能准确回答的寥寥无几，导致缺乏区分度，反正大家都不会。（不是水平问题，而是几率问题）

再往下就是字符串处理了，我相信如果跑个火焰图看一下，30s 上下的方案性能热点应该在自定义的 parser 上。

因为这个竞赛是 Java 的，开发者更习惯的是用 Java 提供的高级抽象，相关的实现都是内存/线程安全的，但是会因为各种检查变慢。

这里不好说到底能优化多少，但是 25s 以内的实现方案里的 parser 基本都是扫描特定字符，而不是用标准库字符串方法了。10s 左右的方案几乎都考虑到了内存分配、变量重用等等技巧。但是这样非常具体的案例在面试里是没有可考察性的，除非应聘者自己主动提出了这个方案。

- 算法

终于轮到算法出场了。对于这样一个场景，算法唯一的要求就是 one pass ，意思是边读取边计算已经读取过的结果里的最大、最小和平均，而不是完全缓存之后再统一计算。

如果是求中位数的话，我觉得倒是可以拿出来讨论。我不清楚是不是有完全准确的 one pass 中位数算法。回到现实里，对于这么大的数据集，求解目标要不要完全精准有可能在数量级上影响实现效率。所以真正考察算法的时候，我会偏好问 bloom 过滤器之类的方向。

这其实也是整个问题里我相对认可的一个点，与其空泛的问 MapReduce/Streaming 之类的，完全不如考察在解决其他问题时，展现出来的触类旁通的能力。只是这个问题又太简单了，而且性能提升很小，甚至性能提升的主要来源是避免了内存分配和 GC 。

多数时候我们都希望开发者有算法基础，但是实际应用里却不希望开发者手撸算法。面试过程里考察对于算法的理解更多体现在应用层面，知道并理解常见算法的复杂度上下界，以此可以来指导方案选择。

但现实的问题是，要么大家都会要么大家都不会，就比如这个场景里，所有人都会选择 hash 结构用来存储结果，所以没有区分度。

- 细节

进入到 10s 水平，再往后的优化几乎就是抠实现细节了。

这个层面的优化，和问题场景强相关，意思就是这些手段是难以复用的。对于 C/C++ 背景的开发者比较好理解，算法逻辑是算法逻辑，数据检查/判断分支是另外的事情。所以剩下的操作无非就是：用 unsafe mmap 替代安全的映射调用，用简化的 hash 方法替代标准实现等等。

还有一个方向是向运行环境做匹配，考虑指令集、cache line 等等微观特征。考虑这里的瓶颈不在 cpu ，我怀疑 SIMD 的方案的有效性。到了这一步，看结果的话又提升了 30%，但实际生产环境可能没人会这么奔放吧。作为面试题来说，能聊到这一步应该 100% 过关了。

这里再补充个插曲，之前有别的面试官面过一个 OI 出身的应聘者，提了一个基于状态机的方案，然后当场把面试官说懵了。后来几个人回看面试记录，证明他说的方案是没问题的。这就是我说的开放性问题对于面试官的要求太高了。

行业里的开发者，一般非科班出身很少会接触状态机。主要原因是业务上需要状态机相关算法的场景非常优先，以状态机作为优化手段的可移植性又太差，除非特别核心的逻辑不得不用，很少会主动选择。



反正现在的就业环境就这样，面试造火箭。我写这些东西就是提供个思路，其实把视角拉远一点，这个具体的题目没有多少值得讨论的东西，解决问题的逻辑更加重要。

[xoyo]

之前写过一篇博客介绍过 mmap 的原理和一些优化思路
http://xoyo.space/2017/11/mmap-performance-analyzing-and-tuning/

[dhb233]

@liprais 我记得是有参数在映射的时候，可以不加载到内存里，但是访问的时候，还是要加载的啊。如果所有内容都要访问，触发缺页中断的开销更大。

[xoyo]

@dhb233 kernel 换页会有预取机制，可以通过 madvice 给出 hint ，也可以通过提前主动访问即将要读的内存，这样不仅把页表结构建好，还把数据加载进 CPU cache

[dhb233]

@xoyo 没用过这么复杂的。。。都是直接 PIN 到内存里，反正服务器内存肯定够用

[vituralfuture]

mmap 映射页面后，会正常的通过 LRU 算法淘汰暂时用不到的页面，所以 mmap 可以用来读取比物理内存还要大的文件，而一般的程序都遵循局部性原理，所以 mmap 后频繁换页的概率也比较低

[vituralfuture]

@vituralfuture 另外 mmap 还有一个机制就是懒分配，把页面的分配从调用 mmap 时推迟到了访问页面时，所以内存占用也不会一下飚很高