game-fifo.md

title	order	description	tag
Store FIFO - Put Your Games in Order	11	You prepare to expire games	deep-dive

Store FIFO - Put Your Games in Order

Make sure you have everything you need before proceeding:

• You understand the concepts of ABCI, Protobuf, and of a doubly-linked list.
• Go is installed.
• You have the checkers blockchain codebase with MsgRejectGame and its handling. If not, follow the previous steps or check out the relevant version.

In this section, you will deal with:

• The FIFO data structure
• FIFO unit tests

You will learn:

• Modularity and data organization styles

In the previous step you added a way for players to reject a game. There are two ways for a game to advance through its lifecycle until resolution, win or draw: play and reject.

Why would you reject?

Game inactivity could become a factor. What if a player never shows up again? Should a game remain in limbo forever?

Eventually you want to let players wager on the outcome of games, so you do not want games remaining in limbo if they have value assigned. For this reason, you need a way for games to be forcibly resolved if one player stops responding.

The simplest mechanism to expire a game is to use a deadline. If the deadline is reached, then the game is forcibly terminated and expires. The deadline is pushed back every time a move is played.

To enforce the termination it is a good idea to use the EndBlock part of the ABCI protocol. The call EndBlock is triggered when all transactions of the block are delivered, and allows you to tidy up before the block is sealed. In your case, all games that have reached their deadline will be terminated.

How do you find all the games that have reached their deadline? You could use a pseudo-code like:

findAll(game => game.deadline < now)

This approach is expensive in terms of computation. The EndBlock code should not have to pull up all games out of the storage just to find a few that are relevant. Doing a findAll costs O(n), where n is the total number of games.

How can you reject?

You need another data structure. The simplest option is a First-In-First-Out (FIFO) that is constantly updated, so that:

• When games are played, they are taken out of where they are and sent to the tail.
• Games that have not been played for the longest time eventually rise to the head.

When terminating expired games in EndBlock, you deal with the expired games that are at the head of the FIFO. Do not stop until the head includes an ongoing game. The cost is:

• O(1) on each game creation and gameplay.
• O(k) where k is the number of expired games on each block.
• k <= n where n is the number of games that exist.

k is still an unbounded number of operations. However, if you use the same expiration duration on each game, for k games to expire together in a block they would all have to have had a move in the same previous block (give or take the block before or after). In the worst case, the largest EndBlock computation will be proportional to the largest regular block in the past. This is a reasonable risk to take.

Remember: this only works if the expiration duration is the same for all games, instead of being a parameter left to a potentially malicious game creator.

New information

How do you implement a FIFO from which you extract elements at random positions? Choose a doubly-linked list:

1. You must remember the game ID at the head to pick expired games, and at the tail to send back fresh games. The existing NextGame object is a useful, as it is already expandable. Add to its Protobuf declaration:

   message NextGame {
       ...
       string fifoHead = 3; // Will contain the index of the game at the head.
       string fifoTail = 4; // Will contain the index of the game at the tail.
   }

2. To make extraction possible, each game must know which other game takes place before it in the FIFO, and which after. Store this double link information in StoredGame. Add them to the game's Protobuf declaration:

   message StoredGame {
       ...
       string beforeId = 8; // Pertains to the FIFO. Toward head.
       string afterId = 9; // Pertains to the FIFO. Toward tail.
   }

3. There must be an "ID" that indicates no game. Use "-1", which you save as a constant:

   const (
       NoFifoIdKey = "-1"
   )

4. Adjust the default genesis values, so that it has proper head and tail:

   func DefaultGenesis() *GenesisState {
       return &GenesisState{
           ...
           NextGame: &NextGame{
               ...
               FifoHead: NoFifoIdKey,
               FifoTail: NoFifoIdKey,
           },
       }
   }

Instruct Ignite CLI and Protobuf recompile the files:

$ ignite chain build

FIFO management

Now that the new fields are created, you need to update them to keep your FIFO up-to-date. It's better to create a separate file that encapsulates this knowledge. Create x/checkers/keeper/stored_game_in_fifo.go with the following:

