Experimenting with transactional memory for SERIALIZABLE - Mailing list pgsql-hackers

Hello hackers,

Here's a *highly* experimental patch set that tries to skip the LWLock
protocol in predicate.c and use HTM[1] instead.  HTM is itself a sort
of hardware-level implementation of SSI for shared memory.  My
thinking was that if your workload already suits the optimistic nature
of SSI, perhaps it could make sense to go all-in and remove the rather
complicated pessimistic locking it's built on top of.  It falls back
to an LWLock-based path at compile time if you don't build with
--enable-htm, or at runtime if a startup test discovered that your CPU
doesn't have the Intel TSX instruction set (microarchitectures older
than Skylake, and some mobile and low power variants of current ones),
or if a hardware transaction is aborted for various reasons.

The good news is that it seems to produce correct results in simple
tests (well, some lock-held-by-me assertions can fail in an
--enable-cassert build, that's trivial to fix).  The bad news is that
it doesn't perform very well yet, and I think the reason for that is
that there are some inherently serial parts of the current design that
cause frequent conflicts.  In particular, the
FinishedSerializableTransactions list, protected by
SerializableFinishedListLock, produces a stream of conflicts, and
falls back to the traditional behaviour which involves long lock wait
queues and thereby more HTM conflicts.  I think we probably need a
more concurrent way to release SSI transactions, entirely independent
of this HTM experiment.  There's another point of serialisation at
snapshot acquisition time, which may be less avoidable; I don't know.
For much of the code that runs between snapshot acquisition and
transaction release, we really only care about touching memory
directly related to the SQL objects we touch in our SQL transaction,
and the other SQL transactions which have also touched them.  The
question is whether it's possible to get to a situation where
non-overlapping read/write sets at the SQL level don't cause conflicts
at the memory level and everything goes faster, or whether the SSI
algorithm is somehow inherently unsuitable for running on top of, erm,
SSI-like technology.  It seems like a potentially interesting research
project.

Here's my one paragraph introduction to HTM programming:  Using the
wrapper macros from my 0001 patch, you call pg_htm_begin(), and if
that returns true you're in a memory transaction and should eventually
call pg_htm_commit() or pg_htm_abort(), and if it returns false your
transaction has aborted and you need to fall back to some other
strategy.  (Retrying is also an option, but the reason codes are
complicated, and progress is not guaranteed, so introductions to the
topic often advise going straight to a fallback.)  No other thread is
allowed to see your changes to memory until you commit, and if you
abort (explicitly, due to lack of cache for uncommitted changes, due
to a serialisation conflict, or due to other internal details possibly
known only to Intel), all queued changes to memory are abandoned, and
control returns at pg_htm_begin(), a bit like the way setjmp() returns
non-locally when you call longjmp().  There are plenty of sources to
read about this stuff in detail, but for a very gentle introduction I
recommend Maurice Herlihy's 2-part talk[2][3] (the inventor of this
stuff at DEC in the early 90s), despite some strange claims he makes
about database hackers.

In theory this should work on POWER and future ARM systems too, with a
bit more work, but I haven't looked into that.  There are doubtless
many other applications for this type of technology within PostgreSQL.
Perhaps some more fruitful.

[1] https://en.wikipedia.org/wiki/Transactional_memory
[2] https://www.youtube.com/watch?v=S3Fx-7avfs4
[3] https://www.youtube.com/watch?v=94ieceVxSHs