Alexandra Halchin
email: alexandra.halchin@ratp.fr

Abderrahmane Feliachi
email: abderrahmane.feliachi@ratp.fr

Neeraj Kumar Singh
email: nsingh@enseeiht.fr

Yamine Ait-Ameur
email: yamine@enseeiht.fr

Julien Ordioni
email: julien.ordioni@ratp.fr

B-PERFect

Keywords: PERF, B method, HLL, Safety assessment

An independent safety assessment of railway software systems is performed by RATP (Régie Autonome des Transports Parisiens) for all safety-critical systems before their deployment in its network. Whenever possible, this activity is performed using the PERF approach (Proof Executed over a Retro-engineered Formal model). PERF is a methodology which handles formal verification of already developed software. This approach is applied to a variety of software systems, developed using languages such as SCADE, Ada or C. It provides an alternative verification that can be applied for the independent safety assessment of critical systems used by RATP. In this paper, we propose the B-PERFect method to generalize the application of the PERF approach for critical systems which are based on the B method. In particular, this paper focuses on transformation strategy from B language to the pivot language of PERF: HLL. HLL is a synchronous data-flow language equipped with formal verification techniques. The differences between B and HLL are pointed out and the translation process is presented in this regard.

Introduction

For several years, RATP has been involved in the application of formal verification techniques to assess the safety level of railway systems. RATP pays a lot of attention to the safety of its deployed systems. This safety regime is implemented through a mandatory internal independent safety assessment of all safety-critical railway systems. It gave birth to a formal verification methodology called PERF [START_REF] Benaissa | The PERF approach for formal verification[END_REF]. It is an independent assessment that helps to double-check the safety of the developed software in addition to the verification performed by the software supplier.

PERF was designed to be applicable to any software system independently of their development processes and languages. By taking the source code of the developed software as the target of the verification, it ensures a complete language-agnostic and non-interference with the software supplier which drastically reduces any possible bias. It also allows for applying formal verification techniques to the safety assessment activity, which is not always achieved by the software supplier in its safety verification.

In order to support the different solutions of all RATP's suppliers, a number of translators were developed and integrated into PERF. These translators give a formal representation of the targeted source code in the PERF's pivot language HLL, a synchronous data-flow language, similar to Lustre, allowing to express, in the same formalism, the system behavior as well as safety requirements. The role of the translators is to give a semantics-preserving formalization of the software to be analyzed in HLL. Currently, translators for SCADE, Ada and C languages are integrated in the PERF tool chain.

In a similar vein, the B-PERFect project was initiated in order to investigate the applicability of PERF on software systems developed using the B method [START_REF] Abrial | The B-book: Assigning Programs to Meanings[END_REF]. Software systems developed using B are valid by construction with respect to safety requirements. The idea behind the B-PERFect project is not to replace the formal verification process of B but to propose a verification alternative to be used for the internal independent safety assessment. This will not question the proof process of B. However, it may eventually reveal any error in the initial formalization of safety requirements.

This paper describes a new approach for software safety verification and gives an overview of a translation process from B0 (a subset of B language close to imperative programs) to HLL, the pivot language of PERF. Moreover, it shows the general architecture of the code generation process, including technical challenges related to tool development. Section 2 introduces the context of this work and motivates the proposed approach. The required background related to the B method and HLL is described in Sect. 3. Section 4 presents the general translation strategy. In Sect. 5, we present some related works. Finally, Sect. 6 concludes our work along with future directions.

Context

RATP operates one of the most complex urban multi-modal public transportation networks in the world. In the Parisian region, its network includes 16 metro lines, 2 RER (intercity trains) lines, 7 tramway lines and more than 300 bus lines; transporting not less than 10 Million passengers each day. RATP has built, throughout the years, a rich expertise not only in operating transportation networks, but also in the engineering of railway transportation systems. This expertise made RATP one of the world pioneers in metro automation and one of the experts in automating existing lines.

The growing demand of transportation capacity coupled with continuous advances in computer technology accelerates the obsolescence of existing systems. These factors, added to the improvement and modernization desires, have led RATP to upgrade its network by adopting integrated and upgradeable solutions, through partially or fully automated transportation systems. The coexistence of these different systems brings additional difficulties, particularly related to the safety assessment of the railway systems which depend on the automation level of these systems. One major concern of RATP is to ensure the safety of any deployed system on the network during all the project phases.

In order to guarantee a better and more extensive safety analysis, RATP's engineering department (ING) relies, whenever possible, on rigorous verification methodologies based on formal methods. One of the first application of formal methods in an RATP project goes back to the late eighties were the Z method revealed a number of safety critical bugs for the SACEM system (RER A) which already passed the tests campaign. This successful application of formal methods led RATP to require their use by all safety-critical software systems suppliers. As a consequence, the development of the first driverless metro line in Paris (Line 14) in 1998 was realized using the B formal method. The safety of the system was proven by the construction which helped to remove all testing phases while guaranteeing a complete coverage.

The use of formal methods cannot be required by RATP anymore because, according to the regulations, this would promote some suppliers over the others. However, the use of a formal development method is still highly recommended by RATP to all its suppliers. In addition, an independent safety assessment is performed internally by RATP. RATP's opinion is that using formal methods independently of the supplier reveals usually more bugs than the simple verification of the supplier's testing campaign. Since the 2000s, RATP is working with different suppliers, using different development methods and languages. This heterogeneity requires RATP to master all its supplier methods and languages, which introduced a skill management difficulty with regards to the assessment process. The solution was to use a unified verification approach, pointed as an "ex post facto" proof, for the different projects which allows for the application of formal verification independently of the supplier's development language or method.

This situation was the starting point of the PERF (Proof Executed over a Retro engineered Formal model) methodology and its supporting team. The technique has been successfully used on Thales, Ansaldo and Alstom (ex-Areva TA) products, in charge of the Computer Based Interlocking Lines 1, 4, 8 & 12, the wayside and the on-board equipment of CBTC (Communication Based Train Control) Line 3, 5, 9 & 13 projects. PERF is now applied in every project, whenever possible, meaning essentially when the source language of the software is supported. This is currently the case for projects developed using C, Ada or Scade languages. The general workflow of the PERF methodology is given in Fig. 1. The real strength of PERF is its supporting tool chain, composed of translators, counter-example analyzers and SAT-based proof engines [START_REF] Prasad | A survey of recent advances in SAT-based formal verification[END_REF].

A number of projects keep using the B method for the development of safetycritical systems. In this case, the independent assessment is a bit more complicated and might be intrusive in some situations. Even though the formal verification performed by the B proof engines can be trusted, the validation of the safety properties can only be performed by cross-reading which, besides being a tedious task, may not be very effective. The idea of the B-PERFect project is to provide an independent alternative for the verification of the safety properties on systems developed using the B method. The B code is transformed in a HLL formal execution model. To this model, the safety requirements targeted by the verification are added and the entire model is passed to the prover. By doing so, one can prove initial system properties which are expressed in natural language. The idea behind this is not to prove again the existent B code but to check if safety properties were modeled correctly in the initial code. The PERF approach makes this verification non intrusive and also supports the verification of the code generation process if needed. It will also help, in the context of heterogeneous systems, to apply a unified verification to all system components.

3 Background B Method. The B method is a formal method based on first-order logic and set theory. It can handle a complete critical-software development process from specification to code [START_REF] Abrial | The B-book: Assigning Programs to Meanings[END_REF]. The B development process is layered. Each layer corresponds to an abstraction level and the refinement provides the relation between layers. This method has proven its feasibility for large-scale industrial applications, particularly in railway domain [START_REF] Behm | Météor: a successful application of B in a large project[END_REF]. Models are represented in B as machines. A machine contains state variables, instances of other machines, a state invariant, an initialization clause and operations acting on the defined variables. Generally, B project models represent a state transition system in which the initialization clause sets the initial values of variables and the operation clause specifies how variables are modified from one state to another. The invariant describes the safety properties of the model and is specified using predicate logic. The highest level of abstraction is the specification, a representation of functional requirements and the lowest one corresponds to the implementation where only programming-like constructs are allowed [START_REF][END_REF]. The refinement is the process of transformation from an abstract model into a concrete model specified in a subset of the B language: the B0 language, which can be automatically translated into executable code [5, [START_REF] Méry | Automatic code generation from EVENT-B models[END_REF][START_REF] Storey | A strategy for the production of verifiable code using the B Method[END_REF][START_REF] Tatibouët | Java card code generation from B specifications[END_REF]. Last level of refinement called implementation must be deterministic. For instance, parallel substitutions are not allowed, the type of variables must be scalar and modules are written in a procedural style. The advantage of using the B method is that it supports a correct by construction development approach which implies that each step of the development process can be proved if the target is a zero bug development.

B Development Example.

As an example, the below implementation describes a simplified B machine which reads the input values from an external machine and computes the minimum of two variables. This example contains two B machines: Utils i defines auxiliary operations and Main i defines the main program. The Main i machine represents an entry point of the execution. Main is an operation to select an order of the execution using defined operations in the imported machine. In the example, firstly, the operation computeSum is called that changes the state of the machine Utils i as a side effect. The variable xx is initialized using the output of the operation readVar. This operation returns the value of a variable which is modified when computeSum is called. Finally, the minimum of two variables is computed using the operation minimum. HLL, the Pivot Language of PERF. The PERF approach is built around HLL (High Level Language), a formal declarative and synchronous data flow language in the tradition of LUSTRE [START_REF] Halbwachs | The synchronous data flow programming language LUSTRE[END_REF]. Models are defined by typed streams that can be composed using either temporal or data operators. Temporal operators can be used to describe clock-dependent expressions. The data operators, such as arithmetic, logical and array operators, are used to manipulate streams values. The declarative nature of the language makes it suitable for the definition of formal models as well as safety properties.

An HLL model is described by a number of sections containing type definitions, constant definitions, stream declarations and definitions, proof obligations, constraints and namespaces definitions. Streams can have integer or values and they are interpreted in the mathematical sense, without any notion of side effects. The notion of sequentiality is absent, which means that the order of the items does not affect the meaning of the HLL model. A HLL project is organized in namespaces sections. Streams are declared in declarations blocks with type checking information, and their values are given in the definitions blocks. The proof obligations block contains a set of properties related to streams for verification purpose. Constraints expressions are used to reduce the domain definition of unbound input streams.

HLL Development Example. This section describes the HLL model that would result from translating the B example given above. The produced HLL model contains two namespaces, one corresponding to the translation of the Main i machine and another for the translation of the imported machine Utils i. For each B operation, a corresponding HLL namespace section is created, such as "Main" which contains the translation of the B operation Main. 3 int "xx"; int "yy"; int "rr"; int "xx<0>"; int "yy<0>";int "rr <0>"; 4 Definitions: "xx<0>" := 0; "yy<0>" := 0; "rr<0>" := 0; 5 "xx" := "Main"::"xx<1>"; // B: xx <--readVar; 6 "yy" := "Main"::"yy<0>"; 7 "rr" := "Main"::"rr<1>"; // B: rr <--minimum(xx,yy) 8 Namespaces: "Main"{ // B: Main operation 9 Declarations: int "xx<0>"; int "yy<0>"; int "rr<0>"; 10 Definitions: 11 "xx<0>" := "Main_i"::"xx<0>"; // Maps the initial values of variables 12 "yy<0>" := "Main_i"::"yy<0>"; 13 "rr<0>" := "Main_i"::"rr<0>"; 14 "xx<1>" := "Utils_i<0>"::"readVar<0>"::"rr"; // Operation call 15 "rr<1>" := "Utils_i<0>"::"minimum<0>"::"rr"; // Operation call 16 }}

Listing 3. HLL Translation of Main Machine

HLL is an SSA language (Single State Assignment) since, in a model, a stream can be assigned only once. As stated in [START_REF] Cytron | Efficiently computing static single assignment form and the control dependence graph[END_REF], when converting from a programming language to SSA form, assignments of a program variable are replaced with assignments to new versions of the variable. Each B assignment will thus be translated to an HLL assignment with a new version of the modified variable. The value of the original variable is replaced by the value of the last known version of this variable. 23 int "sum<0>"; int "ii<0>"; int "ii<1>"; int "ii<2>"; int "sum"; 24 Definitions: 25 "sum<0>" := "Utils_i<0>"::"sum<0>"; "ii<0>" := 0; 26 // While Loop -iter 0 27 "ii<1>" := "ii<0>" + 1; 28 "sum<1>":= "sum<0>" + "ii<1>"; 29 "ii<2>" := if "ii<0>" < 2 then "ii<1>" else "ii<0>"; 30 "sum<2>" := if "ii<0>" < 2 then "sum<1>" else "sum<0>"; 40 int "aa<0>";int "bb<0>";int "rr";int "rr<0>";int "rr<1>";int"rr <2>"; 41 Definitions: 42 "aa<0>" := "Main_i":":Main"::"xx<1>"; //Mapping of input parameters 43 "bb<0>" := "Main_i"::"Main"::"yy<0>"; 44 "rr<0>" := "bb<0>"; // IF block substitution 45 "rr<1>" := "aa<0>"; // ELSE block substitution 46 "rr<2>" := if "aa<0>" >= "bb<0>" then "rr<0>" else "rr<1>";//IF block 47 "rr" := "rr<2>"; 48 }} Listing 4. HLL Translation of Utils Machine Line 3 defines the variables used for the translation of the machine Main i with their corresponding type. Line 4 and lines 8-16 represent the computation done in blocks INITIALISATION and OPERATIONS of the B machine, respectively. In line 14, the output of the operation readVar is assigned to the local variable "xx<1>". Note that state variables are necessary to memorize the final values of variables after the execution of the operation Main (lines 5-7). As the operation call computeSum, does not modify the state of variables in the machine Main i, its translation is not present in the Main namespace. Lines 21-35 represent the translation of the first call of computeSum.

Our work consists in translating concrete formal models based on B0 language in HLL. We propose a transformation strategy, allowing to obtain an equivalent HLL code which is further used for verification purposes. The goal of this work is to obtain HLL models which are behaviorally equivalent to B modules.

The semantic-preserving translation from B to HLL is not straightforward. The first issue to handle is the semantic mismatch between the two paradigms. Thus, a particular attention has to be given to several notions like variable values evolution and updates or loops behaviors. An example of such problems is illustrated in Listing 1. There, a B machine may have operations with sideeffects, implicitly affecting the state of another B machine. For Main i machine, the changes that occur to the variables in order to compute the value of the sum are transparent and not explicit. If the translation process does not follow the correct sequence of the variable changes, the generated HLL model may be erroneous. This kind of scenarios is very tricky to handle. It leads to incorrect HLL models and may hide problems related to safety. Figure 2 illustrates the general translation process made of three main steps: B parsing, preprocessing and code generation. In this paper, we focus on the code generation phase.

The first step of our approach generates an intermediate tree representation AST (Abstract Syntax Tree) of an input code by analyzing it syntactically and semantically. B0 is close to an imperative programming language and handles deterministic B instructions: concrete data (variables and constants), SEES, USES and IMPORTS clauses, and operation calls. Due to the semantics of the HLL language, the preprocessing step annotates the abstract syntax tree with additional information useful for variables evolution or loop transformation. This annotation defines an environment used and updated on the fly by each application of a translation rule. The last part of the process is the HLL code generation. Below, we give the relevant elements related to the code generation process we have set up. We have limited this description due to space limitation.

General Concepts. At the present time, we are interested in translating the IMPLEMENTATION module, the lowest level of a B project, in HLL. Since HLL proposes constructs to divide models in small units and to avoid naming conflicts, the initial B component structure can be preserved in the translation. Therefore, we propose to model B machines as HLL namespaces because both have a notion of variable scoping and structuring facilities which lead to a certain data encapsulation. Dependent machines obtained from IMPORTS, USES and SEES clauses must also be translated into HLL namespaces.

The language used in B expressions is essentially predicate logic and set theory. A B arithmetic expression is a mathematical formula that can contains constants, variables and operators. The supported arithmetic operators are: +,-,×,÷. A predicate expression is evaluated to be true or false in B0 as branching conditions of if substitutions or in while loops. Except for division, the translation of B expressions and B predicates is straightforward because HLL provides the same quantifiers as B [START_REF] Ge | Correct-by-construction specification to verified code[END_REF].

Sequence. In B0, a sequence represents an action which leads to the next action in a predetermined order. All B variables are translated in HLL variables with equivalent types. The link between B0 variables and HLL variables is very crucial for semantics preservation of the translation. This link is not very obvious. In B, variables may evolve during the execution of operations, whereas, in HLL, they correspond to data streams without memory and having a unique value during a cycle. However, our goal is to maintain memory state consistency between B and HLL representation. The HLL equivalent representation of a B variable xx is "xx<i>" for each occurrence i of this variable in left-hand side of an assignment. A new HLL variable is defined by the concatenation of the B variable name and its state evaluated in the translation context. While applying this renaming process, the following properties must be preserved: (i) all value changes of a variable shall be traced and (ii) generated code shall preserve the semantics of the B language. Therefore, the context in which a variable modification occurs is stored and associated to a variable.

Operations. In B language, the dynamic parts of the components are modeled by substitutions, which allow the modification of the data space of a model. Substitutions are used in INITIALISATION and OPERATIONS clauses of a B machine. The proposed transformation of B0 substitutions is based on the understanding of the semantic differences between HLL and B. The general form of an operation is: out ← op name(in) where in and out can be variables or lists of variables representing the parameters of the operation op name. Each B operation is translated in HLL as follows: inside the namespace associated to the translation of a machine we define a new namespace section which contains the translation of an operation. This namespace will have the same name as the original operation appended to an index, counting the different calls of the latter. Parameter passing is one of the crucial points for the semantics preservation when translating programs [4]. In the B language, parameters are passed by reference when calling operations. HLL does not support functions with non scalar types as it is used in common programming languages. In order to preserve the B semantics when transforming to HLL, the translation of B operation call is realized in two steps by separating the operation body substitutions translation and the parameter mapping translation. Extra assignments are introduced in order to map the effective input parameters to formal input ones in an operation call namespace. This situation is illustrated in Listing 4, lines 42-43 where variables "aa<0>","bb<0>" have the role of formal input parameters of the namespace. The operation output it is transformed in a new assignment as shown in Listing 3, line 15.

If Conditions. Both languages provide IF construction with the difference that in HLL it is an expression where in B language it is a statement. In order to merge the information issued from different control flow branches, the translation is performed in two steps. First, the blocks of instructions of each branch are translated (Listing 4, lines 44-45 ), second, extra conditional HLL assignments are introduced taking into account the condition evaluated initially and the previous substitutions. In the example of minimum operation, this corresponds to line 46 of Listing 4.

While Loops. Unlike the B language, HLL does not support loop structures. Therefore, B loops should be flattened in the HLL model. The general form of a loop construct in B0 is WHILE C DO S INVARIANT I VARIANT V END, where S is a substitution, C is a boolean expression, I is a loop invariant and V is a variant that guarantees the loop termination. In B, while loop is a shorthand for writing the same block of instructions many times. A while loop must end after a finite number of iterations a variant is required. We propose to translate while loop as HLL if expressions repeated as many times as the maximum number of iterations needed to exit the loop. This information is extracted using the VARIANT clause. The substitution S is translated using HLL constructs. The translation of invariant is not explicitly required in the HLL code, but it could be modeled as HLL Proof Obligations or Constraints. In the example presented in Listing 2 the maximum number of iterations of the loop is 2, so the HLL translation process repeats according to it. In Listing 4, lines 26-30 show the translation of the first loop iteration. The fact that variables are expressed in function of condition and their previous value guarantees the correctness of the translation by value propagation even if the number of iterations is an overapproximation.

State of the Art

There are several works [4, [START_REF] Storey | A strategy for the production of verifiable code using the B Method[END_REF][START_REF] Tatibouët | Java card code generation from B specifications[END_REF] focusing on code generation in many programming languages (i.e. C, Ada and Java) from B specifications. In [START_REF] Mammar | From a B formal specification to an executable code: application to the relational database domain[END_REF], the authors present a set of translation rules from B to Java/SQL studied in the database domain. To increase the use of formal methods, a tool B2Jml [6] was developed to produce JML specifications from B models. Bonichon et al. [5] have developed LLVM-based code generator that provides llvm executable code for B specification. Moreover, they have also developed a tool b2llvm to automate the code generation process. Furst et al. [START_REF] Fürst | Code generation for Event-B[END_REF] proposed a code generator to produce C code from Event-B models. In Singh et al. [START_REF] Méry | Automatic code generation from EVENT-B models[END_REF], a tool supported code generator, namely EB2ALL, producing source code in many programming languages from verified Event-B specifications is described. Following similar principles, Ge et al. [START_REF] Ge | Correct-by-construction specification to verified code[END_REF] have proposed an approach for translating Event-B models into HLL models. In fact, the main objective of this work is to produce C code from Event-B specification using an intermediate HLL representation. To our knowledge, the proposed translation approach from Event-B to HLL is not automated yet. Similarly, Petit-Doche et al. [16] reported an a posteriori approach for applying formal methods on the developed software, in which a translation strategy is proposed to transform SCADE code to HLL code. In [START_REF] Kalla | Automated translation of C/C++ models into a synchronous formalism[END_REF], the authors present an approach based on the synchronous language SIGNAL [START_REF]Polychrony tool[END_REF] to validate system designs. SIGNAL formal models are generated from C/C++ programs using an SSA intermediate representation. Moreover, translators from C, ADA to HLL already exist. The used translation strategy is not a direct one. An intermediate imperative language is used as a pivot language. There, the goal is to avoid multiple translation steps and to master the whole translation process. It is important to observe that our approach is in similar vein in order to increase confidence in the generated code and promote the use of formal methods in industrial practices. In our work, we propose a translation strategy to produce HLL code from B specification covering the whole B project. Moreover, our approach also highlights the process of translation from a tool development point of view.

Conclusion

We study the applicability of PERF, an industrial toolset which allows the formal verification of systems independently of their development process, on software developed in B. This paper presents our approach to generate verifiable HLL code from an implementation described as B0 code. We focus on the core concepts to ensure semantics preservation when translating B0 implementations to HLL data-flow language. The semantic differences between the two studied languages are pointed out and a general translation scheme is proposed. We describe a translation process as well as a set of translation principles for the constructs that require a particular attention. Our initial ideas are already under development on a prototype tool for automatic translation. In this perspective, we have investigated the existing B parsers and BCompiler1 , an open source tool that offers complex parsing features for syntactical and semantical analysis.

Our future work consists in providing a formalization of the translation rules which shall cover the whole B components and constructs. The correctness of the translation is not studied in this paper. A possible starting point could be the definition of the semantics of both B and HLL in a unified framework and then check semantics preservation. Another possible extension of this work is to handle higher abstraction levels of the B developments in order to enrich the HLL model with lemmas or hints that might help the proof of properties.

Fig. 1 .

 1 Fig. 1. The PERF verification workflow

1 IMPLEMENTATION 8 END 9 ENDListing 1 . 1 IMPLEMENTATION 13 VARIANTListing 2 .

 18911132 Main_i REFINES Main IMPORTS Utils 2 CONCRETE_VARIABLES xx,yy,rr 3 INVARIANT xx ∈ NAT ∧ yy ∈ NAT ∧ rr ∈ NAT 4 INITIALISATION xx := 0 ; yy := 0 ; rr := 0 xx <--readVar ; rr <--minimum (xx , yy) Main Implementation of B Machine -minimum (aa, bb) = 7 IF aa >= bb THEN rr := bb ELSE rr := aa END ; ii := 0 ; 10 WHILE ii < 2 DO 11 ii := ii + 1 ; sum := sum + ii ; 12 INVARIANT ii ∈ NAT ∧ ii ≤ 2 Utils Implementation of B Machine

17

 17

  31//... Repeat the loop code with new index 32 "sum" := "sum<4>";

Fig. 2 .

 2 Fig. 2. Translation Workflow from B to HLL

https://sourceforge.net/projects/bcomp/.


Mohamed Mehdi Kandi
email: mohamed.kandi@irit.fr

Shaoyi Yin
email: shaoyi.yin@irit.fr

Abdelkader Hameurlain
email: abdelkader.hameurlain@irit.fr

Mohamed Mehdi

Kandi Is

Paul Sabatier

Resource auto-scaling for SQL-like queries in the cloud based on parallel reinforcement learning

Keywords: cloud computing, auto-scaling, resource allocation, parallel reinforcement learning

Cloud computing is a technology that provides on-demand services in which the number of assigned resources can be automatically adjusted. A key challenge is how to choose the right number of resources so that the overall monetary cost is minimised. This problem, known as auto-scaling, was addressed in some existing works but most of them are dedicated to web applications. In these applications, it is assumed that the queries are atomic and each of them uses a single resource for a short period of time. However, this assumption cannot be considered for database applications. A query, in this case, contains many dependent and long tasks so several resources are required. We propose in this work an auto-scaling method based on reinforcement learning. The method is coupled with placement-scheduling. In the experimental section, we show the advantage of coupling the auto-scaling to the placement-scheduling by comparing our work to an existing auto-scaling method.

Introduction

Context

Since it was launched in the 2000s, the cloud computing market continues to evolve. Today's cloud providers offer a variety of information technology services, from basic computing resources to complex applications that aim to meet the different tenant needs. Cloud services are based on a pricing model and Service Level Agreements (SLAs). The pricing model describes how services are billed. SLAs define the performance objectives that should be met by the provider and the measures to be taken in case of non-compliance with the objectives. If requirements are not respected, the provider pays penalties to the tenant.

Among cloud applications, we are interested in those concerning querying databases. Data processing has experienced in recent years the arrival of frameworks based on the storage and processing of partitioned data over a set of machines, mainly Hadoop ecosystem. Extensions that propose a syntax close to the classical SQL language (Hive) have been added to these frameworks in order to make them accessible to users who are accustomed to SQL. This syntax is called SQL-like. A submitted SQL-like query is transformed into many MapReduce jobs [START_REF] Dean | Mapreduce: a flexible data processing tool[END_REF], or a single job consisting of a Directed Acyclic Graph (DAG) [START_REF] Saha | Apache tez: A unifying framework for modeling and building data processing applications[END_REF], then assigned to available resources [START_REF] Kllapi | Schedule optimization for data processing flows on the cloud[END_REF]Vavilapalli et al., 213). Cloud providers have quickly adapted to the new data processing frameworks by offering services like Amazon Elastic MapReduce and Microsoft Azure HDInsight.

Problem position

Maximising the profit is an important issue for cloud providers, but the existing data processing frameworks are not designed in a way that takes into account the pricing model and SLAs in the resource allocation process. Expenditures can be reduced if resource management handles these aspects. The number of assigned resources should increase if the load is high and decrease if the demand is low. If it is done in an automated way, this process is called auto-scaling.

The questions, in this case, are: when to scale and how much resources we should add or remove. Most current cloud providers use an intuitive approach based on thresholds for virtual machines (VMs) level auto-scaling and several related methods are proposed in literature [START_REF] Khatua | Optimizing the utilization of virtual resources in cloud environment[END_REF][START_REF] Chieu | Scalability and performance of web applications in a compute cloud[END_REF][START_REF] Simmons | Managing a saas application in the cloud using paas policy sets and a strategy-tree[END_REF][START_REF] Ghanbari | Exploring alternative approaches to implement an elasticity policy[END_REF][START_REF] Han | Lightweight resource scaling for cloud applications[END_REF][START_REF] Hasan | Integrated and autonomic cloud resource scaling[END_REF]. The main idea of this approach is to add (or remove) resources if a certain metric is above (or below) a predefined threshold. The thresholds are usually defined by humans in the provider or the tenant side.

The main drawback of the thresholds based approach is the fact that it requires a deep understanding of workload trends to choose good thresholds, which is not easy to achieve. This is why much scientific work was done to design human independent auto-scaling methods based mainly on reinforcement learning [START_REF] Dutreilh | Using reinforcement learning for autonomic resource allocation in clouds: towards a fully automated workflow[END_REF][START_REF] Rao | A distributed selflearning approach for elastic provisioning of virtualized cloud resources[END_REF]. The learner is an agent that makes successive actions in an environment and receives a reward for each taken action. After a set of random trials, he should learn how to take good actions which avoid human intervention.

In practice, there is no general reinforcement learning solution that provides an efficient scaling for all possible applications and architectures. Each solution must consider the environment, the cost objective and constraints of a specific application and we notice that the most existing methods focus on web querying. A query in these applications can be seen as an atomic task assigned to a single resource for a short time period. These methods are not suitable for database querying applications. Indeed, the structure of a SQL-like query is considered complex compared to other common applications. The physical execution plan of the query contains many tasks. Some of them are parallel, others are linked by a producerconsumer relation. So parallelism and communication must be considered.

Existing works that use reinforcement learning for autoscaling are based on the information about the present to define the state description and cost function. This may be sufficient for applications in which queries consist of one or few tasks with a short execution time but databases queries consist of several dependent tasks with relatively long execution time. Information about the present may generate under or over scaling. Indeed, a query launched at the moment t may end at the moment t t where t is not negligible. This is why it is also important to have some knowledge about the future during the scaling decision.

Moreover, in a database query, if the consumer is not launched at the moment the data is generated by the producer then the intermediate data can be stored on disk. The storage in the cloud has a significant monetary cost.

Contribution

In this work, we propose an auto-scaling method based on reinforcement learning for database querying in the cloud. In order to satisfy scalability and accelerate learning, the method applies a parallel variant of reinforcement learning [START_REF] Kretchmar | Parallel reinforcement learning[END_REF][START_REF] Grounds | Parallel reinforcement learning with linear function approximation[END_REF][START_REF] Barrett | Applying reinforcement learning towards automating resource allocation and application scalability in the cloud[END_REF]. In this variant, the number of agents is greater than one. Agents work independently but share their experience to learn quickly. This variant is recommended for database querying given the large number of queries and resources to manage.

The main originality of our work is the fact that we estimate the resource availability and penalties of a future time window in order to provide more accurate state description and reward function in the reinforcement learning process. These estimations are injected into the reinforcement learning algorithm to improve agents learning ability. The computation of the estimations is based on the placement and scheduling plan. We refer to the overall process (auto-scaling, placement, and scheduling) as elastic resource allocation.

Another originality of our work is the fact that we take into account the storage of intermediate data in the reward function of the reinforcement learning algorithm. Storage is an aspect that characterises database applications. The intermediate data can be temporarily stored on disk if the consumer is not yet available and storage in the cloud has a significant monetary cost.

The rest of this paper is organised as follows: Section 2 explains the context and an overview of the elastic resource allocation process. We give a detailed explanation of the proposed auto-scaling method in Section 3. Section 4 presents the experimental environment and the results. An overview of the existing work on auto-scaling in the cloud is provided in Section 5. We conclude in Section 6.

Elastic resource allocation process: an overview

In this section, we give an overview of the query compilation context (2.1). Then, we explain the idea of the elastic resource allocation process that we propose and the intuition behind the placement-scheduling phases (2.2). Finally, we present the performance model (2.3). More details about placement and scheduling can be found in Appendix A and B.

SQL-like query compilation

Figure 1 shows the SQL-like query compilation process. Tenants submit SQL-like queries using the client interface. First, the lexical and syntactic analyser verifies that the query is syntactically correct. Then, the logical optimisation applies some transformation rules in order to reduce the volume of manipulated data during the query execution. The physical optimisation chooses the join algorithms, defines the join order and generates the execution plan. Finally, the paralleliser defines the degree of parallelism and generates a Directed Acyclic Graph (DAG) of tasks.

Older versions of parallel data processing framework represent this graph by a set of dependent MapReduce jobs (Figure 2a). MapReduce [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF] is recognised as an efficient parallel programming model. Indeed, it allows performing computation on massive data partitioned on a large number of nodes. However, the classical MapReduce model has some drawbacks. The graph is represented by a set of dependent jobs. Between two successive jobs, there is a write operation, then a read operation on the Distributed File System (DFS). In addition, the pipeline is not planned and each job must contain a Map and a Reduce phase even if one of them is not necessary. Recently, another model has been proposed and already integrated into existing tools, mainly Hive/Tez [START_REF] Saha | Apache tez: A unifying framework for modeling and building data processing applications[END_REF] and SparkSQL [START_REF] Armbrust | Spark sql: relational data processing in spark[END_REF]. 1 It consists of using a single job for the entire query (Figure 2b). The internal structure is flexible. Indeed, the query is represented by a set of stages. A stage can perform either a Map or Reduce function. Each stage has many parallel tasks. The task does the processing on part of the data. The pipeline is allowed between the linked stages and read/write of intermediate data in DFS is avoided.

In this paper, we refer to the classical MapReduce as the multi-job model and the new representation as the single-job model. In Hive/Tez, the query in Figure 1 contains three Map Joins (MJ) and a Group Operator (GO). It is represented by a DAG with four Map stages and two Reduce stages.

Elastic resource allocation process

The cloud service infrastructure consists of a set of physical machines (Figure 4). A hypervisor, whose role is to manage VMs, is installed on each physical machine. A VM contains a set of logical resources. A logical resource is an abstract representation of a certain amount of reserved CPU, memory and storage. The system receives DAGs of submitted queries. The capacity manager adjusts the number of logical resources reserved for the service (auto-scaling). The global resource allocation manager performs task placement and scheduling given the available logical resources. Each elementary task is assigned to a particular logical resource for a given time period.

Figure 3 illustrates the elastic allocation process that we propose. This process is a sequence of four steps: (1) autoscaling, (2) choice of method, (3) placement and (4) scheduling. These steps are performed one after another. A complete execution of the four steps is called an iteration. A new iteration is performed in each fixed unit of time dt . In a given iteration launched at the moment t, the system handles the DAGs received between (t -dt) and t.

Auto-scaling is the process of determining the number of logical resources required to meet the load with minimum cost. We give more details about the proposed auto-scaling method in Section 3. Following the auto-scaling, the agent chooses the best method for placement and scheduling of tasks based on graph sizes and the number of assigned resources. The placement consists of choosing a logical resource for each task (Figure 5a). Scheduling allows choosing the time window assigned to each task (Figure 5b). At the end of each iteration of this process, the final placement-scheduling plan, as well as the estimated costs of penalties and storage of the intermediate data are injected into the capacity manager in order to be used for the scaling of the next iteration. There are n agents that work independently. In our architecture, only one database querying application is considered. Each agent is responsible for multiple queries. There are two benefits of using n agents working in parallel: (1) experiences can be shared between agents which accelerate the learning, (2) the elastic allocation process is faster when there are many agents. To explain the second point we consider the following example. We assume that at the moment t , there are 50 allocated logical resources and 20 queries arriving in the system. Consider the first case where we have only one agent, the latter must do the placement-scheduling concerning 20 queries on 50 logical resources. Let's consider a second case where we have five parallel agents. In this case, each agent must do the placement-scheduling concerning four queries (20/5) on approximately ten logical resources (50/5). The problem is less complex in the second case since there are fewer queries and logical resources to manage by an agent, so placement-scheduling decision algorithms are faster.

Our auto-scaling solution is dependent on placement and scheduling. These latter are optimisation problems. In the field of optimisation, there are two main classes of methods: approximate and exact methods. Our elastic resource allocation process supports the approximate method proposed in [START_REF] Kllapi | Schedule optimization for data processing flows on the cloud[END_REF] as well as an exact method based on Integer Linear Programming (ILP) that is part of our research [START_REF] Kandi | An integer linear-programming based resource allocation method for SQL-like queries in the cloud[END_REF]. The ILP formulation is presented in Appendices A and B. A choice of the approach is made first based on the complexity of the queries received and the number of available resources.

Performance model

Since the elastic allocation process is performed before running queries, it is essential to estimate the duration of tasks. This estimation is based on the size of the data, the number of tuples, the selectivity of the operators and some system parameters (Table 1). The formula applied to estimate task duration depends on the operators executed by the task. For example, let's consider a stage Si that performs a selection on a relation 1 R then a Map Join between the result of the selection and a relation 2 R . The duration ( ET ) of an elementary task of the stage Si is estimated as follows [START_REF] Yin | SLA definition for multi-tenant dbms and its impact on query optimization[END_REF]:

( ) = ( ET Si sum (| 1 | * | 1| / ) / ; / / i R

Auto-scaling method

The goal of auto-scaling is to add or remove resources in order to respond to load variation. The proposed auto-scaling method is based on parallel reinforcement learning. We explain in this section the reinforcement learning principle (3.1), then the modelling of the learning solution for the auto-scaling problem (3.2).

Reinforcement learning (RL) principle

The basic idea of reinforcement learning is that we have an agent who makes decisions in a complex environment. At each moment, the agent knows the current state of the system and takes an action that allows moving to another state. When the agent takes an action, the environment provides him a reward (or a penalty) -Figure 6. After a set of iterations, the agent should learn the sequence of actions that maximise the total reward (or minimise the total penalty). The operation of such a system is modeled by a Markov decision process (MDP). An MDP is a mathematical model represented by a state space ( S ), an action space ( A ), probabilities of transitions between states and rewards ( R ). At the moment t , the agent is in a state t s , then he chooses an action ( )

t t a A s , such that ( ) t
A s is the set of possible actions when the system is in the state t s . Following the action, the agent receives a reward Q s a quantifies the possible actions. The best action is the one with the highest value of Q (or the lowest if r is seen as a penalty). When the MDP structure is well known, the values of Q can be computed with the value iteration method [START_REF] Alpaydin | Introduction to Machine Learning[END_REF]. However, usually the structure of the system and its behaviour are not known in advance, and in this case, reinforcement learning algorithms, such as Q-learning (described in [START_REF] Alpaydin | Introduction to Machine Learning[END_REF][START_REF] Watkins | Learning from Delayed Rewards[END_REF]) is more appropriate. There are several variants of Q-learning. A variant called Sarsa is presented in Algorithm 1. The algorithm uses learning to find an estimated value ( Q ). Q is initialised with an arbitrary value (line 1) then improved in each iteration as the agent explores the state space (line 13). The strategy to choose the next action should make a trade-off between exploring the state space and maximising the reward. For this, the agent chooses an action randomly with a probability (lines 8-9) and chooses the action with the highest ˆ( , ) Q s a with the probability 1 (lines 10-11). The parameters , and the function are defined in advance.

Algorithm 1: Q-Learning Sarsa [START_REF] Alpaydin | Introduction to Machine Learning[END_REF] 1: initialise all

Modelling the learning solution for auto-scaling

We apply reinforcement learning to ensure that the cloud service described earlier has the correct number of logical resources. We define the state as a triplet: (1) the number of logical resources allocated for each type, (2) the current time of the day, and (3) the resource availability level.

Formally a state = ( , , ) s n h d . With

1 2 ( ) = ( , ,.... ) card n n n n ,
is the set of resources types, each type is characterised by its memory capacity and monetary cost, c n is the number of assigned type c resources, h is a discrete representation of the current time of the day, 0 1 d define the resource availability level.

Unlike web applications, the duration of a database query can be long. The resource availability level in our method is not just based on the current moment (this is the case for most of the work of state-of-the-art work) but also on a future time window calculated from the resource placement-scheduling plan. The availability level d is computed with the formula (2). With ( ) iter is the set of potential logical resources in the current iteration 'iter', T is the number of considered future time windows, In order to explain the intuition behind formula (2), we consider the example of Figure 7. The numerator of the formula represents the surface of the grey area (the resources are busy). The denominator represents the surface of the grey area plus the surface of the white area (the resources are busy + they are free). So d is a number between 0 and 1, with d is close to 0 (resp. close to 1 ) when there are many available resources (resp. many busy resources) in the considered future time window T . nbDigits is the number of digits from the decimal point when we apply the round function. The round function is necessary to get a state space with a finite number of states.

1 1 2 ( ) = 1 ( ) = 1 ( ) = 0 a c a c a c 2 1
c c (i.e. we don't add or remove more than one resource in a single iteration).

The reward following an action a includes: (1) the cost of using physical resources ress C , (2) the cost of assigning and releasing resources ajust C , (3) the costs of penalties paid by the provider in case of SLA violation pen C and (4) the cost of using storage stor C :

( , ) = ( ) ( ) ( ) ( ) ress ajust pen stor R s a C s C a C s C s (3)
The cost of using resources includes the processor cost proc C and memory mem C :

( ) = ( ) ( ) ress proc mem C s C s C s (4)
The processor (resp. memory) cost is calculated as follows:

( ) = * .

proc proc c c C s W s n (5) ( ) = * ( ) * . mem mem m c c C s W C c s n (6) proc W
is the processor cost weight, mem W is the memory cost weight, . c s n is the number of logical resources of type c when the system is in state s , ( ) m C c is the available memory in the type c resources.

The adjustment cost depends on the cost of adding resources asg C and the cost of removing resources rel C

(1 = 1 condition if the condition is true, = 0 otherwise):

( )>0 ( )<0 ( ) = ( ) *1 ( ) *1 ajust asg a c rel a c c C a C c C c (7)
Penalties ( pen C ) and storage ( stor C ) costs depend on task scheduling (Appendix B). Based on the objective function of the ILP scheduling model and assuming that the optimal solution of this ILP is denoted * * * { , , } y w , we have (the notation is described in Table A1):

* , < < ( ) = * pen i i t i D T t T i i C s W (8) * , , < ( ) = * * stor s i i m t i S m T t T i C s W q w (9)
The goal is to minimise the cumulative reward ( R ) in long run. The best action is the one with the lowest value of Q (formula ( 1)). In our problem, the behaviour of the MDP is not known in advance so, as mentioned in the end on Subsection 3.1, an algorithm such as Q-learning can be used to learn an estimated value Q . The value of Q is improved in each iteration based on the observed reward and the state description.

In reinforcement learning, the number of times a state is visited determines the quality of the decision. Indeed, more visits imply a better experience. It is therefore interesting to adopt methods that accelerate the evolution of the learning agent's experience. We propose to adopt parallel reinforcement learning [START_REF] Kretchmar | Parallel reinforcement learning[END_REF] to accelerate learning. The system has a set of parallel agents who share their experiences. Each agent i makes his decisions using a measure ˆi Q consisting of his own local experience ˆi l Q and the global experience ˆi g Q that the other agents shared with him.

Algorithm 2 illustrates the parallel reinforcement learning applied to our problem and executed by an agent i among a set of agents. In this algorithm: ( , ) i k s a is the number of times the action a was taken following a visit to the state s . The agent can give more importance to his own experience and so, in this case, l W and g W are chosen such that > l g W W . Algorithm 2 is executed by the capacity manager (represented in Figures 3 and4).

j j l j Agents j i k s a Q s a K 23: ˆ( , ) i Q s a ˆ* ( , ) * ( , )
* * ( 1) * ( , ) * ( , ) * * ( 1)

i i i i l l g g l g W k s a Q s a W K nbAgents Q s a W k s a W K
i i i i l l l l Q s a Q s a R s a Q s a Q s a 33: ( , ) (

Experimental results

We present an experimental evaluation of the auto-scaling method. In Subsection 4.1, we give a general overview of the performed simulation. In Subsection 4.2, we compare our method that uses placement-scheduling plan to estimate the future resource availability, penalties and storage usage with an auto-scaling method that works independently of placement-scheduling. We illustrate the advantage of our method in terms of monetary cost. In Subsection 4.3, we show the impact of experience sharing and how the method scale. We assume that some agents exploit the shared experience and others not and evaluate the monetary cost and allocation duration. In Subsection 4.4, we compare two variants of the algorithm: the standard Q-learning and Sarsa. The goal is to justify the choice of the Sarsa variant for our solution

Simulation setup

We evaluate the proposed solution by simulation. The queries are retrieved from the TPC-H benchmark then tested on Hive (a version based on Tez) in order to define: (1) the structure of DAGs, (2) the number of parallel tasks per stage and (3) the estimated size of the intermediate data. ILP models are solved with GLPK. We assume that each agent handles 10 simulated VMs that contain eight logical resources each. We have two types of VMs: type 1 VMs (composed of eight logical resources with 256MB of memory each, price: 0.25$/hour) and type 2 VMs (composed of eightlogical resources with 512MB of memory each: 0.5$/hour). For a given query, the provider pays a penalty of 0.1$ for each minute after the deadline specified in the SLAs. We assume also that the cost of adjusting resources (add or remove a resource) is 0.1$.

Our simulation was performed on a computing node with four AMD processors and 512 GB of RAM. In all experiments, the global monetary cost is simulated. The global monetary cost at a given iteration is the sum of the following costs: 1) used logical resources, 2) penalties caused by violation of deadlines, 3) adjusting resources and 4) storage of data of consumers are not yet ready. The global monetary computation is based on formula (3) -Section 3.2.

