In this paper, we introduce KDB, a novel persistent key-value data store (a concurrent index) with rich linearizable semantics. In contrast to state-of-the-art systems which offer only lookup and put/remove operations, KDB supports both snapshots (which are used by range scans) and atomic batch updates—put and remove operations that are executed atomically. Despite its rich semantics, our system offers highly scalable performance across varied workloads thanks to its unique multiversioned architecture. It features a hybrid lock-CAS synchronization mechanism that allows lookup operations and scans to proceed in a wait-free fashion. Under the hood, KDB maintains all key-value entries in persistent memory (PM) for failure atomicity, but it heavily relies on an efficient DRAM-backed multiversion index based on skip lists to hide the costs of accessing PM. For better PM utilization, entries are arranged in PM in preallocated arrays that occasionally undergo compaction.

In this paper we introduce Jiffy, the first lock-free, linearizable, ordered key-value index that offers both (1) batch updates, i.e., put and remove operations that are executed atomically, and (2) consistent snapshots used by, e.g., range scan operations. Jiffy is built as a multiversioned lock-free skip list and relies on system-provided timestamps (e.g., on x86_64 obtained through the Time Stamp Counter register) to generate version numbers at minimal cost. For faster skip list traversals and better utilization of CPU caches, key-value entries are grouped into immutable objects called revisions. By (automatically) controlling the size of new revisions, our index can adapt to varying contention levels (e.g., smaller revisions are more suited for write-heavy workloads). Structure modifications to the index, which result in changing the size of revisions, happen through (lock-free) skip list node split and merge operations that are carefully coordinated with the update operations. Despite rich semantics, Jiffy offers highly scalable performance across varied workloads. Compared to Jiffy's lock-based rivals that support batch updates, our index can execute large batch updates up to 7.4 times more efficiently. Moreover, Jiffy often outperforms the state-of-the-art lock-free ordered indices that feature linearizable range scan operations but lack batch updates.

In this article we study the properties of distributed systems that mix eventual and strong consistency. We formalize such systems throughacute cloud types(ACTs), abstractions similar to conflict-free replicated data types (CRDTs), which by default work in a highly available, eventually consistent fashion, but which also feature strongly consistent operations for tasks which require global agreement. Unlike other mixed-consistency solutions, ACTs can rely on efficient quorum-based protocols, such as Paxos. Hence, ACTs gracefully tolerate machine and network failures also for the strongly consistent operations. We formally study ACTs and demonstrate phenomena which are neither present in purely eventually consistent nor strongly consistent systems. In particular, we identifytemporary operation reordering, which implies interim disagreement between replicas on the relative order in which the client requests were executed. When not handled carefully, this phenomenon may lead to undesired anomalies, including circular causality. We prove an impossibility result which states that temporary operation reordering is unavoidable in mixed-consistency systems with sufficiently complex semantics. Our result is startling, because it shows that apparentstrengtheningof the semantics of a system (by introducing strongly consistent operations to an eventually consistent system) results in the weakening of the guarantees on the eventually consistent operations.

In this paper we study the properties of eventually consistent distributed systems that feature arbitrarily complex semantics and mix eventual and strong consistency. These systems execute requests in a highly-available, weakly-consistent fashion, but also enable stronger guarantees through additional inter-replica synchronization mechanisms that require the ability to solve distributed consensus. We use the seminal Bayou system as a case study, and then generalize our findings to a whole class of systems. We show dubious and unintuitive behaviour exhibited by those systems and provide a theoretical framework for reasoning about their correctness. We also state an impossibility result that formally proves the inherent limitation of such systems, namely temporary operation reordering, which admits interim disagreement between replicas on the relative order in which the client requests were executed.

We propose Hybrid Transactional Replication (HTR), a novel replication scheme for highly dependable services. It combines two schemes: a transaction is executed either optimistically by only one service replica in the deferred update mode (DU), or deterministically by all replicas in the state machine mode (SM); the choice is made by an oracle. The DU mode allows for parallelism and thus takes advantage of multicore hardware. In contrast to DU, the SM mode guarantees abort-free execution, soit is suitable for irrevocable operations and transactions generating high contention. For expressiveness, transactions can be discarded or retried on demand. We prove that the higher flexibility of the scheme does not come at the cost of weaker guarantees for clients: HTR satisfies strong consistency guarantees akin to those provided by other popular transactional replication schemes such as Deferred Update Replication. We developed HTR-enabled Paxos STM, an object-based distributed transactional memory system, and evaluated it thoroughly under various workloads. We show the benefits of using a novel oracle that relies on machine learning techniques for automatic adaptation to changing conditions. The ML-based oracle, based on algorithms for the multi-armed bandit problem, provides up to 50 percent improvement in throughput when compared to the system running with DU-only or SM-only oracles.

