An Overview of NOSQL Databases

Subhajit Sidhanta,
Assistant Professor,
IIT Bhilai, EECS

1
 Relational Database Management Systems
●
Well-defined formal foundations (relational data model)

schema

instance/
state

Figure from “Fundamentals of Database Systems” by Elmasri and Navathe, Addison Wesley.

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 2
Relational Database Management Systems
●
Well-defined formal foundations (relational data model)
●
SQL – powerful declarative language
– querying
– data manipulation
– database definition

●
Support of transactions with ACID properties
(Atomicity, Consistency preservation, Isolation, Durability)
●
Established technology (developed since the 1970s)
– many vendors
– highly mature systems
– experienced users and administrators

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 3
Business world has evolved
●
Organizations and companies (whole industries) shift to
the digital economy powered by the Internet
●
Central aspect: new IT applications that allow companies
to run their business and to interact with costumers
– Web applications
– Mobile applications
– Connected devices (“Internet of Things”)

Image source: [Link]

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 4
New Challenges for Database Systems
●
Increasing numbers of concurrent users/clients
– tens of thousands, perhaps millions
– globally distributed
– expectations: consistently high performance
and 24/7 availability (no downtime)
●
Different types of data
– huge amounts (generated by users and devices)
– data from different sources together
– frequent schema changes or no schema at all
– semi-structured and unstructured data
●
Usage may change rapidly and unpredictably

Image source: [Link]

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 5
``NoSQL”
●
Some interpretations (without precise definition):
– “no to SQL”
– “not only SQL”
– “not relational”
●
1998: first used for an RDBMS* that omitted usage of SQL
●
2009: picked up again to name a conference on
“open-source, distributed, non-relational databases”
●
Since then, “NoSQL database” loosely specifies a class of
non-relational DBMSs
– Relax some requirements of RDBMSs to gain efficiency and
scalability for use cases in which RDBMSs are a bad fit

*RDBMS = relational database management system

732A54 / TDDE31 Big Data Analytics
Topic: Database Management Systems for Big Data Olaf Hartig 6
Scalability
●
Data scalability: system can handle
growing amounts of data
without losing performance
●
Read scalability: system can handle
increasing numbers of read operations
without losing performance
●
Write scalability: system can handle
increasing numbers of write operations
without losing performance

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 7
Vertical Scalability vs. Horizontal Scalability
●
Vertical scalability (“scale up”)
– Add resources to a server (e.g., more CPUs,
more memory, more or bigger disks)

●
Horizontal scalability (“scale out”)
– Add nodes (more computers)
to a distributed system

Image source: [Link]

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 8
Typical* Characteristics of NoSQL Systems
●
Ability to scale horizontally over many commodity servers
with high performance, availability, and fault tolerance
– achieved by giving up ACID guarantees

– and by partitioning and replication of data

●
Non-relational data model, no requirements for schemas
– data model limitations make partitioning effective

*Attention, there is a broad variety of such systems and not

all of them have these characteristics to the same degree
732A54 / TDDE31 Big Data Analytics
Topic: Database Management Systems for Big Data Olaf Hartig 9
NoSQL Data Models
Data Models
●
Key-value model
●
Document model
●
Wide-column models
●
Graph database models

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 11
Key-Value Stores: Data Model
●
Database is simply a set of key-value pairs
– keys are unique
Key 1 Value 1
– values of arbitrary data types
Key 2 Value 2
●
Values are opaque to the system
Key 3 Value 3

Key 4 Value 4

Key 5 Value 5

Key 6 Value 6

Key 7 Value 7

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 12
Example
●
Assume a relational database
consisting of a single table:
User login name website twitter
alice12 Alice [Link] NULL
bob_in_se Bob NULL @TheBob
charlie Charlie NULL NULL

●
How can we capture this data in the key-value model?

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 13
Example
●
Assume a relational database
consisting of a single table:
User login name website twitter
alice12 Alice [Link] NULL
bob_in_se Bob NULL @TheBob
charlie Charlie NULL NULL

●
How can we capture this data in the key-value model?

alice12 Alice, [Link]

bob_in_se Bob, , @TheBob

