You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Shikhar Bhushan <sb...@etsy.com> on 2013/10/20 00:18:24 UTC

Refactoring Collector interface for parallelism

I got inspired by Uwe Schindler's talk "Is your index reader really atomic
or maybe slow?"<http://www.lucenerevolution.org/sites/default/files/Schindler%20-%20IsYourIndexReaderReallyAtomicOrMaybeSlow_0.pdf>to
look into the state of parallelism when searching across segments. It
seems there has been some effort to do this but we never went all the way.

IndexSearcher has an optional constructor arg for an ExecutorService, which
gets used for searching in parallel for call paths where one of the
TopDocCollector's is created internally. The per-segment search happens in
parallel and then the TopDocs/TopFieldDocs results are merged with locking
around the merge bit.

What's the upside when performing parallel search? I benchmarked using
luceneutil on WIKI_MEDIUM_10M with trunk vs trunk with IndexSearcher
constructor hacked to initialize a
ForkJoinPool<https://gist.github.com/anonymous/7048089>
.

Report after iter 19:
                    TaskQPS baseline      StdDev QPS patched      StdDev
             Pct diff
                 Respell       63.05      (3.0%)       46.37      (2.9%)
 -26.5% ( -31% -  -21%)
                PKLookup      255.80      (2.6%)      194.11      (7.4%)
 -24.1% ( -33% -  -14%)
                  Fuzzy2       54.66      (3.8%)       42.28      (3.5%)
 -22.7% ( -28% -  -16%)
                  Fuzzy1       75.35      (2.9%)       59.23      (4.2%)
 -21.4% ( -27% -  -14%)
         MedSloppyPhrase      141.74      (3.6%)      124.56      (9.7%)
 -12.1% ( -24% -    1%)
              AndHighLow      922.70      (3.1%)      908.18     (10.0%)
-1.6% ( -14% -   11%)
         LowSloppyPhrase       88.50      (4.2%)      106.64     (13.0%)
20.5% (   3% -   39%)
                 LowTerm      694.97      (2.7%)      949.30     (21.6%)
36.6% (  11% -   62%)
             MedSpanNear      102.47      (3.0%)      160.94     (12.7%)
57.1% (  40% -   75%)
            OrNotHighLow       98.58      (4.9%)      155.22     (18.1%)
57.5% (  32% -   84%)
              AndHighMed      260.31      (1.7%)      448.19     (23.5%)
72.2% (  46% -   99%)
               OrHighLow      101.68      (6.7%)      179.91     (27.8%)
76.9% (  39% -  119%)
                 MedTerm      200.49      (3.1%)      365.70     (32.8%)
82.4% (  45% -  122%)
                HighTerm      145.36      (3.3%)      268.51     (27.7%)
84.7% (  51% -  119%)
                 Prefix3       81.59      (2.8%)      153.52     (24.8%)
88.2% (  58% -  119%)
            OrHighNotLow       50.67      (6.9%)       95.91     (22.5%)
89.3% (  56% -  127%)
               OrHighMed       93.37      (6.3%)      182.37     (24.3%)
95.3% (  60% -  134%)
            OrHighNotMed       78.19      (6.7%)      153.30     (30.7%)
96.1% (  54% -  143%)
              OrHighHigh       46.59      (7.0%)       92.33     (31.7%)
98.2% (  55% -  147%)
           OrHighNotHigh       51.01      (5.7%)      105.32     (25.1%)
 106.5% (  71% -  145%)
                Wildcard       78.53      (3.7%)      168.42     (40.8%)
 114.5% (  67% -  164%)
           OrNotHighHigh       40.42      (5.5%)       93.45     (29.5%)
 131.2% (  91% -  175%)
            OrNotHighMed       24.40      (4.8%)       57.00     (22.0%)
 133.6% ( 102% -  168%)
            HighSpanNear        4.13      (3.6%)       10.09     (10.5%)
 144.3% ( 125% -  164%)
             LowSpanNear       14.27      (2.3%)       35.24     (17.0%)
 147.0% ( 124% -  170%)
                  IntNRQ        8.73      (4.8%)       21.69     (23.6%)
 148.6% ( 114% -  185%)
               LowPhrase       29.11      (2.9%)       72.87     (22.4%)
 150.3% ( 121% -  180%)
               MedPhrase       33.19      (3.4%)       83.38     (40.4%)
 151.3% ( 103% -  201%)
        HighSloppyPhrase        6.46      (5.8%)       16.37     (21.9%)
 153.5% ( 119% -  192%)
              HighPhrase       10.00      (6.8%)       25.66     (14.4%)
 156.7% ( 126% -  190%)
             AndHighHigh       44.82      (1.1%)      115.77     (39.6%)
 158.3% ( 116% -  201%)

