Version 1.0

Heinz Mauelshagen (hjm@redhat.com)

Copyright Red Hat GmbH

dm-raid45 - A Device-Mapper target for RAID4 and RAID5 mappings

Device-Mapper, the Linux 2.6 kernel generic device-mapping facility, is capable of mapping block devices in various ways (eg. linear, striped, mirrored). The mappings are implemented in runtime loadable plugins called mapping targets, which take a logical device address and sector and remap it to one or more underlying (logical) device(s).

Targets can be implemented to support arbitrary software RAID solutions on Linux 2.6, such as RAID4 and RAID5.

dm-raid45 is a new device-mapper target (i.e. a mapping plugin) to drive RAID (Redundant Array of independant disks) sets.

RAID level 4 with a dedicated parity drive and RAID level 5 with rotating parity are both supported by this target. It is capable of doing background resynchronization of sets utilizing a dirty-log, which keeps track of dirtied regions (i.e. those with writes in flight).

At set activation, the dirty-log is questioned and resynchronization is started for any dirty regions one-by-one in order to regain the consistency of the RAID set i.e. after a system crash.

The same mechanism is used to set a new RAID set up by dirtying all regions and activating the set, hence causing resynchronization of all regions of the new set.

Full read/write access is possible to the whole RAID set during synchronization.

In case one disk fails within a set, the set will be degraded and access to data is still possible. The defective drive can be replaced and dm-raid45 be configured to resynchronize the new drive.

My talk will give a short device-mapper architecture/feature overview and elaborate on the dm-raid45 target feature set.

Device-Mapper Architecture

The generic block remapping subsystem „Device-Mapper“ (aka „dm“) handles virtual block devices called mapped devices (aka „md“), which get remapped to other underlying block devices in a stacked way. The logical address space of mds is defined via ASCII formated mapping tables. Mapping table lines define segments in the address space of the md in units of sectors (512 bytes). An md can have an arbitrary amount of address segments.
Dm falls appart into the following kernel and user space components:

kernel
o core
o ioctl interface
o io
o kcopyd
o mapping targets
o dirty log
o region hash

user space
o library
o dmsetup tool

The kernel core covers all functionality to create and remove mapped devices, to load and unload their mapping tables and to register mapping targets. It has no concept how to remap an io which is the task of mapping targets. Mapping targets are plug-ins (loadable at runtime) for a growing list of mappings such as linear, striped, mirror, multipath, crypt, snapshot, zero, error and, of course, raid45. The target interface allows passing an io (i.e. a bio in Linux 2.6) to the target, which can do whatever it feels appropriate with it.
That can be as simple as changing bio content (i.e. bi_bdev and bi_sector) and pass it to the lower layers, hence remapping the bio to another block device or it can be more complex as queuing it to an internal list to merge it into an internal cache for io, hence causing io to be carried out to multiple underlying block devices auch as in case of dm-raid45.
The device mapper core will call into the target for other purposes as the mapping of an io such as mapping table segment create/destroy, to retrieve the actual table or the md status, pass messages to the target in order to influence its state or suspend/resume io activity on a target as well.
The ioctl interface exposes all dm kernel funtions available to the user space library, which in turn is used by applications like dmsetup, dmraid or lvm2.
It is recommended that applications utilizing dm use the dm library, because it hides different versions of the ioctl interface from them.
Dmsetup, which of course accesses the ioctl interface through libdevmapper, is a simple 'volume manager' tool, which mainly allows mapped device create/destroy and load/unload mapping tables functionality.
Mapping tables define the logical address space of any given mapped device.
Their syntax is: 'start length target target_paramters'.
Start+length define a segment in the mapped devices address space. All size parameters in dm (such as start) are in units of sectors of 512 bytes.
'target' is the keyword, which selects one of the mapping targets (i.e. 'linear').
This very powerful syntax allows an arbitrary amount of segments and each of them can use a different target. E.g.:
0 1024 linear /dev/hda 0
1024 4096 striped 3 128 /dev/hda 1024 /dev/hdb 0 /dev/hdc 0
maps the first 1024 sector to offset 0 on /dev/hda using the 'linear' mapping target and stripes the next 3072 sectors to 3 devices with stride size 128 sectors.
An io module which contains low-level routines for synchronous and asynchronous io operations is reused by kcopyd and the targets in order to avoid code duplication. Kcopyd is the dm kernel copy daemon, which allows copy requests from one source disk to as many as 32 destination disks. I.e. the mirror target uses kcopyd to resynchronize mirror sets in case they got created or partially ran out of sync because e.g. of a system crash.
A dirty log with different types (transient, resident and cluster) is used to keep track of the state of regions (size configurable) within the md's address space in order to be able to resynchronize dirty regions after e.g. a system crash.
The region hash allows keeping track of state of regions within the md's address space such as CLEAN, DIRTY, NOSYNC and RECOVERING. This in combination with the dirty log is used by targets which keep data redundant such as the mirror and the raid45 target in order to keep the integrity of the data. Because multiple write ios can be in flight against any single region at once, for any write io being carried out against a region, a counter is being incremented and the regions state is set to dirty in the dirty log when the counter goes to 1. For each end io of a write to a region, the counter gets decremented. Only if the counter drops to zero, the region is cleaned in the dirty log.
After a system crash, any dirty regions in the log get promoted to NOSYNC, hence subject to region resynchronization.
As mentioned, utilizing dm means calling the dm library functions to create an md, load its mapping table and access the devnode created for the md (default namespace /dev/mapper/). In test environments this can be done using your favorate text editor to create a mapping table and hand that to dmsetup together with the mapping table and a name for the md. In case you use lvm2, you normally ain't see dm at all, because you will be accessing the well known lvm UI or even a GUI deployed with the distro you're using
(e.g. system-config-lvm for Fedora Core or RHEL).

