| 1 |
% bup-margin(1) Bup %BUP_VERSION% |
| 2 |
% Avery Pennarun <[email protected]> |
| 3 |
% %BUP_DATE% |
| 4 |
|
| 5 |
# NAME |
| 6 |
|
| 7 |
bup-margin - figure out your deduplication safety margin |
| 8 |
|
| 9 |
# SYNOPSIS |
| 10 |
|
| 11 |
bup margin [options...] |
| 12 |
|
| 13 |
# DESCRIPTION |
| 14 |
|
| 15 |
`bup margin` iterates through all objects in your bup |
| 16 |
repository, calculating the largest number of prefix bits |
| 17 |
shared between any two entries. This number, `n`, |
| 18 |
identifies the longest subset of SHA-1 you could use and still |
| 19 |
encounter a collision between your object ids. |
| 20 |
|
| 21 |
For example, one system that was tested had a collection of |
| 22 |
11 million objects (70 GB), and `bup margin` returned 45. |
| 23 |
That means a 46-bit hash would be sufficient to avoid all |
| 24 |
collisions among that set of objects; each object in that |
| 25 |
repository could be uniquely identified by its first 46 |
| 26 |
bits. |
| 27 |
|
| 28 |
The number of bits needed seems to increase by about 1 or 2 |
| 29 |
for every doubling of the number of objects. Since SHA-1 |
| 30 |
hashes have 160 bits, that leaves 115 bits of margin. Of |
| 31 |
course, because SHA-1 hashes are essentially random, it's |
| 32 |
theoretically possible to use many more bits with far fewer |
| 33 |
objects. |
| 34 |
|
| 35 |
If you're paranoid about the possibility of SHA-1 |
| 36 |
collisions, you can monitor your repository by running `bup |
| 37 |
margin` occasionally to see if you're getting dangerously |
| 38 |
close to 160 bits. |
| 39 |
|
| 40 |
# OPTIONS |
| 41 |
|
| 42 |
\--predict |
| 43 |
: Guess the offset into each index file where a |
| 44 |
particular object will appear, and report the maximum |
| 45 |
deviation of the correct answer from the guess. This |
| 46 |
is potentially useful for tuning an interpolation |
| 47 |
search algorithm. |
| 48 |
|
| 49 |
\--ignore-midx |
| 50 |
: don't use `.midx` files, use only `.idx` files. This is |
| 51 |
only really useful when used with `--predict`. |
| 52 |
|
| 53 |
|
| 54 |
# EXAMPLES |
| 55 |
$ bup margin |
| 56 |
Reading indexes: 100.00% (1612581/1612581), done. |
| 57 |
40 |
| 58 |
40 matching prefix bits |
| 59 |
1.94 bits per doubling |
| 60 |
120 bits (61.86 doublings) remaining |
| 61 |
4.19338e+18 times larger is possible |
| 62 |
|
| 63 |
Everyone on earth could have 625878182 data sets |
| 64 |
like yours, all in one repository, and we would |
| 65 |
expect 1 object collision. |
| 66 |
|
| 67 |
$ bup margin --predict |
| 68 |
PackIdxList: using 1 index. |
| 69 |
Reading indexes: 100.00% (1612581/1612581), done. |
| 70 |
915 of 1612581 (0.057%) |
| 71 |
|
| 72 |
|
| 73 |
# SEE ALSO |
| 74 |
|
| 75 |
`bup-midx`(1), `bup-save`(1) |
| 76 |
|
| 77 |
# BUP |
| 78 |
|
| 79 |
Part of the `bup`(1) suite. |