LRU (Least Recently Used) Cache

خوب برگشتیم با یه آموزش دیگه از مجموعه آموزش های جاوا ، البته توضیحاتش زیاد ربطی به جاوا نداره ولی کدی که میزنیم جاواست . (منو برد به دوران دانشگاه)

واقعیت اینکه دارم یه commons برای کش مینویسم که به غیر از تکنولوژی های مرسوم مثل redis , aerospike , memcached و ... میخوام از Collectionهای جاوا استفاده کنم برای پیاده سازی کش .

حالا برای کش کردم یه مفهموم داریم تحت عنوان LRU که میخوام اول اینو توضیح بدم ، بعد میریم یه نمونه کد از پروژه ای که دارم مینویسم رو براتون میزارم.

نگران نباشید COMMONS کامل بشه روی گیت در اختیارتون قرار میدم.

یه منبع : کدش رو از این و gpt کمک گرفتم .

www.javaxp.com

کش LRU (Least Recently Used) یک ساختار داده‌ای است که برای مدیریت مؤثر یک کش با اندازه ثابت از عناصر طراحی شده است.

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

هدف کش LRU حفظ داده‌های پرکاربردتر در کش است و اطمینان از حذف داده‌های قدیمی یا کم استفاده شده هنگام رسیدن به حداکثر ظرفیت.

1. مفهوم کش

کش یک منطقه ذخیره‌سازی موقتی است که برای نگهداری داده‌های پرکاربرد استفاده می‌شود. هدف از کش کردن ارائه دسترسی سریعتر به این داده‌ها از طریق ذخیره‌سازی آنها در مکانی است که سریعتر از منبع اصلی (مثلا یک پایگاه داده یا سرور خارجی) است.

برای مثال، در یک مرورگر وب، کش داده‌هایی مانند تصاویر و فایل‌های وب‌سایت‌های قبلاً مشاهده شده را ذخیره می‌کند. هنگامی که دوباره به این وب‌سایت مراجعه می‌کنید، مرورگر می‌تواند این داده‌ها را از کش بازیابی کند و زمان بارگذاری را کاهش دهد.

2. چه چیزی کش LRU را منحصر به فرد می‌کند؟

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

• ترتیب حذف: کش عنصر کمتر استفاده‌شده را زمانی که از ظرفیت خود فراتر می‌رود، حذف می‌کند.

(برای این حالت و تعریف این ظریفت ها جولو تر توی کد مشخص میکنیم داستان رو فعلا بخون فقط)

• کارایی: کش‌های LRU به گونه‌ای طراحی شده‌اند که داده‌هایی را که احتمالاً به زودی دوباره استفاده خواهند شد، در خود نگهداری کنند و نرخ دسترسی را افزایش دهند.

3. چگونه کش LRU کار می‌کند؟

کش LRU معمولاً از ترکیبی از یک جدول هش (یا دیکشنری) برای دسترسی سریع به داده‌ها و یک لیست پیوندی دو طرفه برای حفظ ترتیب عناصر بر اساس آخرین زمان استفاده تشکیل شده است. روش کار به ترتیب زیر است:

افزودن یک عنصر جدید:

اگر عنصر در کش موجود نباشد و جا برای افزودن وجود داشته باشد، عنصر به جدول هش و لیست پیوندی اضافه می‌شود.
عنصر جدید به ابتدای لیست اضافه می‌شود که نشان‌دهنده این است که اخیراً دسترسی یافته است.

دسترسی به یک عنصر:

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

حذف:

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

4. ساختارهای داده در کش LRU

یک کش LRU کارآمد به دو ساختار داده اصلی وابسته است:

• جدول هش (دیکشنری): این امکان را فراهم می‌کند که عملیات get و put به طور متوسط در زمان اجرا O(1) شوند. جدول هش هر کلید را به مقدار متناظر آن در کش نگاشت می‌کند.
• لیست پیوندی دو طرفه: این امکان را فراهم می‌کند که عملیات انتقال از ابتدای لیست و حذف از انتهای آن نیز در زمان اجرا O(1) شود. لیست پیوندی ترتیب دسترسی را نگه می‌دارد و حذف عناصر کمتر استفاده‌شده را آسان می‌کند.

چرا از هر دو ساختار استفاده می‌شود؟

• جدول هش دسترسی سریع به داده‌ها بر اساس کلید را فراهم می‌کند، اما ترتیب دسترسی را حفظ نمی‌کند.
• لیست پیوندی دو طرفه ترتیب دسترسی را نگهداری کرده و حذف ساده‌ترین عناصر را تسهیل می‌کند.

5. عملیات در کش LRU

• get(key):
• مقدار مرتبط با key را از کش بازیابی می‌کند.

. اگر key وجود داشته باشد، این کلید به ابتدای لیست منتقل شده و مقدار آن برگشت داده می‌شود.
. اگر key وجود نداشته باشد، -1 یا مقدار مشابهی برگردانده می‌شود تا نشان دهد که پیدا نشده است.

• put(key, value):
• مقدار برای key را درج یا به‌روزرسانی می‌کند.

. اگر key وجود داشته باشد، مقدار آن به‌روزرسانی شده و کلید به ابتدای لیست منتقل می‌شود.
. اگر key وجود نداشته باشد:

- اگر کش پر باشد، عنصر کمتر استفاده‌شده را (آخرین عنصر در لیست پیوندی) حذف می‌کند.
- جفت کلید-مقدار جدید به جدول هش و ابتدای لیست پیوندی اضافه می‌شود.

6. کارایی

عملیات به دلیل نکات زیر کارآمد است:

