Morten Siebuhr · NoSQL

• Computer Scientist
• Webdeveloper
• Interest in distributed systems

• Databases
• ACID vs. BASE
• NoSQL anatomy
• Wet Toes
• Fin!

A structured set of data held in a computer, esp. one that is accessible in various ways.

• »Industry Standard«
• ACID (Atomicity, Consistency, Isolation and Durability)
• Been around since ≈1970
• …

• Language within a language
• Constantly on ACID
• Difficult to model some data-structures
• Scaling
• …

• Lower per-CPU cost
• Higher total bandwidth
• Cheaper to achieve redundancy in software

• Forfeit Consistency and Isolation…
• …for availability,
• grateful degradation
• and performance

• Basically Available,
• Soft-state
• and Eventual consistency

All clients see the same data at the same time

Every request recieves a response about whether the operation was successfull or failed

Works despite network partitions
·
Continues to operate despite arbitratry message loss

(Then work very very hard to fake the last!)

• All clients see the same data and all clients recieve responses.
• Traits: 2-phase commit, cache validation protocols
• But what to do with network partitions?
• Typical fix: add hot/cold-failover, replication
• (Also: screwing the System Administrators)

• Single-site/Cluster databases,
• LDAP
• RDBMS's

• All clients see the same data, despite partitioned network.
• Traits: Drop minority partitions when in trouble
• What to do about »unknown« data?
• Deals with it by dropping availability.
• Fix it by replicating data agressively
• (Downtime ≈ screwing users)

• Distributed databases
• Locking and majority protocols
• Google BigTable / HBase
• Redis

• All clients and read and write despite network partitions.
• Optimistic, Conflict resolution, and leases/expiration
• Fix it by replication and Verification
• »Eventual Consistency«
• Screw the Developers

• Caches
• DNS
• Riak
• Cassandra
• CouchDB

• Key/Value
• Document
• Column / Tabular
• (Graph)

SELECT
[ALL | DISTINCT | DISTINCTROW ]
  [HIGH_PRIORITY] [STRAIGHT_JOIN] [SQL_SMALL_RESULT] [SQL_BIG_RESULT]
  [SQL_BUFFER_RESULT] [SQL_CACHE | SQL_NO_CACHE] [SQL_CALC_FOUND_ROWS]
select_expr [, select_expr …]
[FROM table_references
[WHERE where_condition]
[GROUP BY {col_name | expr | position}
  [ASC | DESC], … [WITH ROLLUP]]
[HAVING where_condition]
[ORDER BY {col_name | expr | position}
  [ASC | DESC], …]
[LIMIT {[offset,] row_count | row_count OFFSET offset}]
[PROCEDURE procedure_name(argument_list)]
[INTO OUTFILE 'file_name' export_options
  | INTO DUMPFILE 'file_name'
  | INTO var_name [, var_name]]
    [FOR UPDATE | LOCK IN SHARE MODE]]

• put(document, [key]) → key
• get(key) → document
• delete(key, …)
• Support variations of:
  create_index(document_part) · query_index(…)
• Sometimes:
  query(some_query_language)

• Available + Partition-tolerant → »Eventual Consistency«
• Replicates entire databases … everywhere
• Map/Reduce for indices
• Vector clocks

• Network partitioning as a feature
• (Think mobile clients…)

• map(key1, value1) → [(key2, value2), …]
• … Shuffle output …
• reduce(key2, [value2]) → [value3, …]

def map(document_name, text):
	for word in text.split():
		yield (word, 1)

… Shuffle output …

def reduce(word, count):
	yield (word, sum(count))

PUT /dbname/_design/viewname/
Then query with:
GET /dbname/_design/viewname/_view/all \
	?and_some_modifiers

• Key → Value
• put(key, value)
• get(key)
• delete(key)
• Sometimes:
• get_all()

• Eventual consistency
• Links
• Secondary Indices
• Map/Reduce for bulk operations

• Split it, typically ~64 parts
• Then save each part on multiple machines

• Three parameters: w/dw and r.
• One given: servers.
• w + r > servers

• Given 5 servers…
• w=3 and r=3 → ~ consistent system
• w=1 and r=5 → fast write, slow reads
• w=5 and r=1 → slow write, fast reads
• w=1 and r=1 → cache

• (Table, Row, Prefix:Column) → Value
• create_table(table, column_prefixes)
• put(table, row, prefix:column, value)
• get(table, [row], [prefix:[column]])
• scan(table, row_start, row_end, [prefix:[column]])
• delete(table, …)

• Column-oriented
• Built on Hadoop
• Copy of Google BigTable
• Key-scans
• Map/Reduce

• Column-family → distict set of files
• Keys held in-memory, if possible or explicitly configured
• Many machines holds part of the index → scan in parallel
• Optional bloom filters

• Only get »raw« data in and out.
• Have to massage data in the application.
• Inflexible query-system.
• Fix by inserting same data under multiple keys/documents and pretend those are indices.

• Latitude - longitude
• 55.681722, 12.530602
• 5152..6583…

• Problem:
  Multiple front-end machines will write to the same key
• lock → read → update → write → unlock + read
• Exploit that read < write < lock
• Each machine write separate keys → merge after reading
• read → update → write + multiple read
• Then reader can write back one key, if needed

• Look at your data
• Look at your use-patterns
• What programming language are you using?
• Examine their »DNA«
• They're evolving
• Try them out! … with real data!
• »The Cloud«

Morten Siebuhr

• sbhr.dk
• twitter.com/msiebuhr
• sbhr@sbhr.dk

• Specialized distributed configuration & coordination system
• Filesystem-like interface
• Persistent client connections
• Read-oriented

• Get/Put
• ACLs
• Ephemeral files
• Watches