SQL — NoSQL — NewSQL
Next evolution of databases. Are they only for hyperscalers?

First wave of databases: In the early days the application stored data in file-based databases. With the rising amount of data and the need for fast access to data concepts like hierarchical data model or network data model were developed to ‘organise’ stored data better.

SQL — Relational Databases
Second wave of databases: For a long time the dominant database type was the relational data model invented by Edgar Codd while working for IBM. Main scope was single node database. Consistency was the highest good — constraints and triggers were its guards. With high demand and distribution vertically scaling became expensive. For a part of the developer schema migration is an annoying effort.

NoSQL — Key/Value or Document Databases
Especially large companies like Google and Amazon suffered in their cloud environments from this. Google developed BigTable and MapReduce to scale databases horizontally. A new generation of developers growing up with persistence layers and not JDBC drivers, didn’t care much about databases. Applications with MongoDB got favoured over defining a consistent schema. Weakly typed JSON documents were the key for agile development.

In many applications the advantage of no schema is an erroneous belief. Consistency and migration has to be guaranteed in the application with nearly the costs of a relational database. On the other hand many relational databases added JSON objects as new data types allowing almost the same flexibility of document-based databases. Plus allowing also indices and querying in these nested structures.
Choose two corners of the CAP theorem! When choosing a database you can only cover two of the desired properties.

The clear sides of the triangle are getting blurred. NoSQL databases started to implement joins and query languages, while RDBMS implemented replication/high availability mechanisms.

