TL; DR: Hai catro anos deixei Google cunha idea para unha nova ferramenta de monitorización do servidor. A idea era combinar funcións normalmente illadas nun só servizo e análise de rexistros, recollida de métricas, e cadros de mando. Un dos principios é que o servizo debe ser de verdade rápido, proporcionando aos devops unha experiencia sinxela, interactiva e agradable. Isto require procesar conxuntos de datos de varios gigabytes en fraccións de segundo mantendo dentro do orzamento. As ferramentas de xestión de rexistros existentes adoitan ser lentas e torpes, polo que nos enfrontamos a un bo reto: deseñar unha ferramenta intelixente para ofrecer aos usuarios unha nova experiencia.
Este artigo describe como en Scalyr resolvemos este problema aplicando métodos da vella escola, un enfoque de forza bruta, eliminando capas innecesarias e evitando estruturas de datos complexas. Podes aplicar estas leccións aos teus propios problemas de enxeñería.
Poder da vella escola
A análise do rexistro normalmente comeza cunha busca: busca todas as mensaxes que coincidan cun determinado patrón. En Scalyr, son decenas ou centos de gigabytes de rexistros de moitos servidores. Os enfoques modernos, por regra xeral, implican a construción dalgunha estrutura de datos complexa optimizada para a busca. Sen dúbida vin isto en Google, onde son moi bos neste tipo de cousas. Pero optamos por un enfoque moito máis crudo: a exploración lineal de rexistros. E funcionou: ofrecemos unha interface de busca que é ordes de magnitude máis rápida que os nosos competidores (ver animación ao final).
A idea clave foi que os procesadores modernos son realmente moi rápidos en operacións sinxelas e sinxelas. Isto é fácil de perder en sistemas complexos de varias capas que dependen da velocidade de E/S e das operacións de rede, e estes sistemas son moi comúns hoxe en día. Así que desenvolvemos un deseño que minimiza as capas e o exceso de restos. Con varios procesadores e servidores en paralelo, a velocidade de busca alcanza 1 TB por segundo.
Principais conclusións deste artigo:
- A busca por forza bruta é un enfoque viable para resolver problemas do mundo real a gran escala.
- A forza bruta é unha técnica de deseño, non unha solución sen traballo. Como calquera técnica, é máis axeitada a algúns problemas que a outros, e pódese implementar mal ou ben.
- A forza bruta é especialmente boa para lograr estable produtividade.
- O uso eficaz da forza bruta require optimizar o código e aplicar recursos suficientes no momento adecuado. É axeitado se os seus servidores están baixo unha gran carga de non usuarios e as operacións dos usuarios seguen sendo prioritarias.
- O rendemento depende do deseño de todo o sistema, non só do algoritmo de bucle interno.
(Este artigo descríbese a busca de datos na memoria. Na maioría dos casos, cando un usuario realiza unha busca de rexistros, os servidores de Scalyr xa a almacenaron na caché. O seguinte artigo tratará sobre a busca de rexistros sen caché. Aplícanse os mesmos principios: código eficiente, forza bruta). con grandes recursos computacionais).
Método da forza bruta
Tradicionalmente, búscase un gran conxunto de datos mediante un índice de palabras clave. Cando se aplica aos rexistros do servidor, isto significa buscar cada palabra única no rexistro. Para cada palabra, cómpre facer unha lista de todas as inclusións. Isto fai que sexa doado atopar todas as mensaxes con esta palabra, por exemplo, "erro", "firefox" ou "transaction_16851951"; basta con mirar no índice.
Usei este enfoque en Google e funcionou ben. Pero en Scalyr buscamos os rexistros byte por byte.
Por que? Desde un punto de vista algorítmico abstracto, os índices de palabras clave son moito máis eficientes que as buscas de forza bruta. Non obstante, non vendemos algoritmos, vendemos rendemento. E o rendemento non só se trata de algoritmos, senón tamén de enxeñería de sistemas. Debemos considerar todo: volume de datos, tipo de busca, hardware dispoñible e contexto de software. Decidimos que para o noso problema particular, algo como "grep" era máis adecuado que un índice.
Os índices son xeniais, pero teñen limitacións. Unha palabra é fácil de atopar. Pero buscar mensaxes con varias palabras, como "googlebot" e "404", é moito máis difícil. A busca dunha frase como "excepción non capturada" require un índice máis engorroso que rexistre non só todas as mensaxes con esa palabra, senón tamén a localización específica da palabra.
A verdadeira dificultade vén cando non buscas palabras. Digamos que queres ver canto tráfico procede dos bots. O primeiro pensamento é buscar nos rexistros a palabra "bot". Así atoparás algúns bots: Googlebot, Bingbot e moitos outros. Pero aquí "bot" non é unha palabra, senón unha parte dela. Se buscamos "bot" no índice, non atoparemos ningunha publicación coa palabra "Googlebot". Se comproba todas as palabras do índice e despois escanea o índice para as palabras clave atopadas, a busca ralentizarase moito. Como resultado, algúns programas de rexistro non permiten buscas de palabras parciales ou (no mellor dos casos) permiten unha sintaxe especial con menor rendemento. Queremos evitar isto.
Outro problema é a puntuación. Queres atopar todas as solicitudes de 50.168.29.7? Que pasa cos rexistros de depuración que conteñen [error]? Os subíndices normalmente omiten a puntuación.
Finalmente, os enxeñeiros adoran ferramentas poderosas e, ás veces, un problema só se pode resolver cunha expresión regular. O índice de palabras clave non é moi axeitado para iso.
Ademais, os índices complexo. Cada mensaxe debe engadirse a varias listas de palabras clave. Estas listas deben manterse nun formato facilmente buscable en todo momento. As consultas con frases, fragmentos de palabras ou expresións regulares deben traducirse en operacións de listas múltiples e os resultados escaneados e combinados para producir un conxunto de resultados. No contexto dun servizo multi-inquilino a gran escala, esta complexidade crea problemas de rendemento que non son visibles cando se analizan os algoritmos.
Os índices de palabras clave tamén ocupan moito espazo e o almacenamento é un custo importante nun sistema de xestión de rexistros.
Por outra banda, cada busca pode consumir moita potencia informática. Os nosos usuarios aprecian as buscas de alta velocidade para consultas únicas, pero estas consultas fanse relativamente raramente. Para consultas de busca típicas, por exemplo, para un panel, utilizamos técnicas especiais (describirémolas no seguinte artigo). Outras solicitudes son o suficientemente pouco frecuentes que raramente tes que procesar máis dunha á vez. Pero isto non significa que os nosos servidores non estean ocupados: están ocupados co traballo de recibir, analizar e comprimir novas mensaxes, avaliar alertas, comprimir datos antigos, etc. Así, temos unha oferta bastante importante de procesadores que se poden utilizar para executar consultas.
A forza bruta funciona se tes un problema bruto (e moita forza)
A forza bruta funciona mellor en problemas sinxelos con pequenos bucles internos. Moitas veces pode optimizar o bucle interno para que funcione a velocidades moi altas. Se o código é complexo, é moito máis difícil optimizalo.
O noso código de busca tiña orixinalmente un bucle interno bastante grande. Almacenamos mensaxes en páxinas en 4K; cada páxina contén algunhas mensaxes (en UTF-8) e metadatos para cada mensaxe. Os metadatos son unha estrutura que codifica a lonxitude do valor, o ID interno da mensaxe e outros campos. O ciclo de busca quedou así:
Esta é unha versión simplificada do código real. Pero mesmo aquí son visibles varias colocacións de obxectos, copias de datos e chamadas de funcións. A JVM é bastante boa para optimizar as chamadas de funcións e para asignar obxectos efémeros, polo que este código funcionou mellor do que nos merecíamos. Durante as probas, os clientes usárono con bastante éxito. Pero finalmente levámolo ao seguinte nivel.
(Pode preguntarse por que almacenamos mensaxes neste formato con páxinas de 4K, texto e metadatos, en lugar de traballar con rexistros directamente. Hai moitas razóns, que se reducen a que internamente o motor Scalyr se parece máis a unha base de datos distribuída que a un sistema de ficheiros. A busca de texto adoita combinarse con filtros de estilo DBMS nas marxes despois da análise de rexistros. Podemos buscar simultaneamente moitos miles de rexistros á vez e os ficheiros de texto sinxelos non son axeitados para a nosa xestión de datos transaccionais, replicados e distribuídos).
Inicialmente, parecía que ese código non era moi axeitado para a optimización da forza bruta. "Traballo real" en String.indexOf() nin sequera dominaba o perfil da CPU. É dicir, optimizar este método só non traería un efecto significativo.
Acontece que almacenamos metadatos ao comezo de cada páxina e o texto de todas as mensaxes en UTF-8 está empaquetado no outro extremo. Aproveitando isto, reescribimos o bucle para buscar en toda a páxina á vez:
Esta versión funciona directamente na vista raw byte[] e busca todas as mensaxes á vez en toda a páxina 4K.
Isto é moito máis fácil de optimizar para o método de forza bruta. O bucle de busca interno chámase simultáneamente para toda a páxina 4K, en lugar de por separado en cada publicación. Non hai copia de datos, nin asignación de obxectos. E as operacións de metadatos máis complexas só se chaman cando o resultado é positivo, e non en todas as mensaxes. Deste xeito, eliminamos unha tonelada de sobrecarga e o resto da carga concéntrase nun pequeno bucle de busca interno, que é moi axeitado para unha optimización adicional.
O noso algoritmo de busca real baséase . É semellante ao algoritmo de Boyer-Moore, saltando aproximadamente a lonxitude da cadea de busca en cada paso. A principal diferenza é que verifica dous bytes á vez para minimizar as coincidencias falsas.
A nosa implementación require crear unha táboa de busca de 64 K para cada busca, pero iso non é nada en comparación cos gigabytes de datos que estamos a buscar. O bucle interno procesa varios gigabytes por segundo nun só núcleo. Na práctica, o rendemento estable é duns 1,25 GB por segundo en cada núcleo e hai marxe para mellorar. É posible eliminar parte da sobrecarga fóra do bucle interno, e pensamos experimentar cun bucle interno en C en lugar de Java.
Usamos a forza
Xa comentamos que a busca de rexistros pódese implementar "aproximadamente", pero canto "poder" temos? Bastante.
1 núcleo: Cando se usa correctamente, un só núcleo dun procesador moderno é bastante poderoso por si mesmo.
8 núcleos: Actualmente estamos funcionando en servidores SSD hi1.4xlarge e i2.4xlarge de Amazon, cada un con 8 núcleos (16 fíos). Como se mencionou anteriormente, estes núcleos adoitan estar ocupados con operacións en segundo plano. Cando o usuario realiza unha busca, as operacións en segundo plano quedan suspendidas, liberando os 8 núcleos para a busca. A busca adoita completarse nunha fracción de segundo, despois de que se retoma o traballo en segundo plano (o programa de limitación garante que o aluvión de consultas de busca non interfira co traballo en segundo plano importante).
16 núcleos: para fiabilidade, organizamos os servidores en grupos mestre/escravo. Cada mestre ten un SSD e un servidor EBS baixo o seu mando. Se o servidor principal falla, o servidor SSD ocupa inmediatamente o seu lugar. Case todo o tempo, mestre e escravo funcionan ben, de xeito que cada bloque de datos pódese buscar en dous servidores diferentes (o servidor escravo EBS ten un procesador débil, polo que non o consideramos). Repartimos a tarefa entre eles, de xeito que dispoñemos dun total de 16 núcleos.
Moitos núcleos: Nun futuro próximo, distribuiremos os datos entre os servidores de forma que todos participen no procesamento de todas as solicitudes non triviales. Cada núcleo funcionará. [Nota: implementamos o plan e aumentamos a velocidade de busca a 1 TB/s, vexa a nota ao final do artigo].
A simplicidade garante a fiabilidade
Outra vantaxe do método de forza bruta é o seu rendemento bastante consistente. Normalmente, a busca non é moi sensible aos detalles do problema e do conxunto de datos (supoño que por iso se lle chama "grosero").
O índice de palabras clave ás veces produce resultados incriblemente rápidos, e outras non. Digamos que tes 50 GB de rexistros nos que o termo "customer_5987235982" aparece exactamente tres veces. A busca deste termo conta tres localizacións directamente desde o índice e completarase ao instante. Pero as buscas complexas de comodíns poden escanear miles de palabras clave e levar moito tempo.
Por outra banda, as buscas de forza bruta fan máis ou menos a mesma velocidade para calquera consulta. Buscar palabras longas é mellor, pero mesmo buscar un só personaxe é bastante rápido.
A sinxeleza do método da forza bruta significa que o seu rendemento está preto do seu máximo teórico. Hai menos opcións para sobrecargas inesperadas de disco, contención de bloqueos, persecución de punteiros e miles de outras razóns para o fallo. Acabo de mirar as solicitudes realizadas polos usuarios de Scalyr a semana pasada no noso servidor máis ocupado. Houbo 14 solicitudes. Exactamente oito deles tardaron máis dun segundo; Completouse o 000 % en 99 milisegundos (se non utilizaches ferramentas de análise de rexistros, confía en min: é rápido).
O rendemento estable e fiable é importante para facilitar o uso do servizo. Se se atrasa periódicamente, os usuarios percibirán que non é fiable e serán reticentes a usalo.
Busca de rexistro en acción
Aquí tes unha curta animación que mostra a busca de Scalyr en acción. Temos unha conta de demostración na que importamos todos os eventos en todos os repositorios públicos de Github. Nesta demostración, examino os datos dunha semana: aproximadamente 600 MB de rexistros en bruto.
O vídeo gravouse en directo, sen preparación especial, no meu escritorio (a uns 5000 quilómetros do servidor). O rendemento que verás débese en gran parte , así como un backend rápido e fiable. Sempre que hai unha pausa sen un indicador de "carga", son eu a pausa para que poidas ler o que estou a piques de presionar.
En conclusión
Cando se procesan grandes cantidades de datos, é importante escoller un bo algoritmo, pero "bo" non significa "fantasía". Pense en como funcionará o seu código na práctica. A análise teórica dos algoritmos deixa fóra algúns factores que poden ser de gran importancia no mundo real. Os algoritmos máis sinxelos son máis fáciles de optimizar e máis estables en situacións de borde.
Pense tamén no contexto no que se executará o código. No noso caso, necesitamos servidores suficientemente potentes para xestionar tarefas en segundo plano. Os usuarios inician buscas con relativa pouca frecuencia, polo que podemos pedir prestado un grupo enteiro de servidores durante o curto período necesario para completar cada busca.
Usando un método de forza bruta, implementamos unha busca rápida, fiable e flexible nun conxunto de rexistros. Agardamos que estas ideas sexan útiles para os teus proxectos.
Editar: O título e o texto cambiaron de "Buscar a 20 GB por segundo" a "Buscar a 1 TB por segundo" para reflectir os aumentos de rendemento nos últimos anos. Este aumento da velocidade débese principalmente aos cambios no tipo e número de servidores EC2 que estamos a instalar hoxe para atender a nosa crecente base de clientes. Hai cambios en breve que proporcionarán outro impulso dramático na eficiencia operativa, e non podemos esperar para compartilos.
Fonte: www.habr.com