Hestia : dans les coulisses du stockage de vos factions

Sur Paladium, des milliers de factions et des centaines de milliers de joueurs sont partagés entre des centaines de serveurs, qui peuvent tous modifier la même faction au même instant. Hestia, c'est la bibliothèque qu'on a construite pour tenir cette charge et dans cet article, on vous montre comment.

Le problème

Une faction n'appartient à aucun serveur en particulier. Elle est stockée dans une base de données centrale, et chaque serveur qui en a besoin la lit, la modifie, puis la réécrit. Tant qu'un seul serveur la touche à la fois, tout va bien. Le problème commence quand plusieurs serveurs la modifient en même temps.

Prenons un cas simple. Une faction a 10.000 $ en banque, et deux membres, sur deux serveurs différents, déposent chacun 1.000 $ au même moment.

1. Le serveur A lit la faction, la banque est à 10.000 $.
2. Le serveur B lit la faction au même moment, la banque est toujours à 10.000 $.
3. Le serveur A ajoute 1.000 $, et écrit 11.000 $.
4. Le serveur B ajoute 1.000 $ à ce qu'il avait lu, et écrit lui aussi 11.000 $, par-dessus.

À l'arrivée, la banque affiche 11.000 $ au lieu de 12.000 $. Chaque serveur a fait exactement ce qu'on lui demandait, aucune erreur n'a été levée, et pourtant un dépôt a disparu. C'est ce qu'on appelle une écriture perdue. Et plus il y a de serveurs, plus ça arrive souvent. On l'a mesuré avec 8 serveurs en parallèle qui incrémentent la même factions 2.000 fois, sur ce test nous avons mesuré jusqu'à 86% de perte de donnée.

Il y a aussi un deuxième problème, celui du coût. Pour changer un seul nombre, le serveur réécrit la faction entière, les membres, les grades, les permissions, les claims, etc. Des Ko de données envoyés à chaque modification, multipliés par des centaines de serveurs.

Les solutions habituelles règlent l'un des deux problèmes, jamais les deux.

• Verrouiller la faction le temps de chaque modification. Plus aucune écriture perdue, mais chaque serveur attend son tour, et tout ralentit dès que la charge monte.
• Les transactions optimistes. Le serveur écrit, et si la faction a changé entre-temps, il recommence tout depuis le début. Rien n'est perdu non plus, mais sous forte concurrence, les serveurs passent leur temps à recommencer.
• Dans les deux cas, la faction entière continue de partir sur le réseau à chaque modification.

C'est pour ça qu'on a construit notre propre solution. Et si on en parle aujourd'hui, c'est que le problème n'a rien de propre à Minecraft. N'importe quel système où plusieurs serveurs partagent les mêmes données, un inventaire, un panier, un compte, tombe dessus tôt ou tard.

Redis, en deux mots

Redis, c'est une base de données qui garde tout en mémoire vive plutôt que sur disque. On lui donne une clé, elle renvoie la valeur associée en quelques microsecondes.

Chez nous, chaque faction est un document dans Redis. Tous les serveurs s'y connectent, c'est le point central, la seule source de vérité. Quand un serveur modifie une faction, c'est là qu'il l'écrit, et c'est là que les autres viennent la lire.

Reste une question. Si Redis sait déjà modifier un document champ par champ, pourquoi ne pas s'en servir directement ? Parce que Redis ne connaît pas nos objets complexe. Il sait ajouter 1.000 à un nombre ou insérer un élément dans une liste, mais il faut lui dire précisément quoi faire, champ par champ, à chaque modification.

L'échelle

Pour donner une idée de ce que ça représente chez nous, voici ce que traverse le stockage des factions, sur 9 jours :

• 1.824 factions stockées en permanence, ~20 Ko en moyenne, 380 Ko pour les plus grosse.
• 208 connexions ouvertes en permanence sur le même Redis
• 1,78 milliard de commandes, soit environ 2.300 par seconde, jour et nuit.
• 38,9 millions de lectures de faction, et 4,2 millions d'écriture.
• 124 Go envoyés à Redis, et 16,5 To renvoyés aux serveurs, plus de 20 Mo par seconde en continu.

Hestia

Dans la mythologie grecque, Hestia est la déesse du foyer. Chaque cité avait son foyer commun, un feu qui ne devait jamais s'éteindre, et quand des colons partaient fonder une nouvelle ville, ils emportaient une flamme de ce foyer pour allumer le leur. Un feu central, et partout ailleurs des copies allumées à partir de lui. C'est exactement ce que fait notre projet. Redis est le foyer, la seule source de vérité. Chaque serveur garde sa propre copie des objets, allumée à partir de ce foyer, et toujours synchronisée avec lui.

