18

I think most modern flash drives (from SATA disks to USB drives) have some kind of wear leveling.

Normally a block (small amount of bytes) in a flash chip cannot be erased and programed an unlimited number of times. That is why there is wear leveling. It's actually software (part of the drive firmware) which distributes the usage evenly across the flash chip (see Wikipedia).

Now I've read that PS1 memory cards did not have wear leveling. That's why I doubt early USB pen drives had it.

My question is if somebody knows when wear leveling came up? It doesn't matter if it was dynamic or static wear leveling. But at least one of both.

Questions related are (I think it's not worth creating a new thread): Who was the first manufacturer having this and who invented wear leveling? Which was the first device having it?

Improve this question
14
  • 2
    The most interesting question for me is where is stored the metadata (what kind of memory). Metadata is the info (table) for current allocation of memory. If it is stored on Flash memory like the payload then is there another wear leveling for metadata - because it is updated frequently. Maybe there is SLC area for metadata and MLC for all other.
    – i486
    Oct 5 at 9:17
  • 1
    @i486: The metadata is not updated any more often than the data. It can be stored alongside the data and use the same wear-leveling mechanism. Of course, this means that to find a given piece of data, a search must be performed, and flash file systems normally cache the search results in a table stored in volatile memory in order to speed up future accesses.
    – Dave Tweed
    Oct 5 at 12:18
  • 2
    @Hearth: I was referring to the metadata associated with wear-leveling only. This is normally implemented at a level of abstraction underneath any application-level metadata. A file system usually treats the underlying storage as an array of blocks, in which files, directories and other user-visible metadata are stored. One way to implement wear-leveling is to create a virtualization of that array of blocks.
    – Dave Tweed
    Oct 5 at 15:27
  • 2
    Note that a lot of the cheap-end modern USB pen drives still don't have it. They often burn out absurdly quickly as a result.
    – Perkins
    Oct 5 at 20:47
  • 2
    @i486 You can use regular flash to store the metadata. If you need 1K bytes for the metadata, just use 100K of flash in round robin fashion to get 100X the number of writes. I often do that in microcontrollers when I need to store small frequency updated data that would otherwise exceed the allowed number write cycles for the flash memory. Some wear leveling implementations (including one by Apple) used a small piece of nonvolatile FRAM memory to store the metadata. EEPROM, which typically has much higher write limits (like 100X more than flash) could also be used.
    – user4574
    Oct 6 at 0:46

5 Answers 5

Reset to default
22

It's a long-standing and well understood design principle.

The very first EEPROM I designed into a system in about 1989 had wear levelling implemented in the software. It was a simple conclusion that our system would need it and we were only storing a few bytes.

This decision was influenced through knowledge of our company's earlier financial machines. They were using wear levelling with EEPROMs in about least 1983.

I don't know if you saw it as some slowly-acted-upon conclusion after Flash EPROM came along but it's far from that.

Improve this answer
16

It was certainly a known practice in 1993 when I designed a filesystem for EdenOs that had an optional wear-levelling layer for flash-based storage (battery-backed RAM on PCMCIA was the favourite removable storage at the time). I certainly didn’t invent the practice so it must pre-date that by a little while.

Improve this answer
2
  • Didn't know filesystems could have this. Doesn't it mean you can never reformat the drive because the block usage information (erase counters) would have get lost?
    – zomega
    Oct 4 at 19:39
  • 12
    @zomega: generally when you reformat the drive the new format will assume that all blocks have the same amount of wear. As long as the previous uses of the drive had wear levelling to keep wear reasonably even across all blocks, that should be enough. Combine this with the fact that wear doesn't cause a block to fail after a fixed number of writes, it just has the failure rate rise with more writes, so you want to keep wear globally level, and things work out.
    – Chris Dodd
    Oct 4 at 22:07
9

Wear levelling is/was originally a feature of file systems.

FLASH 'drives' were at first not made to emulate existing standards. In fact, they were not 'drives' at all but just the flash memory chips added via some interface to handle addressing and data transfer. Any store and retrieval was done directly. After all, FLASH memories are interface wise very basic memory devices. Address + CS equals Data :))

Thus any addition of those memory chips to a system means that system has to take care of it's special needs. When used as ROM like storage - that is writing only once and maybe a few updates - like for example to hold a BIOS, they could be treated as regular memory chips.

When used as a disk like storage, the OS must provide some driver taking care of their special nature - like only being able to erase in large blocks, or having limited write cycles. That's why early flash cards always came with drivers implementing elaborate schemes to finge blocks around without the OS noticing - or an OS providing adequate allocation strategy. Something embedded systems soon added - for example QNX' FFS. But also mainstream systems like DOS.

