Entrevista técnica: Implementar una caché TTL con expiración

Pregunta y cuándo aplica

Implemente una caché en memoria donde cada clave tenga un valor y un tiempo de expiración. get nunca debe devolver un valor expirado. Explique el reloj, los límites, la limpieza, la capacidad, la concurrencia y la complejidad.

Amazon incluye estructuras de datos, algoritmos y codificación entre los temas de entrevistas de desarrollo de software y enfatiza la aplicación del conocimiento. Redis documenta la semántica de TTL y EXPIRE, incluido el tiempo de vida restante y la precisión. A diferencia de LRU o LFU, este problema se centra en la semántica del tiempo y la limpieza por expiración.

Qué evalúan los entrevistadores

Los entrevistadores buscan una unidad de TTL y un reloj explícitos, un límite de expiración correcto, opciones de limpieza, consistencia concurrente, comportamiento de capacidad y complejidad temporal y espacial.

Preguntas para aclarar antes de responder

• ¿Los TTL están en segundos o en milisegundos? ¿Cero expira inmediatamente?
• ¿El reloj es monotónico?
• ¿Las entradas expiradas deben eliminarse de inmediato?
• ¿Existe una capacidad máxima o una política de LRU?
• ¿Cómo se sincronizan set, get y la limpieza?
• ¿Actualizar una clave reinicia el TTL?
• ¿Se requiere persistencia o uso compartido entre procesos?
• ¿El trabajo de limpieza debe estar delimitado (bounded)?

Estructura de respuesta en 30 segundos

“Almaceno el valor de cada clave y el expiresAt absoluto en una tabla hash. get consulta primero un reloj monotónico; si now es igual o posterior a expiresAt, elimina la entrada y devuelve un fallo de caché (miss). set reemplaza el valor y el TTL. La versión básica utiliza limpieza perezosa (lazy) con un get amortizado O(1) y espacio O(n). Un min-heap o un escaneo acotado maneja las entradas inactivas (cold). Bloqueos o sharding protegen las actualizaciones de la tabla hash y de la limpieza. Las pruebas cubren TTL cero, igualdad, actualización (refresh) y condiciones de carrera.”

Respuesta a fondo, paso a paso

Paso 1: Definir el elemento

Almacene value y expiresAt; ningún TTL puede usar infinito. Utilice una sola regla, now >= expiresAt, en cada ruta de ejecución.

Paso 2: Implementar get y set

get devuelve un miss para una clave ausente. Para una clave expirada, la elimina antes de devolver un miss. set calcula una expiración absoluta y actualiza cualquier índice de limpieza.

Paso 3: Elegir un reloj

Utilice un reloj monotónico para el tiempo transcurrido, de modo que los ajustes del reloj de pared (wall-clock) no puedan extender un TTL. Los diseños con persistencia y entre procesos necesitan una base de tiempo y una precisión explícitas.

Paso 4: Elegir la estrategia de limpieza

La limpieza perezosa es simple, pero las claves inactivas pueden consumir memoria. Un min-heap extrae primero la expiración más próxima; los escaneos periódicos acotan el trabajo pero pueden retrasar la eliminación.

Paso 5: Garantizar la seguridad ante concurrencia

set, get, delete y la limpieza deben coincidir en el mismo valor y expiración. Utilice un bloqueo global, un bloqueo de lectura/escritura o bloqueos particionados (sharded). La actualización del heap y de la tabla debe ser atómica en conjunto.

Paso 6: Separar la capacidad del TTL

El TTL no define la capacidad. Al alcanzar el límite, elija LRU, desalojo aleatorio o rechazar escrituras. Rastree el desalojo de forma independiente a la expiración.

Paso 7: Indicar la complejidad y el pseudocódigo

El límite central es:

get(key):
  item = table[key]
  if item is absent: return MISS
  if clock.now() >= item.expiresAt:
    delete table[key]
    return MISS
  return item.value

get y set perezosos son O(1) amortizado, espacio O(n). La extracción en la limpieza con heap cuesta O(log n).

Paso 8: Probar los casos límite

Pruebe TTL cero, igualdad, actualización (refresh), limpiezas repetidas, cambios de reloj, get/set concurrentes, desalojo por capacidad y fallos inyectados. Inyecte el reloj en lugar de usar sleep en las pruebas.

Ejemplo de respuesta de alta calidad

“Defino CacheItem(value, expiresAt) y almaceno los elementos en una tabla hash. set convierte el TTL en una expiración absoluta; cero significa expirado de inmediato. get consulta un reloj monotónico y elimina el elemento antes de devolver un miss.

La primera versión utiliza limpieza perezosa, con lecturas y escrituras O(1) amortizadas. Para muchas claves inactivas, agrego un min-heap. Cada registro del heap tiene una versión; la limpieza valida la versión antes de eliminar, por lo que un registro antiguo no puede eliminar un valor actualizado. Bloqueos particionados (sharded) protegen la tabla y el heap. Las pruebas cubren igualdad, actualización, limpiezas repetidas, condiciones de carrera y desalojo por capacidad.”

Errores comunes

• Dejar el TTL cero y la igualdad sin definir.
• Usar el tiempo de reloj de pared para el TTL transcurrido.
• Permitir que get devuelva un valor expirado hasta que se ejecute un proceso en segundo plano.
• Ignorar registros obsoletos en el heap después de una actualización (refresh).
• Tratar el TTL como una política de capacidad LRU.
• Mantener un bloqueo global durante una limpieza prolongada.
• Probar únicamente aciertos (hits) y fallos (misses), sin incluir condiciones de carrera en los límites.
• Omitir la precisión y la complejidad.

Preguntas de seguimiento y cómo responder

Pregunta de seguimiento 1: ¿Por qué una expiración absoluta?

Proporciona una única regla de comparación y permite que la limpieza ordene las entradas por expiración. La actualización (refresh) reemplaza expiresAt.

Pregunta de seguimiento 2: ¿Qué sucede si el reloj de pared se retrasa?

Utilice un reloj monotónico para el tiempo transcurrido. Una caché persistente o distribuida necesita una base de tiempo documentada.

Pregunta de seguimiento 3: ¿Sin hilo en segundo plano, pero con muchas claves inactivas?

Realice una limpieza acotada durante las lecturas o escrituras, como un número fijo de extracciones del heap por operación, y acepte un retraso delimitado en la eliminación.

Pregunta de seguimiento 4: ¿Cómo se mantiene la consistencia entre el heap y la tabla?

Utilice un único bloqueo o una operación atómica y una versión en los registros del heap. Elimine únicamente cuando la versión todavía coincida.

Pregunta de seguimiento 5: ¿Qué ocurre al alcanzar la capacidad máxima?

Elimine primero las entradas expiradas, luego aplique la política de desalojo documentada a las entradas activas y registre el motivo.

Pregunta de seguimiento 6: ¿Cómo la comparten múltiples procesos?

Una caché en memoria pertenece a un solo proceso. El uso entre procesos requiere un almacenamiento externo o distribuido con semántica atómica de TTL, reloj y fallos.