স্টোরেজ — ডিস্ক, page, record আর buffer pool

১ · মেমোরির সিঁড়ি — কেন ডেটাবেস I/O গোনে

এতদিন আপনি SQL লিখেছেন, আর ডেটাবেস উত্তর দিয়েছে। পর্ব ৩-এ দেখেছেন, টেবিলের যৌক্তিক রূপ আর ডিস্কে রাখার physical রূপ আলাদা — internal schema. এবার সেই নিচের তলায় নামার পালা। কারণ একটি সহজ কথা: কোয়েরি ধীর না দ্রুত, তা প্রায় সবসময় ঠিক হয় ডেটা কোথা থেকে আসছে তা দিয়ে।

কম্পিউটারে ডেটা রাখার জায়গাগুলো একটি সিঁড়ির মতো — একে বলে memory hierarchy. ওপরে ছোট, দামি আর অতি দ্রুত; নিচে বড়, সস্তা আর ধীর। নিচের সংখ্যাগুলো আনুমানিক; যন্ত্রভেদে কয়েক গুণ এদিক-ওদিক হয়, কিন্তু মাত্রা (কত শূন্য) মোটামুটি এমনই:

RAM আর HDD-এর random পড়ার মধ্যে ব্যবধান পঞ্চাশ হাজার থেকে এক লাখ গুণ। তাই ডিস্ক-নির্ভর ডেটাবেসে CPU-র কাজ প্রায়ই নগণ্য, আসল খরচ ডিস্কের যাতায়াত। এই কারণে ডেটাবেসের বই আর পরের পর্বগুলো একটি সরল I/O cost model ব্যবহার করে: খরচ = কতগুলো page ডিস্ক থেকে পড়া বা ডিস্কে লেখা হলো। CPU-র হিসাব বাদ, মেমোরিতে থাকা page বিনা খরচে। মডেলটি স্থূল, কিন্তু দুটি পরিকল্পনার মধ্যে কোনটি ভালো, তা বলতে প্রায়ই যথেষ্ট — পর্ব ৪০–৪৩-এ index, join আর optimizer এই মাপকাঠিতেই তুলনা হবে।

২ · HDD আর SSD — random বনাম sequential

HDD (hard disk drive) একটি ঘুরন্ত চৌম্বক থালা, যার ওপর একটি বাহুর মাথায় পড়া-লেখার head. একটি নির্দিষ্ট জায়গা পড়তে তিনটি সময় লাগে:

1. Seek time — head-কে সঠিক বৃত্তাকার পথে (track) সরানো; সাধারণ ডেস্কটপ ডিস্কে গড়ে কয়েক ms, প্রায় ৪–৯ ms.
2. Rotational latency — থালা ঘুরে কাঙ্ক্ষিত অংশটি head-এর নিচে আসার অপেক্ষা। ৭২০০ rpm-এ এক পাক = ৬০ ÷ ৭২০০ সেকেন্ড ≈ ৮.৩৩ ms, গড়ে অর্ধেক পাক ≈ ৪.১৭ ms.
3. Transfer time — আসল বাইটগুলো পড়া; প্রায় ২০০ MB/s হারে ৮ KB পড়তে মাত্র ~০.০৪ ms.

যোগ করলে একটি random ৮ KB পড়া ≈ ৯ + ৪.১৭ + ০.০৪ ≈ ১৩ ms. অথচ head একবার জায়গামতো বসলে পরের page-গুলো পড়তে প্রতিটিতে শুধু transfer time, ~০.০৪ ms. অর্থাৎ HDD-তে sequential I/O random I/O-এর চেয়ে প্রায় ৩০০ গুণ সস্তা। এজন্যই একটি HDD সেকেন্ডে মাত্র ~১০০–২০০টি random পড়া (IOPS) দিতে পারে, অথচ একটানা পড়ায় শতশত MB.

