tarantool/queue

Implement ready space storage mode for vinyl engine for utube and utubettl

DerekBum opened this issue · 1 comments

DerekBum commented

This issue will become relevant after merging this PR: #229

Right now new STORAGE_MODE_UTUBE_READY_SPACE storage mode for utube and utubettl implemented only for memtx engine. With vinyl there is a problem with yields inside of space and space.index methods.
Conflict ER_TRANSACTION_CONFLICT: Transaction has been aborted by conflict may be received in a transaction, resulting in incorrect work of the tube.

Possible fix: repeat the transaction in case of a conflict several times.

DerekBum commented

Ready space.

Original issue #228 was fixed by creating new ready space mode for utube and utubettl. The main idea is to store in the new space only first (in priority order) READY task from each ready queue (queues without any TAKEN tasks) at any given moment. And this invariant is crucial for correct queue work.

This mode was implemented only for memtx engine.

Issue overview.

The main problem with vinyl is that it might yield on almost every space method: https://www.tarantool.io/en/doc/latest/concepts/coop_multitasking/#implicit-yields. And this issue is what prevents us from implementing ready space for vinyl.

Right now every operation on a queue requires working with both spaces: main queue space with all tasks and ready space. And in a nutshell, if vinyl will yield between working with different spaces, that will result in breaking invariants of the ready space.

To be more precise.

Utube.

Lets review some examples.

  • Lets say we delete the TAKEN task from the queue. This will result in search for the first READY task to put into ready space:

    queue/queue/abstract/driver/utube.lua

    Lines 310 to 311 in df24f17

    if task[2] == state.TAKEN then
    put_next_ready(self, task[3])

    queue/queue/abstract/driver/utube.lua

    Lines 134 to 150 in df24f17

    -- Find the first ready task for given 'utube'.
    -- Utube is also checked for the absence of 'TAKEN' tasks.
    local function put_next_ready(self, utube)
    local taken = self.space.index.utube:min{state.TAKEN, utube}
    if taken == nil or taken[2] ~= state.TAKEN then
    local next_task = self.space.index.utube:min{state.READY, utube}
    if next_task == nil or next_task[2] ~= state.READY then
    return
    end
    -- Ignoring ER_TUPLE_FOUND error, if a tuple with the same task_id
    -- or utube name is already in the space.
    -- Note that both task_id and utube indexes are unique, so there will be
    -- no duplicates: each task_id can occur in the space not more than once,
    -- there can be no more than one task from each utube in a space.
    pcall(self.space_ready_buffer.insert, self.space_ready_buffer, {next_task[1], utube})
    end
    end

    Lets simulate yield between lines 138 and 139:
    if taken == nil or taken[2] ~= state.TAKEN then
        require('fiber').sleep(10)
        local next_task = self.space.index.utube:min{state.READY, utube}

After that lets open two terminals:

> queue = require('queue')
---
...
> box.cfg()
---
...
> test_queue = queue.create_tube('test_queue', 'utube', {engine = 'vinyl', storage_mode =  queue.driver.utube.STORAGE_MODE_READY_BUFFER})
---
...
> test_queue:put('0', {utube = tostring(1)})
---
- [0, 'r', '0']
...
> test_queue:put('1', {utube = tostring(1)})
---
- [1, 'r', '1']
...
> test_queue:put('2', {utube = tostring(1)})
---
- [2, 'r', '2']
...
> test_queue:take(0)
---
- [0, 't', '0']
...
> test_queue:delete(0)
// sleep here! Need to call take from the second terminal!
---
- [0, '-', '0']
...

Second terminal (after delete call)

> test_queue:take(1)
---
- [1, 't', '1']
...

After all that we will have two taken tasks from the single queue (task 1 and task 2).

  • We can also break this method by putting sleep before line 148 (imitating yield inside insert call). This way we can insert TAKEN or even deleted task into space ready.
  • Same errors could be done for bury and release (they all the same method).
  • Similar thing could be done with an ordinary put.

    queue/queue/abstract/driver/utube.lua

    Lines 152 to 164 in df24f17

    -- Put this task into ready_buffer.
    -- Utube is also checked for the absence of 'TAKEN' tasks.
    local function put_ready(self, id, utube)
    local taken = self.space.index.utube:min{state.TAKEN, utube}
    if taken == nil or taken[2] ~= state.TAKEN then
    -- Ignoring ER_TUPLE_FOUND error, if a tuple with the same task_id
    -- or utube name is already in the space.
    -- Note that both task_id and utube indexes are unique, so there will be
    -- no duplicates: each task_id can occur in the space not more than once,
    -- there can be no more than one task from each utube in a space.
    pcall(self.space_ready_buffer.insert, self.space_ready_buffer, {id, utube})
    end
    end

    We can delete the task after checks on line 156, but before line 162. Thus, we will insert deleted task into ready space.
  • If we take the task and then release it, this could result in absence of utube in the ready space.

    queue/queue/abstract/driver/utube.lua

    Lines 216 to 248 in df24f17

    -- Take the first task form the ready_buffer.
    local function take_ready(self)
    while true do
    local commit_func = begin_if_not_in_txn()
    local task_ready = self.space_ready_buffer.index.task_id:min()
    if task_ready == nil then
    commit_func()
    return nil
    end
    local id = task_ready[1]
    local task = self.space:get(id)
    local take_complete = false
    if task[2] == state.READY then
    local taken = self.space.index.utube:min{state.TAKEN, task[3]}
    if taken == nil or taken[2] ~= state.TAKEN then
    task = self.space:update(id, { { '=', 2, state.TAKEN } })
    self.space_ready_buffer:delete(id)
    take_complete = true
    end
    end
    commit_func()
    if take_complete then
    self.on_task_change(task, 'take')
    return task
    end
    end
    end

    All we need to do is simulate an yield between lines 235 and 236. While yielding we need to release taken task from the second terminal. Thus this task will be READY (as well as this whole utube), but this task will also be deleted from the ready space (without inserting any new tasks).

As we can see, the main problem here is the necessity to work with two separate spaces. Firstly we need to check that all invariants are fulfilled (using main space) and then to update the ready space. And vinyl could yield between these two steps and break those invariants. But given changes will still affect ready space.

Utubettl.

All yield conflicts from above will also work for utubettl. Moreover, there are more nasty bugs while working with ttl and ttr timeouts.

Proposition.

We cannot fix vinyl for this mode implementation. To make it work we need to write another one, without using several spaces (but only one), because any other solution will result in the same bugs as before (some breaking changes between working with different spaces). This is the hard way.

The easy way is to leave vinyl unsupported.