Storage and Retrieval

Designing Data-Intensive Applications · Chapter 3 · Recall lab

Chapter 2 asked what shape your data has. Chapter 3 goes one layer down and asks what the engine actually does with it: what happens when you store data, and what the database does when you ask for it back. Two questions organise everything below. Are you appending to files or overwriting pages in place? That splits transactional storage into two schools which have been arguing since 1970. Are you fetching a few records by key or scanning millions of them? That splits storage engines into OLTP and analytics altogether, and by the end of the chapter the answer to the second question has quietly rearranged the answer to the first.

#!/bin/bash

db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

The constraint is that all the keys must fit in available RAM, since the hash map is kept completely in memory. The values can use more space than there is memory, because they can be loaded from disk with just one seek, and if that part of the file is already in the filesystem cache, a read requires no disk I/O at all.

The workload this suits is one where the value for each key is updated frequently. The chapter’s example: the key is the URL of a cat video and the value is the number of times it has been played, incremented on every press of play. Lots of writes, not too many distinct keys, so many writes per key and keeping all the keys in memory is feasible.

Compaction and segment merging

If we only ever append, how do we avoid running out of disk? Break the log into segments of a certain size: close a segment file when it reaches a size threshold and write subsequently to a new one. Then run compaction on those segments, throwing away duplicate keys and keeping only the most recent update for each key. Because compaction usually makes segments much smaller, you can merge several at the same time as compacting them.

Five things a real implementation has to get right

Advantage 1, merging is simple and efficient, even beyond memory size

The approach is the one used in mergesort: read the input files side by side, look at the first key in each, copy the lowest key to the output, repeat. The output is a new merged segment, also sorted by key. Watch what happens at handful, the key that is in both inputs.

Advantage 2, the in-memory index can be sparse

You no longer need an index of all the keys in memory. Say you want handiwork and do not know its offset, but you do know the offsets of handful and handkerchief, and because of the sorting handiwork must lie between them. Jump to the lower offset and scan from there. One key every few kilobytes of segment file is sufficient, because a few kilobytes can be scanned very quickly.

Advantage 3, compressed blocks

Since a read has to scan over several key-value pairs in the requested range anyway, you can group those records into a block and compress it before writing to disk. Each entry of the sparse index then points at the start of a compressed block. Besides saving disk space, compression reduces I/O bandwidth use.

Constructing and maintaining SSTables

So how does the data get sorted by key in the first place, when incoming writes arrive in any order? Maintaining a sorted structure on disk is possible, that is a B-tree, but maintaining it in memory is much easier, using a well-known balanced tree such as a red-black tree or an AVL tree: insert in any order, read back in sorted order. That is the answer to the worry above, and the figure on the left is the whole write path running at once.

Making an LSM-tree out of SSTables

This algorithm is essentially what LevelDB and RocksDB use, key-value storage engine libraries designed to be embedded into other applications. LevelDB can be used in Riak as an alternative to Bitcask. Similar engines are used in Cassandra and HBase, both inspired by Google’s Bigtable paper, which introduced the terms SSTable and memtable. The structure was originally described by Patrick O’Neil et al. as the Log-Structured Merge-Tree, building on earlier work on log-structured filesystems, and engines built on this principle of merging and compacting sorted files are called LSM storage engines.

Performance optimizations

The LSM-tree algorithm can be slow when looking up keys that do not exist: you have to check the memtable, then the segments all the way back to the oldest, possibly reading from disk for each one, before you can be sure the key is not there. Hence Bloom filters, a memory-efficient data structure for approximating the contents of a set. It can tell you if a key does not appear in the database, saving many unnecessary disk reads for nonexistent keys.

Like SSTables they keep key-value pairs sorted by key, which allows efficient lookups and range queries. That is where the similarity ends. Log-structured indexes break the database into variable-size segments, typically several megabytes or more, always written sequentially. B-trees break it into fixed-size blocks or pages, traditionally 4 KB, sometimes bigger, and read or write one page at a time. That design corresponds more closely to the underlying hardware, since disks are also arranged in fixed-size blocks.

Branching factor and depth

