Consigna y contexto
Implementa un Xor Filter estático con construcción por lotes y consultas de pertenencia. Explica la disposición de tres segmentos, la cola de peeling, la asignación de huellas digitales, los reintentos de construcción, la tasa de falsos positivos y por qué no se admite la eliminación in situ.
Un Xor Filter es una estructura estática de pertenencia aproximada: almacena una huella digital corta para cada clave y aplica una operación XOR a las huellas en tres posiciones durante una consulta. Las investigaciones demuestran que puede competir con los filtros de Bloom y Cuckoo en espacio y velocidad de búsqueda, pero su construcción depende de un hipergrafo aleatorio pelable (peelable). Una semilla fallida requiere una reconstrucción, por lo que la estructura se adapta a la generación por lotes seguida de una publicación de solo lectura.
Qué evalúa el entrevistador
El entrevistador verifica si puedes construir los tres arreglos, manejar duplicados y un conjunto vacío, pelar un hipergrafo con una cola de grados, asignar huellas digitales en orden inverso, usar un hashing idéntico para la construcción y la consulta, calcular falsos positivos, explicar los límites de eliminación y actualización, y razonar sobre reintentos, memoria máxima (peak memory) y lecturas concurrentes.
Preguntas para clarificar
Conjunto de datos y modelo de actualización
Confirma el recuento de claves, la política de duplicados, la frecuencia de reconstrucción, la latencia de actualización y si la eliminación es obligatoria. Los Xor Filters están orientados a conjuntos estáticos; las cargas de trabajo dinámicas deberían compararse con Cuckoo Filters o reconstrucciones por capas.
Objetivos de error y espacio
Confirma la tasa aceptable de falsos positivos, el ancho de la huella digital, si se permiten falsos negativos y la prioridad entre el rendimiento de búsqueda y el pico de memoria de construcción.
Límite de claves y hash
Confirma si las claves son enteros, cadenas de bytes u objetos estructurados; cómo se persiste la semilla de hash; y si las implementaciones en diferentes lenguajes requieren un orden de bytes (byte order) y una normalización idénticos.
Respuesta de 30 segundos
“Divido la tabla en tres segmentos; cada clave se asigna a una posición en cada segmento y almacena una huella digital de ancho fijo. Durante la construcción, realizo un seguimiento de los grados de las ranuras (slots) y de las aristas incidentes, pelo las ranuras de grado uno y reconstruyo con una nueva semilla si quedan aristas. En orden inverso al peeling, a una ranura se le asigna la huella digital de la clave XOR los otros dos valores de ranura. Una consulta vuelve a calcular las tres posiciones y aplica XOR sobre ellas; la igualdad significa ‘posiblemente presente’. La tabla es estática y aproximada, por lo que no admite una eliminación in situ segura.”
Solución paso a paso
Paso 1: Definir el diseño y las huellas digitales
Deriva tres posiciones y una huella digital de bits bajos a partir de resultados de hash independientes de 64 bits. Divide la tabla en segmentos aproximadamente iguales y reduce cada posición dentro de su segmento. Define el manejo de huellas digitales cero de manera consistente para que una ranura vacía no se confunda con un valor real.
Paso 2: Construir los grados del hipergrafo
Trata cada clave como una hiperarista que conecta tres ranuras. Durante la construcción, almacena el grado de cada ranura y la lista de aristas incidentes, luego encola las ranuras de grado uno. Desduplica las claves primero o define la semántica de conjuntos explícitamente; de lo contrario, una hiperarista puede contarse repetidamente.
Paso 3: Pelar el grafo
Extrae una ranura de grado uno, encuentra su arista única y registra la arista, la ranura única y las otras dos ranuras. Elimina la arista y decrementa el grado de las tres ranuras; encola las ranuras que pasen a ser de grado uno. Si quedan aristas no eliminadas después de que la cola se vacíe, esta semilla produjo un grafo no pelable.
Paso 4: Asignar huellas digitales en orden inverso
Procesa las aristas registradas en el orden inverso al peeling. Establece la ranura única con la huella digital de la clave XOR los valores actuales de las otras dos ranuras. Aplicar XOR a las tres ranuras produce entonces la huella digital de esa clave; las ranuras no escritas contribuyen con cero.
Paso 5: Implementar la búsqueda
La búsqueda utiliza la misma semilla, función de posición y función de huella digital que la construcción, lee los tres segmentos y aplica XOR entre ellos. La igualdad significa únicamente “posiblemente presente”, no una prueba de pertenencia; el llamador debe resolver los aciertos consultando una base de datos o un conjunto exacto.
build(keys):
repeat with a new seed:
edges = positions_and_fingerprints(keys, seed)
queue = all degree-1 slots
order = peel(edges, queue)
if order contains every edge:
table = zeroed slots
for edge in reverse(order):
table[edge.unique] = edge.fp XOR table[edge.other1] XOR table[edge.other2]
return seed, table
fail after bounded retries
contains(key):
a, b, c = positions(key, seed)
return table[a] XOR table[b] XOR table[c] == fingerprint(key)Paso 6: Manejar fallos y recursos
Un fallo de construcción no es un falso negativo de búsqueda; significa que el grafo para esta semilla no tiene un orden de peeling completo. Limita los reintentos, cambia la semilla o el tamaño de la tabla y devuelve un error explícito en lugar de publicar una tabla parcial. Los arreglos de grados, las listas de aristas y la pila de peeling hacen que el pico de memoria de construcción sea mayor que el de la tabla final de solo lectura.
Paso 7: Explicar actualizaciones y verificación
La tabla resuelve ecuaciones sobre el conjunto completo de claves, por lo que una inserción o eliminación puede romper las relaciones XOR de otras claves. Actualiza reconstruyendo, intercambiando atómicamente dos versiones o superponiendo filtros pequeños por capas. Prueba un conjunto vacío, una sola clave, duplicados, colisiones de hash, construcciones fallidas, recuperación por serialización, falsos positivos y búsquedas concurrentes de solo lectura.
Respuesta modelo
Mapearía el conjunto de claves a un hipergrafo 3-uniforme de tres segmentos, lo pelaría con una cola de grados y asignaría huellas digitales cortas en orden inverso al peeling. La búsqueda realiza tres lecturas de ranuras y operaciones XOR, por lo que es de tiempo constante, pero el resultado es una pertenencia aproximada. Un fallo de construcción significa que la semilla actual no es pelable; reintentaría con una nueva semilla bajo un límite y rechazaría la publicación tras alcanzar el límite. Debido a que la tabla depende de cada clave, la inserción o eliminación in situ no es segura; las actualizaciones en producción reconstruyen una nueva tabla y la intercambian atómicamente. Persiste la semilla, el tamaño de la tabla, el ancho de la huella digital y el orden de bytes con la versión, y luego mide los falsos positivos frente a un conjunto exacto.
Errores comunes
- Error: Devolver una tabla parcial después de que falla la construcción. → Por qué falla: Las aristas no procesadas pueden generar falsos negativos. → Solución: Cambia la semilla o el tamaño de la tabla y publica solo después de que se hayan asignado todas las aristas.
- Error: Usar una semilla o un mapeo de segmentos diferente en la búsqueda. → Por qué falla: La construcción y la búsqueda se dirigen a ranuras diferentes. → Solución: Persiste y versiona la semilla, los límites de los segmentos y la implementación del hash.
- Error: Tratar una búsqueda positiva como pertenencia exacta. → Por qué falla: Las huellas digitales cortas generan falsos positivos. → Solución: Usa el filtro como una comprobación previa y luego consulta el almacenamiento exacto.
- Error: Admitir la eliminación in situ. → Por qué falla: Las ranuras compartidas participan en otras ecuaciones XOR. → Solución: Reconstruye, usa dos versiones o elige un filtro dinámico.
Preguntas de seguimiento y respuestas
¿Por qué usar tres segmentos en lugar de un solo arreglo?
Tres segmentos le dan a cada arista una ranura en cada región, lo que hace práctica la construcción del hipergrafo pelable y la búsqueda en tiempo constante. Las proporciones exactas y el factor de carga deben evaluarse mediante benchmarks.
¿Cómo se elige el ancho de la huella digital?
Huellas digitales más cortas reducen el espacio pero aumentan los falsos positivos. Mide los fallos con claves independientes y equilibra el costo resultante de búsqueda en el almacenamiento exacto frente al ahorro de memoria.
¿Los reintentos de semilla hacen que los resultados sean inestables?
La tabla cambia, pero las búsquedas son reproducibles cuando la semilla final, la versión y la tabla se persisten juntas. Incluye los metadatos de construcción en el mismo manifiesto de versión.
¿Cuándo elegirías un Bloom o un Cuckoo Filter en su lugar?
Inserciones, eliminaciones, conteos o cambios de tamaño en línea frecuentes favorecen un filtro dinámico. Los Xor Filters son más fuertes para conjuntos estáticos construidos por lotes donde la búsqueda compacta de solo lectura es prioritaria.