Pablo Alejandro Costesich: 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.

Ramiro Algozino: New Feature for QtQR 1.3

QtQR IconAs asked by an Italian friend that posted a review on his blog (link). I’ve implemented Drag&Drop decoding support for QR Codes images directly from a website in QtQR.

You can see this in action in the following video:

You can expect this feature to be available in the daily PPA or wait for the stable release.

EDIT: Just if you don’t know, you can drag&drop to a QtQR dekstop launcher like showed in the next video, in this manner you don’t even have to open QtQR previusly to decode a file.

Any thoughts, bugs or feature request are more than welcome!


Pablo Alejandro Costesich: 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.

Ramiro Algozino: How to install QtQR in Fedora

Dependencies

QtQR 1.0/1.1/1.2 has the following dependecies:

  • PyQt4
  • qrencode
  • python-imaging (PIL or Python Image Library)
  • python-zbar
Sadly, the last one of these is not available to install via the yum package manager, or maybe it is in some repo I don’t know about. If you know where to find it please tell in the comments.

Installation

For installing PyQt4, qrencode and PIL you can use yum like this (remember to login or run as root):
yum install pyqt4 qrencode python-imaging

Once you got them installed you can go on installing python-zbar using easy_install:

easy_install zbar

If you get an “error: Setup script exited with error: command ‘gcc’ failed with exit status 1″ error, you need to install the zbar-devel package first, like this:

yum install zbar-devel

And there you go.. now you can download the sourcecode from Launchpad, decompress and run QtQR with the following command:

cd <dir of qtqr sourcecode>
python qtqr.py

Summary

In summary, this are the commands you need to run (as root) to get QtQR working:

su
(enter root password)
yum install pyqt4 qrencode python-imaging zbar-devel
easy_install zbar

Tested in Fedora 15, but if you find any difficulties please let me know in the comments.. happy hacking! :-)


Martín Cerdeira: La frase del día...

"Google+ isn’t about sharing cat pictures, it’s about serving ads. Twitter’s massive network of 140-character bits of information isn’t about connecting people across the globe or to view current trends in worldwide thinking, it’s about serving ads. Facebook isn’t about entertaining yourself with games or sharing interesting links, it’s about serving ads."

No es que no lo sepamos, pero...


Fuente.
Info relacionada.

Andrés Gattinoni: Sencillo parser para Apache mod_status en Python

Cuánto hace que no actualizo este blog!! Hoy estuve jugando un poco con Python y me puse a hacer un pequeño script que supongo que a otros les podrá servir como base para hacer algo más interesante. Precisamente, tengo planes para hacer algo más interesante, pero como recién están en veremos, les voy pasando esta pequeña base a ver si alguien me gana de mano 🙂

Como muchos sabrán, Apache (y otros web servers) tiene un módulo llamado mod_status que nos permite ver en tiempo real el estado del servidor (los requests que se están procesando, el uso del CPU, el estado de las conexiones, etc.). Esta información puede ser muy útil para hacer diagnósticos cuando está habiendo algún tipo de problema, para hacer monitoreo, etc. El módulo nos muestra una página web con la información y tiene dos interfaces: una está pensada para ser vista por seres humanos y otra para ser consultada por scripts (para ver esta segunda sólo hace falta pasarle el parámetro “?auto” en la URL). El problema es que esta segunda interfaz no nos muestra a qué dominios (virtual hosts) están dirigidos los requests que se están procesando (o si hay forma de que lo muestre yo no la encontré). Entonces me puse a hacer un sencillo script en Python para parsear la página “para seres humanos”.

Por suerte Python nos ofrece muchas herramientas muy útiles para este tipo de cosas, así que no me tuve que esforzar demasiado. En este caso utilicé urllib2 para acceder a la página de mod_status y BeautifulSoup para parsear el HTML. Por si no lo conocen, BeautifulSoup es un muy poderoso parser para XML/HTML hecho en Python. No viene con el código fuente sino que hay que instalarlo, pero hacerlo es muy fácil:

En Debian/Ubuntu:

apt-get install python-beautifulsoup

En CentOS/RedHat:

yum install python-BeautifulSoup

Con easy_install:

easy_install BeautifulSoup

El código tiene una clase Status que es la que hace la magia y una función main() que utiliza la clase para parsear una URL e imprimir algunos datos a modo de ejemplo.

