Verteilter Algorithmusentwurf

Ich habe "Einführung in Algorithmen" gelesen und begann ein paar Ideen und Fragen in meinem Kopf zu bekommen. Derjenige, der mich am meisten verblüfft, ist, wie Sie einen Algorithmus entwerfen würden, um Elemente / Nachrichten in einer Warteschlange zu planen, die verteilt wird.

Meine Gedanken haben mich dazu gebracht, Wikipedia zu Themen wie Sortieren, Nachrichtenwarteschlangen, Sheduling, verteilten Hashtables zu durchsuchen, um nur einige zu nennen.

Das Szenario: Nehmen wir an, Sie möchten ein System haben, das Nachrichten (Strings oder einige serialisierte Objekte) in die Warteschlange stellt. Ein Hauptmerkmal dieses Systems besteht darin, jeden einzelnen Fehlerpunkt zu vermeiden. Das System musste auf mehrere Knoten innerhalb eines Clusters verteilt werden und musste konsistent (oder so gut wie möglich) die Arbeitslast jedes Knotens im Cluster bewältigen, um Hotspots zu vermeiden.

Sie möchten die Verwendung eines Master / Slave-Designs für die Replikation und Skalierung vermeiden (kein einzelner Fehlerpunkt). Das System vermeidet vollständig das Schreiben auf die Platte und pflegt die Datenstrukturen im Speicher.

Da dies eine Warteschlange irgendeiner Art sein soll, sollte das System in der Lage sein, unterschiedliche Planungsalgorithmen (FIFO, früheste Frist, Round-Robin usw.) zu verwenden, um zu bestimmen, welche Nachricht bei der nächsten Anfrage zurückgegeben werden sollte An welchen Knoten im Cluster die Anfrage gestellt wird.

Meine anfänglichen Gedanken Ich kann mir vorstellen, wie das auf einer einzelnen Maschine funktionieren würde, aber wenn ich anfange darüber nachzudenken, wie man etwas wie diese Fragen verteilen würde wie:

Wie würde ich jede Nachricht hashen?

Wie würde ich wissen, an welchen Knoten eine Nachricht gesendet wurde?

Wie würde ich jedes Element planen, damit ich feststellen kann, welche Nachricht und von welchem ​​Knoten als nächstes zurückgegeben werden soll?

Ich begann über verteilte Hashtabellen zu lesen und wie Projekte wie Apache Cassandra eine Art von konsistentem Hashing verwenden, um Daten zu verteilen, aber dann dachte ich, da die Abfrage keinen Schlüssel liefern wird, muss ich wissen, wo das nächste Element gerade ist versorge es ... Dies führte zum Lesen von Peer-to-Peer-Protokollen und dazu, wie sie das Synchronisationsproblem über Knoten hinweg angehen.

Also meine Frage ist, wie würden Sie ein Problem wie das oben beschriebene angehen, oder ist das zu weit hergeholt und ist einfach eine dumme Idee ...?

Nur eine Übersicht, Hinweise, verschiedene Ansätze, Fallstricke und Vorteile von jedem. Die Technologien / Konzepte / Design / Theorie, die angemessen sein können. Grundsätzlich alles, was nützlich sein könnte, um zu verstehen, wie so etwas funktionieren könnte.

Und wenn Sie sich wundern, nein, ich beabsichtige nicht, so etwas zu implementieren, es ist mir beim Lesen in den Sinn gekommen (Es passiert, dass ich durch wilde Ideen abgelenkt werde, wenn ich ein gutes Buch lese). p>

AKTUALISIEREN

Ein weiterer interessanter Punkt, der zu einem Problem werden könnte, sind verteilte Löschungen . Ich weiß, dass Systeme wie Cassandra dies durch die Implementierung von <> gelöst haben a href="http://wiki.apache.org/cassandra/HintedHandoff"> HingedHandoff , Read Repair und AntiEntropy und es scheint gut zu funktionieren, aber gibt es noch andere (praktikable und effiziente) Mittel, dies anzugehen?