一个排序引发的BUG

2021-08-08 14:58

阅读:973

你好呀,我是why。 前两天在 Git 上闲逛的时候又不知不觉逛到 Dubbo 那里去了。 看了一下最近一个月的数据,社区活跃度还是很高的: 然后看了一下最新的 issue,大家提问都很积极。 其中看到了这样的一个 issue,发现有点意思: https://github.com/apache/dubbo/issues/8055 于是写下这篇文章给你分享一下这个 BUG 和 BUG 背后的故事。 放心,就算你完全不懂 Dubbo,也不影响你了解这个 BUG。 先说一下,下文中提到的 Dubbo 代码,没有特别说明的地方,都是我从 git 上拉下来的 Master 分支上的代码 啥 BUG 啊? 先给你描述一个这个 BUG 是啥样的。 其实就是这个 issue 的作者写出来的:Dubbo 框架里面的 Filter 排序过程有问题,即使按照框架要求写好规则后,最终生成的 Filter 链并不是我们想要的。 那么完全不懂 Dubbo 的朋友可能就遇到了第一个问题:啥是 Filter 呢? 其实就是一个过滤器而已,和 web 服务里面过滤器在概念上没啥两样。而 Dubbo 有非常多的 Filter,这些 Filter 共同组成了一个 Filter 调用链。 引用官网上的一个调用链路图,在 Filter 的地方我框起来了: 可以看到 Filter 是 Dubbo 框架的一个非常核心的组成部分,很多很多的功能都是从 Filter 扩展出来的。 你要是还不明白也没关系,你只要知道有这样的一个 Filter 调用链就行了,链上的 Filter 各司其职,各干各的事儿。 好的,那么现在需求来了: 我现在要求链上的 Filter 的执行顺序是我能控制的,即我定义 Filter 的时候你得给我留个地方设置它的优先级。 听起来是很简单的一个需求,对吧? 我直接给你留个口子,让你输入 order 参数,不输入给个默认值,然后组装 Filter 链的时候根据 Order 排个序。 不是我吹牛,十分钟就能写完,中间还带着三分钟的摸鱼。 但是,就这么个需求出 BUG 了。 具体啥现象呢? 我这里把项目拉下来,基于官方的测试用例,改巴改巴,给你演示一下这个 BUG 的体现是啥。 在 Dubbo 里面有这样的一个注解: org.apache.dubbo.common.extension.Activate 这里的 Order 就是做排序用的。简单演示一下,你看我现在有 5 个 Filter: 排序规则是 Order 越小的越先执行,那么这个 Filter 链的执行顺序应该是这样的: Filter4 -> Filter3 -> Filter2 -> Filter1 -> Filter5 搞个测试案例,我们验证一下: 符合预期,没有任何毛病。 另外说明一下,官方的关于 Filter 的测试用例在这里,你有兴趣,源码拉下来就可以看: org.apache.dubbo.common.extension.support.ActivateComparatorTest#testActivateComparator 不管是官方的案例,还是我自己写的案例,其中最关键的排序功能是这一行代码实现的: Collections.sort(filters, ActivateComparator.COMPARATOR) 而这一行代码里面最关键的就是 ActivateComparator.COMPARATOR 这个东西。 这个东西就是 BUG 之源,不慌,等下再说。 那么为什么说它有 BUG 呢? 前面演示了正常的情况下,是符合预期的。 但是你看 Activate 注解,里面还有这样的两个东西: before、after,含义是指定 Filter A 在 Filter B 之前或者之后执行。 但是被打上了 @Deprecated 注解,字段说明上也备注了: Deprecated since 2.7.0 2.7.0 之后被废除。 那么就有点意思了,为啥被废除? 来,看个例子,还是刚刚的那个测试用例。 我就稍微的这么一改: @Activate(before = "_2")public class Filter5 implements Filter0{} 改动点就是在 Filter5 上配置了: @Activate(before = "_2") 含义就是 Filter5 在 “_2” 之前执行。 “_2” 是啥? 就是 Filter2 的一个映射而已: 那么问题就来了,作为一个正常的程序猿,自信的对 Filter5 进行了这个改动之后,他内心的想法一定是想要把这样的 Filter 链: Filter4 -> Filter3 -> Filter2 -> Filter1 -> Filter5 修改为这样:(Filter5 在 Filter2 之前执行): Filter4 -> Filter3 -> Filter5 -> Filter2 -> Filter1 那么实际情况是怎样的呢? 来跑一把: 咋回事?这不是我预期的执行链啊? 是的,这就是 BUG 的表现。 咋回事啊? 到底是咋回事呢? 且听我给你分析一波。 上一小节我说了,问题出在排序算法上。 org.apache.dubbo.common.extension.support.ActivateComparator 来,一起看一下: 首先标号为 ① 的地方就是把 before、after、order 封装了一下,然后提供了几个比较的方法。你知道 ActivateInfo 这个实体里面有这些东西就行了,后面的代码会用到。 然后说说标号为 ② 的地方。 这个地方你别看挺长的,但是其实逻辑特别简单,当前对比的两个 filter 中的任何一个配置了 before、after 就会进入到标号为 ② 的部分的逻辑。 然后这里面的一坨逻辑是的这样的: 具体逻辑不细说了,等会给你来个直观的演示。 最后标号为 ③ 这个地方,有点意思,稍微多说几句。 能走到标号为 ③ 的地方,说明当前对比的两个 filter 都没有配置 after、before 这两个属性。 直接对比 Order 就行了。 这个地方对 Order 相等的情况还做了一个特殊处理: o1.getSimpleName().compareTo(o2.getSimpleName()) > 0 ? 1 : -1 如果 Order 相等,再比较类名。 这样做的原因也是保证排序的稳定性。 举个例子,比如这两 Filter,都没有指定 Order: 那如果我们去掉这个判断: 代码就变成了这样: if (a1.order > a2.order) {    return 1 } else {    return -1     } 简化一下就是这样: return a1.order > a2.order ? 1:-1 那么这一块的代码,整体就会变成这样: 这样仔细一看:咦,好像还能再优化一下。78 行和 80 行是一样的,所以可以去掉 78 行。 好的,经过这样的一番改造。 恭喜你,获得了一个老版本的代码: 左边是之前版本的代码,右边是现在 Master 分支的代码: 为什么会发生变化,必然是有原因的。 看一眼提交记录: 这次提交指向了编号为 7778 的提交: https://github.com/apache/dubbo/pull/7778 而这次提交指向了编号为 7757 的 issue: https://github.com/apache/dubbo/issues/7757 而这个 issue 在前面提到的编号为 8055 的 issue 里也提到了: 这个 issue 主要就是两张图。 第一张图是这样的: 在没有任何自定义 Filter,仅有官方原有的 Filter 的情况下,构建出来的 Filter 链,ExecuteLimitFilter 在 MonitorFilter 之前。 第二张图是这样的: 在加入了一系列自定义的 Filter(没有指定 Order)之后,ExecuteLimitFilter 就排在了 MonitorFilter 之后了。 至于这两个 Filter 排前排后的影响是什么,和文本关系不大,就不扩展了,你有兴趣的可以去看看对应的链接。 总之,只有这样的判断逻辑是不稳当的: return a1.order > a2.order ? 1:-1 来个例子演示一下: 左边是测试用例,右边是排序规则,下面是输出结果。 从输出结果可以看到,最终的 Filter 链取决于 list 的添加顺序。 这也就是 7757 这个 issues 说的: list 的遍历顺序会影响到排序的顺序。 因此,才会有了这样的一次提交: 好,现在我们把排序顺序改回来,同样的测试用例再跑一次,就稳定了: 眼睛尖的朋友可能还发现了一个问题。 这个地方还有一次提交: 第一种判断:return o1.getSimpleName().compareTo(o2.getSimpleName())第二种判断:return o1.getSimpleName().compareTo(o2.getSimpleName()) > 0 ? 1 : -1; 你说这是在干啥? 第一种判断还疏忽了这样的一种情况,包名不同但是类名相同的情况: com.why.a.whyFiltercom.why.b.whyFilter 这个时候 o1.getSimpleName().compareTo(o2.getSimpleName()) 返回的是 0。 返回 0 会发生啥? 直接吞掉一个 Filter 你信不信? 比如你的集合是 HashSet,或者是 TreeMap。 这就巧了,Dubbo 用的就是 TreeMap。 来个测试用例演示一下。 如果采用第一种判断,最后 TreeMap 里面只有一个 Filter 了: 如果采用第二种判断,最后 TreeMap 里面会有两个 Filter : 细节,魔鬼都在细节里面。 哎呀,真的是防不胜防啊。 好了,比较器我就说完了,但是你发现没有,我到现在都还没给你说排序过程不稳定这个 BUG 到底是啥,只是给你引申了一个其他的 BUG 出来。 莫慌,这不是我还没想好怎么给你描述嘛。 这个过程其实比较复杂,涉及到 Timsort 排序方法,就这方法就得另起一篇文章才能说清楚。 所以,我换了一个思路,主要给你看比较的过程,至于这个过程背后的原因。 就是 Timsort 在搞鬼,欢迎你自己去探索一番。 那过程是啥呢? 我在比较方法的入口处加上这样的输出语句: 五个 Filter 是这样的: 测试用例是这样的: @Testpublic void whyTest(){    List filters = new ArrayList();    filters.add(Filter4.class);    filters.add(Filter3.class);    filters.add(Filter2.class);    filters.add(Filter1.class);    filters.add(Filter5.class);    Collections.sort(filters, ActivateComparator.COMPARATOR);    StringBuilder builder = new StringBuilder();    for (int i = 0; i Filter3->Filter2->Filter1-> 然后,Filter5 进来后先和 Filter1 比,发现其 Order 为 0 比 Filter1 的 -1 大,于是比较结束,得到这样的Filter 链: Filter4->Filter3->Filter2->Filter1->Filter5-> 整个过程中,Filter5 与 Filter2 完全没有发生任何比较的操作,也就更不涉及到 Filter5 里面的 before 标签了: 但是当我把 list 的添加顺序修改一下: 咦,就正确了,你就说神不神奇? 神奇吧? 为啥呢? 去看看 Timsort 的原理吧。 追根溯源 其实写到这里的我产生了一个疑问: 是谁,什么时候,引入了 after/before 机制? 因为这个机制我个人觉得出发点是挺好的,多一个配置的地方,把选择权留给用户。 但是在实际的使用中,却容易出现比较混乱的情况。 于是我看了一下提交记录: 这个注解最早是梁飞(就是 Dubbo 项目要的开创者之一)写出来的,而设计之初没有 before 和 after,但是有一个 match 和 mismatch。 然后在写出这个注解一天之后的凌晨 1 点 54 分,提交了一个方法级别的匹配: 这三个方法使用起来甚至比 before/after 更加复杂了。 于是一觉睡醒之后的 12:34 分,梁飞又删除了这三个配置: 两个月之后的 2012 年 5 月 8 日,加入了 after 和 before 配置: 然后就一直留在 Dubbo 源码里面,直到 6 年后的 2018 年 8 月 7 日,打上了不建议使用的注解: 并提到了这个 issue: https://github.com/apache/dubbo/issues/2180 里面说:Dubbo 源码中没有使用 after 和 before,且排序是存在问题的。 于是这两个方法,在 2.7.0 版本之后,被标注为不建议使用,宣告了该方法的死亡。 我不知道 2012 年,梁飞为什么引入了这两个方法,我也曾想从他的代码提交记录上找到点蛛丝马迹,可惜没有。 但是,有了另外的一个想法: 当年梁飞引入这两个方法后,他写的比较器,是否考虑到了这样的情况呢? 于是我马上又看了比较器的代码提交记录: org.apache.dubbo.common.extension.support.ActivateComparator 并且把他的代码拷贝了出来,用同样的测试用例跑了一下: 很遗憾,也有一样的问题。 或许,当年就不应该引入这两个方法。 大道至简,学 Spring 的 Order,就只有一个 Order: 然后我又突然想了另外一个框架:SofaRPC。 SofaRPC 和 Dubbo 和 HSF 之间有着千丝万缕的爱恨情仇,于是我去瞅了一眼 SofaRPC 对应的地方: com.alipay.sofa.rpc.ext.Extension 用于排序的,也就只是保留了 order。 这样比较器的代码就很简单了: com.alipay.sofa.rpc.common.struct.OrderedComparator 另外,我顺便对比了一下梁飞最早写的比较器和现在最新的比较器的代码,功能完全一样,但是代码却差异较大: 不得不说,经过几次重构之后,最新的比较器的可读性高了很多。 我追踪了一下这个类的提交记录,也就看着这个类的一步步演化,其实算是一个比较好的代码重构的例子。 有兴趣的自己去翻一翻。 好了,就到这了,打完收工。


评论


亲,登录后才可以留言!