PLB: Priority-Aware Load Balancing for Replicated Databases under Constrained Resources

arXiv:2608.06140v1 [cs.DB] 6 Aug 2026

PLB: Priority-Aware Load Balancing for Replicated Databases under Constrained Resources Belkis Djeffal

Pierre Bourhis

Romain Rouvoy

Inria, Univ. Lille, CNRS UMR 9189 CRIStAL, France belkis.djeffal@inria.fr

CNRS, Univ. Lille, Inria UMR 9189 CRIStAL, France pierre.bourhis@inria.fr

Univ. Lille, Inria, CNRS UMR 9189 CRIStAL, France romain.rouvoy@inria.fr

Abstract—Priority-differentiated services are a standard way for applications to expose different performance expectations, yet database systems still tend to treat all sessions alike. When database capacity is fixed, such that replicas cannot be added on demand, and the workload enters contention, this mismatch forces a choice between over-provisioning capacity and allowing lower-priority users to suffer much larger slowdowns. In such settings, we propose to enforce priority by controlling how client sessions are assigned to database replicas. We present PLB, a priority-aware load balancer implemented as a JDBC driver that uses replica assignment to enforce priority differentiation under fixed resources. PLB partitions replicas by user group (premium vs. freemium) and uses load-based borrowing so that higher-priority users can draw on idle capacity while lower-priority degradation remains controlled. We evaluate PLB on a replicated, read-only cluster under OLAP workloads. Compared with static dedicated per-priority partitions, PLB sustains utilization above ≈ 70% in settings where fixed partitions can drive cluster-wide CPU utilization down to ≈ 35%, while keeping latencies close to the best dedicated allocation. Compared with a fully shared round-robin pool, PLB reduces high-priority median latency by about 12% on average (up to 28%), while keeping the low-priority median overhead around 11% and leaving overall median latency close to round-robin.

I. I NTRODUCTION Cloud applications implement tiered service plans that associate different user classes with distinct performance expectations and economic value [1], [2]. This differentiation is reflected in various quality-of-service (QoS) dimensions— including features, response latency, and resolution—and is explicitly enforced at the application layer. However, at the database layer, this distinction is not preserved: database systems optimize queries without directly encoding the applicationlevel service tier of the user. This mismatch becomes particularly significant under resource contention. When database capacity is abundant, uniform optimization may suffice; all users can experience good performance regardless of priority. Under contention, however, the system must preserve better latency for high-priority users while allowing lower-priority users to experience predictable, graceful degradation. This paper focuses on read-only database deployments operating under a fixed replica budget. Such deployments can arise in analytical and machine-learning platforms, where a shared feature store or read-only database may simultaneously serve latency-sensitive online inference and more delay-tolerant offline training or evaluation over the same data. Although the workload is read-only, the services sharing these replicas may

still differ substantially in their latency requirements. Adding resources through elastic scaling might appear to address this problem, but in many settings it is impractical: provisioning a new replica introduces delay due to provisioning and data replication, while elastic scaling itself incurs operational complexity and cost [3], [4]. Moreover, on-premise deployments, edge environments, and resource-constrained cloud offerings may not permit capacity to be added on demand. Prior work has addressed priority through admission control [1], [2], [5] and database engine scheduling [6]–[8]. However, widely deployed systems such as PostgreSQL delegate CPU scheduling to the operating system and do not expose native mechanisms to assign query priorities or isolate priority classes within the engine [9]. In replicated databases, the load balancer mediates access to replicas and therefore provides a natural locus for priority-aware routing without requiring changes to the database engine [10], [11]. At that point, the problem is no longer whether priority should be enforced, but how replica capacity should be allocated across classes so that sharing does not erase isolation. In practice, two deployment choices are common. Dedicated clusters provide strong isolation, but waste capacity when demand is imbalanced: replicas reserved for one class may remain underutilized while the other class saturates. At the opposite extreme, a shared cluster achieves high utilization by allowing all sessions to access all replicas, but without priority-aware routing, all sessions compete equally for capacity, exposing high-priority traffic to the same slowdowns as best-effort traffic. Neither choice is satisfactory: the former sacrifices efficiency, while the latter sacrifices service differentiation. To address this gap, we introduce PLB, a priority-aware session assignment strategy for replicated databases under fixed resource constraints. The key idea is to preserve priority differentiation while dynamically sharing a fixed replica budget as the workload mix shifts. Concretely, PLB organizes replicas into three groups: Premium, Freemium, and Mixed, the latter acting as a dynamic buffer between the first two. When high-priority demand approaches saturation, PLB can temporarily reassign underutilized capacity; when pressure recedes, borrowed replicas are returned so that capacity sharing does not erase long-term isolation. PLB is implemented as a JDBC middleware layer that operates at session admission time, aligning with standard connection-level routing practice and avoiding modifications to the database engine internals [12]–

