Gibt es eine Architektur für die verteilte Geoverarbeitung?

24

Angenommen, ich habe 50 Computer in meinem LAN. Jeder Computer verfügt über eine Geodatabase für alle Paketpolygone in einem bestimmten Bundesstaat in den USA.

Ich möchte eine Geoverarbeitungsaufgabe schreiben, bei der alle Flurstücke mit einem Wert über x $ / Morgen innerhalb von y Fuß eines anderen Flurstücks mit einem Wert von weniger als z $ / Morgen gefunden werden.

Ich möchte diese Abfrage formulieren und ausführen, ohne zu wissen oder zu beachten, dass die Daten auf 50 Computer verteilt sind. Beachten Sie die Randbedingungen: Ich möchte auch, dass die Abfrage Fälle zurückgibt, in denen teure Pakete in einem Bundesstaat in einem anderen Bundesstaat nahezu kostengünstige Pakete sind.

Gibt es eine Architektur, die diese Art der verteilten Geoverarbeitung unterstützt?

Die Architektur kann abstrakt oder als Implementierung speziell für Azure oder Amazon Web Services beschrieben werden. Oder vorzugsweise als typisches Büro, in dem Computer mit zahlreichen ArcGIS-Desktop-Lizenzen nachts im Leerlauf arbeiten.

geoprocessing cloud-gis amazon-web-services Kirk Kuykendall
quelle
1
Gute Frage. In diesem speziellen Beispiel benötigen Sie eine Möglichkeit, die Erstellung und Verwendung einer räumlichen Datenstruktur wie eines Quadtrees automatisch zu parallelisieren. Wenn Sie dies nicht tun und stattdessen eine Brute-Force-Suche auf 50 Computer verteilen, verlangsamen Sie möglicherweise die Abfrage, anstatt sie zu beschleunigen. Ich bin mir ziemlich sicher, dass es eine solche allgemeine Architektur noch nicht gibt. Sie sollten sich also überlegen, welche Arten von Abfragen wahrscheinlich von der verteilten Verarbeitung profitieren, und sich dann mit den erforderlichen Architekturen befassen. Vielleicht diese Frage auf der TCS-Website posten?
whuber
@whuber Danke, was ist die TCS-Site?
Kirk Kuykendall
@ Kirk Entschuldigung, dass ich kryptisch bin - ich war faul. cstheory.stackexchange.com
whuber
1
Grundlegende CS-Theorie wird wahrscheinlich nicht helfen, da die CS-Leute selten räumlich werden :-)
Ian Turton
1
@iant Es gibt nicht allzu viele GIS-Leute, die viel über die Grundlagen des Distributed Computing wissen werden. Ich glaube, die TCS-Leute werden das Wissen haben, um die ursprüngliche Frage nach der Existenz einer Architektur zu beantworten. Meine einzige Sorge ist, ob sie die Frage interessant finden würden! Ich denke, wenn es richtig ist, könnten sie. (ZB könnte man es in Bezug auf Datenstrukturen
umformulieren

Antworten:

13
  1. Speichern Sie alle Ihre Pakete in einer zentralen Datenbank
  2. Formulieren Sie ein Raster über den USA, das aus Quadraten mit N Fuß auf einer Seite besteht, wobei N so ist, dass die Anzahl der Pakete, die in N passen, den Speicher auf einem Ihrer Knoten nicht ausbläst
  3. Erstellen Sie in Ihrer Datenbank eine Tabelle mit einer Zeile pro Gitterquadrat, einer ID-Spalte, einer Geometriespalte und einer Statusspalte
  4. Jeder Knoten führt ein kleines Programm aus, das
    1. finde das nächste unbearbeitete Quadrat
    2. markiert es als in Bearbeitung
    3. zieht alle Pakete ST_DWithin (Quadrat, Paket, Maxfeet)
    4. erledigt die eigentliche Abfrage
    5. Schreibt die Abfrageantwort in eine Lösungstabelle in der zentralen Datenbank zurück
    6. markiert das Quadrat als vollständig
    7. zurück zu 1

Der offensichtliche Fehlerfall besteht darin, dass Ihr Interessensradius in der Paketabfrage so groß wird, dass große Teile Ihres Datensatzes potenzielle Kandidaten für die Übereinstimmung mit jedem Paket sind.

Paul Ramsey
quelle
Danke Paul, würde ich einen Knoten brauchen, der als Koordinator für die anderen Knoten fungiert?
Kirk Kuykendall
Die Datenbank fungiert als impliziter "Koordinator", da sie den Status der Warteschlange enthält, die Knoten müssen jedoch nicht mehr koordiniert werden, als dass sie gestartet wurden und auf die Datenbank verweisen. Nicht sicher, ob das eine Antwort ist oder nicht.
Paul Ramsey
7

Im September gab es in Barcelona einen interessanten Slot zu FOSS4G: http://2010.foss4g.org/presentations_show.php?id=3584

Es wurde mehr zu einer Podiumsdiskussion als zu einer Präsentation.

In der Mitte dieses Blogposts gibt Paul Ramsey eine Art Zusammenfassung davon.

Nicklas Avén
quelle
Das sieht vielversprechend aus, haben sie die Präsentation irgendwo veröffentlicht?
Kirk Kuykendall
Nun, da Schuyler Erle Moderator der Podiumsdiskussion wurde, anstatt die geplante Präsentation abzuhalten, glaube ich nicht, dass es viel mehr Informationen darüber geben wird. Aber da Erle diese Präsentation geplant hatte, hat er wahrscheinlich einige Informationen darüber. Er ist überall, wenn Sie eine Google-Suche durchführen. Es könnte eine Idee sein, ihn direkt zu fragen. Ich weiß es nicht. Die meisten Diskussionen waren unverständlich, daher kann ich keinen besseren Lebenslauf geben als Paul in seinem Blog.
Nicklas Avén
4

Schauen Sie sich vielleicht das Whitepaper "ArcGIS Server in Practice Series: Large Batch Geocoding" in den Whitepapers von esri an .

Es geht um die Geokodierung, aber der allgemeine Prozess der Verwendung eines asynchronen Geoverarbeitungs-Service ist möglicherweise auf Ihren Fall anwendbar.


quelle
Sieht gut aus, ich frage mich, ob dies auf andere Formen der Geoverarbeitung verallgemeinert werden könnte. Scheint, als ob ich eine Überlappung zwischen meinen Datensätzen benötigen würde.
Kirk Kuykendall
3

Das erste, was Sie mit diesem Problem zu tun haben, ist, welche Daten wo und wann benötigt werden. Dazu beginne ich normalerweise mit der blöden, seriellen Version des Problems.

Finden Sie alle Pakete mit einem Wert über x $ / Morgen, die sich innerhalb von y Fuß eines anderen Pakets mit einem Wert von weniger als z $ / Morgen befinden.

foreach p in parcels {
  if value(p) > x {
    foreach q in parcels {
      if (dist(p,q) <= y) and (value(q) < z) {
        emit(p)
      }
    }
  }
}

Dieser Algorithmus ist zwar nicht optimiert, löst jedoch das Problem.

Ein ähnliches Problem habe ich für meine Masterarbeit gelöst, bei der für jeden Punkt eines Datensatzes das nächstgelegene Paket gefunden wurde. Ich habe die Lösung in PostGIS , Hadoop und MPI implementiert . Die Vollversion meiner Dissertation ist hier , aber ich werde die wichtigen Punkte zusammenfassen, die für dieses Problem gelten.

MapReduce ist keine gute Plattform, um dieses Problem zu lösen, da für die Verarbeitung eines einzelnen Pakets der Zugriff auf den gesamten Datensatz (oder eine sorgfältig ausgewählte Teilmenge) erforderlich ist. MapReduce verarbeitet sekundäre Datasets nicht gut.

MPI kann dies jedoch recht handlich lösen. Am schwierigsten ist es, zu bestimmen, wie die Daten aufgeteilt werden sollen. Diese Aufteilung basiert darauf, wie viele Daten vorhanden sind, auf wie vielen Prozessoren Sie sie ausführen müssen und wie viel Speicher Sie pro Prozessor haben. Für eine optimale Skalierung (und damit Leistung) müssen Sie mehrere Kopien des Paketdatensatzes gleichzeitig (auf allen Ihren Computern) im Speicher haben.

Um zu erklären, wie dies funktioniert, gehe ich davon aus, dass jeder Ihrer 50 Computer über 8 Prozessoren verfügt. Ich werde dann jedem Computer die Verantwortung übertragen, 1/50 der Pakete zu prüfen. Diese Überprüfung wird von 8 Prozessen auf dem Computer ausgeführt, von denen jeder eine Kopie desselben 1/50 Teils der Pakete und 1/8 des Paketdatensatzes hat. Bitte beachten Sie, dass die Gruppen nicht auf eine einzelne Maschine beschränkt sind, sondern Maschinengrenzen überschreiten können.

Der Prozess führt den Algorithmus aus und erhält die Pakete für p aus der 1/50-Menge von Paketen und die Pakete für q aus der 1/8-Menge. Nach der inneren Schleife sprechen alle Prozesse auf demselben Computer miteinander, um zu bestimmen, ob das Paket gesendet werden soll.

Ich habe einen ähnlichen Algorithmus für mein Problem implementiert. Die Quelle finden Sie hier .

Sogar mit dieser Art von nicht optimiertem Algorithmus konnte ich beeindruckende Ergebnisse erzielen, die für die Programmiererzeit stark optimiert waren (was bedeutete, dass ich einen dummen einfachen Algorithmus schreiben konnte und die Berechnung dennoch schnell genug sein würde). Der nächste zu optimierende Punkt (wenn Sie ihn wirklich benötigen) ist das Einrichten eines Quadtree-Index des zweiten Datensatzes (von dem Sie q erhalten) für jeden Prozess.

Um die ursprüngliche Frage zu beantworten. Es gibt eine Architektur: MPI + GEOS. Wenn Sie ein wenig Hilfe von meiner ClusterGIS-Implementierung einbringen, können Sie eine ganze Menge tun. All diese Software kann als Open Source gefunden werden, daher fallen keine Lizenzgebühren an. Ich bin mir nicht sicher, wie portabel es für Windows ist (vielleicht mit Cygwin), da ich unter Linux daran gearbeitet habe. Diese Lösung kann auf EC2, Rackspace oder einer beliebigen verfügbaren Cloud bereitgestellt werden. Als ich es entwickelte, verwendete ich einen dedizierten Computercluster an einer Universität.

Nathan Kerr
quelle
2

Die Parallelprogrammierungsmethode der alten Schule besteht darin, nur einen Zustand + die Pakete, die ihn berühren, auf jedem Prozessor zu speichern, und es ist dann peinlich einfach, sie zu parallelisieren. Angesichts der unterschiedlichen Größe der US-Bundesstaaten erzielen Sie jedoch eine bessere Leistung, wenn Sie das Land in Gitterzellen aufteilen (wiederum mit dem berührenden Halo von Paketen) und jede Gitterzelle mithilfe einer Master-Slave-Konfiguration an Prozessoren senden.

Ian Turton
quelle
Anstelle von Paketen, die sich berühren, bräuchte ich Pakete aus den angrenzenden Bundesstaaten in einiger Entfernung.
Kirk Kuykendall
Ich gehe davon aus, dass Y so klein ist, dass es nicht wesentlich größer ist als eine kleine Anzahl von Paketen. Wenn es sich um einen großen Bruchteil eines Staates handelt, ist es wahrscheinlich am besten, nur ein willkürliches Gitter zu verwenden, um die Berechnungen durchzuführen.
Ian Turton
2

Vielleicht möchten Sie Appistry einen Blick geben. Es soll die Migration bestehender Anwendungen auf private Cloud-Infrastrukturen ermöglichen. Möglicherweise gibt es andere Projekte mit einem ähnlichen Ziel: Anstatt für jede Anwendung immer wieder herauszufinden, wie komplex es ist, Aufgaben zu zerlegen und an die parallele Verarbeitung zu verteilen, erstellen Sie eine Bibliothek oder Plattform, die dies automatisch erledigt.

Matt Wilkie
quelle
Danke Matt, das sieht vielversprechend aus. Googeln ich diese Präsentation von FedUC 2008 gefunden proceedings.esri.com/library/userconf/feduc08/papers/... würde ich gespannt sein , ein Update auf , um zu sehen , was sie seitdem getan haben.
Kirk Kuykendall
2

Für diese Art von Problem würde ich ein Map / Reduce-Framework verwenden. Das "rohe" Appistry-Framework eignet sich hervorragend für "peinlich parallele" Probleme, denen dieses nahe steht. Die Randbedingungen lassen es nicht zu. Map / Reduce (der Google-Ansatz für verteiltes Computing) ist bei dieser Art von Problem großartig.

Der größte Fortschritt bei Appistry seit dem 08-Papier ist die Veröffentlichung des CloudIQ Storage-Produkts. Dies ermöglicht eine "s3" -ähnliche Speichereinrichtung, bei der die Festplatten auf Ihren lokalen Servern verwendet werden. Dann kann das CloudIQ Engine-Produkt hochvolumige Dienste oder Anwendungen im Scatter / Gather-Stil jeder Art ermöglichen (wir haben die Skalierbarkeit mit ESRI-Laufzeit und anderen Open Source-Bibliotheken bewiesen). Wenn Sie dateibasierte Daten verarbeiten, verteilen Sie diese mit CloudIQ Storage und leiten Verarbeitungsaufträge an die lokalen Dateireplikate weiter, damit diese nicht im Netzwerk verschoben werden müssen. (so dass nicht jeder Knoten alle Daten benötigt)

Für Map / Reduce können Sie so etwas wie Hadoop (Open Source M / R Framework) auf CloudIQ Storage legen. Ich würde Hadoop nach dem beschriebenen Problem untersuchen, aber Sie müssen wirklich eintauchen, es ist nicht einfach, damit anzufangen, und M / R ist ein Gehirnbrecher. Es gibt auch eine kommerziell unterstützte Distribution, die von Cloudera angeboten wird. Es gibt ein anderes Appistry-Produkt, CloudIQ Manger, das eine gute Ergänzung zu Hadoop (Cloudera oder anders) für Vertrieb und Verwaltung darstellt.

Ich würde mit Hadoop (M / R- und HDFS-Dateisystem) beginnen. Wenn Sie eine kommerziell besser unterstützte skalierbare Lösung benötigen, schauen Sie sich Appistry CloudIQ Manager und Storage in Verbindung mit Cloudera Hadoop Distribution an.

Wenn Sie eine einfachere Architektur für "peinlich parallele" Aufgaben wünschen, schauen Sie sich auch CloudIQ Engine an. (Die Ansätze in dem Artikel, auf den Kirk verweist, sind weiterhin gültig.)


quelle