Videos

Distributed Transactions

I this video, we review serializability and three systems with distributed ACID transactions, namely Spanner, Calvin, and FoundationDB. 



Comments

Post a Comment

Popular posts from this blog

Graph Databases

Image
Graph data is very common in modern applications. The property of this kind of data is the high levels of connectivity between the entities. Although social networks are the most common example for demonstrating graph data and the importance of graph databases, graphs are not limited to social networks; many other applications can be modeled much more clearly and intuitively with graphs. Once we model our data as a graph, we usually want to explore certain parts of the graph to find relations or interesting patterns. That includes simple use cases such as finding a person's friends or friend-of-friends in a social network, or complex patterns revealing frauds in a financial graph. All these applications require fast traversal of graph nodes. Although we can store a graph in a tabular relational database or a NoSQL database such as key-value/document stores, they typically don't provide fast traversal which is critical for graph applications. In this p
Read more

In-memory vs. On-disk Databases

Image
Figure 1 shows the main difference between in-memory and on-disk databases: An in-memory database stores the data in memory and uses disk for backup, while an on-disk database stores the data on disk and uses memory for caching.  Figure 1. In-memory vs On-disk storage engines
Read more

The Paxos algorithm, when presented in plain English, is very simple

Image
Consensus is one of the fundamental problems in distributed systems. In this post, we want to see what is consensus and review the most famous consensus algorithm—Paxos. we will see that despite exaggeration about its complexities, Paxos, at least the singe-decree Paxos that aims to achieve consensus on a single value, is actually very intuitive and easy to understand.
Read more

Amazon DynamoDB: ACID Transactions using Timestamp Ordering

Image
Amazon DynamoDB uses a lightweight transaction protocol via timestamp ordering. Although both Spanner and DynamoDB use timestamps in their transaction protocol, DynamoDB seems significantly simpler than Spanner; while Spanner uses 2PL and MVCC and needs TrueTime, DynamoDB only relies on timestamp ordering and does not use any locking or MVCC scheme. In this post, we want to review the DynamoDB transaction protocol and compare it with Google Spanner. 
Read more

Skip List Data Structure

Image
Skip list is an efficient data structure to store sorted elements. Skip list augments the normal linked list with more metadata to provide better time complexity. Like balanced trees, skip list provides O(logN) time complexity for search/insert/delete. In this post, we review the skip list data structure and see how we can optimize its operation with finger search. We present a simple C++ implementation and provide some experimental results with this implementation. We compare skip list with balanced search trees, and see how for concurrent programs skip list is the clear winner. 
Read more