On a $d$-degree Erdős–Ko–Rado Theorem

###### Abstract

A family of subsets $\mathcal{F}$ is intersecting if $A\cap B\neq\emptyset$
for any $A,B\in\mathcal{F}$. In this paper, we show that for given integers
$k>d\geq 2$ and $n\geq 2k+2d-3$, and any intersecting family $\mathcal{F}$ of
$k$-subsets of $\\{1,\cdots,n\\}$, there exists a $d$-subset of $[n]$
contained in at most $\binom{n-d-1}{k-d-1}$ subsets of $\mathcal{F}$. This
result, proved using spectral graph theory, gives a $d$-degree generalization
of the celebrated Erdős–Ko–Rado Theorem, improving a theorem of Kupavskii.

##  1 Introduction

Denote by $[n]$ the set $\\{1,2,\cdots,n\\}$, and $\binom{[n]}{k}$ the family
of all the $k$-subsets of $[n]$. The celebrated Erdős–Ko–Rado (EKR) Theorem
[3] states that for $n\geq 2k$, an intersecting family
$\mathcal{F}\subset\binom{[n]}{k}$ has at most $\binom{n-1}{k-1}$ subsets. The
upper bound is attained by an $1$-star, i.e. the family of all the size-$k$
subsets of $[n]$ that contain a fixed element. Moreover, when $n\geq 2k+1$,
this construction is unique up to isomorphism. Generalizations and analogues
of the EKR Theorem have been studied over the years, see for example [5] for
different proofs and [2] for a survey.

One may view $\mathcal{F}\subset\binom{[n]}{k}$ as a $k$-uniform $n$-vertex
hypergraph and consider its hypergraph-theoretic properties. Given a subset
$S\subset[n]$, the $S$-degree of $\mathcal{F}$ is defined as
$d_{S}(\mathcal{F})=|\\{T:S\subset T\in\mathcal{F}\\}|$. In other words,
$d_{S}(\mathcal{F})$ counts the number of subsets containing $S$ in
$\mathcal{F}$. For a fixed integer $0\leq d\leq k$, the minimum $d$-degree of
$\mathcal{F}$, denoted by $\delta_{d}(\mathcal{F})$, is the minimum of
$d_{S}(\mathcal{F})$, over all $|S|=d$. For instance,
$\delta_{0}(\mathcal{F})$ is simply the number of edges of $\mathcal{F}$, and
$\delta_{1}(\mathcal{F})$ is the usual minimum vertex degree of $\mathcal{F}$.
In this language, The EKR Theorem determines the maximum of
$\delta_{0}(\mathcal{F})$ among all intersecting $k$-uniform $n$-vertex
hypergraphs.

Motivated by the study of Dirac-type problems in hypergraphs (see [14, 16] for
two comprehensive surveys), Huang and Zhao [9] established the following
degree analogue of the EKR Theorem: for $n\geq 2k+1$ and every intersecting
family $\mathcal{F}\subset\binom{[n]}{k}$,
$\delta_{1}(\mathcal{F})\leq\binom{n-2}{k-2}$. Both the range $n\geq 2k+1$ and
the bound $\binom{n-2}{k-2}$ given by $1$-stars are best possible. Actually,
for most values of $k$, there are regular intersecting subfamilies of
$\binom{[2k]}{k}$ of size $\binom{2k-1}{k-1}$, as shown by Ihringer and
Kupavskii [10]. Subsequently, Frankl and Tokushige [7] gave a combinatorial
proof of the Huang–Zhao Theorem for $n\geq 3k$, based on an earlier result by
Frankl [4] which provides sharp upper bounds on the size of intersecting
families with certain maximum degree. By analyzing their technique more
carefully, one can actually get the proof work for $n\geq 2k+3$, but it seems
very hard to obtain the exact range $n\geq 2k+1$ via combinatorial means.
Later on, Frankl, Han, Huang and Zhao [6] also proved a degree version of the
Hilton–Milner theorem.

It is not hard to observe that by induction on $n$, the Huang–Zhao Theorem
implies the classical EKR Theorem. A natural question arises: for $d\geq 2$,
does the $1$-star still maximize the minimum $d$-degree
$\delta_{d}(\mathcal{F})$, among all intersecting families $\mathcal{F}$?
Kupavskii [11] confirmed this speculation for sufficiently large $n$. He
proved that if $n\geq 2k+\frac{3d}{1-d/k}$ and $1\leq d<k$, then
$\delta_{d}(\mathcal{F})\leq\binom{n-d-1}{k-d-1}$, Note that when $d$ and $k$
are very close, the lower bound on $n$ can be quadratic in $d$ or $k$. In this
paper, we use techniques from spectral graph theory to significantly improve
this range. Our main result is the following.

######  Theorem 1.1.

For positive integers $n,k,d$ satisfying $k>d\geq 2$ and $n\geq 2k+2d-3$ ,
every intersecting family $\mathcal{F}$ of $k$-subsets of $[n]$ must have

$\delta_{d}(\mathcal{F})\leq\binom{n-d-1}{k-d-1}.$

Note that when $d=2$, the range $n\geq 2k+1$ in Theorem 1.1 is the best we
could hope for, since the conclusion might fail for $n=2k$. For example, for
$(n,k,d)=(6,3,2)$, the unique $2$-$(6,3,2)$-design $\\{6,1,2\\}$,
$\\{6,1,3\\}$, $\\{6,2,4\\}$, $\\{6,3,5\\}$, $\\{6,4,5\\}$, $\\{1,2,5\\}$,
$\\{1,3,4\\}$, $\\{1,4,5\\}$, $\\{2,3,4\\}$, $\\{2,3,5\\}$ gives an
intersecting family with $\delta_{2}(\mathcal{F})=2>\binom{6-3}{3-3}$.

The rest of this paper is organized as follows. In the next section, we
introduce some notations used throughout the paper, and sketch an outline of
the proof. Our main result, Theorem 1.1, will be proved in Section 3, after
two key lemmas are established. To ensure a smoother reading experience, we
leave the detailed proofs of several unsurprising identities and inequalities
to Appendix A. Some remarks and open problems are discussed in Section 4.

##  2 Notations and preparations

For $1\leq i\leq k-1$, we say that a family of $k$-subsets is an $i$-star, if
it consists exactly of every $k$-set containing a fixed $i$-set. The
indicating vector of a family $\mathcal{F}\subset\binom{[n]}{k}$, denoted by
$\vec{1}_{\mathcal{F}}$, is a $\binom{n}{k}$-dimensional binary vector, whose
coordinates correspond to subsets $S\in\binom{[n]}{k}$, and whose $S$-th
coordinate is $1$ if $S\in\mathcal{F}$ and $0$ otherwise.

We denote by $KG(n,k)$ the Kneser graph with parameter $n\geq 2k$. Its vertex
set consists of all the $k$-subsets of $[n]=\\{1,\cdots,n\\}$. Two vertices
are adjacent if and only if their corresponding $k$-sets are disjoint. Let $A$
be its adjacency matrix. It is well-known that $A$ has the following
eigenspace decomposition (see for example [12] or [15]):

$\mathbb{R}^{\binom{n}{k}}=E_{0}\oplus E_{1}\cdots\oplus E_{k},$

such that

  * •

$\dim(E_{i})=\binom{n}{i}-\binom{n}{i-1}$.

  * •

For any vector $\vec{v}\in E_{i}$,
$A\vec{v}=(-1)^{i}\binom{n-k-i}{k-i}\vec{v}$.

  * •

The subspace $F_{i}=E_{0}\oplus\cdots\oplus E_{i}$ is an
$\binom{n}{i}$-dimensional subspace, spanned by the indicating vectors of the
$\binom{n}{i}$ distinct $i$-stars. In other words, $E_{i}$ is the orthogonal
complement of $F_{i-1}$ in $F_{i}$.

Let $\vec{h}=\vec{1}_{\mathcal{F}}\in\mathbb{R}^{\binom{n}{k}}$ be the
indicating vector of the intersecting family $\mathcal{F}$. For
$i=0,\cdots,k$, we consider the projection of $\vec{h}$ onto the subspace
$E_{i}$ and denote it by $\vec{h}_{i}$. We have

$\vec{h}=\vec{h}_{0}+\cdots+\vec{h}_{k},$
$A\vec{h}_{i}=(-1)^{i}\binom{n-k-i}{k-i}\vec{h}_{i}.$

Clearly for $i\neq j$, the vectors $\vec{h}_{i}$ and $\vec{h}_{j}$ are
orthogonal.

In the next section, we will prove two inequalities involving the lengths of
$\vec{h}_{i}$’s. The first one follows from a Hoffman bound type argument,
under the assumption that $\mathcal{F}$ is intersecting. The second inequality
is derived directly from information on the minimum $d$-degree
$\delta_{d}(\mathcal{F})$. We will show that a carefully chosen linear
combination of these two inequalities yields a contradiction to the
Erdős–Ko–Rado Theorem which states that $|\mathcal{F}|\leq\binom{n-1}{k-1}$
whenever $n\geq 2k$.

##  3 The main theorem

The first lemma compares two binomial coefficients, helping us later to bound
the small eigenvalues of the Kneser graph $KG(n,k)$.

######  Lemma 3.1.

For $n\geq 2k+1$ and $k>d\geq 1$, we have

$\frac{k-d}{n-k}\binom{n-k}{k}\geq\binom{n-k-d-1}{k-d-1}.$

Furthermore, the equality only holds when $n=2k+1$.

###### Proof.

We have

$\displaystyle\frac{\binom{n-k-d-1}{k-d-1}}{\binom{n-k}{k}}$
$\displaystyle=\frac{(k-d)\cdots k}{(n-k-d)\cdots(n-k)}$
$\displaystyle=\frac{k-d}{n-k}\cdot\left(\frac{k-d+1}{n-k-d}\cdot\frac{k-d+2}{n-k-d+1}\cdots\frac{k}{n-k-1}\right).$

