BRICS - Bit Flip Resilience for In-Memory Column Stores

Coding Reliability

On these pages we provide our findings and results regarding code reliability. More contents will follow in the near future.

AN Coding

For AN coding, the choice of the code parameter $A$ is the most crucial part. As it turned out in our studies, for each data bit width each A behaves differently! Since in-memory database systems operate on each individual data width ranging from 1 to 32 bits, we had to compute the “goodness” of each A for all these bit widths.

For a given $A$ and data bit width $k$, we can compute the probability of silent data corruption (SDC) for a certain bit flip weight $b$. This means, how likely it is for a specific AN code (with given $k$ and $A$) that a $b$-bit flip results in another code word and is therefore not detectable.

For each combination of data bit width ($k$) and bit width of the parameter $A$ ($h$) we want a “best” $A$. We define “goodness” as giving a maximum lower bound of the detectable bit flip weight. In other words, it is those $A$ which generate AN codes of width $n=h+k$ with largest minimal Hamming distance. For each combination of $k$ and $h$, there is typically a set of candidate $A$s, from which the best $A$ needs to be selected. To select a single best $A$, you can define optimization functions and an optimality criterion. In our case, we define two optimization functions:

1. For a given data width $k$ and some $A$, this functions returns the lower bound of the detectable bit flip weight:
   $\eta(k,A) = \max b \quad, \varphi_x^{k,A}=0 \wedge 0 \leq x \leq b$
   This essentially defines the candidate set.
2. From that candidate set, we select that $A$ which has the lowest first non-zero probability of silent data corruption (SDC):
   $\psi(k,A) = \varphi_{b=\eta(k,A)+1}^{k,A}$

Using these target functions, we define our optimization problem:

It takes all (computed) $A$s of a given parameter bit width ($k$) and checks for the largest minimal detectable bit flip weight (the guarantee to detect all $1 \dots x$-bit flips, with maximum x among the available $A$s) and the smallest first non-zero SDC probability.

In the following four tables we list all of the golden $A$s determined through the above optimization problem. In small font and parantheses we also list for the given combination of $A$ and $k$ the minimal detectable bit flip weight.

Contributing and Feedback

GitHub / brics-db / coding_reliability

Please feel free to fork on github, send pull requests, and file issues in the issue tracker.

Disclosure

The SVG image for the link to the GitHub page is taken from GitHub.