Engine

Features

• Consistent hashing
• Replication factor: replicas of the data across the cluster.
• Consistency level controlled for each query
• Up to 2 billion key-value pairs in a row.

• Replication factor = 3
• Consistency level = QUORUM
• Clients talk to any node. The node hashes the partition key and finds the location of the data.
• Data is read from all the replicas, waiting for responses until we reach a quorum.

• Acknowledged when we write to both the commit log (append-only) and the memtable.
• When the memtable becomes full, it’s flushed into an SSTable.
• Periodically, SSTables are merged.

• Check if the key is in the in-memory row cache.
• Query the Bloom filters of the existing SSTables to find the record. If it doesn’t exist, then skip the SSTable.
• If the Bloom filter says that there may be data, check the in-memory key cache.
• On a miss, get the data from the SSTable and merge it with the data in the memtable. Write the key to the in-memory key cache and the merged result to the in-memory row cache.

Data modeling

Goals

• Spread data evenly around the cluster.
• Minimize the number of partitions read.
• Keep partitions manageable.

Process

• Identify initial entities and relationships.
• Key attributes (map to PK columns).
• Equality search attributes (map to the beginning of the PK).
• Inequality search attributes (map to clustering columns).
• Other attributes:
  • Static attributes are shared within a given partition.

primary key = partition key + clustering columns

Legend:

K Partition key
C Clustering key and their ordering (ascending or descending)
S Static columns, fixed and shared per partition

Validation

• Is data evenly spread?
• One partition per read?
• Are writes (overwrites) possible?
• How large are the partitions? Let’s assume that each partition should have at most 1M cells: $n_{cells}=n_{rows}\ast (n_{cols}-n_K-n_S)+n_S<1M$.
• How much data duplication?

Examples

Store books by ISBN

Register a user uniquely identified by an email/password. We also want their full name. They will be accessed by email and password or by UUID.

Find books a logged-in user has read, sorted by title and author.

Interaction of every user on the website

1 year  = 333k / 365 / 24 = 38 actions / h
1 month = 333k / 30 / 24  = 462 actions / h (most realistic case)
1 week  = 333k / 7 / 24   = 1984 actions / h