TL;DR: Преди четири години напуснах Google с идея за нов инструмент за наблюдение на сървъри. Идеята беше да се комбинират обикновено изолирани функции в една услуга и анализ на регистрационни файлове, събиране на показатели, и табла за управление. Един от принципите е услугата да е истинска бърз, предоставяйки на devops лесно, интерактивно и приятно изживяване. Това изисква обработка на набори от данни от няколко гигабайта за части от секундата, в рамките на бюджета. Съществуващите инструменти за регистриране често са бавни и тромави, така че сме изправени пред добро предизвикателство: проектиране на правилния инструмент, който да даде на потребителите ново изживяване.
Тази статия описва как ние от Scalyr решихме този проблем чрез прилагане на методи от старата школа, подход на груба сила, премахване на ненужни слоеве и избягване на сложни структури от данни. Можете да приложите тези уроци към собствените си инженерни проблеми.
Силата на старата школа
Анализът на журнала обикновено започва с търсене: намиране на всички съобщения, които отговарят на някакъв модел. В Scalyr това са десетки или стотици гигабайта логове от много сървъри. Съвременните подходи, като правило, включват изграждането на някаква сложна структура от данни, оптимизирана за търсене. Със сигурност съм виждал това в Google, където са доста добри в такива неща. Но ние се спряхме на много по-груб подход: линейно сканиране на регистрационните файлове. И проработи - ние предоставяме интерфейс с възможност за търсене с порядък по-бърз от конкурентите (вижте анимацията в края).
Ключовото прозрение беше, че съвременните процесори наистина са много бързи в прости, ясни операции. Това е лесно да се пропусне в сложни, многопластови системи, които зависят от I/O скоростта и мрежовите операции, а такива системи са много често срещани днес. По този начин ние разработихме дизайн, който минимизира броя на слоевете и ненужните отпадъци. С множество процесори и сървъри в паралел, скоростта на търсене достига 1 TB в секунда.
Основни изводи от тази статия:
- Грубото търсене е жизнеспособен подход за решаване на реални, мащабни проблеми.
- Грубата сила е техника на проектиране, а не освобождаване от работа. Като всяка техника, тя е по-добра за някои проблеми от други и може да бъде приложена лошо или добре.
- Грубата сила е особено добра за постигане стабилен производителност.
- Ефективното използване на груба сила изисква оптимизиране на кода и навременно използване на достатъчно ресурси. Подходящо е, ако вашите сървъри са под голямо натоварване, което не е потребител, а потребителските операции остават приоритет.
- Производителността зависи от дизайна на цялата система, а не само от алгоритъма на вътрешния цикъл.
(Тази статия описва търсенето на данни в паметта. В повечето случаи, когато потребител търси в регистрационни файлове, сървърите на Scalyr вече са ги кеширали. В следващата статия ще обсъдим търсенето в некеширани регистрационни файлове. Прилагат се същите принципи: ефективен код, метод на груба сила с големи изчислителни ресурси).
метод на груба сила
Традиционно търсенето в голям набор от данни се извършва по индекс на ключова дума. За сървърни регистрационни файлове това означава да търсите всяка уникална дума в регистрационния файл. За всяка дума трябва да направите списък с всички включвания. Това улеснява намирането на всички съобщения с тази дума, като „грешка“, „firefox“ или „transaction_16851951“ – просто погледнете в индекса.
Използвах този подход в Google и той работи добре. Но в Scalyr търсим в регистрационните файлове байт по байт.
Защо? От абстрактна алгоритмична гледна точка, индексите на ключови думи са много по-ефективни от търсенията с груба сила. Ние обаче не продаваме алгоритми, ние продаваме производителност. И производителността не е само алгоритми, но и системно инженерство. Трябва да вземем предвид всичко: количеството данни, вида на търсенето, наличния хардуер и софтуерния контекст. Решихме, че за нашия конкретен проблем опция като 'grep' е по-добра от индекс.
Индексите са страхотни, но имат ограничения. Една дума се намира лесно. Но търсенето на съобщения с няколко думи като „googlebot“ и „404“ е много по-трудно. Търсенето на фраза като „неуловено изключение“ изисква по-тромав индекс, който не само регистрира всички съобщения с тази дума, но и конкретното местоположение на думата.
Истинската трудност идва, когато не търсиш думи. Да приемем, че искате да видите колко трафик идва от ботове. Първата ми мисъл е да потърся в регистрационните файлове думата „бот“. По този начин ще намерите някои ботове: Googlebot, Bingbot и много други. Но тук „бот“ не е дума, а част от нея. Ако търсим „бот“ в индекса, няма да намерим публикации с думата „Googlebot“. Ако проверите всяка дума в индекса и след това сканирате индекса за намерени ключови думи, търсенето ще се забави много. В резултат на това някои програми за регистриране не позволяват частично търсене на думи или (в най-добрия случай) позволяват специален синтаксис с по-лоша производителност. Искаме да избегнем това.
Друг проблем е пунктуацията. Искате да намерите всички заявки от 50.168.29.7? Какво ще кажете за регистрационните файлове за отстраняване на грешки, съдържащи [error]? Индексите обикновено пропускат препинателни знаци.
И накрая, инженерите обичат мощни инструменти и понякога проблемът може да бъде разрешен само с регулярен израз. Индексът на ключовите думи не е много подходящ за това.
Освен това индекси комплекс. Всяка публикация трябва да бъде добавена към множество списъци с ключови думи. Тези списъци трябва да се съхраняват във формат с възможност за търсене по всяко време. Заявките с фрази, фрагменти от думи или регулярни изрази трябва да бъдат преведени в операции с множество списъци и резултатите да бъдат сканирани и комбинирани, за да се получи набор от резултати. В контекста на широкомащабна услуга за много потребители тази сложност създава проблеми с производителността, които не се виждат при анализиране на алгоритми.
Индексите на ключови думи също заемат много място и съхранението е основен разход в системата за управление на журнали.
От друга страна, за всяко търсене може да се изразходва много изчислителна мощност. Нашите потребители оценяват високоскоростното търсене на уникални заявки, но такива заявки са относително редки. За типични заявки за търсене, като табло за управление, използваме специални техники (ще ги опишем в следващата статия). Други заявки са достатъчно редки, така че рядко е необходимо да се обработват повече от една наведнъж. Но това не означава, че нашите сървъри не са заети: те са заети с работата по получаване, анализиране и компресиране на нови съобщения, оценка на предупреждения, компресиране на стари данни и т.н. По този начин имаме доста значителен запас от процесори, които могат да се използват за изпълнение на заявки.
Грубата сила работи, ако имате груб проблем (и много сила)
Грубата сила работи най-добре при прости задачи с малки вътрешни цикли. Често можете да оптимизирате вътрешния цикъл да работи при много високи скорости. Ако кодът е сложен, тогава е много по-трудно да се оптимизира.
Първоначално нашият код за търсене имаше доста голям вътрешен цикъл. Ние съхраняваме публикации на 4K страници; всяка страница съдържа някои съобщения (в UTF-8) и метаданни за всяко съобщение. Метаданните са структура, която кодира дължината на стойността, ID на вътрешното съобщение и други полета. Цикълът на търсене изглеждаше така:
Това е опростена версия на действителния код. Но дори тук можете да видите множество разположения на обекти, копия на данни и извиквания на функции. JVM е доста добър в оптимизирането на извикванията на функции и разпределянето на краткотрайни обекти, така че този код работи по-добре, отколкото заслужавахме. По време на тестването клиентите го използваха доста успешно. Но в крайна сметка преминахме на ново ниво.
(Може да попитате защо съхраняваме съобщения в този формат с 4K страници, текст и метаданни, вместо да работим директно с регистрационните файлове. Има много причини, които се свеждат до факта, че вътрешно машината Scalyr прилича повече на разпределена база данни, отколкото на файл система. Текстовото търсене често се комбинира с филтри в стил СУБД на полетата след анализ на регистрационните файлове. Можем да търсим в много хиляди регистрационни файлове едновременно и обикновените текстови файлове не са подходящи за нашето транзакционно, репликирано, разпределено управление на данни).
Първоначално изглеждаше, че такъв код не е много подходящ за груба оптимизация. „Истинска работа“ в String.indexOf() дори не доминираха в профила на процесора. Тоест оптимизацията на този метод сама по себе си не би донесла значителен ефект.
Така се случи, че съхраняваме метаданни в началото на всяка страница, а текстът на всички съобщения в UTF-8 е опакован в другия край. Възползвайки се от това, ние пренаписахме цикъла, за да търсим в цялата страница наведнъж:
Тази версия работи директно върху изгледа raw byte[] и търси всички съобщения наведнъж на цялата 4K страница.
Това е много по-лесно за оптимизиране за метода на груба сила. Вътрешният цикъл на търсене се извиква едновременно за цялата 4K страница, а не отделно за всяка публикация. Няма копиране на данни, няма селекция на обекти. И по-сложните операции с метаданни се извикват само с положителен резултат, а не за всяко съобщение. По този начин елиминирахме много излишни разходи, а останалата част от работното натоварване е концентрирана в малък вътрешен цикъл за търсене, който е много подходящ за по-нататъшна оптимизация.
Нашият действителен алгоритъм за търсене се основава на . Той е подобен на алгоритъма на Boyer-Moore, като пропуска около дължината на низа за търсене на всяка стъпка. Основната разлика е, че проверява два байта наведнъж, за да минимизира фалшивите съвпадения.
Нашата реализация изисква да бъде създадена справочна таблица от 64K за всяко търсене, но това е нищо в сравнение с гигабайтите данни, които търсим. Вътрешният цикъл обработва няколко гигабайта в секунда на едно ядро. На практика стабилната производителност е около 1,25 GB в секунда за всяко ядро и има място за подобрение. Възможно е да елиминираме някои допълнителни разходи извън вътрешния цикъл и планираме да експериментираме с вътрешния цикъл в C вместо в Java.
Приложете сила
Обсъдихме, че търсенията в регистрационни файлове могат да бъдат приложени "грубо", но колко "сила" имаме? Не много.
1 ядро: Когато се използва правилно, едно ядро на модерен процесор е доста мощно само по себе си.
8 ядраО: В момента работим със SSD сървъри на Amazon hi1.4xlarge и i2.4xlarge, всеки с 8 ядра (16 нишки). Както бе споменато по-горе, тези ядра обикновено са заети с фонови операции. Когато потребителят извърши търсене, фоновите операции се прекратяват, освобождавайки всичките 8 ядра за търсене. Търсенето обикновено приключва за част от секундата, след което фоновата работа се възобновява (регулаторът гарантира, че вълната от търсения не пречи на важната фонова работа).
16 ядра: за надеждност организираме сървърите в главни/подчинени групи. Всеки мастер има един SSD сървър и един EBS. Ако основният сървър падне, тогава сървърът на SSD веднага заема неговото място. През повечето време главният и подчиненият работят добре, така че всеки блок от данни може да се търси на два различни сървъра (подчиненият EBS сървър има слаб процесор, така че не го вземаме предвид). Разделяме задачата между тях, така че имаме общо 16 налични ядра.
Много ядра: в близко бъдеще ще разпределим данните между сървърите по такъв начин, че всички да участват в обработката на всяка нетривиална заявка. Всяко ядро ще работи. [Забележка: изпълнихме плана и увеличихме скоростта на търсене до 1 TB / s, вижте бележката в края на статията].
Простотата гарантира надеждност
Друго предимство на метода на груба сила е, че производителността е доста стабилна. По правило търсенето не е твърде чувствително към детайлите на задачата и набора от данни (мисля, че затова се нарича "грубо").
Индексът на ключовите думи понякога дава невероятно бързи резултати, а друг път не. Да приемем, че имате 50 GB регистрационни файлове, където терминът „customer_5987235982“ се среща точно три пъти. Търсенето на този термин чете три местоположения директно от индекса и завършва незабавно. Но сложните търсения със заместващи знаци могат да обхождат хиляди ключови думи и да отнемат много време.
От друга страна, грубите търсения за всяка заявка се извършват с повече или по-малко същата скорост. Търсенето на дълги думи е по-добро, но дори търсенето на един знак е достатъчно бързо.
Простотата на метода на грубата сила означава, че неговата производителност е близка до теоретичния максимум. Има по-малко опции за неочаквано претоварване на диска, конфликти при заключване, преследване на показалец и хиляди други причини за неуспех. Току-що прегледах заявките, направени от потребители на Scalyr миналата седмица на нашия най-натоварен сървър. Имаше 14 000 заявки. Точно осем от тях отнеха повече от една секунда; 99% завършени в рамките на 111 милисекунди (ако не сте използвали инструменти за анализ на регистрационни файлове, повярвайте ми: бързо е).
Стабилната, надеждна работа е важна за използваемостта на услугата. Ако се забавя от време на време, потребителите ще го възприемат като ненадежден и нямат желание да го използват.
Търсене в лог в действие
Ето малка анимация, която показва търсенето на Scalyr в действие. Имаме демо акаунт, където импортираме всяко събитие във всяко публично репо в Github. В тази демонстрация разглеждам данни за една седмица: приблизително 600 MB необработени регистрационни файлове.
Видеото беше записано на живо, без специална подготовка, на моя десктоп (на около 5000 километра от сървъра). Изпълнението, което ще видите, дължи много , както и бърз и надежден бекенд. Всеки път, когато има пауза без индикатор за „зареждане“, правя пауза, за да можете да прочетете какво ще натисна.
В заключение
При обработката на големи количества данни е важно да изберете добър алгоритъм, но „добър“ не означава „изискан“. Помислете как вашият код ще работи на практика. От теоретичния анализ на алгоритмите излизат някои фактори, които могат да бъдат от голямо значение в реалния свят. По-простите алгоритми са по-лесни за оптимизиране и са по-стабилни в крайни ситуации.
Също така помислете за контекста, в който ще бъде изпълнен кодът. В нашия случай се нуждаем от достатъчно мощни сървъри, за да управляваме фонови задачи. Потребителите инициират търсене сравнително рядко, така че можем да заемем цяла група сървъри за краткия период, необходим за завършване на всяко търсене.
Използвайки метода на груба сила, внедрихме бързо, надеждно и гъвкаво търсене в набор от регистрационни файлове. Надяваме се, че тези идеи ще бъдат полезни за вашите проекти.
Редактиране: заглавието и текстът са променени от „Търсене с 20 GB в секунда“ на „Търсене с 1 TB в секунда“, за да отразят увеличението на производителността през последните няколко години. Това увеличение на скоростта се дължи главно на промяната в типа и броя на EC2 сървърите, които издигаме днес, за да обслужваме нарастващата ни клиентска база. Скоро предстоят промени, които ще осигурят още едно драстично увеличение на оперативната ефективност и очакваме с нетърпение възможността да говорим за това.
Източник: www.habr.com