memory allocated by index is never reduced

[nekufa]

Tarantool version:
I think any version is affected. I reproduce it on 1.7.5, 1.10.3, 2.1.2, 2.3.1.

OS version:
linux

Bug description:
I found out that space size is less then index size. It happens when rows are removed from space, but index memory is still allocated.

Steps to reproduce:

if box.space.tester then box.space.tester:drop() end
box.schema.create_space('tester')
box.space.tester:format({{name = 'id', type = 'unsigned'}})
box.space.tester:create_index('primary', {type = 'hash', parts = { 1,  'unsigned' }})
local rows = 1000000

box.begin()
local i = 1
while i <= rows do i = i + 1; box.space.tester:insert({i}) end
local i = 1
while i <= rows do i = i+1; box.space.tester:delete(i) end
box.commit()

return {
  version = box.info.version,
  space_size = box.space.tester:bsize(),
  index_size = box.space.tester.index.primary:bsize()
}

-- space_size = 0
-- index_size = 16039936

[kostja]

The issue is not that it doesn't release memory back, but that the memory gets fragmented over time.
This still needs a reproducer though.

[kyukhin]

Still waiting for reproducer.

[alyapunov]

I would say it's not a bug but known behavior. Any index does not free any memory; it stays reserved for further insertions. This approach not only makes implementation easier but have some performance advantages as well. I'm not sure we'll change it anytime soon.

[kostja]

@alyapunov all true, as long as this memory doesn't grow over time. I mentioned that this test case is not complete, it needs tweaks to reproduce a real bug.

[kostja]

on another note, @alyapunov earlier there was a patch which reduces memory fragmentation in slab_arena by sharing the oscillation slab. @kyukhin refused to accept it then, may be you can take a look at it now and queue.

[alyapunov]

Tried to tweak the test. I do not see any trace of fragmentation problem. I fear I don't know where to dig.
Where can I find the patch you mentioned?

Hash index test

tarantool> i = s:create_index('test', {type='hash'})
---
...

tarantool> for i = 1,1000000 do s:replace{i} end
---
...

tarantool> i:bsize()
---
- 16039936
...

tarantool> for i = 1,1000000 do if i%1000 ~= 0 then s:delete{i} end end
---
...

tarantool> i:bsize()
---
- 16039936
...

tarantool> for i = 1000001,2000000 do s:replace{i} end
---
...

tarantool> i:bsize()
---
- 16056320
...

tarantool> i:count()
---
- 1001000
...

Tree index test

tarantool> i = s:create_index('test', {type='tree'})
---
...

tarantool> for i = 1,1000000 do s:replace{i} end
---
...

tarantool> i:bsize()
---
- 11288576
...

tarantool> for i = 1,1000000 do if i%1000 ~= 0 then s:delete{i} end end
---
...

tarantool> i:bsize()
---
- 11288576
...

tarantool> for i = 1000001,2000000 do s:replace{i} end
---
...

tarantool> i:bsize()
---
- 11304960
...

tarantool> i:count()
---
- 1001000
...
for i = 1000001,2000000 do if i%1000 ~= 0 then s:delete{i} end end
---
...

tarantool> for i = 2000001,3000000 do s:insert{i} end
---
...

tarantool> i:bsize()
---
- 11304960
...

tarantool> i:count()
---
- 1002000
...

[kostja]

@alyapunov the delete/insert part should be run in a loop for at least some time: Populate a table to contain 10 000 rows. In a loop: insert 1-1000 rows with autoincrement (random value between 1 and 1000), delete similar number of rows from the first part of the range. Run the test for a while, a few minutes, if not hours, at least.

[alyapunov]

Made exactly suggested test. The last loop lasted for 10-15 minutes. Nothing.

Test

tarantool> i = s:create_index('test', {type='tree'})
---
...

tarantool> v = 0
---
...

tarantool> function fill() while s:count() < 10000 do v = v + 1 s:replace{v} end end
---
...

tarantool> function shrink() for k = 1,1000 do s:delete(i:random(math.random(1000000))) end end
---
...

tarantool> fill()
---
...

tarantool> i:count()
---
- 10000
...

tarantool> i:bsize()
---
- 147456
...

tarantool> shrink()
---
...

tarantool> i:count()
---
- 9000
...

tarantool> i:bsize()
---
- 147456
...

tarantool> for n=1,10000 do fill() shrink() end
---
...

tarantool> i:count()
---
- 9000
...

tarantool> i:bsize()
---
- 163840
...

tarantool> for n=1,10000 do fill() shrink() end
---
...

tarantool> i:count()
---
- 9000
...

tarantool> i:bsize()
---
- 163840
...

tarantool> for n=1,30000 do fill() shrink() end
---
...

tarantool> i:count()
---
- 9000
...

tarantool> i:bsize()
---
- 163840
...

It seems that we're done here.