SSD-এ কোনো চলমান অংশ নেই; ডেটা থাকে NAND flash চিপে। random পড়া কয়েক দশ µs, আর NVMe SSD সেকেন্ডে লাখো random পড়া দিতে পারে। তবু sequential এখনো দ্রুততর, কারণ বড় একটানা অনুরোধে ভেতরের বহু চিপ একসাথে কাজ করে। লেখার দিকটি জটিল: flash-এ একটি জায়গায় সরাসরি নতুন করে লেখা যায় না। লেখা হয় ছোট flash page-এ (কয়েক KB), কিন্তু মোছা যায় শুধু অনেকগুলো page-এর বড় erase block একসাথে। তাই SSD-র ভেতরের সফটওয়্যার (FTL) প্রতিটি হালনাগাদ নতুন জায়গায় লেখে, আর পরে পুরোনো block থেকে বৈধ page সরিয়ে block মোছে। ফলে আপনি ১ MB লিখতে বললে ভেতরে হয়তো ২–৩ MB লেখা হয় — একে বলে write amplification. ছোট random লেখা আর প্রায়-ভরা ডিস্কে এটি বাড়ে। flash-এর লেখার আয়ু সীমিত, তাই এটি গতি আর আয়ু দুটিরই প্রশ্ন।

৩ · Page — ডিস্ক আর মেমোরির লেনদেনের একক

ডেটাবেস কখনো ডিস্ক থেকে “একটি সারি” পড়ে না। সে পড়ে একটি নির্দিষ্ট আকারের টুকরো — page (অনেক বইয়ে block). একটি সারি লাগলেও পুরো page আসে, আর ভাগ্য ভালো হলে পরের দরকারি সারিগুলোও সেই page-এই থাকে। প্রচলিত আকার:

একটি টেবিল তাহলে কী? ডিস্কে সেটি এক বা একাধিক ফাইল, আর প্রতিটি ফাইল page-এর একটি সারি: page 0, page 1, page 2 … প্রতিটি page-এর নম্বর জানলেই অবস্থান জানা যায়: অফসেট = নম্বর × page-এর আকার. PostgreSQL প্রতিটি টেবিল আর index-কে আলাদা ফাইলে রাখে; SQLite পুরো ডেটাবেস একটি ফাইলে রাখে, যার ভেতরে প্রতিটি টেবিল আর index নিজস্ব page-গুলোর একটি গাছ। ফাঁকা হয়ে যাওয়া page-গুলোর একটি তালিকাও থাকে — freelist — যাতে নতুন ডেটা ফাইল না বাড়িয়ে সেগুলোতে বসতে পারে।

এবার নিজের চোখে দেখুন। প্রথম এডিটর চলে দোকানের নমুনা ডেটাবেসে (db-shop): customers (customer_id, name, city, phone, joined_on — ৮ জন গ্রাহক), categories (category_id, name — ৪টি শ্রেণি), products (product_id, name, category_id, price, stock — ১০টি পণ্য), orders (order_id, customer_id, order_date, status — ১০টি অর্ডার) আর order_items (order_id, product_id, quantity, unit_price — ১৬টি লাইন)। SQLite-এর PRAGMA কমান্ড ডেটাবেসের ভেতরের তথ্য জানায়, আর sqlite_schema টেবিলে প্রতিটি টেবিল ও index-এর গাছ কোন page থেকে শুরু (rootpage), তা লেখা থাকে। প্রতিবার চালালে ডেটাবেস মেমোরিতে নতুন করে তৈরি হয়।

PRAGMA page_size;
PRAGMA page_count;
PRAGMA freelist_count;
SELECT type, name, rootpage FROM sqlite_schema;

এবার একটি বড় টেবিল বানিয়ে page বাড়তে দেখি। ধরুন বিদ্যুৎ বিতরণ সংস্থার মিটার রিডিং: readings (id, meter, units). পর্ব ২৫-এর recursive CTE দিয়ে প্রথমে ১,০০০টি, তারপর আরও ৪,০০০টি সারি ঢোকানো হচ্ছে; শেষ কোয়েরিটি PRAGMA-কে টেবিলের মতো (pragma_page_count()) ব্যবহার করে হিসাব কষে:

CREATE TABLE readings (id INTEGER PRIMARY KEY, meter INTEGER, units INTEGER);
PRAGMA page_count;
WITH RECURSIVE s(x) AS (SELECT 1 UNION ALL SELECT x + 1 FROM s WHERE x < 1000)
INSERT INTO readings SELECT x, x % 50, x * 3 FROM s;
PRAGMA page_count;
WITH RECURSIVE s(x) AS (SELECT 1001 UNION ALL SELECT x + 1 FROM s WHERE x < 5000)
INSERT INTO readings SELECT x, x % 50, x * 3 FROM s;
PRAGMA page_count;
SELECT p.page_count, s.page_size, p.page_count * s.page_size AS bytes,
       round(5000.0 / (p.page_count - 2), 1) AS rows_per_page
FROM pragma_page_count() p, pragma_page_size() s;

Page বড় হলে কী হয়? একটি নতুন, ফাঁকা ডেটাবেসে প্রথম টেবিল বানানোর আগে PRAGMA page_size বদলানো যায়; পরে বদলাতে VACUUM দিয়ে পুরো ফাইল নতুন করে লিখতে হয়:

PRAGMA page_size = 8192;
CREATE TABLE readings (id INTEGER PRIMARY KEY, meter INTEGER, units INTEGER);
WITH RECURSIVE s(x) AS (SELECT 1 UNION ALL SELECT x + 1 FROM s WHERE x < 5000)
INSERT INTO readings SELECT x, x % 50, x * 3 FROM s;
PRAGMA page_size;
PRAGMA page_count;
PRAGMA page_size = 1024;
VACUUM;
PRAGMA page_size;
PRAGMA page_count;

প্রতিটি টেবিল কত page নিল, তা জানার একটি সরাসরি পথ SQLite-এ আছে — dbstat নামের virtual table. কিন্তু সেটি SQLite compile করার সময় চালু করতে হয়। এই পাতার SQLite (sql.js) সেটি ছাড়া বানানো, তাই নিচের এডিটরটি ইচ্ছে করেই ত্রুটি দেখায়:

CREATE TABLE t (x INTEGER);
SELECT name, pageno, pagetype, ncell FROM dbstat;

৪ · ফাইলের সংগঠন — heap, sorted আর clustered

সারিগুলো page-এ কোন ক্রমে বসবে, তার তিনটি মূল উত্তর:

InnoDB-তে primary key না দিলে সে প্রথম UNIQUE NOT NULL index ব্যবহার করে, তাও না থাকলে একটি লুকানো ৬-বাইটের row id বানায়। আর secondary index-এর leaf-এ থাকে primary key-র মান — তাই secondary index দিয়ে খুঁজলে দুটি গাছে নামতে হয়। PostgreSQL-এ index সরাসরি heap-এর page আর slot দেখায়। দুই নকশার লাভ-ক্ষতি ভাবনার প্রশ্ন ৪-এ।

SQLite-এ সারির ঠিকানা হলো rowid. INTEGER PRIMARY KEY কলাম rowid-এরই আরেক নাম; আর WITHOUT ROWID লিখলে টেবিলটি সরাসরি primary key ধরে সাজানো গাছ হয় — তখন rowid বলে কিছু নেই:

CREATE TABLE visitors (name TEXT, city TEXT);
INSERT INTO visitors VALUES ('Rina', 'Bogura'), ('Kamal', 'Sylhet'), ('Joba', 'Barishal');
DELETE FROM visitors WHERE name = 'Kamal';
INSERT INTO visitors VALUES ('Liton', 'Cumilla');
SELECT rowid, name, city FROM visitors;
CREATE TABLE stations (code TEXT PRIMARY KEY, name TEXT) WITHOUT ROWID;
INSERT INTO stations VALUES ('KMLP', 'Kamalapur'), ('CTG', 'Chattogram');
SELECT * FROM stations;
SELECT rowid FROM stations;

কোন সংগঠনে কত I/O

এবার I/O cost model প্রয়োগ করি। টেবিলে Bটি page, খুঁজছি একটি unique key-র মান। শুধু page-পড়া আর লেখা গোনা হচ্ছে:

Heap-এ গড় B/2 কেন? মানটি সমান সম্ভাবনায় যেকোনো page-এ থাকতে পারে; i-তম page-এ থাকলে i-টি page পড়তে হয়, তাই গড় (১ + ২ + … + B) ÷ B = (B + ১)/২. Sorted file-এ প্রতিবার অর্ধেক বাদ, তাই ⌈log₂ B⌉. ধরুন B = ১০,০০০: heap-এ গড়ে ৫,০০০টি page, sorted-এ ১৪টি, B+ tree-এ ৩–৪টি। sorted file-এর দুর্বলতা হলো ঢোকানো: মাঝখানে জায়গা করতে গড়ে অর্ধেক ফাইল সরাতে হয়। B+ tree দুই সমস্যারই মীমাংসা — পর্ব ৪০-এর বিষয়। SQLite-এর query plan এই পার্থক্য সরাসরি দেখায়:

EXPLAIN QUERY PLAN SELECT * FROM readings WHERE id = 4000;
EXPLAIN QUERY PLAN SELECT * FROM readings WHERE id BETWEEN 100 AND 200;
EXPLAIN QUERY PLAN SELECT * FROM readings WHERE units = 300;

৫ · Record আর slotted page

একটি সারি ডিস্কে একটি record — বাইটের একটি ধারা। সব কলাম নির্দিষ্ট আকারের হলে (INTEGER, CHAR(10)) record-ও নির্দিষ্ট আকারের: fixed-length record. তখন i-তম কলাম কোথায়, সরল যোগে বলা যায়। কিন্তু নাম, ঠিকানা, বিবরণ — এগুলো VARCHAR বা TEXT, প্রতিটি সারিতে আলাদা দৈর্ঘ্যের: variable-length record. তখন record-এর শুরুতে একটি ছোট হেডার রাখা হয়, যাতে প্রতিটি variable কলাম কোথায় শুরু আর কত লম্বা, লেখা থাকে।

NULL কীভাবে রাখা হয়? বেশির ভাগ সিস্টেম record-এর হেডারে একটি NULL bitmap রাখে: প্রতিটি কলামের জন্য একটি bit, ১ মানে NULL, আর NULL কলামের মান কোনো জায়গাই নেয় না। PostgreSQL-এ সারির কোনো কলাম NULL হলেই bitmap যোগ হয়; InnoDB-র compact ধরনেও nullable কলামের জন্য bit থাকে। SQLite আরেকটু চতুর: হেডারে প্রতিটি কলামের একটি “serial type” সংখ্যা, যা টাইপ আর আকার দুটিই বলে — NULL, ০ আর ১-এর জন্য বডিতে কোনো বাইটই লাগে না, আর পূর্ণসংখ্যা মান অনুযায়ী ১, ২, ৩, ৪, ৬ বা ৮ বাইটে বসে।

এখন বড় প্রশ্ন: আলাদা দৈর্ঘ্যের record একটি page-এ কীভাবে সাজানো হবে, যাতে মোছা আর নতুন ঢোকানো সহজ হয়, অথচ বাইরের কেউ (যেমন index) record-টিকে একটি স্থির ঠিকানায় খুঁজে পায়? উত্তর slotted page. page-এর শুরুতে হেডার; তার পরে slot array — প্রতিটি slot-এ একটি record-এর অফসেট আর দৈর্ঘ্য — যা সামনের দিকে বাড়ে; আর record-গুলো বসে page-এর শেষ থেকে, পেছনের দিকে। মাঝখানের ফাঁকা জায়গা দুই দিক থেকে খায়। record-এর ঠিকানা হলো (page নম্বর, slot নম্বর) — একে বলে record id (RID). PostgreSQL-এ এটিই ctid, যেমন (0,1): block 0, slot 1.

বাস্তব সিস্টেমেও ঠিক এই নকশা, খুঁটিনাটি আলাদা। PostgreSQL-এর page-এ ২৪ বাইটের হেডার, প্রতিটি slot (line pointer) ৪ বাইট, আর প্রতিটি সারির নিজস্ব হেডার প্রায় ২৩ বাইট — তাই খুব সরু টেবিলে আসল ডেটার চেয়ে হেডারই বেশি। SQL Server উল্টো দিকে সাজায়: record হেডারের পর থেকে সামনে, আর slot-এর তালিকা page-এর শেষ থেকে পেছনে। ধারণা একই।

কলামের টাইপও page-এর সংখ্যা বদলায়। একই ৫,০০০টি মোবাইল নম্বর একবার INTEGER, একবার TEXT হিসেবে রাখা হলো; page_count-এর পার্থক্যই দ্বিতীয় টেবিলের আকার:

CREATE TABLE a_int (id INTEGER PRIMARY KEY, phone INTEGER);
WITH RECURSIVE s(x) AS (SELECT 1 UNION ALL SELECT x + 1 FROM s WHERE x < 5000)
INSERT INTO a_int SELECT x, 1711000000 + x FROM s;
PRAGMA page_count;
CREATE TABLE b_text (id INTEGER PRIMARY KEY, phone TEXT);
WITH RECURSIVE s(x) AS (SELECT 1 UNION ALL SELECT x + 1 FROM s WHERE x < 5000)
INSERT INTO b_text SELECT x, '0' || (1711000000 + x) FROM s;
PRAGMA page_count;
SELECT typeof(a.phone), a.phone, typeof(b.phone), b.phone, length(b.phone)
FROM a_int a JOIN b_text b USING (id) WHERE id = 1;

মুছলে কী হয়? সারি মুছলে তার জায়গা page-এর ভেতরে গর্ত হয়; পুরো page খালি হলেই কেবল সেটি freelist-এ যায়। আর ফাইল নিজে থেকে ছোট হয় না:

PRAGMA page_count;
DELETE FROM readings WHERE id % 2 = 0;
PRAGMA page_count;
PRAGMA freelist_count;
DELETE FROM readings WHERE id <= 2500;
PRAGMA page_count;
PRAGMA freelist_count;
VACUUM;
PRAGMA page_count;
PRAGMA freelist_count;

৬ · বড় মান, আর row বনাম column store

একটি record যদি page-এর চেয়েই বড় হয় — ধরুন একটি লম্বা নোটিশ, একটি JSON বা ছবি? তখন record-এর একটি অংশ page-এ থাকে, বাকিটা আলাদা page-এর শিকলে: overflow page. SQLite আর InnoDB এভাবে কাজ করে। PostgreSQL-এর কৌশলের নাম TOAST: সারি মোটামুটি ২ KB ছাড়ালে বড় মানগুলো আগে compress করা হয়, তাতেও না কুলোলে টুকরো করে একটি আলাদা TOAST টেবিলে রাখা হয়, আর মূল সারিতে থাকে শুধু একটি ছোট সূত্র।

CREATE TABLE notice (id INTEGER PRIMARY KEY, body TEXT);
INSERT INTO notice VALUES (1, 'অফিস বন্ধ');
PRAGMA page_count;
INSERT INTO notice VALUES (2, printf('%.*c', 20000, 'x'));
PRAGMA page_count;
SELECT id, length(body) AS chars FROM notice;

Row store বনাম column store

এতক্ষণের সব নকশা row store: একটি সারির সব কলাম পাশাপাশি, একই page-এ। একটি অর্ডার পুরোটা পড়তে বা লিখতে — অর্থাৎ OLTP-এর কাজে — এটি আদর্শ। কিন্তু প্রশ্নটি যদি হয় “গত পাঁচ বছরে প্রতি মাসের মোট বিক্রি”? দরকার শুধু দুটি কলাম, অথচ row store-কে প্রতিটি সারির সব কলাম পড়তে হয়। Column store উল্টো: প্রতিটি কলাম আলাদা ধারায়, তাই দুটি কলাম মানে শুধু সেই দুই ধারা পড়া; আর একই ধরনের মান পাশাপাশি থাকায় compression দারুণ কাজ করে। দাম: একটি সারি ঢোকাতে প্রতিটি কলামের ধারায় লিখতে হয়।

Row store:
[1, 2025-09-01, Dhaka, 17400 │ 2, 2025-09-03, Khulna, 1750 │ 3, …]

Column store:
id:     [1 │ 2 │ 3]
date:   [2025-09-01 │ 2025-09-03 │ 2025-09-10]
city:   [Dhaka │ Khulna │ Dhaka]
amount: [17400 │ 1750 │ 1780]

SUM(amount) → row store: সব page / column store: শুধু amount

ধারণাটি পুরোনো — ১৯৯০-এর দশকেই MonetDB আর Sybase IQ-র মতো column-ভিত্তিক সিস্টেম ছিল, আর ২০০৫ সালের C-Store গবেষণা (Michael Stonebraker ও সহকর্মীরা) একে নতুন করে জনপ্রিয় করে। আজ ClickHouse, DuckDB, Parquet ফাইল-ফরম্যাট আর বড় cloud warehouse-গুলো column-ভিত্তিক। SQL Server-এর columnstore index-এর মতো মিশ্র ব্যবস্থাও আছে।

৭ · Buffer pool — মেমোরিতে page-এর কপি

ডিস্ক এত ধীর বলে DBMS মেমোরির একটি বড় অংশ নিজের জন্য রাখে: buffer pool. পর্ব ৩-এর buffer manager এটি চালায়। buffer pool হলো একই আকারের অনেকগুলো ঘর — frame — প্রতিটিতে একটি page-এর কপি ধরে। PostgreSQL-এ এর আকার shared_buffers, InnoDB-তে innodb_buffer_pool_size — দুটিরই default মাত্র ১২৮ MB, আর আসল সার্ভারে সাধারণত অনেক বড় করে দেওয়া হয়। প্রতিটি frame-এর সাথে কিছু হিসাব:

কোনো অংশ (ধরুন একটি scan) page চাইলে buffer manager এই ধাপে কাজ করে: page table-এ খোঁজে; থাকলে (hit) pin count বাড়িয়ে frame-এর ঠিকানা দেয় — কোনো I/O নেই। না থাকলে (miss) policy একটি pin count ০ frame বেছে নেয়; সেটি dirty হলে আগে ডিস্কে লেখে; তারপর নতুন page পড়ে, page table হালনাগাদ করে, pin = ১ দিয়ে ফেরত দেয়। ব্যবহারকারী কাজ শেষে unpin করে, আর page বদলে থাকলে dirty চিহ্ন দেয়। নিচে ৩টি frame-এর একটি ছোট buffer pool, LRU (least recently used — যে page সবচেয়ে বেশি সময় ধরে ব্যবহৃত হয়নি, সেটি সরানো) নিয়মে:

বাস্তবে hit ratio মাপা DBA-র প্রতিদিনের কাজ। OLTP সার্ভারে গরম ডেটার প্রায় সবই buffer pool-এ থাকার কথা; hit ratio অনেকটা পড়ে গেলে হয় pool ছোট, নয়তো কোনো কোয়েরি অপ্রয়োজনে বিশাল scan করছে। PostgreSQL-এ EXPLAIN (ANALYZE, BUFFERS) একটি কোয়েরির জন্য shared hit (pool থেকে পাওয়া) আর read (pool-এর বাইরে থেকে আনা) page গুনে দেখায়:

SHOW block_size;                 -- 8192
SHOW shared_buffers;             -- default: 128MB
SELECT ctid, * FROM orders LIMIT 3;   -- ctid যেমন (0,1), (0,2): block আর slot
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM orders WHERE customer_id = 1;

৮ · কোন page যাবে — LRU, clock আর sequential flooding

সত্যিকারের LRU-র একটি সমস্যা: প্রতিটি hit-এ page-টিকে তালিকার শেষে সরাতে হয়, আর হাজারো thread একসাথে সেই তালিকা বদলাতে গেলে lock-এর লড়াই বাধে। তাই অনেক সিস্টেম একটি সস্তা আনুমানিক রূপ ব্যবহার করে — clock (second chance). frame-গুলো একটি বৃত্তে, প্রতিটির একটি reference bit; hit হলে শুধু bit = ১, তালিকা নড়ে না। শিকার খুঁজতে একটি কাঁটা (hand) ঘোরে: bit ১ হলে ০ করে এগিয়ে যায় (“আরেকটি সুযোগ”), bit ০ পেলে সেটিই শিকার।

PostgreSQL clock-এর একটি রূপ ব্যবহার করে (clock sweep): bit-এর বদলে একটি usage count, যা প্রতিটি ব্যবহারে বাড়ে (সর্বোচ্চ ৫) আর কাঁটার প্রতি পাকে এক কমে — ফলে বারবার ব্যবহৃত page বেশি পাক টিকে থাকে।

