ডিস্ক আর SSD — গঠন আর disk scheduling

১ · হার্ড ডিস্কের ভেতরে — platter থেকে LBA

পর্ব ৩৯-এ দেখেছেন, OS একটি ডিভাইসের সাথে কথা বলে device driver আর device controller-এর মাধ্যমে, আর বড় ডেটা সরায় DMA দিয়ে। এই পর্বে সেই ডিভাইসগুলোর মধ্যে সবচেয়ে গুরুত্বপূর্ণটি — স্থায়ী স্টোরেজ। আপনার ফাইল, ডেটাবেস, swap, এমনকি OS নিজেই থাকে এখানে। আর এখানেই একটি কম্পিউটারের সবচেয়ে বড় গতির ফারাক: RAM-এ একটি পড়া ১০০ ns-এর কাছাকাছি, ঘোরা ডিস্কে কয়েক ms — প্রায় এক লাখ গুণ বেশি।

একটি HDD খুললে দেখবেন এক বা একাধিক চকচকে গোল চাকতি, একটি অক্ষে গাঁথা — এগুলো platter. প্রতিটির দুই পিঠে চৌম্বক আবরণ, যেখানে বিট লেখা থাকে। Platter-গুলো একসাথে মিনিটে কয়েক হাজার পাক ঘোরে — ল্যাপটপে প্রায়ই 5400, ডেস্কটপে 7200, কিছু সার্ভার-ডিস্কে 10000 বা 15000 RPM. প্রতিটি পিঠের ওপর ভাসে একটি read-write head; সব head বসানো একটি arm-এর মাথায়, আর arm-গুলো একসাথে ভেতরে-বাইরে সরে। ঘোরার সময় head পিঠ থেকে মাত্র কয়েক ন্যানোমিটার উঁচুতে বাতাসের স্তরে ভাসে — তাই ধাক্কা লাগলে head পিঠে আঘাত করতে পারে (head crash).

        পাশ থেকে দেখা                     ওপর থেকে একটি platter
   arm ──┬── head 0 ▶ ═══ platter 0 (ওপর পিঠ)        .-~~~~~-.
         ├── head 1 ▶ ═══ platter 0 (নিচ পিঠ)      /  .---.  \   ← track (গোল রেখা)
         ├── head 2 ▶ ═══ platter 1 (ওপর পিঠ)     |  ( ● )  |  ● = অক্ষ (spindle)
         └── head 3 ▶ ═══ platter 1 (নিচ পিঠ)      \  '---'  /   track-এর একটি টুকরো
                                                    '-~~~~~-'      = sector
   cylinder = সব পিঠের একই ব্যাসার্ধের track-গুলো একসাথে

• Track: একটি পিঠে একটি নির্দিষ্ট ব্যাসার্ধের গোল রেখা। একটি পিঠে লাখখানেকেরও বেশি track থাকতে পারে।
• Sector: track-এর একটি টুকরো — পড়া-লেখার সবচেয়ে ছোট একক। প্রতিটি sector-এ ডেটার সাথে থাকে চেনার তথ্য আর ভুল ধরার ও শোধরানোর কোড (ECC).
• Cylinder: সব পিঠের একই ব্যাসার্ধের track মিলে একটি কাল্পনিক চোঙ। Arm না সরিয়েই পুরো cylinder পড়া যায়। Disk scheduling-এর অঙ্কে “cylinder 0–199” বলতে এটাই বোঝায়।

Zoned bit recording — বাইরের track-এ বেশি sector

বাইরের দিকের track ভেতরের track-এর চেয়ে লম্বা। পুরোনো ডিস্কে প্রতিটি track-এ সমান sector থাকত, ফলে বাইরের track-এ বিটগুলো অযথা ছড়ানো থাকত। আধুনিক ডিস্ক zoned bit recording ব্যবহার করে: track-গুলো কয়েকটি zone-এ ভাগ, আর বাইরের zone-এর প্রতিটি track-এ বেশি sector. Platter একই গতিতে ঘোরে, তাই এক পাকে বাইরের track-এর নিচ দিয়ে বেশি sector যায় — বাইরের দিকে transfer rate বেশি, প্রায়ই ভেতরের দিকের প্রায় দ্বিগুণের কাছাকাছি (ডিস্কভেদে আলাদা)। তাই একটি HDD-র শুরুর LBA-গুলো (বাইরের দিকে) শেষের দিকের চেয়ে দ্রুত পড়ে।

512 byte বনাম 4 KiB — Advanced Format

বহু দশক ধরে sector-এর আকার ছিল 512 byte. ডিস্ক বড় হওয়ায় এত ছোট sector-এ প্রতিটির সাথে আলাদা ফাঁক আর ECC-র খরচ বেশি পড়ছিল, তাই প্রায় ২০১০ সাল থেকে নির্মাতারা 4096 byte-এর physical sector চালু করেন — একে Advanced Format বলে। পুরোনো সফটওয়্যার যাতে না ভাঙে, অনেক ডিস্ক বাইরে 512 byte-এর logical sector দেখায় কিন্তু ভেতরে 4 KiB-তে লেখে (512e, “512 emulation”); কিছু ডিস্ক বাইরেও 4 KiB দেখায় (4Kn, “4K native”).

CHS থেকে LBA

পুরোনো দিনে OS-কে একটি sector চাইতে হতো তিনটি সংখ্যায়: cylinder, head, sector — CHS. কিন্তু zone-এ zone-এ sector-সংখ্যা বদলালে, আর ডিস্ক নিজেই খারাপ sector সরিয়ে রাখলে, এই তিন সংখ্যা আর আসল জ্যামিতির সাথে মেলে না। তাই আধুনিক ডিস্ক বাইরে দেখায় শুধু একটি ক্রমিক নম্বর — LBA 0, 1, 2, … শেষ পর্যন্ত। কোন LBA আসলে কোন platter-এর কোন track-এ, তা জানে কেবল ডিস্কের firmware.

তবু একটি মোটামুটি নিয়ম সত্য থাকে, আর disk scheduling-এর পুরো তত্ত্ব তার ওপর দাঁড়ানো: কাছাকাছি LBA সাধারণত কাছাকাছি physical জায়গায়, তাই OS LBA-র দূরত্বকে head-এর দূরত্বের আনুমানিক মাপ ধরে; অঙ্কের “cylinder নম্বর” সেই সরল মডেল।

২ · Access time — seek, rotational latency আর transfer

একটি sector পড়তে ডিস্ককে তিনটি কাজ পরপর করতে হয়:

1. Seek time: arm সরিয়ে head-কে ঠিক cylinder-এ নেওয়া, আর সেখানে স্থির হওয়া (settle). পাশের track-এ যেতে ১ ms-এর কম, পুরো ডিস্ক পেরোতে ১০ ms-এর বেশিও লাগতে পারে; ডেস্কটপ ডিস্কের গড় seek প্রায়ই কয়েক ms থেকে ১০ ms-এর আশপাশে বলা হয় (নির্মাতার datasheet দেখুন)।
2. Rotational latency: চাওয়া sector ঘুরে head-এর নিচে আসা পর্যন্ত অপেক্ষা। সবচেয়ে ভালো ক্ষেত্রে ০, সবচেয়ে খারাপ ক্ষেত্রে পুরো এক পাক; এলোমেলো অবস্থানে গড়ে অর্ধেক পাক.
3. Transfer time: sector-গুলো head-এর নিচ দিয়ে যাওয়ার সময় আসল পড়া। সময় = ডেটার আকার ÷ transfer rate.

উদাহরণ ১ (পরীক্ষার সবচেয়ে পরিচিত অঙ্ক): 7200 RPM ডিস্কের গড় rotational latency কত? এক মিনিটে ৭২০০ পাক, তাই এক পাক = ৬০,০০০ ms ÷ ৭২০০ = ৮.৩৩৩ ms. গড় latency = অর্ধেক পাক = ৪.১৬৭ ms (প্রায় ৪.১৭ ms).

উদাহরণ ২: একই ডিস্ক, গড় seek ৯ ms, transfer rate ১৫০ MB/s (১ MB = ১০^৬ byte ধরে)। একটি এলোমেলো 4 KiB (৪০৯৬ byte) block পড়তে কত সময়? Transfer = ৪০৯৬ ÷ ১৫০,০০,০০,০০০ সেকেন্ড ≈ ০.০২৭ ms. মোট = ৯ + ৪.১৬৭ + ০.০২৭ ≈ ১৩.১৯৪ ms. অর্থাৎ সেকেন্ডে মোটামুটি ১,০০০ ÷ ১৩.১৯৪ ≈ ৭৬টি এলোমেলো পড়া — এই মাপকে বলে IOPS. আসল ডেটা পড়ায় গেল মাত্র ০.০২৭ ms.

উদাহরণ ৩ — random বনাম sequential: ১,০০০টি 4 KiB block পড়তে হবে। এলোমেলো জায়গায় থাকলে প্রতিটির জন্য আলাদা seek আর latency: ১,০০০ × ১৩.১৯৪ ≈ ১৩.২ সেকেন্ড। পাশাপাশি থাকলে একবার seek, একবার latency, তারপর একটানা ৪০,৯৬,০০০ byte transfer: ৯ + ৪.১৬৭ + ২৭.৩০৭ ≈ ৪০.৫ ms — প্রায় ৩২৬ গুণ দ্রুত. তাই file system ফাইলের block পাশাপাশি রাখতে চায় (পর্ব ৪৩), আর OS অনুরোধগুলো সাজিয়ে পাঠায়।

নিচের calculator এই তিনটি উদাহরণ নিজে হিসাব করে। সংখ্যাগুলো (seek, rate) বদলে নিজের বইয়ের অঙ্ক যাচাই করতে পারেন — তবে আগে হাতে করুন।

// HDD access time = seek + rotational latency + transfer (all in ms).
function hdd(rpm, seekMs, mbPerS, bytes) {
  const rotMs = 60000 / rpm;                    // one full revolution
  const latMs = rotMs / 2;                      // on average, wait half a revolution
  const xferMs = bytes / (mbPerS * 1e6) * 1000; // bytes / (bytes per ms)
  return { rotMs, latMs, xferMs, total: seekMs + latMs + xferMs };
}
const f = (x) => x.toFixed(3);
console.log("RPM     one rotation   avg rotational latency");
for (const rpm of [5400, 7200, 10000, 15000]) {
  const r = hdd(rpm, 0, 1, 0);
  console.log(String(rpm).padEnd(8) + (f(r.rotMs) + " ms").padEnd(15) + f(r.latMs) + " ms");
}
// Example drive: 7200 RPM, 9 ms average seek, 150 MB/s sustained transfer.
const SEEK = 9, RATE = 150, BLOCK = 4096, N = 1000;
const r = hdd(7200, SEEK, RATE, BLOCK);
console.log("\nOne random 4 KiB read: seek " + SEEK + " + latency " + f(r.latMs) +
  " + transfer " + f(r.xferMs) + " = " + f(r.total) + " ms");
console.log("=> about " + Math.round(1000 / r.total) + " random reads per second (IOPS)");
const random = N * r.total;                     // every block pays seek + latency
const seq = hdd(7200, SEEK, RATE, N * BLOCK).total; // one seek, then stream
console.log(N + " random 4 KiB reads: " + f(random) + " ms");
console.log(N + " blocks read sequentially: " + f(seq) + " ms");
console.log("sequential is " + (random / seq).toFixed(1) + "x faster");
console.log("effective rate, random: " + (N * BLOCK / random / 1000).toFixed(3) + " MB/s");

RPM     one rotation   avg rotational latency
5400    11.111 ms      5.556 ms
7200    8.333 ms       4.167 ms
10000   6.000 ms       3.000 ms
15000   4.000 ms       2.000 ms

One random 4 KiB read: seek 9 + latency 4.167 + transfer 0.027 = 13.194 ms
=> about 76 random reads per second (IOPS)
1000 random 4 KiB reads: 13193.973 ms
1000 blocks read sequentially: 40.473 ms
sequential is 326.0x faster
effective rate, random: 0.310 MB/s

৩ · Disk scheduling — FCFS আর SSTF

একটি ব্যস্ত সার্ভারে একসাথে বহু প্রসেস ডিস্কে অনুরোধ পাঠায়। OS-এর কাছে তখন একটি অপেক্ষমাণ সারি — কোনটি আগে ডিস্কে পাঠাবে? Seek-ই সবচেয়ে বড় খরচ, তাই disk scheduling-এর লক্ষ্য: মোট head movement (কত cylinder পেরোল) কমানো, কিন্তু কোনো অনুরোধকে অনির্দিষ্টকাল বসিয়ে না রেখে। অর্থাৎ throughput বাড়ানো, আর গড় ও সবচেয়ে খারাপ response time সামলানো।

এই পর্বের ক্লাসিক অঙ্ক (Silberschatz-এর পাঠ্যবইয়ের পরিচিত উদাহরণ): ডিস্কে cylinder 0 থেকে 199. Head এখন cylinder 53-এ। অপেক্ষমাণ অনুরোধ, আসার ক্রমে: 98, 183, 37, 122, 14, 124, 65, 67. প্রতিটি algorithm-এর জন্য বের করতে হবে কোন ক্রমে সেবা হবে আর মোট head movement কত cylinder.

FCFS — যে আগে এসেছে

FCFS (first-come, first-served) অনুরোধগুলো আসার ক্রমেই পাঠায়। ন্যায্য, সহজ, কোনো starvation নেই — কিন্তু head এদিক-ওদিক ছোটে:

53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
   45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 cylinder

দেখুন 122 থেকে 14, তারপর 14 থেকে 124 — প্রায় পুরো ডিস্ক দুবার পেরোনো, অথচ 122 আর 124 পাশাপাশি। 37 আর 14-র কাছে যাওয়ার সময় যদি একসাথে সেরে নেওয়া যেত, অনেক বাঁচত।

SSTF — সবচেয়ে কাছেরটি আগে

SSTF (shortest seek time first) প্রতিবার head-এর বর্তমান অবস্থান থেকে সবচেয়ে কাছের অনুরোধটি বাছে। এটি CPU scheduling-এর SJF-এর মতো একটি লোভী (greedy) কৌশল। নিচের stepper প্রতিটি ধাপে বাকি অনুরোধগুলোর দূরত্ব দেখায় — কেন ওই অনুরোধ জিতল, তা সরাসরি চোখে পড়বে।

1 start  head = 532 serve 653 serve 674 serve 375 serve 146 serve 987 serve 1228 serve 1249 serve 183

SSTF সর্বোত্তম নয় — একটি ছোট প্রমাণ

২৩৬ কি সম্ভাব্য সবচেয়ে কম? না। একটি সহজ যুক্তি দিয়ে এই সারির সর্বনিম্ন সীমা বের করা যায়। সবচেয়ে নিচের অনুরোধ 14, সবচেয়ে ওপরেরটি 183, আর head শুরু করে 53 থেকে। যেকোনো ক্রমেই head-কে 14 আর 183 দুটিই ছুঁতে হবে, তাই [14, 183] পুরো অংশটি অন্তত একবার পেরোতে হবে — ১৬৯ cylinder. তার ওপর 53 থেকে প্রথমে যেদিকের প্রান্তে যাওয়া হবে, সেখান থেকে ফিরে আসার পথের কিছু অংশ দুবার পেরোতে হবে: আগে নিচে গেলে ৫৩ − ১৪ = ৩৯, আগে ওপরে গেলে ১৮৩ − ৫৩ = ১৩০. তাই যেকোনো ক্রমের মোট ≥ ১৬৯ + min(৩৯, ১৩০) = ২০৮. আর “আগে নিচে সবগুলো, তারপর ওপরে সবগুলো” ক্রমটি ঠিক ২০৮ দেয় — অর্থাৎ এই সারির সর্বনিম্ন ২০৮, আর সেটি পরের অংশের LOOK (0-এর দিকে) পায়। SSTF ধাপ ৩-এ লোভী সিদ্ধান্তে নিচে গিয়েছিল, কিন্তু 67-এর কাছ থেকে নামায় ফেরার পথ লম্বা হয়েছে। লোভী কৌশল প্রতিটি ধাপে সেরা, পুরো পথে নয়।

SSTF-এর starvation

বড় সমস্যাটি অবশ্য সংখ্যায় নয়, ন্যায্যতায়। বাস্তবে অনুরোধ একবারে আসে না, ক্রমাগত আসে। ধরুন head 50-এর আশপাশে, আর একটি ডেটাবেস 40 থেকে 60-এর মধ্যে একটানা অনুরোধ পাঠাচ্ছে। এর মধ্যে cylinder 190-এ একটি backup প্রোগ্রামের অনুরোধ এলো। SSTF প্রতিবার কাছের নতুন অনুরোধটিই বাছবে — 190-এর অনুরোধ যতক্ষণ কাছে নতুন অনুরোধ আসছে, ততক্ষণ সেবা পাবে না। এটি starvation — CPU scheduling-এর SJF-এর মতোই। ফল: দীর্ঘ tail latency. প্রতিকার দুই রকম: অপেক্ষার সময় অনুযায়ী অগ্রাধিকার বাড়ানো (aging, বা Linux-এর mq-deadline-এর মতো প্রতিটি অনুরোধে একটি সময়সীমা), অথবা head-কে একদিকে চলতে বাধ্য করা — পরের অংশের SCAN পরিবার।

৪ · SCAN, C-SCAN, LOOK আর C-LOOK — লিফটের নিয়ম

SCAN algorithm-এ head একদিকে চলতে চলতে পথের সব অনুরোধ সেরে ডিস্কের প্রান্ত পর্যন্ত যায়, তারপর দিক উল্টে ফেরার পথে বাকিগুলো সারে। লিফটের সাথে মিলের জন্য একে elevator algorithm-ও বলে। কোনো অনুরোধ সর্বোচ্চ প্রায় দুটি পূর্ণ যাত্রার বেশি অপেক্ষা করে না — starvation নেই।

চারটির পূর্ণ trace (ক্লাসিক queue, head 53)

SCAN-এর হিসাবের একটি শর্টকাট: 0-এর দিকে গেলে মোট = (৫৩ − ০) + (১৮৩ − ০) = ৫৩ + ১৮৩ = ২৩৬ — নিচে প্রান্ত পর্যন্ত, তারপর প্রান্ত থেকে সবচেয়ে ওপরের অনুরোধ পর্যন্ত। LOOK একই পথ, কিন্তু 14-এ ঘোরে: (৫৩ − ১৪) + (১৮৩ − ১৪) = ৩৯ + ১৬৯ = ২০৮ — অংশ ৩-এর সর্বনিম্ন সীমা। C-SCAN (ওপরে): (১৯৯ − ৫৩) + ১৯৯ + ৩৭ = ১৪৬ + ১৯৯ + ৩৭ = ৩৮২; লাফ বাদে ১৪৬ + ৩৭ = ১৮৩.

SCAN বনাম C-SCAN — head-এর পথ পাশাপাশি

তুলনা ন্যায্য রাখতে নিচের stepper-এ দুটিই শুরুতে ওপরে (199-এর দিকে) চলছে। দুই রেখায় H হলো head, o হলো এখনো অপেক্ষমাণ অনুরোধ (৪০ ঘরের রেখায় আনুমানিক অবস্থান, তাই 65/67 আর 122/124 এক ঘরে পড়ে)।

তাহলে C-SCAN কেন?

বাস্তবে অনুরোধ ক্রমাগত আসে, আর ডিস্কজুড়ে মোটামুটি সমানভাবে ছড়ানো থাকে। SCAN একটি প্রান্তে পৌঁছে দিক উল্টালে তার ঠিক পেছনের অংশ মাত্রই সেরে এসেছে — সেখানে নতুন অনুরোধ কম জমেছে। সবচেয়ে বেশি অনুরোধ জমে আছে অন্য প্রান্তে, যারা সবচেয়ে দীর্ঘ সময় অপেক্ষা করছে। C-SCAN (circular SCAN) ডিস্ককে একটি বৃত্তের মতো দেখে: সবসময় একদিকে সেবা, শেষে দ্রুত ফেরা। প্রতিটি cylinder প্রতি চক্রে ঠিক একবার সুযোগ পায় — অপেক্ষার সময় বেশি সমান, বিনিময়ে মোট পথ কিছুটা বেশি।

LOOK আর C-LOOK একই ধারণার ব্যবহারিক রূপ — শেষ অনুরোধ পেরিয়ে খালি প্রান্ত পর্যন্ত যাওয়ার কোনো কারণ নেই। বাস্তবে “SCAN” বা “elevator” বলে যা চালানো হয়, তা প্রায় সবসময় LOOK-এর মতো।

সব নিয়মে সব সংখ্যা — simulator

নিচের simulator ছয়টি algorithm চালায়। DIR ঠিক করে SCAN-পরিবার প্রথমে কোন দিকে যাবে, COUNT_RETURN ঠিক করে C-SCAN/C-LOOK-এর ফেরার লাফ গোনা হবে কি না। প্রথমে নির্বাচিত নিয়মে পুরো trace ছাপে, তারপর চার রকম নিয়মে সব মোটের একটি টেবিল।

// Disk-scheduling simulator: FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK.
const queue = [98, 183, 37, 122, 14, 124, 65, 67];
const head = 53, MAX = 199;              // cylinders 0..199
const DIR = "down";                      // "down" = move toward 0 first, "up" = toward 199
const COUNT_RETURN = true;               // count the C-SCAN / C-LOOK return jump?
const ALGS = ["FCFS", "SSTF", "SCAN", "C-SCAN", "LOOK", "C-LOOK"];
function order(alg, dir) {
  const lo = queue.filter(c => c < head).sort((a, b) => b - a);   // nearest first
  const hi = queue.filter(c => c >= head).sort((a, b) => a - b);
  const [first, second] = dir === "down" ? [lo, hi] : [hi, lo];
  const edge = dir === "down" ? 0 : MAX, far = MAX - edge;
  if (alg === "FCFS") return [...queue];
  if (alg === "SSTF") { const left = [...queue], out = []; let h = head;
    while (left.length) {                // nearest first; a tie goes to the smaller cylinder
      left.sort((a, b) => Math.abs(a - h) - Math.abs(b - h) || a - b);
      h = left.shift(); out.push(h); }
    return out; }
  if (alg === "SCAN") return [...first, edge, ...second];
  if (alg === "LOOK") return [...first, ...second];
  if (alg === "C-SCAN") return [...first, edge, "jump", far, ...second.reverse()];
  return [...first, "jump", ...second.reverse()];                 // C-LOOK
}
function run(alg, dir, countReturn, show) {
  let h = head, total = 0, jump = false; const parts = [], seq = [];
  for (const c of order(alg, dir)) {
    if (c === "jump") { jump = true; continue; }
    const d = Math.abs(c - h);
    if (jump && !countReturn) parts.push("[" + d + " not counted]");
    else { total += d; parts.push(jump ? "[" + d + " return]" : d); }
    jump = false; h = c; seq.push(c);
  }
  if (show) console.log(alg.padEnd(6) + " order: " + seq.join(" ") +
    "\n       moves: " + parts.join(" + ") + "\n       total = " + total);
  return total;
}
for (const a of ALGS) run(a, DIR, COUNT_RETURN, true);
console.log("\nTotals  up+return  up,no-return  down+return  down,no-return");
for (const a of ALGS) console.log(a.padEnd(7) + [["up", true], ["up", false], ["down", true],
  ["down", false]].map(([d, r]) => String(run(a, d, r, false)).padStart(10)).join("    "));

FCFS   order: 98 183 37 122 14 124 65 67
       moves: 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2
       total = 640
SSTF   order: 65 67 37 14 98 122 124 183
       moves: 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59
       total = 236
SCAN   order: 37 14 0 65 67 98 122 124 183
       moves: 16 + 23 + 14 + 65 + 2 + 31 + 24 + 2 + 59
       total = 236
C-SCAN order: 37 14 0 199 183 124 122 98 67 65
       moves: 16 + 23 + 14 + [199 return] + 16 + 59 + 2 + 24 + 31 + 2
       total = 386
LOOK   order: 37 14 65 67 98 122 124 183
       moves: 16 + 23 + 51 + 2 + 31 + 24 + 2 + 59
       total = 208
C-LOOK order: 37 14 183 124 122 98 67 65
       moves: 16 + 23 + [169 return] + 59 + 2 + 24 + 31 + 2
       total = 326

Totals  up+return  up,no-return  down+return  down,no-return
FCFS          640           640           640           640
SSTF          236           236           236           236
SCAN          331           331           236           236
C-SCAN        382           183           386           187
LOOK          299           299           208           208
C-LOOK        322           153           326           157

