Suchfunktionalität in Ride-Hailing-Plattformen: Destinationssuche und Rider-Driver-Matching für Ultra Large Scale Systems

Georg Bühler, Dominik Seitz

Abstract: Ride-Hailing-Plattformen wie Uber müssen zwei grundlegende Suchprobleme lösen, damit Fahrgast und Fahrer zusammenfinden. Zum einen muss der Fahrgast sein gewünschtes Ziel über eine Texteingabe finden können, zum anderen muss aus vielen verfügbaren Fahrern der passende für die Fahrt ermittelt werden. Diese Arbeit untersucht mögliche technische Umsetzungen für beide Probleme, mit Uber als praktischem Referenzbeispiel. Für die Destinationssuche wird gezeigt, dass eine lexikalische Suche über einen invertierten Index, ergänzt um Tippfehlertoleranz und Relevanz-Ranking, gut zu Standortdaten passt. Nach einem Vergleich von Elasticsearch, OpenSearch und Vespa fällt die Wahl auf OpenSearch, unter anderem wegen des offenen Lizenzmodells. Für das Rider-Driver-Matching wird eine Architektur vorgestellt, die Kafka als zentrale Datenquelle nutzt, Fahrerpositionen in Redis vorhält und rohe GPS-Koordinaten mithilfe von H3 sowie Map Matching zu verlässlichen Standortdaten generalisiert. Durch die Vorberechnung von Angebot, Nachfrage und ETA im Feature Store sowie durch Batch Matching, statt einfach den nächstgelegenen Fahrer auszuwählen, wird die Wartezeit für alle Beteiligten möglichst gering gehalten. Am Ende steht eine mögliche Architektur für beide Suchprobleme, die sowohl den funktionalen als auch den nicht-funktionalen Anforderungen einer solchen Plattform gerecht wird.

I. EINLEITUNG

Als digitale Weiterentwicklung des klassischen Taxigewerbes haben sich in den letzten Jahren Ride-Hailing-Plattformen etabliert, die Fahrten zwischen Fahrgästen und Fahrern vermitteln. Die Zahl der Nutzer solcher Plattformen soll bis 2030 weltweit auf über 2,3 Milliarden steigen [1]. Die vorliegende Arbeit betrachtet die Suchfunktionalität einer solchen Plattform. Dabei werden zwei grundlegende Suchprobleme betrachtet: die Destinationssuche und das Rider-Driver-Matching. Hinsichtlich der Destinationssuche muss der Fahrgast in der Lage sein, das gewünschte Fahrtziel über eine Texteingabe zu finden, was Herausforderungen hinsichtlich relevanter und performanter Suchergebnisse mit sich bringt. Beim Rider-Driver-Matching muss aus einer Menge verfügbarer Fahrer derjenige ermittelt werden, der für die Fahrt am besten geeignet ist, was Herausforderungen hinsichtlich räumlicher Nähe sowie weiterer Faktoren wie Wartezeit oder Auslastung mit sich bringt.

Für beide Suchprobleme werden in dieser Arbeit mögliche technische Umsetzungen erarbeitet. Als Referenz dienen dabei bestehende Plattformen, insbesondere Uber, dessen Suchinfrastruktur sich über die Jahre mehrfach gewandelt hat und damit Rückschlüsse auf praxistaugliche Lösungsansätze zulässt. Dabei wird von einem großen, geografisch verteilten System ausgegangen, wie es für den globalen Betrieb einer Ride-Hailing-Plattform notwendig ist. Ziel ist es, für beide Suchprobleme eine geeignete Architektur zu konzipieren, die den Anforderungen einer solchen Plattform gerecht wird. Im Folgenden werden zunächst die für die Destinationssuche relevanten Konzepte und Technologien vorgestellt. Darauf aufbauend werden konkrete Tools analysiert und abschließend zu einer möglichen Architektur zusammengeführt. Anschließend wird auf das Rider-Driver-Matching eingegangen. Auch hier werden zunächst die benötigten Komponenten betrachtet, bevor daraus eine resultierende Architektur abgeleitet wird.

II. DESTINATIONSSUCHE

A. Anforderungen an die Destinationssuche

Im Detail hat die Destinationssuche einer Ride-Hailing-Plattform die Aufgabe, aus der textuellen Eingabe des Kunden die gewünschten Abhol- und Zielstandorte zu bestimmen. Bereits während der Eingabe sollen dem Kunden passende Vorschläge angezeigt werden, sodass im Idealfall schon wenige eingegebene Buchstaben genügen, um den gewünschten Standort zu finden. Die final ausgewählten Standorte legen dabei nicht nur fest, von wo nach wo die Fahrt gehen soll, sondern bilden auch die Grundlage für das nachgelagerte Rider-Driver-Matching. Aus diesem Szenario lassen sich zusammen mit der Voraussetzung eines großen und geografisch verteilten Systems die folgenden Anforderungen ableiten.

Funktionale Anforderungen

• Eingabetoleranz: Die Suche muss tolerant gegenüber Tippfehlern, Abkürzungen und Synonymen sein.
• Suchvorschläge: Die Suche muss bereits während der Eingabe passende Vorschläge liefern.
• Relevanz: Die Suchvorschläge/-ergebnisse müssen möglichst relevant sein. Dabei muss sowohl die textuelle Übereinstimmung als auch Kontextfaktoren wie geografische Nähe oder Nutzerdaten berücksichtigt werden.
• Vorausbuchungen: Da Vorausbuchungen möglich sein müssen, dürfen die Ergebnisse nicht ausschließlich auf nahe Standorte begrenzt sein.

Nicht funktionale Anforderungen

• Performance: Suchanfragen müssen mit niedriger Latenz beantwortet werden, um Suchvorschläge ohne spürbare Verzögerung zu liefern.
• Aktualität: Standortdaten ändern sich selten, sollten aber änderbar sein. Änderungen müssen nicht sofort, sondern innerhalb kurzer Zeit sichtbar werden.
• Geografische Verteilung: Die Suche muss global verteilt nutzbar sein, sodass Nutzer unabhängig von ihrem Standort mit geringer Latenz suchen können.
• Verfügbarkeit: Die Suche muss hochverfügbar sein, da die Funktionalität der Plattform auf die Destinationssuche angewiesen ist.
• Skalierbarkeit: Das System muss skalierbar sein, um bei Bedarf auf wachsendes Anfragevolumen angepasst werden zu können.
• Betreibbarkeit: Das System soll sich auf ein aktives Ökosystem mit guter Dokumentation und Community-Support stützen können, um den langfristigen Betrieb zu erleichtern.

B. Grundlegende Suchkonzepte und -technologien

Bei einer geringen Anzahl an Dokumenten kann eine Suche direkt und sequenziell über den gesamten Datenbestand erfolgen. Für kleinere Dokumentenmengen ist das mit der heutigen Rechenleistung durchaus praktikabel. Mit zunehmender Größe wird dieser Ansatz jedoch ineffizient, da für jede Suchanfrage alle Dokumente durchsucht werden müssen und die Suchzeit dadurch linear mit der Anzahl der Dokumente wächst. Außerdem erschwert dieses Verfahren den Einsatz komplexerer Suchoperationen, wie beispielsweise einer Relevanzbewertung der Suchergebnisse [2]. In der Praxis haben sich zwei Suchverfahren etabliert, darunter die lexikalische Suche auf Basis invertierter Indizes und die semantische Suche.

Lexikalische Suche über invertierte Indizes

Eine effiziente Umsetzung der lexikalischen Suche erfolgt mittels invertiertem Index. Dazu wird im Vorhinein jeder einzelne Term der Dokumente auf eine Liste der Dokumente abgebildet. Für die Suche wird dann, anstatt bei jeder Anfrage alle Dokumente nach dem Term der Suchanfrage zu durchsuchen, ein Lookup des Terms im invertierten Index durchgeführt. Das Ergebnis enthält dann alle Dokumente, die diesen Term enthalten. Die Suchgeschwindigkeit bleibt dabei auch bei großen Datenmengen weitgehend erhalten [3].

Die beschriebene Funktionalität des invertierten Index ermöglicht so in der einfachsten Form zunächst nur exakte Keyword-Treffer. Bei Schreibfehlern oder alternativen Begriffen führt diese Suche zu keinen Treffern. Wie in den Anforderungen definiert wurde, muss die Suche jedoch weitestgehend dagegen tolerant sein. Verschiedene Vor-Verarbeitungsschritte müssen daher zusätzlich eingesetzt werden, um dies zu erfüllen.

Sowohl beim Erstellen des Indexes als auch bei der Suchanfrage werden die Texte zunächst mit einem Tokenizer in einzelne Tokens zerlegt. Diese Tokens sind meist einzelne Wörter [3]. Diese Tokens werden dann gewissermaßen normalisiert, indem sie in Kleinschreibung umgewandelt werden und Sonderzeichen aufgelöst werden [3] [4]. Um auch Suchergebnisse zu erhalten trotz Tippfehlern oder leicht abweichender Schreibweisen, lassen sich Fuzzy-Search-Algorithmen einsetzen. Diese erkennen Ähnlichkeiten zwischen Suchbegriffen und den indexierten Termen, beispielsweise durch die Berechnung der Levenshtein-Distanz. Dabei wird die minimale Anzahl an Einfügungen, Löschungen oder Ersetzungen bestimmt, die nötig sind, um eine Zeichenkette in eine andere umzuwandeln [5]. Für synonyme Begriffe können Synonym-Filter eingesetzt werden, die bedeutungsgleiche Worte zu dem eingegebenen Suchbegriff in den Such-Stream hinzufügen oder den initialen Suchbegriff ersetzen [6]. Dazu muss eine Synonymliste erstellt werden, hierfür lassen sich bereits existierende Listen wie beispielsweise WordNet verwenden, die dann gegebenenfalls erweitert werden können [7]. Diese Mechanismen erweitern den Suchraum über exakte Treffer hinaus und erfüllen dabei die zuvor beschriebene Anforderung hinsichtlich Toleranz gegenüber Tippfehlern, Abkürzungen und Synonymen.

Nachdem die Vor-Verarbeitungsschritte und die Suche selbst durchgeführt wurden, lassen sich die zurückgelieferten Ergebnisse auf textueller Ebene noch nach ihrer Relevanz sortieren. Ein Beispiel hierfür ist BM25, das für jedes Dokument einen Relevanz-Score in Bezug auf die Suchanfrage berechnet. Dieser Score basiert auf drei Faktoren: der Termhäufigkeit (wie oft ein Suchbegriff im Dokument vorkommt), der inversen Dokumenthäufigkeit (seltene Begriffe gelten als aussagekräftiger als häufig vorkommende) sowie einer Normalisierung bezüglich der Dokumentlänge, damit längere Dokumente nicht allein aufgrund ihrer Länge bevorzugt werden [8]. Damit bildet BM25 eine mögliche textuelle Grundlage für Relevanz von Suchergebnissen.

Der invertierte Index sowie die beschriebenen Vor-Verarbeitungsschritte und das textuelle Ranking müssen nicht von Grund auf selbst implementiert werden. Stattdessen lässt sich Apache Lucene verwenden, das praktisch als Industriestandard dafür gilt [9]. Für die Vor-Verarbeitungsschritte und das textuelle Ranking, beispielsweise BM25, lassen sich entsprechende Funktionen der Library nutzen. Der invertierte Index selbst wird als immutable erstellt, ein einmal geschriebener Index kann also nicht mehr verändert werden. Dies ermöglicht, dass mehrere Threads gleichzeitig lesen können, ohne dass Locking erforderlich ist. Damit trotzdem neue Dokumente aufgenommen werden können, löst Lucene dies über sogenannte Segmente. Für neue Dokumente wird dann jeweils ein eigenes Segment angelegt, das selbst wieder ein invertierter Index ist. Alle Segmente zusammen ergeben den vollständigen Index [10]. Ein neues Dokument gelangt dabei zunächst in einen In-Memory-Buffer, wird anschließend über einen Refresh als durchsuchbares Segment im Filesystem-Cache verfügbar gemacht und schließlich über einen Flush persistent auf die Disk geschrieben [11]. Mit der Zeit entstehen durch dieses Verfahren viele kleine Segmente sowie eventuell einige für die Löschung markierte Einträge. Deshalb führt Lucene periodisch ein Merging durch. Dabei werden zum einen die für die Löschung markierten Dokumente endgültig entfernt, wodurch Speicher freigegeben wird. Zum anderen werden viele kleine Segmente, die sonst zu schlechterer Suchperformance führen können, zu wenigen, möglichst gleich großen Segmenten zusammengeführt [12].

Semantische Suche

Die lexikalische Suche ermittelt Ergebnisse auf der textuellen Ebene. Durch die zuvor genannten zusätzlichen Methoden lässt sich diese um Tippfehler-Toleranz sowie zusätzliches Suchen nach Synonymen erweitern, statt nur Terme exakt zu vergleichen. Die semantische Suche hingegen ermittelt bedeutungsnahe Ergebnisse zu der Suchanfrage. Dabei werden Wörter oder ganze Dokumente in numerische Vektoren umgewandelt, welche die Bedeutung der Inhalte abbilden. Inhalte mit ähnlicher Bedeutung liegen im Vektorraum näher beieinander und können dadurch gefunden werden, auch wenn unterschiedliche Begriffe verwendet werden [13].

Für die Suche wird der Vektorraum nach Vektoren durchsucht, die räumlich nahe dem Vektor liegen, der die Suchanfrage repräsentiert. Die exakte Suche nach den nächsten Vektoren wird bei großen Datenmengen jedoch ineffizient, da die Ähnlichkeit mit allen gespeicherten Vektoren berechnet werden müsste. Deshalb kommen für die Suche Approximate-Nearest-Neighbor-Verfahren wie HNSW (Hierarchical Navigable Small World) zum Einsatz. Diese suchen nicht nach einer exakten, sondern nach einer möglichst guten Annäherung der nächsten Vektoren, wodurch sich der Berechnungsaufwand deutlich reduzieren lässt [13]. Für die Destinationssuche ist semantische Suche jedoch von geringerer Relevanz. Standort- und Adressbezeichnungen sind meist eindeutige Eigennamen ohne bedeutungsnahe Alternativen. Die lexikalische Suche gepaart mit einem Synonym-Filter ist für den Anwendungsfall demnach besser geeignet.

Ergänzende Bausteine der Suche

Ein weiterer wichtiger Faktor für die Bestimmung der Relevanz von Ergebnissen sind Kontextfaktoren wie geographische Nähe, Nutzerdaten oder auch die Uhrzeit. Hierfür lässt sich ein Machine Learning Modell einsetzen, das Suchergebnisse anhand dieser zusätzlichen Faktoren bewertet und darauf basierend sortiert. Beispielsweise kann ein Learning-to-Rank-Modell verwendet werden, das mithilfe von Machine-Learning-Verfahren verschiedene Merkmale berücksichtigt, um die erwartete Relevanz von Suchergebnissen zu bestimmen und diese entsprechend zu ordnen [14].

Für Standorte, für die keine zugehörigen Koordinaten vorliegen, kann Geocoding verwendet werden, um aus der Adresse in Textform geografische Koordinaten zu ermitteln. Hierfür gibt es verschiedene APIs, wie beispielsweise die Google Geocoding API [15].

Für die technische Umsetzung einer Autovervollständigung können verschiedene Ansätze eingesetzt werden. Ein Ansatz besteht darin, die möglichen Vervollständigungen separat in einer eigenen Datenstruktur zu indexieren. Optional lässt sich dabei eine Relevanz vergeben, beispielsweise basierend darauf, wie häufig ein Begriff gesucht wird. Bei einer Eingabe werden die passendsten Vervollständigungen direkt aus dieser Datenstruktur zurückgegeben, ohne dass dabei auf den regulären invertierten Index zugegriffen wird. Ein weiterer Ansatz ist die Indexierung von Wortpräfixen. Hierbei werden bereits beim Indexieren Wortpräfixe als eigene Tokens im regulären invertierten Index abgelegt, sodass die Autovervollständigung direkt darüber läuft [16].

