Search

Global-scale data management(GSDM) empowers systems by providing higher levels of fault-tolerance, read availability, and efficiency in utilizing cloud resources. This has led to the emergence of global-scale data management and event processing. However, the Wide-Area Network (WAN) latency separating datacenters is orders of magnitude larger than typical network latencies, and this requires a reevaluation of many of the traditional design trade-offs of data management systems. Therefore, data management problems must be revisited to account for the new design space. In this dissertation, we propose theoretical foundations to understand the limits imposed by WAN latency on GSDM, and propose practical systems and protocols to minimize the overhead caused by WAN latency. The presented work spans global-scale transaction processing, communication, analytics, and machine learning. In all these directions, the focus is on the trade-off between consistency and latency, where we ask the question: what is the best performance (often latency) we can achieve without compromising the consistency and integrity of data? For transaction processing, we propose a lower-bound formulation for transaction latency that is imposed by the WAN latency. Also, we propose a new paradigm for transaction processing (proactive coordination) that inspired out two proposed protocols, Message Futures and Helios, which can achieve the lower-bound latency. We also propose a communication framework, called Chariots, to scale multi-datacenter communication. Chariots is carefully designed to allow scaling communication while providing a consistent view of the communicated information. Finally, we explore challenges in global-scale analytics and machine learning. Specifically, we propose Ogre, a scalable system for global-scale heterogeneous transactional and analytics workloads. Also, we propose COP, a system designed to speed up machine learning on globally generated data.

Although graph-databases have been assuming an increasing relevance in applications that exhibit strong dependability requirements, including tolerance to malicious faults, few works have addressed Byzantine fault tolerance in this particular context, and previous attempts suffer from lack of flexibility and poor performance. This article describes and evaluates Fireplug, a flexible architecture to build robust geo-replicated graph databases. Fireplug can be configured to tolerate from crash to Byzantine faults, both within and across different datacenters. Furthermore, Fireplug is robust to bugs in existing graph database implementations, as it allows to combine multiple graph database instances in a cohesive manner. Thus, Fireplug can support many different deployments, according to the performance/robustness trade-offs imposed by the target application. Our evaluation shows that Fireplug is able implement Byzantine fault tolerance without penalty when compared to the built-in replication mechanism of Neo4j, which only supports crash faults. Additionally, performance optimizations introduced by Fireplug improve the overall performance by up to 900 percent in geo-replicated scenarios.

As current trends start to move storage and computation to the edge in order to provide support for latency constrained applications, new edge storage systems must emerge that optimise latency and reduce the cost of communication, so that they can provide users with the best possible experience. With this goal in mind, several new storage systems have surfaced that make the most of sophisticated replication techniques and weak consistency models, in particular the causal+ consistency model. A way to build such a system is to use a causal broadcast algorithm to propagate write operations between replicas in an order that is compatible with the causal order. However, existing systems rely on mechanisms that have limitations: they either leverage on static tree topologies, not adapting to scenarios where replicas join or leave the system, or they use metadata that grows linearly with the number of replicas, being therefore incapable of scaling to the hundreds or thousands of (smaller) replicas and, as such, not being suitable for supporting the operation of edge data stores. In this work, we propose a new edge-enabled replication scheme that ensures causal delivery of operations in all replicas and, when used together with CRDTs, guarantees causal+ consistency. Our solution is a decentralised causal broadcast algorithm, ECO SYNC Tree, that makes use of a dynamic tree topology, capable of quickly adapting to nodes joining and leaving the system, to offer causal delivery while using negligible metadata to encode causal dependencies. We present an experimental evaluation of ECO SYNC Tree that shows that our solution captures “the best of both worlds” when it comes to the trade-off between broadcast latency and communication cost in stable environments, and in environments subject to events such as large groups of nodes joining or leaving the system. Moreover, when compared with state-of-the-art broadcast protocols, ECO SYNC Tree proved to be the one that is best suited for edge-based deployment, by exhibiting better performance and scalability in scenarios with high churn rates. Conforme as tendências atuais começam a mover o armazenamento e a computação para a periferia da rede de a maneira suportar aplicações com restrições de latência, devem surgir novos sistemas de armazenamento para este paradigma que otimizem a latência e reduzam o custo de comunicação de forma a proporcionar aos utilizadores a melhor experiência possível. Com esse objetivo em mente, surgiram vários novos sistemas de armazenamento que utilizam técnicas sofisticadas de replicação e modelos de coerência fraca, em particular o modelo de coerência causal+. Uma maneira de construir um destes sistemas é usar um algoritmo de difusão causal para propagar operações de escrita entre réplicas numa ordem que seja compatível com a ordem causal. No entanto, os sistemas existentes usam mecanismos que têm limitações: topologias em árvore estáticas que não se adaptam a cenários em que réplicas se juntam ou saem do sistema, ou metadados que crescem linearmente com o número de réplicas e impedem o sistema de escalar para centenas ou milhares de réplicas, não sendo adequados para suportar sistemas de armazenamento na periferia. Neste trabalho, propomos um novo esquema de replicação adaptado à periferia que entrega operações por ordem causal a todas as réplicas e, quando usado em conjunto com CRDTs, garante coerência causal+. A nossa solução é um algoritmo de difusão causal descentralizado, ECO SYNC Tree, baseado numa topologia em árvore dinâmica capaz de se adaptar rapidamente à entrada e saída de nós do sistema, e que usa metadados de tamanho desprezível para codificar dependências causais. Apresentamos uma avaliação experimental que mostra que a nossa solução captura “o melhor dos dois mundos” no trade-off entre latência de difusão e custo de comunicação, tanto em ambientes estáveis, como em ambientes sujeitos a eventos em que grandes gru- pos de nós entram ou saem do sistema. Além disso, quando comparado com protocolos do estado da arte, ECO SYNC Tree provou ser o mais adequado para ambientes na periferia, exibindo melhor desempenho e escalabilidade em cenários com elevadas taxas de churn.

Immediate response, autonomy and availability is brought to edge applications, such as gaming, cooperative engineering, or in-the-field information sharing, by distributing and replicating data at the edge. However, application developers and users demand the highest possible consistency guarantees, and specific support for group collaboration. To address this challenge, COLONY guarantees Transactional Causal Plus Consistency (TCC+) globally, dovetailing with Snapshot Isolation within edge groups. To help with scalability, fault tolerance and security, its logical communication topology is tree-like, with replicated roots in the core cloud, but with the flexibility to migrate a node or a group. Despite this hybrid approach, applications enjoy the same semantics everywhere in the topology. Our experiments show that local caching and peer groups improve throughput and response time significantly, performance is not affected in offline mode, and that migration is seamless., La distribution et la réplication des données en périphérie du réseau apportent une réponse immédiate, une autonomie et une disponibilité aux applications de périphérie, telles que les jeux, l’ingénierie coopérative ou le partage d’informations sur le terrain. Cependant, les développeurs d’applications et les utilisateurs exigent les meilleures garanties de cohérence possibles, ainsi qu’un support spécifique pour la collaboration de groupe. Pour relever ce défi, Colony garantit la cohérence Transactional Causal Plus Consistency (TCC+) à échelle planétaire, en complément de l’isolation des instantanés au sein des groupes de périphérie. Pour favoriser le passage à l’échelle, la tolérance aux pannes et la sécurité, sa topologie de communication logique est arborescente, avec des racines répliquées dans le nuage principal, mais avec la possibilité de migrer un nœud ou un groupe. Malgré cette approche hybride, les applications bénéficient de la même sémantique partout dans la topologie. Nos expériences montrent que la mise en cache locale et les groupes collaboratifs améliorent considérablement le débit et le temps de réponse, que les performances ne sont pas affectées en mode hors ligne et que la migration est transparente.

International audience; Edge applications, such as gaming, cooperative engineering, or in-the-field information sharing, enjoy immediate response, autonomy and availability by distributing and replicating data at the edge. However, application developers and users demand the highest possible consistency guarantees, and specific support for group collaboration. To address this challenge, Colony guarantees Transactional Causal Plus Consistency (TCC+) globally, strengthened to Snapshot Isolation within edge groups. To help with scalability, fault tolerance and security, its logical communication topology is forest-like, with replicated roots in the core cloud, but with the flexibility to migrate a node or a group. Despite this hybrid approach, applications enjoy the same semantics everywhere in the topology. Our experiments show that local caching and peer groups improve throughput and response time significantly, performance is not affected in offline mode, and that migration is seamless.

Modern web applications replicate their data across the globe and require strong consistency guarantees for their most critical data. These guarantees are usually provided via state-machine replication (SMR). Recent advances in SMR have focused on leaderless protocols, which improve the availability and performance of traditional Paxos-based solutions. We propose Tempo - a leaderless SMR protocol that, in comparison to prior solutions, achieves superior throughput and offers predictable performance even in contended workloads. To achieve these benefits, Tempo timestamps each application command and executes it only after the timestamp becomes stable, i.e., all commands with a lower timestamp are known. Both the timestamping and stability detection mechanisms are fully decentralized, thus obviating the need for a leader replica. Our protocol furthermore generalizes to partial replication settings, enabling scalability in highly parallel workloads. We evaluate the protocol in both real and simulated geo-distributed environments and demonstrate that it outperforms state-of-the-art alternatives.