In the simulation, we run Algorithm 2 for a large number of iterations (up to 70000 iterations). An iteration is defined as a complete execution of lines from 14 to 38 of the algorithm. At the beginning of each iteration, we assume the arrival of a number of queries represented by their DAG (line 14 of the algorithm). The number of received queries follows a random distribution that depends on the time of day. The number of queries received on the day is more important than the number received at night. The maximum number of queries considered is 540 queries/hour. All these queries have a DAG that follows the TPC-H benchmark. It is important to mention that a query started at the iteration i may end later (i.e. at iteration i j , > 0 j ). In each iteration, a scaling decision is made (line 25 to 30 of the algorithm).

We set = 0.5 and = 0.8 . We recall that Algorithm 2 uses the parameter to make the compromise between the choice of the right decisions and the exploration of the state space. In order to test different scenarios we propose three policies:

Policy 1 (three steps): In this section, we compare our work with an auto-scaling method from the literature. We chose to not compare our solution with threshold-based methods. The difference between the reinforcement learning approach and the threshold approach is discussed in the related work section. The advantage of reinforcement learning is the fact that it is independent of human intervention. If we compare our work with a method based on thresholds we will have to manually set the values of the thresholds, so performing a fair comparison is not obvious.

We have therefore compared our work with a method of literature also based on reinforcement learning. The baseline is similar to the solution presented in [START_REF] Dutreilh | Using reinforcement learning for autonomic resource allocation in clouds: towards a fully automated workflow[END_REF]. The particularity of our work is the dependence between the auto-scaling and the placement-scheduling. Indeed, as explained in the Subsection 3.2, the output of the placement-scheduling is used to give a more precise representation of the states of the MDP and the reward function. The baseline, contrariwise, uses the Q-learning algorithm but assumes that auto-scaling is performed independently of the outputs of the placement-scheduling. In the following, we call our proposal SQLCloudRL (SQLlike Queries Cloud Reinforcement Learning). The baseline is named BasicCloudRL (Basic Cloud Reinforcement Learning).