That looks pretty awesome! Any feedback from existing users?
*
*
*Problems*

   - (relatively minor) Solr can't take advantage of this yet.
   SolrIndexSearcher's disregard the possibility of propagating an
   ExecutorService up to IndexSearcher constructor.
   - Even if it did, as far as I can tell Solr does not make use of
   IndexSearcher's search() variants that create TopDocCollector's internally
   and parallelize in the presence of the executor.
   - If arbitary Collector args come into play, we don't/can't parallelize.
   Note that even if ultimately results are going to a TopDocCollector it may
   be wrapped inside e.g. a EarlyTerminatingCollector or TimeLimitingCollector
   or both.
   - The special-casing with parallelism layered on top as IndexSearcher
   does with TopDocCollector's does not scale, there are lots* *of
   Collector's that could be potentially lend themselves to parallelism.

*Idea*
*
*

I have been exploring a refactoring of Collector's that allows for
parallelization at the level of the collection protocol. Some of the
design decisions:

   - easy migration path for collectors that want to remain serial
   - the parallelization should be composable (when Collector's wrap
other Collector's)
   - allow collector's to pick the optimal solution (e.g. there might
be memory tradeoffs to be made) by advising the collector about
whether a search will be parallelized
   - encourage use of lock-free parallelism by providing for a
segment-level done() method that is guaranteed to execute in a
single-threaded manner (so if you were to accumulate some state at the
segment-level, it can be safely merged with the composite state
without use of locking)

The code is currently in a fork on github
<https://github.com/shikhar/lucene-solr/compare/apache:trunk...trunk>.

   - Collector goes from being an abstract class to this interface
<https://github.com/shikhar/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/Collector.java>.
A new interface SubCollector
<https://github.com/shikhar/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/SubCollector.java>
is introduced.
   - The existing subclasses of Collector can choose to either
implement the new interface, or subclass a SerialCollector
<https://github.com/shikhar/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/SerialCollector.java>
abstract class which maintains essentially the same API as before.
   - There is javadoc on the new interfaces, but the new collection
protocol is probably clearer in connection with the usage from
IndexSearcher <https://github.com/shikhar/lucene-solr/blob/b3098fc/lucene/core/src/java/org/apache/lucene/search/IndexSearcher.java#L571-L636>.
   - I tried to convert at least all of the collectors that wrap other
collectors over to the new interface, rather than simply extending
SerialCollector (also introduced a new WrappingCollector
<https://github.com/shikhar/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/WrappingCollector.java>
base class), so that the wrappers themselves aren't blockers from a
search being parallelizable. There are probably a few cases I have
missed.
   - An example of a collector that is very easily parallelizable in
the divide-and-conquer style: TotalHitCountCollector
<https://github.com/shikhar/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/TotalHitCountCollector.java>
   - An update of TopScoreDocCollector to being a parallelizable
Collector <https://github.com/shikhar/lucene-solr/commit/b3098fcfdeb302481e93aab93eb77d0cabc72f9b?w=1>,
and corresponding removal of the special-cased parallelism inside
IndexSearcher.

Benchmark results <https://gist.github.com/shikhar/7062026>

*Next steps*
*
*
I would love to get your feedback on the idea and implementation, and how
this could be incorporated into trunk. Code review would be much
appreciated.

Some follow-up work that needs to be done (help needed!):

   - Making TopFieldCollector a parallelizable Collector, like was done for
   TopScoreDocCollector, and removal of the special-casing inside
   IndexSearcher.
   - Solr support -- perhaps making the Executor to be used by
   SolrIndexSearcher configurable from solrconfig.xml.
   - Making more collector's parallelizable - lots of opportunities here. I
   guess this will be an ongoing process.

Looking forward to your thoughts!

Thanks,

Shikhar Bhushan

Re: Refactoring Collector interface for parallelism

Posted by Shikhar Bhushan <sb...@etsy.com>.
Thanks Shawn! I have created these 2 tickets:
https://issues.apache.org/jira/browse/LUCENE-5299 (the refactoring)
https://issues.apache.org/jira/browse/SOLR-5372 (so Solr can take advantage
of it)


On Mon, Oct 21, 2013 at 9:48 AM, Shawn Heisey <so...@elyograg.org> wrote:

> On 10/21/2013 7:10 AM, Shikhar Bhushan wrote:
> > I wanted to add a note as to the motivation for these changes.
> > Essentially we should be able to scale-up better with Solr/Lucene and
> > not just scale-out by sharding. With sharding one enters distributed
> > systems territory with all the pitfalls and failure conditions, which is
> > not ideal especially if your index is not large enough to warrant
> > it. The next frontier seems to be to utilize multiple CPU cores for
> > performing a search request's legwork, and the results are very
> > promising - 2-3x speedups in many cases!
> >
> > Would be great to get a sense of committer interest :) Let me know if I
> > should just open a JIRA with patches.
>
> Although I do not have much understanding of the deep internals, I think
> I can safely say this:  It is almost never a mistake to open an issue in
> Jira and attach a patch, even if the idea ultimately never gets used.
>
> In cases where a patch shows significant performance gains, the code
> needs careful review to make sure that it doesn't break anything or make
> radical changes to the API.  As you might know, major changes to the API
> are typically reserved for the next major release, unless the old API
> can easily be kept and deprecated.
>
> If it's a very good patch, the performance improvement will still be
> significant after any problems are fixed.
>
> Thanks,
> Shawn
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: dev-help@lucene.apache.org
>
>

Re: Refactoring Collector interface for parallelism

Posted by Shawn Heisey <so...@elyograg.org>.
On 10/21/2013 7:10 AM, Shikhar Bhushan wrote:
> I wanted to add a note as to the motivation for these changes.
> Essentially we should be able to scale-up better with Solr/Lucene and
> not just scale-out by sharding. With sharding one enters distributed
> systems territory with all the pitfalls and failure conditions, which is
> not ideal especially if your index is not large enough to warrant
> it. The next frontier seems to be to utilize multiple CPU cores for
> performing a search request's legwork, and the results are very
> promising - 2-3x speedups in many cases!
> 
> Would be great to get a sense of committer interest :) Let me know if I
> should just open a JIRA with patches.

Although I do not have much understanding of the deep internals, I think
I can safely say this:  It is almost never a mistake to open an issue in
Jira and attach a patch, even if the idea ultimately never gets used.

In cases where a patch shows significant performance gains, the code
needs careful review to make sure that it doesn't break anything or make
radical changes to the API.  As you might know, major changes to the API
are typically reserved for the next major release, unless the old API
can easily be kept and deprecated.

If it's a very good patch, the performance improvement will still be
significant after any problems are fixed.

Thanks,
Shawn


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Re: Refactoring Collector interface for parallelism

Posted by Shikhar Bhushan <sb...@etsy.com>.
I wanted to add a note as to the motivation for these changes. Essentially
we should be able to scale-up better with Solr/Lucene and not just
scale-out by sharding. With sharding one enters distributed systems
territory with all the pitfalls and failure conditions, which is not ideal
especially if your index is not large enough to warrant it. The next
frontier seems to be to utilize multiple CPU cores for performing a search
request's legwork, and the results are very promising - 2-3x speedups in
many cases!

Would be great to get a sense of committer interest :) Let me know if I
should just open a JIRA with patches.


On Sat, Oct 19, 2013 at 6:18 PM, Shikhar Bhushan <sb...@etsy.com> wrote:

> I got inspired by Uwe Schindler's talk "Is your index reader really
> atomic or maybe slow?"<http://www.lucenerevolution.org/sites/default/files/Schindler%20-%20IsYourIndexReaderReallyAtomicOrMaybeSlow_0.pdf>to look into the state of parallelism when searching across segments. It
> seems there has been some effort to do this but we never went all the way.
>
> IndexSearcher has an optional constructor arg for an ExecutorService,
> which gets used for searching in parallel for call paths where one of the
> TopDocCollector's is created internally. The per-segment search happens in
> parallel and then the TopDocs/TopFieldDocs results are merged with locking
> around the merge bit.
>
> What's the upside when performing parallel search? I benchmarked using
> luceneutil on WIKI_MEDIUM_10M with trunk vs trunk with IndexSearcher
> constructor hacked to initialize a ForkJoinPool<https://gist.github.com/anonymous/7048089>
> .
>
> Report after iter 19:
>                     TaskQPS baseline      StdDev QPS patched      StdDev
>              Pct diff
>                  Respell       63.05      (3.0%)       46.37      (2.9%)
>  -26.5% ( -31% -  -21%)
>                 PKLookup      255.80      (2.6%)      194.11      (7.4%)
>  -24.1% ( -33% -  -14%)
>                   Fuzzy2       54.66      (3.8%)       42.28      (3.5%)
>  -22.7% ( -28% -  -16%)
>                   Fuzzy1       75.35      (2.9%)       59.23      (4.2%)
>  -21.4% ( -27% -  -14%)
>          MedSloppyPhrase      141.74      (3.6%)      124.56      (9.7%)
>  -12.1% ( -24% -    1%)
>               AndHighLow      922.70      (3.1%)      908.18     (10.0%)
> -1.6% ( -14% -   11%)
>          LowSloppyPhrase       88.50      (4.2%)      106.64     (13.0%)
> 20.5% (   3% -   39%)
>                  LowTerm      694.97      (2.7%)      949.30     (21.6%)
> 36.6% (  11% -   62%)
>              MedSpanNear      102.47      (3.0%)      160.94     (12.7%)
> 57.1% (  40% -   75%)
>             OrNotHighLow       98.58      (4.9%)      155.22     (18.1%)
> 57.5% (  32% -   84%)
>               AndHighMed      260.31      (1.7%)      448.19     (23.5%)
> 72.2% (  46% -   99%)
>                OrHighLow      101.68      (6.7%)      179.91     (27.8%)
> 76.9% (  39% -  119%)
>                  MedTerm      200.49      (3.1%)      365.70     (32.8%)
> 82.4% (  45% -  122%)
>                 HighTerm      145.36      (3.3%)      268.51     (27.7%)
> 84.7% (  51% -  119%)
>                  Prefix3       81.59      (2.8%)      153.52     (24.8%)
> 88.2% (  58% -  119%)
>             OrHighNotLow       50.67      (6.9%)       95.91     (22.5%)
> 89.3% (  56% -  127%)
>                OrHighMed       93.37      (6.3%)      182.37     (24.3%)
> 95.3% (  60% -  134%)
>             OrHighNotMed       78.19      (6.7%)      153.30     (30.7%)
> 96.1% (  54% -  143%)
>               OrHighHigh       46.59      (7.0%)       92.33     (31.7%)
> 98.2% (  55% -  147%)
>            OrHighNotHigh       51.01      (5.7%)      105.32     (25.1%)
>  106.5% (  71% -  145%)
>                 Wildcard       78.53      (3.7%)      168.42     (40.8%)
>  114.5% (  67% -  164%)
>            OrNotHighHigh       40.42      (5.5%)       93.45     (29.5%)
>  131.2% (  91% -  175%)
>             OrNotHighMed       24.40      (4.8%)       57.00     (22.0%)
>  133.6% ( 102% -  168%)
>             HighSpanNear        4.13      (3.6%)       10.09     (10.5%)
>  144.3% ( 125% -  164%)
>              LowSpanNear       14.27      (2.3%)       35.24     (17.0%)
>  147.0% ( 124% -  170%)
>                   IntNRQ        8.73      (4.8%)       21.69     (23.6%)
>  148.6% ( 114% -  185%)
>                LowPhrase       29.11      (2.9%)       72.87     (22.4%)
>  150.3% ( 121% -  180%)
>                MedPhrase       33.19      (3.4%)       83.38     (40.4%)
>  151.3% ( 103% -  201%)
>         HighSloppyPhrase        6.46      (5.8%)       16.37     (21.9%)
>  153.5% ( 119% -  192%)
>               HighPhrase       10.00      (6.8%)       25.66     (14.4%)
>  156.7% ( 126% -  190%)
>              AndHighHigh       44.82      (1.1%)      115.77     (39.6%)
>  158.3% ( 116% -  201%)
>
> That looks pretty awesome! Any feedback from existing users?
> *
> *
> *Problems*
>
>    - (relatively minor) Solr can't take advantage of this yet.
>    SolrIndexSearcher's disregard the possibility of propagating an
>    ExecutorService up to IndexSearcher constructor.
>    - Even if it did, as far as I can tell Solr does not make use of
>    IndexSearcher's search() variants that create TopDocCollector's internally
>    and parallelize in the presence of the executor.
>    - If arbitary Collector args come into play, we don't/can't
>    parallelize. Note that even if ultimately results are going to a
>    TopDocCollector it may be wrapped inside e.g. a EarlyTerminatingCollector
>    or TimeLimitingCollector or both.
>    - The special-casing with parallelism layered on top as IndexSearcher
>    does with TopDocCollector's does not scale, there are lots* *of
>    Collector's that could be potentially lend themselves to parallelism.
>
> *Idea*
> *
> *
>
>
> I have been exploring a refactoring of Collector's that allows for parallelization at the level of the collection protocol. Some of the design decisions:
>
>
>    - easy migration path for collectors that want to remain serial
>
>    - the parallelization should be composable (when Collector's wrap other Collector's)
>    - allow collector's to pick the optimal solution (e.g. there might be memory tradeoffs to be made) by advising the collector about whether a search will be parallelized
>
>    - encourage use of lock-free parallelism by providing for a segment-level done() method that is guaranteed to execute in a single-threaded manner (so if you were to accumulate some state at the segment-level, it can be safely merged with the composite state without use of locking)
>
> The code is currently in a fork on github <https://github.com/shikhar/lucene-solr/compare/apache:trunk...trunk>.
>
>
>    - Collector goes from being an abstract class to this interface <https://github.com/shikhar/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/Collector.java>. A new interface SubCollector <https://github.com/shikhar/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/SubCollector.java> is introduced.
>    - The existing subclasses of Collector can choose to either implement the new interface, or subclass a SerialCollector <https://github.com/shikhar/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/SerialCollector.java> abstract class which maintains essentially the same API as before.
>    - There is javadoc on the new interfaces, but the new collection protocol is probably clearer in connection with the usage from IndexSearcher <https://github.com/shikhar/lucene-solr/blob/b3098fc/lucene/core/src/java/org/apache/lucene/search/IndexSearcher.java#L571-L636>.
>    - I tried to convert at least all of the collectors that wrap other collectors over to the new interface, rather than simply extending SerialCollector (also introduced a new WrappingCollector <https://github.com/shikhar/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/WrappingCollector.java> base class), so that the wrappers themselves aren't blockers from a search being parallelizable. There are probably a few cases I have missed.
>    - An example of a collector that is very easily parallelizable in the divide-and-conquer style: TotalHitCountCollector <https://github.com/shikhar/lucene-solr/blob/trunk/lucene/core/src/java/org/apache/lucene/search/TotalHitCountCollector.java>
>
>    - An update of TopScoreDocCollector to being a parallelizable Collector <https://github.com/shikhar/lucene-solr/commit/b3098fcfdeb302481e93aab93eb77d0cabc72f9b?w=1>, and corresponding removal of the special-cased parallelism inside IndexSearcher.
>
> Benchmark results <https://gist.github.com/shikhar/7062026>
>
> *Next steps*
> *
> *
> I would love to get your feedback on the idea and implementation, and how
> this could be incorporated into trunk. Code review would be much
> appreciated.
>
> Some follow-up work that needs to be done (help needed!):
>
>    - Making TopFieldCollector a parallelizable Collector, like was done
>    for TopScoreDocCollector, and removal of the special-casing inside
>    IndexSearcher.
>    - Solr support -- perhaps making the Executor to be used by
>    SolrIndexSearcher configurable from solrconfig.xml.
>    - Making more collector's parallelizable - lots of opportunities here.
>    I guess this will be an ongoing process.
>
> Looking forward to your thoughts!
>
> Thanks,
>
> Shikhar Bhushan
>