Since $n\geq 2k+1$, each term in the product inside the parentheses is at most
$1$. Thus the above expression is at most $\frac{k-d}{n-k}$. The equality only
holds only when these terms are all $1$, which occurs when $n=2k+1$. ∎

The next lemma considers the projections of the indicating vector $\vec{h}$ of
$\mathcal{F}$ onto the eigenspaces of the Kneser graph $KG(n,k)$.

######  Lemma 3.2.

For an intersecting family $\mathcal{F}\subset\binom{[n]}{k}$ with $n\geq
2k+1,k>d\geq 1$, we have

$0\geq-\frac{k-d}{n-k}\binom{n-k}{k}|\mathcal{F}|+\sum_{i=0}^{d}\left(\frac{k-d}{n-k}\binom{n-k}{k}+(-1)^{i}\binom{n-k-i}{k-i}\right)\|\vec{h}_{i}\|^{2}.$

###### Proof.

Since $\mathcal{F}\subset\binom{[n]}{k}$ is intersecting, it induces an
independent set in the Kneser graph $KG(n,k)$. Therefore from the eigenspace
decomposition in the previous section, we have

$\displaystyle 0$
$\displaystyle=\vec{h}^{T}A\vec{h}=\sum_{i=0}^{k}(-1)^{i}\binom{n-k-i}{k-i}\|\vec{h}_{i}\|^{2}$
$\displaystyle=\sum_{i=0}^{d}(-1)^{i}\binom{n-k-i}{k-i}\|\vec{h}_{i}\|^{2}+\sum_{i=d+1}^{k}(-1)^{i}\binom{n-k-i}{k-i}\|\vec{h}_{i}\|^{2}$
$\displaystyle\geq\sum_{i=0}^{d}(-1)^{i}\binom{n-k-i}{k-i}\|\vec{h}_{i}\|^{2}-\binom{n-k-d-1}{k-d-1}\sum_{i=d+1}^{k}\|\vec{h}_{i}\|^{2}$
$\displaystyle\geq\sum_{i=0}^{d}(-1)^{i}\binom{n-k-i}{k-i}\|\vec{h}_{i}\|^{2}-\frac{k-d}{n-k}\binom{n-k}{k}\sum_{i=d+1}^{k}\|\vec{h}_{i}\|^{2}$
$\displaystyle=-\frac{k-d}{n-k}\binom{n-k}{k}|\mathcal{F}|+\sum_{i=0}^{d}\left(\frac{k-d}{n-k}\binom{n-k}{k}+(-1)^{i}\binom{n-k-i}{k-i}\right)\|\vec{h}_{i}\|^{2}.$

The first inequality uses $\binom{n-k-i}{k-i}\leq\binom{n-k-d-1}{k-d-1}$ for
all $i=d+1,\cdots,k$ and $n\geq 2k$. The second inequality is a direct
consequence from the comparison in Lemma 3.1. The last identity follows from
$|\mathcal{F}|=\|\vec{h}\|^{2}=\sum_{i=0}^{k}\|\vec{h}_{i}\|^{2}.$ ∎

The next lemma is based on the assumption of having large minimum $d$-degree.
It does not require $\mathcal{F}$ to be intersecting.

######  Lemma 3.3.

Suppose $\mathcal{F}$ is a family of $k$-subsets of $[n]$, such that
$\delta_{d}(\mathcal{F})\geq\binom{n-d-1}{k-d-1}$, then the following
inequality holds:

$\displaystyle 0$
$\displaystyle\leq\sum_{j=0}^{d}(-1)^{j}\binom{k-j}{d-j}\binom{n-d-j}{d-j}\binom{n-d-j}{k-d}\|\vec{h}_{j}\|^{2}$
$\displaystyle~{}~{}~{}-2\binom{n-d-1}{k-d-1}\binom{n-d}{d}\binom{k}{d}|\mathcal{F}|+\binom{n-d-1}{k-d-1}^{2}\binom{n}{d}\binom{n-d}{d}.$

Furthermore, the above inequality becomes strict if
$\delta_{d}(\mathcal{F})>\binom{n-d-1}{k-d-1}$.

###### Proof.

Since $d_{S}=d_{S}(\mathcal{F})\geq\binom{n-d-1}{k-d-1}$ for all $|S|=d$, we
have that for all $S,T\in\binom{[n]}{d}$,

$\left(d_{T}-\binom{n-d-1}{k-d-1}\right)\left(d_{S}-\binom{n-d-1}{k-d-1}\right)\geq
0.$

Summing over those (ordered) disjoint pairs, we have

$\displaystyle 0$ $\displaystyle\leq\sum_{S,T:|S|=|T|=d,S\cap
T=\emptyset}\left(d_{T}-\binom{n-d-1}{k-d-1}\right)\left(d_{S}-\binom{n-d-1}{k-d-1}\right)$
$\displaystyle=\vec{D}_{d}^{T}M\vec{D}_{d}-2\binom{n-d-1}{k-d-1}\binom{n-d}{d}\sum_{S:|S|=d}d_{S}+\binom{n-d-1}{k-d-1}^{2}\binom{n}{d}\binom{n-d}{d}.$

Here $M$ is the $\binom{n}{d}$ by $\binom{n}{d}$ matrix with rows and columns
indexed by $d$-subsets of $[n]$, and $M_{S,T}$ equals $1$ if $S\cap
T=\emptyset$ and $0$ otherwise. $\vec{D}_{d}$ stands for the
$\binom{n}{d}$-dimensional vector, whose coordinates record all the
$d$-degrees of $\mathcal{F}$. By double counting, we have
$\sum_{S:|S|=d}d_{S}=\binom{k}{d}|\mathcal{F}|$. So it remains to rewrite the
quadratic part $\vec{D}_{d}^{T}M\vec{D}_{d}$ as a linear combination of
$\|\vec{h}_{i}\|^{2}$’s.

For $0\leq i\leq j\leq k$, we define the $(i,j)$-inclusion matrix $W_{i,j}$ to
be the matrix with rows indexed by all $i$-subsets of $[n]$, columns indexed
by all $j$-subsets of $[n]$, and $(W_{i,j})_{S,T}=1$ if $S\subset T$, and $0$
otherwise. Then we have $\vec{D}_{d}=W_{d,k}\vec{h}.$ Similarly, we also
define the $(i,j)$-disjointness matrix $\overline{W}_{i,j}$ to have
$(S,T)$-entry $1$ if $S\cap T=\emptyset$ and $0$ otherwise. With this
notation, the matrix $M$ in the quadratic form is the same as
$\overline{W}_{d,d}$.

Now we can rewrite the quadratic term $\vec{D}_{d}^{T}M\vec{D}_{d}$ as
$\vec{h}^{T}(W_{d,k}^{T}\overline{W}_{d,d}W_{d,k})\vec{h}$. It is not hard to
see that $W_{d,k}^{T}\overline{W}_{d,d}W_{d,k}$ is an
$\binom{n}{k}\times\binom{n}{k}$ matrix whose $(S,T)$-entry only depends on
$|S\cap T|$. Thus it has the same eigenspace decomposition
$E_{0}\oplus\cdots\oplus E_{k}$ as that of the adjacency matrix of $KG(n,k)$,
and

$\displaystyle W_{d,k}^{T}\overline{W}_{d,d}W_{d,k}$
$\displaystyle=W_{d,k}^{T}\left(\sum_{i=0}^{d}(-1)^{i}W_{i,d}^{T}W_{i,d}\right)W_{d,k}=\sum_{i=0}^{d}(-1)^{i}(W_{i,d}W_{d,k})^{T}W_{i,d}W_{d,k}$
$\displaystyle=\sum_{i=0}^{d}(-1)^{i}\binom{k-i}{d-i}^{2}W_{i,k}^{T}W_{i,k}.$

On the other hand, $E_{j}$ is an eigenspace for the matrix
$W_{i,k}^{T}W_{i,k}$ for its eigenvalue $\binom{k-j}{k-i}\binom{n-i-j}{k-i}$,
which will be proved as Lemma A.1 in Appendix A. Note that this eigenvalue
vanishes whenever $j>i$. Therefore,

$\displaystyle\vec{h}^{T}(W_{d,k}^{T}\overline{W}_{d,d}W_{d,k})\vec{h}$
$\displaystyle=(\sum_{j=0}^{k}\vec{h}_{j})^{T}\left(\sum_{i=0}^{d}(-1)^{i}\binom{k-i}{d-i}^{2}W_{i,k}^{T}W_{i,k}\right)(\sum_{j=0}^{k}\vec{h}_{j})$
$\displaystyle=\sum_{i=0}^{d}(-1)^{i}\binom{k-i}{d-i}^{2}\left(\sum_{j=0}^{i}\binom{k-j}{k-i}\binom{n-i-j}{k-i}\|\vec{h}_{j}\|^{2}\right)$
$\displaystyle=\sum_{j=0}^{d}\|\vec{h}_{j}\|^{2}\cdot\left(\sum_{i=j}^{d}(-1)^{i}\binom{k-i}{d-i}^{2}\binom{k-j}{k-i}\binom{n-i-j}{k-i}\right)$
$\displaystyle=\sum_{j=0}^{d}(-1)^{j}\binom{k-j}{d-j}\binom{n-d-j}{d-j}\binom{n-d-j}{k-d}\|\vec{h}_{j}\|^{2}$

We leave the last equality as Lemma A.2 whose proof is given in the appendix.∎

Now we are ready to prove our main Theorem, the $d$-degree version of the
Erdős–Ko–Rado Theorem.

###### Proof of Theorem 1.1:.

We prove by contradiction, suppose
$\delta_{d}(\mathcal{F})>\binom{n-d-1}{k-d-1}$.

