Ride-Sharing-Systemdesign: Standort-Updates, Matching und Dispatch

Ein Fahrgast tippt auf „Anfordern“ und erwartet innerhalb von Sekunden ein Auto. Hinter diesem Tippen muss das System wissen, wo sich Hunderttausende fahrende Fahrer gerade befinden, einen guten auswählen, sicherstellen, dass kein anderer Fahrgast denselben Fahrer bekommt, und dann eine Fahrt verfolgen, die mit einer Zahlung endet. Es ist eine beliebte Frage in System-Design-Interviews, weil sie einen hochvolumigen Echtzeit-Stream mit einem kleinen, strengen transaktionalen Kern verbindet.

Dieser Beitrag entwirft das Backend Schritt für Schritt: Anforderungen und Kapazitätszahlen, Standort-Ingestion, Geo-Indexierung mit Geohash, S2 und H3, Matching und Dispatch, den Zustandsautomaten der Fahrt und die Ausfälle, die du einplanen musst, mit einem Architekturdiagramm zum Nachbauen.

Anforderungen

Funktional:

• Fahrer gehen online und streamen ihren Standort.
• Fahrgäste fordern eine Fahrt an und sehen Autos in der Nähe sowie eine geschätzte Abholzeit.
• Das System bringt einen Fahrgast mit einem Fahrer zusammen, der annehmen oder ablehnen kann.
• Beide Apps verfolgen die Fahrt live; die Fahrt endet mit einem Fahrpreis und einer Zahlung.

Nicht funktional:

• Ein Match innerhalb weniger Sekunden.
• Fahrerstandorte höchstens ein paar Sekunden alt.
• Nie einen Fahrer zwei Fahrgästen zuweisen.
• Probleme einer Stadt dürfen keine anderen Städte lahmlegen.

Kapazität: die Zahlen, die das Design prägen

Nimm für eine große Installation eine Million Fahrer an, die zur Spitzenzeit online sind und alle 4 Sekunden einen Standort senden, dazu 20.000 Fahrtanfragen pro Minute:

Zwei sehr unterschiedliche Lasten zeigen sich. Standort-Updates sind gewaltig im Volumen, aber jedes einzelne ist klein, wegwerfbar und 4 Sekunden später überholt. Fahrtanfragen sind drei Größenordnungen seltener, aber jede muss genau einmal verarbeitet und mit Geld verknüpft werden. Die Architektur trennt beides.

Standort-Ingestion: nur das Aktuelle behalten

Die Fahrer-Apps senden Standorte über eine dauerhafte Verbindung wie einen WebSocket oder als kleine periodische HTTPS-Requests. Ein Standort-Gateway authentifiziert den Fahrer, verwirft unmögliche Punkte (ein Sprung von 50 km in 4 Sekunden) und schreibt jedes Update in einen Stream wie Kafka, partitioniert nach Stadt.

Drei Consumer lesen den Stream:

1. Der Live-Geo-Index behält nur die letzte Position jedes verfügbaren Fahrers, mit kurzer Ablaufzeit, sodass ein Fahrer, dessen Handy verstummt, nach beispielsweise 30 Sekunden verschwindet.
2. Das Trip-Tracking leitet die Position des zugewiesenen Fahrers an die App des Fahrgasts weiter.
3. Der Cold Storage bewahrt die vollständige Historie im Objektspeicher auf, für Analytics, ETA-Modelle und Streitfälle.

Die zentrale Entscheidung: Der heiße Index hält eine Zeile pro Fahrer, nicht eine Zeile pro Update. Eine Million Fahrer mit je etwa hundert Byte ergeben rund 100 MB, klein genug, um sie pro Stadt im Speicher zu halten.

Geo-Indexierung

Die Matching-Frage lautet: „Welche verfügbaren Fahrer sind in der Nähe dieses Punkts?“ Ein einfacher Datenbankindex auf Breiten- und Längengrad beantwortet sie schlecht, also bilden Systeme Koordinaten auf Zellen ab.

H3, das Uber 2018 als Open Source veröffentlichte, macht die Umkreissuche gleichmäßig: Nimm die Zelle des Fahrgasts und den Ring der Zellen darum herum und sammle dann die Fahrer darin ein. Die Auflösung zählt. Aus der H3-Auflösungstabelle:

Auflösung 8 oder 9 passt zu dichten Städten; ländliche Gebiete brauchen breitere Ringe oder gröbere Zellen.