In Figure 8 the global cost ($) is cumulative over an iteration interval. The value of 'step' indicates the length of this interval. Three agents are considered in each test and the given values in y-axis correspond to the average monetary cost per time unit of the three agents. At iteration 1, each agent has no knowledge of the environment so the monetary cost is high at the beginning. The agent explores the environment, stores its experiences and exploits it in the decision making which makes the monetary cost decreases. On the one hand, the scaling decisions for policy 1 and 2 are almost random at the beginning ( ( ) = 0.999 iteration when 0 < 10000 iteration

). The global costs, therefore, remain stable and high in this period of time. The random decisions allow the agent to explore more possibilities so learning is fast. As soon as we change the value of at iteration = 1000, the agent starts using the stored experience to make the scaling decisions so the costs drop sharply. Policy 3, on the other hand, uses a progressive approach. The agent makes a trade-off between exploration and optimisation from the beginning ( ( ) = 0.1 iteration iteration ). The cost, therefore, decreases in a less brutal way than policies 1 and 2.

The same figure shows the advantage of our formulation compared to the existing auto-scaling method in terms of monetary cost. The benefit of our proposal is due to the consideration of estimate the future resource availability level and penalties from the previous placement-scheduling plan. The formulation of the baseline can be useful for short queries (web applications) but not sufficient for long queries of database querying applications. For long queries, considering a future estimate allows a more precise definition of a state of the MDP. The gain in terms of monetary cost becomes very significant in a real cloud with tens or even hundreds of agents and after a large number of iterations.

