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.