Uras Tos

Riad Mokadem

Abdelkader Hameurlain

Tolga Ayav

Uras Tos, Riad Mokadem, Abdelkader Hameurlain, Tolga Ayav, and Sebnem Bora

I am sure there are many definitions of what a PhD is and what it entails along the lines of conducting independent research and pushing the boundaries of human knowledge. However, I can only attest to my perspective, as an individual who just went through the experience. Facing an immense problem and the emotional concern that comes attached, the feelings of the PhD candidate slowly turns into content as the problem is slowly chipped away with concentration, dedication and steady effort. For me, much like an athlete who pushes the limits of physical strength with repeated exercise, a PhD is a perpetual challenge to one's intellect for advancement.

The fulfillment of conquering a PhD-level problem is rare in a person's life. Being awarded an opportunity towards this goal is indubitably has the utmost importance.

For that reason, I am grateful to Institut de Recherche en Informatique de Toulouse (IRIT) and its director, Prof. Michel Daydé for accepting me as a PhD student.

The contribution of a thesis increases even more with external evaluation by veteran researchers of the relevant field. Hence, I thank to the reviewers Prof.

Esther Pacitti and Prof. Ali Yazıcı, and examiner Prof. Patrick Valduriez for their honest and valuable feedback on my work.

Working on a specialized problem for a long time enables a PhD candidate to gain in-depth knowledge of that field. However, it may also cause the PhD candidate to fall into the pitfall of getting lost along the way. Fortunately, I had the pleasure of working with four brilliant people to guide me during my PhD.

Prof. Abdelkader Hameurlain, with decades of experience under his belt, always shared his vision with me and reminded me not to miss the big picture while I obsessed with the details. Not just the knowledge of my field, but I also learned a great deal about life in academia from him and for that, I am grateful.

Dr. Tolga Ayav have always been a pleasure to work alongside, with his friendly attitude. He was also my advisor during my MSc and I probably would not have pursued an academic career wihout his encouragement. I am thankful to him for everything he has done for so many years.

I also thank Dr. Sebnem Bora for her positive attitude and appreciation of my efforts. She always had a way of showing her support with uplifting emotions.

Last but not least, I thank Dr. Riad Mokadem for his close support on every detail of my thesis. Not only an advisor, but he has also been a life saver in many dayto-day needs I had during my visits to France. I will certainly miss our discussions and I am honored to consider him as a friend.

I thank my colleagues at IRIT, Izmir Institute of Technology and Ege University for providing me a friendly workplace to conduct research. Also, I am grateful to The Scientific and Technological Research Council of Turkey (TÜBİTAK) for providing financial support during my studies. I am also offering my sincerest thanks to all my friends, especially Kamil and Mehmet for vesting their confidence in my success.

Lastly but most importantly, I am deeply grateful to my parents, Nurşen and Turan for having raised me as an individual who values science, reason and logic above all else for guiding me in life. Also my little sister Eda, who always been there for me no matter what. I owe them everything for what I am today.

Abstract Data replication in large-scale data management systems

In recent years, growing popularity of large-scale applications, e.g. scientific experiments, Internet of things and social networking, led to generation of large volumes of data. The management of this data presents a significant challenge as the data is heterogeneous and distributed on a large scale.

In traditional systems including distributed and parallel systems, peer-to-peer systems and grid systems, meeting objectives such as achieving acceptable performance while ensuring good availability of data are major challenges for service providers, especially when the data is distributed around the world. In this context, data replication, as a well-known technique, allows: (i) increased data availability, (ii) reduced data access costs, and (iii) improved fault-tolerance. However, replicating data on all nodes is an unrealistic solution as it generates significant bandwidth consumption in addition to exhausting limited storage space. Defining good replication strategies is a solution to these problems.

The data replication strategies that have been proposed for the traditional systems mentioned above are intended to improve performance for the user. They are difficult to adapt to cloud systems. Indeed, cloud providers aim to generate a profit in addition to meeting tenant requirements. Meeting the performance expectations of the tenants without sacrificing the provider's profit, as well as managing resource elasticities with a pay-as-you-go pricing model, are the fundamentals of cloud systems.

In this thesis, we propose a data replication strategy that satisfies the requirements of the tenant, such as performance, while guaranteeing the economic profit of the provider. Based on a cost model, we estimate the response time required to execute a distributed database query. Data replication is only considered if, for any query, the estimated response time exceeds a threshold previously set in the contract between the provider and the tenant. Then, the planned replication must also be economically beneficial to the provider. In this context, we propose an economic model that takes into account both the expenditures and the revenues of the provider during the execution of any particular database query. Once the data replication is decided to go through, a heuristic placement approach is used to find the placement for new replicas in order to reduce the access time. In addition, a dynamic adjustment of the number of replicas is adopted to allow elastic management of resources.

Proposed strategy is validated in an experimental evaluation carried out in a simulation environment. Compared with another data replication strategy proposed in the cloud systems, the analysis of the obtained results shows that the two compared strategies respond to the performance objective for the tenant. Nevertheless, a replica of data is created, with our strategy, only if this replication is profitable for the provider.

Keywords: Cloud Computing, Database Queries, Data Replication, Performance Evaluation, Economic Benefit

Résumé Réplication de données dans les systèmes de gestion de données à grande échelle

Ces dernières années, la popularité croissante des applications, e.g. les expériences scientifiques, Internet des objets et les réseaux sociaux, a conduit à la génération de gros volumes de données. La gestion de telles données qui de plus, sont hétérogenes et distribuées à grande échelle, constitue un défi important.

Dans les systèmes traditionnels tels que les systèmes distribués et parallèles, les systèmes pair-à-pair et les systèmes de grille, répondre à des objectifs tels que l'obtention de performances acceptables tout en garantissant une bonne disponibilité de données constituent des objectifs majeurs pour l'utilisateur, en particulier lorsque ces données sont réparties à travers le monde. Dans ce contexte, la réplication de données, une technique très connue, permet notamment: (i) d'augmenter la disponibilité de données, (ii) de réduire les coûts d'accès aux données et (iii) d'assurer une meilleure tolérance aux pannes. Néanmoins, répliquer les données sur tous les noeuds est une solution non réaliste vu qu'elle génère une consommation importante de la bande passante en plus de l'espace limité de stockage. Définir des stratégies de réplication constitue la solution à apporter à ces problématiques.

Les stratégies de réplication de données qui ont été proposées pour les systèmes traditionnels cités précédemment ont pour objectif l'amélioration des performances pour l'utilisateur. Elles sont difficiles à adapter dans les systèmes de cloud. En effet, le fournisseur de cloud a pour but de générer un profit en plus de répondre aux exigences des locataires. Satisfaire les attentes de ces locataire en matière de performances sans sacrifier le profit du fournisseur d'un coté et la gestion élastiques des ressources avec une tarification suivant le modèle 'pay-as-you-go' d'un autre coté, constituent des principes fondamentaux dans les systèmes cloud.

Dans cette thèse, nous proposons une stratégie de réplication de données pour satisfaire les exigences du locataire, e.g. les performances, tout en garantissant le profit économique du fournisseur. En se basant sur un modèle de coût, nous estimons le temps de réponse nécessaire pour l'exécution d'une requête distribuée. La réplication de données n'est envisagée que si le temps de réponse estimé dépasse un seuil fixé auparavant dans le contrat établi entre le fournisseur et le client. Ensuite, cette réplication doit être profitable du point de vue économique pour le fournisseur.

Dans ce contexte, nous proposons un modèle économique prenant en compte aussi bien les dépenses et les revenus du fournisseur lors de l'exécution de cette requête.

Nous proposons une heuristique pour le placement des répliques afin de réduire les temps d'accès à ces nouvelles répliques. De plus, un ajustement du nombre de répliques est adopté afin de permettre une gestion élastique des ressources.

Nous validons la stratégie proposée par une évaluation basée sur une simulation.

Nous comparons les performances de notre stratégie à celles d'une autre stratégie de réplication proposée dans les clouds. L'analyse des résultats obtenus a montré que les deux stratégies comparées répondent à l'objectif de performances pour le locataire. Néanmoins, une réplique de données n'est crée, avec notre stratégie, que si cette réplication est profitable pour le fournisseur.

Mots

Chapter 1 Introduction Abstract

In this chapter, the context of this thesis is explained in terms of the targeted data management system and the aim of the data replication strategy. Furthermore, the motivation behind the proposed data replication strategy is described as well as the conditions that necessitate it. Publications resulted from this thesis alongside the contributions are also provided in this chapter.

Context

A noticeable aspect of our lives in the new millennium is that we are now surrounded with a plethora of interconnected services that generate tremendous amount of data.

In the last decade, growing popularity of social networks, Internet of things and cloud-based software services immensely increased the amount of data flowing across the globe. This data is at such a large-scale, even storing it presents significant challenges. Processing this ever-increasing scale of data, is however a completely huge challenge in on itself [START_REF] Hameurlain | Big Data Management in the Cloud: Evolution or Crossroad?[END_REF]. Dealing with largescale data inevitably strains the capabilities of many traditional systems, including centralized database management systems (DBMS).

Dealing with the vastness of large-scale data, several large-scale data management systems have been introduced over the past decades. Among those, some noticeable examples are parallel and distributed systems, peer-to-peer (P2P) systems, data grid systems, and more recently cloud systems. Each of these data management systems have specific properties in their design. These properties may however, be a double edged sword in data management; while providing benefits in one aspect, they can also bring challenges in other issues. A good example would be implementing data replication in a distributed environment. It may provide a performance benefit, but also make it more difficult dealing with data update operations.

Data access performance and availability are other significant issues that must be addressed by any large-scale data management system. Users expect to have a certain level of service quality when it comes to accessing their data. Frequent data access on a global-scale data inevitably poses a significant hurdle for the service providers. Risk of overloaded computational resources and network links, finite storage availability are just a few examples that concern service providers. Service providers are bound to satisfy a certain, acceptable quality of service in a costeffective way to their customers.

In a scenario where the response time of a query is at an undesirably high level for the tenant, the service provider may use some replication solution, e.g. data and task replication, to improve the response time of the query. Sometimes, the executing server may not have enough available CPU, or other necessary resource to process the query with an acceptable response time. This may be a frequent occurrence in a multi-tenant data management environments. In this case, the provider might want to replicate the query to be executed on other servers where there is enough resources available for execution [START_REF] Wang | Efficient task replication for fast response times in parallel computation[END_REF]. On the other hand, there may be some cases where the bottleneck for query execution is not due to some local resource such as the CPU but due to transferring some necessary remote data residing on a different server. If available bandwidth to that particular remote server is not enough, the response time guarantee may not be satisfied due to slow data access. In this case, replicating the associated data closer to the requestor server may improve the performance problem. While it is possible that these performance issues can be solved with some form of replication, e.g. data or task replication, the proposed data replication strategy in this thesis deals data replication aspect of query execution in the cloud [START_REF] Tos | A performance and profit oriented data replication strategy for cloud systems[END_REF](Tos et al., , 2017b,a),a).

Data Replication

On ensuring performance, or rather satisfying an agreed upon performance level; service providers can benefit from a plethora of choices. Among these, data replication is a very well known and researched data management technique that has been used for decades in many systems. Benefits of data replication include increased perfor-mance by strategic placement of replicas, improved availability by having multiple copies of data sets and better fault-tolerance against possible failures of servers.

When tenant queries are submitted to the data management system, depending on the execution plan, e.g. the number of joins, they may require a number of relations in order to carry on with the execution. Naturally, in a large-scale environment where relations are fragmented and distributed geographically in multiple servers, not all required data may be present on the executing node itself. Considering that a query is processed on multiple servers according to inter-operator and intra-operator parallelism, the likelihood of some remote data to be shipped from faraway servers is a realistic possibility. In cases when the network bandwidth capability to the remote servers are not abundant, e.g. due to remote data being at a geographically separate location, a bottleneck that may ultimately lead to a response time dissatisfaction may occur during query execution process.

In order to ensure the satisfaction of query response time objective, the bottleneck data should be identified heuristically to be selected for possible replication before the query is even started executing. Also, when to trigger the actual replication event to start is another important decision that must be made for the same goal. Deciding how many replicas to create and how to retire the unused replicas must also be dealt with further down the road in the data replication decision process. Strategic placement of the newly created replicas plays a key role in reducing data access latency and improving response time satisfaction. Undoubtedly, all of these replication decisions should be made from a cost-effective point of view to ensure the economic benefit of the provider, which is especially important in the economy-based large-scale systems such as cloud computing.

Dealing with the mentioned issues of data replication, a good data replication 1.1. CONTEXT strategy must be able to decide in a meaningful way; (i) what to replicate to correctly determine which fragments of relations are in need of replication, (ii) when to replicate to be able to respond the change in demand of data in a timely manner to quickly resolve performance problems, (iii) how many replicas to create to avoid wasting precious resources such as storage to keep the costs down and retire unnecessary replicas accordingly, and finally (iv) where to replicate to strategically place newly created replicas to ensure tenant performance expectations are met and any possible penalties are avoided. Moreover, all of these decisions should be based on some criteria that are consistent with the aims of both the tenant and the provider.

Cloud Computing

In cloud computing, physical resources are abstracted and rented to a multitude of tenants. While the advantages and disadvantages of abstraction of physical resources is entirely another topic that merits its own research discussion, a well known benefit of this new way of resource provisioning is the elastic scaling of resources on demand, without interruption [START_REF] Hameurlain | Elastic data management in cloud systems[END_REF]. Indeed, [START_REF] Foster | Cloud computing and grid computing 360-degree compared[END_REF] define cloud computing as directly quoted below.

A large-scale distributed computing paradigm that is driven by economies of scale, in which a pool of abstracted, virtualized, dynamically-scalable, managed computing power, storage, platforms, and services are delivered on demand to external customers over the Internet.

Cloud providers share the abstracted physical resources among their tenants. In return, tenants pay the rent associated with their share of services acquired from the cloud provider, according to the pay-as-you-go pricing model. This economic CHAPTER 1. INTRODUCTION relationship between the provider and the tenants is another new aspect of cloud systems in dealing with data management.

As expected from them, tenants demand the best possible performance for their applications. However, best performance is a holy grail, which is very difficult and very costly for the provider to supply. These challenges are further amplified when best performance is continuously demanded in a dynamically changing environment such as cloud systems. It is therefore not realistically possible for a provider to offer the ultimate best performance to the tenants in a cost-effective way [START_REF] Tos | A performance and profit oriented data replication strategy for cloud systems[END_REF]. As any other economic enterprise, cloud providers have to be in pursuit of maximizing their profits. While the intricacies of market economies are beyond the scope of this thesis, it is safe to say that in a competitive market where the cloud providers are pressured to offer their services at lower prices to attract tenants; only realistic option is to reduce the costs of these services for the provider. Unfortunately, low cost and best performance are two goals that often contradict with each other. These conflicting goals are therefore must be regulated in such a way that is acceptable for both parties in this economic relationship. Instead of best performance, providers offer their tenants a threshold performance level as a service guarantee.

The economic relationship between the provider and the tenant is clearly defined in the Service Level Agreement (SLA) [START_REF] Stantchev | Negotiating and enforcing QoS and SLAs in grid and cloud computing[END_REF][START_REF] Buyya | Cloud computing and emerging it platforms: Vision, hype, and reality for delivering computing as the 5th utility[END_REF]. SLA is a legally binding contract that regulates and protects the interests of the parties involved. Among the terms of this contract, Service Level Objectives (SLO) are particularly interesting for this thesis. SLOs are the agreed upon set of objectives, e.g. performance, availability etc. that are included in the SLA to specifically define the quality of the service the provider must supply to the tenants.

Breach of the SLA terms often result in some consequence for the provider, including monetary compensation as a penalty [START_REF] Xiong | Intelligent management of virtualized resources for database systems in cloud environment[END_REF].

Many applications designed for the cloud environment handle data differently. Some would prefer storing fast flowing data in an unstructured way, while others may require a relational model to take advantage of a structured data store that is subject to a schema. Therefore, data management in cloud systems is not a single, fit-for-all solution. In that sense, this thesis focuses on a specific data management context, namely database management systems in the cloud systems. In the considered cloud environment, database relations are fragmented and distributed to many servers around the globe. These servers are contained in datacenters that are located in various geographical regions. Each server, datacenter and region are interlinked with network connections that vary in both bandwidth capacity and cost. In this heterogeneous cloud environment, cloud providers process database queries from multiple tenants, to satisfy a threshold performance level and return a profit at the same time.

Motivations

A good way to understand both data replication and new challenges that are brought to the table by data management in the cloud is to study how data replication is implemented on traditional systems that precede cloud computing. Traditional systems such as data grids precede cloud systems in historical context, therefore many data replication strategies that are proposed for the cloud is somewhat adaptations of their counterparts for data grid systems in order to address some specific challenge of the cloud. Consequently, it allows us to better understand how the challenges of data replication change in conjunction with the challenges of the cloud and how the proposed strategies adapted their implementation to address these challenges. A data management system in the cloud can be elastically scaled on demand, without interruption. A sensible approach for data replication should take advantage of this property of the cloud. A common way of replicating data in the traditional systems, i.e. data grid, is creating as many replicas as possible to attain maximum resource utilization to provide best performance. In cloud systems, such a data replication strategy may not be economically beneficial for the provider, since creation of a large number of replicas can result in a wasteful resource utilization and in return, reduced profit. As mentioned before, in cloud systems, three major questions of what to replicate, when to replicate, and where to replicate [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF]) must be answered in such a way to satisfy the performance in an economically feasible way [START_REF] Tos | A performance and profit oriented data replication strategy for cloud systems[END_REF].

