Storage Engines (LSM-tree vs B-tree)
- ●Storage engine হলো ডাটাবেসের সেই অংশ যেটা ডাটা ডিস্কে লেখা ও পড়ার দায়িত্বে থাকে।
- ●B-tree in-place update করে এবং read-optimized; LSM-tree append-only লেখে আর write-optimized।
- ●Write-Ahead Log (WAL) দুই ক্ষেত্রেই durability নিশ্চিত করে crash থেকে recovery করতে।
সমস্যাটা কী?
ডাটাবেস ব্যবহার করার সময় আমরা সাধারণত INSERT, SELECT, UPDATE লিখি আর ভাবি ডাটা ম্যাজিকের মতো কোথাও সেভ হয়ে যাচ্ছে। কিন্তু ভিতরে একটা বড় চ্যালেঞ্জ লুকিয়ে আছে—ডিস্ক (HDD বা SSD) তুলনামূলকভাবে ধীর, আর random access সবসময় sequential access-এর চেয়ে ব্যয়বহুল।
ধরো তোমার একটা e-commerce সাইটে সেকেন্ডে হাজারো order আসছে (write), আবার একই সাথে ইউজাররা পুরোনো order খুঁজছে (read)। তুমি চাও write দ্রুত হোক, read দ্রুত হোক, ডাটা harddisk-এ নিরাপদ থাকুক, আর crash হলে কিছু হারিয়ে না যায়। এই সব একসাথে অপ্টিমাইজ করা কঠিন—একটা বাড়াতে গেলে আরেকটা কমে যায়।
এই trade-off সামলানোর দায়িত্ব নেয় storage engine। আর সবচেয়ে জনপ্রিয় দুটি design হলো B-tree এবং LSM-tree।
মূল ধারণা
Storage Engine হলো ডাটাবেসের নিচু স্তরের সেই উপাদান, যা ডাটা কীভাবে disk-এ সাজানো হবে, কীভাবে লেখা হবে এবং কীভাবে দ্রুত খুঁজে বের করা যাবে—এই সিদ্ধান্তগুলো নেয়।
একই SQL query চালালেও storage engine ভিন্ন হলে performance characteristics সম্পূর্ণ আলাদা হতে পারে। MySQL-এ যেমন তুমি InnoDB (B-tree) বা MyRocks (LSM-tree) বেছে নিতে পারো।
মূল পার্থক্য একটা প্রশ্নে: নতুন ডাটা কি জায়গায় বসিয়ে দেব (in-place), নাকি শেষে যোগ করে দেব (append)?
- B-tree: ডাটা একটা balanced tree-তে সাজানো থাকে। update করার সময় সঠিক page খুঁজে সেখানেই overwrite করা হয় (in-place update)।
- LSM-tree (Log-Structured Merge-tree): নতুন write প্রথমে memory-তে জমা হয়, তারপর disk-এ append-only ফাইল হিসেবে লেখা হয়। পুরোনো ভ্যালু পরে background-এ পরিষ্কার করা হয়।
কীভাবে কাজ করে
B-tree
B-tree ডাটাকে fixed-size page (সাধারণত ৪ KB বা ৮ KB) ভাগে disk-এ রাখে। প্রতিটি page-এ key এবং পরবর্তী page-এর pointer থাকে। গাছটি "balanced"—অর্থাৎ root থেকে যেকোনো leaf পর্যন্ত depth প্রায় সমান।
একটা key খুঁজতে root page থেকে শুরু করে সঠিক child page-এ নামতে থাকো। ১০ কোটি record হলেও সাধারণত ৩-৪টি page পড়লেই কাঙ্ক্ষিত data পাওয়া যায়, কারণ depth লগারিদমিক ভাবে বাড়ে।
Update-এর সময় সেই page-টা খুঁজে বের করে in-place লেখা হয়। কিন্তু এটাই risk—লেখার মাঝখানে crash হলে page অর্ধেক লেখা থাকতে পারে। তাই B-tree WAL ব্যবহার করে।
LSM-tree
LSM-tree-এর প্রবাহ এমন:
- Memtable: নতুন write প্রথমে memory-তে একটা sorted structure-এ যায়।
- WAL: একই সাথে disk-এ একটা log-এ append হয় (durability-র জন্য)।
- Flush: Memtable ভরে গেলে পুরোটা disk-এ একটা immutable sorted ফাইল—SSTable (Sorted String Table)—হিসেবে লেখা হয়।
- Compaction: সময়ের সাথে অনেক SSTable জমে। background process এগুলো merge করে, ডুপ্লিকেট আর deleted key সরিয়ে দেয়।
Read করার সময় আগে memtable দেখা হয়, তারপর নতুন থেকে পুরোনো SSTable। বেশি ফাইল হলে read ধীর হতে পারে—তাই Bloom filter ব্যবহার করা হয়, যা দ্রুত বলে দেয় কোনো key একটি SSTable-এ "নেই"।
তুলনামূলক টেবিল
| বৈশিষ্ট্য | B-tree | LSM-tree |
|---|---|---|
| Write pattern | In-place (random) | Append-only (sequential) |
| Write speed | মাঝারি | দ্রুত |
| Read latency | কম ও predictable | বেশি ও variable |
| Write amplification | কম | বেশি (compaction-এর জন্য) |
| Space usage | fragmentation থাকে | compaction-এর পরে compact |
| উদাহরণ | InnoDB, PostgreSQL | RocksDB, Cassandra, LevelDB |
কীভাবে কাজ করে: WAL
দুই engine-ই Write-Ahead Log ব্যবহার করে। নিয়মটা সহজ: আসল data structure পরিবর্তন করার আগে change-টা একটা append-only log-এ লিখে ফেলো। commit মানে WAL-এ লেখা সম্পন্ন। এরপর crash হলেও system restart করে WAL replay করে হারানো change ফিরিয়ে আনতে পারে।
ভাবো একটা মুদি দোকান। B-tree হলো এমন খাতা যেখানে প্রতিটা পণ্যের জন্য আলাদা পৃষ্ঠা নির্ধারিত—চাল আপডেট করতে চাইলে "চাল" পৃষ্ঠায় গিয়ে কেটে নতুন সংখ্যা বসাও (in-place)। খুঁজে পাওয়া সহজ, কিন্তু পৃষ্ঠা খুঁজে কাটাকাটি ধীর।
LSM-tree হলো এমন দোকানদার যে প্রতিটা লেনদেন শুধু খাতার শেষে লিখে যায়—"১০ কেজি চাল বিক্রি", "৫ কেজি চাল কেনা"। লেখা খুব দ্রুত (শুধু শেষে যোগ)। কিন্তু "এখন কত চাল আছে?" জানতে পুরো খাতা পড়তে হয়। তাই রাতে সে বসে হিসাব মিলিয়ে একটা পরিষ্কার summary বানায়—এটাই compaction।
প্রকারভেদ ও বাস্তব প্রয়োগ
কোন ডাটাবেস কোন engine ব্যবহার করে, জেনে রাখা ইন্টারভিউতে কাজে লাগে:
- B-tree based: PostgreSQL, MySQL (InnoDB), Oracle, SQL Server, MongoDB (WiredTiger ডিফল্টে B-tree)।
- LSM-tree based: Cassandra, ScyllaDB, RocksDB, LevelDB, HBase, MySQL (MyRocks engine), InfluxDB।
লক্ষণীয়—কোনো ডাটাবেস "ভালো" বা "খারাপ" নয়, বরং তাদের storage engine ভিন্ন trade-off-এর জন্য তৈরি।
কখন ব্যবহার করবে / করবে না
B-tree বেছে নাও যখন: read বেশি, low-latency consistent read দরকার, strong transactional guarantee (OLTP) লাগবে—যেমন banking, inventory।
LSM-tree বেছে নাও যখন: write খুব বেশি, time-series বা logging data, write throughput-ই মূল চাহিদা—যেমন IoT sensor data, event logging, message queue backing store।
LSM-tree-তে write amplification একটা বড় ফাঁদ। compaction বারবার একই ডাটা পুনরায় লেখে, ফলে SSD-তে প্রকৃত disk write তোমার application write-এর চেয়ে ১০ গুণও বেশি হতে পারে। এতে SSD-এর আয়ু কমে আর disk I/O budget দ্রুত শেষ হয়। compaction strategy (size-tiered vs leveled) ভুল হলে read latency-ও হঠাৎ লাফ দিতে পারে।
বাস্তব উদাহরণ
Facebook তাদের MySQL ডাটাবেসে storage খরচ আর write performance উন্নত করতে MyRocks (RocksDB-ভিত্তিক LSM engine) তৈরি করে InnoDB-এর বিকল্প হিসেবে। ফলাফল—একই data রাখতে প্রায় অর্ধেক disk space এবং বেশি write throughput, কারণ তাদের workload ছিল write-intensive।
অন্যদিকে একটা সাধারণ e-commerce অ্যাপ যেখানে product browsing (read) order placement-এর চেয়ে বহুগুণ বেশি, সেখানে PostgreSQL-এর B-tree engine বেশি উপযুক্ত—কারণ ইউজার product page লোডে predictable, দ্রুত read পায়।
ইন্টারভিউতে কেউ "Cassandra কেন write-এ এত fast?" জিজ্ঞেস করলে বলবে: "কারণ এটা LSM-tree ব্যবহার করে—write প্রথমে memtable + WAL-এ যায়, পরে SSTable হিসেবে sequential append হয়, কোনো random in-place update নেই। দাম দিতে হয় read latency আর compaction-জনিত write amplification দিয়ে।" এই এক বাক্যেই trade-off-টা বোঝানো যায়।
মূল শব্দ (Key Terms)
মিনি কুইজ
1. LSM-tree কোন ধরনের workload-এ সবচেয়ে ভালো পারফর্ম করে?
2. Write-Ahead Log (WAL) এর মূল উদ্দেশ্য কী?
3. B-tree সাধারণত কোন দিক থেকে LSM-tree-এর চেয়ে এগিয়ে?