In this paper, we present a framework that automatically decomposes programmer-written flat transactions into closed-nested transactions. The framework relies on two key mechanisms for the decomposition. The first is ...
详细信息
ISBN:
(纸本)9781479986484
In this paper, we present a framework that automatically decomposes programmer-written flat transactions into closed-nested transactions. The framework relies on two key mechanisms for the decomposition. The first is a static tool that analyzes application source code and produces a compact representation of transactions' business logic. The second is a runtime monitor that captures the actual contention level of shared objects and, relying on the outcome of the static tool, triggers the optimal closed-nested configuration for the workload at hand. We implemented this framework atop QR-CN, an open source fault-tolerant DTM written in Java. Our experimental studies conducted using the TPC-C, Vacation and Bank benchmarks reveal that the framework yields better performance than flat nesting and manual closed nesting, especially when the workload changes.
In this paper we consider designing contention managers for distributed software transactionalmemory (DTM), given an input of n transactions sharing s objects in a network of m nodes. We first construct a dynamic ord...
详细信息
ISBN:
(纸本)9783319096209;9783319096193
In this paper we consider designing contention managers for distributed software transactionalmemory (DTM), given an input of n transactions sharing s objects in a network of m nodes. We first construct a dynamic ordering conflict graph G(c)* (phi(kappa)) for an offline algorithm (kappa, phi(kappa)). We show that finding an optimal schedule is equivalent to finding the offline algorithm for which the weight of the longest weighted path in G(c)* (phi(kappa)) is minimized. We further illustrate that when the set of transactions are dynamically generated, processing transactions according to a chi(G(c))- coloring of Gc does not lead to an optimal schedule, where chi(G(c)) is the chromatic number of Gc. We prove that, for DTM, any online work conserving deterministic contention manager provides an Omega(max[s, s(2)/(D) over bar]) competitive ratio in a network with normalized diameter (D) over bar. Compared with the Omega(s) competitive ratio for multiprocessor STM, the performance guarantee for DTM degrades by a factor proportional to s/(D) over bar. To break this lower bound, we present a randomized algorithm CUTTING, which needs partial information of transactions and an approximate algorithm A for the traveling salesman problem with approximation ratio phi(A). We show that the average case competitive ratio of CUTTING is O (s . phi(A) . log(2) m log(2) n), which is close to O(s).
In this paper we propose executive deferred update replication (EDUR), a novel algorithm for multi-primary replication of transactionalmemory and databases. EDUR streamlines transaction certification (i.e., checking ...
详细信息
ISBN:
(纸本)9781479955848
In this paper we propose executive deferred update replication (EDUR), a novel algorithm for multi-primary replication of transactionalmemory 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.
Modern transactional processing systems need to be fast and scalable, but this means many such systems settled for weak consistency models. It is however possible to achieve all of strong consistency, high scalability...
详细信息
ISBN:
(纸本)9781450329200
Modern transactional processing systems need to be fast and scalable, but this means many such systems settled for weak consistency models. It is however possible to achieve all of strong consistency, high scalability and high performance, by using fine-grained partitions and light-weight concurrency control that avoids superuous synchronization and other overheads such as lock management. Independent transactions are one such mechanism, that rely on good partitions and appropriately defined transactions. On the downside, it is not usually straightforward to determine optimal partitioning schemes, especially when dealing with non-trivial amounts of data. Our work attempts to solve this problem by automating the partitioning process, choosing the correct transactional primitive, and routing transactions appropriately.
transactionalmemory is a rather novel approach to concurrency control in parallel computing, that has just recently found its way into distributed systems research. However, the research concentrates mainly on single...
详细信息
transactionalmemory is a rather novel approach to concurrency control in parallel computing, that has just recently found its way into distributed systems research. However, the research concentrates mainly on single processor solutions or cluster environment. In this paper we argue, that peer-to-peer systems would require a different design of transactionalmemory because of the increased failure-rate of nodes, slower network and possibility of network splits. We also present a few of our design ideas, namely increased performance and fault tolerance through the use of higher-level conflict detection and resolution via abstract data types and eventually consistency, that as we think could be important to a successful implementation of a scalable and resilient transactionalmemory.
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 deferr...
详细信息
ISBN:
(纸本)9780769550008
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.
Cloud computing enables diverse new application areas for distributed computing. Many upcoming cloud applications do not fit to simple programming models such as "embarrassing parallelism" but have complex d...
详细信息
ISBN:
(纸本)9781467345651;9780769549033
Cloud computing enables diverse new application areas for distributed computing. Many upcoming cloud applications do not fit to simple programming models such as "embarrassing parallelism" but have complex data dependencies and require atomic operations spanning multiple objects. Some large-scale storage systems already implement atomic multi-object operations, but they do not address the complementary problem of efficiently propagating replica updates. In this paper, we present the design and implementation of a smart replication protocol in the ECRAM in-memory storage, which supports atomic multi-object operations. The performance analysis shows that the adaptive mechanism requires much less bandwidth, less memory, and results in improved application performance and responsiveness.
暂无评论