Conception d'un système de VTC : mises à jour de position, matching et dispatch

Un passager touche « Commander » et attend une voiture en quelques secondes. Derrière ce geste, le système doit savoir où se trouvent en ce moment des centaines de milliers de chauffeurs en mouvement, en choisir un bon, s'assurer qu'aucun autre passager n'obtient le même chauffeur, puis suivre une course qui se termine par un paiement. C'est une question favorite des entretiens de conception de systèmes, parce qu'elle mêle un flux temps réel à fort volume et un petit cœur transactionnel strict.

Cet article conçoit le backend pas à pas : exigences et chiffres de capacité, ingestion des positions, indexation géospatiale avec geohash, S2 et H3, matching et dispatch, machine à états des courses et pannes à prévoir, avec un diagramme d'architecture à copier.

Exigences

Fonctionnelles :

• Les chauffeurs se mettent en ligne et envoient leur position en continu.
• Les passagers demandent une course et voient les voitures proches et une estimation du temps de prise en charge.
• Le système associe un passager à un chauffeur, qui peut accepter ou refuser.
• Les deux apps suivent la course en direct ; la course se termine par un tarif et un paiement.

Non fonctionnelles :

• Un matching en quelques secondes.
• Des positions de chauffeurs qui n'ont pas plus de quelques secondes de retard.
• Ne jamais attribuer un chauffeur à deux passagers.
• Les problèmes d'une ville ne doivent pas faire tomber les autres villes.

Capacité : les chiffres qui façonnent la conception

Supposons, pour un grand déploiement, un million de chauffeurs en ligne au pic, chacun envoyant une position toutes les 4 secondes, et 20 000 demandes de course par minute :

Deux charges très différentes apparaissent. Les mises à jour de position sont énormes en volume, mais chacune est petite, jetable et remplacée 4 secondes plus tard. Les demandes de course sont trois ordres de grandeur plus rares, mais chacune doit être traitée exactement une fois et liée à de l'argent. L'architecture les sépare.

Ingestion des positions : ne garder que l'actuel

Les apps des chauffeurs envoient leurs positions sur une connexion persistante, comme un WebSocket, ou par petites requêtes HTTPS périodiques. Une passerelle de positions authentifie le chauffeur, écarte les points impossibles (un saut de 50 km en 4 secondes) et écrit chaque mise à jour dans un flux comme Kafka, partitionné par ville.

Trois consommateurs lisent le flux :

1. L'index géospatial en direct ne garde que la dernière position de chaque chauffeur disponible, avec une expiration courte, pour qu'un chauffeur dont le téléphone se tait disparaisse au bout de, disons, 30 secondes.
2. Le suivi des courses transmet la position du chauffeur attribué à l'app du passager.
3. Le stockage froid conserve tout l'historique dans un stockage objet pour l'analytique, les modèles d'ETA et le règlement des litiges.

La décision clé : l'index chaud contient une ligne par chauffeur, pas une ligne par mise à jour. Un million de chauffeurs à une centaine d'octets chacun, cela fait environ 100 Mo, assez peu pour tenir en mémoire par ville.

Indexation géospatiale

La question du matching est « quels chauffeurs disponibles sont près de ce point ? ». Un simple index de base de données sur la latitude et la longitude y répond mal, alors les systèmes projettent les coordonnées sur des cellules.

H3, qu'Uber a publié en open source en 2018, rend la recherche par rayon uniforme : prenez la cellule du passager et l'anneau de cellules autour, puis récupérez les chauffeurs qui s'y trouvent. La résolution compte. D'après la table des résolutions H3 :

La résolution 8 ou 9 convient aux villes denses ; les zones rurales demandent des anneaux plus larges ou des cellules plus grossières.

Si vous voulez commencer simplement, Redis intègre des commandes géospatiales :

GEOADD drivers:sf -122.4194 37.7749 driver:8812
GEOSEARCH drivers:sf FROMLONLAT -122.4100 37.7800 BYRADIUS 2 km ASC COUNT 20 WITHDIST

