Re: SSI SLRU strategy choices

Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> wrote:
> I'm not sure how you arrived at that number, though.

http://git.postgresql.org/gitweb?p=postgresql.git;a=blob;f=src/include/access/slru.h;h=710cca70acd67e03e5f3a255b048a719ae4c4709
The way I read this, each segment is (BLCKSZ *
SLRU_PAGES_PER_SEGMENT) long, which is (8kB * 32), or 256kB.  The
number of files is limited to 64k because of the 0000 to FFFF
segment file naming.  So total space is limited to 16GB.  When an
SLRU is used to store xids for random access, that's 4 bytes per
entry, so 2^32 entries are possible, but SLRU code considers it a
problem for the space to become more than half full.  With the eight
byte entries I need, there are 2^31 slots for entries, with the
ability to use 2^30 before it becomes half full and SLRU complains.
Does that look right to you, or have I misunderstood something?
> The only issue I can see with that is that you allocate those 8
> bytes for every xid, even if it's a non-serializable transaction
> or a subtransaction. But the overhead is probably not significant
> in practice.
Right.  And it avoids having to sequentially search for the desired
xid.  A sequential search seems to me like it would get into O(N^2)
performance under extreme load, whereas this approach has a couple
performance plateaus at O(1) which will be, I think, the normal
case, and only goes to O(N) performance under extreme load.
-Kevin