Enrutadores PHP

Cuenta Dave Young que hace un par de años, se propuso construir un enrutador PHP. Anteriormente había construido uno para Opulence, pero estaba interesado en funciones adicionales, como restricciones personalizadas que le permiten hacer coincidir los encabezados (útil para el control de versiones de API basadas en encabezados). Dave no estaba tan interesado en la velocidad hasta que leyó el excelente desglose de Nikita Popov de su biblioteca FastRoute basada en expresiones regulares. Inicialmente adoptó un enfoque de coincidencia muy similar a FastRoute, pero no logró evitar una idea que pensó que podría rivalizar con su algoritmo: el enrutamiento basado en árboles.

Por ejemplo, digamos que Dave tenía las siguientes rutas en mi API:

• users

• users/:id

• users/:id/avatar

• users/:id/email

Dave quería que se generara la siguiente estructura de árbol para la coincidencia:

En informática, esta estructura de datos se llama “trie” (pronunciado como “árbol”). Cada nodo comparte el mismo prefijo que todos los demás nodos hermanos.

El algoritmo

El algoritmo de Dave utiliza la búsqueda en profundidad para encontrar una ruta coincidente en el trie. Para segmentos estáticos, es decir, no variables, utiliza una tabla hash simple para la búsqueda de O(1) para cada segmento y, si no se encuentra ninguna coincidencia, iterará sobre los segmentos variables para obtener una coincidencia, lo que nos da O(n) donde n es el número de nodos variables en ese nivel del trie. Dave sigue descendiendo por el trie hasta que encuentra un candidato coincidente o simplemente, no lo encuentra, lo que da como resultado un 404. El paso final es recorrer las restricciones de ruta en un candidato coincidente, por ejemplo, asegurándose de que la coincidencia acepta el método HTTP de solicitud candidato. Si pasan todas las restricciones, entonces esta es la ruta correspondiente. De lo contrario, obtiene la devolución de cualquier otro candidato coincidente hasta que encuentre uno o devuelva un 404 o 415, dependiendo de si se encontró algún candidato coincidente con diferentes métodos HTTP. Los retornos de rendimiento son útiles porque no tiene que recopilar todos los posibles candidatos coincidentes antes de seleccionar uno, lo que produce una ligera mejora del rendimiento.

El tiempo de ejecución del algoritmo depende del número de segmentos en la ruta (lo llamaremos n). En el mejor de los casos con todas las rutas estáticas, el tiempo de ejecución es O(n) y, en el peor de los casos, O(nm), donde m es el número medio de segmentos variables por segmento.

Un ejemplo

Supongamos que la ruta de la solicitud era /users/123/email. Buscaría users en nuestro trie de ruta y encontraría una coincidencia en O(1) porque existe como un segmento estático en el trie. Luego, buscaría 123 en el nodo de usuarios, pero no encontraría una coincidencia estática. Entonces, iteraría sobre los nodos variables hasta encontrar una coincidencia. En este caso, el nodo :id no tiene restricciones de variable, por lo que coincidirá con cualquier valor. Luego, busco  email en:  :id‘s children, nuevamente encuentro un nodo estático coincidente en O(1). El trie nos dirá que el nodo de email se asigna a una ruta en particular y es un candidato para una coincidencia. En este caso, diré que todas las restricciones de ruta pasan y devuelvo esta ruta como coincidencia.

Resultados comparativos

Entonces, ¿cómo se compara este algoritmo con FastRoute? Eché un vistazo a varios puntos de referencia en la web, pero vi problemas con todos ellos, por ejemplo, URI de longitud irreal con 9 segmentos de ruta o solo pruebas que coinciden con la primera o la última ruta de la colección. Decidí escribir un punto de referencia que coincida con todas las rutas de una colección de 400 con rutas como /abc{0-399}/{0-399}/:foo/{0-399}. Los resultados: el algoritmo de Aphiria es ~ 175% más rápido que el de FastRoute, pero va por detrás del excelente enrutador de Symfony por aproximadamente el mismo margen [mueve el puño].

Estoy seguro de que hay microoptimizaciones que puedo hacer para mejorar un poco la velocidad de Aphiria (por ejemplo, intentar hacer coincidir varios segmentos estáticos de una sola vez), pero es casi seguro que tendrían el precio de una mayor complejidad. El enrutador de Aphiria tiene actualmente 3.976 líneas (123 solo para la coincidencia) en comparación con las 6.727 de Symfony (sin incluir las pruebas). Sin embargo, dado que la velocidad de estas tres bibliotecas es más que suficiente, no estoy particularmente interesado en cerrar la brecha con Symfony. Dicho esto, hay que felicitar a Nicolas Grekas y a la comunidad por lograr esa velocidad.

Conclusiones

Para reiterar, casi todos los enrutadores PHP son lo suficientemente rápidos. ¿Por qué creo que deberías usar el de Aphiria? Soporta:

• Atributos de PHP 8.0 y constructor de sintaxis fluida
• Rutas y hosts coincidentes
• Restricciones de ruta personalizadas que pueden usar cualquier parte de la solicitud para hacer coincidir una ruta, por ejemplo, coincidencia de encabezados para el control de versiones de API
• Agrupación de rutas
• Vinculación de middleware independiente del marco a las rutas
• Crear URI a partir de nombres de rutas
• Sin vínculos con ninguna biblioteca de marco fuera de la biblioteca de reflexión de Aphiria

Si desea probar el enrutador de Aphiria, puede instalar la aplicación básica para comenzar a funcionar rápidamente o instalar solo la biblioteca a través de Composer.

Links

• Aphiria router docs
• Trie route matcher source
• Trie compiler source
• URI template lexer source
• URI template parser source