TL;DR: چهار سال پیش گوگل را با ایده ای برای یک ابزار جدید نظارت بر سرور ترک کردم. ایده این بود که توابع معمولاً جدا شده را در یک سرویس ترکیب کنیم جمع آوری و تجزیه و تحلیل گزارش، مجموعه معیارها، هشدارها و داشبوردها یکی از اصول این است که خدمات باید واقعی باشد سریع، تجربه ای آسان، تعاملی و لذت بخش را به devops ارائه می کند. این نیاز به پردازش مجموعه داده های چند گیگابایتی در کسری از ثانیه دارد و در عین حال در بودجه باقی می ماند. ابزارهای مدیریت لاگ موجود اغلب آهسته و درهم و برهم هستند، بنابراین ما با یک چالش خوب مواجه شدیم: طراحی هوشمندانه ابزاری برای ارائه تجربه جدیدی به کاربران.

این مقاله توضیح می‌دهد که چگونه ما در Scalyr این مشکل را با استفاده از روش‌های قدیمی، رویکرد brute force، حذف لایه‌های غیر ضروری و اجتناب از ساختارهای داده پیچیده حل کردیم. شما می توانید این درس ها را در مسائل مهندسی خود اعمال کنید.

قدرت مدرسه قدیمی

تجزیه و تحلیل گزارش معمولاً با جستجو شروع می شود: همه پیام هایی را که با یک الگوی خاص مطابقت دارند پیدا کنید. در Scalyr، این ها ده ها یا صدها گیگابایت گزارش از بسیاری از سرورها هستند. رویکردهای مدرن، به عنوان یک قاعده، شامل ساخت برخی از ساختار داده های پیچیده است که برای جستجو بهینه شده است. من مطمئناً این را در Google دیده ام، جایی که آنها در این نوع کارها بسیار خوب هستند. اما ما روی یک رویکرد بسیار ساده‌تر نشستیم: اسکن خطی سیاهه‌ها. و کار کرد - ما یک رابط قابل جستجو ارائه می دهیم که مرتبه ای سریعتر از رقبای ما است (به انیمیشن در پایان مراجعه کنید).

بینش کلیدی این بود که پردازنده‌های مدرن واقعاً در عملیات ساده و ساده بسیار سریع هستند. در سیستم‌های پیچیده و چندلایه‌ای که به سرعت I/O و عملیات شبکه تکیه می‌کنند، به راحتی از دست می‌رود و چنین سیستم‌هایی امروزه بسیار رایج هستند. بنابراین ما طرحی را ایجاد کردیم که لایه ها و زباله های اضافی را به حداقل می رساند. با چندین پردازنده و سرور به صورت موازی، سرعت جستجو به 1 ترابایت در ثانیه می رسد.

نکات کلیدی این مقاله:

• جستجوی Brute-Force یک رویکرد مناسب برای حل مسائل دنیای واقعی و در مقیاس بزرگ است.
• Brute force یک تکنیک طراحی است، نه یک راه حل بدون کار. مانند هر تکنیک دیگری، برای برخی مشکلات بهتر از سایر تکنیک ها مناسب است و می تواند ضعیف یا خوب اجرا شود.
• نیروی بی رحم مخصوصاً برای دستیابی خوب است پایدار بهره وری.
• استفاده موثر از brute force مستلزم بهینه سازی کد و استفاده از منابع کافی در زمان مناسب است. اگر سرورهای شما تحت بار غیر کاربر سنگین هستند و عملیات کاربر در اولویت باقی می ماند مناسب است.
• عملکرد به طراحی کل سیستم بستگی دارد، نه فقط به الگوریتم حلقه داخلی.

(این مقاله جستجوی داده ها در حافظه را شرح می دهد. در اغلب موارد، زمانی که کاربر جستجوی گزارش را انجام می دهد، سرورهای Scalyr قبلاً آن را در حافظه پنهان کرده اند. مقاله بعدی جستجوی گزارش های ذخیره نشده را مورد بحث قرار می دهد. همان اصول اعمال می شود: کد کارآمد، نیروی brute force. با منابع محاسباتی بزرگ).

روش Brute Force

