Planteamiento y contexto
Esta pregunta evalúa si puedes elegir una estructura de datos para muchos temporizadores aproximados. Un montículo binario (binary heap) ordena los plazos límite (deadlines), por lo que la inserción y la eliminación mantienen el orden del montículo; una rueda de tiempo (timing wheel) asigna plazos límite en buckets y se adapta a tiempos de espera de red, reintentos y señales de mantenimiento de conexión (keepalives) donde el tiempo exacto no es necesario. Explica la precisión, la complejidad, la semántica de cancelación, los retrasos largos y el límite del hilo de ejecución.
Lo que evalúa el entrevistador
- Si conectas el tick, el recuento de buckets, el intervalo cubierto y el plazo límite de la tarea de forma precisa.
- Si manejas las tareas que cruzan una rotación, el trabajo en el bucket actual, los ticks tardíos y la ejecución anticipada.
- Si la cancelación es económica y los nodos cancelados no pueden ejecutarse accidentalmente.
- Si puedes explicar la seguridad entre hilos (thread safety), el aislamiento de callbacks, la elección del reloj y el comportamiento ante sobrecargas.
Preguntas aclaratorias para hacer primero
Confirma el volumen de tareas, el error mínimo y máximo permitido, el retraso mínimo y máximo, la tasa de cancelación y la duración del callback. ¿Deben ser duraderas las tareas y deberían sobrevivir al reinicio del proceso? ¿Pueden múltiples hilos llamar a schedule y cancel? ¿Pueden bloquearse los callbacks? Si un tick contiene demasiadas tareas vencidas, ¿debe retrasarse la ejecución, descartarse el trabajo de baja prioridad o aplicarse contrapresión (backpressure)? Estas respuestas determinan si una sola rueda es suficiente o si necesitas una rueda jerárquica o persistencia externa.
Un marco de respuesta de 30 segundos
Calcularía los plazos límite relativos con un reloj monotónico y avanzaría un cursor a un tick fijo. Para cada tarea, calcularía un índice de bucket y las rondas restantes, guardándola luego en una lista doblemente enlazada. En cada tick, escanearía únicamente el bucket actual: decrementaría y conservaría las tareas con rondas restantes, y retiraría las tareas vencidas para su ejecución cuando las rondas lleguen a cero. Un handle permite que cancel marque y desenlace un nodo. La rueda programa el trabajo, pero nunca ejecuta los callbacks de usuario en el hilo del tick; la precisión, la concurrencia y el comportamiento ante sobrecargas se verifican con pruebas y métricas.
Análisis detallado paso a paso
1. Definir los parámetros de la rueda y el error
Sea tickDuration el tick y wheelSize el número de buckets; una rotación cubre tickDuration × wheelSize. Convierte un plazo límite a ticks relativos y luego calcula (currentTick + remainingTicks) mod wheelSize. El tick determina la resolución mínima, mientras que el intervalo de rotación determina qué retrasos encajan directamente. Para un rango mayor, usa una rueda jerárquica o mantén un valor de rondas restantes hasta que la tarea pueda ubicarse con mayor precisión.
2. Elegir los nodos de tarea y la estructura de buckets
Cada nodo almacena un plazo límite, remainingRounds, callback, bandera de cancelación y punteros anterior y siguiente. Una lista doblemente enlazada proporciona inserción y eliminación en tiempo constante cuando se conoce el nodo; un handle puede apuntar directamente a él, de modo que cancel no realiza búsquedas. No mantengas todas las tareas en un arreglo ni las escanees todas en cada tick, porque el costo crece con el recuento total de tareas.
3. Avanzar ticks y manejar rotaciones
Avanza el reloj monotónico y el cursor, luego desacopla el bucket actual. Si remainingRounds es positivo, decreméntalo y vuelve a insertar el nodo. De lo contrario, compara el plazo límite real: reubica en un bucket una tarea que aún es prematura y envía solo la tarea que esté vencida. Si una pausa del hilo omite muchos ticks, limita el trabajo de puesta al día y registra el retraso para que la recuperación no se bloquee por un tiempo indefinido.
4. Manejar schedule, cancel y condiciones de carrera
Una cola de productores puede enviar solicitudes de schedule y cancel a un único hilo de tick, reduciendo la contención de bloqueos de buckets. Cancel establece la bandera antes de intentar desenlazar; después de que el hilo de tick toma un nodo de un bucket, vuelve a verificar la bandera para que una condición de carrera no ejecute un callback cancelado. Un plazo límite anterior al momento actual debe definirse como "ejecutar en el siguiente tick disponible", no convertirse con un módulo negativo en un bucket futuro arbitrario.
5. Aislar callbacks y sobrecarga
El hilo del tick solo mueve nodos y envía trabajo; un ejecutor acotado (bounded executor) ejecuta los callbacks de usuario. Cuando esté lleno, define una política como límites de cola, descartar trabajo prescindible por prioridad, retrasar trabajo no crítico o devolver un error de sobrecarga. Monitorea el retraso de expiración, el tiempo de escaneo de buckets, las cancelaciones, la longitud de la cola del ejecutor y los fallos de callbacks para determinar si el cuello de botella es la rueda o el ejecutor posterior.
6. Fijar la invariante central con pseudocódigo
El bucle central se puede expresar de la siguiente manera; el bloqueo y la propiedad de los hilos dependen del lenguaje de implementación:
schedule(task, deadline):
ticks = ceil((deadline - now) / tickDuration)
ticks = max(ticks, 0)
node.rounds = ticks / wheelSize
node.bucket = (currentTick + ticks) % wheelSize
buckets[node.bucket].append(node)
return node.handle
advance(now):
while currentTick <= floor(now / tickDuration):
bucket = buckets[currentTick % wheelSize]
for node in bucket.detachAll():
if node.cancelled: continue
if node.rounds > 0:
node.rounds -= 1
bucket.append(node)
elif node.deadline <= now:
executor.submit(node.callback)
else:
schedule(node, node.deadline)
currentTick += 1Respuesta modelo de alta calidad
Primero confirmaría la tolerancia al error, el rango de retraso, la tasa de cancelación, la durabilidad y el bloqueo de callbacks. Usaría un reloj monotónico y ticks fijos, con listas de buckets doblemente enlazadas cuyos nodos almacenan el plazo límite, las rondas restantes, la bandera de cancelación y el handle. Schedule calcula el bucket y las rondas; cancel desenlaza a través del handle y establece la bandera. El hilo del tick procesa únicamente el bucket actual, reduce las rondas para futuras rotaciones y envía los callbacks vencidos a un ejecutor acotado. La puesta al día tras ticks omitidos se limita y se mide; la sobrecarga del ejecutor cuenta con políticas de cola, prioridad y fallos. Las pruebas cubren plazos límite en los límites, retrasos largos, cancelaciones repetidas, schedule/cancel concurrentes, saltos de reloj, excepciones en callbacks y el costo de escaneo con millones de nodos. Si se requiere un margen de error más estricto o un rango más amplio, agrega una rueda jerárquica o un montículo en lugar de afirmar que la rueda siempre es más rápida.
Errores comunes
- Usar la hora de reloj de pared (wall-clock time) para retrasos relativos e ignorar los ajustes del reloj del sistema.
- Olvidar
remainingRounds, haciendo que una tarea se dispare en la primera rotación. - Ejecutar o perder silenciosamente una tarea del bucket actual que aún no está vencida.
- Establecer un booleano de cancelación sin verificarlo nuevamente después de tomar el nodo.
- Ejecutar callbacks de usuario de forma síncrona en el hilo del tick y bloquear la rueda.
- Escanear un arreglo fijo de todas las tareas y perder la eficiencia de la programación dispersa.
- Omitir el comportamiento para ticks omitidos, sobrecarga, recuperación tras reinicios y fallos de callbacks.
Preguntas de seguimiento y respuestas
¿Por qué no usar un min-heap?
Un min-heap se adapta a cargas de trabajo más pequeñas o a un ordenamiento estricto de plazos límite, pero cada inserción o eliminación mantiene el orden del montículo. Una rueda de tiempo sacrifica precisión a cambio de ubicación y eliminación en buckets en tiempo constante, lo que se adapta a muchos temporizadores aproximados. Elige en función del presupuesto de error y la distribución de operaciones en lugar de afirmar que la rueda siempre es más rápida.
¿Qué pasa si el hilo del tick se pausa durante varios segundos?
Usa el tiempo monotónico para calcular los ticks que debieron haber transcurrido, limita la cantidad de buckets o tareas procesadas en una sola pasada de puesta al día y deja el resto para más tarde. Mide el retraso de programación; si una ráfaga es inaceptable, combina el procesamiento por lotes con contrapresión en lugar de ejecutar cada callback de forma síncrona durante la recuperación.
¿Cómo garantizas que cancel no pueda ejecutar una tarea?
El handle apunta al nodo. Cancel lo marca atómicamente antes de desenlazarlo, y el hilo del tick vuelve a verificar la bandera después de desacoplarlo. Si el callback ya fue enviado, define el punto de linealización de la cancelación y haz que el callback verifique el estado de la tarea antes de iniciar.
¿Cuándo se necesita una rueda de tiempo jerárquica?
Usa una cuando una sola rotación no pueda cubrir el plazo límite más grande o los retrasos de las tareas abarquen varios órdenes de magnitud. Agrega niveles superiores más gruesos y transfiere tareas hacia abajo en cascada, definiendo al mismo tiempo la precisión, la degradación y el costo de migración de cada nivel. La durabilidad y la recuperación ante caídas aún requieren separar la rueda del almacenamiento confiable o de la mensajería.