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@heroku.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
andonly if the tuple has a non-NULL value in a negative-typlen column, possibly a dropped column.  A tuple should not
haveboth 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
thatthe cluster was binary-upgraded from 8.3 or 8.4.  If the user did not upgrade from such a version, the user should
assumecorruption.
 

- Check VARSIZE() of each variable-length datum.  Corrupt lengths might direct you to seek past the end of the tuple,
orthey 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
shouldnot contain a MultiXactStatusUpdate member.  README.tuplock documents other invariants. If the tool sees a tuple
passingHEAP_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.
Thisis 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
pageis compatible with that claim.
 

- Examine PageHeaderData values.  If pd_checksum is non-zero in a cluster with checksums disabled, the cluster was
binary-upgradedfrom [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".