GEOSEARCH, disponible depuis Redis 6.2, renvoie les 20 chauffeurs les plus proches dans un rayon de 2 km, triés par distance. Shardez d'abord par ville, la frontière naturelle, et découpez les lieux très fréquentés comme les aéroports ou les stades en cellules plus fines.

Matching et dispatch

La distance à vol d'oiseau est un mauvais indicateur du temps de prise en charge : un chauffeur à 500 m de l'autre côté d'un fleuve peut être à 15 minutes. Le matching se fait donc en deux étapes :

1. Génération des candidats. Interrogez l'index géo pour trouver les chauffeurs disponibles près du point de prise en charge, filtrés par type de véhicule et autres contraintes.
2. Classement. Demandez à un service d'ETA les temps de prise en charge sur le réseau routier pour les meilleurs candidats, et classez par ETA, en tenant compte d'autres facteurs comme la direction du chauffeur.

Associer chaque demande instantanément au chauffeur le plus proche est une approche gloutonne. Regrouper les demandes pendant une ou deux secondes et les résoudre ensemble comme un problème d'affectation minimise le temps d'attente total des passagers. Le compromis : un court délai contre de meilleurs appariements aux heures chargées.

Le dispatch envoie ensuite une offre à un seul chauffeur à la fois, avec un délai d'expiration d'environ 15 secondes. En cas de refus ou d'expiration, le candidat suivant reçoit l'offre.

Ne jamais attribuer un chauffeur deux fois

Deux workers de matching peuvent choisir le même chauffeur pour deux passagers dans la même seconde. Empêchez-le au niveau de l'état du chauffeur, pas dans la logique de matching :

• Stockez l'état de chaque chauffeur (available, offered, on_trip) avec un numéro de version.
• Une offre est une mise à jour conditionnelle : passez à offered seulement si l'état est encore available dans la version lue.
• Un seul worker gagne ; l'autre passe à son candidat suivant.
• Une offre expirée ramène le chauffeur à available, là encore de façon conditionnelle.

La même idée de compare-and-set protège le côté passager : une seule demande active par passager.

La machine à états des courses

Une course passe par requested, matching, driver_assigned, driver_arrived, in_progress, completed et paid, avec une annulation possible depuis plusieurs états. Le service des courses stocke chaque course dans une base de données relationnelle comme Postgres, n'applique les transitions que si l'état actuel les autorise, et publie chaque changement comme un événement pour la facturation, les notifications, les reçus et l'analytique.

Rendez chaque transition idempotente, avec pour clé l'identifiant de la course et la version de l'état. Les réseaux mobiles réessaient, et un « chauffeur arrivé » livré deux fois ne doit rien faire deux fois. L'exemple de diagramme d'états montre comment dessiner ce cycle de vie à part.

Mises à jour en direct, ETA et tarification

Pendant une course, l'app du passager reçoit la position du chauffeur via une connexion push, limitée à une mise à jour toutes les quelques secondes et lissée côté client. Le même flux de positions alimente le service d'ETA, qui a besoin du trafic en direct, et la tarification dynamique, qui compare par cellule, sur une fenêtre glissante, les demandes aux chauffeurs disponibles. Le paiement a lieu après la course via un prestataire de paiement ; le diagramme d'intégration d'une passerelle de paiement couvre cette partie.

Les pannes à prévoir

• Les chauffeurs perdent la connexion. L'app n'envoie que le dernier point à la reconnexion, et l'index fait expirer les chauffeurs devenus silencieux.
• Un worker de matching plante en pleine offre. Les offres ont une date d'expiration ; le chauffeur revient à available quand l'offre expire.
• Le cluster d'une ville tombe. Comme tout est partitionné par ville, la panne reste locale. Les courses en cours conservent leur état dans le stockage durable des courses.
• GPS falsifié. Des contrôles de vraisemblance sur la vitesse et l'itinéraire, au niveau de la passerelle, attrapent les cas grossiers.

Le diagramme du système de VTC

Comment le lire :

