10/10/11

Lenguaje S (Lógica Computacional)

En el libro Computability, Complexity and Languages de Davis y Weyuker se describe un lenguaje de programación Y (S para algunos). Dicho lenguaje, sencillo, cumple algunas propiedades teóricas interesantes y es empleado en cátedras de Lógica Computacional.

El código de un programa en S es algo como:

[A1] IF X1 != 0 GOTO B1
     Z1 <- Z1 + 1
     IF Z1 != 0 GOTO E1
[B1] X1 <- X1 - 1
     Y  <- Y  + 1
     Z1 <- Z1 + 1
     IF Z1 != 0 GOTO A

(Función Identidad, Página 17 de Computability, Complexity and Languages)

Es un lenguaje simple, con tres instrucciones: incrementar o decrementar una variable. y saltar a una etiqueta si una variable no es cero.

El rango de las variables es [0, +inf) y toman como valor inicial cero. Además, decrementar una que está en cero no cambia su valor.

También están las etiquetas, que permiten nombrar instrucciones y saltar a ellas mediante IF. Si se salta a una etiqueta inexistente el programa termina. Una extensión al lenguaje es la existencia de macros, similares a las de C.

En el Lenguaje S es conveniente probar los edge-cases antes de empezar a probar formalmente el programa, o tener una ayuda para hacer un seguimiento de la ejecución del mismo.

Como el lenguaje es simple decidí implementar un intérprete y un compilador con una reducida máquina virtual (por el momento sólo en Python). Están bastante incompletos (pero funcionan) y necesitan un lexer-parser real. Aclaro que fue una solución Quick n' Dirty.

El código está en GitHub y bajo licencia NewBSD. Cualquier sugerencia constructiva es bien recibida, por lo que agradezco mucho cualquier fork y pull-request, bug report o comentario.

16/9/11

Datastore en App Engine

En el post anterior traté las dificultades que nos trajo App Engine, y en particular su Datastore, con la forma en la que diseñamos nuestra aplicación.

Después de correr unas cuantas pruebas, descubrimos que la mayoría de los problemas de performance no provenían del particionamiento espacial (como erróneamente habíamos considerado), sino que de un derivado de las consultas: la cantidad de geoceldas que empleábamos por consulta. Teníamos, entonces, dos formas de solucionarlo: eliminar celdas, o bien encontrar el motivo por el cual la consulta era lenta.

Las consultas con IN en Datastore son compuestas. Se realiza una consulta por cada elemento en la lista del filtro IN en paralelo, y luego se juntan los resultados para no devolver duplicados. Por este motivo, mientras más consultas con filtros IN tendremos mayor consumo de API, y por ende mayor latencia. En una aplicación que depende de respuestas casi instantáneas eso juega en detrimento de nuestra experiencia de usuario.

¿Cómo podemos resolverlo? ¿O al menos optimizarlo?

Como asumimos que los índices ya están bien armados por el desarrollador (no lo vamos a tratar en esta entrada), lo primero que podemos hacer es reordenar la forma en la que consultamos por datos. Un objeto Query en AppEngine tiene varias etapas, que son: construcción, ejecución y obtención. Si necesitamos ejecutar distintas consultas sin relación entre sí (como en un foro querríamos obtener la lista de usuarios activos, comentarios recientes y nuevos posts) conviene que lo hagan en paralelo. Para eso tenemos el método run(), que corre las consultas asincrónicamente. Podríamos generar nuestras consultas al principio, correrlas en paralelo y levantar el resultado recién cuando sea necesario sin tener que bloquear por cada una.

Vuelta a las celdas, esta técnica no nos ayuda en nada pues las consultas IN ya corren en simultáneo. Podemos optar por una optimización básica: reducir el número de celdas. Menos consultas implica que obtener los datos (previo merging) sea un tanto más rápido, en especial si además filtramos por otras propiedades con IN. Sin embargo, en el post anterior vimos que no siempre es posible y que de todas formas tendremos como resultado pérdida de precisión y mayor cantidad de falsos positivos (elementos fuera de nuestro viewport, inútiles en nuestro caso). Terminaríamos aumentando la cantidad de elementos necesarios por consulta a un número poco práctico.

Otra opción es obtener sólo objetos Key. La gran ventaja es que AppEngine no levantará las entidades y tardará menos en filtrar, pero nos dará la información relevante a nuestra consulta: qué markers se encuentran en nuestro viewport actual, y no la información de los que se encuentran allí. La desventaja es que ahora requerimos dos pasos para mostrar datos al usuario. ¿Pero entonces de qué nos sirve? Podemos aprovechar el poder de los navegadores modernos para continuar nuestras optimizaciones allí (tema que no trataremos en este post).
Ahora debemos implementar get_multi, de forma tal que podamos levantar los markers de manera eficiente (en grupos) y una sola vez.

La última optimización que podemos hacer es subdividir las entidades en fragmentos más pequeños. No es evidente, o al menos no es la opción que primero se nos ocurre, pero también debemos considerar el costo de serialización y el peso que conlleva crear objetos con datos que no vamos a aprovechar. En una aplicación que debe presentar feedback rápido al usuario separaríamos nuestra entidad en información de primer nivel (que efectivamente necesitamos) y secundaria (que sólo aprovechamos cuando el usuario está interesado en ese objetivo).

Como dije en un post anterior, desarrollar en AppEngine requiere pensar en un paradigma distinto y presenta desafíos interesantes.

4/9/11

Problemas con consultas geoespaciales en Google AppEngine


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.

Share it