آشنایی با الگوریتم LFU و نحوۀ کارکرد آن به منظور کَش کردن ریسورس‌های پُرکاربرد


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

اولین کسی باشید که به این سؤال پاسخ می‌دهید

در حقیقت، کَش کردن دیتا در دو صورت منجر به افزایش سرعت و در نتیجه بهبود پرفورمنس سیستم می‌شود که در ادامه هر یک را تشریح می‌کنیم:

- چنانچه اکثر ریکوئست‌ها به منظور دستیابی به فایل‌های مد نظر به حافظۀ کَش سیستم ارسال شوند بدین معنی که فایل مد نظر در حافظۀ کَش موجود بوده و از آن بازیابی شود به طوری که جهت دسترسی به دیتای مورد نیاز کاربر احتیاجی به مراجعه به حافظۀ اصلی نداشته باشیم.

- در صورتی که به اصطلاح Overhead ناشی از ذخیره‌سازی دیتا در حافظۀ کَش پایین باشد بدین معنی که فرآیند بررسی به منظور دسترسی به دیتای مد نظر و همچنین تصمیم‌گیری در مورد زمان مناسب جهت حذف و جایگزینی فایلی از آن تا حد ممکن سریع انجام شود.

حال در این مقاله قصد داریم تا بر آیتم دوم تمرکز کرده و به تشریح الگوریتمی تحت عنوان Least Frequently Used یا به اختصار LFU بپردازیم که به منظور حذف دیتایی از حافظۀ کَش مورد استفاده قرار می‌گیرد که کمترین درخواست را از سمت کاربر داشته است.

LFU چیست؟

LFU یک الگوریتم ذخیره‌سازی دیتا در حافظۀ کَش است و همان‌طور که از نامش برمی‌آید، نحوۀ کارکرد آن بدین صورت است که هر زمان ظرفیت حافظۀ کَش با محدودیت روبه‌رو می‌شود، داده‌هایی که کمترین استفاده را از سوی کاربران داشته‌اند از حافظۀ کَش حذف می‌کند بدین معنی که به ازای هر آیتم در حافظۀ کَش تعداد دفعات ریکوئست‌های انجام‌شده به منظور دستیابی به آن‌ها بررسی شده و آیتم‌هایی از حافظۀ کَش حذف می‌شوند که تعداد درخواست کمتری را از سوی کاربران داشته‌اند؛ بنابراین می‌توان گفت در شرایطی که ظرفیت حافظۀ کَش کاهش می‌یابد، این فرآیند اجرا شده و آیتم‌هایی از داده‌های ذخیره‌شده در حافظه کَش را انتخاب و حذف می‌کند.

الگوریتم LFU چه نقاط قوتی دارا است؟

به منظور آشنایی با نقاط قوت الگوریتم LFU مثالی را در نظر می‌گیریم که در آن برخی از ریسورس‌های مورد نیاز وب اپلیکیشن خود را در حافظۀ کَش سرورهایی از نوع شبکه‌های CDN ذخیره می‌کنیم به طوری که منابع مورد نیاز وب‌سایت مد نظر بر اساس الگوی استفادۀ کاربران ذخیره می‌شوند بدین صورت که ریسورس‌هایی در حافظۀ سیستم ذخیره می‌شوند که تعداد ریکوئست‌ها به منظور دستیابی به آن‌ها از سوی کاربران بالا باشند تا بدین ترتیب وب اپلیکیشن مد نظر در دفعات بعدی به جای فِچ کردن دیتا از سرور اصلی، آن را از حافظۀ کَش نزدیک‌ترین سرور به محل فیزیکی کاربر لود کرده و در اختیار ایشان قرار دهد (CDN مخفف عبارت مخفف Content Delivery Network بوده و به معنای «شبکه‌ٔ توزیع محتوا» می‌باشد که جهت کسب اطلاعات بیشتر در رابطه با نحوۀ کارکرد این شبکه‌ها می‌توانید به مقالۀ CDN چیست و چگونه کار می‌کند؟ مراجعه کنید.)

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

حال شرایطی را در نظر بگیریم که در آن تصاویر مربوط به محصولات جدید را در قالب یکسری به اصطلاح Landing Page و در هوم‌پبج وب‌سایت‌ خود قرار می‌دهیم که در چنین شرایطی آمار بازدید کاربران در ابتدا و در یک بازۀ زمانی خاص بسیار بالا بوده و پس از گذشت مدتی کاهش می‌یابد به طوری که در ابتدا نیاز به کَش کردن دیتای مربوطه به منظور افزایش سرعت دسترسی به آن‌ها داریم اما با گذشت زمان و کاهش تعداد مراجعات به صفحهٔ مد نظر نیازی به نگهداری آن در حافظۀ کَش نخواهیم داشت و از همین روی به‌کارگیری الگوریتم LFU در این موارد بسیار مفید می‌باشد.

در واقع، الگوریتم LFU در چنین شرایطی دیتایی را در حافظۀ کَش ذخیره می‌کند که بیشترین استفاده را از سمت کاربران دارد اما از سوی دیگر به محض کاهش تعداد ریکوئست‌ها به منظور لود دیتای مد نظر، آن را از حافظۀ کَش حذف می‌کند تا بدین ترتیب امکان ذخیره‌سازی برای سایر فایل‌های پُرکاربرد کاربران فراهم گردد.

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

منبع