Wie Discord mit einem einzigen Server 2 Millionen gleichzeitige Nutzer bedient

Elixir als Fanout-System

• Immer wenn auf Discord etwas passiert – etwa wenn eine Nachricht gesendet wird oder jemand einem Sprachkanal beitritt –, muss die UI in den Clients aller online befindlichen Nutzer aktualisiert werden, die sich auf demselben Server befinden (auch „Guild“ genannt).
• Dafür wird pro Guild ein Elixir-Prozess als zentraler Routing-Punkt für alle Ereignisse auf diesem Server verwendet, und für den Client jedes verbundenen Nutzers ein separater Prozess („Session“).
• Der Guild-Prozess verfolgt die Sessions der Nutzer, die Mitglied dieser Guild sind, und ist dafür zuständig, Aufgaben an diese Sessions zu verteilen.
• Wenn eine Session ein Update erhält, wird es über die WebSocket-Verbindung an den Client weitergeleitet.
• Manche Aktionen gelten für alle Personen auf dem Server, während bei anderen Berechtigungen geprüft werden müssen. Dafür muss man nicht nur Informationen über Rollen und Kanäle des Servers kennen, sondern auch die Rollen des jeweiligen Nutzers.
• Das Aktivitätsvolumen einer Guild ist proportional zur Zahl der Personen auf diesem Server, und auch der Arbeitsaufwand, der nötig ist, um eine einzelne Nachricht per Fanout zu verteilen, ist proportional zur Zahl der online befindlichen Nutzer auf diesem Server.
  • Das heißt: Der Arbeitsaufwand, der zur Verarbeitung eines Discord-Servers nötig ist, wächst mit der Größe des Servers in der vierten Potenz.
  • Wenn auf einem Server 1.000 Personen online sind und jede einmal „Ich mag Gelee“ sagt, müssen 1 Million Benachrichtigungen verarbeitet werden.
  • Bei 10.000 Personen entstehen 100 Millionen Benachrichtigungen, bei 100.000 Personen müssen 10 Milliarden Benachrichtigungen zugestellt werden.
• Zusätzlich zum generellen Durchsatzproblem werden einige Operationen langsamer, je größer der Server wird.
• Damit ein Server reaktionsschnell wirkt – also andere eine gesendete Nachricht sofort sehen können oder jemand nach dem Beitritt zu einem Sprachkanal direkt teilnehmen kann –, müssen fast alle Operationen schnell verarbeitet werden.
• Wenn die Verarbeitung teurer Operationen mehrere Sekunden dauert, leidet die User Experience.
• Wie konnte Discord trotz dieser Probleme den Midjourney-Server unterstützen, der mehr als 10 Millionen Mitglieder hat, von denen ständig über 1 Million online sind?
  • Zunächst war es wichtig, die Leistung des Systems zu verstehen.
  • Nachdem die Daten vorlagen, suchte man nach Möglichkeiten, sowohl den Durchsatz als auch die Reaktionsfähigkeit zu verbessern.

Systemleistung verstehen

• Wall time analysis:
  • Stack Tracing mit Process.info(pid, :current_stacktrace)
  • Die Event-Processing-Loop wurde gemessen, um für jeden Nachrichtentyp die Anzahl empfangener Nachrichten sowie minimale/maximale/durchschnittliche/gesamte Verarbeitungszeit zu protokollieren.
  • Operationen, die weniger als 1 % der Gesamtzeit ausmachen, wurden ignoriert, außer in extremen Lastspitzen.
  • So ließen sich günstige Operationen ausblenden und die teuersten hervorheben.
• Process Heap Memory Analysis
  • Ebenso wichtig war es zu verstehen, wie der Speicher genutzt wird.
  • Statt jedes einzelne Element anzusehen, wurde eine Helper-Library geschrieben, die große Maps und Listen (keine Structs) sampelt und daraus eine geschätzte Speichernutzung erzeugt.
  • Diese Library half nicht nur dabei, die GC-Performance zu verstehen, sondern auch Felder zu identifizieren, auf die sich Optimierungen lohnen, sowie solche, die letztlich irrelevant sind.