There is a number of efforts in the literature that studied data replication in the cloud systems. Many of them focus just on satisfying the availability SLO [START_REF] Silvestre | AREN: A popularity aware replication scheme for cloud storage[END_REF]Sun et al., 2012a). In a typical cloud environment, where frequent queries are placed on a large-scale data, having low response time is crucial for the tenants. However, performance guarantees, e.g. response time, are often not offered by cloud providers as a part of the SLA. In order to resolve this issue, there are several works proposed [START_REF] Kouki | Cross-layer SLA selection for cloud services[END_REF][START_REF] Saadat | PDDRA: A new pre-fetching based dynamic data replication algorithm in data grids[END_REF] in the literature to include the response time guarantees in the SLA. Dealing with data replication, only a few studies are particularly interested in improved response time [START_REF] Wei | Cdrm: A cost-effective dynamic replication management scheme for cloud storage cluster[END_REF][START_REF] Bai | RTRM: A response time-based replica management strategy for cloud storage system[END_REF][START_REF] Janpet | Reliable and available data replication planning for cloud storage[END_REF][START_REF] Zhang | Data replication placement strategy based on bidding mode for cloud storage cluster[END_REF]. In addition, even fewer of those studies (Bonvin et al., 2010a;[START_REF] Ghanbari | Feedbackbased optimization of a private cloud[END_REF] are taking economics of the cloud into account.

Considering the state of the art on data replication in cloud systems, as mentioned, a vast majority of the existing studies focus on criteria other than performance, e.g. availability. Among the minority of those that deal with performance, an often noticed pattern is that the performance is not considered as an objective but a measured result of data replication as a consequence of having replicas in the system. A very few number of data replication strategies for cloud systems are actually focused on satisfying a performance objective. Furthermore, among those minority, the examples that target a relational database management system that is operating in the cloud is minuscule. Therefore, only a significantly small number of existing studies are valuable for the specific set of problems that are mentioned throughout this thesis study.

This thesis is therefore built on the motivation to address the mentioned problems and shortcomings of the existing data replication strategies in cloud systems that deal with database queries. More specifically, the proposed data replication strategy in this thesis focuses on a novel solution to satisfy performance guarantees to the tenants, as well as ensuring profitability of the provider while executing queries in a relational database system situated in the cloud.

In this thesis, a strategy for Achieving query Performance in the cloud via a cost-Effective data Replication (APER) is proposed to deal with database queries for OLAP applications. APER focuses on the simultaneous satisfaction of both the response time objective and provider profit. We consider left-deep, right-deep and bushy query plans. In a given query plan, before the execution, APER identifies the pipeline chains that are responsible for a response time dissatisfaction. APER estimates the response time of each operator in pipeline chains, taking into account both the inter-operator and intra-operator parallelism. If a required fragment of a relation is predicted to cause a bottleneck during the execution, that particular fragment is considered for replication. The estimated response time with the inclusion of this particular replication must be less than a certain SLO response time threshold. A placement is found for the new replica through a heuristic that reduces both resource consumption and monetary cost. Furthermore, the number of replicas is dynamically adjusted over time. Carrying out the replication also depends on another estimation, namely the provider profit estimation. We estimate both the revenues and expenditures of the provider when executing a query in a multi-tenant context. If the execution of the query is estimated to be still profitable for the provider with any possible new replicas, only then the data replication is performed.

This constitutes a challenge that consists of maximizing the provider profit while minimizing the expenditures as much as possible.

Contributions

A number of contributions have been made in the duration of this thesis study.

These contributions can be summarized as follows.

(i) A complete data replication strategy that satisfies performance SLO and profitability of the provider simultaneously. The simultaneous satisfaction of two key criteria, namely response time satisfaction and profitability of provider are pursued for each query execution. When a query is submitted for execution, proposed data replication strategy identifies whether data replication is necessary and takes the corresponding action that will result in the desired effect in terms of performance and profit. If a data replication event is necessary to take place, how many replicas to create is also another issue dealt by the data (ii) A cost model for estimating response time of executing database queries in cloud computing context. When tenants submit queries to the cloud, they expect a timely response time that is in accord with the SLA. The cost model therefore, estimates whether a submitted query can be processed with an acceptable response time that satisfies the SLA. If the query is estimated to violate the response time objective, proposed cost model determines the reason by identifying possible data access bottlenecks in the query plan. Bottleneck data is then considered for replication. Response time estimation of database queries has already been a well studied topic in the literature [START_REF] Lanzelotte | Industrial-strength parallel query optimization: Issues and lessons[END_REF][START_REF] Özsu | Principles of Distributed Database Systems[END_REF]. As a result, the proposed cost model takes into account the pipelining, inter-operator and intra-operator parallelism and resource consumption of queries by standing on the shoulders of the existing studies.

(iii) An economic model of database query execution in the cloud that takes data replication into account. This economic model estimates the profitability of the provider by estimating the monetary cost of executing each and every query. Estimated cost of execution is compared with the estimated revenue per query in order to predict the profit generated by the provider for any particular query execution. Naturally, the provider aims to return some profit while satisfying tenant requirements, therefore the proposed profit estimation is employed as a decision criterion in the proposed data replication strategy.

(iv) A detailed performance evaluation study to validate the proposed data replica-CHAPTER 1. INTRODUCTION tion strategy. In a simulation environment, the proposed strategy is compared to another data replication approach. The experiments highlight the difference between the two strategies in a simulation scenario where frequent queries are processed in the cloud. Part of this contribution also includes the modifications necessary to CloudSim [START_REF] Calheiros | CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[END_REF] simulation tool, which does not support data replication out-of-the-box. Extending CloudSim is necessary to accurately simulate a multi-tenant cloud environment that processes database queries with data replication.

Publications

During the research period, the studies described in this thesis manuscript have resulted in preparation of a few publications that demonstrate the contributions.

These publications are shown in Table 1.1.

Organization of the Thesis

While the publications resulted from this thesis study already describe many of our contributions, a coherent narrative is crucial to convey the details of the proposed strategy in a more readable way. As a result, this thesis manuscript is organized as follows.

Chapter 2 discusses the state of the art on some important concepts that concern this thesis. A detailed discussion of existing data replication strategies is provided with respect to various data management systems. This discussion helps to convey the justification of target data management system that is considered in this thesis, namely database management systems operating in the cloud.

The main contribution of the thesis is described in Chapter 3. How the proposed data replication strategy decides which database relations to replicate, when to trigger the replication event, how many replicas to create during each replication and where to place the newly created replicas with respect to the cost model and the economic model are discussed here. Also, retirement of unnecessary replicas are also described in this chapter. Furthermore, this chapter introduces a cost model and an economic model of database query processing in the cloud. The cost model of query processing focuses especially on the response time estimation of the database

Introduction

Data replication is a very well-known data management technique that has been commonly adopted by many traditional systems, including (i) database management systems (DBMS) [START_REF] Kemme | Database Replication[END_REF], (ii) parallel and distributed systems [START_REF] Özsu | Principles of Distributed Database Systems[END_REF], (iii) mobile systems [START_REF] Guerrero-Contreras | Dynamic replication and deployment of services in mobile environments[END_REF] and (iv) other large-scale systems including P2P [START_REF] Spaho | P2P data replication: Techniques and applications[END_REF] and data grid systems [START_REF] Tos | Dynamic replication strategies in data grid systems: a survey[END_REF].

In the large-scale data management systems where the data is distributed geographically, i.e. at the scale of wide area networks [START_REF] Goel | Data replication strategies in wide area distributed systems[END_REF]. Frequent access to data would strain network links, overload remote data stores, and overall degrade computational performance. On the other hand, placing local copies of data sets at each node is costly and simply not realistic. As a result, placement of data plays an important role in all large-scale data management systems.

Dealing with data placement problem, data replication is interested in strategically placing copies of data in order to increase availability, access performance, reliability, and fault-tolerance, as well as to reduce bandwidth usage, and job completion times. Many replication strategies have been proposed [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF]Tang et al., 2005;[START_REF] Sang | Dynamic data grid replication strategy based on internet hierarchy[END_REF][START_REF] Shiung | A dynamic data replication strategy using access-weights in data grids[END_REF] Establishing a good trade-off on when to replicate is crucial as replicating too early might be wasteful on resources, while replicating too late may not yield the full benefits of replication. (iii) How many replicas should be created? An optimal, or at least a near-optimal number of replicas should ideally be present in the system to balance the benefits and costs of the replication. While having too many replicas may be wasteful, having too little can be equally undesirable as it may not be enough to satisfy a desired service quality. (iv) Where should the replicas be placed?

Generally, placing replicas closer to the clients with the most access requests may improve overall performance during frequent data accesses.

Achieving an optimal replica configuration across an entire data management system is an NP-hard problem [START_REF] Tang | QoS-aware replica placement for content distribution[END_REF][START_REF] Du | Optimized qos-aware replica placement heuristics and applications in astronomy data grid[END_REF]. Albeit not providing exactly an optimal solution, existing data replication strategies very widely use heuristics to achieve a desired replica configuration throughout the target largescale environments with at least a near-optimal solution. These data replication strategies set some trade-offs and generally aim to excel in at least one aspect of service quality with minimal undesirable consequence.

In the following subsections, we study the existing data replication strategies in some large-scale data management systems that are relevant to the work put forward in this thesis. Even though the main contribution of this thesis is in the cloud systems context, the state of the art on data replication also contains other data management systems in order to better understand how data replication strategies are evolved with respect to the properties of each individual data management environment.

Data Replication in Data Grid Systems

The notion of grid computing emerged in 1990s as a way to establish a distributed processing infrastructure to satisfy information handling needs of institutions that perform advanced science experiments [START_REF] Foster | The anatomy of the grid: Enabling scalable virtual organizations[END_REF]. These institutions contribute computational resources to the grid as virtual organizations, which in turn share these resources in a federated manner.

Data grid is a specialized grid infrastructure that provides a scalable data management solution for science experiments that generate a large amount of data [START_REF] Chervenak | The data grid: Towards an architecture for the distributed management and analysis of large scientific datasets[END_REF]. It provides a globally-spanned heterogeneous environment to research institutions. Data grid is independent of the research areas of these institutions as the many diverse fields take advantage of the data grid including physics [START_REF] Segal | Grid computing: The european data grid project[END_REF][START_REF] Takefusa | Performance analysis of scheduling and replication algorithms on grid datafarm architecture for high-energy physics applications[END_REF][START_REF] Hoschek | Data management in an international data grid project[END_REF], astronomy [START_REF] Deelman | GriPhyN and LIGO, building a virtual data grid for gravitational wave scientists[END_REF], biology [START_REF] Maltsev | Puma2-grid-based highthroughput analysis of genomes and metabolic pathways[END_REF], and climate science [START_REF] Chervenak | High-performance remote access to climate simulation data: a challenge problem for data grid technologies[END_REF].

A common emergence among these experiments is, all of them generate immense amounts of data that is often in the petabytes region [START_REF] Hoschek | Data management in an international data grid project[END_REF][START_REF] Tatebe | Grid datafarm architecture for petascale data intensive computing[END_REF].

Often times, data sets are generated by some experiment performed at an institution and the resulting data sets are processed by other interested institutions which are located in various parts of the world. Processing these data sets require data to be shipped from their origin to the requestors. Frequent data access, combined with precious and limited bandwidth availability potentially cause disastrous data transfer times. Therefore, data replication is an inevitable necessity in data grid systems.

Existing Classifications

There has been a vast number of efforts in the literature on data replication in data grid systems. Each data replication strategy focus on achieving a clearly defined objective, e.g. availability and performance. In this sense, it is possible to classify these replication strategies with respect to some clearly defined criteria existing in their design. Some of these classifications are based on static vs. dynamic classification [START_REF] Chervenak | Giggle: A framework for constructing scalable replica location services[END_REF][START_REF] Cibej | The complexity of static data replication in data grids[END_REF], while some others deal with centralized vs. decentralized replication strategies [START_REF] Ma | A classification of file placement and replication methods on grids[END_REF][START_REF] Dogan | A study on performance of dynamic file replication algorithms for real-time file access in data grids[END_REF][START_REF] Bibliography Tehmina Amjad | A survey of dynamic replication strategies for improving data availability in data grids[END_REF]. Push-based vs. pull-based classification [START_REF] Nicholson | Dynamic data replication in LCG[END_REF][START_REF] Chervenak | Wide area data replication for scientific collaborations[END_REF][START_REF] Dogan | A study on performance of dynamic file replication algorithms for real-time file access in data grids[END_REF][START_REF] Van Steen | Replicating for performance: case studies[END_REF] also exists in the literature, as well as a classification based on the objective function [START_REF] Mokadem | Data replication strategies with performance objective in data grid systems: a survey[END_REF].

Arguably the most common classification scheme is static vs. dynamic replication. In static replication, all replication decisions are made before the system is operational and replica configuration is not changed during operation [START_REF] Chervenak | Giggle: A framework for constructing scalable replica location services[END_REF][START_REF] Cibej | The complexity of static data replication in data grids[END_REF][START_REF] Loukopoulos | Static and adaptive distributed data replication using genetic algorithms[END_REF][START_REF] Fu | QoS-aware replica placement for data intensive applications[END_REF].

On the other hand, in dynamic replication, what, when, and where to replicate are decided as a response to the changing trends of data grid [START_REF] Sang | Dynamic data grid replication strategy based on internet hierarchy[END_REF]Tang et al., 2005;[START_REF] Shiung | A dynamic data replication strategy using access-weights in data grids[END_REF][START_REF] Nicholson | Dynamic data replication in LCG[END_REF]. In a non-changing grid environment, where nodes do not join or leave the grid and file access patterns are relatively constant, static replication might be the better alternative. Compared to dynamic replication, static replication do not have the overhead caused by replication decisions and management. On the other hand, when replicas need to be periodically reconfigured according to changing access patterns, it causes significant administrative overhead and affects scalability and optimal resource use of the system. In a dynamic environment where grid nodes are free to join or leave, and access patterns change over time, dynamic replication excels static replication.

Centralized vs. decentralized replication depends on what entity will control the replication decision process [START_REF] Ma | A classification of file placement and replication methods on grids[END_REF][START_REF] Dogan | A study on performance of dynamic file replication algorithms for real-time file access in data grids[END_REF][START_REF] Bibliography Tehmina Amjad | A survey of dynamic replication strategies for improving data availability in data grids[END_REF].

Centralized replication strategies contain a central authority to control all aspects of data replication. All decision metrics are either collected by or propagated to this central authority. Replication decisions are made by this point of control and all the other nodes report to it. In contrast, decentralized approach requires no central control mechanism to exist in the system. Nodes themselves decide on how replication will occur. Each approach has its advantages and drawbacks. Centralized replication is easier to implement and generally more efficient, as a single entity is responsible for all the decisions and has knowledge about every aspect of the data grid. On the other hand, the central authority is also a point of failure, thus is not ideal for reliability and fault-tolerance. Decentralized replication is good for reliability as there is no single point of failure in the system and the system can still behave predictably even a number of nodes are lost. However, having no central control and nodes acting on incomplete information about the state of the system may yield non-optimal results, e.g. excessive replication [START_REF] Kavitha Ranganathan | Improving data availability through dynamic model-driven replication in large peer-to-peer communities[END_REF].

On replication of any particular data, there are two actors involved. Former is the server that hosts the data, and the latter is the requestor that pulls the data to its local storage. Push vs. pull based classification is focusing on the fact that which of these two actors trigger the replication event [START_REF] Nicholson | Dynamic data replication in LCG[END_REF][START_REF] Chervenak | Wide area data replication for scientific collaborations[END_REF][START_REF] Dogan | A study on performance of dynamic file replication algorithms for real-time file access in data grids[END_REF][START_REF] Van Steen | Replicating for performance: case studies[END_REF]. In push based replication, replication event is triggered by the originator of data, as the server pushes data sets to clients. Servers receive requests from a number of clients, thus they require enough information about the state of the system to be able to trigger replication. Therefore, push based replication is often proactive. In pull based replication, replication event is triggered by the clients. Pull based replication can be regarded as reactive, since replication is realized on-demand. Client-side caching is also regarded as pull replication due to the fact that in this form of caching, clients decide to temporarily store data in their local storage [START_REF] Van Steen | Replicating for performance: case studies[END_REF].

Considering the fact that data replication aims to minimize or maximize some objective, it is possible to make a classification with regard to the definition of this objective function [START_REF] Mokadem | Data replication strategies with performance objective in data grid systems: a survey[END_REF]. One popular approach is to improve data locality [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF]Tang et al., 2005). In this case, the aim is to place replicas as close to the clients as possible. Some strategies take this aim further by heuristically identifying popular data sets and increase their locality [START_REF] Shorfuzzaman | Adaptive popularity-driven replica placement in hierarchical data grids[END_REF]. Cost based objective functions enable replication decisions to take a number of parameters into account [START_REF] Rm Rahman | Replica placement in data grid: a multi-objective approach[END_REF][START_REF] Vassiliki Andronikou | Dynamic QoS-aware data replication in grid environments based on data importance[END_REF]Mansouri and Dastghaibyfard, 2013). In these works, replication decision is generally made according to the output of a mathematical model that take into account collective file access statistics, bandwidth availability, replica sizes, etc. Market-like mechanisms also exist in some works [START_REF] Bell | Evaluation of an economy-based file replication strategy for a data grid[END_REF][START_REF] Goel | Data replication strategies in wide area distributed systems[END_REF]. In these efforts, data is regarded as tradable goods. During a replication event, clients tend to buy data from remote servers that offer the lowest CHAPTER 2. STATE OF THE ART price while remote servers try to sell their data to return some profit.

Proposed Classification

In the following subsections, we study the state of the art on data replication in data grid systems with respect to a classification based on data grid architecture This novel classification is the main contribution of one the publications [START_REF] Tos | Dynamic replication strategies in data grid systems: a survey[END_REF] resulted from this thesis study.

Data Grids with Multi-tier Architecture

Multi-tier architectures follow the data grid model of GriPhyN project [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF]. It is hierarchical in nature, and it has a well-defined, strict topology. On the other hand, due to this strict organizational structure, multi-tier architectures are not very flexible to allow arbitrary addition of removal of nodes.

Multi-tier data grid is organized in four tiers. Tier 0 denotes the source, e.g. CERN, where the data is generated and master copies are stored. Tier 1 represents national centers, Tier 2 shows the regional centers, Tier 3 consists of work groups, and Tier 4, contains desktop computers as depicted in Figure 2.1. In this model, generally, the storage capacity increases from bottom to the upper levels of the hierarchy.

Taking advantage of the hierarchical architecture, [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF] paved the way by proposing six dynamic replication strategies for multi-tier data grid. Some other data replication strategies also deal with data popularity according to the access histories of files [START_REF] Cui | Based on the correlation of the file dynamic replication strategy in multi-tier data grid[END_REF]. Simple Bottom-Up (SBU) and Aggregate Bottom-Up (ABU) strategies by Tang et al. (2005) In addition to file popularity based on access frequencies, some data replication strategies also deal with spatial locality among files. A good example is File Reunion (FIRE) by Abdurrab and Xie (2010) strategy. FIRE assumes that there is a strong correlation between a group of jobs and a set of files. Based on this assumption, FIRE aims to reunite the file set onto the servers by means of replication. Replication is performed when a file is not locally available, and there is enough storage space to store it. If there is not enough storage space, a file with a lower group correlation degree is removed before replicating the new file. In a simulation scenario, FIRE performed better than Least Frequently Used (LFU) [START_REF] Arlitt | Evaluating content management techniques for web proxy caches[END_REF] and LRU replication strategies.

On improving spatial locality of files, [START_REF] Mohammad Khanli | PHFS: A dynamic replication method, to decrease access latency in the multi-tier data grid[END_REF] proposed Predictive Hierarchical Fast Spread (PHFS) as an improvement over Fast Spread by [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF]. PHFS works in three stages. In monitoring stage, file access records from all clients are collected in a log file. In analyzing stage, data mining techniques are used to discover the relationships between files. For a file A, any file B with a relationship greater than a threshold is considered in the predictive working set (PWS) of A. In the final stage replication configuration is applied according to the calculated PWSs. They left performance evaluation for a future study but showed on an example that PHFS improved access latency over Fast Spread.

Data Grids with Bandwidth Hierarchy Consideration

Data grids usually comprises participation from a number of institutions. These institutions although not necessarily, but usually located in various parts of the world. This geographical diversity is reflected on how a data grid architecture is substantiated in terms of network links (Figure 2.2). At the local network level, the institutions may enjoy the benefits of high-speed network links. However, over large geographical distances the Internet infrastructure is generally used. The problem with transferring large-scale data over Internet is potentially high delays and transfer times due to the lack of abundance in bandwidth. Some data replication strategies take advantage of this heterogeneity in network bandwidth capability.

One of the earliest studies to consider bandwidth hierarchy is the Bandwidth Hierarchy Replication (BHR) by [START_REF] Sang | Dynamic data grid replication strategy based on internet hierarchy[END_REF]. In their approach, they present that bandwidth between regions, e.g. countries, are narrower compared to bandwidth available inside a region. BHR replicates popular files as many times as possible within a region, where intra-region bandwidth is abundant. In simulations, BHR performs better than delete LRU and delete oldest replication when narrow interregion bandwidth or low node storage space exists. However, as the inter-region bandwidth or available storage space of the nodes increase, BHR performs similarly to the traditional strategies.

An improved implementation of BHR was proposed by [START_REF] Sashi | Dynamic replication in a data grid using a modified bhr region based algorithm[END_REF] as Modified BHR algorithm. In their strategy, the data is generated at the master site and replicated to region headers before any jobs are scheduled on the grid. They assume that the files accessed by a node, will also be accessed by nearby nodes and popular files will be accessed more frequently. Replicas are only placed in the region header and the node that makes the most requests. The access records are kept in the region header and least frequently used replicas are chosen as the deletion strategy. Modified BHR algorithm is compared with no replication, LFU, LRU and BHR in a simulation study and the results show improved mean job time than to other strategies.

While BHR and its variants dealt with a two level bandwidth hierarchy, some other strategies considered a three level network hierarchy to better represent a realistic network topology. [START_REF] Horri | A hierarchical scheduling and replication strategy[END_REF] presented 3-Level Hierarchical Algorithm (3LHA) for this purpose. In this work, the first level consists of regions, i.e. having low bandwidth availability. Levels two and three represent local area networks (LAN) and clients in the LANs, respectively. When a client accesses a file, if it has enough storage, the file is replicated. However, if files needed to be deleted before the replication, first, the local files that also already exist on the LAN are chosen for deletion. Then, the local files that already exist in the region are considered for deletion, and if there is still not enough space available, other local files are deleted.

They compared their strategy with BHR and LRU and showed that the proposed strategy performs better in terms of mean job time.

Mansouri and Dastghaibyfard (2012) extended 3LHA and proposed Dynamic Hierarchical Replication (DHR) strategy. They emphasize that 3LHA places replicas in all of the requestor sites. On the other hand, DHR creates a per-region ordered list of sites with respect to the number of accesses to a file. The site that is at the top of the order is chosen to place the new replica. By placing replicas at best sites, DHR aims to lower storage cost and mean job execution time. They compare the effectiveness of DHR against no replication, LFU, LRU, BHR, and 3LHA. The results show that DHR shows better job execution times compared to other studied strategies, especially when grid sites have smaller storage space. In another paper, Mansouri and Dastghaibyfard (2013) also added economic cost model calculation to DHR, and presented Enhanced Dynamic Hierarchical Replication (EDHR). By predicting future economic value of files, they made better assessment of which replicas will not be beneficial and get deleted, and which files will be beneficial and get replicated. Simulations indicate that EDHR yields even better mean job times than DHR. Another variant of 3LHA is the Modified Dynamic Hierarchical Replication Algorithm (MDHRA), which is another extension of DHR strategy by Mansouri et al. (2013). In MDHRA, replica replacement decision mechanism is altered to take last request time, number of accesses, and size of the replica into account. They note that the new approach improve the availability of valuable replicas. Simulations show that, compared to DHR and other studied strategies, MDHRA performs better in terms of mean job completion time and effective network usage. However, performance evaluation does not include EDHR.

Instead of periodically reacting the changing trends in the system, Pre-fetching and Prediction based Replication Algorithm (PPRA) [START_REF] Beigrezaei | PPRA: A new pre-fetching and prediction based replication algorithm in data grid[END_REF]. PPRA uses predictive statistical methods to discover the relationships between files. Therefore, when a file is requested by a client, PPRA pre-fetches any related files and replicates them if necessary. Replica managers continuously collect and update file access logs to extract the patterns in file requests.

Other Hierarchical Data Grid Architectures

Data replication strategies of this type are still designed for a hierarchical data grid architecture. However, they do not strictly target the four level multi-tier data grid [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF] or they do not necessarily consider the bandwidth hierarchy. Still, they assume the data is produced at the origin of the hierarchy and processed by clients at the lower levels. In most cases, there are middle level intermediate nodes in the hierarchy that are used for storing data. Other works focus on correlation between files or file fragments. This way, it is possible to predict, to some degree, which files are going to be accessed after certain files. [START_REF] Saadat | PDDRA: A new pre-fetching based dynamic data replication algorithm in data grids[END_REF] propose Pre-fetching Based Dynamic Data Replication Algorithm (PDDRA) with the assumption that members of a virtual organization (VO) have similar interests in files. PDDRA predicts the future accesses of files and pre-replicates those. When a file is requested, PDDRA scans the logs and determines which files follow that file, and which of the follower files has the greatest number of accesses. PDDRA shows better performance than other strategies in terms of mean job execution time and effective network usage under all simulated access patterns.

Combination of the popularity concept with correlation among file accesses is also a visited issue in the literature. Replication Strategy based on Correlated Patterns (RSCP) [START_REF] Hamrouni | A data mining correlated patterns-based periodic decentralized replication strategy for data grids[END_REF] and Replication Strategy based on Maximal Frequent Correlated Patterns mining (RSMFCP) [START_REF] Qin | Research on decentralized group replication strategy based on correlated patterns mining in data grids[END_REF] use data mining techniques to discover closely related files. Once these correlated file groups are identified, their replication are always carried out in a group. If there is not enough storage on the target node, older replicas are retired in order to make space.

In a similar approach but this time for a different goal, Branch Replication Scheme (BRS) [START_REF] José | Branch replication scheme: A new model for data replication in large scale data grids[END_REF] takes advantage of the relationship between disjoint sub-replicas of a single file, whose replicas are placed on different nodes. With this approach, however, BRS aims to create high levels of fault-tolerance without increasing the storage use.

Improved data locality of popular files is not the only aim of replication, as evidenced by [START_REF] Meroufel | Managing data replication and placement based on availability[END_REF]. They propose a replication strategy called Placement Dynamic (PD) that determines a minimal the number of replicas to ensure a certain level of availability without degrading performance. In PD strategy, placement of replicas and failures in the system are taken into account.

If a failure suspicion is observed, data is moved to other nodes in the system to maintain availability. Authors compared PD to a random replication approach in simulations performed with FTSim. Results show that PD demonstrates better recovery times and satisfies availability compared to random replication.

Data Grids with Peer-to-peer Architecture

In peer-to-peer (P2P) data grid architectures, there is no central authority to make and enforce replication decisions. Grid nodes themselves collect the measurements of metrics used in these decisions. They act in an autonomous way and normally possess enough functionality to act as both servers and clients at the same time.

This decentralized grid architecture shown in Figure 2.3 allows high volatility, as nodes can connect to any part of the grid and leave without notice. In an early effort by [START_REF] Kavitha Ranganathan | Improving data availability through dynamic model-driven replication in large peer-to-peer communities[END_REF], a model-driven dynamic replication strategy keeps a minimum required number of replicas in P2P data grid to satisfy a desired availability level. Their model takes node stability, data transfer time between nodes, storage cost of files into account. While their system expectedly outperforms a static replication approach they highlight the fact that independent acting of nodes on incomplete information sometimes lead to unnecessary replication.

Node

A common approach in the P2P grid where there is no apparent hierarchy among the nodes is to rely on network link connectivity degree to decide on the minimization of data transfer times. [START_REF] Chettaoui | A new decentralized periodic replication strategy for dynamic data grids[END_REF] Another data replication strategy by Challal and Bouabana-Tebibel (2010) maximizes the distance between identical replicas and minimizes the distance between non-identical replicas. They increase availability and ensure that each node has replicas of a different file in its vicinity. Another interesting aspect of their strategy is they supply the data grid with a strategic initial placement of replicas before the jobs are started.

Focusing on network topology is not the only consideration of the replication strategies for P2P data grids. [START_REF] Bell | Evaluation of an economy-based file replication strategy for a data grid[END_REF] present an economy-based data replication strategy that considers the data grid as a marketplace. Files represent tradable goods on this market. Computing elements purchase files and aim to minimize their purchasing cost. Similarly, storage elements try to maximize their profits and make investments based on file access predictions to increase revenue. This strategy reduces total job execution times in sequential file access, however LRU performs better in some specific access patterns.

Data Grids with Hybrid Architecture

Hybrid data grid architectures generally combine at least two other architectures with different properties. For example, a replication strategy can be aimed at a sibling tree hybrid architecture, which combines P2P-like inter-sibling communication with hierarchical parenthood relationships as depicted in Figure 2.4. This is a very specific type of data grid architecture that is not considered by many data replication strategies. A runtime component constantly monitors the grid to collect important parameters, i.e. replica size, and network status. These information used in the calculation of the replication costs. They noted that average response time is improved as replicas are placed closer to clients.

Two-Way Replication (TWR) by [START_REF] Rasool | Replica placement in multi-tier data grid[END_REF] combines a multi-tier architecture with P2P-like features. In the target architecture, each node (except at the leaf level) is connected to its siblings as well being connected to its parent.

Replication decision is handled by a central authority called Grid Replication Scheduler (GRS). GRS targets the files that have higher-than-average access frequency and replicates them at the parent of the client that generate the most requests. In terms of response time, TWR performs similarly to Fast Spread while consuming less resources.

Data Grids with General Graph Architecture

In general graphs, nodes are freely connected (Figure 2.5) without a particular topological enforcement for hierarchy. From a scalability point of view, these architectures are at an advantage because there is no strict limitation on the organization of the nodes. Data replication strategies that are targeting the scale-free, social network based data grid architectures and other general strategies that do not focus on one particular architecture are classified in this subsection.

In general graph data grids, nodes are interconnected with varying degrees of connectivity. This impacts the inter-node data transfer capabilities of the nodes as some nodes having easier access to different parts of the grid. Dynamic Multi-replicas Creation Algorithm (DMRC) [START_REF] Chen | Method for replica creation in data grids based on complex networks[END_REF] takes advantage of this scale-free grid architecture. DMRC measures the degree of distribution of nodes and place replicas on nodes with higher degrees. It also uses a cost model to calculate costs of placing replicas on candidate nodes. is defined as maximizing profits by satisfying quality of service requirements of the system. They proposed a greedy algorithm and an adaptable heuristic algorithm to make replication decisions. They compared these algorithms to show that the heuristic approach outperformed the greedy algorithm in terms of execution speed.

Node

Minimize Data Missing Rate (MinDmr) [START_REF] Lei | An on-line replication strategy to increase availability in data grids[END_REF] Not all replication strategies propose new metrics to improve quality of service.

As some earlier strategies Enhanced Fast Spread (EFS) [START_REF] Bsoul | Enhanced fast spread replication strategy for data grid[END_REF] extends the existing Fast Spread [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF]) replication strategy to improve data locality. In EFS, a replica is created only under two conditions. (i)

When enough storage is available, or (ii) replica to be created is more important than the replicas it is replacing. The replica replacement decision is based on a dynamic threshold that takes the number of requests, frequency of requests, size of the replica, and last request time into account.

Analysis

Studying data replication strategies in data grid systems revealed that these strategies mainly target and take advantage of some grid architecture. Among these, more relaxed architectures offer easier data access, with multiple network routes to remote sites. In applications where frequent remote requests are a necessity, these architectures are found to be more suitable than other architectures with stricter topologies. It is safe to say that in the architectures where nodes are connected in a less restrictive manner, the response time is decreased, regardless of the replication strategy used [START_REF] Tos | Dynamic replication strategies in data grid systems: a survey[END_REF] compared to more sparsely interconnected data grid architectures.

Access patterns of files are shaped by user requests [START_REF] Dogan | A study on performance of dynamic file replication algorithms for real-time file access in data grids[END_REF][START_REF] Sashi | Dynamic replication in a data grid using a modified bhr region based algorithm[END_REF]. In data grids, stored files are read by clients that process them.

Some data processing tasks may require a number of files contained in a data set.

In those cases, a data set contains a number of files that have some correlation between their access frequencies. Furthermore, a newly added file to the grid may gain a popularity, or contrarily a popular file of today may not be popular in the future. There are a number of different access patterns used in the literature, including random access patterns that are generated from statistical distributions, e.g. Gaussian and Zipf, and sequential access pattern models. While some studies use three [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF] or even five [START_REF] Shorfuzzaman | Adaptive popularity-driven replica placement in hierarchical data grids[END_REF][START_REF] Saadat | PDDRA: A new pre-fetching based dynamic data replication algorithm in data grids[END_REF][START_REF] Chang Lee | PFRF: An adaptive data replication algorithm based on star-topology data grids[END_REF] different access patterns for evaluating performance, others argue for using a more realistic access pattern (Adamic and Huberman, 2002), e.g. Zipf-based. Nevertheless, a sensible model of data access patterns is crucial for realistic evaluation of performance.

Many data replication strategies aim to increase availability. Performance enhancement is often times not directly aimed but still obtained as a consequence of having multiple replicas of files. Multiple replicas allows requestor nodes to have multiple access paths to files, and almost always guarantees lower data transfer times. As having these benefits are tempting, there are replication strategies that always replicate [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF][START_REF] Dogan | A study on performance of dynamic file replication algorithms for real-time file access in data grids[END_REF], or create as many replicas as possible [START_REF] Sang | Dynamic data grid replication strategy based on internet hierarchy[END_REF][START_REF] Sashi | Dynamic replication in a data grid using a modified bhr region based algorithm[END_REF]. Data grids are purpose-built and its resources are shared among institutions in a federated way [START_REF] Foster | Cloud computing and grid computing 360-degree compared[END_REF]. Maximizing resource utilization for maximizing desired benefits is a common theme among these data replication strategies.

Grid resources, while being distributed among the institutions in a federated way, are still not free. A drawback of aiming maximized resource utilization in data replication is the increased resource cost incurred on the data grid infrastructure.

Some strategies deal with resources being finite and limited, e.g. BHR [START_REF] Sang | Dynamic data grid replication strategy based on internet hierarchy[END_REF], most of them do it in terms of resource abundance but not the monetary aspect. As a result, economic impact of the replication is not a frequently visited issue by many proposed data replication strategies in data grid systems. An example case is when a traditional strategy aims to increase availability by filling all of the available storage. Considering the cost of increased storage capacity, it is apparent that replication strategies that create as many replicas as possible will create an economic burden on both the consumer and the service provider.

Data Replication in Cloud Systems

