Concevoir une messagerie instantanée

Le central qui sait où joindre chacun

Avant l'automatique, une ville avait un central. Une salle, un panneau de fiches, des opératrices, et un câble qu'on enfonçait dans la bonne prise pour relier deux abonnés.

Le central ne parlait jamais à la place des gens. Il savait une seule chose, et il la savait mieux que quiconque : où se trouve chaque abonné, à cet instant précis.

Une messagerie instantanée fait ce travail, avec deux différences. Le nombre d'abonnés se compte en centaines de millions, et personne ne raccroche vraiment : la ligne reste ouverte toute la journée dans la poche de l'utilisateur.

Le problème central d'une messagerie n'est pas de transporter du texte. C'est de savoir, à chaque milliseconde, quelle machine détient la connexion ouverte du destinataire, et quoi faire quand la réponse est « aucune ».

Cinq décisions structurent le système entier, et ce billet les prend dans l'ordre. Le protocole de transport entre le client et le serveur. Le partage entre services sans état et serveurs avec état. La forme du magasin de messages et sa clé de partition. Le traitement du destinataire absent. Et la présence, qui semble anecdotique et qui devient le premier poste de trafic si on la traite naïvement.

C'est le dernier billet de la série. Il réutilise à peu près tout ce que les quatorze précédents ont posé, et une section en fin de parcours fait l'inventaire.

Les exigences

Le cahier des charges d'un central tient en quelques lignes. Joindre un abonné, monter une conférence à plusieurs, savoir qui a décroché, garder trace des appels passés, et refuser la ligne à quelqu'un qui n'est pas abonné.

Côté fonctionnel, on retient la même liste. Discussion un à un, discussion de groupe avec un plafond de membres assumé, accusés de livraison et de lecture, indicateur de présence, historique consultable depuis n'importe quel appareil, et authentification.

Côté non-fonctionnel, trois contraintes pèsent plus que les autres.

La latence perçue doit rester sous quelques centaines de millisecondes de bout en bout, sinon la conversation cesse d'être une conversation. L'ordre des messages doit être stable à l'intérieur d'une conversation, même si l'ordre global entre deux conversations n'a aucune importance. Et l'historique doit survivre à la perte d'un appareil, ce qui interdit de le stocker uniquement côté client.

On ne conçoit pas une messagerie « temps réel ». On conçoit un système où la connexion est déjà établie avant que le message n'existe. Tout le reste en découle.

L'estimation

Avant de choisir quoi que ce soit, on chiffre. Le geste est celui de l'estimation à la louche, appliqué ici sans raccourci.

Point de départ : 500 millions d'inscrits, dont on suppose 10 % actifs chaque jour, et 40 messages envoyés par actif quotidien. Ces deux hypothèses, le taux d'activité et le volume par actif, ne sont pas des mesures, et c'est précisément pour ça qu'on les écrit.

500 000 000  utilisateurs inscrits
x 10 %       actifs par jour             =    50 000 000  actifs quotidiens
x 40         messages envoyés par actif  = 2 000 000 000  messages par jour
/ 100 000    (86 400 s, arrondi)         =        20 000  messages par seconde

Vingt mille messages par seconde en moyenne. Le trafic d'une messagerie est très irrégulier, donc on retient une pointe à trois fois la moyenne, soit 60 000 messages par seconde à dimensionner.

Ensuite le stockage. Un message texte moyen fait une centaine de caractères, auxquels s'ajoutent les identifiants, l'horodatage et le statut.

100 octets  texte moyen
+ 100 octets  identifiants, horodatage, statut
= 200 octets  par message stocké

2 000 000 000 messages x 200 octets  = 400 000 000 000 octets = 400 Go par jour
400 Go x 365                         = 146 000 Go            = 146 To par an
146 To x 10 ans                      = 1 460 To              = 1,46 Po
1,46 Po x 3 répliques                = 4,4 Po de disque à provisionner

Près de quatre pétaoctets et demi sur dix ans, avant compression et avant toute politique de purge. L'ordre de grandeur suffit à trancher une chose : ce volume ne tiendra pas sur une base relationnelle unique.

Reste le plus déterminant pour ce système précis, le nombre de connexions ouvertes en même temps.

50 000 000 actifs quotidiens
x 20 %      connectés simultanément à la pointe = 10 000 000 connexions ouvertes
/ 100 000   connexions par serveur de discussion =        100 serveurs de discussion

Dix millions de sockets ouverts. À 10 Ko d'état par connexion (session, tampons, contexte de chiffrement), cela fait 10 000 000 × 10 Ko = 100 000 000 Ko, soit 100 Go de mémoire répartis sur la flotte, environ 1 Go par machine.

Le chiffre qui décide de l'architecture n'est pas le débit de messages, c'est le nombre de connexions simultanées. Vingt mille messages par seconde se traitent avec quelques machines ; dix millions de sockets ouverts, non.

Pourquoi le pair-à-pair ne suffit pas

Deux voisins peuvent se parler par-dessus le mur du jardin sans passer par le central. Ça marche très bien, jusqu'au jour où l'un des deux est absent, où il faut inviter huit personnes, ou où l'on veut relire ce qui s'est dit la semaine dernière.

Le pair-à-pair échoue sur quatre points, et chacun suffirait.

Il n'y a pas d'historique, puisqu'aucune des deux extrémités n'est fiable. Il n'y a pas de livraison différée : si le destinataire est éteint, le message n'existe nulle part. La discussion de groupe oblige chaque membre à ouvrir une connexion vers tous les autres, ce qui donne N × (N-1) / 2 connexions pour N participants, soit 4 950 connexions pour un groupe de cent.

Le quatrième point est plus technique. Deux téléphones mobiles sont presque toujours derrière une traduction d'adresses, chacun de son côté. Établir une connexion directe suppose alors de découvrir son adresse publique, de tenter la traversée, puis de relayer le trafic quand elle échoue. Les mécanismes existent, STUN, TURN et ICE, mais ils reposent sur des serveurs tiers. On n'a donc pas supprimé le serveur central, on l'a déguisé.

Le pair-à-pair règle le transport et laisse entier le problème de la mémoire. Une messagerie est d'abord un magasin, accessoirement un tuyau.

Le protocole

Le client doit recevoir un message qu'il n'a pas demandé. HTTP, lui, part du principe que le client demande et que le serveur répond. Toute la difficulté tient dans cet écart.

Quatre réponses existent, dans l'ordre historique.

L'interrogation régulière. Le client redemande toutes les N secondes. Simple à écrire, désastreux à l'échelle : à 10 millions de clients interrogeant toutes les 5 secondes, on obtient 10 000 000 / 5 = 2 000 000 requêtes par seconde, dont l'écrasante majorité ne rapporte rien.

L'interrogation longue. Le serveur garde la requête ouverte jusqu'à ce qu'un message arrive ou que le délai expire. La latence tombe, le nombre de requêtes inutiles aussi, mais le serveur détient déjà une connexion par client. On paie donc le coût de l'état sans en tirer le bénéfice, et chaque message reçu impose de rouvrir un cycle requête-réponse complet.

Les événements envoyés par le serveur. Un flux text/event-stream que le serveur alimente, avec reconnexion automatique et reprise via Last-Event-ID. Élégant pour un fil d'actualité, insuffisant ici : le canal est unidirectionnel, il faut donc un second canal pour l'envoi.

WebSocket. Une connexion TCP unique, bidirectionnelle, établie par une bascule depuis HTTP. C'est le choix par défaut pour ce type de système, normalisé par la RFC 6455.

GET /chat HTTP/1.1
Host: chat.exemple.fr
Upgrade: websocket
Connection: Upgrade
Sec-WebSocket-Key: dGhlIHNhbXBsZSBub25jZQ==
Sec-WebSocket-Version: 13

HTTP/1.1 101 Switching Protocols
Upgrade: websocket
Connection: Upgrade
Sec-WebSocket-Accept: s3pPLMBiTxaQ9kYGzzhZRbK+xOo=

Après le code 101, la connexion cesse d'être du HTTP. Les deux extrémités échangent des trames, dans les deux sens, sans nouvelle négociation.

WebSocket ne rend pas le système temps réel, il rend le serveur permanent. C'est un changement de nature : la machine ne traite plus des requêtes, elle héberge des clients.

L'architecture

Le central ne faisait pas tout. Il y avait le service des abonnements, celui de la facturation, l'annuaire, et la salle des fiches où l'on branchait les câbles. Une seule de ces pièces avait besoin de savoir qui était en ligne à cet instant.

Le système se coupe exactement de la même façon.

D'un côté, les services sans état : authentification, profil, gestion des groupes, recherche. Ils vivent derrière un répartiteur de charge classique, ils se dupliquent sans effort, et ils ne détiennent rien qu'on ne puisse perdre.

De l'autre, les serveurs de discussion, qui portent les connexions WebSocket ouvertes. Ceux-là ont un état, par construction, et cet état est la connexion elle-même. On ne les redémarre pas à la légère.

Entre les deux, il faut une table qui dit quel utilisateur est rattaché à quel serveur. C'est le rôle tenu en pratique par un service de coordination comme ZooKeeper ou etcd, ou par un magasin clé-valeur à faible latence.

Le chemin d'un message devient lisible. Alice écrit sur sa connexion ouverte vers le serveur 1. Le serveur 1 interroge la table pour savoir où se trouve Bob, apprend qu'il est sur le serveur 2, écrit le message dans le magasin, puis le transmet au serveur 2 qui le pousse sur la connexion de Bob.

Un détail change tout côté exploitation : quand un serveur de discussion tombe, ses connexions tombent avec lui. Les clients se reconnectent, le répartiteur les envoie ailleurs, et la table doit être mise à jour avant que quiconque tente de leur écrire. Une reconnexion massive et simultanée est un pic de charge à part entière, qu'on étale avec une attente aléatoire côté client.

La ligne de fracture du système passe entre ce qui se duplique et ce qui se réattribue. Les services sans état se dupliquent, les connexions se réattribuent, et ces deux opérations n'ont ni le même coût ni le même délai.

Le magasin de messages

Le registre des appels du central n'est pas un annuaire. On ne le consulte jamais par abonné pour parcourir toute sa vie ; on l'ouvre à une conversation précise, et on lit les dernières lignes.

C'est exactement le motif d'accès d'une messagerie. On lit une conversation, du plus récent vers le plus ancien, par pages. On n'écrit jamais deux fois le même message, on ne fait aucune jointure, et le volume atteint plusieurs pétaoctets.

Ce profil désigne un magasin orienté colonnes, de la famille de Cassandra, plutôt qu'une base relationnelle. La comparaison de fond entre les deux familles est traitée dans SQL ou NoSQL, on ne la refait pas ici.

La décision structurante est la clé. La clé de partition est l'identifiant de conversation, ce qui garantit qu'une lecture de discussion touche une seule partition. La clé de tri est l'identifiant de message, en ordre décroissant, ce qui rend la lecture des vingt derniers messages triviale.

CREATE TABLE message_un_a_un (
    conversation_id  uuid,
    message_id       bigint,
    expediteur_id    bigint,
    contenu          text,
    envoye_le        timestamp,
    PRIMARY KEY ((conversation_id), message_id)
) WITH CLUSTERING ORDER BY (message_id DESC);

CREATE TABLE message_groupe (
    groupe_id        uuid,
    message_id       bigint,
    expediteur_id    bigint,
    contenu          text,
    envoye_le        timestamp,
    PRIMARY KEY ((groupe_id), message_id)
) WITH CLUSTERING ORDER BY (message_id DESC);

Les deux tables sont presque identiques, et c'est volontaire. La discussion un à un est un groupe à deux membres, à ceci près que sa clé de partition se déduit du couple d'identifiants au lieu d'être créée explicitement.

Reste à produire message_id. Un compteur auto-incrémenté de base relationnelle n'existe pas ici, et un identifiant aléatoire casserait l'ordre. Il faut un identifiant à la fois unique dans tout le système et croissant dans le temps, généré sans coordination.

C'est le problème traité dans l'étude de cas du raccourcisseur d'URL, sous la forme d'un générateur de type Snowflake : horodatage sur les bits de poids fort, identifiant de machine ensuite, compteur local pour finir. L'ordre global n'est qu'approximatif entre deux machines, mais l'ordre à l'intérieur d'une conversation est correct, et c'est la seule garantie que l'exigence réclamait.

La clé de partition d'une messagerie est la conversation, jamais l'utilisateur. Partitionner par utilisateur oblige chaque lecture de discussion à interroger deux partitions, et rend le groupe de cent membres illisible.

Le message quand le destinataire est hors ligne

Le central prenait le message quand l'abonné ne répondait pas, et le lui remettait au prochain appel. La messagerie fait pareil, avec une table dédiée.

À l'écriture, le serveur fait deux choses : il ajoute le message à la conversation, et il ajoute une entrée dans la boîte de réception du destinataire. La première table sert l'historique, la seconde sert la livraison.

CREATE TABLE boite_reception (
    destinataire_id  bigint,
    message_id       bigint,
    conversation_id  uuid,
    PRIMARY KEY ((destinataire_id), message_id)
) WITH CLUSTERING ORDER BY (message_id ASC);

L'ordre est croissant ici, parce qu'on veut consommer les plus anciens en premier. Les entrées sont supprimées une fois la remise confirmée, ce qui garde la table petite.

Les accusés méritent d'être distingués nettement, parce que les utilisateurs les lisent comme un contrat. Envoyé au serveur, remis à l'appareil, lu par la personne : trois états, trois écritures, et trois occasions de dupliquer si le client rejoue sa requête après un délai d'attente. C'est le moment où l'idempotence cesse d'être une élégance théorique.

La notification poussée passe par un service tiers, APNs côté Apple, FCM côté Android. Elle n'est jamais garantie et ne transporte pas le message lui-même, seulement le signal qu'il faut ouvrir l'application et vider sa boîte.

La boîte de réception est ce qui rend la livraison indépendante de la connexion. Sans elle, le système ne remet un message que si les deux personnes sont en ligne au même instant, ce qui n'arrive presque jamais.

La présence

Sur le panneau du central, une petite lampe indiquait les lignes décrochées. C'était une information locale, lue par une seule opératrice, et rafraîchie sans coût.

En version distribuée, la même lampe devient le premier poste de trafic du système si on la traite sans réfléchir.

Le mécanisme de base est un battement de cœur. Le client envoie une trame courte à intervalle régulier sur sa connexion WebSocket, et le serveur note l'horodatage. Un client silencieux pendant trois battements consécutifs est déclaré hors ligne.

10 000 000 connexions ouvertes
/ 10 s entre deux battements = 1 000 000 battements par seconde

Un million de trames par seconde uniquement pour dire « je suis là », contre 20 000 messages réels. Le rapport est de cinquante pour un, et il n'est pas négociable : allonger l'intervalle ralentit la détection de déconnexion, le raccourcir multiplie le trafic.

Le vrai piège est ailleurs, dans la diffusion. Si chaque changement d'état est envoyé à tous les membres des groupes de l'utilisateur, l'arithmétique se retourne violemment.

20 changements d'état par utilisateur et par jour
x 1 000 destinataires par groupe   =        20 000 notifications de présence
x 50 000 000 actifs quotidiens     = 1 000 000 000 000 notifications par jour

Mille milliards de notifications de présence par jour, pour deux milliards de messages réels. Un facteur cinq cents, dépensé pour afficher un point vert.

Les parades sont simples une fois le calcul posé. On ne diffuse la présence que pour les discussions un à un et les petits groupes. Au-delà d'un seuil, le client demande la présence à l'ouverture de la conversation, et pas une seconde après. On regroupe les changements dans une fenêtre de quelques secondes plutôt que de propager chaque bascule. Et on ne considère jamais comme hors ligne un client dont la connexion vient juste de tomber, parce qu'un tunnel de métro fait tomber la connexion plusieurs fois par trajet.

La présence est la seule fonctionnalité d'une messagerie dont le coût croît avec la taille des groupes plutôt qu'avec le nombre de messages. C'est ce qui la rend dangereuse : elle grossit là où personne ne regarde.

Tout ce que la série a servi à faire tenir

Ce système n'introduit presque aucune idée neuve. Il assemble, dans un seul schéma, ce que les billets précédents ont posé un par un.

Une étude de cas réussie ne montre pas une trouvaille. Elle montre que dix décisions déjà comprises séparément tiennent ensemble sans se contredire.

Scénario B : WhatsApp et les deux millions de connexions

