Database Applications (15-
415)
Part I- NoSQL Databases
Types of Data
Data can be broadly classified into four types:
1. Structured Data:
Have a predefined model, which organizes data into a
form that is relatively easy to store, process, retrieve
and manage
E.g., relational data
2. Unstructured Data:
Opposite of structured data
E.g., Flat binary files containing text, video or audio
Note: data is not completely devoid of a structure (e.g.,
an audio file may still have an encoding structure and
some metadata associated with it)
Types of Data
Data can be broadly classified into four types:
3. Dynamic Data:
Data that changes relatively frequently
E.g., office documents and transactional entries in a
financial database
4. Static Data:
Opposite of dynamic data
E.g., Medical imaging data from MRI or CT scans
Why Classifying Data?
Segmenting data into one of the following 4 quadrants can help in
designing and developing a pertaining storage solution
Dynamic Static
Structured Unstructured
Media Production, eCAD, Media Archive, Broadcast,
mCAD, Office Docs Medical Imaging
Transaction Systems, ERP,
BI, Data Warehousing
CRM
Relational databases are usually used for structured data
File systems or NoSQL databases can be used for (static),
unstructured data (more on these later)
Outline
Types of Data
Scaling Databases & the 2PC Protocol
The CAP Theorem and the BASE
Properties
NoSQL Databases
Scaling Traditional Databases
Traditional RDBMSs can be either scaled:
Vertically (or Up)
Can be achieved by hardware upgrades (e.g., faster CPU,
more memory, or larger disk)
Limited by the amount of CPU, RAM and disk that can be
configured on a single machine
Horizontally (or Out)
Can be achieved by adding more machines
Requires database sharding and probably replication
Limited by the Read-to-Write ratio and communication
overhead
Why Sharding Data?
Data is typically sharded (or striped) to allow for
concurrent/parallel accesses
Input data: A large file
Machine 1 Machine 2 Machine 3
Chunk1 of input data Chunk3 of input data Chunk5 of input data
Chunk2 of input data Chunk4 of input data Chunk5 of input data
E.g., Chunks 1, 3 and 5 can be accessed in parallel
Amdahl’s Law
How much faster will a parallel program run?
Suppose that the sequential execution of a program takes T1 time
units and the parallel execution on p processors/machines takes
Tp time units
Suppose that out of the entire execution of the program, s
fraction of it is not parallelizable while 1-s fraction is parallelizable
Then the speedup (Amdahl’s formula):
8
Amdahl’s Law: An Example
Suppose that:
80% of your program can be parallelized
4 machines are used to run your parallel version of
the program
The speedup you can get according to Amdahl’s law is:
Although you use 4 processors you cannot get a speedup more
than 2.5 times!
9
Real Vs. Actual Cases
Amdahl’s argument is too simplified
In reality, communication overhead and potential workload
imbalance exist upon running parallel programs
20 80 20 80
Serial Serial
Parallel 20 20 Parallel 20 20
Process 1 Process 1
Process 2 Process 2
Cannot be parallelized
Process 3 Process 3
Cannot be parallelized Can be parallelized
Process 4 Process 4 Communication overhead
Can be parallelized
Load Unbalance
1. Parallel Speed-up: An Ideal Case 2. Parallel Speed-up: An Actual Case
Some Guidelines
Here are some guidelines to effectively benefit
from parallelization:
1. Maximize the fraction of your program that can
be parallelized
2. Balance the workload of parallel processes
3. Minimize the time spent for communication
11
Why Replicating Data?
Replicating data across servers helps in:
Avoiding performance bottlenecks
Avoiding single point of failures
And, hence, enhancing scalability and availability
Why Replicating Data?
Replicating data across servers helps in:
Avoiding performance bottlenecks
Avoiding single point of failures
And, hence, enhancing scalability and availability
Main Server
Replicated Servers
But, Consistency Becomes a Challenge
An example:
In an e-commerce application, the bank database has
been replicated across two servers
Maintaining consistency of replicated data is a
challenge
Event 1 = Add $1000 Event 2 = Add interest of 5%
1 2
Bal=2000
Bal=2100
Bal=1000 4 3 Bal=1000
Bal=1050
Bal=2050
Replicated Database
The Two-Phase Commit Protocol
The two-phase commit protocol (2PC) can be used to
ensure atomicity and consistency
Phase I: Voting
VOTE_REQUEST
VOTE_COMMIT
Participant 1 Database Server 1
VOTE_REQUEST
VOTE_COMMIT
Coordinator Participant 2 Database Server 2
VOTE_COMMIT
VOTE_REQUEST
Participant 3 Database Server 3
The Two-Phase Commit Protocol
The two-phase commit protocol (2PC) can be used to
ensure atomicity and consistency
Phase II: Commit
GLOBAL_COMMIT LOCAL_COMMIT
Participant 1 Database Server 1
GLOBAL_COMMIT LOCAL_COMMIT
Coordinator Participant 2 Database Server 2
GLOBAL_COMMIT LOCAL_COMMIT
“Strict” consistency, which
limits scalability! Participant 3 Database Server 3
Outline
Types of Data
Scaling Databases & the 2PC Protocol
The CAP Theorem and the BASE
Properties
NoSQL Databases
The CAP Theorem
The limitations of distributed databases can be described
in the so called the CAP theorem
Consistency: every node always sees the same data at any
given instance (i.e., strict consistency)
Availability: the system continues to operate, even if nodes
in a cluster crash, or some hardware or software parts are
down due to upgrades
Partition Tolerance: the system continues to operate in the
presence of network partitions
CAP theorem: any distributed database with shared data, can have at most two
of the three desirable properties, C, A or P
The CAP Theorem (Cont’d)
Let us assume two nodes on opposite sides of a
network partition:
Availability + Partition Tolerance forfeit Consistency
Consistency + Partition Tolerance entails that one side of
the partition must act as if it is unavailable, thus
forfeiting Availability
Consistency + Availability is only possible if there is no
Large-Scale Databases
When companies such as Google and Amazon were
designing large-scale databases, 24/7 Availability was a key
A few minutes of downtime means lost revenue
When horizontally scaling databases to 1000s of machines,
the likelihood of a node or a network failure
increases tremendously
Therefore, in order to have strong guarantees on
Availability and Partition Tolerance, they had to sacrifice
“strict” Consistency (implied by the CAP theorem)
Trading-Off Consistency
Maintaining consistency should balance between the
strictness of consistency versus availability/scalability
Good-enough consistency depends on your application
Trading-Off Consistency
Maintaining consistency should balance between the
strictness of consistency versus availability/scalability
Good-enough consistency depends on your application
Loose Consistency Strict Consistency
Easier to implement, Generally hard to implement,
and is efficient and is inefficient
The BASE Properties
The CAP theorem proves that it is impossible to guarantee
strict Consistency and Availability while being able to
tolerate network partitions
This resulted in databases with relaxed ACID guarantees
In particular, such databases apply the BASE properties:
Basically Available: the system guarantees Availability
Soft-State: the state of the system may change over time
Eventual Consistency: the system will eventually
become consistent
Eventual Consistency
A database is termed as Eventually Consistent if:
All replicas will gradually become consistent in the
absence of updates
Eventual Consistency
A database is termed as Eventually Consistent if:
All replicas will gradually become consistent in the
absence of updates
Webpage-A
Webpage-A Webpage-A
Event: Update Webpage-
Webpage-A A
Webpage-A
Webpage-A
Eventual Consistency:
A Main Challenge
But, what if the client accesses the data from
different replicas?
Webpage-A
Webpage-A Webpage-A
Event: Update Webpage-
Webpage-A A
Webpage-A
Webpage-A
Protocols like Read Your Own Writes (RYOW) can be applied!
Outline
Types of Data
Scaling Databases & the 2PC Protocol
The CAP Theorem and the BASE
Properties
NoSQL Databases
NoSQL Databases
To this end, a new class of databases emerged, which
mainly follow the BASE properties
These were dubbed as NoSQL databases
E.g., Amazon’s Dynamo and Google’s Bigtable
Main characteristics of NoSQL databases include:
No strict schema requirements
No strict adherence to ACID properties
Consistency is traded in favor of Availability
Types of NoSQL Databases
Here is a limited taxonomy of NoSQL databases:
NoSQL Databases
Document Graph Key-Value Columnar
Stores Databases Stores Databases
Document Stores
Documents are stored in some standard format or
encoding (e.g., XML, JSON, PDF or Office Documents)
These are typically referred to as Binary Large Objects
(BLOBs)
Documents can be indexed
This allows document stores to outperform traditional
file systems
E.g., MongoDB and CouchDB (both can be queried
using MapReduce)
Types of NoSQL Databases
Here is a limited taxonomy of NoSQL databases:
NoSQL Databases
Document Graph Key-Value Columnar
Stores Databases Stores Databases
Graph Databases
Data are represented as vertices and edges
0
Id:10 : knows /03 Id: 2
l 0
Labe : 2001/1 Name: Bob
e
S in c Age: 22
1
Id:10 : knows /03 r
be 14
e l 1 0
Lab : 2001/ em 2 /
Id: 1 c e m 0
S in 1 0 : i s_ 1 1 /
5
er
s
Name: Alice Id:1 d : e l 0 b
0 I b : 2
Age: 18 La b e 3 La nce 0 4 Mem
l: M Si :1 :
e mb Id bel
ers La
Id:1 Id: 3
Lab 02 Name: Chess
e
Sin c l: is _m Type: Group
e: 2 e
00 5 mb e r
/ 07
/ 01
Graph databases are powerful for graph-like queries (e.g., find
the shortest path between two elements)
Types of NoSQL Databases
Here is a limited taxonomy of NoSQL databases:
NoSQL Databases
Document Graph Key-Value Columnar
Stores Databases Stores Databases
Key-Value Stores
Keys are mapped to (possibly) more complex value
(e.g., lists)
Keys can be stored in a hash table and can be
distributed easily
Such stores typically support regular CRUD (create,
read, update, and delete) operations
That is, no joins and aggregate functions
E.g., Amazon DynamoDB and Apache Cassandra
Types of NoSQL Databases
Here is a limited taxonomy of NoSQL databases:
NoSQL Databases
Document Graph Key-Value Columnar
Stores Databases Stores Databases
Columnar Databases
Columnar databases are a hybrid of RDBMSs and Key-
Value stores
Values are stored in groups of zero or more columns, but in
Column-Order (as opposed to Row-Order)
Record 1 Column A Column A = Group A
Alice 3 25 Bob Alice Bob Carol Alice Bob Carol
4 19 Carol 0 3 4 0 25 3 25 4 19
45 19 45 0 45
Column Family {B, C}
Row-Order Columnar (or Column-Order) Columnar with Locality Groups
Values are queried by matching keys
E.g., HBase and Vertica
Summary
Data can be classified into 4 types, structured,
unstructured, dynamic and static
Different data types usually entail different database
designs
Databases can be scaled up or out
The 2PC protocol can be used to ensure strict consistency
Strict consistency limits scalability
Summary (Cont’d)
The CAP theorem states that any distributed
database with shared data can have at most two
of the three desirable properties:
Consistency
Availability
Partition Tolerance
The CAP theorem lead to various designs of
databases with relaxed ACID guarantees
Summary (Cont’d)
NoSQL (or Not-Only-SQL) databases follow the BASE
properties:
Basically Available
Soft-State
Eventual Consistency
NoSQL databases have different types:
Document Stores
Graph Databases
Key-Value Stores
Columnar Databases