Schlagwort-Archive: Besucher

Paradigmenwechsel: High Performance Webanwendungen

Ich programmiere schon seit einiger Zeit Webanwendungen. Selten stieß ich dabei auf irgendwelche Performanzgrenzen. Dynamische Webanwendungen sind vom Prinzip her ziemlich simpel gestrickt:

  1. Die Webanwendung erhält eine Anfrage
  2. Die Anwendung holt sich z.B. Daten aus der Datenbank, um die Anfrage beantworten zu können
  3. Die Webanwendung bereitet die Daten auf und gibt sie als HTML aus, die der Browser hübsch dem Benutzer anzeigt

Das gute, alte EVA-Prinzip: Eingabe, Verarbeitung, Ausgabe

Bei Servern, die nicht sonderlich viele Anfragen erhalten, ist das ein bewertes Prinzip. Ein schon etwas in die Jahre gekommener 1-Kern-Webserver konnte beispielsweise locker 5.000 Besucher am Tag bedienen. Nimmt die Anfragefrequenz einer Webseite jedoch weiter zu, muss man sich etwas überlegen. Eine Möglichkeit ist, sich weitere Server anzumieten, um bestimmte Aufgaben auszugliedern – z.B. ein eigener Datenbankserver.

Man kann auch aufs Cachen setzen: Anstatt bei jeder Anfrage die gleichen Berechnungen durchzuführen und auf die DB zuzugreifen, speichert man das Ergebnis oder die auszugebende Seite im Arbeitsspeicher zwischen, so dass sie von dort ohne teure CPU-Zeit und merklich schneller ausgegeben werden kann.

Und wenn diese Maßnahmen nicht mehr ausreichen? Was dann?

Vor genau diesem Problem stand Steve Huffman bei reddit, die monatlich 270 Millionen Anfragen erhielten. In folgendem Vortrag spricht er über die sieben Lehren aus der Zeit bei reddit (eine Transkription gibt es bei ThinkVitamin):

Lessons Learned while at Reddit from Carsonified on Vimeo.

Neben dem „Open Schema“ (oder Entity-Attribute-Value-Model) der Datenbankstruktur finde ich das Zusammenspiel zwischen Anwendung, Cache und Datenbank äußerst interessant. Sämtliche Inhalte von reddit liegen im Cache und sind vorberechnet, sodass die Inhalte ohne Berechnungen angezeigt werden können. Werden Inhalte verändert – etwa Upvote für ein Link, wird der Cache zur Anzeige der höheren Bewertung angelegt, sodass der Benutzer sofort die Rückmeldung bekommt, dass sein Vote erfolgreich war. Des weiteren wird in einer Queue vermerkt, dass der Link einen Vote erhalten hat. Im Hintergrund wird diese Queue abgearbeitet, sodass diese Berechnungen keinen Einfluss auf die Wartezeit des Anwenders haben. Der Vote-Eintrag in der Queue hat z.B. folgende Aktionen zur Folge

  1. Upvote wird in der persistente DB gespeichert, sodass Cache & DB konsistent gehalten werden
  2. Neuberechnung des Caches der betroffenen Übersichten (Listen)
  3. Überarbeitung des Accounts (Cache)
  4. etc.

Fazit

Diese Vorgehensweise der Programmierung einer Webanwendung unterscheidet sich also grundlegend von meiner bisherigen Programmierung: Daten werden redundant gehalten, weil Speicher billig, CPU aber teuer und ein schnell bedienter Kunde (Besucher) wichtig ist. Das Video mit den Einsichten von Steve Huffman in die Abläufe bei reddit stellen für mich einen Paradigmenwechsel dar.

Natürlich: Webanwendungen ohne den Ausblick auf viele Zugriffe, benötigen keine solche Programmierung. Wenn man jedoch auf Skalierbarkeit wert legt, sollte man sich die vorgestellten Lehren besser zu Herzen nehmen…

„Heiße Themen“: Sortierung bei Hacker News, reddit & delicio.us

Die Sortierung von Nachrichten nach Neuigkeit oder Popularität ist trivial und ohne größeren Einsatz von Gehirnschmalz zu bewerkstelligen: etwa mit dem SQL-Statement ORDER BY date DESC bzw. ORDER BY likes DESC. Möchte man jedoch die Themen ausgeben, die momentan populär sind, kommt man mit einfachen Statements nicht mehr weiter. Im Folgenden werden drei Algorithmen von Hacker News, Reddit und delicio.us vorgestellt, die auch hier auf Englisch zusammengefasst sind.

Intuitiver Hacker News-Ansatz

Der intuitive Ansatz für die Problemstellung ist, solche Themen anzuzeigen, deren Bewertung hoch ist und deren Veröffentlichungstermin noch nicht lange her ist. Sei p die Anzahl der positiven Bewertungen (jeder Benutzer kann bei Hacker News nur eine positive Bewertung pro Thema abgeben) und t die Anzahl der Stunden, seitdem das Thema veröffentlicht wurde:

Algorithmus von Hacker News

Je länger also der Veröffentlichungszeitpunkt her ist, desto größer wird der Nenner. Da der Nenner mit der Potenz von 1,5 pro Stunde wächst, müssen die Votes ebenfalls potenziell mit der Zeit zunehmen, um f_h(p, t) auf gleichem Niveau zu halten.

Auch wenn keine Votes für das Thema eingehen, muss die Bewertungsfunktion f_h(p, t) jede Stunde neu berechnet werden. Dieses Problem hat der Reddit-Algorithmus nicht.

Reddit-Algorithmus

Anstatt die Bewertungen mit der Zeit exponentiell zu senken, bleibt bei Reddit die Bewertung über die Zeit gleich. Neue Themen erhalten stattdessen einen höheren Summanden, sodass ihre Bewertung höher ist. Der Reddit-Algorithmus ist etwas umfangreicher und passt nicht in eine einfache Formel. Zunächst definieren wir t_s als Differenz der Sekunden zwischen dem 08.12.2005 07:46:43 und dem Veröffentlichungsdatum des Themas:

t_s

Warum Reddit gerade den 08.12.2005 gewählt hat, ist nicht bekannt..

Da man bei Reddit sowohl positiv als auch negativ bewerten kann, wird x als Differenz der positiven (U) und negativen (D) Bewertungen definiert:

x

Wir definieren y als Signum- oder Vorzeichenfunktion von x. Wenn x > 0, ist y = +1. Wenn x = 0, ist y =0. Wenn x < 0, ist y = -1:

y

Und schließlich definieren wir z wie folgt

z

Ist der Betrag von x = 0, wird 1 genommen, sonst der Betrag von x.

Kommen wir zur eigentlichen Bewertungsfunktion. Mit dieser Funktion werden die Themen bewertet, sodass jene Themen mit der höchsten Bewertung die „heißen Themen“ darstellen:

Algorithmus von reddit

Funktionsgraph des Zehnerlogarithmus
Funktionsgraph des Zehnerlogarithmus (Quelle:Wikipedia)

Der erste Summand ist der „Bewertungssummand“. Wir sehen anhand des Funktionsgraph des Zehnerlogarithmus rechts, warum z so gewählt ist, dass er mindestens 1 ist. Der Summand ist somit immer 0 oder positiv sein.

Der Eintrag mit der höchsten Bewertung bei Reddit hat ein x von 21875. Der erste Summand ist bei diesem Eintrag also
Erster Summand: reddit

Der zweite Summand ist der „Zeitsummand“. y gibt aufgrund positiver/negativer/neutraler Bewertungen an, ob der Zeitsummand addiert, subtrahiert oder gar nicht berücksichtigt werden soll.

t_s ist die Zeitdifferenz in Sekunden. Schauen wir uns ein paar Beispiele an und stellen (Oh, Wunder!) fest, dass t_s mit der Zeit immer größer wird:

t_s Jetzt

t_s 2009

t_s wird noch durch 45.000 geteilt. 45.000 Sekunden sind 12,5 Stunden. Der Zeitsummand erhöht sich also alle 12,5 Stunden um 1. Das bedeutet, dass innerhalb von 12,5 Stunden der Bewertungssummand um 1 zulegen müsste, um das höhere Alter des Beitrags zu kompensieren. Der Bewertungssummand steigt um 1, wenn die Differenz zwischen positiven und negativen Bewertungen, um die Zehnerpotenz zunimmt. Von 1 auf 10 ist ja noch easy, aber es wird immer härter: von 10 auf 100, von 100 auf 1000, von 1000 auf 10.000 etc.

Ein Problem an dem Reddit-Algorithmus ist, dass die Bewertungen aufgrund des „Zeitsummands“ immer weiter steigt und man irgendwann an Grenzen von Speichergrößen stoßen wird. Wann dieser Zeitpunkt erreicht ist, habe ich nicht errechnet.. Vielleicht liefert ja ein Leser das Datum nach? ;)

HOT & delicio.us

Generell muss man sich die Frage stellen, ob die zwei genannten Algorithmen wirklich das liefern, was gerade populär ist. Auf meinem Blog beobachte ich nämlich zwei verschiedene Besucher- und Aktivitätsverläufe. Zum Einen den Blockbuster-Verlauf, sprich: gerade einen Artikel veröffentlicht und sofort Kommentare und Besucher. Und zum Anderen den Sleeper-Verlauf: der Artikel wird veröffentlicht und erst nach Monaten oder Jahren von den Besuchern entdeckt. Auch wenn der Sleeper-Verlauf seltener auftritt, bekommen „Hacker News“- und Reddit-Besucher nichts davon mit, weil das Thema, obwohl es gerade „hot“ ist, zu alt ist, um in den „heißen Themen“ zu landen.

Bei aktuellen Nachrichten ist der Sleeper-Verlauf vernachlässigbar, aber bei Bookmarks wie bei delicio.us, kann es sehr wohl relevant sein, dass ein „alter Bookmark“ gerade wieder „hot“ ist. delicio.us hat daher einen einfachen Ansatz, um heiße Bookmarks zu erkennen:

  • Welche Links wurden in der vergangenen Stunde am häufigsten gebookmarkt?

Fazit

Es gibt verschiedene Ansätze „heiße Themen“ zu erhalten.

  • Der intuitive Ansatz von Hacker News ist mit höherem Aufwand verbunden, da sich jede Stunde die Bewertung ändert und neu berechnet werden muss. Der Sleeper-Verlauf wird zudem nicht erkannt.
  • Der Reddit-Algorithmus bedeutet weniger Aufwand, allerdings erkennt er den Sleeper-Verlauf nicht.
  • Der delicio.us Ansatz erkennt zwar Blockbuster und Sleeper-Verlauf, allerdings kann nicht garantiert werden, dass auf kleinen Plattformen mit wenig User-Aktionen ausreichend Bewertungen vorhanden sind. Wenn keine oder wenig Bewertungen in dem Zeitraum abgegeben wurden, können keine „heiße Themen“ angezeigt werden.

Firefox Erweiterungen – Meine Top 5

5. Echofon

EchofonMit Echofon kannst du Twitter direkt in deinem Browser benutzen. Neue Tweets werden in einer kleinen Box angezeigt. Du kannst eigene Tweets und Direktnachrichten schreiben und siehst, in welchen Tweets, du erwähnt wurdest.

Außerdem werden neue Tweets farblich hervorgehoben, man kann auf Tweets antworten und Tweets favorisieren.

Auch mehrere Twitter Konten werden von Echofon unterstützt.

Download von Echofon

4. Deutsches Wörterbuch

Ein Wörterbuch macht dann Sinn, wenn man viel im Internet schreibt, aber auf eine Rechtschreibprüfung nicht verzichten will:

Firefox Wörterbuch

Einziges Manko dieser Erweiterung ist, dass das Wörterbuch leider nicht alle Wörter kennt und hin und wieder verschlimmbessert, weil sich auch einige Fehler in das Wörterbuch geschlichen haben. Aber da man selbst die Microsoft Office Rechtschreibprüfung nicht blindlings verwenden sollte, weiß man, dass man Rechtschreibprüfungen eh nur mit Vorsicht genießen sollte.

Download des Deutschen Wörterbuchs

3. Copy Plain Text

Diese Erweiterung fügt, wenn man mit der rechten Maustaste auf einen markierten Text klickt, den Punkt „Copy as Plain Text“ unter dem normalen Kopieren hinzu. Wozu das gut ist? Nun, wenn man z.B. etwas von einer Webseite in Word kopieren möchte, werden Formatierungen beim normalen Kopieren auch übernommen. Beim „Copy as Plain Text“ wird nur der Text kopiert.

Download von Copy Plain Text

2. Adblock Plus

Mit Adblock Plus war Werbung gestern, dann die Werbung wird mit dieser Erweiterung einfach ausgeblendet.

Auch wenn perun die Logik hinter Werbeblockern nicht versteht, so setze ich Adblock Plus seit Jahren ohne schlechtes Gewissen ein. Klar, wenn man Geld im Internet verdienen will oder zumindest seine Kosten decken will, sind Werbebanner eine Möglichkeit. Ich habe mich vor dem Einsatz dieser Erweiterung aber schon so oft von Werbung im Internet erschlagen gefühlt, dass mir Werbebanner äußerst suspekt sind und ich ihnen keine Träne nachweine. Wer Werbebanner einsetzt, verschreckt seine Besucher.

Wenn etwas so gut ist, dass ich dadurch einen echten Mehrwert habe, bezahle ich auch gerne dafür. Aber auf zweitklassigen Webseiten mit Werbebannern voll gepflastert zu werden, sehe ich nicht ein.

Download von Adblock Plus

1. Textarea Cache

Diese Erweiterung ist für all diejenigen gedacht, die – während sie lange Texte auf Webseiten schreiben – schon mal

  • auf den falschen Link klicken
  • vergessen den Text auch abzuschicken
  • fälschlicherweise auf den Zurück-Button klicken
  • denen hin und wieder der Computer abstürzt
  • oder per WLAN im Netz sind und beim Abschicken die Verbindung flöten geht

In all diesen Fällen wäre der Text (lange eMail, Forenbeitrag, Kommentar, Blog-Eintrag etc.) unwiderruflich weg – irgendwo im Datennirwana.

Mit dieser Erweiterung wird der Inhalt von Textfeldern allerdings zwischengespeichert, so dass man ihn wiederherstellen kann:

Textarea Cache

Download von Textarea Cache