TL;DR: לפני ארבע שנים עזבתי את גוגל עם רעיון לכלי חדש לניטור שרתים. הרעיון היה לשלב פונקציות מבודדות בדרך כלל לשירות אחד איסוף וניתוח יומן, איסוף מדדים, התראות ודשבורדים. אחד העקרונות הוא שהשירות חייב להיות אמיתי מהיר, מספק ל-devops חוויה קלה, אינטראקטיבית ומהנה. זה מצריך עיבוד מערכי נתונים מרובי גיגה בשברירי שנייה תוך שמירה על התקציב. כלי ניהול היומנים הקיימים הם לרוב איטיים ומסורבלים, ולכן עמדנו בפני אתגר טוב: עיצוב חכם של כלי שיעניק למשתמשים חוויה חדשה.

מאמר זה מתאר כיצד אנו ב-Scalyr פתרנו את הבעיה הזו על ידי יישום שיטות בית ספר ישן, גישת כוח גס, ביטול שכבות מיותרות והימנעות ממבני נתונים מורכבים. אתה יכול ליישם את השיעורים האלה לבעיות ההנדסיות שלך.

אולד סקול כוח

ניתוח יומן מתחיל בדרך כלל בחיפוש: מצא את כל ההודעות התואמות דפוס מסוים. ב-Scalyr מדובר בעשרות או מאות גיגה-בייט של יומנים משרתים רבים. גישות מודרניות, ככלל, כוללות בנייה של מבנה נתונים מורכב המותאם לחיפוש. בהחלט ראיתי את זה בגוגל, שם הם די טובים בדברים מהסוג הזה. אבל הגענו לגישה גסה הרבה יותר: סריקה ליניארית של יומנים. וזה עבד – אנחנו מספקים ממשק חיפוש מהיר יותר בסדרי גודל מהמתחרים שלנו (ראה אנימציה בסוף).

התובנה המרכזית הייתה שהמעבדים המודרניים אכן מהירים מאוד בפעולות פשוטות ופשוטות. קל לפספס זאת במערכות מורכבות מרובות שכבות הנשענות על מהירות קלט/פלט ופעולות רשת, ומערכות כאלה נפוצות מאוד כיום. אז פיתחנו עיצוב שממזער שכבות ועודפי פסולת. עם מספר מעבדים ושרתים במקביל, מהירות החיפוש מגיעה ל-1 TB לשנייה.

נקודות חשובות מהמאמר הזה:

• חיפוש בכוח גס הוא גישה מעשית לפתרון בעיות בקנה מידה גדול בעולם האמיתי.
• כוח גס הוא טכניקת עיצוב, לא פתרון נטול עבודה. כמו כל טכניקה, היא מתאימה יותר לבעיות מסוימות מאחרות, וניתן ליישם אותה בצורה גרועה או טובה.
• כוח גס טוב במיוחד להישגים יַצִיב פִּריוֹן.
• שימוש יעיל בכוח גס דורש אופטימיזציה של קוד והחלת משאבים מספיקים בזמן הנכון. זה מתאים אם השרתים שלך נמצאים תחת עומס כבד שאינו משתמש ופעולות המשתמש נשארות בראש סדר העדיפויות.
• הביצועים תלויים בתכנון של המערכת כולה, לא רק באלגוריתם הלולאה הפנימית.

(מאמר זה מתאר חיפוש אחר נתונים בזיכרון. ברוב המקרים, כאשר משתמש מבצע חיפוש ביומן, שרתי Scalyr כבר שמרו אותו במטמון. המאמר הבא ידון בחיפוש אחר יומנים לא מאוחסנים. אותם עקרונות חלים: קוד יעיל, כוח גס עם משאבי חישוב גדולים).

שיטת כוח גס

באופן מסורתי, ערכת נתונים גדולה מתבצעת באמצעות אינדקס מילות מפתח. כאשר מוחל על יומני שרת, משמעות הדבר היא חיפוש אחר כל מילה ייחודית ביומן. עבור כל מילה, אתה צריך לעשות רשימה של כל התכלילים. זה מקל למצוא את כל ההודעות עם המילה הזו, למשל 'שגיאה', 'פיירפוקס' או "transaction_16851951" - פשוט חפש באינדקס.

השתמשתי בגישה הזו בגוגל והיא עבדה טוב. אבל ב-Scalyr אנחנו מחפשים את היומנים בייט אחר בייט.

למה? מנקודת מבט אלגוריתמית מופשטת, אינדקסים של מילות מפתח הם הרבה יותר יעילים מחיפושי כוח גס. עם זאת, אנחנו לא מוכרים אלגוריתמים, אנחנו מוכרים ביצועים. וביצועים עוסקים לא רק באלגוריתמים, אלא גם בהנדסת מערכות. עלינו לשקול הכל: נפח הנתונים, סוג החיפוש, החומרה הזמינה והקשר התוכנה. החלטנו שלבעיה הספציפית שלנו, משהו כמו 'grep' מתאים יותר מאשר אינדקס.

אינדקסים הם נהדרים, אבל יש להם מגבלות. קל למצוא מילה אחת. אבל חיפוש הודעות עם מילים מרובות, כגון 'googlebot' ו-'404', הוא הרבה יותר קשה. חיפוש אחר ביטוי כמו 'חריג שלא נתפס' דורש אינדקס מסורבל יותר שמתעד לא רק את כל ההודעות עם המילה הזו, אלא גם את המיקום הספציפי של המילה.

הקושי האמיתי מגיע כשאתה לא מחפש מילים. נניח שאתה רוצה לראות כמה תנועה מגיעה מבוטים. המחשבה הראשונה היא לחפש ביומנים את המילה 'בוט'. כך תמצאו כמה בוטים: Googlebot, Bingbot ועוד רבים אחרים. אבל כאן 'בוט' הוא לא מילה, אלא חלק ממנה. אם נחפש 'bot' באינדקס, לא נמצא אף פוסט עם המילה 'Googlebot'. אם תבדוק כל מילה באינדקס ולאחר מכן תסרוק את האינדקס עבור מילות המפתח שנמצאו, החיפוש יאט מאוד. כתוצאה מכך, תוכניות יומן מסוימות אינן מאפשרות חיפוש חלקי מילים או (במקרה הטוב) מאפשרות תחביר מיוחד עם ביצועים נמוכים יותר. אנחנו רוצים להימנע מכך.

בעיה נוספת היא סימני פיסוק. האם אתה רוצה למצוא את כל הבקשות מ 50.168.29.7? מה לגבי איתור באגים ביומנים המכילים [error]? מנויים בדרך כלל מדלגים על סימני פיסוק.

לבסוף, מהנדסים אוהבים כלים רבי עוצמה, ולפעמים ניתן לפתור בעיה רק ​​באמצעות ביטוי רגיל. אינדקס מילות המפתח אינו מתאים במיוחד לכך.

בנוסף, המדדים מורכב. יש להוסיף כל הודעה למספר רשימות מילות מפתח. רשימות אלו צריכות להישמר בפורמט הניתן לחיפוש בקלות בכל עת. שאילתות עם ביטויים, שברי מילים או ביטויים רגולריים צריכות להיות מתורגמות לפעולות מרובות רשימות, ולסרוק את התוצאות ולשלב אותן כדי לייצר ערכת תוצאות. בהקשר של שירות רב-דיירים בקנה מידה גדול, מורכבות זו יוצרת בעיות ביצועים שאינן נראות לעין בעת ​​ניתוח האלגוריתמים.

אינדקסים של מילות מפתח גם תופסים הרבה מקום, ואחסון הוא עלות עיקרית במערכת ניהול יומנים.

מצד שני, כל חיפוש יכול לצרוך הרבה כוח מחשוב. המשתמשים שלנו מעריכים חיפושים מהירים של שאילתות ייחודיות, אך שאילתות כאלה מתבצעות לעתים רחוקות יחסית. עבור שאילתות חיפוש טיפוסיות, למשל, עבור לוח מחוונים, אנו משתמשים בטכניקות מיוחדות (נתאר אותן במאמר הבא). בקשות אחרות אינן תדירות מספיק, כך שלעתים נדירות תצטרך לעבד יותר מאחת בכל פעם. אבל זה לא אומר שהשרתים שלנו לא עסוקים: הם עסוקים בעבודה של קליטה, ניתוח ודחיסת הודעות חדשות, הערכת התראות, דחיסת נתונים ישנים וכדומה. לפיכך, יש לנו היצע די משמעותי של מעבדים שניתן להשתמש בהם לביצוע שאילתות.

כוח גס עובד אם יש לך בעיה אכזרית (והרבה כוח)

כוח גס עובד הכי טוב על בעיות פשוטות עם לולאות פנימיות קטנות. לעתים קרובות אתה יכול לייעל את הלולאה הפנימית כך שתפעל במהירויות גבוהות מאוד. אם הקוד מורכב, הרבה יותר קשה לייעל אותו.

לקוד החיפוש שלנו במקור היה לולאה פנימית גדולה למדי. אנו מאחסנים הודעות בדפים ב-4K; כל עמוד מכיל כמה הודעות (ב-UTF-8) ומטא נתונים עבור כל הודעה. מטא נתונים הם מבנה המקודד את אורך הערך, מזהה ההודעה הפנימית ושדות אחרים. מחזור החיפוש נראה כך:

זוהי גרסה פשוטה של ​​הקוד בפועל. אבל אפילו כאן, מיקומים מרובים של אובייקטים, עותקי נתונים וקריאות פונקציה גלויים. ה-JVM די טוב באופטימיזציה של קריאות פונקציות והקצאת אובייקטים ארעיים, כך שהקוד הזה עבד טוב יותר ממה שמגיע לנו. במהלך הבדיקה, הלקוחות השתמשו בו בהצלחה רבה. אבל בסופו של דבר לקחנו את זה לשלב הבא.

(תוכלו לשאול מדוע אנו מאחסנים הודעות בפורמט זה עם דפי 4K, טקסט ומטא נתונים, במקום עבודה עם יומנים ישירות. ישנן סיבות רבות, אשר מסתכמות בעובדה שבאופן פנימי מנוע Scalyr דומה יותר למסד נתונים מבוזר מאשר לבסיס נתונים מבוזר. מערכת קבצים. חיפוש טקסט משולב לעתים קרובות עם פילטרים בסגנון DBMS בשוליים לאחר ניתוח יומנים. אנו יכולים לחפש בו-זמנית אלפים רבים של יומנים בו-זמנית, וקבצי טקסט פשוטים אינם מתאימים לניהול נתונים עסקאות, משוכפלות, מבוזר שלנו).

בתחילה, נראה היה שקוד כזה אינו מתאים במיוחד לאופטימיזציה של כוח גס. "עבודה אמיתית" ב String.indexOf() אפילו לא שלט בפרופיל המעבד. כלומר, ייעול שיטה זו לבדה לא יביא השפעה משמעותית.

זה קורה שאנחנו מאחסנים מטא נתונים בתחילת כל עמוד, והטקסט של כל ההודעות ב-UTF-8 ארוז בקצה השני. מנצלים זאת, שכתבנו את הלולאה כדי לחפש את כל העמוד בבת אחת:

גרסה זו פועלת ישירות על התצוגה raw byte[] ומחפש את כל ההודעות בבת אחת על פני כל עמוד 4K.

