MycelK — Fase 1: NodeId, distancia XOR y Kbuckets

#rust #kademlia #p2p #distributedsystems

Vamos a crear crates separados para manejar:

Kademlia: Solo el algoritmo, así podemos hacer tests estáticos fácilmente
Transport: Manejo de UDP/Tokio etc.
Node: El nodo en sí, que usará los crates anteriores

Organizamos las carpetas, scaffoldeamos los crates y configuramos el crate "Node".
"Node" es el crate central, le cambiamos el Cargo.toml para definir las dependencias.

Un pequeño cargo build para asegurarnos de no haber roto la config del Node.

Disclaimer

Normalmente uso Claude Code para acelerar ciertas implementaciones. Sé que si estás leyendo este blog vas a pensar: "Una IA programa esto en 15 minutos, eres un completo inútil".
Como dice el filósofo, la aventura es el camino recorrido, no el destino (o algo así).

Acá no vamos a usar IA para programar. La uso para formatear el blog, realizar investigaciones (best practices, documentación de las libs utilizadas, etc.) pero no va a escribir ni una línea de código en este proyecto. Así que les propongo código 100% orgánico y de vez en cuando no del todo optimizado.

No me juzguen, simplemente tengo ganas de programar y de romperme la cabeza a la antigua.

Empezamos con Kademlia

Primero lo primero: ¿cómo almacenamos el identificador de nodo? No hay u256 en Rust. Vamos a crear nuestra propia estructura [u8; 32] (32x8 = 256):

pub struct NodeId([u8; 32]); // 256 bits, nos pegamos a la spec

Tests y más tests

Ya sé que no soy un gurú del TDD, pero los tests no hacen daño. Vamos a cubrir las mecánicas básicas y le pediremos al amigo Claude que genere tests adicionales para desafiar mi código (dado que no tengo a nadie a mano para hacer peer review).

Me gusta mucho usar IA para generar tests unitarios adicionales, me permite matar dos pájaros de un tiro:

Si no logra generar tests coherentes sin más explicación que "Generate unittests for class/struct/mod XXXX", generalmente es porque el código no está suficientemente documentado
A veces encuentra ángulos de tests que yo no había considerado

Condición de salida fase 1

Le pedí a Claude que organizara el roadmap que había escrito y que le agregara condiciones de salida para cada fase. Le pedí que fuera exigente y me tiró una condición entretenida para la primera fase:
voz de robot: Criterio de salida: routing table correcta sobre 1000 nodos simulados en memoria.
Nada menos.

Entonces vamos, acá está mi función para determinar los nodos más cercanos:

    pub fn get_closest_nodes(&self, searched_node: &NodeId, node_count: usize) -> Vec<NodeId> {
        let center = self.get_bucket_index(searched_node);
        let mut closest_nodes: Vec<NodeId> = Vec::new();

        //Vamos a ver si tenemos suficientes nodes en el bucket objetivo, sino nos moveremos haciendo +/- 1
        closest_nodes.extend_from_slice(&self.routing_table[center]);

        let mut extension = 1usize;
        //Condiciones de parada cuando hayamos dado la vuelta
        let max_extension: usize = 255 - center;

        while closest_nodes.len() < node_count
            && (extension < max_extension)
        {
            if center >= extension {
                closest_nodes.extend_from_slice(&self.routing_table[center - extension]);
            }
            if center + extension <= 255 {
                closest_nodes.extend_from_slice(&self.routing_table[center + extension]);
            }
            extension += 1;
        }

        //Hay que ordenarlos de nuevo si tenemos más que node_count para retornar los más cercanos
        if closest_nodes.len() > node_count {
            closest_nodes.sort_by_cached_key(|n| searched_node.distance(n));
            closest_nodes.truncate(node_count);
        }

        closest_nodes
    }

