Louis-Claude Canon
email: louis-claude.canon@femto-st.fr

Anthony Dugois
email: anthony.dugois@ens-lyon.fr

Loris Marchal
email: loris.marchal@ens-lyon.fr

Bounding the Flow Time in Online Scheduling with Structured Processing Sets

Keywords: Flow Time, Lower Bound, Restricted Assignment, Processing Set Restrictions, Replication, Key-Value Stores

Replication in distributed key-value stores makes scheduling more challenging, as it introduces processing set restrictions, which limits the number of machines that can process a given task. We focus on the online minimization of the maximum response time in such systems, that is, we aim at bounding the latency of each task. When processing sets have no structure, Anand et al. (Algorithmica, 2017) derive a strong lower bound on the competitiveness of the problem: no online scheduling algorithm can have a competitive ratio smaller than Ω(m), where m is the number of machines. In practice, data replication schemes are regular, and structured processing sets may make the problem easier to solve. We derive new lower bounds for various common structures, including inclusive, nested or interval structures. In particular, we consider fixed sized intervals of machines, which mimic the standard replication strategy of key-value stores. We prove that EFT (Earliest Finish Time) scheduling is (3-2/k)-competitive when optimizing maxflow on disjoint intervals of size k. However, we show that the competitive ratio of EFT is at least m -k + 1 when these intervals overlap, even when unit tasks are considered. We compare these two replication strategies in simulations and assess their efficiency when popularity biases are introduced, i.e., when some machines are accessed more frequently than others because they hold popular data. Even though overlapping intervals suffer from a bad worst-case in theory, they enable clusters to reach a maximum load that is up to 50% higher than with disjoint sets.

I. INTRODUCTION

Since more than a decade, a variety of applications increasingly relies on key-value stores to record user data [START_REF] Featherston | Cassandra: Principles and application[END_REF], monitoring information in scientific projects [START_REF] Sicoe | A persistent back-end for the atlas tdaq online information service (pbeast)[END_REF], activity logs, metadata, statistics, etc. Such systems deal with a heavy load and while they succeed to process most requests with reasonable performance, they are prone to high delays for a few tasks (also known as the tail latency problem [START_REF] Atikoglu | Workload analysis of a large-scale key-value store[END_REF], [START_REF] Dean | The tail at scale[END_REF]), which motivates the design of efficient processing strategies.

The large amount of stored data most commonly requires the replication of the key-value tuples on distributed resources. This mechanism ensures high availability in the case of a large number of requests. For instance, Dynamo [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF] replicates data on nodes organized as a ring in a clockwise fashion. This approach inspired other implementations such as Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF], Riak KV and Project Voldemort [START_REF] Sumbaly | Serving large-scale batch computed data with project voldemort[END_REF]. However, this eligibility constraint of each task to specific machines prevents achieving optimal performance in current systems. Moreover, loads between machines tend to be heterogeneous [START_REF] Cavalcante | Popring: A popularity-aware replica placement for distributed key-value store[END_REF], [START_REF] Makris | Load balancing for minimizing the average response time of get operations in distributed key-value stores[END_REF] due to varying popularities between the keys, which constitutes an additional challenge. Finally, requests vary in size and the moment they are performed cannot be predicted precisely, leading to a difficult problem.

In this paper, we focus on the scheduling problems that appear in key-value stores and other distributed systems using data replication. We consider requests for data in the keyvalue store as tasks to be processed on a server (or machine in the scheduling terminology). In key-value stores, the most common objective is to minimize the response time, which is the time between the submission of a request (the release of a task) and the moment a server answers this request (completion time of the task). In the scheduling literature, this is called the flow time. Given the dynamic nature of the problem, we focus on simple practical algorithms with competitive guarantees: we say that an online algorithm (without knowledge of future tasks) is ρ-competitive if it provides a solution that is always at most ρ times worst than an optimal offline solution. Using Graham's notation [START_REF] Graham | Optimization and approximation in deterministic sequencing and scheduling: a survey[END_REF], we consider the problem P |online-r i |F max : minimize the maximum flow time (F max ) on identical machines (P ), with tasks released over time (r i ) without prior knowledge of tasks before their release times (online). For this problem, FIFO (First In First Out) is known to be a good solution: it is (3 -2/m)competitive on m parallel machines [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF], [START_REF] Mastrolilli | Scheduling to minimize max flow time: Off-line and on-line algorithms[END_REF].

A major difficulty that we need to take into account is that data are not replicated everywhere in key-value stores: only a subset of servers holds the data for a specific request. In the scheduling literature, processing set restrictions are used to model the fact that only a subset M i of machines may process some task T i . This constraint makes the problem a lot more difficult: Anand et al. [START_REF] Anand | Minimizing maximum (weighted) flow-time on related and unrelated machines[END_REF] prove a lower bound of Ω(m) on the competitive ratio of any online algorithm.

However, processing set restrictions often exhibit particular structures such as the clockwise ring used by Dynamo. In this case, data are replicated on direct neighbors forming an interval of consecutive machines, and it is unknown if this enables better results. In particular, we show that EFT, which is equivalent to FIFO for the problem P |online-r i |F max (Section IV), is a good strategy in some cases, but suffers from inefficient worst case performance with such realistic processing set restrictions (Section V). Moreover, we establish the challenge of this problem, even with specific processing set restrictions, by proving lower bounds on the competitive ratio of any simple algorithm. Section VI provides the last contribution by assessing the interaction of the popularity bias, or load imbalance, with the replication scheme in key-value stores. The rest of this paper starts by covering related works (Section II) and presenting the model (Section III).

II. RELATED WORK