charlie Charlie

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 14
Example
Fav user favorite
●
Let's add another table: alice12 bob_in_se
alice12 charlie
User login name website twitter
alice12 Alice [Link] NULL
bob_in_se Bob NULL @TheBob
charlie Charlie NULL NULL

●
How can we capture this data in the key-value model?

alice12 Alice, [Link]

bob_in_se Bob, , @TheBob

charlie Charlie

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 15
Example
Fav user favorite
●
Let's add another table: alice12 bob_in_se
alice12 charlie
User login name website twitter
alice12 Alice [Link] NULL
bob_in_se Bob NULL @TheBob
charlie Charlie NULL NULL

●
How can we capture this data in the key-value model?

alice12 Alice, [Link] , [bob_in_se,charlie]

bob_in_se Bob, , @TheBob

charlie Charlie

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 16
Key-Value Stores: Querying
●
Only CRUD operations in terms of keys
– CRUD: create, read, update, delete
– put(key, value); get(key); delete(key)
●
No support for value-related queries
– Recall that values are opaque to the system
(i.e., no secondary index over values)
●
Accessing multiple items requires separate requests
– Beware: often no transactional capabilities

alice12 Alice, [Link] , [bob_in_se,charlie]

bob_in_se Bob, , @TheBob

charlie Charlie

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 17
Key-Value Stores: Querying
●
Only CRUD operations in terms of keys
– CRUD: create, read, update, delete
– put(key, value); get(key); delete(key)
●
No support for value-related queries
– Recall that values are opaque to the system
(i.e., no secondary index over values)
●
Accessing multiple items requires separate requests
– Beware: often no transactional capabilities
●
Advantage of these limitations: partition the data based
on keys (“horizontal partitioning”, also called “sharding”)
and distributed processing can be very efficient

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 18
Example (cont'd)
●
Assume we try to find all users for whom Bob is a favorite
●
It is possible (how?), but very inefficient
●
What can we do to make it more efficient?

alice12 Alice, [Link] , [bob_in_se,charlie]

bob_in_se Bob, , @TheBob

charlie Charlie

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 19
Example (cont'd)
●
Assume we try to find all users for whom Bob is a favorite
●
It is possible (how?), but very inefficient
●
What can we do to make it more efficient?
– Add redundancy (downsides: more space needed,
updating becomes less trivial and less efficient)

alice12 Alice, [Link] , [bob_in_se,charlie], [ ]

bob_in_se Bob, , @TheBob, [ ], [alice12]

charlie Charlie, , , [ ], [alice12]

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 20
Key-Value Stores: Use Cases
●
Whenever values need to be accessed only via keys
●
Examples:
– Storing Web session information

– User profiles and configuration

– Shopping cart data

– Caching layer that stores results of

expensive operations (e.g., complex
queries over an underlying database,
user-tailored Web pages)

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 21
Examples of Key-Value Stores
●
In-memory key-value stores
– Memcached
– Redis

●
Persistent key-value stores
– Berkeley DB
– Voldemort
– RiakDB

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 22
Data Models
●
Key-value model
●
Document model
●
Wide-column models
●
Graph database models

Image source: [Link]

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 23
 Document Stores: Data Model
●
Document: a set of fields consisting of a name and a value
– field names are unique within the document
– values are scalars (text, numeric, boolean) or lists

login : "alice12"
name : "Alice"
website : "[Link]
favorites : [ "bob_in_se", "charlie" ]

User
login name website twitter Fav
alice12 Alice [Link] NULL user favorite
bob_in_se Bob NULL @TheBob alice12 bob_in_se
charlie Charlie NULL NULL alice12 charlie

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 24
Document Stores: Data Model
●
Document: a set of fields consisting of a name and a value
– field names are unique within the document
– values are scalars (text, numeric, boolean) or lists
– in some systems, values may also be other documents

login : "alice12"
name : "Alice"
website : "[Link]
favorites : [ "bob_in_se", "charlie" ]
address : {
street : "Main St"
city : "Springfield"
}

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 25
Document Stores: Data Model
●
Document: a set of fields consisting of a name and a value
– field names are unique within the document
– values are scalars (text, numeric, boolean) or lists
– in some systems, values may also be other documents
●
Database is a set of documents (or multiple such sets)
– each document additionally associated with
a unique identifier (typically system-generated)
– schema free: different documents may have different fields

271 login : "alice12"

name : "Alice"
website : "[Link]
favorites : [ "bob_in_se", "charlie" ]

308 login : "bob_in_se"

name : "Bob"
twitter : "@TheBob"

912 login : "charlie"

name : "Charlie"

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 26
Document Stores: Data Model
●
Document: a set of fields consisting of a name and a value
– field names are unique within the document
– values are scalars (text, numeric, boolean) or lists
– in some systems, values may also be other documents
●
Database is a set of documents (or multiple such sets)
– each document additionally associated with
a unique identifier (typically system-generated)
– schema free: different documents may have different fields
– grouping of documents into separate sets
(called “domains” or “collections”) Collection: Users
271 login : "alice12"
name : "Alice"

Collection: Posts
website : "[Link]
favorites : [ "bob_in_se", "charlie" ]

334 author : "alice12"

date : "2017-01-23" 308 login : "bob_in_se"
name : "Bob"
text : "Lorem ipsum dolor sit amet ..." twitter : "@TheBob"

196 author : "bob_in_se"

Date : "2017-09-21" 912 login : "charlie"
name : "Charlie"
text : "But I must explain to you ho..."

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 27
Document Stores: Data Model
●
Document: a set of fields consisting of a name and a value
– field names are unique within the document
– values are scalars (text, numeric, boolean) or lists
– in some systems, values may also be other documents
●
Database is a set of documents (or multiple such sets)
– each document additionally associated with
a unique identifier (typically system-generated)
– schema free: different documents may have different fields
– grouping of documents into separate sets
(called “domains” or “collections”)
●
Partitioning based on collections and/or on document IDs
●
Secondary indexes over fields in the documents possible
– different indexes per domain/collection of documents

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 28
Document Stores: Querying
●
Querying in terms of conditions on document content
●
Queries expressed in terms of program code using an API
or in a system-specific query language

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 29
Document Stores: Querying
●
Querying in terms of conditions on document content
●
Queries expressed in terms of program code using an API
or in a system-specific query language
●
Examples (using MongoDB's query language):
– Find all docs in collection Users whose name field is "Alice"
[Link]( {name: "Alice"} )
– Find all docs in collection Users whose age is greater than 23
[Link]( {age: {$qt: 23}} )
– Find all docs about Users who favorite Bob
[Link]( {favorites: {$in: ["bob_in_se"]}} )
login : "alice12"
name : "Alice"
website : "[Link]
732A54 / TDDE31 Big Data Analytics favorites : [ "bob_in_se", "charlie" ]
Topic: Database Management Systems for Big Data Olaf Hartig 30
Document Stores: Querying
●
Querying in terms of conditions on document content
●
Queries expressed in terms of program code using an API
or in a system-specific query language
●
Examples (using MongoDB's query language):
– Find all docs in collection Users whose name field is "Alice"
[Link]( {name: "Alice"} )
– Find all docs in collection Users whose age is greater than 23
[Link]( {age: {$qt: 23}} )
– Find all docs about Users who favorite Bob
[Link]( {favorites: {$in: ["bob_in_se"]}} )
●
However, no cross-document queries (like joins)
– have to be implemented in the application logic

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 31
Document Stores: Use Cases
●
Whenever we have items of similar
nature but slightly different structure
●
Examples:
– Blogging platforms

– Content management systems

– Event logging
●
Fast application development

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 32
Examples of Document Stores
●
Amazon's SimpleDB

●
CouchDB

●
Couchbase

●
MongoDB

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 33
Data Models
●
Key-value model
●
Document model
●
Wide-column models
●
Graph database models

also called
column-family models
or
extensible-record models

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 34
Wide-Column Stores: Data Model (Basic)
●
Database is a set of “rows” each of which …
… has a unique key, and
… a set of key-value pairs (called “columns”)
●
Schema free: different rows may contain different columns

column 1 column 2 column 4 column 5

row key 1
value 1 value 2 value 4 value 5

column 1 column 3
row key 2
value 1' value 3

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 35
Wide-Column Stores: Data Model
●
Database is a set of “rows” each of which …
… has a unique key, and
… a set of key-value pairs (called “columns”)
●
Schema free: different rows may contain different columns
●
Like a single, very wide relation (SQL table) that is
a) extensible, b) schema-free, and c) potentially sparse

column 1 column 2 column 4 column 5

row key 1
value 1 value 2 value 4 value 5

column 1 column 3
row key 2
value 1' value 3

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 36
Wide-Column Stores: Data Model
●
Database is a set of “rows” each of which …
… has a unique key, and
… a set of key-value pairs (called “columns”)
●
Schema free: different rows may contain different columns
●
Like a single, very wide relation (SQL table) that is
a) extensible, b) schema-free, and c) potentially sparse
●
Like the document model without nesting

column 1 column 2 column 4 column 5

row key 1
value 1 value 2 value 4 value 5

column 1 column 3
row key 2
value 1' value 3

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 37
 Example (cont'd)
User Fav
login name website twitter user favorite
alice12 Alice [Link] NULL alice12 bob_in_se
bob_in_se Bob NULL @TheBob alice12 charlie
charlie Charlie NULL NULL

name website bob_in_se charlie

alice12
"Alice" "[Link] true true

name twitter
bob_in_se
"Bob" "@TheBob"

name
charlie
"Charlie"

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 38
Wide-Column Stores: Data Model (cont'd)
●
Columns may be grouped into so called “column families”
– Hence, values are addressed by
(row key, column family, column key)

basic user data favorites

name website bob_in_se charlie

alice12
"Alice" "[Link] true true

name twitter
bob_in_se
"Bob" "@TheBob"

name
charlie
"Charlie"

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 39
Wide-Column Stores: Data Model (cont'd)
●
Columns may be grouped into so called “column families”
– Hence, values are addressed by
(row key, column family, column key)
●
Data may be partitioned …
… based on row keys (horizontal partitioning),
… but also based on column families (vertical partitioning),
… or even on both

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 40
Wide-Column Stores: Data Model (cont'd)
●
Columns may be grouped into so called “column families”
– Hence, values are addressed by
(row key, column family, column key)
●
Data may be partitioned …
… based on row keys (horizontal partitioning),
… but also based on column families (vertical partitioning),
… or even on both
●
Secondary indexes can be created over arbitrary columns

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 41
Wide-Column Stores: Querying
●
Querying in terms of keys or conditions on column values
●
Queries expressed in a system-specific query language or
in terms of program code using an API
– Conceptually similar to queries in document stores
●
No joins
– Again, must be implemented in the application logic

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 42
Wide-Column Stores: Use Cases
●
Similar to use cases for document store
●
Analytics scenarios
– Web analytics
– Personalized search
– Inbox search

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 43
Examples of Wide-Column Stores
●
Basic form (no column families):
– Amazon SimpleDB

– Amazon DynamoDB

●
With column families:
– Google’s BigTable

– Hadoop HBase

– Apache Cassandra

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 44
Data Models
●
Key-value model
●
Document model
●
Wide-column models
●
Graph database models

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 45
Graph Database Systems: Data Model
●
Database is some form of a graph (nodes and edges)
– plus some extra features
●
Prominent example: Property Graphs in which any node
and any edge may additionally have a label as well as
key-value pairs (called “properties”)

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 46
Graph Database Systems: Querying
●
Graph pattern matching
●
Traversal queries
– e.g., shortest paths, navigational expressions
●
Graph algorithms
– e.g., PageRank, connected components, clustering

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 47
Graph Database Systems: Use Cases
●
Complex networks
– e.g., social, information, technological, biological
●
Concrete example use cases:
– Location-based services
– Recommendation
– Fraud detection

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 48
Examples of (Property) Graph Systems
●
Neo4j

●
TigerGraph

●
InfiniteGraph

●
JanusGraph

●
Cambridge Semantics' AnzoGraph

●
Amazon Neptune

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 49
Data Models
●
Key-value model
●
Document model
●
Wide-column models
●
Graph database models
There are also multi-model NoSQL stores
Examples:
●
OrientDB (key-value, documents, graph)

●
ArangoDB (key-value, documents, graph)

●
Cosmos DB (key-value, documents, wide-column, graph)

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 50
Typical* Characteristics of NoSQL Systems
●
Ability to scale horizontally over many commodity servers
with high performance, availability, and fault tolerance
– achieved by giving up ACID guarantees

– and by partitioning and replication of data

●
Non-relational data model, no requirements for schemas
– data model limitations make partitioning effective

*Attention, there is a broad variety of such systems and not

all of them have these characteristics to the same degree
732A54 / TDDE31 Big Data Analytics
Topic: Database Management Systems for Big Data Olaf Hartig 51
BASE rather than ACID
What is BASE?
●
Idea: by giving up ACID guarantees, one can achieve
much higher performance and scalability
●
Basically Available
– system available whenever accessed,
even if parts of it unavailable
●
Soft state
– the distributed data does not need
to be in a consistent state at all times
●
Eventually consistent
– state will become consistent
after a certain period of time
●
BASE properties suitable for applications for
which some inconsistency may be acceptable
732A54 / TDDE31 Big Data Analytics
Topic: Database Management Systems for Big Data Olaf Hartig 53
CAP Theorem none can
be here BASE systems
are here
●
Only 2 of 3 properties can RDBMSs C
be guaranteed at the same are here
time in a distributed system
A P
with data replication

●
Consistency: the same copy of a replicated data item is
visible from all nodes that have this item
– Note that this is something else than consistency in ACID
●
Availability: all requests for a data item will be answered
– Answer may be that operation cannot be completed
●
Partition Tolerance: system continues to operate even if it
gets partitioned into isolated sets of nodes

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 54
Consistency Models
●
Strong consistency: after an update completes, every
subsequent access will return the updated value
– may be achieved without consistency in the CAP theorem
●
Weak consistency: no guarantee that all subsequent
accesses will return the updated value
– eventual consistency: if no new updates are made,
eventually all accesses will
return the last updated value
– inconsistency window: the period until all replicas have
been updated in a lazy manner

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 55
Consistency Models (cont'd)
●
Let:
– N be the number of nodes that store replicas
– R be the number of nodes required for a successful read
– W be the number of nodes required for a successful write
●
Then:
– Consistency as per CAP requires W = N
– Strong consistency requires R + W > N
– Eventual consistency if R + W ≤ N
– High read performance means a great N and R = 1
– Fault tolerance/availability (and relaxed consistency) W = 1

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 56
Summary
Summary
●
NoSQL systems support non-relational data models
(key-value, document, wide-column, graph)
– schema free
– support for semi-structured and unstructured data
– limited query capabilities (no joins!)
●
NoSQL systems provide high (horizontal) scalability
with high performance, availability, and fault tolerance
– achieved by:
●
data partitioning (effective due to data model limitations)
●
data replication
●
giving up consistency requirements

732A54 / TDDE31 Big Data Analytics

Topic: Database Management Systems for Big Data Olaf Hartig 58
Cassandra - A Decentralized
Structured Storage System
Avinash Lakshman and Prashant Malik
Facebook

Presented by Ravi Theja M

 Agenda

• Outline
• Data Model
• System Architecture
• Implementation
• Experiments
 Outline

• Extension of Bigtable with aspects of Dynamo

• Motivations:
– High Availability
– High Write Throughput
– Fail Tolerance
 Data Model

• Table is a multi dimensional map indexed by key (row key).

• Columns are grouped into Column Families.
• 2 Types of Column Families
– Simple
– Super (nested Column Families)
• Each Column has
– Name
– Value
– Timestamp
 Data Model

keyspace

column family

settings column
settings
name value timestamp

* Figure taken from Eben Hewitt’s (author of Oreilly’s Cassandra book) slides.
 System Architecture
• Partitioning
How data is partitioned across nodes
• Replication
How data is duplicated across nodes
• Cluster Membership
How nodes are added, deleted to the cluster
 Partitioning

• Nodes are logically structured in Ring Topology.

• Hashed value of key associated with data partition is used
to assign it to a node in the ring.
• Hashing rounds off after certain value to support ring
structure.

• Lightly loaded nodes moves position to alleviate highly

loaded nodes.
 Replication
• Each data item is replicated at N (replication factor) nodes.

• Different Replication Policies

– Rack Unaware – replicate data at N-1 successive nodes after its
coordinator
– Rack Aware – uses ‘Zookeeper’ to choose a leader which tells nodes
the range they are replicas for
– Datacenter Aware – similar to Rack Aware but leader is chosen at
Datacenter level instead of Rack level.
 Partitioning and Replication
1 0 h(key1)
E
A N=3

h(key2) F

B
D

1/2
* Figure taken from Avinash Lakshman and Prashant Malik (authors of the paper) slides.
9
 Gossip Protocols
• Network Communication protocols inspired for real life
rumour spreading.
• Periodic, Pairwise, inter-node communication.
• Low frequency communication ensures low cost.
• Random selection of peers.
• Example – Node A wish to search for pattern in data
– Round 1 – Node A searches locally and then gossips with node B.
– Round 2 – Node A,B gossips with C and D.
– Round 3 – Nodes A,B,C and D gossips with 4 other nodes ……
• Round by round doubling makes protocol very robust.
 Gossip Protocols
• Variety of Gossip Protocols exists

– Dissemination protocol
• Event Dissemination: multicasts events via gossip. high latency might cause
network strain.
• Background data dissemination: continuous gossip about information
regarding participating nodes

– Anti Entropy protocol

• Used to repair replicated data by comparing and reconciling differences. This
type of protocol is used in Cassandra to repair data in replications.
 Cluster Management
• Uses Scuttleback (a Gossip protocol) to manage nodes.
• Uses gossip for node membership and to transmit system
control state.
• Node Fail state is given by variable ‘phi’ which tells how
likely a node might fail (suspicion level) instead of simple
binary value (up/down).
• This type of system is known as Accrual Failure Detector.
 Accrual Failure Detector
• If a node is faulty, the suspicion level monotonically
increases with time.
Φ(t) → k as t → k
Where k is a threshold variable (depends on system load)
which tells a node is dead.
• If node is correct, phi will be constant set by application.
Generally
Φ(t) = 0
 Bootstrapping and Scaling
• Two ways to add new node
– New node gets assigned a random token which gives its position in
the ring. It gossips its location to rest of the ring
– New node reads its config file to contact it initial contact points.
• New nodes are added manually by administrator via CLI or
Web interface provided by Cassandra.

• Scaling in Cassandra is designed to be easy.

• Lightly loaded nodes can move in the ring to alleviate
heavily loaded nodes.
 Local Persistence
• Relies on local file system for data persistency.
• Write operations happens in 2 steps
– Write to commit log in local disk of the node
– Update in-memory data structure.
– Why 2 steps or any preference to order or execution?
• Read operation
– Looks up in-memory ds first before looking up files on disk.
– Uses Bloom Filter (summarization of keys in file store in memory)
to avoid looking up files that do not contain the key.
 Read Operation
Client

Query Result

Cassandra Cluster

Closest replica Result Read repair if

digests differ
Replica A

Digest Query
Digest Response Digest Response

Replica B Replica C

* Figure taken from Avinash Lakshman and Prashant Malik (authors of the paper) slides.
 Facebook Inbox Search
• Cassandra developed to address this problem.
• 50+TB of user messages data in 150 node cluster on which
Cassandra is tested.
• Search user index of all messages in 2 ways.
– Term search : search by a key word
– Interactions search : search by a user id

Latency Stat Search Interactions Term Search

Min 7.69 ms 7.78 ms
Median 15.69 ms 18.27 ms
Max 26.13 ms 44.41 ms
 Comparison with MySQL
• MySQL > 50 GB Data
Writes Average : ~300 ms
Reads Average : ~350 ms

• Cassandra > 50 GB Data

Writes Average : 0.12 ms
Reads Average : 15 ms

• Stats provided by Authors using facebook data.

 Comparison using YCSB
• Following results taken from ‘Benchmarking Cloud Serving
Systems with YCSB’ by Brain F Cooper et all.
• YCSB is Yahoo Cloud Server Benchmarking framework.
• Comparison between Cassandra, HBase, PNUTS, and
MySQL.

• Cassandra and Hbase have higher read latencies on a read

heavy workload than PNUTS and MySQL, and lower update
latencies on a write heavy workload.
• PNUTS and Cassandra scaled well as the number of servers
and workload increased proportionally.
 Comparison using YCSB
• Cassandra, HBase and PNUTS were able to grow elastically
while the workload was executing.
• PNUTS and Cassandra scaled well as the number of
• servers and workload increased proportionally. HBase’s
• performance was more erratic as the system scaled.
Thank You