[14]. To evaluate this approach, we use the TPC-H decisionsupport benchmark [15] on a replicated, read-only PostgreSQL cluster under varying load levels and Premium:Freemium client mixes. We compare PLB against two common deployments: static dedicated clusters and a shared priority-agnostic roundrobin pool (RR). Our results show that PLB reacts better to changes in workload composition than fixed partitions: when the live Premium:Freemium mix diverges from the partition for which the deployment was sized, dedicated clusters can strand a large fraction of capacity and drive cluster-wide CPU utilization down to around 35%, whereas PLB keeps utilization above about 70% while maintaining latencies close to the best dedicated allocation. At the same time, PLB enforces service differentiation without substantially increasing overall cost: in our experiments, it improves Premium median latency by roughly 12% on average (up to 28%) and Premium p95 latency by about 10% (up to 14%), while keeping the Freemium penalty around 10% and leaving overall latency close to RR. This paper delivers four contributions: (1) We formalize the isolation-efficiency trade-off in priority-aware replica allocation for replicated databases. (2) We present PLB, a priorityaware session assignment policy with dynamic borrowing that achieves high utilization and service differentiation simultaneously. (3) We provide an open-source JDBC middleware implementation, and (4) we experimentally validate PLB across different workload configurations. The remainder of this paper is organized as follows. Sections 2–3 formalize the problem and introduce the PLB design. Sections 4–5 cover the experimental setup and empirical evaluation. Section 6 surveys related work, Section 7 discusses threats to validity, and Section 8 concludes. II. P ROBLEM S TATEMENT A. System & Workload Model We consider a cluster of K read-only replicas of a database, each running on a separate node. All replicas store the same data and share the same DBMS configuration; they only differ in their current load. The number of replicas K and their hardware configuration are fixed for the duration of the deployment and cannot be scaled on demand. Clients interact with the system through sessions—i.e., sequences of queries issued over persistent database connections. Each session is tagged with a priority class, Premium or Freemium, reflecting the client’s application-level service plan. Once a session is assigned to a replica, all its queries are executed on that replica; we do not migrate sessions between replicas, nor do we modify DBMS internals, such as the query optimizer or executor. Let Σ(t) denote the system state observed by the routing layer at time t (e.g., per-replica and per-class active-session counts). A routing strategy Γ assigns each incoming session to one replica in R = {1, . . . , K} as a function of the session’s priority class and Σ(t). Formally, when a session s arrives
at time t, the strategy chooses a replica Γ class(s), Σ(t) ∈ R that will serve that session.

B. Capacity, Load & Contention We model the current load on a replica as the number of active sessions. Let loadP (r, t) and loadF (r, t) denote the numbers of active Premium and Freemium sessions assigned to replica r ∈ R and not yet completed at time t. We write load(r, t) = loadP (r, t) + loadF (r, t) for the total number of active sessions on r. In our implementation, these per-class session counts are the primary load signals available to the routing layer. For each class c ∈ {P, F }, we configure a per-replica saturation threshold θc . We say that replica r has headroom for class c at time t when loadc (r, t) < θc , and that it is saturated for class c otherwise. These empirically calibrated thresholds, described in Section IV, are used as control signals by the routing policy. We refer to regimes in which many replicas approach or exceed their per-class thresholds as contention regimes. In such regimes, the routing strategy must enforce differentiation between Premium and Freemium while coping with fixed capacity. A practical solution must therefore preserve priority differentiation while keeping the fixed replica budget well utilized as the Premium:Freemium demand mix changes. C. Key Performance Metrics Because we consider read-intensive workloads (e.g., OLAP), we evaluate performance primarily in terms of query latency. For each workload run, we collect latency distributions separately for Premium, Freemium, and all queries, denoted respectively by ψP , ψF , and ψAll . In the evaluation, we summarize these distributions using central and tail statistics, depending on the experiment, to compare both typical and degraded behavior under contention. D. Service Level Objectives We characterize the behavior sought from a routing strategy under fixed resources through three objectives. O1: Prioritized Premium latency under contention: When the cluster enters a contention regime, Premium queries should systematically experience shorter latency than Freemium queries. As load increases and replicas saturate, ψP may grow, but it should grow more slowly than ψF , so that Premium sessions remain closer to their expected QoS. O2: Controlled Freemium degradation: While Freemium queries may be deprioritized under heavy load, they should not be starved. Compared to priority-agnostic strategies, such as round-robin, ψF under our design may be higher, but it should degrade smoothly rather than through pathological spikes. In the evaluation, we assess this objective empirically by comparing ψF against priority-agnostic baselines across various load levels.

O3: Efficient sharing under fixed capacity: Under a fixed replica budget, the routing strategy should sustain high utilization of the replica pool while keeping load well balanced across replicas as the Premium:Freemium demand mix varies. This objective captures the ability to adapt to changing demand without leaving part of the replica budget underused.

Borrowing is implemented as a temporary role change: the donor replica is moved into the borrower’s pool and is counted there until it is released. Returns are also implemented as role changes: an eligible borrowed replica is moved either to the pool whose target is not yet satisfied or to the Mixed pool.

E. Problem Formulation

Routing decisions are taken at session admission using perreplica, per-class active-session counts. For a replica r, we write loadP (r) and loadF (r) for the numbers of active Premium and Freemium sessions on r, observed at admission time. We also write load(r) = loadP (r) + loadF (r)

We formulate the addressed problem as: Given a fixed pool of K read-only replicas, a stream of incoming sessions tagged as Premium or Freemium, and per-replica load observations based on active sessions, we seek a session-level routing strategy Γ that satisfies O1–O3: it should preserve prioritized latency for Premium sessions under contention, keep Freemium degradation controlled relative to priorityagnostic baselines, and reuse idle replicas across classes without elastic scaling. III. P RIORITY-AWARE L OAD BALANCING We consider the model defined in Section II-A: a fixed pool of read-only replicas and session-level routing for two priority classes (Premium, Freemium). We operate at session admission time, which matches common connection-level routing practice in replicated database middleware and avoids per-query routing overhead. Our goal is to enforce priorityaware routing under fixed resources by combining class separation with temporary capacity sharing under pressure.

C. Load Metrics & Control Signals

for the total number of active sessions on r. The routing policy uses four control signals: • Saturation thresholds θP , θF : thresholds used to decide when a class has exhausted the headroom of its current pool and may attempt borrowing. • Return watermarks τc = ⌊αc θc ⌋: lower thresholds used to decide when pressure has eased enough to release borrowed capacity. • Freemium floor κF : minimum number of replicas kept in the Freemium pool when Premium borrows from that pool. • Pool targets KP , KF : configured target sizes used when deciding whether a returned replica should go to a class pool or to the Mixed pool.