RAID basics

The essential purpose to have a RAID4/RAID5 software, is to gain resilience against any single disk drive failure, hence you're not going to loose your data in case just one drive fails. In order to achive this, disks need to be grouped into RAID sets, which keep a minimum amount of redundant data with the set to survive a single drive members death.
The minimum number of disks in a set is 3, because of an xor based block level crc algorithm used to combine a minimum of 2 blocks on 2 different disks to create redundant data (a parity block). In general, N (N>2) blocks will be xored to create the parity information stored on a different disk from the ones the xored blocks are located on. The xor algorithm has the advantage to be symmetric, which allows the same code to be used for both creation of the redundant and reconstruction of any lost data. In theory, N can be arbitrarilly large, but because all disks need to be read in case a drive fails, going to large drive numbers per set would cause serious performance degration. In practice N is <10 (typically 3-7).
In case of RAID4, a dedicated parity disk is used to hold all parity blocks..
RAID4 essentially looks like a striped set with N-1 (N>2) data disks (i.e. Data chunks rotate on N-1 disks) plus an additional disk to hold all parity blocks being calculated from the data blocks. The parity disk is the performance bottleneck with RAID4, because any block update causes a parity block update as well, hence causing parallel io to the data disks for different data blocks but sequential io to the parity disk for the related parity blocks.
RAID5 avoids this bottleneck by rotating data and parity blocks on all disks of the RAID set, hence avoiding the single parity disk perfomance issue of RAID4 by parallelising all io (data and parity) to all disks.. Different data and parity address rotation patterns are possible; there's 4 different selectable algorithms to locate the data and parity chunks with RAID5 (left-symmetric, left-asymmetric, right symmetric, right-asymmetric).

dm-raid45

For any given data block, a layout algorithm is used to calculate the address of the data disk for this block, the one of the parity block and a starting address of the related stripe.
Stripes are mandatory, because all data blocks from all disks of a set need to be present in memory in order to be able to calculate a parity block. A configurable amount of stripes gets preallocated and added to a stripe cache. In order to gain performance, the stripes don't have single disk blocks per drive hanging off but chunks, which are size configurable (n^^2 * pagesize; default: 64KB). The stripes in the cache are being hashed in order to be able to look them up fast. In case there's no hit for a given stripe address in the cache, a least recently used inactive one is used. If all stripes are active, the io needs to wait until a stripe becomes available.
The dm-raid45 target (target name for mapping tables is 'raid45') has to implement a couple of building blocks in order to address the above outlined functionality and resuses some alreday given ones (namly io, dirty log and region hash):

the interface to the core
o target register/unregister
o the mapping table construction/destruction
o the map function itself
o the resume/postsuspend functions

the stripe cache

kernel thread per RAID set to do the io work

resynchronization

degraded mode logic

In normal operation (i.e. all disks of the RAID set are ok), the target queues incoming ios to an input queue and starts the kernel thread, which retrieves the ios and does the address calculation in order to lookup a stripe for the respective address. If a stripe for this address exists in the cache and is uptodate, the data is being copied from the cache to the io data area (i.e. the biovec) for reads and endio is being performed. Write data will get merged into the stripes chunks and the parity chunk gets calculated before queuing it to be written out to the sets disks which ends with endio being reported to the upper layers.
If the stripes data is not uptodate, a read operation is being queued and the above read/write copy/merge operations are carried out after the stripe got read in. No parity calculation is necessary on reads during normal operation. If all stripes of the cache are active (i.e. io is in-flight to or from the stripes chunks) and none fits the address of the io request, the io needs to wait for another thread cycle.

