ribbonGo

package module

v1.0.10 Latest Latest Go to latest Published: Jul 17, 2026 License: MIT Imports: 5 Imported by: 0

Details

Valid go.mod file
Redistributable license
Tagged version
Stable version
Learn more about best practices

Repository

github.com/RibbonFilter/ribbonGo

Links

Open Source Insights

README ¶

ribbonGo

A high-performance Ribbon filter in Go — a static, space-efficient probabilistic data structure for approximate set membership that is practically smaller than Bloom and Xor filters.

Based on:

"Ribbon filter: practically smaller than Bloom and Xor" Peter C. Dillinger & Stefan Walzer, 2021 — arXiv:2103.02515

What is a Ribbon Filter?

A Ribbon filter answers "is this key in the set?" — the same problem Bloom filters solve — while using significantly less space. Given a fixed set of keys, it provides:

No false negatives — a member key always returns true.
Configurable false-positive rate — a non-member returns true with probability ≈ 2^−r for r result bits.
Near-optimal space — within ~1–5% of the information-theoretic minimum.

Ribbon vs Bloom vs Xor

Property	Bloom	Xor	Ribbon
Space overhead	~44% over optimal	~23% over optimal	~1–5% over optimal
Construction	Fast, incremental	Fast, static	Moderate, static
Supports deletion	No (without counting)	No	No
Bits/key at 1% FPR	9.6	9.8	≈ 8.0

Ribbon filters suit read-heavy, write-once workloads: LSM-tree engines (RocksDB, LevelDB), static lookup tables, networking data planes — any case where a set is built once and queried many times.

Installation

go get github.com/RibbonFilter/ribbonGo

Requires Go 1.24+.

Quick Start

The package name is ribbonGo, so the qualifier for all exported symbols is ribbonGo..

package main

import (
	"fmt"
	"log"

	"github.com/RibbonFilter/ribbonGo"
)

func main() {
	// Build a filter from a set of unique keys with default settings
	// (w=128, r=7, FPR ≈ 0.78%).
	keys := []string{"apple", "banana", "cherry", "date", "elderberry"}

	f, err := ribbonGo.NewFromKeys(keys)
	if err != nil {
		log.Fatal(err)
	}

	// Query membership.
	fmt.Println(f.Contains("banana")) // true  (always correct for members)
	fmt.Println(f.Contains("fig"))    // false (probably — FPR ≈ 0.78%)
}

Building Explicitly

New + Build separates construction from key insertion, and Build may be called again to rebuild against a different key set.

f := ribbonGo.New()
if err := f.Build(keys); err != nil {
	log.Fatal(err)
}

Custom Configuration

f, err := ribbonGo.NewFromKeysWithConfig(ribbonGo.Config{
	CoeffBits:           64,   // w=64: balanced speed/space
	ResultBits:          8,    // r=8: FPR ≈ 0.39%
	FirstCoeffAlwaysOne: true, // deterministic pivot (faster)
	MaxSeeds:            256,  // hash-seed retries before failure
}, keys)
if err != nil {
	// err is ribbonGo.ErrConstructionFailed if banding never succeeds.
	log.Fatal(err)
}

Note: keys must be unique. Duplicate keys produce identical equations regardless of the hash seed and cause guaranteed construction failure. De-duplicate the input first if duplicates may be present.

API Reference

The public surface is intentionally small: one type, its config, and a sentinel error.

Types

Type	Description
`Ribbon`	The main filter type. Create → Build → Contains.
`Config`	Construction parameters (ribbon width, result bits, etc.).
`ErrConstructionFailed`	Sentinel error returned when banding fails after all seed retries.

Functions

Function	Signature	Description
`New`	`func New() *Ribbon`	Create a filter with defaults: w=128, r=7, fcao=true, maxSeeds=256.
`NewWithConfig`	`func NewWithConfig(cfg Config) *Ribbon`	Create a filter with custom parameters. Panics on invalid config.
`NewFromKeys`	`func NewFromKeys(keys []string) (*Ribbon, error)`	Create with defaults and build in one step.
`NewFromKeysWithConfig`	`func NewFromKeysWithConfig(cfg Config, keys []string) (*Ribbon, error)`	Create with custom config and build in one step.
`Build`	`func (r *Ribbon) Build(keys []string) error`	Construct the filter from a set of unique keys. May be called repeatedly.
`Contains`	`func (r *Ribbon) Contains(key string) bool`	Test membership. Zero allocations; safe for concurrent use after Build.

Config Fields

Field	Type	Default	Description
`CoeffBits`	`uint32`	128	Ribbon width w ∈ {32, 64, 128}. Larger → more compact, slower to build.
`ResultBits`	`uint`	7	Fingerprint bits r ∈ [1, 8]. FPR ≈ 2^−r.
`FirstCoeffAlwaysOne`	`bool`	true	Force bit 0 of each coefficient row to 1 for deterministic pivoting.
`MaxSeeds`	`uint32`	256	Maximum hash-seed retries before returning `ErrConstructionFailed`. `0` uses the default.

Full documentation: pkg.go.dev/github.com/RibbonFilter/ribbonGo.

How It Works

A Ribbon filter encodes set membership as a system of linear equations over GF(2):

Hash each key to a triple: a starting position s, a w-bit coefficient row c, and an r-bit result r.
Band the equations into an upper-triangular matrix via Gaussian elimination — the "banding" step.
Solve the triangular system by back-substitution, producing a compact solution vector Z.
Query a candidate key by recomputing its triple and checking whether c · Z[s..s+w] == r.

The name refers to the banded structure of the coefficient matrix: each equation touches only w consecutive columns starting at position s, forming a ribbon-like diagonal band.

Why is it smaller than Bloom?

A Bloom filter sets independent bit positions, so it cannot pack information tightly. A Ribbon filter encodes membership as equations, letting the solver store nearly r bits of information per key in the solution vector. The information-theoretic minimum is r bits/key, and Ribbon comes within 1–5% of it.

Architecture

The implementation follows the paper's full algorithmic pipeline:

Key → [Hash] → [Bander] → [Solver] → [Filter/Query]
       §2         §2,§4       §2           §2

Pipeline Layers

Layer	File	Description
uint128	`uint128.go`	128-bit integer type for coefficient rows when w=128.
Hash	`hash.go`	Two-phase pipeline: hash each key once with XXH3, then cheaply remix per seed to derive `(start, coeffRow, result)` triples.
Bander	`bander.go`	On-the-fly Gaussian elimination over GF(2). Converts hashed equations into an upper-triangular banded matrix. Hottest construction path.
Solver	`solver.go`	Back-substitution writing the solution directly into the Interleaved Column-Major Layout (paper §5.2).
Filter	`filter.go`	Query evaluation: one hash, then a per-result-column GF(2) dot product over the ICML words, short-circuiting on the first mismatch.
Builder	`builder.go`	Orchestrates hashing → banding → solving → filter construction, including RocksDB-style dynamic slot computation.
Public API	`ribbon.go`	Sole public surface: `Ribbon`, `Config`, constructors, `Build`, `Contains`.

Key Optimisations

Interleaved Column-Major Layout (ICML) — the solution is stored as w-bit words grouped into blocks of r words (RocksDB's InterleavedSolutionStorage, paper §5.2), not one byte per slot. Queries decode r result columns via XOR-fold + POPCNT parity and short-circuit on the first mismatch. Storage is width-specialised: []uint64 for w ∈ {64, 128}, []uint32 for w=32.
SoA construction layout — coefficient data lives in parallel arrays (coeffLo, coeffHi, result). For w≤64, coeffHi is nil, doubling coefficients per cache line versus an array-of-structs.
Width specialisation — add() dispatches to addW64() (pure uint64) or addW128() (separate lo/hi ops), avoiding generic branch dispatch.
Software-pipelined prefetching — addRange() prefetches the next key's cache line while processing the current one (20–36% throughput at scale).
Dynamic overhead ratio — slot count m uses RocksDB-style empirical tables where overhead grows logarithmically with n, keeping banding reliable at all scales.
Two-phase hashing — keys are hashed once with XXH3; seed retries apply only a cheap remix, never re-hashing key data.

Benchmarks

All benchmarks follow the methodology of Dillinger & Walzer (2021), at both n = 10⁶ and n = 10⁸ keys, with r = 7 result bits and firstCoeffAlwaysOne = true.

The Build and Space tables were measured on an Apple M3 Pro (ARM64); the Query table was re-measured on an x86 Xeon Platinum host after the ICML migration. Space/correctness figures (bits/key, FPR) are CPU-independent; absolute ns/op are not comparable across the two hosts.

Build Performance

n	Width	ns/key	bits/key	Overhead
10⁶	w=32	56.89	9.227	31.81%
10⁶	w=64	64.56	7.840	11.99%
10⁶	w=128	106.3	7.334	4.749%
10⁸	w=32	355.3	10.17	45.30%
10⁸	w=64	266.2	8.231	17.58%
10⁸	w=128	384.7	7.512	7.314%

bits/key is the actual ICML physical storage (paper §5.2): the r result columns packed at r bits per slot (r × numSlots / n). At n = 10⁶, w=128 achieves 7.33 bits/key — only 4.7% above the 7-bit minimum for r=7.

Query Performance

Lookup latency per key at n = 10⁶, on an x86 Xeon Platinum host.

Width	Positive (ns/op)	Negative (ns/op)
w=32	32.3	26.9
w=64	31.5	26.3
w=128	43.2	31.7

With ICML each query decodes the r result columns one at a time (XOR-fold + POPCNT parity), so cost is roughly flat in w for w ≤ 64 and only rises at w=128 (two 64-bit halves per column). Negative queries short-circuit on the first mismatched column, so they are consistently faster than positive queries.

Space Efficiency

n	Width	bits/key	Overhead
10⁶	w=32	9.227	31.81%
10⁶	w=64	7.840	11.99%
10⁶	w=128	7.334	4.749%
10⁸	w=32	10.17	45.30%
10⁸	w=64	8.231	17.58%
10⁸	w=128	7.512	7.314%

w=128 at n = 10⁶ uses only 7.33 bits/key vs Bloom's 9.6 bits/key at the same FPR — a 23.6% space saving.

Running the Benchmarks

# Full benchmark suite
go test -bench=. -benchmem -count=3 ./...

# Paper-aligned benchmarks at n=10⁶ and n=10⁸
go test -run=^$ -bench='BenchmarkRibbon' -benchtime=3s -count=1

# A specific benchmark
go test -run=^$ -bench='BenchmarkRibbonBuild/w=128/n=1000000' -benchtime=3s

Testing

The suite covers correctness, every configuration, scale, and cross-validation of the optimised code against reference implementations.

Correctness — single insertion, no false negatives, FPR validation, collision chains, 128-bit boundary crossing, redundant/contradictory equations.
All configurations — w ∈ {32, 64, 128} × firstCoeffAlwaysOne ∈ {true, false} × r ∈ {1, 4, 7, 8}.
Scale — builds at n = 100,000 verified against expected FPR.
Edge cases — empty input, single key, nil/empty filter, rebuild semantics, invalid-config panics.
Cross-validation — optimised add() vs reference slowadd(), and addRange() vs an add()-loop, verified slot-by-slot.

go test -v -count=1 ./...

Contributing

Contributions are welcome. This project tracks the paper's design closely — please read the relevant paper section before modifying any algorithm.

Getting Started

git clone https://github.com/RibbonFilter/ribbonGo.git
cd ribbonGo
go test ./...

Guidelines

Paper-first — every design decision should cite a specific section (§N) of Dillinger & Walzer (2021).
RocksDB cross-references — use the [RocksDB: FunctionName in file.h] format for implementation parallels.
All configs — tests must cover w ∈ {32, 64, 128} × firstCoeffAlwaysOne ∈ {true, false}.
Reference implementations — include slow* variants for cross-validation of optimised code.
Zero allocations — hot paths must not escape to the heap; verify with go test -bench=X -benchmem.
Naming — unexported everything internal (standardBander, not StandardBander); constants use kCamelCase.

References

Dillinger, P. C. & Walzer, S. (2021). Ribbon filter: practically smaller than Bloom and Xor. arXiv:2103.02515
RocksDB Ribbon filter: ribbon_impl.h, ribbon_alg.h, ribbon_config.cc
XXH3 hash function (Go): github.com/zeebo/xxh3

License

Documentation ¶

Index ¶

Variables
type Config
type Ribbon
- func (r *Ribbon) Build(keys []string) error
- func (r *Ribbon) Contains(key string) bool

Constants ¶

This section is empty.

Variables ¶

View Source

var ErrConstructionFailed = errors.New("ribbon: construction failed after exhausting all seed retries")

ErrConstructionFailed is returned by Build when the banding algorithm could not solve the linear system within the configured number of seed retries.

This typically means the input contains duplicate keys (which always produce linearly dependent equations regardless of seed).

Callers should either:

Remove duplicate keys from the input.
Increase Config.MaxSeeds.

Functions ¶

This section is empty.

Types ¶

type Config ¶

type Config struct {
	// CoeffBits is the ribbon width w: must be 32, 64, or 128.
	//
	// Paper §4: "w ∈ {32, 64, 128}. Overhead ratio m/n ≈ 1 + 2.3/w."
	// Larger w → less space overhead per key, slower construction per key.
	//   w=32:  ~7.2% overhead, fastest construction per key
	//   w=64:  ~3.6% overhead, balanced
	//   w=128: ~1.8% overhead, most compact, slowest construction per key
	CoeffBits uint32

	// ResultBits is the number of fingerprint bits r stored per key.
	// The false-positive rate (FPR) is approximately 2^(-r).
	//
	// Paper §3: "each query computes an r-bit fingerprint and compares
	// it against the stored solution row."
	//   r=7:  FPR ≈ 0.78%
	//   r=8:  FPR ≈ 0.39%
	//   r=10: FPR ≈ 0.098%
	//
	// Must be in [1, 8]. Limited to 8 because each key's fingerprint is a
	// uint8 (the paper calls these "result rows"). The solution itself is
	// NOT stored one uint8 per slot: it uses the Interleaved Column-Major
	// Layout (paper §5.2), which packs the r result-bit columns of each
	// w-row block into r w-bit words (see filter and icmlSolution).
	ResultBits uint

	// FirstCoeffAlwaysOne controls whether bit 0 of every coefficient row
	// is forced to 1. When true, the Gaussian elimination pivot is
	// deterministic at column s(x), removing the need for a leading-zero
	// scan during banding (faster construction).
	//
	// Paper §4: "setting the first coefficient bit to 1."
	// Set to false for research/experimentation with natural coefficient
	// distributions.
	FirstCoeffAlwaysOne bool

	// MaxSeeds is the maximum number of hash seed retries before
	// construction returns ErrConstructionFailed.
	// A value of 0 uses the default (256).
	//
	// Paper §2: "if banding fails, retry with a new seed."
	// With typical overhead ratios (≥ 1.05), fewer than 10 seeds are
	// usually needed.
	MaxSeeds uint32
}

Config holds the parameters for constructing a Ribbon filter.

Every configurable knob described in Dillinger & Walzer (2021) is exposed so that users can reproduce and experiment with every trade-off:

CoeffBits (w): ribbon width, controlling the space–construction trade-off.
ResultBits (r): fingerprint bits, controlling the FPR.
FirstCoeffAlwaysOne: whether to force the first coefficient bit to 1.
MaxSeeds: the maximum number of hash seed retries before giving up.

type Ribbon ¶

type Ribbon struct {
	// contains filtered or unexported fields
}

Ribbon is a space-efficient probabilistic filter for approximate set membership queries.

Create one with New (default settings) or NewWithConfig (custom parameters), then call Build to construct the filter from a set of keys. After building, call Contains to test membership.

A Ribbon filter guarantees:

No false negatives: if a key was in the build set, Contains always returns true.
Configurable false positives: non-member keys return true with probability ≈ 2^(-r), where r is Config.ResultBits.

Thread safety: after Build completes, Contains may be called concurrently from multiple goroutines without synchronisation.

Based on: Dillinger & Walzer, "Ribbon filter: practically smaller than Bloom and Xor" (2021), arXiv:2103.02515.

func New ¶

func New() *Ribbon

New creates a Ribbon filter with default settings.

Defaults: w=128 (most compact), r=7 (FPR ≈ 0.78%), firstCoeffAlwaysOne=true (fastest construction), maxSeeds=256.

Paper §4: "w=128 seems to be closest to a generally good choice."

func NewFromKeys ¶ added in v1.0.7

func NewFromKeys(keys []string) (*Ribbon, error)

NewFromKeys creates a Ribbon filter with default settings and builds it from the given keys in a single step.

This is a convenience function equivalent to:

r := New()
err := r.Build(keys)

Keys must be unique: duplicate keys produce identical equations regardless of the hash seed, causing guaranteed construction failure. If duplicates may be present, the caller should de-duplicate first.

Returns ErrConstructionFailed if banding fails for all seed retries.

func NewFromKeysWithConfig ¶ added in v1.0.7

func NewFromKeysWithConfig(cfg Config, keys []string) (*Ribbon, error)

NewFromKeysWithConfig creates a Ribbon filter with custom parameters and builds it from the given keys in a single step.

This is a convenience function equivalent to:

r := NewWithConfig(cfg)
err := r.Build(keys)

Panics if Config.CoeffBits is not 32, 64, or 128, or if Config.ResultBits is not in [1, 8].

Keys must be unique: duplicate keys produce identical equations regardless of the hash seed, causing guaranteed construction failure. If duplicates may be present, the caller should de-duplicate first.

Returns ErrConstructionFailed if banding fails for all seed retries.

func NewWithConfig ¶

func NewWithConfig(cfg Config) *Ribbon

NewWithConfig creates a Ribbon filter with custom parameters.

Panics if Config.CoeffBits is not 32, 64, or 128, or if Config.ResultBits is not in [1, 8].

func (*Ribbon) Build ¶

func (r *Ribbon) Build(keys []string) error

Build constructs the filter from the given keys.

Keys must be unique: duplicate keys produce identical equations regardless of the hash seed, causing guaranteed construction failure. If duplicates may be present, the caller should de-duplicate first.

Build may be called multiple times to rebuild the filter with different key sets. Each call replaces the previous filter.

Returns ErrConstructionFailed if banding fails for all seed retries.

func (*Ribbon) Contains ¶

func (r *Ribbon) Contains(key string) bool

Contains tests whether key is probably a member of the set used to build this filter.

Returns true if the key is probably in the set (with false-positive probability ≈ 2^(-r)), or false if the key is definitely not in the set.

Returns false if Build has not been called yet.

This is the hot path of the library — zero allocations, branchless coefficient derivation, and a short-circuiting per-column ICML query.

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL

README ¶

ribbonGo

Table of Contents

What is a Ribbon Filter?

Ribbon vs Bloom vs Xor

Installation

Quick Start

Building Explicitly

Custom Configuration

API Reference

Types

Functions

Config Fields

How It Works

Why is it smaller than Bloom?

Architecture

Pipeline Layers

Key Optimisations

Benchmarks

Build Performance

Query Performance

Space Efficiency

Running the Benchmarks

Testing

Contributing

Getting Started

Guidelines

References

License

Documentation ¶

Index ¶

Constants ¶

Variables ¶

Functions ¶

Types ¶

type Config ¶

type Ribbon ¶

func New ¶

func NewFromKeys ¶ added in v1.0.7

func NewFromKeysWithConfig ¶ added in v1.0.7

func NewWithConfig ¶

func (*Ribbon) Build ¶

func (*Ribbon) Contains ¶

Source Files ¶