Re: amcheck (B-Tree integrity checking tool)

On Fri, Oct 14, 2016 at 04:56:39PM -0700, Peter Geoghegan wrote:
> On Mon, Feb 29, 2016 at 4:09 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> > To recap, the extension adds some SQL-callable functions that verify
> > certain invariant conditions hold within some particular B-Tree index.
> > These are the conditions that index scans rely on always being true.
> > The tool's scope may eventually cover other AMs, including heapam, but
> > nbtree seems like the best place to start.
>
> Noah and I discussed possible future directions for amcheck in person
> recently. I would like to get Noah's thoughts again here on how a tool
> like amcheck might reasonably target other access methods for
> verification. In particular, the heapam. MultiXacts were mentioned as
> a structure that could receive verification in a future iteration of
> this tool, but I lack expertise there.

Yes, a heap checker could examine plenty of things. Incomplete list:

- Detect impossible conditions in the hint bits. A tuple should not have both
HEAP_XMAX_COMMITTED and HEAP_XMAX_INVALID. Every tuple bearing
HEAP_ONLY_TUPLE should bear HEAP_UPDATED. HEAP_HASVARWIDTH should be true
if and only if the tuple has a non-NULL value in a negative-typlen column,
possibly a dropped column. A tuple should not have both HEAP_KEYS_UPDATED
and HEAP_XMAX_LOCK_ONLY.

- Report evidence of upgrades from older versions. If the tool sees
HEAP_MOVED_IN or HEAP_MOVED_OFF, it can report that the cluster was
binary-upgraded from 8.3 or 8.4. If the user did not upgrade from such a
version, the user should assume corruption.

- Check VARSIZE() of each variable-length datum. Corrupt lengths might direct
you to seek past the end of the tuple, or they might imply excess free space
at the end of the tuple.

- Verify agreement between CLOG, MULTIXACT, and hint bits. If the hint bits
include HEAP_XMAX_LOCK_ONLY, the multixact should not contain a
MultiXactStatusUpdate member. README.tuplock documents other invariants.
If the tool sees a tuple passing HEAP_LOCKED_UPGRADED, it can report that
the cluster was binary-upgraded from a version in [8.3, 9.1].

- Verify that TOAST pointers (in non-dropped columns of visible tuples) point
to valid data in the TOAST relation. This is much more expensive than the
other checks I've named, so it should be optional.

- If VM_ALL_VISIBLE() or VM_ALL_FROZEN() passes for a particular page, verify
that the visibility data stored in the page is compatible with that claim.

- Examine PageHeaderData values. If pd_checksum is non-zero in a cluster with
checksums disabled, the cluster was binary-upgraded from [8.3, 9.2].

> I've placed a lot of emphasis on the importance of having a
> low-overhead verification process, particularly in terms of the
> strength of heavyweight lock that the verification process requires.
> Ideally, it would be possible to run any new verification process in a
> fairly indiscriminate way with only limited impact on live production
> systems.

I suspect you could keep heap checker overhead similar to the cost of "SELECT
count(*) FROM table_name".