طراحی کش سنجاقک – انجمن DEV

من در پست قبلی خود در مورد سیاست های اخراج Redis صحبت کردم.
در این پست، می خواهم طراحی پشت کش Dragonfly را شرح دهم.

اگر در مورد Dragonfly نشنیده اید – لطفاً آن را بررسی کنید. از ایده‌های بدیع و جالبی که توسط تحقیقات سال‌های اخیر پشتیبانی شده‌اند، استفاده می‌کند [1]و [2]. این به معنای رفع بسیاری از مشکلاتی است که امروزه با Redis وجود دارد. من در 7 ماه گذشته روی Dragonfly کار کرده‌ام و یکی از جالب‌ترین و چالش‌برانگیزترین پروژه‌هایی بوده است که تا به حال انجام داده‌ام!

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

LRU

همانطور که از نامش پیداست، خط‌مشی کش کمتر استفاده شده (LRU) مواردی را که اخیراً کمتر استفاده شده‌اند، بیرون می‌کند. این روش کار می کند زیرا یک الگوریتم کش تلاش می کند تا نسبت ضربه یا احتمال دسترسی به آیتم های آن در آینده را بهینه کند.

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

این فرض معقول است، اما متأسفانه، اگر فرض بالا برقرار نباشد، این الگوریتم ضعیف عمل می کند. به عنوان مثال، یک الگوی دسترسی با توزیع دم بلند را در نظر بگیرید. در اینجا، محور y فرکانس دسترسی نرمال شده اقلام را در حافظه پنهان و محور x نشان دهنده مواردی است که از بالاترین فرکانس به کمترین مرتب شده اند.

در این مورد، بسیاری از آیتم‌های «زرد» تازه اضافه شده با فرکانس دسترسی کم، می‌توانند آیتم‌های «سبز» کمیاب اما ارزشمند را که مسئول اکثر بازدیدها هستند، خارج کنند. در نتیجه، سیاست LRU ممکن است محتویات آن را همراه با نهادهای ارزشمند “سبز” به دلیل نوسانات ترافیک جارو کند.

کارایی اجرای LRU

LRU یک الگوریتم ساده است که می تواند به طور موثر پیاده سازی شود.
در واقع، تمام موارد را در یک لیست دوگانه نگهداری می کند. هنگامی که به یک آیتم دسترسی پیدا می شود، LRU آن را به سر لیست منتقل می کند. برای خالی کردن آیتم های LRU، از انتهای لیست ظاهر می شود. نمودار بالا را ببینید. تمامی عملیات در داخل انجام می شود O(1)و سربار حافظه برای هر آیتم 2 اشاره گر است، یعنی 16 بایت در معماری 64 بیتی.

LRU در Redis

ردیس چند اکتشافی خط مشی اخراج را اجرا می کند. برخی از آنها به عنوان “LRU تقریبی” توصیف می شوند. چرا تقریبی؟ زیرا Redis یک نظم جهانی دقیق را در بین اقلام خود مانند LRU کلاسیک حفظ نمی کند. در عوض، آخرین مهر زمان دسترسی را در هر ورودی ذخیره می کند.

هنگامی که نیاز به بیرون انداختن یک آیتم دارد، Redis نمونه‌برداری تصادفی از کل فضای کلید انجام می‌دهد و K کاندید را انتخاب می‌کند. سپس موردی را که دارای کمترین مُهر زمانی اخیراً استفاده شده در میان آن کاندیدای K است انتخاب کرده و آن را خالی می‌کند. به این ترتیب، Redis 16 بایت در هر ورودی مورد نیاز برای سفارش اقلام در یک سفارش جهانی ذخیره می کند. این اکتشافی یک تقریب بسیار تقریبی از یک LRU است.نگهدارکنندگان Redis اخیراً در مورد امکان افزودن یک اکتشافی اضافی به Redis با اجرای یک خط مشی کلاسیک LRU با نظم جهانی بحث کرده اند، اما در نهایت تصمیم به مخالفت با آن گرفتند.

