Dies ist ein Gastbeitrag von Ankit Sirmorya. Ankit arbeitet als Device Finding out Lead/Sr. Device Finding out Engineer bei Amazon und hat mehrere Device-Finding out-Initiativen im Amazon-Ökosystem geleitet. Ankit hat an der Anwendung von maschinellem Lernen gearbeitet, um mehrdeutige Geschäftsprobleme zu lösen und das Kundenerlebnis zu verbessern. Beispielsweise hat er eine Plattform zum Experimentieren mit verschiedenen Hypothesen auf Amazon-Produktseiten mithilfe von Reinforcement-Finding out-Techniken geschaffen. Derzeit ist er in der Alexa Buying groceries-Organisation tätig, wo er auf maschinellem Lernen basierende Lösungen entwickelt, um Kunden personalisierte Hinweise zur Nachbestellung zu senden, um deren Erfahrung zu verbessern.

Problemstellung

Entwerfen Sie eine standortbasierte soziale Suchanwendung ähnlich wie Tinder, die oft als Relationship-Carrier verwendet wird. Es ermöglicht Benutzern, eine Wischbewegung zu verwenden, um andere Benutzer zu mögen (nach rechts wischen) oder abzulehnen (nach hyperlinks wischen), und Benutzer können chatten, wenn sich beide Parteien mögen (ein „Fit“).

Anforderungen sammeln

Im Visier

Die Anwendung sollte in der Lage sein, die folgenden Anforderungen zu unterstützen.

  • Der Benutzer sollte in der Lage sein, sein Tinder-Profil zu erstellen, indem er seine Biografie hinzufügt und Fotos hochlädt.
  • Benutzer sollten in der Lage sein, Empfehlungen anderer Benutzer in geografisch nahen Regionen anzuzeigen.
  • Benutzer sollten andere empfohlene Benutzer mögen (nach rechts wischen) oder nicht mögen (nach hyperlinks wischen).
  • Benutzer sollten Benachrichtigungen erhalten, wenn sie mit anderen Benutzern übereinstimmen.
  • Benutzer sollten in der Lage sein, an einen anderen Ort zu wechseln und trotzdem Empfehlungen von Benutzern in der Nähe zu erhalten.

Außer Reichweite

  • Senden und Empfangen von Nachrichten von anderen Benutzern.

Design auf hohem Niveau

Die Architektur

Hinter dem Gateway wird es eine Flotte von Mikrodiensten geben, die die Benutzeranfragen bedienen. Der Profile Writer Carrier wird aufgerufen, wenn das Benutzerprofil erstellt wird. Dieser Dienst speichert die Benutzerinformationen in einer Datenbank und fügt den Benutzer dem entsprechenden Geo-Sharding-Index hinzu, sodass der Benutzer in Empfehlungen von Benutzern in der Nähe angezeigt wird. Dieser Index wird vom Empfehlungsdienst abgefragt, wenn er die Anforderung erhält, Empfehlungen für andere Benutzer zu generieren. Sobald der Benutzer beginnt, durch diese Empfehlungen zu wischen, empfängt der Swipes-Carrier diese Swipes und platziert sie in einem Datenstrom (z. B. AWS Kinesis/SQS). Es gibt eine Flotte von Workern, die Daten aus diesen Streams lesen, um Übereinstimmungen zu generieren. Die Employee tun dies, indem sie den LikesCache abfragen, um festzustellen, ob es sich um eine Übereinstimmung handelt. In diesem Fall wird die Übereinstimmungsbenachrichtigung mithilfe von Technologien wie WebSockets an beide Benutzer gesendet.

Komponentendesign

Erstellung von Benutzerprofilen

Das obige Sequenzdiagramm zeigt die Abfolge von Operationen, die ausgeführt werden, wenn ein Benutzer ein Profil auf Tinder erstellt. Innerhalb des synchronen Prozesses werden die Benutzermedien (z. B. Fotos) auf einen Dateiserver hochgeladen und die Benutzerinformationen einschließlich des Standorts des Benutzers werden in einem Schlüsselwertspeicher wie Amazon DynamoDB gespeichert. Außerdem wird dieser Benutzer zu einer Warteschlange hinzugefügt, um den Benutzer zu einem Geo-Sharding-Index hinzuzufügen.

