Tomasz Buchert

Cristian Ruiz

Lucas Nussbaum

Olivier Richard

A survey of general-purpose experiment management tools for distributed systems

Keywords:

In the field of large-scale distributed systems, experimentation is particularly difficult. The studied systems are complex, often nondeterministic and unreliable, software is plagued with bugs, whereas the experiment workflows are unclear and hard to reproduce. These obstacles led many independent researchers to design tools to control their experiments, boost productivity and improve quality of scientific results.

Despite much research in the domain of distributed systems experiment management, the current fragmentation of efforts asks for a general analysis. We therefore propose to build a framework to uncover missing functionality of these tools, enable meaningful comparisons between them and find recommendations for future improvements and research.

The contribution in this paper is twofold. First, we provide an extensive list of features offered by general-purpose experiment management tools dedicated to distributed systems research on real platforms. We then use it to assess existing solutions and compare them, outlining possible future paths for improvements.

Introduction

Distributed systems are among the most complex objects ever built by humans, as they are composed of thousands of systems that collaborate together. They also have a central role in today's society, supporting many scientific advances (scientific & high-performance computing, simulation, Big Data, etc.), and serving as the basis for the infrastructure of popular services such as Google or Facebook. Their role and popularity makes them the target of numerous research studies in areas such as scheduling, cost evaluation, fault tolerance, trust, scalability and energy consumption.

Given the size and complexity of distributed systems, it is often unfeasible to carry out analytic studies, and researchers generally use an empirical approach relying on experimentation: despite being built by humans, distributed systems are studied as if they were natural objects, with methods similar to those used in biology or physics.

One can distinguish four main methodologies for experimentation on distributed systems [1]:

• in-situ: a real application is tested on a real platform.

• simulation: a model of an application is tested on a model of the platform.

• emulation: a real application is tested using a model of the platform.

• benchmarking: a model of an application is used to evaluate a real platform.

Each methodology has its advantages and disadvantages. For example, results obtained during simulation are (usually) completely reproducible. On the other hand, as the platform is a model of the reality, the results may not apply in a general sense, as the model could lack some unnoticed but important features. In this paper we focus on experiments based on the in-situ and emulation methodologies.

Because of the actual size of the available testbeds and of the complexity of the different software layers, a lot of time is required to set up and perform experiments. Scientists are confronted with low-level tasks that they are not familiar with, making the validation of current and next generation of distributed systems a complex task. In order to lower the burden in setting up an experiment, different testbeds and experiment management tools have appeared. The last decade has seen more interest in the latter, mainly influenced by the needs of particular testbeds and other problems found in the process of experimentation such as reproducibility, replicability, automation, ease of execution, and scalability. Additionally, the existing number of papers oriented toward such tools asks for a classification in order to uncover their capabilities and limitations. Such experiment management tools are the main object of study in this paper. We propose a set of features that improve the experimentation process in various ways at each step (design, deployment, running the main experiment and related activities, and data and result management). Then, this list of features is used to carry out a fair comparison of tools for conducting experiments.

The rest of this paper is structured as follows. In Section 2 existing methods and approaches to experimentation with distributed systems are presented, as well as a definition of experiment management tools. Then, in Section 3, a set of features offered by existing experimentation tools is constructed and each element is carefully and precisely explained. In Section 4, we present a list of tools helping with research in distributed systems. Each tool is shortly presented and its features explained. Our additional observations and ideas are presented in Section 5. Finally, in Section 6 we conclude our work and discuss future work.

Context and terminology

This section introduces some definitions that will be used throughout this paper, as well as the context where our object of study plays its role.

Definitions

For our purposes, an experiment is a set of actions carried out to test (confirm, falsify) a particular hypothesis. There are three elements involved in the process: a laboratory (the place where one experiments), an investigator (the one who experiments) and an apparatus (the object used to measure). If an experiment can be run with a different laboratory, investigator and apparatus, and still produce the same conclusions, one says that it is reproducible. This is in contrast with replicability which requires the same results while keeping these three elements unchanged. The terms reproducibility and replicability (replayability) produce a lot of confusion and discrepancies as they are often used to describe different ideas and goals. The above definitions are compatible with the definitions given in [START_REF] Drummond | Replicability is not reproducibility: Nor is it good science[END_REF], although we do not share such a negative view about replicability as the authors. Being a "poor cousin" of reproducibility, replicability is nevertheless essential for the verification of results and code reusability as expressed in [START_REF] Davison | Automated Capture of Experiment Context for Easier Reproducibility in Computational Research[END_REF].

Finally, let us introduce a last piece of terminology and define the object of study in this paper. An experimentation tool or an experiment management tool (for research in distributed systems) is a piece of software that helps with the following main steps during the process of experimenting:

• design-by ensuring reproducibility or replicability, providing unambiguous description of an experiment, and making the experiment more comprehensible,

• deployment-by giving efficient ways to distribute files (e.g., scripts, binaries, source code, input data, operating system images, etc.), automating the process of installation and configuration, ensuring that everything needed to run the experiment is where it has to be,

• running the experiment itself-by giving an efficient way to control and interact with the nodes, monitoring the infrastructure and the experiment and signaling problems (e.g., failure of nodes),

• collection of results-by providing means to get and store results of the experiment.

Furthermore, it addresses experimentation in its full sense and it is normally conceived with one of the following purposes described fully in the next section:

• ease of experimenting,

• replicability,

• reproducibility,

• controlling and exploring parameter space.

In this study we narrow the object of study even more by considering only general-purpose experiment management tools (i.e., tools that can express arbitrary experimental processes) and only ones that experiment with real applications (i.e., in-situ and emulation methodologies). The former restriction excludes many tools with predefined experimental workflows whereas the latter excludes, among others, simulators (see Section 4.10).

Motivations for experimentation tools

As described before, there exist many tools that strive to ease experimentation with distributed systems. These tools are the main object of study in this article and as such they are described thoroughly in Section 4. Here, however, we discuss the main driving forces that are behind the emergence of experimentation tools.

Ease of experimenting

The first motivation, and the main one, for creating experimentation tools is helping with the scientific process of experimenting and making the experimenter more productive.

By providing well designed tools that abstract and outsource tedious yet already solved tasks, the development cycle can be shortened, while becoming more rigorous and targeted. Moreover, it may become more productive as the scientist may obtain additional insights and feedback that would not be available otherwise.

The ease of experimenting can indirectly help to solve the problem of research of questionable quality in the following sense. As the scientific community exerts pressure on scientists to publish more and more, they are often forced to publish results of dubious quality. If they can forget about time-consuming, low-level details of an experiment and focus on the scientific question to answer, hopefully they could spend more time testing and strengthening their results.

Replicability (automation)

Replicability which is also known as replayability deals with the act of repeating a given experiment under the very same conditions. In our context it means: same software, same external factors (e.g., workload, faults, etc.), same configuration, etc. If done correctly, it will lead to the same results as obtained before, allowing others to build on previous results and to carry out fair comparisons.

There are several factors that hamper this goal: size of the experiment, heterogeneity and faulty behavior of testbeds, complexity of the software stack, numerous details of the configuration, generation of repeatable conditions, etc. Among other goals, experimentation tools try to control the experiment and produce the same results under the same conditions, despite the aforementioned factors.

Reproducibility

It refers to the process of independent replication of a given experiment by another experimenter. Achieving reproducibility is much harder than replicability because we have to deal with the measurement bias that can appear even with the slightest change in the environment.

Therefore, in order to enhance the reproducibility of an experiment, the following features are required:

• automatic capture of the context (i.e., environment variables, command line parameters, versions of software used, software dependencies, etc.) in which the experiment is executed; • detailed description of all the steps that led to a particular result. The description of an experiment has to be independent of the infrastructure used. To do so abstractions for the platform have to be offered.

Controlling and exploring the parameter space

Each experiment is run under a particular set of conditions (parameters) that precisely define its environment. The better these conditions are described, the fuller is understanding of the experiment and obtained results. Moreover, a scientist may want to explore the parameter space in an efficient and adaptive manner instead of doing it exhaustively.

Typical parameters contained in a parameter space for a distributed system experiment are:

• number of nodes,

• network topology,

• hardware configuration (CPU frequency, network bandwidth, disk, etc.),

• workload during the experiment. One can enlarge the set of parameters tested (e.g., considering CPU speed in a CPU-unaware experiment) as well as vary parameters in their allowed range (e.g., testing a network protocol under different topologies).

Whereas the capability to control the various experimental parameters can be, and quite often is, provided by an external tool or a testbed (e.g., Emulab), the high-level features helping with the design of experiments (DoE), as the efficient parameter space exploration, belong to experimentation tools.

Scalability

Another motivation for an experiment control is scalability of experiments, that is, being able to increase their size without harming some practical properties and scalability metrics. For example, one can consider if an experimentation tool is able to control many nodes (say, thousands) without significantly increasing the time to run the experiment, or without hampering the statistical significance of results.

The most important properties concerning scalability are:

• time-additional time needed to control the experiment (over the time to run it itself),

• resources-amount of resources required to control the experiment,

• cost of the experiment-funds required to run the experiment and control it (cf. commercial cloud computing), • quality of results-the scientific accuracy of the results, their reproducibility in particular (contrary to the above properties, this one is hard to define and measure). These metrics are functions of experiment parameters (see Section 2.2.4) and implementation details. Among important factors that limit scalability understood as the metrics above are:

• number of nodes used in the experiment,

• size of monitoring infrastructure,

• efficiency of data management.

Testbeds

Testbeds play an important role in the design and validation of distributed systems. They offer controlled environments that are normally shielded from the randomness of production environments. Here, we present a non-exhaustive list of testbeds that motivated the development of experiment management tools. There exists a work on defining useful features of network testbeds, similar to the goals of our paper [START_REF] Siaterlis | A survey of software tools for the creation of networked testbeds[END_REF]. Unsurprisingly, some features overlap in both analyses.

Grid'5000 [START_REF] Cappello | Grid'5000: a large scale, reconfigurable, controlable and monitorable Grid platform[END_REF] is an experimental testbed dedicated to the study of large-scale parallel and distributed systems. It is a highly configurable experimental platform with some unique features. For example, a customized operating system (e.g., with a modified kernel) can be installed and full "root" rights are available. The platform offers a REST API to control reservations, but does not provide dedicated tools to control experiments. However, the nodes can be monitored during the experiment using a simple API.

Emulab [START_REF] White | An Integrated Experimental Environment for Distributed Systems and Networks[END_REF] is a network testbed that allows one to specify an arbitrary network topology (thanks to the emulation of the network). This feature ensures a predictable and repeatable environment for experiments. The user has access to a "root" account on the nodes and hence can easily adjust their configuration. Emulab comes with a dedicated tool to control experiments (see 4.3).

PlanetLab [START_REF] Peterson | A blueprint for introducing disruptive technology into the Internet[END_REF] is a globally distributed platform for developing, deploying and accessing planetary-scale network services. It consists of geographically distributed nodes running a light, virtualized environment. The nodes are connected over the Internet. PlanetLab offers Plush (see 4.4) for the experiment control.

ORBIT [START_REF] Raychaudhuri | Overview of the ORBIT radio grid testbed for evaluation of next-generation wireless network protocols[END_REF][START_REF] Ott | ORBIT testbed software architecture: supporting experiments as a service[END_REF] is a radio grid testbed for scalable and reproducible evaluation of next-generation wireless network protocols. It offers a novel approach involving a large grid of radio nodes which can be dynamically interconnected into arbitrary topologies with reproducible wireless channel models. A dedicated tool to run experiments with ORBIT platform is OMF (see 4.6).

DAS1 (Distributed ASCI Supercomputer) is a Dutch wide-area distributed system designed by the Advanced School for Computing and Imaging (ASCI). Distinguishably, it employs various HPC accelerators (e.g., GPUs) and novel network interconnect. Its most recent iteration is DAS-4. DAS does not offer a dedicated tool to control experiments, however it provides a number of tools to help with deployment, discovering problems and scheduling.

With the emergence of efficient and cheap virtualization, the scientists turn to cloud computing infrastructures as a viable experimentation platform. A popular commercial service is Amazon EC22 , but many alternatives and variations exist (e.g., Windows Azure3 ). There are non-commercial, open-source solutions available as well (e.g., OpenStack4 ). Even though the development of cloud computing solutions was not inspired by a need of a research platform, the scalability and elasticity offered by those make it an attractive solution for science. In [START_REF] Klinginsmith | Towards Reproducible eScience in the Cloud[END_REF] a framework oriented toward reproducible research on such infrastructures is proposed.

List of features offered by experiment management tools

In this section, we present properties available in experiment management tools for distributed systems after doing a literature review using the following sources:

• tools used and published by the most important and large-scale testbeds (see Section 2.3),

• papers referenced by these tools and papers that cite them,

• IEEE and ACM digital libraries search with the following keywords in the abstract or title: experiments, experiment, distributed systems, experimentation, reproducible.

We ended up with 8 relevant tools for managing experiments that met our criteria of an experimentation tool, however we also include Naive approach (see Section 4.1) in our analysis. An extensive analysis of the papers dedicated to those tools was performed; subsequently, a set of properties and features -highlighted by each of the tools as to be important for the experimentation process -was selected and classified. The list consists of nine groups of properties and features that have an important role in the experimentation process. The complete hierarchy is presented in Figure 1. The properties are grouped into 9 groups that cover different aspects of experiment management.

Description Language

The design of the experiment is the very first step in the experimentation process. The description language helps users with this step, allowing them to describe how the experiment has to be performed, as well as their needs for running the experiment. Characteristics that help with describing the experiment are presented in the following sections.

Representation (Imperative / Declarative / Workflow / Scripts) of experiments featured by a given tool is the approach used to describe the experiment and relevant details. Possible representations differ in their underlying paradigm (e.g., imperative, declarative) and in a level of abstraction that the description operates on. Some tools use low-level scripts to build experiments whereas others turn to higher abstractions, some of them graphical (e.g., workflows). The choice of a certain representation has implications on other aspects of the description language.

Modularity (Yes / No) is a property of experiment description language that enables easy adding, removing, replacing and reusing parts of experiments. An experiment expressed in a modular way can be logically split into modules with well-defined interfaces that can be worked on independently, possibly by different researchers specializing in a particular aspect of the experiment.

Expressiveness (Yes / No) that makes it effective in conveying thoughts and ideas, in short and succinct form. Expressiveness provides a more maintainable, clearer description. Various elements can improve expressiveness: well-chosen abstractions and constructions, highlevel structure, among others.

Low entry barrier (Yes / No) is the volume of work needed to switch from naive approach to the given approach while assuming prior knowledge about the infrastructure and the experiment itself. In other words, it is the time required to learn how to efficiently design experiments in the language of the given experimentation tool.

Type of Experiments

This encompasses two important aspects of an experiment: the platform where the experiments are going to be run on and the research fields where those experiments are performed.

Platform type (Real / Model) is the range of platforms supported by the experimentation tool.

The platform type can be real (i.e., consists of physical nodes) or be a model (i.e., built from simplified components that model details of the platform like network topology, links bandwidth, CPU speed, etc.). For example, platforms using advanced virtualization or emulation techniques (like Emulab testbed) are considered to be modeled. Some testbeds (e.g., PlanetLab) are considered real because they do not hide the complexity of the platform, despite the fact that they use virtualization.

Intended use (Distributed applications / Wireless / Services / Any) refers to the research context the experimentation tool targets. Examples of research domains that some tools specialize in include: wireless networks, network services, high performance computing, peer-to-peer networks, among many others.

Interoperability

It is important for an experimentation tool to interact with different platforms, as well as to exploit their full potential. The interaction with external software is an indisputable help during the process of experimenting.

Testbed independence (Yes / No) of the experimentation tool is its ability to be used with different platforms. The existing tools are often developed along with a single testbed and tend to focus on its functionality and, therefore, cannot be easily used somewhere else. Other tools explicitly target a general use and can be used with a wide range of experimental infrastructures.

Support for testbed services (Yes / No) is a capability of the tool to interface different services provided by the testbed where it is used (e.g., resource requesting, monitoring, deployment, emulation, virtualization, etc.). Such a support may be vital to perform scalable operations efficiently, exploit advanced features of the platform or to collect data unavailable otherwise.

Resource discovery (Yes / No) is a feature that allows to reserve a set of testbed resources meeting defined criteria (e.g., nodes with 8 cores interconnected with 1 Gbit network). Among methods to achieve this feature are: interoperating with testbed resource discovery services or emulation of resources by the tool.

Software interoperability (Yes / No) is the ability of using various types of external software in the process of experimenting. The experimentation tool that interoperates with software should offer interfaces or means to access or integrate monitoring tools, commands executers, software installers, package managers, etc.

Reproducibility

This group concerns all methods used to help with reproducibility and repeatability as was described in Section 2.2.3.

Provenance tracking (Yes / No) is defined as a way of tracing and storing information of how scientific results have been obtained. An experimentation tool supports data provenance if it can describe the history of a given result for a particular experiment. An experimentation tool can provide data provenance through the tracking of details at different layers of the experiment. At a low-level layer, the tool must be able to track details such as: commandline parameters, process arguments, environment variables, version of binaries, libraries and kernel modules in use, hardware devices used, and file system operations executed.

At a high-level layer, it must track details such as: number of nodes used, details of used machines, timestamps of operations, and state of the platform.

Fault injection (Yes / No) is a feature that enables the experimenter to introduce factors that can modify and disrupt the functioning of the systems being studied. These factors include: node failures, link failures, memory corruption, background CPU load, etc. This feature allows to run experiments under more realistic and challenging conditions and test behavior of the studied system under exceptional situations.

Workload generation (Yes / No) is a range of features that allow to inject a predefined workload into the experimental environment (e.g., number of requests to a service). The generated workload is provided by real traces or by synthetic specification. Similarly to fault injection, this feature allows to run experiments in more realistic scenarios.

Fault Tolerance

This group of features encompasses all of them that help with common problems that can happen during experiments and may lead to either invalid results (especially dangerous if gone unnoticed) or to increased time required to manually cope with them.

Checkpointing (Yes / No) allows to save a state of the experiment and to restore it later as if nothing happened. It is a feature that can, above all, save the time of the user. There are at least two meanings of checkpointing in our context:

• only some parts of the experiment are saved or cached,

• the full state of the experiment is saved (including the platform).

Of course, the second type of checkpointing is much more difficult to provide. Checkpointing helps with fault tolerance as well, since a failed experiment run will not necessarily invalidate the whole experiment.

Failure handling (Yes / No) of the experimentation tool can mitigate runtime problems with the infrastructure an experiment is running on. This means in particular that failures are detected and appropriate steps are taken (e.g., the experiment is restarted). Typical failures are crashing nodes, network problems, etc.

Verification of configuration (Yes / No) consists in having an automatic way to verify the state of an experimentation platform. Usually such a step is performed before the main experiment to ensure that properties of the platform agree with a specification. We distinguish verification of:

• software -ensuring that the software is coherent on all computing nodes,

• hardware -ensuring that the hardware configuration is as it is supposed to be.

Debugging

The features grouped in this section help to find problems and their causes during the experimentation process.

Interactive execution (Yes / No) refers to an ability to run the experiment "on-the-fly" including: manually scheduling parts of the experiment, introspecting its state and observing intermediate results. This feature is inspired by debuggers offered by integrated development environments (IDEs) for programming languages.

Logging (Yes / No) consists of features that allow bookkeeping of low-level messages emitted during experiments including those that were placed at arbitrary places by the experimenter. The messages are normally stored sequentially along with their timestamps making the log is essentially a one-dimensional dataset. The log can be used to debug an experiment and document its execution.

Validation (Yes / No) is a feature that offers the user a way to perform a fast (that is, faster than full execution of the experiment) and automatic way to verify the description of an experiment. Depending on the modeling language used and other details, the validation may be accordingly thorough and complete. For our purposes, we require that at least some semantic analysis must be performed, in contrast to simple syntactic analysis.

Monitoring

Monitoring is necessary to understand the behavior of the platform and the experiment itself. It consists in gathering data from various sources: the experiment execution information, the platform parameters and metrics, and other strategic places like instrumented software.

Experiment monitoring (Yes / No) consists in observing the progress of the experiment understood as set of timing and causal information between actions in the experiment. The monitoring includes keeping track of currently running parts of the experiment as well as their interrelations. Depending on the model used, this feature may take different forms.

Platform monitoring (Yes / No) is the capability of an experimentation tool to know the state of resources that comprise the experiment (nodes, network links, etc.). Data collected that way may be used as a result of the experiment, to detect problems with the execution or as a way to get additional insights about the experiment.

Instrumentation (Yes / No) enables the user to take measurements at different moments and places while executing the experiment. This includes instrumentation of software in order to collect measures about its behavior (CPU usage, performance, resource consumption, etc.).

Data Management

The management of data is an important part of the experiment. This section contains features that help with distribution and collection of data.

Provisioning (Yes / No) is the set of actions to prepare a specific physical resource with the correct software and data, and make it ready for the experimentation. Provisioning involves tasks such as: loading of appropriate software (e.g., operating system, middleware, applications), configuration of the system and starting necessary services. It is necessary for any experimentation tool to provide at least a rudimentary form of this functionality.

File management (Yes / No) is a feature that abstracts a tedious job of working with files. Therefore the user does not have to manage them manually at a low level which often is errorprone. This includes actions like automatic collection of results stored at participating nodes.

Analysis of results (Yes / No) is a service of an experimentation tool that is used to collect, store and visualize experimental results, as well as making dynamic decisions based on their runtime values. The latter ability paves a way for intelligent design of experiments by exploring only relevant regions of parameter space and therefore saving resources like energy or time.

3.9. Architecture This section contains features and properties related to how the tool is designed and what architecture decisions the authors made. This includes ways to interact with the tool, as well as technical details such as software dependencies, methods to achieve scalability and efficient execution of experiments.

Control structure (Centralized / Distributed) refers to the structure of nodes used to control the experiment. The architecture of a tool is centralized if the control of an experiment is centralized and there exists one node that performs all principal work. Otherwise, if there are multiple nodes involved in the experiment control, then the architecture is distributed.

Low resource requirements (Yes / No) of an experimentation tool refer to its resource consumption (memory, CPU, network bandwidth, etc.) associated with the activity of controlling the experiment. As the number of elements the experiment consists of increases (e.g., nodes), so does the amount of the resources necessary to control them.

Simple installation (Yes / No) is understood as a low difficulty of setting up a completely functional infrastructure that the tool needs in order to be used. This usually implies software dependencies (interpreters, libraries, special services, etc.) or a required hardware infrastructure (number of network interfaces, minimum memory size, number of dedicated nodes to control the experiment, etc.)

Efficient operations (Yes / No) is the range of features that provide methods, tools and algorithms to perform large-scale operations with the experimental infrastructure. This in particular includes: efficient and scalable methods for command execution, file distribution, monitoring of nodes, gathering of results, among others. Providing efficient versions of these actions is notably difficult as operations involving nodes in a distributed systems are non-trivially scalable as a number of nodes increases.

Interface (CLI / GUI / API) consists of different ways that the user can interact with the experimentation tool. Most of the tools provide command line interface, whereas some tools provide graphical interfaces, usually via webpage used to interact with the experiment.

Existing experimentation tools

The aim of this section is to present the state of the art of the existing tools for experimentation with distributed systems. We focus our attention on the tools that fulfill the criteria for being considered as an experimentation tool (for a list of tools that are not included in the analysis, see Section 4.10). The evaluation of all tools and the main result of our study are presented in Table 1 that shows a comparison of the tools based on the proposed list of features. Figure 2 shows a timeline of publications about these experiment management tools whereas Table 2 shows their impact measured as the number of citations about them.

Naive method

Frequently, experiments are done using this method which includes manual procedures and use of hand-written and low-level scripts. Lack of modularity and expressiveness is commonly seen because of the ad hoc nature of these scripts, and it is even worse when the experiment involves many machines. The experiment is controlled at a very low level, including some human 12 8 Modular API based on Python 9 Using GUI 10 Supports wired resources as well 11 PlanetLab oriented 12 GNU m4 13 Event-based (Tcl & ns) 14 XML 15 Ruby 16 Event-based (Ruby) 17 Modular API based on Python 18 Workflows (Ruby) 19 Modular API based on Python 20 Using GUI 21 Supports wired resources as well 22 PlanetLab oriented ⋆ Provided by testbed Table 1: Summary of analyzed experiment management tools for distributed systems research. Each feature is presented along with a number of tools that provide it. Similarly, for each group a percentage of implemented features from this group is shown. Features that are due to the integration with a testbed are marked with ⋆.

13

Figure 2: Timeline of publications dedicated to experiment management tools. The publication that attracted most of the citations (main publication) is underlined.

intervention. Therefore, interaction with many types of applications and platforms is possible at the cost of time required to do so. Parameters for running the experiment can be forgotten as well as the reason for which they were used. This leads to an experiment that is difficult to understand and repeat. Since the experiment is run in partially manual fashion, the user can react against some unexpected behaviors seen during the experiment.

Weevil

It is a tool to evaluate distributed systems under real conditions, providing techniques to automate the experimentation activity. This experimentation activity is considered as the last stage of development. Experiments are described declaratively with a language that is used to instantiate various models and provides clarity and expressiveness. Workload generation is one of its main features, which helps with the replicability of results.

Workbench for Emulab

Workbench is an integrated experiment management system, which is motivated by the lack of replayable research on the current testbed-based experiments. Experiments are described using an extended version of the ns language which is provided by Emulab. The description encompasses static definitions (e.g., network topology, configuration of devices, operating system and software, etc.) and dynamic definitions of activities that are based on program agents, entities that run programs as part of the experiment. Moreover, activities can be scheduled or can be triggered by defined events. Workbench provides a generic and parametric way of instantiating an experiment using features already provided by Emulab to manage experiments. This allows experimenters to run different instances of the same experiment with different parameters. All pieces of information necessary to run the experiment (e.g., software, experiment description, inputs, outputs, etc.) are bundled together in templates.

Templates are both persistent and versioned, allowing experimenters to move through the history of the experiment and make comparisons. Therefore, the mentioned features facilitate the replay of experiments, reducing the burden on the user. Data management is provided by the underlying infrastructure of Emulab, enabling Workbench to automatically collect logs that were generated during the experiment.

Plush/Gush

Plush, and its another incarnation called Gush, cope with the deployment, maintenance and failure management of different kinds of applications or services running on PlanetLab. The description of the application or services to be controlled is done using XML. This description comprehends the acquisition of resources, software to be installed on the nodes and the workflow of the execution. It has a lightweight client-server architecture with a few dependencies that can be easily deployed on a mix of normal clusters and GENI control frameworks: PlanetLab, ORCA 5 and ProtoGENI 6 . One of the most important features of Plush is its capacity to manage failures. The server receives a constant stream of information from all the client machines involved in the experiment and performs corrective actions when a failure occurs.

Expo

Expo offers abstractions for describing experiments, enabling users to express complex scenarios. These abstractions can be mapped to the hierarchy of the platform or can interface underlying tools, providing efficient execution of experiments. Expo brings the following improvements to the experimentation activity: it makes the description of the experiment easier and more readable, automates the experimentation process, and manages experiments on a large set of nodes.

OMF

It is a framework used in different wireless testbeds around the world and also in PlanetLab. Its architecture versatility aims at federation of testbeds. It was mainly conceived for testing network protocols and algorithms in wireless infrastructures. The OMF architecture consists of 3 logical planes: Control, Measurement, and Management. Those planes provide users with tools to develop, orchestrate, instrument and collect results as well as tools to interact with the testbed services. For describing the experiment, it uses a comprehensive domain specific language based on Ruby to provide experiment-specific commands and statements.

NEPI

NEPI is a Python library that enables one to run experiments for testing distributed applications on different testbeds (e.g., PlanetLab, OMF wireless testbeds, network simulator, etc). It provides a simple way for managing the whole experiment life cycle (i.e., deployment, control and results collection). One important feature of NEPI is that it enables to use resources from different platforms at the same time in a single experiment. NEPI abstracts applications and computational equipment as resources that can be connected, interrogated and conditions can be registered in order to specify workflow dependencies between them.

XPFlow

XPFlow is an experimentation tool that employs business workflows in order to model and run experiments as control flows. XPFlow serves as a workflow engine that uses a domainspecific language to build complex processes (experiments) from smaller, independent tasks called activities. This representation is claimed to bring useful features of Business Process Modeling (BPM), that is: easier understanding of the process, expressiveness, modularity, builtin monitoring of the experiment, and reliability.

Both XPFlow and scientific workflow systems rely on workflows. However, scientific workflows are data-oriented and the distributed system underneath (e.g., a computational grid) is merely a tool to efficiently process data, not an object of a study. Moreover, the formalism of XPFlow is inspired by workflow patterns identified in the domain of BPM, which are used to model control flows, as opposed to data flows (see Section 4.10.2).

Execo

Execo is a generic toolkit for scripting, conducting and controlling large-scale experiments in any computing platform. Execo provides different abstractions for managing local and remote processes as well as files. The engine provides functionality to track the experiment execution and offers features such as parameter sweep over a defined set of values. The partial results of the parameter sweep can be saved to persistent storage, therefore avoiding unnecessary reruns in case of a failure.

Tools not covered in the study

In the following section, we discuss other tools that could be mistaken as an experiment management tool according to our definition. They either contradict the definition (cf. Section 4.10.1) or support only subset of all activities required by it (cf. Section 4.10.4). The latter ones are sometimes used by experiment management tools to implement features presented in Section 3.

Non general-purpose experiment management tools

Tools like ZENTURIO [START_REF] Prodan | On using ZENTURIO for performance and parameter studies on cluster and Grid architectures[END_REF] and Nimrod [START_REF] Abramson | Parameter Exploration in Science and Engineering Using Many-Task Computing[END_REF] help experimenters to manage the execution of parameter studies on cluster and Grid infrastructures. Both tools cover activities like the set up of the infrastructure to use, collection and analysis of results. ZENTURIO offers a more generic parametrization, making it suitable for studying parallel applications under different scenarios where different parameters can be changed (e.g., application input, number of nodes, type of network interconnection, etc.). Even though Nimrod parametrization is restricted to application input files, a relevant feature is the automation of the design of fractional factorial experiments. NXE [START_REF] Guillier | A User-oriented Test Suite for Transport Protocols Comparison in Datagrid Context[END_REF] scripts the execution of several steps of the experimental workflow from the reservation of resources in a specific platform to the analysis of collected logs. The whole experiment scenario is described using XML which is composed of three parts: topology, configuration and scenario. All the interactions with resources and applications are wrapped using bash scripts. NXE is mainly dedicated to the evaluation of network protocols.

The aforementioned tools were not included in our analysis, because there are not generalpurpose experiment management tools. They address only very specific scenarios of experimentation with a distributed system like parameter studies and network protocols evaluation.

Scientific workflow systems

The aim of scientific workflow systems is automation of the scientific process that a scientist may go through to get publishable results from raw data. The main objective is to communicate analytical procedures repeatedly with minimal effort, enabling the collaboration on conducting large, data-processing, scientific experiments. Scientific workflows are designed specifically to compose and execute a series of computational or data manipulation steps. Normally, those systems are provided with GUIs that enable non-expert users to easily construct their applications as a visual graph. Goals such as data provenance and experiment repeatability are both shared by scientific workflows and experimentation tools. Some examples of scientific workflows are: Kepler [START_REF] Ludäscher | Scientific workflow management and the Kepler system[END_REF], Taverna [START_REF] Hull | Taverna: a tool for building and running workflows of services[END_REF] and Vistrails [START_REF] Callahan | VisTrails: visualization meets data management[END_REF]. An interesting analysis of these systems, and a motivation for this work, is presented in [START_REF] Yu | A Taxonomy of Scientific Workflow Systems for Grid Computing[END_REF].

There are two main reasons why scientific workflows are not covered in our study. First, scientific workflows are data flows in nature-they are used to run complex computations on data, while the computational platform is abstracted and the user has no direct control over it (e.g., the nodes used during computation). Hence the platform is not the object of study, but merely a tool to carry out computation. Second, the declarative representation of many scientific workflows as acyclic graphs is generally limited in its expressiveness, therefore they do not meet the criteria of general-purpose experimentation tools according to our definition (see [START_REF] Deelman | Workflows and e-Science: An overview of workflow system features and capabilities[END_REF][START_REF] Curcin | Scientific workflow systems -can one size fit all?[END_REF] for analyses of scientific workflows expressiveness).

Simulators and abstract frameworks

An approach widely used for evaluating and experimenting with distributed systems is simulation. In [START_REF] Naicken | The State of Peer-to-peer Simulators and Simulations[END_REF] the most used simulators for overlay networks and peer-to-peer applications are presented. Another framework called SimGrid [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF] is used for the evaluation of algorithms, heuristics and even real MPI applications in distributed systems such as Grid, Cloud or P2P systems.

Even though simulators provide many features required by the definition of the experimentation tool, they are not included in our study. First, they do not help with experiments on real platforms as they provide an abstract and modeled platform instead. Second, the goals of simulators are often very specific to a particular research subdomain and hence are not general-purpose tools [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF].

Other tools such as Splay [START_REF] Leonini | SPLAY: distributed systems evaluation made simple (or how to turn ideas into live systems in a breeze)[END_REF] and ProtoPeer [START_REF] Galuba | ProtoPeer: A P2P Toolkit Bridging the Gap Between Simulation and Live Deployement[END_REF] go one step further by making easy the transition between simulation and real deployment. Both tools provide a framework to write distributed applications based on a model of the target platform. They are equipped with measurement infrastructures and event injection for reproducing the dynamics of a live system.

The tools providing abstract framework to write applications under experimentation are not considered in our study, because real applications cannot be evaluated with them. Although real machines may be used to run experiments (as it is the case with Splay), the applications must be ported to APIs provided by these tools. viding unambiguous, declarative description of a desired system state and then carrying out necessary steps to reach it. Operating at even higher level are orchestration management tools, like Juju9 , which are designed to coordinate complex systems in flexible and reactive ways, usually in the cloud computing context. All these tools do not fulfill the definition of the experiment management tool. First, they are not general-purpose since no precise control over the execution is available (which is actually the goal of these tools). Second, the collection of results is not present.

Tools capturing experimental context

As mentioned in Section 2.2.3 one important feature required given the complexity of software nowadays, is the capture of the experimental context, undoubtedly useful for the reproduction of an experiment. Experimenters can take advantage of version control systems (e.g., Git, Subversion) or more sophisticated frameworks like Sumatra [START_REF] Davison | Automated Capture of Experiment Context for Easier Reproducibility in Computational Research[END_REF] which aim at recording and tracking the scientific context in which a given experiment was performed.

These tools are not experiment management tools according to our definition, of course, yet their use is convenient to document history of any software project, including experiment description and results. Some tools use them as a building block to store experimental context (cf. Section 4.3).

Discussion

Existing tools for experiment control were analyzed and evaluated using our set of features defined in Section 3 and the final results are presented in Table 1. For each position in the table (i.e., each property/tool pair) we sought for an evidence to support possible values of a given property in a given tool from a perspective of a prospective user. To this end, the publications, documentation, tutorials and other on-line resources related to the given approach were consulted. If presence of the property (or lack thereof) could be clearly shown from these observations, the final value in the table reflects this fact. However, if we could not find any mention of the feature, then the final value claims that the feature does not exist in the tool, as for all practical purposes the prospective user would not be aware of this feature, even if it existed. In ambiguous cases additional comments were provided. Much more detailed analysis that led to this concise summary is available on-line 10 . Using information collected in the table, one can easily draw few conclusions.