Microsoft introduced their FFS2 for MS-DOS in 1992. M-Systems developed around the same time their TrueFFS to support their DiskOnChip modules which might qualify as first (successful) generic FLASH drives (*1). Parts of TrueFFS was later (ca. 1994) turned into a Flash Translation Layer (FTL) by Intel and M-Systems and adopted by PCMCIA as standard resulting in a first wave of flash cards for laptops.

FTL provides an OS/Driver interface to handle block allocation on an abstract level while translating between logical block numbers the OS sees and the actual flash block number used for storage. That way wear levelling can be implemented and defect blocks be replaced without (much) interaction of the OS.

Flash drives seen as standard nowadays are a development based on those standards but now have them operate using a standard mass storage interface - like SCSI or ATA (or later USB) - and a controller handling most of the FTL.

Again later more capable controllers began to hide the whole nature of being a FLASH drive and do all management internally.

*1 - It was very much focused on MS-DOS support, not ad great for every other file system.

Improve this answer
3
  • You oversimplify the nature of flash devices. They're not addressable like other memory devices, they're very much block oriented.
    – Mark Ransom
    Oct 6 at 12:31
  • @MarkRansom Erm, you may want to look at some data sheet. to read or write a byte/word address is applied and exactly that byte or word is read or written. No difference from any other memory - especially no difference for other, prior ROM like device, e.g. (E)PROM, etc. In fact, the restriction of most types that writing can only go in one direction (usually 1->0) and erase being done in large chunks is exactly the same, isn't it? It would be nice to hear what difference you see.
    – Raffzahn
    Oct 6 at 14:13
  • 1
    I've never seen a data sheet for them, so maybe my understanding was an incorrect extrapolation of other facts. I'll drop it at this point and assume you know more than I do.
    – Mark Ransom
    Oct 6 at 15:39
6

Basic static wear leveling is ancient by technology standards. Simple implementations were used somewhat regularly with EEPROMs at least as early as the mid 1980's, and probably earlier even than that. You have to remember that flash storage is far from the earliest write-limited media, it just happened to be the first one that was economical enough for usage at large enough scales to serve as a major part of secondary storage while still having a short enough lifetime for wear leveling to matter.

And early usage was always an engineering tradeoff (it still is, it’s just fundamentally unrealistic for almost any consumer device to not provide a FTL with wear leveling these days). That’s why the PS1 memory cards didn’t use wear leveling, cost was more important than long-term durability, and it cost them more money to include wear leveling. Same for many early USB flash drives, they were mostly marketed as a cheap way to transfer files between two computers without having to use a network connection between them, so they were kind of inherently disposable in the same sense that cheap floppy disks were.

Improve this answer
6

While most flash memories use a different circuit topology from most EEPROMs (some devices using the EEPROM circuit topology are marketed as flash, and perhaps vice versa), many EEPROM memories have long been subject to operational limitations similar to flash, to wit:

  1. It's possible to change bits within individual bytes from "1" to "0", but the only way to convert "0"'s to "1"'s is to erase large blocks at a time.

  2. Performance, and eventually reliability, of blocks will degrade with each erase cycle.

Thus, for essentially as long as EEPROM memories have existed, it has been necessary for software to deal with these constraints. If the EEPROM was being used to hold a set of parameters that would be unlikely to change even a dozen times during the lifetime of a device, and never more than a few hundred, it would be fine for software to simply erase and rewrite the same block every time the parameters were changed even if the memory was only rated to be usable through 1,000 program/erase cycles. If, however, a device would be used to hold a counter that would be updated once per minute, even 10,000 write/erase cycles wouldn't be enough for such a design to last even a week.

Note that if a device had e.g. four separately erasable 256-byte blocks, and was unlikely to lose power while changing its configuration, it could use one block to hold the configuration and use the other three blocks in rotating sequence to hold the last multiple of 128 counts, along with 240 bytes that were used individually to mark off individual minutes. Every time those 240 bytes got full, the system would need to erase and reprogram the next block in rotation. This would reduce the stress on each block from being programmed and erased once every minute to being programmed and erased about once every 12 hours. If each block can only be programmed 10,000 times the device would wear out after about 13.5 years, but that's a huge improvement over lasting less than a week.

Historically, software to manage flash or EEPROM memory would often partition it into various regions, and use wear leveling only when storing frequently-updated data. Flash drives, however, generally use a more unified wear-leveling approach which manages everything. Doing that would often require using a fair amount of RAM to keep track of where many individual pieces of data are presently located, but as RAM prices have decreased such an approach has become more practical. This wasn't a sudden design change, however. Instead, the fraction of devices using such approaches gradually increased as adequate RAM would more often be available to handle it.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .