While property based tests proved to be a powerful tool for finding
and fixing problems with ReactVR
the limitations of the simplistic
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
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
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
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
does not need to send state syncs at all, making it significantly more
clientPredictionConsistency which I renamed
resyncConsistency to make the differences between the two optimistic
consistency policies clear.
eyeballing several games of ReactVR Pairs suggested that the new
consistency mechanism was working as intended, but finding all of the
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
replayConsistency result in all
clients being eventually consistent for thousands of sequences of actions.
With my tests passing I had high confidence that
was working and didn’t impose any limitations on event ordering making
it a much more general and efficient solution than
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.
Building Safety in to Social VR
Testing Replicated Redux
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
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
Creating A Safe Environment For People In VR
At the 3rd Party Dev State of the Union at EVE Fanfest 2016 earlier this year, CCP FoxFour drew my attention to a limitation of the current approach used by crestmatic to generate CREST documentation: it only discovers resources always reachable from the API root from the perspective of the ...read more
Strange Tales From Other Worlds
Towards A Generic Media Type System
The early days of RESTful hypermedia API design tends to involve lots of homogeneous collections. In the case of CREST vnd.ccp.eve.Api-v1 pointed to the logged in vnd.ccp.eve.ccp.Capsuleer-v1 which pointed to a vnd.eve.ccp.CharacterCollection-v1 of contacts which pointed to many vnd.ccp ...read more
A year ago I gave a talk at EVE Vegas about building RESTful CREST applications. My #1 recommendation was to specify representations in requests, but that’s hard to do when there is little documentation on which representations are available and what they contain.
Fortunately CREST is self describing: send ...read more
Free Tests For Everyone!
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
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
There have been a number of blog posts recently about exciting new organisational structures. As Cory points out “Every early stage company thinks it has reinvented management”: a very dangerous belief when betting on a new organisational structure can be much riskier than betting on the wrong product.
It starts ...read more
Beyond Time Dilation?
EVE online is a remarkable game. On Monday over 2000 people spent over 20 hours destroying virtual spaceships worth 200,000 USD in real money in what was the likely the largest battle in a video game ever. That EVE is capaple of supporting such large engagements is an amazing ...read more
In mid-2004 I first started exploring Second Life. Version 1.4 had just been released and Philip Rosedale had said in the press release “My fantasy is to be Uma Thurman in Kill Bill, and now I can. I’d pay $10 for her yellow jumpsuit and sword moves and ...read more