Posts by Tags

Abstract locks

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

5 minute read

Published:

Software transactional memory (STM) is an emergent alternative to mutual exclusion. In STM, the activities are organised as transactions which can commit or abort. Most transactional memory systems synchronise on the basis of read/write conflicts. Two transactions are said to be in conflict if they modify at-least one same object. When conflicting transactions need to commit, we need some mechanism to resolve this conflict. This can be done by forcing either transaction to abort. The benefit of this type of conflict detection and resolution is that the overhead of managing conflicts does not fall to the programmer. But at the same time, this method also severely restricts the concurrency for shared objects which come under contention very often. Read more

Ancestors

Dominance Locking in arbitrary rooted hierarchies

9 minute read

Published:

The current state of affairs in databases is typically oriented towards two-dimensional data. If some data is managed in an apparent multidimensional space, then it is usually achieved by some trick that involves joining tables and pivoting them. This not only makes performing queries on the data difficult and less efficient but also introduces an overhead of managing these multidimensional views. Read more

Availability

Zeus: locality aware distributed transactions

15 minute read

Published:

Typical databases have distributed transactions that update multiple objects. These objects are updated by transactions that span multiple shards and require coordination for state reconciliation. Most popular protocol to reconcile the state is the two phase commit protocol. This distribution is an inherent problem since most transactions access multiple replicas and thus the communication latency between those replicas leads to a slowdown. The commit requiring coordination is also blocking. Zeus fetches the objects involved in a transaction’s operations locally and then performs the reads and writes on the local versions of the objects. Read more

Commutativity

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

5 minute read

Published:

Software transactional memory (STM) is an emergent alternative to mutual exclusion. In STM, the activities are organised as transactions which can commit or abort. Most transactional memory systems synchronise on the basis of read/write conflicts. Two transactions are said to be in conflict if they modify at-least one same object. When conflicting transactions need to commit, we need some mechanism to resolve this conflict. This can be done by forcing either transaction to abort. The benefit of this type of conflict detection and resolution is that the overhead of managing conflicts does not fall to the programmer. But at the same time, this method also severely restricts the concurrency for shared objects which come under contention very often. Read more

Commutativity lattice

Dominators

Dominance Locking in arbitrary rooted hierarchies

9 minute read

Published:

The current state of affairs in databases is typically oriented towards two-dimensional data. If some data is managed in an apparent multidimensional space, then it is usually achieved by some trick that involves joining tables and pivoting them. This not only makes performing queries on the data difficult and less efficient but also introduces an overhead of managing these multidimensional views. Read more

DomLock: a new multi-granularity locking technique for hierarchies

14 minute read

Published:

In the paper “DomLock: a new multi-granularity locking technique for hierarchies” the authors present an interesting technique for locking objects that follow a hierarchical structure. Several applications that operate on objects that form a hierarchy suffer from synchronization bottlenecks because of lock contention. When several transactions operate on different parts of the data hierarchy, there is contention which restricts concurrency. Read more

Dynamic sharding

Zeus: locality aware distributed transactions

15 minute read

Published:

Typical databases have distributed transactions that update multiple objects. These objects are updated by transactions that span multiple shards and require coordination for state reconciliation. Most popular protocol to reconcile the state is the two phase commit protocol. This distribution is an inherent problem since most transactions access multiple replicas and thus the communication latency between those replicas leads to a slowdown. The commit requiring coordination is also blocking. Zeus fetches the objects involved in a transaction’s operations locally and then performs the reads and writes on the local versions of the objects. Read more

Granularity

Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs

6 minute read

Published:

Atomic operations are a key primitive in parallel computing. Typically atomic ownership is provided via mutual exclusion which is achieved in the simplest way through locking. A lock is said to be finely grained if it exclusively locks only a small part of the data structure and thus suffers from low contention. The question still remains. What should we lock and how fine can the lock granularity be without sacrificing on performance? At what point does the cost of maintaining locks override the benefit achieved from the finer locking. Read more

Graph Databases

Graph queries

Graphs

Dominance Locking in arbitrary rooted hierarchies

9 minute read

Published:

The current state of affairs in databases is typically oriented towards two-dimensional data. If some data is managed in an apparent multidimensional space, then it is usually achieved by some trick that involves joining tables and pivoting them. This not only makes performing queries on the data difficult and less efficient but also introduces an overhead of managing these multidimensional views. Read more

DomLock: a new multi-granularity locking technique for hierarchies

14 minute read

Published:

In the paper “DomLock: a new multi-granularity locking technique for hierarchies” the authors present an interesting technique for locking objects that follow a hierarchical structure. Several applications that operate on objects that form a hierarchy suffer from synchronization bottlenecks because of lock contention. When several transactions operate on different parts of the data hierarchy, there is contention which restricts concurrency. Read more

Locality

Zeus: locality aware distributed transactions

15 minute read

Published:

Typical databases have distributed transactions that update multiple objects. These objects are updated by transactions that span multiple shards and require coordination for state reconciliation. Most popular protocol to reconcile the state is the two phase commit protocol. This distribution is an inherent problem since most transactions access multiple replicas and thus the communication latency between those replicas leads to a slowdown. The commit requiring coordination is also blocking. Zeus fetches the objects involved in a transaction’s operations locally and then performs the reads and writes on the local versions of the objects. Read more

Lock Contention

Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs

6 minute read

Published:

Atomic operations are a key primitive in parallel computing. Typically atomic ownership is provided via mutual exclusion which is achieved in the simplest way through locking. A lock is said to be finely grained if it exclusively locks only a small part of the data structure and thus suffers from low contention. The question still remains. What should we lock and how fine can the lock granularity be without sacrificing on performance? At what point does the cost of maintaining locks override the benefit achieved from the finer locking. Read more

Locking

Dominance Locking in arbitrary rooted hierarchies

9 minute read

Published:

The current state of affairs in databases is typically oriented towards two-dimensional data. If some data is managed in an apparent multidimensional space, then it is usually achieved by some trick that involves joining tables and pivoting them. This not only makes performing queries on the data difficult and less efficient but also introduces an overhead of managing these multidimensional views. Read more

DomLock: a new multi-granularity locking technique for hierarchies

14 minute read

Published:

In the paper “DomLock: a new multi-granularity locking technique for hierarchies” the authors present an interesting technique for locking objects that follow a hierarchical structure. Several applications that operate on objects that form a hierarchy suffer from synchronization bottlenecks because of lock contention. When several transactions operate on different parts of the data hierarchy, there is contention which restricts concurrency. Read more

Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs

6 minute read

Published:

Atomic operations are a key primitive in parallel computing. Typically atomic ownership is provided via mutual exclusion which is achieved in the simplest way through locking. A lock is said to be finely grained if it exclusively locks only a small part of the data structure and thus suffers from low contention. The question still remains. What should we lock and how fine can the lock granularity be without sacrificing on performance? At what point does the cost of maintaining locks override the benefit achieved from the finer locking. Read more

Non-Blocking algorithms

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

5 minute read

Published:

Software transactional memory (STM) is an emergent alternative to mutual exclusion. In STM, the activities are organised as transactions which can commit or abort. Most transactional memory systems synchronise on the basis of read/write conflicts. Two transactions are said to be in conflict if they modify at-least one same object. When conflicting transactions need to commit, we need some mechanism to resolve this conflict. This can be done by forcing either transaction to abort. The benefit of this type of conflict detection and resolution is that the overhead of managing conflicts does not fall to the programmer. But at the same time, this method also severely restricts the concurrency for shared objects which come under contention very often. Read more

OLTP

Object Graphs

Dominance Locking in arbitrary rooted hierarchies

9 minute read

Published:

The current state of affairs in databases is typically oriented towards two-dimensional data. If some data is managed in an apparent multidimensional space, then it is usually achieved by some trick that involves joining tables and pivoting them. This not only makes performing queries on the data difficult and less efficient but also introduces an overhead of managing these multidimensional views. Read more

DomLock: a new multi-granularity locking technique for hierarchies

14 minute read

Published:

In the paper “DomLock: a new multi-granularity locking technique for hierarchies” the authors present an interesting technique for locking objects that follow a hierarchical structure. Several applications that operate on objects that form a hierarchy suffer from synchronization bottlenecks because of lock contention. When several transactions operate on different parts of the data hierarchy, there is contention which restricts concurrency. Read more

Optimistic parallelism

Strict serializability

Zeus: locality aware distributed transactions

15 minute read

Published:

Typical databases have distributed transactions that update multiple objects. These objects are updated by transactions that span multiple shards and require coordination for state reconciliation. Most popular protocol to reconcile the state is the two phase commit protocol. This distribution is an inherent problem since most transactions access multiple replicas and thus the communication latency between those replicas leads to a slowdown. The commit requiring coordination is also blocking. Zeus fetches the objects involved in a transaction’s operations locally and then performs the reads and writes on the local versions of the objects. Read more

Synchronization

DomLock: a new multi-granularity locking technique for hierarchies

14 minute read

Published:

In the paper “DomLock: a new multi-granularity locking technique for hierarchies” the authors present an interesting technique for locking objects that follow a hierarchical structure. Several applications that operate on objects that form a hierarchy suffer from synchronization bottlenecks because of lock contention. When several transactions operate on different parts of the data hierarchy, there is contention which restricts concurrency. Read more

