压缩算法技术讨论贴：海量调用栈数据如何设计压缩算法？

[CC11001100]

一、缘起

很久之前接触过一个灰盒的漏洞检测工具，当时跟工具的开发者讨论了一些工具未解决的一些痛点，op 印象比较深的是其中一个点，这个工具的漏洞检测算法会参考调用栈信息，因此存储了海量的stack trace数据，因为一些业务上的因素，这些数据需要能够存储一段时间才能删除，比如存储够一个月，那这累积下来存储空间的占用就是一个比较头疼的问题，比如 Java 的调用栈可能的一个数据样例：

java.lang.RuntimeException: level 2 exception
	at com.msh.demo.exceptionStack.Test.fun2(Test.java:17)
	at com.msh.demo.exceptionStack.Test.main(Test.java:24)
	at sun.reflect.NativeMethodAccessorIm 猴子 pl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
	at java.lang.reflect.Method.invoke(Method.java:498)
	at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)
Caused by: java.io.IOException: level 1 exception
	at com.msh.demo.exceptionStack.Test.fun1(Test.java:10)
	at com.msh.demo.exceptionStack.Test.fun2(Test.java:15)
	... 6 more

• 这个调用栈可能会有几十层甚至上百层，甚至包的长度也可能会很长
• 数据量可能会有数十亿条，每次扫描漏洞的任务都会疯狂产生新的调用栈，这些调用栈数据需要持续保留一段时间
• 使用场景更多的是 key/value ，比如存储一个调用栈，然后返回一个 id ，然后下次拿着这个 id 来读取，至于如何存储就是需要花心思尽可能优化的地方，使用的场景是很简单的 ，所以这就有了比较大的优化空间

二、思路

笔者之前看过美剧《硅谷》之后就对压缩算法领域很是感兴趣，也研究过一些压缩算法的实现，之前自己也针对性的设计过几款压缩算法整体压缩率还是很高的，于是就想着看看能不能解决这个问题，开始思考如何针对此类数据的特性针对性设计压缩算法：

1. 首先是拆解调用栈，大概可以分为几部分：
   • 最上面的第一行可能会有异常信息，包括异常类的名字或者异常消息，这里为了简单先忽略，其实对栈帧的处理已经涵盖了这部分故而不再展开讨论
   • 然后是可能会有若干个栈帧，等会儿再拆解每个栈帧里面都有啥
   • 栈帧之间可能夹杂着 Caused by 信息，这意味着是一个新的栈，不过这个影响的更多是解析的 parser 逻辑，而不是存储逻辑 ，所以此处忽略这个点
2. 每个栈帧又可以拆解为几部分：
   • 首先是被调用的方法，对于 Java 而言可能是sun.reflect.DelegatingMethodAccessorImpl.invoke，让我们来以代码静态分析的视角来看这个数据，我们把这个称之为符号symbol，则让我们把这个符号按照包分隔符.进行分割，并且从上往下对应到一颗树上，则我们可以把程序代码中的所有可能的符号都看做是一颗根节点为空字符的树上的不同的路径（因为程序代码量是有限的，所以这颗树的大小其实也是可控的，一般不会特别离谱，暂不考虑代码混淆的情况的话...），则我们的问题转换为如何存储这棵树以及每个路径对应的节点
   • 因为每条路径的最左节点是根节点，所以只需要确定路径的最右节点即可，因为最右节点它在树上去往根节点的路径是唯一的，所以只存储一个节点就能够还原整个路径（这也是能够实现压缩的理论基础）， 所以这里就出现了第一个能够压缩的点，对于一条路径，我们只需要标记路径最右节点的 id 即可，这个时候我们能够实现的效果就是把sun.reflect.DelegatingMethodAccessorImpl.invoke压缩到一个 4 字节甚至更短的整数，比如把sun.reflect.DelegatingMethodAccessorImpl.invoke对应到整数10086
   • 上一步能够把一个符号转换为一个数字的基础是我们已经存储了树，比如树上每个节点的父子关系及节点本身的 id ，让我们来观察这棵树，我们会发现 Java 的符号其实有一个规律，它的前缀大部分都是重叠的，比如同一个包下面有 10 个类，而每个类又有 10 个方法，则这 100 个方法被调用的时候除了类名和方法之外它们的包名路径是相同的，针对这种情况使用前缀树就比较合适，于是我们就可以在内存中维护一颗按包名.分割的前缀树（或者基数树更合适更节省空间，可惜 op 也不熟悉基数树 o(╥﹏╥)o ），然后存储的时候就可以用这个树把每个栈帧里最占地方的内容压缩到一个整数了，这一步树的存储和节点编号是为符号的压缩提供了基础支撑
   • 然后是文件名和行列位置，这个其实也可以对应着一棵树，只不过这棵树比较矮（某些语言会展示文件的全路径类名，这种情况下树就比较高了，效果就会比较好），原理跟上面类似，不再展开讨论