• Nachdem klar war, wo der Guild-Prozess seine Zeit verbringt, konnten Strategien entwickelt werden, damit der Guild-Prozess nicht zu 100 % ausgelastet ist.
  • In manchen Fällen reichte es, eine ineffiziente Implementierung effizienter neu zu schreiben.
  • Aber damit kam man nur bis zu einem gewissen Punkt; es waren grundlegendere Änderungen nötig.

Passive Sessions – unnötige Arbeit vermeiden

• Eine der besten Methoden, einen Durchsatz-Bottleneck zu entschärfen, ist es, die Arbeit zu reduzieren.
• Ein Ansatz dafür war, die Anforderungen der Client-Anwendung zu berücksichtigen.
• In der ursprünglichen Topologie erhielten alle Nutzer jede sichtbare Aktion aus allen Guilds, denen sie angehörten.
• Einige Nutzer gehören jedoch zu mehreren Guilds und klicken möglicherweise nicht einmal in bestimmte Guilds hinein, um zu sehen, was dort passiert.
• Was wäre, wenn man nicht alles sendet, bis der Nutzer tatsächlich hineinklickt? Dann müsste man nicht für jede Nachricht einzeln Berechtigungen prüfen, und entsprechend würde auch viel weniger Daten an den Client gesendet.
• Discord nannte dies eine „Passive“-Verbindung und hielt sie in einer separaten Liste gegenüber „Active“-Verbindungen, die alle Daten empfangen müssen.
• Das Ergebnis: Auf großen Servern waren etwa 90 % der Nutzer-Guild-Verbindungen passive Verbindungen, wodurch die Kosten der Fanout-Arbeit um 90 % sanken.
• Das verschaffte etwas Luft, aber mit weiterem Wachstum der Community reichte auch das natürlich nicht aus.
  (Wenn sich das Arbeitsvolumen um den Faktor 10 verringert, ergibt sich bei maximaler Community-Größe ungefähr ein Vorteil um den Faktor 3.)

Relays – Fanout über mehrere Maschinen aufteilen

• Eine Standardtechnik zur Skalierung über die Durchsatzgrenze eines einzelnen Kerns hinaus besteht darin, die Arbeit auf mehrere Threads aufzuteilen (oder, in Elixir-Terminologie, Prozesse).
• Auf Basis dieser Idee wurde zwischen Guild und Nutzer-Session ein System namens „Relay“ aufgebaut.
• Statt die gesamte Arbeit zur Verarbeitung von Sessions in einem einzigen Prozess zu erledigen, wurde sie auf mehrere Relays verteilt. So konnte eine einzelne Guild mehr Ressourcen nutzen, um große Communities zu bedienen.
• Einige Aufgaben mussten weiterhin im Haupt-Guild-Prozess ausgeführt werden, aber damit ließ sich eine Community mit Hunderttausenden Mitgliedern verarbeiten.
• Für die Umsetzung musste identifiziert werden, welche wichtigen Aufgaben auf dem Relay laufen sollten, welche auf der Guild bleiben mussten und welche in beiden Systemen ausgeführt werden konnten.
• Nachdem klar war, was benötigt wurde, begann das Refactoring, um Logik auszulagern, die zwischen den Systemen geteilt werden konnte.
  • Ein Großteil der Logik dafür, wie Fanout ausgeführt wird, wurde beispielsweise in eine Library refaktoriert, die sowohl von Guild als auch von Relay verwendet wird.
  • Für einen Teil der Logik, der sich nicht so teilen ließ, waren andere Lösungen nötig. Das Management von Sprachstatus wurde im Wesentlichen so umgesetzt, dass das Relay mit minimalen Änderungen alle Nachrichten an die Guild proxyt.
• Eine interessante Designentscheidung beim ersten Release der Relays war, den vollständigen Mitgliederbestand in den Zustand jedes Relays aufzunehmen.
  • Das war hinsichtlich der Einfachheit eine gute Entscheidung, weil alle benötigten Mitgliederinformationen verfügbar waren.
  • Aber bei einer Midjourney-Größe mit Millionen Mitgliedern ergab dieses Design zunehmend weniger Sinn.
