Search

Distributed databases are supposed to manipulate data safely, ensuring properties like serializability even when nodes or networks fail. Unfortunately, they often don't. We found consistency violations in 26 systems over the last eight years, ranging from stale reads to catastrophic data loss. We review the Jepsen testing library [1], which combines automated deployment, fault injection, and property-based testing techniques to uncover safety violations and performance characteristics in a broad range of distributed systems. We then present Elle [2], a new library for analyzing Jepsen histories and finding consistency violations in linear time. We build on Adya's formalism [3] of transactional anomalies as cycles in a dependency graph. Unfortunately these graphs are invisible to clients. However, by carefully choosing the datatypes and operations we submit to a database, we can generate histories whose client-observable structure constrains the dependency graph of every Adya history the database could have executed. Elle can identify every anomaly in the Adya formalism (except for predicates) in linear time, allowing us to validate a broad range of isolation properties up to strict serializability. It automatically finds minimal counterexamples, helping an engineer see exactly which transactions were incompatible with (e.g.) snapshot isolation. It is sound, but since some information may be missing from observed histories, not complete. We use Jepsen and Elle to find consistency errors in a broad variety of datastores, including PostgreSQL, Dgraph, and Redis-Raft.

Serializability is a well-understood concurrency control mechanism that eases reasoning about highly-concurrent database programs. Unfortunately, enforcing serializability has a high-performance cost, especially on geographically distributed database clusters. Consequently, many databases allow programmers to choose when a transaction must be executed under serializability, with the expectation that transactions would only be so marked when necessary to avoid serious concurrency bugs. However, this is a significant burden to impose on developers, requiring them to (a) reason about subtle concurrent interactions among potentially interfering transactions, (b) determine when such interactions would violate desired invariants, and (c) then identify the minimum number of transactions whose executions should be serialized to prevent these violations. To mitigate this burden, in this paper we present a sound and fully automated schema refactoring procedure that transforms a program's data layout -- rather than its concurrency control logic -- to eliminate statically identified concurrency bugs, allowing more transactions to be safely executed under weaker and more performant database guarantees. Experimental results over a range of database benchmarks indicate that our approach is highly effective in eliminating concurrency bugs, with safe refactored programs showing an average of 120% higher throughput and 45% lower latency compared to the baselines., 20 pages, to appear in 42nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2021)

Concurrent correctness conditions formalize the notion of “seeming atomicity” in concurrent access to shared object state. For different sorts of objects (databases, concurrent data structures, software transactional memory) different sorts of correctness conditions have been proposed (serializability, linearizability, opacity). Decidability of concurrent correctness conditions studies two problems: the membership problem asks whether a single execution is correct; the correctness problem asks whether all executions of a given implementation are correct.

A distributed file system is used to store and share files in a peer-to-peer network using the InterPlanetary File System (IPFS) protocol. In a distributed file system, multiple central servers can save the files which will be accessed by various remote clients with proper authorization rights within the network. Nowadays, the amount of data getting generated each minute is huge and can be accessed by multiple users. This creates a problem in managing, accessing and executing data and finally leading to concurrency control issues. Concurrency control is a process of simultaneously managing the execution of data in a shared database and ensures the serializability of data for multiple users. Thus, in the context of Hadoop, if multiple clients want to write an updated data in the HDFS file system then the protocol that needs to be followed to make sure that the write done by one client does not influence the computation performed by the other client. This paper elaborates how multiple users can access the same file without getting any distortion in the content of that file. It also provides a theoretical solution to handle the concurrency control problem in Hadoop. The solution discussed in this paper is to implement Hadoop’s Java-based Filesystem interface for the decentralised, peer-to-peer file system using IPFS. The proposed interface will allow the Hadoop MapReduce functions to be directly performed on data files hosted on IPFS.

The optimistic concurrency control (OCC) utilized by in-memory databases performs writes on thread-local copies and makes the writes visible upon passing validation. However, high contention workloads suffer from failure of the validation step due to non-semantic memory access conflicts, leading to frequent transaction aborts. In this work, we improve the commit rate of in-memory databases by replacing OCC and the underlying indexing of key-value entries in the Silo database with a lock-free transactional dictionary. To further optimize the transactional commit rate, we present transactional merging, a technique that relaxes the semantic conflict resolution of transactional data structures by merging conflicting operations to reduce aborts. Transactional merging guarantees strict serializability through a strategy that recovers the correct abstract state given that a transaction attempting to merge operations aborts. The experimental evaluation demonstrates that the lock-free transactional dictionary with transactional merging achieves an average speedup of 175% over OCC and the Masstree indexing used in the Silo database for write-dominated workloads on a non-uniform memory access system.

The growth of classical computers can be credited in no small part to the development of operating systems designed to provide program portability between different hardware configurations. Quantum computing should learn from classical computing history in order to expedite their development. The approach presented in this paper results in basic parallel execution of quantum programs. The approach utilises the information required for sequential execution including program dependancies, program mappings and qubit connectivities reshaping it to present novel data in the form of a serializability conflict graph. Utilising this graph the quantum system can easily determine parallelisable programs as well as how to parallelise them. This premiere system has been implemented and an attempted comparison has been made to other simulators. Because this system requires no new information, the comparison demonstrates that the cost of employing this strategy is largely similar to employing current sequential techniques, with the added novel benefit of parallel execution. Refereed/Peer-reviewed