• Le cadre est une ville, la frontière de partitionnement de tout ce qu'elle contient.
• Le chemin des positions passe en haut : app chauffeur, passerelle de positions, Kafka, puis de là l'index géo Redis et le magasin d'objets pour l'historique.
• Le chemin des demandes passe en dessous : l'app passager appelle le matching, qui lit les candidats dans l'index géo, demande au service d'ETA les temps de prise en charge et envoie l'offre au chauffeur.
• Le service des courses possède la machine à états et la stocke dans Postgres.
• Le bloc Markdown affiche les chiffres de capacité.

Dessiner des diagrammes de conception de systèmes temps réel

• Séparez le chemin chaud du chemin transactionnel. Ici, le flux de positions et le cycle de vie des courses ont des volumes, des garanties et des modes de défaillance différents ; dessinez-les comme des couloirs séparés.
• Écrivez la clé de partitionnement sur le diagramme. « Partitionné par ville » explique la montée en charge et l'isolation des pannes en trois mots.
• Montrez ce qui est actuel et ce qui est historique. L'index des dernières positions et le stockage de l'historique répondent à des questions différentes.
• Étiquetez les arêtes avec des débits : 250 000 mises à jour par seconde sur une flèche montrent aux relecteurs où se trouve la charge.

Pour une approche générale de ces diagrammes, voyez l'exemple de diagramme de conception de système. Les connexions push sont traitées dans le diagramme d'architecture d'une application de chat, et le flux lui-même dans le diagramme d'architecture Kafka.

Le construire dans Archboard

1. Connectez-vous avec Google ou GitHub et créez un diagramme.
2. Ajoutez un Cadre du pack Base portant le nom de la ville.
3. Ajoutez deux nœuds Appareil du pack Réseau pour l'app chauffeur et l'app passager.
4. Ajoutez une Passerelle API du pack Cloud pour la passerelle de positions, un nœud Kafka du pack Données pour le flux, un nœud Redis pour l'index géo et un Magasin d'objets pour l'historique.
5. Ajoutez trois nœuds Instance de calcul du pack Cloud pour les services de matching, d'ETA et de courses, et un nœud Postgres du pack Données pour les courses.
6. Reliez le chemin des positions en haut et le chemin des demandes en dessous, et étiquetez les arêtes avec ce qu'elles transportent et à quelle fréquence.
7. Ajoutez un bloc Markdown du pack Base avec les chiffres de capacité.

L'exemple utilise 12 nœuds de diagramme et reste dans les limites de l'offre Free.

FAQ

À quelle fréquence les chauffeurs doivent-ils envoyer leur position ? Toutes les quelques secondes, c'est une fourchette courante. Des mises à jour plus fréquentes rendent les positions plus fraîches mais multiplient le volume d'ingestion : diviser l'intervalle par deux, de 4 à 2 secondes, double le trafic.

Faut-il utiliser geohash, S2 ou H3 ? Les trois fonctionnent. Geohash est le plus simple et intégré à Redis ; H3 donne des distances uniformes entre voisines, ce qui rend plus propres les recherches par rayon et la tarification par cellule. Choisissez-en un et utilisez-le de façon cohérente.

Comment éviter d'attribuer un chauffeur à deux passagers ? Faites de l'offre une mise à jour conditionnelle sur l'état du chauffeur, pour qu'elle ne réussisse que si le chauffeur est encore disponible dans la version lue par le matcher. Un seul matcher peut gagner.

Pourquoi ne pas associer immédiatement chaque passager au chauffeur le plus proche ? Un matching glouton peut laisser les passagers suivants attendre longtemps. Regrouper les demandes pendant une ou deux secondes et les résoudre ensemble réduit le temps d'attente total, au prix d'un court délai.

Quelle base de données stocke les courses ? Une base de données relationnelle convient bien : les courses sont transactionnelles, exigent des transitions d'état strictes et alimentent la facturation. Les données de position à fort volume vivent ailleurs, en mémoire et dans le stockage objet.

Commencez gratuitement — un siège, sans carte bancaire.