About Phil Eaton

2024-08-24 08:00:00

In your professional and personal life, I don't believe there is a stronger motivation than having something in mind and the desire to do it. Yet the natural way to deal with a desire to do something is to justify why it's not possible.

"I want to read more books but nobody reads books these days so how could I."

"I want to write for a magazine but I have no experience writing professionally."

"I want to build a company someday but how could someone of my background."

Our official mentors, our managers, through a combination of well-intentioned defeatism and well-intentioned lack of accomplishment themselves, among other things, are often unable to process big goals or guide you toward them.

I've been one of these managers myself. In fact I have, to my immense regret, tried too often to convince people to do what is practical rather than what they want to do. Or to do what I judged they were capable of doing rather than what they wanted to do.

In the best cases, my listener had the self-confidence to ignore me. They did what they wanted to do anyway. In the worst case, again to my deep regret, I've been a well-intentioned part of derailing someone's career for years.

So I don't want to convince anyone of anything anymore. If I start trying to convince someone by accident, I try to catch myself. I try to avoid sentences like "I think you should …". Instead "Here is something that's worked for me: …" or "Here is what I've heard works well for other people: …".

Nobody wants to be convinced. But intelligent people will change their mind when exposed to new facts or different ideas. Being convinced is a battle of will. Changing one's mind is a purely personal decision.

There are certainly people with discipline who can grind on things they hate doing and eventually become experts at it. But more often I see people grind on things they hate only to become depressed and give up.

For most of us, our best hope is (healthy) obsession. And obsession, in the sense I'm talking about, does not come from something you are ambivalent about or hate. Obsession can only come when you're doing something you actually want to do.

For big goals or big changes, you need regular commitment weekly, monthly, yearly. Over the course of years. And only obsession makes that work not actually feel like work. Obsession is the only thing that makes discipline not feel like discipline.

That big goals take years to accomplish need not be scary. Obsession doesn't mean you can't pivot. There is quite a lot to gain by committing to something regularly over the course of years even if you decide to stop and commit from then on to something else. You will learn a good deal.

And healthy obsession to me is more specifically measurable on the order of weeks, not hours or days. Healthy obsession means you're still building healthy personal and professional relationships. You're still taking care of yourself, emotionally and physically.

I do not have high expectations for people in general. This seems healthy and reasonable. But as I meet more people and observe them over the years, I am only more convinced of the vast potential of individuals. Individuals are almost universally underestimated.

I think you can do almost anything you want to do. If you commit to do doing it.

I'll end this with a personal story.

Until 11th grade, I hated school. I hated the rigidity. Being forced to be somewhere for hours and to follow so many rules. I skipped so many days of school I'm embarrassed by it. I'd never do homework at home. I never studied for tests. I got Bs and Cs in the second-tier classes. I was in the orchestra for 6 years and never practiced at home. I was not cool enough to be a "bad kid" but I did not understand the system and had no discipline whatsoever.

I found out at the end of 10th grade that I could actually afford college if I got into a good enough school that paid full needs-based tuition. It sounded significantly better than the only other option that seemed obvious, joining the military as a recruit. I realized and decided that if I wanted to get into a good school I needed to not half-ass things.

Somehow, I decided to only do things I could become obsessed with. And I decided to be obsessed in the way that I wanted, not to do what everyone else did (which I basically could not do since I had no discipline). If we covered a topic in class, I'd read news about it or watch movies about it. I'd get myself excited about the topic in every way I could.

It basically worked out. I ended high school in the top 10% of the class (up from top 40% or something). I got into a good liberal arts college that paid the entirety of my tuition. But I remained a basically lazy and undisciplined person. I never stayed up late studying for a test. I dropped out after a year and a half for family reasons.

But I've now spent the last 10 years in my spare time working on compiler projects, interpreter projects, parser projects, database projects, distributed systems projects. I've spent the last 6 years consistently publishing at least one blog post per month.

I didn't want to work the way everyone else worked. I wanted to be obsessed about what I worked on.

Obsession has made all of this into something I now barely register as doing. It's allowed me to continue adding activities like organizing book clubs and meetups to the list of things I'm up to. Up until basically this year I could have in good faith said I am a very lazy and undisciplined person. But obsession turned me into someone with discipline.

Obsession became about more than just the tech. It meant trying to fully understand the product, the users, the market. It meant thinking more carefully about product documentation, user interfaces, company messaging. Obsession meant reflecting on how I treat my coworkers, and how my coworkers feel treated by others in general. Obsession meant wanting an equitable and encouraging work environment for everyone.

And, as I said, it's about healthy obsession. I didn't really understand the "healthy" part until a few years ago. But I'm now convinced that the "healthy" part is as important as the "obsession" part. To go to the gym regularly. To play pickup volleyball. To cook excellent food. To read fiction and poetry and play music. To serve the community. To be friendly and encouraging to all people. To meet new people and build better genuine friendships.

And in the context of work, "healthy obsession" means understanding you can't do everything, even while you care about everything. It means accepting that you make mistakes and that you do your best; that you try to do better and learn from mistakes the next time.

It's got to be sustainable. And we can develop a healthy obsession while we have quite a bit of fun too. :)

I wrote an essay on my mistakes trying to convince people to do something, on doing what you want to do, and on obsession.

Ended with a personal note on developing healthy discipline, and having fun. :)https://t.co/4WWdtU6AhL pic.twitter.com/lBw7zlqWeq

— Phil Eaton (@eatonphil) August 24, 2024

2024-08-20 08:00:00

Bugs in distributed systems are hard to find, largely because systems interact in chaotic ways. And even once you've found a bug, it can be anywhere from simple to impossible to reproduce it. It's about as far away as you can get from the ideal test environment: property testing a pure function.

But what if we could write our code in a way that we can isolate the chaotic aspects of our distributed system during testing: run multiple systems communicating with each other on a single thread and control all randomness in each system? And property test this single-threaded version of the distributed system with controlled randomness, all the while injecting faults (fancy term for unhappy path behavior like errors and latency) we might see in the real-world?

Crazy as it sounds, people actually do this. It's called Deterministic Simulation Testing (DST). And it's become more and more popular with startups like FoundationDB, Antithesis, TigerBeetle, Polar Signals, and WarpStream; as well as folks like Tyler Neely and Pekka Enberg, talking about and making use of this technique.

It has become so popular to talk about DST in my corner of the world that I worry it risks coming off sounding too magical and maybe a little hyped. It's worth getting a better understanding of both the benefits and the limitations.

Thank you to Alex Miller and Will Wilson for reviewing a version of this post.

Randomness and time

A big source of non-determinism in business logic is the use of random numbers—in your code or your transitive dependencies or your language runtime or your operating system.

Crucially, DST does not imply you can't have randomness! DST merely assumes that you have a global seed for all randomness in your program and that the simulator controls the seed. The seed may change across runs of the simulator.

Once you observe a bad state as a result of running the simulation on a random seed, you allow the user to enter the same seed again. This allows the user to recreate the entire program run that led to that observed bad state. Allows the user to debug the program trivially.

Another big source of non-determinism is being dependent on time. As with randomness, DST does not mean you can't depend on time. DST means you must be able to control the clock during the simulation.

To "control" randomness or time basically means you support dependency injection, or the old-school alternative to dependency injection called passing the dependency as an explicit parameter. Rather than referring to a global clock or a global seed, you need to be able to receive a clock or a seed from someone.

For example we might separate the operation of an application into the language's main() entrypoint and an actual application start() entrypoint.

# app.pseudocode

def start(clock, seed):
  # lots of business logic that might depend on time or do random things

def main:
  clock = time.clock()
  seed = time.now()
  app.start(clock, seed)

The application entrypoint is where we must be able to swap out a real clock or real random seed for one controlled by our simulator:

# sim.pseudocode

import "app.pseudocode"

def main:
  sim_clock = make_sim_clock()
  sim_seed = os.env.DST_SEED or time.now()
  try:
    app.start(sim_clock, sim_seed)
  catch(e):
    print("Bad execution at seed: %s", sim_seed)
    throw e

Let's look at another example.

Converting an existing function

Let's say that we had a helper method that kept calling a function until it succeeded, with backoff.

# retry.pseudocode
class Backoff:
  def init:
    this.rnd = rnd.new(seed = time.now())
    this.tries = 0

  async def retry_backoff(f):
    while this.tries < 3:
      if f():
        return

      await time.sleep(this.rnd.gen())
      this.tries++

There is a single source of nondeterminism here and it's where we generate a seed. We could parameterize the seed, but since we want to call time.sleep() and since in DST we control the time, we can just parameterize time.

# retry.psuedocode
class Backoff:
  def init(this, time):
    this.time = time
    this.rnd = rnd.new(seed = this.time.now())
    this.tries = 0

  async def retry_backoff(this, f):
    while this.tries < 3:
      if f():
        return

      await this.time.sleep(this.rnd.gen())
      this.tries++

Now we can write a little simulator to test this:

# sim.psuedocode
import "retry.pseudocode"

sim_time = {
  now: 0
  sleep: (ms) => {
    await future.wait(ms)
  }
  tick: (ms) => now += ms
}

backoff = Backoff(sim_time)

while true:
  failures = 0
  f = () => {
    if rnd.rand() > 0.5:
      failures++
      return false

    return true
  }
  try:
    while sim_time.now < 60min:
      promise = backoff.retry_backoff(f)
      sim_time.tick(1ms)
      if promise.read():
        break

    assert_expect_failure_and_expected_time_elapse(sim_time, failures)
  catch(e):
    print("Found logical error with seed: %d", seed)
    throw e

This demonstrates a few critical aspects of DST. First, the simulator itself depends on randomness. But allows the user to provide a seed so they can replay a simulation that discovers a bug. The controlled randomness in the simulator is what lets us do property testing.

Second, the simulation workload must be written by the user. Even when you've got a platform like Antithesis that gives you an environment for DST, it's up to you to exercise the application.

Now let's get a little more complex.

A single thread and asynchronous IO

The determinism of multiple threads can only be controlled at the operating system or emulator or hypervisor layer. Realistically, that would require third-party systems like Antithesis or Hermit (which, don't get excited, is not actively developed and hasn't worked on any interesting program of mine) or rr.

These systems transparently transform multi-threaded code into single threaded code. But also note that Hermit and rr have only limited ability to do fault injection which, in addition to deterministic execution, is a goal of ours. And you can't run them on a mac. And can't run them on ARM.

But we can, and would like, to write a simulator without writing a new operating system or emulator or hypervisor, and without a third-party system. So we must limit ourselves to writing code that can be collapsed into a single thread. Significantly, since using blocking IO would mean an entire class of concurrency bugs could not be discovered while running the simulator in a single thread, we must limit ourselves to asynchronous IO.

Single threaded and asynchronous IO. These are already two big limitations.

Some languages like Go are entirely built around transparent multi-threading and blocking IO. Polar Signals solved this for DST by compiling their application to WASM where it would run on a single thread. But that wasn't enough. Even on a single thread, the Go runtime intentionally schedules goroutines randomly. So Polar Signals forked the Go runtime to control this randomness with an environment variable. That's kind of crazy. Resonate took another approach that also looks cumbersome. I'm not going to attempt to describe it. Go seems like a difficult choice of a language if you want to do DST.

Like Go, Rust has no builtin async IO. The most mature async IO library is tokio. The tokio folks attempted to provide a tokio-compatible simulator implementation with all sources of nondeterminism removed. From what I can tell, they did not at any point fully succeed. That repo has now been replaced with a "this is very experimental" tokio-rs project called turmoil that provides deterministic execution plus network fault injection. (But not disk fault injection. More on that later.) It isn't surprising that it is difficult to provide deterministic execution for an IO library that was not designed for it. tokio is a large project with many transitive dependencies. They must all be combed for non-determinism.

On the other hand, Pekka has already demonstrated for us how we might build a simpler Rust async IO library that is designed to be simulation tested. He modeled this on the TigerBeetle design King and I wrote about two years ago.

So let's sketch out a program that does buggy IO and let's look at how we can apply DST to it.

# readfile.pseudocode
def read_file(io, name, into_buffer):
  f = await io.open(name)
  read_buffer = [4096]u8{}
  while true:
    err, n_read = await f.read(&read_buffer)
    if err == io.EOF:
      into_buffer.copy_maybe_allocate(read_buffer[0:sizeof(read_buffer)])
      return

    if err:
      throw err

    into_buffer.copy_maybe_allocate(read_buffer[0:sizeof(read_buffer)])

In our simulator, we will provide a mocked out IO system and we will randomly inject various errors while asserting pre- and post-conditions.

# sim.psuedocode
import "readfile.pseudocode"

seed = if os.env.DST_SEED ? int(os.env.DST_SEED) : time.now()
rnd = rnd.new(seed)

while true:
  sim_disk_data = rnd.rand_bytes(10MB)
  sim_fd = {
    pos: 0
    EOF: Error("eof")
    read: (fd, buf) => {
      partial_read = rnd.rand_in_range_inclusive(0, sizeof(buf))
      memcpy(sim_disk_data, buf, fd.pos, partial_read)
      fd.pos += partial_read
      if fd.pos == sizeof(sim_disk_data):
        return io.EOF, partial_read
      return partial_read 
    }
  }
  sim_io = {
    open: (filename) => sim_fd
  }

  out_buf = Vector<u8>.new()
  try:
    read_file(sim_io, "somefile", out_buf)
    assert_bytes_equal(out_buf.data, sim_disk_data)
  catch (e):
    print("Found logical error with seed: %d", seed)
    throw e

And with this simulator we would have eventually caught our partial read bug! In our original program when we wrote:

      into_buffer.copy_maybe_allocate(read_buffer[0:sizeof(read_buffer)])

We should have written:

      into_buffer.copy_maybe_allocate(read_buffer[0:n_read])

Great! Let's get a little more complex.

A distributed system

I already mentioned in the beginning that the gist of deterministic simulation testing a distributed system is that you get all of the nodes in the system to run in the same process. This would be basically impossible if you wanted to test a system that involved your application plus Kafka plus Postgres plus Redis. But if your system is a self-contained distributed system, such as one that embeds a Raft library for high availability of your application, you can actually run multiple nodes into the same process!

For a system like this, our simulator might look like:

# sim.pseudocode
import "distsys-node.pseudocode"

seed = if os.env.DST_SEED ? int(os.env.DST_SEED) : time.now()
rnd = rnd.new(seed)

while true:
  sim_fd = {
    send(fd, buf) => {
      # Inject random failure.
      if rnd.rand() > .5:
         throw Error('bad write')

      # Inject random latency.
      if rnd.rand() > .5:
        await time.sleep(rnd.rand())

      n_written = assert_ok(os.fd.write(buf))
      return n_written
    },
    recv(fd, buf) => {
      # Inject random failure.
      if rnd.rand() > .5:
         throw Error('bad read')

      # Inject random latency.
      if rnd.rand() > .5:
        await time.sleep(rnd.rand())

      return os.fd.read(buf)
    }
  }
  sim_io = {
    open: (filename) => {
      # Inject random failure.
      if rnd.rand() > .5:
        throw Error('bad open')

      # Inject random latency.
      if rnd.rand() > .5:
        await time.sleep(rnd.rand())

      return sim_fd
    }
  }

  all_ports = [6000, 6001, 6002]
  nodes = [
    await distsys-node.start(sim_io, all_ports[0], all_ports),
    await distsys-node.start(sim_io, all_ports[1], all_ports),
    await distsys-node.start(sim_io, all_ports[2], all_ports),
  ]
  history = []
  try:
    key = rnd.rand_bytes(10)
    value = rnd.rand_bytes(10)
    nodes[rnd.rand_in_range_inclusive(0, len(nodes)].insert(key, value)
    history.add((key, value))
    assert_valid_history(nodes, history)

    # Crash a process every so often
    if rnd.rand() > 0.75:
      node = nodes[rnd.rand_in_range_inclusive(0, 3)]
      node.restart()
  catch (e):
    print("Found logical error with seed: %d", seed)
    throw e

I'm completely hand waving here to demonstrate the broader point and not any specific testing strategy for a specific distributed system. The important points are that these three nodes run in the same process, on different ports.

We control disk IO. We control network IO. We control how time elapses. We run a deterministic simulated workload against the three node system while injecting disk, network, and process faults.

And we are constantly checking for an invalid state. When we get the invalid state, we can be sure the user can easily recreate this invalid state.

Other sources of non-determinism

Within some error margin, most CPU instructions and most CPU behavior are considered to be deterministic. There are, however, certain CPU instructions that are definitely not. Unfortunately that might include system calls. It might also include malloc. There is very little to trust.

If we ignore Antithesis, people doing DST seem not to worry about these smaller bits of nondeterminism. Yet it's generally agreed that DST is still worthwhile anyway. The intuition here is that every bit of non-determinism you can eliminate makes it that much easier to reproduce bugs when you find them.

Put another way: determinism, even among DST practitioners, remains a spectrum.

Considerations

As you may have noticed already from some of the pseudocode, DST is not a panacea.

Consideration 1: Edges

First, because you must swap out non-deterministic parts of your code, you are not actually testing the entirety of your code. You are certainly encouraged to keep the deterministic kernel large. But there will always be the non-deterministic edges.

Without a system like Antithesis which gives you an entire deterministic machine, you can't test your whole program.

But even with Antithesis you cannot test the integration between your system and external systems. You must mock out the external systems.

It's also worth noting that there are many areas where you could inject simulation. You could do it at a high-level RPC and storage layer. This would be simpler and easier to understand. But then you'd be omitting testing and error-handling of lower-level errors.

Consideration 2: Your workload(s)

DST is dependent on your creativity and thoroughness of your workload as much as any other type of test or benchmark.

Just as you wouldn't depend on one single benchmark to qualify your application, you may not want to depend on a single simulated workload.

Or as Will Wilson put it for me:

The biggest challenge of DST in my experience is that tuning all the random distributions, the parameters of your system, the workload, the fault injection, etc. so that it produces interesting behavior is very challenging and very labor intensive. As with fuzzing or PBT, it's terrifyingly easy to build a DST system that appears to be doing a ton of testing, but actually never explores very much of the state space of your system. At FoundationDB, the vast majority of the work we put into the simulator was an iterative process of hunting for what wasn't being covered by our tests and then figuring out how to make the tests better. This process often resembles science more than it does engineering.

Unfortunately, unlike with fuzzing, mere branch coverage in your code is usually a pretty poor signal for the kinds of systems you want to test with DST. At Antithesis we handle this with Sometimes assertions, at FDB we did something pretty similar, and I assume TigerBeetle and others have their own version of this. But of course the ultimate figure of merit is whether your DST system is finding 100% of your bugs. It's quite difficult to get to the point that it does. The truly ambitious part of Antithesis isn't the hypervisor, but the fact that we also aim to solve the much harder "is my DST working?" problem with minimal human guidance or supervision.

Consideration 3: Your knowledge of what you mocked

When you mock out the behavior of disk or network IO, the benefits of DST are tied to your understanding of the spectrum of behavior that may happen in the real world.

What are all possible error conditions? What are the extreme latency bounds of the original method? What about corruption or misdirected IO?

The flipside here is that only in deterministic simulation testing can you configure these crazy scenarios to happen at a configurable regularity. You can kick off a set of runs that have especially high IO latency or especially high corrupt reads/writes. Joran and I wrote a year ago about how the TigerBeetle simulator does exactly this.

Consideration 4: Non-reproducible seeds as code changes

Critically, the reproducibility of DST only helps so long as your code doesn't change. As soon as your code changes, the seed may no longer even get you to the state where the bug was exhibited. So the reproducibility of DST means more that it may help you convert the seed simulation run into an integration test that describes the precise scenario even as the code changes.

Consideration 5: Time and compute

Because of Consideration 4, you need to keep rerunning the simulator not just to keep finding new seeds and new histories but because the new seeds and new histories may change every time you make changes to code.

What about Jepsen?

Jepsen does limited process and network fault injection while testing for linearizability. It's a fantastic project.

However, it represents only a subset of what is possible with Deterministic Simulation Testing (if you actually put in the effort described above to get there).

But even more importantly, Jepsen has nothing to do with deterministic execution. If Jepsen finds a bug and your system can't do deterministic execution, you may or may not be able to reproduce that Jepsen bug.

Here's another Will Wilson quote for you on Jepsen and FoundationDB:

Anyway, we did [Deterministic Simulation Testing] for a while and found all of the bugs in the database. I know, I know, that’s an insane thing to say. It’s kind of true though. In the entire history of the company, I think we only ever had one or two bugs reported by a customer. Ever. Kyle Kingsbury aka “aphyr” didn’t even bother testing it with Jepsen, because he didn’t think he’d find anything.

Conclusion

The degree to which you can place faith in DST alone, and not time spent in production, has limits. However, it certainly does no harm to employ DST. And, barring the considerations described above, will likely make the kernel of your product significantly more stable. Furthermore, everyone who uses DST knows about these considerations. But I think it's worthwhile to list them out to help folks who do not know DST to build an intuition for what it's excellent at.

Further reading:

• "Testing Distributed Systems w/ Deterministic Simulation" by Will Wilson
• (Mostly) Deterministic Simulation Testing in Go
• Magical Deterministic Simulator for distributed systems in Rust

I wrote a new post talking through the basics, considerations, and limitations of Deterministic Simulation Testing.https://t.co/9Fp5ytL7Wz pic.twitter.com/xRE6FOwc0P

— Phil Eaton (@eatonphil) August 20, 2024

2024-07-30 08:00:00

This is an external post of mine. Click here if you are not redirected.

2024-07-07 08:00:00

This year has seen a resurgence in really high quality systems programming meetups. Munich Database Meetup, Berlin Systems Group, SF Distributed Systems Meetup, NYC Systems, Bengaluru Systems, to name a few.

This post summarizes a bit of disappointing recent tech meetup history, the new trend of excellent systems programming meetups, and ends with some encouragement and guidance for running your own systems programming events.

I will be a little critical in this post but I want to preface by saying: organizing meetups is really tough! It takes a lot of work and I have a huge amount of respect for meetup organizers even when their meetup style did not resonate with me.

Although much of this post talks about NYC Systems, the reason I think this post is worth writing is because so many other meetups in a similar vein popped up. I hope to encourage these other meetups and to encourage folks in other major metros (London, for example) to start similar meetups.

Meetups

I used to attend a bunch of meetups before the pandemic. But I quickly got disillusioned. Almost every meetup was varying degrees of startups pitching their product. The last straw for me was sitting through a talk at a JavaScript meetup that was by a devrel employee of a startup who literally gave a tutorial for their product.

There were also some pretty intelligent meetups like the New York Haskell Users Group and the New York Emacs Meetup. But not being an expert in either domain, and the attendees almost solely appearing to be experts, I didn't particularly enjoy going.

There were a couple of meetups that felt inclusive for various skill-levels of attendees yet still went into interesting depth. Specifically, New York Linux User Group and Papers We Love NYC.

These meetups were exceptional because they were language- and framework-agnostic, they would start broad to give you background, but then go deep into a topic. Maybe you only understood 50% of what was covered. But you get exposed to something new from an expert in that domain.

Unfortunately, the pandemic happened and these two excellent meetups basically have not come back.

A couple of students in Munich

The pandemic ended and I tried a couple of meetups I thought might be better quality. Rust and Go. But they weren't much better than I remembered. People would give a high level talk and brush over all the interesting concepts.

I had been thinking of doing an in-person talk series since 2022.

If I put together a systems/databases/distributed systems meetup in NYC (a physical meetup, not Zoom), who'd be interested (in attending, or presenting, or helping me organize, or donating space)?

No promises!

— Phil Eaton (@eatonphil) September 27, 2022

But I was busy with TigerBeetle until December of 2023 when I was messaged on LinkedIn by Georg Kreuzmayr, a graduate student at Technical University of Munich (TUM).

Georg and his friends, fellow graduate students at TUM, started a database club: TUMuchData. We got to talking about opportunities for collaboration and I started feeling a bit embarrassed that a graduate student had more guts than I had to get back onto the meetup organizer wagon.

A week later, with assurance from Justin Jaffray that at least he would show up with me if no one else did, I started the NYC Systems Coffee Club to bring together folks in NYC interested in any topic of systems programming (e.g. compilers, databases, web browser internals, distributed systems, formal methods, etc.). To bring them together in a completely informal setting for coffee at 9am in the morning in a public space in midtown Manhattan.

Trying something new! If you're a dev in NYC working
on (or interested in) systems programming, grab a coffee and come hang out at 1 Bryant Park (indoor space) this Thursday 9AM - 9:30AM.

See post for details and fill out the Google Form or DM me!https://t.co/A4bzcPGy6x pic.twitter.com/n1ECMd59ev

— Phil Eaton (@eatonphil) December 11, 2023

I set up that linked web page and started collecting subscribers to the club via Google Form. Once a month I'd send an email out to the list asking for RSVPs to this month's coffee club. The first 20 to respond would get a calendar invite.

And about the same time I started asking around on Twitter/LinkedIn if someone would be interested in co-organizing a new systems programming meetup in NYC. Angelo Saraceno immediately took me up on the idea and we met up.

NYC Systems

We agreed on the premise: this would be a language- and framework-agnostic meetup that was focused on engineering challenges, not product pitches. It would be 100% for the sake of corporate marketing, but corporate marketing of the engineering team, not the product.

NYC Systems was born!

We'd find speakers who could start broad and dive deep into some interesting aspect of databases, programming languages, distributed systems, and so on. Product pitches were necessary to establish a context, but the focus of the talk would be about some interesting recent technical challenge and how they dealt with it.

We'd schedule talks only every other month to ease our own burden in organizing and finding great speakers.

Once Angelo and I had decided to go forward, the next two challenges were finding speakers and finding a venue. Thanks to Twitter and LinkedIn, finding speakers turned out to be the easy part.

It was harder to find a venue. It was surprisingly challenging to find a company in NYC with a shared vision that the important thing about being associated with a meetup like this is to be associated with the quality of speakers and audience we can bring in by not allowing transparent product pitches.

Almost every company in Manhattan with space we spoke with had a requirement that they have their own speaker each night. That seemed like a bad idea.

I think it was especially challenging to find a company willing to relax about branding requirements like this because we were a new meetup.

It was pretty frustrating not to find a sympathetic company with space in Manhattan. And the only reason we didn't give up was because Angelo was so adament that this kind of meetup actually happen. It's always best to start something new with someone else for this exact reason. You can keep each other going.

In the end we went with the company that did not insist on their own speaker or their own branding. A Brooklyn-based company whose CEO immediately got in touch with me that they wanted to host us, Trail of Bits.

How it works

To keep things easy, I set up a web page on my personal site with information about the meetup. (Eventually we moved this to nycsystems.xyz.) I set up a Google Form to collect emails for a mailing list. And we started posting about the group on Twitter and LinkedIn.

Very pleased to share the first NYC Systems Talks are taking place next Thursday Feb 22nd 6PM. Hosted by @trailofbits, with @paulgb and @StefanKarpinski speaking.

Space is not infinite, fill out the Google Form if you can attend and would like an invite!https://t.co/jNssr5v1kJ

— Phil Eaton (@eatonphil) February 15, 2024

We published the event calendar in advance (an HTML table on the website) and announced each event's speakers a week in advance of the event. I'd send another Google Form to the mailing list taking RSVPs for the night. The first 60 people to respond got a Google Calendar invite.

It's a bit of work, sure, but I'd do anything to avoid Meetup.com.

It is interesting to see every new systems programming meetup also not pick Meetup.com. The only one that went with it, Munich Database Meetup, is a revival of an existing group, the Munich NoSQL Meetup and presumably they didn't want to give up their subscribers. Though most others use lu.ma.

The mailing list is now about 400+ people. And in each event RSVP we have a wait list of 20-30 people. Of course although 60 people say Yes initially, by the time of the event we have typically gotten about 50 people in attendance.

At each event, Trail of Bits provided screens, chairs, food, and drink. Angelo had recording equipment so he took over audio/video capturing (and later editing and publishing).

After each event we'd publish talk videos to our @NYCSystems Youtube.

Network effects

In March 2024, the TUMuchData folks joined Alex Petrov's Munich NoSQL Meetup to form the Munich Database Meetup. In May, Kaivalya Apte and Manish Gill started the Berlin Systems Group, inspired by Alex and the Munich Database Meetup.

I want to start a Berlin Database/Storage systems group, where we have regular meetups, discussions and talks.

WDYT? @mgill25 @mehd_io @ClickHouseDB @SnowflakeDB @awscloud @GoogleDE @TUBerlin

Can I get some support? Who else would be interested? #Databases

Thanks…

— Kaivalya Apte - The Geek Narrator (@thegeeknarrator) May 15, 2024

In May 2024, two PhD students in the San Francisco Bay Area, Shadaj Laddad and Conor Power, started the SF Distributed Systems meetup.

We’re super excited to be organizing a new SF Distributed Systems meetup NEXT WEEK! Our first meetup features @julianhyde and @conor_power23 presenting work on extending SQL and applying algebraic properties, sign up at https://t.co/d2lLDaQ5iJ

— Shadaj Laddad (@ShadajL) May 15, 2024

And in July 2024, Shraddha Agrawal, Anirudh Rowjee and friends kicked off the first Bengaluru Systems Meetup.

Are you ready, Systems Enthusiasts of Bengaluru?

Speaking at our first-ever meetup on 6th July, we have:@simsimsandy with "Learn about the systems that power GenAI applications" and @vivekgalatage with "The Browser Backstage: Performance vs Security"
(talks linked below!)

— Bengaluru Systems Meetup (@BengaluruSys) July 4, 2024

Suggestions

First off, don't pay for anything yourself. Find a company who will host. At the same time, don't feel the need to give in too much to the demands of the company. I'd be happy to help you think through how to talk about the event with companies. It is mutually beneficial for them to get to give a 5-minute hiring/product pitch and not need to do extensive branding nor to give a 30-minute product tutorial.

Second, keep a bit of pressure on speakers to not do an overview talk and not to do a product pitch. Suggest that they tell the story of some interesting recent bug or interesting recent feature. What happened? Why was it hard? What did you learn?

Focusing on these types of talks will help you get a really interesting audience.

I have been continuously surprised and impressed at the folks who show up for NYC Systems. It's a mix of technical founders in the systems space, pretty experienced developers in the systems space, graduate students, and developers of all sorts.

I am certain we can only get these kinds of folks to show up because we avoid product pitch-type talks.

Third, finding speakers is still hard! The best approach so far has been to individually message folks in industry and academia who hang out on Twitter. Sending out a public call is easy but doesn't often pan out. So keep an eye on interesting companies in the area.

Another avenue I've been thinking about is messaging VC connections to ask them if they know any engineers/technical founders/CTOs in the area who could give an interesting technical talk.

Fourth, speak with other organizers! I finally met Alex Petrov in person last month and we had a great time talking about the challenges and joys of organizing really high quality meetups.

I'm always happy to chat, DMs are open.

New post telling a bit of the history behind https://t.co/NEh1tm8v3Q; why it only exists due to folks like @georg_kreuzmayr and @ngeloxyz; the explosion of systems meetups around the world; and encouragement and suggestions for future organizers!https://t.co/dwe4TtmXKK pic.twitter.com/ZMLkVYdZDJ

— Phil Eaton (@eatonphil) July 7, 2024

2024-07-01 08:00:00

A database does not need a write-ahead log (WAL) to achieve durability. A database can write its long-term data structure durably to disk before returning to a client. Granted, this is a bad idea! And granted, a WAL is critical for durability by design in most databases. But I think it's helpful to understand WALs by understanding what you could do without them.

So let's look at what terrible design we can make for a durable database that has no write-ahead log. To motivate the idea of, and build an intuition for, a write-ahead log.

Thank you to Alex Miller for reviewing a version of this post.

But first, what is durability?

Durability

Durability happens in the context of a request a client makes to a data system (either an embedded system like SQLite or RocksDB or a standalone system like Postgres). Durability is a spectrum of guarantees the server provides when a client requests to write some data: that either the request succeeds and the data is safely written to disk, or the request fails and the client must retry or decide to do something else.

It can be difficult to set an absolute definition for durability since different databases have different concepts of what can go wrong with disks (also called a "storage fault model"), or they have no concept at all.

Let's start from the beginning.

An in-memory database

An in-memory database has no durability at all. Here is pseudo-code for an in-memory database service.

db = btree()

def handle_write(req):
  db.update(req.key, req.value)
  return 200, {}

def handle_read(req):
  value = db.read(req.key)
  return 200, {"value": value}

Throughout this post, for the sake of code brevity, imagine that the environment is concurrent and that data races around shared mutable values like db are protected somehow.

Writing to disk

If we want to achieve the most basic level of durability, we can write this database to a file.

f = open("kv.db")
db = btree.init_from_disk(f)

def handle_write(req):
  db.update(req.key, req.value)
  db.write_to_disk(f)
  return 200, {}

def handle_read(req):
  value = db.read(req.key)
  return 200, {"value": value}

btree.write_to_disk will call pwrite(2) under the hood. And we'll assume it does copy-on-write for only changed pages. So imagine we have a large database represented by a btree that takes up 10GiB on disk. With the btree algorithm, if we write a single entry to the btree, often only a single (often 4Kib) page will get written rather than all pages (holding all values) in the tree. At the same time, in the worst case, the entire tree (all 10GiB of data) may need to get rewritten.

But this code isn't crash-safe. If the virtual or physical machine this code is running on reboots, the data we wrote to the file may not actually be on disk.

fsync

File data is buffered by the operating system by default. By general consensus, writing data without flushing the operating system buffer is not considered durable. Every so often a new database will show up on Hacker News claiming to beat all other databases on insert speed until a commenter points out the new database doesn't actually flush data to disk.

In other words, the commonly accepted requirement for durability is that not only do you write data to a file on disk but you fsync(2) the file you wrote. This forces the operating system to flush to disk any data it has buffered.

f = open("kv.db")
db = btree.init_from_disk(f)

def handle_write(req):
  db.update(req.key, req.value)
  db.write_to_disk(f)
  f.fsync() # Force a flush
  return 200, {}

def handle_read(req):
  value = db.read(req.key)
  return 200, {"value": value}

Furthermore you must not ignore fsync failure. How you deal with fsync failure is up to you, but exiting immediately with a message that the user should restore from a backup is sometimes considered acceptable.

Databases don't like to fsync because it's slow. Many major databases offer modes where they do not fsync data files before returning a success to a client. Postgres offers this unsafe mode, though does not default to it and warns against it. MongoDB offers this unsafe mode but does not default to it.

An earlier version of this post said that MongoDB would unsafely flush on an interval. Daniel Gomez Ferro from MongoDB messaged me that while the docs are confusing, the default write concern "majority" does actually imply "j: true" which means data is synchronized (i.e. fsync-ed) before returning a success to a client.

Almost every database trades safety for performance in some regard. For example, few databases but SQLite and Cockroach default to Serializable Isolation. While it is commonly agreed that basically no level below Serializable Isolation (that all other databases default to) can be reasoned about. Other databases offer Serializable Isolation, they just don't default to it. Because it can be slow.

Group commit

But let's get back to fsync. One way to amortize the cost of fsync is to delay requests so that you write data from each of them and then fsync the data from all requests. This is sometimes called group commit.

For example, we could update the database in-memory but have a background thread serialize to disk and call fsync only every 5ms.

f = open("kv.db")
db = btree.init_from_disk(f)

group_commit_sems = []

@background_worker()
def group_commit():
  for:
    if clock() % 5ms == 0:
      db.write_to_disk(f)
      f.fsync() # Durably flush for the group
      for sem in group_commit_sems:
        sem.signal()

def handle_write(req):
  db.update(req.key, req.value)
  sem = semaphore()
  group_commit_sems.push(sem)
  sem.wait()
  return 200, {}

def handle_read(req):
  value = db.read(req.key)
  return 200, {"value": value}

It is critical that handle_write waits to return a success until the write is durable via fsync.

So to reiterate, the key idea for durability of a client request is that you have some version of the client message stored on disk durably with fsync before returning a success to a client.

From now on in this post, when you see "durable" or "durability", it means that the data has been written and fsync-ed to disk.

Optimizing durable writes

A key insight is that it's silly to serialize the entire permanent structure of the database to disk every time a user writes.

We could just write the user's message itself to an append-only log. And then only periodically write the entire btree to disk. So long as we have fsync-ed the append-only log file, we can safely return to the user even if the btree itself has not yet been written to disk.

The additional logic this requires is that on startup we must read the btree from disk and then replay the log on top of the btree.

f = open("kv.db", "rw")
db = btree.init_from_disk(f)

log_f = open("kv.log", "rw")
l = log.init_from_disk()
for log in l.read_logs_from(db.last_log_index):
  db.update(log.key, log.value)

group_commit_sems = []

@background_worker()
def group_commit():
  for:
    log_accumulator = log_page()
    if clock() % 5ms == 0:
      for (log, _) in group_commit_sems:
        log_accumulator.add(log)

      log_f.write(log_accumulator.page()) # Write out all log entries at once
      log_f.fsync() # Durably flush wal data
      for (_, sem) in group_commit_sems:
        sem.signal()

    if clock() % 1m == 0:
      db.write_to_disk(f)
      f.fsync() # Durably flush db data

def handle_write(req):
  db.update(req.key, req.value)
  sem = semaphore()
  log = req
  group_commit_sems.push((log, sem))
  sem.wait() # This time waiting for only the log to be written and flushed, not the btree.
  return 200, {}

def handle_read(req):
  value = db.read(req.key)
  return 200, {"value": value}

This is a write-ahead log!

Consider a few scenarios. One request writes the smallest key ever seen. And one request within the same millisecond writes the largest key ever seen. Writing these to disk on the btree means modifying at least two pages spread out in space on disk.

But if we only have to durably write these two messages to a log, they can likely both be included in the same log page. ("Likely" so long as key and values are small enough that multiple can fit into the same page.)

That is, it's cheaper to write only these small messages representing the client request to disk. And we save the structured btree persistence for a less frequent durable write.

Filesystem and disk bugs

Sometimes filesystems will write data to the wrong place. Sometimes disks corrupt data. A solution to both of these is to checksum the data on write, store the checksum on disk, and confirm the checksum on read. This combined with a background process called scrubbing to validate unread data can help you learn quickly when your data has been corrupted and you must recover from backup.

MongoDB's default storage engine WiredTiger does checksum data by default.

But some databases famous for integrity do not. Postgres does no data checksumming by default:

By default, data pages are not protected by checksums, but this can optionally be enabled for a cluster. When enabled, each data page includes a checksum that is updated when the page is written and verified each time the page is read. Only data pages are protected by checksums; internal data structures and temporary files are not.

SQLite likewise does no checksumming by default. Checksumming is an optional extension:

The checksum VFS extension is a VFS shim that adds an 8-byte checksum to the end of every page in an SQLite database. The checksum is added as each page is written and verified as each page is read. The checksum is intended to help detect database corruption caused by random bit-flips in the mass storage device.

But even this isn't perfect. Disks and nodes can fail completely. At that point you can only improve durability by introducing redundancy across disks (and/or nodes), for example, via distributed consensus.

Other reasons you need a WAL?

Some databases (like SQLite) require a write-ahead log to implement aspects of ACID transactions. But this need not be a requirement for ACID transactions if you do MVCC (SQLite does not). See my previous post on implementing MVCC for details.

Logical replication (also called change data capture (CDC)) is another interesting feature that requires a write-ahead log. The idea is that the log already preserves the exact order and changes that affect the database's "state machine". So we could copy these changes out of the system by tracking the write-ahead log, preserving change order, and apply these changes to a foreign system.

But again, just CDC is not about durability. It's an ancillary feature that write-ahead logs make simple.

Conclusion

A few key points. One, durability primarily matters if it is established before returning a success to the client. Second, a write-ahead log is a cheap way to get durability.

And finally, durability is a spectrum. You need to read the docs for your database to understand what it does and does not.

Here's a new post about durability and write-ahead logs. Write-ahead logs are used almost everywhere. But to build an intuition for why, it is helpful to imagine what you would do without a WAL. And to explore the meaning of durability.https://t.co/nzS2pMz22z pic.twitter.com/m1n9x8CNcp

— Phil Eaton (@eatonphil) July 1, 2024

2024-06-17 08:00:00

This is an external post of mine. Click here if you are not redirected.

2024-06-14 08:00:00

Some of the most interesting technical blog posts I read come from, and a common reason for posts I write is, confusion. You're at work and you start asking questions that are difficult to answer. You spend a few hours or a day trying to get to the bottom of things.

If you ask a question to very experienced and successful developers at work, they have a tendency not to give context and to simplify things down to a single answer. This may be a good way to make business decisions. (One can't afford to waste an eternity considering everything indefinitely.) But accepting an answer you don't understand is actively harmful for building intuition.

Certainly, sometimes not accepting an answer can be irritating. You'll have to figure that out.

But beyond "go along to get along", another reason we don't pursue what we're confused about is because we're embarrassed that we're confused in the first place. What's worse, the embarrassment we feel naturally grows the more experienced we get. "I've got this job title, I don't want to seem like I don't know what you mean."

But if you fight the embarrassment and pursue your confusion regardless, you'll likely figure something very interesting out. Moreover, you will probably not have been the only person who was confused. At least personally it is quite rare that I am confused about something and no one else is.

So pay attention when you get confused, and consider why it happened. What did you expect to be the case, and how did reality differ? Explore the angles and the options. When you finally understand, think about what led you to that understanding.

Write it down. Put it into an internal Markdown doc, an internal Atlassian doc, an internal Google Slides page, whatever. The medium doesn't matter.

This entire process doesn't come easily. We feel embarrassed. We aren't used to lingering on something we're confused by. We aren't used to writing things down.

But if you can make yourself pause every once in a while and think about what you (or someone around you) got confused by, and if you can force yourself to stop getting embarrassed by what you got confused by, and if you can write down the background and the reasoning that led to your ultimate understanding, you're going to have something pretty interesting to talk about.

You'll contribute to the growth and intuition of your colleagues. And you'll never run out of things to write about.

Confusion is embarrassing. But fight that feeling, and dig into why you're confused. And write it down.

You won't be the only one who was confused. And you'll tend to have something pretty interesting to talk about.https://t.co/IdX1nGBheR pic.twitter.com/KzTjqMxw6u

— Phil Eaton (@eatonphil) June 14, 2024

2024-05-30 08:00:00

I've been running software book clubs almost continuously since last summer, about 12 months ago. We read through Designing Data-Intensive Applications, Database Internals, Systems Performance, and we just started Understanding Software Dynamics.

The DDIA discussions were in-person in NYC with about 5-8 consistent attendees. The rest have been over email with 300, 500, and 600 attendees.

This post is for folks who are interested in running their own book club. None of these ideas are novel. I co-opted the best parts I saw from other people running similar things. And hopefully you'll improve on my experience too, should you try.

Despite the length of this post running a book club takes almost no noticeable effort, other than when I need to select and confirm discussion leaders. It is the limited-effort-required to thank that I've kept up the book clubs so consistently.

Google Groups

I run the virtual book clubs over email. I create a Google Group and tell people to send me their email for an invite. I use a Google Form to collect emails since I get many. If you're doing a small group book club you can just collect member emails directly.

In the Google Form I ask people to volunteer to lead discussion for a chapter (or chapters). And I ask for a Twitter/GitHub/LinkedIn account.

When I've gotten enough responses I go through the list and check Twitter/GitHub/LinkedIn info to find people who might have a particularly interesting perspective to lead a discussion.

"Lead a discussion" sounds formal but I mean anything but. All I am looking for is someone to start a new Google Group thread each week and for them to share their thoughts.

For example a discussion leader might share:

• What they liked about the chapter
• Something new they learned from the chapter
• A story about their work that the chapter reminded them of
• A little project they hacked on, inspired by reading the chapter
• A paper or YouTube video this chapter reminded them of
• Something from the chapter that was confusing
• Etc.

The "discussion leader" has no responsibility for remaining in the discussion after posting the thread. There just isn't an easy way to say "person who kicks off discussion" than to call them a "discussion leader".

By the way, I didn't do discussion leaders for the first book club, reading DDIA. And that book club took noticeably more effort. Because I organized it, I was effectively the discussion leader every time. Having discussion leaders disperses the effort of the book club. And I think it makes the club much more interesting.

SparkNotes-ification

One thing I noticed happening often was that the discussion leader might do a large summary of the chapter. I greatly appreciate and respect that effort, but I think this is not the ideal thing to happen. Of course you can't control what people do and maybe they really wanted to write a summary. But since noticing this happen I now try to discourage the discussion leader from summarizing since 1) it must be quite time-consuming and 2) it isn't as interesting as some of the above bullet points.

Confirming with leaders

When I have picked out folks who seem like they'd be fun discussion leaders, I bcc email them all asking them to confirm. At the same time I explain what being a discussion leader means. As I just explained it here above.

Each week's discussion gets a new Google Group thread. Discussion happens in responses to the thread.

I ask the discussion leaders to create the new discussion thread between Friday and Saturday their local time.

For folks who don't confirm, I email them one last time and then if they still haven't confirmed I find someone new.

I always lead the first week's discussion so that the discussion leaders can see what I do and so that I can establish the pattern.

Managing leaders

It takes a while to read a book. Sometimes the leaders forget to do their part. If it gets to be Sunday and the discussion leader for the week hasn't started discussion, I email them to gently ask if they are still available to kick off discussion. And if they are not, no worries, I can step in.

I have had to step in a few times to start discussion and it's no problem.

Managing non-leaders

Just as you need to clarify and set expectations for discussion leaders, you need to clarify and set expectations for everyone else.

When I invite people to the Google Group I typically also create an Intro thread where I explain the discussion format.

An annoying aspect of Google Groups is that I cannot limit who can create a thread without limiting who can respond to a thread.

It would simplify things for me if I could limit thread creation to discussion leaders. But since I cannot, I try to repeatedly and explicitly mention in the Intro thread that no one should start a new discussion thread unless they are a discussion leader. And that new threads will come out each weekend to discuss the previous chapter.

Setting the tone

One of the most important things to do in the Intro email is to set the tone. I try to clarify this is a friendly and encouraging group focused on learning and improving ourselves. We have experts in the group and we have noobs in the group and they are all welcome and will all come away with different things.

Why email?

Email seems to be the most time-friendly and demographic-friendly medium. Doing live discussion sounds stressful and difficult to schedule, although I believe Alex Petrov runs live discussions. Email forces you to slow down and think things through. And email is built around an inbox. If you didn't get to read some discussion, you can mark it unread. You can't do that in Discord or Slack.

Avoiding long-term commitments

When I pick a book, aside from picking books I think are likely to be exceptionally well-written, I try to avoid books that we could not finish within 3 months. It concerns me to try to get people to commit to something longer than that.

This has led to some distortion though. Systems Performance has only 16 chapters. One chapter a week means about 3 months in total. But each chapter is 100 pages long.

I was hesitant to do a reading of Understanding Software Dynamics because it has 28 chapters. But each chapter is only 10-15 pages long. So when I decided to go with it, I decided we'd read 2 chapters a week. Each discussion leader is responsible for 2 chapters at a time. That means we can finish within 3 months. And each week we read only 20-30 pages, which is still much more doable than 100 pages of Systems Performance.

On the other hand, we did make it through Systems Performance! Which gives me confidence to pick other books that are physically daunting, should they otherwise seem like a good idea.

A book ends

Many public book clubs go through a book a month and have no ending. That is totally fair. But what I love about the way I organize book clubs is that each reading is unrelated to the next. It's an entirely new signup for each book. You need only "commit" (I mean, you can drop off whenever and definitely people do) to a 3-month reading and then you can justly feel good about yourself and join again in the future or not.

In contrast a paper reading club has no obvious ending, unless you pick all the papers in advance and organize them around a school year or something. This has made running a paper reading club feel more concerning to me. Though I greatly appreciate folks like Aleksey Charapko and Murat Demirbas who do.

Most people don't actively contribute, but they still value it

In a group of 500 people, maybe 1-2% of those people actively contribute to discussion. 5-10 people. But I often hear from people who didn't participate that they still highly valued the group. And this high percentage of non-active-participants is part of why I keep allowing the group size to grow. There's little work I have to do and a bunch of people benefit.

Doing it at your company likely won't go well

I wrote about this before. For some reason it's hard to get people who would otherwise join an external reading club to join a company-internal reading club.

Though perhaps I'm just doing it wrong because I hear of others like Elizabeth Garrett Christensen who run an internal software book club successfully.

Good luck, have fun!

That's all I've got. Send me questions if you've got any. But mostly, just give it a shot if you want to and you'll learn!

And if you still don't get it, you can of course just join one of my book clubs. :)

Since folks have asked, here's how I run a software book club.

But also, you could just join and see. :)https://t.co/tXBrLFYbvC pic.twitter.com/4iW8EfZCeY

— Phil Eaton (@eatonphil) May 30, 2024

2024-05-16 08:00:00

In this post we'll build a database in 400 lines of code with basic support for five standard SQL transaction levels: Read Uncommitted, Read Committed, Repeatable Read, Snapshot Isolation and Serializable. We'll use multi-version concurrency control (MVCC) and optimistic concurrency control (OCC) to accomplish this. The goal isn't to be perfect but to explain the basics in a minimal way.

You don't need to know what these terms mean in advance. I did not understand them before doing this project. But if you've ever dealt with SQL databases, transaction isolation levels are likely one of the dark corners you either 1) weren't aware of or 2) wanted not to think about. At least, this is how I felt.

While there are many blog posts that list out isolation levels, I haven't been able to internalize their lessons. So I built this little database to demonstrate the common isolation levels for myself. It turned out to be simpler than I expected, and made the isolation levels much easier to reason about.

Thank you to Justin Jaffray, Alex Miller, Sujay Jayakar, Peter Veentjer, and Michael Gasch for providing feedback and suggestions.

All code is available on GitHub.

Why do we need transaction isolation?

If you already know the answer, feel free to skip this section.

When I first started working with databases in CRUD applications, I did not understand the point of transactions. I was fairly certain that transactions are locks. I was wrong about that, but more on that later.

I can't remember exact code I wrote, but here's something I could have written:

with database.transaction() as t:
  users = t.query("SELECT * FROM users WHERE group = 'admin';")
  ids = []
  for user in users:
    if some_complex_logic(user):
      ids.push(user.id)

  t.query("UPDATE users SET metadata = 'some value' WHERE id IN ($1)';", ids)

I would have thought that all users that were seen from the initial SELECT who matched the some_complex_logic filter would be exactly the same that are updated in my second SQL statement.

And if I were using SQLite, my guess would have been correct. But if I were using MySQL or Postgres or Oracle or SQL Server, and hadn't made any changes to defaults, that wouldn't necessarily be true! We'll discover exactly why throughout this post.

For example, some other connection and transaction could have set a user's group to admin after the initial SELECT was executed. It would then be missed from the some_complex_logic check and from the subsequent UPDATE.

Or, again after our initial SELECT, some other connection could have modified the group for some user that previously was admin. It would then be incorrectly part of the second UPDATE statement.

These are just a few examples of what could go wrong.

This is the realm of transaction isolation. How do multiple transactions running at the same time, interacting with the same data, interact with each other?

The answer is: it depends. The SQL standard itself loosely prescribes four isolation levels. But every database implements these four levels slightly differently. Sometimes using entirely different algorithms. And even among the standard levels, the default isolation level for each database differs.

Funky bugs that can show up across databases and across isolation levels, often dependent on particular details of common ways of implementing isolation levels, create what are called "anomalies". Examples include intimidating terms like "dirty reads" and "write cycles" and G2-Item.

The topic is so complex that we've got decades of research papers critiquing SQL isolation levels, categorization of common isolation anomalies, walkthroughs of anomalies by Martin Kleppmann in Designing Data-Intensive Applications, Martin Kleppman's Hermitage project documenting common anomalies across isolation levels in major databases, and the ACIDRain paper showing isolation-related bugs in major open-source ecommerce projects.

These aren't just random links. They're each quite interesting. And particularly for practitioners who don't know why they should care, check out Designing Data-Intensive Applications and the last link on ACIDRain.

And this is only a small list of some of the most interesting research and writing on the topic.

So there's a wide variety of things to consider:

• Not every database implements transaction isolation levels identically, resulting in different behavior
• Not all researchers agree, and not all database developers agree, on what any given isolation level means
• Not every database has the same default isolation level, and most developers tend not to change the default
• Not every developer is correctly using the isolation level they pick (default or not)

Transaction isolation levels are basically vibes. The only truth for real projects is Martin Kleppmann's Hermitage project that catalogs behavior across databases. And a truth some people align with is Generalized Isolation Level Definitions.

So while all these linked works above are authoritative, and even though we can see that there might be some anomalies we have to worry about, the research can still be difficult to internalize. And many developers, my recent self included, do not have a great understanding of isolation levels.

Throughout this post we'll stick to informal definitions of isolation levels to keep things simple.

Let's dig in.

Locks? MVCC?

Historically, databases implemented isolation with locking algorithms such as Two-Phase Locking (not the same thing as Two-Phase Commit). Multi-version concurrency control (MVCC) is an approach that lets us completely avoid locks.

It's worthwhile to note that while we will validly not use locks (implementing what is called optimistic concurrency control or OCC), most MVCC databases do still use locks for certain things (implementing what is called pessimistic concurrency control).

But this is the story of databases in general. There are numerous ways to implement things.

We will take the simpler lockless route.

Consider a key-value database. With MVCC, rather than storing only the value for a key, we would store versions of the value. The version includes the transaction id (a monotonic incrementing integer) wherein the version was created, and the transaction id wherein the version was deleted.

With MVCC, it is possible to express transaction isolation levels almost solely as a set of different visibility rules for a version of a value; rules that vary by isolation level.

So we will build up a general framework first and discuss and implement each isolation level last.

Scaffolding

We'll build an in-memory key-value system that acts on transactions. I usually try to stick with only the standard library for projects like this but I really wanted a sorted data structure and Go doesn't implement one.

In main.go, let's set up basic helpers for assertions and debugging:

package main

import (
        "fmt"
        "os"
        "slices"

        "github.com/tidwall/btree"
)

func assert(b bool, msg string) {
        if !b {
                panic(msg)
        }
}

func assertEq[C comparable](a C, b C, prefix string) {
        if a != b {
                panic(fmt.Sprintf("%s '%v' != '%v'", prefix, a, b))
        }
}