A. High-Level Overview PLB partitions replicas into three pools: a Premium pool, a D. Admission and Return Policy Common principles: We call a replica Premium-empty Freemium pool, and a Mixed pool. Sessions are first routed to the pool currently assigned to their class as long as that pool when loadP (r) = 0. The following rules apply to both priority still has headroom. When a class exhausts its headroom, the classes. First, a class may borrow only when all active replicas router may temporarily borrow capacity from the Mixed pool currently assigned to that class are at or above the saturation or, under stricter conditions, from the opposite dedicated pool. threshold. Second, role changes are applied only at session Figure 1 summarizes the design. Figure 1a gives an example admission time: whether a replica is borrowed or released, of how replica assignments evolve over time, while Figure 1b existing sessions are not moved, interrupted, or killed; only summarizes the possible role transitions; the admission and future session assignments see the new role. Third, a borrowed replica is released only after pressure on the borrowing class return conditions are described below. The policy is asymmetric across classes. Premium may has dropped below the return watermark and after the replica borrow from the Mixed pool and, when a minimum reserve for no longer hosts sessions of that borrowing class. In the admission rules below, when PLB selects among Freemium is preserved, from the Freemium pool. Freemium may also borrow from the Mixed pool, but borrowing from replicas already assigned to class c, it uses loadc (r). For the Premium pool is permitted only when the donor replica replicas currently borrowed for class c, it uses the total load is empty of Premium sessions and the Premium pool target load(r), so that residual sessions from the previous role are counted. remains protected. Premium admission: A Premium session is first routed B. Replica Roles & Pool Partitioning to an eligible replica in RP , choosing the least-loaded replica At any time, the router maintains three replica sets: the whose Premium load is below θP . If no such replica exists, Premium pool, the Freemium pool, and the Mixed pool, denoted the router attempts to borrow from the Mixed pool. Among by RP , RF , and RM , respectively. The total replica budget is Mixed replicas, PLB first prefers replicas that do not already fixed, with K = |RP | + |RF | + |RM |. The initial split across host Premium sessions, so that Premium traffic is spread over additional replicas; it then chooses the one with the smallest the three pools is configured at startup. Replicas in RP serve Premium sessions by default, replicas Freemium load. in RF serve Freemium sessions by default, and replicas in RM If the Mixed pool is empty, PLB may borrow from the form a flexible buffer that can donate capacity in either direction. Freemium pool. This is allowed only if the Freemium floor is

PLB JDBC driver

Application

Mixed return(P,M)

return(F,M)

borrow(P,M) borrow(F,M)

borrow(P,F) T0

T1

T2

T3

(a) Routing dynamics over time.

T4

T5

T6

T7

Premium

return(P,F)

Freemium

(b) Conceptual role transitions.

Fig. 1. Overview of PLB. (a) Routing dynamics over time. (b) Conceptual borrow/return transitions between Premium, Freemium, and Mixed roles.

preserved, i.e., |RF | − 1 ≥ κF , and if the candidate Freemium pool targets KP , KF govern how conservatively capacity is replica is less loaded than the best current Premium choice shared and returned. For the experiments, these values are under the load convention above. calibrated once per replica budget and then kept fixed across Among eligible Freemium donors, PLB prefers replicas the full evaluation grid, as described in Section IV. below the Freemium return watermark and then chooses the Implementation: PLB is implemented as a JDBC midleast-loaded one. If no donor is eligible, the session is routed dleware that intercepts connection establishment. Replicas and to the least-loaded replica in RP . the initial pool split are provided through configuration files, Freemium admission: A Freemium session is first routed while role changes are maintained internally by the router. to a replica in RF whose Freemium load is below θF , choosing At session admission, the middleware identifies the session the least-loaded eligible replica. If no such replica exists, the priority, reads the current per-replica state (role and per-class router first considers donors in the Mixed pool, choosing the session counts), and applies Algorithm 1. Per-replica counters replica with the fewest active Premium sessions and then are updated atomically when a connection opens or closes. The the smallest active Freemium load. If Freemium still has no design is compatible with standard JDBC connection pools, eligible replica and the Mixed pool is empty, the router may since sessions remain pinned to their assigned replica for their borrow from the Premium pool, but only from replicas that lifetime. are Premium-empty and only if the Premium pool target is Complexity: Each admission scans at most K replicas. preserved, i.e., |RP | − 1 ≥ KP . If no donor is eligible, the Routing therefore runs in O(K) time, while the middleware session is routed to the least-loaded replica in RF . maintains O(K) state. Return: A borrowed replica is returned only when two IV. E XPERIMENTAL S ETUP conditions hold: pressure on the borrowing class has eased, and the borrowed replica no longer hosts sessions of the borrowing To assess the effectiveness of our priority-aware loadclass. Pressure is considered eased when some active replica balancing strategy under realistic conditions, we deploy it assigned to class c falls below the return watermark τc . on a physically distributed PostgreSQL cluster configured as When a borrowed replica is returned, it normally goes to the read-only replicas and simulate session priority and contention Mixed pool. The exception is when a class pool is below its con- using a custom benchmarking framework. figured target: a borrowed-to-Premium replica is assigned back to the Freemium pool if |RF | < KF , and to the Mixed A. Infrastructure & Workload pool otherwise. Symmetrically, a borrowed-to-Freemium Experiments are conducted on Grid’5000 [16], using horeplica is assigned back to the Premium pool if |RP | < KP , mogeneous physical machines from the gros cluster at the and to the Mixed pool otherwise. Nancy site. Each node is equipped with an 18-core Intel Xeon Algorithm 1 summarizes the session-admission path. The Gold 5220 CPU and 96 GiB of RAM. Replicas are provisioned functions selectM →P , selectF →P , and selectM →F use the as identical clones of the same dataset, while the workload donor-ordering rules described above. generator and JDBC middleware run on a dedicated injector node in order to isolate benchmarking overhead from database E. Implementation & Complexity execution. Configuration: The policy is instantiated through the All nodes run Ubuntu 22.04 LTS, PostgreSQL 14, and initial pool split and the control parameters introduced above. OpenJDK 21. PostgreSQL is tuned once for read-heavy In practice, the main controls are the per-class saturation workloads, starting from a PGTune [17] configuration and thresholds θc , which determine when borrowing is triggered; adjusting key settings such as shared buffers and parallelism the return watermark τc is derived from θc , while κF and the limits through workload-driven tests.

