1 of 24

CSE 451

Operating Systems

L20 - SSDs and Flash Translation Layer

Slides by: Tom Anderson

Rohan Kadekodi

2 of 24

Main Points

Survey of physical storage hardware devices

SRAM, DRAM, Flash, magnetic disk

File systems

Useful abstraction on top of physical devices

File system usage patterns

Small files and large files are both commonplace

3 of 24

Volatile Memory: SRAM and DRAM

Individual word (8 byte) and cache line (64 byte) access
Data degrades without power; power proportional to storage capacity
Bit density scales with Moore’s Law
Static RAM (SRAM)

Typical uses: CPU registers, on chip cache, I/O device caches
Data stored in a transistor flip/flop
Access latency range: 1 – 20ns (smaller caches => faster)

Dynamic RAM (DRAM)

Typical use: main memory (8GB/chip with DDR5, usually sold as an array of chips)
Data stored in a capacitor, 2D/3D array for dense packing
Data degrades even when powered; bits need periodic refresh
Access latency: 50 - 100 ns

Tiered DRAM (CXL)

Rack-level extension to server DRAM (cache coherent, PCI)
Access latency: 300 ns

2 things about what we talked about today and the last couple of classes is Volatile Memory.

What technologies are used for volatile memory?

Volatile: turn power off, data goes away.

DRAM and SRAM are technologies for volatile memory. THey store data, but turn off power, bits disappear.

One type of memory: SRAM, used for processor caches.

In SRAM, transistor for every bit.

What DRAM does is that it uses a capacitor for every bit. Different technology. The fabrication facilities for SRAM and DRAM are different, completely different. Don’t share the two on individual chips.

DRAM = design a system for high density of bits per silicon. You are trying to pack bits as efficiently as possibly. One property of capacitor, compared to flip/flop. if as long as the system is powered, flip/flop is not using additional power to keep flip/flop charged relatively. Consequence: SRAM in static use (not reading/writing), not as much power is used, compared to DRAM.

DRAM: capacitor, charge degrades over time, loses data it has in it. Requires active refresh. Fair amount of power in datacenter, is active refresh in DRAM opposed to doing computing – to keep bits live in DRAM of system.

Important: DRAM and SRAM, you can address individual words, read/write individual words / cachelines in DRAM/SRAM. Unit of reading = arbitrary. Selectively read/write particular flip/flop. This is not true for storage.

Additional thing called tiered DRAM (new) called CXL, you put additional DRAM in a separate server. and connect it to your server for increased capacity.

4 of 24

Persistent Memory: Flash and Magnetic Disk

Block level (4KB) access (or larger); asynchronous request queues
Data valid even when unpowered
NAND Flash/Solid State Drive (SSD)

Bits stored in special silicon gate, densely packed in 2-D or 3-D array
10-50 us block level random read/write
Each block can only be written once, but can be erased
Limited number of erasures per physical block (10K depending on type)
Typical use: smartphones, laptops, servers, data centers

Magnetic “hard” disk drive (HDD)

Bits stored on magnetic surface: 1.5 Tbit per square inch
Physical motion (spinning disk) needed to read bits off surface
10 ms random access latency; 250MB/s max throughput
Typical use: data center bulk storage, backup

For persistent Memory, two alternatives.

Almost all have used both of it, whether you know or not.

If you have a backup system at home, almost all are Hard disks.

Almost all storage in laptops / phones are flash.

First we will talk about flash, then magnetic disks where we talk about backup.

In cloud you have a mixture of the two: some flash, some disks.

Servers in lab, local hard disk in them. Flash is more expensive per byte. If you want cheap, Hard disk, if you want something lightweight (cell-phone) you generally use flash.

Both of these are block-level operations: you read / write in a block, usually 4KB. Can be as small as 512B, generally page size that people use.

What if I only wanted little bit, to write few bytes, read old data in memory, update it, write the data back to disk.

1st part: how does flash work? Essentially, instead of storing those bits as a capacitor, or as a flip/flop, they are stored in a specially constructed thing that retains state even when turned off.

The block-level accesses are in the range of 10-50 microseconds - much much slower. SRAM is 1 ns per operation, DRAM = 100ns per operation, Tiered DRAM = 200 ns. This is couple of order of magnitude slower.

Page fault, go to disk, wildly expensive.

Magnetic disk, orders of magnitude even slower than flash.

5 of 24

5

[J. McCallum, jcmit.org]

DRAM

Flash

Disk

Graph over time of memory price per MB, and time on x-axis.

1955 to now.

Let’s look at trends – 3 lines.

DRAM, Flash, Disk.

Note the log-scale on the y-axis.

What this implies is that over time, exponential improvement in disk cost / capacity for all 3 technologies.

That exponential rate changed over time.

Disk: improving at exponential, still improving, but slower.

Flash, has been improving fast rate, slowing little bit.

DRAM is now much slower improvement.

Difference in cost of DRAM vs Flash = 30x, Flash vs Disk = 3x.

You can see that they are not smooth, some times DRAM is very expensive, sometimes not. Right now for example, expensive. Large scheme of things, not super important. DRAM chip shortage causes these blips.

Over time people get better at building these things, there is more competition, production is more streamlined. hardware gets cheaper.

It is unclear if you look 10 years from now, if Flash and Disk will converge. Flash has huge advantages. If converge, people will stop buying disks.

6 of 24

Flash Memory

Original use cases:

BIOS
OS Bootloader
Device Configuration

Updates rare but necessary

Fix bugs after product ship

Exponential improvement in density over time

500x in 20 years

Read/write Latency: �10-50 microseconds

So our context here is we'd like to understand the underlying mechanisms for, um, physical disk storage.

One common place where lot of memory in storage goes these days is notion of flash memory. Most bytes stored are in magnetic disks, which we will talk later.

In terms of what most bytes written / read go to, and most perf issues come from, is flash memory.

Original use case was to serve as starting point for booting of computers. When computer starts, where does it know where to start? BIOS, this was the original use case for flash memory - �computer should be able to configure itself by executing instructions.

Where does it get instructions from? - some memory. Should be able to upgrade those, so programmable. Want it to be persistent - operate like regular memory, but instructions available even when �you hit power button. Unlike DRAM that loses data on power, flash will hold up.

Also used for bootloader, and for device configuration. Devices themselves have computers on them, and these computers have programs. Where do they live? Flash memory.

The updates to flash memory are rare but necessary. Example is to fix bugs after shipping program. For example, put BIOS and never change it. What if wrong? This was original use case.

Over time, exponential improvement in density, 500x over 20 years. Show previous graph.

Physics: Floating gate, info lives. Control gate: how I am programming that. Electrons are in source and destination. On a write, forced into floating gate. It is like a capacitor. No connection to outside world. �How flash works? If you write to it, then you have to erase it to write to it again. Sets a magnetic property to floating gate. Rest looks like transistor when reading it.

Speed of flash: 10-50 micros. Slower than DRAM, much slower than SRAM.

7 of 24

Flash Memory Challenge

Writes must be to “clean” cells

Erasure required before block can be rewritten
Erasure is 20x slower than single block read/write
Erasure needs empty guard regions to avoid erasing useful data in nearby blocks
Limited number of erasures per physical block (10-35K for MLC, 1K for QLC)

Solutions?

minimize erasure
block translation

Challenge of flash: writes must be to clean cells rather than things already written.

DRAM: update = overwrite.

Flash: first erase, and then rewrite.

�BIOS: a problem. If I am using this as my boot instructions. If I erase what is there and rewrite it, problem if power goes off halfway through. If I reset it, before writing again to it, could end up with no BIOS at all.

Next time reboot computer: nothing there. When updating BIOS: careful. Always plugged in, nothing bad should happen. Write quickly and hope that nothing bad happens.

When flash used for storage generally, phones, laptops, cloud, because flash is much cheaper now, we have ways to erase before rewriting.

Erasure is slower than writing a block, takes about a millisecond, much slower.

