En uno de los proyectos donde estoy trabajando la principal funcionalidad depende de búsqueda de puntos en un mapa. La aplicación debe responder de manera rápida, estable y devolver datos según diversos filtros para luego ser procesados del lado cliente (web).
El stack de AppEngine presentó unos cuantos desafíos, particularmente en Datastore y CPU. Si bien la aplicación es relativamente sencilla, la gran cantidad de puntos y los filtros demandan una forma distinta de pensar.
Datastore
Como el Datastore de AppEngine está basado en BigTable, las consultas sobre el sistema se limitan a desigualdades sobre un solo campo. Esto elimina búsquedas donde encerramos entre rangos de latitud/longitud, y además evita el ordenamiento de los datos.
La solución es usar una especie de función hash para almacenar la posición aproximada de los puntos. La idea es particionar el mapa en una cantidad arbitraria de celdas y utilizar el operador IN de AppEngine. Esto nos ahorra la búsqueda por desigualdad a costo de incrementar el número de consultas (y CPU).
Geomodel es una librería que implementa este sistema. Provee un modelo del que heredamos y los métodos necesarios para generar y consultar las geoceldas. Es totalmente transparente al usuario y sólo requiere que llamemos a un método para actualizar la información de las celdas. Sin embargo, es necesario conocer la teoría para hacer uso correcto de los recursos y no llevarnos sorpresas desagradables.
(Nota: omito el chequeo de errores para ser breve)
Teoría
¿Qué es una geocelda?
Podemos pensar al mapa como un rectángulo. La idea de las geoceldas es partir el mapa en secciones
más pequeños, seleccionar la celda donde se encuentra nuestro punto y reiterar el proceso hasta que logremos una celda arbitrariamente pequeña (como un
quadtree). Lo bueno de este sistema es que como trabajamos sobre el par latitud/longitud es independiente a la proyección.
(Nota: Geomodel implementa los métodos de forma distinta y más eficiente, pero la esencia es la misma)
Ejemplo:
Supongamos que tenemos un sistema que va desde 0 a 100 metros para la latitud y la longitud, y queremos celdas de 10 metros de precisión. Para facilitar el ejemplo, sólo partiremos el mapa en 4 celdas por vez, a las que llamaremos Q, W, A y S (por la posición en el teclado).
Para ubicar el punto 2-32:
class Map(object):
def __init__(self, x, y, cell_size):
self.x = x
self.y = y
self.cell_size = cell_size
def locate(self, x, y):
cell = ""
middle_x, middle_y = self.x / 2, self.y / 2
size = max(self.x, self.y)
while size > self.cell_size:
left, right = int(x > middle_x), int(y > middle_y)
cell += ("QW", "AS")[left][right]
middle_x *= 0.5 + left * 0.25
middle_y *= 0.5 + right * 0.25
size /= 2
return cell
m = Map(100, 100, 10)
print m.locate(2, 32)
Vemos que calcular el hash tiene costo Tita(log(max(x, y) / cell_size)). Una propiedad importante es que si dos puntos tienen el mismo prefijo entonces son vecinos, mientras que la inversa no es cierta para todos los casos (ejemplo: 51-50 y 50-51). Esto dificulta la búsqueda de proximidad (pues debemos generar las ocho celdas vecinas), y aumenta el uso de CPU.
Por el tipo de arquitectura de BigTable, para almacenar los registros conviene precomputar una lista de todas las celdas a las que un punto pertenece y almacenarlas en una ListProperty. De esta manera, el costo de una consulta por celda será proporcional a la precisión (número de elementos).
La búsqueda por caja (bounding box) es la que más utilizamos. Para ello se computa una serie de celdas a partir de una vista (viewport) a una resolución determinada, y con esas celdas se consulta a la base de datos. Geomodel filtra los resultados para eliminar aquellos que quedan fuera de la vista, pero eso incrementa el uso de CPU.
Para calcular el viewport necesitamos un par de funciones para obtener los vecinos (izquierdo e inferior) de una celda. Eso lo podemos lograr así:
class Map(Map):
...
@staticmethod
def right(cell):
if cell[-1] == "Q":
return cell[:-1] + "W"
elif cell[-1] == "A":
return cell[:-1] + "S"
elif cell[-1] == "W":
return Map.right(cell[:-1]) + "Q"
elif cell[-1] == "S":
return Map.right(cell[:-1]) + "A"
@staticmethod
def down(cell):
if cell[-1] == "Q":
return cell[:-1] + "A"
elif cell[-1] == "W":
return cell[:-1] + "S"
elif cell[-1] == "A":
return Map.down(cell[:-1]) + "Q"
elif cell[-1] == "S":
return Map.down(cell[:-1]) + "W"
El costo de calcular el vecino es relativo a la precisión, pero en la mayoría de los casos requiere sólo un par de cambios. Con estas funciones sólo resta calcular el viewport, para lo cual calculamos los cuatro extremos de nuestra caja y generamos a partir de ellos el resto:
class Map(Map):
...
@classmethod
def row(cls, cell, limit):
yield cell
while cell != limit:
cell = cls.right(cell)
yield cell
@classmethod
def col(cls, cell, limit):
yield cell
while cell != limit:
cell = cls.down(cell)
yield cell
def viewport(self, n, e, s, w):
left_col = self.col(self.locate(n, e), self.locate(s, e))
right_col = self.col(self.locate(n, w), self.locate(s, w))
for start, stop in zip(left_col, right_col):
for cell in self.row(start, stop):
yield cell
Para nuestro mapa, el uso sería:
for cell in m.viewport(0, 0, 20, 20):
print cell
Vemos que la búsqueda por viewport es simple, pero que requiere una cantidad de recursos importante si se quiere un buen nivel de precisión. En particular, generar las celdas es proporcional a la resolución y tamaño de la caja, por lo que un buen algoritmo debería ser capaz de detectar el tamaño óptimo de las celdas para reducir la cantidad de consultas (por prefijo común, por ejemplo) y no superar el límite práctico de AppEngine.
Existen otros esquemas de partición, pero es aconsejable escoger uno que nos permita ordenar los resultados de forma coherente. Para los interesados, Geomodel particiona en 16 subceldas y asigna un orden similar a un código Morton (
Z-Order Curve).
No voy a tratar el análisis de búsqueda por proximidad, al menos no en este post. ¿Por qué? Una idea: el método proximity_fetch en Geomodel tiene +150 líneas. Se puede obtener un resultado similar para celdas pequeñas generando un viewport centrado en el objetivo.
