Wear Leveling in Flash Storage: Dynamic and Static Methods from Early Patents to JFFS2 and Static Leveling (1992-2007)

Short answer: wear leveling began as part of the mapping layers that let flash imitate a disk, and the split into dynamic and static leveling is visible in the sources from the early 1990s but became a named, separately patented problem only around 2001 to 2007. Intel's Wells patent (application of October 1992, continuation filed November 1993) already says that blocks holding programs are rewritten very rarely while blocks holding changing data are cleaned more and more often, and ranks blocks by a weighted mix of invalid sectors and erase count. Cirrus Logic's 1993 filing adds per-block erase counters and an erase-inhibit flag. Axis's JFFS, released in late 1999, levelled perfectly by rewriting all data on every pass until JFFS2 replaced that with a one-in-a-hundred pick of a block holding only valid data. M-Systems' 2001 filing calls static areas the problem that the earlier methods leave open, and a 2007 design paper adds a bit-table static leveler whose memory need is a few tens to a few thousand bytes (the authors' figures).

The problem the methods answer, 1993 to 2001. Gal and Toledo say flash cells can be written only 10,000 to 1,000,000 times before they wear out, that bits can only be cleared by a write and set again only by erasing a whole erase unit of several to hundreds of kilobytes, and that if blocks are mapped straight onto flash addresses the frequently used erase units wear out quickly. Woodhouse gives 100,000 erases per block as the typical lifetime, with 128 KiB blocks on NOR flash and 8 KiB on NAND, and Kawaguchi et al. call 100,000 erasures 'not unusual'. Wells's patent estimates that erasing took one to two seconds and that switching began to slow after about ten thousand operations, with about one hundred thousand needed before the slowing affected the system. M-Systems' 2001 patent says vendors state the program and erase endurance as a number from tens of thousands to a million (a vendor statement). Gal and Toledo add a second reason for the same mapping: with 4 KB file-system blocks and 128 KB erase units, an identity mapping would copy a whole erase unit for each small write and could lose 128 KB if power failed during the rewrite.

The shared basis: write somewhere else and keep a map. Gal and Toledo describe the idea behind all the wear-leveling techniques as mapping the host's block number to a physical sector and writing the new data to another sector on each update. The 1992 to 1993 patents say the same in their own words: Wells describes a lookup table that records where a logical sector currently sits, with the old position marked dirty and a later 'clean up' that moves the valid data out of a dirty block and erases it, which can happen in the background; Ban's M-Systems patent (filed 8 March 1993) describes a virtual map that lets data be written continuously to unwritten physical locations; and the Cirrus Logic patent describes a map from logical to physical block address with flags for defective, used and old blocks. Gal and Toledo say the Flash Translation Layer was originally patented by Ban and later adopted as a PCMCIA standard, citing an Intel application note that was not opened here. Hitachi's 1995 driver used the same mapping inside a log-structured design, and its authors say plainly that their prototype 'does not implement wear-leveling'.

1992 to 1996: the first patents that weigh erase counts. Wells's patent states the static-data problem before the term existed: it says studies indicate that 'certain areas of a flash memory array such as those blocks in which application programs are stored are subject to very infrequent rewriting', that blocks with rapidly changing data are cleaned more often, and that 'a block containing data initially subject to rapid change will automatically be subject to additional rapid change due to the nature of the data architecture'. Its claims choose the block to clean by a score that weights the number of invalid sectors against the block's erase count, with weights of 0.8 and minus 0.2 when space is needed and 0.2 and minus 0.8 when a cleanup is not required but time is available, the second mode being triggered by a difference of 500 or more erase operations between blocks (Gal and Toledo describe the same score and threshold). Cirrus Logic's patent keeps an erase counter for each block with a programmable maximum: when a block reaches one below the maximum it is erased one last time, written with the file that then has the smallest count and protected from further erasing by an erase-inhibit flag, and when all blocks approach the maximum the counters and flags are cleared. Gal and Toledo describe a sibling Cirrus Logic patent that stores a bounded 8-bit unary erase counter on a different erase unit so that no erase is needed to update it, and they list other approaches in the same period: a relocation through a spare unit, triggered when reclaiming a heavily worn unit whose erase count exceeds that of the least worn unit by a threshold (Lofgren et al., a SanDisk and Western Digital patent; the example threshold is 15,000), an upper bound on wear kept in a queue of erase candidates (Jou and Jeppesen), ranking units by how long erasing takes, which grows with wear in some devices (Han, LG), and swapping the most and least worn units when their counts differ by 100 (Wu and Zwaenepoel's eNVy, 1994, which Gal and Toledo describe and which was not opened here).

A disagreement about Wells. Ban's 2001 filing says Wells 'does not really treat static areas' and 'omits the crucial step of forcing cleanup on units that don't need cleanup, but are static', and says the Cirrus Logic patents also omit that step. The claim text of Wells read for this card says the second, wear-heavy score is used when a cleanup is not required but time is available, once the erase counts differ by 500 or more, which can be read as forcing a cleanup of a block that was not due. Gal and Toledo describe the wear-heavy phase as choosing additional units for reclamation. The card shows both readings without resolving them; Ban's statement is one competitor's characterisation made to distinguish his own patent.

