Recorrido de árboles y pruebas de integración

Las pruebas unitarias demuestran que las funciones individuales funcionan. Las pruebas de integración demuestran que el sistema funciona. Hay una brecha enorme entre "cada pieza funciona aisladamente" y "las piezas funcionan juntas para resolver un problema real". FlinDB cruzó esa brecha a través de una estrategia de pruebas deliberada: cada funcionalidad se validó no solo con pruebas unitarias, sino con pruebas de integración que imitan aplicaciones reales.

Este artículo cubre dos temas interconectados. Primero, cómo FlinDB maneja datos jerárquicos -- árboles, estructuras recursivas y entidades auto-referenciadas. Segundo, cómo probamos todo el motor de base de datos a través de pruebas de integración que simulan plataformas de blog, sistemas de comercio electrónico y aplicaciones de tareas.

Datos jerárquicos en FlinDB

Los árboles están en todas partes en los datos de aplicaciones. Jerarquías de categorías en comercio electrónico. Organigramas en sistemas de recursos humanos. Hilos de comentarios en plataformas sociales. Sistemas de archivos. Estructuras de menú. Navegación anidada. Cualquier dato que tiene una relación padre-hijo forma un árbol.

En el mundo relacional, los datos jerárquicos son notoriamente difíciles. Los enfoques estándar tienen desventajas significativas:

Lista de adyacencia (cada fila tiene una columna parent_id) es simple de escribir pero costosa de consultar. Encontrar todos los descendientes de un nodo requiere CTEs recursivas o múltiples consultas.

Conjuntos anidados (cada fila tiene valores left y right) hace que las consultas de subárboles sean rápidas pero las inserciones y actualizaciones son costosas porque requieren renumeración.

Ruta materializada (cada fila almacena su ruta completa como "/1/3/7/") hace que las consultas de ruta sean rápidas pero las cadenas de ruta son frágiles y difíciles de mantener.

FlinDB toma el enfoque de lista de adyacencia pero lo combina con algoritmos de recorrido de grafos que hacen rápidas las operaciones costosas.

Entidades auto-referenciadas

En FLIN, una entidad auto-referenciada se declara naturalmente:

flinentity Category {
    name: text
    parent: Category?         // Optional self-reference
}

// Build a tree
electronics = Category { name: "Electronics" }
save electronics

phones = Category { name: "Phones", parent: electronics }
save phones

smartphones = Category { name: "Smartphones", parent: phones }
save smartphones

iphones = Category { name: "iPhones", parent: smartphones }
save iphones

El campo parent: Category? crea una referencia anulable al mismo tipo de entidad. ZeroCore almacena esto como un ID de entidad, como cualquier otra referencia. El ? la hace opcional, porque los nodos raíz no tienen padre.

Encontrar ancestros

Para encontrar todos los ancestros de un nodo (el camino de una hoja a la raíz), recorres la referencia parent hacia arriba:

flin// Starting from "iPhones", find the path to the root
node = Category.find(iphones.id)
path = []

while node.parent != none {
    path.push(node)
    node = node.parent
}
path.push(node)  // Add the root

// path = [iPhones, Smartphones, Phones, Electronics]

En ZeroCore, este recorrido usa resolve_reference() en cada paso:

rustlet mut path = Vec::new();
let mut current_id = start_id;

loop {
    let entity = db.find_by_id("Category", current_id)?;
    path.push(entity.clone());

    match entity.fields.get("parent") {
        Some(Value::EntityRef(_, parent_id)) => {
            current_id = *parent_id;
        }
        _ => break,  // Reached the root
    }
}

Debido a que los campos de referencia se indexan automáticamente, cada llamada a find_by_id() es O(1). El recorrido total es O(d) donde d es la profundidad del árbol -- típicamente muy pequeña (5-10 niveles para la mayoría de las jerarquías).

Encontrar descendientes

Encontrar todos los descendientes de un nodo -- todas las subcategorías de "Electrónica" -- usa los métodos de recorrido de grafos de la Sesión 166:

rustlet descendants = db.traverse("Category", electronics_id, "parent", 10)?;

El método traverse() realiza una búsqueda en anchura comenzando desde el nodo dado, siguiendo la referencia parent en reversa (encontrando entidades que referencian al nodo dado). El parámetro de profundidad (10) limita qué tan profundo va el recorrido, previniendo bucles infinitos en caso de referencias circulares accidentales.

Detectar ciclos

Las referencias circulares en un árbol son un bug. Si el padre de la Categoría A es B, el padre de B es C, y el padre de C es A, la jerarquía es inválida. La detección de ciclos de FlinDB captura esto:

rustlet cycles = db.find_cycles("Category", "parent")?;
if !cycles.is_empty() {
    // Report circular references
    for cycle in cycles {
        log("Circular reference detected: {:?}", cycle);
    }
}

La detección de ciclos usa búsqueda en profundidad con un conjunto "visitado". Si DFS encuentra un nodo que ya está en la ruta actual de recorrido, se ha encontrado un ciclo. El ciclo completo se extrae rastreando hacia atrás a través de la ruta.