Transactional Boosting

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

5 minute read

Published:

Software transactional memory (STM) is an emergent alternative to mutual exclusion. In STM, the activities are organised as transactions which can commit or abort. Most transactional memory systems synchronise on the basis of read/write conflicts. Two transactions are said to be in conflict if they modify at-least one same object. When conflicting transactions need to commit, we need some mechanism to resolve this conflict. This can be done by forcing either transaction to abort. The benefit of this type of conflict detection and resolution is that the overhead of managing conflicts does not fall to the programmer. But at the same time, this method also severely restricts the concurrency for shared objects which come under contention very often. Read more

Transactional memory

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

5 minute read

Published:

Software transactional memory (STM) is an emergent alternative to mutual exclusion. In STM, the activities are organised as transactions which can commit or abort. Most transactional memory systems synchronise on the basis of read/write conflicts. Two transactions are said to be in conflict if they modify at-least one same object. When conflicting transactions need to commit, we need some mechanism to resolve this conflict. This can be done by forcing either transaction to abort. The benefit of this type of conflict detection and resolution is that the overhead of managing conflicts does not fall to the programmer. But at the same time, this method also severely restricts the concurrency for shared objects which come under contention very often. Read more

Transactions

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

5 minute read

Published:

Software transactional memory (STM) is an emergent alternative to mutual exclusion. In STM, the activities are organised as transactions which can commit or abort. Most transactional memory systems synchronise on the basis of read/write conflicts. Two transactions are said to be in conflict if they modify at-least one same object. When conflicting transactions need to commit, we need some mechanism to resolve this conflict. This can be done by forcing either transaction to abort. The benefit of this type of conflict detection and resolution is that the overhead of managing conflicts does not fall to the programmer. But at the same time, this method also severely restricts the concurrency for shared objects which come under contention very often. Read more

Lock Coarsening: Eliminating Lock Overhead in Automatically Parallelized Object-Based Programs

6 minute read

Published:

Atomic operations are a key primitive in parallel computing. Typically atomic ownership is provided via mutual exclusion which is achieved in the simplest way through locking. A lock is said to be finely grained if it exclusively locks only a small part of the data structure and thus suffers from low contention. The question still remains. What should we lock and how fine can the lock granularity be without sacrificing on performance? At what point does the cost of maintaining locks override the benefit achieved from the finer locking. Read more

Zeus: locality aware distributed transactions

15 minute read

Published:

Typical databases have distributed transactions that update multiple objects. These objects are updated by transactions that span multiple shards and require coordination for state reconciliation. Most popular protocol to reconcile the state is the two phase commit protocol. This distribution is an inherent problem since most transactions access multiple replicas and thus the communication latency between those replicas leads to a slowdown. The commit requiring coordination is also blocking. Zeus fetches the objects involved in a transaction’s operations locally and then performs the reads and writes on the local versions of the objects. Read more

Trees

Dominance Locking in arbitrary rooted hierarchies

9 minute read

Published:

The current state of affairs in databases is typically oriented towards two-dimensional data. If some data is managed in an apparent multidimensional space, then it is usually achieved by some trick that involves joining tables and pivoting them. This not only makes performing queries on the data difficult and less efficient but also introduces an overhead of managing these multidimensional views. Read more

DomLock: a new multi-granularity locking technique for hierarchies

14 minute read

Published:

In the paper “DomLock: a new multi-granularity locking technique for hierarchies” the authors present an interesting technique for locking objects that follow a hierarchical structure. Several applications that operate on objects that form a hierarchy suffer from synchronization bottlenecks because of lock contention. When several transactions operate on different parts of the data hierarchy, there is contention which restricts concurrency. Read more

pipelining

Zeus: locality aware distributed transactions

15 minute read

Published:

Typical databases have distributed transactions that update multiple objects. These objects are updated by transactions that span multiple shards and require coordination for state reconciliation. Most popular protocol to reconcile the state is the two phase commit protocol. This distribution is an inherent problem since most transactions access multiple replicas and thus the communication latency between those replicas leads to a slowdown. The commit requiring coordination is also blocking. Zeus fetches the objects involved in a transaction’s operations locally and then performs the reads and writes on the local versions of the objects. Read more

replication

Zeus: locality aware distributed transactions

15 minute read

Published:

Typical databases have distributed transactions that update multiple objects. These objects are updated by transactions that span multiple shards and require coordination for state reconciliation. Most popular protocol to reconcile the state is the two phase commit protocol. This distribution is an inherent problem since most transactions access multiple replicas and thus the communication latency between those replicas leads to a slowdown. The commit requiring coordination is also blocking. Zeus fetches the objects involved in a transaction’s operations locally and then performs the reads and writes on the local versions of the objects. Read more