Database replication is an approach for scaling throughput and ensuring high availability. Using workload knowledge, we are able to load-balance queries to replica nodes according to the data being accessed. However, balancing the load evenly while maximizing data reuse is a challenging allocation problem. To address large-size problems, we developed a novel decomposition-based heuristic using linear programming. We compare our approach with a rule-based stateof-the-art allocation algorithm using a real-world workload comprising thousands of queries. Further, we outline how we plan to extend our approach for versatile allocation problems, e.g., considering changing workloads and robustness against node failures.
Partitioning and replication are means to allow databases
to process increasing workloads. Analyses of real workloads
show that read-only queries account for the largest workload
share [
Using a naive load-balancing approach, one can distribute queries independently of the accessed data. As a result, one has to store all data and apply all data modifications on all nodes. Further, queries are unlikely to profit from caching e↵ects, because similar queries are not guaranteed to be assigned to the same replica.
In our research, we investigate query-driven workload distributions, i.e., load-balancing queries based on their accessed data. In particular, we reduce the amount of required memory on all nodes, while balancing the load evenly. Query-driven workload distributions are also beneficial to maximize caching e↵ects. Further, when adding new nodes to a database cluster, we are able to decide which data to load first to quickly process a large share of the workload.
In practice, there are varying constraints and goals to distribute the workload and/or required data on nodes. By using linear programming (LP) we are able to address versatile allocation problems, which include robustness against potential node failures or ecient reallocations to react to changing workloads.
Proceedings of the VLDB 2019 PhD Workshop, August 26th, 2019. Los Angeles, California. Copyright (C) 2019 for this paper by its authors. Copying permitted for private and academic purposes.
The remainder of this paper is structured as follows: We
introduce the basic allocation problem in Section 2. In
Section 3, we discuss related work. In Section 4, we summarize
our scalable decomposition-based approach [
The allocation problem being examined is a coupled
workload distribution and data placement problem. We assume
a horizontally and/or vertically partitioned database with
N disjoint data fragments. Each fragment i has a size ai,
i = 1, ..., N . Note, we assume a separation of the data
partitioning and the allocation process, which is common [
Further, we assume a workload consisting of Q queries (query classes). Each query class j is defined by the subset of fragments qj ✓ { 1, ..., N }, j = 1, ..., Q, it accesses. Queries account for workload shares, defined by query frequencies fj and query costs cj , j = 1, ..., Q.
Last, we assume a number of nodes K to load-balance the workload evenly. In practice, the number of nodes K can be chosen manually by a database administrator or automatically by a replication framework with regard to the desired query throughput.
We want to decide which query should be executed to
which extent on a node in order to minimize the overall
memory consumption for all nodes. Processing query j on
node k requires to store all fragments qj on the node. In [
Figure 1 shows an example workload and an optimal solution, i.e., an even workload distribution for Q = 5 queries, accessing N = 10 fragments, that minimizes the overall memory consumption for a database cluster with K = 4 nodes. (We assume an equal size for each fragment, i.e., ai = 1, i = 1, ..., N .)
By W/V , we denote the replication factor of an allocation, where the total amount of data used W is normalized by the minimal amount of used data V . Because each of the ten fragments is accessed by at least one query, the minimal amount of used data is equal to the number of fragments V = N = 10. The replication factor of our exemplary allocation for four nodes is W/V = 1.4.
1 Database (V=10) 1 3.
Our workload distribution problem (see Section 2) is an
allocation problem in the field of distributed database
systems. O¨zsu and Valduriez [
Our problem formulation is similar to the one presented
by Rabl and Jacobsen [
To address large problem sizes, with thousands of queries, fragments, and dozens of nodes, Rabl and Jacobsen propose a greedy heuristic that assigns queries to nodes one after another. In specific, they order queries by the product of their workload share and the overall size of accessed fragments. Queries are then assigned to the node with the largest fragment overlap with already assigned queries. Nodes with no assigned queries are treated as if they have a complete overlap. If the load of the assigned query exceeds the capacity of a node, the query is inserted back to the assignment list with its remaining load.
We implemented Rabl and Jacobsen’s algorithm and
investigated the steps chosen during allocations for TPC-H
and TPC-DS [
Our research addresses two shortcomings of Rabl and Jacobsen’s approach: (1) When ordering queries and determining overlap, the algorithm does not consider the specific accessed fragments, but only their sizes. (2) When assigning queries to nodes, the remaining queries are not analyzed. In contrast, our decomposition approach (see Section 4) divides the problem into subproblems which preserves the structure of the problem. Specifically, we regard all queries (whose load we try to divide into workload chunks) with all individual fragments the queries access.
Solutions/allocations of our algorithm can be used for
replicated databases, e.g., SAP HANA [
Using LP to solve allocation problems is flexible compared to rule-based heuristics. We can add or change constraints, and modify the objective function to address varied allocation problems, e.g., requiring to store only a certain subset of fragments (instead of all) or demanding a similar memory consumption per node. Including such constraints into a rule-based heuristic is more challenging, because it is more dicult to decide how and in which part to adapt the algorithm without losing sight of the optimization goal. 4.
The complexity of our query-driven workload distribution problem increases with an increasing number of nodes, queries, and fragments. It is challenging to find good heuristics, as minimizing data redundancy and balancing the load on additional replicas are in conflict with each other.
The core idea of our decomposition heuristic is to split
the workload iteratively using easier to solve but similar
subproblems, forming a tree. In specific, we split the
workload into chunks of queries, which access similar fragments.
Thereby, we reduce the data redundancy in each splitting
step. In the following, we describe the approach using an
example. In [
K
Figure 2 shows a decomposition of a workload, represented by the top node, to K = 2 + 2 = 4 final nodes, represented as leaves. Each parent node can have an arbitrary number of child nodes. The workload share of each child must correspond to the workload share of the leaves in its subtree. In Figure 2, the top node has two children. Both children have two leaves in their subtree. Therefore, their workload share is 2 ⇤ 14 = 12 .
Using the decomposition approach, we can split the
workload into an arbitrary number of final nodes with equal
workload shares. Note, the existence of a solution with equal
workload shares is guaranteed, because our model (like Rabl
and Jacobsen’s) allows to split query loads arbitrarily
without regard to query frequencies and costs, which both are
discrete (see [
With each decomposition, the problem gets easier as fewer
relevant queries and accessed fragments have to be
considered. For chunk 1 in Figure 2, the distribution problem is
shrunken to Q = 3 queries and N = 5 fragments. By
choosing the number of child nodes, we can control the problem
complexity. For large problem instances, it is advisable to
split the top node into a low number of chunks for lowest
computation times. If the problem is still too large, other
heuristic approaches, e.g., [
In this section, we demonstrate our heuristic using a realworld workload. We analyzed queries against an accounting table, comprising of N = 344 columns/fragments. We extracted Q = 4461 query classes, whose query costs are distributed exponentially. In particular, 38 queries account for more than 95% of the workload share.
We compare our solution to the greedy heuristic by Rabl
and Jacobsen [
W/W S -32% -42% -33% -36% -37%
We used the Gurobi Optimizer [
Numerical experiments show that our heuristic calculates
allocations with lower memory consumption than the
heuristic by Rabl and Jacobsen [
In addition, we plan to investigate the impact of di↵erent database fragmentations and query clusterings on the allocation, especially, in the case of skewed model input (cf. Section 4.1). When running workloads in practice, fragment allocations and workload distributions must consider further factors, e.g., data modification costs, robustness against failures, or changing model inputs, that are not included in the basic allocation problem (cf. Section 2). We describe our plans to address these factors in the following sections. 5.1
In practice, workloads consist of a number of active database connections sending a stream of queries. We model a workload as a set of queries in a potentially long period of time. The performance of an allocation in practice depends on the query timing, especially, whether all (or at least many) nodes are used for processing while there are pending queries. This can be supported by query scheduling: in case an incoming query is executable on multiple nodes, we send the query to the node with the lowest load.
Further, we can calculate allocations that trade memory consumption (allocating additional fragments to nodes) for flexibility (increased share of query loads to be processed by multiple replicas). Flexibility is also beneficial to handle imprecise query costs, e.g., caused by concurrency e↵ects at runtime. Currently, we use average query execution times as query costs metric, because they are easy to obtain and widely applicable. 5.2
As a result of inserts, updates, or deletes, data may change
over time. We can adapt our basic model to include data
modification costs. We are able to model update costs
either as execution costs similar to costs for read queries (see
also [
Besides scalability, data replication enables high
availability. Thereby, a database cluster can support di↵erent levels
of robustness in case of node failures. Basic robust
allocations ensure that each fragment is stored on multiple nodes,
or queries can be processed on multiple nodes [
Workloads (including query costs) or fragment sizes may change. As a result, a current data allocation may not allow an even workload distribution anymore or a di↵erent allocation may reduce the memory consumption.
If workload changes are known in advance, Rabl and
Jacobsen propose to calculate allocations for each scenario and
merge all of the allocations to a combined allocation that is
robust with regard to the workload changes [
As workloads and underlying data, and thus model inputs change, we want to adapt allocations over time, ideally without downtime or performance degradation. The previous sections described building blocks to implement a faulttolerant and adaptive replication cluster. We can monitor the workload to detect when we have to adapt a current allocation. At that time we can calculate a new allocation, which is better suited to the current workload and which can be created with reasonable reallocation costs.
We presented the current status and plans to extend our work in the field of query-driven workload distribution and fragment allocation. While balancing the query load evenly, our decomposition approach calculates cluster configurations with lower memory footprint than state-of-the-art heuristics. We believe that our approach allows integrating further factors, such as data modification costs, robustness against node failures, and economical reallocations. Using LP, we can express these factors as constraints without changing the structure of the algorithm. In future work, we plan to not only extend our LP approach, but also demonstrate the extensions in end-to-end evaluations.