Sequential flooding — একটি scan যখন সব ভাসিয়ে নেয়

LRU-র সবচেয়ে বিখ্যাত দুর্বলতা দেখা দেয় বড় একটানা scan-এ। ধরুন টেবিলে ৪টি page, buffer pool-এ ৩টি frame, আর একটি রিপোর্ট টেবিলটি দুবার পড়ে: ১ ২ ৩ ৪ ১ ২ ৩ ৪. LRU যাকে সরায়, ঠিক সেটিই পরের অনুরোধ। তুলনার জন্য পাশে উল্টো নিয়ম MRU (most recently used — সবচেয়ে সাম্প্রতিকটি সরানো):

শুধু MRU-তে চলে যাওয়া সমাধান নয় — সাধারণ OLTP-তে MRU ভয়ংকর। বাস্তব সিস্টেম scan-কে আলাদা করে সামলায়:

• PostgreSQL: buffer pool-এর এক-চতুর্থাংশের চেয়ে বড় টেবিলের sequential scan একটি ছোট ring buffer (২৫৬ KB) ব্যবহার করে — scan নিজের ছোট বৃত্তেই page ঘোরায়, বাকি pool অক্ষত।
• InnoDB: LRU তালিকার মাঝখানে নতুন page ঢোকায় (midpoint insertion): তালিকার শেষ প্রায় ৩/৮ অংশ “পুরোনো” উপতালিকা। নতুন পড়া page সেখানে বসে, আর অন্তত কিছু সময় (default ১ সেকেন্ড) পরে আবার ব্যবহৃত হলে তবেই “নতুন” অংশে ওঠে।
• LRU-K আর 2Q: শুধু শেষ ব্যবহার নয়, শেষ K-টি ব্যবহারের সময় দেখা (LRU-2 সবচেয়ে প্রচলিত); বা নতুন page-কে আগে একটি ছোট পরীক্ষামূলক সারিতে রাখা, দ্বিতীয়বার লাগলে তবেই মূল pool-এ তোলা। একবার পড়া scan-এর page মূল pool-এ পৌঁছায়ই না।

নিচের ছোট JavaScript প্রোগ্রাম ৪টি frame-এ LRU আর একটি সরল 2Q-ধাঁচের নিয়ম পাশাপাশি চালায়: ৩টি গরম page (A, B, C) বারবার, তারপর ৬ page-এর একটি scan (1–6), তারপর আবার গরম page. প্রতিটি অনুরোধে H = hit, . = miss. অনুরোধের তালিকা বদলে নিজে পরীক্ষা করুন।

function lru(refs, n) {                           // pool[0] = least recently used
  const pool = []; let out = "";
  for (const p of refs) {
    const i = pool.indexOf(p); out += i >= 0 ? "H" : ".";
    if (i >= 0) pool.splice(i, 1); else if (pool.length === n) pool.shift();
    pool.push(p);
  }
  return out;
}
function twoQ(refs, n) {   // 1 probation frame, n-1 main frames, ids of pages seen once
  let probe = null, out = ""; const main = [], seen = [];
  for (const p of refs) {
    const m = main.indexOf(p), hit = m >= 0 || probe === p; out += hit ? "H" : ".";
    if (m >= 0) { main.splice(m, 1); main.push(p); }
    else if (!hit && seen.includes(p)) { seen.splice(seen.indexOf(p), 1); if (main.length === n - 1) main.shift(); main.push(p); }
    else if (!hit) { if (probe) { seen.push(probe); if (seen.length > n) seen.shift(); } probe = p; }
  }
  return out;
}
const refs = [..."ABCABCABC", ..."123456", ..."ABCABC"];   // hot pages, a scan, hot again
console.log("refs  " + refs.join(""));
for (const [name, f] of [["LRU", lru], ["2Q", twoQ]]) { const s = f(refs, 4); console.log(name.padEnd(5), s, "hits:", s.split("H").length - 1); }

refs  ABCABCABC123456ABCABC
LRU   ...HHHHHH.........HHH hits: 9
2Q    .....HHHH......HH.HHH hits: 9

