Существует ли архитектура распределенной геообработки?

24

Предположим, у меня есть 50 компьютеров в локальной сети. Каждый компьютер имеет базу геоданных для всех полигонов участков в определенном штате США.

Я хотел бы написать задачу геообработки, которая находит все участки стоимостью более x $ / акр, которые находятся в пределах y футов от другого участка стоимостью менее z $ / акр.

Я хотел бы сформулировать и выполнить этот запрос, не зная и не заботясь о том, что данные распределены по 50 компьютерам. Помните о граничных условиях: я также хочу, чтобы запрос возвращал случаи, когда дорогие посылки в одном штате находятся рядом с недорогими посылками в другом.

Существует ли архитектура, поддерживающая такого рода распределенную геообработку?

Архитектура может быть описана абстрактно или как реализация, специфичная для Azure или Amazon Web Services. Или, предпочтительно, в качестве типичного офиса, где компьютеры бездействуют ночью с многочисленными лицензиями ArcGIS для настольных ПК.

geoprocessing cloud-gis amazon-web-services Кирк Куйкендалл
источник
1
Хороший вопрос В этом конкретном примере вам нужен способ автоматического распараллеливания построения и использования пространственной структуры данных, такой как дерево квадрантов. Если вы этого не сделаете, а просто распределите поиск методом перебора по 50 компьютерам, вы можете на самом деле замедлить запрос, а не ускорить его. Я почти уверен, что такой архитектуры как таковой еще не существует, так что вам, возможно, повезет больше, если сначала подумать, какие типы запросов могут получить выгоду от распределенной обработки, а затем изучить архитектуры, которые им требуются. Может быть, разместить этот вопрос на сайте TCS?
whuber
@whuber Спасибо, что такое сайт TCS?
Кирк Куйкендалл
@ Кирк извините за то, что я загадочный - мне было лень. cstheory.stackexchange.com
whuber
1
базовая теория CS, вероятно, не поможет, так как парни из CS редко становятся пространственными :-)
Ian Turton
1
@iant Не так уж много людей из ГИС, которые собираются много знать о гайках и минусах распределенных вычислений (я не намекаю на членов этого сайта, которые, очевидно, являются исключительными). Я верю, что люди TCS будут иметь знания, чтобы ответить на первоначальный вопрос о существовании архитектуры. Мое единственное беспокойство - найдут ли они вопрос интересным! Я думаю, если это правильно, они могли бы. (Например, можно перефразировать его с точки зрения структур данных.)
whuber

Ответы:

13
  1. хранить все ваши посылки в одной центральной базе данных
  2. сформулируйте сетку по США, состоящую из квадратов N футов на стороне, где N таково, что количество посылок, которые вписываются в N, не будет выбрасывать память на одном из ваших узлов
  3. создать таблицу в вашей базе данных с одной строкой на квадрат сетки, столбцом id, столбцом геометрии и столбцом состояния
  4. каждый узел запускает небольшую программу, которая
    1. найти следующий необработанный квадрат
    2. помечает это как незавершенное
    3. вытягивает все посылки ST_DWithin (квадрат, посылка, maxfeet)
    4. делает фактический запрос
    5. записывает ответ на запрос в таблицу решений в центральной базе данных
    6. помечает квадрат как завершенный
    7. вернуться к 1

Очевидный случай сбоя заключается в том, что ваш радиус интереса в запросе на посылку становится достаточно большим, так что большие части вашего набора данных являются потенциальными кандидатами для соответствия каждой посылке.

Пол Рэмси
источник
Спасибо, Пол, мне нужен один узел, выступающий в качестве координатора для других узлов?
Кирк Кайкендалл
База данных действует как неявный «координатор» в том смысле, что она хранит состояние очереди, но узлы не должны координироваться после запуска и указания на базу данных. Не уверен, если это ответ или нет.
Пол Рэмси
7

В сентябре в Барселоне на FOSS4G был интересный слот на эту тему: http://2010.foss4g.org/presentations_show.php?id=3584

Это стало больше панельной дискуссией, чем презентацией.

В середине этого сообщения в блоге Пол Рэмси дает какое-то краткое изложение этого.

Никлас Авен
источник
Это выглядит многообещающе, они разместили презентацию где-нибудь?
Кирк Куйкендалл
Ну, так как Шайлер Эрле стала модератором панельной дискуссии вместо того, чтобы копировать запланированную презентацию, я не думаю, что будет намного больше информации об этом. Но так как Эрл планировал эту презентацию, он, вероятно, имеет некоторую информацию об этом. Он везде, если вы делаете поиск в Google. Это может быть идея спросить его напрямую. Я не знаю. Большинство обсуждений были выше моего понимания, поэтому я не могу дать лучшего резюме, чем Пол сделал в своем блоге.
Никлас Авен
4

Возможно, взгляните на технический документ «Серия ArcGIS Server на практике: геокодирование больших партий » на официальном документе esri .

Речь идет о геокодировании, но общий процесс использования асинхронной службы геообработки может быть применим в вашем случае.


источник
Выглядит хорошо, интересно, можно ли это обобщить на другие формы геообработки. Похоже, мне нужно пересечение между моими наборами данных, хотя.
Кирк Куйкендалл
3

Первое, о чем нужно беспокоиться, это то, какие данные нужны, где и когда. Для этого я обычно начинаю с глупой, серийной версии проблемы.

Найти все участки стоимостью более x $ / акр, которые находятся в пределах y футов от другого участка стоимостью менее z $ / акр.

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

Хотя этот алгоритм не оптимизирован, он решит проблему.

Я решил аналогичную задачу для своей магистерской диссертации, которая нашла ближайшую посылку для каждой точки в наборе данных. Я реализовал решение в PostGIS , Hadoop и MPI . Полная версия моей диссертации находится здесь , но я суммирую важные моменты, которые относятся к этой проблеме.

Уменьшение карты не является хорошей платформой для решения этой проблемы, поскольку для обработки одной посылки требуется доступ ко всему набору данных (или тщательно отобранному подмножеству). MapReduce плохо обрабатывает вторичные наборы данных.

MPI, однако, может решить эту проблему довольно легко. Сложнее всего определить, как разделить данные. Это разделение основано на том, сколько данных имеется, сколько процессоров вам нужно для этого и сколько памяти у вас на процессор. Для лучшего масштабирования (и, следовательно, производительности) вам необходимо иметь несколько копий набора данных участков в памяти (на всех ваших компьютерах) одновременно.

Чтобы объяснить, как это работает, я предполагаю, что каждый из ваших 50 компьютеров имеет 8 процессоров. Затем я назначу каждому компьютеру ответственность за проверку 1/50 посылок. Эта проверка будет выполняться 8 процессами на компьютере, каждый из которых имеет копию одной и той же 1/50 части участков и 1/8 набора данных участков. Обратите внимание, что группы не ограничены одной машиной, но могут пересекать границы машины.

Процесс выполнит алгоритм, получив посылки для p из 1/50 набора, а посылки для q из 1/8 набора. После внутреннего цикла все процессы на одном компьютере будут взаимодействовать, чтобы определить, следует ли отправлять посылку.

Я реализовал алгоритм, аналогичный этому для моей проблемы. Вы можете найти источник здесь .

Даже с этим неоптимизированным алгоритмом я смог получить впечатляющие результаты, которые были сильно оптимизированы для программиста (это означало, что я мог бы написать глупый простой алгоритм, и вычисления все равно были бы достаточно быстрыми). Следующее место, которое нужно оптимизировать (если оно вам действительно нужно), - это установить индекс дерева ветвей второго набора данных (откуда вы получаете q) для каждого процесса.

