Storage engine — B-tree বনাম LSM-tree, WAL, row বনাম column store

১ · Storage engine কী — আর কেন এর নকশাই গতি ঠিক করে

পাড়ার মুদি দোকানির তিনটি কাজ: মাল তাকে রাখা, খদ্দের চাইলে দ্রুত খুঁজে দেওয়া, আর হিসাব যেন বিদ্যুৎ গেলেও হারিয়ে না যায়। মাল কীভাবে সাজানো, তা-ই ঠিক করে কাজ কত দ্রুত হবে।

Database-এর ভেতরে এই দোকানির নাম storage engine. SQL বোঝা আর query-র পরিকল্পনা ওপরের স্তরের কাজ; কিন্তু ডেটা ডিস্কের কোথায়, কোন আকারে বসবে, কীভাবে খোঁজা হবে আর crash-এর পরে কীভাবে ফিরবে — সে সিদ্ধান্ত engine-এর। একই MySQL-এ আলাদা engine বসানো যায় (InnoDB, বা RocksDB-ভিত্তিক MyRocks); MongoDB-র ডিফল্ট engine হলো WiredTiger. Engine বদলালে SQL একই থাকে, অথচ লেখার গতি, ডিস্কের খরচ আর p99 latency কয়েক গুণ বদলে যেতে পারে।

যন্ত্রের সত্য — random বনাম sequential

Engine-এর নকশা বুঝতে তিনটি সংখ্যার মাত্রা মনে রাখুন (পর্ব ৩-এর latency-র মই; বিস্তারিত Computer Architecture · মেমরি হায়ারার্কি-তে)। সংখ্যাগুলো মোটামুটি; যন্ত্র আর প্রজন্মভেদে কয়েক গুণ আলাদা হয়।

একটি হিসাব: ধরা যাক ১ GiB (২^৩০ byte) ডেটা ৪ KiB-র টুকরোয় পড়তে হবে — ২,৬২,১৪৪টি টুকরো। HDD-তে প্রতিটি random I/O-তে ১০ ms ধরলে প্রায় ২,৬২১ সেকেন্ড (৪৪ মিনিট); টানা পড়লে (sequential I/O, সেকেন্ডে ২০০ MB) মাত্র ৫.৪ সেকেন্ড — প্রায় ৪৯০ গুণ কম। SSD-তে (random ১০০ µs, টানা ৩ GB/s) ২৬ সেকেন্ড বনাম ০.৩৬ সেকেন্ড — ফারাক কমে প্রায় ৭০ গুণে, তবু থাকে।

ডেটাবেস ডিস্কের সাথে লেনদেন করে নির্দিষ্ট মাপের ব্লকে — page, সাধারণত ৪ থেকে ১৬ KB (ডিফল্টে SQLite-এ ৪ KB, PostgreSQL-এ ৮ KB, InnoDB-তে ১৬ KB). সারি ১০০ byte হলেও ডিস্ক থেকে আসে পুরো page; RAM-এ তার কপি থাকে buffer pool-এ, database-এর নিজস্ব cache.

২ · তিন রকম খরচ — read, write আর space amplification

Engine তুলনার সবচেয়ে কাজের ভাষা হলো amplification — আপনি যতটুকু চাইলেন, engine-কে তার কত গুণ কাজ করতে হলো।

বাস্তবে buffer pool অনেকটা বাঁচায়: একই page-এ ৫০টি বদল জমিয়ে একবার লিখলে ১৬৪ গুণ নেমে আসে প্রায় ৩.৩ গুণে, যদিও এলোমেলো key-তে জমানোর সুযোগ কম। SSD-র ভেতরেও আলাদা একটি write amplification আছে (ভাবনার প্রশ্ন ৩) — তাই এটি গতি, খরচ আর যন্ত্রের আয়ু, তিনটিরই প্রশ্ন।

RUM conjecture — তিনটি একসাথে কমানো যায় না

২০১৬ সালে Manos Athanassoulis ও সহকর্মীরা (EDBT সম্মেলনের প্রবন্ধ) একটি পর্যবেক্ষণকে নাম দেন RUM conjecture — Read, Update, Memory (জায়গা): কোনো access method যদি তিনটির দুটির ঊর্ধ্বসীমা বেঁধে দেয়, তাহলে তৃতীয়টির একটি নিম্নসীমা অনিবার্য। এটি গাণিতিক প্রমাণিত উপপাদ্য নয়, “conjecture” — কিন্তু বাস্তবের প্রতিটি নকশায় খাটে। দুই চরম উদাহরণে দেখুন:

পর্বের বাকিটা এই টেবিলের শেষ দুই সারির বিস্তার। কোনো engine “সেরা” নয়; প্রশ্ন হলো আপনার access pattern-এ কোন খরচ সবচেয়ে দামি — read:write ratio, key এলোমেলো না ক্রমিক, range query লাগে কি না, আর টানাটানি ডিস্কে না RAM-এ।

৩ · Write-ahead log — আগে খাতায়, পরে তাকে

মুদি দোকানি বাকির খাতায় আগে লেখেন “রহিম — ২ কেজি চাল, ১৫০ টাকা”, তারপর ধীরেসুস্থে তাকের হিসাব মেলান। মাঝপথে বিদ্যুৎ গেলেও খাতা দেখে বাকি কাজ শেষ করা যায়; আর খাতায় লেখা সহজ, কারণ সবসময় শেষ লাইনে।

Database-এর খাতার নাম write-ahead log (WAL), আর নিয়মটি এক লাইনের: কোনো বদল ডেটা-ফাইলে পৌঁছানোর আগে তার বিবরণ log-এ টেকসইভাবে লেখা থাকতে হবে, আর commit-এর log record ডিস্কে স্থায়ী হলে তবেই commit সফল। লাভ তিনটি:

• Durability সস্তায়: log-এ লেখা শুধু ফাইলের শেষে যোগ (append-only) — sequential I/O; আসল page পরে, অনেক বদল জমিয়ে লেখা যায়।
• Crash recovery: চালু হওয়ার সময় engine শেষ checkpoint থেকে log পড়ে, ডেটা-ফাইলে না-পৌঁছানো বদল আবার করে (redo) আর অসম্পূর্ণ transaction উল্টে দেয় (undo); checkpoint তাই recovery-র সময়ের সীমা টানে।
• বাড়তি উপহার: একই log পাঠিয়ে replica তৈরি করা যায় (পর্ব ২২), log পড়ে অন্য সিস্টেমে বদলের ধারা পাঠানো যায় (পর্ব ৩৩, log-ভিত্তিক streaming), আর log-কেই মূল সত্য ধরার নকশা আসবে পর্ব ৩৫-এ (event sourcing).

PostgreSQL-এর WAL, InnoDB-র redo log, SQLite-এর WAL মোড, আর LSM-tree-এর “commit log” — নাম আলাদা, ধারণা এক। File system-ও একই কৌশলে metadata রক্ষা করে: Operating Systems · crash consistency আর journaling. Log record, LSN আর ARIES-এর তিন ধাপের পুরো বিবরণ পাবেন DBMS · Recovery — log, WAL, checkpoint আর ARIES-এ; এখানে আমরা দেখব নকশার সংখ্যাগুলো।

fsync-এর দাম আর group commit

অ্যাপ write() করলে OS ডেটা প্রথমে নিজের page cache-এ রাখে; ডিস্কে পৌঁছানোর নিশ্চয়তা দেয় fsync (বা fdatasync). fsync ধীর: সাধারণ SSD বা HDD-তে প্রায় ০.১ থেকে ১০ ms; বিদ্যুৎ-বিভ্রাটে সুরক্ষিত cache-ওয়ালা enterprise SSD-তে অনেক কম। ধরা যাক একটি fsync-এ ২ ms লাগে।

৪ · B-tree পরিবার — page, fan-out আর উচ্চতা

একটি ঠিকানা খোঁজার কথা ভাবুন: আগে বিভাগ (৮টির একটি), তারপর জেলা, তারপর উপজেলা, তারপর রাস্তা — চার-পাঁচ ধাপেই দেশের যেকোনো বাড়ি। B-tree ঠিক এই কৌশল: প্রতিটি ধাপে দুটির একটি নয়, কয়েকশো শাখার একটি।

ডেটাবেসে যা চলে তা মূলত B+-tree: প্রতিটি node একটি page; internal node-এ শুধু পথ দেখানোর key আর child-এর ঠিকানা; ডেটা বা সারির ঠিকানা থাকে leaf-এ, আর leaf-গুলো শিকলে বাঁধা — range query মানে একবার নেমে শিকল ধরে হাঁটা। একটি page-এ কতগুলো child ধরে, তার নাম fan-out.

কেন ৭০%? এলোমেলো insert-এ ভরা page দুই ভাগ হয়, নতুন page শুরু করে অর্ধেক ভরা অবস্থায়; Andrew Yao-র ১৯৭৮ সালের বিশ্লেষণে গড় ভরাট প্রায় ln 2 ≈ ৬৯%. নিচের হিসাবযন্ত্রে page size, key আর fill বদলে চালাতে পারেন:

// B+-tree: how tall is the tree, and how many page reads does one lookup cost?
// Assumptions (change them): key 8 bytes (BIGINT), pointer 8 bytes, pages ~70% full.
const KEY = 8, PTR = 8, FILL = 0.7;
const fanout = (page) => Math.floor((page * FILL) / (KEY + PTR));
function height(n, f) {                      // levels, leaf included: smallest h with f^h >= n
  let h = 1, cap = f;
  while (cap < n) { cap *= f; h++; }
  return h;
}
function levelBytes(n, f, page) {            // [leaf level, all levels above it] in bytes
  let pages = Math.ceil(n / f), upper = 0;
  const leaf = pages;
  while (pages > 1) { pages = Math.ceil(pages / f); upper += pages; }
  return [leaf * page, upper * page];
}
const size = (b) => b >= 2 ** 30 ? (b / 2 ** 30).toFixed(1) + " GB" : (b / 2 ** 20).toFixed(2) + " MB";
console.log("check: fan-out 500, 3 levels -> 500^3 = " + (500 ** 3).toLocaleString("en-US") + " keys");
const F = [500, fanout(4096), fanout(8192), fanout(16384)];
console.log("fan-out at 70% fill: 4 KB page " + F[1] + ", 8 KB " + F[2] + ", 16 KB " + F[3]);
console.log("\n     N  h(f=500)  h(4 KB)  h(8 KB)  h(16 KB)   16 KB: leaf level  levels above");
for (let e = 3; e <= 10; e++) {
  const n = 10 ** e, [leaf, upper] = levelBytes(n, F[3], 16384);
  console.log(("10^" + e).padStart(6) + F.map((f, i) => String(height(n, f)).padStart(i ? 9 : 10)).join("") +
    size(leaf).padStart(19) + size(upper).padStart(14));
}
console.log("\nI/O per lookup: h page reads if nothing is cached; 1 (the leaf) if the levels above sit in RAM");

check: fan-out 500, 3 levels -> 500^3 = 125,000,000 keys
fan-out at 70% fill: 4 KB page 179, 8 KB 358, 16 KB 716

     N  h(f=500)  h(4 KB)  h(8 KB)  h(16 KB)   16 KB: leaf level  levels above
  10^3         2        2        2        2            0.03 MB       0.02 MB
  10^4         2        2        2        2            0.22 MB       0.02 MB
  10^5         2        3        2        2            2.19 MB       0.02 MB
  10^6         3        3        3        3           21.83 MB       0.05 MB
  10^7         3        4        3        3          218.23 MB       0.33 MB
  10^8         3        4        4        3             2.1 GB       3.08 MB
  10^9         4        4        4        4            21.3 GB      30.55 MB
 10^10         4        5        4        4           213.1 GB     305.25 MB

I/O per lookup: h page reads if nothing is cached; 1 (the leaf) if the levels above sit in RAM

এবার একটি খোঁজ ধাপে ধাপে — একটি কাল্পনিক mobile wallet সেবার ১০ কোটি account, primary key দিয়ে:

লেখা — জায়গায় বদল আর page split

B-tree-তে একটি সারি বদলাতে engine ওপরের পথেই leaf-এ নামে, page-টি buffer pool-এ এনে জায়গায় বদলায় (in-place update), বিবরণ WAL-এ লেখে, আর পরে পুরো page ডিস্কে ফেরত লেখে। Leaf ভরে গেলে page split: অর্ধেক entry নতুন page-এ, বাবার node-এ একটি নতুন key; বাবাও ভরা থাকলে split ওপরে ছড়ায়, আর root ভাঙলে গাছ এক স্তর উঁচু হয়।

• ক্রমিক key (auto-increment, সময়-ক্রমের ID): সব insert ডানতম leaf-এ — split সস্তা, cache-এ গরম একটি-দুটি page.
• এলোমেলো key (যেমন random UUID): insert ছড়ায় সব leaf-এ — বেশি split, অর্ধেক-ভরা page, বড় টেবিলে প্রায় প্রতিটি insert-এ একটি cache miss. তাই সময়-ক্রমের ID (২০২৪ সালের RFC 9562-এর UUIDv7, বা Snowflake-ধাঁচের ID — পর্ব ২৩) জনপ্রিয় হচ্ছে।
• প্রতিটি secondary index একটি আলাদা B-tree: ৫টি index-ওয়ালা টেবিলে একটি insert মানে ৬টি গাছে লেখা। InnoDB-র clustered নকশায় সারি থাকে primary key-এর গাছের leaf-এ, আর secondary index রাখে primary key; PostgreSQL-এ সারি আলাদা heap ফাইলে, index রাখে তার ঠিকানা (ভাবনার প্রশ্ন ২)।

Insert-delete-এর অ্যালগরিদম আর উচ্চতার সীমার প্রমাণ পাবেন DBMS · Index — B+ tree, hash আর bitmap আর DSA · B-tree আর B+ tree-এ; composite আর covering index বাছাই পর্ব ২১-এ।