1. A function to remove from the FIFO:

   func (k Keeper) RemoveFromFifo(ctx sdk.Context, game *types.StoredGame, info *types.NextGame) {
       // Does it have a predecessor?
       if game.BeforeId != types.NoFifoIdKey {
           beforeElement, found := k.GetStoredGame(ctx, game.BeforeId)
           if !found {
               panic("Element before in Fifo was not found")
           }
           beforeElement.AfterId = game.AfterId
           k.SetStoredGame(ctx, beforeElement)
           if game.AfterId == types.NoFifoIdKey {
               info.FifoTail = beforeElement.Index
           }
           // Is it at the FIFO head?
       } else if info.FifoHead == game.Index {
           info.FifoHead = game.AfterId
       }
       // Does it have a successor?
       if game.AfterId != types.NoFifoIdKey {
           afterElement, found := k.GetStoredGame(ctx, game.AfterId)
           if !found {
               panic("Element after in Fifo was not found")
           }
           afterElement.BeforeId = game.BeforeId
           k.SetStoredGame(ctx, afterElement)
           if game.BeforeId == types.NoFifoIdKey {
               info.FifoHead = afterElement.Index
           }
           // Is it at the FIFO tail?
       } else if info.FifoTail == game.Index {
           info.FifoTail = game.BeforeId
       }
       game.BeforeId = types.NoFifoIdKey
       game.AfterId = types.NoFifoIdKey
   }

   The game passed as an argument is not saved in storage here, even if it was updated. Only its fields in memory are adjusted. The before and after games are saved in storage. Do a SetStoredGame after calling this function to avoid having a mix of saves and memory states. The same applies to SetNextGame.

2. A function to send to the tail:

   func (k Keeper) SendToFifoTail(ctx sdk.Context, game *types.StoredGame, info *types.NextGame) {
       if info.FifoHead == types.NoFifoIdKey && info.FifoTail == types.NoFifoIdKey {
           game.BeforeId = types.NoFifoIdKey
           game.AfterId = types.NoFifoIdKey
           info.FifoHead = game.Index
           info.FifoTail = game.Index
       } else if info.FifoHead == types.NoFifoIdKey || info.FifoTail == types.NoFifoIdKey {
           panic("Fifo should have both head and tail or none")
       } else if info.FifoTail == game.Index {
           // Nothing to do, already at tail
       } else {
           // Snip game out
           k.RemoveFromFifo(ctx, game, info)
   
           // Now add to tail
           currentTail, found := k.GetStoredGame(ctx, info.FifoTail)
           if !found {
               panic("Current Fifo tail was not found")
           }
           currentTail.AfterId = game.Index
           k.SetStoredGame(ctx, currentTail)
   
           game.BeforeId = currentTail.Index
           info.FifoTail = game.Index
       }
   }

   Again, it is advisable to do SetStoredGame and SetNextGame after calling this function.

FIFO Integration

With these functions ready, it is time to use them in the message handlers.

1. In the handler when creating a new game, set default values for BeforeId and AfterId:

   ...
   storedGame := types.StoredGame{
       ...
       BeforeId:  types.NoFifoIdKey,
       AfterId:   types.NoFifoIdKey,        
   }

   Send the new game to the tail because it is freshly created:

   ...
   k.Keeper.SendToFifoTail(ctx, &storedGame, &nextGame)
   k.Keeper.SetStoredGame(ctx, storedGame)
   ...

2. In the handler, when playing a move send the game back to the tail because it was freshly updated:

   ...
   nextGame, found := k.Keeper.GetNextGame(ctx)
   if !found {
       panic("NextGame not found")
   }
   k.Keeper.SendToFifoTail(ctx, &storedGame, &nextGame)
   storedGame.Game = game.String()
   ...
   k.Keeper.SetNextGame(ctx, nextGame)
   ...

   Note that you also need to call SetNextGame.

3. In the handler, when rejecting a game remove the game from the FIFO:

   ...
   nextGame, found := k.Keeper.GetNextGame(ctx)
   if !found {
       panic("NextGame not found")
   }
   k.Keeper.RemoveFromFifo(ctx, &storedGame, &nextGame)
   k.Keeper.RemoveStoredGame(ctx, msg.IdValue)
   ...
   k.Keeper.SetNextGame(ctx, nextGame)
   ...

You have implemented a FIFO that is updated but never really used.

Unit tests

At this point, your previous unit tests are failing, so they must be fixed. Add FifoHead and FifoTail in your value requirements on NextGame as you create games, play moves, and reject games. Also add BeforeId and AfterId in your value requirements on StoredGame as you create games and play moves.

Next, you should add more specific FIFO tests. For instance, testing what happens to NextGame and StoredGame as you create up to three new games:

func TestCreate3GamesHasSavedFifo(t *testing.T) {
    msgSrvr, keeper, context := setupMsgServerCreateGame(t)
    msgSrvr.CreateGame(context, &types.MsgCreateGame{
        Creator: alice,
        Red:     bob,
        Black:   carol,
    })

    msgSrvr.CreateGame(context, &types.MsgCreateGame{
        Creator: bob,
        Red:     carol,
        Black:   alice,
    })
    nextGame2, found2 := keeper.GetNextGame(sdk.UnwrapSDKContext(context))
    require.True(t, found2)
    require.EqualValues(t, types.NextGame{
        Creator:  "",
        IdValue:  3,
        FifoHead: "1",
        FifoTail: "2",
    }, nextGame2)
    game1, found1 := keeper.GetStoredGame(sdk.UnwrapSDKContext(context), "1")
    require.True(t, found1)
    require.EqualValues(t, types.StoredGame{
        Creator:   alice,
        Index:     "1",
        Game:      "*b*b*b*b|b*b*b*b*|*b*b*b*b|********|********|r*r*r*r*|*r*r*r*r|r*r*r*r*",
        Turn:      "b",
        Red:       bob,
        Black:     carol,
        MoveCount: uint64(0),
        BeforeId:  "-1",
        AfterId:   "2",
    }, game1)
    game2, found2 := keeper.GetStoredGame(sdk.UnwrapSDKContext(context), "2")
    require.True(t, found2)
    require.EqualValues(t, types.StoredGame{
        Creator:   bob,
        Index:     "2",
        Game:      "*b*b*b*b|b*b*b*b*|*b*b*b*b|********|********|r*r*r*r*|*r*r*r*r|r*r*r*r*",
        Turn:      "b",
        Red:       carol,
        Black:     alice,
        MoveCount: uint64(0),
        BeforeId:  "1",
        AfterId:   "-1",
    }, game2)

    msgSrvr.CreateGame(context, &types.MsgCreateGame{
        Creator: carol,
        Red:     alice,
        Black:   bob,
    })
    nextGame3, found3 := keeper.GetNextGame(sdk.UnwrapSDKContext(context))
    require.True(t, found3)
    require.EqualValues(t, types.NextGame{
        Creator:  "",
        IdValue:  4,
        FifoHead: "1",
        FifoTail: "3",
    }, nextGame3)
    game1, found1 = keeper.GetStoredGame(sdk.UnwrapSDKContext(context), "1")
    require.True(t, found1)
    require.EqualValues(t, types.StoredGame{
        Creator:   alice,
        Index:     "1",
        Game:      "*b*b*b*b|b*b*b*b*|*b*b*b*b|********|********|r*r*r*r*|*r*r*r*r|r*r*r*r*",
        Turn:      "b",
        Red:       bob,
        Black:     carol,
        MoveCount: uint64(0),
        BeforeId:  "-1",
        AfterId:   "2",
    }, game1)
    game2, found2 = keeper.GetStoredGame(sdk.UnwrapSDKContext(context), "2")
    require.True(t, found2)
    require.EqualValues(t, types.StoredGame{
        Creator:   bob,
        Index:     "2",
        Game:      "*b*b*b*b|b*b*b*b*|*b*b*b*b|********|********|r*r*r*r*|*r*r*r*r|r*r*r*r*",
        Turn:      "b",
        Red:       carol,
        Black:     alice,
        MoveCount: uint64(0),
        BeforeId:  "1",
        AfterId:   "3",
    }, game2)
    game3, found3 := keeper.GetStoredGame(sdk.UnwrapSDKContext(context), "3")
    require.True(t, found3)
    require.EqualValues(t, types.StoredGame{
        Creator:   carol,
        Index:     "3",
        Game:      "*b*b*b*b|b*b*b*b*|*b*b*b*b|********|********|r*r*r*r*|*r*r*r*r|r*r*r*r*",
        Turn:      "b",
        Red:       alice,
        Black:     bob,
        MoveCount: uint64(0),
        BeforeId:  "2",
        AfterId:   "-1",
    }, game3)
}

