Construire un protocole de jeu en réseau

Bonjour, je suis Glenn Fiedler et bienvenu sur la série Construire un protocole de jeu en réseau.

Beaucoup de personnes vous diront qu’implémenter votre propre système de fiabilité basé sur UDP est stupide. Après tout, pourquoi réimplémenter TCP ?

Mais pourquoi nous limiter au fonctionnement de TCP ? Il y a tellement de manières différentes d’implémenter des messages fiables et la plupart n’ont rien à voir avec TCP !

Alors soyons créatifs et voyons comment nous pouvons implémenter un système de messages fiables meilleur et plus souple que TCP pour des jeux temps-réel.

Une approche classique à la fiabilité dans les jeux est d’avoir deux types de paquets : les paquets fiables et ordonnés et les non fiables. Vous verrez cette approche dans plusieurs bibliothèques réseau.

L’idée de base est que la bibliothèque renvoie les paquets fiables jusqu’à ce qu’ils soient reçus par l’autre partie. C’est la solution qui finit généralement par ressembler à TCP pour les paquets fiables. Ce n’est pas trop mal, mais vous pouvez faire bien mieux.

Je préfère penser aux messages comme de petits amas de bits tassés qui savent comment se sérialiser. Ceci est particulièrement évident quand le préfixe de longueur et l’alignement des messages à l’octet n’est pas souhaitable (cas des petits messages inclus dans chaque paquet). Les messages envoyés sont mis dans une file et chaque fois qu’un paquet est envoyé, on y inclut quelques paquets de la file d’envois. Ainsi il n’y a aucun paquet fiable qui a besoin d’être renvoyé. Les messages fiables sont juste inclus dans les paquets sortants jusqu’à ce qu’ils soient reçus.

La façon la plus simple d’y parvenir est d’inclure tous les paquets non acquittés dans chaque paquet envoyé. Quelque chose comme ça : chaque message envoyé a un identifiant qui s’incrémente à chaque envoi. Chaque paquet sortant inclut l’identifiant du premier message suivi des données pour n messages. Le receveur envoie en continu l’identifiant du message le plus récent reçu à l’émetteur comme acquittement et seuls les messages plus récents que le dernier message acquitté sont inclus dans les paquets.

C’est simple et facile à implémenter, mais si de lourdes pertes surviennent pendant l’envoi de messages, vous provoquez un pic dans la taille du paquet à envoyer à cause des nombreux messages non acquittés.

Vous pouvez éviter ceci en implémentant un nombre maximum de messages à inclure par paquet n. Mais maintenant, si vous avez une vitesse d’envoi élevée (comme 60 paquets par seconde), vous envoyez plusieurs fois le même message jusqu’à ce qu’il soit acquitté.

Si votre temps de parcours (ou RTT) est de 100 ms, chaque message sera envoyé en moyenne six fois avant d’être acquitté. Il est possible que vous ayez vraiment besoin de cette redondance parce que les messages sont très critiques, mais dans la plupart des cas, votre bande passante serait mieux utilisée à d’autres fins.

L’approche que je préfère combine des acquittements au niveau du paquet avec un système de priorisation qui prend les n messages les plus importants à inclure dans chaque paquet. Ceci unifie la distribution de données critiques et offre la possibilité d’envoyer seulement n messages par paquet, tout en distribuant les envois sur l’ensemble des messages de la file.

Pour implémenter les acquittements au niveau du paquet, nous ajoutons l’en-tête suivant au paquet :

struct Header
{
    uint16_t sequence;
    uint16_t ack;
    uint32_t ack_bits;
};

Ces éléments d’en-tête forment le système d’acquittement : sequence est un nombre qui s’incrémente à chaque paquet envoyé, ack est le numéro de séquence du plus récent paquet reçu, et ack_bits est un champ de bits encodant les paquets acquittés.

Si le bit n vaut 1 dans ack_bits, alors le paquet ack – n est acquitté. Non seulement ack_bits est un encodage plutôt malin qui permet d’économiser de la bande passante, mais il ajoute en plus de la redondance contrant la perte de paquet. Chaque acquittement est envoyé 32 fois. Si un paquet est perdu, il y a 31 autres paquets avec le même acquittement. Statistiquement, les acquittements vont très certainement parvenir à l’autre partie.

Mais les pertes importantes momentanées existent, il est donc important de noter que :

• Si vous recevez un acquittement pour le paquet n, alors ce paquet a définitivement été reçu.
• Si vous ne recevez pas d’acquittement, le paquet a probablement été perdu. Mais il a pu être reçu et seul l’acquittement a été perdu. Ceci est extrêmement rare.

D’expérience, il n’est pas nécessaire d’envoyer des acquittements parfaits. Construire un système fiable par-dessus un système qui perd très rarement des acquittements n’ajoute aucun problème significatif. Mais ça ajoute un peu de défi pour tester qu’un tel système fonctionne correctement dans toutes les situations à cause des cas particuliers où les acquittements sont perdus.

Donc s’il vous plait, si vous implémentez ce système vous-même, mettez en place des tests reproduisant ces horribles conditions réseau pour vous assurer que votre système d’acquittement fonctionne correctement. Vous trouverez un exemple de test dans le code source de cet article, et dans les bibliothèques open source reliable.io et yojimbo qui implémentent également cette technique.

Pour implémenter ce système d’acquittements, nous avons besoin d’une structure de données chez l’émetteur qui traque qu’un paquet a été acquitté afin d’ignorer les acquittements redondants (chaque paquet est acquitté plusieurs fois via ack_bits). Nous devons également avoir une structure de données chez le receveur pour garder trace des paquets qui ont été reçus pour pouvoir remplir la valeur de ack_bits dans l’en-tête du paquet.

La structure devrait avoir ces propriétés :

• un temps d’insertion constant (les insertions peuvent être aléatoires, avec les paquets désordonnés…) ;
• une requête pour vérifier qu’une entrée existe avec un certain numéro de séquence en temps constant ;
• un accès aux données d’un certain numéro de séquence en temps constant ;
• une suppression des entrées en temps constant.

Vous vous dites peut-être « mais bien sûr, une table de hachage (hash table) ». Mais il y a bien plus simple :

const int BufferSize = 1024;

uint32_t sequence_buffer[BufferSize];

struct PacketData
{
    bool acked;
};

PacketData packet_data[BufferSize];

PacketData * GetPacketData( uint16_t sequence )
{
    const int index = sequence % BufferSize;
    if ( sequence_buffer[index] == sequence )
        return &packet_data[index];
    else
        return NULL;
}

Comme vous pouvoir voir, l’astuce ici est le tampon glissant indexé par le numéro de séquence : const int index = sequence % BufferSize;

Ça marche parce que nous nous moquons de détruire les anciennes entrées. Avec l’incrémentation du numéro de séquence, les entrées plus anciennes sont naturellement écrasées lors de l’insertion des nouvelles. La valeur de sequence_buffer[index] est utilisée pour tester si l’entrée à cet index correspond au numéro de séquence recherché. Une valeur de 0xFFFFFFFF indique une entrée vide et retourne naturellement NULL pour chaque numéro de séquence demandé sans condition supplémentaire.

Quand des entrées sont ajoutées dans l’ordre comme pour une file d’envois, tout ce qu’il y a à faire lors de l’insertion est de mettre à jour la valeur du tampon correspondant avec le nouveau numéro de séquence et écraser les données à cet index :

PacketData & InsertPacketData( uint16_t sequence )
{
    const int index = sequence % BufferSize;
    sequence_buffer[index] = sequence;
    return packet_data[index];
}

Malheureusement, du côté de la réception les paquets arrivent désordonnés et certains sont perdus. Avec un taux de perte ridiculement élevé (99 %), j’ai constaté des entrées d’un ancien numéro de séquence traîner d’avant la dernière réinitialisation à 65 535 et briser ma logique d’acquittement (menant à de faux acquittements et interrompant la fiabilité puisque l’émetteur pense que l’autre partie a reçu des données qui, en fait, ont été perdues…).

La solution à ce problème est de réinitialiser les entrées à la valeur 0xFFFFFFFF entre le précédent numéro de séquence et le nouveau (s’il est plus récent). Désormais, dans la plupart des cas l’insertion est très proche d’être en temps constant, et dans le pire cas linéaire avec n le nombre de séquences entre l’entrée précédente et la nouvelle.

Avant d’aller plus loin, j’aimerais vous montrer que vous pouvez faire bien plus que juste des acquittements avec cette structure. Vous pouvez par exemple étendre les données par paquet pour inclure le moment d’envoi :

struct PacketData
{
    bool acked;
    double send_time;
};

Avec cette information, vous pouvez créer votre propre estimation du temps de parcours (Round Trip Time ou RTT) en comparant le temps d’envoi au temps où le paquet est acquitté en prenant une moyenne glissante lissée exponentiellement. Vous pouvez même vérifier les paquets dans la file d’envois qui sont plus vieux que votre RTT (vous auriez déjà dû recevoir un acquittement pour ceux-ci…) pour créer votre propre estimation de pertes.

Maintenant que nous avons les structures de données et l’en-tête de paquet, voici l’algorithme pour implémenter les acquittements au niveau des paquets :

Lors de l’envoi d’un paquet :

1. Insérez une entrée pour le numéro de séquence du paquet en cours d’envoi dans la file d’envois en le marquant non acquitté.
2. Générez ack et ack_bits à partir du plus récent numéro de séquence reçu et du tampon des numéros de séquence reçus.
3. Insérez le numéro de séquence, ack et ack_bits dans l’en-tête du paquet.
4. Envoyez le paquet puis incrémentez le numéro de séquence d’envoi.

Lors de la réception d’un paquet :

1. Lisez le numéro de séquence de l’en-tête du paquet.
2. Si le numéro de séquence est plus récent que le précédent numéro de séquence reçu, mettez à jour le plus récent numéro de séquence reçu avec celui-ci.
3. Insérez une entrée pour ce paquet dans le tampon des numéros de séquence reçus.
4. Décodez les acquittements à partir de ack et ack_bits de l’en-tête du paquet.
5. Itérez tous ces acquittements, et pour chaque paquet qui n’est pas encore acquitté, appelez OnPacketAcked(uint16_t sequence) et marquez ce paquet comme acquitté dans le tampon des numéros de séquence d’envoi.

Il est très important de réaliser cet algorithme chez l’émetteur et le récepteur, donc si vous avez un client et un serveur, alors chacun exécute la même logique, maintient son propre numéro de séquence pour les paquets envoyés, enregistre le numéro de séquence reçu le plus récent de l’autre partie et un tampon des numéros de séquence reçus qui servira à générer les valeurs de sequence, ack et ack_bits à faire parvenir à la machine distante.

Et c’est tout. Maintenant vous avez une fonction de post-traitement (callback) quand un paquet a été reçu par la machine distante : OnPacketAcked. Le bénéfice principal de ce système d’acquittement est que maintenant que vous savez quels paquets ont été reçus, vous pouvez construire n’importe quel système de fiabilité par-dessus. Ce n’est pas limité aux seuls messages fiables et ordonnés. Par exemple, vous pourriez l’utiliser pour implémenter un codage différentiel (delta encoding) par objet.

Les messages sont de petits objets (plus petit qu’un paquet de telle sorte que plusieurs peuvent être insérés dans un paquet) qui savent comment se sérialiser. Dans mon système, ils réalisent cette sérialisation via une fonction de sérialisation unifiée.

La fonction de sérialisation est une fonction template afin de pouvoir gérer l’écriture, la lecture et la mesure avec un seul code.

Oui. La mesure. Une de mes astuces préférées est d’avoir une classe de flux factice nommée MeasureStream qui ne fait aucune sérialisation, mais se contente de mesurer le nombre de bits qui seraient écrits si vous appelez la fonction de sérialisation. C’est particulièrement utile pour déterminer quels messages vont pouvoir entrer dans le paquet, en particulier quand les messages eux-mêmes peuvent avoir des fonctions de sérialisation arbitraires et complexes.

    template <typename Stream> bool Serialize( Stream & stream )
    { 
        serialize_bits( stream, a, 32 );
        serialize_bits( stream, b, 32 );
        serialize_bits( stream, c, 32 );
        return true;
    }

    virtual SerializeInternal( WriteStream & stream )
    {
        return Serialize( stream );
    }

    virtual SerializeInternal( ReadStream & stream )
    {
        return Serialize( stream );
    }

    virtual SerializeInternal( MeasureStream & stream )
    {
        return Serialize( stream );        
    }
};

L’astuce est de relier la fonction de sérialisation template (pour n’avoir à l’écrire qu’une seule fois) aux fonctions de sérialisation virtuelles en l’appelant depuis les fonctions virtuelles par type de flux. Je mets généralement ça sous forme de macro, mais elle est développée dans le code au-dessus pour que vous voyiez ce qu’il se passe.

Maintenant, quand vous avez un pointeur vers un message de base, vous pouvez faire ceci et ça marche :

Message * message = CreateSomeMessage();
message->SerializeInternal( stream );

Une alternative si vous connaissez l’ensemble des messages à la compilation est d’implémenter un gros switch sur le type de message afin d’appeler la fonction de sérialisation correspondante. J’ai fait ceci par le passé sur des implémentations de ce système de message sur consoles (par exemple sur les SPUs de la PS3), mais pour les applications actuelles (en 2016) le surcoût lié aux fonctions virtuelles est négligeable.

Les messages dérivent d’une classe de base qui fournit une interface commune telle que la sérialisation, un accesseur pour récupérer le type de message et un compteur de référence. Le compteur de référence est nécessaire parce que les messages sont passés par pointeur et stockés non seulement dans la file d’envois jusqu’à ce qu’ils soient acquittés, mais aussi dans les paquets sortants qui sont eux-mêmes des structures C++.

C’est une technique pour éviter d’avoir à copier les données en transférant les messages et paquets par pointeur. Ailleurs (idéalement sur un thread différent), les paquets et les messages qu’il contient sont sérialisés dans un tampon. Une fois que plus aucune référence vers un message n’existe dans la file d’envois des messages (que le message est acquitté) et que plus aucun paquet n’incluant ce message n’existe dans la file d’envois des paquets, le message est détruit.

Nous avons aussi besoin d’une façon de créer des messages. Je le fais via une fabrique de messages avec une fonction virtuelle spécialisée pour créer un message par type. C’est une bonne chose si la fabrique connaît le nombre total de types de message, ainsi nous pouvons sérialiser un type de message avec des bornes précises et rejeter les paquets malicieux contenant une valeur de type de message en dehors de la plage valide :

enum TestMessageTypes
{
    TEST_MESSAGE_A,
    TEST_MESSAGE_B,
    TEST_MESSAGE_C,
    TEST_MESSAGE_NUM_TYPES
};

// definitions des messages omis

class TestMessageFactory : public MessageFactory
{ 
public:

    Message * Create( int type )
    {
        switch ( type )
        {
            case TEST_MESSAGE_A: return new TestMessageA();
            case TEST_MESSAGE_B: return new TestMessageB();
            case TEST_MESSAGE_C: return new TestMessageC();
        }
    }

    virtual int GetNumTypes() const
    {
        return TEST_MESSAGE_NUM_TYPES;
    }
};

Ici aussi, le code est amené à être répété et est d’habitude enveloppé dans des macros, mais voilà ce qu’il se passe derrière celles-ci.

L’algorithme pour envoyer des messages fiables et ordonnés est le suivant :

Lors de l’envoi du message :

1. Mesurez combien de bits le message nécessite en utilisant le flux de mesure.
2. Insérez le pointeur du message et le nombre de bits nécessaires à sa sérialisation dans un tampon de séquence indexé par identifiant de message. Assignez la valeur -1 au moment où le message a été envoyé.
3. Incrémentez l’identifiant de message d’envoi.

