Consigna y contexto
Diseña un servicio anti-entropy en segundo plano para un almacén clave-valor replicado. Los nodos pueden estar temporalmente fuera de línea mientras las escrituras continúan; el sistema debe evitar escaneos completos y converger eventualmente. Explica cómo los árboles de Merkle localizan diferencias, cómo se limita la tasa de reparación y cómo se evita que las réplicas desactualizadas sobrescriban datos más nuevos.
El artículo de Dynamo describe un árbol de Merkle por rango de claves: primero se comparan la raíz y los nodos internos, y luego se sincronizan únicamente los rangos de hojas con hashes diferentes. La entrevista consiste en conectar la detección, el arbitraje de versiones, la reparación concurrente, los presupuestos de recursos y la observabilidad en un solo protocolo.
Qué está evaluando el entrevistador
El entrevistador está evaluando objetivos de consistencia, versionado, límites de partición y de actualización de árboles, comparación incremental, reparación idempotente, limitación de tasa (throttling), reintentos, cambios de topología y un argumento de convergencia verosímil. Explica cuándo se necesita read repair o recuperación manual humana.
Preguntas para clarificar
Confirma las particiones del espacio de claves, el factor de replicación, la consistencia de lectura y escritura, la representación de versiones, la semántica de eliminación, la desactualización tolerada, el tamaño de los datos y el ancho de banda para reparación. Pregunta sobre el modelo de fallas, particiones, cifrado, aislamiento de inquilinos (tenants) y si la reparación puede compartir recursos con el tráfico de negocio.
Respuesta de 30 segundos
“Mantendría un árbol de Merkle versionado por nodo virtual o rango de claves. Los pares intercambian el rango, el hash raíz y la marca de agua (watermark) de la instantánea; las raíces iguales omiten el trabajo, mientras que las raíces desiguales descienden recursivamente a las hojas con diferencias y agrupan las claves en lotes. Las escrituras de reparación llevan versiones o tombstones y utilizan reglas deterministas de conflicto que rechazan valores desactualizados. Lotes idempotentes, leases, presupuestos de ancho de banda, reintentos y métricas de saturación mantienen la reparación segura. La antigüedad de la reparación, el conteo de diferencias y las lecturas muestreadas de réplicas demuestran la convergencia.”
Respuesta detallada
Paso 1: Definir particiones y versiones
Divide el espacio de claves en rangos estables con un conjunto de réplicas propietarias. Cada registro lleva una versión monotónica, un vector clock o una versión causal. Las eliminaciones necesitan tombstones que se propaguen; la ausencia de un registro no puede significar “nunca existió”.
Paso 2: Construir un árbol de Merkle comparable
Las hojas agregan claves y resúmenes (digests) de versión en un orden determinista; los padres almacenan los hashes de sus hijos. Tanto las reconstrucciones como las actualizaciones incrementales son posibles, pero el límite de la instantánea de escritura debe ser explícito para que una raíz tenga un significado único.
Paso 3: Comparar desde la raíz hasta las hojas
Compara primero la identidad del rango y las raíces. Raíces iguales no requieren transferencia. Raíces desiguales descienden recursivamente a través de los hijos hasta encontrar los rangos divergentes más pequeños, y luego se agrupan en lotes las claves y los resúmenes de versión. Divide rangos muy activos (hot ranges) o limita el tamaño del lote para que una reparación no bloquee otras particiones.
Paso 4: Arbitrar versiones y eliminaciones
Compara las relaciones de versión cuando llega una clave divergente. Las versiones concurrentes no pueden resolverse únicamente por la hora de llegada; fusiona, conserva el conflicto o aplica una regla de negocio. Los tombstones necesitan un período de retención y una marca de agua segura antes de su limpieza.
Paso 5: Hacer que los lotes de reparación sean idempotentes
Un lote lleva su rango, versión de instantánea, secuencia y digest. Repetirlo no tiene ningún efecto secundario adicional. El destino verifica la versión antes de aplicarlo; un lote antiguo se rechaza o se omite de forma segura. Los resultados son reproducibles y auditables.
Paso 6: Presupuestar recursos y concurrencia
Establece presupuestos de concurrencia, ancho de banda, CPU, lectura de disco y colas por inquilino, rango, nodo y prioridad. El tráfico de negocio tiene prioridad. Pausa la reparación cuando un nodo esté sobrecargado o el retraso de replicación supere un umbral. Agrega variación aleatoria (jitter) al retroceso exponencial (exponential backoff) para que los nodos no reintenten al mismo tiempo.
Paso 7: Manejar cambios de topología y fallas
Recalcula los conjuntos de réplicas y los metadatos del árbol cuando los nodos se unan, se retiren o los rangos se muevan. Persiste el progreso, las instantáneas y los leases para que un reinicio pueda reanudar la operación. Durante una partición de red, continúa aceptando escrituras pero expón estados desactualizados y de conflicto en lugar de afirmar que hay convergencia.
Paso 8: Demostrar convergencia y operar
Monitorea la última hora de reparación, claves divergentes, antigüedad de tombstones, lotes fallidos, conflictos de versión y ancho de banda por rango. Periódicamente compara lecturas muestreadas entre réplicas y establece un SLO de desactualización máxima. Genera alertas, aísla o recupera un rango manualmente cuando la reparación falle de forma persistente en lugar de reintentar indefinidamente.
Respuesta modelo
Particionaría el espacio de claves en rangos de nodos virtuales y mantendría un árbol de Merkle con digests de versión para cada rango. Los pares intercambian la identidad del rango, el hash raíz y la marca de agua de la instantánea; las raíces iguales se omiten, mientras que los árboles desiguales descienden recursivamente a las hojas con diferencias y transfieren únicamente esas claves. Los registros usan vector clocks o versiones monotónicas, las eliminaciones usan tombstones y los conflictos siguen una regla determinista de fusión o arbitraje; una versión más antigua no puede ganar solo por haber llegado más tarde. Los lotes de reparación llevan instantánea, secuencia y digest, y son idempotentes. Presupuestos por inquilino, rango, nodo y ancho de banda protegen el tráfico de negocio, con backoff con jitter ante fallas. Los cambios de topología recalculan conjuntos de réplicas y leases. Operaciones rastrea diferencias, antigüedad de reparación, conflictos, tombstones y fallas, muestrea lecturas de réplicas y establece un SLO de desactualización. Una divergencia persistente aísla un rango para recuperación manual humana.
Errores comunes
Enviar todo el shard cuando la raíz difiere
El propósito de un árbol de Merkle es localizar recursivamente el rango divergente más pequeño. Una transferencia completa multiplica el costo de red y disco y puede bloquear particiones muy activas.
Resolver todos los conflictos con last-write-wins
El desfase de reloj (clock skew) y las escrituras concurrentes hacen que la hora de llegada sea una señal causal poco confiable. Utiliza relaciones de versión, reglas de fusión o arbitraje de negocio.
Ignorar eliminaciones y tombstones
Si una eliminación desaparece de inmediato, una réplica retrasada puede resucitar el valor antiguo. La retención de tombstones y la limpieza segura son parte de la convergencia.
Preguntas de seguimiento y respuestas
¿Cómo manejan los árboles de Merkle las escrituras continuas?
Compara una instantánea consistente o marca de agua de versión mientras las nuevas escrituras entran con versiones posteriores; avanza la marca de agua de reparación después de que se complete el lote. Una raíz cambiante no representa una instantánea única.
¿Qué pasa si un rango es extremadamente activo?
Divídelo aún más, limita el lote y la concurrencia, y prioriza el rango secundario con la mayor ventana de desactualización. Reduce temporalmente la amplificación de lectura o mueve réplicas cuando sea necesario.
¿Qué sucede si un nodo se reinicia a mitad de la reparación?
Reanuda a partir de un lease, la secuencia de lotes y el progreso persistido. Las verificaciones de versión del lado de destino hacen que los lotes duplicados sean seguros, y el origen revalida la instantánea.
¿Cómo evitas que los tombstones antiguos se eliminen demasiado pronto?
Límpialos solo después de que todas las réplicas relevantes superen una marca de agua segura o un punto de confirmación (acknowledgement), y monitorea la antigüedad del tombstone más viejo. Consérvalos cuando falte confirmación.
¿En qué se diferencia read repair de anti-entropy?
Read repair corrige las diferencias descubiertas en la ruta de lectura de negocio y cubre claves calientes (hot keys). Anti-entropy es un escaneo proactivo en segundo plano y cubre datos fríos (cold data). Ambos comparten la semántica de versiones y reparación.
¿Cuándo debe detenerse la reparación automática?
Pausa y aísla un rango cuando los conflictos no puedan fusionarse, los datos estén corruptos, la autorización sea anormal o los recursos permanezcan sobrecargados. Preserva evidencia e instantáneas para la recuperación manual humana.