lib/bup/bloom.py

   1 """Discussion of bloom constants for bup:
   2
   3 There are four basic things to consider when building a bloom filter:
   4 The size, in bits, of the filter
   5 The capacity, in entries, of the filter
   6 The probability of a false positive that is tolerable
   7 The number of bits readily available to use for addresing filter bits
   8
   9 There is one major tunable that is not directly related to the above:
  10 k: the number of bits set in the filter per entry
  11
  12 Here's a wall of numbers showing the relationship between k; the ratio between
  13 the filter size in bits and the entries in the filter; and pfalse_positive:
  14
  15 mn|k=3    |k=4    |k=5    |k=6    |k=7    |k=8    |k=9    |k=10   |k=11
  16  8|3.05794|2.39687|2.16792|2.15771|2.29297|2.54917|2.92244|3.41909|4.05091
  17  9|2.27780|1.65770|1.40703|1.32721|1.34892|1.44631|1.61138|1.84491|2.15259
  18 10|1.74106|1.18133|0.94309|0.84362|0.81937|0.84555|0.91270|1.01859|1.16495
  19 11|1.36005|0.86373|0.65018|0.55222|0.51259|0.50864|0.53098|0.57616|0.64387
  20 12|1.08231|0.64568|0.45945|0.37108|0.32939|0.31424|0.31695|0.33387|0.36380
  21 13|0.87517|0.49210|0.33183|0.25527|0.21689|0.19897|0.19384|0.19804|0.21013
  22 14|0.71759|0.38147|0.24433|0.17934|0.14601|0.12887|0.12127|0.12012|0.12399
  23 15|0.59562|0.30019|0.18303|0.12840|0.10028|0.08523|0.07749|0.07440|0.07468
  24 16|0.49977|0.23941|0.13925|0.09351|0.07015|0.05745|0.05049|0.04700|0.04587
  25 17|0.42340|0.19323|0.10742|0.06916|0.04990|0.03941|0.03350|0.03024|0.02870
  26 18|0.36181|0.15765|0.08392|0.05188|0.03604|0.02748|0.02260|0.01980|0.01827
  27 19|0.31160|0.12989|0.06632|0.03942|0.02640|0.01945|0.01549|0.01317|0.01182
  28 20|0.27026|0.10797|0.05296|0.03031|0.01959|0.01396|0.01077|0.00889|0.00777
  29 21|0.23591|0.09048|0.04269|0.02356|0.01471|0.01014|0.00759|0.00609|0.00518
  30 22|0.20714|0.07639|0.03473|0.01850|0.01117|0.00746|0.00542|0.00423|0.00350
  31 23|0.18287|0.06493|0.02847|0.01466|0.00856|0.00555|0.00392|0.00297|0.00240
  32 24|0.16224|0.05554|0.02352|0.01171|0.00663|0.00417|0.00286|0.00211|0.00166
  33 25|0.14459|0.04779|0.01957|0.00944|0.00518|0.00316|0.00211|0.00152|0.00116
  34 26|0.12942|0.04135|0.01639|0.00766|0.00408|0.00242|0.00157|0.00110|0.00082
  35 27|0.11629|0.03595|0.01381|0.00626|0.00324|0.00187|0.00118|0.00081|0.00059
  36 28|0.10489|0.03141|0.01170|0.00515|0.00259|0.00146|0.00090|0.00060|0.00043
  37 29|0.09492|0.02756|0.00996|0.00426|0.00209|0.00114|0.00069|0.00045|0.00031
  38 30|0.08618|0.02428|0.00853|0.00355|0.00169|0.00090|0.00053|0.00034|0.00023
  39 31|0.07848|0.02147|0.00733|0.00297|0.00138|0.00072|0.00041|0.00025|0.00017
  40 32|0.07167|0.01906|0.00633|0.00250|0.00113|0.00057|0.00032|0.00019|0.00013
  41
  42 Here's a table showing available repository size for a given pfalse_positive
  43 and three values of k (assuming we only use the 160 bit SHA1 for addressing the
  44 filter and 8192bytes per object):
  45
  46 pfalse|obj k=4     |cap k=4    |obj k=5  |cap k=5    |obj k=6 |cap k=6
  47 2.500%|139333497228|1038.11 TiB|558711157|4262.63 GiB|13815755|105.41 GiB
  48 1.000%|104489450934| 778.50 TiB|436090254|3327.10 GiB|11077519| 84.51 GiB
  49 0.125%| 57254889824| 426.58 TiB|261732190|1996.86 GiB| 7063017| 55.89 GiB
  50
  51 This eliminates pretty neatly any k>6 as long as we use the raw SHA for
  52 addressing.
  53
  54 filter size scales linearly with repository size for a given k and pfalse.
  55
  56 Here's a table of filter sizes for a 1 TiB repository:
  57
  58 pfalse| k=3        | k=4        | k=5        | k=6
  59 2.500%| 138.78 MiB | 126.26 MiB | 123.00 MiB | 123.37 MiB
  60 1.000%| 197.83 MiB | 168.36 MiB | 157.58 MiB | 153.87 MiB
  61 0.125%| 421.14 MiB | 307.26 MiB | 262.56 MiB | 241.32 MiB
  62
  63 For bup:
  64 * We want the bloom filter to fit in memory; if it doesn't, the k pagefaults
  65 per lookup will be worse than the two required for midx.
  66 * We want the pfalse_positive to be low enough that the cost of sometimes
  67 faulting on the midx doesn't overcome the benefit of the bloom filter.
  68 * We have readily available 160 bits for addressing the filter.
  69 * We want to be able to have a single bloom address entire repositories of
  70 reasonable size.
  71
  72 Based on these parameters, a combination of k=4 and k=5 provides the behavior
  73 that bup needs.  As such, I've implemented bloom addressing, adding and
  74 checking functions in C for these two values.  Because k=5 requires less space
  75 and gives better overall pfalse_positive perofrmance, it is preferred if a
  76 table with k=5 can represent the repository.
  77
  78 None of this tells us what max_pfalse_positive to choose.
  79
  80 Brandon Low <lostlogic@lostlogicx.com> 2011-02-04
  81 """
  82 import sys, os, math, mmap
  83 from bup import _helpers
  84 from bup.helpers import *
  85
  86 BLOOM_VERSION = 2
  87 MAX_BITS_EACH = 32 # Kinda arbitrary, but 4 bytes per entry is pretty big
  88 MAX_BLOOM_BITS = {4: 37, 5: 29} # 160/k-log2(8)
  89 MAX_PFALSE_POSITIVE = 1. # Totally arbitrary, needs benchmarking
  90
  91 _total_searches = 0
  92 _total_steps = 0
  93
  94 bloom_contains = _helpers.bloom_contains
  95 bloom_add = _helpers.bloom_add
  96
  97
  98 class ShaBloom:
  99     """Wrapper which contains data from multiple index files. """
 100     def __init__(self, filename, f=None, readwrite=False, expected=-1):
 101         self.name = filename
 102         self.rwfile = None
 103         self.map = None
 104         assert(filename.endswith('.bloom'))
 105         if readwrite:
 106             assert(expected > 0)
 107             self.rwfile = f = f or open(filename, 'r+b')
 108             f.seek(0)
 109
 110             # Decide if we want to mmap() the pages as writable ('immediate'
 111             # write) or else map them privately for later writing back to
 112             # the file ('delayed' write).  A bloom table's write access
 113             # pattern is such that we dirty almost all the pages after adding
 114             # very few entries.  But the table is so big that dirtying
 115             # *all* the pages often exceeds Linux's default
 116             # /proc/sys/vm/dirty_ratio or /proc/sys/vm/dirty_background_ratio,
 117             # thus causing it to start flushing the table before we're
 118             # finished... even though there's more than enough space to
 119             # store the bloom table in RAM.
 120             #
 121             # To work around that behaviour, if we calculate that we'll
 122             # probably end up touching the whole table anyway (at least
 123             # one bit flipped per memory page), let's use a "private" mmap,
 124             # which defeats Linux's ability to flush it to disk.  Then we'll
 125             # flush it as one big lump during close().
 126             pages = os.fstat(f.fileno()).st_size / 4096 * 5 # assume k=5
 127             self.delaywrite = expected > pages
 128             debug1('bloom: delaywrite=%r\n' % self.delaywrite)
 129             if self.delaywrite:
 130                 self.map = mmap_readwrite_private(self.rwfile, close=False)
 131             else:
 132                 self.map = mmap_readwrite(self.rwfile, close=False)
 133         else:
 134             self.rwfile = None
 135             f = f or open(filename, 'rb')
 136             self.map = mmap_read(f)
 137         got = str(self.map[0:4])
 138         if got != 'BLOM':
 139             log('Warning: invalid BLOM header (%r) in %r\n' % (got, filename))
 140             return self._init_failed()
 141         ver = struct.unpack('!I', self.map[4:8])[0]
 142         if ver < BLOOM_VERSION:
 143             log('Warning: ignoring old-style (v%d) bloom %r\n'
 144                 % (ver, filename))
 145             return self._init_failed()
 146         if ver > BLOOM_VERSION:
 147             log('Warning: ignoring too-new (v%d) bloom %r\n'
 148                 % (ver, filename))
 149             return self._init_failed()
 150
 151         self.bits, self.k, self.entries = struct.unpack('!HHI', self.map[8:16])
 152         idxnamestr = str(self.map[16 + 2**self.bits:])
 153         if idxnamestr:
 154             self.idxnames = idxnamestr.split('\0')
 155         else:
 156             self.idxnames = []
 157
 158     def _init_failed(self):
 159         if self.map:
 160             self.map = None
 161         if self.rwfile:
 162             self.rwfile.close()
 163             self.rwfile = None
 164         self.idxnames = []
 165         self.bits = self.entries = 0
 166
 167     def valid(self):
 168         return self.map and self.bits
 169
 170     def __del__(self):
 171         self.close()
 172
 173     def close(self):
 174         if self.map and self.rwfile:
 175             debug2("bloom: closing with %d entries\n" % self.entries)
 176             self.map[12:16] = struct.pack('!I', self.entries)
 177             if self.delaywrite:
 178                 self.rwfile.seek(0)
 179                 self.rwfile.write(self.map)
 180             else:
 181                 self.map.flush()
 182             self.rwfile.seek(16 + 2**self.bits)
 183             if self.idxnames:
 184                 self.rwfile.write('\0'.join(self.idxnames))
 185         self._init_failed()
 186
 187     def pfalse_positive(self, additional=0):
 188         n = self.entries + additional
 189         m = 8*2**self.bits
 190         k = self.k
 191         return 100*(1-math.exp(-k*float(n)/m))**k
 192
 193     def add_idx(self, ix):
 194         """Add the object to the filter, return current pfalse_positive."""
 195         if not self.map:
 196             raise Exception("Cannot add to closed bloom")
 197         self.entries += bloom_add(self.map, ix.shatable, self.bits, self.k)
 198         self.idxnames.append(os.path.basename(ix.name))
 199
 200     def exists(self, sha):
 201         """Return nonempty if the object probably exists in the bloom filter.
 202
 203         If this function returns false, the object definitely does not exist.
 204         If it returns true, there is a small probability that it exists
 205         anyway, so you'll have to check it some other way.
 206         """
 207         global _total_searches, _total_steps
 208         _total_searches += 1
 209         if not self.map:
 210             return None
 211         found, steps = bloom_contains(self.map, str(sha), self.bits, self.k)
 212         _total_steps += steps
 213         return found
 214
 215     def __len__(self):
 216         return int(self.entries)
 217
 218
 219 def create(name, expected, delaywrite=None, f=None, k=None):
 220     """Create and return a bloom filter for `expected` entries."""
 221     bits = int(math.floor(math.log(expected*MAX_BITS_EACH/8,2)))
 222     k = k or ((bits <= MAX_BLOOM_BITS[5]) and 5 or 4)
 223     if bits > MAX_BLOOM_BITS[k]:
 224         log('bloom: warning, max bits exceeded, non-optimal\n')
 225         bits = MAX_BLOOM_BITS[k]
 226     debug1('bloom: using 2^%d bytes and %d hash functions\n' % (bits, k))
 227     f = f or open(name, 'w+b')
 228     f.write('BLOM')
 229     f.write(struct.pack('!IHHI', BLOOM_VERSION, bits, k, 0))
 230     assert(f.tell() == 16)
 231     # NOTE: On some systems this will not extend+zerofill, but it does on
 232     # darwin, linux, bsd and solaris.
 233     f.truncate(16+2**bits)
 234     f.seek(0)
 235     if delaywrite != None and not delaywrite:
 236         # tell it to expect very few objects, forcing a direct mmap
 237         expected = 1
 238     return ShaBloom(name, f=f, readwrite=True, expected=expected)
 239