this one's more interesting, because lses are not independent of each other like
drive failures are! they are most likely to occur in groups, temporally and
spatially close to each other (see above for the approximate distribution).
thus, if we encounter one lse on a given drive, we have a decent chance of
having have more nearby. hence, we have to take the pmf into account when
determining how bad data corruption via lse is.
\begin{equation}
\label{1411fb31d54e13e11aea72b812891307}
\begin{split}
& P[k\ \text{drives develop the same LSE in}\ t] \\[0.7em]
& = P[\text{one drive develops an LSE in}\ t] \\
& \qquad \cdot \sum_{m = 1}^\infty P[m\ \text{LSEs}\ |\ 1\ \text{LSE}] \cdot P[\text{the rest share}\ \geq 1\ \text{of the}\ m], \\
\end{split}
\end{equation}
with, if lse events are also Poisson-like,
\begin{equation}
P[\text{one drive develops an LSE in}\ t] = 1 - \exp\left(-\text{LSE rate} \cdot t\right). \\
\end{equation}
that last probability in \eqref{1411fb31d54e13e11aea72b812891307}, \(P[\text{the
rest share}\ \geq 1\ \text{of the}\ m]\), is the tricky one. because those \(m\)
lses are clustered, if one of the other drives in the array has an lse in or
nearby those \(m\), it has an elevated chance of more nearby. so maybe we need
to multiply the probabilities together per bad sector, per given configuration
of bad sectors on the first drive, maybe with some \(E[\text{something}]\)
bullshit in here somewhere…
i claim that this is hard to think about.
the thing that stymied me for a while in this analysis was: i wanted to get an
estimate of the probability of a given lse configuration, so that i could
estimate the probability of all drives sharing a given lse, but i didn't have
that probability — all i had from the papers and my data was an estimate of
how likely an lse was given that there was another one nearby. in other words, i
had an estimate of \(P[\text{LSE at}\ s_1\ |\ \text{LSE at}\ s_2]\) for some
disk sectors \(s_1, s_2\), but what i really wanted was \(P[\text{LSEs at}\ S]\)
for some subset \(S\) of all possible disk sectors \(D\).
so: how do we get \(P[S], S \subset D\) from \(P[s], P[s_1 | s_2], \forall s, s_1, s_2 \in D\
\)?
…you can't. i spent a while trying to do this before realizing it had some
real similarity to the problem of reconstructing the full pdf of a random vector
from its elementwise expected value & autocorrelation, which i couldn't find a
way to do and suspect is not possible, as well as reconstruction of a
probability distribution from its moments alone, which is, well, the moment
problem… so i asked claude if this was feasible and it came up with a
counterexample for \(N = 3\) that shot to hell any hope i had of a strategy. in
short, you can't get \(P[S]\) from \(P[s]\) & \(P[s_1 | s_2]\) because it's
hopelessly underconstrained.
since there's massive uncertainty about even the quantities i would take as
givens for that problem, i figured my best bet was to come up with a
justifiable approach to the whole thing and run with it.
i decided i would figure that the empirical prior probability of lses in a given
sector would take the higher-order correlations into account enough for an
estimate, and treat the probability of additional bad sectors on other drives as
independent of each other. i think this should yield a conservative estimate, as
we effectively double-count a bunch of cases in which drives have more than one
lse in the range under consideration… but i'm not totally sure about this! it
passes the vibe check, i suppose. we'll rely on \(P[m\ \text{LSEs}\ |\ 1\
\text{LSE}]\) to do most of the probabalistic heavy lifting, and merely
construct something plausible for the rest of the expression.
i will also use a real useful bit of the earlier analysis: since most lses were
of the form "we drop one 4 KiB on-disk sector only," and btrfs blocks are 16 KiB
large, i can do the analysis with a sector granularity of 16 KiB and come much
closer to correct! a 16 KiB block is 32 × 512 B sectors, which (given the pmf
estimation for lses for my drives) gives a new lse pmf, based on blocks, as
follows:
| 16 KiB sector count |
probability |
| 1 |
81% |
| 2–3 |
15% |
| 4+ |
4% |
now the math. for each bad sector on the drive that had a failure, we want to
know the probability that, for at least one of those sectors, all the remaining
drives have also failed on that sector:
\begin{equation}
\begin{split}
& P[\text{the rest share}\ \geq 1\ \text{of the}\ m] \\
& = P[k - 1\ \text{drives share one of}\ m\ \text{LSEs}] \\
\end{split}
\end{equation}
or, in other words, the dual of the probability that every other drive saved at
least one of those sectors from corruption:
\begin{equation}
\begin{split}
& P[\text{the rest share}\ \geq 1\ \text{of the}\ m] \\
& = P[k - 1\ \text{drives share one of}\ m\ \text{LSEs}] \\
& = 1 - P[k - 1\ \text{drives share none of}\ m\ \text{LSEs}] \\
& \approx 1 - P[k - 1\ \text{drives do not share a given LSE}]^m \\
\end{split}
\end{equation}
the last deduction is only approximate, because lses on a given drive are not
independent of each other. however, since we increased the definition of
"sector" to a larger size and the analysis is prohibitively difficult if we take
this into account, we assume they are independent.
that last probability, of at least one drive being able to salvage a given lse,
we can calculate exactly:
\begin{equation}
\begin{split}
& P[k - 1\ \text{drives do not share a given LSE}] \\
& = 1 - P[k - 1\ \text{drives share a given LSE}] \\
& = 1 - P[\text{a given drive has a given LSE}]^{k - 1} \\
\end{split}
\end{equation}
the prior odds that you'll get an lse for a given sector, \(P[\text{a given
drive has a given LSE}]\), is worth looking into, because this is where things
like bitrot and regular scrubs come into play. intuitively, more regular
scrubbing should decrease this chance, because the drive will only have been
able to accumulate lses since the last scrub on the nas. except that lse rate
is empirically mostly constant with time and isn't really correlated with
workload, so as a first blush approximation, we could just say
\begin{equation}
\begin{split}
& \text{worst-case expected LSEs per sector} \\
& \qquad = \text{empirical LSE rate} \times \text{rebuild time} \times \frac{\text{sector size}}{\text{drive size}}. \\
\end{split}
\end{equation}
as for the manner in which lses occur: the distribution of error burst size is
roughly ~Pareto, but the rate at which bursts occur is an annoying
distribution… though, for our purposes, "is there an lse in this sector when
we go to read it" is kind of just a Bernoulli random variable measured when we
do a rebuild, so
\begin{equation}
\begin{split}
& P[\text{a given drive has a given LSE}] \\
& \approx \text{worst-case expected LSEs per sector} \\
\end{split}
\end{equation}