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.

>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.

>Most writes are random writes, at least on my system. The
>writes that aren't don't have to be quick either.

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.

>>So in most use, you'd have a mix of small random writes
>>and larger contiguous ones, and the realistic situation is
>>that the remapping never gets really bad - at least not as
>>bad as the extreme benchmarks make it.
>
>I'm not really convinced of this. It may take a bit of
>time, but you'll get there eventually.

Well, it's true that you'll get there "eventually" if you
never try to clean things up.

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.

>>- garbage collection is much easier if you have
>>lots of free space.
>
>I don't see how this is. Some free space is needed, sure,
>but not that much. Garbage collection is just not needed
>when there's free space left...

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.

With that really basic and stupid model, you can always
make room for a new write by finding one free block in
your FTL tables, then doing a erase (bigger than the
block size), copying all the non-free blocks that shared
the erase block with the rewritten one to the newly
erased block, writing the new data, and updating the
translations.

Yes, yes, you can do it that way - but if you do, you'll
always actually be esasing and writing much more
than the blocks you actually want to write, since
you'll be copying all the other blocks around it too.

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.

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.

>>Now, you could actually sell the exact same drive
>>with a capacity of just 75GB, and you'd essentially have
>>doubled your "scratch area" to do GC in. End result:
>>smoother garbage collection with fewer GC spikes.
>
>Only way that is possible is by allowing more space be
>wasted, or in other words, do less garbage collection by
>allowing more fragmentation to happen.

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

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.

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.

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.

Is it simple? No. Now SanDisk is talking about their new
ExtremeFFS(tm) vs their old TrueFFS(tm), and I'm sure they
spent lots of effort on this all. I'm sure the new thing
is much more complex. But the thing is, it's worth it.

>More scratch area doesn't help a bit as far as I can see.

More scratch area helps because you can do better block
allocation when you have more freedom. 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.

Linus