নিজের চোখে — SQLite, একটি B-tree storage engine

এই পাতার SQLite চলে ব্রাউজারের memory-তে; এতে প্রতিটি টেবিল আর প্রতিটি index একটি করে B-tree. নিচের কোড WAL-এর সেটিং দেখে, ৫০,০০০টি account বানায়, তারপর দেখে কোন খোঁজ কোন গাছ ধরে যায়:

PRAGMA journal_mode;
PRAGMA journal_mode = WAL;
PRAGMA synchronous;
PRAGMA page_size;
CREATE TABLE accounts (
  id      INTEGER PRIMARY KEY,
  wallet  TEXT NOT NULL,
  balance INTEGER NOT NULL
);
WITH RECURSIVE seq(n) AS (
  SELECT 1 UNION ALL SELECT n + 1 FROM seq WHERE n < 50000
)
INSERT INTO accounts
SELECT n, 'W' || printf('%07d', (n * 7919) % 10000000), (n * 37) % 100000
FROM seq;
PRAGMA page_count;
EXPLAIN QUERY PLAN SELECT balance FROM accounts WHERE id = 31337;
EXPLAIN QUERY PLAN SELECT id FROM accounts WHERE wallet = 'W8157703';
CREATE UNIQUE INDEX idx_accounts_wallet ON accounts(wallet);
EXPLAIN QUERY PLAN SELECT id FROM accounts WHERE wallet = 'W8157703';
SELECT id, wallet, balance FROM accounts WHERE wallet = 'W8157703';
PRAGMA page_count;

৫ · LSM-tree — জমিয়ে রাখা, সাজিয়ে নামানো, পরে মেলানো

ডাকঘরে প্রতিটি চিঠি আসামাত্র গুদামের ঠিক তাকে রাখতে দৌড়ালে কর্মীর দিন শেষ। তার বদলে চিঠি জমে টেবিলের ট্রেতে; ট্রে ভরলে এলাকা ধরে সাজিয়ে একটি বস্তায় বাঁধা হয়, আর রাতে কয়েকটি ছোট বস্তা মিলিয়ে একটি বড় সাজানো বস্তা। চিঠি খুঁজতে হলে আগে ট্রে, তারপর নতুন বস্তা থেকে পুরোনো বস্তা।

১৯৯৬ সালে Patrick O'Neil, Edward Cheng, Dieter Gawlick আর Elizabeth O'Neil-এর প্রবন্ধ “The Log-Structured Merge-Tree” (Acta Informatica) এই কৌশলটি দাঁড় করায়: LSM-tree. মূল চিন্তা — ডিস্কে পুরোনো জায়গায় কখনো বদল নয়; লেখা জমে RAM-এ, বড় সাজানো টুকরো হয়ে ক্রমিকভাবে ডিস্কে নামে, আর পেছনে টুকরোগুলো মিলিয়ে গোছানো হয়। Google-এর Bigtable (২০০৬) memtable আর SSTable নাম দুটি জনপ্রিয় করে; আজ LevelDB, RocksDB, Cassandra, HBase আর ScyllaDB এই পরিবারের।

চারটি অংশ

• WAL: প্রতিটি লেখা আগে log-এর শেষে (অংশ ৩), যাতে crash-এ RAM-এর ডেটা ফেরানো যায়।
• Memtable: RAM-এ key-এর ক্রমে সাজানো কাঠামো (LevelDB আর RocksDB-র ডিফল্ট একটি skip list — DSA · treap আর skip list). সীমা ছুঁলে এটি immutable memtable হয়, নতুন খালি memtable লেখা নেয়।
• SSTable (sorted string table): immutable memtable এক টানে ডিস্কে নামে একটি অপরিবর্তনীয়, সাজানো ফাইল হয়ে — flush; সাথে ছোট একটি index আর একটি Bloom filter.
• Compaction: পেছনে কয়েকটি SSTable merge sort-এর মতো মিলিয়ে (DSA · merge sort) নতুন SSTable লেখা — প্রতিটি key-এর নতুনতম মান রেখে; তারপর পুরোনো ফাইল মোছা।

পুরোনো ফাইল বদলানোই যায় না, তাহলে delete? একটি বিশেষ লেখা দিয়ে — tombstone, “এই key মৃত” চিহ্ন। পড়ার সময় tombstone আগে মিললে পুরোনো মান উপেক্ষা হয়। Tombstone ফেলা যায় কেবল তখন, যখন compaction নিশ্চিত যে নিচের কোনো স্তরে ওই key-এর পুরোনো কপি নেই — নইলে মুছে ফেলা ডেটা আবার “জেগে” ওঠে। Replica থাকলে আরও সাবধানতা: Cassandra tombstone একটি grace সময় রাখে (লেখার সময়ের ডিফল্ট ১০ দিন), যাতে ফিরে আসা কোনো replica পুরোনো মান আবার না ছড়ায়।

