raid5: add a log device to fix raid5/6 write hole issue

This is my attempt to fix raid5/6 write hole issue, it's not for merge yet, I post it out for comments. Any comments and suggestions are welcome!

Thanks,
Shaohua

We expect a completed raid5/6 stack with reliability and high performance. Currently raid5/6 has 2 issues:

1. read-modify-write for small size IO. To fix this issue, a cache layer above raid5/6 can be used to aggregate write to full stripe write.
2. write hole issue. A write log below raid5/6 can fix the issue.

We plan to use a SSD to fix the two issues. Here we just fix the write hole issue.

1. We don't try to fix the issues together. A cache layer will do write acceleration. A log layer will fix write hole. The seperation will simplify things a lot.

2. Current assumption is flashcache/bcache will be used as the cache layer. If they don't work well, we can fix them or add a simple cache layer for raid write aggregation later. We also assume cache layer will absorb write, so log doesn't worry about write latency.

Quoted 17 lines · Shaohua Li

This is my attempt to fix raid5/6 write hole issue, it's not for merge yet, I post it out for comments. Any comments and suggestions are welcome!

Thanks,
Shaohua

We expect a completed raid5/6 stack with reliability and high performance. Currently raid5/6 has 2 issues:

1. read-modify-write for small size IO. To fix this issue, a cache layer above raid5/6 can be used to aggregate write to full stripe write.
2. write hole issue. A write log below raid5/6 can fix the issue.

We plan to use a SSD to fix the two issues. Here we just fix the write hole issue.

Quoted 8 lines

1. We don't try to fix the issues together. A cache layer will do write acceleration. A log layer will fix write hole. The seperation will simplify things a lot.

2. Current assumption is flashcache/bcache will be used as the cache layer. If they don't work well, we can fix them or add a simple cache layer for raid write aggregation later. We also assume cache layer will absorb write, so log doesn't worry about write latency.

It seems neither bcache nor dm-cache are tackling the write-buffering problem head on... they still seem to be concerned with some amount of read caching which I can see as useful for file servers and workstations, but not necessarily scale out storage.

I'll try to set aside time to take a look at the patch this week.

Quoted 27 lines · Dan Williams

Quoted 17 lines · Shaohua Li

This is my attempt to fix raid5/6 write hole issue, it's not for merge yet, I post it out for comments. Any comments and suggestions are welcome!

Thanks,
Shaohua

We expect a completed raid5/6 stack with reliability and high performance. Currently raid5/6 has 2 issues:

1. read-modify-write for small size IO. To fix this issue, a cache layer above raid5/6 can be used to aggregate write to full stripe write.
2. write hole issue. A write log below raid5/6 can fix the issue.

We plan to use a SSD to fix the two issues. Here we just fix the write hole issue.

Quoted 8 lines

1. We don't try to fix the issues together. A cache layer will do write acceleration. A log layer will fix write hole. The seperation will simplify things a lot.

2. Current assumption is flashcache/bcache will be used as the cache layer. If they don't work well, we can fix them or add a simple cache layer for raid write aggregation later. We also assume cache layer will absorb write, so log doesn't worry about write latency.

Quoted 6 lines

It seems neither bcache nor dm-cache are tackling the write-buffering problem head on... they still seem to be concerned with some amount of read caching which I can see as useful for file servers and workstations, but not necessarily scale out storage.

I'll try to set aside time to take a look at the patch this week.

Thanks! The cache layer is definitely what I'll focus on next. bcache supports writeback, I guess we can add an option to skip read data from backing disks for read caching if it's possible. Another option is writting a simple caching just for raid 5/6 write aggregation. We can append all data to a log, and maintain an index in memory. At raid shutdown, we can flush all data to raid disks, the index doesn't need presistent in disk, which makes the caching fairly simple.

Quoted 35 lines · On Tue, 31 Mar 2015 22:53:21 -0700 Shaohua Li <[email protected]> wrote:

Quoted 27 lines · Dan Williams

Quoted 17 lines · Shaohua Li

This is my attempt to fix raid5/6 write hole issue, it's not for merge yet, I post it out for comments. Any comments and suggestions are welcome!

Thanks,
Shaohua

We expect a completed raid5/6 stack with reliability and high performance. Currently raid5/6 has 2 issues:

1. read-modify-write for small size IO. To fix this issue, a cache layer above raid5/6 can be used to aggregate write to full stripe write.
2. write hole issue. A write log below raid5/6 can fix the issue.