Algorithm 1 Priority-aware session admission 1: function ASSIGN S ESSION T O R EPLICA(p) 2: if p = premium then 3: D ← replicas in RP below θP 4: if D ̸= ∅ then 5: return least-loaded replica in D 6: end if 7: if RM ̸= ∅ then 8: rb ← selectM →P (RM ) 9: change role of rb to borrowed-to-Premium 10: return rb 11: end if 12: if |RF | − 1 ≥ κF then 13: mP ← load of the least-loaded replica in RP 14: CF ← Freemium donors with load below mP 15: if CF ̸= ∅ then 16: rb ← selectF →P (CF ) 17: change role of rb to borrowed-to-Premium 18: return rb 19: end if 20: end if 21: return least-loaded replica in RP 22: else ▷ Freemium 23: D ← replicas in RF below θF 24: if D ̸= ∅ then 25: return least-loaded replica in D 26: end if 27: if RM ̸= ∅ then 28: rb ← selectM →F (RM ) 29: change role of rb to borrowed-to-Freemium 30: return rb 31: end if 32: CP ← {r ∈ RP : loadP (r) = 0} 33: if CP ̸= ∅ and |RP | − 1 ≥ KP then 34: rb ← least-loaded replica in CP 35: change role of rb to borrowed-to-Freemium 36: return rb 37: end if 38: return least-loaded replica in RF 39: end if 40: end function

B. PLB Configuration In all experiments, we use a single PLB configuration per replica budget. This configuration is chosen once on the same TPC-H SF10 workload as in our evaluation, using a subset of client counts and Premium:Freemium mixes that cover both moderate and high load. Once chosen, the saturation thresholds and other PLB parameters are kept fixed for the full experimental grid. a) Saturation and return parameters: The per-class saturation thresholds θP and θF determine when a replica is considered to have exhausted headroom for a given class. We select these thresholds by sweeping θ over a small range on the calibration subset and measuring end-to-end latency for both priority classes. Very small values trigger borrowing too early and lead to unnecessary churn, whereas very large values delay borrowing and leave the mixed pool underused. We therefore set θP = θF = 10 for all reported experiments. Because these thresholds only determine when borrowing is triggered, we keep them symmetric across classes and express priority through pool partitioning, borrowing rules, and asymmetric return watermarks. Return watermarks τc = ⌊αc θc ⌋ and pool targets KP , KF determine when borrowed replicas can be returned and how the pool partition is restored once pressure has eased. We fix αP = 0.60 and αF = 0.80, so that replicas borrowed by Premium become eligible to return at a lower load than replicas borrowed by Freemium. For the five-replica budget, we initialize the pools as (|RP |, |RF |, |RM |) = (2, 2, 1), set KP = KF = 2, and keep a small Freemium floor κF = 1 to avoid giving away the last Freemium replica during borrowing.

C. Evaluation Protocol We evaluate PLB over a grid of load levels and priority mixes, and against the baselines introduced in Section V-A. The number of terminals T ranges from 30 to 2,500, and for each T we vary the Premium share from 20% to 80% in steps of 10 percentage points, yielding 161 distinct (T, Premium share) configurations. All configurations are executed sequentially in a single Our workload is based on TPC-H [15] at a scale factor of batch, with a single warmup before the batch begins. Each 10, representing read-only decision-support queries. We use configuration runs for 3 minutes and is repeated 10 times. B ENCH BASE [18], extended to support fixed session priorities During each run, we collect per-query latencies, per-session (premium or freemium), Poisson arrivals, and configurable statistics, and per-replica CPU usage. Latency distributions session lifetimes. Within each session, queries are selected for each class and the overall distribution are derived as uniformly at random from the TPC-H query set and executed in Section II-C, and CPU utilization and imbalance are sequentially. computed from pidstat samples, as detailed in Section V. All deployment and benchmarking scripts, including our In our modified B ENCH BASE, a terminal corresponds to JDBC middleware and modified B ENCH BASE, are publicly one JDBC session pinned to a single replica for its lifetime. 1 available. For a target of T terminals over duration D, arrivals follow an exponential process of rate λ = T /D, and each terminal V. E MPIRICAL R ESULTS lives for a duration uniformly sampled in [10, 30] seconds. A. Baselines, Configurations & Objectives Because sessions have finite lifetimes and include think time, We evaluate PLB under fixed replica budgets and compare the instantaneous number of concurrently executing PostgreSQL it with two deployment choices that a provider can implement backends per replica remains much smaller than T ; for example, today. For a given budget K, we consider: with five replicas and T =1000, we observe a median of about 1 https://zenodo.org/records/20233910 50 active backends per replica.

Strategy 3RR+2RR 4RR+1RR 5PLB10 Bucket P<40 40-60 P>60 Hybrid

Latency (Avg)

18 16 14 12 10 8 6

Premium

Latency (Avg)

18 16 14 12 10 8 6

Freemium 18 16 14 12 10 8

18 00

12 00

0 80

0 60

0 50

0

0

40

30

0 20

0

6

10

B. PLB vs. Dedicated Partitions

Overall

Latency (Avg)