var DEBUG = slices.Contains(os.Args, "--debug")

func debug(a ...any) {
        if !DEBUG {
                return
        }

        args := append([]any{"[DEBUG]"}, a...)
        fmt.Println(args...)
}

As mentioned previously, a value in the database will be defined with start and end transaction ids.

type Value struct {
        txStartId uint64
        txEndId   uint64
        value     string
}

Every transaction will be in an in-progress, aborted, or committed state.

type TransactionState uint8
const (
        InProgressTransaction TransactionState = iota
        AbortedTransaction
        CommittedTransaction
)

And we'll support a few major isolation levels.

// Loosest isolation at the top, strictest isolation at the bottom.
type IsolationLevel uint8
const (
        ReadUncommittedIsolation IsolationLevel = iota
        ReadCommittedIsolation
        RepeatableReadIsolation
        SnapshotIsolation
        SerializableIsolation
)

We'll get into detail about the meaning of the levels later.

A transaction has an isolation level, an id (monotonic increasing integer), and a current state. And although we won't make use of this data yet, transactions at stricter isolation levels will need some extra info. Specifically, stricter isolation levels need to know about other transactions that were in-progress when this one started. And stricter isolation levels need to know about all keys read and written by a transaction.

type Transaction struct {
        isolation  IsolationLevel
        id         uint64
        state      TransactionState

        // Used only by Repeatable Read and stricter.
        inprogress btree.Set[uint64]

        // Used only by Snapshot Isolation and stricter.
        writeset   btree.Set[string]
        readset    btree.Set[string]
}

We'll discuss why later.

Finally, the database itself will have a default isolation level that each transaction will inherit (for our own convenience in tests).

The database will have a mapping of keys to an array of value versions. Later elements in the array will represent newer versions of a value.

The database will also store the next free transaction id it will use to assign ids to new transactions.

type Database struct {
        defaultIsolation  IsolationLevel
        store             map[string][]Value
        transactions      btree.Map[uint64, Transaction]
        nextTransactionId uint64
}

func newDatabase() Database {
        return Database{
                defaultIsolation:  ReadCommittedIsolation,
                store:             map[string][]Value{},
                // The `0` transaction id will be used to mean that
                // the id was not set. So all valid transaction ids
                // must start at 1.
                nextTransactionId: 1,
        }
}

To be thread-safe: store, transactions, and nextTransactionId should be guarded by a mutex. But to keep the code small, this post will not use goroutines and thus does not need mutexes.

There's a bit of book-keeping when creating a transaction, so we'll make a dedicated method for this. We must give the new transaction an id, store all in-progress transactions, and add it to database transaction history.

func (d *Database) inprogress() btree.Set[uint64] {
        var ids btree.Set[uint64]
        iter := d.transactions.Iter()
        for ok := iter.First(); ok; ok = iter.Next() {
                if iter.Value().state == InProgressTransaction {
                        ids.Insert(iter.Key())
                }
        }
        return ids
}

func (d *Database) newTransaction() *Transaction {
        t := Transaction{}
        t.isolation = d.defaultIsolation
        t.state = InProgressTransaction

        // Assign and increment transaction id.
        t.id = d.nextTransactionId
        d.nextTransactionId++

        // Store all inprogress transaction ids.
        t.inprogress = d.inprogress()

        // Add this transaction to history.
        d.transactions.Set(t.id, t)

        debug("starting transaction", t.id)

        return &t
}

And we'll add a few more helpers for completing a transaction, for fetching a transaction by id, and for validating a transaction.

func (d *Database) completeTransaction(t *Transaction, state TransactionState) error {
        debug("completing transaction ", t.id)

        // Update transactions.
        t.state = state
        d.transactions.Set(t.id, *t)

        return nil
}

func (d *Database) transactionState(txId uint64) Transaction {
        t, ok := d.transactions.Get(txId)
        assert(ok, "valid transaction")
        return t
}

func (d *Database) assertValidTransaction(t *Transaction) {
        assert(t.id > 0, "valid id")
        assert(d.transactionState(t.id).state == InProgressTransaction, "in progress")
}

The final bit of scaffolding we'll set up is an abstraction for database connections. A connection will have at most associated one transaction. Users must ask the database for a new connection. Then within the connection they can manage a transaction.

type Connection struct {
        tx *Transaction
        db *Database
}

func (c *Connection) execCommand(command string, args []string) (string, error) {
        debug(command, args)

        // TODO
        return "", fmt.Errorf("unimplemented")
}

func (c *Connection) mustExecCommand(cmd string, args []string) string {
        res, err := c.execCommand(cmd, args)
        assertEq(err, nil, "unexpected error")
        return res
}

func (d *Database) newConnection() *Connection {
        return &Connection{
                db: d,
                tx: nil,
        }
}

func main() {
        panic("unimplemented")
}

And that's it for scaffolding. Now set up the go module and make sure this builds.

$ go mod init gomvcc
go: creating new go.mod: module gomvcc
go: to add module requirements and sums:
        go mod tidy
$ go mod tidy
go: finding module for package github.com/tidwall/btree
go: found github.com/tidwall/btree in github.com/tidwall/btree v1.7.0
$ go build
$ ./gomvcc
panic: unimplemented

goroutine 1 [running]:
main.main()
        /Users/phil/tmp/main.go:166 +0x2c

Great!

Transaction management

When the user asks to begin a transaction, we ask the database for a new transaction and assign it to the current connection.

 func (c *Connection) execCommand(command string, args []string) (string, error) {
         debug(command, args)

+       if command == "begin" {
+               assertEq(c.tx, nil, "no running transactions")
+               c.tx = c.db.newTransaction()
+               c.db.assertValidTransaction(c.tx)
+               return fmt.Sprintf("%d", c.tx.id), nil
+       }
+
         // TODO
         return "", fmt.Errorf("unimplemented")
 }

To abort a transaction, we call the completeTransaction method (which makes sure the database transaction history gets updated) with the AbortedTransaction state.

                return fmt.Sprintf("%d", c.tx.id), nil
        }

+       if command == "abort" {
+               c.db.assertValidTransaction(c.tx)
+               err := c.db.completeTransaction(c.tx, AbortedTransaction)
+               c.tx = nil
+               return "", err
+       }
+
         // TODO
         return "", fmt.Errorf("unimplemented")
 }

And to commit a transaction is similar.

                return "", err
        }

+       if command == "commit" {
+               c.db.assertValidTransaction(c.tx)
+               err := c.db.completeTransaction(c.tx, CommittedTransaction)
+               c.tx = nil
+               return "", err
+       }
+
         // TODO
         return "", fmt.Errorf("unimplemented")
 }

The neat thing about MVCC is that beginning, committing, and aborting a transaction is metadata work. Committing a transaction will get a bit more complex when we add support for Snapshot Isolation and Serializable Isolation, but we'll get to that later. Even then, it will not involve modifying any values we get, set, or delete.

Get, set, delete

Here is where things get fun. As mentioned earlier, the key-value store is actually map[string][]Value. With the more recent versions of a value at the end of the list of values for the key.

For get support, we'll iterate the list of value versions backwards for the key. And we'll call a special new isvisible method to determine if this transaction can see this value. The first value that passes the isvisible test is the correct value for the transaction.

                return "", err
        }

+       if command == "get" {
+               c.db.assertValidTransaction(c.tx)
+
+               key := args[0]
+
+               c.tx.readset.Insert(key)
+
+               for i := len(c.db.store[key]) - 1; i >= 0; i-- {
+                       value := c.db.store[key][i]
+                       debug(value, c.tx, c.db.isvisible(c.tx, value))
+                       if c.db.isvisible(c.tx, value) {
+                               return value.value, nil
+                       }
+               }
+
+               return "", fmt.Errorf("cannot get key that does not exist")
+       }
+
         // TODO
         return "", fmt.Errorf("unimplemented")
 }

I snuck in tracking which keys are read, and we'll also soon sneak in tracking which keys are written. This is necessary in stricter isolation levels. More on that later.

set and delete are similar to get. But this time when we walk the list of value versions, we will set the txEndId for the value to the current transaction id if the value version is visible to this transaction.

Then, for set, we'll append to the value version list with the new version of the value that starts at this current transaction.

                return "", err
        }

+       if command == "set" || command == "delete" {
+               c.db.assertValidTransaction(c.tx)
+
+               key := args[0]
+
+               // Mark all visible versions as now invalid.
+               found := false
+               for i := len(c.db.store[key]) - 1; i >= 0; i-- {
+                       value := &c.db.store[key][i]
+                       debug(value, c.tx, c.db.isvisible(c.tx, *value))
+                       if c.db.isvisible(c.tx, *value) {
+                               value.txEndId = c.tx.id
+                               found = true
+                       }
+               }
+               if command == "delete" && !found {
+                       return "", fmt.Errorf("cannot delete key that does not exist")
+               }
+
+               c.tx.writeset.Insert(key)
+
+               // And add a new version if it's a set command.
+               if command == "set" {
+                       value := args[1]
+                       c.db.store[key] = append(c.db.store[key], Value{
+                               txStartId: c.tx.id,
+                               txEndId:   0,
+                               value:     value,
+                       })
+
+                       return value, nil
+               }
+
+               // Delete ok.
+               return "", nil
+       }
+
        if command == "get" {
                c.db.assertValidTransaction(c.tx)

This time rather than modifying the readset we modify the writeset for the transaction.

And that is how commands get executed!

Let's zoom in to the core of the problem we have mentioned but not implemented: MVCC visibility rules and how they differ by isolation levels.

Isolation levels and MVCC visibility rules

To varying degrees, transaction isolation levels prevent concurrent transactions from messing with each other. The looser isolation levels prevent this almost not at all.

Here is what the 1999 ANSI SQL standard (page 84) has to say.

But as I mentioned in the beginning of the post, we're going to be a bit informal. And we'll mostly refer to Jepsen summaries of each isolation levels.

Read Uncommitted

According to Jepsen, the loosest isolation level, Read Uncommitted, has almost no restrictions. We can merely read the most recent (non-deleted) version of a value, regardless of if the transaction that set it has committed or aborted or not.

func (d *Database) isvisible(t *Transaction, value Value) bool {
        // Read Uncommitted means we simply read the last value
        // written. Even if the transaction that wrote this value has
        // not committed, and even if it has aborted.
        if t.isolation == ReadUncommittedIsolation {
                // We must merely make sure the value has not been
                // deleted.
                return value.txEndId == 0
        }

       assert(false, "unsupported isolation level")
       return false
}

Let's write a test that demonstrates this. We create two transactions, c1 and c2, and set a key in c1. The value set for the key in c1 should be immediately visible if c2 asks for that key. In main_test.go:

package main

import (
        "testing"
)

func TestReadUncommitted(t *testing.T) {
        database := newDatabase()
        database.defaultIsolation = ReadUncommittedIsolation

        c1 := database.newConnection()
        c1.mustExecCommand("begin", nil)

        c2 := database.newConnection()
        c2.mustExecCommand("begin", nil)

        c1.mustExecCommand("set", []string{"x", "hey"})

        // Update is visible to self.
        res := c1.mustExecCommand("get", []string{"x"})
        assertEq(res, "hey", "c1 get x")

        // But since read uncommitted, also available to everyone else.
        res = c2.mustExecCommand("get", []string{"x"})
        assertEq(res, "hey", "c2 get x")

        // And if we delete, that should be respected.
        res = c1.mustExecCommand("delete", []string{"x"})
        assertEq(res, "", "c1 delete x")

        res, err := c1.execCommand("get", []string{"x"})
        assertEq(res, "", "c1 sees no x")
        assertEq(err.Error(), "cannot get key that does not exist", "c1 sees no x")

        res, err = c2.execCommand("get", []string{"x"})
        assertEq(res, "", "c2 sees no x")
        assertEq(err.Error(), "cannot get key that does not exist", "c2 sees no x")
}

Thank you to @glaebhoerl for pointing out that in an earlier version of this post, Read Uncommitted incorrectly made deleted values visible.

That's pretty simple! But also pretty useless if your workload has conflicts. If you can arrange your workload in a way where you know no concurrent transactions will ever read or write conflicting keys though, this could be pretty efficient! The rules will only get more complex (and thus potentially more of a bottleneck) from here on.

But for the most part, people don't use this isolation level. SQLite, Yugabyte, Cockroach, and Postgres don't even implement it. It is also not the default for any major database that does implement it.

Let's get a little stricter.

Read Committed

We'll pull again from Jepsen:

Read committed is a consistency model which strengthens read uncommitted by preventing dirty reads: transactions are not allowed to observe writes from transactions which do not commit.

This sounds pretty simple. In isvisible we'll make sure that the value has a txStartId that is either this transaction or a transaction that has committed. Moreover we will now begin checking against txEndId to make sure the value wasn't deleted by any relevant transaction.

                return value.txEndId == 0
        }

+       // Read Committed means we are allowed to read any values that
+       // are committed at the point in time where we read.
+       if t.isolation == ReadCommittedIsolation {
+               // If the value was created by a transaction that is
+               // not committed, and not this current transaction,
+               // it's no good.
+               if value.txStartId != t.id &&
+                       d.transactionState(value.txStartId).state != CommittedTransaction {
+                       return false
+               }
+
+               // If the value was deleted in this transaction, it's no good.
+               if value.txEndId == t.id {
+                       return false
+               }
+
+               // Or if the value was deleted in some other committed
+               // transaction, it's no good.
+               if value.txEndId > 0 &&
+                       d.transactionState(value.txEndId).state == CommittedTransaction {
+                       return false
+               }
+
+               // Otherwise the value is good.
+               return true
+       }
+
        assert(false, "unsupported isolation level")
        return false
 }

This begins to look useful! We will never read a value that isn't part of a committed transaction (or isn't part of our own transaction). Indeed this is the default isolation level for many databases including Postgres, Yugabyte, Oracle, and SQL Server.

Let's add a test to main_test.go. This is a bit long, but give it a slow read. It is thoroughly commented.

func TestReadCommitted(t *testing.T) {
        database := newDatabase()
        database.defaultIsolation = ReadCommittedIsolation

        c1 := database.newConnection()
        c1.mustExecCommand("begin", nil)

        c2 := database.newConnection()
        c2.mustExecCommand("begin", nil)

        // Local change is visible locally.
        c1.mustExecCommand("set", []string{"x", "hey"})

        res := c1.mustExecCommand("get", []string{"x"})
        assertEq(res, "hey", "c1 get x")

        // Update not available to this transaction since this is not
        // committed.
        res, err := c2.execCommand("get", []string{"x"})
        assertEq(res, "", "c2 get x")
        assertEq(err.Error(), "cannot get key that does not exist", "c2 get x")

        c1.mustExecCommand("commit", nil)

        // Now that it's been committed, it's visible in c2.
        res = c2.mustExecCommand("get", []string{"x"})
        assertEq(res, "hey", "c2 get x")

        c3 := database.newConnection()
        c3.mustExecCommand("begin", nil)

        // Local change is visible locally.
        c3.mustExecCommand("set", []string{"x", "yall"})

        res = c3.mustExecCommand("get", []string{"x"})
        assertEq(res, "yall", "c3 get x")

        // But not on the other commit, again.
        res = c2.mustExecCommand("get", []string{"x"})
        assertEq(res, "hey", "c2 get x")

        c3.mustExecCommand("abort", nil)

        // And still not, if the other transaction aborted.
        res = c2.mustExecCommand("get", []string{"x"})
        assertEq(res, "hey", "c2 get x")

        // And if we delete it, it should show up deleted locally.
        c2.mustExecCommand("delete", []string{"x"})

        res, err = c2.execCommand("get", []string{"x"})
        assertEq(res, "", "c2 get x")
        assertEq(err.Error(), "cannot get key that does not exist", "c2 get x")

        c2.mustExecCommand("commit", nil)

        // It should also show up as deleted in new transactions now
        // that it has been committed.
        c4 := database.newConnection()
        c4.mustExecCommand("begin", nil)

        res, err = c4.execCommand("get", []string{"x"})
        assertEq(res, "", "c4 get x")
        assertEq(err.Error(), "cannot get key that does not exist", "c4 get x")
}

Again this seems great. However! You can easily get inconsistent data within a transaction at this isolation level. If the transaction A has multiple statements it can see different results per statement, even if the transaction A did not modify data. Another transaction B may have committed changes between two statements in this transaction A.

Let's get a little stricter.

Repeatable Read

Again as Jepsen says, Repeatable Read is the same as Read Committed but with the following anomaly not allowed (quoting from the ANSI SQL 1999 standard):

P2 (“Non-repeatable read”): SQL-transaction T1 reads a row. SQL-transaction T2 then modifies or deletes that row and performs a COMMIT. If T1 then attempts to reread the row, it may receive the modified value or discover that the row has been deleted.

To support this, we will add additional checks for the Read Committed logic that make sure the value was not created and not deleted within a transaction that started before this transaction started.

As it happens, this is the same logic that will be necessary for Snapshot Isolation and Serializable Isolation. The additional logic (that makes Snapshot Isolation and Serializable Isolation different) happens at commit time.

                return true
        }

