ТЛ;ДР: Пре четири године напустио сам Гугл са идејом за нови алат за надгледање сервера. Идеја је била да се обично изоловане функције комбинују у једну услугу и анализа дневника, прикупљање метрика, и контролне табле. Један од принципа је да услуга мора бити истинита брзо, пружајући девопс-у лако, интерактивно, пријатно искуство. Ово захтева обраду вишегигабајтних скупова података у делићима секунде, а да притом остане у оквиру буџета. Постојећи алати за управљање евиденцијама су често спори и незграпни, тако да смо се суочили са добрим изазовом: паметно дизајнирање алата како би корисницима пружили ново искуство.
Овај чланак описује како смо ми у Сцалир-у решили овај проблем применом метода старе школе, приступа грубе силе, елиминисањем непотребних слојева и избегавањем сложених структура података. Ове лекције можете применити на сопствене инжењерске проблеме.
Олд Сцхоол Повер
Анализа дневника обично почиње претрагом: пронађите све поруке које одговарају одређеном обрасцу. У Сцалир-у, ово су десетине или стотине гигабајта дневника са многих сервера. Савремени приступи, по правилу, подразумевају изградњу неке сложене структуре података оптимизоване за претрагу. Ово сам сигурно видео на Гуглу, где су прилично добри у оваквим стварима. Али одлучили смо се на много грубљи приступ: линеарно скенирање дневника. И успело је – обезбеђујемо интерфејс за претрагу који је за редове величине бржи од наших конкурената (погледајте анимацију на крају).
Кључни увид је био да су савремени процесори заиста веома брзи у једноставним, једноставним операцијама. Ово је лако пропустити у сложеним, вишеслојним системима који се ослањају на И/О брзину и мрежне операције, а такви системи су данас веома чести. Зато смо развили дизајн који минимизира слојеве и вишак отпада. Са више процесора и сервера паралелно, брзина претраге достиже 1 ТБ у секунди.
Кључни закључци из овог чланка:
- Бруте форце претрага је одржив приступ за решавање проблема великих размера у стварном свету.
- Груба сила је техника дизајна, а не решење без посла. Као и свака техника, она је боље прилагођена неким проблемима од других и може се лоше или добро применити.
- Груба сила је посебно добра за постизање стабилан перформансе.
- Ефикасна употреба грубе силе захтева оптимизацију кода и примену довољних ресурса у право време. Погодан је ако су ваши сервери под великим оптерећењем не-корисника и операције корисника остају приоритет.
- Перформансе зависе од дизајна целог система, а не само од алгоритма унутрашње петље.
(Овај чланак описује претрагу података у меморији. У већини случајева, када корисник изврши претрагу дневника, Сцалир сервери су га већ кеширали. Следећи чланак ће говорити о тражењу некешираних евиденција. Примењују се исти принципи: ефикасан код, груба сила са великим рачунским ресурсима).
Метода грубе силе
Традиционално, велики скуп података се претражује помоћу индекса кључних речи. Када се примени на евиденције сервера, ово значи тражење сваке јединствене речи у евиденцији. За сваку реч треба да направите списак свих укључења. Ово олакшава проналажење свих порука са овом речју, на пример „грешка“, „фирефок“ или „трансацтион_16851951“ – само погледајте у индексу.
Користио сам овај приступ у Гоогле-у и добро је функционисао. Али у Сцалир-у тражимо дневнике бајт по бајт.
Зашто? Са апстрактне алгоритамске тачке гледишта, индекси кључних речи су много ефикаснији од претраживања грубом силом. Међутим, ми не продајемо алгоритме, ми продајемо перформансе. А перформансе се не односе само на алгоритме, већ и на системски инжењеринг. Морамо узети у обзир све: обим података, врсту претраге, расположиви хардверски и софтверски контекст. Одлучили смо да је за наш конкретан проблем нешто попут 'греп' боље прикладније од индекса.
Индекси су одлични, али имају ограничења. Једну реч је лако пронаћи. Али тражење порука са више речи, као што су 'гооглебот' и '404', много је теже. Претраживање фразе као што је „неухваћени изузетак“ захтева гломазнији индекс који бележи не само све поруке са том речју, већ и специфичну локацију речи.
Права потешкоћа долази када не тражите речи. Рецимо да желите да видите колико саобраћаја долази од ботова. Прва помисао је да претражите дневнике за реч 'бот'. Овако ћете пронаћи неке ботове: Гооглебот, Бингбот и многе друге. Али овде 'бот' није реч, већ њен део. Ако тражимо 'бот' у индексу, нећемо пронаћи постове са речју 'Гооглебот'. Ако проверите сваку реч у индексу, а затим скенирате индекс у потрази за пронађеним кључним речима, претрага ће се знатно успорити. Као резултат тога, неки програми дневника не дозвољавају претрагу по делу речи или (у најбољем случају) дозвољавају посебну синтаксу са нижим перформансама. Желимо да избегнемо ово.
Други проблем је интерпункција. Да ли желите да пронађете све захтеве од 50.168.29.7? Шта је са евиденцијама за отклањање грешака које садрже [error]? Подскрипти обично прескачу интерпункцију.
Коначно, инжењери воле моћне алате, а понекад се проблем може решити само регуларним изразом. Индекс кључних речи није баш погодан за ово.
Поред тога, индекси комплекс. Сваку поруку треба додати на неколико листа кључних речи. Ове листе треба увек да се чувају у лако претраживом формату. Упити са фразама, фрагментима речи или регуларним изразима морају бити преведени у операције са више листа, а резултати скенирани и комбиновани да би се добио скуп резултата. У контексту велике услуге са више закупаца, ова сложеност ствара проблеме са перформансама који нису видљиви приликом анализе алгоритама.
Индекси кључних речи такође заузимају много простора, а складиштење је велики трошак у систему управљања евиденцијама.
С друге стране, свака претрага може потрошити много рачунарске снаге. Наши корисници цене брзу претрагу јединствених упита, али се такви упити постављају релативно ретко. За типичне упите за претрагу, на пример, за контролну таблу, користимо посебне технике (описаћемо их у следећем чланку). Остали захтеви су довољно ретки да ретко морате да обрађујете више од једног истовремено. Али то не значи да наши сервери нису заузети: они су заузети послом примања, анализе и компресије нових порука, процене упозорења, компримовања старих података и тако даље. Дакле, имамо прилично значајну понуду процесора који се могу користити за извршавање упита.
Груба сила функционише ако имате груби проблем (и много силе)
Груба сила најбоље функционише на једноставним проблемима са малим унутрашњим петљама. Често можете оптимизовати унутрашњу петљу за рад при веома великим брзинама. Ако је код сложен, много је теже оптимизовати га.
Наш код за претрагу је првобитно имао прилично велику унутрашњу петљу. Поруке чувамо на страницама на 4К; свака страница садржи неке поруке (у УТФ-8) и метаподатке за сваку поруку. Метаподаци су структура која кодира дужину вредности, интерни ИД поруке и друга поља. Циклус претраге је изгледао овако:
Ово је поједностављена верзија стварног кода. Али чак и овде, вишеструко постављање објеката, копије података и позиви функција су видљиви. ЈВМ је прилично добар у оптимизацији позива функција и алоцирању ефемерних објеката, тако да је овај код функционисао боље него што смо заслужили. Током тестирања, купци су га прилично успешно користили. Али на крају смо то подигли на следећи ниво.
(Можете се питати зашто чувамо поруке у овом формату са 4К страницама, текстом и метаподацима, уместо да директно радимо са евиденцијама. Постоји много разлога који се своде на чињеницу да интерно Сцалир мотор више личи на дистрибуирану базу података него на систем датотека. Претраживање текста се често комбинује са филтерима у ДБМС стилу на маргинама након рашчлањивања дневника. Можемо истовремено претраживати хиљаде дневника одједном, а једноставне текстуалне датотеке нису погодне за наше трансакцијско, реплицирано, дистрибуирано управљање подацима).
У почетку се чинило да такав код није баш погодан за бруте форце оптимизацију. „Прави рад“ у String.indexOf() није чак ни доминирао ЦПУ профилом. То јест, само оптимизација ове методе не би донела значајан ефекат.
Дешава се да метаподатке чувамо на почетку сваке странице, а текст свих порука у УТФ-8 је упакован на други крај. Користећи ово, поново смо написали петљу да бисмо претражили целу страницу одједном:
Ова верзија ради директно на приказу raw byte[] и претражује све поруке одједном на целој 4К страници.
Ово је много лакше оптимизовати за метод грубе силе. Интерна петља за претрагу се позива истовремено за целу 4К страницу, а не одвојено за сваки пост. Нема копирања података, нема алокације објеката. А сложеније операције са метаподацима се позивају само када је резултат позитиван, а не на свакој поруци. На овај начин смо елиминисали гомилу додатних трошкова, а остатак оптерећења је концентрисан у малој унутрашњој петљи за претрагу, која је веома погодна за даљу оптимизацију.
Наш стварни алгоритам претраге је заснован на . Сличан је Боиер-Мооре алгоритму, прескачући приближно дужину стринга за претрагу у сваком кораку. Главна разлика је у томе што проверава два бајта истовремено да би се лажна подударања свела на минимум.
Наша имплементација захтева креирање табеле за претрагу од 64К за сваку претрагу, али то није ништа у поређењу са гигабајтима података које претражујемо. Унутрашња петља обрађује неколико гигабајта у секунди на једном језгру. У пракси, стабилне перформансе су око 1,25 ГБ у секунди на сваком језгру и има простора за побољшање. Могуће је елиминисати неке од додатних трошкова изван унутрашње петље, а планирамо да експериментишемо са унутрашњом петљом у Ц уместо у Јави.
Користимо силу
Разговарали смо о томе да претраживање дневника може да се примени „грубо“, али колико „снаге“ имамо? Доста.
1 језгро: Када се правилно користи, једно језгро модерног процесора је само по себи прилично моћно.
8 језгара: Тренутно радимо на Амазон хи1.4кларге и и2.4кларге ССД серверима, сваки са 8 језгара (16 нити). Као што је горе поменуто, ова језгра су обично заузета операцијама у позадини. Када корисник изврши претрагу, позадинске операције се суспендују, ослобађајући свих 8 језгара за претрагу. Претрага се обично завршава у делићу секунде, након чега се наставља рад у позадини (програм за пригушивање обезбеђује да гомила упита за претрагу не омета важан рад у позадини).
16 језгара: ради поузданости организујемо сервере у мастер/славе групе. Сваки мастер има један ССД и један ЕБС сервер под својом командом. Ако се главни сервер сруши, ССД сервер одмах заузима његово место. Готово све време, мастер и славе раде добро, тако да се сваки блок података може претраживати на два различита сервера (ЕБС славе сервер има слаб процесор, па га не узимамо у обзир). Поделимо задатак између њих, тако да имамо на располагању укупно 16 језгара.
Много језгара: У блиској будућности ћемо дистрибуирати податке по серверима на начин да сви учествују у обради сваког нетривијалног захтева. Свако језгро ће радити. [Белешка: имплементирали смо план и повећали брзину претраге на 1 ТБ/с, погледајте белешку на крају чланка].
Једноставност осигурава поузданост
Још једна предност методе грубе силе је њен прилично конзистентан учинак. Типично, претрага није много осетљива на детаље проблема и скупа података (ваљда се зато и зове „грубо“).
Индекс кључних речи понекад даје невероватно брзе резултате, а други пут не. Рецимо да имате 50 ГБ евиденције у којима се термин „цустомер_5987235982“ појављује тачно три пута. Претрага овог термина броји три локације директно из индекса и завршиће се одмах. Али сложене претраге џокер знакова могу скенирати хиљаде кључних речи и потрајати дуго.
С друге стране, бруталне претраге раде мање-више истом брзином за било који упит. Тражење дугих речи је боље, али чак и тражење једног знака је прилично брзо.
Једноставност методе грубе силе значи да је њен учинак близу свог теоријског максимума. Постоји мање опција за неочекивана преоптерећења диска, сукобе око закључавања, јурење показивача и хиљаде других разлога за неуспех. Управо сам погледао захтеве корисника Сцалир-а прошле недеље на нашем најпрометнијем серверу. Било је 14 захтева. За тачно осам њих требало је више од једне секунде; 000% завршено у року од 99 милисекунди (ако нисте користили алате за анализу дневника, верујте ми: брзо је).
Стабилне, поуздане перформансе су важне за једноставно коришћење услуге. Ако периодично заостаје, корисници ће га сматрати непоузданим и нерадо га користе.
Претрага дневника у акцији
Ево кратке анимације која приказује Сцалир претрагу у акцији. Имамо демо налог на који увозимо сваки догађај у свако јавно Гитхуб спремиште. У овој демонстрацији, испитујем податке вредне недељу дана: отприлике 600 МБ необрађених евиденција.
Видео је снимљен уживо, без посебне припреме, на мом десктопу (око 5000 километара од сервера). Перформансе које ћете видети у великој мери су последица , као и брз и поуздан бацкенд. Кад год постоји пауза без индикатора 'учитавања', ја паузирам да бисте могли да прочитате шта ћу да притиснем.
У закључку
Када обрађујете велике количине података, важно је изабрати добар алгоритам, али „добар“ не значи „фенси“. Размислите о томе како ће ваш код функционисати у пракси. Теоријска анализа алгоритама изоставља неке факторе који могу бити од великог значаја у стварном свету. Једноставније алгоритме је лакше оптимизовати и стабилнији су у ивичним ситуацијама.
Такође размислите о контексту у којем ће се код извршити. У нашем случају, потребни су нам довољно моћни сервери за управљање позадинским задацима. Корисници релативно ретко покрећу претраге, тако да можемо да позајмимо читаву групу сервера на кратак период потребан за завршетак сваке претраге.
Користећи методу грубе силе, имплементирали смо брзу, поуздану и флексибилну претрагу у низу евиденција. Надамо се да су ове идеје корисне за ваше пројекте.
Уредити: Наслов и текст су промењени са „Претражи при 20 ГБ у секунди“ у „Претражи при 1 ТБ у секунди“ да би одразили повећање перформанси у последњих неколико година. Ово повећање брзине је првенствено последица промена у типу и броју ЕЦ2 сервера које данас постављамо да опслужујемо нашу повећану базу клијената. Ускоро долазе промене које ће пружити још једно драматично повећање оперативне ефикасности и једва чекамо да их поделимо.
Извор: ввв.хабр.цом