In the paper, we analyze and experimentally compare two popular replication schemes relying on atomic broadcast: state machine replication (SMR) and deferred update replication (DUR). We estimate the lower bounds on the time of executing requests by the SMR and DUR systems running on multi-core servers. We also consider variants of systems that can process read-only requests with a lower overhead. In the analysis of DUR, we consider conflict patterns. We then formally show the scalability of SMR and DUR, which reflects the capacity of systems to effectively utilize an increasing number of processor cores. Next, we compare SMR and DUR experimentally under different levels of contention, using several benchmarks. We show throughput, abort rate (in DUR), and network congestion. The key results of our work are that neither system is superior in all cases, and that the theoretical and experimental results are heavily influenced by the dominance of either the CPU execution time or atomic broadcast time. We therefore propose to combine both replication schemes and gain the best of both worlds.

Eventually consistent linearizability (ec-linearizability) is a new correctness condition for eventually consistent distributed systems (modeled as shared objects). Unlike the existing definitions of eventual consistency, ec-linearizability is suitable for describing the behaviour of some popular eventually consistent systems, such as Cassandra. It is because ec-linearizability allows for certain types of phenomena, such as lost updates. Similarly to linearizability, ec-linearizability is a safety property and is both local and nonblocking. Thus, ec-linearizability is a property that is both easy to use and reason about.

In this paper we propose executive deferred update replication (EDUR), a novel algorithm for multi-primary replication of transactional memory and databases. EDUR streamlines transaction certification (i.e., checking for conflicts between concurrent transactions) with the broadcast protocol, which improves overall performance and scalability compared to deferred update replication based on total order broadcast (TOB). EDUR uses executive order broadcast (EOB), a novel protocol that can be seen as a generalization of TOB. Compared to TOB, EOB features new primitives and properties that enable the application to delegate some work to a leader -- a process inherently present in many TOB algorithms that is responsible for coordination of message dissemination. The results of experimental evaluation show significant performance gains when using our approach.

We propose a novel algorithm for hybrid transactional replication (HTR) of highly dependable services. It combines two schemes: a transaction is executed either optimistically by only one service replica in the deferred update mode (DU), or deterministically by all replicas in the state machine mode (SM); the choice is made by an oracle. The DU mode allows for parallelism and thus takes advantage of multicore hardware. In contrast to DU, the SM mode guarantees abort-free execution, so it is suitable for irrevocable operations and transactions generating high contention. For expressiveness, transactions can be discarded or retried on demand. We developed HTR-enabled Paxos STM, an object-based distributed transactional memory system, and evaluated it using several benchmarks: Bank, Distributed STMBench7, and Twitter Clone. We tested our system under various workloads and three oracle types: DU and SM, which execute all transactions in one mode, and Hybrid -- tailored specifically for each benchmark -- which selects a mode for each transaction dynamically based on various parameters. In all our tests, the Hybrid oracle is not worse than DU and SM and outperforms them when the number of replicas grows.

In this paper, we analyze and experimentally compare state-machine-based and deferred-update (or transactional) replication, both relying on atomic broadcast. We define a model that describes the upper and lower bounds on the execution of concurrent requests by a service replicated using either scheme. The model is parametrized by the degree of parallelism in either scheme, the number of processor cores, and the type of requests. We analytically compared both schemes and a non-replicated service, considering a bcast- and request-execution-dominant workloads. To evaluate transactional replication experimentally, we developed Paxos STM---a novel fault-tolerant distributed software transactional memory with programming constructs for transaction creation, abort, and retry. For state-machine-based replication, we used JPaxos. Both systems share the same implementat ion of atomic broadcast based on the Paxos algorithm. We present the results of performance evaluation of both replication schemes, and a non-replicated (thus prone to failures) service, considering various workloads. The key result of our theoretical and experimental work is that neither system is superior in all cases. We discuss these results in the paper.