Subject: Re: Conflict Detection and Resolution

From: shveta malik <[email-masked]>
Date: Wed, 3 Jul 2024 11:00:43 +0530

On Wed, Jul 3, 2024 at 10:47 AM Dilip Kumar <[email-masked]> wrote:
>
> On Tue, Jul 2, 2024 at 2:40 PM shveta malik <[email-masked]> wrote:
> >
> > On Wed, Jun 19, 2024 at 1:52 PM Dilip Kumar <[email-masked]> wrote:
> > >
> > > On Tue, Jun 18, 2024 at 3:29 PM shveta malik <[email-masked]> wrote:
> > > > On Tue, Jun 18, 2024 at 11:34 AM Dilip Kumar <[email-masked]> wrote:
> > > >
> > > > I tried to work out a few scenarios with this, where the apply worker
> > > > will wait until its local clock hits 'remote_commit_tts - max_skew
> > > > permitted'. Please have a look.
> > > >
> > > > Let's say, we have a GUC to configure max_clock_skew permitted.
> > > > Resolver is last_update_wins in both cases.
> > > > ----------------
> > > > 1) Case 1: max_clock_skew set to 0 i.e. no tolerance for clock skew.
> > > >
> > > > Remote Update with commit_timestamp = 10.20AM.
> > > > Local clock (which is say 5 min behind) shows = 10.15AM.
> > > >
> > > > When remote update arrives at local node, we see that skew is greater
> > > > than max_clock_skew and thus apply worker waits till local clock hits
> > > > 'remote's commit_tts - max_clock_skew' i.e. till 10.20 AM. Once the
> > > > local clock hits 10.20 AM, the worker applies the remote change with
> > > > commit_tts of 10.20AM. In the meantime (during wait period of apply
> > > > worker)) if some local update on same row has happened at say 10.18am,
> > > > that will applied first, which will be later overwritten by above
> > > > remote change of 10.20AM as remote-change's timestamp appear more
> > > > latest, even though it has happened earlier than local change.
> > >
> > > For the sake of simplicity let's call the change that happened at
> > > 10:20 AM change-1 and the change that happened at 10:15 as change-2
> > > and assume we are talking about the synchronous commit only.
> > >
> > > I think now from an application perspective the change-1 wouldn't have
> > > caused the change-2 because we delayed applying change-2 on the local
> > > node which would have delayed the confirmation of the change-1 to the
> > > application that means we have got the change-2 on the local node
> > > without the confirmation of change-1 hence change-2 has no causal
> > > dependency on the change-1.  So it's fine that we perform change-1
> > > before change-2 and the timestamp will also show the same at any other
> > > node if they receive these 2 changes.
> > >
> > > The goal is to ensure that if we define the order where change-2
> > > happens before change-1, this same order should be visible on all
> > > other nodes. This will hold true because the commit timestamp of
> > > change-2 is earlier than that of change-1.
> > >
> > > > 2)  Case 2: max_clock_skew is set to 2min.
> > > >
> > > > Remote Update with commit_timestamp=10.20AM
> > > > Local clock (which is say 5 min behind) = 10.15AM.
> > > >
> > > > Now apply worker will notice skew greater than 2min and thus will wait
> > > > till local clock hits 'remote's commit_tts - max_clock_skew' i.e.
> > > > 10.18 and will apply the change with commit_tts of 10.20 ( as we
> > > > always save the origin's commit timestamp into local commit_tts, see
> > > > RecordTransactionCommit->TransactionTreeSetCommitTsData). Now lets say
> > > > another local update is triggered at 10.19am, it will be applied
> > > > locally but it will be ignored on remote node. On the remote node ,
> > > > the existing change with a timestamp of 10.20 am will win resulting in
> > > > data divergence.
> > >
> > > Let's call the 10:20 AM change as a change-1 and the change that
> > > happened at 10:19 as change-2
> > >
> > > IIUC, although we apply the change-1 at 10:18 AM the commit_ts of that
> > > commit_ts of that change is 10:20, and the same will be visible to all
> > > other nodes.  So in conflict resolution still the change-1 happened
> > > after the change-2 because change-2's commit_ts is 10:19 AM.   Now
> > > there could be a problem with the causal order because we applied the
> > > change-1 at 10:18 AM so the application might have gotten confirmation
> > > at 10:18 AM and the change-2 of the local node may be triggered as a
> > > result of confirmation of the change-1 that means now change-2 has a
> > > causal dependency on the change-1 but commit_ts shows change-2
> > > happened before the change-1 on all the nodes.
> > >
> > > So, is this acceptable? I think yes because the user has configured a
> > > maximum clock skew of 2 minutes, which means the detected order might
> > > not always align with the causal order for transactions occurring
> > > within that time frame. Generally, the ideal configuration for
> > > max_clock_skew should be in multiple of the network round trip time.
> > > Assuming this configuration, we wouldn’t encounter this problem
> > > because for change-2 to be caused by change-1, the client would need
> > > to get confirmation of change-1 and then trigger change-2, which would
> > > take at least 2-3 network round trips.
> >
> > As we agreed, the subscriber should wait before applying an operation
> > if the commit timestamp of the currently replayed transaction is in
> > the future and the difference exceeds the maximum clock skew. This
> > raises the question: should the subscriber wait only for insert,
> > update, and delete operations when timestamp-based resolution methods
> > are set, or should it wait regardless of the type of remote operation,
> > the presence or absence of conflicts, and the resolvers configured?
> > I believe the latter approach is the way to go i.e. this should be
> > independent of CDR, though needed by CDR for better timestamp based
> > resolutions. Thoughts?
>
> Yes, I also think it should be independent of CDR.  IMHO, it should be
> based on the user-configured maximum clock skew tolerance and can be
> independent of CDR.

