I. EINLEITUNG<\/strong> <\/h3>\n\n\n\nAls digitale Weiterentwicklung des klassischen Taxigewerbes haben sich in den letzten Jahren Ride-Hailing-Plattformen etabliert, die Fahrten zwischen Fahrg\u00e4sten und Fahrern vermitteln. Die Zahl der Nutzer solcher Plattformen soll bis 2030 weltweit auf \u00fcber 2,3 Milliarden steigen [1]. Die vorliegende Arbeit betrachtet die Suchfunktionalit\u00e4t 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\u00fcnschte Fahrtziel \u00fcber eine Texteingabe zu finden, was Herausforderungen hinsichtlich relevanter und performanter Suchergebnisse mit sich bringt. Beim Rider-Driver-Matching muss aus einer Menge verf\u00fcgbarer Fahrer derjenige ermittelt werden, der f\u00fcr die Fahrt am besten geeignet ist, was Herausforderungen hinsichtlich r\u00e4umlicher N\u00e4he sowie weiterer Faktoren wie Wartezeit oder Auslastung mit sich bringt. <\/p>\n\n\n\n
F\u00fcr beide Suchprobleme werden in dieser Arbeit m\u00f6gliche technische Umsetzungen erarbeitet. Als Referenz dienen dabei bestehende Plattformen, insbesondere Uber, dessen Suchinfrastruktur sich \u00fcber die Jahre mehrfach gewandelt hat und damit R\u00fcckschl\u00fcsse auf praxistaugliche L\u00f6sungsans\u00e4tze zul\u00e4sst. Dabei wird von einem gro\u00dfen, geografisch verteilten System ausgegangen, wie es f\u00fcr den globalen Betrieb einer Ride-Hailing-Plattform notwendig ist. Ziel ist es, f\u00fcr beide Suchprobleme eine geeignete Architektur zu konzipieren, die den Anforderungen einer solchen Plattform gerecht wird. Im Folgenden werden zun\u00e4chst die f\u00fcr die Destinationssuche relevanten Konzepte und Technologien vorgestellt. Darauf aufbauend werden konkrete Tools analysiert und abschlie\u00dfend zu einer m\u00f6glichen Architektur zusammengef\u00fchrt. Anschlie\u00dfend wird auf das Rider-Driver-Matching eingegangen. Auch hier werden zun\u00e4chst die ben\u00f6tigten Komponenten betrachtet, bevor daraus eine resultierende Architektur abgeleitet wird.<\/p>\n\n\n\n
II. DESTINATIONSSUCHE<\/strong><\/h3>\n\n\n\nA. Anforderungen an die Destinationssuche<\/p>\n\n\n\n
Im Detail hat die Destinationssuche einer Ride-Hailing-Plattform die Aufgabe, aus der textuellen Eingabe des Kunden die gew\u00fcnschten Abhol- und Zielstandorte zu bestimmen. Bereits w\u00e4hrend der Eingabe sollen dem Kunden passende Vorschl\u00e4ge angezeigt werden, sodass im Idealfall schon wenige eingegebene Buchstaben gen\u00fcgen, um den gew\u00fcnschten Standort zu finden. Die final ausgew\u00e4hlten Standorte legen dabei nicht nur fest, von wo nach wo die Fahrt gehen soll, sondern bilden auch die Grundlage f\u00fcr das nachgelagerte Rider-Driver-Matching. Aus diesem Szenario lassen sich zusammen mit der Voraussetzung eines gro\u00dfen und geografisch verteilten Systems die folgenden Anforderungen ableiten. <\/p>\n\n\n\n
Funktionale Anforderungen<\/strong><\/p>\n\n\n\n\n- Eingabetoleranz: Die Suche muss tolerant gegen\u00fcber Tippfehlern, Abk\u00fcrzungen und Synonymen sein.<\/li>\n\n\n\n
- Suchvorschl\u00e4ge: Die Suche muss bereits w\u00e4hrend der Eingabe passende Vorschl\u00e4ge liefern.<\/li>\n\n\n\n
- Relevanz: Die Suchvorschl\u00e4ge\/-ergebnisse m\u00fcssen m\u00f6glichst relevant sein. Dabei muss sowohl die textuelle \u00dcbereinstimmung als auch Kontextfaktoren wie geografische N\u00e4he oder Nutzerdaten ber\u00fccksichtigt werden.<\/li>\n\n\n\n
- Vorausbuchungen: Da Vorausbuchungen m\u00f6glich sein m\u00fcssen, d\u00fcrfen die Ergebnisse nicht ausschlie\u00dflich auf nahe Standorte begrenzt sein.<\/li>\n<\/ul>\n\n\n\n
Nicht funktionale Anforderungen<\/strong><\/p>\n\n\n\n\n- Performance: Suchanfragen m\u00fcssen mit niedriger Latenz beantwortet werden, um Suchvorschl\u00e4ge ohne sp\u00fcrbare Verz\u00f6gerung zu liefern.<\/li>\n\n\n\n
- Aktualit\u00e4t: Standortdaten \u00e4ndern sich selten, sollten aber \u00e4nderbar sein. \u00c4nderungen m\u00fcssen nicht sofort, sondern innerhalb kurzer Zeit sichtbar werden.<\/li>\n\n\n\n
- Geografische Verteilung: Die Suche muss global verteilt nutzbar sein, sodass Nutzer unabh\u00e4ngig von ihrem Standort mit geringer Latenz suchen k\u00f6nnen.<\/li>\n\n\n\n
- Verf\u00fcgbarkeit: Die Suche muss hochverf\u00fcgbar sein, da die Funktionalit\u00e4t der Plattform auf die Destinationssuche angewiesen ist.<\/li>\n\n\n\n
- Skalierbarkeit: Das System muss skalierbar sein, um bei Bedarf auf wachsendes Anfragevolumen angepasst werden zu k\u00f6nnen.<\/li>\n\n\n\n
- Betreibbarkeit: Das System soll sich auf ein aktives \u00d6kosystem mit guter Dokumentation und Community-Support st\u00fctzen k\u00f6nnen, um den langfristigen Betrieb zu erleichtern.<\/li>\n<\/ul>\n\n\n\n
B. Grundlegende Suchkonzepte und -technologien<\/p>\n\n\n\n
Bei einer geringen Anzahl an Dokumenten kann eine Suche direkt und sequenziell \u00fcber den gesamten Datenbestand erfolgen. F\u00fcr kleinere Dokumentenmengen ist das mit der heutigen Rechenleistung durchaus praktikabel. Mit zunehmender Gr\u00f6\u00dfe wird dieser Ansatz jedoch ineffizient, da f\u00fcr jede Suchanfrage alle Dokumente durchsucht werden m\u00fcssen und die Suchzeit dadurch linear mit der Anzahl der Dokumente w\u00e4chst. Au\u00dferdem 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.<\/p>\n\n\n\n
Lexikalische Suche \u00fcber invertierte Indizes<\/strong> <\/p>\n\n\n\nEine 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\u00fcr 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\u00fchrt. Das Ergebnis enth\u00e4lt dann alle Dokumente, die diesen Term enthalten. Die Suchgeschwindigkeit bleibt dabei auch bei gro\u00dfen Datenmengen weitgehend erhalten [3]. <\/p>\n\n\n\n
Die beschriebene Funktionalit\u00e4t des invertierten Index erm\u00f6glicht so in der einfachsten Form zun\u00e4chst nur exakte Keyword-Treffer. Bei Schreibfehlern oder alternativen Begriffen f\u00fchrt diese Suche zu keinen Treffern. Wie in den Anforderungen definiert wurde, muss die Suche jedoch weitestgehend dagegen tolerant sein. Verschiedene Vor-Verarbeitungsschritte m\u00fcssen daher zus\u00e4tzlich eingesetzt werden, um dies zu erf\u00fcllen. <\/p>\n\n\n\n
Sowohl beim Erstellen des Indexes als auch bei der Suchanfrage werden die Texte zun\u00e4chst mit einem Tokenizer in einzelne Tokens zerlegt. Diese Tokens sind meist einzelne W\u00f6rter [3]. Diese Tokens werden dann gewisserma\u00dfen normalisiert, indem sie in Kleinschreibung umgewandelt werden und Sonderzeichen aufgel\u00f6st werden [3] [4]. Um auch Suchergebnisse zu erhalten trotz Tippfehlern oder leicht abweichender Schreibweisen, lassen sich Fuzzy-Search-Algorithmen einsetzen. Diese erkennen \u00c4hnlichkeiten zwischen Suchbegriffen und den indexierten Termen, beispielsweise durch die Berechnung der Levenshtein-Distanz. Dabei wird die minimale Anzahl an Einf\u00fcgungen, L\u00f6schungen oder Ersetzungen bestimmt, die n\u00f6tig sind, um eine Zeichenkette in eine andere umzuwandeln [5]. F\u00fcr synonyme Begriffe k\u00f6nnen Synonym-Filter eingesetzt werden, die bedeutungsgleiche Worte zu dem eingegebenen Suchbegriff in den Such-Stream hinzuf\u00fcgen oder den initialen Suchbegriff ersetzen [6]. Dazu muss eine Synonymliste erstellt werden, hierf\u00fcr lassen sich bereits existierende Listen wie beispielsweise WordNet verwenden, die dann gegebenenfalls erweitert werden k\u00f6nnen [7]. Diese Mechanismen erweitern den Suchraum \u00fcber exakte Treffer hinaus und erf\u00fcllen dabei die zuvor beschriebene Anforderung hinsichtlich Toleranz gegen\u00fcber Tippfehlern, Abk\u00fcrzungen und Synonymen. <\/p>\n\n\n\n
Nachdem die Vor-Verarbeitungsschritte und die Suche selbst durchgef\u00fchrt wurden, lassen sich die zur\u00fcckgelieferten Ergebnisse auf textueller Ebene noch nach ihrer Relevanz sortieren. Ein Beispiel hierf\u00fcr ist BM25, das f\u00fcr jedes Dokument einen Relevanz-Score in Bezug auf die Suchanfrage berechnet. Dieser Score basiert auf drei Faktoren: der Termh\u00e4ufigkeit (wie oft ein Suchbegriff im Dokument vorkommt), der inversen Dokumenth\u00e4ufigkeit (seltene Begriffe gelten als aussagekr\u00e4ftiger als h\u00e4ufig vorkommende) sowie einer Normalisierung bez\u00fcglich der Dokumentl\u00e4nge, damit l\u00e4ngere Dokumente nicht allein aufgrund ihrer L\u00e4nge bevorzugt werden [8]. Damit bildet BM25 eine m\u00f6gliche textuelle Grundlage f\u00fcr Relevanz von Suchergebnissen. <\/p>\n\n\n\n
Der invertierte Index sowie die beschriebenen Vor-Verarbeitungsschritte und das textuelle Ranking m\u00fcssen nicht von Grund auf selbst implementiert werden. Stattdessen l\u00e4sst sich Apache Lucene verwenden, das praktisch als Industriestandard daf\u00fcr gilt [9]. F\u00fcr 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\u00e4ndert werden. Dies erm\u00f6glicht, dass mehrere Threads gleichzeitig lesen k\u00f6nnen, ohne dass Locking erforderlich ist. Damit trotzdem neue Dokumente aufgenommen werden k\u00f6nnen, l\u00f6st Lucene dies \u00fcber sogenannte Segmente. F\u00fcr neue Dokumente wird dann jeweils ein eigenes Segment angelegt, das selbst wieder ein invertierter Index ist. Alle Segmente zusammen ergeben den vollst\u00e4ndigen Index [10]. Ein neues Dokument gelangt dabei zun\u00e4chst in einen In-Memory-Buffer, wird anschlie\u00dfend \u00fcber einen Refresh als durchsuchbares Segment im Filesystem-Cache verf\u00fcgbar gemacht und schlie\u00dflich \u00fcber einen Flush persistent auf die Disk geschrieben [11]. Mit der Zeit entstehen durch dieses Verfahren viele kleine Segmente sowie eventuell einige f\u00fcr die L\u00f6schung markierte Eintr\u00e4ge. Deshalb f\u00fchrt Lucene periodisch ein Merging durch. Dabei werden zum einen die f\u00fcr die L\u00f6schung markierten Dokumente endg\u00fcltig entfernt, wodurch Speicher freigegeben wird. Zum anderen werden viele kleine Segmente, die sonst zu schlechterer Suchperformance f\u00fchren k\u00f6nnen, zu wenigen, m\u00f6glichst gleich gro\u00dfen Segmenten zusammengef\u00fchrt [12].<\/p>\n\n\n\n
Semantische Suche<\/strong> <\/p>\n\n\n\nDie lexikalische Suche ermittelt Ergebnisse auf der textuellen Ebene. Durch die zuvor genannten zus\u00e4tzlichen Methoden l\u00e4sst sich diese um Tippfehler-Toleranz sowie zus\u00e4tzliches Suchen nach Synonymen erweitern, statt nur Terme exakt zu vergleichen. Die semantische Suche hingegen ermittelt bedeutungsnahe Ergebnisse zu der Suchanfrage. Dabei werden W\u00f6rter oder ganze Dokumente in numerische Vektoren umgewandelt, welche die Bedeutung der Inhalte abbilden. Inhalte mit \u00e4hnlicher Bedeutung liegen im Vektorraum n\u00e4her beieinander und k\u00f6nnen dadurch gefunden werden, auch wenn unterschiedliche Begriffe verwendet werden [13]. <\/p>\n\n\n\n
F\u00fcr die Suche wird der Vektorraum nach Vektoren durchsucht, die r\u00e4umlich nahe dem Vektor liegen, der die Suchanfrage repr\u00e4sentiert. Die exakte Suche nach den n\u00e4chsten Vektoren wird bei gro\u00dfen Datenmengen jedoch ineffizient, da die \u00c4hnlichkeit mit allen gespeicherten Vektoren berechnet werden m\u00fcsste. Deshalb kommen f\u00fcr die Suche Approximate-Nearest-Neighbor-Verfahren wie HNSW (Hierarchical Navigable Small World) zum Einsatz. Diese suchen nicht nach einer exakten, sondern nach einer m\u00f6glichst guten Ann\u00e4herung der n\u00e4chsten Vektoren, wodurch sich der Berechnungsaufwand deutlich reduzieren l\u00e4sst [13]. F\u00fcr 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\u00fcr den Anwendungsfall demnach besser geeignet. <\/p>\n\n\n\n
Erg\u00e4nzende Bausteine der Suche<\/strong> <\/p>\n\n\n\nEin weiterer wichtiger Faktor f\u00fcr die Bestimmung der Relevanz von Ergebnissen sind Kontextfaktoren wie geographische N\u00e4he, Nutzerdaten oder auch die Uhrzeit. Hierf\u00fcr l\u00e4sst sich ein Machine Learning Modell einsetzen, das Suchergebnisse anhand dieser zus\u00e4tzlichen Faktoren bewertet und darauf basierend sortiert. Beispielsweise kann ein Learning-to-Rank-Modell verwendet werden, das mithilfe von Machine-Learning-Verfahren verschiedene Merkmale ber\u00fccksichtigt, um die erwartete Relevanz von Suchergebnissen zu bestimmen und diese entsprechend zu ordnen [14]. <\/p>\n\n\n\n
F\u00fcr Standorte, f\u00fcr die keine zugeh\u00f6rigen Koordinaten vorliegen, kann Geocoding verwendet werden, um aus der Adresse in Textform geografische Koordinaten zu ermitteln. Hierf\u00fcr gibt es verschiedene APIs, wie beispielsweise die Google Geocoding API [15]. <\/p>\n\n\n\n
F\u00fcr die technische Umsetzung einer Autovervollst\u00e4ndigung k\u00f6nnen verschiedene Ans\u00e4tze eingesetzt werden. Ein Ansatz besteht darin, die m\u00f6glichen Vervollst\u00e4ndigungen separat in einer eigenen Datenstruktur zu indexieren. Optional l\u00e4sst sich dabei eine Relevanz vergeben, beispielsweise basierend darauf, wie h\u00e4ufig ein Begriff gesucht wird. Bei einer Eingabe werden die passendsten Vervollst\u00e4ndigungen direkt aus dieser Datenstruktur zur\u00fcckgegeben, ohne dass dabei auf den regul\u00e4ren invertierten Index zugegriffen wird. Ein weiterer Ansatz ist die Indexierung von Wortpr\u00e4fixen. Hierbei werden bereits beim Indexieren Wortpr\u00e4fixe als eigene Tokens im regul\u00e4ren invertierten Index abgelegt, sodass die Autovervollst\u00e4ndigung direkt dar\u00fcber l\u00e4uft [16]. <\/p>\n\n\n\n
F\u00fcr die Standortdaten selbst wird eine Datenquelle ben\u00f6tigt, aus der Orte mit ihren zugeh\u00f6rigen Informationen wie Namen, Adressen und Koordinaten stammen. Hierf\u00fcr k\u00f6nnen externe Provider genutzt werden, die eine Datenbank mit Orten sowie eine Schnittstelle zur Abfrage dieser Orte bereitstellen. Ein Beispiel hierf\u00fcr ist die Places API von Google [17].<\/p>\n\n\n\n
C. Verteilte Suchtechnologien<\/p>\n\n\n\n
Die zuvor beschriebenen Suchtechnologien liefern bereits die Grundlagen daf\u00fcr, die funktionalen Anforderungen zu erf\u00fcllen. Bez\u00fcglich der nicht-funktionalen Anforderungen, besonders Skalierung und geografischer Verteilung, zeigen die beschriebenen Technologien noch keine m\u00f6gliche Umsetzung. Apache Lucene selbst bietet keine M\u00f6glichkeit die Suche verteilt zu betreiben. Die Verteilung von Daten \u00fcber mehrere Knoten hinweg sowie deren Koordination ist damit nicht Teil von Lucene selbst und m\u00fcsste manuell drumherum implementiert werden [18]. <\/p>\n\n\n\n
Im Folgenden werden daher Suchtechnologien untersucht, die diese Funktionalit\u00e4ten bereits mitbringen, sodass sie nicht von Grund auf selbst implementiert werden m\u00fcssen. Daf\u00fcr 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\u00fchrt [19]. Erg\u00e4nzend wurde Vespa hinzugezogen, das f\u00fcr seine F\u00e4higkeiten in der semantischen Suche bekannt ist, aber auch lexikalische Suche unterst\u00fctzt [20]. Der Vergleich betrachtet dazu Query-Speed, Datenaktualit\u00e4t, Skalierung, Replikation, geografische Distribution, Ranking mit Kontextfaktoren, Autovervollst\u00e4ndigung sowie das jeweilige \u00d6kosystem.<\/p>\n\n\n\n
Query Speed<\/strong> F\u00fcr 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\u00fchrt hat [21]. Bei der f\u00fcr die Destinationssuche relevantesten Operation, einfachen Term-Abfragen, zeigt sich praktisch kein Unterschied zwischen beiden Systemen. F\u00fcr Vespa existieren ausschlie\u00dflich herstellereigene Benchmark-Daten, die einen deutlichen Geschwindigkeitsvorteil zu ES bei lexikalischer Suche aufzeigen [22]. Diese Zahlen sind jedoch nicht unabh\u00e4ngig verifiziert und daher mit Vorsicht zu betrachten. <\/p>\n\n\n\nDatenaktualit\u00e4t<\/strong> Da sowohl ES als auch OS auf Apache Lucene aufbauen, ist die Datenaktualit\u00e4t durch das Refresh-Intervall von Lucene begrenzt. Demnach ist Near-Real-Time die maximal erreichbare Aktualit\u00e4t [11]. Auch bei Vespa werden Dokumente nicht sofort, sondern erst nach einem periodischen Flush durchsuchbar, \u00e4hnlich wie bei Lucene, auch wenn Vespa nicht auf Lucene basiert [23]. <\/p>\n\n\n\nSkalierung<\/strong> Bei der Skalierung folgen ES und OS demselben Prinzip: Beide setzen auf statisches Sharding, das hei\u00dft, die Anzahl der Shards wird bereits beim Erstellen des Index festgelegt [24] [25]. M\u00fcssen weitere Shards hinzuf\u00fcgt werden, muss der Index neu erstellt werden, da die Anzahl der Shards f\u00fcr einen existierenden Index nicht mehr angepasst werden k\u00f6nnen [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 \u00fcber die konkrete Datenverteilung einher. <\/p>\n\n\n\nReplikation<\/strong> ES und OS folgen dem Prinzip der Active-Passive-Replikation: \u00c4nderungen werden zun\u00e4chst auf einem Prim\u00e4rshard angewendet und dann an die Replicas verteilt [28]. Vespa schreibt stattdessen synchron auf alle verf\u00fcgbaren Replicas parallel und wartet auf deren Best\u00e4tigung, ohne festen Prim\u00e4rknoten [29]. <\/p>\n\n\n\nGeografische Distribution<\/strong> ES und OS bieten mit Cross-Cluster Replication (CCR) ein dediziertes Feature f\u00fcr den Betrieb \u00fcber mehrere Rechenzentren hinweg. Mehrere unabh\u00e4ngige Cluster werden dabei nach dem Active-Passive-Prinzip \u00fcber Regionen hinweg repliziert [30] [31]. Bei Vespa gibt es kein \u00c4quivalent zu CCR. Knoten m\u00fcssten stattdessen innerhalb einer einzigen, zusammenh\u00e4ngenden Einheit geografisch verteilt werden [29]. <\/p>\n\n\n\nRanking mit Kontextfaktoren<\/strong> Bei ES und OS kann Learning to Rank \u00fcber 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\u00e4tzliches Plugin [34]. <\/p>\n\n\n\nAutovervollst\u00e4ndigung<\/strong> ES und OS unterst\u00fctzen beide zuvor beschriebenen Ans\u00e4tze. Zum einen das Plugin Completion Suggester, das Vervollst\u00e4ndigungen in einer eigenen, separaten Datenstruktur indexiert. Zum anderen die Option, Wortpr\u00e4fixe direkt im regul\u00e4ren invertierten Index abzulegen und somit auf die normale Suchinfrastruktur zur\u00fcckzugreifen [16] [35]. Vespa bietet daf\u00fcr keine fertige L\u00f6sung, eine Pr\u00e4fixsuche m\u00fcsste selbst umgesetzt werden [36]. <\/p>\n\n\n\n\u00d6kosystem<\/strong> ES und OS verf\u00fcgen beide \u00fcber eine gro\u00dfe Community und ein breites Angebot an Zusatzwerkzeugen. OpenSearch ist dazu vollst\u00e4ndig quelloffen. Vespa hat demgegen\u00fcber eine deutlich kleinere Community und gilt als weniger etabliert. Hinsichtlich verf\u00fcgbarer Ressourcen sind ES und OS damit im Vorteil.<\/p>\n\n\n\nD. Praxisbeispiel: Uber<\/p>\n\n\n\n
Ein Blick auf Uber als gro\u00dfe Ride-Hailing-Plattform lohnt sich, da sich deren Suchinfrastruktur \u00fcber die Jahre mehrfach gewandelt und weiterentwickelt hat. Uber setzte vor 2019 auf Elasticsearch, stellte jedoch fest, dass die Near-Real-Time-Aktualit\u00e4t f\u00fcr bestimmte Anwendungsf\u00e4lle nicht ausreichte [37]. F\u00fcr die Destinationssuche selbst erscheint das zun\u00e4chst weniger naheliegend, da sich Standortdaten selten \u00e4ndern und nicht unbedingt Echtzeit aktuell sein m\u00fcssen. Es d\u00fcrfte sich also eher um einen anderen Bereich von Uber gehandelt haben, der auch Teil derselben Suchinfrastruktur ist. <\/p>\n\n\n\n
Als Reaktion entwickelte Uber mit SIA (2019 bis 2024) eine eigene, auf Apache Lucene basierende L\u00f6sung mit Echtzeit-F\u00e4higkeiten. 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\u00f6chentlich zusammengef\u00fchrt werden. Erg\u00e4nzend f\u00fchrte Uber gRPC statt REST f\u00fcr effizientere Service-Kommunikation ein und stellte auf eine Kafka-basierte Pull-Ingestion um, wodurch Backpressure-Handling erm\u00f6glicht wird. Zus\u00e4tzlich implementierte Uber Active-Active-Cross-Cluster-Replikation statt der zuvor \u00fcblichen Active-Passive-Variante [37]. Bei Active-Active k\u00f6nnen, im Unterschied zum Leader-Follower-Prinzip von OS und ES, bei dem nur der Leader-Cluster Schreibvorg\u00e4nge annimmt, alle Regionen \u00c4nderungen annehmen. Eine \u00c4nderung wird dabei zun\u00e4chst in das lokale Kafka der jeweiligen Region geschrieben, das sie anschlie\u00dfend an die Kafka-Instanzen aller anderen Regionen verteilt, wo sie wiederum von den dortigen Suchclustern konsumiert wird [38]. <\/p>\n\n\n\n
SIA erwies sich jedoch langfristig als problematisch. Die Eigenentwicklung war wartungsintensiv, und neue Lucene-Features lie\u00dfen sich nur schwer integrieren. Zudem zeigte sich, dass die meisten tats\u00e4chlichen Anwendungsf\u00e4lle gar kein Echtzeit-Indexing ben\u00f6tigten und mit Near-Real-Time-Aktualit\u00e4t 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\u00fcr den Umstieg auf OpenSearch, unter anderem auch, um direkt an dessen Weiterentwicklung mitzuwirken. Bew\u00e4hrte Konzepte aus SIA wie die gRPC-Kommunikation und die Pull-based-Ingestion wurden dabei zu OpenSearch \u00fcbernommen [37]. <\/p>\n\n\n\n
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\u00fcr OS statt ES entschieden, um dort eigene Erkenntnisse einzubringen [37].<\/p>\n\n\n\n
E. Technologiewahl<\/p>\n\n\n\n
Basierend auf der vorangegangenen Betrachtung der Tools sowie dem Praxisbeispiel Uber f\u00e4llt die Wahl auf OpenSearch. Zwischen ES und OS selbst gibt es kaum Unterschiede: Bei Query-Speed f\u00fcr einfache Term-Abfragen, dem f\u00fcr die Destinationssuche relevantesten Fall, zeigt sich praktisch kein Unterschied. Auch bei Datenaktualit\u00e4t, Skalierung und Replikation folgen beide demselben architektonischen Prinzip, da OS urspr\u00fcnglich ein Fork von ES ist. Den Ausschlag gibt daher das Lizenzmodell: OpenSearch steht vollst\u00e4ndig unter der offenen Apache License 2.0, w\u00e4hrend neuere Elasticsearch-Versionen unter der restriktiveren Elastic License stehen, ein Aspekt, den auch Uber als Grund f\u00fcr die Wahl von OpenSearch statt Elasticsearch anf\u00fchrt. 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\u00dfen Systemen im praktischen Einsatz bewiesen haben, dass sie zuverl\u00e4ssig funktionieren. Zudem hat Vespa eine deutlich kleinere Community und bietet hinsichtlich Query-Speed und Datenaktualit\u00e4t keinen belegten Vorteil gegen\u00fcber OpenSearch.<\/p>\n\n\n\n
F. Architektur<\/p>\n\n\n\n
F\u00fcr eine konkrete m\u00f6gliche Umsetzung besteht die Architektur aus f\u00fcnf zentralen Komponenten: dem Search Service als zentrale orchestrierende Komponente, dem OpenSearch-Cluster f\u00fcr 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\u00f6nnen.<\/p>\n\n\n\n
F\u00fcr 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 \u00c4nderungen an bestehenden Standorten. Diese \u00c4nderungen k\u00f6nnen dabei in jeder Region eingetragen werden und gelangen zun\u00e4chst 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 \u00fcblichen OpenSearch-Leader-Follower-Prinzip nur in einer prim\u00e4ren Region. Jedes regionale OpenSearch-Cluster konsumiert die \u00c4nderungen anschlie\u00dfend \u00fcber die Pull-based-Funktionalit\u00e4t. Innerhalb des OpenSearch-Clusters kommen mehrere Komponenten zum Einsatz. F\u00fcr die Autovervollst\u00e4ndigung werden zwei Ans\u00e4tze kombiniert eingesetzt. Der Completion Suggester speichert h\u00e4ufig gesuchte Ergebnisse zu den entsprechenden Pr\u00e4fixen in einer eigenen, schnellen In-Memory-Datenstruktur. \u00dcber die Geo-Context-Funktion wird dabei auch der geografische Bereich der Eintr\u00e4ge gespeichert, wodurch sich schnell popul\u00e4re Ergebnisse aus der N\u00e4he abfragen lassen. Ein separates Caching ist dadurch nicht erforderlich, da der Completion Suggester bereits selbst als schnelle, In-Memory-Datenstruktur f\u00fcr die h\u00e4ufigsten Anfragen fungiert. Erg\u00e4nzend wird der Index mit der Option erstellt, zus\u00e4tzliche Wortpr\u00e4fixe zu speichern, damit auch der regul\u00e4re invertierte Index f\u00fcr die Suche noch unvollst\u00e4ndiger 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.<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2026\/07\/grafik-5.png\")
<\/a>Abbildung 1: Architektur der Destinationssuche innerhalb einer Region<\/figcaption><\/figure>\n\n\n\nEine Anfrage l\u00e4uft dann wie folgt ab. W\u00e4hrend der Nutzer seine Anfrage eingibt, wird bereits mit den ersten eingegebenen Buchstaben eine Anfrage gesendet. Dieser Anfrage werden zus\u00e4tzlich die Nutzerkennung und optional der aktuelle Standort mitgegeben. Die Anfrage wird \u00fcber das API Gateway an den Search Service \u00fcbermittelt. 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\u00e4re Ergebnisse, die mit dem geografischen Standort vereinbar sind, werden diese zur\u00fcckgeliefert. Liefert der Completion Suggester keine Ergebnisse, wird auf das Ergebnis der bereits parallel angefragten Suche \u00fcber den invertierten Index gewartet. Die Ergebnisse durchlaufen anschlie\u00dfend das Ranking des Learning-to-Rank-Plugins, das sie basierend auf dem mitgeschickten Standort sowie weiteren Kontextfaktoren bewertet und die relevantesten Ergebnisse zur\u00fcckliefert. Der Search Service f\u00fcgt den Ergebnissen gegebenenfalls Standorte aus der zuvor vom User Service abgefragten Nutzerhistorie hinzu, sofern diese mit der Suchanfrage \u00fcbereinstimmen. Die sortierten Ergebnisse werden abschlie\u00dfend \u00fcber das API Gateway an den Nutzer zur\u00fcckgeliefert.<\/p>\n\n\n\n
III. RIDER-DRIVER MATCHING<\/strong><\/h3>\n\n\n\nIm vorherigen Schritt wurde der gew\u00fcnschte Zielort des Nutzers erschlossen. Die zweite Hauptaufgabe der “Uber Search Plattform” besteht darin, den bestm\u00f6glichen Fahrer f\u00fcr 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\u00e4mtliche ben\u00f6tigten Komponenten, die f\u00fcr diese Funktionalit\u00e4t ben\u00f6tigt werden. In den folgenden Unterkapiteln werden die einzelnen Architekturentscheidungen aus dem Diagramm Schritt f\u00fcr Schritt erl\u00e4utert.<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2026\/07\/grafik-6-1024x413.png\")
<\/a>Abbildung 2: Rider-Driver Matching Architektur<\/figcaption><\/figure>\n\n\n\nA. Scenario<\/p>\n\n\n\n
Das gew\u00fcnschte Endresultat ist eine informative \u00dcbersichtsseite (siehe Abbildung 3). Der Ablauf zum Finden eines Paares ben\u00f6tigt folgende Schritte: <\/p>\n\n\n\n
1) Es m\u00fcssen kontinuierliche Standort-Updates der Fahrer, sowie der Standort des Kunden ermittelt werden. Mit dem gew\u00fcnschten 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. <\/p>\n\n\n\n
2) Retrieval: Aus allen georteten Fahrern m\u00fcssen naheliegende und verf\u00fcgbare ermittelt werden, wobei diese visualisiert und der Bestm\u00f6gliche f\u00fcr die Angebots- bzw. Preiserstellung ausgew\u00e4hlt wird. <\/p>\n\n\n\n
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\u00e4hrleistet ist, damit keine Doppelbuchungen auftreten.<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2026\/07\/grafik-7.png\")
<\/a>Abbildung 3: Informative \u00dcbersichtsseite f\u00fcr den Kunden.<\/figcaption><\/figure>\n\n\n\nB. Nicht-funktionale Anforderungen<\/p>\n\n\n\n
Damit das Matching-System eine Vielzahl von Nutzern zufriedenstellen kann, sind folgende Anforderungen wichtig, die es erf\u00fcllen muss:<\/p>\n\n\n\n
\n- Eine geringe End-to-End-Latenz f\u00fcr 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]<\/li>\n\n\n\n
- Eine hohe Verf\u00fcgbarkeit von 99,9%, wof\u00fcr redundante Serverstandorte den Ausfall einzelner Regionen abfangen m\u00fcssen. [37]<\/li>\n\n\n\n
- Datenaktualit\u00e4t in Form von sek\u00fcndlich aktualisierten Fahrerstandorten.<\/li>\n\n\n\n
- Eine gute Skalierbarkeit, da das System eine steigende Anzahl an Nutzeranfragen verarbeiten und mit Lastspitzen wie z.B. Freitagabenden oder Silvester rechnen muss.<\/li>\n<\/ul>\n\n\n\n
C. Empfangen von Location-Daten<\/p>\n\n\n\n
Die erste getroffene architektonische Entscheidung umfasst, wie die Standorte aller Fahrer kontinuierlich an die Server \u00fcbermittelt werden (siehe Schritt 1 in Abbildung 2). Der naheliegendste Ansatz ist hier, dass s\u00e4mtliche Fahrer-Clients ihre Daten \u00fcber HTTP-Requests an REST-APIs senden, die auf dem Server eingerichtet sind. Dabei sind jedoch einige Nachteile zu beachten. Clients m\u00fcssen auf die Antwort des Servers auf ihre HTTP-POST-Requests warten. Au\u00dferdem 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\u00fcsste. Direktes Schreiben in eine Datenbank ist ebenfalls nicht sinnvoll, da u. a. die Datenmenge zu gro\u00df ist und die Datenbank somit schnell \u00fcberlastet w\u00e4re. Um wiederholten Overhead zu vermeiden, ist es sinnvoll, eine persistente Verbindung (Session) zwischen Fahrer-Client und Server aufzubauen. Es liegt nahe, dies \u00fcber 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\u00f6nnte der Client gebremst werden, falls der Server gerade keine weiteren Daten empfangen kann. [42] <\/p>\n\n\n\n
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\u00e4nger 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. <\/p>\n\n\n\n
Der Broker ist hierbei die zentrale Komponente, die die Daten entgegennimmt und an die dahinterliegenden Konsumenten (Routing- oder Pricing-Service) weiterleitet. Konsumenten m\u00fcssen sich explizit beim Broker f\u00fcr den Datenempfang anmelden. Nachdem sie das Empfangen einer Datensequenz best\u00e4tigt haben, wird diese beim Broker gel\u00f6scht, wodurch kein Replay der Daten mehr erfolgen kann. [44] <\/p>\n\n\n\n
Eine deutlich geeignetere L\u00f6sung stellt hier Apache Kafka dar. Dabei handelt es sich um eine Plattform, die ausdr\u00fccklich f\u00fcr 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\u00f6rigen Daten, und der Key gibt die Partition an, auf der ein geordnetes Log gef\u00fchrt wird, in welchem die Nachrichten (Standortdaten) gespeichert werden. Somit k\u00f6nnen 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\u00fcgt werden k\u00f6nnen, ohne dass der Broker davon wissen muss. [45]<\/p>\n\n\n\n
D. Map Index Updater<\/p>\n\n\n\n
Das erste Ziel der Such\u00fcbersicht ist es, Fahrer im Umkreis des Kunden zu finden. Ein trivialer Ansatz w\u00fcrde die Abst\u00e4nde zwischen dem Kunden und allen Fahrern in dessen Region berechnen, wobei die relevanten Standortdaten \u00fcber das korrekte Kafka-Topic gefiltert werden k\u00f6nnten. Dies ist jedoch einerseits \u00fcberkorrekt, da die genaue Distanz nicht ben\u00f6tigt wird, sondern nur die Information, ob ein Fahrer in der N\u00e4he ist. Andererseits werden fast nie zwei Anfragen von exakt dem gleichen Standort gemacht, weshalb die Berechnungen nicht wiederverwendet werden k\u00f6nnen. <\/p>\n\n\n\n
Aus diesen Gr\u00fcnden ist es vorteilhafter, bei Standorten nicht exakte Koordinatenpunkte, sondern Fl\u00e4chen zu verwenden. Diese Umwandlung geschieht durch einen Map Index Updater (siehe Schritt 2 in Abbildung 2). <\/p>\n\n\n\n
Uber verwendet hierf\u00fcr das hierarchische Raumindex-System H3, welches die gesamte Erde in ein gleichm\u00e4\u00dfiges 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\u00e4chenform verwendet, da diese unregelm\u00e4\u00dfige Formen haben und potenziell mit der Zeit ver\u00e4ndert werden k\u00f6nnten und sich deshalb nicht f\u00fcr Kalkulationen eignen. Hexagons hingegen haben den Vorteil, dass ein gleichm\u00e4\u00dfiger Abstand zu allen Nachbarn gegeben ist.<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2026\/07\/grafik-8.png\")
<\/a>Abbildung 4: H3-Hexagon-Preis-Smoothing.<\/figcaption><\/figure>\n\n\n\nEiner H3-Zelle werden Metriken wie verf\u00fcgbare 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\u00fchren w\u00fcrde, k\u00f6nnen folgende Funktionen angewendet werden:<\/p>\n\n\n\n
\n- Mit der kRing(index, k)-Funktion k\u00f6nnen alle Nachbarzellen bis zu einer Distanz von k Ringen um die Zelle index ermittelt werden.<\/li>\n\n\n\n
- 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\u00fchrt dies beispielsweise dazu, dass die zentrale Zelle mit Preismultiplikator 5 und deren Nachbarzellen aneinander angepasst werden. <\/li>\n<\/ul>\n\n\n\n
In Abbildung 4 f\u00fchrt dies beispielsweise dazu, dass die zentrale Zelle mit Preismultiplikator 5 und deren Nachbarzellen aneinander angepasst werden. Somit k\u00f6nnen drastische Preisspr\u00fcnge vermieden werden, nur weil der Kunde sich einen Stra\u00dfenblock weiter bewegt. [46]<\/p>\n\n\n\n
E. Map Matching<\/p>\n\n\n\n
Ein Hindernis beim Nachverfolgen von Fahrern besteht darin, dass GPS-Daten zeitweise ungenau sind und Koordinaten beinhalten, die nicht auf Stra\u00dfen liegen. Diese Daten einfach zu \u00fcbernehmen h\u00e4tte eine negative Auswirkung auf die Benutzeroberfl\u00e4che, bspw. wenn ein Auto in einem Geb\u00e4ude angezeigt wird, und k\u00f6nnte zu Problemen bei der Routenberechnung f\u00fchren. Die haupts\u00e4chlichen Gr\u00fcnde f\u00fcr diese Ausrei\u00dfer sind gel\u00e4ndebedingt, wie etwa Stra\u00dfenschluchten zwischen hohen Geb\u00e4uden, bei denen das GPS-Signal von Fassaden reflektiert wird, bevor es den Empf\u00e4nger erreicht. [47, S. 337] Dieses Problem wird durch einen Map Matcher gel\u00f6st (siehe Schritt 3 in Abbildung 2), welcher GPS-Koordinaten auf die korrekte Stra\u00dfe abbildet. Dabei wird das sog. Hidden Markov Model (HMM) verwendet, bei dem neben der Entfernung zur n\u00e4chsten Stra\u00dfe auch der Kontext, also vorher und nachher gesendete Koordinaten, ausgewertet wird, um die korrekte Stra\u00dfe zu bestimmen. Das Map Matching wird auf zwei Ebenen angewandt: Ein niedrig-latenter Matcher l\u00e4sst die Fahrer nahezu in Echtzeit auf den Stra\u00dfen erscheinen, w\u00e4hrend ein Offline-Matcher das CATCHME-System mit Standortdaten f\u00fcttert. <\/p>\n\n\n\n
CATCHME steht f\u00fcr “Catch Map Error” und wertet Routeninformationen aus, um das Uber-eigene Stra\u00dfensystem zu optimieren. Befinden sich wiederholt Daten am gleichen Punkt neben anstatt auf einer berechneten Route, so ist dies ein Zeichen daf\u00fcr, dass die eigentliche Stra\u00dfe neu gezeichnet werden muss. [48]<\/p>\n\n\n\n
F. Standortspeicherung<\/p>\n\n\n\n
F\u00fcr 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\u00e4lt und dadurch besonders schnelle Lese- \/Schreibzugriffe erm\u00f6glicht. [49] <\/p>\n\n\n\n
Aufgrund der \u00fcberaus gro\u00dfen Datenmenge wird ein Sharding-Layer namens “Ringpop” eingesetzt, in welchem mehrere Redis-Server ringf\u00f6rmig angeordnet werden, wobei jedem Server ein fester Teilbereich der Fahrerdaten z.B. basierend auf geographischer Region zugeteilt wird [50], [51].<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2026\/07\/grafik-9.png\")
<\/a>Abbildung 5: Ringpop-Sharding-Ring.<\/figcaption><\/figure>\n\n\n\nFalls ein Server ausf\u00e4llt oder entfernt wird, kommunizieren die Server untereinander \u00fcber 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\u00e4sst, kann gel\u00f6st werden, indem die Verbindung zum urspr\u00fcnglichen Server aufrechterhalten wird, und dieser die Daten einfach an den korrekten Server weiterleitet [50]. Durch das Replizieren von Daten auf mehreren Servern kann au\u00dferdem die Ausfalltoleranz erh\u00f6ht werden [50], [51].<\/p>\n\n\n\n
G. Routing-Service<\/p>\n\n\n\n
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\u00fcr weitere Schritte wie Preisberechnung und Fahrer-Matching ben\u00f6tigt wird. Der klassische Ansatz, das Stra\u00dfennetz als Graphen zu modellieren, bei dem die ben\u00f6tigte 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\u00e4mlich nicht statisch, sondern \u00e4ndern 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\u00fcnglichen Routing-Engine-Sch\u00e4tzung und der tats\u00e4chlichen Fahrzeit angeben. Zum Beispiel erh\u00e4lt eine H3-Zelle mit einer Stra\u00dfenkreuzung, die wochentags um 7:10 Uhr stark frequentiert wird, f\u00fcr diesen Zeitrahmen ein Residual von +2 Minuten, welches in s\u00e4mtliche ETA-Berechnungen einflie\u00dft. [52]<\/p>\n\n\n\n
H. Surge Pricing<\/p>\n\n\n\n
F\u00fcr das Erf\u00fcllen von Auftr\u00e4gen sind manche Regionen f\u00fcr Fahrer attraktiver als andere. Innenst\u00e4dte bieten beispielsweise eine hohe Auftragsdichte, jedoch sind daf\u00fcr meist die Stra\u00dfen \u00fcberf\u00fcllter, Park- oder Haltegelegenheiten seltener und die Fahrtzeiten dadurch l\u00e4nger. 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\u00f6here Multiplikatoren gezielt Anreize f\u00fcr Fahrer in bestimmten Regionen setzt und die Fahrer dadurch gleichm\u00e4\u00dfig auf die Karte verteilt. [53] Damit Fahrer sich bereits im Voraus vorteilhaft positionieren k\u00f6nnen, m\u00fcssen diese Werte vorab berechnet werden. Weitere Faktoren, die zu einem hohen Preis-Multiplikator zu einer bestimmten Zeit an einem bestimmten Ort f\u00fchren, sind etwa Gro\u00dfevents oder schlechte Wetterbedingungen. [54]<\/p>\n\n\n\n![\"\"](\"https:\/\/blog.mi.hdm-stuttgart.de\/wp-content\/uploads\/2026\/07\/grafik-10.png\")
<\/a>Abbildung 6: Surge-Pricing-Heatmap.<\/figcaption><\/figure>\n\n\n\nI. Feature Store<\/p>\n\n\n\n
Da komplexe Metriken wie ETA oder Preisindizes in Echtzeit die Latenz erh\u00f6hen w\u00fcrden, werden sie bereits im Vorfeld berechnet und in einem Feature Store gespeichert (siehe Schritt 7 in Abbildung 2). F\u00fcr die kontinuierliche Vorberechnung wird die Stream-Processing-Engine Apache Flink eingesetzt, welche zustandsbehaftete Berechnungen \u00fcber unbegrenzte Datenstr\u00f6me erm\u00f6glicht, d.h. Berechnungen, die auch Vergangenheitsdaten mit einbeziehen. [55] In diesem Fall flie\u00dfen 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 \u00dcbergang entsteht. Flink l\u00e4uft also als Rechenmaschine permanent im Hintergrund, und wenn eine Nutzeranfrage am System eingeht, so k\u00f6nnen dahinterliegende Services sofort auf die hier berechneten Daten zugreifen.<\/p>\n\n\n\n
J. Matching Service<\/p>\n\n\n\n
A. Anforderungen an die Destinationssuche<\/p>\n\n\n\n
Im Detail hat die Destinationssuche einer Ride-Hailing-Plattform die Aufgabe, aus der textuellen Eingabe des Kunden die gew\u00fcnschten Abhol- und Zielstandorte zu bestimmen. Bereits w\u00e4hrend der Eingabe sollen dem Kunden passende Vorschl\u00e4ge angezeigt werden, sodass im Idealfall schon wenige eingegebene Buchstaben gen\u00fcgen, um den gew\u00fcnschten Standort zu finden. Die final ausgew\u00e4hlten Standorte legen dabei nicht nur fest, von wo nach wo die Fahrt gehen soll, sondern bilden auch die Grundlage f\u00fcr das nachgelagerte Rider-Driver-Matching. Aus diesem Szenario lassen sich zusammen mit der Voraussetzung eines gro\u00dfen und geografisch verteilten Systems die folgenden Anforderungen ableiten. <\/p>\n\n\n\n
Funktionale Anforderungen<\/strong><\/p>\n\n\n\n Nicht funktionale Anforderungen<\/strong><\/p>\n\n\n\n B. Grundlegende Suchkonzepte und -technologien<\/p>\n\n\n\n Bei einer geringen Anzahl an Dokumenten kann eine Suche direkt und sequenziell \u00fcber den gesamten Datenbestand erfolgen. F\u00fcr kleinere Dokumentenmengen ist das mit der heutigen Rechenleistung durchaus praktikabel. Mit zunehmender Gr\u00f6\u00dfe wird dieser Ansatz jedoch ineffizient, da f\u00fcr jede Suchanfrage alle Dokumente durchsucht werden m\u00fcssen und die Suchzeit dadurch linear mit der Anzahl der Dokumente w\u00e4chst. Au\u00dferdem 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.<\/p>\n\n\n\n Lexikalische Suche \u00fcber invertierte Indizes<\/strong> <\/p>\n\n\n\n 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\u00fcr 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\u00fchrt. Das Ergebnis enth\u00e4lt dann alle Dokumente, die diesen Term enthalten. Die Suchgeschwindigkeit bleibt dabei auch bei gro\u00dfen Datenmengen weitgehend erhalten [3]. <\/p>\n\n\n\n Die beschriebene Funktionalit\u00e4t des invertierten Index erm\u00f6glicht so in der einfachsten Form zun\u00e4chst nur exakte Keyword-Treffer. Bei Schreibfehlern oder alternativen Begriffen f\u00fchrt diese Suche zu keinen Treffern. Wie in den Anforderungen definiert wurde, muss die Suche jedoch weitestgehend dagegen tolerant sein. Verschiedene Vor-Verarbeitungsschritte m\u00fcssen daher zus\u00e4tzlich eingesetzt werden, um dies zu erf\u00fcllen. <\/p>\n\n\n\n Sowohl beim Erstellen des Indexes als auch bei der Suchanfrage werden die Texte zun\u00e4chst mit einem Tokenizer in einzelne Tokens zerlegt. Diese Tokens sind meist einzelne W\u00f6rter [3]. Diese Tokens werden dann gewisserma\u00dfen normalisiert, indem sie in Kleinschreibung umgewandelt werden und Sonderzeichen aufgel\u00f6st werden [3] [4]. Um auch Suchergebnisse zu erhalten trotz Tippfehlern oder leicht abweichender Schreibweisen, lassen sich Fuzzy-Search-Algorithmen einsetzen. Diese erkennen \u00c4hnlichkeiten zwischen Suchbegriffen und den indexierten Termen, beispielsweise durch die Berechnung der Levenshtein-Distanz. Dabei wird die minimale Anzahl an Einf\u00fcgungen, L\u00f6schungen oder Ersetzungen bestimmt, die n\u00f6tig sind, um eine Zeichenkette in eine andere umzuwandeln [5]. F\u00fcr synonyme Begriffe k\u00f6nnen Synonym-Filter eingesetzt werden, die bedeutungsgleiche Worte zu dem eingegebenen Suchbegriff in den Such-Stream hinzuf\u00fcgen oder den initialen Suchbegriff ersetzen [6]. Dazu muss eine Synonymliste erstellt werden, hierf\u00fcr lassen sich bereits existierende Listen wie beispielsweise WordNet verwenden, die dann gegebenenfalls erweitert werden k\u00f6nnen [7]. Diese Mechanismen erweitern den Suchraum \u00fcber exakte Treffer hinaus und erf\u00fcllen dabei die zuvor beschriebene Anforderung hinsichtlich Toleranz gegen\u00fcber Tippfehlern, Abk\u00fcrzungen und Synonymen. <\/p>\n\n\n\n Nachdem die Vor-Verarbeitungsschritte und die Suche selbst durchgef\u00fchrt wurden, lassen sich die zur\u00fcckgelieferten Ergebnisse auf textueller Ebene noch nach ihrer Relevanz sortieren. Ein Beispiel hierf\u00fcr ist BM25, das f\u00fcr jedes Dokument einen Relevanz-Score in Bezug auf die Suchanfrage berechnet. Dieser Score basiert auf drei Faktoren: der Termh\u00e4ufigkeit (wie oft ein Suchbegriff im Dokument vorkommt), der inversen Dokumenth\u00e4ufigkeit (seltene Begriffe gelten als aussagekr\u00e4ftiger als h\u00e4ufig vorkommende) sowie einer Normalisierung bez\u00fcglich der Dokumentl\u00e4nge, damit l\u00e4ngere Dokumente nicht allein aufgrund ihrer L\u00e4nge bevorzugt werden [8]. Damit bildet BM25 eine m\u00f6gliche textuelle Grundlage f\u00fcr Relevanz von Suchergebnissen. <\/p>\n\n\n\n Der invertierte Index sowie die beschriebenen Vor-Verarbeitungsschritte und das textuelle Ranking m\u00fcssen nicht von Grund auf selbst implementiert werden. Stattdessen l\u00e4sst sich Apache Lucene verwenden, das praktisch als Industriestandard daf\u00fcr gilt [9]. F\u00fcr 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\u00e4ndert werden. Dies erm\u00f6glicht, dass mehrere Threads gleichzeitig lesen k\u00f6nnen, ohne dass Locking erforderlich ist. Damit trotzdem neue Dokumente aufgenommen werden k\u00f6nnen, l\u00f6st Lucene dies \u00fcber sogenannte Segmente. F\u00fcr neue Dokumente wird dann jeweils ein eigenes Segment angelegt, das selbst wieder ein invertierter Index ist. Alle Segmente zusammen ergeben den vollst\u00e4ndigen Index [10]. Ein neues Dokument gelangt dabei zun\u00e4chst in einen In-Memory-Buffer, wird anschlie\u00dfend \u00fcber einen Refresh als durchsuchbares Segment im Filesystem-Cache verf\u00fcgbar gemacht und schlie\u00dflich \u00fcber einen Flush persistent auf die Disk geschrieben [11]. Mit der Zeit entstehen durch dieses Verfahren viele kleine Segmente sowie eventuell einige f\u00fcr die L\u00f6schung markierte Eintr\u00e4ge. Deshalb f\u00fchrt Lucene periodisch ein Merging durch. Dabei werden zum einen die f\u00fcr die L\u00f6schung markierten Dokumente endg\u00fcltig entfernt, wodurch Speicher freigegeben wird. Zum anderen werden viele kleine Segmente, die sonst zu schlechterer Suchperformance f\u00fchren k\u00f6nnen, zu wenigen, m\u00f6glichst gleich gro\u00dfen Segmenten zusammengef\u00fchrt [12].<\/p>\n\n\n\n Semantische Suche<\/strong> <\/p>\n\n\n\n Die lexikalische Suche ermittelt Ergebnisse auf der textuellen Ebene. Durch die zuvor genannten zus\u00e4tzlichen Methoden l\u00e4sst sich diese um Tippfehler-Toleranz sowie zus\u00e4tzliches Suchen nach Synonymen erweitern, statt nur Terme exakt zu vergleichen. Die semantische Suche hingegen ermittelt bedeutungsnahe Ergebnisse zu der Suchanfrage. Dabei werden W\u00f6rter oder ganze Dokumente in numerische Vektoren umgewandelt, welche die Bedeutung der Inhalte abbilden. Inhalte mit \u00e4hnlicher Bedeutung liegen im Vektorraum n\u00e4her beieinander und k\u00f6nnen dadurch gefunden werden, auch wenn unterschiedliche Begriffe verwendet werden [13]. <\/p>\n\n\n\n F\u00fcr die Suche wird der Vektorraum nach Vektoren durchsucht, die r\u00e4umlich nahe dem Vektor liegen, der die Suchanfrage repr\u00e4sentiert. Die exakte Suche nach den n\u00e4chsten Vektoren wird bei gro\u00dfen Datenmengen jedoch ineffizient, da die \u00c4hnlichkeit mit allen gespeicherten Vektoren berechnet werden m\u00fcsste. Deshalb kommen f\u00fcr die Suche Approximate-Nearest-Neighbor-Verfahren wie HNSW (Hierarchical Navigable Small World) zum Einsatz. Diese suchen nicht nach einer exakten, sondern nach einer m\u00f6glichst guten Ann\u00e4herung der n\u00e4chsten Vektoren, wodurch sich der Berechnungsaufwand deutlich reduzieren l\u00e4sst [13]. F\u00fcr 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\u00fcr den Anwendungsfall demnach besser geeignet. <\/p>\n\n\n\n Erg\u00e4nzende Bausteine der Suche<\/strong> <\/p>\n\n\n\n Ein weiterer wichtiger Faktor f\u00fcr die Bestimmung der Relevanz von Ergebnissen sind Kontextfaktoren wie geographische N\u00e4he, Nutzerdaten oder auch die Uhrzeit. Hierf\u00fcr l\u00e4sst sich ein Machine Learning Modell einsetzen, das Suchergebnisse anhand dieser zus\u00e4tzlichen Faktoren bewertet und darauf basierend sortiert. Beispielsweise kann ein Learning-to-Rank-Modell verwendet werden, das mithilfe von Machine-Learning-Verfahren verschiedene Merkmale ber\u00fccksichtigt, um die erwartete Relevanz von Suchergebnissen zu bestimmen und diese entsprechend zu ordnen [14]. <\/p>\n\n\n\n F\u00fcr Standorte, f\u00fcr die keine zugeh\u00f6rigen Koordinaten vorliegen, kann Geocoding verwendet werden, um aus der Adresse in Textform geografische Koordinaten zu ermitteln. Hierf\u00fcr gibt es verschiedene APIs, wie beispielsweise die Google Geocoding API [15]. <\/p>\n\n\n\n F\u00fcr die technische Umsetzung einer Autovervollst\u00e4ndigung k\u00f6nnen verschiedene Ans\u00e4tze eingesetzt werden. Ein Ansatz besteht darin, die m\u00f6glichen Vervollst\u00e4ndigungen separat in einer eigenen Datenstruktur zu indexieren. Optional l\u00e4sst sich dabei eine Relevanz vergeben, beispielsweise basierend darauf, wie h\u00e4ufig ein Begriff gesucht wird. Bei einer Eingabe werden die passendsten Vervollst\u00e4ndigungen direkt aus dieser Datenstruktur zur\u00fcckgegeben, ohne dass dabei auf den regul\u00e4ren invertierten Index zugegriffen wird. Ein weiterer Ansatz ist die Indexierung von Wortpr\u00e4fixen. Hierbei werden bereits beim Indexieren Wortpr\u00e4fixe als eigene Tokens im regul\u00e4ren invertierten Index abgelegt, sodass die Autovervollst\u00e4ndigung direkt dar\u00fcber l\u00e4uft [16]. <\/p>\n\n\n\n F\u00fcr die Standortdaten selbst wird eine Datenquelle ben\u00f6tigt, aus der Orte mit ihren zugeh\u00f6rigen Informationen wie Namen, Adressen und Koordinaten stammen. Hierf\u00fcr k\u00f6nnen externe Provider genutzt werden, die eine Datenbank mit Orten sowie eine Schnittstelle zur Abfrage dieser Orte bereitstellen. Ein Beispiel hierf\u00fcr ist die Places API von Google [17].<\/p>\n\n\n\n C. Verteilte Suchtechnologien<\/p>\n\n\n\n Die zuvor beschriebenen Suchtechnologien liefern bereits die Grundlagen daf\u00fcr, die funktionalen Anforderungen zu erf\u00fcllen. Bez\u00fcglich der nicht-funktionalen Anforderungen, besonders Skalierung und geografischer Verteilung, zeigen die beschriebenen Technologien noch keine m\u00f6gliche Umsetzung. Apache Lucene selbst bietet keine M\u00f6glichkeit die Suche verteilt zu betreiben. Die Verteilung von Daten \u00fcber mehrere Knoten hinweg sowie deren Koordination ist damit nicht Teil von Lucene selbst und m\u00fcsste manuell drumherum implementiert werden [18]. <\/p>\n\n\n\n Im Folgenden werden daher Suchtechnologien untersucht, die diese Funktionalit\u00e4ten bereits mitbringen, sodass sie nicht von Grund auf selbst implementiert werden m\u00fcssen. Daf\u00fcr 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\u00fchrt [19]. Erg\u00e4nzend wurde Vespa hinzugezogen, das f\u00fcr seine F\u00e4higkeiten in der semantischen Suche bekannt ist, aber auch lexikalische Suche unterst\u00fctzt [20]. Der Vergleich betrachtet dazu Query-Speed, Datenaktualit\u00e4t, Skalierung, Replikation, geografische Distribution, Ranking mit Kontextfaktoren, Autovervollst\u00e4ndigung sowie das jeweilige \u00d6kosystem.<\/p>\n\n\n\n Query Speed<\/strong> F\u00fcr 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\u00fchrt hat [21]. Bei der f\u00fcr die Destinationssuche relevantesten Operation, einfachen Term-Abfragen, zeigt sich praktisch kein Unterschied zwischen beiden Systemen. F\u00fcr Vespa existieren ausschlie\u00dflich herstellereigene Benchmark-Daten, die einen deutlichen Geschwindigkeitsvorteil zu ES bei lexikalischer Suche aufzeigen [22]. Diese Zahlen sind jedoch nicht unabh\u00e4ngig verifiziert und daher mit Vorsicht zu betrachten. <\/p>\n\n\n\n Datenaktualit\u00e4t<\/strong> Da sowohl ES als auch OS auf Apache Lucene aufbauen, ist die Datenaktualit\u00e4t durch das Refresh-Intervall von Lucene begrenzt. Demnach ist Near-Real-Time die maximal erreichbare Aktualit\u00e4t [11]. Auch bei Vespa werden Dokumente nicht sofort, sondern erst nach einem periodischen Flush durchsuchbar, \u00e4hnlich wie bei Lucene, auch wenn Vespa nicht auf Lucene basiert [23]. <\/p>\n\n\n\n Skalierung<\/strong> Bei der Skalierung folgen ES und OS demselben Prinzip: Beide setzen auf statisches Sharding, das hei\u00dft, die Anzahl der Shards wird bereits beim Erstellen des Index festgelegt [24] [25]. M\u00fcssen weitere Shards hinzuf\u00fcgt werden, muss der Index neu erstellt werden, da die Anzahl der Shards f\u00fcr einen existierenden Index nicht mehr angepasst werden k\u00f6nnen [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 \u00fcber die konkrete Datenverteilung einher. <\/p>\n\n\n\n Replikation<\/strong> ES und OS folgen dem Prinzip der Active-Passive-Replikation: \u00c4nderungen werden zun\u00e4chst auf einem Prim\u00e4rshard angewendet und dann an die Replicas verteilt [28]. Vespa schreibt stattdessen synchron auf alle verf\u00fcgbaren Replicas parallel und wartet auf deren Best\u00e4tigung, ohne festen Prim\u00e4rknoten [29]. <\/p>\n\n\n\n Geografische Distribution<\/strong> ES und OS bieten mit Cross-Cluster Replication (CCR) ein dediziertes Feature f\u00fcr den Betrieb \u00fcber mehrere Rechenzentren hinweg. Mehrere unabh\u00e4ngige Cluster werden dabei nach dem Active-Passive-Prinzip \u00fcber Regionen hinweg repliziert [30] [31]. Bei Vespa gibt es kein \u00c4quivalent zu CCR. Knoten m\u00fcssten stattdessen innerhalb einer einzigen, zusammenh\u00e4ngenden Einheit geografisch verteilt werden [29]. <\/p>\n\n\n\n Ranking mit Kontextfaktoren<\/strong> Bei ES und OS kann Learning to Rank \u00fcber 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\u00e4tzliches Plugin [34]. <\/p>\n\n\n\n Autovervollst\u00e4ndigung<\/strong> ES und OS unterst\u00fctzen beide zuvor beschriebenen Ans\u00e4tze. Zum einen das Plugin Completion Suggester, das Vervollst\u00e4ndigungen in einer eigenen, separaten Datenstruktur indexiert. Zum anderen die Option, Wortpr\u00e4fixe direkt im regul\u00e4ren invertierten Index abzulegen und somit auf die normale Suchinfrastruktur zur\u00fcckzugreifen [16] [35]. Vespa bietet daf\u00fcr keine fertige L\u00f6sung, eine Pr\u00e4fixsuche m\u00fcsste selbst umgesetzt werden [36]. <\/p>\n\n\n\n \u00d6kosystem<\/strong> ES und OS verf\u00fcgen beide \u00fcber eine gro\u00dfe Community und ein breites Angebot an Zusatzwerkzeugen. OpenSearch ist dazu vollst\u00e4ndig quelloffen. Vespa hat demgegen\u00fcber eine deutlich kleinere Community und gilt als weniger etabliert. Hinsichtlich verf\u00fcgbarer Ressourcen sind ES und OS damit im Vorteil.<\/p>\n\n\n\n D. Praxisbeispiel: Uber<\/p>\n\n\n\n Ein Blick auf Uber als gro\u00dfe Ride-Hailing-Plattform lohnt sich, da sich deren Suchinfrastruktur \u00fcber die Jahre mehrfach gewandelt und weiterentwickelt hat. Uber setzte vor 2019 auf Elasticsearch, stellte jedoch fest, dass die Near-Real-Time-Aktualit\u00e4t f\u00fcr bestimmte Anwendungsf\u00e4lle nicht ausreichte [37]. F\u00fcr die Destinationssuche selbst erscheint das zun\u00e4chst weniger naheliegend, da sich Standortdaten selten \u00e4ndern und nicht unbedingt Echtzeit aktuell sein m\u00fcssen. Es d\u00fcrfte sich also eher um einen anderen Bereich von Uber gehandelt haben, der auch Teil derselben Suchinfrastruktur ist. <\/p>\n\n\n\n Als Reaktion entwickelte Uber mit SIA (2019 bis 2024) eine eigene, auf Apache Lucene basierende L\u00f6sung mit Echtzeit-F\u00e4higkeiten. 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\u00f6chentlich zusammengef\u00fchrt werden. Erg\u00e4nzend f\u00fchrte Uber gRPC statt REST f\u00fcr effizientere Service-Kommunikation ein und stellte auf eine Kafka-basierte Pull-Ingestion um, wodurch Backpressure-Handling erm\u00f6glicht wird. Zus\u00e4tzlich implementierte Uber Active-Active-Cross-Cluster-Replikation statt der zuvor \u00fcblichen Active-Passive-Variante [37]. Bei Active-Active k\u00f6nnen, im Unterschied zum Leader-Follower-Prinzip von OS und ES, bei dem nur der Leader-Cluster Schreibvorg\u00e4nge annimmt, alle Regionen \u00c4nderungen annehmen. Eine \u00c4nderung wird dabei zun\u00e4chst in das lokale Kafka der jeweiligen Region geschrieben, das sie anschlie\u00dfend an die Kafka-Instanzen aller anderen Regionen verteilt, wo sie wiederum von den dortigen Suchclustern konsumiert wird [38]. <\/p>\n\n\n\n SIA erwies sich jedoch langfristig als problematisch. Die Eigenentwicklung war wartungsintensiv, und neue Lucene-Features lie\u00dfen sich nur schwer integrieren. Zudem zeigte sich, dass die meisten tats\u00e4chlichen Anwendungsf\u00e4lle gar kein Echtzeit-Indexing ben\u00f6tigten und mit Near-Real-Time-Aktualit\u00e4t 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\u00fcr den Umstieg auf OpenSearch, unter anderem auch, um direkt an dessen Weiterentwicklung mitzuwirken. Bew\u00e4hrte Konzepte aus SIA wie die gRPC-Kommunikation und die Pull-based-Ingestion wurden dabei zu OpenSearch \u00fcbernommen [37]. <\/p>\n\n\n\n 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\u00fcr OS statt ES entschieden, um dort eigene Erkenntnisse einzubringen [37].<\/p>\n\n\n\n E. Technologiewahl<\/p>\n\n\n\n Basierend auf der vorangegangenen Betrachtung der Tools sowie dem Praxisbeispiel Uber f\u00e4llt die Wahl auf OpenSearch. Zwischen ES und OS selbst gibt es kaum Unterschiede: Bei Query-Speed f\u00fcr einfache Term-Abfragen, dem f\u00fcr die Destinationssuche relevantesten Fall, zeigt sich praktisch kein Unterschied. Auch bei Datenaktualit\u00e4t, Skalierung und Replikation folgen beide demselben architektonischen Prinzip, da OS urspr\u00fcnglich ein Fork von ES ist. Den Ausschlag gibt daher das Lizenzmodell: OpenSearch steht vollst\u00e4ndig unter der offenen Apache License 2.0, w\u00e4hrend neuere Elasticsearch-Versionen unter der restriktiveren Elastic License stehen, ein Aspekt, den auch Uber als Grund f\u00fcr die Wahl von OpenSearch statt Elasticsearch anf\u00fchrt. 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\u00dfen Systemen im praktischen Einsatz bewiesen haben, dass sie zuverl\u00e4ssig funktionieren. Zudem hat Vespa eine deutlich kleinere Community und bietet hinsichtlich Query-Speed und Datenaktualit\u00e4t keinen belegten Vorteil gegen\u00fcber OpenSearch.<\/p>\n\n\n\n F. Architektur<\/p>\n\n\n\n F\u00fcr eine konkrete m\u00f6gliche Umsetzung besteht die Architektur aus f\u00fcnf zentralen Komponenten: dem Search Service als zentrale orchestrierende Komponente, dem OpenSearch-Cluster f\u00fcr 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\u00f6nnen.<\/p>\n\n\n\n F\u00fcr 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 \u00c4nderungen an bestehenden Standorten. Diese \u00c4nderungen k\u00f6nnen dabei in jeder Region eingetragen werden und gelangen zun\u00e4chst 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 \u00fcblichen OpenSearch-Leader-Follower-Prinzip nur in einer prim\u00e4ren Region. Jedes regionale OpenSearch-Cluster konsumiert die \u00c4nderungen anschlie\u00dfend \u00fcber die Pull-based-Funktionalit\u00e4t. Innerhalb des OpenSearch-Clusters kommen mehrere Komponenten zum Einsatz. F\u00fcr die Autovervollst\u00e4ndigung werden zwei Ans\u00e4tze kombiniert eingesetzt. Der Completion Suggester speichert h\u00e4ufig gesuchte Ergebnisse zu den entsprechenden Pr\u00e4fixen in einer eigenen, schnellen In-Memory-Datenstruktur. \u00dcber die Geo-Context-Funktion wird dabei auch der geografische Bereich der Eintr\u00e4ge gespeichert, wodurch sich schnell popul\u00e4re Ergebnisse aus der N\u00e4he abfragen lassen. Ein separates Caching ist dadurch nicht erforderlich, da der Completion Suggester bereits selbst als schnelle, In-Memory-Datenstruktur f\u00fcr die h\u00e4ufigsten Anfragen fungiert. Erg\u00e4nzend wird der Index mit der Option erstellt, zus\u00e4tzliche Wortpr\u00e4fixe zu speichern, damit auch der regul\u00e4re invertierte Index f\u00fcr die Suche noch unvollst\u00e4ndiger 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.<\/p>\n\n\n\n Eine Anfrage l\u00e4uft dann wie folgt ab. W\u00e4hrend der Nutzer seine Anfrage eingibt, wird bereits mit den ersten eingegebenen Buchstaben eine Anfrage gesendet. Dieser Anfrage werden zus\u00e4tzlich die Nutzerkennung und optional der aktuelle Standort mitgegeben. Die Anfrage wird \u00fcber das API Gateway an den Search Service \u00fcbermittelt. 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\u00e4re Ergebnisse, die mit dem geografischen Standort vereinbar sind, werden diese zur\u00fcckgeliefert. Liefert der Completion Suggester keine Ergebnisse, wird auf das Ergebnis der bereits parallel angefragten Suche \u00fcber den invertierten Index gewartet. Die Ergebnisse durchlaufen anschlie\u00dfend das Ranking des Learning-to-Rank-Plugins, das sie basierend auf dem mitgeschickten Standort sowie weiteren Kontextfaktoren bewertet und die relevantesten Ergebnisse zur\u00fcckliefert. Der Search Service f\u00fcgt den Ergebnissen gegebenenfalls Standorte aus der zuvor vom User Service abgefragten Nutzerhistorie hinzu, sofern diese mit der Suchanfrage \u00fcbereinstimmen. Die sortierten Ergebnisse werden abschlie\u00dfend \u00fcber das API Gateway an den Nutzer zur\u00fcckgeliefert.<\/p>\n\n\n\n Im vorherigen Schritt wurde der gew\u00fcnschte Zielort des Nutzers erschlossen. Die zweite Hauptaufgabe der “Uber Search Plattform” besteht darin, den bestm\u00f6glichen Fahrer f\u00fcr 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\u00e4mtliche ben\u00f6tigten Komponenten, die f\u00fcr diese Funktionalit\u00e4t ben\u00f6tigt werden. In den folgenden Unterkapiteln werden die einzelnen Architekturentscheidungen aus dem Diagramm Schritt f\u00fcr Schritt erl\u00e4utert.<\/p>\n\n\n\n A. Scenario<\/p>\n\n\n\n Das gew\u00fcnschte Endresultat ist eine informative \u00dcbersichtsseite (siehe Abbildung 3). Der Ablauf zum Finden eines Paares ben\u00f6tigt folgende Schritte: <\/p>\n\n\n\n 1) Es m\u00fcssen kontinuierliche Standort-Updates der Fahrer, sowie der Standort des Kunden ermittelt werden. Mit dem gew\u00fcnschten 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. <\/p>\n\n\n\n 2) Retrieval: Aus allen georteten Fahrern m\u00fcssen naheliegende und verf\u00fcgbare ermittelt werden, wobei diese visualisiert und der Bestm\u00f6gliche f\u00fcr die Angebots- bzw. Preiserstellung ausgew\u00e4hlt wird. <\/p>\n\n\n\n 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\u00e4hrleistet ist, damit keine Doppelbuchungen auftreten.<\/p>\n\n\n\n B. Nicht-funktionale Anforderungen<\/p>\n\n\n\n Damit das Matching-System eine Vielzahl von Nutzern zufriedenstellen kann, sind folgende Anforderungen wichtig, die es erf\u00fcllen muss:<\/p>\n\n\n\n C. Empfangen von Location-Daten<\/p>\n\n\n\n Die erste getroffene architektonische Entscheidung umfasst, wie die Standorte aller Fahrer kontinuierlich an die Server \u00fcbermittelt werden (siehe Schritt 1 in Abbildung 2). Der naheliegendste Ansatz ist hier, dass s\u00e4mtliche Fahrer-Clients ihre Daten \u00fcber HTTP-Requests an REST-APIs senden, die auf dem Server eingerichtet sind. Dabei sind jedoch einige Nachteile zu beachten. Clients m\u00fcssen auf die Antwort des Servers auf ihre HTTP-POST-Requests warten. Au\u00dferdem 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\u00fcsste. Direktes Schreiben in eine Datenbank ist ebenfalls nicht sinnvoll, da u. a. die Datenmenge zu gro\u00df ist und die Datenbank somit schnell \u00fcberlastet w\u00e4re. Um wiederholten Overhead zu vermeiden, ist es sinnvoll, eine persistente Verbindung (Session) zwischen Fahrer-Client und Server aufzubauen. Es liegt nahe, dies \u00fcber 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\u00f6nnte der Client gebremst werden, falls der Server gerade keine weiteren Daten empfangen kann. [42] <\/p>\n\n\n\n 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\u00e4nger 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. <\/p>\n\n\n\n Der Broker ist hierbei die zentrale Komponente, die die Daten entgegennimmt und an die dahinterliegenden Konsumenten (Routing- oder Pricing-Service) weiterleitet. Konsumenten m\u00fcssen sich explizit beim Broker f\u00fcr den Datenempfang anmelden. Nachdem sie das Empfangen einer Datensequenz best\u00e4tigt haben, wird diese beim Broker gel\u00f6scht, wodurch kein Replay der Daten mehr erfolgen kann. [44] <\/p>\n\n\n\n Eine deutlich geeignetere L\u00f6sung stellt hier Apache Kafka dar. Dabei handelt es sich um eine Plattform, die ausdr\u00fccklich f\u00fcr 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\u00f6rigen Daten, und der Key gibt die Partition an, auf der ein geordnetes Log gef\u00fchrt wird, in welchem die Nachrichten (Standortdaten) gespeichert werden. Somit k\u00f6nnen 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\u00fcgt werden k\u00f6nnen, ohne dass der Broker davon wissen muss. [45]<\/p>\n\n\n\n D. Map Index Updater<\/p>\n\n\n\n Das erste Ziel der Such\u00fcbersicht ist es, Fahrer im Umkreis des Kunden zu finden. Ein trivialer Ansatz w\u00fcrde die Abst\u00e4nde zwischen dem Kunden und allen Fahrern in dessen Region berechnen, wobei die relevanten Standortdaten \u00fcber das korrekte Kafka-Topic gefiltert werden k\u00f6nnten. Dies ist jedoch einerseits \u00fcberkorrekt, da die genaue Distanz nicht ben\u00f6tigt wird, sondern nur die Information, ob ein Fahrer in der N\u00e4he ist. Andererseits werden fast nie zwei Anfragen von exakt dem gleichen Standort gemacht, weshalb die Berechnungen nicht wiederverwendet werden k\u00f6nnen. <\/p>\n\n\n\n Aus diesen Gr\u00fcnden ist es vorteilhafter, bei Standorten nicht exakte Koordinatenpunkte, sondern Fl\u00e4chen zu verwenden. Diese Umwandlung geschieht durch einen Map Index Updater (siehe Schritt 2 in Abbildung 2). <\/p>\n\n\n\n Uber verwendet hierf\u00fcr das hierarchische Raumindex-System H3, welches die gesamte Erde in ein gleichm\u00e4\u00dfiges 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\u00e4chenform verwendet, da diese unregelm\u00e4\u00dfige Formen haben und potenziell mit der Zeit ver\u00e4ndert werden k\u00f6nnten und sich deshalb nicht f\u00fcr Kalkulationen eignen. Hexagons hingegen haben den Vorteil, dass ein gleichm\u00e4\u00dfiger Abstand zu allen Nachbarn gegeben ist.<\/p>\n\n\n\n Einer H3-Zelle werden Metriken wie verf\u00fcgbare 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\u00fchren w\u00fcrde, k\u00f6nnen folgende Funktionen angewendet werden:<\/p>\n\n\n\n In Abbildung 4 f\u00fchrt dies beispielsweise dazu, dass die zentrale Zelle mit Preismultiplikator 5 und deren Nachbarzellen aneinander angepasst werden. Somit k\u00f6nnen drastische Preisspr\u00fcnge vermieden werden, nur weil der Kunde sich einen Stra\u00dfenblock weiter bewegt. [46]<\/p>\n\n\n\n E. Map Matching<\/p>\n\n\n\n Ein Hindernis beim Nachverfolgen von Fahrern besteht darin, dass GPS-Daten zeitweise ungenau sind und Koordinaten beinhalten, die nicht auf Stra\u00dfen liegen. Diese Daten einfach zu \u00fcbernehmen h\u00e4tte eine negative Auswirkung auf die Benutzeroberfl\u00e4che, bspw. wenn ein Auto in einem Geb\u00e4ude angezeigt wird, und k\u00f6nnte zu Problemen bei der Routenberechnung f\u00fchren. Die haupts\u00e4chlichen Gr\u00fcnde f\u00fcr diese Ausrei\u00dfer sind gel\u00e4ndebedingt, wie etwa Stra\u00dfenschluchten zwischen hohen Geb\u00e4uden, bei denen das GPS-Signal von Fassaden reflektiert wird, bevor es den Empf\u00e4nger erreicht. [47, S. 337] Dieses Problem wird durch einen Map Matcher gel\u00f6st (siehe Schritt 3 in Abbildung 2), welcher GPS-Koordinaten auf die korrekte Stra\u00dfe abbildet. Dabei wird das sog. Hidden Markov Model (HMM) verwendet, bei dem neben der Entfernung zur n\u00e4chsten Stra\u00dfe auch der Kontext, also vorher und nachher gesendete Koordinaten, ausgewertet wird, um die korrekte Stra\u00dfe zu bestimmen. Das Map Matching wird auf zwei Ebenen angewandt: Ein niedrig-latenter Matcher l\u00e4sst die Fahrer nahezu in Echtzeit auf den Stra\u00dfen erscheinen, w\u00e4hrend ein Offline-Matcher das CATCHME-System mit Standortdaten f\u00fcttert. <\/p>\n\n\n\n CATCHME steht f\u00fcr “Catch Map Error” und wertet Routeninformationen aus, um das Uber-eigene Stra\u00dfensystem zu optimieren. Befinden sich wiederholt Daten am gleichen Punkt neben anstatt auf einer berechneten Route, so ist dies ein Zeichen daf\u00fcr, dass die eigentliche Stra\u00dfe neu gezeichnet werden muss. [48]<\/p>\n\n\n\n F. Standortspeicherung<\/p>\n\n\n\n F\u00fcr 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\u00e4lt und dadurch besonders schnelle Lese- \/Schreibzugriffe erm\u00f6glicht. [49] <\/p>\n\n\n\n Aufgrund der \u00fcberaus gro\u00dfen Datenmenge wird ein Sharding-Layer namens “Ringpop” eingesetzt, in welchem mehrere Redis-Server ringf\u00f6rmig angeordnet werden, wobei jedem Server ein fester Teilbereich der Fahrerdaten z.B. basierend auf geographischer Region zugeteilt wird [50], [51].<\/p>\n\n\n\n Falls ein Server ausf\u00e4llt oder entfernt wird, kommunizieren die Server untereinander \u00fcber 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\u00e4sst, kann gel\u00f6st werden, indem die Verbindung zum urspr\u00fcnglichen Server aufrechterhalten wird, und dieser die Daten einfach an den korrekten Server weiterleitet [50]. Durch das Replizieren von Daten auf mehreren Servern kann au\u00dferdem die Ausfalltoleranz erh\u00f6ht werden [50], [51].<\/p>\n\n\n\n G. Routing-Service<\/p>\n\n\n\n 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\u00fcr weitere Schritte wie Preisberechnung und Fahrer-Matching ben\u00f6tigt wird. Der klassische Ansatz, das Stra\u00dfennetz als Graphen zu modellieren, bei dem die ben\u00f6tigte 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\u00e4mlich nicht statisch, sondern \u00e4ndern 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\u00fcnglichen Routing-Engine-Sch\u00e4tzung und der tats\u00e4chlichen Fahrzeit angeben. Zum Beispiel erh\u00e4lt eine H3-Zelle mit einer Stra\u00dfenkreuzung, die wochentags um 7:10 Uhr stark frequentiert wird, f\u00fcr diesen Zeitrahmen ein Residual von +2 Minuten, welches in s\u00e4mtliche ETA-Berechnungen einflie\u00dft. [52]<\/p>\n\n\n\n H. Surge Pricing<\/p>\n\n\n\n F\u00fcr das Erf\u00fcllen von Auftr\u00e4gen sind manche Regionen f\u00fcr Fahrer attraktiver als andere. Innenst\u00e4dte bieten beispielsweise eine hohe Auftragsdichte, jedoch sind daf\u00fcr meist die Stra\u00dfen \u00fcberf\u00fcllter, Park- oder Haltegelegenheiten seltener und die Fahrtzeiten dadurch l\u00e4nger. 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\u00f6here Multiplikatoren gezielt Anreize f\u00fcr Fahrer in bestimmten Regionen setzt und die Fahrer dadurch gleichm\u00e4\u00dfig auf die Karte verteilt. [53] Damit Fahrer sich bereits im Voraus vorteilhaft positionieren k\u00f6nnen, m\u00fcssen diese Werte vorab berechnet werden. Weitere Faktoren, die zu einem hohen Preis-Multiplikator zu einer bestimmten Zeit an einem bestimmten Ort f\u00fchren, sind etwa Gro\u00dfevents oder schlechte Wetterbedingungen. [54]<\/p>\n\n\n\n I. Feature Store<\/p>\n\n\n\n Da komplexe Metriken wie ETA oder Preisindizes in Echtzeit die Latenz erh\u00f6hen w\u00fcrden, werden sie bereits im Vorfeld berechnet und in einem Feature Store gespeichert (siehe Schritt 7 in Abbildung 2). F\u00fcr die kontinuierliche Vorberechnung wird die Stream-Processing-Engine Apache Flink eingesetzt, welche zustandsbehaftete Berechnungen \u00fcber unbegrenzte Datenstr\u00f6me erm\u00f6glicht, d.h. Berechnungen, die auch Vergangenheitsdaten mit einbeziehen. [55] In diesem Fall flie\u00dfen 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 \u00dcbergang entsteht. Flink l\u00e4uft also als Rechenmaschine permanent im Hintergrund, und wenn eine Nutzeranfrage am System eingeht, so k\u00f6nnen dahinterliegende Services sofort auf die hier berechneten Daten zugreifen.<\/p>\n\n\n\n J. Matching Service<\/p>\n\n\n\n\n
\n
<\/a>III. RIDER-DRIVER MATCHING<\/strong><\/h3>\n\n\n\n
<\/a><\/a>\n
<\/a>\n
<\/a><\/a>