Erasure: pass a large magnetic field over empty bits to erase useful data. Problem: also erase useful data in nearby blocks. So you should have empty room or guard regions to avoid erasing useful data. �You want empty bits not storing useful info, empty space. ��Consequence, you tend to want to erase more and more larger chunks.

Final point, flash only has limited number of erasures per physical block. A block can only be written and erased limited number of times. Reads unlimited, but writes limited, before block is worn out.

Then next time, you can’t write to it. Then, that block becomes useless as storage.

THis is challenge. What are solutions?

You want to minimize the erasure you are doing.

Block translation: move blocks around, also for erasure. Block of data overwritten, then overwritten, then overwritten, level the wear on the device, across multiple blocks.

8 of 24

Managing Wearout

Each flash block can only be written limited number of times

Depends on encoding: 1000 (QLC), 10-35K (MLC), 100K (SLC)

What if app repeatedly updates the same physical block?

1ms per write/erase cycle
Assume 10K write/erase cycles before wearout

⇒ Wearout (of one block) in 10 seconds !

⇒ Disk keeps getting smaller over time…

=> Can’t allow update in place

For managing wearout, given a block can be written only a number of times. The #times depends on encoding.

E.g., encoding: how many bits you are storing in each transistor. The QLC = 4 bits, MLC = 2-3 bits, SLC = single-bit encoding. Single encoding for each unit that was being stored information.

As a consequence of technology changes, single bit encoding you can overwrite many times. Double bit you can write almost as many times, not quite as many.

Quad ones, densest encoding, is ver limited in the number of rewrites, so can only be used for very cold / infrequently changed data.,

What happens if app repeatedly updates same block, like in DRAM.

In DRAM, if I write to some virtual memory location, it can go anywhere. But in physical memory, that goes to the same location everywhere in DRAM. In DRAM does not wear out. I can write and rewrite and rewrite and rewrite - it is fine.

By contrast with flash, if I rewrite the same physical block, it wears out.

E.g., if I take a millisecond per rewrite / erase cycle.

So I write it, around 50 micros, then erase it, one millisecond, rewrite it, again 50 microsecond, again erase it, millisecond.

In order to write something, I should write it out, erase, then write.

If QLC, I need to do it 1k times, MLC 10k times.

Let’s say if we need to do 10K times since most flash is MLC today. Only ones that you are updating a lot can be in SLC with more durability.

Say we are taking some normal flash drive, and we are writing it as fast as such.

Implication: 10000 times one millisecond, if you were to hammer on one particular block, then in 10 seconds you cant use it to store anything.

Implication: you have a block that can’t be used. What happens when someone asks me to write data to it, I need to store it somewhere else.

So I need some mapping structure to put somewhere else.

Also, some user can do activity to wear out part of my disk - not good. As a consequence, flash devices do not allow update in place.

9 of 24

Flash Translation Layer (FTL)

Disk firmware exports a virtual block interface

Read/Write/Trim (block delete)

Firmware relocates each virtual block to physical location as needed

Overwrite to a previously written block goes to new empty location
Reads to the newly written block are redirected to its new location
Previous block is stale, unused, ready for erasure (reuse for other block writes)

Like putting the block into the trash - device firmware can still read the old data (until erasure)

FTL needs a map from virtual block # to physical location

Stored in SRAM for fast lookup
Written back to SSD on power failure (battery, capacitor)

Instead, what we do is called Flash translation layer.

We use firmware in the device (a small microprocessor in the device) that makes the flash device itself look like an exported interface that looks like a regular disk,

it has block operations, certain size.

When executing operations on underlying disk, it will put them to different locations. Firmware gives a virtual block interface which flash exports to external world, and then turns them into physical blocks.

Overwrite / update to previously written block, instead of erasing and replacing data again, an overwrite / update goes to new empty location, which will leave old data where it was before. What do to do that old data?

The new location can be anywhere. As long as I have translation, anyone asks me to read the virtual block number, FTL will redirect to new location.

Read to VBN goes to new physical location - done by disk firmware. Totally transparently to OS, software. FS operates in the same way as it was. It looks like a physical block.

The firmware does this underneath the covers.

Once overwritten, previous block is stale, ready for erasure if we need to use it.

It is very like putting file into trash if you use a MAC or PC. Firmware can still read old data. I.e. file on trash is not really deleted. Likewise if I write new version of a block, I am not erasing old block right away.

If someone had access to firmware, it can read old data from media. If you were trying to do forensics on someone’s computer, understand if they deleted this file, you could think you are deleting it, but it is there.

Consequence, FTL needs a map from virtual block number to physical location.

That is stored in SRAM on the device. Fast lookup. Written to SSD on power failure. Devices have some battery / capacitor, when power goes out, device has enough juice left to flush changes made to the translation.

This makes sure that the changes are persistent, done by batteries on SSDs / flash itself.

SSD is a misnomer, there is nothing round about it. It is just a silicon.

10 of 24

FTL in Picture Form

Eventually we’ll run out of space…

D C E A D C B A

writes

Translation map

A B C D E F G H

Block storage

1 2 3 4 5 6 7 8

A

1

B

2

C

3

D

4

A

5

E

6

C

7

D

8

crash

read

11 of 24

Erasures

Erase many blocks at a time (erasure region)

Multi-block erasure region is always erased together at same time
Minimizes wasted area/density due to guard regions

Guard per multi-block erasure region

Prorate time spent erasing over more blocks

Device still appears to read/write individual 4KB blocks

Number of blocks in erasure region is an internal value, not visible to customers
Tens to hundreds 4KB blocks per erasure region

What if some of the data in the erasure region is still live?

Where do we put that data during the erasure?

What can we do about that? THis is when we will get erasures.

Erasures take a lot longer than writing data in the first place.

We better not be erasing just one block at a time. We want to erase a larger region of data.

Region needs to be larger than a block and I will need guard region around it, because I will erase more data than block, because it will erase things around edges too.

As a consequence, I will group a set of blocks of data together, and erase as a unit.

THis minimizes wasted area for guard regions. Also prorates the time I’m spending in erasing, over more blocks.

Although I am erasing larger chunks, device still appears to read/write individual 4KB blocks.

The number of blocks in erasure region is an internal value not visible to users. Generally, around 10-100s of 4KB blocks per region. If it takes 100 times longer to erase than write, maybe you can have 100 blocks. This amortizes the cost of erasing, to not be a huge factor.

One question: suppose I have some region that I should erase, because it has dead data in it, but some data is alive. Where do I put data during erasure?

I could end up erasing some data, and it is gone. Could be totally missing. So if I end up losing data during erasure, that is terrible.

12 of 24

Efficient Compaction

write amplification due to compaction

% of disk utilization

Avoid worst-case compaction by reserving unused physical space (20-30%)

So lets try to plot efficiency of compaction.

Write amplification is the y-axis, which is how much live data I have to copy during compaction from one place to another.

So how often does a particular block that I am writing to on average have to be copied before it gets deleted. Once deleted, it is garbage and reclaim it.

Question: How many times will I have to write A again, then X again, then Y again. Possibility that I might have to do that many many times depending on how full my disk is.

How much is write amplification due to compaction, the extra writes I am doing. We have to do atleast once, regardless. But how often do I have to do more than once? That is a function of the percentage disk utilization on x-axis, between 0 and 100%. That’s going to go as a go closer to 100% utilization in my physical disk,then every new block is really at that edge.

So every new block that I write will create an extra empty spot somewhere that I can reclaim by copying everything else in that erasure region, which might be more live data, in order for me to create exactly one block that I could write.

In the worst case, for every block write, I might require an erasure. This will make my disk roughly 100x slower for writes, than what it was doing, than if it was acting normally on mostly empty disk.

That knee of the curve, will be increasing overhead, around 70-90% depending on workload.

So, many times, disk vendors advertise a significantly smaller capacity than the disk actually has, to avoid being on the wrong end of the knee curve, such that the performance remains stable. They reserve 20% of the SSD’s physical space to avoid this worst case compaction behavior.

Furthermore, increased compaction also has the problem of wearing out the device quickly. The more you write and move around, the more are the overwrites in the same region on the device, and causes the device to wear out faster.