Wenn du einfach anfangen willst, hat Redis eingebaute Geo-Befehle:

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, verfügbar seit Redis 6.2, liefert die 20 nächsten Fahrer im Umkreis von 2 km, nach Entfernung sortiert. Sharde zuerst nach Stadt, der natürlichen Grenze, und teile sehr belebte Orte wie Flughäfen oder Stadien in feinere Zellen auf.

Matching und Dispatch

Die Luftlinie ist ein schlechter Ersatz für die Abholzeit: Ein Fahrer 500 m entfernt auf der anderen Flussseite kann 15 Minuten brauchen. Das Matching arbeitet deshalb in zwei Stufen:

1. Kandidatenauswahl. Frag den Geo-Index nach verfügbaren Fahrern nahe dem Abholpunkt, gefiltert nach Fahrzeugtyp und weiteren Einschränkungen.
2. Ranking. Hol dir von einem ETA-Service die Abholzeiten über das Straßennetz für die besten Kandidaten und sortiere nach ETA, plus Faktoren wie der Fahrtrichtung des Fahrers.

Jede Anfrage sofort dem nächsten Fahrer zuzuordnen ist gierig. Anfragen ein, zwei Sekunden lang zu sammeln und gemeinsam als Zuordnungsproblem zu lösen, minimiert die gesamte Wartezeit über alle Fahrgäste. Der Kompromiss: eine kurze Verzögerung im Tausch gegen bessere Matches in Stoßzeiten.

Dann schickt der Dispatch jeweils einem Fahrer ein Angebot, mit einem Timeout von rund 15 Sekunden. Bei Ablehnung oder Timeout bekommt der nächste Kandidat das Angebot.

Nie einen Fahrer doppelt buchen

Zwei Matching-Worker können in derselben Sekunde denselben Fahrer für zwei Fahrgäste auswählen. Verhindere das am Zustand des Fahrers, nicht in der Matching-Logik:

• Speichere den Zustand jedes Fahrers (available, offered, on_trip) mit einer Versionsnummer.
• Ein Angebot ist ein bedingtes Update: Setz offered nur, wenn der Zustand in der gelesenen Version noch available ist.
• Genau ein Worker gewinnt; der andere geht zu seinem nächsten Kandidaten.
• Ein abgelaufenes Angebot setzt den Fahrer zurück auf available, wieder bedingt.

Dieselbe Compare-and-Set-Idee schützt die Fahrgastseite: eine aktive Anfrage pro Fahrgast.

Der Zustandsautomat der Fahrt

Eine Fahrt durchläuft requested, matching, driver_assigned, driver_arrived, in_progress, completed und paid, wobei aus mehreren Zuständen eine Stornierung möglich ist. Der Trip-Service speichert jede Fahrt in einer relationalen Datenbank wie Postgres, wendet Übergänge nur an, wenn der aktuelle Zustand sie erlaubt, und veröffentlicht jede Änderung als Event für Abrechnung, Benachrichtigungen, Belege und Analytics.

Mach jeden Übergang idempotent, mit Fahrt-ID und Zustandsversion als Schlüssel. Mobilfunknetze wiederholen Requests, und ein doppelt zugestelltes „Fahrer angekommen“ darf nichts doppelt auslösen. Das Zustandsdiagramm-Beispiel zeigt, wie du diesen Lebenszyklus für sich zeichnest.

Live-Updates, ETAs und Preise

Während einer Fahrt erhält die App des Fahrgasts die Position des Fahrers über eine Push-Verbindung, gedrosselt auf alle paar Sekunden und auf dem Client geglättet. Derselbe Standort-Stream speist den ETA-Service, der Live-Verkehrsdaten braucht, und das Surge Pricing, das pro Zelle über ein gleitendes Fenster Anfragen mit verfügbaren Fahrern vergleicht. Bezahlt wird nach der Fahrt über einen Zahlungsanbieter; diesen Teil behandelt das Diagramm zur Payment-Gateway-Integration.

Ausfälle, die du einplanen musst

• Fahrer verlieren die Verbindung. Die App sendet beim erneuten Verbinden nur den letzten Punkt, und der Index lässt verstummte Fahrer ablaufen.
• Ein Matching-Worker stürzt mitten im Angebot ab. Angebote haben Ablaufzeiten; der Fahrer kehrt zu available zurück, wenn das Angebot verfällt.
• Der Cluster einer Stadt fällt aus. Da alles nach Stadt partitioniert ist, bleibt der Ausfall lokal. Laufende Fahrten behalten ihren Zustand im dauerhaften Fahrtspeicher.
• Gefälschtes GPS. Plausibilitätsprüfungen von Geschwindigkeit und Route am Gateway fangen die plumpen Fälle ab.