Für die Standortdaten selbst wird eine Datenquelle benötigt, aus der Orte mit ihren zugehörigen Informationen wie Namen, Adressen und Koordinaten stammen. Hierfür können externe Provider genutzt werden, die eine Datenbank mit Orten sowie eine Schnittstelle zur Abfrage dieser Orte bereitstellen. Ein Beispiel hierfür ist die Places API von Google [17].

C. Verteilte Suchtechnologien

Die zuvor beschriebenen Suchtechnologien liefern bereits die Grundlagen dafür, die funktionalen Anforderungen zu erfüllen. Bezüglich der nicht-funktionalen Anforderungen, besonders Skalierung und geografischer Verteilung, zeigen die beschriebenen Technologien noch keine mögliche Umsetzung. Apache Lucene selbst bietet keine Möglichkeit die Suche verteilt zu betreiben. Die Verteilung von Daten über mehrere Knoten hinweg sowie deren Koordination ist damit nicht Teil von Lucene selbst und müsste manuell drumherum implementiert werden [18].

Im Folgenden werden daher Suchtechnologien untersucht, die diese Funktionalitäten bereits mitbringen, sodass sie nicht von Grund auf selbst implementiert werden müssen. Dafür wurden Elasticsearch (ES) und OpenSearch (OS) untersucht, da diese praktisch die Industriestandards darstellen. OpenSearch ist ein Fork von Elasticsearch, den AWS 2021 erstellte, nachdem Elastic auf ein restriktiveres Lizenzmodell wechselte, und wird seitdem unter der Apache License 2.0 weitergeführt [19]. Ergänzend wurde Vespa hinzugezogen, das für seine Fähigkeiten in der semantischen Suche bekannt ist, aber auch lexikalische Suche unterstützt [20]. Der Vergleich betrachtet dazu Query-Speed, Datenaktualität, Skalierung, Replikation, geografische Distribution, Ranking mit Kontextfaktoren, Autovervollständigung sowie das jeweilige Ökosystem.

Query Speed Für den direkten Vergleich zwischen OS und ES liegen Benchmark-Daten von Trail of Bits vor, einem auf Cybersicherheit spezialisierten Unternehmen, das im Auftrag von AWS einen Vergleich zwischen beiden Systemen durchgeführt hat [21]. Bei der für die Destinationssuche relevantesten Operation, einfachen Term-Abfragen, zeigt sich praktisch kein Unterschied zwischen beiden Systemen. Für Vespa existieren ausschließlich herstellereigene Benchmark-Daten, die einen deutlichen Geschwindigkeitsvorteil zu ES bei lexikalischer Suche aufzeigen [22]. Diese Zahlen sind jedoch nicht unabhängig verifiziert und daher mit Vorsicht zu betrachten.

Datenaktualität Da sowohl ES als auch OS auf Apache Lucene aufbauen, ist die Datenaktualität durch das Refresh-Intervall von Lucene begrenzt. Demnach ist Near-Real-Time die maximal erreichbare Aktualität [11]. Auch bei Vespa werden Dokumente nicht sofort, sondern erst nach einem periodischen Flush durchsuchbar, ähnlich wie bei Lucene, auch wenn Vespa nicht auf Lucene basiert [23].

Skalierung Bei der Skalierung folgen ES und OS demselben Prinzip: Beide setzen auf statisches Sharding, das heißt, die Anzahl der Shards wird bereits beim Erstellen des Index festgelegt [24] [25]. Müssen weitere Shards hinzufügt werden, muss der Index neu erstellt werden, da die Anzahl der Shards für einen existierenden Index nicht mehr angepasst werden können [26]. Vespa hingegen setzt auf dynamisches Sharding, bei dem keine feste Zahl vorgegeben werden muss, sondern sich die Verteilung automatisch nach Bedarf anpasst [27]. Das reduziert den administrativen Aufwand, geht jedoch mit geringerer Kontrolle über die konkrete Datenverteilung einher.

Replikation ES und OS folgen dem Prinzip der Active-Passive-Replikation: Änderungen werden zunächst auf einem Primärshard angewendet und dann an die Replicas verteilt [28]. Vespa schreibt stattdessen synchron auf alle verfügbaren Replicas parallel und wartet auf deren Bestätigung, ohne festen Primärknoten [29].

Geografische Distribution ES und OS bieten mit Cross-Cluster Replication (CCR) ein dediziertes Feature für den Betrieb über mehrere Rechenzentren hinweg. Mehrere unabhängige Cluster werden dabei nach dem Active-Passive-Prinzip über Regionen hinweg repliziert [30] [31]. Bei Vespa gibt es kein Äquivalent zu CCR. Knoten müssten stattdessen innerhalb einer einzigen, zusammenhängenden Einheit geografisch verteilt werden [29].

Ranking mit Kontextfaktoren Bei ES und OS kann Learning to Rank über ein separates Plugin eingesetzt werden [32] [33]. Bei Vespa ist Ranking hingegen ein natives Kernfeature. Beliebige Kontextsignale lassen sich direkt in die Ranking-Expression einbinden, ohne zusätzliches Plugin [34].

Autovervollständigung ES und OS unterstützen beide zuvor beschriebenen Ansätze. Zum einen das Plugin Completion Suggester, das Vervollständigungen in einer eigenen, separaten Datenstruktur indexiert. Zum anderen die Option, Wortpräfixe direkt im regulären invertierten Index abzulegen und somit auf die normale Suchinfrastruktur zurückzugreifen [16] [35]. Vespa bietet dafür keine fertige Lösung, eine Präfixsuche müsste selbst umgesetzt werden [36].

Ökosystem ES und OS verfügen beide über eine große Community und ein breites Angebot an Zusatzwerkzeugen. OpenSearch ist dazu vollständig quelloffen. Vespa hat demgegenüber eine deutlich kleinere Community und gilt als weniger etabliert. Hinsichtlich verfügbarer Ressourcen sind ES und OS damit im Vorteil.

D. Praxisbeispiel: Uber

Ein Blick auf Uber als große Ride-Hailing-Plattform lohnt sich, da sich deren Suchinfrastruktur über die Jahre mehrfach gewandelt und weiterentwickelt hat. Uber setzte vor 2019 auf Elasticsearch, stellte jedoch fest, dass die Near-Real-Time-Aktualität für bestimmte Anwendungsfälle nicht ausreichte [37]. Für die Destinationssuche selbst erscheint das zunächst weniger naheliegend, da sich Standortdaten selten ändern und nicht unbedingt Echtzeit aktuell sein müssen. Es dürfte sich also eher um einen anderen Bereich von Uber gehandelt haben, der auch Teil derselben Suchinfrastruktur ist.

Als Reaktion entwickelte Uber mit SIA (2019 bis 2024) eine eigene, auf Apache Lucene basierende Lösung mit Echtzeit-Fähigkeiten. Der Kern war ein dreischichtiger Index: ein Live-Index, der neue Daten sofort im RAM durchsuchbar macht, ein Snapshot-Index, der den Live-Index periodisch (alle 30 Minuten) auf die Disk schreibt, sowie ein Base-Index, in dem die Snapshots wöchentlich zusammengeführt werden. Ergänzend führte Uber gRPC statt REST für effizientere Service-Kommunikation ein und stellte auf eine Kafka-basierte Pull-Ingestion um, wodurch Backpressure-Handling ermöglicht wird. Zusätzlich implementierte Uber Active-Active-Cross-Cluster-Replikation statt der zuvor üblichen Active-Passive-Variante [37]. Bei Active-Active können, im Unterschied zum Leader-Follower-Prinzip von OS und ES, bei dem nur der Leader-Cluster Schreibvorgänge annimmt, alle Regionen Änderungen annehmen. Eine Änderung wird dabei zunächst in das lokale Kafka der jeweiligen Region geschrieben, das sie anschließend an die Kafka-Instanzen aller anderen Regionen verteilt, wo sie wiederum von den dortigen Suchclustern konsumiert wird [38].

SIA erwies sich jedoch langfristig als problematisch. Die Eigenentwicklung war wartungsintensiv, und neue Lucene-Features ließen sich nur schwer integrieren. Zudem zeigte sich, dass die meisten tatsächlichen Anwendungsfälle gar kein Echtzeit-Indexing benötigten und mit Near-Real-Time-Aktualität ausreichend bedient waren. Da eine Eigenentwicklung zudem kaum mit der schnellen Innovationsgeschwindigkeit im Such- und KI-Bereich mithalten konnte, entschied sich Uber 2024 im Rahmen von Project Sunrise für den Umstieg auf OpenSearch, unter anderem auch, um direkt an dessen Weiterentwicklung mitzuwirken. Bewährte Konzepte aus SIA wie die gRPC-Kommunikation und die Pull-based-Ingestion wurden dabei zu OpenSearch übernommen [37].

Die Entwicklung bei Uber zeigt, dass eine Eigenentwicklung schwer zu warten ist und nur schwer mit der Innovationsgeschwindigkeit etablierter Systeme mithalten kann. Uber hat sich letztlich wegen des Open-Source-Gedankens für OS statt ES entschieden, um dort eigene Erkenntnisse einzubringen [37].

E. Technologiewahl

Basierend auf der vorangegangenen Betrachtung der Tools sowie dem Praxisbeispiel Uber fällt die Wahl auf OpenSearch. Zwischen ES und OS selbst gibt es kaum Unterschiede: Bei Query-Speed für einfache Term-Abfragen, dem für die Destinationssuche relevantesten Fall, zeigt sich praktisch kein Unterschied. Auch bei Datenaktualität, Skalierung und Replikation folgen beide demselben architektonischen Prinzip, da OS ursprünglich ein Fork von ES ist. Den Ausschlag gibt daher das Lizenzmodell: OpenSearch steht vollständig unter der offenen Apache License 2.0, während neuere Elasticsearch-Versionen unter der restriktiveren Elastic License stehen, ein Aspekt, den auch Uber als Grund für die Wahl von OpenSearch statt Elasticsearch anführt. Gegen Vespa spricht vor allem, dass es als noch nicht so etabliertes Tool wie ES und OS ein gewisses Risiko birgt, da ES und OS bereits vielfach in großen Systemen im praktischen Einsatz bewiesen haben, dass sie zuverlässig funktionieren. Zudem hat Vespa eine deutlich kleinere Community und bietet hinsichtlich Query-Speed und Datenaktualität keinen belegten Vorteil gegenüber OpenSearch.

F. Architektur

Für eine konkrete mögliche Umsetzung besteht die Architektur aus fünf zentralen Komponenten: dem Search Service als zentrale orchestrierende Komponente, dem OpenSearch-Cluster für die eigentliche Suche, einem User Service, der Informationen zu Nutzern abruft, einem Standortdaten-Provider als Datenquelle sowie Kafka als Puffer zwischen Datenquelle und Suchcluster. Dabei wird das Setup pro Region repliziert, sodass Nutzer weltweit mit geringer Latenz auf ein nahegelegenes Cluster zugreifen können.

Für die Aktualisierung der Standortdaten wird sich an der Umsetzung von Uber orientiert. Der Standortdaten-Provider liefert initial die Daten zur Erstellung des Index sowie im laufenden Betrieb Änderungen an bestehenden Standorten. Diese Änderungen können dabei in jeder Region eingetragen werden und gelangen zunächst in ein lokales Kafka, das sie an die Kafka-Instanzen aller anderen Regionen verteilt. Damit wird das Active-Active-Prinzip angewendet: Es kann aus jeder Region geschrieben werden, statt wie beim üblichen OpenSearch-Leader-Follower-Prinzip nur in einer primären Region. Jedes regionale OpenSearch-Cluster konsumiert die Änderungen anschließend über die Pull-based-Funktionalität. Innerhalb des OpenSearch-Clusters kommen mehrere Komponenten zum Einsatz. Für die Autovervollständigung werden zwei Ansätze kombiniert eingesetzt. Der Completion Suggester speichert häufig gesuchte Ergebnisse zu den entsprechenden Präfixen in einer eigenen, schnellen In-Memory-Datenstruktur. Über die Geo-Context-Funktion wird dabei auch der geografische Bereich der Einträge gespeichert, wodurch sich schnell populäre Ergebnisse aus der Nähe abfragen lassen. Ein separates Caching ist dadurch nicht erforderlich, da der Completion Suggester bereits selbst als schnelle, In-Memory-Datenstruktur für die häufigsten Anfragen fungiert. Ergänzend wird der Index mit der Option erstellt, zusätzliche Wortpräfixe zu speichern, damit auch der reguläre invertierte Index für die Suche noch unvollständiger Anfragen verwendet werden kann. Des Weiteren kommt das Learning-to-Rank-Plugin zum Einsatz, um Ergebnisse basierend auf Kontextfaktoren zu bewerten. Der beschriebene Aufbau ist in Abbildung 1 dargestellt.

Eine Anfrage läuft dann wie folgt ab. Während der Nutzer seine Anfrage eingibt, wird bereits mit den ersten eingegebenen Buchstaben eine Anfrage gesendet. Dieser Anfrage werden zusätzlich die Nutzerkennung und optional der aktuelle Standort mitgegeben. Die Anfrage wird über das API Gateway an den Search Service übermittelt. Dieser fragt zum einen den User Service nach Informationen zu diesem Nutzer ab und leitet zum anderen die Anfrage zusammen mit dem Standort an das OpenSearch-Cluster weiter. Innerhalb des OpenSearch-Clusters werden dabei parallel der Completion Suggester sowie der invertierte Index angefragt. Liefert der Completion Suggester populäre Ergebnisse, die mit dem geografischen Standort vereinbar sind, werden diese zurückgeliefert. Liefert der Completion Suggester keine Ergebnisse, wird auf das Ergebnis der bereits parallel angefragten Suche über den invertierten Index gewartet. Die Ergebnisse durchlaufen anschließend das Ranking des Learning-to-Rank-Plugins, das sie basierend auf dem mitgeschickten Standort sowie weiteren Kontextfaktoren bewertet und die relevantesten Ergebnisse zurückliefert. Der Search Service fügt den Ergebnissen gegebenenfalls Standorte aus der zuvor vom User Service abgefragten Nutzerhistorie hinzu, sofern diese mit der Suchanfrage übereinstimmen. Die sortierten Ergebnisse werden abschließend über das API Gateway an den Nutzer zurückgeliefert.

III. RIDER-DRIVER MATCHING

Im vorherigen Schritt wurde der gewünschte Zielort des Nutzers erschlossen. Die zweite Hauptaufgabe der “Uber Search Plattform” besteht darin, den bestmöglichen Fahrer für den Kunden zu finden, damit der Kunde einen Auftrag aufgeben kann. Dieser Schritt wird “Rider-Driver Matching” genannt. Das Architektur-Diagramm in Abbildung 2 zeigt sämtliche benötigten Komponenten, die für diese Funktionalität benötigt werden. In den folgenden Unterkapiteln werden die einzelnen Architekturentscheidungen aus dem Diagramm Schritt für Schritt erläutert.

A. Scenario

Das gewünschte Endresultat ist eine informative Übersichtsseite (siehe Abbildung 3). Der Ablauf zum Finden eines Paares benötigt folgende Schritte:

1) Es müssen kontinuierliche Standort-Updates der Fahrer, sowie der Standort des Kunden ermittelt werden. Mit dem gewünschten Zielort aus dem vorherigen Schritt kann somit die Route und daraus abgeleitete Metriken wie die Estimated Time of Arrival (ETA) oder der Preis ermittelt werden.

2) Retrieval: Aus allen georteten Fahrern müssen naheliegende und verfügbare ermittelt werden, wobei diese visualisiert und der Bestmögliche für die Angebots- bzw. Preiserstellung ausgewählt wird.

3) Reservierung: Dieser Fahrer bekommt eine Anfrage vom Kunden, und ist somit reserviert, bis er den Auftrag ablehnt oder annimmt. Nimmt er ihn an, so ist ein Paar gefunden. [39] Hierbei ist es wichtig, dass Konsistenz gewährleistet ist, damit keine Doppelbuchungen auftreten.

