System Design Interview

Wrap Up

Wrap up 1 min readLesson 5 of 5

This chapter covers many concepts and techniques. To refresh your memory, the following table summarizes features and corresponding techniques used for a distributed key-value store.

Goal/ProblemsTechnique
Ability to store big dataUse consistent hashing to spread load across servers
High availability readsData replicationMulti-datacenter setup
Highly available writesVersioning and conflict resolution with vector clocks
Dataset partitionConsistent Hashing
Incremental scalabilityConsistent Hashing
HeterogeneityConsistent Hashing
Tunable consistencyQuorum consensus
Handling temporary failuresSloppy quorum and hinted handoff
Handling permanent failuresMerkle tree
Handling data center outageCross-datacenter replication

Table 2

Reference materials

  1. Amazon DynamoDB: https://aws.amazon.com/dynamodb/
  2. memcached: https://memcached.org/
  3. Redis: https://redis.io/
  4. Dynamo: Amazon’s Highly Available Key-value Store: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
  5. Cassandra: https://cassandra.apache.org/
  6. Bigtable: A Distributed Storage System for Structured Data: https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf
  7. Merkle tree: https://en.wikipedia.org/wiki/Merkle_tree
  8. Cassandra architecture: https://cassandra.apache.org/doc/latest/architecture/
  9. SStable: https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/
  10. Bloom filter https://en.wikipedia.org/wiki/Bloom_filter

Finished reading?

Mark it complete to track your progress.

PreviousArchitecture, Write and Read PathsDesign a Key-Value StoreNext Understand the ProblemDesign a Unique ID Generator