৯ · Dirty page লেখা, WAL আর OS-এর page cache

Dirty page কখন ডিস্কে যাবে? শুধু শিকার হওয়ার সময় লিখলে হঠাৎ একটি কোয়েরি ধীর হয়ে যায়, আর crash হলে মেমোরির সব পরিবর্তন হারায়। তাই DBMS-এর পেছনে একটি প্রক্রিয়া (PostgreSQL-এ background writer আর checkpointer, InnoDB-তে page cleaner) ধীরে ধীরে dirty page লিখে রাখে, যাতে শিকার বাছাইয়ের সময় পরিষ্কার frame পাওয়া যায়।

কিন্তু commit-এর সময় সব বদলানো page লিখে ফেললেই তো নিরাপদ? সেটি random লেখার পাহাড় — প্রতিটি ছোট transaction-এ এখানে-ওখানে দশটি page. সমাধান write-ahead log (WAL): commit-এর সময় শুধু পরিবর্তনের বিবরণ একটি log ফাইলের শেষে একটানা (sequential!) লেখা হয় আর fsync দিয়ে ডিস্কে নিশ্চিত করা হয়; data page পরে, সুবিধামতো। আর buffer manager-এর একটি কঠোর নিয়ম: একটি dirty page ডিস্কে লেখার আগে, তার পরিবর্তনের log record অবশ্যই ডিস্কে পৌঁছাতে হবে। crash হলে log থেকে সব আবার গড়া যায়। পুরো গল্প — checkpoint আর ARIES — পর্ব ৪৮-এ।

OS-এর page cache আর double buffering

অপারেটিং সিস্টেমও নিজের একটি cache রাখে: সাধারণ read() দিয়ে পড়া ফাইলের অংশ মেমোরিতে — OS page cache. DBMS নিজের buffer pool-ও রাখলে একই page মেমোরিতে দুবার থাকতে পারে: double buffering. এর দুটি সমাধানের পথ:

পরের পর্বগুলোর জন্য I/O cost model

পর্ব ৪০–৪৩-এ খরচের হিসাব এই ভাষায় হবে: টেবিল R-এ B(R)টি page, T(R)টি সারি, buffer pool-এ Mটি frame. full scan-এর খরচ B(R); B+ tree-এ একটি key খোঁজা ≈ উচ্চতা h; আর কোনো অ্যালগরিদম “M frame-এ কী ধরে”, তা দিয়েই sort আর join-এর কৌশল বদলায়। মনে রাখবেন মডেলের সরলীকরণগুলো: random আর sequential I/O-কে সমান ধরা হয়, CPU বাদ, আর buffer pool-এ আগে থেকে থাকা page প্রায়ই উপেক্ষিত। আসল optimizer (পর্ব ৪৩) random page-এ বেশি দাম ধরে — PostgreSQL-এ random_page_cost-এর default ৪, seq_page_cost ১.

১০ · AI-এর যুগে স্টোরেজ আর পারফরম্যান্সের প্রশ্ন

“ডেটাবেস ধীর, কনফিগারেশন ঠিক করে দাও” — AI আত্মবিশ্বাসের সাথে সেটিং-এর তালিকা দেয়, কিন্তু প্রায়ই আপনার RAM, ডিস্ক, সংস্করণ বা কাজের ধরন না জেনে। সাধারণ ভুল:

AI-এর পরামর্শ চালু করার আগে — চেকলিস্ট

• কোন DBMS আর কোন সংস্করণের কথা, নিশ্চিত হয়েছি; প্রতিটি সেটিংয়ের নাম ডকুমেন্টেশনে মিলিয়েছি
• বদলানোর আগে আর পরে একই কোয়েরির সময় আর buffer hit/read মেপেছি
• EXPLAIN দেখে নিশ্চিত হয়েছি যে সমস্যাটি index বা কোয়েরির নয়
• মেমোরির হিসাব করেছি: buffer pool + OS cache + প্রতি সংযোগের মেমোরি ≤ মোট RAM
• পরীক্ষামূলক সার্ভারে আগে চালিয়েছি, আর পুরোনো সেটিং ফেরানোর পথ রেখেছি