پایگاه داده پیام VKontakte را از ابتدا بازنویسی کنید و زنده بمانید

کاربران ما بدون آگاهی از خستگی برای یکدیگر پیام می نویسند.

این خیلی زیاد است. اگر بخواهید همه پیام های همه کاربران را بخوانید، بیش از 150 هزار سال طول می کشد. به شرطی که خواننده نسبتاً پیشرفته ای باشید و بیش از یک ثانیه برای هر پیام صرف نکنید.

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

برای ما این لحظه یک سال و نیم پیش آمد. چگونه به این نتیجه رسیدیم و در پایان چه اتفاقی افتاد - به ترتیب به شما می گوییم.

پس زمینه

در اولین پیاده‌سازی، پیام‌های VKontakte روی ترکیبی از باطن PHP و MySQL کار می‌کردند. این یک راه حل کاملاً عادی برای یک وب سایت دانشجویی کوچک است. با این حال، این سایت به طور غیرقابل کنترلی رشد کرد و شروع به درخواست بهینه سازی ساختارهای داده برای خود کرد.

در پایان سال 2009، اولین مخزن متن-موتور نوشته شد و در سال 2010 پیام ها به آن منتقل شد.

در موتور متن، پیام ها در لیست ها ذخیره می شدند - نوعی "صندوق پست". هر یک از این لیست ها توسط یک uid تعیین می شود - کاربری که همه این پیام ها را در اختیار دارد. یک پیام دارای مجموعه ای از ویژگی ها است: شناسه مخاطب، متن، پیوست ها و غیره. شناسه پیام در داخل "جعبه" local_id است، هرگز تغییر نمی کند و به صورت متوالی برای پیام های جدید اختصاص داده می شود. "جعبه ها" مستقل هستند و در داخل موتور با یکدیگر هماهنگ نیستند؛ ارتباط بین آنها در سطح PHP رخ می دهد. شما می توانید ساختار داده و قابلیت های موتور متن را از داخل نگاه کنید اینجا.

این برای مکاتبه بین دو کاربر کاملاً کافی بود. حدس بزنید بعد چه اتفاقی افتاد؟

در ماه مه 2011، VKontakte مکالماتی را با چندین شرکت کننده معرفی کرد - چند چت. برای کار با آنها، ما دو خوشه جدید ایجاد کردیم - چت اعضا و چت اعضای. اولی داده های مربوط به چت های کاربران را ذخیره می کند، دومی داده های مربوط به کاربران را توسط چت ها ذخیره می کند. علاوه بر خود لیست ها، برای مثال، کاربر دعوت کننده و زمان اضافه شدن آنها به چت را نیز شامل می شود.

کاربر می گوید: «PHP، بیایید یک پیام به چت ارسال کنیم.
PHP می گوید: «بیا، {username}.

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

در پایان سال 2015، ما پیام های جامعه را راه اندازی کردیم و در ابتدای سال 2016، یک API برای آنها راه اندازی کردیم. با ظهور ربات‌های چت بزرگ در جوامع، می‌توان توزیع بار را فراموش کرد.

یک ربات خوب روزانه چندین میلیون پیام تولید می کند - حتی پرحرف ترین کاربران هم نمی توانند به این موضوع ببالند. این بدان معنی است که برخی از نمونه‌های موتور متن، که چنین ربات‌هایی روی آن‌ها زندگی می‌کردند، به شدت آسیب دیدند.

موتورهای پیام در سال 2016 100 نمونه از اعضای چت و چت اعضا و 8000 موتور متن هستند. آنها روی هزار سرور میزبانی می شدند که هر کدام 64 گیگابایت حافظه داشتند. به عنوان اولین اقدام اضطراری، ما حافظه را 32 گیگابایت دیگر افزایش دادیم. پیش بینی ها را برآورد کردیم. بدون تغییرات شدید، این برای حدود یک سال دیگر کافی خواهد بود. شما باید یا سخت افزار را در اختیار داشته باشید یا خود پایگاه های داده را بهینه کنید.

با توجه به ماهیت معماری، تنها افزایش چند برابری سخت افزار منطقی است. یعنی حداقل دو برابر کردن تعداد اتومبیل ها - بدیهی است که این یک مسیر نسبتاً گران است. ما بهینه سازی خواهیم کرد.

مفهوم جدید

