Cdb: Add support for cdb64

https://cdb.cr.yp.to/download.html

86•kreco•3mo ago

Comments

Bolwin•3mo ago

Interesting, never heard of this before. I'm assuming the use case is when your data is too large to conveniently fit into memory?

dsr_•3mo ago

It is a database for when you read a lot and don't write too often; when a write might be pretty big but not frequent; when you don't want to write a database engine yourself (I.e. figure out what to write and when). And, especially, when corrupting the data would be a big problem.

And it is especially good on copy-on-write filesystems, because it is CoW itself.

bloppe•3mo ago

So it's not constant?

tptacek•3mo ago

The lookups are ~O(1).

renewiltord•3mo ago

Nothing is truly constant lookup in number of elements in nature because we can’t pack it tighter than a sphere.

tptacek•3mo ago

It's a database for strictly exact-match lookups for very read-intensive workloads; think systems where the database only changes when the configuration changes, like email alias or domain lookups. It's very simple (a first-level hash table chaining to a second-level open-addressed hash table) and easy to get your head around, but also very limiting; an otherwise strict K-V system that uses b-trees instead of hash tables can do range queries, which you can build a lot of other stuff out of.

Most people would use Redis or SQLite today for what CDB was intended for; CDB will be faster, but for a lot of applications that speed improvement will be sub-threshold for users.

paws•3mo ago

For me this answer was helpful and succinct, thank you.

kimos•3mo ago

Great reply.

What comes to mind from my experience is storing full shipping rate tables for multiple shipping providers. Those change extremely rarely but are a high throughput exact lookup in a critical path (a checkout).

But we just implemented them in SQLite and deployed that file with the application. Simple clean, effective, and fast. Maybe shipping rate data is smaller than this is intended for, but I doubt using this instead would see a consequential perf increase. Seems niche, like the domain name lookup example.

tptacek•3mo ago

Haven't there been 64-bit ports of CDB for ages?

wolfgang42•3mo ago

Yes, the modifications you need to support it are trivially obvious (literally just replace “4 bytes” with “8 bytes” everywhere in the spec) and have been implemented by a number of authors, some of which this page links to. I guess it’s nice that they’ve been “officially” acknowledged, though.

eesmith•3mo ago

And update the hash algorithm, yes?

eesmith•3mo ago

In answer to my own question, no, except for the trivial expansion to 64-bits. https://cdb.cr.yp.to/cdb-20251021/cdb_hash.c.html with constants at https://cdb.cr.yp.to/cdb-20251021/cdb.h.html .

gnabgib•3mo ago

Title: cdb: Intro (please use the original title) https://news.ycombinator.com/newsguidelines.html

gchamonlive•3mo ago

It'd never have crawled out of the new page with that title.

trvz•3mo ago

No, the title is much better as it is.

gjvc•3mo ago

weak

stevefan1999•3mo ago

Can't this be implemented as a PHF: https://en.wikipedia.org/wiki/Perfect_hash_function

wolfgang42•3mo ago

CDB is an interesting format, optimized for read-heavy write-rarely[1] random lookups on slow media. This isn’t a very common requirement these days, but it’s convenient for very specific use cases.

[1] You “update” by overwriting the entire file. This is remarkably fast and means that there’s no overhead/tracking for empty space, but it does mean you probably want this to be a fairly rare operation.

I rolled my own cdb reader library for a project a few years ago, and wrote up my notes on the format and its internals here: https://search.feep.dev/blog/post/2022-12-03-cdb-file-format

a-dub•3mo ago

GALACTIC SCALE QMAIL that can run efficiently on a 486 AND survive a supernova!

tombert•3mo ago

I'm kind of surprised I hadn't heard of this, I could see this being something useful for a few projects. Historically for things in this space I've used RocksDB but RocksDB has given me headaches with unpredictable memory usage for large data sets.

tveita•3mo ago

In the low-level DB space there is also https://dbmx.net/tkrzw/, of the Tokyo Cabinet / Kyoto Cabinet lineage.

binary132•3mo ago

Now I’m curious about working around the writer limitations….

tptacek•3mo ago