B. Nicht-funktionale Anforderungen

Damit das Matching-System eine Vielzahl von Nutzern zufriedenstellen kann, sind folgende Anforderungen wichtig, die es erfüllen muss:

• Eine geringe End-to-End-Latenz für das Bilden und Anzeigen des Fahrer-Kunden-Paares. Der Richtwert von unter einer Sekunde ist hierbei sinnvoll, da in dieser kurzen Wartezeit der Gedankenfluss des Nutzers nicht unterbrochen wird. [40]
• Eine hohe Verfügbarkeit von 99,9%, wofür redundante Serverstandorte den Ausfall einzelner Regionen abfangen müssen. [37]
• Datenaktualität in Form von sekündlich aktualisierten Fahrerstandorten.
• Eine gute Skalierbarkeit, da das System eine steigende Anzahl an Nutzeranfragen verarbeiten und mit Lastspitzen wie z.B. Freitagabenden oder Silvester rechnen muss.

C. Empfangen von Location-Daten

Die erste getroffene architektonische Entscheidung umfasst, wie die Standorte aller Fahrer kontinuierlich an die Server übermittelt werden (siehe Schritt 1 in Abbildung 2). Der naheliegendste Ansatz ist hier, dass sämtliche Fahrer-Clients ihre Daten über HTTP-Requests an REST-APIs senden, die auf dem Server eingerichtet sind. Dabei sind jedoch einige Nachteile zu beachten. Clients müssen auf die Antwort des Servers auf ihre HTTP-POST-Requests warten. Außerdem wird bei jedem Update ein Overhead durch TCP- bzw. TLS-Handshakes erzeugt. [41] Zudem fehlt ein eingebauter Verteilermechanismus, wodurch der empfangende Server die Daten selbst an die dahinterliegenden Systeme (z.B. zum Berechnen der Route) weiterleiten müsste. Direktes Schreiben in eine Datenbank ist ebenfalls nicht sinnvoll, da u. a. die Datenmenge zu groß ist und die Datenbank somit schnell überlastet wäre. Um wiederholten Overhead zu vermeiden, ist es sinnvoll, eine persistente Verbindung (Session) zwischen Fahrer-Client und Server aufzubauen. Es liegt nahe, dies über eine Websocket-Schnittstelle zu realisieren, jedoch ist diese Technologie zu limitiert. Sie bietet keinen automatischen Wiederaufbau von Verbindungen und keinen Backpressure-Mechanismus. Mit letzterem könnte der Client gebremst werden, falls der Server gerade keine weiteren Daten empfangen kann. [42]

Der weiterentwickelte Ansatz einer Message-Queue bringt Vorteile mit sich. Hierbei werden Messages (Standortdaten) in einem Puffer gespeichert, wodurch der Daten-Produzierende (hier: der Fahrer-Client) vom Empfänger entkoppelt wird, und ersterer bspw. nicht auf die Datenverarbeitung des Servers warten muss. [43] Durch den Puffer wird ebenso Ausfallsicherheit sowie das Abfangen von Lastspitzen verbessert.

Der Broker ist hierbei die zentrale Komponente, die die Daten entgegennimmt und an die dahinterliegenden Konsumenten (Routing- oder Pricing-Service) weiterleitet. Konsumenten müssen sich explizit beim Broker für den Datenempfang anmelden. Nachdem sie das Empfangen einer Datensequenz bestätigt haben, wird diese beim Broker gelöscht, wodurch kein Replay der Daten mehr erfolgen kann. [44]

Eine deutlich geeignetere Lösung stellt hier Apache Kafka dar. Dabei handelt es sich um eine Plattform, die ausdrücklich für das Event-Streaming von Echtzeitdaten entwickelt wurde. Daten werden von den Produzenten an ein Topic mit einem Key geschickt, bspw. ein Topic mit einer Postleitzahl “driver-locations-70178” und der ID des Fahrers als Key. Das Topic dient zur Gruppierung von zusammengehörigen Daten, und der Key gibt die Partition an, auf der ein geordnetes Log geführt wird, in welchem die Nachrichten (Standortdaten) gespeichert werden. Somit können stets chronologisch die Standortdaten eines jeden Fahrers abgerufen und bei zwischenzeitlichem Ausfall erneut angefragt bzw. an Konsumenten wiederholt weitergeleitet werden (Replay). Bei der sog. Pull-based ingestion fragen Konsumenten selbst die Daten beim Broker an, wodurch beliebig viele Konsumenten im Entwicklungsverlauf hinzugefügt werden können, ohne dass der Broker davon wissen muss. [45]

D. Map Index Updater

Das erste Ziel der Suchübersicht ist es, Fahrer im Umkreis des Kunden zu finden. Ein trivialer Ansatz würde die Abstände zwischen dem Kunden und allen Fahrern in dessen Region berechnen, wobei die relevanten Standortdaten über das korrekte Kafka-Topic gefiltert werden könnten. Dies ist jedoch einerseits überkorrekt, da die genaue Distanz nicht benötigt wird, sondern nur die Information, ob ein Fahrer in der Nähe ist. Andererseits werden fast nie zwei Anfragen von exakt dem gleichen Standort gemacht, weshalb die Berechnungen nicht wiederverwendet werden können.

Aus diesen Gründen ist es vorteilhafter, bei Standorten nicht exakte Koordinatenpunkte, sondern Flächen zu verwenden. Diese Umwandlung geschieht durch einen Map Index Updater (siehe Schritt 2 in Abbildung 2).

Uber verwendet hierfür das hierarchische Raumindex-System H3, welches die gesamte Erde in ein gleichmäßiges Gitter aus eindeutig identifizierbaren Sechsecken aufteilt. Jede GPS-Koordinate kann somit einer Hexagon-Zelle zugeordnet werden. Bereits vorhandene Regionensysteme wie z.B. Stadtteile oder Postleitzahlen werden nicht als Flächenform verwendet, da diese unregelmäßige Formen haben und potenziell mit der Zeit verändert werden könnten und sich deshalb nicht für Kalkulationen eignen. Hexagons hingegen haben den Vorteil, dass ein gleichmäßiger Abstand zu allen Nachbarn gegeben ist.

Einer H3-Zelle werden Metriken wie verfügbare Fahrer, durchschnittliche Fahrtdauer zu einer anderen Zelle oder ein Preis-Multiplikator zugeordnet. Um stark unterschiedliche Werte zwischen zwei Nachbarzellen zu vermeiden, was bspw. bei Preisen zu einer schlechten Kundenerfahrung führen würde, können folgende Funktionen angewendet werden:

• Mit der kRing(index, k)-Funktion können alle Nachbarzellen bis zu einer Distanz von k Ringen um die Zelle index ermittelt werden.
• Mit den gesammelten Daten kann Smoothing eingesetzt werden, wobei der Wert einer Zelle mit den durch kRing gesammelten Nachbarwerten gemittelt wird. In Abbildung 4 führt dies beispielsweise dazu, dass die zentrale Zelle mit Preismultiplikator 5 und deren Nachbarzellen aneinander angepasst werden.

In Abbildung 4 führt dies beispielsweise dazu, dass die zentrale Zelle mit Preismultiplikator 5 und deren Nachbarzellen aneinander angepasst werden. Somit können drastische Preissprünge vermieden werden, nur weil der Kunde sich einen Straßenblock weiter bewegt. [46]

E. Map Matching