Furthermore, this compaction and write amplification due to erasure also is workload dependent. If there is a high locality to workload, i.e., if you create and delete consecutive blocks at the same time, then you don’t have to perform compaction as much. For example, say I have the source code to XK, it is a lot of code together and I am creating the executable, which is large, and storing it somewhere on flash device. Then, if I compile a new version if it, I will rewrite the file, all those blocks become dead. I could then potentially erase them all at the same time.

One final thing: trim at the top.

13 of 24

Wear Levelling

Each block can only be written a maximum number of times

FTL tracks # of erase/write cycles for each block
Unmap blocks if they can’t hold new data

To keep from losing blocks due to wear out

Write new data into regions with fewer update cycles
Put data that won’t change in blocks that are near the end of their lifetime

Go back to the notion of wear levelling. �

I want to make sure that my writes end up being balanced over the disk. Example: I am updating FTL on a regular basis.

The information of where data goes, I don’t want to write to same physical location again anad again. I want to put it in different places such that I am not wearing some place.

Since each block can only be written a maximum number of times, you need to keep track of how many write cycles and erasure cycles a block has taken, and you unmap those erasure block regions if they can’t hold new data, and to keep from losing those erasure regions due to wear out,

you want to write new data to regions that have fewer updates to them. Places with not as much wear, and put data that doesn’t change very much. Things that I don’t have to erase in the future, can put in erasure regions that are near the end of lifetime. So it is like cold data that won’t be modified.

We have to be somewhat more intelligent. THis is done by disk controller, not visible to user / OS.

14 of 24

SSD Encoding/Error Detection

SSDs have different internal bit-level encodings

SLC: single level cell (1 bit)
MLC: multilevel cell (2 bits, some vendors use MLC to mean 2+)
TLC: triple level cell (3 bits)
QLC: quadlevel cell (4 bits)

SLC: frequently changed data

Higher cost, faster writes, more erasure cycles
Compete with DRAM

QLC: cold data

Lower cost, good if data is mostly reads or disk is not heavily used
Compete with magnetic disks

15 of 24

Micron 9550 NVMe SSD (TLC)

Capacity	25 TB
Page Size	4 KB
Bandwidth (Sequential Reads)	14 GB/s
Bandwidth (Sequential Writes)	7.6 GB/s (peak)
Random 4KB Reads	2.8M/sec
Random 4KB Writes	.75M/sec
Endurance	10000 erase/write cycles
Latency (read/write)	60us/15us
Interface	NVMe

16 of 24

Error Detection/Correction

Data stored with extra space for error correction bits to improve reliability

Writing/erasing bits is an electromagnetic process
Signal not confined to erasure/guard region
Customers expect data you read to be exactly what you wrote

Even with error correction

uncorrected bit error rate ~ 1/10^17
For Micron SSD (previous slide) => 1/day (if bandwidth fully used)
Typical hyperscale data center has 100K SSDs

=> In cloud settings, both ECC and application-level validation checks needed

One final thing about flash: There are errors: electromagnetic properties about writing / reading things with magnets.

�Data stored needs extra space for error correction bits to improve reliability.

As I am writing / erasing bits to neighboring blocks, I could potentially be flipping bits in other regions.

Customers use storage systems to get back what they wrote.

Even with this error correction, you have an uncorrected bit error rate which is 10**-17th, which means extremely small. But if you are using the micron SSD in previous slide, using all the bandwidth that you are reading / writing as fast as you can all the time.

Essentially heavy-duty cycle in datacenter, you will read a wrong bit everyday. It will give an incorrect bit everyday. If you were in a very large datacenter with 100k devices, then roughly, somewhere in the datacenter reading wrong bit every second.

If your system is not tolerant to recovering from these error that is a problem. Consequence: cloud settings, you will see error correction in the device, and the application / file system does additional level of validation checks on data it is reading, to make system resilient to these errors.

17 of 24

SSD Scaling Bandwidth

Final thing: individual blocks you have for device: how to get higher bandwidth, given individual ops take 50-60 micros to read/write. How to get high bandwidth of 14 GB/s bandwidth?

