Verteiltes Rechnen mit Javascript und Google Gears
Wie ich ja bereits des öfteren anmerkte, habe ich früher ein Browsergame programmiert. Begonnen habe ich 2003, als es erst recht wenige Browsergames gab, und diese auch alle von Privatleuten als Hobby betrieben wurden. Da man natürlich Alleinstellungsmerkmale braucht gegen „die Konkurrenz“, baut man viele Ideen ein, die andere nicht haben. Unter anderem war in meinem Browsergame (es handelte sich um ein Aufbauspiel a la OGame, Stoneage etc.) das erste Mal auch ein Turniermodus (1on1) möglich, so dass man abseits der lang laufenden Welten auch in einem KO-Modus gegen andere antreten konnte. Dazu wurden Speed-Server für die ausgelosten Paare gestartet, wo dann 2 Spieler gegeneinander antreten mussten und gewisse Siegbedingungen erreichen mussten. ICQ-Benachrichtigungen bei bestimmten Ereignissen hatte ich auch recht früh eingebaut.
In der folgende Version (die leider nie das Licht der Welt erblickt hat) kamen noch viele weitere interessante Features hinzu. Der Quellcode wurde komplett neu geschrieben in PHP5, war nun voll objektorientiert (in PHP4 war das ja nur sehr beschränkt möglich), und auch neue „Web2.0“ Funktionalitäten waren mit drin.
So gab es zum Beispiel eine Möglichkeit, dass Spieler sich selbst Weltkarten zusammenbauen konnten mit einem einfachen Editor. Der Spieler hat dazu mehrere Feldtypen (Gras, Fels, Wasser, Berg, Moor) und kann daraus eine Karte basteln, auf der er dann gegen andere antreten kann (und wenn sie gut bewertet wird, kann es auch eine Karte für einen „großen“ Server werden, wo tausende Spieler drauf spielen). Eines der Probleme, die es dabei gab, war die Berechnung der Wege. Man muss, um seine Armee zu bewegen, nur das Zieldorf anwählen und kann dort angreifen. Der Dijkstra-Algorithmus bestimmt dann die Zeit, die die Armee unterwegs ist. Dazu muss man den genauen Weg kennen, denn es gibt auch unpassierbares Gelände (in diesem Fall Berge) oder Flächen, auf denen die Armee langsamer ist (Moor). Da die Karten mitunter sehr groß sind (zB 1000*1000), dauert diese Berechnung recht lang. Diese Berechnung bei jeder Armeebewegung zu machen macht die Webseite ziemlich lahm. Also habe ich für die „Standardkarten“ diese Berechnungen bereits erledigt und die 500.000 Ergebnisse (von jedem Feld zu jedem anderen) in einer Datenbank gespeichert.
Wenn nun aber viele Spieler neue Karten basteln, schafft das der Server nicht mehr, er muss ja auch nebenbei noch für die eigentlichen Webseiten und Datenbanken herhalten. Eine Berechnung für eine Karte dauert mitunter 20 Stunden (Dijkstra Algorithmus in PHP).
Was also tun? Richtig, wir verteilen die Arbeit auf die Client-Rechner. Die 500 Spieler, die auf der Webseite rumsurfen und das Spiel spielen, können nebenbei auch bei der Berechnung helfen. Doch wie macht man das? Aufwendige Dinge wie ein eigenes Client-Programm schreiben, oder Plugins für BOINC etc. sind zu aufwändig und übertrieben. Wie so häufig gibt es eine einfache Lösung: Gears von Google.
Mit Gears kann man asynchron Javascripte ausführen, die die Webseite nicht beeinträchtigen, indem man sogenannte WorkerPools mit Arbeit versorgt.
Hier habe ich mal ein einfaches Beispiel:
main.html
<script type="text/javascript" src="gears_init.js"></script>
<script type="text/javascript">
var workerPool = google.gears.factory.create('beta.workerpool');
workerPool.onmessage = function(a, b, message) {
alert('result from worker ' + message.sender + ': \n' + message.body);
};
var childWorkerId = workerPool.createWorkerFromUrl('worker2.js');
workerPool.sendMessage([5, 1, 8], childWorkerId);
</script>
worker2.js:
var wp = google.gears.workerPool;
wp.onmessage = function(a, b, message) {
// do calculation here
var reply = message.body[0] + message.body[1] + message.body[2];
wp.sendMessage(reply, message.sender);
}
Wenn man die entsprechende Webseite aufruft, wird man gefragt, ob der Zugriff auf Gears erlaubt werden soll. Wenn man Gears installiert hat, kann man also noch von Fall zu Fall unterscheiden, ob man der Webseite seine Resourcen zur Verfügung stellen möchte oder nicht.
Was passiert nun? Die Webseite startet einen WorkerPool, in diesem Workerpool wird ein Worker gestartet, der das Script worker2.js ausführen soll. Wir senden an den darin befindlichen Worker ein Array mit 3 Zahlen.
Der Worker errechnet dann die Summe dieser Zahlen, und sendet das Ergebnis zurück an den WorkerPool. Diese Nachricht fangen wir mit dem „onMessage“ Eventhandler ab und zeigen das Ergebnis mittels alert() an.
Wie würde nun die Kartenberechnung funktionieren? Wir übergeben statt dem einfachen Array ein komplexes großes Array mit dem Graphen, den Kantengewichten usw. Im Worker findet dann die eigentliche Dijkstra-Berechnung statt. Dort wäre es sinnvoll, nicht die ganze Karte zu berechnen (Dauer 20 Stunden), sondern nur kleine Häppchen, die in wenigen Sekunden bearbeitet sind. Statt das Ergebnis dann via alert() auszugeben, schicken wir es via AJAX zurück an den Webserver, der das Ergebnis in die Datenbank einträgt.
Leider ist es bei diesen ersten Tests geblieben, ich habe die eigentlichen umfangreichen Dijkstra-Berechnungen nie in Javascript mit Gears umgesetzt. Aber möglich ist es.
Eine einzige Hürde gibt es: Auf dem Clientrechner muss Gears installiert sein. Mit einer guten Community und Nutzern, die einem vertrauen, ist aber auch das machbar.
Alternativ kann man natürlich auch ohne Gears die Berechnungen in Javascript durchführen lassen. Dabei muss man jedoch beachten, dass der Browser dadurch nicht unbenutzbar wird. Man muss also die Berechnung künstlich bremsen, außerdem muss man eine Lösung dafür finden, dass der Browser lang laufende Javascripte gern auch mal abbrechen möchte.
Mit Gears passiert sowas nicht.
Anwendungsfälle des Dijkstra-Algorithmus sind beispielsweise das bekannte „Friend of a Friend“ Problem (soziale Netzwerke zeigen an, über wieviele Kontakte man eine andere Person kennt) oder alle anderen Arten, wo man in einem Graphen den kürzesten Pfad ermitteln möchte. Man kann so sicherlich auch noch andere, komplexe Berechnungen auf die Clients auslagern.
Gears kann man natürlich auch noch für viele weitere Dinge nutzen, wie schöne Benachrichtigungen, als lokalen Speicher für Dateien oder Daten (Datenbank), Geolocation (was ja mittlerweile die Browser schon nativ beherrschen) usw.
Habt ihr Erfahrungen mit Gears, oder Ideen welche revolutionären Dinge man damit umsetzen könnte?
Klingt sehr interessant, das würd ich auch mal benutzen. Das gute daran ist, es ist dann auch plattformunabhängig.
maTTes
30 Sep 09 at 14:59
Ja, potenziell mächtig klingt das schon. NUR: grad für einen Anwendungsfall wie den von dir beschriebenen (Browsergame) würde ich eben _nicht_ irgendwelche spielbeeinflussenden Berechnungen auf nem Client laufen lassen. Oder wie filterst du raus, ob der Client die Berechnung richtig abgewickelt (bzw. nicht manipuliert) hat? Auf dem Server nochmal nachrechnen und die Wege vergleichen?
Vielleicht gäbs da ja ne clevere Lösung…?
Lukas
1 Okt 09 at 07:37
Da hast du recht, da müsste man wirklich zur Sicherheit die Berechnungen von 2 verschiedenen Clients machen lassen (also alles doppelt), damit man relativ sicher sein kann, dass nichts manipuliert wurde. Guter Punkt!
Ich weiß gar nicht wie andere Grid Computing Projekte das machen. Sprich sich gegen falsche Ergebnisse zu schützen.
Man könnte außerdem noch fix das Ergebnis auf grobe Fehler untersuchen, beispielsweise kann es zu einem Feld (bei einer quadratischen Welt, keine Oktaeder) nur 8 Felder geben, die zu einem bestimmten Feld den Abstand 1 haben. Solche einfachen Prüfungen könnte man auf dem Server noch erledigen.
Aber dein Hinweis ist wichtig, und man sollte nie vergessen: Alle Informationen, die vom Client kommen (und dazu zählen auch solche Berechnungsergebnisse) sind potentiell manipuliert.
Michael Kliewe
1 Okt 09 at 09:49
hmm also eine sinnvolle Maßnahme wäre es meiner Meinung nach, die Übertragung der Ergebnisse zu verschlüsseln. Andere Projekte wie BOINC haben halt den Vorteil, dass sie den Algorithmus zur Berechnung der Ergebnisse nicht offenlegen müssen, da die ja (soweit ich weiß) fertig kompilierte programme rausgeben. Mit JS hat man halt immer den Nachteil, dass der Quellcode offenliegt und damit auch die Übertragung, das Format etc.
Berechnung von 2 Clients: eine Möglichkeit, die allerdings auch keine wirklich hohe Sicherheit bringt. Ich könnte ja zB mit 2 Rechnern das Ergebnis manipulieren und so in meine selbst kreierte Karte einen „gekürzten“ Weg einbauen und damit (böse wie ich ja bin 😉 meine eigenen „Bugs“ ins System einschleusen…
bin gespannt, was uns hierzu noch einfällt
Lukas
1 Okt 09 at 09:58
Verschlüsseln ist bei Javascript leider keine Alternative wie du schon sagtest.
Um mit 2 Rechnern das Ergebnis zu manipulieren, müßtest du 2 Accounts haben und IP-Adresse wechseln, Cookies löschen, Gears-Speicher löschen und alles weitere unternehmen, was dich als „Multi“ enttarnen könnte. Und dann müßtest du noch das Glück haben, dass der Server dir die selben zu berechnenden Wege zuteilt. Es ist wahrscheinlicher, dass irgendwer anders deine Ergebnisse gegenrechnet, und wenn dabei Probleme auftauchen, all deine Ergebnisse verworfen werden (nicht nur das falsche Ergebnis, sondern alle Ergebnisse deines Rechners/Accounts) bzw. deine Accounts für die Berechnung gesperrt werden.
Da du der Bad-Boy bist, was könntest du dagegen machen? 😉
Michael Kliewe
1 Okt 09 at 10:13
trotz der berechtigen kritikpunkte, sehr interessanter anwendungsfall…
dcdieci
1 Okt 09 at 10:52
@Michael:
klar du hast schon recht, es wird da schon seehr schwer, unbemerkt reinzukommen. Mir gings auch nicht darum, die Technik an sich zu kritisieren, sondern eventuell eine Lösung zu finden, diese Möglichkeit by design sicher einzusetzen.
Lukas
1 Okt 09 at 11:20
Eine Lösung „by design“ wäre wirklich interessant, mir fällt nach wie vor keine ein. Das Wesen von Javascript ist nunmal offen liegender, manipulierbarer Code, daran wird sich auch nichts ändern fürchte ich.
Früher war eine andere Alternative, ein Flash-Applet zu basteln, was die Berechnung auf Clientseite übernimmt. Das ist zwar auch decompilierbar, aber etwas aufwändiger. Aber da hat man auch wieder das Problem, dass der Browser dadurch arg verlangsamt wird. Die Idee mit den browserunabhängigen WorkerPools gefällt mir da besser.
Ich könnte mir auch vorstellen, dass viele Script-Kiddys allein durch Javascript Obfuscating schon den Spass daran verlieren, die Berechnung nachzuvollziehen, dann wirds auch sehr aufwändig für den „Hacker“. Aber auch das ist keine Sicherheit, auf die man sich verlassen kann.
Michael Kliewe
1 Okt 09 at 11:39
das ist genau das, was ich meinte – durch Sachen wie doppelte Berechnung und Abgleich, Code-Obfuscating etc. wirds zwar sehr schwierig, die Ergebnisse zu manipulieren, aber eben nicht unmöglich. Trotzdem eine sehr interessante Idee, die ich sicher weiterverfolgen werde.
Lukas
1 Okt 09 at 12:12
Du hast dutzende (bestimmt dreistellig 😉 Stunden Arbeit in die neue Version deines Browserspiels gesteckt und diese nie veröffentlicht?
Was ist passiert? :-O
Sven
1 Okt 09 at 14:50
@Sven: Du hast Recht, sowas ist sehr aufwändig. Das war auch ein Grund, weshalb ich es dann irgendwann aufgehört habe. In die erste Version habe ich damals ca. 1100 Stunden gesteckt (reine Entwicklung, dazu kam noch der Spielsupport etc).
Die zweite Version war zu ~80% fertig, aber das Ende des Studiums, keine Lust mehr, und vor allem allein (es fand sich einfach niemand, der mitmachen wollte) zu programmieren war dann der letzte Nagel im Sarg.
Es ging natürlich darum, etwas großes im Internet präsentieren zu können, aber auch das Lernen von PHP bis ins Letzte, Performance-Tuning von PHP, Mysql, Apache-Tuning, Erfahrung mit Projektmanagement, CodeStyles, Versionskontrolle usw habe ich hautnah damals schon kennengelernt, das kann man nicht mit einem kleinen Webseiten-Projekt vergleichen. Und diese Erfahrungen sind Gold wert.
Leider ist es heutzutage alles zu kommerziell geworden. Es gibt tausende sehr gute Browsergames, hinter vielen davon stecken große Firmen, die sehr viel Hardware und Manpower haben, großartige Ajax-Spiele, Flash-Spiele, Java-Spiele erstellen. Und mittlerweile muss man ja schon auf den 3D-Browser-Plugin-Zug aufspringen, denn in nicht allzu ferner Zukunft werden da die Spiele aus dem Boden sprießen, wo OpenGL im Browser möglich wird, und man Spiele nicht mehr kauft und installiert, sondern 3D-Spiele im Browser spielt.
Die Zukunft wird es zeigen.
Michael Kliewe
1 Okt 09 at 16:52
Moin.
Auch wenn das eigentliche Thema deines Artikels das verteilte Rechnen war, so habe ich mir dennoch Gedanken über das graphentheoretische Problem gemacht. Wenn ich es richtig verstanden habe, dann hast du den Dijkstra-Algorithmus für jedes Koordinatenpaar ausgeführt? Die Verwendung des Algorithmus von Floyd und Warshall [1] wäre bestimmt effizienter gewesen.
Hast du Beispieldaten für eine Karte, bei der die Zeit 20h betrug, noch zur Hand? Ich würde mich gerne daran versuchen. 🙂
gez. Andre
[1] http://de.wikipedia.org/wiki/Floyd-Warshall-Algorithmus
Andre Moelle
2 Okt 09 at 21:08
Puh, das ist schon einige Jahre her, ich durchsuch morgen mal die Festplatte danach… Soll ich dir das mal zukommen lassen via Email?
Michael Kliewe
2 Okt 09 at 21:17
Ich lasse gerade nochmal einige Berechnungen durchlaufen, morgen gibt es die Details, woran du dich versuchen kannst. Würde mich sehr drüber freuen wenn du es mal mit dem Floyd-Warshall versuchen würdest.
Michael Kliewe
4 Okt 09 at 00:40
Irgendwie habe ich keine E-Mail erhalten, dass du geantwortet hast. Merkwürdig… Deshalb kommt meine Antwort zwei Tage zu spät. :-/ Ja, per E-Mail wäre am besten. Die E-Mailadresse kannst du ja einsehen.
Andre Moelle
4 Okt 09 at 11:16
Laut dem Mail-Log ist auch keine Email verschickt worden. Bist du sicher, dass du das Thema auch abboniert hattest? Aktuell ist es abboniert.
Ich poste heute Nachmittag/Abend einen neuen Artikel zu dem Thema, wenn meine Berechnungen hier gelaufen sind, dann kannst du loslegen.
Edit: Nun hast du eine Benachrichtung bekommen laut Mail-Log. Ich würde tippen, dass du das Häkchen vergessen hattest 😉
Michael Kliewe
4 Okt 09 at 12:05
Ich war der festen Auffassung, dass ich es bereits abonniert hätte… So täuscht man sich. 🙂 Habe es jedenfalls bei meiner letzten Antwort aktiviert und da hat es auch funktioniert.
Den Artikel erwarte ich mit Spannung. 🙂
Andre Moelle
4 Okt 09 at 12:17
[…] zu einem älteren Artikel über Google Gears hier eine kurze Statusmeldung: Mittlerweile sind die modernen Browser (zur Zeit Firefox 3.5, Safari […]
Javascript Web Worker | PHP Gangsta - Der PHP Blog
28 Okt 09 at 21:24
As we have knowledge fantastic releases just about discount-program, people must receive the essay writing services just about this good post.
Chloe21
26 Jan 10 at 00:13
[…] Herunterfahren als Dienst gestarteter VM – VMware Workstation – VMware Forum Verteiltes Rechnen mit Javascript und Google Gears | PHP Gangsta – Der PHP Blog What is entity-relationship model? | EXPLAIN EXTENDED YouTube – Conkers Bad Fur Day […]
Linkliste 16 at Random People
25 Jan 11 at 06:09