diff options
Diffstat (limited to 'docs/state_resolution.rst')
| -rw-r--r-- | docs/state_resolution.rst | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/docs/state_resolution.rst b/docs/state_resolution.rst new file mode 100644 index 0000000000..fec290dd79 --- /dev/null +++ b/docs/state_resolution.rst @@ -0,0 +1,51 @@ +State Resolution +================ +This section describes why we need state resolution and how it works. + + +Motivation +----------- +We want to be able to associate some shared state with rooms, e.g. a room name +or members list. This is done by having a current state dictionary that maps +from the pair event type and state key to an event. + +However, since the servers involved in the room are distributed we need to be +able to handle the case when two (or more) servers try and update the state at +the same time. This is done via the state resolution algorithm. + + +State Tree +------------ +State events contain a reference to the state it is trying to replace. These +relations form a tree where the current state is one of the leaf nodes. + +Note that state events are events, and so are part of the PDU graph. Thus we +can be sure that (modulo the internet being particularly broken) we will see +all state events eventually. + + +Algorithm requirements +---------------------- +We want the algorithm to have the following properties: +- Since we aren't guaranteed what order we receive state events in, except that + we see parents before children, the state resolution algorithm must not depend + on the order and must always come to the same result. +- If we receive a state event whose parent is the current state, then the + algorithm will select it. +- The algorithm does not depend on internal state, ensuring all servers should + come to the same decision. + +These three properties mean it is enough to keep track of the current state and +compare it with any new proposed state, rather than having to keep track of all +the leafs of the tree and recomputing across the entire state tree. + + +Current Implementation +---------------------- +The current implementation works as follows: Upon receipt of a newly proposed +state change we first find the common ancestor. Then we take the maximum +across each branch of the users' power levels, if one is higher then it is +selected as the current state. Otherwise, we check if one chain is longer than +the other, if so we choose that one. If that also fails, then we concatenate +all the pdu ids and take a SHA1 hash and compare them to select a common +ancestor. |