Existing approaches to tolerate Byzantine faults in geo-replicated environments require systems to execute complex agreement protocols over wide-area links and consequently are often associated with high response times. In this paper we address this problem with Spider, a resilient replication architecture for geo-distributed systems that leverages the availability characteristics of today's public-cloud infrastructures to minimize complexity and reduce latency. Spider models a system as a collection of loosely coupled replica groups whose members are hosted in different cloud-provided fault domains (i.e., availability zones) of the same geographic region. This structural organization makes it possible to achieve low response times by placing replica groups in close proximity to clients while still enabling the replicas of a group to interact over short-distance links. To handle the inter-group communication necessary for strong consistency Spider uses a reliable group-to-group message channel with first-in-first-out semantics and built-in flow control that significantly simplifies system design., Comment: 25 pages, extended version of Middleware 2020 paper

Online applications now routinely replicate their data at multiple sites around the world. In this paper we present Atlas, the first state-machine replication protocol tailored for such planet-scale systems. Atlas does not rely on a distinguished leader, so clients enjoy the same quality of service independently of their geographical locations. Furthermore, client-perceived latency improves as we add sites closer to clients. To achieve this, Atlas minimizes the size of its quorums using an observation that concurrent data center failures are rare. It also processes a high percentage of accesses in a single round trip, even when these conflict. We experimentally demonstrate that Atlas consistently outperforms state-of-The-Art protocols in planet-scale scenarios. In particular, Atlas is up to two times faster than Flexible Paxos with identical failure assumptions, and more than doubles the performance of Egalitarian Paxos in the YCSB benchmark., H2020 - Horizon 2020 Framework Programme(825184)

This paper presents a causally consistent key-value store Orion, which uses a novel protocol for Read Only Transactions (ROT). Unlike most of the existing protocols, Orion uses only one round of communication in the best case, and not more than two rounds in the worst case. We provide a theoretical bound on its communication complexity and qualitatively compare it with recent ROT protocols. We also quantitatively compare Orion with state-of-the-art protocol CausalSpartanX and illustrate that Orion achieves up to 1.7x higher throughput and generates 10x fewer messages on widely-used YCSB workload.

In geo-replicated systems, the heterogeneous latencies of connections between replicas limit the system's ability to achieve consensus fast. State machine replication (SMR) protocols can be refined for their deployment in wide-area networks by using a weighting scheme for active replication that employs additional replicas and assigns higher voting power to faster replicas. Utilizing more variability in quorum formation allows replicas to swiftly proceed to subsequent protocol stages, thus decreasing consensus latency. However, if network conditions vary during the system's lifespan or faults occur, the system needs a solution to autonomously adjust to new conditions. We incorporate the idea of self-optimization into geographically distributed, weighted replication by introducing AWARE, an automated and dynamic voting weight tuning and leader positioning scheme. AWARE measures replica-to-replica latencies and uses a prediction model, thriving to minimize the system's consensus latency. In experiments using different Amazon EC2 regions, AWARE dynamically optimizes consensus latency by self-reliantly finding a fast weight configuration yielding latency gains observed by clients located across the globe.

Most of today’s Internet applications generate vast amounts of data (typically, in the form of event logs) that needs to be processed and analyzed for detailed reporting, enhancing user experience and increasing monetization. In this paper, we describe the architecture of Ubiq, a geographically distributed framework for processing continuously growing log files in real time with high scalability, high availability and low latency. The Ubiq framework fully tolerates infrastructure degradation and data center-level outages without any manual intervention. It also guarantees exactly-once semantics for application pipelines to process logs as a collection of multiple events. Ubiq has been in production for Google’s advertising system for many years and has served as a critical log processing framework for several dozen pipelines. Our production deployment demonstrates linear scalability with machine resources, extremely high availability even with underlying infrastructure failures, and an end-to-end latency of under a minute.

Existing state machine replication protocols are confronting two major challenges in geo-replication: (1) limited performance caused by load imbalance, and (2) severe performance degradation in heterogeneous environments or under high-contention workloads. This paper presents a new semi-decentralized approach to addressing both the challenges at the same time. Our protocol, SDPaxos, divides the task of a replication protocol into two parts: durably replicating each command across replicas without global order, and ordering all commands to enforce the consistency guarantee. We decentralize the process of replicating commands, which accounts for the largest proportion of load, to provide high performance. In contrast, we centralize the process of ordering commands, which is lightweight but needs a global view, for better performance stability against heterogeneity or contention. The key novelty lies in that SDPaxos achieves the optimal one-round-trip latency under realistic configurations, despite the two separated steps, replicating and ordering, which are both based on Paxos. We also design a recovery protocol to do rapid failover under failures, and a series of optimizations to boost performance. We show via a prototype implementation the significant advantage of SDPaxos on both throughput and latency, facing different environments and workloads.

International audience; Large-scale applications are ever-increasingly geo-distributed. Maintaining the highest possible data locality is crucial to ensure high performance of such applications. Dynamic replication addresses this problem by dynamically creating replicas of frequently accessed data close to the clients. This data is often stored in decentralized storage systems such as Dynamo or Voldemort, which offer support for mutable data. However, existing approaches to dynamic replication for such mutable data remain centralized, thus incompatible with these systems. In this paper we introduce a write-enabled dynamic replication scheme that leverages the decentralized architecture of such storage systems. We propose an algorithm enabling clients to locate tentatively the closest data replica without prior request to any metadata node. Large-scale experiments on various workloads show a read latency decrease of up to 42% compared to other state-of-the-art, caching-based solutions.

Eventually consistent systems can be made more consistent by reducing the time until a write is fully replicated, thereby improving global update visibility. While gossip-based anti-entropy methods scale well, random selection of anti-entropy partners is less than efficient. Moreover, while eventual consistency may be consistent enough in a single data center, geographic replication increases visibility latency and leads to externally observable inconsistencies. In this paper, we explore an improvement to pairwise, bilateral anti-entropy; instead of uniform random selection, we introduce reinforcement learning mechanisms to assign selection probabilities to replicas most likely to have information. The result is more efficient replication, faster visibility, and stronger eventual consistency while maintaining high availability and partition tolerance.

Distributed storage systems are a fundamental component of large-scale Internet services. To keep up with the increasing expectations of users regarding availability and latency, the design of data storage systems has evolved to achieve these properties, by exploiting techniques such as partial replication, geo-replication and weaker consistency models. While systems with these characteristics exist, they usually do not provide all these properties or do so in an inefficient manner, not taking full advantage of them. Additionally, weak consistency models, such as eventual consistency, put an excessively high burden on application programmers for writing correct applications, and hence, multiple systems have moved towards providing additional consistency guarantees such as implementing the causal (and causal+) consistency models. In this thesis we approach the existing challenges in designing a causally consistent replication protocol, with a focus on the use of geo and partial data replication. To this end, we present a novel replication protocol, capable of enriching an existing geo and partially replicated datastore with the causal+ consistency model. In addition, this thesis also presents a concrete implementation of the proposed protocol over the popular Cassandra datastore system. This implementation is complemented with experimental results obtained in a realistic scenario, in which we compare our proposal withmultiple configurations of the Cassandra datastore (without causal consistency guarantees) and with other existing alternatives. The results show that our proposed solution is able to achieve a balanced performance, with low data visibility delays and without significant performance penalties.

We propose a novel consistency model called external causality, which aims at making external consistency affordable for geo-replicated systems. In this short paper, we (i) outline this idea---informally defining external causality, and (ii) motivate it with two simple examples that illustrate how developers of cloud services may benefit from it.

The paper describes and evaluates Fireplug, a flexible architecture to build robust geo-replicated graph databases. Fireplug can be configured to tolerate from crash to Byzantine faults, both within and across different datacenters. Furthermore, Fireplug is robust to bugs in existing graph database implementations, as it allows to combine multiple graph databases instances in a cohesive manner. Thus, Fireplug can support many different deployments, according to the performance/robustness tradeoffs imposed by the target application. Our evaluation shows that Fireplug can implement Byzantine fault tolerance in geo-replicated scenarios and still outperform the built-in replication mechanism of Neo4j, which only supports crash faults.

Distributed storage systems are a fundamental component of large-scale Internet services. To keep up with the increasing expectations of users regarding availability and latency, the design of data storage systems has evolved to achieve these properties by exploiting techniques such as partial replication, geo-replication, and weaker consistency models. How to combine all these techniques in a single solution in a practical and efficient way is highly challenging. In this paper we propose a novel replication scheme that can offer causal+ consistency in a geo-distributed scenario with partial replication, where datacenters replicate different portions of the entire database. We leverage on a recently proposed methodology that decouples the propagation of data and causality-tracking metadata. Our solution presents a novel causal consistency tracking and enforcing algorithm, focusing on maximizing parallelism in the execution of remote operations which, as we show, has a significant influence on the performance of a partially replicated system. We also propose and implement a design to integrate our solution in the popular Cassandra database. Experimental results show that, by exploring a new position in the trade-off between throughput and data visibility (by balancing the execution of local and remote operations, respectively), our solution presents overall good performance.