Max-flow minimization. Bender et al. were the first to propose the max-flow objective F max = max i (C i -r i ) [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF], [START_REF] Bender | New algorithms and metrics for scheduling[END_REF], in which C i and r i denote the completion and release times of the i-th task, respectively. They show that the wellknown FIFO strategy is a (3-2/m)-competitive algorithm for minimizing max-flow on m parallel machines (note that this ratio is tight [START_REF] Mastrolilli | Notes on max flow time minimization with controllable processing times[END_REF]), and they give a lower bound of 3/2 on the online problem's competitiveness. The offline minimization of max-flow is strongly NP-hard since it is a generalization of the parallel makespan problem; Mastrolilli gives an FPTAS (Fully Polynomial-Time Approximation Scheme) in unrelated setting that runs in time O(nm(n 2 /ε) m ) [START_REF] Mastrolilli | Scheduling to minimize max flow time: Off-line and on-line algorithms[END_REF], where n is the number of tasks. When preemption is allowed, the problem becomes solvable on unrelated machines, as F max is a special case of L max , in which a task's deadline is set to the value of its release time (i.e., d i = r i ) [START_REF] Lawler | On preemptive scheduling of unrelated parallel processors by linear programming[END_REF]- [START_REF] Legrand | Minimizing the stretch when scheduling flows of divisible requests[END_REF]. FIFO has also been shown to be (3 -2/m)-competitive for the preemptive problem [START_REF] Mastrolilli | Scheduling to minimize max flow time: Off-line and on-line algorithms[END_REF]. Ambühl et al. refine the lower bound for both the preemptive and non-preemptive versions, proving that no online algorithm can achieve a ratio better than 2 -1/m [START_REF] Ambühl | On-line scheduling to minimize max flow time: an optimal preemptive algorithm[END_REF]. They provide an optimal algorithm for the preemptive case (i.e., matching the lower bound) and a lower bound of 2 for the non-preemptive problem when m = 2, implying that FIFO is also optimal on two parallel machines. In related setting, Bansal et al. derive lower bounds of Ω(m) and Ω(log m) on the competitive ratio of SLOW-FIT and GREEDY [START_REF] Bansal | Minimizing maximum flow-time on related machines[END_REF]. They develop a new online algorithm, DOUBLE-FIT, that is 13.5-competitive by combining these two strategies. They also present a PTAS in unrelated environment, running in time n O(m/ε) [START_REF] Bansal | Minimizing flow time on a constant number of machines with preemption[END_REF], and an offline O(log n)-approximation [START_REF] Bansal | Minimizing flow-time on unrelated machines[END_REF].

Processing set restrictions. Various surveys have been conducted on scheduling problems involving processing set restrictions. The majority of such problems concern makespan minimization in a wide range of situations, including preemption, structured sets, release times, and so on [START_REF] Brucker | Complexity of scheduling problems with multi-purpose machines[END_REF]- [START_REF] Leung | Scheduling with processing set restrictions: A literature update[END_REF]. To the best of our knowledge, the only result on online max-flow minimization under (unstructured) processing set restrictions is due to Anand et al., who derive a lower bound of Ω(m) on the competitive ratio of any online algorithm [START_REF] Anand | Minimizing maximum (weighted) flow-time on related and unrelated machines[END_REF].

Table I summarizes existing results on online max-flow minimization. In this table, P , P |M i , Q and R respectively denote parallel machines, parallel machines with processing set restrictions, related machines, and unrelated machines. Note that we have P → Q → R and P → P |M i → R, where A → B means that A is a special case of B.

III. MODEL

Even though our problem originates from key-value stores, we formally formulate it using classical scheduling terms. In particular, we want to schedule a set T of n tasks T 1 , . . . , T n on a set M of m homogeneous machines M 1 , . . . , M m (or n requests on m servers/processors). Each task T i has a release time r i ≥ 0 and a processing time p i > 0. Any machine cannot process several tasks simultaneously and preemption is not allowed. Tasks arrive in the system over time and no information (release or processing time) on task T i is available to the scheduler before time r i , which is noted online-r i . Without loss of generality, we assume tasks are numbered such that i < j =⇒ r i ≤ r j .

Processing set restrictions (or eligibility constraints) prevent tasks to be processed on any machine. Formally, a task T i can only be processed by a subset of machines M i ⊆ M and we say that M i is the processing set of T i . Let us consider the following special structures for these processing sets: M i (interval). Interval processing sets are such that for all

T i , M i = {M j s.t. a i ≤ j ≤ b i } or M i = {M j s.t. j ≤ a i or b i ≤ j}, for some a i ≤ b i . M i (nested).
Nested processing sets are such that for all T i , T j (with i = j), either

M i ⊆ M j , M j ⊆ M i or M i ∩ M j = ∅. M i (inclusive).
Inclusive processing sets are such that for all T i , T j (with i = j), either M i ⊆ M j or M j ⊆ M i . M i (disjoint). Disjoint processing sets are such that for all T i , T j (with i = j), either

M i = M j or M i ∩ M j = ∅.
The nested, inclusive and disjoint processing set restrictions can be seen as special cases of the interval processing set restriction because it is always possible to reorder the machines in each subset M i so that one obtains contiguous intervals of machines. Furthermore, the inclusive and disjoint processing set restrictions are special cases of the nested processing set restriction.

In key-value stores, requests indicate which file to retrieve based on a key that can be used multiple times. This implies that multiple tasks may share the same processing time and processing set.

We can now define the desired output and objective function. For any scheduling algorithm S, we note ρ S i the time at which T i is scheduled by S, µ S i the index of the machine on which T i is scheduled by S, and σ S i the starting time of T i under S. In other words, S gives a schedule Π S such that Π S (i) = (µ S i , σ S i ) for all task T i . We want to minimize the maximum flow time F S max = max F S i , where

F S i = C S i -r i (C S i denotes the completion time of T i in Π S : C S i = σ S i +p i ).
The superscript S is omitted when the considered algorithm is obvious from context.

