Replaying Replicated Redux

Fri 10 November 2017 by Jim Purbrick

While property based tests proved to be a powerful tool for finding and fixing problems with ReactVR pairs, the limitations of the simplistic clientPredictionConstistenty mechanism remained.

It’s easy to think of applications where one order of a sequence of actions is valid, but another order is invalid. Imagine an application which models a door which can be locked: an unlock action followed by an open action should be valid, but an open action followed by unlock should be invalid given a starting state where the door is locked. It’s a lot more difficult to imagine how every ordering of this simple sequence of actions can be made either valid or invalid.

The limitation of clientPredictionConsistency is caused by the master client having to see an invalid action before it notices that clients need resyncing. An obvious way to avoid this limitation would be to have all other clients let the master know if they have seen an invalid action, but this solution becomes more complicated when you want to avoid the master sending duplicate sync actions if multiple clients report invalid actions simultaneously.

At this point, I took a step back: even if clients could report conflicts without duplicate resyncs, the improved clientPredictionConsistency would centralise conflict resolution in the master. Clients receiving a state sync action would have no context on the conflict and so would be unable to do anything more than reset their local state. Reusing the state sync mechanism which allows late joining is simple, but doesn’t allow anything more than effectively rejoining.

One of the nice things about Redux actions is that they are more meaningful than either UI events or state updates: it would be nice if clients could use the context they have in the actions to resolve conflicts and reconcile optimistic updates with authoritative actions gracefully. This made me think of the optimistic update mechanism used by Half Life which keeps a list of actions which have been predicted locally and reapplies the predictions to new states received by the server. Redux was built to easily support this kind of time travel through application history, so I wondered whether something similar could be built for replicated redux.

Some hacking on these ideas produced replayConsistency: a generalisation of the Half Life optimistic update ideas applied to arbitrary Redux actions. When a non-master client generates a valid local action it is sent to the master, immediately reduced locally, but also appended to a list of predicted actions. When the client recieves a new action from the master it rewinds the state back to the start of the prediction, applies the new master validated action and then reapplies the predicted actions if they are still valid. Eventually every predicted action becomes part of the total ordering defined by the series of actions validated by the master and is sent back to the client, or the state which caused the prediction to be invalid on the master is reached on the client. In either case the prediction is discarded. In the case where a prediction becomes invalid, the client has the state before the prediction, the master validated action and the list of predicted actions available when updatePredictions is called. This context allows the client to do something significantly more sophisticated to fix the local state than simply reseting the entire local state. In fact replayConsistency does not need to send state syncs at all, making it significantly more efficient than clientPredictionConsistency which I renamed resyncConsistency to make the differences between the two optimistic consistency policies clear.

Switching out resyncConsistency for replayConsistency and eyeballing several games of ReactVR Pairs suggested that the new consistency mechanism was working as intended, but finding all of the kinks in resyncConsistency had required testing thousands of sequences of actions using property based tests. My existing tests didn’t apply here: they made sure that an application would work given the limitations of resyncConsistency. The property I really wanted to ensure held for all consistency mechanisms is that regardless of the predictions made at each client, eventually all clients would be consistent.

This test generates a sequence of pairs actions which might be sent by the master or one of two non-master clients and then checks that all clients are eventually consistent even in the pathological case where each non-master predicts all of its actions before getting any actions from the master. A nice feature of this test is that it is independent of the consistency mechanism and so the same test can be run to ensure that both resyncConsistency and replayConsistency result in all clients being eventually consistent for thousands of sequences of actions.

With my tests passing I had high confidence that replayConsistency was working and didn’t impose any limitations on event ordering making it a much more general and efficient solution than resyncConsistency as well as much easier to use as it doesn’t require complicated reasoning about application event ordering. The potential to perform sophisticated application specific state reconciliation when predictions are invalidated is also interesting and I’m excited to see what we can do with it in future.

If you’d like to play the ReactVR version of pairs or see the rest of the code, it’s available on github here.

All code in this post is made available under the ReactVR examples license.

Testing Replicated Redux

Mon 31 July 2017 by Jim Purbrick

Opening a couple of browser windows and clicking around was more than sufficient for testing the initial version of ReactVR pairs. Implementing a simple middleware to log actions took advantage of the Redux approach of reifying events to allow a glance at the console to reveal precisely which sequence of …

read more

ReactVR Redux Revisited

Tue 04 July 2017 by Jim Purbrick

There were a couple of aspects of my previous experiments building networked ReactVR experiences with Redux that were unsatisfactory: there wasn’t a clean separation between the application logic and network code and, while the example exploited idempotency to reduce latency for some actions, actions which could generate conflicts used …

read more

VR Redux

Wed 04 January 2017 by Jim Purbrick

Mike and I have been talking about how to easily build simple networked social applications with ReactVR for a while, so I spent some time hacking over the Christmas break to see if I could build a ReactVR version of the pairs game in Oculus Rooms. Pairs is simple and …

read more

Free Tests For Everyone!

Thu 11 June 2015 by Jim Purbrick

Modern software development is sometimes colourfully described as being similar to firing tracer bullets at a target. Rather than spending time doing a lot of research, design and specification up front, the smallest, simplest version of the software is built and the feedback gathered from its use is used to …

read more

Investing In Testing

Wed 10 June 2015 by Jim Purbrick

Last year I was talking to an engineer at Droidcon London who was working on an Android app with 100% test coverage. I immediately asked whether he thought 100% test coverage was worthwhile: many software engineering teams strive to achieve 100% test coverage, but few succeed because it’s an …

read more


Mon 18 August 2014 by Jim Purbrick


One of the things I’ve been working on since joining Facebook is Buck, an open source Android & Java build tool which is significantly faster than many other Java build tools for a number of reasons.

As well as being fast, Buck gains a lot of power and flexibility by …

read more

Evolving Develop

Mon 20 July 2009 by Jim Purbrick

As usual I headed down to the Metropole on the sea front last week to attend the annual Develop conference in Brighton. Unusually, this time I was attending the Evolve day which shifts the focus from console development to online, mobile and social games, which I had helped create as …

read more

dConstructing dConstruct

Thu 18 September 2008 by Jim Purbrick

A couple of weeks ago the great and the good of web development descended on Brighton for the wonderful clearleft produced dconstruct conference and once again I’m glad I went along.

Steven Johnson kicked off with a talk about how Dr. John Snow’s innovative data visualization of a …

read more
Fork me on GitHub