[RFC PATCH 04/23] vinyl: make point lookup always return the latest tuple version

[Vladimir Davydov]

On Tue, Jul 10, 2018 at 07:19:26PM +0300, Konstantin Osipov wrote:
> * Vladimir Davydov <vdavydov.dev at gmail.com> [18/07/08 22:52]:
> > Currently, vy_point_lookup(), in contrast to vy_read_iterator, doesn't
> > rescan the memory level after reading disk, so if the caller doesn't
> > track the key before calling this function, the caller won't be sent to
> > a read view in case the key gets updated during yield and hence will
> > be returned a stale tuple. This is OK now, because we always track the
> > key before calling vy_point_lookup(), either in the primary or in a
> > secondary index. However, for #2129 we need it to always return the
> > latest tuple version, no matter if the key is tracked or not.
> > 
> > The point is in the scope of #2129 we won't write DELETE statements to
> > secondary indexes corresponding to a tuple replaced in the primary
> > index. Instead after reading a tuple from a secondary index we will
> > check whether it matches the tuple corresponding to it in the primary
> > index: if it is not, it means that the tuple read from the secondary
> > index was overwritten and should be skipped. E.g. suppose we have the
> > primary index over the first field and a secondary index over the second
> > field and the following statements in the space:
> > 
> >   REPLACE{1, 10}
> >   REPLACE{1, 20}
> > 
> > Then reading {10} from the secondary index will return REPLACE{1, 10}, but
> > lookup of {1} in the primary index will return REPLACE{1, 20} which
> > doesn't match REPLACE{1, 10} read from the secondary index hence the
> > latter was overwritten and should be skipped.
> > 
> > The problem is in the example above we don't want to track key {1} in
> > the primary index before lookup, because we don't actually read its
> > value. So for the check to work correctly, we need the point lookup to
> > guarantee that the returned tuple is always the newest one. It's fairly
> > easy to do - we just need to rescan the memory level after yielding on
> > disk if its version changed.
> 
> Thank you for the explanation. I haven't read the patch itself
> yet. But aren't you complicating things more than necessary? All
> we need to do when looking up a match in the primary index is to
> compare the match LSN and the secondary index tuple LSN. If there
> is a mismatch, then we need to skip the secondary key tuple: it's
> garbage. The mismatch does not need to take into account new
> tuples which appeared during yield, since a mismatch can not
> appear during yield.

Using LSNs solely for detecting mismatch is complicated, because of
prepared and txn statements, but even if we put those aside, there's
an optimization in write iterator, which excludes a statement from
the output in case it doesn't modify key parts - see

  https://github.com/tarantool/tarantool/blob/f64f46199e19542fa60eede939d62cd115abb83a/src/box/vy_write_iterator.c#L674

This optimization makes detection by LSN impossible.

Anyway, this particular patch is needed no matter if we detect mismatch
by LSN or by value. Example:

  Let primary index be over part 1 and secondary index be over part 2.
  Let the following statement be committed to both indexes and written
  to disk:

  REPLACE{1, 10, lsn = 123}

  Now let us consider the following race condition:

  Fiber 1                               Fiber 2
  -------                               -------
  look up {10} in the secondary index
  get REPLACE{1, 10, lsn = 123}
  look up {1} in the primary index to check for mismatch
  yields on disk read

                                        commits REPLACE{1, 20, lsn = 456}

  ( skips the new statement, because point
    lookup doesn't rescan the memory level )
  gets REPLACE{1, 10, lsn = 123}

  LSNs are equal, values are equal too,
  hence no mismatch, return to the user

This behavior would be incorrect, because the transaction wouldn't
be sent to read view in this case since secondary key {10} is not
modified.

We could track primary key {1} before the lookup to make sure the
transaction is sent to read view in such a case, but that wouldn't be
quire right: if there was no {1} in the primary index, we would track
a value we didn't actually read.

Hope this explains the problem I'm coping with here.