There is no agreement whether a declarative description is more beneficial than an imperative one. Declarative descriptions seem to be associated with higher modularity and expressiveness, but at a price of a higher entry barrier. Moreover, the tools tend to be independent of a particular testbed, but those with tight integration offer a more complete set of features or features not present in other solutions (e.g., Emulab Workbench).

The majority of addressed features come from Architecture (70%), Description Language (67%), Debugging (63%) and Interoperability (61%) groups. On the other hand, support for Fault Tolerance and Monitoring is quite low (44% and 37%, respectively), whereas support for Reproducibility is almost nonexistent (only 15%). The features available in majority of the analyzed tools are: Testbed independence (8/9), Expressiveness (7/9), Low entry barrier (7/9), Support for testbed services (7/9), Interactive execution (7/9), Failure handling (6/9), Logging (6/9), Resource discovery (5/9), File management (5/9) and Provisioning (5/9). Moreover, the tools have nearly universally Simple installation (7/9), Low resource requirements (6/9) and offer methods to perform Efficient operations (6/9). The two most unimplemented features are Provenance tracking (1/9) and Workload generation (1/9), both crucial for reproducibility of experiments.

Additionally, some tools offer unique features: Software interoperability (Plush and OMF), Provenance tracking (Workbench), Fault injection (Weevil and OMF), Workload generation (Weevil), Verification of configuration (Workbench and OMF) and Instrumentation (Plush and OMF). However, it is worth pointing out that features such as Workload generation are often provided by standalone tools.

Finally, we did a simple "impact analysis" of described tools by summing all unique scientific citations to papers about each tool using Google Scholar (see Table 2). Clearly, without adjusting the score to the age of each tool, the most cited tool is Plush. As interesting as these data may be, we abstain from drawing any more conclusions from them. The summary of this analysis is available on-line11 .

Conclusions

In this paper, we presented an extensive list of properties expected from general-purpose experiment management tools for distributed systems on real platforms. The diversity of the research domain of distributed systems motivated development of different techniques and tools to control experiments, and explains the multitude of approaches to manage experiments. With the construction of the feature list, we tried to establish a common vocabulary in order to understand and compare the existing experiment management tools.

The size and complexity of distributed systems nowadays have uncovered new concerns and needs in the experimentation process. We need to control an always increasing number of variables to assure two important characteristics of an experiment, its reproducibility and replicability. With the motivation of providing a controlled environment to execute experiments in the domain of distributed systems, several testbeds were created which stimulated the development of different experiment management tools. Among the benefits of experiment management tools are: encouraging researchers to experiment more and improve their results, educational value of being able to play with known algorithms and protocols under real settings, reduction of the time required to perform an evaluation and publish results, capacity to experiment with many nodes and complex scenarios, different software layers, topologies, workloads, etc.

Despite the emergence of experiment management tools, some of them are in an immature state of development which prevents them from fully exploiting the capacity of certain testbeds. There is indeed, a lot of challenges in the domain of experimentation and the need of further development of those tools is apparent. To achieve this, technologies developed with different purposes could arguably be used in the experimentation process. For instance, we mentioned that workflow systems and configuration management tools share some concerns and goals with the problem of experimenting with distributed systems.

Finally, a deeper understanding of the experimentation process with distributed systems is needed to identify novel ways to perfect the quality of experiments and give researchers the possibility to build on each others' results.

  The tree of features. All evaluated properties and features are presented with their respective domains of values.

		Representation	Imperative / Declarative
	Description		/ Workflow / Scripts
	Language	Modularity	Yes / No
		Expressiveness	Yes / No
		Low entry barrier	Yes / No
	Type of Experiments	Platform type	Real / Model
		Intended use	Distributed applications
			/ Wireless / Services / Any
		Testbed independence	Yes / No
	Interoperability	Support for testbed services	Yes / No
		Resource discovery	Yes / No
		Software interoperability	Yes / No
		Provenance tracking	Yes / No
	Reproducibility	Fault injection	Yes / No
		Workload generation	Yes / No
	Fault	Checkpointing	Yes / No
	Tolerance	Failure handling	Yes / No
		Verification of configuration	Yes / No
		Interactive execution	Yes / No
	Debugging	Logging	Yes / No
		Validation	Yes / No
		Experiment monitoring	Yes / No
	Monitoring	Platform monitoring	Yes / No
		Instrumentation	Yes / No
	Data	Provisioning	Yes / No
	Management	File management	Yes / No
		Analysis of results	Yes / No
		Control structure	Centralized / Distributed
		Low resource requirements	Yes / No
	Architecture	Simple installation	Yes / No
		Efficient operations	Yes / No
		Interface	CLI / GUI / API
	Figure 1:

Table 2 :

 2 4.10.4. Configuration and orchestration management softwarePuppet7 and Chef 8 are commonly used in automating administrative tasks such as software provision and configuration of operating systems. They simplify complex deployments by pro-Number of publications citing papers dedicated to each experimentation tool (as verified on 4 July 2014).

	Tool	First publication Citations
	Weevil	2005	69
	Workbench	2006	80
	Plush/Gush	2006	177
	Expo	2007	16
	OMF	2009	152
	NEPI	2010	38
	XPFlow	2012	3
	Execo	2013	1

http://www.cs.vu.nl/das4/

http://aws.amazon.com/ec2/

http://www.windowsazure.com/

http://www.openstack.org/

http://groups.geni.net/geni/wiki/ORCABEN

http://www.protogeni.net

https://puppetlabs.com/

http://www.opscode.com/chef/

https://juju.ubuntu.com/

http://www.loria.fr/ ~buchert/exp-survey.yaml

http://www.loria.fr/ ~buchert/exp-impact.yaml

Yes Yes Failure handling (6/9) No Yes No Yes No Yes Yes Yes Yes Verification of configuration (2/9) No No Yes ⋆ No No Yes No No No Debugging (17/27 ≈ 63%) Interactive execution (7/9) Yes No Yes Yes Yes Yes Yes No Yes Logging (6/9) No No Yes ⋆ No Yes Yes Yes Yes Yes Validation (4/9) No Yes Yes No No No Yes Yes No Monitoring (10/27 ≈ 37%) Experiment monitoring (4/9) No No Yes No No Yes Yes Yes No Platform monitoring (4/9) No No Yes ⋆ Yes No Yes Yes No No Instrumentation (2/9) No No No Yes No Yes No No No Data Management (13/27 ≈ 48%) Provisioning (5/9) No Yes Yes ⋆ Yes No Yes Yes No No File management (5/9) No Yes Yes Yes No Yes No No Yes Analysis of results (3/9) No No Yes No No Yes No Yes No


Francesca Bugiotti
email: francesca.bugiotti@inria.fr

Damian Bursztyn
email: damian.bursztyn@inria.fr

Alin Deutsch

Ioana Ileana
email: ioana.ileana@telecom-paristech.fr

Ioana Manolescu
email: ioana.manolescu@inria.fr

Invisible Glue: Scalable Self-Tuning Multi-Stores

Next-generation data centric applications often involve diverse datasets, some very large while others may be of moderate size, some highly structured (e.g., relations) while others may have more complex structure (e.g., graphs) or little structure (e.g., text or log data). Facing them is a variety of storage systems, each of which can host some of the datasets (possibly after some data migration), but none of which is likely to be best for all, at all times. Deploying and efficiently running data-centric applications in such a complex setting is very challenging.

We propose Estocada, an architecture for efficiently handling highly heterogeneous datasets based on a dynamic set of potentially very different data stores. Estocada provides to the application/programming layer access to each data set in its native format, while hosting them internally in a set of potentially overlapping fragments, possibly distributing (fragments of ) each dataset across heterogeneous stores. Given workload information, Estocada self-tunes for performance, i.e., it automatically choses the fragments of each data set to be deployed in each store so as to optimize performance. At the core of Estocada lie powerful view-based rewriting and view selection algorithms, required in order to correctly handle the features (nesting, keys, constraints etc.) of the diverse data models involved, and thus to marry correctness with high performance.

CONTEXT AND OUTLINE

Digital data is being produced at a fast pace and has become central to daily life in modern societies. Data is being produced and consumed in many data models, some of which may be structured (flat and nested relations, tree models such as JSON, graphs such as those encoding RDF data or social networks) and some of which may be less so (e.g., CSV or flat text files). Each of the data types above arises in application scenarios including traditional data warehousing, e-commerce, social network data analy-sis, Semantic Web data management, data analytics, etc.

