Simon Willison links to an idea that I immediately fell in love with, and will obviously never use. But that someone has done it makes me somehow happier.
I Saved a PNG Image To A Bird. Benn Jordan provides one of the all time great YouTube video titles, and it’s justified. He drew an image in an audio spectrogram, played that sound to a talented starling (internet celebrity “The Mouth”) and recorded the result that the starling almost perfectly imitated back to him.
Benn himself further says:
Hypothetically, if this were an audible file transfer protocol that used a 10:1 data compression ratio, that’s nearly 2 megabytes of information per second. While there are a lot of caveats and limitations there, the fact that you could set up a speaker in your yard and conceivably store any amount of data in songbirds is crazy.
Sometimes you have to write down an intent publicly to make sure you carry it through to the end. And so here is one such statement, to encourage me to complete this vital part of toykv.
I’ve started work on Simple Compaction · Issue #24 · mikerhodes/toykv. I’d been putting it off for a while — it felt big, and tackling it in the short evening blocks of time I usually have seemed a bit overwhelming.
To make it more manageable, I spent the first hour dividing the work into several “versions”, creating an iterative path to the simplest compaction scheme: merge all sstables into a single sorted run. This broke the back of the task: three hours in, I’ve now reached version 2 of 7.
The top-level method is deceptively, but pleasingly, simple:
// Attempt to run a compaction on the stored data. The exact
// compaction carried out is opaque to the caller.
pub fn compact(&mut self) -> Result<(), ToyKVError> {
// v2 compaction just compacts all existing sstables
// in L0 into a single L0 table. This is implemented
// with SimpleCompactionPolicy.
let policy = SimpleCompactionPolicy::new();
// Guard ensures only one compaction can happen at a time.
let _guard = CompactionGuard::acquire(self.state.clone())?;
// Get a table compaction task from the sstables structure.
let c_task = {
let state = self.state.read().unwrap();
state.sstables.build_compaction_task_v2(policy)?
};
// Compaction task is safe to run outside state lock, to
// allow reads and writes to continue while we compact.
let c_result = c_task.compact_v2()?;
// Commit the compacted table while holding write lock.
{
let mut state = self.state.write().unwrap();
state.sstables.try_commit_compaction_v2(c_result)?;
}
self.metrics.compacts.fetch_add(1, Ordering::Relaxed);
Ok(())
}
And so here is my stake in the ground, my statement to say, “Behold, for this is something I intend to complete!” 😬
This is a brief tale, told mostly through links, about subtlety. And fsync,
though perhaps the two are synonymous.
While I’m writing about this in September, the events actually happened back around March; I intended to write this up back then, but somehow it just never happened.
Earlier this year, I read NULL BITMAP Builds a Database #2: Enter the Memtable. At the end, Justin Jaffray mentions a potential sad path when the database you are coding up (as one does) crashes. Here, we are talking about whether the database can accidentally lie to a reader about whether a write is on-disk (durable):
I do a write, and it goes into the log, and then the database crashes before we fsync. We come back up, and the reader, having not gotten an acknowledgment that their write succeeded, must do a read to see if it did or not. They do a read, and then the write, having made it to the OS’s in-memory buffers, is returned. Now the reader would be justified in believing that the write is durable: they saw it, after all. But now we hard crash, and the whole server goes down, losing the contents of the file buffers. Now the write is lost, even though we served it!
The solution is easy: just fsync the log on startup so that any reads we do are based off of data that has made it to disk.
If you’re anything like me, that will take you at least three reads to get the order of events straight in your head. But once I did, it felt right to me. As I work on a database, I thought I’d ask the team whether we did that. I was pretty sure we did, but it’s part of my job to double-check these things when I come across them.
Herewith, the story and the warning about subtlety.
In June Journal, I left off with a thought to make toykv thread-safe and to implement simple compaction. I did get to thread-safety, which took a while, but I didn’t get to compaction. I did make several other improvements, however.
I also did some work on ai-codeexplorer. Here, I now have a work in progress UI using textual, a python terminal UI toolkit. I haven’t merged it to master yet as it’s incomplete. It was interesting to work with an event driven UI toolkit again, however, it’s been quite a long time since I’ve done that.
Overall, it wasn’t as productive as previous months, but school holidays do that to a person; there’s plenty of other things to do!
I really enjoyed this transcript of a talk. It’s an exploration of the design space of distributed consensus by Alex Miller, who I first came across several years ago when Cloudant were looking at FoundationDB; Alex was one of the primary authors. He knows his stuff. There are several great papers linked in the post.
This talk is an extension of my earlier Data Replication Design Spectrum blog post. The blog post was the analysis of the various replication algorithms, which concludes with showing that Raft has no particular advantage along any easy analyze/theoretical dimension. This builds on that argument to try and persuade you out of using Raft and to supply suggestions on how to work around the downsides of quorum-based or reconfiguration-based replication which makes people shy away from them.