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.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…
- 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…
- 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…
- 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…
- 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…
- 06.06System componentsIn this section, we will discuss the following core components and techniques used to build a key-value store: Data partitionData replicationConsistencyInconsistency…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
- 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…
References
Summary
- Amazon DynamoDB: https://aws.amazon.com/dynamodb/
- memcached: https://memcached.org/
- Redis: https://redis.io/
- Dynamo: Amazon’s Highly Available Key-value Store: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
- Cassandra: https://cassandra.apache.org/
- Bigtable: A Distributed Storage System for Structured Data: https://static.googleusercontent.com/media/research.google.com/en//archive/bigtableosdi06.pdf
- Merkle tree: https://en.wikipedia.org/wiki/Merkle_tree
- Cassandra architecture: https://cassandra.apache.org/doc/latest/architecture/
- SStable: https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/
- Bloom filter https://en.wikipedia.org/wiki/Bloom_filter