New feature Idea
I have been thinking about a new feature to start work on that I am interested in and I was hoping people could give me some feedback and ideas of how to tackle it. Anyways, I want to create a data deduplication system that can work in two different modes. One mode is that when the system is idle or not beyond a set load point a background process would scan the volume for duplicate blocks. The other mode would be used for systems that are nearline or backup systems that don't really care about the performance and it would do the deduplication during block allocation.
One of the ways I was thinking of to find the duplicate blocks would be to use the checksums as a quick compare. If the checksums match then do a complete compare before adjusting the nodes on the files. However, I believe that I will need to create a tree based on the checksum values.
So any other ideas and thoughts about this?
Thanks,
Morey
Quoted 5 lines · Morey Roof
I have been thinking about a new feature to start work on that I am interested in and I was hoping people could give me some feedback and ideas of how to tackle it. Anyways, I want to create a data deduplication system that can work in two different modes. One mode is that when the system is idle or not beyond a set load point a background process would scan the volume for duplicate blocks. The other mode would be used for systems that are nearline or backup systems that don't really care about the performance and it would do the deduplication during block allocation.
One of the ways I was thinking of to find the duplicate blocks would be to use the checksums as a quick compare. If the checksums match then do a complete compare before adjusting the nodes on the files. However, I believe that I will need to create a tree based on the checksum values.
So any other ideas and thoughts about this?
This is something that I'm very interested in myself.
Mainly for backup purposes but the background deduplication scheme is also interesting and something I had not thought of.
Jeff
Quoted 5 lines · Morey Roof
I have been thinking about a new feature to start work on that I am interested in and I was hoping people could give me some feedback and ideas of how to tackle it. Anyways, I want to create a data deduplication system that can work in two different modes. One mode is that when the system is idle or not beyond a set load point a background process would scan the volume for duplicate blocks. The other mode would be used for systems that are nearline or backup systems that don't really care about the performance and it would do the deduplication during block allocation.
One of the ways I was thinking of to find the duplicate blocks would be to use the checksums as a quick compare. If the checksums match then do a complete compare before adjusting the nodes on the files. However, I believe that I will need to create a tree based on the checksum values.
So any other ideas and thoughts about this?
Don't do it!!!
OK, I know Chris has described some block sharing. But I hate it.
If I copy "resume" to "resume.save", it is because I want 2 copies for safety. I don't want the fs to reduce it to 1 copy. And reducing the duplicates is exactly opposite to Chris's paranoid make-multiple-copies-by-default.
Now feel free to tell me I'm an idiot (other people do) :)
jim
Quoted 10 lines
Don't do it!!!
OK, I know Chris has described some block sharing. But I hate it.
If I copy "resume" to "resume.save", it is because I want 2 copies for safety. I don't want the fs to reduce it to 1 copy. And reducing the duplicates is exactly opposite to Chris's paranoid make-multiple-copies-by-default.
Now feel free to tell me I'm an idiot (other people do) :)
I would imagine that it would be optional and at worst, a specialized fork of btrfs that follows the mainline but adds the deduplication bits.
Jeff
Quoted 8 lines · jim owens
Don't do it!!!
OK, I know Chris has described some block sharing. But I hate it.
If I copy "resume" to "resume.save", it is because I want 2 copies for safety. I don't want the fs to reduce it to 1 copy. And reducing the duplicates is exactly opposite to Chris's paranoid make-multiple-copies-by-default.
Hi Jim,
My thoughts on what you are saying is that it is not generally a good idea to assume any filesystem will lay things out in any specific way, including whether it has one-to-one mapping of files to blocks. In other words, making a copy of a file on the same filesystem for safety reasons (unless you are modifying a file and want a backup of its old state, like emacs' ~ files) is probably not a great habit to get into.
The implementation details of how a filesystem makes things safer should be behind-the-scenes (like checksums, multiple-copies-by-default, mirroring, etc.). That way, you can simply rely on the filesystem to manage protection of your data rather than going to the effort of managing multiple copies of files yourself for that reason.
-Joe
I was hoping to have it specified as a set of mount options or defaults controlled in the super block so that if you want to use it you can otherwise it doesn't exist.
-Morey
Quoted 15 lines · Jeff Fisher
Quoted 10 lines
Don't do it!!!
OK, I know Chris has described some block sharing. But I hate it.
If I copy "resume" to "resume.save", it is because I want 2 copies for safety. I don't want the fs to reduce it to 1 copy. And reducing the duplicates is exactly opposite to Chris's paranoid make-multiple-copies-by-default.
Now feel free to tell me I'm an idiot (other people do) :)
I would imagine that it would be optional and at worst, a specialized fork of btrfs that follows the mainline but adds the deduplication bits.
Jeff
Quoted 10 lines
Don't do it!!!
OK, I know Chris has described some block sharing. But I hate it.
If I copy "resume" to "resume.save", it is because I want 2 copies for safety. I don't want the fs to reduce it to 1 copy. And reducing the duplicates is exactly opposite to Chris's paranoid make-multiple-copies-by-default.
Now feel free to tell me I'm an idiot (other people do) :)
In situations where there's non-trivial benefits to some workloads, but also non-trivial drawbacks, it strikes me as something that could be enabled and disabled as a mount option, like data=ordered.
Quoted 7 lines · Joe Peterson
My thoughts on what you are saying is that it is not generally a good idea to assume any filesystem will lay things out in any specific way, including whether it has one-to-one mapping of files to blocks. In other words, making a copy of a file on the same filesystem for safety reasons (unless you are modifying a file and want a backup of its old state, like emacs' ~ files) is probably not a great habit to get into.
Quoted 5 lines
The implementation details of how a filesystem makes things safer should be behind-the-scenes (like checksums, multiple-copies-by-default, mirroring, etc.). That way, you can simply rely on the filesystem to manage protection of your data rather than going to the effort of managing multiple copies of files yourself for that reason.
I'm a filesystem guy so I only use ones I know do what I want, I never trust ones I don't know about :)
I agree with you about the danger of assuming what a filesystem will or won't do on local copies. I also fear that 99% of normal users have an expectation that making a copy makes a new physical instance (which of course is not safe if the device crashes either).
I hate dealing with customers that have lost their data because of the filesystem.
Quoted 1 line · Morey Roof
I was hoping to have it specified as a set of mount options or defaults controlled in the super block so that if you want to use it you can otherwise it doesn't exist.
I don't have veto power in btrfs so my aversion means nothing.
As you say, there are a number of good ways to control it.
If you pursue this, I might suggest having a dedup limit so they can say "keep at least 2 copies" or "just one".
jim
This would be a kind of filesystem block level compression, right?
Quoted 20 lines · On Wed, Aug 13, 2008 at 12:28 PM, <[email protected]> wrote:
Quoted 10 lines
Don't do it!!!
OK, I know Chris has described some block sharing. But I hate it.
If I copy "resume" to "resume.save", it is because I want 2 copies for safety. I don't want the fs to reduce it to 1 copy. And reducing the duplicates is exactly opposite to Chris's paranoid make-multiple-copies-by-default.
Now feel free to tell me I'm an idiot (other people do) :)
In situations where there's non-trivial benefits to some workloads, but also non-trivial drawbacks, it strikes me as something that could be enabled and disabled as a mount option, like data=ordered.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 31 lines · jim owens
Quoted 7 lines · Joe Peterson
My thoughts on what you are saying is that it is not generally a good idea to assume any filesystem will lay things out in any specific way, including whether it has one-to-one mapping of files to blocks. In other words, making a copy of a file on the same filesystem for safety reasons (unless you are modifying a file and want a backup of its old state, like emacs' ~ files) is probably not a great habit to get into.
Quoted 5 lines
The implementation details of how a filesystem makes things safer should be behind-the-scenes (like checksums, multiple-copies-by-default, mirroring, etc.). That way, you can simply rely on the filesystem to manage protection of your data rather than going to the effort of managing multiple copies of files yourself for that reason.
I'm a filesystem guy so I only use ones I know do what I want, I never trust ones I don't know about :)
I agree with you about the danger of assuming what a filesystem will or won't do on local copies. I also fear that 99% of normal users have an expectation that making a copy makes a new physical instance (which of course is not safe if the device crashes either).
I hate dealing with customers that have lost their data because of the filesystem.
Quoted 3 lines · Morey Roof
I was hoping to have it specified as a set of mount options or defaults controlled in the super block so that if you want to use it you can otherwise it doesn't exist.
Quoted 8 lines
I don't have veto power in btrfs so my aversion means nothing.
As you say, there are a number of good ways to control it.
If you pursue this, I might suggest having a dedup limit so they can say "keep at least 2 copies" or "just one".
jim
This is an interesting idea. Perhaps we could tie this in a little closer to the protection systems in btrfs so that depending on the type of protection chosen the dedup will try to match it.
However, I need to start figuring out a prototype for this which is what I started this thread for.
-Morey
It is the same idea for the way space efficient snapshots work currently in btrfs. I'm just planning out a way to make a process got find them and link them together and increase the reference counts and another method for having the allocator do it while writing.
-Morey
Quoted 27 lines · Kevin Cantu
This would be a kind of filesystem block level compression, right?
Quoted 11 lines · On Wed, Aug 13, 2008 at 12:28 PM, <[email protected]> wrote:
Quoted 10 lines
Don't do it!!!
OK, I know Chris has described some block sharing. But I hate it.
If I copy "resume" to "resume.save", it is because I want 2 copies for safety. I don't want the fs to reduce it to 1 copy. And reducing the duplicates is exactly opposite to Chris's paranoid make-multiple-copies-by-default.
Now feel free to tell me I'm an idiot (other people do) :)
Quoted 9 lines
In situations where there's non-trivial benefits to some workloads, but also non-trivial drawbacks, it strikes me as something that could be enabled and disabled as a mount option, like data=ordered.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 9 lines · Morey Roof
I have been thinking about a new feature to start work on that I am interested in and I was hoping people could give me some feedback and ideas of how to tackle it. Anyways, I want to create a data deduplication system that can work in two different modes. One mode is that when the system is idle or not beyond a set load point a background process would scan the volume for duplicate blocks. The other mode would be used for systems that are nearline or backup systems that don't really care about the performance and it would do the deduplication during block allocation.
Seems like a special case of compression? Perhaps compression would help more?
Quoted 5 lines
One of the ways I was thinking of to find the duplicate blocks would be to use the checksums as a quick compare. If the checksums match then do a complete compare before adjusting the nodes on the files. However, I believe that I will need to create a tree based on the checksum values.
If you really want to do deduplication: It might be advantageous to do this on larger units.
If you assume that data is usually shared between similar files (which is a reasonable assumption) and do the deduplication on whole files you can also use the size as an index and avoid checksumming all files with a unique size. I wrote a user level duplicated file checker some time ago that used this trick successfully.
-Andi
Quoted 24 lines · Andi Kleen
Quoted 9 lines · Morey Roof
I have been thinking about a new feature to start work on that I am interested in and I was hoping people could give me some feedback and ideas of how to tackle it. Anyways, I want to create a data deduplication system that can work in two different modes. One mode is that when the system is idle or not beyond a set load point a background process would scan the volume for duplicate blocks. The other mode would be used for systems that are nearline or backup systems that don't really care about the performance and it would do the deduplication during block allocation.
Seems like a special case of compression? Perhaps compression would help more?
Quoted 5 lines
One of the ways I was thinking of to find the duplicate blocks would be to use the checksums as a quick compare. If the checksums match then do a complete compare before adjusting the nodes on the files. However, I believe that I will need to create a tree based on the checksum values.
If you really want to do deduplication: It might be advantageous to do this on larger units.
Quoted 7 lines
If you assume that data is usually shared between similar files (which is a reasonable assumption) and do the deduplication on whole files you can also use the size as an index and avoid checksumming all files with a unique size. I wrote a user level duplicated file checker some time ago that used this trick successfully.
-Andi
I would like to use the tree in a similar fashion as the way snapshots are handled. Also, I want to catch blocks that exist in different files.
Say, you have several Virtual Machine Disk files on the volume. Those virtual machine disk files may not be the same in terms of files but if the are virtual machines that are both running the same operating system then some of the blocks/extents are going to be the same and I want to be able to dedup them.
-Morey
Quoted 20 lines · jim owens
Quoted 10 lines · Morey Roof
I have been thinking about a new feature to start work on that I am interested in and I was hoping people could give me some feedback and ideas of how to tackle it. Anyways, I want to create a data deduplication system that can work in two different modes. One mode is that when the system is idle or not beyond a set load point a background process would scan the volume for duplicate blocks. The other mode would be used for systems that are nearline or backup systems that don't really care about the performance and it would do the deduplication during block allocation.
Quoted 6 lines
One of the ways I was thinking of to find the duplicate blocks would be to use the checksums as a quick compare. If the checksums match then do a complete compare before adjusting the nodes on the files. However, I believe that I will need to create a tree based on the checksum values.
So any other ideas and thoughts about this?
Don't do it!!!
Quoted 8 lines
OK, I know Chris has described some block sharing. But I hate it.
If I copy "resume" to "resume.save", it is because I want 2 copies for safety. I don't want the fs to reduce it to 1 copy. And reducing the duplicates is exactly opposite to Chris's paranoid make-multiple-copies-by-default.
Now feel free to tell me I'm an idiot (other people do) :)
Grin, the C in cow does stand for something after all. It is pretty darn hard to overwrite existing bytes in a file in btrfs without mount -o nodatacow.
There isn't any difference between dedup and a snapshot from a data protection point of view.
With that in said, maintaining all the machinery for dedup is definitely non-trivial, and I haven't yet convinced myself it wouldn't be better done at higher layers. We already have the cow-single-file ioctl, why not have a userland process go around and create cow links between identical files.
File granularity is not well suited to dedup when files differ by only a few blocks, but I'd want to see some numbers on how often that happens before carrying around the disk format needed to do block level dedup.
-chris
Quoted 5 lines
With that in said, maintaining all the machinery for dedup is definitely non-trivial, and I haven't yet convinced myself it wouldn't be better done at higher layers. We already have the cow-single-file ioctl, why not have a userland process go around and create cow links between identical files.
Can verification + cow-single-file be done atomically with the existing ioctl? Pushing this out into userspace seems reasonable enough, but not if it gives a malicious user a window where they can alter part of their file and have it CoW'd into everyone else's copy.
Is this a 1.0 feature?
Quoted 4 lines
File granularity is not well suited to dedup when files differ by only a few blocks, but I'd want to see some numbers on how often that happens before carrying around the disk format needed to do block level dedup.
I was imagining that one could easily make a flag to debug-tree which caused it to just dump the file block checksums from the extent items, maybe restricted to a given subvol. Pipe that through sort and uniq -c and you have a pretty easy path to a rough histogram of checksum values.
But I sort of wonder if the point isn't to dedup systems that were deployed on previous-generation file systems. If people knew that dedup worked, they might be able to more easily deploy simpler systems that didn't have to be so careful at, say, maintaining hard link farms.
I dunno, just a thought.
- z
Quoted 10 lines · Zach Brown
Quoted 4 lines
File granularity is not well suited to dedup when files differ by only a few blocks, but I'd want to see some numbers on how often that happens before carrying around the disk format needed to do block level dedup.
I was imagining that one could easily make a flag to debug-tree which caused it to just dump the file block checksums from the extent items, maybe restricted to a given subvol. Pipe that through sort and uniq -c and you have a pretty easy path to a rough histogram of checksum values.
Quoted 9 lines
But I sort of wonder if the point isn't to dedup systems that were deployed on previous-generation file systems. If people knew that dedup worked, they might be able to more easily deploy simpler systems that didn't have to be so careful at, say, maintaining hard link farms.
I dunno, just a thought.
- z
Well, if we look at NetApp's claims dedup can be pretty useful. Also, it really depends on what kinds of data workload the volume is being used for. People claim that they often see a size reduction of about 40%-80% of the space used when they have volumes that store virtual machine disk files.
Chris, I would like to go ahead and make a small simple prototype for this and see how it works before just ruling it out of the code base.
-Morey
Quoted 9 lines · Zach Brown
Quoted 3 lines
File granularity is not well suited to dedup when files differ by only a few blocks, but I'd want to see some numbers on how often that happens before carrying around the disk format needed to do block level dedup.
I was imagining that one could easily make a flag to debug-tree which caused it to just dump the file block checksums from the extent items, maybe restricted to a given subvol. Pipe that through sort and uniq -c and you have a pretty easy path to a rough histogram of checksum values.
Quoted 6 lines
But I sort of wonder if the point isn't to dedup systems that were deployed on previous-generation file systems. If people knew that dedup worked, they might be able to more easily deploy simpler systems that didn't have to be so careful at, say, maintaining hard link farms.
I dunno, just a thought.
The backup and virtualization use cases are why I've still got it on the table for consideration at least. Especially virtualization because there you'll tend to have large disk image files that have tiny changes between each other.
-chris