.. SPDX-License-Identifier: GPL-2.0-only

================
Design of dm-vdo
================

The dm-vdo (virtual data optimizer) target provides inline deduplication,
compression, zero-block elimination, and thin provisioning. A dm-vdo target
can be backed by up to 256TB of storage, and can present a logical size of
up to 4PB. This target was originally developed at Permabit Technology
Corp. starting in 2009. It was first released in 2013 and has been used in
production environments ever since. It was made open-source in 2017 after
Permabit was acquired by Red Hat. This document describes the design of
dm-vdo. For usage, see vdo.rst in the same directory as this file.

Because deduplication rates fall drastically as the block size increases, a
vdo target has a maximum block size of 4K. However, it can achieve
deduplication rates of 254:1, i.e. up to 254 copies of a given 4K block can
reference a single 4K of actual storage. It can achieve compression rates
of 14:1. All zero blocks consume no storage at all.

Theory of Operation
===================

The design of dm-vdo is based on the idea that deduplication is a two-part
problem. The first is to recognize duplicate data. The second is to avoid
storing multiple copies of those duplicates. Therefore, dm-vdo has two main
parts: a deduplication index (called UDS) that is used to discover
duplicate data, and a data store with a reference counted block map that
maps from logical block addresses to the actual storage location of the
data.

Zones and Threading
-------------------

Due to the complexity of data optimization, the number of metadata
structures involved in a single write operation to a vdo target is larger
than most other targets. Furthermore, because vdo must operate on small
block sizes in order to achieve good deduplication rates, acceptable
performance can only be achieved through parallelism. Therefore, vdo's
design attempts to be lock-free.

Most of a vdo's main data structures are designed to be easily divided into
"zones" such that any given bio must only access a single zone of any zoned
structure. Safety with minimal locking is achieved by ensuring that during
normal operation, each zone is assigned to a specific thread, and only that
thread will access the portion of the data structure in that zone.
Associated with each thread is a work queue. Each bio is associated with a
request object (the "data_vio") which will be added to a work queue when
the next phase of its operation requires access to the structures in the
zone associated with that queue.

Another way of thinking about this arrangement is that the work queue for
each zone has an implicit lock on the structures it manages for all its
operations, because vdo guarantees that no other thread will alter those
structures.

Although each structure is divided into zones, this division is not
reflected in the on-disk representation of each data structure. Therefore,
the number of zones for each structure, and hence the number of threads,
can be reconfigured each time a vdo target is started.

The Deduplication Index
-----------------------

In order to identify duplicate data efficiently, vdo was designed to
leverage some common characteristics of duplicate data. From empirical
observations, we gathered two key insights. The first is that in most data
sets with significant amounts of duplicate data, the duplicates tend to
have temporal locality. When a duplicate appears, it is more likely that
other duplicates will be detected, and that those duplicates will have been
written at about the same time. This is why the index keeps records in
temporal order. The second insight is that new data is more likely to
duplicate recent data than it is to duplicate older data and in general,
there are diminishing returns to looking further back in time. Therefore,
when the index is full, it should cull its oldest records to make space for
new ones. Another important idea behind the design of the index is that the
ultimate goal of deduplication is to reduce storage costs. Since there is a
trade-off between the storage saved and the resources expended to achieve
those savings, vdo does not attempt to find every last duplicate block. It
is sufficient to find and eliminate most of the redundancy.

Each block of data is hashed to produce a 16-byte block name. An index
record consists of this block name paired with the presumed location of
that data on the underlying storage. However, it is not possible to
guarantee that the index is accurate. In the most common case, this occurs
because it is too costly to update the index when a block is over-written
or discarded. Doing so would require either storing the block name along
with the blocks, which is difficult to do efficiently in block-based
storage, or reading and rehashing each block before overwriting it.
Inaccuracy can also result from a hash collision where two different blocks
have the same name. In practice, this is extremely unlikely, but because
vdo does not use a cryptographic hash, a malicious workload could be
constructed. Because of these inaccuracies, vdo treats the locations in the
index as hints, and reads each indicated block to verify that it is indeed
a duplicate before sharing the existing block with a new one.

Records are collected into groups called chapters. New records are added to
the newest chapter, called the open chapter. This chapter is stored in a
format optimized for adding and modifying records, and the content of the
open chapter is not finalized until it runs out of space for new records.
When the open chapter fills up, it is closed and a new open chapter is
created to collect new records.

Closing a chapter converts it to a different format which is optimized for
reading. The records are written to a series of record pages based on the
order in which they were received. This means that records with temporal
locality should be on a small number of pages, reducing the I/O required to
retrieve them. The chapter also compiles an index that indicates which
record page contains any given name. This index means that a request for a
name can determine exactly which record page may contain that record,
without having to load the entire chapter from storage. This index uses
only a subset of the block name as its key, so it cannot guarantee that an
index entry refers to the desired block name. It can only guarantee that if
there is a record for this name, it will be on the indicated page. Closed
chapters are read-only structures and their contents are never altered in
any way.

Once enough records have been written to fill up all the available index
space, the oldest chapter is removed to make space for new chapters. Any
time a request finds a matching record in the index, that record is copied
into the open chapter. This ensures that useful block names remain available
in the index, while unreferenced block names are forgotten over time.

