On Tue, May 1, 2018 at 11:58 AM, Robert Haas <robertmh...@gmail.com> wrote: > That's not to say that the total of all usage counts must remain equal > to a constant or something dumb like that -- there's decisions to be > made in terms of how you implement things. For example, you can > imagine a system where every time we would bump the usage count of a > buffer that already has a usage count of 5, we would instead advance > the clock hand by 1 buffer. In such a system the total of the usage > counts can fluctuate, but you can't peg everything at 5 because > there's back-pressure built into the algorithm.
This seems to be an old idea. See "Data Cache Management Using Frequency-Based Replacement", a 1990 paper that is referenced by the ARC paper. It says: "When a block is first brought into the cache, its reference count is initialized to one. Previous algorithms using reference counts have incremented the count for a given block on every reference to that block. This results in the following kind of problem: certain blocks are relatively infrequently referenced overall, and yet when they are referenced, due to locality there are short intervals of repeated re-references, thus building up high reference counts. After such an interval is over, the high reference count is misleading: it is due to locality, and cannot be used to estimate the probability that such a block will be re-referenced following the end of this interval (this description is intuitive, since in practice such intervals are not as well-defined as the preceding discussion may suggest)." It goes on to propose a solution, that I gather isn't so far from your thought experiment design for fixing the usage_count saturation problem: "More precisely, we dynamically maintain the sum of all reference counts. Whenever the average reference count exceeds a predetermined maximum value, A-max (another parameter of the algorithm), every reference count C is reduced to C/2. Thus, in the steady state the sum of all reference counts stays between N x A-max/2 and N x A-max (where N is the number of cache blocks), and the reference count of a block is approximately linearly related to the frequency of references to the block while it is in the middle and old sections. Note that in this reduction of reference counts, a count of one remains at one, a count of two is reduced to one, a count of three is reduced to two, etc." This 1990 paper seems to only try to solve the correlated references problem that we see when using CLOCK to approximate an LRU, which is not to be confused with actually weighing frequency in a clever way, which AFAICT is a general idea that didn't come along until the LRU-K paper came out a couple of years later. In other words, the 1990 paper only cares about making sure that CLOCK actually manages to approximate an LRU when reference counts are messed up by correlated references. That's all. This really is a distinct problem to the problem that ARC and CAR aim to solve (2Q and LRU-K must be in the same category, since IIRC they have ghost lists). CART tries to solve both problems at the same time, which suggests that they're independent problems. In summary: I see two clearly distinct problems here, though they are superficially similar. We have both problems. > That's a really appealing property. If there's a "hot" set of buffers > that accounts for nearly all accesses, the algorithm will be willing > to regard that all buffers in that set as frequently-used regardless > of whether it is a large or a small percentage of shared_buffers, and > they will never get evicted. But the buffers must really be hot > enough to justify the space they're taking up. When there are only a > few hot buffers, it's sufficient for them to be a little hotter than > the typical buffer. But when there are a lot of hot buffers, they > have to be *really* hot. Intuitively, that makes sense, because > making the set of "hot" -- and thus unevictable -- buffers large means > that other buffers are going to get evicted very quickly. That's only > justifiable if the hot buffers are very significantly more useful than > the non-hot buffers. Right. How hot "really hot" actually is needs to be based on the behavior of the system as a whole. If it's impossible to better characterize the behavior of the system as a whole, then no improvement is possible; shared_buffers services the system as a whole. I've always had a problem with the 8GB/16GB upper limit on the size of shared_buffers. Not because it's wrong, but because it's not something that has ever been explained. I strongly suspect that it has something to do with usage_count saturation, since it isn't reproducible with any synthetic workload that I'm aware of. Quite possibly because there are few bursty benchmarks. >> All of that having been said, maybe we have an independent low-level >> problem: we increase usage_count when we pin a buffer, even if we last >> pinned the buffer 5ms ago. IIRC a change to this went in when ARC went >> in (and came out with ARC, too). This is more of a problem with >> miscounting the number of hits based on accidents around how things >> are structured in the executor -- we need to be more careful about >> recognizing whether or not block hits are logically distinct. >> Particularly with stuff like nested loop joins. > > I agree that double-counting correlated accesses is a a problem, and I > agree that we probably want to do something about it. I am skeptical > that using wall-clock time is the right way to solve that problem > because it leads to edge effects I agree that wall-clock time is a bad approach, actually. If we were to use wall-clock time, we'd only do so because it can be used to discriminate against a thing that we actually care about in an approximate, indirect way. If there is a more direct way of identifying correlated accesses, which I gather that there is, then we should probably use it. -- Peter Geoghegan