While browsing GitHub recently, I found myself exploring the Dubbo repository again. The community activity over the past month has been quite impressive:

Looking at the latest issues, I came across an interesting bug report:

https://github.com/apache/dubbo/issues/8055

This article examines the bug and the underlying story. Even if you're not familiar with Dubbo, you can still understand the issue.

All Dubbo code mentioned in this article is from the Master branch unless otherwise specified.

The Bug

The bug is described in the issue: the filter sorting process in the Dubbo framework has problems. Even when following the framework's rules for defining filter priorities, the resulting filter chain doesn't match expectations.

For those unfamiliar with Dubbo, a filter is essentially a filter component, similar conceptually to filters in web services. Dubbo has numerous filters that form a filter invocation chain.

Referencing the official documentation's call chain diagram, I've highlighted the filter section:

Filters are a core component of the Dubbo framework, with many features extended through them.

Now, consider this requirement:

I want to control the execution order of filters in the chain. When defining a filter, I need a way to specify its priority.

This seems like a simple requirement. I could add an order parameter, provide a default value when unspecified, and sort the filter chain based on this order during assembly.

However, this simple requirement led to a bug.

Reproducing the Bug

Let me demonstrate the bug using a modified version of the official test case. Dubbo has the following annotation:

org.apache.dubbo.common.extension.Activate

The order attribute is used for sorting. For demonstration, I have 5 filters:

The sorting rule is that filters with lower order values execute first. The expected filter chain execution order should be:

Filter4 -> Filter3 -> Filter2 -> Filter1 -> Filter5

Let's create a test case to verify this:

The result matches expectations, with no issues.

For reference, the official test cases for filters are located here:

org.apache.dubbo.common.extension.support.ActivateComparatorTest#testActivateComparator

The key sorting functionality in both the official and my test cases is implemented by this line:

Collections.sort(filters, ActivateComparator.COMPARATOR)

The critical component here is ActivateComparator.COMPARATOR, which is the source of the bug.

Why is it considered a bug? While the normal case works as expected, let's look at other attributes in the Activate annotation:

before and after specify that Filter A should execute before or after Filter B. However, these attributes are marked with @Deprecated and noted as "Deprecated since 2.7.0".

Why were they deprecated? Let's modify our previous test case slightly:

@Activate(before = "_2")
public class Filter5 implements Filter0 {
}

The change is adding to Filter5:

@Activate(before = "_2")

This means Filter5 should execute before "_2". What is "_2"? It's simply a mapping for Filter2:

The question is, after making this change as a normal developer expecting Filter5 to execute before Filter2, the expected filter chain should be:

Filter4 -> Filter3 -> Filter5 -> Filter2 -> Filter1

But what actually happens when we run this?

This isn't the expected execution chain! This is the manifestation of the bug.

Root Cause Analysis

The issue lies in the sorting algorithm:

org.apache.dubbo.common.extension.support.ActivateComparator

First, section ① encapsulates before, after, and order, then provides several comparison methods. You just need to know that the ActivateInfo entity contains these attributes, which will be used in the subsequent code.

Now, let's discuss section ②. Despite its length, the logic is straightforward. If either of the two filters being compared has before or after configured, the logic in section ② is executed.

The specific logic here is:

I won't delve into the details of this logic now, but I'll provide a clear demonstration later.

Finally, section ③ is interesting and deserves some explanation. Reaching section ③ means that neither of the two filters being compared has configured the after or before attributes.

We simply compare the order values directly. This section also has special handling for the case where orders are equal:

o1.getSimpleName().compareTo(o2.getSimpleName()) > 0 ? 1 : -1

If the orders are equal, the class names are compared. This is done to ensure sorting stability.

For example, consider these two filters without specified order values:

If we remove this judgment:

The code becomes:

if (a1.order > a2.order) {
    return 1 
} else {
    return -1 
}

Simplified, it's:

return a1.order > a2.order ? 1:-1

Looking at this more closely: hey, it seems we can optimize this further. Lines 78 and 80 are identical, so we can remove line 78.

After this transformation, congratulations, you've obtained an older version of the code:

Why did this change? There must be a reason. Looking at the commit history:

This commit points to commit #7778:

https://github.com/apache/dubbo/pull/7778

Which in turn points to issue #7757:

https://github.com/apache/dubbo/issues/7757

This issue is also mentioned in the previously mentioned #8055 issue:

The issue primarily contains two diagrams. The first diagram shows that when using only the original filters without any custom filters, the constructed filter chain has ExecuteLimitFilter before MonitorFilter.

The second diagram shows that after adding a series of custom filters (without specified order), ExecuteLimitFilter is placed after MonitorFilter.

The impact of these two filters being ordered before or after each other is beyond the scope of this article, but you can explore the relevant links if interested.

In summary, the following judgment logic is unstable:

return a1.order > a2.order ? 1:-1

