요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
Data store
vdo-design.rst:196-319data_vio와 zone queue, slab depot, 60개 radix tree block map, FUA recovery journal의 역할을 연결해 설명합니다.
I/O and recovery
vdo-design.rst:320-63313단계 asynchronous write path, read와 small-write 처리, crash recovery 및 명시적 read-only rebuild를 추적합니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
.. 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," which is used to reduce the amount of work needed to come back
online after a crash. The slab summary maintains an entry for each slab
indicating whether or not the slab has ever been used, whether all of its
reference count updates have been persisted to storage, and approximately
how full it is. During recovery, each physical zone will attempt to recover
at least one slab, stopping whenever it has recovered a slab which has some
free blocks. Once each zone has some space, or has determined that none is
available, the target can resume normal operation in a degraded mode. Read
and write requests can be serviced, perhaps with degraded performance,
while the remainder of the dirty slabs are recovered.
*The Block Map*
The block map contains the logical to physical mapping. It can be thought
of as an array with one entry per logical address. Each entry is 5 bytes,
36 bits of which contain the physical block number which holds the data for
the given logical address. The other 4 bits are used to indicate the nature
of the mapping. Of the 16 possible states, one represents a logical address
which is unmapped (i.e. it has never been written, or has been discarded),
one represents an uncompressed block, and the other 14 states are used to
indicate that the mapped data is compressed, and which of the compression
slots in the compressed block contains the data for this logical address.
In practice, the array of mapping entries is divided into "block map
pages," each of which fits in a single 4K block. Each block map page
consists of a header and 812 mapping entries. Each mapping page is actually
a leaf of a radix tree which consists of block map pages at each level.
There are 60 radix trees which are assigned to "logical zones" in round
robin fashion. (If there are L logical zones, tree n will belong to zone n
mod L.) At each level, the trees are interleaved, so logical addresses
0-811 belong to tree 0, logical addresses 812-1623 belong to tree 1, and so
on. The interleaving is maintained all the way up to the 60 root nodes.
Choosing 60 trees results in an evenly distributed number of trees per zone
for a large number of possible logical zone counts. The storage for the 60
tree roots is allocated at format time. All other block map pages are
allocated out of the slabs as needed. This flexible allocation avoids the
need to pre-allocate space for the entire set of logical mappings and also
makes growing the logical size of a vdo relatively easy.
In operation, the block map maintains two caches. It is prohibitive to keep
the entire leaf level of the trees in memory, so each logical zone
maintains its own cache of leaf pages. The size of this cache is
configurable at target start time. The second cache is allocated at start
time, and is large enough to hold all the non-leaf pages of the entire
block map. This cache is populated as pages are needed.
*The Recovery Journal*
The recovery journal is used to amortize updates across the block map and
slab depot. Each write request causes an entry to be made in the journal.
Entries are either "data remappings" or "block map remappings." For a data
remapping, the journal records the logical address affected and its old and
new physical mappings. For a block map remapping, the journal records the
block map page number and the physical block allocated for it. Block map
pages are never reclaimed or repurposed, so the old mapping is always 0.
Each journal entry is an intent record summarizing the metadata updates
that are required for a data_vio. The recovery journal issues a flush
before each journal block write to ensure that the physical data for the
new block mappings in that block are stable on storage, and journal block
writes are all issued with the FUA bit set to ensure the recovery journal
entries themselves are stable. The journal entry and the data write it
represents must be stable on disk before the other metadata structures may
be updated to reflect the operation. These entries allow the vdo device to
reconstruct the logical to physical mappings after an unexpected
interruption such as a loss of power.
*Write Path*
All write I/O to vdo is asynchronous. Each bio will be acknowledged as soon
as vdo has done enough work to guarantee that it can complete the write
eventually. Generally, the data for acknowledged but unflushed write I/O
can be treated as though it is cached in memory. If an application
requires data to be stable on storage, it must issue a flush or write the
data with the FUA bit set like any other asynchronous I/O. Shutting down
the vdo target will also flush any remaining I/O.
Application write bios follow the steps outlined below.
1. A data_vio is obtained from the data_vio pool and associated with the
application bio. If there are no data_vios available, the incoming bio
will block until a data_vio is available. This provides back pressure
to the application. The data_vio pool is protected by a spin lock.
The newly acquired data_vio is reset and the bio's data is copied into
the data_vio if it is a write and the data is not all zeroes. The data
must be copied because the application bio can be acknowledged before
the data_vio processing is complete, which means later processing steps
will no longer have access to the application bio. The application bio
may also be smaller than 4K, in which case the data_vio will have
already read the underlying block and the data is instead copied over
the relevant portion of the larger block.
2. The data_vio places a claim (the "logical lock") on the logical address
of the bio. It is vital to prevent simultaneous modifications of the
same logical address, because deduplication involves sharing blocks.
This claim is implemented as an entry in a hashtable where the key is
the logical address and the value is a pointer to the data_vio
currently handling that address.
If a data_vio looks in the hashtable and finds that another data_vio is
already operating on that logical address, it waits until the previous
operation finishes. It also sends a message to inform the current
lock holder that it is waiting. Most notably, a new data_vio waiting
for a logical lock will flush the previous lock holder out of the
compression packer (step 8d) rather than allowing it to continue
waiting to be packed.
This stage requires the data_vio to get an implicit lock on the
appropriate logical zone to prevent concurrent modifications of the
hashtable. This implicit locking is handled by the zone divisions
described above.
3. The data_vio traverses the block map tree to ensure that all the
necessary internal tree nodes have been allocated, by trying to find
the leaf page for its logical address. If any interior tree page is
missing, it is allocated at this time out of the same physical storage
pool used to store application data.
a. If any page-node in the tree has not yet been allocated, it must be
allocated before the write can continue. This step requires the
data_vio to lock the page-node that needs to be allocated. This
lock, like the logical block lock in step 2, is a hashtable entry
that causes other data_vios to wait for the allocation process to
complete.
The implicit logical zone lock is released while the allocation is
happening, in order to allow other operations in the same logical
zone to proceed. The details of allocation are the same as in
step 4. Once a new node has been allocated, that node is added to
the tree using a similar process to adding a new data block mapping.
The data_vio journals the intent to add the new node to the block
map tree (step 10), updates the reference count of the new block
(step 11), and reacquires the implicit logical zone lock to add the
new mapping to the parent tree node (step 12). Once the tree is
updated, the data_vio proceeds down the tree. Any other data_vios
waiting on this allocation also proceed.
b. In the steady-state case, the block map tree nodes will already be
allocated, so the data_vio just traverses the tree until it finds
the required leaf node. The location of the mapping (the "block map
slot") is recorded in the data_vio so that later steps do not need
to traverse the tree again. The data_vio then releases the implicit
logical zone lock.
4. If the block is a zero block, skip to step 9. Otherwise, an attempt is
made to allocate a free data block. This allocation ensures that the
data_vio can write its data somewhere even if deduplication and
compression are not possible. This stage gets an implicit lock on a
physical zone to search for free space within that zone.
The data_vio will search each slab in a zone until it finds a free
block or decides there are none. If the first zone has no free space,
it will proceed to search the next physical zone by taking the implicit
lock for that zone and releasing the previous one until it finds a
free block or runs out of zones to search. The data_vio will acquire a
struct pbn_lock (the "physical block lock") on the free block. The
struct pbn_lock also has several fields to record the various kinds of
claims that data_vios can have on physical blocks. The pbn_lock is
added to a hashtable like the logical block locks in step 2. This
hashtable is also covered by the implicit physical zone lock. The
reference count of the free block is updated to prevent any other
data_vio from considering it free. The reference counters are a
sub-component of the slab and are thus also covered by the implicit
physical zone lock.
5. If an allocation was obtained, the data_vio has all the resources it
needs to complete the write. The application bio can safely be
acknowledged at this point. The acknowledgment happens on a separate
thread to prevent the application callback from blocking other data_vio
operations.
If an allocation could not be obtained, the data_vio continues to
attempt to deduplicate or compress the data, but the bio is not
acknowledged because the vdo device may be out of space.
6. At this point vdo must determine where to store the application data.
The data_vio's data is hashed and the hash (the "record name") is
recorded in the data_vio.
7. The data_vio reserves or joins a struct hash_lock, which manages all of
the data_vios currently writing the same data. Active hash locks are
tracked in a hashtable similar to the way logical block locks are
tracked in step 2. This hashtable is covered by the implicit lock on
the hash zone.
If there is no existing hash lock for this data_vio's record_name, the
data_vio obtains a hash lock from the pool, adds it to the hashtable,
and sets itself as the new hash lock's "agent." The hash_lock pool is
also covered by the implicit hash zone lock. The hash lock agent will
do all the work to decide where the application data will be
written. If a hash lock for the data_vio's record_name already exists,
and the data_vio's data is the same as the agent's data, the new
data_vio will wait for the agent to complete its work and then share
its result.
In the rare case that a hash lock exists for the data_vio's hash but
the data does not match the hash lock's agent, the data_vio skips to
step 8h and attempts to write its data directly. This can happen if two
different data blocks produce the same hash, for example.
8. The hash lock agent attempts to deduplicate or compress its data with
the following steps.
a. The agent initializes and sends its embedded deduplication request
(struct uds_request) to the deduplication index. This does not
require the data_vio to get any locks because the index components
manage their own locking. The data_vio waits until it either gets a
response from the index or times out.
b. If the deduplication index returns advice, the data_vio attempts to
obtain a physical block lock on the indicated physical address, in
order to read the data and verify that it is the same as the
data_vio's data, and that it can accept more references. If the
physical address is already locked by another data_vio, the data at
that address may soon be overwritten so it is not safe to use the
address for deduplication.
c. If the data matches and the physical block can add references, the
agent and any other data_vios waiting on it will record this
physical block as their new physical address and proceed to step 9
to record their new mapping. If there are more data_vios in the hash
lock than there are references available, one of the remaining
data_vios becomes the new agent and continues to step 8d as if no
valid advice was returned.
d. If no usable duplicate block was found, the agent first checks that
it has an allocated physical block (from step 3) that it can write
to. If the agent does not have an allocation, some other data_vio in
the hash lock that does have an allocation takes over as agent. If
none of the data_vios have an allocated physical block, these writes
are out of space, so they proceed to step 13 for cleanup.
e. The agent attempts to compress its data. If the data does not
compress, the data_vio will continue to step 8h to write its data
directly.
If the compressed size is small enough, the agent will release the
implicit hash zone lock and go to the packer (struct packer) where
it will be placed in a bin (struct packer_bin) along with other
data_vios. All compression operations require the implicit lock on
the packer zone.
The packer can combine up to 14 compressed blocks in a single 4k
data block. Compression is only helpful if vdo can pack at least 2
data_vios into a single data block. This means that a data_vio may
wait in the packer for an arbitrarily long time for other data_vios
to fill out the compressed block. There is a mechanism for vdo to
evict waiting data_vios when continuing to wait would cause
problems. Circumstances causing an eviction include an application
flush, device shutdown, or a subsequent data_vio trying to overwrite
the same logical block address. A data_vio may also be evicted from
the packer if it cannot be paired with any other compressed block
before more compressible blocks need to use its bin. An evicted
data_vio will proceed to step 8h to write its data directly.
f. If the agent fills a packer bin, either because all 14 of its slots
are used or because it has no remaining space, it is written out
using the allocated physical block from one of its data_vios. Step
8d has already ensured that an allocation is available.
g. Each data_vio sets the compressed block as its new physical address.
The data_vio obtains an implicit lock on the physical zone and
acquires the struct pbn_lock for the compressed block, which is
modified to be a shared lock. Then it releases the implicit physical
zone lock and proceeds to step 8i.
h. Any data_vio evicted from the packer will have an allocation from
step 3. It will write its data to that allocated physical block.
i. After the data is written, if the data_vio is the agent of a hash
lock, it will reacquire the implicit hash zone lock and share its
physical address with as many other data_vios in the hash lock as
possible. Each data_vio will then proceed to step 9 to record its
new mapping.
j. If the agent actually wrote new data (whether compressed or not),
the deduplication index is updated to reflect the location of the
new data. The agent then releases the implicit hash zone lock.
9. The data_vio determines the previous mapping of the logical address.
There is a cache for block map leaf pages (the "block map cache"),
because there are usually too many block map leaf nodes to store
entirely in memory. If the desired leaf page is not in the cache, the
data_vio will reserve a slot in the cache and load the desired page
into it, possibly evicting an older cached page. The data_vio then
finds the current physical address for this logical address (the "old
physical mapping"), if any, and records it. This step requires a lock
on the block map cache structures, covered by the implicit logical zone
lock.
10. The data_vio makes an entry in the recovery journal containing the
logical block address, the old physical mapping, and the new physical
mapping. Making this journal entry requires holding the implicit
recovery journal lock. The data_vio will wait in the journal until all
recovery blocks up to the one containing its entry have been written
and flushed to ensure the transaction is stable on storage.
11. Once the recovery journal entry is stable, the data_vio makes two slab
journal entries: an increment entry for the new mapping, and a
decrement entry for the old mapping. These two operations each require
holding a lock on the affected physical slab, covered by its implicit
physical zone lock. For correctness during recovery, the slab journal
entries in any given slab journal must be in the same order as the
corresponding recovery journal entries. Therefore, if the two entries
are in different zones, they are made concurrently, and if they are in
the same zone, the increment is always made before the decrement in
order to avoid underflow. After each slab journal entry is made in
memory, the associated reference count is also updated in memory.
12. Once both of the reference count updates are done, the data_vio
acquires the implicit logical zone lock and updates the
logical-to-physical mapping in the block map to point to the new
physical block. At this point the write operation is complete.
13. If the data_vio has a hash lock, it acquires the implicit hash zone
lock and releases its hash lock to the pool.
The data_vio then acquires the implicit physical zone lock and releases
the struct pbn_lock it holds for its allocated block. If it had an
allocation that it did not use, it also sets the reference count for
that block back to zero to free it for use by subsequent data_vios.
The data_vio then acquires the implicit logical zone lock and releases
the logical block lock acquired in step 2.
The application bio is then acknowledged if it has not previously been
acknowledged, and the data_vio is returned to the pool.
*Read Path*
An application read bio follows a much simpler set of steps. It does steps
1 and 2 in the write path to obtain a data_vio and lock its logical
address. If there is already a write data_vio in progress for that logical
address that is guaranteed to complete, the read data_vio will copy the
data from the write data_vio and return it. Otherwise, it will look up the
logical-to-physical mapping by traversing the block map tree as in step 3,
and then read and possibly decompress the indicated data at the indicated
physical block address. A read data_vio will not allocate block map tree
nodes if they are missing. If the interior block map nodes do not exist
yet, the logical block map address must still be unmapped and the read
data_vio will return all zeroes. A read data_vio handles cleanup and
acknowledgment as in step 13, although it only needs to release the logical
lock and return itself to the pool.
*Small Writes*
All storage within vdo is managed as 4KB blocks, but it can accept writes
as small as 512 bytes. Processing a write that is smaller than 4K requires
a read-modify-write operation that reads the relevant 4K block, copies the
new data over the appropriate sectors of the block, and then launches a
write operation for the modified data block. The read and write stages of
this operation are nearly identical to the normal read and write
operations, and a single data_vio is used throughout this operation.
*Recovery*
When a vdo is restarted after a crash, it will attempt to recover from the
recovery journal. During the pre-resume phase of the next start, the
recovery journal is read. The increment portion of valid entries are played
into the block map. Next, valid entries are played, in order as required,
into the slab journals. Finally, each physical zone attempts to replay at
least one slab journal to reconstruct the reference counts of one slab.
Once each zone has some free space (or has determined that it has none),
the vdo comes back online, while the remainder of the slab journals are
used to reconstruct the rest of the reference counts in the background.
*Read-only Rebuild*
If a vdo encounters an unrecoverable error, it will enter read-only mode.
This mode indicates that some previously acknowledged data may have been
lost. The vdo may be instructed to rebuild as best it can in order to
return to a writable state. However, this is never done automatically due
to the possibility that data has been lost. During a read-only rebuild, the
block map is recovered from the recovery journal as before. However, the
reference counts are not rebuilt from the slab journals. Instead, the
reference counts are zeroed, the entire block map is traversed, and the
reference counts are updated from the block mappings. While this may lose
some data, it ensures that the block map and reference counts are
consistent with each other. This allows vdo to resume normal operation and
accept further writes.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
dm-vdo의 기능과 설계 한계
1-21`dm-vdo`(virtual data optimizer) target은 inline deduplication, compression, zero-block elimination, thin provisioning을 제공합니다. 하나의 dm-vdo target은 최대 256TB의 backing storage를 사용할 수 있고 최대 4PB의 logical size를 제공할 수 있습니다. 이 target은 Permabit Technology Corp.가 2009년부터 개발했으며 2013년에 처음 출시된 뒤 계속 production 환경에서 사용되었습니다. 2017년 Red Hat이 Permabit을 인수한 뒤 open source로 공개되었습니다. 이 문서는 dm-vdo의 설계를 설명하며 사용법은 같은 디렉터리의 `vdo.rst`를 참조하십시오.
Block size가 커질수록 deduplication 비율이 급격히 떨어지므로 vdo target의 최대 block size는 4K입니다. 대신 동일한 4K block의 사본을 최대 254개까지 실제 storage의 단일 4K block에 참조시켜 254:1의 deduplication 비율을 달성할 수 있습니다. Compression 비율은 최대 14:1이며 zero block은 storage를 전혀 소비하지 않습니다.
문서가 명시한 address capacity와 block-level data optimization 상한입니다.
동작 이론과 zone 기반 threading
22-62dm-vdo의 설계는 deduplication이 두 부분으로 이루어진 문제라는 생각에서 출발합니다. 첫째는 중복 data를 인식하는 것이고, 둘째는 그 중복 사본을 여러 번 저장하지 않는 것입니다. 따라서 dm-vdo에는 두 핵심 부분이 있습니다. 중복 data를 발견하는 deduplication index인 UDS와, logical block address를 실제 data storage 위치로 연결하는 reference-counted block map을 포함한 data store입니다.
중복을 찾는 index와 사본 공유를 기록하는 data store가 함께 동작합니다.
Data optimization은 복잡하므로 vdo target에 대한 단일 write operation이 관여하는 metadata structure의 수는 대부분의 다른 target보다 많습니다. 또한 좋은 deduplication 비율을 얻으려면 작은 block size로 동작해야 하므로 허용 가능한 성능은 parallelism을 통해서만 얻을 수 있습니다. 이 때문에 vdo 설계는 lock-free 동작을 지향합니다.
vdo의 주요 data structure 대부분은 `zone`으로 쉽게 분할되도록 설계됩니다. 주어진 bio는 zone으로 나뉜 각 structure에서 오직 하나의 zone에만 접근하면 됩니다. 정상 동작 중에는 각 zone을 특정 thread에 배정하고 그 thread만 해당 zone의 structure 부분에 접근하게 하여 최소한의 locking으로 안전성을 확보합니다. 각 thread에는 work queue가 연결됩니다. 각 bio에는 request object인 `data_vio`가 연결되며, 다음 처리 단계가 특정 zone의 structure에 접근해야 할 때 그 zone과 연결된 work queue에 추가됩니다.
달리 표현하면 각 zone의 work queue는 자신이 관리하는 structure에 대한 모든 operation 동안 암묵적인 lock을 보유합니다. 다른 thread가 그 structure를 변경하지 않도록 vdo가 보장하기 때문입니다.
각 structure가 zone으로 분할되더라도 이 구분은 각 data structure의 on-disk representation에는 반영되지 않습니다. 따라서 structure별 zone 수와 그에 따른 thread 수는 vdo target을 시작할 때마다 다시 설정할 수 있습니다.
명시적인 fine-grained lock 대신 queue ownership으로 structure 접근을 직렬화합니다.
Deduplication index의 원칙과 검증
63-97중복 data를 효율적으로 식별하도록 vdo는 중복 data에서 흔히 나타나는 특성을 활용합니다. 경험적 관찰에서 두 가지 핵심 통찰을 얻었습니다. 첫째, 중복이 많은 대부분의 data set에서는 duplicate가 temporal locality를 보입니다. 하나의 duplicate가 나타나면 다른 duplicate도 발견될 가능성이 높고, 그 duplicate들은 비슷한 시점에 기록되었을 가능성이 높습니다. 그래서 index는 record를 시간 순서로 유지합니다.
둘째, 새 data는 오래된 data보다 최근 data와 중복될 가능성이 높고 더 과거까지 검색할수록 일반적으로 수익이 감소합니다. 따라서 index가 가득 차면 가장 오래된 record를 제거하여 새 record를 위한 공간을 만들어야 합니다. Index 설계의 또 다른 중요한 생각은 deduplication의 최종 목표가 storage cost를 줄이는 것이라는 점입니다. 절약되는 storage와 이를 위해 소비되는 resource 사이에 trade-off가 있으므로 vdo는 마지막 한 개까지 모든 duplicate block을 찾으려 하지 않습니다. 중복의 대부분을 찾아 제거하면 충분합니다.
각 data block을 hash하여 16-byte block name을 만듭니다. Index record는 이 block name과 underlying storage에서 그 data가 있을 것으로 추정되는 위치를 한 쌍으로 저장합니다. 그러나 index의 정확성을 보장할 수는 없습니다. 가장 흔한 이유는 block이 overwrite되거나 discard될 때 index를 갱신하는 비용이 너무 크기 때문입니다. 갱신하려면 block name을 block과 함께 저장해야 하는데 block-based storage에서 효율적으로 하기 어렵거나, overwrite하기 전에 각 block을 읽어 다시 hash해야 합니다.
서로 다른 두 block이 같은 name을 갖는 hash collision도 부정확성을 만들 수 있습니다. 실제로는 극히 드물지만 vdo가 cryptographic hash를 사용하지 않으므로 악의적인 workload를 구성할 수 있습니다. 이런 부정확성 때문에 vdo는 index의 위치를 hint로만 취급합니다. 기존 block을 새 block과 공유하기 전에 표시된 block을 읽어 실제로 duplicate인지 반드시 검증합니다.
UDS 위치는 확정 mapping이 아니라 읽어서 확인해야 하는 hint입니다.
Chapter, volume index와 delta index
98-162Record는 `chapter`라는 group으로 모입니다. 새 record는 가장 최신 chapter인 `open chapter`에 추가됩니다. 이 chapter는 record 추가와 수정에 최적화된 형식으로 저장되며 새 record를 넣을 공간이 없어질 때까지 내용이 확정되지 않습니다. Open chapter가 가득 차면 이를 닫고 새 open chapter를 만들어 새 record를 모읍니다.
Chapter를 닫으면 읽기에 최적화된 다른 형식으로 변환합니다. Record는 받은 순서에 따라 일련의 record page에 기록됩니다. 따라서 temporal locality가 있는 record는 소수의 page에 모이고, 이를 가져오는 데 필요한 I/O가 줄어듭니다. Chapter는 주어진 name이 어느 record page에 있는지 나타내는 index도 만듭니다. 덕분에 전체 chapter를 storage에서 읽지 않고도 name request가 해당 record를 포함할 수 있는 정확한 record page를 결정할 수 있습니다.
Chapter index는 block name 일부만 key로 사용하므로 index entry가 원하는 block name을 가리킨다고 보장하지는 못합니다. 특정 name의 record가 존재한다면 표시된 page에 있다는 것만 보장합니다. 닫힌 chapter는 read-only structure이며 그 내용은 어떤 방식으로도 변경되지 않습니다.
사용 가능한 index 공간 전체를 채울 만큼 record가 기록되면 가장 오래된 chapter를 제거하여 새 chapter를 위한 공간을 만듭니다. Request가 index에서 matching record를 찾을 때마다 그 record를 open chapter로 복사합니다. 이 방식으로 유용한 block name은 index에 남고 참조되지 않는 block name은 시간이 지나면서 잊힙니다.
오래된 chapter의 record를 찾기 위해 index는 `volume index`라는 상위 structure도 유지합니다. 이 structure는 각 block name을 그 name의 가장 최신 record가 있는 chapter에 mapping합니다. Block name record가 복사되거나 갱신될 때 mapping도 갱신되므로 name별 가장 최신 record만 찾을 수 있습니다. 오래된 record가 chapter에서 삭제되지 않았어도 더는 검색 결과에 나타나지 않습니다.
Chapter index와 마찬가지로 volume index도 block name의 일부만 key로 사용하여 특정 name의 record가 존재한다고 확정할 수 없습니다. Record가 존재한다면 어느 chapter에 있을지만 말할 수 있습니다. Volume index 전체는 memory에 저장되고 vdo target이 shut down될 때만 storage에 저장됩니다.
특정 block name request는 먼저 volume index에서 name을 찾습니다. 그 결과는 name이 새롭거나 검색할 chapter가 어디인지 알려 줍니다. Chapter가 반환되면 chapter index에서 name을 찾아 새 name인지 또는 어느 record page를 검색할지 결정합니다. 새 name이 아니면 마지막으로 표시된 record page에서 name을 찾습니다. Request 하나에 chapter index page와 record page를 각각 읽어 최대 두 번의 page read가 필요할 수 있지만 최근 접근 page를 cache하므로 많은 block name request에 걸쳐 이 비용을 분산할 수 있습니다.
Volume index와 chapter index는 memory-efficient structure인 `delta index`로 구현됩니다. Entry마다 전체 block name(key)을 저장하는 대신 name 순으로 entry를 정렬하고 인접 key의 차이인 delta만 저장합니다. Hash가 무작위로 분포한다고 예상하므로 delta 크기는 exponential distribution을 따르며, 이 분포에 맞춰 Huffman code로 표현하여 공간을 더 줄입니다.
정렬된 key 전체 목록을 `delta list`라고 합니다. 전통적인 hash table보다 entry당 훨씬 적은 byte를 사용하지만 lookup은 조금 비쌉니다. 필요한 record를 찾으려면 request가 delta list의 각 entry를 읽고 delta를 누적해야 하기 때문입니다. Delta index는 key space를 고정 key value에서 시작하는 여러 짧은 sub-list로 나눠 이 lookup cost를 줄입니다.
상위 index에서 chapter와 page를 좁힌 뒤 실제 record를 확인합니다.
Write-friendly open chapter가 immutable read-friendly chapter로 전환됩니다.
Deduplication window와 sparse indexing
163-195기본 index size는 6,400만 record, 즉 약 256GB data에 해당하는 정보를 보유합니다. 따라서 원본 data가 최근 256GB write 범위 안에서 기록되었다면 index가 duplicate를 식별할 수 있습니다. 이 범위를 `deduplication window`라고 합니다. 새 write가 이보다 오래된 data와 중복되면 오래된 record가 이미 제거되었으므로 index가 찾지 못합니다.
예를 들어 application이 200GB file을 vdo target에 쓰고 즉시 다시 쓰면 두 사본은 완전히 deduplicate됩니다. 같은 일을 500GB file로 하면 두 번째 write가 시작되어 앞부분에 도달할 때 첫 file의 시작 record가 index에서 사라졌으므로 deduplication이 전혀 일어나지 않습니다. 이 예시는 file 자체 안에는 duplicate가 없다고 가정합니다.
Workload가 256GB 경계를 넘어 유용한 deduplication을 보일 것으로 예상하면 더 큰 deduplication window를 갖도록 vdo index를 크게 설정할 수 있습니다. 이 설정은 target을 만들 때만 가능하고 나중에 변경할 수 없으므로 target을 구성하기 전에 예상 workload를 고려해야 합니다. 방법은 두 가지입니다.
첫 번째 방법은 index memory size를 늘리는 것이며 필요한 backing storage도 함께 증가합니다. Index size를 두 배로 하면 deduplication window 길이가 두 배가 되지만 storage size와 memory requirement도 두 배가 됩니다.
두 번째 방법은 sparse indexing을 활성화하는 것입니다. Sparse indexing은 deduplication window와 storage size를 각각 10배로 늘리지만 memory requirement는 증가시키지 않습니다. 대신 request당 computation이 조금 늘고 발견되는 deduplication 양이 약간 감소합니다. Duplicate가 많은 대부분의 workload에서 sparse indexing은 standard index가 찾아낼 deduplication의 97~99%를 탐지합니다.
더 긴 window를 얻는 두 방법의 resource trade-off입니다.
vio와 data_vio structure
196-219`vio`는 Vdo I/O의 줄임말이며 개념적으로 bio와 비슷하지만 vdo 전용 정보를 추적하는 field와 data가 추가됩니다. `struct vio`는 bio pointer를 유지하면서 vdo operation 고유의 다른 field도 추적합니다. Vdo가 bio를 완료한 뒤에도 deduplication 또는 compression 관련 작업을 계속해야 하는 경우가 많으므로 vio는 관련 bio와 분리되어 유지됩니다.
Metadata read/write와 vdo 내부에서 시작되는 다른 write는 `struct vio`를 직접 사용합니다. Application read/write는 진행 상황을 추적하기 위해 더 큰 `data_vio` structure를 사용합니다. `struct data_vio`는 `struct vio`를 포함하며 deduplication과 기타 vdo 기능 관련 field도 포함합니다. `data_vio`는 vdo에서 application work의 기본 단위입니다. 각 data_vio는 application data를 처리하는 일련의 단계를 거친 뒤 reset되어 재사용을 위해 data_vio pool로 돌아갑니다.
고정 pool에는 2,048개의 data_vio가 있습니다. 이 수는 crash recovery에 필요한 작업량을 제한하기 위해 선택되었습니다. 또한 benchmark에서 pool을 더 크게 해도 성능이 크게 향상되지 않았습니다.
Bio 수명과 최적화 작업 수명을 분리하는 object hierarchy입니다.
Data store와 slab depot
220-263Data store는 세 가지 주요 data structure로 구현됩니다. 이들은 가능한 한 많은 data write에 metadata update를 줄이거나 분산하도록 함께 동작합니다.
vdo volume 대부분은 `slab depot`에 속합니다. Depot은 slab collection을 포함합니다. Slab은 최대 32GB이며 세 section으로 나뉩니다. Slab 대부분은 4K block의 linear sequence입니다. 이 block은 data 저장 또는 block map 일부 저장에 사용됩니다. Data block 외에도 각 slab은 data block마다 1 byte를 사용하는 reference counter set과 journal 하나를 가집니다.
Reference update는 slab journal에 기록됩니다. Slab journal block은 가득 찼을 때 또는 main recovery journal이 공간을 비울 수 있도록 recovery journal이 요청할 때 storage에 기록됩니다. Slab journal은 main recovery journal이 주기적으로 공간을 비우게 하고 개별 reference block update 비용을 분산하는 두 역할을 합니다.
Reference counter는 memory에 유지됩니다. Slab journal 공간을 회수해야 할 때만 가장 오래전에 dirty된 순서로 block 단위로 기록됩니다. Write operation은 필요에 따라 background에서 수행되므로 특정 I/O operation에 latency를 추가하지 않습니다.
각 slab은 다른 모든 slab과 독립적입니다. Slab은 `physical zone`에 round-robin으로 배정됩니다. Physical zone이 P개이면 slab n은 zone `n mod P`에 배정됩니다.
Slab depot은 crash 뒤 online으로 복귀하는 작업량을 줄이기 위해 `slab summary`라는 작은 data structure도 유지합니다. Slab별 entry는 slab 사용 이력, 모든 reference count update의 storage 반영 여부, 대략적인 사용량을 나타냅니다.
Recovery 동안 각 physical zone은 최소 한 slab을 복구하려고 하며 free block이 있는 slab 하나를 복구하면 멈춥니다. 각 zone이 공간을 확보하거나 사용 가능한 공간이 없음을 확인하면 target은 degraded mode로 정상 동작을 재개할 수 있습니다. 나머지 dirty slab이 복구되는 동안에도 성능이 떨어질 수는 있지만 read/write request를 처리할 수 있습니다.
최대 32GB slab을 구성하는 세 section입니다.
모든 slab 복구를 기다리지 않고 zone별 최소 free space가 확보되면 I/O를 재개합니다.
Logical-to-physical block map
264-298Block map은 logical-to-physical mapping을 포함합니다. Logical address마다 하나의 entry를 갖는 array로 생각할 수 있습니다. 각 entry는 5 byte이며 그중 36 bit는 해당 logical address의 data를 담은 physical block number입니다. 나머지 4 bit는 mapping의 성격을 나타냅니다.
4 bit로 표현 가능한 16 state 중 하나는 한 번도 쓰이지 않았거나 discard된 unmapped logical address를 나타내고, 하나는 uncompressed block을 나타냅니다. 나머지 14 state는 mapped data가 compressed되었으며 compressed block 안의 어느 compression slot에 이 logical address의 data가 있는지 표시합니다.
실제로 mapping entry array는 4K block 하나에 맞는 `block map page`로 나뉩니다. 각 page는 header와 mapping entry 812개로 이루어집니다. 각 mapping page는 모든 level이 block map page로 구성된 radix tree의 leaf입니다.
Radix tree는 60개이며 `logical zone`에 round-robin으로 배정됩니다. Logical zone이 L개이면 tree n은 zone `n mod L`에 속합니다. 각 level에서 tree가 interleave되므로 logical address 0~811은 tree 0, 812~1623은 tree 1에 속하는 식입니다. 이 interleaving은 60개 root node까지 모든 level에서 유지됩니다. Tree 60개를 선택하면 가능한 logical zone 수가 여러 가지여도 zone마다 tree 수가 고르게 분배됩니다.
60개 tree root의 storage는 format할 때 할당합니다. 그 외 모든 block map page는 필요할 때 slab에서 할당합니다. 이 유연한 allocation은 logical mapping 전체 공간을 미리 할당하지 않아도 되게 하고 vdo logical size 확장도 비교적 쉽게 만듭니다.
동작 중 block map은 두 cache를 유지합니다. Tree의 leaf level 전체를 memory에 두는 것은 비용이 너무 크므로 각 logical zone은 자체 leaf page cache를 유지합니다. 이 cache size는 target 시작 때 설정할 수 있습니다. 두 번째 cache는 시작 때 할당되며 block map 전체의 non-leaf page를 모두 담을 만큼 큽니다. Page가 필요해질 때 이 cache를 채웁니다.
Physical address와 compression state를 compact하게 저장합니다.
Logical address range가 60개 interleaved radix tree와 logical zone에 분산됩니다.
Recovery journal의 durability contract
299-319Recovery journal은 block map과 slab depot에 대한 update 비용을 분산합니다. 각 write request는 journal entry 하나를 만듭니다. Entry는 `data remapping` 또는 `block map remapping`입니다. Data remapping은 영향을 받는 logical address와 old/new physical mapping을 기록합니다. Block map remapping은 block map page number와 그 page에 할당된 physical block을 기록합니다. Block map page는 회수되거나 다른 목적으로 전환되지 않으므로 old mapping은 항상 0입니다.
각 journal entry는 data_vio에 필요한 metadata update를 요약한 intent record입니다. Recovery journal은 journal block을 쓰기 전에 flush를 발행하여 해당 block의 새 physical mapping이 가리키는 data가 storage에서 stable하도록 합니다. Journal block write에는 모두 FUA bit를 설정하여 recovery journal entry 자체도 stable하게 합니다.
Operation을 반영하도록 다른 metadata structure를 갱신하기 전에 journal entry와 그것이 나타내는 data write가 disk에서 stable해야 합니다. 이 entry 덕분에 vdo device는 power loss 같은 예기치 않은 중단 뒤 logical-to-physical mapping을 재구성할 수 있습니다.
Data, recovery intent, 파생 metadata의 순서를 강제합니다.
Write path 1~2: object 획득과 logical lock
320-365vdo에 대한 모든 write I/O는 asynchronous입니다. vdo가 write를 결국 완료할 수 있다고 보장할 만큼 작업을 마치면 각 bio를 acknowledge합니다. 일반적으로 acknowledge되었지만 flush되지 않은 write I/O data는 memory에 cache된 것처럼 취급할 수 있습니다. Application이 storage에서 data가 stable하기를 요구하면 다른 asynchronous I/O와 마찬가지로 flush를 발행하거나 FUA bit를 설정해 써야 합니다. vdo target shutdown도 남은 I/O를 flush합니다.
Application write bio는 아래 단계를 따릅니다.
1. data_vio pool에서 `data_vio` 하나를 얻어 application bio와 연결합니다. 사용 가능한 data_vio가 없으면 incoming bio는 하나가 반환될 때까지 block됩니다. 이는 application에 back pressure를 제공합니다. Data_vio pool은 spin lock으로 보호됩니다.
새로 얻은 data_vio를 reset하고, write이며 data가 모두 zero가 아니면 bio data를 data_vio에 복사합니다. Data_vio 처리가 끝나기 전에 application bio를 acknowledge할 수 있어 이후 단계에서는 bio data에 접근할 수 없으므로 복사가 필요합니다. Application bio가 4K보다 작을 수도 있습니다. 이때 data_vio는 이미 underlying block을 읽었고 새 data는 더 큰 block의 해당 부분에 복사됩니다.
2. data_vio가 bio의 logical address에 `logical lock`이라는 claim을 겁니다. Deduplication은 block 공유를 포함하므로 같은 logical address를 동시에 수정하지 못하게 하는 것이 매우 중요합니다. 이 claim은 logical address를 key로, 해당 address를 처리 중인 data_vio pointer를 value로 갖는 hashtable entry로 구현합니다.
Hashtable에서 다른 data_vio가 같은 logical address를 처리 중임을 발견하면 이전 operation이 끝날 때까지 기다립니다. 또한 현재 lock holder에게 자신이 기다리고 있음을 알리는 message를 보냅니다. 특히 logical lock을 기다리는 새 data_vio는 이전 holder가 compression packer에서 계속 packing을 기다리게 두지 않고 step 8d로 내보냅니다.
이 단계에서는 hashtable 동시 수정을 막기 위해 적절한 logical zone의 implicit lock이 필요합니다. 이 implicit locking은 앞서 설명한 zone division으로 처리됩니다.
Pool이 back pressure를 제공하고 logical lock이 같은 address의 overwrite를 직렬화합니다.
Write path 3~5: block map 준비와 allocation
366-4283. data_vio는 logical address의 leaf page를 찾으면서 block map tree를 순회하여 필요한 internal tree node가 모두 할당되었는지 확인합니다. 누락된 interior tree page가 있으면 application data와 같은 physical storage pool에서 이때 할당합니다.
3a. Tree의 page-node가 아직 할당되지 않았다면 write를 계속하기 전에 할당해야 합니다. Data_vio는 할당할 page-node를 lock해야 합니다. Step 2의 logical block lock처럼 이 lock도 다른 data_vio가 allocation 완료를 기다리게 하는 hashtable entry입니다.
Allocation 동안 같은 logical zone의 다른 operation이 진행할 수 있도록 implicit logical zone lock을 해제합니다. Allocation 세부 사항은 step 4와 같습니다. 새 node가 할당되면 새 data block mapping을 추가하는 것과 비슷한 절차로 tree에 추가합니다. Data_vio는 새 node를 block map tree에 추가할 intent를 journal에 기록하고(step 10), 새 block의 reference count를 갱신한 뒤(step 11), implicit logical zone lock을 다시 얻어 parent tree node에 새 mapping을 추가합니다(step 12). Tree update 뒤 data_vio는 아래 level로 진행하며 이 allocation을 기다리던 다른 data_vio도 진행합니다.
3b. Steady state에서는 block map tree node가 이미 할당되어 있으므로 필요한 leaf node까지 tree를 순회하기만 합니다. Mapping 위치인 `block map slot`을 data_vio에 기록하여 이후 단계에서 tree를 다시 순회하지 않게 합니다. 그런 다음 implicit logical zone lock을 해제합니다.
4. Block이 zero block이면 step 9로 건너뜁니다. 그렇지 않으면 free data block 할당을 시도합니다. Deduplication과 compression이 불가능해도 data를 기록할 곳을 보장하는 allocation입니다. 이 단계는 한 physical zone의 implicit lock을 얻어 그 zone 안의 free space를 검색합니다.
Data_vio는 free block을 찾거나 없다고 판단할 때까지 zone의 각 slab을 검색합니다. 첫 zone에 공간이 없으면 그 zone lock을 해제하고 다음 physical zone의 implicit lock을 얻는 방식으로 free block을 찾거나 모든 zone을 소진할 때까지 계속합니다.
Free block을 찾으면 `struct pbn_lock`, 즉 physical block lock을 얻습니다. `pbn_lock`에는 data_vio가 physical block에 가질 수 있는 여러 claim 종류를 기록하는 field도 있습니다. Logical block lock처럼 hashtable에 추가되며 이 table도 implicit physical zone lock으로 보호됩니다. 다른 data_vio가 free로 판단하지 못하도록 free block reference count를 갱신합니다. Reference counter는 slab의 sub-component이므로 역시 physical zone implicit lock으로 보호됩니다.
5. Allocation을 얻으면 data_vio는 write를 완료하는 데 필요한 resource를 모두 확보한 것이므로 이 시점에서 application bio를 안전하게 acknowledge할 수 있습니다. Application callback이 다른 data_vio operation을 막지 않도록 acknowledgement는 별도 thread에서 수행합니다.
Allocation을 얻지 못해도 deduplicate 또는 compress 시도는 계속하지만 vdo device가 out of space일 수 있으므로 bio는 acknowledge하지 않습니다.
Metadata node와 fallback data block을 실제 write 이전에 확보합니다.
Write path 6~8: hash, deduplication과 compression
429-5326. 이제 vdo는 application data를 어디에 저장할지 결정해야 합니다. Data_vio data를 hash하고 그 hash인 `record name`을 data_vio에 기록합니다.
7. data_vio는 같은 data를 쓰는 모든 data_vio를 관리하는 `struct hash_lock`을 예약하거나 기존 lock에 합류합니다. Active hash lock은 step 2의 logical block lock과 비슷한 hashtable로 추적하며 이 table은 hash zone implicit lock으로 보호됩니다.
Record name에 대한 hash lock이 없으면 pool에서 lock을 얻어 hashtable에 추가하고 자신을 새 hash lock의 `agent`로 설정합니다. Hash_lock pool도 hash zone implicit lock으로 보호됩니다. Agent가 application data를 어디에 기록할지 결정하는 모든 작업을 수행합니다. 같은 record name의 hash lock이 이미 있고 data가 agent data와 같으면 새 data_vio는 agent가 작업을 완료할 때까지 기다린 뒤 결과를 공유합니다.
드물게 hash는 같지만 data가 agent와 일치하지 않으면 data_vio는 step 8h로 건너뛰어 data를 직접 쓰려고 합니다. 서로 다른 data block이 같은 hash를 만드는 경우가 그 예입니다.
8. Hash lock agent는 다음 단계로 data deduplication 또는 compression을 시도합니다.
8a. Agent는 내장 deduplication request인 `struct uds_request`를 초기화하여 deduplication index에 보냅니다. Index component가 자체 locking을 관리하므로 data_vio가 lock을 얻을 필요는 없습니다. Data_vio는 index response를 받거나 timeout될 때까지 기다립니다.
8b. Deduplication index가 advice를 반환하면 data_vio는 표시된 physical address에서 physical block lock을 얻으려고 합니다. Data를 읽어 자신의 data와 같은지, reference를 더 받을 수 있는지 검증하기 위해서입니다. 다른 data_vio가 이미 address를 lock했다면 그 위치의 data가 곧 overwrite될 수 있어 deduplication에 안전하게 사용할 수 없습니다.
8c. Data가 일치하고 physical block이 reference를 추가할 수 있으면 agent와 대기 중인 다른 data_vio는 이 block을 새 physical address로 기록하고 step 9로 진행하여 새 mapping을 기록합니다. Hash lock 안의 data_vio 수가 사용 가능한 reference 수보다 많으면 남은 data_vio 중 하나가 새 agent가 되어 usable advice가 없었던 것처럼 step 8d부터 계속합니다.
8d. 사용할 수 있는 duplicate block을 찾지 못하면 agent는 먼저 step 4에서 받은 allocated physical block이 있는지 확인합니다. Allocation이 없으면 hash lock 안에서 allocation을 가진 다른 data_vio가 agent를 넘겨받습니다. 어느 data_vio도 allocated block이 없으면 이 write들은 out of space이므로 cleanup을 위해 step 13으로 진행합니다.
8e. Agent가 data compression을 시도합니다. 압축되지 않으면 step 8h로 진행해 직접 씁니다. 충분히 작게 압축되면 hash zone implicit lock을 해제하고 `struct packer`로 이동합니다. 그곳에서 다른 data_vio와 함께 `struct packer_bin`에 배치됩니다. 모든 compression operation에는 packer zone implicit lock이 필요합니다.
Packer는 하나의 4K data block에 compressed block을 최대 14개 결합할 수 있습니다. 최소 2개 data_vio를 한 data block에 pack해야 compression이 유용합니다. 따라서 data_vio는 compressed block을 채울 다른 data_vio를 임의로 긴 시간 기다릴 수 있습니다.
계속 기다리면 문제가 될 때 대기 data_vio를 evict하는 mechanism이 있습니다. Application flush, device shutdown, 같은 logical block address를 overwrite하려는 후속 data_vio가 eviction을 일으킵니다. 더 압축 가능한 block이 bin을 필요로 하기 전에 다른 compressed block과 pair를 만들지 못해도 evict될 수 있습니다. Evict된 data_vio는 step 8h로 이동하여 data를 직접 씁니다.
8f. 14 slot을 모두 사용했거나 남은 공간이 없어 agent가 packer bin을 채우면 그 bin의 data_vio 하나가 가진 allocated physical block을 사용해 기록합니다. Step 8d에서 allocation이 있음을 이미 보장했습니다.
8g. 각 data_vio는 compressed block을 새 physical address로 설정합니다. Physical zone implicit lock을 얻고 compressed block의 `struct pbn_lock`을 획득하여 shared lock으로 변경합니다. 그런 다음 implicit physical zone lock을 해제하고 step 8i로 진행합니다.
8h. Packer에서 evict된 data_vio는 step 4에서 얻은 allocation을 가지고 있으므로 그 allocated physical block에 data를 씁니다.
8i. Data write 뒤 data_vio가 hash lock agent이면 hash zone implicit lock을 다시 얻고 hash lock 안에서 가능한 한 많은 다른 data_vio와 physical address를 공유합니다. 각 data_vio는 새 mapping을 기록하기 위해 step 9로 진행합니다.
8j. Agent가 compressed 여부와 무관하게 실제로 새 data를 썼다면 새 data 위치를 반영하도록 deduplication index를 갱신합니다. 그런 다음 agent는 hash zone implicit lock을 해제합니다.
같은 content를 쓰는 request가 한 agent의 결과를 공유합니다.
무기한 대기가 correctness나 progress를 막기 전에 direct write로 전환합니다.
Write path 9~13: mapping commit과 cleanup
533-5819. data_vio가 logical address의 이전 mapping을 결정합니다. Block map leaf node가 너무 많아 모두 memory에 둘 수 없으므로 leaf page용 `block map cache`가 있습니다. 원하는 leaf page가 cache에 없으면 slot을 예약하고, 필요하면 오래된 cached page를 evict한 뒤 page를 load합니다. 현재 logical address의 physical address인 `old physical mapping`이 있으면 찾아 기록합니다. 이 단계는 block map cache structure lock이 필요하며 implicit logical zone lock으로 보호됩니다.
10. data_vio가 logical block address, old physical mapping, new physical mapping을 포함하는 recovery journal entry를 만듭니다. Entry 생성에는 implicit recovery journal lock을 보유해야 합니다. Transaction이 storage에서 stable하도록 자신의 entry가 든 recovery block까지의 모든 block이 기록되고 flush될 때까지 journal에서 기다립니다.
11. Recovery journal entry가 stable해지면 data_vio는 두 slab journal entry를 만듭니다. 새 mapping에는 increment, old mapping에는 decrement entry를 기록합니다. 각 operation은 대상 physical slab의 lock이 필요하며 해당 physical zone implicit lock으로 보호됩니다.
Recovery correctness를 위해 각 slab journal의 entry 순서는 대응하는 recovery journal entry 순서와 같아야 합니다. 두 entry가 다른 zone에 있으면 동시에 만들고, 같은 zone이면 underflow를 피하도록 항상 increment를 decrement보다 먼저 만듭니다. 각 slab journal entry를 memory에 만든 뒤 관련 reference count도 memory에서 갱신합니다.
12. 두 reference count update가 끝나면 data_vio는 implicit logical zone lock을 얻고 block map의 logical-to-physical mapping을 새 physical block으로 갱신합니다. 이 시점에 write operation이 완료됩니다.
13. data_vio가 hash lock을 가지고 있으면 implicit hash zone lock을 얻고 hash lock을 pool에 반환합니다. 이어 implicit physical zone lock을 얻어 allocated block의 `struct pbn_lock`을 해제합니다. 사용하지 않은 allocation이 있으면 그 block의 reference count도 0으로 되돌려 이후 data_vio가 사용할 수 있게 합니다.
그런 다음 implicit logical zone lock을 얻어 step 2의 logical block lock을 해제합니다. 아직 acknowledge하지 않은 application bio를 acknowledge하고 data_vio를 pool에 반환합니다.
Recovery 가능한 ordering을 유지한 뒤 lock과 임시 allocation을 정리합니다.
Read path와 4K 미만 write
582-607Application read bio의 단계는 훨씬 단순합니다. Write path의 step 1과 2를 수행하여 data_vio를 얻고 logical address를 lock합니다. 같은 logical address에서 완료가 보장된 write data_vio가 이미 진행 중이면 read data_vio는 그 write data_vio에서 data를 복사해 반환합니다.
그렇지 않으면 step 3처럼 block map tree를 순회해 logical-to-physical mapping을 찾고 표시된 physical block address의 data를 읽으며 필요하면 decompress합니다. Read data_vio는 누락된 block map tree node를 할당하지 않습니다. Interior node가 아직 없다면 logical block map address는 여전히 unmapped여야 하므로 zero data를 반환합니다.
Read data_vio는 step 13처럼 cleanup과 acknowledgement를 처리하지만 logical lock 해제와 pool 반환만 필요합니다.
vdo 내부 storage는 모두 4KB block으로 관리되지만 512 byte만큼 작은 write도 받을 수 있습니다. 4K보다 작은 write는 관련 4K block을 읽고 새 data를 block의 해당 sector에 덮어쓴 뒤 수정된 data block의 write operation을 시작하는 read-modify-write가 필요합니다.
이 operation의 read와 write 단계는 정상 read/write와 거의 같으며 operation 전체에서 하나의 data_vio를 사용합니다.
Read는 allocation을 만들지 않으며 partial write는 하나의 data_vio로 4K block을 병합합니다.
Crash recovery와 read-only rebuild
608-633Crash 뒤 vdo를 다시 시작하면 recovery journal에서 복구를 시도합니다. 다음 시작의 pre-resume phase에서 recovery journal을 읽습니다. Valid entry의 increment 부분을 block map에 replay합니다. 이어 valid entry를 필요한 순서대로 slab journal에 replay합니다. 마지막으로 각 physical zone이 최소 하나의 slab journal을 replay하여 slab 하나의 reference count를 재구성합니다.
각 zone이 free space를 확보하거나 공간이 없음을 확인하면 vdo는 online으로 돌아옵니다. 나머지 slab journal은 background에서 나머지 reference count를 재구성하는 데 사용됩니다.
vdo가 복구할 수 없는 error를 만나면 read-only mode로 들어갑니다. 이 mode는 이전에 acknowledge한 data 일부가 유실되었을 수 있음을 의미합니다. Writable state로 돌아가기 위해 가능한 범위에서 rebuild하도록 지시할 수 있지만 data loss 가능성이 있으므로 자동으로 실행하지는 않습니다.
Read-only rebuild에서는 이전처럼 recovery journal에서 block map을 복구합니다. 그러나 slab journal에서 reference count를 재구성하지 않습니다. 대신 reference count를 0으로 만들고 block map 전체를 순회하여 block mapping에서 reference count를 갱신합니다.
이 과정에서 data 일부를 잃을 수 있지만 block map과 reference count가 서로 일관되도록 보장합니다. 그 결과 vdo는 정상 동작을 재개하고 추가 write를 받을 수 있습니다.
정상 crash replay와 명시적 read-only rebuild의 reference count source가 다릅니다.
Architecture
vdo-design.rst:1-1954K 단위 data를 UDS에서 탐색하고 reference-counted data store에 공유하는 구조, chapter 기반 index와 deduplication window의 trade-off를 다룹니다.