Re: Conflict Detection and Resolution

From: shveta malik <shveta(dot)malik(at)gmail(dot)com>
To: Tomas Vondra <tomas(dot)vondra(at)enterprisedb(dot)com>
Cc: pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>, "Zhijie Hou (Fujitsu)" <houzj(dot)fnst(at)fujitsu(dot)com>, Nisha Moond <nisha(dot)moond412(at)gmail(dot)com>, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>, shveta malik <shveta(dot)malik(at)gmail(dot)com>
Subject: Re: Conflict Detection and Resolution
Date: 2024-06-11 08:35:32
Message-ID: CAJpy0uAdrsy0SHddrZ25gU3jGvZV+D+M-UaJCO2sNhdjvex8gg@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Mon, Jun 10, 2024 at 5:24 PM Tomas Vondra
<tomas(dot)vondra(at)enterprisedb(dot)com> wrote:
>
>
>
> On 6/10/24 12:56, shveta malik wrote:
> > On Fri, Jun 7, 2024 at 6:08 PM Tomas Vondra
> > <tomas(dot)vondra(at)enterprisedb(dot)com> wrote:
> >>
> >>>>>
> >>>>> UPDATE
> >>>>> ================
> >>>>>
> >>>>> Conflict Detection Method:
> >>>>> --------------------------------
> >>>>> Origin conflict detection: The ‘origin’ info is used to detect
> >>>>> conflict which can be obtained from commit-timestamp generated for
> >>>>> incoming txn at the source node. To compare remote’s origin with the
> >>>>> local’s origin, we must have origin information for local txns as well
> >>>>> which can be obtained from commit-timestamp after enabling
> >>>>> ‘track_commit_timestamp’ locally.
> >>>>> The one drawback here is the ‘origin’ information cannot be obtained
> >>>>> once the row is frozen and the commit-timestamp info is removed by
> >>>>> vacuum. For a frozen row, conflicts cannot be raised, and thus the
> >>>>> incoming changes will be applied in all the cases.
> >>>>>
> >>>>> Conflict Types:
> >>>>> ----------------
> >>>>> a) update_differ: The origin of an incoming update's key row differs
> >>>>> from the local row i.e.; the row has already been updated locally or
> >>>>> by different nodes.
> >>>>> b) update_missing: The row with the same value as that incoming
> >>>>> update's key does not exist. Remote is trying to update a row which
> >>>>> does not exist locally.
> >>>>> c) update_deleted: The row with the same value as that incoming
> >>>>> update's key does not exist. The row is already deleted. This conflict
> >>>>> type is generated only if the deleted row is still detectable i.e., it
> >>>>> is not removed by VACUUM yet. If the row is removed by VACUUM already,
> >>>>> it cannot detect this conflict. It will detect it as update_missing
> >>>>> and will follow the default or configured resolver of update_missing
> >>>>> itself.
> >>>>>
> >>>>
> >>>> I don't understand the why should update_missing or update_deleted be
> >>>> different, especially considering it's not detected reliably. And also
> >>>> that even if we happen to find the row the associated TOAST data may
> >>>> have already been removed. So why would this matter?
> >>>
> >>> Here, we are trying to tackle the case where the row is 'recently'
> >>> deleted i.e. concurrent UPDATE and DELETE on pub and sub. User may
> >>> want to opt for a different resolution in such a case as against the
> >>> one where the corresponding row was not even present in the first
> >>> place. The case where the row was deleted long back may not fall into
> >>> this category as there are higher chances that they have been removed
> >>> by vacuum and can be considered equivalent to the update_ missing
> >>> case.
> >>>
> >>
> >> My point is that if we can't detect the difference reliably, it's not
> >> very useful. Consider this example:
> >>
> >> Node A:
> >>
> >> T1: INSERT INTO t (id, value) VALUES (1,1);
> >>
> >> T2: DELETE FROM t WHERE id = 1;
> >>
> >> Node B:
> >>
> >> T3: UPDATE t SET value = 2 WHERE id = 1;
> >>
> >> The "correct" order of received messages on a third node is T1-T3-T2.
> >> But we may also see T1-T2-T3 and T3-T1-T2, e.g. due to network issues
> >> and so on. For T1-T2-T3 the right decision is to discard the update,
> >> while for T3-T1-T2 it's to either wait for the INSERT or wait for the
> >> insert to arrive.
> >>
> >> But if we misdetect the situation, we either end up with a row that
> >> shouldn't be there, or losing an update.
> >
> > Doesn't the above example indicate that 'update_deleted' should also
> > be considered a necessary conflict type? Please see the possibilities
> > of conflicts in all three cases:
> >
> >
> > The "correct" order of receiving messages on node C (as suggested
> > above) is T1-T3-T2 (case1)
> > ----------
> > T1 will insert the row.
> > T3 will have update_differ conflict; latest_timestamp wins or apply
> > will apply it. earliest_timestamp_wins or skip will skip it.
> > T2 will delete the row (irrespective of whether the update happened or not).
> > End Result: No Data.
> >
> > T1-T2-T3
> > ----------
> > T1 will insert the row.
> > T2 will delete the row.
> > T3 will have conflict update_deleted. If it is 'update_deleted', the
> > chances are that the resolver set here is to 'skip' (default is also
> > 'skip' in this case).
> >
> > If vacuum has deleted that row (or if we don't support
> > 'update_deleted' conflict), it will be 'update_missing' conflict. In
> > that case, the user may end up inserting the row if resolver chosen is
> > in favor of apply (which seems an obvious choice for 'update_missing'
> > conflict; default is also 'apply_or_skip').
> >
> > End result:
> > Row inserted with 'update_missing'.
> > Row correctly skipped with 'update_deleted' (assuming the obvious
> > choice seems to be 'skip' for update_deleted case).
> >
> > So it seems that with 'update_deleted' conflict, there are higher
> > chances of opting for right decision here (which is to discard the
> > update), as 'update_deleted' conveys correct info to the user. The
> > 'update_missing' OTOH does not convey correct info and user may end up
> > inserting the data by choosing apply favoring resolvers for
> > 'update_missing'. Again, we get benefit of 'update_deleted' for
> > *recently* deleted rows only.
> >
> > T3-T1-T2
> > ----------
> > T3 may end up inserting the record if the resolver is in favor of
> > 'apply' and all the columns are received from remote.
> > T1 will have' insert_exists' conflict and thus may either overwrite
> > 'updated' values or may leave the data as is (based on whether
> > resolver is in favor of apply or not)
> > T2 will end up deleting it.
> > End Result: No Data.
> >
> > I feel for second case (and similar cases), 'update_deleted' serves a
> > better conflict type.
> >
>
> True, but this is pretty much just a restatement of the example, right?
>
> The point I was trying to make is that this hinges on the ability to
> detect the correct conflict type. And if vacuum can swoop in and remove
> the recently deleted tuples (which I believe can happen at any time,
> right?), then that's not guaranteed, because we won't see the deleted
> tuple anymore.

Yes, that's correct. However, many cases could benefit from the
update_deleted conflict type if it can be implemented reliably. That's
why we wanted to give it a try. But if we can't achieve predictable
results with it, I'm fine to drop this approach and conflict_type. We
can consider a better design in the future that doesn't depend on
non-vacuumed entries and provides a more robust method for identifying
deleted rows.

> Also, can the resolver even convert the UPDATE into INSERT and proceed?
> Maybe with REPLICA IDENTITY FULL?

Yes, it can, as long as the row doesn't contain toasted data. Without
toasted data, the new tuple is fully logged. However, if the row does
contain toasted data, the new tuple won't log it completely. In such a
case, REPLICA IDENTITY FULL becomes a requirement to ensure we have
all the data necessary to create the row on the target side. In
absence of RI full and with row lacking toasted data, the operation
will be skipped or error will be raised.

> Otherwise the row might be incomplete,
> missing required columns etc. In which case it'd have to wait for the
> actual INSERT to arrive - which would work for actual update_missing,
> where the row may be delayed due to network issues. But if that's a
> mistake due to vacuum removing the deleted tuple, it'll wait forever.

Even in case of 'update_missing', we do not intend to wait for 'actual
insert' to arrive, as it is not guaranteed if the 'insert' will arrive
or not. And thus we plan to skip or error out (based on user's
configuration) if a complete row can not be created for insertion.

thanks
Shveta

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Amit Kapila 2024-06-11 08:39:15 Re: confirmed flush lsn seems to be move backward in certain error cases
Previous Message Bertrand Drouvot 2024-06-11 08:26:23 Re: Track the amount of time waiting due to cost_delay