Writing about computer science topics that I am curious about, ranging from distributed systems to (eventually) bioinformatics.
Late last year, while working on my C++ series and on the lookout for a project to build in C++, I came across "How to Recalculate a Spreadsheet" , which inspired me to build Anchors — a C++ library for incremental computing. I highly recommend reading the post on lord.io if you want to learn about incremental computing, and perhaps return here if you're interested in some implementation details.…
This is a continuation of the series on C++ topics I've found interesting. You can read the earlier parts here and here . Before I started learning C++, I had read about Java being pass-by-value rather than pass-by-reference, but I found it easier to think I was passing objects around by reference. This post begins by summarizing pointers and references in C++, before describing the different…
This is a continuation of the series on C++ topics that I've found interesting, coming from a Java background. You can read the first post here . I'll start this post by describing forward declarations in C++ before talking about header files. Table of Contents Forward declarations Working with multiple files Multiple declarations, single definition Header files Header guards Header files and…
I recently had to learn C++ for work and have done most of that learning so far through Learn C++ . This series of posts will highlight what I have found interesting about C++, especially given my Java background. Note that these posts are not meant to be tutorials on writing C++; I recommend visiting Learn C++ if you want a thorough C++ tutorial. Table of Contents Building a C++ Program…
The final post in this lecture series is about Blockstack. Blockstack is a network for building decentralized applications based on blockchain. I find the idea of decentralized applications appealing because of its promise to give users more ownership and control of their data. Blockstack is also interesting as it's a non-cryptocurrency use of blockchain, which I covered in the previous post .…
Following the lecture on Certificate Transparency , we are exploring Bitcoin, another open system comprising mutually untrustworthy components. Bitcoin is a digital currency for making online payments. I'll start this post by making a case for digital currencies, before describing Bitcoin and how it solves the double-spending problem. Table of Contents Digital Currencies Bitcoin Limitations of the…
This lecture is about building systems out of mutually untrustworthy components—using the Web as a case study. The systems we have seen so far are closed systems for which we have assumed that all the participants are trustworthy. But in an open system like the Web where anyone can take part, and there is no universally trusted authority, trust and security are top-level issues to address. A…
In studying distributed systems, I've come across systems like Spanner , which incurs additional latency for strong consistency, and DynamoDB , which sacrifices strong consistency for low latency in responding to requests. This latency vs consistency tradeoff is one that many systems have to make, and COPS —this lecture's focus—is no exception. What the COPS (Cluster of Order-Preserving Servers)…
This lecture is about building systems at scale. The associated 2013 paper from Facebook doesn't present any new ideas per se, but I found it interesting to see how some ideas this course has covered so far on replication, partitioning and consistency play out in such a large scale system. The paper is about how Facebook uses memcached as a building block for a distributed key-value store.…
In the first lecture of this series, I wrote about MapReduce as a distributed computation framework. MapReduce partitions the input data across worker nodes, which process data in two stages: map and reduce. While MapReduce was innovative, it came with some limitations: Running iterative operations like PageRank in MapReduce involves chaining multiple MapReduce jobs together. Since a MapReduce job…
This lecture on optimistic concurrency control is based on a 2015 paper from Microsoft Research describing a system called FaRM. FaRM (Fast Remote Memory) is a main memory computing platform that provides distributed transactions with strict serializability, high performance, durability and high availability. FaRM takes advantage of two hardware trends to provide these guarantees: Using Remote…
Unlike many other databases that either choose not to support distributed transactions at all or opt for weaker consistency models, Spanner is an example of a distributed database that supports externally consistent distributed transactions. This post will cover how Google Spanner implements a fault-tolerant two-phase commit protocol and how its novel TrueTime API enables it to guarantee external…
Distributed databases typically divide their tables into partitions spread across different servers which get accessed by many clients. In these databases, client transactions often span the different servers as the transactions may need to read from various partitions. A distributed transaction is a database transaction which spans multiple servers. A transaction with the correct behaviour must…
The ideal distributed file system would guarantee that all its users have coherent access to a shared set of files and be easily scalable. It would also be fault-tolerant and require minimal human administration. Frangipani is a distributed file system that approximates this ideal by providing a consistent view of shared files while maintaining a cache for each user, offering the ability to scale…
Amazon Aurora is a distributed database service provided by AWS. Its original paper describes the considerations in building a database for the cloud and details how Aurora's architecture differs from many traditional databases today. This post will explain how traditional databases work and then highlight how Aurora provides great performance through quorum writes and by building a database…
Many distributed systems today sacrifice stronger consistency guarantees for the sake of greater availability and higher throughput. CRAQ , which stands for Chain Replication with Apportioned Queries, is a system designed to challenge this tradeoff. CRAQ's approach differs from existing replication techniques we have seen so far, like in Raft . It improves on the original form of Chain…
This week's lecture was on ZooKeeper , with the original paper being used as a case study. The paper sheds light on the following questions: Can the coordination of distributed systems be handled by a stand-alone general-purpose service? If so, what should the API of that service look like? Can we improve the performance of a system by N times if we add N times replica servers? That is, can the…
One common pattern in the previous systems we have discussed like MapReduce , GFS , and VMware FT is that they all rely on a single entity to make the key decisions. For example: MapReduce has a single master node responsible for organizing the computation among the workers. GFS has a master responsible for picking the primary replica for a chunkserver. VMware FT uses an atomic test-and-set…
Although 'Raft' is mentioned in the title, a better title for this post is 'Concurrency in Go', as Raft will not be discussed until the next post. Also, unlike other posts on this blog, this one will also feature code samples! Examples of good and bad Go code will be shown for building concurrent applications. Note that although the examples below are in Go, these concepts apply more generally to…
This lecture's material was on the subject of replication as a means of achieving fault tolerance in a distributed system. The VMware FT paper was used as a case study on how replication can be implemented. VMware FT Paper Summary Glossary Overview Deterministic Replay FT Protocol Detecting and Handling Failures Practical Implementation of FT Starting and Restarting VMs Managing the Logging…
The Google File System paper is relevant to this course because GFS is an example of distributed storage , which is a key abstraction in building distributed systems. Many distributed systems are either distributed storage systems or systems built on top of distributed storage. Building distributed storage is a hard problem for a couple of reasons: These systems are built to get a high performance…
This course is based on the Go programming language , and this post will introduce some features in Go that make it well suited for building concurrent and distributed applications. Table of Contents Threads Why use threads? What if we can't have multiple threads? Downsides of Event-Driven Programming Threading Challenges Remote Procedure Call (RPC) Dealing with failures RPC Semantics Go RPC…
Background # I started a study group with some of my friends where we'll be going through this course. Over the next couple of weeks, I intend to upload my notes from studying each week's material. MapReduce # This week's material focused on the MapReduce paradigm for data processing. The material included the seminal MapReduce paper by Jeff Dean and Sanjay Ghemawat, and an accompanying video…
Background # I was reading the documentation for Google's Cloud Spanner recently, and came across the claim that the consistency level guaranteed by the database is External Consistency. The documentation then went on to state that External Consistency is a stronger guarantee than Linearizability . I found this confusing because I had come across resources that suggested that these terms referred…
In the first part of Chapter 9, we looked at Linearizability and Causality as consistency guarantees and used those topics to discuss the difference between total order and partial order. We also briefly discussed Lamport timestamps and how they are used to enforce a total ordering of operations across multiple nodes. We concluded by seeing that it's not enough to know the total order of…
Notes from Chapter 9 of Martin Kleppmann's 'Designing Data-Intensive Applications' book. This chapter is split into two parts. In this chapter, we focus on some of the abstractions that applications can rely on in building fault-tolerant distributed systems. One of these is Consensus. Once there's a consensus implementation, applications can use it for things like leader election and state machine…
This is the second part of the series on 'Data Storage on Disk'. This post will focus on database indexes and the underlying data structure of in many relational databases today: B-Trees. Table of Contents Recap of Previous Post. Heaps Navigating Through a Heap Indexes B-Trees "So how does the index relate to the actual data being stored?" Write Amplification in B-Trees B+ Trees Conclusion Further…
Notes from Chapter 8 of Martin Kleppmann's 'Designing Data-Intensive Applications' book In this chapter, we'll look at the things that may go wrong in distributed systems. We'll cover problems with network, clocks and timing issues, and other faults. Table of Contents Faults and Partial Failures Cloud Computing and Supercomputing Unreliable Networks Network Faults in Practice Detecting Faults…
My notes from Chapter 7 of 'Designing Data-Intensive Applications' by Martin Kleppmann. Table of Contents The Meaning of ACID Single-Object and Multi-Object Operations Weak Isolation Levels Read Committed Dirty Reads Dirty Writes Implementing read committed Snapshot Isolation and Repeatable Read Implementing snapshot isolation Indexes and snapshot isolation Repeatable read and naming confusion…
My notes from Chapter 6 of 'Designing Data-Intensive Applications' by Martin Kleppmann. Table of Contents Partitioning and Replication Partitioning of Key-Value Data Partitioning by Key Range Partitioning by Hash of Key Skewed Workloads and Relieving Hot Spots Partitioning and Secondary Indexes Partitioning Secondary Indexes by Document Partitioning Secondary Indexes by Term Rebalancing Partitions…
My notes from the fifth chapter of Martin Kleppmann's book: Designing Data Intensive Applications. Table of Contents Leaders and Followers Synchronous Versus Asynchronous Replication Synchronous Replication Asynchronous Replication Setting Up New Followers Handling Node Outages Scenario A - Follower Failure: Catch-up recovery Scenario B - Leader failure: Failover Implementation of Replication Logs…
These are my notes from the fourth chapter of Martin Kleppmann's Designing Data Intensive Applications. Table of Contents Formats for Encoding Data Language-Specific Formats JSON, XML, and Binary Variants Binary Encoding Modes of Dataflow Dataflow Through Databases Dataflow Through Services: REST and RPC Message-Passing Dataflow Advantages of a message broker Message brokers Distributed actor…
These are my notes from the third chapter of Martin Kleppmann's Designing Data Intensive Applications. Table of Contents Storage Engines Log-Structured Storage Engines Indexing Hash Index SSTables and LSM-Trees Constructing and maintaining SSTables Making an LSM-tree out of SSTables Performance Optimizations B-Trees Making B- Trees reliable B-tree optimizations Comparing B-Trees and LSM-Trees…
These are my notes from the second chapter of Martin Kleppmann's Designing Data Intensive Applications. Table of Contents Relational Model Versus Document Model Relational Versus Document Databases Today Schema Flexibility in the document model Data locality for queries Convergence of document and relational databases Query Languages For Data MapReduce Querying Graph-Like Data Models This chapter…
These are my notes from the first chapter of Martin Kleppmann's Designing Data Intensive Applications. Table of Contents Reliability Hardware Faults Software Errors Human Errors Scalability Describing Load Maintainability Three important concerns in most software systems are reliability, scalability, and maintainability: Reliability: The system should work correctly (performing the correct…
Background # I tend to read a technical book twice before I can convince myself that I've actually read the book. The first time is typically during my commute to work, and the second time is when I'm home and try to take notes from the book. This post is to share the notes I've taken while reading Martin Kleppmann's book: Designing Data-Intensive Applications. This was inspired by Jasdev 's…
Table of Contents Background A bit about data storage on disk Records Pages Writeback Write-ahead Logs Transactions Conclusion/Next Steps Open Question I Still Have Further Reading General Overview of Distributed Systems Records & Pages Write-ahead Logs Background # You may skip this story and go straight to the main post. I've been reading Martin Kleppmann's great book on "Designing…