Der asynchrone Prozess liest die Benutzerinformationen aus der Warteschlange und übergibt diese Informationen an den GeoShardingIndexer. Der Indexer verwendet Geobibliotheken wie die S2-Bibliothek von Google, um den Standort des Benutzers einem Geo-Shard zuzuordnen und den Benutzer dem mit diesem Shard verknüpften Index hinzuzufügen. Dies hilft dem Benutzer, in Empfehlungen anderer Benutzer in der Nähe zu erscheinen. In der Abbildung unten haben wir beispielsweise gezeigt, wie ein Benutzer aus Nordamerika dem entsprechenden Index zugeordnet wird, sodass der Benutzer in Empfehlungen von Benutzern in der Nähe angezeigt wird.

UserProfileInfo – Beispieldatenmodell

Wir haben unten ein JSON-Blob zum Speichern der Benutzerprofilinformationen gezeigt. Wir können einen Schlüsselwertspeicher wie Amazon DynamoDB oder Riak verwenden, um diese Daten zu verwalten.

{
    “userId”(PK) : “AWDGT567RTH”,
	“title” : “Julie”,
	“age” : 25,
	“gender” : “F”,
	“location”: {
		“latitude” : 
		“longitude” : 
        },
        “media”: {
	   “photographs”: [
		“https://mybucket.s3.amazonaws.com/myfolder/img1.jpg”,
		“https://mybucket.s3.amazonaws.com/myfolder/img2.jpg”,
		“https://mybucket.s3.amazonaws.com/myfolder/img3.jpg”
           ]
        },

    “recommendationPreferences”: {
	“ageRange”: {
	“min”: 21,
	“max”: 31
        },
       “radius”: 50
    }
}

Benutzerempfehlungen abrufen

Im vorherigen Abschnitt haben wir gesehen, wie Benutzer zum Geo-Sharding-Index hinzugefügt werden. Mal sehen, wie der Person in der Empfehlung anderer Person angezeigt wird. Wenn eine Benutzeranfrage bei der Advice Engine eingeht, leitet sie die Anfrage an den GeoShardedIndexer weiter. Der Indexer bestimmt die abzufragenden Geo-Shards basierend auf Benutzerstandort und -radius unter Verwendung von Geo-Bibliotheken wie Googles S2. Danach fragt der Indexer alle Geo-Sharding-Indizes (weitere Main points im nächsten Abschnitt) ab, die den von Google S2 zurückgegebenen Shards zugeordnet sind, um die Liste aller Benutzer in diesen Indizes abzurufen, und gibt diese Liste an die RecommendationEngine zurück. Die Engine wendet eine Filterung auf die Liste basierend auf Benutzerpräferenzen an und gibt die endgültige Liste von Empfehlungen an den Benutzer zurück.

Geo-Sharded-Index

Ein naiver Ansatz zur Verwaltung dieses Index wäre, einen Elasticsearch-Cluster mit einem Index und der Standardanzahl von Shards zu haben. Dieser Ansatz wird jedoch den Skalierungserwartungen, die eine Anwendung wie Tinder erfordert, nicht gerecht. Wir sollten die Tatsache nutzen, dass die Empfehlungen von Tinder ortsbezogen sind. Wenn wir beispielsweise einen Benutzer aus Indien bedienen, müssen wir die Benutzer in den USA nicht einbeziehen. Diese Tatsache kann genutzt werden, indem eine optimale Indexgröße für eine bessere Leistung beibehalten wird. Wir können die Indexgröße optimieren, indem wir die aktiven Benutzerdatensätze basierend auf ihren geografischen Standorten fragmentieren, sodass die Anzahl der aktiven Benutzer über die Shards hinweg ausgeglichen bleibt. Wir können das Gleichgewicht einer Geo-Sharding-Konfiguration mit N Shards durch die Standardabweichung der Anzahl aktiver Benutzer über die Shards hinweg darstellen, wie unten erwähnt.

    Stability(Shard1, Shard2,…, ShardN) = standard-deviation(Lively Person Depend of Shard1, Shard2,…, ShardN)

Die Geo-Sharding-Konfiguration mit der minimalen Standardabweichung wäre am besten ausbalanciert. Wir können Geo-Bibliotheken wie die S2-Bibliothek von Google verwenden, die auf der hierarchischen Zerlegung von Kugeln in „Zellen“ unter Verwendung von Quad-Timber basiert. Wir haben unten eine Visualisierung der generierten Geo-Sharding-Karte für unseren Anwendungsfall gezeigt. Aus der folgenden Grafik können wir schließen, dass Geo-Shards physisch näher und größer für Gebiete mit einer geringeren Anzahl aktiver Benutzer sind. In der Abbildung unten sind Shards beispielsweise auf Gewässern wie Meeren und Ozeanen größer, da sie nur Benutzer von einigen Inseln haben, jedoch sind Shards an Land kleiner. In der Abbildung unten sehen wir, dass Nordamerika drei Shards hat, aber ganz England und Grönland zusammen mit einem großen Teil des Atlantiks teilen sich aufgrund der geringeren Dichte aktiver Benutzer einen einzigen Shard.

