I can't pass an extremely competitive
test to become a surgeon. But you give
me any operation on a heart. I can
perhaps do much better than most
people. I am like an artist. Don't expect
me to compete in an exam. Give me the
job and I will show you how good I am.
[Link]
NoSQL DB
Venkatesh Vinayakarao
venkateshv@[Link]
[Link]
Chennai Mathematical Institute
The cost of managing traditional databases is high. Mistakes made during routine
maintenance are responsible for 80 percent of application downtime. – Dev Ittycheria,
MongoDB.
Venkatesh Vinayakarao (Vv)
A Relation as a Data Model
• Let the set, id = {1,2,3} id name
• Let the set, names = {vv, sd} 1 sd
• What is id x names? 1 vv
2 sd
• We have a relation if we assign a
sequential id to each name. 2 vv
3 sd
id name
3 vv
1 sd
2 vv
… and thus we had the relational database.
311
An Entity-Relationship Design
DB Designs:
• Can get too complex!
• May become too
hard to maintain!!
Source: [Link]
312
Key Challenges of Relational DB
• Schema needs to be defined.
• Maintenance becomes harder over time.
• Impedance mismatch problem.
• Does not scale out by design.
• ACID Transactions – Consistency Vs. Availability
Trade-off.
313
Impedance Mismatch
314
DB Design
Personal Info
How will you design the
Academic Profile DB for this content?
Employment
315
Impedance Mismatch Problem
Multiple Tables
One unit
Intermediate Solution: Object Relational Mapping (ORM)
316
Object Relational Mapping
Multiple Tables
Personal Info
Object
Person Academic Profile
Object
(Instance of a
A Single Person’s Data Person Class)
Employment
Hibernate Framework, Java Data Objects, … and
many other ORM frameworks emerged.
317
Scaling Out
318
Table Joins Using MapReduce
• How would you do it?
Map-side Reduce-side
Join Join
Join is performed by Join is performed by
the mapper. the reducer.
Table joins are expensive. So, new solutions
emerged. Google BigTable, Amazon Dynamo…
319
Join Pattern
See [Link] 320
A New Movement was Born
• We needed a
• Not only relational
• Cluster friendly
• Schemaless
way to store and retrieve data.
• Johan Oskarsson proposed a meetup. He needed a
twitter hashtag. He used, “nosql”.
321
Transactions,
Consistency and CAP
Theorem
322
Transaction
1. read(A)
2. A := A – 50
3. write(A) transfer $50 from
4. read(B) account A to account B
5. B := B + 50
6. write(B)
A transaction is a unit of program execution
that accesses and possibly updates various
data items.
Do You See Any Issues Here?
DB
A transaction that reads
and writes to disk.
324
Issues
• Two main issues to deal with:
Failure (hardware failure,
system crash, software concurrent execution
defect…)
Atomicity
• What happens if step 3 is executed
but not step 6?
• Failure could be due to software or
hardware
• The system should ensure that
updates of a partially executed
transaction are not reflected in the
database.
326
Consistency Consistent State
• Respect
• Explicitly specified
integrity constraints
• Implicit integrity
constraints Temporarily
Inconsistent
• e.g., sum of balances of all
accounts stays constant State
Consistent State
327
Isolation
• T2 sees an inconsistent database if T1 and T2 are
concurrent.
T1 T2
1. read(A)
2. A := A – 50
3. write(A)
read(A), read(B), print(A+B)
4. read(B)
5. B := B + 50
6. write(B)
• Isolation can be ensured trivially by running transactions
serially
• That is, one after the other.
Durability
• After step 6, the updates to the
database by the transaction
must
• persist even if there are software
or hardware failures.
329
ACID Properties
• Atomicity. Either all operations of the transaction are
properly reflected in the database or none are.
• Consistency. Execution of a transaction in isolation
preserves the consistency of the database.
• Isolation. Although multiple transactions may execute
concurrently, each transaction must be unaware of other
concurrently executing transactions. Intermediate
transaction results must be hidden from other concurrently
executed transactions.
• That is, for every pair of transactions Ti and Tj, it appears to Ti that
either Tj, finished execution before Ti started, or Tj started execution
after Ti finished.
• Durability. After a transaction completes successfully, the
changes it has made to the database persist, even if there
are system failures.
But, as a facebook user, I had a different
observation…
331
Eventual Consistency
• I updated my facebook
status and asked my
friend to check it out.
• But she found nothing
there!!!
• Asked her to wait a bit
and check again.
• Now, she finds it!
332
Eventual Consistency
• Facebook is eventually consistent.
• Why not use a strongly consistent model?
• Stores Petabytes of data.
• We have Availability vs. Consistency tradeoff.
CAP Theorem
• Concerns while designing distributed systems:
• Consistency –all clients of a data store get responses to
requests that ‘make sense’. For example, if Client A
writes 1 and later 2 to location X, Client B cannot read 2
followed by 1.
• Availability – all operations on a data store eventually
return successfully. We say that a data store is ‘available’
for, e.g. write operations.
• Partition tolerance – if the network stops delivering
messages between two sets of servers, will the system
continue to work correctly?
334
The CAP Message
If you:
• cannot limit the number of faults,
• requests can be directed to any
server, and
• insist on serving every request you
receive,
Then:
• you cannot possibly be consistent.
335
The Transaction Properties
Atomicity Basically
Available
Consistency
Soft-State
Isolation
Eventually
Durability Consistent
336
337
NoSQL DB Types
338
Types of NoSQL DB
• Key-Value Stores
• Simplest. Every item is a key-value pair.
• Examples: Riak, Voldemort, and Redis
• Document DB
• Complex data structures are represented as documents.
• Examples: MongoDB
• Wide-Column Stores
• Data stored as columns.
• Examples: Cassandra and Hbase
• Graph DB
• Examples: Neo4J and HyperGraphDB
339
Redis DB – Key Value Store
redis> GET nonexisting
(nil)
redis> SET mykey "Hello"
"OK"
redis> GET mykey
"Hello"
redis>
Read [Link]
340
Voldemort DB
341
mongoDB – Document Database
• mongoDB = “Humongous DB”
• Open-source
• Document-based data model
• “High performance, high availability”
• Automatic scaling
• C-P on CAP
342
MongoDB vs. RDBMS
• Collection vs. table
• Document vs. row
• Field vs. column
• Schema-less
343
Document Data
Model
A record in MongoDB
is a document
• Documents are a
natural way to
represent data.
• Here is a “Person”
object represented as a
JSON document.
• MongoDB stores this as
a BSON document
(Binary representation
of JSON).
[Link]( { x: 1 } )
[Link]({ “name" : “al" } );
Commands
Read [Link]
344
Operations on MongoDB Data
345
Columnar Storage
Read [Link]
346
Columnar Storage
Same datatype in a block helps in devising efficient compression
schemes. Therefore, improve storage efficiency.
Assumption: “OLTP transactions typically involve most or all of the
columns in a row for a small number of records, data warehouse queries
commonly read only a few columns for a very large number of rows”
347
Cassandra - Wide-Column Store
• A column is the basic data structure of Cassandra.
• A Column has three values, namely key or column
name, value, and a time stamp.
• A super column is a special column. stores a map of
sub-columns.
348
Column-Family DB
• Cassandra does not force individual rows to have all
the columns.
• An example of a Cassandra column family:
349
Cassandra Keyspace
• Keyspace is a container for a list of one or
more column families.
• A column family, in turn, is a container of a
collection of rows.
• Each row contains ordered columns.
350
cqlsh
• Cassandra Query Language Shell
[hadoop@linux bin]$ cqlsh
Connected to … Cluster at ….
cqlsh> select * from emp;
• Note: Cassandra does not join!
• If you need to lookup several tables, create another
column-family.
351
Graph DB
• Facebook, LinkedIn, Google …have connected data.
• It is natural to store and retrieve data as graphs.
Twitter users represented in a graph database model.
Read [Link]
352
Summary
Impedance
Mismatch
Schema-based
Relational Model -
maintenance CAP Theorem
problems Scale-up
Challenges
Types of NoSQL datastores
redis> GET nonexisting
Columnar DB
Key-Valuecv
Doc-based
Graph DB
(nil)
redis> SET mykey "Hello"
"OK"
redis> GET mykey
"Hello"
redis>
353
Thank You
354