Beaver2.5.0 syalia-srl/beaver

The same email twice

The desk reads the support mailbox every minute, and a mail server sometimes delivers the same message twice. Each email has a Message-ID header, so the reader remembers the ids it has turned into tickets and skips the ones it has seen. A dictionary of ids does that exactly:

import os

from beaver import BeaverDB

db = BeaverDB("helpdesk.db")
seen = db.dict("seen-ids")

with seen.batched() as batch:
    for n in range(50_000):
        batch[f"<{n}.support@mail.example>"] = True

print("<17.support@mail.example>" in seen, "<new@mail.example>" in seen)
db.close()
print(f"{os.path.getsize('helpdesk.db') / 1e6:.1f} MB for {50_000:,} ids")
True False
5.2 MB for 50,000 ids

It grows with every email, forever. A busy shop's mailbox runs to millions of messages, and the table that only answers "seen it?" becomes the largest one in the file. The other question the desk asks, how many distinct customers wrote this month, needs a set of addresses that grows the same way.

Sketches#

db.sketch(name) is an approximate set with a fixed size. It answers two questions: whether an item was added (a Bloom filter), and about how many distinct items were added (a HyperLogLog). Its size is set by the capacity and the error_rate you ask for, not by what you add. Both structures live in one ApproximateSet, stored as a single blob in the file.

os.remove("helpdesk.db")
db = BeaverDB("helpdesk.db")
ids = db.sketch("seen-ids", capacity=1_000_000, error_rate=0.01)

with ids.batched() as batch:
    for n in range(50_000):
        batch.add(f"<{n}.support@mail.example>")

print("<17.support@mail.example>" in ids, "<new@mail.example>" in ids)
print(len(ids), "distinct, approximately")
db.close()
print(f"{os.path.getsize('helpdesk.db') / 1e6:.1f} MB, for up to 1,000,000 ids")
True False
50431 distinct, approximately
1.4 MB, for up to 1,000,000 ids

The file is the same size at fifty thousand ids and at a million. The price is the error rate. "Not seen" is always right, and "seen" is wrong for about 1 in 100 items never added, when the sketch is full. The count is off by a fraction of a percent. For the mailbox that means about one new email in a hundred mistaken for a duplicate, at a million ids. A desk that cannot afford that checks the sketch first and the exact record only when the sketch says "seen", which is rare.

with BeaverDB("helpdesk.db") as db:
    ids = db.sketch("seen-ids", capacity=1_000_000, error_rate=0.01)
    wrong = sum(f"<other-{n}@mail.example>" in ids for n in range(5_000))
    print(wrong, "false positives in 5,000 ids never added")
0 false positives in 5,000 ids never added

At fifty thousand ids the sketch is far from full, so the rate measured here is well under the 1% it guarantees at capacity.

What a sketch remembers#

The capacity and error rate are fixed when the sketch is created. Opening it again with other values is an error, since the bits would mean something else:

with BeaverDB("helpdesk.db") as db:
    try:
        db.sketch("seen-ids", capacity=10_000).add("<x@mail.example>")
    except ValueError as e:
        print("ValueError:", e)
ValueError: Sketch 'seen-ids' exists with capacity=1000000, error=0.01. Cannot load with requested capacity=10000, error=0.01.

add and batched() write to the file, and the next BeaverDB that opens the sketch sees those items. contains (and in) reads the copy this BeaverDB loaded, which is refreshed by its own next add. So in a program that only checks, items another process added since appear after its next add, or after reopening. The mailbox reader is the only writer of its sketch, which keeps it simple. A sketch keeps no items, so it cannot list what it holds, and nothing can be removed from it except everything, with clear().

The program#

The mailbox reader: skip what was seen, count the distinct senders.

examples/mailbox.py · L1–43
from beaver import BeaverDB

def read_mailbox(db: BeaverDB, emails: list[dict]) -> list[str]:
    seen = db.sketch("seen-ids", capacity=1_000_000, error_rate=0.01)
    senders = db.sketch("senders", capacity=100_000, error_rate=0.01)
    new_tickets = []
    for email in emails:
        if email["message_id"] in seen:
            continue
        seen.add(email["message_id"])
        senders.add(email["from"])
        new_tickets.append(email["subject"])
    return new_tickets

def main():
    with BeaverDB("helpdesk.db") as db:
        db.sketch("seen-ids", capacity=1_000_000, error_rate=0.01).clear()
        db.sketch("senders", capacity=100_000, error_rate=0.01).clear()
        inbox = [
            {
                "message_id": "<1@mail.example>",
                "from": "maria@example.com",
                "subject": "Brakes",
            },
            {
                "message_id": "<2@mail.example>",
                "from": "omar@example.com",
                "subject": "Chain",
            },
            {
                "message_id": "<1@mail.example>",
                "from": "maria@example.com",
                "subject": "Brakes",
            },
        ]
        print("new tickets:", read_mailbox(db, inbox))
        print(
            "distinct senders:",
            len(db.sketch("senders", capacity=100_000, error_rate=0.01)),
        )

if __name__ == "__main__":
    main()
new tickets: ['Brakes', 'Chain']
distinct senders: 2
Last updated 2026-11-10 · Edit this pageBeaver is MIT-licensed. Made by Syalia.