RAID$(4+k)$ disk arrays with $N$ data and $k$ checks disks continue their
operation after a single disk failure without data loss by on-demand recovery
of requested data blocks but with degraded performance. Denoting disk
reliability as $R(t)=1-F(t)$, where $F(t)$ is the PDF of disk lifetime
reliability of RAID$(4+k),k\geq 1$ arrays with no repair is given as follows:

$\displaystyle
R_{RAID(4+k)}(t)=\sum_{i=0}^{k}\binom{N+k}{i}R^{N+k-i}(t)(1-R(t))^{i}.$ (42)

The Mean Time To Failure - MTTF of PC disks was crudely estimated based on
customer returns of broken disks to manufacturers Gibson 1992 [65] using
statistical methods for small samples in Lawless 2003 [128]. Notable studies
of storage failure are: Bairavasundaram et al. 2007 [13]: (1) there is a high
degree of temporal locality between successive LSEs. (2) the vast majority of
disks developed relatively few errors during first three years, but these few
errors cause significant data loss if not detected proactively by disk
scrubbing. Schroeder and Gibson 2007 [201], Pinheiro et al. 2007 [175], Jiang
et al. [111], DRAM faults Schroeder et al. 2009 [202], Latent Sector Errors -
LSE Schroeder et al. 1010 [203], NAND flash-based SSDs in Schroeder et al.
2017 [204], SSDs Maneas et al. 2021 [140].

While the two parameter Weiball distribution Trivedi 2001 [249] as utilized by
Elerath and Schindler 2014 [50], is a better fit for disk lifetimes. Due to
its mathematical tractability disk reliability was approximated a single
parameter negative exponential distribution by Gibson 1992 [65]:
$r(t)=e^{-\delta t}$, where $\delta$ is the disk failure rate. 223223223We are
using $\delta$, since we use $\lambda$ to denote the arrival rate in queueing
systems. The HDD Mean Time to Failure -
MTTF$=\int_{0}^{\infty}R(t)dt=1/\delta$ and the RAID5 Mean Time to Repair -
MTTR$=1/\mu$ are two key input parameters for RAID analysis.

RAID5 rebuild processing may be started after a brief delay to allow for fail-
slow faults 11.10 without human intervention provided a hot spare is
available. Data loss occurs if a second disk fails before rebuild is
completed, but a much more common cause of rebuild failures are Latent Sector
Errors - LSEs as discussed in Section 11.5.

RAID6 provides an extra check disk based Q whose blocks are computed using
Reed-Solomon coding Fujiwara 2006 [Fiji06] Note that RAID6 remains operational
in degraded mode with two failed disks.

RAID5 reliability analysis is given in Section 5.4.1 in Gibson 1992 [65],
which is repeated below.. 224224224Out of print and also not available as an
EECS Berkeley dissertation. A similar analysis in the context of mirrored
disks is given by Example 8.34 in Trivedi 2001 [249].

### Transient Analysis of CTMC for RAID5 Rebuild

The evolution of the system is modeled by a CTMC with three states ${\cal
S}_{i}$, where $i=0,1,2$ is the number of disks failed disks. We have the
following transitions:

${\cal S}_{0}\xrightarrow{(N+1)\delta}{\cal S}_{1},\hskip 14.22636pt{\cal
S}_{0}\xleftarrow{\mu}{\cal S}_{1},\hskip 14.22636pt{\cal
S}_{1}\xrightarrow{N\delta}{\cal S}_{2}.$

The system evolution is described by the following set of linear Ordinary
Differential Equations - ODEs:

$\frac{dP_{0}(t)}{dt}=-(N+1)\delta P_{0}(t)+\mu P_{1}(t),\hskip
5.69054pt\frac{dP_{1}(t)}{dt}=-(\delta+\mu)P_{1}(t)(N+1)\delta P_{0}(t),\hskip
5.69054pt\frac{dP_{2}(t)}{dt}=N\delta P_{1}(t).$

The LST $L^{*}(s)=\int_{0}^{\infty}P(t)e^{-st}dt$ for the ODEs are given by
Eq. (43)

$\displaystyle s{\cal L}^{*}_{0}(s)-P_{0}(0)$ $\displaystyle=-(N+1)\delta{\cal
L}^{*}_{0}(s)+\mu{\cal L}^{*}_{1}(s),\hskip 14.22636ptP_{0}(0)=1.$ (43)
$\displaystyle s{\cal L}^{*}_{1}(s)-P_{1})0)$
$\displaystyle=-(\delta+\mu){\cal L}^{*}_{1}(s)+(N+1){\cal L}^{*}_{0}(s)\hskip
14.22636ptP_{1}(0)=0.$ $\displaystyle s{\cal L}^{*}_{2}(s)-P_{2}(0)$
$\displaystyle=N\delta{\cal L}^{*}_{1}{s}\hskip 14.22636ptP_{2}(0)=0.$

Solving for ${\cal L}^{*}_{2}(s)$ leads to

$\displaystyle{\cal L}^{*}_{Y}(s)=s{\cal
L}^{*}_{2}(s)=\frac{2\delta^{2}}{s^{2}+((2N+1)\delta+\mu)s+2N\delta^{2}}=\frac{2\delta^{2}}{\zeta-\eta}\left(\frac{1}{s+\zeta}-\frac{1}{s+\eta}\right)$

The reliability is the sum of probabilities that the system is functional.

$R(t)=P_{0}(t)+P_{1}(t)=1-P_{2}(t)\mbox{ so that
}f_{Y}(t)=-\frac{dR(t)}{dt}=\frac{dP_{2}(t)}{dt}.$

$\displaystyle R_{RAID5}(t)=\frac{\zeta e^{\eta t}-\eta e^{\zeta
t}}{\zeta-\eta}\mbox{ where:
}\zeta,\eta=\frac{1}{2}[-(2N+1)\delta+\mu\pm\sqrt{\delta^{2}+\mu^{2}+2(2N+1)\delta\mu}].$
(44)

Given $R(t)$ the MTTDL can be obtained where we have substituted
$\delta^{-1}=\mbox{MTTF}$ and $\mu^{-1}=\mbox{MTTR}$ leads to:

$\displaystyle\mbox{MTTDL}_{\mbox{RAID5}}=\int_{t=0}^{\infty}R_{RAID5}(t)dt=\frac{(2N+1)\delta+\mu}{N(N+1)\delta^{2}}\approx\frac{\mu}{N(N+1)\delta^{2}}=\frac{MTTF^{2}}{N(N+1)\mbox{MTTR}}.$
(45)

A simple method to derive Eq. (45) is to multiply the number of times the
normal state: ${\cal S}_{0}$ and the degraded state: ${\cal S}_{1}$ are
visited, before there is a transition to the failed state: ${\cal S}_{2}$.
Given that the probability of an unsuccessful rebuild is
$p_{f}=N\delta/(N\delta+\mu)$, then the probability of $k$ successful rebuilds
and the mean number of successful is:

$p_{k}=p_{f}(1-p_{f})^{k-1},k\geq 1\mbox{ with mean
}\bar{k}=1/p_{f}=1+\mu/(N\delta)\approx\frac{MTTDL}{N\times MTTR}.$

$\mbox{MTTDL}_{RAID5}$ is obtained by multiplying $\bar{k}$ by the sum of
holding times in ${\cal S}_{0}$ and ${\cal S}_{1}$.

Chen et al. 1994 [31] provide the MTTDL for RAID5 and RAID6 with $N$ disks in
total and parity group size $G$:

$\displaystyle\mbox{MTTDL}_{\mbox{RAID5}}\approx\frac{\mbox{MTTF}^{2}}{N(G-1)\mbox{MTTR}},\hskip
14.22636pt\mbox{MTTDL}_{\mbox{RAID6}}\approx\frac{\mbox{MTTF}^{3}}{N(G-1)(G-2)\mbox{MTTR}^{2}}.$
(46)

Generalizing the formula and with one parity group ($N=G$) we have:

$\displaystyle\mbox{MTTDL}_{\mbox{RAID}(4+k)}\approx\frac{\mbox{MTTF}^{k+1}}{N(N-1)\ldots(N-k+1)\mbox{MTTR}^{k}}$
(47)

Chen’s formula assumes that the repair rate remains fixed regardless of the
number of failed disks and one disk is repaired at a time. With two failed
disks in RAID6 corresponding strips in both disks are reconstructed together.

Given $N$ disks and with $i\leq k$ failed disks we have the transitions:

${\cal S}_{N-i}\rightarrow{\cal S}_{N-(i+1)}:\hskip 5.69054pt(N-i)\delta\hskip
14.22636pt{\cal S}_{N-(i+1)}\leftarrow{\cal S}_{N-i}:\hskip 5.69054pt\mu$

A repair rate proportional to the number of disks is postulated in Angus 1988
[10]. and furthermore the number of failed disks is allowed to exceed $n-k$.

${\cal S}_{N-i}\rightarrow{\cal S}_{N-(i+1)}:\hskip 5.69054pt(N-i)\delta\hskip
14.22636pt{\cal S}_{N-(i+1)}\leftarrow{\cal S}_{N-i}:\hskip 5.69054pti\mu$

Angus’ MTTDL formula is as follows:

$\displaystyle
MTTDL_{Angus}=\frac{\mbox{MTTF}^{n-k+1}}{k\binom{n}{k}\mbox{MTTR}^{n-k}}\times\sum_{i=0}^{n-k}\binom{n}{i}(\frac{MTTR}{MTTF})^{i}\approx\frac{\mbox{MTTF}}{k\binom{n}{k}}(\frac{\mbox{MTTF}}{\mbox{MTTR}})^{n-k}.$
(48)

It can be observed from Table 20 obtained by simulation in Resch and Volvivski
2013 [189] that Chen’s formula overestimates MTTDL by a factor
$\approx(n-k)!$.

$n$ | $k$ | MTTF | Simul | Chen | S/C | Angus | S/C
---|---|---|---|---|---|---|---
10 | 10 | 2000 | 1.988E2 | 2.000E2 | 0.994 | 1.988E2 | 0.994
10 | 9 | 2000 | 4.488E4 | 4.444E4 | 1.010 | 4.467E4 | 1.005
10 | 8 | 1500 | 9.446E6 | 4.688E6 | 2.105 | 9.438E6 | 1.001
10 | 7 | 500 | 7.786E7 | 1.240E7 | 6.278 | 7.591E7 | 1.026
10 | 6 | 200 | 6.407E7 | 2.511E6 | 25.513 | 6.441E7 | 0.995
Table 20: Validation of Chen and Angus MTTDL formulas versus simulation.
MTTR=1 hour and small values of MTTF are used for simulation efficiency.

A RAID5 system is considered operational with no or one disk failures, but the
two states differ substantially performance-wise, e.g., the maximum read
bandwidth is halved when a disk fails. In the case of readonly workload $i<k$
disk failures results in an $(i+1)$-fold reduction in throughput.

Performability combines reliability and performance, see Trivedi 2001 [249].
In the context of disk arrays it may be defined as the number of I/Os after
first failure to the time of data loss occurs. Performability of four RAID1
variants in Section 14 is obtained in Thomasian and Xu 2008 [234].

In reliability modeling RAID5 can be substituted by a single component.

$\displaystyle R_{\mbox{RAID5}}^{appr}=e^{-t/\mbox{MTTDL}}$ (49)

where MTTDL is given by Eq. (45).

RAID designs in the context of a 70 disk strawman array is presented in Gibson
1992 [65] and Gibson and Patterson 1993 [66]. Assuming that there are
$G_{string}$s with $\mbox{MTTF}_{string}$ taking into account component
unreliabilities the overall failure rate is given as:

$\frac{1}{MTTDL_{RAID}}=\frac{G(N+1)(N=2)MTTR_{disk}}{MTTF^{2}_{disk}}+\frac{G_{string}}{MTTF_{string}}$

### Crosshatch Disk Array

The crosshatch disk array is proposed in Ng 1994 [157]. It takes into account
supporting hardware such as a controller or cable failures. The array consists
of 7+P RAID5s placed as an array of $N\times N=64$ disks. Faults causing data
loss for the following configuration are as follows.

1\. Single path horizontal:

(1) double disk failure, (2) single disk and single controller failure, (3)
double controller failure, MTTDL=$2.32\times 10^{6}$

2\. Dual path vertical array:

Disks connected to two vertical buses each with own controller constitute a
RAID5. (1) double disk failures, (2) double disk failures. MTTDL=$8.72\times
10^{7}$.

3\. Dual path horizontal:

(1) double disk failure, (2) single disk failure plus double controller
failures, (3) quadruple controller failures. MTTDL=$2.32\times 10^{7}$

4\. Dual path horizontal:

Same as 2 except disks in rows constitute a RAID5. (1) double disk failures,
(2) single disk failure plus double controller failure, (3) quadruple
controller failure. $\mbox{MTTD}L=8.72\times 10^{7}$ hours

5\. Crosshatch diagonal:

(1) double disk failures, (2) single disk failure plus double controller
failure, (3) quadruple controller failure. $\mbox{MTTDL}=8.90\times 10^{7}$
hours.

The analysis is approximate and perhaps the reason that there is a small
difference in MTTDLs. The simulation method used in Section 3.2 could be used
for this purpose.

###  11.2 System Reliability Metrics

The MTTDL metric has been proven useful for comparing reliability schemes and
for estimating the effect of the various parameters on system dependability.

It is argued in Elerath and Schindler 2014 [50] that the MTTDL derived using
CTMC models provides unrealistically high reliability estimates. This is
refuted by Iliadis and Venkatesan 2015 [100] by showing that MTTDL equations
that account for latent sector errors and scrubbing operations yield
satisfactory results.

The Expected Annual Fraction of Data Loss - EAFDL metric in conjunction with
the MTTDL metric, for various redundancy schemes and for the Weiball and Gamma
real-world distributions, see e.g., Trivedi 2001 [249], is presented by the
refuting authors.

It is shown that the declustered placement scheme offers superior reliability
in terms of both metrics. The parameters used in the study are summarized in
Table 21.

Parameter | Definition
---|---
$n$ | number of storage devices
$c$ | amount of data stored on each devise
$r$ | replication factor
$k$ | spread factor of data placement scheme
$b$ | reserved rebuild bandwidth per device
$1/\lambda$ | mean time to failure of a storage device
$U$ |  amount of user data stored in the system ($U=nc/r$)
$1/\mu$ |  time to read $c$ bytes at rate $b$ ($1/\mu=c/b$)
Table 21: Systems parameters with derived parameters below the line.

At any point the system is either in normal or rebuild mode. Deferring rebuild
has its advantages, since some disk failures are due to transient server
failures and are resolved by restarting servers. Following a first-device
failure, rebuild operations and subsequent device failures may occur, which
eventually lead the system either to Data Loss - DL with probability $P_{DL}$
or back to the original normal mode by restoring all replicas with probability
$1-P_{DL}$. Typically, rebuild time is negligible compared to the time between
failures: $E[T]=1/(n\delta)$. Given that the expected number of first-device
failures until data loss occurs is $1/P_{DL}$. It follows:

$\displaystyle MTTDL\approx\frac{E(T)}{P_{DL}}$ (50)

Let $H$ denote the amount in data loss when data loss occurs and $U$ the
amount of stored user data. EAFDL is then the normalized data lost per MTTDL:

$\displaystyle EAFDL=\frac{E[H]}{MTTDL\cdot U}$ (51)

Define $Q$ as follows: $Q=H$ if DL and $Q=0$ if no DL. Given $E(Q)$ we can
determine EAFDL as follows:

$\displaystyle E(Q)=P_{DL}\cdot E(H),\mbox{ hence: }EAFDL=\frac{E(Q)}{E(T)U}$
(52)

###  11.3 Clustered versus Declustered Data Placements

To justify the EAFDL measure consider clustered and declustered data
placements. In Clustered Placement - CP the $k$ blocks on a device are
replicated in another device, while in Declustered Placement - DP the $k$
blocks are distributed over $k$ blocks as shown in Fig. 18.

$\begin{array}[]{|c|c|c|c|c|c|}\hline\cr
D_{1}&D_{2}&D_{3}&D_{4}&D_{5}&D_{6}\\\ \hline\cr A&A&K&K&\cdot&\cdot\\\
B&B&L&L&\cdot&\cdot\\\ C&C&\cdot&\cdot&\cdot&\cdot\\\
D&D&\cdot&\cdot&\cdot&\cdot\\\ E&E&\cdot&\cdot&\cdot&\cdot\\\
F&F&\cdot&\cdot&\cdot&\cdot\\\ G&G&\cdot&\cdot&\cdot&\cdot\\\
I&I&\cdot&\cdot&\cdot&\cdot\\\ J&J&\cdot&\cdot&\cdot&\cdot\\\
\hline\cr\end{array}\hskip 14.22636pt\begin{array}[]{|c|c|c|c|c|c|}\hline\cr
D_{1}&D_{2}&D_{3}&D_{4}&D_{5}&D_{6}\\\ \hline\cr A&A&B&C&D&E\\\ B&F&G&H&I&J\\\
C&K&K&L&\cdot&\cdot\\\ D&D&\cdot&\cdot&\cdot&\cdot\\\
E&E&\cdot&\cdot&\cdot&\cdot\\\ F&F&\cdot&\cdot&\cdot&\cdot\\\
G&G&\cdot&\cdot&\cdot&\cdot\\\ I&I&\cdot&\cdot&\cdot&\cdot\\\
J&J&\cdot&\cdot&\cdot&\cdot\\\ \hline\cr\end{array}$
Figure 18: Clustered (left) and declustered (right) data placement with six
devices with degree of replication $r=2$.

In both cases two node failures will lead to data loss, but two node failures
with DP result in a lower volume of data loss than CP.

Symmetric placement schemes lies between the clustered and declustered
schemes. For each node in the system the redundancy spread factor $k$ denotes
the number of nodes over which the data on that node and its corresponding
redundant data are spread. In a symmetric placement scheme, the $r-1$ replicas
of the data on each node are equally spread across $k-1$ other nodes, the
$r-2$ replicas of the data shared by any two nodes are equally spread across
$k-2$ other nodes, and so on. The system is effectively divided into $n/k$
disjoint groups of $k$ nodes. Each group contains an amount of $U/k$ user data
along with all of the corresponding replicas that are placed in its $k$ nodes
in a declustered manner. Clustered and declustered placement schemes are
special cases of symmetric placement schemes with in which $k=r$ and $k=n$,
respectively.

Expressions for MTTDL and EAFDL derived in Iliadis and Venkatesan 2014 [99]
are as follows:

$MTTDL\approx\begin{cases}(\frac{b}{\delta c})^{r-1}\frac{1}{n\delta}&\mbox{
for CP}\\\ (\frac{b}{2\delta
c})^{r-1}\frac{(r-1)!}{n\delta}\prod_{e=1}^{r-2}(\frac{n-e}{r-e})^{r-e-1}&\mbox{
for DP}\end{cases}\hskip 14.22636ptEAFDL\approx\begin{cases}(\frac{\delta
c}{b})^{r-1}\lambda&\mbox{ for CP}\\\ (\frac{2\delta
c}{b})^{r-1}\frac{\delta}{(r-1)!}\prod_{e=1}^{r-1}(\frac{r-e}{n-e})^{r-e}&\mbox{
for DP}\end{cases}$

In an intelligent rebuild process, the system attempts to first recover the
codewords of the user data that have the least number of codeword symbols left
or most exposed codewords. In blind rebuild lost codeword symbols are being
recovered in any order. i.e., not specifically aimed at recovering the
codewords with the least number of surviving symbols first.

It is demonstrated that lazy rebuild result in an order of magnitude
reliability degradation Iliadis 2022 [106]. The degradation of MTTDL due to
sector errors is observed in cases that apply lazy rebuild, and those that do
not. By contrast there is no degradation for the EAFDL. It is also shown that
the declustered data placement scheme offers superior reliability.

The adverse effect of LSEs on the MTTDL and the EAFDL reliability metrics as
closed-form expressions for the metrics in Iliadis 2023 [107] The MTTDL and
EAFDL are obtained analytically for (i) the entire range of BERs; (ii) the
symmetric, clustered, and declustered data placement schemes; and (iii)
arbitrary device failure and rebuild time distributions under network rebuild
bandwidth constraints.

For realistic values of sector error rates the MTTDL degrades, while EAFDL
remains practically unaffected. In the range of typical sector error rates and
powerful erasure codes, EAFDL degrades as well. It is also shown that the
declustered data placement scheme offers superior reliability. The actual
probability of data loss in the case of correlated symbol errors is smaller
than that obtained assuming independent symbol errors and of the same order of
magnitude.

###  11.4 RAID5/6 Reliability Analysis With Unrecoverable Sector Errors

Based on the discussion in Dholakia et al. 2008 [45] we extend the previous
discussion to include the effect of unrecoverable sector failures in addition
to disk failures on MTTDL. We consider a CTMC for RAID5 with two states
representing the number of failed disks and DF and UF states representing data
loss due to a disk failure (DF) and an unrecoverable sector failure (UF).

${\cal S}_{0}\rightarrow{\cal S}_{1}:\hskip 5.69054ptN\delta\hskip
8.53581pt{\cal S}_{1}\rightarrow{\cal S}_{UF}:\hskip
5.69054pt\mu_{1}P_{uf}^{(1)}\hskip 8.53581pt{\cal S}_{1}\rightarrow{\cal
S}_{DF}:\hskip 5.69054pt(N-1)\delta\hskip 8.53581pt{\cal S}_{1}\leftarrow{\cal
S}_{0}:\hskip 5.69054pt\mu_{1}(1-P_{uf}^{(1)}$

$P_{uf}^{k},k=1,2$ are given by Eq. (54) for RAID5 and RAID6 arrays. The state
transition matrix for RAID5 is given as follows.

${\bf Q}=\begin{pmatrix}-N\delta&N\delta&0&0\\\
\mu(1-P_{uf}^{(1)}&-\mu-(N-1)\delta&(N-1)\delta&\mu P_{uf}^{(1)}\\\ 0&0&0&0\\\
0&0&0&0\\\ \end{pmatrix}$

Since there are no transitions from the DF and UF states, the submatrix ${\bf
Q}_{T}$ representing states ${\cal S}_{0}$ and ${\cal S}_{1}$ is:

${\bf Q}_{T}=\begin{pmatrix}-N]\delta&N\delta&0&0\\\
\mu(1-P_{uf}^{(1)}&-\mu&-(N-1)\delta&\mu P_{uf}^{(1)}\\\ \end{pmatrix}$

The vector of the average time spent in the transient states before the CTMC
enters either one of the absorbing states DF and UF is obtained in Trivedi
2001 [249] by solving the following linear equations:

$\tau{\bf Q}_{T}={\bf P}_{T}(0)\mbox{ where }\tau-[\tau_{0},\tau_{1}]\mbox{
and }{\bf P}_{T}(0)=[1,0.0]$ $\tau_{0}=\frac{(N-1)\delta+\mu}{N(N-1)\delta+\mu
P_{uf}^{(1)}}\hskip 14.22636pt\tau_{1}=\frac{1}{(N-1)\delta+\mu P_{uf}^{(1)}}$

$\displaystyle\mbox{MTTDL}_{RAID5}=\tau_{0}+\tau_{1}=\frac{(2N-1)\delta+\mu}{N\delta[(N-1)\delta+\mu
P_{uf}^{(1)}]}.$ (53)

Numerical results for typical parameters have shown that RAID5 plus IDR
attains the same MTTDL as RAID6. While IDR incurs longer transfers, this
overhead is negligible compared to the extra disk access to update Q blocks
required by RAID6 with respect to RAID5.

In the case of RAID6 the probability $P_{recf}$ that a given segment of the
failed disk cannot be reconstructed is upper-bounded by the probability that
two or more of the corresponding segments residing in the remaining disks are
in error. As segments residing in different disks are independent, the upper
bound to $P_{recf}$ is given by:

$P^{UB}_{recf}=\sum_{j=2}^{N-1}\binom{N-1}{j}P_{seg}^{j}(1-P_{seg}^{N-1-j}\approx\binom{N-1}{2}P^{2}_{seg}.$

Given $N_{d}$ segments per disk drive their reconstruction is independent of
the reconstruction of the other disk segments. The probability that an
unrecoverable failure occurs, because the rebuild of the failed disk cannot be
completed is given by:

$P_{uf}^{r}=1-(1-p^{UB}_{recf})^{N}_{d}$

It is assumed that rebuild time in the degraded and critical mode are
exponentially distributed with rate $\mu_{1}$ and $\mu_{2}$.

Let ${\cal S}_{i},i=0,1,2$ denote the operating states of RAID6 with $i$
failed disks, ${calS}_{DF}$ and ${\cal S}_{UF}$ failed states due to disk
failure and unreadable sectors. We have the following transitions due to
failures and repairs.

${\cal S}_{0}\rightarrow{\cal S}_{1}:\hskip 5.69054ptN\delta\hskip
8.53581pt{\cal S}_{1}\rightarrow{\cal S}_{2}:\hskip 5.69054pt(N-1)\delta\hskip
8.53581pt{\cal S}_{1}\rightarrow{\cal S}_{UF}:\hskip
5.69054pt\mu_{1}p_{uf}^{(2)}\hskip 8.53581pt{\cal S}_{2}\rightarrow{\cal
S}_{DF}:\hskip 5.69054pt(N-2)\delta\hskip 8.53581pt{\cal
S}_{2}\rightarrow{\cal S}_{UF}:\hskip 5.69054pt\mu_{2}P_{uf}^{(2)}$ ${\cal
S}_{1}\leftarrow{\cal S}_{0}:\hskip 5.69054pt\mu_{1}(1-P_{uf}^{r})\hskip
8.53581pt{\cal S}_{2}\leftarrow{\cal S}_{0}:\hskip
5.69054pt\mu_{2}(1-P_{uf}^{(2)}).$

Similarly to RAID5 we have the following submatrix ${\bf Q}_{T}$ for states
(0,1,2): The rebuild rates with one and two disk failures are $\mu_{1}$ and
$\mu_{2}$ In fact two failed disks in RAID6 are rebuild concurrently.

$\tau{\bf Q}_{T}={\bf P}_{T}(0)\mbox{ with }{\bf P}_{T}(0)=[1,0.0]$ ${\bf
Q}_{T}=\begin{pmatrix}-N\delta&N\delta&0\\\
\mu_{1}(1-P_{uf}^{(r)})&-(N-1)\delta&-\mu(N-1)\delta\\\
\mu_{2}(1-P_{uf}^{(2)})&0&-(N-2)\delta-\mu_{2}\\\ \end{pmatrix}$

$\tau_{0}=\frac{[(N-1)\delta+\mu_{1}][(N-1)\delta+\mu_{2}]}{N\delta V},\hskip
8.53581pt\tau_{1}=\frac{(N-2)\delta+\mu_{2}}{V},\hskip
8.53581pt\tau_{2}=\frac{N-1)\delta}{V}$

$V=[(N-1)\delta+\mu
P_{uf}^{(r)}][(N-2)\delta+\mu_{2}P_{uf}^{(r)}]+\mu_{1}\mu_{2}P_{uf}^{(r)}(1-P_{uf}^{(2)})$

$MTTDL_{RAID6}=\tau_{0}+\tau_{1}+\tau_{2}$

###  11.5 Disk Scrubbing and IntraDisk Redundancy to Deal with LSEs

The main cause of rebuild failures are LSEs rather than whole disk failures.
Intra-Disk Redundancy - IDR in Dholakia et al. 2008 [45] and disk scrubbing
are two less costly methods to deal with LSEs, rather than RAID6. The
probability of uncorrectable disk failures ($P_{uf}$) due to segment errors is
used in [45] to extend RAID5 reliability analysis in Section 11.1 to take into
account LSEs.

IDR divides strips or SUs into segments with $n$ data and $m$ checks sectors
per segment, so that there are $\ell=n+m$ sectors per segment. There are $S$
bits per sector and the probability that a bit is in error is $P_{bit}$. Given
that the probability of an uncorrectable sector error is $P_{s}$ the
probability that a segment is in error when no coding is applied ($m=0$) is
$P_{seg}$

$P_{S}=1-(1-P_{bit})^{S},\hskip 14.22636ptP_{seg}^{none}=1-(1-P_{S})^{\ell}.$

A single parity sector can be used to correct a single sector in error, since
the sector in error is identified with a Cyclic Redundancy Check - CRC.
225225225https://en.wikipedia.org/wiki/Cyclic_redundancy_check

There are $n_{d}=C_{d}/(\ell S)$ segments on a disk with capacity $C_{d}$. The
probability of an uncorrectable failure for a RAID$(4+k)$ with $k$ failed
disks, so that it in critical mode:

$\displaystyle P_{uf}^{(k)}=1-(1-P_{seg})^{\frac{(N-k)C_{d}}{\ell S}}$ (54)

Note that the exponent denotes the number of disk segments in critical rebuild
mode.

Two categories of sector errors are considered: independent and correlated. In
the case of independent errors there is a probability $P_{s}$ that a sector
has an Unrecoverable Failure - UF. Correlated errors have an average burst
length $\bar{B}$ and there are $\bar{I}$ successive error-free sectors. Both
are modeled with a geometric distribution:

$a_{j}=P[I=j]=\alpha(1-\alpha)\alpha^{j-1},\mbox{ hence }\bar{I}=1/\alpha$

We also have $P[B=j]=b_{j}$ and $\bar{B}=\sum_{j\geq 1}jb_{j}$. Utilized in
further discussions is the following parameter.

$G_{n}\overset{\Delta}{=}P[\mbox{burst\\_length}\geq n]=\sum_{j\geq n}b_{j}$

The independent model is a special case of correlated model where:

$b_{j}=(1-P_{s})P_{s}^{j-1}\mbox{ and }\bar{B}=1/(1-P_{s})$

The probability $P_{s}$ that an arbitrary sector has an unrecoverable error
is:

$P_{S}=\frac{\bar{B}}{\bar{B}+\bar{I}}\mbox{ it follows
}\alpha=\frac{P_{s}}{\bar{B}(1-P_{s})}\approx\frac{P_{s}}{\bar{B}}\mbox{ hence
}P_{s}\leq\frac{\bar{B}}{\bar{B}+1}$

For independent errors:

$\displaystyle P{seg}^{none}=1-(1-P_{s})^{\ell}\approx\ell P_{s},\hskip
14.22636ptP_{seg}^{none}\approx(1+\frac{\ell-1}{\bar{B}})P_{s}$ (55)

and for bursty errors

$\displaystyle
P_{seg}^{none}=1-(1-P_{s})(1-\frac{1}{\bar{B}})\approx(1+\frac{\ell-1}{\bar{B}})P_{s}$
(56)

The probability that a segment is in error can be specified with the summation
below, but only one term need to be considered for small $P_{s}$ and the
correlated model:

$P_{seg}=\sum_{i\geq 1}c_{i}P_{s}^{i}\hskip
14.22636ptP_{seg}=c_{1}P_{s}+O(P_{s}^{2})$

###  11.6 Schemes to Implement IntraDisk Redundancy - IDR

Three IDR methods are proposed and evaluated in Dholakia et al. 2008 [45].

#### Reed-Solomon Check

The RS - Reed-Solomon code is discussed in Fujiwara 2006 [62]. With RS coding
an error occurs when over $m$ bits among $\ell=n+m$ bits are in error.

$\displaystyle
P_{seg}^{RS}=\sum_{j=m+1}^{e}llP_{s}^{j}(1-P_{s})^{\ell-j}\approx\binom{\ell}{m+1}P_{s}^{m+1}.$
(57)

In the case of a correlated model for small values of $P_{s}$.

$\displaystyle
P_{seg}^{RS}\approx\left[1+\frac{1}{\bar{B}}\left((\ell-m-1)G_{m+1}-\sum_{j=1}^{m}G_{j}\right)\right]P_{s}.$
(58)

This is the best that can be done since for a code with $m$ parity symbols for
a codeword of $n$ symbols any $m$ erasures can be corrected, but RS codes are
computationally expensive.

$\displaystyle
P_{seg}^{RS}=\sum_{j=m+1}^{\ell}\binom{\ell}{j}P_{s}^{j}(1-P_{s})^{\ell-j}\approx\binom{\ell}{m+1}P_{s}^{m+1}.$
(59)

In the case of correlated model for small values of $P_{s}$ results in
Appendix B of the paper yield:

$\displaystyle
P_{seg}^{RS}\approx\left[1+\frac{(\ell-m-1)G_{m+1}-\sum_{j=1}^{m}G_{j}}{\bar{B}}\right]P_{s}.\mbox{where
}\bar{B}=\sum_{j=1}^{\infty}G_{j},\hskip 5.69054ptb_{j}=G_{j}-G_{j-1}.$ (60)

#### Single Parity Check - SPC

This is the simplest coding scheme in which a single parity sector is computed
by XORing $\ell-1$ data sectors to form a segment with $\ell$ sectors. The
independent model yields:

$\displaystyle
P_{seg}^{SPC}=\sum_{j=2}^{\ell}\binom{\ell}{j}P_{s}^{j}(1-P_{s})^{\ell-j}\approx\frac{\ell(\ell-1)}{2}P_{s}^{2}$
(61)

In the case of correlated model for small values of $P_{s}$.

$\displaystyle
P_{seg}^{SPC}\approx\left[1+\frac{1}{\bar{B}}\left((\ell-2)G_{2}-1\right)\right]P_{s}.$
(62)

#### Interleaved Parity Check - IPC

In this scheme $\ell-m$ contiguous sectors are placed in a rectangle with $m$
columns. The XOR of the sectors in a column is the parity sector which is
placed in an additional row. This scheme with $\ell/m$ sectors per interleave
can correct a single error per interleave, but a segment is in error if there
is at least one interleave with two uncorrectable segment errors.

An IPC scheme with $m$ ($m\leq\ell/2$) interleaves per segment, i.e., $\ell/m$
sectors per interleave, has the capability of correcting a single error per
interleave. Consequently, a segment is in error if there is at least one
interleave in which there are at least two unrecoverable sector errors. Note
that this scheme can correct a single burst of $m$ consecutive errors
occurring in a segment. However, unlike the RS scheme, it in general does not
have the capability of correcting any $m$ sector errors in a segment. The
probability of an interleave error is:

$P_{interleave\\_error}=\sum_{j=2}^{\ell/m}\binom{\ell/m}{j}P_{s}^{j}(1-P_{s})^{\ell/m-j}\approx\frac{\ell(\ell-m)}{2m^{2}}P_{s}^{2}$

$\displaystyle
P_{seg}^{IPC}=1-(1-P_{interleave\\_error})^{m}\approx\frac{\ell(\ell-m)}{2m}P_{s}^{2}$
(63)

In the case of correlated model:

$\displaystyle
P_{seg}^{IPC}\approx\left[1+\frac{1}{\bar{B}}\left((\ell-m-1)G_{m+1}-\sum_{j=1}^{m}G_{j}\right)\right]P_{s}.$
(64)

It follows $P_{seg}^{RS}\approx P_{seg}^{IPC}$, but IPC is preferable since it
is easier to implement.

###  11.7 Effect of IDR on Disk Performance

The main focus in Dholakia et al. 2008 [45] is to study the effect of IDR on
RAID5 and RAID6 reliability, but performance is also investigated using
simulation and IO Equivalents - IOEs Hafner et al. 2004 [77].

$\displaystyle IOE(k)=1+\frac{\mbox{time to transfer 4 KB}}{\mbox{average time
per 4 KB}}=1+\frac{\mbox{4 KB/1024}}{\mbox{Avg. media transfer rate in
MB/sec}}\times\mbox{Avg IO/sec.}$ (65)

Table 22: Results for IOE. | 10K RPM | 15K RPM | Units
---|---|---|---
IOs/sec. | 250 | 333 | IO/sec.
Avg. media transfer rate | 53.25 | 62 | MB/sec.
IOE for k KB | $1+k/55$ | $1+k/48$ | IOE

The $IOE(k)\approx 1+k/50$ was used in the study.

When a single-sector A is written using the IPC scheme, for example, it is
written by a single I/O request also containing the corresponding intra-disk
parity sector PA. The average length of an I/O request is minimized when the
intra-disk parity sectors are placed in the middle of the segment. The
analysis in Section 8.2 of the paper determines the increase in IOE as 8.5%
for small and 3.6% for long writes.

The following parameters were used by the simulator: $1/\delta$=500K hours,
disk capacity $S=300$ GB, $P_{bit}=10^{-14}$, number of disks $N=8/16$ for
RAID5/6, rebuild time $1/\mu=17.8$ hours, sector size $S=512$ bytes (4KB
sectors became prevalent in 2010), $\ell=128$ sectors, $m=8$ interleaves.

Both random number driven and trace-driven simulations results are reported.
Other scheduling policies besides FCFS such as SSTF, Look, C-Look are tried
and shown to have a small effect on the relative performance due to IDR. Look
is a variation of SCAN that reverses if there are no additional requests in
the direction of the SCAN and C-look scans in one direction only Thomasian
2011 [236].

### Numerical Results

A SATA drive with a capacity $C_{d}=300$ GB, $P_{bit}=10^{-14}$ is considered,
so that 512 B sectors and $P_{s}=4096\times P_{bit}=4.096\times 10^{-11}$. The
segment length was set to $\ell=128$ sectors with $m=8$ interleaving, burst
length distribution with at most 16 sector and $\bar{B}=1.0291$

$\underline{b}=[0.9812,0.016,0.0013(2),0.0003(2),0.00020.0001(2),0,0.0001,0,0.0001(2),0,0.0001(2)]$

$P_{seg}$ and $P_{uf}$ with this parameter are given below.

Errors | Independent | Correlated
---|---|---
None | $5.2\times 10^{-9}$ | $5\times 10^{-9}$
RS | $6.2\times 10^{-81}$ | $2.5\times 10^{-12}$
SPC | $1.3\times 10^{-17}$ | $8.5\times 10^{-14}$
IPC | $1.6\times 10^{-18}$ | $9.5\times 2.5\times 10^{-12}$
Table 23: Approximate $P_{seg}$ for two error models.

Scheme | Independent | Correlated
---|---|---
None | $1.5\times 10*{-1}$ | $1.5\times 10^{-1}$
RS | $2\times 10^{-73}$ | $7.9\times 10^{-5}$
SPC | $4.3\times 10^{-10}$ | $3.1\times 10^{-3}$
IPC | $6.1\times 10^{-11}$ | $7.95\times 10^{-5}$
Table 24: Approximate $P_{uf}$ for RAID5 with $N=8$.

###  11.8 Comparison of Disk Scrubbing and IDR with IPC

Closed-form expressions are derived for operation with random, uniformly
distributed I/O requests, for the probability of encountering unrecoverable
sector errors, the percentage of unrecoverable sector errors that disk
scrubbing detects and corrects, the throughput and the minimum scrubbing
period achievable Illiadis et al. [98].

The probability of an error due to a write is $P_{w}$ and writes constitute a
fraction $r_{w}$ of disk accesses with rate $h$. The probability of error in
reading a sector without scrubbing is $P_{e}=r_{w}P_{w}$. The probability of
sector failure for deterministic scrubbing and random (exponentially
distributed) scrubbing period are:

$P_{s}^{(det)}=[1-(1-e^{-hT_{s}})/(hT_{S})]P_{e},\hskip
14.22636ptP_{s}^{exp)}=[hT_{S}/(1+hT_{S})]P_{e},$

where $T_{S}$ denotes the mean scrub period. Given that $hT_{s}\ll 1$ we have
the following approximations for deterministic and exponential scrubbing:

$P_{s}^{(det)}\approx P_{e}hT_{s},\hskip
14.22636ptP_{s}^{(exp)}\approx\frac{1}{2}P_{s}P_{e}hT_{s}$

Random scrubbing has double the value for $P_{s}$, hence deterministic
scrubbing is preferable.

For heavy-write workloads and for typical scrubbing frequencies and loads, the
reliability improvement due to disk scrubbing does not reach the level
achieved by the IPC-based IDR scheme, which is load insensitive. Note that
IPC-based IDR for SATA drives achieves the same reliability as that of a
system with no sector errors, with a small (about 6%) increase in capacity.

The penalty of disk scrubbing on I/O performance can be significant, whereas
that of the IPC-based IDR scheme is minimal, some disk space overhead.

Given IOE(k) in Eq. (65) the maximum rate of read/write operations to the disk
is:

$\hat{\sigma}_{max}=[IOE(K)t_{seek}]^{-1}.$

Given a small write scenario with $k$ sectors per chunk, $S_{D}$ sectors per
disk, with $G_{S}$ sectors scrubbed a time, and $p=1$ for RAID5 and $p=2$ for
RAID6

$\displaystyle\sigma\leq\sigma_{max}(k,T_{S})=\frac{\hat{\sigma}_{max}(k,T_{S})}{1+(1+2p)r_{w}]}$
(66)

The scrubbing $T_{S}$ period should not be smaller than a critical value
$T^{*}_{S}$ given below:

$\displaystyle T_{S}\geq
T_{S}^{*}=\frac{S_{D}IOE(G_{S})}{[1+(1+2p)r_{w})]G_{S}IOE(k)[\sigma_{max}(k)-\sigma]}$
(67)

Fig. 6 in Iliadis et al. 2011 [98] shows that in the area of practical
interest the reliability offered by scrubbing is inferior to that achieved by
the IDR scheme. That IDR is preferable to disk scrubbing contradicts that of
Schroeder et al. 2010 [203], on the other hand IDR does not seem to be
implemented while scrubbing is common practice.

###  11.9 Combining Scrubbing with SMART and Machine Learning

Self-Monitoring And Reporting Technology - SMART technology has been applied
to predict HDD failures Hughes et al. 2002 [95], Eckart et al. 2008 [49].
226226226https://en.wikipedia.org/wiki/Self-
Monitoring,_Analysis_and_Reporting_Technology Once a disk is determined to be
failing its contents are copied onto a spare with possibly occasional assist
from erasure coding to restore unreadable sectors. A disk detected to be
failing by simply copying it, which is referred to as smart rebuild.
227227227https://community.ibm.com/community/user/storage/blogs/brian-
kraemer1/2021/06/11/ds8000-smart-rebuild

SMART monitors 30 disk Attributes corresponding to different measures of
performance and reliability.
228228228https://www.linuxjournal.com/article/6983 Attributes have a one-byte
normalized value ranging from 1 to 253, e.g., SMART 187 is the number of read
errors that could not be recovered using hardware ECC. If one or more of the
Attribute values less than or equal to its corresponding threshold, then
either the disk is expected to fail in less than 24 hours or it has exceeded
its design or usage lifetime. 229229229https://www.backblaze.com/blog/hard-
drive-smart-stats/

Western Digital Network Attached Storage - NAS HDDs are automatically given a
warning label after being powered on for three years by Synology’s DiskStation
Manager -DSM. Western Digital Device Analytics - WDDA and Seagate’s IronWolf
are similar offerings.
230230230https://arstechnica.com/gadgets/2023/06/clearly-predatory-western-
digital-sparks-panic-anger-for-age-shaming-hdds/

HPE’s Nimble predictive storage makes 86% of problems disappear. A 6-nines
(99.9999%) availability is guaranteed over the installed base and 54% of
problems resolved are determined to be outside storage.
231231231https://m.softchoice.com/web/newsite/documents/partners/hpe/Nimble-
Six-Nine-White-Paper.pdf Nimble’s InfoSight applies data science to identify,
predict, and prevent problems across infrastructure layers.
232232232https://en.wikipedia.org/wiki/Data_science

Machine Learning - ML methods is used by Murray et al. 2005 [153] to predict
HDD failures by monitoring internally the attributes of individual drives. An
algorithm based on the multiple-instance learning framework and the naive
Bayesian classifier (mi-NB) are specifically designed for the low false-alarm
case. Other considered methods are Support Vector Machines - SVMs,
233233233https://en.wikipedia.org/wiki/Support_vector_machine unsupervised
clustering, 234234234https://www.section.io/engineering-education/clustering-
in-unsupervised-ml/ and non-parametric statistical tests (rank-sum and reverse
arrangements). 235235235https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4754273/
The failure-prediction performance of these methods is considerably better
than the threshold method currently implemented in drives, while maintaining
low false alarm rates.

Goldszmidt 2012 [67] characterizes and evaluates Disk Failure Advance
Detector- D-FAD of Soon-To-Fail - STF disks. The input to D-FAD is a single
signal from every disk, a time series containing in each sample the Average
Maximum Latency - AML and the output is an alarm according to a combination of
statistical models. The parameters in these models are automatically trained
from a population of healthy and failed disks ML techniques. Results from an
Hidden Markov Model - HMM
236236236https://en.wikipedia.org/wiki/Hidden_Markov_model and a threshold
(peak counter) were fused using logistic regression to sound alarms.
237237237https://en.wikipedia.org/wiki/Logistic_regression When applied to
1190 production disks D-FAD predicted 15 out of 17 failed disks (88.2%
detection rate), with 30 false alarms (2.56% false positive rate).

Amvrosiadis et al. 2012 [7] state that the goal of a scrubber is to minimize
the time between the occurrence of an LSE and its detection/correction or Mean
Latent Error Time - MLET, since during this time the system is exposed to the
risk of data loss. In addition to reducing the MLET, a scrubber must ensure to
not significantly affect the performance of foreground workloads.

Staggered scrubbing provides a lower MLET exploiting the fact that LSEs occur
in temporal and spatial bursts. Rather than sequentially reading the disk from
beginning to end staggered scrubbing quickly probes different regions of a
drive hoping to achieve quicker detection of error bursts son that they are
scrubbed immediately. Staggered scrubbing potentially reduces scrub throughput
used by foreground workloads. Larger request sizes lead to more efficient use
of the disk, but also have the potential of bigger impact on foreground
traffic.

EMC’s RAIDShield characterizes, monitors, and proactively protects against
disk failures eliminating 88% of triple disk failures in RAID6, which
constituted 80% of all RAID failures Ma et al. 2015 [137]. The method uses
joint failure probability to quantify and predict vulnerability to failure.
Simulation shows that most vulnerable RAID6 systems can improve the coverage
to 98% of triple errors.

The use of ML to make storage systems more reliable by detecting sector errors
in HDDs and SSDs is explored by Mahdisoltani et al. 2017 [138] Exploration of
a widerange of ML techniques shows that sector errors can be predicted ahead
of time with high accuracy. Possible use cases for improving storage system
reliability through the use of sector error predictors is provided. The mean
time to detecting errors can be greatly reduced by adapting the speed of a
scrubber based on error predictions.

A scrub unleveling technique that enforces a lower rate scrubbing to healthy
disks and a higher rate scrubbing to disks subject to LSEs is proposed by
Jiang et al. 2019 [112]. A voting-based method ensures prediction accuracy.
Experimental results demonstrate that the proposed approach achieves a lower
scrubbing cost together with higher data reliability than traditional fixed-
rate scrubbing methods on read-world datasets. Compared with the state-of-the-
art method the same level of Mean-Time-To-Detection - MTTD. with almost 32%
less scrubbing is achieved.

The first experimental comparison of sequential versus staggered scrubbing in
production systems determined that staggered scrubbing implemented with the
right parameters can achieve the same (or better) scrub throughput as a
sequential scrubber, without penalizing foreground applications. A detailed
statistical analysis of I/O traces is used to define policies for deciding
when to issue scrub requests, while keeping foreground request slowdown at a
user-defined threshold. The simplest approach, based on idle waiting and using
a fixed scrub request size outperforms more complex statistical approaches.

Scrubbing schemes to deal with LSEs have several limitations according to
Zhang et al. 2020 [268]. (1) schemes use ML to predict LSEs, but only a single
snapshot of training data for prediction; ignoring sequential dependencies
between different statuses of a HDD over time. (2) accelerating scrubbing at a
fixed rate based on the results of a binary classification model results in
unnecessary increases in scrubbing cost; (3) naively accelerating scrubbing
over full disks neglects partial high-risk areas; (4) they do not employ
strategies to scrub these high-risk areas in advance based on I/O accesses
patterns, in order to further increase the efficiency of scrubbing.

Tier-Scrubbing - TS scheme combines a Long Short-Term Memory - LSTM based
238238238https://en.wikipedia.org/wiki/Long_short-term_memory Adaptive
Scrubbing Rate Controller - ASRC, module focuses on sector error locality to
locate high-risk disk areas and a piggyback scrubbing strategy to improve the
reliability of a storage system. Realistic datasets and workloads evaluated
from two data centers demonstrate that TS can simultaneously decreases Mean-
Time-To-Detection - MTTD by about 80% and scrubbing cost by 20%, compared to a
state-of-the-art scrubbing scheme.

Disk fault detection models based on SMART data with ML algorithms require a
large amount of disk data to train the models, but the small amount of
training data in traditional ML algorithms greatly increases the risks of
overfitting, which weaken the performance of the model and seriously affect
the reliability.

A novel Small-Sample Disk Fault Detection optimizing method, with synthetic
data using Generative Adversarial Networks - GANs [68] is proposed in Wang
2022 [252]. The approach generates failed disk data conforming to the failed
disk data distribution. Disk SMART attributes vary with the usage and are
time-related; LSTM is adopted since it is good at learning the characteristics
of time series data as the GAN generator to fit the distribution of SMART
data, and use the multi-layer neural network as the discriminator to train the
GAN-model to generate realistic failed disk data. With sufficient generated
failed disk data samples, ML algorithms can detect disk faults more precisely
than before with the small original failed disk data samples.

###  11.10 Fail-Slow Faults in Drives and Their Detection

A major study of fail-slow or gray failures based on reports of such incidents
from twelve large-scale clusters are summarized in Table 25 from Gunawi et al.
2018 [75].

Root | SSD | Disk | Mem | Net | CPU | Total | Perm | Trans. | Partial | Tr. stop.
---|---|---|---|---|---|---|---|---|---|---
ERR | 10 | 8 | 9 | 10 | 3 | 40 | 19 | 8 | 7 | 6
FW | 6 | 3 | 0 | 9 | 2 | 20 | 11 | 3 | 1 | 4
TEMP | 1 | 3 | 0 | 2 | 5 | 11 | 6 | 2 | 1 | 2
PWR | 1 | 0 | 1 | 0 | 6 | 8 | 3 | 2 | 1 | 2
ENV | 3 | 5 | 2 | 4 | 4 | 18 | 11 | 3 | 3 | 1
CONF | 1 | 1 | 0 | 2 | 3 | 7 | 6 | 1 | 0 | 0
UNK | 0 | 3 | 1 | 2 | 2 | 8 | 5 | 1 | 0 | 2
Total | 22 | 23 | 13 | 29 | 25 | 112 | - | - | - | -
Table 25: Root causes of fail-slow problems across hardware types. Fail-slow
symptoms across root causes are given in four rightmost columns of as
Permanent, Transient slowdown, Partial slowdown, Transient stoppage.
Abbreviations: FW=FirmWare, CONF=configuration, UNK=UNKnown.

Perseus developed at Alibaba deals with Fail-Slow Detection - FSD of
components functioning with degraded performance Lu et al. 2023 [134]. Within
a ten month period 304 slow cases were found among 248K drives. Design goals
for Perseus are: (1) non-intrusive, (2) fine-grained, (3) accurate, (4)
general, both SSD and HHD based block, object, and file/database storage.

Four methodologies are used: 1\. Threshold filtering. Setting up a threshold
on drive latency to identify slow drives based on Service Level Objectives -
SLO. To account for legitimate temporary events such as Garbage Collection -
GC in SSDs a minimum slowdown is also specified. As shown in Fig. 4 and stated
in the paper the method has low accuracy. The spikes in the figure are
ascribed to increased throughput rather than slowdown. 2\. Peer Evaluation.
Drives on the same node receive equal loads due to load balancing. The median
delay over normal drives which constitute the majority is used to determine
abnormal drives, i.e., those that are twice slower for more than half the
time. 3\. IASO-based model. IASO is a fail-slow detection and mitigation
framework for distributed storage services Panda et al. 2019 [165]. The
accuracy, as defined below, was only 0.48.

Perseus was developed since these attempts were either too labor-intensive or
ineffective. The following questions are raised: Q1: Reads or writes. Read
requests, which are satisfied with the response from one replica are used in
the study. Q2: Modeling workload pressure. Spearman’s Rank Correlation
Coefficient 239239239https://en.wikipedia.org/wiki/Spearman shows that
throughput (bytes per second) is a better metric than IOPS. Q3: Selecting
adaptive thresholds. Given service-, cluster-, and node-wise latency (L)
versus throughput (T) (LvT) node-wise was selected. Regression models are used
to define a statistically normal drive and use its upper latency bound as the
adaptive threshold. Q4: Fail slow identification criterion. Instead of a
binary result a likelihood is expressed.

Perseus applies polynomial regression on the node-level LvT distribution to
automatically derive an adaptive threshold. A scoreboard mechanism to single
out the drives with severe fail-slow failures. The five entries of the time-
series dataset are: (avg_latency, avg_throughput, drive_ID, node_UID,
timestamp).

Perseus worklflow has the following steps: 1\. Outlier detection. Collect
entries at each node and use Principal Component Analysis - PCA, to transform
a large set of variables into a smaller set with those with small variance
removed. 240240240https://en.wikipedia.org/wiki/Principal_component_analysis
Outliers are discarded using the DBSCAN density-based clustering algorithm
Ester et al. 96 [51]. 2\. Building polynomial regression model. The prediction
upperbound is a fail-slow detection threshold, which is then applied to the
raw dataset to identify out-of-bound entries and mark them as slow. 3\.
Identifying fail-slow events. Use is made of a sliding window and a Slowdown
Ratio - SR defined as drive latency by the upper bound entry, to identify
consecutive slow entries and formulate corresponding fail-slow events. 4\.
Evaluating risk. A risk-score mechanism estimates the duration and degree of
fail-slow events and assigns each drive a risk score based on daily fail-slow
events. 241241241https://en.wikipedia.org/wiki/Risk_score Cases are
investigated based on severity. Perseus risk levels based on daily slowdown
events specified as SRs are given in Table 26.

Slowness | Long-term, | Moderate | Temporal
---|---|---|---
(minutes) | $\geq 120$ | [60,120) | [30,60)
Severe (SR $\geq$ 5) | Extreme | High | Moderate
Moderate (SR $\in$ [2,5)) | High | Moderate | Low
Mild (SR $\in$[1,2)) | Moderate | Low | Minor
Table 26: Perseus risk levels based on SR.

##  12 Appendix III: RAID Reliability Simulation

12.1 Simulation studies of RAID performance.
12.2 Simulation study of a digital archive.
12.3 Simulation of hierarchical RAID reliability.
12.4 Proteus open-source simulator.
12.5 CQSIM_R Tool Developed at AT&T.
12.6 SIMedc simulator for erasure coded data centers.

###  12.1 Simulation Studies of RAID Performance

The Parallel Data Laboratory- PDL founded by G. Gibson at CMU initially solely
concentrated on storage research. RAIDframe was developed to assist in the
implementation and evaluation of new RAID architectures by rapid prototyping
disk arrays Courtright et al. 1997 [38]. DiskSim with its origin at Univ. of
Michigan was further developed at PDL by G. Ganger.
242242242https://www.pdl.cmu.edu/DiskSim/index.shtml DiskSim relies on
extracted disk drive parameters by DIXTRAC.
https://www.pdl.cmu.edu/Dixtrac/index.shtml which provides disk specifications
until 2007. 243243243https://www.pdl.cmu.edu/DiskSim/diskspecs.shtml

The Pantheon simulator was developed at HP Labs by J. Wilkes et al. 1995
[255], which was used in several projects, most notably AutoRAID discussed in
Section 14.2 In evaluating the performance of IDR in Section 11.7 IBM
researchers developed their own simulator rather than relying on DiskSim or
Pantheon.

Disk and RAID simulators were developed at NJIT’s Integrated Systems Lab
(2000-07) by the author and his students.

####  12.1.1 Disk Scheduling Policies

There have been numerous applications of simulation in evaluating the
performance of disk scheduling policies. Disk access time can be reduced by
disk scheduling by processing pending I/O requests out-of-order, i.e., non-
FCFS scheduling, such as Shortest Seek Time First - SSTF and SCAN Denning 1967
[44] and Shortest Access Time First - SATF Jacobson and Wilkes 1991 [109].
Disk scheduling policies are compared via simulation in Worthington, Ganger,
and Yale 1994 [258], Hsu and Smith 2005 [88].

Thomasian and Liu [224] extended SATF with lookahead and priorities. An
empirical equation for SATF mean disk service versus queue-length ($q$) is
given in Thomasian 2011 [236].

$\bar{x}_{SATF}(q)=\bar{x}_{FCFS}/q^{p}\mbox{ where }p\approx 1/5$

i.e., disk service time is halved for $q=32$. Increase in throughput versus
$q$ is given in Table 2 in Anderson et al. 2003 [8] Complete Fairness Queueing
- CFQ provides fair allocation of the disk I/O bandwidth for all the processes
which request an I/O operation.
244244244https://www.kernel.org/doc/Documentation/block/cfq-iosched.txt Disk
scheduling mainly based on Thomasian 11 [236] is discussed in Section 3.3 in
Thomasian 2021 [245].

There have been several studies to reorganize data on disk to improve access
times, which are reviewed in Hsu et al. 2005 [89] Automatic Locality Improving
Storage - ALIS scheme based on analyzing common sequences of disk requests is
proposed and evaluated in this work.

Hsu and Smith 2004 [88] is a comprehensive study using server and PC workloads
to analyze the performance impact of I/O optimization techniques, i.e., read
caching, sequential prefetching, opportunistic prefetching, write buffering,
request scheduling, striping, and short-stroking. Disk technology improvement
in the form of faster seeks, higher RPM, linear density improvement, and
increase in track density is analyzed. A methodology is developed for
replaying real workloads that accurately models I/O arrivals Techniques that
reduce the number of physical I/Os are investigated. Sequential prefetching
and write buffering are particularly effective, reducing the average read and
write response time by about 50% and 90%, respectively. Larger caches up to
and even beyond 1% of the storage are shown to improve performance. Disk
technology improvement at the historical rate increases performance by about
8% per year if the disk occupancy rate is kept constant, and by about 15% per
year if the same number of disks are used. Actual average seek time and
rotational latency are determined to be, only about 35% and 60% of the
specified values, respectively. Disk head positioning time far dominates the
data transfer time suggesting that data should be reorganized such that
accesses become more sequential.

In what follows several simulation studies of storage systems are discussed.

###  12.2 Simulation Study of a Digital Archive

Digital archives require stronger reliability measures than RAID to avoid data
loss due to device failure. Wildani et al. 2009 [254] consider is multi-level
redundancy coding to reduce the probability of data loss from multiple
simultaneous device failures. This approach handles failures of one or two
devices efficiently, while still allowing the system to survive rare-events,
i.e., four or more device failures.

An uber parity is provided which is calculated from all user data in all
disklets belonging to a stripe in the uber-group using another erasure code.
The uber parity can be stored on NVRAM or always powered-on disks to offset
write bottlenecks, while still keeping the number of active devices low.
Calculations of failure probabilities was used to determines that the addition
of uber parities allows the system to absorb many more disk failures without
data loss. Adding uber-groups negatively impacts performance when these groups
need to be used for a rebuild, but since rebuilds using uber parity occur
rarely, the impact on system performance is minimal. Robustness against rare
events is achieved for under 5% of total system cost.

###  12.3 Simulation of Hierarchical Reliability

HRAID - Hierarchical RAID described in Sectionsec:HRAID has three operational
options:

I. Intra-SN but no Inter-SN Redundancy:

There are $N$ independent Storage Nodes - SNs which are RAID$(4+\ell)$ disk
arrays. This option serves as a baseline in reliability comparisons.

Option II: Inter-SN Redundancy and Rebuild Processing:

Inter-SN processing is invoked on demand for accessed data and for rebuild.
Rebuild is carried out by restriping Rao et al. 2011 [185].

Option III: Inter-SN Redundancy, but no Rebuild Processing:

Rebuild may not be possible due to limited interconnection network bandwidth,
which is geared to normal processing. In the case of SNs considered failed due
to the failure of more than $\ell$ failed disks at an SN but no controller
failures, operation continues in degraded mode with on-demand reconstruction
via inter-SN redundancy, until data loss detected. This is strictly done to
determine the MTTDL, since the system can continue operation.

Given that $u$ is a uniformly distributed pseudo-random numbers in the range
$(0,1)$, it is converted to (negative) exponential distribution to determine
the time to next failures as follows.

$F(t)=1-e^{-\Omega t}=u\mbox{ leads to }t=(-1/\sum_{\forall
i}\delta_{i})\times ln(1-u)\mbox{ or just }t=-\mbox{MTTF}\times\mbox{ln}(u).$

More complex methods for obtaining distributions are available. The accuracy
of simulation results is specified by the confidence interval at a given
confidence level. The two topics are discussed in Chapters 5 and 6 in
Lavenberg 1983 [127].

Procedure: Hierarchical RAID Simulator to Determine MTTDL

Inputs:

$N$: The number of SNs.
$M$: The number of disks per SN.
$D=N\times M$: Total number of disks.
$k$: InterSN redundancy level ($k=0$ for Option I).
$\ell$: IntraSN redundancy level, $\ell=0$ for RAID0, else RAID($4+\ell)$.
$\delta$: Disk failure rate, $\delta=10^{-6}$, so that Mean Time To Failures -
MTTF$=1/\delta=10^{6}$ hours.
$\gamma$: Controller failure rate, multiple of $\delta$).

Outputs

(with initializations):

$F_{cd}=0/1$ data loss occurred due to controller/disk failure.
$N_{c}=0$: number of failed controllers.
Initialize SN/controller state: $C[n]=1,\forall{n}$.
Initialize number of failed disks at $n^{th}$ SN: $F[n]=0,\forall{n}$.

Simulation Variables:

$Clock=0$: Simulation time initialized.
State 0: Failed. State 1: Operational.
$C[0:N-1]$ the state of controllers.
$Disks[0:N-1,0:M-1]$ the state of $D=N\times M$ disks.
$(Disks[n,m]=1,\forall{n},\forall{m}$. /* initial disk states*/
$F[0:N-1]$ # of failed disks at node $n$
$\Omega=\sum_{\forall(i)}\delta_{i}$ sum of component failures rates.
$T_{NF}:$ Time to next failure.
$N_{c}=0$: Number of failed controllers.
$N_{n}=0:$ Number of failed nodes due to controller or $>\ell$ disk failures
$N_{d}=0$: number of failed disks.
$u_{i}$: $i^{th}$ uniformly distributed pseudo-random variable in $(0,1)$.

Simulation steps:

Step_1:

Total failure rate since all failures exponential:
$\Omega=(N-N_{c})\gamma+(D-N_{d})\delta.$

Compute time to next failure and increment $Clock$:
$T_{NF}=(-1/\Omega)ln(u_{1})$,
$Clock+=T_{NF}$. /* advance simulation clock */

Step_2:

Probability a controller failed: $p=(N-N_{c})\gamma/\Omega$.
If $u_{2}\leq p$ then controller failure: goto Step 3.
Else disk failure: goto Step 4.

Step_3:

Determine failed controller: $n=\lfloor N\times u_{3}\rfloor$.
If $C[n]==0$ then regenerate $u_{3}$ and recompute $n$,
else { $C[n]=0$, $N_{c}++$, $N_{n}++$, $D[n,m]=0,0\leq m\leq M-1$,
$t=M-F[n]$ disk inaccessible, so $N_{d}=N_{d}+t$. }
If $N_{n}>k$ then {$F_{cd}=0$, goto Step 6}, else goto Step_1.

Step_4:

$t=\lfloor D\times u_{4}\rfloor$. /* index of failed disk */
SN number: $n=\lfloor t/M\rfloor$;
Disk number: $m=\mbox{mod}(t,M)$.
If $Disks[n,m]==0$ (disk already failed) resample $u_{4}$ and recompute $n$
and $m$,
/* disks attached to failed controller are considered failed */
else {$Disks[n,m]==0$, $N_{d}++$, $F[n]++$]}.
If $F[n]\leq\ell$ goto Step_1.
else { C[n]=0, $t=M-F[n]$, $N_{d}=N_{d}+t$, $N_{n}++$ }.
If $N_{n}\leq k$ then go to Step_1, else $F_{cd}=1$.

Step_5:

Return($Clock$, $F_{cd}$, $N_{c}$, $N_{df}$).

The simulation is repeated to obtain confidence intervals at a sufficiently
high confidence level.

HRAID is conceptually similar to IBM Intelligent Bricks project Wilcke et al.
2006 [253]. It is shown by the shortcut reliability analysis method Thomasian
2006 [231] and simulation results in Thomasian et al. 2012 [240] that for the
same total redundancy level a higher MTTDL is attained by associating higher
reliability at the intraSN rather than interSN level. In other words to
optimize apportionment of three check strips P, Q, and R, it is preferable to
use P and Q for intra-SN and R for inter-SN recovery. This is contradictory to
the two preferred configurations for Intelligent Bricks.
(1) 1DFT (RAID5) at the the node level and 2NFT at the node level provides
40-75% storage efficiency.
(2) 0DFT in bricks and 3NFT at brick level provides 50-75% storage efficiency.

###  12.4 Proteus Open-Source Simulator

Proteus was developed at Storage Systems Research Center - SSRC at U. Calif.
at Santa Cruz - UCSC to predict the risk of data loss in various RAID levels
and two-dimensional arrays Kao et al. 2013 [117]. Proteus was used to learn
that there is no measurable difference between values obtained assuming
deterministic versus exponential repair times. The latter are required by
Markov chain modeling, an issue raised in RAID5 reliability analysis in Gibson
1992 [65].

###  12.5 CQSIM_R Tool Developed at AT&T

CQSIM_R is a tool suited for predicting the reliability of large scale storage
systems at AT&T Hall 2016 [81]. It includes direct calculations based on an
only-drives-fail failure model and an event-based simulator for predicting
failures. These are based on a common combinatorial framework for modeling
placement strategies.

CQSIM_R models common storage systems, including replicated and erasure coded
designs. New results, such as the poor reliability scaling of spread-placed
systems and a quantification of the impact of data center distribution and
rack-awareness on reliability, demonstrate the usefulness of the tool.
Analysis and empirical studies show the tool’s soundness, performance, and
scalability.

###  12.6 SIMedc Simulator for Erasure Coded Data Centers

The discrete-event SIMedc simulator for the reliability analysis of erasure-
coded data centers -edc was developed at Chinese Univ. of Hong-Kong - CUHK by
Zhang et al. 2019 [269]. SIMedc reports reliability metrics of an erasure-
coded data center based on data center topology, erasure codes, redundancy
placement, and failure/repair patterns of different subsystems based on
statistical models or production traces.

Simulation is accelerated via importance sampling assisted by uniformization
Grassman 1991 [71]. It is shown that placing erasure-coded data in fewer racks
generally improves reliability by reducing cross-rack repair traffic, even
though it sacrifices rack-level fault tolerance in the face of correlated
failures.

##  13 Appendix IV: RAID Reliability Modeling Tools

13.1 Automated Reliability Interactive Estimation System - ARIES.
13.2 System AVailability Estimator - SAVE Project at IBM Research.
13.3 Symbolic Hierarchical Automated Reliability and Performance Evaluator -
SHARPE.
13.3.1The mathematics behind SHARPE reliability modeling package.
13.3.2Numerical method for computing the transient probabilities.

Analytic and simulation software packages developed to assess the reliability,
availability, and serviceability of computer systems are surveyed in Johnson
and Malek 1988 [113]. Provided are the application of the tool, input, models,
and model solution methods. ARIES, SHARPE, and SAVE tools are reviewed in this
section.

###  13.1 Automated Reliability Interactive Estimation System - ARIES Project
at UCLA

A. Avizienis who later joined Univ. of Calif. at Los Angeles - UCLA from Jet
Propulsion Labs - JPL led the design and reliability analysis of fault-
tolerant JPL Self-Testing and Repairing - STAR computer, for an unmanned ten
year mission to a distant planet. The computer used Trip Modular Redundancy -
TMR with a majority voter.

An example of this effort was a reliability expression derived for a a hybrid
$k$-out-of-$n$ system with $n$ components energized reported in Mathur and
Avizienis [141], which is given in Example 3.32 in Trivedi 2001 [249]. Aries
is a unifying method for analyzing closed systems Ng and Avizienis 1980 [158].
The parameters used in this study given in Table LABEL:tab:NgAv80¿

$N$ | initial number of modules in the active configuration.
---|---
$D$ | number of degradations allowed in the active configuration
$S$ | number of spare modules.
$Ca$ | coverage for recovery from active module failures.
$Cd$ | coverage for recovery from spare module failures.
$\lambda$ | failure rate of active modules.
$\mu$ | failure rate of spare modules
${\bf Y}$ | sequence of allowed degradations of the active configuration.
${\bf CY}$ | coverage vector for transitions into degraded configuration.
Table 27: Parameters used in ARIES.

The reliability of a closed fault-tolerant system is expressed as:

$\displaystyle R(t)=\sum_{\forall i}A_{i}e^{-\sigma_{i}t}$ (68)

The analysis is based on the eigenvalues of the CTMC representing the failure
of system components and its recovery by using spares. Repeated roots are not
considered.

Let ${\cal S}_{i}$ indicate a nonfailed state and $\sigma_{i}$ the failure
rate at that state. $A_{i}$ can be expressed as a function of state parameters
and can be quite complex. The MTTF easily follows from Eq. 68

$\mbox{MTTF}=\int_{t=0}^{\infty}R(t)dt=\sum_{\forall
i}\frac{A_{i}}{\sigma_{i}}.$

For closed systems $R(t)$ given by Eq. (68) has a specific form.

$\displaystyle R(t)=X(t){\cal A}W(t).$ (69)

$\displaystyle X(t)=(e^{-Y[0]\lambda t},\ldots,e^{-Y[D]\lambda t})\mbox{ with
}Y[0]=N\hskip 14.22636pt\mbox{ and }W(t)=(1,e^{-\mu t},\ldots,e^{-S\mu t}),$

$\displaystyle{\cal A}=\begin{pmatrix}A_{S,0}^{0}&\ldots&A_{S,0}^{D}\\\
\vdots&\ddots&\vdots\\\ A_{S,S}^{0}&\ldots&A_{S,S}^{D}\\\ \end{pmatrix}$ (70)

Two more parameters used for modeling repairable systems are the number of
repairman or repair facilities ($M$) and the repair rate of one repairman
($\Psi$)

###  13.2 System AVailability Estimator - SAVE Project at IBM Research

An early reliability modeling effort at IBM defined the coverage factor ($c$),
which is the probability that the system can successfully recover Bouricius et
al. 1971 [25]. The SAVE project was started in S. Lavenberg’s Systems Modeling
and Analysis Dept. at IBM Research in mid-1985. The effort first dealt with
analytical reliability modeling, along the lines adopted in ARIES and SHARPE
Blum et al. 1994 [22].

Realistic system models are often not amenable to analysis using conventional
analytic or numerical methods Stewart 2021 [213]. Adopting simulation as an
alternative to analysis for reliability estimation led to a unified framework
for simulating Markovian models of highly dependable systems Goyal et al. 1992
[69],

Straightforward simulations is too costly since failures are rare. Techniques
for fast simulation of models of highly dependable systems are reviewed in
Nicola et al. 2001 [160]. Importance sampling is one such method and when it
works well it can reduce simulation run lengths by several orders of
magnitude. 245245245http://jrxv.net/x/16/ism.pdf

The following example is provided in this study: (1) two sets of processors
with four processors per set, (2) two sets of controllers with two controllers
per set, (3) four clusters of disks each consisting of four disks. The
multiprocessors are connected to all controllers. The pair of controllers have
two connections to disk clusters. In a disk cluster, data are replicated so
that one disk can fail without affecting the system. The ID mirrored disk
organization in Section 14 is utilized.

When a processor fails it has a 0.01 probability of causing another processor
to fail. Each unit in the system has two failure modes which occur with equal
probability. The repair rates for mode 1 and 2 failures are 1 and 0.5 hour,
respectively. The failure rates in hour-1 are 1/1000 for processors, 1/20,000
for controllers, and 1/60,000 for disks. The repair rates are 1 and 1/2 for
mode 1 and mode 2 failures.

Efficient simulation techniques for estimating steady-state quantities in
models of highly dependable computing systems with general component failure
and repair time distributions are developed in Nicola et al. 1993 [159]. The
regenerative method of simulation for steady state estimation can be used when
the failure time distributions are exponentially distributed. A splitting
technique is used for importance sampling to speed up the simulation of rare
system failure events during a cycle. Experimental results show that the
method is effective in practice.

###  13.3 Symbolic Hierarchical Automated Reliability and Performance
Evaluator - SHARPE

SHARPE was developed at Duke Univ. by Sahner, Trivedi and Puliafito 1996
[196]. Several generations of K. Trivedi’s students contributed to SHARPE.
246246246https://sharpe.pratt.duke.edu/

Section 4.7.2 in [196] considers a CTMC with $m=2$ non-absorbing and $n=2$
absorbing states, which have no transitions to other states Trivedi 2001
[249]. In the case of RAID5 a second disk failure or unreadable sector will
lead to data loss as discussed in Section 11.5. Section 5.4 titled “Imperfect
Fault Coverage and Reliability” in Trivedi 2001 [249] provides a good
discussion and formulas derived in Ng and Avizienis [158]. Section 8.5 titled
“Markov Chains with Absorbing States” discusses a technique used in Sharpe..
Hierarchical reliability modeling is discussed in Chapter 16 in Trivedi and
Bobbio 2017 [250].

####  13.3.1 The Mathematics Behind SHARPE Reliability Modeling Package

The infinitesimal generator matrix with the states indexed as $(0:m-1)$ and
$(m:m+n-1)$ for $m=n=2$ is given as:

${\bf Q}=\begin{pmatrix}-(\gamma+\lambda)&\gamma&\lambda&0\\\
\beta&-(\beta+\delta+\mu)&\mu&\delta\\\ 0&0&0&0\\\ 0&0&0&0\\\ \end{pmatrix}$

Differential equations and respective LSTs are as follows where
${\bf\alpha}={\bf\pi}(0)=\\{\alpha_{0},\alpha_{1},\alpha_{2},\alpha_{3}\\}$
denotes the initial state vector.

$\displaystyle\frac{d\pi_{0}(t)}{dt}$
$\displaystyle=-(\gamma+\lambda)\pi_{0}(t)+\beta\pi_{1}(t),\hskip
14.22636ptsL^{*}_{0}(s)-\alpha_{0}=-(\gamma+\lambda)L^{*}_{0}(s)+\beta
L^{*}_{1}(s)$ $\displaystyle\frac{d\pi_{1}(t)}{dt}$
$\displaystyle=-(\beta+\delta+\mu)\pi_{1}(t_{+}\gamma\pi_{0}(t),\hskip
14.22636ptsL^{*}_{1}(s)-\alpha_{1}=-(\beta+\delta+\mu)L^{*}_{1}(s)+\gamma
L^{*}_{0}(s)$ $\displaystyle\frac{d\pi_{2}(t)}{dt}$
$\displaystyle=\lambda\pi_{0}(t)+\mu\pi_{1}(t),\hskip
14.22636ptsL^{*}_{2}(s)-\alpha_{2}=\lambda L^{*}_{0}(s)+\mu L^{*}_{1}(s)$
$\displaystyle\frac{d\pi_{3}(t)}{dt}$ $\displaystyle=\delta\pi_{1}(t),\hskip
14.22636ptsL^{*}_{3}(s)-\alpha_{3}=\delta L^{*}_{1}(s)$

The vector of transforms is given as ${\bf
L^{*}}=\left(L^{*}_{0},\ldots,L^{*}_{m-1}\right)$. the vector of initial
probabilities as ${\bf\alpha}=(\alpha_{0},\alpha_{1},\ldots,\alpha_{m-1})$ and
${\bf T}$ is the upper $m\times m$ upper left hand corner of generator matrix
${\bf Q}$, we have: The system of first $m$ equations in matrix form and their
solution is given as follows:

$\displaystyle s{\bf L}^{*}-{\bf\alpha}={\bf L}^{*}{\bf T}\Rightarrow{\bf
L}^{*}={\bf\alpha}\left(s{\bf I}-{\bf T}\right)^{-1}$

We now have the LST to the transient distribution functions for nonabsorbing
states We define ${\bf T}_{i}$ to be the $m\times 1$ vector that is transpose
of $(q_{1i},q_{2i},\ldots,q_{mi})$ so:

$sL^{*}_{2}(s)=\alpha_{2}+{\bf L}{\bf T}_{2}=\alpha_{2}+{\bf\alpha}(s{\bf
I}-{\bf T})^{-1}{\bf T}_{2}$

For the absorbing state $L^{*}_{i}$ we have:

${\bf L}^{*}_{i}(s)=\frac{1}{s}\left(\alpha_{i}+{\bf\alpha}\left(s{\bf I}-{\bf
T}\right)^{-1}\right){\bf T}_{i},$

Define $T_{i}$ as the transpose of $\left(q_{1i},q_{2i},\ldots,q_{mi}\right)$.
We have:

$sL^{*}_{2}(s)=\alpha_{2}+{\bf L}{\bf T_{2}}=\alpha_{2}+{\bf\alpha}(s{\bf
I}={bfT})^{-1}T_{2}$

In general, for absorbing state $i$, we have:

$L_{i}(s)=\frac{1}{s}\left(\alpha_{i}+{\bf\alpha}(s{\bf I}-{\bf
T})^{-1}T_{i}\right)$

The real work is inverting the LST using partial fraction expansion:

${\bf P}(s)=\frac{1}{s}\left({\bf\alpha}\left(s{\bf I}-{\bf
T}\right)^{-1}T_{i}\right)$

Vector ${\bf X}(s)$ is defined as

${\bf X}(s)=\left(s{\bf I}-{\bf T}\right)^{-1}{\bf T}_{i}\mbox{ then
}\left(s{\bf I}-{\bf T}\right){\bf X}(s)={\bf T}_{i}$

Applying Cramer’s rule the $i^{th}$ element of ${\bf X}$ is:
247247247https://en.wikipedia.org/wiki/Cramer’s_rule

$X_{i}(s)=\frac{N_{i}(s)}{D(s)}$

$D(s)$ is the determinant of $({\bf I}-{\bf T})$ and $N_{i}(s)$ is the
determinant of the matrix obtained by replacing the $i^{th}$ column of $s{\bf
I}-{\bf T}$ by the column vector $T_{i}$.

Given the column vector ${\bf X}$ we have:

$\displaystyle P(s)=\frac{1}{s}\left({\bf\alpha}{\bf
X}(s)\right)=\frac{\sum\alpha_{i}N_{i}(s)}{sD(s)}$

To invert $P(s)$ we need to carry out a partial fraction expansion. The zero
root of the denominator yields the steady state solution. Given
$D(s)=det(s{\bf I}-{\bf T})$ eigenvalues of ${\bf T}$ are given as sorted list
of the roots $(s_{1},s_{2},\ldots,s_{m+1})$, where root $s_{k}$ may occur
$d_{k}$ times. Then after determining $a_{k}$ we have the inversion:

$\displaystyle
P^{*}(s)=\sum_{k=1}^{m+1}\frac{a_{k}}{(s-s_{k})^{d_{k}}}\Rightarrow
F(t)=\sum_{k=1}^{m+1}\frac{a_{k}}{(d_{k}-1)!}t^{d_{k}-1}e^{s_{k}t}$

This solution yields transient state probabilities. However, the number and
types of matrix manipulations make the algorithm unstable for some CTMC.

####  13.3.2 Numerical Method for Computing the Transient Probabilities

A formal solution to $\frac{d\pi(t)}{dt}=\pi(t)Q$ is:

${\bf\pi}(t)={\bf\pi}(0)e^{{\bf Q}t}\mbox{ where }e^{{\bf
Q}t}=\sum_{i=0}^{\infty}\frac{({\bf Q}t)^{i}}{i!}$

Given $q\geq\mbox{max}_{i}|q_{ii}|$

${\bf\pi}(t)=\sum_{k=0}^{\infty}\theta(k)e^{-qt}\frac{(qt)^{k}}{k!}$

where $\theta(0)={\bf\pi}(0)$, ${\bf Q}^{*}=\frac{{\bf Q}}{q}+{\bf I}$ and
$\theta(k)=\theta(k-1){\bf Q}^{*}$

The reader is referred to Chapter 8 in Stewart 2021 [213] for alternate
solution methods.

##  14 Appendix V: Mirrored and Hybrid Disk Arrays

14.1. Mirrored and hybrid disk arrays description and reliability comparison.
14.3. Shortcut Method to compare RAID reliability.
14.4. Reliability analysis of multilevel RAID arrays.
14.5. Mirrored RAID5 - RAID1/5 reliability analysis.
14.6. RAID5 with mirrored disks - RAID5/1.
14.7. Shortcut reliability analysis to compare RAID1/5 and RAID5/1.
14.8 Reliability and performance comparison of two Heterogeneous Disk Arrays

###  14.1 Mirrored and Hybrid Disk Arrays Descriptions and Reliability
Comparison

In addition to increased availability replication helps with meeting Service
Level Agreements - SLAs. 248248248https://en.wikipedia.org/wiki/Service-
level_agreement A request does not have to wait if at least one disk with
utilization $\rho_{i},1\leq i\leq m$ is idle:

$P[\mbox{at least one disk idle out of }m]=1-\prod_{i=1}^{m}(1-\rho_{i}).$

Mirrored or duplexed disks which are the simplest form of replication are
classified as RAID1 in Patterson et al. 1988 [169]. Mirroring and duplexed
processors were adopted by Tandem (now part of HP) which evolved to NonStop
SQL system Tandem 1987 [217]. The Teradata Data Base Computer - DBC/1012 with
terabyte capacity was first shipped in 1980s Sloan 1992 [210]. EMC’s (now
Dell/EMC) Symmetrix was an early raid1 which could emulate IBM DASD.
249249249https://en.wikipedia.org/wiki/EMC_Symmetrix

Four mirrored disk organizations are described and their reliability and
performance compared in Thomasian and Blaum 2006 [232] and Thomasian and Xu
2008 [234]. Hybrid disk arrays which store XORs of multiple disks instead of
just mirroring are patented Wilner 2001 [257] and evaluated in Thomasian and
Tang 2012 [239]

$k$-way replication provides the opportunity to reduce disk access time for
read requests by accessing the disk with the lowest seek distance, hence with
minimum seek distance. Since all disks need to be updated the maximum of $k$
uniformly distributed seek distances as well as the minimum is derived in Gray
and Bitton 1988 [18]:

$\displaystyle E[\mbox{min of k-way seeks}]\approx\frac{C}{2k+1},\hskip
14.22636ptE[\mbox{max of k-way seeks}]\approx C(1-I_{k}),\mbox{ where:
}I_{k}=\frac{2k}{2k+1}\frac{2k-2}{2k-1}\ldots\frac{2}{3}.$ (71)

Distributed Shortest Processing Time First - DSPTF is a request distribution
protocol for decentralized brick storage system with high-speed interconnects,
which dynamically selects servers with a replica to satisfy a request, while
balancing load exploits aggregate cache capacity Lumb and Golding 2004 [136]
Compared to existing decentralized approaches, such as hash-based request
distribution, D-SPTF achieves up to 65% higher throughput. Storage bricks are
reviewed in Sections 11.12 and 11.13 in Thomasian 2021 [245], presentation on
the topic is by Gray 1992 in [74].

Anticipatory arm placement places the arm at $C/2$ in disk with $C$ cylinders
reducing the seek distance to C/4 for uniform requests over all cylinders,
while otherwise it is $C/3$ according to Eq. (6). In mirrored disks the arms
are placed at $C/4$ and $3C/4$ reducing the mean seek distance to $C/4$, while
$C/5$ is achievable by shortest seek routing according to Eq. (71). Disks with
hot spots (frequently accessed cylinders) and zoning are also considered
Thomasian and Fu 2006 [229].

Loads across BM disk pairs can be balanced via striping in the hierarchical
array RAID0/1, with RAID0 at the higher level and RAID1 at the lower level.
The load due to read requests to disk pairs is balanced via uniform routing
(with equal probabilities) or round-robin routing. In what follows we show
that the latter exhibits shorter mean waiting times under the assumption that
arrivals are Poisson with arrival rate $\lambda$ and service times
exponentially distributed with mean $\bar{x}=1/\mu$.

With round robin routing the arrival process to each disk is the sum of two
exponentials or Erlang-2 distribution with Coefficient of Variation -
CV$=1/2$, while the CV for exponential distribution is one. The mean waiting
time on a GI/M/1 queue with Erlang-2 arrivals is Kleinrock 1975 [122]:

$W_{GI/M/1}=\frac{\sigma\bar{x}}{1-\sigma}\mbox{ with }\sigma={\cal
A}^{*}(\mu-\mu\sigma),\mbox{ where }{\cal
A}^{*}(s)=[\frac{2\lambda}{s+2\lambda}]^{2}$
$\sigma^{2}-(1+4\rho)\sigma+4\rho^{2}=0,\hskip
8.53581pt\sigma=\frac{1}{2}(1+4\rho-\sqrt{1+8\rho})$

$W_{GI/M/1}<W_{M/M/1}$ since it can be shown that $\rho>\sigma$. A smaller CV
does not insure a smaller mean waiting time for $W_{GI/M/1}$ as shown by a
counterexample in Thomasian 2014b [242].

RAID1 is especially suited in doubling disk bandwidth for random updates of
small blocks as in OLTP, while RAID5 incurs SWP. RAID1 is less efficient than
RAID5 in writing large blocks or accessing large blocks of data that can be
carried out in parallel in RAID5.

When one of two of disk pairs in BM fails the load of the surviving disk is
doubled and this may lead to overload or at least higher queueing delays. This
BM weakness led to several RAID1 configurations which are described here:

Basic Mirroring - BM:

This is the simplest form of replication, where the same data appears at both
disks. RAID0/1 is a striped array with $M=N/2$ pairs of mirrored disks. Up to
$M$ disk failures can be tolerated as long as they are not pairs. When a disk
fails BM has the worst performance in terms of unbalanced disk loads, i.e.,
the read load of the surviving disk is doubled. According to Table 28 BM has
the highest reliability among the four RAID1 organizations considered here.
This is because the probability that the second disk failure leading to data
loss by being a pair of the first failed disk is lowest.

Interleaved Declustering - ID:

Teradata DBC/1012 partitioned its $N$ disks into $c$ clusters with $n=N/c$
disks per cluster as shown in Fig. 21. Each disk has a primary and a secondary
area. The data in primary area is partitioned and placed onto $n-1$ secondary
areas in the same cluster. A failed disk results in $n/(n-1)$ load increase at
the $n-1$ surviving disks in a cluster. Two disk failure in a cluster will
lead to data loss. The setting $c=N/2$ or $n=2$ is tantamount to BM. Teradata
latest product is Vantage 17.20, whose Native Object Store - NOS can reside on
cloud storage. 250250250https://www.dwhpro.com/teradata-nos-native-object-
store/

Group Rotate Declustering - GRD:

There are two mirrored RAID0 arrays with $M=N/2$ disks each, specified as
RAID1/0, but strips on the right side are rotated with respect to the strips
on the left side as shown in Fig. 20 Chen and Towsley 1996 [34]. When a disk
fails its load is evenly distributed over the disks on the other side. Two
disk failures on one side will lead to data loss.

Chained Declustering- CD:

Hsiao and DeWitt 1990 [87] proposed CD in conjunction with the Gamma database
machine project at U Wisconsin in 1990, i.e., years after the Teradata
DBC/1012. 251251251https://research.cs.wisc.edu/techreports/1990/TR921.pdf
Data in the primary area on the $i^{th}$ disk is replicated on the secondary
area of the ${i+1}^{st}\mbox{mod}(N)$ disk as shown in Fig. 22 Similarly to ID
primary and secondary data can be placed in outer or inner cylinders, or upper
and lower disk tracks when there are an even number of tracks per cylinder.
Two successive disk failures leads to data loss, but the reliability is lower
than BM since there are twice as many data loss opportunities as in BM: when
following the $i^{th}$ disk failure the $i\pm 1\mbox{mod}(N)$ disk fails.

Primary Disks | Secondary Disks
---|---
$D_{1}$ | $D_{2}$ | $D_{3}$ | $D_{4}$ | $D_{5}$ | $D_{6}$ | $D_{7}$ | $D_{8}$
$A$ | $B$ | $C$ | $D$ | $A^{\prime}$ | $B^{\prime}$ | $C^{\prime}$ | $D^{\prime}$
$E$ | $F$ | $G$ | $H$ | $E^{\prime}$ | $F^{\prime}$ | $G^{\prime}$ | $H^{\prime}$
$I$ | $J$ | $K$ | $L$ | $I^{\prime}$ | $J^{\prime}$ | $K^{\prime}$ | $L^{\prime}$
$M$ | $N$ | $O$ | $P$ | $M^{\prime}$ | $N^{\prime}$ | $O^{\prime}$ | $P^{\prime}$
Figure 19: RAID0/1 with $N=8$ disks. Primary Disks | Secondary Disks
---|---
$D_{1}$ | $D_{2}$ | $D_{3}$ | $D_{4}$ | $D_{5}$ | $D_{6}$ | $D_{7}$ | $D_{8}$
$A$ | $B$ | $C$ | $D$ | $A^{\prime}$ | $B^{\prime}$ | $C^{\prime}$ | $D^{\prime}$
$E$ | $F$ | $G$ | $H$ | $H^{\prime}$ | $E^{\prime}$ | $F^{\prime}$ | $G^{\prime}$
$I$ | $J$ | $K$ | $L$ | $K^{\prime}$ | $L^{\prime}$ | $I^{\prime}$ | $J^{\prime}$
$M$ | $N$ | $O$ | $P$ | $N^{\prime}$ | $O^{\prime}$ | $P^{\prime}$ | $M^{\prime}$
Figure 20: Group Rotate Declustering with $N=8$ disks. Cluster 1 | Cluster 2
---|---
$D_{1}$ | $D_{2}$ | $D_{3}$ | $D_{4}$ | $D_{5}$ | $D_{6}$ | $D_{7}$ | $D_{8}$
$~{}A~{}$ | $~{}B~{}~{}$ | $~{}C~{}~{}$ | $~{}D~{}~{}$ | $~{}E~{}~{}$ | $~{}F~{}~{}$ | $~{}G~{}~{}$ | $~{}H~{}~{}$
$b_{3}$ | $a_{1}$ | $a_{2}$ | $a_{3}$ | $f_{3}$ | $e_{1}$ | $e_{2}$ | $e_{3}$
$c_{2}$ | $c_{3}$ | $b_{1}$ | $b_{2}$ | $g_{2}$ | $g_{3}$ | $f_{1}$ | $f_{2}$
$d_{1}$ | $d_{2}$ | $d_{3}$ | $c_{1}$ | $h_{1}$ | $h_{2}$ | $h_{3}$ | $g_{1}$
Figure 21:  Interleaved Declustering with $N=8$ disks, $c=2$ clusters, and $n=4$ disks per cluster. Capital letters denote primary data and small letters subsets of secondary data. $D_{1}$ | $D_{2}$ | $D_{3}$ | $D_{4}$ | $D_{5}$ | $D_{6}$ | $D_{7}$ | $D_{8}$
---|---|---|---|---|---|---|---
$\frac{1}{2}A$ | $\frac{1}{2}B$ | $\frac{1}{2}C$ | $\frac{1}{2}D$ | $\frac{1}{2}E$ | $\frac{1}{2}F$ | $\frac{1}{2}G$ | $\frac{1}{2}H$
$\frac{1}{2}h$ | $\frac{1}{2}a$ | $\frac{1}{2}b$ | $\frac{1}{2}c$ | $\frac{1}{2}d$ | $\frac{1}{2}e$ | $\frac{1}{2}f$ | $\frac{1}{2}g$
Figure 22:  Chained declustering with $N=8$ disks. Primary (resp. secondary)
blocks are in capital (resp. small) letters. The read load is evenly
distributed among the primary and secondary copies.

Let $I$ denote the maximum number of disk failures that can be tolerated
without data loss For BM with $N=2M$ disks $I=M$ and $I=c$ for the ID
organization.

Setting $r=r(t)$ to simplify the notation RAID1 reliability expressions can be
expressed as follows:

$\displaystyle R_{RAID}(N)=\sum_{i=0}^{I}A(N,i)r^{N-i}(1-r)^{i}.$ (72)

$A(N,0)=1$ by and $A(N,i)=0$ for $i>M$.

In the case of BM up to $M$ disk failures can be tolerated, as long as one
disk in each pair survives, hence:

$\displaystyle A(N,i)=\binom{M}{i}2^{i},\hskip 5.69054pt0\leq i\leq M.$ (73)

In the case of ID with $c$ clusters and $n=N/c$ disks per cluster, there can
only be one disk failure per cluster.

$\displaystyle A(N,i)=\binom{c}{i}n^{i},\mbox{ where }n=N/c,\hskip
5.69054pt0\leq i\leq c.$ (74)

In the case of GRD up to $M$ disks on each side all $M$ disks can fail as long
as they are all on one side.

$\displaystyle A(N,i)=2\binom{M}{i},\hskip 5.69054pt0\leq i\leq M.$ (75)

The expression for $A(N,i)$ for CD is derived in Thomasian and Blaum 2006
[232] as:

$\displaystyle A(N,i)=\binom{N-i-1}{i-1}+\binom{N-i}{i},\hskip 5.69054pt1\leq
i\leq M.$ (76)

Hybrid disk arrays combine mirroring with parity coding. LSI RAID has disks
holding the XOR of neighboring disks according to Wilner 2001 [257].

$D_{A},(D_{A}\oplus D_{B}),D_{B},(D_{B}\oplus D_{C}),D_{C},(D_{C}\oplus
D_{D}),D_{D},(D_{D}\oplus D_{A})$

Three consecutive disk failures can be tolerated as long as the middle disk is
not a data disk.

SSPiRAL is a generalization to three disks participating in parity computation
Amer et al. 2008 [12] Given four data disk $D_{A},D_{B},D_{C},D_{D}$ the four
parities are computed as follows:

$(D_{A}\oplus D_{B}\oplus D_{C}),\hskip 8.53581pt(D_{B}\oplus D_{C}\oplus
D_{D}),\hskip 8.53581pt(D_{C}\oplus D_{D}\oplus D_{A}),\hskip
8.53581pt(D_{D}\oplus D_{A}\oplus D_{B}).$

Up to four disk failures can be tolerated as long as it is not a data disk and
the three parities it participates in. 252252252A minor correction to the
reliability expression in SSPiRAL paper is made in Thomasian and Tang 2012
[239].

Duplexed disks in Tandem computers came with two cross-connected processors,
instead of processor disk pairs. Given that $R_{c}$ and $R_{d}$ are the CPU
and disk reliability, the former configuration has a higher reliability.

$R_{cross-connected}=1-(1-R_{c}R_{d})^{2}\approx
2R_{c}R_{d}-4R_{c}^{2}R_{d}^{2},\hskip
14.22636ptR_{dedicated}=[1-(1-R_{c})^{2}][1-(1-R_{d})^{2}]\approx
4R_{c}R_{d}-2R_{c}R_{d}^{2}-2R_{d}R^{2}_{c}d$

###  14.2 AutoRAID Multilevel RAID

AutoRAID is a two level memory hierarchy with RAID1 acting as a cache holding
hot data and cold data is held in a RAID5/LSA array Wilkes et al. 1996 [256].
Data is initially written onto RAID1 and as RAID1 disks fill their contents
are moved to RAID5/LSA.

AutoRAID assumes that the working set for RAID1’s active data changes slowly.
A trace-driven analysis of storage working set sizes was conducted by Ruemmler
and Wilkes 1993 [192]. Relocation Blocks - RBs are promoted to RAID1 when they
are updated.

###  14.3 Shortcut Method to Compare the Reliability of Mirrored Disks and
RAID(4+$\ell$

The shortcut method allows the comparison of the reliability of various RAID
configurations, which does not require the transient analysis or plotting disk
reliability $R(t)$ versus $t$ Thomasian 2006 [231]. This is accomplished by
expressing disk reliability as $r=1-\varepsilon$, e.g., for MTTF=$10^{6}$
hours or 114 years, a good approximation for relatively short time $(t_{s})$

$R(t_{s})=e^{-\delta t_{s}}\approx 1-\delta t_{s}\mbox{ after three years
}R(3)=1-3/114=0.975,\mbox{ hence :}\varepsilon=0.025.$

RAID with $n$-way replication fails with $n$ disk failures and this is
indicated by the power $n$ in the reliability expression. In other words the
number of failures tolerated is $n-1$ (we use $\bar{r}=1-r$).

$R_{n-way}=1-(1-r)^{n}=1-\bar{r}^{n}=1-\varepsilon^{n}$

The expressions for the RAID1 with BM configurations is as follows:

$\displaystyle R_{BM}\approx
r^{N}+Nr^{N-1}\bar{r}+\binom{N}{2}r^{N-2}(\bar{r})^{2}\approx
1-0.5N\varepsilon^{2}.$ (77)

For GRD the reliability expression can be written directly, since it is as if
we have two logical disks each comprising $M=N/2$ disks.

$\displaystyle R_{GRD}=2r^{N/2}-r^{N}\approx
1-\frac{1}{4}N^{2}\varepsilon^{2}.$ (78)

$\displaystyle R_{ID}\approx
r^{N}+c(\frac{N}{c})r^{N-1}\bar{r}+\binom{c}{2}(\frac{N}{c})^{2}r^{N-2}(\bar{r})^{2}=1-\frac{N}{2}(\frac{N}{c}-1)\varepsilon^{2}.$
(79)

We only need the first three terms in the reliability expression to obtain
$R_{CD}$ With two disk failures there are N configurations leading to data
loss:

$A(N,2)\approx\binom{N}{2}-N=\frac{1}{2}N(N-3)$

$\displaystyle R_{CD}\approx
r^{N}+Nr^{N-1}\bar{r}+\frac{1}{2}N(N-3)r^{N-2}(\bar{r})^{2}=1-N\varepsilon^{2}.$
(80)

We denote the reliability of RAID5 and RAID(4+$\ell$) as $R_{\ell}$.

$R_{5}=r^{N}+N\bar{r}r^{N-1}=(1-\varepsilon)^{N}+N\varepsilon(1-\varepsilon)^{N-1}\approx
1-\frac{1}{2}5N(N-1)\varepsilon^{2}$

$\displaystyle R_{\ell}\approx
1-\binom{N}{\ell+1}\varepsilon^{\ell+1}+\binom{N}{\ell+2}\varepsilon^{\ell+2}-\ldots$
(81)

A summary of shortcut reliability analysis results in [239] are given in Table
28.

RAID5 | BM | CD | GRD | ID | RAID6 | LSI | RAID7 | SSP
---|---|---|---|---|---|---|---|---
| $\frac{163}{280\delta}$ | $\frac{379}{840\delta}$ | $\frac{3}{8\delta}$ | $\frac{61}{168\delta}$ | $\frac{73}{168\delta}$ | $\frac{82}{105\delta}$ | $\frac{533}{840\delta}$ | $\frac{701}{840\delta}$
$0.268\delta^{-1}$ | $0.582\delta^{-1}$ | $0.451\delta^{-1}$ | $0.375\delta^{-1}$ | $0.363\delta^{-1}$ | $0.435\delta^{-1}$ | $0.781\delta^{-1}$ | $0.635\delta^{-1}$ | $0.8345\delta^{-1}$
$\binom{N}{2}\varepsilon^{2}$ | $\frac{N\varepsilon^{2}}{2}$ | $N\varepsilon^{2}$ | $\frac{N(N-1)\varepsilon^{2}}{4}$ | $\frac{N(N-c)\varepsilon^{2}}{2c}$ | $\binom{N}{3}\varepsilon^{3}$ |  $(\binom{N}{3}-\frac{N}{2})$$\varepsilon^{3}$ | $\binom{N}{4}\varepsilon^{4}$ | $\frac{1}{5}\binom{N}{4}\varepsilon^{4}$
Table 28: MTTDLs as a ratio and a fraction of the MTTF ($\delta^{-1}$) and the
first term in asymptotic reliability expression with $\varepsilon$ denoting
the unreliability of a single disk and the power is the minimum number of disk
failures leading to data loss.

RAID6 results apply to EVENODD, X-code, and RDP, all three of which are 2DFT.

Hybrid disk arrays which combine replication and parity coding provide a
higher reliability at the same redundancy level. RAID1 provides 2-way, LSI
RAID 3-way, and SSPiRAL 4-way replication. The update penalty is proportional
to the number of ways. In the case of hybrid arrays in addition to a write a
RMW is required.

###  14.4 Reliability Analysis of Multilevel RAID Arrays

Two multilevel RAID disk arrays are considered in this section: mirrored RAID5
(RAID1/5) and RAID5 consisting of mirrored disks (RAID5/1). RAID1/0 and
RAID0/1 was discussed in the previous section. Note that the number of disks
is the same in both cases, but one configuration provides higher reliability
than the other and this is verified with the shortcut reliability analysis
method in Thomasian 2006 [231].

###  14.5 Reliability of Mirrored RAID5 - RAID1/5 Reliability

Consider mirroring of RAID5 arrays and no repair via mirroring, from one side
to the other. If more than one disk on each side fails, that side is
considered failed although the remaining disks are intact.

$R_{RAID1/5}=2R_{5}(t)-R_{5}^{2}(t)$

Substituting $R_{RAID5}(t)$ given by Eq. (refeq:RAID5t):

$\displaystyle R_{RAID1/5}=2[\frac{\zeta e^{\eta t}-\eta e^{\zeta
t}}{\zeta-\eta}]-[\frac{\zeta e^{\eta t}-\eta e^{\zeta t}}{\zeta-\eta}]^{2}=$
(82) $\displaystyle 2\frac{\zeta e^{\eta t}-\eta e^{\zeta
t}}{\zeta-\eta}-\frac{\zeta^{2}e^{2\eta t}+\eta^{2}e^{2\zeta t}-2\eta\zeta
e^{(\eta+\zeta)t}}{(\zeta-\eta)^{2}}$

$\displaystyle
MTTDL_{mirrored/RAID5}=\frac{1}{\zeta-\eta}[-2\frac{\zeta}{\eta}+\frac{\eta}{\zeta}]-\frac{1}{(\zeta-\eta)^{2}}[-2\frac{\zeta^{2}}{\eta}+2\frac{\eta^{2}}{\zeta}+2\frac{\eta\zeta}{\eta+\zeta}]$

RAID5 reliability can be expressed as a single component whose MTTF equals the
MTTDL as was given by Eq. (49).

$R_{RAID15}^{appr}(t)=2R_{5}^{appr}(t)-[R_{5}^{appr}(t)]^{2}$
$MTTDL_{RAID15}^{appr}=\frac{1.5\mu}{N(N+1)\delta^{2}}=\frac{1.5MTTF^{2}}{N(N+1)MTTR}$

###  14.6 Reliability of RAID5 Consisting of Mirrored Disks - RAID5/1

An approximate expression for mirrored RAID5 MTTDL was given in Xin et al.
2003 [260]. The contents of a failed disk are recovered by its mirror, but
otherwise by invoking the RAID5 paradigm

$MTTDL_{RAID5/1}\approx\frac{\mu^{3}}{4N(N-1)\delta^{4}}=\frac{MTTF^{4}}{4N(N-1)MTTR^{3}}$

A rigorous method to derive RAID5/1 MTTDL using the shortest path reliability
model is presented in Iliadis and Venkatesan 2015b [101]. The state tuples
$(x,y,z)$ indicate that there are x pairs with both devices in operation, $y$
pairs with one device in operation and one device failed, and $z$ pairs with
both devices failed. With $D$ devices on each side and failure rate $\delta$
and repair rate $\mu$ we have the following state transitions leading to Data
Loss - DL.

$\displaystyle(D,0,0)$ $\displaystyle\xrightarrow{2D\delta}(D-1,1.0),\hskip
14.22636pt\xleftarrow{\mu}(D-1,1,0)$ $\displaystyle(D-1,1,0)$
$\displaystyle\xrightarrow{\delta}(D-1,0,1),\hskip
14.22636pt(D-1,0,1)\xleftarrow{2\mu}(D-1,1,0)$ $\displaystyle(D-1,1,0)$
$\displaystyle\xrightarrow{2(D-1)\delta}(D-2,2.0),\hskip
14.22636pt(D-2,2,01)\xleftarrow{2\mu}(D-1,1,0)$ $\displaystyle(D-1,0,1)$
$\displaystyle\xrightarrow{2(D-1)\delta}(D-2,1,1),\hskip
14.22636pt(D-2,1,1)\xleftarrow{\mu}(D-1,0,10)$ $\displaystyle(D-2,2,0)$
$\displaystyle\xrightarrow{2\delta}(D_{2},1,1),\hskip
14.22636pt(D-2,1,1)\xleftarrow{\mu}(D-2,2,0)$ $\displaystyle D_{2},1,1)$
$\displaystyle\xrightarrow{\delta}\mbox{DL}$

Taking into account that $\delta\ll\mu$ we get the following end-to-end
probabilities for the upper and lower paths.

$P_{u}\approx\frac{\delta}{\mu}\times\frac{2(D-1)\delta}{2\mu}\times\frac{\delta}{2\mu}=\frac{(D-1)\delta^{3}}{2\mu^{3}}$
$P_{ell}\approx\frac{2(D-1)\delta}{\mu}\times\frac{\delta}{\mu}\times\frac{\delta}{2\mu}=\frac{(D-1)\delta^{3})}{\mu^{3}}$
$P_{DL}=P_{u}+P_{\ell}\approx\frac{3(D-1)\delta^{3}}{2\mu^{3}}$

