前阵子做用户画像系统遇到一个看起来特别简单的需求存 1 亿个用户的布尔标签。不就是 True/False 吗我当时想这有什么难的一行代码的事。结果前前后后优化了 5 版每一版都觉得“这下总完美了吧”结果上线就翻车内存和速度来回横跳最后才发现原来这么简单的问题水比我想象的深多了。今天把整个踩坑过程写出来从新手最容易写的第一版代码到最后怎么一步步被逼到写混合存储相信你看完会对“空间换时间”这句话有新的理解。第一版新手写法list 一把梭最开始我想都没想直接写了最符合 Python 直觉的代码# 1亿个用户默认都是未激活 user_active [False] * 100_000_000 标记某个用户激活了 user_active[1234567] True写完本地跑了个小测试没问题就推到测试环境了结果容器刚启动没两秒直接 OOM 被 Kill。我当时还纳闷不就是 1 亿个布尔值吗能占多少内存算完账我傻了Python 的 list 存的根本不是布尔值本身是指针。64 位系统下一个指针 8 字节1 亿个指针就是 800MB。这还没算别的光一个标签就占了快 1G 内存我有十几个标签这不得直接 10G 起步而且你以为这就完了Python 的 bool 是对象虽然 True 和 False 是单例但 list 本身的开销还不止指针算下来实际内存比 800MB 还多。翻车点把 Python 的动态类型特性想当然了高级语言帮你屏蔽了底层细节但不代表底层细节不存在。第二版用 bytearray内存直接砍 10 倍被 OOM 打醒之后我第一个想到的就是布尔值不就是 0 和 1 吗我用字节数组存啊一个字节存一个布尔值总不浪费了吧user_active bytearray(100_000_000) user_active[1234567] 1改完一测内存1 亿字节也就是 95MB 左右比第一版的 800MB 直接砍了快 90%当时觉得自己可太聪明了。这版稳稳当当跑了一周我都以为这事结束了直到产品过来说我们要做全量用户大概 10 亿个用户。我算了算10 亿字节是 950MB好像也不是不能接受但紧接着我又发现一个更致命的问题如果我的标签是“是否付费用户”这种1 亿个用户里可能只有 100 万个付费的那 bytearray 还是要老老实实占 1 亿字节其中 99% 都是 0这不是纯纯浪费吗就好像你买了一栋 100 层的楼就为了放一把椅子虽然椅子确实放下了但这楼钱花得冤不冤啊翻车点固定长度存储在稀疏数据下内存浪费是指数级的。第三版位图压缩再砍 8 倍这时候我想到了位图Bitmap。对啊一个字节有 8 位我用一位存一个布尔值不就又能省 8 倍内存# 用int当位图或者用bitarray之类的库 user_active 0 # 一个int可以存很多位 标记第n位为1 user_active | (1 1234567)算下来 1 亿位只需要 12.5MB10 亿位也才 125MB比 bytearray 又省了 8 倍当时我觉得这已经是物理极限了——一位存一个信息总不能再小了吧结果我还是太年轻了。我拿“是否付费用户”这个标签测了下1 亿用户里 100 万付费的位图占 12.5MB。但是我换个思路如果我只存那 100 万个付费用户的 ID 呢一个 ID 用 4 字节存100 万个 ID 才 4MB比位图的 12.5MB 还小 3 倍如果更极端一点1 亿用户里只有 1 万个付费用户那位图还是 12.5MB存索引只需要 40KB差了 300 多倍。哦原来位图的“一位一个”在极端稀疏的数据下还是浪费。那为什么不直接存索引呢翻车点你以为的物理极限只是“密集数据下的物理极限”数据分布变了最优解也会变。第四版稀疏存储只存异常索引说干就干我把存储方式改成了只存值为 True 的位置索引存在一个排序好的数组里。import array 初始是空数组因为默认都是False true_indices array.array(I) 标记用户1234567为True就把索引插进去保持有序 这里省略二分查找插入的代码 true_indices.append(1234567)这版在稀疏数据下简直无敌1 亿用户 100 万 True内存 4MB1 万 True内存 40KB比位图省太多了。我当时拍桌子说这总该是最终方案了吧结果上线第二天监控报警接口超时。查了半天发现问题了我另一个标签是“是否登录过”这个标签 99% 的用户都是 True只有不到 1% 的用户从来没登录过。按照稀疏存储的逻辑我要存 9900 万个索引算一下内存9900 万 * 4 字节 380MB。还记得位图占多少吗12.5MB。差了 30 倍。而且更坑的是速度位图查某个位置是不是 True直接位运算 O(1)稀疏存储要二分查找O(log n)数据量大了之后速度差了 10 倍都不止。我当时人都傻了合着密集的时候位图好稀疏的时候索引好那我到底用哪个总不能让业务方自己判断这个标签是稀疏还是密集吧产品说用户行为是会变的这个月付费用户少下个月搞活动可能付费用户就多了总不能到时候我再改代码切存储方式吧翻车点没有一种存储结构能通吃所有数据分布你以为的最优解换个场景就是最差解。第五版为什么不能自动切换我盯着屏幕上两种存储方式的内存对比图突然冒出来一个想法为什么我不能写一个类内部自己判断当前数据是稀疏还是密集自动选择用哪种存储方式数据密的时候就用位图/数组数据稀的时候就存索引数据分布变了就自动在两种模式之间切换对外 API 还和普通 list 一模一样用户根本感知不到底层变了比如初始化的时候全是 False那就是稀疏模式只存 True 的索引当 True 的数量超过某个阈值自动切换成密集模式用连续数组存如果之后 True 又变少了再自动切回稀疏模式所有的索引、赋值、切片操作都和普通 list 用法完全一样这思路听起来是不是特别简单但真要写起来坑特别多两种模式之间切换的阈值设多少合适切换的时候怎么保证原子性切片、位运算、统计 count 这些操作怎么在两种模式下都保持高性能频繁修改的时候会不会来回切换导致性能抖动我当时自己试着写了个原型写了三天边界情况写得头都大了改了七八个版本还是有 bug。直到我搜 PyPI 的时候发现哦原来已经有人把这个思路完整实现了就是 bool-hybrid-array。说实话我最开始看到这个库的时候还挺不屑的觉得不就是个布尔数组吗能玩出花来直到我看了它的实现思路发现和我想的一模一样但是人家把所有坑都踩完了。它的逻辑特别朴素数据密集的时候底层用 numpy 存连续数组numpy 访问快数据稀疏的时候底层用 array.array 存异常索引省内存你不管怎么修改它内部自动判断要不要切换存储模式对外 API 和 Python list 几乎一模一样索引、切片、赋值怎么用 list 就怎么用它最有意思的是它的设计细节为什么密集区用 numpy稀疏区用 array因为密集区长度是固定的numpy 性能好稀疏区索引要频繁增删numpy 每次修改都创建新数组太慢用 array.array 刚好。这个细节一看就是真的写过业务踩过坑的人想出来的不是纸上谈兵。给你们看个最简单的例子from bool_hybrid_array import BoolHybridArr, TruesArray, FalsesArray 创建1亿个False这时候几乎不占内存因为是稀疏模式 arr FalsesArray(100_000_000) 只设置100万个位置为True for i in range(1_000_000): arr[i * 100] True 这时候内存只有几MB远小于bytearray的97MB print(arr[1000]) # True访问速度和list几乎一样 print(arr[1234]) # False 如果你手贱设置了9000万个True它会自动无缝切换成密集存储 整个过程不需要你手动干预API完全一致它还有个 memory_usage 方法可以直接告诉你当前用了多少内存比原生 list 省了多少要不要优化特别直观。我知道看到这里肯定有人会说“这不就是个轮子吗我自己也能写。”没错原理确实不复杂但是你自己写要处理多少边界情况要测多少种数据分布要踩多少坑别人已经把这些坑都踩完了测试也写好了API 也设计得顺手直接拿来用就完事了。当然我也不是说这东西就是银弹你要是就存几千个布尔值那直接用 list 就行犯不上引个第三方库。但是当你要存百万、千万甚至上亿级别的布尔值而且数据分布你还不确定的时候这种自动切换的混合存储确实能省你很多事。最后说点实在的选型建议优化到最后我最大的感触是根本没有什么“最好的”存储结构只有最适合你当前场景的。给大家一个我踩完坑总结出来的选型指南不用记什么花里胡哨的概念数据量小于 100 万直接用 list[bool]可读性最重要那点内存根本不值当优化数据量 100 万-1000 万分布稳定密集用 bytearray简单高效标准库不用引依赖数据量超过 1000 万或者分布稀疏/不确定可以试试 bool-hybrid-array 这种混合存储一劳永逸不用你自己判断需要做大量位运算与或非、交集并集可以配合位图一起用它也支持位运算很多人做优化一上来就找最牛逼的技术、最复杂的数据结构其实完全没必要。工程上的优化从来不是追求理论最优而是在你当前的业务场景下用最简单、最可维护的方式解决问题。就像这个布尔存储的问题你说它难吗一点都不难不就是存 0 和 1 吗但真要做到极致要在内存、速度、可维护性之间找平衡就需要你一层一层去优化一次一次去翻车最后才能找到那个最合适的点。哦对了最后提一嘴这个库的作者说他做这个东西的初衷是写线性筛的时候发现密集数组太占内存、稀疏数组跑起来太慢所以才做了混合存储。你看所有的优化本质上都是被业务逼出来的没有凭空想出来的银弹。如果这篇文章对你有帮助欢迎点个赞收个藏也可以去项目主页看看实现代码其实核心逻辑不复杂但是很多细节值得学习。