Re: Protect syscache from bloating with negative cache entries

At Tue, 21 Jan 2020 17:29:47 +0100, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote in
> I see this patch is stuck in WoA since 2019/12/01, although there's a
> new patch version from 2020/01/14. But the patch seems to no longer
> apply, at least according to https://commitfest.cputube.org :-( So at
> this point the status is actually correct.
>
> Not sure about the appveyor build (it seems to be about
> jsonb_set_lax),
> but on travis it fails like this:
>
> catcache.c:820:1: error: no previous prototype for
> ‘CatalogCacheFlushCatalog2’ [-Werror=missing-prototypes]

I changed my mind to attach the benchmark patch as .txt file,
expecting the checkers not picking up it as a part of the patchset.

I have in the precise performance measurement mode for a long time,
but I think it's settled. I'd like to return to normal mode and
explain this patch.

=== Motive of the patch

System cache is a mechanism that accelerates access to system catalogs
Basically the entries in a cache is removed via invalidation machanism
when corresponding system catalog entry is removed. On the other hand
the system cache also holds "negative" entries that indicates that the
object is nonexistent, which entry accelerates the response for
nonexistent objects. But the negative cache doesn't have a chance of
removal.

On a long-lived session that accepts a wide variety of queries on many
objects, system cache holds the cache entries for many objects that
are accessed once or a few times. Suppose every object is accessed
once per, say, 30 minutes, and the query doesn't needed to run in a
very short time. Such cache entries are almost useless but occupy a
large amount of memory.

=== Possible solutions.

Many caching system has expiration mechanism, which removes "useless"
entries to keep the size under a certain limit. The limit is
typically defined by memory usage or expiration time, in a hard or
soft way. Since we don't implement an detailed accouting of memory
usage by cache for the performance reasons, we can use coarse memory
accounting or expiration time. This patch uses expiration time
because it can be detemined on a rather clearer basis.

=== Pruning timing

The next point is when to prune cache entries. Apparently it's not
reasonable to do on every cache access time, since pruning takes a far
longer time than cache access.

The system cache is implemented on a hash. When there's no room for a new cache entry, it gets twice in size and rehashes all entries. If pruning made some space for the new entry, rehashing can be avoided, so this patch tries pruning just before enlarging hash table.

A system cache can be shrinked if less than a half of the size is
used, but this patch doesn't that. It is because we cannot predict if
the system cache that have just shrinked is going to enlarged just
after and I don't want get this patch that complex.

=== Performance

The pruning mechanism adds several entries to cache entry and updates

System cache is a very light-weight machinery so that inserting one
branch affects performance apparently. So in this patch, the new stuff
is isolated from existing code path using indirect call. After trials
on some call-points that can be indirect calls, I found that
SearchCatCache[1-4]() is the only point that doesn't affect
performance. (Please see upthread for details.) That configuraion
also allows future implements of system caches, such like shared
system caches.

The alternative SearchCatCache[1-4] functions get a bit slower because
it maintains access timestamp and access counter. Addition to that
pruning puts a certain amount of additional time if no entries are not
pruned off.

=== Pruning criteria

At the pruning time described above, every entry is examined agianst
the GUC variable catalog_cache_prune_min_age. The pruning mechanism
involves a clock-sweep-like mechanism where an entry lives longer if
it had accessed. Entry of which access counter is zero is pruned after
catalog_cache_prune_min_age. Otherwise an entry survives the pruning
round and its counter is decremented.

All the timestamp used by the stuff is "catcacheclock", which is
updated at every transaction start.

=== Concise test

The attached test1.pl can be used to replay the syscache-bloat caused
by negative entries. Setting $prune_age to -1, pruning is turned of
and you can see that the backend unlimitedly takes more and more
memory as time proceeds. Setting it to 10 or so, the memory size of
backend process will stops raising at certain amount.

=== The patch

The attached following are the patch. They have been separated for the
benchmarking reasons but that seems to make the patch more easy to
read so I leave it alone. I forgot its correct version through a long
time of benchmarking so I started from v1 now.

- v1-0001-base_change.patch
Adds new members to existing structs and catcacheclock-related code.

- v1-0002-Make-CatCacheSearchN-indirect-functions.patch
Changes SearchCatCacheN functions to be called by indirect calls.

- v1-0003-CatCache-expiration-feature.patch
The core code of the patch.

- catcache-benchmark-extension.patch.txt
The benchmarking extension that was used for benchmarking
upthread. Just for information.

- test1.pl
Test script to make syscache bloat.

The patchset doesn't contain documentaion for the new GUC option. I
will add it later.

regards.

--
Kyotaro Horiguchi
NTT Open Source Software Center