Database buffer pool in C++: keeping pages in memory

Intro

0:00 Hello and welcome back to episode five, where we're going to give smollerGraph a buffer pool, the part of a database that keeps pages in memory, and find out what it does to our million relationships. Let's begin with a quick look at where we're going to be by the end of the episode.

0:16 By the end, smollerGraph is going to load our a million relationships about eleven times faster than it did, and walk two hops in about six microseconds, without reading a single page from its files.

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. The graph learned to be written as JSON, with tests that check each answer without a server. Sg serve answers HTTP requests for it, with cpp-httplib. A page in the browser draws the graph with D3's force simulation, lights up a walk a hop at a time, and shows a node's record, its bytes and its chain, as they're kept on disk. And sg serve answers requests on several threads at once, which matters for what we're going to build today. Today, we get back to what episode three found: each relationship we add reads or writes six pages.

Today

1:22 Today, we're going to keep pages in memory. First, sg learns to count the pages it reads and writes, so we can see what we're about to save. Then we write a buffer pool, which holds pages in frames, and picks which one to give up when it's full. The record files go on top of it, and a latch keeps sg serve's threads from getting in each other's way. Then we measure it all again, against Neo4j and Kùzu. All right, let's get started with counting what we read and write.

Counting pages

1:50 First, a correction to episode three, about how sg was built. Without a build type, CMake builds with no optimisations at all, which is handy in a debugger and no way to measure a database, and that's how episode three's benchmark built sg. So in CMake, when no build type is given, it's now Release, which optimises, and the comment over it says why. We're going to measure the before again with it, so the comparison is fair. In pager dot h, we include atomic, and the pager gets two counts, reads and writes, which say how many pages it has read and written since it opened. The comment over them says so, in a sentence of its own. They're kept in two members, reads and writes, which are atomic. Sg serve reads on several threads at once, and an atomic number can be added to from two threads without losing a count. Reads is mutable too, and the comment says why both are what they are: Read is const, and it still counts. In pager dot c c, Read adds one to reads after a page is read, and Write adds one to writes, after it writes. In record file dot h, the record file passes its pager's two counts on, as page reads and page writes. In graph dot h, the graph adds up its two files' counts, as its comment says: how many pages the graph's two files have read and written. In main dot c c, sg load prints them on a second line, after the time it took: how many pages were read, and how many written. In sg bench, reads before is the count before the timed walks. After them, reads is how many pages they read, as a double, and the JSON gets one more field, page reads, which is that divided by the number of walks, the pages each walk read.

3:32 Let's load the million relationships from episode three again, into friends dot sg, and see what it costs. It takes about as long as it did then. And there's the new line: about three million pages read, and three point two million written, which is six for each relationship, as we worked out. Each one of them is a system call, a trip into the operating system's kernel and back. Then sg bench, which walks two hops from a thousand people. Each walk reads a hundred and twenty-one pages: one for each of the eleven nodes whose relationships it follows, and one for each of their hundred and ten relationships.

4:09 And here's episode three's comparison again, with the optimised build, and before any of today's changes, so we have something fair to measure against. It loads the graph into the three databases, three times each, and times a two-hop walk from a thousand people in each. The video skips ahead while it runs, as it takes a few minutes. Optimised, smollerGraph loads in about twelve point zero seconds, and walks two hops in about forty-six microseconds. Most of that is still the system calls.

A buffer pool

4:42 A buffer pool keeps a database's pages in memory, so the pages it uses most are read from disk once, and changed in memory as often as it likes. The file is still where the pages live, and the pool has a number of frames, each a page-sized piece of memory that can hold one of them. A table says which frame holds which page, so finding a page in the pool is a lookup in a hash map. A page that someone is using is pinned, and a pinned page stays where it is. A page that was changed is dirty, and it's written back to the file before its frame is given to another page. And when the pool is full, something has to pick which page leaves: we're going to use the clock, which PostgreSQL uses a version of too. Neo4j calls its pool the page cache, and Kùzu calls its the buffer manager, and both are sized to hold a graph like ours.

