Use fast-check to test concurrency consistency invariants #382
Comments
teebirdy
added
r&d:polykey:core activity 1
|
Ok, looks like using a combination of One of the better features here is that we can specify a deterministic test for re-creating failures. Or we can define our own test conditions that will be run every time. When a test fails it will log out the exact conditions that led to the failures. To make full use of this we will need our own custom arbitraries https://github.com/dubzzz/fast-check/blob/main/packages/fast-check/documentation/AdvancedArbitraries.md . Here is an example of how to use this. test('concurrent trusting gestalts', async () => {
const acl = await ACL.createACL({ db, logger });
await fc.assert(
fc.asyncProperty(fc.scheduler(), async (s) => {
await Promise.all([
s.schedule(acl.setNodesPerm([nodeIdG1First, nodeIdG1Second] as Array<NodeId>, {
gestalt: {
notify: null,
},
vaults: {
[vaultId1]: { pull: null },
},
})),
s.schedule(acl.setNodesPerm([nodeIdG1First, nodeIdG1Second] as Array<NodeId>, {
gestalt: {
notify: null,
},
vaults: {
[vaultId1]: { pull: null },
},
})),
await s.waitAll()
]);
})
);
})example of the failure I think fast-check's utility is limited here. If we're just testing for transaction conflicts then the order of operations doesn't really matter much. It can be useful for randomising values for testing such as IDs and strings if we want to add more robustness to our testing. |
|
As for generating random values for testing. It can be done like so; test('random values', async () => {
await fc.assert(
fc.asyncProperty(
// We can generate arrays
fc.array(fc.integer(), {maxLength: 5}),
// We can filter for conditions on values
fc.float().filter( num => num > 10),
fc.boolean(),
async (integer, float, bool) => {
// We can set pre-conditions to adhere too.
// If this condition is false then the test is tried again with new values.
// The test will fail if this fails too often.
fc.pre(integer[0] < float);
console.log(integer, float, bool);
// The fc.assert will fail in the case of a thrown error or if we return any falsy value.
return bool;
})
);
})We provide a set of arbitraries types that are generated and then provided to the test. One very useful feature is that when a test failure happens it will shrink test values down to the simplest set causing the failure. Example failure; So this can be useful for for finding any intermittent errors in a test. Using the test failure information here we can deterministically run the same conditions that caused the failure over and over again. Very useful for finding some of the harder to find bugs. |
|
Detection of a transaction conflict wouldn't be useful unless the idea is upon a random selection of async operations, some will have conflicts and some will not under certain conditions. It can also be applied to the counter racing to ensure that we don't have conflicts in that case and that the end state is consistent. Also many of our domains have an expected end state after concurrent operations. We should use this. |
|
Creating custom arbitrary seem simple enough. You can derive them from an existing arbitrary. Doing this we can also benefit from shrinkage. test('custon arbitrary', async () => {
const nodeIdArb: fc.Arbitrary<NodeId> = fc.uint8Array({maxLength: 32, minLength: 32})
.map((array) => IdInternal.fromBuffer<NodeId>(Buffer.from(array)));
await fc.assert(
fc.asyncProperty(
nodeIdArb,
async (nodeId) => {
console.log(nodeId);
return false;
})
);
})Will throw and shrink to; |
|
So in summary, this will be very useful for the following test cases.
It's not so useful for;
|
|
For longer running tests we will need to adjust the amount of testing done using the |
|
domains that can make use of the deterministic random value generation.
can make use of scheduler for concurrency
|
|
Can we start integrating it into our db changes so we can test for transaction conflicts? Starting from the RPC handlers. I reckon some tests can be replaced with using this too. |
|
New PR required. |
Here's an alternative using The The expectation is that the callback passed at the end of |
|
It looks like the fast check report tells us how to reproduce the failure. @tegefaulkes should try this using the given code: |
|
We need to configure the number of times it runs, and to have its max timeout in line with jest's test timeout too. This only applies for asynchronous tests. We can default it to the When a test has an overridden timeout, it should probably apply to the If it runs alot, it may blow up our test times overall. We might want to reduce the number of times it runs for very simple tests. |
|
I think the random arbitraries can be useful for any data that we are processing. This includes the For things like I think alot of vault domain operations can be applied to randomly generated files. Arbitrary buffers basically. Any time we are reading something where we have to parse the data, would be suitable. So imagine reading a file, or reading off the network, any case where we are parsing that data into a useful structure can make use of fuzzing the input data. In many cases we may just be doing So I think for any of our functions in PK, we have a first line of defense being the type signature. Like |
|
As for the asynchronous scheduling, I think that would work quite nicely when we have more than 2 operations running concurrently. But I also think it's a good idea to use it for any place where we want to assert how a race condition may or may not be possible. I think the first place would be the counter racing areas. Like any place where we have multiple creation operations, that may step on each other, lets use fast check to ensure that they don't step on each other. Test any concurrent operations that shouldn't be clobbering the data the end. |
|
One example EFS where none of the operations should return a transaction conflict, because it's supposed to lock everything up. We could use this tool to fuzz the EFS sending in lots of reads/writes in different ways and at the end ensure that we don't throw a transaction conflicts. Other post conditions should also be considered. Not sure what they might right now. |
|
@tegefaulkes should find out how to reproduce test failures and report it here, can be useful in the future. |
|
This may be useful to streamline fast-check with jest. |
|
That can be useful since it will support |
|
Does it integrate timeouts though from |
|
It would reduce the noise of the |
|
It doesn't do anything fancy with the parameters. So no it won't propagate the jest timeouts to the |
|
Given a failed attempt There are two ways we can recreate the result. 1st by using the seed information provided the 2nd is to add the counter example For the scheduler the seed method will work fine, and the example method can be used as well. |
|
Where is the |
|
For the first it would've been await fc.assert(
fc.asyncProperty(fc.integer(), async (number) => {...}
)The second await fc.assert(
fc.asyncProperty(fc.integer(), fc.scheduler(), async (number, s) => {...}
) |
|
When dealing with EFS, the result check can use regular expressions. This is because the result is just a byte string. When dealing with PK, the result check may have to use asymmetric matchers to work agains the object instead. Jest extended provides additional asymmetric matchers in particular the In a way, the more ideal test case would be indicate that a given way of doing things should result in a particular output deterministically. But it's difficult to enumerate all the ways that could be the case, so instead, it's easier to say all these possible matches are correct, but then try to test as many concurrent variants as possible. This is all due to observable non-determinism. A model check on the other hand would argue that each output state is a state that needs to be checked with a deterministic path through the state machine. But this works best at a higher level, otherwise it's overkill for smaller dataflow functions. So front end components but also databases and other stateful components. This is where |
|
Example of command generation: #438 (comment) |
|
Some notes about fast-check:
|
|
Actually it turns out you cannot use fc without at least 1 arbitrary. And if we are doing this, we might as well do it with just a normal loop or |
|
This is pretty useful https://github.com/dubzzz/fast-check/blob/296cde419382eac6fe257ac4105a893dbdf5cfcc/packages/fast-check/documentation/Tips.md#combine-with-other-faker-or-random-generator-libraries. So it's easy enough to integrate other faker libraries such as this https://www.npmjs.com/package/@faker-js/faker. This can be quite useful for fuzz testing our UI too. |
|
This one is pretty large. It can be converted into an epic and each domain a separate issue. |
|
My recent work with However one thing is that with the async model runs, I believe they run each command serialised. So to properly test asynchronous concurrency, we would have to make fast check model checking to run the commands in concurrently. I'm not entirely sure how to achieve this atm, beyond making composed commands that run multiple commands together. The question is whether model checking testing works well with asynchronous concurrency testing as discussed above, and if there's a combination of these 2 that can be done. |
|
Subsequently I've made use of the The work was done based on this dubzzz/fast-check#564. So it works pretty well with the fast-check jest integration, the scheduler is just another arbitrary. The only thing lacking is the need to manually run the function call later. Unfortunately FC doesn't have a built in We did have a utility function called I noticed that in some cases, model checking isn't actually required if there's only a single mutation method. In the case of That means model checking is mostly useful when there are multiple mutation methods. At the same time, the current model checking I'm doing in If we really want to combine model checking (best used with multiple mutation methods) and concurrent scheduling, we have to use But if we only 1 single mutation method, then model checking is not necessary, but More details here: In particular this is important:
|
|
So the only last thing to explore is the usage of We could upgrade the And then this issue can be closed, as we now have examples of how to do this in new domains upon the merge of #446. Subsequent smaller issues can be created to upgrade particular tests to use fast check. But from now, most tests should use fast check. Domains that have fast check applied:
|
|
I think we have a good handle on how this all works. And @tegefaulkes you've been applying it to other places now too. I think we can close this. Please add your own notes about how you've been using fast check here too. Then later we can add a guide to wour wiki for development. |
Specification
We are likely to have alot of concurrency consistency invariants to test. EFS showed us alot of potential pitfalls and bugs in race conditions. SI helps at least ensure that we always have consistency at the DB layer, however it turns out testing concurrency is always really complicated and involves some overhead. Simple
expecttests are not enough.Here comes https://github.com/dubzzz/fast-check, it's a property based testing based on quickcheck. This can be used for quick light-weight model based testing.
Primarily quick-check related libraries provide 2 things:
So we should see if fast-check can help us do concurrency testing in a number of domains:
Additional context
scheduledDelayedFunctiondubzzz/fast-check#564 - issue about delaying scheduled functions so that the calls themselves can be made concurrentTasks
fast-checkcan help with concurrent tests and fuzz testsfast-checkinto jest testing including timeouts and reportingThe text was updated successfully, but these errors were encountered: