Angenommen, wir haben einen Dienst, der Daten speichern kann. Dieser Dienst soll aber nicht auf einem einzigen Rechner laufen, sondern auf mehreren, die gemeinsam ein Cluster bilden.
Anforderungen dabei sind:
Die Daten sollen sich gleichmäßig auf die einzelnen Knoten des Clusters verteilen (das heißt, es kann nicht passieren, dass ein Knoten zu 90% belegt ist, ein anderer nur zu 10%).
Jegliche Daten sind auf mindestens zwei Servern redundant gespeichert - fällt ein Knoten aus, kann ein anderer als Ersatz einspringen (wobei nicht zwingend eine 1:1-Beziehung zwischen den Server gegeben sein muss, es können auch die Daten A von Server 1 auf Server 2 liegen, die Daten B aber auf Server 3).
Fällt einer von Knoten aus, verteilen sich die Daten automatisch neu, um sich auf die verbleibenden n-1 Knoten wieder gleichmäßig zu verteilen.
Kommt ein neuer Knoten hinzu, ebenso ;-).
Ich bin sicher nicht der erste Mensch auf der Welt, der sich dafür interessiert, wie ein entsprechender Verteilungsalgorithmus funktioniert - Werkzeuge wie zB Hazelcast oder Velocity zeigen, dass so etwas funktioniert.
Die Frage ist bloß - wie?
Mir fehlt letztlich ein Ansatz, ein Stichwort. Ich denke, dass es im Bereich der Graphentheorie hierfür sicherlich einen Ansatz gibt, weiß aber nicht, wonach ich suchen soll oder wie ich die Sache angehen soll.
Wie sind deine Daten aufgeteilt, kannst du einen Schlüssel bilden? Ich habe mich mal mit einen ähnlichen Konstrukt beschäftigt, ich wollte damals in einem Cluster System Apfelmännchen berechnen lassen.
Hängengeblieben bin ich bei Kademlia. Dabei handelt es sich um eine verteilte Hashtabelle. Sehr ausfallsicher und Lastverteilung inkl. das Gewicht der Graphen ist die verbindungsgeschwindigkeit zwischen zwei Nodes.
Der Graph selbst verteilt sich auch über die Nodes du musst also nicht irgendwo zentral den Graph vorhalten.
Mein Problem damals war das ich keine C# Implementierung gefunden hatte und das Protokoll selbst zu schreiben dazu hatte ich nicht Zeit und Lust. Interessant ist die Technik aber allemal ;)
So, ich habe mich jetzt mal ein bisschen über Kademlia schlau gemacht, ebenso über verteilte Hashtabellen - und ich denke, das wäre ein durchaus gangbarer Ansatz :-)!
Es gibt sogar eine .NET-Implementierung von Kademlia, siehe http://sourceforge.net/apps/trac/daylight/wiki ... ich denke, mit der werde ich mich nun mal näher auseinandersetzen.
Aktiv ist es wirklich nicht, aber doch schon ganz gut brauchbar. Es fehlen ein paar Dinge (insbesondere, was das Republishing angeht), aber die sind super kommentiert, so dass man hier leicht selbst nachhelfen kann.
Ich würde jedes Paket zufällig auf zwei unterschiedliche Server legen. Ist einfach umzusetzen, die erwartete Auslastung ist gut und Du musst keine Statistiken über aktuelle Auslastung der einzelnen Server führen.
Bei einer Abfrage, können alle Server per Mutlicast gefragt werden. Wenn nur einer antwortet, können die Daten zusätzlich auf einen zufällig gewählten anderen repliziert werden. Wenn mehr als zwei antworten, können die Daten von allen bis auf zweien (die zufällig gewählt werden) gelöscht werden.
Ist sicher nicht optimal, aber ich weiss nicht, ob eine bessere Lösung den zusätzlichen Aufwand wert ist. IMHO haben Randomized Algorithms durch ihre Einfachheit und Performanz durchaus ihren Reiz.
Den Graph musst Du aber irgendwo pflegen. Im Prinzip verteilt, damit Du keinen Single Point of Failure kriegst. Halte ich für schwierig und nicht der Mühe wert. Aber ich lasse mich gerne von einem besseren Algorithmus überzeugen :-)
Du könntest die Daten nach einem bestimmten Schlüssel verteilen. Zum Beispiel ein Hash oder eine GUID die jeden Paket zugeordnet wird. Dann brauchst du eine Tabelle die die Schlüssel den Servern zuordnet. Mit GUIDs zum Beispiel so:
beginnt mit | Server 1 | Server 2 ------------------------------------- 0 .. 4 | s1.test.de | s2.test.de 5 .. 9 | s3.test.de | s4.test.de A .. F | s5.test.de | s6.test.de
Wird ein Datenpaket gespeichert, wird der Schlüssel geprüft und je nach Anfang der GUID wird er auf die entsprechenden Server verteilt.
Wenn du einen Hash auf deinen Schlüssel anwendest und diesen zur Verteilung auf die Server benutzt entfallen beide Probleme. Die Hashes sollten gleichverteilt sein und den Masterserver kannst du dir sparen wenn die Schlüsselbereichzuordnung so wie von mir oben geschrieben durchgeführt werden. Du musst nur noch das Mapping für Bereiche und nicht mehr für komplette Schlüssel mitschleppen.
Ich finde diesen Ansatz zu statisch: Wie würde das System beim Ausfall eines Knotens reagieren? Da dies berücksichtigt werden soll, können wir nicht a priori (durch eine Hash-Funktion) die aktuellen Knoten ermitteln.
Die Ausfallsicherheit soll sich doch durch die Server-Redundanz ergeben. Das ist ja nun auch recht simpel:
1.) Ich will Datensatz "Blafasel" holen. 2.) Ich erzeugen den Hash von "Blafasel". 3.) Ich hole mir aus dem Mapping alle Server die für diesen Bereich zuständig sind. 4.) Ich frage den ersten Server ab. Ist der nicht erreichbar, frage ich den zweiten usw. (Ist gar keiner erreichbar kucke ich nach ob die apokalyptischen Reitern am Horizont erschienen sind.)
Die Frage wäre noch: Wie entscheidet ein Server, für welches Hashes er zuständig ist? Weil irgendwie muss das ja im System halbwegs gleichverteilt sein, aber die Server sollen das ja autonom aushandeln?
Der Server entscheidet das gar nicht in diesem Szenario, sondern der Client der liest und schreibt. Ich weiß leider nicht wie dein System genau aussieht, bei mir ist der Client ein Service der die Schreib/Leseaufgaben übernimmt. Die Liste der verfügbaren Server und ihre Zuordnung kann sich der Client auch von den Servern ziehen. Genauso gut kann natürlich auch der Server beim Schreibversuch eine Rückmeldung geben: "Dafür ist XXX zuständig." Dazu müssen sich die Server untereinander kennen, das kann per P2P, Configfiles, Masterserver, sonstewie geregelt werden.
Das soll (in meinem Szenario) aber für den Client transparent sein - insofern müssten das schon die Server untereinander ausmachen, und zwar automatisch, ohne Konfiguration von außen.
Im Prinzip reden wir hier von einer verteilten Datenbank, richtig? Einziger Unterschied: Nicht jeder Knoten hat alle Daten. Frage: Warum nicht? Sind es so viele Daten?
Ich würde auch ein DBMS zurückgreifen, das Replikation beherrscht (z.B. CouchDB, db4o). Ansonsten fällt mir dazu am ehesten Peer2Peer ein (Artikel: .NET P2P).
Grundsätzlich: Wie hast Du Dir den Zugriff vorgestellt, also wenn z.B. die Daten für User A auf den Servern 1+2 liegen, weiss das dann ein Loadbalancer, oder eine Client Application? Du brauchst doch dann nen Index, der auch noch dynamisch sein muss (Datenumzug auf anderen Server).
EDIT: Geht es eher um Daten- oder um Lastverteilung?
EDIT2: Distributed Database Systems - P2P Systems Google Suchtext: "distributed peer2peer database" liefert einige interessante Artikel, aber nix Fertiges [aber Du wolltest ja Denkanstösse :)]
Warum nicht jeder Knoten alle Daten hat: Dafür sind es zu viele Daten. Dass ich einfach CouchDB & Co nehmen könnte, ist mir klar - mich interessiert aber, wie man so etwas selbst bauen würde, beziehungsweise wie so etwas funktioniert.
Wo welche Daten liegen sollen eigentlich nur die Server wissen - sprich, der Client kann irgendeinen Server nach den Daten für User A fragen, und bekommt seine Antwort. Entweder direkt, oder indem der Server den zuständigen Server kontaktiert.
Replikation wie bei CouchDB und Co ist ja was anderes als eine verteilte DB ;) Ich denke da kommst Du mit den Prizipen des P2P weiter: Jeder hat nen Index und kann jederzeit alles von jedem bekommen.