הרבה יותר קל לייעל את זה עבור שיטת הכוח הגס. לולאת החיפוש הפנימית נקראת בו-זמנית עבור כל עמוד 4K, ולא בנפרד בכל פוסט. אין העתקה של נתונים, אין הקצאת אובייקטים. ופעולות מטא נתונים מורכבות יותר נקראות רק כאשר התוצאה חיובית, ולא בכל הודעה. כך חיסלנו המון תקורה, ושאר העומס מתרכז בלולאת חיפוש פנימית קטנה, שמתאימה היטב לאופטימיזציה נוספת.

אלגוריתם החיפוש בפועל שלנו מבוסס על רעיון נהדר של לאוניד וולניצקי. זה דומה לאלגוריתם Boyer-Moore, מדלג בערך על אורך מחרוזת החיפוש בכל שלב. ההבדל העיקרי הוא שהוא בודק שני בתים בכל פעם כדי למזער התאמות שווא.

ההטמעה שלנו דורשת יצירת טבלת חיפוש של 64K עבור כל חיפוש, אבל זה כלום בהשוואה לג'יגה-בייט של נתונים שאנחנו מחפשים דרכם. הלולאה הפנימית מעבדת מספר גיגה-בייט בשנייה על ליבה אחת. בפועל, ביצועים יציבים הם בסביבות 1,25 GB לשנייה בכל ליבה, ויש מקום לשיפור. אפשר לבטל חלק מהתקורה מחוץ ללולאה הפנימית, ואנו מתכננים להתנסות עם לולאה פנימית ב-C במקום ב-Java.

אנחנו משתמשים בכוח

דנו בכך שניתן ליישם חיפוש ביומן "בערך", אבל כמה "כוח" יש לנו? די הרבה.

1 ליבה: בשימוש נכון, ליבה אחת של מעבד מודרני היא חזקה למדי בפני עצמה.

8 ליבות: כרגע אנחנו פועלים על שרתי SSD hi1.4xlarge של Amazon ו-i2.4xlarge, כל אחד עם 8 ליבות (16 שרשורים). כפי שהוזכר לעיל, ליבות אלה עמוסות בדרך כלל בפעולות רקע. כאשר המשתמש מבצע חיפוש, פעולות הרקע מושעות, ומשחררות את כל 8 הליבות לחיפוש. החיפוש מסתיים לרוב בשבריר שנייה, ולאחר מכן מתחדשת עבודת הרקע (תוכנית המצערת מבטיחה ששטף שאילתות החיפוש לא יפריע לעבודת רקע חשובה).

16 ליבות: עבור אמינות, אנו מארגנים שרתים לקבוצות מאסטר/עבדים. לכל מאסטר יש SSD אחד ושרת EBS אחד בפיקודו. אם השרת הראשי קורס, שרת ה-SSD תופס מיד את מקומו. כמעט כל הזמן, מאסטר ו-slave עובדים מצוין, כך שכל בלוק נתונים ניתן לחיפוש בשני שרתים שונים (לשרת ה-slave של EBS יש מעבד חלש, אז אנחנו לא מתייחסים לזה). אנחנו מחלקים את המשימה ביניהם, כך שיש לנו בסך הכל 16 ליבות זמינות.

ליבות רבות: בעתיד הקרוב, נפיץ נתונים בין שרתים בצורה כזו שכולם ישתתפו בעיבוד כל בקשה לא טריוויאלית. כל ליבה תעבוד. [הערה: יישמנו את התוכנית והגדלנו את מהירות החיפוש ל-1 TB/s, ראה הערה בסוף המאמר].

הפשטות מבטיחה אמינות

יתרון נוסף של שיטת ה-Brute Force הוא הביצועים העקביים למדי שלה. בדרך כלל, החיפוש אינו רגיש במיוחד לפרטי הבעיה ומערך הנתונים (אני מניח שבגלל זה הוא נקרא "גס").

אינדקס מילות המפתח לפעמים מייצר תוצאות מהירות להפליא, ופעמים אחרות לא. נניח שיש לך 50 GB של יומנים שבהם המונח 'customer_5987235982' מופיע בדיוק שלוש פעמים. חיפוש אחר מונח זה סופר שלושה מיקומים ישירות מהאינדקס ויסתיים באופן מיידי. אבל חיפושים מורכבים של תווים כלליים יכולים לסרוק אלפי מילות מפתח ולקחת זמן רב.

