The relational model

The relational model has been around since its initial proposal by E.F. Codd, who issued his paper “A Relational Model of Data for Large Shared Data Banks” in 1970 after an internal IBM paper one year earlier. Because the purpose of this guide is not to give you a full background but rather to help you to understand systems you encounter today, we will focus on relational systems in modern organizations.

The basic premise of relational database models, is that data is represented as a series of relationships, based around unique keys that are the core identifiers for a piece of data. The relational model creates consistency of data across tables with constraints on relationships, cardinality, values, and the requirements for certain attributes to exist or not. The relational model is formalized and includes various levels of strictness, also known as normalization. The reality is that many of these theoretical requirements fall by the wayside as performance and concurrency come into play.¹

Well-known relational databases include Oracle, MySQL, PostgreSQL, DB2, SQL Server, and Sybase. More alternative players in field include Google Spanner, Amazon RedShift, NuoDB, and Firebird. Many of these alternative systems are classifed as NewSQL. These are considered to be a subclass of relational database management systems that seek to break some of the barriers of concurrency and scale while maintaining consistency guarantees. This will be discussed further in this chapter.²

The relational model provides a very well-known approach to data retrieval. By supporting joins, one-to-many, and many-to-many relationships, developers have a high level of flexibility in how they define their data model. This can also lead to much more challenging approaches to schema evolution, as the addition, modification or removal of tables, relationships, and attributes all can require a large amount of coordination and moving parts in order to be accomplished. This can lead to expensive and risky changes, as discussed in Chapter 8.

Many software teams choose to operate an object relational management (ORM) layer to facilitate work by mapping the relational model to the object model defined at the software layer. Such ORMs can be great tools for developer velocity, but they can prove problematic to the database reliability engineer (DBRE) team in multiple ways.

All of this leads many software engineers and architects to think of relational systems as unflexible and an impedance to developer velocity. This is far from accurate, however, and later in this chapter we present a more accurate list of pros and cons and bust some of the myths prevalent in many such lists.

The key–value model

A key–value model stores data as a dictionary or hash. A dictionary is analogous to a table and contains any number of objects. Each object can store any number of attributes or fields within it. Like a relational database, these records are uniquely identified with a key. Unlike relational databases, there is no way to create mappings between objects based on those keys.

The key–value datastore sees an object as a blob of data. It isn’t inherently aware of the data it holds, and thus each object can have different fields, nested objects, and an infinite amount of variety. This variety comes at a cost, including the potential for inconsistency because rules are not enforced at the common storage layer. Similarly, efficiencies in datatypes and indexing are unavailable. On the other hand, a lot of the overhead inherent to managing various datatypes, constraints, and relationships are gone. If the application doesn’t need this, efficiencies can be realized.

Examples of key–value stores can be quite varied. One example is Dynamo. In 2007, Amazon published the Dynamo paper as a set of techniques to build a highly available, distributed datastore. As soon as we’ve gone over all of the attributes, we will discuss Dynamo in more detail. Dynamo-based systems include Aerospike, Cassandra, Riak, and Voldemort. Other key–value implementations include Redis, Oracle NoSQL Database, and Tokyo Cabinet.

The document model

The document model is technically a subset of the key–value model. The difference with the document model is that the database maintains metadata about the structure of the document. This allows for datatype optimization, secondary indexing, and other optimizations. Document stores store all information about the object together, rather than across tables. This allows for all data to be retrieved from one call, rather than requiring joins, which, although declaratively easy, can consume significantly more resources. This also typically eliminates the need for an ORM layer.

On the other hand, this means that document stores inherently require denormalization if there are different views of the object required. This can cause bloat and create consistency issues. Additionally, external tools are required to enforce data governance, as the schema no longer exists as a self-documenting system.⁴

The navigational model

Navigational models began with hierarchical and network databases. Today, when referring to navigation models, we are almost always discussing the graph data model. A graph database uses nodes, edges, and properties to represent and store data and the connections between objects. The node holds the data about a specific object, the edge is the relationship to another object, and properties allow additional data about the node to be added. Because relationships are directly stored as part of the data, links can easily be followed. Often, an entire graph can be retrieved in one call.

Graph stores, like document stores, often map more directly to the structure of object-oriented applications. They also eliminate the need for joins and can prove to have more flexibility in terms of data model evolution. Of course, this works only for data that is ideal for graph-appropriate queries. Traditional queries can prove to be far less performant.⁵

Each of these models has its place in a certain subset of applications. We will summarize the options and trade-offs within. First, let’s look at transactional support and implementation attributes.

ACID

An ACID database provides a set of guarantees that, when put together, create the acronym ACID. These guarantees are (A)tomicity, (C)onsistency, (I)solation, and (D)urability. In 1983, Andreas Reuter and Theo Härder coined the acronym, building on work by Jim Gray, who enumerated Atomicity, Consistency, and Durability but left out Isolation. These four properties describe the major guarantees of the transaction paradigm, which has influenced many aspects of development in database systems.

It is of the utmost importance when working with a datastore to understand how it defines and implements these concepts because there can be a significant amount of ambiguity and diversity. With this in mind, it behooves us to consider each property and to understand the variations to be found in the wild.⁶

Atomicity

Atomicity refers to the guarantee that an entire transaction will be committed, or written, to the datastore or that the entire transaction will be rolled back. There is no such thing as a partial write or rollback in an atomic database. Atomicity, in this context, does not refer to atomic operations as you might find in software engineering. That term refers to the guarantee of isolation from concurrent processes seeing work in progress rather than only the before and after results.

There are many reasons that a transaction might fail and require rollback. The client process might terminate mid-transaction, or perhaps a network fault could terminate the connection. Similarly, database crashes, server faults, and numerous other operations could require a partially completed transaction to be rolled back.

PostgreSQL implements this by using pg_log. Transactions are written in pg_log and given a state of in progress, committed, or aborted. Should a client abandon or rollback a transaction, it will be marked as aborted. Backend processes will also periodically mark transactions as aborted if there are no backends mapped to it.

It is important to note that you can consider writes atomic only if the underlying disk page writes are atomic. There is significant disagreement on the atomicity of sector writes. Most modern disks will channel power to writing a sector even during a disk failure. But depending on the layers of abstraction between the physical drive and the actual writes being flushed to disk, there are still plenty of opportunities for data loss.

Consistency

The guarantee of consistency is a guarantee that any transaction will bring the database from one valid state to another. A transaction being written can assume to not be able to violate defined rules. Technically, consistency is defined at the application level rather than the database. Traditional databases do, however, give the developer tools to enforce this consistency. Those tools can be guaranteed effective and include constraints and triggers. Constraints can include foreign keys with cascading, not null, uniqueness constraints, datatypes and lengths, and even specific values being allowed in a specific field.

It is interesting and frustrating that consistency is used elsewhere in the realms of databases and software. The CAP theorem uses the term consistency also but in a very different way. Similarly, you will hear this term when discussing hashing and replication.

Isolation

The isolation guarantee is a promise that the concurrent execution of transactions results in the same state that would occur if you were to run those transactions serially and sequentially. ACID databases do this via a combination of techniques that can include write locks, read locks, and snapshots. Collectively this is called concurrency control. In practice, there are multiple types of concurrency control that can lead to different behaviors in the database. Stricter versions can significantly impact performance of concurrent transactions, whereas more relaxed ones might lead to better performance at the cost of less isolation. ⁷

The ANSI/ISO SQL standard defines four possible levels of transaction isolation. Each level would potentially provide a different outcome for the same transaction. These levels are defined in terms of three potential occurrences that are permitted or not at each isolation level:

Dirty read

With a dirty read, you can potentially read uncommitted, or dirty, data that is being written in another transaction from another client.

Nonrepeatable read

With a nonrepeatable read, within the context of a transaction, if you perform the same read twice, you could potentially get different results based on other concurrent activities in the database.

Phantom read

With a phantom read, within the context of a transaction, you perform the same read twice, and the data returned the second time is different from the first. This is different from a nonrepeatable read because with a phantom read, data you have already queried does not change, but more data is returned by your query than before.

To avoid these phenomena, there are four potential isolation levels that can be utilized:

Read Uncommitted

This is the lowest isolation level. Here, dirty reads, dirty writes, and nonrepeatable and phantom reads are all allowed.

Read Committed

In this isolation level, the goal is to avoid dirty reads and dirty writes. In other words, you should not be able to read, or overwrite, uncommitted data. Some databases will avoid dirty writes via write locks acquired on selected data. Write locks are held until the data is committed, and read locks are released after select. Dirty reads are usually implemented by keeping two copies of the data being written in the transaction, one of older committed data to be used for reads from other transactions and one for the data that has been written but not committed.

In read committed isolation, you can still experience nonrepeatable reads however. If uncommitted data is read once and then read again after it has been committed, you will see different values within the context of your own transaction.

Repeatable Reads

To achieve read committed isolation level and to avoid nonrepeatable reads, you must implement additional controls. If a database is using locks to manage concurrency control, a client would need to keep read and write locks until the end of the transaction. This would not maintain a range lock, though, so it would be possible to get phantom reads. As you can imagine, this lock-based approach is heavy handed and can lead to significant performance impact on highly concurrent systems.

The other way to accomplish this is via snapshot isolation. In snapshot isolation, after a transaction is started, the client will see an image of the database based on the current time. Additional writes will not show in the snapshot, allowing for long-running queries to have consistent, repeatable reads. Snapshot isolation uses write locks but not read locks. The goal is to ensure that reads do not block writers, and vice versa. Since this requires more than just two copies, it is referred to as multiversion concurrency control (MVCC).

In repeatable read snapshot isolation, write skew can still occur. In write skew, two writes can be allowed on the same column or columns in a row from two different writers who have read the columns they are updating. This results in rows that can have data from two transactions.

Serializable

This is the highest isolation level and is meant to avoid all of the aforementioned phenomena. Like in repeatable read, if locks are the focus of concurrency control, read and write locks are held for the duration of the transaction. There are additions, however, and the locking strategy is called 2-phase locking (2PL).

In 2PL, a lock can be shared or exclusive. Multiple readers can hold shared locks for reading. However, to get an exclusive lock for a write, all shared read locks must be released after a commit. Similarly, if a write is occurring, shared locks for reads cannot be acquired. In this mode, it can be quite common in high-concurrency environments for transactions to be stuck waiting for a lock. This is called a deadlock. Additionally, range-locks must also be acquired for queries using ranges in their WHERE clauses. Otherwise, phantom reads occur.

2PL can dramatically affect latency for transactions. When many transactions are waiting, system-wide latency can increase significantly. Thus, many systems do not truly implement serializability and stick to repeatable read.

The non-lock-based approach builds on snapshot isolation and is called serial snapshot isolation (SSI). This approach is an optimistic serialization, whereby the database waits until commit to see if any activities have occurred to cause a serializability issue, most often a write collision. This can significantly reduce latency in systems for which concurrency violations are few. However, if these are regular things, the constant rollback and retries can be quite significant.

Because each isolation level is stronger than those below in that no higher isolation level allows an action forbidden by a lower one, the standard permits a DBMS to run a transaction at an isolation level stronger than that requested (e.g., a “Read Committed” transaction may actually be performed at a “Repeatable Read” isolation level).

We have only scratched the surface of isolation, isolation anomalies, and isolation implementations. We have a few delightful recommended reads for you for further dives at the end of the chapter.

Durability

The durability guarantee promises us that as soon as a transaction has been committed, it remains committed. Whether there is a power loss, database crash, hardware fault, or any other issue, the transaction stays durable. Obviously, the database cannot promise that the underlying hardware will support this durability. As discussed in Chapter 5, there are numerous opportunities for the database to believe it has synchronized to disk, when the reality is very different.

Durability is linked closely to atomicity, as durability is required for atomicity. Many databases implement a write-ahead log (WAL) to capture all writes before they are pushed to disk. This log is used to undo a transaction as well as to reapply it. If there is a failure, upon restarting, the database can check this log against the system to determine whether the transaction must be undone, completed, or ignored.

Much like isolation levels, there are times when durability can and should be relaxed to accommodate performance. For true durability, flush to disk must occur on every commit. This can become prohibitively expensive and is not required for all transactions and writes. For instance, in MySQL, you can tune the Innodb log flush to perform periodically rather than after each commit. Similarly, you can do this for replication logs.⁹

Even though we have stayed fairly high-level here, it should be apparent just how much detail is hidden and taken for granted in systems that support transactions. As a DBRE in an organization, it is critical for you to ensure familiarity with the implementation not only for yourself, but also for the development organization. Often the details of these implementations are not readily apparent from documentation, and further tests via such tools as Jepsen and Hermitage can assist you in this discovery process.

Similarly, this knowledge can help you in choosing appropriate configurations when there are options to relax durability or use weaker isolation. Alternatively, knowing when database defaults do not meet your applications needs can be just as important.