Distributed Cache (Redis) ডিজাইন

ডেটাবেস থেকে প্রতিবার ডেটা পড়া ধীর ও ব্যয়বহুল। তাই আমরা প্রায়ই-দরকারি ডেটা RAM-এ রাখি—এটাই Cache। আজ আমরা Redis-এর মতো একটা distributed in-memory cache ডিজাইন করব, যা মিলিসেকেন্ডের নিচে read latency দেয়।

১. সমস্যা বোঝা (Requirements)

Functional Requirements:

• get(key) ও set(key, value)—মূল key-value operation।
• expire(key, ttl)—key-এর time-to-live সেট করা।
• একাধিক data type সাপোর্ট: string, list, hash, set, sorted set।
• মেমরি ভরে গেলে eviction policy অনুযায়ী key বাদ দেওয়া।

Non-functional Requirements:

• Low latency: read/write ১ ms-এর কম (single-digit millisecond)।
• High throughput: সেকেন্ডে লক্ষ লক্ষ operation।
• Scalable: একটা মেশিনের RAM ছাড়িয়ে গেলে অনেক node-এ ছড়ানো (sharding)।
• High availability: একটা node পড়ে গেলেও cache চালু থাকা (replication)।
• Durability (optional): restart-এ ডেটা ফিরে পাওয়া (persistence)।

২. স্কেল আন্দাজ (Estimation)

ধরি: 100 মিলিয়ন active key
গড় value সাইজ: 1 KB

মোট মেমরি (raw):
  100,000,000 × 1 KB = 100 GB

overhead (key, pointer, metadata ~30%):
  100 GB × 1.3 ≈ 130 GB

একটা cache node-এ ধরি 64 GB usable RAM
দরকারি node সংখ্যা: 130 / 64 ≈ 3 (shard) → safety-তে 4-6 node

read QPS ধরি: 1,000,000 reads/সেকেন্ড
write QPS ধরি: 100,000 writes/সেকেন্ড  (10:1 read-heavy)

একটা Redis node সহজে 100k+ ops/সেকেন্ড দেয়
  → 1M read হ্যান্ডেল করতে ~10+ node বা read replica

সংখ্যাগুলো দেখাচ্ছে—single node যথেষ্ট না; sharding ও replication দুটোই লাগবে।

৩. API ডিজাইন

get(key: string) -> value | null
set(key: string, value: bytes, ttlSeconds: int = 0) -> OK
del(key: string) -> int            # কতগুলো key মুছল
expire(key: string, ttlSeconds: int) -> bool
incr(key: string) -> int           # atomic counter

# data structure specific
lpush(key, value) / rpush(key, value)
hset(key, field, value) / hget(key, field)
zadd(key, score, member)           # sorted set

প্রতিটা operation atomic—Redis single-threaded command execution দিয়ে এটা নিশ্চিত করে (concurrency complexity ছাড়াই)।

৪. ডেটা মডেল

Redis মূলত একটা বিশাল hash table (dictionary), যার প্রতিটা value আবার একটা নির্দিষ্ট data structure।

Data Type	অভ্যন্তরীণ structure	ব্যবহার
String	SDS (simple dynamic string)	cache value, counter
List	quicklist (linked list of arrays)	queue, recent items
Hash	hashtable / ziplist	object/field map
Set	hashtable / intset	unique members, tags
Sorted Set	skiplist + hashtable	leaderboard, ranking

Storage choice কেন in-memory? মূল target হলো latency—RAM access ~100 ns, SSD ~100 μs, network DB ~1-10 ms। তাই প্রধান store RAM-এ, আর persistence শুধু durability/restart-এর জন্য ডিস্কে (RDB/AOF)।

প্রতিটা key-এর সাথে একটা optional expiry timestamp থাকে, যা আলাদা একটা expires dictionary-তে রাখা হয়।

৫. হাই-লেভেল ডিজাইন

Client → Cache Cluster → (miss হলে) → Database। মূল component:

1. Client library / proxy: key দেখে কোন shard-এ যাবে তা ঠিক করে (consistent hashing)।
2. Cache nodes (shards): প্রতিটা node মোট keyspace-এর একটা অংশ ধরে রাখে।
3. Replica nodes: প্রতিটা primary-র এক বা একাধিক replica—read scaling ও failover-এর জন্য।
4. Eviction engine: memory limit ছাড়ালে LRU/LFU অনুযায়ী key বাদ দেয়।
5. Persistence engine: RDB snapshot ও AOF log ডিস্কে লেখে।

Read flow (cache-aside pattern):

1. App get(key) কল করে → cache-এ hit হলে value ফেরত (দ্রুত)।
2. Miss হলে → DB থেকে পড়ে → cache-এ set করে → ফেরত।

Write flow: DB-তে লেখার পর cache-এ key invalidate বা update (write-through/write-around অনুযায়ী)।

৬. গভীরে (Deep Dive)

৬.১ Eviction Policy (LRU)

