[PATCH 2/2] vinyl: optimize mem iterator for frequently updated keys

[Vladimir Davydov]

On Thu, Feb 28, 2019 at 02:09:24PM +0300, Vladimir Davydov wrote:
> On Thu, Feb 28, 2019 at 12:37:20AM +0300, Vladimir Davydov wrote:
> > If a key is frequently updated, iteration to the next key stored in the
> > memory level can take quite a while, because:
> > 
> >  - In case of GE/GT iterator, vy_mem_iterator_next_key will have to
> >    iterate the tree from left to right to skip older key versions.
> > 
> >  - In case of LE/LT iterator, vy_mem_iterator_find_lsn will have to
> >    iterate the tree from right to left to find the newest key version
> >    visible in the read view.
> > 
> > To avoid that, let's fall back on key lookup if we failed to find an
> > appropriate statement after one iteration, because in this case there's
> > a good chance that there's more statements for this key. This should be
> > fine since a lookup in a memory tree is pretty cheap.
> > ---
> > https://github.com/tarantool/tarantool/commits/dv/vy-optimize-next-key
> > 
> >  src/box/vy_mem.c | 80 ++++++++++++++++++++++++++++++++++++++++----------------
> >  1 file changed, 57 insertions(+), 23 deletions(-)
> 
> Pushed to 2.1. Will backport to 1.10 once stability test passes.

The patch helped - see the attached plots:

 - "before.png" - sysbench latency/RPS results without the fix.
 - "after.png" - sysbench latency/RPS with the fix applied.

Pushed both patches to 1.10.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: before.png
Type: image/png
Size: 123701 bytes
Desc: not available
URL: <https://lists.tarantool.org/pipermail/tarantool-patches/attachments/20190228/c5c4d7a1/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: after.png
Type: image/png
Size: 170799 bytes
Desc: not available
URL: <https://lists.tarantool.org/pipermail/tarantool-patches/attachments/20190228/c5c4d7a1/attachment-0001.png>