Wide-area Edge Database (WedgeDB) span globally and store data closer to the users. We term this the Global Edge Data management problem. In such an environment, aspects such as data storage, retrieval, transaction processing, and protection from malicious actors need to be addressed by any data management system that aims to consider itself a viable solution. Although blockchain technology (both permissioned and permissionless) has provided a way to address these concerns, transaction processing in these environments is still challenging. WedgeDB is an attempt to address these security problems in edge-cloud data systems [2]. The main goals of WedgeDB are to support distributed transaction processing coupled with secure transaction execution. Data stored in WedgeDB is partitioned into clusters with each cluster handling a unique set of keys. WedgeDB is a collection of such clusters. This is shown in figure 1. In figure 1, each cluster Cx stores a unique set of keys. This partitioning scheme allows us to build a distributed transaction model which runs transactions on a subset of clusters in the network. Transactions in WedgeDB are serializable. In WedgeDB, clients perform read operations as part of a transaction via read requests which can be sent to any of the WedgeDB nodes. The read operations are added to the transaction's history. Write operations are cached by the client until a commit is called which sends the transaction object containing the read history and write operations to a WedgeDB node to be committed. Transactions are processed in batches called Epochs. Each cluster maintains a leader which receives transactions and groups them into epochs. A cluster in WedgeDB contains 3f + 1 nodes (where f is the number of tolerable faulty nodes) and PBFT[1] is used to attain consensus among the nodes when executing transactions. Keys modified during an epoch are added to a Merkle tree which is used to verify changes to keys handled by the cluster. During transaction execution, proof of transaction execution is generated in the form of signed data blocks by the nodes in the cluster. At least f + 1 signed messages must be gathered before an epoch can be committed. These data blocks along with the root of the Merkle tree are stored in an SMR log where each entry in the SMR log corresponds to an epoch. Transactions that contain keys from different clusters are executed via two-phase commit. During the prepare phase a remote cluster executes PBFT within its local cluster and checks for dependency violations before moving ahead with the commit phase. Committed epoch may not have committed transactions and therefore an additional parameter is used to indicate the last committed epoch. This parameter combined with the dependency vector help in finding out serializability violations and abort transactions. With WedgeDB, transactions that affect only a few clusters do not require global consensus to commit. Transactions that read keys from a number of clusters do not require consensus at the server nodes and allow data to be read from a consistent snapshot of the WedgeDB network. We thus, present WedgeDB as a viable solution to the problem of global edge data management.

In-memory transactional data girds, often referred to as NoSQL data grids demand high concurrency for scalability and high performance in data-intensive applications. As an alternative concurrency control model, distributed transactional memory (DTM) promises to alleviate the difficulties of lock-based distributed synchronization. However, if a transaction aborts, DTM suffers from additional communication delays to remotely request and retrieve all its objects again, resulting in degraded performance. To avoid unnecessary aborts, the multi-versioning (MV) model of using multiple object versions in DTM can be considered. MV transactional memory inherently guarantees commits of read-only transactions, but limits concurrency of write transactions. We present a new transactional scheduler, called partial rollback-based transactional scheduler (or PTS), for a multi-versioned DTM model. The model supports multiple object versions to exploit concurrency of read-only transactions, and detects conflicts of write transactions at an object level. Instead of aborting a transaction, PTS assigns backoff times for conflicting transactions, and the transaction is rolled-back partially. We implemented PTS on Infinispan, and conducted comprehensive experimental studies on no and partial replication models. Our implementation reveals that PTS improves transactional throughput over MV-Transactional Forwarding Algorithm without PTS and a scalable one-copy serializable partial replication protocol (SCORe) by as much as 2.4× and 1.3×, respectively.

Debugging transactions and understanding their execution are of immense importance for developing OLAP applications, to trace causes of errors in production systems, and to audit the operations of a database. However, debugging transactions is hard for several reasons: 1) after the execution of a transaction, its input is no longer available for debugging, 2) internal states of a transaction are typically not accessible, and 3) the execution of a transaction may be affected by concurrently running transactions. We present a debugger for transactions that enables non-invasive, post-mortem debugging of transactions with provenance tracking and supports what-if scenarios (changes to transaction code or data). Using reenactment, a declarative replay technique we have developed, a transaction is replayed over the state of the DB seen by its original execution including all its interactions with concurrently executed transactions from the history. Importantly, our approach uses the temporal database and audit logging capabilities available in many DBMS and does not require any modifications to the underlying database system nor transactional workload., Comment: to appear as "Debugging Transactions and Tracking their Provenance with Reenactment" in PVDLB 2017, vol 10., nr. 12

Multi-version concurrency control (MVCC) is currently the most popular transaction management scheme in modern database management systems (DBMSs). Although MVCC was discovered in the late 1970s, it is used in almost every major relational DBMS released in the last decade. Maintaining multiple versions of data potentially increases parallelism without sacrificing serializability when processing transactions. But scaling MVCC in a multi-core and in-memory setting is non-trivial: when there are a large number of threads running in parallel, the synchronization overhead can outweigh the benefits of multi-versioning. To understand how MVCC perform when processing transactions in modern hardware settings, we conduct an extensive study of the scheme's four key design decisions: concurrency control protocol, version storage, garbage collection, and index management. We implemented state-of-the-art variants of all of these in an in-memory DBMS and evaluated them using OLTP workloads. Our analysis identifies the fundamental bottlenecks of each design choice.