Die S2-Bibliothek bietet zwei Hauptfunktionen: i) bei einem Standortpunkt (Breite, Länge) die S2-Zelle zurückgeben, die ihn enthält ii) bei einem Kreis (Breite, Länge, Radius) die S2-Zellen zurückgeben, die den Kreis bedecken. Jede S2-Zelle kann durch einen Geo-Shard dargestellt werden, der einem Index in unserem Gadget zugeordnet wird. Wenn ein Profil erstellt wird, wird der Benutzer zum Suchindex für diese entsprechende S2-Zelle hinzugefügt. Um Empfehlungen für einen Benutzer abzurufen, fragen wir die Indizes der nahe gelegenen S2-Zellen in Abhängigkeit vom Kreisradius ab, wie in der Abbildung unten gezeigt.

Abb: Abrufen von Empfehlungen für einen Benutzer von Shards in der Nähe (Bild: Tinder Engineering Weblog)

Swipes und Fits

Abb.: Ablauf von Person Swipes und Matching

In der obigen Abbildung haben wir die Abfolge von Operationen gezeigt, die ausgeführt wird, wenn ein Benutzer nach hyperlinks/rechts wischt. Der Swipes Inster verarbeitet die Swipes und fügt die linken Swipes in einen Movement ein, der diese Swipes in einem kostengünstigen Datenspeicher (z. B. Amazon S3) persistiert. Diese Linksbewegungen können für einige Anwendungsfälle zur Datenanalyse verwendet werden.

Andererseits werden die richtigen Swipes in einen separaten Movement gestellt und schließlich vom Matcher-Employee-Thread gelesen. Der Matcher-Employee-Thread liest die Likes-Nachricht aus dem Movement und prüft, ob der entsprechende Eintrag im LikesCache existiert. In der obigen Abbildung magazine beispielsweise Alice Bob und der Fit Employee prüft, ob ein Eintrag für Bob, der Alice magazine, im Cache vorhanden ist. Wenn sowohl Alice als auch Bob einander mögen, wird dies als Übereinstimmung bezeichnet, und eine Übereinstimmungsbenachrichtigung wird an beide Benutzer gesendet, die einen Server-Push-Mechanismus wie Websockets verwenden. Wenn Bob Alice noch nicht gemocht hat, wird ein Eintrag in den LikesCache für Alice gemacht, die Bob magazine.

Entspricht dem Datenmodell

Wir können einen Key-Worth-Speicher (z. B. Amazon DynamoDB) verwenden, um die Informationen über Übereinstimmungen (Benutzer mögen sich gegenseitig) zu speichern. Der für diesen Datenspeicher verwendete Hash-Schlüssel kann ein zusammengesetzter Schlüssel aus den eindeutigen Identifikatoren der Benutzer sein, die sich gegenseitig mochten. Der Wert im Datenspeicher enthält Metadateninformationen zur Übereinstimmung.

Benutzer wechselnde Standorte

Wenn ein Benutzer den Standort wechselt, möchten wir sicherstellen, dass wir dem Benutzer vom neuen Standort aus Empfehlungen geben und umgekehrt. Der Benutzerstandort wird auf den neuen Standort aktualisiert, sodass der aktualisierte Standort zum Abrufen von Empfehlungen für den Benutzer verwendet wird. Darüber hinaus aktualisieren wir auch den Index, der dem neuen Standort des Benutzers zugeordnet ist, mit den Benutzerinformationen, sodass der Benutzer in Empfehlungen am Standort angezeigt wird. Dieser Prozess wird asynchron ausgeführt.

Der elastische Suchcluster (unten erklärt), der die Geo-Sharding-Indizes enthält, liest die Nachricht aus einer Warteschlange, um den Index des Benutzers zu aktualisieren. Die Koordinationsknoten für die elastische Suche verschieben die Informationen des Benutzers von dem Index, der dem alten Standort des Benutzers zugeordnet ist, zu dem Index, der dem neuen Standort des Benutzers zugeordnet ist. Dadurch wird sichergestellt, dass der Benutzer in Empfehlungen anderer Benutzer am neuen Standort angezeigt wird.

