Session 6.2 – RAID Systems

RAID Design Goals:

1. Fault Tolerance (Reliability)
   ┌─────────────────────────────────────────────────────────────┐
   │ • Survive disk failures without data loss                  │
   │ • Provide continuous operation during hardware failures     │
   │ • Enable hot-swapping of failed drives                     │
   │ • Support automatic reconstruction of data                  │
   └─────────────────────────────────────────────────────────────┘

2. Performance Improvement
   ┌─────────────────────────────────────────────────────────────┐
   │ • Increase read/write throughput through parallelism       │
   │ • Reduce access latency via load distribution              │
   │ • Scale bandwidth with number of drives                    │
   │ • Optimize for sequential and random access patterns       │
   └─────────────────────────────────────────────────────────────┘

3. Capacity Management
   ┌─────────────────────────────────────────────────────────────┐
   │ • Present multiple drives as single logical volume         │
   │ • Efficient space utilization based on RAID level          │
   │ • Support dynamic capacity expansion                       │
   │ • Balance between usable space and redundancy              │
   └─────────────────────────────────────────────────────────────┘

RAID Trade-off Triangle:
                Performance
                     △
                    /│\
                   / │ \
                  /  │  \
                 /   │   \
                /    │    \
               /     │     \
         Cost ───────┼─────── Reliability
                     │
                 Capacity

RAID 0 - Data Striping Algorithm:

Configuration: Minimum 2 disks, no redundancy
Capacity: Sum of all disk capacities
Fault Tolerance: None (any disk failure = total failure)

Algorithm RAID0_Write:
Input: data_block, stripe_size, num_disks
Output: disk_assignments[]

BEGIN
    stripe_number = block_address ÷ stripe_size
    disk_number = stripe_number MOD num_disks
    local_address = (stripe_number ÷ num_disks) × stripe_size + 
                   (block_address MOD stripe_size)
    
    write_to_disk(disk_number, local_address, data_block)
END

Data Distribution Example:
┌─────────┬─────────┬─────────┬─────────┐
│ Disk 0  │ Disk 1  │ Disk 2  │ Disk 3  │
├─────────┼─────────┼─────────┼─────────┤
│ Block A │ Block B │ Block C │ Block D │
│ Block E │ Block F │ Block G │ Block H │
│ Block I │ Block J │ Block K │ Block L │
└─────────┴─────────┴─────────┴─────────┘

Performance:
• Read Speed: N × Single Disk Speed
• Write Speed: N × Single Disk Speed
• I/O Operations: Parallel across all disks

RAID 1 - Data Mirroring Algorithm:

Configuration: Minimum 2 disks, exact copies
Capacity: 50% of total disk capacity
Fault Tolerance: Can survive failure of all but one disk

Algorithm RAID1_Write:
Input: data_block, mirror_set[]
Output: success/failure status

BEGIN
    write_success_count = 0
    
    FOR EACH disk in mirror_set DO
        IF disk is operational THEN
            result = write_to_disk(disk, block_address, data_block)
            IF result == SUCCESS THEN
                write_success_count++
            END IF
        END IF
    END FOR
    
    IF write_success_count > 0 THEN
        RETURN SUCCESS
    ELSE
        RETURN FAILURE
    END IF
END

Algorithm RAID1_Read:
BEGIN
    FOR EACH disk in mirror_set DO
        IF disk is operational THEN
            data = read_from_disk(disk, block_address)
            IF read is successful THEN
                RETURN data
            END IF
        END IF
    END FOR
    
    RETURN READ_error
END

RAID 5 - Parity Calculation Algorithm:

Configuration: Minimum 3 disks, distributed parity
Capacity: (N-1)/N of total capacity
Fault Tolerance: Can survive single disk failure

Algorithm RAID5_Calculate_Parity:
Input: data_blocks[], num_data_blocks
Output: parity_block

BEGIN
    parity_block = 0
    
    FOR i = 0 TO num_data_blocks-1 DO
        parity_block = parity_block XOR data_blocks[i]
    END FOR
    
    RETURN parity_block
