Electrified Filth

Electrified Filth

@ak47.io

tylerneely.com

1.2K followers178 following238 posts

Electrified Filth reposted

Hank Green
@hankgreen.bsky.social

Replying to @hankgreen.bsky.social

The advent of germ theory, vaccines, sanitation, and antibiotics, in this view, indirectly lead to an increase in social services, and a decrease in capital punishment, murder, slavery, and torture. In effect, it raised the value of human life in human eyes.

Electrified Filth
@ak47.io

I put together a talk for HYTRADBOI 2025 about my favorite technique for building databases or almost anything with high complexity - extreme rewriting!

HYTRADBOI@hytradboi.bsky.social

The program is up and tickets are live at www.hytradboi.com/2025/#program. I'll keep updating this thread as the last 10 talks hit camera-ready.

Electrified Filth
@ak47.io

Lately I've been playing around with a new type of LSM storage engine that has some interesting properties. Most LSM implementations split the sst data into blocks. But what if those blocks were stored in a heap instead of a file, and compaction only happened on overlapping blocks? Kinda Bε-like.

View full thread
Electrified Filth
@ak47.io

LSM, Bε, Bw trees all try to avoid moving data around until doing so can be amortized, with them forming a spectrum of how specifically a particular block/page can be rewritten in response to write locality. Plain LSM is locality blind. Bε rewrites data as it moves back. Bw is hyper local.

Electrified Filth
@ak47.io

The thing that appeals to me about the heap-backed LSM block approach is that it gives you a way to decide at runtime how much effort you will spend compacting overlapping ranges in order to make the overall block index more specific, while avoiding copying unchanging blocks as a plain LSM would.

Electrified Filth
@ak47.io

Lately I've been playing around with a new type of LSM storage engine that has some interesting properties. Most LSM implementations split the sst data into blocks. But what if those blocks were stored in a heap instead of a file, and compaction only happened on overlapping blocks? Kinda Bε-like.

View full thread
Electrified Filth
@ak47.io

And one of the nice things is that it is fairly clean to bolt this onto a heap-backed B+tree to give it nice LSM-style asymptotics for random write workloads while still retaining optimal B+tree write amplification for sequential writes via the block gifting trick.

Electrified Filth
@ak47.io

Compared to a Bw-Tree where you need to maintain pointers to every delta update that needs to be read along with the base page for a point lookup, this has a much lower metadata:data ratio, but that metadata is less specific, so filters are useful.

Electrified Filth
@ak47.io

Lately I've been playing around with a new type of LSM storage engine that has some interesting properties. Most LSM implementations split the sst data into blocks. But what if those blocks were stored in a heap instead of a file, and compaction only happened on overlapping blocks? Kinda Bε-like.

Electrified Filth
@ak47.io

While a naive Bε-tree still has the suboptimal LSM behavior on sequential writes of copying data several times from the tip to the leaf, this block-based LSM lets sequential writes immediately be "gifted" to the last "level" (but levels no longer exist as such).

Electrified Filth
@ak47.io

With an LSM, you tend to want to maintain an index of the ranges of keys that each sst block holds anyway. And for this block-first style, it does the same. But compaction becomes a bit more sophisticated, where range density can be more explicitly reasoned about.

Electrified Filth
@ak47.io

After 8.5 years in Germany, I finally earned the right to wear socks and sandals. Citizenship has been a goal for a long time- I’ve had to line up at 4am and dodge physical punches at the immigration office to compete for limited appointment slots for visas. Now it’s time for some exciting new goals

Electrified Filth
@ak47.io

Took a chance and used mezcal instead of red wine while making the sauce for this lasagna. The smokiness really goes well with the spicy salsiccia inside!

Electrified Filth
@ak47.io

Just increased the write throughput of my lock-free B+ tree by around 400% when it's dynamically detected that it's not being used concurrently. This is another benefit of selectively avoiding Sync in concurrent Rust. Also, now that I'm preparing to merge it into sled, I've made it MIT/Apache-2.0

github.comoptimize non concurrent insert by spacejam · Pull Request #6 · komora-io/concurrent-maplock-free B+ tree. Contribute to komora-io/concurrent-map development by creating an account on GitHub.
Electrified Filth
@ak47.io

Quorum Fixer and FlexiRaft are good examples of applying both operational and theoretical best practices while scaling up large numbers of quorum-based replicated systems.

v@handle.invalid

Meta has published a blog post on making MySQL distributed using Raft 🔗 https://engineering.fb.com/2023/05/16/data-infrastructure/mysql-raft-meta/

Electrified Filth
@ak47.io

Over time, "hard things" like lock-free programming seem easier than basics like using files or sockets. Any program that reads a file is concurrent w/ all processes that have ever written to it. Distributed systems are (indistinguishable from being) concurrent w/ infinite instances of themselves.

View full thread
Electrified Filth
@ak47.io

Even if it's a "single threaded program" - if that thread crashes and a user or the system starts another, bang - you're concurrent due to interacting through the shared state that is encoded (and possibly only partially encoded) into the file.

Electrified Filth
@ak47.io

So many problems collapse to "barrier engineering" where we just try to claw back a little bit of freedom to make assumptions about atomicity, monotonicity and idempotency to rebuild interesting things on top of again despite having files or sockets in the mix to open up funky concurrent histories.

Electrified Filth
@ak47.io

Over time, "hard things" like lock-free programming seem easier than basics like using files or sockets. Any program that reads a file is concurrent w/ all processes that have ever written to it. Distributed systems are (indistinguishable from being) concurrent w/ infinite instances of themselves.

Electrified Filth
@ak47.io

Even ignoring the large amount of subtle stuff around fsync & inode idiosyncrasies, anything that overwrites existing parts of a file becomes freakishly concurrent from a correctness perspective due to crash & recovery semantics.

You are up to date.