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 talks 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 bloomfilters of the existing SSTables to find the record, if it doesn’t exist then skip the SSTable
• If the bloomfilter says that there may be data check the in-memory key cache
• On 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 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?
• 1 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 fullname. 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 in 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