-       assert(false, "unsupported isolation level")
-       return false
+       // Repeatable Read, Snapshot Isolation, and Serializable
+       // further restricts Read Committed so only versions from
+       // transactions that completed before this one started are
+       // visible.
+
+       // Snapshot Isolation and Serializable will do additional
+       // checks at commit time.
+       assert(t.isolation == RepeatableReadIsolation ||
+               t.isolation == SnapshotIsolation ||
+               t.isolation == SerializableIsolation, "invalid isolation level")
+       // Ignore values from transactions started after this one.
+       if value.txStartId > t.id {
+               return false
+       }
+
+       // Ignore values created from transactions in progress when
+       // this one started.
+       if t.inprogress.Contains(value.txStartId) {
+               return false
+       }
+
+       // If the value was created by a transaction that is not
+       // committed, and not this current transaction, it's no good.
+       if d.transactionState(value.txStartId).state != CommittedTransaction &&
+               value.txStartId != t.id {
+               return false
+       }
+
+       // If the value was deleted in this transaction, it's no good.
+       if value.txEndId == t.id {
+               return false
+       }
+
+       // Or if the value was deleted in some other committed
+       // transaction that started before this one, it's no good.
+       if value.txEndId < t.id &&
+               value.txEndId > 0 &&
+               d.transactionState(value.txEndId).state == CommittedTransaction &&
+               !t.inprogress.Contains(value.txEndId) {
+               return false
+       }
+
+       return true
 }

 type Connection struct {

How do I derive these rules? Mostly by writing tests that should pass or fail and seeing what doesn't make sense. I tried to steal from existing projects but these rules were not so simple to discover. Which is part of what I hope makes this project particularly useful to look at.

Let's write a test for Repeatable Read. Again, the test is long but well commented.

func TestRepeatableRead(t *testing.T) {
        database := newDatabase()
        database.defaultIsolation = RepeatableReadIsolation

        c1 := database.newConnection()
        c1.mustExecCommand("begin", nil)

        c2 := database.newConnection()
        c2.mustExecCommand("begin", nil)

        // Local change is visible locally.
        c1.mustExecCommand("set", []string{"x", "hey"})
        res := c1.mustExecCommand("get", []string{"x"})
        assertEq(res, "hey", "c1 get x")

        // Update not available to this transaction since this is not
        // committed.
        res, err := c2.execCommand("get", []string{"x"})
        assertEq(res, "", "c2 get x")
        assertEq(err.Error(), "cannot get key that does not exist", "c2 get x")

        c1.mustExecCommand("commit", nil)

        // Even after committing, it's not visible in an existing
        // transaction.
        res, err = c2.execCommand("get", []string{"x"})
        assertEq(res, "", "c2 get x")
        assertEq(err.Error(), "cannot get key that does not exist", "c2 get x")

        // But is available in a new transaction.
        c3 := database.newConnection()
        c3.mustExecCommand("begin", nil)

        res = c3.mustExecCommand("get", []string{"x"})
        assertEq(res, "hey", "c3 get x")

        // Local change is visible locally.
        c3.mustExecCommand("set", []string{"x", "yall"})
        res = c3.mustExecCommand("get", []string{"x"})
        assertEq(res, "yall", "c3 get x")

        // But not on the other commit, again.
        res, err = c2.execCommand("get", []string{"x"})
        assertEq(res, "", "c2 get x")
        assertEq(err.Error(), "cannot get key that does not exist", "c2 get x")

        c3.mustExecCommand("abort", nil)

        // And still not, regardless of abort, because it's an older
        // transaction.
        res, err = c2.execCommand("get", []string{"x"})
        assertEq(res, "", "c2 get x")
        assertEq(err.Error(), "cannot get key that does not exist", "c2 get x")

        // And again still the aborted set is still not on a new
        // transaction.
        c4 := database.newConnection()
        res = c4.mustExecCommand("begin", nil)

        res = c4.mustExecCommand("get", []string{"x"})
        assertEq(res, "hey", "c4 get x")

        c4.mustExecCommand("delete", []string{"x"})
        c4.mustExecCommand("commit", nil)

        // But the delete is visible to new transactions now that this
        // has been committed.
        c5 := database.newConnection()
        res = c5.mustExecCommand("begin", nil)

        res, err = c5.execCommand("get", []string{"x"})
        assertEq(res, "", "c5 get x")
        assertEq(err.Error(), "cannot get key that does not exist", "c5 get x")
}

Let's get stricter!

Snapshot Isolation

Back to [Jepsen](https://jepsen.io/consistency/models/snapshot-isolation for a definition:

In a snapshot isolated system, each transaction appears to operate on an independent, consistent snapshot of the database. Its changes are visible only to that transaction until commit time, when all changes become visible atomically to any transaction which begins at a later time. If transaction T1 has modified an object x, and another transaction T2 committed a write to x after T1’s snapshot began, and before T1’s commit, then T1 must abort.

So Snapshot Isolation is the same as Repeatable Read but with one additional rule: the keys written by any two concurrent committed transactions must not overlap.

This is why we tracked writeset. Every time a transaction modified or deleted a key, we added it to the transaction's writeset. To make sure we abort correctly, we'll add a conflict check to the commit step. (This idea is also well documented in A critique of snapshot isolation. This paper can be hard to find. Email me if you want a copy.)

When a transaction A goes to commit, it will run a conflict test for any transaction B that has committed since this transaction A started.

Serializable Isolation is going to have a similar check. So we'll add a helper for iterating through all relevant transactions, running a check function for any transaction that has committed.

func (d *Database) hasConflict(t1 *Transaction, conflictFn func(*Transaction, *Transaction) bool) bool {
        iter := d.transactions.Iter()

        // First see if there is any conflict with transactions that
        // were in progress when this one started.
        inprogressIter := t1.inprogress.Iter()
        for ok := inprogressIter.First(); ok; ok = inprogressIter.Next() {
                id := inprogressIter.Key()
                found := iter.Seek(id)
                if !found {
                        continue
                }
                t2 := iter.Value()
                if t2.state == CommittedTransaction {
                        if conflictFn(t1, &t2) {
                                return true
                        }
                }
        }

        // Then see if there is any conflict with transactions that
        // started and committed after this one started.
        for id := t1.id; id < d.nextTransactionId; id++ {
                found := iter.Seek(id)
                if !found {
                        continue
                }

                t2 := iter.Value()
                if t2.state == CommittedTransaction {
                        if conflictFn(t1, &t2) {
                                return true
                        }
                }
        }

        return false
}

It was around this point that I decided I did really need a B-Tree implementation and could not just stick to vanilla Go data structures.

Now we can modify completeTransaction to do this check if the transaction intends to commit. If the current transaction A's write set intersects with any other transaction B committed since transaction A started, we must abort.

 func (d *Database) completeTransaction(t *Transaction, state TransactionState) error {
         debug("completing transaction ", t.id)

+
+       if state == CommittedTransaction {
+               // Snapshot Isolation imposes the additional constraint that
+               // no transaction A may commit after writing any of the same
+               // keys as transaction B has written and committed during
+               // transaction A's life.
+               if t.isolation == SnapshotIsolation && d.hasConflict(t, func(t1 *Transaction, t2 *Transaction) bool {
+                       return setsShareItem(t1.writeset, t2.writeset)
+               }) {
+                       d.completeTransaction(t, AbortedTransaction)
+                       return fmt.Errorf("write-write conflict")
+               }
+       }
+
         // Update transactions.
         t.state = state
         d.transactions.Set(t.id, *t)

Lastly, the definition of setsShareItem.

func setsShareItem(s1 btree.Set[string], s2 btree.Set[string]) bool {
        s1Iter := s1.Iter()
        s2Iter := s2.Iter()
        for ok := s1Iter.First(); ok; ok = s1Iter.Next() {
                s1Key := s1Iter.Key()
                found := s2Iter.Seek(s1Key)
                if found {
                        return true
                }
        }

        return false
}

Since Snapshot Isolation shares all the same visibility rules as Repeatable Read, the tests get to be a little simpler! We'll simply test that two transactions attempting to commit a write to the same key fail. Or specifically: that the second transaction cannot commit.

func TestSnapshotIsolation_writewrite_conflict(t *testing.T) {
        database := newDatabase()
        database.defaultIsolation = SnapshotIsolation

        c1 := database.newConnection()
        c1.mustExecCommand("begin", nil)

        c2 := database.newConnection()
        c2.mustExecCommand("begin", nil)

        c3 := database.newConnection()
        c3.mustExecCommand("begin", nil)

        c1.mustExecCommand("set", []string{"x", "hey"})
        c1.mustExecCommand("commit", nil)

        c2.mustExecCommand("set", []string{"x", "hey"})

        res, err := c2.execCommand("commit", nil)
        assertEq(res, "", "c2 commit")
        assertEq(err.Error(), "write-write conflict", "c2 commit")

        // But unrelated keys cause no conflict.
        c3.mustExecCommand("set", []string{"y", "no conflict"})
        c3.mustExecCommand("commit", nil)
}

Not bad! But let's get stricter.

Upon further discussion with Alex Miller, and after reviewing A Critique of ANSI SQL Isolation Levels, the difference I am trying to suggest (between Repeatable Read an Snapshot Isolation) likely does not exist. A Critique of ANSI SQL Isolation Levels mentions Repeatable Read must not exhibit P4 (Lost Update) anomalies. And it mentions that you must check for read-write conflicts to avoid these. Therefore it seems likely that you can't easily separate Repeatable Read from Snapshot Isolation when implemented using MVCC. The differences between Repeatable Read and Snapshot Isolation may more readily show up when implementing transactions the classical way with Two-Phase Locking.

To reiterate, with MVCC and optimistic concurrency control, correct implementations of Repeatable Read and Snapshot Isolation do not seem to be distinguishable. Both require write-write conflict detection.

Serializable Isolation

In terms of end-result, this is the simplest isolation level to reason about. Serializable Isolation must appear as if only a single transaction were executing at a time. Some systems, like SQLite and TigerBeetle, do Actually Serial Execution where only one transaction runs at a time. But few databases implement Serializable like this because it removes a number of fair concurrent execution histories. For example, two concurrent read-only transactions.

Postgres implements serializability via Serializable Snapshot Isolation. MySQL implements serializability via Two-Phase Locking. FoundationDB implements serializability via sequential timestamp assignment and conflict detection.

But the paper, A critique of snapshot isolation, provides a simple (though not necessarily efficient; I have no clue) approach via what they call Write Snapshot Isolation. In their algorithm, if any two transactions read and write set intersect (but not write and write set intersect), the transaction should be aborted. And this (plus Repeatable Read rules) is sufficient for Serializability.

I leave it to that paper for the proof of correctness. In terms of implementing it though it's quite simple and very similar to the Snapshot Isolation we already mentioned.

Inside of completeTransaction add:

                }) {
                        d.completeTransaction(t, AbortedTransaction)
                        return fmt.Errorf("write-write conflict")
+               }
+
+               // Serializable Isolation imposes the additional constraint that
+               // no transaction A may commit after reading any of the same
+               // keys as transaction B has written and committed during
+               // transaction A's life, or vice-versa.
+               if t.isolation == SerializableIsolation && d.hasConflict(t, func(t1 *Transaction, t2 *Transaction) bool {
+                       return setsShareItem(t1.readset, t2.writeset) ||
+                               setsShareItem(t1.writeset, t2.readset)
+               }) {
+                       d.completeTransaction(t, AbortedTransaction)
+                       return fmt.Errorf("read-write conflict")
                }
        }

And if we add a test for read-write conflicts:

func TestSerializableIsolation_readwrite_conflict(t *testing.T) {
        database := newDatabase()
        database.defaultIsolation = SerializableIsolation

        c1 := database.newConnection()
        c1.mustExecCommand("begin", nil)

        c2 := database.newConnection()
        c2.mustExecCommand("begin", nil)

        c3 := database.newConnection()
        c3.mustExecCommand("begin", nil)

        c1.mustExecCommand("set", []string{"x", "hey"})
        c1.mustExecCommand("commit", nil)

        _, err := c2.execCommand("get", []string{"x"})
        assertEq(err.Error(), "cannot get key that does not exist", "c5 get x")

        res, err := c2.execCommand("commit", nil)
        assertEq(res, "", "c2 commit")
        assertEq(err.Error(), "read-write conflict", "c2 commit")

        // But unrelated keys cause no conflict.
        c3.mustExecCommand("set", []string{"y", "no conflict"})
        c3.mustExecCommand("commit", nil)
}

We see it work! And that's it for a basic implementation of MVCC and major transaction isolation levels.

Production-quality testing

There are two major projects I'm aware of that help you test transaction implementations: Elle and Hermitage. These are probably where I'd go looking if I were implementing this for real.

This project took me long enough on its own and I felt reasonably comfortable with my tests that the gist of my logic was right that I did not test further. For that reason it surely has bugs.

Vacuuming and cleanup

One of the major things this implementation does not do is cleaning up old data. Eventually, older versions of values will be required by no transactions. They should be removed from the value version array. Similarly, eventually older transactions will be required by no transactions. They should be removed from the database transaction history list.

Even if we had the vacuuming process in place though, what about some extreme use patterns. What if a key's value was always going to be 1GB long. And what if multiple transactions made only small changes to the 1GB data. We'd be duplicating a lot of the value across versions.

It sounds less extreme when thinking about storing rows of data rather than key-value data. If a user has 100 columns and only updates one column a number of times, in our scheme we'd end up storing a ton of duplicate cell data for a row.

This is a real-world issue in Postgres that was called out by Andy Pavlo and the Ottertune folks. It turns out that Postgres alone among major databases stores the entire value for every version. In contrast other major databases like MySQL store a diff.

Conclusion

This post only begins to demonstrate that database behavior differs quite a bit both in terms of results and in terms of optimizations. Everyone implements the ideas differently and to varying degrees.

Moreover, we have only begun to implement the behavior a real SQL database supports. For example, how do visibility rules and conflict detection work with range queries? What about sub-transactions, and save points? These will have to be covered another time.

Hopefully seeing this simple implementation of MVCC and visibility rules helps to clarify at least some of the basics.

Here's a new post walking through an implementation of MVCC and major SQL transaction isolation levels, in 400 lines of Go code.

These ideas might sound esoteric, but they impact almost every developer using any database.https://t.co/crFKM74R5h pic.twitter.com/o9awTPpvvx

— Phil Eaton (@eatonphil) May 16, 2024

2024-04-10 08:00:00

I want to explain why the blogs in My favorite technical blogs are my favorite. That page is solely about non-corporate tech blogs. So this post is too. I'll have to make another list for favorite corporate tech blogs.

In short, they:

• Tackle hard and confusing topics
• Show working code
• Make things simpler
• Write regularly
• Talk about tradeoffs and downsides
• Avoid internet slang, memes, swearing, sarcasm, and ranting

Tackle hard and confusing topics

There are a number of problems in programming and computer science where otherwise knowledgeable programmers have to start mumbling about, or revert to cliches or group-think, because they aren't sure.

These are the best topics you can possibly dive deep into. And my favorite writers do exactly this.

They write about durability guarantees of disks and filesystems. They write about common pitfalls in benchmarking. They write about database consistency anomalies. They write about threading and IO models.

And they write about it by showing concrete examples and concrete logic so you can learn how to stop handwaving on the topic.

Their writing helps you come out with a useful mental model you can apply to your own problems.

And you know, sometimes it's not about about the topic being obscure. Good writers have the ability to tackle a boring topic in an interesting light. Maybe by digging deeper into a root cause. Or showing you the history behind the scenes.

Moreover, my favorite writers don't know everything. But they also don't pretend to know everything. They're quick to admit they don't understand something and ask for help from their readers.

Show working code

I love to see complete working code in a post. In contrast there are many projects that start out simple and people write an article that covers the project at a high level. But they keep working on the project and it becomes more complex.

It's not always easy to follow commits over time.

Eli Bendersky and Serge Zaitsev are particularly great at developing small but meaningful projects in a single post or short series.

On the other hand, if people only did this, we wouldn't hear about the development of long-running projects like V8 or Postgres. So I guess this style has limits. And I don't penalize people talking about long-running projects for not showing working code.

Make things simpler

One of the marks of a good writer is that you can make complex topics simple. And not just by being reductive. Though sometimes even being reductive is useful for education.

In contrast I sometimes see articles by less experienced writers and I marvel how they make a simple topic so complex. I recognize this because I was absolutely like that 10 years ago, if not 5 years ago.

Write regularly

My favorite blogs typically get a new post at least once a month. Some people, like Murat, write once a week.

I think the practice probably does improve your writing but mostly it's that they keep my attention by publishing regularly!

Talk about tradeoffs and downsides

Nothing builds trust like talking about the issues with something you built. No project is perfect. And to ignore the downsides risks seeming like you don't know or understand them.

So the writers I like the most talk about decisions in context. They talk about the good and the bad.

Avoid internet slang, memes, swearing, sarcasm, and ranting

There's no way I can think of talking about this without sounding super lame.

One thing I've noticed, particularly among younger colleagues, is the use of memes or swearing or using 4chan slang or using sarcasm. I used to write like this 10 years ago too.

There is a chunk of your audience who won't care. The problem is that there's also a chunk of your (potential) audience who definitely does care. There's even a chunk of your audience who may not care but just won't understand (i.e. non-native English speakers).

I have friends and folks I respect who write very well. But that also are also overly, unnecessarily edgy when they write. I don't like sharing these posts because I don't want to unnecessarily offend or turn off people either.

Closing thoughts

It would be boring if everyone wrote the same way. I'm glad the internet is fun and weird. But I wanted to share a few things that go into my favorite technical blogs that I'm always happy to refer people to.

I wrote a short post on what I think makes a great technical blog.https://t.co/QRFtQyQyU5 pic.twitter.com/QpsQC90EX5

— Phil Eaton (@eatonphil) April 10, 2024

2024-04-05 08:00:00

I started a paper reading club this week at work, focused on databases and distributed systems research. I posted in a general channel about the premise and asked if anyone was interested. I clarified the intended topic and that discussions would be asynchronous over email, run fortnightly.

Weekly seemed way too often. A month seemed way too infrequent. Fortnightly seemed decent.

I was nervous to do this because I've been here about 2 months. In the past I would have waited 6 months or a year to do this. But I don't know. If you see something you think should exist, why wait?

The only other consideration was past experiences I've written about having difficulty getting engagement with clubs at work. But EDB has near 1,000 employees. I figured there might at least be a couple interested.

Furthermore I figured if I only got a few people this entire idea would at least benefit myself, since I have been wanting to force myself to build a paper reading habit. And if no one responded, it would be only mildly embarassing and I'd not pursue it further.

But after a day, about 6 people showed interest. Which was better than I hoped! Folks from product management, support, development, and beyond.

So I opened a dedicated channel and asked people to start submitting papers and voting on them. One of my teammates started submitting some great papers on caches and reference counting.

I picked a first one, the Redshift paper, to get us started. Demonstrating the process to avoid confusion. And I made a calendar invite for everyone in the channel, the paper linked in the invite. I clarified in the invite that it was just a reminder and that the real discussion would still be async over email. (I've found it's best to repeatedly clarify process stuff.)

Once I had these first few folks interested I was able to post again in a broader company channel that a couple of us were starting this paper club. By the end of the day the dedicated channel was 29 folks. All in about 2 days.

Mailing lists are nicer than Slack or Discord in my opinion because they sort of force you to slow down, they are harder to miss (if someone starts a thread after you've seen a message in Slack or Discord, you tend to miss it), and easier to manage (read/unread).

Engineers often seem to get overwhelmed by a mass of Slack messages. Whereas they seem to be a bit more comfortable with email threads.

All of this is all the more important when you're running a global group. EDB has people everywhere.

Why do this?

Before I dropped out of college I did a research internship with a VLSI group at Harvard SEAS. And my favorite part was that they had a weekly (or biweekly?) Wednesday paper reading session where 15 people from the lab and adjacent labs would eat pizza after hours and discuss a paper.

I've been dying to recreate this at a company ever since. Since EDB is so distributed, we won't be discussing over pizza. But I'm still excited.

And I hope my experience serves as a blueprint for others.

I started a paper reading club at work, wrote about it as a possible blueprint for others.

I'm excited! I've wanted to have a gang at work with whom to read papers for a long time.https://t.co/vpwERj8pHe

— Phil Eaton (@eatonphil) April 6, 2024

2024-03-27 08:00:00

This is an external post of mine. Click here if you are not redirected.

2024-03-15 08:00:00

Having worked a bit in Zig, Rust, Go and now C, I think there are a few common topics worth having a fresh conversation on: automatic memory management, the standard library, and explicit allocation.

Zig is not a mature language. But it has made enough useful choices for a number of companies to invest in it and run it in production. The useful choices make Zig worth talking about.

Go and Rust are mature languages. But they have both made questionable choices that seem worth talking about.

All of these languages are developed by highly intelligent folks I personally look up to. And your choice to use any one of these is certainly fine, whichever it is.

The positive and negative choices particular languages made, though, are worth talking about as we consider what a systems programming language 10 years from now would look like. Or how these languages themselves might evolve in the next 10 years.

My perspective is mostly building distributed databases. So the points that I bring up may have no relevance to the kind of work you do, and that's alright. Moreover, I'm already aware most of these opinions are not shared by the language maintainers, and that's ok too. I am not writing to convince anyone.

Automatic memory management

One of my bigger issues with Zig is that it doesn't support RAII. You can defer cleanup to the end of a block; and this is half of the problem. But only RAII will allow for smart pointers and automatic (not manual) reference counting. RAII is an excellent option to default to, but in Zig you aren't allowed to. In contrast, even C "supports" automatic cleanup (via compiler extensions).

But most of the time, arenas are fine. Postgres is written in C and memory is almost entirely managed through nested arenas (called "memory contexts") that get cleaned up when some subset of a task finishes, recursively. Zig has builtin support for arenas, which is great.

Standard library

It seems regrettable that some languages have been shipping smaller standard libraries. Smaller standard libraries seem to encourage users of the language to install more transitively-unvetted third-party libraries, which increases build time and build flakiness, and which increases bitrot over time as unnecessary breaking changes occur.

People have been making jokes about node_modules for a decade now, but this problem is just as bad in Rust codebases I've seen. And to a degree it happens in Java and Go as well, though their larger standard libraries allow you to get further without dependencies.

Zig has a good standard library, which may be Go and Java tier in a few years. But one goal of their package manager seemed to be to allow the standard library to be broken up; made smaller. For example, JSON support moving out of the standard library into a package. I don't know if that is actually the planned direction. I hope not.

Having a large standard library doesn't mean that the programmer shouldn't be able to swap out implementations easily as needed. But all that is required is for the standard library to define an interface along with the standard library implementation.

The small size of the standard library doesn't just affect developers using the language, it even encourages developers of the language itself to depend on libraries owned by individuals.

Take a look at the transitive dependencies of an official Node.js package like node-gyp. Is it really the ideal outcome of a small standard library to encourage dependence in official libraries on libraries owned by individuals, like env-paths, that haven't been modified in 3 years? 68 lines of code. Is it not safer at this point to vendor that code? i.e. copy the env-paths code into node-gyp.

Similarly, if you go looking for compression support in Rust, there's none in the standard library. But you may notice the flate2-rs repo under the official rust-lang GitHub namespace. If you look at its transitive dependencies: flate2-rs depends on (an individual's) miniz_oxide which depends on (an individual's) adler that hasn't been updated in 4 years. 300 lines of code including tests. Why not vendor this code? It's the habits a small standard library builds that seem to encourage everyone not to.

I don't mean these necessarily constitute a supply-chain risk. I'm not talking about left-pad. But the pattern is sort of clear. Even official packages may end up depending on external party packages, because the commitment to a small standard library meant omitting stuff like compression, checksums, and common OS paths.

It's a tradeoff and maybe makes the job of the standard library maintainer easier. But I don't think this is the ideal situation. Dependencies are useful but should be kept to a reasonable minimum.

Hopefully languages end up more like Go than like Rust in this regard.

Explicit allocation

When folk discuss the Zig standard library's pattern of requiring an allocator argument for every method that allocates, they often talk about the benefit of swapping out allocators or the benefit of being able to handle OOM failures.

Both of these seem pretty niche to me. For example, in Zig tests you are encouraged to pass around a debug allocator that tells you about memory leaks. But this doesn't seem too different from compiling a C project with a debug allocator or compiling with different sanitizers on and running tests against the binary produced. In both cases you mostly deal with allocators at a global level depending on the environment you're running the code in (production or tests).

The real benefit of explicit allocations to me is much more trivial. You basically can't code a method in Zig without acknowledging allocations.

This is particularly useful for hotpath code. Take an iterator for example. It has a new() method, a next() method, and a done() method. In most languages, it's basically impossible at the syntax or compiler-level to know if you are allocating in the next() method. You may know because you know the behavior of all the code in next() by heart. But that won't happen all the time.

Zig is practically alone in that if you write the next() method and and don't pass an allocator to any method in the next() body, nothing in that next() method will allocate.

In any other language it might not be until you run a profiler that you notice an allocation that should have been done once in new() accidentally ended up in next() instead.

On the other hand, for all the same reasons, writing Zig is kind of a pain because everything takes an allocator!

Explicit allocation is not intrinsic to Zig, the language. It is a convention that is prevalent in the standard library. There is still a global allocator and any user of Zig could decide to use the global allocator. At which point you've got implicit allocation. So explicit allocation as a convention isn't a perfect solution.

But it, by default, gives you a level of awareness of allocations you just can't get from typical Go or Rust or C code, depending on the project's practices. Perhaps it's possible to switch off the Go, Rust and C standard library and use one where all functions that allocate do require an allocator.

But explicitly passing allocators is still sort of a visual hack.

I think the ideal situation in the future will be that every language supports annotating blocks of code as must-not-allocate or something along those lines. Either the compiler will enforce this and fail if you seem to allocate in a block marked must-not-allocate, or it will panic during runtime so you can catch this in tests.

This would be useful beyond static programming languages. It would be as interesting to annotate blocks in JavaScript or Python as must-not-allocate too.

Otherwise the current state of things is that you'd normally configure this sort of thing at the global level. Saying "there must not be any allocations in this entire program" just doesn't seem as useful in general as being able to say "there must not be any allocations in this one block".

Optional, not required, allocator arguments

Rust has nascent support for passing an allocator to methods that allocate. But it's optional. From what I understand, C++ STL is like this too.

These are both super useful for programming extensions. And it's one of the reasons I think Zig makes a ton of sense for Postgres extensions specifically. Because it was only and always ever built for running in an environment with someone else's allocator.

Praise for Zig, Rust, and Go tooling

All three of these have really great first-party tooling including build system, package management, test runners and formatters. The idea that the language should provide a great environment to code in (end-to-end) makes things simpler and nicer for programmers.

Meandering non-conclusion

Use the language you want to use. Zig and Rust are both nice alternatives to writing vanilla C.

On the other hand, I've been pleasantly surprised writing Postgres C. How high level it is. It's almost a separate language since you're often dealing with user-facing constructs, like Postgres's Datum objects which represent what you might think of as a cell in a Postgres database. And you can use all the same functions provided for Postgres SQL for working with Datums, but from C.

I've also been able work a bit on Postgres extensions in Rust with pgrx lately, which I hope to write about soon. And when I saw pgzx for writing Postgres extensions in Zig I was excited to spend some time with that too.

Wrote a post on my wishlist for Zig and Rust. Focused on automatic memory management, the standard library, and explicit allocation.https://t.co/dvynizU9V2 pic.twitter.com/iTXp5QVxj0

— Phil Eaton (@eatonphil) March 15, 2024

2024-03-11 08:00:00

A little over a month ago, I joined EnterpriseDB on a distributed Postgres product (PGD). The process of onboarding myself has been pretty similar at each company in the last decade, though I think I've gotten better at it. The process is of course influenced by the team, and my coworkers have been excellent. Still, I wanted to share my thought process and personal strategies.

Avoid, at first, what is always challenging

Trickier things at companies are the people, organization, and processes. What code exists? How does it work together? Who owns what? How can I find easy code issues to tackle? How do I know what's important (so I can avoid picking it up and becoming a bottleneck).

But also, in the first few days or weeks you aren't exactly expected to contribute meaningfully to features or bugs. Your sprint contributions are not tracked too closely.

The combination of 1) what to avoid and 2) the sprint-freedom-you-have leads to a few interesting and valuable areas to work on on your own: the build process, tests, running the software, and docs.

But code need not be ignored either. Some frequent areas to get your first code contributions in include user configuration code, error messages, and stale code comments.

What follows are some little 1st day, 1st week, 1st month projects I went through to bootstrap my understanding of the system.

Build process

First off, where is the code and how do you build it? This requires you to have all the relevant dependencies. Much of my work is on a Postgres extension. This meant having a local Postgres development environment, having gcc, gmake (on mac), Perl, and so on. And furthermore, PGD is a pretty mature product so it supports building against multiple Postgres distributions. Can I build against all of them?

The easiest situation is when there are instructions for all of this, linked directly from your main repo. When I started, the instructions did exist but in a variety of places. So over the first week I started collecting all of what I had learned about building the system, with dependencies, across distributions, and with various important flags (debug mode on, asserts enabled, etc.). I finished the first week by writing a little internal blog post called "Hacking on PGD".

I hadn't yet figured out the team processes so I didn't want to bother anyone by trying to get this "blog post" committed anywhere yet as official internal documentation. Maybe there already was a good doc, I just hadn't noticed it yet. So I just published it in a private Confluence page and shared it in the private team slack. If anyone else benefited from it, great! Otherwise, I knew I'd want to refer back to it.

This is an important attitude I think. It can be hard to tell what others will benefit from. If you get into the habit of writing things down internally for your own sake, but making it available internally, it is likely others will benefit from it too. This is something I've learned from years of blogging publicly outside of work.

Moreover, the simple act of writing a good post creates yourself as something of an authority. This is useful for yourself if no one else.

Writing a good post

Let's get distracted here for a second. One of the most important things I think in documentation is documenting not just what does exist but what doesn't. If you had to take a path to get something to work, did you try other paths that didn't work? It can be extremely useful to figure out what exactly is required for something.

Was there a flag that you tried to build with but you didn't try building without it? Well try again without it and make sure it was necessary. Was there some process you executed where the build succeeded but you can't remember if it was actually necessary for the build to succeed?

It's difficult to explain why I think this sort of precision is useful but I'm pretty sure it is. Maybe because it builds the habit of not treating things as magic when you can avoid it. It builds the habit of asking questions (if only to yourself) to understand and not just to get by.

Static analysis? Dynamic analysis?

Going back to builds, another aspect to consider is static and dynamic analysis. Are there special steps to using gdb or valgrind or other analyzers? Are you using them already? Can you get them running locally? Has any of this been documented?

Maybe the answer to all of those is yes, or maybe none of those are relevant but there are likely similar tools for your ecosystem. If analysis tools are relevant and no one has yet explored them, that's another very useful area to explore as a newcomer.

Testing

After I got the builds working, I felt the obvious next step was to run tests. But what tests exist? Are there unit tests? Integration tests? Anything else? Moreover, is there test coverage? I was certain I'd be able to find some low-hanging contributions to make if I could find some files with low test coverage.

Alas, my certainty hit the wall in that there were in fact too many types of integration tests that all do provide coverage already. They just don't all report coverage.

The easiest ways to report coverage (with gcov) were only reporting coverage for certain integration tests that we run locally. There are more integration tests run in cloud environments and getting coverage reports there to merge with my local coverage files would have required more knowledge of people and processes, areas that I wanted not to be forced to think about too quickly.

So coverage wasn't a good route to go. But around this time, I noticed a ticket that asked for a simple change to user configuration code. I was able to make the change pretty quickly and wanted to add tests. We have our own test framework built on top of Postgres's powerful Perl test framework. But it was a little difficult to figure out how to use either of them.

So I copied code from other tests and pared it down until I got the smallest version of test code I could get. This took maybe a day or two of tweaking lines and rerunning tests since I didn't understand everything that was/wasn't required. Also it's Perl and I've never written Perl before so that took a bit of time and ChatGPT. (Arrays, man.)

In the end though I was able to collect my learnings into another internal confluence post just about how to write tests, how to debug tests, how to do common things within tests (for example, ensuring a Postgres log line was outputted), etc. I published this post as well and shared it in the team Slack.

Running

I had PGD built locally and was able to run integration tests locally, but I still hadn't gotten a cluster running. Nor played with the eventual consistency demos I knew we supported. We had a great quickstart that ran through all the manual steps of getting a two-node cluster up. This was a distillation, for devs, of a more elaborate process we give to customers in a production-quality script.

But I was looking for something in between a production-quality script and manually initializing a local cluster. And I also wanted to practice my understanding of our test process. So I ported our quickstart to our integration test framework and made a PR with this new test, eventually merging this into the repo. And I wrote a minimal Python script for bringing up a local cluster. I've got an open PR to add this script to the repo. Maybe I'll learn though that a simple script such as this does already exist, and that's fine!

Docs

The entire time, as I'd been trying to build and test and run PGD, I was trying to understand our terminology and architecture by going through our public docs. I had a lot of questions coming out of this I'd ask in the team channel.

Not to toot my horn but I think it's somewhat of a superpower to be able/willing to ask "dumb questions" in a group setting. That's how I frame it anyway. "Dumb question: what does X mean in this paragraph?" Or, "dumb question: when we say performance improvement because of Y, what is the intuition here?" Because of the time spent here, I was able to make a few more docs contributions as I read through the docs as well.

You have to balance where you ask your dumb questions though. Asking dumb questions to one person doesn't benefit the team. But asking dumb questions in too wide a group is sometimes bad politics. Asking "dumb questions" in front of your team seems to have the best bang for buck.

But maybe the more important contributions were, when I got more comfortable with the team, proposing to merge my personal, internal Confluence blog posts into the repo as docs. I think in a number of cases, what I wrote about indeed hadn't been concisely collected before and thus was useful to have as team documentation.

Even more challenging was trying to distill (a chunk of) the internal architecture. Only after following many varied internal docs and videos, and following through numerous code paths, was I able to propose an architecture diagram outlining major components and communication between them, with their differing formats (WAL records, internal enums, etc.) and means of communication (RPC, shared memory, etc.). This architecture diagram is still in review and may be totally off. But it's already helped at least me think about the system.

In most cases this was all information that the team had already written or explained but just bringing it together and summarizing provided a different useful perspective I think. Even if none of the docs got merged it still helped to build my own understanding.

Beyond the repo

Learning the project is just one aspect of onboarding. Beyond that I join the #cats channel, the #dogs channel, found some fellow New Yorkers and opened a NYC channel, and tried to find Zoom-time with the various people I'd see hanging around common team Slack channels. Trying to meet not just devs but support folk, product managers, marketing folk, sales folk, and anyone else!

Walking the line between scouring our docs and GitHub and Confluence and Jira on my own, and bugging people with my incessant questions.

I've enjoyed my time at startups. I've been a dev, a manager, a founder, a cofounder. But I'm incredibly excited to be back, at a bigger company, full-time as a developer hacking on a database!

And what about you? What do you do to onboard yourself at a new company or new project?

I've been having an absolute blast in my first month at EDB and I wanted to share a few of my strategies for onboarding myself on a database team. Strategies broadly applicable for devs on a new team/project.https://t.co/TS5qRLysuA pic.twitter.com/lvuxDBQJwx

— Phil Eaton (@eatonphil) March 12, 2024

2024-02-08 08:00:00

Distributed consensus in transactional databases (e.g. etcd or Cockroach) is a big deal these days. Most often under the hood are variations of log-based Paxos-like algorithms such as MultiPaxos, Viewstamped Replication, or Raft. While there are new variations that come out each year, optimizing for various workloads, these algorithms are fairly standard and well-understood.

In fact they are used in so many places, Kubernetes for example, that even if you don't decide to implement Raft (which is fun and I encourage it), it seems worth building an intuition for distributed consensus.

What happens as you tweak a configuration. What happens as the production environment changes. Or what to reach for as product requirements change.

I've been thinking about the basics of distributed consensus recently. There has been a lot to digest and characterize. And I'm only beginning to get an understanding.

This post is an attempt to share some of the intuition built up reading about and working in this space. Originally this post was also going to end with a walkthrough of my most recent Raft implementation in Rust. But I'm going to hold off on that for another time.

I was fortunate to have a few excellent reviewers looking at versions of this post: Paul Nowoczynski, Alex Miller, Jack Vanlightly, Daniel Chia, and Alex Petrov. Thank you!

Let's start with Raft.

Raft

Raft is a distributed consensus algorithm that allows you to build a replicated state machine on top of a replicated log.

A Raft library handles replicating and durably persisting a sequence (or log) of commands to at least a majority of nodes in a cluster. You provide the library a state machine that interprets the replicated commands. From the perspective of the Raft library, commands are just opaque byte strings.

For example, you could build a replicated key-value store out of SET and GET commands that are passed in by a client. You provide a Raft library state machine code that interprets the Raft log of SET and GET commands to modify or read from an in-memory hashtable. You can find concrete examples of exactly this replicated key-value store modeling in previous Raft posts I've written.

All nodes in the cluster run the same Raft code (including the state machine code you provide); communicating among themselves. Nodes elect a semi-permanent leader that accepts all reads and writes from clients. (Again, reads and writes are modeled as commands).

To commit a new command to the cluster, clients send the command to all nodes in the cluster. Only the leader accepts this command, if there is currently a leader. Clients retry until there is a leader that accepts the command.

The leader appends the command to its log and makes sure to replicate all commands in its log to followers in the same order. The leader sends periodic heartbeat messages to all followers to prolong its term as leader. If a follower hasn't heard from the leader within a period of time, it becomes a candidate and requests votes from the cluster.

When a follower is asked to accept a new command from a leader, it checks if its history is up-to-date with the leader. If it is not, the follower rejects the request and asks the leader to send previous commands to bring it up-to-date. It does this ultimately, in the worst case of a follower that has lost all history, by going all the way back to the very first command ever sent.

When a quorum (typically a majority) of nodes has accepted a command, the leader marks the command as committed and applies the command to its own state machine. When followers learn about newly committed commands, they also apply committed commands to their own state machine.

For the most part, these details are graphically summarized in Figure 2 of the Raft paper.

Availability and linearizability

Taking a step back, distributed consensus helps a group of nodes, a cluster, agree on a value. A client of the cluster can treat a value from the cluster as if the value was atomically written to and read from a single thread. This property is called linearizability.

However, with distributed consensus, the client of the cluster has better availability guarantees from the cluster than if the client atomically wrote to or read from a single thread. A single thread that crashes becomes unavailable. But some number f nodes can crash in a cluster implementing distributed consensus and still 1) be available and 2) provide linearizable reads and writes.

That is: distributed consensus solves the problem of high availability for a system while remaining linearizable.

Without distributed consensus you can still achieve high availability. For example, a database might have two read replicas. But a client reading from a read replica might get stale data. Thus, this system (a database with two read replicas) is not linearizable.

Without distributed consensus you can also try synchronous replication. It would be very simple to do. Have a fixed leader and require all nodes to acknowledge before committing, But the value here is extremely limited. If a single node in the cluster goes down the entire cluster is down.

You might think I'm proposing a strawman. We could simply designate a permanent leader that handles all reads and writes; and require a majority of nodes to commit a command before the leader responds to a client. But in that case, what's the process for getting a lagging follower up-to-date? And what happens if it is the leader who goes down?

Well, these are not trivial problems! And, beyond linearizability that we already mentioned, these problems are exactly what distributed consensus solves.

Why does linearizability matter?

It's very nice, and often even critical, to have a highly available system that will never give you stale data. And regardless, it's convenient to have a term for what we might naively think of as the "correct" way you'd always want to set and get a value.

So linearizability is a convenient way of thinking about complex systems, if you can use or build a system that supports it. But it's not the only consistency approach you'll see in the wild.

As you increase the guarantees of your consistency model, you tend to sacrifice performance. Going the opposite direction, some production systems sacrifice consistency to improve performance. For example, you might allow stale reads from any node, reading only from local state and avoiding consensus, so that you can reduce load on a leader and avoid the overhead of consensus.

There are formal definitions for lower consistency models, including sequential and read-your-writes. You can read the Jepsen page for more detail.

Best and worst case scenarios

A distributed system relies on communicating over the network. The worse the network, whether in terms of latency or reliability, the longer it will take for communication to happen.

Aside from the network, disks can misdirect writes or corrupt data. Or you could be mounted on a network filesystem such as EBS.

And processes themselves can crash due to low disk space or the OOM killer.

It will take longer to achieve consensus to commit messages these scenarios. If messages take longer to reach nodes, or if nodes are constantly crashing, followers will timeout more often, triggering leader election. And the leader election itself (which also requires consensus) will also take longer.

The best case scenario for distributed consensus is where the network is reliable and low-latency. Where disks are reliable and fast. And where processes don't often crash.

TigerBeetle has an incredible visual simulator that demonstrates what happens across ever-worsening environments. While TigerBeetle and this simulator use Viewstamped Replication, the demonstrated principles apply to Raft as well.

What happens when you add nodes?

Distributed consensus algorithms make sure that some minimum number of nodes in a cluster agree before continuing. The minimum number is proportional to the total number of nodes in the cluster.

A typical implementation of Raft for example will require 3 nodes in a 5-node cluster to agree before continuing. 4 nodes in a 7-node cluster. And so on.

Recall that the p99 latency for a service is at least as bad as the slowest external request the service must make. As you increase the number of nodes you must talk to in a consensus cluster, you increase the chance of a slow request.

Consider the extreme case of a 101-node cluster requiring 51 nodes to respond before returning to the client. That's 51 chances for a slower request. Compared to 4 chances in a 7-node cluster. The 101-node cluster is certainly more highly available though! It can tolerate 49 nodes going down. The 7-node cluster can only tolerate 3 nodes going down. The scenario where 49 nodes go down (assuming they're in different availability zones) seems pretty unlikely!

Horizontal scaling with distributed consensus? Not exactly

All of this is to say that the most popular algorithms for distributed consensus, on their own, have nothing to do with horizontal scaling.

The way that horizontally scaling databases like Cockroach or Yugabyte or Spanner work is by sharding the data, transparent to the client. Within each shard data is replicated with a dedicated distributed consensus cluster.

So, yes, distributed consensus can be a part of horizontal scaling. But again what distributed consensus primarily solves is high availability via replication while remaining linearizable.

This is not a trivial point to make. etcd, consul, and rqlite are examples of databases that do not do sharding, only replication, via a single Raft cluster that replicates all data for the entire system.

For these databases there is no horizontal scaling. If they support "horizontal scaling", they support this by doing non-linearizable (stale) reads. Writes remain a challenge.

This doesn't mean these databases are bad. They are not. One obvious advantage they have over Cockroach or Spanner is that they are conceptually simpler. Conceptually simpler often equates to easier to operate. That's a big deal.

Optimizations

We've covered the basics of operation, but real-world implementations get more complex.

Snapshots

Rather than letting the log grow indefinitely, most libraries implement snapshotting. The user of the library provides a state machine and also provides a method for serializing the state machine to disk. The Raft library periodically serializes the state machine to disk and truncates the log.

When a follower is so far behind that the leader no longer has a log entry (because it has been truncated), the leader transfers an entire snapshot to the follower. Then once the follower is caught up on snapshots, the leader can transfer normal log entries again.

This technique is described in the Raft paper. While it isn't necessary for Raft to work, it's so important that it is hardly an optimization and more a required part of a production Raft system.

Batching

Rather than limiting clients of the cluster to submitting only one command at a time, it's common for the cluster to accept many commands at a time. Similarly, many commands at a time are submitted to followers. When any node needs to write commands to disk, it can batch commands to disk as well.

But you can go a step beyond this in a way that is completely opaque to the Raft library. Each opaque command the client submits can also contain a batch of messages. In this scenario, only the user-provided state machine needs to be aware that each command it receives is actually a batch of messages that it should pull apart and interpret separately.

This latter techinque is a fairly trivial way to increase throughput by an order of magnitude or two.

Disk and network

In terms of how data is stored on disk and how data is sent over the network there is obvious room for optimization.

A naive implementation might store JSON on disk and send JSON over the network. A slightly more optimized implementation might store binary data on disk and send binary data over the network.

Similarly you can swap out your RPC for gRPC or introduce zlib for compression to network or disk.

You can swap out synchronous IO for libaio or io_uring or SPDK/DPDK.

A little tweak I made in my latest Raft implementation was to index log entries so searching the log was not a linear operation. Another little tweak was to introduce a page cache to eliminate unnecessary disk reads. This increased throughput for by an order of magnitude.

Flexible quorums

This brilliant optimization by Heidi Howard and co. shows you can relax the quorum required for committing new commands so long as you increase the quorum required for electing a leader.

In an environment where leader election doesn't happen often, flexible quorums can increase throughput and decrease latency. And it's a pretty easy change to make!

More

These are just a couple common optimizations. You can also read about parallel state machine apply, parallel append to disk, witnesses, compartmentalization, and leader leases. TiKV, Scylla, RedPanda, and Cockroach tend to have public material talking about this stuff.

There are also a few people I follow who are often reviewing relevant papers, if they are not producing their own. I encourage you to follow them too if this is interesting to you:

• https://muratbuffalo.blogspot.com/
• https://charap.co/
• https://brooker.co.za/blog/
• https://distributed-computing-musings.com/

Safety and testing

The other aspect to consider is safety. For example, checksums for everything written to disk and passed over the network; or being able to recover from corruption in the log.

Testing is also a big deal. There are prominent tools like Jepsen that check for consistency in the face of fault injection (process failure, network failure, etc.). But even Jepsen has its limits. For example, it doesn't test disk failure.

FoundationDB made popular a number of testing techniques. And the people behind this testing went on to build a product, Antithesis, around deterministic testing of non-deterministic code while injecting faults.

And on that topic there's Facebook Experimental's Hermit deterministic Linux hypervisor that may help to test complex distributed systems. However, my experience with it has not been great and the maintainers do not seem very engaged with other people who have reported bugs. I'm hopeful for it but we'll see.

Antithesis and Hermit seem like a boon when half the trouble of working on distributed consensus implementations is avoiding flakey tests.

Another promising avenue is emitting logs during the Raft lifecycle and validating the logs against a TLA+ spec. Microsoft has such a project that has begun to see adoption among open-source Raft implementations.

Conclusion

Everything aside, consensus is expensive. There is overhead to the entire consensus process. So if you do not need this level of availability and can settle for some process via backups, it's going to have lower latency and higher throughput than if it had to go through distributed consensus.

If you do need high availability, distributed consensus can be a great choice. But consider the environment and what you want from your consensus algorithm.

Also, while MultiPaxos, Raft, and Viewstamped Replication are some of the most popular algorithms for distributed consensus, there is a world beyond. Two-phase commit, ZooKeeper Atomic Broadcast, PigPaxos, EPaxos, Accord by Cassandra. The world of distributed consensus also gets especially weird and interesting outside of OLTP systems.

But that's enough for one post.

Further reading

• The Raft Paper
• The Raft TLA+ Spec
• The Raft Author's PhD Thesis on Raft
• Designing Data-Intensive Applications
• David Beazley's Raft Course if you can get your company to pay for it

I wrote a post about building an intuition for distributed consensus in OLTP systems!

Very grateful to all the folks who reviewed.https://t.co/wMxUuokKeg pic.twitter.com/cfY2kdfqak

— Phil Eaton (@eatonphil) February 8, 2024

2024-01-09 08:00:00

I spent a week looking at MySQL/MariaDB internals along with ~80 other devs. Although MySQL and MariaDB are mostly the same (more on that later), I focused on MariaDB specifically this week.

Before last week I had never built MySQL/MariaDB before. The first day of this hack week, I got MariaDB building locally and made a code tweak so that SELECT 23 returned 213, and another tweak so that SELECT 80 + 20 returned 60. The second day I got a basic UDF in C working so that SELECT mysum(20, 30) returned 50.

The rest of the week I spent figuring out how to build a minimal in-memory storage engine, which I'll walk through in this post. 218 lines of C++.

It supports CREATE, DROP, INSERT, and SELECT for tables that only have INTEGER fields. It is explicitly not thread-safe because I didn't have time to understand MariaDB's lock primitives.

In this post I'll also talk about how the MariaDB custom storage API compares to the Postgres one, based on a previous hack week project I did.

All code for this post can be found in my fork on GitHub.

MySQL and MariaDB

Before we go further though, why do I keep saying MySQL/MariaDB?

MySQL is GPL licensed (let's completely ignore the commercial variations of MySQL that Oracle offers). The code is open-source. However, the development is done behind closed doors. There is a code dump every month or so.

MariaDB is a fork of MySQL by the creator of MySQL (who is no longer involved, as it happens). It is also GPL licensed (let's completely ignore the commercial variations of MariaDB that MariaDB Corporation offers). The code is open-source. The development is also open-source.

When you install "MySQL" in your Linux distro you are often actually installing MariaDB.

The two are mostly compatible. During this week, I stumbled onto that they evolved support for SELECT .. FROM VALUES .. differently. Some differences are documented on the MariaDB KB. But this KB is painful to browse. Which leads me to my next point.

The MySQL docs are excellent. Easy to read, browse; and they are thorough. The MariaDB docs are a work in progress. I'm sorry I can't be stoic: in just a week I've come to really hate using this KB. Thankfully, in some twisted way, it also doesn't seem to be very thorough either. It isn't completely avoidable though since there is no guarantee MySQL and MariaDB do the same thing.

Ultimately, I spent the week using MariaDB because I'm biased toward fully open projects. But I kept having to look at MySQL docs, hoping they were relevant.

Now that you understand the state of things, let's move on to fun stuff!

Storage engines

Mature databases often support swapping out the storage layer. Maybe you want an in-memory storage layer so that you can quickly run integration tests. Maybe you want to switch between B-Trees (read-optimized) and LSM Trees (write-optimized) and unordered heaps (write-optimized) depending on your workload. Or maybe you just want to try a third-party storage library (e.g. RocksDB or Sled or TiKV).

The benefit of swapping out only the storage engine is that, from a user's perspective, the semantics and features of the database stay mostly the same. But the database is magically faster for a workload.

You keep powerful user management, extension support, SQL support, and a well-known wire protocol. You modify only the method of storing the actual data.

Existing storage engines

MySQL/MariaDB is particularly well known for its custom storage engine support. The MySQL docs for alternate storage engines are great.

While the docs do warn that you should probably stick with the default storage engine, that warning didn't quite feel strong enough because nothing else seemed to indicate the state of other engines.

Specifically, in the past I was always interested in the CSV storage engine. But when you look at the actual code for the CSV engine there is a pretty strong warning:

First off, this is a play thing for me, there are a number of things
wrong with it:
  *) It was designed for csv and therefore its performance is highly
     questionable.
  *) Indexes have not been implemented. This is because the files can
     be traded in and out of the table directory without having to worry
     about rebuilding anything.
  *) NULLs and "" are treated equally (like a spreadsheet).
  *) There was in the beginning no point to anyone seeing this other
     then me, so there is a good chance that I haven't quite documented
     it well.
  *) Less design, more "make it work"

Now there are a few cool things with it:
  *) Errors can result in corrupted data files.
  *) Data files can be read by spreadsheets directly.

TODO:
 *) Move to a block system for larger files
 *) Error recovery, its all there, just need to finish it
 *) Document how the chains work.

-Brian

The difference between the seeming confidence of the docs and seeming confidence of the contributor made me chuckle.

The benefit of these diverse storage engines for me was that they give examples of how to implement the storage engine API. The csv, blackhole, example, and heap storage engines were particularly helpful to read.

The heap engine is a complete in-memory storage engine. Complete means complex though. So there seemed to be room for a stripped down version of an in-memory engine.

And that's we'll cover in this post! First though I want to talk a little bit about the limitations of custom storage engines.

Limitations

While being able to tailor a storage engine to a workload is powerful, there are limits to the benefits based on the design of the storage API.

Both Postgres and MySQL/MariaDB currently have a custom storage API built around individual rows.

Column-wise execution

I have previously written that custom storage engines allows you to switch between column- and row-oriented data storage. Two big reasons to do column-wise storage are 1) opportunity for compression, and 2) fast operations on a single column.

The opportunity for 1) compression on disk would still exist even if you needed to deal with individual rows at the storage API layer since the compression could happen on disk. However any benefits of passing around compressed columns in memory disappear if you must convert to rows for the storage API.

You'd also lose the advantage for 2) fast operations on a single column if the column must be converted into a row at the storage API whereupon it's passed to higher levels that perform execution. The execution would happen row-wise, not column-wise.

All of this is to say that while column-wise storage is possible, the benefit of doing so is not obvious with the current API design for both MySQL/MariaDB and Postgres.

Vectorization

An API built around individual rows also sets limits on the amount of vectorization you can do. A custom storage engine could still do some vectorization under the hood: always filling a buffer with N rows and returning a row from the buffer when the storage API requests a single row. But there is likely some degree of performance left on the table with an API that deals with individual rows.

Remember though: if you did batched reads and writes of rows in the custom storage layer, there isn't necessarily any vectorization happening at the execution layer. From a previous study I did, neither MySQL/MariaDB nor Postgres do vectorized query execution. This paragraph isn't a critique of the storage API, it's just something to keep in mind.

Storage versus execution

The general point I'm making here is that unless both the execution and storage APIs are designed in a certain way, you may attempt optimizations in the storage layer that are ineffective or even harmfull because the execution layer doesn't or can't take advantage of them.

Nothing permanent

The current limitations of the storage API are not intrinsic aspects of MySQL/MariaDB or Postgres's design. For both project there used to be no pluggable storage at all. We can imagine a future patch to either project that allows support for batched row reads and writes that together could make column-wise storage and vectorized execution more feasible.

Even today there have been invasive attempts to fully support column-wise storage and execution in Postgres. And there have also been projects to bring vectorized execution to Postgres.

I'm not as familiar with the MySQL landscape to comment about efforts at the moment their.

Debug build of MariaDB running locally

Now that you've got some background, let's get a debug build of MariaDB!

$ git clone https://github.com/MariaDB/server mariadb
$ cd mariadb
$ mkdir build
$ cd build
$ cmake -DCMAKE_BUILD_TYPE=Debug ..
$ make -j8

This takes a while. When I was hacking on Postgres (a C project), it took 1 minute on my beefy Linux server to build. It took 20-30 minutes to build MySQL/MariaDB from scratch. That's C++ for you!

Thankfully incremental builds of MySQL/MariaDB for a tweak after the initial build take roughly the same time as incremental builds of Postgres after a tweak.

Once the build is done, create a database.

$ ./build/scripts/mariadb-install-db --srcdir=$(pwd) --datadir=$(pwd)/db

And create a config for the database.

$ echo "[client]
socket=$(pwd)/mariadb.sock

[mariadb]
socket=$(pwd)/mariadb.sock

basedir=$(pwd)
datadir=$(pwd)/db
pid-file=$(pwd)/db.pid" > my.cnf

Start up the server.

$ ./build/sql/mariadbd --defaults-extra-file=$(pwd)/my.cnf --debug:d:o,$(pwd)/db.debug
./build/sql/mariadbd: Can't create file '/var/log/mariadb/mariadb.log' (errno: 13 "Permission denied")
2024-01-03 17:10:15 0 [Note] Starting MariaDB 11.4.0-MariaDB-debug source revision 3fad2b115569864d8c1b7ea90ce92aa895cfef08 as process 185550
2024-01-03 17:10:15 0 [Note] InnoDB: !!!!!!!! UNIV_DEBUG switched on !!!!!!!!!
2024-01-03 17:10:15 0 [Note] InnoDB: Compressed tables use zlib 1.2.13
2024-01-03 17:10:15 0 [Note] InnoDB: Number of transaction pools: 1
2024-01-03 17:10:15 0 [Note] InnoDB: Using crc32 + pclmulqdq instructions
2024-01-03 17:10:15 0 [Note] InnoDB: Initializing buffer pool, total size = 128.000MiB, chunk size = 2.000MiB
2024-01-03 17:10:15 0 [Note] InnoDB: Completed initialization of buffer pool
2024-01-03 17:10:15 0 [Note] InnoDB: Buffered log writes (block size=512 bytes)
2024-01-03 17:10:15 0 [Note] InnoDB: End of log at LSN=57155
2024-01-03 17:10:15 0 [Note] InnoDB: Opened 3 undo tablespaces
2024-01-03 17:10:15 0 [Note] InnoDB: 128 rollback segments in 3 undo tablespaces are active.
2024-01-03 17:10:15 0 [Note] InnoDB: Setting file './ibtmp1' size to 12.000MiB. Physically writing the file full; Please wait ...
2024-01-03 17:10:15 0 [Note] InnoDB: File './ibtmp1' size is now 12.000MiB.
2024-01-03 17:10:15 0 [Note] InnoDB: log sequence number 57155; transaction id 16
2024-01-03 17:10:15 0 [Note] InnoDB: Loading buffer pool(s) from ./db/ib_buffer_pool
2024-01-03 17:10:15 0 [Note] Plugin 'FEEDBACK' is disabled.
2024-01-03 17:10:15 0 [Note] Plugin 'wsrep-provider' is disabled.
2024-01-03 17:10:15 0 [Note] InnoDB: Buffer pool(s) load completed at 240103 17:10:15
2024-01-03 17:10:15 0 [Note] Server socket created on IP: '0.0.0.0'.
2024-01-03 17:10:15 0 [Note] Server socket created on IP: '::'.
2024-01-03 17:10:15 0 [Note] mariadbd: Event Scheduler: Loaded 0 events
2024-01-03 17:10:15 0 [Note] ./build/sql/mariadbd: ready for connections.
Version: '11.4.0-MariaDB-debug'  socket: './mariadb.sock'  port: 3306  Source distribution

With that --debug flag, debug logs will show up in $(pwd)/db.debug. It's unclear why debug logs are treated separately from the console logs shown here. I'd rather them all be in one place.

In another terminal, run a client and make a request!

$ ./build/client/mariadb --defaults-extra-file=$(pwd)/my.cnf --database=test
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MariaDB monitor.  Commands end with ; or \g.
Your MariaDB connection id is 3
Server version: 11.4.0-MariaDB-debug Source distribution

Copyright (c) 2000, 2018, Oracle, MariaDB Corporation Ab and others.

Type 'help;' or '\h' for help. Type '\c' to clear the current input statement.

MariaDB [test]> SELECT 1;
+---+
| 1 |
+---+
| 1 |
+---+
1 row in set (0.001 sec)

Huzzah! Let's write a custom storage engine!

Where does the code go?

When writing an extension for some project, I usually expect to have the extension exist in its own repo. I was able to do this with the Postgres in-memory storage engine I wrote. And in general, Postgres extensions exist as their own repos.

I was able to create and build a UDF plugin outside the MariaDB source tree. But when it came to getting a storage engine to build and load successfully, I wasted almost an entire day (a large amount of time in a single hack week) getting nowhere.

Extensions for MySQL/MariaDB are most easily built via the CMake infrastructure within the repo. Surely there's some way to replicate that infrastructure from outside the repo but I wasn't able to figure it out within a day and didn't want to spend more time on it.

Apparently the normal thing to do in MySQL/MariaDB is to keep extensions within a fork of MySQL/MariaDB.

When I switched to this method I was able to very quickly get the storage engine building and loaded. So that's what we'll do.

Boilerplate

Within the MariaDB source tree, create a new folder in the storage subdirectory.

$ mkdir storage/memem

Within storage/memem/CMakeLists.txt add the following.

# Copyright (c) 2006, 2010, Oracle and/or its affiliates. All rights reserved.
# 
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; version 2 of the License.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1335 USA

SET(MEMEM_SOURCES  ha_memem.cc ha_memem.h)
MYSQL_ADD_PLUGIN(memem ${MEMEM_SOURCES} STORAGE_ENGINE)

This hooks into MySQL/MariaDB build infrastructure. So next time you run make within the build directory we created above, it will also build this project.

The storage engine class

It would be nice to see a way to extend MySQL in C (for one, because it would then be easier to port to other languages). But all of the builtin storage methods use classes. So we'll do that too.

The class we must implement is an instance of handler. There is a single handler instance per thread, corresponding to a single running query. (Postgres gives each query its own process, MySQL gives each query its own thread.) However, handler instances are reused across different queries.

There are a number of virtual methods on handler we must implement in our subclass. For most of them we'll do nothing: simply returning immediately. These simple methods will be implemented in ha_memem.h. The methods with more complex logic will be implemented in ha_memem.cc.

Let's set up includes in ha_memem.h.

/* Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; version 2 of the License.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */

#ifdef USE_PRAGMA_INTERFACE
#pragma interface /* gcc class implementation */
#endif

#include "thr_lock.h"
#include "handler.h"
#include "table.h"
#include "sql_const.h"

#include <vector>
#include <memory>

Next we'll define structs for our in-memory storage.

typedef std::vector<uchar> MememRow;

struct MememTable
{
  std::vector<std::shared_ptr<MememRow>> rows;
  std::shared_ptr<std::string> name;
};

struct MememDatabase
{
  std::vector<std::shared_ptr<MememTable>> tables;
};

Within ha_memem.cc we'll implement a global (not thread-safe) static MememDatabase* that all handler instances will query when requested. We need the definitions in the header file though because we'll store the table currently being queried in the handler subclass.

This is so that every call to write_row to write a single row or call to rnd_next to read a single row does not need to look up the in-memory table object N times within the same query.

And finally we'll define the subclass of handler and implementations of trivial methods.

class ha_memem final : public handler
{
  uint current_position= 0;
  std::shared_ptr<MememTable> memem_table= 0;

public:
  ha_memem(handlerton *hton, TABLE_SHARE *table_arg) : handler(hton, table_arg)
  {
  }
  ~ha_memem()= default;
  const char *index_type(uint key_number) { return ""; }
  ulonglong table_flags() const { return 0; }
  ulong index_flags(uint inx, uint part, bool all_parts) const { return 0; }
  /* The following defines can be increased if necessary */
#define MEMEM_MAX_KEY MAX_KEY     /* Max allowed keys */
#define MEMEM_MAX_KEY_SEG 16      /* Max segments for key */
#define MEMEM_MAX_KEY_LENGTH 3500 /* Like in InnoDB */
  uint max_supported_keys() const { return MEMEM_MAX_KEY; }
  uint max_supported_key_length() const { return MEMEM_MAX_KEY_LENGTH; }
  uint max_supported_key_part_length() const { return MEMEM_MAX_KEY_LENGTH; }
  int open(const char *name, int mode, uint test_if_locked) { return 0; }
  int close(void) { return 0; }
  int truncate() { return 0; }
  int rnd_init(bool scan);
  int rnd_next(uchar *buf);
  int rnd_pos(uchar *buf, uchar *pos) { return 0; }
  int index_read_map(uchar *buf, const uchar *key, key_part_map keypart_map,
                     enum ha_rkey_function find_flag)
  {
    return HA_ERR_END_OF_FILE;
  }
  int index_read_idx_map(uchar *buf, uint idx, const uchar *key,
                         key_part_map keypart_map,
                         enum ha_rkey_function find_flag)
  {
    return HA_ERR_END_OF_FILE;
  }
  int index_read_last_map(uchar *buf, const uchar *key,
                          key_part_map keypart_map)
  {
    return HA_ERR_END_OF_FILE;
  }
  int index_next(uchar *buf) { return HA_ERR_END_OF_FILE; }
  int index_prev(uchar *buf) { return HA_ERR_END_OF_FILE; }
  int index_first(uchar *buf) { return HA_ERR_END_OF_FILE; }
  int index_last(uchar *buf) { return HA_ERR_END_OF_FILE; }
  void position(const uchar *record) { return; }
  int info(uint flag) { return 0; }
  int external_lock(THD *thd, int lock_type) { return 0; }
  int create(const char *name, TABLE *table_arg, HA_CREATE_INFO *create_info);
  THR_LOCK_DATA **store_lock(THD *thd, THR_LOCK_DATA **to,
                             enum thr_lock_type lock_type)
  {
    return to;
  }
  int delete_table(const char *name) { return 0; }

private:
  void reset_memem_table();
  virtual int write_row(const uchar *buf);
  int update_row(const uchar *old_data, const uchar *new_data)
  {
    return HA_ERR_WRONG_COMMAND;
  };
  int delete_row(const uchar *buf) { return HA_ERR_WRONG_COMMAND; }
};

A complete storage engine might seriously implement all of these methods. But we'll only seriously implement 7 of them.

To finish up the boilerplate, we'll switch over to ha_memem.cc and set up the includes.

/* Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved.

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; version 2 of the License.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */

#ifdef USE_PRAGMA_IMPLEMENTATION
#pragma implementation // gcc: Class implementation
#endif

#define MYSQL_SERVER 1
#include <my_global.h>
#include "sql_priv.h"
#include "unireg.h"
#include "sql_class.h"

#include "ha_memem.h"

Ok! Let's dig into the implementation.

Implementation

The global database

First up, we need to declare a global MememDatabase* instance. We'll also implement a helper function for finding the index of a table by name within the database.

// WARNING! All accesses of `database` in this code are thread
// unsafe. Since this was written during a hack week, I didn't have
// time to figure out MySQL/MariaDB's runtime well enough to do the
// thread-safe version of this.
static MememDatabase *database;

static int memem_table_index(const char *name)
{
  int i;
  assert(database->tables.size() < INT_MAX);
  for (i= 0; i < (int) database->tables.size(); i++)
  {
    if (strcmp(database->tables[i]->name->c_str(), name) == 0)
    {
      return i;
    }
  }

  return -1;
}

As I wrote this post I noticed that this code also assumes there's only a single database. That isn't how MySQL works. Everytime you call USE ... in MySQL you are switching between databases. You can query tables across databases. A real in-memory backend would need to be aware of the different databases, not just different tables. But to keep the code succinct we won't implement that in this post.

Next we'll implement plugin initialization and cleanup.

Plugin lifecycle

Before we register the plugin with MariaDB, we need to set up initialization and cleanup methods for it.

The initialization method will take care of initializing the global MememDatabase* database object. It will set up a handler for creating new instances of our handler subclass. And it will set up a handler for deleting tables.

static handler *memem_create_handler(handlerton *hton, TABLE_SHARE *table,
                                     MEM_ROOT *mem_root)
{
  return new (mem_root) ha_memem(hton, table);
}

static int memem_init(void *p)
{
  handlerton *memem_hton;

  memem_hton= (handlerton *) p;
  memem_hton->db_type= DB_TYPE_AUTOASSIGN;
  memem_hton->create= memem_create_handler;
  memem_hton->drop_table= [](handlerton *, const char *name) {
    int index= memem_table_index(name);
    if (index == -1)
    {
      return HA_ERR_NO_SUCH_TABLE;
    }

    database->tables.erase(database->tables.begin() + index);
    DBUG_PRINT("info", ("[MEMEM] Deleted table '%s'.", name));

    return 0;
  };
  memem_hton->flags= HTON_CAN_RECREATE;

  // Initialize global in-memory database.
  database= new MememDatabase;

  return 0;
}

The DBUG_PRINT macro is a debug helper MySQL/MariaDB gives us. As noted above, the output is directed to a file specified by the --debug flag. Unfortunately I couldn't figure out how to flush the stream this macro writes to. It seemed like occasionally when there was a segfault logs I expected to be there weren't there. And the file would often contain what looked like partially written logs. Anyway, as long as there wasn't a segfault the debug file will eventually contain the DBUG_PRINT logs.

The only thing the plugin cleanup function must do is delete the global database.

static int memem_fini(void *p)
{
  delete database;
  return 0;
}

Now we can register the plugin!

Plugin registration

The maria_declare_plugin and maria_declare_plugin_end register the plugin's metadata (name, version, etc.) and callbacks.

struct st_mysql_storage_engine memem_storage_engine= {
    MYSQL_HANDLERTON_INTERFACE_VERSION};

maria_declare_plugin(memem){
    MYSQL_STORAGE_ENGINE_PLUGIN,
    &memem_storage_engine,
    "MEMEM",
    "MySQL AB",
    "In-memory database.",
    PLUGIN_LICENSE_GPL,
    memem_init, /* Plugin Init */
    memem_fini, /* Plugin Deinit */
    0x0100 /* 1.0 */,
    NULL,                          /* status variables                */
    NULL,                          /* system variables                */
    "1.0",                         /* string version */
    MariaDB_PLUGIN_MATURITY_STABLE /* maturity */
} maria_declare_plugin_end;

That's it! Now we need to implement methods for writing rows, reading rows, and creating a new table.

Create table

To create a table, we make sure one by this name doesn't already exist, make sure it only has INTEGER fields, allocate memory for the table, and append it to the global database.

int ha_memem::create(const char *name, TABLE *table_arg,
                     HA_CREATE_INFO *create_info)
{
  assert(memem_table_index(name) == -1);

  // We only support INTEGER fields for now.
  uint i = 0;
  while (table_arg->field[i]) {
    if (table_arg->field[i]->type() != MYSQL_TYPE_LONG)
      {
    DBUG_PRINT("info", ("Unsupported field type."));
    return 1;
      }

    i++;
  }

  auto t= std::make_shared<MememTable>();
  t->name= std::make_shared<std::string>(name);
  database->tables.push_back(t);
  DBUG_PRINT("info", ("[MEMEM] Created table '%s'.", name));

  return 0;
}

Not very complicated. Let's handle INSERT-ing rows next.

Insert row

There is no method called when an INSERT starts. There is a table field on the handler parent class that is updated though when a SELECT or INSERT is going. So we can fetch the current table from that field.

Since we have a slot for a std::shared_ptr<MememTable> memem_table on the ha_memem class, we can check if it is NULL when we insert a row. If it is, we look up the current table and set this->memem_table to its MememTable.

But there's a bit more to it than just the table name. The const char* name passed to the create() method above seems to be a sort of fully qualified name for the table. By observation, when creating a table y in a database test, the const char* name value is ./test/y. The . prefix probably means that the database is local, but I'm not sure.

So we'll write a helper method that will reconstruct the fully qualified table name before looking up that fully qualified table name in the global database.

void ha_memem::reset_memem_table()
{
  // Reset table cursor.
  current_position= 0;

  std::string full_name= "./" + std::string(table->s->db.str) + "/" +
                         std::string(table->s->table_name.str);
  DBUG_PRINT("info", ("[MEMEM] Resetting to '%s'.", full_name.c_str()));
  assert(database->tables.size() > 0);
  int index= memem_table_index(full_name.c_str());
  assert(index >= 0);
  assert(index < (int) database->tables.size());

  memem_table= database->tables[index];
}

Then we can use this within write_row to figure out the current MememTable being queried.

But first, let's digress into how MySQL stores rows.

The MySQL row API

When you write a Postgres custom storage API, you are expected to basically read from or write to an array of Datum.

Totally sensible.

In MySQL, you read from and write to an array of bytes. That's pretty weird to me. Of course you can build your own higher level serialization/deserialization on top of it. But it's just strange to me everyone has to know this basically opaque API.

Certainly it's documented.

The handler class is the interface for dynamically loadable
storage engines. Do not add ifdefs and take care when adding or
changing virtual functions to avoid vtable confusion

Functions in this class accept and return table columns data. Two data
representation formats are used:
1. TableRecordFormat - Used to pass [partial] table records to/from
   storage engine

2. KeyTupleFormat - used to pass index search tuples (aka "keys") to
   storage engine. See opt_range.cc for description of this format.

TableRecordFormat
=================
[Warning: this description is work in progress and may be incomplete]
The table record is stored in a fixed-size buffer:

  record: null_bytes, column1_data, column2_data, ...

The offsets of the parts of the buffer are also fixed: every column has 
an offset to its column{i}_data, and if it is nullable it also has its own
bit in null_bytes.

In our implementation, we'll skip the support for NULL values. We'll only support INTEGER fields. But we still need to be aware that the first byte will be taken up. We'll also assume there won't be more than one byte of a NULL bitmap.

It is this opaque byte array that we'll read from in write_row(const uchar* buf) and write to in read_row(uchar* buf).

Insert row (take two)

To keep things simple we're going to store the row in MememTable the same way MySQL passes it around.

int ha_memem::write_row(const uchar *buf)
{
  if (memem_table == NULL)
  {
    reset_memem_table();
  }

  // Assume there are no NULLs.
  buf++;

  uint field_count = 0;
  while (table->field[field_count]) field_count++;

  // Store the row in the same format MariaDB gives us.
  auto row= std::make_shared<std::vector<uchar>>(
      buf, buf + sizeof(int) * field_count);
  memem_table->rows.push_back(row);

  return 0;
}

Which makes reading the row quite simple too!

Read row

The only slight difference between reading and writing a row is that MySQL/MariaDB will tell us when the SELECT scan for a table starts.

We'll use that opportunity to reset the current_row cursor and reset the memem_table field. Since, again, handler classes are only used once per query but they are reused for queries running at other times.

int ha_memem::rnd_init(bool scan)
{
  reset_memem_table();
  return 0;
}

int ha_memem::rnd_next(uchar *buf)
{
  if (current_position == memem_table->rows.size())
  {
    // Reset the in-memory table to make logic errors more obvious.
    memem_table= NULL;
    return HA_ERR_END_OF_FILE;
  }
  assert(current_position < memem_table->rows.size());

  uchar *ptr= buf;
  *ptr= 0;
  ptr++;

  // Rows internally are stored in the same format that MariaDB
  // wants. So we can just copy them over.
  std::shared_ptr<std::vector<uchar>> row= memem_table->rows[current_position];
  std::copy(row->begin(), row->end(), ptr);

  current_position++;
  return 0;
}