In the last decade, cloud computing has established itself as a popular computing paradigm. Cloud providers offer seemingly infinite amount of resources to meet ever-increasing storage and computational needs of the tenants [START_REF] Foster | Cloud computing and grid computing 360-degree compared[END_REF] by benefiting from filling datacenters with commodity hardware. Elastic scaling of abstracted resources [START_REF] Kouki | SCAling: SLA-driven cloud auto-scaling[END_REF]) also opened the doors for the cloud providers to offer an economy-based service model [START_REF] Suleiman | On understanding the economics and elasticity challenges of deploying business applications on public cloud infrastructure[END_REF]. These seemingly infinite resources are rented to tenants as a utility with pay-as-you-go pricing model (Philip [START_REF] Philip Chen | Data-intensive applications, challenges, techniques and technologies: A survey on big data[END_REF].

In a typical cloud environment, where frequent access requests are placed on a Part of the proposed SLA-aware data replication strategies are tenant-centric [START_REF] Zhao | SLA-driven database replication on virtualized database servers[END_REF]. Some propose replication strategies that focus on minimizing consumption of a certain cloud resource [START_REF] Vulimiri | Global analytics in the face of bandwidth and regulatory constraints[END_REF], e.g. bandwidth, while others deal with replication of databases to satisfy the SLA without considering monetary impact of the replication decisions (Sousa and Machado, 2012).

Performance guarantees, e.g. response time, are often not offered to the tenants by cloud providers as a part of the SLA. Many of the data replication strategies in the cloud focus just on satisfying the availability SLO [START_REF] Silvestre | AREN: A popularity aware replication scheme for cloud storage[END_REF]Sun et al., 2012a). The lack of performance guarantees in SLAs is also true for the commercial clouds offered by Amazon1 , Google2 , and Microsoft3 . In order to address this shortcoming, there are several works proposed [START_REF] Kouki | Cross-layer SLA selection for cloud services[END_REF][START_REF] Saadat | PDDRA: A new pre-fetching based dynamic data replication algorithm in data grids[END_REF] in the literature to propose mechanisms to include response time guarantees in the SLA. Dealing with data replication, only a few studies are particularly interested in improved response time [START_REF] Wei | Cdrm: A cost-effective dynamic replication management scheme for cloud storage cluster[END_REF][START_REF] Bai | RTRM: A response time-based replica management strategy for cloud storage system[END_REF][START_REF] Janpet | Reliable and available data replication planning for cloud storage[END_REF][START_REF] Zhang | Data replication placement strategy based on bidding mode for cloud storage cluster[END_REF]. Furthermore, even fewer of those studies (Bonvin et al., 2010a;[START_REF] Ghanbari | Feedbackbased optimization of a private cloud[END_REF] are taking economic impact of data replication into account.

Data replication is an integral part of the cloud and many distributed data management systems on the cloud such as Google File System (GFS) and Hadoop

File System (HDFS) already implement some form of replication. As an example,

56

CHAPTER 2. STATE OF THE ART HDFS creates triple replicas in a rack-aware fashion to enhance both the performance and availability [START_REF] Lee | Efficient data replication scheme based on hadoop distributed file system[END_REF]. However, as the scale of the cloud systems enlarge as the number of datacenters and their geographical disparities increase to the scale of Internet, it is necessary for data replication strategies to address this trend.

The following subsections classify the existing data replication strategies in cloud systems according to their objective and whether they consider the monetary impact of data replication in the replication decision process. Since one of the contributions of this thesis is on the performance satisfaction through data replication, the classification is deliberately based on the satisfaction performance objective or satisfaction of objectives other than performance.

Of course, boundaries of classifying data replication strategies in the cloud may sometimes become not clearly apparent due to a certain amount of overlap in the classification criteria. For example, many strategies that focus on increased availability also observe improved performance even though performance may not be an objective in such strategies. This performance benefit occurs as a consequence of having multiple replicas of data sets. As mentioned earlier, a significant portion of data replication strategies in the cloud ignore the economic impact of data replication. Following classification is done in such a way that highlights this phenomenon in the existing strategies.

Data Replication to Satisfy Objectives Other Than Performance

Arguably the most widely considered objective by data replication in the cloud is the satisfaction of a desired level of availability. Availability of data sets often depends on the availability of the nodes hosting them or their system load, as overloaded nodes will not be able to serve requests. Increasing availability of data therefore be satisfied by increasing the number of replicas accordingly.

Cost-effective Dynamic Replication Management (CDRM) [START_REF] Wei | Cdrm: A cost-effective dynamic replication management scheme for cloud storage cluster[END_REF] highlights that having too many replicas does not increase availability but instead results in diminished returns. CDRM calculates and maintains a minimum number of replicas to satisfy a given level of availability. In the considered cloud storage, data sets are fragmented into several blocks. Authors calculate the availability of data sets depending on the availability of each of their fragments. With this information, CDRM calculates a required number of replicas for each fragment. Placement of replicas is performed in such a way that balances the load on all sites. Reducing access skew ensures that all of the fragments are served without causing a bottleneck. As a consequence of balanced load, the authors also observe increased access performance. Investigating the relationship between the number of replicas and the level of availability has been the focus of other studies as well [START_REF] Myint | Management of data replication for pc cluster based cloud storage system[END_REF]. Another approach that is very similar to CDRM (Sun et al., 2012a) also deals with finding minimum number of replicas from a data popularity point of view in cloud storage clusters. In this work, not all data but only a subset of files which exceed an access threshold are considered for replication.

It is also possible to achieve a desired quality of service from an availability standpoint by calculating the minimum level of redundancy with respect to heterogeneous cloud resources [START_REF] Pamies-Juarez | Towards the design of optimal data redundancy schemes for heterogeneous cloud storage infrastructures[END_REF]. In these heterogeneous environments, availability calculation is performed with respect to each cloud site having different reliability levels. This heterogeneity in reliability also determines how many replicas can a cloud site is trusted to host as well. The issue of reliability can also be handled as a fault-tolerance problem by mathematically modeling failure rates of cloud sites [START_REF] Sun | Building a high serviceability model by checkpointing and replication strategy in cloud computing environments[END_REF]. This way, the mentioned study makes it possible to satisfy the availability objective through a fault-tolerance framework based on data replication.

Modeling a data placement strategy to improve availability can be also be achieved through custom economic cost models. Some present an auction model to implement a replica placement policy in a large-scale cloud storage environment [START_REF] Zhang | Data replication placement strategy based on bidding mode for cloud storage cluster[END_REF]. If the desired availability level cannot be maintained, a bidding is held to determine some placement for a new replica. Bidding price is dependent on several properties of the nodes including failure probability, network bandwidth and available space. Some performance increase is also observed as a consequential benefit of data replication. Others deal with a similar problem in a multi-cloud context (Abouzamazem and Ezhilchelvan, 2013), where tenants receive services from multiple cloud providers. These examples use a custom economic model that is tailored to take into account the heterogeneity caused by resource and pricing variations among multiple cloud providers. Similarly to existing strategies, this economic model is used in order to minimize a cost model [START_REF] Miglierina | Model based control for multi-cloud applications[END_REF].

Some other strategies deal with availability as a reliability issue regarding the cloud sites [START_REF] Li | A novel cost-effective dynamic data replication strategy for reliability in cloud data centres[END_REF][START_REF] Li | Ensuring cloud data reliability with minimum replication by proactive replica checking[END_REF]. While availability is a frequently considered objective, what sets these two strategies apart is their consideration of cost-effectiveness in satisfying availability. By determining the duration to keep replicas according to a reliability metric, these strategies can optimize the number of replicas for each file, hence saving provider costs on storage resource.

In another similar effort, Skute is introduced by Bonvin et al. (2010a) as a costefficient data replication strategy based on a virtual economy that takes into account marginal utility, storage usage and query load. Virtual nodes act autonomously and they periodically announce their rent to other nodes. Moreover, nodes also accu-mulate wealth by answering queries and spend this wealth on other nodes to store replicas on them, according to their rent. Skute self organizes replica configuration among the virtual nodes to minimize communication cost while maximizing economic benefit. Even though the strategies of this type utilize some form virtual economy, it is not an actual monetary cost model of the provider-tenant relationship (Bonvin et al., 2010b).

Increasing availability by replicating popular data closer to the locations that originate most amount of requests is also a frequently researched problem. Some strategies even propose mechanisms to predict future accesses based on historical access records to preemptively replicate data to meet the increased demand [START_REF] Ismaeel | Location-aware data replication in cloud computing systems[END_REF]. Moreover, some other strategies deal with data popularity that peaks for a short amount of time, and then tapers off [START_REF] Qu | RFH: A resilient, fault-tolerant and high-efficient replication algorithm for distributed cloud storage[END_REF]. In order to deal with the quick burst of popularity, these data replication strategies quickly respond and change the replica configuration accordingly. Increasing data locality based on popularity also decreases network consumption [START_REF] Huang Mengxing | A strategy of dynamic replica creation in cloud storage[END_REF]. [START_REF] Zeng | Toward cost-effective replica placements in cloud storage systems with QoS-awareness[END_REF] deal with replica creation and placement in cloud storage systems dealing with balanced load. In their work, cloud hierarchy is described as service providers buying services from cloud vendors and in turn, clients buying services from these service providers. Authors aim to minimize costs of the service providers while maximizing storage utilization for users. They measure quality of service and calculate an importance metric of data sets. What to replicate is then determined according to the importance metric. Replica placement is performed in a way that maximizes data transfer volume per unit expenditure.

An interesting objective for data replication is to specifically target some expenditure that is particularly interesting in the cloud. In this respect, some data replication strategies (Boru et al., 2015a,b) focus on minimizing energy consumption and communication delays through data replication. These strategies take data access frequencies into account for a periodical replica reconfiguration. During this periodical assessment, the replication strategy predicts a future value of data sets that include energy and bandwidth demand. According to this estimation, a suitable placement is found for the replicas to minimize their power and bandwidth consumption in the following time periods. Another strategy [START_REF] Maheshwari | Dynamic energy efficient data placement and cluster reconfiguration algorithm for mapreduce framework[END_REF] with a similar aim takes the idea further by integrating data placement strategy to be linked with the power controller for a storage cluster. This way, replicas can be reconfigured to scale the cluster up or down and turn of inactive sites according to workload changes in order to save power.

Data Replication for Performance Objective without

Economic Consideration

While availability-focused strategies can observe some performance improvement as a result of data replication, this performance increase is not generally resulted from an enforcement by the SLA. In other words, performance is usually not among the service guarantees put forward in the SLA contract to the tenant [START_REF] Tos | A performance and profit oriented data replication strategy for cloud systems[END_REF] in the strategies of the previous subsection.

The strategies in this subsection commonly takes performance SLA into account and elastically adjust the number of replicas in some way to ensure performance guarantees to the tenant. Some strategies such as RepliC (Sousa and Machado, 2012) perform this task in an elastic multi-tenant database environment. RepliC monitors the system utilization against workload changes in order to handle the variation by directing transactions to the replicas with available resources. As a result, RepliC strategy satisfies QoS with minimal SLA violations.

Increasing data locality, more specifically spatial locality through data replication yields increased performance with strategically placing replicas closer to the requestor sites. Even though some strategies do not directly consider performance as an objective, increased performance is observed as a consequence of data replication [START_REF] Lee | Efficient data replication scheme based on hadoop distributed file system[END_REF]. Another form of increasing locality of data for improved performance is focusing on temporal locality. In this manner, some strategies argue that frequently accessed data sets will likely stay popular in the future [START_REF] Jayalakshmi | Dynamic data replication strategy in cloud environments[END_REF] and decide what to replicate according to the mentioned popularity assessment. This is a simple but effective strategy for satisfying performance guarantees as evidenced by RTRM strategy [START_REF] Bai | RTRM: A response time-based replica management strategy for cloud storage system[END_REF]. When accessing popular data is causing a higher-than-desired average response time, these data sets are replicated to resolve the performance issue. What is interesting about RTRM is that it replicates not all but just popular data in order to conserve resource usage.

Multi-objective optimization model for data replication is another interesting approach, as described by MORM strategy [START_REF] Long | Morm: A multi-objective optimized replication management strategy for cloud storage cluster[END_REF]. Establishing mathematical models for multiple objectives including availability, response time, network latency; data placement can be performed according to an optimization function that takes these objectives into account. This way it is possible to satisfy more than one SLO simultaneously.

The idea of dynamic provisioning of data is employed in database management systems in the cloud as well. Sakr and Liu (2012) introduced an SLA-aware customer-centric strategy, in which the database servers are scaled in and out according to SLA requirements. As the main SLA objective for the decision process, they chose the total execution time of transactions. In the proposed strategy, cloud sys-tem is closely monitored and cloud providers declaratively define application specific rules to adaptively scale resources. While SLA-aware provisioning is beneficial for scaling, economic impact of the replication for the cloud provider is not considered by this strategy.

While performance benefit can be had by balancing the load of sites, it is also possible to increase performance by decreasing network delays in data access. [START_REF] Sharov | Take me to your leader![END_REF] present such a data replication strategy for leader-based cloud storage.

One replica of each data set is elected as a leader that coordinates the replication tasks. While all replicas may be used for a read operation, leaders often respond to reads or write transactions. The authors state that placement of leaders impact the performance. They propose three algorithms to handle the placement of the leaders, voters and the replicas to reduce the latency of the data access operations. They

show that their strategy improves data access latency by up to 50% in a distributed file system.

Not all data replication strategies deal with performance as a temporal measure of data processing (e.g. response time). Especially in content delivery networks, performance objective may just consist of delivering the data to the requestor. In this sense, AREN [START_REF] Silvestre | AREN: A popularity aware replication scheme for cloud storage[END_REF] is a good example of enforcing SLA as a data delivery guarantee. AREN performs popularity-aware data replication to optimize bandwidth usage to minimize SLA violations and reduce storage consumption to improve overall user experience.

On a similar performance objective, Zhao (2013) deals with replication delay, i.e.

how quickly a database server refreshes all replicas. If the replication delay is longer than a predetermined threshold, new replicas are created to resolve performance degradation. This strategy aims to satisfy the SLA in a tenant-centric fashion, hence the provider profit is not considered. In another study (Sakr et al., 2011) discuss an elastic, cloud-based database management system that enables automatic management of data management tasks, including a rule based implementation of replication decisions. Minimizing cost of resources can also be considered in a heterogeneous cloud context [START_REF] Mansouri | Cost optimization for dynamic replication and migration of data in cloud data centers[END_REF]. Datacenters in different locations can have varying costs for storage, network etc. for placing replicas. A replication strategy should take advantage of this heterogeneous pricing while responding with replication to future variations in workloads. As a common theme in many other distributed environments, reducing network transfers between datacenters through replication to both ensure performance due to faster access to data and provider costs by utilizing more expensive network links less frequently is also present in the cloud systems context [START_REF] Vulimiri | Global analytics in the face of bandwidth and regulatory constraints[END_REF]. A small subset of data replication in the cloud deals with managing how the virtual machines are provisioned on physical hosts. According to provider cost and performance objective [START_REF] Ghanbari | Feedbackbased optimization of a private cloud[END_REF][START_REF] Casas | A balanced scheduler with data reuse and replication for scientific workflows in cloud computing systems[END_REF]. These type of strategies deal with determining how many virtual machines are necessary to perform a set of tasks owned by multiple tenants. Files required for the execution are replicated alongside the virtual machines in order to address the changing demand in the task execution.

Data Replication for

Analysis

While many challenges of traditional large-scale data management systems are still valid in cloud systems, there are some new issues that should be taken into account when dealing with data replication in the cloud. These new issues include elastic adjustment of the resources and renting of the services as an utility with pay-asyou-go pricing to name a few. One particular aspect of the cloud that is interesting for data replication is the provider's point of view in terms of monetary cost of operating a cloud in a multi-tenant environment [START_REF] Lang | Towards multitenant performance SLOs[END_REF].

In traditional systems, many available data replication strategies create as many replicas as possible to achieve higher system utilization. Especially in federated systems like data grids, maximized utilization is pursued in order to have maximum performance and prevent resources to be left idle. However, such an approach may not be economically feasible in cloud computing. Cloud providers expect to return some profit from their business relationship with the tenants. Therefore, such an aggressive data replication approach, while possibly satisfying performance, may also result in higher-than-desired operating cost for the provider. Creation and maintenance of an unnecessarily high number of replicas are therefore inevitably bound to have an impact on the provider profit.

As a result of the economic expectations of the provider, new replicas should be added in order to satisfy SLA requirements, while the removal of replicas occurs when these objectives are satisfied over time. Since SLA requires only the satisfaction of a given level of a quality of service metric, e.g. availability, performance; ideally, the provider should aim to supply the promised service quality, without trying to overachieve. In other words, pursuing best performance for the tenant is unrealistic and most likely a wasteful endeavor for the provider. Instead, the provider should focus on delivering an acceptable quality of service that will maximize its profits.

Therefore, in cloud systems, major questions of what to replicate, when to replicate, how many replicas to create and where to place these replicas must be answered in such a way to satisfy the SLA in an economically feasible way [START_REF] Tos | A performance and profit oriented data replication strategy for cloud systems[END_REF].

Conclusion

In this chapter, we studied the state of the art on data replication in some largescale data management systems. We observed how data replication strategies are adapted their objectives as the computing paradigm is shifted from federated data management systems such as data grids towards economy-based systems, namely cloud computing.

The most common theme in data replication in data grid systems is the emphasis on data access times. Most studies on data replication in data grid systems specifically focus on scientific applications that run on data grids. As multiple institutions access the data that is often generated at a single origin, e.g. physics experiments at CERN, data replication is primarily aimed towards making it easier for the clients to quickly access this data. Other issues such as monetary cost of data replication is often not a visited issue by almost all data replication strategies that are proposed for the data grid.

On the cloud computing side of the fence, existing data replication strategies are geared towards a wider selection of scenarios. Albeit some strategies still target a scientific cloud environment, many other strategies also exist to deal with content delivery, database management systems and various other applications. As cloud computing is nowadays being immensely popular, this was not a surprising outcome.

What was relatively surprising is the decision criteria used in the vast majority of the existing strategies. Cloud computing, as described by [START_REF] Foster | Cloud computing and grid computing 360-degree compared[END_REF], is an

Introduction

As briefly discussed in Chapter 1, simultaneous satisfaction of performance objective and provider profit is the core aim of this thesis. Proposed cost model predicts whether a newly arrived tenant query would satisfy the performance guarantee and economic model is responsible for assessing whether processing of that particular query is profitable for the provider. Neither of these models are enough on their own to form a complete data replication strategy as they are merely tools to assist in making replication decisions. Hence, this chapter describes the proposed strategy for Achieving query Performance in the cloud via a cost-Effective data Replication (APER), as well as how the two models are integrated in the replication decisions at the core of the proposed strategy.

APER takes advantages of some properties of cloud systems, such as a global network hierarchy and heterogeneous resource availability and pricing. Therefore, we start with the chapter by laying out the details of the considered cloud environment and how the various aspects of the cloud would impact APER on making replication decisions. Afterwards, the details of when to start data replication, how many replicas to create and where to place the newly created replicas are discussed.

Of course, all of these replication decisions are handled with the consideration of performance and provider profit objectives. For each query, APER tries to make a replication decision that satisfies the tenant's performance expectation with returning most amount of profit for the provider.

APER deals with database queries for analytical purposes, i.e. query processing for OLAP applications. Therefore, the proposed data replication strategy deals with a cost-effective replica management in a read-only data management context.

Other challenges that are typically associated with data replication, e.g. consistency of data updates, are not in the scope of this thesis.

Cloud Topology

Cloud providers often establish multiple facilities in separate geographical regions for a multitude of reasons, including providing services that span across the globe.

Each region may contain several subregions. These subregions are cloud facilities that host a number of nodes that provide computational power and storage to the tenants. The cloud system we consider consists of geographical regions with each region containing a number of datacenters. Expectedly, each datacenter in turn contains a number of servers, i.e. virtual machines (VM), that reside on physical hosts. Each server is equipped with computational resources, e.g. CPU, network, storage, to contribute during query execution.

Regions, datacenters and servers are interconnected via network links in a hierarchical manner. This hierarchy describes the network bandwidth as it is relatively cheaper and far more abundant inside a datacenter while it is more expensive and less abundant between regions where Internet infrastructure is usually employed. As the network hierarchy goes from inter-node links to inter-region links, bandwidth abundance decreases and bandwidth cost increases [START_REF] Sang | Dynamic data grid replication strategy based on internet hierarchy[END_REF]. A typical example of this cloud hierarchy is depicted in Figure 3.1.

Tenants utilize the services they rent from the provider by placing queries to the cloud. These queries require data sets that may reside on multiple servers scattered around different geographical regions. From the tenant's perspective, it is essential for the response time of an average query to be within the threshold defined in the SLA. The cloud provider aims to satisfy the SLA with the maximum amount of profit. The essence of the proposed strategy contains two models. Former is the cost model based on a response time estimation and latter is the economic cost model used for provider profit estimation. It should also be noted that, processing data in the cloud has many challenges including distributed execution and partitioning. The focus of our study is only on the data replication aspect of data management in the cloud.

An important characteristic that differentiates the cloud from traditional data management systems is the penalty mechanism. Should an SLA breach occur, the provider is obligated to pay an agreed upon monetary sum to the tenant [START_REF] Kouki | Cross-layer SLA selection for cloud services[END_REF]. In our case, when the actual response time is found to be greater than the threshold defined in the SLA, it is indicative of an SLA violation. It is therefore important to note that, penalties play an important role in the economics of the cloud.

Data Replication Issues

Any data replication strategy should be addressing a few key concerns in the decision process for replication to constitute a complete strategy that is suitable for managing data for satisfaction of a certain objective. Some of these concerns have been described in many traditional systems, particularly in data grids [START_REF] Ranganathan | Identifying dynamic replication strategies for a high-performance data grid[END_REF], as what to replicate, when to replicate, and where to place the replicas. However, in economy-based data management systems, i.e. particularly in cloud systems, these decisions must be made from a cost-efficient perspective. We therefore, extend these considerations in the data replication process to take both the tenant and provider's point of views into account. When to replicate is the next important step towards performing data replication.

A set of solid criteria based on the desired goal to achieve is key at this step.

Replicating too early or too frequently would result in inefficient use of resources and also reduce the performance due to frequent re-occurrence of the replication overhead. Too late or too lazily performing data replication is also harmful since it would erase the benefit of data replication due to missing the opportunity for providing actual benefit.

Degree of replication is another important issue in data replication. Too few number of replicas may not satisfy the data access load of the queries while too many replicas would increase data management costs for the provider due to wasteful use of resources. A good middle ground is to dynamically adjust the degree of replication according to the changing demand of tenant queries.

Placement of the planned creation of replicas is equally important as the previous issues. While finding the best placement is a costly venture due to it being an NP-complete problem [START_REF] Tang | QoS-aware replica placement for content distribution[END_REF], finding a good placement in a timely manner to satisfy the requirements of the system is key in this step. Therefore, a data replication should find a cost-effective placement quickly in order to reduce the overhead of data replication and not lose time over trying to find the optimal placement.

Finally, the removal of unnecessary replicas should also be handled by the data replication strategy. Over time, some replicas may become unused due to changing demand in the data management system. To free up resources for future replicas and increase profitability by reducing resource consumption, these replicas should be retired from the system as the queries come and go through the cloud.

In the following sections, we discuss how APER strategy deals with these issues of data replication in a cost-effective manner to satisfy the performance guarantees.

Replication Decision

First, and most fundamental decision in APER strategy is whether to actually perform data replication or not. The replication decision depends on the fulfillment of two important criteria. (i) If the estimated response time (T C ) of a query Q is greater than the threshold response time enforced by the SLA (T SLO ) and (ii) processing of that particular query is estimated by the profit estimation (P Q ) to generate a min-imum desired profit (P T h ) for the provider, with the inclusion of potential creation of any new replicas. The steps of making the decision to replicate are depicted in Algorithm 1. Of course, the profitability prediction of the query includes the cost of new replicas as well.

Algorithm 1 Replication decision on query processing.

1: Receive query Q 2: T C ← Estimated response time of Q 3: if T C > T SLO then 4:
Select bottleneck data for replication 5:

Find a placement for new replicas that would satisfy T C < T SLO

6:

P Q ← Estimated profit by executing Q with the new replicas 7:

if (P Q > P T h ) ∧ (T C < T SLO ) then 8:
Place the new replicas 9:

end if 10: end if 11: Continue executing Q When a tenant submits a query to the cloud for processing, first order of business is to predict whether that particular query can satisfy the response time objective with the given execution plan. Response time estimation of the cost model of APER handles this task. Moreover, in the given query plan, which operator causes the bottleneck that would ultimately result in an SLA breach is identified by the response time estimation.

Dealing with a query that consists of multiple operators, it is important to measure which operator (hence what data related to that operator) will experience a bottleneck in what resource (e.g. network, CPU) in order to resolve the bottleneck and satisfy SLA through data replication. Therefore the data associated with the replication is always the bottleneck data for each replication event during query execution.

In case a query is predicted to violate the SLA performance threshold, then comes the latter part of the replication decision. The second important criterion to fulfill is the provider profitability. Assuming that creation of some new replicas is considered, the processing of the query must still be profitable with the inclusion of the costs associated with the new replicas. Of course, this necessitates finding an economical placement for the new replicas. The provider expects to return a desired amount of profit (P T h ), on average, from every query execution. For this purpose, the profit estimation model predicts the satisfaction of this condition. Only the simultaneous satisfaction of the two mentioned criteria would trigger the replication to be carried out.

As described, APER makes the decision whether to replicate on arrival of each and every query. Another alternative is to perform the replica reconfiguration on a periodical basis. Of course, the calculations required for estimating response time and profit might introduce some overhead to query execution, APER has the benefit of immediately responding to changing trends in the queries arriving at the cloud.

While periodical replica reconfiguration may have less overhead, an obvious drawback of such an approach would be a slow response to changing access trends. A further discussion on this is left for future work as mentioned in Chapter 5.

Replication Degree

Determining the number of replicas for each piece of data is an interesting aspect of data replication. Too many replicas may cause wasteful use of resources, while too few replicas would not be enough to satisfy expected performance level. Some data replication strategies predefine [START_REF] Fu | QoS-aware replica placement for data intensive applications[END_REF] a degree of replication for the data management system. The number of replicas may then be re-adjusted periodically.

APER makes the replication decisions dynamically and on demand, on arrival of each new query. Therefore the degree of replication is also determined in a similar manner.

When the necessity of data replication arises and the required conditions for going through with the replication is met, APER increments the number of replicas for a particular fragment by one. APER aims to place the replica in such a way that it would satisfy the needs of both the provider and the tenant. Therefore, there is no need to create more than one replica at a time for a particular fragment. It is true to say that the number of replicas is dynamically adjusted as the queries are processed in the cloud.

Naturally, a given query can consist of a number of operators that require processing of several fragments. It is possible that more than one of these fragments can be predicted to cause a bottleneck. In cases like this, of course, APER can consider replicating as many of these fragments as it is necessary to resolve the bottleneck condition to satisfy the response time. However, each of these fragments would still be replicated incrementally. In this manner, APER does not enforce an upper limit for the number of replicas of any particular fragment. Consequently, as long as it is still profitable and necessary, the number of replicas of any fragment can be incremented many times as the queries come and go.

Satisfying an agreed upon performance for the tenant is indeed a crucial part of APER. However, ensuring the availability of fragments is another objective that is a commonly present in SLAs [START_REF] Stamou | SLA data management criteria[END_REF]. Therefore, availability should not be ignored for the purpose of focusing on performance. There are many studies in the literature that dare dealing with replicating data for improved availability [START_REF] Qu | RFH: A resilient, fault-tolerant and high-efficient replication algorithm for distributed cloud storage[END_REF]Abouzamazem and Ezhilchelvan, 2013). Therefore, we do not revisit this issue in this strategy. Our strategy simply maintains a minimum number of replicas (e.g. triplication in the HDFS) to satisfy a minimum required availability for each fragment. The number of replicas are never allowed to fall below this minimum during replica removal operations.

Replica Placement

The two estimation models makes it possible to identify resource bottlenecks to determine what to replicate and also decide when the replication is necessary. However it is the strategic placement of the replicas that actually achieves the response time and profitability objectives during execution.

A candidate server for placing the new replica should have low load, enough storage space and sufficient network bandwidth to serve the new replica to the requestors. Furthermore, the candidate placement should also incur low cost to store the new replica.

Clouds can be heterogeneous in many ways. Storage, CPU and network costs for the provider can change from region to region, or datacenter to datacenter for several reasons, e.g. different prices of raw materials. Also, not all regions can satisfy the response time of queries originating from other regions. For example, accessing a fragment in a datacenter in Europe from another datacenter in North America can satisfy the response time SLO, while a datacenter in Asia may fail to do so. Therefore it is a very hard task to find the best placement that satisfies the response time SLO with the lowest cost.

Finding the best placement requires all servers in the cloud to be evaluated for load, storage and network resources, as well as considering the cost of storing it there. Taking into account that the cloud consists of a seemingly infinite number of servers, this approach is non-trivial. Finding a placement for the new replica should be completed in a time sensitive manner. Lingering on for pursuing the best placement would waste time and in turn erase the benefit of actually performing the replication.

For every query execution, when the necessity of creating a new replica of a fragment arises, a placement heuristic is used by our strategy to find a good placement.

Considering all geographical regions of the cloud, only a number of them may satisfy the response time SLO by having mathematically enough network bandwidth. The placement heuristic simply determines this by evaluating the network bandwidth between the requestor and originator regions. The next issue is to find which particular datacenter in these subset of regions has the lowest execution cost with the new replica. The placement heuristic reduces the search space by first eliminating unsuitable regions and datacenters successively and then finding the first suitable server instead of searching for the best one.

Let the cloud L consist of a number of geographical regions as L = {G 1 , G 2 , ..., G i }.

In turn, each of these geographical regions may contain a number of datacenters as

G i = {D i,1 , D i,2 , ..., D i,j }.
Let an estimation function T in Equation 3.1 determine the predicted response time of executing a query Q with the assumption of a new replica of R m n,l placed to region G i . A candidate subset G regions that can satisfy the response time SLO can be found by evaluating all regions by the T function.

G ⊂ G|T (Q, R m n,l , G i ) < T SLO (3.1)
In the next step, the placement focuses on the provider profit. Among the datacenters belong to the G set of regions, placement heuristic choses the D datacenter, which offers storage for R m n,l that results in the lowest cost of execution for the query Q, as depicted in Equation 3.2.

D | min(Cost(Q, R m n,l , D i,j ) ∧ D i,j ⊂ G ) (3.2)
Network bandwidth inside a datacenter uses the dedicated local network infrastructure. This highly controlled network capability is more or less uniform. Therefore if a datacenter is found to have sufficient network capability, it does not matter to store the new replica on which particular server, as long as the candidate server has low load and enough storage.

N m ∈ D |load(N m ) < T h load ∧ f reeSpace(N m ) ≥ sizeof (R n,l ) (3.3)
The replica is placed on the server N m of the datacenter D . The condition for N m is to have enough storage space to store the fragment R n,l and have a computational load that is lower than a load threshold T h load as shown in Equation 3.3. T h load is a system parameter that is predetermined by the cloud provider and may be included Algorithm 2 Placement heuristic for placing new replicas.

1: set G ← empty set 2: for all Regions G i ∈ Cloud L do 3: if T (Q, R m n,l , G i ) < T SLO then 4:
Add G i to set G {regions that has enough bandwidth to satisfy response time} 5: Using the equations that describe the search process for candidate servers, the complete algorithm for finding placement for new replicas is depicted in Algorithm 2.

end if 6: end for 7: D ← min(Cost(Q, R m n,l , D i,j ) ∧ (D i,j ⊂ G ))

Replica Retirement

Over time, some replicas may get less and less frequent accesses due to changing trends in the arrival of the queries. Keeping these replicas in the system consumes precious storage and causes unnecessary costs for the provider. Therefore, retiring unused replicas is a way of eliminating burden on the provider profit. While other replication decisions are made on a per-query basis, determining which replicas are sparsely used is a task that must be undertaken with respect to usage information over time.

APER periodically evaluates all replicas to decide on their eligibility for removal.

The duration of this period (P er remove ) for considering replica removal is determined by the provider. If the response time SLO is satisfied by the queries that require a particular relation, in a certain period (P er sat ), it is regarded that some replicas of the fragments of that relation may be unnecessary, therefore safe for removal. In other words, that a relation R n can be fragmented into l fragments as R n,l and these fragments may have replicas on j servers as R j n,l . If the queries that require R n have no difficulty in satisfying the response time over a predetermined period of time, APER may consider that there may be an abundance in the degree of replication for the fragments of R n .

In order to determine which of the mentioned replicas are unnecessary, each of them are checked for their access histories. Among them, those with an access count below a threshold (T h access ) are retired from the cloud. Of course, the number of replicas for any particular fragment is never allowed to drop below the minimum number of replicas (T h numRep ) to satisfy a given availability level. The replica removal algorithm is depicted in Algorithm 3. The thresholds for the removal operation and the time period to initiate replica removal parameters are left to the discretion of the provider. If cloud providers desire a more aggressive replica removal for quickly freeing up cloud resources or vice versa, they are free to adjust these parameters accordingly. Reset access counts of all replicas 14: end for

A Cost Model for DB Query Processing

As discussed in Chapter 1, APER, data replication strategy proposed in this thesis regards both the satisfaction of query performance and provider profit simultaneously. In this section, how the former criterion, namely the performance metric is treated in the proposed strategy. The data management aspect of this thesis is focused on a relational database system hosted in the cloud, response time of database queries is regarded as the primary metric for performance.

Processing a database query in a distributed context involves a set of steps that include query decomposition (syntax and semantic analysis), resource discovery, generating query plans etc. among many other tasks that are handled by the data management system. APER starts with the assumption that, a query optimizer has already generated a near-optimal query plan. APER strategy is positioned after generating the mentioned query plan and just before carrying out processing of the query. Hence, query plan generation and other related tasks of query execution are not a focus of this thesis as APER only deals with the data replication aspect in the query execution process.

Response Time Estimation

The query plan generation mechanism of DBMS tries to generate a near-optimal query plan according the state of the cloud in terms of location of required relations, load of the servers etc. The generated query plan may not still satisfy performance threshold indicated in the SLA. In other words, a near-optimal query plan may not necessarily guarantee the performance expectation of the tenant. The response time estimation model in this section, is therefore aims to determine whether a given query plan is viable or not in satisfying SLA.

Estimating Response Time of Database Queries

In distributed environments such as clouds, database queries can be processed by participation of a number of servers. These servers process queries with (i) interquery parallelism as executing multiple queries in parallel in the cloud, and (ii) intra-query parallelism as executing individual parts of any single query in parallel.

During processing, database queries require relations, or fragments of relations to be present. These fragments may be scattered across multiple servers. Processing of a query constitute a multitude of operators that can be executed in a pipeline. Furthermore, multiple operators can be executed in parallel with intra-operator parallelism concept. These operators themselves may be divided to be executed in parallel on multiple servers with intra-operator parallelism, which makes the response time estimation even more challenging. Moreover, the result of an operator often can be the input of another as intermediate results. Query processing is therefore not a straightforward task, but it is a set of operations that are intertwined in a complicated manner with presence of parallel execution.

Estimating response time of a query of such complex intricacies is a significant challenge. Dealing with these issues, estimating response time of database queries has been an active research area for decades, as the response time estimation constitutes an integral part of query optimizers in DBMSs [START_REF] Hsiao | On parallel execution of multiple pipelined hash joins[END_REF][START_REF] Swami | On the estimation of join result sizes[END_REF]. Therefore in APER, we benefit from several existing studies [START_REF] Tomov | Some results from a new technique for response time estimation in parallel dbms[END_REF][START_REF] Tomov | Analytical response time estimation in parallel relational database systems[END_REF] to propose a response time estimation model that is suitable for the proposed data replication strategy. These existing studies follow an approach that estimates resource usage (e.g. CPU) by the queries. A novel aspect of response time estimation in APER is that it uses the information on estimated resource consumption by also considering the monetary cost of these resources in replication decisions.

Estimating resource usage of each query as soon as it is submitted is a significant challenge. Many issues as mentioned above, especially parallel execution complicates the task of calculating an accurate estimation. Response time estimation for a single simple query, i.e. without joins, is a relatively straightforward task [START_REF] Tos | A performance and profit oriented data replication strategy for cloud systems[END_REF]. In these queries, there are no dependent operations and as a result, estimating response time is just an approximation of execution and data transfer times. In contrast, estimating the response time of a query that consists of multiple join operators is significantly more difficult. Identifying pipelines, computational complexity of each operator in these pipelines, the amount of data required to be shipped from remote servers all come into play in estimating a complicated query. In order to model the response time estimation over a realistic case, we deal with queries that consist of a multitude of hash join operations. In query plans with multiple hash joins, left-deep, right-deep and bushy plans are investigated (Figure 3.2). We design our response time estimation model to cover all three of these query plan types. Generating query execution plans, and selecting a suitable plan for execution is not a part of this thesis. The scope of the proposed work begins when a new query with a given execution plan is estimated to not satisfy the SLA response time threshold. At that time, APER estimates whether this query plan can satisfy the performance objective, and takes action accordingly.

R 1 R 2 R n-1 R n ⋈ ⋈ ⋈ (a) Left-deep query plan R n-1 R n R 2 R 1 ⋈ ⋈ ⋈ (b) Right-deep query plan R n R n-1 R 2 R 1 ⋈ ⋈ ⋈ (c) Bush query plan
Initially, APER is given a query execution plan P < Q, N > of a query Q that will be executed on a set of servers N . APER estimates the response time of Q by calculating the expected resource usage before the execution of a query takes place. Accurate estimation of the usage of these resources is a significantly hard task with considering both inter-operator and intra-operator parallelism. First step in attacking this task is to identify the pipeline chains in the given query plan to deal with inter-operator parallelism.

Intra-operator Parallelism

Intra-operator parallelism is another issue that must be addressed by the response time estimation model. Intra-operator parallelism deals with parallel execution of an operator on several servers and combining the results generated on each server afterwards. No matter how the fragmentation was done by the DBMS, i.e. horizontal or vertical, there may be response variations between the execution of an operator on different fragments due to skew, available CPU etc. As a result, the response time of an operator that is executed on multiple servers and on multiple fragments is determined by the execution of the operator on a particular one of those fragments that yields the largest amount of response time.

Let C i be a pipeline chain in the query Q. This pipeline chain C i consists of a number of operators,

C i = {O i,1 , O i,2 , ..., O i,k } that
T O i,k = max j (T (O j i,k ), T T r , T F in )|O j i,k ∈ O i,k (3.4)
When an operator is executed on multiple fragments in parallel, the results are required to be transferred to a final destination for combining. When estimating the response time T O i,k of the operator O i,k , Equation 3.4 takes this into account by considering transfer of results (T T r ) and producing the final result (T F in ), e.g. union operation for joining horizontally fragmented relations.

Inter-operator Parallelism and Pipeline Chains

In order to determine the pipeline chains in the query plan, at the first step, APER

assesses in what order the operators are going to be executed. In this sense, when we deal with inter-operator parallelism, we take into account both independent and pipelined execution. In query execution, some operators block data flow between operators [START_REF] Minos | Multi-dimensional resource scheduling for parallel queries[END_REF][START_REF] Tomov | Analytical response time estimation in parallel relational database systems[END_REF][START_REF] Wu | Towards predicting query execution time for concurrent and dynamic database workloads[END_REF] that is necessary for pipelined execution. For example, during hash join, hash tables must be built before the probing stage. Therefore, these blocking operators are identified and the query is deconstructed into pipeline chains according to them [START_REF] Minos | Multi-dimensional resource scheduling for parallel queries[END_REF][START_REF] Tomov | Analytical response time estimation in parallel relational database systems[END_REF][START_REF] Wu | Towards predicting query execution time for concurrent and dynamic database workloads[END_REF].

An example of how the pipeline chains are identified in the left-deep, right-deep and bush query plans is depicted in Figure 3.3. The set of operators that belong in each pipeline chain are executed in a pipeline, until the last operator in the respective pipeline chain, which is ultimately a blocking operator. represented by each root-to-leaf path of the pipeline chain tree [START_REF] Lanzelotte | Industrial-strength parallel query optimization: Issues and lessons[END_REF][START_REF] Özsu | Principles of Distributed Database Systems[END_REF]. In this sense, the response time estimation of a CHAPTER 3. PROPOSED DATA REPLICATION STRATEGY query can be formulated as follows. Let C = {C 1 , C 2 , ..., C i } be the set of pipeline chains containing a number of operators in the query plan P. Moreover, let W = {W 1 , W 2 , ..., W m } be the set of the root-to-leaf paths for all leaf nodes of a pipeline chain tree Y < V, E >, in the given query plan. Consequently, the estimated response time of the query Q is as shown in Equation 3.5, with respect to dependencies and between pipelines. Considering that C i consists of a number of operators,

