ক্যাশ ইনভ্যালিডেশন ও ইভিকশন পলিসি

Cache invalidation & eviction policies (LRU/LFU)

৮ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

ক্যাশিং-এর দুটি ভিন্ন সমস্যা — ইনভ্যালিডেশন (কোনো এন্ট্রি কখন পুরনো/ভুল হয়ে গেছে তা জানা) ও ইভিকশন (ক্যাশ পূর্ণ হলে কোন এন্ট্রি সরিয়ে জায়গা করা)।
ইনভ্যালিডেশন স্ট্র্যাটেজি — TTL (নির্দিষ্ট সময় পর মেয়াদ শেষ), Explicit invalidation (ডেটা বদলালে অ্যাপ নিজে মুছে দেয়), Versioning (কী-এর মধ্যে ভার্সন নম্বর জুড়ে দেওয়া)।
ইভিকশন পলিসি — LRU (least-recently-used সরানো), LFU (least-frequently-used সরানো), FIFO (সবচেয়ে পুরনো insert সরানো)।
Phil Karlton-এর বিখ্যাত উক্তি অনুযায়ী কম্পিউটার সায়েন্সের দুটি সবচেয়ে কঠিন সমস্যার একটি হলো cache invalidation — Python কোডে collections.OrderedDict দিয়ে একটি সম্পূর্ণ LRU ক্যাশ বানিয়ে দেখব কেন।

এই পাঠে যা শিখবেন

ইনভ্যালিডেশন ও ইভিকশন — দুটি ভিন্ন সমস্যা কেন ও কীভাবে আলাদা
তিনটি ইনভ্যালিডেশন স্ট্র্যাটেজি — TTL, Explicit invalidation, Versioning
তিনটি ইভিকশন পলিসি — LRU, LFU, FIFO — এবং কখন কোনটি উপযুক্ত
Python দিয়ে OrderedDict-ভিত্তিক একটি সত্যিকারের LRU ক্যাশ বাস্তবায়ন, ধাপে ধাপে eviction ট্রেস করে

১ · ইনভ্যালিডেশন বনাম ইভিকশন — দুটি ভিন্ন সমস্যা

L19-L20-এ আমরা ক্যাশিং কীভাবে ডেটা রাখে ও ব্যবহার করে তা দেখেছি। কিন্তু দুটি প্রশ্ন এখনও বাকি —

ইনভ্যালিডেশনCache Invalidationএকটি ক্যাশ এন্ট্রি এখনো "সঠিক"/আপ-টু-ডেট আছে কি না তা নির্ধারণ করা এবং পুরনো হয়ে গেলে সেটি সরিয়ে দেওয়া বা আপডেট করার প্রক্রিয়া।
মূল ডেটা বদলে গেলে ক্যাশে থাকা পুরনো কপিটি কীভাবে জানব যে এটি এখন ভুল/স্টেল?

ইভিকশনCache Evictionক্যাশ তার নির্ধারিত ক্যাপাসিটিতে পূর্ণ হয়ে গেলে, নতুন এন্ট্রির জন্য জায়গা করতে কোন পুরনো এন্ট্রি সরিয়ে ফেলা হবে তা ঠিক করার নীতি।
ক্যাশের সীমিত মেমরি (RAM) পূর্ণ হয়ে গেলে নতুন এন্ট্রির জন্য জায়গা করতে কোনটি সরাব?

দুটি সমস্যা স্বাধীন — একটি এন্ট্রি সঠিক (invalid নয়) থাকা সত্ত্বেও ইভিকশন পলিসি সেটি সরিয়ে দিতে পারে (জায়গার অভাবে), আবার একটি এন্ট্রি ক্যাশে জায়গা থাকা সত্ত্বেও ইনভ্যালিডেশন লজিক সেটি সরিয়ে দিতে পারে (কারণ ডেটা বদলে গেছে)।

২ · ইনভ্যালিডেশন স্ট্র্যাটেজি

TTL (Time To Live)
প্রতিটি এন্ট্রি একটি নির্দিষ্ট সময় পর স্বয়ংক্রিয়ভাবে মেয়াদোত্তীর্ণ হয়ে যায় (যেমন ৬০ সেকেন্ড পর)। সবচেয়ে সহজ বাস্তবায়ন, কিন্তু মেয়াদ শেষ না হওয়া পর্যন্ত ডেটা বদলে গেলেও স্টেল থেকে যায়।

