Construyendo un motor de recomendaciones al estilo FourSquare

En el blog del departamento de ingeniería de FourSquare han publicado un post realmente interesante sobre como han construido su motor de recomendaciones de lugares.

Lo primero que comentan básicamente es la dificultad de este tipo de motores al tener gran cantidad de datos, en su caso 10 millones de locales, y necesitar por una parte computar la similitud de estos lugares, es decir agrupar los lugares en los que se come Sushi, o Churrasco, o donde se toca Jazz, y por otra parte ponderar estos resultados con las preferencias personales de los usuarios, es decir como los han puntuado o cuantas veces los han visitado y con que frecuencia, y las preferencias de sus amigos, es decir si tus amigos suelen ir a restaurantes Indios hay una gran posibilidad de que a ti también te interesen estos restaurantes.



En Jobsket utilizamos algoritmos similares para la recomendación de ofertas de trabajo a los candidatos y candidatos a las empresas, pero ya os digo que ni de broma al nivel de esta empresa. La gran cantidad de datos y combinaciones de similitudes que se generan en FourSquare (comentan en el blog que les sale una matriz de combinaciones con más de 100 trillones de elementos) les obliga a precalcular las similitudes entre los diferentes locales. Para realizar estos cálculos, utilizaron un cluster con 40 ordenadores utilizando Hadoop, Hive y para los algoritmos matemáticos han utilizado Mahout, una librería Open Source de Apache que implementa diferentes algoritmos de Machine Leraning y minería de datos.

Con la matriz de similitud precalculada y otra serie de optimizaciones el equipo de FourSquare ha conseguido que cualquier consulta de recomendaciones se reduzca a menos de 100 milisegundos excluyendo la latencia del servidor, lo cual está realmente bien. El principal coste se encuentra como es de esperar en las consultas a las bases de datos. Una de las notas más a recordar de su caso de uso es que comentan que las bases de datos tradicionales no están preparadas para manejar datos geoespaciales a su escala. Recálculo el "a su escala" porque tampoco creo que nos debamos obcecar con imitar a estos monstruos de los datos si lo que tenemos son unas cuantas miles de filas.

Para mejorar el rendimiento, lo que hacen es recoger un número fijo de locales cuando se hace una consulta (por ejemplo cien). Por lo tanto, dependiendo del radio geoespacial de la consulta los resultados serán más o menos exactos. Una recomendación de 100 restaurantes en 20 kilómetros a la redonda será peor que una recomendación de 100 restaurantes en un kilómetro a la redonda. Después de su investigación, en FourSquare se decantaron por MongoDB que parece que ofrece un rendimiento bastante aceptable dando 30 milisegundos de respuesta para una consulta de 16 kilómetros a la redonda en Nueva York, lo que engloba a varios cientos de miles de locales.

Su segundo reto ha sido el recoger el historial y preferencias de tus contactos en FourSquare, y el hecho de que cada contacto puede haber acudido a decenas de locales, en múltiples ocasiones, lo que multiplicado por cientos de locales puede dar cifras importantes. Para solucionar este problema construyeron una caché con datos agregados de locales y usuarios y la colocaron en un servidor intermedio. Básicamente una aproximación tradicional de Datawarehouse.

Y esto es todo lo que he podido sacar en claro del artículo. Me parece realmente muy interesante y un caso de éxito a considerar. Estoy viendo que cada vez son más los servicios que usan Mahout, y también que Hadoop+Hive se está imponiendo cada vez en más lugares. MongoDB también se está haciendo más y más popular. Como cambian los tiempos de nuestras viejas arquitecturas de servidor de aplicaciones más Oracle o MySQL. ¿No os parece?