Lwan, un servidor web de alto rendimiento conocido por su eficiencia en memoria, ha reemplazado completamente su tabla hash antigua (basada en el proyecto kmod) por una implementación completamente nueva inspirada en las llamadas 'Swiss Tables'. Este cambio busca resolver años de deuda técnica y complejidad acumulada que estaban causando problemas de estabilidad.
Las Swiss Tables son un diseño de tabla hash desarrollado originalmente por Abseil (la biblioteca estándar de C++ de Google) y adoptado posteriormente por Rust y el lenguaje Go. Su innovación principal radica en cómo procesan la información: el resultado de la función hash se divide en dos partes llamadas H1 y H2. H1 determina la posición inicial donde buscar, mientras que H2 se almacena en lo que se llama 'Control Word' (palabra de control). La genialidad del diseño está en usar instrucciones SIMD para comparar múltiples ranuras simultáneamente, lo que permite búsquedas extremadamente rápidas.
Sin embargo, las implementaciones tradicionales de Swiss Tables requieren SIMD, que no está disponible en todas las arquitecturas. El autor de Lwan optó por usar la función estándar de C 'memchr()' en lugar de SIMD directo, ya que generalmente está implementada con SIMD internamente pero funciona de forma portable. Esto simplificó significativamente la implementación al trabajar con un solo grupo en lugar de múltiples grupos como en el diseño original.
La tabla divide el hash resultante en dos componentes: 'startpos' (posición inicial de búsqueda) y 'tophash' (lo que se busca). Las funciones de búsqueda utilizan memchr() para localizar rápidamente coincidencias de tophash, y luego verifican si la clave es exactamente igual. Curiosamente, aunque teóricamente las búsquedas podrían ser O(capacidad), en la práctica las funciones hash FNV-1a o CRC32 de Intel funcionan tan bien que rara vez se necesita buscar en la segunda mitad de la tabla.
Una limitación importante es que eliminar elementos requiere un 'rehash' completo de toda la tabla, una operación costosa que el autor está investigando cómo optimizar mediante técnicas de rehashing perezoso o en-place.
La nueva implementación incluye pruebas unitarias automáticas que se ejecutan en cada arranque del servidor en modo debug, usando una macro SELF_TEST personalizada que ha permitido refactorizar el código con confianza. El enfoque principal no fue mejorar el rendimiento, sino lograr una implementación más simple y mantenible, aunque se espera que el rendimiento sea superior al diseño anterior.