Les transactions redis

Pour expliquer ce dont il s'agit, je vais prendre l'exemple du jeu Beasts of Wanderia, un jeu en réseau en cours développement actif, qui se sert de transactions redis pour chacune des actions utilisateur.

Deux joueurs souhaitent se déplacer. Nous ne souhaitons pas que deux joueurs puissent se trouver à une même position. Que se passe-t-il si les deux joueurs décident d'aller au même endroit au même moment? Comment faire pour s'assurer que cette situation n'arrive pas?

1. Des transactions empêchent les joueurs de finir au même endroit

Instinctivement on pourrait se dire qu'il suffit de vérifier que la case est vide pour initier le déplacement. Mais cela ne suffit pas dans le cas d'un jeu en réseau, où chaque utilisateur dispose de son jeu de threads gérant ses actions indépendamment des autres joueurs. Si l'on se contentait de cette vérification, deux joueurs souhaitant se déplacer pourrait effectuer la vérification, voir que la case est vide, enclencher l'action de déplacement, pour finalement finir à deux au même endroit. Et une fois dans cette situation que faire ? Un rollback ? Mais de quel joueur? Quelle conséquence visuelle pour lui?

Non la solution est bien évidemment une transaction. Il faut bien que cet article serve à quelque chose.

Le rapport entre redis et un personnage?

Les données dans redis sont stockées sous la forme clef/valeur.

2. Les données d'un personnage en jeu dans redis, avec sa position

C'est à dire que pour une clef donnée, on pourra récupérer des données, grâce à la commande GET, sous la forme d'un tableau de bytes par exemple.

Le système de déplacement

Afin qu'un joueur se déplace, plusieurs informations nous intéressent. D'abord, nous avons besoin de connaître la direction de son déplacement, mais aussi sa position. Cette information se trouve dans les données qui lui sont propres, et qui sont affichées plus haut.

Enfin, nous avons également besoin de savoir si il y a d'autres joueurs sur cette carte, et où ils se trouvent. cette information se trouve ailleurs, dans les données propres à une carte, qui contiennent par ailleurs beaucoup plus de données.

L'algorithme consiste à itérer chaque joueur présent sur la carte du joueur, et à vérifier que l'un d'entre eux ne se trouve pas déjà là où le déplacement du joueur qui veut bouger l'aménerait.

Et les transactions dans tout ça ?

C'est là que ça se corse. S'il suffisait d'implémenter l'algorithme mentionné plus haut, le travail serait terminé en quelques minutes.

Non, cela ne suffit évidemment pas, il va falloir mettre les mains dans la doc.

Concrétement, les transactions redis

Une transaction redis est un ensemble d'opérations indivisible. Cela signifie que pour qu'une transaction réussisse, il faut que chacune des opérations qu'elle contient aient réussi.

Une transaction redis est dîte optimiste, car elle suppose qu'elle va réussir, et échoue si une donnée surveillée est modifiée durant son exécution

Les requêtes faites à redis sont les suivantes:

WATCH monPersonnage maCarte
GET monPersonnage
GET maCarte

[Transformer les données pour mettre à jour le cache via un algorithme côté backend]

MULTI
SET monPersonnage
SET maCarte
EXEC

On retrouve ici 3 grandes parties:

  • La partie WATCH: On liste les données qui vont intervenir dans notre transactions, et qui doivent être surveillées
  • L'obtention des données/l'execution de l'algorithme entre le WATCH et le MULTI
  • Le modifications avec les opérations SET pour mettre à jour les données, puis EXEC pour exécuter la transaction.

WATCH

Cette commande redis va permettre de spécifier quelle valeurs sont concernées par la transaction, l'idée étant que si au moment de l'appel de EXEC, des données précisées dans le WATCH ont été modifiées, la transaction échoue.

Après la requête WATCH, les valeur des clefs monPersonnage et maCarte sont obtenues par le backend via les deux GET.

MULTI

Le backend va alors exécuter son algorithme relatif au déplacement d'un joueur, puis va appeler MULTI pour spécifier le début de l'ensemble de commandes à exécuter par redis. Dans cet exemple, il s'agit de mettre à jour la carte et le personnage.

EXEC

Cette commande permet de terminer la transaction, et de demander l'exécution de ce qu'on trouve après le MULTI. Si aucune donnée n'a changé depuis le WATCH, la transaction réussit. Si l'une des données a changé, la transaction échoue.

Un peu de code

Afin de simplifier l'utilisation des transactions dans mon projet, j'ai mis en place une interface permettant de faciliter l'utilisation des transactions. Le langage est ici du go, mais cette logique pourrait s'appliquer à d'autres langages. La librarie redis utilisée est go-redis.

// Transaction execute transactional request on redis instance. Execution order is "Init->Prepare->Execute"
// Init step is to query some keys you don't know you need at first or perform some initialization on your data
// Prepare is the querying step on the keys you're watching
// Execute is the writing step on the keys you're watching
// All these steps will be re-executed each time transaction fails because of `redis.TxFailed`
// related transactions are executed in order of nesting, as it could need previous result from parent transaction
type Transaction interface {
	// Init can be used to get some key you need to watch but you don't know at first
  Init(client redis.Cmdable) error

  // Prepare will get data need for execution via Tx (no Set here)
  Prepare(tx *redis.Tx) error

  // Execute will write data to redis (no Get here)
  Execute(pipe redis.Pipeliner) error

  // KeyToWatch is expected to return all the keys that will be monitored by redis.Watch function
  KeyToWatch() []string
}

Cette interface découpe les transactions en 3 grandes parties:

  • Init() qui permet d'obtenir des données permettant d'initialiser la transaction sans appeler WATCH, afin de pouvoir analyser l'état des clefs concernant la transaction
  • Prepare(), qui est appelé après avoir effectué le WATCH des clefs retournées par la méthode KeyToWatch(), et qui contient l'algorithme
  • Execute(), qui effectue la mise à jour des données, après la commande MULTI, et juste avant la commande EXEC

Et ici, la méthode utilisant cette interface pour exécuter concrètement la transaction:

func Execute(client redis.UniversalClient,
  transaction Transaction) error {
  // retry the transaction until it succeeds
  for {
    // initialise transaction
    if err := transaction.Init(client); err != nil {
      return err
    }

    // watch the key returned by KeyToWatch()
    if err := client.Watch(context.Background(),
      func(tx *redis.Tx) error {
        // on prepare transaction
        if err := transaction.Prepare(tx); err != nil {
          return err
        }

        // do the transactional work
        _, err := tx.TxPipelined(context.Background(),
          func(pipe redis.Pipeliner) error {
            return transaction.Execute(pipe)
          },
        )

        return err
      },
      transaction.KeyToWatch()...); err == nil {
      return nil
    } else {
      // redis.TxFailedErr is when a data WATCH.ed has changed. it means we need to retry the transaction
      if err == redis.TxFailedErr {
        continue
      } else {
        return err
      }
    }
  }
}

Ainsi, en implémentant l'interface, et en passant une instance de cette implémentation à la méthode Execute, il est très facilement possible de réaliser des transactions.

Conclusion

Voilà qui conclut cet article au sujet des transactions redis. En espérant qu'il ait été clair et qu'il puisse aider à mettre en place ce genre de système très pratique.