The NoSQL Ecosystem Flashcards
NoSQL: definition, according to the community
Not Only a SQL interface, referring to providing an alternative rather than a wholesale replacement for SQL
SQL’s expressiveness makes it challenging to ___
reason about the cost of each query, and thus the cost of a workload
Application developers may find using relational data models to be challenging because ___
it may not be perfect for modeling every kind of data (i.e. lists, queues, sets, etc)
If relational data grows past the capacity of one server, then ___
the tables in the database will have to be partitioned across computers, leading to denormalization
Complex query logic is typically left to the application, resulting in ___
a data store with more predictable query performance because of lack of variability in queries
Two characteristics of Google’s BigTable
hierarchical range-based partitioning scheme
strict consistency
Two characteristics of Amazon’s Dynamo
Maps keys to application-specific blobs of data
Loose consistency makes the partitioning model resilient to failure
Considerations regarding NoSQL systems (SPACTSDD)
Scalability Partitioning Analytical workloads Consistency Transactional semantics Single-server performance Data and query model Durability
The simplest form of a NoSQL store is a ___
key-value store
key-value store
each key is mapped to a value containing arbitrary data
store popularized by Redis
key-data structure store
key-data structure store
assigns each value a type (i.e. integer, string, list, set, sorted set, etc)
store common to CouchDB, MongoDB, Riak
key-document store
key-document store
map a key to some document that contains structured information in a JSON or JSON-like format
key-document stores grant a lot of freedom in document modeling, however ___
application-based query logic can become exceedingly complex
store common to HBase, Cassandra
BigTable column family store
column family store
- complex key identifies a row containing data stored in one or more Column Families
- each row can contain multiple columns with a CF
- values within each column are timestamped
store common to HyperGraphDB, Neo4J
graph store
exception to key-only lookup: MongoDB
allows indexing of data based on any number of properties and has a relatively high-level language for specifying which data to retrieve
exception to key-only lookup: BigTable-based systems
support scanners to iterate over a column family and select particular items by a filter on a column
exception to key-only lookup: CouchDB
allows creation of different views of the data and running MapReduce tasks across the table to facilitate more complex lookups and updates
ACID
Atomic
Consistency
Isolation
Durability
Most NoSQL systems choose performance over ___
full ACID guarantees
Redis is an exception to NoSQL’s no-transaction trend, in that ___
it provides a MULTI command to combine multiple operations atomically and a WATCH command to allow isolation
benefits of schema-free storage
supports less structured data requirements and requires less structured data requirements
after a few iterations of a project relying on sloppy-schema NoSQL systems, ___
data and schema versioning is usually present in application-level code
single-server durability
ensures that any data modification will survive a server restart or power loss
the OS may not immediately write data to an on-disk file, instead ___
buffering the write to group several writes together in a single operation
typical hard drives can perform ___ random accesses (seeks) per second
100 - 200
typical hard drives are limited to ___ of sequential writes
30 - 100 MB/s
ensuring efficient single-server durability means ___
limiting the number of random writes the system incurs and increasing the number of sequential writes per hard drive
Ideally, one wants to minimize ___ and maximize ___, all while ___
the number of writes between fsync calls
the number of those writes that are sequential
never telling the user their data has written until the write has been fsynced
Techniques for improving performance of single-server durability guarantees
Control fsync frequency
Increase sequential writes by logging
Increase throughput by grouping writes
Memcached offers ___ in exchange for ___
no on-disk durability
extremely fast in-memory operations
Redis offers several options for ___
when to call fsync
To reduce random writes, some systems ___
append update operations to a sequentially written file (a log)
log-structured merge tree / log-structured hash table
combining logs and lookup data structures into one
Techniques such as log-structure merge trees / hash tables and modified B+ trees ___
result in improved write throughput, but require a periodic log compaction
group commit
grouping multiple concurrent updates within a short window into a single fsync call
benefit of group commit
increase in throughput, as multiple log appends can happen in a single fsync
drawback of group commit
higher latency per update, as users must wait on several concurrent updates for acknowledgement of their own update
Multi-server durability varies between systems as either ___ or ___
traditional primary-replica structure
replication where multiple servers store copies of the data
scaling up
adding more RAM and disks to handle load on one machine
scaling out
replicate data and spread requests across multiple machines
the ideal horizontal scalability goal is
linear scalability
linear scalability
doubling the number of machines in your storage system doubles the query capacity of the system
sharding
the act of splitting your read and write workloads across multiple machines to scale out your storage system
sharding your data means that no one machine ___ but also is unable to ____
has to handle the write workload on the entire dataset
answer queries about the entire dataset
sharding adds ___
system complexity
two ways to scale without sharding
read replicas
caching
read replica structure
make copies of the data on multiple machines, while write requests go to a primary node
Generally, the less stringent the demands for freshness of content, the more you can ___
use read replicas to improve read-only query performance
___ and ___ allow you to scale up your read-heavy workloads
read replicas
caching
To add memory to Memcached’s cache pool:
just add another Memcached host
sharding through coordinators: Lounge and BigCouch
a coordinator distributes requests to individual CouchDB instances based on the key of the requested doc
sharding through coordinators: Gizzard
takes standalone data stores and arranges them in trees of any depth to partition keys by key range
NoSQL systems built around Dynamo’s consistent hashing technique
Voldemort
Riak
Cassandra
consistent hashing
a kind of hashing such that when a hash table is resized, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots
range partitioning differs from consistent hashing in that ___
two keys that are next to each other in the key’s sort order are likely to appear in the same partition
range partitioning allows active management of load by ___
having a load manager that can reduce the size of a range on an overloaded server
tablets in BigTable
stores a range of row keys and values within a column family, maintaining all necessary logs and data structures to answer queries
as BigTable’s tablets change in size, ___
two small tablets may merge or a big tablet splits in two
a primary server in BigTable manages ___
tablet size, load, and availability
to recognize and handle machine failures, the BigTable paper describe the use of Chubby, which is ___
a distributed locking system for managing server membership and liveness
ZooKeeper is used in several Hadoop-based projects to ___
manage secondary leader servers and tablet server reassignment
BigTable employs a hierarchical approach to range-partitioning by ___
maintaining tablet assignment in a metadata table, which is also sharded into tablets
HBase uses BigTable’s hierarchical approach to range-partitioning by ___
using HDFS to handle data storage, replication, and consistency, leaving the rest to servers
MongoDB handles range-partitioning by ___
using config nodes to specify key ranges, staying in sync with a two-phase commit protocol
Cassandra allows fast range scans over data by ___
preserving order in its partitioning, mapping data to the server directly managing its key range
Gizzard’s routing servers ___
form routing hierarchies of any depth, assigning ranges of keys to servers below them in the hierarchy
range partitioning is the obvious choice when ___
one will be frequently be performing range scans over the keys of the data, avoiding random node jumps over the network
range partitioning requires the up-front cost of ___
maintaining routing and configuration nodes
when executed well, range partitioning data can be load-balanced ___
in small chunks which can be re-assigned in high-load situations
In practice, maintaining replicas are hard and the following will happen:
crash and get out of sync
crash and never come back
networks will partition two sets of replicas
messages between machines will get delayed or lost
two major approaches to data consistency in NoSQL ecosystem
strong consistency
eventual consistency
systems that promote strong consistency ___
ensure that the replicas of a data item will always be able to come to consensus on the value of a key
the minimum R, W, and N choices for ensuring strong consistency while allowing temporary replica disagreements is
R + W = N + 1
in HDFS, a write cannot succeed until ___, while a read ___
it has been replicated to all N servers (W=N)
will be satisfied by a single replica (R=1)
Dynamo-based systems use a type of versioning called
vector clocks
Voldemort handles conflicts by ___
returning multiple copies of the key to the requesting client application
Cassandra resolved conflicts by ___
using the most recently timestamped version of the data
Voldemort’s and Cassandra’s conflict resolution are both present in ___
Riak
CouchDB provides a hybrid of Voldemort’s and Cassandra’s conflict resolution:
it identifies a conflict and allows users to query for conflicted keys for manual repair, but deterministically picks a version to return to users until conflicts are repaired
read repair is handled in Dynamo-based systems by ___
repairing out-of-sync replicas of the data in the background while returning the non-conflicting data to the requestor
hinted handoff
assigning a node to temporarily take over an unavailable node’s write workload, forwarding all those writes when the node is available again
Cassandra and Riak synchronize from one another using ___
Merkle trees
gossip
periodically (~1s) a node will communicate with a random node to exchange knowledge on other nodes’ health
