Packetfury.net

For 3 months now, I've been creating a Linux system that is based on an Ubuntu, but that is modified so that it works well on Netbook systems. The processor and RAM are below average, and that is understandable since the system is designed to be low-powered, but my biggest concern hasn't been the CPU or the processor, it has been the hard drive.

SSD technology has been around for some time, and today's disks are little more than updated USB keys, or compact flash systems. When it boils down to bare hardware, the common denominator is NAND flash. The building block of NAND FLASH is a transistor; one transistor per NAND cell. There are two variants, Single Level Cell (SLC) flash that can store one bit, and Multi Level Cell (MLC) flash that can store two. Typical timing for an SLC cell is 25µs read time, 2ms erase per block, and 250µs per write operation. For an MLC, typical results are 50µs read time, 2ms erase per block, and 900µs per write operation. The read time is identical; 25µs to read one bit, 50µs to read two. Nothing strange here. The erase time is constant, since an erase operation will erase an entire block (more on that later), but the write time does change. Writing to an MLC cell is almost 4 times slower than a typical SLC cell. Faster disks will tend to use SLC, and cheaper drives will use MLC. The P-SSD1800 uses MLC. Most desktop SSDs will use MLC, and most server SSDs will use SLC.

Architecture

The P-SSD1800 uses 4 Samsung K9LBG08U0M chips, and a Phison PS3006-L controller. The flash chips are comprised of 8192 blocks, 128 pages per block, and 4096 (+128) bytes per page. This is typical of most flash chips, and the architecture stays the same for most devices. The minimum read/write size is one "page", and in this case, 4k. It doesn't matter if you are writing one byte or 4k, in the end the drive will still end up writing 4k, filling up a page. A block is a section of the flash chip, and is comprised of pages. In this case, a block is comprised of 128 pages. Now, here comes the weak part of SSD drives. A page can be read and can be written, but can not be over-written. In order to write over the contents of a page, the entire block containing the page must be erased. Following me?

What makes an SSD fast?

While the statistics might sound impressive, don't forget that SSDs are more or less glorified USB drives, and we all know how slow USB drives can be. So what makes an SSD so fast? Concurrency. If you can read one bit from a NAND chip in x micro-seconds, why not read 8 bits from 8 different NAND chips at the same time? You then get 8 times the throughput, just by using more chips. The P-SSD1800 uses 4 chips to allow 4 more times the bandwidth than a single chip could do, so how come this drive isn't that fast?

The slow-down

Just to recap, remember that a single NAND flash die is subdivided into blocks. Typically, each block is 512KB in size. Each block is further subdivided into pages, with the typical page size these days being 4KB.
You can read and write to individual pages, so long as they are empty. However once a page has been written, it can’t be overwritten, it must be erased first before you can write to it again. There's our bottleneck, the smallest structure that an SSD drive can erase is a block, not just a single page.
SSDs are not designed like standard mechanical drives, there are no moving parts to take into consideration, and data can be put just about anywhere. On platters, data has to be stored in a specific way, so that the data can be retrieved in a logical way. Fragmentation can be a real problem on platters, a weak point that SSDs don't have. SSDs are not prone to fragmentation issues, since SSDs can read random data without mechanical considerations; there isn't a head that needs to be moved over a specific area of the platter. SSDs are therefore free to write data to anywhere on the disk, and they will always pick a place where pages haven't yet been used, maximizing speed. When a page is no longer used (deleted data, or portions of a file that have been reallocated), the page is simply marked as unavailable, meaning that the page is awaiting an erase. This technique works well, but isn't eternal. Sooner or later, all of the free pages will be used, and the drive will have to place data elsewhere. This is where things start to go wrong.

Example SSD

Imagine, if you will, a strange SSD drive, composed of one block, and 10 4k pages in that block. Its read speed is 8k a second, and the write speed is 4k a second. The drive is entirely empty, and has never been used before. All pages are blank, and ready to be used.
We will first write a file to the SSD, a 20k file that will be placed on 5 pages. Writing 5 pages will take the drive 5 seconds. We then read back the file, reading in 20k of data from the 5 pages. Reading in 20k from the drive will take the drive 2.5 seconds. The drive now has 5 used pages, and 5 free pages.
Next, a temporary file is written to the SSD. The temporary fill is small, being only 1k in size. The SSD will write that onto a free page, writing 1k into a 4k block in 1 second. A few seconds later, the task is complete, and the block is no longer needed; the SSD is issued a delete command. A page cannot be deleted, it can only be erased when the entire page is erased, but we don't need to do that. The SSD marks the page as unavailable, which is close to instantaneous. Our drive now has 5 used pages, 4 free pages and one unavailable page.
A second application writes a small 1k temporary file. The drive has 4 free pages left, so the SSD will choose one of those pages to write to. The write action will take 1 second, just as before. Once again, the file is deleted afterwards, and the page is marked as unavailable. Our drive now has 5 used pages, 3 free pages and 2 unavailable pages.
The operating sytem reports, correctly, that 20k is free on out 40k drive. The operating system does not know about free and unavailable pages, and it doesn't even need to know about the SSDs strategy. Our user will now write another 20k file to the SSD, and the OS reports that it can. The SSD is issued an order to write 5 pages of data, and this is where things go wrong. We don't have enough free pages on our SSD, but we do have enough space. It is time to erase some data. Once again, we cannot erase individual pages, so we must erase the entire block. But we already have data there, so what do we do? This is where the drive's cache comes in - we have to read in some pages into cache. The SSD therefore reads in the 5 used pages into cache, for a total of 2.5 seconds. The entire block is then erased, and only after that can we write back the used pages. We have 5 pages that were previously used, and another 5 pages that must be written. The SSD therefore writes 10 pages of data, for a total of 10 seconds. The total write time is now 12.5 seconds, but should have taken only 5 seconds. Our SSD has now taken more than twice the time it should have, for what appears to be a relatively simple write operation.
Our fake hard drive is small compared to real SSDs, especially since a typical SSD doesn't have 10 pages per block, but normally have 128. In the worst case, we would have to read in 127 blocks, perform an erase command, then issue 128 page writes, creating drastic slowdowns. This is what I'm up against. The drive is optimized for burst transfers, but random access just doesn't cut it, so I need to reduce writes to an absolute minimum.