Therefore Equation (46) implies $\limsup_{\lambda\to
0}\lVert\hat{F}^{\lambda\pm}_{[t/\lambda]}-\hat{F}^{\pm}_{t}\rVert_{\infty}\leq\varepsilon$.
Since $\varepsilon>0$ is arbitrary, this concludes the proof of Theorem 1.9. ∎

###### Proof of Theorem 1.12.

Using the fact that $\mathcal{T}$ is a locally Lipschitz operator of
$(\mathbb{B},\lVert\cdot\rVert_{\infty})$, as mentioned in Remark 4.2, the
proof of (i) is the same as for the proof of Theorem 4.3.

By Theorem 4.4, we have for all $t\in[0,t^{*})$, where $t^{*}$ is the maximal
definition time of the ODE,

$\frac{\mathrm{d}}{\mathrm{d}{t}}\hat{F}_{t}=\mathcal{T}^{+}(\hat{F}^{+}_{t}-\hat{F}^{-}_{t})-\mathcal{T}^{-}(\hat{F}^{+}_{t}-\hat{F}^{-}_{t})=\mathcal{T}(\hat{F}_{t})$

in $L^{2}_{\mathbf{x}}$. By Proposition 3.7 (ii), we know that the convergence

$\lim_{s\to
t}\frac{\hat{F}^{\pm}_{t}-\hat{F}^{\pm}_{s}}{t-s}=\mathcal{T}^{\pm}(\hat{F}_{t})$

holds also in $\mathbb{B}$, which shows that
$\frac{\mathrm{d}}{\mathrm{d}{t}}\hat{F}_{t}=\mathcal{T}(\hat{F}_{t})$ holds
also in $\mathbb{B}$, concluding the proof of (ii). ∎

####  5.3.3 Proofs related to Section 4.4

###### Proof of Proposition 4.7.

  1. (i)

This monotonicity property is established in the proof of Theorem 4.3, see
Equation (32).

  2. (ii)

Because $L$ is convex and differentiable with respect to the second variable,
the initialization (8) implies that $\bar{r}_{t}=0$ at time $t=0$. Similarly
as in Equation (32), the derivative with respect to $t\geq 0$ is given by

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\bar{r}_{t}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathcal{T}(F_{t})(x_{i})\,\frac{\partial^{2}L}{\partial
z^{2}}(y_{i},\hat{F}_{t}(x_{i}))$
$\displaystyle=-\frac{1}{n}\mathbb{E}_{\zeta}\left[\sum_{v\in\\{0,1\\}^{d}}\sum_{i=1}^{n}\frac{\partial
L}{\partial z}(y_{i},\hat{F}_{t}(x_{i}))\mathds{1}_{A_{v}}(x_{i})\right]$
$\displaystyle=-\bar{r}_{t}.$ (47)

In the second line, for each term indexed by $v$, a factor
$\sum_{i=1}^{n}\frac{\partial L^{2}}{\partial
z^{2}}(y_{i},\hat{F}_{t}(x_{i}))\mathds{1}_{A_{v}}(x_{i})$ is canceling out.
The third line follows because the sum of all terms is equal to $\bar{r}_{t}$
and does not depend on the randomness $\zeta$.

Equation (47) implies that $\bar{r}_{t}=\bar{r}_{0}e^{-t}$. This is equal to
$0$ for initialization (8). Interestingly, a different initialization would
provide an exponentially fast decay of the residuals mean. ∎

The following Lemma will be used in the proof of Proposition 4.9.

######  Lemma 5.3.

Let $(x_{i},r_{i})_{1\leq i\leq n}$ and $(\beta,K,d)$ be fixed. Consider
$J\subset[\\![1,p]\\!]$ with $\lvert J\rvert\leq d$ and define

$A(h)=\\{x\in[0,1]^{p}\ :\ \forall j\in J,\,x^{j}<h^{j}\\},\quad
h\in[0,1]^{J}.$

Then for any $h_{0}\in[0,1]^{p}$ and $\varrho>0$, there exists $q>0$ such that

$P_{\beta,K}\big{(}A_{0}(\xi)=A(h)\mbox{ for some $h$ such that $\lVert
h-h_{0}\rVert_{\infty}\leq\varrho$}\big{)}\geq q,$

where $P_{\beta,K}$ is the splitting scheme distribution in Equation (21) and
$A_{0}(\xi)$ is the region containing $0$ in the partition associated to
$\xi$. Furthermore, the constant $q$ depends only on $p,\beta,K,d,\varrho$ and
$R:=\max_{i}\lvert r_{i}\rvert$.

###### Proof of Lemma 5.3.

We first consider the case $\beta=0$, i.e. $P_{\beta,K}=P_{0}$, and prove that
the event

$E_{h_{0},\varrho}=\left\\{A_{0}(\xi)=A(h)\mbox{ for some $h$ such that
$\lVert h-h_{0}\rVert_{\infty}\leq\varrho$}\right\\}$

satisfies $P_{0}(E_{h_{0},\varrho})\geq q$ with $q>0$ depending only on $p$,
$d$ and $\varrho$. Possibly shifting $h_{0}$ by a small distance and reducing
$\varrho$, we may assume without loss of generality that
$h_{0}\in[\varrho,1-\varrho]^{J}$. For simplicity, assume first that $\lvert
J\rvert=d$, and let $j_{1}<\dots<j_{d}$ be the increasing enumeration of $J$.
We recall the notation $\xi=(j_{v},u_{v})_{v\in\mathscr{T}_{d-1}}$ and observe
that the region $A_{0}(\xi)$ containing $0$ depends only of the values
$(j_{v},u_{v})$ for the $d$ leftmost nodes in $\mathscr{T}_{d-1}$ that we
denote by $v_{1},v_{2},\dots,v_{d}$. We then have

$\displaystyle P_{0}(E_{h_{0},\varrho})$
$\displaystyle\;\geq\;P_{0}\big{(}\forall
k\in[\\![1,d]\\!],\;j_{v_{k}}=j_{k}\text{ and
}u_{v_{k}}\in[h_{0}^{j_{k}}-\varrho,h_{0}^{j_{k}}+\varrho]\big{)}$
$\displaystyle\;=\;\Big{(}\frac{2\varrho}{p}\Big{)}^{d}\;=:\;q.$

This simple argument is adapted to the case when $\lvert J\rvert=r<d$ by
considering the sequence $j_{1}<\cdots<j_{r}=\ldots=j_{d}$ and noting that
$\xi\in E_{h_{0},\varrho}$ if and only if

$j_{v_{k}}=j_{k}\quad\mbox{and}\quad
u_{v_{k}}\in[h_{0}^{j_{k}}-\varrho,h_{0}^{j_{k}}+\varrho],\quad\mbox{for
$k=1,\ldots,r-1$,}$

and

$j_{v_{r}}=\cdots=j_{v_{d}}=j_{r},\quad\prod_{k=r}^{r}u_{v_{d}}\in[h_{0}^{j_{r}}-\varrho,h_{0}^{j_{r}}+\varrho].$

Further details are left to the reader.

Next we consider the case $\beta>0$. Since $P_{\beta,K}$ is absolutely
continuous with respect to $P_{0}$ according to Proposition 2.1, we can write

$P_{\beta,K}(E_{h_{0},\varrho})=\int_{E_{h_{0},\varrho}}\frac{\mathrm{d}P_{\beta,K}}{\mathrm{d}P_{0}}(\xi)\;P_{0}(\mathrm{d}\xi).$

We prove that the Radon-Nykodym derivative (21) is bounded from below by a
positive constant. By definition each of the
$\Delta(s^{k}_{v},u^{k}_{v};A_{v}(\xi))$ is a nonnegative polynomial with
degree $2$ in the $(r_{i})$ and with coefficients bounded by $2$. Therefore
there is a uniform bound

$0\leq\Delta(s^{k}_{v},u^{k}_{v};A_{v}(\xi))\leq C,$

where $C$ depends only on $R:=\max_{i}\lvert r_{i}\rvert$. This implies that
each factor in (21) satisfies

$\frac{\exp(\beta\operatorname{\Delta}(s_{v}^{1},u_{v}^{1};A_{v}(\xi)))}{\sum_{k=1}^{K}\exp(\beta\operatorname{\Delta}(s_{v}^{k},u_{v}^{k};A_{v}(\xi)))}\geq\frac{1}{1+(K-1)\mathrm{e}^{\beta
C}}.$

We deduce that the Radon-Nykodym derivative (21) is bounded from below by a
positive constant depending only on $\beta,K,d$ and $R$. Since
$P_{0}(E_{h_{0},\varrho})\geq q$, this yields a lower bound for
$P_{\beta,K}(E_{h_{0},\varrho})$ and concludes the proof. ∎

###### Proof of Proposition 4.9.

It is trivially checked that, for $F\in\mathbb{B}$, the nullity of the
residuals $r_{i}=\frac{\partial L}{\partial{z}}(y_{i},F(x_{i}))$ implies
$\mathcal{T}(F)=0$. We prove here the converse implication under assumption
$(A5)$. We consider $F\in\mathbb{B}$ such that $(r_{i})_{1\leq i\leq n}\neq
0$, and our goal is to show that $\mathcal{T}(F)\neq 0$.

Recall from (32) that we can write

$\sum_{i=1}^{n}\mathcal{T}(F)(x_{i})r_{i}=-\mathbb{E}_{\xi}\left[\sum_{v\in\\{0,1\\}^{d}}\frac{\big{(}\sum_{i=1}^{n}r_{i}\mathds{1}_{A_{v}}(x_{i})\big{)}^{2}}{\sum_{i=1}^{n}\frac{\partial^{2}L}{\partial{z}^{2}}(y_{i},F(x_{i}))\mathds{1}_{A_{v}}(x_{i})}\right].$

It is therefore sufficient to show that the sum under the expectation is not
null with positive probability. All the terms being nonnegative, we show that
the term corresponding to the region $A_{0}$ is positive with positive
probability. Consider the set of indices $i\in[\\![1,n]\\!]$ such that
$r_{i}\neq 0$, and among those, fix $i_{0}$ such that $x_{i_{0}}$ is minimal
for the lexicographic order on $[0,1]^{p}$. Under assumption $(A5)$, there is
$J$ such that the $(x_{i}^{J})_{i}$ are pairwise distinct, which ensures the
positivity of $\varrho=\min_{1\leq i_{1}<i_{2}\leq n}\lVert
x_{i_{1}}^{J}-x_{i_{2}}^{J}\rVert_{\infty}>0$. By definition of $i_{0}$ and
$\varrho$, for $h\in(x_{i_{0}}^{J},x_{i_{0}}^{J}+\varrho)$ (addition by
$\varrho$ meant componentwise), the region $A(h)$ contains only one point
$x_{i}$ corresponding to a non-null residual and this point is $x_{i_{0}}$.
Lemma 5.3 shows that

$P_{\beta,K}\big{(}A_{0}(\xi)=A(h)\text{ for some
}h\in(x_{i_{0}}^{J},x_{i_{0}}^{J}+\varrho)\big{)}>0.$

On this event, we have
$(\sum_{i=1}^{n}r_{i}\mathds{1}_{A_{0}}(x_{i}))^{2}=r_{i_{0}}^{2}>0$ and the
sum is positive. This implies that
$\sum_{i=1}^{n}\mathcal{T}(F)(x_{i})r_{i}\neq 0$ and hence $\mathcal{T}(F)\neq
0$. ∎

###### Proof of Proposition 4.11.

According to Proposition 4.7, the non-negative function $t\mapsto
L_{n}(\hat{F}_{t})$ is non-increasing. We denote by $\ell\geq 0$ its limit as
$t\to+\infty$ and we prove that $\ell=0$. We proceed by contradiction and
assume that $\ell>0$. Then we will prove below that

