admin-guide/device-mapper/vdo-design.rst

1 .. SPDX-License-Identifier: GPL-2.0-only
4 Design of dm-vdo
7 The dm-vdo (virtual data optimizer) target provides inline deduplication,
8 compression, zero-block elimination, and thin provisioning. A dm-vdo target
9 can be backed by up to 256TB of storage, and can present a logical size of
12 production environments ever since. It was made open-source in 2017 after
14 dm-vdo. For usage, see vdo.rst in the same directory as this file.
19 reference a single 4K of actual storage. It can achieve compression rates
20 of 14:1. All zero blocks consume no storage at all.
25 The design of dm-vdo is based on the idea that deduplication is a two-part
27 storing multiple copies of those duplicates. Therefore, dm-vdo has two main
30 maps from logical block addresses to the actual storage location of the
34 -------------------
41 design attempts to be lock-free.
43 Most of a vdo's main data structures are designed to be easily divided into
59 reflected in the on-disk representation of each data structure. Therefore,
64 -----------------------
78 ultimate goal of deduplication is to reduce storage costs. Since there is a
79 trade-off between the storage saved and the resources expended to achieve
83 Each block of data is hashed to produce a 16-byte block name. An index
85 that data on the underlying storage. However, it is not possible to
87 because it is too costly to update the index when a block is over-written
89 with the blocks, which is difficult to do efficiently in block-based
90 storage, or reading and rehashing each block before overwriting it.
112 without having to load the entire chapter from storage. This index uses
116 chapters are read-only structures and their contents are never altered in
135 in memory and is saved to storage only when the vdo target is shut down.
149 memory-efficient structure called a delta index. Instead of storing the
160 splitting its key space into many sub-lists, each starting at a fixed key
183 the amount of backing storage required. Doubling the size of the index will
185 the storage size and the memory requirements.
189 increasing the storage size by a factor of 10. However with sparse
190 indexing, the memory requirements do not increase. The trade-off is
193 duplicate data, sparse indexing will detect 97-99% of the deduplication
197 -------------------------------
200 fields and data to track vdo-specific information. A struct vio maintains a
221 --------------
223 The data store is implemented by three main data structures, all of which
239 requests they do so in order to allow the main recovery journal (see below)
240 to free up space. The slab journal is used both to ensure that the main
243 memory and are written out, a block at a time in oldest-dirtied-order, only
249 zones" in round-robin fashion. If there are P physical zones, then slab n
256 reference count updates have been persisted to storage, and approximately
283 0-811 belong to tree 0, logical addresses 812-1623 belong to tree 1, and so
286 for a large number of possible logical zone counts. The storage for the 60
289 need to pre-allocate space for the entire set of logical mappings and also
296 time, and is large enough to hold all the non-leaf pages of the entire
312 new block mappings in that block are stable on storage, and journal block
326 requires data to be stable on storage, it must issue a flush or write the
369     missing, it is allocated at this time out of the same physical storage
372     a. If any page-node in the tree has not yet been allocated, it must be
374        data_vio to lock the page-node that needs to be allocated. This
391     b. In the steady-state case, the block map tree nodes will already be
416     sub-component of the slab and are thus also covered by the implicit
549     and flushed to ensure the transaction is stable on storage.
565     logical-to-physical mapping in the block map to point to the new
589 logical-to-physical mapping by traversing the block map tree as in step 3,
600 All storage within vdo is managed as 4KB blocks, but it can accept writes
602 a read-modify-write operation that reads the relevant 4K block, copies the
611 recovery journal. During the pre-resume phase of the next start, the
620 *Read-only Rebuild*
622 If a vdo encounters an unrecoverable error, it will enter read-only mode.
626 to the possibility that data has been lost. During a read-only rebuild, the