We say that an online algorithm D has the Immediate Dispatch property if all tasks are scheduled as soon as they arrive in the system, i.e., for all T i , we have r i ≤ ρ D i < r i + ε, where 0 < ε 1, and we call D an immediate dispatch algorithm. This property is of particular importance in systems that need to scale and cannot handle large waiting queues; the scheduling phase should be as fast as possible. It is often the case in online distributed systems such as load balancers or replicated key-value stores. IV. EQUIVALENCE OF FIFO AND EFT STRATEGIES FIFO scheduling has been extensively studied in previous work. It consists of a single queue of tasks, located on a central scheduler, that are pulled whenever some machine is available (see Algorithm 1). It is known to be (3 -2/m)competitive when minimizing maximum flow time on parallel machines [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF], [START_REF] Mastrolilli | Scheduling to minimize max flow time: Off-line and on-line algorithms[END_REF], [START_REF] Bender | New algorithms and metrics for scheduling[END_REF], which makes it optimal on a single machine. In the present paper, we move our focus to the EFT scheduler (see Algorithm 2), which pushes each released task on the machine that finishes the earliest. We show here that both schedulers are equivalent on any instance of the scheduling problem P |online-r i |F max . However, EFT has two main advantages over FIFO, which motivates our choice:

1) FIFO relies on a centralized queue, whereas EFT allocates tasks to machines as soon as they arrive (it is an immediate dispatch algorithm). Hence, it does not require a centralized scheduler with a potentially large queue of jobs, which is impractical in most existing online systems with critical scalability needs. 2) EFT can easily be extended to scenarios with processing set restrictions, whereas transforming FIFO to allow such constraints would be cumbersome. For each machine M j ∈ M and for any 1 ≤ i ≤ n, let H j,i denote the subset of tasks T 1 , . . . , T i being assigned to M j in a schedule Π:

H j,i = {T i ∈ T s.t. 1 ≤ i ≤ i and µ i = j}.
Then we define C j,i as the time at which M j completes its assigned tasks among the first i tasks in Π, i.e., C j,i = max

T i ∈Hj,i {C i } ,
where C i = σ i + p i is the completion time of T i in Π, with the convention C j,0 = 0. Finally, we define U i as the set of machines that may start the i-th task at the earliest possible time t min,i = max r i , min Mj ∈M {C j,i-1 } , i.e., U i is the set of machines that are in a tie for T i :

U i = {M j ∈ M s.t. C j,i-1 ≤ t min,i } . (1)
Note that EFT needs to know the set U i for each released task T i , which implies that one must know the processing time of arriving tasks with precision, in order to compute the completion times of machines at each step (we are in a clairvoyant setting). In this way, EFT can be readily modified to account for processing set restrictions by changing Equation ( 1) to

U i = M j ∈ M i s.t. C j,i-1 ≤ t min,i , (2)
where t min,i = max r i , min Mj ∈Mi {C j,i-1 } .

For both EFT and FIFO strategies, a tie-break policy decides which machine will process T i . We consider that ties are broken according to the same policy BREAKTIE in FIFO and EFT (in FIFO, ties are broken when at least 2 machines are idle at the same time; we assume the selected machine runs first).

Algorithm 1 FIFO Require: Global FIFO queue Q Input: Incoming tasks T i Output: Allocated machines µ i , starting times σ i 1: when a new task T i is released do 2:
enqueue(i , Q)

In parallel, do:

1: when some machines U are idle at time t do

2: i ← dequeue(Q) 3: if i = NIL then 4: u ← BREAKTIE(U ) 5: µ i ← u 6: σ i ← t
Now we show that EFT is equivalent to FIFO for the problem P |online-r i |F max . We give the proof in the companion research report [START_REF] Canon | Bounding the Flow Time in Online Scheduling with Structured Processing Sets (extended version)[END_REF].

Proposition 1. For any instance I of the problem P |online-r i |F max , we have FIFO(I) = EFT(I), i.e., Π FIFO (i) = Π EFT (i) for all T i ∈ T in the instance I.

Algorithm 2 EFT Input: Incoming tasks T i Output: Allocated machines µ i , starting times σ i 1: when a new task T i is released do 2:

Get U i according to completion times of machines M (Equation ( 1))

3:

u ← BREAKTIE(U i ) 4: µ i ← u 5: σ i ← max (r i , C u,i-1 ) 6:
Update the completion time of M u

The equivalence between EFT and FIFO implies that all existing results for FIFO also apply to EFT in the context of max-flow minimization on parallel machines without processing set restrictions.

V. BOUNDS UNDER PROCESSING SET RESTRICTIONS

Obviously, the problem P |r i , M i |F max is NP-hard in the offline context, that is, when all details on tasks are available beforehand. However, when considering tasks with unit processing times, Brucker et al. show that the problem [START_REF] Brucker | Complexity of scheduling problems with multi-purpose machines[END_REF]. Thus, P |r i , p i = 1, M i |L max is also polynomial, and by setting the deadline d i = r i for all tasks, it follows that

P |r i , p i = 1, M i | w i T i is solvable in polynomial time
P |r i , p i = 1, M i |F max is polynomial. Anand et al. show that P |online-r i , p i = 1, M i |F max
has a lower bound of Ω(m) on the competitive ratio of any online algorithm [START_REF] Anand | Minimizing maximum (weighted) flow-time on related and unrelated machines[END_REF] (even the ones that do not have the Immediate Dispatch property). However, their proof is only valid for the general constraint M i , and it is unknown if special structures of the processing sets make the problem easier.

We provide here lower bounds on the competitive ratios of scheduling algorithms when considering that the processing sets follow a particular structure. Table II gives a summary of the results presented here.

We first study the inclusive structure of processing sets. We show in Theorem 1 that restricting to this structure reduces the lower bound on the competitive ratios to log 2 (m) + 1 for immediate dispatch algorithms. This is also true for the nested and interval structures, as they generalize the inclusive structure.

Theorem 1. The competitive ratio of any immediate dispatch algorithm is at least log 2 (m) + 1 for the problem P |online-r i , p i = p, M i (inclusive)|F max .