$\sup_{t\geq
0}\frac{\mathrm{d}}{\mathrm{d}t}L_{n}(\hat{F}_{t})\leq-\eta\qquad\text{for
some }\eta>0,$

whence $L_{n}(\hat{F}_{t})\leq L_{n}(\hat{F}_{0})-\eta t$, yielding a
contradiction because the function is non-negative.

We will use the following properties of $L_{n}$:

  1. (i)

for fixed $(y_{i})_{1\leq i\leq n}$ and $\ell_{1}>0$, there is a constant
$R>0$ such that $L_{n}(F)\leq\ell_{1}$ implies

$\max_{1\leq i\leq n}\big{\lvert}\frac{\partial
L}{\partial{z}}(y_{i},F(x_{i}))\big{\rvert}\leq R;$

  2. (ii)

for fixed $(y_{i})_{1\leq i\leq n}$ and $\ell_{0}>0$, there is a constant
$\delta>0$ such that $L_{n}(F)\geq\ell_{0}$ implies

$\max_{1\leq i\leq n}\big{\lvert}\frac{\partial
L}{\partial{z}}(y_{i},F(x_{i}))\big{\rvert}\geq\delta.$

The first point relies on the fact that $z\mapsto L(y,z)$ is convex and non-
negative for all $y$ (Assumption 1.8). The second point uses the fact that
$z\mapsto L(y,z)$ has infimum $0$ (Assumption $(A3)$); then
$L_{n}(F)\geq\ell_{0}$ implies $L(y_{i},F(x_{i}))\geq\ell_{0}/n$ for some $i$,
so that $F(x_{i})$ is far from the minimizer of the convex function $z\mapsto
L(y_{i},z)$ and the (non-increasing) derivative must be bounded away from $0$.

We let $\ell_{0}=\ell>0$ and $\ell_{1}=L_{n}(\hat{F}_{0})$. Note that
$\ell_{0}\leq L_{n}(\hat{F}_{t})\leq\ell_{1}$ for all $t\geq 0$ so that we can
make use of the bound (i) and (ii) above. By (32),
$\frac{\mathrm{d}}{\mathrm{d}t}L_{n}(\hat{F}_{t})=\sum_{i}\mathcal{T}(\hat{F}_{t})(x_{i})r_{i}$
where

$\sum_{i=1}^{n}\mathcal{T}(\hat{F}_{t})(x_{i})r_{i}=-\mathbb{E}_{\xi}\left[\sum_{v\in\\{0,1\\}^{d}}\frac{\big{(}\sum_{i=1}^{n}r_{i}\mathds{1}_{A_{v}}(x_{i})\big{)}^{2}}{\sum_{i=1}^{n}\frac{\partial^{2}L}{\partial{z}^{2}}(y_{i},F(x_{i}))\mathds{1}_{A_{v}}(x_{i})}\right],$

where we use again, for conciseness, the notation $r_{i}=\frac{\partial
L}{\partial{z}}(y_{i},\hat{F}_{t}(x_{i}))$. We need to provide a lower bound
for $\sum_{i=1}^{n}\mathcal{T}(F)(x_{i})r_{i}$ when $\ell_{0}\leq
L_{n}(F)\leq\ell_{1}$ and use a similar argument as in the proof of
Proposition 4.9. Let $J$ be the set of coordinates appearing in $(A5)$ and set
$\varrho=\frac{1}{2}\min_{i_{1}\neq i_{2}}\lVert
x_{i_{1}}^{J}-x_{i_{2}}^{J}\rVert_{\infty}>0$. Consider the sets

$A(h)=\\{x\in[0,1]^{p}\ :\ x^{j}<h^{j}\text{ for all }j\in J\\},\quad
h\in[0,1]^{J}.$

By (ii) above, $L_{n}(F)\geq\ell_{0}$ implies that there is an index $i_{0}$
such that $\lvert r_{i_{0}}\rvert\leq\delta$. Introducing the function

$S(h)=\sum_{i=1}^{n}r_{i}\mathds{1}_{A(h)}(x_{i}),$

we have

$r_{i_{0}}=\sum_{v\in\\{-1,1\\}^{J}}\sigma_{v}S(x_{i}+\varrho
v)\quad\text{with}\quad\sigma_{v}=(-1)^{\sum_{k}\mathds{1}_{v_{k}=-1}}.$ (48)

This is due to the fact that $S$ is a tree function on $[0,1]^{J}$ with
$\mu_{S}=\sum_{i=1}^{n}r_{i}\delta_{x_{i}^{J}}$ and that $x_{i_{0}}^{J}$ is
the only atom in the hypercube $[x_{i_{0}}^{J}-\varrho,x_{i_{0}}^{J}+\varrho]$
— addition by $\varrho$ meant componentwise. Then the bound
$r_{i_{0}}\geq\delta$ together with Equation (48) imply that

$\lvert S(x_{i_{0}}+\varrho v)\rvert\geq 2^{-\lvert J\rvert}\lvert
r_{i_{0}}\rvert\geq 2^{-d}\delta$

for some $v\in\\{-1,1\\}^{J}$ . Furthermore, by construction we have
$S(h)=S(x_{i}+\varrho v)$ for all $h$ such that $\lVert
h-x_{i_{0}}^{J}-\varrho v\rVert_{\infty}<\varrho$. Now we use Lemma 5.3 to
bound from below the probability of the event

$E=\\{A_{0}(\xi)=A(h)\;\mbox{for some
$h\in[x_{i_{0}}^{J}-\varrho,x_{i_{0}}^{J}+\varrho]$}\\}$

More precisely, we have $P_{\beta,K}(E)\geq q>0$, where $q$ depends only on
$p,\beta,K,d,\varrho$ and $R\geq\max_{i}\lvert r_{i}\rvert$. By point (i)
above, $R$ depends on $\ell_{1}$ but not on $F$ satisfying
$L_{n}(F)\leq\ell_{1}$. On the event $E$, we have
$\big{(}\sum_{i=1}^{n}r_{i}\mathds{1}_{A(h)}\big{)}^{2}\geq 4^{-d}\delta^{2}$
and, by $(A4)$,

$\sum_{i=1}^{n}\frac{\partial^{2}L}{\partial{z}^{2}}(y_{i},F(x_{i}))\mathds{1}_{A(h)}\leq
nC,$

where $C$ depends only on $R$ and the $(y_{i})$. Therefore on the event $E$,
we have

$\frac{\big{(}\sum_{i=1}^{n}r_{i}\mathds{1}_{A(h)}\big{)}^{2}}{\sum_{i=1}^{n}\frac{\partial^{2}L}{\partial{z}^{2}}(y_{i},F(x_{i}))\mathds{1}_{A(h)}}\geq\frac{4^{-d}\delta^{2}}{nC},$

whence we deduce

$\mathbb{E}_{\xi}\left[\sum_{v\in\\{0,1\\}^{d}}\frac{\big{(}\sum_{i=1}^{n}r_{i}\mathds{1}_{A_{v}}(x_{i})\big{)}^{2}}{\sum_{i=1}^{n}\frac{\partial^{2}L}{\partial{z}^{2}}(y_{i},F(x_{i}))\mathds{1}_{A_{v}}(x_{i})}\right]\geq
q\frac{4^{-d}\delta^{2}}{nC}>0.$

This proves that $L_{n}(\hat{F}_{t})\to 0$. It follows that
$L(y_{i},\hat{F}_{t}(x_{i}))\to 0$ for all $i$. Since $0$ is the infimum of
the convex function $z\mapsto L(y_{i},z)$, the convergence $\frac{\partial
L}{\partial{z}}(y_{i},\hat{F}_{t}(x_{i}))\to 0$ holds for the derivative as
well, ending the proof. ∎

Our proof of Proposition 4.12 relies on the following lemma.

######  Lemma 5.4.

For all $F\in\mathbb{B}$, $\mathcal{T}(F)\in\mathbb{W}$ and the mapping
$\mathcal{T}:(\mathbb{B},\lVert\cdot\rVert_{\infty})\rightarrow(\mathbb{W},\lVert\cdot\rVert_{W})$
is locally Lipschitz. Furthermore, the same is true for $\mathcal{T}^{+}$ and
$\mathcal{T}^{-}$.

Similarly as in Remark 4.2, the inclusion $\mathbb{W}\subset\mathbb{B}$ with
norm inequality $\lVert F\rVert_{\infty}\leq\pi_{0}([0,1]^{p})\lVert
F\rVert_{\mathbb{W}}$ for all $F\in\mathbb{W}$ implies that $\mathcal{T}$ can
be seen as a locally Lipschitz operator on
$(\mathbb{W},\lVert\cdot\rVert_{\mathbb{W}})$.

###### Proof of Lemma 5.4.

We consider only the proof for $\mathcal{T}$ which is easily adapted for
$\mathcal{T}^{+}$ and $\mathcal{T}^{-}$ by considering the positive and
negative part of the gradient trees. It is enough to prove the following
properties:

  1. (i)

for all $F\in\mathbb{B}$, there is $M\geq 0$ such that

$|\mu_{\mathcal{T}(F)}(A)|\leq M\pi_{0}(A),\quad\mbox{for all borel set
$A\subset[0,1]^{p}$};$

  2. (ii)

for all $R>0$, there exists $M\geq 0$ such that for all $F$ and
$F^{\prime}\in\mathbb{B}$ satisfying $\max(\lVert F\rVert_{\infty},\lVert
F^{\prime}\rVert_{\infty})\leq R$,

$|\mu_{\mathcal{T}(F)}(A)-\mu_{\mathcal{T}(F^{\prime})}(A)|\leq M\lVert
F-F^{\prime}\rVert_{\infty}\pi_{0}(A),\quad\mbox{for all borel set
$A\subset[0,1]^{p}$}.$

Proof of (i). According to Proposition 3.2 and its proof, for each splitting
scheme $\xi$, the measure associated to the gradient tree
$\widetilde{T}(\,\cdot\,;F,\xi)$ is a point measure with atoms at the vertices
in $[0,1)^{p}$ of the partition $(A_{v}(\xi))_{v\in\\{0,1\\}^{d}}$ and each
atom has a mass with absolute value less than
$\|\widetilde{T}(\,\cdot\,;F,\xi)\|_{\mathrm{TV}}$. By the definition of
$\pi_{\xi}$, this implies

$\mu_{\widetilde{T}(\,\cdot\,;F,\xi)}\ll\pi_{\xi}\quad\mbox{with
}\Big{|}\frac{\mathrm{d}\mu_{\widetilde{T}(\,\cdot\,;F,\xi)}}{\mathrm{d}\pi_{\xi}}(x)\Big{|}\leq\|\widetilde{T}(\,\cdot\,;F,\xi)\|_{\mathrm{TV}}\leq
C,$

for some $C>0$ that depends only on $\lVert F\rVert_{\infty}$ — this last
inequality is a consequence of Equations (30) with $F^{\prime}=0$. We deduce

$\displaystyle|\mu_{\mathcal{T}(F)}(A)|$
$\displaystyle=\Big{|}\int\mu_{\widetilde{T}(\,\cdot\,;F,\xi)}(A)\,P_{\beta,K}(\mathrm{d}\xi)\Big{|}$
$\displaystyle\leq\int\Big{(}\int_{A}\Big{|}\frac{\mathrm{d}\mu_{\widetilde{T}(\,\cdot\,;F,\xi)}}{\mathrm{d}\pi_{\xi}}(x)\Big{|}\,\pi_{\xi}(\mathrm{d}x)\Big{)}\,\frac{\mathrm{d}P_{\beta,K}}{\mathrm{d}P_{0}}(\xi)\,P_{0}(\mathrm{d}\xi)$
$\displaystyle\leq\int
C\,\pi_{\xi}(A)\,\frac{\mathrm{d}P_{\beta,K}}{\mathrm{d}P_{0}}(\xi)\,P_{0}(\mathrm{d}\xi).$

