Some observations on the idea of an intent-logging bitmap.
1/ You don't want or need very fine granularity. The value of this is
to speed up resync time. Currently it is limited by drive
bandwidth. If you have lots of little updates due to fine
granularity, you will be limited by seek time.
One possibly reasonable approach would be to pick a granulatity
such that it takes about as long to read or write a chunk and it
would to seek to the next one. This probably means a few hundred
kilobytes. i.e. one bit in the bitmap for every hundred K.
This would require a 125K bitmap for a 100Gig drive.
Another possibility would be a fixed size bitmap - say 4K or 8K.
An 8K bitmap used to map a 100Gig drive would be 1.5Meg per bit.
This may seem biggish, but if your bitmap were sparse, resync would
still be much much faster, and if it were dense, having a finer
grain in the bitmap isn't going to speed things up much.
2/ You cannot allocate the bitmap on demand.
Demand happens where you are writing data out, and when writing
data out due to high memory pressure, kmalloc *will* fail.
Relying on kmalloc in the write path is BAD. That is why we have
mempools which pre-allocate.
For the bitmap, you simply need to pre-allocate everything.
3/ Internally, you need to store a counter for each 'chunk' (need a
better word, this is different from the raid chunksize, this is the
amount of space that each bit refers to).
The counter is needed so you know when the bit can be cleared.
This too must be pre-allocated and so further limits the size of
your bitmap.
16 bit counters would use less ram and would allow 33553920 bytes
(65535 sectors) per 'chunk' which, with an 8K bitmap, puts an upper
limit of 2 terabytes per device, which I think is adequate. (that's
per physical device, not per raid array).
Or you could just use 32 bit counters.
4/ I would use device plugging to help reduce the number of times you
have to write the intent bitmap.
When a write comes in, you set the bit in the bitmap, queue the
write on a list of 'plugged' requests, and mark the device as
'plugged'. The device will eventually be unplugged, at which point
you write out the bitmap, then release all the requests to the
lower devices.
You could optimise this a bit, and not bother plugging the device
if it wasn't already plugged, and the request only affected bits
that were already set.
NeilBrown
Neil,
You've made some really good points and suggestions...thanks...
1/ You don't want or need very fine granularity. The value of this is
to speed up resync time. Currently it is limited by drive
bandwidth. If you have lots of little updates due to fine
granularity, you will be limited by seek time.
One more reason why an adjustable bit to block ratio would be nice :)
...
2/ You cannot allocate the bitmap on demand.
Hmm...that's a very good point. I had not really thought about that, but
you're right. Maybe there are some advantages to having a simple, flat,
pre-allocated bitmap...although, I do really like Peter's two-level
on-demand allocation scheme. Maybe we could do partial pre-allocation,
using the pre-allocated pages when we're under pressure and kmalloc
fails, and doing on-demand allocation the rest of the time? Another
idea, expanding on what Peter has already done with marking the pointer
with an "address" of 1 if the kmalloc fails (this means that the bitmap
degrades from 1bit/1k to 1bit/4MB, which is not a terrible thing, all in
all). What if we were clever and used more than just one bit when the
allocation fails, so that the ratio could be kept more reasonable (I'm
thinking the 1bit/4MB is OK now, but with a default bit/block ratio
that's much higher, it might get out of control)...maybe something
similar to the IS_ERR and ERR_PTR macros that are elsewhere in the
kernel? Those use 1000 values (I think...) that are known not to be
valid pointer values as error values instead.
3/ Internally, you need to store a counter for each 'chunk' (need a
Yes, in order to use a bit/block ratio other than 1 bit/1k, we need some
mechanism for tracking multiple pending writes to the same 'chunk'. One
way to do this is to keep a counter (say 16 or 32 bits) on each chunk,
rather than just a single bit. Another alternative might be to queue the
writes (using a hash on the 'chunk' number, for quick insertion and
deletion). This would tell us how many writes are pending for a given
'chunk', and allow us to clear the bit at the appropriate time (once the
last pending write for the 'chunk' had finished). This could be expanded
later to queueing entire requests (including data) so we could do full
transaction logging, so that a short network outage (how short depends
on how much $$ (sorry Peter, pesetas^Weuros) you want to lay out for RAM
:)) could be recovered from quickly, by just replaying the already
queued data.
4/ I would use device plugging to help reduce the number of times you
have to write the intent bitmap.
That's a good idea. I also think that with a large bit/block ratio, the
bitmap syncing will be fairly efficient, since the bitmap will
only have to be synced once per XXXk of data written.
--
Paul