[PATCH] vinyl: fix read iterator skips source after reading cache
Vladimir Davydov
vdavydov.dev at gmail.com
Fri Jun 22 19:53:07 MSK 2018
If a source is used on a read iteration (i.e. the key at which it is
positioned is the next best match or, in terms of the read iterator
implementation, its front_id matches the read iterator front_id), its
history is cleaned up, see vy_read_iterator_apply_history(). This breaks
the logic behind vy_read_src_is_behind(), which assumes that the history
always points to the last used key. As a result, a source may be
mistakenly skipped, as illustrated below:
Fiber 1 Fiber 2
------- -------
1. Opens read iterator.
2. Advances it to the next key.
The returned key was read from
a mem or run (not from cache).
The source's history is emptied.
Adds a chain containing
the key read by fiber 1
to the cache.
3. Continues iteration, reads
next few keys from the cache
until the chain ends. The source
used at step 2 is skipped.
4. Calls vy_read_src_is_behind()
on the source used at step 2 and
skipped at step 3. It returns
false, because its history is
empty, thus skipping keys stored
in it.
Fix this bug by moving the code that checks whether a source iterator
needs to be advanced from vy_read_src_is_behind() to source iterator
'skip' method, because there we always know the last key returned by
the iterator.
Basically, this returns the code we had before commit b4d57284d270
("vinyl: consolidate skip optimization checks in read iterator").
Closes #3477
---
https://github.com/tarantool/tarantool/issues/3477
https://github.com/tarantool/tarantool/commits/gh-3477-vy-read-iterator-fix-skip-source
src/box/vy_cache.c | 15 ++++++++++++--
src/box/vy_mem.c | 11 +++++++++++
src/box/vy_read_iterator.c | 24 +++-------------------
src/box/vy_run.c | 14 ++++++++++++-
src/box/vy_tx.c | 11 +++++++++++
test/vinyl/iterator.result | 47 ++++++++++++++++++++++++++++++++++++++++++++
test/vinyl/iterator.test.lua | 22 +++++++++++++++++++++
7 files changed, 120 insertions(+), 24 deletions(-)
diff --git a/src/box/vy_cache.c b/src/box/vy_cache.c
index 2b9e40fa..4f6d0c7f 100644
--- a/src/box/vy_cache.c
+++ b/src/box/vy_cache.c
@@ -700,11 +700,22 @@ vy_cache_iterator_skip(struct vy_cache_iterator *itr,
const struct tuple *last_stmt,
struct vy_history *history, bool *stop)
{
+ assert(!itr->search_started || itr->version == itr->cache->version);
+
+ /*
+ * Check if the iterator is already positioned
+ * at the statement following last_stmt.
+ */
+ if (itr->search_started &&
+ (itr->curr_stmt == NULL || last_stmt == NULL ||
+ iterator_direction(itr->iterator_type) *
+ vy_tuple_compare(itr->curr_stmt, last_stmt,
+ itr->cache->cmp_def) > 0))
+ return 0;
+
*stop = false;
vy_history_cleanup(history);
- assert(!itr->search_started || itr->version == itr->cache->version);
-
itr->search_started = true;
itr->version = itr->cache->version;
if (itr->curr_stmt != NULL)
diff --git a/src/box/vy_mem.c b/src/box/vy_mem.c
index 29ef7710..7c9690ef 100644
--- a/src/box/vy_mem.c
+++ b/src/box/vy_mem.c
@@ -546,6 +546,17 @@ vy_mem_iterator_skip(struct vy_mem_iterator *itr,
{
assert(!itr->search_started || itr->version == itr->mem->version);
+ /*
+ * Check if the iterator is already positioned
+ * at the statement following last_stmt.
+ */
+ if (itr->search_started &&
+ (itr->curr_stmt == NULL || last_stmt == NULL ||
+ iterator_direction(itr->iterator_type) *
+ vy_tuple_compare(itr->curr_stmt, last_stmt,
+ itr->mem->cmp_def) > 0))
+ return 0;
+
vy_history_cleanup(history);
const struct tuple *key = itr->key;
diff --git a/src/box/vy_read_iterator.c b/src/box/vy_read_iterator.c
index d8d66229..160bb899 100644
--- a/src/box/vy_read_iterator.c
+++ b/src/box/vy_read_iterator.c
@@ -244,24 +244,6 @@ vy_read_iterator_evaluate_src(struct vy_read_iterator *itr,
}
}
-/**
- * Check if a read iterator source is behind the current read
- * iterator position and hence needs to be fast-forwarded.
- */
-static inline bool
-vy_read_src_is_behind(struct vy_read_iterator *itr, struct vy_read_src *src)
-{
- uint32_t src_id = src - itr->src;
- if (!src->is_started)
- return true;
- if (src_id < itr->skipped_src)
- return false;
- struct tuple *stmt = vy_history_last_stmt(&src->history);
- if (vy_read_iterator_cmp_stmt(itr, stmt, itr->last_stmt) > 0)
- return false;
- return true;
-}
-
/*
* Each of the functions from the vy_read_iterator_scan_* family
* is used by vy_read_iterator_advance() to:
@@ -327,7 +309,7 @@ vy_read_iterator_scan_cache(struct vy_read_iterator *itr,
int rc = vy_cache_iterator_restore(src_itr, itr->last_stmt,
&src->history, &is_interval);
if (rc == 0) {
- if (vy_read_src_is_behind(itr, src)) {
+ if (!src->is_started || itr->cache_src >= itr->skipped_src) {
rc = vy_cache_iterator_skip(src_itr, itr->last_stmt,
&src->history, &is_interval);
} else if (src->front_id == itr->prev_front_id) {
@@ -359,7 +341,7 @@ vy_read_iterator_scan_mem(struct vy_read_iterator *itr, uint32_t mem_src,
rc = vy_mem_iterator_restore(src_itr, itr->last_stmt, &src->history);
if (rc == 0) {
- if (vy_read_src_is_behind(itr, src)) {
+ if (!src->is_started || mem_src >= itr->skipped_src) {
rc = vy_mem_iterator_skip(src_itr, itr->last_stmt,
&src->history);
} else if (src->front_id == itr->prev_front_id) {
@@ -384,7 +366,7 @@ vy_read_iterator_scan_disk(struct vy_read_iterator *itr, uint32_t disk_src,
assert(disk_src >= itr->disk_src && disk_src < itr->src_count);
- if (vy_read_src_is_behind(itr, src))
+ if (!src->is_started || disk_src >= itr->skipped_src)
rc = vy_run_iterator_skip(src_itr, itr->last_stmt,
&src->history);
else if (src->front_id == itr->prev_front_id)
diff --git a/src/box/vy_run.c b/src/box/vy_run.c
index e2edbcaa..a15777b5 100644
--- a/src/box/vy_run.c
+++ b/src/box/vy_run.c
@@ -1523,10 +1523,22 @@ vy_run_iterator_skip(struct vy_run_iterator *itr,
const struct tuple *last_stmt,
struct vy_history *history)
{
- vy_history_cleanup(history);
if (itr->search_ended)
return 0;
+ /*
+ * Check if the iterator is already positioned
+ * at the statement following last_stmt.
+ */
+ if (itr->search_started &&
+ (itr->curr_stmt == NULL || last_stmt == NULL ||
+ iterator_direction(itr->iterator_type) *
+ vy_tuple_compare(itr->curr_stmt, last_stmt,
+ itr->cmp_def) > 0))
+ return 0;
+
+ vy_history_cleanup(history);
+
const struct tuple *key = itr->key;
enum iterator_type iterator_type = itr->iterator_type;
if (last_stmt != NULL) {
diff --git a/src/box/vy_tx.c b/src/box/vy_tx.c
index 04792ce7..f5bb624f 100644
--- a/src/box/vy_tx.c
+++ b/src/box/vy_tx.c
@@ -983,6 +983,17 @@ vy_txw_iterator_skip(struct vy_txw_iterator *itr,
assert(!itr->search_started ||
itr->version == itr->tx->write_set_version);
+ /*
+ * Check if the iterator is already positioned
+ * at the statement following last_stmt.
+ */
+ if (itr->search_started &&
+ (itr->curr_txv == NULL || last_stmt == NULL ||
+ iterator_direction(itr->iterator_type) *
+ vy_tuple_compare(itr->curr_txv->stmt, last_stmt,
+ itr->lsm->cmp_def) > 0))
+ return 0;
+
vy_history_cleanup(history);
const struct tuple *key = itr->key;
diff --git a/test/vinyl/iterator.result b/test/vinyl/iterator.result
index 4798f5f2..be0744d1 100644
--- a/test/vinyl/iterator.result
+++ b/test/vinyl/iterator.result
@@ -2182,3 +2182,50 @@ box.commit()
s:drop()
---
...
+--
+-- gh-3477: read iterator skips a source after reading cache.
+--
+s = box.schema.space.create('test', {engine = 'vinyl'})
+---
+...
+_ = s:create_index('pk')
+---
+...
+for i = 1, 5 do s:insert{i} end
+---
+...
+-- Start iteration.
+t = {}
+---
+...
+gen, param, state = s:pairs({})
+---
+...
+_, v = gen(param, state)
+---
+...
+table.insert(t, v)
+---
+...
+-- Add chain {1}..{3} to the cache
+box.space.test:select({}, {limit = 3})
+---
+- - [1]
+ - [2]
+ - [3]
+...
+-- Continue iteration.
+for k, v in gen, param, state do table.insert(t, v) end
+---
+...
+t
+---
+- - [1]
+ - [2]
+ - [3]
+ - [4]
+ - [5]
+...
+s:drop()
+---
+...
diff --git a/test/vinyl/iterator.test.lua b/test/vinyl/iterator.test.lua
index b15f4ef1..9fa6609a 100644
--- a/test/vinyl/iterator.test.lua
+++ b/test/vinyl/iterator.test.lua
@@ -759,3 +759,25 @@ value
box.commit()
s:drop()
+
+--
+-- gh-3477: read iterator skips a source after reading cache.
+--
+s = box.schema.space.create('test', {engine = 'vinyl'})
+_ = s:create_index('pk')
+for i = 1, 5 do s:insert{i} end
+
+-- Start iteration.
+t = {}
+gen, param, state = s:pairs({})
+_, v = gen(param, state)
+table.insert(t, v)
+
+-- Add chain {1}..{3} to the cache
+box.space.test:select({}, {limit = 3})
+
+-- Continue iteration.
+for k, v in gen, param, state do table.insert(t, v) end
+t
+
+s:drop()
--
2.11.0
More information about the Tarantool-patches
mailing list