What happens when you have two games and play once on the older one? Or have two games and play them twice in turn:

func TestPlayMove2Games2MovesHasSavedFifo(t *testing.T) {
    msgServer, keeper, context := setupMsgServerWithOneGameForPlayMove(t)
    msgServer.CreateGame(context, &types.MsgCreateGame{
        Creator: bob,
        Red:     carol,
        Black:   alice,
    })
    msgServer.PlayMove(context, &types.MsgPlayMove{
        Creator: carol,
        IdValue: "1",
        FromX:   1,
        FromY:   2,
        ToX:     2,
        ToY:     3,
    })

    msgServer.PlayMove(context, &types.MsgPlayMove{
        Creator: alice,
        IdValue: "2",
        FromX:   1,
        FromY:   2,
        ToX:     2,
        ToY:     3,
    })
    nextGame1, found1 := keeper.GetNextGame(sdk.UnwrapSDKContext(context))
    require.True(t, found1)
    require.EqualValues(t, types.NextGame{
        Creator:  "",
        IdValue:  3,
        FifoHead: "1",
        FifoTail: "2",
    }, nextGame1)
    game1, found1 := keeper.GetStoredGame(sdk.UnwrapSDKContext(context), "1")
    require.True(t, found1)
    require.EqualValues(t, types.StoredGame{
        Creator:   alice,
        Index:     "1",
        Game:      "*b*b*b*b|b*b*b*b*|***b*b*b|**b*****|********|r*r*r*r*|*r*r*r*r|r*r*r*r*",
        Turn:      "r",
        Red:       bob,
        Black:     carol,
        MoveCount: uint64(1),
        BeforeId:  "-1",
        AfterId:   "2",
    }, game1)
    game2, found2 := keeper.GetStoredGame(sdk.UnwrapSDKContext(context), "2")
    require.True(t, found2)
    require.EqualValues(t, types.StoredGame{
        Creator:   bob,
        Index:     "2",
        Game:      "*b*b*b*b|b*b*b*b*|***b*b*b|**b*****|********|r*r*r*r*|*r*r*r*r|r*r*r*r*",
        Turn:      "r",
        Red:       carol,
        Black:     alice,
        MoveCount: uint64(1),
        BeforeId:  "1",
        AfterId:   "-1",
    }, game2)
}

What happens when you have two games and reject the older one? Or have three games and reject the middle one?

func TestRejectMiddleGameHasSavedFifo(t *testing.T) {
    msgServer, keeper, context := setupMsgServerWithOneGameForRejectGame(t)
    msgServer.CreateGame(context, &types.MsgCreateGame{
        Creator: bob,
        Red:     carol,
        Black:   alice,
    })
    msgServer.CreateGame(context, &types.MsgCreateGame{
        Creator: carol,
        Red:     alice,
        Black:   bob,
    })
    msgServer.RejectGame(context, &types.MsgRejectGame{
        Creator: carol,
        IdValue: "2",
    })
    nextGame, found := keeper.GetNextGame(sdk.UnwrapSDKContext(context))
    require.True(t, found)
    require.EqualValues(t, types.NextGame{
        Creator:  "",
        IdValue:  4,
        FifoHead: "1",
        FifoTail: "3",
    }, nextGame)
    game1, found1 := keeper.GetStoredGame(sdk.UnwrapSDKContext(context), "1")
    require.True(t, found1)
    require.EqualValues(t, types.StoredGame{
        Creator:   alice,
        Index:     "1",
        Game:      "*b*b*b*b|b*b*b*b*|*b*b*b*b|********|********|r*r*r*r*|*r*r*r*r|r*r*r*r*",
        Turn:      "b",
        Red:       bob,
        Black:     carol,
        MoveCount: uint64(0),
        BeforeId:  "-1",
        AfterId:   "3",
    }, game1)
    game3, found3 := keeper.GetStoredGame(sdk.UnwrapSDKContext(context), "3")
    require.True(t, found3)
    require.EqualValues(t, types.StoredGame{
        Creator:   carol,
        Index:     "3",
        Game:      "*b*b*b*b|b*b*b*b*|*b*b*b*b|********|********|r*r*r*r*|*r*r*r*r|r*r*r*r*",
        Turn:      "b",
        Red:       alice,
        Black:     bob,
        MoveCount: uint64(0),
        BeforeId:  "1",
        AfterId:   "-1",
    }, game3)
}