Lors de l’envoi d’un paquet :

1. Itérez sur les messages dans le tampon de séquence d’envoi depuis le plus vieil identifiant non acquitté et le plus récent inséré (par ordre croissant d’identifiant).
2. N’envoyez jamais un message que le receveur ne peut pas mettre en mémoire ou vous briserez les acquittements de message (puisque le message ne sera pas mis en mémoire, mais le paquet le contenant sera acquitté, l’émetteur pensera que le message a été reçu et ne le renverra pas). Ceci signifie que vous ne devez jamais envoyer un identifiant égal ou plus récent que le plus ancien identifiant non acquitté + la taille du tampon de réception.
3. Chaque message qui n’a pas été envoyé dans le dernier dixième de seconde et qui rentre dans l’espace restant du paquet est ajouté à la liste des messages à envoyer. Les messages sur la gauche (les messages plus anciens) ont naturellement priorité dû à l’ordre d’itération.
4. Ajoutez les messages dans le paquet sortant et ajoutez une référence vers chaque message. Assurez-vous que le destructeur du paquet décrémente le compteur de référence pour chaque message.
5. Stockez le nombre de messages inclus dans le paquet n et le tableau des identifiants de message qu’il contient dans un tampon de séquence indexé par le numéro de séquence du paquet sortant afin de pouvoir faire correspondre les acquittements de paquet aux messages inclus dans ce paquet.
6. Ajoutez le paquet à la file d’envois.

Lors de la réception d’un paquet :

1. Itérez l’ensemble des messages inclus dans le paquet et insérez-les dans le tampon des messages reçus indexé par leur identifiant de message.
2. Le système d’acquittement acquitte automatiquement le numéro de séquence du paquet que nous venons de recevoir.

Lorsqu’un paquet est acquitté :

1. Recherchez l’ensemble des identifiants de message inclus dans le paquet via son numéro de séquence.
2. Supprimez ces messages de la file d’envois s’ils existent et décrémentez leur compteur de référence.
3. Mettez à jour l’identifiant du dernier message non acquitté en itérant depuis le précédent identifiant non acquitté dans le tampon de séquence d’envoi jusqu’à trouver une entrée valide, ou bien, jusqu’à atteindre l’identifiant de message courant. Quel que soit le premier cas rencontré.

Lors de la réception d’un message :

1. Vérifiez dans le tampon de séquence des messages reçus qu’un message existe pour l’identifiant reçu.
2. Si le message existe, supprimez-le du tampon de séquence des messages reçus, incrémentez l’identifiant du message reçu et retournez un pointeur vers le message.
3. Sinon, aucun message n’est disponible à la réception. Retournez NULL.

En résumé, les messages sont inclus dans les paquets jusqu’à ce qu’un paquet contenant ce message est acquitté. Nous utilisons une structure de données chez l’émetteur pour faire correspondre les numéros de séquence des paquets à l’ensemble des identifiants de message à acquitter. Les messages sont retirés de la file d’envois quand ils sont acquittés. Chez le receveur, les messages arrivent désordonnés et sont stockés dans un tampon de séquence indexé par l’identifiant de message, qui permet de les recevoir dans l’ordre dans lequel ils ont été envoyés.

Ceci fournit à l’utilisateur une interface qui ressemble à l’envoi :

TestMessage * message = (TestMessage*) factory.Create( TEST_MESSAGE );
if ( message )
{
    message->a = 1;
    message->b = 2;
    message->c = 3;
    connection.SendMessage( message );
}

Et à la réception :

while ( true )
{
    Message * message = connection.ReceiveMessage();
    if ( !message )
        break;

    if ( message->GetType() == TEST_MESSAGE )
    {
        TestMessage * testMessage = (TestMessage*) message;
        // process test message
    }

    factory.Release( message );
}

Ce qui est assez souple pour implémenter ce que vous souhaitez par-dessus.

Cet article est une traduction autorisée de l’article de Glenn Fiedler.