<br>I may be mistaken, but I heard at one time that rsync was noticeably slower when asked to preserve hard links.  I'm guessing this is a matter of CPU requirements rather than I/O requirements, but that's just a guess.<br>
<br>You can go a long way toward detecting hardlinks by just watching for st_nlink > 1 from fstat().<br><br>Another way, one that only bothers with hardlinks that are part of a transfer, uses bloom filters.  You stash a inode#,device# pair in the filter.<br>
<br>A bloom filter is a probabilistic set datastructure.   You can't iterate over its elements (it doesn't store them all), but you can add elements and test candidate elements for membership.  The chief advantage is that you can have storage requirements as low as one bit per element "stored".<br>
<br>When you do a set membership test, a bloom filter can give one of two answers: "This element is definitely not in the set" or "This element is almost definitely in the set".<br><br>Detecting hardlinks is a good use of a bloom filter, because all you really want to do is cut down on the number of things you need to store in an array/list.  It's OK to have a few things in the list that aren't really hardlinks - the goal is chiefly to dramatically cut down on the storage requirements, and avoid a large sort() or O(file_count) hash table.  That's where the "filter" part of the name comes from - it's filtering the count of the objects of interest down to a more manageable size.<br>
<br><div class="gmail_quote">On Tue, Aug 7, 2012 at 9:07 PM, Linda Walsh <span dir="ltr"><<a href="mailto:rsync@tlinx.org" target="_blank">rsync@tlinx.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im"><br>
<br>
Dan Stromberg wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
FWIW, it might be nice to add a hardlink detecting bloom filter to rsync at some point.  This makes the process of detecting hardlinks less expensive.  Another way to narrow down the field is to just look at st_nlink.<br>

</blockquote></div>
----<br>
        What's a bloom filter? and how / why would it make things<br>
less expensive?  I don't understand why it is expensive now?  You have<br>
to visit all files -- likely a previsit to get a size estimate -- reading<br>
all the inodes at that point,<br>
<br>
Then have a hash 'ino2names' for each inode to point to an array name of files<br>
found in the tree with the same inode<br>
<br>
%ino2names<br>
$ino2names=>[array of paths relative to root of tree being examined]<br>
<br>
Since the size of the transfer is known after the initial scan -- all the inode<br>
inode->path mapping would be knowable as well, at that point.  No extra expense involved.<br>
<br>
Of course given the error I reported, it seems rsync has gotten broken, recently<br>
with hard links -- they aren't that difficult.  It is presumed, that links 'out of tree'<br>
are ignored @ source and target -- meaning target files end up with same internal<br>
linkages as on source, and any external links would be broken.<br>
<br>
I still have no clue what a bloom filter is?? ;-)  Cluesticks anyone?<br>
<br>
<br>
<br>
</blockquote></div><br>