import sys
import urllib2
from operator import itemgetter
from BeautifulSoup import BeautifulSoup

class Status (object):
    _url = None

    def __init__ (self, url):
        self._url = url

    def fetch (self):
        return urllib2.urlopen(self._url).read()

    def parse (self):
        html = self.fetch()
        soup = BeautifulSoup(html)
        status = {}
        status[‘server_info’] = [i.string.strip() for i in soup.findAll(‘dt’)]
        status[‘requests’] = []
        requests = soup.find(‘table’).findAll(‘tr’)
        keys = [i.string for i in requests.pop(0)]
        for tr in requests:
            req = {}
            for n, td in enumerate(tr):
                req[keys[n]] = td.string
            status[‘requests’].append(req)
        return status

def main (argv):
    if len(argv) < 2:
        print "Usage %s "%argv[0]
        return 1

    status = Status(argv[1])
    data = status.parse()
    print "SERVER INFORMATION"
    print "=================="
    for v in data[‘server_info’]:
        print v

    print "REQUESTS BY VHOST"
    print "================="
    entries = [i[‘VHost’] for i in data[‘requests’]]
    requests = sorted([(entries.count(i), i) for i in list(set(entries))], reverse=True)
    print "\n".join(["%d: %s"%(a,b) for a,b in requests])

if __name__ == "__main__":
    sys.exit(main(sys.argv))

La forma de uso es:

python status.py "http://localhost/server-status"

Y en este caso la salida del script es algo así:

SERVER INFORMATION
==================
Server Version: Apache/2.2.19 (Unix) mod_ssl/2.2.19 OpenSSL/0.9.8e-fips-rhel5 DAV/2
Server Built: May 26 2011 15:14:47
Current Time: Sunday, 31-Jul-2011 00:53:59 ART
Restart Time: Saturday, 30-Jul-2011 12:07:12 ART
Parent Server Generation: 0
Server uptime:  12 hours 46 minutes 47 seconds
Total accesses: 407813 - Total Traffic: 3.7 GB
CPU Usage: u2.05 s3.23 cu52 cs0 - .125% CPU load
8.86 requests/sec - 85.0 kB/second - 9.6 kB/request
10 requests currently being processed, 8 idle workers
REQUESTS BY VHOST
=================
9: www.tail-f.com.ar
5: www.otro-dominio.com.ar
4: www.not-a-domain.com.ar
3: www.algunlado.com.ar
2: subdominio.dominio.com.ar
1: www.pepe.com.ar
1: www.no-votes-a-macri.com.ar
1: www.asd.com.ar
1: localhost

Obviamente esto no es una aplicación funcional, sino un ejemplo que espero que les sirva para hacer algo más copado. Yo seguiré jugando y si hago algo un poco más interesante, ya se los mostraré.

Martín Cerdeira: Otra idea loca: MyGoogle

Lamentablemente, esto no puedo, ni siquiera soñar con llevarlo a la práctica (ni siquiera sé si lo puede hacer google) y, aunque la idea es simple, su implementación no lo es tanto.

Google, como buscador es un servicio, personalizado (hasta cierto punto) pero... Qué pasa si yo quiero mi buscador? Y no me refiero un buscador de mis archivitos en mi pc, no.

Yo quiero mi google.

Quiero decirle a mi "googlito" que indexe, por ejemplo, datos sobre fútbol, porque quiero una base de datos del tema, o que indexe info sobre la bolsa, porque soy un corredor de bolsa y quiero datos estadísticos.
Es decir, quiero que mi "googlito" me genere una base de datos, que yo pueda consultar (como hoy se consulta el google normal) pero, "saborizada" con mi forma particular de indexar.

Así, tendría una cuenta de google index (como hoy tengo de Gmail, por ejemplo)  donde customizo "mi google", diciendole (de alguna forma) como quiero que indexe, con qué criterios, qué relaciones, etc, etc.

Así mismo, puedo publicar esos "googles" customizados para que los usen otras personas.
De esta forma, no sé, Bonadeo capaz tiene su google (como hoy tenés tu twitter) donde, vas a www.google.com/#bonadeo y buscás data sobre, que se yo, tennis de forma más personalizada y enfocada en el tema tennis, y no tan general como hoy buscaríamos sobre tennis en el google normal.

Es medio porrera la idea, pero, ojalá papa noel me traiga algo así para navidad.