Lines Matching +full:step +full:- +full:size
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.
16 Because deduplication rates fall drastically as the block size increases, a
17 vdo target has a maximum block size of 4K. However, it can achieve
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.
59 reflected in the on-disk representation of each data structure. Therefore,
64 -----------------------
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
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
152 Because we expect the hashes to be randomly distributed, the size of the
160 splitting its key space into many sub-lists, each starting at a fixed key
163 The default index size can hold 64 million records, corresponding to about
182 One way is to increase the memory size of the index, which also increases
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
217 benchmarks have indicated that increasing the size of the pool does not
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
290 makes growing the logical size of a vdo relatively easy.
294 maintains its own cache of leaf pages. The size of this cache is
296 time, and is large enough to hold all the non-leaf pages of the entire
358 compression packer (step 8d) rather than allowing it to continue
372 a. If any page-node in the tree has not yet been allocated, it must be
373 allocated before the write can continue. This step requires the
374 data_vio to lock the page-node that needs to be allocated. This
375 lock, like the logical block lock in step 2, is a hashtable entry
382 step 4. Once a new node has been allocated, that node is added to
385 map tree (step 10), updates the reference count of the new block
386 (step 11), and reacquires the implicit logical zone lock to add the
387 new mapping to the parent tree node (step 12). Once the tree is
391 b. In the steady-state case, the block map tree nodes will already be
398 4. If the block is a zero block, skip to step 9. Otherwise, an attempt is
412 added to a hashtable like the logical block locks in step 2. This
416 sub-component of the slab and are thus also covered by the implicit
436 tracked in step 2. This hashtable is covered by the implicit lock on
451 step 8h and attempts to write its data directly. This can happen if two
473 physical block as their new physical address and proceed to step 9
476 data_vios becomes the new agent and continues to step 8d as if no
480 it has an allocated physical block (from step 3) that it can write
484 are out of space, so they proceed to step 13 for cleanup.
487 compress, the data_vio will continue to step 8h to write its data
490 If the compressed size is small enough, the agent will release the
507 data_vio will proceed to step 8h to write its data directly.
511 using the allocated physical block from one of its data_vios. Step
518 zone lock and proceeds to step 8i.
521 step 3. It will write its data to that allocated physical block.
526 possible. Each data_vio will then proceed to step 9 to record its
540 physical mapping"), if any, and records it. This step requires a lock
565 logical-to-physical mapping in the block map to point to the new
577 the logical block lock acquired in step 2.
589 logical-to-physical mapping by traversing the block map tree as in step 3,
595 acknowledgment as in step 13, although it only needs to release the logical
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