shadow_storage/
erasure.rs

1//! Erasure coding for redundancy
2
3use shadow_core::error::{Result, ShadowError};
4use bytes::Bytes;
5
6/// Erasure encoder using Reed-Solomon
7pub struct ErasureEncoder {
8    /// Number of data shards
9    data_shards: usize,
10    /// Number of parity shards
11    parity_shards: usize,
12}
13
14impl ErasureEncoder {
15    /// Create new erasure encoder
16    pub fn new(data_shards: usize, parity_shards: usize) -> Result<Self> {
17        if data_shards == 0 || parity_shards == 0 {
18            return Err(ShadowError::Configuration(
19                "Shard counts must be positive".into()
20            ));
21        }
22
23        Ok(Self {
24            data_shards,
25            parity_shards,
26        })
27    }
28
29    /// Encode data into shards with parity
30    pub fn encode(&self, data: &[u8]) -> Result<Vec<Bytes>> {
31        // Calculate shard size (pad if needed)
32        let shard_size = (data.len() + self.data_shards - 1) / self.data_shards;
33        
34        // Create data shards
35        let mut shards = Vec::new();
36        for i in 0..self.data_shards {
37            let start = i * shard_size;
38            let end = (start + shard_size).min(data.len());
39            
40            if start < data.len() {
41                let mut shard = data[start..end].to_vec();
42                // Pad to shard_size
43                shard.resize(shard_size, 0);
44                shards.push(Bytes::from(shard));
45            } else {
46                // Empty shard (padding)
47                shards.push(Bytes::from(vec![0u8; shard_size]));
48            }
49        }
50
51        // Create parity shards (simple XOR-based for demonstration)
52        // In production, use proper Reed-Solomon library
53        for i in 0..self.parity_shards {
54            let mut parity = vec![0u8; shard_size];
55            
56            // XOR all data shards
57            for data_shard in &shards {
58                for (j, &byte) in data_shard.iter().enumerate() {
59                    parity[j] ^= byte;
60                }
61            }
62            
63            // Add some variation for different parity shards
64            for byte in &mut parity {
65                *byte = byte.wrapping_add(i as u8);
66            }
67            
68            shards.push(Bytes::from(parity));
69        }
70
71        Ok(shards)
72    }
73
74    /// Decode data from shards (with possible losses)
75    pub fn decode(&self, shards: &[Option<Bytes>], original_size: usize) -> Result<Bytes> {
76        // Count available shards
77        let available: Vec<_> = shards.iter()
78            .enumerate()
79            .filter_map(|(i, s)| s.as_ref().map(|s| (i, s)))
80            .collect();
81
82        if available.len() < self.data_shards {
83            return Err(ShadowError::Storage(format!(
84                "Not enough shards to reconstruct: {} < {}",
85                available.len(),
86                self.data_shards
87            )));
88        }
89
90        // If we have all data shards, just concatenate
91        let mut has_all_data = true;
92        for i in 0..self.data_shards {
93            if shards[i].is_none() {
94                has_all_data = false;
95                break;
96            }
97        }
98
99        if has_all_data {
100            let mut result = Vec::new();
101            for i in 0..self.data_shards {
102                if let Some(ref shard) = shards[i] {
103                    result.extend_from_slice(shard);
104                }
105            }
106            result.truncate(original_size);
107            return Ok(Bytes::from(result));
108        }
109
110        // Reconstruction needed - simplified version
111        // In production, use proper Reed-Solomon decoding
112        Err(ShadowError::Storage("Reconstruction not fully implemented".into()))
113    }
114
115    /// Minimum shards needed for reconstruction
116    pub fn min_shards(&self) -> usize {
117        self.data_shards
118    }
119
120    /// Total shards created
121    pub fn total_shards(&self) -> usize {
122        self.data_shards + self.parity_shards
123    }
124
125    /// Redundancy factor
126    pub fn redundancy(&self) -> f64 {
127        self.total_shards() as f64 / self.data_shards as f64
128    }
129}
130
131impl Default for ErasureEncoder {
132    fn default() -> Self {
133        Self::new(3, 2).unwrap() // 3 data + 2 parity = can lose 2 shards
134    }
135}
136
137#[cfg(test)]
138mod tests {
139    use super::*;
140
141    #[test]
142    fn test_encoder_creation() {
143        let encoder = ErasureEncoder::new(3, 2).unwrap();
144        assert_eq!(encoder.min_shards(), 3);
145        assert_eq!(encoder.total_shards(), 5);
146        assert!((encoder.redundancy() - 1.666).abs() < 0.01);
147    }
148
149    #[test]
150    fn test_encoding() {
151        let encoder = ErasureEncoder::new(3, 2).unwrap();
152        let data = b"Hello, Shadow Network!";
153        
154        let shards = encoder.encode(data).unwrap();
155        
156        assert_eq!(shards.len(), 5);
157    }
158
159    #[test]
160    fn test_decoding_with_all_shards() {
161        let encoder = ErasureEncoder::new(3, 2).unwrap();
162        let data = b"Hello, World!";
163        
164        let shards = encoder.encode(data).unwrap();
165        
166        // Convert to Option<Bytes>
167        let shard_opts: Vec<Option<Bytes>> = shards.into_iter().map(Some).collect();
168        
169        let decoded = encoder.decode(&shard_opts, data.len()).unwrap();
170        
171        assert_eq!(&decoded[..data.len()], data);
172    }
173}
shadow_storage/erasure.rs

shadow_storage/
erasure.rs