• Es wurden nicht nur Dutzende Kopien von Informationen zu zig Millionen Mitgliedern im RAM gehalten; um ein neues Relay zu erzeugen, mussten außerdem alle Mitgliederinformationen serialisiert und an das neue Relay übertragen werden, was zu Verzögerungen von mehreren Dutzend Sekunden in der Guild führte.
• Um dieses Problem zu lösen, wurde Logik ergänzt, mit der Relays nur die Mitglieder identifizieren, die sie tatsächlich zum Funktionieren benötigen – und das war nur ein sehr kleiner Teil aller Mitglieder.

Server-Reaktionsfähigkeit erhalten

• Neben dem Einhalten der Durchsatzgrenzen musste auch die Reaktionsfähigkeit des Servers erhalten bleiben.
• Auch hier war es hilfreich, Zeitmessdaten zu betrachten.
• Effektiver war es, sich stärker auf Operationen mit langer Dauer pro Aufruf zu konzentrieren als auf die Gesamtdauer.
• Worker-Prozesse + ETS
  • Einer der größten Gründe für mangelnde Reaktionsfähigkeit waren Operationen, die auf der Guild laufen und über alle Mitglieder iterieren müssen.
  • Das kommt selten vor, passiert aber durchaus. Wenn etwa jemand @everyone pingt, muss bekannt sein, welche Personen auf dem Server diese Nachricht sehen können.
  • Solche Prüfungen können jedoch mehrere Sekunden dauern. Wie lässt sich das handhaben?
  • Ideal wäre es, diese Logik auszuführen, während die Guild andere Aufgaben weiterbearbeitet. Elixir-Prozesse teilen Speicher aber nicht besonders gut, daher war eine andere Lösung nötig.
  • Eines der Werkzeuge in Erlang/Elixir, mit dem sich Daten in gemeinsam zugreifbarem Speicher ablegen lassen, ist ETS.
  • Das ist eine In-Memory-Datenbank, die Funktionen für sicheren Zugriff durch mehrere Elixir-Prozesse unterstützt.
  • Sie ist weniger effizient als der Zugriff auf Daten im Prozess-Heap, aber immer noch sehr schnell. Außerdem verringert sie durch kleinere Prozess-Heaps die Latenz der Garbage Collection.
  • Es wurde entschieden, eine hybride Struktur zur Speicherung der Mitgliederliste zu bauen:
    • Die Mitgliederliste wird in ETS gespeichert, damit auch andere Prozesse sie lesen können; gleichzeitig werden jüngste Änderungen (Einfügen, Aktualisieren, Löschen) zusätzlich im Prozess-Heap gehalten.
    • Da die meisten Mitglieder nicht ständig aktualisiert werden, ist die Menge der jüngsten Änderungen nur ein sehr kleiner Teil der gesamten Mitgliederbasis.
  • Nun konnten mit den Mitgliedern in ETS Worker-Prozesse erzeugt und ihnen bei teuren Operationen die Kennung der ETS-Tabelle übergeben werden, auf der sie arbeiten sollen.
  • Die Worker-Prozesse können dann den teuren Teil übernehmen, während die Guild andere Aufgaben fortsetzt. Es wird auch auf eine einfache Möglichkeit hingewiesen, dies umzusetzen (im Original mit Code-Snippet).
  • Ein Beispiel für den Einsatz ist die Übergabe eines Guild-Prozesses von einer Maschine auf eine andere (typischerweise für Wartung oder Deployment).
  • Dabei wird auf der neuen Maschine ein neuer Prozess zur Verarbeitung der Guild erzeugt, dann der Zustand des alten Guild-Prozesses in den neuen kopiert, alle verbundenen Sessions wieder mit dem neuen Guild-Prozess verbunden und anschließend der währenddessen aufgelaufene Backlog verarbeitet.
  • Mit Worker-Prozessen kann der Großteil der Mitgliederdaten – möglicherweise mehrere GB – übertragen werden, während der bestehende Guild-Prozess weiterarbeitet. So lassen sich die Verzögerungen von mehreren Minuten bei jeder Handover deutlich reduzieren.