Experiment 2: impact of experience sharing

(no share vs. share)

We consider three agents who work in parallel and share their experiences. Agents 2 and 3 use the shared experience (share)

while agent 1 uses only its own experience (no share). Table 2 and Figure 9 show the results. We note the same remarks as the previous experiment 1 regarding the overall trend of the curves. In addition, the cost values for the agents who benefit from the shared experience (agents 2 and 3) are lower than those who do not (agent 1). Indeed, sharing experience allows agents 2 and 3 to learn faster than agent 1. Then we vary the number of agents and observe the evolution of the monetary cost and allocation duration: scaling+placement+scheduling (Figure 11). On the one hand, the monetary cost decreases with the increase in the number of agents. Indeed, more there are agents sharing their experience, faster is the learning and therefore the auto-scaling is done in a more efficient way. On the other hand, the increase in the number of agents implies more messages exchanged and therefore more allocation duration.

To limit the allocation duration when the number of agents is very large, it is possible to group the agents into clusters such that each agent shares its experience only with the agents of his cluster. Another solution is not to exchange at each iteration but rather after a certain number of iterations.

Experiment 3: comparison of the standard Q-learning algorithm and the Sarsa variant (standard Q-learning vs. Sarsa)

We show in this experiment why we chose the Sarsa variant as a learning algorithm. The difference between the standard Q-learning algorithm and Sarsa is the way to update the values of ˆ( , ) Q s a . Standard Q-learning uses the best action a of the next state s to update ˆ( , ) Q s a while Sarsa first chooses an action a using the current policy and then returns to update ˆ( , )

