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
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.
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
34 -------------------
41 design attempts to be lock-free.
46 normal operation, each zone is assigned to a specific thread, and only that
59 reflected in the on-disk representation of each data structure. Therefore,
64 -----------------------
70 have temporal locality. When a duplicate appears, it is more likely that
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
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
108 locality should be on a small number of pages, reducing the I/O required to
116 chapters are read-only structures and their contents are never altered in
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
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
201 pointer to a bio but also tracks other fields specific to the operation of
221 --------------
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
283 0-811 belong to tree 0, logical addresses 812-1623 belong to tree 1, and so
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
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
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,
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