Disk itself has parallelism in many dimensions.

First dimension, disk controller will have a cache of written data, in SRAM.

Reads, I will go to a location where I have multiple erasure blocks stacked on a lane.

So if I want DATA, it could be reading a block from one erasure blocks, and then reading another block from another erasure block. This can be done in parallel.

In addition I have multiple buses / lanes from same disk controller, to have multiple reads happening in parallel, across multiple lanes, to different erasure blocks.

Operations can be in parallel in different lanes, operations can be pipelined on different bus / lane.

Disk controller can be in charge of multiple flash chips, in an SSDs. You can have even more bandwidth. I can scale up bandwidth by having more chips per device.

�So if I am writing some data, should I put them in the same erasure block or different, in the same lane, or different lanes?

To get more bandwidth when reading data, I can assign blocks to different erasure blocks on different lanes, so that I can read all of these in parallel.

18 of 24

Implications of Striping

Striping implies blocks written together are spread out over many erasure blocks
Even if write in large chunks, will still have high compaction overhead

Need giant chunks to avoid compaction

Compaction can also cause slowdowns for reads of data in same lane

Unpredictable tail latencies

Add command to defer compaction temporarily?

19 of 24

Device management overhead

SSD Throughput (MB/s)

SSD prefers large sequential IO

64 MB 128 MB 256 MB 512 MB 1024 MB

1250

1000

750

500

250

0

0.1 0.25 0.5 0.6 0.7 0.8 0.9 1

SSD utilization

SSD Random writes: 5-6x difference in performance

20 of 24

Magnetic Disk

21 of 24

Magnetic Disk Anatomy

2 pictures. One how physically looks, and one is schematic.

Definitions: disk itself is a stack of platters of disk. Disk heads are like a column oof those platters. They read both upper and lower surface of the platter. So there is info on both sides of the platter.

So if you have 10 platters, that means you will have 20 disk heads. The spindle is the thing that is rotating them, thousands of times per minute, at a really high speed.

The actuator is the disk arm is moving in and out to locate bit / block of information that you are reading back / forth.

On the write, as the disk head rotates, the information rotates, and that is a magnet that reads or writes data that particular block. This gives me the ability to read /w rite particular track. If I want to read other tracks, I move the head.

Data is concentrically located. There is another ring of blocks.

These tracks are very small. Disks have a terrabyte of information per square inch. Very tightly connected.

22 of 24

Disk Tracks

~ 1 micron wide

Wavelength of light is ~ 0.5 micron
Resolution of human eye: 50 microns
100K tracks on a typical 2.5” disk

Separated by unused guard regions

Reduces likelihood neighboring tracks are corrupted during writes
Bit level corruption still happens with non-zero chance

Track length varies across disk

Outside: More sectors per track, higher bandwidth
Disk is organized into regions of tracks with same # of sectors/track
Only outer half of radius is used

Most of the disk area in the outer regions of the disk

23 of 24

Disk Performance

Disk Latency =

Seek Time + Rotation Time + Transfer Time

Seek Time: time to move disk arm over track (1-20ms)

Fine-grained position adjustment necessary for head to “settle”

Head switch time ~ track switch time (on modern disks)

Rotation Time: time to wait for disk to rotate under disk head

Disk rotation: 4 – 15ms (depending on price of disk) On average, only need to wait half a rotation

Transfer Time: time to transfer data onto/off of disk

Disk head transfer rate: 100-250MB/s (5-10 usec/sector)

Host transfer rate dependent on I/O connector (USB, SATA, …)

24 of 24

Western Digital Ultrastar DC HC690

Capacity	32 TB, 7 platters
Spin Speed	7200 RPM
Sustained Transfer Rate	270 MB/s (read), 260 MB/s (write)
Interface Transfer Rate	1.2 GB/s
Seek time (avg)	8 ms (read), 8.6 ms (write)
Rotational latency (avg)	4.16 ms
Cache	512 MB DRAM
Idle/Operating Power	5.8W/9.7W
Bit Error Rate (read)	10^-15