It is increasingly the case that an application's needs can no longer be met within a single dataset or even within a single data model. Consider for instance a traditional customer relationship management (CRM) application. While typically CRM needed to deal only with a relational data warehouse, now the application needs to incorporate new data sources in order to build a better knowledge of its customers: (i) information gleaned from social network graphs about clients' activity and interests, and (ii) log file from multiple e-commerce stores, characterizing the clients' purchase activity in those stores. Monetizing access to operational databases is predicted to grow 1 , thus access to such third-party data sources is increasing.

The in-house RDBMS performs just fine on the relational data. However, the social graph data fits badly in that system, and the company attempts to store it in a dedicated graph store, until an engineer argues that it should be decomposed and stored into a highly-efficient NoSQL key-value store system she has just experimented with. The storage and processing of log files is delegated to a Hive installation (over Hadoop), until the summer research intern observes that recent work [START_REF] Lefevre | MISO: souping up big data query processing with a multistore system[END_REF] has shown that some data from Hive should be lifted at runtime in the relational data warehouse to gain a few orders of magnitude of performance! Deploying and exploiting the CRM application for best performance is set to be a nightmare now. There is little consensus on what systems to use, if any; three successive engineers have recommended (and moved the social data into and out of) three different stores, one for graphs, one for key-value pairs, and the last an in-memory column database. Part of the log data has been moved in the inmemory column store, too, when the social data was stored there; this made their joint exploitation faster. But the whole log dataset could not fit in the single-node column store installation, and data migration fatigue had settled in before a suggestion was made (and rejected) to move everything to yet another cluster installation of the column store. The team working on the application feels battered and confused. The application is sometimes very slow. Migrating data is painful at every change of system; they are not sure the complete data set survived at each step, and data keeps accumulating. Yet, a new system may be touted as the most efficient for graph (or for log) data next week. How are they to tell the manager that no, they are not going to migrate the application to that system? What, if any, part of the data to deploy there? Would it be faster? Who knows?

In this work, we present Estocada, a platform we have started building, to help deploy and self-tune for performance applications having to deal with mixed-model data, relying on a dynamic set of diverse, heterogeneous data stores. While heterogeneous data integration is an old topic [START_REF] Levy | Querying Heterogeneous Information Sources Using Source Descriptions[END_REF][START_REF] Halevy | Answering Queries Using Views: A Survey[END_REF][START_REF] Deutsch | MARS: A System for Publishing XML from Mixed and Redundant Storage[END_REF][START_REF] Manolescu | Answering XML queries on heterogeneous data sources[END_REF], the remark "one-size does not fit all" [START_REF] Stonebraker | One Size Fits All": An Idea Whose Time Has Come and Gone[END_REF] has been revisited for instance in the last CIDR [START_REF] Lim | How to Fit when No One Size Fits[END_REF][START_REF] Jindal | WWHow! Freeing Data Storage from Cages[END_REF][START_REF] Dittrich | Say No! No! and No! In CIDR[END_REF], and the performance advantages brought by multi-stores have been recently noted e.g., in [START_REF] Lefevre | MISO: souping up big data query processing with a multistore system[END_REF]. Self-tuning stores have also been a topic of hot research. The set of features which, together, make Estocada novel are:

Natively multi-model Estocada supports a variety of data models, including flat and nested relations, trees and graphs, including important classes of semantic constraints such as primary and foreign keys, inclusion constraints, redundancy of information within and across distinct storage formats, etc. which are needed to enforce application semantics.

Application-invisible Estocada provides to client applications access to each dataset in its native format. This does not preclude other mapping / translation logic above Estocada' client API but we do not discuss them in this paper. Instead, our focus is on efficiently storing the data, even if in a very different format from its original one, as discussed below.

Fragment-based store Each data set is stored as a set of fragments, whose content may overlap. The fragmentation is completely transparent to Estocada' clients, i.e., it is the system's task to answer queries based on the available fragments.

Mixed store Each fragment may be stored in any of the stores underlying a Estocada installation, be it relational, tree-or graph-structured, based on key-value pairs etc., centralized or distributed, disk-or memorybased etc. Query answering must be aware of the constraints introduced implicitly when storing fragments in non-native models. For instance, when tree-structured data are stored in a relational store, the resulting edge relation satisfies the constraint that each node has at most one parent, the descendant and ancestor relations are inverses of each other and are related nontrivially to the edge relation, etc.

Self-tuning store The choice of fragments and their placement is fully automatic. It is based on a combination of heuristics and cost-based decisions, taking into account data access patterns (through queries or simpler data access requests) as these become available.

View-based rewriting and view selection

The invisible glue holding all the pieces together is view-based rewriting with constraints. Specifically, each data fragment is internally described as a materialized view over one or several datasets; query answering amounts to viewbased query rewriting, and storage tuning relies on view selection. Describing the stored fragments as views over the data allows changing the set of stores with no impact on Estocada' applications [START_REF] Halevy | Answering Queries Using Views: A Survey[END_REF]; this simplifies the migration nightmare outlined above. Finally, our reliance on views gives sound foundation to efficiency, as it guarantees the complete storage of data, and the correctness of the fragmentation and query answering, among others.

Technical challenges

The Estocada scenario involves the coexistence of a large number of materialized views mixing data formats (modeling the native sources) with significant redundancy between them (due to repeated migration and view selection arising organically over the history of the system, as opposed to clean-slate planning). While the problem of rewriting using views is classical, it has typically been addressed and practically implemented only in limited scenarios that do not apply here. These scenarios feature (i) only relatively small numbers of views; (ii) minimal overlap between views as their selection is planned ahead of time;

(iii) views expressed over the same data model; (iv) rewriting that exploits only limited integrity constraints (typically only key/foreign key in existing systems). The large number of views and their redundancy notoriously contribute (at least) exponentially to the explosion in the search space for rewritings, even when working within a single data model.

In the sequel, we introduce some motivating scenarios, present Estocada's architecture, and walk the reader through the main technical elements of our solution, by means of an example. Finally, we discuss related works, then conclude.

APPLICATION SCENARIOS

