Line data Source code
1 : // Copyright 2013 The LevelDB-Go and Pebble Authors. All rights reserved. Use 2 : // of this source code is governed by a BSD-style license that can be found in 3 : // the LICENSE file. 4 : 5 : // Package bloom implements Bloom filters. 6 : package bloom // import "github.com/cockroachdb/pebble/bloom" 7 : 8 : import ( 9 : "encoding/binary" 10 : "fmt" 11 : "sync" 12 : 13 : "github.com/cockroachdb/pebble/internal/base" 14 : ) 15 : 16 : const ( 17 : cacheLineSize = 64 18 : cacheLineBits = cacheLineSize * 8 19 : ) 20 : 21 : type tableFilter []byte 22 : 23 1 : func (f tableFilter) MayContain(key []byte) bool { 24 1 : if len(f) <= 5 { 25 1 : return false 26 1 : } 27 1 : n := len(f) - 5 28 1 : nProbes := f[n] 29 1 : nLines := binary.LittleEndian.Uint32(f[n+1:]) 30 1 : cacheLineBits := 8 * (uint32(n) / nLines) 31 1 : 32 1 : h := hash(key) 33 1 : delta := h>>17 | h<<15 34 1 : b := (h % nLines) * cacheLineBits 35 1 : 36 1 : for j := uint8(0); j < nProbes; j++ { 37 1 : bitPos := b + (h % cacheLineBits) 38 1 : if f[bitPos/8]&(1<<(bitPos%8)) == 0 { 39 1 : return false 40 1 : } 41 1 : h += delta 42 : } 43 1 : return true 44 : } 45 : 46 1 : func calculateProbes(bitsPerKey int) uint32 { 47 1 : // We intentionally round down to reduce probing cost a little bit 48 1 : n := uint32(float64(bitsPerKey) * 0.69) // 0.69 =~ ln(2) 49 1 : if n < 1 { 50 1 : n = 1 51 1 : } 52 1 : if n > 30 { 53 1 : n = 30 54 1 : } 55 1 : return n 56 : } 57 : 58 : // extend appends n zero bytes to b. It returns the overall slice (of length 59 : // n+len(originalB)) and the slice of n trailing zeroes. 60 1 : func extend(b []byte, n int) (overall, trailer []byte) { 61 1 : want := n + len(b) 62 1 : if want <= cap(b) { 63 0 : overall = b[:want] 64 0 : trailer = overall[len(b):] 65 0 : clear(trailer) 66 1 : } else { 67 1 : // Grow the capacity exponentially, with a 1KiB minimum. 68 1 : c := 1024 69 1 : for c < want { 70 1 : c += c / 4 71 1 : } 72 1 : overall = make([]byte, want, c) 73 1 : trailer = overall[len(b):] 74 1 : copy(overall, b) 75 : } 76 1 : return overall, trailer 77 : } 78 : 79 : // hash implements a hashing algorithm similar to the Murmur hash. 80 1 : func hash(b []byte) uint32 { 81 1 : const ( 82 1 : seed = 0xbc9f1d34 83 1 : m = 0xc6a4a793 84 1 : ) 85 1 : h := uint32(seed) ^ uint32(uint64(uint32(len(b))*m)) 86 1 : for ; len(b) >= 4; b = b[4:] { 87 1 : h += uint32(b[0]) | uint32(b[1])<<8 | uint32(b[2])<<16 | uint32(b[3])<<24 88 1 : h *= m 89 1 : h ^= h >> 16 90 1 : } 91 : 92 : // The code below first casts each byte to a signed 8-bit integer. This is 93 : // necessary to match RocksDB's behavior. Note that the `byte` type in Go is 94 : // unsigned. What is the difference between casting a signed 8-bit value vs 95 : // unsigned 8-bit value into an unsigned 32-bit value? 96 : // Sign-extension. Consider the value 250 which has the bit pattern 11111010: 97 : // 98 : // uint32(250) = 00000000000000000000000011111010 99 : // uint32(int8(250)) = 11111111111111111111111111111010 100 : // 101 : // Note that the original LevelDB code did not explicitly cast to a signed 102 : // 8-bit value which left the behavior dependent on whether C characters were 103 : // signed or unsigned which is a compiler flag for gcc (-funsigned-char). 104 1 : switch len(b) { 105 1 : case 3: 106 1 : h += uint32(int8(b[2])) << 16 107 1 : fallthrough 108 1 : case 2: 109 1 : h += uint32(int8(b[1])) << 8 110 1 : fallthrough 111 1 : case 1: 112 1 : h += uint32(int8(b[0])) 113 1 : h *= m 114 1 : h ^= h >> 24 115 : } 116 1 : return h 117 : } 118 : 119 : const hashBlockLen = 16384 120 : 121 : type hashBlock [hashBlockLen]uint32 122 : 123 : var hashBlockPool = sync.Pool{ 124 1 : New: func() interface{} { 125 1 : return &hashBlock{} 126 1 : }, 127 : } 128 : 129 : type tableFilterWriter struct { 130 : bitsPerKey int 131 : 132 : numHashes int 133 : // We store the hashes in blocks. 134 : blocks []*hashBlock 135 : lastHash uint32 136 : 137 : // Initial "in-line" storage for the blocks slice (to avoid some small 138 : // allocations). 139 : blocksBuf [16]*hashBlock 140 : } 141 : 142 1 : func newTableFilterWriter(bitsPerKey int) *tableFilterWriter { 143 1 : w := &tableFilterWriter{ 144 1 : bitsPerKey: bitsPerKey, 145 1 : } 146 1 : w.blocks = w.blocksBuf[:0] 147 1 : return w 148 1 : } 149 : 150 : // AddKey implements the base.FilterWriter interface. 151 1 : func (w *tableFilterWriter) AddKey(key []byte) { 152 1 : h := hash(key) 153 1 : if w.numHashes != 0 && h == w.lastHash { 154 1 : return 155 1 : } 156 1 : ofs := w.numHashes % hashBlockLen 157 1 : if ofs == 0 { 158 1 : // Time for a new block. 159 1 : w.blocks = append(w.blocks, hashBlockPool.Get().(*hashBlock)) 160 1 : } 161 1 : w.blocks[len(w.blocks)-1][ofs] = h 162 1 : w.numHashes++ 163 1 : w.lastHash = h 164 : } 165 : 166 : // Finish implements the base.FilterWriter interface. 167 1 : func (w *tableFilterWriter) Finish(buf []byte) []byte { 168 1 : // The table filter format matches the RocksDB full-file filter format. 169 1 : var nLines int 170 1 : if w.numHashes != 0 { 171 1 : nLines = (w.numHashes*w.bitsPerKey + cacheLineBits - 1) / (cacheLineBits) 172 1 : // Make nLines an odd number to make sure more bits are involved when 173 1 : // determining which block. 174 1 : if nLines%2 == 0 { 175 1 : nLines++ 176 1 : } 177 : } 178 : 179 1 : nBytes := nLines * cacheLineSize 180 1 : // +5: 4 bytes for num-lines, 1 byte for num-probes 181 1 : buf, filter := extend(buf, nBytes+5) 182 1 : 183 1 : if nLines != 0 { 184 1 : nProbes := calculateProbes(w.bitsPerKey) 185 1 : for bIdx, b := range w.blocks { 186 1 : length := hashBlockLen 187 1 : if bIdx == len(w.blocks)-1 && w.numHashes%hashBlockLen != 0 { 188 1 : length = w.numHashes % hashBlockLen 189 1 : } 190 1 : for _, h := range b[:length] { 191 1 : delta := h>>17 | h<<15 // rotate right 17 bits 192 1 : b := (h % uint32(nLines)) * (cacheLineBits) 193 1 : for i := uint32(0); i < nProbes; i++ { 194 1 : bitPos := b + (h % cacheLineBits) 195 1 : filter[bitPos/8] |= (1 << (bitPos % 8)) 196 1 : h += delta 197 1 : } 198 : } 199 : } 200 1 : filter[nBytes] = byte(nProbes) 201 1 : binary.LittleEndian.PutUint32(filter[nBytes+1:], uint32(nLines)) 202 : } 203 : 204 : // Release the hash blocks. 205 1 : for i, b := range w.blocks { 206 1 : hashBlockPool.Put(b) 207 1 : w.blocks[i] = nil 208 1 : } 209 1 : w.blocks = w.blocks[:0] 210 1 : w.numHashes = 0 211 1 : return buf 212 : } 213 : 214 : // FilterPolicy implements the FilterPolicy interface from the pebble package. 215 : // 216 : // The integer value is the approximate number of bits used per key. A good 217 : // value is 10, which yields a filter with ~ 1% false positive rate. 218 : type FilterPolicy int 219 : 220 : var _ base.FilterPolicy = FilterPolicy(0) 221 : 222 : // Name implements the pebble.FilterPolicy interface. 223 1 : func (p FilterPolicy) Name() string { 224 1 : // This string looks arbitrary, but its value is written to LevelDB .sst 225 1 : // files, and should be this exact value to be compatible with those files 226 1 : // and with the C++ LevelDB code. 227 1 : return "rocksdb.BuiltinBloomFilter" 228 1 : } 229 : 230 : // MayContain implements the pebble.FilterPolicy interface. 231 1 : func (p FilterPolicy) MayContain(ftype base.FilterType, f, key []byte) bool { 232 1 : switch ftype { 233 1 : case base.TableFilter: 234 1 : return tableFilter(f).MayContain(key) 235 0 : default: 236 0 : panic(fmt.Sprintf("unknown filter type: %v", ftype)) 237 : } 238 : } 239 : 240 : // NewWriter implements the pebble.FilterPolicy interface. 241 1 : func (p FilterPolicy) NewWriter(ftype base.FilterType) base.FilterWriter { 242 1 : switch ftype { 243 1 : case base.TableFilter: 244 1 : return newTableFilterWriter(int(p)) 245 0 : default: 246 0 : panic(fmt.Sprintf("unknown filter type: %v", ftype)) 247 : } 248 : }