Let's demonstrate with an example:

The left side is the test case, the right side is the sorting rule, and below is the output result. From the output, we can see that the final filter chain depends on the order in which elements were added to the list.

This is what issue 7757 pointed out:

The iteration order of the list affects the sorting order.

Therefore, this commit was made:

Now, let's revert the sorting order and run the same test case again, and it becomes stable:

Keen-eyed readers may have noticed another issue. There was another commit:

- First judgment: return o1.getSimpleName().compareTo(o2.getSimpleName()) - Second judgment: return o1.getSimpleName().compareTo(o2.getSimpleName()) > 0 ? 1 : -1;

What's this about?

The first judgment overlooked a case where class names are the same but package names differ:

- com.why.a.whyFilter - com.why.b.whyFilter

In this case, o1.getSimpleName().compareTo(o2.getSimpleName()) returns 0.

What happens when 0 is returned?

Would you believe it directly discards a filter? For example, if your collection is a HashSet or TreeMap.

It turns out that Dubbo uses TreeMap. Let's demonstrate with a test case.

If using the first judgment, only one filter remains in the TreeMap:

If using the second judgment, there will be two filters in the TreeMap:

Details, the devil is in the details.

Well, I've finished discussing the comparator, but you may have noticed that I haven't yet explained what the sorting instability bug actually is. I've only introduced another bug.

Don't worry, I haven't figured out how to describe it yet.

This process is quite complex, involving the Timsort sorting method, which would require another article to explain thoroughly.

So, I took a different approach, focusing on showing you the comparison process. As for the reasons behind this process, it's Timsort at work. Feel free to explore it yourself.

So what is the process?

I added output statements at the entry point of the comparison method:

The five filters are:

The test case is:

@Test
public void whyTest(){
    List<Class> 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 < filters.size(); i++) {
        builder.append(filters.get(i).getSimpleName()).append("->");
    }
    System.out.println(builder.toString());
}

The output log is:

Did you notice the issue? First, I deliberately controlled the order in which elements were added to the list:

This way, the first three comparisons construct this filter chain:

Filter4->Filter3->Filter2->Filter1->

Then, when Filter5 enters, it first compares with Filter1 and finds that its order (0) is greater than Filter1's (-1), so the comparison ends, resulting in this filter chain:

Filter4->Filter3->Filter2->Filter1->Filter5->

Throughout this process, Filter5 never compares with Filter2 at all, let alone considering the before tag in Filter5:

But when I modify the order in which elements are added to the list:

Hey, it works correctly. Isn't that amazing?

Amazing, right? Why? Go explore the principles of Timsort.

Historical Context

This leads me to a question:

Who, when, and why introduced the after/before mechanism?

From my perspective, the original intention of this mechanism was good - providing another configuration option and giving users more control. However, in actual use, it can easily lead to confusing situations.

So I looked at the commit history:

This annotation was originally written by Liang Fei (one of the founders of the Dubbo project). Initially, it didn't have before and after, but it had match and mismatch.

Then, at 1:54 AM the day after writing this annotation, he submitted a method-level matching:

These three methods are even more complex to use than before/after.

Then, after waking up at 12:34 PM, Liang Fei deleted these three configurations:

Two months later, on May 8, 2012, the after and before configurations were added:

They remained in the Dubbo source code until August 7, 2018, when they were marked as deprecated:

And this issue was referenced:

https://github.com/apache/dubbo/issues/2180

It stated: "The after and before are not used in Dubbo source code, and there are problems with sorting."

Thus, these methods were marked as deprecated after version 2.7.0,宣告了该方法的死亡 (declaring the death of this method).

I don't know why Liang Fei introduced these methods in 2012. I tried to find clues in his code commit history but couldn't.

However, another thought occurred to me:

After Liang Fei introduced these methods, did the comparator he wrote consider such situations?

So I immediately looked at the code commit history of the comparator:

org.apache.dubbo.common.extension.support.ActivateComparator

I copied out his code and ran it with the same test case:

Unfortunately, it has the same issue.

Perhaps, these methods shouldn't have been introduced in the first place.

Simplicity is the ultimate sophistication. Learning from Spring's Order, there's only one Order:

Then, I suddenly thought of another framework: SofaRPC.

SofaRPC has intricate connections with Dubbo and HSF, so I took a look at the corresponding place in SofaRPC:

com.alipay.sofa.rpc.ext.Extension

For sorting, only order is retained.

This makes the comparator code very simple:

com.alipay.sofa.rpc.common.struct.OrderedComparator

Additionally, I compared Liang Fei's earliest comparator with the latest one. The functionality is identical, but the code differs significantly:

I must admit that after several refactoring iterations, the readability of the latest comparator has improved considerably.

I traced the commit history of this class and watched its evolution step by step, which actually serves as a good example of code refactoring. Feel free to explore it yourself.

That's all for now. Time to wrap up.