+1

> IIUC we would make the remote apply wait just
> before committing if the remote commit timestamp is ahead of the local
> clock by more than the maximum clock skew tolerance, is that correct?

+1 on condition to wait.

But I think we should make apply worker wait during begin
(apply_handle_begin) instead of commit. It makes more sense to delay
the entire operation to manage clock-skew rather than the commit
alone. And only then CDR's timestamp based resolution which are much
prior to commit-stage can benefit from this. Thoughts?

thanks
Shveta

---

From: Dilip Kumar <[email-masked]>
Date: Wed, 3 Jul 2024 11:29:25 +0530

> prior to commit-stage can benefit from this. Thoughts?

But do we really need to wait at apply_handle_begin()? I mean if we
already know the commit_ts then we can perform the conflict resolution
no?  I mean we should wait before committing because we are
considering this remote transaction to be in the future and we do not
want to confirm the commit of this transaction to the remote node
before the local clock reaches the record commit_ts to preserve the
causal order.  However, we can still perform conflict resolution
beforehand since we already know the commit_ts. The conflict
resolution function will be something like "out_version =
CRF(version1_commit_ts, version2_commit_ts)," so the result should be
the same regardless of when we apply it, correct?  From a performance
standpoint, wouldn't it be beneficial to perform as much work as
possible in advance? By the time we apply all the operations, the
local clock might already be in sync with the commit_ts of the remote
transaction.  Am I missing something?

However, while thinking about this, I'm wondering about how we will
handle the streaming of in-progress transactions. If we start applying
with parallel workers, we might not know the commit_ts of those
transactions since they may not have been committed yet. One simple
option could be to prevent parallel workers from applying in-progress
transactions when CDR is set up. Instead, we could let these
transactions spill to files and only apply them once we receive the
commit record.

--
Regards,
Dilip Kumar
EnterpriseDB: http://www.enterprisedb.com

---

From: Amit Kapila <[email-masked]>
Date: Wed, 3 Jul 2024 12:30:15 +0530

> transaction.  Am I missing something?