Explicit Invalidation
ডেটাবেসে পরিবর্তন হওয়ার সাথে সাথেই অ্যাপ্লিকেশন সক্রিয়ভাবে সংশ্লিষ্ট ক্যাশ এন্ট্রি মুছে দেয় বা আপডেট করে। তাৎক্ষণিক সঠিকতা দেয়, কিন্তু প্রতিটি রাইট পাথে অতিরিক্ত লজিক ও একাধিক ক্যাশ সার্ভারের ক্ষেত্রে সমন্বয় প্রয়োজন।

Versioning
ক্যাশ কী-এর মধ্যে একটি ভার্সন নম্বর জুড়ে দেওয়া হয় (যেমন user:42:v3) — ডেটা বদলালে ভার্সন বাড়িয়ে দিলেই পুরনো কী স্বয়ংক্রিয়ভাবে "অকার্যকর" হয়ে যায় (নতুন কী দিয়ে খোঁজা হয়), যদিও পুরনো এন্ট্রি মেমরিতে থেকে যায় যতক্ষণ না ইভিকশন তা সরায়।

৩ · ইভিকশন পলিসি

LRU — Least Recently Used
যে এন্ট্রি সবচেয়ে বেশি সময় ধরে অ্যাক্সেস করা হয়নি সেটি সরানো হয়। ধারণা: সাম্প্রতিক অতীতে যা ব্যবহৃত হয়নি, নিকট ভবিষ্যতেও সম্ভবত হবে না। বাস্তবে সবচেয়ে বেশি ব্যবহৃত পলিসি।

LFU — Least Frequently Used
যে এন্ট্রি সবচেয়ে কম সংখ্যকবার অ্যাক্সেস হয়েছে সেটি সরানো হয় — সাম্প্রতিকতার বদলে মোট ফ্রিকোয়েন্সি গণনা করে। কোনো আইটেম হঠাৎ জনপ্রিয় হয়ে আবার নিষ্ক্রিয় হয়ে গেলে LRU-এর চেয়ে ভিন্ন সিদ্ধান্ত নিতে পারে।

FIFO — First In, First Out
যে এন্ট্রি সবচেয়ে আগে ক্যাশে ঢুকেছিল সেটি সরানো হয় — অ্যাক্সেস প্যাটার্ন উপেক্ষা করে, শুধু insert-এর ক্রম দেখে। বাস্তবায়ন সবচেয়ে সহজ কিন্তু প্রায়ই সবচেয়ে কম কার্যকর, কারণ একটি সাম্প্রতিক-ব্যবহৃত পুরনো এন্ট্রিও সরিয়ে ফেলতে পারে।

কম্পিউটার সায়েন্সে একটি বিখ্যাত (মজার) উক্তি আছে — Phil Karlton-এর ভাষায়, "There are only two hard things in Computer Science: cache invalidation and naming things." ক্যাশ ইনভ্যালিডেশন সহজ মনে হলেও — কখন, কীভাবে, কোন স্কেলে (একটি সার্ভার নাকি হাজারো CDN এজ, L20) সঠিকভাবে করা যায় তা বাস্তবে বিস্ময়কর রকম জটিল হয়ে ওঠে।

OrderedDict-এ get/put হলে সেই কী move_to_end() দিয়ে পেছনে সরানো হয় — ক্যাপাসিটি ছাড়ালে popitem(last=False) দিয়ে সবচেয়ে সামনের (LRU) এন্ট্রি সরানো হয়।

৪ · Python-এ সম্পূর্ণ LRU ক্যাশ বাস্তবায়ন

collections.OrderedDict এন্ট্রির insertion order মনে রাখে এবং move_to_end() দিয়ে যেকোনো কী-কে "সবচেয়ে সাম্প্রতিক" হিসেবে চিহ্নিত করা যায়। ক্যাপাসিটি ৩ ধরে নিচে একটি ধারাবাহিক get/put সিকোয়েন্স চালিয়ে দেখা যাক ঠিক কখন এবং কোন কী evict হয়।

Python

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key not in self.cache:
            print(f"GET {key} → মিস (cache-এ নেই, আগেই evict হয়ে গেছে)")
            return None
        self.cache.move_to_end(key)
        print(f"GET {key} → হিট ({self.cache[key]}), নতুন order: {list(self.cache.keys())}")
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        print(f"PUT {key}={value} → order: {list(self.cache.keys())}")
        if len(self.cache) > self.capacity:
            evicted_key, _ = self.cache.popitem(last=False)
            print(f"  ⚠ ক্যাপাসিটি ({self.capacity}) অতিক্রম — evict হলো: '{evicted_key}' (least-recently-used)")

