Add backfill operation to ensure action consistency

ovidiuch · Feb 24, 2018 · 59a8d4c · 59a8d4c
1 parent f117778
commit 59a8d4c
Show file tree

Hide file tree

Showing 13 changed files with 375 additions and 63 deletions.
diff --git a/TODO.md b/TODO.md
@@ -95,17 +95,27 @@
 * [x] Add copy to clipboard btn to "Invite or play" screen
   * [x] Show share button when clicking on "2P insert coin"
 * [x] [BEAUTIFUL MVP]
-* [ ] Create actionId, link actions to prev actions, ensuring consistency
-* [ ] Create action backfill if user has old state and new actions
-* [ ] Throttle key down events
-* [ ] Minimize network communication: Don't send noop actions
-* [ ] Minimize state footprint
-* [ ] Freeze game on player disconnect (Keep seat taken in case user returns)
+* [x] Ensure action consistency
+  * [x] Create action backfill if user has old state and new actions
+    * [x] Create action.id, action.prevId and game.player.lastActionId
+    * [x] Store actions on the server
+    * [x] Create backfill operation
 * [ ] Index page with preview of all existing games
   * [ ] Batch actions
   * [ ] Algorithm for distributing events from bundled messages in time
         Calc time of each event in min-max interval and map [0, 1] value to [server timestamp of last received message...now...1s]
 * [ ] Log errors and stats
 * [ ] [1.0]
+
+OPTIMIZATIONS
+
+* [ ] Minimize network communication: Don't send noop actions
+* [ ] Minimize state footprint
+* [ ] Profile browser performance (detect unnecessary renders)
+
+BACKLOG
+
+* [ ] Freeze game on player disconnect (Keep seat taken in case user returns)
+* [ ] Throttle key down events
 * [ ] Create drop shadow from active Tetromino
-* [ ] Sounds?
+* [ ] Sounds
diff --git a/actions.js b/actions.js
@@ -1,5 +1,6 @@
 /* global performance */
 // @flow
+// TODO: Split actions file
 
 import raf from 'raf';
 