নিচে একটি লেখার পুরো যাত্রা। Memtable-এর সীমা ইচ্ছা করে মাত্র ৪টি key; আসল engine-এ memtable সাধারণত কয়েক দশ MB.

পড়ার পথ বনাম লেখার পথ

লেখার পথ ছোট: WAL-এ যোগ আর memtable-এ বসানো; কোনো পুরোনো page পড়তে হয় না। পড়ার পথ লম্বা: memtable, immutable memtable, তারপর SSTable-গুলো নতুন থেকে পুরোনো — প্রথম মিলেই থামা। যে key কোথাও নেই, তার জন্য সব জায়গা খুঁজে তবে “নেই”।

এখানে কাজে আসে প্রতিটি SSTable-এর Bloom filter — একটি ছোট bit array, যা বলে “এই key এই ফাইলে অবশ্যই নেই” বা “হয়তো আছে”; “নেই” বললে তা নিশ্চিত। প্রতি key-এ ১০ bit দিলে ভুলের হার প্রায় ০.৮%: ১০টি SSTable-এ একটি অনুপস্থিত key-এর জন্য ১০টির বদলে গড়ে মাত্র প্রায় ০.০৮টি অকারণ ডিস্ক-পড়া। দাম RAM: ১০০ কোটি key-এ প্রায় ১.২৫ GB. সূত্র আর প্রমাণ আসবে পর্ব ৪৫-এ (Probabilistic data structure — Bloom filter, count-min sketch আর HyperLogLog). Range query-তে Bloom filter সাহায্য করে না।

এবার পুরো কৌশলটি একটি ছোট simulator-এ চালান — stepper-এর মতোই ১০টি লেখা (একটি delete-সহ), প্রতিটি অবস্থা, ৫টি খোঁজ আর amplification-এর হিসাব:

// Tiny LSM-tree: write -> WAL + memtable (RAM) -> sorted runs (SSTables) -> compaction.
const LIMIT = 4, TOMB = null;               // flush when the memtable holds 4 keys
let mem = new Map(), runs = [], io = { user: 0, wal: 0, flush: 0, compact: 0 };  // runs[0] = newest
const sorted = (m) => [...m].sort((a, b) => (a[0] < b[0] ? -1 : 1));
function put(k, v) {                        // v === TOMB means "delete k"
  io.user++; io.wal++; mem.set(k, v);       // 1) append to WAL  2) insert into memtable
  if (mem.size >= LIMIT) { runs.unshift(sorted(mem)); io.flush += mem.size; mem = new Map(); }
}
function get(k) {                           // memtable first, then runs newest -> oldest
  if (mem.has(k)) return [mem.get(k), 1];
  for (let i = 0; i < runs.length; i++) {   // (a real SSTable: index block + binary search)
    const hit = runs[i].find((e) => e[0] === k); if (hit) return [hit[1], i + 2]; }
  return [TOMB, runs.length + 1];
}
function merged() {                         // newest version of every key, tombstones dropped
  const m = new Map(); for (const run of [...runs].reverse()) for (const [k, v] of run) m.set(k, v);
  return sorted(m).filter((e) => e[1] !== TOMB);
}
const compact = () => { runs = [merged()]; io.compact += runs[0].length; };
const txt = (r) => r.map(([k, v]) => k + "=" + (v === TOMB ? "(tomb)" : v)).join(" ");
function show(title) {
  console.log("== " + title + "\n  memtable: " + txt(sorted(mem)));
  runs.forEach((r, i) => console.log("  run " + (i + 1) + ": " + txt(r)));
  const disk = runs.flat().length, live = merged().length, sst = io.flush + io.compact;
  console.log("  on disk " + disk + " entries for " + live + " live keys -> space amp " + (disk / live).toFixed(2));
  for (const k of ["u2", "u1", "u4", "u3", "u9"]) { const [v, n] = get(k);
    console.log("  get " + k + " -> " + (v === TOMB ? "not found" : v) + "  (looked in " + n + ")"); }
  console.log("  writes: user " + io.user + ", WAL " + io.wal + ", SSTable " + sst +
    " -> write amp " + (sst / io.user).toFixed(1) + " (with WAL " + ((sst + io.wal) / io.user).toFixed(1) + ")");
}
"u1=Rahim u2=Karim u3=Salma u4=Nila u2=Karim2 u3 u5=Rafi u1=Rahim2 u6=Tania u2=Karim3".split(" ")
  .forEach((w) => { const [k, v] = w.split("="); put(k, v === undefined ? TOMB : v); });  // "u3" = delete
