NoSQL Databases
What are NoSQL databases?
No to SQL?
No. The goal is not to replace SQL databases. NoSQL databases are designed and optimized for different types of applications.
Not only SQL (More than SQL)?
No. SQL databases also offer capabilities beyond tables and relational algebra, such as full-text search or storing structured data (e.g. JSON).
Without SQL?
No. Not every non-SQL database is called NoSQL. For example object-oriented databases (OODB) and systems for storing XML data.
What are SQL databases?
(SQL: Structured Query Language)
A brief history
How did we get SQL databases in the first place?
The 1950s
In the beginning, (raw) data was stored directly in files. The data format had to take the storage medium into account: punched cards, magnetic tapes, disks. The physical layout of data was optimized for efficient writing and reading; records often had a fixed structure and length.
1956 IBM 350 Disk Storage Unit: 3.75 MB
The 1960s
Greater disk capacity and faster writing and reading made it possible to store variable-length records, more complex structures, and indexes. Database systems emerged that offered an abstract view of data and made it possible to search, sort and query data.
The 1970s
Edgar F. Codd🌐 proposed the relational model🌐 of databases: data is represented using relations, usually in the form of tables. Data normalization removes redundancy. Queries are expressed using relational operations: joining (JOIN) and selection (WHERE).
The 1980s
The relational model became established in practice. The SQL language🌐 emerged to standardize work with data (definition, manipulation, and queries).
More: RDBS.
The emergence of NoSQL databases
1998
The term NoSQL was first used (coined) by Carlo Strozzi for his relational database.
2009 →
The term NoSQL began to be used to describe a range of non-relational, distributed databases. (Strozzi: NoREL would be a more appropriate term.)
Its adoption was due to the growth of the web, cloud computing, social networks, mobile applications, and IoT →
large amounts of unstructured, semi-structured, and graph data
no schema, or a frequently changing schema
data is inserted and rarely changed (WORM: write once/read many)
the need for greater scalability in database systems
the need for distributed data processing
Traditional relational databases are not well suited for these tasks.
→ Big Data:
How big is it? The five Vs of big data:
Volume: massive volumes of (collected or generated) data (TB, PB): enterprise data, stock market records, sensor data, logs, video, audio, text …
Velocity: data arrives and/or is processed at high speed, often as continuous streams → time windows
Variety: data is diverse
Veracity (NOT): data has uncertain reliability (it may be inaccurate or contain errors and noise) ⇒
Value: ⇒ yet it is still valuable
Some sources add further Vs; for example:
Validity: data has a limited period of validity, and therefore ⇒
Volatility: ⇒ older data disappears
Scalability:
It is a property of a system's architecture that makes it possible to increase its performance and capacity by adding resources (hardware, servers, nodes).
In simplified terms:
Vertical scaling
Traditional database systems scale vertically (scaling up).
From the client's perspective, the system appears to be a single server, even if its internal implementation is more complex.
As the amount of data grows, we strengthen the server (more powerful hardware: processor, memory, disk).
the post-Moore era!
Horizontal scaling
NoSQL systems typically scale horizontally (scaling out).
Servers (nodes) work together in a cluster. Data can be partitioned across nodes (sharding), replicated across multiple nodes (replication), or both. (Replication increases availability and resilience to node failure, but by itself does not increase the capacity to store distinct data.)
As the amount of data grows, we add more servers to the cluster and distribute the work or data among them.
higher overhead, unreliable network
Vertical scaling enlarges one server. Horizontal scaling adds nodes.
Database consistency / data integrity
consistere: to stand (firm) together, to hold together
integritas: the quality of being complete and whole (untouched)
transactio: to carry through, such as a (business) agreement
Relational (non-distributed) databases: ACID
Strong/strict, transactional consistency: integrity constraints are guaranteed between transactions (a consistent state).
BEGIN → READ/WRITE → COMMIT/ROLLBACK
Atomicity
Consistency
Isolation
Durability
Distributed systems: BASE
We trade strong consistency and isolation for weaker consistency plus better scalability (performance), availability, and resilience to failures (graceful degradation).
Basically available: the system tries to respond even during some failures, possibly providing only a subset of its functionality or less up-to-date data. Complete unavailability is still possible.
Soft-state: the system is dynamic and nondeterministic; the state of replicas can change even without new client requests, for example as changes propagate asynchronously.
Eventual consistency: if writes stop, replicas will eventually converge and the system will reach a consistent state; however, consistency is not guaranteed at all times.
NoSQL databases can support ACID transactions; ACID and BASE are therefore not simple, mutually exclusive categories.
CAP
In a distributed data storage system, there are three guarantees:
Consistency: all clients see (read) the same, most recent (last-written) data from any node
Availability: every functioning (non-failing) node responds correctly to requests, even if it may not provide the most recent data
Partition tolerance: the system continues operating even when parts of the cluster cannot communicate with one another (messages are not delivered or are delayed)
The CAP (quasi-)theorem
theōrēma: something observed
Eric E. Brewer: Towards Robust Distributed Systems:
Only two of C, A, and P can be guaranteed simultaneously.
If a network partition cannot occur, or partitions are not tolerated (there is no need to guarantee P), we can have both C and A at the same time: for example, in a centralized ACID database or with two-phase commit over a network.
In a distributed system with shared data, however, P must be guaranteed; it means that network partitions must be tolerated. What happens when a network partition occurs? The system chooses which operations to restrict:
CP: the system sacrifices availability; it rejects or blocks (delays) requests to avoid returning stale or conflicting data (e.g. banking systems). A pessimistic approach.
AP: the system sacrifices immediate consistency; available nodes continue to respond based on different states and rely on eventual consistency (shopping carts). An optimistic approach.
A partition splits the cluster. The two sides cannot exchange the latest write.
Once the network is connected again,
CP: we fulfill the delayed requests, or
AP: we resolve conflicts and bring the data to a consistent state
and we have AC(P) again.
It is not a black-and-white choice; there is a gray area CAP twelve years later: how the rules have changed:
An AP/CP combination: withdrawing a small amount from a bank account is AP; withdrawing a large amount is CP.
Eventual consistency
During the inconsistency window, some reads may return an older value. If writes stop, replicas can synchronize and converge; the system's strategy determines which value remains after conflicting writes.
Data distribution
Two distinct, often combined techniques:
sharding: different parts of the data (shards) are distributed across different cluster nodes ⇒ to increase available storage capacity and potentially throughput
replication: copies of data are stored on multiple nodes ⇒ greater availability and resilience to node failure; read capacity may also increase
Sharding stores different records. Replication stores copies of one record. Lecture 02 develops both.
Sharding
Main goals:
distribute data evenly across nodes (homogeneous clusters)
minimize the number of nodes a user must access to retrieve data (a simple distribution function)
optimize the physical location of servers relative to clients (network topology, geographic location)
Heterogeneous clusters
We can choose a special strategy when data is "hot" and "cold": distribute
hot (current) data on fast but low-capacity storage (new computers with SSDs and fast network connections)
cold (historical) data on slower but high-capacity storage (older computers with hard drives)
Current data can live on a fast small store, and history on a slow large one.
Replication
Two basic strategies:
master-slave (woke: primary-secondary): writes are performed on the primary node, and changes propagate to secondary nodes. Reads can be routed also to secondary nodes, which may have stale data.
peer-to-peer replication: all nodes are equal (but some are more equal than others).
Master-slave replication
Advantages:
during normal operation, writes are routed to primary node, so there are no concurrent writes on multiple nodes
Disadvantages:
writes may be limited by the performance of the primary node
secondary nodes may serve stale data due to replication lag
if the primary node fails, a new one must be elected; writes may be restricted during the election
Writes go to the primary. The log reaches the secondaries with a lag. Reads may go to a secondary, which can be behind.
Peer-to-peer replication
masterless/leaderless
All nodes are equal, and each can accept both writes and reads. How can the nodes be kept consistent?
Quorum: a minimum number of nodes must confirm an operation for it to be considered successful.
N — number of nodes (data replicas)
W — number of replicas that must acknowledge a write before it completes
R — number of replicas that must respond to a read request before the result is returned
Common configurations:
W = N, R = 1: fast reads, slow/fragile writes (all replicas must be available).
W = 1, R = N: fast writes, slow/fragile reads.
W = R > N/2 (majority quorum): balanced; node failures can be tolerated.
A write with W = 2. Two replicas have acknowledged, so the coordinator can answer before the third replica finishes.
How a write works
The client sends a write request to one node (the coordinator).
The coordinator forwards the write in parallel to all replicas, including itself.
Each replica that successfully performs the write sends an acknowledgment (ACK) back to the coordinator.
The coordinator counts the ACKs. Once it has W, it reports success to the client.
The remaining replicas complete the write.
If W ACKs have not arrived before the timeout expires, the coordinator reports failure to the client.
How a read works
The client sends a read request to one node (the coordinator).
The coordinator requests the current value in parallel from enough replicas to reach R responses. Each value is tagged with a version or timestamp.
Once the coordinator has received R values, it returns the one with the newest version to the client.
If some replicas have an older value, the coordinator then initiates read repair — an asynchronous update of the stale replicas.