END

Algorithm RAID5_Write_Stripe:
BEGIN
    stripe_number = block_address ÷ stripe_size
    parity_disk = stripe_number MOD num_disks
    
    // Distribute data blocks
    data_disk = 0
    FOR i = 0 TO num_disks-1 DO
        IF i != parity_disk THEN
            write_to_disk(i, local_address, data_blocks[data_disk])
            data_disk++
        END IF
    END FOR
    
    // Calculate and write parity
    parity = calculate_parity(data_blocks)
    write_to_disk(parity_disk, local_address, parity)
END

Parity Distribution Example (4 disks):
┌─────────┬─────────┬─────────┬─────────┐
│ Disk 0  │ Disk 1  │ Disk 2  │ Disk 3  │
├─────────┼─────────┼─────────┼─────────┤
│   A1    │   B1    │   C1    │  P1=    │
│         │         │         │A1⊕B1⊕C1 │
├─────────┼─────────┼─────────┼─────────┤
│   A2    │   B2    │  P2=    │   C2    │
│         │         │A2⊕B2⊕C2│         │
├─────────┼─────────┼─────────┼─────────┤
│   A3    │  P3=    │   B3    │   C3    │
│         │A3⊕B3⊕C3│         │         │
├─────────┼─────────┼─────────┼─────────┤
│  P4=    │   A4    │   B4    │   C4    │
│A4⊕B4⊕C4│         │         │         │
└─────────┴─────────┴─────────┴─────────┘

RAID 6 - Dual Parity Algorithm:

Configuration: Minimum 4 disks, dual parity
Capacity: (N-2)/N of total capacity  
Fault Tolerance: Can survive two simultaneous disk failures

Algorithm RAID6_Calculate_Dual_Parity:
Input: data_blocks[], num_data_blocks
Output: P_parity, Q_parity

BEGIN
    // P Parity (simple XOR)
    P_parity = 0
    FOR i = 0 TO num_data_blocks-1 DO
        P_parity = P_parity XOR data_blocks[i]
    END FOR
    
    // Q Parity (Reed-Solomon coding)
    Q_parity = 0
    FOR i = 0 TO num_data_blocks-1 DO
        Q_parity = Q_parity XOR (galois_multiply(data_blocks[i], 
                                 galois_power(2, i)))
    END FOR
    
    RETURN P_parity, Q_parity
END

Reed-Solomon Galois Field Operations:
┌─────────────────────────────────────────────────────────────┐
│ galois_multiply(a, b):                                      │
│   • Multiplication in GF(2^8) finite field                 │
│   • Uses irreducible polynomial x^8 + x^4 + x^3 + x^2 + 1  │
│   • Essential for Q parity calculations                     │
│                                                             │
│ galois_power(base, exponent):                               │
│   • Exponentiation in Galois field                         │
│   • Used to weight data blocks differently                  │
│   • Enables recovery from dual failures                     │
└─────────────────────────────────────────────────────────────┘

Dual Parity Distribution Example:
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│ Disk 0  │ Disk 1  │ Disk 2  │ Disk 3  │ Disk 4  │ Disk 5  │
├─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤
│   A1    │   B1    │   C1    │   D1    │  P1=    │  Q1=    │
│         │         │         │         │A⊕B⊕C⊕D  │RS(A,B,C,D)
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘

RAID 10 - Nested RAID Algorithm:

Configuration: Minimum 4 disks, striped mirrors
Capacity: 50% of total disk capacity
Fault Tolerance: Can survive multiple failures (not in same mirror)

Algorithm RAID10_Write:
Input: data_block, stripe_size, mirror_sets[]
Output: write_status

BEGIN
    // Step 1: Determine target mirror set (RAID 0 logic)
    stripe_number = block_address ÷ stripe_size
    mirror_set_index = stripe_number MOD num_mirror_sets
    target_mirror_set = mirror_sets[mirror_set_index]
    
    // Step 2: Write to both disks in mirror (RAID 1 logic)
    local_address = (stripe_number ÷ num_mirror_sets) × stripe_size +
                   (block_address MOD stripe_size)
    
    success_count = 0
    FOR EACH disk in target_mirror_set DO
        IF write_to_disk(disk, local_address, data_block) == SUCCESS THEN
            success_count++
        END IF
    END FOR
    
    IF success_count > 0 THEN
        RETURN SUCCESS
    ELSE
        RETURN FAILURE
    END IF
END

RAID 10 Structure:
   RAID 0 (Striping)
   ┌─────────┬─────────┐
   │Mirror 1 │Mirror 2 │
   ├─────────┼─────────┤
   │ Disk 0  │ Disk 2  │ ← RAID 1
   │ Disk 1  │ Disk 3  │ ← RAID 1
   └─────────┴─────────┘

Data Layout:
┌─────────┬─────────┬─────────┬─────────┐
│ Disk 0  │ Disk 1  │ Disk 2  │ Disk 3  │
│(Mirror A│ Mirror A│(Mirror B│ Mirror B│
├─────────┼─────────┼─────────┼─────────┤
│   A     │    A    │    B    │    B    │
│   C     │    C    │    D    │    D    │
│   E     │    E    │    F    │    F    │
└─────────┴─────────┴─────────┴─────────┘

RAID 5 Single Disk Recovery:

Algorithm RAID5_Recover_Failed_Disk:
Input: failed_disk_id, stripe_data[], surviving_disks[]
Output: recovered_data

BEGIN
    FOR EACH stripe in RAID_array DO
        recovered_block = 0
        
        // XOR all surviving data and parity blocks
        FOR EACH disk in surviving_disks DO
            IF disk contains data for this stripe THEN
                recovered_block = recovered_block XOR disk_data[stripe]
            END IF
        END FOR
        
        // Write recovered block to replacement disk
        write_to_replacement_disk(stripe, recovered_block)
    END FOR
END

RAID 6 Dual Disk Recovery (Reed-Solomon):

Algorithm RAID6_Recover_Two_Failed_Disks:
Input: failed_disk1, failed_disk2, surviving_data[], P_parity, Q_parity
Output: recovered_data1, recovered_data2

BEGIN
    FOR EACH stripe DO
        // Set up system of equations using Galois Field arithmetic
        // P = D0 ⊕ D1 ⊕ D2 ⊕ ... ⊕ Dn
        // Q = 1×D0 ⊕ 2×D1 ⊕ 4×D2 ⊕ ... ⊕ 2^n×Dn
        
        known_P = P_parity
        known_Q = Q_parity
        
        // Subtract known data from parity values
        FOR EACH surviving_disk DO
            known_P = known_P XOR surviving_data[disk]
            known_Q = known_Q XOR galois_multiply(surviving_data[disk], 
                                                  galois_power(2, disk_position))
        END FOR
        
        // Solve system using Galois Field operations
        coefficient_matrix = setup_galois_matrix(failed_disk1, failed_disk2)
        recovered_values = solve_galois_system(coefficient_matrix, 
                                              known_P, known_Q)
        
        recovered_data1 = recovered_values[0]
        recovered_data2 = recovered_values[1]
    END FOR
END

Recovery Time Estimation:
┌─────────────────────────────────────────────────────────────┐
│ Recovery_time = (Disk_capacity × Surviving_disks) /        │
│                 (Read_throughput × Network_bandwidth)        │
│                                                             │
│ Example: 1TB disk in 4-disk RAID 5                         │
│   - Read 3 × 1TB = 3TB of data                             │
│   - At 100MB/s throughput                                  │
│   - Recovery time ≈ 8.3 hours                              │
└─────────────────────────────────────────────────────────────┘

Linux RAID Management Commands:

1. Create RAID Arrays:
# RAID 0 (striping)
mdadm --create /dev/md0 --level=0 --raid-devices=2 /dev/sda1 /dev/sdb1

# RAID 1 (mirroring)
mdadm --create /dev/md1 --level=1 --raid-devices=2 /dev/sdc1 /dev/sdd1

# RAID 5 (striping with parity)
mdadm --create /dev/md2 --level=5 --raid-devices=4 \
  /dev/sde1 /dev/sdf1 /dev/sdg1 /dev/sdh1

# RAID 6 (striping with dual parity)  
mdadm --create /dev/md3 --level=6 --raid-devices=4 \
  /dev/sdi1 /dev/sdj1 /dev/sdk1 /dev/sdl1

# RAID 10 (mirrored stripes)
mdadm --create /dev/md4 --level=10 --raid-devices=4 \
  /dev/sdm1 /dev/sdn1 /dev/sdo1 /dev/sdp1

2. Monitor RAID Status:
# Check array status
cat /proc/mdstat

# Detailed information
mdadm --detail /dev/md0

# Monitor in real-time
watch cat /proc/mdstat

3. Handle Disk Failures:
# Mark disk as failed
mdadm --manage /dev/md0 --fail /dev/sda1

# Remove failed disk
mdadm --manage /dev/md0 --remove /dev/sda1

# Add replacement disk
mdadm --manage /dev/md0 --add /dev/sdx1

# Hot spare configuration
mdadm --manage /dev/md0 --add-spare /dev/sdy1

4. Performance Optimization:
# Set read-ahead value
blockdev --setra 8192 /dev/md0

# Configure stripe cache size
echo 16384 > /sys/block/md0/md/stripe_cache_size

# Set chunk size during creation
mdadm --create /dev/md0 --level=5 --chunk=64 --raid-devices=4 \
  /dev/sda1 /dev/sdb1 /dev/sdc1 /dev/sdd1

RAID Performance Tuning Guidelines:

1. Chunk/Strip Size Selection:
┌─────────────────────────────────────────────────────────────┐
│ Optimal_chunk_size = Average_I/O_size / Number_of_data_disks│
│                                                             │
│ Guidelines:                                                 │
│ • Small files (< 64KB): Use 32KB or 64KB chunks           │
│ • Large files (> 1MB): Use 128KB or 256KB chunks          │
│ • Database workloads: Match database page size             │
│ • Video streaming: Use large chunks (512KB+)               │
└─────────────────────────────────────────────────────────────┘

2. Read-ahead Buffer Optimization:
Algorithm Optimize_Readahead:
BEGIN
    IF workload is sequential THEN
        readahead_size = chunk_size × num_data_disks × 4
    ELSE IF workload is random THEN
        readahead_size = chunk_size
    ELSE
        readahead_size = chunk_size × num_data_disks × 2
    END IF
    
    set_readahead(raid_device, readahead_size)
END

3. Write Intent Bitmap:
# Enable write-intent bitmap for faster resync
mdadm --grow /dev/md0 --bitmap=internal

Benefits:
• Faster resync after unclean shutdown
• Only resync blocks that were being written
• Slight performance overhead during normal operation

4. RAID Level Selection Matrix:
┌─────────────────────┬──────────┬──────────┬──────────┐
│    Workload Type    │  RAID 0  │  RAID 5  │ RAID 10  │
├─────────────────────┼──────────┼──────────┼──────────┤
│ High Read/Write     │   Best   │   Good   │   Best   │
│ Random Small I/O    │   Good   │   Poor   │   Best   │
│ Sequential Large I/O│   Best   │   Good   │   Good   │
│ Database OLTP       │   Poor   │   Poor   │   Best   │
│ Data Warehouse      │   Best   │   Good   │   Good   │
│ File Server         │   Good   │   Best   │   Good   │
│ Backup Storage      │   Good   │   Best   │   Fair   │
└─────────────────────┴──────────┴──────────┴──────────┘

5. Hardware Considerations:
• Use identical disk models for best performance
• Ensure adequate power supply for all disks
• Use dedicated RAID controller with battery backup
• Implement proper disk cooling and ventilation
• Monitor disk health with SMART attributes