PostgreSQL's buffer manager - Problems & Improvements
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Freund, Andres
The buffer manager (primarily configured by shared_buffers) is the part of Postgres that caches on-disk data in memory. That is required both for correct crash recovery and performance. Unfortunately some parts are showing its age. We'll discuss how it currently works, what problems there are, and what attempts are in progress to rectify these weaknesses: * Checkpoints can sometimes trigger huge amounts of IO, leading to long delays of concurrent requests * Lookups in the buffer cache are expensive * The Buffer Mapping table is a hash table, making efficient implementations of prefetching, write coalescing, dropping of cache contents hard * Relation extension scales badly * Cache replacement is inefficient and often replaces the wrong buffers * Double Buffering between the OS and postgres The exact content of the talk will take the state of postgresql's master branch from around the conference into account. It'll less focus on how to tune postgres, and more on how postgres itself can be improved.
 I'm Andres, I work for Citus Data these days. I'm a PostgreSQL developer and committer, and that's where I spend most of my time. And I'm going to talk about PostgreSQL's buffer manager, and which problems it has, and what improvements we can make. First of two questions. Who was in Amit Kapila's talk two slots ago? Okay, significant portion. And who was in the talk about the right-hand look after that? Okay, so good portions. Good, then during their talks I deleted slides, so we don't have to repeat that. So the reason I'm talking about the problems and improvements in the buffer manager is that the buffer manager's design basically has really changed very much in the last 10, 15 years, but the world in which we operate, like we have a lot more memory, we have a lot more disk, faster disks, latencies have changed. So there's some aging, I think, in the algorithms that were chosen back then, so I think there's a lot to improve. But on the other hand, even if I say this doesn't work at all or something like that, we are starting at a pretty good place. In a lot of scenarios, none of the problems I'm talking about here will ever be an actual production problem, and you really mostly hit the issues at the higher end. So I want to very quickly go over the absolute basics that are necessary to understand what I'm going to talk about. I'm not going to go into details about how this works, because that seems like to take about the whole talk. Postgres uses shared buffers to cache disk accesses, because the disk is slow, even when you're talking about SSDs, SSDs are still a couple of orders of magnitude slower than memory, and that's not likely to entirely change, even if there's now non-volatile memory around and stuff like that. And there's also some correctness issues where they write a headlock as it only works if we actually don't write a date back earlier. That was explained in the slot before. So Postgres uses a buffer mapping hash table to map from which table, are we talking about which block in which table, to a finite list of buffers, and these buffers then contain the actual disk data on in that block. And by default, they're a kilobyte large, but you can recompile them to be differently sized. If you want to read data, what happens is that you look up in the hash table, you say, do we have at the moment data in memory for the table so and so, block so and so. And if there's none, we just use a free block, let's just assume we have a free block available, and lock that block, and then read in the data from the operating system. And one very important part is that we actually ask the operating system's page cache. We don't use O-direct to directly go to the disk without, we instead ask the OS to potentially also cache data. And if the OS hasn't cached the data, it asks the actual storage, then it goes back to the page cache, if the page cache is filled in, and then the data is read back into Postgres' buffer cache. And after that, we are done. So the writing case is a bit different because we only ever write to blocks basically if they're already in the shared buffers. So if there's like an insert to a row, then we just write that into memory. That means there's no OS interaction here. We just write it into the page that contains the right block. So earlier said that we just assumed that there's a free block, but what if your workload is actually bigger than shared memory? In that case, you have to find free, replace a block. And Postgres uses an algorithm called clock sweep for that purpose. It basically orders all the blocks we saw as an array earlier into a circle and wrapping around at the last one. And when we need a few new buffer for another purpose, what we do is we walk around that clock and the clock hand basically says, we are currently looking at that buffer. And to decide whether to replace a buffer at the clock hand, every buffer has a so-called usage count. Initially, the usage count is a number in Postgres by default if you, unless you change compilation settings between zero and five. And if we just assume that the buffer two at which the clock hand points right now has a usage count of four, the way it works that is that if the hand points there and we need a replacement buffer, it looks at the usage count. And if it's zero, then it directly uses the buffer. And if it's bigger, it just decrements the buffer usage count by one. So it just does this. And after that, we look at the next buffer. And they're the same game. If the buffer usage count is zero, then we use it. If not, we just decrement the usage count. So that continues to tick until we find a buffer with usage count of zero. In that case, I can possibly just use that buffer directly if there's no, if the data in there is not important, but potentially we've modified the data in that block. In that case, we obviously need to write the data back to disk first because otherwise we'd lose important data if we just reuse the buffer. So that's the point when rides go to disk. The way that works is just that we again, lock the buffer and then we ask the OS to write data. But here, important is that again, we just ask the OS to write to the page cache. We don't directly write it to the storage. And the OS decides on its own basically when that data is written out. And that actually leads us to the first problem I want to discuss, which is that if you run a minimally tuned Postgres on a relatively slow storage device, it's like my home server workstation. And in this case, it's a rotational storage. You often end up with throughput graphs and latency graphs that look like this. At the beginning, you have a pretty good performance. And then after a while, you get very, very, very spiky performance. You can see that we can do 18,000 TPS when it's okay. And then in between, we go basically to one 10th or something on the latency spikes. So I've just said how writing out data works. And one important detail to know here is like, you can see that the promise is okay until that 300 seconds. And that's because then that's when the first checkpoint starts, if you start Postgres, starts after five minutes, 300 seconds, so we start to write out data at this point. And coincidentally or not, the decreases in performance start there. So why is that? If you look at the same time at the stats in the operating system, how much dirty data is in its own, in the OS page cache, you can see something like this. So there's a lot of, there's four or 500 megabytes of dirty data at the peak points. And that's also when things are slow because the OS, every now and then has to decide, I'm now writing data back. And unfortunately Linux by default just says, I'm trying to do this as fast as possible. And that's when all the other writes that we have to do, for example, PG bench, which we saw the results there for, was, does a lot of small transactions. If the transaction wants to commit, they have to make sure that the data goes to physical storage. And that's when we see the delay because there's so much write back going on when the OS tries to write the dirty data from the page cache onto the disk. So you can kind of work around this in various ways. But if you don't, you can really see latency spikes in the couple of hundreds of milliseconds. I've seen machines stall for over an hour without anything happening because there was so much dirty data. And whether you are prone to see that problem depends a lot of what kind of workload you have and what kind of hardware have and how you configure the operating system. And you'll either see that you get these stalls, every dirty write back sent to text in Linux, which is 30 seconds by default. Or you'll see them when dirty background ratio of memory or dirty ratio of memory is reached. And that's by default, 20% of the available memory or 10% of the available memory. And you'll also see the spikes whenever the checkpoint finishes. And if you ever looked at the locked checkpoints output of Postgres, you can see that sometimes it says, the sync of the files took so and so many seconds. And if that's very long, that's usually to blame this problem. So you can work around this in Linux by just setting dirty background ratio and dirty ratio to very low values. And that can give you performance back. There's also other solutions which we now implemented in 9.6. We can tell the kernel that whenever we write data back, hey, we now wrote a couple megabytes or couple kilobytes, please now write that data back, but don't do a full data integrity write, just flush it out now. And the call in Linux is for that a sync file range. In other operating systems, we can use M-Sync and there's a bunch of other possible implementations. These are the ones that are okay, performance-wise okay. And that works on Linux and that works on FreeBSD and OSX. But because it's a bit more expensive, only on Linux this feature is enabled by default. But the problem is with optimizations like this that they can have a trade-off. If you have a large workload and you write a lot, but your total and the workload is bigger than shared memory, but smaller than the OS's page cache or smaller than the dirty page ratio, dirty background ratio, then you can actually have the case that by flushing more eagerly, you get noticeable slowdowns because previously, we just used the operating systems page cache as an extension to shared buffers. We constantly wrote dirty data to the kernel, but we already only wrote data that was already dirty, so the kernel didn't have to, there was no write involved. But if you force the flashes to happen earlier, that can have a performance impact. So that's why you can configure the writes that this does not happen, but it's at the moment enabled by default. And if you look at the performance impact of the same workload on the same hardware, this is now how it looks. You can see that at the beginning, the performance is mostly consistently good. This one is actually when my backup tool started doing the test and slowed things down, but after 300 seconds, the first checkpoint starts, and we see that the performance is lower because the checkpoint actually does work, but it's not as low as before, it was below 200 before. And after another 300 seconds, the checkpoint finishes, or after 300 times 0.9 because that's a completion target, and the performance is good for a short while, and then it's in the middle again. You can get this one, this performance level, a lot closer to this one by saying, my checkpoints are allowed to take longer. You can increase the checkpoint timeout. But one second, this trade-off with, okay, we can improve the performance if your postgres is configured correctly, but it might decrease performance in other cases when you haven't, it's unfortunately pretty fundamental. I think it will come more and more into play the higher performance you want because at some point, the trade-offs are that your postgres does more work and gives less control to the operating system, and that means the postgres has to be configured better. Jeff? So it's about the latency by their... That's the F-sync, at the end of the checkpoint. I think we can improve on that as well. I sent a patch a while back where we do the F-sync on the individual files whenever we are done with them, because we now sort checkpoints, we can do the F-sync whenever we did an individual file. That is actually, you have to do it for more automation for that or an individual segment, but nobody has done the work yet. But that reduces, makes it more interleaved with the rest of the work. So I think that's a good improvement, but it means that you have to tune shared buffers more carefully. So if not, if you can't do that, you need to turn off back and flush after because that's the biggest performance in that. So the next big problem I see is that postgres uses a hash table for this buffer mapping. We saw that on the first slide, where whenever we ask, is this buffer in memory? We ask the hash table and then check, go to the buffer in shared buffers. And that's actually performance problematic for several reasons. Some of them are like micro optimizations or others are architectural. Like from the micro optimization perspective, it's actually pretty expensive to do hash table lookups. For one, the key into the hash table is fairly wide in postgres. Because we have to store the database ID, we have to store the tablespace ID, we have to store the relation identifier and the fork number. And that makes 20 bytes a total. And while we hash that to a small value, we still need to do a mem compare whenever we do the lookup, because otherwise, obviously there can be hash collisions. So that actually is the biggest chunk of work we do for the hash table lookups, often the comparison of the actual key. It's also a problem that hash tables, while they are one in performance in the average case, they're actually not very good from a CPU efficiency point of view, because there's no spatial locality. If you lookup block one in a relation and you lookup block two afterwards, they're going to be entirely different parts of the memory. But that's a very common task to look at spatially related blocks. So you'll have completely independent cache lines. So data structure that has spatial locality would be a lot faster. There's also a big problem that hash tables by definition have no meaningful order between, you can't efficiently say, give me the next defined buffer in the relation. Say I'm looking at block one, give me block two, it's block two already in memory, give me the next block that is in the relation. That's not possible in a hash table, because there's no ordering. So that is a problem for a number of cases. One of them is, for example, if you drop a table at the moment, we have to scan the whole shared buffers sequentially, which is a problem if it's a couple terabytes, and see whether there's any blocks that we have to throw out of shared buffers. It's also a problem for write combining, but I'll talk about that in a bit. So my solution, my proposed solution, and I've actually have a working patch that I'm going to post sometime next week or the next week after, is to split the hash table into two parts. We can say that we want to have one data structure that keeps track of which files we have actually open and which are present in shared buffers, and that's indexed by the tablespace, by the database, and by the rail file node, and that we can keep open for a long while. And then from there, we can have an entry into a smaller tree per relation, which says, okay, which block is where in shared buffers? And that has the advantage that if you, for example, want to drop the table, you can just walk down that relation to just scan the blocks that can potentially be in that relation. And it also has the advantage that the key into the tree where we do the actual lookups is now only four bytes, because our block numbers are limited to four bytes. So we have a lot less data to look at for doing the lookup. In my patch, I continued to implement the relation level mapping as a hash table. And, but the lower level, because there's no need to normally to go through all the open relations in a defined order, we don't actually need to do that very often because we can cache which relations are open in the back, and Postgres has structures that keep track of which tables look how, and we can keep a pointer there to how does, which, where in shared buffers, shared memory is that relation open. But the lower level tree, which is, I kept one per tree per fork of the relation, Postgres has, for each relation, you can have like the main data, and then sometimes you have a free space map which keeps track where we can we place new data. You can have the visibility map, so this one's supposed to be visibility not FSM, and that keeps track of which tables does vacuum not have to scan, and for each of them I've kept the smaller tree, and that is then ordered, and for that I used the so-called erotic stream, talk about that in a second, and I also think that the having a structure in memory that represents an open relation has actually a lot of advantages, because at the moment, whenever we do like a sequential scan on a table, or whenever we insert a new block, we have to at the moment to do an L-seq on the underlying relations to figure out how big it is. Whenever we want to extend a relation, we have to lock the relation exclusively because we don't know whether another session concurrently also extends the table, and we would potentially overwrite data the other session wants to extend. So being able to have an in-memory location where you can say, okay, these many blocks are actually initialized, and what I'm extending up to here would be very helpful. Not just for extension, but also for getting, making the shrinking of files more efficient. At the moment, when vacuum decides I can shrink a table, we have to exclusively lock the table, which is not very good, because then you can't read anything anymore, you can't write anything anymore, and I think if you had a notion in memory how much data is actually initialized, then you could get rid of that. So I think that has architectural benefits as well as efficiency benefits. What I'm imagining to use for the smaller tree for each relation to index blocks, yeah? I just have a quick question. So your proposal is eventually to move from a sequel level, you know, logical lock on a table down to a latch on a state-shared data source, is that the idea? Well, yeah, kind of, you would hold a lock on the last relation, on the block, and then you would just say the in memory, you would decrement the initialized up to here variable in memory by one, and then do that for the next block, decrement, so you only need one block level locks, and then after that you can truncate, and you probably would need a lock that prevents concurrent extension of the file, because that will get hairy, but yeah. You could push that down on the in memory. Yes, exactly. So what I'm imagining for the tree to do the lookups on the block level is at the moment a radix tree, or a bitcrypt tree, or something, and basically that works by, if you have imagined that the block number is a four-byte integer, saying, okay, we subdivide it for the individual tree levels, we subdivide the key space into evenly sized chunks until the last part, which can't be evenly sized because there's not that nice divisors for 32 bits that work well in this case. So in this case I just used six bits for each tree level, and when I want to do a lookup, I can see, okay, the first two by, six bits of my, the block I look up is, I don't know, a three or something, and then I go into the top level, tree level, and say, okay, I'm looking at the slot three, and from then I know there's a pointer to the next tree level, or let's say one, that maps to the next tree level here, and then I do the next for the next six bits, I can do a lookup here, and then iterate through that to the last block, to the last level, and at the last level I then have the block number stored, and the number in shared buffers. And that's, one of the benefits here is that you have a very limited number of lookups, and that is actually relatively pipeline, CPU pipeline friendly, because it can start executing stuff for the next block level relatively early. That's, and it's the same thing that Linux uses, it kind of works well. I tried other data structures so far, the locking overhead of others is worse, but yeah. Yeah, but like a lot of people. It's the next thing that I actually wanted to mention. So this, both the open relation table, and this one have the problem that memory manage gets more complicated, because it can end up having like, as many open relations as shared buffers, and for each shared buffers you only access the last block in a two terabyte table or something, then your trees get fairly deep, and I think it's not a particularly realistic use case, but obviously you can't error out. What I'm thinking of doing right now is to basically say, I'm just reclaiming memory and throwing stuff out of cache if that happens. And like, you can actually, with some trickery, you can do have shortcuts in the tree here. If there's no neighboring pages, you can go like directly from here to here with some, with a bit flex set. So there's some issues here, and generally, so far we had a memory structure which are fairly easy because you can predict the size beforehand directly, but that's not necessarily the case if you have like, predict we how large is the table, that number of open relations, you don't really want to size that up for number of buffers that use a fairly high percentage. So there's some complexity here. I think being more aggressive about reclaiming memory, like open relations is the best way here because it's not that interesting of a use case. Nobody has a couple million relations open at the same time, it only one block in each. So in this data structure, also as the advantage that you can implement locking fairly efficiently, it's fairly easy to do a lockless upgrade, walk, reads in here, and even writes are quite possible. There's some issues around how to do. I said nobody has a couple million relations at one block, but I've actually seen that whenever people find the most dependent in that data. No, no, I'm not saying that they don't have it, but in memory, one block of O. It's not about the on-disk situation, nobody cares, that's fine, it's about having one block in memory of each relation and that never changing. So you basically never read the two billionth paid, the two billionth page of each, of 100 million different tables, that's fairly unlikely. Because I mean, you don't have that much storage. Yeah, it's more effective also. So one of the advantages of this type of data structure is that it's relatively easy to implement lock-free reads and even lock-free writes are quite possible. There's some complexity around how to do save memory reclamation if somebody else is currently walking the tree. I've looked at three different implementations of how to do that safely in a not garbage collected language. I so far have looked at hazard pointers and Robert has had an implementation of that for Postgres. I don't like them very much because they're very invasive in the implementation of the algorithm and the read side overhead is a bunch of memory barriers usually and that's actually not that cheap. I also looked at epoch based reclamation, that's fairly nice because they're fairly easy to implement. But again, the read side overhead is fairly large. I now have a implementation of RCU for Postgres, read copy updates, it's an algorithm to do lock-free read sides and how to do delayed reclamation when you can be sure that nobody else can see the memory anymore. And the big advantage is that you don't have to do very invasive changes in each of the data structures you're visiting. So I think that's so far the best approach. Unfortunately, it's not that simple to implement and it's fairly complex. So I'm not sure whether it's the best approach but it's the one I came up with. Yeah, I'm doing for time one second. So the next problem with the buffer manager that we have that I see is that at the moment, whenever you have a workload that is bigger than shared memory, usually you can see that most of the writes are actually done by backends themselves. Whenever they read something that's not in shared buffers, they have to write out another page that's dirty, which is very bad for performance. Because obviously you rather want your back-end sessions to be active processing the query instead of writing out independent data. It also has the problem that if you have a lot of back-ends that do that and they each write out in the real block, you end up with a lot of random writes. Because each back-end just writes out a random buffer, random page, that's not very good. It also makes the management of the dirty data in the kernel, which I showed earlier to be important, rather hard, because each back-end does independent writes. So if you want to have a total limit across all back-ends, you end up with some complex locking or complex accounting. So I think it's good if we move the processing of write-outs more into the background writer, but more about that in a second. We also have the problem that this cache replacement algorithm, the clock sweep that I talked about earlier, actually scales very badly. Because we had some bad locking around that, that's fixed in 9.05, but the other problem is that each back-end performs the clock sweep. And that means that the integral buffer, like the headers for the buffers, go from one numer node to the next numer node and back constantly. Also, we actually, one clock sweep to find a free buffer is really expensive. You potentially have to go around all buffers five times, around all shared buffers five times, because that's a max usage count to find a replacement buffer. The worst case is actually a bit worse than that, because you can currently, can increase the user count as well. So I don't really have a way to address the second part, but I think we can address the rest and make that a little bit less bad by improving the background writer infrastructure we have right now. At the moment, the background writer is designed to help the clocks, to make the clock sweep less more efficient. And just so by, whenever the clock hand is, it basically tries to scan the next couple hundred blocks after the, in front of the clock hand. And when it finds a dirty buffer, but only if the dirty buffer has a huge count of zero, then it tries to write that out in advance. The problem with that is that the algorithm basically is not, it's not really all that adaptive. It tries, if there's buffers with, it basically tries to always write out a thousand buffers, or something, there's some adaptive logic there, but it doesn't really work. Also, the problem that it actually doesn't do, perform the clock sweep itself. It doesn't change the usage count, which means that you usually have the background writer touching all the buffer headers to here, and then directly afterwards, you have the back ends that also touch the same cache lines, which then obviously have to bounce between all the different processes or numer nodes or anything like that. So what I think we should do instead is basically rename the background writer to a clock sweeper or sweeper or something process, and to actually do the clock sweep in there, and do all the ticks here, and whenever it finds a free block, or finds a dirty buffer and has that are written out, then it puts the clean pages with a usage count of zero into a ring buffer, which then other, whenever another backend needs a page from there, it can go to the end of the ring buffer, or the front, depending on how you want to see it, and say, okay, I want one of these free buffers, and it might be that since then the page has been reused and has incremented the usage count again, but okay, then it just goes to the next one, and that's also fairly easy to scale up. If you have one background writer and it can't keep up, you can just increase the number of these sweeper processes by one, and you can continue to scale across, and it's also, I think, actually fairly easy to tune that, because you can just say, my shared buffers is, I don't know, 100 gigabytes, I always want to have 100 megabytes of that available for reuse, and then you can have as many processes trying to make 100 megabytes available, and if there's nothing to do anymore, then can sleep and can be woken up with a latch, and they will just continue filling up that ring buffer until more than the high watermark of buffers are filled. So, and if that shouldn't work, we can still fall back to the normal clock seep in the back end. So I think that's a fairly sane approach. I posted a patch in another thread a couple months back, but I plan to submit that as a proper thing, and I think I see very little reason not to go for a model like this, but I don't know whether other people have a different opinion. I might admit this, but how does this integrate with the perrelation tree patch? Because if you have now your buffers in the perrelation tree, wouldn't the sweeper keep the low-key stuff tree defined? No, the clock seep you can still do through all shared buffers. You don't need to look at inside the individual trees, because shared buffers still is an array that, I mean, if you think back to the initial slide, the hash table already was there. It's always pointing into the area of shared buffers. So that shouldn't be affected at all, except for the case that you might remove the last buffer that a relation had cached, and then you might need to remove that from the open relations table, but that's, I think, the only interaction. And there's also the problem at the moment that whenever we do writes by the background writer or by individual backends, we write a random page, essentially, because we just chose one somewhere in shared buffers without any closeness logic or anything, and write that back to the operating system. That means usually all the writes done by backends and by the background writer are entirely random. And even on modern SSDs, random writes are really bad in performance. Usually, if you have larger writes and on a good SSD, you can scale up the, if you increase the size of an individual write, it scales nearly linearly to a significant size of write. So it would be good if we were able to efficiently say, OK, I'm writing back an individual block. OK, are any of the neighboring blocks also dirty? And that's where the radix tree comes in again, because if we implement that, we have a data structure that efficiently is able to look into both directions, are there any neighboring writes? And then you can say, OK, I found neighboring writes, and I can combine these and do them as long one, either small consecutive writes, which then can be combined in the sub-OIO submission queue of either the operating system or the storage device. Or what you could also do is use pwrite, which is a system call that allows you to submit non-contiguous writes as a contiguous block, non-contiguous memory buffers as a one-contiguous write. I very, very quickly hacked this together to do writes up to 16 blocks together, and I got a 40% performance improvement on bigger than memory PG-bench workload, which I think that obviously was really just hacked together. But that seems fairly promising to me. And the most interesting part was how much that reduced the AO weight you saw on the storage devices. After that, we hit some other bottlenecks somewhere in Postgres. So we also have the problem at the moment that the clock sweep algorithm, unfortunately, actually does a lot of work, but doesn't really work that well. Because in many workloads, you have that many accesses to buffers, and whenever we access a buffer, we increase the usage count. Then you end up with a lot of buffers that have the highest usage count. And then the clock sweep comes and reduces all of the usage counts to zero, so all of them can be reused. And then after a short while, everything has five again, and that way there's no actual benefit of the usage count anymore. And you need a specific usage pattern to generate that, but it's unfortunately pretty common once. Essentially, at the moment, there's all the way it only works if your replacement rate of buffers is higher than your access rate. And that might be because we implement clock sweep in a bit awkward manner, but there's different theories why that is. It's also, we can't easily just say, OK, we just, because of that problem, increment increased usage count to have a maximum of 100 or something, because that means our clock sweep now has to potentially go around the clock 100 times, which will make performance not very good either. So we need to do something about that. One of the solutions I was thinking about is to make the usage count increment differently. We can very cheaply go from zero usage count to one, and from one to two. But after that, either use a probabilistic thing, say, OK, from two to three, you need have a 10% chance of increasing or 50%, and then decrease that, which will mean that we only still need the same number of clock sweeps, but we need a lot more accesses to increase to a usage count of five, which means our recency information will be better. I haven't implemented that, but I would be very curious about how that goes, and it shouldn't be very hard, I think. It would, because we don't need, at the moment, we only need a maximum of five clock sweeps, like full clocks around, which, if we increment it to 100, we need to 100. I guess you could definitely take 20. Yeah, then you have no benefit. No, the point is that you need to want a nonlinear growth. So what are you, or are you more done with? Yeah, I think you could do it on either. Yeah, OK. So another idea would be to replace the go away from clock sweep. Unfortunately, there's not that many very good algorithms out there that are actually applicable to have couple terabytes of memory under, because a lot of the research in this was made in the 1980s and stuff, and like, oh, yeah, we have a couple thousand buffers, OK, whatever. That doesn't really apply to the current world. I hacked something together using list-based LRUs, and the locking around that gets very complicated, because the list manipulation makes, you need very dirty hacks to be able to, in the middle of lists, to avoid the hotspots at the beginning, at the end of the list. So it's not that easy. At the moment, Heike basically commented recently that random replacement would be better than what we are doing today, because it's actually cheaper. I implemented that, and it actually did perform better, which I found very, very sad. For PG Bench, random replacement is more efficient than what we are doing today. I mean, yes. So PG Bench is not a very good benchmark, because it accesses data in a uniformly distributed random manner. So I don't think that's universally true. That's why I'm not suggesting we seriously go there. But at the moment, for some use cases, we have a very expensive implementation of random replacement, which is not very good. Do you find anything else? I think it's better to use other sources. No, this was a hack on a flight across the pond somewhere. I didn't have any internet, so I needed to make do it. So we also have the problem at the moment that we interact weirdly with the kernel page cache, more than just that we have the problem that the dirty data is not written back early enough or at the wrong time. We also have the problem that at the moment, in many cases, you will have double buffering. We will have the data once in shared buffers and once in the US cache. Sorry, you skipped the one that was working first. It seemed it all. I always assumed. Oh, yeah. I implemented that, actually. Sorry, I forgot about that. But it performs horribly if you have a workload that actually is mostly cache resident, because you do clock sweeps on buffer accesses. And that's like four orders of magnitude more expensive than the actual pin buffer. And lots of workloads are really read. I mean, we just made the pinning and unpinning of buffers lock free for a good reason, because it is an actual contention point. If you then start accessing the neighboring cache lines from all sessions at the same time, the performance goes down. I used it on a two-node neural machine. And basically, it's. Is that something you could do by moving the usage counts to a different pinpecker? I don't think so. I mean, that will mean we access two cache lines for every pin buffer. That will just make things worse. I don't think there is a reason why we didn't implement that. And that's because it's too inefficient. I would be very interested if you can come up with an implementation that doesn't have that problem. Please do, but I don't think it's feasible. Sorry. Yeah, at the moment, if you have a workload with a lot of reads and your shared buffers is smaller than half of the operating system's page cache, then you end up with most of the time have one copy of the page in the OS cache and one another copy in Postgres. And one solution to that is to just set shared buffers to something higher. But that doesn't work well if you also have queries that need a lot of memory. Or if you want to add memory or want to shrink memory, all that doesn't really work with that. So I think we'll end up at the point where just keeping all the data in kernel buffers and in our own buffers is not that feasible anymore. The more our memory size increase, the more problems the kernel page has as well. There's a lot of scalability problems there. They have to be a lot more generic than we have to do. So there's good reasons why it would be better to potentially keep that and make that our problem instead of the kernels. Unfortunately, a lot of the solutions for that are not very nice. One of the really easy to implement ways would be to just hint the kernel whenever we've written something. Oh, yeah, forget about that, right? And remove it. And whenever we've read something, also say, yeah, kernel, please forget about this page. Unfortunately, that doesn't really help make any use of the page cache anymore because we then can't, if we forget about a page in memory, then it's also forgotten on disk in the US page cache. So the current effect of making the page cache as a read-only extension of shared buffers doesn't work anymore. So there's a dirty hack which I talked about to some Linux guys that we could say, this is right, but please don't write it back to storage and then sense up the kernel page cache. But unsurprisingly, they're a bit hesitant about adding that feature because that means you can arbitrarily corrupt the page cache, which I kind of understand why they want that. But yeah, that is one solution. Sorry? Yeah. The problem is that that basically also requires explicit configuration. And the benefit of having using the US page cache is that it's adaptive. So I think it's like, I don't know whether that works well enough. It's certainly worth thinking about and playing around with. The other solution is just to all, most of the IO we do with O-direct. And O-direct is a flag that tells the kernel to bypass the US page cache. So every read directly goes to storage. Every write directly goes to storage. And usually that path is a good bit faster for the internal reads because it has to do a lot less and also has been optimized by other big database vendors. But it has a lot of problems too because we would need to improve a lot on our performance side because we relied on the kernel. At the moment, if we do a write to the kernel, we can basically expect that to take as long as a mem copy takes plus some state management in the kernel. But after that, every write would take as long as your storage device takes to write something. So suddenly, writes become synchronous. And so far, they've been asynchronous. We've started to do work to do with that. For example, the sweeper process I just talked about earlier would address that to some degree because it would now move all the writes to the background. But they would still be synchronous. So we probably would either need a lot more of those or we would need to use asynchronous IO. But asynchronous IO, there's all implementation of asynchronous IO suck. So it's hard. And it has a problem that I just mentioned that if you go there, there's no more adaptivity of using setting a small shared buffers and rely on the US to be adaptive and use them. Potentially, we need to make shared buffers more easily replaceable. Perhaps we need to be able to say, OK, this part of shared buffers we are not using efficiently. Give, say, market is unused and allow the US to reuse the pages that actually is possible in several operating systems. I don't really know what the best answer to that is. It also has the problem that every operating system needs nearly independent implementations to be halfway efficient. Something you do on Linux works not at all on Solaris. Does not work at all on Windows. So the overhead in the last maintaining post-graph will increase considerably. One of the other things that I've seen on other instances running is that we don't know if the time of year is much faster. Is the time of year on every transaction on mobile pages much more over time than the average time of year? Yeah, I think that's largely because of the dirty right thing I just mentioned. And I think we have the feature I mentioned earlier with keeping track of how much dirty data the kernel has was mainly motivated by managing latency. We've seen latency reduction by 300%, 400%. Yeah, we've not seen on a mobile screen a real workload. I agree. Just saying, we've made it a little bit less bad, but the problem is still there. Because the main reason for that is that whenever you do a syscall, you have the potential are much more likely to be scheduled out. And that doesn't exist if you don't act through a syscall. So yeah, that actually is my last slide. Any questions? So the question is basically, if you have operations that access a lot of data, but that don't use our ring buffer, we have ring buffer sequential IO, but they are not used for index accesses and how what are the potential optimizations and whether we can use adapt the clock sweep algorithm for that. I think to a large degree, that might actually be addressed by improving the recency information because of this problem that we are. If you do a single index look up, you usually end up with like three, a usage count of three already. So that already destroys a lot of the recency information because we end up touching a single index page multiple times. So I think the first improvement would be to improve the user count management. I have some doubts about the second clock hand being really useful. I don't know. There's a bunch of papers that have ideas like that. I'm a bit doubtful. I think what might be useful to tell your session, you always use a ring buffer for the accesses independent where they are. We call them bulk access strategies. So you can declare if you do bulk operation, I also want to keep track of indexes and keep the ring buffer size across several relations at the same time instead of one per relation. I think that might be a viable approach to improve on that. I think that the ring buffer is sort of a kind of a process to sort of do that. Yes. I mean, we already have like small ring buffers for sequential access. So if you do a copy, a vacuum, a sequential scan of a large table, then we use a ring buffer if it's more than one fourth of shared buffers. I don't know who came up with that. So we already have some of that. But I think we might be able to make that more widely used. Other questions? OK, cool. Thank you.
 I'm Andres, I work for Citus Data these days.  I'm a PostgreSQL developer and committer,  and that's where I spend most of my time.  And I'm going to talk about PostgreSQL's buffer manager,  and which problems it has, and what improvements we can make.  First of two questions.  Who was in Amit Kapila's talk two slots ago?  Okay, significant portion.  And who was in the talk about the right-hand look after that?  Okay, so good portions.  Good, then during their talks I deleted slides,  so we don't have to repeat that.  So the reason I'm talking about the problems  and improvements in the buffer manager is that  the buffer manager's design basically  has really changed very much in the last 10, 15 years,  but the world in which we operate,  like we have a lot more memory,  we have a lot more disk, faster disks,  latencies have changed.  So there's some aging, I think,  in the algorithms that were chosen back then,  so I think there's a lot to improve.  But on the other hand, even if I say  this doesn't work at all or something like that,  we are starting at a pretty good place.  In a lot of scenarios, none of the problems  I'm talking about here will ever be  an actual production problem,  and you really mostly hit the issues at the higher end.  So I want to very quickly go over the absolute basics  that are necessary to understand  what I'm going to talk about.  I'm not going to go into details about how this works,  because that seems like to take about the whole talk.  Postgres uses shared buffers to cache disk accesses,  because the disk is slow, even when you're talking about SSDs,  SSDs are still a couple of orders of magnitude slower  than memory, and that's not likely to entirely change,  even if there's now non-volatile memory around  and stuff like that.  And there's also some correctness issues  where they write a headlock as it only works  if we actually don't write a date back earlier.  That was explained in the slot before.  So Postgres uses a buffer mapping hash table  to map from which table,  are we talking about which block in which table,  to a finite list of buffers,  and these buffers then contain the actual disk data  on in that block.  And by default, they're a kilobyte large,  but you can recompile them to be differently sized.  If you want to read data, what happens is  that you look up in the hash table,  you say, do we have at the moment data in memory  for the table so and so, block so and so.  And if there's none, we just use a free block,  let's just assume we have a free block available,  and lock that block, and then read in the data  from the operating system.  And one very important part is that we actually ask  the operating system's page cache.  We don't use O-direct to directly go to the disk without,  we instead ask the OS to potentially also cache data.  And if the OS hasn't cached the data,  it asks the actual storage,  then it goes back to the page cache,  if the page cache is filled in,  and then the data is read back into Postgres' buffer cache.  And after that, we are done.  So the writing case is a bit different  because we only ever write to blocks basically  if they're already in the shared buffers.  So if there's like an insert to a row,  then we just write that into memory.  That means there's no OS interaction here.  We just write it into the page that contains the right block.  So earlier said that we just assumed  that there's a free block, but what if your workload  is actually bigger than shared memory?  In that case, you have to find free, replace a block.  And Postgres uses an algorithm called clock sweep  for that purpose.  It basically orders all the blocks we saw as an array earlier  into a circle and wrapping around at the last one.  And when we need a few new buffer for another purpose,  what we do is we walk around that clock  and the clock hand basically says,  we are currently looking at that buffer.  And to decide whether to replace a buffer at the clock hand,  every buffer has a so-called usage count.  Initially, the usage count is a number in Postgres  by default if you, unless you change compilation settings  between zero and five.  And if we just assume that the buffer two  at which the clock hand points right now  has a usage count of four, the way it works that is that  if the hand points there and we need a replacement buffer,  it looks at the usage count.  And if it's zero, then it directly uses the buffer.  And if it's bigger, it just decrements the buffer  usage count by one.  So it just does this.  And after that, we look at the next buffer.  And they're the same game.  If the buffer usage count is zero, then we use it.  If not, we just decrement the usage count.  So that continues to tick until we find a buffer  with usage count of zero.  In that case, I can possibly just use that buffer directly  if there's no, if the data in there is not important,  but potentially we've modified the data in that block.  In that case, we obviously need to write the data back  to disk first because otherwise we'd lose important data  if we just reuse the buffer.  So that's the point when rides go to disk.  The way that works is just that we again,  lock the buffer and then we ask the OS to write data.  But here, important is that again,  we just ask the OS to write to the page cache.  We don't directly write it to the storage.  And the OS decides on its own basically  when that data is written out.  And that actually leads us to the first problem  I want to discuss, which is that if you run  a minimally tuned Postgres on a relatively slow storage  device, it's like my home server workstation.  And in this case, it's a rotational storage.  You often end up with throughput graphs  and latency graphs that look like this.  At the beginning, you have a pretty good performance.  And then after a while, you get very, very,  very spiky performance.  You can see that we can do 18,000 TPS when it's okay.  And then in between, we go basically to one 10th  or something on the latency spikes.  So I've just said how writing out data works.  And one important detail to know here is like,  you can see that the promise is okay until that 300 seconds.  And that's because then that's when the first checkpoint  starts, if you start Postgres, starts after five minutes,  300 seconds, so we start to write out data at this point.  And coincidentally or not, the decreases  in performance start there.  So why is that?  If you look at the same time at the stats  in the operating system, how much dirty data  is in its own, in the OS page cache,  you can see something like this.  So there's a lot of, there's four or 500 megabytes  of dirty data at the peak points.  And that's also when things are slow because the OS,  every now and then has to decide,  I'm now writing data back.  And unfortunately Linux by default just says,  I'm trying to do this as fast as possible.  And that's when all the other writes that we have to do,  for example, PG bench, which we saw the results there for,  was, does a lot of small transactions.  If the transaction wants to commit,  they have to make sure that the data goes  to physical storage.  And that's when we see the delay  because there's so much write back going on  when the OS tries to write the dirty data  from the page cache onto the disk.  So you can kind of work around this in various ways.  But if you don't, you can really see latency spikes  in the couple of hundreds of milliseconds.  I've seen machines stall for over an hour  without anything happening  because there was so much dirty data.  And whether you are prone to see that problem  depends a lot of what kind of workload you have  and what kind of hardware have  and how you configure the operating system.  And you'll either see that you get these stalls,  every dirty write back sent to text in Linux,  which is 30 seconds by default.  Or you'll see them when dirty background ratio of memory  or dirty ratio of memory is reached.  And that's by default,  20% of the available memory  or 10% of the available memory.  And you'll also see the spikes  whenever the checkpoint finishes.  And if you ever looked at the locked checkpoints  output of Postgres,  you can see that sometimes it says,  the sync of the files took so and so many seconds.  And if that's very long,  that's usually to blame this problem.  So you can work around this in Linux  by just setting dirty background ratio  and dirty ratio to very low values.  And that can give you performance back.  There's also other solutions  which we now implemented in 9.6.  We can tell the kernel that whenever we write data back,  hey, we now wrote a couple megabytes or couple kilobytes,  please now write that data back,  but don't do a full data integrity write,  just flush it out now.  And the call in Linux is for that a sync file range.  In other operating systems,  we can use M-Sync and there's a bunch  of other possible implementations.  These are the ones that are okay, performance-wise okay.  And that works on Linux  and that works on FreeBSD and OSX.  But because it's a bit more expensive,  only on Linux this feature is enabled by default.  But the problem is with optimizations like this  that they can have a trade-off.  If you have a large workload and you write a lot,  but your total and the workload is bigger than shared memory,  but smaller than the OS's page cache  or smaller than the dirty page ratio,  dirty background ratio,  then you can actually have the case  that by flushing more eagerly,  you get noticeable slowdowns because previously,  we just used the operating systems page cache  as an extension to shared buffers.  We constantly wrote dirty data to the kernel,  but we already only wrote data that was already dirty,  so the kernel didn't have to, there was no write involved.  But if you force the flashes to happen earlier,  that can have a performance impact.  So that's why you can configure the writes  that this does not happen,  but it's at the moment enabled by default.  And if you look at the performance impact  of the same workload on the same hardware,  this is now how it looks.  You can see that at the beginning,  the performance is mostly consistently good.  This one is actually when my backup tool  started doing the test and slowed things down,  but after 300 seconds, the first checkpoint starts,  and we see that the performance is lower  because the checkpoint actually does work,  but it's not as low as before, it was below 200 before.  And after another 300 seconds, the checkpoint finishes,  or after 300 times 0.9 because that's a completion target,  and the performance is good for a short while,  and then it's in the middle again.  You can get this one, this performance level,  a lot closer to this one by saying,  my checkpoints are allowed to take longer.  You can increase the checkpoint timeout.  But one second, this trade-off with,  okay, we can improve the performance  if your postgres is configured correctly,  but it might decrease performance  in other cases when you haven't,  it's unfortunately pretty fundamental.  I think it will come more and more  into play the higher performance you want  because at some point, the trade-offs are  that your postgres does more work  and gives less control to the operating system,  and that means the postgres has to be configured better.  Jeff?  So it's about the latency by their...  That's the F-sync, at the end of the checkpoint.  I think we can improve on that as well.  I sent a patch a while back  where we do the F-sync on the individual files  whenever we are done with them,  because we now sort checkpoints,  we can do the F-sync whenever we did an individual file.  That is actually, you have to do it for more automation  for that or an individual segment,  but nobody has done the work yet.  But that reduces, makes it more  interleaved with the rest of the work.  So I think that's a good improvement,  but it means that you have to tune shared buffers  more carefully.  So if not, if you can't do that,  you need to turn off back and flush after  because that's the biggest performance in that.  So the next big problem I see is that postgres uses  a hash table for this buffer mapping.  We saw that on the first slide,  where whenever we ask, is this buffer in memory?  We ask the hash table and then check,  go to the buffer in shared buffers.  And that's actually performance problematic  for several reasons.  Some of them are like micro optimizations  or others are architectural.  Like from the micro optimization perspective,  it's actually pretty expensive to do hash table lookups.  For one, the key into the hash table  is fairly wide in postgres.  Because we have to store the database ID,  we have to store the tablespace ID,  we have to store the relation identifier  and the fork number.  And that makes 20 bytes a total.  And while we hash that to a small value,  we still need to do a mem compare  whenever we do the lookup,  because otherwise, obviously there can be hash collisions.  So that actually is the biggest chunk of work we do  for the hash table lookups,  often the comparison of the actual key.  It's also a problem that hash tables,  while they are one in performance in the average case,  they're actually not very good  from a CPU efficiency point of view,  because there's no spatial locality.  If you lookup block one in a relation  and you lookup block two afterwards,  they're going to be entirely different parts of the memory.  But that's a very common task  to look at spatially related blocks.  So you'll have completely independent cache lines.  So data structure that has spatial locality  would be a lot faster.  There's also a big problem that hash tables  by definition have no meaningful order between,  you can't efficiently say,  give me the next defined buffer in the relation.  Say I'm looking at block one, give me block two,  it's block two already in memory,  give me the next block that is in the relation.  That's not possible in a hash table,  because there's no ordering.  So that is a problem for a number of cases.  One of them is, for example,  if you drop a table at the moment,  we have to scan the whole shared buffers sequentially,  which is a problem if it's a couple terabytes,  and see whether there's any blocks  that we have to throw out of shared buffers.  It's also a problem for write combining,  but I'll talk about that in a bit.  So my solution, my proposed solution,  and I've actually have a working patch  that I'm going to post sometime next week  or the next week after, is to split the hash table  into two parts.  We can say that we want to have one data structure  that keeps track of which files we have actually open  and which are present in shared buffers,  and that's indexed by the tablespace,  by the database, and by the rail file node,  and that we can keep open for a long while.  And then from there, we can have an entry  into a smaller tree per relation,  which says, okay, which block is where in shared buffers?  And that has the advantage that if you, for example,  want to drop the table, you can just walk down  that relation to just scan the blocks  that can potentially be in that relation.  And it also has the advantage that the key into the tree  where we do the actual lookups is now only four bytes,  because our block numbers are limited to four bytes.  So we have a lot less data to look at for doing the lookup.  In my patch, I continued to implement  the relation level mapping as a hash table.  And, but the lower level, because there's no need  to normally to go through all the open relations  in a defined order, we don't actually need  to do that very often because we can cache  which relations are open in the back,  and Postgres has structures that keep track  of which tables look how, and we can keep a pointer there  to how does, which, where in shared buffers,  shared memory is that relation open.  But the lower level tree, which is,  I kept one per tree per fork of the relation,  Postgres has, for each relation,  you can have like the main data,  and then sometimes you have a free space map  which keeps track where we can we place new data.  You can have the visibility map,  so this one's supposed to be visibility not FSM,  and that keeps track of which tables  does vacuum not have to scan,  and for each of them I've kept the smaller tree,  and that is then ordered, and for that I used  the so-called erotic stream, talk about that in a second,  and I also think that the having a structure in memory  that represents an open relation  has actually a lot of advantages,  because at the moment, whenever we do  like a sequential scan on a table,  or whenever we insert a new block,  we have to at the moment to do an L-seq  on the underlying relations to figure out how big it is.  Whenever we want to extend a relation,  we have to lock the relation exclusively  because we don't know whether another session  concurrently also extends the table,  and we would potentially overwrite data  the other session wants to extend.  So being able to have an in-memory location  where you can say, okay, these many blocks  are actually initialized,  and what I'm extending up to here would be very helpful.  Not just for extension, but also for getting,  making the shrinking of files more efficient.  At the moment, when vacuum decides I can shrink a table,  we have to exclusively lock the table,  which is not very good, because then you can't read  anything anymore, you can't write anything anymore,  and I think if you had a notion in memory  how much data is actually initialized,  then you could get rid of that.  So I think that has architectural benefits  as well as efficiency benefits.  What I'm imagining to use for the smaller tree  for each relation to index blocks, yeah?  I just have a quick question.  So your proposal is eventually to move from a sequel level,  you know, logical lock on a table down to a latch  on a state-shared data source, is that the idea?  Well, yeah, kind of, you would hold a lock  on the last relation, on the block,  and then you would just say the in memory,  you would decrement the initialized up to here  variable in memory by one, and then do that  for the next block, decrement,  so you only need one block level locks,  and then after that you can truncate,  and you probably would need a lock  that prevents concurrent extension of the file,  because that will get hairy, but yeah.  You could push that down on the in memory.  Yes, exactly.  So what I'm imagining for the tree  to do the lookups on the block level  is at the moment a radix tree, or a bitcrypt tree,  or something, and basically that works by,  if you have imagined that the block number  is a four-byte integer, saying, okay,  we subdivide it for the individual tree levels,  we subdivide the key space into evenly sized chunks  until the last part, which can't be evenly sized  because there's not that nice divisors for 32 bits  that work well in this case.  So in this case I just used six bits for each tree level,  and when I want to do a lookup, I can see,  okay, the first two by, six bits of my,  the block I look up is, I don't know,  a three or something, and then I go into the top level,  tree level, and say, okay, I'm looking at the slot three,  and from then I know there's a pointer  to the next tree level, or let's say one,  that maps to the next tree level here,  and then I do the next for the next six bits,  I can do a lookup here, and then iterate through that  to the last block, to the last level,  and at the last level I then have the block number stored,  and the number in shared buffers.  And that's, one of the benefits here is that you have  a very limited number of lookups,  and that is actually relatively pipeline,  CPU pipeline friendly, because it can start executing stuff  for the next block level relatively early.  That's, and it's the same thing that Linux uses,  it kind of works well.  I tried other data structures so far,  the locking overhead of others is worse, but yeah.  Yeah, but like a lot of people.  It's the next thing that I actually wanted to mention.  So this, both the open relation table,  and this one have the problem that memory manage  gets more complicated, because it can end up having like,  as many open relations as shared buffers,  and for each shared buffers you only access the last  block in a two terabyte table or something,  then your trees get fairly deep,  and I think it's not a particularly realistic use case,  but obviously you can't error out.  What I'm thinking of doing right now is to basically say,  I'm just reclaiming memory and throwing stuff  out of cache if that happens.  And like, you can actually, with some trickery,  you can do have shortcuts in the tree here.  If there's no neighboring pages,  you can go like directly from here to here with some,  with a bit flex set.  So there's some issues here, and generally,  so far we had a memory structure which are fairly easy  because you can predict the size beforehand directly,  but that's not necessarily the case if you have like,  predict we how large is the table,  that number of open relations,  you don't really want to size that up for number of buffers  that use a fairly high percentage.  So there's some complexity here.  I think being more aggressive about reclaiming memory,  like open relations is the best way here  because it's not that interesting of a use case.  Nobody has a couple million relations open at the same time,  it only one block in each.  So in this data structure, also as the advantage  that you can implement locking fairly efficiently,  it's fairly easy to do a lockless upgrade,  walk, reads in here, and even writes are quite possible.  There's some issues around how to do.  I said nobody has a couple million relations at one block,  but I've actually seen that whenever people find the  most dependent in that data.  No, no, I'm not saying that they don't have it,  but in memory, one block of O.  It's not about the on-disk situation, nobody cares,  that's fine, it's about having one block in memory  of each relation and that never changing.  So you basically never read the two billionth paid,  the two billionth page of each, of 100 million different  tables, that's fairly unlikely.  Because I mean, you don't have that much storage.  Yeah, it's more effective also.  So one of the advantages of this type of data structure  is that it's relatively easy to implement lock-free reads  and even lock-free writes are quite possible.  There's some complexity around how to do  save memory reclamation if somebody else is currently  walking the tree.  I've looked at three different implementations  of how to do that safely in a not garbage collected language.  I so far have looked at hazard pointers  and Robert has had an implementation of that  for Postgres.  I don't like them very much because they're very invasive  in the implementation of the algorithm  and the read side overhead is a bunch of memory barriers  usually and that's actually not that cheap.  I also looked at epoch based reclamation,  that's fairly nice because they're fairly easy to implement.  But again, the read side overhead is fairly large.  I now have a implementation of RCU for Postgres,  read copy updates, it's an algorithm to do lock-free  read sides and how to do delayed reclamation  when you can be sure that nobody else  can see the memory anymore.  And the big advantage is that you don't have to do  very invasive changes in each  of the data structures you're visiting.  So I think that's so far the best approach.  Unfortunately, it's not that simple to implement  and it's fairly complex.  So I'm not sure whether it's the best approach  but it's the one I came up with.  Yeah, I'm doing for time one second.  So the next problem with the buffer manager that we have  that I see is that at the moment,  whenever you have a workload that is bigger  than shared memory, usually you can see  that most of the writes are actually done  by backends themselves.  Whenever they read something that's not in shared buffers,  they have to write out another page that's dirty,  which is very bad for performance.  Because obviously you rather want your back-end sessions  to be active processing the query instead of writing out  independent data.  It also has the problem that if you have a lot of back-ends  that do that and they each write out in the real block,  you end up with a lot of random writes.  Because each back-end just writes out a random buffer,  random page, that's not very good.  It also makes the management of the dirty data  in the kernel, which I showed earlier to be important,  rather hard, because each back-end does independent writes.  So if you want to have a total limit across all back-ends,  you end up with some complex locking or complex accounting.  So I think it's good if we move the processing  of write-outs more into the background writer,  but more about that in a second.  We also have the problem that this cache replacement algorithm,  the clock sweep that I talked about earlier,  actually scales very badly.  Because we had some bad locking around that,  that's fixed in 9.05, but the other problem is that  each back-end performs the clock sweep.  And that means that the integral buffer,  like the headers for the buffers,  go from one numer node to the next numer node and back  constantly.  Also, we actually, one clock sweep to find a free buffer  is really expensive.  You potentially have to go around all buffers five times,  around all shared buffers five times,  because that's a max usage count  to find a replacement buffer.  The worst case is actually a bit worse than that,  because you can currently, can increase the user count  as well.  So I don't really have a way to address the second part,  but I think we can address the rest and make that  a little bit less bad by improving the background writer  infrastructure we have right now.  At the moment, the background writer is designed  to help the clocks, to make the clock sweep  less more efficient.  And just so by, whenever the clock hand is,  it basically tries to scan the next couple hundred blocks  after the, in front of the clock hand.  And when it finds a dirty buffer,  but only if the dirty buffer has a huge count of zero,  then it tries to write that out in advance.  The problem with that is that the algorithm basically is not,  it's not really all that adaptive.  It tries, if there's buffers with,  it basically tries to always write out a thousand buffers,  or something, there's some adaptive logic there,  but it doesn't really work.  Also, the problem that it actually doesn't do,  perform the clock sweep itself.  It doesn't change the usage count,  which means that you usually have the background writer  touching all the buffer headers to here,  and then directly afterwards, you have the back ends  that also touch the same cache lines,  which then obviously have to bounce between all the different  processes or numer nodes or anything like that.  So what I think we should do instead is basically rename  the background writer to a clock sweeper or sweeper  or something process, and to actually do the clock sweep  in there, and do all the ticks here,  and whenever it finds a free block,  or finds a dirty buffer and has that are written out,  then it puts the clean pages with a usage count of zero  into a ring buffer, which then other,  whenever another backend needs a page from there,  it can go to the end of the ring buffer,  or the front, depending on how you want to see it,  and say, okay, I want one of these free buffers,  and it might be that since then the page has been reused  and has incremented the usage count again,  but okay, then it just goes to the next one,  and that's also fairly easy to scale up.  If you have one background writer and it can't keep up,  you can just increase the number of these sweeper processes  by one, and you can continue to scale across,  and it's also, I think, actually fairly easy to tune that,  because you can just say, my shared buffers is,  I don't know, 100 gigabytes, I always want to have  100 megabytes of that available for reuse,  and then you can have as many processes  trying to make 100 megabytes available,  and if there's nothing to do anymore,  then can sleep and can be woken up with a latch,  and they will just continue filling up that ring buffer  until more than the high watermark of buffers are filled.  So, and if that shouldn't work,  we can still fall back to the normal clock seep in the back end.  So I think that's a fairly sane approach.  I posted a patch in another thread a couple months back,  but I plan to submit that as a proper thing,  and I think I see very little reason not to go for a model like this,  but I don't know whether other people have a different opinion.  I might admit this, but how does this integrate  with the perrelation tree patch?  Because if you have now your buffers in the perrelation tree,  wouldn't the sweeper keep the low-key stuff  tree defined?  No, the clock seep you can still do through all shared buffers.  You don't need to look at inside the individual trees,  because shared buffers still is an array that,  I mean, if you think back to the initial slide,  the hash table already was there.  It's always pointing into the area of shared buffers.  So that shouldn't be affected at all,  except for the case that you might remove the last buffer  that a relation had cached, and then you  might need to remove that from the open relations table,  but that's, I think, the only interaction.  And there's also the problem at the moment  that whenever we do writes by the background writer  or by individual backends, we write a random page,  essentially, because we just chose one somewhere  in shared buffers without any closeness logic or anything,  and write that back to the operating system.  That means usually all the writes done by backends  and by the background writer are entirely random.  And even on modern SSDs, random writes  are really bad in performance.  Usually, if you have larger writes and on a good SSD,  you can scale up the, if you increase the size of an individual  write, it scales nearly linearly to a significant size  of write.  So it would be good if we were able to efficiently say, OK,  I'm writing back an individual block.  OK, are any of the neighboring blocks also dirty?  And that's where the radix tree comes in again,  because if we implement that, we have a data structure  that efficiently is able to look into both directions,  are there any neighboring writes?  And then you can say, OK, I found neighboring writes,  and I can combine these and do them  as long one, either small consecutive writes, which then  can be combined in the sub-OIO submission  queue of either the operating system or the storage device.  Or what you could also do is use pwrite, which  is a system call that allows you to submit  non-contiguous writes as a contiguous block,  non-contiguous memory buffers as a one-contiguous write.  I very, very quickly hacked this together  to do writes up to 16 blocks together,  and I got a 40% performance improvement on bigger than memory  PG-bench workload, which I think that obviously was really  just hacked together.  But that seems fairly promising to me.  And the most interesting part was how much  that reduced the AO weight you saw on the storage devices.  After that, we hit some other bottlenecks  somewhere in Postgres.  So we also have the problem at the moment  that the clock sweep algorithm, unfortunately,  actually does a lot of work, but doesn't really work that well.  Because in many workloads, you have that many accesses to  buffers, and whenever we access a buffer,  we increase the usage count.  Then you end up with a lot of buffers  that have the highest usage count.  And then the clock sweep comes and reduces all of the usage  counts to zero, so all of them can be reused.  And then after a short while, everything has five again,  and that way there's no actual benefit of the usage count  anymore.  And you need a specific usage pattern  to generate that, but it's unfortunately pretty common once.  Essentially, at the moment, there's  all the way it only works if your replacement rate of buffers  is higher than your access rate.  And that might be because we implement clock sweep  in a bit awkward manner, but there's different theories  why that is.  It's also, we can't easily just say, OK,  we just, because of that problem,  increment increased usage count to have a maximum of 100  or something, because that means our clock sweep now  has to potentially go around the clock 100 times, which  will make performance not very good either.  So we need to do something about that.  One of the solutions I was thinking about  is to make the usage count increment differently.  We can very cheaply go from zero usage count to one,  and from one to two.  But after that, either use a probabilistic thing,  say, OK, from two to three, you need  have a 10% chance of increasing or 50%,  and then decrease that, which will  mean that we only still need the same number of clock sweeps,  but we need a lot more accesses to increase to a usage count of five,  which means our recency information will be better.  I haven't implemented that, but I would be very curious  about how that goes, and it shouldn't be very hard, I think.  It would, because we don't need, at the moment,  we only need a maximum of five clock sweeps,  like full clocks around, which, if we increment it to 100,  we need to 100.  I guess you could definitely take 20.  Yeah, then you have no benefit.  No, the point is that you need to want a nonlinear growth.  So what are you, or are you more done with?  Yeah, I think you could do it on either.  Yeah, OK.  So another idea would be to replace the go away from clock sweep.  Unfortunately, there's not that many very good algorithms  out there that are actually applicable to have  couple terabytes of memory under, because a lot of the research  in this was made in the 1980s and stuff, and like, oh, yeah,  we have a couple thousand buffers, OK, whatever.  That doesn't really apply to the current world.  I hacked something together using list-based LRUs,  and the locking around that gets very complicated,  because the list manipulation makes,  you need very dirty hacks to be able to,  in the middle of lists, to avoid the hotspots  at the beginning, at the end of the list.  So it's not that easy.  At the moment, Heike basically commented recently  that random replacement would be better than what  we are doing today, because it's actually cheaper.  I implemented that, and it actually did perform better,  which I found very, very sad.  For PG Bench, random replacement is more efficient  than what we are doing today.  I mean, yes.  So PG Bench is not a very good benchmark,  because it accesses data in a uniformly distributed  random manner.  So I don't think that's universally true.  That's why I'm not suggesting we seriously go there.  But at the moment, for some use cases,  we have a very expensive implementation  of random replacement, which is not very good.  Do you find anything else?  I think it's better to use other sources.  No, this was a hack on a flight across the pond somewhere.  I didn't have any internet, so I needed to make do it.  So we also have the problem at the moment  that we interact weirdly with the kernel page cache, more  than just that we have the problem  that the dirty data is not written back early enough  or at the wrong time.  We also have the problem that at the moment, in many cases,  you will have double buffering.  We will have the data once in shared buffers  and once in the US cache.  Sorry, you skipped the one that was working first.  It seemed it all.  I always assumed.  Oh, yeah.  I implemented that, actually.  Sorry, I forgot about that.  But it performs horribly if you have a workload  that actually is mostly cache resident,  because you do clock sweeps on buffer accesses.  And that's like four orders of magnitude more expensive  than the actual pin buffer.  And lots of workloads are really read.  I mean, we just made the pinning and unpinning of buffers  lock free for a good reason, because it  is an actual contention point.  If you then start accessing the neighboring cache lines  from all sessions at the same time,  the performance goes down.  I used it on a two-node neural machine.  And basically, it's.  Is that something you could do by moving the usage counts  to a different pinpecker?  I don't think so.  I mean, that will mean we access two cache lines  for every pin buffer.  That will just make things worse.  I don't think there is a reason why we didn't implement that.  And that's because it's too inefficient.  I would be very interested if you  can come up with an implementation that  doesn't have that problem.  Please do, but I don't think it's feasible.  Sorry.  Yeah, at the moment, if you have a workload with a lot of reads  and your shared buffers is smaller than half  of the operating system's page cache,  then you end up with most of the time  have one copy of the page in the OS cache  and one another copy in Postgres.  And one solution to that is to just set shared buffers  to something higher.  But that doesn't work well if you also  have queries that need a lot of memory.  Or if you want to add memory or want to shrink memory,  all that doesn't really work with that.  So I think we'll end up at the point  where just keeping all the data in kernel buffers  and in our own buffers is not that feasible anymore.  The more our memory size increase,  the more problems the kernel page has as well.  There's a lot of scalability problems there.  They have to be a lot more generic than we have to do.  So there's good reasons why it would  be better to potentially keep that and make  that our problem instead of the kernels.  Unfortunately, a lot of the solutions for that  are not very nice.  One of the really easy to implement ways  would be to just hint the kernel whenever we've written  something.  Oh, yeah, forget about that, right?  And remove it.  And whenever we've read something, also say, yeah,  kernel, please forget about this page.  Unfortunately, that doesn't really  help make any use of the page cache anymore  because we then can't, if we forget about a page in memory,  then it's also forgotten on disk in the US page cache.  So the current effect of making the page  cache as a read-only extension of shared buffers  doesn't work anymore.  So there's a dirty hack which I talked about to some Linux  guys that we could say, this is right,  but please don't write it back to storage  and then sense up the kernel page cache.  But unsurprisingly, they're a bit hesitant about adding  that feature because that means you can arbitrarily corrupt  the page cache, which I kind of understand why they want that.  But yeah, that is one solution.  Sorry?  Yeah.  The problem is that that basically also  requires explicit configuration.  And the benefit of having using the US page cache  is that it's adaptive.  So I think it's like, I don't know  whether that works well enough.  It's certainly worth thinking about and playing around with.  The other solution is just to all,  most of the IO we do with O-direct.  And O-direct is a flag that tells the kernel  to bypass the US page cache.  So every read directly goes to storage.  Every write directly goes to storage.  And usually that path is a good bit faster  for the internal reads because it has to do a lot less  and also has been optimized by other big database vendors.  But it has a lot of problems too because we would need  to improve a lot on our performance side  because we relied on the kernel.  At the moment, if we do a write to the kernel,  we can basically expect that to take as long as a mem copy  takes plus some state management in the kernel.  But after that, every write would take as long as your storage  device takes to write something.  So suddenly, writes become synchronous.  And so far, they've been asynchronous.  We've started to do work to do with that.  For example, the sweeper process I just talked about earlier  would address that to some degree  because it would now move all the writes to the background.  But they would still be synchronous.  So we probably would either need a lot more of those  or we would need to use asynchronous IO.  But asynchronous IO, there's all implementation  of asynchronous IO suck.  So it's hard.  And it has a problem that I just mentioned  that if you go there, there's no more  adaptivity of using setting a small shared  buffers and rely on the US to be adaptive and use them.  Potentially, we need to make shared buffers more easily  replaceable.  Perhaps we need to be able to say, OK,  this part of shared buffers we are not using efficiently.  Give, say, market is unused and allow the US  to reuse the pages that actually is possible  in several operating systems.  I don't really know what the best answer to that is.  It also has the problem that every operating system  needs nearly independent implementations  to be halfway efficient.  Something you do on Linux works not at all on Solaris.  Does not work at all on Windows.  So the overhead in the last maintaining post-graph  will increase considerably.  One of the other things that I've seen on other instances  running is that we don't know if the time of year  is much faster.  Is the time of year on every transaction  on mobile pages much more over time  than the average time of year?  Yeah, I think that's largely because of the dirty right thing  I just mentioned.  And I think we have the feature I mentioned earlier  with keeping track of how much dirty data the kernel has  was mainly motivated by managing latency.  We've seen latency reduction by 300%, 400%.  Yeah, we've not seen on a mobile screen  a real workload.  I agree.  Just saying, we've made it a little bit less bad,  but the problem is still there.  Because the main reason for that is  that whenever you do a syscall, you  have the potential are much more likely to be scheduled out.  And that doesn't exist if you don't act through a syscall.  So yeah, that actually is my last slide.  Any questions?  So the question is basically, if you  have operations that access a lot of data,  but that don't use our ring buffer,  we have ring buffer sequential IO,  but they are not used for index accesses  and how what are the potential optimizations  and whether we can use adapt the clock sweep algorithm for that.  I think to a large degree, that might actually  be addressed by improving the recency information  because of this problem that we are.  If you do a single index look up, you usually  end up with like three, a usage count of three already.  So that already destroys a lot of the recency information  because we end up touching a single index page multiple times.  So I think the first improvement would  be to improve the user count management.  I have some doubts about the second clock  hand being really useful.  I don't know.  There's a bunch of papers that have ideas like that.  I'm a bit doubtful.  I think what might be useful to tell your session,  you always use a ring buffer for the accesses  independent where they are.  We call them bulk access strategies.  So you can declare if you do bulk operation,  I also want to keep track of indexes  and keep the ring buffer size across several relations  at the same time instead of one per relation.  I think that might be a viable approach to improve on that.  I think that the ring buffer is sort of a kind of a process  to sort of do that.  Yes.  I mean, we already have like small ring buffers  for sequential access.  So if you do a copy, a vacuum, a sequential scan  of a large table, then we use a ring buffer  if it's more than one fourth of shared buffers.  I don't know who came up with that.  So we already have some of that.  But I think we might be able to make that more widely used.  Other questions?  OK, cool.  Thank you.
PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_0_131.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_132_2111.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_2112_2591.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_2592_2807.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_2808_2939.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_2940_2987.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_2988_3527.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_3528_3971.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_3972_4151.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_4152_4559.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_4560_5219.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_5220_5411.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_5412_5507.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_5508_5627.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_5628_5747.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_5748_5879.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_5880_6011.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_6012_6143.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_6144_8519.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_8520_8663.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_8664_9143.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_9144_10943.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_10944_12083.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_12084_14039.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_14040_16475.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_16476_17687.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_17688_18431.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_18432_19511.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_19512_23315.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_23316_26363.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_26364_26423.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_26424_26699.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_26700_28271.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_28272_28535.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_28536_29687.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_29688_32627.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_32628_32687.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_32688_33431.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_33432_34043.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_34044_34691.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_34692_35111.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_35112_36839.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_36840_37379.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_37380_37475.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_37476_38039.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_38040_38327.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_38328_38807.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_38808_38867.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_38868_39563.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_39564_39695.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_39696_39851.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_39852_40379.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_40380_40475.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_40476_40523.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_40524_41915.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_41916_43643.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_43644_43919.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_43920_44075.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_44076_47723.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_47724_49475.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_49476_51131.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_51132_53051.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_53052_57335.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_57336_58019.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_58020_59867.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_59868_61523.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_61524_69095.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_69096_74219.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_74220_74267.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_74268_74327.png PostgreSQL_s_buffer_manager_-_Problems___Improveme_Wll4tezLzRE_74328_74350.png