show("after 10 writes (2 flushes)");
compact(); show("after compaction");

== after 10 writes (2 flushes)
  memtable: u2=Karim3 u6=Tania
  run 1: u1=Rahim2 u2=Karim2 u3=(tomb) u5=Rafi
  run 2: u1=Rahim u2=Karim u3=Salma u4=Nila
  on disk 8 entries for 4 live keys -> space amp 2.00
  get u2 -> Karim3  (looked in 1)
  get u1 -> Rahim2  (looked in 2)
  get u4 -> Nila  (looked in 3)
  get u3 -> not found  (looked in 2)
  get u9 -> not found  (looked in 3)
  writes: user 10, WAL 10, SSTable 8 -> write amp 0.8 (with WAL 1.8)
== after compaction
  memtable: u2=Karim3 u6=Tania
  run 1: u1=Rahim2 u2=Karim2 u4=Nila u5=Rafi
  on disk 4 entries for 4 live keys -> space amp 1.00
  get u2 -> Karim3  (looked in 1)
  get u1 -> Rahim2  (looked in 2)
  get u4 -> Nila  (looked in 2)
  get u3 -> not found  (looked in 2)
  get u9 -> not found  (looked in 2)
  writes: user 10, WAL 10, SSTable 12 -> write amp 1.2 (with WAL 2.2)

Compaction-এর দুই প্রধান নীতি

কোন ফাইল কখন কার সাথে মিলবে — এই নীতিই LSM-এর read, write আর space খরচ ঠিক করে।

এখানেই RUM সবচেয়ে স্পষ্ট: শুধু compaction-এর নীতি বদলে খরচ এক দিক থেকে আরেক দিকে সরে, তিনটি একসাথে কমে না। অনেক engine মাঝামাঝি নীতিও দেয় (ওপরের স্তরে size-tiered, নিচে leveled).

৬ · B-tree বনাম LSM-tree — কোন কাজে কোনটি

দুটি পরিবার পাশাপাশি দেখুন। বাঁয়ে একই key 42-এর খোঁজ আর বদল B+-tree-তে, ডানে একটি লেখা LSM-tree-তে কোথায় কোথায় যায়:

• লেখা-প্রধান, প্রায় শুধু যোগ (location ping, log, বার্তা, metrics) — LSM.
• পড়া-প্রধান, লেনদেন আর range query (হিসাব, অর্ডার, পণ্যের তালিকা) — B-tree-এর relational database.
• মাঝামাঝি: আধুনিক SSD-তে দুটোই যথেষ্ট ভালো; সিদ্ধান্ত আসে data model, transaction আর ops-এর অভিজ্ঞতা থেকে (পর্ব ২০), আর শেষ কথা বলে নিজের ধাঁচের benchmark.

তৃতীয় পথ — log আর memory-তে hash index

সবচেয়ে সরল টেকসই key-value store: ডিস্কে একটি append-only log, আর RAM-এ একটি hash table, যা মনে রাখে প্রতিটি key-এর সর্বশেষ মান log-এর কোন offset-এ। লেখা = log-এর শেষে যোগ + hash table হালনাগাদ; পড়া = offset ধরে ঠিক ১টি ডিস্ক-পড়া; পুরোনো segment পেছনে মিলিয়ে ছোট করা হয়। এই নকশার পরিচিত উদাহরণ Bitcask, যা ২০১০ সালের দিকে Riak database-এর জন্য বর্ণিত হয় (DSA · hash table).

এই hash index-এর সীমা দুটি। সব key RAM-এ ধরতে হবে: key গড়ে ২০ byte আর entry-প্রতি ঠিকানা-তথ্য ২০ byte ধরলে ১০ কোটি key-এ প্রায় ৪ GB RAM. আর hash ক্রম রাখে না, তাই range query চলে না। কম key, অনেক লেখা, শুধু point lookup — সেখানে এটি দারুণ সরল আর দ্রুত।

৭ · Row বনাম column store — OLTP আর OLAP

এতক্ষণের সব engine row store: একটি সারির সব কলাম একই page-এ পাশাপাশি — একটি অর্ডার পুরোটা পড়া-লেখার, অর্থাৎ OLTP-এর জন্য আদর্শ। কিন্তু “দুই বছরে জেলাভিত্তিক মোট বিক্রি”-র মতো OLAP প্রশ্নে দরকার কোটি সারির দু-তিনটি কলাম, অথচ row store-কে সব কলাম পড়তে হয়।

