Btrfs devel - Dec 2012 - Online Deduplication for Btrfs (Master's thesis)

Hello everyone,

my name is Martin Krizek. I am a student at Faculty of Information, Brno
University of Technology, Czech Republic. As my master''s thesis I chose
to work
on Online Deduplication for Btrfs.

My goal is to study Btrfs design, the offline deduplication patch [1] and to
come up with a design for the online dedup, this semester. I will be
implementing
the feature next semester (spring, that is).

I would like to shortly introduce my ideas on what I think the feature
should look
like.

* Use cases
The two main use cases for the dedup are:
1. virtual machine images
2. backup servers

* When to dedup
The choice of ''when to dedup'' is not up to me as the
master''s thesis
specification
states "online". :)

* What to dedup
I''d say the most reasonable is block-level deduplication as it seems
the most
general approach to me.

* Controlling dedup
- turn on/off deduplication - specify subvolumes on which
deduplication is turned on
 (mount, ioctl - inherited),
- turn on/off byte-by-byte comparison of blocks that have same hashes
(mount, ioctl),
- deduplication statistics (ioctl)

* Limitations
Not really limitations, but this is a list of situations when dedup will not
be triggered:
- encryption,
- compression - basically, dedup is kind of compression, might be worth to into
  it in the future though
- inline/prealloc extents,
- data across subvolumes

* How to store hashes
The obvious choice would be to use the checksum tree that holds block checksums
of each extent. The problem with the checksum tree is that the
checksums are looked up by logical address for the start of the extent data.
This is undesirable since it needs to be done the other way around. Logical
addresses need to be looked up by a hash.
To solve this, another key type would be created inside the checksum tree (or
maybe better, a new tree would be introduced) that
would have a hash as item''s right-hand key value. This way, items could
be
looked up on a hash:
(root, HASH_ITEM, hash)
The root value says which root (subvolume) is hashed block stored on. The hash
value is hash itself.
The item data would be of the following structure:
struct btrfs_hash_item {
__le64 disk_bytenr;
__le64 disk_num_bytes;
__le64 offset;
}
Fields disk_bytenr and disk_num_bytes would point to a
extent item of the extent allocation tree. The offset is a offset of a hashed
block in the extent.

* When to trigger dedup exactly
So It might be appropriate to delay the process just before data are
written out to disk to give data the chance to be changed. I looked a bit into
the compression code and it seems like dedup could use the similar aproach -
to have threads that would do dedup on sync or general writeback.

* Hash algorithm
sha256 seems like a safe choice.

* Future improvements
There are some features that might be considered if time permits or as something
that could be implemented in the future:
- dedup across subvolumes
- specify a hash algorithm
- specify number of deduplication blocks


I would appreciate any comments you might have, thanks!

Best regards,
Martin Krizek


[1] http://lwn.net/Articles/422331/
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Monday 17 of December 2012 13:05:01 Martin Křížek
wrote:
> * Limitations
> Not really limitations, but this is a list of situations when dedup will
> not be triggered:
> - compression - basically, dedup is kind of compression, might be worth to
> into it in the future though
I don''t see why it would be incompatible, compressed blocks are data
like
any other. COW and subvolume snapshots work with compressed nodes just as 
well as with regular ones...
> - data across subvolumes
Wasn''t the "cp --reflink" across subvolumes merged to
mainline quite a bit
ago? Under 3.6.9 it works fine for me... Also, the blocks are shared between 
subvolumes if the other subvolume is a snapshot of the first one.

Besides, I think that doing a rsync from remote server and snapshotting the 
subvolume dedicated for server will be the standard approach.

Regards,
-- 
Hubert Kario
QBS - Quality Business Software
02-656 Warszawa, ul. Ksawerów 30/85
tel. +48 (22) 646-61-51, 646-74-24
www.qbs.com.pl
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

I did some research on deduplication in the past and there are some
problems that you will face. I''ll try to list some of them (for sure
not all).