NewSQL — the new kid on the block
We try to determine if the NewSQL databases merge the best of the two worlds. These databases fall into two categories: extensions of existing SQL databases and new developments. Currently new developments are from the big hyperscalers, while OpenSource is developing extensions to existing RDBMS. Relational databases can be extended on two sides:
- a proxy before a set of instances, every instance holding a subset of the data. The proxy controls to which database instance a request goes
- changing the underlying database storage engine
MariaDB extensions
MaxScale is a sharding proxy while ColumnStore and Cassandra are storage engines.
PostgresDB extensions
Citus is a sharding proxy while Bucardo is a data replication based on triggers allowing single and multi leader setups.
Most of the new developments are closed source from cloud providers as “database-as-a-service” (DaaS). An often used approach provides an SQL API for NoSQL databases.
Googles Cloud Spanner
Promises a relational database with almost unlimited horizontal scalability with a SLA of 99.9999%. Providing an easy integration with a JDBC driver for Spring Data. With features like
- uses hardware-assisted (atomic clock) time synchronisation to achieve data consistency (TrueTime)
- transactions can span across multiple tables
- table data are stored in PK order, which makes it very efficient and fast for PK lookups
- tables can have physical dependencies with each other. A row of a child table can be collocated with rows of the parent table. This approach speeds up lookups of relations
- support for secondary indexes
Amazon Aurora
Is either a 5-times faster MySQL database or a 3-times faster PostgresDB with a SLA of 99.99%. With features like
- automatic fault repair and scaling up to 64 TB per instance
- up to 15 read-only replicas over three availability zones
Azure CosmosDB
Is a globally distributed, horizontally partitioned, multi-model database service with a SLA of 99.99%. It supports graph-based and document-based models but also supports transactions and unique constraints. Its provides SQL API and APIs compatible to MongoDB and Cassandra. In CosmosDB ‘items’ are stored in ‘containers’. With these two concepts depending on the API different databases are possible
- MongoDB: items are documents and containers are collections
- Cassandra: items are rows and containers are tables
- Gremlin: items are nodes/edges and containers are graphs
The most popular OpenSource license database today is CockroachDB.
CockroachDB
Is based on Googles’s Cloud Spanner, compatible to PostgresDB and built on Kubernetes. Beside the OpenSource version a managed version for AWS and GCP are provided by CockroachLabs the creator of CockroachDB. With features like
- uses the Raft consensus algorithm
- distributed transactions and geo-partitioning
- uses NTP for clock synchronisation and provides serialisability as the default isolation level
What defines a NewSQL database?
Requirements of NewSQL databases:
- Replication
- Sharding
- Flexible data modeling
- Operational simplicity
Replication
Data sets are stored on several instances. This increases reliability and prevents data loss. Data can be replicated synchronous or asynchronous. In synchronous versions a transaction is only committed after all instances executed the request. In this cases a two-phase-commit can be used. Disadvantage is that with every replication instance the write time increases. Hence asynchronous versions commit a transaction after the first instance confirmed the request, but have to deal with Eventual Consistency.
Consensus Algorithm Paxos
Solves consensus in a network of unreliable processors, similar to the Raft algorithm (but harder to understand). It is used by Google’s Cloud Spanner. For that Google installed atom clocks and GPS receivers in their data centers.
Consensus Algorithm Raft
Values consistency always over availability. To guarantee linearizability all instances’ clocks have to stay in a defined range. Raft Algorithm is used by CockroachDB.
Multi model
CosmosDB allows the user to choose between five different consistency models — from guaranteed linearizability (strong), bounded staleness, session, consistent prefix to eventual consistency. Each model provides availability and performance tradeoffs.
- Strong: offers guaranteed linearizability. Linearizability refers to serving requests concurrently. The reads are guaranteed to return the most recent committed version of an item. A client never sees an uncommitted or partial write. Users are always guaranteed to read the latest committed write.
- Bounded staleness: offers total global order except within the “staleness window.” The guaranteed monotonic read exist within a region both inside and outside the staleness window.
- Session: is the default consistency level for newly created databases. It provides strong consistency for the client’s session, but writes from other sessions my lag. Data from other sessions comes in the correct order, but it is not guaranteed to be current. This provides good performance and good availability at half the cost of strong consistency and bounded staleness.
- Consistent prefix: updates that are returned contain some prefix of all the updates — with no gap. The consistent prefix consistency level guarantees that reads never see out-of-order writes.
- Eventual: has no ordering guarantee for reads. In the absence of any further writes, the replicas eventually converge.
Sharding
For a data set a shard key is determined. According to this key the data set is stored on 1-n instances. The shard key is in the simplest case a hash of the primary key, but can also be a functional key. The two challenges are joins which needs data from several instances and requests which can’t be fulfilled from one shard key e.g. secondary keys.
In cloud environments sharding is often used to store e.g. user accounts in a region close to the user in order to get small response times. Privacy regulations may also demand to keep customer data in his origin country.
CosmosDB splits the data sets according to the defined partition key. Data is automatically indexed but queries which do not refer to the partition key are slower.
Google Cloud Spanner uses a dynamic sharding. Tables will be split and merged according to the load. It supports joins and secondary indexes.
Flexible data modeling
NoSQL broke with the strong data schema of SQL databases and the need for migrations when changing the schema. Most NoSQL databases rely on JSON data structures. But the schema is implicitly defined in the application — either it expects the JSON to have a structure (because the application stored it this way) or it has to check costly a response for every field (and handle missing values).
Second advantage is to have nested data types. For example an article has a list of tags. NoSQL and NewSQL databases would allow to have a list of tags in a field of the article object. Classical relational databases would have to create an additional table with foreign key constraints.
NewSQL databases should allow to query also over this nested JSON field. For PostgresDB an extension exists which is also used by CockroachDB. As well in CosmosDB it is possible to query with SQL over the JSON data type.
Google’s Cloud Spanner goes an other way. It supports ARRAY and STRUCT beside the basic datatypes (but no JSON).
Operational simplicity
The relational database’s way for replication was to have a (single) master database and a slave database (or more). The slave databases executed with some delay the queries. Setting up replication and testing fallback scenarios was a time consuming nerve recking task.
For NewSQL databases this task should be much simpler. An instance is installed on a node and gets a list of the other instances. The instance finds the nodes and starts an automatic rebalancing.
In part II we will challenge the big 3 — Cloud Spanner, CosmosDB and CockroachDB with real live examples to see how they meet the four NewSQL requirements. Stay tuned and up to the next peak!