DrTM is a fast in-memory transaction processing system that exploits advanced hardware features such as remote direct memory access (RDMA) and hardware transactional memory (HTM). To achieve high efficiency, it mostly offloads concurrency control such as tracking read/write accesses and conflict detection into HTM in a local machine and leverages the strong consistency between RDMA and HTM to ensure serializability among concurrent transactions across machines. To mitigate the high probability of HTM aborts for large transactions, we design and implement an optimized transaction chopping algorithm to decompose a set of large transactions into smaller pieces such that HTM is only required to protect each piece. We further build an efficient hash table for DrTM by leveraging HTM and RDMA to simplify the design and notably improve the performance. We describe how DrTM supports common database features like read-only transactions and logging for durability. Evaluation using typical OLTP workloads including TPC-C and SmallBank shows that DrTM has better single-node efficiency and scales well on a six-node cluster; it achieves greater than 1.51, 34 and 5.24, 138 million transactions per second for TPC-C and SmallBank on a single node and the cluster, respectively. Such numbers outperform a state-of-the-art single-node system (i.e., Silo) and a distributed transaction system (i.e., Calvin) by at least 1.9X and 29.6X for TPC-C.

Existing storage stacks are top heavy and expect little from block storage. As a result, new high-level storage abstractions—and new designs for existing abstractions—are difficult to realize, requiring developers to implement from scratch complex functionality such as failure atomicity and fine-grained concurrency control. In this article, we argue that pushing transactional isolation into the block store (in addition to atomicity and durability) is both viable and broadly useful, resulting in simpler high-level storage systems that provide strong semantics without sacrificing performance. We present Isotope, a new block store that supports ACID transactions over block reads and writes. Internally, Isotope uses a new multiversion concurrency control protocol that exploits fine-grained, subblock parallelism in workloads and offers both strict serializability and snapshot isolation guarantees. We implemented several high-level storage systems over Isotope, including two key-value stores that implement the LevelDB API over a hash table and B-tree, respectively, and a POSIX file system. We show that Isotope’s block-level transactions enable systems that are simple (100s of lines of code), robust (i.e., providing ACID guarantees), and fast (e.g., 415MB/s for random file writes). We also show that these systems can be composed using Isotope, providing applications with transactions across different high-level constructs such as files, directories, and key-value pairs.

In order to guarantee recoverable transaction execution, database systems permit a transaction's writes to be observable only at the end of its execution. As a consequence, there is generally a delay between the time a transaction performs a write and the time later transactions are permitted to read it. This delayed write visibility can significantly impact the performance of serializable database systems by reducing concurrency among conflicting transactions. This paper makes the observation that delayed write visibility stems from the fact that database systems can arbitrarily abort transactions at any point during their execution. Accordingly, we make the case for database systems which only abort transactions under a restricted set of conditions, thereby enabling a new recoverability mechanism, early write visibility , which safely makes transactions' writes visible prior to the end of their execution. We design a new serializable concurrency control protocol, piece-wise visibility (PWV), with the explicit goal of enabling early write visibility. We evaluate PWV against state-of-the-art serializable protocols and a highly optimized implementation of read committed, and find that PWV can outperform serializable protocols by an order of magnitude and read committed by 3X on high contention workloads.

The Push/Pull semantic model of transactions has appeared recently as a solution that unifies a wide range of transactional memory algorithms. It has been proved that the push/pull semantic model satisfies serializability, thus one may prove that a given STM satisfies serializability by constructing its push/pull model such that this model satisfies respective correctness criteria. In this paper, we prove that a Python STM implementation is serializable by constructing its Push/Pull model and by showing that the model satisfies the correctness criteria for the relevant push/pull semantic rules. We first identify that modeling Python STM requires only four, out of seven, push/pull operations, namely the operations pull, apply, push, and commit. Next, we introduce the detailed specification of the PSTM transactional algorithm. Then we map the steps of the PSTM transactional algorithm to the respective push/pull semantic rules. Finally, we prove that the PSTM algorithm satisfies the correctness criteria of the respective push/pull semantic rules. We have envisaged this paper to provide interested researchers with a better understanding of PSTM semantics, in order to construct push/pull models of their own STMs more easily.

Relational database applications are notoriously difficult to test and debug. Concurrent execution of database transactions may violate complex structural invariants that constraint how changes to the contents of one (shared) table affect the contents of another. Simplifying the underlying concurrency model is one way to ameliorate the difficulty of understanding how concurrent accesses and updates can affect database state with respect to these sophisticated properties. Enforcing serializable execution of all transactions achieves this simplification, but it comes at a significant price in performance, especially at scale, where database state is often replicated to improve latency and availability. To address these challenges, this paper presents a novel testing framework for detecting serializability violations in (SQL) database-backed Java applications executing on weakly-consistent storage systems. We manifest our approach in a tool named CLOTHO, that combines a static analyzer and a model checker to generate abstract executions, discover serializability violations in these executions, and translate them back into concrete test inputs suitable for deployment in a test environment. To the best of our knowledge, CLOTHO is the first automated test generation facility for identifying serializability anomalies of Java applications intended to operate in geo-replicated distributed environments. An experimental evaluation on a set of industry-standard benchmarks demonstrates the utility of our approach., Comment: Conditionally accepted to OOPSLA'19

In a classic transactional distributed database management system (DBMS), write transactions invariably synchronize with a coordinator before final commitment. While enforcing serializability, this model has long been criticized for not satisfying the applications' availability requirements. When entering the era of Internet of Things (IoT), this problem has become more severe, as an increasing number of applications call for the capability of hybrid transactional and analytical processing (HTAP), where aggregation constraints need to be enforced as part of transactions. Current systems work around this by creating escrows, allowing occasional overshoots of constraints, which are handled via compensating application logic.The WiSer DBMS targets consistency with availability, by splitting the database commit into two steps. First, a PROMISE step that corresponds to what humans are used to as commitment, and runs without talking to a coordinator. Second, a SERIALIZE step, that fixes transactions' positions in the serializable order, via a consensus procedure. We achieve this split via a novel data representation that embeds read-sets into transaction deltas, and serialization sequence numbers into table rows. WiSer does no sharding (all nodes can run transactions that modify the entire database), and yet enforces aggregation constraints. Both readwrite conflicts and aggregation constraint violations are resolved lazily in the serialized data. WiSer also covers node joins and departures as database tables, thus simplifying correctness and failure handling. We present the design of WiSer as well as experiments suggesting this approach has promise.