• عملیات get(key) و put(key, value) هر دو دارای زمان پیچیدگی O(1) هستند، چون جدول هش دسترسی ثابت را فراهم می‌کند.
• حذف عنصر کمتر استفاده‌شده نیز دارای زمان پیچیدگی O(1) است زیرا حذف از لیست پیوندی (از انتها) و به‌روزرسانی در جدول هش در زمان ثابت صورت می‌گیرد.

7. کاربردهای عملی کش LRU

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

• مرورگرهای وب: ذخیره‌سازی تصاویر و فایل‌های وب‌سایت‌های پر بازدید. وقتی کش پر شود، منابع کمتر استفاده‌شده حذف می‌شود.
• کشینگ کوئری‌های پایگاه داده: در پایگاه داده‌ها، می‌توان کوئری‌ها یا نتایج پر استفاده را کش کرد. وقتی کوئری جدیدی وارد می‌شود و کش پر است، کمتر استفاده‌شده‌ها حذف خواهند شد.
• مدیریت حافظه: کش‌های LRU در سیستم‌عامل‌ها و سیستم‌های حافظه مجازی برای نگهداری صفحات اخیر در حافظه استفاده می‌شوند، در حالی که صفحات کم‌تر استفاده شده از حافظه خارج می‌شوند.
• شبکه‌های تحویل محتوا (CDN): هنگام ارائه محتوا مانند تصاویر یا ویدئوها، CDNها معمولاً از کش‌های LRU برای ذخیره‌سازی محتواهای پر درخواست در لبه شبکه استفاده می‌کنند.

8. انواع مختلف کش LRU

برخی از انواع یا گسترش‌های کش LRU که ممکن است عملکرد یا ویژگی‌های آن را بهبود دهند یا تغییر دهند عبارتند از:

• LFU (Least Frequently Used):

برخلاف LRU که کمتر استفاده‌شده را حذف می‌کند، LFU اقلامی را حذف می‌کند که به کمترین تعداد دفعات دسترسی داشته‌اند.

• MRU (Most Recently Used):

در مقابل LRU، کش MRU اقلامی را حذف می‌کند که اخیراً بیشترین استفاده را داشته‌اند.

• کشینگ دو سطحی:

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

9. نمونه پیاده‌سازی

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

public class LRUCache<K, V> {

private static final float hashTableLoadFactor = 0.75f;

private Map<K, V> map;
private int cacheSize;

public LRUCache(int cacheSize) {
this.cacheSize = cacheSize;
int hashTableCapacity = (int) Math.ceil(cacheSize / hashTableLoadFactor) + 1;
map = Collections.synchronizedMap(new LinkedHashMap<K, V>(hashTableCapacity, hashTableLoadFactor, true) {
// (an anonymous inner class)
private static final long serialVersionUID = 1;

@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > LRUCache.this.cacheSize;
}
});
}

public synchronized V get(K key) {
return map.get(key);
}

public synchronized V remove(K key) {
return map.remove(key);
}

public synchronized void put(K key, V value) {
map.put(key, value);
}

public synchronized void clear() {
map.clear();
}

public synchronized int usedEntries() {
return map.size();
}

public synchronized Collection<Map.Entry<K, V>> getAll() {
return new ArrayList<>(map.entrySet());
}

}

خوب اگر به این خط کد دقت کنید :

private static final float hashTableLoadFactor = 0.75f;

این یک فاکتور بارگزاری (load factor) برای جداول هش است که به‌عنوان شاخصی برای کنترل میزان پرشدگی استفاده می‌شود. مقدار 0.75 به این معنی است که جدول هش زمانی که به 75% ظرفیت خود برسد، اندازه‌اش افزایش می‌یابد.

خوب حالا یکی بگه این چیه پس :

int hashTableCapacity = (int) Math.ceil(cacheSize / hashTableLoadFactor) + 1;

در اینجا به عنوان ظرفیت اولیه برای LinkedHashMap تعریف شده است که در ساختار LRUCache استفاده می‌شود. این ظرفیت اولیه نمایانگر تعداد اولیه باکت‌ها یا سطل‌هایی است که HashMap باید در خود جای دهد تا با تعداد اولیه عناصر مورد نظر تطابق داشته باشد.

این رابطه توش چیه حالا : cacheSize / hashTableLoadFactor

این رابطه نشان می‌دهد که ظرفیت اولیه (hashTableCapacity) باید کمی بیشتر از cacheSize تنظیم شود تا فاکتور بار نیز در نظر گرفته شود.

فاکتور بار 0.75 به این معنی است که وقتی HashMap به 75% ظرفیت خود برسد، شروع به افزایش اندازه می‌کند. با استفاده از این فرمول، تعداد باکت‌های واقعی مورد نیاز حساب می‌شود تا مطمئن شوند که cacheSize مدنظر را بتوانند به طور مؤثری پشتیبانی کند.

حالا چرا تهش یه +1 داره :

یک واحد به مقدار محاسبه شده اضافه می‌شود تا از مشکلات بالقوه‌ی پرشدگی جدول جلوگیری شود و فضای اضافی برای رشد بهتر فراهم گردد.
این محاسبه به بهینه‌سازی عملکرد LinkedHashMap و موثر نگه داشتن LRU Cache کمک می‌کند تا مطمئن شود که ظرفیت کافی برای مدیریت تعداد درخواست‌های مشخص شده برای ذخیره‌سازی را دارد.

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

امیدوارم به کارتون بیاد ، لطفا اگر اطلاعاتی دارید که بهم کمک کنه برای بهتر کردن پروژه بگید.

خلاصه هر گلی زدید به سر خودتون زدید :))

نتیجه‌گیری

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

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

آدرس گیت رو بعد از کامل شدن اینجا میزارم سر بزنید تا 1 هفته دیگه .

منتظر نگاه های زیباتون هستم .