Concrètement, Hestia est une bibliothèque Java de Shared Object Storage. Tu modifies tes objets Java normalement, tu appelles save, et elle s'occupe du reste :

• Aucune écriture perdue. Les modifications de plusieurs serveurs fusionnent au lieu de s'écraser.
• Atomique. Un objet n'est jamais à moitié écrit, même en cas de coupure au pire moment.
• Plus rapide que la méthode classique. Seul ce qui a changé part sur le réseau, pas l'objet entier.
• Caches locaux synchronisés. Chaque serveur lit ses objets en mémoire, sans aller sur le réseau, et reçoit les modifications des autres en temps réel.
• Verrous distribués. Pour les opérations qui doivent être exclusives, avec une vraie protection si le verrou expire en cours de route.

Comment on l'utilise

Le principe est simple, un objet Java classique, avec quelques annotations.

public class Faction {

    private final String id;

    private long bank;
    private long power;
    @RedisIndex private String name;
    @RedisJsonVersion private long version;
    @RedisJsonOverwrite private long lastActivity;

    @RedisJsonSnapshot
    private transient JsonElement snapshot;

}

Et côté code, rien de plus que ce qu'on écrirait avec n'importe quelle base de données.

final RedisStore<Faction> factions = RedisStore.create(client, RedisStoreConfig.create(Faction.class, Faction::getId));

factions.fetch(id).thenCompose(faction -> {
    faction.setBank(faction.getBank() + 1000L);
    return factions.save(faction);
});

Le développeur ne pense jamais à la concurrence. Il n'y a ni WATCH, ni transaction, ni boucle de nouvelle tentative à écrire. Il modifie son objet, il sauvegarde, et c'est Hestia qui garantit que les 1.000 $ arrivent bien en banque, même si dix autres serveurs touchent la même faction au même moment.

Comment ça fonctionne

Tout repose sur une idée. On n'envoie jamais l'objet, on envoie ce qui a changé, sous une forme que Redis peut appliquer sans risque, même si l'objet a bougé entre-temps.

Le snapshot

Quand un objet est chargé, Hestia garde une copie de son état d'origine, le snapshot, dans le champ @RedisJsonSnapshot. Au moment de la sauvegarde, elle compare l'objet actuel à ce snapshot, champ par champ, et en déduit une liste d'opérations.

Et c'est là que tout se joue. Hestia ne regarde pas seulement si une valeur a changé, elle regarde comment elle a changé.

• Un nombre qui a bougé devient un incrément. La banque est passée de 10.000 à 11.000 ? Hestia n'envoie pas « la banque vaut 11.000 », elle envoie « ajoute 1.000 à la banque ». Deux serveurs qui ajoutent chacun 1.000 donnent donc bien 12.000.
• Un élément ajouté à une liste devient un ajout en fin de liste, pas une réécriture de la liste.
• Un élément retiré d'une liste devient un retrait de cet élément précis.
• Un champ supprimé devient une suppression de ce champ.
• Le reste est écrit à son emplacement exact, et uniquement lui.

Pour les nombres qui ne s'accumulent pas, un horodatage, une priorité, une valeur recalculée, l'annotation @RedisJsonOverwrite dit à Hestia d'écrire la valeur telle quelle plutôt qu'un incrément.

L'exécution

Cette liste d'opérations part dans Redis sous forme d'une exécution. Redis l'exécute d'un seul bloc, sans jamais rien intercaler au milieu. Soit toutes les opérations passent, soit aucune. Il n'existe aucun moment où un autre serveur pourrait voir la faction à moitié modifiée.

Avant d'appliquer quoi que ce soit, Hestia vérifie aussi que chaque opération a encore du sens. Si un autre serveur a supprimé la faction entre-temps, les opérations qui la concernent sont simplement ignorées, plutôt que de la recréer à moitié.

Le résultat, pour un dépôt en banque sur une faction de 16 Ko :

Et comme le patch ne dépend que de ce qui change, l'écart grandit avec la taille de l'objet. Sur un objet de 130 Ko, la méthode classique envoie 133,5 Ko. Hestia envoie toujours 165 octets.

Rejouer sans doubler

Il reste un cas vicieux. Le serveur envoie son patch, Redis l'applique, mais la réponse se perd en route, une coupure réseau, un timeout. Le serveur ne sait pas si son écriture est passée. S'il renvoie le même « ajoute 1.000 », la banque risque de recevoir 2.000.