ماهیت اصلی رویکرد جدید چت است. یک چت دارای فهرستی از پیام های مرتبط با آن است. کاربر فهرستی از چت ها دارد.

حداقل مورد نیاز دو پایگاه داده جدید است:

• موتور چت این یک مخزن از وکتورهای چت است. هر چت دارای بردار پیام هایی است که به آن مربوط می شود. هر پیام دارای یک متن و یک شناسه پیام منحصر به فرد در داخل چت است - chat_local_id.
• موتور کاربر این یک ذخیره سازی از بردارهای کاربران است - پیوندهایی به کاربران. هر کاربر دارای یک بردار peer_id (همکار - سایر کاربران، چند چت یا جوامع) و یک بردار پیام است. هر peer_id دارای یک بردار از پیام های مربوط به آن است. هر پیام یک chat_local_id و یک شناسه پیام منحصر به فرد برای آن کاربر دارد - user_local_id.

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

کار با دیسک در پایگاه داده های ما در بیشتر موارد بر اساس ترکیبی از یک گزارش باینری از تغییرات (binlog)، عکس های فوری استاتیک و یک تصویر جزئی در حافظه است. تغییرات در طول روز در یک binlog نوشته می‌شوند و یک عکس فوری از وضعیت فعلی به صورت دوره‌ای ایجاد می‌شود. یک عکس فوری مجموعه ای از ساختارهای داده است که برای اهداف ما بهینه شده است. این شامل یک هدر (فرا نمایه تصویر) و مجموعه ای از متافایل ها است. هدر به طور دائم در RAM ذخیره می شود و نشان می دهد که در کجا به دنبال داده از عکس فوری بگردید. هر متافایل شامل داده‌هایی است که احتمالاً در زمان‌های نزدیک به آن‌ها مورد نیاز است - مثلاً مربوط به یک کاربر. هنگامی که با استفاده از هدر عکس فوری، پایگاه داده را پرس و جو می کنید، متافیل مورد نیاز خوانده می شود و سپس تغییرات در binlog که پس از ایجاد عکس فوری رخ داده است، در نظر گرفته می شود. می توانید در مورد مزایای این روش بیشتر بخوانید اینجا.

در همان زمان، اطلاعات روی هارد دیسک تنها یک بار در روز تغییر می کند - اواخر شب در مسکو، زمانی که بار حداقل است. به لطف این (با دانستن اینکه ساختار روی دیسک در طول روز ثابت است)، ما می توانیم بردارها را با آرایه هایی با اندازه ثابت جایگزین کنیم - و به همین دلیل حافظه را افزایش می دهیم.

ارسال پیام در طرح جدید به این صورت است:

1. پشتیبان PHP با موتور کاربر تماس می گیرد تا پیامی ارسال کند.
2. user-engine درخواست را به نمونه موتور چت مورد نظر پراکسی می کند، که به chat_local_id موتور کاربر باز می گردد - یک شناسه منحصر به فرد یک پیام جدید در این چت. chat_engine سپس پیام را برای همه گیرندگان در چت پخش می کند.
3. user-engine chat_local_id را از chat-engine دریافت می کند و user_local_id را به PHP برمی گرداند - یک شناسه پیام منحصر به فرد برای این کاربر. سپس از این شناسه استفاده می شود، به عنوان مثال، برای کار با پیام ها از طریق API.

اما علاوه بر ارسال پیام، باید چند مورد مهم دیگر را نیز پیاده سازی کنید:

• فهرست‌های فرعی، برای مثال، جدیدترین پیام‌هایی هستند که هنگام باز کردن فهرست مکالمه مشاهده می‌کنید. پیام های خوانده نشده، پیام های دارای برچسب ("مهم"، "هرزنامه"، و غیره).
• فشرده سازی پیام ها در موتور چت
• ذخیره پیام ها در موتور کاربر
• جستجو (از طریق تمام گفتگوها و در یک گفتگوی خاص).
• به روز رسانی در زمان واقعی (Longpolling).
• ذخیره تاریخچه برای پیاده سازی حافظه پنهان در مشتریان تلفن همراه.