3. 字符串常量池字典
   • 我们会发现字符串很多都是超过 4 个字节的，并且字符串会出现大量重复，于是就想是不是可以抽象一个更底层的数据结构，比如引入一个字典来把字符串置换为整数，是不是能够更节省存储空间呢，这是另一个压缩点，这一点有点像 JVM 内部的字符串常量池引用
4. 栈级别避免重复
   • 上面讨论的点都是逐层往下拆分的，现在让我们来看一下最上层的栈级别，我们知道程序执行起来走不同的分支调用栈就可能会不一样，各种分支组合起来可能栈帧里来来回回是调用那几个方法，但是整个栈可能都是不同的，尽管如此，根据二八定律，80%的情况下可能都是走的 20%的固定的逻辑路径，则当调用次数大到一定程度的时候，会出现很多完全相同的调用栈，则我们可以在调用栈这个级别再做一次映射引用，如果之前已经存储过了，则直接返回之前的 id 避免重复存储

三、交换 idea

以上仅为个人的头脑风暴，还未编码验证，发到 v2 里与老哥们讨论一下，欢迎老哥们发表看法互相讨论。

最后，贴上一个美剧《硅谷》中我比较喜欢的一帧截图：

[kneo]

你有发帖子的闲工夫，不如先实现出来测试一下效果。

[1423]

先用常规通用算法跑一遍做个列表对比下吧, 约摸心里有个数
gzip xz zstd shoco smaz
zstd 还能预训练字典, 用自己的数据训练后可以尝试压缩单独的数据(而不是只能用于大量数据)

[CC11001100]

@kneo 代码在写了老哥，方案设计写了大概一个小时，只是感觉算法应该还有挺大优化空间，论坛里牛逼大佬比较多先发出来让大家喷一下，这样我在写的时候也能及时调整，代码估计要写个两三天国庆后应该能发出来具体效果 https://github.com/stack-database 😀

[CC11001100]

@1423 通用的压缩算法大部分都是基于字典和偏移尽量消除重复数据，比较依赖的是压缩的时候的字典窗口大小和一次性被压缩的数据量的大小，调用栈是热数据需要能够随时查询不适合批量压缩，如果 gzip 只能针对单条调用栈进行压缩，那个工具的开发者现在已经是在这么做了，消耗的资源（ gzip 的内存、CPU 消耗等）与效果做性价比的话不是很理想（但也能凑活用。。。），所以才想着看看探索更极致的优化，当然这也只是一次尝试，也很可能还不如通用的压缩算法也说不好 😅

[CC11001100]

@1423 预训练字典的方式也跟那个工具的作者讨论过他否定了，他的业务场景不太满足，数据拿不到那是个类似私有部署的 CLI 工具，要训练只能在用户自己的电脑上训练。。。🤣

[1423]

那你想的挺清楚了,还要讨论啥呢?

[1423]

😅

[nuk]

重要的是重复数据，只做栈压缩没啥意义，exception 产生的地方是有限的

[CC11001100]

@1423 #6 哈哈哈我有点慌呗，我在压缩这块还没太多经验属于刚入门还在各种探索寻找案例练手，我怕自己有想不到的点导致后面全都是错的心态就真崩了那，发到论坛里让大家喷一喷聊一聊能更完善一些有问题我也能及时调整，我之前出现过埋头造轮子造完才发现因为最开始一个很基础的东西没想对到后面全都是错的整个都白费劲哈哈哈。。。😂

[CC11001100]

@nuk 是的老哥，所以压缩分为了两部分：

1. 一部分是栈内部的压缩，这一步相当于是所有的栈共享了一个全局字典来压缩自己内部的重复部分

2. 一部分是栈之间的压缩，完全相同的栈就直接引用同一个 id ，有点类似于 jvm 里的 fast throw 机制，完全相同的栈从第二次开始就是引用的之前的 id 而不重复存储，相当于把整个栈压缩为一个整数

对了怪我的背景故事介绍不完整，他那个工具调用栈不只是异常抛出，他那个工具是通过 java agent 技术给代码添加 hook 点来检出漏洞（原理跟 arthas 类似），每个 hook 点都会有对应的调用栈，hook 点是用户可配置的不可控，甚至可能会出现用户把每行代码都 hook 的情况。。。

[Gota]

pyroscope 做过类似的存储优化，可以参考看看： https://pyroscope.io/docs/storage-design/

[nuk]

@CC11001100 前缀压缩树，行号感觉需要单独处理。。

[learningman]

你直接用 brotli ，然后把他那个内置的字典换成适用于你这个场景的不就好了