lru = LRUCache(3)

lru.put("A", 1)
lru.put("B", 2)
lru.put("C", 3)
lru.get("A")
lru.put("D", 4)
lru.get("B")
lru.put("E", 5)
lru.get("C")

print(f"\nচূড়ান্ত cache order: {list(lru.cache.keys())}")

ট্রেস করে দেখা যাক: A, B, C যোগ হওয়ার পর order হলো [A, B, C]। get("A") A-কে পেছনে সরায় → [B, C, A]। এরপর put("D") নতুন কী যোগ করে ক্যাপাসিটি ৪-এ পৌঁছায় → সবচেয়ে সামনের (least recently used) B evict হয় → [C, A, D]। get("B") তাই মিস দেয় (আগেই evict হয়ে গেছে)। এরপর put("E") আবার ক্যাপাসিটি ছাড়ায় → এই মুহূর্তে সামনে থাকা C evict হয় (C সবচেয়ে বেশি সময় ধরে অ্যাক্সেস হয়নি — শেষবার শুধু insert হয়েছিল, A ও D পরে অ্যাক্সেস/insert হয়েছে) → [A, D, E]। তাই get("C")-ও মিস দেয়। প্রতিটি eviction ঠিক সেই মুহূর্তে প্রকৃত least-recently-used কী-কেই সরিয়েছে — কোনো র‍্যান্ডম বা ভুল অনুমান নয়।

মূল কথা · Key takeaway

ইনভ্যালিডেশন ঠিক করে "ডেটা কখন ভুল" আর ইভিকশন ঠিক করে "জায়গার অভাবে কী সরাব" — বাস্তব ক্যাশিং সিস্টেম দুটোই একসাথে ব্যবহার করে (যেমন Redis-এ একটি এন্ট্রির TTL থাকতে পারে, আবার মেমরি পূর্ণ হলে LRU/LFU দিয়ে আগেভাগেও evict হতে পারে)। মডিউল ৫ (ক্যাশিং) এখানেই শেষ — L19-এ আমরা প্যাটার্ন শিখেছি, L20-এ ভৌগোলিক বিস্তার, L21-এ জীবনচক্র ব্যবস্থাপনা। পরের মডিউলে আমরা অ্যাসিনক্রোনাস সিস্টেম (মেসেজ কিউ, ইভেন্ট-ড্রিভেন আর্কিটেকচার) দেখব।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ TTL সবচেয়ে সহজ ইনভ্যালিডেশন স্ট্র্যাটেজি হওয়া সত্ত্বেও এতে একটি "স্টেল উইন্ডো" থাকে — এটি কখন গ্রহণযোগ্য?

যখন ডেটা মাঝে মাঝে সামান্য পুরনো হলেও ব্যবসায়িকভাবে কোনো ক্ষতি হয় না — যেমন একটি আবহাওয়ার পূর্বাভাস (৫ মিনিট পুরনো হলেও সমস্যা নেই) বা একটি প্রোডাক্ট পেজের "স্টক আছে" ব্যাজ (কিছু সেকেন্ড দেরিতে আপডেট হলেও গ্রহণযোগ্য)। TTL-এর সৌন্দর্য হলো এটি explicit invalidation-এর মতো প্রতিটি ডেটা-পরিবর্তনের সাথে সমন্বয় করার জটিলতা ছাড়াই কাজ করে — শুধু "কতক্ষণ স্টেল থাকা সহনীয়" এই একটি সংখ্যা ঠিক করলেই চলে।

প্র ০২ এমন একটি বাস্তব দৃশ্যকল্প দিন যেখানে LFU, LRU-এর চেয়ে ভালো সিদ্ধান্ত নেবে।

