¿Existe una arquitectura para el geoprocesamiento distribuido?

Supongamos que tengo 50 computadoras en mi LAN. Cada computadora tiene una geodatabase para todos los polígonos de parcelas en un estado particular en los EE. UU.

Me gustaría escribir una tarea de geoprocesamiento que encuentre todas las parcelas valoradas en x $ / acre que estén dentro de y pies de otra parcela valorada en menos de z $ / acre.

Me gustaría formular y ejecutar esta consulta sin saber o importar que los datos se distribuyan en 50 computadoras. Tenga en cuenta las condiciones de contorno: también quiero que la consulta devuelva casos en los que las parcelas caras en un estado estén cerca de las parcelas económicas en otro.

¿Existe una arquitectura que admita este tipo de geoprocesamiento distribuido?

La arquitectura se puede describir de manera abstracta o como una implementación específica de Azure o Amazon Web Services. O, preferiblemente, como una oficina típica donde las computadoras permanecen inactivas por la noche con abundantes licencias de escritorio ArcGIS.

1. almacenar todas sus parcelas en una base de datos central
2. formule una cuadrícula sobre los EE. UU. hecha de cuadrados N pies a un lado, donde N sea tal que el número de parcelas que quepan dentro de N no destruya la memoria de uno de sus nodos
3. cree una tabla en su base de datos con una fila por cuadrícula, una columna de identificación, una columna de geometría y una columna de estado
4. cada nodo ejecuta un pequeño programa que
   1. encuentra el siguiente cuadrado sin procesar
   2. lo marca como en proceso
   3. extrae todas las parcelas ST_DWithin (cuadrado, parcela, maxfeet)
   4. hace la consulta real
   5. escribe la respuesta de la consulta en una tabla de solución en la base de datos central
   6. marca el cuadrado como completo
   7. volver a 1

El caso de falla obvio es que su radio de interés en la consulta de paquetes crece lo suficiente como para que grandes porciones de su conjunto de datos sean candidatos potenciales para que coincidan con cada paquete.

Hubo un espacio interesante en FOSS4G en septiembre en Barcelona sobre esto: http://2010.foss4g.org/presentations_show.php?id=3584

Se convirtió más en un panel de discusión que en una presentación.

En el medio de esta publicación de blog, Paul Ramsey da algún tipo de resumen de eso.

Tal vez eche un vistazo al documento técnico "ArcGIS Server in Practice Series: Large Batch Geocoding" en los documentos técnicos de esri .

Se trata de geocodificación, pero el proceso general de uso de un servicio de geoprocesamiento asíncrono podría ser aplicable a su caso.

Lo primero que debe preocuparse con este problema es qué datos se necesitan dónde y cuándo. Para hacerlo, generalmente comienzo con la estúpida versión en serie del problema.

Encuentre todas las parcelas valoradas en x $ / acre que estén dentro de y pies de otra parcela valorada en menos de z $ / acre.

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

Si bien este algoritmo no está optimizado, resolverá el problema.

Resolví un problema similar para mi tesis de maestría que encontró el paquete más cercano para cada punto en un conjunto de datos. Implementé la solución en PostGIS , Hadoop y MPI . La versión completa de mi tesis está aquí , pero resumiré los puntos importantes que se aplican a este problema.

MapReduce no es una buena plataforma para resolver este problema porque requiere acceso a todo el conjunto de datos (o un subconjunto cuidadosamente seleccionado) para procesar una parcela simple. MapReduce no maneja bien los conjuntos de datos secundarios.

MPI, sin embargo, puede resolver esto bastante fácilmente. La parte más difícil es determinar cómo dividir los datos. Esta división se basa en la cantidad de datos que hay, en cuántos procesadores tiene que ejecutarlos y cuánta memoria tiene por procesador. Para obtener la mejor escala (y, por lo tanto, el rendimiento), necesitará tener múltiples copias del conjunto de datos de las parcelas en la memoria (en todas sus computadoras) a la vez.

Para explicar cómo funciona esto, supondré que cada una de sus 50 computadoras tiene 8 procesadores. Luego asignaré a cada computadora la responsabilidad de verificar 1/50 de los paquetes. Esta verificación será ejecutada por 8 procesos en la computadora, cada uno de los cuales tiene una copia de la misma 1/50 parte de las parcelas y 1/8 del conjunto de datos de la parcela. Tenga en cuenta que los grupos no se limitan a una sola máquina, sino que pueden cruzar los límites de la máquina.

