Sequences, txids, and serial order of transactions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Sequences, txids, and serial order of transactions

Christian Ohler
Hi,

we have a use case similar to auditing packages like pgMemento or Audit Trigger 91plus – we are looking to keep an ordered history of certain write transactions.  I'm trying to understand the trade-offs between different ways of getting that order, i.e., assigning numbers to transactions (ideally strictly monotonic, modulo concurrency).  All of our transactions are serializable (for now).

The two main candidates I'm aware of are txid_current() or nextval() of a sequence; but perhaps there are other mechanisms we should be considering.

Some observations and questions from my investigations so far (and please correct me if any of this is wrong):

(1) managing a counter in a table would essentially eliminate concurrency, so we're not too interested in that

(2) the orders produced by txid_current and a sequence can be different (unsurprisingly).  (If it was desirable to make them match, we could probably do so by briefly holding a lock while we call both txid_current and nextval – seems like this shouldn't limit concurrency too much.  Or would it?  Is one of them potentially slow?)

(3) logical replication has mechanisms to keeps sequences in sync, but not txid_current (unsurprisingly)

(4) behaviors like http://permalink.gmane.org/gmane.comp.db.postgresql.bugs/35636 make me think that monotonicity of txid_current is not something we should bet on

(5) Postgres can give us a "high watermark" ("no transactions with IDs below this number are still in-flight") for txid_current (using txid_snapshot_xmin(txid_current_snapshot())), but has no equivalent feature for sequences

(6) neither txid_current nor a sequence give us a valid serial order of the transactions

(7) given that we can't get a valid serial order, what guarantees can we get from the ordering?  I'm not entirely sure what to look for, but at a minimum, it seems like we want writes that clobber each other to be correctly ordered.  Are they, for both txid_current and for sequences?  My guess was "yes" for txids (seems intuitive but just a guess) and "no" for sequences (because https://www.postgresql.org/docs/current/static/functions-sequence.html mentions that sequences are non-transactional); but for sequences, I couldn't immediately construct a counterexample and am wondering whether that's by design.  Specifically, it seems that Postgres acquires the snapshot for the transaction (if it hasn't already) when I call nextval(), and as long as the snapshot is acquired before the sequence is incremented, I suspect that this guarantees ordering writes.  Does it?

(8) ...and is the snapshot acquired before or after the increment?  (Is it acquired as soon as Postgres sees SELECT, before even evaluating nextval()?  I think that's what I'm seeing.  Is that something we can rely on, or should we SELECT txid_current_snapshot() before SELECT nextval() to be on the safe side?)

(9) are there other important properties that one order satisfies but the other doesn't, or that neither satisfies but that we should be aware of?


(3) and (4) seem like strong reasons to go with a sequence, as long as we can live without (5) and figure out (7) and (8).

Any help appreciated,
Christian.

Reply | Threaded
Open this post in threaded view
|

Re: Sequences, txids, and serial order of transactions

Alban Hertroys-4

> On 12 Jun 2016, at 4:03, Christian Ohler <[hidden email]> wrote:

> we have a use case similar to auditing packages like pgMemento or Audit Trigger 91plus – we are looking to keep an ordered history of certain write transactions.  I'm trying to understand the trade-offs between different ways of getting that order, i.e., assigning numbers to transactions (ideally strictly monotonic, modulo concurrency).  All of our transactions are serializable (for now).

> (2) the orders produced by txid_current and a sequence can be different (unsurprisingly).  (If it was desirable to make them match, we could probably do so by briefly holding a lock while we call both txid_current and nextval – seems like this shouldn't limit concurrency too much.  Or would it?  Is one of them potentially slow?)

I'm aware of only 2 cases that those can have a different order:
1. The txid or the sequence wraps
2. The txid of a transaction exists some time already when the sequence's nextval() gets called. A later transaction (higher txid) running in parallel could request a nextval() in between those moments.

I think that situation 1 can be caught (the few times it occurs). Situation 2 is probably what bothers you? As long as the request for nextval() is early in the transaction, a wait-lock shouldn't block other waiting transactions for long.

To make sure, I would run some tests comparing running enough parallel transactions calling a sequence's nextval() both with and without the lock. The first of those will also give you some insight in how bad the transaction ordering vs. sequence ordering problem actually is.
That is, unless you're perhaps overcomplicating your problem (see my answer to (6)).

> (5) Postgres can give us a "high watermark" ("no transactions with IDs below this number are still in-flight") for txid_current (using txid_snapshot_xmin(txid_current_snapshot())), but has no equivalent feature for sequences

How would it know whether a sequence number is still in use? For example, I have a process @work where I use a database sequence to distinguish between batches of data in a user's HTTP session. Nothing of that is in the database, but the sequence is most certainly in use, across different database sessions.

> (6) neither txid_current nor a sequence give us a valid serial order of the transactions

That depends on what you consider a transaction for your application. Do you care about the order that data got manipulated in, or do you care in what order the surrounding database transactions were created?
Usually, people only care about the first, for which a sequence should be just fine. The second is usually only relevant for systems that are closely tied to the database internals, such as replication systems.

> (7) given that we can't get a valid serial order, what guarantees can we get from the ordering?  I'm not entirely sure what to look for, but at a minimum, it seems like we want writes that clobber each other to be correctly ordered.  Are they, for both txid_current and for sequences?  My guess was "yes" for txids (seems intuitive but just a guess) and "no" for sequences (because https://www.postgresql.org/docs/current/static/functions-sequence.html mentions that sequences are non-transactional); but for sequences, I couldn't immediately construct a counterexample and am wondering whether that's by design.  Specifically, it seems that Postgres acquires the snapshot for the transaction (if it hasn't already) when I call nextval(), and as long as the snapshot is acquired before the sequence is incremented, I suspect that this guarantees ordering writes.  Does it?

As I understand it, sequences have to be non-transactional to be able to guarantee correct ordering.

Calling nextval() will increment the sequence, but does not relate it to the transaction at that point. The select statement that does the call to nextval() receives the value from the sequence and is part of the transaction. That links them together, as long as you don't use that sequence value outside that transaction.

Alban Hertroys
--
If you can't see the forest for the trees,
cut the trees and you'll find there is no forest.



--
Sent via pgsql-general mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general
Reply | Threaded
Open this post in threaded view
|

Re: Sequences, txids, and serial order of transactions

Tom Lane-2
In reply to this post by Christian Ohler
Christian Ohler <[hidden email]> writes:
> we have a use case similar to auditing packages like pgMemento or Audit
> Trigger 91plus – we are looking to keep an ordered history of certain write
> transactions.  I'm trying to understand the trade-offs between different
> ways of getting that order, i.e., assigning numbers to transactions
> (ideally strictly monotonic, modulo concurrency).  All of our transactions
> are serializable (for now).
> ...

> (4) behaviors like
> http://permalink.gmane.org/gmane.comp.db.postgresql.bugs/35636 make me
> think that monotonicity of txid_current is not something we should bet on

Not following why you think bugs might break txids but not sequences.

> (7) given that we can't get a valid serial order, what guarantees can we
> get from the ordering?  I'm not entirely sure what to look for, but at a
> minimum, it seems like we want writes that clobber each other to be
> correctly ordered.

Um ... if you're running the transactions in serializable mode, there
aren't going to *be* any "writes that clobber each other".  Maybe you
should clarify what you're hoping to accomplish exactly.

> Specifically, it seems that Postgres acquires the
> snapshot for the transaction (if it hasn't already) when I call nextval(),
> and as long as the snapshot is acquired before the sequence is incremented,
> I suspect that this guarantees ordering writes.  Does it?

If you're doing "BEGIN; SELECT nextval(); ..." in each transaction, then
yes, the SELECT would acquire a snapshot before calling nextval, but no,
that doesn't mean anything with respect to the apparent commit order of
the transactions.  I think you are confusing snapshots with XIDs.

A look at the nextval() source code says that, if the sequence doesn't
have caching enabled and is WAL-logged, and we don't already have an XID,
then we acquire one inside the buffer lock on the sequence's page.  This
would explain why you are seeing txid_current and the sequence value as
always advancing in lockstep.  It doesn't seem like something to rely on
though; somebody might decide to move that out of the buffer critical
section to improve concurrency.  In any case, neither txid_current nor the
sequence value will provide any reliable guide to the apparent commit
order of concurrently-running transactions.

                        regards, tom lane


--
Sent via pgsql-general mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general
Reply | Threaded
Open this post in threaded view
|

Re: Sequences, txids, and serial order of transactions

Kevin Grittner-7
In reply to this post by Christian Ohler
On Sat, Jun 11, 2016 at 9:03 PM, Christian Ohler <[hidden email]> wrote:

> we have a use case similar to auditing packages like pgMemento or Audit
> Trigger 91plus – we are looking to keep an ordered history of certain write
> transactions.  I'm trying to understand the trade-offs between different
> ways of getting that order, i.e., assigning numbers to transactions (ideally
> strictly monotonic, modulo concurrency).  All of our transactions are
> serializable (for now).

The guarantee that serializable transactions provide is that for
any group of concurrent serializable transactions which
successfully commit, there is some serial (one-at-a-time) order in
which they could have been run which would provide the same
results.  Note that in PostgreSQL that order is not necessarily
commit order.  So the first question is whether you want the order
of the numbers to match the apparent order of execution of the
serializable transactions which committed or the commit order.
Those almost certainly won't always be the same.

If you are satisfied with the commit order, there is a way to do
that with minimal loss of concurrency.  As the very last thing
before commit, take out an exclusive transactional advisory lock
(pg_advisory_xact_lock):

https://www.postgresql.org/docs/current/static/functions-admin.html#FUNCTIONS-ADVISORY-LOCKS-TABLE

Under cover of that lock, assign the number.  You may need to write
some custom code for assigning that across multiple backends with
the right characteristics (e.g., the database may need to make a
request of some external service for the number).  There is some
actual serialization of this small bit at the end of the
transaction, but if you're careful it can be a very small window of
time.

If you want the numbers to be assigned in the apparent order of
execution of the serializable transactions, I'm afraid that I don't
know of any good solution for that right now.  There has been some
occasional talk of providing a way to read the AOoE, but nothing
has come of it so far.

--
Kevin Grittner
EDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


--
Sent via pgsql-general mailing list ([hidden email])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general