به طور سنتی، یک مجموعه داده بزرگ با استفاده از یک فهرست کلیدواژه جستجو می شود. هنگامی که در گزارش های سرور اعمال می شود، این به معنای جستجو برای هر کلمه منحصر به فرد در گزارش است. برای هر کلمه، باید فهرستی از همه شامل ها تهیه کنید. این کار یافتن همه پیام‌های حاوی این کلمه را آسان می‌کند، به عنوان مثال «خطا»، «فایرفاکس» یا «transaction_16851951» - فقط کافیست به فهرست نگاه کنید.

من از این روش در گوگل استفاده کردم و به خوبی جواب داد. اما در Scalyr ما لاگ ها را بایت به بایت جستجو می کنیم.

چرا؟ از دیدگاه الگوریتمی انتزاعی، شاخص های کلیدواژه بسیار کارآمدتر از جستجوهای brute force هستند. با این حال، ما الگوریتم نمی فروشیم، بلکه عملکرد را می فروشیم. و عملکرد فقط در مورد الگوریتم ها نیست، بلکه در مورد مهندسی سیستم ها نیز هست. ما باید همه چیز را در نظر بگیریم: حجم داده، نوع جستجو، سخت افزار و زمینه نرم افزاری موجود. ما تصمیم گرفتیم که برای مشکل خاص ما، چیزی مانند "grep" بهتر از یک شاخص مناسب است.

ایندکس ها عالی هستند، اما محدودیت هایی دارند. پیدا کردن یک کلمه آسان است. اما جستجوی پیام هایی با چند کلمه، مانند 'googlebot' و '404'، بسیار دشوارتر است. جستجوی عبارتی مانند 'excaught uncaught' به نمایه دست و پا گیر تری نیاز دارد که نه تنها همه پیام ها را با آن کلمه، بلکه مکان خاص کلمه را نیز ثبت می کند.

سختی واقعی زمانی اتفاق می افتد که شما به دنبال کلمات نباشید. فرض کنید می خواهید ببینید چقدر ترافیک از ربات ها می آید. اولین فکر این است که لاگ ها را برای کلمه 'bot' جستجو کنید. به این ترتیب می توانید برخی از ربات ها را پیدا کنید: Googlebot، Bingbot و بسیاری دیگر. اما در اینجا "ربات" یک کلمه نیست، بلکه بخشی از آن است. اگر "ربات" را در فهرست جستجو کنیم، هیچ پستی با کلمه "Googlebot" پیدا نخواهیم کرد. اگر هر کلمه در فهرست را بررسی کنید و سپس فهرست را برای کلمات کلیدی یافت شده اسکن کنید، سرعت جستجو بسیار کاهش می یابد. در نتیجه، برخی از برنامه‌های لاگ اجازه جستجوی قسمتی از کلمه را نمی‌دهند یا (در بهترین حالت) دستور خاصی را با عملکرد پایین‌تر اجازه می‌دهند. ما می خواهیم از این امر اجتناب کنیم.

مشکل دیگر نقطه گذاری است. آیا می خواهید همه درخواست ها را پیدا کنید 50.168.29.7? در مورد اشکال زدایی سیاهههای مربوط به آن چه می توان گفت [error]? زیرنویس ها معمولاً از علائم نگارشی صرف نظر می کنند.

در نهایت، مهندسان عاشق ابزارهای قدرتمند هستند و گاهی اوقات یک مشکل تنها با یک بیان منظم قابل حل است. شاخص کلیدواژه برای این کار چندان مناسب نیست.

علاوه بر این، شاخص ها مجتمع. هر پیام باید به چند لیست کلیدواژه اضافه شود. این فهرست ها باید همیشه در قالبی به راحتی قابل جستجو نگهداری شوند. پرس و جوهایی با عبارات، قطعات کلمه یا عبارات منظم باید به عملیات چند لیستی ترجمه شوند و نتایج اسکن و ترکیب شوند تا یک مجموعه نتیجه تولید شود. در زمینه یک سرویس چند مستاجر در مقیاس بزرگ، این پیچیدگی مسائل عملکردی را ایجاد می کند که هنگام تجزیه و تحلیل الگوریتم ها قابل مشاهده نیستند.

فهرست های کلیدواژه نیز فضای زیادی را اشغال می کنند و ذخیره سازی هزینه اصلی در سیستم مدیریت لاگ است.

