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     """
 101     def __init__(self, filename, f=None, readwrite=False, expected=-1):
 102         self.name = filename
 103         self.rwfile = None
 104         self.map = None
 105         assert(filename.endswith('.bloom'))
 106         if readwrite:
 107             assert(expected > 0)
 108             self.rwfile = f = f or open(filename, 'r+b')
 109             f.seek(0)
 110
 111             # Decide if we want to mmap() the pages as writable ('immediate'
 112             # write) or else map them privately for later writing back to
 113             # the file ('delayed' write).  A bloom table's write access
 114             # pattern is such that we dirty almost all the pages after adding
 115             # very few entries.  But the table is so big that dirtying
 116             # *all* the pages often exceeds Linux's default
 117             # /proc/sys/vm/dirty_ratio or /proc/sys/vm/dirty_background_ratio,
 118             # thus causing it to start flushing the table before we're
 119             # finished... even though there's more than enough space to
 120             # store the bloom table in RAM.
 121             #
 122             # To work around that behaviour, if we calculate that we'll
 123             # probably end up touching the whole table anyway (at least
 124             # one bit flipped per memory page), let's use a "private" mmap,
 125             # which defeats Linux's ability to flush it to disk.  Then we'll
 126             # flush it as one big lump during close().
 127             pages = os.fstat(f.fileno()).st_size / 4096 * 5 # assume k=5
 128             self.delaywrite = expected > pages
 129             debug1('bloom: delaywrite=%r\n' % self.delaywrite)
 130             if self.delaywrite:
 131                 self.map = mmap_readwrite_private(self.rwfile, close=False)
 132             else:
 133                 self.map = mmap_readwrite(self.rwfile, close=False)
 134         else:
 135             self.rwfile = None
 136             f = f or open(filename, 'rb')
 137             self.map = mmap_read(f)
 138         got = str(self.map[0:4])
 139         if got != 'BLOM':
 140             log('Warning: invalid BLOM header (%r) in %r\n' % (got, filename))
 141             return self._init_failed()
 142         ver = struct.unpack('!I', self.map[4:8])[0]
 143         if ver < BLOOM_VERSION:
 144             log('Warning: ignoring old-style (v%d) bloom %r\n'
 145                 % (ver, filename))
 146             return self._init_failed()
 147         if ver > BLOOM_VERSION:
 148             log('Warning: ignoring too-new (v%d) bloom %r\n'
 149                 % (ver, filename))
 150             return self._init_failed()
 151
 152         self.bits, self.k, self.entries = struct.unpack('!HHI', self.map[8:16])
 153         idxnamestr = str(self.map[16 + 2**self.bits:])
 154         if idxnamestr:
 155             self.idxnames = idxnamestr.split('\0')
 156         else:
 157             self.idxnames = []
 158
 159     def _init_failed(self):
 160         if self.map:
 161             self.map = None
 162         if self.rwfile:
 163             self.rwfile.close()
 164             self.rwfile = None
 165         self.idxnames = []
 166         self.bits = self.entries = 0
 167
 168     def valid(self):
 169         return self.map and self.bits
 170
 171     def __del__(self):
 172         self.close()
 173
 174     def close(self):
 175         if self.map and self.rwfile:
 176             debug2("bloom: closing with %d entries\n" % self.entries)
 177             self.map[12:16] = struct.pack('!I', self.entries)
 178             if self.delaywrite:
 179                 self.rwfile.seek(0)
 180                 self.rwfile.write(self.map)
 181             else:
 182                 self.map.flush()
 183             self.rwfile.seek(16 + 2**self.bits)
 184             if self.idxnames:
 185                 self.rwfile.write('\0'.join(self.idxnames))
 186         self._init_failed()
 187
 188     def pfalse_positive(self, additional=0):
 189         n = self.entries + additional
 190         m = 8*2**self.bits
 191         k = self.k
 192         return 100*(1-math.exp(-k*float(n)/m))**k
 193
 194     def add_idx(self, ix):
 195         """Add the object to the filter, return current pfalse_positive."""
 196         if not self.map: 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         global _total_searches, _total_steps
 203         _total_searches += 1
 204         if not self.map: return None
 205         found, steps = bloom_contains(self.map, str(sha), self.bits, self.k)
 206         _total_steps += steps
 207         return found
 208
 209     @classmethod
 210     def create(cls, name, expected, delaywrite=None, f=None, k=None):
 211         """Create and return a bloom filter for `expected` entries."""
 212         bits = int(math.floor(math.log(expected*MAX_BITS_EACH/8,2)))
 213         k = k or ((bits <= MAX_BLOOM_BITS[5]) and 5 or 4)
 214         if bits > MAX_BLOOM_BITS[k]:
 215             log('bloom: warning, max bits exceeded, non-optimal\n')
 216             bits = MAX_BLOOM_BITS[k]
 217         debug1('bloom: using 2^%d bytes and %d hash functions\n' % (bits, k))
 218         f = f or open(name, 'w+b')
 219         f.write('BLOM')
 220         f.write(struct.pack('!IHHI', BLOOM_VERSION, bits, k, 0))
 221         assert(f.tell() == 16)
 222         # NOTE: On some systems this will not extend+zerofill, but it does on
 223         # darwin, linux, bsd and solaris.
 224         f.truncate(16+2**bits)
 225         f.seek(0)
 226         if delaywrite != None and not delaywrite:
 227             # tell it to expect very few objects, forcing a direct mmap
 228             expected = 1
 229         return cls(name, f=f, readwrite=True, expected=expected)
 230
 231     def __len__(self):
 232         return int(self.entries)
 233
 234