Linus Torvalds (torvalds@linux-foundation.org) on 1/9/09 wrote:
---------------------------
>iz (indan@nul.nu) on 1/9/09 wrote:
>>
>>Every random write can cause a remapping table change,
>>which is basically a random write as well.
>
>No, it's a non-random write if you do it well. The remapping
>table doesn't have to be some array - that would be the
>last thing you want. You'd make it a smarter extent-based
>thing, along with a log of the last remapping events
>so that you can do those as basically a streaming area
>that is pre-erased (and then you write a more space-
>efficient long-term thing when that fills up).
>
>So no, you do not need to be stupid about the FTL at
>all. Although a lot of previous-generation flash apparently
>is pretty naive about it.

However smart you do it, it only groups multiple random writes together. And yeah, that's probably pretty non-random in most loads, but with a truly random write load it's still pretty much an extra random write. Perhaps not one for every write, but still pretty bad. It can be done in parallel though.

Previous-generation flash didn't seem to even try to do anything smart at all. :-/

>>Larger extends reduces your theoretical maximum random
>>write performance (that or they waste a lot of space).
>
>That makes no sense. An extent-based allocation model
>means that if you can do the remapping in bigger blocks,
>then that remapping information can be done more densely
>and the lookup can be more efficient. Rather than having
>to have a huge translation table for all blocks, you have
>a more size-efficient (but yes, more complex) translation
>layer.

Bad wording on my part, what I meant is that a bigger virtual block size (the remapped chunk size) reduces random write performance. If you do remapping on 16KB chunks then you can't write out a stream of random 4KB writes continuously at max flash speed.

>It is true that nice streaming writes tend to not have
>nearly the same latency issues as the random ones. But
>I'm surprised that you would say "most" writes are random,
>because at least in my experience metadata writes do tend
>to be pretty random, but in most loads they are not the
>bulk of the data.
>
>(Well, metadata updates are often the bulk, but only when
>there are almost no other writes going on - under UNIX
>filesystems, atime updates are very common, and happen
>when there is just reading going on to update the access
>times. So yes, they can be the "bulk", but that's often
>only when the bulk is very little ;^)
>
>But it clearly does depend on the load.

Umm, git? ;-)

The closest I come to a streaming write load is probably a system update, but that's still all over the place. Everything else is pretty much synchronized random writes (sync in the sense something is waiting till it's all written safely, not necessarily all in the same order).

And noatime should be the default mount option for all filesystems, seriously. Forget backward compatibility for a moment, think about forward compatibility for a change. ;-)

>But that's part of what any GC worth its salt should be
>doing: not just moving blocks around, but also moving them
>around so that the mapping tables become less fragmented.
>You wan to move the right data around, so that next
>time you need an erase block, you've compacted all the
>used blocks, and have unused space that is all ready to
>be erased.
>
>So a good GC is (a) incremental - so that you don't get
>huge spikes when you suddenly have to do a lot and latency
>suffers and (b) compacting - so that you get big free
>areas for future erase cycles and don't have to spend all
>your time just copying stuff around to make them.

Seems like you're saying there's a (c) ordering. Basically putting adjacent logical blocks back next to each other physically as well. This would improve streamed reading of randomly written files as well. Or were you thinking about another way of compacting your remapping tables, like rebuilding the remaping tree or whatever data structure is used?

>No, no, no.
>
>You seem to really be talking about just a very stupid
>garbage collector that doesn't try to improve on block
>layout at all, and just desperately tries to find free
>blocks, and then in order to make those free blocks
>usable for re-writing you technically only ever need
>one single erase block.

I was thinking that you wouldn't need more than, say, 1 GB, or even 4 GB to do anything smart you'd want, and throwing more free space in wouldn't improve much, however smart. Having more flash chips dedicated to GC, on the other hand, would improve GC speed.

>But your job is going to be much simpler if the
>device isn't nearly full. If you are always at 99%
>capacity and only have one free erase block, then for
>every single random write, you will have to do a full
>erase cycle and rewrite a whole erase block.
>
>Your performance will suck.

There's a huge difference between one free erase block and 1 GB or much more than that. Considering you want to do GC incremental I'm not sure how 8 GB of scratch area instead of 4 would improve things much.

>And quite frankly, from the performance data I have seen,
>this is exactly what the previous-gen flash disks did. It
>is why they count their write IOPS in tens of writes per
>second - if that.
>
>And that's simply not acceptable.

And mind-boggling as well, that they did it that way at all...

Sadly there doesn't seem to be a decent 1.8" ATA SSD and I'm stuck with a painfully slow HD.

>No. You don't do less garbage collection. You do
>a better job at it!

If you do a better job at it you need to do it less, which is where the improvement comes from. ;-)

But it depends on what "less" means for GC. I meant doing less writes/more efficient GC.

>If you don't make your drive be 99% full, but you always
>know you have (say) at least 10-15% free, you can actually
>get away from that bad cycle of having to do a full erase
>block for every random write. If you have extra space to
>play with, you can make a generational GC that doesn't
>copy the old data immediately, but can do an erase cycle
>and then write multiple new writes to that - because you
>have extra space.

Ah, yes, I sort of assumed the drive had some extra space, but that isn't necessarily the case of course.

>Then, instead of trying to keep just ahead of the
>piper all the time, you try to keep quite a bit ahead, so
>that you always have tens (or hundreds) of pre-erased
>blocks available - and when you do end up having to copy
>old data in your GC, you try to defragment your block
>translations at the same time, so that you get new blocks
>that you can erase entirely.

It's easy to get decent performance while you're ahead, and I suppose in general you do stay ahead as most people don't have continuously random writing going on. But with a SSD that can do 10K random writes a second, the GC speed actually becomes the limiting factor when the thing is put under heavy load.

I'd love to know what the random write speed is for e.g. the Intel drive over a prolonged time, say hours or days (until it hits the bottom), where the full disk is written and overwritten. Would be nice to be able to reset them after this test though.

>But this is all impossible to do if you don't have any
>scratch area. If you are constantly 99% full, there's
>simply no "buffer" to defragment into - you're always just
>having to solve the immediate problem of getting that one
>next erase-block.

Yes, yes, of course. But please explain how much more scratch area makes things faster than just having a few GB, besides the fact that you can do more multiple GCs in parallel with a bigger scratch area. Easier, probably, but faster?

>More scratch area helps because you can do better block
>allocation when you have more freedom.

E.g. 1 GB scratch area has 8K 128KB erase blocks. That seems enough freedom, how does increasing that help allocating blocks better?

> There's a diminishing
>return, of course, and in the end up can never write faster
>than the flash itself can take data, but with a good
>block remapper, you generally should be able to approach
>writing data as quickly as the flash can take it, rather
>than spending all your time erasing and copying old data
>around just to make space for the (small) new data.

The first step is already taken, getting random writes near raw flash write speed. The next one is having GC that's fast enough to stay ahead all the time.