While working on the server for a multiplayer game, I ended up with quite tangled structures for managing the Game and the Client connections.

struct Client {
    id: Uuid,
    game_id: Option<String>,
    // ...Connection Details here...
}

struct Game {
    id: String,
    clients_ids: Vec<Uuid>,
    // ...Other game state.
}

// These led to the following types for the shared state in the
// multi-threaded server.
type ClientsMap = Arc<RwLock<HashMap<Uuid, Client>>>;
type GamesMap = Arc<RwLock<HashMap<String, Game>>>;

This resulted in the following when updating the state of the Game that then needed to update all of the Clients.

// First we need to get the game id:
let game_id = clients 
    .read()
    .await
    .get(id)
    .and_then(|client| client.game_id.to_owned())
    .unwrap();

// Then update all the relevant clients:
 
clients
    .read()
    .await
    .iter()
    .filter(|(_, client)| {
        if let Some(ref client_game_id) = client.game_id {
            client_game_id == game_id
        } else {
            false
        }
    })
    .try_for_each(|(_, client)| {
        // Send message to each client.
    })
Filtering all the clients based on what Game they are in before sending them a message.

It seemed better to maintain a HashMap of both Game ID to the relevant clients as well as to the Games themselves:

let game = game_ids_to_games.read().await.get(&game_id);
let clients = game_ids_to_clients.read().await.get(&game_id).clients;

However there is a snag: Due to the ownership and borrowing rules in Rust, a Game can only belong to one HashMap... Maybe a MultiMap could help us overcome this?

Enter... MultiMaps

Multimaps allow a Key-Value store with access to Values from two different Keys. Check out the crate docs here. I was hoping for an interface like the following (note I'm omitting the sync primitives on the Multimap for clarity, I'll show the full type later):

let magic_multimap: MultiMap<GameId, ClientId, Game> = MultiMap::new();

// When we have a Game ID
let game = magic_multimap.get(&game_id);
// When we have a Client ID
let game = magic_multimap.get_alt(&client_id);

And this may have worked if we only ever wanted to have one player in the game. This becomes apparent when we try to use it:

let magic_multimap: MultiMap<GameId, ClientId, Game> = MultiMap::new();

let game = Game::new();
let client = Client::new();
magic_multimap.insert(game.id.to_owned(), client.id.to_owned(), game);

let other_client = Client::new();
magic_multimap.insert(game.id.to_owned(), other_client.id.to_owned(), game); // Use of moved value, game.

Ah... So we need to share the Game anyway. How do we do this? More Arc!

let magic_multimap: MultiMap<GameId, ClientId, Arc<RwLock<Game>>> = MultiMap::new();

let game = Arc::new(RwLock::new(Game::new()));
let client = Client::new();
magic_multimap.insert(game.id.to_owned(), client.id.to_owned(), Arc::clone(&game));

let other_client = Client::new();
magic_multimap.insert(game.id.to_owned(), other_client.id.to_owned(), Arc::clone(&game));

Okay, but there is a snag. When a Game is created or has no active players, it has no Clients. That means that we have to be able to create an entry without a Client:

let magic_multimap: MultiMap<GameId, Option<ClientId>, Arc<RwLock<Game>>> = MultiMap::new();

let game = Arc::new(RwLock::new(Game::new()));
magic_multimap.insert(game.id.to_owned(), None, Arc::clone(&game));
let client = Client::new();
magic_multimap.insert(game.id.to_owned(), Some(client.id.to_owned()), Arc::clone(&game));

So the final type ends up as (now with sync primitives shown):

type GamesMap = Arc<RwLock<MultiMap<GameId, Option<ClientId>, Arc<RwLock<Game>>>>>;

This works, but its usage when retrieving the items was still clunky, as the Option for the alternate key needs to own the value it contains, even if we are passing it by reference for the lookup:

let client_id_to_find = Uuid::v4::parse_str("b3f3a48a-a916-4732-b908-646c0b8240c5").unwrap();
games.get_alt(&Some(client_id_to_find.to_owned())).unwrap();

Instead of this, I think it is preferable to just have two HashMaps, but have the values set as Arcs pointing to the relevant games. This is similar to the initial types, but wrapping our Game in sync primitives:

type ClientsMap = Arc<RwLock<HashMap<ClientId, Arc<RwLock<Game>>>>>;
type GamesMap = Arc<RwLock<HashMap<String, Arc<RwLock<Game>>>>>;

The Multimap itself is implemented as two HashMaps, so chances are the performance will be similar.

Learning

  • Multimaps are best suited to hierarchical structures where you can always insert both keys at once.
  • Try to avoid using Option values in maps due to the costly .to_owned() calls that are required (I would be interested to hear a way around this if anyone knows it).