Re: Multixid hindsight design

On Fri, Jun 5, 2015 at 6:17 AM, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
> I think we should think back to exactly what we are trying to store, why and
> for how long. A clear definition of what we are trying to achieve is
> essential to solving the problem.
>
> In my understanding we need to store
> * at most one xid - the Updating Xid
> * potentially many Locking Xids
>
> The current design has two SLRUs and puts all of those xids in the Members
> SLRU, causing it to need to be persistent.
>
> The problems come from having significant numbers of locking xids. My
> understanding is that any change in the number of lockers requires the full
> array to be rewritten. So with N lockers we end up with 2N-1 arrays, each
> array has an average of N/2 members, or N^2 entries, i.e. an O(N^2)
> algorithm, which makes it a bad thing to persist. Assuming that design
> continues mostly unchanged in its core points...
>
> An alternate proposal:
>
> 1. Store only the Locking xids in the Members SLRU
> 2. In the Offsets SLRU store: 1) the Updating Xid and 2) the offset to the
> Locking xids in the Members SLRU.
>
> This means the Offsets SLRU will be around twice the size it was before BUT
> since we reduce the size of each Members array by one, there is a balanced
> saving there, so this change is disk-space-neutral.
>
> That way if we need to make Offsets SLRU persistent it won't bloat.
> We then leave the Members SLRU as non-persistent, just as it was <9.3

Hmm, this is a neat idea. It would have been easier to implement if
we'd thought of it before we released 9.3, though. At this point, I
guess we'd have to either have a pg_upgrade compatibility break, or
teach pg_upgrade to rejigger the old files into the new file format,
or some other fix that's not immediately apparent to me. And it also
sounds like a fair amount of work. But it might be worth it.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company