Search

The last few decades have witnessed the unprecedented growth of large-scale online services. Distributed data storage systems, which are the fundamental building blocks of large-scale online services, are faced with a number of challenging, and often antagonistic, requirements. On the one hand, many distributed data storage systems have shifted away from weak consistency and embraced strong, transactional, semantics in order to tame the ever growing complexity of modern applications. On the other hand, the need for storing sheer amount of data and serving geo-dispersed clients with low latency has driven modern data storage systems to adopt partial replication techniques, often applied to geo-distributed infrastructures. Unfortunately, when employed in the geo-distributed and/or partial replicated settings, state of the art approaches to enforce transactional consistency suffer from severe bottlenecks that strongly hinder their efficiency. This dissertation investigates the use of speculative techniques to enhance performance of partially replicated transactional data stores, with a focus on geo-distributed platforms. With the term speculation, in this dissertation, we refer to the possibility of exposing the updates produced by uncommitted transactions to other transactions and/or to external clients in order to enhance performance. We apply speculation techniques to two fundamental approaches to develop replicated transactional data stores, namely Deferred Update Replication (DUR) and State Machine Replication (SMR). In DUR-based systems, transactions are firstly executed in a node and then propagated to other nodes for a global verification phase, during which pre-commit locks have to be held on data items updated by transactions. The global verification phase can throttle system throughput, especially when there is high conflict. We tackle this problem by introducing Speculative Transaction Replication (STR), a DUR protocol that exploits speculative reads to enhance performance of geo-distributed, partially replicated transactional data stores. The use of speculative reads greatly reduces the ‘effective duration’ of pre-commit locks, thus removing one of the key bottlenecks of DUR-based protocols. However, the indiscriminate use of speculative reads can expose applications to concurrency anomalies that can compromise their correctness in subtle ways. We tackle this issue by introducing Speculative Snapshot Isolation (SPSI), an extension of Snapshot Isolation (SI), which specifies desirable atomicity and isolation guarantees that must hold when using speculative processing techniques. In a nutshell, SPSI guarantees that, applications designed to operate using SI can safely execute atop STR, sheltering programmers from complex concurrency anomalies and source code modification. Our experimental study shows that STR, thanks to the use of speculative reads, yields up to 11× throughput improvements over state-of-the-art approaches that do not adopt speculative techniques. In SMR-based systems, transactions first undergo an ordering phase, then replicas have to guarantee that the result of transaction execution is equivalent to a serial execution according to the produced order from the ordering phase. To ensure this guarantee, existing approaches use a single-thread to execute or serialize transactions, which severely limits throughput especially given the current architectural trend towards massively parallel multi-core processors. This limitation is tackled through the introduction of SPARKLE. SPARKLE is an innovative deterministic concurrency control designed for Partially-Replicated State Machines (PRSMs). SPARKLE untaps the potential parallelism of modern multi-core systems through the use of speculative technique and by avoiding inherently non-scalable designs that rely on a single thread for either executing or scheduling transactions. The key contribution of SPARKLE is a set of techniques that can greatly minimize the frequency of misspeculations and the cost associated with correcting them. Our evaluation shows that SPARKLE achieves up to one order of magnitude throughput gains when compared to state of the art systems. (FSA - Sciences de l'ingénieur) -- UCL, 2020

This work presents STR, a geo-distributed, partially replicated transactional data store, which leverages on novel speculative techniques to mask the inter-replica synchronization latency. The theoretical foundations on top of which we built STR is a novel consistency criterion, which we call SPeculative Snapshot Isolation (SPSI). SPSI extends the well-known Snapshot Isolation semantics in an intuitive, yet rigorous way, by specifying desirable atomicity and isolation guarantees that shelter applications from subtle anomalies that can arise when adopting speculative transaction processing techniques. We assess STR’s performance on up to nine geo-distributed Amazon EC2 data centers, using both synthetic benchmarks as well as complex benchmarks (TPC-C and RUBiS). Our experimental study highlights that STR achieves throughput gains of up to 6⇥ and latency reduction up to 100⇥, in workloads characterized by low inter-data center contention. Furthermore, thanks to self-tuning techniques that automatically adjust the aggressiveness of STR’s speculation degree, STR offers robust performance even when faced with unfavourable workloads that suffer from high misspeculation rates.

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 support for high-level data types (developer friendly API) with safe resolution of concurrent updates (guaranteeing convergence). These guarantees minimise the anomalies caused by parallelism and distribution, thus facilitating the development of applications. This paper presents the protocols for highly available transactions, and an experimental evaluation showing that Cure is able to achieve scalability similar to eventuallyconsistent NoSQL databases, while providing stronger guarantees.

The current web consists of documents that are highly heterogeneous and hard for machines to understand. The SemanticWeb is a progressive movement of the Word Wide Web, aiming at converting the current web of unstructured documents to the web of data. In the Semantic Web, web documents are annotated with metadata using standardized ontology language. These annotated documents are directly processable by machines and it highly improves their usability and usefulness. In Ericsson, similar problems occur. There are massive documents being created with well-defined structures. Though these documents are about domain specific knowledge and can have rich relations, they are currently managed by a traditional search engine, which ignores the rich domain specific information and presents few data to users. Motivated by the Semantic Web, we aim to find standard ways to process these documents, extract rich domain specific information and annotate these data to documents with formal markup languages. We propose this project to develop a domain specific search engine for processing different documents and building explicit relations for them. This research project consists of the three main focuses: examining different domain specific documents and finding ways to extract their metadata; integrating a text search engine with an ontology server; exploring novel ways to build relations for documents. We implement this system and demonstrate its functions. As a prototype, the system provides required features and will be extended in the future.