Advanced Programming I Lecture Notes

4 May 2006 • Data Structures and Algorithms for Flash Storage

Outline

• Outline

• Flash storage

  • History and properties.

  • Structure and behavior.

• Flash storage uses and objectives.

• Block mapping.

• Block reclamation.

• Flash-Specific Applications

Flash Storage

• Flash storage is a type of electronically erasable programmable read-only memory (or EEPROM).

• Invented in 1984 by Fujio Masuoka at Toshiba.

• Marketed in 1988 by Intel.

• Widespread by the early 90s.

Flash Properties

• Persistence and fatigue are two important flash-storage properties.

• Persistence: data in flash storage can be retained without power.

• Fatigue: Flash storage becomes unreliable after it's been written 10,000 to a million times.

  • It also gets slower as it degrades.

  • Flash-storage reads do not cause fatigue.

The Storage Hierarchy

• Flash storage sits between main (primary) and disk (secondary) storage.

  	mbyte/sec		mbyte/$
  DRAM	160		9
  Flash	60		26
  Disk	46		1230

• DRAM: 60 ns, 512 mbytes.

• Flash: 512 mbytes USB 2.

• Disk: 160 gbytes, 5400 rpm USB.

Patents

• Most information on flash storage is available through patents.

• Patents are supposed to (among other things)

  • advance knowledge or practice by non-obvious novelty,

  • describe the advance in reproducible detail.

• As a pratical matter, patents may

  • advance by trivialities, and

  • be unclear on crucial details.

Flash Storage Structure

• Flash storage is organized as a sequence of blocks called erase units.

  • An erase unit contains from a few to a few 100 kbytes.

• An erase unit is divided into a sequence of pages of around 512 bytes per page.

I-O Behavior

• Flash storage is a block structured device, similar to disks.

• I-O requires buffering a block (page or erase unit) in main storage.

  1. Read the block of interest into a buffer.

  2. Perform the read or write to or from the buffer.

  3. Write back the buffer (on a write to the buffer).

Flash Write Behavior

• Flash write behavior is asymmetric based on the data being written

• Individual flash-storage bits can be cleared (set from 1 to 0).

• All the bits in an erase unit can be set (set from 0 to 1).

  • This operation is known as an erasure.

Zero-Write Example

One-Write Example

Reliable Clearing

• Bits on a page can be reliably cleared only a few times between successive erasures.

  • This is separate from overall flash storage fatigue.

  • It contributes to overall fatigue.

• The page write cycle is

  erase, write₁, ..., write_n, erase, ...

  for some small n.

Summary

• Individual bits can be cleared to 0 at page level.

• All bits can be set to 1 (erased) at erase-unit level.

• Successive erasures ensure reliable clearing.

• Overall write reliability decreases with the total number of writes.

Flash Storage Uses

• At increasing levels of abstraction, flash storage has three main uses:

  1. A block-storage replacement for disks.

  2. A flash-specific file system.

  3. Application-specific storage.

     • Search data structures, executable code.

Block-Storage Objectives

• The two main objectives for block-storage flash are:

  1. Abstract away the low-level erase-unit-page differences, presenting only disk-like blocks.

  2. Evenly distribute writes to get steady, predictable degradation.

• Both these objectives can be met using various wear-leveling techniques.

Block Mapping

• Introduce a level of indirection, called block mapping, between applications and flash storage.

• Block mapping

  • Provides applications with a fixed block array.

  • Organizes flash-storage pages into sectors.

  • Maps between blocks and sectors.

• Most wear-leveling techniques are variations on block mapping.

Block-Mapping Example

Direct Mapping

• The block mapper should map block numbers to segment numbers.

  • This is the direct map.

  • dm[i] is the segment number holding block i.

• The direct map changes frequently.

  • Frequent changes and flash storage don't play well.

• Read the direct map to start and write it at the end.

Removable Media

• Flash storage is frequently packaged as removable media.

  • Camera smart cards, USB flash drives.

• Unplugging a flash device without writing back the direct map trashes the device.

  • This is a problem on Unix, but not on Windows.

• A similar problem exists for power failures.

Inverse Mapping

• The inverse map determines the block number represented by a segment.

  • Segment i represents the block im[i].

• A segment's inverse mapping changes less frequently than does a block's direct mapping.

• On initialization the direct map can be constructed in RAM from the indirect map in flash storage.

Version Numbers

• Over time, many segments will represent the same block.

  • Which segment representing block i is the most recent?

• Store a version number along with the block index for each segment.

  • Each non-free segment is associated with a pair (bi, vn).

  • The current segment has the largest vn.

Map Storage

• The segment pair (bi, vn) can be stored

  • on a header for each segment, or

  • in directory pages for the erase unit.

Erase Units

• An erase unit gradually fills up with spent pages.

  • It may also contain some active and free pages.

• Once full of spent pages, an erase unit is reclaimed (garbage collected) by erasing it.

  • Any active pages have to be copied to other erase units.

Reclamation Steps

• Select one or more erase units for reclamation.

• Copy active pages to other, non-selected erase units.

• Erase the selected units.

• Reconstruct header and other infrastructure pages if needed.

• Add the units to the free list.

Reclamation Policies

• Reclamation policies determine

  • When reclamation should occur.

  • Which erase units should be reclaimed.

  • Which non-selected units get copies of active pages.

• The reclamation policies should mesh with other active policies, including the sequence-allocation policy.

Reclamation Timing

• Reclamation can be performed

  • on demand when triggered (garbage collection),

  • in background when the system is otherwise idle (scavenging).

• The choice between demand and background is system and application dependent.

Reclamation for Wear

• Reclamation can be used to even-out erase-unit wear patterns.

  • The idea is to have each erase unit exhibit average wear with low variance.

• Reclamation for wear and for space interact.

  • Reclaiming for wear introduces "unnecessary" reclamations.

  • Reclaiming for space should reduce and even-out wear.

Space vs. Wear

• Reclamation for space.

  

• Reclamation for wear.

  

• Assume full unit = many writes = high wear.

Simple Reclamation

• Prerequisites:

  • A spare erase unit.

  • The erase count for each unit.

• If erase unit E has low space or high wear:

  • Find erase unit E' with low wear.

  • Copy E' to the spare, then E to E'.

  • Erase E and make it the spare.

Deferred Erasure

• Maintain a priority queue of erase units ordered by erase counts.

• To reclaim:

  • Remove the unit at the queue head (least erased unit).

  • Erase and use the dequeued unit.

  • Copy active pages from the spent to the new unit.

  • Hang the spent unit on the queue.

Avoiding Erase Counts

• Maintaining erase counts requires writing.

• Avoid erase counts by:

  • Randomly selecting erase units to reclaim.

    • Spread wear evenly in the long term.

  • Deduce wear history from erase behavior.

    • Erase time is proportional to erase frequency.

    • More erasures means longer erasures.

Space + Wear Reclamation

• Rather than choose between, combine space and wear reclamation in one policy.

• Assign a score to each erase unit, then recover units with extreme score values.

• The unit score is a weighted combination of costs and benefits.

  • The costs are erasures and data-structure updating.

  • The benefits are free pages and even wear.

Example Combination

• Reclamation benefit is the amount of free pages recovered.

• The cost is the number of active pages copied.

• The weight is the time since last erasure.

  S = P_spent/(TP_active)

  • Large S indicates many spent pages.

  • Small S indicates many active pages or long-lived (stable) active pages (or both).

General Combinations

• Erase unit j has the score

  Sj	= a × spentj
  	+ (1 - a) × (max(erasuresp) - erasuresj)

• The parameter 0 ≤ a ≤ 1 determines the relative importance of space vs wear.

  • a near 0 for space, a near 1 for wear.

Flash-Specific Applications

• To operate well, flash-storage management needs specific information.

• Generic block-storage management can only provide general information.

  • And historic infomration at that.

• Better information comes with more knowledge of how specific applications use flash storage.

• Applications can also be adapted to fit better with flash storage characteristics.

References

• Algorithms and Data Structures for Flash Memories by Eran Gal and Sivan Toledo in ACM Computing Surveys, June, 2005.

• Development of the magnetic tunnel junction MRAM at IBM: From first junctions to a 16-Mb MRAM demonstrator chip by William Gallagher and Stuart Parkin in the IBM Journal of Research and Development, January 2006.