در سیستمهای نرم‌افزاری جهت جلوگیری از ارسال کوئری های زیاد و تکراری به دیتابیس اصلی، پاسخ درخواست های تکراری را در cache ذخیره می کنند تا پاسخ دهی با سرعت بیشتری انجام شود. همان‌طور که گفته شد Redis یکی از تکنولوژی هایی است که جهت cache کردن داده میتوان استفاده کرد. استفاده از Redis آسان است و به همین دلیل این دیتابیس زیاد استفاده می ‌شود.

هنگامی که از Redis به عنوان حافظه cache استفاده می ‌کنیم، حذف داده‌های قدیمی پس از درج داده جدید از نیاز های معمول است. انجام چنین کاری میان توسعه ‌دهندگان مشهور است. همچنین حذف داده قدیمی پس از درج داده جدید در Memcached (یک سیستم cache) از قابلیت‌های محبوب آن است.

در این مقاله می ‌خواهیم به بررسی دو سیاست حذف داده های قدیمی از cache بپردازیم. یکی از این روش ها Least Recently Used (به اختصار LRU) و روش دیگر که در نسخه چهارم Redis معرفی شده، روش Least Frequently Used (به اختصار LFU) است.

تعیین حداکثر حافظه قابل استفاده

پارامتر maxmemory در پیکربندی Redis برای مشخص کردن حداکثر حافظه ای که در اختیار این دیتابیس قرار دارد، استفاده می ‌شود. جهت تنظیم این مقدار میتوان از فایل redis.conf یا دستور CONFIG SET استفاده کرد.

در مثال زیر حد مجاز حافظه را 100 مگابایت قرار می ‌دهیم.

maxmemory 100mb

اگر این مقدار را صفر قرار دهیم می ‌توانیم بدون محدودیت از حافظه مموری استفاده کنیم. پیش‌فرض این مقدار در سیستم‌های 64 بیتی 0 و در سیستم‌های 32 بیتی 3GB است.

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

سیاست های حذف

رفتاری که Redis پس از رسیدن به حد مجاز مموری انجام می ‌دهد، توسط پیکربندی maxmemory-policy قابل تنظیم است.

سیاست های زیر در حال حاضر موجود اند:

· noeviction: هنگامی که کاربر دستور جدیدی اجرا می ‌کند (معمولا دستوراتی که داده جدید ذخیره می‌ کنند) که باعث اشغال حافظه بیشتر می‌شود، خطا دریافت می ‌کند.

· allkeys-lru: کلید هایی که اخیرا کمتر استفاده شده‌اند را پاک می‌کند تا برای داده جدید، فضای کافی داشته باشیم.

· volatile-lru: مانند allkeys-lru عمل می‌کند با این تفاوت که تنها کلید هایی که تاریخ انقضا (expire time) برای آن‌ها تعریف شده است را پاک می ‌کند.

· allkeys-random: کلید ها را به صورت تصادفی پاک می‌کند تا برای داده جدید، فضا کافی داشته باشیم.

· volatile-random: مانند allkeys-random عمل می‌کند اما تنها کلید هایی که تاریخ انقضا برای آن‌ها تعریف شده است را پاک می ‌کند.

· volatile-ttl: از میان کلید هایی که تاریخ انقضا دارند، ابتدا کلید هایی که تاریخ انقضا آن‌ها نزدیک‌ تر است را حذف می‌ کند تا برای داده جدید، فضا کافی داشته باشیم.

سیاست های volatile-lru ، volatile-random و volatile-ttl در صورتی که هیچ کلیدی متناسب با پیش نیاز آن‌ها (تاریخ انقضا) نباشد، مانند noeviction رفتار می ‌کنند.

انتخاب سیاست درست بر اساس شرایط برنامه شما (چگونگی دسترسی به داده در برنامه شما)، اهمیت زیادی دارد. البته شما می‌توانید در روند اجرای برنامه، سیاست موردنظر خود را پیکربندی کنید و با اجرای دستور INFO مشاهده کنید که چه مقادیری در cache خوانده شدند.

چند قاعده کلی برای انتخاب سیاست مناسب :

· زمانی از سیاست allkeys-lru استفاده کنید که بیشتر درخواست های برنامه شما به بخش خاصی از داده‌ها مربوط می‌شود. به بیان دیگر هنگامی که شما انتظار دارید بخش خاصی از کلید های ذخیره شده بیشتر از بقیه کلید ها مورد استفاده قرار بگیرند، بهتر است این سیاست را انتخاب کنید. اگر مطمئن نیستید کدام سیاست برای برنامه شما مناسب است، allkeys-lru انتخاب خوبی است.

· زمانی از سیاست allkeys-random استفاده کنید که دسترسی به کلید ها در cache یک چرخه دورانی دارد. به عبارت دیگر هنگامی که انتظار دارید از همه بخش‌های cache به یک میزان استفاده شود، این سیاست را پیکربندی کنید.

· در صورتی از سیاست volatile-ttl استفاده کنید که می خواهید با استفاده از مقدار های TTL (Time To Live یا تاریخ انقضا) کلید های cache به Redis بفهمانید که کدام کلید اهمیت بیشتری دارد.

همچنین بهتر است توجه داشته باشید که تنظیم TTL برای کلید ها مقداری از مموری را اشغال می‌کند. بنابراین از آن جایی که سیاست allkeys-lru برای حذف کلید ها به TTL نیازی ندارد، استفاده از این سیاست کارامد تر است.

نحوه عملکرد فرآیند حذف:

این که بدانیم فرآیند حذف به چه شکل کار می‌کند، اهمیت زیادی دارد.

· کلاینت دستور جدیدی را اجرا می‌کند که باعث اضافه شدن داده می ‌شود.

· Redis میزان حافظه استفاده شده را بررسی کرده و اگر از حد حافظه پیکربندی شده بیشتر باشد، بر اساس سیاست تعیین شده کلید ها را حذف می کند.

· یک دستور جدید اجرا و این چرخه تکرار می ‌شود.

بنابراین ما به طور مداوم محدودیت حافظه را رد می‌کنیم و با حذف کردن کلید ها به حد تعیین شده باز می گردیم. اگر اجرای یک دستور موجب مصرف مقدار زیادی حافظه شود (مانند درج یک set بزرگ) به مدت قابل ‌توجهی، بیشتر از حد معین از حافظه استفاده خواهیم کرد.

الگوریتم تقریبی LRU

اگر به نام سیاست های مطرح شده در بخش قبلی دقت کنید واژه LRU که ابتدای مقاله نیز به آن اشاره شده بود را می بینید. در این بخش به بررسی عملکرد این الگوریتم می‌پردازیم.

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

این الگوریتم از نسخه 3 Redis به نحوی بهبود داده شد تا کلید هایی را برای نمونه برداری انتخاب کند که کاندید های خوبی برای حذف شدن باشند. این کار موجب افزایش بهره‌وری الگوریتم شد و رفتار آن را به رفتار الگوریتم اصلی LRU نزدیک‌تر کرد. چیزی که در مورد الگوریتم LRU در Redis اهمیت دارد این است که شما می‌توانید دقت عملکرد این الگوریتم را تغییر دهید. این کار با پیکربندی maxmemory-samples و تعیین تعداد کلید هایی که برای هر بار حذف کردن توسط Redis بررسی می‌شود قابل انجام است.

دلیل این که Redis از پیاده سازی حقیقی LRU استفاده نمی‌کند این است که الگوریتم اصلی مصرف حافظه بالاتری دارد. البته دقت پیاده سازی Redis از این الگوریتم، بسیار نزدیک به الگوریتم اصلی است. تصویر زیر یک مقایسه گرافیکی بین دقت پیاده سازی Redis و الگوریتم اصلی LRU است.

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

3 رنگ متفاوت در این تصویر دیده می‌شود که سه بخش متمایز را ایجاد کرده است.

· طوسی روشن، کلید های حذف شده است.

· طوسی، کلید های حذف نشده است.

· سبز کلید های اضافه شده است.

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

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

CONFIG SET maxmemory-samples <count>

انجام می‌شود.

اکنون که با LRU آشنا شدیم، مثالی از عملکرد آن می‌آوریم. تصور کنید حداکثر حافظه مجاز برای cache ما 3 است و کلید های زیر زیر به ترتیب از cache ما درخواست می‌شود:

A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D
در صورتی که از الگوریتم LRU استفاده کنیم حافظه cache ما حین پردازش درخواست ها اهمیت کلید ها را به شکل زیر تعیین می‌کند:

کلید A درخواست می‌شود

[A]

کلید B درخواست می‌شود

[A, B]

کلید C درخواست می‌شود

[A, B, C]

در اینجا چندین A پشت سر هم درخواست می‌شود. بنابراین A در ابتدای لیست قرار می‌گیرد (اخیرا بیشترین استفاده را داشته است)

[B, C, A]

کلید B درخواست می‌شود

[C, A, B]

کلید C درخواست می‌شود

[A, B, C]

کلید D درخواست می‌شود و از آن جایی که حافظه محدودیت 3 دارد کلید A از لیست خارج می‌شود

[B, C, D]

طبق این الگوریتم در صورتی که حافظه cache به محدودیت خود برسد، کلید A اولین کلیدی است که حذف می‌شود و پس از آن به ترتیب کلید های B، C و D حذف خواهند شد. این در حالی است که کلید A بسیار پر استفاده بوده و به احتمال زیاد در آینده نیز استفاده خواهد شد.

حالت جدیدی به نام LFU

از ابتدای عرضه نسخه 4 Redis، حالت جدیدی به نام Least Frequently Used موجود شد که در برخی موارد بهتر عمل می‌کند. پس از استفاده از LFU دیتابیس Redis تلاش می‌کند تعداد دسترسی به کلید ها را ضبط کند تا آن‌هایی که به ندرت استفاده شده‌اند را حذف کند و آن‌هایی که به طور معمول استفاده شده‌اند شانس بیشتری برای ماندن در حافظه داشته باشند.

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

برای پیکربندی حالت LFU سیاست های زیر وجود دارد:

· volatile-lfu: حذف کردن بر اساس الگوریتم LFU تقریبی، از بین کلید هایی که تاریخ انقضا دارند.

· allkeys-lfu: حذف هر کلید توسط الگوریتم LFU (داشتن یا نداشتن تاریخ انقضا اهمیتی ندارد).

LFU هم مانند LRU تقریبی است. LFU از یک شمارنده مبتنی بر احتمال به نام Morris counter استفاده می‌کند تا تناوب دسترسی به یک کلید را تخمین بزند. برخلاف LRU در LFU پارامترهای قابل تنظیمی وجود دارد. به عنوان مثال: با چه سرعتی امتیاز یک کلید پس از این که مدتی فراخوانی نشد، کاهش یابد؟

به طور پیش‌فرض Redis با تنظیمات مناسب و آزمایش شده ای پیکربندی شده است. اما در صورتی که کاربر بخواهد شخصی سازی بیشتری انجام دهد دست او باز گذاشته شده است تا در فایل redis.conf این کار را انجام دهد.

اکنون که با LFU آشنا شدیم، مثالی که بالاتر برای LRU آورده شد را با این الگوریتم بازبینی می‌کنیم.

در آن مثال محدودیت حافظه 3 بود و کلید ها به ترتیب زیر درخواست می‌شدند:

A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D

در صورتی که از الگوریتم LFU استفاده کنیم، تعداد دفعاتی که هر کلید درخواست شده است ضبط می‌شود و بر اساس آن کلیدی جهت حذف کردن انتخاب می‌شود. در این مثال تعداد درخواست کلید ها به صورت زیر ضبط می‌شود:

A - 12

B - 2

C - 2

D - 1

در مثال LRU کلید A برای حذف شدن انتخاب شد. اما طبق الگوریتم LFU برای کلید A شانس بیشتری وجود دارد که دوباره درخواست شود. بنابراین در این مثال، هنگامی که حافظه cache پر می‌شود کلیدی که کمترین درخواست را داشته است (به ترتیب D، C، B و سپسA ) حذف خواهد شد.

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

به طور کلی استفاده از LFU پیشنهاد بهتری بنظر می‌رسد اما اگر از نسخه‌های قدیمی تر Redis (قبل از 4) استفاده می‌کنید LRU تنها انتخاب شما است.

آشنایی با الگوریتم های LFU و LRU در Redis