Skip to content

vinyl: do not reset cache link LSN on partial key lookup#11297

Merged
locker merged 1 commit intotarantool:masterfrom
locker:vy-cache-read-view-fix
Mar 26, 2025
Merged

vinyl: do not reset cache link LSN on partial key lookup#11297
locker merged 1 commit intotarantool:masterfrom
locker:vy-cache-read-view-fix

Conversation

@locker
Copy link
Member

@locker locker commented Mar 25, 2025

Since commit e8109b2 ("vinyl: ignore cache chains with invisible DELETEs") each cache node stores the LSNs of the left and right links. They are used to ignore links that are invisible from the current read view (created after the read view was opened). We update the LSN not only when we link two nodes together but also when we update the node's boundary level. This is incorrect if the node is linked.

For example, suppose we have an index over two fields that contains tuples {0,2} and {2,0} and there's a transaction that was sent to a read view. Now another transaction inserts {0,1} and deletes {0,2}, then selects all tuples. This results in creation of two interlinked cache nodes: {0,1} and {2,0}. The link is invisible from the read view: since we skipped DELETE{0,2}, its LSN equals the LSN of the DELETE statement, which is greater than the read view LSN. However, if we now select GT{1}, we will update the boundary level of the node storing {2,0} from 2 to 1 and reset its LSN to 0 because we didn't skip any DELETE statements. As a result, if the transaction operating in the read view tries to select GT{0,1}, it will find {2,0}, see that it's left-linked and the link LSN is 0, and return it right away, skipping {0,2}, which is visible from the read view.

To fix this issue, let's skip the boundary level update if the node is linked. It doesn't make sense anyway because the boundary level is used only for unlinked nodes, see vy_cache_iterator_is_stop().

Follow-up #11079
Closes #11294

Since commit e8109b2 ("vinyl: ignore cache chains with invisible
DELETEs") each cache node stores the LSNs of the left and right links.
They are used to ignore links that are invisible from the current read
view (created after the read view was opened). We update the LSN not
only when we link two nodes together but also when we update the node's
boundary level. This is incorrect if the node is linked.

For example, suppose we have an index over two fields that contains
tuples {0,2} and {2,0} and there's a transaction that was sent to
a read view. Now another transaction inserts {0,1} and deletes {0,2},
then selects all tuples. This results in creation of two interlinked
cache nodes: {0,1} and {2,0}. The link is invisible from the read view:
since we skipped DELETE{0,2}, its LSN equals the LSN of the DELETE
statement, which is greater than the read view LSN. However, if we now
select GT{1}, we will update the boundary level of the node storing
{2,0} from 2 to 1 and reset its LSN to 0 because we didn't skip any
DELETE statements. As a result, if the transaction operating in the read
view tries to select GT{0,1}, it will find {2,0}, see that it's
left-linked and the link LSN is 0, and return it right away, skipping
{0,2}, which is visible from the read view.

To fix this issue, let's skip the boundary level update if the node
is linked. It doesn't make sense anyway because the boundary level is
used only for unlinked nodes, see vy_cache_iterator_is_stop().

Follow-up tarantool#11079
Closes tarantool#11294

NO_DOC=bug fix
@locker locker requested a review from a team as a code owner March 25, 2025 13:53
@locker locker requested a review from nshy March 25, 2025 14:07
@coveralls
Copy link

Coverage Status

coverage: 90.324% (+2.9%) from 87.466%
when pulling 58450ad on locker:vy-cache-read-view-fix
into 76c8264
on tarantool:master
.

Copy link
Contributor

@nshy nshy left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM.

@nshy nshy assigned locker and unassigned nshy Mar 26, 2025
@locker locker added the full-ci Enables all tests for a pull request label Mar 26, 2025
@locker locker merged commit ae519ed into tarantool:master Mar 26, 2025
58 of 60 checks passed
@locker locker deleted the vy-cache-read-view-fix branch March 26, 2025 13:30
@locker
Copy link
Member Author

locker commented Mar 26, 2025

Cherry-picked to 2.11, 3.2, 3.3.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

full-ci Enables all tests for a pull request

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Vinyl MVCC repeatable read anomaly with secondary index and several different scans

4 participants