• Stars
    star
    270
  • Rank 152,163 (Top 3 %)
  • Language
    Rust
  • License
    MIT License
  • Created over 9 years ago
  • Updated over 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Cuckoo Filter: Practically Better Than Bloom (In Rust)

Cuckoo Filter

Crates.io

Documentation

Cuckoo filter is a Bloom filter replacement for approximated set-membership queries. While Bloom filters are well-known space-efficient data structures to serve queries like "if item x is in a set?", they do not support deletion. Their variances to enable deletion (like counting Bloom filters) usually require much more space.

Cuckoo filters provide the flexibility to add and remove items dynamically. A cuckoo filter is based on cuckoo hashing (and therefore named as cuckoo filter). It is essentially a cuckoo hash table storing each key's fingerprint. Cuckoo hash tables can be highly compact, thus a cuckoo filter could use less space than conventional Bloom filters, for applications that require low false positive rates (< 3%).

For details about the algorithm and citations please use this article for now

"Cuckoo Filter: Better Than Bloom" by Bin Fan, Dave Andersen and Michael Kaminsky

Example usage

extern crate cuckoofilter;

...

let value: &str = "hello world";

// Create cuckoo filter with default max capacity of 1000000 items
let mut cf = cuckoofilter::new();

// Add data to the filter
let success = cf.add(value).unwrap();
// success ==> Ok(())

// Lookup if data is in the filter
let success = cf.contains(value);
// success ==> true

// Test and add to the filter (if data does not exists then add)
let success = cf.test_and_add(value).unwrap();
// success ==> Ok(false)

// Remove data from the filter.
let success = cf.delete(value);
// success ==> true

C Interface

This crate has a C interface for embedding it into other languages than Rust. See the C Interface Documentation for more details.

Notes & TODOs

  • This implementation uses a a static bucket size of 4 fingerprints and a fingerprint size of 1 byte based on my understanding of an optimal bucket/fingerprint/size ratio from the aforementioned paper.
  • When the filter returns NotEnoughSpace, the element given is actually added to the filter, but some random other element gets removed. This could be improved by implementing a single-item eviction cache for that removed item.
  • There are no high-level bindings for other languages than C. One could add them e.g. for python using milksnake.

More Repositories

1

hyperloglog

HyperLogLog with lots of sugar (Sparse, LogLog-Beta bias correction and TailCut space reduction) brought to you by Axiom
Go
920
star
2

next-axiom

The official Next.js library for Axiom.
TypeScript
353
star
3

hyperminhash

HyperMinHash: Bringing intersections to HyperLogLog
Go
302
star
4

quantiles

Optimal Quantile Approximation in Streams
Go
162
star
5

axiom-js

Official language bindings and library extensions for Axiom
TypeScript
85
star
6

zig-hyperloglog

Zig library for HyperLogLog estimation
Zig
82
star
7

axiom-node

[DEPRECATED] Use axiomhq/axiom-js instead.
TypeScript
78
star
8

axiom-go

Official Go bindings for the Axiom API
Go
47
star
9

cli

The power of Axiom on the command line.
Go
41
star
10

flipcounter

A counter data structure that knows when to start estimating to save space
Go
36
star
11

axiom-rs

Official Rust bindings for the Axiom API
Rust
31
star
12

axiom-py

The official Python bindings for the Axiom API
Python
23
star
13

axiom-cloudflare-workers

Send logs from Cloudflare Workers to Axiom
JavaScript
22
star
14

tracing-axiom

The official Rust tracing layer for Axiom
Rust
18
star
15

puppeteer-request-intercepter

Intercept API Requests and return Mocked Data
TypeScript
16
star
16

prisma-axiom

Axiom observability for Prisma
TypeScript
16
star
17

variance

Go implementation of variance's method for one-pass variance computation with D. H. D. West improved methods which features merging of several multiple sets of statistics and adding weighted values.
Go
16
star
18

hypertwobits

HyperTwoBits implementation
Rust
12
star
19

awesome-axiom

A curated list of awesome Axiom Platform, libraries, open source repos, guides, blogs, Documentation and other resources.
12
star
20

axiom-demo

Take a look at Axiom on your local machine.
Shell
11
star
21

ngbuild

Dream builders 😴💭
Go
9
star
22

axiom-lambda-extension

Ingest logs and platform events from your lambda functions
Go
9
star
23

axiom-syslog-proxy

A syslog push interface to Axiom.
Go
8
star
24

axiom-honeycomb-proxy

A log forwarder/multiplexer for Axiom and Honeycomb.
Go
7
star
25

deno-client

Minimal deno library for sending events and logs to Axiom
TypeScript
6
star
26

axiom-ai

The official package to send events from AI libraries to Axiom
TypeScript
6
star
27

axiom-grafana

The official Axiom datasource plugin for Grafana.
TypeScript
5
star
28

splitblockbloom

Go
5
star
29

pkg

Commonly used Go packages for Axiom projects.
Go
4
star
30

axiom-loki-multiplexer

A push interface to Axiom via Loki endpoint.
Go
4
star
31

axiom-elements

TypeScript
4
star
32

topkapi

Topkapi: Parallel and Fast Sketches for Finding Top-K Frequent Elements
Go
3
star
33

axiom-cloudwatch-forwarder

Forward CloudWatch Logs to Axiom.
Python
3
star
34

randhn

Random new or top 500 HN story
TypeScript
3
star
35

setup-axiom

Set up a local Axiom stack for testing your integration.
JavaScript
2
star
36

annotation-action

This action allows you to create an annotation in Axiom.
TypeScript
2
star
37

terraform-provider-axiom

Axiom Terraform Provider
Go
2
star
38

homebrew-tap

Collection of Homebrew formulas for Axiom, Inc. open source projects.
Ruby
1
star
39

golang-sync-bench

Benchmarking Synchronization Primitives in Go
Go
1
star
40

axiom-nomad

Axiom 🤝 HashiCorp
HCL
1
star
41

axiom-helm-charts

Axiom Helm Charts
Smarty
1
star
42

logmanager

Yet another Go logging library.
Go
1
star
43

terraform-aws-axiom

Setup required infrastructure and install Axiom Enterprise on AWS using Terraform.
1
star
44

monaco-kusto

JavaScript
1
star
45

terraform-aws-axiom-cloudwatch-forwarder

Official Terraform modules for Axiom Cloudwatch Forwarder
HCL
1
star