Das Ride-Sharing-Diagramm

So liest du es:

• Der Rahmen ist eine Stadt, die Partitionsgrenze für alles darin.
• Der Standortpfad verläuft oben: Fahrer-App, Standort-Gateway, Kafka und von dort der Redis-Geo-Index sowie die Objektablage für die Historie.
• Der Anfragepfad verläuft darunter: Die Fahrgast-App ruft das Matching auf, das Kandidaten aus dem Geo-Index liest, beim ETA-Service Abholzeiten erfragt und das Angebot an den Fahrer schickt.
• Der Trip-Service besitzt den Zustandsautomaten und speichert ihn in Postgres.
• Der Markdown-Block zeigt die Kapazitätszahlen.

System-Design-Diagramme für Echtzeitsysteme zeichnen

• Trenn den heißen Pfad vom transaktionalen Pfad. Hier haben Standort-Stream und Fahrt-Lebenszyklus unterschiedliche Volumen, Garantien und Fehlerbilder; zeichne sie als getrennte Bahnen.
• Schreib den Partitionsschlüssel ins Diagramm. „Nach Stadt partitioniert“ erklärt Skalierung und Fehlerisolation in drei Worten.
• Zeig, was aktuell ist und was Historie. Der Index der letzten Positionen und der Historienspeicher beantworten unterschiedliche Fragen.
• Beschrifte Kanten mit Raten: 250.000 Updates pro Sekunde an einem Pfeil zeigen Reviewern, wo die Last liegt.

Zu einem allgemeinen Ansatz für solche Diagramme sieh dir das System-Design-Diagramm-Beispiel an. Push-Verbindungen behandelt das Architekturdiagramm einer Chat-App, den Stream selbst das Kafka-Architekturdiagramm.

In Archboard nachbauen

1. Melde dich mit Google oder GitHub an und leg ein Diagramm an.
2. Füge einen Rahmen aus dem Basis-Pack hinzu, benannt nach der Stadt.
3. Füge zwei Gerät-Nodes aus dem Netzwerk-Pack für die Fahrer-App und die Fahrgast-App hinzu.
4. Füge ein API-Gateway aus dem Cloud-Pack für das Standort-Gateway hinzu, einen Kafka-Node aus dem Daten-Pack für den Stream, einen Redis-Node für den Geo-Index und eine Objektablage für die Historie.
5. Füge drei Recheninstanz-Nodes aus dem Cloud-Pack für Matching-, ETA- und Trip-Service hinzu und einen Postgres-Node aus dem Daten-Pack für die Fahrten.
6. Verbinde den Standortpfad oben und den Anfragepfad darunter und beschrifte die Kanten damit, was sie transportieren und wie oft.
7. Füge einen Markdown-Block aus dem Basis-Pack mit den Kapazitätszahlen hinzu.

Das Beispiel nutzt 12 Diagramm-Nodes und bleibt damit im Free-Plan.

FAQ

Wie oft sollten Fahrer ihren Standort senden? Alle paar Sekunden ist ein üblicher Bereich. Häufigere Updates machen Positionen frischer, vervielfachen aber das Eingangsvolumen: Halbierst du das Intervall von 4 auf 2 Sekunden, verdoppelt sich der Traffic.

Sollte ich Geohash, S2 oder H3 verwenden? Alle drei funktionieren. Geohash ist am einfachsten und in Redis eingebaut; H3 liefert gleichmäßige Nachbarabstände, was Umkreissuchen und Preise pro Zelle sauberer macht. Wähl eins und nutze es konsequent.

Wie vermeidest du, einen Fahrer zwei Fahrgästen zuzuweisen? Mach das Angebot zu einem bedingten Update auf dem Zustand des Fahrers, sodass es nur gelingt, wenn der Fahrer in der Version, die der Matcher gelesen hat, noch verfügbar ist. Nur ein Matcher kann gewinnen.

Warum nicht jeden Fahrgast sofort dem nächsten Fahrer zuordnen? Gieriges Matching kann späteren Fahrgästen lange Wartezeiten bescheren. Anfragen ein, zwei Sekunden zu bündeln und gemeinsam zu lösen, senkt die gesamte Wartezeit, auf Kosten einer kurzen Verzögerung.

Welche Datenbank speichert die Fahrten? Eine relationale Datenbank passt gut: Fahrten sind transaktional, brauchen strikte Zustandsübergänge und speisen die Abrechnung. Die hochvolumigen Standortdaten liegen woanders, im Speicher und im Objektspeicher.

Kostenlos starten — ein Seat, keine Kreditkarte.