The number of references to child pages in one page is the branching factor. In practice it depends on the space needed to store page references and range boundaries, but typically it is several hundred. Which is the entire reason a lookup is three or four hops rather than thirty.

Updates, insertions, and the page split

To update an existing key, find the leaf page containing it, change the value in that page, and write the page back to disk. Any references to that page remain valid. To add a new key, find the page whose range encompasses it and add it there. If there is not enough free space, the page is split into two half-full pages, and the parent page is updated to account for the new subdivision of key ranges. Inserting is reasonably intuitive; deleting a key while keeping the tree balanced is somewhat more involved.

Making B-trees reliable

The basic underlying write operation of a B-tree is to overwrite a page on disk with new data, and it is assumed the overwrite does not change the page’s location, so all references to it remain intact. This is in stark contrast to LSM-trees, which only append to files and eventually delete obsolete ones, but never modify files in place. Think of it as an actual hardware operation. On a magnetic drive: move the head, wait for the right position on the spinning platter, overwrite the sector. On SSDs it is more complicated, because an SSD must erase and rewrite fairly large blocks of a storage chip at a time.

Updating pages in place also demands careful concurrency control if multiple threads access the tree at once, or a thread may see the tree in an inconsistent state. This is typically done by protecting the data structures with latches, lightweight locks. Log-structured approaches are simpler here, because they do all the merging in the background without interfering with incoming queries, and atomically swap old segments for new ones from time to time.

B-tree optimizations, in brief

Write amplification

A B-tree index must write every piece of data at least twice: once to the write-ahead log, and once to the tree page itself, and perhaps again as pages are split. There is also overhead from having to write an entire page at a time even if only a few bytes changed. Some storage engines even overwrite the same page twice, to avoid ending up with a partially updated page after a power failure. Log-structured indexes also rewrite data multiple times, through repeated compaction and merging of SSTables.

It is also very common to have secondary indexes: several per table via CREATE INDEX, often crucial for performing joins efficiently. A secondary index is easily constructed from a key-value index; the main difference is that keys are not unique, since many rows may share a key. Two ways to solve that: make each value in the index a list of matching row identifiers, like a postings list in a full-text index, or make each key unique by appending a row identifier to it. Either way, both B-trees and log-structured indexes work as secondary indexes.

Storing values within the index

Multi-column indexes

The most common kind is a concatenated index, which combines several fields into one key by appending one column to another, in the order the index definition specifies. This is an old-fashioned paper phone book: an index from (lastname, firstname) to phone number. Two of the three queries below are what it was built for. The third is the one that exposes it.

Multi-dimensional indexes are a more general way to query several columns at once, which matters particularly for geospatial data. A restaurant-search site showing a map needs a two-dimensional range query:

SELECT * FROM restaurants WHERE latitude  > 51.4946 AND latitude  < 51.5079
                            AND longitude > -0.1162 AND longitude < -0.1004;

A standard B-tree or LSM-tree cannot answer that efficiently. It can give you all the restaurants in a range of latitudes at any longitude, or all in a range of longitudes anywhere between the poles, but not both simultaneously. One option is to translate the two-dimensional location into a single number with a space-filling curve and use a regular B-tree; more commonly, specialized spatial indexes such as R-trees are used. PostGIS implements geospatial indexes as R-trees using PostgreSQL’s Generalized Search Tree facility.

Full-text search and fuzzy indexes

Every index so far assumes exact data and lets you query exact values, or a range of values with a sort order. What they do not let you do is search for similar keys, such as misspelled words. Full-text search engines commonly expand a search for one word to include synonyms, ignore grammatical variations, search for words near each other in the same document, and other features that depend on linguistic analysis. To cope with typos, Lucene can search for words within a certain edit distance, where an edit distance of 1 means one letter has been added, removed or replaced.

Keeping everything in memory

Every data structure in this chapter so far is an answer to the limitations of disks. Compared to main memory, disks are awkward: data must be laid out carefully for good performance on both magnetic disks and SSDs. We tolerate that because disks have two significant advantages, they are durable and they have a lower cost per gigabyte than RAM. As RAM gets cheaper the cost argument erodes, and many datasets simply are not that big, so keeping them entirely in memory becomes feasible, potentially across several machines.

It is still an in-memory database even when it writes to disk, because the disk is merely used as an append-only log for durability and reads are served entirely from memory. Writing to disk also has operational advantages: files can be backed up, inspected and analyzed by external utilities. VoltDB, MemSQL and Oracle TimesTen are in-memory databases with a relational model, whose vendors claim big improvements from removing all the overheads of managing on-disk structures. RAMCloud is an open source in-memory key-value store with durability, using a log-structured approach for the data in memory as well as on disk. Redis and Couchbase provide weak durability by writing to disk asynchronously.

Recent research suggests the architecture could be extended past available memory without bringing back disk-centric overheads. The anti-caching approach evicts the least recently used data from memory to disk when memory runs short, and loads it back when accessed again. This is similar to what operating systems do with virtual memory and swap files, but the database can manage memory more efficiently than the OS because it works at the granularity of individual records rather than entire memory pages. It still requires the indexes to fit entirely in memory, like the Bitcask example at the start of the chapter. Further design changes will probably be needed if non-volatile memory technologies become widely adopted.

The access pattern stayed similar even as the data changed: an application looks up a small number of records by some key, using an index, and inserts or updates records based on user input. Because these applications are interactive, the pattern became known as online transaction processing (OLTP).

Analytics has very different patterns. An analytic query usually scans over a huge number of records, reads only a few columns per record, and calculates aggregate statistics, count, sum, average, rather than returning raw data to the user. The chapter’s three examples:

• What was the total revenue of each of our stores in January?
• How many more bananas than usual did we sell during our latest promotion?
• Which brand of baby food is most often purchased together with brand X diapers?

These are often written by business analysts and feed reports that help management make better decisions, which is business intelligence. To distinguish the pattern it was named online analytic processing (OLAP). The meaning of online there is unclear; it probably refers to the fact that queries are not just for predefined reports, but that analysts use the system interactively for explorative queries.

Data warehousing

An enterprise may have dozens of transaction processing systems: the customer-facing website, point-of-sale checkout, warehouse inventory, vehicle route planning, supplier management, employee administration. Each is complex, needs a team, and ends up operating mostly autonomously. They are expected to be highly available and low-latency because they are critical to the business, so database administrators guard them closely and are usually reluctant to let analysts run ad hoc queries on them: those queries are expensive, scan large parts of the dataset, and can harm the performance of concurrently executing transactions.

A data warehouse is a separate database analysts can query to their hearts’ content without affecting OLTP operations. It holds a read-only copy of the data from all the various OLTP systems, brought over by Extract, Transform, Load (ETL): extracted using either a periodic data dump or a continuous stream of updates, transformed into an analysis-friendly schema, cleaned up, then loaded.

A warehouse’s data model is most commonly relational, because SQL is generally a good fit for analytic queries, and many graphical tools generate SQL, visualize results, and let analysts explore through operations like drill-down and slicing and dicing. On the surface a warehouse and a relational OLTP database look similar, both have a SQL interface, but the internals can look quite different because they are optimized for very different query patterns. Microsoft SQL Server and SAP HANA support both in one product, but they are increasingly becoming two separate storage and query engines that happen to be accessible through a common SQL interface.

Stars and snowflakes

Transaction processing uses a wide range of data models depending on the application. Analytics has much less diversity: many warehouses are used in a fairly formulaic style known as a star schema, also known as dimensional modeling.

-- Are people more inclined to buy fresh fruit or candy,
-- depending on the day of the week?
SELECT
  dim_date.weekday, dim_product.category,
  SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
  JOIN dim_date    ON fact_sales.date_key    = dim_date.date_key
  JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
  dim_date.year = 2013 AND
  dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
  dim_date.weekday, dim_product.category;

It touches a large number of rows, every purchase of fruit or candy in 2013, but only three columns of fact_sales: date_key, product_sk and quantity. It ignores all the others. In most OLTP databases storage is laid out row-oriented, with all the values from one row stored next to each other, and document databases are similar, since an entire document is typically one contiguous sequence of bytes. Watch what that costs.