Since $\frac{\mathrm{d}P_{\beta,K}}{\mathrm{d}P_{0}}(\xi)\leq K^{2^{d}-1}$
according to Equation (21), we get

$\displaystyle|\mu_{\mathcal{T}(F)}(A)|$ $\displaystyle\leq
CK^{2^{d}-1}\int\pi_{\xi}(A)\,P_{0}(\mathrm{d}\xi)$
$\displaystyle=CK^{2^{d}-1}\pi_{0}(A).$

We deduce $\mu_{\mathcal{T}(F)}\ll\pi_{0}$ with Radon-Nykodym derivative
bounded by $CK^{2^{d}-1}$, so that $\mathcal{T}(F)\in\mathbb{W}$.

Proof of (ii). With similar notation as in the proof of Proposition 4.1, we
compute

$\displaystyle|\mu_{\mathcal{T}(F)}(A)-\mu_{\mathcal{T}(F^{\prime})}(A)|$
$\displaystyle\leq$
$\displaystyle\int\Big{(}\int_{A}\Big{|}\frac{\mathrm{d}\mu_{\widetilde{T}(\,\cdot\,;F,\xi)}}{\mathrm{d}\pi_{\xi}}(x)-\frac{\mathrm{d}\mu_{\widetilde{T}(\,\cdot\,;F^{\prime},\xi)}}{\mathrm{d}\pi_{\xi}}(x)\Big{|}\pi_{\xi}(\mathrm{d}x)\Big{)}\,\frac{\mathrm{d}P_{\beta,K}}{\mathrm{d}P_{0}}(\xi)P_{0}(\mathrm{d}\xi)$
$\displaystyle\quad+\int\Big{(}\int_{A}\Big{|}\frac{\mathrm{d}\mu_{\widetilde{T}(\,\cdot\,;F^{\prime},\xi)}}{\mathrm{d}\pi_{\xi}}(x)\Big{|}\pi_{\xi}(\mathrm{d}x)\Big{)}\,\Big{|}\frac{\mathrm{d}P_{\beta,K}}{\mathrm{d}P_{0}}(\xi)P_{0}(\mathrm{d}\xi)-\frac{\mathrm{d}P_{\beta,K}^{\prime}}{\mathrm{d}P_{0}}(\xi)\Big{|}P_{0}(\mathrm{d}\xi)$
$\displaystyle\leq$
$\displaystyle\int\Big{(}\int_{A}\lVert\widetilde{T}(\,\cdot\,;F,\xi)-\widetilde{T}(\,\cdot\,;F^{\prime},\xi)\rVert_{\mathrm{TV}}\,\pi_{\xi}(\mathrm{d}x)\Big{)}\,\frac{\mathrm{d}P_{\beta,K}}{\mathrm{d}P_{0}}(\xi)P_{0}(\mathrm{d}\xi)$
$\displaystyle\quad+\int
C\pi_{\xi}(A)\,\Big{|}\frac{\mathrm{d}P_{\beta,K}}{\mathrm{d}P_{0}}(\xi)P_{0}(\mathrm{d}\xi)-\frac{\mathrm{d}P_{\beta,K}^{\prime}}{\mathrm{d}P_{0}}(\xi)\Big{|}P_{0}(\mathrm{d}\xi)$
$\displaystyle\leq$
$\displaystyle\;(4^{d}CK^{2^{d}-1}+CR)\|F-F^{\prime}\|_{\infty}\pi_{0}(A),$

where the constant $C$ depends on $R$ but not on $F$ or $F^{\prime}$. The last
inequality relies on Equations (30) and (26). ∎

###### Proof of Proposition 4.12.

We consider the proof for $(\hat{F}_{t})_{t\geq 0}$ only since it can be
easily adapted to $(\hat{F}_{t}^{+})_{t\geq 0}$ and $(\hat{F}_{t}^{-})_{t\geq
0}$. By Theorem 4.3, infinitesimal gradient boosting is a solution of the ODE
(18) in the space $(\mathbb{T},\lVert\cdot\rVert_{\mathrm{TV}})$ so that

$\hat{F}_{t}=\hat{F}_{0}+\int_{0}^{t}\mathcal{T}(\hat{F}_{s})\,\mathrm{d}s,\quad
t\geq 0.$

By Lemma 5.4, $\mathcal{T}$ takes its value in $\mathbb{W}\subset\mathbb{T}$
and, since $\hat{F}_{0}\in\mathbb{W}$, it implies that
$\hat{F}_{t}\in\mathbb{W}$ for all $t\geq 0$. Furthermore,
$\mathcal{T}:\mathbb{W}\to\mathbb{W}$ is locally Lipschitz so that
$(\hat{F}_{t})_{t\geq 0}$ is the unique solution of the ODE (18) in
$(\mathbb{W},\lVert\cdot\rVert_{\mathbb{W}})$. Therefore infinitesimal
gradient boosting defines a smooth path in $\mathbb{W}$. ∎

## References

  * Biau and Cadre, (2021) Biau, G. and Cadre, B. (2021).  Optimization by gradient boosting.  In Advances in contemporary statistics and econometrics—Festschrift in honor of Christine Thomas-Agnan, pages 23–44. Springer, Cham.  doi:10.1007/978-3-030-73249-3_2.
  * Billingsley, (1995) Billingsley, P. (1995).  Probability and measure.  Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons, Inc., New York, third edition.  A Wiley-Interscience Publication.
  * Billingsley, (1999) Billingsley, P. (1999).  Convergence of probability measures.  Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons, Inc., New York.  doi:10.1002/9780470316962, second edition.  A Wiley-Interscience Publication.
  * Billingsley and Topsøe, (1967) Billingsley, P. and Topsøe, F. (1967).  Uniformity in weak convergence.  Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 7:1–16.  doi:10.1007/BF00532093.
  * Blanchard et al., (2004) Blanchard, G., Lugosi, G., and Vayatis, N. (2004).  On the rate of convergence of regularized boosting classifiers.  J. Mach. Learn. Res., 4(5):861–894.  doi:10.1162/1532443041424319.
  * Breiman, (2004) Breiman, L. (2004).  Population theory for boosting ensembles.  Ann. Statist., 32(1):1–11.  doi:10.1214/aos/1079120126.
  * Breiman et al., (1984) Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984).  Classification and Regression Trees.  Chapman & Hall.  doi:10.1201/9781315139470.
  * Bühlmann and Yu, (2003) Bühlmann, P. and Yu, B. (2003).  Boosting with the $L_{2}$ loss: regression and classification.  J. Amer. Statist. Assoc., 98(462):324–339.  doi:10.1198/016214503000125.
  * Chen and Guestrin, (2016) Chen, T. and Guestrin, C. (2016).  XGBoost: A scalable tree boosting system.  In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785–794, San Francisco California USA. ACM.  doi:10.1145/2939672.2939785.
  * Diestel and Uhl, (1977) Diestel, J. and Uhl, J. J. (1977).  Vector Measures, volume 15 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, Rhode Island.  doi:10.1090/surv/015.
  * Dombry and Esstafa, (2020) Dombry, C. and Esstafa, Y. (2020).  Behaviour of linear $l^{2}$-boosting algorithm in the vanishing learning rate asymptotic.  arXiv:2012.14657.  preprint.
  * Ethier and Kurtz, (1986) Ethier, S. N. and Kurtz, T. G., editors (1986).  Markov Processes.  Wiley Series in Probability and Statistics. John Wiley & Sons, Inc., Hoboken, NJ, USA.  doi:10.1002/9780470316658.
  * Freund and Schapire, (1999) Freund, Y. and Schapire, R. (1999).  Adaptive game playing using multiplicative weights.  volume 29, pages 79–103.  doi:10.1006/game.1999.0738.  Learning in games: a symposium in honor of David Blackwell.
  * Friedman et al., (2000) Friedman, J., Hastie, T., and Tibshirani, R. (2000).  Additive logistic regression: a statistical view of boosting.  Ann. Statist., 28(2):337–407.  doi:10.1214/aos/1016218223.  With discussion and a rejoinder by the authors.
  * Friedman, (2001) Friedman, J. H. (2001).  Greedy function approximation: a gradient boosting machine.  Annals of statistics, pages 1189–1232.  doi:10.1214/aos/1013203451.
  * Friedman, (2002) Friedman, J. H. (2002).  Stochastic gradient boosting.  Computational statistics & data analysis, 38(4):367–378.  doi:10.1016/S0167-9473(01)00065-2.
  * Geurts et al., (2006) Geurts, P., Ernst, D., and Wehenkel, L. (2006).  Extremely randomized trees.  Machine Learning, 63(1):3–42.  doi:10.1007/s10994-006-6226-1.
  * Hastie et al., (2009) Hastie, T., Tibshirani, R., and Friedman, J. (2009).  The Elements of Statistical Learning: Data mining, inference, and prediction.  Springer Series in Statistics. Springer, New York.  doi:10.1007/978-0-387-84858-7, second edition.
  * Jiang, (2004) Jiang, W. (2004).  Process consistency for AdaBoost.  Ann. Statist., 32(1):13–29.  doi:10.1214/aos/1079120128.
  * Lugosi and Vayatis, (2004) Lugosi, G. and Vayatis, N. (2004).  On the Bayes-risk consistency of regularized boosting methods.  Ann. Statist., 32(1):30–55.  doi:10.1214/aos/1079120129.
  * Métivier, (1982) Métivier, M. (1982).  Semimartingales: A Course on Stochastic Processes.  De Gruyter, Berlin, New York.  doi:10.1515/9783110845563.
  * Neuhaus, (1971) Neuhaus, G. (1971).  On weak convergence of stochastic processes with multidimensional time parameter.  The Annals of Mathematical Statistics, 42(4):1285–1295.  doi:10.1214/aoms/1177693241.
  * Ridgeway, (2007) Ridgeway, G. (2007).  Generalized boosting models: a guide to the gbm package.  url: https://cran.r-project.org/web/packages/gbm/vignettes/gbm.pdf.
  * Zhang and Yu, (2005) Zhang, T. and Yu, B. (2005).  Boosting with early stopping: convergence and consistency.  Ann. Statist., 33(4):1538–1579.  doi:10.1214/009053605000000255.


# Enabling Efficient RDMA-based Synchronous Mirroring
of Persistent Memory Transactions

Arash Tavakkol1 Aasheesh Kolli2,3 Stanko Novakovic2 Kaveh Razavi1,4 Juan
Gómez-Luna1
Hasan Hassan1 Claude Barthels1 Yaohua Wang1 Mohammad Sadrosadati1 Saugata
Ghose5
Ankit Singla1 Pratap Subrahmanyam2 Onur Mutlu1,5
1ETH Zürich 2VMware 3The Pennsylvania State University 4Vrije Universiteit
Amsterdam 5Carnegie Mellon University

###### Abstract

Synchronous Mirroring (SM) is a standard approach to building highly-available
and fault-tolerant enterprise storage systems. SM ensures strong data
consistency by maintaining multiple exact data replicas and synchronously
propagating every update to all of them. Such strong consistency provides
fault tolerance guarantees and a simple programming model coveted by
enterprise system designers. For current storage devices, SM comes at modest
performance overheads. This is because performing both local and remote
updates simultaneously is only marginally slower than performing just local
updates, due to the relatively slow performance of accesses to storage (e.g.,
hard drives, flash-based solid-state drives) in today’s systems. However,
emerging persistent memory (or storage class memory) and ultra-low-latency
network technologies necessitate a careful re-evaluation of the existing SM
techniques, as these technologies present fundamentally different latency
characteristics compared to their traditional counterparts. In addition to
that, existing low-latency network technologies, such as Remote Direct Memory
Access (RDMA), provide limited ordering guarantees and do not provide
durability guarantees necessary for SM.