We plan to use a SSD to fix the two issues. Here we just fix the write hole issue.

Quoted 8 lines

1. We don't try to fix the issues together. A cache layer will do write acceleration. A log layer will fix write hole. The seperation will simplify things a lot.

2. Current assumption is flashcache/bcache will be used as the cache layer. If they don't work well, we can fix them or add a simple cache layer for raid write aggregation later. We also assume cache layer will absorb write, so log doesn't worry about write latency.

Quoted 6 lines

It seems neither bcache nor dm-cache are tackling the write-buffering problem head on... they still seem to be concerned with some amount of read caching which I can see as useful for file servers and workstations, but not necessarily scale out storage.

I'll try to set aside time to take a look at the patch this week.

Quoted 7 lines

Thanks! The cache layer is definitely what I'll focus on next. bcache supports writeback, I guess we can add an option to skip read data from backing disks for read caching if it's possible. Another option is writting a simple caching just for raid 5/6 write aggregation. We can append all data to a log, and maintain an index in memory. At raid shutdown, we can flush all data to raid disks, the index doesn't need presistent in disk, which makes the caching fairly simple.

Surely if the index doesn't need to persist in disk, then the data doesn't either, as without the index you cannot find the data...

Quoted 17 lines · Shaohua Li

This is my attempt to fix raid5/6 write hole issue, it's not for merge yet, I post it out for comments. Any comments and suggestions are welcome!

Thanks,
Shaohua

We expect a completed raid5/6 stack with reliability and high performance. Currently raid5/6 has 2 issues:

1. read-modify-write for small size IO. To fix this issue, a cache layer above raid5/6 can be used to aggregate write to full stripe write.
2. write hole issue. A write log below raid5/6 can fix the issue.

We plan to use a SSD to fix the two issues. Here we just fix the write hole issue.

Quoted 8 lines

1. We don't try to fix the issues together. A cache layer will do write acceleration. A log layer will fix write hole. The seperation will simplify things a lot.

2. Current assumption is flashcache/bcache will be used as the cache layer. If they don't work well, we can fix them or add a simple cache layer for raid write aggregation later. We also assume cache layer will absorb write, so log doesn't worry about write latency.

It seems neither bcache nor dm-cache are tackling the write-buffering problem head on... they still seem to be concerned with some amount of read caching which I can see as useful for file servers and workstations, but not necessarily scale out storage.

I'll try to set aside time to take a look at the patch this week.

--
To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 27 lines · Dan Williams

Quoted 17 lines · Shaohua Li

This is my attempt to fix raid5/6 write hole issue, it's not for merge yet, I post it out for comments. Any comments and suggestions are welcome!

Thanks,
Shaohua

We expect a completed raid5/6 stack with reliability and high performance. Currently raid5/6 has 2 issues:

1. read-modify-write for small size IO. To fix this issue, a cache layer above raid5/6 can be used to aggregate write to full stripe write.
2. write hole issue. A write log below raid5/6 can fix the issue.

We plan to use a SSD to fix the two issues. Here we just fix the write hole issue.

Quoted 8 lines

1. We don't try to fix the issues together. A cache layer will do write acceleration. A log layer will fix write hole. The seperation will simplify things a lot.

2. Current assumption is flashcache/bcache will be used as the cache layer. If they don't work well, we can fix them or add a simple cache layer for raid write aggregation later. We also assume cache layer will absorb write, so log doesn't worry about write latency.

Quoted 6 lines

It seems neither bcache nor dm-cache are tackling the write-buffering problem head on... they still seem to be concerned with some amount of read caching which I can see as useful for file servers and workstations, but not necessarily scale out storage.

I'll try to set aside time to take a look at the patch this week.

There is one thing I do not really get.

The target is to avoid the "write hole", which happens, for example, when there is a sudden power failure.

Now, how can be assured, in that case, that the "cache" device is safe after the power is restored?

Doesn't this solution just shifts the problem from the array to a different device (SSD, for example)?

Speaking of SSD, these are quite "power failure" sensitive, it seems...

Quoted 35 lines · Piergiorgio Sartor

Quoted 27 lines · Dan Williams

Quoted 17 lines · Shaohua Li

This is my attempt to fix raid5/6 write hole issue, it's not for merge yet, I post it out for comments. Any comments and suggestions are welcome!

Thanks,
Shaohua

We expect a completed raid5/6 stack with reliability and high performance. Currently raid5/6 has 2 issues:

1. read-modify-write for small size IO. To fix this issue, a cache layer above raid5/6 can be used to aggregate write to full stripe write.
2. write hole issue. A write log below raid5/6 can fix the issue.

We plan to use a SSD to fix the two issues. Here we just fix the write hole issue.

Quoted 8 lines

1. We don't try to fix the issues together. A cache layer will do write acceleration. A log layer will fix write hole. The seperation will simplify things a lot.

2. Current assumption is flashcache/bcache will be used as the cache layer. If they don't work well, we can fix them or add a simple cache layer for raid write aggregation later. We also assume cache layer will absorb write, so log doesn't worry about write latency.

Quoted 6 lines

It seems neither bcache nor dm-cache are tackling the write-buffering problem head on... they still seem to be concerned with some amount of read caching which I can see as useful for file servers and workstations, but not necessarily scale out storage.

I'll try to set aside time to take a look at the patch this week.

Quoted 7 lines

There is one thing I do not really get.

The target is to avoid the "write hole", which happens, for example, when there is a sudden power failure.

Now, how can be assured, in that case, that the "cache" device is safe after the power is restored?

If you lose the cache the data-loss damage is greater, but this has always been the case with hardware-raid adapters.

Quoted 5 lines

Doesn't this solution just shifts the problem from the array to a different device (SSD, for example)?

Speaking of SSD, these are quite "power failure" sensitive, it seems...

Simple, if a cache-device is not itself power-failure safe then it should not be used for power-failure protection.

Quoted 27 lines · Dan Williams

Quoted 17 lines · Shaohua Li

This is my attempt to fix raid5/6 write hole issue, it's not for merge yet, I post it out for comments. Any comments and suggestions are welcome!

Thanks,
Shaohua

We expect a completed raid5/6 stack with reliability and high performance. Currently raid5/6 has 2 issues:

1. read-modify-write for small size IO. To fix this issue, a cache layer above raid5/6 can be used to aggregate write to full stripe write.
2. write hole issue. A write log below raid5/6 can fix the issue.

We plan to use a SSD to fix the two issues. Here we just fix the write hole issue.

Quoted 8 lines

1. We don't try to fix the issues together. A cache layer will do write acceleration. A log layer will fix write hole. The seperation will simplify things a lot.

2. Current assumption is flashcache/bcache will be used as the cache layer. If they don't work well, we can fix them or add a simple cache layer for raid write aggregation later. We also assume cache layer will absorb write, so log doesn't worry about write latency.

Quoted 6 lines

It seems neither bcache nor dm-cache are tackling the write-buffering problem head on... they still seem to be concerned with some amount of read caching which I can see as useful for file servers and workstations, but not necessarily scale out storage.

I'll try to set aside time to take a look at the patch this week.

There is one thing I do not really get.

The target is to avoid the "write hole", which happens, for example, when there is a sudden power failure.

Now, how can be assured, in that case, that the "cache" device is safe after the power is restored?

Doesn't this solution just shifts the problem from the array to a different device (SSD, for example)?

Quoted 2 lines

Now, how can be assured, in that case, that the "cache"

Quoted 1 line

device is safe after the power is restored?

You do sync write-ahead logging on the Flash cache. If it return successful, you do fire the writes to the RAID. If system crash/fails during the RAID writes (Write-hole), you just recover data by scanning write-ahead log in the flash cache and replay the logs into the RAID drives.

Quoted 8 lines · Alireza Haghdoost

Quoted 2 lines

Now, how can be assured, in that case, that the "cache"

Quoted 1 line

device is safe after the power is restored?

You do sync write-ahead logging on the Flash cache. If it return successful, you do fire the writes to the RAID. If system crash/fails during the RAID writes (Write-hole), you just recover data by scanning write-ahead log in the flash cache and replay the logs into the RAID drives.

Just to throw something nasty into the mix, I'm not sure whether it's SSDs or SD-cards, but there certainly *was* a spate of corrupted *controllers*.

In other words, a power failure would RELIABLY TRASH the device, if it happened at the wrong moment. Hopefully that's been fixed ...

Quoted 9 lines · Wols Lists

Quoted 8 lines · Alireza Haghdoost

Quoted 2 lines

Now, how can be assured, in that case, that the "cache"

Quoted 1 line

device is safe after the power is restored?

You do sync write-ahead logging on the Flash cache. If it return successful, you do fire the writes to the RAID. If system crash/fails during the RAID writes (Write-hole), you just recover data by scanning write-ahead log in the flash cache and replay the logs into the RAID drives.