En janvier 2012, l'équipe d'ingénierie de WhatsApp publie un billet au titre narquois, « 1 million is so 2011 ». Elle y raconte avoir franchi le seuil de deux millions de connexions simultanées sur un seul serveur, et détaille comment.

La machine tournait sous FreeBSD, l'application était écrite en Erlang. Le billet décrit un travail de réglage à deux étages : les paramètres du noyau, en particulier les limites de sockets et les tampons TCP, et ceux de la machine virtuelle Erlang. Rien d'exotique, beaucoup de mesure.

Le choix du langage n'a rien d'anecdotique. Erlang a été créé chez Ericsson, à la fin des années 1980, pour programmer des commutateurs téléphoniques. Le langage a donc été conçu, littéralement, pour le central de La Ville : des dizaines de milliers d'appels concurrents, une isolation stricte entre eux, et une tolérance aux pannes qui n'interrompt pas les autres communications.

Son modèle de concurrence explique le résultat. Chaque connexion devient un processus léger, isolé, ordonnancé par la machine virtuelle et non par le noyau. Là où un modèle à un fil d'exécution système par connexion s'écroule bien avant le million, ce modèle traite la connexion comme l'unité de base plutôt que comme une ressource rare.

La sobriété qui en découle ressort au moment du rachat par Facebook, annoncé en février 2014 pour environ 19 milliards de dollars. L'annonce faisait état d'environ 450 millions d'utilisateurs actifs mensuels ; la presse technique a rapporté, à la même date, une équipe d'une cinquantaine de salariés, dont une trentaine d'ingénieurs.

Reprends le dimensionnement du début du billet avec ce record. On avait retenu 100 000 connexions par serveur, donc 10 000 000 / 100 000 = 100 serveurs de discussion. À deux millions de connexions par machine, la même charge donne 10 000 000 / 2 000 000 = 5 serveurs. Un facteur vingt sur la flotte, obtenu sans changer une ligne d'architecture.

Deux réserves honnêtes. Ce chiffre est un record de laboratoire mesuré en 2012, pas une capacité d'exploitation courante avec marge de sécurité. Et une messagerie chiffrée de bout en bout, avec accusés multiples et médias, coûte plus cher par connexion qu'un banc d'essai.

L'enseignement tient malgré tout : sur ce type de système, le modèle de concurrence pèse plus lourd que le nombre de machines. C'est la décision la moins visible d'un schéma d'architecture, et souvent la plus coûteuse à changer après coup.

Points clés

• Le dimensionnement d'une messagerie se joue sur les connexions simultanées, pas sur le débit de messages : 20 000 messages par seconde tiennent sur peu de machines, 10 millions de sockets ouverts non.
• WebSocket rend le serveur de discussion permanent et avec état. Le système se coupe donc en deux : ce qui se duplique librement, et ce qui doit être réattribué après une panne.
• La clé de partition du magasin de messages est la conversation, avec un identifiant de message croissant comme clé de tri. Partitionner par utilisateur casse la lecture de discussion et le groupe.
• La boîte de réception rend la livraison indépendante de la connexion, et la notification poussée reste un signal, jamais un canal de transport fiable.
• La présence est le poste qui explose en silence : diffusée sans limite, elle produit ici mille milliards de notifications par jour pour deux milliards de messages réels.

Dans la série

Palier 3 : Tenir les registres. Domaine : Études de cas.

• Précédent : Concevoir un magasin clé-valeur
• Vue d'ensemble : System design : par où commencer

Pour aller plus loin

• Concevoir un magasin clé-valeur, pour la brique qui porte ici la table utilisateur vers serveur.
• L'estimation à la louche : chiffrer avant de construire, la méthode de calcul reprise en début de billet.
• System design : par où commencer, le plan de lecture complet, à relire une fois la série terminée pour repérer ce qui mérite un second passage.
• RFC 6455, la spécification du protocole WebSocket, et la section sur les événements envoyés par le serveur du standard HTML pour l'alternative unidirectionnelle.
• RFC 8445, qui décrit ICE et par extension le problème de traversée d'adresses évoqué à propos du pair-à-pair.
• La documentation Apache Cassandra, pour les clés de partition et de tri utilisées dans le magasin de messages.
• WhatsApp, billet d'ingénierie « 1 million is so 2011 », janvier 2012, pour les réglages FreeBSD et Erlang du scénario B.