Ingredients of Storage System — Part I

TL;DR: this note is a rewrite of my earlier note about Lakehouse. The feedback I got is that the Lakehouse note is too long. In this note, I will focus on some of the key ingredients of single node storage system. I will rewrite the Lakehouse note later.

Background

The acts of the mind, wherein it exerts its power over simple ideas, are chiefly these three: 1. Combining several simple ideas into one compound one, and thus all complex ideas are made. 2. The second is bringing two ideas, whether simple or complex, together, and setting them by one another so as to take a view of them at once, without uniting them into one, by which it gets all its ideas of relations. 3. The third is separating them from all other ideas that accompany them in their real existence: this is called abstraction, and thus all its general ideas are made.

John Locke, An Essay Concerning Human Understanding (1690)

Thinking in terms of abstractions and combinations is powerful. There are numerous storage systems, but there are only a limited set of concepts and techniques in them. The difference between them is mostly about how to combine things together to serve the use cases they are targeting at best.

This document will summarize some of the key concepts and techniques for single node storage systems.

Write Read and space amplification

Write, read, and space amplification might be the most important problems to address in any storage system.

If we read or write a record that is about M bytes from a storage system, the actual I/O size in bytes (N) is likely to be different from M. The ratio between N and M is the amplification. For example, if we read 1K bytes from a 4K disk block, the amplification is 4.

Space amplification is about the ratio between the disk space used to store the data and the data size. Compression is one technique that reduces space amplification. Internal fragmentation, external fragmentation, out of date version of records, auxiliary metadata and index are common factors that increase space amplification.

Example: Sequential File

We will use sequential file without index that stores key value pairs as an example to understand amplification better.

To find latest record for a key, we will have to scan the entire file. The read amplification will be the total file size / record size. Assume on average we only need to read half of the file to find a record, the amplification is reduced by a factor of two.

To write/update a new record, we append record to the end of file. It seems that write amplification will be 1. But this might not necessarily be true. A natural requirement for storage system is the data written will be persistent, which means the data need to be flushed to disk before the call to write data returns. Most storage systems do I/O in blocks (4KB,16KB etc.) Writing a block that is not fully occupied will amplify the write. Therefore, most storage systems have settings for buffer size and flush interval. Full blocks can be accumulated in memory before writing them to disk to reduce amplification. The flush interval is important for latency sensitive use cases.

Since we always append records to the end of the file, there could be multiple records for the same key in the files if there are updates. If 10% of the records in the file are updates, then space occupied by these records is wasted. The space amplification is 100/90 if the records are fixed size.

It should be obvious that looking up individual records from sequential files is something we should avoid. Batching is one commonly used technique that can help (read amplification is reduced by the number of records in a batch.) Another technique is adding index to the file, which is typically done when we seal files. The index can be a sorted array or a hash table like data structure. This effectively turns a linked list data structure into a binary search tree/hash table so individual record lookup will be more efficient. Even with index, batching is still preferred since we can potentially merge many requests into one sequential I/O, which might be more efficient than many small random I/Os.

How to Control Amplification

We used sequential file as an example to analyze amplification above. Amplification characteristics will be quite different for different storage organization schemes that are designed with different tradeoffs in mind and are targeted at different use cases. The designer of a system can either:

• document the use cases the system is optimized for.
• make it possible for users to choose from a few schemes and provide knobs to tune
• choose the right options based on access pattern for the users.

Option 3 is the ideal case, but the industry is still in the early stage in this direction. For more information about this direction, search for autonomous database or self-driving database.

Before autonomous systems are available, users/designers of storage system need to have a good understanding about the access patterns of their use cases to make the right choice. It will be helpful to list details about the operations needed by use cases, the frequency and latency requirement of these operations. Without such information, it is hard to tell what the right tradeoffs are.

Amplification has a profound impact on the performance of storage systems. Storage systems in general provide a lot of tuning knobs related to amplification.

Bloom Filter

