Re: Freezing without write I/O

On 01.06.2013 23:21, Robert Haas wrote:
> On Sat, Jun 1, 2013 at 2:48 PM, Heikki Linnakangas
>   wrote:
>>> We define a new page-level bit, something like PD_RECENTLY_FROZEN.
>>> When this bit is set, it means there are no unfrozen tuples on the
>>> page with XIDs that predate the current half-epoch.  Whenever we know
>>> this to be true, we set the bit.  If the page LSN crosses more than
>>> one half-epoch boundary at a time, we freeze the page and set the bit.
>>>    If the page LSN crosses exactly one half-epoch boundary, then (1) if
>>> the bit is set, we clear it and (2) if the bit is not set, we freeze
>>> the page and set the bit.
>>
>> Yep, I think that would work. Want to write the patch, or should I? ;-)
>
> Have at it.

Here's a first draft. A lot of stuff missing and broken, but "make 
check" passes :-).

In the patch, instead of working with "half-epochs", there are "XID-LSN 
ranges", which can be of arbitrary size. An XID-LSN range consists of 
three values:

minlsn: The point in WAL where this range begins.
minxid - maxxid: The range of XIDs allowed in this range.

Every point in WAL belongs to exactly one range. The minxid-maxxid of 
the ranges can overlap. For example:

1. XIDs 25000942 - 27000003 LSN 0/3BB9938
2. XIDs 23000742 - 26000003 LSN 0/2AB9288
3. XIDs 22000721 - 25000003 LSN 0/1AB8BE0
4. XIDs 22000002 - 24000003 LSN 0/10B1550

The invariant with the ranges is that a page with a certain LSN is only 
allowed to contain XIDs that belong to the range specified by that LSN. 
For example, if a page has LSN 0/3500000, it belongs to the 2nd range, 
and can only contain XIDs between 23000742 - 26000003. If a backend 
updates the page, so that it's LSN is updated to, say, 0/3D12345, all 
XIDs on the page older than 25000942 must be frozen first, to avoid 
violating the rule.

The system keeps track of a small number of these XID-LSN ranges. Where 
we currently truncate clog, we can also truncate the ranges with maxxid 
< the clog truncation point. Vacuum removes any dead tuples and updates 
relfrozenxid as usual, to make sure that there are no dead tuples or 
aborted XIDs older than the minxid of the oldest tracked XID-LSN range. 
It no longer needs to freeze old committed XIDs, however - that's the 
gain from this patch (except to uphold the invariant, if it has to 
remove some dead tuples on the page and update its LSN).

A new range is created whenever we reach the maxxid on the current one. 
The new range's minxid is set to the current global oldest xmin value, 
and maxxid is just the old maxxid plus a fixed number (1 million in the 
patch, but we probably want a higher value in reality). This ensures 
that if you modify a page and update its LSN, all the existing XIDs on 
the page that cannot be frozen yet are greater than the minxid of the 
latest range. In other words, you can always freeze old XIDs on a page, 
so that any remaining non-frozen XIDs are within the minxid-maxxid of 
the latest range.

The HeapTupleSatisfies functions are modified to look at the page's LSN 
first. If it's old enough, it doesn't look at the XIDs on the page level 
at all, and just considers everything on the page is visible to everyone 
(I'm calling this state a "mature page").

> I think the tricky part is going to be figuring out the
> synchronization around half-epoch boundaries.

Yep. I skipped all those difficult parts in this first version. There 
are two race conditions that need to be fixed:

1. When a page is updated, we check if it needs to be frozen. If its LSN 
is greater than the latest range's LSN. IOW, if we've already modified 
the page, and thus frozen all older tuples, within the current range. 
However, it's possible that a new range is created immediately after 
we've checked that. When we then proceed to do the actual update on the 
page and WAL-log that, the new LSN falls within the next range, and we 
should've frozen the page. I'm planning to fix that by adding a "parity 
bit" on the page header. Each XID-LSN range is assigned a parity bit, 0 
or 1. When we check if a page needs to be frozen on update, we make note 
of the latest range's parity bit, and write it in the page header. 
Later, when we look at the page's LSN to determine which XID-LSN range 
it belongs to, we compare the parity. If the parity doesn't match, we 
know that the race condition happened, so we treat the page to belong to 
the previous range, not the one it would normally belong to, per the LSN.

2. When we look at a page, and determine that it's not old enough to be 
"matured", we then check the clog as usual. A page is considered mature, 
if the XID-LSN range (and corresponding clog pages) has already been 
truncated away. It's possible that between those steps, the XID-LSN 
range and clog is truncated away, so that the backend tries to access a 
clog page that doesn't exist anymore. To fix that, the XID-LSN range and 
clog truncation needs to be done in two steps. First, mark the 
truncation point in shared memory. Then somehow wait until all backends 
see the new value, and go ahead with actually truncating the clog only 
after that.


Aside from those two race conditions, there are plenty of scalability 
issues remaining. Currently, the shared XID-LSN range array is checked 
every time a page is accessed, so it could quickly become a bottleneck. 
Need to cache that information in each backend. Oh, and I didn't 
implement the PD_RECENTLY_FROZEN bit in the page header yet, so you will 
get a freezing frenzy right after a new XID-LSN range is created.

I'll keep hacking away on those things, but please let me know if you 
see some fatal flaw with this plan.

- Heikki