Quoted 7 lines

Just to throw something nasty into the mix, I'm not sure whether it's SSDs or SD-cards, but there certainly *was* a spate of corrupted *controllers*.

In other words, a power failure would RELIABLY TRASH the device, if it happened at the wrong moment. Hopefully that's been fixed ...

That is certainly true. As Dan mentioned, the cache device it-self should be safe against power failure. I agree this is not the case for all SSD cards in the market but might be the case for Facebook. I hate to say this but It seems these efforts are useful dependent to what kind of hardware is deployed for cache device.

Quoted 8 lines · Alireza Haghdoost

Quoted 2 lines

Now, how can be assured, in that case, that the "cache"

Quoted 1 line

device is safe after the power is restored?

You do sync write-ahead logging on the Flash cache. If it return successful, you do fire the writes to the RAID. If system crash/fails during the RAID writes (Write-hole), you just recover data by scanning write-ahead log in the flash cache and replay the logs into the RAID drives.

Just to throw something nasty into the mix, I'm not sure whether it's SSDs or SD-cards, but there certainly *was* a spate of corrupted *controllers*.

In other words, a power failure would RELIABLY TRASH the device, if it happened at the wrong moment. Hopefully that's been fixed ...

This is my attempt to fix raid5/6 write hole issue, it's not for merge yet, I post it out for comments. Any comments and suggestions are welcome!

Thanks,
Shaohua

We expect a completed raid5/6 stack with reliability and high performance. Currently raid5/6 has 2 issues:

1. read-modify-write for small size IO. To fix this issue, a cache layer above raid5/6 can be used to aggregate write to full stripe write.
2. write hole issue. A write log below raid5/6 can fix the issue.

We plan to use a SSD to fix the two issues. Here we just fix the write hole issue.

1. We don't try to fix the issues together. A cache layer will do write acceleration. A log layer will fix write hole. The seperation will simplify things a lot.

2. Current assumption is flashcache/bcache will be used as the cache layer. If they don't work well, we can fix them or add a simple cache layer for raid write aggregation later. We also assume cache layer will absorb write, so log doesn't worry about write latency.

3. For log, write will hit to log disk first, then raid disks, and finally IO completion is reported. An optimal way is to report IO completion just after IO hits to log disk to cut write latency. But in that way, read path need query log disk and increase complexity. And since we don't worry about write latency, we choose a simple soltuion. This will be revisited if there is performance issue.

This design isn't intrusive for raid5/6. Actully only very few changes of existing code is required.

Log looks like jbd. Stripe IO to raid disks will be written to log disk first in atomic way. Several stripe IO will consist a transaction. If all stripes of a transaction are finished, the tranaction can be checkpoint.

Basic logic of raid 5/6 write will be:
1. normal raid5/6 steps for a stripe (fetch data, calculate checksum, and etc). log hooks to ops_run_io.
2. stripe is added to a transaction. Write stripe data to log disk (metadata block, stripe data)
3. write commit block to log disk
4. flush log disk cache.
5. stripe is logged now and normal stripe handling continues

Transaction checkpoint process:
1. all stripes of a transaction are finished
2. flush disk cache of all raid disks
3. change log super to reflect new log checkpoint position
4. WRITE_FUA log super

metadata, data and commit block IO can run in the meaning time, as checksum will be used to make sure their data is correct (like jbd2). Log IO doesn't wait 5s to start like jbd, instead the IO will start every time a metadata block is full. This can cut some latency.

Disk layout:

|super|metadata|data|metadata| data ... |commitdata|metadata|data| ... |commitdata| super, metadata, commit will use one block

