Full Width [alt+shift+f] Shortcuts [alt+shift+k]
Sign Up [alt+shift+s] Log In [alt+shift+l]
30

Writing a minimal in-memory storage engine for MySQL/MariaDB

from Notes on software development [alt+shift+b] in technology

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....
9th Jan 2024

Stay updated

Get a weekly newsletter with the top 5 articles worth reading every week.

More from Notes on software development

Transactions are a protocol

Transactions are not an intrinsic part of a storage system. Any storage system can be made transactional: Redis, S3, the filesystem, etc. Delta Lake and Orleans demonstrated techniques to make S3 (or cloud storage in general) transactional. Epoxy demonstrated techniques to make Redis (and any other system) transactional. And of course there's always good old Two-Phase Commit. If you don't want to read those papers, I wrote about a simplified implementation of Delta Lake and also wrote about a simplified MVCC implementation over a generic key-value storage layer. It is both the beauty and the burden of transactions that they are not intrinsic to a storage system. Postgres and MySQL and SQLite have transactions. But you don't need to use them. It isn't possible to require you to use transactions. Many developers, myself a few years ago included, do not know why you should use them. (Hint: read Designing Data Intensive Applications.) And you can take it even further by ignoring the transaction layer of an existing transactional database and implement your own transaction layer as Convex has done (the Epoxy paper above also does this). It isn't entirely clear that you have a lot to lose by implementing your own transaction layer since the indexes you'd want on the version field of a value would only be as expensive or slow as any other secondary index in a transactional database. Though why you'd do this isn't entirely clear (I will like to read about this from Convex some time). It's useful to see transaction protocols as another tool in your system design tool chest when you care about consistency, atomicity, and isolation. Especially as you build systems that span data systems. Maybe, as Ben Hindman hinted at the last NYC Systems, even proprietary APIs will eventually provide something like two-phase commit so physical systems outside our control can become transactional too. Transactions are a protocol short new post pic.twitter.com/nTj5LZUpUr — Phil Eaton (@eatonphil) April 20, 2025

20th Apr 2025 • 54 votes
Phil Eaton on Technical Blogging

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

25th Mar 2025 • 77 votes
From web developer to database developer in 10 years

Last month I completed my first year at EnterpriseDB. I'm on the team that built and maintains pglogical and who, over the years, contributed a good chunk of the logical replication functionality that exists in community Postgres. Most of my work, our work, is in C and Rust with tests in Perl and Python. Our focus these days is a descendant of pglogical called Postgres Distributed which supports replicating DDL, tunable consistency across the cluster, etc. This post is about how I got here. Black boxes I was a web developer from 2014-2021†. I wrote JavaScript and HTML and CSS and whatever server-side language: Python or Go or PHP. I was a hands-on engineering manager from 2017-2021. I was pretty clueless about databases and indeed database knowledge was not a serious part of any interview I did. Throughout that time (2014-2021) I wanted to move my career forward as quickly as possible so I spent much of my free time doing educational projects and writing about them on this blog (or previous incarnations of it). I learned how to write primitive HTTP servers, how to write little parsers and interpreters and compilers. It was a virtuous cycle because the internet (Hacker News anyway) liked reading these posts and I wanted to learn how the black boxes worked. But I shied away from data structures and algorithms (DSA) because they seemed complicated and useless to the work that I did. That is, until 2020 when an inbox page I built started loading more and more slowly as the inbox grew. My coworker pointed me at Use The Index, Luke and the DSA scales fell from my eyes. I wanted to understand this new black box so I built a little in-memory SQL database with support for indexes. I'm a college dropout so even while I was interested in compilers and interpreters earlier in my career I never dreamed I could get a job working on them. Only geniuses and PhDs did that work and I was neither. The idea of working on a database felt the same. However, I could work on little database side projects like I had done before on other topics, so I did. Or a series of explorations of Raft implementations, others' and my own. Startups From 2021-2023 I tried to start a company and when that didn't pan out I joined TigerBeetle as a cofounder to work on marketing and community. It was during this time I started the Software Internals Discord and /r/databasedevelopment which have since kind of exploded in popularity among professionals and academics in database and distributed systems. TigerBeetle was my first job at a database company, and while I contributed bits of code I was not a developer there. It was a way into the space. And indeed it was an incredible learning experience both on the cofounder side and on the database side. I wrote articles with King and Joran that helped teach and affirm for myself the basics of databases and consensus-based distributed systems. Holding out When I left TigerBeetle in 2023 I was still not sure if I could get a job as an actual database developer. My network had exploded since 2021 (when I started my own company that didn't pan out) so I had no trouble getting referrals at database companies. But my background kept leading hiring managers to suggest putting me on cloud teams doing orchestration in Go around a database rather than working on the database itself. I was unhappy with this type-casting so I held out while unemployed and continued to write posts and host virtual hackweeks messing with Postgres and MySQL. I started the first incarnation of the Software Internals Book Club during this time, reading Designing Data Intensive Applications with 5-10 other developers in Bryant Park. During this time I also started the NYC Systems Coffee Club. Postgres After about four months of searching I ended up with three good offers, all to do C and Rust development on Postgres (extensions) as an individual contributor. Working on extensions might sound like the definition of not-sexy, but Postgres APIs are so loosely abstracted it's really as if you're working on Postgres itself. You can mess with almost anything in Postgres so you have to be very aware of what you're doing. And when you can't mess with something in Postgres because an API doesn't yet exist, companies have the tendency to just fork Postgres so they can. (This tendency isn't specific to Postgres, almost every open-source database company seems to have a long-running internal fork or two of the database.) EnterpriseDB Two of the three offers were from early-stage startups and after more than 3 years being part of the earliest stages of startups I was happy for a break. But the third offer was from one of the biggest contributors to Postgres, a 20-year old company called EnterpriseDB. (You can probably come up with different rankings of companies using different metrics so I'm only saying EnterpriseDB is one of the biggest contributors.) It seemed like the best place to be to learn a lot and contribute something meaningful. My coworkers are a mix of Postgres veterans (people who contributed the WAL to Postgres, who contributed MVCC to Postgres, who contributed logical decoding and logical replication, who contributed parallel queries; the list goes on and on) but also my developer-coworkers are people who started at EnterpriseDB on technical support, or who were previously Postgres administrators. It's quite a mix. Relatively few geniuses or PhDs, despite what I used to think, but they certainly work hard and have hard-earned experience. Anyway, I've now been working at EnterpriseDB for over a year so I wanted to share this retrospective. I also wanted to cover what it's like coming from engineering management and founding companies to going back to being an individual contributor. (Spoiler: incredibly enjoyable.) But it has been hard enough to make myself write this much so I'm calling it a day. :) I wrote a post about the winding path I took from web developer to database developer over 10 years. pic.twitter.com/tf8bUDRzjV — Phil Eaton (@eatonphil) February 15, 2025 † From 2011-2014 I also did contract web development but this was part-time while I was in school.

15th Feb 2025 • 57 votes
Logical replication in Postgres: Basics

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

17th Jan 2025 • 95 votes
Picking up volleyball in NYC with Goodrec and New York Urban

I was so intimidated to go at first, but it is in fact easy and fun to start playing beginner volleyball in New York. The people are so friendly and welcoming that it has been easy to keep playing consistently every week since I started for the first time this August. It's been a great workout and a great way to make friends! The two platforms I've used to find volleyball games are Goodrec and New York Urban. While these platforms may also offer classes and leagues, I mostly use them to play "pickup" games. Pickup games are where you show up and join (or get assigned to) a team to play for an hour or two. Easy to go on your own or with friends. I'm not an expert! My only hope with this post is that maybe it makes trying out volleyball in New York feel a little less intimidating for you! Goodrec With Goodrec you have to use their mobile app. Beginner tier is called "social" on Goodrec. So browse available games until you find one at the level you want to play. You enroll in (buy a place in) sessions individually. Sessions are between 90-120 minutes long. They ask you not to arrive more than 10 minutes early at the gym. When you arrive you tell the gym managers (usually in a desk up front somewhere) you're there for Goodrec and the tier (in case the gym has multiple level games going on at the same time). Then you wait until the Goodrec "host" arrives and they will organize everyone into teams. Goodrec hosts are players who volunteer to organize the games. They'll explain the rules of the game (makes Goodrec very good for beginners) and otherwise help you out. Always say thank you to your host! New York Urban With New York Urban, pickup sessions are called "open play". There is no mobile app, you just use the website to purchase a spot in a session. The sessions are longer and cheaper than Goodrec. But there is no host; players self-organize. The options are more limited too. You play at one of four high schools on either a Friday night or on Sunday. And session slots tend to sell out much more quickly than with Goodrec. Big City Volleyball You can also check out Big City Volleyball but I haven't used it yet. Volo I haven't ever done Volo but I think I've heard it described as "beer league". That even some of the beginner tier sessions with Goodrec and New York Urban are more competitive. But also, Volo is built around leagues so you have to get the timing right. Goodrec's and New York Urban's pickup games make it easy to get started playing any time of year. Making friends It was super awkward to go at first! I went by myself. I didn't know what I was doing. I couldn't remember, and didn't know, many rules. I didn't have court shoes or knee pads. But the Goodrec host system is particularly great for bringing beginners in and making them feel welcome. You have a great time even if you're terrible. The first game I went to, I tried to hang out afterward to meet people. But people either came with their SO or with their friends or by themselves so they all just left immediately or hung out in their group. So you can't just go once and expect to make friends immediately. But if you keep going at the same place and time regularly week over week, you'll see familiar faces. Maybe half the people I play with each week are regulars. If you're friendly you'll start making friends with these people and eventually start going out to bars with them after the games. Improving Even if you find yourself embarrassingly bad at first, just keep going! I'm 29, 6'1, 190lbs and from observation the past 5 months, age, height, and weight have a very indirect relation to playing ability. Most of the people who play are self-taught, especially at the lower tiers I've played at. But some people played for the school team in high school or college. These people are fun to play with and you can learn a lot from them. Most people who are self-taught seem to watch YouTube videos like Coach Donny, helpful for learning how to serve, set, block, etc. Or they take "clinics" (classes) with Goodrec or other platforms. (I have no idea about these, I've never done them before.) At first I played 2 hours a week and I was completely exhausted after the session. Over time it got easier so I started playing 2-3 sessions a week (6-9-ish hours). With practice and consistency (after about 3-4 months), I started playing Intermediate tier with Goodrec and New York Urban. And I don't think I'll play Beginner/Social at all anymore. I still primarily play for fun and for the workout and to meet people. But it's also fun to get better! I played with one person much better than myself in an Intermediate session one time and he mentioned he will probably stop playing Intermediate and only play High Intermediate. He mentioned you get better when you keep pushing yourself to play with better and better players. Good advice!

26th Dec 2024 • 80 votes

More in technology

FLIP Fluid on Flip Dots

[Hardware] Electromechanical Fluid Simulation

4 hours ago • 1 votes
Is This A Joke? In The Auth Header? (F5 BIG-IP UnAuth Heap-Overflow to RCE CVE-2026-94127)

Well, well, well, well, well, well, well, well, well, well, well, well, well, well, well. We're back. Sorry. We've been watching the onslaught of vulnerabilities flood the internet. Every man, dog, and their grandmas (apparently?) are now using LLMs to find and reproduce vulnerabilities - it’

20 hours ago • 1 votes
The Reason You Prohibit Things

You want less of them. That’s the reason. You may find that it’s too hard to stop people from doing the thing, literally blood, sweat, and tears trying to prosecute people, but that’s a different thing.

22 hours ago
Solitaire Alone Together

Solitaire Alone Together I made a new game. It's called Solitaire Alone Together. It's Windows 98 solitaire, but you can play with everyone else on the internet. Read the full post on my blog! Here's a raw link, if you need it: https://eieio.games/blog/solitaire-alone-together

3 days ago • 1 votes
All The Ways I Broke My Website

This post is a living diary of all the times I messed up something with my website in a funny way. I value those who have the confidence to own their mistakes and share the learning with others, and so this is me doing just that! That Time I Accidentally Made a Tarpit That Time I Accidentally Made Really Large Headers That Time I Accidentally Made a Tarpit Back to Top A "tarpit" is an unofficial term used in computing to describe an intentionally slow response to a request. In these modern times many people are using tarpits as a way to combat the relentless theft of data by AI companies, although there's little to no evidence of that actually being in any way effective. I don't use tarpits, at least not intentionally, but there was that one time when I accidentally created a tarpit and trapped all visitors in it. As I've shared previously, I refuse connections from IP addresses that are blocked or belong to a blocked subnet, and I enforce this firewall during the TCP handshake. The logic here is straightforward: there's no reason to waste resources doing a TLS handshake, accepting an HTTP request, and then rejecting the connection if I already know I'm going to reject it at the earliest step. At the time, the code worked like this: the HTTP server would repeatedly call the Accept() function below expecting a new connection. I've added some comments to help explain the logic. func (l *firewallListener) Accept() (net.Conn, error) { // Accept the connection from the TCP listener. This blocks until there is a connection to accept or the listner was closed. conn, err := l.l.AcceptTCP() if err != nil { return conn, err } // Separate the IP address out from the remote address (which includes the port) ip := utils.SocketStringToIPAddress(conn.RemoteAddr().String()) if ip == nil { return nil, nil } // Check if it's blocked, if so close the connection and return a refuseError if IsBlocked(ip, true) { conn.Close() return nil, &refuseError{} } // Otherwise return the connection on to the HTTP server return conn, nil } If the incoming connection was from a blocked IP then I'd return a refuseError. I need to use a specific error interface because the HTTP server will halt if it encounters a non-temporary error from the call to Accept(), so I need to return an error that satisfies the definition of a temporary error. I defined refuseError like this: type refuseError struct{} func (e *refuseError) Error() string { return "." } func (e *refuseError) Timeout() bool { return true } func (e *refuseError) Temporary() bool { return true } func (e *refuseError) Is(err error) bool { return err == context.DeadlineExceeded } This did accomplish the goal of rejecting connections before the TLS handshake for blocked addresses, but it had one really unintended and difficult to track down side-effect. Accepting connections is done serially, after which servers typically then process that request on a dedicated thread (or in Go's case a goroutine). This means that any delays during the accept loop will block all incoming connection. What I had missed while reviewing the code for Go's HTTP server is that when it receives a temporary error from Accept() is that while it doesn't abort, it does sleep for up to a maximum of 1 second. This sleep blocks the entire server for all incoming connections. You can see a trimmed copy of the code that does this below, with some marks I've added which I will explain. // src/net/http/server.go // Copyright 2009 The Go Authors. All rights reserved. // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. for { // (1) rw, err := l.Accept() if err != nil { if s.shuttingDown() { return ErrServerClosed } // (2) if ne, ok := err.(net.Error); ok && ne.Temporary() { if tempDelay == 0 { tempDelay = 5 * time.Millisecond } else { tempDelay *= 2 } if max := 1 * time.Second; tempDelay > max { tempDelay = max } s.logf("http: Accept error: %v; retrying in %v", err, tempDelay) // (3) time.Sleep(tempDelay) continue } return err } connCtx := ctx if cc := s.ConnContext; cc != nil { connCtx = cc(connCtx, rw) if connCtx == nil { panic("ConnContext returned nil") } } tempDelay = 0 c := s.newConn(rw) c.setState(c.rwc, StateNew, runHooks) // before Serve can return // (4) go c.serve(connCtx) } At mark 1 the server calls the Accept() function, this is the exact function that I defined above where I might return a temporary error. At mark 2 it checks if an error was returned, and if so if that error is temporary. If there was a temporary error, at mark 3 it sleeps for an increasing amount of time up-to 1 second, otherwise, at mark 4 it processes the connection on a dedicated goroutine, which allows the server to accept the next connection. I'm not entirely sure why the Go developers added this sleep delay and the change when it was introduced doesn't provide any meaningful insight. Regardless, it caused significant latency connecting to my website when a flood of rejected requests was coming in. It just goes to show how important it is to write meaningful commit messages, because you never know when somebody might come back years later wondering "why was this done?". I sure home I don't come to eat those words later. Coincidentally, you can actually see this happening if you look carefully at one of the metric graphs I shared in my first post about my server's security model: Securing My Web Infrastructure. This is the graph I shared in that blog post and while I didn't know it at the time, the fact that these request spikes all cap-out at around 60 requests per minute was not a coincidence. These requests were not being made with a limit in mind, attackers rarely ever care about things like that, instead it the accidental tarpit I had created. The downside to this was that while the malicious requests were being rate-limited, all requests were being rate-limited, up to a point of taking so long they timed out. The Fix Fixing the issue was relatively straightforward enough. Instead of returning a temporary error to the HTTP server during the accept loop, just don't return anything at all and wait for the next valid connection. func (l *firewallListener) Accept() (net.Conn, error) { for { conn, err := l.l.AcceptTCP() if err != nil { return conn, err } ip := utils.SocketStringToIPAddress(conn.RemoteAddr().String()) if ip == nil { return nil, nil } if IsBlocked(ip, true) { conn.SetLinger(0) conn.Close() continue } return conn, nil } } Now, when the HTTP server calls Accept(), the only time it returns is with a connection from an IP that isn't blocked, or if there genuinely is an error. No more sleep delays, no more excessive timeouts. That Time I Accidentally Made Really Large Headers Back to Top For about 10 years now all major browsers have support for a security feature known as a Content Security Policy or CSP. A CSP is an HTTP header provided by the server that instructs the browser on where it can load assets from, this could be scripts, images, stylesheets, fonts, etc. The objective of using a CSP is to prevent against injected HTML that tries to load assets, such as a malicious Javascript file, from a remote source. With so much user-provided content being available online, it's very possible for this to happen without an attacker compromising the entire web server. CSP protects against that by saying "scripts can only be loaded from these domains". That's a really simplified way of looking at it, anyways. My web server supports injecting the CSP header automatically, but before I go on I need to explain a little bit about the structure of my web server. When an incoming HTTP request is accepted (having passed all firewall checks and assertions), we look at the destination host for the request. This can either be the value of the Host header or as specified during the TLS handshake. We then look at a map of hosts to apps. Apps are just an interface that accept a few methods: type App interface { Cleanup() ReloadConfig() ServeHTTP(rw http.ResponseWriter, r *http.Request) Setup(dataDir string) error Shutdown() } One of the apps is the Proxy app, which is a reverse proxy - it accepts the incoming HTTP request and then proxies it on to another host. This is a very common design, especially with increasingly complex TLS setups. Because each app is unique to a host, and different hosts have different requirements for CSP rules, the proxy app includes a CSP preset that we use to build the header value, or skip it entirely. When the proxy app was going to copy an HTTP request to the downstream host, it would build the CSP header, however there was a slight bug... func (a *App) ServeHTTP(rw http.ResponseWriter, inRequest *ht2.Request) { // --snip -- if a.CSP != nil { a.CSP.ConnectSrc += " " + inRequest.Origin } CopyHttpRequest(inRequest, outRequest, rw, CopyHttpRequestOptions{ Origin: inRequest.Origin, Csp: a.CSP, Cors: a.CORS, AddHeaders: !a.SkipHeaders, UseHTTP3: a.UseHTTP3, InsecureTLS: a.InsecureTLS, }) } I'm really unsure as to what I was doing with the line to append to the ConnectSrc, but the impact is that I'm appending to a variable that lives on the App, rather than a variable that is per-request. This meant that every time there was a request to the app, any request at all, the origin would be appended to the header value. This went on for quite a long time unnoticed and unresolved, largely because I am constantly tweaking and tinkering with my web server, after all, it's how I made having a website fun again. Each time I restarted the server process, the header value would be reset, but only for it to continue to grow and grow. Eventually, after a period of being busy with other matters, the server process stayed running for long enough that the header value grew too large and HTTP clients began to reject it. There is no defined maximum for an HTTP header value, however most HTTP clients use 100KiB, which is perfectly reasonable, and this header value would continue to grow well beyond that. Diagnosing this issue turned out to be difficult as tools like Curl would fail with errors relating to entities being too large, but stopped short of saying what specifically. I eventually used openssl s_client to send an HTTP request by hand and observed my terminal window being filled with a domain name repeated thousands of times. Looking at the commit history, it was really unclear why I added the culprit lines of code. The commit message just says "Improved CSP support". It just goes to show how important it is to write - hey look it's those words I'm now having to eat! The Fix The fix was to just delete those three lines of code. Yup, it really was that simple, and fixing this bug actually made a larger positive impact than I had expected, as it was immediately clear when I fixed the bug by looking at outbound network bytes: So much traffic was being wasted on excessive header sizes. You might look at these mistakes I've made and think "wow, Ian, these are some obvious mistakes, I never would have made them!" to which I say "good for you!" with the utmost sarcasm and disdain. I enjoy making and refining software, and making anything means making mistakes along the way. Each time I make mistakes such as the ones above, I improve my skills of investigation, diagnosing, and repair. Skills that, judging by my peers in the industry, seemingly everyone is quickly willing to throw away because a robot does it "better" than you. Header Image: "Car accident on the Ffestiniog to Bala road. Nobody was hurt" by Geoff Charles, CC BY-SA 4.0, via Wikimedia Commons.

5 days ago
📚 BoredReading

You seem to be enjoying this.

Join free to unlock everything.

Create free account

Already have an account? Sign in