We now present two typical scenarios which stand to benefit from our proposal. They are inspired from real-world applications being built by several partners including us, within the French R&D project Datalyse on Big Data analytics. (http://www.datalyse.fr).

Open Data warehousing for Digital Cities. The application is based on Open Data published and shared in a digital city context. The purpose is to predict the traffic flow and the consequent customer behavior taking into account information about events that influence people behavior such as city events (e.g., celebrations, demonstrations, or a highly attended show or football match), weather forecasts (bad weather often leading to traffic slowdown), etc. The analysis is performed in a metropolitan area of a 600.000strong French city. The data used in the project comes from city administrations, public services (e.g., weather and traffic data), companies, and individuals in the area, through Web-based and mobile applications; the sources are heterogeneous, comprising RDF, relational, JSON and key-value data. More precisely, (i) Open data about traffic and events is encoded in RDF; (ii) city events information is published as JSON documents; (iii) social media data holding users' locations, as well as their notifications of public transport events (such as delayed buses or regional trains) is organized in key-value pairs; (iv) weather data is generated as relational tuples.

The application comprises the following queries:

• Estimated concentration of people and vehicles in a particular area and moment. One use of such information is to plan some corrective/preventive measures, for instance diverting traffic from an overcrowded area; it can also be used to identify business opportunities according to where people are. This query requires: traffic information, social events, social network information, the weather (open space events may be cancelled depending on the weather) and public transport information.

• Most popular trajectories in the area which can be used to optimize public transport or car traffic routes. This needs traffic information, social network data on traffic events, and public transportation timetables.

Large-scale e-commerce application. We consider a scenario from a large-scale e-commerce application whose goal is to maximize sales while improving the customer experience. A large retailer wants to use the clients' social network activity with the e-commerce application logs, to improve targeted product recommendation. This requires exploiting the data produced by the users both actively (orders, product reviews, etc.) and passively (logs), as well as social network data.

The heterogeneous sources of information in this scenario are: (i) shopping cart data stored in key-value pairs; (ii) the product catalog, structured in documents using a data store with full-text search, faceted search and filtering capabilities; (iii) orders, stored in a relational data store; (iv) user data (such as birth date, gender, interests, delivery addresses, preferences, etc.) organized in documents; (v) products reviews and ratings, structured in a partitioned row store, and (vi) social network data organized in key-value pairs. The queries in this scenario:

• Retrieve items to recommend to each user, by displaying them on the user homepage and inside bars while the user is shopping. This requires combining cart information, the product catalog, past relational sale data, personal user data, product reviews, and possible recommendations gleaned from the social network.

• Improve product search: this requires attribute-based search in the product catalog, as well as user's recent search and purchase history to decide which products to return at the top of the search result.

This application uses massive data (the sale history of many users), yet response time is critical, because query answers must be made available in the user's Web interface. To get such performance, the engineers in charge of the application have decided to use memcached [START_REF]Memcached distributed memory object caching system[END_REF] to make access to parts of the database very fast. However, automatically deciding which parts to put in memcached, and correctly computing results out of memcached and the other external sources is challenging, especially given the heterogeneity of the data representation formats.

ARCHITECTURE

The architecture we envision is depicted in Figure 1. Data centric applications issue two types of requests to Estocada: storing data, and querying, or, more generally, issuing data access requests, through each data set's native query language or API2 As previously mentioned, we mostly target applications based on many data sets D1, D2, . . . , Dn, even though our smart storage method may be helpful even for a single data set, distributing it for efficient access across many stores, potentially based on different data models. The Storage Advisor module is in charge of splitting each data set into possibly overlapping fragments D1/F1, D1/F2, . . ., D1/Fn, D2/F1, . . ., etc., and delegating their storage to one of the underlying data management systems. In the figure, this is illustrated by a NoSQL store, a key-value store, a document store, one for nested relations, and finally a relational one. Several among the available stores could be based on the same data model; each of them may be distributed or centralized, memory-or disk-resident, etc.

The data set fragmentation decisions are taken based on (i) information about the workload of data access requests, to be issued by the applications. This may comprise exact data access requests, or parameterized ones, where the values of some parameters (typically constants used in a selection) are not statically known but represented by a parameter; (ii) a set of heuristics driven by the data models of the dataset Di, and of the store S k holding Di/Fj. The fragment can thus be seen as a materialized view over Di. The where part of the descriptor is structured according to the organization of data within S k . For instance, if S k is a relational store, the where information consists of the schema and table name, whereas if S k is a key-value store, it could hold the name of the collection, the attribute name, etc.Finally, the descriptor sd(S k , Di/Fj) also specifies the data access operation supported by S k which allows retrieving the Di/Fj data (such as: a table scan, a look-up based on a collection name, column group name, and column name in a key-value store, etc.), as well as the access credentials required in order to connect to the system and access it.

The Storage Descriptor Manager (SDM, in short) keeps the catalog of the available storage fragments, that is the set of the current storage descriptors. The SDM also records some cost information C sd for each storage descriptor sd, characterizing the processing costs involved in accessing the fragment Di/Fj through the data access operation encoded in sd. The cost information can be gathered explicitly using the tools provided by the storage system S k , and/or inferred by Estocada dynamically over time by monitoring execution and refining the values of its own cost model. For instance, the cost associated to a descriptor sd referring to a full collection (or table) scan will be different from the one describing an index-(or key-based) lookup access.

The SDM also records the usage frequency (and cost) of each storage descriptor. Based on this information, the Storage Advisor may recommend dropping a fragment rarely used over a period of time and/or slow-performing, or ask for adding a new fragment which fits recent, frequent data access requests. Observe that this reorganization of storage, under the control of the Storage Advisor, spans over all the data stores. Thus, a particular case of data reorganization is moving a fragment Di/Fj from one store to another.

The Query Evaluator receives queries (or data access requests) issued by the application, in the original language (model) of a data source Di. To handle them, the evaluator looks up the storage descriptors corresponding to fragments of Di, and computes ways to answer the incoming request based on the available fragments; thus, the evaluator rewrites the data access requests using the materialized views (or fragments). The evaluator then selects one among these rewritings considered to have the best performance, let us denote it r(sd1, sd2, . . . , sd k ), where each sdi is a storage descriptor representing a fragment within the storage system Si, and hands it to the runtime component (see below).

The Runtime Execution Engine translates a rewriting (essentially a logical plan joining the results of various data access operations on the store) into a physical plan which can be directly executed by dividing the work between (i) the stores S1, . . . , S k and (ii) Estocada's own runtime engine, which supplies implementations of physical operators such as select, join, etc. While in classical mediator style, the runtime of Estocada can be used to combine data across different stores, we stress that this may be needed even for two fragments within the same store, if the store does not support joins internally; this is the case, for instance, of current key-value stores not providing native joins. Evaluating the physical plan returns results to the client application.

From the above description, it is easy to see that Estocada resembles wrapper-mediator systems, where data resides in various stores and query execution is divided between the mediator and the wrappers. Different from mediators, however, Estocada distributes the data across the different-data model stores, which are not autonomous but treated as slave systems, in order to obtain the best possible performance from the available combination of systems.

UNDER THE HOOD

Estocada aims at efficiently managing several datasets across a set of heterogeneous stores. In this section, based on a toy example inspired from our Digital City Open Data Warehousing scenario, we provide some details of the main issues raised by our approach: (i) uniformly describing data fragments stored in the heterogeneous stores we consider, by means of storage descriptors; (ii) view-based query rewriting to identify the best storage data fragments to be used in order to answer a data access request; (iii) storage tuning that moves data across systems and/or builds new data access structures for performance.

Dataset fragment representation

We assume a first dataset D of structured documents, such as XML, JSON etc., storing public transport information for the whole city area. The dataset is fragmented across three systems, as follows: a MongoDB document store holds tram and metro information; bus routes reside in a Redis keyvalue store, while RER and metro routes are stored within PostgreSQL. In the following, we discuss details of these fragments' storage, illustrating the expressive power of their storage descriptors. MongoDB fragment Fragment F1 comprises trams and metros, stored in a MongoDB collection named trams_metros. Each line is modeled as a document. A document contains the line name and the route, that is, the names of all the stops; the latter are stored as an array reflecting their order. Thus, the "what" part of the storage descriptor sd1 corresponding to F1 is the query: D/trams/tram ∪ D/metros/metro expressed in a simple XPath-like syntax that we shall use throughout this section. In practice, such view-defining queries are written in the native language of the dataset D. To access the data, MongoDB provides the find operation that, given a station name s, retrieves the documents describing all the lines whose route includes s: db.trams_metros.find( { route: s } )

In the above, route: s encodes the constraint that the station s appears in the metro or tram route. Thus, the "how" part of sd1 is depicted in the following figure, where the b superscript reflects that the value of that node must be provided (the node is said to be bound), while f denotes the node(s) whose content is obtained by the respective access method, and which are said free [START_REF] Rajaraman | Answering queries using templates with binding patterns[END_REF]. The above example illustrates a valuable feature of the how storage descriptor component, namely binding patterns. These are very useful especially when describing access methods supported by efficient current-day stores, such as keyvalue stores or document stores providing built-in search functionality, as MongoDB in the above example. Other lower-level information typically found in the how part includes the name of the database db, access credentials to the database, etc.

The final component of sd1 is a cost function C1 which, given a station name s1, estimates the cost of retrieving from MongoDB all the lines passing through station s1. This may be estimated once for all stations, or be stored at a finer granularity (different values for distinct s1 bindings), etc.

Redis fragments comprise bus information. The data can be accessed in two different ways (the "how" part), leading to two storage descriptors: sd 1 2 and sd 2 2 , as we explain next. First, the bus information is broken down into pairs of the form (s|n), where s denotes a station name and is used as a Redis key, whereas n is a bus line name stored as a value associated to s (Redis allows storing a set of values on a given key). Thus, the what part of sd 1 2 can be encoded by the query q 1 2 , describing F 1 2 as a materialized view over D:

for $b in D/buses/bus return ($b/name, $b/route/station)

As for the "how" part, F 1 2 data can be accessed by providing values for the station name, and receiving bus line names in return. This is represented by the left-hand tree with a binding pattern, in Figure 2. The same bus data is split again in a different way within Redis: using the bus line name n as a key, to which we associate a value for each station in the route, by appending the name of each station to its order along the route. The corresponding query q 2 2 is:

for $b in D/buses/bus, $s in $b/route/station return ($b/name as bname, $s/name as sname, $s/position())

where the position function is used to record in the (unordered) Redis store the position of each station along the route. As for the "how" part, in sd 2 2 the binding pattern is the one shown at right in Figure 2.

Cost descriptors C 1 2 , C 2 2 , and Redis access information (omitted here) complete the storage descriptors sd 1 2 and sd 2 2 . Postgres fragments Regional train and metro information is stored in Postgres, under the form of the following five tables (underlined attribute denote primary keys):

Train(rid, rname)
Metro (mid, mname) Tstat(rid, sid, pos) Mstat (mid, sid, pos)

Station(sid, sname)

The query defining the first relation as a view over D is: for $t in D/trains/train return ($t/id(), $t/name); the four other queries are similar and we omit them for brevity.

Regarding the "how" part of the storage, each table can be scanned, which is reflected by five storage descriptors sd 1 3 to sd 5 3 , one for each table, e.g., Train(tid f , tname f ). Further, assuming that an index exists on Station.sname, this is modeled by the storage descriptor sd 6 3 with the binding pattern Station(sid f , sname b ). The presence of indexes is one reason why we create a distinct fragment (and storage descriptor) for each binding pattern: the cost is likely to be very different for an indexed access through sd 6 3 , than by the respective scan-based descriptor sd 5 3 . The second reason is that each fragment is usable only when the values of the attributes bound in its binding pattern can be filled in (from the query or another already accessed fragment).

DFS fragments A second dataset D of social media notifications of public transport events is in a distributed file system (DFS). Events are partitioned in the DFS according to their date. Each event notification comprises the date, time, station, line, and a short description (e.g., delay on the line etc.). The data can be freely accessed through a (parallel) scan. We omit the query defining this fragment F4 and its (all-f ) binding pattern. Further, city events (such as concerts, public manifestations etc.) are also stored in the DFS, in two ways: partitioned by event type (fragment F 1 5 ) and by event date (fragment F 2 5 ). Fragments F4, F 1 5 , and F 2 5 illustrate a final feature of the "how" part of storage descriptors: if the data is partitioned, the SD records the partitioning attribute(s), in our case, date for F4 and F 2 5 and event type for F 1 5 . This information is extremely helpful during cost-based query rewriting (discussed below), as in large-scale distributed stores (e.g., based on MapReduce), joins which can be performed on common partitioning keys (for instance, join transport and city events on the date to find which city events lead to most transport disruption) are the most efficient [START_REF] Li | Distributed data management using MapReduce[END_REF].

View-based query rewriting

Following with our example, we consider an application query, shown in Figure 3, asking for all transportation paths going from station Cadet to station Villers with at most one connection. In Figure 3, val subscripts denote nodes to be returned by the query, while the dashed line denotes a join. Part of the answers to this query can be obtained by joining sd1 (accessed using the value "Cadet" for the bound station name) with itself (accessed a second time using the value "Villers"). The intersection of the results (routes) allows finding common (connection) stations, thus providing paths made of two trams, two metros, or one of each. To obtain tram-bus or metro-bus paths, one may join sd1 (accessed as above with "Cadet") with sd 1 2 for each station in the routes retrieved from sd1, to learn the lines on which the connecting station sits, and then with sd 1 2 again (accessed with "Villers"), to retain those bus lines that stop at Villers. An alternative way to obtain such paths consists in accessing sd 1 2 to learn the bus lines that stop at Villers, finding their routes by accessing sd 2 2 , and then further intersecting these with routes that pass through Cadet, as retrieved from sd1. Further, joining sd1 (accessed with "Cadet") with sd 1 3 , sd 3 3 , and sd 5 3 and then selecting on "Villers" provides tram-train and metro-train paths. The same paths can be obtained by rather employing the more efficient sd 6 3 . Metro-train or metro-metro paths can also be obtained by solely relying on the corresponding Postgres fragments, etc.

Combining such partial answers through unions leads to a large number of (equivalent) rewritings of the query; the one with the least estimated cost is selected for execution.

Thus, query answering in Estocada reduces to a problem of cost-based query reformulation under constraints. First, all view definitions ("what" part of the storage descrip- tors) are compiled into an internal, conjunctive query model with constraints. The constraints are (i) application-driven, i.e., those holding on the original dataset, or (ii) inserted by the translation to correctly account for the structural characteristics of the original data model. For instance, if data was originally structured in documents, the relational queries defining the views must be interpreted together with constraints stating e.g., that each document node has only one parent, any child node is also a descendant, etc. Costbased reformulation under constraints of this expressivity and scale has not been addressed by any commercial system; the only relevant research prototype we are aware of is [START_REF] Ileana | Complete yet practical search for minimal query reformulations under constraints[END_REF], which we adopt as a starting point.

Unified Storage Tuning

Ultimately, Estocada aims at making applications efficient by providing storage structures best adapted to the workload, based on any of the available stores. In our example, the storage advisor may recommend to move the metro data into Redis due the lower access costs and the application high demand for metro routes. If sd1 is accessed multiple times using the station name, it can recommend an index on station names within MongoDB. If our sample query is run many times with different starting and ending stations, the storage advisor can recommend to materialize in a key-value store a view (asking for all the possible paths from one station to another with at most one change), with the name of the start station, for instance, as key.

The problem of automatic storage tuning, or cost-based, workload-driven index/materialized view recommendation, is long-known to be difficult due to the huge space of alternatives. So far, the problem has been studied for simpler situations when the views and the stores share the same data model. Heuristics such as avoiding views computable from others, or pruning candidate views based on the estimated costs of rewriting have been shown useful [START_REF] Katsifodimos | Materialized view selection for XQuery workloads[END_REF], as well as linear programming techniques to efficiently search through the alternatives [START_REF] Dash | Cophy: A scalable, portable, and interactive index advisor for large workloads[END_REF]. In our setting, the choice of a store for a candidate view (fragment) also complicates the search: while there are more alternatives, all do not make sense, as some views (identified by queries in our internal language) may not be valid structures to build within some stores.

RELATED WORK

The interest of simultaneously using multiple data stores has previously been noted in [START_REF] Lim | How to Fit when No One Size Fits[END_REF][START_REF] Dittrich | Say No! No! and No! In CIDR[END_REF][START_REF] Jindal | WWHow! Freeing Data Storage from Cages[END_REF]. In this paper, we propose a storage approach that allows and optimizes the simultaneous use of multiple data stores. Recent work also demonstrated the performance benefits of using two heterogeneous systems, in particular by materializing workloaddriven views into the most efficient among the two [START_REF] Lefevre | MISO: souping up big data query processing with a multistore system[END_REF][START_REF] Lefevre | Opportunistic physical design for big data analytics[END_REF]. Our approach is more general, since Estocada can take ad-vantage of any number of storage systems, based on a variety of data models; this is supported by its central algorithm for query reformulation under constraints.

Our work shares some features of classic data integration or mediator systems, by dividing query processing between underlying stores and a runtime integration component running on top of them; recently, the integration of so-called "NoSQL" stores has been revisited e.g., in [START_REF] Atzeni | Uniform access to NoSQL systems[END_REF]. However, the automatic cross-model, cross-system storage tuning problem we consider has not been studied in mediator systems.

Adaptive stores have been the focus of many works such as [START_REF] Idreos | Database Cracking[END_REF][START_REF] Alagiannis | H2O: a hands-free adaptive store[END_REF][START_REF] Dash | Cophy: A scalable, portable, and interactive index advisor for large workloads[END_REF][START_REF] Katsifodimos | Materialized view selection for XQuery workloads[END_REF]. The novelty of Estocada here is to support multiple data models, by relying on powerful query reformulation techniques under constraints.

View-based rewriting and view selection techniques are grounded in the seminal works [START_REF] Halevy | Answering Queries Using Views: A Survey[END_REF][START_REF] Levy | Querying Heterogeneous Information Sources Using Source Descriptions[END_REF]; the latter focuses on maximally contained rewritings, while we target exact query rewriting, which leads to very different algorithms. Further setting our work apart is the scale and usage of integrity constraints; our methodologies are similar to the ones described in [START_REF] Deutsch | MARS: A System for Publishing XML from Mixed and Redundant Storage[END_REF][START_REF] Manolescu | Answering XML queries on heterogeneous data sources[END_REF] which did not consider storage tuning. Views are used in [START_REF] Shute | F1: A Distributed SQL Database That Scales[END_REF][START_REF] Agrawal | Asynchronous View Maintenance for VLSD Databases[END_REF] to improve the performance of a distributed relational system. In contrast, Estocada aims at introducing materialized views and indexes to get the best performance out of a heterogeneous data store, leading first, to integrity constraints for modeling such heterogeneity, and second, a potentially very large number of views. To achieve correctness and practically relevant performance in such setting, we start from complete and scalable algorithms for query reformulation under constraints, such as [START_REF] Ileana | Complete yet practical search for minimal query reformulations under constraints[END_REF], evolving them appropriately.

Finally, our approach shares some analogies with works in data exchange such as Clio [START_REF] Fagin | Data exchange: Semantics and query answering[END_REF][START_REF] Haas | Clio grows up: from research prototype to industrial tool[END_REF], allowing to migrate data between two schemas and to build completely defined mappings given a set of user-defined correspondences. In contrast, Estocada aims at providing to the applications transparent data access to heterogeneous systems, relying on fundamentally different rewriting techniques.

CONCLUSIONS

To conclude, we believe that hybrid (multi-store) systems can bring very significant boost to performance; further, such systems must accommodate dynamic sets of stores, and adapt to changing workloads. These two aspects lead to local-as-view integration and view-based rewriting as cornerstones of Estocada's approach; reformulation under constraints is required to guarantee correctly computed answers from a variety of stores. The implementation of Estocada is ongoing, building on [START_REF] Ileana | Complete yet practical search for minimal query reformulations under constraints[END_REF] and our experience in [START_REF] Katsifodimos | Materialized view selection for XQuery workloads[END_REF].

Figure 1 :

 1 Figure 1: Estocada architecture.

  For each data fragment Di/Fj residing in the store S k , a storage descriptor sd(S k , Di/Fj) is produced. The descriptor specifies what data (the fragment Di/Fj) is stored where within S k . The what part of the descriptor is specified by a query over the data set Di, following the native model of Di.

Figure 2 :

 2 Figure 2: Sample storage descriptor.

Figure 3 :

 3 Figure 3: Sample query.

As previously said, one could integrate on top of Estocada the various data sources under a common data model; this is out of the scope of the architecture we describe here.

Acknowledgments This work has been partially funded by the Datalyse "Investissement d'Avenir" project, by the as-sociated INRIA-Sillicon Valley OakSad team, and the KIC ICT Labs Europa activity.