Apply Lemma 3.2 and 3.3 to $\mathcal{F}$ and rewrite the two inequalities
obtained as:

$0\geq\sum_{i=0}^{d}a_{i}\|\vec{h}_{i}\|^{2}-c|\mathcal{F}|,$

and

$0<\sum_{i=0}^{d}b_{i}\|\vec{h}_{i}\|^{2}-f|\mathcal{F}|+g,$

where $a_{i}=\frac{k-d}{n-k}\binom{n-k}{k}+(-1)^{i}\binom{n-k-i}{k-i}$,
$c=\frac{k-d}{n-k}\binom{n-k}{k}$,
$b_{i}=(-1)^{i}\binom{k-i}{d-i}\binom{n-d-i}{d-i}\binom{n-d-i}{k-d}$,
$f=2\binom{n-d-1}{k-d-1}\binom{n-d}{d}\binom{k}{d}$, and
$g=\binom{n-d-1}{k-d-1}^{2}\binom{n}{d}\binom{n-d}{d}$. We subtract the second
inequality by the first inequality multiplied by $b_{1}/a_{1}$. It is not hard
to observe that both $b_{1}$ and $a_{1}=-\frac{d}{n-k}\binom{n-k}{k}$ are
negative. Thus we have

$0<\left(b_{0}-\frac{a_{0}b_{1}}{a_{1}}\right)\|\vec{h}_{0}\|^{2}+\left(\sum_{i=2}^{d}(b_{i}-\frac{a_{i}b_{1}}{a_{1}})\|\vec{h}_{i}\|^{2}\right)-\left(f-\frac{cb_{1}}{a_{1}}\right)|\mathcal{F}|+g.$

We claim the following:

  1. 1.

The coefficient of $\|\vec{h}_{0}\|^{2}$ is
$b_{0}-a_{0}b_{1}/a_{1}=\frac{n(k-d)}{k(n-d)}\cdot b_{0}$, which is strictly
positive.

  2. 2.

For each even integer $2\leq i\leq d$, we have $b_{i}\leq a_{i}b_{1}/a_{1}$ as
long as $n\geq 2k+1$. For each odd integer $3\leq i\leq d$, we have $b_{i}\leq
a_{i}b_{1}/a_{1}$ as long as $n\geq 2k+2d-3$.

  3. 3.

$f-b_{1}c/a_{1}=\frac{2kn-dk-
dn}{k(n-d)}\cdot\binom{n-d-1}{k-d-1}\binom{n-d}{d}\binom{k}{d}.$

Suppose all three claims are true. Note that $\|\vec{h}_{i}\|^{2}\geq 0$, so
using
$\|\vec{h}_{0}\|^{2}=\langle\vec{h}_{0},\frac{\vec{1}}{\sqrt{\binom{n}{k}}}\rangle^{2}=|\mathcal{F}|^{2}/\binom{n}{k}$,
we have

$\displaystyle 0$
$\displaystyle<\frac{n(k-d)}{k(n-d)}\cdot\binom{k}{d}\binom{n-d}{d}\binom{n-d}{k-d}\cdot\frac{|\mathcal{F}|^{2}}{\binom{n}{k}}$
$\displaystyle~{}~{}~{}-\frac{2kn-dk-
dn}{k(n-d)}\cdot\binom{n-d-1}{k-d-1}\binom{n-d}{d}\binom{k}{d}|\mathcal{F}|+\binom{n-d-1}{k-d-1}^{2}\binom{n}{d}\binom{n-d}{d}.$

After simplification, this quadratic inequality is equivalent to

$\displaystyle
0<\left(|\mathcal{F}|-\binom{n-1}{k-1}\right)\left(|\mathcal{F}|-\binom{n-d-1}{k-d-1}\frac{\binom{n}{d}}{\binom{k}{d}}\right),$
(1)

Recall that we assume $\delta_{d}(\mathcal{F})>\binom{n-d-1}{k-d-1}$. This
implies

$|\mathcal{F}|=\frac{\sum_{S:|S|=d}d_{S}}{\binom{k}{d}}>\binom{n-d-1}{k-d-1}\frac{\binom{n}{d}}{\binom{k}{d}}.$

Therefore, we must have $|\mathcal{F}|>\binom{n-1}{k-1}$, contradicting the
Erdős–Ko–Rado Theorem. This completes the proof that
$\delta_{d}(\mathcal{F})\leq\binom{n-d-1}{k-d-1}$ for intersecting family
$\mathcal{F}$.

It remains to verify the three claims we made earlier. The first and third are
done by straightforward calculations:

$\displaystyle b_{0}-\frac{a_{0}b_{1}}{a_{1}}$
$\displaystyle=b_{0}\left(1-\frac{a_{0}}{a_{1}}\cdot\frac{b_{1}}{b_{0}}\right)=b_{0}\left(1-\frac{\frac{n-d}{n-k}\binom{n-k}{k}}{\frac{-d}{n-k}\binom{n-k}{k}}\cdot\frac{-\binom{k-1}{d-1}\binom{n-d-1}{d-1}\binom{n-d-1}{k-d}}{\binom{k}{d}\binom{n-d}{d}\binom{n-d}{k-d}}\right)$
$\displaystyle=b_{0}\cdot\left(1-\frac{n-d}{d}\cdot\frac{d}{k}\cdot\frac{d}{n-d}\cdot\frac{n-k}{n-d}\right)=b_{0}\cdot\frac{n(k-d)}{k(n-d)}.$
$\displaystyle f-\frac{b_{1}c}{a_{1}}$
$\displaystyle=2\binom{n-d-1}{k-d-1}\binom{n-d}{d}\binom{k}{d}-\frac{\frac{k-d}{n-k}\binom{n-k}{k}\cdot\binom{k-1}{d-1}\binom{n-d-1}{d-1}\binom{n-d-1}{k-d}}{\frac{d}{n-k}\binom{n-k}{k}}$
$\displaystyle=\binom{n-d-1}{k-d-1}\binom{n-d}{d}\binom{k}{d}\cdot\left(2-\frac{k-d}{d}\cdot\frac{d}{k}\cdot\frac{d}{n-d}\cdot\frac{n-k}{k-d}\right)$
$\displaystyle=\binom{n-d-1}{k-d-1}\binom{n-d}{d}\binom{k}{d}\cdot\frac{2kn-
dk-dn}{k(n-d)}.$

To verify the second claim, since $a_{1},b_{1}<0$, it suffice to prove for
$i=2,\cdots,d$, $b_{i}/(-b_{1})\leq a_{i}/(-a_{1})$. We plug in the values of
$a_{1},b_{1},a_{i},b_{i}$. Denote by $(x)_{i}$ the falling factorial
$x(x-1)\cdots(x-i+1)$, then

$\frac{a_{i}}{-a_{1}}=\frac{\frac{k-d}{n-k}\binom{n-k}{k}+(-1)^{i}\binom{n-k-i}{k-i}}{\frac{d}{n-k}\binom{n-k}{k}}=\frac{k-d+(-1)^{i}\cdot
k\cdot\frac{(k-1)_{i-1}}{(n-k-1)_{i-1}}}{d}.$
$\frac{b_{i}}{-b_{1}}=(-1)^{i}\cdot\frac{\binom{k-i}{d-i}\binom{n-d-i}{d-i}\binom{n-d-i}{k-d}}{\binom{k-1}{d-1}\binom{n-d-1}{d-1}\binom{n-d-1}{k-d}}=(-1)^{i}\cdot\frac{[(d-1)_{i-1}]^{2}\cdot(n-k-1)_{i-1}}{[(n-d-1)_{i-1}]^{2}\cdot(k-1)_{i-1}}.$

Therefore the inequality $b_{i}/(-b_{1})\leq a_{i}/(-a_{1})$ we would like to
establish can be rewritten as

$(-1)^{i}\left[d\cdot\frac{[(d-1)_{i-1}]^{2}\cdot(n-k-1)_{i-1}}{[(n-d-1)_{i-1}]^{2}\cdot(k-1)_{i-1}}-k\cdot\frac{(k-1)_{i-1}}{(n-k-1)_{i-1}}\right]\leq
k-d.$

We define

$S_{i}(n)=\frac{(k-1)_{i-1}}{(n-k-1)_{i-1}},~{}~{}~{}T_{i}(n)=\frac{[(d-1)_{i-1}]^{2}\cdot(n-k-1)_{i-1}}{[(n-d-1)_{i-1}]^{2}\cdot(k-1)_{i-1}}.$

Since $k>d$, we have $(d-1)_{i-1}<(k-1)_{i-1}$ and
$(n-d-1)_{i-1}>(n-k-1)_{i-1}$. It is not hard to see that $S_{i}(n)>T_{i}(n)$
for $i\geq 2$. This implies that when $i$ is even, the left hand side is
negative, so this inequality is automatically true in that case. We remark
that this simple observation already shows the $2$-degree Erdős–Ko–Rado
Theorem holds for every $n\geq 2k+1$.

Now suppose $i$ is odd and thus $i\geq 3$. We would need to show that

$k\cdot S_{i}(n)-d\cdot T_{i}(n)\leq k-d.$

The proof of this last inequality is somewhat technical, so we leave it to the
appendix as Lemma A.3. ∎

##  4 Concluding Remarks

In this paper, we show that the $d$-degree analogue of the Erdős–Ko–Rado
Theorem holds for $n\geq 2k+2d-3$. On the other hand, we are not aware of any
construction strictly beating the $1$-star construction, in the range of
$n\geq 2k+1$. In [9], it was shown that for every $n\geq 2k+1$, the $1$-star
is the unique example with $\delta_{1}=\binom{n-2}{k-2}$. However this fails
to be the case for larger $d$. The simplest example is to take a Fano plane
for $n=7$ and $k=3$. The minimum $2$-degree is equal to $1$, while the
$1$-star also has minimum degree $\binom{n-3}{k-3}=1$ in this case. For the
next case $(n,k,d)=(9,4,2)$, a more sophisticated construction by Östergård
[13] gives an intersecting family $\mathcal{F}\subset\binom{[9]}{4}$ that has
$\delta_{2}(\mathcal{F})=6=\binom{n-3}{k-3}$. This example is obtained from
gluing three copies of the $2$-$(6,3,2)$ design mentioned in the introduction.
More discussions on the $n=2k+1$ case can be found in [10].

Even though unlike the $d=1$ case, the uniqueness no longer holds for $d=2$
and $n=2k+1$, the following conjecture is still plausible and has been now
verified for $d\in\\{0,1,2\\}$.

######  Conjecture 4.1.

For every $k>d\geq 0$ and $n\geq 2k+1$, an intersecting family
$\mathcal{F}\subset\binom{[n]}{k}$ always has minimum $d$-degree

$\delta_{d}(\mathcal{F})\leq\binom{n-d-1}{k-d-1}.$

Here let we mention one possible approach to further lower the threshold.
Recall that Lemma 3.2 works even if we replace $\frac{k-d}{n-k}\binom{n-k}{k}$
by any constant at least $\binom{n-k-d-1}{k-d-1}$. It is possible that by
selecting a different constant in Lemma 3.2, after subtracting the two
inequalities given by Lemma 3.2 and Lemma 3.3 in the proof of Theorem 1.1, one
could have the coefficient of not just $\|\vec{h}_{1}\|^{2}$, but also that of
$\|\vec{h}_{3}\|^{2}$ to vanish, while still keeping all the other
coefficients of $\|\vec{h}_{i}\|^{2}$ non-positive. Such more careful analysis
may further lower the threshold needed for $n$, possibly solving for the range
$n\geq 2k+cd$ for a smaller $c$. But we believe that if Conjecture 4.1 is
indeed true, some new ideas are necessary to cover the whole range $n\geq
2k+1$.

One can also ask a more general question: for a given family
$\mathcal{G}\subset 2^{[n]}$, when can we guarantee that any intersecting
subfamily $\mathcal{F}\subset\mathcal{G}$ has
$\delta_{d}(\mathcal{F})\leq\max_{i\in[n]}\delta_{d}(\mathcal{G}_{i})$? Here
$\mathcal{G}_{i}$ is the family of subsets of $\mathcal{G}$ that contains $i$.
Theorem 1.1 shows that $\mathcal{G}=\binom{[n]}{k}$ has such property for
$d\geq 2$ and $n\geq 2k+2d-3$. On the other hand for $d=0$, Chvátal [1]
conjectured that as long as $\mathcal{G}$ is hereditary, meaning that whenever
$A\subset B$ and $B\in\mathcal{G}$ then $A\in\mathcal{G}$, then such
inequality holds. One might want to guess that this also works for $d\geq 1$.
However we can just take $\mathcal{G}=2^{[n]}$ and
$\mathcal{F}=\binom{[n]}{\geq(n+1)/2}$ for odd $n$. It is not hard to see that
$\delta_{d}(\mathcal{F})>\delta_{d}(\mathcal{G}_{i})$ for every $i\in[n]$. It
would be very interesting to find the right assumptions that may generalize
Chvátal’s conjecture to the $d$-degree case.

##  Appendix A Technical lemmas

In this appendix, we give the proofs of several technical lemmas used in the
paper. Recall that the $(i,j)$-inclusion matrix $W_{i,j}$ is the matrix with
rows indexed by all $i$-subsets of $[n]$, columns indexed by all $j$-subsets
of $[n]$, and $(W_{i,j})_{S,T}=1$ if $S\subset T$, and $0$ otherwise. And the
$(i,j)$-disjointness matrix $\overline{W}_{i,j}$ has $(S,T)$-entry $1$ if
$S\cap T=\emptyset$ and $0$ otherwise. It is not hard to see that they have
the same row space.

######  Lemma A.1.

Take any column vector $\vec{v}\in E_{j}\subset\mathbb{R}^{\binom{n}{k}}$,
then for $j>i$ we have $W_{i,k}^{T}W_{i,k}\vec{v}=0$, and for $0\leq j\leq i$,

$W_{i,k}^{T}W_{i,k}\vec{v}=\binom{k-j}{k-i}\binom{n-i-j}{k-i}\vec{v}$

###### Proof.

As discussed in Section 2, $E_{j}$ is the orthogonal complement of $F_{j-1}$
in $F_{j}$. And $F_{j}$ is spanned by the indicating vectors of all the
$j$-stars. Therefore, $W_{j-1,k}\vec{v}=0$, and $\vec{v}=W_{j,k}^{T}\vec{u}$
for some $\vec{u}\in\mathbb{R}^{\binom{n}{j}}.$ Therefore for $j>i$,

$W_{i,k}\vec{v}=\frac{W_{i,j-1}W_{j-1,k}}{\binom{k-i}{j-1-i}}\cdot\vec{v}=\vec{0}.$

For $\ell<j$, note that $W_{\ell,k}$ and $\overline{W}_{\ell,k}$ have the same
row spaces. Since $\vec{v}$ is in the orthogonal complement of $F_{\ell}$, we
know that $W_{\ell,k}\vec{v}=\vec{0}$ and thus we also have
$\overline{W}_{\ell,k}\vec{v}=\vec{0}$. Using $\vec{v}=W_{j,k}^{T}\vec{u}$, we
have

$\vec{0}=\overline{W}_{\ell,k}W_{j,k}^{T}\vec{u}=\binom{n-\ell-j}{k-j}\overline{W}_{\ell,j}\vec{u}.$

Again since $W_{\ell,j}$ and $\overline{W}_{\ell,j}$ have the same row spaces,
we have $W_{\ell,j}\vec{u}=\vec{0}$ whenever $\ell<j$.

Now for $j\leq i$, we apply the following identity (6.11 from Page 124 of
[8]):

$\displaystyle
W_{i,k}W_{j,k}^{T}=\sum_{\ell=0}^{j}\binom{n-i-j}{n-k-\ell}W_{\ell,i}^{T}W_{\ell,j}.$

From the above discussions, $W_{\ell,j}\vec{u}=0$ whenever $\ell<j$, therefore

$\displaystyle W_{i,k}^{T}W_{i,k}\vec{v}$
$\displaystyle=W_{i,k}^{T}W_{i,k}W_{j,k}^{T}\vec{u}=\sum_{\ell=0}^{j}\binom{n-i-j}{n-k-\ell}W_{i,k}^{T}W_{\ell,i}^{T}W_{\ell,j}\vec{u}$
$\displaystyle=\sum_{\ell=0}^{j}\binom{n-i-j}{n-k-\ell}\binom{k-\ell}{k-i}W_{\ell,k}^{T}W_{\ell,j}\vec{u}$
$\displaystyle=\binom{n-i-j}{n-k-j}\binom{k-j}{k-i}W_{j,k}^{T}W_{j,j}\vec{u}=\binom{n-i-j}{n-k-j}\binom{k-j}{k-i}\vec{v},$

which completes the proof of this lemma. ∎

######  Lemma A.2.

For integers $j\leq d<k\leq n/2$,we have

$\sum_{i=j}^{d}(-1)^{i}\binom{k-i}{d-i}^{2}\binom{k-j}{k-i}\binom{n-i-j}{k-i}=(-1)^{j}\binom{k-j}{d-j}\binom{n-d-j}{d-j}\binom{n-d-j}{k-d}.$

###### Proof.

We divide the left hand side by the right hand side. After canceling terms,
the identity we would like to prove is equivalent to

$\sum_{i=j}^{d}(-1)^{i-j}\frac{\binom{d-j}{i-j}\binom{n-i-j}{d-i}}{\binom{n-d-j}{n-2d}}=1.$

This identity follows from comparing the coefficients of $x^{d-j}=x^{i-j}\cdot
x^{d-i}$ in the expansions of the following two equal generating functions at
$x=0$:

$(1-x)^{d-j}\cdot(1-x)^{-(n-d-j+1)}=(1-x)^{-(n-2d+1)}.$

∎

######  Lemma A.3.

Suppose $k>d\geq i\geq 3$ and $n\geq 2k+2d-3$, let

$S_{i}(n)=\frac{(k-1)_{i-1}}{(n-k-1)_{i-1}},~{}~{}~{}~{}T_{i}(n)=\frac{[(d-1)_{i-1}]^{2}\cdot(n-k-1)_{i-1}}{[(n-d-1)_{i-1}]^{2}\cdot(k-1)_{i-1}},$

where $(x)_{i}$ is the falling factorial $(x)_{i}=x(x-1)\cdots(x-i+1)$. Then
the following inequality holds:

$k\cdot S_{i}(n)-d\cdot T_{i}(n)\leq k-d.$

###### Proof.

It is not hard to see that $0<T_{i}(n)<S_{i}(n)\leq 1$ since $n>2k$ and $k>d$.
Furthermore, since $d<k$, we have

$\frac{S_{i}(n+1)}{S_{i}(n)}=\frac{n-k-i+1}{n-k}\leq\left(\frac{n-d-i+1}{n-d}\right)^{2}\cdot\frac{n-k}{n-k-i+1}=\frac{T_{i}(n+1)}{T_{i}(n)}.$

Thus suppose $k\cdot S_{i}(n)-d\cdot T_{i}(n)\leq k-d$, we can immediately get

$k\cdot S_{i}(n+1)-d\cdot T_{i}(n+1)\leq(k\cdot S_{i}(n)-d\cdot
T_{i}(n))\cdot\frac{S_{i}(n+1)}{S_{i}(n)}\leq k\cdot S_{i}(n)-d\cdot
T_{i}(n)\leq k-d.$

Therefore for fixed parameters $k,d$ and $i$, it suffices to verify the
inequality $k\cdot S_{i}(n)-d\cdot T_{i}(n)\leq k-d$ for the base case
$n=2k+2d-3$, and then the proof for larger $n$ follows by induction.

Fix $k,d$ and $n=2k+2d-3$, we let

$\alpha_{i}=\frac{(k-1)_{i-1}}{(n-k-1)_{i-1}},~{}~{}~{}~{}\beta_{i}=\frac{(d-1)_{i-1}}{(n-d-1)_{i-1}}.$

Then $S_{i}=\alpha_{i}$, $T_{i}=\beta_{i}^{2}/\alpha_{i}$. We first show that
$kS_{i}-dT_{i}$ decreases in $i$. First note that
$\alpha_{i+1}/\alpha_{i}=(k-i)/(n-k-i)<1$, and similarly
$\beta_{i+1}/\beta_{i}<1$. So $\\{\alpha_{i}\\}$ and $\\{\beta_{i}\\}$ are
both decreasing in $i$. Furthermore,

$\alpha_{i}-\alpha_{i+1}=\alpha_{i}(1-\frac{k-i}{n-k-i})=\frac{n-2k}{n-k-i}\cdot\alpha_{i}=\frac{(k-1)_{i-1}(n-2k)}{(n-k-1)_{i}},$

and similarly $\beta_{i}-\beta_{i+1}=\frac{(d-1)_{i-1}(n-2d)}{(n-d-1)_{i}}.$
Since $i\geq 3$, it is straightforward to check that
$(n-2k)(k-1)(k-2)\geq(n-2d)(d-1)(d-2)$ for $n=2k+2d-3$. Therefore using $k>d$
again, we have

$\displaystyle\alpha_{i}-\alpha_{i+1}$
$\displaystyle=\frac{(k-3)_{i-3}}{(n-k-1)_{i}}\cdot(k-1)(k-2)(n-2k)$
$\displaystyle\geq\frac{(d-3)_{i-3}}{(n-d-1)_{i}}\cdot(d-1)(d-2)(n-2d)=\beta_{i}-\beta_{i+1}.$

This shows $\alpha_{i}-\beta_{i}$ decreases in $i$. On the other hand,

$\frac{\beta_{i+1}/\alpha_{i+1}}{\beta_{i}/\alpha_{i}}=\frac{(d-i)/(n-d-i)}{(k-i)/(n-k-i)}<1,$

so $\beta_{i}/\alpha_{i}$ also decreases in $i$. We immediately know that

$k\cdot S_{i}-d\cdot
T_{i}=(k-d)S_{i}+d(S_{i}-T_{i})=(k-d)\alpha_{i}+d(\alpha_{i}-\beta_{i})(1+\frac{\beta_{i}}{\alpha_{i}})$

also decreases in $i$. Thus to show $kS_{i}-dT_{i}\leq k-d$, it suffices to
check for $i=3$. For this case, the inequality we would like to prove is
equivalent to

$d(\alpha_{3}-\beta_{3})(1+\frac{\beta_{3}}{\alpha_{3}})\leq(k-d)(1-\alpha_{3}).$

Calculations give that

$1-\alpha_{3}=1-\frac{(k-1)(k-2)}{(n-k-1)(n-k-2)}=\frac{(n-3)(n-2k)}{(n-k-1)(n-k-2)}.$
$\alpha_{3}-\beta_{3}=\frac{(k-d)(n-3)((k+d-3)n-2dk+4)}{(n-k-1)(n-k-2)(n-d-1)(n-d-2)}.$
$\displaystyle 1+\frac{\beta_{3}}{\alpha_{3}}$
$\displaystyle=1+\frac{(d-1)(d-2)/(n-d-1)(n-d-2)}{(k-1)(k-2)/(n-k-1)(n-k-2)}$
$\displaystyle\leq 1+\frac{(d-1)(d-2)}{(k-1)(k-2)}$ $\displaystyle\leq
1+\frac{((k-1)-1)((k-1)-2)}{(k-1)(k-2)}$
$\displaystyle=1+\frac{k-3}{k-1}=\frac{2k-4}{k-1}.$

Combining these observations, it suffices to prove for $n=2k+2d-3$,

$\frac{d(2k-4)((k+d-3)n-2dk+4)}{(k-1)(n-d-1)(n-d-2)}\leq n-2k$

Plugging in $n=2k+2d-3,$ it becomes

$(4d-12)k^{3}+(4d^{2}-30d+66)k^{2}-(2d^{3}+3d^{2}-53d+114)k+(6d^{3}-15d^{2}-15d+60)\geq
0$

Since $d\geq 3$, it is easy to verify that $4d-12\geq 0$, $4d^{2}-30d+66\geq
0$. Thus using $k\geq d+1$, the left hand side is at least

$\displaystyle
k((4d-12)(d+1)^{2}+(4d^{2}-30d+66)(d+1)-2d^{3}-3d^{2}+53d-114)+(6d^{3}-15d^{2}-15d+60)$
$\displaystyle=(6d^{3}-33d^{2}+69d-60)k+(6d^{3}-15d^{2}-15d+60)$

It is not hard to check that when $d\geq 3$, both terms in the expression
above are again non-negative. This completes the proof. ∎

## References

  * [1] V. Chvátal,  Intersecting families of edges in hypergraphs having the hereditary property, Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), 61–66. Lecture Notes in Math., Vol. 411, Springer, Berlin, 1974.
  * [2] M. Deza and P. Frankl, Erdős–Ko–Rado theorem—22 years later. SIAM J. Algebraic Discrete Methods 4 (1983), no. 4, 419–431.
  * [3] P. Erdős, C. Ko and R. Rado,  Intersection theorems for systems of finite sets,  Quart. J. Math. Oxford Ser. (2) , 12 (1961), 313–318.
  * [4] P. Frankl, Erdős–Ko–Rado theorem with conditions on the maximal degree. J. Combin. Theory Ser. A 46 (1987), no. 2, 252–263.
  * [5] P. Frankl and R. L. Graham, Old and new proofs of the Erdős–Ko–Rado theorem. Sichuan Daxue Xuebao 26 (1989), 112–122.
  * [6] P. Frankl, J. Han, H. Huang, Y. Zhao,  A degree version of the Hilton-Milner Theorem,  Journal of Combinatorial Theory, Series A, 155 (2018), 493–502.
  * [7] P. Frankl and N. Tokushige,  A note on Huang–Zhao theorem on intersecting families with large minimum degree,  Discrete Mathematics, 340(5) (2017), 1098–1103.
  * [8] C. Godsil and K. Meagher,  Erdős–Ko–Rado Theorems: Algebraic Approaches,  Number 149 in Cambridge Studies in Advanced Mathematics. Cambridge Univ. Press, December 2016.
  * [9] H. Huang and Y. Zhao,  Degree versions of the Erdős-Ko-Rado Theorem and Erdős hypergraph matching conjecture,  Journal of Combinatorial Theory, Ser. A, 150 (2017), 233–247.
  * [10] F. Ihringer, A. Kupavskii,  Regular intersecting families,  Discrete Applied Mathematics 270 (1) (2019), 142–152.
  * [11] A. Kupavskii,  Degree versions of theorems on intersecting families via stability,  Journal of Combinatorial Theory, Ser. A, 168 (2019), 272–287.
  * [12] László Lovász,  On the Shannon capacity of a graph,  IEEE Trans. Inform. Theory, 25 (1979), 1–7.
  * [13] P. Östergård,  There are 270,474,142 non-isomorphic $2$-$(9,4,6)$ designs,  Journal of Combinatorial Mathematics and Combinatorial Computing, 37 (2001), 173–176.
  * [14] V. Rödl and A. Ruciński, Dirac-type questions for hypergraphs – a survey (or more problems for Endre to solve), _An Irregular Mind (Szemerédi is 70)_ , Bolyai Soc. Math. Studies 21 (2010), 1–30.
  * [15] R. Wilson,  The exact bound in the Erdős–Ko–Rado theorem,  Combinatorica, 4 (1984), 247–257.
  * [16] Y. Zhao,  Recent advances on Dirac-type problems for hypergraphs.  Recent Trends in Combinatorics,  the IMA Volumes in Mathematics and its Applications 159, Springer, New York 2016.


# Automated System Performance Testing at MongoDB

Henrik Ingo<EMAIL_ADDRESS>0000-0003-1571-5108 MongoDB Inc and
David Daly<EMAIL_ADDRESS>0000-0001-9678-3721 MongoDB Inc

(2020)

###### Abstract.

Distributed Systems Infrastructure (DSI) is MongoDB’s framework for running
fully automated system performance tests in our Continuous Integration (CI)
environment. To run in CI it needs to automate everything end-to-end:
provisioning and deploying multi-node clusters, executing tests, tuning the
system for repeatable results, and collecting and analyzing the results. Today
DSI is MongoDB’s most used and most useful performance testing tool. It runs
almost 200 different benchmarks in daily CI, and we also use it for manual
performance investigations. As we can alert the responsible engineer in a
timely fashion, all but one of the major regressions were fixed before the
4.2.0 release. We are also able to catch net new improvements, of which DSI
caught 17. We open sourced DSI in March 2020.

Databases, Distributed Databases, Testing, Performance, MongoDB, Python, Cloud

††journalyear: 2020††copyright: none††conference: Author Preprint;
Arxiv††booktitle: ;††doi: …/…††isbn: -††ccs: Software and its engineering
Acceptance testing††ccs: General and reference Performance††ccs: General and
reference Validation††ccs: Information systems Parallel and distributed
DBMSs††ccs: Computer systems organization Cloud computing

Figure 1. Timeseries of daily build results for YCSB load

Timeseries of daily build results for YCSB load

##  1\. Introduction

MongoDB created a dedicated performance testing team in 2013. The first
approach was to build a team of systems engineers and performance experts that
would manually benchmark new releases of MongoDB, and was found to be
problematic. It was not scalable, and it also had issues with repeatability.

The focus then shifted to running system performance tests in a daily
Continuous Integration (CI) build, just like is done for any other testing.
But where all our other tests can run on a single server, the system
performance builds needed to deploy realistic MongoDB clusters in EC2.
Initially this was accomplished by moving some shell scripts, and
Terraform(Ter, [n.d.]) config files, from the manual benchmarking, into the CI
configuration.

From these humble beginnings arose a software development project to design
and rewrite the same system more properly in Python. The framework was called
Distributed System Infrastructure, or DSI for short.

In this paper, we present the architecture and design of this framework and
results from using it to benchmark MongoDB. DSI is used in MongoDB to run
hundreds of automated benchmarks per day. The benchmarks in CI are fully
automated end-to-end: provisioning EC2 infrastructure and deploying the
MongoDB cluster, orchestrating test execution, and collecting and analyzing
results. It is also used by engineers to create new tests, reproduce results
from CI and manual ”explorative” benchmarking. Since 2018, DSI is our most
used and most useful performance testing tool. We have open sourced it in
March 2020 (DSI, [n.d.]).

##  2\. Problem Definition

The focus for DSI was serving the more complex requirements of end-to-end
system performance tests on real clusters, automating every step including
provisioning of hardware, and generating consistent, repeatable results.

More specifically, the high level goals of the project were:

  1. (1)

Full end-to-end automation.

  2. (2)

Support both CI and manual benchmarking.

  3. (3)

Elastic, public cloud infrastructure.

  4. (4)

Everything configurable.

  5. (5)

All configuration is via a single, consistent, YAML based system.

  6. (6)

Clear modularity for executables and configuration.

  7. (7)

Diagnosability.

  8. (8)

Repeatability.

###  2.1. Configuration

The main design goal was to move from a model where each new configuration
required a new shell script, to a model where everything was driven by
configuration files and no code changes would be needed to add a new MongoDB
configuration or test.

Further, even for parts that had configuration files, it was becoming tedious
to deal with so many of them. Terraform has JSON-like configuration files.
MongoDB configuration files are in YAML. YCSB(YCS, [n.d.]) configuration is a
Java properties file. We wanted all configuration to be in one place and in a
homogeneous format so that a user could easily understand the whole
configuration.

We also wanted to avoid redundancy in configuration. When Terraform needs an
SSH key to connect to the hosts, and when we later use SFTP to collect log
files, both of these operations should use the same SSH key and it should
exist in the configuration only once.

We wanted maximum flexibility. The framework needed to support any
infrastructure, any possible MongoDB configuration option, any cluster
topology, including deploying more than a single cluster, and needed to be
capable of executing any benchmark software.

The configuration also needed to be modular. It must be possible to execute
the same YCSB test against different MongoDB configurations, and it must be
possible to use the same MongoDB configuration on different hardware.

We also needed to be able to document and trace every bit of configuration. A
common organizational setup is a separate team that develops and deploys the
operating system images. If that team changes the image without the developers
or performance experts noticing, and such changes lead to performance changes,
then much time can be wasted as engineers futilely try to diagnose a change
they do not have visibility into. We use vanilla OS images available in EC2.
All operating system configuration is done by scripts that are part of DSI.
This means that the entire configuration, and changes to it, can be reviewed
from a single commit history.

While developing DSI, we learned that our system performance testing also had
issues with repeatability of test results. So as a parallel project we learned
to configure EC2, Linux and the tests themselves to minimize system noise. We
have reported on this work previously in (Ingo and Daly, 2019). DSI
encapsulates the results of that work in its configuration. When MongoDB
engineers use DSI for performance testing, they automatically deploy systems
configured for minimal noise and maximum repeatability.

###  2.2. Cloud-first

In 2016 MongoDB was already heavily invested in using public cloud
infrastructure for testing and CI. We had even developed our own CI system,
Evergreen(Erf, 2016), to replace Jenkins(Smart, 2011) with a system where
everything was built from the ground up to use elastic cloud resources. As
commits tend to happen during daytime, the need for CI builds varies over the
day. To minimize the turnaround time from commit to a completed CI build, we
try to parallelize test execution as much as possible.

For system performance testing, the elasticity of cloud infrastructure is even
more valuable. We want to test realistic clusters. A weekly build over a
cluster with 3 shards has 16 servers. To test scaling to the largest instance
sizes we occasionally have tested servers with 96 CPUs or 500 GB of RAM. To
procure such servers as on-premise hardware would not be realistic.

At the start of the project, an open question was whether public cloud
infrastructure could be relied on for performance testing at all. We found
when comparing on-premise and cloud that there was no difference in terms of
repeatable performance (Ingo and Daly, 2019).

###  2.3. Diagnosability

The primary use case is to run daily CI builds on public cloud servers. This
requires full end-to-end automation.

A challenge in diagnosing regressions and test errors, is that by the time a
human is looking at the results, the servers are no longer available. For
example, we once had a failure where the storage engine aborted during a test.
A possible reason for the abort could simply be that the disk was full. But we
had no way to know whether the disk had been full.

At the end of the test, DSI therefore collects all the log files back to the
control host, before the test cluster is terminated. The results are then
uploaded to S3. Around 2017 the MongoDB server had itself developed rather
sophisticated metrics collection. Full Time Diagnostic Data Capture (FTD,
[n.d.]) collects over a thousand metrics, including system level metrics like
CPU, disk, network, and memory utilization. All we needed to do was to save
those files. To augment these metrics, we also borrowed a script used by our
support team (mdi, [n.d.]) which collects additional information from the
host, such as how full the disks are.

An important question, when diagnosing test results, is to verify what
configuration exactly was used for the test. Therefore the DSI input
configuration is added to the same archive file as the logs and test results.
This configuration can also be used to reproduce the regression if required.

###  2.4. Support manual benchmarking outside of CI

In addition to running benchmarks in Evergreen, DSI also needs to be usable on
its own. This is important both for engineers developing DSI itself, and for
MongoDB engineers who need to reproduce and diagnose performance issues
assigned to them. This requirement may seem obvious, but at the start of the
project, the shell script based system was so entangled with the evergreen
configuration file, that it had become practically impossible to reproduce
tests outside of Evergreen. It was faster to submit a new CI job than to try
to execute the same manually!

As these system-level tests are complex and have many parameters, commands
that did support command line options could often stretch up to 3 lines. We
felt this was poor usability, and in fact went against the goal of easy
reproducibility of tests, as it was easy to miss some option. As a result, we
decided to ban command line options completely, and force all options into
configuration files. This also ensured a full audit trail, since configuration
files would be archived after each test, while command line options may not be
recorded anywhere.

The Evergreen configuration for MongoDB system performance tests is stored in
the MongoDB source code repository (sys, [n.d.]), while DSI itself is its own
repository. This often led to situations where a change had to be committed
part to DSI, part to MongoDB, and in the latter case often to 3 different
stable branches too. This added both unnecessary complexity and stress. A
high-priority goal was for the interface between the two repositories to be as
minimal and stable as possible.

##  3\. High Level Architecture

Based on experience from the existing system, we could identify eight separate
modules, that together constitute a full execution of one or more benchmarks.

#### Bootstrap

As the system began to take shape, we realized that automating some repetitive
setup tasks from the beginning made sense: Copying the configuration files
into place, finding EC2 credentials, installing correct version of Terraform.
This evolved into the bootstrap module.

The bootstrap.yml configuration file acts as the interface between the MongoDB
repository and the DSI repository. It declares the composition of
configuration files wanted for all the other modules. For example: YCSB on a
three-node replica set. Those other configuration files are stored inside DSI
repository. Thus, the details of each configuration is abstracted away from
the MongoDB repository.

#### Infrastructure provisioning

Infrastructure provisioning uses Terraform to deploy EC2 resources. The DSI
configuration, in YAML format, is significantly simpler than the Terraform
files used behind the scenes. It also ensures that if the deployment fails,
the Terraform destroy command is called to cleanup any half-deployed
resources.

#### System setup

As of this writing, system setup was never implemented as its own top level
executable. It remains a ”remote script” executed by Terraform. One drawback
is that it is therefore unaware of the rich DSI configuration files and
essentially installs the same software and formats the same disks each time.

#### Workload setup

This module installs dependencies for the specific test, such as Java for
YCSB(YCS, [n.d.]) and Linkbench(Armstrong, 2013). An interesting question was
whether workload setup should happen before or after MongoDB setup. Some tests
need to provision a data directory, and this must be done before MongoDB
starts. Other tests need to specify a shard key, and this must be done against
a running MongoDB cluster. In the end we came to the conclusion that
workload_setup is run first, and the test control module offers pre_task and
pre_test hooks to cover for the second use case.

#### MongoDB setup

MongoDB setup deploys one or more MongoDB clusters.

#### Test control

The test control module supports several in-house and third-party benchmark
tools. In addition to running the benchmark itself, it supports the
aforementioned pre_task and pre_test hooks. After the test it collects a
number of log files and diagnostics back to the control host.

#### Analysis

Analysis of results comes in two parts. Our main interest is to determine
whether benchmark results deviate from some recent history of results, and
secondarily from past releases. We eventually concluded that this question is
better answered by signal processing algorithms that look at our daily results
holistically as a timeseries, rather than focusing on the single point in time
that is the currently finished benchmark result. We have reported on this work
in (Daly et al., 2020). These algorithms are developed and executed separately
from DSI.

Some static checks remain in DSI: Does the MongoDB server log file contain
errors or stack traces, or are there core files on the cluster hosts, etc? The
scope of DSI is therefore everything that concerns a single system performance
task execution. Anything that requires historical data as input is in the
signal processing project.

#### Infrastructure teardown

Infrastructure teardown uses Terraform to release the cloud resources.