Q s a . The two algorithms combine the exploration and the optimisation in the decision making but the standard Q-learning considers that the agent takes always the optimal policy when updating the values of Q whereas Sarsa considers the fact that actual policy combines the exploration and the optimisation (i.e. Sarsa allows the agent to learn that some of his decisions are random). The stored experience in Sarsa is, therefore, more accurate than the standard Q-learning. We consider only one agent in this experiment. Table 3 andFigure 10 confirm that Sarsa is more efficient than Standard Q-learning in terms of monetary cost.

Discussion

The performed experiments concern three aspects:

First, reinforcement learning and its applicability to the auto-scaling problem for SQL-like queries. A comparison of our auto-scaling method and an existing method showed the benefit of using the placementscheduling output. The state definition of the MDP is more precise so the monetary cost is lower.

Then, the collaboration between agents. We observed that exploiting the shared experience allows agents to learn faster and reduce costs but the allocation time is more important because of the communication between agents.

Finally, the performance of Sarsa learning. Sarsa variant is more efficient than the standard Q-learning. This can be explained by the fact that Sarsa is based on more precise calculations of Q . Indeed, Sarsa allows the agent to learn that some of his decisions are random.

Related work

The existing methods that deal with auto-scaling are diverse in regards to the decision making approach. Each work has been designed with particular goals and focusing on a target architecture. State-of-the-art methods can be classified in different ways. In this section, we give a brief overview of existing methods and focus on two approaches: (1) threshold based and (2) reinforcement learning. On the one hand, because of its intuitive appearance, the threshold based approach is adopted by the current cloud providers. On the other hand, reinforcement learning is currently experiencing interest from the scientific community and its adoption for different cloud applications and architectures is a promising trend.

Threshold based approach

