notexOPENOverview
Notex/Systems/Design a key-value store

Design a key-value store

Always free to read

A key-value store, also referred to as a key-value database, is a non-relational database. Each unique identifier is stored as a key with its associated value. This data…

06

DESIGN CASE STUDIES

Design a key-value store

15 LESSONS · 25 MIN
  1. 06.01Design a key-value storeA key-value store, also referred to as a key-value database, is a non-relational database. Each unique identifier is stored as a key with its associated value. This data…READING1 MIN
  2. 06.02Understand the problem and establish design scopeThere is no perfect design. Each design achieves a specific balance regarding the tradeoffs of the read, write, and memory usage. Another tradeoff has to be made was between…READING1 MIN
  3. 06.03Single server key-value storeDeveloping a key-value store that resides in a single server is easy. An intuitive approach is to store key-value pairs in a hash table, which keeps everything in memory. Even…READING1 MIN
  4. 06.04Distributed key-value storeA distributed key-value store is also called a distributed hash table, which distributes keyvalue pairs across many servers. When designing a distributed system, it is…READING1 MIN
  5. 06.05CAP theoremCAP theorem states it is impossible for a distributed system to simultaneously provide more than two of these three guarantees: consistency, availability, and partition…READING3 MIN
  6. 06.06System componentsIn this section, we will discuss the following core components and techniques used to build a key-value store: Data partitionData replicationConsistencyInconsistency…READING1 MIN
  7. 06.07Data partitionFor large applications, it is infeasible to fit the complete data set in a single server. The simplest way to accomplish this is to split the data into smaller partitions and…READING1 MIN
  8. 06.08Data replicationTo achieve high availability and reliability, data must be replicated asynchronously over N servers, where N is a configurable parameter. These N servers are chosen using the…READING1 MIN
  9. 06.09ConsistencySince data is replicated at multiple nodes, it must be synchronized across replicas. Quorum consensus can guarantee consistency for both read and write operations. Let us…READING3 MIN
  10. 06.10Inconsistency resolution: versioningReplication gives high availability but causes inconsistencies among replicas. Versioning and vector locks are used to solve inconsistency problems. Versioning means treating…READING4 MIN
  11. 06.11Handling failuresAs with any large system at scale, failures are not only inevitable but common. Handling failure scenarios is very important. In this section, we first introduce techniques to…READING4 MIN
  12. 06.12System architecture diagramNow that we have discussed different technical considerations in designing a key-value store, we can shift our focus on the architecture diagram, shown in Figure 6-17. Main…READING1 MIN
  13. 06.13Write pathFigure 6-19 explains what happens after a write request is directed to a specific node. Please note the proposed designs for write/read paths are primary based on the…READING1 MIN
  14. 06.14Read pathAfter a read request is directed to a specific node, it first checks if data is in the memory cache. If so, the data is returned to the client as shown in Figure 6-20. If the…READING1 MIN
  15. 06.15SummaryThis chapter covers many concepts and techniques. To refresh your memory, the following table summarizes features and corresponding techniques used for a distributed key-value…READING1 MIN

References

Summary
  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/bigtableosdi06.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
KEEP EXPLORING

One note leads to another.

Back to the library →
⌕
Search across the entire library ⌘ K