Todos los tests pasan en verde de primera, excepto el terrible get_closest_nodes_correctness_1000_nodes.
Durante mi análisis me di cuenta de que con una cantidad de nodos inferior a 20, el sort funcionaba y el test pasaba.
Tenemos entonces un problema en el manejo de n > 20, lo que corresponde a un routing map con más de 1 índice lleno.
Mirando un poco la lógica, tengo un error de razonamiento en el sort final.

Hay que ejecutar SIEMPRE closest_nodes.sort_by_cached_key(|n| searched_node.distance(n)); dado que dentro de un bucket los nodos no están ordenados por distancia sino por disponibilidad (vía ping, etc.).

La condición de parada del while también está mal pensada (Matthieu por favor...), los buckets están ordenados respecto al owner, no al searched_node. Diferencia importante.

Tenemos entonces dos maneras de resolverlo:

Un fullscan: Recorremos todos los nodos conocidos, sort, truncate, return.
Optimizamos implementando varias etapas de scan:
- Primero el bucket que corresponde al nodo buscado. Si tiene una cantidad de nodos igual o superior a la cantidad buscada, sort, truncate, return.
- Segunda parte: No tenemos la cantidad de nodos pedida en el centro. Miramos los buckets de 0 a centro. Si tenemos la cantidad buscada, sort, truncate, return.
- Tercera parte: Todavía no tenemos lo que necesitamos, hay que explorar los buckets centro + k y paramos cuando tengamos la cantidad deseada o hayamos agotado los buckets. Sort, truncate, return.

Dije al principio que quería aprender, así que no nos vamos a conformar con el full scan.

    pub fn get_closest_nodes(&self, searched_node: &NodeId, node_count: usize) -> Vec<NodeId> {
        let center = self.get_bucket_index(searched_node);
        let mut closest_nodes: Vec<NodeId> = Vec::new();

        //Primera pasada: Si tenemos lo que necesitamos en el bucket objetivo, sort, truncate, return y listo.
        closest_nodes.extend_from_slice(&self.routing_table[center]);

        if closest_nodes.len() < node_count {
            //Segunda pasada: Revisamos los nodos cercanos
            let mut extension = 0usize;
            while extension < center {
                closest_nodes.extend_from_slice(&self.routing_table[extension]);
                extension += 1;
            }

            //Tercera pasada: Chequeamos los siguientes
            extension = center + 1;
            while extension < 255 && closest_nodes.len() < node_count {
                closest_nodes.extend_from_slice(&self.routing_table[extension]);
                extension += 1;
            }
        }

        closest_nodes.sort_by_cached_key(|n| searched_node.distance(n));
        closest_nodes.truncate(node_count);

        closest_nodes
    }

Y ahí tenemos derecho a un bonito output de terminal:

running 17 tests
test k_bucket::tests::add_myself ... ok
test k_bucket::tests::add_node_to_full_bucket_head_responds ... ok
test k_bucket::tests::add_same_node_twice ... ok
test k_bucket::tests::add_same_node_moved_to_tail ... ok
test k_bucket::tests::add_unknown_node_to_bucket ... ok
test k_bucket::tests::get_closest_nodes_returns_all_when_fewer_than_k ... ok
test k_bucket::tests::has_node_returns_none_when_absent ... ok
test k_bucket::tests::has_node_with_explicit_bucket_index ... ok
test node_id::tests::xor_identity ... ok
test node_id::tests::xor_symmetry ... ok
test k_bucket::tests::get_closest_nodes_never_exceeds_k ... ok
test k_bucket::tests::has_node_returns_some_when_present ... ok
test k_bucket::tests::get_bucket_index_basic ... ok
test k_bucket::tests::get_closest_nodes_correctness_1000_nodes ... ok
test node_id::tests::test_node_id_creation ... ok
test k_bucket::tests::get_closest_nodes_owner_never_in_result ... ok
test k_bucket::tests::get_closest_nodes_empty_routing_table ... ok

test result: ok. 17 passed; 0 failed; 0 ignored; 0 filtered out; finished in 0.02s