634 lines · plain
1.. SPDX-License-Identifier: GPL-2.0-only2 3================4Design of dm-vdo5================6 7The dm-vdo (virtual data optimizer) target provides inline deduplication,8compression, zero-block elimination, and thin provisioning. A dm-vdo target9can be backed by up to 256TB of storage, and can present a logical size of10up to 4PB. This target was originally developed at Permabit Technology11Corp. starting in 2009. It was first released in 2013 and has been used in12production environments ever since. It was made open-source in 2017 after13Permabit was acquired by Red Hat. This document describes the design of14dm-vdo. For usage, see vdo.rst in the same directory as this file.15 16Because deduplication rates fall drastically as the block size increases, a17vdo target has a maximum block size of 4K. However, it can achieve18deduplication rates of 254:1, i.e. up to 254 copies of a given 4K block can19reference a single 4K of actual storage. It can achieve compression rates20of 14:1. All zero blocks consume no storage at all.21 22Theory of Operation23===================24 25The design of dm-vdo is based on the idea that deduplication is a two-part26problem. The first is to recognize duplicate data. The second is to avoid27storing multiple copies of those duplicates. Therefore, dm-vdo has two main28parts: a deduplication index (called UDS) that is used to discover29duplicate data, and a data store with a reference counted block map that30maps from logical block addresses to the actual storage location of the31data.32 33Zones and Threading34-------------------35 36Due to the complexity of data optimization, the number of metadata37structures involved in a single write operation to a vdo target is larger38than most other targets. Furthermore, because vdo must operate on small39block sizes in order to achieve good deduplication rates, acceptable40performance can only be achieved through parallelism. Therefore, vdo's41design attempts to be lock-free.42 43Most of a vdo's main data structures are designed to be easily divided into44"zones" such that any given bio must only access a single zone of any zoned45structure. Safety with minimal locking is achieved by ensuring that during46normal operation, each zone is assigned to a specific thread, and only that47thread will access the portion of the data structure in that zone.48Associated with each thread is a work queue. Each bio is associated with a49request object (the "data_vio") which will be added to a work queue when50the next phase of its operation requires access to the structures in the51zone associated with that queue.52 53Another way of thinking about this arrangement is that the work queue for54each zone has an implicit lock on the structures it manages for all its55operations, because vdo guarantees that no other thread will alter those56structures.57 58Although each structure is divided into zones, this division is not59reflected in the on-disk representation of each data structure. Therefore,60the number of zones for each structure, and hence the number of threads,61can be reconfigured each time a vdo target is started.62 63The Deduplication Index64-----------------------65 66In order to identify duplicate data efficiently, vdo was designed to67leverage some common characteristics of duplicate data. From empirical68observations, we gathered two key insights. The first is that in most data69sets with significant amounts of duplicate data, the duplicates tend to70have temporal locality. When a duplicate appears, it is more likely that71other duplicates will be detected, and that those duplicates will have been72written at about the same time. This is why the index keeps records in73temporal order. The second insight is that new data is more likely to74duplicate recent data than it is to duplicate older data and in general,75there are diminishing returns to looking further back in time. Therefore,76when the index is full, it should cull its oldest records to make space for77new ones. Another important idea behind the design of the index is that the78ultimate goal of deduplication is to reduce storage costs. Since there is a79trade-off between the storage saved and the resources expended to achieve80those savings, vdo does not attempt to find every last duplicate block. It81is sufficient to find and eliminate most of the redundancy.82 83Each block of data is hashed to produce a 16-byte block name. An index84record consists of this block name paired with the presumed location of85that data on the underlying storage. However, it is not possible to86guarantee that the index is accurate. In the most common case, this occurs87because it is too costly to update the index when a block is over-written88or discarded. Doing so would require either storing the block name along89with the blocks, which is difficult to do efficiently in block-based90storage, or reading and rehashing each block before overwriting it.91Inaccuracy can also result from a hash collision where two different blocks92have the same name. In practice, this is extremely unlikely, but because93vdo does not use a cryptographic hash, a malicious workload could be94constructed. Because of these inaccuracies, vdo treats the locations in the95index as hints, and reads each indicated block to verify that it is indeed96a duplicate before sharing the existing block with a new one.97 98Records are collected into groups called chapters. New records are added to99the newest chapter, called the open chapter. This chapter is stored in a100format optimized for adding and modifying records, and the content of the101open chapter is not finalized until it runs out of space for new records.102When the open chapter fills up, it is closed and a new open chapter is103created to collect new records.104 105Closing a chapter converts it to a different format which is optimized for106reading. The records are written to a series of record pages based on the107order in which they were received. This means that records with temporal108locality should be on a small number of pages, reducing the I/O required to109retrieve them. The chapter also compiles an index that indicates which110record page contains any given name. This index means that a request for a111name can determine exactly which record page may contain that record,112without having to load the entire chapter from storage. This index uses113only a subset of the block name as its key, so it cannot guarantee that an114index entry refers to the desired block name. It can only guarantee that if115there is a record for this name, it will be on the indicated page. Closed116chapters are read-only structures and their contents are never altered in117any way.118 119Once enough records have been written to fill up all the available index120space, the oldest chapter is removed to make space for new chapters. Any121time a request finds a matching record in the index, that record is copied122into the open chapter. This ensures that useful block names remain available123in the index, while unreferenced block names are forgotten over time.124 125In order to find records in older chapters, the index also maintains a126higher level structure called the volume index, which contains entries127mapping each block name to the chapter containing its newest record. This128mapping is updated as records for the block name are copied or updated,129ensuring that only the newest record for a given block name can be found.130An older record for a block name will no longer be found even though it has131not been deleted from its chapter. Like the chapter index, the volume index132uses only a subset of the block name as its key and can not definitively133say that a record exists for a name. It can only say which chapter would134contain the record if a record exists. The volume index is stored entirely135in memory and is saved to storage only when the vdo target is shut down.136 137From the viewpoint of a request for a particular block name, it will first138look up the name in the volume index. This search will either indicate that139the name is new, or which chapter to search. If it returns a chapter, the140request looks up its name in the chapter index. This will indicate either141that the name is new, or which record page to search. Finally, if it is not142new, the request will look for its name in the indicated record page.143This process may require up to two page reads per request (one for the144chapter index page and one for the request page). However, recently145accessed pages are cached so that these page reads can be amortized across146many block name requests.147 148The volume index and the chapter indexes are implemented using a149memory-efficient structure called a delta index. Instead of storing the150entire block name (the key) for each entry, the entries are sorted by name151and only the difference between adjacent keys (the delta) is stored.152Because we expect the hashes to be randomly distributed, the size of the153deltas follows an exponential distribution. Because of this distribution,154the deltas are expressed using a Huffman code to take up even less space.155The entire sorted list of keys is called a delta list. This structure156allows the index to use many fewer bytes per entry than a traditional hash157table, but it is slightly more expensive to look up entries, because a158request must read every entry in a delta list to add up the deltas in order159to find the record it needs. The delta index reduces this lookup cost by160splitting its key space into many sub-lists, each starting at a fixed key161value, so that each individual list is short.162 163The default index size can hold 64 million records, corresponding to about164256GB of data. This means that the index can identify duplicate data if the165original data was written within the last 256GB of writes. This range is166called the deduplication window. If new writes duplicate data that is older167than that, the index will not be able to find it because the records of the168older data have been removed. This means that if an application writes a169200 GB file to a vdo target and then immediately writes it again, the two170copies will deduplicate perfectly. Doing the same with a 500 GB file will171result in no deduplication, because the beginning of the file will no172longer be in the index by the time the second write begins (assuming there173is no duplication within the file itself).174 175If an application anticipates a data workload that will see useful176deduplication beyond the 256GB threshold, vdo can be configured to use a177larger index with a correspondingly larger deduplication window. (This178configuration can only be set when the target is created, not altered179later. It is important to consider the expected workload for a vdo target180before configuring it.) There are two ways to do this.181 182One way is to increase the memory size of the index, which also increases183the amount of backing storage required. Doubling the size of the index will184double the length of the deduplication window at the expense of doubling185the storage size and the memory requirements.186 187The other option is to enable sparse indexing. Sparse indexing increases188the deduplication window by a factor of 10, at the expense of also189increasing the storage size by a factor of 10. However with sparse190indexing, the memory requirements do not increase. The trade-off is191slightly more computation per request and a slight decrease in the amount192of deduplication detected. For most workloads with significant amounts of193duplicate data, sparse indexing will detect 97-99% of the deduplication194that a standard index will detect.195 196The vio and data_vio Structures197-------------------------------198 199A vio (short for Vdo I/O) is conceptually similar to a bio, with additional200fields and data to track vdo-specific information. A struct vio maintains a201pointer to a bio but also tracks other fields specific to the operation of202vdo. The vio is kept separate from its related bio because there are many203circumstances where vdo completes the bio but must continue to do work204related to deduplication or compression.205 206Metadata reads and writes, and other writes that originate within vdo, use207a struct vio directly. Application reads and writes use a larger structure208called a data_vio to track information about their progress. A struct209data_vio contain a struct vio and also includes several other fields210related to deduplication and other vdo features. The data_vio is the211primary unit of application work in vdo. Each data_vio proceeds through a212set of steps to handle the application data, after which it is reset and213returned to a pool of data_vios for reuse.214 215There is a fixed pool of 2048 data_vios. This number was chosen to bound216the amount of work that is required to recover from a crash. In addition,217benchmarks have indicated that increasing the size of the pool does not218significantly improve performance.219 220The Data Store221--------------222 223The data store is implemented by three main data structures, all of which224work in concert to reduce or amortize metadata updates across as many data225writes as possible.226 227*The Slab Depot*228 229Most of the vdo volume belongs to the slab depot. The depot contains a230collection of slabs. The slabs can be up to 32GB, and are divided into231three sections. Most of a slab consists of a linear sequence of 4K blocks.232These blocks are used either to store data, or to hold portions of the233block map (see below). In addition to the data blocks, each slab has a set234of reference counters, using 1 byte for each data block. Finally each slab235has a journal.236 237Reference updates are written to the slab journal. Slab journal blocks are238written out either when they are full, or when the recovery journal239requests they do so in order to allow the main recovery journal (see below)240to free up space. The slab journal is used both to ensure that the main241recovery journal can regularly free up space, and also to amortize the cost242of updating individual reference blocks. The reference counters are kept in243memory and are written out, a block at a time in oldest-dirtied-order, only244when there is a need to reclaim slab journal space. The write operations245are performed in the background as needed so they do not add latency to246particular I/O operations.247 248Each slab is independent of every other. They are assigned to "physical249zones" in round-robin fashion. If there are P physical zones, then slab n250is assigned to zone n mod P.251 252The slab depot maintains an additional small data structure, the "slab253summary," which is used to reduce the amount of work needed to come back254online after a crash. The slab summary maintains an entry for each slab255indicating whether or not the slab has ever been used, whether all of its256reference count updates have been persisted to storage, and approximately257how full it is. During recovery, each physical zone will attempt to recover258at least one slab, stopping whenever it has recovered a slab which has some259free blocks. Once each zone has some space, or has determined that none is260available, the target can resume normal operation in a degraded mode. Read261and write requests can be serviced, perhaps with degraded performance,262while the remainder of the dirty slabs are recovered.263 264*The Block Map*265 266The block map contains the logical to physical mapping. It can be thought267of as an array with one entry per logical address. Each entry is 5 bytes,26836 bits of which contain the physical block number which holds the data for269the given logical address. The other 4 bits are used to indicate the nature270of the mapping. Of the 16 possible states, one represents a logical address271which is unmapped (i.e. it has never been written, or has been discarded),272one represents an uncompressed block, and the other 14 states are used to273indicate that the mapped data is compressed, and which of the compression274slots in the compressed block contains the data for this logical address.275 276In practice, the array of mapping entries is divided into "block map277pages," each of which fits in a single 4K block. Each block map page278consists of a header and 812 mapping entries. Each mapping page is actually279a leaf of a radix tree which consists of block map pages at each level.280There are 60 radix trees which are assigned to "logical zones" in round281robin fashion. (If there are L logical zones, tree n will belong to zone n282mod L.) At each level, the trees are interleaved, so logical addresses2830-811 belong to tree 0, logical addresses 812-1623 belong to tree 1, and so284on. The interleaving is maintained all the way up to the 60 root nodes.285Choosing 60 trees results in an evenly distributed number of trees per zone286for a large number of possible logical zone counts. The storage for the 60287tree roots is allocated at format time. All other block map pages are288allocated out of the slabs as needed. This flexible allocation avoids the289need to pre-allocate space for the entire set of logical mappings and also290makes growing the logical size of a vdo relatively easy.291 292In operation, the block map maintains two caches. It is prohibitive to keep293the entire leaf level of the trees in memory, so each logical zone294maintains its own cache of leaf pages. The size of this cache is295configurable at target start time. The second cache is allocated at start296time, and is large enough to hold all the non-leaf pages of the entire297block map. This cache is populated as pages are needed.298 299*The Recovery Journal*300 301The recovery journal is used to amortize updates across the block map and302slab depot. Each write request causes an entry to be made in the journal.303Entries are either "data remappings" or "block map remappings." For a data304remapping, the journal records the logical address affected and its old and305new physical mappings. For a block map remapping, the journal records the306block map page number and the physical block allocated for it. Block map307pages are never reclaimed or repurposed, so the old mapping is always 0.308 309Each journal entry is an intent record summarizing the metadata updates310that are required for a data_vio. The recovery journal issues a flush311before each journal block write to ensure that the physical data for the312new block mappings in that block are stable on storage, and journal block313writes are all issued with the FUA bit set to ensure the recovery journal314entries themselves are stable. The journal entry and the data write it315represents must be stable on disk before the other metadata structures may316be updated to reflect the operation. These entries allow the vdo device to317reconstruct the logical to physical mappings after an unexpected318interruption such as a loss of power.319 320*Write Path*321 322All write I/O to vdo is asynchronous. Each bio will be acknowledged as soon323as vdo has done enough work to guarantee that it can complete the write324eventually. Generally, the data for acknowledged but unflushed write I/O325can be treated as though it is cached in memory. If an application326requires data to be stable on storage, it must issue a flush or write the327data with the FUA bit set like any other asynchronous I/O. Shutting down328the vdo target will also flush any remaining I/O.329 330Application write bios follow the steps outlined below.331 3321. A data_vio is obtained from the data_vio pool and associated with the333 application bio. If there are no data_vios available, the incoming bio334 will block until a data_vio is available. This provides back pressure335 to the application. The data_vio pool is protected by a spin lock.336 337 The newly acquired data_vio is reset and the bio's data is copied into338 the data_vio if it is a write and the data is not all zeroes. The data339 must be copied because the application bio can be acknowledged before340 the data_vio processing is complete, which means later processing steps341 will no longer have access to the application bio. The application bio342 may also be smaller than 4K, in which case the data_vio will have343 already read the underlying block and the data is instead copied over344 the relevant portion of the larger block.345 3462. The data_vio places a claim (the "logical lock") on the logical address347 of the bio. It is vital to prevent simultaneous modifications of the348 same logical address, because deduplication involves sharing blocks.349 This claim is implemented as an entry in a hashtable where the key is350 the logical address and the value is a pointer to the data_vio351 currently handling that address.352 353 If a data_vio looks in the hashtable and finds that another data_vio is354 already operating on that logical address, it waits until the previous355 operation finishes. It also sends a message to inform the current356 lock holder that it is waiting. Most notably, a new data_vio waiting357 for a logical lock will flush the previous lock holder out of the358 compression packer (step 8d) rather than allowing it to continue359 waiting to be packed.360 361 This stage requires the data_vio to get an implicit lock on the362 appropriate logical zone to prevent concurrent modifications of the363 hashtable. This implicit locking is handled by the zone divisions364 described above.365 3663. The data_vio traverses the block map tree to ensure that all the367 necessary internal tree nodes have been allocated, by trying to find368 the leaf page for its logical address. If any interior tree page is369 missing, it is allocated at this time out of the same physical storage370 pool used to store application data.371 372 a. If any page-node in the tree has not yet been allocated, it must be373 allocated before the write can continue. This step requires the374 data_vio to lock the page-node that needs to be allocated. This375 lock, like the logical block lock in step 2, is a hashtable entry376 that causes other data_vios to wait for the allocation process to377 complete.378 379 The implicit logical zone lock is released while the allocation is380 happening, in order to allow other operations in the same logical381 zone to proceed. The details of allocation are the same as in382 step 4. Once a new node has been allocated, that node is added to383 the tree using a similar process to adding a new data block mapping.384 The data_vio journals the intent to add the new node to the block385 map tree (step 10), updates the reference count of the new block386 (step 11), and reacquires the implicit logical zone lock to add the387 new mapping to the parent tree node (step 12). Once the tree is388 updated, the data_vio proceeds down the tree. Any other data_vios389 waiting on this allocation also proceed.390 391 b. In the steady-state case, the block map tree nodes will already be392 allocated, so the data_vio just traverses the tree until it finds393 the required leaf node. The location of the mapping (the "block map394 slot") is recorded in the data_vio so that later steps do not need395 to traverse the tree again. The data_vio then releases the implicit396 logical zone lock.397 3984. If the block is a zero block, skip to step 9. Otherwise, an attempt is399 made to allocate a free data block. This allocation ensures that the400 data_vio can write its data somewhere even if deduplication and401 compression are not possible. This stage gets an implicit lock on a402 physical zone to search for free space within that zone.403 404 The data_vio will search each slab in a zone until it finds a free405 block or decides there are none. If the first zone has no free space,406 it will proceed to search the next physical zone by taking the implicit407 lock for that zone and releasing the previous one until it finds a408 free block or runs out of zones to search. The data_vio will acquire a409 struct pbn_lock (the "physical block lock") on the free block. The410 struct pbn_lock also has several fields to record the various kinds of411 claims that data_vios can have on physical blocks. The pbn_lock is412 added to a hashtable like the logical block locks in step 2. This413 hashtable is also covered by the implicit physical zone lock. The414 reference count of the free block is updated to prevent any other415 data_vio from considering it free. The reference counters are a416 sub-component of the slab and are thus also covered by the implicit417 physical zone lock.418 4195. If an allocation was obtained, the data_vio has all the resources it420 needs to complete the write. The application bio can safely be421 acknowledged at this point. The acknowledgment happens on a separate422 thread to prevent the application callback from blocking other data_vio423 operations.424 425 If an allocation could not be obtained, the data_vio continues to426 attempt to deduplicate or compress the data, but the bio is not427 acknowledged because the vdo device may be out of space.428 4296. At this point vdo must determine where to store the application data.430 The data_vio's data is hashed and the hash (the "record name") is431 recorded in the data_vio.432 4337. The data_vio reserves or joins a struct hash_lock, which manages all of434 the data_vios currently writing the same data. Active hash locks are435 tracked in a hashtable similar to the way logical block locks are436 tracked in step 2. This hashtable is covered by the implicit lock on437 the hash zone.438 439 If there is no existing hash lock for this data_vio's record_name, the440 data_vio obtains a hash lock from the pool, adds it to the hashtable,441 and sets itself as the new hash lock's "agent." The hash_lock pool is442 also covered by the implicit hash zone lock. The hash lock agent will443 do all the work to decide where the application data will be444 written. If a hash lock for the data_vio's record_name already exists,445 and the data_vio's data is the same as the agent's data, the new446 data_vio will wait for the agent to complete its work and then share447 its result.448 449 In the rare case that a hash lock exists for the data_vio's hash but450 the data does not match the hash lock's agent, the data_vio skips to451 step 8h and attempts to write its data directly. This can happen if two452 different data blocks produce the same hash, for example.453 4548. The hash lock agent attempts to deduplicate or compress its data with455 the following steps.456 457 a. The agent initializes and sends its embedded deduplication request458 (struct uds_request) to the deduplication index. This does not459 require the data_vio to get any locks because the index components460 manage their own locking. The data_vio waits until it either gets a461 response from the index or times out.462 463 b. If the deduplication index returns advice, the data_vio attempts to464 obtain a physical block lock on the indicated physical address, in465 order to read the data and verify that it is the same as the466 data_vio's data, and that it can accept more references. If the467 physical address is already locked by another data_vio, the data at468 that address may soon be overwritten so it is not safe to use the469 address for deduplication.470 471 c. If the data matches and the physical block can add references, the472 agent and any other data_vios waiting on it will record this473 physical block as their new physical address and proceed to step 9474 to record their new mapping. If there are more data_vios in the hash475 lock than there are references available, one of the remaining476 data_vios becomes the new agent and continues to step 8d as if no477 valid advice was returned.478 479 d. If no usable duplicate block was found, the agent first checks that480 it has an allocated physical block (from step 3) that it can write481 to. If the agent does not have an allocation, some other data_vio in482 the hash lock that does have an allocation takes over as agent. If483 none of the data_vios have an allocated physical block, these writes484 are out of space, so they proceed to step 13 for cleanup.485 486 e. The agent attempts to compress its data. If the data does not487 compress, the data_vio will continue to step 8h to write its data488 directly.489 490 If the compressed size is small enough, the agent will release the491 implicit hash zone lock and go to the packer (struct packer) where492 it will be placed in a bin (struct packer_bin) along with other493 data_vios. All compression operations require the implicit lock on494 the packer zone.495 496 The packer can combine up to 14 compressed blocks in a single 4k497 data block. Compression is only helpful if vdo can pack at least 2498 data_vios into a single data block. This means that a data_vio may499 wait in the packer for an arbitrarily long time for other data_vios500 to fill out the compressed block. There is a mechanism for vdo to501 evict waiting data_vios when continuing to wait would cause502 problems. Circumstances causing an eviction include an application503 flush, device shutdown, or a subsequent data_vio trying to overwrite504 the same logical block address. A data_vio may also be evicted from505 the packer if it cannot be paired with any other compressed block506 before more compressible blocks need to use its bin. An evicted507 data_vio will proceed to step 8h to write its data directly.508 509 f. If the agent fills a packer bin, either because all 14 of its slots510 are used or because it has no remaining space, it is written out511 using the allocated physical block from one of its data_vios. Step512 8d has already ensured that an allocation is available.513 514 g. Each data_vio sets the compressed block as its new physical address.515 The data_vio obtains an implicit lock on the physical zone and516 acquires the struct pbn_lock for the compressed block, which is517 modified to be a shared lock. Then it releases the implicit physical518 zone lock and proceeds to step 8i.519 520 h. Any data_vio evicted from the packer will have an allocation from521 step 3. It will write its data to that allocated physical block.522 523 i. After the data is written, if the data_vio is the agent of a hash524 lock, it will reacquire the implicit hash zone lock and share its525 physical address with as many other data_vios in the hash lock as526 possible. Each data_vio will then proceed to step 9 to record its527 new mapping.528 529 j. If the agent actually wrote new data (whether compressed or not),530 the deduplication index is updated to reflect the location of the531 new data. The agent then releases the implicit hash zone lock.532 5339. The data_vio determines the previous mapping of the logical address.534 There is a cache for block map leaf pages (the "block map cache"),535 because there are usually too many block map leaf nodes to store536 entirely in memory. If the desired leaf page is not in the cache, the537 data_vio will reserve a slot in the cache and load the desired page538 into it, possibly evicting an older cached page. The data_vio then539 finds the current physical address for this logical address (the "old540 physical mapping"), if any, and records it. This step requires a lock541 on the block map cache structures, covered by the implicit logical zone542 lock.543 54410. The data_vio makes an entry in the recovery journal containing the545 logical block address, the old physical mapping, and the new physical546 mapping. Making this journal entry requires holding the implicit547 recovery journal lock. The data_vio will wait in the journal until all548 recovery blocks up to the one containing its entry have been written549 and flushed to ensure the transaction is stable on storage.550 55111. Once the recovery journal entry is stable, the data_vio makes two slab552 journal entries: an increment entry for the new mapping, and a553 decrement entry for the old mapping. These two operations each require554 holding a lock on the affected physical slab, covered by its implicit555 physical zone lock. For correctness during recovery, the slab journal556 entries in any given slab journal must be in the same order as the557 corresponding recovery journal entries. Therefore, if the two entries558 are in different zones, they are made concurrently, and if they are in559 the same zone, the increment is always made before the decrement in560 order to avoid underflow. After each slab journal entry is made in561 memory, the associated reference count is also updated in memory.562 56312. Once both of the reference count updates are done, the data_vio564 acquires the implicit logical zone lock and updates the565 logical-to-physical mapping in the block map to point to the new566 physical block. At this point the write operation is complete.567 56813. If the data_vio has a hash lock, it acquires the implicit hash zone569 lock and releases its hash lock to the pool.570 571 The data_vio then acquires the implicit physical zone lock and releases572 the struct pbn_lock it holds for its allocated block. If it had an573 allocation that it did not use, it also sets the reference count for574 that block back to zero to free it for use by subsequent data_vios.575 576 The data_vio then acquires the implicit logical zone lock and releases577 the logical block lock acquired in step 2.578 579 The application bio is then acknowledged if it has not previously been580 acknowledged, and the data_vio is returned to the pool.581 582*Read Path*583 584An application read bio follows a much simpler set of steps. It does steps5851 and 2 in the write path to obtain a data_vio and lock its logical586address. If there is already a write data_vio in progress for that logical587address that is guaranteed to complete, the read data_vio will copy the588data from the write data_vio and return it. Otherwise, it will look up the589logical-to-physical mapping by traversing the block map tree as in step 3,590and then read and possibly decompress the indicated data at the indicated591physical block address. A read data_vio will not allocate block map tree592nodes if they are missing. If the interior block map nodes do not exist593yet, the logical block map address must still be unmapped and the read594data_vio will return all zeroes. A read data_vio handles cleanup and595acknowledgment as in step 13, although it only needs to release the logical596lock and return itself to the pool.597 598*Small Writes*599 600All storage within vdo is managed as 4KB blocks, but it can accept writes601as small as 512 bytes. Processing a write that is smaller than 4K requires602a read-modify-write operation that reads the relevant 4K block, copies the603new data over the approriate sectors of the block, and then launches a604write operation for the modified data block. The read and write stages of605this operation are nearly identical to the normal read and write606operations, and a single data_vio is used throughout this operation.607 608*Recovery*609 610When a vdo is restarted after a crash, it will attempt to recover from the611recovery journal. During the pre-resume phase of the next start, the612recovery journal is read. The increment portion of valid entries are played613into the block map. Next, valid entries are played, in order as required,614into the slab journals. Finally, each physical zone attempts to replay at615least one slab journal to reconstruct the reference counts of one slab.616Once each zone has some free space (or has determined that it has none),617the vdo comes back online, while the remainder of the slab journals are618used to reconstruct the rest of the reference counts in the background.619 620*Read-only Rebuild*621 622If a vdo encounters an unrecoverable error, it will enter read-only mode.623This mode indicates that some previously acknowledged data may have been624lost. The vdo may be instructed to rebuild as best it can in order to625return to a writable state. However, this is never done automatically due626to the possibility that data has been lost. During a read-only rebuild, the627block map is recovered from the recovery journal as before. However, the628reference counts are not rebuilt from the slab journals. Instead, the629reference counts are zeroed, the entire block map is traversed, and the630reference counts are updated from the block mappings. While this may lose631some data, it ensures that the block map and reference counts are632consistent with each other. This allows vdo to resume normal operation and633accept further writes.634