@@ -10,6 +11,7 @@ import { getCurUser } from './reducers/cur-user';
 
 import type { UserId, User, GameId, Game } from './types/state';
 import type {
+  ActionId,
   AuthAction,
   LoadGameAction,
   JoinGameAction,
@@ -50,26 +52,33 @@ export function joinGame(gameId: GameId, user: User): JoinGameAction {
   return {
     type: 'JOIN_GAME',
     payload: {
+      actionId: 0,
+      prevActionId: 0,
+      userId: user.id,
       gameId,
       user
     }
   };
 }
 
 export function playerReady(): ThunkAction {
-  return decorateAction(({ userId, gameId }) => ({
+  return decorateGameAction(({ actionId, prevActionId, userId, gameId }) => ({
     type: 'PLAYER_READY',
     payload: {
+      actionId,
+      prevActionId,
       userId,
       gameId
     }
   }));
 }
 
 export function playerPause(): ThunkAction {
-  return decorateAction(({ userId, gameId }) => ({
+  return decorateGameAction(({ actionId, prevActionId, userId, gameId }) => ({
     type: 'PLAYER_PAUSE',
     payload: {
+      actionId,
+      prevActionId,
       userId,
       gameId
     }
@@ -120,9 +129,11 @@ export function cancelGameFrame() {
 }
 
 export function drop(rows: number): ThunkAction {
-  return decorateAction(({ userId, gameId }) => ({
+  return decorateGameAction(({ actionId, prevActionId, userId, gameId }) => ({
     type: 'DROP',
     payload: {
+      actionId,
+      prevActionId,
       userId,
       gameId,
       rows
@@ -131,69 +142,83 @@ export function drop(rows: number): ThunkAction {
 }
 
 export function moveLeft(): ThunkAction {
-  return decorateAction(({ userId, gameId }) => ({
+  return decorateGameAction(({ actionId, prevActionId, userId, gameId }) => ({
     type: 'MOVE_LEFT',
     payload: {
+      actionId,
+      prevActionId,
       userId,
       gameId
     }
   }));
 }
 
 export function moveRight(): ThunkAction {
-  return decorateAction(({ userId, gameId }) => ({
+  return decorateGameAction(({ actionId, prevActionId, userId, gameId }) => ({
     type: 'MOVE_RIGHT',
     payload: {
+      actionId,
+      prevActionId,
       userId,
       gameId
     }
   }));
 }
 
 export function rotate(): ThunkAction {
-  return decorateAction(({ userId, gameId }) => ({
+  return decorateGameAction(({ actionId, prevActionId, userId, gameId }) => ({
     type: 'ROTATE',
     payload: {
+      actionId,
+      prevActionId,
       userId,
       gameId
     }
   }));
 }
 
 export function enableAcceleration(): ThunkAction {
-  return decorateAction(({ userId, gameId }) => ({
+  return decorateGameAction(({ actionId, prevActionId, userId, gameId }) => ({
     type: 'ENABLE_ACCELERATION',
     payload: {
+      actionId,
+      prevActionId,
       userId,
       gameId
     }
   }));
 }
 
 export function disableAcceleration(): ThunkAction {
-  return decorateAction(({ userId, gameId }) => ({
+  return decorateGameAction(({ actionId, prevActionId, userId, gameId }) => ({
     type: 'DISABLE_ACCELERATION',
     payload: {
+      actionId,
+      prevActionId,
       userId,
       gameId
     }
   }));
 }
 
 export function appendPendingBlocks(): ThunkAction {
-  return decorateAction(({ userId, gameId }) => ({
+  return decorateGameAction(({ actionId, prevActionId, userId, gameId }) => ({
     type: 'APPEND_PENDING_BLOCKS',
     payload: {
+      actionId,
+      prevActionId,
       userId,
       gameId
     }
   }));
 }
 
 export function ping(): ThunkAction {
-  return decorateAction(({ userId, gameId }) => ({
+  return decorateGameAction(({ actionId, prevActionId, userId, gameId }) => ({
     type: 'PING',
     payload: {
+      actionId,
+      prevActionId,
       userId,
       gameId,
       time: Date.now()
@@ -212,14 +237,30 @@ function scheduleFrame(cb) {
   });
 }
 
-type ActionDecorator = ({ gameId: GameId, userId: UserId }) => Action;
+type GameActionDecorator = ({
+  actionId: ActionId,
+  prevActionId: ActionId,
+  gameId: GameId,
+  userId: UserId
+}) => Action;
 
-function decorateAction(fn: ActionDecorator): ThunkAction {
+function decorateGameAction(fn: GameActionDecorator): ThunkAction {
   return (dispatch: Dispatch, getState: GetState) => {
     const state = getState();
+
     const userId = getCurUser(state).id;
-    const gameId = getCurGame(state).id;
+    const curGame = getCurGame(state);
+
+    const player = getPlayer(curGame, userId);
+    const { lastActionId: prevActionId } = player;
+    const actionId = getActionId(prevActionId);
 
-    return dispatch(fn({ userId, gameId }));
+    return dispatch(fn({ actionId, prevActionId, userId, gameId: curGame.id }));
   };
 }
+
+function getActionId(prevActionId: ActionId): ActionId {
+  // Ensure action ids never duplicate (only relevant if two actions occur
+  // within the same millisecond)
+  return Math.max(Date.now(), prevActionId + 1);
+}
diff --git a/multiplayer.md b/multiplayer.md
@@ -15,7 +15,7 @@ Lines are formed when a player drops their falling Tetromino piece on other stil
 
 ### Recursive line transferring
 
-It's possible for the blocks received from the other player as a penalty to be a blessing in disguise, and help the receiving player form lines upon the new blocks' arrival. These blocks create the opposite effect for the receiving player, as they offer extra points instead of a penalty. To avoid infinite recursion, these lines are no longer transferred back to the player which created the original lines.
+~~It's possible for the blocks received from the other player as a penalty to be a blessing in disguise, and help the receiving player form lines upon the new blocks' arrival. These blocks create the opposite effect for the receiving player, as they offer extra points instead of a penalty. To avoid infinite recursion, these lines are no longer transferred back to the player which created the original lines.~~ This functionality was removed in favor of a simpler, easier to understand game dynamic.
 
 ### Pushing up the falling Tetromino
 
@@ -37,3 +37,42 @@ Actions are synced between users over the network and should follow these rules:
 * **TODO:** Network optimization: Actions should be batched. Holding a key pressed can yield a dozen actions per second and in these cases it's unrealistic to expect clients to reliably send and receive messages at such high frequency.
 
 These rules tie into each other and overlap, but it's useful to keep each in mind when designing action payloads.
+
+## Ensuring action consistency
+
+### Context
+
+When a user loads a game, the server returns the current state snapshot at the time of the request, already converted into a server-side rendered HTML output. Upon receiving the initial HTML, the client starts fetching JS assets and once they're received it runs the client-side code, which _hydrates_ the static HTML received initially from the server. At this point a socket connection is opened with the server, instructing it to send the client any new action other (active) players dispatch for the loaded game.
+
+### Problem
+
+From the time the server returns the initial snapshot, to the time the client opens the socket connection, other players might've authored new actions which the connecting user needs to also receive, lest he get the game state out of sync. In other words, once a new user subscribes to receive a game's actions, a **backfill** operation might be needed.
+
+### Solution
+
+#### Short term action pool
+
+First off, the server needs to retain actions for a short time window, before discarding them to rely solely on the reduced state snapshot.
+
+> TODO: GC strategy for short-term action pool (ie. make it short term)
+
+#### Action id
+
+In order to know that a new action cannot be applied on a state snapshot, there must be a connection between the state snapshot and the last action applied.
+
+To be able to identify a **valid chain of actions**, actions will also point to the previous action.
+
+#### Backfill
+
+While the (async) backfill operation is underway, real time actions can still be received. This means that:
+
+1. Real time actions received must be stored in a secondary client state location until backfill has completed.
+2. Upon backfill completion, we merge the returned actions with other recent actions that might've been received via websocket in the meantime, remove duplicates, and dispatch them into the the local Redux store. From here on new actions are dispatched as they are received. We assume an open websocket connection does not drop messages.
+
+#### How does the action id look like?
+
+The action id is a local timestamp, separate for each player. Being a timestamp, it allows us to fast forward events while still conveying the rhythm in which the actions were performed.
+
+Caveat: To ensure action order consistency, the action id needs to be unique. So each player will ensure a new action's id is higher than the id of the previous action, in the highly unlikely event that two actions are dispatched in the same millisecond.
+
+> **Quirk:** Player state is initiated with `lastActionId` equal to `0`, and `JOIN_GAME` actions also have `actionId` set to `0`.
diff --git a/package.json b/package.json
@@ -53,7 +53,7 @@
     "eslint-plugin-flowtype": "^2.42.0",
     "eslint-plugin-import": "^2.8.0",
     "eslint-plugin-react": "^7.6.0",
-    "flow-bin": "^0.65.0",
+    "flow-bin": "^0.66.0",
     "flow-typed": "^2.3.0",
     "html-webpack-plugin": "^2.30.1",
     "identity-obj-proxy": "^3.0.0",