מצד שני, חיפושי כוח גס מבצעים פחות או יותר באותה מהירות עבור כל שאילתה. חיפוש מילים ארוכות עדיף, אבל אפילו חיפוש של תו בודד הוא די מהיר.

הפשטות של שיטת הכוח הברוט פירושה שהביצועים שלה קרובים למקסימום התיאורטי. יש פחות אפשרויות לעומס בלתי צפוי של דיסקים, מחלוקת נעילה, רדיפה אחר מצביעים ואלפי סיבות אחרות לכישלון. בדיוק הסתכלתי על הבקשות של משתמשי Scalyr בשבוע שעבר בשרת העמוס ביותר שלנו. היו 14 בקשות. שמונה מהם בדיוק ארכו יותר משנייה אחת; 000% הושלמו תוך 99 מילישניות (אם לא השתמשת בכלי ניתוח יומנים, תאמין לי: זה מהיר).

ביצועים יציבים ואמינים חשובים לנוחות השימוש בשירות. אם הוא מפגר מעת לעת, המשתמשים יתפסו אותו כלא אמין ויימנעו מלהשתמש בו.

חיפוש יומן בפעולה

הנה אנימציה קצרה המציגה את חיפוש Scalyr בפעולה. יש לנו חשבון הדגמה שבו אנו מייבאים כל אירוע בכל מאגר Github ציבורי. בהדגמה זו, אני בוחן נתונים של שבוע: כ-600 מגה-בייט של יומנים גולמיים.

הסרטון הוקלט בלייב, ללא הכנה מיוחדת, על שולחן העבודה שלי (כ-5000 קילומטרים מהשרת). הביצועים שתראו נובעים במידה רבה ממנו אופטימיזציה של לקוחות אינטרנט, כמו גם אחורי מהיר ואמין. בכל פעם שיש הפסקה ללא מחוון 'טעינה', זה אני שמשהה כדי שתוכל לקרוא על מה אני עומד ללחוץ.

לסיכום

כאשר מעבדים כמויות גדולות של נתונים, חשוב לבחור באלגוריתם טוב, אבל "טוב" אין פירושו "מפואר". תחשוב על איך הקוד שלך יעבוד בפועל. הניתוח התיאורטי של אלגוריתמים משאיר כמה גורמים שיכולים להיות בעלי חשיבות רבה בעולם האמיתי. קל יותר לייעל אלגוריתמים פשוטים יותר ויציבים יותר במצבי קצה.

חשוב גם על ההקשר שבו הקוד יבוצע. במקרה שלנו, אנחנו צריכים שרתים חזקים מספיק כדי לנהל משימות רקע. משתמשים יוזמים חיפושים בתדירות נמוכה יחסית, כך שאנו יכולים לשאול קבוצה שלמה של שרתים לתקופה הקצרה הדרושה להשלמת כל חיפוש.

באמצעות שיטת כוח גס, יישמנו חיפוש מהיר, אמין וגמיש על פני קבוצה של יומנים. אנו מקווים שרעיונות אלה יהיו שימושיים עבור הפרויקטים שלך.

לַעֲרוֹך: הכותרת והטקסט השתנו מ"חפש ב-20 GB לשנייה" ל"חפש ב-1 TB לשנייה" כדי לשקף את העליות בביצועים במהלך השנים האחרונות. עלייה זו במהירות נובעת בעיקר משינויים בסוג ובמספר שרתי EC2 שאנו מציבים היום כדי לשרת את בסיס הלקוחות המוגדל שלנו. בקרוב יהיו שינויים שיספקו דחיפה דרמטית נוספת ביעילות התפעולית, ואנחנו לא יכולים לחכות לשתף אותם.

מקור: www.habr.com