The issue of seeking backward in XLogReadDetermineTimeline()

Hi hackers,

Here's a proposed bug fix for the $subject in XLogReadDetermineTimeline()
noted while working on [1].

1) The problem
This function selects which timeline's file to read a WAL page from.
Reading the timeline history file every time is not ideal. So for the
common case of reading forward, the function caches its last answer:

- state->currTLI: which timeline;
- state->currTLIValidUntil: where that timeline ends.

in the reader and reuses it if one of the fast checks passes:

- Page already loaded. The reader already holds the requested page, so
nothing left to choose.
- Current timeline, moving forward. The cached currTLI is the current
server tli and the read goes forward. Keep the cached value.
- Historical timeline, before its end. The cached timeline is historical,
and the read stays before the segment where that timeline ended. It's also
kept.

The condition checks here are to ensure reading from the cached timeline is
safe. For the second fast path, reading forward is safe since the future
belongs to the current timeline. However, seeking backward is not the case
because a timeline only has files from the segment where it started;
earlier ones exist only under an older timeline's name. It means that
looking back could cross the timeline's beginning, which is hard to know
and prevent because the reader does not remember the onset of a timeline.
So enforce the forward locking rule. The problem here is that the rule is
missing from the third historical timeline case and the crossing boundary
issue is also possible for it. Currently, it only protects the safe read
from the end boundary of the timeline derived from currTLIValidUntil.

/*
* If we're just reading pages from a previously validated historical
* timeline and the timeline we're reading from is valid until the end of
* the current segment we can just keep reading.
*/
if (XLogRecPtrIsValid(state->currTLIValidUntil) &&
state->currTLI != currTLI &&
state->currTLI != 0 &&
((wantPage + wantLength) / state->segcxt.ws_segsize) <
(state->currTLIValidUntil / state->segcxt.ws_segsize))
return;

This shortcut dates back to 1148e22a82e, but the backend find-and-rewind
path was not exposed for a while. That changed when 2258e76f90b added
pg_walinspect and made XLogFindNextRecord() available to backend code.
XLogFindNextRecord() reads a record and then rewinds to the beginning of
that, which makes crossing a timeline's beginning possible.

while (XLogReadRecord(state, errormsg) != NULL)
{
/* past the record we've found, break out */
if (RecPtr <= state->ReadRecPtr)
{
/* Rewind the reader to the beginning of the last record. */
found = state->ReadRecPtr;
XLogBeginRead(state, found);
return found;
}
}

The attached test serves as a reproducer for the issue. Consider this case.
Timeline 1 is promoted to timeline 2 part way through segment N+1. Later,
timeline 2 is promoted to timeline 3 in a later segment, and the server is
now on timeline 3. A record R starts in segment N and ends in segment N+1:

segment: N N+1 … later
timeline 1: │ TLI1 │ TLI1 │
timeline 2: │ TLI2 │ TLI2 │ TLI2 │
timeline 3: │ TLI3 │ …
record R: ────┼────>

Segment N exists only as a TLI 1 file, segment N + 1 is read from TLI 2's
copy. Now run pg_get_wal_record_info() at R's start:

- XLogFindNextRecord() reads R from start to end. It reads segment N from
TLI 1, then segment N+1 from TLI 2. The reader now caches TLI 2 as a
historical timeline, and its last read page is in N+1.
- It rewinds to R's start. The read position moves back to segment N, but
the cached timeline is still 2.
- Reading R again asks for a page in segment N. The fast path check only
asks whether N is before the end of TLI 2. It is, so the check keeps TLI 2.
- The reader tries to open TLI 2's file for segment N, which never existed.
It fails with "requested WAL segment … has already been removed", even
though TLI 1's file for segment N is still in pg_wal.

2) The proposed fix
The simple and picked fix is adding the same forward reading rule to the
third check. The cons of this fix is preventing some safe backward reading
that does not exceed the segment boundary. A more precise fix is to let the
reader remember the start of the last timeline it reads from. However, not
sure how much that buys at the cost of extra bookkeeping given that reading
backward is rare.

[1]
https://www.postgresql.org/message-id/CABPTF7W0s_XHGkbsWdVaGs5sBefePXmG64i3RY0FsdU=b_1xwA@mail.gmail.com

--
Regards,
Xuneng Zhou
HighGo Software Co., Ltd.