La maña, Paso a paso

Integrando Facebook como Fuente de Datos

Alguna vez te has puesto a pensar ¿Cómo es que las empresas de renombre como Facebook, Twitter, Amazón, Netflix o Spotify saben tanto de nosotros?. Si tu respuesta es asertiva seguramente ya has pasado por una situación parecida a la siguiente.

Imaginemos que un día nuestro mejor amigo(a) nos sorprende con la noticia de que se va a casar y somos el padrino/madrina. Como todo buen padrino/madrina tenemos que ir presentables a la recepción y al observar nuestro ropero caemos en el hecho de que no tenemos una camisa presentable para la ocasión, así que nos vemos en la necesidad de comprar una. Cómo estamos en la era de la tecnología y el sol está sobre el cielo en pleno apogeo, decidimos no salir a la calle y ver algunos modelos de camisas por internet. Al cabo de un rato, una notificación salvaje aparece en nuestro celular, es un anuncio de Facebook con modelos de camisas que nos podrían gustar. — ¿Qué?, ¿Cómo lo supo? —.

Nuestros datos están por todos lados y cada día generamos muchos más, son recolectados, almacenados y procesados para convertirlos en información muy valiosa. Puede sonar un poco tenebroso y lo es. Muchas opiniones y puntos de vista se han alzado sobre este tema y probablemente las toquemos en otro artículo. Pero aquí en Karma podemos decir que nos regimos bajo la Ley de Benjamin Parker

Un gran poder conlleva una gran responsabilidad

Creamos herramientas para hacer Social Listening para poder ayudar a diferentes organizaciones, cómo empresas, escuelas o personas a tomar mejores decisiones basadas en datos. Y para poder cubrir la demanda y brindar mejores soluciones, necesitamos estar actualizados con el universo social e integrar nuevas fuentes.

Al igual que los procesos para extraer oro y petróleo son distintos debido a las particularidades de cada material, la extracción de datos de cada fuente también es diferente. No todos los datos pueden ser obtenidos de la misma manera ni se encuentran en el mismo formato, además de las restricciones impuestas ya sea por el proveedor o por las leyes del país.

ETL

Extracción, Transformación y Carga, ETL (por sus siglas en inglés), son las tres fases por las que pasan los datos antes de ser convertidos en información que ayude a la gestión y toma de decisiones de muchas organizaciones.

En el Proceso de Extracción, como su nombre lo indica, los datos son extraídos de alguna fuente y validados para que cumplan con el formato requerido para después ser enviados al siguiente proceso, el Proceso de Transformación. En esta etapa los datos son limpiados, homogenizados y enriquecidos con información extra derivada de esta misma. Al final, una vez transformados, en el Proceso de Carga los datos pasan a su almacenamiento en uno o diversos medios (Data Warehouse) según se sea requerido. En cada una de las tres etapas los procedimientos intermedios son distintos dependiendo el fin y necesidades de cada organización.

 

Facebook, la nueva fuente de datos

Facebook es una de las nuevas fuente de datos de la que les hablaba al principio. Facebook nos proporciona una herramienta llamada API Graph, que es el medio a través del cual podemos realizar la extracción de los datos. De sus propias palabras, la API Graph es la principal forma de ingresar y extraer datos de la plataforma, se trata de una API basada en HTTP de nivel inferior que las aplicaciones pueden usar de manera programática para consultar datos, publicar nuevas historias, administrar anuncios, subir fotos y llevar a cabo una amplia gama de otras tareas.

Facebook impone distintas medidas sobre la extracción y uso de sus datos dependiendo de los permisos asignados a la entidad que representas (un usuario, una aplicación, una página, etc.). Una de ellas es el número de llamadas a su API realizadas en un periodo determinado de tiempo, mejor conocido como Rate Limiting.