Many systems use ad hoc collections of files and directories to store persistent data. For consumers of this data, the process of properly parsing, using, and updating these filestores using conventional APIs is cumbersome and error-prone. Making matters worse, most filestores are too big to fit in memory, so applications must process the data incrementally while managing concurrent accesses by multiple users. This paper presents Transactional Forest (TxForest), which builds on earlier work on Forest to provide a simpler, more powerful API for managing filestores, including a mechanism for managing concurrent accesses using serializable transactions. Under the hood, TxForest implements an optimistic concurrency control scheme using Huet’s zippers to track the data associated with filestores. We formalize TxForest in a core calculus, develop a proof of serializability, and describe our OCaml prototype, which we have used to build several practical applications.

Modern database-management systems permit the isolation level to be set on a per-transaction basis. In such a mixed-level setting, it is important to understand how transactions running at different levels interact. More fundamentally however, these levels are sometimes of different scopes. For example, READ COMMITTED and REPEATABLE READ are of local scope, since the defining properties depend upon only the transaction and its relationship to those running concurrently. On the other hand, SERIALIZABLE is of global scope; serializability is a property of a schedule of transactions, not of a single transaction. In this work, in addition to formalizing the interaction of transactions at different levels, the meaning of serializability within local scope is also addressed.

Software Transactional Memory (STM) has recently emerged as a promising synchronization abstraction for multicore architectures. State-of-the-art STM algorithms, however, suffer from performance challenges due to contention and spinning on locks during the transaction commit phase. In this paper, we introduce Remote Transaction Commit (or RTC), a mechanism for executing commit phases of STM transactions. RTC dedicates server cores to execute transactional commit phases on behalf of application threads. This approach has two major benefits. First, it decreases the overheads of spinning on locks during commit, such as the number of cache misses, blocking of lock holders, and CAS operations. Second, it enables exploiting the benefits of coarse-grained locking algorithms (simple and fast lock acquisition, reduced false conflicts) and bloom filter-based algorithms (concurrent execution of independent transactions). Our experimental study on a 64-core machine with four sockets shows that RTC solves the problem of performance degradation due to spin locking on both micro-benchmarks (red-black trees), and macro-benchmarks (STAMP), especially when the commit phase is relatively long and when thread contention increases.

Graph databases have become a common infrastructure component. Yet existing systems either operate on offline snapshots, provide weak consistency guarantees, or use expensive concurrency control techniques that limit performance. In this paper, we introduce a new distributed graph database, called Weaver, which enables efficient, transactional graph analyses as well as strictly serializable ACID transactions on dynamic graphs. The key insight that allows Weaver to combine strict serializability with horizontal scalability and high performance is a novel request ordering mechanism called refinable timestamps. This technique couples coarse-grained vector timestamps with a fine-grained timeline oracle to pay the overhead of strong consistency only when needed. Experiments show that Weaver enables a Bitcoin blockchain explorer that is 8x faster than Blockchain.info, and achieves 10.9x higher throughput than the Titan graph database on social network workloads and 4x lower latency than GraphLab on offline graph traversal workloads.

Distributed Transactional Memory (DTM) is a recent but promising model for programming distributed systems. It aims to present programmers with a simple to use distributed concurrency control abstraction (transactions), while maintaining performance and scalability similar to distributed fine-grained locks. Any complications usually associated with such locks (e.g., distributed deadlocks) are avoided. In this article, we analyze the use of open nesting in the DTM setting. We extend two DTM algorithms, Transactional Forwarding Algorithm (TFA) and SCORe with support for open nested transactions and we implement them into two frameworks for running distributed transactions, such as Hyflow and Infinispan. We discuss the mechanisms and performance implications of such nesting, and identify the cases where using open nesting is warranted and the relevant parameters for such a decision. To the best of our knowledge, our work also contributes the first ever implementations of DTM systems with support for open-nested transactions.

Snapshot Isolation (SI) is in wide use by database systems but does not guarantee serializability. Serializable snapshot isolation (SSI) was defined in 2008 by Cahill, Rohm, and Fekete in Ref. [1] and an enhanced version that we call ESSI was defined in 2009 by the same authors [2] . Both guarantee serializable execution by aborting transactions that might be involved in anomalies, but occasional transactions are aborted unnecessarily. The resulting commit order is often different from the serialization order and this can confuse bank auditors, for example. In this paper we show how to determine the proper serialization order of these transactions and store this information for later access. With this known serialization order the database system can perform time-travel queries to capture snapshots of consistent database states in the past. Our algorithm assigns to each SSI or ESSI transaction at its commit time an appropriate serialization order timestamp that falls within the transaction lifetime, i.e., between its start-time and commit-time. The algorithm uses only information already gathered by the algorithm implementing ESSI in [2] .

As new applications of cloud data management system (CDMS) such as online games, cooperation edit, social network, and so on, are increasing, transaction processing capabilities for CDMS are required. Several transaction processing methods for cloud data management system (CDMS) have been proposed. However, existing transaction processing methods have some problems. Some of them provide limited transaction processing capabilities. Some of them are hard to be integrated with existing CDMSs. In this paper, we proposed a new concurrency control method to support transaction processing capability for CDMS to solve these problems. The proposed method was designed and implemented based on Spark, an in-memory distributed processing framework. It uses RDD (Resilient Distributed Dataset) model to provide fault tolerant to data in the main memory. In our proposed method, database stored in CDMS is loaded to main memory managed by Spark. The loaded data set is then transformed to RDD. In addition, we proposed a multi-version concurrency control method through immutable characteristics of RDD. Finally, we performed experiments to show the feasibility of the proposed method.

So far, transactional memory—although a promising technique—suffered from the absence of an efficient hardware implementation. Intel’s Haswell microarchitecture introduced hardware transactional memory (HTM) in mainstream CPUs. HTM allows for efficient concurrent, atomic operations, which is also highly desirable in the context of databases. On the other hand, HTM has several limitations that, in general, prevent a one-to-one mapping of database transactions to HTM transactions. In this work, we devise several building blocks that can be used to exploit HTM in main-memory databases. We show that HTM allows for achieving nearly lock-free processing of database transactions by carefully controlling the data layout and the access patterns. The HTM component is used for detecting the (infrequent) conflicts, which allows for an optimistic, and thus very low-overhead execution of concurrent transactions. We evaluate our approach on a four-core desktop and a 28-core server system and find that HTM indeed provides a scalable, powerful, and easy to use synchronization primitive.

At present, to deal with a large amount of variety data in the database, various NoSQL databases have been proposed and put to practical use. However, since most of them support the transaction processing only on the single data, there is the problem that the plural data cannot be updated in a lump with maintaining the ACID properties. To solve this problem, in this paper, we propose a method to process plural data as a single transaction for MongoDB, which is a kind of document oriented NoSQL database. Concretely, each data has both of the before and after update fields, and the state of the transaction is managed. Then, in the case of before the commit, the former data is queried; after the commit, the latter data is queried. By this method, we show that the plural data can be updated as a transaction with the specified isolation level.

The Optimistic Concurrency Control (OCC) method has been commonly used for in-memory databases to ensure transaction serializability --- a transaction will be aborted if its read set has been changed during execution. This simple criterion to abort transactions causes a large proportion of false positives, leading to excessive transaction aborts. Transactions aborted false-positively (i.e. false aborts) waste system resources and can significantly degrade system throughput (as much as 3.68x based on our experiments) when data contention is intensive. Modern in-memory databases run on systems with increasingly parallel hardware and handle workloads with growing concurrency. They must efficiently deal with data contention in the presence of greater concurrency by minimizing false aborts. This paper presents a new concurrency control method named Balanced Concurrency Control (BCC) which aborts transactions more carefully than OCC does. BCC detects data dependency patterns which can more reliably indicate unserializable transactions than the criterion used in OCC. The paper studies the design options and implementation techniques that can effectively detect data contention by identifying dependency patterns with low overhead. To test the performance of BCC, we have implemented it in Silo and compared its performance against that of the vanilla Silo system with OCC and two-phase locking (2PL). Our extensive experiments with TPC-W-like, TPC-C-like and YCSB workloads demonstrate that when data contention is intensive, BCC can increase transaction throughput by more than 3x versus OCC and more than 2x versus 2PL; meanwhile, BCC has comparable performance with OCC for workloads with low data contention.

Locking is one of the predominant costs in transaction processing. While much work has focused on designing efficient concurrency control mechanisms, not much has been done on understanding how transaction applications issue queries and leveraging application semantics to improve application performance. This paper presents Q uro , a query-aware compiler that automatically reorders queries in transaction code to improve performance. Observing that certain queries within a transaction are more contentious than others as they require locking the same tuples as other concurrently executing transactions, Q uro automatically changes the application such that contentious queries are issued as late as possible. We have evaluated Q uro on various transaction benchmarks, and our results show that Q uro -generated implementations can increase transaction throughput by up to 6.53x, while reduce transaction latency by up to 85%.

We propose a new method for runtime checking of a relaxed consistency property called quasi linearizability for concurrent data structures.Quasi linearizability generalizes the standard notion of linearizability by introducing nondeterminism into the parallel computations quantitatively and then exploiting such nondeterminism to improve the runtime performance. However, ensuring the quantitative aspects of this correctness condition in the low-level code of the concurrent data structure implementation is a difficult task.Our runtime verification method is the first fully automated method for checking quasi linearizability in the C/C++ code of concurrent data structures. It guarantees that all the reported quasi linearizability violations manifested by the concurrent executions are real violations. We have implemented our method in a software tool based on the LLVM compiler and a systematic concurrency testing tool called Inspect. Our experimental evaluation shows that the new method is effective in detecting quasi linearizability violations in the source code implementations of concurrent data structures.

The paper study on the TEMPEST standards with not only analyzing a large number of data from decrypted and semi-decrypted documents, but also tie up with the EMC standards because of they are indivisible. It proposed three attributers on TEMPEST standard, including serializability, architecture and life cycle. The serializable standard means no conflicts, including but not limited to, of the standards specifications, issue times, data limits, publishers, practitioners and so on. The architecture of standard exists so that should be named in nomenclature and demonstrated with systematic way. The standard should be established and published on opportune moment, living cycle from established to cancelled. The attributers are demonstrated through TEMPEST standard examples. The development of TEMPEST standards should be consistent with TEMPEST theories and products.

Transaction management schemes and data models proposed for conventional database applications such as data processing are inadequate for advanced applica­ tions encountered in CAD/CAM, VLSI and office automation. The main issues that need to resolved are a new transaction model and control mechanism and a data model. Design transactions cooperate and communicate with other design transac­ tions. This behavior cannot be captured by a transaction model where correctness is based on serializability theory. Due to the multiple versions that coexist in a design database, other correctness criteria version control, internal and mutual consistency are also required. In addition, issues such as recovery are reviewed in the context of design databases.