RAM সীমিত—maxmemory ছাড়ালে কোন key ফেলব? সবচেয়ে জনপ্রিয় LRU (Least Recently Used): যেটা সবচেয়ে আগে ব্যবহার হয়েছিল, সেটা বাদ।

• নিখুঁত LRU চাইলে প্রতিটা access-এ একটা doubly-linked list update করতে হয়—কিন্তু এতে memory ও CPU overhead।
• Redis তাই approximate LRU ব্যবহার করে: কয়েকটা key random sample করে, তাদের মধ্যে সবচেয়ে পুরোনো access timestamp-ওয়ালাটা বাদ দেয়। প্রতিটা key-তে একটা ছোট LRU clock field রাখে। এতে প্রায়-সঠিক ফল আসে অনেক কম খরচে।
• বিকল্প: LFU (Least Frequently Used)—কতবার access হয়েছে তার উপর ভিত্তি করে; hot key বেশি, একবারের spike কম।

৬.২ Persistence: RDB vs AOF

In-memory cache restart হলে ডেটা হারায়। দুটো persistence কৌশল:

• RDB (snapshot): নির্দিষ্ট সময় অন্তর পুরো dataset একটা compact binary file-এ dump। দ্রুত restart, ছোট ফাইল—কিন্তু দুই snapshot-এর মাঝের ডেটা হারাতে পারে (data loss window)।
• AOF (Append Only File): প্রতিটা write command log-এ append। restart-এ command replay করে state পুনর্গঠন। কম data loss (fsync policy-র উপর নির্ভর: every-second সাধারণ), কিন্তু ফাইল বড় ও replay ধীর। সময়ে সময়ে AOF rewrite করে compact করা হয়।

Production-এ প্রায়ই দুটো একসাথে চলে: দ্রুত restart-এর জন্য RDB base + শেষ মুহূর্তের ডেটার জন্য AOF।

৬.৩ Sharding via Consistent Hashing

ডেটা এক node-এ ধরে না—তাই অনেক node-এ ভাগ করতে হয়। সরল উপায় hash(key) % N, কিন্তু এতে N বদলালে (node যোগ/বাদ) প্রায় সব key পুনর্বণ্টন হয় → বিশাল cache miss storm।

Consistent hashing এর সমাধান:

• সব node-কে একটা কল্পিত বৃত্তে (hash ring) বসাও।
• প্রতিটা key-ও ring-এ hash হয়; ঘড়ির কাঁটার দিকে প্রথম যে node পাওয়া যায়, key সেখানে যায়।
• নতুন node যোগ হলে শুধু তার পরবর্তী segment-এর key সরে—গড়ে K/N key, পুরোটা নয়।
• Virtual nodes (একই physical node-এর অনেক point ring-এ) ব্যবহার করে load সমানভাবে ছড়ানো হয়, যাতে কোনো একটা node hotspot না হয়।

Redis Cluster অবশ্য একটু ভিন্ন—16384টা hash slot ব্যবহার করে, প্রতিটা key CRC16(key) % 16384 দিয়ে একটা slot-এ পড়ে, আর slot-গুলো node-দের মধ্যে ভাগ। ধারণাটা একই: rebalancing সস্তা রাখা।

৭. বটলনেক ও স্কেলিং

• Cache Stampede (Thundering Herd): একটা hot key expire হলে হাজার request একসাথে miss → সবাই DB-তে ঝাঁপায়। সমাধান:
  • Lock / single-flight: শুধু একটা request DB থেকে আনে, বাকিরা অপেক্ষা করে।
  • Stale-while-revalidate: expire হলেও পুরোনো value কিছুক্ষণ serve করো, পেছনে async refresh।
  • Jittered TTL: সব key একসাথে expire না করিয়ে TTL-এ random jitter যোগ করো।
• Hot key: একটা key-তে অস্বাভাবিক traffic এক node-কে ডুবিয়ে দেয়। সমাধান: client-side local cache, বা key replicate করে ছড়ানো।
• Cache penetration: যে key DB-তেই নেই তা বারবার খোঁজা (সব miss)। সমাধান: null value cache করা, বা Bloom filter দিয়ে আগেই বাদ।
• Hot shard: uneven key distribution। সমাধান: virtual node দিয়ে balance।
• Failover: primary পড়লে replica-কে promote (Redis Sentinel/Cluster gossip)। তবে async replication-এ promotion-এ সামান্য data loss সম্ভব।

৮. সারসংক্ষেপ

একটা distributed cache-এর মেরুদণ্ড পাঁচটা সিদ্ধান্ত: in-memory data structure, eviction (approximate LRU/LFU), persistence (RDB snapshot + AOF log), replication (HA ও read scaling), আর sharding (consistent hashing/hash slot)। আর কখনো ভুলো না—cache হলো accelerator, source of truth নয়; তাই stampede ও invalidation কৌশল ঠিক রাখাই আসল পরীক্ষা।