But waiting after applying the operations and before applying the
commit would mean that we need to wait with the locks held. That could
be a recipe for deadlocks in the system. I see your point related to
performance but as we are not expecting clock skew in normal cases, we
shouldn't be too much bothered on the performance due to this. If
there is clock skew, we expect users to fix it, this is just a
worst-case aid for users.

> transactions spill to files and only apply them once we receive the

Agreed, we should do it as you have suggested and document it.

-- 
With Regards,
Amit Kapila.

---

From: Dilip Kumar <[email-masked]>
Date: Wed, 3 Jul 2024 14:16:08 +0530

> worst-case aid for users.

But if we make it wait at the very first operation that means we will
not suck more decoded data from the network and wouldn't that make the
sender wait for the network buffer to get sucked in by the receiver?
Also, we already have a handling of parallel apply workers so if we do
not have an issue of deadlock there or if we can handle those issues
there we can do it here as well no?

---

From: Amit Kapila <[email-masked]>
Date: Wed, 3 Jul 2024 15:35:28 +0530

> sender wait for the network buffer to get sucked in by the receiver?

That would be true even if we wait just before applying the commit
record considering the transaction is small and the wait time is
large.

> there we can do it here as well no?

Parallel apply workers won't wait for a long time. There is some
similarity and in both cases, deadlock will be detected but chances of
such implementation-related deadlocks will be higher if we start
waiting for a random amount of times. The other possibility is that we
can keep a cap on the max clock skew time above which we will give
ERROR even if the user has configured wait. This is because anyway the
system will be choked (walsender won't be able to send more data,
vacuum on publisher won't be able to remove dead rows) if we wait for
longer times. But even with that, I am not sure if waiting after
holding locks is a good idea or gives us the benefit that is worth the
risk of deadlocks.

-- 
With Regards,
Amit Kapila.

---

From: shveta malik <[email-masked]>
Date: Wed, 3 Jul 2024 16:02:05 +0530

On Wed, Jul 3, 2024 at 11:29 AM Dilip Kumar <[email-masked]> wrote:
> no?

I would like to highlight one point here that the resultant data may
be different depending upon at what stage (begin or commit) we
conclude to wait. Example:

--max_clock_skew set to 0 i.e. no tolerance for clock skew.
--Remote Update with commit_timestamp = 10.20AM.
--Local clock (which is say 5 min behind) shows = 10.15AM.

Case 1: Wait during Begin:
When remote update arrives at local node, apply worker waits till
local clock hits 'remote's commit_tts - max_clock_skew' i.e. till
10.20 AM. In the meantime (during the wait period of apply worker) if
some local update on the same row has happened at say 10.18am (local
clock), that will be applied first. Now when apply worker's wait is
over, it will detect 'update_diffe'r conflict and as per
'last_update_win', remote_tuple will win as 10.20 is latest than
10.18.

Case 2: Wait during Commit:
When remote update arrives at local node, it finds no conflict and
goes for commit. But before commit, it waits till the local clock hits
10.20 AM. In the meantime (during wait period of apply worker)) if
some local update is trying to update the same row say at 10.18, it
has to wait (due to locks taken by remote update on that row) and
remote tuple will get committed first with commit timestamp of 10.20.
Then local update will proceed and will overwrite remote tuple.

So in case1, remote tuple is the final change while in case2, local
tuple is the final change.

thanks
Shveta

---

From: Dilip Kumar <[email-masked]>
Date: Wed, 3 Jul 2024 16:04:00 +0530

> record considering the transaction is small and the wait time is

What I am saying is that if we are not applying the whole transaction,
it means we are not receiving it either unless we plan to spill it to
a file. If we don't spill it to a file, the network buffer will fill
up very quickly. This issue wouldn't occur if we waited right before
the commit because, by that time, we would have already received all
the data from the network.

---

From: shveta malik <[email-masked]>
Date: Wed, 3 Jul 2024 16:09:21 +0530

On Wed, Jul 3, 2024 at 3:35 PM Amit Kapila <[email-masked]> wrote:
> ERROR even if the user has configured wait.