তুলনা এক নজরে

লোড কম হলে (সারিতে ০–১টি অনুরোধ) সব algorithm একই; ভারী লোডে LOOK/C-LOOK ভালো ভারসাম্য দেয়।

৫ · বাস্তব সিস্টেমে — NCQ, Linux-এর I/O scheduler আর NVMe

ডিস্ক নিজেই সাজায় — NCQ

OS ডিস্কের আসল জ্যামিতি জানে না, আর platter এই মুহূর্তে কোন কোণে আছে, তা তো নয়ই। ডিস্কের firmware দুটিই জানে। তাই SATA ডিস্কে NCQ (Native Command Queuing) আছে: OS একসাথে সর্বোচ্চ ৩২টি অনুরোধ ডিস্কে পাঠাতে পারে, আর ডিস্ক নিজে ঠিক করে কোনটি আগে — seek আর rotational latency দুটিই হিসাব করে। SCSI/SAS ডিস্কে একই ধারণা আগে থেকেই ছিল (tagged command queuing). ফলে আধুনিক সিস্টেমে disk scheduling দুই স্তরে হয়: OS মোটামুটি সাজায় আর ন্যায্যতা দেখে, ডিস্ক শেষ মুহূর্তের সূক্ষ্ম সাজানোটা করে।

Linux-এর I/O scheduler

Linux-এর block layer (blk-mq, multi-queue) প্রতিটি ডিভাইসের জন্য একটি I/O scheduler বেছে নিতে দেয়। Linux 5.0 (২০১৯) থেকে পুরোনো single-queue পথ আর তার CFQ, deadline, noop scheduler সরিয়ে দেওয়া হয়েছে; এখন বিকল্প চারটি:

BFQ (Paolo Valente ও সহকর্মীরা) আর Kyber (Facebook-এর Omar Sandoval) দুটিই Linux 4.12-এ (২০১৭) kernel-এ আসে। কোন ডিভাইসে কোনটি ডিফল্ট, তা kernel version আর distro-র udev নিয়মের ওপর নির্ভর করে — নিজের মেশিনে দেখে নিন। নিচের bash প্রোগ্রাম ডিস্কগুলোর তালিকা, ঘোরা ডিস্ক কি না (ROTA = 1 মানে HDD), আর বর্তমান scheduler দেখায়। Container-এ চালালে ডিস্কের তথ্য লুকানো থাকতে পারে — প্রোগ্রাম সেটিও সামলায়।

echo "== lsblk =="
if command -v lsblk >/dev/null 2>&1; then
  lsblk -o NAME,ROTA,SIZE,SCHED 2>/dev/null | head -n 12 || echo "lsblk: no output here"
else
  echo "lsblk not installed"