The amount of data being processed in Data Centres (DCs) keeps growing at an enormous rate so that full replication may start being impractical. One way to increase data availability can be accomplished using replication between DCs so data may be accessed locally, if possible, which allows to recover in the presence of site failures and reduce access costs. This means that replicating the data only in some of the DCs is becoming more critical to reduce the costs of keeping the data consistent or eventually consistent and still maintaining a high availability (scalability) and low access costs. The data locations overall the DCs must be determined dynamically giving the changing patterns of read and write requests for the data to be replicated. Given that the problem of finding an optimal replication schema in a general network has been shown to be NP-complete for the static case, it is unlikely to be able to generate a general algorithm to find efficient solutions to the dynamic problem. An adaptive bio-inspired replication strategy is presented here, which is completely decentralised, adaptive, inspired on the Ant Colony algorithm, and event-driven. Also, the replication protocol is independent of the strategy implemented but it is guided by the strategy.

Availability of the database is of utmost importance to any application’s experience. In cases in which the user engagement is critical, and the availability of the database in data-driven application is most important, one must ensure the availability and scalability of the database. Among examples of data-driven applications problems could be the following: an e-commerce application with a plethora of easy-to-use and marquee features going down every time a user tries to make a purchase, because something in the database is not available; a billing solution for a hospital that leaves patients standing in line to make payments, owing to a database instance not being available; or a transport company with footprints across the globe seeking to access the system, but apart from that at the main location, the system performs badly, owing to latency issues. So, how do you ensure that a database is available? How do you ensure that the database is always deployed nearest to the relevant application? And how do you achieve the lowest possible latency?

Causal consistency is an intermediate consistency model that can be achieved together with high availability and high-performance requirements even in presence of network partitions. In the context of partitioned data stores, it has been shown that implicit dependency tracking using clocks is more efficient than explicit dependency tracking by sending dependency check messages. Existing clock-based solutions depend on monotonic psychical clocks that are closely synchronized. These requirements make current protocols vulnerable to clock anomalies. In this paper, we propose a new clock-based algorithm, CausalSpartan, that instead of physical clocks, utilizes Hybrid Logical Clocks (HLCs). We show that using HLCs, without any overhead, we make the system robust on physical clock anomalies. This improvement is more significant in the context of query amplification, where a single query results in multiple GET/PUT operations. We also show that CausalSpartan decreases the visibility latency for a given data item comparing to existing clock-based approaches. In turn, this reduces the completion time of collaborative applications where two clients accessing two different replicas edit same items of the data store. Like previous protocols, CausalSpartan assumes that a given client does not access more than one replica. We show that in presence of network partitions, this assumption (made in several other works) is essential if one were to provide causal consistency as well as immediate availability to local updates.

International audience; Pour augmenter les performances et la disponibilité, les bases de données sont généralement répliquées sur différents serveurs au sein de centres de données à travers le monde. Cependant, la réplication implique quelques problèmes de cohérence. La cohérence causale est un choix in-téressant pour construire ce modèle de bases de données. Elle permet aux clients d'observer un état cohérent par rapport à leurs écritures, en incluant les opérations qu'ils ont précédem-ment observé, tout en minimisant les anomalies pour le programmeur. Cependant, les mises en oeuvre actuelles de la cohérence causale sont susceptibles de connaitre des ralentissements en chaîne à l'échelle de plusieurs centres de données. Ce papier décrit la conception d'un sys-tème causalement cohérent, évolutif, et non exposé à l'impact que peut avoir un serveur lent ou défaillant, sur la disponibilité des données.

Complete data center failures may occur due to disastrous events such as earthquakes or fires. To attain robustness against such failures and reduce the probability of data loss, data must be replicated in another data center sufficiently geographically separated from the original data center. Implementing geo-replication is expensive as every data update operation in the original data center must be replicated in the backup. Running the application and the replication service in parallel is cost effective but creates a trade-off between potential replication consistency and data loss and reduced application performance due to network resource contention. We model this trade-off and provide a control-theoretical solution based on Model Predictive Control to dynamically allocate network bandwidth to accommodate the objectives of both replication and application data streams. We evaluate our control solution through simulations emulating the individual services, their traffic flows, and the shared network resource. The MPC solution is able to maintain a consistent performance over periods of persistent overload, and is quickly able to indiscriminately recover once the system return to a stable state. Additionally, the MPC balances the two objectives of consistency and performance according to the proportions specified in the objective function.

Large Web applications usually require replicating data across geo-distributed datacenters to achieve high locality, durability and availability. However, maintaining strong consistency in geo-replicated systems usually suffers from long latency due to costly coordination across datacenters. Among others, transaction chopping is an effective and efficient approach to cope with such a challenge. In this paper, we propose DTC (Dynamic Transaction Chopping), a novel technique that chops transactions and checks their conflicts in a dynamic and automatic way, during application execution. DTC mainly consists of two parts: a dynamic chopper that chops transaction dynamically according to data partition scheme, and a conflict detection algorithm for determining the safety of the dynamic chopping. Compared with existing transaction chopping technique for geo-replicated systems, DTC has several advantages, including transparency to programmers, flexibility in conflict analysis, high degree of piecewise execution, and adaptability to dynamic partition schemes. We implement our DTC technique and conduct experiments to examine the correctness of DTC and evaluate its performance. The experiment results show that our DTC technique can achieve much more piecewise execution than the existing chopping approach does, and reduce execution time obviously.

Developers of cloud-scale applications face a difficult decision of which kind of storage to use, summarised by the CAP theorem. Currently the choice is between classical CP databases, which provide strong guarantees but are slow, expensive, and unavailable under partition; and NoSQL-style AP databases, which are fast and available, but too hard to program against. We present an alternative: Cure provides the highest level of guarantees that remains compatible with availability. These guarantees include: causal consistency (no ordering anomalies), atomicity (consistent multi-key updates), and high-level data types (developer friendly) with safe resolution of concurrent updates (guaranteeing convergence). These guarantees minimise the anomalies caused by parallelism and distribution, and facilitate the development of applications. This paper presents the protocols for highly available transactions , and an experimental evaluation showing that Cure is able to achieve performance similar to eventually-consistent NoSQL databases, while providing stronger guarantees., Les développeurs d’application à très grande échelle (dans le nuage) doivent prendre la difficile décision de quel type de stockage utiliser, selon le théorème CAP. Aujourd’hui, ils n’ont le choix qu’entre les bases de données classiques de type CP, qui donnent des garanties fortes, mais sont lentes, chères, et non disponible en cas de partition réseau ; et les bases de données NoSQL de type AP, qui sont rapides et disponibles, mais complexifient le développement applicatif. Nous proposons une troisième voie : la base de données répartie Cure, qui offre les garanties les plus fortes compatibles avec la dispo- nibilité. Il s’agit des garanties suivantes : cohérence causale (pas d’ordonnancement anormal), atomicité (mises-à-jour multi-clefs mutuellement cohérentes), et types de données de haut niveau (aidant les dé- veloppeurs) avec résolution sûre des mises-à-jour concurrentes (garantie de convergence). Ces garanties minimisent les anomalies causées par le parallélisme et la répartition, et facilitent le développement ap- plicatif. Ce rapport présente les protocoles utilisés pour rendre les transactions hautement disponibles, ainsi qu’une évaluation expérimentale, qui montre que Cure atteint des performances proches des bases de données NoSQL à cohérence à terme, tout en offrant des garanties plus fortes.

International audience; Large-scale scientific experiments increasingly rely on geo-distributed clouds to serve relevant data to scientists worldwide with minimal latency. State-of-the-art caching systems often require the client to access the data through a caching proxy, or to contact a metadata server to locate the closest available copy of the desired data. Also, such caching systems are inconsistent with the design of distributed hash-table databases such as Dynamo, which focus on allowing clients to locate data independently. We argue there is a gap between existing state-of-the-art solutions and the needs of geographically distributed applications, which require fast access to popular objects while not degrading access latency for the rest of the data. In this paper, we introduce a probabilistic algorithm allowing the user to locate the closest copy of the data efficiently and independently with minimal overhead , allowing low-latency access to non-cached data. Also, we propose a network-efficient technique to identify the most popular data objects in the cluster and trigger their replication close to the clients. Experiments with a real-world data set show that these principles allow clients to locate the closest available copy of data with small memory footprint and low error-rate, thus improving read-latency for non-cached data and allowing hot data to be read locally.

This paper focuses on the problem of implementing web applications on top of weakly consistent geo-replicated systems. Several techniques, such as CRDTs, have been proposed to achieve state convergence on a per-object and per-data type basis. However, that does not guarantee application correctness, as convergence rules applied individually at each object may lead to an invalid state.We advocate that it is possible to address these problems and implement correct applications under weak consistency. To that end, it is necessary to combine CRDTs with novel semantics, judiciously select the CRDTs that are used by applications, and transform application operations to guarantee that convergence rules, applied on a per-object basis, always lead to valid application states. Achieving this is complex and requires tools to help programmers tame the complexity of programming on top of weak consistency and make the technology more accessible.In the presentation of this work we make a demonstration of a prototype tool that is capable of detecting concurrency conflicts on applications and propose transformations to make them conflict-free.