Scheduling transactions in a real-time database requires an integrated approach in which the schedule does not only guarantee execution before the deadline, but also maintains data consistency. The problem has been studied under a common framework which considers both concurrency control issues and the real-time constraints in centralized and distributed transaction processing. A real-time transaction processing model has been defined for a centralized system. The proposed protocols use a unified approach to maximize concurrency while meeting real-time constraints at the same time. In order to test the behavior of the model and the proposed protocols, a real-time transaction processing testbed has been developed using discrete event simulation techniques. The results indicate that different protocols work better under different load scenarios and that the overall performance can be significantly enhanced by modifying the underlying system configuration. Among other system and transaction parameters, the effect of data partitioning, buffer management, preemption, disk contention, locking mode and multiprocessing has been studied. For the distributed environment, new concepts of real-time nested transactions and priority propagation have been proposed. Real-time nested transactions incorporate the deadline requirements in the hierarchical structure of nested transactions. Priority propagation addresses the issues related to transaction aborts in real-time nested transaction processing. The notion of priority ceiling has been used to avoid the priority inversion problem. The proposed protocols exhibit freedom from deadlock and have tightly bounded waiting period. Both of these properties make them very suitable for distributed real-time transaction processing environment.

Flash memory has accelerated the architectural evolution of storage systems with its unique characteristics compared to magnetic disks. The no-overwrite property of flash memory naturally supports transactions, a commonly used mechanism in systems to provide consistency. However, existing embedded transaction designs in flash-based Solid State Drives (SSDs) either limit the transaction concurrency or introduce high overhead in tracking transaction states. This leads to low or unstable SSD performance. In this paper, we propose a transactional SSD (TxSSD) architecture, LightTx, to enable better concurrency and low overhead. First, LightTx improves transaction concurrency arbitrarily by using a page-independent commit protocol. Second, LightTx tracks the recent updates by leveraging the near-log-structured update property of SSDs and periodically retires dead transactions to reduce the transaction state tracking cost. Experiments show that LightTx achieves nearly the lowest overhead in garbage collection, memory consumption and mapping persistence compared to existing embedded transaction designs. LightTx also provides up to 20.6 percent performance improvement due to improved transaction concurrency.

Software transactional memory (STM) is one of the techniques used towards achieving non-blocking process synchronization in multi-threaded computing environment. In spite of its high potential, one of the major limitations of transactional memory (TM) is that in order to ensure data consistency as well as progress condition, TM often forces transactions to abort. This paper proposes a new concurrency control mechanism. It starts with the existing TM implementations for obstruction freedom and eventually builds a new STM methodology. The primary objective is to reduce aborting of transactions in some typical scenarios. A programming model is described for a chain of update transactions that share the same data object among themselves. Using the proposed approach, any new update transaction appended in this chain need not wait for the earlier transactions to finish. The proposed STM allows wait-free, non-blocking implementation of a mix of read and multiple update transactions on the same shared data object with higher throughput.

XML concurrency control protocol (CCP) is used to guard the consistence and isolation of transactions in Native XML databases. Experiments show that locking overhead of existing approaches based on locking may be huge, especially in the applications with few or without conflicts. Optimistic concurrency control (OCC) is an alternative to locking. This paper presents a new optimistic approach for concurrency control over XML documents named FOCCX (Forward oriented Optimistic Concurrency Control over XML) facing XPath-based API. FOCCX increases the degree of transaction concurrency. This is achieved by aborting the current transaction when a potential UPDATE-UPDATE conflict taking place as early as possible, and reduces comparison times by checking a small write set against read set of a limited number of concurrent transactions. Experimental results show that our protocol has superior performance to approaches based on Backward Oriented mechanism (BOCC).

We address the problem of building scalable transaction management mechanisms for multi-row transactions on key-value storage systems, which are commonly termed as NoSQL systems. We develop scalable techniques for transaction management utilizing the snapshot isolation (SI) model. Because the SI model can lead to non-serializable transaction executions, we investigate two conflict detection techniques for ensuring serializability. To support scalability, we investigate system architectures and mechanisms in which the transaction management functions are decoupled from the storage system and integrated with the application-level processes. We present two system architectures and demonstrate their scalability under the scale-out model of cloud computing platforms. In the first system architecture all transaction management functions are executed in a fully decentralized manner by the application processes. The second architecture is based on a hybrid approach in which the conflict detection functions are performed by a dedicated service. We perform a comparative evaluation of these architectures using the TPC-C benchmark and demonstrate their scalability.

Optimistic scheduling policy based on the concept of Very Important Transaction.Progressively pessimistic scheduling policy with low runtime overheads.Adaptive scheduler that combines two scheduling policies in a synergistic way.Thorough evaluation of 4 schedulers with the STAMP and the STMBench7 benchmark. Transaction schedulers reduce the number of transaction reexecutions in applications using Software Transactional Memory (STM) by preventing conflicting transactions to run in parallel. Unfortunately, current scheduling solutions are too conservative, rely on coarse measures to serialize transactions, and are specially inadequate for workloads with long transactions.In this paper we introduce an optimistic and adaptive transaction scheduler that takes advantage of the information already collected by the STM runtime to increase parallelism between transactions and, thus, improve transactions' throughput. Our new ProVIT scheduler implements a low-overhead scheduling policy for short transactions that reduces concurrency as contention increases and a fine-grained scheduling policy for long transactions based on the novel concept of Very Important Transaction.Experimental results conducted with the STMBench7 benchmark and the STAMP benchmark suite showed that the ProVIT scheduler has comparable performance to other current scheduling solutions for short transactions, but is up to 65% faster for long-running transactions.

