TL;DR: Чатыры гады таму я пакінуў Google з ідэяй новага інструмента для маніторынгу сервераў. Ідэя складалася ў тым, каб аб'яднаць у адну службу звычайна ізаляваныя функцыі і аналізу логаў, збору метрык, і панэлі маніторынгу. Адзін з прынцыпаў - сэрвіс павінен быць сапраўды хуткім, забяспечваючы дэвапсам лёгкую, інтэрактыўную, прыемную працу. Гэта патрабуе апрацоўкі набораў дадзеных па некалькі гігабайт за долі секунды, не выходзячы за межы бюджэту. Існуючыя прылады для працы з логамі часта павольныя і нязграбныя, таму мы сутыкнуліся з добрай задачай: пісьменна распрацаваць прыладу, каб даць карыстачам новыя адчуванні ад працы.
У гэтым артыкуле апісваецца, як мы ў Scalyr вырашылі гэтую праблему, ужыўшы метады старой школы, падыход грубіянскай сілы, ухіліўшы лішнія пласты і пазбягаючы складаных структур дадзеных. Гэтыя ўрокі вы можаце прымяніць да ўласных інжынерных задач.
Сіла старой школы
Аналіз логаў звычайна пачынаецца з пошуку: знайсці ўсе паведамленні, якія адпавядаюць некатораму шаблону. У Scalyr гэта дзясяткі ці сотні гігабайт логаў са шматлікіх сервераў. Сучасныя падыходы, як правіла, мяркуюць пабудову нейкай складанай структуры дадзеных, аптымізаванай для пошуку. Я, вядома, бачыў такое ў Google, дзе яны даволі добрыя ў такіх рэчах. Але мы спыніліся на значна грубейшым падыходзе: лінейнае сканаванне логаў. І гэта спрацавала – мы забяспечваем інтэрфейс з пошукам на парадак хутчэй, чым у канкурэнтаў (гл. анімацыю ў канцы).
Ключавым азарэннем стала тое, што сучасныя працэсары сапраўды вельмі хуткія ў простых, прамалінейных аперацыях. Гэта лёгка ўпусціць у складаных, шматслаістых сістэмах, якія залежаць ад хуткасці I/O і сеткавых аперацый, а такія сістэмы сёння вельмі распаўсюджаныя. Такім чынам, мы распрацавалі дызайн, які мінімізуе колькасць пластоў і лішняга смецця. З некалькімі працэсарамі і серверамі раўналежна хуткасць пошуку дасягае 1 ТБ у секунду.
Ключавыя высновы з гэтага артыкула:
- Грубіянскі пошук - цалкам жыццяздольны падыход для рашэння рэальных, маштабных праблем.
- Грубая сіла - гэта тэхніка праектавання, а не вызваленне ад працы. Як і любая тэхніка, яна лепш падыходзіць для адных праблем, чым для іншых, і яе можна рэалізаваць дрэнна ці добра.
- Грубая сіла асабліва добрая для дасягнення стабільнай прадукцыйнасці.
- Эфектыўнае выкарыстанне грубай сілы патрабуе аптымізацыі кода і своечасовага прымянення дастатковай колькасці рэсурсаў. Яна падыходзіць, калі вашы серверы пад вялікай нагрузкай, не звязанай з карыстальнікамі, а карыстацкія аперацыі застаюцца ў прыярытэце.
- Прадукцыйнасць залежыць ад дызайну ўсёй сістэмы, а не толькі ад алгарытму ўнутранага цыклу.
(У гэтым артыкуле апісваецца пошук дадзеных у памяці. У большасці выпадкаў, калі карыстач выконвае пошук па логах, серверы Scalyr ужо кэшавалі іх. У наступным артыкуле абмяркуем пошук па некэшаваных логах. Ужываюцца тыя ж прынцыпы: эфектыўны код, метад грубіянскай сілы з вялікімі вылічальнымі рэсурсамі).
Метад грубай сілы
Традыцыйна, пошук у вялікім наборы дадзеных праводзіцца па індэксе ключавых слоў. У дачыненні да серверных логаў гэта азначае пошук кожнага ўнікальнага слова ў часопісе. Для кожнага слова трэба скласці спіс усіх уключэнняў. Гэта дазваляе лёгка знайсці ўсе паведамленні з гэтым словам, напрыклад 'error', 'firefox' ці "transaction_16851951" - проста глядзім у азначніку.
Я выкарыстоўваў такі падыход у Google, і ён працаваў добра. Але ў Scalyr мы шукаем у логах байт за байтам.
Чаму? З абстрактнай алгарытмічнай пункту гледжання індэксы ключавых слоў значна больш эфектыўна, чым грубы пошук. Аднак мы не прадаем алгарытмы, мы прадаем прадукцыйнасць. І прадукцыйнасць - гэта не толькі алгарытмы, але і сістэмная інжынерыя. Мы павінны ўлічваць усё: аб'ём даных, тып пошуку, даступнае абсталяванне і праграмны кантэкст. Мы вырашылі, што для нашай канкрэтнай праблемы варыянт накшталт 'grep' падыходзіць лепш, чым азначнік.
Індэксы - гэта выдатна, але ў іх ёсць абмежаванні. Адно слова знайсці лёгка. А вось пошук паведамленняў з некалькімі словамі, такімі як 'googlebot' і '404' - ужо нашмат складаней. Пошук фразы накшталт 'uncaught exception' патрабуе больш грувасткага азначніка, які рэгіструе не толькі ўсе паведамленні з гэтым словам, але і пэўнае месцазнаходжанне слова.
Сапраўдная цяжкасць узнікае, калі вы шукаеце не словы. Выкажам здагадку, вы хочаце паглядзець, колькі трафіку прыходзіць ад ботаў. Першая думка - пошук у логах па слове 'bot'. Дык вы знойдзеце некаторых ботаў: Googlebot, Bingbot і многіх іншых. Але тут 'bot' - гэта не слова, а яго частка. Калі шукаць 'bot' у азначніку, мы не знойдзем паведамленняў са словам 'Googlebot'. Калі правяраць кожнае слова ў азначніку і затым сканаваць азначнік па знойдзеных ключавіках, пошук моцна замарудзіцца. У выніку некаторыя праграмы для працы з логамі не дазваляюць пошук па частках слова ці (у лепшым выпадку) дазваляюць выкарыстоўваць адмысловы сінтаксіс з ніжэйшай прадукцыйнасцю. Мы жадаем гэтага пазбегнуць.
Яшчэ адна праблема - пунктуацыя. Хочаце знайсці ўсе запыты ад 50.168.29.7? Што наконт адладкі логаў, якія змяшчаюць [error]? Індэксы звычайна прапускаюць пунктуацыю.
Нарэшце, інжынеры кахаюць магутныя прылады, а часам праблему можна вырашыць толькі рэгулярным выразам. Індэкс ключавых слоў не вельмі падыходзіць для гэтага.
Акрамя таго, індэксы складаныя. Кожнае паведамленне трэба дадаць у некалькі спісаў ключавых слоў. Гэтыя спісы трэба пастаянна трымаць у зручным для пошуку фармаце. Запыты з фразамі, фрагментамі слоў ці рэгулярнымі выразамі трэба перакладаць у аперацыі з некалькімі спісамі, а вынікі сканаваць і аб'ядноўваць для атрымання выніковага набору. У кантэксце буйнамаштабнай шматкарыстальніцкай службы такая складанасць стварае праблемы прадукцыйнасці, якія не бачныя пры аналізе алгарытмаў.
Індэксы ключавых слоў таксама займаюць шмат месца, а сховішча - асноўны артыкул выдаткаў у сістэме кіравання логамі.
З іншага боку, на кожны пошук можна патраціць шмат вылічальнай магутнасці. Нашы карыстачы шануюць высакахуткасны пошук па ўнікальных запытах, але такія запыты робяцца адносна рэдка. Для тыповых пошукавых запытаў, напрыклад, для панэлі маніторынгу, мы ўжываем спецыяльныя прыёмы (апішам іх у наступным артыкуле). Іншыя запыты дастаткова рэдкія, так што рэдка даводзіцца апрацоўваць больш за адзін за раз. Але гэта не значыць, што нашы серверы не занятыя: яны загружаныя працай па прыёме, аналізу і сціску новых паведамленняў, адзнацы абвестак, сціску старых дадзеных і гэтак далей. Такім чынам, у нас дастаткова істотны запас працэсараў, якія можна задзейнічаць для выканання запытаў.
Грубая сіла працуе, калі ў вас ёсць грубая праблема (і шмат сілы)
Грубая сіла лепш за ўсё працуе на простых задачах з маленькімі ўнутранымі цыкламі. Часта вы можаце аптымізаваць унутраны цыкл для працы на вельмі высокіх хуткасцях. Калі код складаны, то нашмат складаней яго аптымізаваць.
Першапачаткова ў нашым кодзе для пошуку быў даволі вялікі ўнутраны цыкл. Мы захоўваем паведамленні на старонках па 4K; кожная старонка змяшчае некаторыя паведамленні (у UTF-8) і метададзеныя для кожнага паведамлення. Метададзеныя - гэта структура, у якой закадаваны даўжыня значэння, унутраны ID паведамлення і іншыя палі. Цыкл пошуку выглядаў так:
Гэта спрошчаны варыянт у параўнанні з фактычным кодам. Але нават тут бачна некалькі месцаванняў аб'екта, копій дадзеных і выклікаў функцый. JVM даволі добра аптымізуе выклікі функцый і вылучае эфемерныя аб'екты, таму гэты код працаваў лепш, чым мы таго заслугоўвалі. Падчас тэсціравання кліенты даволі паспяхова ім карысталіся. Але ў рэшце рэшт мы перайшлі на новы ўзровень.
(Вы можаце спытаць, чаму мы захоўваем паведамленні ў такім фармаце са старонкамі па 4K, тэкстам і метададзенымі, а не працуем з логамі напрамую. Ёсць шмат прычын, якія зводзяцца да таго, што ўнутрана рухавічок Scalyr больш падобны на размеркаваную базу дадзеных, чым на файлавую сістэму.Тэкставы пошук часта спалучаецца з фільтрамі ў стылі СКБД на палях пасля парсінгу логаў.Мы можам адначасова шукаць па шматлікіх тысячах логаў адначасова, і простыя тэкставыя файлы не падыходзяць для нашага транзакцыйнага, рэплікаванага, размеркаванага кіравання дадзенымі).
Першапачаткова падавалася, што такі код не вельмі падыходзіць для аптымізацыі пад метад грубай сілы. «Сапраўдная праца» у String.indexOf() нават не дамінавала ў профілі CPU. Гэта значыць, аптымізацыя толькі гэтага метаду не прынесла б істотнага эфекту.
Так атрымалася, што мы захоўваем метададзеныя ў пачатку кожнай старонкі, а тэкст усіх паведамленняў у UTF-8 запакаваная ў іншым канцы. Скарыстаўшыся гэтым, мы перапісалі цыкл для пошуку адразу па ўсёй старонцы:
Такая версія працуе непасрэдна на паданні raw byte[] і выконвае пошук усіх паведамленняў адразу на ўсёй старонцы 4K.
Гэта значна лягчэй аптымізаваць для метада грубіянскай сілы. Унутраны пошукавы цыкл выклікаецца адначасова для ўсёй старонкі 4K, а не асобна на кожным паведамленні. Няма ні капіявання дадзеных, ні вылучэнні аб'ектаў. І больш складаныя аперацыі з метададзенымі выклікаюцца толькі пры дадатным выніку, а не на кожнае паведамленне. Такім чынам, мы выключылі тону накладных выдаткаў, а астатняя нагрузка засяроджана ў невялікім унутраным цыкле пошуку, які добра падыходзіць для далейшай аптымізацыі.
Наш фактычны пошукавы алгарытм заснаваны на . Ён падобны на алгарытм Баера - Мура з пропускам прыкладна даўжыні пошукавага радка на кожным кроку. Галоўнае адрозненне ў тым, што ён правярае два байта за раз, каб мінімізаваць ілжывыя супадзенні.
Наша рэалізацыя патрабуе для кожнага пошуку стварэння пошукавай табліцы 64K, але гэта глупства ў параўнанні з гігабайтамі дадзеных, у якіх мы шукаем. Унутраны цыкл апрацоўвае некалькі гігабайт у секунду на адным ядры. На практыцы стабільная прадукцыйнасць складае каля 1,25 ГБ у секунду на кожным ядры, і ёсць патэнцыял для паляпшэння. Можна ўхіліць некаторыя накладныя выдаткі за межамі ўнутранага цыклу, і мы плануем паэксперыментаваць c унутраным цыклам на C замест Java.
Ужывальны сілу
Мы абмеркавалі, што пошук па логах можна рэалізаваць "груба", але колькі "сілы" ў нас ёсць? Нямала.
1 ядро: пры правільным выкарыстанні адно ядро сучаснага працэсара даволі магутнае само па сабе.
8 ядраў: у цяперашні час мы працуем на серверах Amazon hi1.4xlarge і i2.4xlarge SSD, на кожным з якіх 8 ядраў (16 патокаў). Як згадвалася вышэй, звычайна гэтыя ядры заняты фонавымі аперацыямі. Калі карыстач выконвае пошук, то фонавыя аперацыі прыпыняюцца, вызваляючы ўсе 8 ядраў для пошуку. Пошук звычайна завяршаецца за дзель секунды, пасля чаго фонавая праца аднаўляецца (праграма-рэгулятар гарантуе, што шквал пошукавых запытаў не перашкодзіць важнай фонавай працы).
16 ядраў: для надзейнасці мы арганізуем серверы па групах master/slave. У кожнага майстра ў падпарадкаванні адзін сервер SSD і адзін EBS. Калі галоўны сервер падае, то сервер на SSD неадкладна займае ягонае месца. Амаль увесь час master і slave працуюць нармальна, так што кожны блок дадзеных даступны для пошуку на двух розных серверах (у падпарадкаванага сервера EBS слабы працэсар, таму мы яго не разглядаем). Дзелім задачу паміж імі, так што ў нас даступныя ў агульнай складанасці 16 ядраў.
Шмат ядраў: у найбліжэйшай будучыні мы размяркуем дадзеныя па серверах такім чынам, каб усе яны ўдзельнічалі ў апрацоўцы кожнага нетрывіяльнага запыту. Будзе працаваць кожнае ядро. [Заўвага: мы рэалізавалі план і павысілі хуткасць пошуку да 1 ТБ/с, гл. нататку ў канцы артыкула].
Прастата забяспечвае надзейнасць
Яшчэ адна перавага метаду грубіянскай сілы складаецца ў даволі стабільнай прадукцыйнасці. Як правіла, пошук не занадта адчувальны да дэталяў задачы і набору дадзеных (думаю, менавіта таму яго завуць "грубым").
Індэкс ключавых слоў часам выдае неверагодна хуткі вынік, а ў іншых выпадках не. Дапусцім, у вас 50 ГБ логаў, у якіх тэрмін 'customer_5987235982' сустракаецца роўна тры разы. Пошук па гэтым тэрміне лічыць непасрэдна з азначніка тры месцазнаходжання і завершыцца імгненна. Але складаны пошук з падстаноўчымі знакамі можа сканаваць тысячы ключавых слоў і заняць шмат часу.
З іншага боку, пошук метадам грубай сілы для любога запыту выконваецца з больш-менш аднолькавай скорасцю. Пошук доўгіх слоў лепш, але нават пошук аднаго знака адбываецца дастаткова хутка.
Прастата метаду грубіянскай сілы азначае, што яго прадукцыйнасць блізкая да тэарэтычнага максімуму. Тут менш варыянтаў для непрадбачанай перагрузкі дыскаў, канфлікту пры блакіроўках, пагоні паказальніка і тысяч іншых прычын для збояў. Я проста паглядзеў на запыты, зробленыя карыстальнікамі Scalyr на мінулым тыдні на нашым самым загружаным сэрвэры. Было 14 запытаў. Роўна восем з іх занялі больш за адну секунду; 000% выканана ў межах 99 мілісекунд (калі вы не выкарыстоўвалі інструменты аналізу логаў, паверце: гэта хутка).
Стабільная, надзейная прадукцыйнасць важна для зручнасці выкарыстання сэрвісу. Калі ён перыядычна тармозіць, карыстачы будуць успрымаць яго як ненадзейны і неахвотна выкарыстоўваць.
Пошук па логах у дзеянні
Вось невялікая анімацыя, якая паказвае пошук Scalyr у дзеянні. У нас ёсць дэма-рахунак, куды мы імпартуем кожную падзею ў кожным публічным рэпазітары Github. У гэтай дэманстрацыі я вывучаю дадзеныя за тыдзень: прыкладна 600 МБ неапрацаваных логаў.
Відэа запісана ў прамым эфіры, без спецыяльнай падрыхтоўкі, на маім дэсктопе (каля 5000 кіламетраў ад сервера). Прадукцыйнасць, якую вы ўбачыце, шмат у чым абавязаная , а таксама хуткаму і надзейнаму бэкенду. Кожны раз, калі ўзнікае паўза без індыкатара 'loading', гэта я раблю паўзу, каб вы паспелі прачытаць, што я збіраюся націснуць.
У заключэнне
Пры апрацоўцы вялікіх аб'ёмаў дадзеных важна абраць добры алгарытм, але "добры" не значыць "мудрагелісты". Падумайце аб тым, як ваш код будзе працаваць на практыцы. З тэарэтычнага аналізу алгарытмаў выпадаюць некаторыя фактары, якія могуць мець вялікае значэнне ў рэальным свеце. Прасцейшыя алгарытмы лягчэй аптымізаваць і яны стабільней у памежных сітуацыях.
Таксама падумайце аб кантэксце, у якім будзе выконвацца код. У нашым выпадку патрэбныя дастаткова магутныя серверы для кіравання фонавымі задачамі. Карыстальнікі адносна рэдка ініцыююць пошук, таму мы можам запазычыць цэлую групу сервераў на кароткі перыяд, неабходны для выканання кожнага пошуку.
Метадам грубай сілы мы рэалізавалі хуткі, надзейны, гнуткі пошук па наборы логаў. Спадзяемся, што гэтыя ідэі будуць карысныя для вашых праектаў.
Праўка: загаловак і тэкст змяніліся з "Пошук на хуткасці 20 ГБ у секунду" на "Пошук на хуткасці 1 ТБ у секунду", каб адлюстраваць павелічэнне прадукцыйнасці за апошнія некалькі гадоў. Гэта павелічэнне хуткасці ў першую чаргу звязана са змяненнем тыпу і колькасці сервераў EC2, якія мы сёння ўздымаем для абслугоўвання ўзрослай кліенцкай базы. У бліжэйшы час чакаюцца змены, якія забяспечаць яшчэ адно рэзкае павышэнне эфектыўнасці працы, і мы з нецярпеннем чакаем, калі з'явіцца магчымасць пра гэта расказаць.
Крыніца: habr.com