Proof: Let us assume that we work on a number of machines m that is a power of 2, i.e., m = 2 log 2 (m ) , where m is the actual number of machines. Let D be an arbitrary online immediate dispatch algorithm. We build the following adversary. For each such that 1 ≤ ≤ log 2 (m), let T ( ) denote the set of m 2 tasks with p i = p > log 2 (m) and r i = -1 for all T i ∈ T ( ) . A final task is released at time

r i = log 2 (m).
Then we define M (1) = {M 1 , . . . , M m } and for all > 1, M ( ) denotes the subset of machines of M ( -1) of size m

2 -1
with at least ( -1) m 2 -1 allocated tasks in total after step -1 (we prove below that such a set exists). Finally, for each and for all T i ∈ T ( ) , we set

M i = M ( ) .
Let us prove by induction that the construction of M ( ) is valid, i.e., that such a subset exists for all > 0. Note that as D is an immediate dispatch algorithm, all tasks of T ( ) are irremediably scheduled at time -1 on some machines of M ( ) . For the construction of M (2) , we start from M (1) = {M 1 , . . . , M m } where m 2 tasks have been allocated on the first step. We select for M (2) the subset of machines where these tasks have been allocated, possibly with additional machines to reach the proper size m 2 . We now assume that M ( ) has been constructed and prove that we can build M ( +1) . By induction, M ( ) has been allocated ( -1) m 2 -1 tasks up to step -1, and m 2 new tasks on step . This makes a total of (2 -1) m 2 tasks. We select for M ( +1) the m 2 machines that are the most loaded in M ( ) . We consider two cases:

(i) Each of the selected machines has at least tasks. Then in total, we have at least m 2 tasks, as requested. (ii) There exists a selected machine with at most -1 tasks.

This means that all non-selected machines have at most -1 tasks (otherwise, we would have selected one of them instead), for a total work (on the m 2 non-selected machines) of at most ( -1) m 2 tasks. Thus, on selected machines, the number of tasks is at least

(2 -1) m 2 -( -1) m 2 = m 2 .
At step log 2 (m), M (log 2 (m)) is reduced to two machines, with at least 2(log 2 (m)-1) allocated tasks, where a single task is scheduled at time log 2 (m)-1. This leaves one machine with at least log 2 (m) tasks, where we finally allocate the last task at time log 2 (m), leading to a maximum flow of (log 2 (m) + 1)p -log 2 (m). Note that

log 2 (m) + 1 = log 2 (2 log 2 (m ) ) + 1 = log 2 (m ) + 1 = log 2 (m ) + 1 .
The optimal strategy consists in scheduling each set T ( ) on the machines of M ( ) \ M ( +1) , for a max-flow of p. Thus, as p → ∞, we have a competitive ratio of log 2 (m ) + 1 .

The previous result may be adapted for processing sets that do not present any particular structure, but have all the same size k. The proof is an adaptation of the previous one and is available in the companion research report [START_REF] Canon | Bounding the Flow Time in Online Scheduling with Structured Processing Sets (extended version)[END_REF].

Theorem 2. The competitive ratio of any immediate dispatch algorithm is at least log k (m) for the problem

P |online-r i , p i = p, M i , |M i | = k|F max .
When considering online algorithms that do not have the Immediate Dispatch property (and thus may allocate tasks only when machines are available for computation), we can still prove a similar lower bound on the competitive ratio, as long as the processing sets are nested. The proof is an adaptation of Anand et al. [START_REF] Anand | Minimizing maximum (weighted) flow-time on related and unrelated machines[END_REF], which did not consider any structure. Theorem 3. The competitive ratio of any online algorithm is at least 1 3 log 2 (m) + 2 for the problem P |online-r i , p i = 1, M i (nested)|F max .

Proof: Let us assume that we work on a number of machines m that is a power of 2, i.e., m = 2 log 2 (m ) , where m is the actual number of machines. Let N be an arbitrary online scheduling algorithm. Machines are numbered from 1 to m, and let F be a number such that F ≥ log 2 (m) + 2. We construct the following instance. At time t 0 = 0, we consider the interval of machines of size s 0 and starting from u 0 (that is, {M u0 , M u0+1 , . . . , M u0+s0-1 }), denoted by I(u 0 , s 0 ), where u 0 = 1 and s 0 = m. We submit s 0 unit tasks at time t 0 , with the processing set restriction M i = I(u 0 , s 0 ). Let G 1,0 denote this set of tasks. For each machine M j ∈ I(u 0 , s 0 ), we release one unit task at each time t 0 , t 0 +1, . . . , t 0 +F -1 and feasible only on the machine M j . Let G 2,0 denote this set. Note that at time t 0 + F -1, algorithm N should have completed the tasks of G 1,0 , otherwise the maximum flow time would be greater than log 2 (m) + 2. Now, for all k 0, we set t k = t k-1 + F and s k =

1 2 s k-1 . We choose u k such that u k-1 ≤ u k ≤ u k-1 + s k-1 - s k = u k-1 + s k (in other words, I(u k , s k ) is a subinterval of I(u k-1 , s k-1 )
), and such that |G 0,k | is maximized, where G 0,k ⊂ G 2,k-1 is the set of tasks that are submitted before t k but not completed at this time, and that can be executed on one machine only in the interval I(u k , s k ). Then we submit task sets G 1,k and G 2,k as previously: G 1,k is made of s k tasks with processing set I(u k , s k ) released at time t k , and G 2,k contains F tasks for each machine M j ∈ I(u k , s k ) submitted at times t k , t k + 1, . . . , t k + F -1 and that must be processed on M j .

We prove the following statements by induction: for all k ≥ 0, (i) s k = m/2 k and (ii) there are at least ks k uncompleted tasks on

I(u k , s k ) at time t k before sending G 1,k and G 2,k , i.e., |G 0,k | ≥ ks k .
For the base case (k = 0), we have s 0 = m/2 0 = m, and G 0,k = ∅, so there is no completed task on I(1, m) at time 0 before sending G 1,0 and G 2,0 . Now assume that s k = m/2 k is true at a certain step k. At step k + 1, we have s k+1 = 1 2 s k by definition, so