As transaction processing services begin to be used in new application domains, low transaction latency becomes an important consideration. Motivated by such use cases we developed Fragola, a highly scalable low-latency and high-throughput transaction processing engine for Apache HBase. Similarly to other modern transaction managers, Fragola provides a variant of generalized snapshot isolation (SI), which scales better than traditional serializability implementations.

Online transaction processing systems use two-phase locking (2PL) to guarantee serializability. However, traditional 2PL does not perform well under high contention, because a transaction will be blocked when it fails to acquire lock. This paper proposes a scalable work stealing algorithm for 2PL to leverage intra-transaction parallelism. The key idea is to parallelize the lock holder's work among lock waiters. Compared to traditional 2PL, our approach can achieve up to 2.8X throughput improvement for TPC-C new-order transactions under high contention.

This paper introduces the first state-based formalization of isolation guarantees. Our approach is premised on a simple observation: applications view storage systems as black-boxes that transition through a series of states, a subset of which are observed by applications. Defining isolation guarantees in terms of these states frees definitions from implementation-specific assumptions. It makes immediately clear what anomalies, if any, applications can expect to observe, thus bridging the gap that exists today between how isolation guarantees are defined and how they are perceived. The clarity that results from definitions based on client-observable states brings forth several benefits. First, it allows us to easily compare the guarantees of distinct, but semantically close, isolation guarantees. We find that several well-known guarantees, previously thought to be distinct, are in fact equivalent, and that many previously incomparable flavors of snapshot isolation can be organized in a clean hierarchy. Second, freeing definitions from implementation-specific artefacts can suggest more efficient implementations of the same isolation guarantee. We show how a client-centric implementation of parallel snapshot isolation can be more resilient to slowdown cascades, a common phenomenon in large-scale datacenters.

In the last years, remarkable improvements have been made in the ability of distributed database systems performance. A distributed database is composed of some sites which are connected to each other through network connections. In this system, if good harmonization isn't made between different transactions, it may result in database incoherence. Nowadays, because of the complexity of many sites and their connection methods, it is difficult to extend different models in distributed database serially. The principle goal of concurrency control in distributed database is to ensure not interfering in accessibility of common database by different sites. Different concurrency control algorithms have been suggested to use in distributed database systems. In this paper, some available methods have been introduced and compared for concurrency control in distributed database.

Shared-memory languages and systems generally provide weak or undefined semantics for executions with data races. Prior work has proposed memory consistency models that ensure well-defined, easy-to-understand semantics based on region serializability (RS), but the resulting system may throw a consistency exception in the presence of a data race. Consistency exceptions can occur unexpectedly even in well-tested programs, hurting availability and thus limiting the practicality of RS-based memory models. To our knowledge, this paper is the first to consider the problem of availability for memory consistency models that throw consistency exceptions. We first extend existing approaches that enforce RSx , a memory model based on serializability of synchronization-free regions (SFRs), to avoid region conflicts and thus consistency exceptions. These new approaches demonstrate both the potential for and limitations of avoiding consistency exceptions under RSx. To improve availability further, we introduce (1) a new memory model called RIx based on isolation of SFRs and (2) a new approach called Avalon that provides RIx. We demonstrate two variants of Avalon that offer different performance-availability tradeoffs for RIx. An evaluation on real Java programs shows that this work's novel approaches are able to reduce consistency exceptions, thereby improving the applicability of strong memory consistency models. Furthermore, the approaches provide compelling points in the performance-availability tradeoff space for memory consistency enforcement. RIx and Avalon thus represent a promising direction for tackling the challenge of availability under strong consistency models that throw consistency exceptions.

The optimistic variants of Multi-Version Concurrency Control (MVCC) avoid blocking concurrent transactions at the cost of having a validation phase. Upon failure in the validation phase, the transaction is usually aborted and restarted from scratch. The "abort and restart" approach becomes a performance bottleneck for use cases with high contention objects or long running transactions. In addition, restarting from scratch creates a negative feedback loop in the system, because the system incurs additional overhead that may create even more conflicts. In this paper, we propose a novel approach for conflict resolution in MVCC for in-memory databases. This low overhead approach summarizes the transaction programs in the form of a dependency graph. The dependency graph also contains the constructs used in the validation phase of the MVCC algorithm. Then, when encountering conflicts among transactions, our mechanism quickly detects the conflict locations in the program and partially re-executes the conflicting transactions. This approach maximizes the reuse of the computations done in the initial execution round, and increases the transaction processing throughput.

In this paper, we propose one comprehensive distributed database transaction method for InfiniBand transaction integrity in the distributed heterogeneous environment caused by data and application expansion. The method first integrates the functions of the standard online transaction engine and then uses the optimistic concurrency control technique to deal with the online memory allocation problem. On the one hand, it reduces the delay time of the online transaction and on the other hand, allocates the computing cost of the transaction to the server and the client. In the existing enterprise network environment using YCSB as a benchmark test shows that the different keys under the method of response speed are the fastest. The result shows that this kind of hybrid processing scheme can make full use of the advantages of remote direct memory access and fast network, which can further improve the consistency and reliability of the distributed database system.

We will focused the concept of serializability in order to ensure the correct processing of transactions. However, both serializability and relevant properties within transaction-based applications might be affected. Ensure transaction serialization in corrupt systems is one of the demands that can handle properly interrelated transactions, which prevents blocking situations that involve the inability to commit either transaction or related sub-transactions. In addition some transactions has been marked as malicious and they compromise the serialization of running system. In such context, this paper proposes an approach for the processing of transactions in a cloud of databases environment able to secure serializability in running transactions whether the system is compromised or not. We propose also an intrusion tolerant scheme to ensure the continuity of the running transactions. A case study and a simulation result are shown to illustrate the capabilities of the suggested system.