It's designed to rebuild the whole database with every write, and the format reflects that.

binary132•3mo ago

yes — I have a few thoughts in mind for how to build a usable database around static chunks of that sort but I don’t suppose I’ll ever get around to it nor do I feel the need to explain myself beyond this. :)

waynesonfire•3mo ago

cdb is a fun format to implement! highly recommend it.

justin66•3mo ago

What's Bernstein working on that would have demanded this?

An AI model that can read and diagnose a brain MRI in seconds

Dev with 5 of experience switched to Rails, what should I be careful about?

AlphaFace: High Fidelity and Real-Time Face Swapper Robust to Facial Pose

Scientists discover “levitating” time crystals that you can hold in your hand

Rammstein – Deutschland (C64 Cover, Real SID, 8-bit – 2019) [video]

Tell HN: Yet Another Round of Zendesk Spam

Postgres Message Queue (PGMQ)

Show HN: Django-rclone: Database and media backups for Django, powered by rclone

NY lawmakers proposed statewide data center moratorium

OpenClaw AI chatbots are running amok – these scientists are listening in

Show HN: AI agent forgets user preferences every session. This fixes it

Introduce the Vouch/Denouncement Contribution Model

Show HN: SSHcode – Always-On Claude Code/OpenCode over Tailscale and Hetzner

Microsoft appointed a quality czar. He has no direct reports and no budget

Multi-agent coordination on Claude Code: 8 production pain points and patterns

Washington Post CEO Will Lewis Steps Down After Stormy Tenure

DevXT – Building the Future with AI That Acts

A Minimal OpenClaw Built with the OpenCode SDK

The silent death of Good Code

The Internal Negotiation You Have When Your Heart Rate Gets Uncomfortable

Show HN: Glance – Fast CSV inspection for the terminal (SIMD-accelerated)

Busy for the Next Fifty to Sixty Bud

Imperative

Show HN: I decomposed 87 tasks to find where AI agents structurally collapse

I went back to Linux and it was a mistake

Octrafic – open-source AI-assisted API testing from the CLI

US Accuses China of Secret Nuclear Testing

Peacock. A New Programming Language

A postcard arrived: 'If you're reading this I'm dead, and I really liked you'

What to know about the software selloff

An AI model that can read and diagnose a brain MRI in seconds

Dev with 5 of experience switched to Rails, what should I be careful about?

AlphaFace: High Fidelity and Real-Time Face Swapper Robust to Facial Pose

Scientists discover “levitating” time crystals that you can hold in your hand

Rammstein – Deutschland (C64 Cover, Real SID, 8-bit – 2019) [video]

Tell HN: Yet Another Round of Zendesk Spam

Postgres Message Queue (PGMQ)

Show HN: Django-rclone: Database and media backups for Django, powered by rclone

NY lawmakers proposed statewide data center moratorium

OpenClaw AI chatbots are running amok – these scientists are listening in

Show HN: AI agent forgets user preferences every session. This fixes it

Introduce the Vouch/Denouncement Contribution Model

Show HN: SSHcode – Always-On Claude Code/OpenCode over Tailscale and Hetzner

Microsoft appointed a quality czar. He has no direct reports and no budget

Multi-agent coordination on Claude Code: 8 production pain points and patterns

Washington Post CEO Will Lewis Steps Down After Stormy Tenure

DevXT – Building the Future with AI That Acts

A Minimal OpenClaw Built with the OpenCode SDK

The silent death of Good Code

The Internal Negotiation You Have When Your Heart Rate Gets Uncomfortable

Show HN: Glance – Fast CSV inspection for the terminal (SIMD-accelerated)

Busy for the Next Fifty to Sixty Bud

Imperative

Show HN: I decomposed 87 tasks to find where AI agents structurally collapse

I went back to Linux and it was a mistake

Octrafic – open-source AI-assisted API testing from the CLI

US Accuses China of Secret Nuclear Testing

Peacock. A New Programming Language

A postcard arrived: 'If you're reading this I'm dead, and I really liked you'

What to know about the software selloff

Cdb: Add support for cdb64

Comments