It is argued that the MTTDL is a product of two first device failures and the
expected number of first device failure events:

Given that $MTTDL\approx E[T]/P_{DL}$, where $E[T]=1/(N\delta)$. It follows
that $MTTDL\approx 1/(N\delta P_{DL})$ and noting that $N=2D$ we obtain:

$\displaystyle
MTTDL^{(approx)}_{RAID(5/1)}\approx\frac{\mu^{3}}{3D(D-1)\delta^{4}}=\frac{MTTF^{4}}{D(D-1)MTTR^{3}}$
(83)

###  14.7 Shortcut Reliability Analysis to compare RAID1/5 and RAID5/1

That RAID5/1 is more reliable than RAID1/5 as shown by the shortcut
reliability analysis in Thomasian 2006 [231]. We consider RAID with $N$ disks
and denote disk reliability with $r$.

$\displaystyle
R_{RAID1/5}=1-[1-R_{RAID5}]^{2}=1-[R^{N}+Nr^{N-1}(\bar{r})]^{2}.$ (84)

The reliability of RAID5 with mirrored disks can be expressed as:

$\displaystyle
R_{RAID5/1}=NR_{RAID1}^{N-1}-(N-1)R_{RAID}^{N}=N[1-(1-r)^{2}]^{N-1}-(N-1)[1-(\bar{r})^{2}]^{N}.$
(85)

For $N=3$ it easily follows that $RAID_{5/1}>R_{RAID1/5}$, since:
$R_{RAID5/1}-R_{RAID1/5}=6r^{2}(\bar{r})^{4}>0$. Rather than attempting to
show this for arbitrary $N$ we use the shortcut method setting
$r=1-\varepsilon$ in the above equations and retaining only the lowest power
of $\varepsilon$ we have:

$\displaystyle R_{RAID1/5}\approx
1-\frac{1}{4}N^{2}(N-1)\varepsilon^{4},\hskip 14.22636ptR_{RAID5/1}\approx
1-\frac{1}{2}N(N-1)\varepsilon^{4}.$

It is easy to see that $R_{RAID5/1}>R_{RAID1/5}$.

###  14.8 Reliability and Performance Comparison of Two Heterogeneous Disk
Arrays

We next utilize the asymptotic reliability analysis to compare the reliability
of two HDA configurations described in Section 10.11. The total number of
disks is $N=8$.

${\cal C}_{1}$: Vertical Disk Partitioning:

$n=2$ disks are dedicated to RAID1 and $N-n=6$ disks to RAID5.

${\cal C}_{2}$: Horizontal Disk Partitioning:

This is the HDA paradigm. RAID1 is allocated over $N=8$ disks, occupying $2/N$
or 25% of the space on each disk. The remaining space on $N$ disks is more
than adequate to hold the RAID5 array allocated on six disks in ${\cal
C}_{1}$, since the wider RAID5 array allocates less space to parity.
253253253RAID5 data (not parity) blocks are distributed over seven disks,
utilizing 5/7 or 72% of disk capacity, i.e., less than 75% of available space.

The reliability of RAID1/0 with $p$ disk pairs is
$R_{R1}(p)=[1-(1-r)^{2}]^{p}$, while the reliability of a RAID5 with $w$ disks
is $R_{R5}(w)=r^{w}+w(1-r)r^{w-1}$. We consider highly reliable disks, so that
$r=1-\epsilon$ with $\epsilon\ll 1$.

$R_{{\cal C}_{1}}=[1-(1-r)^{2}]\times[r^{6}+6r^{5}(1-r)]\approx
1-16\epsilon^{2}.$

$R_{{\cal C}_{2}}=\\{[1-(1-r)^{2}]^{4}\\}\times[r^{8}+8r^{7}(1-r)]\approx
1-32\epsilon^{2}.$

It follows that the ${\cal C}_{1}$ configuration is more reliable than ${\cal
C}_{2}$, since it tolerates two disk failures as long as long as they do not
affect the same array: RAID1 or RAID5. This reliability analysis is extensible
to more complicated cases.

In evaluating HDA performance we postulate an M/M/1 queueing system [122] with
Poisson arrivals and exponential service times, which has been utilized in
RAID5 performance studies [146]. Given an arrival rate $\lambda$ and mean disk
service time $\overline{x}_{d}$, the mean disk response time is
$R=\overline{x}_{d}/(1-\rho)$, where $\rho=\lambda\overline{x}_{d}$ is the
disk utilization factor.

The arrival rate of read requests to RAID1 and RAID5 arrays is $\Lambda_{R1}$
and $\Lambda_{R5}$, respectively. The mean response time for RAID1 with ${\cal
C}_{1}$ is: $R_{R1}=\overline{x}_{d}/(1-\rho)$, where the disk utilization is
$\rho=(\Lambda_{1}/2)\overline{x}_{d}$. The mean response time for RAID5 with
${\cal C}_{1}$ is $R_{R5}=\overline{x}_{d}/(1-\rho)$, where
$\rho=(\Lambda_{R5}/6)\overline{x}_{disk}$,

For ${\cal C}_{2}$ there are two components to disk utilization, since RAID1
and RAID5 disk arrays share disk space:
$\rho^{\prime}=[(\Lambda_{R1}+\Lambda_{R5})/N]\overline{x}_{d}$, so that
${R^{\prime}}_{R1}={R^{\prime}}_{R5}=\overline{x}_{d}/(1-\rho^{\prime})$. If
$\rho^{\prime}<\rho$ or $\Lambda_{R5}<(N/2-1)\Lambda_{R1}$ then
${R^{\prime}}_{R1}<R_{R1}$. For $N=8$ ${\cal C}_{2}$ will improve the RAID1
response time with respect to ${\cal C}_{1}$ for
$\Lambda_{R1}>\Lambda_{R5}/3$.

RAID1 response times in ${\cal C}_{2}$ can be improved by processing its
accesses at a higher priority than RAID5 accesses.
${R^{\prime\prime}}_{R1}=\overline{x}_{d}/(1-\rho^{\prime\prime})$, where
$\rho^{\prime\prime}=(\Lambda_{R1}/N)\overline{x}_{d}$, since only the disk
utilization due to RAID1 accesses affects ${R^{\prime\prime}}_{R1}$ [122]. For
${\cal C}_{1}$ with
$\rho^{\prime\prime}=(\Lambda_{R1}/2)\overline{x}_{disk}=0.8$,
$R_{R1}=\overline{x}_{d}/(1-0.8)=5\overline{x}_{d}$ and for ${\cal C}_{2}$
with ${\rho^{\prime\prime}}=n\times 0.8/N=0.2$ and
${R^{\prime\prime}}_{R1}=\overline{x}_{d}/(1-0.2)=1.25\overline{x}_{d}$, i.e.,
a 4-fold improvement.

### Abbreviations

AFR \- Annual Failure Rate, BER \- Bit Error Rate, BIBD \- Balanced Incomplete
Block Design, CTMC \- Continuous Time Markov Chain, DAC \- Disk Array
Controller, EAFDL \- Expected Annual Fraction of Data Loss, ECC \- Error
Correcting Code, FB \- Fixed Block (disks), HDFS \- Hadoop Distributed File
System, IOPS -Input/Output Per Second, IDR \- Intra-Disk Redundancy, kDFT \- k
Disk-Failure Tolerant, LRC \- Local Redundancy Code. LSE \- Latent Sector
Error, LST \- Laplace Stieltjes Transform, MDS \- Maximum Distance Separable,
ML \- Machine Learning, MTTDL \- Mean Time To Data Loss, MTTF \- Mean Time To
Failure, MTTR \- Mean Tine To Repair, NRP \- Nearly Random Permutation, NVMeoF
\- NVMe®over Fabrics (NVMe-oF™), NVRAM \- Non-Volatile Random Access Memory,
OLTP \- OnLine Transaction Processing, PUE \- Power Usage Effectiveness, RAID
\- Redundant Array of Inexpensive/Independent Disks, RDP \- Rotated Diagonal
Parity, RMW \- Read-Modify Write, RU \- Rebuild Unit, SCM \- Storage Class
Memory, SDC \- Silent Data Corruption, SLA/O \- Service Level
Agreement/Objective. SSD \- Solid State Disk, SU \- Stripe Unit, SWP \- Small
Write Penalty, TCO \- Total Cost of Ownership, UDE \- Undetected Disk Errors,
UPS \- Uninterruptible Power Supply, VSM \- Vacationing Server Model, XOR \-
eXclusive OR, ZBR \- Zoned Bit Recording, ZLA \- Zero Latency Access.