Towards flexibility and robustness of LSM trees

When modeling the read cost of LSM trees, a key quantity to accurately capture is the amount of superfluous I/Os that take place. Although Bloom filters are used to minimize extra I/Os, they allow for a small fraction of false positives. If the filter returns negative, the target key does not exist in the run, and the lookup skips over the assigned fence pointer saving a single random I/O. If a filter returns positive, then the target key may exist, so the lookup probes the run at a cost of one I/O. Then, if the run contains the correct key the lookup terminates. Otherwise, we have a false positive and the lookup continues to probe the next run increasing the number of I/Os. The false positive rate (\(\epsilon \)) of a standard Bloom filter that is designed to hold information over n entries using a bit-array of size m is given by [82]:Note that the above equation assumes the use of an optimal number of hash functions in the Bloom filter [85].

Classically, LSM tree-based key-value stores use the same number of bits-per-entry across all Bloom filters. This means that a lookup probes on average of the runs, where \({{m_{\textrm{filt}}}}\) is the overall amount of main memory allocated to the filters. As \({{m_{\textrm{filt}}}}\) approaches 0 or infinity, the term approaches 1 or 0 respectively. Here, we build on the state-of-the-art Bloom filter allocation strategy proposed in Monkey [26] that uses different false positive rates for each level of the LSM tree to offer optimal memory allocation; for a size ratio \(T\), the false positive rate corresponding to the Bloom filter at the level i is given byAdditionally, false positive rates for all levels satisfy \(0 \le f_i({{T}}) \le 1\). It should be further noted that Monkey optimizes false positive rates at individual levels to minimize the worst-case average cost of empty point queries. Non-empty point query costs, being significantly lower than those of empty point queries, are not considered during the optimization process.

LSM tree design and system parameters. In Sect. 3 we introduced the key design and system parameters needed to model LSM tree performance. In addition to those parameters, there are two more auxiliary and derived parameters we use: the potential storage asymmetry [64] in reads and writes (\(f_{a}\)) and the expected selectivity of range queries (\(S_\textrm{RQ}\)).

We now introduce a new variable \(K_i\) that denotes the maximum number of files for a given level i. It captures a unified design for both classical compaction policies (i.e., tiering and leveling) by introducing a range of new hybrid policies.

Maximum files per level. Figure 2 displays the basic structure of an LSM tree with \(K_i\) assigned for all levels. We define \(K_i\) as the maximum number of sorted immutable runs before a full-level compaction triggers, essentially the capacity of runs per level. In a classic tiering compaction policy, a single level of an LSM Tree traditionally has a max of \(({{T}}- 1)\) runs, each of size \(\frac{{{m_{\textrm{buf}}}}}{E} \cdot {{T}}^{(i - 1)}\) where i is the assigned level. A full-level compaction triggers once the level receives \({{T}}\) runs from the level above, as a result, a level will have at most \(({{T}}- 1)\) runs. In our new design, each level still respects the maximum entry capacity for an LSM tree, as each run will have at most \(\frac{{{m_{\textrm{buf}}}}}{E} \cdot \frac{{{T}}^{i - 1}}{K_i}\) entries. Figure 2a shows an example of a tree right before the compaction occurs. Once the buffer is flushed, Level 1 will compact all runs within the level and send a sorted run to Level 2, which subsequently sort-merges the received run with the existing data. Then after four more buffer flushes, Level 2 will have received another run and trigger a compaction, creating a new Level 3.

Compaction behavior. When \(K_i = {{T}}- 1\) for level i, the design is equivalent to a tiering policy, while for \(K_i = 1\), it is equivalent to a leveling policy. As incoming sorted runs are compacted, we choose not to split runs, rather, we only merge runs or logically move them from one level to another. Therefore, for values in between \({{T}}- 1\) and 1, we alternate when compacted runs from the level above are merged or simply logically moved. For example, Fig. 2b shows a scenario for \(K_i = 2\), and \({{T}}= 6\). The first three runs from the level above would be compacted to form a single run; the next 2 runs would merge to form a sorted run. In this instance, each run would be of a different size, one holding the equivalent of three compactions while the other holding 2. Otherwise, if \(K_i\) and \({{T}}\) are set such that \((K_i - 1) / {{T}}\) is an integer, the size of each sorted run is equivalent. The sixth flush from Level \(i-1\) triggers a full-level compaction flushing to Level \(i+1\).

Using the above insights, we model the costs in terms of the expected number of I/O operations required for the fulfillment of the individual queries. We summarize new notations introduced for the cost model in Table 2.

Expected empty point query cost. (\(Z_0\)) A point query that returns an empty result will have visited all sorted runs on every level and issue an I/O for every false positive result among the Bloom filters. Therefore, the expected number of I/Os per level depends on the Bloom filter memory allocation at that level. Hence, Eq. (4) expresses \(Z_0\) in terms of the false positive rates at each level as:For each level, there will be at most \(K_i\) runs, and each run will have equal false positive rates.

Expected non-empty point query cost. (Z) There are two components to the expected non-empty point query cost. First, we assume that the probability of a point query finding a non-empty result in a level is proportional to the size of the level. Thus, the probability of such a query being satisfied on Level i by a unit cost I/O operation is simply \(\frac{({{T}}-1) \cdot {{T}}^{i-1}}{N_f({{T}})} \cdot \frac{{{m_{\textrm{buf}}}}}{E}\), where \(N_f({{T}})\) denotes the number of entries in a full tree up to \(L({{T}})\) levels:Second, we assume that all levels preceding Level i will trigger an I/O operation with a probability equivalent to the false positive rates of the Bloom filters at those levels. Similarly to empty point queries, the expected cost of such failed I/Os on the preceding levels is \(\sum _{j=1}^{i-1}f_j({{T}})\). Lastly, each level will contain at most \(K_i\) sorted runs, we assume that on average the entry is found in the middle run resulting in an additional \(\frac{(K_i - 1)}{2} \cdot f_i({{T}})\) extra I/Os. Thus, we can compute the non-empty point query cost as an expectation over the entry being found at any of the \(L({{T}})\) levels of the tree as follows:Range queries cost. (Q) A range query will issue at most one disk seek per run per level, or \(K_i\) disk seeks. Each seek is then followed by a sequential scan. The cumulative number of pages scanned over all runs is \({{S_\textrm{RQ}}}\cdot \frac{N}{B}\), where \(S_\textrm{RQ}\) is the average proportion of all entries included in range lookups. After finding the first valid page, range queries perform sequential I/Os for subsequent pages rather than a random I/O. Therefore, we add a scaling factor \(f_{\textrm{seq}}\) that represents the cost of a sequential I/O with respect to one random I/O. Hence, the overall range lookup cost Q in terms of logical pages reads is as follows:

Write cost. (W) We model worst-case writing cost assuming that the vast majority of incoming entries do not overlap. This implies most entries will propagate through all levels of the LSM tree. Therefore, we calculate the expected number of I/Os by first estimating the average number of merge operations a single write participates in at Level i, and summing over all levels. We start by deriving the total number of merges that occur on Level i. note that Level i will receive at most \({{T}}- 1\) flushes from Level \(i - 1\) before a full level compaction is triggered. Additionally, a run at Level i needs \(\frac{{{T}}- 1}{K_i}\) flushes from Level \(i - 1\) to reach its maximum size; we will refer to this as the flush capacity. Figure 3 shows the number of flushes and flush capacity for Level i.

Analyzing a single sorted run at Level i, we observe that the last flush will only participate in a single eager compaction as the sorted run will reach its flush capacity at that point. The second to last flush participates in 2 merges, the third to last in 3 merges, and the first flush in \(\frac{{{T}}- 1}{K_i} - 1\) merges as new flushes are eagerly compacted into the sorted run. Therefore, the total count of merge operations for \(K_i\) sorted runs on Level i isGiven the total merges for Level i, we can now calculate the average number of merges a single write participates in. First, we divide the total merges at Level i from Eq. (8) by the number of flushes from Level \(i - 1\) (\(T - 1\)) to receive an average merge count of \(\frac{(T - 1 - K_i)}{2K_i}\). Second, to account for the final full-level merge that occurs on the \(T^{th}\) flush, we add 1 additional merge. Therefore, the average number of merges, and subsequently I/Os, a single write participates in at Level i is simply \(\frac{T - 1 + K_i}{2K_i}\)

To calculate the cost of a single insert, we need to divide the average number of merges every level by the number of entries per page, B. Additionally, as every compaction operation reads data at Level \(i-1\) and writes to Level i, we model the potential asymmetry between reads and writes on the underlying storage device³ using \({{f_{a}}}\). For example, a device for which a write operation is twice as expensive as a read operation has \({{f_{a}}}=2\). When flushing the buffer, writes perform sequential I/Os as opposed to random I/Os, hence, we add \(f_{\textrm{seq}}\) term to account for the cost of different I/O types. Summing the average I/Os per level for all levels, the total I/O cost is captured by:Total expected cost. The total expected operation cost, \({{\text {C}}}({\mathbf{{w}}}, {{\Phi }})\), is computed by weighing the empty point lookup cost \(Z_0({{\Phi }})\) from Eq. (4), the non-empty point lookup cost \(Z({{\Phi }})\) from Eq. (6), the range lookup cost \(Q({{\Phi }})\) from Eq. (7), and the write cost \(W({{\Phi }})\) from Eq. (9) by their proportion in the workload represented by the terms \(z_0\), z, q and w respectively (note that \(z_0 + z_1 + q + w = 1\)).

With the introduction of \(K_i\), we can use our cost model to effectively describe the behavior of other common LSM designs. For example, for a classic leveling compaction policy we set \(\forall i, K_i = 1\). This results in each level eagerly merging incoming compacted runs into a single run, which is equivalent to leveling. Additionally, our cost model can easily describe other flexible LSM compaction behavior. If we restrict all capacities before the last level to be equivalent (i.e., \(K_1 = K_2 = \ldots = K_{L - 1}\) where L is the last level), our cost model expresses the Fluid LSM design as described in Dostoevsky [28]. With \(K_{L} = 1\) and all \(K_1 = K_2 = \ldots = K_{L - 1} = T - 1\), we have an equivalent cost model for Lazy Leveling. However, our proposed K-LSM is the most flexible, as each level has an independent limit on the number of runs. Table 3 summarizes how K-LSM describes other common LSM variations:

Traditionally, designers focus on finding the configuration \({{{\Phi }}}^*\) that minimizes the total cost \({{\text {C}}}({\mathbf{{w}}}, {{\Phi }}^*)\), for a given fixed workload \({\mathbf{{w}}}\). We call this problem the Nominal Tuning problem, which is defined as follows:

The problem described above captures the classic tuning paradigm of finding a system configuration that minimizes a cost model (describing I/O or latency) given a specific static workload and system environment. Therefore, each LSM design described in Table 3 has a different Nominal Tuning problem based on the form of the cost function. Prior tuning approaches either individually solve the Nominal Tuning problem solely for LSM data layouts [28, 53] (e.g., tiering or leveling) or memory allocation [26], but not simultaneously for both.

To solve the Nominal Tuning problem, we utilize an off-the-shelf numerical solver. We opt to use the Sequential Least Square Quadratic Solver (SLSQP) implemented in Python and packaged under the SciPy library [84]. When choosing a data layout to optimize, we reduce the cost model to express the appropriate LSM design.

Relaxing integer values. Certain decision variables such as \(T\) (size ratio) pose an issue as they are required to be integers as LSM trees cannot implement fractional size ratios. To keep the problem feasible, we relax the integer constraint for such decision variables and opt to take the ceiling of any feasible solution before deploying the tuning. In practice, this approach works well and leads to high-performance configurations.

In this section, we explore the optimal configurations for different designs described in Table 3 by solving the Nominal Tuning problem for each respective LSM design variation. We compare average I/Os per query to analyze the performances of different flexible designs.

Experiment setup. We adopt the following setting for system parameters: the database initially holds 10 billion entries, each of size 1 KB; a memory budget of 10 bits per element, or 10 GB in total divided among Bloom filter and write buffer; and a page size of 4 KB. It should be noted that the original Dostoevsky strategy uses Fluid LSM as an LSM design with fixed memory allocation, and only optimizes for the maximum number of runs for the upper levels, the lowest level, and size ratio while fixing memory. Therefore, while evaluating Dostoevsky we fix \(m_{\textrm{filt}}\) to 10 bits per entry and \(m_{\textrm{buf}}\) to 2 MB as in [28]. For all other design variations, we solve a Nominal Tuning problem that optimizes memory and design while fixing other memory allocations such as fence pointers and the random access buffer.

Flexible performance. Figure 4 shows the average I/O performance of various tuning configurations normalized to K-LSM design across different workloads. We experiment with a mixed read-write (\({{\mathbf{{w}}}}_7\)) and a read-heavy (\({{\mathbf{{w}}}}_{11}\)) workload from the uncertainty benchmark, which is presented in detail in Sect. 7. Note that \({{\mathbf{{w}}}}_7\) would traditionally lead a designer to focus on tiering as writes make up a large portion of the workload, while \({{\mathbf{{w}}}}_{11}\) would suggest a leveling policy would be best. When solving for more flexible designs—in this instance K-LSM and Fluid LSM—we observe that the optimizer always produces the best tunings. Because \({\mathbf{{w}}}_{11}\) is a read-heavy distribution, the optimal configuration has a leveling policy, which is reinforced by observing that the optimal K-LSM and Fluid LSM designs chosen are equivalent leveling. For the balanced read-write workload \({\mathbf{{w}}}_7\), we see that flexible designs outperform traditional designs as the optimizer finely tunes the capacity per level to accommodate both reads and writes.

The Nominal Tuning problem assumes perfect information about the workload before deploying the system. For example, we may assume that the input vector \({\mathbf{{w}}}\) represents the workload for which we optimize, while in practice, \({\mathbf{{w}}}\) is simply an estimate of what an observed workload may look like. Hence, the configuration obtained by solving Problem 1 may result in variable performance if the observed workload upon deployment varies greatly from the expected workload.

We capture this uncertainty by reformulating Problem 1 to take into account variability observed in the input workload. Given an expected workload \({\mathbf{{w}}}\), we introduce the notion of the uncertainty region of \({\mathbf{{w}}}\), which we denote by \({\mathcal {U}}_{\mathbf{{w}}}\).

We can define the robust version of Problem 1, under the assumption that there is uncertainty in the input workload as follows:

Note that the above problem definition intuitively states the following: it recognizes that the input workload \({\mathbf{{w}}}\) will not be observed exactly, and it assumes that any workload in \({\mathcal {U}}_{\mathbf{{w}}}\) is possible. Then, it searches for the configuration \({{\Phi }}_{\mathbf{{w}}}\) that is best for the worst-case scenario among all those in \({\mathcal {U}}_{\mathbf{{w}}}\).

The challenge in solving Robust Tuning is that one needs to explore all the workloads in the uncertainty region to solve the problem. In the next section, we show that this is not necessary. In fact, by appropriately rewriting the problem definition we show that we can solve Problem 2 in polynomial time.

In this section, we discuss our solutions to the Robust Tuning problem. On a high level, the solution strategy is the following: first, we express the objective of the problem (as expressed in Eq. (11)) as a standard continuous optimization problem. We then take the dual of this problem and use existing results in robust optimization to show: (i) the duality gap between the primal and the dual is zero, and (ii) the dual problem is solvable in polynomial time. Thus, the dual solution can be translated into the optimal solution for the primal, i.e., the original Robust Tuning problem. The specifics of the methodology are described below:

Defining the uncertainty region. \({\mathcal {U}}_{\mathbf{{w}}}\) Recall that \({\mathbf{{w}}}\) is a probability vector, i.e., \({\mathbf{{w}}}^\intercal {\mathbf{{e}}}= 1\). Thus, in order to define the uncertainty region \({\mathcal {U}}_{\mathbf{{w}}}\), we use the Kullback–Leibler (KL) divergence function [52] defined as follows:

Since our workloads are represented as probability distributions, the KL-divergence is the most natural choice of distance between them. One could use \(L_p\) norms instead. However, calculating the \(L_p\) norm between workloads requires a summation of the \(p^{\text {th}}\) power of differences in probabilities, which are extremely small values, and are not meaningful in this setting.

Using the KL-divergence we can now formalize the definition of the uncertainty region around an expected workload \(\textbf{w}\) as follows,Here, \(\rho \) determines the maximum KL-divergence that is allowed between any workload \({{\hat{\textbf{w}}}}\) in the uncertainty region and the input expected workload \({\mathbf{{w}}}\). Note that the definition of the uncertainty region takes as input the parameter \(\rho \), which intuitively defines the neighborhood around the expected workload. Figure 5 shows an example of the uncertainty region for \(\rho = 0.2\) and expected workload \({\mathbf{{w}}}_0 = (25\%, 25\%, 25\%, 25\%)\), and for \(\rho = 2\) and expected workload \({\mathbf{{w}}}_1 = (97\%, 1\%, 1\%, 1\%)\). For this visualization, we combined the two types of read queries (empty and non-empty) onto one axis. Note that the shape of the uncertainty region is defined by the expected workload, the value of \(\rho \), and the fact that all workloads are restricted to be probability distributions. In terms of notation, \(\rho \) is required for defining the uncertainty region \({\mathcal {U}}_{\mathbf{{w}}}^\rho \). However, we drop the superscript notation unless required for context.

Rewriting of the ROBUST TUNING problem (Primal). Using the above definition of the workload uncertainty region \({\mathcal {U}}_{\mathbf{{w}}}^\rho \), we are now ready to proceed to the solution of the Robust Tuning problem. For a given \(\rho \), the problem definition, as captured by Eq. (11), can be rewritten as follows:This rewrite captures the intuition that the optimization is done over the worst-case scenario across all the workloads in the uncertainty region \({\mathcal {U}}_{\mathbf{{w}}}\). Equation (13) can be rewritten by introducing an additional variable \(\beta \in {\mathbb {R}}\), as follows:This reformulation allows us to remove the \(\min \max \) term in the objective from Eq. (13). The constraint in Eq. (14) can be equivalently expressed as,Finally, the Lagrange function for the optimization on the right-hand side of the above equation is:where \(\lambda \) and \(\eta \) are the Lagrangian variables.

Formulating the dual problem. We can now express the dual objective as,which we need to minimize.

Now we borrow the following result from [10],

In other words, minimizing the dual objective \(g(\lambda , \eta )\)—as expressed in Eq. (15)—will lead to the optimal solution for the Robust Tuning problem.

Solving the dual optimization problem optimally. Formulating the dual problem and using the results of Ben-Tal et al. [10], we have shown that the dual solution leads to the optimal solution for the Robust Tuning problem. Moreover, we can obtain the optimal solution to the original Robust Tuning problem in polynomial time, a consequence of the tractability of the dual objective.

To solve the dual problem, we first simplify the dual objective \(g(\lambda ,\eta )\) so that it takes the following form:In Eq. (16), \(\phi _{KL}^*(.)\) denotes the conjugate of KL-divergence function and \({\mathbf{{c}}}_i\) corresponds to the i-th dimension of the cost vector \({\mathbf{{c}}}({{\Phi }})\) as defined in Sect. 3 – clearly in this case \(k=4\) as we have 4 types of queries in our workload. Results of Ben-Tal et al. [10] show that minimizing the dual function as described in Eq. (16) is a convex optimization problem, and it can be solved optimally in polynomial time if and only if the cost function \({\mathbf{{c}}}({{\Phi }})\) is convex in all its dimensions.

In our case, the cost function for the range queries is not convex w.r.t. size ratio \(T\) for the tiering policy. However, on account of its smooth non-decreasing form, we are still able to find the global minimum solution forThis minimization problem can be solved using the Sequential Least Squares Quadratic Programming solver (SLSQP) included in the popular Python optimization library SciPy [84]. Solving this problem outputs the values of the Lagrangian variables \(\lambda \) and \(\eta \) and most importantly the configuration \({{\Phi }}\) that optimizes the objective of the Robust Tuning problem—for input \(\rho \). In terms of running time, the SLSQP solver outputs a robust tuning configuration for a given input in less than a second.

Finding a value for \(\varvec{\rho }\). Since \(\rho \) is a robust tuning parameter, we also provide a few heuristics for setting it. In the presence of historically observed workloads, a DBA may calculate \(\rho \) using the following definition: that is, \(\rho \) is set to be the largest KL-divergence between any observed workload and the corresponding workload average as described in Algorithm 1. If the DBA does not have information about past workloads, they may provide ranges for each query type; then, can sample workloads within those ranges and then calculate \(\rho \) using the definition above to find an appropriate value. DBAs may instead provide two workloads, one that is expected during a normal observation period, and another off-period or unlikely workload. In this case, the KL-divergence between these two workloads can be used as \(\rho \).

In this section, we provide definitions of metrics used to evaluate the performance of tunings.

Normalized delta throughput (\(\varvec{\Delta }\)). Defining throughput as the reciprocal of the cost of executing a workload, we measure the normalized delta throughput of a configuration \({{\Phi }}_2\) w.r.t. another configuration \({{\Phi }}_1\) for a given workload \(\textbf{w}\) as follows,\(\Delta _{{\mathbf{{w}}}}({{\Phi }}_1, {{\Phi }}_2) > 0\) implies that \({{\Phi }}_2\) outperforms \({{\Phi }}_1\) when executing a workload \(\textbf{w}\) and vice versa when \(\Delta _{{\mathbf{{w}}}}({{\Phi }}_1, {{\Phi }}_2) < 0\).

Throughput range (\(\varvec{\Theta }\)). While normalized delta throughput compares two different tunings, we use the throughput range to evaluate an individual tuning \({{{\Phi }}}\) w.r.t. the benchmark set \(\mathcal {B}\) as follows,\(\Theta _{{{\mathcal {B}}}}({{\Phi }})\) intuitively captures the best and the worst-case outcomes of the tuning \(\Phi \). A smaller value of this metric implies higher consistency in performance.

To evaluate the performance of our proposed robust tuning approach, we design a large-scale experiment comparing different tunings over the sampled workloads in \(\mathcal {B}\) using the analytical cost model. For each of the expected workloads in Table 4, we obtain a single nominal tuning configuration (\({{{\Phi }}_N}\)) by solving the Nominal Tuning problem. For 15 different values of \(\rho \) in the range (0.0, 4.0) with a step size of 0.25, we obtain a set of robust tuning configurations (\({{\Phi }}_R\)) by solving the Robust Tuning problem. Finally, we individually compare each of the robust tunings with the nominal over the 10,000 workloads in \(\mathcal {B}\) to obtain over 2 million comparisons. While computing the costs, we assume that the database contains 10 billion entries each of size 1 KB. The analysis presented in the following sections assumes a total available memory of 10 GB. For brevity, we present representative results corresponding to individual expected workloads and specific system parameters. We primarily focus on two workloads from Table 4, \({\mathbf{{w}}}_{7}\) which is a mixed read-write workload, and \({\mathbf{{w}}}_{11}\), which is a read-heavy workload. However, we exhaustively confirmed that changing these parameters does not qualitatively affect the outcomes of our experiment.

Here, we present an analysis of the comparisons between the robust and the nominal tuning configurations. Using an off-the-shelf global minimizer from the popular Python optimization library SciPy [84], we obtain both nominal and robust tunings with the runtime for the above experiment being less than 10 min.

Comparison of tunings. First, we address the question—is it beneficial to adopt robust tunings relative to the nominal tunings? Intuitively, it should be clear that the performance of nominally tuned databases would degrade when the workloads being executed on the database are significantly different from the expected workloads used for tuning. In Fig. 6, we present performance comparisons between the robust and the nominal tunings for different values of uncertainty parameter \(\rho \). We observe that robust tunings provide substantial benefit in terms of normalized delta throughput for unimodal, bimodal, and trimodal workloads. The normalized delta throughput \(\Delta _{{\hat{\textbf{w}}}}({{\Phi }}_N, {{\Phi }}_R)\) shows over 95% improvement on average over all \({{\hat{\textbf{w}}}}\in {{\mathcal {B}}}\) for robust tunings with \(\rho \ge 0.5\), when the expected workload used during tuning belongs to one of these categories. For uniform expected workload, we observe that the nominal tuning outperforms the robust tuning by a modest 5%.

Intuitively, unbalanced workloads result in overfit nominal tunings. Hence, even small variations in the observed workload can lead to significant degradation in the throughput of such nominally tuned databases. On the other hand, robust tunings by their very nature take into account such variations and comprehensively outperform the nominal tunings. In the case of the uniform expected workload \({\mathbf{{w}}}_0\), a low value of \(\rho \) covers a larger area of possible workloads than that same value would in a different workload as evident in Fig. 5. In this case, when tuned for high values of \(\rho \), the robust tunings are unrealistically pessimistic and lose performance relative to the nominal tuning.

Impact of tuning parameter \(\varvec{\rho }\). Next, we address the question—how does the uncertainty tuning parameter \(\rho \) impact the performance of the robust tunings? In Fig. 7, we take a deep dive into the performance of robust tunings for an individual expected workload for different values of \(\rho \). We observe that the robust tunings for \(\rho =0\) i.e., zero uncertainty, are very close to the nominal tunings. As the value of \(\rho \) increases, its performance advantage over the nominal tuning for the observed workloads with higher KL-divergence w.r.t. expected workload increases. Furthermore, the robustness of such configurations have logically sound explanations. The expected workload in Fig. 7 consists of just 1% writes. Hence, for low values of \(\rho \), the robust tuning has a higher size ratio leading to shallower LSM trees to achieve good read performance. For higher values of \(\rho \), the robust tunings anticipate an increasing percentage of write queries and hence limit the size ratio to achieve higher throughput.

In Fig. 8, we show the impact of tuning parameter \(\rho \) on the throughput range. In Fig. 8a we plot a histogram of the nominal and robust throughputs for workload \({\mathbf{{w}}}_{11}\). As the value of \(\rho \) increases, the interval size between the lowest and the highest throughputs for the robust tunings consistently decreases. We provide further evidence of this phenomenon in Fig. 8b, by plotting the decreasing throughput range \(\Theta _{{\mathcal {B}}}({{\Phi }}_R)\) averaged across all the expected workloads. Thus, robust tunings not only provide a higher average throughput for all \({{\hat{\textbf{w}}}}\in {{\mathcal {B}}}\), but they have a more consistent performance (lower variance) compared to the nominal tunings.

Choice of \(\varvec{\rho }\). Now, we address the question—What is the appropriate choice for the value of uncertainty parameter \(\rho \)? In Fig. 9, we explore the relationship between \(\rho \) and the KL-divergence \(I_{KL}({{\hat{\textbf{w}}}}, {\mathbf{{w}}})\) for \({{\hat{\textbf{w}}}}\in {{\mathcal {B}}}\), by making a contour plot of the corresponding normalized delta throughput \(\Delta _{{{\hat{\textbf{w}}}}}({{\Phi }}_N, {{\Phi }}_R)\). We confirm our intuition that nominal tunings compare favorably with our proposed robust tunings only in two scenarios: (1) when the observed workloads are extremely similar to the expected workload (close to zero observed uncertainty), and (2) when the robust tunings assume extremely low uncertainty with \(\rho < 0.2\) while the observed variation is higher. Based on this evidence, we propose the following rule of thumb: the maximum KL-divergence between any two pairs of observed workloads is a reasonable value of \(\rho \) in practice.

Sensitivity analysis w.r.t. entry size. Lastly, we take a look at the expected tuning performance w.r.t to system settings. Figure 10 shows average I/O, or single logical page accesses, per query over different entry sizes with the standard deviation highlighted around each line. Each data point corresponds to the average I/O per query for the optimal tuning for all workloads \({\hat{{\mathbf{{w}}}}} \in {{\mathcal {B}}}\). For our mixed read-write workload, we see that the Endure always performs better than the nominal tuning regardless of the entry size. When we tune with a read-heavy workload as the expected input, we observe that for lower entry sizes the nominal tuning produces a better tuning, however, at larger entry sizes Endure outperforms its nominal counterpart. Because the total number of entries is fixed, lower entry sizes cause the physical size of the database to be relatively small w.r.t. to the available memory budget. Hence, we observe the allocation between \(m_{\textrm{filt}}\) and \(m_{\textrm{buf}}\) does not play a major role in performance as the tree can be made relatively shallow. However, as the size of the database starts to increase and the memory budget becomes a smaller fraction of the database size, we observe the allocation between memory plays a larger role. This implies proper robust tunings play a larger role in constrained environments, where the available memory is a small fraction of the total database size.

Our server is configured with two Intel Xeon Gold 6230 processors, 384 GB of main memory, a 1 TB Dell P4510 NVMe drive, CentOS 7.9.2009, and a default page size of 4 KB. We use Facebook’s RocksDB, a popular LSM tree-based storage system, to evaluate our approach [32]. While RocksDB provides implementations of leveling and tiering policies, the system implements micro-optimizations not common across all LSM tree-based storage engines. Therefore, we use RocksDB’s event hooks to implement both classic leveling and tiering policies to benchmark the common compaction strategies. For default RocksDB comparisons, we set a custom policy hook to match the default compaction policy of leveling. Additionally, RocksDB does not toggle on Bloom filters by default. In the interest of fair comparison, we add Bloom filters with the bits per element set to 10. Following the Monkey memory allocation scheme [26], we allocate different bits per element for Bloom filters per level. We note that turning off direct I/O improves read performance for any tuning deployed to RocksDB. However, to obtain an accurate count of block accesses we instead enable direct I/Os for both queries and compaction and disable the block cache. To obtain detailed insights about accesses, we present our findings with direct I/Os, however, our qualitative results remain unchanged with direct I/Os turned off. Lastly, portions of memory reserved for the fence pointer and max read buffer are fixed to their default values before performing any tuning for buffer size and Bloom filter memory.

Endure’s pipeline Fig. 11 shows the workflow used for Endure and the following experiments. A workload descriptor (expected workload and uncertainty value \(\rho \)) is provided to Endure to create an uncertainty neighborhood centered around an expected workload. This description of workload uncertainty is then incorporated into the solver. In combination with the cost model, which uses the workload and system parameters as inputs, Endure outputs an expected performance profile and a robust tuning over various workloads in the uncertainty neighborhood. Endure then deploys the robust tuning on a RocksDB instance where we execute workloads to measure performance.

Empirical measurements. We use the internal RocksDB statistics module to measure the number of logical block accesses during reads, bytes flushed during writes, and bytes read and written in compactions. The number of logical blocks accessed during writes is calculated by dividing the number of bytes reported by the default page size. To estimate the amortized cost of writes, we compute the I/Os from compactions across all workloads of a session and redistribute them across write queries. Our approach of measuring average I/Os per query allows us to compare the effects of different tuning configurations, while simultaneously minimizing the effects of extraneous factors on performance.