Scan R 1 Scan R 2 Scan R n-1 Scan R n C i C 2 C i-1 C 1 B P B P B P (a) Left-deep query plan Scan R n-1 Scan R n Scan R 2 Scan R 1 C i C i-1 C 2 C 1 B P B P B P (b) Right-deep query plan Scan R n Scan R n-1 Scan R 2 Scan R 1 C i C i-1 C 2 C 1 B P B P B P (
C i C i-1 C 2 C 1 (a) Left-deep query plan C i C 1 C 2 C i-1 . . . (b) Right-deep query plan C i C 2 C i-1 C 1 . . . (
T C = max m 1 T (V )|V ∈ W m ( 3
C i = {O i,1 , O i,2 , ..., O i,k }
that are executed in a pipeline, some operator depend on the first generated result tuple of the previous operator further up the pipeline chain. In other words, operators that belong to the same pipeline chain does not necessarily start processing at the same time. Therefore, for operators other than the first, there is a pipelining delay, equal to the mentioned waiting duration [START_REF] Lanzelotte | Industrial-strength parallel query optimization: Issues and lessons[END_REF][START_REF] Özsu | Principles of Distributed Database Systems[END_REF]. In order to estimate the response time of each individual pipeline chain, this pipelining delay of each operator O i,k in the pipeline chain C i , must also be estimated to be able to estimate the response time T C i of pipeline chain C i [START_REF] Lanzelotte | Industrial-strength parallel query optimization: Issues and lessons[END_REF][START_REF] Özsu | Principles of Distributed Database Systems[END_REF], as depicted in Equation 3.6.

T C i = max k (T O i,k + pipeDelay O i,k ) (3.6)
Execution of C i starts with processing O i,1 , therefore, starting time of O i,2 depends of the response time of O i,1 . This waiting time is the pipelining delay mentioned above. Response time estimation model recursively estimates the pipelining delay of each operator by going back from the last one to the first since the pipelining delay of the first operator in any pipeline chain is zero. In this subsection, we explain how the response time of an operator is determined with respect to its resource consumption in terms of the resources mentioned above.

Resource Consumption

This process involves estimating the CPU, I/O and network usage of all operators in their respective pipeline chains [START_REF] Hsiao | On parallel execution of multiple pipelined hash joins[END_REF]. This estimation will also play a role in determining which fragments to replicate. Assuming that an operator O i,k in the pipeline chain C i is executed on R j n,l fragment at server j, the estimation model calculates which resource type will cause a response time violation by causing a bottleneck.

CPU Consumption

Consumption of CPU by an operator depends on how much CPU time it is necessary to be spent on actual CPU instructions. First consideration towards estimating CPU consumption is the amount of data to be processed by an operator. Naturally, the more data an operator needs to process, the longer the response time is expected to be. In this sense, we take the terms t(R j n,l ) and sR j n,l ) into account, which denote the number of tuples and size of a tuple in the fragment R j n,l , respectively. Some operators are more computationally expensive compared to others. For example, hash table generation requires more instructions to be executed by the CPU per a single byte of data, compared to relatively simple and cheaper scan op-eration. This variation between the operators are taken into account by the IP B O i,k multiplier, which denotes how many CPU instructions are required by processing one byte of data by any particular operator.

T CP U O j i,k = t(R j n,l ) × s(R j n,l ) × IP B O i,k r CP U j (3.7)
Consumption of the CPU resource by an operator is depicted in Equation 3.7.

In the equation, we have dealt with data size and number of instructions required to process a unit amount of data. In order to have a result in the time unit, we divide these multipliers by r CP U j . r CP U j indicates how many instructions the CPU of the server j can process per unit amount of time. This value is scaled as the number of operators executing simultaneously on a particular server changes. If more than one operators are simultaneously processed on one server, CPU time is consequently divided among them. Therefore, r CP U j is a function of arrival rate, which affects the number of operators simultaneously executing on the servers.

I/O Consumption

During query processing, the relations that are required for that query is read from the disk of the server hosting the data. Whether it is for shipping the relation to another server or processing the relation locally in a query, these operations consume I/O resource on that particular server. The amount of time of time spent on consuming I/O resource depends on the size of the data read from the local storage and the I/O throughput specific to that server, i.e. how many bytes can be read per unit amount of time. In both cases described above, the same I/O consumption model is used to estimate the I/O related response time component of the total response time of any particular query.

In both components, the data size of R j n,l is utilized, similarly to the CPU consumption model.

T I/O O j i,k = t(R j n,l ) × s(R j n,l ) r I/O j (3.8)
I/O consumption is relatively straightforward. On the server N j that hosts the fragment R j n,l that is relevant in the processing of an operator O j i,k ; the fragment R j n,l is read over an I/O throughput of that particular server, r

I/O j
as depicted in Equation 3.8.

Network Consumption

When a server participates in processing of a query, ideally it is desired for this server to have the relevant data to be locally present. In some cases, a portion of required data may be required to be shipped from remote nodes. In another case, if the execution is migrated to another server due a reason that makes the initial server to be temporarily non-viable for query execution, e.g. having a temporarily high load, the associated data may also be required to another server alongside the execution. These type of query processing scenarios require the consumption of network resource. Obviously, consumption of network resource means a duration of time to be spent for transferring data. Response time estimation model also takes this into account when predicting response time of queries.

T N et O j i,k = t(R e n,l ) × s(R e n,l ) r N et j,e
(3.9)

The equation for estimating the network consumption (Equation 3.9) is similar to estimating I/O consumption in the way that both of them are base on the amount of data handled. This time, data transfer occurs between two servers, therefore the estimated time spent on network transfer is determined by bandwidth r N et j,e between the local server N j and the remote server N e during the shipping of the remote fragment R e n,l . We assume that messaging delay for initiating the data transfer process is constant, and included in the total transfer time.

Total Resource Consumption

The three types of resources that are consumed during processing of a query are used in calculating the response time

T O j i,k
of the operators individually.

Of course, for each operator the consumption of these resources do not happen sequentially. Their consumption are time shared on the executing server. For example, CPU can start processing a relation that is shipped from a remote server to the local server as soon as a meaningful amount of data e.g. a page, has becomes available locally. In that sense, the total resource consumption takes time sharing into account by taking the maximum time spent with respect to time-shared utilization of different types of resources as shown as shown in Equation 3.10.

T O j i,k = max((T CP U O j i,k + T I/O O j i,k ), T N et O j i,k ) (3.10)
The resource consumption model used in response time estimation inevitably makes some simplifications in order to rapidly estimate the response time of the queries on arrival. Too complex of a model would increase the computational overhead caused by data replication and in return possibly erase the performance gains expected to be made through data replication. For this purpose, we assume that CPU is occupied during I/O operations and tread the consumption of CPU and I/O to be not happen simultaneously on a single server.

It should be noted that all three types of considered resources take the data size that is relevant to a particular operator into account. In real query processing scenarios, some operators would need intermediate relations as input for processing them. Intermediate relations are outputs of other operators that precede the actual operator in the query execution plan. Since these intermediate relations simply do not exist before the execution of the query starts, the DBMS may not have statistical information about them, e.g. data size. Some research effort have been made to estimate the result sizes [START_REF] Vengerov | Join size estimation subject to filter conditions[END_REF][START_REF] Harangsri | Query Result Size Estimation Techniques in Database Systems[END_REF] and cardinalities [START_REF] Swami | On the estimation of join result sizes[END_REF] of the intermediate relations. We use the methods proposed by these studies to obtain a more accurate estimated response time.

An Economic Model for DB Query Processing in the Cloud

Cloud computing is a computer paradigm that brings several new challenges for data replication strategies to deal with. These challenges have been discussed in detail in Chapter 2. Among the new challenges of the cloud, a particular one is of significant interest for the data replication strategy proposed in this thesis.

In contrast to other traditional data management systems that precede the cloud, resources are rented to the tenants with an economy based model in cloud computing [START_REF] Foster | Cloud computing and grid computing 360-degree compared[END_REF]. It is indeed true as the cloud providers rent the services to the tenants in return of some monetary compensation from them. What this signify is that, operating in the cloud should take economic impact of every decision into account. More specifically, since the context of this thesis is in query execution and data replication in a multi-tenant cloud environment; the economic burden of processing the queries and associated costs of data replication on the cloud provider is of utmost importance.

The economic model presented in this section deals with the economic aspect of the cloud while processing database queries with the presence of data replication.

Replication decisions are based on satisfaction of both the response time satisfaction and provider profit generation. While the response time estimation handles the former part of the condition, the economic part of whether the execution of a query is still profitable for the provider with possible creation of new replicas is handled by the economic model.

Estimating Provider Profit

Dealing with database management in the cloud, requires an immense undertaking by cloud enterprises, similarly to delivering other cloud-based services. Cloud providers establish enormous facilities to host computing resources and process data, pay significant upfront investment in material and personnel, and occupy global network links with transferring data throughout the globe. Inevitably, all of these expenditures add up to a significant monetary sum for cloud providers as operating costs.

For a cloud provider, the entire sum of investment and effort is motivated by gaining economic benefit, namely returning a monetary profit [START_REF] Buyya | Cloud computing and emerging it platforms: Vision, hype, and reality for delivering computing as the 5th utility[END_REF].

As it is the case for all business enterprises, the cloud providers seek profit from their interactions with their tenants. Ideally, every interaction (e.g. query execution) with a tenant should be profitable from the provider's point of view.

While providers aim to return a healthy amount of profit for their benefit, tenants demand a good performance for a reasonable price. Focusing on supplying a service 98

CHAPTER 3. PROPOSED DATA REPLICATION STRATEGY
with the best performance is often a costly pursuit for the provider [START_REF] Tos | A performance and profit oriented data replication strategy for cloud systems[END_REF]. Eagerly replicating data to attain the lowest possible response time may result in high storage and network costs for the provider as a consequence. Among the possible replication decisions, the data replication strategy should be able to go through with the one that just satisfies the response time SLO and yield the most amount of economic benefit to the provider. A profit estimation model is therefore necessary to predict the monetary impact of the resource consumption of processing queries.

Replication decisions are made at the per-query level. As a result, similar to the response time estimation model, the profit estimation is also calculated for each individual query. Equation 3.11 shows the provider profit (P Q ) for executing a query Q, which is the difference between the revenue and total cost (C Q ) associated with that particular query.

P Q = REV Q -C Q (3.11)
It is very straightforward to estimate provider profit with known revenue and expenditures. What is challenging about profit estimation lies in the difficulty of estimating revenue and expenditures for each query the provider processes for each tenant. Some properties that are specific to cloud systems such as dynamically adjusted service capability with pay-as-you-go pricing, heterogeneity of services and their unit costs with respect to global region make it more challenging to estimate the profit.

Estimating Provider Revenue

Cloud providers are large business entities, and as such, it is possible for a provider to have multiple revenue streams. However, in this thesis, we are only interested in the revenue generated from the tenants for query processing. Therefore, in the proposed economic model, rent is regarded as the only revenue source of the provider. In this way, APER strategy estimates the average revenue expected from processing each tenant query.

SLA terms include the details for the rent and the corresponding billing period.

A billing period is an agreed upon duration of time that the tenant acquires services from the provider. The tenant pays the corresponding amount of rent (REV ) to the cloud provider for the services acquired during each billing period.

Naturally, the provider desires to return a profit from each query execution.

APER calculates the per query revenue and cost estimates to predict an expected profit for each query. However, in order to be able to calculate the per-query profit, the SLA should also include the maximum amount of queries the agreed upon service level handles per unit amount of time, i.e. maximum query arrival rate (AR), before scaling the service up.

From the maximum query arrival rate and the duration of the billing period (P ER), it is possible to calculate an expected average revenue REV Q per query as depicted in Equation 3.12.

REV Q = REV P ER × AR (3.12)
It should be noted that, it is not realistically possible to know beforehand that, how many queries a tenant will submit to the cloud with what arrival rate. There-fore, the revenue estimation calculates the average revenue expected from each tenant query. Assuming that the set of services are elastically scaled up and down according to the query arrival rate (and possibly other metrics) of a particular tenant, revenue estimation provides quick prediction of per-query revenue that is accurate enough for replication decisions.

Estimating Provider Expenditures

With a known amount of expected revenue from each query processed, next issue to address is estimating the monetary cost of processing a particular query. Estimating revenue is relatively straightforward to estimating expenditures, because revenue prediction is based on an average. In contrast, expenditures caused by a particular query depends on the cloud resources it will consume once the execution is started.

Therefore, estimating monetary cost of a query is a comparatively more difficult task that involves more steps.

In the cloud environment, where distributed query processing is a natural occurrence, execution of a query Q may involve the participation of a number of servers.

The resources on these servers may be fully or partially utilized by the execution of Q. These resources inevitably cost money for the provider [START_REF] Greenberg | The cost of a cloud: Research problems in data center networks[END_REF].

As in response time estimation model, APER takes into account CPU cost (C U ), network bandwidth cost (C B ) and storage cost (C S ) resources, as well as cost of the penalties (C Y ) in the previous billing period. The sum of these estimated costs determines the total cost of executing a particular query for the provider. These four types of costs are shown in Equation 3.13 as they are used in the profit estimation.

How each of these cost items are estimated is described in detail in the following sections.

C Q = C U + C B + C S + C Y (3.13)
In real world, cloud providers have many types of costs, ranging from employee salaries to on-site physical security. These costs may not be directly linked to, or rather caused by data replication or query execution. However, provider naturally still would want to have enough profit margin to cover these costs as well. As a result, we do not set the profit condition for triggering replication to P Q > 0, but rather P Q > P T h . P T h describes a predefined threshold profit margin as the minimum amount of profit a provider desires to generate from the execution of a query.

CPU Cost

First cost item to estimate in the breakdown of total cost of processing query Q by the provider is predicting CPU cost (C U ). CPU cost depends on the CPU time that is expected to be spend during the execution of a particular query Q. Queries can be processed by the joint effort of a number of servers in a distributed environment.

Therefore, CPU cost is determined by the sum of CPU time consumption of each server (U j ) that is expected to participate in the execution.

Let R = {R 1 , R 2 , ..., R n } be the set of relations with l fragments as R n,l that are used in the execution of Q and N = {N 1 , N 2 , ..., N j } be the set of servers that host j replicas of these fragments as R j n,l and carry out the actual execution task. Then the processing cost is as depicted in Equation 3.14.

C U = j U j × φ j (3.14)
Considering that the cloud is a heterogeneous environment, the unit processing cost (φ j ) may differ according to which particular servers are utilized during execution. Unit processing cost is adjusted in the estimation to reflect the regional differences. For example, high power costs in a particular geographical region may ultimately lead to a higher CPU unit cost as power consumption of a server depends on the CPU consumption.

I/O Cost

While I/O cost depend on the size of the relations that is expected to be used in processing a query, I/O cost estimation is not directly attributed to the amount of storage used by the fragments of these relations. Storage use on its own would not be enough to estimate I/O usage because in case when a new replica is created, not just one but all future queries would benefit from it.

Some queries are more data intensive than the others. These queries may require a particular fragment to be read several times during an execution. Therefore, a realistic storage cost calculation should not just consider the size of the fragments but also consider the amount of disk read operations caused by accessing any particular relation fragment. 3.16.

C S = j e n l sizeof (R n,l ) × ω je × s jenl (3.15) s jenl =          1 if R n,l is

Network Cost

Query processing in distributed environments such as cloud systems, inevitably causes some network resource to be consumed due to data transfer between servers.

The cost of data transfer is another cost item that the provider has to deal with during query execution.

For a certain amount of data transfer, network cost inside a datacenter is considerably cheaper than transferring data between geographical regions. Inside a datacenter, network links are owned and operated by the cloud provider. On the other hand, inter-region data transfer usually performed over the Internet, hence yielding more cost. Furthermore, accessing different geographical regions from the same requestor server likely to net different unit costs simply due to heterogeneous bandwidth availability and pricing toward various regions. As a result, the unit cost of network transfers (ν) is dependent on where the local N j and remote N e servers are located in the cloud.

Since query Q may consist of many operators that may be executed on a num-ber of servers, a multitude of inter-server data transfers involving several remote fragments (R n,l ) may take place. The factor b jenl is used to signify which particular replica is accessed among the many possible replicas of R n,l in the cloud. Equations 3.17 and 3.18 show the network cost and b jenl factor, respectively.

C B = j e n l sizeof (R n,l ) × ν je × b jenl (3.17) b jenl =         
1 if R n,l migrated from node N e to N j 0 otherwise (3.18)

Penalties

SLA terms mandate the provider to complete the execution of every query to satisfy the service guarantees given to the tenant. While providers take necessary precautions (e.g. data replication in our case) to prevent SLA breaches from happening, in reality there may be some queries executed with response times greater than SLO response time threshold. In these cases, the provider pays the tenants an agreed upon sum of penalty, as described in the SLA [START_REF] Wu | SLA-based resource allocation for software as a service provider (saas) in cloud computing environments[END_REF][START_REF] Flávio | Towards elastic multi-tenant database replication with quality of service[END_REF].

Penalty total is not the cost of a consumed resource associated with neither data replication nor query execution. However, amount of penalties incurred to the provider depends on the effectiveness of the data replication strategy. A good data replication strategy should be able to enable query execution to meet the SLA and as a consequence, reduce the penalties for the provider.

C Y = t N U M Q t × P QB t × ρ P ER t × AR t (3.19)
Whether a query has respected SLA response time or not can be observed after the execution is completed. Therefore, the actual penalty cannot be reliably determined by an estimation. Moreover, while the resources consumed by a particular tenant query is backed by the revenue generated by that particular query, the penalties are paid to all tenants by the single provider. As Equation 3.19 shows, for each tenant t, the amount of penalties inflicted per query in the next billing period will depend on the total number of queries processed (N U M Q t ) and percentage of them breaching the SLA (P BQ t ) and per-query unit penalty amount (ρ). Using this formula, we include the increased cost of queries due to penalties paid by the provider.

Conclusion

In chapter, we presented APER, a dynamic data replication strategy to satisfy both the response time objective and economic benefit of the provider for processing database queries in cloud systems. APER estimates the response time of database queries before execution and predicts whether the response time objective is going to be satisfied. If a query is estimated to violate the SLA, the proposed strategy considers placing a new replica based on placement heuristic to carry on the execution with an acceptable response time. Of course, the processing of this query is still required to be profitable with the new replica. An economical model predicts the provider costs for executing that particular query and makes sure that profitability 106 CHAPTER 3. PROPOSED DATA REPLICATION STRATEGY is ensured before the replication is carried out. For all query execution events, this replication decision mechanism is evaluated to identify bottleneck data and replicate them as necessary.

Response time estimation model in APER considers the consumption of the cloud resources in left-deep, right-deep and bushy join query plans. Profit estimation is based on the estimation of both the revenues and expenditures of the provider when executing a tenant query. Based on predicted resource consumptions, we estimate the monetary cost of executing each query while expected revenue is calculated from the rent collected from the tenants.

The outputs of cost model and economic model of database query execution is utilized in every aspect of the replication decisions. Once these two criteria are met and data replication is being carried out, relevant fragments are replicated in an incremental manner. Placement of these replicas are also handled in a cost-effective manner that also satisfies the performance according to the placement heuristic.

Moreover, unnecessary replicas are retired from the system over time to further improve the expenditures of the provider.

Introduction

Another crucial step on proposing a novel data replication strategy is to validate the performance of the proposed strategy through experimental evaluation. Of course, obtaining repeatable results has a key importance in the performance evaluation study. Experimental evaluation of APER strategy can be summarized in two steps.

(i) Preparation of a testbed for evaluating the performance and (ii) actually performing the experiments themselves.

First, a controlled test environment is established to represent a database management system in the cloud that will process a query load with predetermined parameters. For this purpose, we tailored CloudSim [START_REF] Calheiros | CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[END_REF] simulation tool by customizing it to suit the need of our simulation scenarios. In CloudSim,

SIMULATION ENVIRONMENT

109

APER strategy is implemented as well as CDRM [START_REF] Wei | Cdrm: A cost-effective dynamic replication management scheme for cloud storage cluster[END_REF], another data replication strategy. We employed these two strategies to be used in a comparative analysis. The test bed contains all the necessary system requirements for evaluating query performance with the presence of data replication. Moreover, the testbed allows for measuring monetary costs of the provider resulting from resource consumption.

In the second part of the performance evaluation, the results are obtained from processing queries for a predetermined timespan. Of course, the necessary metrics regarding the performance analysis is collected during the tests for both of the evaluated data replication strategies. In this part, the aim is to highlight how APER strategy excels in simultaneously satisfying both the performance and provider profit objectives against the other strategy.

Simulation Environment

Cloud systems are volatile environments in terms of load and resource availability. Especially when considering that many tenants share the same set of resources through abstraction, it is possible to have continuously changing performance. This situation may prevent us from performing controlled experiments [START_REF] Zeng | Toward cost-effective replica placements in cloud storage systems with QoS-awareness[END_REF] that is crucial for demonstrating the performance of the proposed strategy. Simply, we need to be able to control all properties of the cloud environment to have repeatable results. This necessity pushes us towards using a simulation environment, rather than a real cloud.

There are several aspects of the simulated environment that are important for achieving a realistic model of the desired data management system operating in the

Cloud Simulator

Creating an entire cloud topology by renting resources from a cloud provider is a very hard and expensive way of verifying the performance of any study. Furthermore, this performance evaluation study requires us to assume the role of a cloud provider, which is very likely to cause real cloud providers to hesitate donating this kind of access privilege. In order to address these concerns of researchers, several cloud simulators have been proposed in the literature (Ahmed and Sabyasachi, 2014).

These tools let researchers to accurately implement performance evaluation scenarios without the burden and cost of dealing with an actual cloud environment.

All available cloud simulators focus on a key aspect of the cloud, hence designed around that key property. For example, GreenCloud simulator is specifically focuses on simulating energy consumption of datacenters. While other examples exist that are interested in some other properties of the cloud systems, as of writing this thesis manuscript, no particular cloud simulator specifically deal with data replication.

Among the available simulators, CloudSim [START_REF] Calheiros | CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[END_REF] is noticeably widely used in the literature. CloudSim is also an open source project, therefore it is possible to tailor the simulation tool with some extensions to better suit the requirements of the performance evaluation study in this thesis.

In its standard form, CloudSim is targeted for resource provisioning in datacenters in terms of allocating virtual machines on physical hosts. It allows for the creation of simple tasks called cloudlets and models the execution of cloudlets on virtual machines. In a typical usage scenario of CloudSim, number of virtual machines are scaled with respect to the load generated by processing cloudlets. Like many other cloud simulators however, mechanisms for performing data replication is not present in CloudSim. As a result, an extension in functionality of CloudSim is necessary to enhance it with support for data replication; before realizing any simulation scenarios involving the proposed strategy.

First, the cloudlet model of CloudSim is extended to have them better represent database queries. Cloudlets are atomic tasks, independent from each other. This model is extended to have dependencies between cloudlets, which is necessary since processing a database query that may consist of operations with inter-dependencies.

Furthermore, the storage model is also extended to allow for virtual machines to have their own storage, instead of CloudSims own storage model which uses a centralized storage for each datacenter. Next, the necessary changes for measuring important metrics is added to CloudSim. These include monetary cost of resources, which was not measurable in the original form of CloudSim. Most importantly, data replication support is added to CloudSim. With this extension, data replication can be triggered before processing each query or at periodical intervals depending on the requirement of the data replication strategy to be simulated. With these changes, CloudSim is ready to be used for the performance evaluation purposes of this thesis.

Simulated Cloud Topology

As cloud systems often offer services on a global-scale, we realized a cloud topology that consist of 5 geographical regions. These geographical regions represent continent-scale zones that contains datacenters. In turn, each region contains 3 datacenters, which host the actual computational resources. In each of these datacenters, 10 servers are realized as virtual machines. These virtual machines possess processing, storage and network capabilities to process the queries assigned to them.

The regions, datacenters and virtual machines are interconnected as shown in Fig- In the simulations, we realized a hierarchical network bandwidth capability. As the global hierarchy of the cloud goes from regions to towards smaller scales towards the VMs, the network bandwidth is changed in parallel. The network infrastructure is established in such a way that, the bandwidth capacity is more abundant and cheaper at the lower levels of the hierarchy, i.e. inside the datacenters, but less abundant and more expensive towards the higher levels, i.e. between geographical regions.

In addition to network bandwidth, computational capabilities and storage capacities of virtual machines also vary from datacenter to datacenter to simulate a heterogeneous cloud environment. This heterogeneity is not only limited to the capacities of these resources but also extended to their unit costs as well. In every region, the provider costs of these resources are varied to achieve a more realistic cloud system. Therefore, both the performance and cost of the CPU, I/O and network resources depend on the virtual machines participate the processing of any particular query. Each VM is equipped with computational resources (e.g. CPU, storage etc.) essential to perform the execution of queries. During execution, VMs strategies.

We generated a query load of 10000 queries. On generation, each query plan is determined to have a number of joins that vary between 1 to 5. The exact number of join operations each query to have is randomly determined on generation to create a computational variation between different queries. By dealing with different number of joins and ultimately different computational loads caused by each query, the simulation scenario is aimed to be more realistic. Of course, generated queries requires a number of relations for processing depending on the number of joins. All of the generated queries have a right-deep query plan to take advantage of parallel execution in the cloud. These queries are randomly created and submitted to the cloud during the simulation. For all simulation scenarios, same initial placement of the fragments is used to ensure fair starting conditions.

Resource allocation during query processing is not a focus of this thesis, therefore newly generated queries are accepted with their given query execution plan. This execution plan is assumed to already have the target servers that are selected for executing that particular query. In the simulations, when queries are submitted to the cloud, they start processing in the same region they are submitted to, by using servers that are most suitable with respect to their load and hosted fragments in their storage. Queries are generated at random interval with an average arrival rate and submitted to the cloud system. Generated queries require a number of fragments that is dependent on their execution plan, e.g. number of joins. Moreover, computational load generated by each query is also randomly changed from one query to another to simulate the computational load variations between queries, e.g. a simple projection versus an aggregate function.

Simulation Parameters

In the simulations, we used a specific topology and query load as described in the earlier sections. However, the simulation environment is further tailored with a specific set of parameters that describe the other properties of the cloud. These include, network bandwidth capacities, storage availability of the virtual machines, unit cost of resources among many other system parameters. Table 4.1 shows these specific set of system parameters used in the simulation scenarios.

The simulation parameters must be in accordance with the real cloud environments to realistically model query processing on a real cloud. Some of these parameters are relatively easier to model after real clouds, however others, especially the unit cost of resources is difficult to obtain as they are usually treated as trade secrets by the cloud providers to mask their profit margins. Therefore, we referred to the existing studies [START_REF] Luiz | The Datacenter As a Computer: An Introduction to the Design of Warehouse-Scale Machines[END_REF] on datacenter infrastructures to realistically choose these system parameters to represent an accurate cloud environment.

Other system parameters such as the arrival rate of the queries are determined empirically to properly demonstrate the operation of the evaluated strategies in a meaningful manner. For example, a low arrival rate would result in a relaxed system that is not strained by the query load. Such a scenario may not necessitate or benefit from data replication. On the other hand, an extremely high query load that is not possibly be handled by the existing capability of the cloud would also not yield meaningful results from an opposing sense. Therefore, the selected simulation parameters allows us to evaluate performance at the middle ground of the two mentioned cases. 4.2 shows the measured values of these metrics. What these metrics signify regarding the performance of the evaluated data replication strategies is discussed in the following subsections.

Average Response Time

Average response time metric indicates, on average, how long it takes for a query to produce a response starting from its submission. As the tenant's expectation from the provider is the satisfaction of the performance objective, average response time is key in demonstrating whether the evaluated strategies performed acceptably.

APER satisfied the response time with respect to the threshold set in the SLA.

There are some queries that produced a response with a less-than ideal response times during the initial replica reconfiguration. However, after the starting period where replicas are starting to be distributed across the cloud, APER yielded ac-

Number of Replications

During the simulation, both strategies performed relatively similar number of replications. The marginal difference is resulted from the replication decision criteria of the two strategies. In other words, APER replicated data more often than the CDRM, in order to satisfy the response time SLO. On the other hand, CDRM did not continue to create more replicas to satisfy the response time once the balanced load is achieved. The difference is further evidenced by the fact that, APER considers cost-effective satisfaction of response time for triggering replication while CDRM only considers access frequencies of fragments.

In an example case where a query requires an unpopular but large data, APER may perform replication if necessary due to a predicted SLA breach. On the other hand, CDRM would not replicate it even though long data transfer time would violate the SLA since unpopular data is uninteresting for CDRM. Both strategies pursue different objectives it may be possible that the satisfaction of performance necessitate more replications to be triggered compared to the satisfaction of balanced load in this specific simulation scenario.

Storage Usage

APER used 8% more amount of storage space compared to CDRM. While this affects the expenditures of the provider, there is a certain trade-off behind this decision. On replication decisions, APER evaluates which decision is more economically feasible for the provider, doing a remote read or replicating the data to a more suitable location. In the simulation scenarios, apparently performing data replication is more economical for the provider compared to remote reads in a larger percentage of time.

APER followed this route in order to avoid (i) high utilization of expensive network links and (ii) avoiding penalties by taking advantage of having more replicas to satisfy the response time. Of course, APER would not create these replicas if they were not profitable for the provider to have them. Lower number of replicas of CDRM can be attributed to the core decision mechanism of the strategy. In these simulation scenarios, evidently, it takes less number of replicas to ensure availability and balanced load compared to satisfying response time objective. This is further apparent in the number of SLA breaches for the two strategies.

Network Usage

Network usage highly impact the costs of the provider and also data transfer times, as the network links vary both in pricing and throughput depending on the type of the link, e.g. intra-datacenter network area. In this sense, APER performed a majority of data transfers inside regions and datacenters, as shown in Figure 4.3. This is not a coincidence. APER often chose to replicate data residing in remote geographical locations to more locally available servers, preferably in the same datacenters as the requestors are located. More frequent utilization of cheaper network links is also decreases expenditures, as APER avoids using expensive and slow inter-region links by placing replicas on servers that are cheaply accessed with good bandwidth. CDRM does not take into account the network hierarchy among servers during data placement. Instead, it performs server selection for placing new replicas according to the workload of candidate servers. As a result, there are many cases where a target server with a suitable properties for replica placement to be found in a remote datacenter or region. A drawback CDRM is high utilization of expensive and slower inter-region network links.

Number of SLA Violations

The number of SLA violations is the ultimate verdict of replication decisions on their effectiveness during the simulation period. If a strategy performs data replication in accordance with satisfying the SLA, the number of breaches should ideally be zero. However, initially the fragments are scattered across the cloud topology.

Inevitably, during a small period at the beginning of the simulations, some violations are observed simply due to replica reconfiguration to respond query arrival rate. Therefore, a more realistic view of the number of breaches is to keep them at a minimum after the initial replica reconfiguration.

APER caused significantly less number of SLA breaches compared to CDRM during the simulation. As can be seen in the discussion of the average response time metric, some SLA violations (Table 4.2) occurred with the proposed strategy at the initial replica configuration phase. However, CDRM caused a significant number of SLA breaches as a result of the high average response time. Minimizing the number of SLA breaches is the most important measure to take in order to avoid The expenditures are calculated with respect to the resource consumption and their unit costs as described in the simulation parameters. Since penalty cost is not an expenditure generated by the consumption of a resource, it is calculated by using the number of SLA breaches during the simulation.

Conclusion

There are several takeaways emerged from the results of the simulation study. While a data replication strategy is essential to satisfy performance guarantees, simply using a traditional strategy is not enough for the cloud provider to ensure economic benefit. Traditional strategies tend to eagerly replicate to attain best possible performance. However, in pursuit of the best performance, traditional strategies increase provider costs. Consequently, as long as the performance objective is satisfied, it is important to focus on improving the economic benefit of the provider.

Focusing on one aspect of the cloud may also result in some undesirable outcome for other aspects. An example for this phenomenon is observed in the simulations.

While CDRM focuses on satisfying availability and load balancing, economic impact of the replication is not taken into account. The disregard of economic impact of replication on provider profitability resulted in an unacceptable outcome for the provider.

Furthermore, it can be said that, balanced load does not always necessarily satisfy the performance objective. APER successfully satisfied both the response time guarantee and the provider profitability by establishing a good trade-off between them. APER does not pursue best performance in a wasteful way that would ex-haust the cloud resources. Instead, it aims to keep the performance at an acceptable threshold level to leave a healthy profit margin for the provider. In light of the performance evaluation, we believe that, simultaneous satisfaction of SLA and economic benefit should be the key ingredient in any data replication strategy operating in the cloud.

Chapter 5

Conclusion and Future Work Abstract

This chapter concludes the thesis manuscript with a summary of the studies conducted during the research period and contributions made. The novel aspects of the proposed data replication strategy is revisited with discussing on its benefits and shortcomings. Furthermore, some future directions that may inspire researchers who are interested in doing research in this area are discussed.

Summary of Studies

Cloud computing is a computing paradigm that has been growing into popularity in more than a decade. Cloud providers rent the abstracted resources to the tenants in a economy-based model, which allows the tenants to be billed just for their share of resource usage. Moreover, elastic scaling of the resources makes it possible to quickly scale the cloud services to respond demand changes without interruption. In return for their money, tenants expect a certain level of performance from the providers.

On the other hand, providers aim to minimize their expenditures to maximize their profit.

Data replication has been around for many decades to assist in achieving goals such as increased performance, improved availability and introducing fault-tolerance.

Data replication deals with identification of what data needs replication, when to perform the task of replication, decide on the degree on replication, where to place the created replicas and finally retirement of the unnecessary replicas from the system. Of course, while pursuing for performance benefit through data replication, it is important to do it in a cost-effective way especially in economy-based systems such as clouds.

In this thesis we presented APER, a dynamic data replication strategy to satisfy both the response time of database queries and provider's economic benefit in the cloud. APER estimates the response time of database queries before the execution takes place and predicts whether the response time objective is going to be satisfied. If a query is estimated to violate the SLA due to the potential of producing a response time greater than the promised threshold to the tenant, the proposed strategy considers creating new replicas to resolve the performance problem. However, the query still needs to be estimated as profitable for the provider before the We analyzed the performance of APER alongside CDRM [START_REF] Wei | Cdrm: A cost-effective dynamic replication management scheme for cloud storage cluster[END_REF], which is another data replication strategy proposed for cloud systems. The performance evaluation processed a large number of queries on a simulated cloud topology.

The query load consist of different number of joins for each query and cloud topology is established to reflect a heterogeneous cloud environment to represent a realistic scenario. Results indicate that, APER satisfied performance and returned a profit for the provider by strategically placing replicas to simultaneously achieve improved data access time and reduced resource consumption. On the other hand, CDRM resulted in high network and penalty costs due to not considering network hierarchy in data placement and high number of SLA breaches.

Future Directions

After having done in-depth research on data replication in large-scale data management systems, some new research directions or bifurcation possibilities from the research presented in this thesis have emerged. Below, we discuss some of those future work in our research area.

(i) Proposing a more efficient penalty management. On satisfaction of SLA, the ultimate measure of to what extent the tenant's expectations are satisfied by the provider is the penalty mechanism. If the provider manages to keep tenants happy by satisfying SLA, no penalty is incurred on the provider. Otherwise, some amount of penalty is paid by the provider to the tenant, with the amount depending on the degree of SLA violation. In APER, we ensure the satisfaction of SLA by estimating the response time of the the queries and make them meet threshold performance through data replication. Another possible way of achieving this result is by estimating the penalty amount due to execution of some query. This way, SLA satisfaction would still be satisfied and penalty management would become an objective of the data replication strategy, instead of a consequence. Of course, penalty minimization should also be done in a cost-effective way for the profitability of the provider.

(ii) APER makes the replication decisions before the execution of every single query that arrives at the cloud. One significant advantage of this approach is to immediately respond to any changing trend in query load and popularity.

However, one could argue that experiencing the overhead of data replication at every single query may be a high price to pay for the luxury of quickly responding to change. The alternative is to perform a periodical replication, instead of considering it at every query. In periodical replication, historical data for which queries are popular and which fragments are accessed more frequently is collected. Afterwards, this information can be used at periodical intervals to perform a global optimization for reconfiguring replicas. This approach may respond to changing trends more slowly than APER, but it can also be cheaper in terms of overhead. A good research opportunity is available here to compare both approaches and study which one is more suitable for what particular scenario.

(iii) Current economic model deals with the issue of multi-tenancy from the perspective of a single tenant. With a simplistic assumption of the provider having the same set of performance guarantees for each of its tenants, APER is capable of handling a multi-tenant cloud environment. However, each tenant having its own set of requirements from the provider complicates the matters.

In this case, an extension to the economic model to take into account the heterogeneity among service level agreements with multiple tenants is necessary. This direction is worth pursuing and can open new research possibilities.

Considering that queries that belong to a multitude of tenants are processed by the same set of resources, fairness of the provider towards each tenant with different levels of performance guarantees and other service level objectives would also pose interesting challenges to tackle.

(iv) Some other future research opportunities can also be pursued to evaluate the performance of the proposed strategy in various other simulation scenarios. A few example issues that may be worth researching on this matter are listed below.

(a) Performance evaluation study can be taken afar by creating some variation in certain simulation parameters. An way to accomplish this would be to impose different response time threshold values to be used for triggering data replication. This can also be conjoined with the multi-tenancy point made above, with some tenants requiring stricter response time guarantees while others may be more relaxed with their performance demand from the provider.

(b) Some variation can also be introduced in the workload generation routines used in the simulation. Currently, query load is randomly generated in terms of computational intensiveness and their arrival intervals at the cloud system. A more in-depth performance analysis can be done by extending the workload generation to invoke some intentional workload spikes to simulate a query load that resembles real-world system loads more closely.

(c) In the current simulation setup, the query load is generated with a randomly determined number of joins in order to create a load variation between each query. Another possible way to achieve this would be using a standard, well known batch of queries, more specifically TPC-H queries [START_REF] Barata | An Overview of Decision Support Benchmarks: TPC-DS[END_REF]. Also it would be interesting to see the impact of query complexity (in terms of number of joins) on the response time objective. One example evaluation may consider modeling simple queries with 1 join, medium queries with 3 joins and complex queries with 7 joins.

(d) Finally, the simulation topology can be expanded to have a larger number of VMs to better represent a realistic cloud environment. However, it should be noted that it would require a powerful hardware to accomplish as CloudSim gets increasingly resource-hungry as the number of simulated cloud topology gets larger.

Bibliography

Azizol In recent years, growing popularity of large-scale applications, e.g. scientific experiments, Internet of things and social networking, led to generation of large volumes of data. The management of this data presents a significant challenge as the data is heterogeneous and distributed on a large scale.

In traditional systems including distributed and parallel systems, peer-to-peer systems and grid systems, meeting objectives such as achieving acceptable performance while ensuring good availability of data are major challenges for service providers, especially when the data is distributed around the world. In this context, data replication, as a well-known technique, allows: (i) increased data availability, (ii) reduced data access costs, and (iii) improved fault-tolerance. However, replicating data on all nodes is an unrealistic solution as it generates significant bandwidth consumption in addition to exhausting limited storage space. Defining good replication strategies is a solution to these problems.

The data replication strategies that have been proposed for the traditional systems mentioned above are intended to improve performance for the user. They are difficult to adapt to cloud systems. Indeed, cloud providers aim to generate a profit in addition to meeting tenant requirements. Meeting the performance expectations of the tenants without sacrificing the provider's profit, as well as managing resource elasticities with a pay-as-you-go pricing model, are the fundamentals of cloud systems.

In this thesis, we propose a data replication strategy that satisfies the requirements of the tenant, such as performance, while guaranteeing the economic profit of the provider. Based on a cost model, we estimate the response time required to execute a distributed database query. Data replication is only considered if, for any query, the estimated response time exceeds a threshold previously set in the contract between the provider and the tenant. Then, the planned replication must also be economically beneficial to the provider. In this context, we propose an economic model that takes into account both the expenditures and the revenues of the provider during the execution of any particular database query. Once the data replication is decided to go through, a heuristic placement approach is used to find the placement for new replicas in order to reduce the access time. In addition, a dynamic adjustment of the number of replicas is adopted to allow elastic management of resources.

Proposed strategy is validated in an experimental evaluation carried out in a simulation environment. Compared with another data replication strategy proposed in the cloud systems, the analysis of the obtained results shows that the two compared strategies respond to the performance objective for the tenant. Nevertheless, a replica of data is created, with our strategy, only if this replication is profitable for the provider.

Keywords: Cloud Computing, Database Queries, Data Replication, Performance Evaluation, Economic Benefit

Réplication de données dans les systèmes de gestion de données à grande échelle

Ces dernières années, la popularité croissante des applications, e.g. les expériences scientifiques, Internet des objets et les réseaux sociaux, a conduit à la génération de gros volumes de données. La gestion de telles données qui de plus, sont hétérogenes et distribuées à grande échelle, constitue un défi important.

Dans les systèmes traditionnels tels que les systèmes distribués et parallèles, les systèmes pair-à-pair et les systèmes de grille, répondre à des objectifs tels que l'obtention de performances acceptables tout en garantissant une bonne disponibilité de données constituent des objectifs majeurs pour l'utilisateur, en particulier lorsque ces données sont réparties à travers le monde. Dans ce contexte, la réplication de données, une technique très connue, permet notamment: (i) d'augmenter la disponibilité de données, (ii) de réduire les coûts d'accès aux données et (iii) d'assurer une meilleure tolérance aux pannes. Néanmoins, répliquer les données sur tous les noeuds est une solution non réaliste vu qu'elle génère une consommation importante de la bande passante en plus de l'espace limité de stockage. Définir des stratégies de réplication constitue la solution à apporter à ces problématiques.

Les stratégies de réplication de données qui ont été proposées pour les systèmes traditionnels cités précédemment ont pour objectif l'amélioration des performances pour l'utilisateur. Elles sont difficiles à adapter dans les systèmes de cloud. En effet, le fournisseur de cloud a pour but de générer un profit en plus de répondre aux exigences des locataires. Satisfaire les attentes de ces locataire en matière de performances sans sacrifier le profit du fournisseur d'un coté et la gestion élastiques des ressources avec une tarification suivant le modèle 'pay-as-you-go' d'un autre coté, constituent des principes fondamentaux dans les systèmes cloud.

Dans cette thèse, nous proposons une stratégie de réplication de données pour satisfaire les exigences du locataire, e.g. les performances, tout en garantissant le profit économique du fournisseur. En se basant sur un modèle de coût, nous estimons le temps de réponse nécessaire pour l'exécution d'une requête distribuée. La réplication de données n'est envisagée que si le temps de réponse estimé dépasse un seuil fixé auparavant dans le contrat établi entre le fournisseur et le client. Ensuite, cette réplication doit être profitable du point de vue économique pour le fournisseur. Dans ce contexte, nous proposons un modèle économique prenant en compte aussi bien les dépenses et les revenus du fournisseur lors de l'exécution de cette requête. Nous proposons une heuristique pour le placement des répliques afin de réduire les temps d'accès à ces nouvelles répliques. De plus, un ajustement du nombre de répliques est adopté afin de permettre une gestion élastique des ressources.

Nous validons la stratégie proposée par une évaluation basée sur une simulation. Nous comparons les performances de notre stratégie à celles d'une autre stratégie de réplication proposée dans les clouds. L'analyse des résultats obtenus a montré que les deux stratégies comparées répondent à l'objectif de performances pour le locataire. Néanmoins, une réplique de données n'est crée, avec notre stratégie, que si cette réplication est profitable pour le fournisseur.

Mots-clés: Systèmes cloud, requêtes de base de données, réplication de données, évaluation de performances, profit économique

  -clés: Systèmes cloud, requêtes de base de données, réplication de données, évaluation de performances, profit économique 4.3.4 Storage Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.5 Network Usage . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.6 Number of SLA Violations . . . . . . . . . . . . . . . . . . . . 4.3.7 Monetary Expenditures of the Provider . . . . . . . . . . . . . 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 5: Conclusion and Future Work 5.1 Summary of Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bibliography List of Figures 2.1 Multi-tier data grid architecture. . . . . . . . . . . . . . . . . . . . . 2.2 A hierarchical data grid architecture based on network-level locality. . 2.3 Peer-to-peer data grid architecture. . . . . . . . . . . . . . . . . . . . 2.4 An example hybrid data grid architecture (sibling tree). . . . . . . . . 2.5 An example data grid architecture with scale-free topology. . . . . . . 3.1 An example cloud topology showing regions and subregions (datacenters). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Query plans that are considered by the response time estimation model. 3.3 Pipeline chains in left-deep, right-deep and bushy query plans (Garofalakis and Ioannidis, 1996). . . . . . . . . . . . . . . . . . . . . . . . 3.4 Dependencies among pipeline chains in left-deep, right-deep and bushy query plans. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 The cloud topology realized in the simulation. . . . . . . . . . . . . . 4.2 Response time of the queries during simulation. . . . . . . . . . . . . 4.3 Consumption of bandwidth with respect to network hierarchy. . . . . 4.4 Total costs of the provider during the simulation. . . . . . . . . . . .

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.1.1 Data Replication . . . . . . . . . . . . . . . . . . . . . . 19 1.1.2 Cloud Computing . . . . . . . . . . . . . . . . . . . . . . 21 1.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.4 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.5 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . 28 18 CHAPTER 1. INTRODUCTION

  replication strategy. Where to place the replicas are determined strategically to satisfy the SLA with most amount of profit.

Figure 2

 2 Figure 2.2: A hierarchical data grid architecture based on network-level locality.

  Improving data locality through replicating popular files is a common focus for many studies. An access-weight based dynamic replication strategy is proposed by[START_REF] Shiung | A dynamic data replication strategy using access-weights in data grids[END_REF]. Their work, Latest Access Largest Weight (LALW), defines a strategy for measuring popularity of files on the grid, calculating the required number of replicas, and determining sites for replica placement. Recently accessed files have larger weights and, the replica placement is based on weighted access frequencies. LALW shows similar total job execution times compared to LFU while consuming less storage space and having more effective bandwidth usage.Another strategy called Popular File Replicate First (PFRF) by[START_REF] Chang Lee | PFRF: An adaptive data replication algorithm based on star-topology data grids[END_REF] employs a threshold-based popularity measure to replicate the top 20% popular files to every grid site. Files are replicated to destination sites from the closest site that holds the required files. In a simulation scenario using five access patterns, PFRF shows improved performance on average job turnaround time, average data availability, and bandwidth cost ratio metrics.Dynamic Optimal Replication Strategy (DORS) byZhao et al. (2010) is yet another popularity-based replication strategy. A file is replicated when the number of replicas of that particular file is less than a dynamic threshold. Replicas are valued according to their values, which depend on access frequency and access cost of the replicas. DORS performs better than LFU and LRU in terms of mean job execution time and effective network use metrics.

Figure 2 . 3 :

 23 Figure 2.3: Peer-to-peer data grid architecture.

  capitalize on this idea with DPRSKP, Decentralized Periodic Replication Strategy based on Knapsack Problem. DPRSKP selects what files to replicate by creating a prioritized list of the popularity and availability of each file. Replicas of popular files are then placed on nodes that are stable and having good bandwidth to the requestor nodes. Also dealing with network distances when making replication decisions, Abdullah et al. (2008) propose two dynamic replication strategies, Path and Requestor Node Placement Strategy, and N-hop Distance Node Placement Strategy. Path and Requestor Node Placement Strategy replicates files on all nodes on the path to the requestor node, including the requestor itself. In N-hop Distance Node PlacementStrategy, replicas are placed on all neighbors of the provider node with a distance of N. These two strategies increase availability and decrease response time at the expense of using more bandwidth.

Figure 2 . 4 :

 24 Figure 2.4: An example hybrid data grid architecture (sibling tree).

Figure 2

 2 Figure 2.5: An example data grid architecture with scale-free topology.

2. 3 .

 3 DATA REPLICATION IN CLOUD SYSTEMS 55 large-scale data, having low response time and high availability is crucial for the tenants. As in many systems, a number of data replication strategies have been proposed(Alami Milani and Jafari Navimipour, 2016;[START_REF] Tabet | Data replication in cloud systems: A survey[END_REF] to improve the service quality through SLA-awareness in the cloud systems.

  Performance Objective with Economic Consideration[START_REF] Kumar | SWORD: workload-aware data placement and replica selection for cloud data management systems[END_REF] proposed SWORD, a workload-aware data placement and replica selection scheme. Authors introduced a new metric named query span, which is the average number of nodes used in execution of a query. Their approach aims to minimize query span in order to reduce the communication overhead, resource consumption, energy footprint, and transaction cost. They claim that SWORD deals with performance degradation with incremental repartitioning of data. Although provider profit is not a focus of this study, the authors show the effectiveness of their work by doing an experimental analysis to measure query span and transaction times.

  [START_REF] Xiong | Intelligent management of virtualized resources for database systems in cloud environment[END_REF] present a resource management strategy that uses machine learning techniques to return an optimum amount of profit from the tenants in a multi-tenant cloud database context. They employ a predictive model to determine a CPU and memory allocation configuration that yields a minimum amount of penalty cost for a given workload. The authors vary the number of replicas to balance the cost of hosting and managing the replicas against the improvement in the performance.A dynamic data replication strategy is proposed by Gill and Singh (2016) for a heterogeneous cloud environment. Their strategy keeps performance and availability at a desired level while optimizing the cost of replication. The cost of replication is calculated by the unit replication cost per datacenter and whether a replica is placed there. A metric called replica factor is used to calculate weighted access frequencies. Replica factor is compared with a threshold for making replication decision. Placement of replicas is performed with an optimization technique that gets lowest replication cost with highest value of replicas.[START_REF] Janpet | Reliable and available data replication planning for cloud storage[END_REF] designed a data replication strategy to minimize data access time by finding the shortest access path to data objects. They model access frequency, delay and replication budget to find the closest, most suitable node for replica placement. Replication budget is predefined and it is only used as a limiting factor for the users in such a way to regulate number of replicas. A detailed economic relationship between the users and the cloud provider is not addressed. The experimental study shows that by placing data objects closer to the nodes with high access frequency, response time is improved.

  economy-based architecture. Many existing strategies deal with availability with a minority of them considering performance as well, but studying economic impact of replication is still open for new research. Only a handful of data replication strategies proposed for the cloud take into account performance and economic benefit simultaneously.Studying the related work on data replication served us as an evidence of the need of cost-effective data replication strategies that are specifically tailored for the needs of the cloud systems, including satisfaction of SLA-based performance objectives and profitability of the cloud providers. In other words, the work presented in this chapter further reinforced the motivation behind this thesis.

Figure 3 . 1 :

 31 Figure 3.1: An example cloud topology showing regions and subregions (datacenters).

First

  item on the agenda of any data replication strategy should be correctly identifying what data to replicate. Especially in database query processing, a query may require multiple relations during the execution. A replication strategy should correctly identify if any of these relations poses a bottleneck that may hamper the response time of the query. Incorrectly identifying what to replicate would just result in wasted resources without any actual benefit for performance. In the proposed strategy this step is handled by the response time estimation model.

  {datacenter that offers the lowest cost with the new replica} 8: for all Servers N m ∈ D do 9: if load(N ) < T h load and f reeSpace(N m ) ≥ sizeof (R n,l ) then 10: place on N m {the server with lower-than-threshold load and enough free storage} 11: end if 12: end for in the SLA.

Figure 3 . 2 :

 32 Figure 3.2: Query plans that are considered by the response time estimation model.

Figure 3 . 3 :

 33 Figure 3.3: Pipeline chains in left-deep, right-deep and bushy query plans (Garofalakis and Ioannidis, 1996).

Figure 3 . 4 :

 34 Figure 3.4: Dependencies among pipeline chains in left-deep, right-deep and bushy query plans.

. 5 )

 5 Estimated response time T C of the query Q is the estimated response time of the longest execution branch (in terms of response time) in the pipeline chain tree Y < V, E >. An execution branch in a query plan can consist of a number of pipeline chain that are executed in succession as depicted in Figure 3.4. The response time estimation model takes this into account when dealing with multiple pipeline chains in the query plan.

  So far, the response time estimation dealt with how the pipeline chains are identified, how they consist of multiple operators and how the execution of these operators impact on response time estimation. The actual amount of time consumed by each individual operator has not yet been addressed. During execution, an operator consumes CPU time resources for calculations, e.g. calculating hash tables, I/O resource for data access e.g. performing scans, and network resource for shipping fragments located in remote servers. Each of these resources consume time during query processing, hence the response time of an operator is a combination of the amount of time spent by the consumption of these resources.

3. 5 .

 5 AN ECONOMIC MODEL FOR DB QUERY PROCESSING IN THE CLOUD 101

  read from node N e by N j all queries benefit from stored fragments and replicas, more storage cost should be incurred to the data-intensive queries accordingly. Therefore, an I/O cost calculation (Equation 3.15) is performed in a similar manner as in the network cost calculation. However, this time the unit cost of I/O (ω je ) is used when accessing a fragment on server N e by requestor server N j to consider any potential read or write operations. Since the intermediate relations of pipelined operations are not stored, they are not included in the storage cost. The indices of the unit cost is used to indicate the heterogeneity of different cloud regions having different unit cost values. A storage factor s jenl shows which particular replica is accessed among the many possible replicas of the same fragment, as shown in Equation

  cloud. Some noticeable issues dealt with in preparation of the simulation environment include the following. (i) Having a simulation tool that is capable of simulating database query execution in the cloud with the presence of data replication. (ii) Creation of a simulated cloud topology that reflects a realistic cloud environment, e.g. multiple geographical regions, heterogeneous resource availability etc. (iii) A query load with coherent properties such as arrival rate and average number of joins. Of course, these requirements of the simulation environment also necessitate careful selection of all simulation parameters.

CHAPTER 4 .

 4 PERFORMANCE EVALUATIONsections. These logs are then processed at the end of the simulation to obtain values of the desired metrics. These include, average response time of the queries, total number of replication events, used storage percentage of the entire cloud as well as I/O consumption, network bandwidth consumption and finally the number of SLA violations. Table

Figure 4 . 2 :

 42 Figure 4.2: Response time of the queries during simulation.

Figure 4 . 3 :

 43 Figure 4.3: Consumption of bandwidth with respect to network hierarchy.

4. 3 . 7 Figure 4 . 4 :

 3744 Figure 4.4: Total costs of the provider during the simulation.

Figure 4 .

 4 4 shows the monetary costs of the cloud resources corresponding to their consumptions during the simulation. Apart from penalty and network costs, both strategies yielded similar resource costs. Lower-than-threshold average response time and minimal SLA violations enabled APER to cause less expenditures for the provider in terms of penalties paid to the tenants. Furthermore, having enough replicas in strategic places allowed APER to accumulate cost savings by avoiding high utilization of the expensive network links.

5. 1 .

 1 SUMMARY OF STUDIESreplication is triggered. Therefore, both the performance objective and provider profitability criterion must be simultaneously satisfied in order to replicate data.When data replication takes place, only the fragments that are expected to cause a bottleneck are selected for replication. There fragments are incrementally replicated to more suitable locations in the cloud. The placement of replicas is based on a placement heuristic, which finds candidate servers that are able to satisfy performance objective in a cost-effective manner. All of these replication decisions are made in such a way that reduces the resource consumption in the cloud to reduce the expenditures of the provider.Regarding the cost model and economic model used in the replication decisions, former is responsible for estimating the response time of database queries. Response time estimation model in APER considers the consumption of the cloud resources in left-deep, right-deep and bushy join query plans. Latter model is focused on the profit estimation for the provider and it is based on the estimation of both the revenues and expenditures of the provider when executing a tenant query. Based on predicted resource consumptions, APER estimates the monetary cost of executing each query while expected revenue is calculated from the rent collected from the tenants.

  Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

	32	CHAPTER 2. STATE OF THE ART
		2.3.2 Data Replication for Performance Objective without Eco-
		nomic Consideration . . . . . . . . . . . . . . . . . . . . 60
		2.3.3 Data Replication for Performance Objective with Eco-
		nomic Consideration . . . . . . . . . . . . . . . . . . . . 63
		2.3.4 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
		2.4
		Contents
		2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
		2.2 Data Replication in Data Grid Systems . . . . . . . . . . . . . . 34
		2.2.1 Existing Classifications . . . . . . . . . . . . . . . . . . . 35
		2.2.2 Proposed Classification . . . . . . . . . . . . . . . . . . . 38
		2.2.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
		2.3 Data Replication in Cloud Systems . . . . . . . . . . . . . . . . 54
		2.3.1 Data Replication to Satisfy Objectives Other Than Per-
		formance . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

  is another data replication strategy that improves service quality by satisfying availability. Two data availability metrics, System File Missing Rate (SFMR) and System Bytes Missing Rate (SBMR) are proposed to represent the ratio of the missing number of files and amount of data to total files, respectively. All files have weights according to their availability, number of predicted future accesses, number of copies, and size. The files with lower weights are called cold data and files with higher weights are called hot data. During replica replacement, cold data is deleted first, and hot data has the greater probability of replication.

  Contents 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.2 Cloud Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.3 Data Replication Issues . . . . . . . . . . . . . . . . . . . . . . . 74 3.3.1 Replication Decision . . . . . . . . . . . . . . . . . . . . 75 3.3.2 Replication Degree . . . . . . . . . . . . . . . . . . . . . 77

3.3.3 Replica Placement . . . . . . . . . . . . . . . . . . . . . 79 3.3.4 Replica Retirement . . . . . . . . . . . . . . . . . . . . . 82 3.4 A Cost Model for DB Query Processing . . . . . . . . . . . . . . 83 3.4.1 Response Time Estimation . . . . . . . . . . . . . . . . . 84 3.4.2 Resource Consumption . . . . . . . . . . . . . . . . . . . 91 3.5 An Economic Model for DB Query Processing in the Cloud . . . 96 3.5.1 Estimating Provider Profit . . . . . . . . . . . . . . . . . 97 3.5.2 Estimating Provider Revenue . . . . . . . . . . . . . . . 99 3.5.3 Estimating Provider Expenditures . . . . . . . . . . . . . 100 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

  is fragmented into l fragments as R n = {R n,1 , R n,2 , ..., R n,l }, with replicas on j servers as N = {N 1 , N 2 , ..., N j }; the operator O i,k will be executed on each of this fragments in parallel as O j i,k . In this case, the estimated response time of O i,k is determined by the longest estimated amount of time it takes for O i,k to execute on a certain particular fragment R j n,l as shown in Equation3.4.

are executed in a pipeline. Let an operator O i,k to require a relation R n for processing. Assuming that the relation R n

Table 4

 4

	.2: Simulation results.
	Replication strategy	APER CDRM
	Average response time (s)	64.7	351.7
	Number of replications	908	796
	Storage use (%)	22	14
	Inter-region transfer (GB)	27.50 335.53
	Intra-region transfer (GB)	301.05 149.71
	Intra-datacenter transfer (GB) 302.25 147.07
	Number of SLA violations	533	5005

  Contents 5.1 Summary of Studies . . . . . . . . . . . . . . . . . . . . . . . . . 128 5.2 Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . 130

	128	CHAPTER 5. CONCLUSION AND FUTURE WORK
		127

  Abdullah, Mohamed Othman, Hamidah Ibrahim, Md Nasir Sulaiman, and Abu Talib Othman. Decentralized replication strategies for P2P based scientific data grid. In International Symposium on Information Technology (ITSim 2008), volume 3, pages 1-8. IEEE, 2008. ISBN 9781424423286. Abdul Rahman Abdurrab and Tao Xie. FIRE: A file reunion based data replication strategy for data grids. In 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, pages 215-223. IEEE, 2010. ISBN 978-1-4244-6987-1. doi: 10.1109/CCGRID.2010.12. Abdallah Abouzamazem and Paul Ezhilchelvan. Efficient inter-cloud replication for high-availability services. In 2013 IEEE International Conference on Cloud Engineering (IC2E), pages 132-139. IEEE, mar 2013. ISBN 978-0-7695-4945-3. doi: 10.1109/IC2E.2013.27. Lada A. Adamic and Bernardo A. Huberman. Zipf's law and the internet. Glottometrics, 3(1):143-150, 2002. Arif Ahmed and Abadhan Saumya Sabyasachi. Cloud computing simulators: A detailed survey and future direction. In Souvenir of the 2014 IEEE International Advance Computing Conference, IACC 2014, pages 866-872, 2014. ISBN 978-1-4799-2572-8. doi: 10.1109/IAdCC.2014.6779436. Bahareh Alami Milani and Nima Jafari Navimipour. A comprehensive review of the data replication techniques in the cloud environments: Major trends and future directions. Journal of Network and Computer Applications, 64:229-238, 2016. ISSN 10958592. doi: 10.1016/j.jnca.2016.02.005.

http://aws.amazon.com/s3/sla/

https://cloud.google.com/storage/sla

http://azure.microsoft.com/en-us/support/legal/sla/

Acknowledgments

List of Tables

1.1 Publications that resulted from the studies described in the thesis. . .

Chapter 3 Proposed Data Replication

Strategy Abstract

Meeting performance expectations of tenants without sacrificing economic benefit is a tough challenge for cloud providers. In this chapter we discuss APER, the proposed data replication strategy that satisfies both performance and provider profit criteria simultaneously. APER estimates the response time of database queries. If the estimated response time is not acceptable, the bottleneck resource is identified.

Then, the course of action for data replication to resolve the bottleneck through data replication is determined. Data placement is heuristically performed in such a way to satisfy the query response time at a minimal cost for the provider. Consequently, this chapter provides the details of response time and profit estimation models and the actual data replication strategy itself.

Chapter 4 Performance Evaluation Abstract

In this chapter, the performance of APER, the proposed strategy is validated in an experimental evaluation. Throughout the chapter, we first establish the testbed for the performance evaluation. This includes selection and extension of a simulation tool for the tests, preparation of the simulated cloud topology and the generation of query load. Later, the performance of APER is studied in a comparative study against another data replication strategy. The results are analyzed in a discussion throughout the rest of the chapter.

Simulated Query Load

After having a capable simulation tool equipped with a suitable simulation topology, next item on the agenda is to generate the query plans that will serve as the load for the cloud system. This query load is processed by the cloud. Some of these queries may trigger data replication to satisfy the objectives of the studied data replication

Comparison of Data Replication Strategies

APER strategy brings cost-effective satisfaction of query response times as a novel contribution to large-scale data management in the cloud. However, highlighting the impact of this novelty is better conveyed through a comparative performance evaluation study against a more traditional data replication strategy. Hence, we compared the performance of APER with CDRM [START_REF] Wei | Cdrm: A cost-effective dynamic replication management scheme for cloud storage cluster[END_REF], another data replication strategy proposed for cloud systems.

Main focus of CDRM is maintaining a minimum number of replicas to satisfy a given level of availability. It calculates a minimum number of replicas to sat-

Simulation Results

The simulation study is conducted by evaluating the generated query load on the established cloud topology for the duration of time that is described in the simulation parameters. During the simulations, several metrics are collected for further analysis. In the following subsections, some discussion on the collected metrics are given to highlight how the two studied data replication strategies handle the query load by performing replication.

Measured Metrics

The performance of both APER and CDRM is analyzed over some key metrics measured during the simulations. While simulation scenarios are executed by CloudSim, several system parameters are logged to be further discussed in their respective sub-