Subject: Re: logical decoding and replication of sequences, take 2

From: Robert Haas <[email-masked]>
Date: Tue, 13 Feb 2024 22:07:11 +0530

On Sun, Jan 28, 2024 at 1:07 AM Tomas Vondra
<[email-masked]> wrote:
> Right, locks + apply in commit order gives us this guarantee (I can't
> think of a case where it wouldn't be the case).

I couldn't find any cases of inadequate locking other than the one I mentioned.

> Doesn't the whole logical replication critically depend on the commit
> order? If you decide to arbitrarily reorder/delay the transactions, all
> kinds of really bad things can happen. That's a generic problem, it
> applies to all kinds of objects, not just sequences - a parallel apply
> would need to detect this sort of dependencies (e.g. INSERT + DELETE of
> the same key), and do something about it.

Yes, but here I'm not just talking about the commit order. I'm talking
about the order of applying non-transactional operations relative to
commits.

Consider:

T1: CREATE SEQUENCE s;
T2: BEGIN;
T2: SELECT nextval('s');
T3: SELECT nextval('s');
T2: ALTER SEQUENCE s INCREMENT 2;
T2: SELECT nextval('s');
T2: COMMIT;

The commit order is T1 < T3 < T2, but T3 makes no transactional
changes, so the commit order is really just T1 < T2. But it's
completely wrong to say that all we need to do is apply T1 before we
apply T2. The correct order of application is:

1. T1.
2. T2's first nextval
3. T3's nextval
4. T2's transactional changes (i.e. the ALTER SEQUENCE INCREMENT and
the subsequent nextval)

In other words, the fact that some sequence changes are
non-transactional creates ordering hazards that don't exist if there
are no non-transactional changes. So in that way, sequences are
different from table modifications, where applying the transactions in
order of commit is all we need to do. Here we need to apply the
transactions in order of commit and also apply the non-transactional
changes at the right point in the sequence. Consider the following
alternative apply sequence:

1. T1.
2. T2's transactional changes (i.e. the ALTER SEQUENCE INCREMENT and
the subsequent nextval)
3. T3's nextval
4. T2's first nextval

That's still in commit order. It's also wrong.

Imagine that you commit this patch and someone later wants to do
parallel logical apply. So every time they finish decoding a
transaction, they stick it in a queue to be applied by the next
available worker. But, non-transactional changes are very simple, so
we just directly apply those in the main process. Well, kaboom! But
now this can happen with the above example.

1. Decode T1. Add to queue for apply.
2. Before the (idle) apply worker has a chance to pull T1 out of the
queue, decode the first nextval and try to apply it.

Oops. We're trying to apply a modification to a sequence that hasn't
been created yet. I'm not saying that this kind of hypothetical is a
reason not to commit the patch. But it seems like we're not on the
same page about what the ordering requirements are here. I'm just
making the argument that those non-transactional operations actually
act like mini-transactions. They need to happen at the right time
relative to the real transactions. A non-transactional operation needs
to be applied after any transactions that commit before it is logged,
and before any transactions that commit after it's logged.

> Yes, I think this is a bug in handling of owned sequences - from the
> moment the "ALTER TABLE ... SET UNLOGGED" is executed, the two sessions
> generate duplicate values (until the S1 is committed, at which point the
> values generated in S2 get "forgotten").
>
> It seems we end up updating both relfilenodes, which is clearly wrong.
>
> Seems like a bug independent of the decoding, IMO.

Yeah.

-- 
Robert Haas
EDB: http://www.enterprisedb.com

---

From: Tomas Vondra <[email-masked]>
Date: Wed, 14 Feb 2024 17:51:37 +0100

> T2: ALTER SEQUENCE s INCREMENT 2;

It's not clear to me if you're talking about nextval() that happens to
generate WAL, or nextval() covered by WAL generated by a previous call.

I'm going to assume it's the former, i.e. nextval() that generated WAL
describing the *next* sequence chunk, because without WAL there's
nothing to apply and therefore no issue with T3 ordering.