En resumen, si usamos la API Graph de Facebook debemos tomar en cuenta los siguientes puntos:

  • La limitación de frecuencia es calculada en una ventana de una hora.
  • El máximo número de llamadas que puedes hacer es calculada por la cantidad de usuarios activos diarios de tu aplicación, 200 llamadas por cada uno.
  • Si no tienes muchos usuarios activos, el cálculo de usuarios activos pasa a ser semanal o incluso mensual.
  • El límite no aplica por usuario, es decir, si tu aplicación tiene dos usuarios puedes realizar las 400 llamadas usando el mismo token de usuario.
  • Existe limitación de frecuencia por cada token de usuario, y este límite es compartido entre todas las aplicaciones de terceros a las que el usuario ha dado permisos, así que no hay que abusar del uso de un solo token.
  • Algunas llamadas requieren más procesamiento que otras por lo que se incluye otras métricas, Tiempo de CPU y Tiempo Total.
  • Las respuestas de la API Graph incluyen la cabecera HTTP X-App-Usage que contiene la información de los porcentajes de uso de tu aplicación.
  • Dependiendo de la complejidad de la consulta a la API Graph esta puede contarse como más de una llamada a pesar de ser solo una petición HTTP.
  • No todas las llamadas están sujetas al los límites de frecuencia.
  • Peticiones usando un token de página tiene una limitación de frecuencia distinta aplicable solo a la página.

Es importante notar que los cálculos proporcionados por Facebook son estimaciones, y tal como ellos lo mencionan, mientras más usuarios tengas se te proporcionaran estimaciones más precisas.

Además, dependiendo del perímetro del nodo que estás consultando hay un límite superior de datos que puedes obtener en un sola consulta. Por tanto, si la consulta tiene 10,000 resultados y el límite del resultados en la respuesta es de 500 no vamos a poder obtener todos los datos al mismo tiempo. Por ello, debemos obtener poco a poco nuestros datos haciendo uso de la Paginación.

Su don, su maldición

La mayoría de nuestra infraestructura se encuentra bajo Amazon Web Services y el uso de AWS Lambdas es nuestro pan de cada día. La extracción de datos se implementó en este servicio principalmente por su alta capacidad de escalabilidad horizontal y ahorro de recursos, manteniendo al margen automáticamente la cantidad de ejecuciones dependiendo de la carga de trabajo.

Por naturaleza las Lambdas de AWS son entes aislados y sin persistencia que son detonados por algún evento. Viven un corto periodo de tiempo en el que realizan una solo tarea y mueren, así, la correcta ejecución o finalización de la tarea no debe depender de alguna otra. Además, las tareas que realiza cada una deben de ser simples tal que su Tiempo de Ejecución no sobrepase el tiempo máximo de vida asignado (5 minutos a lo más).

Fig. 1.1 – Modelado de comunicación de Lambdas para la extracción de datos

El en diagrama de arriba (Fig. 1.1) se ejemplifica una parte del proceso de recolección de datos a través de los servicios de AWS y Facebook. Existen varias colas del servicio de SQS encargadas de almacenar los mensajes con la información de extracción y cada una está ligada con cierto tipo(s) de nodo(s) de Facebook. El tener esta separación nos proporciona un mejor control del proceso de los datos y un mejor uso de la paginación. Así, este el modelo se reutiliza varias veces por cada tipo de información a extraer.

El proceso consiste en lo siguiente:

  1. Se recibe una solicitud de extracción de datos conforme a las reglas de consulta de la API Graph.
  2. Nuestro servicio recibe la solicitud y de acuerdo al tipo o tipos de datos a extraer son almacenadas en la cola correspondiente de SQS.
  3. Una Lambda por cada cola de SQS está inspeccionando todo momento en espera de mensajes de extracción que procesar. Si hay, los entrega a través de su respectivo Tópico de SNS. Nota, en el momento de la implementación no existían la posibilidad de usa un mensaje de SQS para detonar la ejecución de una Lambda, ahora ya es posible y esta parte puede ser optimizada.
  4. Por cada publicación en algún Tópico se levanta una instancia de la Lambda para resolver la tarea.
  5. Cada Lambda obtiene los datos de Facebook los procesa y los envía a la siguiente proceso de ETL, el de Transformación.
  6. Si los datos son demasiados se hace uso de la paginación y se manda un nuevo mensaje a la cola de SQS para iniciar otra vez el proceso desde el punto 3 hasta que no haya datos restantes.

Es evidente que el servicio de extracción debe ser capaz de procesar varias peticiones en paralelo y los tiempos de espera para finalizar de cada solicitud no deben depender de otra directamente. Sin embargo, si dependen de manera indirecta debido a que mientras más tareas (Lambdas) de extracción haya, el número de peticiones a Facebook también incrementa y entraría en acción la limitación de frecuencia. Si ésta es sobrepasada provocaría que nos quedáramos sin servicio por algunas horas. Por tanto las tareas ejecutadas en paralelo deben ser distribuidas de tal manera que no se sobrepase el Rate limit. Hay que recordar que el Rate limit de Facebook varia dinámicamente dependiendo de los usuarios activos diarios, semanales o mensuales.

Volvamos al diagrama anterior y observemos algunos detalles.

  • Si la demanda de solicitudes de extracción aumenta también lo hacen el número de Lambdas que se ejecutan a la vez.
  • Las ejecuciones de las Lambdas son independientes unas de otras, por tanto, no tienen noción (al menos nativamente) de cuántas hay al mismo tiempo o en qué ciclo de su vida están y mucho menos hay comunicación alguna entre sí.

Entonces, ¿cómo podemos distribuir el trabajo de recolección tal que el número de invocaciones a la Lambda que se ejecutan a la vez no sobrepase el límite de frecuencia de Facebook?

Limitación de Frecuencia

Existen muchos algoritmos clásicos usados para implementar un sistema de limitación de frecuencia.

Leaky Bucket

Se basa en el entendimiento de cómo el agua fluye a través de una cubeta con una fuga en el fondo en dos casos: cuando el flujo de entrada es menor o igual al flujo del hueco y cuando el flujo de entrada excede al flujo del hueco. Usualmente es usado como una cola tipo FIFO, donde los peticiones (u otra entidad) son almacenados según la demanda y sacados de ella a un ritmo fijo. Las peticiones que provoquen que se sobrepase el tamaño de la cola son descartadas (el agua que se desborda de la cubeta).

Token bucket

Al igual que el anterior algoritmo se basa una cubeta de cierta capacidad. La cubeta contiene una cantidad X de fichas (delimitados por su capacidad) y cada cierto tiempo (a un ritmo constante) la cubeta es llenada de nuevo, cuando un petición llega (u otra entidad) se revisa que en la cubeta haya alguna ficha y es sacada de ella, si no hay alguna disponible la petición es descartada.

Fixed Window y Sliding Window

El término window o ventana puede variar dependiendo de dónde se aplique, ya sea a un intervalo de tiempo que puede ser desplazado a través de un historia (nuestro caso) o a la toma de cualquier subconjunto de elementos consecutivos y ordenados bajo cierto criterio. En ambas aproximaciones el algoritmo trabaja con una ventana o intervalo de tiempo y un conteo perteneciente a la ventana.

Para el primer enfoque, Fixed Window, por ejemplo, la ventana puede ser definida de 1 minuto iniciando en el segundo 0 y terminando en el segundo 59 moviéndose minuto a minuto. Las peticiones que sean recibidas dentro del intervalo de tiempo actual son contadas y aquellas que sobrepasen el límite de peticiones definidas para esa ventana de tiempo son rechazadas. Usando una ventana deslizante (Sliding Window) los tiempos de conteo de las peticiones no es definido dentro del minuto fijo en el que nos encontramos (del segundo 0 al segundo 59) sino que el conteo de las peticiones se realiza en el minuto relativo inmediato anterior, e.g., si una petición es realizada a las 10:23:34 y se usa una ventana de 1 minuto, usando una Ventana Fija el conteo es dentro del intervalo [10:23:00, 10:23:59] y dentro del intervalo [10:22:35, 10:23:24] usando una Ventana deslizante.


