Czy istnieje architektura rozproszonego geoprzetwarzania?

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.

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.

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.

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.

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.

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.

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.

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)

Zobacz OGSA-DQP. „DQP pozwala na zapytania do tabel z wielu rozproszonych relacyjnych baz danych za pomocą SQL, tak jakby w jednej bazie danych było wiele tabel” http://ogsa-dai.sourceforge.net/documentation/ogsadai4.0/ogsadai4.0- oś / DQPOverview.html