Column store প্রতিটি কলাম আলাদা ধারায় রাখে। লাভ তিনটি: শুধু দরকারি কলাম পড়া; একই ধরনের মান পাশাপাশি থাকায় চমৎকার compression — dictionary encoding (লম্বা মানের বদলে ছোট সংখ্যা), run-length encoding (“মান × কতবার”), bit-packing (যত bit লাগে ঠিক ততটুকু); আর vectorised execution — হাজারখানেক মানের দল ধরে একটি ছোট loop, যা CPU-র cache আর SIMD-এর (একটি নির্দেশে কয়েকটি মান) পক্ষে আদর্শ। নিচে একই প্রশ্ন দুই সাজানোয়:

id │ date       │ district │ amount │ channel
 1 │ 2025-01-03 │ Dhaka    │    500 │ app
 2 │ 2025-01-03 │ Khulna   │   1200 │ web
 3 │ 2025-01-04 │ Dhaka    │    300 │ app
 4 │ 2025-01-04 │ Sylhet   │    900 │ app

SELECT district, SUM(amount)
FROM sales GROUP BY district;

page 1: [1, 2025-01-03, Dhaka, 500, app]
        [2, 2025-01-03, Khulna, 1200, web]
page 2: [3, 2025-01-04, Dhaka, 300, app]
        [4, 2025-01-04, Sylhet, 900, app]
↑ উজ্জ্বল অংশটুকুই দরকার, বাকি সব পড়তে হলো

district: [Dhaka │ Khulna │ Dhaka │ Sylhet]
amount:   [500 │ 1200 │ 300 │ 900]
id:       [1 │ 2 │ 3 │ 4]           (বাদ)
date:     [2025-01-03 │ … ]         (বাদ)
channel:  [app │ web │ app │ app]   (বাদ)

অভিধান:   0 = Dhaka, 1 = Khulna, 2 = Sylhet
district: [0 │ 1 │ 0 │ 2]   প্রতিটি 2 bit
amount:   [500 │ 1200 │ 300 │ 900]
          প্রতিটি 11 bit (সর্বোচ্চ 2047)

loop: sum[code] += amount
(একসাথে হাজারখানেক মানের দলে)

এবার বড় পরিসরে হিসাব করুন: ১০ লাখ সারি, ৫০টি কলাম, প্রশ্নটি ছোঁয় মাত্র ২টি — district আর amount. প্রতিটি অনুমান কোডের মাথায় লেখা; বদলে চালিয়ে দেখুন:

// SELECT district, SUM(amount) FROM sales GROUP BY district  -- bytes read: row vs column store
// Assumptions: 1,000,000 rows, 50 columns, 8 bytes per raw value, 64 districts, amount 50..100,000
// taka; an RLE run = 1-byte code + 4-byte count. Real engines add headers and smarter codecs.
function rng(seed) {                                   // mulberry32: seeded, repeatable
  return () => { seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}
const N = 1e6, COLS = 50, W = 8, rand = rng(19);
const district = new Uint8Array(N), amount = new Uint32Array(N);
for (let i = 0; i < N; i++) { district[i] = Math.floor(rand() * 64); amount[i] = 50 + Math.floor(rand() * 99951); }
const bits = (max) => Math.ceil(Math.log2(max + 1));    // bits needed for values 0..max
const runs = (a) => { let r = 1; for (let i = 1; i < a.length; i++) r += a[i] !== a[i - 1]; return r; };
const dBits = bits(63), aBytes = (N * bits(100000)) / 8, sortedD = district.slice().sort();
const plans = [
  ["row store: all 50 columns", N * COLS * W],
  ["column store: 2 raw columns", 2 * N * W],
  ["+ dictionary district (" + dBits + " bits)", (N * dBits) / 8 + N * W],
  ["+ bit-packed amount (" + bits(100000) + " bits)", (N * dBits) / 8 + aBytes],
  ["  RLE district instead, unsorted", runs(district) * 5 + aBytes],
  ["  RLE district instead, sorted", runs(sortedD) * 5 + aBytes],
];
console.log("plan".padEnd(36) + "bytes read".padStart(12) + "share".padStart(8) + "smaller".padStart(9));
for (const [name, b] of plans)
  console.log(name.padEnd(36) + ((b / 1e6).toFixed(3) + " MB").padStart(12) +
    ((100 * b / plans[0][1]).toFixed(2) + "%").padStart(8) + ((plans[0][1] / b).toFixed(0) + "x").padStart(9));
console.log("RLE runs: unsorted " + runs(district) + ", sorted " + runs(sortedD));
const sum = new Float64Array(64);                       // the scan itself: one tight loop, 2 arrays
for (let i = 0; i < N; i++) sum[district[i]] += amount[i];
console.log("district 0 total " + sum[0].toLocaleString("en-US") + ", all " + sum.reduce((a, b) => a + b, 0).toLocaleString("en-US"));

plan                                  bytes read   share  smaller
row store: all 50 columns             400.000 MB 100.00%       1x
column store: 2 raw columns            16.000 MB   4.00%      25x
+ dictionary district (6 bits)          8.750 MB   2.19%      46x
+ bit-packed amount (17 bits)           2.875 MB   0.72%     139x
  RLE district instead, unsorted        7.047 MB   1.76%      57x
  RLE district instead, sorted          2.125 MB   0.53%     188x
RLE runs: unsorted 984457, sorted 64
district 0 total 778,971,071, all 49,985,788,669

বাস্তবের column store আরও কৌশল যোগ করে: প্রতিটি block-এর সর্বনিম্ন-সর্বোচ্চ মান রেখে অপ্রাসঙ্গিক block পুরো বাদ (zone map), আর সংকুচিত ডেটার ওপরেই হিসাব। দাম লেখায়: নতুন সারি মানে প্রতিটি কলামের ধারায় লেখা, আর সংকুচিত block বদলানো দামি — তাই লেখা জমিয়ে দলে দলে নেওয়া হয়, অনেকটা LSM-এর মতো। ClickHouse, DuckDB, Parquet ফাইল-ফরম্যাট আর বড় cloud warehouse-গুলো column-ভিত্তিক। Data warehouse-এর star schema আর ETL পাবেন DBMS · Data warehouse — OLAP, star schema আর ETL-এ; OLTP থেকে warehouse-এ ডেটার ধারা আসবে পর্ব ৩৩ আর ৩৬-এ।

৮ · In-memory database আর durability-র বিকল্প

সব ডেটা RAM-এ ধরে গেলে page, buffer pool আর ডিস্ক-পড়া অপ্রয়োজনীয় মনে হয়। In-memory database (যেমন Redis, বা গবেষণা থেকে জন্ম নেওয়া VoltDB) এভাবেই চলে: hash table, skip list-এর মতো RAM-বান্ধব কাঠামো, অনুরোধ মাইক্রোসেকেন্ডের ঘরে। কিন্তু RAM বিদ্যুৎ গেলে মুছে যায়, তাই প্রশ্ন থাকে: কতটুকু হারানো চলে, আর ফিরতে কত সময় লাগে?

Recovery-র সময়ও হিসাব করুন: ৫০ GB-র snapshot সেকেন্ডে ৫০০ MB হারে পড়তে লাগে ৫০ × ১০০০ ÷ ৫০০ = ১০০ সেকেন্ড, তারপর log-এর বাকিটা — এ সময় সার্ভিস হয়তো অনুরোধ নিতে পারে না। Redis-এর RDB snapshot আর AOF (appendfsync-এর always, everysec, no) এই আপসগুলোর বাস্তব রূপ; ডিফল্ট সংস্করণভেদে আলাদা, বিস্তারিত DBMS · Redis — in-memory key-value আর cache-এ।

৯ · AI-এর যুগে storage engine বাছাই যাচাই

“লেখা অনেক, কোন database নেব?” — AI প্রায়ই এক নিঃশ্বাসে বলে “Cassandra নিন, পাশে ClickHouse, সামনে Redis, মাঝে Kafka.” নামগুলো ভুল নয়, কিন্তু মূল প্রশ্ন বাদ পড়ে: পড়ার ধাঁচ, delete, compaction-এর জায়গা, crash-এ কী হারায়। সাধারণ ভুলগুলো:

প্রশ্ন ২-এর হিসাব নিজে করে রাখুন: ৫০,০০০ × ১০০ byte = সেকেন্ডে ৫ MB; দিনে ৫ × ৮৬,৪০০ = ৪,৩২,০০০ MB, অর্থাৎ ৪৩২ GB. Write amplification ১০ হলে ডিস্কে দিনে প্রায় ৪.৩২ TB — SSD-র আয়ুর হিসাবেও লাগবে। AI-এর সংখ্যা আলাদা হলে ভুলটি খুঁজুন।

AI-এর storage-পরিকল্পনা হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি কাজের read:write ratio, key-এর ধাঁচ আর range query লিখে মিলিয়েছি
• আকার, লেখার হার আর write amplification-এর অঙ্ক নিজে কষেছি; উচ্চতা f^h ≥ N দিয়ে মিলিয়েছি
• কোন সেটিংয়ে crash-এ কী হারায়, অফিসিয়াল documentation থেকে যাচাই করেছি
• Delete আর মেয়াদের নীতি, compaction-এর headroom আর write stall-এর alert আছে
• নিজের ডেটার ধাঁচে ছোট benchmark বা simulation চালিয়েছি — গড় নয়, p99 দেখেছি
• Failure-mode পর্যালোচনা: বিদ্যুৎ যাওয়া, ডিস্ক ভরা, replica একসাথে পড়া