The requirements for OLTP database systems are becoming ever more demanding. Domains such as finance and computer games increasingly mandate that developers be able to encode complex application logic and control transaction latencies in in-memory databases. At the same time, infrastructure engineers in these domains need to experiment with and deploy OLTP database architectures that ensure application scalability and maximize resource utilization in modern machines. In this paper, we propose a relational actor programming model for in-memory databases as a novel, holistic approach towards fulfilling these challenging requirements. Conceptually, relational actors, or reactors for short, are application-defined, isolated logical actors that encapsulate relations and process function calls asynchronously. Reactors ease reasoning about correctness by guaranteeing serializability of application-level function calls. In contrast to classic transactional models, however, reactors allow developers to take advantage of intra-transaction parallelism and state encapsulation in their applications to reduce latency and improve locality. Moreover, reactors enable a new degree of flexibility in database deployment. We present ReactDB, a system design exposing reactors that allows for flexible virtualization of database architecture between the extremes of shared-nothing and shared-everything without changes to application code. Our experiments illustrate latency control, low overhead, and asynchronicity trade-offs with ReactDB in OLTP benchmarks., Comment: Extended version of SIGMOD 2018 paper with an expanded appendix consisting of additional experiments, figures and code examples

Serializability is a well-understood correctness criterion that simplifies reasoning about the behavior of concurrent transactions by ensuring they are isolated from each other while they execute. However, enforcing serializable isolation comes at a steep cost in performance and hence database systems in practice support, and often encourage, developers to implement transactions using weaker alternatives. Unfortunately, the semantics of weak isolation is poorly understood, and usually explained only informally in terms of low-level implementation artifacts. Consequently, verifying high-level correctness properties in such environments remains a challenging problem. To address this issue, we present a novel program logic that enables compositional reasoning about the behavior of concurrently executing weakly-isolated transactions. Recognizing that the proof burden necessary to use this logic may dissuade application developers, we also describe an inference procedure based on this foundation that ascertains the weakest isolation level that still guarantees the safety of high-level consistency invariants associated with such transactions. The key to effective inference is the observation that weakly-isolated transactions can be viewed as functional (monadic) computations over an abstract database state, allowing us to treat their operations as state transformers over the database. This interpretation enables automated verification using off-the-shelf SMT solvers. Case studies and experiments of real-world applications (written in an embedded DSL in OCaml) demonstrate the utility of our approach., Comment: 46 pages, 12 figures

Software Transactional Memory (STM) algorithms provide programmers with a high-level synchronization technique for concurrent access to shared state. STMs typically guarantee some sort of serializability: the concurrent execution of transactions appears to occur in a sequential order. With Guerraoui and Kapalka’s 2008 paper, serializability of software transactions has been phrased as opacity. While opacity has been accepted as the standard correctness criterion for STMs, later verification approaches nevertheless adopt different formulations – claiming them to be opacity.

P-Store is a well-known partially replicated transactional data store that combines wide-area replication, data partition, some fault tolerance, serializability, and limited use of atomic multicast. In addition, a number of recent data store designs can be seen as extensions of P-Store. This paper describes the formalization and formal analysis of P-Store using the rewriting logic framework Maude. As part of this work, this paper specifies group communication commitment and defines an abstract Maude model of atomic multicast, both of which are key building blocks in many data store designs. Maude model checking analysis uncovered a non-trivial error in P-Store; this paper also formalizes a correction of P-Store whose analysis did not uncover any flaw.

This article describes a transactional memory execution model intended to exploit maximum parallelism from sequential and multithreaded programs. A program code section is partitioned into chunks that will be mapped onto threads and executed transactionally. These transactions run concurrently and out of order, trying to exploit maximum parallelism but managed by a specific fully distributed commit control to meet data dependencies. To accomplish correct parallel execution, a partial precedence order relation is derived from the program code section and/or defined by the programmer. When a conflict between chunks is eagerly detected, the precedence order relation is used to determine the best policy to solve the conflict that preserves the precedence order while maximizing concurrency. The model defines a new transactional state called executed but not committed . This state allows exploiting concurrency on two levels: intrathread and interthread. Intrathread concurrency is improved by having pending uncommitted transactions while executing a new one in the same thread. The new state improves interthread concurrency because it permits out-of-order transaction commits regarding the precedence order. Our model has been implemented in a lightweight software transactional memory system, TinySTM, and has been evaluated on a set of benchmarks obtaining an important performance improvement over the baseline TM system.

In multi-version databases, updates and deletions of records by transactions require appending a new record to tables rather than performing in-place updates. This mechanism incurs non-negligible performance overhead in the presence of multiple indexes on a table, where changes need to be propagated to all indexes. Additionally, an uncommitted record update will block other active transactions from using the index to fetch the most recently committed values for the updated record. In general, in order to support snapshot isolation and/or multi-version concurrency, either each active transaction is forced to search a database temporary area (e.g., roll-back segments) to fetch old values of desired records, or each transaction is forced to scan the entire table to find the older versions of the record in a multi-version database (in the absence of specialized temporal indexes). In this work, we describe a novel kV-Indirection structure to enable efficient (parallelizable) optimistic and pessimistic multi-version concurrency control by utilizing the old versions of records (at most two versions of each record) to provide direct access to the recent changes of records without the need of temporal indexes. As a result, our technique results in higher degree of concurrency by reducing the clashes between readers and writers of data and avoiding extended lock delays. We have a working prototype of our concurrency model and kV-Indirection structure in a commercial database and conducted an extensive evaluation to demonstrate the benefits of our multi-version concurrency control, and we obtained orders of magnitude speed up over the single-version concurrency control.