Ein Hindernis beim Nachverfolgen von Fahrern besteht darin, dass GPS-Daten zeitweise ungenau sind und Koordinaten beinhalten, die nicht auf Straßen liegen. Diese Daten einfach zu übernehmen hätte eine negative Auswirkung auf die Benutzeroberfläche, bspw. wenn ein Auto in einem Gebäude angezeigt wird, und könnte zu Problemen bei der Routenberechnung führen. Die hauptsächlichen Gründe für diese Ausreißer sind geländebedingt, wie etwa Straßenschluchten zwischen hohen Gebäuden, bei denen das GPS-Signal von Fassaden reflektiert wird, bevor es den Empfänger erreicht. [47, S. 337] Dieses Problem wird durch einen Map Matcher gelöst (siehe Schritt 3 in Abbildung 2), welcher GPS-Koordinaten auf die korrekte Straße abbildet. Dabei wird das sog. Hidden Markov Model (HMM) verwendet, bei dem neben der Entfernung zur nächsten Straße auch der Kontext, also vorher und nachher gesendete Koordinaten, ausgewertet wird, um die korrekte Straße zu bestimmen. Das Map Matching wird auf zwei Ebenen angewandt: Ein niedrig-latenter Matcher lässt die Fahrer nahezu in Echtzeit auf den Straßen erscheinen, während ein Offline-Matcher das CATCHME-System mit Standortdaten füttert.

CATCHME steht für “Catch Map Error” und wertet Routeninformationen aus, um das Uber-eigene Straßensystem zu optimieren. Befinden sich wiederholt Daten am gleichen Punkt neben anstatt auf einer berechneten Route, so ist dies ein Zeichen dafür, dass die eigentliche Straße neu gezeichnet werden muss. [48]

F. Standortspeicherung

Für das Speichern der verarbeiteten Live-Standorte (siehe Schritt 4 in Abbildung 2) wird die In-Memory-Datenbank Redis verwendet, da diese die Daten direkt im RAM anstatt auf der Festplatte hält und dadurch besonders schnelle Lese- /Schreibzugriffe ermöglicht. [49]

Aufgrund der überaus großen Datenmenge wird ein Sharding-Layer namens “Ringpop” eingesetzt, in welchem mehrere Redis-Server ringförmig angeordnet werden, wobei jedem Server ein fester Teilbereich der Fahrerdaten z.B. basierend auf geographischer Region zugeteilt wird [50], [51].

Falls ein Server ausfällt oder entfernt wird, kommunizieren die Server untereinander über das Peer-to-Peer-Gossip-Protokoll (SWIM) und ermitteln einen anderen Server als neuen Speicherort [50]. Das Moving-Driver-Problem, bei dem ein Fahrer durch Bewegung den geographischen Bereich eines Servers verlässt, kann gelöst werden, indem die Verbindung zum ursprünglichen Server aufrechterhalten wird, und dieser die Daten einfach an den korrekten Server weiterleitet [50]. Durch das Replizieren von Daten auf mehreren Servern kann außerdem die Ausfalltoleranz erhöht werden [50], [51].

G. Routing-Service

Der Routing-Service hat die Aufgabe, die Fahrzeit und somit auch die Estimated Time of Arrival (ETA) zwischen Kunden und Zielort zu berechnen (siehe Schritt 5 in Abbildung 2), was für weitere Schritte wie Preisberechnung und Fahrer-Matching benötigt wird. Der klassische Ansatz, das Straßennetz als Graphen zu modellieren, bei dem die benötigte Fahrtzeit einer Strecke das Kantengewicht darstellt, und per Shortest-Path-Algorithmus (z.B. Dijkstra) diese Gewichte aufzusummieren, um die optimale Route zu finden, scheitert jedoch. Fahrtzeiten sind nämlich nicht statisch, sondern ändern sich je nach Tageszeit, Wochentag und Verkehrslage. Uber entwickelte daher den DeepETA-Algorithmus, ein nachgeschaltetes (“Post-Processing”) Deep-Learning-Modell. Anhand der o.g. Daten sowie vergangenen Fahrt- und Ankunftszeiten sagt es pro Zeitfenster und H3-Zelle sog. Residuals, die die prognostizierte Abweichung zwischen der ursprünglichen Routing-Engine-Schätzung und der tatsächlichen Fahrzeit angeben. Zum Beispiel erhält eine H3-Zelle mit einer Straßenkreuzung, die wochentags um 7:10 Uhr stark frequentiert wird, für diesen Zeitrahmen ein Residual von +2 Minuten, welches in sämtliche ETA-Berechnungen einfließt. [52]

H. Surge Pricing

Für das Erfüllen von Aufträgen sind manche Regionen für Fahrer attraktiver als andere. Innenstädte bieten beispielsweise eine hohe Auftragsdichte, jedoch sind dafür meist die Straßen überfüllter, Park- oder Haltegelegenheiten seltener und die Fahrtzeiten dadurch länger. Um hier dennoch der Nachfrage gerecht zu werden, implementiert Uber mit dem “Surge Pricing” eine dynamische Preisgestaltung (siehe Schritt 6 in Abbildung 2), die durch Boni bzw. höhere Multiplikatoren gezielt Anreize für Fahrer in bestimmten Regionen setzt und die Fahrer dadurch gleichmäßig auf die Karte verteilt. [53] Damit Fahrer sich bereits im Voraus vorteilhaft positionieren können, müssen diese Werte vorab berechnet werden. Weitere Faktoren, die zu einem hohen Preis-Multiplikator zu einer bestimmten Zeit an einem bestimmten Ort führen, sind etwa Großevents oder schlechte Wetterbedingungen. [54]

I. Feature Store

Da komplexe Metriken wie ETA oder Preisindizes in Echtzeit die Latenz erhöhen würden, werden sie bereits im Vorfeld berechnet und in einem Feature Store gespeichert (siehe Schritt 7 in Abbildung 2). Für die kontinuierliche Vorberechnung wird die Stream-Processing-Engine Apache Flink eingesetzt, welche zustandsbehaftete Berechnungen über unbegrenzte Datenströme ermöglicht, d.h. Berechnungen, die auch Vergangenheitsdaten mit einbeziehen. [55] In diesem Fall fließen die Daten (Fahrer-Standorte) laufend in den Flink-Stream ein, werden auf Worker verteilt (z.B. nach H3-Zelle) und verarbeitet, und die Ergebnisse werden als State (Zwischenspeicher) beim Worker gespeichert. Die Live-Index States sind dabei Sliding Windows, die die Daten der letzten N Zeiteinheiten zusammenfassen, z.B. die durchschnittliche Durchfahrzeit einer H3-Zelle in den letzten 5 Minuten. Das Fenster kann in einem festen Intervall z.B. jede Minute aktualisiert, also nach vorne verschoben werden, wobei ein neues Aggregat mit glattem Übergang entsteht. Flink läuft also als Rechenmaschine permanent im Hintergrund, und wenn eine Nutzeranfrage am System eingeht, so können dahinterliegende Services sofort auf die hier berechneten Daten zugreifen.

J. Matching Service

Der Matching Service (siehe Schritt 8 in Abbildung 2) befasst sich mit den letzten beiden Schritten der Informations-Pipeline für die Buchungsübersicht: Dem Einstufen der relevanten Fahrer in eine Rangliste und dem Treffen einer Entscheidung eines Fahrers für den Kunden. Die Auswahlkriterien beinhalten hierbei neben Nutzer-Präferenzen eine minimale Wartezeit für den Kunden auf das Abholen und einen minimalen Bewegungsaufwand für den Fahrer. Uber verwendet jedoch nicht das “First-to-request”-Prinzip, bei dem einfach der Fahrer mit der kürzesten Fahrtdauer zum Kunden ausgewählt wird. Stattdessen wird sogenanntes “Batch Matching” verwendet, wobei mehrere Anfragen und Fahrer gesammelt werden und daraufhin die optimale Zuordnung über das gesamte Batch hinweg berechnet wird. Es wird also die Kombination gewählt, die die kollektive Wartezeit über alle Kunden und Fahrer hinweg minimiert. Dies zieht eine etwas längere Wartezeit bis zur Fahrerauswahl für den Einzelnen mit sich, senkt jedoch die durchschnittliche Wartezeit im gesamten System. [39]

K. Reservierung

In einem klassischen Request-Response-Modell fragt eine Partei nach Informationen, wenn diese benötigt werden. So fragt der Fahrer-Client den Server bspw. jede 5 Sekunden danach, ob ein neues Fahrerangebot vorliegt, oder der Kunden-Client fragt den Server jede 5 Sekunden danach, wo sich sein Fahrer befindet. Dies könnte einfach mithilfe einer REST-API umgesetzt werden, über die HTTP-Requests ausgetauscht werden. Im System von Uber führte dies dazu, dass 80% aller Requests von Clients an Backend-APIs aus Polling-Calls bestanden, also Fragen der Clients, ob sich etwas geändert hat. Dieses System wurde als zu ineffizient eingestuft.

