Die Vorteile unvollkommener Systeme: Blueskys verlustbehaftete (lossy) Timeline

• Bei der Systementwicklung ist es praktisch kaum möglich, perfekte Konsistenz, Verfügbarkeit, niedrige Latenz und hohen Durchsatz gleichzeitig zu erreichen
  • Wichtig ist, eine geeignete Architektur zu finden, indem man den richtigen Kompromiss für die jeweilige Anwendung bestimmt
• Beim Design des Following-Feeds bzw. der Timeline von Bluesky wurde ein Trade-off gewählt, bei dem zugunsten besserer Schreibleistung teilweise auf Konsistenz verzichtet wird
  • Dadurch sank die P99-Latenz um mehr als 96 %, ohne die Nutzer spürbar negativ zu beeinträchtigen

Fanout der Timeline

• Wenn ein Nutzer bei Bluesky einen Beitrag veröffentlicht, wird dieser vom System indexiert, in der Datenbank gespeichert und über API-Antworten bereitgestellt
• Gleichzeitig durchläuft der Beitrag einen „Fanout“-Prozess, bei dem er in die Timeline-Tabelle jedes einzelnen Followers eingefügt wird
• Dazu wird zunächst die Follower-Liste abgefragt und anschließend in jede Timeline-Tabelle der Follower in umgekehrter Reihenfolge eingefügt
• Die Timeline-Tabellen sind pro Nutzer partitioniert, werden in der verteilten Datenbank ScyllaDB gespeichert und zur hohen Verfügbarkeit über mehrere Shards repliziert
  • Jeder Nutzer kann einem anderen Shard zugewiesen sein
• Um Speicherplatz zu sparen, werden bei Timelines, die eine bestimmte Länge überschreiten, ältere Beitragsreferenzen regelmäßig gelöscht

Das Hot-Shard-Problem

• Bluesky hat rund 32 Millionen Nutzer, und die Timeline-Datenbank ist in Hunderte von Shards aufgeteilt
• In einem System mit Millionen von Nutzern kann es einzelne Nutzer mit extrem vielen Following-Beziehungen geben
  • Beispiel: Nutzer, die Hunderttausenden Accounts folgen
• In einem Shard werden die Timelines vieler Nutzer gemeinsam gespeichert
• Wenn ein bestimmter Nutzer extrem viele Schreibvorgänge auslöst, wird der betreffende Shard überlastet und zu einem „Hot Shard“
• Solche Hot Shards bündeln Schreib- oder Leseoperationen, wodurch sich die Latenz auch auf andere Nutzer im selben Shard ausbreitet

Aufsummierte Latenz

• Hat ein Nutzer 2.000.000 Follower, kann das Schreiben bei sequenzieller Verarbeitung mehr als 20 Minuten dauern
• Durch Parallelisierung des Fanouts sinkt zwar die durchschnittliche Latenz
• Allerdings können P99-Latenzen (etwa ab 15 Millisekunden) vielfach auftreten und so den gesamten parallelen Job verzögern
• Bei sehr vielen Followern kann die gesamte Fanout-Zeit durch P99- oder P99.9-Latenzen im schlechtesten Fall auf mehrere Minuten bis hin zu Dutzenden Minuten anwachsen

Verlustbehaftete (lossy) Timelines

• Für Nutzer, die einer übermäßig großen Zahl von Accounts folgen, ist es praktisch unmöglich, alle Beiträge exakt in Reihenfolge anzuzeigen
• Auch realistisch betrachtet kann ein Mensch ohnehin nicht alle diese Beiträge konsumieren
• Deshalb wurde für Timelines von Nutzern, deren Zahl an Followings einen bestimmten Schwellenwert überschreitet (z. B. reasonable_limit), ein Verfahren eingeführt, bei dem ein Teil der Schreibvorgänge probabilistisch „gedroppt“ wird
• Verwendet wird die Formel loss_factor = min(reasonable_limit / num_follows, 1)
• Beim Fanout wird ein Zufallswert erzeugt; ist er größer als loss_factor, wird der Timeline-Schreibvorgang ausgelassen
• So lassen sich übermäßige Schreibvorgänge auf einzelne Nutzer-Timelines begrenzen und Leistungseinbrüche des gesamten Shards vermeiden

Zum Caching

• Da pro Sekunde mehr als eine Million Timeline-Schreibvorgänge anfallen, würde es enorme Last verursachen, bei jedem Schreibvorgang die Zahl der Followings direkt aus der Datenbank abzufragen
• Stattdessen werden Accounts mit hoher Following-Zahl in Redis als Sorted Set zwischengespeichert
• Die Fanout-Service-Instanzen laden diese Cache-Informationen alle 30 Sekunden in den Arbeitsspeicher
• Dadurch lassen sich Informationen über Nutzer mit vielen Followings auch während des Fanout-Prozesses schnell abrufen
• Da diese Cache-Daten nicht perfekt aktuell sein müssen, wird ein gewisses Maß an Unvollkommenheit akzeptiert, um Performance und Skalierbarkeit zu erhöhen

Ergebnis

• Nach Einführung der lossy Timelines verschwanden Hot Shards in der Timelines-Datenbank praktisch vollständig
• Die P99-Latenz für die Verarbeitung einer Fanout-Seite sank um mehr als 90 %
• Betrachtet man die gesamte Fanout-Verarbeitungszeit, verkürzten sich Jobs, die im P99-Fall 5 bis 10 Minuten dauerten, auf unter 10 Sekunden
• Das zeigt, dass selbst bei teilweisem Verzicht auf Konsistenz die Erwartungen der Nutzer erfüllt und zugleich Skalierbarkeit im großen Maßstab erhalten werden kann
• Auch wenn die Timeline-Architektur von Bluesky weiterhin Verbesserungspotenzial hat, wurden durch diese Änderung Schreibdurchsatz und Skalierbarkeit deutlich verbessert

[GN⁺]

Hacker-News-Kommentare

• Als Systemliebhaber mag ich solche Artikel. Man verfällt leicht in die Denkweise, dass "es perfekt sein muss"

  • Beim Backend der Suchmaschine Blekko wurde ein "eventually consistent" Index aufgebaut. Das liefert Updates schneller an die Nutzer aus, aber zwei Nutzer mit derselben Query können leicht unterschiedliche Ergebnisse bekommen
  • Hier kommt viel Systemtheorie zum Einsatz, und bei positivem Feedback kann es zu Schwingungen kommen. Bei Suchmaschinen erzeugt ein Ranker, der Links höher gewichtet, auf die Nutzer klicken, positives Feedback
  • Es war wichtig, das System "kritisch gedämpft" zu halten. Dadurch konvergiert es schnell
  • Die Art, wie die Timelines der Nutzer geshardet sind und Feedback-Schleifen haben (z. B. "Likes" oder "Reposts"), wirkt wie ein interessanter Problemraum

• Ich frage mich, warum die Timeline nicht hybrid nach Popularität des Accounts umgesetzt wird

  • Bei Promi-Accounts wäre es günstiger, Beiträge der Prominenten beim Ausliefern der Follower-Timeline abzurufen und einzumischen, statt jede Nachricht an Millionen von Followern zu verteilen
  • Wenn Millionen von Followern das so machen, wäre es billig, das nur lesend aus einem Hot Cache zu holen

• Eine interessante Lösung für ein interessantes Problem. Danke fürs Teilen

  • Ich hatte Schwierigkeiten, den Übergang des Autors von "Promi" zu "Bot" zu verstehen
  • Es wirkte, als würde der Autor mit der "Lossy Timeline" ein völlig anderes Konzept einführen

• Ich bin neugierig auf diese Strategie, bei der Konsistenz geopfert wird. Ich frage mich, ob es Überlegungen zu anderen Ansätzen gab, die weder vollständiges Fan-out beim Lesen noch beim Schreiben sind

  • Statt in die Timeline jedes Nutzers zu schreiben, stelle ich mir vor, pro Shard nur einmal zu schreiben, sofern dort mindestens ein Follower ist
  • Beim Lesen würde man den Content für den jeweiligen Nutzer holen und nach den tatsächlichen Followern filtern
  • Da die Lesevorgänge innerhalb des Shards stattfinden, wäre die Latenz gering
  • Bei Mega-Followern würde die Seite keine veralteten Einträge sehen

• Es ist nicht nötig, jedem Nutzer alles, was Tausende von Accounts posten, perfekt chronologisch zu zeigen, solange genug Content da ist, damit die Timeline immer frisch wirkt

  • Die Lösung wirkte nicht wie eine unvollkommene zeitliche Reihenfolge, sondern eher so, als würden Posts im Feed fehlen

• Ich frage mich, wie es funktionieren würde, die Zahl der Follower zu begrenzen, um das Hot-Shard-Problem zu vermeiden

  • Jeder Nutzer hätte pro 1000 Follower eine eigene Timeline, und der Client würde sie zusammenführen
  • Falls nötig, könnte man nur Teile der tatsächlichen Timeline laden, um den lossy Teil umzusetzen

• AWS hat dafür einen coolen allgemeinen Ansatz

  • Jeder Nutzer wird mehreren Shards zugewiesen, damit es unwahrscheinlicher wird, dass andere Nutzer alle Shards teilen
  • Hätte man von Anfang an Shuffle Sharding eingesetzt, hätte man neue Probleme lösen können, ohne viele andere Nutzer zu beeinträchtigen

• Ein Account, der Hunderttausenden Nutzern folgt, ist offensichtlich ein Bot-Account zum Scrapen von Content. Ich würde ihn einfach blockieren und damit ist es erledigt

  • Ich lese gern über technische Herausforderungen. Twitter hat eine spezielle Architektur für Prominente mit Millionen von Followern
  • Wenn Bluesky ein ähnlicher Klon ist, frage ich mich, warum man dem nicht gefolgt ist

• Wenn ich direkt auf das Profil eines Nutzers gehe und alle Posts sehe, fehlen dort manchmal Beiträge, die in der Timeline hätten sein sollen

  • Das erklärt, warum ich bei Bluesky trotz weniger als 100 gefolgten Nutzern gelegentlich Posts von jemandem nicht in meiner Timeline sehe

• Ich frage mich, warum das Fan-out so implementiert wurde, dass jede "Seite" das Holen der nächsten Seite blockiert

  • Die Aktivität zum Holen von Seiten sollte Follower fortlaufend holen und nicht warten müssen, bis alle Einträge einer Seite aktualisiert sind
  • Mir kommt in den Sinn, eine Fetch-Komponente zu haben, die Seiten holt, in S3 speichert und Metadaten samt S3-Position in eine Queue (SQS) publiziert
  • In so einem System ließe sich die Parallelität besser steuern, und man könnte Aufgaben durch Partitionierung in der Queue mit dem Shard als Schlüssel "verlangsamen"