The Math Citadel
Home
About Us People
Research Consulting Shop Patreon
Projects Papers/Articles Book Reviews Contact

Mailbox Answers: Calculating New Parity After An Overwrite

R. Traylor


This article is inspired by an e-mail question regarding parity for a data stripe on a storage system. It provides motivation for an elegant $\bmod 2$-based proposition and proof. 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:
  1. Read the 64KB strip that contains the 4KB to be overwritten into a memory buffer
  2. Modify the memory buffer with the data to be written
  3. Read however much other data as would be needed to recalculate the parity strip for this stripe
  4. 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]:
  1. Read the existing $D_4$ into a variable $D'_4$.
  2. Modify the data into $D_4$.
  3. Calculate the changes as $D_4\oplus D_{4}'$ into variable $C$
  4. Read the parity strip $P$
  5. 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[note]The "exponent" doesn't denote powers. It's telling us which word that bit belongs to. This way we can keep all the components of different words straight. It gives us a way to show how we XOR component-wise.[/note] $d_{i}$.XOR operation works bit-by-bit, and will be denoted by $\oplus$: $$\begin{aligned}D_{j} \oplus D_{k} &= (d_{1}^{(j)}d_{2}^{(j)}\ldots d_{l}^{(j)})\oplus d_{1}^{(k)}d_{2}^{(k)}\ldots d_{l}^{(k)}\\&= (d_{1}^{(j)} \oplus d_{1}^{(k)})(d_{2}^{(j)}\oplus d_{2}^{(k)})\ldots (d_{l}^{(j)}\oplus d_{l}^{(k)})\end{aligned}$$ 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. 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 = 001$$ Now suppose we change $D_{2}$ to $D_{2}' = 101$. First, the new sum $P'$ is given by $$P' = 110 \oplus 101 \oplus 101 = 110$$ Now, the change in $D_{2}$ and $D_{2}'$ is given by $$C = 010 \oplus 101 = 111$$ Notice 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! This doesn't mean we're done.One example doesn't constitute proof. We have to show this is true forany finite number of binary words ofany length.

Prove this statement is true

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}$$ 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$. This can actually be shown formally by noting that, in mod 2 arithmetic, each element is its own additive inverse. Thus, "subtracting" a binary word is the same thing as XORing that word on both sides. We now plug in the new expression for $D_{j}'$ into $P'$: $$\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}\end{aligned}$$ Now, we know from this post that XOR is a commutative operation. Coupled with the associative property ((a + b) + c = a + (b+c)), 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}$$ That last thing in parentheses 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.