همه فهرست‌های فرعی ساختارهایی به سرعت در حال تغییر هستند. برای کار با آنها استفاده می کنیم پخش درختان. این انتخاب با این واقعیت توضیح داده می شود که در بالای درخت ما گاهی اوقات یک بخش کامل از پیام ها را از یک عکس فوری ذخیره می کنیم - به عنوان مثال، پس از فهرست بندی مجدد شبانه، درخت از یک بالا تشکیل شده است که شامل تمام پیام های فهرست فرعی است. درخت Splay باعث می شود که به راحتی در وسط چنین راسی قرار داده شود بدون اینکه به تعادل فکر کنید. علاوه بر این، Splay داده های غیر ضروری را ذخیره نمی کند که باعث صرفه جویی در حافظه ما می شود.

پیام ها شامل حجم زیادی از اطلاعات، عمدتا متن، هستند که برای فشرده سازی مفید است. مهم است که بتوانیم حتی یک پیام فردی را با دقت از حالت آرشیو خارج کنیم. برای فشرده سازی پیام ها استفاده می شود الگوریتم هافمن با اکتشافات خود - به عنوان مثال، ما می دانیم که در پیام ها کلمات با "غیر کلمات" - فاصله ها، علائم نقطه گذاری - جایگزین می شوند - و همچنین برخی از ویژگی های استفاده از نمادها برای زبان روسی را به خاطر می آوریم.

از آنجایی که تعداد کاربران بسیار کمتر از چت است، برای ذخیره درخواست‌های دیسک با دسترسی تصادفی در موتور چت، پیام‌ها را در موتور کاربر ذخیره می‌کنیم.

جستجوی پیام به عنوان یک پرس و جو مورب از موتور کاربر به تمام نمونه‌های موتور چت که حاوی چت‌های این کاربر هستند، اجرا می‌شود. نتایج در خود موتور کاربر ترکیب می شوند.

خوب، تمام جزئیات در نظر گرفته شده است، تنها چیزی که باقی می ماند تغییر به یک طرح جدید است - و ترجیحا بدون اینکه کاربران متوجه آن شوند.

مهاجرت داده ها

بنابراین، ما یک موتور متن داریم که پیام‌های کاربر را ذخیره می‌کند، و دو خوشه چت اعضای و چت اعضا که داده‌های اتاق‌های چت چندگانه و کاربران موجود در آن‌ها را ذخیره می‌کنند. چگونه از این به موتور کاربر جدید و موتور چت منتقل شویم؟

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

صف برای اعضای چت. این شامل 100 نمونه است، در حالی که موتور چت 4 هزار مورد دارد. برای انتقال داده ها، باید آن را مطابقت دهید - برای این، اعضای چت به همان 4 هزار نسخه تقسیم شدند و سپس خواندن بیلوگ اعضای چت در موتور چت فعال شد.

اکنون موتور چت از چند چت از اعضای چت اطلاع دارد، اما هنوز چیزی در مورد گفتگو با دو همکار نمی داند. چنین گفتگوهایی در موتور متن با اشاره به کاربران قرار دارند. در اینجا ما داده‌ها را «سردر» در نظر گرفتیم: هر نمونه موتور چت از همه نمونه‌های موتور متن سؤال می‌کرد که آیا دیالوگ مورد نیاز را دارند یا خیر.

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

هر پیام دارای یک مهر زمانی است که حاوی زمان ارسال و متن است. ما از زمان برای مرتب‌سازی استفاده می‌کنیم - نشانگرهایی را به قدیمی‌ترین پیام‌های شرکت‌کنندگان چند چت قرار می‌دهیم و هش‌ها را از متن کپی‌های مورد نظر مقایسه می‌کنیم و به سمت افزایش مهر زمانی حرکت می‌کنیم. منطقی است که کپی ها دارای هش و مهر زمانی یکسان باشند، اما در عمل همیشه اینطور نیست. همانطور که به یاد دارید، همگام سازی در طرح قدیمی توسط PHP انجام می شد - و در موارد نادر، زمان ارسال یک پیام در بین کاربران مختلف متفاوت بود. در این موارد، ما به خودمان اجازه می‌دهیم مهر زمانی را ویرایش کنیم - معمولاً در عرض یک ثانیه. مشکل دوم ترتیب متفاوت پیام ها برای گیرندگان مختلف است. در چنین مواردی، ما اجازه دادیم یک کپی اضافی با گزینه های مختلف سفارش برای کاربران مختلف ایجاد شود.

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

ما از یک ساختار داده ویژه برای ذخیره پیام های وارد شده استفاده می کنیم.

این یک بردار اندازه را نشان می دهد بقیه کجا هستند - متفاوت هستند و به ترتیب نزولی با ترتیب خاصی از عناصر مرتب شده اند. در هر بخش با شاخص عناصر مرتب شده اند جستجوی یک عنصر در چنین ساختاری زمان می برد از طریق جستجوهای باینری اضافه شدن یک عنصر بیش از حد مستهلک می شود .

بنابراین، ما متوجه شدیم که چگونه داده ها را از موتورهای قدیمی به موتورهای جدید منتقل کنیم. اما این روند چندین روز طول می کشد - و بعید است که در این روزها کاربران ما عادت نوشتن برای یکدیگر را ترک کنند. برای اینکه پیام‌ها در این مدت گم نشوند، به یک طرح کاری تغییر می‌کنیم که از خوشه‌های قدیمی و جدید استفاده می‌کند.

داده ها برای اعضای چت و موتور کاربر (و نه به موتور متن، مانند عملکرد عادی طبق طرح قدیمی) نوشته می شود. موتور کاربر درخواست را به موتور چت پراکسی می کند - و در اینجا رفتار بستگی به این دارد که آیا این چت قبلاً ادغام شده است یا خیر. اگر چت هنوز ادغام نشده باشد، موتور چت پیام را برای خود نمی نویسد و پردازش آن فقط در موتور متن اتفاق می افتد. اگر چت قبلاً در chat-engine ادغام شده باشد، chat_local_id را به موتور کاربر برمی گرداند و پیام را برای همه گیرندگان ارسال می کند. موتور کاربر تمام داده‌ها را به موتور متنی پراکسی می‌کند - به طوری که اگر اتفاقی افتاد، ما همیشه می‌توانیم به عقب برگردیم و همه داده‌های فعلی را در موتور قدیمی داشته باشیم. text-engine user_local_id را برمی‌گرداند که موتور کاربر ذخیره می‌کند و به باطن باز می‌گرداند.

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

یافته ها

به لطف رویکرد جدید، تمام معیارهای عملکرد موتورها بهبود یافته و مشکلات مربوط به سازگاری داده ها حل شده است. اکنون می‌توانیم به سرعت ویژگی‌های جدید را در پیام‌ها پیاده‌سازی کنیم (و قبلاً این کار را شروع کرده‌ایم - حداکثر تعداد شرکت‌کنندگان در چت را افزایش دادیم، جستجوی پیام‌های ارسال‌شده را اجرا کردیم، پیام‌های پین‌شده را راه‌اندازی کردیم و محدودیت تعداد کل پیام‌ها را برای هر کاربر افزایش دادیم) .

تغییرات در منطق واقعاً عظیم است. و من می خواهم توجه داشته باشم که این همیشه به معنای سال ها توسعه کامل توسط یک تیم بزرگ و هزاران خط کد نیست. موتور چت و موتور کاربر به همراه تمام داستان‌های اضافی مانند هافمن برای فشرده‌سازی پیام، درخت‌های Splay و ساختار پیام‌های وارداتی کمتر از 20 هزار خط کد است. و آنها توسط 3 توسعه دهنده فقط در 10 ماه نوشته شده اند (با این حال، ارزش این را دارد که در نظر داشته باشید همه سه توسعه دهنده - قهرمانان جهان در برنامه های ورزشی).

علاوه بر این، به جای دو برابر کردن تعداد سرورها، تعداد آنها را به نصف کاهش دادیم - اکنون موتور کاربر و موتور چت روی 500 ماشین فیزیکی زنده هستند، در حالی که طرح جدید فضای بزرگی برای بارگذاری دارد. ما پول زیادی در تجهیزات صرفه جویی کردیم - حدود 5 میلیون دلار + 750 هزار دلار در سال در هزینه های عملیاتی.

ما در تلاش هستیم تا بهترین راه حل ها را برای پیچیده ترین و بزرگ ترین مشکلات پیدا کنیم. ما تعداد زیادی از آنها را داریم - و به همین دلیل است که ما به دنبال توسعه دهندگان با استعداد در بخش پایگاه داده هستیم. اگر دوست دارید و می دانید چگونه چنین مشکلاتی را حل کنید، دانش بسیار خوبی از الگوریتم ها و ساختارهای داده دارید، از شما دعوت می کنیم به تیم بپیوندید. با ما تماس بگیرید HRبرای جزئیات

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

منبع: www.habr.com