In order to find records in older chapters, the index also maintains a
higher level structure called the volume index, which contains entries
mapping each block name to the chapter containing its newest record. This
mapping is updated as records for the block name are copied or updated,
ensuring that only the newest record for a given block name can be found.
An older record for a block name will no longer be found even though it has
not been deleted from its chapter. Like the chapter index, the volume index
uses only a subset of the block name as its key and can not definitively
say that a record exists for a name. It can only say which chapter would
contain the record if a record exists. The volume index is stored entirely
in memory and is saved to storage only when the vdo target is shut down.

From the viewpoint of a request for a particular block name, it will first
look up the name in the volume index. This search will either indicate that
the name is new, or which chapter to search. If it returns a chapter, the
request looks up its name in the chapter index. This will indicate either
that the name is new, or which record page to search. Finally, if it is not
new, the request will look for its name in the indicated record page.
This process may require up to two page reads per request (one for the
chapter index page and one for the request page). However, recently
accessed pages are cached so that these page reads can be amortized across
many block name requests.

The volume index and the chapter indexes are implemented using a
memory-efficient structure called a delta index. Instead of storing the
entire block name (the key) for each entry, the entries are sorted by name
and only the difference between adjacent keys (the delta) is stored.
Because we expect the hashes to be randomly distributed, the size of the
deltas follows an exponential distribution. Because of this distribution,
the deltas are expressed using a Huffman code to take up even less space.
The entire sorted list of keys is called a delta list. This structure
allows the index to use many fewer bytes per entry than a traditional hash
table, but it is slightly more expensive to look up entries, because a
request must read every entry in a delta list to add up the deltas in order
to find the record it needs. The delta index reduces this lookup cost by
splitting its key space into many sub-lists, each starting at a fixed key
value, so that each individual list is short.

The default index size can hold 64 million records, corresponding to about
256GB of data. This means that the index can identify duplicate data if the
original data was written within the last 256GB of writes. This range is
called the deduplication window. If new writes duplicate data that is older
than that, the index will not be able to find it because the records of the
older data have been removed. This means that if an application writes a
200 GB file to a vdo target and then immediately writes it again, the two
copies will deduplicate perfectly. Doing the same with a 500 GB file will
result in no deduplication, because the beginning of the file will no
longer be in the index by the time the second write begins (assuming there
is no duplication within the file itself).

If an application anticipates a data workload that will see useful
deduplication beyond the 256GB threshold, vdo can be configured to use a
larger index with a correspondingly larger deduplication window. (This
configuration can only be set when the target is created, not altered
later. It is important to consider the expected workload for a vdo target
before configuring it.)  There are two ways to do this.

One way is to increase the memory size of the index, which also increases
the amount of backing storage required. Doubling the size of the index will
double the length of the deduplication window at the expense of doubling
the storage size and the memory requirements.

The other option is to enable sparse indexing. Sparse indexing increases
the deduplication window by a factor of 10, at the expense of also
increasing the storage size by a factor of 10. However with sparse
indexing, the memory requirements do not increase. The trade-off is
slightly more computation per request and a slight decrease in the amount
of deduplication detected. For most workloads with significant amounts of
duplicate data, sparse indexing will detect 97-99% of the deduplication
that a standard index will detect.

The vio and data_vio Structures
-------------------------------

A vio (short for Vdo I/O) is conceptually similar to a bio, with additional
fields and data to track vdo-specific information. A struct vio maintains a
pointer to a bio but also tracks other fields specific to the operation of
vdo. The vio is kept separate from its related bio because there are many
circumstances where vdo completes the bio but must continue to do work
related to deduplication or compression.

Metadata reads and writes, and other writes that originate within vdo, use
a struct vio directly. Application reads and writes use a larger structure
called a data_vio to track information about their progress. A struct
data_vio contain a struct vio and also includes several other fields
related to deduplication and other vdo features. The data_vio is the
primary unit of application work in vdo. Each data_vio proceeds through a
set of steps to handle the application data, after which it is reset and
returned to a pool of data_vios for reuse.

There is a fixed pool of 2048 data_vios. This number was chosen to bound
the amount of work that is required to recover from a crash. In addition,
benchmarks have indicated that increasing the size of the pool does not
significantly improve performance.

The Data Store
--------------

The data store is implemented by three main data structures, all of which
work in concert to reduce or amortize metadata updates across as many data
writes as possible.

*The Slab Depot*

Most of the vdo volume belongs to the slab depot. The depot contains a
collection of slabs. The slabs can be up to 32GB, and are divided into
three sections. Most of a slab consists of a linear sequence of 4K blocks.
These blocks are used either to store data, or to hold portions of the
block map (see below). In addition to the data blocks, each slab has a set
of reference counters, using 1 byte for each data block. Finally each slab
has a journal.

Reference updates are written to the slab journal. Slab journal blocks are
written out either when they are full, or when the recovery journal
requests they do so in order to allow the main recovery journal (see below)
to free up space. The slab journal is used both to ensure that the main
recovery journal can regularly free up space, and also to amortize the cost
of updating individual reference blocks. The reference counters are kept in
memory and are written out, a block at a time in oldest-dirtied-order, only
when there is a need to reclaim slab journal space. The write operations
are performed in the background as needed so they do not add latency to
particular I/O operations.

Each slab is independent of every other. They are assigned to "physical
zones" in round-robin fashion. If there are P physical zones, then slab n
is assigned to zone n mod P.

The slab depot maintains an additional small data structure, the "slab
summary," whic                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      