1) Shared, priority-agnostic pool (KRR). All client sessions (Premium and Freemium) share the same set of K replicas, and connections are distributed using a standard policy such as round-robin. We denote this baseline by KRR (e.g., 5RR when K = 5). 2) Dedicated per-class partitions (rRR+f RR, r + f = K). The K replicas are statically partitioned between the two priority classes. The left-hand term counts Premium replicas and the right-hand term Freemium replicas; within each subset, sessions are routed by round-robin. We denote such a partition by rRR+f RR— e.g., 3RR+2RR (three Premium-only replicas and two Freemium-only replicas) or 4RR+1RR when K = 5. PLB itself uses all K replicas in a single shared pool but routes sessions with the priority-aware logic of Section III. We denote this configuration by KPLB (e.g., 5PLB, 6PLB). Our evaluation focuses on the objectives defined in Section II: prioritized Premium latency under contention, controlled Freemium degradation, and efficient sharing under fixed capacity. In a shared KRR pool, sessions are routed without regard to priority, with the result that Premium and Freemium latencies remain closely coupled. Dedicated per-class partitions provide stronger isolation, but require fixing the split a priori and become brittle once the Premium:Freemium mix drifts. The following subsections are organized around these objectives. We first examine whether PLB reproduces the class-level behavior of dedicated partitions across loads and mixes (O1, O2). We then study whether it uses the fixed replica budget more efficiently as the Premium:Freemium mix changes, while revisiting class-level latency at a fixed heavy load (O3, O1, O2). Finally, we compare PLB with shared round-robin to quantify the Premium gains and the induced cost for Freemium (O1, O2).

We compare 5PLB with two dedicated 5-replica partitions, Total Clients 3RR+2RR and 4RR+1RR, over terminal counts from 100 to 1, 800 and three representative Premium:Freemium mixes. Fig. 2. Per-class average latency vs. terminals for 5PLB and dedicated clusters Figure 2 reports the corresponding average latencies for Overall, (three mixes). Premium, and Freemium queries. Because these dedicated baselines are hybrid constructions built from separate Premiumonly and Freemium-only runs, we report average latency here: demand is low, its latency approaches that of 4RR+1RR; combined means can be computed from the component runs, as Premium traffic grows, it settles near 3RR+2RR. In whereas combined medians cannot. We then examine whether practice, Premium latency under 5PLB stays close to the PLB matches the class-level behavior of the best static partition three-replica dedicated baseline and often approaches the fouracross load levels and demand mixes, which speaks directly replica configuration when Premium demand is low, which is consistent with O1. to O1 and O2. At light load (T ≲ 200), all strategies exhibit nearly identical Freemium exhibits the symmetric effect. When Freemium latencies, reflecting that replicas are far from saturation. Under dominates, 5PLB slightly improves on 3RR+2RR, since contention, their behavior diverges. Overall average latency borrowing allows it to exploit more capacity than a fixed oneunder 5PLB remains close to 3RR+2RR and clearly below or two-replica budget. As Premium load increases, Freemium 4RR+1RR, indicating that enforcing priority does not incur a latency under 5PLB rises, but remains much closer to the visible aggregate cost. behavior of the dedicated configurations that preserve two On the Premium side, 5PLB behaves as if Premium were replicas for Freemium than to the one-replica worst case. This served by three to four dedicated replicas. When Premium controlled slowdown of the low-priority class, while the high-

C. PLB vs. Dedicated Partitions at Fixed Load

Cluster CPU fraction vs premium share (T = 1000) Mean cluster CPU fraction

priority class continues to track the best dedicated configuration, matches O2. Taken together, these curves show that 5PLB satisfies O1 and O2: across loads and mixes, Premium follows the best of 3RR+2RR and 4RR+1RR as contention increases, while Freemium remains close to a dedicated two-replica budget rather than collapsing to a one-replica worst case.

0.8 0.6 0.4

PLB

Replica imbalance (CV)

0.2 3RR+2RR We compare KPLB with dedicated per-class partitions at 4RR+1RR a fixed heavy load. Specifically, we set the total number of 0.0 terminals to T = 1000 and vary the Premium:Freemium mix, 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 in order to assess both resource efficiency (O3) and per-class performance relative to static partitions (O1, O2). Replica imbalance (lower is better) CPU metrics are obtained from pidstat samples. For 0.8 PLB each replica and second, we sum the user and system CPU 3RR+2RR percentages across postgres processes, divide by 100 · C 0.6 4RR+1RR (where C is the number of cores), and average over time to obtain a per-replica mean CPU fraction ui . ForPeach 0.4 1 configuration, cluster-level CPU utilization is u = K i ui , and the coefficient of variation CV(u) = σ(ui )/µ(ui ) measures 0.2 load imbalance across replicas. Both metrics are averaged across repeated runs. 0.0 Dedicated partitions are derived from single-priority round0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 robin experiments. For each Premium:Freemium mix (P, F ), Premium share we run 3RR and 4RR with P Premium terminals and 2RR and 1RR with F Freemium terminals, collect the per-replica means Fig. 3. CPU utilization and replica imbalance at T = 1000 terminals for ui , and use them as empirical pools. We then approximate 5PLB and dedicated partitions. 3RR+2RR and 4RR+1RR by bootstrap resampling from the corresponding Premium-only and Freemium-only pools, respectively, and report the average over 400 resamples. dedicated partition is competitive only near the Premium share CPU utilization and imbalance: Figure 3 shows the mean for which it is implicitly tuned. As the Premium share moves cluster CPU fraction and the coefficient of variation of per- away from those points, overall latency under 3RR+2RR or replica CPU across Premium shares at T = 1000. With 5PLB, 4RR+1RR deteriorates substantially; in the worst Freemiummixes between roughly 0.2 and 0.8 Premium share keep the heavy case, one of the dedicated partitions is more than cluster in a high-utilization, low-imbalance regime: u stays 30% slower than 5PLB. This mirrors the CPU results in between about 0.80 and 0.84, and CV(u) remains below 0.12. Figure 3: 5PLB uses the replica budget consistently across Even in the most skewed mixes, 5PLB does not drop below mixes, whereas static partitions incur penalties when their fixed u ≈ 0.69, with CV(u) well under 0.4. split no longer matches the workload. In contrast, dedicated partitions are much more brittle. When From the Premium perspective, dedicated partitions are the live Premium:Freemium mix diverges from the configured most advantageous when Premium is a minority, since they split, replicas tied to the minority class are underutilized while reserve three or four replicas exclusively for a small number majority replicas saturate. For example, in a Freemium-heavy of Premium sessions. In these mixes, 3RR+2RR achieves mix (Premium share 0.1), 4RR+1RR falls to about u ≈ 0.35 Premium medians about 8–17% lower than 5PLB, and with CV(u) ≈ 0.80, whereas 5PLB still reaches u ≈ 0.69 4RR+1RR about 12–25% lower. PLB deliberately does not with much lower imbalance (CV(u) ≈ 0.36). Symmetrically, chase this extra headroom: it keeps more replicas accessible to when Premium dominates (Premium share 0.9), 3RR+2RR Freemium, which generates most of the queries in this regime, leaves part of the cluster underused (u ≈ 0.67, CV(u) ≈ 0.59), rather than reserving most of the cluster for a small set of whereas 5PLB keeps more replicas busy and better balanced Premium sessions. As Section V-D shows, this sacrifice is (u ≈ 0.75, CV(u) ≈ 0.14). At T = 1000, these results support only relative to ideal dedicated partitions: even when Premium O3: 5PLB maintains high, well-balanced CPU utilization across traffic is modest, Premium latency under 5PLB remains mixes, whereas fixed partitions can strand a large fraction of comparable to, or better than, the shared 5RR baseline. Once capacity and introduce skew when the Premium:Freemium Premium traffic becomes substantial, the situation reverses: ratio shifts. 5PLB closely tracks the best dedicated partition and is up to Per-class latency at fixed load: Across mixes, 5PLB 16% better than 3RR+2RR. keeps overall median latency in a narrow band, whereas each Freemium exhibits the symmetric effect. When Freemium

