O(n^2) complexity in fifottl:take()

[rtsisyk]

take() degrades to O(N^2) complexity where N is the number of expired tasks:

https://github.com/tarantool/queue/blob/3adda75efab42c8bf437cb554c81d269cfe1b27e/queue/abstract/driver/fifottl.lua#L265-L275

Affects Cloud.

[kostja]

• Roman Tsisyk notifications@github.com [17/10/02 16:32]:

  take() degrades to O(N^2) complexity where N is the number of expired tasks:

  https://github.com/tarantool/queue/blob/3adda75efab42c8bf437cb554c81d269cfe1b27e/queue/abstract/driver/fifottl.lua#L265-L275 Affects Cloud.

I have received numerous complains about this, without exact trace to the root cause.

Let's fix asap.

-- Konstantin Osipov, Moscow, Russia, +7 903 626 22 32 http://tarantool.org - www.twitter.com/kostja_osipov

[RunsFor]

I reproduced it under following conditions:

I put my laptop into sleep mode while it was about 50k tuples in fifottl tube and 10 fibers were constantly taking tasks from it from another instance over a net box connection.

I woke up laptop after ttl was already expired for all tasks and noticed that:

• Tarantool was draining 100% CPU
• Tarantool instance was not respond to any requests (http server, netbox connection, console)
• There was only mmap and munmap syscalls in strace (which means it was stuck inside one event loop)
• gdb was saying that tarantool constantly iterates over the space
• tarantool returned back to normal behaviour after about an hour (all expired tasks was deleted)