Inconsistent order of tuned-group-by output causes random failure

[visibletrap]

We are having random failure issue with our test suite. This is the result of our investigation.

• We have a rule which inserts a few facts in the rhs.
• In our test suite, at flush-updates, in some runs, one fact is processed first which result to a passing test, but in some other runs, the other fact is processed first which result to a failing test.
• We found that the reason why the facts are processed in a random order betwenn the runs is because output of tuned-group-by doesn't always be in a consistent order.
• The reason why tuned-group-by output doesn't return a list in consistent order is because Java's HashMap, which is using internally, doesn't keep or guarantee any order.

Now, I have some questions regarding this.

• Does this make sense to you? Do you see any wrong conclusions here?
• Is the processing order really important here or is it just incidental? Is it possible to make a modification such that we don't care about the output order of tuned-group-by?
• If the order is essential, should we drop back to use default Clojure's group-by? Have you had a performance issue because of using it?

Note 1: Clojure's group-by guarantees the result order.
Note 2: I wrote a generative test to show that Clojure's group-by and tuned-group-by don't return result in the same order before I realize that it's apparent since Java's HashMap doesn't provide order guarantee. I'll put it here just in case you want to check it out.

[rbrush]

Hey, thanks for reporting this. The purpose of the tuned-group-by is indeed for performance needs, which I described a bit in this blog post. Basically, Clojure's group-by will repeatedly update non-transient vectors repeatedly if many items match to the same key. For some workloads using Clara, we were spending 50% of the time updating vectors in group-by, (!) so I wrote an optimized version.

Note that tuned-group-by should guarantee the order or the values in each key, but not the order of the keys themselves due to the use of HashMap that you point out. However, I don't think Clojure's group-by makes any strong guarantees here either. The doc on group-by says its values under a given key preserve input order, but doesn't make a guarantee to the order of the keys themselves in the returned map.

I'd be open to a change to tuned-group-by to create consistent key ordering if we can do so without a significant performance penalty. (It might be as simple as replacing HashMap with LinkedHashMap.) However, making assumptions about the ordering of group-by keys might not be safe since I don't think it's fully guaranteed.

In your tests, is Clara itself producing unexpected outcomes due to this ordering issue? Or is the order just different each run, making it difficult to test? If it's the latter, we've run into the same issue and basically have tweaked our test to be robust to different ordering. For instance, we put the the query results into a set or map to check the expected results, versus a list-based comparison that could break due to order.

Of course, if Clara itself is producing surprising results because of this it's definitely something we need to fix.

[rbrush]

I ran some benchmarks using java.util.LinkedHashMap instead of java.util.HashMap and the cost is negligible, and it also passes the generative test you had posted.

If this solves your problem then I'm happy to merge it in. I'm not sure that relying on group-by ordering is a great idea, but it makes sense for Clara's behavior to match that of the built-in group by in any case.

If you'd like to put together a pull request with this change and your generative test I can merge it.

[mrrodriguez]

I'd be curious to understand what unpredictable order behavior Nuttanart is seeing as well. I do think there are definitely areas where Clara should have freedom to not guarantee evaluation order. Most of the time if things are breaking due to order changes, it is a sign that the rules need to be restructured in a way where they are always logically consistent with expectations. Sometimes it is just a test concern (as Ryan has said) where the tests are inappropriately using vectors or lists when they should be using unordered comparisons or something like frequencies comparisons instead.

I do want to note that Clojure's group-by does not produce a reliable order as implemented in any of the recent versions (ever really) . The map that is returned is built from a (transient {}), which for the purposes of this behaves the same as the non-transient counterparts.

For small sizes of maps returned, it may appear that there is some sort of consistency in order guaranteed, but this is just a implementation detail of Clojure's "array map" being used for maps of size less than certain thresholds (looks to be currently 9 for literals and 16 for assoc growth).
So, if you are grouping things with group-by and arrive at only less than a threshold number groups, you will likely see consistent order, but this is not something to rely on.

Demonstration of the underlying impl details:

(group-by identity
          [1 2 3 4 5 6 7 8])
;= {1 [1], 2 [2], 3 [3], 4 [4], 5 [5], 6 [6], 7 [7], 8 [8]}


;; Passing the new map creation threshold for array maps vs hash maps
(group-by identity
          [1 2 3 4 5 6 7 8 9])
;= {7 [7], 1 [1], 4 [4], 6 [6], 3 [3], 2 [2], 9 [9], 5 [5], 8 [8]}

You can see this behavior without group-by as well.

{:a 1
 :b 2
 :c 3
 :d 4
 :e 5
 :f 6
 :g 7
 :h 8}
;= {:a 1, :b 2, :c 3, :d 4, :e 5, :f 6, :g 7, :h 8}

;; Adding one more item to the map literal
{:a 1
 :b 2
 :c 3
 :d 4
 :e 5
 :f 6
 :g 7
 :h 8
 :i 9}
;= {:e 5, :g 7, :c 3, :h 8, :b 2, :d 4, :f 6, :i 9, :a 1}

[devn]

For a moment what I thought was being suggested was that tuned-group-by did not preserve the ordering of the values in the resulting map as group-by does. This is not true. tuned-group-by behaves the same as Clojure's group-by in this respect and preserves value insertion order.

I will echo previous comments that there's no guarantee of the order of keys in maps returned by group-by and that it's a bad idea to ever rely on the order of keys in a map unless you're talking about a sorted clojure.lang.PersistentTreeMap.

[visibletrap]

Hi guys, thanks for looking at this. And sorry for my misunderstanding of group-by's ordering. You are right, the doc doesn't say that it guarantees the keys order. It now feels to me that the randomness just uncovers an actual underline issue.

Our test doesn't break because the order is expected by the output. It breaks because after firing the rules, sometimes a fact exist while sometimes it disappears. E.g. the success case, querying for a fact get 1 result back while the failure case, querying for a fact get back nothing.

I have extracted a simplified version of our code. I wasn't success in replicating the issue with this simplified version but I think it helps explaining the issue easier. https://gist.github.com/visibletrap/dfee267731cab99d2a6e

This the rough processing step I have seen.

1. Data and UpdateDate which inserted in line 23 are activated

2. "the-rule" is matched so Data is retracted by line 14, then Data and Flag are inserted by line 15

3. At this point, I have seen 2 flows which one of it is a failure case.

   3.1 For failure case, the Data is processed first follows by Flag.
   3.1.1 PendingUpdate is processed. Data and Flag are retracted
   3.1.2 Rule processing is done
   3.1.3 Querying for Data in line 25 returns nothing

   3.2 For passing case, the Flag is processed first follows by Data.
   3.2.1 Rule processing is done
   3.2.2 Querying for Data in line 25 returns a Data

I randomly see 3.1 and 3.2 in both our real code and this simplified version. But I can't manage to make 3.1.1 happen in this simplified version. This version PendingUpdate in 3.1.1 doesn't have any fact.

In summary, I now found that group-by randomness is not actually the cause of the problem. The actual problem I'm seeing "now" is that mem/remove-insertions! which is called before 3.1.1 sometimes returns empty, sometimes returns Data and Flag. I'll need more time to digging further more. The current impression is putting debug println inside remove-insertions! or add-insertions! makes the issue disappear.

[rbrush]

Hmm, sounds strange. One thing that pops to mind is the pitfalls of using retract! on the right-hand side of a rule. I have no idea if this is the problem you're seeing, but things like this can occur:

Unless you explicitly control the activation order of rules, in a complex rule set you could end up with a rule firing a retract! before the item being retracted is inserted by another rule. Since the item yet wasn't inserted, the retract! would have no effect and the item would show up later.

Frankly, I try to avoid use of retract! from within the rules outright because it's hard to think through this sort of thing.. There are some special cases when it can be useful but it often just causes confusion, and goes against the idea of letting the engine maintain truth and support itself. I do have a note in the Clojure documentation on the retract!, but it's probably something we should make more explicit. I've found that I've never really needed retract! to express domain logic, although I added it to match similar functionality in other engines.

Another pitfall is that in the example you're retracting a fact that was used in that fired the retract. Since Clara uses truth maintenance for (insert!), an explicitly retraction of a supporting fact could cause Clara to retract items inserted on behalf of the fact. You can avoid truth maintenance by replacing insert! with insert-unconditional!. This is probably a good idea if you're using retract! to keep the engine from trying to manage support for a rule itself, creating more confusion.

Of course, this could also be caused by a bug in Clara itself, which obviously we'd want to fix. I don't see an obvious issue, but these can be easy to miss. If the above notes on using retract! and insert-unconditional! aren't helpful then we should dig into reproducing this issue with a test.

[visibletrap]

Thanks for fast response and the explanation. We'll not be using retract! then.