Operating Systems Lecture Notes

2014 November 6 • Massed Storage

---

Outline

Disks again. Performance effects. Multiplicity and RAID. Latency

Motivations

• Insatiable demand for more storage.
  • More data being created.
  • Analysis ranging longer time periods.
• More components mean more failures.
  • One disk: five years between failures.
  • 100 disks: three weeks between failures.
• Redundancy to the rescue.

Exploiting The Multitude

• Making an excessively big, fast disk is hard and expensive.
• Collecting an equivalent bunch of small cheap disks is easy.
• But how are a bunch of small, cheap disks arranged into a big, fast disk-equivalent?
• This is the problem solved by RAID (redundant array of inexpensive disks).
  • Marketing: “inexpensive” → “independent.”

Combining Disks

• The “big” part of “big, fast” seems easy.
  • Tying the disks together is essentially a mechanical problem.
• The “fast” part seems less obvious.
• There are two performance hits: latency and delay.
  • Latency: how long to get the first bit?
  • Delay: how long to get the last bit?

The Performance Problem

• Reducing latency is usually hard.
  • Requires juggling fundamental limits.
  • Usually impossible, always expensive.
• Consider delay: how can n disks deliver the last bit more quickly?

Exploiting Parallelism

• Reading a page from a disk takes time t.

  

• Reading a page from n disks takes time t/n.

  

An Alternative

• But what about reading several pages at the same time?

  

• This works if the page demand is high, and the page mapping is clever.

Data Striping

• Data striping exploits multiple disks using parallelism.
• Bit striping writes bytes to a factor or multiple of eight disks.
  • Disk i gets bit i of each byte.
• Block striping writes associated blocks across the disks.
  • Block i goes to disk i mod n.
• There are many striping variants.

Striping Advantages

• Striping (block striping, mostly) exploits multiplicity to provide
  • Load balancing: smearing pages across disks reduces per-disk queuing.
    • No queuing improves small request throughput.
  • Parallelism: smearing associated pages across disks improves large request throughput.

Technology Advances

• Improving storage technology makes “big fast” less difficult.
• But electromechanical devices like disks still fail.
• The more disks are piled up, the more likely one of them’s going to fail.
• Fortunately, reliability comes from redundancy.
  • And having many disks means much redundancy.

RAID Reliability

• RAID: redundant array of independent disks.
• RAID exploits the redundancy possible with many disks to provide reliability.
  • This trades-off performance for reliability.
• The RAID level determines how a RAID device
  • resolves the performance-reliability trade-off, and
  • exploits redundancy to get reliability.

Raid Levels

• Raid levels differ in technology used.

  Raid 0:		striping
  Raid 1:		mirroring
  Raid 2:		Error-correcting storage.
  Raid 3:		bit-interleaved parity.
  Raid 4:		block-interleaved parity.
  Raid 5:		block-interleaved distributed parity.
  Raid 6:		P+Q redundancy.
  Raid 0+1:		striping and mirroring.

• And then there's marketing.

RAID 0 and 1

• RAID 0 has no redundancy.
  • All disks are used to store data.
• Raid 1 uses mirroring.

• RAID 1 has a 100% overhead.

Error Detection

• Single bit-flip errors have highest probability: 1 → 0 or 0 → 1.
• Parity counts 1 bits in a byte (bit string).

  An even number of 1s: even (0) parity.
  An odd number of 1s: odd (1) parity.

• Single-bit parity detects single-bit errors.

  01010101+0		01010101+0
  \(\downarrow\)		\(\downarrow\)
  01011101+0		01001101+0

Error Correction

• Parity detects but can’t correct a bit flip.
• Correcting a bit flip requires three extra (non-parity) bits.

  00+000 01+011 10+101 11+110

• This is known as an error-correcting code (ECC).

RAID 2

• RAID 2 disks bit-stripe bytes across seven disks.

  

  • Four data disks and three parity disks.
• The disk set forms an ECC over the data disks.
• The three-disk overhead varies with the data disks, but is usually less than RAID 1.

RAID 3

• External error detection makes possible one-bit error recovery.

  010?0101+0 → 01010101+0

• Modern disks provide sector-level error detection.
• RAID 3 uses n - 1 data disks and a parity disk for reliability.
  • Bit-striped bytes, but sector-level recovery.

But What of Latency?

• Reducing latency via technology is hard and expensive.
  • Not so delay.
• Latency usually responds to cleverly using current technology.
  • Load balancing, for example.
• File systems are mainly responsible for reducing latency.

Summary

• Disks provide an array abstraction with (cylinder, track, sector) addressing.
  • And involve persistence.
• Good performance requires handling latency and delay.
• Delay can be handled simply (more or less) with redunpdancy.
  • From there come RAID devices.
• Handling latency is the file system’s responsibility.

Credits

• Papertape3.jpg from the Wikimedia Commons under a Creative Commons BY SA license.

---

This page last modified on 2011 October 9.