Using threshold rules is a well-known approach for autoscaling in the cloud. The idea is to add new resources when a certain metric exceeds an allocation threshold and to release resources when the metric is below a release threshold. Existing work can be classified into two categories. Some works are based on the observed values of the metric [START_REF] Han | Lightweight resource scaling for cloud applications[END_REF][START_REF] Hasan | Integrated and autonomic cloud resource scaling[END_REF] while others apply prediction techniques [START_REF] Khatua | Optimizing the utilization of virtual resources in cloud environment[END_REF]. [START_REF] Han | Lightweight resource scaling for cloud applications[END_REF] claim that scaling resources does not always require to add or remove VMs constantly. Modifying VM's capacity (CPU and memory) can be conducted to achieve scaling with fewer costs and less time. They introduced a lightweight algorithm to enable scaling at the level of underlying CPU and memory. The solution uses separate thresholds for the processor and the memory. The considered metrics are based on observation and not predictions. Moreover, communication costs are not considered.

The communication aspect has been considered in some works. [START_REF] Hasan | Integrated and autonomic cloud resource scaling[END_REF] use link load, jitter, and delay as metrics. They focus on the relation between compute and network. They emphasise the fact that these three domains are often considered separately for scaling. To address this limitation, they proposed a threshold mechanism that combines metrics from computing and network domains. This work also considers only observed values to compute metrics.

Some other works propose to associate the approach of thresholds with a voting process (RightScale). Each VM votes for a scaling action (add or remove resources). The vote is based on one or more rules managed by metrics and thresholds. The scaling action is triggered if the majority of VMs agree. This solution was adopted by [START_REF] Chieu | Scalability and performance of web applications in a compute cloud[END_REF] and [START_REF] Simmons | Managing a saas application in the cloud using paas policy sets and a strategy-tree[END_REF]. There are also works that combined the thresholdbased approach with other scaling approaches. [START_REF] Ghanbari | Exploring alternative approaches to implement an elasticity policy[END_REF] propose an elasticity policy using both control theory and threshold based approaches. Unlike the use of thresholds which is more intuitive, the control theory is based on mathematical modeling. RightScale was used in this work as a threshold based management cloud system.

All the works cited above use the observed values to calculate the metrics. Other studies have considered the prediction of future values. We mention, for example, [START_REF] Khatua | Optimizing the utilization of virtual resources in cloud environment[END_REF] who uses time series theory [START_REF] Mills | Time Series Techniques for Economists[END_REF] to predict future values. If any of the predicted values exceeds the predefined threshold then an event is triggered.

The intuitive nature of threshold rules attracted cloud providers. However, the choice of metrics to consider and the setting of thresholds in an efficient manner requires human intervention and a deep understanding of the current workload trends which is not easy to achieve. Another approach independent of human intervention interests the scientific community. It is based on reinforcement learning

Reinforcement learning approach

Reinforcement learning has been adopted for auto-scaling in some cloud work. Existing methods can be differentiated by the scaling mode, the learning algorithm and the technique used to accelerate learning.

Scaling mode in the cloud can be horizontal or vertical. In the horizontal scaling, possible actions are to add or remove resources [START_REF] Dutreilh | Using reinforcement learning for autonomic resource allocation in clouds: towards a fully automated workflow[END_REF]. In the vertical scaling, contrariwise, the number of resources is fixed and possible actions consist to adjust their configuration in terms of CPU and memory [START_REF] Rao | Vconf: a reinforcement learning approach to virtual machines autoconfiguration[END_REF][START_REF] Rao | A distributed selflearning approach for elastic provisioning of virtualized cloud resources[END_REF].

The typical reinforcement learning algorithm is standard Q-learning but some works use a variant called Sarsa [START_REF] Tesauro | A hybrid reinforcement learning approach to autonomic resource allocation[END_REF]. The two variants were considered and compared in the experimental section. More details on the difference between standard Q-learning and Sarsa can be found in [START_REF] Alpaydin | Introduction to Machine Learning[END_REF].

Despite their advantages, reinforcement learning algorithms have certain problems including the large learning time and the size of the state space. [START_REF] Dutreilh | Using reinforcement learning for autonomic resource allocation in clouds: towards a fully automated workflow[END_REF] introduce a greedy policy to find a good initialisation of learning values, a convergence speedup technique, and performance model change detection. [START_REF] Rao | Vconf: a reinforcement learning approach to virtual machines autoconfiguration[END_REF] propose initially to adopt a global reinforcement learning model for vertical scaling. In this model, the state is described by the amount of CPU/memory of all VMs in the cloud. This approach gives rise to a very large number of states and therefore a lot of time to sufficiently explore the model. Then, [START_REF] Rao | A distributed selflearning approach for elastic provisioning of virtualized cloud resources[END_REF] consider that each VM has its own local model and in this case, the state is defined by the amount of CPU/memory of this VM only so the complexity is reduced. [START_REF] Barrett | Applying reinforcement learning towards automating resource allocation and application scalability in the cloud[END_REF] use a parallel version of learning but the level of generality is limited to the VM level (not logical resource level), the auto-scaling is independent of placement-scheduling and the specificities of databases querying are not considered in the state description and reward function).

Discussion

Few works for auto-scaling in the cloud are dedicated to database querying. There are some works that proposed autoscaling solutions for databases in the cloud but they focused on specific technologies, for example, MongoDB [START_REF] Huang | The improvement of auto-scaling mechanism for distributed database-a case study for mongodb[END_REF] or Hadoop [START_REF] Gandhi | Autoscaling for hadoop clusters[END_REF]. These works made performances (not monetary) metrics in their proposals. Some work focuses on NoSQL databases. For example, TIRAMOLA is an open-source framework to perform autoscaling of NoSQL clusters according to user-defined policies [START_REF] Konstantinou | Tiramola: elastic nosql provisioning through a cloud management platform[END_REF][START_REF] Angelou | Automatic scaling of selective sparql joins using the tiramola system[END_REF][START_REF] Tsoumakos | Automated, elastic resource provisioning for nosql clusters using tiramola[END_REF]. Decisions on adding or removing workers are modelled as MDPs. There is also existing work on cost-aware horizontal scaling of NoSQL databases [START_REF] Naskos | Dependable horizontal scaling based on probabilistic model checking[END_REF][START_REF] Naskos | Cost-aware horizontal scaling of nosql databases using probabilistic model checking[END_REF][START_REF] Naskos | Elton: a cloud resource scaling-out manager for nosql databases[END_REF]. These proposals are based on MDPs as well and they use probabilistic model checking as the main decision mechanism. In our work we focus on more complex and long-running queries.

The level of granularity in most existing work on autoscaling is limited to the VM level and queries are seen as atomic entities. In our work, we consider a finer granularity level. Indeed, a VM contains a set of logical resources and each query is decomposed into a job (or stage) graph with dependencies. Each logical resource uses a specific amount of physical resources (CPU, memory, and disk) on a specific machine. A job (or stage) contains a set of parallel tasks. The problem is therefore much more complex if we compare it to web applications.

Finally, the management of intermediate data is generally neglected in the existing work. This is an important feature for data processing applications. Indeed, if the next consumer of intermediate data is not available immediately, then this data might be stored. The use of storage capacity in the cloud has a monetary cost that cannot be ignored. Disks on Amazon S3, for example, are billed according to the size and duration of storage.

Conclusion

We addressed in this paper the resource allocation problem for database querying in the cloud. We proposed an autoscaling method coupled with placement-scheduling. The auto-scaling is based on parallel reinforcement learning and experience sharing. The results show that: (1) considering placement and scheduling plan to describe the MDP is more suitable to long queries than the reinforcement learning methods proposed in previous work, (2) using experience sharing reduces the monetary cost but generates exchanges that increase the allocation duration, (3) the Sarsa variant of Q-learning brings a lower monetary cost compared to the standard Q-learning.

In future work, we will focus more on placement and scheduling problems. So far, we proposed a static method based on estimates (Appendices A and B). The real values may not match those of the estimates at execution time which will generate additional costs. We plan to design a dynamic allocation strategy that detects estimation errors during execution time and change the allocation plan to reduce the impact of these errors. , , , , , , > 0

i j i m a i j j r b a b i j i j i j Q x Q x v Q i j m r a b Q (A5)
We add the constraint (A6) to improve the fair distribution of tasks between resources. Without this constraint, we noticed that tasks are not distributed in a balanced way on the resources. Tasks are more likely to be on the same resource. This reduces communication costs but there is a risk to be in situations where we have some too busy resources (risk of exceeding deadlines) and other resources underexploited. Adding the constraint (A6) makes it possible to take into account the balanced distribution of tasks on the available resources. The compromise between load balancing and communication costs is expressed in the objective function. We introduce the variable {0,1...., } T . The objective function we present later includes as a variable to minimise.

, , , < * ( 1) ,

i i m r r t i m t T i T x F r (A6)
The following objective function f takes into account the processor, memory, and network cost. It also takes into account load balancing:

, ,

1 2 , 1 2 1 2 = ( ) * * ( , ) * * i i m r i m r i com r r rep r r f C r T x C r r v W
The ILP formulation of the placement problem is: In the experimental section, the optimal solution of the placement ILP is found with GLPK software using Branchand-Bound algorithm [START_REF] Lawler | Branch-and-bound methods: a survey[END_REF][START_REF] Hromkovi | Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics[END_REF].

