Key Value Stores
- Low cost scalable DBMSs
- Google’s Bigtable
- Yahoo!’s PNUTS
- Amazon’s Dynamo
- Supports
- Simple key-value-based data model
- Single atomic key-value access guarantees.
Data Model
- Each record is identified by a unique key, and the value can vary in its structure:
- Blob Data Model: the value is a binary string object, i.e., a blob.
- Relational Data Model: the value is structured into multiple columns, each with its own attribute name.
- @question: Is null value permitted?
- Column Family Data Model: the columns in the value field are grouped together into column families, each consisting of a set of columns.
- Example: Bigtable, Cassandra, HBase
Data Distribution
For flexible scaling out to multiple servers
- In general, a table is partitioned into tablets (similar to shards or chunks), which form the units of distribution and load balancing.
- The two main approaches:
- Range partitioning:
- Orders all records lexicographically based on the key, then divides the objects on different servers in that order.
- Hash partitioning:
- Hashes the records based on the key to linear address space, which is then divided among the different servers.
- A typical hashing approach can use a distributed hash table (DHT) such as Chord.
- Range partitioning: