[Cloud] Gestion de données avec modifications concurrentielles sur un cluster


#1

Introduction

Après la dernière phase d’Alpha que nous avons eu, nous avons découvert un problème au niveau de la gestion des groupes et des inscriptions aux listes d’attente pour le Matchmaking: Certains joueurs n’avaient pas de groupe assignés ou étaient inscris deux fois en file d’attente. Il s’agissait d’un problème de synchronisation et de modification concurrente des données.
Dans cet article, nous parlerons des techniques utilisées pour pallier aux problèmes de concurrence de données que nous avons rencontré. Nous parlerons entre autre de la gestion d’état de modification d’une donnée partagée entre plusieurs services différents.

Petite vue sur l’architecture d’Unexpected: Quels outils?

De manière à pouvoir proposer un service pouvant supporter un maximum d’utilisateurs et de requêtes possibles, nous avons choisi de développer l’architecture d’Unexpected (et de dWARf) autour de plusieurs services.

Le but principal est de penser tous les services de manière à être totalement scalables (ajouter de nouvelles instances dudit service de manière à répartir la charge sur plusieurs serveurs différents) tout en limitant au maximum les besoins en données partagées (c’est ce qu’on appelle faire du “stateless”).

En ayant ce contexte en tête, nous avons donc choisi des outils permettant d’obtenir un partage de données inter-services efficace et ne consommant pas beaucoup de ressources. Dans ce contexte, c’est Redis qui a été choisi pour servir de cache de données partagées et RabbitMQ qui servira d’intermédiaire pour fournir un aspect temps-réel aux données envoyées sur le réseau. RabbitMQ est utilisé comme intermédiaire pour permettre aux services d’envoyer des messages aux clients de manière ciblée ou non, ainsi que de transmettre des messages entre les services. Le service RabbitMQ se charge de l’envoi et du routage du message à la bonne instance du service de Notifications (qui se comporte comme un PubSub) ou des services écoutant sur certains évènements (libération d’une donnée, déconnexion d’un joueur, etc.) permettant aux clients d’être informés en temps réel via des notifications. Par définition, RabbitMQ n’est donc pas la cible de notre problème de synchronisation.

Nous utilisons Redis en temps que cache de données partagées, c’est à dire qu’il nous permet de stocker, de manière temporaire, différentes données, qui peuvent être accessibles par n’importe quel service connecté à Redis. Il est donc utilisé en temps que “WorkingQueue”, qui permet de définir et répartir les données qui seront exécutées les unes après les autres, via un ou plusieurs services et aussi en temps que simple cache, qui nous permet, par exemple, de stocker le statut d’un utilisateur sur le réseau (connecté, en cours de partie, etc) (il faut voir Redis comme une mémoire partagée que tous les services peuvent utiliser pour récupérer des données volatiles (comme une barrette de “RAM” qui serait partagée sur tous nos services).

Un problème vous avez dit?

Oui, un problème réside sur les WorkingQueues utilisées par nos systèmes de Matchmaking. En effet, lorsqu’un système de Matchmaking crée un “groupe temporaire pour une partie”, il ajoute au groupe des utilisateurs jusqu’à atteindre un certain nombre d’utilisateurs (6 pour les parties standard de dWARf) avant de lancer la partie. Et c’est exactement ce “groupe temporaire” qui pose problème: Lorsqu’on a des utilisateurs qui s’inscrivent seuls au matchmaking -je parle ici d’utilisateurs sans groupes-, tout se passe correctement: Les utilisateurs sont ajoutés un par un dans le groupe, jusqu’à atteindre 6 joueurs pour lancer la partie et vider le groupe temporaire. Pour comprendre le problème, il faut bien comprendre que le groupe est construit en ajoutant les joueurs au groupe temporaire un par un, même lorsque l’utilisateur est dans un groupe et c’est due au système de groupe temporaire qui est utilisé par plusieurs instances de Matchmaking qu’il y a un problème de modification concurrente du groupe temporaire. En effet, lorsque 2 groupes s’inscrivent au Matchmaking en même temps, il est possible que 2 instances de matchmaking les ajoutent en même temps dans le groupe temporaire, le problème étant: vue que les joueurs sont ajoutés les uns après les autres, il est possible de se retrouver avec un groupe temporaire ayant des joueurs qui étaient dans un groupe, mais qui ont été retirés et ajoutés au prochain groupe temporaire car celui-ci a été remplis trop rapidement et en même temps par la seconde instance de Matchmaking. Ainsi, on se retrouve avec un joueur orphelin de son groupe et la liste d’attente de matchmaking devient corrompue et inutilisable.

Voici un schéma pour vous aider à comprendre:
Cration%20d'un%20groupe%20de%20matchmaking%20corrompu
Dans cet exemple, le groupe de création de partie est déjà quasiment plein, il ne lui manque que 3 joueurs pour pouvoir lancer la partie.
Bien entendu, ce schéma est simplifié, dans la réalité, les workers matchmaking ont pour tâche de vérifier la taille actuelle du groupe en construction avant d’y ajouter un groupe, mais la vérification doit être protégée elle aussi, sinon le problème reste le même.
Dans ce schéma, le joueur 2 du 2nd groupe va “décaler” tous les groupes suivants. Ce qui va générer un groupe de matchmaking corrompu.

Du coup, une solution claire s’impose: Il faut que le groupe temporaire ne puisse être modifié que par une instance à la fois.

C’est dans ce contexte qu’on utilise ce qu’on appelle un “Lock partagé”. C’est tout simplement un système permettant de verrouiller une donnée à travers Redis pour ne laisser qu’une seule instance travailler dessus à la fois. Ainsi, si une seconde instance souhaite modifier ladite donnée, elle attendra son tour.

Un léger problème subsiste ici: Un Lock ralentit énormément l’accès et la modification de la donnée. Et donc, limite le nombre d’instances optimales par groupe temporaire.

Après quelques tests, pour un groupe définit et dans le cas du matchmaking d’Unexpected, pour un groupe temporaire précis, il est possible de faire tourner 4 instances de matchmaking avant que celles-ci ne se gênent trop et perdent en performance.

Du coup, une solution simple est trouvée: On regroupe par “mini-clusters” de 4 les instances. Ainsi, pour chaque mini-cluster on définit un groupe temporaire différent (ex: dwarf:matchmaking:queue:1:tmp_group:1, dwarf:matchmaking:queue:1:tmp_group:2, etc.) par cluster, ce qui nous permet de contourner le problème.

L’étape suivante est de définir des règles et utiliser un système de consensus P2P permettant aux différentes instances de Matchmaking de décider de manière groupées du nombre d’instances à ajouter et de la répartition de chaque instances sur les listes de Matchmaking dépendant de la charge actuelle de la liste en question (par ex: Matchmaking 2v2v2, 1v1v1v1v1v1 etc.).

Mais ça sera le sujet d’un prochain blog :wink:


#2

#3