5:31 The clock is a hand that goes round the frames, each of which has a referenced bit, set each time its page is fetched. When the pool needs a frame, the hand moves on from where it stopped. A page that was referenced since the hand last came by gets a second chance: the hand clears its bit, and moves on. A pinned page is skipped, as someone is using it. And the first page that's neither referenced nor pinned is the one that goes, so pages that keep being used keep their frames. It costs a bit for each frame, instead of a list in order of use, which is why databases like it.

6:07 You might be wondering why a database doesn't let the operating system do this, as it already keeps files in memory, and mmap can map a file into a program's memory. This paper, by Andrew Crotty, Viktor Leis and Andy Pavlo, from Carnegie Mellon's database group, is called Are you sure you want to use mmap in your database management system? Their answer, for most databases, is no, and they give their reasons. With mmap, the operating system decides when a changed page is written, which gets in the way of a log that has to be written first. A page that isn't in memory stalls the program while it's read, with no say in what's read next. And with many threads, the operating system's own bookkeeping slows things down. So, like Neo4j and Kùzu, we keep our own pool.

6:54 The buffer pool goes in a header of its own, buffer pool dot h. It includes cstddef, unordered map for the page table, and vector for the frames, and our pager. First, the buffer pool class is declared, as the page handle needs to know about it. A page handle is a page pinned in a buffer pool. Its comment says what that means: the pool doesn't evict a pinned page, and the handle unpins it when it goes away. That's the RAII pattern, where an object's destructor gives back what it holds, so a page can't be left pinned by mistake. The handle's constructor keeps a reference to its pool and the number of its frame, which is where the page sits in the pool. Its destructor, which is declared here and written in the source file, unpins, and it can't be copied, as two copies would unpin twice. Read gives us the page to read, as a const reference. Write gives us the page to change, which marks it to be written back to the file, as its comment says. Then the buffer pool class, whose comment says what it does: it keeps some of a file's pages in memory, in frames, so reading or changing a page there needs no system call. The file is read when a page comes into a frame, and written when a changed page leaves one, or when it's flushed. Its constructor takes a pager and a number of frames, and the destructor writes the changed pages back. It can't be copied either, for a similar reason. Fetch pins page id, and its comment says what it does when the page isn't in a frame: it reads it from the file, and a page past the end of the file starts out as zeros. Flush writes the changed pages back, and keeps them, and Clear writes them back and forgets them all, for when the pager opens another file. In the private part, page handle is a friend, so it can reach the frames and unpin. A frame is a struct, which holds the page's bytes while it's in the pool, and the page's id. Then come its pins, a count of the handles that hold it, starting at zero. Dirty says whether it's been changed, and referenced whether it's been fetched since the clock's hand last passed. The comment over the struct says what the referenced bit is for. Victim picks a frame to reuse, by the clock, as its comment says, and Unpin takes a pin off a frame. The members are the pager, the capacity, the most frames the pool can have, the frames, the table from page ids to frames, and the clock's hand. In buffer pool dot c c, we include cstdio and cstdlib, for stopping with an error. The handle's destructor unpins its frame, through the pool. Read returns the frame's page, and Write marks the frame dirty first. The constructor keeps the pager and the capacity, and reserves room for the frames, without making any. The comment says why: frames are made as pages come in, so a pool that doesn't fill up stays small. Reserving the room up front also means the vector doesn't move its frames as it grows, so a frame stays where it is. The destructor flushes, so no change is lost. Now, on to Fetch, the heart of the pool. First, it looks the page up in the table. When it's there, the frame gets one more pin, and its referenced bit, and we return a handle to it. That's the case we want to be common, and it costs a lookup, with no system call. When the page isn't there, it needs a frame. While the pool has room, it makes a new one at the end. When it's full, the clock picks a victim, and if the victim's page is dirty, it's written back to the file first, before its entry leaves the table. Then the frame takes the new page: its id, one pin, not dirty, and referenced. A page the file has is read into it, and a page past the end of the file is filled with zeros, as it's about to be written for the first time. The table records the page's frame, and we return a handle. Victim is the clock, which we saw a moment ago. The hand goes round the frames, at most twice. Each step takes the frame under the hand, and moves the hand on, round to the start after the last frame. A pinned frame is skipped, as it's in use. A referenced one has its bit cleared, and is skipped too, and the first frame that's neither is returned. The comment above the loop says why twice is enough: the first time round, the hand clears the bits it passes, so the second time round it finds one, unless all of them are pinned. In that case, there's nothing to evict, so we stop with an error. Unpin takes a pin off its frame, and that's all. Flush goes through the frames, and writes each dirty page back to its place in the file, through the pager. Then it marks the frame clean, as the file has what it holds. And Clear flushes, then forgets the frames and the table, and puts the hand back at the start. In CMake, buffer pool dot c c joins the library, next to the pager, and buffer pool test dot c c joins the tests, after the API's. Buffer pool test dot c c includes the buffer pool's header first, then cstddef, string, GoogleTest and the pager. It has four tests, and each of them starts the way the pager's tests do, with a pager on a temporary file, and an assert that it opened. The first one, Reads a page once, writes an empty page zero through the pager, so the file has a page to read. Then it makes a pool of four frames, and fetches page zero, and then page zero again. The comment says what happens to the handles: each one unpins the page at the end of its line, as nobody keeps it. The pager has to have read the page once, for both fetches, as the second one finds it in the pool. The second test, Writes back a changed page it evicts, makes a pool of two frames, and the comment says why: the third page evicts the first. It fetches pages zero, one and two, and writes a byte into each one, through its handle, one more than its id. The pager has to have written once by then, when page zero left. Then fetching page zero again reads it back from the file, and its byte has to be one. The third test, Keeps a pinned page, makes a pool of two frames too, and holds page zero pinned, in a handle of its own. It changes page zero's first byte to seven. Then four other pages, one to four, come and go through the other frame. Page zero's byte has to be seven still, and nothing was written, as page zero stayed in its frame. The last test, Flush writes changed pages, makes a pool of four frames, and changes the byte at five in page zero, through the pool. Then it flushes, and reads the page straight from the pager, into a page of its own, and the byte at five has to be nine.