This is an initial version, which works but a lot of stuffes are missing:
1. error handling
2. log recovery and impact to raid resync (don't need resync anymore)
3. utility changes

The big question is how we report log disk. In this patch, I simply use a spare disk for testing. We need a new raid disk role for log disk.

Signed-off-by Shaohua Li <[email protected]>

Quoted 72 lines · On Mon, 30 Mar 2015 15:25:17 -0700 Shaohua Li <[email protected]> wrote:

This is my attempt to fix raid5/6 write hole issue, it's not for merge yet, I post it out for comments. Any comments and suggestions are welcome!

Thanks,
Shaohua

We expect a completed raid5/6 stack with reliability and high performance. Currently raid5/6 has 2 issues:

1. read-modify-write for small size IO. To fix this issue, a cache layer above raid5/6 can be used to aggregate write to full stripe write.
2. write hole issue. A write log below raid5/6 can fix the issue.

We plan to use a SSD to fix the two issues. Here we just fix the write hole issue.

1. We don't try to fix the issues together. A cache layer will do write acceleration. A log layer will fix write hole. The seperation will simplify things a lot.

2. Current assumption is flashcache/bcache will be used as the cache layer. If they don't work well, we can fix them or add a simple cache layer for raid write aggregation later. We also assume cache layer will absorb write, so log doesn't worry about write latency.

3. For log, write will hit to log disk first, then raid disks, and finally IO completion is reported. An optimal way is to report IO completion just after IO hits to log disk to cut write latency. But in that way, read path need query log disk and increase complexity. And since we don't worry about write latency, we choose a simple soltuion. This will be revisited if there is performance issue.

This design isn't intrusive for raid5/6. Actully only very few changes of existing code is required.

Log looks like jbd. Stripe IO to raid disks will be written to log disk first in atomic way. Several stripe IO will consist a transaction. If all stripes of a transaction are finished, the tranaction can be checkpoint.

Basic logic of raid 5/6 write will be:
1. normal raid5/6 steps for a stripe (fetch data, calculate checksum, and etc). log hooks to ops_run_io.
2. stripe is added to a transaction. Write stripe data to log disk (metadata block, stripe data)
3. write commit block to log disk
4. flush log disk cache.
5. stripe is logged now and normal stripe handling continues

Transaction checkpoint process:
1. all stripes of a transaction are finished
2. flush disk cache of all raid disks
3. change log super to reflect new log checkpoint position
4. WRITE_FUA log super

metadata, data and commit block IO can run in the meaning time, as checksum will be used to make sure their data is correct (like jbd2). Log IO doesn't wait 5s to start like jbd, instead the IO will start every time a metadata block is full. This can cut some latency.

Disk layout:

|super|metadata|data|metadata| data ... |commitdata|metadata|data| ... |commitdata| super, metadata, commit will use one block

This is an initial version, which works but a lot of stuffes are missing:
1. error handling
2. log recovery and impact to raid resync (don't need resync anymore)
3. utility changes

Quoted 4 lines

The big question is how we report log disk. In this patch, I simply use a spare disk for testing. We need a new raid disk role for log disk.

Signed-off-by Shaohua Li <[email protected]>

Hi,
thanks for the proposal and the patch which makes it nice and concrete...

I should start out by saying that I'm not really sold on the importance of the issues you are addressing here.
The "write hole" is certainly of theoretical significance, but I do wonder how much practical significance it has. It can only be a problem if you have a system failure and a degraded array at the same time, and both of those should be very rare event individually...
I wonder if anyone has *ever* lost data to the "write hole".

As for write-ahead caching to reduce latency, most writes from Linux are async and so would not benefit from that. If you do have a heavily synchronous write load, then that can be fixed in the filesystem. e.g. with ext3 and an external log to a low-latency device you can get low-latency writes which largely mask the latency issues introduced by RAID5.

The fact that I'm "not really sold" doesn't mean I am against them ... maybe it is just an encouragement for someone to sell them more :-)

While I understand that keeping the two separate might simplify the problem, I'm not at all sure it is a good idea. It would mean that every data block were written three times - once to the write-ahead log, once to the write-hole-protection log, and once to the RAID5.

Your code does avoid write-hole-protection for fill-stripe-writes, and this would greatly reduce the number of block that were written multiple times. However I'm not convinced that is correct.
A reasonable goal is that if the system crashes while writing to a storage device, then reads should return the old data or not new data, not anything else. A crash in the middle of a full-stripe-write to a degraded array could result in some block in the stripe appearing to contain data that is different to both the old and the new. If you are going to close the whole, I think it should be done properly.

A combined log would "simply" involve writing every data block and every compute parity block (with index information) to the log device. Replaying the log would collect data blocks and flush out those in a stripe once the parity block(s) for that stripe became available.

I think this would actually turn into a fairly simple logging mechanism.

Quoted 9 lines

Your code does avoid write-hole-protection for fill-stripe-writes, and this would greatly reduce the number of block that were written multiple times. However I'm not convinced that is correct.
A reasonable goal is that if the system crashes while writing to a storage device, then reads should return the old data or not new data, not anything else. A crash in the middle of a full-stripe-write to a degraded array could result in some block in the stripe appearing to contain data that is different to both the old and the new. If you are going to close the whole, I think it should be done properly.

I can do it simpley. But don't think this assumption is true. If you write to a disk range and there is failure, there is nothing guarantee you can either read old data or new data.

Quoted 7 lines

A combined log would "simply" involve writing every data block and every compute parity block (with index information) to the log device. Replaying the log would collect data blocks and flush out those in a stripe once the parity block(s) for that stripe became available.

Quoted 1 line

I think this would actually turn into a fairly simple logging mechanism.

It's not simple at all. It's unlikely we write data and parity continuously in disk and in the same time. This will make log checkpoint fairly complex.

Quoted 10 lines · On Wed, 1 Apr 2015 16:40:57 -0700 Shaohua Li <[email protected]> wrote:

Quoted 9 lines

Your code does avoid write-hole-protection for fill-stripe-writes, and this would greatly reduce the number of block that were written multiple times. However I'm not convinced that is correct.
A reasonable goal is that if the system crashes while writing to a storage device, then reads should return the old data or not new data, not anything else. A crash in the middle of a full-stripe-write to a degraded array could result in some block in the stripe appearing to contain data that is different to both the old and the new. If you are going to close the whole, I think it should be done properly.

Quoted 3 lines

I can do it simpley. But don't think this assumption is true. If you write to a disk range and there is failure, there is nothing guarantee you can either read old data or new data.

If you write a range of blocks to a normal disk and crash during the write, each block will contain either the old data or the new data.
If you write a range to a degraded RAID5 and crash during the write, you cannot make that same guarantee.
I don't know how important this is, but then I don't really know how important any of this is.

Quoted 7 lines

Quoted 7 lines

A combined log would "simply" involve writing every data block and every compute parity block (with index information) to the log device. Replaying the log would collect data blocks and flush out those in a stripe once the parity block(s) for that stripe became available.

Quoted 5 lines

Quoted 1 line

I think this would actually turn into a fairly simple logging mechanism.

It's not simple at all. It's unlikely we write data and parity continuously in disk and in the same time. This will make log checkpoint fairly complex.

I don't see any cause for complexity. Let me be more explicit.

I imagine that all data remains in the stripe cache, in memory, until it is finally written to the RAID5. So the stripe cache will need to be quite a bit bigger.

Every time we get a block that we want to write, either a new data block or a a computed parity block, we queue it to the log.

The log works like this:
- take the first (e.g.) 256 blocks in the queue, create a header to describe them, write the header with FUA, then write all the data blocks. If there are fewer than 256, just write what we have.
- when the header write completes, all blocks written *previously* are now safe and we can call bio_end_io on data or unlock the stripe for parity.
- loop back and write some more blocks. If there are no blocks to write, write a header which describes an empty set of blocks, and wait for more blocks to appear.

Each stripe_head needs to track (roughly) where the relevant blocks were written so it can release them when the stripe is written.
I would conceptually divide the log into 32 regions and keep a 32bit number with each stripe. When a block is assigned to a region in the log, the relevant bit is set for the stripe, and a per-region counter is incremented. When a stripe completes its write, the region counters for all the bits are cleared. The log cannot progress into a region which has a non-zero counter.

Hi,
This is what I'm working on now, and hopefully had the basic code running next week. The new design will do cache and fix the write hole issue too. Before I post the code out, I'd like to check if the design has obvious issues.

Quoted 2 lines

I'm not enthusiastic to use stripe cache though, we can't keep all data in stripe cache. What we really need is an index.

Thanks,
Shaohua

Main goal is to aggregate write IO to hopefully make full stripe IO and fix the write hole issue. This might speed up read too, but it's not optimized for read, eg, we don't proactivly cache data for read. The aggregation makes a lot of sense for workloads which sequentially write to several files. Such workloads are popular in today's datacenter.

Here cache = cache disk, generally SSD. raid = raid array or raid disks (excluding cache disk)
-------------------------
cache layout will like this:

|super|chunk descriptor|chunk data|

We divide cache to equal sized chunks. each chunk will have a descriptor. Its size will be raid_chunk_size * raid_disks. That is the cache chunk can store a whole raid chunk data and parity.

Write IO will store to cache chunks first and then flush to raid chunks. We use fixed size chunk:

(quoted diff) +0 -3

-manage cache space easily. We don't need a complex tree-like index
 
-flush data from cache to raid easily. data and parity are in the same chunk
 
-reclaim space is easy. when there is no free chunk in cache, we must try to

free some chunks, eg, reclaim. We do reclaim in chunk unit. reclaim a chunk just means flush the chunk from cache to raid. If we use complex data structure, we will need garbage collection and so on.

-The downside is we waste space. Eg, a single 4k data will use a whole chunk in cache. But we can reclaim chunks with low utilization quickly to mitgate this issue partially.

--------------------
chunk descriptor looks like this:

chunk_desc {
	u64 seq;
	u64 raid_chunk_index;
	u32 state;
	u8 bitmaps[];
}

seq: seq can be used to implement LRU-like algorithm for chunk reclaim. Every time data is written to the chunk, we update the chunk's seq. When we flush a chunk from cache to raid, we freeze the chunk (eg, the chunk can't accept new IO). If there is new IO, we write the new IO to another chunk. The new chunk will have a bigger seq than original chunk. crash and reboot can use the seq to detinguish which chunk is newer.

