TL;DR: Hace cuatro años dejé Google con una idea para una nueva herramienta de monitoreo de servidores. La idea era combinar funciones normalmente aisladas en un solo servicio. y análisis de registros, recopilación de métricas, y paneles de control. Uno de los principios es que el servicio debe ser verdaderamente rápido, brindando a los desarrolladores una experiencia fácil, interactiva y agradable. Esto requiere procesar conjuntos de datos de varios gigabytes en fracciones de segundo sin salirse del presupuesto. Las herramientas de administración de registros existentes suelen ser lentas y torpes, por lo que nos enfrentamos a un buen desafío: diseñar inteligentemente una herramienta para brindar a los usuarios una nueva experiencia.
Este artículo describe cómo en Scalyr resolvimos este problema aplicando métodos de la vieja escuela, un enfoque de fuerza bruta, eliminando capas innecesarias y evitando estructuras de datos complejas. Puede aplicar estas lecciones a sus propios problemas de ingeniería.
Poder de la vieja escuela
El análisis de registros generalmente comienza con una búsqueda: encuentre todos los mensajes que coincidan con un patrón determinado. En Scalyr, se trata de decenas o cientos de gigabytes de registros de muchos servidores. Los enfoques modernos, por regla general, implican la construcción de alguna estructura de datos compleja optimizada para la búsqueda. Ciertamente he visto esto en Google, donde son bastante buenos en este tipo de cosas. Pero nos decidimos por un enfoque mucho más tosco: escaneo lineal de registros. Y funcionó: proporcionamos una interfaz de búsqueda que es mucho más rápida que la de nuestros competidores (ver animación al final).
La idea clave fue que los procesadores modernos son realmente muy rápidos en operaciones simples y directas. Esto es fácil de pasar por alto en sistemas complejos de múltiples capas que dependen de la velocidad de E/S y las operaciones de red, y estos sistemas son muy comunes hoy en día. Por eso desarrollamos un diseño que minimiza las capas y el exceso de escombros. Con múltiples procesadores y servidores en paralelo, la velocidad de búsqueda alcanza 1 TB por segundo.
Conclusiones clave de este artículo:
- La búsqueda por fuerza bruta es un enfoque viable para resolver problemas a gran escala del mundo real.
- La fuerza bruta es una técnica de diseño, no una solución que no requiere trabajo. Como cualquier técnica, se adapta mejor a algunos problemas que a otros y puede implementarse bien o mal.
- La fuerza bruta es especialmente buena para lograr estable productividad.
- El uso eficaz de la fuerza bruta requiere optimizar el código y aplicar suficientes recursos en el momento adecuado. Es adecuado si sus servidores tienen una gran carga de no usuarios y las operaciones de los usuarios siguen siendo una prioridad.
- El rendimiento depende del diseño de todo el sistema, no sólo del algoritmo del bucle interno.
(Este artículo describe la búsqueda de datos en la memoria. En la mayoría de los casos, cuando un usuario realiza una búsqueda de registros, los servidores Scalyr ya los han almacenado en caché. El siguiente artículo analizará la búsqueda de registros no almacenados en caché. Se aplican los mismos principios: código eficiente, fuerza bruta con grandes recursos computacionales).
método de fuerza bruta
Tradicionalmente, se busca en un gran conjunto de datos mediante un índice de palabras clave. Cuando se aplica a los registros del servidor, esto significa buscar cada palabra única en el registro. Para cada palabra, debes hacer una lista de todas las inclusiones. Esto hace que sea fácil encontrar todos los mensajes con esta palabra, por ejemplo 'error', 'firefox' o "transaction_16851951" - simplemente mire en el índice.
Utilicé este enfoque en Google y funcionó bien. Pero en Scalyr buscamos los registros byte a byte.
¿Por qué? Desde un punto de vista algorítmico abstracto, los índices de palabras clave son mucho más eficientes que las búsquedas de fuerza bruta. Sin embargo, no vendemos algoritmos, vendemos rendimiento. Y el rendimiento no se trata sólo de algoritmos, sino también de ingeniería de sistemas. Hay que considerarlo todo: volumen de datos, tipo de búsqueda, contexto de hardware y software disponible. Decidimos que para nuestro problema particular, algo como 'grep' era más adecuado que un índice.
Los índices son geniales, pero tienen limitaciones. Una palabra es fácil de encontrar. Pero buscar mensajes con varias palabras, como "googlebot" y "404", es mucho más difícil. La búsqueda de una frase como "excepción no detectada" requiere un índice más engorroso que registre no sólo todos los mensajes con esa palabra, sino también la ubicación específica de la palabra.
La verdadera dificultad surge cuando no buscas palabras. Supongamos que desea ver cuánto tráfico proviene de los bots. La primera idea es buscar en los registros la palabra "bot". Así encontrarás algunos bots: Googlebot, Bingbot y muchos otros. Pero aquí 'bot' no es una palabra, sino una parte de ella. Si buscamos 'bot' en el índice, no encontraremos ninguna publicación con la palabra 'Googlebot'. Si verifica cada palabra en el índice y luego escanea el índice en busca de las palabras clave encontradas, la búsqueda se ralentizará considerablemente. Como resultado, algunos programas de registro no permiten búsquedas de palabras parciales o (en el mejor de los casos) permiten una sintaxis especial con menor rendimiento. Queremos evitar esto.
Otro problema es la puntuación. ¿Quieres encontrar todas las solicitudes de 50.168.29.7? ¿Qué pasa con los registros de depuración que contienen [error]? Los subíndices suelen omitir la puntuación.
Por último, a los ingenieros les encantan las herramientas potentes y, a veces, un problema sólo puede resolverse con una expresión regular. El índice de palabras clave no es muy adecuado para esto.
Además, los índices complejo. Cada mensaje debe agregarse a varias listas de palabras clave. Estas listas deben mantenerse en un formato de fácil búsqueda en todo momento. Las consultas con frases, fragmentos de palabras o expresiones regulares deben traducirse en operaciones de listas múltiples y los resultados escanearse y combinarse para producir un conjunto de resultados. En el contexto de un servicio multiinquilino a gran escala, esta complejidad crea problemas de rendimiento que no son visibles al analizar los algoritmos.
Los índices de palabras clave también ocupan mucho espacio y el almacenamiento es un costo importante en un sistema de gestión de registros.
Por otro lado, cada búsqueda puede consumir una gran cantidad de potencia informática. Nuestros usuarios aprecian las búsquedas de alta velocidad para consultas únicas, pero dichas consultas se realizan relativamente raramente. Para consultas de búsqueda típicas, por ejemplo, para un panel, utilizamos técnicas especiales (las describiremos en el próximo artículo). Otras solicitudes son tan poco frecuentes que rara vez es necesario procesar más de una a la vez. Pero esto no significa que nuestros servidores no estén ocupados: lo están con el trabajo de recibir, analizar y comprimir mensajes nuevos, evaluar alertas, comprimir datos antiguos, etc. Así, tenemos una oferta bastante importante de procesadores que se pueden utilizar para ejecutar consultas.
La fuerza bruta funciona si tienes un problema bruto (y mucha fuerza)
La fuerza bruta funciona mejor en problemas simples con pequeños bucles internos. A menudo se puede optimizar el bucle interno para que funcione a velocidades muy altas. Si el código es complejo, es mucho más difícil optimizarlo.
Nuestro código de búsqueda originalmente tenía un bucle interno bastante grande. Almacenamos mensajes en páginas a 4K; cada página contiene algunos mensajes (en UTF-8) y metadatos para cada mensaje. Los metadatos son una estructura que codifica la longitud del valor, el ID del mensaje interno y otros campos. El ciclo de búsqueda se veía así:
Esta es una versión simplificada del código real. Pero incluso aquí, son visibles múltiples ubicaciones de objetos, copias de datos y llamadas a funciones. La JVM es bastante buena para optimizar llamadas a funciones y asignar objetos efímeros, por lo que este código funcionó mejor de lo que merecíamos. Durante las pruebas, los clientes lo utilizaron con bastante éxito. Pero finalmente lo llevamos al siguiente nivel.
(Quizás se pregunte por qué almacenamos mensajes en este formato con páginas, texto y metadatos de 4K, en lugar de trabajar con registros directamente. Hay muchas razones, que se reducen al hecho de que internamente el motor Scalyr se parece más a una base de datos distribuida que a una sistema de archivos. La búsqueda de texto a menudo se combina con filtros de estilo DBMS en los márgenes después del análisis de registros. Podemos buscar simultáneamente muchos miles de registros a la vez, y los archivos de texto simples no son adecuados para nuestra gestión de datos transaccionales, replicados y distribuidos).
Inicialmente, parecía que dicho código no era muy adecuado para la optimización de fuerza bruta. "Trabajo real" en String.indexOf() Ni siquiera dominó el perfil de la CPU. Es decir, optimizar este método por sí solo no produciría un efecto significativo.
Sucede que almacenamos metadatos al principio de cada página y el texto de todos los mensajes en UTF-8 está empaquetado en el otro extremo. Aprovechando esto, reescribimos el bucle para buscar en toda la página a la vez:
Esta versión funciona directamente en la vista. raw byte[] y busca todos los mensajes a la vez en toda la página 4K.
Esto es mucho más fácil de optimizar para el método de fuerza bruta. El bucle de búsqueda interno se llama simultáneamente para toda la página 4K, en lugar de hacerlo por separado en cada publicación. No hay copia de datos ni asignación de objetos. Y las operaciones de metadatos más complejas se llaman solo cuando el resultado es positivo y no en cada mensaje. De esta manera, hemos eliminado una gran cantidad de gastos generales y el resto de la carga se concentra en un pequeño bucle de búsqueda interno, que es muy adecuado para una mayor optimización.
Nuestro algoritmo de búsqueda real se basa en . Es similar al algoritmo de Boyer-Moore, omitiendo aproximadamente la longitud de la cadena de búsqueda en cada paso. La principal diferencia es que verifica dos bytes a la vez para minimizar coincidencias falsas.
Nuestra implementación requiere crear una tabla de búsqueda de 64K para cada búsqueda, pero eso no es nada comparado con los gigabytes de datos que estamos buscando. El bucle interno procesa varios gigabytes por segundo en un único núcleo. En la práctica, el rendimiento estable ronda los 1,25 GB por segundo en cada núcleo y hay margen de mejora. Es posible eliminar parte de la sobrecarga fuera del bucle interno y planeamos experimentar con un bucle interno en C en lugar de Java.
usamos la fuerza
Hemos discutido que la búsqueda de registros se puede implementar "aproximadamente", pero ¿cuánto "poder" tenemos? Bastante.
1 horas: Cuando se usa correctamente, un solo núcleo de un procesador moderno es bastante poderoso por sí solo.
8 núcleos: Actualmente estamos ejecutando servidores SSD Amazon hi1.4xlarge e i2.4xlarge, cada uno con 8 núcleos (16 subprocesos). Como se mencionó anteriormente, estos núcleos suelen estar ocupados con operaciones en segundo plano. Cuando el usuario realiza una búsqueda, las operaciones en segundo plano se suspenden, liberando los 8 núcleos para la búsqueda. La búsqueda normalmente se completa en una fracción de segundo, después de lo cual se reanuda el trabajo en segundo plano (el programa de limitación garantiza que la avalancha de consultas de búsqueda no interfiera con el trabajo en segundo plano importante).
16 núcleos: para mayor confiabilidad, organizamos los servidores en grupos maestro/esclavo. Cada maestro tiene bajo su mando un SSD y un servidor EBS. Si el servidor principal falla, el servidor SSD ocupa inmediatamente su lugar. Casi todo el tiempo, el maestro y el esclavo funcionan bien, de modo que cada bloque de datos se puede buscar en dos servidores diferentes (el servidor esclavo de EBS tiene un procesador débil, por lo que no lo consideramos). Dividimos la tarea entre ellos, de forma que tengamos un total de 16 núcleos disponibles.
Muchos núcleos: En un futuro próximo, distribuiremos datos entre servidores de tal manera que todos participen en el procesamiento de cada solicitud no trivial. Cada núcleo funcionará. [Nota: Implementamos el plan y aumentamos la velocidad de búsqueda a 1 TB/s, ver nota al final del artículo.].
La simplicidad garantiza la fiabilidad
Otra ventaja del método de fuerza bruta es su rendimiento bastante consistente. Normalmente, la búsqueda no es muy sensible a los detalles del problema y al conjunto de datos (supongo que por eso se llama "gruesa").
El índice de palabras clave a veces produce resultados increíblemente rápidos y otras veces no. Supongamos que tiene 50 GB de registros en los que el término "cliente_5987235982" aparece exactamente tres veces. Una búsqueda de este término cuenta tres ubicaciones directamente desde el índice y se completará al instante. Pero las búsquedas complejas con comodines pueden analizar miles de palabras clave y llevar mucho tiempo.
Por otro lado, las búsquedas de fuerza bruta se realizan más o menos a la misma velocidad para cualquier consulta. La búsqueda de palabras largas es mejor, pero incluso la búsqueda de un solo carácter es bastante rápida.
La simplicidad del método de fuerza bruta significa que su rendimiento se acerca a su máximo teórico. Hay menos opciones para sobrecargas inesperadas de disco, contención de bloqueos, persecución de punteros y miles de otras razones de falla. Acabo de ver las solicitudes realizadas por los usuarios de Scalyr la semana pasada en nuestro servidor más ocupado. Hubo 14 solicitudes. Exactamente ocho de ellos tardaron más de un segundo; 000 % completado en 99 milisegundos (si no ha utilizado herramientas de análisis de registros, créame: es rápido).
Un rendimiento estable y confiable es importante para facilitar el uso del servicio. Si se retrasa periódicamente, los usuarios lo percibirán como poco fiable y se mostrarán reacios a utilizarlo.
Búsqueda de registros en acción
Aquí hay una breve animación que muestra la búsqueda de Scalyr en acción. Tenemos una cuenta de demostración donde importamos cada evento en cada repositorio público de Github. En esta demostración, examino los datos de una semana: aproximadamente 600 MB de registros sin procesar.
El vídeo fue grabado en vivo, sin preparación especial, en mi escritorio (a unos 5000 kilómetros del servidor). El rendimiento que verá se debe en gran medida a , así como un backend rápido y confiable. Siempre que hay una pausa sin un indicador de "carga", soy yo quien hace la pausa para que puedas leer lo que estoy a punto de presionar.
en conclusión
Al procesar grandes cantidades de datos, es importante elegir un buen algoritmo, pero "bueno" no significa "elegante". Piense en cómo funcionará su código en la práctica. El análisis teórico de los algoritmos deja de lado algunos factores que pueden ser de gran importancia en el mundo real. Los algoritmos más simples son más fáciles de optimizar y más estables en situaciones límite.
Piense también en el contexto en el que se ejecutará el código. En nuestro caso, necesitamos servidores lo suficientemente potentes para gestionar tareas en segundo plano. Los usuarios inician búsquedas con relativa poca frecuencia, por lo que podemos tomar prestado un grupo completo de servidores durante el breve período necesario para completar cada búsqueda.
Utilizando un método de fuerza bruta, implementamos una búsqueda rápida, confiable y flexible en un conjunto de registros. Esperamos que estas ideas sean útiles para tus proyectos.
Editar: El título y el texto han cambiado de "Buscar a 20 GB por segundo" a "Buscar a 1 TB por segundo" para reflejar los aumentos de rendimiento de los últimos años. Este aumento en la velocidad se debe principalmente a cambios en el tipo y la cantidad de servidores EC2 que estamos instalando hoy para atender a nuestra creciente base de clientes. Próximamente habrá cambios que brindarán otro impulso dramático en la eficiencia operativa y estamos ansiosos por compartirlos.
Fuente: habr.com