To evaluate the performance implications of RDMA-based SM, we develop a
rigorous testing framework that is based on emulated persistent memory. Our
testing framework makes use of two different tools: (i) a configurable
microbenchmark and (ii) a modified version of the WHISPER benchmark suite,
which comprises a set of common cloud applications, with support for SM over
RDMA. Using this framework, we find that recently proposed RDMA primitives,
such as remote commit, provide correctness guarantees, but do not take full
advantage of the asynchronous nature of RDMA hardware. To this end, we propose
new primitives enabling efficient and correct SM over RDMA, and use these
primitives to develop two new techniques delivering high-performance SM of
persistent memories. Overall, we find that our two SM designs outperform the
remote commit based design by 1.8x and 2.9x, respectively.

##  1 Introduction

Enterprise applications require high-availability and durability guarantees.
User data loss or service downtime can have significant economic impact or
even lead to bankruptcy. For example, JournalSpace has been shut down due to a
complete loss of the company’s main database [56]. In August 2013, Amazon
services stopped operating for a few minutes and the company lost millions of
dollars in revenue [19]. In such situations, it is of essence for any company
to ensure that they can keep serving their users by relying on a different
copy of the user data. To provide such uninterruptible business continuity,
most companies maintain multiple copies of data in different failure domains.

Synchronous Mirroring (SM) is one of the most widely used approaches to
building highly-available storage systems for the enterprise. Technologies
like RAID 1, EMC MirrorView/S [18], VMware vSAN [58], IBM Metro Mirror [24],
and NetApp SnapMirror [46] provide synchronous mirroring over short distances
to ensure high availability and disaster recovery. SM guarantees strong
consistency of data by employing (at least) a pair of replica servers that
host an exact copy of the application data. SM ensures that in the rare event
of a failure, the application can rely on another active replica to continue
seamless operation using the _most recent version_ of the data. To provide
such a guarantee, the underlying system has to propagate _each_ data update
_synchronously_ to all of the replicas. Unlike more weakly-consistent systems,
such as asynchronous mirroring (AM), SM (1) guarantees zero data loss; and (2)
takes advantage of a simplified programming model, since the programmer does
not need to worry about reading an out-of-date replica.

Existing enterprise systems prefer to provide SM instead of weakly-consistent
techniques such as AM, even though the weakly-consistent techniques lower
performance overheads [18, 58, 24, 46]. This is because in existing systems,
the additional overhead of performing SM in place of techniques such as AM is
relatively small [62]. The small overhead is a result of the relatively small
latency difference between a local update and a remote update today. In
systems that use off-the-shelf magnetic hard disk drives (HDDs) and Ethernet
controllers, waiting for a remote update via Ethernet does not take
significantly longer than a local update to the HDD. While the relative cost
of a remote update over Ethernet increases when the local system uses a solid-
state drive consisting of NAND flash memory, prior work [33] has proposed
domain-specific operating systems and network stacks that greatly reduce the
round-trip latency for a remote update. As a result, the additional overhead
of SM over AM remains insignificant in systems with SSDs.

Unfortunately, persistent memory technologies such as PCM, MRAM, ReRAM, and
Intel’s 3D XPoint [37, 36, 65, 29] make it much more difficult to close the
gap. These persistent memories are expected to replace traditional storage
devices (HDDs/NAND flash based SSDs) in the near future [53, 13, 48], and are
orders of magnitude faster than current storage media (100,000X faster than
HDDs and 1000X faster than SSDs [53]). Since local updates will take much less
time with storage class memory, remote SM updates will become even more
expensive relative to local updates. Without significant innovation on the
remote update latency, it will become increasingly more difficult to amortize
and justify the additional overhead of SM over AM.

A promising approach to maintaining the viability of SM for persistent memory
is to make use of high-performance networks such as Infiniband [42], which are
already becoming commonplace in modern datacenters [68, 47]. Prior works [15,
59, 67, 53] have already proposed to combine fast Remote Direct Memory Access
(RDMA) or Infiniband with the emerging memories to improve the efficiency of
SM, but these works do not perform a detailed study of how these remote access
protocols affect the latency trade-offs between the remote access, local
access, and application performance.

Our goal is to understand the performance implications of using RDMA to
provide SM for storage class memory, which we refer to as _memory-level SM_
(SM hence forth), and propose new hardware primitives that will enable more
efficient memory-level SM. RDMA requires a specialized RDMA-enabled Network
Interface Card (RNIC). Applications access the local RNIC directly from user-
space to schedule read and write commands to the remote RNICs. The end-to-end
latency of RDMA operations depends on the complex interplay between the
workload characteristics, processor architecture, and RNIC architecture.
Finally, even though RNIC sits on the PCIe bus, it is capable of writing and
reading from the CPU cache directly using Intel’s Data Direct Input Output
(DDIO) technology [27]. However, because the CPU cache resides outside of the
persistence domain [51], enforcing durability in RDMA-based SM is a challenge.

We develop a rigorous testing framework to evaluate memory-level SM using RDMA
over an Infiniband network. Our workloads consist of (1) a configurable
transaction microbenchmark and (2) applications from the _WHISPER_ [44]
benchmark suite that have been extended with support for SM over RDMA. Using
our framework and workloads, we find that an SM design that uses the recently
proposed remote commit (_rcommit_) primitive [54] is unable to take full
advantage of the asynchronous nature of the RDMA hardware. We find that
_rcommit_ is an expensive primitive because it is overloaded to provide both
ordering and durability of SM updates. And that significant performance gains
can be made by developing separate primitives for ordering and durability and
using only the appropriate primitive. Similar insight has been used to improve
the performance of single-node persistent memory systems [44, 48] and file
systems [12].

Inspired by our analysis, we design a new set of RDMA hardware primitives
(i.e., _verbs_): remote ordering fence, remote durability fence, remote write-
through, and remote non-temporal writes. These new RDMA primitives aim to
unleash the full potential of RDMA hardware and enable efficient memory-level
SM. To showcase the new primitives, we propose two SM techniques, one based on
ordered buffering, which leverages ordering, durability fences and remote
write-through; and another one based on non-temporal writes and the implicit
ordering guarantees provided by modern RDMA hardware.

We use our framework to evaluate the effectiveness of our new SM techniques.
We find that the techniques provide much greater performance for memory-level
SM than remote commit based SM. On average across our benchmarks, we find that
our techniques improve the program execution time by 1.8x and 2.9x and the
throughput by 1.9x and 3.4x, respectively. Thus, we argue that new primitives
allowing for asynchronous updates, such as non-temporal remote writes, will be
necessary for efficient SM over RDMA.

We make the following contributions in this work:

  * •

We conduct a detailed study of RDMA-based synchronous mirroring of persistent
memory using the existing remote commit verb. We find that remote commit verb
does not take full advantage of the RDMA capabilities.

  * •

We identify that remote commit is inefficient as it is overloaded to provide
both ordering and durability of SM updates. And that by developing separate
primitives for ordering and durability we can significantly reduce the
overheads of SM.

  * •

We propose a new set of hardware primitives that are key to performing SM
efficiently: remote ordering fence, remote durability fence, remote write-
through, and remote non-temporal writes.

  * •

We use our new primitives to develop two new SM techniques that our techniques
significantly outperform RDMA-based SM using the remote commit verb.

  * •

We design and implement a benchmark suite comprising of an RDMA microbenchmark
and a version of the WHISPER benchmark suite that has been extended for
memory-level RDMA-based SM.

##  2 Background

###  2.1 Persistent Memories

The emerging non-volatile memory technologies (e.g., PCM [37] and Intel 3D
XPoint [61]) provide DRAM-like performance combined with disk-like durability
[13, 37, 48]. These new memory technologies can be used to store and
manipulate persistent data directly in-memory. Such systems, referred to as
persistent memory systems, have the potential to revolutionize how we manage
persistent data and have sparked a wide variety of exciting research recently
[30, 45, 57, 13, 17, 64, 60, 66, 3, 49, 11, 2, 55, 63, 38, 34].

Persistent software running on persistent memory systems requires in-memory
data to be recoverable across system failures. Ensuring recoverability
requires programmers to have control over the order in which writes/updates
reach the data in memory [48, 12]. However, in the presence of system failures
(power outages, application/kernel crashes, etc.) today’s systems do not
provide any guarantees on the order in which writes reach persistent memory
due to performance optimizations, like write back caching and memory
controller reordering, which coalesce and reorder writes to persistent memory.
For example, consider adding a new node to a persistent linked list in memory.
The linked list can become inconsistent during an insertion operation if a
power failure happens after the pointer to the new node has been persisted in
memory, but the write that fills the new node with valid data did not persist
in memory. The recovery process of the linked list would observe a node with
garbage values. To ensure ordered updates, all the way to persistent memory,
programmers have rely on a _memory persistency model_ [48] and annotate their
programs with appropriate low-level primitives, like Intel’s $clwb$ [26]
instruction.

###  2.2 Synchronous Mirroring

To guarantee high availability and durability of business-critical and
mission-critical data, system designers employ some form of data replication.
SM is a commonly used replication strategy where multiple replicas are kept in
sync by propagating every update to all the replicas simultaneously, and is a
feature on many commercial storage platforms [18, 58, 24, 46]. In this paper,
we limit ourselves to studying a variant of SM that involves only two
replicas. All the updates originate at the primary server and are propagated
to both local media and to the replica. However, the insights gained from our
work can be applied to a much broader class of replication strategies.

Storage-level SM has minimal performance overhead on the system, because
storage write occupies significant portion of the latency of the entire
persistent update operation (even the remote update) [39].

For memory-level SM, to perform a persistent update, along with issuing a
write to local persistent memory (i), the DMA engine fetches the data from the
cache (ii) and sends a write request to the replica over the network (iii).
Upon receiving the request, the replica server performs a persistent memory
write (iv) and then sends back an acknowledgement to the main server (v),
completing the persistent update. Since local persistent memory writes are
much faster than remote writes (100s of ns vs 1000s of us [53]), the overheads
of memory-level SM (over a baseline of just local updates) are prohibitive.
Storage-level SM (i.e., mirroring hard disks or SSDS) does not face the same
problem because storage write occupies significant portion of the latency of
the entire persistent update operation (even the remote update) [39]. To make
memory-level SM feasible, system designers need to employ ultra-low latency
networks. Next, we present an overview of RDMA, the ultra-low latency network
protocol of choice in modern datacenters.

###  2.3 RDMA

Remote Direct Memory Access (RDMA) is a mechanism enabling a user-level
program to directly access the memory of another computer, without
interrupting the processors. There are several existing networks that provide
support for RDMA, of which the two most widely used are Infiniband [43] and an
implementation using Converged Ethernet. InfiniBand (IB) [43] is a complete
network stack consisting of specialized transport, network, link, and physical
layers. IB is commonly used in high-performance computing environments and is
now making inroads into datacenters. IB offers low-latency and high-throughput
communication, as it is implemented entirely in hardware and allows for kernel
bypass.

RDMA over InfiniBand requires special network gear, including a specialized
switch, the links, and _Host Channel Adapters (HCA)_ or _RDMA Network
Interface Card (RNIC)_. For many RDMA applications it is important that the
network can guarantee reliable delivery, meaning packets should not be dropped
at any point in time. The RNIC implements the entire network stack in
hardware, allowing user-level programs to directly interact with the
controller and request remote operations. In existing RNIC implementation, the
memory that is exposed to another server must be first _registered_ with the
RNIC [43]. A portion of main memory that has been registered is referred to as
a _memory region_. During registration, the RNIC device driver pins the memory
region in order to guarantee that this memory never gets swapped out from
physical memory and thus is always accessible for RDMA operations.
Registration also makes the virtual-to-physical address translation
information (i.e., the page tables) accessible to the RNIC. A special copy of
the page table entries that is designated for the RNIC is called _Memory
Translation Table_ (MTT). MTT entries reside in memory and are buffered in the
HCA cache.

User applications initiate RDMA transfers by sending their requests directly
to the RNIC using the _verbs_ API. There are two categories of verbs:
_messaging verbs_ and _memory verbs_. These categories differ in terms of
semantics and required inter-process synchronization. In this work, we limit
our study to memory verbs due to their lower overheads. Memory verbs are
called _one-sided_ operations since the execution of the remote read and write
operations does not involve the CPU on the target machine. The lack of CPU
overhead at the responder makes one-sided verbs attractive; they provide the
lowest latency and highest throughput among all verbs [32]. In this work, we
use one-sided RDMA writes to implement synchronous mirroring.

RNICs have been designed to be compatible with commodity servers while, at the
same time, providing a low-overhead hardware-software interface. RNIC connects
with the rest of the server components using the PCIe bus, where the CPU
communicates with the RNIC using PCIe commands. The RNIC uses the PCIe bus to
DMA to and from local memory. Most recently, Intel introduced the _Data Direct
I/O Access_ (DDIO) [27] feature in its CPUs, allowing RNIC to read and write
directly to the CPU cache, reducing the overhead of DMA controller
invalidations, which used to be the key mechanism enabling coherent memory
accesses in RDMA.

##  3 PM Transactions

In this work, we assume that the applications modifying persistent memory use
a storage transactions [34, 44] for failure-atomicity. Figure 1 shows a
typical transaction that uses undo logging to achieve failure-atomicity.
Storage transactions do not provide concurrency control and programmers have
to use a separate mechanism (e.g., locks) to achieve concurrency control.
Next, we describe the guarantees provided by storage transactions and the
primitives necessary to provide these guarantees.

Figure 1: A typical undo-logging transaction [34, 44] using ordering and
durability fences to enforce intra-transaction ordering guarantees and inter-
transaction (or end of transaction) durability guarantees.

Guarantee-1: Failure-atomicity This guarantee provided by the transaction
system developer states that either all the updates from a transaction or none
of the updates from a transaction are visible during recovery after a system
failure. The typical way to achieve failure-atomicity is to employ some form
of logging. For example, with undo logging (Fig 1), first a log entry (back up
copy) of the data being modified is prepared, then the actual data is
modified, and finally the log entry (back up copy) is invalidated to commit
the transaction. If during the execution of the transaction a failure occurs,
the log entry is used to roll back the partial updates and provide the
illusion of failure-atomicity.

To achieve failure-atomicity, a primitive that provides “ordering” guarantees
between different steps of a transaction is mandatory. Without such a
primitive, failure-atomicity _cannot_ be provided. For example, in the undo
logging transaction, the programmer must have a way to ensure that the updates
from the PrepareLogEntry step persist before any from MutateDataStructure
persist. As long as such an ordering primitive is provided to the programmer,
the programmer can develop software crash consistency mechanisms (not just
undo/redo logging) to provide failure-atomicity. Hence forth, we refer to
portions of a transaction between two successive ordering points as an epoch.
So, a transaction may contain multiple epochs, all updates within on epoch may
persist concurrently, however, updates from successive epochs must persist in
order.

Guarantee-2: Durability While failure-atomicity provides a guarantee over what
parts of a transaction may persist, the durability guarantee describes when a
transaction must persist. The end of a transaction is considered a
“durability” point, i.e., after the completion of the transaction, all the
updates of the transaction must be persisted. The importance of a durability
point is best understood in its contrast with an ordering point. A ordering
point simply enforces the order in which two sets of updates (before and after
the ordering point) must persist. It does not specify any constraints on when
the sets of updates an be considered persisted, that is the responsibility of
a durability point. A durability point, once executed past, guarantees that
all prior updates have persisted.

Primitive-1: Ordering Fence The first primitive, necessary to achieve failure-
atomicity, is one that provides ordering guarantees. We refer to a primitive
that provides ordering guarantees as an ordering fence (ofence).

Primitive-2: Durability Fence The second primitive is one that provides
durability guarantees. We refer to a primitive that provides durability
guarantees as a durability fence (dfence).

It is important to note that while some architectural proposals [48, 44]
provide separate primitives to provide ordering an durability guarantees, some
architectures overload the ordering and durability functionality on the same
primitive (for example, sfence in x86. [35])

##  4 Memory-level SM

###  4.1 SM over RDMA

Figure 2: A primary-backup RDMA configuration. (1) Source flushes a cache-line
to local PM; (2) source issues an RDMA write and busy waits (polls CQ); (3)
RDMA write; (4) RDMA write ack (RDMA writes are posted); (5) PCIe write to
backup LLC; (6) replicated cache line eventually gets evicted to persistent
memory (PM).

In this paper, we assume a system implementing Intel’s recently proposed
persistency model [26] to ensure _local persistence_ of data. The key
instruction introduced as part of this persistency model is the _cache line
write back_ ($clwb$) instruction, which writes back a cache line from the
cache to the memory controller write queue. We further assume that the system
has support for Asynchronous DRAM Refresh (ADR), mandatory on Intel platforms
[28, 51], which guarantees that all accepted writeback requests at the memory
controller write queue will be drained to persistent memory in the event of a
system failure [51, 28]. Under this persistency model, two writes to addresses
A and B are guaranteed to persist in order A < B, by using the following
pseudo-assembly-code sequence:

$strA;\;clwbA;\;sfence;\;strB;$ (1)

The combination of $clwb$ and $sfence$ above ensures that the store to A
becomes persistent (by reaching the write queue at the memory controller)
before the store to B. And, this programming idiom can be used to provide more
intuitive durability guarantees (e.g., transactions) to the regular
programmers [34]. For processors which do not support the recently announced
$clwb$ instruction, it can be replaced with the more expensive $clflush$ or
$clflushopt$ instructions to provide the same persistence guarantees albeit at
degraded performance [26].

On top of achieving local persistence of data, to ensure memory-level SM, a
programmer has to communicate two important pieces of information to the
underlying replication system: (1) the dirty data that needs to be replicated
and (2) specify the synchronization point in program where the replication of
the identified dirty data has to be completed. For example, in storage-level
SM, the file system captures all the necessary information and relays it to
the replication system [67]. System calls like _fwrite, fappend_ indicate the
dirty data that needs to be replicated while those like _fsync, msync_ specify
the synchronization point in the program where the dirty data has to be
replicated. Similarly, for memory-level SM, the memory persistency model
employed helps capture this information.

For programs annotated with Intel’s persistency model, the $clwb$ instruction
(if unsupported, then $clflushopt$ or $clflush$) identifies the dirty
cachelines that need to be persisted and the $sfence$ specifies the
synchronization point by which the dirty cachelines have to be persisted.
Based on such annotations, one could use RDMA writes to replicate dirty
cachlines and enforce ordering and durability guarantees. Using one-sided -
RDMA writes is a preferred way of synchronous mirroring, as it only involves
one server. Because of its one-sided nature, RDMA writes are cheaper in terms
of latency and throughput compared to two-sided mechanisms, such as RPC. In
the following section, we expand on why it is challenging to use one-sided -
RDMA operations in SM.

###  4.2 Challenges in mirroring transactions over RDMA

While mirroring PM transactions, the replication system must be cognizant of
the ordering and durability guarantees that must be provided within and at the
end of the transaction respectively.

Ordering challenges: When mirroring using RDMA, there are many points in the
path to the PM on the remote machine that can violate either the ordering or
durability or both guarantees necessary to ensure the failure atomicity and
durability of transactions. For example, successive RDMA writes maybe placed
in different Queue Pairs at the local NIC and may be processed in different
order. Or, even if the writes reach the remote NIC in the correct order and
are processed in the correct order, modern architectures employ DDIO which
causes the writes to be written to the LLC of the remote machine. The LLC may
then evict the corresponding cacheline in any order. So, any mechanism that
replicates transactions must ensure that the writes to remote PM persist in
the correct order.

Durability challenges: Durability guarantees are also not easily provided when
replicating PM transactions over RDMA. When a durability fence is executed,
the replication system must ensure that all the prior RDMA writes have been
persisted in the remote PM. However, the path for an RDMA write from the local
machine to the remote PM consists of many buffers and caches that can cause
the request to be buffered at any point (even in the local machine) and not be
completed. So, the replication system must deploy mechanisms which guarantee
that upon the execution of dfence, the RDMA writes will in fact be persisted
on a remote PM.

Both of these challenges stem from the fact that the acknowledgement to an
RDMA write request (as shown in Figure 2) is sent before the PCIe write is
posted let alone the write becoming persistent.

###  4.3 Key Goals of This Study

This work aims to understand the performance implications of using RDMA in SM
of persistent memories. We would like to understand whether RDMA is well-
suited for SM of persistent memories and, if not, identify key performance
issues and propose new techniques and hardware primitives that will make SM
over RDMA more efficient. The two key questions this paper aims to answer:

  * •

What does it take to enforce ordering and durability guarantees in SM using
the rcommit RDMA primitive? And, what is the performance impact of such a
replication strategy?

  * •

What are the other possible replication strategies? What primitives / hardware
extensions do they require? And, how to reduce the performance overhead of SM
using RDMA?

##  5 Replication Strategies

⬇ 1 (a) LOCAL 2 \--------- 3 4Start Tx 5 St A; CLWB A; 6 7 St B; CLWB B; 8 9
SFENCE; 10 11 St C; CLWB C; 12 13 St D; CLWB D; 14 15 SFENCE; 16End Tx

⬇ 1 (b) SM-RC 2 \--------- 3 4Start Tx 5 St A; CLWB A; 6 RDMA Write A; 7 St B;
CLWB B; 8 RDMA Write B; 9 10 SFENCE; RCOMMIT; 11 12 St C; CLWB C; 13 RDMA
Write C; 14 St D; CLWB D; 15 RDMA Write D; 16 17 SFENCE; RCOMMIT 18End Tx

⬇ 1 (c) SM-OB 2 \--------- 3 4Start Tx 5 St A; CLWB A; 6 // Write Through
Write 7 RDMA Write (WT) A; 8 St B; CLWB B; 9 RDMA Write (WT) B; 10 11 SFENCE;
ROFENCE; 12 13 St C; CLWB C; 14 RDMA Write (WT) C; 15 St D; CLWB D; 16 RDMA
Write (WT) D; 17 18 SFENCE; RDFENCE; 19End Tx

⬇ 1 (d) SM-DD 2 \--------- 3 4Start Tx 5 St A; CLWB A; 6 // Non-Temporal Write
7 RDMA Write (NT) A; 8 St B; CLWB B; 9 RDMA Write (NT) B; 10 11 SFENCE; 12 13
St C; CLWB C; 14 RDMA Write (NT) C; 15 St D; CLWB D; 16 RDMA Write (NT) D; 17
18 SFENCE; RDMA Read 0; 19End Tx

Table 1: The code transformations necessary to implement various replication strategies discussed in this section. lt |  lt |  lt |  lt
---|---|---|---
Figure 3: This figure depicts some of the new RDMA primitives proposed to
enable and improve the performance of SM. (a) Depicts conventional RDMA writes
and the new rcommit primitive used in SM-RC. (b) Depicts Write-Through writes
(RDMA Write(WT)) that modify data in the LLC and then write back the data to
the memory controller, a subsequent rofence forces them to completion (c)
Depicts Non-Temporal writes (RDMA Write(NT)) that directly write data to the
memory controller bypassing the LLC.

In this section, we describe several strategies to synchronously mirror the
contents of persistent memories and we evaluate each of these designs in
subsequent sections.

NO Synchronous Mirroring (NO-SM): NO-SM is a replication strategy where we do
not perform any replication but just persist data locally. While no credible
replication strategy can realistically match the performance of NO-SM, it
provides a hypothetical upper bound on the possible performance and also helps
us measure the costs introduced by various replication strategies. Table 1(a)
shows the code of a sample transaction with two epochs implemented using
Intel’s x86 extensions for PM programming (clwb and sfence).

SM using Remote Commit (SM-RC): Recently, there has been a push towards using
single-sided RDMA verbs (like RDMA read() and write()) to avoid the overheads
of interrupting the processor on the remote machine. These read() and write()
requests are completely handled by the receiving NIC without ever interrupting
the associated CPU. However, the challenge with using single-sided RDMA verbs
for SM is that the completion of the write() verb does not provide any
guarantees on whether the corresponding data persisted on the remote machine.
Upon receiving a completion acknowledgement, the sender of the write() message
is just guaranteed that the write command has been communicated to the remote
NIC. The remote NIC may subsequently (at some future point) post a PCIe write
command to write the corresponding data to the LLC of the attached processor
(due to DDIO support). Current PCIe interface does not provide any mechanisms
to query if a posted write command has been completed. Furthermore, even if
the NIC can be assured that a posted PCIe write command is complete, the data
has only been written to the LLC that is volatile and may lose its contents in
the event of a system failure. To achieve persistence, the corresponding data
has to be written back from the LLC to the memory controller.

One way to achieve the persistence of data written to the LLC is to have a
“flusher” thread running on the dedicated core in the processor and
periodically interrupt the thread and request it to flush the data from the
LLC. However, that approach wastes valuable processor resources. Taley and
Pinkerton [54] propose a single-sided RDMA verb called rcommit to tackle this
problem. The completion acknowledgement of an rcommit message guarantees to
the sender that all prior issued RDMA writes are complete and that they are
written back to the memory controller and hence persistent. NICs that support
the rcommit primitive receive as input the range of memory addresses to be
flushed to the persistent memory and have to ensure that all cachelines that
belong to the specified range reach the memory controller before sending a
completion acknowledgement. Figure 3(a) shows how an rcommit writes back all
the cachelines touched by prior writes from the cache hierarchy to the
persistent memory controller. We discuss the implementation details of rcommit
and how we model it in §6.

rcommit is both an ordering and durability primitive as the completion of an
rcommit ensures that all prior RDMA writes are durable. That is, RDMA writes
separated by an rcommit will necessarily persist in order. So, an rcommit is
an overloaded primitive (like an sfence) that provides both ordering and
durability guarantees. Table 1(b) shows the code a sample transaction with two
epochs being replicated using the SM-RC approach. For each clwb encountered,
an RDMA write is issued and at the end of every epoch (indicated by an
sfence), an rcommit is issued, whether its for intra-transaction ordering
guarantees or for the end of transaction durability guarantees.

SM using Ordered Buffering (SM-OB): In this design, we propose to decouple
RDMA primitives for ordering and durability of remote writes. We introduce a
new primitive called rofence, that ensures the ordering of remote writes,
while a separate rdfence primitive ensures their durability. The rofence
demarcates different epochs within a transaction and hence allows the remote
NIC to process the write requests in the correct order. This approach allows
all writes in the same epoch to be processed concurrently while writes in
different epochs will be persisted in order. While processing a write request,
it is not enough for a remote NIC to simply post a PCIe command as that would
result in the data being written to the LLC only. We introduce a new PCIe
command to allow the the data to not only be written to the LLC but also to be
written back to memory controller. We refer to this new PCIe command as a
Write-Through Writes (Write (WT)). Figure 3(b) highlights how the RDMA Write
(WT) first is written to the LLC and then immediately also written through to
the memory controller. A subsequent rofence ensures that all prior write
through writes have been completed. The durability fence, rdfence, ensures
that all outstanding RDMA writes and rofence commands are executed before it
completes.

Table 1(c) shows a sample transaction with two epochs being replicated using
the SM-OB approach. For every clwb encountered, a RDMA write with Write-
Through attribute is issued. Further, an rofence is issued at the end of each
epoch within a transaction to achieve ordering guarantees while an rdfence is
issued at the end of the transaction to achieve durability guarantees.

SM using Disabled DDIO (SM-DD): SM-OB causes the RDMA writes to be first
written to the LLC on the remote machine and then be written back to the
memory controller. In this approach, we disable the DDIO optimization on the
remote machine allowing the remote writes to bypass the LLC and go directly to
the memory controller. Using this approach, the remote NIC can issue Non-
Temporal Write requests (RDMA Write (NT)), that when completed are guaranteed
to be persistent, as shown in Figure 3(c). Furthermore, we route all the RDMA
writes executed by the application through a single queue pair on the local
and remote NICs. By routing all the write requests through a single queue
pair, we ensure that all the writes are processed by both the NICs (local and
remote) in the order in which they were executed, ensuring the necessary
ordering guarantees without the need for an explicit rofence command. And, to
ensure the durability of all outstanding write commands, we issue a RDMA read
command and poll for its completion. By the properties provided by the RDMA
standard, the completion of the RDMA read ensures that all prior writes are
completed and by disabling DDIO, we can be sure that the writes are indeed
persistent.

Table 1(d) shows a sample transaction with two epochs being replicated using
the SM-DD approach. For every clwb encountered, a RDMA write with Non-Temporal
attribute is issued, leading to bypass the LLC on the remote machine and
directly reach the memory controller. No fences are required to order writes
from different epochs as SM-DD provides an implicit guarantee that all writes
will persist in program order (even those within the same epoch). However, at
the end of the transaction, to achieve durability guarantees, we need to
ensure that all outstanding write requests are completed. In order to achieve
this durability guarantee, we issue an RDMA read to a sentinel address (0 in
this case) which forces all prior writes to be completed (owing to the
relationship between RDMA reads and writes).

Discussion: The main benefits of disabling DDIO for the purposes of SM are:
(1) the RDMA writes are faster as they can now bypass the LLC and directly
reach the persistent memory controller, (2) the overheads of rofence, like
additional RDMA commands incurred, are completely eliminated, and (3)
designing the replication system is simpler as the designer is relieved of the
burden of accurately identifying and placing the appropriate rofence commands.
However, the downsides of this approach are: (1) all the RDMA writes issued
for SM are routed through a single QP (for ordering purposes), failing to take
advantage of the parallelism provided by multiple QPs at the NIC, and (2)
today’s computer systems have multiple tenants, so disabling DDIO for the
benefit of one application might hurt the performance of other applications.
While the first concern is fundamental to this approach, the second can be
eliminated by a feature that can enable/disable DDIO on a per application or
on an per QP basis.

While SM-DD is implementable on certain select motherboards (which we
unfortunately do not have access to), SM-RC and SM-OB are not feasible on
current systems as they require support for new RDMA verbs and PCIe commands.
To make a fair comparison of the different approaches, we develop an emulation
methodology that we describe next and then present a comprehensive performance
analysis of the different approaches.

##  6 Methodology

While SM for Persistent Memories is important, efficient mechanisms to enable
SM are yet to be developed. The mechanisms that we are proposing in this paper
need new primitives that are not available in today’s computing systems. To
estimate the performance impact of our proposed techniques, we model the
latencies of the necessary remote memory operations that are currently not
available. To this end, we create a precise model of the last level cache
(LLC) and the memory controller and investigate how local and remote
operations interact with this model. We use this model to measure delays when
interacting with the memory subsystem. We combine these delays with actual
RDMA network traffic to gain insights and compare end-to-end performance of SM
for Persistent Memories using techniques proposed in this paper (SM-OB and SM-
DD) and the existing SM-RC proposal.

We first describe our model of the last level cache and the memory controller
before discussing how we estimated the performance of our new primitives.

###  6.1 Modeling the LLC and the Memory Controller

Given a certain physical address, we can find the LLC cache set in which it
will be stored using existing models for Intel processors [41]. On the remote
side, we measure that 10% of each cache set in L3 is dedicated to DDIO traffic
(2 out of the available 20 ways in the Xeon E5-2630 v3 processor in our test
bed). Hence, assuming a least recently used (LRU) policy for DDIO traffic and
the knowledge of physical addresses of the remote RDMA buffer, we can predict
how each RDMA write will change the state of the remote cache and could
potentially evict items from the LLC.

Assuming a system with DDIO support, items that are evicted from the LLC will
end up in the memory controller queue before being written to the persistent
memory. Since the memory controller is part of the persistent domain, we need
to ensure that the items enter this queue in the correct order. In systems
without DDIO support, the writes from the network (i.e., from PCIe) will
directly enter the memory controller’s queue in the same order that they
arrive.

Note that once the memory controller’s queue is full, the items cannot be
inserted either from the LLC or the network. In this case, a back-pressure
mechanism ensures that we can no longer send write requests to the remote
server. Assuming a processor with a certain number of cache sets, our model
takes four parameters as input: the latency of a PCIe write to the LLC
(default - 200ns round-trip), the latency of a write from LLC to the memory
controller’s queue (10ns), the size of the memory controller’s queue (64), and
the latency of a write from the memory controller’s queue to the persistent
memory (150ns). Once configured, our model can estimate the latency of a given
memory write at a certain address with a given size.

###  6.2 Modeling Persistent Memory Primitives

We now describe the individual remote and local memory access operations and
how we model them.

Cacheline Writeback (CLWB). The clwb instruction writes back dirty cachelines
from the cache hierarchy to the memory controller. The instruction initiates a
writeback and the programmers have to use a subsequent sfence to ensure the
completion of all prior clwb instructions.

The clwb instruction is going to be available in the Skylake server micro-
architecture. To model clwb, we rely on our model tag the cachelines that
should be written to the memory controller’s queue eagerly. At each clwb, we
calculate how many previously tagged cachelines have had time to have been
eagerly sent to the memory controller. To model sfence, we calculate how many
tagged cachelines still need to be written to the memory controller and return
the necessary delay for these writes to be completed.

Remote Commit (RCOMMIT). rcommit is a new RDMA verb being proposed in the RDMA
standard to writeback the cachelines touched by all prior RDMA write
operations from the LLC to the memory controller on the remote machine. The
completion of an rcommit indicates that all prior RDMA writes have been
persisted on the remote machine.

To estimate the latency of an rcommit, we treat is as being two separate
operations performed in series. First, the round trip to the remote machine,
that involves setting up the QP entry, draining it on the local RNIC,
receiving it on the remote RNIC, issuing the appropriate PCIe command and
finally sending a response back. Second, the actions performed on the remote
machine, that is the write back operations. Hence, we model an rcommit as
being two operations performed in series, a remote RDMA read (to estimate the
latency of a round trip) and the price of draining the previously written
cachelines that are still present in the LLC as estimated by our model. This
also means that some RDMA write operations may observe increased latency if
the target cache set and the memory controller’s queue are both full.

Remote Writes Write-Through (rwtw) and Non-Temporal (rntw). rntw and rwtw are
new RDMA primitives we introduce to write the cachelines directly to the
memory controller instead of just writing them to the LLC. When an application
issues these new RDMA verbs and it is received on the remote RNIC, the remote
RNIC tags the cachelines associated with this write to be either directly sent
to the memory controller bypassing the LLC (rntw) or written through from the
LLC to the memory controller (rwtw) from the PCIe root complex.

To estimate the latency of an rntw or rwtw, we treat it as being two separate
operations performed in series. First, the round trip to the remote machine,
that involves setting up the queue pair entry, draining it on the local NIC,
receiving it on the remote NIC, issuing the appropriate PCIe command and
finally sending a response back. Second, the action performed on the remote
machine. For the non-temporal write (rntw), we use our model to estimate the
latency assuming no DDIO support (i.e., writes directly go to the memory
controller’s queue). For the write-through write (rwtw), we use the same
estimation from our model as clwb.

Remote Ordering Fence (rofence). rofence defines ordering points within the
execution of an application where the hardware must ensure that all prior
issued RDMA writes or rntw or rwtw are guaranteed to persist before any
subsequent RDMA writes.The exact mechanism by which the hardware provides this
guarantee is left up to the discretion of the hardware designer. One possible
implementation is that the remote NIC receiving the RDMA write and rofence
commands, places them in a single FIFO queue.

To estimate the latency of an rofence, we simply treat is an RDMA write which
incurs a standard round trip latency. The reason for this choice is that the
rofence, like an RDMA write, simply notifies the remote NIC of certain action
to be performed (the write for RDMA write, while the ordering specification in
case of rofence) and does not actually force the completion of any action on
the remote machine.

Such a queue introduces two sources of overheads: (1) it serializes the
commands that are received from multiple independent threads/applications, (2)
it does not allow any reordering of RDMA writes between successive rofence
commands. Hardware designers may implement optimized versions of the queue
that mitigates one or both of the overheads described. Note that rofence does
not change the state of the LLC and/or the memory controller’s queue and hence
need not to interact with our model.

Remote Durability Fence (rdfence). rdfence defines the durability points
within the execution of an application where the hardware must ensure that all
prior issued RDMA writes are guaranteed to persist before the completion of
the rdfence command. Note that while persisting data due to an rdfence
command, the hardware must still provide the ordering guarantees specified by
any prior rofence commands.

To estimate the latency of rdfence command, we treat it as two separate serial
operations, a round trip and draining writes to the persistent memory, similar
to an rcommit command. The notable exception for rdfence is that the
cachelines are eagerly written to the memory controller’s queue from the LLC,
following the same mechanism as clwb. The latency of the writes to the
persistent memory is hence estimated by our model similar to clwb.

###  6.3 Experimental Setup

To evaluate memory-level SM on RDMA, we build an RDMA test-bed based on
Infiniband. Our test-bed assumes the following server configuration; an Intel
Xeon E5-2630 v3 CPUs running at 2.4GHz and DDR4 memory. Our platform is based
on Mellanox ConnectX-3 40Gbps RDMA network adapters. The IB platform is
equipped with Infiniband SX6036 switch. A detailed summary of our platform is
presented in Table 2.

Table 2: RDMA platform Component |  Platform
---|---
CPU |  Intel Xeon E5-2630 (2.4GHz)
Memory |  DDR5 - 2400MHz (16x16GB DIMMs)
Network |  Infiniband (40Gbps)
RNIC |  Mellanox ConnectX-3
Switch |  SX6036 (w/FDR)

Platform disclaimers: Our platform does not support the newly introduced
$clwb$ or $clflushopt$ instructions, so we use the $clflush$ instruction in
our programs. The RDMA write verb, once completed on current hardware does not
guarantee that the data has been persisted to the remote memory, instead, it
just guarantees that a PCIe write for the data has been posted in the remote
machine. This problem is already being addressed by the industry [53] and we
expect future RNICs to close this vulnerability.

##  7 Evaluation

To compare the performance of the different replication strategies, we
instrument a microbenchmark and workloads from the WHISPER [44] with the
primitives detailed in §5 and execute them on our test-bed with our model.

###  7.1 Microbenchmarks

Figure 4: Slowdowns seen due to SM of Transact with different replication
strategies over a baseline of NO-SM. The x-axis labels are of the form $e-w$,
where $e$ represents the number of epochs per transaction and $w$ represents
the number of writes per epoch used in Transact.

Our microbenchmark, _Transact_ , executes 1M transactions, each of which is
replicated. Transact allows configurable number of epochs per transaction and
further, configurable number of writes per epoch. However, once configured,
all the transactions have the same number of epochs per transactions and
writes per epoch. We vary the number of writes per epoch from [1 … 8] and the
number of epochs per transaction from [1 … 256]. The ranges were decided based
on the analysis of persistent memory workloads presented by Nalli et al. [44],
which showed that applications exhibit very few writes per epoch, but can
exhibit hundreds of epochs per transaction. The addresses of writes within a
transaction are randomly chosen.

Our goal with this study is to understand the suitability of different
replication strategies to different kinds of transactions - small
transactions, large transactions, ones with fewer epochs, etc. We evaluate
Transact on the platform described in Section 6.3. Figure 4 shows the
slowdowns incurred with different replication strategies over a baseline of
NO-SM, where no replication is performed. The x-axis labels are of the form
$e-w$, where $e$ represents the number of epochs per transaction and $w$
represents the number of writes per epoch used in Transact. For example, a
configuration of $16-2$ indicates that there are $16$ epochs per transaction
and $2$ writes per epoch. We make three major observations from Figure 4.

First, SM-RC incurs the highest performance overheads. As Figure 4 shows, SM-
RC incurs the highest slowdowns for all different Transact configurations,
ranging from about 20x to over 55x. SM-RC uses expensive rcommit verbs to
ensure ordering and durability guarantees and the frequent use of this
primitive results in the high overheads. These overheads are highest for
transactions with only 1 write per epoch and gradually reduce with increasing
number of writes per epoch. This behavior is to be expected as higher number
of writes per epoch allows the an expensive rcommit verb to be amortized over
a larger number of asynchronous RDMA writes.

Second, SM-OB and SM-DD consistently outperform SM-RC. Both SM-OB and SM-DD
outperform SM-RC for all Transact configurations by as much as 3.5x (for
Transact 4-1). The main reason for the performance advantage of SM-OB and SM-
DD is that they eliminate the use of blocking rcommit verbs to ensure intra-
transaction ordering guarantees. The performance difference is especially high
when Transact has a low number of writes per epoch, due to a high ratio of
rcommit verbs per write.

Third, SM-OB and SM-DD are suitable to different kinds of transactions.
Controlling for the number of writes per epoch within a transaction, SM-OB
performs better for transactions with higher number of epochs per transaction
while SM-DD performs better for transactions with lower number of epochs per
transactions. This trade-off in performance with SM-DD and SM-OB is to be
expected as they optimize different aspects of SM. For example, SM-DD reduces
the number of blocking ordering enforcement points than SM-OB by eliminating
the need for rofence primitive. However, SM-DD increases the latency of
individual RDMA write operations by forcing each write to be written directly
to the memory controller. Furthermore, SM-DD may cause frequent pauses to
write processing at the remote NIC as it might cause the small write queue (64
entries, 4KB) at the memory controller to fill up while SM-OB allows the
remote NIC to process more requests to buffer more writes in the LLC (up to
2MB as described in Section 6). For these reasons SM-DD is more efficient for
small transactions while SM-OB is more efficient for larger transactions.

Discussion. With the optimized cache flush instructions ($clflushopt$ and
$clwb$), we expect the time to perform local flush operations to reduce
significantly providing fewer opportunities to overlap remote RDMA writes and
local flush operations resulting in higher performance overheads even for
larger transactions. However, Transact is dominated by writes and real
applications with less frequent write operations can expect lower overheads.
Next, we analyze the overheads experienced with real applications from the
WHISPER [44] benchmark suite.

###  7.2 WHISPER applications

(a) Execution Time

(b) Throughput

Figure 5: Changes in the execution time and throughput due to SM for different
WHISPER workloads.

In this subsection, we first present a quick overview of persistent memory
applications from the WHISPER [44] benchmark suite and then show the overheads
of employing memory-level SM for these workloads.

C-tree is a multi-threaded benchmark that performs inserts and deletes on a
persistent crit-bit tree data structure. This workload was initially released
as part of NVML [25].

Echo mimics the behavior of a persistent key-value store. The benchmark
consists of a master thread that manages the store and many client threads
that send updates to the store.

Hashmap is a multi-threaded benchmark that performs inserts and deletes on a
persistent crit-bit tree data structure. This workload was initially released
as part of NVML [25].

YCSB and TPCC are two transaction processing workloads operating over N-store,
a relational database management system designed from scratch for persistent
memories.

Next, we delve in the performance of different replication strategies for
these workloads.

SM-DD $>$ SM-OB $>$ SM-RC. Figure 5 highlights the increased execution times
and decreased throughputs for the WHISPER applications described above for
various replication strategies. As with Section 7.1, the measurements
presented for each platform are normalized over NO-SM. We draw two key
observations. First, SM-RC, on average, increases execution time by 6.7x,
while SM-OB and SM-DD increase execution times by only 3.8x and 2.3x,
respectively. Hence, SM-OB and SM-DD outperform SM-RC by 1.8x and 2.9x,
respectively. Second, SM-RC decreases throughput by 85%, while SM-OB and SM-DD
decrease throughput by only 73% and 52%, respectively. SM-DD consistently
performs best, while SM-RC performs worst.

Workload characteristics. The relative performance of SM-RC, SM-OB, and SM-DD
are to be expected based on the characteristics of the workloads. These
benchmarks have only a modest fraction of all the write instructions executed
during the applications and update persistent data (about 5%) [44]. We expect
that the performance degradation due to memory-level SM for different
applications will be largely determined by the fraction of accesses to
persistent data, with applications having higher fractions of accesses to
persistent data seeing more performance degradation. The rest of the write
instructions in the application arise due to modifications to volatile data
structures not necessary for crash consistency. Furthermore, the average
number of writes per epoch for these workloads is only 1.4. A disproportionate
number of epochs in most of the workloads modify only one cacheline worth of
data. However, the average number of epochs per transaction vary significantly
for the various workloads from about 10 (hashmap) to over 300 (echo). Based on
the low number of writes per epoch in these workloads and our analysis of the
microbenchmark Transact, we can expect SM-DD to perform best.

##  8 Related Work

In this section, we present a brief overview of the research most relevant to
our work.

RDMA Applications. The use of RDMA has gained popularity as a communication
mechanism in many distributed database systems and algorithms. In the context
of join algorithms, the costs of large data transfers can be significantly
reduced by interleaving compute and communication, and by avoiding
intermediate copies through the use of one-sided memory operations [7]. These
algorithms have been shown to scale to several thousands of cores and are able
to achieve a high throughput [8]. RDMA is used in BatchDB as a low-latency
communication mechanism to replicate data to multiple workload-specific
replicas in order to maintain strict performance, data freshness, and
consistency requirements [40]. Many distributed database systems have explored
RDMA communication primitives as part of their query pipeline in order to
speed up query response times [50, 52], while others have been re-designed
from the ground up with RDMA in mind [9, 6]. Key-value storage systems make
use of high-performance networks to enable low-latency access to remote data
[16, 32].

Persistent memory systems. Emerging persistent memory technologies present a
paradigm shift in storage technologies and have set off an assortment of
research projects in the areas of persistent data structures [30, 45, 57],
file systems [13, 17, 64, 60, 66, 2], transaction logging techniques [3, 49,
11, 63, 38, 34] and many more. Many recent works, both from academia and
industry, have also sought to develop new programming models [26, 48, 31, 44]
to program for persistent memory systems and have also developed architectural
solutions to efficiently implement these models [35, 31, 44]. However, all of
these works assume that data is “persistent” as soon as it reaches local
persistent memory, as assumption that cannot be employed in large scale multi-
node systems.

Replicating persistent memory data. Replicating data to ensure high-
availability and high-durability is a widely used approach [1, 10, 14, 20, 22,
21]. While many different replication techniques are used, synchronous
mirroring (SM) is a common feature of enterprise storage solutions [18, 23,
46, 58, 24]. For conventional storage and network technologies, the strong
consistency guarantees of SM comes at a very low performance cost [39].
However, with the emergence of persistent memory technologies a reevaluation
of the costs of SM have to be reevaluated.

Recent proposals from the Storage Networking Industry Association (SNIA) [53,
4] indicate that both hardware manufacturers and software developers are
looking to enable efficient remote persistent memory access over RDMA. Mojim
[67] enables SM for persistent memories and most closely resembles the systems
envisioned in our work. However, one major difference is that Mojim is
designed to provide SM for file systems mounted on persistent memories and not
designed to support the newer persistent memory programming interfaces [5].
Unlike the file systems, these newer interfaces expose a byte-addressable
storage media to the programmers, resulting in fine-grain accesses (a few
cachelines at a time [44]).

##  9 Conclusion

In this work we propose a set of new RDMA primitives that aim to improve the
efficiency of persistent memory mirroring. On top of that, we propose two
novel SM techniques that leverage the new primitives to unleash the full
potential of modern RDMA hardware. The first technique is based on ordered
buffering, while the other one uses non-temporal remote writes to ensure
ordering and durability guarantees. We add the support for SM in the WHISPER
benchmark suite and use a microbenchmark to evaluate the performance of our
two proposals and compare them to a prior proposal based on the remote commit
RDMA verb. We conclude that ordered buffering and non-temporal writes enable
highly concurrent SM and outperform designs that use remote commit.

## References

  * [1] A. Adya _et al._ , “Farsite: Federated, available, and reliable storage for an incompletely trusted environment,” _SIGOPS Oper. Syst. Rev._ , 2002\.
  * [2] M. K. Aguilera _et al._ , “Remote regions: a simple abstraction for remote memory,” in _ATC_ , 2018.
  * [3] J. Arulraj _et al._ , “Write-behind logging,” _PVLDB_ , 2016.
  * [4] S. N. I. Association, _NVM Summit Presentations_ , https://www.snia.org/nvmsummit/abstracts.
  * [5] S. N. I. Association, _Persistent Memory, NVM Programming Model, and NVDIMMs_ , https://www.flashmemorysummit.com/English/Collaterals/Proceedings/2017/20170809_FR21_SNIA.pdf.
  * [6] C. Barthels _et al._ , “Designing databases for future high-performance networks,” _IEEE Data Eng. Bulletin_ , 2017.
  * [7] C. Barthels _et al._ , “Rack-scale in-memory join processing using RDMA,” in _SIGMOD_ , 2015.
  * [8] C. Barthels _et al._ , “Distributed join algorithms on thousands of cores,” _PVLDB_ , 2017.
  * [9] C. Binnig _et al._ , “The end of slow networks: It’s time for a redesign,” _PVLDB_ , 2016.
  * [10] B. Calder _et al._ , “Windows Azure storage: A highly available cloud storage service with strong consistency,” in _SOSP_ , 2011.
  * [11] A. Chatzistergiou _et al._ , “REWIND: Recovery write-ahead system for in-memory non-volatile data-structures,” _PVLDB_ , 2015.
  * [12] V. Chidambaram _et al._ , “Optimistic crash consistency,” in _SOSP_ , 2013\.
  * [13] J. Condit _et al._ , “Better I/O through byte-addressable, persistent memory,” in _SOSP_ , 2009.
  * [14] G. DeCandia _et al._ , “Dynamo: Amazon’s highly available key-value store,” in _SOSP_ , 2007.
  * [15] C. Douglas, “RDMA with PMEM,” in _SDC_ , 2015.
  * [16] A. Dragojevic _et al._ , “FaRM: Fast remote memory,” in _NSDI_ , 2014\.
  * [17] S. R. Dulloor, “Systems and applications for persistent memory,” Ph.D. dissertation, Georgia Institute of Technology, 2015.
  * [18] EMC, _EMC VNXe HIGH AVAILABILITY_ , 2013, https://www.emc.com/collateral/hardware/white-papers/h8276-emc-vnxe-high-availability-wp.pdf.
  * [19] Forbes, _Amazon.com Goes Down, Loses $66,240 Per Minute_ , https://www.forbes.com/sites/kellyclay/2013/08/19/amazon-com-goes-down-loses-66240-per-minute/#5a947b5d495c.
  * [20] S. Ghemawat _et al._ , “The Google file system,” in _SOSP_ , 2003.
  * [21] G. A. Gibson _et al._ , “Coding techniques for handling failures in large disk arrays,” Tech. Rep., 1988.
  * [22] J. Gray _et al._ , “The dangers of replication and a solution,” in _SIGMOD_ , 1996.
  * [23] HPE, _HPE 3PAR Replication Software_ , https://www.hpe.com/h20195/v2/GetPDF.aspx/4AA4-4251ENW.pdf.
  * [24] IBM, _IBM Metro Mirror_ , https://www.ibm.com/support/knowledgecenter/en/ssw_ibm_i_73/rzaue/rzauemetromirror.htm.
  * [25] Intel, “NVM library,” http://pmem.io/nvml/.
  * [26] Intel Corporation, “Intel architecture instruction set extensions programming reference (319433-029 April 2017),” https://software.intel.com/sites/default/files/managed/c5/15/architecture-instruction-set-extensions-programming-reference.pdf.
  * [27] Intel Corporation, “Intel datat direct I/O technology,” https://www.intel.com/content/www/us/en/io/data-direct-i-o-technology.html.
  * [28] Intel Corporation, “Platform brief Intel Xeon processor c5500/c3500 series and Intel 3420 chipset,” https://www.intel.com/content/www/us/en/intelligent-systems/picket-post/embedded-intel-xeon-c5500-processor-series-with-intel-3420-chipset.html.
  * [29] Intel Corporation, “Revolutionary memory technology,” http://www.intel.com/content/www/us/en/architecture-and-technology/non-volatile-memory.html.
  * [30] J. Izraelevitz _et al._ , _Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model_ , 2016.
  * [31] A. Joshi _et al._ , “Efficient persist barriers for multicores,” in _MICRO_ , 2015.
  * [32] A. Kalia _et al._ , “Using RDMA efficiently for key-value services,” in _SIGCOMM_ , 2014.
  * [33] A. Klimovic _et al._ , “ReFlex: Remote flash ≈ local flash,” in _ASPLOS_ , 2017.
  * [34] A. Kolli _et al._ , “High-performance transactions for persistent memories,” in _ASPLOS_ , 2016.
  * [35] A. Kolli _et al._ , “Delgated persist ordering,” in _MICRO_ , 2016.
  * [36] E. Kültürsay _et al._ , “Evaluating STT-RAM as an energy-efficient main memory alternative,” in _ISPASS_ , 2013.
  * [37] B. C. Lee _et al._ , “Architecting phase change memory as a scalable DRAM alternative,” in _ISCA_ , 2009.
  * [38] Y. Lu _et al._ , “Loose-ordering consistency for persistent memory,” in _ICCD_ , 2014.
  * [39] J. MacCormick _et al._ , “Boxwood: Abstractions as the foundation for storage infrastructure,” in _OSDI_ , 2004.
  * [40] D. Makreshanski _et al._ , “BatchDB: Efficient isolated execution of hybrid OLTP+OLAP workloads for interactive applications,” in _SIGMOD_ , 2017.
  * [41] C. Maurice _et al._ , “Reverse engineering Intel last-level cache complex addressing using performance counters,” in _Research in Attacks, Intrusions, and Defenses_ , H. Bos _et al._ , Eds., 2015.
  * [42] Mellanox, _Introduction to InfiniBand_ , https://www.mellanox.com/pdf/whitepapers/IB_Intro_WP_190.pdf.
  * [43] Mellanox Technologies, “RDMA aware networks programming user manual,” 2015\.
  * [44] S. Nalli _et al._ , “An analysis of persistent memory use with WHISPER,” in _ASPLOS_ , 2017.
  * [45] F. Nawab _et al._ , “Dalí: A periodically persistent hash map,” in _DISC_ , 2017.
  * [46] Netapp, _SnapMirror Data Replication_ , http://www.netapp.com/us/products/backup-recovery/snapmirror-data-replication.aspx.
  * [47] S. Novakovic _et al._ , “The case for RackOut: Scalable data serving using rack-scale systems,” in _SoCC_ , 2016.
  * [48] S. Pelley _et al._ , “Memory persistency,” in _ISCA_ , 2014.
  * [49] S. Pelley _et al._ , “Storage management in the NVRAM era,” _PVLDB_ , 2013.
  * [50] W. Rödiger _et al._ , “High-speed query processing over high-speed networks,” _PVLDB_ , 2015.
  * [51] A. M. Rudoff, “Deprecating the PCOMMIT instruction,” https://software.intel.com/en-us/blogs/2016/09/12/deprecate-pcommit-instruction, 2016\.
  * [52] A. Salama _et al._ , “Rethinking distributed query execution on high-speed networks,” _IEEE Data Eng. Bulletin_ , 2017.
  * [53] SNIA Technical White Paper, “NVM PM remote access for high availability, version 1.0,” 2016.
  * [54] T. Talpey and J. Pinkerton, _RDMA Durable Write Commit draft-talpey-rdma-commit-00_ , https://tools.ietf.org/html/draft-talpey-rdma-commit-00.
  * [55] A. Tavakkol _et al._ , “MQSim: A framework for enabling realistic studies of modern multi-queue SSD devices,” in _FAST_ , 2018.
  * [56] TechCrunch, _JournalSpace Drama: All Data Lost Without Backup, Company Deadpooled_ , https://techcrunch.com/2009/01/03/journalspace-drama-all-data-lost-without-backup-company-deadpooled/.
  * [57] S. Venkataraman _et al._ , “Consistent and durable data structures for non-volatile byte-addressable memory,” in _FAST_ , 2011.
  * [58] VMware, _VMware vSAN_ , https://www.vmware.com/content/dam/digitalmarketing/vmware/en/pdf/products/vsan/vmware-virtual-san-datasheet.pdf.
  * [59] D. Voigt, “RDMA requirements for high availability in the NVM programming model,” in _SDC_ , 2014.
  * [60] H. Volos _et al._ , “Aerie: Flexible file-system interfaces to storage-class memory,” in _EuroSys_ , 2014.
  * [61] P. von Behren, “The NVM revolution,” in _SDC_ , 2015.
  * [62] H. Wada _et al._ , “Data consistency properties and the trade-offs in commercial cloud storages: the consumers’ perspective,” in _CIDR_ , 2011\.
  * [63] T. Wang and R. Johnson, “Scalable logging through emerging non-volatile memory,” _PVLDB_ , 2014.
  * [64] X. Wu and A. L. N. Reddy, “SCMFS: A file system for storage class memory,” in _SC_ , 2011.
  * [65] C. Xu _et al._ , “Overcoming the challenges of crossbar resistive memory architectures,” in _HPCA_ , 2015.
  * [66] J. Xu and S. Swanson, “NOVA: A log-structured file system for hybrid volatile/non-volatile main memories,” in _FAST_ , 2016.
  * [67] Y. Zhang _et al._ , “Mojim: A reliable and highly-available non-volatile memory system,” in _ASPLOS_ , 2015.
  * [68] Y. Zhu _et al._ , “Congestion control for large-scale RDMA deployments,” in _SIGCOMM_ , 2015.