Muy bien, hasta este punto ya tenemos algunos algoritmos que nos pueden ayudar, pero aún tenemos un problema que resolver, las Condiciones de Carrera generadas por la Concurrencia de todas las ejecuciones de las Lambdas. El hecho que tengamos que hacer incrementos y decrementos en los conteos que registran el número de solicitudes a Facebook eventualmente puede provocar inconsistencias. Afortunadamente, existen diversos mecanismos de sincronización que nos ayudan a resolver este problema fácilmente y muchas Bases de Datos (o todas ¯\\_(ツ)_/¯) ya tienen implementado uno de estos mecanismos, locks. Algunas Bases de Datos están enfocadas al almacenamiento de datos tipo clave-valor y pueden soportar gran cantidad de operaciones sin despeinarse como Redis, RocksDB, Memcached, Ehcache, LevelDB, BoldDB, etc., por mencionar algunas.

Usar Redis y una aproximación al algoritmo de Token Bucket (usando las llaves como tokens) y Slide Window (llaves con TTL de una hora) fue nuestra opción. Principalmente por que nos permite tener un mejor manejo para distribuir el número de llamadas a lo largo de una hora y la libertad de usar los tokens necesarios debido a que ciertas consultas a la API Graph equivalen a más de una petición dependiendo de su complejidad.

Fig. 1.2 – Implementación de ratelimiting a las lambdas de extracción de datos

El el diagrama de la Figura 1.2 observamos que se han agregado tres Lambdas que se encargan de controlar la peticiones a la API Graph.

La primera (de izquierda a derecha) es la encargada de calcular y actualizar en Redis el número de usuarios diarios activos. La última realiza una consulta a facebook cada cierto periodo de tiempo para actualizar las estadísticas de uso en Redis. Por último la Lambda intermedia es la encarga de usar esos datos para insertar en redis una llave con la cantidad de llamadas disponibles por minuto (Token Bucket) y expiración de 1 hora (Sliding Window). Distribuyendo las llamadas cada minuto a lo largo de una hora evitamos que los valores de Tiempo de CPUTiempo Total incrementen desmesuradamente y se mantengan lo más uniforme posible a lo largo del tiempo.

Así que para poder continuar normalmente con el proceso, cada Lambda encargada de repartir las tareas de extracción (según sea el tipo) deben obtener desde Redis decrementando (estas operaciones son atómicas en Redis) de una o más llaves válidas el número de tokens que necesita según sea la complejidad de la consulta, de lo contrario deberá esperar hasta que haya los suficientes para intentar de nuevo.

Tamaño de la ventana

Si bien, anteriormente dijimos que podemos liberar tokens al bucket de Redis con expiración de una hora (el mismo tiempo que Facebook utiliza), cuando haya lapsos de inactividad obtendremos un comportamiento algo extraño.

Imaginemos que durante más de una hora no hay ningún trabajo de extracción, entonces, tenemos almacenados el número de tokens necesarios para extraer datos de una hora completa. Una gran cantidad de solicitudes para extraer la información en ese momento provocaría que, por ejemplo, se acaben los tokens almacenados de una hora en 10 min. Es decir el número de peticiones que tenías reservadas para una hora se consumirían en 10 min y en promedio, en los siguientes 50 min restantes, los tokens liberados estarían fuera de nuestro limite de uso, provocando que Facebook nos quitara el servicio por unas horas.

Se podría pensar en usar una expiración de 1 min para cada token y así nos evitamos este problema. Claro, funciona, pero no estaríamos aprovechando al máximo el uso de la API. Cuando tienes una gran cantidad de peticiones en el escenario anterior, reducir el tamaño de la ventana entre 30 y 45 min (según nuestras pruebas) el uso de la app no supera el 90%, lo que es sumamente bueno pues se estará aprovechando al 90% el uso de la API sin sobrepasar los límites.

Calculando el número de usuarios activos por día

Para poder obtener la cantidad de llamadas que puede hacer tu aplicación, es necesario que tengas un registro de la actividad de tus usuarios, y con ella realizar un aproximación del total de usuarios activos de tu aplicación. No podemos saber con exactitud cuantos usuarios activos tenemos, por tanto, al igual que Facebook (no menciona como realiza el cálculo ni con que precisión) tenemos que calcular un estimado.

