Check out the new USENIX Web site. next up previous
Next: Optimizations to Enhance Performance Up: Implementation Previous: RAID5 I/O Handling

Implementation of Migration

Here we discuss only the ordered write strategy for migrations between RAID1 and RAID5 for ensuring reliable persistence semantics7. We are currently investigating policies for migrations to/from cRAID5, mostly in a prefetching/caching framework[#!bib:app-prefetch!#,#!bib:trace-pref!#].

In ordered write strategy, the updates are performed in a well defined order. We now explain this ordering of events and show how it does not result in wrong operation in the event of a crash.

Invalid to RAID5

1: The allocation bitmap is checked for a free physical stripe. If a free physical stripe is found, it is marked allocated and the entry of the bitmap is flushed to stable storage. The physical stripe is returned to the caller.

2: If no free physical stripes are left, a RAID1 stripe is victimized migrating it from RAID1 to RAID5 (this conversion itself involves multiple steps which are explained next), and one physical stripe is returned to the caller.

3: The maptable entry of the stripe is marked RAID5 and flushed to stable storage. The access is retried.

If the system fails between steps 1 and 3 or between 2 and 3, some storage may go unaccounted but does not result in any incorrect operation. This storage can be recovered online using the device-check program (see the section on application interface).

RAID1 to RAID5

1: An interlock is set on the stripe so that no one can access this stripe.

2: Full stripe data is read in, the parity is computed and the parity stripe unit of the physical stripe to be retained is updated.

3: The maptable entry of the stripe is marked RAID5 and flushed to stable storage. The physical stripe currently unused is returned to the caller.

Steps 1 and 2 do not change the structural state information of the system in any persistent way. If the system fails just after completing step 3 (marked RAID5, metadata flushed), one physical stripe goes unaccounted but cannot result in incorrect operation. The lost stripe can be recovered by running device-check.

RAID5 to RAID1

In the current implementation, a partial stripe write access to a RAID5 stripe triggers this migration. A more general scheme might wait till the stripe is accessed frequently enough and then attempt migration. To make transition from RAID5 to RAID1, a stripe requires a physical stripe whose polarity is different from the physical stripe currently used.

1: The allocation bitmap is searched for a free physical stripe whose polarity differs from the currently used physical stripe.

2: If the required physical stripe cannot be found in the free list, a RAID1 stripe is identified and victimized, migrating it to RAID5.

3: The full stripe data is read in and the physical stripe obtained from the victimization is updated with this data.

4: The maptable entry of the stripe is marked RAID1 and flushed to stable storage.

Steps 1 and 2 change the structural state information, but only one of them do it as step 2 is attempted only when step 1 fails. Step 3 does not change the structural information in any persistent way. If the system crashes before step 4, one physical stripe goes unaccounted which can be recovered by using device-check.


next up previous
Next: Optimizations to Enhance Performance Up: Implementation Previous: RAID5 I/O Handling
Dr K Gopinath
2000-04-25