Median latency (s)

Overall 17.5 15.0 12.5 10.0 7.5 5.0

Premium

Freemium

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Premium share

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Premium share

PLB 3RR+2RR 4RR+1RR

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Premium share

Fig. 4. Per-class median latency at T = 1000 terminals.

D. PLB vs. Round-Robin: Cost of Enforcing Priority We now compare PLB against the shared, priority-agnostic round-robin baseline RR to quantify both the Premium benefit of enforcing priority (O1) and the corresponding cost for Freemium behavior (O2). We set the replica budget to 5 replicas and compare 5PLB with 5RR across 39 workload configurations, derived from 13 terminal counts and three representative Premium:Freemium mixes. For each configuration, we collect per-run latency statistics for Premium and Freemium and apply Welch’s two-sample t-test [19] between PLB and RR on both median and 95thpercentile latencies. We summarize the results using a volcano plot (Figure 5), where each point corresponds to a single configuration. The xaxis reports the standardized Hedges’ effect size g [20] between PLB and RR, and the y-axis reports − log10 (p), where p is the p-value of the Welch test computed from per-run medians (top row) or 95th-percentile latencies (bottom row). The negative values of g indicate lower latency under PLB than under RR (improvement), and positive values indicate higher latency under PLB (regression). The horizontal dashed line marks

Premium (Median)

−log10 (p)

8

Freemium (Median)

Bucket Premium ≤40% ≈50:50 Premium ≥60%

6

significant improvement

significant degradation

non-significant improvement

non-significant degradation

4 2 0 Premium (95th)

Freemium (95th)

−2.5

−2.5

8 −log10 (p)

dominates, 5PLB achieves the lowest Freemium median, reducing it by roughly 14–17% compared to 3RR+2RR and by about 25–30% compared to 4RR+1RR. Around a balanced mix, the 5PLB Freemium median lies between the two dedicated partitions and remains close to the better one. As Premium becomes clearly dominant, PLB gradually withdraws borrowed capacity from Freemium: the best static partition can then make Freemium about 20–25% faster than under 5PLB, while the other remains within a few percent. This is the intended trade-off under heavy contention: PLB is willing to slow down the low-priority class relative to the most Freemiumfriendly partition when Premium drives the load, to keep Premium latency low. Together with the CPU results, these curves show that 5PLB meets O3 while preserving the intended class-level trade-offs of O1 and O2: overall latency stays within a few percent of the best dedicated configuration, Premium approaches its best achievable latency once it becomes the majority, and Freemium benefits when it dominates the workload.

6 4 2 0 0.0

2.5

0.0

2.5

Fig. 5. Latency volcano plots (5PLB vs 5RR).

the significance threshold (p = 0.05), while the vertical dotted lines provide descriptive reference bands for standardized effect sizes [21]. We use these bands as visual guides rather than universal decision thresholds. Premium latency: Across workloads, the Premium volcano plots are dominated by improvements. Out of 39 configurations, 26 show a statistically significant reduction in Premium median latency under PLB; the remaining configurations are not statistically distinguishable from RR. In those significant cases, Premium median latency typically improves by 8%–18% (median 11.5%) relative to RR, and reaches up to 28.4% in the best case. At the 95th percentile, 14/39 configurations show significant Premium tail reductions of about 10%, reaching up to 14%, with no significant regressions. Once contention appears, PLB therefore shifts the Premium

latency distribution towards lower values at both the median and the tail. Freemium latency: For Freemium, the volcano plots show the expected cost of enforcing priority. Across 39 configurations, 28 show a significant increase in Freemium median latency under PLB, with an overhead of about 11% relative to RR. At the 95th percentile, 14 configurations show a significant slowdown of about 7%, reaching up to 15% in the worst case. These slowdowns are concentrated in Premiumdominated mixes, where the policy is designed to protect Premium. This shows that the cost of enforcing priority remains moderate: even when Freemium slows down under PLB, the degradation stays on the order of 10% rather than factors, while overall latency remains close to RR, consistent with O2. Taken together, these results show that PLB meets O1 and O2: it improves Premium latency over shared RR while keeping the induced Freemium slowdown controlled. VI. R ELATED WORK Prior work on load balancing and replica selection for distributed databases has primarily focused on optimizing performance, placement, or fairness without explicit consideration of user or service tiers. Techniques such as load balancing through replica swaps in multi-tenant databases [22], gametheoretic allocation in elastic database clusters [23], workloadaware replica selection [24], [25], and adaptive replica provision or fragment allocation under changing workloads [26]–[28] improve efficiency and responsiveness, but do not address service-tier differentiation at the session-routing layer. In contrast, PLB targets replicated databases under fixed resources and makes user priority an explicit signal in replica assignment. Prior work has approached priority through a range of mechanisms, including admission control and query scheduling. SmartSLA, ActiveSLA, and Bouncer [1], [2], [5] decide whether or when to admit a request based on predicted system behavior and SLA objectives, while workload-aware schedulers and performance prediction methods prioritize concurrent queries inside the engine [6], [7]. These approaches are complementary to ours, but operate at the level of admission or query execution rather than deciding, at session open, which replica should serve a given priority class. More broadly, service differentiation and fixed-capacity resource management have been explored at the infrastructure level. Priority-aware resource sharing in edge and cloud systems [29]–[32] show the value of embedding service differentiation throughout the stack, while capacity-aware resource management approaches [1], [33] study efficiency under nonelastic resources. However, these works operate at the VM, application, or network layer, or do not incorporate servicetier awareness into replica assignment. PLB instead addresses priority-aware capacity sharing at the database session layer in replicated deployments. VII. T HREATS TO VALIDITY Workload and system scope: Our evaluation focuses on a read-only OLAP setting using TPC-H at a single scale

factor on PostgreSQL 14 in a replicated deployment over homogeneous machines. This matches our target scenario, but does not cover OLTP or mixed read/write workloads, other DBMSs, replication schemes, or heterogeneous hardware. In such settings, contention may arise differently, and we therefore do not expect the exact numerical results reported here to carry over unchanged. Configuration and priority model: PLB exposes a small set of parameters, which in this study are fixed once per replica budget using the calibration procedure of Section IV; we do not explore the full parameter space or automatic tuning. We also restrict attention to two priority classes and session-level routing, assuming that sessions can be tagged with a class. This leaves richer service hierarchies and per-query priorities outside the scope of the present study. VIII. C ONCLUSION & P ERSPECTIVES This paper addressed priority-aware routing in replicated databases under a fixed replica budget. We presented PLB, a session routing strategy that partitions replicas by priority class and borrows capacity across classes under contention without modifying the database engine. Our evaluation shows that PLB provides a middle ground between static dedicated partitions and a fully shared roundrobin pool. Compared to dedicated clusters, it avoids underutilized replicas and large load imbalances when the Premium:Freemium mix changes, while keeping latency close to that of the best static allocation. Compared to round-robin, it improves Premium median latency by about 11–12% on average, up to 28%, while keeping the Freemium overhead around 10% and leaving overall latency largely unchanged. Overall, PLB achieves prioritized latency for high-priority users, controlled degradation for low-priority users, and efficient sharing of a fixed replica budget. Although we evaluate PLB on a replicated relational database, the same approach to priority-aware capacity sharing may also apply to other replicated, read-heavy services operating under fixed resource budgets. Likewise, the Premium/Freemium classes used in our experiments are only one interpretation of priority: the same mechanism could also differentiate applications, tenants, or request types with different latency requirements. Future work includes extending PLB beyond two priority classes, exploring query-level routing, and studying transactional, mixed, and multi-tenant workloads. ACKNOWLEDGMENT This work received funding from the France 2030 program, managed by the French National Research Agency under grant agreement No. ANR-23-PECL-0003.