Bloom filter is one example to reduce read amplification. If we try to find a record from a set of files, it is useful to tell if a key exists in file so we can skip files that we do not need. We can use a set data structure to implement this. The overhead of the set data structure will be the number of keys * average key size. A bloom filter is a more memory-efficient data structure, which only uses a few bits per key, to tell whether an element is present in a set.

A bloom filter is a fixed-size bitmap. For each key in a set, two or more hash functions are called to generate slots that will be marked in the bitmap. During lookup, we will call the same set hash functions to generate slots to check. A key only exists in the set when all its slots are marked.

The following is an example of bloom filter that uses three hash functions:

The main caveat of bloom filter is that it can generate false positive. False positives happen when all slots of a non-existing key are marked by some other keys due to hash collision. This is not a problem in practice for two reasons:

• The chance of false positive is low and controllable by choosing number of hash functions and bitmap size. As we mentioned earlier, more than one hash function are used in practice because false positive rate might be too high if one hash function is used.
• The filter is normally used to avoid reading from a file. The worst thing that can happen when there is false positive is that we will read a file and find the key does not exist. We will waste some time, but the system will still behave correctly.

Another problem with Bloom filter is that we cannot delete key from the set since we do not know if the slots for the key are also marked some other keys.

*There are some new filters (XOR, Robbin) that can perform better than bloom filters. The recent version of RocksDB implemented this.

Columnar Format

Records in storage systems can be stored one after another on disk. This is called row format. The benefit of row format is that if once we find the offset and size information about a record from index, we can send one I/O request to fetch the record. This is commonly used in key value stores or online transactional systems where we access individual records frequently.

In analytics system, reading selected columns from many records that satisfies specific criteria is the more typical access pattern. Row format is not suitable for this pattern since we will read data for unnecessary columns.

Columnar format is designed to improve this. In columnar format, data for columns are stored one after another. We only need to read the columns we need. To further reduce I/O, columns can be divided into groups. Each group can have some basic statistics such as min/max value for each column. The statistics of groups can be used to skip groups that will not satisfy the criteria user specified. Another side benefit of organizing data by columns is that the entropy of data (in plain words the possible values) for columns is lower so we can compress the columns much better. This is another example of reading the data we really need to reduce amplification.

Parquet is a popular columnar format:

In Parquet, data in each row group can be sorted by a column. The recommendation is to have large enough row groups (for example 1GB). The data in a column can be broken into small pages (for example 8KB.) The small pages combined with page index can provide reasonably good performance for point lookup. Note point lookup is still more expensive than row format since we might need to read from pages from multiple columns.

MVCC

Storage system needs to have concurrency control to provide isolation between concurrent readers and writers and prevent anomalies in read and write. One solution is to use read-write lock, which means writers will block other writers and readers. If we look at the conflict between writer and reader, the main reason we want to block readers while writer is in progress is that value of the data might be a temporary inconsistent state and writer can abort. MVCC solves the problem by keeping multiple versions of each data item. The uncommitted versions can be hidden from readers, so readers do not need to be blocked by writers.

One way to implement MVCC is to assign a timestamp to each reader when it starts and a commit timestamp to each writer when it commits. The commit time stamp will be associated with all items committed by a writer. If we store all versions of a data item as a linked list (from newest to oldest,) then the reader can walk the linked list to find a committed version that is older than its timestamp. Writers can still use locks to block other writers. This scheme is also called snapshot isolation since a reader can use the same timestamp to read data in the same transaction and will get the same values for the same data items.

The following is an example that illustrates how MVCC avoids reader/writer conflicts:

In this example, T2 can update record 100 while T1 reads the previous version.

Of course, nothing comes for free. The obvious price we need to pay for MVCC is space amplification caused by storing multiple versions of data. Systems that use MVCC will need a background service to clean up out-of-date versions that are no longer used for active transactions.

Two Phase Locking

Transactions can modelled as a series of read and write operations. If we run one transaction one after another in serial, the behavior of the system will be easy to understand. However to improve system performance, we want to allow transactions to run concurrently. As we mentioned earlier, locking is used to prevent undesired anomalies. Two phase locking are a set of rules that can help achieve serial behavior while running transaction concurrently:

• before reading x, sets a read lock on x
• before writing x, sets a write lock on x
• holds each lock until after a transaction executes the corresponding operation
• after its first unlock operation, it requests no new locks

Basically, each transaction sets locks during a growing phase and releases them during a shrinking phase.

We define conflicting operations as read and write or write and write on the same item. The goal of the rules above is to force ordering between transactions with conflicting operations. Following is an example:

… rx_1 <non-conflicting ops from T1 and T2 > wx_2(blocks T2) <ops from T1>

‘rx_1’ means reading x in T1. ‘wx_2’ means writing x in T2. We can see wx_2 will block T2 and T1 can continue to finish all its operation. So T1 will precede T2.

We should note these rules don’t prevent deadlocks. Following is an example:

… rx_1 ry_2 wx_2(blocks T2) wy_1(blocks T1>

Deadlock is ok since the system didn’t allow the execution that doesn’t behave serial.

The formal proof can be found here.

Optimistic Concurrency

The mechanism we use to prevent conflicts between writers, locking, is called pessimistic concurrency control since we expect conflicts will happen and try to prevent them from happening. Optimistic concurrency control is the opposite: we will assume conflicts will not happen and deal with conflicts when they happen.

Version numbers can be used for conflict detection. A writer can take note of the version of items being updated and abort if the version of any item being updated by it has changed during commit. Version check and commit are still two separate steps and there might be race conditions. One way to prevent race condition during version check and commit phase is to use locks. The locks are held for a much shorter duration, so this will be much better than holding the locks during the entire transaction. Another way is to use operations such as put-if-absent provided by the platform. The file/key name can contain the version number. Writers will try to create a file/key with the current version + 1. Only one of the writers will succeed.

Following is an example that illustrates what happens when two writers try to update the same item:

Atomicity

It is desirable to have all or none of the effects of a transaction to be in place. This is what atomicity is about. For example, if we transfer money from account A to account B, we will deduct money from account A and deposit money into account B. We do not want only one of the two actions to happen. It is ok that none of the actions in a transaction are executed. In this case, we can retry the transaction. One of the important properties of transactions is that they can be aborted halfway and retried. This property can be used to address a lot of problems, such as deadlocks, in transaction processing.

A transaction can make a lot of changes over a long interval. It seems challenging to have atomic behavior. The idea is to utilize some existing atomic mechanism. In transaction processing, this is typically achieved by writing a commit record to log file. The commit record can fit into a single disk block and writing a disk block can be regarded as atomic. A transaction can log as many changes as necessary before writing the commit record. The existence of the commit record in the log marks the completion of the transaction. The concurrency control mechanism we introduced earlier will make sure in-progress changes of a transaction will not be visible to others so we can pretend they do not exist until the commit record is written.

Note some cleanup mechanisms also need to be in place to remove the changes by failed transaction/job since they will waste some space. The details about this process can be found in the classic Aries paper.

Log Structured Merge Tree

Sequentially I/O has better throughput on both HDD and SDD compared to random I/O. **Log structured merge tree (LSM) is a technique that avoids in place update and turns all write operations into append operations and sequential I/Os. We can think of LSM as a sequential log that we keep appending to. If we add an index to point keys to their most recent record in the log, we will have a key value store. The caveat is that out-of-date versions of records will exist, and the log can grow without bound. Having multiple versions is useful for MVCC and can enable us to read values at a past timepoint, but we need to mechanism to clean up old versions** and keep the number of versions under control.

RocksDB

LSM implementation in storage systems became popular in the industry after Google published Bigtable paper. The Bigtable storage engine was open sourced as Level DB and later forked into Rocks DB by Facebook.

In Rocks DB, updates are added to an in-memory buffer (memtable), which is usually held as a tree to preserve key-ordering. Updates are also recorded in a write-ahead-log on disk for recovery purposes. When the in-memory buffer is full, the content is packed into a new file on disk. Files on disk are immutable. This process repeats as more writes come in.

Multiple versions of a key can exist in multiple files and in memory buffer due to the way write is implemented. During read time, we will need to look at all the files on disk and the in-memory buffer. Statistics information and bloom filter in the files are crucial to help reduce the number of files we need to check. In addition, there is a background compaction process to merge files to keep the number of files under control. During compaction we can also cleanup versions we do not need anymore.

Compaction will write data from existing files again to some new files and this is another source for write amplification. Leveled storage is one way to combat this. The files are grouped into levels. Data in each level (except for level 0) is partitioned into many files so a single record can only exist in one file at one level. Files at each level are many times larger than the previous level. Compaction into level N merges data from level N-1 into level N. The number of levels is limited since the file size at each level grows exponentially. Hence write/read/space amplifications are limited.

Following is architecture of RocksDB:

The SST file is a sealed sequential file divided into blocks with index and metadata:

<beginning_of_file>
[data block 1]
[data block 2]
…
[data block N]
[meta block 1: filter block] (see section: “filter” Meta Block)
[meta block 2: index block]
[meta block 3: compression dictionary block] (see section: “compression dictionary” Meta Block)
[meta block 4: range deletion block] (see section: “range deletion” Meta Block)
[meta block 5: stats block] (see section: “properties” Meta Block)
…
[meta block K: future extended block] (we may add more meta blocks in the future)
[metaindex block]
[Footer] (fixed size; starts at file_size — sizeof(Footer))<end_of_file>

Copy-on-Write

Copy-on-write was one of the oldest mechanisms for concurrency control. The idea is to make a copy of the previous version and create an updated version (there will be optimization to copy only the necessary parts.) Naturally, writers will not interfere with readers. Writers can use optimistic currency control to detect conflicts. CouchDB was a storage system that uses this:

The diagram above what happens we update a record. All the nodes along the path from the root to the record are copied. Copy-on-write seems expensive, but it is used in many places (for example, Git, Blockchain.)

Five Minutes Rules

The five-minute rule explores the trade-off between the cost of DRAM and the cost of disk I/O. Given that caching pages in memory reduces the number of disk I/Os, the five-minute rule provides a formula to predict the optimal break-even interval–the time window within which data must be re-accessed for it to qualified for being cached in memory. The interval is computed as:

Breakeven Interval in Seconds = (Pages Per MB of RAM / Accesses Per Second Per Disk) × (Price Per Disk Drive / Price Per MB of RAM)

The intuitive way to understand this rule is that if we have pages that are accessed at intervals longer than the breakeven interval, it will be cheaper to store than on disk.

Prices and bandwidth of various kinds of media changed dramatically over time, so the old five- minute rule does not apply directly anymore. But the principle is still useful.

Today, storage systems typically use a four-tier storage hierarchy:

The online layer is for latency sensitive case and the near/offline is for latency insensitive case. If we apply the rule to recent hardware, it seems to suggest an inevitable shift from DRAM-based data management engines to solid-state-storage-based persistent-memory engines.

For latency-insensitive nature of batch analytics, it might be economically beneficial to merge the conventional capacity and archival tiers into a single Cold Storage Tier based on tape/CSD (CSD is a Massive Array of Idle Disks in which only a small subset of HDDs is spun up and active at any given time).

Further Readings

1. Database System Concepts
2. Designing Data-Intensive Applications
3. Amazon — Database Systems: The Complete Book
4. The Internals of PostgreSQL : Introduction (interdb.jp)
5. Principles of Transaction Processing
6. Transaction Processing: Management of the Logical Database and its Underlying Physical Structure
7. Transaction Processing: Concepts and Techniques
8. Streaming Systems: The What, Where, When, and How of Large-Scale Data Processing
9. CSEP 545 Lectures Archive (washington.edu)