کش سنجاقک

Dragonfly کش را پیاده سازی می کند که:

• برخلاف LRU در برابر نوسانات ترافیک اخیر مقاوم است.
• به نمونه گیری تصادفی یا سایر تقریب ها مانند Redis نیاز ندارد.
• دارد صفر سربار حافظه برای هر مورد
• بسیار کوچک دارد O(1) سربار زمان اجرا

این یک رویکرد جدید برای طراحی کش است که قبلاً در تحقیقات دانشگاهی پیشنهاد نشده است.

کش سنجاقک (کش خط تیره) بر اساس سیاست کش معروف دیگری از مقاله 1994 است – “2Q: الگوریتم جایگزینی مدیریت بافر با کارایی بالا پایین”.

2Q با معرفی دو بافر مستقل به مشکلات مربوط به LRU می پردازد. 2Q به جای اینکه فقط تازگی را به عنوان یک عامل در نظر بگیرد، فرکانس دسترسی را نیز برای هر مورد در نظر می گیرد. ابتدا موارد اخیر را به اصطلاح می پذیرد بافر آزمایشی (پایین را ببینید). این بافر تنها بخش کوچکی از فضای کش را نگه می دارد، مثلاً کمتر از 10%. همه موارد جدید اضافه شده در داخل این بافر با یکدیگر رقابت می کنند.

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

2Q با اذعان به اینکه فقط به این دلیل که یک مورد جدید به حافظه پنهان اضافه شده است، LRU را بهبود می بخشد – به این معنی نیست که مفید است. 2Q مستلزم آن است که حداقل یک بار قبلاً به آن دسترسی داشته باشید تا به عنوان یک مورد با کیفیت بالا در نظر گرفته شود. به این ترتیب، کش 2Q ثابت شده است که قوی تر است و نرخ ضربه بالاتری نسبت به سیاست LRU دارد.

دشتر در 60 ثانیه

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

برای اهداف امروز ما، باید حقایق زیر را در مورد Dashtable در اجرای Dragonfly بدانیم:

1. از بخش هایی با اندازه ثابت تشکیل شده است. هر بخش دارای 56 سطل معمولی با چندین شکاف است. هر شکاف فضایی برای یک آیتم دارد.
2. الگوریتم مسیریابی Dashtable از مقدار هش آیتم برای محاسبه شناسه بخش آن استفاده می کند. علاوه بر این، از 56 سطل، 2 مورد را از پیش تعریف می‌کند که آیتم می‌تواند در آن بخش قرار گیرد. آیتم می تواند در هر شکاف آزاد در آن دو سطل قرار گیرد.
3. علاوه بر سطل‌های معمولی، یک بخش Dashtable 4 سطل مخفی را مدیریت می‌کند که ممکن است موارد سرریز را که فضایی در سطل‌های اختصاص‌داده‌شده ندارند، جمع‌آوری کند. الگوریتم مسیریابی هرگز سطل های مخفی را مستقیماً اختصاص نمی دهد. درعوض، تنها در صورتی که 2 سطل خانگی آن پر باشد، کالا مجاز است در هر یک از 4 سطل مخفی بماند. این به میزان زیادی استفاده از بخش را افزایش می دهد.
4. هنگامی که یک بخش پر می شود، و جایی برای یک کالای جدید در سطل های خانه و یا سطل های مخفی وجود ندارد، Dashtable با افزودن یک بخش جدید و تقسیم محتویات بخش کامل تقریباً به نصف رشد می کند.

نقطه ای که در آن یک بخش پر می شود، زمان مناسبی برای افزودن هر نوع سیاست اخراج به Dashtable است، زیرا این زمانی است که Dashtable رشد می کند. علاوه بر این، برای جلوگیری از رشد دشتبل، ما فقط می‌توانیم اقلام را از یک بخش کامل خارج کنیم. این یک چارچوب تخلیه بسیار دقیق است که در آن عمل می کند O(1) پیچیدگی زمان اجرا

اجرای 2Q

Dragonfly ایده های بالا را گسترش می دهد. یک راه حل ساده لوحانه، تقسیم ورودی های hashtable به دو بافر است: بافر آزمایشی با سفارش FIFO، و بافر محافظت شده با استفاده از لیست پیوندی LRU. این کار می کند اما نیاز به استفاده از ابرداده اضافی و هدر دادن حافظه گرانبها دارد.

در عوض، Dragonfly از طراحی منحصربه‌فرد Dashtable بهره می‌برد و از ویژگی‌های سفارشی ضعیف آن به نفع خود استفاده می‌کند.

برای توضیح نحوه کار 2Q با Dashtable، باید توضیح دهیم که چگونه بافرهای آزمایشی و محافظت شده را در آنجا تعریف می کنیم، چگونه یک آیتم آزمایشی را به بافر محافظت شده تبلیغ می کنیم و چگونه موارد را از حافظه پنهان خارج می کنیم.

ما معنای زیر را روی دشتبل اصلی قرار دادیم:

1. شکاف های درون یک سطل اکنون دارای رتبه یا اولویت هستند. یک شکاف در سمت چپ بالاترین رتبه را دارد (0)و آخرین شکاف سمت راست کمترین رتبه را دارد (9).
2. سطل های مخفی در یک بخش به عنوان یک بافر آزمایشی عمل می کنند. هنگامی که یک مورد جدید به بخش کامل اضافه می‌شود، به یک سطل مخفی در شیار 0 اضافه می‌شود. همه موارد دیگر در سطل به سمت راست منتقل می‌شوند و آخرین مورد در سطل خارج می‌شود. به این ترتیب سطل به عنوان یک صف FIFO برای موارد آزمایشی عمل می کند.
3. هر ضربه حافظه پنهان مورد خود را “ترویج” می کند:
   • اگر مورد در یک سطل انبار بود، بلافاصله به سطل خانه خود تا آخرین شکاف منتقل می شود.
   • اگر آن را در یک سطل خانه در شکاف بود i، با یک مورد در اسلات تعویض شده است i-1.
   • یک مورد در اسلات 0 در همان مکان می ماند
4. هنگامی که یک مورد آزمایشی به سطل محافظت شده ارتقا می یابد، به آخرین شکاف آنجا منتقل می شود. موردی که قبلاً آنجا بود دوباره به سطل آزمایشی تنزل داده می شود.

اساساً، خط مشی اخراج Dash-Cache شامل یک مرحله “اخراج” است که توسط (2) و مرحله تقویت مثبت توصیف شده توسط (3) توضیح داده شده است.

خودشه. هیچ ابرداده اضافی مورد نیاز نیست. اقلام با کیفیت بالا خیلی سریع در جایگاه های با رتبه بالا در سطل های خانه خود قرار می گیرند، در حالی که اقلام جدید اضافه شده در سطل های مخفی / آزمایشی با یکدیگر رقابت می کنند. در اجرای ما، هر سطل دارای 14 اسلات است، به این معنی که هر آیتم آزمایشی را می توان 14 بار قبل از خارج شدن از حافظه پنهان جابجا کرد، مگر اینکه مفید بودن خود را ثابت کند و ارتقا یابد. هر بخش دارای 56 سطل معمولی و 4 سطل مخفی است. بنابراین ما داریم 6.7% کل فضای اختصاص داده شده برای یک بافر آزمایشی. کافی است اقلام با کیفیت بالا را قبل از بیرون راندن بگیرید.

امیدوارم از خواندن اینکه چگونه طراحی کش Dragonfly از مفاهیم به ظاهر نامرتبط با هم به نفع خود استفاده می کند لذت برده باشید.

می خواهم سپاسگزاری کنم بن مانس، نویسنده بسته کافئین فوق العاده برای نظرات اولیه و راهنمایی در مورد نحوه استفاده از شبیه ساز کافئین به منظور مقایسه Dragonfly Cache با سایر کش ها.