Чтобы ответить на оригинальный вопрос. Есть архитектура: MPI + GEOS. Добавьте небольшую помощь от моей реализации ClusterGIS, и многое можно сделать. Все это программное обеспечение можно найти как открытый исходный код, поэтому никаких лицензионных сборов. Я не уверен, насколько она совместима с Windows (возможно, с Cygwin), так как я работал над ней в Linux. Это решение может быть развернуто в EC2, Rackspace или любом другом доступном облаке. Когда я его разрабатывал, я использовал выделенный вычислительный кластер в университете.

Натан Керр
источник
2

Методология параллельного программирования старой школы заключается в том, чтобы просто хранить состояние + посылки, которые касаются его, на каждом процессоре, и тогда его очень легко распараллелить. Но, учитывая различия в размере штатов США, вы получите лучшую производительность, разделив страну на ячейки сетки (опять же с трогательным ореолом посылок) и отправив каждую ячейку сетки на процессоры, используя конфигурацию «ведущий-ведомый».

Ян Тертон
источник
Вместо соприкасающихся посылок мне понадобятся посылки из соседних государств на расстоянии y.
Кирк Куйкендалл
Я предполагаю, что Y достаточно меньше, чтобы он не был значительно больше, чем небольшое количество посылок. Если это большая доля состояния, то вам лучше всего использовать произвольную сетку для выполнения расчетов.
Ян Тертон
2

Возможно, вы захотите взглянуть на Апстери . Предполагается включить миграцию существующих приложений в частные облачные инфраструктуры. Могут быть и другие проекты с аналогичной целью: вместо того, чтобы снова и снова выяснять для каждого приложения очень сложный орех разбиения и распределения задач на параллельную обработку, создайте библиотеку или платформу, которая делает это автоматически.

Мэтт Уилки
источник
Спасибо, Мэтт, это выглядит многообещающе. Погуглил я нашел эту презентацию в FedUC 2008 разбирательства.esri.com/ library/userconf/feduc08/papers/… Мне было бы любопытно увидеть обновленную информацию о том, что они сделали с тех пор.
Кирк Куйкендалл
2

Для этого типа проблемы, я бы использовал карту / уменьшить рамки. «Сырая» платформа Appistry отлично подходит для «смущающе параллельных» проблем, с которыми эта проблема близка. Краевые условия не позволяют этому быть. Map / Reduce (подход Google к распределенным вычислениям) хорош в этом типе проблем.

Самым большим достижением в Appistry со времени выхода статьи 08 является выпуск продукта CloudIQ Storage. Это позволяет использовать хранилище типа «s3», используя диски на локальных серверах. Затем продукт CloudIQ Engine может запускать сервисы большого объема или разбирать / собирать приложения любого типа (мы доказали масштабируемость, используя среду выполнения ESRI и другие библиотеки с открытым исходным кодом). Если вы работаете с данными на основе файлов, вы распространяете их с помощью CloudIQ Storage и перенаправляете задания на обработку в локальные файловые реплики, чтобы их не приходилось перемещать по сети. (поэтому каждому узлу не нужны все данные)

Для Map / Reduce вы можете создать что-то вроде Hadoop (M / R-фреймворк с открытым исходным кодом) в CloudIQ Storage. Я бы посмотрел на Hadoop для решения проблемы, как описано, но вам действительно нужно погрузиться в это, начать нелегко, а M / R - искривление мозга. Существует также коммерчески поддерживаемый дистрибутив, предлагаемый Cloudera. Есть еще один продукт Appistry, CloudIQ Manger, который является хорошим дополнением к Hadoop (Cloudera или иным образом) для распространения и управления.

Я бы начал с Hadoop (файловая система M / R и HDFS), и если вам нужно более коммерчески поддерживаемое масштабируемое решение, обратите внимание на Appistry CloudIQ Manager и Storage вместе с дистрибутивом Cloudera Hadoop.

Если вы хотите более простую архитектуру для «смущающе параллельных» задач, посмотрите на CloudIQ Engine. (подходы, изложенные в статье, на которую ссылается Кирк, остаются в силе)


источник