از طرف دیگر، هر جستجو می تواند قدرت محاسباتی زیادی را مصرف کند. کاربران ما از جستجوهای پرسرعت برای جستارهای منحصربفرد قدردانی می کنند، اما چنین پرس و جوهایی نسبتاً به ندرت انجام می شوند. برای سوالات جستجوی معمولی، به عنوان مثال، برای داشبورد، از تکنیک های خاصی استفاده می کنیم (در مقاله بعدی آنها را توضیح خواهیم داد). سایر درخواست ها به اندازه کافی نادر هستند که به ندرت مجبور می شوید بیش از یک درخواست را همزمان پردازش کنید. اما این بدان معنا نیست که سرورهای ما مشغول نیستند: آنها مشغول کار دریافت، تجزیه و تحلیل و فشرده سازی پیام های جدید، ارزیابی هشدارها، فشرده سازی داده های قدیمی و غیره هستند. بنابراین، ما یک منبع نسبتاً قابل توجهی از پردازنده ها داریم که می توانند برای اجرای پرس و جو استفاده شوند.

اگر مشکل بی رحمانه (و زور زیاد) دارید، فورس بی رحم کار می کند.

Brute force روی مشکلات ساده با حلقه های داخلی کوچک بهترین کار را دارد. اغلب می توانید حلقه داخلی را برای اجرا با سرعت های بسیار بالا بهینه کنید. اگر کد پیچیده باشد، بهینه سازی آن بسیار دشوارتر است.

کد جستجوی ما در ابتدا یک حلقه داخلی نسبتاً بزرگ داشت. ما پیام ها را در صفحات 4K ذخیره می کنیم. هر صفحه حاوی چند پیام (در UTF-8) و ابرداده برای هر پیام است. فراداده ساختاری است که طول مقدار، شناسه پیام داخلی و سایر فیلدها را رمزگذاری می کند. چرخه جستجو به این صورت بود:

این یک نسخه ساده شده از کد واقعی است. اما حتی در اینجا، قرار دادن چندین شیء، کپی داده ها و فراخوانی تابع قابل مشاهده است. JVM در بهینه سازی فراخوانی توابع و تخصیص اشیاء زودگذر بسیار خوب عمل می کند، بنابراین این کد بهتر از آنچه شایسته ما بود کار می کرد. در طول آزمایش، مشتریان با موفقیت از آن استفاده کردند. اما در نهایت ما آن را به سطح بعدی رساندیم.

