Graph database in C++: pages on disk

Intro

0:00 Hello and welcome back to episode two, where we're going to move smollerGraph's graph out of memory and into files on disk, as pages of fixed-size records. Let's begin with a quick look at where we're going to be by the end of the episode.

0:14 We load the animals into a folder on disk, once, as ten nodes and fifteen relationships. Then a second run of sg walks two hops down the food chain from that folder, and gets the clover and the wheat without reading the facts again.

0:29 On the website of the series, you can find more information about the project. The code is open source on GitHub, tagged at each step of each episode, so that you can follow along, and each episode has a page here, with its chapters and its code.

Last time

0:43 Now, before we get to today's work, let's quickly go over what we did last time. We looked at why graphs come up in so many places, and at how Neo4j and Kùzu keep a graph on disk. Neo4j has records that point at each other, and Kùzu has columns, with compressed sparse row adjacency. Then we wrote a throwaway graph in C++, which kept everything in vectors in memory, with each node's relationships beside it. It loaded the animals from a file of Cypher patterns, and walked two hops down the food chain to the clover and the wheat. We pinned that down with four tests, written with GoogleTest. And we said its three functions, Add node, Add relationship and Neighbours, would stay, while the vectors behind them would go. Today starts right where that left off, with those vectors.

Today

1:33 Today, we're going to move the graph onto disk. First, a bit of engineering we skipped last time: a Docker build, and GitHub Actions running it on each push, so that each step from here on is built and tested on a clean machine. Then a pager, which reads and writes a file in pages of four kilobytes. On top of it, files of fixed-size records, packed into those pages. Then the graph moves onto node and relationship records, behind the three functions from last time, so the tests can tell us whether anything broke. With that, a graph we load once can be walked by a later run, and we're going to read its records back, byte by byte. All right, let's get started with Docker, and a build on a clean machine.

Docker and CI

2:15 Docker builds a program inside a container, a small Linux system of its own, from a recipe called a Dockerfile, so the build doesn't depend on what's installed on the machine. Ours has three stages, each starting from the one before. The first, the toolchain, starts from Ubuntu twenty-four point oh four, and installs what we need to build with apt: the compilers in build essential, CMake, Ninja and certificates, which FetchContent needs to download GoogleTest over HTTPS. No install recommends keeps apt from adding packages we didn't ask for, and we delete apt's lists afterwards, so they don't sit in the image. The build stage copies our code into the image, and configures and builds it, in release mode this time. On Ubuntu, the compiler is GCC, where on my Mac it's Clang, so the code gets checked by a second compiler with its own warnings. And the test stage runs ctest, with output on failure, so a failing test prints what went wrong, and the build stops there. A dockerignore file keeps the build folder and git's own folder out of what Docker copies in. Then GitHub Actions runs that build for us, from a workflow file in dot github slash workflows. It runs on each push to main and on each pull request, and from a button on GitHub, which is what workflow dispatch means. Its job runs on an Ubuntu machine that GitHub provides, checks the repository out, and builds the test stage with Docker. So CI builds and tests the code with the commands you'd run on your own machine. And the README says how to run that build.

3:49 Dash dash target picks the stage to build, the test stage, and Docker builds the stages before it first. Progress plain prints each step's output as it runs. And no cache filter test runs the test stage again, even when Docker has it cached from before, as a cached stage doesn't run its tests at all. It downloads Ubuntu and the toolchain, which takes a minute the first time and is cached after that. Then it compiles our code with GCC, which gives no warnings either, and runs the four tests from last time, which all pass.

Pages

4:23 Before we write anything to disk, let's look at how SQLite, the database inside a lot of the apps we use, lays out its file. SQLite's file format says the main database file consists of one or more pages. Each page has the size the file's header gives it, a power of two from five hundred and twelve bytes to sixty-four kilobytes, and SQLite reads and writes the file a page at a time. Our files are going to work like that too, with pages of four kilobytes.

4:50 Our pages are going to be four kilobytes, and the reason is the hardware underneath. Modern disks store data in sectors of four kilobytes, and most file systems hand out space in blocks of that size too, so reading one of our pages is reading one block. On most systems, the operating system's memory pages are four kilobytes as well. On my Mac, which has an Apple chip, they're sixteen, so that's something we can measure later on. Bigger pages mean fewer reads when a query scans a lot of data, while smaller ones move less data for a single hop to a record. Graph walks hop between records all over a file, which suits smallish pages. So the page size is a single constant, and four kilobytes is where we start.

5:34 The pager goes in a header of its own, pager dot h. We include array, for a fixed-size array whose size is part of its type, and cstddef and cstdint for sizes and fixed-width integers, along with string, for errors. K page size is four thousand and ninety-six, the four kilobytes. It's an inline constexpr, which means a constant the compiler knows, defined once for the whole program, even though the header is included in many files. Its comment says why: it's the size of a block on most file systems and disks. A page id is a thirty-two bit number, and a Page is a standard array of four thousand and ninety-six bytes, of type standard byte, which is C++'s type for raw bytes that aren't characters or numbers. The Pager class holds a file of pages, read and written whole by their number, as its comment says. A default constructor makes a pager with no file yet. The destructor, with the tilde, runs when a pager goes away, and closes its file, so no file is left open by accident. We delete the copy constructor and copy assignment, with equals delete, as two pagers sharing one open file would close it twice. Next come the two functions that open a file, each returning whether it worked. Open opens a file at a path, given as a string, the way we'd type it. Its comment says it creates the file when it isn't there, and returns false with the reason in the error when it can't, the way Load facts does. Open temporary opens a file with no name, which is deleted once it's closed, for graphs that aren't meant to last, such as the ones in our tests. Page count says how many pages the file has. Read reads a page into a page we hand it, which has to exist, and Write writes one, and writing at the page count adds a page at the end. Inside, there's a private helper, Adopt, then the file descriptor, the small number the operating system gives us for an open file, starting at minus one for none, and the page count. In pager dot c c, we include three POSIX headers, the operating system's own interface on Linux and macOS: fcntl, for open, sys stat, for a file's size, and unistd, for reading, writing and closing. Then cerrno, cstdio, cstdlib and cstring, for the error number, printing, abort and the error's text. In an unnamed namespace, Fail prints what went wrong and stops the program. It's marked no return, so the compiler knows it doesn't come back. Its comment says why: a page that can't be read or written once the file is open leaves nothing sensible to carry on with. It prints to standard error with f print f, along with strerror of errno, the system's own description of the last error, such as no space left on the device. Then standard abort ends the program on the spot. In a database meant to run for months, we'd want something gentler, and for now, stopping keeps the code short. The destructor closes the file, if there is one. Open calls open with read and write access, and O CREAT, which creates the file with permissions six four four, readable by all and writable by us. Open temporary keeps its path in a character array, not a string, as mkstemp writes the name it picks into it. Mkstemp makes a file with a unique name from that template, replacing the six X's at its end, and then unlink removes the name right away. The comment says what that buys us: without a name, the file lasts as long as it's open. Adopt takes the file descriptor either one got, and asks fstat for the file's size. If either failed, it keeps the system's reason as the error, and closes what it opened. Otherwise, it closes any file the pager had before, keeps the new one, and works out the page count from the size. Read works out where its page starts, as its id times the page size, as an off t, the type for offsets in files. Pread reads at that offset, without moving a position in the file. Passing the offset in the call keeps two reads from getting in each other's way, which matters once there's more than one thread. It has to read a whole page, or we fail. Write works out its offset like Read does, and pwrite writes the whole page there, or we fail. And writing past the last page grows the page count. Both of them come down to one multiplication, the page's id times four thousand and ninety-six, to find where the page lives in the file. In CMake, pager dot c c joins the library, and pager test dot c c joins the tests. In pager test dot c c, the pager's header comes first, then cstdio, for removing a file, and string. The first test, Reads back what it wrote, opens a temporary pager, and assert true stops it right there if the file didn't open. Then it fills in a page of its own. The braces after Page make it start out as zeros, and we put forty-two in its first byte and seven in its last, so a page cut short at either end would show. It writes that page as page zero, and an empty page as page one, and checks that the pager counts two pages. Then it reads page zero into a fresh page, and checks the two are equal, byte for byte, as arrays compare each element. The second test, Keeps its pages in the file, uses a real file, in GoogleTest's temporary folder, and removes any left over from an earlier run, so the test starts clean. Inside braces, it opens a pager on that file, and writes a page with a one at byte a hundred. At the closing brace, the pager goes away, and its destructor closes the file. Then a second pager opens the file again, and has to find one page in it, with the one still at byte a hundred.

11:11 Let's build it, and run the tests, which are now four from last time and two for the pager, and all six of them pass.

Records in pages

11:19 Next, we pack records into those pages, and each record of a file is going to be one size. Ours are going to be thirty-two bytes, so a page holds four thousand and ninety-six divided by thirty-two, which is a hundred and twenty-eight of them. That makes a record's page its id divided by a hundred and twenty-eight, rounded down, plus one, as page zero is going to be a header that holds how many records there are. And its place in the page is the remainder, times thirty-two. So a record's id tells us where it is, without a search, which is what Neo4j relies on too.

11:55 Record file dot h holds the whole thing in a header, as it's a template. We include cstring, for copying bytes with memcpy, and type traits, for checking a type at compile time, along with our pager. A template is code written once for a type it's given later, so Record file of a node record and Record file of a relationship record are two classes the compiler writes for us from this one. The comment above it says what it is: a file of fixed-size records, packed into pages after a header page that holds how many there are. A record's id says which page it's on and where, so finding one needs no search. A static assert checks, at compile time, that a record is trivially copyable. That means its bytes are all there is to it, with no pointers to elsewhere, so copying it to and from a page as bytes is safe. K per page is the page size divided by the record's size, the hundred and twenty-eight we worked out. Open opens the pager on a file, and returns false when that fails, with the pager's error. Then it loads the count of records from the header, which we're going to write further down, and returns true. Open temporary does that with a temporary file instead. Count says how many records the file holds so far. Read is for a record that exists, which its comment says. It declares a page, four kilobytes that live as long as the function runs, reads the record's page into it, and copies the record's bytes out of it with memcpy, from its offset in the page. Write starts from a page of zeros, with the braces, and reads the record's page into it when that page is already in the file. Then it copies the record's bytes in at its offset, and writes the whole page back, as a page is the smallest thing we write. Append writes the record after the last one, adds one to the count, and writes the count into the first four bytes of a header page, so it's there the next time the file opens. Then it returns the new record's id to whoever appended it. At the bottom, in the private part, Page of and Offset of are the two formulas we just saw. They're static, as they need nothing from a particular file, just the id. The comment over them says why there's a plus one: page zero is the header, so the records start on page one. Offset of is the remainder, times the size of a record, in bytes from the start of the page. Each of them fits on a line or two, as integer division and its remainder do all the work. Those two short functions are where a record's id becomes a place on disk. Load count starts from zero, and when the file has pages, reads the header and copies the count out of its first four bytes. The pager and the count are the record file's two members. In CMake, the tests get a third file. Record file test includes our record file's header first, then cstdint, cstdio and string. It uses a small record of its own, Pair, a struct of two thirty-two bit numbers, eight bytes in all, so five hundred and twelve of them fit in a page. The first test, Appends across pages, opens a temporary record file of pairs, and assert true stops it if the file didn't open, as in the pager's tests. The loop's counter is a thirty-two bit number, like our ids. The comment says why the loop goes as far as it does: enough records to fill the first page and start a second. So the loop runs to k per page plus ten, appends a pair with designated initialisers for a and b, and checks that each append returns the next id. The expect inside the loop runs for each of the five hundred and twenty-two appends, and a failure would say which one went wrong. After the loop, it reads the last record, which sits on the second page, and checks its first number. And it checks that record three, back on the first page, has six as its second number. The second test, Keeps its count in the header, removes any file left over, and then, inside braces, opens a record file on a real file and appends two pairs. At the closing brace, the record file closes, along with its pager. Then it opens the file again, and checks that the count says two, which has to come from the header, and that record one, the second pair, reads back with three.

16:05 We build it again, and run the tests, now with two for the record file, and all eight of them pass.

The graph on disk

16:13 Now, let's look at the graph's own records. A node's record holds its name, and the id of the first of its outgoing relationships. For the red fox, that's relationship eleven, where it eats the field mouse. Each relationship's record holds the id of the next one from that node, so the fox's relationships form a chain, through ten, four and zero. The last one points at none, which ends the chain. A new relationship goes at the front, so adding one is a write to the relationship and a write to its node, however long the chain is. As far as I know, that's how Neo4j's record format adds them too, and it means the chain is newest first.

16:54 In graph dot h, the graph now includes our record file. K no relationship is the id at the end of a chain, the largest thirty-two bit number, which no real relationship gets. Node record is the node on disk: twenty-eight characters for its name, and the id of its first outgoing relationship, thirty-two bytes in all. Relationship record has twenty characters for its type, the two nodes it joins, and the next relationship from the node it starts at. Each struct has a comment over it, and the relationship's says that those next ids make a node's relationships form a chain. Two static asserts check that both are thirty-two bytes, so the compiler hasn't padded them. The class's comment says it keeps a graph in two files of records, one for nodes and one for relationships. Then, inside the class, come two constants, which are static, so they belong to the class and not to each graph. K max name and k max type are the longest names and types that fit, one less than their fields, as a zero marks where each one ends. The default constructor makes a graph in temporary files, which is what our tests and sg have been using without knowing it. Open puts the graph in a folder instead, creating it when it isn't there. Like the pager's Open, it returns false with the reason in the error when it can't. Add node, Add relationship, Find and Neighbours keep their signatures, and Add node's comment adds that a name has to fit, at most k max name bytes long. Name now returns a copy of the name, as it's read from a record. It's a single line, which reads the node's record and turns its characters into a string, up to the zero. The counts come from the two record files now. Inside, the two record files replace the vectors, one of node records and one of relationship records. And the hash map from names to ids stays, built from the node records when the graph opens, which its comment says. In graph dot c c, we include algorithm, for reverse and min, cstdio and cstdlib for stopping with an error, cstring, and filesystem and system error, for making folders. Copy field copies text into a fixed-size field, padded with zeros, and cut short if it's too long. It's a template on the field's size, N, and it takes the field as a reference to an array, so the template can see how big the field is, which a plain pointer would lose. Memset fills the field with zeros, and memcpy copies the text over them, at most one byte short of the field. It's in an unnamed namespace, as nothing outside this file needs it. So it works for names and types alike, and its comment says the field always ends in a zero. Cutting a name short is a last resort, as Load facts is going to refuse names that are too long before they get this far. Then the constructor, for a graph with no folder, opens two temporary files, and if the system can't give us any, it stops with a message. A constructor can't return an error, and without its files there's no graph to speak of. Open creates the folder, with an error code, as the style guide doesn't use the exceptions standard filesystem throws otherwise. Then it opens a nodes file and a relationships file in it, and if either fails to open, Open returns false with that file's error. There's no index on names yet, so it reads each node record to fill in the map, which its comment says. Reading each node at open is quick for our ten, and we're going to see what it costs later on. Add node returns the node when Find knows it. Otherwise, it fills in a node record with the name and no relationships, appends it, and keeps its id in the map. Add relationship reads the node it starts from first, as it needs that node's current first relationship. Then it fills in a relationship record with the type and the two nodes. The type goes through Copy field, like the name did, and from and to are the ids we were given. The new relationship's next is the node's old first, and the comment over that line says what it buys us: adding one takes two writes, however long the chain is. Then the node's first becomes the new relationship, appended to its file, which puts it at the front of the chain, and the node's record is written back with it. Those two lines are all it takes to put a relationship at the front of its chain. Find works as it did before, looking the name up in the map, so finding a node by name doesn't touch the disk. Neighbours reads the node's record to get its first relationship, the start of the chain, and follows each next until there's none. Each step reads one relationship record, which is one page read, and compares its type with the one we asked for, a zero-ended string against a string view. The chain is newest first, so we reverse what we found, and callers get the neighbours in the order they were added, as they did from the vectors. In facts dot c c, Load facts now keeps the three pieces of a fact as string views first: the first name, the type and the second name, as before. Each of them is a substring of the line, cut at the positions where the two splits were found. The first name starts after the opening bracket, the type after the colon, and the second name after the arrow, without its closing bracket, which the comment over it says. Each of these is a view into the line, so nothing is copied until a node or a relationship is added. Before adding anything, it checks that they fit in their records, with the names at most twenty-seven characters and the type at most nineteen. Graph's k max name and k max type say where those limits come from, so they change along with the records. When a piece is too long, the line goes in the error and Load facts returns false, as it does for a line it can't read, and the comment over that check says why. Then it adds the two nodes one after the other, and after them, the relationship between them. In C++, the compiler can work out a call's arguments in any order, and GCC and Clang don't always agree. So splitting the two Add node calls out of the call means their ids come out in the order they're named, on any compiler.

22:51 Let's build it, and run the tests, which is the moment of truth. The four tests from last time haven't changed, not by a line, and they now run against records in pages, and all eight tests pass. And sg, which we haven't touched either, loads the animals into a temporary graph on disk and walks the food chain, to the clover and the wheat. That's what keeping those three functions was for.

Two runs, one folder

23:16 Right now, sg loads the facts each time it runs, into a graph that's gone when it exits. To keep a graph between runs, sg gets two commands: load adds a facts file to the graph in a folder, and walk answers from that folder. The helpers go in an unnamed namespace, as nothing outside this file uses them. Usage prints how to use both commands, to standard error, as two lines of one string, and returns one, so main can return what it returns. The two lines are two string literals one after the other, which C++ joins into one, as in our tests. Load, whose comment says it adds the facts in a file to the graph, does what main did before. It takes the graph by reference, as loading changes it, and the path as a C string, straight from the arguments. It opens the facts file with an input file stream, and says so when it can't. Then it loads the facts into the graph, prints the line it couldn't read if there is one, and otherwise prints the counts of nodes and relationships. Walk takes the graph as a const reference, as walking doesn't change it, along with the start, the type and the hops as text. Its comment says it prints the nodes that many hops away. It finds the start node with Find, and says so if there's none by that name. Then it reads the hops with from chars, and checks they're a whole number that isn't negative, as before. And it walks, printing the name of each node it reaches. Then comes main, at the bottom of the file, outside the namespace. It reads the command, the first argument, or an empty string when there's none, with the conditional operator, which picks one value or the other on a condition. A load needs two arguments after it, so four in all, counting sg, and a walk needs four after it, so six. Anything else prints the usage, and sg stops there. Then main makes a graph and opens it in the folder after the command, which creates the folder the first time, and stops with the error when it can't. Last, it hands the rest of the arguments to load or to walk, with the conditional operator again. In graph test dot c c, we include filesystem, for removing a folder, and optional, for what Find returns. The new test, Keeps its records in a folder, works out a path in GoogleTest's temporary folder, and removes anything left there by an earlier run, with remove all. Inside braces, it opens a graph in that folder, adds the rabbit, and gives it a relationship of EATS to the clover. At the closing brace, the graph goes away, and its record files close. Then a new graph opens the folder again. Find has to know the rabbit, which it can't unless Open read the names back from the node records, and assert true stops the test if it doesn't. And the rabbit's neighbours along EATS have to be the clover, which comes from its chain on disk. Git ignores folders ending in dot sg, so a graph we load doesn't end up in the repository, and the README shows the two commands.

26:16 We build it, and run the tests with ctest. They now include the one for a restart, and some of them read and write real files, in GoogleTest's temporary folder, and all nine of them pass. Then we load the animals into a folder called animals dot sg, which sg creates for us, and it holds ten nodes and fifteen relationships. In a second run, sg walks the food chain from that folder, without the facts file, and gets the clover and the wheat. The folder has two files, nodes and relationships, each of them two pages, a header and a page of records. So let's look at the nodes file, byte by byte, with xxd, which prints a file in hexadecimal, sixteen bytes to a line, and dash a squeezes runs of zeros into a star. The header page starts with ten, as a four-byte number with its lowest byte first, which is how our CPUs store numbers. The rest of the header page is zeros, which the star skips. Page one starts at four thousand and ninety-six, and its first record is the red fox, with its name padded out with zeros. At the end of the record, after the name, is its first relationship, hex b, which is eleven, the start of the chain we drew earlier.

What's slow, for now

27:25 Our graph is on disk now, and there are three things it does that are going to get slow, or unsafe, as the graph grows. Each record we write reads its whole page and writes it back, and appending also writes the header, so adding a relationship reads or writes six pages. A buffer pool keeps the pages we use in memory, so most of those reads and writes don't reach the disk. Each time the graph opens, it reads all the node records to find their names again, which is fine for ten nodes and not for ten million. An index on names fixes that, by keeping them on disk too. And a crash between the two writes of Add relationship leaves a relationship that no chain points to. That's what transactions and a log are for. They're all on the plan, and we're going to measure each one as it comes in.

Wrap-up

28:10 So, today we set up a Docker build, with GitHub Actions running it on each push. We wrote a pager that reads and writes a file in pages of four kilobytes, and files of fixed-size records packed into those pages, after a header that counts them. The graph moved onto thirty-two byte node and relationship records, with each node at the head of a chain of its relationships, as in Neo4j. The tests from last time passed without a change, and with load and walk, a graph now outlives the program that loaded it, as we saw in its bytes.

28:42 This is going to be an evolving project, so I'd love to hear from you. Let me know in the comments how you'd lay out a graph on disk, and if you'd like to follow along, subscribe to the channel. I hope you find this useful, and thanks for watching.