s k+1 = 1 2 (m/2 k ) = m/2 k+1
, which proves the statement (i).

Suppose that there are at least ks k uncompleted tasks on I(u k , s k ) at time t k , i.e., |G 0,k | ≥ ks k . Then we send G 1,k and G 2,k , which means that there are at least 1 2 s k and by contradiction, assume that no such subinterval contains (k+1) 1 2 s k uncompleted tasks, i.e., there are at most (k + 1) 1 2 s k -1 uncompleted tasks on each of these subintervals. Thus, there are at most 2 ((k + 1) 1 2 s k -1) = (k + 1)s k -2 uncompleted tasks on I(u k , s k ), which contradicts the fact that I(u k , s k ) holds at least (k+1)s k uncompleted tasks. Then, the chosen subinterval I(u k+1 , s k+1 ) contains at least (k + 1) 1 2 s k = (k + 1)s k+1 uncompleted tasks at time t k+1 before sending G 1,k+1 and G 2,k+1 (that is, |G 0,k+1 | ≥ (k + 1)s k+1 ), which proves the statement (ii).

ks k + s k + F s k -F s k = (k + 1)s k uncompleted tasks on I(u k , s k ) at time t k+1 = t k + F . Now we choose the subinterval I(u k+1 , s k+1 ) ⊂ I(u k , s k ) maximizing |G 0,k+1 | at time t k+1 . Let us divide I(u k , s k ) into 2 disjoint subintervals of size
We stop when we reach the step k such that s k = 1. This means that m/2 k = 1, i.e., k = log 2 (m). Therefore, there remains at least ks k = log 2 (m) uncompleted tasks on an interval of size 1 at time t k , plus 1 task of G 1,k and 1 task of G 2,k , which gives a maximum flow time of at least log 2 (m)+2. Thus, on all m machines, we have a maximum flow of

log 2 (m) + 2 = log 2 (2 log 2 (m ) ) + 2 = log 2 (m ) + 2 = log 2 (m ) + 2 .
The optimal strategy consists, at each step 0 ≤ k < log 2 (m), in executing all tasks of G 1,k on the subinterval I(u k , s k ) \ I(u k+1 , s k+1 ), for a max-flow of 3: tasks of G 1,k are scheduled first (with flow 2), followed by tasks of G 2,k , which have a flow at most 3.

The case of disjoint processing sets is particular: we may apply a competitive algorithm independently on each set, which leads to an algorithm with adapted competitive ratio (see detailed proof in the companion research report [START_REF] Canon | Bounding the Flow Time in Online Scheduling with Structured Processing Sets (extended version)[END_REF]). Theorem 4. From any f (m)-competitive algorithm for the problem P |online-r i |F max , we can design an adapted algorithm with a competitive ratio of max i {f (|M i |)} for the disjoint case (P |online-r i , M i (disjoint)|F max ).

Proof: Let I be an arbitrary instance of the problem P |online-r i , M i (disjoint)|F max , and let N be an f (m)competitive algorithm for P |online-r i |F max . By definition of the disjoint processing set restriction, we have M i ∩ M j = ∅ or M i = M j for all tasks T i , T j (with i = j) of the instance I. Let M denote the set of all subsets M i .

Then, for all M u ∈ M, we construct the set of tasks

T u = {T i ∈ T s.t. M i = M u }. As M u ∩ M v = ∅ for all M u , M v ∈ M such that u = v, we clearly have T u ∩ T v = ∅. Moreover, Mu∈M T u = T.
Hence, for all M u ∈ M, T u and M u can clearly constitute an instance I u of the problem P |online-r i |F max . We design an online algorithm N for the original problem by applying N in parallel to each instance I u .

By definition of the competitive ratio of N , we have

F N max (I u ) ≤ f (|M u |)F OPT max (I u )
, where OPT is an optimal offline strategy. As I u is a subproblem of I, we also have

F OPT max (I u ) ≤ F OPT max (I) for all I u ,
where OPT is an optimal offline strategy built by applying OPT in parallel on each instance I u . Then,

F N max (I u ) ≤ f (|M u |)F OPT max (I), and
F N max (I) = max u F N max (I u ) ≤ max u {f (|M u |)} F OPT max (I).
This result has an important corollary for EFT on disjoint processing sets.

Corollary 1. EFT is (3 -2/ max |M i |)-competitive for the disjoint case and (3 -2/k)-competitive when |M i | = k for all M i .
We now move to the study of processing sets that are intervals of fixed size, which we outlined in the introduction as being representative of the replication scheme used in key-value stores. We show that the competitive ratio of any algorithm (even without the Immediate Dispatch property) is not smaller than 2.

Theorem 5. The competitive ratio of any online algorithm is at least 2 for the fixed-size interval problem P |online-r i , p i = p, M i (interval), |M i | = k|F max .

The proof, detailed in the report [START_REF] Canon | Bounding the Flow Time in Online Scheduling with Structured Processing Sets (extended version)[END_REF], consists in a simple adversary argument: we first submit a task with processing set {M 2 , M 3 }. When the scheduler has started this task on some machine M u , we submit two tasks whose processing set is an interval of size 2 containing

M u : either {M 1 , M 2 } or {M 3 , M 4 }.
The lower bound on the competitive ratio can be largely increased when considering immediate dispatch algorithms, and in particular EFT, as defined in Algorithm 2 in Section IV. Note that among immediate dispatch algorithms, EFT is a very reasonable candidate: when a new task is submitted, it is allocated to the machine that will finish it the earliest. Without processing set restrictions, this is known to produce a very good load balancing, as well as good performance for the max-flow [START_REF] Bender | Flow and stretch metrics for scheduling continuous job streams[END_REF] (we detail this proof in the report [START_REF] Canon | Bounding the Flow Time in Online Scheduling with Structured Processing Sets (extended version)[END_REF]).