Chaque patch porte donc un identifiant unique. La première fois qu'il est appliqué, Hestia laisse une marque dans Redis. Si le même patch revient, il le voit la marque et ne fait rien. Hestia peut donc renvoyer un patch autant de fois que nécessaire, il ne s'appliquera jamais qu'une seule fois.

Le cache

Lire dans Redis à chaque fois qu'un serveur a besoin d'une faction, ce serait beaucoup trop lent. Chaque serveur garde donc toutes les factions en mémoire, dans un cache local. La question, c'est comment garder ces caches à jour.

Chaque objet porte un numéro de version, le champ @RedisJsonVersion, incrémenté à chaque sauvegarde, dans le même patch que le reste. Quand un serveur sauvegarde une faction, Redis lui renvoie l'objet complet après fusion, et le serveur le diffuse aux autres avec sa version. Chaque serveur compare cette version à celle qu'il a déjà, et ignore tout ce qui est plus ancien. Peu importe l'ordre dans lequel les messages arrivent, un cache ne peut jamais revenir en arrière.

Et au lieu de relire toutes les factions régulièrement pour être sûr de n'avoir rien raté, chaque serveur ne demande plus que la liste des versions, quelques octets par faction. Il ne relit ensuite que les factions dont la version a changé.

Les verrous

Fusionner les modifications suffit dans l'immense majorité des cas. Mais certaines opérations doivent être exclusives. Un seul serveur à la fois doit pouvoir traiter un retrait de banque pour s'assurer que le solde est suffisant.

Hestia fournit des verrous distribués pour ça. Le problème classique d'un verrou distribué, c'est qu'il expire. Un serveur prend le verrou mais si l'opération prend trop de temps le verrou expire, un autre serveur le prend, puis le premier termine et écrit comme si de rien n'était. Deux serveurs ont écrit sous le même verrou.

client.getLock().withLockWaiting("faction:bank:" + id, token -> factions.fetch(id).thenCompose(faction -> {
    faction.setBank(faction.getBank() - amount);
    return factions.save(faction, token);
}));

En passant le token du verrou à save, Hestia vérifie dans Redis même, au moment exact de l'écriture, que ce verrou appartient toujours à ce serveur. Si ce n'est plus le cas, l'écriture est refusée.

L'envoi

Dernière pièce, la façon dont les commandes partent vers Redis. Il y a deux stratégies classiques. Envoyer chaque commande dès qu'elle arrive, c'est rapide quand il y en a peu, mais chacune attend sa réponse avant de libérer sa connexion. Tout grouper en pipeline, c'est efficace quand il y en a beaucoup, mais tout le monde attend le groupe.

Hestia fait les deux. Tant qu'une connexion est libre, une écriture part directement, depuis le thread qui sauvegarde, sans attendre personne. Quand toutes les connexions sont occupées, les écritures qui arrivent s'accumulent, et partent groupées en pipeline sur la première connexion qui se libère. Plus la charge monte, plus les groupes grossissent, et plus chaque aller-retour réseau est rentabilisé.

Les lectures suivent la même logique, avec en plus de la déduplication. Si cinquante threads demandent la même faction au même moment, Redis ne reçoit qu'une seule lecture, et chacun récupère sa propre copie de l'objet.

Les bench

Tout ça, on l'a mesuré. Hestia face à la méthode classique, un JSON.SET de l'objet complet pour écrire et un JSON.GET pour lire, sur Redis 8.

Le chiffre le plus important, c'est la charge Redis. Avec 16 serveurs en parallèle sur des objets de 130 Ko, la méthode classique sature Redis à 92 %. Avec Hestia, le même Redis encaisse 3,6 fois plus d'écritures, en restant à un cinquième de sa capacité. Ce n'est plus Redis qui limite, c'est le serveur lui-même.

Et face à l'autre méthode correcte, la transaction optimiste (WATCH / MULTI), qui ne perd rien elle non plus mais recommence à chaque conflit, Hestia est près de 4 fois plus rapide. Sur les 2.000 incréments concurrents, la transaction a dû recommencer 10.248 fois. Hestia, zéro.

Pour l'envoi hybride, avec 64 serveurs en parallèle sur de petits objets et une latence réseau de 1 ms, Hestia monte à 15.987 écritures par seconde, contre 7.313 en envoyant chaque commande séparément. Plus de 2 fois plus.