Ordenamiento topológico

Para árboles de dependencias (la tarea A depende de la tarea B, que depende de la tarea C), el ordenamiento topológico proporciona un orden de ejecución que respeta las dependencias:

flinentity Task {
    name: text
    depends_on: Task?
}

// Tasks with dependencies
deploy = Task { name: "Deploy" }
build = Task { name: "Build" }
test = Task { name: "Test", depends_on: build }
deploy_task = Task { name: "Deploy to prod", depends_on: test }

rustlet order = db.topological_sort("Task", "depends_on")?;
// Returns: [Build, Test, Deploy to prod]
// Each task appears after its dependency

El ordenamiento topológico falla si existen ciclos (no se pueden ordenar dependencias circulares). La implementación de FlinDB detecta esto y devuelve un error con la ruta del ciclo.

Estrategia de pruebas de integración

Las pruebas de integración de FlinDB no son las tradicionales "llama a una API y verifica la respuesta". Simulan escenarios de aplicación completos, ejercitando el stack completo desde la definición de entidades hasta la consulta y eliminación.

La prueba de aplicación de blog

La prueba de blog crea Users y Posts, verificando que el modelo de relaciones completo funciona de extremo a extremo:

rust#[test]
fn test_flindb_blog_example() {
    let mut db = ZeroCore::new();

    // Register schemas
    let user_schema = EntitySchema::new("User")
        .field("name", FieldType::String)
        .field("email", FieldType::String);
    db.register_schema("User", user_schema);

    let post_schema = EntitySchema::new("Post")
        .field("title", FieldType::String)
        .field("body", FieldType::String)
        .field("author", FieldType::EntityRef("User".to_string()));
    db.register_schema("Post", post_schema);

    // Create users
    let user1 = db.save("User", None, hashmap!{
        "name" => Value::Text("Thales".into()),
        "email" => Value::Text("[email protected]".into()),
    }).unwrap();

    // Create posts
    let post1 = db.save("Post", None, hashmap!{
        "title" => Value::Text("Hello World".into()),
        "body" => Value::Text("First post!".into()),
        "author" => Value::EntityRef("User".to_string(), user1.id),
    }).unwrap();

    // Query posts by author
    let thales_posts = db.query("Post")
        .where_ref("author", user1.id)
        .execute()
        .unwrap();
    assert_eq!(thales_posts.len(), 1);
}

Esta prueba ejercita registro de esquemas, creación de entidades, almacenamiento de referencias, consultas de referencia y carga eager -- cinco subsistemas diferentes en una sola prueba. Si cualquiera de ellos está roto, la prueba falla. Si todos funcionan individualmente pero no interoperan, la prueba falla. Este es el valor de las pruebas de integración.

Por qué las pruebas de integración capturan lo que las pruebas unitarias no

Las pruebas unitarias verifican que check_unique_constraints() devuelve un error para valores duplicados. Las pruebas de integración verifican que un email duplicado en una aplicación de blog es correctamente rechazado cuando el usuario intenta registrarse, que el mensaje de error tiene sentido, y que el estado de la base de datos no cambia después del rechazo.

La diferencia es sutil pero crítica. Una prueba unitaria para save() podría pasar incluso si check_unique_constraints() nunca se llama durante save() -- porque la prueba unitaria llama a check_unique_constraints() directamente, no a través de save(). Una prueba de integración que crea dos usuarios con el mismo email fallará si la verificación de restricciones no está conectada en la ruta de guardado.

La estrategia de pruebas de FlinDB fue: pruebas unitarias para corrección algorítmica (ordenamiento, comparación, generación de claves de índice), pruebas de integración para corrección de comportamiento (¿hace el sistema lo correcto en un escenario realista?). Ambas son necesarias. Ninguna es suficiente por sí sola.

Los números de pruebas

A lo largo de todas las sesiones de FlinDB, los conteos de pruebas crecieron de forma constante:

Más de 340 pruebas agregadas solo para FlinDB. La suite total de pruebas del proyecto FLIN superó las 2.400 pruebas -- y cada una pasaba antes de que terminara cualquier sesión.

La disciplina fue absoluta: ninguna funcionalidad se consideraba completa sin pruebas. Ninguna sesión terminaba con pruebas fallando. Ninguna prueba se saltaba o ignoraba sin una razón documentada. Cuando sois dos personas construyendo un motor de base de datos -- un humano, una IA -- la suite de pruebas es tu red de seguridad. Captura regresiones antes de que lleguen a los usuarios. Documenta el comportamiento esperado mejor que cualquier especificación. Y da confianza para hacer cambios agresivos, porque si las pruebas pasan, el sistema funciona.

Esta es la Parte 12 de la serie "Cómo construimos FlinDB", documentando cómo construimos un motor de base de datos embebido completo para el lenguaje de programación FLIN.

Navegación de la serie: - [065] The EAVT Storage Model - [066] Database Encryption and Configuration - [067] Tree Traversal and Integration Testing (estás aquí) - [068] FlinDB Hardening for Production - [069] FlinDB vs SQLite: Why We Built Our Own