The way I think about non-transactional sequence changes is as if they
were tiny transactions that happen "fully" (including commit) at the LSN
where the LSN change is logged.

> 4. T2's transactional changes (i.e. the ALTER SEQUENCE INCREMENT and

Is that quite true? If T3 generated WAL (for the nextval call), it will
be applied at that particular LSN. AFAIK that guarantees it happens
after the first T2 change (which is also non-transactional) and before
the transactional T2 change (because that creates a new relfilenode).

> That's still in commit order. It's also wrong.

Yes, this would be wrong. Thankfully the apply is not allowed to reorder
the changes like this, because that's not what "non-transactional" means
in this context.

It does not mean we can arbitrarily reorder the changes, it only means
the changes are applied as if they were independent transactions (but in
the same order as they were executed originally). Both with respect to
the other non-transactional changes, and to "commits" of other stuff.

(for serial apply, at least)

> and before any transactions that commit after it's logged.

How is this issue specific to sequences? AFAIK this is a general problem
with transactions that depend on each other. Consider for example this:

T1: INSERT INTO t (id) VALUES (1);
T2: DELETE FROM t WHERE id = 1;

If you parallelize this in a naive way, maybe T2 gets applied before T1.
In which case the DELETE won't find the row yet.

There's different ways to address this. You can detect this type of
conflicts (e.g. when a DELETE that doesn't find a match), drain the
apply queue and retry the transaction. Or you may compare keysets of the
transactions and make sure the apply waits until the conflicting one
gets fully applied first.

AFAIK for sequences it's not any different, except the key we'd have to
compare is the sequence itself.

regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

---

From: Robert Haas <[email-masked]>
Date: Thu, 15 Feb 2024 09:46:30 +0530

> where the LSN change is logged.

100% this.

> the other non-transactional changes, and to "commits" of other stuff.

Right, this is very important and I agree completely.

I'm feeling more confident about this now that I heard you say that
stuff -- this is really the key issue I've been worried about since I
first looked at this, and I wasn't sure that you were in agreement,
but it sounds like you are. I think we should (a) fix the locking bug
I found (but that can be independent of this patch) and (b) make sure
that this patch documents the points from the quoted material above so
that everyone who reads the code (and maybe tries to enhance it) is
clear on what the assumptions are.

(I haven't checked whether it documents that stuff or not. I'm just
saying it should, because I think it's a subtlety that someone might
miss.)

---

From: Tomas Vondra <[email-masked]>
Date: Thu, 15 Feb 2024 21:26:59 +0100

> saying it should, because I think it's a subtlety that someone might

Thanks for thinking about these issues with reordering events. Good we
seem to be in agreement and that you feel more confident about this.
I'll check if there's a good place to document this.

For me, the part that I feel most uneasy about is the decoding while the
snapshot is still being built (and can flip to consistent snapshot
between the relfilenode creation and sequence change, confusing the
logic that decides which changes are transactional).

It seems "a bit weird" that we either keep the "simple" logic that may
end up with incorrect "non-transactional" result, but happens to then
work fine because we immediately discard the change.

But it still feels better than the alternative, which requires us to
start decoding stuff (relfilenode creation) before building a proper
snapshot is consistent, which we didn't do before - or at least not in
this particular way. While I don't have a practical example where it
would cause trouble now, I have a nagging feeling it might easily cause
trouble in the future by making some new features harder to implement.

regards

---

From: Robert Haas <[email-masked]>
Date: Tue, 20 Feb 2024 10:30:01 +0530

> trouble in the future by making some new features harder to implement.

I don't understand the issues here well enough to comment. Is there a
good write-up someplace I can read to understand the design here?

Is the rule that changes are transactional if and only if the current
transaction has assigned a new relfilenode to the sequence?

Why does the logic get confused if the state of the snapshot changes?

My naive reaction is that it kinda sounds like you're relying on two
different mistakes cancelling each other out, and that might be a bad
idea, because maybe there's some situation where they don't. But I
don't understand the issue well enough to have an educated opinion at
this point.

---

From: Dilip Kumar <[email-masked]>
Date: Tue, 20 Feb 2024 13:32:36 +0530

> transaction has assigned a new relfilenode to the sequence?

Yes, thats the rule.

> Why does the logic get confused if the state of the snapshot changes?

The rule doesn't get changed, but the way this identification is
implemented at the decoding gets confused and assumes transactional as
non-transactional.  The identification of whether the sequence is
transactional or not is implemented based on what WAL we have decoded
from the particular transaction and whether we decode a particular WAL
or not depends upon the snapshot state (it's about what we decode not
necessarily what we sent).  So if the snapshot state changed the
mid-transaction that means we haven't decoded the WAL which created a
new relfilenode but we will decode the WAL which is operating on the
sequence.  So here we will assume the change is non-transaction
whereas it was transactional because we did not decode some of the
changes of transaction which we rely on for identifying whether it is
transactional or not.

> don't understand the issue well enough to have an educated opinion at

I would say the first one is a mistake in identifying the
transactional as non-transactional during the decoding and that
mistake happens only when we decode the transaction partially.  But we
never stream the partially decoded transactions downstream which means
even though we have made a mistake in decoding it, we are not
streaming it so our mistake is not getting converted into a real
problem.  But again I agree there is a temporary wrong decision and if
we try to do something else based on this decision then it could be an
issue.

You might be interested in more detail [1] where I first reported this
problem and also [2] where we concluded why this is not creating a
real problem.

[1] https://www.postgresql.org/message-id/CAFiTN-vAx-Y%2B19ROKOcWnGf7ix2VOTUebpzteaGw9XQyCAeK6g%40mail.gmail.com
[2] https://www.postgresql.org/message-id/CAFiTN-sYpyUBabxopJysqH3DAp4OZUCTi6m_qtgt8d32vDcWSA%40mail.gmail.com

-- 
Regards,
Dilip Kumar

---

From: Robert Haas <[email-masked]>
Date: Tue, 20 Feb 2024 15:38:23 +0530

> [2] https://www.postgresql.org/message-id/CAFiTN-sYpyUBabxopJysqH3DAp4OZUCTi6m_qtgt8d32vDcWSA%40mail.gmail.com

Thanks. Dilip and I just spent a lot of time talking this through on a
call. One of the key bits of logic is here:

+ /* Skip the change if already processed (per the snapshot). */
+ if (transactional &&
+ !SnapBuildProcessChange(builder, xid, buf->origptr))
+ return;
+ else if (!transactional &&
+ (SnapBuildCurrentState(builder) != SNAPBUILD_CONSISTENT ||
+   SnapBuildXactNeedsSkip(builder, buf->origptr)))
+ return;

As a stylistic note, I think this would be mode clear if it were
written if (transactional) { if (!SnapBuildProcessChange()) return; }
else { if (something else) return; }.

Now, on to correctness. It's possible for us to identify a
transactional change as non-transactional if smgr_decode() was called
for the relfilenode before SNAPBUILD_FULL_SNAPSHOT was reached. In
that case, if !SnapBuildProcessChange() would have been true, then we
need SnapBuildCurrentState(builder) != SNAPBUILD_CONSISTENT ||
SnapBuildXactNeedsSkip(builder, buf->origptr) to also be true.
Otherwise, we'll process this change when we wouldn't have otherwise.
But Dilip made an argument to me about this which seems correct to me.
snapbuild.h says that SNAPBUILD_CONSISTENT is reached only when we
find a point where any transaction that was running at the time we
reached SNAPBUILD_FULL_SNAPSHOT have finished. So if this transaction
is one for which we incorrectly identified the sequence change as
non-transactional, then we cannot be in the SNAPBUILD_CONSISTENT state
yet, so SnapBuildCurrentState(builder) != SNAPBUILD_CONSISTENT will be
true and hence whole "or" condition we'll be true and we'll return. So
far, so good.

I think, anyway. I haven't comprehensively verified that the comment
in snapbuild.h accurately reflects what the code actually does. But if
it does, then presumably we shouldn't see a record for which we might
have mistakenly identified a change as non-transactional after
reaching SNAPBUILD_CONSISTENT, which seems to be good enough to
guarantee that the mistake won't matter.

However, the logic in smgr_decode() doesn't only care about the
snapshot state. It also cares about the fast-forward flag:

+ if (SnapBuildCurrentState(builder) < SNAPBUILD_FULL_SNAPSHOT ||
+ ctx->fast_forward)
+ return;

Let's say fast_forward is true. Then smgr_decode() is going to skip
recording anything about the relfilenode, so we'll identify all
sequence changes as non-transactional. But look at how this case is
handled in seq_decode():

+ if (ctx->fast_forward)
+ {
+ /*
+ * We need to set processing_required flag to notify the sequence
+ * change existence to the caller. Usually, the flag is set when
+ * either the COMMIT or ABORT records are decoded, but this must be
+ * turned on here because the non-transactional logical message is
+ * decoded without waiting for these records.
+ */
+ if (!transactional)
+ ctx->processing_required = true;
+
+ return;
+ }

This seems suspicious. Why are we testing the transactional flag here
if it's guaranteed to be false? My guess is that the person who wrote
this code thought that the flag would be accurate even in this case,
but that doesn't seem to be true. So this case probably needs some
more thought.

It's definitely not great that this logic is so complicated; it's
really hard to verify that all the tests match up well enough to keep
us out of trouble.

---

From: Dilip Kumar <[email-masked]>
Date: Tue, 20 Feb 2024 16:32:03 +0530

> + ctx->processing_required = true;

It appears that the 'processing_required' flag was introduced as part
of supporting upgrades for logical replication slots. Its purpose is
to determine whether a slot is fully caught up, meaning that there are
no pending decodable changes left before it can be upgraded.

So now if some change was transactional but we have identified it as
non-transaction then we will mark this flag  'ctx->processing_required
= true;' so we temporarily set this flag incorrectly, but even if the
flag would have been correctly identified initially, it would have
been set again to true in the DecodeTXNNeedSkip() function regardless
of whether the transaction is committed or aborted. As a result, the
flag would eventually be set to 'true', and the behavior would align
with the intended logic.

But I am wondering why this flag is always set to true in
DecodeTXNNeedSkip() irrespective of the commit or abort. Because the
aborted transactions are not supposed to be replayed?  So if my
observation is correct that for the aborted transaction, this
shouldn't be set to true then we have a problem with sequence where we
are identifying the transactional changes as non-transaction changes
because now for transactional changes this should depend upon commit
status.

On another thought, can there be a situation where we have identified
this flag wrongly as non-transaction and set this flag, and the
commit/abort record never appeared in the WAL so never decoded? That
can also lead to an incorrect decision during the upgrade.

---

From: Amit Kapila <[email-masked]>
Date: Wed, 21 Feb 2024 12:06:30 +0530

On Wed, Feb 14, 2024 at 10:21 PM Tomas Vondra
<[email-masked]> wrote:
> the same order as they were executed originally).
>

In this regard, I have another scenario in mind where the apply order
could be different for the changes in the same transactions. For
example,

Transaction T1
Begin;
Insert ..
Insert ..
nextval .. --consider this generates WAL
..
Insert ..
nextval .. --consider this generates WAL

In this case, if the nextval operations will be applied in a different
order (aka before Inserts) then there could be some inconsistency.
Say, if, it doesn't follow the above order during apply then a trigger
fired on both pub and sub for each row insert that refers to the
current sequence value to make some decision could have different
behavior on publisher and subscriber. If this is not how the patch
will behave then fine but otherwise, isn't this something that we
should be worried about?

-- 
With Regards,
Amit Kapila.

---

From: Dilip Kumar <[email-masked]>
Date: Wed, 21 Feb 2024 13:05:58 +0530

> because now for transactional changes this should depend upon commit

I have checked this case with Amit Kapila.  So it seems in the cases
where we have sent the prepared transaction or streamed in-progress
transaction we would need to send the abort also, and for that reason,
we are setting 'ctx->processing_required' as true so that if these
WALs are not streamed we do not allow upgrade of such slots.