Calculando el límite de llamadas por hora

Obtener el límite de llamadas por hora es muy simple, por cada usuario activo Facebook nos da 200 llamadas a su API, por tanto el límite está dado por una simple fórmula.

Llamadas por hora = Usuarios Activos Diarios * 200

Usando las estadísticas para limitar las peticiones

La respuesta de cada petición realizada a Facebook retorna en la cabecera x-app-usage tres datos: call_count, total_time y total_cputime. Con estas estadísticas de uso debemos limitar nuestras consultas dinámicamente. Cuando nuestra aplicación alcanza altos niveles para cualquiera de estos tres valores podemos hacer uso de la siguiente fórmula para poder reducir la cantidad de peticiones.

limitación = 0.5 + 0.5 * (100 – max(estadísticasDeUso)) / (100 – nivelCrítico)

Dónde:

  • max: Es una función que obtiene el máximo de un conjunto de valores.
  • estadísticasDeUso: Los valores correspondientes a las estadísticas de la cabecera x-app-usage.
  • nivelCrítico: Valor del 0 al 100 que consideremos como crítico. Cuando cualquier de los valores de las estadísticas de uso alcance o supere ese valor el número de llamadas se reducirá.

La limitación solo es aplicable cuando alcanzamos el nivel crítico que hayamos definido, pudiendo reducir el número de llamadas hasta la mitad como se observa en la siguiente tabla.

Nivel Crítico Máximo valor de Estadísticas de Uso Limitación
80 80 1
80 85 0.875
80 90 0.75
80 95 0.625
80 100 0.5

No son datos exactos, son estimaciones…

Como no todo en la vida es color de rosa, no podemos asegurar que todo vaya como se planeó a la primera, así que hemos agregado una última variable a la fórmula, el Nivel de Confiabilidad. Está variable nos permitirá definir que tan exactos son nuestros cálculos y acotarlos según su valor. Todo lo anterior está reunido en el siguiente pseudocódigo.

Ya tenemos la lógica de la Lambda que se encargar de liberar tokens cada minuto y por tanto ahora la Lambdas que reparten el trabajo de procesamiento de datos deben leer del Buket en Redis el número de tokens necesarios para realizar la operación.

Recomendaciones

Recuerda que los estadísticas de uso que Facebook proporciona son estimaciones. Así que para obtener un configuración óptima es importante jugar con los parámetros anteriores o agregar otros así lo creamos conveniente.

No nos olvidemos de monitorear el comportamiento de la aplicación. Tal vez las primeras pruebas no concuerden para nada con nuestras estimaciones (como nos pasó en un principio) pero poco a poco Facebook entregará estadísticas más precisas.

Podemos hacer más inteligente el nuestro algoritmo. Por ejemplo, el tener separado la extracción de los datos por el tipo de nodos consultados nos permite rastrear perfectamente cuáles son aquellas consultas que son más pesadas, por tanto, si obtenemos niveles altos de uso de CPU podemos solo limitar solo estas consultas sin afectar a las que no tienen un gran impacto en el rendimiento del API de Facebook.

Hay que tener cuidado con los tiempos de visibilidad de los mensajes de las colas de SQS, si ese tiempo es menor a la ejecución de las Lambda el mensaje puede procesarse varias veces.

Es importante agregar Dead-Letter Queues para tener un control sobre los mensajes que no pudieron ser procesados y poder tomar las medidas pertinentes. Por ejemplo, Facebook no te asegura (según el modo que uses) que el token de paginación sea válido todo el tiempo. Si un token se invalida puedes mandar este mensaje a la dead-letter queue e iniciar un proceso de recuperación de la búsqueda desde el punto en que se interrumpió.

Aún hay bastante trabajo por hacer pero por el momento éste es un buen comienzo. Espero que este artículo te sea de gran ayuda y no dudes en compartirnos tus experiencias y aprendizajes.