Data Layout

Figure 2: Data Layout

The underlying storage is organized in RAID5 fashion as shown in figure 2. The storage consist of a set of columns which may be separate disks or partitions of a disk. The smallest column limits the size of the TSS device. Each column is divided into contiguous regions called stripe units. A stripe is comprised of one stripe unit from each column. If there are N columns the number of data stripe units is N-1 and one stripe unit is kept for parity. We define the polarity of the stripe as the index of the column that contains the parity information. The stripes on the actual storage devices are the physical stripes and they provide the backing store for the logical stripes which the TSS device exports to the upper layers.

The logical stripe to physical stripe mapping is maintained by a Maptable. Any logical stripe can be mapped to a -

1. Invalid stripe - The logical stripe is not backed by any physical stripe. At device creation time all stripes will be of this type.

2. RAID1 physical stripe - The logical stripe is mapped to two physical stripes. The two physical stripes must have different polarity otherwise the failure of one disk (other than the parity disk) makes the data irrecoverable. The parity stripe units in case of RAID1 are left unused; this leads to a wastage of space which is 1/N the fraction of RAID1 storage of the total storage capacity of the device. But this makes for a simpler design.

3. RAID5 stripe - The logical stripe needs only one physical stripe.

4. cRAID5 stripe - The physical stripe that backs a logical stripe is not a full stripe but a part of it. Hence the unit of allocation has to be at a sub stripe level.

   If a logical stripe is backed by a cRAID5 stripe the maptable gives the index into the compression table where information of the backing physical stripe is stored. The compression table gives the physical stripe that contains the backing store for the logical stripe, the actual size after compression, and the offset of the allocation unit in the physical stripe.

The free stripe information is stored in a bitmap format in bitmap table. As the cRAID5 physical stripe is smaller than a RAID5 physical stripe due to the use of compression, the bitmaps also should at the sub-stripe granularity. i.e., if the full physical stripe is allocated in terms of equal sub-parts (say, a maximum of 4) for the cRAID5 storage, then a bit in the bitmap table corresponds to 1/4$^{th}$ of a stripe.