What Is This Course About?

Introduction

Dynamo: Introduction

High-Level Architecture

Data Partitioning

Replication

Vector Clocks and Conflicting Data

The Life of Dynamo’s put() & get() Operations

Anti-entropy Through Merkle Trees

Gossip Protocol

Dynamo Characteristics and Criticism

Summary: Dynamo

Quiz: Dynamo

Mock Interview: Dynamo

Dynamo: How to design a key value store?

Cassandra: Introduction

High-level Architecture

Cassandra Consistency Levels

Gossiper

Anatomy of Cassandra's Write Operation

Anatomy of Cassandra's Read Operation

Compaction

Tombstones

Summary: Cassandra

Quiz: Cassandra

Mock Interview: Cassandra

Cassandra: How to Design a Wide-column NoSQL Database?

Messaging Systems: Introduction

Kafka: Introduction

Kafka: Deep Dive

Consumer Groups

Kafka Workflow

Role of ZooKeeper

Controller Broker

Kafka Delivery Semantics

Kafka Characteristics

Summary: Kafka

Quiz: Kafka

Mock Interview: Kafka

Kafka: How to Design a Distributed Messaging System?

Chubby: Introduction

Design Rationale

How Chubby Works

File, Directories, and Handles

Locks, Sequencers, and Lock-delays

Sessions and Events

Master Election and Chubby Events

Caching

Database

Scaling Chubby

Summary: Chubby

Quiz: Chubby

Mock Interview: Chubby

Chubby: How to Design a Distributed Locking Service?

Google File System: Introduction

Single Master and Large Chunk Size

Metadata

Master Operations

Anatomy of a Read Operation

Anatomy of a Write Operation

Anatomy of an Append Operation

GFS Consistency Model and Snapshotting

Fault Tolerance, High Availability, and Data Integrity

Garbage Collection

Criticism on GFS

Summary: GFS

Quiz: GFS

Mock Interview: GFS

GFS: How to Design a Distributed File System Storage?

Hadoop Distributed File System: Introduction

Deep Dive

Data Integrity & Caching

Fault Tolerance

HDFS High Availability (HA)

HDFS Characteristics

Summary: HDFS

Quiz: HDFS

Mock Interview: HDFS

HDFS: How to Design File Storage System?

BigTable: Introduction

BigTable Data Model

System APIs

Partitioning and High-level Architecture

SSTable

GFS and Chubby

Bigtable Components

Working with Tablets

The Life of BigTable's Read & Write Operations

Fault Tolerance and Compaction

BigTable Refinements

BigTable Characteristics

 Summary: BigTable

Quiz: BigTable

Mock Interview: BigTable

BigTable: How to Design a Wide Column Storage System? 

Introduction: System Design Patterns

1. Bloom Filters

2. Consistent Hashing

3. Quorum

4. Leader and Follower

5. Write-ahead Log

6. Segmented Log

7. High-Water Mark

8. Lease

9. Heartbeat

10. Gossip Protocol

11. Phi Accrual Failure Detection

12. Split Brain

13. Fencing

14. Checksum

15. Vector Clocks

16. CAP Theorem

17. PACELC Theorem

18. Hinted Handoff

19. Read Repair

20. Merkle Trees

System Design Patterns

Quiz I

Quiz II

Final Assessment

Contact us

Appendix

Grokking the Advanced System Design Interview

Test your knowledge of Dynamo's architecture by answering these questions.

Dynamo uses **consistent hashing** to scale. Furthermore, with the help of Vnodes, adding nodes to the cluster is quite easy. For distributing the load, any newly added node receives Vnodes from existing nodes.

Dynamo replicates data to multiple nodes for reliability and fault-tolerance.

While writing data, if the required node is unreachable, another node can accept writes on its behalf. The write is then kept in a local buffer and sent out once the destination node is healthy again. This process is called **Hinted handoff**, and it makes Dynamo "always writeable" even in the extreme case where only a single node is alive, write requests will still get accepted and eventually processed.

Dynamo ensures durability by replicating data across multiple replicas, as well as storing them on the disk.

Dynamo uses a consistency protocol similar to quorum systems. If $R$ is the minimum number of nodes that must participate in a successful read operation. And $W$ is the same as $R$, except it's for a write operation. Then $R+W > N$ yields a quorum-like system, where $N$ is the total number of replicas. If $N=3$, we can have the following configuration. For faster writes, we can use $R=3, W=1$. This also means that reads will be slower, and data is not very durable. For faster reads, we can use $R=1, W=3$. This also means that writes will be slower, but data will be durable

Using **sloppy quorum** and **hinted handoff**, Dynamo is always available for writes even if the first $N$ nodes in the preference list are not healthy.

Dynamo uses **Merkle trees** to compare replicas of a data range. The principal advantage of using the Merkle tree is that each branch of the tree can be compared independently without requiring nodes to download the entire tree or the whole data set. Merkle trees minimize the amount of data that needs to be transferred for synchronization and reduce the number of disk reads performed during the anti-entropy process.

Dynamo uses **gossip protocol** which enables each node to keep track of state information about the other nodes in the cluster, like which nodes are reachable, what key ranges they are responsible for, etc. Nodes share state information with each other to stay in-sync. Gossip protocol is a peer-to-peer communication mechanism in which nodes periodically exchange state information about themselves and about other nodes they know about. Each node initiates a gossip round every second to exchange state information about itself and other nodes with one other random node. This means that any new events will eventually propagate through the system, and all nodes quickly learn about all other nodes in a cluster.