Elastischer Suchcluster

Der Cluster besteht aus mehreren Grasp-Knoten mit jeweils zwei Auto-Scaling-Gruppen (ASG), eine enthält nur koordinierende Knoten (hier werden alle Anfragen gesendet) und eine andere enthält alle Datenknoten. Jeder Datenknoten enthält eine bestimmte Anzahl von Indizes (Kombination aus primären und Replikaten) von zufällig verteilten Shards. Für jede Benutzerabfrage ist der koordinierende Knoten dafür verantwortlich, die Datenknoten der Ziel-Shards abzufragen, um die Benutzerabfrage zu bearbeiten. Wir erhöhen die Zuverlässigkeit und Robustheit des elastischen Suchclusters, indem wir die Benutzerdaten anhand ihrer geografischen Standorte fragmentieren und Repliken dieser Shards erstellen.

Optimierung

Einer der wichtigsten Aspekte einer Anwendung wie Tinder sind die Empfehlungen (potenzielle Übereinstimmungen), die sie einem Benutzer bietet. In einem der obigen Abschnitte haben wir gesehen, wie wir Empfehlungen für einen Benutzer generieren, indem wir Indizes abfragen, die den nahe gelegenen Geo-Shards eines Benutzers entsprechen. Wir können das Gadget optimieren, indem wir maschinelles Lernen anwenden, um die Empfehlungen zu ordnen. Das maschinelle Lernmodell optimiert das Potenzial des Benutzers, empfohlene potenzielle Übereinstimmungen mit der rechten Maustaste zu streichen. Wir haben unten einige der Funktionen aufgelistet, die sich auf die Entscheidung des Benutzers auswirken können, nach hyperlinks oder rechts zu streichen.

  • Demografische Daten der Benutzer: Adjust, Geschlecht, Rasse, Ort, Beruf und so weiter
  • Tinder-Verlaufsdaten des Benutzers: Wischen Sie nach hyperlinks, Wischen Sie nach rechts, Historische Geo-Standorte, Tägliche Nutzungszeit
  • Extrahierte Informationen aus der Biografie des Benutzers: Vorlieben, Abneigungen, Vorlieben
  • Extrahierte Informationen aus Benutzerbildern: Gesichtszüge, Haarfarbe, Körpertyp

Wir können ein Regressionsproblem formulieren, indem wir diese Funktionen verwenden, um die Wahrscheinlichkeit zu ermitteln, dass der Benutzer eine Empfehlung nach rechts wischt. Wir können dann Algorithmen wie die logistische Regression nutzen, um diese Wahrscheinlichkeiten zu berechnen, die für das Score der Empfehlungen verwendet werden. Darüber hinaus können wir auch den Mechanismus zum Senden von Übereinstimmungsbenachrichtigungen an Benutzer optimieren, indem wir die Informationen vorab abrufen, dass ein Benutzer von einem empfohlenen Benutzer nach rechts geswiped wurde. Indem wir diese Informationen vorab abrufen, können wir den Benutzer sofort über eine Übereinstimmung benachrichtigen (falls und wenn sie auftritt) und somit den Netzwerkaufruf verhindern. Wenn beispielsweise Alice in Bobs Empfehlung angezeigt wird und Alice Bob bereits richtig gewischt hat, erhält Bob eine sofortige Übereinstimmungsbenachrichtigung (ohne Netzwerksprung), falls Bob Alice auch richtig wischt.

Verweise

  • https://medium.com/tinder-engineering/geosharded-recommendations-part-1-sharding-approach-d5d54e0ec77a
  • https://medium.com/tinder-engineering/geosharded-recommendations-part-2-architecture-3396a8a7efb
  • https://medium.com/tinder-engineering/geosharded-recommendations-part-3-consistency-2d2cb2f0594b
  • https://medium.com/tinder-engineering/taming-elasticache-with-auto-discovery-at-scale-dc5e7c4c9ad0
  • https://medium.com/tinder-engineering/how-we-improved-our-performance-using-elasticsearch-plugins-part-1-b0850a7e5224
  • https://medium.com/tinder-engineering/how-we-improved-our-performance-using-elasticsearch-plugins-part-2-b051da2ee85b
  • https://www.youtube.com/watch?v=Lq4aNihcS8A
  • https://www.youtube.com/watch?v=8zh4iUNFjKc
  • https://www.youtube.com/watch?v=o3WXPXDuCSU

https://aspiringsysadmin.com/