Batch updates in Ignite B+ tree.

[Pavel Pereslegin]

Hi Igniters!

I am working on implementing batch updates in PageMemory [1] to
improve the performance of preloader, datastreamer and putAll.

This task consists of two major related improvements:
1. Batch writing to PageMemory via FreeList - store several values at
once to single memory page.
2. Batch updates in BPlusTree (for introducing invokeAll operation).

I started to investigate the issue with batch updates in B+ tree, and
it seems that the concurrent top-down balancing algorithm (TD)
described in this paper [2] may be suitable for batch insertion of
keys into Ignite B+ Tree.
This algorithm uses a top-down balancing approach and allows to insert
a batch of keys belonging to the leaves having the same parent. The
negative point of top-down balancing approach is that the parent node
is locked when performing insertion/splitting in child nodes.

WDYT? Do you know other approaches for implementing batch updates in
Ignite B+ Tree?

[1] https://issues.apache.org/jira/browse/IGNITE-7935
[2] https://aaltodoc.aalto.fi/bitstream/handle/123456789/2168/isbn9512258951.pdf

[Vladimir Ozerov]

Hi Pavel,

As far as I know batch tree updates already being developed. Alex, could
you please elaborate?

On Tue, Mar 5, 2019 at 5:05 PM Pavel Pereslegin <[hidden email]> wrote:

> Hi Igniters!
>
> I am working on implementing batch updates in PageMemory [1] to
> improve the performance of preloader, datastreamer and putAll.
>
> This task consists of two major related improvements:
> 1. Batch writing to PageMemory via FreeList - store several values at
> once to single memory page.
> 2. Batch updates in BPlusTree (for introducing invokeAll operation).
>
> I started to investigate the issue with batch updates in B+ tree, and
> it seems that the concurrent top-down balancing algorithm (TD)
> described in this paper [2] may be suitable for batch insertion of
> keys into Ignite B+ Tree.
> This algorithm uses a top-down balancing approach and allows to insert
> a batch of keys belonging to the leaves having the same parent. The
> negative point of top-down balancing approach is that the parent node
> is locked when performing insertion/splitting in child nodes.
>
> WDYT? Do you know other approaches for implementing batch updates in
> Ignite B+ Tree?
>
> [1] https://issues.apache.org/jira/browse/IGNITE-7935
> [2]
> https://aaltodoc.aalto.fi/bitstream/handle/123456789/2168/isbn9512258951.pdf
>

[Alexey Goncharuk]

Hello Pavel, Vladimir,

As far as I know, Semyon Boikov and Sergi Vladykin (CCed) are prototyping
this feature.

Folks, can you comment?


ср, 6 мар. 2019 г. в 10:57, Vladimir Ozerov <[hidden email]>:

> Hi Pavel,
>
> As far as I know batch tree updates already being developed. Alex, could
> you please elaborate?
>
> On Tue, Mar 5, 2019 at 5:05 PM Pavel Pereslegin <[hidden email]> wrote:
>
>> Hi Igniters!
>>
>> I am working on implementing batch updates in PageMemory [1] to
>> improve the performance of preloader, datastreamer and putAll.
>>
>> This task consists of two major related improvements:
>> 1. Batch writing to PageMemory via FreeList - store several values at
>> once to single memory page.
>> 2. Batch updates in BPlusTree (for introducing invokeAll operation).
>>
>> I started to investigate the issue with batch updates in B+ tree, and
>> it seems that the concurrent top-down balancing algorithm (TD)
>> described in this paper [2] may be suitable for batch insertion of
>> keys into Ignite B+ Tree.
>> This algorithm uses a top-down balancing approach and allows to insert
>> a batch of keys belonging to the leaves having the same parent. The
>> negative point of top-down balancing approach is that the parent node
>> is locked when performing insertion/splitting in child nodes.
>>
>> WDYT? Do you know other approaches for implementing batch updates in
>> Ignite B+ Tree?
>>
>> [1] https://issues.apache.org/jira/browse/IGNITE-7935
>> [2]
>> https://aaltodoc.aalto.fi/bitstream/handle/123456789/2168/isbn9512258951.pdf
>>
>

[Pavel Pereslegin]

Folks,

I have prepared draft IEP [1] for batch updates in PageMemory [2].

This IEP contains a description of the proposed changes and a plan for
their implementation.
It does not contain a description for batch insert in B+ Tree, if you are
working on it and have any updates it will be good to add them to an
appropriate topic [3]. If you are not working on this task I'll do it by
myself later.

WDYT?

Also, I have a draft implementation of batch insertions to the FreeList
(without B+ Tree batch updates) and testing results look nice [4].

[1]
https://cwiki.apache.org/confluence/display/IGNITE/IEP-32+Batch+updates+in+PageMemory
[2] https://issues.apache.org/jira/browse/IGNITE-7935
[3]
https://cwiki.apache.org/confluence/display/IGNITE/IEP-32+Batch+updates+in+PageMemory#IEP-32BatchupdatesinPageMemory-BatchupdateinB+Tree
[4]
https://cwiki.apache.org/confluence/display/IGNITE/IEP-32+Batch+updates+in+PageMemory#IEP-32BatchupdatesinPageMemory-Prototypetestingresults


ср, 6 мар. 2019 г. в 14:35, Alexey Goncharuk <[hidden email]>:

> Hello Pavel, Vladimir,
>
> As far as I know, Semyon Boikov and Sergi Vladykin (CCed) are prototyping
> this feature.
>
> Folks, can you comment?
>
>
> ср, 6 мар. 2019 г. в 10:57, Vladimir Ozerov <[hidden email]>:
>
> > Hi Pavel,
> >
> > As far as I know batch tree updates already being developed. Alex, could
> > you please elaborate?
> >
> > On Tue, Mar 5, 2019 at 5:05 PM Pavel Pereslegin <[hidden email]>
> wrote:
> >
> >> Hi Igniters!
> >>
> >> I am working on implementing batch updates in PageMemory [1] to
> >> improve the performance of preloader, datastreamer and putAll.
> >>
> >> This task consists of two major related improvements:
> >> 1. Batch writing to PageMemory via FreeList - store several values at
> >> once to single memory page.
> >> 2. Batch updates in BPlusTree (for introducing invokeAll operation).
> >>
> >> I started to investigate the issue with batch updates in B+ tree, and
> >> it seems that the concurrent top-down balancing algorithm (TD)
> >> described in this paper [2] may be suitable for batch insertion of
> >> keys into Ignite B+ Tree.
> >> This algorithm uses a top-down balancing approach and allows to insert
> >> a batch of keys belonging to the leaves having the same parent. The
> >> negative point of top-down balancing approach is that the parent node
> >> is locked when performing insertion/splitting in child nodes.
> >>
> >> WDYT? Do you know other approaches for implementing batch updates in
> >> Ignite B+ Tree?
> >>
> >> [1] https://issues.apache.org/jira/browse/IGNITE-7935
> >> [2]
> >>
> https://aaltodoc.aalto.fi/bitstream/handle/123456789/2168/isbn9512258951.pdf
> >>
> >
>

[Ivan Pavlukhin]

Pavel and others,

FYI. I noticed a ticket
https://issues.apache.org/jira/browse/IGNITE-11722 It looks related to
the subject.

чт, 14 мар. 2019 г. в 20:04, Pavel Pereslegin <[hidden email]>:

>
> Folks,
>
> I have prepared draft IEP [1] for batch updates in PageMemory [2].
>
> This IEP contains a description of the proposed changes and a plan for
> their implementation.
> It does not contain a description for batch insert in B+ Tree, if you are
> working on it and have any updates it will be good to add them to an
> appropriate topic [3]. If you are not working on this task I'll do it by
> myself later.
>
> WDYT?
>
> Also, I have a draft implementation of batch insertions to the FreeList
> (without B+ Tree batch updates) and testing results look nice [4].
>
> [1]
> https://cwiki.apache.org/confluence/display/IGNITE/IEP-32+Batch+updates+in+PageMemory
> [2] https://issues.apache.org/jira/browse/IGNITE-7935
> [3]
> https://cwiki.apache.org/confluence/display/IGNITE/IEP-32+Batch+updates+in+PageMemory#IEP-32BatchupdatesinPageMemory-BatchupdateinB+Tree
> [4]
> https://cwiki.apache.org/confluence/display/IGNITE/IEP-32+Batch+updates+in+PageMemory#IEP-32BatchupdatesinPageMemory-Prototypetestingresults
>
>
> ср, 6 мар. 2019 г. в 14:35, Alexey Goncharuk <[hidden email]>:
>
> > Hello Pavel, Vladimir,
> >
> > As far as I know, Semyon Boikov and Sergi Vladykin (CCed) are prototyping
> > this feature.
> >
> > Folks, can you comment?
> >
> >
> > ср, 6 мар. 2019 г. в 10:57, Vladimir Ozerov <[hidden email]>:
> >
> > > Hi Pavel,
> > >
> > > As far as I know batch tree updates already being developed. Alex, could
> > > you please elaborate?
> > >
> > > On Tue, Mar 5, 2019 at 5:05 PM Pavel Pereslegin <[hidden email]>
> > wrote:
> > >
> > >> Hi Igniters!
> > >>
> > >> I am working on implementing batch updates in PageMemory [1] to
> > >> improve the performance of preloader, datastreamer and putAll.
> > >>
> > >> This task consists of two major related improvements:
> > >> 1. Batch writing to PageMemory via FreeList - store several values at
> > >> once to single memory page.
> > >> 2. Batch updates in BPlusTree (for introducing invokeAll operation).
> > >>
> > >> I started to investigate the issue with batch updates in B+ tree, and
> > >> it seems that the concurrent top-down balancing algorithm (TD)
> > >> described in this paper [2] may be suitable for batch insertion of
> > >> keys into Ignite B+ Tree.
> > >> This algorithm uses a top-down balancing approach and allows to insert
> > >> a batch of keys belonging to the leaves having the same parent. The
> > >> negative point of top-down balancing approach is that the parent node
> > >> is locked when performing insertion/splitting in child nodes.
> > >>
> > >> WDYT? Do you know other approaches for implementing batch updates in
> > >> Ignite B+ Tree?
> > >>
> > >> [1] https://issues.apache.org/jira/browse/IGNITE-7935
> > >> [2]
> > >>
> > https://aaltodoc.aalto.fi/bitstream/handle/123456789/2168/isbn9512258951.pdf
> > >>
> > >
> >

--
Best regards,
Ivan Pavlukhin