Resume bucket garbage collection after the preceding batch

[andrejbranch]

Resume bucket garbage collection after the preceding batch

Problem

VShard garbage-collects a transferred bucket in bounded transactions. When one transaction reaches BUCKET_CHUNK_SIZE, gc_bucket_in_space_xc() commits it and jumps back to restart, where it opens a new iterator at {bucket_id}. The next transaction therefore starts scanning the bucket secondary index from the bucket prefix again instead of continuing after the last tuple deleted by the preceding transaction.

This is particularly expensive for large Vinyl buckets. Deleted index entries remain as LSM history and tombstones until compaction, and a Vinyl secondary-index iterator performs primary-index lookups to materialize and validate tuples. Each new batch can revisit an increasingly large deleted prefix before reaching the next live tuple. The resulting prefix work grows with both bucket cardinality and the number of batches, making smaller garbage-collection transactions disproportionately expensive.

The sender does not have the same behavior: it keeps one iterator while emitting multiple transfer chunks. The repeated-prefix scan is specific to bucket garbage collection across transaction boundaries.

Existing behavior

The current loop is equivalent to:

::restart::
box.begin()
for _, tuple in bucket_index:pairs({bucket_id}) do
    space:delete(extract_primary_key(tuple))
    if the_batch_is_full then
        box.commit()
        goto restart
    end
end
box.commit()

For a bucket containing N tuples and a batch size B, this creates approximately N / B iterators at the same prefix. On an LSM index, the repeatedly encountered deleted prefix can make the amount of scan work grow approximately like N² / (2B), depending on the engine state and compaction history.

Proposal

When supported by Tarantool and the bucket index is a TREE index, retain the last tuple returned by the bucket iterator and pass it through the after iterator option when opening the next transaction:

local after = nil
::restart::
box.begin()
for _, tuple in bucket_index:pairs({bucket_id}, {after = after}) do
    space:delete(extract_primary_key(tuple))
    if the_batch_is_full then
        after = tuple
        box.commit()
        goto restart
    end
end
box.commit()

The tuple used as the position was deleted by the preceding transaction, but Tarantool pagination explicitly supports an after tuple that is no longer present in the index. Bucket state continues to be checked after each commit as it is today.

Tarantool added index pagination in 2.11, while VShard supports Tarantool 1.10. The optimization must therefore be feature-gated. Tarantool 2.11 and later can use the resumable cursor for TREE indexes; older versions and unsupported index types must retain the current prefix-restarting behavior.

Correctness considerations

A bucket being garbage-collected is no longer writable through VShard. Cursor resumption relies on the same lifecycle invariant as bucket sending: tuples are not inserted into the bucket behind an iterator that has already passed their position. Direct writes that bypass VShard bucket-state checks are outside this invariant.

The implementation should preserve the current behavior when a transaction fails, when the bucket generation or state changes after a commit, and when pagination is unavailable. The cursor is local to one bucket and one space and is discarded when the function returns or raises.

Benchmark

A representative local benchmark used a 50,000-tuple Vinyl bucket with three indexes, synchronous replication, and a garbage-collection batch size of 100. Values are medians across three fresh-cluster runs.

Iteration behavior	Cleanup wall time	Cleanup CPU time
Restart from bucket prefix	4.906 s	4.757 s
Resume after last tuple	0.602 s	0.414 s

The cursor reduced cleanup wall time by approximately 88% and cleanup CPU by approximately 91% without changing the number of tuple deletes, WAL rows, transactions, index updates, or synchronous commits.

Latency percentiles measured only for the duration of each cleanup are intentionally omitted from the table. Cursor cleanup finished in approximately 0.6 seconds and collected about 225 probe observations, while prefix-restarting cleanup ran for approximately 4.9 seconds and collected about 1,815 observations. Comparing percentiles from those unequal exposure periods is misleading: the cursor p99 is approximately the third-highest observation, whereas the prefix-restart p99 is approximately the nineteenth-highest observation.

A separate comparison kept direct source probes running for the same eight-second wall-clock window after starting cleanup. Both cases deleted the same 50,000-tuple bucket, and each case collected approximately 3,300 probe observations. Values are medians across three fresh-cluster runs.

Iteration behavior	Cleanup duration	Probe average	Probe p50	Probe p95	Probe p99
Restart from bucket prefix	4.906 s	0.118 ms	0.089 ms	0.234 ms	0.632 ms
Resume after last tuple	0.501 s	0.085 ms	0.057 ms	0.217 ms	0.582 ms

Over the equal wall-clock window, cursor resumption did not regress the direct probe p99 and improved the average, p50, p95, and p99. The p99 difference was modest, so these results should be interpreted as evidence against a material regression rather than as a precise latency improvement. These direct probes measure TX-thread responsiveness and are not a substitute for end-to-end client latency measurements.

In a separate batch-size matrix, cursor-based cleanup took 0.543, 0.511, 0.495, and 0.483 seconds for batch sizes 100, 250, 500, and 1000 respectively. Without the cursor, the same cases took 4.999, 2.301, 1.407, and 0.970 seconds. Resuming the iterator made cleanup throughput nearly independent of the transaction batch size while retaining smaller transactions as the control for the TX scheduling quantum.

Testing

• Verify that Tarantool 2.11 and later pass the last deleted tuple through after on subsequent garbage-collection batches.
• Verify that the first batch starts at the bucket prefix.
• Verify that the fallback path never passes after when pagination is unavailable.
• Verify complete deletion with MemTX and Vinyl, with and without MVCC.
• Verify that a deleted cursor tuple is accepted as the next iterator position.
• Run the complete garbage-collector suite on supported Tarantool versions, including the Tarantool 1.10 compatibility job.

Related work

• Make garbage collection gradually #132 introduced bounded garbage-collection transactions. Preserving iterator position completes that design by avoiding repeated work between those transactions.
• Do yields when iterating over _bucket, or a bucket content #85 addresses yielding during iteration but does not preserve scan progress across garbage-collection transactions.

[Serpentian]

Can confirm, that using pagination makes the GC dramatically faster on vinyl:

$>  RUN_COUNT=1 MODES=restart,tuple,position tarantool /tmp/vshard_gc_cursor_perf.lua
Tarantool=3.8.0-entrypoint-163-g15f5b41033 engine=vinyl tuples=50000 batch=100 runs=1 payload=256
mode run wall_seconds cpu_seconds transactions
restart 1 49.230459 48.508282 501
restart median 49.230459 48.508282
tuple 1 5.939550 5.701680 501
tuple median 5.939550 5.701680
position 1 5.704963 5.487291 501
position median 5.704963 5.487291

It also majorly bumps the perf of the GC with MVCC enabled:

RUN_COUNT=1 MODES=restart,tuple,position ENGINE=memtx MVCC=true TUPLE_COUNT=50000 tarantool /tmp/vshard_gc_cursor_perf.lua
Tarantool=3.8.0-entrypoint-163-g15f5b41033 engine=memtx mvcc=true tuples=50000 batch=100 runs=1 payload=256
mode run wall_seconds cpu_seconds transactions
restart 1 5.783472 5.714658 501
restart median 5.783472 5.714658
tuple 1 0.708128 0.671281 501
tuple median 0.708128 0.671281
position 1 0.529716 0.504538 501
position median 0.529716 0.504538

Perf test

-- Microbenchmark for bucket GC iterator restart versus pagination.
--
-- It intentionally implements only the hot loop from
-- gc_bucket_in_space_xc(). This keeps the measurement focused on Vinyl
-- secondary-index prefix scanning rather than VShard setup and recovery.
--
-- Environment variables:
--   TUPLE_COUNT   tuples in the bucket (default: 50000)
--   BATCH_SIZE    deletes per transaction (default: 100)
--   RUN_COUNT     fresh-space runs per mode (default: 3)
--   PAYLOAD_SIZE  bytes in the non-indexed value (default: 256)
--   ENGINE        vinyl or memtx (default: vinyl)
--   MVCC          true to enable the MemTX MVCC engine (default: false)
--   MODES         comma-separated restart,tuple,position
--                 (default: restart,position)
--
-- The "tuple" mode models the patch under review. The "position" mode stores
-- index:tuple_pos(tuple), which avoids the vulnerable tuple-pagination path on
-- older Tarantool 3.x releases.

local clock = require('clock')
local fio = require('fio')

local function getenv_number(name, default)
    local value = os.getenv(name)
    if value == nil then
        return default
    end
    value = tonumber(value)
    assert(value ~= nil and value > 0, name .. ' must be a positive number')
    return value
end

local tuple_count = getenv_number('TUPLE_COUNT', 50000)
local batch_size = getenv_number('BATCH_SIZE', 100)
local run_count = getenv_number('RUN_COUNT', 3)
local payload_size = getenv_number('PAYLOAD_SIZE', 256)
local engine = os.getenv('ENGINE') or 'vinyl'
assert(engine == 'vinyl' or engine == 'memtx',
       'ENGINE must be vinyl or memtx')
local mvcc = os.getenv('MVCC') == 'true'

local modes = {}
for mode in (os.getenv('MODES') or 'restart,position'):gmatch('[^,]+') do
    assert(mode == 'restart' or mode == 'tuple' or mode == 'position',
           'unknown mode: ' .. mode)
    table.insert(modes, mode)
end
assert(#modes > 0, 'MODES must not be empty')

local data_dir = fio.tempdir()
box.cfg({
    log = fio.pathjoin(data_dir, 'tarantool.log'),
    memtx_dir = data_dir,
    vinyl_dir = data_dir,
    wal_dir = data_dir,
    vinyl_memory = 128 * 1024 * 1024,
    memtx_use_mvcc_engine = mvcc,
})

local bucket_id = 1
local payload = string.rep('x', payload_size)

local function create_and_fill(name)
    local space = box.schema.space.create(name, {
        engine = engine,
        format = {
            {name = 'id', type = 'unsigned'},
            {name = 'bucket_id', type = 'unsigned'},
            {name = 'value', type = 'unsigned'},
            {name = 'payload', type = 'string'},
        },
    })
    space:create_index('primary', {
        parts = {{field = 'id', type = 'unsigned'}},
    })
    space:create_index('bucket_id', {
        parts = {{field = 'bucket_id', type = 'unsigned'}},
        unique = false,
    })
    space:create_index('value', {
        parts = {{field = 'value', type = 'unsigned'}},
        unique = false,
    })

    local fill_batch = 1000
    box.begin()
    for i = 1, tuple_count do
        space:insert({i, bucket_id, i, payload})
        if i % fill_batch == 0 and i ~= tuple_count then
            box.commit()
            box.begin()
        end
    end
    box.commit()

    -- Put the inserted secondary-index entries on disk. Deletes performed by
    -- the measured loop then leave history/tombstones in front of live tuples.
    if engine == 'vinyl' then
        box.snapshot()
    end
    return space
end

local function cleanup(space, mode)
    local bucket_index = space.index.bucket_id
    local after = nil
    local transaction_count = 0

::restart::
    local count = 0
    box.begin()
    local opts = after ~= nil and {after = after} or nil
    for _, tuple in bucket_index:pairs({bucket_id}, opts) do
        space:delete({tuple.id})
        count = count + 1
        if count == batch_size then
            if mode == 'tuple' then
                after = tuple
            elseif mode == 'position' then
                after = bucket_index:tuple_pos(tuple)
            else
                after = nil
            end
            box.commit()
            transaction_count = transaction_count + 1
            goto restart
        end
    end
    box.commit()
    transaction_count = transaction_count + 1
    return transaction_count
end

local function median(values)
    table.sort(values)
    local middle = math.floor(#values / 2) + 1
    if #values % 2 == 1 then
        return values[middle]
    end
    return (values[middle - 1] + values[middle]) / 2
end

print(('Tarantool=%s engine=%s mvcc=%s tuples=%d batch=%d runs=%d ' ..
       'payload=%d'):
      format(_TARANTOOL, engine, tostring(mvcc), tuple_count, batch_size,
             run_count, payload_size))
print('mode run wall_seconds cpu_seconds transactions')

for _, mode in ipairs(modes) do
    local walls = {}
    local cpus = {}
    for run = 1, run_count do
        local name = ('bench_%s_%d'):format(mode, run)
        local space = create_and_fill(name)
        collectgarbage('collect')

        local wall_start = clock.monotonic64()
        local cpu_start = clock.proc64()
        local transactions = cleanup(space, mode)
        local cpu = tonumber(clock.proc64() - cpu_start) / 1e9
        local wall = tonumber(clock.monotonic64() - wall_start) / 1e9

        assert(space:count() == 0, mode .. ' left tuples behind')
        walls[run] = wall
        cpus[run] = cpu
        print(('%s %d %.6f %.6f %d'):
              format(mode, run, wall, cpu, transactions))
        space:drop()
    end
    print(('%s median %.6f %.6f'):
          format(mode, median(walls), median(cpus)))
end

os.exit(0)

[Gerold103]

Just one question. Do we really need the {after = ...} thing? Can't we simply start the pairs loop, and then inside the loop begin+commit batches without even restarting the loop at all?

[andrejbranch]

Good question. I did look at that first. The blocker is that the iterator can't be carried across the box.commit():
it's tied to the transaction's read view, and on memtx (especially without MVCC, and on 1.10) deleting from the space while the commit yields invalidates the open iterator. Since bounded per-chunk transactions are a hard requirement (#132), GC has to cross a commit boundary between chunks, which means reopening the iterator — and {after = ...} just lets the reopened one resume at the right place instead of rescanning the deleted prefix.

The sender can keep a single iterator precisely because it only reads a snapshot and streams it; GC additionally deletes and commits mid-scan, which is the difference.

One more reason specific to Vinyl: a single iterator held for the whole bucket keeps one read view open for the entire cleanup, which pins the tombstones/old runs and blocks compaction from reclaiming them, the opposite of what we want here. Reopening per chunk keeps each read view short-lived.

Happy to be corrected if I'm missing a safe way to hold it across commits

[Serpentian]

@Gerold103, if pairs() is created inside the explicit transaction, Vinyl binds it to that transaction. After box.commit(), the next iteration fails with ER_CURSOR_NO_TRANSACTION. The following code produces the error:

box.cfg()
local space = box.schema.space.create('test', {engine = 'vinyl'})
space:create_index('primary')
local bucket_index = space:create_index('bucket_id', {
    parts = {{field = 2, type = 'unsigned'}},
    unique = false,
})

local bucket_id = 1
local tuple_count = 25
local batch_size = 10
for id = 1, tuple_count do
    space:insert({id, bucket_id})
end
box.snapshot()

local count = 0
box.begin()
for _, tuple in bucket_index:pairs({bucket_id}) do
    space:delete({tuple[1]})
    count = count + 1
    if count == batch_size then
        box.commit()
        count = 0
        box.begin()
        -- The next iterator step raises ER_CURSOR_NO_TRANSACTION because
        -- the transaction which owned the iterator has ended.
    end
end
box.commit()

2026-07-17 17:32:07.368 [184067] main vinyl_pairs_transaction_repro.lua:19 E> ER_CURSOR_NO_TRANSACTION: The transaction the cursor belongs to has ended

Though, the following approach works:

  local gen, param, state = bucket_index:pairs({bucket_id})

  box.begin()
  for _, tuple in gen, param, state do
      space:delete(extract_primary_key(tuple))
      if batch_is_full then
          box.commit()
          bucket_guard_xc(...)
          box.begin()
      end
  end
  box.commit()

It's also good performance wise, but LLM says, it's not good for Vinyl, and I don't understand a word it says:

  However, on Vinyl this produces a long-lived read transaction. As soon as the first delete batch conflicts
  with what the iterator has read, Tarantool moves the iterator’s internal transaction into a read view. In my
  small test, after each commit:

  read_views = 1

  and it remained until the iterator reached EOF. That matters because:

  - Compaction must retain versions needed by the old read view; Tarantool’s compaction code explicitly
    preserves history according to the oldest read view (/home/serpentian/Programming/tnt/tarantool/src/box/
    vy_write_iterator.h:86).

  - The read view spans the entire bucket cleanup, not one bounded batch.
  - If the guard or a commit raises midway, the iterator has no explicit Lua close(). Its internal transaction
    and read view may survive until the FFI iterator is garbage-collected.

  - This relies on the subtler “autocommit iterator coexisting with explicit write transactions” behavior.
    Pagination is the API designed to carry position between independent transactions. The official iterator
    documentation also warns that ordinary iterator behavior across yields should not be treated as a stable
    consistent view contract: index_object:pairs()
    (https://www.tarantool.io/en/doc/latest/reference/reference_lua/box_index/pairs/).

Perf

RUN_COUNT=1 MODES=restart,position,pairs tarantool /tmp/vshard_gc_cursor_perf.lua
Tarantool=3.3.0-entrypoint-727-gd324811b07 engine=vinyl mvcc=false tuples=50000 batch=100 runs=1 payload=256
mode run wall_seconds cpu_seconds transactions
restart 1 35.548755 34.199098 501
restart median 35.548755 34.199098
position 1 2.024511 1.988429 501
position median 2.024511 1.988429
pairs 1 2.502235 2.483641 501
pairs median 2.502235 2.483641

-- Microbenchmark for bucket GC iterator restart versus pagination versus a
-- persistent iterator created outside the delete transactions.
--
-- It intentionally implements only the hot loop from
-- gc_bucket_in_space_xc(). This keeps the measurement focused on Vinyl
-- secondary-index prefix scanning rather than VShard setup and recovery.
--
-- Environment variables:
--   TUPLE_COUNT   tuples in the bucket (default: 50000)
--   BATCH_SIZE    deletes per transaction (default: 100)
--   RUN_COUNT     fresh-space runs per mode (default: 3)
--   PAYLOAD_SIZE  bytes in the non-indexed value (default: 256)
--   ENGINE        vinyl or memtx (default: vinyl)
--   MVCC          true to enable the MemTX MVCC engine (default: false)
--   MODES         comma-separated restart,tuple,position,pairs
--                 (default: restart,position,pairs)
--
-- The "tuple" mode passes the last tuple through the pagination API. The
-- "position" mode stores index:tuple_pos(tuple), which avoids the vulnerable
-- tuple-pagination path on older Tarantool 3.x releases. The "pairs" mode
-- creates one index:pairs() iterator before the first box.begin() and keeps it
-- while committing and beginning all delete batches.

local clock = require('clock')
local fio = require('fio')

local function getenv_number(name, default)
    local value = os.getenv(name)
    if value == nil then
        return default
    end
    value = tonumber(value)
    assert(value ~= nil and value > 0, name .. ' must be a positive number')
    return value
end

local tuple_count = getenv_number('TUPLE_COUNT', 50000)
local batch_size = getenv_number('BATCH_SIZE', 100)
local run_count = getenv_number('RUN_COUNT', 3)
local payload_size = getenv_number('PAYLOAD_SIZE', 256)
local engine = os.getenv('ENGINE') or 'vinyl'
assert(engine == 'vinyl' or engine == 'memtx',
       'ENGINE must be vinyl or memtx')
local mvcc = os.getenv('MVCC') == 'true'

local modes = {}
for mode in (os.getenv('MODES') or 'restart,position,pairs'):gmatch('[^,]+') do
    assert(mode == 'restart' or mode == 'tuple' or mode == 'position' or
           mode == 'pairs', 'unknown mode: ' .. mode)
    table.insert(modes, mode)
end
assert(#modes > 0, 'MODES must not be empty')

local data_dir = fio.tempdir()
box.cfg({
    log = fio.pathjoin(data_dir, 'tarantool.log'),
    memtx_dir = data_dir,
    vinyl_dir = data_dir,
    wal_dir = data_dir,
    vinyl_memory = 128 * 1024 * 1024,
    memtx_use_mvcc_engine = mvcc,
})

local bucket_id = 1
local payload = string.rep('x', payload_size)

local function create_and_fill(name)
    local space = box.schema.space.create(name, {
        engine = engine,
        format = {
            {name = 'id', type = 'unsigned'},
            {name = 'bucket_id', type = 'unsigned'},
            {name = 'value', type = 'unsigned'},
            {name = 'payload', type = 'string'},
        },
    })
    space:create_index('primary', {
        parts = {{field = 'id', type = 'unsigned'}},
    })
    space:create_index('bucket_id', {
        parts = {{field = 'bucket_id', type = 'unsigned'}},
        unique = false,
    })
    space:create_index('value', {
        parts = {{field = 'value', type = 'unsigned'}},
        unique = false,
    })

    local fill_batch = 1000
    box.begin()
    for i = 1, tuple_count do
        space:insert({i, bucket_id, i, payload})
        if i % fill_batch == 0 and i ~= tuple_count then
            box.commit()
            box.begin()
        end
    end
    box.commit()

    -- Put the inserted secondary-index entries on disk. Deletes performed by
    -- the measured loop then leave history/tombstones in front of live tuples.
    if engine == 'vinyl' then
        box.snapshot()
    end
    return space
end

local function cleanup_with_persistent_pairs(space)
    local bucket_index = space.index.bucket_id
    local transaction_count = 0
    local count = 0

    -- index:pairs() creates the Vinyl iterator immediately. Constructing it
    -- before box.begin() gives it an internal autocommit read transaction,
    -- rather than binding it to the first delete transaction.
    local gen, param, state = bucket_index:pairs({bucket_id})
    box.begin()
    for _, tuple in gen, param, state do
        space:delete({tuple.id})
        count = count + 1
        if count == batch_size then
            box.commit()
            transaction_count = transaction_count + 1
            count = 0
            box.begin()
        end
    end
    box.commit()
    transaction_count = transaction_count + 1
    return transaction_count
end

local function cleanup(space, mode)
    if mode == 'pairs' then
        return cleanup_with_persistent_pairs(space)
    end

    local bucket_index = space.index.bucket_id
    local after = nil
    local transaction_count = 0

::restart::
    local count = 0
    box.begin()
    local opts = after ~= nil and {after = after} or nil
    for _, tuple in bucket_index:pairs({bucket_id}, opts) do
        space:delete({tuple.id})
        count = count + 1
        if count == batch_size then
            if mode == 'tuple' then
                after = tuple
            elseif mode == 'position' then
                after = bucket_index:tuple_pos(tuple)
            else
                after = nil
            end
            box.commit()
            transaction_count = transaction_count + 1
            goto restart
        end
    end
    box.commit()
    transaction_count = transaction_count + 1
    return transaction_count
end

local function median(values)
    table.sort(values)
    local middle = math.floor(#values / 2) + 1
    if #values % 2 == 1 then
        return values[middle]
    end
    return (values[middle - 1] + values[middle]) / 2
end

print(('Tarantool=%s engine=%s mvcc=%s tuples=%d batch=%d runs=%d ' ..
       'payload=%d'):
      format(_TARANTOOL, engine, tostring(mvcc), tuple_count, batch_size,
             run_count, payload_size))
print('mode run wall_seconds cpu_seconds transactions')

for _, mode in ipairs(modes) do
    local walls = {}
    local cpus = {}
    for run = 1, run_count do
        local name = ('bench_%s_%d'):format(mode, run)
        local space = create_and_fill(name)
        collectgarbage('collect')

        local wall_start = clock.monotonic64()
        local cpu_start = clock.proc64()
        local transactions = cleanup(space, mode)
        local cpu = tonumber(clock.proc64() - cpu_start) / 1e9
        local wall = tonumber(clock.monotonic64() - wall_start) / 1e9

        assert(space:count() == 0, mode .. ' left tuples behind')
        walls[run] = wall
        cpus[run] = cpu
        print(('%s %d %.6f %.6f %d'):
              format(mode, run, wall, cpu, transactions))
        space:drop()
    end
    print(('%s median %.6f %.6f'):
          format(mode, median(walls), median(cpus)))
end

os.exit(0)

@locker, can you help us out here, what is better to use here for Vinyl? The one with pairs outside the transaction or pagination with after, the first one is simpler in code, but LLM doesn't like that solution and prefers the after.

[Gerold103]

if pairs() is created inside the explicit transaction,

My proposal is rather that we create an iterator outside of any txns, and then iterate it and do stuff in txns. But the iterator itself would be created before any txns.

Btw, this whole thing about restarting an iterator without after leading to a huge degradation looks more like a bug than like normal behaviour. Why do we have to go through the already deleted stuff?

Yep, we need @locker 😭 🙏!

[Serpentian]

The performance-wise behavior is absolutely the same for MVCC, the difference is 10 times:

RUN_COUNT=1 MODES=restart,tuple,position,pairs ENGINE=memtx MVCC=true TUPLE_COUNT=50000 tarantool /tmp/vshard_gc_cursor_perf.lua 
Tarantool=3.3.0-entrypoint-727-gd324811b07 engine=memtx mvcc=true tuples=50000 batch=100 runs=1 payload=256
mode run wall_seconds cpu_seconds transactions
restart 1 4.465468 4.428404 501
restart median 4.465468 4.428404
tuple 1 0.355984 0.339904 501
tuple median 0.355984 0.339904
position 1 0.373596 0.354531 501
position median 0.373596 0.354531
pairs 1 0.366477 0.339195 501
pairs median 0.366477 0.339195

Perf

-- Microbenchmark for bucket GC iterator restart versus pagination versus a
-- persistent iterator created outside the delete transactions.
--
-- It intentionally implements only the hot loop from
-- gc_bucket_in_space_xc(). This keeps the measurement focused on Vinyl
-- secondary-index prefix scanning rather than VShard setup and recovery.
--
-- Environment variables:
--   TUPLE_COUNT   tuples in the bucket (default: 50000)
--   BATCH_SIZE    deletes per transaction (default: 100)
--   RUN_COUNT     fresh-space runs per mode (default: 3)
--   PAYLOAD_SIZE  bytes in the non-indexed value (default: 256)
--   ENGINE        vinyl or memtx (default: vinyl)
--   MVCC          true to enable the MemTX MVCC engine (default: false)
--   MODES         comma-separated restart,tuple,position,pairs
--                 (default: restart,position,pairs)
--
-- The "tuple" mode passes the last tuple through the pagination API. The
-- "position" mode stores index:tuple_pos(tuple), which avoids the vulnerable
-- tuple-pagination path on older Tarantool 3.x releases. The "pairs" mode
-- creates one index:pairs() iterator before the first box.begin() and keeps it
-- while committing and beginning all delete batches.

local clock = require('clock')
local fio = require('fio')

local function getenv_number(name, default)
    local value = os.getenv(name)
    if value == nil then
        return default
    end
    value = tonumber(value)
    assert(value ~= nil and value > 0, name .. ' must be a positive number')
    return value
end

local tuple_count = getenv_number('TUPLE_COUNT', 50000)
local batch_size = getenv_number('BATCH_SIZE', 100)
local run_count = getenv_number('RUN_COUNT', 3)
local payload_size = getenv_number('PAYLOAD_SIZE', 256)
local engine = os.getenv('ENGINE') or 'vinyl'
assert(engine == 'vinyl' or engine == 'memtx',
       'ENGINE must be vinyl or memtx')
local mvcc = os.getenv('MVCC') == 'true'

local modes = {}
for mode in (os.getenv('MODES') or 'restart,position,pairs'):gmatch('[^,]+') do
    assert(mode == 'restart' or mode == 'tuple' or mode == 'position' or
           mode == 'pairs', 'unknown mode: ' .. mode)
    table.insert(modes, mode)
end
assert(#modes > 0, 'MODES must not be empty')

local data_dir = fio.tempdir()
box.cfg({
    log = fio.pathjoin(data_dir, 'tarantool.log'),
    memtx_dir = data_dir,
    vinyl_dir = data_dir,
    wal_dir = data_dir,
    vinyl_memory = 128 * 1024 * 1024,
    memtx_use_mvcc_engine = mvcc,
})

local bucket_id = 1
local payload = string.rep('x', payload_size)

local function create_and_fill(name)
    local space = box.schema.space.create(name, {
        engine = engine,
        format = {
            {name = 'id', type = 'unsigned'},
            {name = 'bucket_id', type = 'unsigned'},
            {name = 'value', type = 'unsigned'},
            {name = 'payload', type = 'string'},
        },
    })
    space:create_index('primary', {
        parts = {{field = 'id', type = 'unsigned'}},
    })
    space:create_index('bucket_id', {
        parts = {{field = 'bucket_id', type = 'unsigned'}},
        unique = false,
    })
    space:create_index('value', {
        parts = {{field = 'value', type = 'unsigned'}},
        unique = false,
    })

    local fill_batch = 1000
    box.begin()
    for i = 1, tuple_count do
        space:insert({i, bucket_id, i, payload})
        if i % fill_batch == 0 and i ~= tuple_count then
            box.commit()
            box.begin()
        end
    end
    box.commit()

    -- Put the inserted secondary-index entries on disk. Deletes performed by
    -- the measured loop then leave history/tombstones in front of live tuples.
    if engine == 'vinyl' then
        box.snapshot()
    end
    return space
end

local function cleanup_with_persistent_pairs(space)
    local bucket_index = space.index.bucket_id
    local transaction_count = 0
    local count = 0

    -- index:pairs() creates the Vinyl iterator immediately. Constructing it
    -- before box.begin() gives it an internal autocommit read transaction,
    -- rather than binding it to the first delete transaction.
    local gen, param, state = bucket_index:pairs({bucket_id})
    box.begin()
    for _, tuple in gen, param, state do
        space:delete({tuple.id})
        count = count + 1
        if count == batch_size then
            box.commit()
            transaction_count = transaction_count + 1
            count = 0
            box.begin()
        end
    end
    box.commit()
    transaction_count = transaction_count + 1
    return transaction_count
end

local function cleanup(space, mode)
    if mode == 'pairs' then
        return cleanup_with_persistent_pairs(space)
    end

    local bucket_index = space.index.bucket_id
    local after = nil
    local transaction_count = 0

::restart::
    local count = 0
    box.begin()
    local opts = after ~= nil and {after = after} or nil
    for _, tuple in bucket_index:pairs({bucket_id}, opts) do
        space:delete({tuple.id})
        count = count + 1
        if count == batch_size then
            if mode == 'tuple' then
                after = tuple
            elseif mode == 'position' then
                after = bucket_index:tuple_pos(tuple)
            else
                after = nil
            end
            box.commit()
            transaction_count = transaction_count + 1
            goto restart
        end
    end
    box.commit()
    transaction_count = transaction_count + 1
    return transaction_count
end

local function median(values)
    table.sort(values)
    local middle = math.floor(#values / 2) + 1
    if #values % 2 == 1 then
        return values[middle]
    end
    return (values[middle - 1] + values[middle]) / 2
end

print(('Tarantool=%s engine=%s mvcc=%s tuples=%d batch=%d runs=%d ' ..
       'payload=%d'):
      format(_TARANTOOL, engine, tostring(mvcc), tuple_count, batch_size,
             run_count, payload_size))
print('mode run wall_seconds cpu_seconds transactions')

for _, mode in ipairs(modes) do
    local walls = {}
    local cpus = {}
    for run = 1, run_count do
        local name = ('bench_%s_%d'):format(mode, run)
        local space = create_and_fill(name)
        collectgarbage('collect')

        local wall_start = clock.monotonic64()
        local cpu_start = clock.proc64()
        local transactions = cleanup(space, mode)
        local cpu = tonumber(clock.proc64() - cpu_start) / 1e9
        local wall = tonumber(clock.monotonic64() - wall_start) / 1e9

        assert(space:count() == 0, mode .. ' left tuples behind')
        walls[run] = wall
        cpus[run] = cpu
        print(('%s %d %.6f %.6f %d'):
              format(mode, run, wall, cpu, transactions))
        space:drop()
    end
    print(('%s median %.6f %.6f'):
          format(mode, median(walls), median(cpus)))
end

os.exit(0)

Maybe @drewdzzz can help us here and explain, whether it's a bug or expected behavior in MVCC.

[locker]

@locker, can you help us out here, what is better to use here for Vinyl? The one with pairs outside the transaction or pagination with after, the first one is simpler in code, but LLM doesn't like that solution and prefers the after.

Behavior of an iterator created outside a transaction differs between memtx and vinyl: tarantool/tarantool#11070. A vinyl iterator is sent to a read view in case of a conflict, which prevents compaction from collecting tombstone. This will probably be fixed eventually because it prevents us from implementing space upgrade for vinyl.

Anyway, why not just restart the iterator from the last deleted key instead of using pagination? We do this in Aeon: https://github.com/tarantool/aeon/commit/a2d022f1a73ebed3f76ee3724d057fba0834f7a1.

Btw, this whole thing about restarting an iterator without after leading to a huge degradation looks more like a bug than like normal behaviour. Why do we have to go through the already deleted stuff?

Because this is an iterator works in vinyl: it has to go through all statements starting from the given key. We could bump compaction priority (tarantool/tarantool#3225) or introduce range deletion (tarantool/tarantool#11335) to improve on that.

[Serpentian]

Anyway, why not just restart the iterator from the last deleted key instead of using pagination? We do this in Aeon: https://github.com/tarantool/aeon/commit/a2d022f1a73ebed3f76ee3724d057fba0834f7a1.

Aeon iterates a primary index, so the usage of GT is justified. But vshard iterates over non-unique secondary bucket_id index, it seems, we cannot apply Aeon's approach here. Or am I missing smth?

[locker]

Anyway, why not just restart the iterator from the last deleted key instead of using pagination? We do this in Aeon: tarantool/aeon@a2d022f.

Aeon iterates a primary index, so the usage of GT is justified. But vshard iterates over non-unique secondary bucket_id index, it seems, we cannot apply Aeon's approach here. Or am I missing smth?

Right. You could include primary index parts in the secondary index. Basically, you'd do the same thing that pagination does under the hood. Or you can use pagination restarting the iterator in each transaction with after - this would work as well.

[Serpentian]

And why not the iterator outside the transaction?

A vinyl iterator is sent to a read view in case of a conflict, which prevents compaction from collecting tombstone

Sorry, I don't understand, how will that affect user(

This will probably be fixed eventually because it prevents us from implementing space upgrade for vinyl.

This sounds like an argument for using pairs instead of pagination. Pagination doesn't work with all TREE indexes, the approach with pairs works (#662 (comment))

[drewdzzz]

Pagination doesn't work with all TREE indexes

AFAIR, it works with all TREE indexes - some of them just don't support tuple_pos. Couldn't you just use select with limit = batch_size - it has fetch_pos option that automatically extracts position from the last tuple - and it works with all the TREE index types.

[drewdzzz]

Regarding slowdown caused by memtx MVCC. I suspect this issue is the reason - tarantool/tarantool#12038. Deleted tuples are not garbage collected by MVCC so Tarantool iterates over them on each iterator creation.

This issue is quite fixable for MemTX, I just deprioritized it. But vinyl has the same problem, as locker has mentioned above, and I suspect its fix (or an improvement, at least) is much more complicated.

IMO, this case is perfect for pagination. The only stopper here is that you use pairs that doesn't allow to do pagination with all TREE index types. What we could do about that:

1. You could use select.
2. We could try to support all TREE index types for pairs. At the first glance, it shouldn't be complicated (but I'm not sure, and it will take some time anyway).
3. We could support tuple_pos for functional indexes, it shouldn't be complicated as well. But we can't support it for multikey indexes by design. Though, is multikey index a proper one for bucket_id at all?

[Serpentian]

AFAIR, it works with all TREE indexes

The only stopper here is that you use pairs that doesn't allow to do pagination with all TREE index types.

You contradict yourself)

AFAIR, it works with all TREE indexes

Nope, it doesn't:

Example

local function check(name, space, index, prefix, expected)
    assert(index.type == 'TREE')
    assert(index.parts[1].type == 'unsigned')
    local tuple = index:select(prefix, {limit = 1})[1]
    assert(tuple ~= nil)

    local ok, err = pcall(index.pairs, index, prefix, {after = tuple})
    assert(not ok and tostring(err):find(expected, 1, true))
    print(('%s: pairs{after = tuple} -> %s'):format(name, tostring(err)))
end

box.cfg()

-- 1. A regular JSON-path multikey index. The bucket part is scalar and a
-- later key part is multikey. This is the most plausible accidental VShard
-- schema: bucket prefix scans work normally until `after = tuple` is used.
local s1 = box.schema.space.create('json_multikey_later_part')
s1:create_index('primary')
local i1 = s1:create_index('bucket_id', {
    type = 'TREE',
    unique = false,
    parts = {
        {field = 2, type = 'unsigned'},
        {field = 3, type = 'string', path = '[*]'},
    },
})
s1:insert({1, 10, {'tag'}})
check('json_multikey_later_part', s1, i1, {10},
      'Multikey index does not support position by tuple')

-- 2. A regular JSON-path multikey index whose first (bucket) part itself is
-- multikey. VShard discovery accepts it because it checks only the part type,
-- although assigning one tuple to multiple buckets violates VShard's normal
-- data model.
local s2 = box.schema.space.create('json_multikey_bucket_part')
s2:create_index('primary')
local i2 = s2:create_index('bucket_id', {
    type = 'TREE',
    unique = false,
    parts = {
        {field = 2, type = 'unsigned', path = '[*]'},
    },
})
s2:insert({1, {10}})
check('json_multikey_bucket_part', s2, i2, {10},
      'Multikey index does not support position by tuple')

-- 3. A single-key functional index. Its declared parts describe fields in the
-- key returned by the function, so the unsigned first part passes VShard
-- discovery.
box.schema.func.create('extract_bucket', {
    body = [[function(tuple) return {tuple[2]} end]],
    is_deterministic = true,
    is_sandboxed = true,
})
local s3 = box.schema.space.create('functional')
s3:create_index('primary')
local i3 = s3:create_index('bucket_id', {
    type = 'TREE',
    unique = false,
    func = 'extract_bucket',
    parts = {{field = 1, type = 'unsigned'}},
})
s3:insert({1, 10})
check('functional', s3, i3, {10},
      'Functional index does not support position by tuple')

-- 4. A functional multikey index. It has both unsupported properties, but the
-- functional-index check runs first, so Tarantool reports it as functional.
box.schema.func.create('extract_bucket_multikey', {
    body = [[function(tuple) return {{tuple[2]}} end]],
    is_deterministic = true,
    is_sandboxed = true,
    is_multikey = true,
})
local s4 = box.schema.space.create('functional_multikey')
s4:create_index('primary')
local i4 = s4:create_index('bucket_id', {
    type = 'TREE',
    unique = false,
    func = 'extract_bucket_multikey',
    parts = {{field = 1, type = 'unsigned'}},
})
s4:insert({1, 10})
check('functional_multikey', s4, i4, {10},
      'Functional index does not support position by tuple')

os.exit(0)

---

At the end I see no reason not to use the pairs outside the transaction, it's the simplest solution code-wise and works everywhere. @locker, @drewdzzz, are we ok with pairs outside the transaction?

I see no reason to re-implement the after as Vladimir proposes, there definitely a reason, why it still doesn't work with all TREE indexes. Using after itself is also difficult and requires checking whether index supports it. select is not the way (proposed by Andrey), We can easily run out of Lua memory. The last too solutions from Andrey won't be implemented soon, and Vshard supports old versions (even 1.10), the fix in vshard will bump the perf for all of the versions.

A vinyl iterator is sent to a read view in case of a conflict, which prevents compaction from collecting tombstone

@locker. Sorry, I don't understand, how will that affect user( Could you elaborate please?