כתוב מחדש את מסד הנתונים של VKontakte מאפס ושרוד

המשתמשים שלנו כותבים הודעות אחד לשני מבלי לדעת עייפות.

זה די הרבה. אם תצאו לקרוא את כל ההודעות של כל המשתמשים, זה ייקח יותר מ-150 אלף שנה. בתנאי שאתה קורא מתקדם למדי ומבזבז לא יותר משנייה על כל הודעה.

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

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

ההיסטוריה במקרה

ביישום הראשון, הודעות VKontakte עבדו על שילוב של PHP backend ו-MySQL. זהו פתרון נורמלי לחלוטין לאתר סטודנטים קטן. עם זאת, אתר זה גדל ללא שליטה והחל לדרוש אופטימיזציה של מבני נתונים עבור עצמו.

בסוף 2009 נכתב מאגר מנוע הטקסט הראשון, ובשנת 2010 הועברו אליו הודעות.

במנוע הטקסט, הודעות אוחסנו ברשימות - מעין "תיבות דואר". כל רשימה כזו נקבעת על ידי uid - המשתמש שבבעלותו כל ההודעות הללו. להודעה יש קבוצה של תכונות: מזהה בן שיח, טקסט, קבצים מצורפים וכן הלאה. מזהה ההודעה בתוך "תיבה" הוא local_id, הוא לעולם לא משתנה ומוקצה ברצף להודעות חדשות. ה"קופסאות" עצמאיות ואינן מסונכרנות אחת עם השנייה בתוך המנוע; התקשורת ביניהן מתרחשת ברמת PHP. אתה יכול להסתכל על מבנה הנתונים והיכולות של מנוע טקסט מבפנים כאן.

זה היה מספיק עבור התכתבות בין שני משתמשים. נחשו מה קרה אחר כך?

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

"PHP, בוא נשלח הודעה לצ'אט", אומר המשתמש.
"קדימה, {username}," אומר PHP.

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

בסוף 2015 השקנו הודעות קהילתיות ובתחילת 2016 השקנו עבורם API. עם כניסתם של צ'טבוטים גדולים בקהילות, אפשר היה לשכוח מחלוקת עומסים אחידה.

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

מנועי הודעות ב-2016 הם 100 מופעים של חברי צ'אט וצ'אטים של חברים, ו-8000 מנועי טקסט. הם התארחו באלף שרתים, כל אחד עם 64 ג'יגה-בייט של זיכרון. כאמצעי חירום ראשון, הגדלנו את הזיכרון בעוד 32 GB. הערכנו את התחזיות. ללא שינויים דרסטיים, זה יספיק לשנה נוספת. אתה צריך או להשיג חומרה או לבצע אופטימיזציה של מסדי הנתונים עצמם.

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

קונספט חדש

המהות המרכזית של הגישה החדשה היא צ'אט. לצ'אט יש רשימה של הודעות הקשורות אליו. למשתמש יש רשימה של צ'אטים.

המינימום הנדרש הוא שני מסדי נתונים חדשים:

• מנוע צ'אט. זהו מאגר של וקטורי צ'אט. לכל צ'אט יש וקטור של הודעות שקשורות אליו. לכל הודעה יש טקסט ומזהה הודעה ייחודי בתוך הצ'אט - chat_local_id.
• מנוע משתמש. זהו אחסון של וקטורים של משתמשים - קישורים למשתמשים. לכל משתמש יש וקטור של peer_id (בני שיח - משתמשים אחרים, מולטי צ'אט או קהילות) ווקטור של הודעות. לכל peer_id יש וקטור של הודעות שקשורות אליו. לכל הודעה יש chat_local_id ומזהה הודעה ייחודי עבור אותו משתמש - user_local_id.

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

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

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

שליחת הודעה בסכימה החדשה נראית כך:

1. ה-PHP יוצר קשר עם מנוע המשתמש בבקשה לשלוח הודעה.
2. מנוע משתמש מעביר את הבקשה למופע מנוע הצ'אט הרצוי, אשר חוזר אל מנוע המשתמש chat_local_id - מזהה ייחודי של הודעה חדשה בתוך הצ'אט הזה. לאחר מכן, הצ'אט_מנוע משדר את ההודעה לכל הנמענים בצ'אט.
3. user-engine מקבל chat_local_id מ-chat-engine ומחזיר את user_local_id ל-PHP - מזהה הודעה ייחודי עבור משתמש זה. המזהה הזה משמש אז, למשל, לעבודה עם הודעות דרך ה-API.

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

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

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

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

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

חיפוש הודעות מיושם כשאילתה אלכסונית ממנוע משתמש לכל מופעי מנוע הצ'אט המכילים צ'אטים של משתמש זה. התוצאות משולבות במנוע המשתמש עצמו.

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

העברת נתונים

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

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

תור לחברי צ'אט. זה כולל 100 מופעים, בעוד ש-Chat-motor יש 4. כדי להעביר את הנתונים, אתה צריך להביא אותם לתאימות - לשם כך, חברי הצ'אט חולקו לאותם 4 עותקים, ואז הופעלה קריאת ה-binlog של חברי הצ'אט במנוע הצ'אט.

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

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

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

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

אנו משתמשים במבנה נתונים מיוחד לאחסון הודעות מיובאות.

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

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

הנתונים נכתבים לחברי צ'אט ולמנוע משתמש (ולא למנועי טקסט, כמו בפעולה רגילה לפי הסכמה הישנה). מנוע משתמש מיישר את הבקשה לצ'אט מנוע - וכאן ההתנהגות תלויה בשאלה אם הצ'אט הזה כבר מוזג או לא. אם הצ'אט עדיין לא מוזג, מנוע הצ'אט לא כותב לעצמו את ההודעה, והעיבוד שלה מתרחש רק במנוע הטקסט. אם הצ'אט כבר מוזג לתוך צ'אט-מנוע, הוא מחזיר את chat_local_id למנוע-משתמש ושולח את ההודעה לכל הנמענים. מנוע המשתמש מעביר את כל הנתונים לטקסט מנוע - כך שאם משהו קורה, נוכל תמיד לחזור אחורה, עם כל הנתונים הנוכחיים במנוע הישן. text-engine מחזיר את user_local_id, אשר מנוע המשתמש מאחסן וחוזר ל-backend.

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

ממצאים

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

השינויים בלוגיקה הם באמת עצומים. ואני רוצה לציין שזה לא תמיד אומר שנים שלמות של פיתוח על ידי צוות ענק ואינספור שורות קוד. מנוע צ'אט ומנוע משתמש יחד עם כל הסיפורים הנוספים כמו האפמן לדחיסת הודעות, עצי Splay ומבנה להודעות מיובאות הוא פחות מ-20 אלף שורות קוד. והם נכתבו על ידי 3 מפתחים תוך 10 חודשים בלבד (עם זאת, כדאי לזכור ש כל שלוש מפתח - אלופי עולם בתכנות ספורט).

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

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

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

מקור: www.habr.com