To evaluate the performance of our proposed robust tuning approach, we create multiple instances of RocksDB using different tunings and empirically measure their performance by executing workloads from the uncertainty benchmark \(\mathcal {B}\). To obtain consistent performance metrics, each instantiation of the database is initialized with the same 10 million unique 1 KB key-value pairs. Each key-value entry has a 16-bit uniformly at random sampled key, with the remaining bits being allocated to a randomly generated value.

While evaluating the performance of the database, we sample a sequence of workloads from the benchmark set \(\mathcal {B}\). Every sampled workload is executed throughout 200,000 queries to measure steady-state performance. This observation period is sufficient to capture spikes in performance and background compactions allowing us to record accurate performance numbers. We group sets of workloads into sequences and catalog them into one of six categories—expected, empty read, non-empty read, read, range, and write—based on the dominant query type. The expected session contains workloads with a KL-divergence less than 0.2 w.r.t. the expected workload used for tuning. For all other sessions, the dominant query type encompasses at least 80% of the total queries while the remaining queries may belong to any of the remaining types. When generating keys of the queries to run on the database, we ensure that non-empty point reads will query a key that exists, while empty point reads will query a key that is not present in the database but is sampled from the same domain. All range queries are generated with minimal selectivity \(S_{RQ}\) to act as short-range queries, which on average read zero to two pages per level. Write queries consist of randomly generated keys that are distinct from the existing keys in the database. Similarly to Sect. 8, we present representative findings for an expected mixed read-write workload (\({\mathbf{{w}}}_{7}\)) and an expected read-heavy workload (\({\mathbf{{w}}}_{11}\)).

In this section, we replicate key insights from Sect. 8, evaluate system performance, and show that Endure scales with database size. We present detailed results for expected workloads \({\mathbf{{w}}}_{7}\) and \({\mathbf{{w}}}_{11}\). Table 5 summarizes the normalized delta throughputs \(\Delta _{\mathbf{{w}}}({{\Phi }}_N, {{\Phi }}_R)\) for all expected workload from \({{\mathcal {B}}}\).

Read performance. We begin by examining the system performance and verifying that the model-predicted I/O and the system-measured I/O match when considering read queries in Figs. 12 and 13. In both figures, we include the model-predicted I/Os per query (top), I/Os per query measured on the system (middle), and the system latency (bottom) for nominal, robust, and default configurations across different read sessions. Additionally, the total throughput numbers in queries per second are reported at the end of the system latency graph. The empirical measurements confirm that the predicted performance benefits from the model translate to similar performance benefits in practice. Note that the discrepancy observed between the relative performance between the nominal and the robust tunings in the presence of range queries (session 2 in Fig. 12) is due to the fence pointers in RocksDB. The analytical model does not account for fence pointers allowing the system to completely skip a run, which may reduce the measured I/Os for short-range queries compared to the predicted I/Os. Lastly, we consider the default configuration as another tuning of RocksDB that does not take into account workload information. Therefore, in certain cases such as Fig. 12, it may outperform other configurations. This can be explained by the fact that the default configuration includes a larger reserve of memory for the Bloom filter, thereby allowing it to outperform the configurations that expect writes in the executed workload. However, in other cases such as Fig. 13, we see a large performance dropoff as both the nominal and robust configurations expect a high amount of reads and therefore tune their size ratios accordingly.

Write performance. In the presence of writes in Fig. 15, the model is still predicting the disk accesses successfully and Endure leads to significant performance benefits. Note that now the structure of the LSM tree is continually changing across all sessions due to the compactions caused by write queries. For example, in Fig. 15 the dip in measured I/Os and latency in the range-query session are the result of empty levels being created via compactions triggered from preceding workloads. Additionally, writes may appear instantaneous w.r.t. system latency as seen in Fig. 14 due to RocksDB assigning compactions to background threads. We observe that the default configuration starts to degrade in performance significantly as more writes are issued to the database. Figure 16 shows the breakdown across each operation type. As the database experiences more writes, the performance for the default configuration drops off, while both the nominal tuning and robust configurations expect writes and experience a performance improvement. From the write session of Fig. 15, we observe that the nominal tuning suffers from high latency and I/O cost. This is due to the large size ratio \(T\) that creates a shallow tree with huge levels, causing long stalls during compactions. Compare this to the robust tuning: the smaller size ratio creates a tree with more stable performance for both I/Os per query and query latency, leading to a higher overall throughput. Overall, we observe that the robust tuning reduces I/O and latency by up to \(90\%\). Figures 12, 13, 14 and 15 confirm that our analytical model accurately captures the relative performance of different tunings.

Robust outperforms nominal for properly selected \(\varvec{\rho }\). In the model evaluation (Fig. 9), we showed that robust tuning outperforms the nominal tuning in the presence of uncertainty for tuning parameter \(\rho \) approximately greater than 0.2. This is further supported by all the system experiments described. Specifically, Figs. 12 and 15 show instances where the KL-divergence of the observed workload averaged across all the sessions w.r.t. the expected workload is close to the tuning parameter \(\rho \). Additionally, we present results for all expected workloads in Table 5. Each entry in the table summarizes the total throughput after running the same experimental setup presented in Fig. 15. We observe that the robust outperforms the nominal in 10 of our expected workloads, with only 2 workloads where robust tuning does worse, however, in these cases the reported throughputs are comparable. In each of these experiments, the robust tuning outperforms the nominal resulting in up to a \(90\%\) reduction in latency and system I/O. Lastly, in Fig. 13, the observed workloads are similar to the expected one (\(I_{KL}({{\hat{\textbf{w}}}}, {\mathbf{{w}}}_{11}) < 0.2\)), resulting in a latency increase of \(20\%\).