M-Systems: the Flash Translation Layer and TrueFFS. Gal and Toledo say M-Systems sold TrueFFS, a block-mapping driver that implements the FTL, and that M-Systems literature (a 1997 technical overview by Dan and Williams, not opened here) states that its wear leveling combines randomness with erase counts, with the claim that randomness removes the need to protect exact counters; they add that the algorithm is not described in the open literature or in patents. Woodhouse writes in 2001 that both FTL and the newer NAND variant NFTL are encumbered by patents in the United States, much of Europe and Australia, that M-Systems had licensed FTL for all PCMCIA devices and allowed NFTL only on DiskOnChip devices, and that Linux supported both but deprecated them. Ban's own patent for the original FTL mapping (US 5,404,485) contains no wear-leveling description in the text read, and Ban's 2001 filing says that patent and its 1999 successor 'do not provide means for wear leveling'; so the first FTL patent is a mapping patent, and the sources read place M-Systems' wear-leveling disclosure in the 2001 filing.

File systems for raw flash, 1995 to 2001. Kawaguchi, Nishioka and Motoda of Hitachi built a Unix driver that writes sequentially like a log-structured file system and uses a cleaner; Gal and Toledo call them probably the first to identify log-structured file systems as suitable for flash. The paper reports random write throughput falling from 222 KB per second at 30% utilisation to 40 KB per second at 90%, and that mixing hot and cold blocks hurt: their first hot-and-cold results were far worse than expected, and a modified driver that used one segment for cleaning cold segments and another for writes improved write throughput by more than 40% at 90% initial data. Gal and Toledo note that policies which cluster static data in some units improve cleaning efficiency but leave static units unreclaimed for long periods, which gives uneven wear unless a separate wear-leveling mechanism exists. Woodhouse says Axis released JFFS under the GPL in late 1999. In JFFS the garbage collector moved forward through the log, so on a 16 MiB file system holding 12 MiB of static data, 2 MiB of slack and 2 MiB of dynamic data it rewrote the 12 MiB on every pass; in his words JFFS 'provided perfect wear levelling - each block was erased exactly the same number of times - but this meant that the blocks were also erased more often than was necessary', and wear leveling 'must be provided, by occasionally picking on a clean block and moving its contents. But that should be an occasional event, not the normal behaviour.' JFFS2 takes a block from the dirty list unless the jiffies counter is divisible by 100, in which case it takes one from the clean list. Gal and Toledo describe the same one-in-100 rule, but they rely on Woodhouse's article, so the two accounts are not independent, and they point out that a method that selects units only by the amount of invalid data can leave a lightly worn unit with little invalid data unreclaimed for ever.

Static leveling becomes its own mechanism, 2001 to 2007. M-Systems' filing of 1 June 2001 (issued 4 May 2004 as US 6,732,221) names the gap: methods that choose where to write new data cannot influence 'static areas' such as operating-system and application code, and static areas occupied a major part of the media in many uses, so the lifetime could be halved if they span half of it (a vendor claim). Its method launches once per some large number of write or erase operations, picks a unit so that successive picks reach every unit, moves its data to a free unit and erases it. Gal and Toledo describe it as relying on a spare unit with a random or fixed trigger such as the 1000th erase since the last event, aimed at giving every unit about 100 swaps, and say the idea appears to have been used earlier in TrueFFS. Chang, Hsieh and Kuo presented a different design at DAC in June 2007: a Block Erasing Table with one bit for each 2^k consecutive blocks, a count of erases since the table was reset (ecnt) and of set bits (fcnt), a trigger when ecnt divided by fcnt reaches a threshold T, a request to the cleaner to copy and erase a block from a block set that the leveler selects, and a reset of the table when all bits are set. Their slides give the table's memory need as 256 bytes at k = 0 for 512 MB of flash up to 4,096 bytes for 8 GB, and 32 to 512 bytes at k = 3 (their table; for 1 GB with 256 KB blocks, 4,096 blocks at one bit each is 512 bytes, which matches). Their evaluation used a one-month trace of a mobile PC with a 20 GB hard disk (1.82 writes and 1.97 reads per second, 36.62% of logical addresses accessed) on a modelled 1 GB two-bit-per-cell flash, and reports first-failure time improved by 100.2% at k = 3, T = 100 and by 87.5% at k = 0, T = 100 with less than 3% extra block erases. The text extracted from the slides does not show whether the 87.5% figure is for the FTL or the NFTL configuration. The slides also give 100,000 erase cycles for single-level and 10,000 for two-bit-per-cell flash as the motivating bound (authors' figures).

A raw-flash layer in the Linux kernel. The Linux MTD project's UBI page says UBI has been in the mainline kernel since version 2.6.22, works on raw flash and 'is not a Flash Translation Layer', keeps an erase-counter header in every physical eraseblock, provides global wear leveling across the whole chip by moving data from more worn to less worn blocks, reserves one physical eraseblock for wear-leveling purposes, and rebuilds its tables in RAM by scanning all headers when it attaches, so attach time grows with flash size (a 256 MiB OneNAND device attached in under a second and a 1 GiB NAND in about two seconds on the devices it names). Its authors explain that they chose not to keep the erase-counter and mapping tables on flash because that would need journaling and replay code that boot loaders could not hold.

What the sources do not settle. Who first used the labels 'dynamic' and 'static' wear leveling; whether Wells's second score already forces cleanup of static blocks (Ban says it does not, the claim text can be read the other way); how TrueFFS actually levelled wear; when the FTL's wear leveling was first shipped, because the card relies on patents and later descriptions, not on product documentation; whether SanDisk, Lexar or other controller makers of the 1990s used counters, randomness or neither, beyond what Gal and Toledo say of the Lofgren patents; and whether the 87.5% to 100.2% gain generalises beyond one trace. Not covered: current SSD controllers, hot and cold data separation by temperature (the cat and dac policies that Gal and Toledo describe were read but not summarised here), the effect of wear leveling on write amplification, and the NAND-specific changes after 2007.