一、缘起

很久之前接触过一个灰盒的漏洞检测工具，当时跟工具的开发者讨论了一些工具未解决的一些痛点，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 来读取，至于如何存储就是需要花心思尽可能优化的地方，使用的场景是很简单的，所以这就有了比较大的优化空间

二、思路

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

首先是拆解调用栈，大概可以分为几部分：
- 最上面的第一行可能会有异常信息，包括异常类的名字或者异常消息，这里为了简单先忽略，其实对栈帧的处理已经涵盖了这部分故而不再展开讨论
- 然后是可能会有若干个栈帧，等会儿再拆解每个栈帧里面都有啥
- 栈帧之间可能夹杂着 Caused by 信息，这意味着是一个新的栈，不过这个影响的更多是解析的 parser 逻辑，而不是存储逻辑，所以此处忽略这个点
每个栈帧又可以拆解为几部分：
- 首先是被调用的方法，对于 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 ），然后存储的时候就可以用这个树把每个栈帧里最占地方的内容压缩到一个整数了，这一步树的存储和节点编号是为符号的压缩提供了基础支撑
- 然后是文件名和行列位置，这个其实也可以对应着一棵树，只不过这棵树比较矮（某些语言会展示文件的全路径类名，这种情况下树就比较高了，效果就会比较好），原理跟上面类似，不再展开讨论
字符串常量池字典
- 我们会发现字符串很多都是超过 4 个字节的，并且字符串会出现大量重复，于是就想是不是可以抽象一个更底层的数据结构，比如引入一个字典来把字符串置换为整数，是不是能够更节省存储空间呢，这是另一个压缩点，这一点有点像 JVM 内部的字符串常量池引用
栈级别避免重复
- 上面讨论的点都是逐层往下拆分的，现在让我们来看一下最上层的栈级别，我们知道程序执行起来走不同的分支调用栈就可能会不一样，各种分支组合起来可能栈帧里来来回回是调用那几个方法，但是整个栈可能都是不同的，尽管如此，根据二八定律，80%的情况下可能都是走的 20%的固定的逻辑路径，则当调用次数大到一定程度的时候，会出现很多完全相同的调用栈，则我们可以在调用栈这个级别再做一次映射引用，如果之前已经存储过了，则直接返回之前的 id 避免重复存储

三、交换 idea

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

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

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

一、缘起

二、思路

三、交换 idea