The modules should be executed in the above order. To allow for flexibility
and modularity, it is however allowed to skip some. For example, a user who
wants to test an existing MongoDB cluster could just point test_control
directly at that.

##  4\. Implementation

The analysis code was already written in Python. We ended up writing the other
modules in Python as well. Maybe it was mostly as a function of gravity, but
we have found Python a rather suitable language for this task. The combination
of being a real programming language and yet a scripting language that does
not require compilation has afforded a lot of flexibility during the active
development phase.

###  4.1. Configuration

The configuration files are the heart of DSI. Since we do not allow command
line options at all, the configuration files are essentially the user
interface. The docs/ directory in the source code (DSI, [n.d.]) documents all
the available configuration options. The configurations/ directory contains a
growing selection of canned configurations, including all configurations used
by daily CI builds.

As mentioned in the design goals (see 2.1), ideally we wanted all
configuration in one big file, but modularity requires that users can mix and
match different configurations. The actual implementation has one YAML
configuration file for each module: infrastructure_provisioning.yml,
workload_setup.yml, etc…

To ensure that all modules read the configuration in a consistent way, a
library is used to access the configuration. The library reads all the YAML
files into one big Python dictionary structure. So from the DSI developer’s
perspective it truly is like all configuration was provided from a single big
YAML file. The same library also provides various additional functionality.
All defaults are centralized in a defaults.yml file, from which a default
value is transparently returned when the actual config file does not specify a
value. Since YAML anchors cannot be used between different YAML files, the
library also provides a ${variable.reference} syntax to reference one
configuration value from another part of the configuration.

Listing 1: mongodb_setup.yml

⬇

1mongod_config_file:

2 storage:

3 engine: wiredTiger

4 replication:

5 replSetName: rs0

6

7topology:

8 - cluster_type: replset

9 id: rs0

10 mongod:

11 - public_ip: ${infrastructure_provisioning.out.mongod.0.public_ip}

12 - public_ip: ${infrastructure_provisioning.out.mongod.1.public_ip}

13 - public_ip: ${infrastructure_provisioning.out.mongod.2.public_ip}

14

15# Meta data about this mongodb setup

16meta:

17 # The list of hosts that can be used in a mongodb connection string

18 hosts: ${mongodb_setup.topology.0.mongod.0.private_ip}:27017

19 hostname: ${mongodb_setup.topology.0.mongod.0.private_ip}

20 mongodb_url: mongodb://${mongodb_setup.meta.hosts}/test?replicaSet=rs0

21 is_replset: true

Listing 2: test_control.yml

⬇

1run:

2 - id: ycsb_load

3 type: ycsb

4 cmd: ./bin/ycsb load mongodb -s -P ../../workloadEvergreen -threads 8

5 config_filename: workloadEvergreen

6 workload_config: |

7 mongodb.url=${mongodb_setup.meta.mongodb_url}

8 recordcount=5000000

9 workload=com.yahoo.ycsb.workloads.CoreWorkload

10 - id: ycsb_100read

11 type: ycsb

12 cmd: ./bin/ycsb run mongodb -s -P ../../workloadEvergreen_100read -threads
32

13 config_filename: workloadEvergreen_100read

14 workload_config: |

15 mongodb.url=${mongodb_setup.meta.mongodb_url}

16 recordcount=5000000

17 maxexecutiontime=240

18 workload=com.yahoo.ycsb.workloads.CoreWorkload

19 readproportion=1.0

Listings 1 and 2 show two simplified configuration files. Keys
mongod_config_file and workload_config embed literal MongoDB and YCSB
configuration files. When executing the benchmark, DSI will extract these into
their own files, that are used as input to mongod and ycsb respectively.

Since we do not know the IP address of an EC2 host ahead of time, the
infrastructure_provisioning module will store that information in a special
.out.yml file. The MongoDB topology configuration uses those IP addresses via
references. The config library resolves these automatically.

The meta section facilitates the modular mixing of config files. Since the
MongoDB URL depends on the type of MongoDB cluster, the URL to use is provided
together with the MongoDB configuration. The YCSB configuration then uses the
provided URL via reference.

The system also supports a variety of hooks for setup and post processing. For
example, a pre_cluster_start hook can be used to download and provision
database files before starting MongoDB, and a pre_task hook might create
indexes or shard collections before the test starts.

For a consistent experience, all configuration is in YAML. Terraform and
MongoDB Atlas111Atlas is MongoDB’s Database as a Service product API expect
JSON syntax as input. DSI transparently transforms the YAML configuration for
those components to JSON.

###  4.2. Technical Challenges

We have been early adopters of Terraform (Ter, [n.d.]). Generally it has
served us well, but some details have required workarounds along the way.
Early on Terraform had a hard limit for how many servers it could provision at
once. As a workaround we needed to deploy our sharded cluster in two separate
steps. Another problem was that the plugin that configures AWS Virtual Private
Cloud (VPC) networks lacked dependency information. This caused server
deployments to fail when they tried to use a VPC that did not exist yet.

Newer Terraform versions almost never supported the configuration files from
the older versions. This caused us to upgrade only rarely, as it was often
days of work.

Originally we reused clusters between Evergreen tasks. This was implemented
because EC2 billing was hourly, and we wanted to avoid situations where we
would have to double pay for an hour due to terminating and instantly re-
deploying the same cluster. As EC2 moved to per minute billing, we wanted to
remove this code path that is used in CI only and therefore hard to test and
easy to forget. Yet doing this caused InsufficientInstanceCapacity errors from
EC2. It may have been related to some special EC2 configurations we use:
either dedicated instances or placement groups. For whatever reason it was not
possible to terminate a cluster of N nodes and then expect to immediately
start the same N nodes again. Recently we revisited this issue, and it seems
this is no longer an issue. So now we were finally able to remove the re-use
of clusters.

###  4.3. Human Challenges

Many challenges are human rather than technical:

DSI takes a laissez faire attitude to all the configuration. DSI’s role is
pass thru in nature: YAML is turned into a Python dictionary structure, part
of which is passed as input to mongod and ycsb. If there is an error in the
configuration, then at this point mongod or ycsb will print an error and fail.
Trying to duplicate such an error checking procedure in DSI would be futile:
MongoDB supports hundreds of configuration options and new ones are added
every year.

Yet software engineers are trained to validate user input. Teaching a software
team to not do so is surprisingly hard. Early on a module had been written in
Go, a strongly typed language. Each time we wanted to pass a new option to the
test, we had to add an attribute to the Go class that held the JSON input.
This was a huge impediment until the Go code was replaced by Python.

A similar struggle has been around the issue of providing defaults from a
centralized defaults.yml file. The instinct to always provide a default in the
code — such as by sprinkling Python constants around the Python code — is
strong among well educated software engineers. Accepting that there is a
default, it’s just provided by a library and therefore not visible in the
lines of code being written at this moment, can be hard. Yet in the DSI
architecture, providing default values in the code can be considered an error.
Since different modules access the same configuration, it is possible (and
encouraged) that two independent code paths can access the same configuration
option. If both of them specify default values in the Python code, there is a
chance that they specify different defaults, which would be inconsistent and a
bug.

A final observation around challenges of the human mind has been a recurring
tendency to overestimate the importance of whatever small feature an engineer
is currently working on. This recency bias causes engineers to add new options
to bootstrap.yml — the top level configuration file end users look at first —
and documenting this option on the first page of the user manual. But DSI has
hundreds of configuration options and putting all of them in the top level is
not scalable. Moving options from the bootstrap.yml config file further ”down”
into other, more topical sections of the configuration, remains a regular
occupation for the authors.

##  5\. Results

Figure 2. Results for a YCSB test in the Evergreen CI environment.

UI from a performance test result in Evergreen CI.

Figure 2 shows the Evergreen result page of a task where DSI has executed the
YCSB benchmark. The benchmark results are shown as a yellow dot on the graphs
in the bottom. The graph as a whole is the timeseries of daily build results.
Bolded lines are statistically significant changes highlighted by the signal
processing algorithm, and the green diamonds link to associated Jira tickets.
The investment in running performance tests daily in CI has paid off: A major
regression has been found and fixed as part of normal engineering process,
instead of waiting until a release candidate is released and only finding
issues then. The top right corner shows fail/pass status of the static checks
done by the DSI analysis module.

As the development of DSI proceeded and its usability improved, the system
performance benchmarking project in Evergreen has become the primary target
for MongoDB engineers to write performance tests for new features. As of March
2020 we have almost 200 tests and 20 MongoDB configurations in the DSI
repository, most of which run once per day. This is on top of the single-node
microbenchmarks that have been in use before DSI, and also in addition to the
Google Benchmark C++ unit tests, which run several times per day.

The goal of developing a flexible system that could be used to test arbitrary
MongoDB configurations was achieved. An early validation of the design was the
addition of a test to measure performance of the initial synchronization of
data files, when a new node is added to a replica set. The test required one
of the MongoDB nodes to be deployed detached from the replica set and in
uninitialized state. This abnormal setup was possible with a configuration
change only. Similar small victories, such as using arbiter nodes in a replica
set, have followed later.

While we have focused our testing on a single platform: EC2 and Amazon Linux,
the goal was for DSI to be able to support also other hardware infrastructure.
This was finally proven recently when we have pointed a test_control.yml file
against servers running in Azure. A similar triumph of modular design was to
replace the deployment of a MongoDB cluster with a HTTP call to deploy an
Atlas cluster instead. By replacing mongodb_setup entirely, DSI could be used
to test other database products than MongoDB. Similarly, to add more
infrastructure options, such as Kubernetes, we would add support for them in
infrastructure_provisioning module.

Reproducing regressions caught by the CI system is straightforward. An
engineer can simply download the ”DSI Artifacts” tar file from the Evergreen
result page (see 2), untar the package, cd into the directory, and execute the
sequence of DSI commands (infrastructure_provisioning, …) to reproduce the
exact same steps as were executed in CI.