El proceso ejecutará el algoritmo, obteniendo las parcelas para p del 1/50 conjunto de parcelas, y las parcelas para q del 1/8 conjunto. Después del bucle interno, todos los procesos en la misma computadora hablarán juntos para determinar si se debe emitir el paquete.

Implementé un algoritmo similar a este para mi problema. Puedes encontrar la fuente aquí .

Incluso con este tipo de algoritmo no optimizado pude obtener resultados impresionantes que estaban altamente optimizados para el tiempo del programador (lo que significa que podría escribir un algoritmo simple estúpido y el cálculo aún sería lo suficientemente rápido). El siguiente punto para optimizar (si realmente lo necesita), es configurar un índice quadtree del segundo conjunto de datos (de donde obtiene q) para cada proceso.

Para responder la pregunta original. Hay una arquitectura: MPI + GEOS. Agregue un poco de ayuda de mi implementación de ClusterGIS y se puede hacer mucho. Todo este software se puede encontrar como código abierto, por lo que no hay tarifas de licencia. No estoy seguro de lo portátil que es Windows (tal vez con Cygwin) ya que trabajé en Linux. Esta solución se puede implementar en EC2, Rackspace o cualquier nube disponible. Cuando lo desarrollé estaba usando un clúster informático dedicado en una universidad.

La metodología de programación paralela de la vieja escuela es simplemente almacenar un estado + las parcelas que lo tocan en cada procesador, entonces es vergonzosamente fácil paralelizar. Pero dada la variación en el tamaño de los estados de EE. UU., Obtendría un mejor rendimiento al dividir el país en celdas de cuadrícula (nuevamente con el halo conmovedor de las parcelas) y enviar cada celda de cuadrícula a los procesadores utilizando una configuración maestra esclava.

Es posible que desee echar un vistazo a Appistry . Pretende permitir la migración de aplicaciones existentes a infraestructuras de nube privadas. Puede haber otros proyectos con un objetivo similar: en lugar de descubrir una y otra vez para cada aplicación la nuez muy compleja de desglosar y distribuir tareas para el procesamiento paralelo, hacer una biblioteca o plataforma que lo haga automáticamente.

Para este tipo de problema, usaría un marco de mapa / reducción. El marco de trabajo "en bruto" de Appistry es ideal para problemas "vergonzosamente paralelos", a los que este se acerca. Las condiciones de borde no permiten que sea. Map / Reduce (el enfoque de Google para la informática distribuida) es excelente en este tipo de problema.

El mayor avance en Appistry desde el documento 08 es el lanzamiento del producto CloudIQ Storage. Esto permite "s3" como instalación de almacenamiento utilizando los discos en sus servidores locales. Luego, el producto CloudIQ Engine puede habilitar servicios de alto volumen o aplicaciones de estilo de dispersión / recopilación de cualquier tipo (hemos comprobado la escalabilidad mediante el tiempo de ejecución de ESRI y otras bibliotecas de código abierto). Si está operando con datos basados ​​en archivos, los distribuye usando CloudIQ Storage y enruta los trabajos de procesamiento a las réplicas de archivos locales para que no tengan que moverse en la red. (por lo que cada nodo no necesita todos los datos)

Para Map / Reduce, puede superponer algo como Hadoop (marco M / R de código abierto) en CloudIQ Storage. Miraría a Hadoop para el problema como se describe, pero realmente necesitas sumergirte, no es fácil comenzar, y M / R es un doblador cerebral. También hay una distribución con soporte comercial que ofrece Cloudera. Existe otro producto de Appistry, CloudIQ Manger, que es un buen complemento para Hadoop (Cloudera o de otro tipo) para distribución y administración.

Comenzaría con Hadoop (sistema de archivos M / R y HDFS), y si necesita una solución escalable más compatible comercialmente, mire Appistry CloudIQ Manager y Storage, junto con la distribución de Cloudera Hadoop.

Si desea una arquitectura más simple para tareas "vergonzosamente paralelas", mire también CloudIQ Engine. (los enfoques descritos en el documento al que Kirk hizo referencia siguen siendo válidos)

Echa un vistazo a OGSA-DQP. "DQP permite consultar las tablas de múltiples bases de datos relacionales distribuidas, utilizando SQL, como si hubiera múltiples tablas en una sola base de datos" http://ogsa-dai.sourceforge.net/documentation/ogsadai4.0/ogsadai4.0- axis / DQPOverview.html