Ayush Pandey

Ayush Pandey

Distributed systems researcher

Posts by Tags

Abstract locks

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

2 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.

Ancestors

Dominance Locking in arbitrary rooted hierarchies

4 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.

Availability

Zeus: locality aware distributed transactions

7 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.

Commutativity

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

2 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.

Commutativity lattice

Concurrency systems

Consistency models and their interplay

1 minute read

Published:

Consistency models are difficult to explain and even more difficult to understand. At the time of writing, there is about 40 consistency levels that I know of, each with its own set of assumptions and implications which in a lot of cases are only subtly different between different consistency levels. Adding to this complexity is the fact that different communities refer to different things with the same name. Take Snapshot Isolation(SI) for example. To a relational database practitioner, SI means concurrent snapshots that remain isolated from each other. It is not really a consistency level but rather the Isolation property in the ACID mode. But for a distributed systems practitioner, SI means something completely different.

Consistency models

Consistency models and their interplay

1 minute read

Published:

Consistency models are difficult to explain and even more difficult to understand. At the time of writing, there is about 40 consistency levels that I know of, each with its own set of assumptions and implications which in a lot of cases are only subtly different between different consistency levels. Adding to this complexity is the fact that different communities refer to different things with the same name. Take Snapshot Isolation(SI) for example. To a relational database practitioner, SI means concurrent snapshots that remain isolated from each other. It is not really a consistency level but rather the Isolation property in the ACID mode. But for a distributed systems practitioner, SI means something completely different.

Distributed computing

Fallacies of distributed computing

less than 1 minute read

Published:

Today while looking at some literature about serverless computing from RedHat, i came across a wikipedia article that mentions the fallacies of distributed computing. The original assertions were made by L Peter Deustch and others at Sun Microsystems.

Distributed systems

Consistency models and their interplay

1 minute read

Published:

Consistency models are difficult to explain and even more difficult to understand. At the time of writing, there is about 40 consistency levels that I know of, each with its own set of assumptions and implications which in a lot of cases are only subtly different between different consistency levels. Adding to this complexity is the fact that different communities refer to different things with the same name. Take Snapshot Isolation(SI) for example. To a relational database practitioner, SI means concurrent snapshots that remain isolated from each other. It is not really a consistency level but rather the Isolation property in the ACID mode. But for a distributed systems practitioner, SI means something completely different.

Dominators

Dominance Locking in arbitrary rooted hierarchies

4 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.

DomLock: a new multi-granularity locking technique for hierarchies

7 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.

Dynamic sharding

Zeus: locality aware distributed transactions

7 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.

Granularity

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

3 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.

Graph Databases

The World of Graph Databases from An Industry Perspective

5 minute read

Published:

This paper by Yuanyuan Tian presents an overview of the graph database landscape from an industry perspective. It covers the graph database landscape, graph query languages and several graph database products. It also discusses the challenges and opportunities in the graph database industry.

Graph queries

The World of Graph Databases from An Industry Perspective

5 minute read

Published:

This paper by Yuanyuan Tian presents an overview of the graph database landscape from an industry perspective. It covers the graph database landscape, graph query languages and several graph database products. It also discusses the challenges and opportunities in the graph database industry.

Graphs

Dominance Locking in arbitrary rooted hierarchies

4 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.

DomLock: a new multi-granularity locking technique for hierarchies

7 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.

Locality

Zeus: locality aware distributed transactions

7 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.

Lock Contention

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

3 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.

Locking

Dominance Locking in arbitrary rooted hierarchies

4 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.

DomLock: a new multi-granularity locking technique for hierarchies

7 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.

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

3 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.

Non-Blocking algorithms

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

2 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.

OLTP

The World of Graph Databases from An Industry Perspective

5 minute read

Published:

This paper by Yuanyuan Tian presents an overview of the graph database landscape from an industry perspective. It covers the graph database landscape, graph query languages and several graph database products. It also discusses the challenges and opportunities in the graph database industry.

Object Graphs

Dominance Locking in arbitrary rooted hierarchies

4 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.

DomLock: a new multi-granularity locking technique for hierarchies

7 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.

Optimistic parallelism

Strict serializability

Zeus: locality aware distributed transactions

7 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.

Synchronization

DomLock: a new multi-granularity locking technique for hierarchies

7 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.

System Design

Fallacies of distributed computing

less than 1 minute read

Published:

Today while looking at some literature about serverless computing from RedHat, i came across a wikipedia article that mentions the fallacies of distributed computing. The original assertions were made by L Peter Deustch and others at Sun Microsystems.

Transactional Boosting

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

2 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.

Transactional memory

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

2 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.

Transactions

Consistency models and their interplay

1 minute read

Published:

Consistency models are difficult to explain and even more difficult to understand. At the time of writing, there is about 40 consistency levels that I know of, each with its own set of assumptions and implications which in a lot of cases are only subtly different between different consistency levels. Adding to this complexity is the fact that different communities refer to different things with the same name. Take Snapshot Isolation(SI) for example. To a relational database practitioner, SI means concurrent snapshots that remain isolated from each other. It is not really a consistency level but rather the Isolation property in the ACID mode. But for a distributed systems practitioner, SI means something completely different.

Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

2 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.

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

3 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.

Zeus: locality aware distributed transactions

7 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.

Trees

Dominance Locking in arbitrary rooted hierarchies

4 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.

DomLock: a new multi-granularity locking technique for hierarchies

7 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.

pipelining

Zeus: locality aware distributed transactions

7 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.

replication

Zeus: locality aware distributed transactions

7 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.