Interact via the CLI

Time to explore the commands. You need to start afresh because you made numerous additions to the blockchain state:

$ ignite chain serve --reset-once

Do not forget to export alice and bob again, as explained in an earlier section.

1. Is the genesis FIFO information correctly saved?

   $ checkersd query checkers show-next-game

   This should print:

   NextGame:
     creator: ""
     fifoHead: "-1" # There is nothing
     fifoTail: "-1" # There is nothing
     idValue: "0"
   

2. If you create a game, is the game as expected?

   $ checkersd tx checkers create-game $alice $bob --from $bob
   $ checkersd query checkers show-next-game

   This should print:

   NextGame:
     creator: ""
     fifoHead: "0" # The first game you created
     fifoTail: "0" # The first game you created
     idValue: "1"
   

3. What about the information saved in the game?

   $ checkersd query checkers show-stored-game 0   

   Because it is the only game, this should print:

   StoredGame:
     afterId: "-1" # Nothing because it is alone
     beforeId: "-1" # Nothing because it is alone
   ...
   

4. And if you create another game?

   $ checkersd tx checkers create-game $alice $bob --from $bob
   $ checkersd query checkers show-next-game

   This should print:

   NextGame:
     creator: ""
     fifoHead: "0" # The first game you created
     fifoTail: "1" # The second game you created
     idValue: "2"
   

5. Did the games also store the correct values?

   $ checkersd query checkers show-stored-game 0 # The first game you created

   This should print:

   afterId: "1" # The second game you created
   beforeId: "-1" # No game
   ...
   

   Run:

   $ checkersd query checkers show-stored-game 1 # The second game you created

   This should print:

   afterId: "-1" # No game
   beforeId: "0" # The first game you created
   ...
   

   Your FIFO in effect has the game IDs [0, 1]. If you add a third game, your FIFO will be [0, 1, 2].

6. What happens if Bob plays a move in game 1, the game in the middle?

   $ checkersd tx checkers play-move 1 1 2 2 3 --from $bob
   $ checkersd query checkers show-next-game

   This should print:

   NextGame:
     creator: ""
     fifoHead: "0" # The first game you created
     fifoTail: "1" # The second game you created and on which Bob just played
     idValue: "3"
   

7. Is game 2 in the middle now?

   $ checkersd query checkers show-stored-game 2

   This should print:

   StoredGame:
     afterId: "1"
     beforeId: "0"
   ...
   

   Your FIFO now has the game IDs [0, 2, 1]. You see that game 1, which was played on, has been sent to the tail of the FIFO.

8. What happens if Alice rejects game 2?

   $ checkersd tx checkers reject-game 2 --from $alice
   $ checkersd query checkers show-next-game

   This prints:

   NextGame:
     creator: ""
     fifoHead: "0"
     fifoTail: "1"
     idValue: "3"
   

   There is no change because game 2 was in the middle, so it did not affect the head or the tail.

   Run the following two queries:

   $ checkersd query checkers show-stored-game 0

   This prints:

   StoredGame:
     afterId: "1"
     beforeId: "-1"
   ...
   

   And:

   $ checkersd query checkers show-stored-game 1

   This prints:

   StoredGame:
     afterId: "-1"
     beforeId: "0"
   ...
   

   Your FIFO now has the game IDs [0, 1]. Game 2 was correctly removed from the FIFO.

Next up

Having a list of games ordered by age is not enough to ascertain their staleness. You must also add an expiry date on each game to reach that decision. That is the goal of the next section.