# Store FIFO - Put Your Games in Order

Make sure you have everything you need before proceeding:

synopsis

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:

Copy 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) (opens new window), 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:

    Copy 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. } proto checkers next_game.proto View source
  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:

    Copy message StoredGame { ... string beforeId = 8; // Pertains to the FIFO. Toward head. string afterId = 9; // Pertains to the FIFO. Toward tail. } proto checkers stored_game.proto View source
  3. There must be an "ID" that indicates no game. Use "-1", which you save as a constant:

    Copy const ( NoFifoIdKey = "-1" ) x checkers types keys.go View source
  4. Adjust the default genesis values, so that it has proper head and tail:

    Copy func DefaultGenesis() *GenesisState { return &GenesisState{ ... NextGame: &NextGame{ ... FifoHead: NoFifoIdKey, FifoTail: NoFifoIdKey, }, } } x checkers types genesis.go View source

Instruct Ignite CLI and Protobuf recompile the files:

Copy $ 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:

    Copy 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 } x checkers keeper stored_game_in_fifo.go View source

    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:

    Copy 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 } } x checkers keeper stored_game_in_fifo.go View source

    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:

    Copy ... storedGame := types.StoredGame{ ... BeforeId: types.NoFifoIdKey, AfterId: types.NoFifoIdKey, } x checkers keeper msg_server_create_game.go View source

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

    Copy ... k.Keeper.SendToFifoTail(ctx, &storedGame, &nextGame) k.Keeper.SetStoredGame(ctx, storedGame) ... x checkers keeper msg_server_create_game.go View source
  2. In the handler, when playing a move send the game back to the tail because it was freshly updated:

    Copy ... 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) ... x checkers keeper msg_server_play_move.go View source

    Note that you also need to call SetNextGame.

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

    Copy ... 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) ... x checkers keeper msg_server_reject_game.go View source

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 (opens new window), play moves (opens new window), and reject games (opens new window). Also add BeforeId and AfterId in your value requirements on StoredGame as you create games (opens new window) and play moves (opens new window).

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:

Copy 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) } x checkers keeper msg_server_create_game_fifo_test.go View source

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

Copy 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) } x checkers keeper msg_server_play_move_fifo_test.go View source

What happens when you have two games and reject the older one (opens new window)? Or have three games and reject the middle one?

Copy 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) } x checkers keeper msg_server_reject_game_fifo_test.go View source

# Interact via the CLI

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

Copy $ 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?

    Copy $ checkersd query checkers show-next-game

    This should print:

    Copy 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?

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

    This should print:

    Copy 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?

    Copy $ checkersd query checkers show-stored-game 0

    Because it is the only game, this should print:

    Copy StoredGame: afterId: "-1" # Nothing because it is alone beforeId: "-1" # Nothing because it is alone ...
  4. And if you create another game?

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

    This should print:

    Copy 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?

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

    This should print:

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

    Run:

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

    This should print:

    Copy 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?

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

    This should print:

    Copy 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?

    Copy $ checkersd query checkers show-stored-game 2

    This should print:

    Copy 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?

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

    This prints:

    Copy 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:

    Copy $ checkersd query checkers show-stored-game 0

    This prints:

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

    And:

    Copy $ checkersd query checkers show-stored-game 1

    This prints:

    Copy 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.