Un éxito absurdo
(marginalia.nu)- Marginalia Search redujo recientemente a la mitad los requisitos de RAM y disminuyó mucho la carga operativa de tener que apagar el motor de búsqueda durante las actualizaciones
- La falla se hizo visible durante el cambio de índice tras el lanzamiento más reciente, y una estructura que borraba la base de datos de URL durante la actualización terminó provocando largos periodos fuera de línea
- El almacén de URL pasó de una enorme tabla e índices en MariaDB a una sola base de datos SQLite y una estructura de IDs de URL de 64 bits generados por proceso
- La creación del índice invertido dejó atrás el lexicon para IDs de términos densos y las grandes escrituras aleatorias, y cambió a un método que crea pequeños preindex y luego los fusiona
- La nueva estructura permite respaldos en archivos que pueden restaurarse en pocas horas incluso tras un mal despliegue, y facilita reutilizar resultados del procesamiento de grandes conjuntos de datos que cambian poco, como Wikipedia
Las condiciones operativas del motor de búsqueda cambiaron en una semana
- Marginalia Search redujo varios problemas de largo plazo al mismo tiempo con una semana de trabajo de programación
- Los requisitos de RAM del motor de búsqueda se redujeron a la mitad
- Desapareció la necesidad de poner el sistema fuera de línea durante las actualizaciones
- Se eliminó el límite duro en la cantidad de documentos indexables
- El límite blando en la cantidad de palabras clave que podían incluirse en el corpus aumentó 4 veces
- El objetivo de largo plazo era mantener el sistema operativo incluso en hardware de bajo rendimiento, y este cambio representa una mejora aún mayor que una optimización anterior, cuando una máquina de desarrollo con 32 GB de RAM ya se sentía holgada
La estructura anterior de actualización amplificó la caída
- Marginalia Search estuvo fuera de línea casi una semana por problemas en el lanzamiento más reciente
- La causa directa fue una cadena de problemas de escalabilidad relativamente menores, pero hubo que reiniciar varias veces un proceso que normalmente toma 1 día y, si hay problemas, entre 2 y 3 días
- La mayoría de los reinicios ocurrieron por falta de RAM
- La razón por la que la caída fue tan visible para los usuarios fue que el sistema tenía que ponerse fuera de línea durante el cambio de índice
- En la estructura anterior, la base de datos de URL se borraba durante la actualización, y el cuello de botella era insertar y actualizar filas rápidamente en una tabla de casi mil millones de registros
- El proceso que cargaba los datos nuevos consumía mucha RAM
- Era difícil ejecutarlo al mismo tiempo que el servicio de indexación, que consumía RAM de la misma forma
- La clave primaria era un entero de 32 bits, así que había un límite difícil de superar más allá de los 2 mil millones
Rediseño de la base de datos de URL
- La base de datos de URL era un componente antiguo del motor de búsqueda, y sus decisiones de diseño iniciales ya no encajaban con la estructura actual del sistema
- En el núcleo había dos tablas que solo se usaban al cargar un índice nuevo y se leían únicamente por búsqueda de clave primaria
- La tabla URL asignaba un ID numérico único a cada URL
- La tabla PAGE_DATA guardaba información como el título y la descripción de los enlaces indexados
- Había un índice adicional para mantener la unicidad de rutas dentro de cada dominio, pero era muy grande para el papel que cumplía
- La nueva estructura combina ambas tablas en una sola base de datos SQLite de tabla única, delega la generación de IDs únicos al proceso cargador y maneja en una tabla separada la lista de URL que no se indexan
- Usar MariaDB y SQLite juntas no es una elección convencional, pero ambos almacenes cubren necesidades distintas
- El sistema necesita una visión del mundo persistente relativamente pequeña
- Al mismo tiempo, debe poder reemplazar estado de escala terabyte como si fuera plug and play
- Las tablas DOCUMENT y DOMAIN están relacionadas de forma laxa a través de las bases de datos, pero no requieren joins reales
- En una situación de desastre, las partes importantes de la tabla DOMAIN pueden reconstruirse a partir de la tabla DOCUMENT
Crear IDs de URL de 64 bits sin índices
- La tabla URL anterior usaba IDs de 32 bits, y la cercanía al desbordamiento entero era un problema de escalabilidad ya conocido
- Una de las razones para borrar la base de datos de URL era justamente evitar que la columna de IDs se desbordara
- Un contador simple no bastaba para manejar URLs repetidas, y también había que evitar mantener en memoria una colección de todas las URLs ya vistas
- El nuevo método ya no hace que la base de datos asigne el ID, sino que construye directamente IDs de 64 bits
- Los 26 bits inferiores se usan como número secuencial
- Los bits 26 a 56 se usan como ID de documento
- Los bits más altos quedan reservados para un truco de ordenamiento del índice
- Esta distribución permite alrededor de 67 millones de documentos por dominio
- Es unas 10 veces el tamaño de la Wikipedia en inglés
- Permite hasta 2 mil millones de dominios
- Es casi 100 veces la cantidad de dominios en los que Marginalia ha visto referencias en toda la web
- La responsabilidad por la integridad de los datos pasa de la base de datos al proceso que los genera, pero el costo de imponerla ahí es mucho menor
Cómo el rediseño de URL redujo la carga de memoria
- Al eliminar enormes índices y una gran tabla con datos de URL calientes y fríos mezclados, el servidor MariaDB ya no necesita 36 GB de RAM
- Los datos calientes que quedan en MariaDB son de como mucho unos cientos de MB, y probablemente ya no haga falta asignarle más de 2 GB de RAM al servidor
- Los datos de SQLite siguen necesitando un índice para la clave primaria, pero se espera que la parte realmente caliente del índice sea menor a 1 GB
- La cantidad de datos que se indexan se redujo en un orden de magnitud
- El índice apunta a un único long de 64 bits
- No hay restricciones únicas adicionales
- Como la salida del cargador pasó a ser un conjunto de archivos, ahora es más fácil crear respaldos automáticos
- Incluso si ocurre un mal despliegue, se puede recuperar en pocas horas en vez de tardar casi una semana como antes
Cuello de botella en la creación del índice invertido
- El cargador produce la base de datos de URL y un journal centrado en documentos con forma
(document, words[]), pero la búsqueda necesita un índice transpuesto con forma(word, documents[]) - El método anterior usaba un lexicon que asignaba cadenas de palabras clave a IDs de términos densos
- La primera palabra recibía el ID 0, la siguiente el ID 1, y así sucesivamente
- Las cadenas se mapeaban a
longmediante hashes de 64 bits - La estructura era, en la práctica, un open hashmap de
longaint
- Esta estructura se llenaba con facilidad al crecer la escala
- Java no permite arreglos de más de 2 mil millones de elementos
- La implementación usada ya se topaba con un límite alrededor de mil millones
- Con mil millones de entradas usaba 12 GB de RAM
- El servicio de indexación en producción usa 60 GB de RAM, y la mayor parte es memoria off-heap
- También era un problema que el tamaño on-heap superara los 32 GB, lo que dificulta usar CompressedOOPs
La amplificación de escritura del algoritmo anterior de índice invertido
- El algoritmo anterior encontraba el ID de palabra más grande, creaba un arreglo
countsde ese tamaño, calculaba la posición de cada documento por palabra y escribía los datos de documentos en un archivo memory-mapped - Ese método necesitaba el lexicon porque asumía que el dominio de IDs de palabra estaba densamente ocupado
- El cuello de botella más grande era escribir casi 1 TB de datos en un archivo memory-mapped en un orden casi completamente aleatorio
- Los SSD manejan bien el acceso aleatorio en lectura, pero con escrituras pequeñas aparece el problema de write amplification
- Incluso para actualizar un byte del disco, un SSD tiene que borrar y volver a escribir una página completa
- Hay cachés que agrupan escrituras cercanas, pero no ayudan mucho con escrituras aleatorias a escala de terabytes
- Mientras se escribía 1 TB, la unidad terminaba escribiendo alrededor de 0.5 PB
- Como mitigación temporal existía
RandomWriteFunnel- Primero dividía las escrituras en buckets de archivos pequeños
- Luego escribía los archivos grandes en orden
- Era mejor que el método original, pero seguía siendo muy lento
Crear pequeños preindex y fusionarlos
- La nueva creación del índice invertido genera varios índices pequeños en los que todos los datos caben en memoria y luego los fusiona
- La fusión de listas ordenadas es rápida y funciona incluso en discos duros mecánicos
- Con este método, el lexicon deja de ser necesario
- El hash de cadena de 64 bits puede usarse directamente como ID de término
- Los problemas iniciales estuvieron en que la entrada está comprimida y en la forma de fusionar los índices
- En vez de leer rápido partes de la entrada comprimida, se crean varios archivos pequeños y se leen uno por uno
- En vez de fusionar los índices después de crearlos, se fusionan los datos antes de crear el índice
- La nueva abstracción
preindexestá compuesta por un arreglo de IDs de palabras, un arreglo de conteos y un arreglo de datos de documentos - Como la entrada es pequeña, la mayor parte del preindex puede construirse en RAM, confirmarse en disco durante la creación y luego convertirse en el preindex final en una etapa posterior de fusión
- El preindex final se transforma luego en un índice invertido, como antes, agregando una tabla de palabras y un índice btree estático a cada bloque de documentos, y este proceso es relativamente rápido
Cambios en operación y reutilización de datos
- Al eliminar el lexicon, bajaron los requisitos de RAM y la nueva creación del índice invertido es más rápida que el algoritmo anterior
- El lexicon anterior creaba un dialecto distinto para cada lote de datos procesado
- La misma palabra podía recibir un ID en una ejecución y otro diferente en otra
- Por eso era necesario procesar todos los datos al mismo tiempo
- Al abandonar el lexicon, ahora es posible fusionar distintos lotes de datos
- Se pueden reutilizar resultados del procesamiento de datos grandes y que cambian poco, como Wikipedia, y combinarlos con datos de indexación que cambian con más frecuencia
- Este cambio redujo casi todos los problemas conocidos de escalabilidad y las incomodidades operativas, y dejó el sistema en condiciones de revisar más efectos secundarios
2 comentarios
Éxito absurdo
Marginalia - motor de búsqueda DIY operado de forma independiente
Opiniones de Hacker News
Da mucho gusto ver casos de éxito así en proyectos que van en una dirección totalmente opuesta al resto del mundo
Me gustaría llamarlo Engildification, y debería haber más cosas así
También me gustó el artículo Sleeping At Night y, junto con el reciente “Lie Still in Bed”, parece una opción muy simple para intentar corregir el problema del entrenamiento del sueño
En el caso del motor de búsqueda Marginalia, su autor pasó hace poco a dedicarse a tiempo completo y, hasta donde sé, el equipo es de una sola persona, así que está lo más lejos posible del riesgo de enshittification. Más bien, a esa escala es donde se crean joyas y donde brillan la creatividad, la originalidad y la visión
Este comentario fue patrocinado por el grupo “deja tu trabajo de oficina y trabaja de forma independiente”
Redujo a la mitad el consumo de recursos, fue más productivo que antes con una pantalla más pequeña y por la noche duerme como un tronco
Enlace para quien tenga interés: https://www.marginalia.nu/log/86-sleep/
Como referencia, Kagi, el motor de búsqueda de paga que quizá hayan visto también en Hacker News, usa Marginalia como una de sus fuentes de datos
https://help.kagi.com/kagi/search-details/search-sources.htm...
Si usas la lente “non-commercial”, se priorizan estos resultados junto con los del propio índice de Kagi y algunas fuentes independientes
Al leer esto, me hace pensar que quizá los humanos somos seres a los que les cuesta crear algo sobresaliente sin restricciones artificiales
La razón por la que Marginalia es absurdamente eficiente es que Victor limita deliberadamente el hardware de ejecución y la capacidad de memoria
Si simplemente le agregara 32 GiB más, probablemente seguiría funcionando por un tiempo, pero el diseño ineficiente quedaría ahí, y más adelante el mismo problema podría explotar en un estado más complejo y ser más difícil de arreglar
Si esta suposición es correcta, también explica por qué el software actual está inflado, es lento y tiene tantos bugs. Como cada software por separado casi nunca llega a sus límites, cada pieza puede ser ineficiente, pero con una M2 Pro moderna y conexiones de nivel GiB se sigue adelantando al punto donde aparecería el problema
La conclusión podría ser que imponerse límites a uno mismo termina siendo mejor, a largo plazo, para uno y para todos
En muchas aplicaciones no tiene sentido dedicar tanto tiempo a pequeñas optimizaciones. Si puedes agregar 32 GiB de RAM a un servidor por menos de 50 dólares, comparado con gastar más de 40 horas de un desarrollador a al menos 20 dólares por hora, desde el punto de vista del negocio la respuesta es obvia. Además, el sitio web estuvo caído toda una semana, y eso por sí solo puede matar a la mayoría de los negocios
A los técnicos nos gusta profundizar así, y quisiéramos microoptimizar incluso código trivial durante años, pero el yak shaving interminable no genera dinero. Si el código solo corre en muy pocas máquinas, normalmente no vale la pena. Además, estas optimizaciones muchas veces terminan en código más difícil de mantener
Creo que la bloatwareización del software en apps que corren en dispositivos de usuarios hoy viene en gran parte del desajuste entre los equipos de los desarrolladores y los de los usuarios. Los desarrolladores necesitan estaciones de trabajo potentes para trabajar y también hacen ahí las pruebas básicas, pero los usuarios ejecutan la app en dispositivos que hace 5 años eran de gama media o inferior
Es difícil venderle a un gerente “podemos ahorrar 150 MB de memoria”, pero sí se puede vender “si ahorramos 150 MB de memoria, para el 10% de los usuarios el rendimiento de la app pasará de ser terrible a apenas usable”
Antes el software realmente se hacía así. Por eso un sistema operativo con la mayor parte de lo que esperamos hoy podía correr bien incluso en máquinas como una Pentium 1. En cambio, hoy una página web se traba al hacer scroll incluso en smartphones que tienen literalmente unas mil veces más recursos en todos los ejes. El equipo de Word 95 se topaba constantemente con límites y compromisos de rendimiento, y el resultado era claro: funcionaba o no funcionaba
Si simplemente hubieran agregado más RAM, habrían seguido atrapados en un diseño inferior, y pronto habrían tenido que comprar aún más RAM. Lo sorprendente de este cambio es que no solo redujo el uso de recursos, sino que, gracias a la RAM libre, aumentó la caché de disco y el sistema se volvió más capaz y más rápido
[1] Por ejemplo, esto corre en una sola Pi y, como no permite actualizaciones, es mucho más rápido que la Wikipedia en operación: https://encyclopedia.marginalia.nu/article/Hacker_News
Por eso quizá las computadoras viejas se sentían bien, y los juegos antiguos también podían ser tan excelentes
Tal vez tenga que ver con la complejidad de los sistemas que manejamos. Cuando recursos como RAM, espacio físico, comida, materiales, tiempo o dinero son limitados, hay que planear cómo usarlos, y no queda otra que volverse más inteligente
Si tienes recursos prácticamente infinitos, puedes construir como quieras, pero disminuye la necesidad de preocuparte por el estado final. Simplemente empiezas y ves cómo queda cuando funcione
No soy un gamer de verdad, pero siempre me asombra la capacidad humana de meter tanta emoción, aventura y horas de diversión en cartuchos ROM de apenas unos KB/MB. La ROM de Ocarina Of Time tiene apenas el tamaño de unas 8 fotos recientes tomadas con mi iPhone
Una Raspberry Pi 2 puede procesar más de 4 mil millones de instrucciones Dhrystone por segundo, y una Pi 4 más de 10 mil millones por segundo
Claro que, según los estándares modernos, SABRE de mediados de los 70 era bastante básico para ser el sistema central de una aerolínea, pero en teoría sería posible correr simultáneamente en una sola Pi 2 los sistemas simplificados de más de 100 aerolíneas
Los programas modernos están muy lejos de estar optimizados. Salvo en casos con muchas operaciones matemáticas, son posibles mejoras de 1000x o 10000x
Creo que Microsoft sufre mucho este problema. Incluso una laptop de 3000 dólares de hace 5 años se vuelve inaceptablemente lenta si corres al mismo tiempo una llamada de Teams, varios Office y un navegador con 30 pestañas
Si los pruebas por separado, cuando solo corre uno están bien, pero la gente real no los usa así
Una posible solución serían límites artificiales: restringir el tiempo de ejecución en hardware claramente definido y subir ese límite solo después de una decisión explícita
Dicho eso, yo solo escribo software empresarial donde el aspecto de rendimiento se reduce a “no hagas estupideces con la base de datos, y no te preocupes por lo demás porque el cliente no paga por esa preocupación”, así que podría estar totalmente equivocado
Siempre me alegra ver actualizaciones de marginalia.nu. Es un usuario valioso en este sitio, y ojalá siga publicándolas
Gracias. Estoy trabajando en un proyecto hobby de motor de búsqueda, y por alguna razón seguía buscando solo variantes de “Magnolia”. Me cuesta recordar el nombre Marginalia. Ahora estoy tratando de entender Searx
Me pregunto si Marginalia soporta búsquedas con filtros de tiempo, como el último día o la última semana. Viendo las palabras clave especiales, parece que los parámetros de búsqueda solo aceptan criterios basados en año
year>2005 (beta) el documento aparentemente fue publicado después de 2005
year=2005 (beta) el documento aparentemente fue publicado en 2005
year<2005 (beta) el documento aparentemente fue publicado antes de 2005
Incluso el filtro por año es bastante aproximado, y determinar con precisión la fecha de la mayoría de las páginas web es muy difícil
Me pregunto si eso de que “cada vez que un SSD actualiza un solo byte en alguna parte del disco, tiene que borrar y reescribir una página completa” realmente aplica a los SSD.
En flash sin procesar no es así. Es posible si estás sobrescribiendo un valor “vacío” de todos unos, o si solo cambias 1 a 0. Las escrituras son varios órdenes de magnitud más lentas que las lecturas, pero también varios órdenes de magnitud más rápidas que los borrados, y solo los borrados cuentan para el presupuesto de desgaste.
Si el controlador del SSD no aprovecha esto, suena como meterse un autogol. Aunque si internamente en verdad tiene una estructura de log, puedo imaginar que quizá no pueda hacerlo.
Hace tiempo escribí drivers para varios chips flash populares, y todos los chips con los que trabajé entonces usaban solo E/S por páginas de tamaño fijo para lectura y escritura.
Como un SSD es un conjunto de chips, esperaría que cada chip dentro del SSD también solo soporte E/S por páginas de tamaño fijo.
Normalmente los controladores usan varias técnicas para evitar esos patrones de peor caso, como sobreaprovisionamiento, buffering y reordenamiento de escrituras, pero tienen límites.
La unidad más pequeña que se puede escribir en un SSD es una página, y la unidad más pequeña que se puede borrar es un bloque compuesto por varias páginas.
Por eso, aunque una operación de escritura afecte solo 1 byte dentro de una página, el SSD no puede borrar solo ese byte. Pero eso tampoco significa que necesariamente tenga que borrar todo el bloque.
El SSD puede realizar una operación del tipo “leer-modificar-escribir”. Lee en el búfer de caché del SSD la página completa que contiene el byte que cambiará, modifica solo ese byte en la caché de la página, borra un nuevo bloque vacío, escribe la página modificada desde la caché al nuevo bloque y actualiza la tabla de mapeo FTL para que apunte a la página actualizada en el nuevo bloque.
Por lo tanto, aunque solo cambie 1 byte, la página tiene que reescribirse. Pero se puede evitar borrar el bloque completo hasta que muchas páginas dentro de él hayan sido modificadas.
A medida que ocurren escrituras, las páginas se mueven dentro del dispositivo físico. La propia unidad mantiene un mapa de qué dirección se usa para qué, cuál es su estado de salud, etc. Es una especie de almacenamiento disperso.
También existen comandos como TRIM, mantenimiento periódico y recolección de basura.
En la práctica, cuando escribes en una unidad que no está llena, busca una página donde poner los datos, verifica si ya hay datos ahí, si hace falta hace leer/modificar/escribir, decide dónde escribir los datos y luego escribe. Por el wear leveling, es muy probable que no vuelva al lugar original.
Es cierto que el controlador realiza pasos mucho más complejos por rendimiento. Por eso una unidad nueva y vacía funciona mejor durante un tiempo, y una unidad vieja y llena, sin páginas de reserva, puede volverse realmente más lenta.
Como contexto: fui ingeniero principal de un acelerador flash con mapeo de memoria y coherencia de caché. Permitía mapear unidades de forma muy eficiente desde el espacio de usuario de Linux, pero al final por un tiempo terminamos cediendo al modelo de programación “fácil” en el que solo parecía otro disco duro más.
Me hizo pensar que mi jefe en Mojeek probablemente recorrió un camino muy parecido. Este texto coincide mucho con conversaciones pasadas.
Mojeek empezó en 2004, y su estructura fue creada en gran parte por un solo desarrollador, que construyó casi todo el sistema de recuperación de información y la infraestructura.
Las restricciones financieras y de hardware, las decisiones de ID de 32 bits frente a 64 bits, el sharding y la velocidad de actualización suenan muy familiares.
También me recuerda al antiguo “Google dance” de Google. En ese entonces los resultados de búsqueda se actualizaban una vez al mes, y ahora fluctúan todos los días. Todo es parte de la evolución, y es bueno ver que Marginalia ofrece otra perspectiva de la web más allá de las big tech.
Fue una buena lectura.
Mucha gente ve la optimización como una especie de magia negra profunda, pero la mayoría de las veces es incluso más fácil que corregir bugs comunes. Basta con tratar el uso excesivo de recursos igual que un bug.
Creo que la mayoría de los bugs fáciles de reproducir no requieren magia para arreglarse. Si puedes pinchar el bug, normalmente puedes clasificarlo, y hasta los defectos de diseño raros suelen quedar al descubierto bastante rápido una vez que se pueden reproducir.
El software cuyo rendimiento nadie ha revisado de forma crítica es como un software con cientos de bugs fácilmente reproducibles que nadie ha depurado. Puedes ir eliminándolos uno por uno durante bastante tiempo antes de topar con algo difícil.
Creo que esta actitud es más bien un vestigio de la época en que la gente ajustaba las direcciones de destino de los saltos para que llegaran justo cuando el cabezal del tambor entregaba a la CPU la instrucción que necesitaba. Cuando los recursos eran extremadamente limitados, todo se escribía a mano en ensamblador y una misma ubicación global de memoria tenía significados distintos según la fase del programa, ya había gente muy inteligente revisando críticamente el rendimiento, así que había que encontrar lo que ellos no habían encontrado. En el código moderno, eso es raro.
Si al enviar la solicitud X al servicio Y se reproduce el bug, puedes ir reduciendo el caso de prueba hasta encontrar al culpable.
La optimización suele ser un problema de arquitectura. A veces se está copiando algo cuando se podría reutilizar un búfer, pero ese tipo de casos se agota rápido, y el profiler te da la información necesaria.
Las grandes mejoras de rendimiento suelen venir de cambiar todo el flujo de datos y eliminar partes importantes, para que el código haga lo necesario en la menor cantidad de pasos posible.
Me pregunto por qué eligieron SQLite y no un almacén clave-valor. Si solo quieren leer por ID y no parecen necesitar otras columnas, una base de datos relacional parece innecesaria.
SQLite tiene la ventaja de ser un solo archivo. Así puedes copiarlo, compartirlo y hacer otras cosas interesantes.
Me gusta porque es otro ejemplo de cómo las restricciones generan innovación. La innovación suele encontrarse más a menudo en los límites que en la abundancia.