Anstelle dessen implementierte Uber eine sog. push-basierte Plattform namens “RAMEN” (siehe Schritt 9 in Abbildung 2), die Polling eliminierte und bei der die Informationsquelle (z.B. der Redis-Server mit Standortdaten) in Intervallen eigenständig ihre Informationen an die Clients schickt, ohne dass diese explizit danach fragen müssen. Das System wurde zunächst auf Server-Sent Events (SSE) aufgebaut, später wechselte man jedoch auf gRPC. [56] Hierbei enthält jeder Client einen sog. “Stub”, welcher vom Server vordefinierte Methoden beinhaltet, auf welche der Server optimal reagieren kann, z.B. das Aktualisieren der Fahrerposition, womit der Server unmittelbar eine Timeline der letzten Fahrerpositionen erstellen kann. Die Gründe zur Entscheidung für gRPC waren die Möglichkeit, eine bidirektionale Verbindung zwischen Client und Server zu etablieren, sequenzierte Empfangsbestätigungen (ACKs) zu senden sowie die native Binär-Serialisierung über das Protobuf-Format. [57] [58]

Um die Datenmenge zu reduzieren und die Effizienz weiter zu steigern, könnte sog. “Adaptive Sampling” eingesetzt werden, wobei die Frequenz der Standort-Updates dynamisch an den Status des Fahrers angepasst wird. Ein sich schnell bewegender Fahrer sollte während eines Auftrages häufiger Updates senden als ein nicht-beschäftigter, stehender Fahrer. [59]

IV. CONCLUSION

Zunächst wurden die Anforderungen an die Destinationssuche aufgestellt und untersucht, wie sich diese technisch umsetzen lassen. Anschließend wurden OS, ES und Vespa hinsichtlich nicht-funktionaler Anforderungen wie Performance, Skalierung und geografischer Verteilung verglichen. OS ging als Gewinner hervor: Zu ES zeigte sich kaum ein Unterschied, OpenSearch ist jedoch quelloffen. Vespa bringt als weniger etabliertes, praxiserprobtes Tool ein gewisses Risiko mit sich. Die resultierende Architektur nutzt OpenSearch für Autovervollständigung und kontextabhängiges Ranking über das LTR-Plugin, orientiert sich für die geografische Verteilung an Ubers Active-Active-Ansatz über Kafka und wird von einem zentralen Search Service orchestriert. Damit erfüllt die Architektur sowohl die funktionalen als auch die nicht-funktionalen Anforderungen an die Destinationssuche.

Beim Rider-Driver-Matching bildet Kafka die zentrale Datenquelle für alle Standortdaten, mit der Möglichkeit, alte Daten erneut abzurufen. Redis sorgt, unterstützt durch den Sharding-Layer Ringpop, für schnelles Lesen und Schreiben der aktuellen Fahrerpositionen. H3 und ein auf einem Hidden-Markov-Modell basierendes Map Matching wandeln rohe GPS-Koordinaten in verlässliche, straßenkorrekte Standortdaten um. Durch Vorberechnung mit der Streaming-Engine Flink im Feature Store, etwa von Angebot/Nachfrage, ETA oder Preis-Multiplikator, wird die Antwortzeit bei einer Anfrage verringert, da die aufwändigen Berechnungen schon vorher gemacht wurden. Statt einfach den nächstgelegenen Fahrer zu wählen, sorgt Batch Matching dafür, dass die Wartezeit für alle Nutzer zusammen möglichst kurz bleibt. RAMEN ersetzt außerdem das ineffiziente Abfragen durch die Clients, indem der Server Angebote und Änderungen direkt an die Clients schickt.

Beide Teile folgen damit einer ähnlichen Idee: Daten werden früh vereinfacht oder vorberechnet, um bei der eigentlichen Anfrage Zeit zu sparen. Gleichzeitig sorgen verteilte Systeme wie Kafka und die OpenSearch-Cluster dafür, dass alles zuverlässig und weltweit verfügbar bleibt, auch wenn dafür auf strikte Echtzeit-Aktualität verzichtet wird.

[1] Statista Market Insights, “Ride-hailing – worldwide,”
https://www.statista.com/outlook/mmo/shared-mobility/ride-hailing/
worldwide/revenue, 2026, accessed 2026-07-30.
[2] C. D. Manning, P. Raghavan, and H. Schütze, Introduction to Informa-
tion Retrieval. Cambridge, UK: Cambridge University Press, 2008.
[3] Elastic, “What is full-text search? a guide to fts,” https://www.elastic.
co/what-is/full-text-search, 2024, accessed 2026-07-30.
[4] ——, “Anatomy of an analyzer,” https://www.elastic.co/docs/
manage-data/data-store/text-analysis/anatomy-of-an-analyzer, 2024,
accessed 2026-07-30.
[5] Google Cloud, “What is fuzzy search? fuzzy search meaning,” https://
cloud.google.com/discover/what-is-fuzzy-search, 2024, accessed 2026-
07-30.
[6] Elastic, “Search with synonyms,” https://www.elastic.co/docs/solutions/
search/full-text/search-with-synonyms, 2024, accessed 2026-07-30.
[7] ——, “Synonym token filter,” https://www.elastic.co/docs/reference/
text-analysis/analysis-synonym-tokenfilter, 2024, accessed 2026-07-30.
[8] IBM, “Document retrieval and ranking,” https://www.ibm.com/docs/en/
content-cortex/26.0.0?topic=domain-document-retrieval-ranking, 2024,
iBM Documentation, Content Cortex 26.0.0. Accessed 2026-07-30.
[9] Apache Software Foundation, “Apache lucene core,” https://lucene.
apache.org/core/, 2024, accessed 2026-07-30.
[10] S. Maheshwari, “The secret architecture behind lucene: A library
of immutable wings,” https://satyadeepmaheshwari.medium.com/
the-secret-architecture-behind-lucene-a-library-of-immutable-wings-21cf072e8015,
2024, medium. Accessed 2026-07-30.
[11] Elastic, “Near real-time search,” https://www.elastic.co/docs/
manage-data/data-store/near-real-time-search, 2024, accessed 2026-07-
30.
[12] M. McCandless, “Visualizing lucene’s segment merges,” https://blog.
mikemccandless.com/2011/02/visualizing-lucenes-segment-merges.
html, 2011, accessed 2026-07-30.
[13] M. Syed and E. Russi, “What is vector search?” https://www.ibm.com/
think/topics/vector-search, 2024, iBM. Accessed 2026-07-30.
[14] Amazon Web Services, “Learning to rank for amazon open-
search service,” https://docs.aws.amazon.com/opensearch-service/latest/
developerguide/learning-to-rank.html, 2024, amazon OpenSearch Ser-
vice Developer Guide. Accessed 2026-07-30.
[15] Google for Developers, “Geocoding api overview,” https://developers.
google.com/maps/documentation/geocoding/guides-v3/overview, 2024,
google Maps Platform. Accessed 2026-07-30.
[16] Elastic, “Elasticsearch autocomplete: search as you type,
query time and more,” https://www.elastic.co/search-labs/blog/
elasticsearch-autocomplete-search, 2024, elasticsearch Labs. Accessed
2026-07-30.
[17] Google for Developers, “About the places api (new),” https://developers.
google.com/maps/documentation/places/web-service/op-overview,
2024, google Maps Platform. Accessed 2026-07-30.
[18] Dremio, “Apache lucene,” https://www.dremio.com/wiki/
apache-lucene/, 2024, dremio Wiki. Accessed 2026-07-30.
[19] C. Yun, “Announcing amazon opensearch service which
supports opensearch 1.0,” https://aws.amazon.com/blogs/aws/
announcing-amazon-opensearch-service-which-supports-opensearch-10/,
2021, aWS News Blog, Sep. 8, 2021. Accessed 2026-07-30.
[20] Vespa.ai, “Use cases,” https://vespa.ai/use-cases/, 2024, accessed 2026-
07-30.
[21] E. Downing, R. Schirone, F. Bertolaccini, and R. Eytchison,
“Opensearch benchmark assessment,” https://github.com/trailofbits/
publications/blob/master/reports/OpenSearch-Benchmarking.pdf, 2024,
trail of Bits, Aug. 2024. Accessed 2026-07-30.
[22] G. Storli, J. K. Bergum, and R. Gheorghe, “Elasticsearch
vs vespa performance comparison,” https://blog.vespa.ai/
elasticsearch-vs-vespa-performance-comparison/, 2024, vespa Blog,
Nov. 6, 2024. Accessed 2026-07-30.
[23] Vespa.ai, “Proton,” https://docs.vespa.ai/en/content/proton.html, 2024,
vespa Documentation. Accessed 2026-07-30.
[24] Elastic, “General index settings,” https://www.elastic.co/docs/reference/
elasticsearch/index-settings/index-modules, 2024, elasticsearch Refe-
rence. Accessed 2026-07-30.
[25] OpenSearch Project, “Index settings,” https://docs.opensearch.org/latest/
install-and-configure/configuring-opensearch/index-settings/, 2024,
openSearch Documentation. Accessed 2026-07-30.
[26] Elastic, “How to increase primary shard count in
elasticsearch,” https://www.elastic.co/search-labs/blog/
elasticsearch-increase-primary-shard-count, 2024, elasticsearch Labs.
Accessed 2026-07-30.
[27] Vespa.ai, “Content cluster elasticity,” https://docs.vespa.ai/en/content/
elasticity.html, 2024, vespa Documentation. Accessed 2026-07-30.
[28] Elastic, “Reading and writing documents,” https://www.elastic.co/
guide/en/elasticsearch/reference/8.19/docs-replication.html, 2024, ela-
sticsearch Guide [8.19]. Accessed 2026-07-30.
[29] Vespa.ai, “Consistency model,” https://docs.vespa.ai/en/content/
consistency.html, 2024, vespa Documentation. Accessed 2026-07-30.
[30] OpenSearch Project, “Cross-cluster replication,” https://docs.
opensearch.org/latest/tuning-your-cluster/replication-plugin/index/,
2024, openSearch Documentation. Accessed 2026-07-30.
[31] Elastic, “Cross-cluster replication,” https://www.elastic.co/docs/
deploy-manage/tools/cross-cluster-replication, 2024, elastic Docs.
Accessed 2026-07-30.
[32] ——, “Learning to rank (ltr),” https://www.elastic.co/docs/solutions/
search/ranking/learning-to-rank-ltr, 2024, elastic Docs. Accessed 2026-
07-30.
[33] OpenSearch Project, “Learning to rank,” https://docs.opensearch.org/
latest/search-plugins/ltr/index/, 2024, openSearch Documentation. Ac-
cessed 2026-07-30.
[34] Vespa.ai, “Ranking introduction,” https://docs.vespa.ai/en/ranking/
ranking-intro.html, 2024, vespa Documentation. Accessed 2026-07-30.
[35] OpenSearch Project, “Autocomplete functionality,” https://docs.
opensearch.org/latest/search-plugins/searching-data/autocomplete/,
2024, openSearch Documentation. Accessed 2026-07-30.
[36] Vespa.ai, “Text matching,” https://docs.vespa.ai/en/text-matching.html,
2024, vespa Documentation. Accessed 2026-07-30.
[37] Uber Technologies, Inc., “The evolution of uber’s search platform,”
https://www.uber.com/eg/en/blog/evolution-of-ubers-search-platform/,
2025, accessed 2026-07-27.
[38] Y. Fu, X. Xiong, and M. Froh, “How uber indexes streaming data with
pull-based ingestion in opensearch,” https://www.uber.com/us/en/blog/
how-uber-indexes-streaming-data-with-pull-based-ingestion-in-opensearch/,
2025, uber Blog, Dec. 16, 2025. Accessed 2026-07-30.
[39] Uber Technologies, Inc., “Understanding uber’s marketplace mat-
ching,” https://www.uber.com/de/en/marketplace/matching/, 2024, ac-
cessed 2026-07-23.
[40] J. Nielsen, “Response time limits: Article by jakob nielsen,” https://
www.nngroup.com/articles/response-times-3-important-limits/, Nielsen
Norman Group, 1993, nielsen Norman Group. Accessed 2026-07-28.
[41] R. Braden, “RFC 1379: Extending tcp for transactions – concepts,” https:
//www.rfc-editor.org/rfc/rfc1379.html, 1992, iETF. Accessed 2026-07-
28.
[42] OpenJS Foundation, “Backpressuring in streams,” https://nodejs.org/
learn/modules/backpressuring-in-streams, 2024, node.js Documentation.
Accessed 2026-07-28.
[43] Broadcom, Inc. (RabbitMQ), “Consumer acknowledgements and pu-
blisher confirms,” https://www.rabbitmq.com/docs/confirms, 2024, rab-
bitMQ Documentation. Accessed 2026-07-28.
[44] ——, “Consumers,” https://www.rabbitmq.com/docs/consumers, 2024,
rabbitMQ Documentation. Accessed 2026-07-29.
[45] Apache Software Foundation, “Design,” https://kafka.apache.org/42/
design/design/, 2024, apache Kafka Documentation. Accessed 2026-07-
29.
[46] Uber Technologies, Inc., “H3: Uber’s hexagonal hierarchical spatial
index,” https://www.uber.com/us/en/blog/h3/, 2024, accessed 2026-07-
23.
[47] P. Newson and J. Krumm, “Hidden markov map matching through noise
and sparseness,” in Proceedings of the 17th ACM SIGSPATIAL Interna-
tional Conference on Advances in Geographic Information Systems (GIS
’09), 2009.
[48] Uber Technologies, Inc., “Improving mapping accuracy with catchme,”
https://www.uber.com/us/en/blog/mapping-accuracy-with-catchme/,
2024, accessed 2026-07-23.
[49] Redis Ltd., “Redis,” https://redis.io/, 2024, accessed 2026-07-23.
[50] D. Kumar, “Ringpop: A scalable and fault-tolerant application-
layer sharding strategy,” https://dilipkumar.medium.com/
ringpop-a-scalable-and-fault-tolerant-application-layer-sharding-strategy-7910ab39b9c 2023, accessed 2026-07-23.
[51] Uber Technologies, Inc., “Ringpop: Open-source node.js libra-
ry for application-layer sharding,” https://www.uber.com/us/en/blog/
ringpop-open-source-nodejs-library/, 2024, accessed 2026-07-23.
[52] ——, “Deepeta: How uber predicts arrival times,” https://www.uber.
com/us/en/blog/deepeta-how-uber-predicts-arrival-times/, 2024, acces-
sed 2026-07-23.
[53] ——, “Uber marketplace: Surge pricing,” https://www.uber.com/us/en/
marketplace/pricing/surge-pricing/, 2024, accessed 2026-07-31.
[54] ——, “How surge pricing works,” https://www.uber.com/us/en/drive/
driver-app/how-surge-works/, 2024, accessed 2026-07-31.
[55] Apache Software Foundation, “Flink architecture,” https://flink.apache.
org/what-is-flink/flink-architecture/, 2024, apache Flink Documentation.
Accessed 2026-07-31.
[56] Uber Technologies, Inc., “Ramen: Uber’s real-time push delivery plat-
form,” https://www.uber.com/in/en/blog/real-time-push-platform/, 2024,
accessed 2026-07-23.
[57] The gRPC Authors, “Introduction to grpc,” https://grpc.io/docs/
what-is-grpc/introduction/, 2024, accessed 2026-07-28.
[58] ——, “Flow control,” https://grpc.io/docs/guides/flow-control/, 2024,
accessed 2026-07-28.
[59] M. Banger, “Architecting an uber-scale real-time
tracking & dispatch system,” https://dev.to/madhur_banger/
architecting-an-uber-scale-real-time-tracking-dispatch-system-3a72,
2023, accessed 2026-07-23.