On Mon, Dec 17, 2012 at 1:05 PM, Martin Křížek <martin.krizek@gmail.com>
wrote:
> Hello everyone,
>
> my name is Martin Krizek. I am a student at Faculty of Information, Brno
> University of Technology, Czech Republic. As my master''s thesis I
chose to work
> on Online Deduplication for Btrfs.
>
> My goal is to study Btrfs design, the offline deduplication patch [1] and
to
> come up with a design for the online dedup, this semester. I will be
> implementing
> the feature next semester (spring, that is).
The offline dedup patch is quite old and won''t apply/compile anymore.
You should probably look into the clone ioctl which basically does the
same as the extent_same ioctl from the patch. Based on the clone ioctl
you can at least learn how to "inject" existing extents into other
inodes.
>
> I would like to shortly introduce my ideas on what I think the feature
> should look
> like.
>
> * Use cases
> The two main use cases for the dedup are:
> 1. virtual machine images
> 2. backup servers
>
> * When to dedup
> The choice of ''when to dedup'' is not up to me as the
master''s thesis
> specification
> states "online". :)
>
> * What to dedup
> I''d say the most reasonable is block-level deduplication as it
seems the most
> general approach to me.
Here you have two options:
1. Based on the per volume tree where you''ll find btrfs_file_extent
items which point to the global extent tree.
2. Based on the global extent tree. By using the backref resolving
code, you can find which volumes refer to these extents.
>
> * Controlling dedup
> - turn on/off deduplication - specify subvolumes on which
> deduplication is turned on
>  (mount, ioctl - inherited),
> - turn on/off byte-by-byte comparison of blocks that have same hashes
> (mount, ioctl),
> - deduplication statistics (ioctl)
You''ll get trouble when online dedup is turned on and off again. While
it is offline, extents still get written, but you won''t have your hash
tree up-to-date. You''ll need to find a way to update when dedup is
online again, without too much performance loos while
updating.
>
> * Limitations
> Not really limitations, but this is a list of situations when dedup will
not
> be triggered:
> - encryption,
I''ve already heard somewhere else that encryption+dedup is not
possible but I don''t understand why. Can someone explain this
limitation?
> - compression - basically, dedup is kind of compression, might be worth to
into
>   it in the future though
> - inline/prealloc extents,
Should be possible to dedup inline extents, but must be configurable
(e.g. minimum block size). People should also be able to completely
disable it when performance is important.
> - data across subvolumes
Should be possible. See my comment on the key in the hash
tree.
>
> * How to store hashes
> The obvious choice would be to use the checksum tree that holds block
checksums
> of each extent. The problem with the checksum tree is that the
> checksums are looked up by logical address for the start of the extent
data.
> This is undesirable since it needs to be done the other way around. Logical
> addresses need to be looked up by a hash.
> To solve this, another key type would be created inside the checksum tree
(or
> maybe better, a new tree would be introduced) that
> would have a hash as item''s right-hand key value. This way, items
could be
> looked up on a hash:
> (root, HASH_ITEM, hash)
> The root value says which root (subvolume) is hashed block stored on. The
hash
> value is hash itself.
With the root inside the key you make it impossible to allow
cross-subvolume deduplication. Also, the offset field in the key that
you plan to use for the hash is only 64bit, so you can at best store a
part of the hash in the key. You should probably split the hash into 3
parts: 64bit to put into the objectid field, 64bit to put into the
offset field and the remainder into the item data. A lookup would then
do the necessary splitting and in case a match is found also compare
the remainder found in the items data.
> The item data would be of the following structure:
> struct btrfs_hash_item {
> __le64 disk_bytenr;
> __le64 disk_num_bytes;
> __le64 offset;
> }
You could omit the offset here and and store the sum of disk_bytenr
and offset in one field. You could also omit the disk_num_bytes field
if you have a fixed dedup block length. The reason: No matter what you
store here, you never know if the referred extent is still existent
and still contains the same data. So when you found a possible
duplicate, a lookup into the extent tree is required to make sure it
is still valid. Probably the extents generation can help
here.
> Fields disk_bytenr and disk_num_bytes would point to a
> extent item of the extent allocation tree. The offset is a offset of a
hashed
> block in the extent.
>
> * When to trigger dedup exactly
> So It might be appropriate to delay the process just before data are
> written out to disk to give data the chance to be changed. I looked a bit
into
> the compression code and it seems like dedup could use the similar aproach
-
> to have threads that would do dedup on sync or general writeback.
It''s important that you avoid unnecessary writes of duplicated blocks
in case you do delayed deduplication. See my final comment for
details.
>
> * Hash algorithm
> sha256 seems like a safe choice.
Doesn''t fit into the dedup tree''s key. See my above
comments.
>
> * Future improvements
> There are some features that might be considered if time permits or as
something
> that could be implemented in the future:
> - dedup across subvolumes
> - specify a hash algorithm
> - specify number of deduplication blocks
>
>
> I would appreciate any comments you might have, thanks!
>
> Best regards,
> Martin Krizek
>
>
> [1] http://lwn.net/Articles/422331/
> --
> To unsubscribe from this list: send the line "unsubscribe
linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
After my research I came to the conclusion that a real online
deduplication feature is not worth the trouble. The only advantage of
online deduplication compared to offline deduplication is that you can
avoid unnecessary writes for duplicate data and thus increase
performance in theory. In practice, I don''t know if you really gain
much performance, because for small writes of duplicated data you
still have to write out meta data. In all cases, at least the inodes
extent items need to written, no matter if they point to new data or
duplicate data. The performance gain will only be measurable for large
duplicated blocks, in all other cases you''ll loose performance due to
the overhead of deduplication.