Conflict-free Replicated Data Types (CRDTs) are high-level data types that can be replicated with minimal coordination among replicas due to its confluent semantics. This property makes CRDTs specially appealing for geo-replicated settings. Different approaches, such as state transfer and operation forwarding, have been proposed to propagate updates among replicas, with different tradeoffs among the amount of network traffic generated and the staleness of local information. This paper proposes and evaluates techniques to automatically adapt a CRDT implementation, such that the best approach is used, based on the application needs (captured by a SLA) and the observed system configuration. Our techniques have been integrated in SwiftCloud, a state of the art geo-replicated store based on CRDTs.

Existing partial geo-replication systems do not always provide optimal cost or latency, because their replication decisions are based on statically established data access popularity metrics, regardless of the application types. We demonstrate that additional reduction in cost and latency can be achieved by 1) using the right object attributes for making replication decisions for each type of application, 2) using multi-attribute-based replications, and 3) combining the popularity-based but reactive approach with the more random but proactive approach to data replication. Toward this end, we propose Acorn, an Attribute-based COntinuous partial geo-ReplicatioN system, and its prototype implementation based on Apache Cassandra. Experiments with two types of global-scale, data-sharing applications demonstrate up to 54% and 90% cost overhead reduction over existing systems or 38% and 91% latency overhead reduction.

Client-side apps (e.g., mobile or in-browser) need cloud data to be available in a cache, for both reads and updates. The cache should use resources sparingly, be consistent and fault-tolerant. The system needs to scale to high numbers of unreliable and resource-poor clients, and large database. The SwiftCloud distributed object database is the first to provide fast reads and writes via a causally-consistent client-side local cache. It is thrifty in resources and scales well, thanks to consistent versioning provided by the cloud, using small and bounded metadata. It remains available during faults, switching to a different data centre when the current one is not responsive, while maintaining its consistency guarantees. This paper presents the SwiftCloud algorithms, design, and experimental evaluation. It shows that client-side apps enjoy the high performance and availability, under the same guarantees as a remote cloud data store, at a small cost.; Les applications localisées côté client, par exemple les applications mobiles ou les applications dans le navigateur, ont besoin que les données du nuage soient disponibles dans un cache local, aussi bien pour l'écriture que pour la lecture. Ce cache doit utiliser les ressources avec économie, être cohérent, et tolérer les fautes. Le système doit passer à l'échelle d'un nombre élevé de clients non fiables et disposant de peu de ressources, et d'une base de données de grande capacité. La base de données répartie SwiftCloud est la première qui permet les lectures et les écritures rapides et cohérentes par l'intermédiaire d'un cache situé côté client. Elle utilise les ressources avec parcimonie, et passe bien à l'échelle, grâce au fait que le nuage sert des versions cohérentes tout en ne nécessitant que des métadonnées de taille petite et bornée. Les données restent disponibles pendant les fautes de réseau, car, quand le centre de calcul courant ne répond pas, le cache peut passer à un nouveau centre de calcul sans violer ses garanties de cohérence. Le présent papier présente les algorithmes, la conception et l'évaluation expérimentale de SwiftCloud. Il montre que le système fournit aux applications côté client, à la fois des performances et une disponibilité élevées, et à la fois les mêmes garanties qu'un stockage distant dans le nuage, à un faible coût.

Causal consistency is a consistency criteria of practical relevance in geo-replicated settings because it provides well-defined semantics in a scalable manner. In fact, it has been proved that causal consistency is the strongest consistency model that can be enforced in an always-available system. Previous approaches to provide causal consistency, which successfully tackle the problem under full geo-replication, have unveiled the inherent tradeoff between the concurrency that the system allows and the size of the metadata needed to enforce causality. When the metadata is compressed, information about concurrency may be lost, creating false dependencies, i.e., the encoding may suggest a causal relation that does not exist in reality. False dependencies may cause artificial delays when processing requests, and decrease the quality of service experienced by the clients.Nevertheless, whether is possible to design a scalable solution that only uses an almost negligible amount of metadata and it is still capable of achieving high levels of concurrency under partial geo-replication, an increasingly relevant setting, remains as a challenging and interesting open research question. This position paper reports on the on-going development of Saturn, a metadata service for geo-replicated systems, that aims at mitigating the effects of false dependencies while keeping the metadata size small (even for challenging settings as partial geo-replication).

