Prioritized Commitments for Interactive

[connor4312]

This is a small draft specification for implementation of the new Interactive feature. Please leave any feedback or suggestions you have!

For background, etags were built into interactive so that state can be maintained between the game client and server once the server becomes capable of changing state and providing updates on its own. Each document and meta property is tagged with an etag, and to change the state of that resource the client must provide its current etag. This ensures that the client is aware of the resource's state and does not cause invalid transition.

We chose etags as the means for concurrency control in Interactive v2.0. A few undesirable characteristics have emerged from them. Many of these I've heard from other developers, several of these I've learned myself when writing clients and integrations:

• In realtime scenarios, the logical overhead of dealing with etags, retries, and awaiting updates slows things down. It's not optimistic.
• This logic can become devilishly complicated, and easy to mess up.
• Aesthetically, etags add bloat and complexity to an otherwise simple CRUD API

In this short document, I propose a 'weakly' conflict-free method of concurrency control. We drop transactional verbosity and allow for ahead-of-time definitions of priority to assist the service in making a decision if conflicts are discovered.

Implementation of this method is non-breaking on the existing protocol.

Overview

We will keep an incrementing counter on the server-side and share it with the client. The client must include the last counter value it saw in packets it sends up.

Internally every resource and metadata property in interactive will be tagged with three values. In TypeScript notation:

interface Field<T> {
    /**
     * The current value stored in the field.
     */
    value: T;

    /**
     * The sequence number of the packet that last updated the field.
     */
    updateSeqNumber: number;

    /**
     * The priority value of the packet that last updated the field, or zero.
     */
    updatePriority: number;
}

Update that the client sends are tagged with a priority. We use sequencing to determine if a conflict occurred and priority to decide the winner of the conflict.

Conflict Resolution

Take conflicting changes C and S, where C is being submitted by client and S is already persisted on the server. For each property in C ∩ S, the following cases arise:

1. If C.sequenceNumber > S.sequenceNumber, then apply C's change;
2. If C.sequenceNumber ≤ S.sequenceNumber ∧ C.priority ≠ S.priority, then pick the change with the greater priority value;
3. If C.sequenceNumber < S.sequenceNumber ∧ C.priority = S.priority, then pick S's change. If a conflict occurs, the client will need to correct it later or the developer will need to adjust their priorities so that the conflict can be resolved in a happier case;
4. If C.sequenceNumber = S.sequenceNumber ∧ C.priority = S.priority, then pick C. This indicates the client received the update that occurred as a result of S firing previously and wants to subsequently update it (and no packets were sent from the server since that update.

Protocol Changes

• A sequence counter will be stored on the Interactive server. Each packet that the server sends includes a seq integer, and each packet the client sends up must include the last seq it saw.
• The params in update methods now optionally take a priority field, which may be any signed int32. It defaults to 0.
• Error code values dealing with conflicted etags will be removed.

In order to avoid breaking changes:

• In cases where the seq number is not provided, it will be treated as the current sequence number, giving the client priority in all case.
  • This is not problematic, as no one but the client updates things currently! We should get our official libraries up to date in the near future, however.
• Etag fields will continue to exist on all resources, but these will be empty strings.
• Etags passed to the interactive service will be ignored.

For example, a participant update call might look like this:

{
  "type": "method",
  "id": 123,
  "method": "updateParticipants",
  "seq": 1234,
  "params": {
    "priority": 1,
    "participants": [
      {
        "sessionID": "505cfe7c123f40e78c78754103d16531",
        "groupID": "red_team",
        "meta": {
          "is_awesome": true
        }
      }
    ]
  }
}

Note that there's no need for the value in metadata any longer. Although consumers may still provide this, it'll be stored as a literal object {"value":true}.

Internal Implementation

The seq counter will be stored in the websocket's RPC layer to be a first-class citizen of the protocol. It'll be stored as an signed, 32-bit integer, starting at zero, and atomically incrementing on each outgoing packet. To deal with wrapping, we assume the client is less than 2³¹ updates behind the server. A sequence number b comes after a if by integer subtraction b − a > 0.

As mentioned, all data fields are stored with the current value and the sequence number and priority of their last update; this provides the information needed to conduct conflict resolution. Memory overhead is increased by 8 bytes per data field, but the current 24-byte etag-handling data structure can be eliminated, and the data structure as proposed would provide greater cache locality than does the current etag implementation.

Methods will be provided in custom aggregations will be able to set the priority of updates. Aggregation updates' default priority will be zero.

[kateract]

I'm a vote in support of this change.

• I was considering the ETAG structure as a necessary evil
• The sequence number and priority method really gives control over conflict resolution over to the developer
• The sequence number scheme also allows for some missing/out of order message detection for the client as well
• The developer can define levels of importance for different events, such as default priority for button presses, priority 3 for board switches, priority 5 for bans(disable) etc.
• sequence/priority is concurrency management that also has semantic value, the etag was just a concurrency check with no relevance

[connor4312]

Thanks for everyone's feedback, here and through other channels. Implementation of these changes as specified above is under way.