• Manifold-Offload
  • Eine weitere Idee zur Verbesserung der Reaktionsfähigkeit und zum Überwinden von Durchsatzgrenzen war, Manifold zu erweitern und für den Fanout auf den Empfängerknoten separate „Sender“-Prozesse zu verwenden, statt den Fanout im Guild-Prozess selbst auszuführen.
  • Dadurch reduziert sich nicht nur die Arbeit des Guild-Prozesses; es schützt auch vor dem Backpressure des BEAM, wenn eine der Netzwerkverbindungen zwischen Guild und Relay vorübergehend einen Rückstau hat (BEAM ist die virtuelle Maschine, auf der Elixir-Code läuft).
  • Theoretisch schien das leicht lösbar, doch beim Testen dieser Funktion – „Manifold-Offload“ genannt – zeigte sich leider, dass die Performance tatsächlich deutlich schlechter wurde.
  • Wie konnte das sein? Theoretisch wurde die Arbeitsmenge doch kleiner – warum war der Prozess dann stärker ausgelastet?
  • Eine genauere Untersuchung zeigte, dass der Großteil der zusätzlichen Arbeit mit Garbage Collection zusammenhing.
  • Hier erwies sich die Funktion erlang.trace als Rettung.
  • Damit konnten bei jeder Garbage Collection des Guild-Prozesses Daten gesammelt werden, was nicht nur Einblick in die Häufigkeit der Garbage Collection gab, sondern auch darin, was sie ausgelöst hatte.
  • Auf Basis dieser Trace-Informationen und eines Blicks in den Garbage-Collection-Code von BEAM stellte sich heraus, dass bei aktiviertem Manifold-Offload der Auslöser für Major GC (Full GC) der virtuelle Binär-Heap war.
  • Der virtuelle Binär-Heap ist eine Funktion, die dafür gedacht ist, Speicher freizugeben, der von Strings belegt wird, die nicht im Prozess-Heap gespeichert sind – auch dann, wenn der Prozess eigentlich keine Garbage Collection bräuchte.
  • Leider bedeutete das Nutzungsmuster hier, dass fortlaufend Garbage Collection ausgelöst wurde, um einige hundert KB Speicher freizugeben – zum Preis des Kopierens eines mehrere GB großen Heaps. Das war ganz offensichtlich kein sinnvoller Trade-off.
  • Glücklicherweise lässt sich dieses Verhalten im BEAM mit dem Prozess-Flag min_bin_vheap_size anpassen.
  • Nachdem dieser Wert auf einige MB erhöht worden war, verschwand das pathologische Garbage-Collection-Verhalten, und mit aktiviertem Manifold-Offload zeigte sich eine deutliche Performance-Verbesserung.

[roxie]

Elixir, weiter so!

[arfwene]

Passive Sessions sind technisch gesehen nichts Besonderes, wirken aber wie eine gute Idee.
Damit lässt sich die Last sicher deutlich reduzieren.

Nicht nur Discord, sondern vermutlich auch andere Dienste werden so eine Funktion implementiert haben; ich frage mich, worin sich die Unterschiede je nach Service zeigen.

[mhj5730]

Wirklich beeindruckend.

[abhidhamma]

In letzter Zeit scheint das Endziel des inzwischen bekannten Streaming SSR von Next.js ebenfalls das Phoenix-Framework von Elixir zu sein. In vielerlei Hinsicht scheint Elixir an der vordersten Front moderner Programmiersprachen zu stehen.

[papillon]

Elixir, weiter so!

[n1ghtc4t]

Vor einigen Jahren habe ich mich auf den Technik-Blog von Discord bezogen und Elixir für einen Echtzeitdienst eingeführt. Mit der Entwicklungsgeschwindigkeit und Stabilität waren sowohl ich als auch die verantwortlichen Führungskräfte sehr zufrieden, und wir konnten den Service erfolgreich starten — daran habe ich viele gute Erinnerungen.

[kotlinc]

Ich hoffe, dass Elixir populärer wird.

[damtet]

Heutzutage scheint es nicht mehr so sehr Naver-Kakao-Line-Coupang zu sein; eher haben mittelständische Startups offenbar ein Spring-Monopol. Das liegt wohl daran, dass diese Startup-Manager meist selbst auf Spring spezialisiert sind.

Jede Ineffizienz lässt sich mit Geld und Größenordnung lösen. Die Unternehmen wissen es ja ohnehin nicht besser.