We describe PNUTS, a massively parallel and geographically distributed database system for Yahoo!'s web applications. PNUTS provides data storage organized as hashed or ordered tables, low latency for large numbers of concurrent requests including updates and queries, and novel per-record consistency guarantees. It is a hosted, centrally managed, and geographically distributed service, and utilizes automated load-balancing and failover to reduce operational complexity. The first version of the system is currently serving in production. We describe the motivation for PNUTS and the design and implementation of its table storage and replication layers, and then present experimental results.

Co-located with SRDS; International audience; The Mobile-Edge Computing standard promises co-locating edge servers with mobile phone base stations. Web services running on this new ecosystem will have to address the challenges of this new model in order to see its benefits. In this work, we briefly discuss design guidelines for scaling strongly consistent geo-distributed databases to the MEC environment. Following these guidelines, we present the design of a MEC database tailored for a specific kind of web services and a protocol for ensuring transactional non-monotonic snapshot isolation (NMSI) at MEC scale.

International audience; Geo-replicated databases often offer high availability and low latency by relying on weak consistency models. The inability to enforce invariants across all replicas remains a key shortcoming that prevents the adoption of such databases in several applications. In this paper we show how to extend an eventually consistent cloud database for enforcing numeric invariants. Our approach builds on ideas from escrow transactions, but our novel design overcomes the limitations of previous works. First, by relying on a new replicated data type, our design has no central authority and uses pairwise asynchronous communication only. Second, by layering our design on top of a fault-tolerant database, our approach exhibits better availability during network partitions and data center faults. The evaluation of our prototype, built on top of Riak, shows much lower latency and better scalability than the traditional approach of using strong consistency to enforce numeric invariants.

State machine replication is a fundamental technique for implementing consistent fault-tolerant services. In the last years, several protocols have been proposed for improving the latency of this technique when the replicas are deployed in geographically-dispersed locations. In this work we evaluate some representative optimizations proposed in the literature by implementing them on an open-source state machine replication library and running the experiments in geographically-diverse PlanetLab nodes and Amazon EC2 regions. Interestingly, our results show that some optimizations widely used for improving the latency of geo-replicated state machines do not bring significant benefits, while others - not yet considered in this context - are very effective. Based on this evaluation, we propose WHEAT, a configurable crash and Byzantine fault-tolerant state machine replication library that uses the optimizations we observed as most effective in reducing SMR latency. WHEAT employs novel voting assignment schemes that, by using few additional spare replicas, enables the system to make progress without needing to access a majority of replicas. Our evaluation shows that a WHEAT system deployed in several Amazon EC2 regions presents a median latency up to 56% lower than a "normal" SMR protocol.

Client-side apps (e.g., mobile or in-browser) need cloud data to be available in a cache, for both reads and updates. The cache should use resources sparingly, be consistent and fault-tolerant. The system needs to scale to high numbers of unreliable and resource-poor clients, and large database. The SwiftCloud distributed object database is the first to provide fast reads and writes via a causally-consistent client-side local cache. It is thrifty in resources and scales well, thanks to consistent versioning provided by the cloud, using small and bounded metadata. It remains available during faults, switching to a different data centre when the current one is not responsive, while maintaining its consistency guarantees. This paper presents the SwiftCloud algorithms, design, and experimental evaluation. It shows that client-side apps enjoy the high performance and availability, under the same guarantees as a remote cloud data store, at a small cost.; Les applications localisées côté client, par exemple les applications mobiles ou les applications dans le navigateur, ont besoin que les données du nuage soient disponibles dans un cache local, aussi bien pour l'écriture que pour la lecture. Ce cache doit utiliser les ressources avec économie, être cohérent, et tolérer les fautes. Le système doit passer à l'échelle d'un nombre élevé de clients non fiables et disposant de peu de ressources, et d'une base de données de grande capacité. La base de données répartie SwiftCloud est la première qui permet les lectures et les écritures rapides et cohérentes par l'intermédiaire d'un cache situé côté client. Elle utilise les ressources avec parcimonie, et passe bien à l'échelle, grâce au fait que le nuage sert des versions cohérentes tout en ne nécessitant que des métadonnées de taille petite et bornée. Les données restent disponibles pendant les fautes de réseau, car, quand le centre de calcul courant ne répond pas, le cache peut passer à un nouveau centre de calcul sans violer ses garanties de cohérence. Le présent papier présente les algorithmes, la conception et l'évaluation expérimentale de SwiftCloud. Il montre que le système fournit aux applications côté client, à la fois des performances et une disponibilité élevées, et à la fois les mêmes garanties qu'un stockage distant dans le nuage, à un faible coût.