Balancing query times. To determine how the tunings from Endure outperform the nominal tunings we analyze the query response times for each operation for an expected workload \({\mathbf{{w}}}\). We observe that robust tunings will provide lower performance for the queries that dominate the expected workload, however, as a tradeoff these tunings perform exceptionally well in unexpected operations. For example, Fig. 17 shows robust tuning performs worse in both range queries and empty point queries, however, in exchange we observe a significant decrease in the response time of write queries. Hence, if the executed workload contains writes, robust tuning will increase overall throughput, especially in the presence of write spikes.

Workload skew. To verify that Endure works across workload distributions, we break down the different query response times in Fig. 17. When the keys generated for the workload follow a Zipfian distribution, we see that the response time for non-empty read queries is significantly lowered. This is in part due to keys toward the top of the tree being repeated, therefore the query does not need to traverse further down the tree resulting in an increase in false positives from the Bloom filter. Regardless, we observe the same patterns for uniform and Zipfian distributions; Endure tunings achieve a better tradeoff in performance for the dominant query types in the expected workload with that of other query types, thereby preventing large performance regressions.

ENDURE scales with data size. To verify that Endure scales, we repeat the previous experiments, while varying the size of the initial database. Each point in Fig. 18 is calculated based on a series of workload sessions similar to the ones presented in Figs. 13 (15) for the left (right) part of Fig. 18. All points use the same expected workload, therefore the nominal and robust tunings are the same across each graph. We observe that the robust and nominal tuning increases buffer memory as the initial database size grows. As a result, for all cases, the number of initial levels is the same regardless of the number of entries. This highlights the importance of the number of levels w.r.t performance. Finally, the performance gap between robust and nominal stays consistent as database size grows, showing that Endure is effective regardless of data size.

To evaluate the robustness of all designs, we design an experiment to compare different optimal tunings for a subset of designs listed in Table 3. For each expected workload in the uncertainty benchmark in Table 4, we obtain a list of tunings by solving Nominal Tuning for various LSM data layouts. We also compute a robust tuning with input \({\mathbf{{\rho }}}= 2\). Next, for every observed workload in \({{\mathcal {B}}}\), we calculate the KL-divergence w.r.t. the expected workload used to obtain each tuning and plot the average I/Os per query for this observed workload (\({{\text {C}}}({{\hat{\textbf{w}}}}, {{\Phi }})\)) versus the KL-divergence. We then execute the initial expected workload for all designs, reset the database to the initial state, and then progressively repeat this process for workloads further away from the expected workload. Similar to Sect. 5.3, we adopt the following setting for system parameters: the database initially holds 10 billion with each entry at 1 KB; page size is 4 KB; and memory budget is set to 10 bits per element or a total of 10 GB.

Figure 19 shows the average I/O per query for various LSM models. Note that for \({\mathbf{{w}}}_{11}\), the performance lines for K-LSM, Fluid LSM, and Endure’s nominal tuning slightly overlap, as the configurations are the same. The same occurs for K-LSM and Fluid LSM on \({\mathbf{{w}}}_{7}\). When evaluating Dostoevsky, we fix memory allocation such that the buffer size is kept at 2 MB as per convention, while the remaining memory is delegated to storing Bloom filters [28, 69].

Robustness of various LSM designs. It should be noted that in instances where the observed workload closely matches the expected workload, Endure’s robust tunings underperform. This is consistent with previous experiments and the intuition that robust tunings proactively compensate for potential changes in the observed workload distribution. As the observed workload drifts further from the expected, robust tunings maintain consistent performance while other tunings show a steady increase in the average number of I/Os. This observation can be attributed to the selected tuning. For example, with \({\mathbf{{w}}}_{7}\) models such as Dostoevsky (\(T = 47\), all \(K_i = 1 \)) and K-LSM (\({{m_{\textrm{filt}}}}= 4.4\) bits per entry, \(T = 48\), all \(K_i = 1\)) optimally selects larger size ratios with effectively leveling policies to accommodate for the expected high amount of writes. In contrast, the robust tuning (\(T = 9\), \({{\pi }}= L\)) selects a size ratio that performs reasonably well in comparison, however, the selected size ratio is small enough to accommodate a large shift to reads.

In the presence of workload drifts, we observe that most models, except Lazy Leveling, experience a performance degradation similar to Endure’s nominal tuning. The optimal tuning of Lazy Leveling (\({{m_{\textrm{filt}}}}= 4.6\) bits per entry, \(T = 2\)) performs robustly when tuned for a read-heavy workload (\({\mathbf{{w}}}_{11}\)). It should be noted that the optimizer selects a size ratio \(T = 2\) that enables Lazy Leveling to accommodate an increase in writes, as merge operations are relatively cheap. Furthermore, increasing the size ratio any further could lead to the creation of upper levels that follow a tiering policy, thereby degrading the performance.