Este repositorio corresponde a una prueba técnica para Aranda Software.

Implementa un árbol binario con una búsqueda de ancestro común más cercano que se basa en recorrer con DFS y, copiando la pila de trabajo de DFS, encontrar el primer nodo de coincidencia entre dos rutas.

En cuanto a la interfaz, implementa web services (RestBed) con JSON (NLohmann). En cuanto a documentación usa Doxygen y, en cuanto a testing unitario, DocTest.

El diseño general es similar a un MVCS, con los web services cargados dinámicamente como plugins. Esto permite, a futuro, establecer un sistema para carga y actualización de los web services en caliente, con pocas modificaciones respecto del código actual. El encapsulamiento que se genera es tal que escribir un web service nuevo es agnóstico de todo el resto del modelo.

En cuanto a la documentación específica de la implementación (diagramas de clases, etc.) vea make doc (requiere Doxygen).

Esta interfaz usa Restbed de Corvusoft y fue programada y probada en Ubuntu 21.04.

Todas estas dependencias están probadas en Ubuntu 21.04.

Para usar RestBed en Ubuntu:

apt install librestbed0 librestbed-dev

Esta interfaz usa SQLite3. Para usar SQLite en Ubuntu:

apt install libsqlite3-0 libsqlite3-dev

Para compilar se utilizan GNU make y g++, parte de GCC, para instalar estas utilidades en Ubuntu:

apt install build-essential

Con todas las dependencias anteriores satisfechas, se puede compilar tan simplemente como:

make

Para compilar la documentación DOXYGEN (requiere Doxygen):

make doc

NOTA: Puede ver la documentación una vez compilada abriendo doc/html/index.html (este link no funcionará en GitHub porque la documentación compilada no forma parte del repositorio).

Las pruebas unitarias están escritas usando DOCtest. Durante el testing unitario se usa el puerto 37337 para evitar problemas de permisos. La base de datos durante las pruebas es test/test.db. Para compilar y ejecutar:

make test

Para compilar y ejecutar mediante valgrind (requiere valgrind):

make valgrind-test

Se usan variables de entorno para configurar los web services. Estas variables son:

1. RESTFUL_PORT: El número de puerto en el que servir los web services. Default: 80.
2. RESTFUL_DB: El nombre del archivo de base de datos. Default: restful.db.
3. RESTFUL_MAX_THREADS: El número máximo de hilos a usar. Default: 4.

Una vez compilado, el servidor puede iniciarse directamente mediante su ejecutable:

./restful

Sin embargo, ejecutar los web services en el puerto 80 puede solicitar privilegios. Los siguientes son consejos de seguridad:

1. Asgúrese que el ejecutable NO tiene set-user-ID ni set-group-ID:

chmod u-s,g-s restful

2. En lo posible, tenga un usuario separado, sin privilegios ni permisos. Este usuario debe poder escribir en el directorio en que se ubica el binario. Supondremos que ese usuario es foobar. Cambie el propietario y grupo de restful a este usuario:

chown foobar restful
chgrp foobar restful

3. Use setcap para darle a restful acceso a los puertos bajos (setcap requiere privilegios):

setcap CAP_NET_BIND_SERVICE=+eip restful

Los webservices se inician en el servidor, que puede ser la misma máquina que el cliente o no. Para usarse, se envian solicitudes del tipo application/json, via POST para el webservice crear-arbol, y vía GET para el webservice ancestro-comun. En el primero, cada árbol se forma con objetos nodo, cada uno con el siguiente formato:

{
    "node": <datos>,
    "left": {<objeto>},
    "right": {<objeto>}
}

En todos los nodos debe existir el campo node, y los datos pueden ser cualesquiera que desee siempre que cumplan con el modelo de JSON (incluso otros objetos). Los campos left y right son opcionales. En conformidad con el estándar JSON, el orden de los campos no importa.

La respuesta de crear-arbol vuelve en formato JSON, indicando el ID del árbol, ya sea que fue creado o que coincide con un árbol creado con anterioridad. En cualquier caso, el ID identifica al árbol en cuestión:

{"id":<ID>}

Este mismo ID debe ser usado en la consulta ancestro-comun, junto a los nodos de los que se quiere conocer el ancestro común, llámense node_a y node_b.

{
    "id":<ID>,
    "node_a":<datos>,
    "node_b":<datos>
}

Véase que los datos en los nodos deben ser coincidentes con aquellos que existen en los nodos del árbol creado anteriormente. En caso de cualquier error, el webservice devuelve BAD REQUEST. En caso de éxito, el web service devuelve el contenido del nodo que es ancestro común.

Para probar los servicios manualmente, se puede usar curl, por ejemplo:

# CREAR ARBOL
# Devuelve un JSON con un ID para consultar
curl --header "Content-Type: application/json" \
     --request POST \
     -w'\n'\
     --data '{"node":1,"left":{"node":2}}' \
     http://localhost/crear-arbol


# CONSULTAR ANCESTRO COMÚN
# Usar el id devuelto por el servicio anterior
curl --header 'Content-Type: application/json' \
     -s -G -w'\n' \
     --data-urlencode 'q={"id":1,"node_a":1,"node_b":2}' \
     http://localhost/ancestro-comun

Se incluyen en el directorio test, dos scripts llamados crear-arbol-curl y ancestro-comun-curl.

1. crear-arbol-curl usa CURL para acceder al web service de creación de un árbol modelo.
2. ancestro-comun-curl usa CURL para hacer solicitudes de varios casos de uso de pedido de ancestro común.

Estas son pruebas de stress para los web services, enfocadas en el algoritmo de búsqueda del ancestro común, que es el centro de este programa (nótese que estas pruebas NO miden cómo crece el algoritmo con la profundidad del árbol ni el número de nodos, sino cómo se comporta en servicio atendiendo solicitudes similares, ésto es deliberado).

Al llamar bash test/ancestro-comun-curl 5 10000 por ejemplo, se hacen 5 rondas de 10000 (diez mil) solicitudes al servidor. Cada ronda de 10000 debe terminar para que comience la ronda siguiente.

En cada ronda, se mide el tiempo total de respuesta del servidor para el total de las solicitudes.

Para evitar sesgos por recursos propios de la máquina que emite las solicitudes, se crean dos blancos que sirven de comparación:

1. blanco de script: El script nunca llama a curl, pero hace todos los forks y escrituras de logs normalmente. Este tiempo es propio del script de pruebas.
2. blanco de red: Se usa curl pero la solicitud para los WS es inválida, forzando un error y evitando que el servidor ejecute el WS en cuestión. Este tiempo de respuesta es el mínimo que se puede obtener sin tener en cuenta la aplicación.

Se puede usar este script para obtener muestras de 'n' mediciones de tiempo en condiciones controladas.

Al finalizar el SCRIPT, la última ejecución de todos los casos de prueba se guarda, sirviendo también para probar situaciones particulares.

Cada test está titulado de manera intuitiva.

Estas pruebas se usaron para elaborar el siguiente gráfico, donde cliente y servidor se encuentran en la misma máquina, pero usan la red local para comunicarse. A fin de dar significado a los tiempos obtenidos, considerar que se trata de un Intel® Core™ i5-4210U CPU @ 1.70 GHz con 4 núcleos y 5.7 GiB de memoria RAM. El servidor fue configurado con RESTFUL_MAX_THREADS=4. No se grafica el blanco de script por haber resultado muy similar al blanco de red: