این تأخیر حافظه است، احمقانه

وقتی CPU پایگاه داده خود را روی 100% می بینید، در واقع چه کاری انجام می دهد؟ ما دوست داریم طوری عمل کنیم که گویی CPU ها به خاطر سادگی کد را به صورت خطی اجرا می کنند، اما در حقیقت CPU ها حیواناتی فوق العاده پیچیده هستند. آنها به طور بالقوه می توانند دستورالعمل های زیادی را به طور همزمان انجام دهند، یا گاهی اوقات هیچ کدام را (با وجود اینکه کنسول ما 100٪ را نشان می دهد). از آنجایی که CPU ها می توانند کارهای زیادی را انجام دهند، یک CPU در 100% ممکن است بسیار کمتر از دیگری در 100% انجام دهد. یک CPU تنها در صورتی "بیکار" در نظر گرفته می شود که هیچ وظیفه ای (وظیفه لینوکس) به زمان CPU نیاز نداشته باشد. این بدان معنا نیست که خود CPU کاملا اشباع شده است.

پس چرا یک CPU به طور کامل مورد استفاده قرار نمی گیرد، حتی اگر به نظر می رسد 100٪ باشد؟

دسترسی به حافظه نسبت به عملیات داخلی CPU بسیار کندتر است. برای ارائه یک تصویر خوب از این میزان، یک CPU مدرن ممکن است بتواند جایی در قلمرو 4-8 دستورالعمل در هر نانوثانیه پردازش کند. دسترسی به حافظه به RAM می تواند چیزی در محدوده 50 تا 100 ثانیه طول بکشد. برای سهولت محاسبه شما، این بدان معناست که یک CPU مدرن می تواند حدود 400-800 دستورالعمل را برای هر دسترسی به حافظه از RAM انجام دهد.

با توجه به این موضوع، CPU ها از ابتدا ساخته شده اند تا راه خود را در این زمینه حل کنند. واضح ترین روشی که با آن برخورد می شود، حافظه پنهان CPU است. حافظه نهان CPU نسبت به RAM حافظه را نزدیکتر به CPU نگه می دارد که به معنای واقعی کلمه در تراشه CPU قرار می گیرد. نزدیکترین کش (کش L1) در هر عملیات حافظه حدود 1 ثانیه طول می کشد - این 50 تا 100 برابر سریعتر از RAM است! البته "مشکل" در اینجا این است که حافظه پنهان CPU نسبتا کوچک است. حافظه نهان L1 برای یک CPU مدرن احتمالا حدود 64 کیلوبایت است، در حالی که حافظه کش دورتر حداکثر تا چند صد مگابایت برای پردازنده های سطح بالا است.

یک پایگاه داده خوب سعی می‌کند داده‌ها را در «تکه‌های» کوچک دستکاری کند تا از حافظه پنهان استفاده کامل کند، و اغلب می‌شنوید که استفاده از کش به عنوان یکی از دغدغه‌های اصلی مهندسی عملکرد است.

بیایید به تجمیع‌های GROUP BY نگاهی بیندازیم تا بتوانیم استفاده از حافظه پنهان را بهتر درک کنیم. در GROUP BY، ما به دنبال این هستیم که یک مجموعه داده را بگیریم، آن را بر اساس یک ستون خاص (یا بیشتر) گروه بندی کنیم و تجمیع های خاصی را انجام دهیم (به عنوان مثال، شمارش یا جمع در ستون دیگری). روش "ساده لوح" ممکن است باز کردن HashTable با کلید گروهی باشد که بزرگتر می شود. برای هر ردیف جدید، باید بررسی کنید که آیا آن کلید وجود دارد یا خیر، اگر وجود دارد، به مجموعه مربوطه آن بروید و نتیجه را به‌روزرسانی کنید. ساده است، درست است؟ مشکل این است که اگر میلیون‌ها گروه منحصربه‌فرد دارید، اصلا از کش خود استفاده نمی‌کنید!

تقریبا هر دسترسی HashTable یک ضربه "سرد" خواهد بود که به رم می رود. این بدان معنی است که اگرچه CPU شما ممکن است /به نظر برسد/ به نظر می رسد که 100٪ استفاده شده است، در حقیقت دائما منتظر دسترسی های حافظه سرد خواهد بود.

برای نشان دادن این موضوع، ما پیشرفته ترین موتور Pivot خود را می گیریم و آن را خراب می کنیم! ما تمام منطق پیچیده خود را حذف می کنیم و آن را با سادگی جایگزین می کنیم:

سپس یک پرس و جوی ساده SELECT count(*) اجرا می کنیم، UserID FROM GROUP BY UserID در مجموعه داده "hits" که ClickBench ارائه می دهد (99 متر ردیف) را نشان می دهد. این پرس و جو به ما یک تعداد در هر UserID می دهد، به این معنی که ما یک ورودی در HashMap خود برای هر UserID خواهیم داشت - من در اینجا یک اسپویلر می دهم که حدود 17 میلیون شناسه کاربری منحصر به فرد وجود دارد. بررسی عملکرد ما روی سرور فلزی خالی از دوستان خوبمان در CherryServers (AMD EPYC 9124 Genoa، 16 هسته، 128 گیگابایت DDR5) خواهد بود.

متأسفانه نمی‌توانیم از یک ماشین معمولی AWS/GCP استفاده کنیم، زیرا می‌خواهیم به شمارنده‌هایی دسترسی داشته باشیم که به دلایل امنیتی در آن قرار ندارند (به عنوان مثال، می‌خواهیم ببینیم چقدر حافظه از کنترل‌کننده DRAM به ما منتقل می‌شود). ما خود را به یک هسته محدود می کنیم، زیرا این گروه ساده لوح نمی تواند روی هسته های زیادی کار کند.

این 3.9 ثانیه طول می کشد. آیا این خوب است؟ این بد است؟ همه چیز در این دنیا نسبی است یا اینطور می گویند. اگر دوباره کوئری را اجرا کنیم (بدون راه اندازی مجدد سرور)، 3.6 ثانیه طول می کشد. اجرای دوم همان موردی است که ما بیشتر به آن علاقه مندیم - هیچ دیسکی درگیر نیست زیرا همه چیز از قبل در کش صفحه ما قرار دارد.

متوجه خواهید شد که ما taskset -c را انجام دادیم. این فرآیند را به یک CPU معین پین می کند. این به ما این امکان را می دهد که Perf stat را روی آن CPU اجرا کنیم و ببینیم در داخل چه خبر است. ما دو گروه متریک را اندازه‌گیری می‌کنیم: درصد اسلات‌های CPU که به دلیل حافظه متوقف می‌شوند (و در عین حال کاری انجام نمی‌دهند)، و درصدی از اسلات‌های CPU که در واقع یک میکرو آپ را بازنشسته می‌کنند:

این به ما می گوید که 50.1٪ مواقع، CPU نمی تواند کاری انجام دهد، زیرا حافظه آن متوقف شده بود! و تنها 16.1 درصد از مواقع CPU عملا بازنشسته می‌شد (معروف به انجام آن).

آمار جالب دیگری که باید به دست آورد این است که چه تعداد از بارهای حافظه CPU ما از DRAM (و نه از حافظه پنهان) می آید:

هر بار 64 بایت است (حداقل مقداری که می‌توانید بیاورید، یک خط کش)، بنابراین می‌توانیم در 64 ضرب کنیم تا ببینیم در طول این پرس‌وجو، 4.5 گیگابایت از DRAM روی بارهای CPU برداشته‌ایم (این بدون هیچ‌گونه واکشی اولیه است).

بیایید اکنون سعی کنیم الگوریتم خود را برای استفاده از حافظه پنهان CPU بهبود دهیم. برای این کار از روشی به نام پارتیشن بندی رادیکس استفاده می کنیم. ایده این است که ادغام را به دو مرحله مجزا تقسیم کنیم:

فاز 1: در این مرحله، ما به سادگی کلیدها را به 4096 پارتیشن مختلف جدا می‌کنیم (به سادگی یک Vec از SlabVecs - یک SlabVec یک ساختار داده شبیه به یک Vec است که بالای حافظه‌ای است که قبلا در آن صفحه‌گذاری شده است. ما از Vecs برای حافظه خام در Pivot استفاده نمی‌کنیم، زیرا واریانس زیادی ایجاد می‌کند؛ چیزی برای این پست وبلاگ نیست!). پارتیشن با هش کردن کلید و گرفتن 12 بیت بالای آن (2**12=4096) تعیین می شود.

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

در نگاه اول، این راه حل ممکن است نسبتا عجیب به نظر برسد. ما در اینجا عملیات بیشتری انجام می دهیم، نه کمتر! هر ردیف، در هر دو راه حل، هش شده و به HashMap ارسال می شود. اما در این راه حل، ما ابتدا ردیف ها را به vec های به ظاهر بی معنی فشار می دهیم.

نکته کلیدی در اینجا (بدون جناس) این است که بفهمیم چرا این کار را انجام داده ایم. این برای کوچکتر کردن HashMaps جمع‌آوری شده است. با تقسیم گروه خود به 4096 قطعه، HashMaps کار خود را بسیار محتمل‌تر کرده‌ایم که در حافظه پنهان CPU ما قرار بگیرد. هر بار که ما در HashMap خود جستجو می کنیم، CPU ما به احتمال زیاد حافظه مربوطه را در حافظه پنهان خود پیدا می کند، که باعث صرفه جویی در زمان زیادی می شود. اما چرا به من اعتماد کنید؟ بیایید آن را اجرا کنیم!

و... بوم! 3.3 ثانیه و سپس در اجرای دوم 2.7 ثانیه! ما قطعا پیشرفت کرده ایم. اما برای اینکه واقعا این نقطه را به خانه هدایت کنیم، بیایید دوباره perf را اجرا کنیم:

اکنون می توانیم ببینیم که تصویر کاملا تغییر کرده است - 23.5٪ از زمان صرف انتظار برای حافظه (در مقابل 50٪ قبل)، 32٪ برای عملیات بازنشستگی واقعی است. ممکن است متوجه شوید که ما در واقع کار بیشتری انجام می دهیم، نه کمتر - در این اجرا، ما 19350459182 عملیات (مشتری ex_ret_ops) انجام دادیم، در حالی که قبل از پایگاه داده 11431618219 عملیات انجام می شد. با این حال، ارزش آن را دارد، زیرا همانطور که قبلا گفتیم - اگر بتوانیم دسترسی‌های سرد DRAM را به دستورالعمل‌های CPU ترجمه کنیم، تقریبا همیشه معامله خوبی است. در این مورد، ما از 8364109137 اسلات پردازنده متوقف شده به دلیل حافظه به 3790955223 کاهش یافتیم.

برای تکمیل تصویر و اینکه واقعا متوجه شوید که حافظه کمتری از DRAM می کشیم، بیایید دوباره بررسی کنیم که چند بار حافظه ما از DRAM می آید:

اووو این بدان معناست که در صورت تقاضا، به جای 4.5 گیگابایت در نسخه ساده، 1.5 گیگابایت از DRAM برداشتیم.

البته این محدودیتی نیست که ما می‌توانیم از حافظه پنهان CPU خود برای GROUP BYs استفاده کنیم. و استفاده از حافظه پنهان CPU ما تنها راهی نیست که بتوانیم تأخیر DRAM را پنهان کنیم. ترفند دیگر این است که حافظه را قبل از اینکه به حافظه پنهان نیاز داشته باشیم، از پیش واکشی کنیم، و ترفند دیگر ایجاد الگوریتم هایی است که به حداکثر رساندن توان حافظه اجازه می دهد - اما این برای این وبلاگ نیست! ما در وبلاگ بعدی خود به آن خواهیم پرداخت.

در حال حاضر، بدون توضیح زیاد، سرعت Pivot را برای این پرس و جو در یک هسته به شما واگذار می کنم:

البته، Pivot می داند که به طور موازی روی 16 هسته ما اجرا شود (جایی که موارد جالب دیگر وجود دارد)، در این صورت به این نتیجه می رسد:

اگر می‌خواهید سرعت‌های فوق‌العاده‌ای بالاتر از پارکت‌ها داشته باشید (تفریح OSS!) از Pivot استفاده کنید، دفعه بعد شما را می‌بینم.