It turns out that this is not the case when adding processing interval restrictions. We prove in Theorems 6, 7 and 8 that the competitive ratio of EFT is larger than m -k + 1 in a variety of settings.

To exhibit this result, we need to focus on a specific tie-break function. We start by studying the MIN tie-break function: in the set U i of candidate machines that may finish task T i at the earliest, we choose the machine with smallest index. The obtained algorithm is called EFT-MIN and its competitive ratio is bounded in Theorem 6. Theorem 6. The competitive ratio of EFT-MIN is at least m-k+1 for the fixed-size interval problem P |online-r i ,

p i = 1, M i (interval), |M i | = k|F max , where 1 < k < m.
We give here a summary of the long and technical proof of this result, available in the companion research report [START_REF] Canon | Bounding the Flow Time in Online Scheduling with Structured Processing Sets (extended version)[END_REF].

For ease of reading, we say that a given task T i is of type λ if its processing interval restriction starts on machine M λ , i.e., M i = {M λ , . . . , M λ+k-1 }. Let us build the following adversary instance (we illustrate an EFT-MIN schedule of this instance in Figure 1). At each time t, m tasks are submitted: 1); (ii) for m -k < i ≤ m, task T i is of type 1 (red task in Figure 1). This adversary relies on the key observation that EFT-MIN favors the machine with smallest index when several machines are available at the same time. On the proposed instance, EFT-MIN will rarely use machines with high indices, whereas machine m is able to process the first task only in each round. The proof consists in showing that machines with smaller indices will be overloaded, and their delay propagates up to the desired flow time, while an optimal schedule would allocate each task on the very last machine of its processing set, reaching a flow of 1.

(i) for 1 ≤ i ≤ m -k, task T i is of type m -k -i + 2 (blue task in Figure
A key notion in this proof is the concept of profile w, defined as follows: w t (j) = max (0, C j,mt -t) is the work allocated on machine M j and waiting to be processed, just before the adversary releases the m next tasks at time t. We show that EFT-MIN converges to a stable schedule profile w τ such that for all j,

w τ (j) = min(m -j, m -k).
The proof is divided in two steps, summarized below:

Step 1. We prove that while we have not reached or exceeded the stable profile w τ , the total delay is strictly increasing with time (i.e., we are getting closer to w τ ).

Step 2. We prove that, at each round, either we have not yet reached the stable profile, or some machine has a delay larger than m -k. These two intermediate results allow us to conclude that some machine eventually reaches a max-flow of m -k + 1: from

Step 2, we know that at each round, either we have already exceeded the stable profile w τ , or we have not yet reached it. In this case, Step 1 tells us that we will get closer to the stable profile until we reach or exceed it. In both cases, we conclude that some machine has a max-flow of m -k + 1.

The previous bound on the competitive ratio of EFT-MIN can be extended to the case where EFT uses a random tiebreak function RAND, and we call this algorithm EFT-RAND. The only condition for Theorem 7 to hold is that among a set of candidate machines, the random tie-break function chooses each machine with positive probability, i.e., no machine is systematically discarded when it is a possible candidate. The proof is availabe in the report [START_REF] Canon | Bounding the Flow Time in Online Scheduling with Structured Processing Sets (extended version)[END_REF].

Theorem 7. The competitive ratio of EFT-RAND is at least m -k + 1 (almost surely) for the fixed-size interval problem P |online-r i , p i = 1, M i (interval), |M i | = k|F max , where 1 < k < m.
In other words, there exists an instance for which we have

P F max ≥ (m -k + 1)F OPT max = 1.
Finally, this result holds for any tie-break function provided that tasks are not anymore of unitary duration (see proof in the research report [START_REF] Canon | Bounding the Flow Time in Online Scheduling with Structured Processing Sets (extended version)[END_REF]).

Theorem 8. The competitive ratio of EFT (with any tie-break policy) is at least m -k + 1 for the fixed-size interval problem P |online-r i , M i (interval), |M i | = k|F max .

VI. EXPERIMENTAL RESULTS

In this section, we evaluate the relative impact of structured processing set restrictions on the performance of simple scheduling heuristics. We focus on both interval processing sets, because they are used in actual systems [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF]- [START_REF] Sumbaly | Serving large-scale batch computed data with project voldemort[END_REF], and disjoint processing sets, because it is the restrictions for which we have the best, and only, approximation ratio (Theorem 4). Moreover, the performance of actual systems are affected by the popularity of requests, which is not uniform, i.e., certain tasks restricted to the same processing set appear more frequently than others. We begin by explaining our model of popularity before developing the process we used to evaluate the theoretical maximum load permitted by data item replication. Finally, we perform simulations to provide an experimental perspective to the bounds derived in the previous section. All the related code, data and analysis are available online 1 .

1 https://doi.org/10.6084/m9.figshare.19123139.v1

A. Model of Popularity

Let us consider a cluster of m machines, where tasks have a unit processing time and are released according to a Poisson process with parameter λ (in other words, λ tasks are released in average at each time unit). λ/m measures the average load on the whole cluster; thus, when λ = m, the cluster is loaded at 100%.

For now, suppose that each task can be processed by only one specific machine, i.e., we have |M i | = 1 for all task T i . This corresponds to what happens in key-value stores when data items are not replicated: each task T i carries a key, which is uniquely associated to a data item in the system, and this data item is held by only one machine of the cluster. Therefore, T i has no choice but to be sent and processed on this specific machine.

In practice, some data items are requested more frequently than others during the service lifetime; depending on the data partitioning and popularity bias on requested keys, some machines will potentially have to process more tasks than others, leading to a biased distribution on machine popularity. Let E j be the event in which a task must be processed by machine M j (because it requests a key held by M j ), which occurs with probability P (E j ). Thus, λP (E j ) is the average number of tasks sent on M j at each time unit, and measures the load of M j . Note that because of the non-uniform popularity bias P (E j ), the load of a given machine can be greater than 100% (even if the average cluster load is below 100%). In this case, the machine completely saturates as there is no replication.

Let us consider that the machine popularity follows a Zipf distribution, which has been advocated to model popularity distributions [START_REF] Feitelson | Workload modeling for computer systems performance evaluation[END_REF]. We have P (E j ) = 1 j s Hm,s , where s ≥ 0 is the shape parameter of the distribution and H m,s is the m-th generalized harmonic number of order s. We use s to control the popularity bias: the larger s, the more the popularity heterogeneity increases. In the following, we focus on three specific situations. When s = 0, the distribution degenerates to the uniform distribution, i.e., no machine is more popular than another (we call this case the Uniform case). When s > 0, the Zipf distribution has the particularity to generate a monotonically decreasing load on machines M 1 , . . . , M m . This corresponds to a worst case, as the first machines concentrate most of the workload (Worst-case). Finally, we randomly permute P (E j ) to match with more realistic settings (Shuffled case). As realistic bias strongly depends on the dataset and system usage, each permutation is chosen uniformly as we assume no prior knowledge. Figure 2 shows an example of load distribution for each case.

B. Analysis of Theoretical Maximum Load

We want to find the theoretical maximum cluster load (that is, finding the maximum value of λ such that the load on each machine is below 100%) one can achieve when data items are replicated across the cluster. Up to now, as we did not consider replication yet, we supposed that each task could only be processed by a single machine (the one holding its requested key). In this case, we clearly have λ ≤ 1/ max j P (E j ).

Let us give more choices to each task by adding more machines to the processing sets M i . This can be seen as replicating data items. Our goal is to study how extending M i under a popularity bias affects performance metrics such as the maximum flow time or the maximum cluster load, and how structures in processing sets impact them.

For each task T i , we build a new set M i from M i by defining a replication strategy; in other words, starting from a set with a single machine M i = {M u }, we replicate the keys held by M u on all machines of M i . We focus on strategies that consist in adding k -1 machines (with 1 ≤ k ≤ m) to the set, such that M i constitutes an interval of size k, i.e., M i = I k (u). We describe two manners to build I k (u) from M u . Figure 3 illustrates these constructions.

Overlapping intervals. There are m distinct overlapping replication intervals of size k, arranged as a ring:

I k (u) = {M j s.t. j = (j -1) mod m + 1 for all u ≤ j ≤ u + k -1}.
This constitutes the basic replication strategy of key-value stores: machines are arranged as a ring, and data items held by a given machine are replicated on the successors of this machine [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF], [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF]. We have seen in Theorems 6, 7 8 that EFT does not always provide a good competitive ratio when minimizing maximum flow time with this structure. Mi (no replication)

M i (disjoint) M i (overlapping)
Figure 3: Example of replication strategies in overlapping and disjoint settings, with k = 3. For example, suppose that a task T i is feasible on M 3 only (M i = {M 3 }). Then, in overlapping setting (resp. disjoint setting), the new processing set restriction of

T i is M i = {M 3 , M 4 , M 5 } (resp. M i = {M 1 , M 2 , M 3 }).
Disjoint intervals. We divide the cluster into m k disjoint replication intervals of size k:

I k (u) = {M j s.t. u + 1 ≤ j ≤ min(m, u + k)}, where u = k u-1 k
. This corresponds to the situation seen in Theorem 4 and related corollaries. EFT guarantees a good competitive ratio when minimizing maximum flow time with this structure.

After replication, all tasks that could only run on a given machine M j can now be processed by any machine of I k (j). To quantify the gain on maximum cluster load permitted by a given replication strategy, we solve the following optimization problem modeled as a Linear Program:

maximize λ (3a) subject to ∀j, i a ij = λP (E j ), (3b) ∀i
, j a ij ≤ 1, (3c) ∀i
, j s.t. M i / ∈ I k (j), a ij = 0, (3d) ∀i, j, a ij ≥ 0, (3e) λ ≥ 0. (3f)
a ij denotes the average amount of work (in tasks per time unit) that is eventually processed by machine M i and that corresponds to tasks originally restricted to machine M j . We consider the following constraints:

• The total work corresponding to tasks originally restricted on M j is exactly equal to the initial work of M j (Equation (3b)). • The average work eventually processed on M i does not exceed 1 (Equation (3c)). • We can transfer work from M j to M i if and only if M i belongs to the interval of size k generated from M j according to the considered replication strategy, i.e., all tasks that could originally run exclusively on M j can now also run on M i (Equation (3d)).

C. Experimental Evaluation of Theoretical Maximum Load

In the following experiments, we set the cluster size m to 15, which is a common setup when conducting experiments with scheduling in real key-value store systems [START_REF] Jaiman | Héron: Taming tail latencies in key-value stores under heterogeneous workloads[END_REF], [START_REF] Suresh | C3: cutting tail latency in cloud data stores via adaptive replica selection[END_REF]. Figure 4a shows the result of our Linear Program (Equations ( 3)) as a function of bias s and interval size k, for both previously described replication strategies, in the Shuffled case (median over 100 different permutations).

At first glance, it seems that the disjoint strategy is less efficient than the overlapping strategy to cope with high cluster load when non-uniform popularity biases are introduced. For example, for s = 1 and k = 5, Figure 4a indicates that the cluster can theoretically tolerate a maximum load of 100% when intervals overlap, whereas the disjoint strategy allows reaching a maximum load of 70%.

The overlapping strategy superiority is clearly confirmed by Figure 4b, which shows the gain on the maximum load permitted by overlapping replication intervals over the disjoint strategy. The overlapping strategy allows the cluster to handle loads that are up to 50% higher than the disjoint strategy (e.g., for s = 1.25 and k = 6), and we can observe a gain up to 35% for common situations in key-value stores, when 0 < s ≤ 1.5 (moderate popularity bias) and k = 3 (standard replication factor in most implementations). Note that the popularity bias has obviously no effect when data are fully replicated (k = m), and that replication strategies exhibit no difference on the tolerable load when no bias is introduced (s = 0).

D. Simulations with Popularity Bias

Now we simulate EFT scheduling on m = 15 machines with a popularity bias, on 10 000 generated unit tasks, which is sufficient to reach a steady state. Figure 5 illustrates the impact of both replication strategies on maximum flow time in the EFT-MIN scheduler and its counterpart EFT-MAX (which selects the candidate machine with highest index). We consider the three cases of popularity bias (in Worst-case and Shuffled case, we set s = 1). We repeat the experiment 10 times, and we take the median among max-flow values. We set k = 3 to match with a realistic key-value store system.

In the Uniform case, no difference is visible between EFT-MIN and EFT-MAX; however, overlapping replication intervals give better results than the disjoint strategy (e.g., for an average cluster load of 90%, EFT exhibits a maxflow of 5 when intervals overlap, whereas it gives a maxflow of 10 with disjoint intervals). When randomly dispatched popularity biases are introduced (Shuffled case), we see the relative gain of the overlapping strategy increasing. This is even more obvious when we consider the Worst-case. We also see EFT-MAX becoming more efficient than EFT-MIN for the overlapping strategy, which is consistent with the situation in Theorem 6: when breaking a tie, EFT-MIN will select the most popular machine, whereas EFT-MAX does the opposite (as we are in a worst-case, popularity biases are sorted in decreasing order), leading to a smaller max-flow. However, the gain permitted by the scheduling heuristic is rather marginal compared to the gain allowed by a carefully chosen replication structure.

The replication strategy where intervals overlap, commonly used in key-value stores, exhibits better results than the disjoint strategy when popularity biases are introduced, even if the max-flow of EFT in disjoint setting is bounded (Theorem 4). However, there is no efficient worst-case guarantee for the overlapping strategy, as seen in Theorem 6. The question of whether there exists a replication strategy giving both good practical results and theoretical guarantees on EFT scheduling remains open.

VII. CONCLUSION

The high throughput and scalability needs of key-value stores require immediate dispatch algorithms in which requests are allocated to servers as soon as they arrive (such as EFT). In the absence of processing set restrictions, EFT benefits from favorable competitive guarantee for the maximum flow time. However, storage constraints usually prevent replicating all data on all servers; this is modeled by introducing restrictions on the task processing sets. We provide bounds on the competitive ratio for several structured processing sets.

In particular, we show that the competitive ratio of EFT goes from (3 -2/m) to m -k + 1 for interval processing sets, which are the most commonly used in key-value stores. However, despite the poor theoretical guarantee for EFT, we show experimentally that interval processing sets allow a load up to 50% larger than disjoint processing sets. Future directions include devising a structured processing set, or replication strategy, that would provide efficient performance on average and in the worst case. Moreover, the current bound on the competitive ratio of EFT with interval processing sets could be extended to other immediate dispatch algorithms.

Figure 1 :

 1 Figure 1: An EFT-MIN schedule of the adversary from time t = 0 to t = 3, for m = 6 and k = 3. Colored tasks are released in-order at each time t.

Figure 2 :

 2 Figure 2: Example of load distribution on a cluster of m = 6 machines, with λ = m, for each case.

M 1 M 2 M 3 M 4 M 5

 12345

  Ratio between the max-load of each strategy

Figure 4 :

 4 Figure 4: Maximized load for both overlapping and disjoint strategies, for each 0 ≤ s ≤ 5 (by steps of 0.25) and 1 ≤ k ≤ m, in the Shuffled case. In Figure (a), we show the median value obtained from 100 different permutations of weights P (E j ). In Figure (b), we show the ratio between the median max-loads of both replication strategies.

Figure 5 :

 5 Figure5: Maximum flow time given by both heuristics EFT-MIN and EFT-MAX as a function of the average load when k = 3, for both the overlapping (solid lines) and disjoint (dashed lines) strategies. Each facet corresponds to a distinct case (for the Worst-case and Shuffled case, we set s = 1). Finally, each vertical red line shows the theoretical maximum load value given by the LP (3) in the corresponding case.

Table I :

 I Existing results on max-flow optimization.

	Env. Preemption	Algorithm	Type	Approx./Competitive Ratio Ref.
	P Non-preemptive FIFO	Online	3 -2/m	[11]
		any	Online	≥ 2 -1/m	[19]
	Preemptive	FIFO	Online	3 -2/m	[12]
		Ambühl et al. Online	2 -1/m	[19]
		any	Online	≥ 2 -1/m	[19]
	P |Mi Non-preemptive any	Online	≥ Ω(m)	[13]
	Q Non-preemptive DOUBLE-FIT	Online	13.5	[20]
		SLOW-FIT	Online	≥ Ω(m)	[20]
		GREEDY	Online	≥ Ω(log m)	[20]
	R Non-preemptive Bansal et al.	Offline	O(log n)	[22]
		Bansal	Offline, PTAS	1 + ε in n O(m/ε)	[21]
		Mastrolilli	Offline, FPTAS 1 + ε in O(nm(n 2 /ε) m )	[12]
	Preemptive	Legrand et al. Offline	Optimal	[18]

Table II :

 II Competitive ratio guarantees for the problem P |online-r i , M i |F max with various processing set restrictions and depending on the type of algorithm.

	Processing Set Structure Algorithm Type	Competitive Ratio	Ref.
	inclusive	Immediate Dispatch ≥ log 2 (m) + 1	Th. 1
	|Mi| = k nested disjoint, |Mi| = k	Immediate Dispatch ≥ log k (m) Online ≥ 1 3 log 2 (m) + 2 EFT 3 -2/k	Th. 2 Th. 3 Cor. 1
	interval, |Mi| = k	Online	≥ 2	Th. 5
		EFT	≥ m -k + 1	Th. 6, 7, 8