In degraded mode (i.e. one drive failed), no data will be read from or written to the failed drive any more. All data of the missing drive is being reconstructed based on the same block xor algorithm used for writes after a read so that any application will get the proper data returned. In case of a write, data is being merged from the biovecs into the chunks of the stripe as in normal operation with the exception that no write to the failed drive is being tried.

The dirty log is used indirectly through the region hash in order to request any regions which are subject to recovery. The region hash quiesces regions, which means that no application io is allowed to get to the region while resynchronization happens on it. In case a quiesced region is available on a regin hash inquiry, the per RAID set thread initializes a read to a special resynchronization stripe. Once that is done, it calculates parity and writes the data back to the region. Due to memory consumption reasons, this is done in multiple read/calculate/write cycles per region, because the region size is typically larger than the resynchronization stripe size. Once all recovery work has been finished, the recovery stripe is released from memory. This mechanism can be used to initialize a new set and to inititialize a new disk after a disk failure and the replacement of the respective drive as well.
The main RAID thread function which performs
- end ios on all bios with read/written stripes
- updating the region hash
- recovery
- fetching the io input queue
- handling new ios by relating them to stripes
- flushing any non-uptdat or dirty stripes
looks like:

static void do_raid(void *context)

{

struct raid_set *rs = context;

/*

* We always need to end io, so that ios

* can get errored in case the set failed

* and the region counters get decremented

* before we update the region hash states

*/

do_endios(rs);

/* Update region hash states before we go any further */

rh_update_states(rs->recover.rh);

/* Try to recover regions */

do_recovery(rs);

/* Quickly add all new ios queued to the work list */

spin_lock_irq(&rs->io.lock);

bio_list_merge_init(&rs->io.work, &rs->io.in);

spin_unlock_irq(&rs->io.lock);

/* Let's assume we're operational most of the time ;-) */

if (likely(raid_set_operational(rs))) {

do_ios(rs);

do_cache_flush(rs);

} else

/* No way to reconstruct data with too many devices failed */

bio_list_fail(rs, &rs->io.work, 0);

}

dm-raid45 mapping table examples

Mapping table for 6 disks using a persistent dirty log: dev/tst/r5_6disks_log

0 25165820 raid45 disk 2 /dev/tst/r5_6disks_log 8192 raid5_la 2 64 128 6 0 \
/dev/sdk 0 /dev/mapper/error 0 /dev/sdm 0 /dev/sdn 0 /dev/sdo 0 /dev/sdp 0

This mapping table defines:

one segment starting at 0, length ~12GB,

selects the dm-raid45 target with the keyword 'raid45'

selects the persistent dirtly log with the keyword 'disk'

hands 2 parameters to the dirty log (stored in /dev/tst/r5_6disks_log with region size 8192 sectors)

selects the left-asymmetric address calculation algorithm with the keyword 'raid5_la'

hands 2 parameters to the dm-raid45 constructor to select a chunk size of 64 sectors and 128 stripes allocated for the stripe cache

defines 6 disks with disk #0 (the first one on the list) to be the one to initialize; this is an example of drive #0 being a rerplacement for
a previously broken one

gives devnodes and offsets for all 6 disks

Mapping table for a 480GB 4 disk RAID5 array (transient 'core' dirty log, 2 parameters to the dirty log telling it to define 128MB region size and avoid synchronizationm select right-asymmetric addressing algorithm, '0' to select default chunk size and amount of stripes, 4 disks with the last on the list to be initialized):

0 960518976 raid45 core 2 262144 nosync raid5_ra 0 4 3 \
/dev/sdi 0 /dev/sdj 0 /dev/sdk 0 /dev/sdl 0

Of course the initialization is a noop even though #3 got selected, because we tell the dirtyl log via the 'nosync' option to set all regions to sync.
The above mapping table exaples can be created using a favorate text editor, as mentioned before and the RAID sets can be created by running
dmsetup create r5 r5_6disks
presumably the fist example got filed to 'r5_6disks'.

The dmraid utility supports this target, which is not yet in mainline, but a patch is available on my people page(see URLs below) for a couple of ATARAID flavours (i.e. isw and nvidia).

URLs

http://people.redhat.com/heinzm/sw/dm/dm-raid45
http://people.redhat.com/heinzm/dmraid

Michael Kleinhenz

2003-12-06T20:16:47