fi
echo "== /sys/block =="
found=0
for d in /sys/block/*; do
  [ -e "$d" ] || continue
  found=1
  n=$(basename "$d")
  rot=$(cat "$d/queue/rotational" 2>/dev/null || echo "?")
  sch=$(cat "$d/queue/scheduler" 2>/dev/null || echo "?")
  echo "$n rotational=$rot scheduler=$sch"
done | head -n 12
[ -d /sys/block ] && [ -n "$(ls /sys/block 2>/dev/null)" ] || echo "/sys/block is empty or hidden here"

== lsblk ==
== /sys/block ==
loop0 rotational=1 scheduler=[none] mq-deadline
loop1 rotational=1 scheduler=[none] mq-deadline
loop2 rotational=1 scheduler=[none] mq-deadline
loop3 rotational=1 scheduler=[none] mq-deadline
loop4 rotational=1 scheduler=[none] mq-deadline
loop5 rotational=1 scheduler=[none] mq-deadline
loop6 rotational=1 scheduler=[none] mq-deadline
loop7 rotational=1 scheduler=[none] mq-deadline
loop8 rotational=1 scheduler=[none] mq-deadline
loop9 rotational=1 scheduler=[none] mq-deadline
sr0 rotational=1 scheduler=none [mq-deadline]
vda rotational=1 scheduler=[none] mq-deadline

নিজের Linux মেশিনে (container নয়) সাধারণত এমন কিছু দেখবেন — নমুনা, আপনার মেশিনে নাম ও সংখ্যা আলাদা হবে:

$ lsblk -o NAME,ROTA,SIZE,SCHED
NAME        ROTA   SIZE SCHED
sda            1   1.8T mq-deadline
nvme0n1        0 476.9G none
$ cat /sys/block/sda/queue/scheduler
[mq-deadline] kyber bfq none
$ echo bfq | sudo tee /sys/block/sda/queue/scheduler    # reboot হলে আগের অবস্থায় ফেরে
bfq

বন্ধনীর ভেতরেরটি এখন চলছে। স্থায়ীভাবে বদলাতে udev নিয়ম লাগে (অনুশীলন ৪)। Windows আর macOS-এ Linux-এর মতো ব্যবহারকারীর বাছাই করার scheduler-তালিকা নেই; সেখানে অনুরোধ সাজানো মূলত storage driver স্তর আর ডিস্কের firmware-এর কাজ, আর OS I/O priority-র মতো সুবিধা দেয়।

NVMe-তে কেন “none”

SSD-তে কোনো arm নেই — LBA 5 আর LBA 5,000,000 পড়ার খরচ প্রায় সমান, তাই “কাছের অনুরোধ আগে” কথাটির মানেই নেই। তার ওপর NVMe ডিভাইসে অনেকগুলো hardware queue থাকে, আর Linux সাধারণত প্রতিটি CPU core-কে নিজের queue দেয় — core-গুলো lock ছাড়াই সমান্তরালে অনুরোধ পাঠায়। Scheduler বসালে প্রতিটি অনুরোধে বাড়তি CPU খরচ আর lock-এর প্রতিযোগিতা যোগ হয়, যা কয়েক দশ µs-এর ডিভাইসে চোখে পড়ে। তাই ডিফল্ট none; তবে একই NVMe-তে কয়েকটি কাজের মধ্যে ন্যায্যতা বা latency-লক্ষ্য দরকার হলে kyber বা mq-deadline, আর cgroup-এর I/O নিয়ন্ত্রণ কাজে লাগে।

৬ · SSD-র ভেতরে — NAND flash, FTL আর garbage collection

একটি SSD-তে কোনো ঘোরা অংশ নেই। ডেটা থাকে NAND flash চিপে — কোটি কোটি ছোট cell, প্রতিটি একটি বিশেষ transistor, যার ভেতরে আটকে রাখা বৈদ্যুতিক চার্জের পরিমাণই ডেটা। বিদ্যুৎ চলে গেলেও চার্জ থেকে যায়, তাই ডেটা হারায় না।

প্রতি cell-এ কত বিট — SLC থেকে QLC

একটি cell-এ চার্জের কয়টি স্তর আলাদা করে চেনা যায়, তার ওপর নির্ভর করে সে কত বিট রাখে। বেশি বিট মানে একই চিপে বেশি ধারণক্ষমতা আর কম দাম — কিন্তু স্তরগুলো কাছাকাছি হয়ে যায়, তাই পড়া-লেখা ধীর, ভুল বেশি, আর cell কম বার লেখা সহ্য করে।

এখানে P/E cycle মানে একবার লেখা (program) আর একবার মোছা (erase). প্রতিটি cycle cell-এর অন্তরক স্তরকে একটু ক্ষয় করে; একসময় cell আর নির্ভরযোগ্যভাবে চার্জ ধরে রাখতে পারে না।

তিনটি নিয়ম, যা সব বদলে দেয়

1. পড়া আর লেখা হয় page ধরে — একটি page সাধারণত কয়েক KiB থেকে ১৬ KiB.
2. মোছা হয় শুধু erase block ধরে — একটি block-এ শত শত page, আকার কয়েক MiB পর্যন্ত। মোছা ধীর (ms-মাত্রার), পড়া মাইক্রোসেকেন্ড-মাত্রার।
3. একটি page আবার লেখার আগে তার পুরো block মুছতে হয়। অর্থাৎ জায়গায় বসে overwrite হয় না।

ভাবুন, OS বলল “LBA 1 বদলে নতুন ডেটা লেখো।” HDD হলে head সেই sector-এ গিয়ে লিখে দেয়। SSD-তে LBA 1 যে page-এ আছে, সেটি সরাসরি আবার লেখা যায় না; পুরো block মুছতে হলে সেই block-এর বাকি শত page-এর ডেটা আগে সরাতে হবে — একটি 4 KiB লেখার জন্য কয়েক MiB নড়াচড়া! সমাধান: নতুন ডেটা অন্য একটি ফাঁকা page-এ লেখা, আর পুরোনো page-কে “বাতিল” (invalid) চিহ্ন দেওয়া। কিন্তু তাহলে LBA 1 এখন কোথায়, সেই হিসাব কেউ রাখতে হবে।

Flash Translation Layer — SSD-র নিজের “page table”

সেই হিসাব রাখে FTL (flash translation layer) — SSD-র controller-এ চলা firmware. এটি প্রতিটি LBA-র জন্য লিখে রাখে, ডেটা এখন কোন physical page-এ। পর্ব ৩২-এর page table-এর সাথে মিলটি লক্ষ করুন: সেখানে virtual page → physical frame, এখানে LBA → flash page. OS ভাবে সে একটি সাধারণ ব্লক-ডিভাইসে নির্দিষ্ট ঠিকানায় লিখছে; ভেতরে প্রতিটি লেখা নতুন জায়গায় যায়।

নতুন জায়গায় লিখতে লিখতে একসময় ফাঁকা page ফুরোয়, আর অনেক block-এ জমে বাতিল page. তখন চলে garbage collection (GC): একটি block বাছা (সাধারণত যেটিতে সবচেয়ে কম valid page), তার valid page-গুলো অন্য ফাঁকা জায়গায় কপি করা, তারপর পুরো block মুছে ফাঁকা তালিকায় ফেরত দেওয়া। কপি করা page-গুলো হলো বাড়তি লেখা — host চায়নি, তবু NAND-এ লেখা হলো। এটিই write amplification.

নিচের stepper একটি খেলনা SSD দেখায়: ৩টি erase block (A, B, C), প্রতিটিতে ৪টি page. ঘরে সংখ্যা মানে সেই LBA-র বৈধ ডেটা, x মানে বাতিল page, . মানে ফাঁকা। FTL একটি block সবসময় GC-র জন্য খালি রাখে (বাস্তব SSD-ও এমন সংরক্ষিত জায়গা রাখে)।

Write amplification-এর সূত্র

WA = ১ মানে কোনো বাড়তি লেখা নেই; WA = ৩ মানে host-এর প্রতি ১ GB লেখায় flash-এ ৩ GB লেখা হচ্ছে, অর্থাৎ SSD-র আয়ু তিন গুণ দ্রুত খরচ হচ্ছে, আর GC-র কাজে host-এর লেখাও ধীর হচ্ছে।

একটি সরল মডেল: ধরুন প্রতিবার GC যে block বাছে, তার page-গুলোর u অংশ বৈধ (০ ≤ u < ১)। P page-এর block থেকে u·P page কপি করলে (P − u·P) page নতুন লেখার জন্য ফাঁকা হয়। অর্থাৎ (১ − u)·P page host-লেখার জন্য NAND-এ মোট P page লিখতে হয়:

উদাহরণ: ৬৪ page-এর একটি block-এ GC-র সময় ১৬টি বৈধ (u = ০.২৫)। ১৬টি কপি করে ৪৮টি ফাঁকা পাওয়া গেল, তাতে ৪৮টি host-লেখা — মোট NAND লেখা ৪৮ + ১৬ = ৬৪. WA = ৬৪ ÷ ৪৮ = ১ ÷ (১ − ০.২৫) ≈ ১.৩৩. Victim যদি ৭৫% বৈধ হয়, WA = ৪; ৯০% হলে ১০. Drive প্রায় ভরা থাকলে GC ভালো victim পায় না — WA লাফিয়ে বাড়ে। (বাস্তব FTL আরও জটিল; এটি শুধু প্রবণতা বোঝার মডেল।)

নিচের প্রোগ্রাম stepper-এর খেলনা SSD-টিই চালায় — page-level FTL আর “সবচেয়ে কম বৈধ page” নীতির GC — আর শেষে সূত্রের কয়েকটি মান ছাপে।

// Toy SSD: 3 erase blocks x 4 pages, page-level FTL, greedy garbage collection.
const PAGES = 4, nand = [[], [], []];       // each block: list of {lba, valid}
const map = {};                             // FTL map: LBA -> [block, page]
let host = 0, flash = 0, active = 0;
const free = () => nand.filter(b => b.length === 0).length;
function program(lba) {                     // NAND pages are written once: append only
  if (nand[active].length === PAGES) active = nand.findIndex(b => b.length === 0);
  if (map[lba]) { const [b, p] = map[lba]; nand[b][p].valid = false; }  // old copy dies
  nand[active].push({ lba, valid: true });
  map[lba] = [active, nand[active].length - 1]; flash++;
}
function gc() {                             // victim = full block with fewest valid pages
  let v = -1;
  nand.forEach((b, i) => { if (b.length === PAGES && i !== active &&
    (v < 0 || b.filter(x => x.valid).length < nand[v].filter(x => x.valid).length)) v = i; });
  const live = nand[v].filter(x => x.valid).map(x => x.lba);
  active = nand.findIndex(b => b.length === 0);  // the reserved free block
  for (const lba of live) program(lba);     // copy valid pages: extra NAND writes
  nand[v] = [];                             // erase the whole block
  console.log("  GC: block " + "ABC"[v] + " had " + live.length + " valid pages (LBA " +
    live.join(",") + ") -> copied, block erased");
}
function write(lba) {                       // keep one free block in reserve for GC
  host++;
  if (nand[active].length === PAGES && free() <= 1) gc();
  program(lba);
}
const show = (t) => console.log(t.padEnd(22) + nand.map((b, i) => "ABC"[i] + "[" +
  [0, 1, 2, 3].map(p => b[p] ? (b[p].valid ? b[p].lba : "x") : ".").join(" ") + "]").join(" ") +
  "  host=" + host + " nand=" + flash);
for (const l of [0, 1, 2, 3]) write(l); show("write LBA 0-3");
for (const l of [1, 2]) write(l); show("overwrite LBA 1,2");
for (const l of [4, 5]) write(l); show("write LBA 4,5");
for (const l of [6, 7]) write(l); show("write LBA 6,7");
console.log("WA = NAND writes / host writes = " + flash + "/" + host + " = " + (flash / host).toFixed(2));
for (const u of [0.25, 0.5, 0.75, 0.9]) console.log("victim " + u * 100 + "% valid -> WA = 1/(1-u) = " + (1 / (1 - u)).toFixed(2));

write LBA 0-3         A[0 1 2 3] B[. . . .] C[. . . .]  host=4 nand=4
overwrite LBA 1,2     A[0 x x 3] B[1 2 . .] C[. . . .]  host=6 nand=6
write LBA 4,5         A[0 x x 3] B[1 2 4 5] C[. . . .]  host=8 nand=8
  GC: block A had 2 valid pages (LBA 0,3) -> copied, block erased
write LBA 6,7         A[. . . .] B[1 2 4 5] C[0 3 6 7]  host=10 nand=12
WA = NAND writes / host writes = 12/10 = 1.20
victim 25% valid -> WA = 1/(1-u) = 1.33
victim 50% valid -> WA = 1/(1-u) = 2.00
victim 75% valid -> WA = 1/(1-u) = 4.00
victim 90% valid -> WA = 1/(1-u) = 10.00

Wear leveling, TRIM আর over-provisioning

• Wear leveling: কিছু LBA বারবার লেখা হয় (log, metadata), কিছু বছরের পর বছর বদলায় না (সিনেমা, OS-এর ফাইল)। FTL লেখাগুলো সব block-এ ছড়িয়ে দেয়, আর মাঝে মাঝে “ঠান্ডা” ডেটাকেও বেশি-ক্ষয় হওয়া block থেকে সরিয়ে কম-ক্ষয় হওয়া block-এ রাখে (static wear leveling), যাতে সব block মোটামুটি সমানভাবে বুড়ো হয়। এর দামও বাড়তি লেখা।
• TRIM / discard: আপনি একটি ফাইল মুছলে file system শুধু নিজের হিসাবে block-গুলো “ফাঁকা” লেখে; SSD জানে না। FTL-এর চোখে সেই page-গুলো এখনো বৈধ — GC সেগুলো বারবার কপি করবে! TRIM হলো OS-এর পক্ষ থেকে SSD-কে জানানো “এই LBA-গুলোর ডেটা আর লাগবে না।” ATA-তে TRIM, SCSI-তে UNMAP, NVMe-তে Deallocate নামে। Linux-এ fstrim (অনেক distro-তে সাপ্তাহিক fstrim.timer) বা mount-এর discard বিকল্প; Windows-এ “Optimize Drives” TRIM পাঠায়, আর fsutil behavior query DisableDeleteNotify-এর ফল 0 মানে TRIM চালু।
• Over-provisioning: SSD-তে বিক্রির ধারণক্ষমতার চেয়ে বেশি flash থাকে — বাড়তি অংশ ব্যবহারকারী দেখেন না, FTL GC আর খারাপ block বদলানোর জন্য রাখে। যত বেশি ফাঁকা জায়গা, GC তত বেশি বাতিল-ভরা victim পায় (u কম), WA তত কম। Enterprise SSD প্রায়ই বেশি over-provisioning রাখে; ভোক্তা হিসেবে আপনিও ড্রাইভ পুরো ভরে না রেখে একই সুবিধা পান।

৭ · NVMe আর গতির মাত্রা — HDD, SATA SSD, NVMe

প্রথম দিকের SSD-গুলো SATA সংযোগে বসানো হতো — যে interface ঘোরা ডিস্কের জন্য বানানো। SATA-র AHCI নিয়মে একটি মাত্র command queue, তাতে সর্বোচ্চ ৩২টি অনুরোধ; আর SATA III-এর তারের গতি ৬ Gb/s, বাস্তবে প্রায় ৫৫০ MB/s-এর কাছাকাছিতে আটকে যায়।

২০১১ সালে NVMe (Non-Volatile Memory Express) স্পেসিফিকেশনের প্রথম সংস্করণ আসে, সরাসরি PCIe-র ওপর flash-এর জন্য নকশা করা। এর কেন্দ্রে জোড়া queue: একটি submission queue, যেখানে host অনুরোধ রাখে, আর একটি completion queue, যেখানে ডিভাইস ফল জানায় — দুটিই RAM-এ রাখা ring, ঠিক পর্ব ৫-এ দেখা io_uring-এর ধাঁচে। স্পেসিফিকেশন অনুযায়ী সর্বোচ্চ প্রায় ৬৪ হাজার I/O queue, প্রতিটিতে প্রায় ৬৪ হাজার অনুরোধ রাখা যায়; বাস্তব ডিভাইস এর অনেক কম queue দেয়, আর Linux সাধারণত প্রতিটি CPU core-কে একটি করে দেয়। কোনো core-কে অন্য core-এর সাথে lock ভাগ করতে হয় না।

নিচের টেবিল মাত্রা বোঝানোর জন্য — নির্দিষ্ট মডেল, queue depth আর workload অনুযায়ী আসল সংখ্যা অনেক বদলায়।

HDD থেকে NVMe-তে latency কমেছে প্রায় হাজার গুণ — এখন OS-এর নিজের সফটওয়্যার-পথই মোট সময়ের লক্ষণীয় অংশ (ভাবনার প্রশ্ন ০৪)।

৮ · ডিস্ক প্রস্তুত করা — formatting, partition, boot block, bad block আর সংযোগ

তিন স্তরের formatting

1. Low-level (physical) formatting: platter-এ track আর sector-এর কাঠামো, প্রতিটি sector-এর header আর ECC-র জায়গা বসানো। আধুনিক ডিস্কে এটি কারখানাতেই হয়ে আসে; ব্যবহারকারী আর করেন না।
2. Partitioning: ডিস্ককে এক বা একাধিক partition-এ ভাগ করা — হিসাব থাকে MBR বা GPT partition table-এ। প্রতিটি partition OS-এর কাছে আলাদা ডিস্কের মতো।
3. Logical formatting: একটি partition-এ file system তৈরি করা — superblock, free-space-এর হিসাব, প্রথম directory (Linux-এ mkfs.ext4, Windows-এ Format). এর ভেতরের কাঠামো আসবে পর্ব ৪৩-এ। কিছু database file system ছাড়াই সরাসরি partition (raw disk) ব্যবহার করতে পারে।

Boot block

কম্পিউটার চালু হলে firmware-কে জানতে হয় কোথা থেকে OS শুরু করবে। BIOS-এর যুগে ডিস্কের প্রথম sector — boot sector, LBA 0-এর MBR — একটি ছোট boot code রাখত, যা পরের ধাপের bootloader আনত। UEFI-তে বুটের ফাইল থাকে একটি আলাদা FAT partition-এ (ESP). বিস্তারিত পর্ব ৭ · বুট প্রক্রিয়া-য়।

Bad block — খারাপ জায়গা লুকানো

কোনো চৌম্বক স্তর নিখুঁত নয়; কারখানাতেই কিছু খারাপ sector থাকে, ব্যবহারের সময় আরও তৈরি হয়। আধুনিক ডিস্ক নিজেই সামলায়: কারখানায় কিছু অতিরিক্ত (spare) sector রেখে দেওয়া হয়। কোনো sector খারাপ হলে controller তার LBA-কে একটি spare sector-এ পাঠিয়ে দেয় — sector sparing (forwarding). এতে একটি অসুবিধা: OS-এর scheduler যে LBA-কে পাশাপাশি ভাবছে, তার একটি আসলে অন্য cylinder-এ — তাই অনেক ডিস্ক প্রতিটি cylinder-এ কিছু spare রাখে। আরেক কৌশল sector slipping: খারাপ sector-এর পরের সব sector এক ঘর সরিয়ে দেওয়া, যাতে ক্রম অটুট থাকে। SSD-তে একই কাজ FTL করে — খারাপ block বাদ দিয়ে over-provisioning-এর block বসায়।

Reallocated sector-এর সংখ্যা ডিস্কের S.M.A.R.T. তথ্যে দেখা যায় (Linux-এ smartctl -a /dev/sda, root লাগে)। এই সংখ্যা বাড়তে থাকা ডিস্ক বদলানোর একটি সতর্কসংকেত — ব্যাকআপ আগে নিশ্চিত করুন।

ডিস্ক কোথায় লাগানো — DAS, NAS, SAN আর ক্লাউড

চাবি: NAS ফাইল দেয়, তাই file system চলে সার্ভারে; SAN আর ক্লাউড block storage ব্লক দেয়, তাই file system চলে আপনার মেশিনে। একাধিক ডিস্ক মিলিয়ে নির্ভরযোগ্যতা — RAID — পর্ব ৪৫-এ।

৯ · AI-এর যুগে ডিস্ক আর SSD

Disk scheduling-এর অঙ্ক আর storage-এর পরামর্শ — দুটিতেই AI দ্রুত উত্তর দেয়, আর দুটিতেই নিয়মিত ভুল করে:

AI-এর উত্তর মানার আগে — চেকলিস্ট

• দিক, প্রান্ত ছোঁয়া আর ফেরার লাফ — তিনটি নিয়ম উত্তরে লেখা আছে কি না দেখেছি
• প্রতিটি ধাপের দূরত্ব নিজে যোগ করে মোট মিলিয়েছি; FCFS ৬৪০ আর SSTF ২৩৬-এর মতো জানা উত্তর দিয়ে AI-এর simulator আগে পরীক্ষা করেছি
• কোনো মোট অংশ ৩-এর সর্বনিম্ন সীমার (এই queue-তে ২০৮) চেয়ে কম এলে নিশ্চিত ভুল ধরে নিয়েছি
• Access time-এর অঙ্কে একক (ms, µs; MB = ১০^৬ না ২^২০) আর “গড় latency = অর্ধেক পাক” মিলিয়েছি
• I/O scheduler বা sysctl বদলের পরামর্শ — কোন kernel version, কোন distro, কোন ডিভাইস — ডকুমেন্টেশনে মিলিয়েছি, আর fio-র মতো টুলে আগে-পরে মেপেছি
• dd, mkfs, fdisk বা sudo-ওয়ালা কোনো কমান্ড ডিভাইস নাম যাচাই আর ব্যাকআপ ছাড়া চালাইনি