Diagnóstico

«Es O(1), no puede ser lento»

Un servicio guarda sesiones en una tabla hash, «que es O(1)». Bajo ataque, con peticiones fabricadas, se vuelve cientos de veces más lento. El equipo cree que es la red.

Un servicio guarda sesiones en una tabla hash, «que es O(1)». Bajo ataque, con peticiones fabricadas, se vuelve cientos de veces más lento. ¿Qué hipótesis explica mejor el síntoma?La red: con peticiones fabricadas llegan más datos y la tabla espera a que lleguen para buscarEl O(1) de la tabla es esperado: claves fabricadas caen en la misma casilla y cada búsqueda recorre muchasEl O(1) de la tabla hash es amortizado: con más peticiones hay que rehacer la tabla y esa copia es la que tardaLa tabla hash es en realidad O(log n): el costo crece despacio y el ataque lo hace visible