13:29 Let's build it, and run the buffer pool's tests, with dash R, which picks tests by their names. All four of them pass, on the first run.

Records through the pool

13:39 In record file dot h, we include buffer pool dot h, and the class comment gets a sentence. Its pages go through a buffer pool, which writes the changed ones to the file when it needs their frames, or when it's flushed or closed. K pool pages is the most pages the pool keeps in memory, sixteen thousand three hundred and eighty-four of them, which is sixty-four mebibytes. The comment says why that many: it holds the million relationships we benchmark, which take about thirty-two mebibytes. Open and Open temporary clear the pool before the pager opens another file, which the comment over them says: opening another file writes back the changes to the one that was open. Flush writes the changed pages to the file, through the pool. Read now fetches its record's page from the pool, and copies the record out of the frame, with no system call when the page is already there. The handle is called page, and it unpins at the end of Read. Write fetches the page, and copies the record into it, through write, which marks it dirty. It doesn't need to know whether the page is in the file yet, as the pool gives it zeros past the end. Append's header goes through the pool too, as a page whose first four bytes are the count, and Load count reads the count through the pool as well. Those lines are where a record read or a record written stops costing a system call. At the bottom, the pool is a member, after the pager, made with the pager and k pool pages. The comment says why it's declared after the pager: members are destroyed in reverse, so the pool goes first, and writes its changed pages while the file is still open. It's mutable, as Read is const, and still brings pages into the pool. In graph dot h, Flush writes the graph's changed pages to its two files, which closing the graph does too. In main dot c c, sg load flushes the graph before it stops its clock, as the comment says, so the time includes the writes. Otherwise, they'd happen when the program ends, after the time was printed.

15:39 First, the tests, all of them, from episode one on. They pass, with each record now going through the pool. Then we load the million relationships again, into a fresh folder. This time, the load takes a fraction of a second, where it took about twelve. It read no pages, as each page it needed was new, or in the pool already, and it wrote about eight and a half thousand, once each, when it flushed. And the walks read no pages at all, as the whole graph is in memory after it opens.

A latch for threads

16:10 Sg serve answers requests on several threads at once, which the pool doesn't know about yet. So here's a test from the next step, Threads fetch at once, which fetches pages on four threads, through a pool of four frames, so they keep evicting each other's pages. Let's build it on this step, without the next step's fix, and run it. It crashes, with a segmentation fault, each time it runs. Two threads changed the frames and the table at once, and one of them followed what the other had half done.

16:40 In buffer pool dot h, we include mutex, and the pool gets a latch, a standard mutex. The comment says what it's for: sg serve fetches pages on several threads at once, so a latch, a mutex held for a moment, keeps them from changing the frames and the table together. A pinned page is safe to read without it, as nobody can evict it. Databases say latch for a lock that protects their own structures for a moment, and lock for one that protects your data for a transaction. In buffer pool dot c c, a lock guard takes the latch for as long as it's in scope, and gives it back at the end, which is RAII again. Write takes it to mark its frame dirty. Fetch takes it for the whole fetch, and the comment over it says what that costs: it's held while a page is read or written too, which keeps this simple, and makes other threads wait for the disk. A busier database would let go of it while it waits. Unpin takes it to take a pin off, and Flush takes it while it writes. Clear flushes first, then takes the latch to forget the frames, as a thread that takes a standard mutex it already holds waits forever. In the test, we include atomic, thread and vector. Threads fetch at once writes sixty-four pages, each with its own id in its first byte. The comment says why the pool has four frames for sixty-four pages: the threads evict each other's pages. Wrong is an atomic count of pages that came back with the wrong byte. Four threads each fetch ten thousand pages, spread over all of them, and check each one's first byte. Join waits for each thread to finish, and wrong has to be zero. And in server dot c c, the comment about threads now says what keeps their reads apart: the buffer pools' latches.

18:21 Let's build it, and run the tests, the threads among them. All twenty pass, and the threads find the right pages.

The numbers again

18:30 Let's run episode three's comparison again, which loads the generated graph into smollerGraph, Kùzu and Neo4j, three times each, and times a two-hop walk from a thousand people in each of them, keeping the medians. It takes a few minutes, as Neo4j's import runs in Docker, so the video skips ahead. SmollerGraph's line is the one that changed since episode three.

18:52 Before the pool, a load took about twelve point zero seconds. Now it takes about one point one, which is about eleven times faster, and quicker than Neo4j's bulk import. That puts it level with Kùzu's copy, at about one point two seconds this time, though Kùzu's own load moves about from run to run, and it isn't a fair fight either. Kùzu does a lot more when it loads: it builds its adjacency in both directions, an index on the names, and compressed columns, in files that survive a crash. We keep one direction, no index on disk yet, and nothing that survives a crash in the middle.

19:29 The walk was quick already, and it gets quicker. It went from about forty-six microseconds to about six, without the hundred and twenty-one system calls each walk made. What's left is the walk's own work: looking pages up in the table, copying records out of frames, and the vectors it builds. Neo4j and Kùzu are still answering Cypher, which we don't parse yet, so the walk isn't a fair fight, as we said in episode three.

What it costs

19:56 A buffer pool doesn't come for free, though. It takes memory, up to sixty-four mebibytes for each of our two files, though frames are made as pages come in, so a small graph uses little of it. And a changed page now lives in memory until it's flushed or evicted. If sg crashed in the middle of a load, the changes still in the pool would be lost, and the files could be left half written, with a node pointing at a relationship that didn't make it to disk. That's what a write-ahead log is for, which writes each change down before the page it changes, and we're going to need one when transactions come in.

Wrap-up

20:32 So, today we counted the pages sg reads and writes, and found six page calls for each relationship we add. We wrote a buffer pool, with frames, a table from pages to frames, pins, dirty pages, and the clock to pick which page goes. The record files read and write through it, a latch keeps sg serve's threads apart, and a load is about eleven times faster than it was. Next time, we're going to look at what happens when a graph opens: sg reads each node, to build a map of names in memory. An index on names, kept on disk in pages from our pool, is going to let it find a node without that.

21:10 This is going to be an evolving project, so I'd love to hear from you. Let me know in the comments which eviction policy you'd have picked, and if you'd like to follow along, subscribe to the channel. I hope you find this useful, and thanks for watching.