79 lines
3.1 KiB
ReStructuredText
79 lines
3.1 KiB
ReStructuredText
Deduplication
|
|
=============
|
|
|
|
Going by the definition in the context of filesystems, it's a process of
|
|
looking up identical data blocks tracked separately and creating a shared
|
|
logical link while removing one of the copies of the data blocks. This leads to
|
|
data space savings while it increases metadata consumption.
|
|
|
|
There are two main deduplication types:
|
|
|
|
* **in-band** *(sometimes also called on-line)* -- all newly written data are
|
|
considered for deduplication before writing
|
|
* **out-of-band** *(sometimes also called offline)* -- data for deduplication
|
|
have to be actively looked for and deduplicated by the user application
|
|
|
|
Both have their pros and cons. BTRFS implements **only out-of-band** type.
|
|
|
|
BTRFS provides the basic building blocks for deduplication allowing other tools
|
|
to choose the strategy and scope of the deduplication. There are multiple
|
|
tools that take different approaches to deduplication, offer additional
|
|
features or make trade-offs. The following table lists tools that are known to
|
|
be up-to-date, maintained and widely used.
|
|
|
|
.. list-table::
|
|
:header-rows: 1
|
|
|
|
* - Name
|
|
- File based
|
|
- Block based
|
|
- Incremental
|
|
* - `BEES <https://github.com/Zygo/bees>`_
|
|
- No
|
|
- Yes
|
|
- Yes
|
|
* - `duperemove <https://github.com/markfasheh/duperemove>`_
|
|
- Yes
|
|
- No
|
|
- Yes
|
|
|
|
File based deduplication
|
|
------------------------
|
|
|
|
The tool takes a list of files and tries to find duplicates among data only
|
|
from these files. This is suitable e.g. for files that originated from the same
|
|
base image, source of a reflinked file. Optionally the tool could track a
|
|
database of hashes and allow to deduplicate blocks from more files, or use that
|
|
for repeated runs and update the database incrementally.
|
|
|
|
Block based deduplication
|
|
-------------------------
|
|
|
|
The tool typically scans the filesystem and builds a database of file block
|
|
hashes, then finds candidate files and deduplicates the ranges. The hash
|
|
database is kept as an ordinary file and can be scaled according to the needs.
|
|
|
|
As the files change, the hash database may get out of sync and the scan has to
|
|
be done repeatedly.
|
|
|
|
Safety of block comparison
|
|
--------------------------
|
|
|
|
The deduplication inside the filesystem is implemented as an ``ioctl`` that takes
|
|
a source file, destination file and the range. The blocks from both files are
|
|
compared for exact match before merging to the same range (i.e. there's no
|
|
hash based comparison). Pages representing the extents in memory are locked
|
|
prior to deduplication and prevent concurrent modification by buffered writes
|
|
or mmapped writes. Blocks are compared byte by byte and not using any hash-based
|
|
approach, i.e. the existing checksums are not used.
|
|
|
|
Limitations, compatibility
|
|
--------------------------
|
|
|
|
Files that are subject to deduplication must have the same status regarding
|
|
COW, i.e. both regular COW files with checksums, or both NOCOW, or files that
|
|
are COW but don't have checksums (NODATASUM attribute is set).
|
|
|
|
If the deduplication is in progress on any file in the filesystem, the *send*
|
|
operation cannot be started as it relies on the extent layout being unchanged.
|