## Mailbox Answers: Calculating New Parity After an Overwrite

I recently did some work for Mr. Howard Marks, an independent analyst and founder of Deep Storage on the subject of data protection and data loss. He e-mailed me with a question regarding calculating the new parity for a stripe of data on a storage system.

Let us consider the case of a 10+1 RAID 5 set with a strip size of 64KB. When an application performs a 4KB write the system must:

- Read the 64KB strip that contains the 4KB to be overwritten into a memory buffer
- Modify the memory buffer with the data to be written
- Read however much other data as would be needed to recalculate the parity strip for this stripe
- Write the new data and new parity strip (Min 1 4KB write, 1 64KB write)
When we casually talk about this condition we say the RAID controller would need to read all 10 data strips in the stripe so it can XOR all ten together as part of step 4. I, however have been thinking about XOR and think that rather than requiring N+1 total I/Os I can get it down to three.

If P, the parity strip, already contains

D_1 \oplus D_2 \oplus D_3 \oplus D_4 \oplus D_5 \oplus D_6 \oplus D_7 \oplus D_8 \oplus D_9 \oplus D_{10}and we’re overwriting part of D_4 couldn’t I [do the following]:

- Read the existing D_4 into a variable D'_4.
- Modify the data into D_4.
- Calculate the changes as D_4\oplus D_{4}' into variable C
- Read the parity strip P
- Calculate new parity strip as P=P \oplus C

In short, the answer is yes. We’re going to prove that here, because I think this is a great exercise to really show off the power of XOR. We’ve explored the operation here and began our discussion of coding theory by looking at maximum likelihood decoding. Let’s take a brief review of the XOR (or mod 2) operation:

## XOR is just modulo 2 addition

Let’s call generic binary words D_{j}. That is, each D_{j} is simply a string of 1s and 0s of whatever length l we feel like setting. So a binary word D_{j} = d_{1}^{(j)}d_{2}^{(j)}\ldots d_{l}^{(j)} consists of binary **bits** given by the lowercase^{1} d_{i}. XOR operation works bit-by-bit, and will be denoted by \oplus:

For a quick numerical example, suppose D_{j} = 1011 and D_{k} = 0010. Then

D_{j} \oplus D_{k} = 1011 \oplus 0010 = (1\oplus 0)(0\oplus 0)(1\oplus 1)(1\oplus 0)Remember, too, that XOR is addition modulo 2, so we add the bits together, then divide by 2 and take the remainder. So, in particular, 1\oplus 1 = 0 because 1+1 leaves a remainder of 0 when divided by 2. So,

D_{j} \oplus D_{k} = 1001## Back to the question

Mr. Marks’ question can be stated mathematically in the following way (and I’m going to generalize it to any finite amount of words of any length XORed together, because that’s what mathematicians do):

Suppose P = D_{1} \oplus D_{2} \oplus \ldots \oplus D_{j} \oplus \ldots \oplus D_{K} for some K, and one word (say D_{j}) is modified to give D_{j}'. Let C be the binary word that represents the changes between D_{j} and D_{j}'. That is,

C = D_{j} \oplus D_{j}'(Note: XOR as an operation to identify differences in binary words is one of the more elegant features. If all the bits in two words are the same, then bitwise XORing would always give the binary word of all 0s. Only when two bits are different is their XOR result a 1.) Call P' the new XOR sum with D_{j}' substituted for D_{j}. So

P' := D_{1}\oplus D_{2}\oplus \ldots \oplus D_{j}'\oplus \ldots \oplus D_{K}.Then does P'= P \oplus C?

### Numerical example

Whenever I’m seeking to prove a statement, I always “play” with an example. Now, simply finding an example that fits the statement doesn’t constitute proof. But playing with explicit numbers can often yield a way to prove the statement in general. Plus, we can deepen our understanding by really “seeing the theorem in action,” as opposed to just manipulating symbols via logic.

Let’s just test this with a sum of 3 words to make our lives easier. Let D_{1} = 110, D_{2} = 010, and D_{3} = 101. Then

P = D_{1} \oplus D_{2} \oplus D_{3} = 110 \oplus 010 \oplus 101 = 001Now suppose we change D_{2} to D_{2}' = 101. First, the new sum P' is given by

P' = 110 \oplus 101 \oplus 101 = 110Now, the change in D_{2} and D_{2}' is given by

C = 010 \oplus 101 = 111Notice that all three positions changed. Each position that is different has a 1.Let’s see if P \oplus C = P' P \oplus C = 001 \oplus 111 = 110

Success! Now, this doesn’t mean we’re done. *One example doesn’t constitute proof.* We have to show this is true for *any* finite number of binary words of *any * length.

### Time to prove this statement is true

So, let D_{1},...,D_{K} be binary words of generic length l. Choose one word D_{j} and modify it to form the new word D_{j}'. Let C = D_{j} \oplus D_{j}' denote the change vector. Then

\begin{aligned}P^{\prime}&=D_{1}\oplus D_{2}\oplus\ldots D^{\prime}_{j}\oplus\ldots D_{K}\end{aligned}

Now, let’s note that C = D_{j}\oplus D^{\prime}_{j} tells us which positions changed between the two. Another way to look at it is that C is the word you need to XOR with D_{j} to get to the new D^{\prime}_{j}. That is, D^{\prime}_{j} = D_{j} \oplus C.^{2}. Now, let’s plug in the new expression for D_{j}' into P':

Now, we know from this post that XOR is a commutative operation. Coupled with the associative property^{3}, we can actually rearrange the order of the XORing to put C last.

(You’ve done this with regular arithmetic all the time. 5 + 1 + 6 + 3 can be rearranged and grouped into (6+3+1) + 5 = 10 +5 = 15. Commutativity and associativity combined allow this to happen with any operation.)

So,

\begin{aligned}P^{\prime}&=D_{1}\oplus D_{2}\oplus\ldots D^{\prime}_{j}\oplus\ldots D_{K}\\&=D_{1}\oplus D_{2}\oplus\ldots (D_{j} \oplus C)\oplus\ldots D_{K}\\&=(D_{1}\oplus D_{2}\oplus\ldots D_{j}\oplus\ldots D_{K})\oplus C\end{aligned}But wait, that last thing in parenthesis is exactly P. Therefore,

\begin{aligned}P^{\prime}&=D_{1}\oplus D_{2}\oplus\ldots D^{\prime}_{j}\oplus\ldots D_{K}\\&=D_{1}\oplus D_{2}\oplus\ldots (D_{j} \oplus C)\oplus\ldots D_{K}\\&=(D_{1}\oplus D_{2}\oplus\ldots D_{j}\oplus\ldots D_{K})\oplus C\\&= P \oplus C\end{aligned}Since we showed this for any generic number of binary words added together, and allowed to binary words to be any length, we’ve proven the statement.

## Bonus: Multiple modifications

What if we modified more than one word in our original sum P? It’s a pretty simple extension to run through the proof again with multiple modified words and show that if we have multiple C^{\prime}s, one for each modified word, we can perform the same substitution and show that the new P^{\prime} is simply the old P XORed with all of the change vectors. Alternatively, you could XOR all the change vectors first into one big change vector, then XOR that with your original P to compute the new P^{\prime}. If you want to verify it for yourself formally, simply follow the same steps we did above for one modified word. You’ll just be performing the same type of substitution multiple times to account for each modification.

## Conclusion

Mr. Marks brought this up because he was seeking a way to compute the new parity strip in a more efficient way (with fewer arithmetic steps) than simply following the definition. You can absolutely “brute force” your way to calculating the new parity strip. Companies and startups are always concerned about “scalability”. Sure, you won’t notice the time different between 10 extra things added together. But what about 10 million? 1 billion? More than that? None of those numbers are infeasible for the amount of calculations we perform on data now. In those cases, the brute force method of simply using the definition starts to cause performance problems. It was worth taking the time to “be clever” and search for a nice, elegant way that cuts down the number of operations necessary to calculate a new parity strip. It took a little upfront work, but the result speaks loudly for itself.

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.