event-reduce: Incorrect event-reduce action

We discovered some scary behavior in our app where items were being sorted wrong. We dug into and realized that event-reduce is actually suggesting an insertLast when it should be an insertFirst.

Here’s the test case showing it: https://github.com/pubkey/event-reduce/pull/443/

I thiiink (though I don’t fully understand the library yet) the issue is somewhere in the truth table to bdd conversion?

I think this because the json truth table calculateActionFromMap seems to correctly tell us runFullQueryAgain (well it’s not ideal, which would be insertFirst, but it doesn’t give us incorrect results) for this case of 0101000000010011001.

However, calculateActionName is wrong. It tells us to insertLast.

–

We can obviously patch this, but the issue opens up some serious questions for us:

From reading the iterative fuzzing process, it seems there is no guarantee of correctness – is that true?
How can we be confident there are no further issues like this?

About this issue

Original URL
State: closed
Created 7 months ago
Comments: 19 (8 by maintainers)

Commits related to this issue

ADD test from #444 — committed to pubkey/event-reduce by pubkey 7 months ago

Most upvoted comments

Hi @TristanH I just released 15.0.0-beta.37 with the fixes, please test.

From reading the iterative fuzzing process, it seems there is no guarantee of correctness – is that true?

Let me re-answer that question. So before I said that there are 2^19 (=524288) state combinations that the fuzzing has to test. This was not true. The state functions return boolean values and not all combinations of values are possible. For example the combination of isInsert, isUpdate and isDelete does not mean that there are 2^3 combinations of them because on an event, only one of these 3 can return true. The same goes for other state functions like hasLimit and wasLimitReached and so on. So the question is, how many possible state combinations can exist in practice? And that is what the fuzzing is trying to find out. Atm it found 525 combinations, which is shown in the amount of lines in the truth-table.json. Last time I had run the fuzzing, some years ago, it found new possible combinations even weeks after the fuzzing has started. This was suspicious for me at that time and might have given a clue that the random query+event generation was not correct. But I did not investigate any further, which lead to this bug you found.

This time the fuzzing only found new combinations in the first 8 hours, then it no longer found any new ones even after having run 95hours on 8 CPUs, still running. This give me confidence that the random generation works correctly now and it is close-to-zero likely that there are any query+event combinations that the algortihm does not know about. From my point of view, the “guarantee of correctness” is the same I can give you on any of my hand written source code. The only option of event-reduce new version being wrong is that there is a whole category of query+event combinations that I did not think about or that the tests or binary-decission-diagram itself is broken.

Anyway thank you very much for your time in investigating this problem. This helped me a lot and I am really happy that we found this before eventReduce: true was released as a default in RxDB v15.

I will let the fuzzing continue for some months, just to be sure. Also there is an optimization running to find a better bdd (by trying out different ordering of the bdd-nodes) which improves the performance. I did some re-research and there is still no better method of optimizing bdds other then random shuffling the order. I already optimized the bdd for some hours but I will release another event-reduce version in some weeks to have a smaller, more optimal bdd. In the unexpected case the fuzzing finds any more states combinations, I will ping you here and postpone the RxDB@15 release again.

pubkey on Nov 28, 2023

@TristanH There is a problem at RxDB Premium atm which is why I did not ping you here. RxDB core is released with the fixed event reduce already. Working on the premium plugins. I will likely release them today or tomorrow morning.

pubkey on Nov 27, 2023

After 1d of fuzzing, it found out by itself that your 3rd test needs the action ‘runFullQueryAgain’ 🥳 I will let it run over the weekend and then release a new version of the RxDB beta with the updated event-reduce. Until RxDB v15 is out of beta, the fuzzing can run for some weeks.

pubkey on Nov 24, 2023

That’s great news. We have a digitalocean box with 48 intel cores if you wanna use that, we can give you ssh access if you want to run there on ubuntu.

Thank you for the offering. I will be using my own server atm. Last time I ran the fuzzing it did not find any new states after 2 weeks. So having it run in parallel 8x I think it should be fine. Also I switched out minimongo with the mingo package, so fuzzing runs faster by itself now. My plan is to let it run for a few months even after everthing is fixed and the new version is released.

pubkey on Nov 24, 2023

@TristanH that is exactly what I was thinking about a few minutes ago.

So the main changes atm are:

Better random query generation: https://github.com/pubkey/event-reduce/pull/445/commits/a3c7002e2c68080c0c80ee4b5df2fa2d50e9f169#diff-e3b9537b24b427eebaa0e38f8a980b22234dd1ba20a1a65092d35d35f2b18485R182
Better random event generation: https://github.com/pubkey/event-reduce/pull/445/commits/9331c1629be65501fcdf80883b375897a9fe42e1#diff-a7a98b6c47fa60580c301fabb7647b20bc1c7b6b08e23d68effd419ac4732e8bR53

It will now change up to all 3 fields or even no field at all.

pubkey on Nov 23, 2023