Column compression and bitmap encoding

Beyond loading fewer columns, you can further reduce demands on disk throughput by compressing, and column-oriented storage often lends itself very well to it, because the sequences of values in a column often look quite repetitive. One technique particularly effective in warehouses is bitmap encoding. Often the number of distinct values in a column is small compared with the number of rows: a retailer may have billions of sales transactions but only 100,000 distinct products.

Memory bandwidth and vectorized processing

For queries scanning millions of rows, a big bottleneck is the bandwidth for getting data from disk into memory, but that is not the only one. Developers of analytical databases also worry about efficiently using the bandwidth from main memory into the CPU cache, about avoiding branch mispredictions and bubbles in the CPU instruction processing pipeline, and about making use of SIMD instructions in modern CPUs.

Sort order in column storage

In a column store it does not necessarily matter in which order rows are stored. Insertion order is easiest, since then inserting a row just means appending to each of the column files. But you can choose to impose an order, as with SSTables, and use it as an indexing mechanism.

The administrator chooses the sort columns using knowledge of common queries. If queries often target date ranges such as the last month, it makes sense to make date_key the first sort key, so the optimizer can scan only the rows from the last month. A second column determines the order of rows tied on the first, so making product_sk second groups all sales for the same product on the same day together, which helps queries that group or filter sales by product within a date range.

Several different sort orders

A clever extension introduced in C-Store and adopted in Vertica: different queries benefit from different sort orders, so why not store the same data sorted in several different ways? Data needs to be replicated to multiple machines anyway so you do not lose it when one fails, so you might as well store that redundant data sorted differently, and use whichever version best fits the query pattern you are processing.

Writing to column-oriented storage

All these optimizations make sense because most of the load in a warehouse is large read-only queries run by analysts. The downside is that they make writes more difficult. An update-in-place approach, as B-trees use, is not possible with compressed columns. Insert a row in the middle of a sorted table and you would most likely have to rewrite all the column files, because rows are identified by their position within a column, so the insertion has to update all columns consistently.

Aggregation, data cubes and materialized views

Not every data warehouse is necessarily a column store, since traditional row-oriented databases and a few other architectures are also used, but columnar storage can be significantly faster for ad hoc analytical queries, so it is rapidly gaining popularity. Warehouse queries often involve an aggregate function such as COUNT, SUM, AVG, MIN or MAX, and if the same aggregates are used by many queries, crunching the raw data every time is wasteful. So cache them.

A common special case of a materialized view is a data cube or OLAP cube: a grid of aggregates grouped by different dimensions. Imagine each fact having foreign keys to just two dimension tables, date and product. Draw a two-dimensional table with dates on one axis and products on the other, and each cell holds the aggregate of an attribute of all facts with that date-product combination. Then apply the same aggregate along each row or column to get a summary reduced by one dimension.

Chapter 3 in one breath. Storage engines fall into two broad categories. OLTP engines are user-facing and see a huge volume of requests, each touching a small number of records fetched by key through an index, and disk seek time is often the bottleneck. Analytic systems handle far fewer queries, but each is very demanding, scanning millions of records in a short time, and here disk bandwidth, not seek time, is often the bottleneck, with column-oriented storage as an increasingly popular answer.

On the OLTP side there are two schools of thought. The log-structured school only permits appending to files and deleting obsolete ones, never updating a file already written: Bitcask, SSTables, LSM-trees, LevelDB, Cassandra, HBase, Lucene. The update-in-place school treats the disk as a set of fixed-size pages that can be overwritten, with B-trees as the biggest example, used in all major relational databases and many nonrelational ones. Log-structured engines are a comparatively recent development, and their key idea is that they systematically turn random-access writes into sequential writes on disk, which enables higher write throughput given the performance characteristics of hard drives and SSDs.

The detour into warehouse architecture explains why analytic workloads are so different: when queries sequentially scan a large number of rows, indexes matter much less, and what becomes important is encoding data very compactly to minimize how much the query must read from disk.