Planteamiento y alcance
Mantienes una API de archivos, organizaciones o grafos de conocimiento cuyos recursos pueden apuntar a otros recursos mediante alias o enlaces. Un cliente solicita una expansión recursiva similar a Depth: infinity de WebDAV. Diseña el recorrido, el reporte de ciclos, los presupuestos de profundidad y de nodos, y explica cuándo 508 es incorrecto. Esto encaja en entrevistas de backend, almacenamiento y plataformas.
La RFC 5842 define 508 para terminar una operación de profundidad infinita después de encontrar un bucle; no es un código genérico para bucles de redirección o tiempos de espera agotados de CPU. Asume que el grafo puede cruzar inquilinos (tenants) y que cada arista y nodo requiere autorización.
Qué está evaluando el entrevistador
- Si modelas el recorrido recursivo como un grafo en lugar de esperar un desbordamiento de pila (stack overflow).
- Si distingues un nodo repetido de un nodo en la ruta actual, utilizando el estado visitado global y el de la ruta para diferentes tareas.
- Si estableces presupuestos para profundidad, nodos, aristas, bytes y tiempo, y luego devuelves una falla procesable para el cliente.
Una respuesta débil añade una profundidad máxima de recursión. Una respuesta sólida cubre la identidad estable de los recursos, ciclos en la ruta frente a subgrafos compartidos, agotamiento del presupuesto, límites del 508 y seguridad de caché multi-inquilino.
Preguntas aclaratorias para hacer primero
- ¿Es la relación un árbol, un DAG o un grafo dirigido arbitrario? Un DAG aún necesita un conjunto de visitados para evitar trabajo duplicado; un grafo arbitrario también necesita detección de ciclos en la ruta actual.
- ¿El cliente necesita una expansión completa, resultados paginados o solo alcanzabilidad? El contrato de salida determina si los resultados parciales o un trabajo asíncrono son válidos.
- ¿Son los IDs de recursos globalmente únicos? Los alias y los enlaces entre inquilinos requieren una identidad canónica antes de construir las claves de visitados.
- ¿Quién controla el presupuesto? El servicio debe imponer límites estrictos; una profundidad proporcionada por el cliente no puede elegir directamente el consumo de base de datos o memoria.
Una respuesta de 30 segundos
“Modelizo la relación como un grafo dirigido y canonizo cada recurso a un ID estable. Durante el recorrido mantengo un conjunto para la ruta actual para detectar ciclos reales y un conjunto global de visitados para evitar volver a expandir subgrafos compartidos. El servicio impone límites estrictos en profundidad, nodos, aristas, bytes de respuesta y tiempo de reloj de pared. Un ciclo detectado puede producir 508; los presupuestos agotados producen un error de límite explícito o el estado de un trabajo asíncrono. Los resultados incluyen una arista de ciclo redactada, el motivo de truncamiento y un ID de solicitud, nunca nodos no autorizados. Las pruebas cubren autociclos, ciclos por alias, subgrafos compartidos, aristas denegadas y grafos profundos hostiles.”
Solución paso a paso
1. Definir el límite del 508
La RFC 5842 utiliza 508 cuando una operación recursiva sobre recursos encuentra un bucle infinito. Las redirecciones URL ordinarias necesitan protección contra cadenas de redirección; un tiempo de espera agotado o un presupuesto agotado necesita su propio error. El estado explica la clase de falla, mientras que el cuerpo proporciona diagnósticos.
2. Canonizar la identidad del recurso
Resuelve un alias a una tupla de inquilino, tipo de recurso e ID inmutable. No uses cadenas de ruta, variantes de mayúsculas/minúsculas o URLs diferentes como claves de visitados. La resolución de alias también necesita un límite de saltos para que no pueda entrar en bucle antes de que comience el recorrido del grafo.
3. Mantener separados el estado de la ruta y el de visitados
path representa la rama DFS actual; una arista a un nodo en path es un ciclo. visited representa nodos ya completados o encolados para esta solicitud y elimina el trabajo duplicado en un grafo con forma de diamante. Un único conjunto combinado o bien reporta un uso compartido legal como un ciclo o bien pasa por alto un ciclo en otra rama.
4. Establecer presupuestos y reglas de truncamiento
Limita la profundidad máxima, nodos, aristas, bytes de respuesta y tiempo de reloj de pared. Aplica presupuestos por inquilino y solicitud, y pagina las lecturas de la base de datos. Al agotarse, devuelve recuentos, un motivo de truncamiento y un mecanismo de continuación. Si el protocolo requiere un resultado completo, crea un trabajo de recorrido asíncrono en lugar de devolver un árbol parcial engañoso.
5. Manejar autorización y almacenamiento en caché
Autoriza cada recurso antes de agregarlo al resultado visible. Las claves de caché deben incluir el inquilino, la versión del permiso y los parámetros de recorrido; de lo contrario, un inquilino podría inferir el nodo oculto de otro inquilino a partir de los diagnósticos del ciclo. Para grafos costosos, almacena en caché las aristas canónicas pero vuelve a verificar la autorización para cada solicitud.
6. Elegir la forma de la respuesta
Cuando se encuentra un ciclo y el cliente comprende los diagnósticos, devuelve 508 con los IDs de ciclo redactados, la ubicación del corte y un ID de solicitud. Si el cliente desea el mejor esfuerzo posible, devuelve una colección paginada exitosa marcada con truncated; eso difiere de la falla de operación completa del 508. No etiquetes el desbordamiento de pila de la base de datos o un bucle propio de proxy como 508 sin que coincida con la causa.
7. Probar ataques y rutas de falla
Prueba un autociclo, A-hacia-B-hacia-A, múltiples alias para un nodo, un subgrafo compartido, una profundidad exactamente en el límite, un abanico de salida (fan-out) enorme, una arista denegada entre inquilinos y tiempo de espera agotado. Verifica que cada nodo se expanda como máximo una vez, que la denegación no altere los recuentos visibles y que los errores no revelen IDs de recursos ocultos.
Respuesta de muestra de alta calidad
“Trato la expansión recursiva como un problema de grafo dirigido. Resuelvo los alias a un inquilino y a un ID de recurso estable, uso el estado de la ruta actual para ciclos reales y uso el estado global de visitados para la deduplicación de subgrafos compartidos. Los presupuestos de profundidad, nodos, aristas, tamaño de respuesta y tiempo son límites estrictos que se pasan a las consultas paginadas. Devuelvo 508 solo cuando la operación recursiva realmente encuentra un ciclo y el cliente admite ese contrato; las redirecciones ordinarias y los tiempos de espera agotados usan sus propios errores. La respuesta contiene únicamente datos de ciclo autorizados y redactados junto con un ID de solicitud. Las claves de caché incluyen inquilino, versión de permiso y parámetros. Las pruebas cubren autociclos, ciclos por alias, grafos en diamante, aristas denegadas y profundidad hostil.”
Errores comunes
- Igualar la profundidad máxima con la detección de ciclos → Los árboles profundos válidos fallan mientras que los ciclos superficiales pueden permanecer → Usa el estado de la ruta para ciclos y la profundidad únicamente como presupuesto.
- Mantener solo visitados globales → Un subgrafo compartido se reporta como un ciclo → Separa la ruta actual del estado de recorrido global.
- Devolver 508 para cada tiempo de espera agotado → Los clientes no pueden distinguir un ciclo en el grafo de una sobrecarga → Haz que el estado coincida con la causa real.
- Expandir antes de la autorización → Los detalles del error pueden filtrar nodos ocultos → Autoriza antes del recorrido visible y el conteo.
- Omitir la versión del permiso en las claves de caché → Los resultados de accesos anteriores siguen siendo visibles → Vincula las entradas de caché al inquilino, versión del permiso y parámetros.
Preguntas de seguimiento y respuestas
Si el grafo es un DAG, ¿por qué mantener el estado de la ruta actual?
El modelo de datos puede prometer un DAG, pero las migraciones, los alias o las escrituras concurrentes pueden violarlo temporalmente. El estado de la ruta es una protección económica en tiempo de ejecución; un ciclo detectado también debería identificar el origen de su escritura y bloquear nuevos enlaces.
¿Se puede devolver 508 cuando el cliente desea los nodos que se hayan encontrado?
No disfraces datos parciales como una falla 508 completa. Define un contrato paginado o asíncrono que devuelva páginas completadas, el motivo de truncamiento y un cursor de continuación. Usa 508 solo cuando el cliente requiera una expansión completa atómica.
¿Cómo evitas que un inquilino con alto factor de ramificación (fan-out) agote la base de datos?
Establece cuotas por inquilino para concurrencia, nodos, aristas, tiempo de consulta y bytes de respuesta; limita la precarga por lotes y aplica contrapresión (backpressure). Encola o rechaza las solicitudes que excedan el presupuesto, monitorea el consumo por inquilino y las causas de fallas, y no permitas que los clientes eludan los límites aumentando la profundidad.