COW and volume management? [LWN.net]

COW and volume management?

Posted Jan 27, 2026 13:45 UTC (Tue) by Wol (subscriber, #4433)
In reply to: COW and volume management? by koverstreet
Parent article: Filesystem medley: EROFS, NTFS, and XFS

> We're not using it to do anything particularly novel yet, just doing normal filesystem stuff but done better and more cleanly, so far. And it's still not quite as general as I want; the main remaining limitation is that keys are fixed size at 160 bits (64 bit inum, 64 bit offset, 32 bit snapshot); key types really need to be per-btree definable, bpos has been increasingly overloaded in different places and it's annoying.

> It's also definitely nowhere near SQL, where you define tables and indexes and do joins; it's more of a NoSQL database. But it's got a solid transaction model, locking model (with a full cycle detector, as real databases do), triggers, nice iterators, lots of support for extending the database schema - it's generally quite pleasant to work with.

Don't confuse SQL and Relational, they're two completely separate things in a marriage :-)

And you say "NoSQL" - do you mean No SQL, or Not Only SQL? :-) (I'm sure you don't mean the database actually called "NoSQL" :-)

But it might be worth taking a look at Pick's Not Only SQL model. I don't understand what you're going about key types and btree especially, but Pick is hash-based not btree based. Investigate Linear/Dynamic hashing. That swaps btree's "all accesses take the same time" for hashing's "most accesses are extremely fast" and the linear/dynamic algorithm makes resizing order 1, not order N. I've been thinking about making ScarletDMEs hash buckets into btrees so in the worst case access degrades to btrees ?order root N? rather than a naive hash's order N. (And speeds up splitting an overflowed bucket, too.)

But if you're looking at "the file system is a database", don't restrict yourself to SQL/Relational. Just because it's taken the universities by storm so that nobody knows anything else, doesn't mean it's the best, or even has any ideas worth nicking :-)

Cheers,
Wol

to post comments

COW and volume management?

Posted Jan 27, 2026 15:07 UTC (Tue) by koverstreet (subscriber, #4296) [Link] (1 responses)

SQL may not be the prettiest language, and the relational model may not be what you want in every context - it's too abstracted when you really need to optimize for performance - but there's a reason it's taught, it's a good model, and it's something every programmer should probably know.

Hash tables are no-go in on disk data structures, they destroy locality and you can't do range lookups. Extents require range lookups, along with a lot of other things filesystems need to do, and we very frequently need to do efficient scans - btrees are much better suited to that.

Locality is a prime consideration when designing on disk data structures, and frequently you'll be doing short linear scans - linear searches are not slow as long as you keep them short.

E.g., the way bcachefs does full writeable snapshots, with versioning (so snapshots are at key granularity, not btree node granularity like btrfs) uses the low bits of the key as the snapshot ID - so a lookup finds either a key in the current snapshot, or an ancestor snapshot - that requires range lookups. But then for writeable snapshots, the snapshot ID is not a linear history, it's a tree; so we also have to skip over keys in unrelated branches of the snapshots tree. This search will be short for a variety of reasons (the main one being that creates always get a new inode number that won't be shared by any other snapshots), so snapshot lookups are fast; you can't do these kinds of tricks with hash tables.

COW and volume management?

Posted Jan 27, 2026 21:02 UTC (Tue) by Wol (subscriber, #4433) [Link]

> SQL may not be the prettiest language, and the relational model may not be what you want in every context - it's too abstracted when you really need to optimize for performance - but there's a reason it's taught, it's a good model, and it's something every programmer should probably know.

The relational *model* is great, yes. The engineering is flawed by design :-(

Pick allows you to stick a 4NF view directly into the database as a table row ... that's why an optimiser is a waste of time ... (now that most RDBMSs have arrays and structures, they've finally caught up, 40 years late, but SQL can't query them cleanly)

Cheers,
Wol