People connecting to sites hosted on exe.dev are contacting a proxy server that routes the connection to the correct VM. Routing depends on details about the connection, such as the HTTP Host header or an SSH public key. It also depends on details of exe.dev internal network, such as where the VM is running and how to access it. These details are, naturally, stored in a database.
exe.dev proxies run all over the world. We don’t want every incoming connection to have to check with a single centralized database; that would introduce unnecessary slowness. We also don’t want to replicate the entire database to every proxy; most of the information in the database is irrelevant to the proxy, and some of it is potentially sensitive, such as links to billing information.
The natural approach is for the proxy to cache the information that it needs. The first time somebody uses a particular proxy to contact a particular VM, we do a slow query of the centralized database. After that, each subsequent connection is handled out of a local cache.
Of course, information changes over time. People can change the sharing status of their VMs, VMs can move to different hosts, and in general the routing information that the proxy is using can change. So while using a cache is efficient, it means that we have to handle what is notoriously one of the two hard problems of computer systems: cache invalidation (the other hard problem is naming; also, off-by-one errors).
sqlc
Before we tackle cache invalidation, let’s back up and discuss database access.
Our code is written in Go, and our database access uses the excellent sqlc tool. The sqlc tool is a code generator that parses SQL commands and generates type-safe functions to execute those commands. This brings the advantage of compile-time static type checking to the dynamically typed SQL language. The sqlc tool understands how to parse SQL statements for various databases. For every database operation, it generates a type-safe function that performs the operation. At exe, all of our database access goes through functions generated by sqlc.
Table and Row Information
Given that we are already using tooling for database access, it was a small extension to that tooling to support cache invalidation. We tweaked our copy of sqlc to emit additional code in each generated function.
In a function that reads from the database, we record a mapping from a database table name to the field/value pairs used to select rows from the table. The mapping is stored in the Go context value, so that it accumulates across a set of database operations that share a context.
In a function that writes to the database, we call a user-supplied function for each write operation, again passing a mapping from a database table name to the field/value pairs used to select rows from the table. We don’t record the changed fields, we only record the fields used to select the row (in SQL terms, this is the WHERE clause). We only call the function when the transaction is committed.
Cache Invalidation
When a proxy needs information that isn’t cached locally, it contacts the central database. During this operation it records the database tables and rows that are accessed. Because this is done via the sqlc generated code and the Go context value, there is no need for the code to know ahead of time what database information is relevant, and the recorded information is always accurate even as the program changes or the database is rearranged. We record the table and row information in a cache invalidation data structure.
All database changes, wherever they originate, go through a single writer process to reach the database. That is the one we instrument via sqlc. The sqlc hooks check the cache invalidation data structure. If the write affects a table that some cache depends upon, we send a cache invalidation message to all proxies that accessed the data. The message includes the fields and values used to select the row.
When the proxy receives the message, it knows the database table that was modified, and the field values used to select the row. That is enough information to clear the cache elements that may have been modified. We don’t attempt to be precise about modification. If some field changed for a particular VM, we simply discard all cached information for that VM. The proxy will refetch the data from the central database when and if it is needed.
For example, a proxy may need information about the VM with ID 789. It will ask the centralized database for that information, which will send all relevant information about the VM, including the ID and owner and routing information. The database server will record that the proxy got information from the VM database table. Later something about that VM may change, perhaps because we are changing all information about VMs owned by the user baz. The writer process will see that the table changed, and send a notification to the proxy saying that a VM owned by baz changed. The proxy, which knows the ID and owner of all VM information it has cached, will discard from the cache all information about VMs owned by baz.
This approach automatically detects the information that is cached, and automatically detects the cases where the cached information may be out of date. That is enough for reliable cache invalidation, and reliable VM routing.