During the MongoDB 4.2 development cycle the system performance CI builds
caught 63 regressions, far beyond the microbenchmarks project at 20. But more
importantly, the MongoDB Server engineers are now committed and able to
reproduce and investigate the regressions from CI. As a result, all but one of
the major performance regressions had been fixed before stable release. In
addition, we are also able to track net new improvements in performance, of
which there were 17 caught by DSI tests. The major improvements were
chronicled by marketing in a blog post (Walker-Morgan, 2019).

##  6\. Related Work

At the time we started developing DSI, we were not aware of any similar end-
to-end tools for performance testing of distributed databases — and certainly
not one supporting MongoDB.

On first sight, it still seems like not much has been published on the topic
of automating system level performance benchmarking. An illustrative example
is the CockroachDB documentation, which includes a guide for benchmarking
CockroachDB with TPC-C (Coc, [n.d.]). It directs the user to start with
manually deploying a CockroachDB cluster: ”Repeat steps 1 – 3 for the other 80
VMs for CockroachDB nodes”. In reality this is not how Cockroach Labs
engineers test CockroachDB clusters, rather the Github repository does include
a DSI-like pair of tools roachprod and roachtest (roa, [n.d.]).

Mikael Ronström’s book ”MySQL Cluster 7.5 inside and out” includes a whole
chapter on bench_run.sh, which supports several benchmark clients used to
benchmark MySQL NDB Cluster (Ronström, 2018). It requires the user to have
downloaded the necessary software to the control host, and expects the servers
to exist, but from this starting point automates deployment of the MySQL
software and execution of the test.

Scylla Cluster Tests (SCT) (Scy, [n.d.]) is an end to end framework very
similar to DSI. It supports the use of a ”test oracle”, a reference database
that executes the same tests and is assumed to always produce the correct
response. The test oracle could be a previous stable release.

Rally is the benchmarking tool for ElasticSearch (Ela, [n.d.]). It is
installable as a Python module via the pip tool, and comes with an extensive
user manual. Similar to SCT, it supports benchmarking different ElasticSearch
releases and comparing the results. Rally does not deploy any cloud resources,
rather expects cluster hosts to already exist.

The above approach to compare a new version in parallel to a ”known good”
release seems to be a common approach. While DSI does not support that as a
first class feature, we should note that we do similar comparisons of the
development branch results against recent stable releases. However, we
consider these monthly and annual reviews as a stopgap measure only. We feel
that in a daily CI oriented workflow, focusing on comparing results against a
recent history helps us catch regressions as they happen.

SAP HANA uses a more CI oriented workflow for performance testing, very
similar to ours (Rehmann et al., 2016). At MongoDB we have recently moved to a
process, where merges to the master source code branch go through an automated
CI gatekeeper. However, we have yet to add performance tests to this automated
gatekeeping process, rather engineers must submit their changes for
performance testing on an opt-in basis. SAP is using performance tests as part
of their gatekeeping step. SAP reports also resource consumption, such as CPU
utilization, as part of their test results. They note that only a human
evaluator can judge whether increased CPU utilization is a positive or
negative change.

Outside of the database space, BenchFlow (Ferme and Pautasso, 2017) provides a
very DSI-like end-to-end automation for benchmarking web services.

##  7\. Conclusions

Distributed Systems Infrastructure (DSI) is MongoDB’s framework for running
fully automated system performance tests in our CI environment. Automating
deployment of real multi-node clusters, executing tests, tuning the system for
repeatable results, and then collecting and analyzing the results, is a hard
problem, and it took us 3 attempts and 6 years to get it right. The open
sourced DSI project is the result of those efforts.

Today DSI is MongoDB’s most used and most useful performance testing tool. It
runs almost 200 different benchmarks in daily CI, and we also use it for
manual performance investigations. During MongoDB 4.2 development cycle, DSI
caught 63 regressions. As we can alert the responsible engineer in a timely
fashion, all but one non-trivial regressions were fixed before the 4.2.0
release. We are also able to detect net new improvements, of which DSI caught
17.

DSI presents some novel design choices. For example, we have banned the use of
command line options completely. By forcing all configuration into
configuration files, we get an audit trail of each test execution, and
engineers are also easily able to reproduce the exact same execution. Another
uncommon choice is that we use vanilla images when deploying servers instead
of building our own custom image. This means that all configuration code is in
the DSI repository.

###### Acknowledgements.

Chung-Yen Chang and Rui Zhang were with us in the original Performance team
that started work on a properly designed Python based version. Jim O’Leary,
Ryan Timmons, and Julian Edwards were part of the team that wrote most of the
code that is in DSI today. Several interns and new grads contributed major
components while visiting the team: Shane Harvey created mongodb_setup.py and
the SSH plumbing. Ryan Chipman created bootstrap.py and Blake Oler the key
feature to restart MongoDB between tests. Severyn Kozak, William Brown, Kathy
Chen, Pia Kochar worked on rules in analysis.py and test configurations. After
the active development phase completed, maintainership of DSI has been with
Max Hirschorn, Ryan Timmons, Robert Guo and Raiden Worley, while we have taken
the role of end users using DSI to investigate MongoDB performance. It was
Ryan Timmons who never gave up the hope of one day open sourcing DSI, and
played an active role in facilitating merges of remaining cleanup work to make
that hope a reality. Dan Pasette and Ian Whalen have acted as project leads
during transition phases between above team compositions, and overall deserve
thanks for not giving up on the project during a long but necessary rewrite.
Cristopher Stauffer and April Schoffer have provided similar project oversight
in recent years. We thank Eoin Brazil and the anonymous reviewers for valuable
feedback on this article, helping us to present our work more clearly.

## References

  * (1)
  * DSI ([n.d.]) [n.d.].  Distributed System Infrastructure 2.0.  https://github.com/henrikingo/dsi/
  * sys ([n.d.]) [n.d.].  Evergreen configuration file for MongoDB system performance tests.  https://github.com/mongodb/mongo/blob/master/etc/system_perf.yml
  * FTD ([n.d.]) [n.d.].  Full Time Diagnostic Data Capture.  https://docs.mongodb.com/manual/faq/diagnostics/
  * mdi ([n.d.]) [n.d.].  mdiag.sh: MongoDB Diagnostic Report.  https://raw.githubusercontent.com/henrikingo/support-tools/master/mdiag/mdiag.sh
  * Coc ([n.d.]) [n.d.].  Performance Benchmarking with TPC-C.  CockroachDB manual.  https://www.cockroachlabs.com/docs/stable/performance-benchmarking-with-tpc-c-100k-warehouses.html
  * Ela ([n.d.]) [n.d.].  Rally (ElasticSearch).  https://esrally.readthedocs.io/en/latest/quickstart.html
  * roa ([n.d.]) [n.d.].  roachtest (CockroachDB).  https://github.com/cockroachdb/cockroach/blob/master/pkg/cmd/roachtest/README.md
  * Scy ([n.d.]) [n.d.].  SCT - Scylla Cluster Tests.  https://github.com/scylladb/scylla-cluster-tests/README.rst
  * Ter ([n.d.]) [n.d.].  Terraform.  https://github.com/hashicorp/terraform
  * YCS ([n.d.]) [n.d.].  YCSB (Yahoo! Cloud Service Benchmark.  wiki.  https://github.com/brianfrankcooper/YCSB/wiki
  * Armstrong (2013) Tim Armstrong. 2013\.  Linkbench.  https://www.facebook.com/notes/facebook-engineering/linkbench-a-database-benchmark-for-the-social-graph/10151391496443920/
  * Daly et al. (2020) David Daly, William Brown, Henrik Ingo, Jim O’Leary, and David Bradford. 2020.  The Use of Change Point Detection to Identify Software Performance Regressions in a Continuous Integration System. In _ICPE ’20, April 20–24, 2020, Edmonton, AB, Canada_ _(ICPE ’20)_ , TODO (Ed.), Vol. 3. ACM.  https://doi.org/10.1145/3358960.3375791
  * Erf (2016) Kyle Erf. 2016.  Evergreen Continuous Integration: Why We Reinvented The Wheel.  Blog Post.  https://engineering.mongodb.com/post/evergreen-continuous-integration-why-we-reinvented-the-wheel
  * Ferme and Pautasso (2017) Vincenzo Ferme and Cesare Pautasso. 2017.  Towards Holistic Continuous Software Performance Assessment. 159–164.  https://doi.org/10.1145/3053600.3053636
  * Ingo and Daly (2019) Henrik Ingo and David Daly. 2019.  Reducing variability in performance tests on EC2: Setup and Key Results.  Blog Post.  https://engineering.mongodb.com/post/reducing-variability-in-performance-tests-on-ec2-setup-and-key-results
  * Rehmann et al. (2016) Kim-Thomas Rehmann, Changyun Seo, Dongwon Hwang, Binh Than Truong, Alexander Boehm, and Dong Hun Lee. 2016.  Performance Monitoring in SAP HANA’s Continuous Integration Process.  _SIGMETRICS Perform. Eval. Rev._ 43, 4 (Feb. 2016), 43–52.  https://doi.org/10.1145/2897356.2897362
  * Ronström (2018) M. Ronström. 2018\.  _MySQL Cluster 7.5 inside and out_.  Books on Demand, Chapter 71: DBT2-0.37.50 Benchmark Scripts, 586–609.  https://drive.google.com/file/d/1z72GCsHudw1X4Z4RZM869mxDViz0fxrB/view
  * Smart (2011) John Ferguson Smart. 2011\.  _Jenkins: The Definitive Guide: Continuous Integration for the Masses_.  ” O’Reilly Media, Inc.”.
  * Walker-Morgan (2019) DJ Walker-Morgan. 2019\.  MongoDB 4.2 Performance Boosts.  Blog.  https://www.mongodb.com/blog/post/mongodb-42-performance-boosts