F

Indicate whether the resource a is initially available at the moment t ( = 1 ) or not ( = 0 ), r the deadline for the query to which the stage i belongs

Appendix B Task scheduling ILP model

The output of the placement model is considered as an input to the scheduling ILP model that we present in this section.

Table A1 shows the sets, parameters, and variables of the scheduling model. The linear constraints are as follows.

We can deduce from the definition of the family of variables y that: We propose the following formulation for the precedence between tasks constraint. We recall that 'pipeline' means that the task j can start as soon as the task i generates its first output. 'non-pipeline' means that the task j can start from the moment the task i ends.

, , , The optimal solution of the scheduling ILP is found with GLPK software using Branch-and-Bound algorithm [START_REF] Lawler | Branch-and-bound methods: a survey[END_REF][START_REF] Hromkovi | Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics[END_REF].

j r t i j j i y S i j r t T (B7) , , 1 , , , , < 1

Figure 1 Figure 2

 12 Figure 1 SQL-like query compilation process

Figure 3 Figure 4 Figure 5

 345 Figure 3 Parallel elastic allocation process

Figure 6

 6 Figure 6 Interaction between the agent and the environment

Figure 7

 7 Figure 7 Placement-scheduling plan example

Algorithm 2 :

 2 Parallel reinforcement learning (Agent i ) 1: initialise all ˆ( , ) DAGs of the new submitted queries 15: execute the action a (scaling) 16: notify the global resource allocation manager that the scaling is done (Figure3, arrow (a)), the placement and scheduling of new queries is therefore launched,

Figure 8

 8 Figure 8 Evolution of monetary cost over time (SQLCloudRL vs. BasicCloudRL)

Figure 9

 9 Figure 9 Evolution of monetary cost over time (no share vs. share)

Figure 10 Figure 11

 1011 Figure 10 Evolution of monetary cost over time (standard Q-learning vs. Sarsa)

  associated with each run time window after the deadline of the stage s W the weight associated with the storage cost of intermediate results i q the estimated amount of data generated by the stage i tasks Variables

Table 1

 1 Cost model parameters[START_REF] Yin | SLA definition for multi-tenant dbms and its impact on query optimization[END_REF]

		R		S	pd	i	iph cpu prepare tuples partioning
	(| 12 | * | 12 | * / ( R S	* pd pd i	i	1	) /	) * nb nd max pd pd ( , i	i	1	)
		/ /	transmit the result to the next stage	)
	Parameter			Signification
	| | Rx				number of tuples in Rx
	| | Sx				size of a tuple in Rx (Bytes)
	|	Rxy	|			number of tuples in Rx	Ry
	|	Sxy	|			size of a tuple in Rx	Ry (Bytes)
								selectivity
	pd	i				number of tasks in the stage Si
	db						disk I/O bandwidth
	dl						disk latency
	cpu				CPU processing speed
	nb						network bandwidth
	nd						network delay
	ipc						number of instructions for comparing
								two bytes
	iph						number of instructions for hashing a byte

S pd db dl read the data from disk (| 1 | * | 1 | / ) * ( / ); / / i R S pd ipc cpu execute de select operator (| ( 1) | *| 1| / )*( / ); / / i R S pd iph cpu execute de prob operator (| 2 | * | 2 | / ) / ; / / i R S pd db dl read the data from disk (| 2 | * | 2 | / ) *( / ); / / i R S pd iph cpu execute de build operator (| 12 | * | 12 | / )*( / ); //

  , ) 1

		i k s a	i k s a
	34: share ˆ( , ) i l Q s a and ( , ) i k s a with the others agents
	35: s s
	36: a a
	37:	iteration iteration	1
	38: wait for the next iteration
	39: until the system stops

Table A1

 A1 Notation used in the ILP placement and scheduling models Set of resources types, each type is characterised by its memory capacity and monetary cost

			Sets
		Set of stages of all submitted queries
		Set of potential logical resources
		The set of final stages of the submitted queries
			Parameters
	( ) T r y	the type of the resource r	, ( ) Ty r
	* ( ) m C i	The memory amount needed for a task of the stage i
	( ) C c m	the available memory amount in a type c resource c
	, i j Q	The amount of data transferred between a task of the stage i	and a task of the stage j

i Set of tasks of the stage i i T The local response time of a task from stage i T The number of considered future time windows , r t

Table A1

 A1 Notation used in the ILP placement and scheduling models (continued)

					Parameters
	1 2 ( , ) Dist r r	The distance between the resource 1 r	and the resource 2 r
	W	proc	The processor cost weight
	mem W	The memory cost weight
	com W	Load communication weight
	rep W	repartition weight
	( ) C r	The cost of the logical resource r	( ( ) = C r W	proc	mem W	* ( ( )) m y C T r )
	1 2 ( , ) C r r com	The cost of communication between the logical resources 1 r and 2 r	(	1 2 ( , ) = C r r com	com W	*	1 2 ( , ) Dist r r )
	S	, i j	indicates whether the stage i	and j	are linked by non-pipeline, , i j , , i j S	{0,1} ("non-pipeline"
				means that the task j can start from the moment the task i ends completely)
	, i j P	indicates whether the stage i	and are linked by pipeline, , {0,1} i j P	("pipeline" means that the task j
				can start as soon as the task i generates its first output)
	, i m A	indicates the logical resource in which the task	m	i	of the stage i	was placed following the placement
				phase

i D

  A resource cannot run more than one task at a time (exclusivity constraint). From the definition of the family of variables y and knowing that a task cannot be interrupted before its end, we can deduce that: , , uses the resource r at moment t ; = 0 otherwise. The linear formulation of the exclusivity constraint is as follows:

	, i j , P y * i m t , , 1 , i j m 1	, i j P	2 m * (1 , i	y	, , 2 , < , ) j m t w i m t , , 1 , j i j t T P	1, > 1	(B4)
									i m t y	, , i m t T i y	= 1	if the task m of the stage i
	i	, m A i m	= i	r	t T i	1 (	, , , , i m t y i m t y	, , , i m t T i , y r t F	) r	, < t T	(B5)
	i	, m A i m	= i	r	t T i	<1
																			The intermediate results of a task are maintained on the
																			local storage space until all successive tasks begin:
																			, , 1 , i m t y i j	= 1 ,	1 and y m	, , 2 , j m t 2 i m	= 0	j	,	, , 1 = 1 i m t w , i j S	, i j or P = 1	= 1	(B2)
																			This constraint can be expressed linearly as follows:
	, , i m t y	, , 1 , i m t y		i	,	m		i	, < t T	(B1)	S	, i j , i j *	, , 1 , i m t y m 1	S	, i j	2 * (1 , i m	y	, , 2 , < , ) j m t w i m t , , 1 , j i j t T S	1, > 1	(B3)

  The economic costs that influence the scheduling of tasks are penalties and storage of intermediate results. The goal is to find the combination of y and w that minimises this cost. Each query has a deadline specified in SLAs. The accumulation of penalties begins when the execution of the query exceeds the deadline. The objective function to minimise is the following. The first (resp. second) line represents the penalty cost (resp. storage cost):

								g	=	i W s	< < D T t T * W i i i	, , (1 i m t q w * max * r i i	, , i r t y	)	(B9)
											i	m	i	< t T
								This objective function is non-linear. To have a linear form,
								we introduce the family of variables	such as:
								1	, , i r t y		, i t		i		,	r	i	, < t T	(B10)
								The objective function can be expressed linearly as follows:
								g	=			i W	*	, i t
										i W s	< < D T t T * i i			, , i m t q w * i	(B11)
											< i S m T t T i
								The ILP formulation for the scheduling problem is:
								minimise	g
								subject to (B1), (B3), (B 4), (B5), (B 6), (B7), (B8), (B10)
												, , i m t y		{0,1},	i	,	m	i	, < t T
	y	r t i j	i m t y m	i	i j P r	j	t T	(B8)				, , i m t w , i t	{0,1}, {0,1},	i	i	, , < m t T	i	, < t T

Appendix A Task placement ILP model

Table A1 shows the sets, parameters, and variables of the placement ILP model. The linear constraints are the following.

The memory amount needed for a task of the stage i must not exceed the available memory amount in the chosen logical resource r : * , , ( ) * ( ( )), , ,

Each task is placed on one and only one logical resource:

, , = 1, ,

In order to ensure intra-stage parallelism, two tasks belonging to the same stage cannot be placed in the same resource:

, ,

1, ,

is the maximum amount of data transferred between the tasks placed on the resource a and the task placed on the resource b . This definition satisfies the statement (A4).

, ,

The statement (A4) can be expressed linearly with: , , ,