Czy istnieje architektura rozproszonego geoprzetwarzania?

24

Załóżmy, że mam 50 komputerów w mojej sieci LAN. Każdy komputer ma geobazę dla wszystkich wielokątów paczek w określonym stanie w USA.

Chciałbym napisać zadanie Geoprzetwarzania który wyszukuje wszystkie paczki o wartości ponad x $ / akr, które są w zasięgu y nogi innej działce, która jest szacowana na mniej niż z $ / akr.

Chciałbym sformułować i uruchomić to zapytanie, nie wiedząc ani nie dbając o to, że dane są rozproszone na 50 komputerach. Pamiętaj o warunkach brzegowych: chcę również, aby zapytanie zwróciło przypadki, w których drogie paczki w jednym stanie są prawie niedrogie w innym.

Czy istnieje architektura obsługująca tego rodzaju rozproszone geoprzetwarzanie?

Architektura może być opisana abstrakcyjnie lub jako implementacja specyficzna dla Azure lub Amazon Web Services. Lub, najlepiej, jako typowe biuro, w którym komputery siedzą bezczynnie w nocy z dużą liczbą licencji ArcGIS na komputery.

Kirk Kuykendall
źródło
1
Fajne pytanie. W tym konkretnym przykładzie potrzebujesz sposobu, aby automatycznie zrównoleglić budowę i wykorzystanie struktury danych przestrzennych, takich jak drzewo czterokąta. Jeśli tego nie zrobisz, a zamiast tego rozprowadzisz wyszukiwanie metodą brutalnej siły na 50 komputerach, możesz faktycznie spowolnić zapytanie, a nie przyspieszyć. Jestem pewien, że taka ogólna architektura jeszcze nie istnieje, więc możesz mieć więcej szczęścia, najpierw zastanawiając się, jakie rodzaje zapytań prawdopodobnie skorzystają na przetwarzaniu rozproszonym, a następnie przyjrzyj się wymaganym architekturom. Może opublikujesz to pytanie na stronie TCS?
whuber
@whuber Dzięki, jaka jest strona TCS?
Kirk Kuykendall
@Kirk przepraszam, że jestem tajemniczy - byłem leniwy. cstheory.stackexchange.com
whuber
1
podstawowa teoria CS prawdopodobnie nie pomoże, ponieważ faceci CS rzadko stają się przestrzenni :-)
Ian Turton
1
@iant Nie ma zbyt wielu ludzi z GIS, którzy będą dużo wiedzieć o zaletach przetwarzania rozproszonego (nie rzucam żadnych podejrzeń na członków tej witryny, którzy oczywiście są wyjątkowi). Wierzę, że ludzie TCS będą mieli wiedzę, aby odpowiedzieć na pierwotne pytanie dotyczące istnienia architektury. Moją jedyną obawą jest to, czy uznają to pytanie za interesujące! Myślę, że jeśli jest to właściwe, mogą. (Np. Można go
przeformułować

Odpowiedzi:

13
  1. przechowuj wszystkie swoje paczki w jednej centralnej bazie danych
  2. utwórz siatkę nad USA z kwadratów N stóp na boku, gdzie N jest taka, że ​​liczba działek mieszczących się w N nie zniszczy pamięci na jednym z twoich węzłów
  3. utwórz tabelę w bazie danych z jednym rzędem na kwadrat siatki, kolumną id, kolumną geometrii i kolumną stanu
  4. każdy węzeł uruchamia mały program, który
    1. znajdź następny nieprzetworzony kwadrat
    2. oznacza to jako w toku
    3. ściąga wszystkie paczki ST_DWithin (kwadrat, paczka, maxfeet)
    4. wykonuje aktualne zapytanie
    5. zapisuje odpowiedź na zapytanie w tabeli rozwiązań w centralnej bazie danych
    6. oznacza kwadrat jako kompletny
    7. Wróć do 1

Oczywistym przypadkiem niepowodzenia jest to, że twój promień zainteresowania w zapytaniu o paczkę rośnie na tyle, że duże części twojego zestawu danych są potencjalnymi kandydatami do dopasowania do każdej paczki.

Paul Ramsey
źródło
Dzięki Paul, czy potrzebowałbym jednego węzła działającego jako koordynator dla innych węzłów?
Kirk Kuykendall
Baza danych działa jako domyślny „koordynator”, ponieważ utrzymuje stan kolejki, ale węzły nie muszą być koordynowane poza uruchomieniem i wskazaniem na bazę danych. Nie jestem pewien, czy to odpowiedź, czy nie.
Paul Ramsey,
7

Na FOSS4G we wrześniu w Barcelonie pojawił się interesujący automat: http://2010.foss4g.org/presentations_show.php?id=3584

Stało się bardziej dyskusją panelową niż prezentacją.

W środku tego wpisu na blogu Paul Ramsey podaje podsumowanie.

Nicklas Avén
źródło
To wygląda obiecująco, czy opublikowali prezentację gdziekolwiek?
Kirk Kuykendall
Odkąd Schuyler Erle stała się moderatorem dyskusji panelowej, zamiast organizować planowaną prezentację, nie sądzę, że będzie więcej informacji na jej temat. Ale skoro Erle zaplanował tę prezentację, prawdopodobnie ma o niej trochę informacji. Jest wszędzie, jeśli przeprowadzisz wyszukiwanie w Google. Zapytanie go bezpośrednio może być pomysłem. Nie wiem Większość dyskusji była ponad moim zrozumieniem, więc nie mogę dać lepszego podsumowania niż Paul na swoim blogu.
Nicklas Avén
4

Może rzucisz okiem na białą księgę „ArcGIS Server in Practice Series: Large Batch Geocoding” na esri białych kartkach .

Chodzi o geokodowanie, ale ogólny proces korzystania z asynchronicznej usługi geoprzetwarzania może mieć zastosowanie w twoim przypadku.


źródło
Wygląda dobrze, zastanawiam się, czy można by to uogólnić na inne formy geoprzetwarzania. Wydaje mi się, że potrzebuję nakładania się między moimi zestawami danych.
Kirk Kuykendall
3

Pierwszą rzeczą, na którą należy zwrócić uwagę w związku z tym problemem, jest to, jakie dane są potrzebne gdzie i kiedy. Aby to zrobić, zwykle zaczynam od głupiej, seryjnej wersji problemu.

Znajdź wszystkie działki o wartości powyżej x $ / akr, które znajdują się w odległości y stóp od innej działki o wartości mniejszej niż z $ / akr.

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

Chociaż ten algorytm nie jest zoptymalizowany, rozwiąże problem.

Podobny problem rozwiązałem w mojej pracy magisterskiej, która znalazła najbliższą paczkę dla każdego punktu w zbiorze danych. Zaimplementowałem rozwiązanie w PostGIS , Hadoop i MPI . Pełna wersja mojej pracy dyplomowej jest tutaj , ale podsumuję ważne punkty, które dotyczą tego problemu.

MapReduce nie jest dobrą platformą do rozwiązania tego problemu, ponieważ wymaga dostępu do całego zestawu danych (lub starannie wybranego podzbioru) w celu przetworzenia pojedynczej paczki. MapReduce nie radzi sobie dobrze z dodatkowymi zestawami danych.

MPI może jednak całkiem łatwo to rozwiązać. Najtrudniejsze jest określenie sposobu podziału danych. Podział ten opiera się na ilości danych, liczbie procesorów, na których trzeba je uruchomić oraz ilości pamięci na procesor. Aby uzyskać najlepsze skalowanie (a tym samym wydajność), musisz mieć jednocześnie wiele kopii zestawu danych paczek w pamięci (na wszystkich komputerach).

Aby wyjaśnić, jak to działa, założę, że każdy z 50 komputerów ma 8 procesorów. Następnie przypiszę każdemu komputerowi odpowiedzialność za sprawdzenie 1/50 paczek. To sprawdzenie zostanie wykonane przez 8 procesów na komputerze, z których każdy ma kopię tej samej 1/50 części paczek i 1/8 zestawu danych paczki. Należy pamiętać, że grupy nie są ograniczone do jednego komputera, ale mogą przekraczać granice komputera.

Proces wykona algorytm, uzyskując paczki dla p z 1/50 zestawu paczek, a paczki dla q z 1/8 zestawu. Po wewnętrznej pętli wszystkie procesy na tym samym komputerze będą ze sobą rozmawiać, aby ustalić, czy paczka powinna zostać wysłana.

Zaimplementowałem algorytm podobny do tego dla mojego problemu. Możesz znaleźć źródło tutaj .

Nawet z tego rodzaju niezoptymalizowanym algorytmem byłem w stanie uzyskać imponujące wyniki, które były wysoce zoptymalizowane pod kątem czasu programisty (co oznacza, że ​​mogłem napisać głupi prosty algorytm, a obliczenia nadal byłyby wystarczająco szybkie). Następnym miejscem do zoptymalizowania (jeśli naprawdę jest to potrzebne) jest ustawienie indeksu poczwórnego drugiego zestawu danych (skąd otrzymujesz q z) dla każdego procesu.


Aby odpowiedzieć na oryginalne pytanie. Istnieje architektura: MPI + GEOS. Dodaj trochę pomocy z mojej implementacji ClusterGIS i całkiem sporo można zrobić. Całe to oprogramowanie można znaleźć jako oprogramowanie typu open source, więc nie ma opłat licencyjnych. Nie jestem pewien, jak przenośny jest dla systemu Windows (może z Cygwinem), ponieważ pracowałem nad nim w systemie Linux. To rozwiązanie można wdrożyć w EC2, Rackspace lub dowolnej dostępnej chmurze. Kiedy go opracowałem, korzystałem z dedykowanego klastra obliczeniowego na uniwersytecie.

Nathan Kerr
źródło
2

Metodą programowania równoległego starej szkoły jest po prostu przechowywanie stanu + paczek, które dotykają go na każdym procesorze, a następnie jest kłopotliwie łatwe do zrównoleglenia. Biorąc jednak pod uwagę różnice w wielkości stanów USA, można uzyskać lepszą wydajność, dzieląc kraj na komórki siatki (ponownie z dotykającą aureolą paczek) i wysyłając każdą komórkę siatki do procesorów przy użyciu konfiguracji master slave.

Ian Turton
źródło
Zamiast paczek, które się dotykają, potrzebowałbym paczek z sąsiednich stanów w odległości y.
Kirk Kuykendall
Zakładam, że Y jest na tyle mniejsze, że nie jest znacznie większe niż niewielka liczba paczek. Jeśli jest to duży ułamek stanu, prawdopodobnie najlepiej byłoby użyć dowolnej siatki do wykonania obliczeń.
Ian Turton
2

Możesz rzucić okiem na Appistry . Ma to umożliwić migrację istniejących aplikacji do infrastruktury chmury prywatnej. Mogą istnieć inne projekty o podobnym celu: zamiast zastanawiać się nad każdą aplikacją bardzo złożoną nutą podziału i podziału zadań na przetwarzanie równoległe, stwórz bibliotekę lub platformę, która robi to automatycznie.

matowe wilkie
źródło
Dzięki Matt, to wygląda obiecująco. Googlowania znalazłem tę prezentację z FedUC 2008 proceedings.esri.com/library/userconf/feduc08/papers/... byłbym ciekaw, aktualne informacje na temat tego, co zrobili od tego czasu.
Kirk Kuykendall
2

W przypadku tego typu problemu użyłbym frameworku mapuj / zmniejsz. „Surowa” struktura Appistry doskonale nadaje się do „kłopotliwie równoległych” problemów, do których ten jest bliski. Warunki brzegowe na to nie pozwalają. Map / Reduce (podejście Google do przetwarzania rozproszonego) doskonale sprawdza się w tego typu problemach.

Największym postępem w Appistry od czasu publikacji 08 jest wydanie produktu CloudIQ Storage. Pozwala to na przechowywanie danych w stylu „s3” przy użyciu dysków na lokalnych serwerach. Następnie produkt CloudIQ Engine może włączyć usługi o dużej objętości lub dowolne aplikacje rozpraszające / zbierające (sprawdziliśmy skalowalność za pomocą środowiska uruchomieniowego ESRI i innych bibliotek open source). Jeśli operujesz na danych opartych na plikach, rozprowadzasz je za pomocą CloudIQ Storage i kierujesz zadania przetwarzania do lokalnych replik plików, aby nie musiały być przenoszone w sieci. (więc każdy węzeł nie potrzebuje wszystkich danych)

W przypadku Map / Reduce możesz nałożyć warstwę podobną do Hadoop (framework M / R open source) w CloudIQ Storage. Chciałbym spojrzeć na Hadoopa w celu opisania problemu, ale naprawdę musisz się zanurzyć, nie jest łatwo zacząć, a M / R jest mózgiem. Istnieje również komercyjnie wspierana dystrybucja oferowana przez Cloudera. Istnieje inny produkt Appistry, CloudIQ Manger, który jest miłym uzupełnieniem Hadoop (Cloudera lub w inny sposób) do dystrybucji i zarządzania.

Zacznę od Hadoop (system plików M / R i HDFS), a jeśli potrzebujesz bardziej skalowalnego rozwiązania obsługiwanego komercyjnie, spójrz na Appistry CloudIQ Manager and Storage, w połączeniu z dystrybucją Cloudera Hadoop.

Jeśli chcesz prostszej architektury do zadań „krępujących równolegle”, spójrz również na CloudIQ Engine. (podejścia przedstawione w dokumencie, do którego odwołuje się Kirk, są nadal aktualne)


źródło