Storing the hashes inside a btrfs tree is also a bad idea. The hashes
are randomly distributed and thus have completely randomly ordered
keys. Lookup and insertion will be very slow when there is not enough
ram to hold the whole hash tree in memory...which is very likely to
happen. You should think about an alternative, e.g. storing the hash
table inside a dedicated inode (in a format that is more appropriate
for hash tables). But even with this solution, you''ll get out of ram
very fast. You can use bloom filters or some comparable probabilistic
data structure to avoid most of the lookups, but then you still have a
lot of insertions because no matter if a duplicate is written or not,
you need to update the hash table for later lookups.

Even if you find a good and fast solution for storing the hashes,
you''ll get in trouble when data gets overwritten or deleted. Then you
have old hash values in the hash tree/table. This means, for each
lookup you''ll also need to check if the found extent is still there
and unchanged. As an alternative, you could update the hash table
on-the-fly when data gets overwritten or deleted...but this again
means some additional lookups and writes and finally performance loss.
Also, when dedup is enabled for the first time (or after it was
disabled for some time), you have no hash table at all (or only a
partial out-of-date hash table)...what to do in this case?

Next problem is...the backref resolving code gets very slow when there
are too many references to the same block. This will slow down
everything that depends on backref resolving, e.g. scrubbing (in case
of errors), send and deduplication itself. So you''ll need to limit the
number of allowed references to each block, which may give poor
deduplication results. Probably the backref resolving code can be
optimized...I tried it but with limited results.

Then you have fragmentation...which maybe can be ignored in some cases
(e.g. for SSD''s).

In my opinion, the only acceptable deduplication solution would be
either an offline or semi online solution which basically does
periodic offline deduplication. I''m a big fan of doing this in-kernel,
because then it can use a lot of information already present. For
example, the checksums that are already present in the checksum tree
can be used as a first phase hint. Some time ago I had a in-kernel
prototype running that used this approach:

1. Run through the checksum tree and do the following for each checksum:
    a. Check if we (probably) have the checksum in bloom_filter1.
    b. If yes, add the checksum to bloom_filter2
    c. In any case, add the checksum to bloom_filter1
2. Run through the checksum tree a seconds time and do the following
for each checksum:
    a. Check if we (probably) have the checksum in bloom_filter2.
    b. If yes, put the extent info (sha256, disk_bytenr, ...) into a
list with a defined maximum size. If the list gets full, sort by hash
and write out the previously collected extents to a dedicated inode.
Then start with a fresh empty list.
3. We now have a dedicated file with multiple sorted blocks. Each
sorted block contains a list of extents. We can now do a very fast
merge sort like read and thus get a large stream of hash sorted
extents. While reading in the sorted extents, we can check if the
previous extent has the same hash as the current. If yes, we have a
duplicate.

I stopped working on that due to missing time. There are still a lot
of problems to solve with this solution which I won''t go into detail
now. The main advantages of this solution are low memory consumption
and time mostly being dependent on the number of duplicates instead of
the whole filesystem size as there is no need to hash the whole
filesystem. Also, you don''t have a permanent large table on-disk, as
you can delete the dedicated inodes after you''re finished.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Mon, Dec 17, 2012 at 06:33:24AM -0700, Alexander Block
wrote:
> I did some research on deduplication in the past and there are some
> problems that you will face. I''ll try to list some of them (for
sure
> not all).
Thanks Alexander for writing all of this up.  There are a lot of great
points here, but I''ll summarize with:

[ many challenges to online dedup ]

[ offline dedup is the best way ]

So, the big problem with offline dedup is you''re suddenly read bound. 
I
don''t disagree that offline makes a lot of the dedup problems easier,
and Alexander describes a very interesting system here.

I''ve tried to avoid features that rely on scanning though, just because
idle disk time may not really exist.  But with scrub, we have the scan
as a feature, and it may make a lot of sense to leverage that.

online dedup has a different set of tradeoffs, but as Alexander says the
hard part really is the data structure to index the hashes.  I think
there are a few different options here, including changing the file
extent pointers to point to a sha instead of a logical disk offset.

So, part of my answer really depends on where you want to go with your
thesis.  I expect the data structure work for efficient hash lookup is
going to be closer to what your course work requires?

-chris
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Mon, Dec 17, 2012 at 2:12 PM, Hubert Kario <hka@qbs.com.pl>
wrote:
> On Monday 17 of December 2012 13:05:01 Martin Křížek wrote:
>> * Limitations
>> Not really limitations, but this is a list of situations when dedup
will
>> not be triggered:
>> - compression - basically, dedup is kind of compression, might be worth
to
>> into it in the future though
>
> I don''t see why it would be incompatible, compressed blocks are
data like
> any other. COW and subvolume snapshots work with compressed nodes just as
> well as with regular ones...
>
I agree, I am not saying it''s incompatible, just that I probably
won''t
deal with that unless time permits.

Thanks,
Martin
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Mon, Dec 17, 2012 at 2:33 PM, Alexander Block <ablock84@gmail.com>
wrote:
> I did some research on deduplication in the past and there are some
> problems that you will face. I''ll try to list some of them (for
sure
> not all).
>
> On Mon, Dec 17, 2012 at 1:05 PM, Martin Křížek
<martin.krizek@gmail.com> wrote:
>> Hello everyone,
>>
>> my name is Martin Krizek. I am a student at Faculty of Information,
Brno
>> University of Technology, Czech Republic. As my master''s
thesis I chose to work
>> on Online Deduplication for Btrfs.
>>
>> My goal is to study Btrfs design, the offline deduplication patch [1]
and to
>> come up with a design for the online dedup, this semester. I will be
>> implementing
>> the feature next semester (spring, that is).
> The offline dedup patch is quite old and won''t apply/compile
anymore.
> You should probably look into the clone ioctl which basically does the
> same as the extent_same ioctl from the patch. Based on the clone ioctl
> you can at least learn how to "inject" existing extents into
other
> inodes.
I am aware of this, thanks for pointing that out though.
>>
>> I would like to shortly introduce my ideas on what I think the feature
>> should look
>> like.
>>
>> * Use cases
>> The two main use cases for the dedup are:
>> 1. virtual machine images
>> 2. backup servers
>>
>> * When to dedup
>> The choice of ''when to dedup'' is not up to me as the
master''s thesis
>> specification
>> states "online". :)
>>
>> * What to dedup
>> I''d say the most reasonable is block-level deduplication as it
seems the most
>> general approach to me.
> Here you have two options:
> 1. Based on the per volume tree where you''ll find
btrfs_file_extent
> items which point to the global extent tree.
> 2. Based on the global extent tree. By using the backref resolving
> code, you can find which volumes refer to these extents.
Agreed.
>>
>> * Controlling dedup
>> - turn on/off deduplication - specify subvolumes on which
>> deduplication is turned on
>>  (mount, ioctl - inherited),
>> - turn on/off byte-by-byte comparison of blocks that have same hashes
>> (mount, ioctl),
>> - deduplication statistics (ioctl)
> You''ll get trouble when online dedup is turned on and off again.
While
> it is offline, extents still get written, but you won''t have your
hash
> tree up-to-date. You''ll need to find a way to update when dedup is
> online again, without too much performance loos while updating.
Well, yes.
>>
>> * Limitations
>> Not really limitations, but this is a list of situations when dedup
will not
>> be triggered:
>> - encryption,
> I''ve already heard somewhere else that encryption+dedup is not
> possible but I don''t understand why. Can someone explain this
> limitation?
>> - compression - basically, dedup is kind of compression, might be worth
to into
>>   it in the future though
>> - inline/prealloc extents,
> Should be possible to dedup inline extents, but must be configurable
> (e.g. minimum block size). People should also be able to completely
> disable it when performance is important.
I agree that it''s possible, but I don''t think it''s
worth doing. You
won''t save much storage that way.
>> - data across subvolumes
> Should be possible. See my comment on the key in the hash tree.
Again, I agree that it''s possible but this would be something I
probably won''t go into.
>>
>> * How to store hashes
>> The obvious choice would be to use the checksum tree that holds block
checksums
>> of each extent. The problem with the checksum tree is that the
>> checksums are looked up by logical address for the start of the extent
data.
>> This is undesirable since it needs to be done the other way around.
Logical
>> addresses need to be looked up by a hash.
>> To solve this, another key type would be created inside the checksum
tree (or
>> maybe better, a new tree would be introduced) that
>> would have a hash as item''s right-hand key value. This way,
items could be
>> looked up on a hash:
>> (root, HASH_ITEM, hash)
>> The root value says which root (subvolume) is hashed block stored on.
The hash
>> value is hash itself.
> With the root inside the key you make it impossible to allow
> cross-subvolume deduplication. Also, the offset field in the key that
> you plan to use for the hash is only 64bit, so you can at best store a
> part of the hash in the key. You should probably split the hash into 3
> parts: 64bit to put into the objectid field, 64bit to put into the
> offset field and the remainder into the item data. A lookup would then
> do the necessary splitting and in case a match is found also compare
> the remainder found in the items data.
Right, I thought of this but somehow forgot to mention it. Yes, the
hash would need to be split if it does not fit into the offset. Thanks
for noticing.
>> The item data would be of the following structure:
>> struct btrfs_hash_item {
>> __le64 disk_bytenr;
>> __le64 disk_num_bytes;
>> __le64 offset;
>> }
> You could omit the offset here and and store the sum of disk_bytenr
> and offset in one field. You could also omit the disk_num_bytes field
> if you have a fixed dedup block length. The reason: No matter what you
> store here, you never know if the referred extent is still existent
> and still contains the same data. So when you found a possible
> duplicate, a lookup into the extent tree is required to make sure it
> is still valid. Probably the extents generation can help here.
Good points.
>> Fields disk_bytenr and disk_num_bytes would point to a
>> extent item of the extent allocation tree. The offset is a offset of a
hashed
>> block in the extent.
>>
>> * When to trigger dedup exactly
>> So It might be appropriate to delay the process just before data are
>> written out to disk to give data the chance to be changed. I looked a
bit into
>> the compression code and it seems like dedup could use the similar
aproach -
>> to have threads that would do dedup on sync or general writeback.
> It''s important that you avoid unnecessary writes of duplicated
blocks
> in case you do delayed deduplication. See my final comment for
> details.
>>
>> * Hash algorithm
>> sha256 seems like a safe choice.
> Doesn''t fit into the dedup tree''s key. See my above
comments.
>>
>> * Future improvements
>> There are some features that might be considered if time permits or as
something
>> that could be implemented in the future:
>> - dedup across subvolumes
>> - specify a hash algorithm
>> - specify number of deduplication blocks
>>
>>
>> I would appreciate any comments you might have, thanks!
>>
>> Best regards,
>> Martin Krizek
>>
>>
>> [1] http://lwn.net/Articles/422331/
>> --
>> To unsubscribe from this list: send the line "unsubscribe
linux-btrfs" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
> After my research I came to the conclusion that a real online
> deduplication feature is not worth the trouble. The only advantage of
> online deduplication compared to offline deduplication is that you can
> avoid unnecessary writes for duplicate data and thus increase
> performance in theory. In practice, I don''t know if you really
gain
> much performance, because for small writes of duplicated data you
> still have to write out meta data. In all cases, at least the inodes
> extent items need to written, no matter if they point to new data or
> duplicate data. The performance gain will only be measurable for large
> duplicated blocks, in all other cases you''ll loose performance due
to
> the overhead of deduplication.
>
> Storing the hashes inside a btrfs tree is also a bad idea. The hashes
> are randomly distributed and thus have completely randomly ordered
> keys. Lookup and insertion will be very slow when there is not enough
> ram to hold the whole hash tree in memory...which is very likely to
> happen. You should think about an alternative, e.g. storing the hash
> table inside a dedicated inode (in a format that is more appropriate
> for hash tables). But even with this solution, you''ll get out of
ram
> very fast. You can use bloom filters or some comparable probabilistic
> data structure to avoid most of the lookups, but then you still have a
> lot of insertions because no matter if a duplicate is written or not,
> you need to update the hash table for later lookups.
>
> Even if you find a good and fast solution for storing the hashes,
> you''ll get in trouble when data gets overwritten or deleted. Then
you
> have old hash values in the hash tree/table. This means, for each
> lookup you''ll also need to check if the found extent is still
there
> and unchanged. As an alternative, you could update the hash table
> on-the-fly when data gets overwritten or deleted...but this again
> means some additional lookups and writes and finally performance loss.
> Also, when dedup is enabled for the first time (or after it was
> disabled for some time), you have no hash table at all (or only a
> partial out-of-date hash table)...what to do in this case?
>
> Next problem is...the backref resolving code gets very slow when there
> are too many references to the same block. This will slow down
> everything that depends on backref resolving, e.g. scrubbing (in case
> of errors), send and deduplication itself. So you''ll need to limit
the
> number of allowed references to each block, which may give poor
> deduplication results. Probably the backref resolving code can be
> optimized...I tried it but with limited results.
>
> Then you have fragmentation...which maybe can be ignored in some cases
> (e.g. for SSD''s).
>
> In my opinion, the only acceptable deduplication solution would be
> either an offline or semi online solution which basically does
> periodic offline deduplication. I''m a big fan of doing this
in-kernel,
> because then it can use a lot of information already present. For
> example, the checksums that are already present in the checksum tree
> can be used as a first phase hint. Some time ago I had a in-kernel
> prototype running that used this approach:
>
> 1. Run through the checksum tree and do the following for each checksum:
>     a. Check if we (probably) have the checksum in bloom_filter1.
>     b. If yes, add the checksum to bloom_filter2
>     c. In any case, add the checksum to bloom_filter1
> 2. Run through the checksum tree a seconds time and do the following
> for each checksum:
>     a. Check if we (probably) have the checksum in bloom_filter2.
>     b. If yes, put the extent info (sha256, disk_bytenr, ...) into a
> list with a defined maximum size. If the list gets full, sort by hash
> and write out the previously collected extents to a dedicated inode.
> Then start with a fresh empty list.
> 3. We now have a dedicated file with multiple sorted blocks. Each
> sorted block contains a list of extents. We can now do a very fast
> merge sort like read and thus get a large stream of hash sorted
> extents. While reading in the sorted extents, we can check if the
> previous extent has the same hash as the current. If yes, we have a
> duplicate.
>
I am not really following this as I am not familiar with bloom
filters, I will need to get back to it later. Thanks for sharing.
> I stopped working on that due to missing time. There are still a lot
> of problems to solve with this solution which I won''t go into
detail
> now. The main advantages of this solution are low memory consumption
> and time mostly being dependent on the number of duplicates instead of
> the whole filesystem size as there is no need to hash the whole
> filesystem. Also, you don''t have a permanent large table on-disk,
as
> you can delete the dedicated inodes after you''re finished.
Thanks for your comments!
Martin
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

On Tue, Dec 18, 2012 at 2:31 AM, Chris Mason <chris.mason@fusionio.com>
wrote:
> On Mon, Dec 17, 2012 at 06:33:24AM -0700, Alexander Block wrote:
>> I did some research on deduplication in the past and there are some
>> problems that you will face. I''ll try to list some of them
(for sure
>> not all).
>
> Thanks Alexander for writing all of this up.  There are a lot of great
> points here, but I''ll summarize with:
>
> [ many challenges to online dedup ]
>
> [ offline dedup is the best way ]
>
> So, the big problem with offline dedup is you''re suddenly read
bound.  I
> don''t disagree that offline makes a lot of the dedup problems
easier,
> and Alexander describes a very interesting system here.
>
> I''ve tried to avoid features that rely on scanning though, just
because
> idle disk time may not really exist.  But with scrub, we have the scan
> as a feature, and it may make a lot of sense to leverage that.
>
> online dedup has a different set of tradeoffs, but as Alexander says the
> hard part really is the data structure to index the hashes.  I think
> there are a few different options here, including changing the file
> extent pointers to point to a sha instead of a logical disk offset.
>
I am not sure if I am following the approach with replacing the
pointers, could you please explain?

I agree that the data structure is the key part in designing the feature.
> So, part of my answer really depends on where you want to go with your
> thesis.  I expect the data structure work for efficient hash lookup is
> going to be closer to what your course work requires?
No, I don''t think it is really necessary that the data structure
should be close to my course work. What is your opinion on the most
suitable data structure to index the hashes?

Thanks!
Martin
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Hi,

I am looking for a place (source code wise) where the actual
online/immediate dedup would happen:
-- splitting an extent about to be written into new extents that are
unique (that would be actually written) and into blocks of the
original extent that would be thrown away (duplicates) and
file_extent_item pointing to portion of existing extent created
instead.

Could anyone please give me some pointers on that place and/or
functions that could be used for that? Would delalloc time would be
appropriate?

Thanks!
Martin
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html