3 ms·

The deduplication code works, but each deduplication operation requires 3 serial IOS to lookup the information needed to check if deduplication is possible and

by ryao 11y ago

The deduplication code works, but each deduplication operation requires 3 serial IOS to lookup the information needed to check if deduplication is possible and if they are in aches, that becomes painful fast on storage with low IOPS. On my workstation where I have enough memory that the results of all of the lookups naturally fit and high IOPS storage, the deduplication code runs well. You would have a similar problem designing a system that perfectly deduplicates data at the record level if you tried.

infogulch 11y ago
I was thinking about this. To reduce both the huge ram usage and serial IOs you could use something similar to a Bloom filter to quickly test whether you should attempt to dedup a new block. If the filter says it's not a duplicate, then completely skip the standard (slow) dedup path. Bloom filters specifically have issues: they don't permit removing entries for one, and they're not really that efficient. But there's a paper about Cuckoo Filters which seems to solve both of these problems. For example: The "semi-sort" variant of the cuckoo filter benchmarked in the paper has a size of 192 MB and holds 128M items. So for 8kb blocks, it can dedup 1TB of blocks. More if you increase the block size or the size of the table. It has a 0.09% false-positive rate (!). I.e. unique blocks would use the slow path to test for duplication in vain only once in 1111 writes. The algorithm can perform 6 million lookups per second on the benchmark hardware. (2x Xeons at 2.27GHz, 12MB L3, 32 GB DRAM) This is assuming that the majority of writes are actually unique, and dedup is more of a "it would be nice" thing than essential. But for that case something like this would be a lot easier to implement and use far fewer resources. Just stick it in front of the existing dedup lookup and early-exit if the filter says it's not duplicate. [0]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

by ryao 11y ago

infogulch 11y ago

I was thinking about this. To reduce both the huge ram usage and serial IOs you could use something similar to a Bloom filter to quickly test whether you should attempt to dedup a new block. If the filter says it's not a duplicate, then completely skip the standard (slow) dedup path. Bloom filters specifically have issues: they don't permit removing entries for one, and they're not really that efficient. But there's a paper about Cuckoo Filters which seems to solve both of these problems. For example: The "semi-sort" variant of the cuckoo filter benchmarked in the paper has a size of 192 MB and holds 128M items. So for 8kb blocks, it can dedup 1TB of blocks. More if you increase the block size or the size of the table. It has a 0.09% false-positive rate (!). I.e. unique blocks would use the slow path to test for duplication in vain only once in 1111 writes. The algorithm can perform 6 million lookups per second on the benchmark hardware. (2x Xeons at 2.27GHz, 12MB L3, 32 GB DRAM) This is assuming that the majority of writes are actually unique, and dedup is more of a "it would be nice" thing than essential. But for that case something like this would be a lot easier to implement and use far fewer resources. Just stick it in front of the existing dedup lookup and early-exit if the filter says it's not duplicate. [0]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf