PG optimistic operational transformation setup

Readme.txt

This postgres script provides an example for a system with 
soft resolution of state change conflicts.

In this system updates do not mutate rows in tables,
instead they insert new rows retaining versioning metadata.
It is possible to restore all actions and side effects post-mortem.

A client first fetches current state of data, and receives its version id.
Client does somemething that invokes operations on that data, and changes it. 
It then sends that data to server, with log of operation that led to it.
The request provides version identifier of state known to be "true".

If no new versions were created between that version and now,
server quickly inserts new row with updated state and operations
and notifies external listeners.

If server detects that object was updated concurrently, 
external operational transformation routine is invoked.
It takes history of operations since the base version
on the server and history of client's requested changes
and produces 2 new sets of operations for client and server.
When applied, both parties will have consensus over results. 
The order of changes is decided by whichever request is served 
by PG first.

Due to actions being asynchronous, there could be more outgoing 
operations by the time client gets server response. In that case
client rebases its actions on top of received operations and 
sends transformed operations to server again. 

in p2p scenarios, one peer can be selected as the master
to make all others rebase and validate their changes against
it without server involvement.

external.operational.tranformation.sql

CREATE TABLE characters(,
  serial id
  varchar(256) name,
  integer health,

  integer object_id, -- id of a first version of object
  integer version,
  integer previous_version,
  jsonb   operations -- array of operations happened in this version of document

)


-- I: game initializes boss, it gets id 123
INSERT INTO characters(health, name, version, operations) 
       VALUES(100, 'Boss', 1, operations)
       RETURNING *; 
       -- client gets: {id: 123, version: 1, object_id: 123, health: 100, name: 'Boss'}




-- II: user1 hits boss for 20 damage
UPDATE characters 
  SET health=80, previous_version=1, operations=[{"name": "decrement", "key": "health", "value": 20}], object_id=123
  WHERE object_id = 123
  RETURNING *;

  // server does check if any concurrent changes happened
  SELECT * FROM characters where object_id=123 and version > 1;
  -- 0 rows, no concurrency

  // trigger turns UPDATE into INSERT of a new version
  INSERT into characters(health, name, version, object_id, operations)
  VALUES(80, 'Boss', 2, 123, [{"name": "decrement", "key": "health", "value": 20}])

  -- client gets: {id: 124, version: 2, object_id: 123, health: 100, name: 'Boss'}




-- III: user2 debuffs boss for 50% of current health concurrently
UPDATE characters 
  SET health=80, previous_version=1, [{"name": "multiply", "key": "health", "value": 0.5}]
  WHERE id = 123
  RETURNING *;

  -- server does check if any concurrent changes happened
  SELECT * FROM characters where object_id=123 and version > 1;
  -- RETURN: 1 row, need to transform operation to conform updated history

  -- invoke external listener via socket, e.g. node.js with https://github.com/JoshData/jot
  -- to transform operations
  NOTIFY transform_operations, `{
    base:  {id: 123, version: 1, object_id: 123, health: 100, name: 'Boss'}, -- base operation
    left:  [{"name": "decrement", "key": "health", "value": 20}],            -- user1 history, the truth
    right: [{"name": "multiply", "key": "health", "value": 0.5}]                 -- user2 history
  }`;

  -- Use transformed operations to insert new version
  INSERT into characters(health, name, version, previous_version, object_id, operations)
                  VALUES(40,     'Boss', 3,     2,                123,       [{"name": "multiply", "key": "health", "value": 0.5}]);

  -- user2 gets transformed operation back
  --   {"id": 125, "version": 3, "object_id": 123, "health": 100, "name": "Boss",
  --    [{"name": "decrement", "key": "health", "value": 10}]} -- <<< Decrement by 10, not 20
    
  -- user1 gets untransformed operation
  -- user2 ignores this message, as it already has version 3 transformed
  NOTIFY clients_in_the_room, `
    {"id": 125, "version": 3, "object_id": 123, "health": 100, "name": "Boss", 
      [{"name": "multiply", "key": "health", "value": 0.5}]}
  `;





-- both clients can now rebase received operations
-- against optimistally buffered actions on clientside
-- and send their updates.