bloombits

Package bloombits implements bloom filtering on batches of data.

Generator

// Generator takes a number of bloom filters and generates the rotated bloom bits
// to be used for batched filtering.
type Generator struct {
    blooms   [types.BloomBitLength][]byte // Rotated blooms for per-bit matching
    sections uint                         // Number of sections to batch together
    nextSec  uint                         // Next section to set when adding a bloom
}

Matcher

// Matcher is a pipelined system of schedulers and logic matchers which perform
// binary AND/OR operations on the bit-streams, creating a stream of potential
// blocks to inspect for data content.
type Matcher struct {
    sectionSize uint64 // Size of the data batches to filter on

    filters    [][]bloomIndexes    // Filter the system is matching for
    schedulers map[uint]*scheduler // Retrieval schedulers for loading bloom bits

    retrievers chan chan uint       // Retriever processes waiting for bit allocations
    counters   chan chan uint       // Retriever processes waiting for task count reports
    retrievals chan chan *Retrieval // Retriever processes waiting for task allocations
    deliveries chan *Retrieval      // Retriever processes waiting for task response deliveries

    running uint32 // Atomic flag whether a session is live or not
}

MatcherSession

// MatcherSession is returned by a started matcher to be used as a terminator
// for the actively running matching operation.
type MatcherSession struct {
    matcher *Matcher

    closer sync.Once     // Sync object to ensure we only ever close once
    quit   chan struct{} // Quit channel to request pipeline termination
    kill   chan struct{} // Term channel to signal non-graceful forced shutdown

    ctx context.Context // Context used by the light client to abort filtering
    err atomic.Value    // Global error to track retrieval failures deep in the chain

    pend sync.WaitGroup
}

scheduler

// scheduler handles the scheduling of bloom-filter retrieval operations for
// entire section-batches belonging to a single bloom bit. Beside scheduling the
// retrieval operations, this struct also deduplicates the requests and caches
// the results to minimize network/database overhead even in complex filtering
// scenarios.
type scheduler struct {
    bit       uint                 // Index of the bit in the bloom filter this scheduler is responsible for
    responses map[uint64]*response // Currently pending retrieval requests or already cached responses
    lock      sync.Mutex           // Lock protecting the responses from concurrent access
}