Sonntag, 2. März 2008

Ein unorthodoxer Ansatz für ein Datenbank-Design: Das Aufkommen des Shardings

Quelle: http://highscalability.com/unorthodox-approach-database-design-coming-shard
Autor: Todd Hoff am 31. Juli 2007 18:13
Übersetzung: Sebastian Wallroth

Vor langer, langer Zeit skalierten wir Datenbanken, indem wir immer größere, schneller und teurere Maschinen kauften. Während diese Vorgehensweise tolle fette Gewinnspannen ist, funktioniert es nicht so gut mit den Girokonten unserer heldenhaften Systembauer, die weit mehr skalieren müssen, als sie für gigantische Datenbankserver aufbringen können. In einer außergewöhnlichen zweiteiligen Artikelserie erklärt Dathan Pattishall seine Beweggründe für ein revolutionäres neues Datenbankdesign - Sharding -, über das er nachzudenken begann noch bevor er bei Friendster arbeitete und dann bei Flickr voll implementierte. Flickr verarbeitet heute mehr als 1 Milliarde Transaktionen pro Tag, in weniger als ein paar Sekunden antwortend und bei niedrigen Kosten linear skalieren.

Was ist Sharding und wie wurde es die Antwort auf die Skalierungsprobleme großer Webseiten?

InformationsquellenWas ist Sharding?
Während er an Auction Watch arbeitete kam Dathan die Idee, ihre Skalierungsprobleme zu lösen, indem er einen Datenbankserver für eine Benutzergruppe aufbaute und diese Server auf billigen Linuxkisten laufen ließ. In diesem Schema sind die Daten für den Benutzer A auf einem Server gespeichert und die Daten für Benutzer B auf einem anderen Server. Es ist ein föderatives Modell. Gruppen von 500.000 Benutzern werden zusammen in sogenannten Shards gespeichert

Die Vorteile sind:
  • Hohe Verfügbarkeit. Wenn eine der Kisten abstürzt, können die anderen weiterarbeiten.
  • Schnellere Abfragen. Kleine Datenmengen in jeder Benutzergruppe bedeuten schelleres Durchsuchen.
  • Mehr Schreibbandbreite. Ohne Masterdatenbank, die die Schreibzugriffe serialisiert kann man parallel schreiben, was die Schreibdurchsatz erhöht. Schreiben ist der Hauptengpass für viele Webseiten.
  • Du kannst mehr Arbeit erledigen. Ein paralleles Backend bedeutet, dass Du mehr Arbeiten gleichzeitig erledigen lassen kannst. Du kannst mit mehr Benutzerlast verkraften, insbesondere, wenn Du Daten schreibst, weil es parallele Wege durch das System gibt. Du kannst die Last zwischen den Webservern verteilen, die auf die Shards über verschiedene Netzwerkwege zugreifen, von getrennten CPUs betrieben werden, getrennte RAM-Caches und getrennte IO-Wege verwenden, um die Aufgaben zu bearbeiten. Nur sehr wenige Engpässe begrenzen Deine Arbeit.
Was unterscheidet Sharding von traditionellen Architekturen?
Sharding unterscheidet sich von traditionellen Datenbankarchitekturen in mehreren wichtigen Punkten:
  • Daten sind denormalisiert. Traditionell normalisieren wir Daten. Daten werden über anomaliefreie Tabellen verteilt und dann wieder miteinander verbunden, wenn sie gebraucht werden. Beim Sharding werden die Daten denormalisiert. Man speichert Daten zusammen, wenn sie später zusammen verwendet werden.
    Das bedeutet nicht, dass man Daten auch nach Typ aggregiert. Man kann Benutzerprofile getrennt von deren Kommentaren, Blogs, E-Mails, Medien etc. speichern, aber die Benutzerprofildaten würden als Einheit gespeichert und verarbeitet. Das ist ein sehr schneller Ansatz. Man holt und speichert einfach einen Blob. Man braucht keine Joins und man kann sie mit einem Festplattenzugriff speichern.
  • Daten sind über viele physikalische Instanzen hinweg parallelisiert. Nach althergebrachter Weise werden Datenbanken vertikal skaliert (scale up). Man kauft größere Maschinen, um mehr Power zu kriegen. Mit diesem Ansatz kann man jedoch massiv mehr Arbeit erledigen, weil sie parallel erledigt werden kann.
  • Daten werden klein gehalten. Je größer ein Datenset ist, das ein Server bearbeitet, desto schwerer ist es, intelligent zu optimieren, weil man auf eine so breite Vielfalt von Daten zugreifen muss. Man braucht gewaltige Brocken RAM, die dann nicht mal dazu ausreichen, die Daten zu cachen, wenn man es braucht. Indem man Daten in kleineren Shards isoliert, können die Daten, auf die man zugreift leichter im Cache gehalten werden.
    Kleinere Datensets kann man außerdem leichter sichern, wiederherstellen und verwalten.
  • Daten sind höher verfügbar. Weil die Shards unabhängig sind, schadet eine Fehlfunktion an einem Shard keinem anderen Shard. Und wenn man jeden Shard mit 50% Kapazität laufen lässt, ist es viel einfacher, einen Shard an Ort und Stelle upzugraden. Das Vorhalten mehrerer Datenkopien innerhalb eines Shards hilft außerdem bei Redundanzen und dabei, die Daten mehr zu parallelisieren, so dass mehr Arbeit mit den Daten erledigt werden kann. Man kann einen Shard auch so aufsetzen, dass man eine Master-Slave- oder eine Doppel-Master-Beziehung zwischen den Shards hat, um einzelne Fehlerquellen innerhalb des Shards zu vermeiden. Wenn ein Server abstürzt, kann ein anderer übernehmen.
  • Man braucht keine Replikation. Daten von einem Master-Server zu einem Slave-Server zu replizieren ist ein traditioneller Ansatz für das Skalieren. Daten werden auf den Master-Server geschrieben und dann auf einen oder mehr Slave-Server repliziert. An diesem Punkt können Lese-Operationen von den Slaves übernommen werden, aber alle Schreiboperationen passieren auf dem Master.
    Selbstverständlich wird der Master zum Schreib-Engpass und zur Fehlerquelle. Und wenn die Last zunimmt, nehmen auch die Kosten für die Replikation zu. Replikation kostet CPU, Netzwerkbandbreite und Festplatten-IO. Die Slave fallen zurück und haben veraltete Daten. Die Typen bei YouTube hatten ein großes Problem mit Replikationsoverhead, als sie skalieren wollten.
    Sharding löst das Replikationsproblem klar und elegant.
Einige Probleme mit Sharding
Sharding ist nicht perfekt. Es hat einige Probleme.
  • Rebalancieren von Daten. Was passiert, wenn ein Shard die Speichergröße übersteigt und geteilt werde muss? Sagen wir, einige Benutzer haben ein besonders lange Freundesliste, die die Speicherkapazitäten für den Shard überschreiten. Man muss den Benutzer in einen anderen Shard übertragen.
    Auf einigen Plattformen, mit denen ich gearbeitet habe, war das ein tödliches Problem. Man muss das Datenzentrum von Anfang an korrekt ausbauen, weil das übertragen von Daten von Shard zu Shard eine Menge Downtime verbraucht.
    Rebalancing muss von Anfang an eingebaut sein. Googles Shards werden automatisch rebalanciert. Dafür müssen Datenreferenzen durch so eine Art Naming-Dienst laufen, so dass sie wiedergefunden werden können. So macht es Flickr. Und die Referenzen müssen annullierbar sein, so dass die darunterliegenden Daten übertragen werden können, während man sie benutzt.
  • Daten von multiplen Shards joinen. Um eine komplexe Freundeseite zu bauen oder eine Benutzerprofilseite oder eine Diskussionsseite mit Threads muss mann normalerweise viele verschiedene Daten aus vielen verschiedenen Quellen zusammen ziehen. Mit Sharding kann man nicht einfach eine Abfrage ausführen und alle Daten kriegen. Man muss einzelne Anfragen an die Datenquellen stellen, alle Antworten einsammeln und dann die Seite bauen. Dankenswerterweise ist dieser Prozess wegen Caching und schnellen Netzwerken normalerweise schnell genug, so dass die Ladezeiten der Seiten exzellent sein können.
  • Wie partitioniert man Daten in Shards? Welche Daten tut man in welche Shards? Wo kommen Kommentare hin? Gehören alle Benutzerdaten wirklich zusammen oder nur die Profildaten? Sollten die Mediendaten, IMs und Freundeslisten usw. der Benutzer irgenwo anders hin? Unglücklicherweise gibt es keine einfachen Antworten auf diese Fragen.
  • Weniger Schwung. Die Leute haben Erfahrung mit traditionellen RDBMS-Werkzeugen, so dass es viel Hilfe von außen gibt. Man hat Bücher, Experten, Werkzeugsätze und Diskussionforen, wenn etwas schief läuft oder man sich fragt, wie man ein neues Feature implementiert. Eclipse wird keinen Shard-View haben und man wird keine automatischen Backup- und Wiederherstellungsprogramme für Shards finden. Mit Shards ist man auf sich gestellt.
  • Die Implementierung von Shards wird nicht gut unterstützt. Sharding ist zur Zeit zumeist ein Eigenbau-Ansatz. LiveJournal macht seine Werkzeugsätze verfügbar. Hibernate entwickelt eine Bibliothek, MySQL hat die Unterstützung von Partitionierung hinzugefügt. Aber im Allgemeinen ist es immer noch etwas, was man selbst implementieren muss.

Siehe auch

Samstag, 12. Januar 2008

Twitter skalieren: Wie man Twitter 1.000 Prozent schneller macht

Original: http://highscalability.com/scaling-twitter-making-twitter-10000-percent-faster
Autor: Todd Hoff am 10. Agust 2007 21:01
Übersetzung: Sebastian Wallroth

Twitter begann als Nebenprojekt und wuchs schnell an, von 0 auf Millionen Pageviews in erschreckend wenigen Monaten. Frühe Design-Entscheidungen, die im Kleinen gut funktionierten schmolzen unter dem Andrang neuer Benutzer, die Piepse zu all ihren Freunden zwitscherten. Der Web-Liebling Ruby on Rails wurde früh für die Skalierungsprobleme verantwortlich gemacht, aber Blaine Cook, Twitters Hauptarchitekt, hält Ruby für schuldlos:
Für uns geht es wirklich um horizontales Skalieren - auf dieser Seite waren Rails und Ruby nicht die Stolpersteine, verglichen mit anderen Sprachen und Frameworks. Die Leistungssteigerung, die mit “schnelleren” Sprachen assoziiert wird, hätte uns 10-20% Verbesserung gebracht, aber Dank der Architektur-Änderungen, die Ruby und Rails glücklicherweise beinhaltet, ist Twitter im August 2007 1.000% schneller, als es im Januar 2007 war.

Wenn Ruby on Rails nicht Schuld war, wie lernte Twitter immer höher und höher zu skalieren?

Website: http://twitter.com

Informationsquellen
Die Plattform
  • Ruby on Rails
  • Erlang
  • MySQL
  • Mongrel - Ein hybrider Ruby/C-HTTP-Server, designed, klein, schnell und sicher zu sein
  • Munin
  • Nagios
  • Google Analytics
  • AWStats - Echtzeit-Logdatei-Analysierer für erweiterte Statistiken
  • Memcached
Die Fakten
  • Mehr als 350.000 Benutzer. Die tatsächliche Anzahl ist wie immer, sehr sehr super geheim.
  • 600 Aufrufe pro Sekunde.
  • durchschnittlich 200-300 Verbindungen pro Sekunde. Spitzen bis zu 800 Verbindungen pro Sekunde.
  • MySQL verarbeitet 2.400 Aufrufe pro Sekunde.
  • 180 Rails-Instanzen. Verwendet Mongrel als "Web"-Server.
  • 1 MySQL Server (eine große 8-Kern-Box) und einen Slave. Der Slave ist nur zum lesen für Statistiken und Reporting.
  • 30+ Prozesse für die Behandlung von Sonderaufträgen (odd jobs).
  • 8 Sun X4100s.
  • Ein Aufruf wird in Rails innerhalb von 200 Millisekunden verarbeitet.
  • Die durchschnittliche Verarbeitungszeit in der Datenbank liegt bei 50-100 Millisekunden.
  • Über 16 GB Memcached.
Die Architektur
  • Lief vor aller Augen in Skalierungsprobleme. Eine Zeit lang traten immer wieder Fehler auf.
  • Ursprünglich hatten sie kein Monitoring, keine Diagramme, keine Statistiken, was es schwer machte, die Probleme festzumachen und zu lösen. Munin und Nagios wurden hinzugefügt. Es gab Schwierigkeiten damit, die Tools unter Solaris zu verwenden. Sie hatten Google Analytics, aber die Seiten wurden gar nicht geladen, so dass das nichts brachte :-)
  • Verwendet Caching mit Memcached ausgiebig.
    • Wenn zum Beispiel der Aufruf eines Zählers langsam wird, kann man den Zähler in Millisekunden in Memcache memoisieren.
    • Die Status der Freund zu erhalten ist schwierig. Es gab Sicherheits- und andere Herausforderungen. Anstatt eine Datenbanksuche auszuführen, wird der Freundesstatus im Cache erneuert. Das gibt einen vorhersagbaren Antwortzeitrahmen (Obergrenze 20 Millisekunden).
    • ActiveRecords-Objekte sind gewaltig, weshalb sie nicht gecached werden. Also wollen sie kritische Attribute in einem Hash speichern und die anderen Attribute bei Bedarf per Lazy loading holen.
    • 90% der Anfragen sind API-Abfragen. Also mach kein Seiten/Abschnitts-Caching im Frontend. Die Seiten sind so zeitempfindlich, dass nichts Gutes dabei herauskommt. Aber sie cachen API-Abfragen.
  • Messaging
    • Verwende Messaging ausgiebig. Produzenten produzieren nachrichten, die in Warteschlangen warten und dann an die Kunden ausgeliefert werden. Twitters Hauptfunktionalität ist es, als eine Nachrichtenbrücke zwischen verschiedenen Formaten (SMS, Web, IM, etc.) zu agieren.
    • Sende eine Nachricht, um die Cache des Freundes im Hintergrund zu leeren, anstatt alles einzeln gleichzeitig zu machen.
    • Gestartet mit DRb (Distributed Ruby). Eine Bibliothek, die Dir erlaubt Nachrichten von ferngesteuerten Ruby-Objekten (remote Ruby objects) via TSP/IP zu senden und zu empfangen. Aber es funktionierte irgendwie komisch und war eine Fehlerwuelle.
    • Umstellung auf Rinda, eine gemeinsam genutzte Warteschlange, die ein Tuple space-Modell im Rahmen von Linda verwendet. Aber die Warteschlangen sind persistent und die Nachrichten gehen im Fehlerfall verloren.
    • Erlang wurde getestet. Problem: Wie kriegt man einen abgestürzten Server am Sonntag zum Kaufen, wenn 20.000 Benutzer warten? Der Entwickler wusste es nicht. Nicht viel Dokumentation. Also bedrohte es den Betrieb - was tödlich ist.
    • Umstellung auf Starling, eine in Ruby geschriebene verteilte Warteschlange.
    • Verteilte Warteschlangen wurde geschaffen, um Systemabstürze zu überleben, indem sie auf die Festplatte geschrieben werden. Andere große Webseiten verwenden diesen einfachen Ansatz ebenfalls.
  • SMS werden mittels einer von einer Drittpartei bereitgestellten API verwendet. Ist sehr teuer.
  • Deployment
    • Sie untersuchen und installieren neue Mongrel Server. Kein sehr schöner Weg.
    • Dem Benutzer wird ein interner Serverfehler angezeigt, wenn die Mongrel Server ersetzt werden.
    • Alle Server werden zeitgleich abgeschossen. Ein rollender Ausfall wird nicht angewandt, weil der Status der Nachrichtenschlange in Mongrels steckt und ein rollierender Ansatz die Warteschlangen dazu bringen würde, die verbleibenden Mongrels überlaufen zu lassen.
  • Missbrauch
    • Eine Menge Downtime weil Leute durch die Seite surfen und jedermann als Freund hinzufügen. 9.000 Freunde in 24 Stunden. Das würde die Seite abstürzen lassen.
    • Baue Werkzeuge, um diese Probleme anzuzeigen, so dass man genau festmachen kann, wann und wo sowas passiert.
    • Sei unbarmherzig. Lösche deren Benutzeraccounts.
    Partitionierung
    • Es gibt Pläne für eine zukünftige Partitionierung. Zur Zeit machen sie das nicht. Diese Änderungen haben bisher gereicht.
    • Das Partitionierungsschema wird auf Zeit basieren, nicht auf Benutzern, weil die meisten Anfragen zeitlich eng begrenzt und nur lokal auftreten.
    • Partitionierung wird schwierig sein wegen der automatischem Memoisation. Sie können nicht garantieren, das Nur-Lesen-Operationen wirklich nur-lesend sein werden. Sie könnten auf einen Nur-Lesen-Slve schreiben, was wirklich schlecht ist.
  • Twitters API-Traffic ist zehnmal größer als der Seiten-Traffic
    • Deren API ist das wichtigste, was Twitter gemacht hat.
    • Den Dienst zu halten erlaubt den Entwicklern auf der Infrastruktur aufzubauen und mit Ideen zu kommen, die besser sind als das, was Twitter selbst einfallen würde. Twitterific zum Beispiel, ein wundevollerer Weg, Twitter zu nutzen, als ein kleines Team mit anderen Prioritäten erstellen könnte.
  • Monit wird verwendet, um Prozesse abzuschießen, wenn sie zu groß sind.

Gelernte Lektionen
  • Sprich mit der Community. Verstecke dich nicht und versuche nicht, Probleme selber zu lösen. Viele hervorragende Leute sind bereit zu helfen, wenn Du fragst.
  • Behandle Deinen Skalierungsplan wie einen Geschäftsplan. Stelle ein Beratergremium zusammen, das Dich unterstützt.
  • Mach es selbst. Twitter verbrachte viel Zeit damit, anderer Leute Lösungen auszuprobieren, die fast zu funktionieren schienen, aber dann doch nicht ausreichten. Es ist besser, einige Dinge selber zu bauen, so dass man immerhin etwas Kontrolle behält und man kann die Features einbauen, die man braucht.
  • Baue Benutzerbeschränkungen ein. Die Leute werden versuchen, Dein System kaputt zu machen. Baue vertretbare Beschränkungen und Warnmelder ein, um Dein System davor zu beschützen, abgemurkst zu werden.
  • Mach die Datenbank nicht zum zentralen Flaschenhals des Untergangs. Nicht alles erfordert einen gigantischen Join. Cache Daten. Denk über andere kreative Wege nach, um dasselbe Ergebnis zu erhalten. Ein gutes Beispiel wird in Twitter, Schienen, Hämmer und 11.000 Nägel pro Sekunde beschrieben.
  • Mach Deine Applikation von Start weg partitionierbar. Dann wirst Du immner einen Weg haben, Dein System zu skalieren.
  • Wenn Du merkst, dass Deine Seite langsam ist, füge sofort ein Reporting hinzu, um die Probleme analysieren zu können.
  • Optimiere die Datenbank.
    • Indiziere alles. Rails macht das nicht für Dich.
    • Versuche mal zu erklären, was deine Abfragen (queries) machen. Die Indexe könnten anders sein, als Du erwartest.
    • Denormalisiere viel. Kleinlichkeit nützte ihnen. Zum Beispiel speichern sie alle Benutzer-IDs zusammen mit den IDs der Freunde, was ihnen eine Menge aufwändiger Joins erparte.
    • Vermeide komplexe Joins.
    • Vermeide das Scannen großer Datenmengen.
    Cache verdammt noch mal alles. Individuelle aktive Einträge werden derzeit noch nicht gecached. Testabfragen sind zur Zeit noch schnell genug.
  • Teste alles.
    • Du willst wissen, wenn Du eine Applikation ausrollst, dass sie richtig funktionieren wird.
    • Sie haben jetzt eine komplette Testsuite. Wenn das Caching nicht funktioniert, dann sind sie in der Lage den Fehler zu finden, bevor sie Live gehen.
  • Lange laufende Prozesse sollten zu Daemons abstrahiert werden.
  • Verwende Ausnahme-Melder und Ausnahme-Logger, um sofort über Probleme benachrichtigt zu werden, so dass Du korrekt reagieren kannst.<
  • Mach keine Dummheiten.
    • Skalieren bedeutet, dass vorher richtige Vorgehensweisen jetzt bescheuert sind.
    • Zu versuchen 4.000 Freunde auf einmal in den Speicher zu laden, kann den Server zum Absturz bringen, aber wenn da nur 4 Freunde sind, funktioniert es großartig.
  • Die meiste Leistung kommt nicht von der Sprache, sondern vom Anwendungsdesign.
  • Mach aus Deiner Webseite einen offenen Dienst, indem Du einen API baust. Ihre API ist ein gewaltiger Grund für Twitters Erfolg. Es erlaubt Benutzern ein immer weiter expandierendes Ökosystem um Twitter herum aufzubauen, so dass es schwierig ist, mit ihm zu konkurrieren. Du kannst niemals all die Arbeit machen, die Deine Benutzer machen und Du wirst wahrscheinlich niemals so kreativ sein. Also öffne Deine Anwendungen und mach es Anderen einfach, ihre Anwendungen mit Deinen zu verbinden.


Verwandte Artikel

technorati skalieren - 100 Millionen täglich indizierte Blogs

Original: http://www.royans.net/arch/2007/10/25/scaling-technorati-100-million-blogs-indexed-everyday/
Autor: Royans Tharakan
Übersetzung: Sebastian Wallroth

Mit der Indizierung von 100 Millionen Blogs mit über 10 Milliarden Objekten und einer Benutzerbasis, die sie alle sechs Monate verdoppelt, ist technorati den meisten anderen Blog-Suchmaschinen weit voraus. Aber technorati ist viel mehr als nur eine Suche und jeder technorati-Benutzer kann Dir das erläutern. Ich empfehle, John Newtons Interview mit David Sifry zu lesen, dass ich faszinierend fand. Hier ein paar Höhepunkte aus diesem Interview, wenn Du nicht die Zeit hast, das ganze Ding zu lesen.

Gegenwärtiger Stand von technorati

  • 1 Terabyte Inhalt kommen pro Tag hinzu
  • 100 Millionen Blogs
  • 10 Milliarden Objekte
  • 0,5 Milliarden Fotos und Videos
  • Datenverdopplung alle sechs Monate
  • Benutzerverdopplung alle sechs Monate

Die erste Version war dafür vorgesehen, für eine gewisse Zeit für wenig Geld Informationen zu tracken.

  • Diese Version tat alles in eine relationale Datenbank, was ausreichte, solange die Größe des Indexes kleiner war als der physikalische Speicher
  • Es funktionierte gut bis etwa 20 Millionen Blogs

Die nächste Generation zog Vorteil aus der Parallelisierung.

  • Die Daten wurden in Shards aufgebrochen
  • Die Daten wurden häufig zwischen den Servern synchronisiert
  • Die Datenbankgröße erreichte die größte bekannte OLTP-Größe.

    • Daten Schreiben und Lesen hielten sich sie Waage
    • Die Verwaltung der Datenintegrität war wichtig

      • So kam viel Druck auf das System



Die dritte Generation

  • Die Shards entwickelten sich weiter

    • Die Shards basierten jetzt auf Zeiten statt auf URLs
    • Inhalte wurden in spezielle Datenbank verschoben, anstatt sie in einer relationalen Datenbank zu halten

  • Nichts wurde gelöscht
  • Es wurden nur Shards bewegt und für Hinzugekommenes wurden neue Shards verwendet

Verwendete Werkzeuge

  • Green Plum - ermöglicht Firmen, für eine genaue Analyse schnell auf große Mengen kritischer Daten zuzugreifen. Entworfen für hohe Leistung und groß skalierende Business Intelligence besteht Greenplums Familie von Datenbankprodukten aus Lösungen für Installationen von Abteilungs-Datamarts bis zu Multi-Terabyte-Data Warehouses.

Hätte früher gemacht werden sollen

  • Man hätte sich für Klickstromanalyse-Software interessieren sollen, um zu analysieren, was Klicks mit den Benutzern

    • Aussagen, wieviel Zeit die Benutzer mit einem Feature zubringen