raid_chunk_index: where the chunk should be flushed to raid

state: chunk state. Currently I defined 3 states

(quoted diff) +0 -3

-FREE, the chunk is free
-RUNNING, the chunk maps to raid chunk and accepts new IO
-PARITY_INCORE, the chunk has both data and parity stored in cache

bitmaps: each page of data and parity has one bit. 1 means present. Store data bits first.

-----IO READ PATH------
IO READ will check each chunk desc. If data is present in cache, dispatch to cache. otherwise to raid.

-----IO WRITE PATH------
1. find or create a chunk in cache
2. write to cache
3. write descriptor

We write descriptor immediately in asynchronous way to reduce data loss, the chunk will be RUNNING state.

-For normal write, IO return after 2. This will cut latency too. If there is a crash, the chunk state might be FREE or bitmap isn't set. In either case, this is the first write to the chunk, IO READ will read raid and get old data. We meet the symantics. If data isn't in cache, we will read old data in cache, we meet the symantics too.

-For FUA write, 2 will be a FUA write. When 2 finishes, run 3 with FUA. IO return after 3. Crash after IO return deosn't impact symantics. We will read old or new data if crash happens before IO return, which is the similar like the normal write case.

-For FLUSH, wait all previous descriptor write finish and then flush cache disk cache. In this way, we guarantee all previous write hit cache.