+1. But I think cap has to be on wait-time. As an example, let's say
the user has configured 'clock skew tolerance' of 10sec while the
actual clock skew between nodes is 5 min. It means, we will mostly
have to  wait '5 min - 10sec' to bring the clock skew to a tolerable
limit, which is a huge waiting time. We can keep a max limit on this
wait time.

thanks
Shveta

---

From: Dilip Kumar <[email-masked]>
Date: Wed, 3 Jul 2024 16:12:12 +0530

> tuple is the final change.

Got it, but which case is correct, I think both.  Because in case-1
local commit's commit_ts is 10:18 and the remote commit's commit_ts is
10:20 so remote apply wins.  And case 2, the remote commit's commit_ts
is 10:20 whereas the local commit's commit_ts must be 10:20 + delta
(because it waited for the remote transaction to get committed).

Now say which is better, in case-1 we have to make the remote apply to
wait at the beginning state without knowing what would be the local
clock when it actually comes to commit, it may so happen that if we
choose case-2 by the time the remote transaction finish applying the
local clock is beyond 10:20 and we do not even need to wait?

---

From: Amit Kapila <[email-masked]>
Date: Wed, 3 Jul 2024 16:47:52 +0530

> the data from the network.

We would have received the transaction data but there could be other
transactions that need to wait because the apply worker is waiting
before the commit. So, the situation will be the same. We can even
decide to spill the data to files if the decision is that we need to
wait to avoid network buffer-fill situations. But note that the wait
in apply worker has consequences that the subscriber won't be able to
confirm the flush position and publisher won't be able to vacuum the
dead rows and we won't be remove WAL as well. Last time when we
discussed the delay_apply feature, we decided not to proceed because
of such issues. This is the reason I proposed a cap on wait time.

-- 
With Regards,
Amit Kapila.

---

From: Dilip Kumar <[email-masked]>
Date: Wed, 3 Jul 2024 17:06:05 +0530

On Wed, Jul 3, 2024 at 4:48 PM Amit Kapila <[email-masked]> wrote:
> before the commit.

Yeah, that's a valid point, can parallel apply worker help here?

 So, the situation will be the same. We can even
> of such issues. This is the reason I proposed a cap on wait time.

Yes, spilling to file or cap on the wait time should help, and as I
said above maybe a parallel apply worker can also help.

So I agree that the problem with network buffers arises in both cases,
whether we wait before committing or before beginning. So keeping that
in mind I don't have any strong objections against waiting at the
beginning if it simplifies the design compared to waiting at the
commit.

However, one point to remember in favor of waiting before applying the
commit is that if we decide to wait before beginning the transaction,
we would end up waiting in many more cases compared to waiting before
committing. Because in cases, when transactions are large and the
clock skew is small, the local clock would have already passed the
remote commit_ts by the time we reach the commit.

---

From: shveta malik <[email-masked]>
Date: Wed, 3 Jul 2024 17:08:21 +0530

> local clock is beyond 10:20 and we do not even need to wait?

yes, agree that wait time could be lesser to some extent in case 2.
But the wait during commit will make user operations on the same row
wait, without user having any clue on concurrent blocking operations.
I am not sure if it will be acceptable.

thanks
Shveta

---

From: Dilip Kumar <[email-masked]>
Date: Wed, 3 Jul 2024 17:22:55 +0530

> I am not sure if it will be acceptable.

I don't think there is any problem with the acceptance of user
experience because even while applying the remote transaction
(irrespective of whether we implement this wait feature) the user
transaction might have to wait if updating the common rows right?

---

From: shveta malik <[email-masked]>
Date: Thu, 4 Jul 2024 09:31:01 +0530

> worst-case aid for users.

Please find the new patch set.  patch004 is the new patch which
attempts to implement:

1) Either wait or error out on clock skew as configured. Please note
that currently wait is implemented during 'begin'. Once the ongoing
discussion is concluded, it can be changed as needed.
2) last_update_wins resolver. Thanks Nisha for providing the resolver
related changes.

Next to be done:
1) parallel apply worker related changes as mentioned in [1]
2) cap on wait time due to clock skew
3) resolvers for delete_differ as conflict detection thread [2] has
implemented detection for that.

[1]: https://www.postgresql.org/message-id/CAFiTN-sf23K%3DsRsnxw-BKNJqg5P6JXcqXBBkx%3DEULX8QGSQYaw%40mail.gmail.com
[2]: https://www.postgresql.org/message-id/OS0PR01MB571686E464A325F26CEFCCEF94DD2%40OS0PR01MB5716.jpnprd01.prod.outlook.com

thanks
Shveta

---

From: Amit Kapila <[email-masked]>
Date: Thu, 4 Jul 2024 17:37:10 +0530

> said above maybe a parallel apply worker can also help.

It is not clear to me how a parallel apply worker can help in this
case. Can you elaborate on what you have in mind?

-- 
With Regards,
Amit Kapila.

---

From: Dilip Kumar <[email-masked]>
Date: Fri, 5 Jul 2024 11:57:44 +0530

> case. Can you elaborate on what you have in mind?

If we decide to wait at commit time, and before starting to apply if
we already see a remote commit_ts clock is ahead, then if we apply
such transactions using the parallel worker, wouldn't it solve the
issue of the network buffer congestion? Now the apply worker can move
ahead and fetch new transactions from the buffer as our waiting
transaction will not block it.  I understand that if this transaction
is going to wait at commit then any future transaction that we are
going to fetch might also going to wait again because if the previous
transaction committed before is in the future then the subsequent
transaction committed after this must also be in future so eventually
that will also go to some another parallel worker and soon we end up
consuming all the parallel worker if the clock skew is large.  So I
won't say this will resolve the problem and we would still have to
fall back to the spilling to the disk but that's just in the worst
case when the clock skew is really huge.  In most cases which is due
to slight clock drift by the time we apply the medium to large size
transaction, the local clock should be able to catch up the remote
commit_ts and we might not have to wait in most of the cases.

---

From: Nisha Moond <[email-masked]>
Date: Fri, 5 Jul 2024 12:22:29 +0530

Please find the new patch set (v4). It implements the resolvers for
conflict type : 'delete_differ'.
Supported resolutions for ‘delete_differ’ are :
 - ‘last_update_wins': Apply the change with the latest timestamp (default)
 - 'remote_apply': Apply the remote delete.
 - 'keep_local': Skip the remote delete and continue.
 - 'error': The apply worker will error out and restart.

The changes made in the patches are as follows:
 - Updated the conflict detection patch (patch0001) to the latest
version from [1], which implements delete_differ conflict detection.
 - Patch0002 now supports resolver settings for delete_differ.
 - Patch0003 implements resolutions for delete_differ as well.
 - Patch0004 includes changes to support last_update_wins resolution
for delete_differ.

[1] https://www.postgresql.org/message-id/OS0PR01MB571686E464A325F26CEFCCEF94DD2%40OS0PR01MB5716.jpnprd01.prod.outlook.com

--
Thanks,
Nisha

---

From: Amit Kapila <[email-masked]>
Date: Fri, 5 Jul 2024 14:23:13 +0530

> commit_ts and we might not have to wait in most of the cases.

Yeah, this is possible but even if go with the spilling logic at first
it should work for all cases. If we get some complaints then we can
explore executing such transactions by parallel apply workers.
Personally, I am of the opinion that clock synchronization should be
handled outside the database system via network time protocols like
NTP. Still, we can have some simple solution to inform users about the
clock_skew.

-- 
With Regards,
Amit Kapila.

---

From: Dilip Kumar <[email-masked]>
Date: Fri, 5 Jul 2024 17:11:40 +0530

> NTP. Still, we can have some simple solution to inform users about the

Yeah, that makes sense, in the first version we can have a simple
solution and we can further improvise it based on the feedback.