(شما ممکن است بپرسید که چرا ما پیام ها را با این فرمت با صفحات 4K، متن و ابرداده ذخیره می کنیم، به جای اینکه مستقیماً با گزارش ها کار کنیم. دلایل زیادی وجود دارد که در این واقعیت خلاصه می شود که موتور Scalyr در داخل بیشتر شبیه یک پایگاه داده توزیع شده است تا یک پایگاه داده توزیع شده. سیستم فایل. جستجوی متن اغلب با فیلترهای سبک DBMS در حاشیه پس از تجزیه گزارش ترکیب می‌شود. ما می‌توانیم همزمان هزاران گزارش را جستجو کنیم و فایل‌های متنی ساده برای مدیریت داده‌های تراکنشی، تکراری و توزیع‌شده ما مناسب نیستند.

در ابتدا به نظر می رسید که چنین کدی برای بهینه سازی بروت فورس چندان مناسب نیست. "کار واقعی" در String.indexOf() حتی بر نمایه CPU تسلط نداشت. یعنی بهینه سازی این روش به تنهایی تاثیر قابل توجهی نخواهد داشت.

این اتفاق می افتد که ما متادیتا را در ابتدای هر صفحه ذخیره می کنیم و متن تمام پیام ها در UTF-8 در انتهای دیگر بسته بندی می شود. با استفاده از این، حلقه را برای جستجوی کل صفحه به یکباره بازنویسی کردیم:

این نسخه به طور مستقیم بر روی نمایش کار می کند raw byte[] و همه پیام ها را به طور همزمان در کل صفحه 4K جستجو می کند.

بهینه سازی این روش برای روش بروت فورس بسیار ساده تر است. حلقه جستجوی داخلی به طور همزمان برای کل صفحه 4K فراخوانی می شود، نه به طور جداگانه در هر پست. هیچ کپی برداری از داده ها، هیچ تخصیصی از اشیا وجود ندارد. و عملیات فراداده پیچیده تر فقط زمانی فراخوانی می شود که نتیجه مثبت باشد و نه در هر پیام. به این ترتیب ما یک تن از سربار را حذف کرده ایم و بقیه بار در یک حلقه جستجوی داخلی کوچک متمرکز می شود که برای بهینه سازی بیشتر مناسب است.

الگوریتم جستجوی واقعی ما بر اساس آن است ایده عالی لئونید ولنیتسکی. این الگوریتم شبیه به الگوریتم بویر مور است و تقریباً طول رشته جستجو را در هر مرحله نادیده می گیرد. تفاوت اصلی این است که دو بایت را در یک زمان بررسی می کند تا مطابقت های نادرست را به حداقل برساند.

پیاده سازی ما نیاز به ایجاد یک جدول جستجوی 64K برای هر جستجو دارد، اما این در مقایسه با گیگابایت داده ای که در آن جستجو می کنیم چیزی نیست. حلقه داخلی چندین گیگابایت در ثانیه را روی یک هسته پردازش می کند. در عمل، عملکرد پایدار در حدود 1,25 گیگابایت در ثانیه در هر هسته است و جای بهبود دارد. ممکن است مقداری از سربار خارج از حلقه داخلی حذف شود، و ما قصد داریم به جای جاوا با یک حلقه داخلی در C در C آزمایش کنیم.

ما از زور استفاده می کنیم

ما بحث کرده‌ایم که جستجوی گزارش را می‌توان «تقریباً» پیاده‌سازی کرد، اما چقدر «قدرت» داریم؟ خیلی زیاد.

1 هسته: هنگامی که به درستی استفاده می شود، تک هسته یک پردازنده مدرن به خودی خود بسیار قدرتمند است.

8 هسته: ما در حال حاضر روی سرورهای آمازون hi1.4xlarge و i2.4xlarge SSD اجرا می کنیم که هر کدام دارای 8 هسته (16 رشته) هستند. همانطور که در بالا ذکر شد، این هسته ها معمولاً مشغول عملیات پس زمینه هستند. هنگامی که کاربر جستجو را انجام می دهد، عملیات پس زمینه به حالت تعلیق در می آید و هر 8 هسته را برای جستجو آزاد می کند. جستجو معمولاً در کسری از ثانیه کامل می‌شود و پس از آن کار پس‌زمینه از سر گرفته می‌شود (برنامه throttling تضمین می‌کند که رگبار درخواست‌های جستجو در کار پس‌زمینه مهم تداخل ایجاد نمی‌کند).

16 هسته: برای اطمینان، سرورها را در گروه‌های master/slave سازماندهی می‌کنیم. هر استاد یک SSD و یک سرور EBS تحت فرمان خود دارد. اگر سرور اصلی خراب شود، سرور SSD بلافاصله جای آن را می گیرد. تقریباً همیشه، master و slave به خوبی کار می کنند، به طوری که هر بلوک داده در دو سرور مختلف قابل جستجو است (سرور برده EBS پردازنده ضعیفی دارد، بنابراین ما آن را در نظر نمی گیریم). ما کار را بین آنها تقسیم می کنیم، به طوری که در مجموع 16 هسته در دسترس داریم.

هسته های زیادی: در آینده نزدیک، ما داده ها را در بین سرورها به گونه ای توزیع خواهیم کرد که همه آنها در پردازش هر درخواست غیر پیش پا افتاده شرکت کنند. هر هسته کار خواهد کرد. [توجه داشته باشید: ما این طرح را اجرا کردیم و سرعت جستجو را به 1 ترابایت در ثانیه افزایش دادیم، به یادداشت انتهای مقاله مراجعه کنید].

سادگی قابلیت اطمینان را تضمین می کند

مزیت دیگر روش بروت فورس عملکرد نسبتاً ثابت آن است. به طور معمول، جستجو به جزئیات مشکل و مجموعه داده‌ها خیلی حساس نیست (من حدس می‌زنم به همین دلیل به آن «درشت» می‌گویند).

شاخص کلمات کلیدی گاهی اوقات نتایج فوق العاده سریعی تولید می کند و گاهی اوقات اینطور نیست. فرض کنید 50 گیگابایت گزارش دارید که عبارت "customer_5987235982" دقیقاً سه بار در آن ظاهر می شود. جستجوی این عبارت سه مکان را مستقیماً از فهرست شمارش می کند و فوراً تکمیل می شود. اما جستجوهای پیچیده با حروف عامیانه می توانند هزاران کلمه کلیدی را اسکن کنند و زمان زیادی طول بکشد.

از سوی دیگر، جستجوهای brute force برای هر پرس و جو با سرعت کم و بیش یکسانی انجام می شود. جستجوی کلمات طولانی بهتر است، اما حتی جستجو برای یک کاراکتر بسیار سریع است.

سادگی روش brute force به این معنی است که عملکرد آن به حداکثر تئوری نزدیک است. گزینه های کمتری برای اضافه بارهای غیرمنتظره دیسک، جدال قفل، تعقیب نشانگر و هزاران دلیل دیگر برای شکست وجود دارد. من فقط به درخواست های کاربران Scalyr هفته گذشته در شلوغ ترین سرورمان نگاه کردم. 14 درخواست وجود داشت. دقیقاً هشت مورد از آنها بیش از یک ثانیه طول کشید. 000٪ در 99 میلی ثانیه تکمیل شد (اگر از ابزارهای تجزیه و تحلیل گزارش استفاده نکرده اید، به من اعتماد کنید: سریع است).

عملکرد پایدار و قابل اعتماد برای سهولت استفاده از سرویس مهم است. اگر به صورت دوره ای تاخیر داشته باشد، کاربران آن را غیرقابل اعتماد می دانند و تمایلی به استفاده از آن ندارند.

جستجوی ورود به سیستم در عمل

در اینجا یک انیمیشن کوتاه است که جستجوی Scalyr را در عمل نشان می دهد. ما یک حساب آزمایشی داریم که در آن هر رویداد را در هر مخزن عمومی Github وارد می کنیم. در این نسخه ی نمایشی، من داده های یک هفته ای را بررسی می کنم: تقریباً 600 مگابایت گزارش خام.

این ویدیو به صورت زنده و بدون آمادگی خاصی روی دسکتاپ من (حدود 5000 کیلومتر از سرور) ضبط شده است. عملکردی که خواهید دید تا حد زیادی به دلیل آن است بهینه سازی مشتری وب، و همچنین یک باطن سریع و قابل اعتماد. هر زمان که یک مکث بدون نشانگر "بارگیری" وجود دارد، این من هستم که مکث می کنم تا بتوانید آنچه را که می خواهم فشار دهم را بخوانید.

در نتیجه

هنگام پردازش مقادیر زیادی داده، انتخاب یک الگوریتم خوب مهم است، اما "خوب" به معنای "فانتزی" نیست. به نحوه عملکرد کد شما در عمل فکر کنید. تحلیل نظری الگوریتم‌ها برخی از عواملی را که می‌توانند در دنیای واقعی از اهمیت بالایی برخوردار باشند، کنار گذاشته است. الگوریتم های ساده تر برای بهینه سازی آسان تر و در موقعیت های لبه پایدارتر هستند.

همچنین به زمینه ای که کد در آن اجرا می شود فکر کنید. در مورد ما، ما به سرورهای به اندازه کافی قدرتمند برای مدیریت وظایف پس زمینه نیاز داریم. کاربران جستجوها را نسبتاً به ندرت آغاز می کنند، بنابراین ما می توانیم یک گروه کامل از سرورها را برای مدت کوتاه مورد نیاز برای تکمیل هر جستجو قرض بگیریم.

با استفاده از روش brute force، ما یک جستجوی سریع، قابل اعتماد و منعطف را در میان مجموعه‌ای از سیاهه‌ها اجرا کردیم. امیدواریم این ایده ها برای پروژه های شما مفید باشد.

ویرایش: عنوان و متن از «جستجو با سرعت 20 گیگابایت در ثانیه» به «جستجو با سرعت 1 ترابایت در ثانیه» تغییر کرده است تا نشان دهنده افزایش عملکرد در چند سال گذشته باشد. این افزایش سرعت در درجه اول به دلیل تغییر در نوع و تعداد سرورهای EC2 است که ما امروز برای ارائه خدمات به مشتریان افزایش یافته خود راه اندازی می کنیم. به زودی تغییراتی وجود دارد که باعث افزایش چشمگیر دیگری در بهره وری عملیاتی می شود و ما نمی توانیم منتظر به اشتراک گذاشتن آنها باشیم.

منبع: www.habr.com