Blog de Amazon Web Services (AWS)

La ciencia de la computación y AWS como una abstracción

Por Francisco Javier Baños Lemoine, Solutions Architect, AWS México

 

Siempre me he preguntado cómo hacen sitios como amazon.com, linkedin.com o google.com para implementar la funcionalidad de autocomplete en la búsqueda de productos, compañías o el asunto de interés del que se trate. Aplicar una dosis de la ciencia de computación para implementar el autocomplete nos pone en contacto con la estructura de datos Trie. Por ejemplo, para buscar el nombre de un país con autocomplete, un primer nivel del Trie se ve como aparece a continuación:

 

 

Debajo de cada nodo vendrán todas las letras de países que comienzan con la letra correspondiente: ‘A’ para ‘Alemania’, ‘Austria’, ‘Australia’, etc. ‘B’ para ‘Bolivia’, ‘Bosnia’, ‘Burundi’, etc. Al desarrollar los nodos hijos de la letra ‘A’ se tendrá una estructura semejante a la siguiente figura:

 

 

En el nodo ‘l’ debajo de ‘A’ se pueden desarrollar los nombres de los países como ‘Alemania’ y ‘Albania’ y debajo del nodo ‘z’ vendría el nombre de ‘Azerbaiyán’. Los nombres de los países ‘Austria’ y ‘Australia’ dejan ver las ventajas de una estructura de datos como Trie: conforme llegan las letras de la palabra que se busca, se camina la ruta que marcan los nodos. Por ejemplo, con los caracteres ‘A’, ‘u’, ’s’, ’t’ y ‘r’ se recorre la misma ruta hasta el nodo ‘r’. Si el siguiente caracter es una ‘i’, se navega hacia el nodo izquierdo y si es un caracter ‘a’ se hace hacia el nodo derecho. Con fines ilustrativos, se ha hecho una implementación simple de un Trie en Java que se puede ver en este repositorio de GitHub. Enseguida se muestra un ejemplo de su ejecución:

Prefijo (introduce un punto para terminar): Aust

Sugerencias de autocomplete...

     (Aust)ralia

     (Aust)ria

Prefijo (introduce un punto para terminar): Ale

Sugerencias de autocomplete...

     (Ale)mania

Fragmento (para terminar, introduce un punto): Ru

Sugerencias de autocomplete...

     (Ru)sia

     (Ru)mania

Fragmento (para terminar, introduce un punto): Z

Sugerencias de autocomplete...

     (Z)aire

     (Z)imbawe

Fragmento (para terminar, introduce un punto): .

La complejidad tiempo de buscar una palabra en un Trie es O(k) donde k representa la longitud de la palabra. ¡Es lineal! Por supuesto que procesar todo el texto disponible en Internet y estructurar y mantener un Trie demanda mucho más que un proceso y la memoria que tiene disponible. El objetivo del ejemplo es destacar la importancia de elegir la estructura de datos o el algoritmo correcto para el problema en turno.

 

AWS como una abstracción

La mayoría del tiempo, si no es que todo, me veo usando abstracciones. Por ejemplo, si tengo que escribir un programa que lea un archivo de disco, usaré una función como open() en Python o fopen() en C que son abstracciones que me alivian la tarea de interactuar con el File System directamente. Otra abstracción, read(), me permite leer el archivo sin tener de ocuparme de tareas de bajo nivel como ‘hilar’ los sectores en disco en los que están distribuidos los datos; la abstracción que es read(), me da la ilusión de que están contiguos así que todo lo que necesito es aprender cómo usarla.

Desde mi punto de vista, AWS provee un conjunto de abstracciones. Por ejemplo, si una aplicación necesita la funcionalidad de autocomplete, es preciso considerar la cantidad de memoria que un Trie demanda. Un cluster de memoria suele estar presente en estos casos. Adicionalmente, la programación debe adaptarse para trabajar con la memoria del cluster en lugar de la del proceso asociado. Las anteriores son tareas que un staff de IT, si decide implementarlo por su cuenta, tendría que realizar. Sin embargo, aquí es donde viene la propuesta de valor de AWS: una oferta como Amazon CloudSearch resulta más conveniente en tiempo de implementación cualquier cosa que, por lo menos yo, haría.

Detrás de los servicios AWS, hay ciencia de la computación aplicada. Amazon CloudSearch es una abstracción del Trie. Por la mejor experiencia de usuario que provee, la funcionalidad de autocomplete es una demanda de muchas soluciones que se construyen hoy en día. Un servicio como Amazon CloudSearch, permite proveerla a una fracción de los recursos que le tomaría a una empresa implementarla en su Data Center.

Es el caso para las diversas necesidades de procesamiento de información en las que los CxOs y el staff de arquitectura en cada empresa tienen que resolver el dilema Buy vs. Build. Al igual que la idea de implementar un cluster de memoria, la instalación y administración de las tecnologías base de Big Data (Hadoop, HBase, Spark, etc.) encuentran una mejor resolución en comprar (Buy), literal y metafóricamente, una abstracción como Amazon Elastic Map Reduce (EMR).

La decisión es más importante que lo que, a primera vista, parece. La tecnología de información es un medio para alcanzar un fin: las soluciones de negocio que los usuarios internos o externos demandan de una empresa. Por ejemplo, para decidir una inversión, un tesorero necesita consultar ciertos PKIs en un tablero y poco le importa si para ello se requiere un cluster de Hadoop y aún menos si éste reside en el centro de datos de la empresa o en AWS. Es responsabilidad del CIO, del CTO y del staff de IT la entrega de la mejor solución posible al tiempo que conserva los costos bajos y la seguridad y disponibilidad altas.

 

Resumen

En este artículo he recordado que la ciencia de la computación consta de algoritmos y estructuras de datos. Un ejemplo es el Trie para la funcionalidad de autocomplete y otro es MapReduce para el procesamiento de datos a lo grande (Big Data). Implementarlas a escala corporativa tiene el potencial de requerir una inversión considerable de recursos (con el tiempo como el que más valioso). La tecnología es un medio para alcanzar el fin que son las soluciones de negocio que demandan los clientes y usuarios. De ahí que la decisión de implementarla por su cuenta (Build) o contratarla como un servicio en AWS (Buy) será la marca distintiva entre una empresa lenta y una ágil.

 

 


Sobre el autor

Francisco Javier Baños Lemoine es Solutions Architect en AWS México.