-----chunk reclaim--------
1. select a chunk
2. freeze the chunk
3. copy chunk data from cache to raid, so stripe state machine runs, eg, calculate parity and so on
4. Hook to raid5 run_io. We write parity to cache
5. flush cache disk cache
6. mark descriptor PARITY_INCORE, and WRITE_FUA to cache
7. raid5 run_io continue run. data and parity write to raid disks
8. flush all raid disk cache
9. mark descriptor FREE, WRITE_FUA to cache

We will batch several chunks for reclaim for better performance. FUA write can be replaced with FLUSH too.

If there is a crash before 6, descriptor state will be RUNNING. Recovery just need discard the parity bitmap. If there is a crash before 9, descriptor state will be PARITY_INCORE, recovery must copy both data and parity to raid. --
To unsubscribe from this list: send the line "unsubscribe linux-raid" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 5 lines · On Wed, 8 Apr 2015 17:43:11 -0700 Shaohua Li <[email protected]> wrote:

Hi,
This is what I'm working on now, and hopefully had the basic code running next week. The new design will do cache and fix the write hole issue too. Before I post the code out, I'd like to check if the design has obvious issues.

I can't say I'm excited about it....

You still haven't explained why you would ever want to read data from the "cache"? Why not just keep everything in the stripe-cache until it is safe

Quoted 2 lines · in the RAID. I asked before and you

Quoted 2 lines

I'm not enthusiastic to use stripe cache though, we can't keep all data in stripe cache. What we really need is an index.

which is hardly an answer. Why cannot you keep all the data in the stripe cache? How much data is there? How much memory can you afford to dedicate?

You must have some very long sustained bursts of writes which are much faster than the RAID can accept in order to not be able to keep everything in memory.

Your cache layout seems very rigid. I would much rather a layout that was very general and flexible. If you want to always allocate a chunk at a time then fine, but don't force that on the cache layout.

The log really should be very simple. A block describing what comes next, then lots of data/parity. Then another block and more data etc etc. Each metadata block points to the next one.
If you need an index of the cache, you keep that in memory. On restart, you read all of the metadata blocks and built up the index.

I think that space in the log should be reclaimed in exactly the order that
it is written, so the active part of the log is contiguous. Obviously
individual blocks become inactive in arbitrary order as they are written to the RAID, but each extent of the log becomes free in order.
If you want that to happen out of order, you would need to present a very good reason.

Quoted 34 lines · NeilBrown

Quoted 5 lines · On Wed, 8 Apr 2015 17:43:11 -0700 Shaohua Li <[email protected]> wrote:

Hi,
This is what I'm working on now, and hopefully had the basic code running next week. The new design will do cache and fix the write hole issue too. Before I post the code out, I'd like to check if the design has obvious issues.

I can't say I'm excited about it....

You still haven't explained why you would ever want to read data from the "cache"? Why not just keep everything in the stripe-cache until it is safe

Quoted 2 lines · in the RAID. I asked before and you

Quoted 2 lines

I'm not enthusiastic to use stripe cache though, we can't keep all data in stripe cache. What we really need is an index.

which is hardly an answer. Why cannot you keep all the data in the stripe cache? How much data is there? How much memory can you afford to dedicate?

You must have some very long sustained bursts of writes which are much faster than the RAID can accept in order to not be able to keep everything in memory.

Your cache layout seems very rigid. I would much rather a layout that was very general and flexible. If you want to always allocate a chunk at a time then fine, but don't force that on the cache layout.

The log really should be very simple. A block describing what comes next, then lots of data/parity. Then another block and more data etc etc. Each metadata block points to the next one.
If you need an index of the cache, you keep that in memory. On restart, you read all of the metadata blocks and built up the index.

Quoted 6 lines

I think that space in the log should be reclaimed in exactly the order that
it is written, so the active part of the log is contiguous. Obviously
individual blocks become inactive in arbitrary order as they are written to the RAID, but each extent of the log becomes free in order.
If you want that to happen out of order, you would need to present a very good reason.

I came to the same idea when I'm thinking about a caching layer, but the memory size is the main blocking issue. If the solution requires a large amount of extra memory, it's not cost effective, so a hard sell to replace hardware raid with software raid. The design completely depends on if we can store all data in memory. I don't have an anwser yet how much memory we should use to make the aggregation efficient. Guess only number can talk. I'll try to collect some data and get back to you.

Quoted 42 lines · Shaohua Li

Quoted 34 lines · NeilBrown

Quoted 5 lines · On Wed, 8 Apr 2015 17:43:11 -0700 Shaohua Li <[email protected]> wrote:

Hi,
This is what I'm working on now, and hopefully had the basic code running next week. The new design will do cache and fix the write hole issue too. Before I post the code out, I'd like to check if the design has obvious issues.

I can't say I'm excited about it....

You still haven't explained why you would ever want to read data from the "cache"? Why not just keep everything in the stripe-cache until it is safe

Quoted 2 lines · in the RAID. I asked before and you

Quoted 2 lines

I'm not enthusiastic to use stripe cache though, we can't keep all data in stripe cache. What we really need is an index.

which is hardly an answer. Why cannot you keep all the data in the stripe cache? How much data is there? How much memory can you afford to dedicate?

You must have some very long sustained bursts of writes which are much faster than the RAID can accept in order to not be able to keep everything in memory.

Your cache layout seems very rigid. I would much rather a layout that was very general and flexible. If you want to always allocate a chunk at a time then fine, but don't force that on the cache layout.

The log really should be very simple. A block describing what comes next, then lots of data/parity. Then another block and more data etc etc. Each metadata block points to the next one.
If you need an index of the cache, you keep that in memory. On restart, you read all of the metadata blocks and built up the index.

Quoted 6 lines

I think that space in the log should be reclaimed in exactly the order that
it is written, so the active part of the log is contiguous. Obviously
individual blocks become inactive in arbitrary order as they are written to the RAID, but each extent of the log becomes free in order.
If you want that to happen out of order, you would need to present a very good reason.

Quoted 8 lines

I came to the same idea when I'm thinking about a caching layer, but the memory size is the main blocking issue. If the solution requires a large amount of extra memory, it's not cost effective, so a hard sell to replace hardware raid with software raid. The design completely depends on if we can store all data in memory. I don't have an anwser yet how much memory we should use to make the aggregation efficient. Guess only number can talk. I'll try to collect some data and get back to you.

Another consideration to keep in mind is persistent memory. I'm working on an in-kernel mechanism to claim and map pmem and a raid-write-cache is an obvious first application. I'll include you on the initial submission of that capability.