ধরুন একটি ভাইরাল পোস্ট এক ঘণ্টায় ১০,০০০ বার অ্যাক্সেস হলো, তারপর হঠাৎ নিষ্ক্রিয় হয়ে গেল — কিন্তু ঠিক পরের মুহূর্তে অন্য একটি সাধারণ পোস্টও একবার অ্যাক্সেস হলো। LRU শুধু "সাম্প্রতিকতা" দেখে, তাই সেই একবার-অ্যাক্সেস-হওয়া সাধারণ পোস্টটিকেই "সবচেয়ে সাম্প্রতিক" ভেবে ভাইরাল পোস্টের বদলে অন্য কিছু (হয়তো ভাইরাল পোস্টের চেয়ে অনেক কম গুরুত্বপূর্ণ একটি এন্ট্রি) সরিয়ে ফেলার ঝুঁকি রাখে না ঠিকই, কিন্তু সময়ের সাথে ভাইরাল পোস্ট আর অ্যাক্সেস না হলে eventually সরে যাবে। LFU এখানে ভাইরাল পোস্টের বিশাল সঞ্চিত ফ্রিকোয়েন্সি কাউন্ট মনে রাখে এবং তাকে অনেক বেশি সময় ধরে ক্যাশে রাখবে, এমনকি সাম্প্রতিক অ্যাক্সেস না থাকলেও — যদি অনুমান করা হয় সেটি আবার জনপ্রিয় হতে পারে।

প্র ০৩ Phil Karlton-এর মতে cache invalidation কেন কম্পিউটার সায়েন্সের সবচেয়ে কঠিন সমস্যাগুলোর একটি, যখন এটি শোনায় সহজ ("যখন ডেটা বদলায়, ক্যাশ মুছে ফেলো")?

বাস্তবে "কখন ডেটা বদলে গেছে তা জানা" নিজেই কঠিন হয়ে ওঠে যখন সিস্টেমটি ডিস্ট্রিবিউটেড — একই ডেটার কপি একাধিক অ্যাপ সার্ভারের লোকাল ক্যাশে, একটি শেয়ার্ড Redis-এ, এবং হাজারো CDN এজে (L20) থাকতে পারে। একটি আপডেট সব জায়গায় একই মুহূর্তে ছড়িয়ে দেওয়া, নেটওয়ার্ক বিলম্ব ও আংশিক ব্যর্থতা সামলে, এবং একইসাথে over-invalidation (অপ্রয়োজনে বারবার ক্যাশ খালি করে পারফরম্যান্স নষ্ট করা) এড়ানো — এই ভারসাম্য বজায় রাখাই আসল চ্যালেঞ্জ, শুধু একটি লাইন কোড লেখা নয়।

অনুশীলন

ট্রেস করুন: ক্যাপাসিটি ২ ধরে এই সিকোয়েন্স হাতে ট্রেস করুন: put(X), put(Y), get(X), put(Z) — প্রতিটি ধাপে order কী হবে এবং শেষ ধাপে কোন কী evict হবে তা লিখুন, তারপর কোড সেলে LRUCache(2) দিয়ে যাচাই করুন।

put(X) → [X]। put(Y) → [X, Y] (ক্যাপাসিটি ২, এখনও ঠিক আছে)। get(X) → X পেছনে সরে → [Y, X]। put(Z) → নতুন কী যোগ হয়ে [Y, X, Z], ক্যাপাসিটি ছাড়ায় → সামনের (least-recently-used) Y evict হয় → চূড়ান্ত order [X, Z]। লক্ষ্য করুন Y evict হলো, X নয় — কারণ X মাঝখানে get দিয়ে "সাম্প্রতিক" হিসেবে চিহ্নিত হয়েছিল।
সিদ্ধান্ত নিন: একটি CDN এজ সার্ভারের (L20) থাম্বনেইল ইমেজ ক্যাশ এবং একটি সার্চ অটোকমপ্লিট সিস্টেমের (L49) সাজেশন ক্যাশ — এই দুটির জন্য LRU নাকি LFU বেশি উপযুক্ত হবে বলে মনে হয়?

থাম্বনেইল ক্যাশ: ট্রাফিক প্যাটার্ন প্রায়ই "সাম্প্রতিক ট্রেন্ডিং কন্টেন্ট" অনুসরণ করে — যা এখন জনপ্রিয় তা কালকেও জনপ্রিয় নাও হতে পারে, তাই LRU স্বাভাবিক পছন্দ (সাম্প্রতিক অ্যাক্সেসই সবচেয়ে গুরুত্বপূর্ণ সংকেত)। অটোকমপ্লিট সাজেশন: জনপ্রিয় সার্চ টার্ম (যেমন সাধারণ শব্দ) দীর্ঘমেয়াদে বারবার ফিরে আসে, সাময়িক নিষ্ক্রিয়তা সত্ত্বেও — তাই LFU এখানে বেশি উপযোগী হতে পারে, কারণ এটি দীর্ঘমেয়াদী সামগ্রিক জনপ্রিয়তা মনে রাখে, শুধু সর্বশেষ অ্যাক্সেস নয়।