R EFERENCES [1] P. Xiong, Y. Chi, S. Zhu, H. J. Moon, C. Pu, and H. Hacıgümüş, “Smartsla: Cost-sensitive management of virtualized resources for cpubound database services,” IEEE Trans. Parallel Distrib. Syst., vol. 26, no. 5, p. 1441–1451, May 2015. [2] P. Xiong, Y. Chi, S. Zhu, J. Tatemura, C. Pu, and H. Hacıgümüş, “Activesla: a profit-oriented admission control framework for databaseas-a-service providers,” in Proceedings of the 2nd ACM Symposium on Cloud Computing, ser. SOCC’11. ACM, 2011. [3] R. Taft, N. El-Sayed, M. Serafini, Y. Lu, A. Aboulnaga, M. Stonebraker, R. Mayerhofer, and F. Andrade, “P-store: An elastic database system with predictive provisioning,” in Proceedings of the 2018 International Conference on Management of Data, ser. SIGMOD’18. ACM, 2018, p. 205–219. [4] Y. Yang, Q. Cao, and H. Jiang, “EdgeDB: An efficient time-series database for edge computing,” IEEE Access, vol. 7, pp. 142 295–142 307, 2019. [5] H. Xu and J. A. Colmenares, “Bouncer: Admission control with response time objectives for low-latency online data systems,” in Companion of the 2024 International Conference on Management of Data, ser. SIGMOD’24. ACM, 2024, p. 400–413. [6] B. Wagner, A. Kohn, and T. Neumann, “Self-tuning query scheduling for analytical workloads,” in Proceedings of the 2021 International Conference on Management of Data, ser. SIGMOD’21. ACM, 2021, p. 1879–1891. [7] Z. Wu, M. Markakis, C. Liu, P. B. Chen, B. Narayanaswamy, T. Kraska, and S. Madden, “Improving dbms scheduling decisions with accurate performance prediction on concurrent queries,” Proc. VLDB Endow., vol. 18, no. 11, p. 4185–4198, Sep. 2025. [8] I. Sabek, T. S. Ukyab, and T. Kraska, “Lsched: A workload-aware learned query scheduler for analytical database systems,” in Proceedings of the 2022 International Conference on Management of Data, ser. SIGMOD’22. ACM, 2022, p. 1228–1242. [9] PostgreSQL Wiki contributors, “Priorities,” https://wiki.postgresql.org/ wiki/Priorities, Apr. 2017, postgreSQL Wiki. Last updated: 2017-04-28. [10] M. Kleppmann, Designing Data-Intensive Applications. O’Reilly Media, 2017, ch. 5. [11] G. Kim and W. Lee, “In-network leaderless replication for distributed data stores,” Proc. VLDB Endow., vol. 15, no. 7, p. 1337–1349, Mar. 2022. [12] Pgpool Global Development Group, “Pgpool-ii — middleware that works between postgresql servers and clients,” https://www.pgpool.net/, 2025, accessed: 2025-11-03. [13] HAProxy Technologies, “Haproxy — the reliable, high performance tcp/http load balancer,” https://www.haproxy.org/, 2025, accessed: 202511-03. [14] PgPool Global Development Group, “Pgpool-ii documentation: Connection pooling,” 2025. [Online]. Available: https://www.pgpool.net/ docs/latest/en/html/runtime-config-connection-pooling.html [15] Transaction Processing Performance Council, “TPC Benchmark™ H (Decision Support), Standard Specification, Revision 3.0.1,” http://www. tpc.org/tpch/, 2022, transaction Processing Performance Council, San Francisco, CA. [16] “Grid’5000: A large scale and flexible testbed for experiment-driven research,” https://www.grid5000.fr, 2024. [17] A. Vasiliev, “Pgtune: calculate configuration for postgresql based on the maximum performance for a given hardware configuration,” 2025, accessed 2025-12-12. [Online]. Available: https://pgtune.leopard.in.ua/ [18] D. E. Difallah, A. Pavlo, C. Curino, and P. Cudré-Mauroux, “Oltp-bench: An extensible testbed for benchmarking relational databases,” PVLDB, vol. 7, no. 4, pp. 277–288, 2013. [19] B. L. Welch, “The generalization of student’s problem when several different population variances are involved,” Biometrika, vol. 34, no. 1–2, pp. 28–35, 1947. [20] L. V. Hedges, “Distribution theory for glass’s estimator of effect size and related estimators,” Journal of Educational Statistics, vol. 6, no. 2, pp. 107–128, 1981. [21] J. Cohen, Statistical Power Analysis for the Behavioral Sciences, 2nd ed. Hillsdale, NJ: Lawrence Erlbaum Associates, 1988. [22] H. J. Moon, H. Hacıgümüş, Y. Chi, and W.-P. Hsiung, “Swat: a lightweight load balancing method for multitenant databases,” in Proceedings of the 16th International Conference on Extending Database Technology, ser. EDBT’13. ACM, 2013, p. 65–76.

[23] R. Marcus, O. Papaemmanouil, S. Semenova, and S. Garber, “Nashdb: An end-to-end economic method for elastic database fragmentation, replication, and provisioning,” in Proceedings of the 2018 International Conference on Management of Data, ser. SIGMOD’18. ACM, 2018, p. 1253–1267. [24] K. A. Kumar, A. Quamar, A. Deshpande, and S. Khuller, “Sword: workload-aware data placement and replica selection for cloud data management systems,” The VLDB Journal, vol. 23, no. 6, p. 845–870, Dec. 2014. [25] W. Jiang, L. Fang, H. Xie, X. Zhou, and J. Wang, “Tars: Timelinessaware adaptive replica selection for key-value stores,” in 2017 26th International Conference on Computer Communication and Networks (ICCCN), 2017, pp. 1–9. [26] Q. Zheng, Z. Zhao, W. Lu, C. Yao, Y. Chen, A. Pan, and X. Du, “Lion: Minimizing distributed transactions through adaptive replica provision,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE), 2024, pp. 2012–2025. [27] S. Halfpap and R. Schlosser, “Fragment allocations for partially replicated databases considering data modifications and changing workloads,” in Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, ser. CIKM’24. ACM, 2024, p. 758–767. [28] ——, “Exploration of dynamic query-based load balancing for partially replicated database systems with node failures,” in Proceedings of the 29th ACM International Conference on Information & Knowledge Management, ser. CIKM’20. ACM, 2020, p. 3409–3412. [29] P. S. Pati, M. Sonu, R. Datta, D. Krishnaswamy, and C. Singhal, “Pars: A priority-aware resource sharing scheme for services with differential qos requirements in b5g edge network,” IEEE Networking Letters, vol. 5, no. 2, pp. 105–109, 2023. [30] Y. Ren, S. Shen, Y. Ju, X. Wang, W. Wang, and V. C. Leung, “Edgematrix: A resources redefined edge-cloud system for prioritized services,” in IEEE INFOCOM 2022 - IEEE Conference on Computer Communications. IEEE, 2022, p. 610–619. [31] D. Dhaanish and N. R. Reddy, “SLA-aware load balancing in cloud computing using machine learning based virtual machine scheduling,” Journal of Computer Allied Intelligence, vol. 3, no. 3, pp. 11–27, Jun. 2025. [32] W. Ke, Y. Wang, and M. Ye, “Grsa: Service-aware flow scheduling for cloud storage datacenter networks,” China Communications, vol. 17, no. 6, pp. 164–179, 2020. [33] A. Hussain, M. Aleem, A. Ur Rehman, and U. Arshad, “DE-RALBA: Dynamic enhanced resource aware load balancing algorithm for cloud computing,” PeerJ Computer Science, vol. 11, p. e2739, 2025.

Related documents

• Replication data#208051
• FlintKV: A Fast Durable Storage Engine for Modern Databases#332486
• Replication-Aware Placement of Functions and Data in the Edge-Cloud Continuum#1013089
• Replication-Aware Placement of Functions and Data in the Edge-Cloud Continuum#965376
• A Scalable Digital Twin Framework for Energy Optimization in Data Centers#168279