On Wed, May 13, 2015 at 09:23:25AM -0700, Learner Study wrote: > I have been reading on de-duplication and how algorithms such as Bloom > and Cuckoo filters are used for this purpose. > > Does BTRFS dedup use any of these, or are there plans to incorporate > these in future? btrfs dedup currently lives in user space, and there are multiple dedup userspace projects in development. Administrators can choose the dedup tool, and can use multiple dedup tools on the same filesystem. This is particularly handy if you know something about your data that a naive hashing algorithm might not (e.g. you have two large trees derived from a common base, so you can use a much more efficient algorithm than you would if you knew nothing about the data). The basic kernel interface for dedup is the extent-same ioctl. A userspace program creates a list of (fd, length, offset) tuples referencing identical content and passes them to the kernel. The kernel locks the file contents, compares them, and replaces identical data copies with references to a single extent in an atomic operation. The kernel also provides interfaces to efficiently discover recently modified extents in a filesystem, enabling deduplicators to follow new data without the need to block writes. Most btrfs deduplicators are based on a block-level hash table built by scanning files, but every other aspect of the tools (e.g. the mechanism by which files are discovered, block sizes, scalability, use of prefiltering algorithms such as Bloom filters, whether the hash table is persistent or ephemeral, etc) is different from one tool to another, and changing over time as the tools are developed. Because the kernel interface implies a read of both copies of duplicate data, it is not necessary to use a collision-free hash. Optimizing the number of bits in the hash function for the size of the filesystem and exploiting the statistical tendency for identical blocks to be adjacent to other identical blocks in files enables considerable space efficiency in the hash table--possibly so much that the Bloom/Cuckoo-style pre-filtering benefit becomes irrelevant. I'm not aware of a released btrfs deduplicator that currently exploits these optimizations. > Thanks for your guidance! > -- > To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in > the body of a message to majordomo@xxxxxxxxxxxxxxx > More majordomo info at http://vger.kernel.org/majordomo-info.html
Attachment:
signature.asc
Description: Digital signature
