Search on IndexWriter's RAM Buffer [LUCENE-2312]

[asfimport]

In order to offer user's near realtime search, without incurring
an indexing performance penalty, we can implement search on
IndexWriter's RAM buffer. This is the buffer that is filled in
RAM as documents are indexed. Currently the RAM buffer is
flushed to the underlying directory (usually disk) before being
made searchable.

Todays Lucene based NRT systems must incur the cost of merging
segments, which can slow indexing.

Michael Busch has good suggestions regarding how to handle deletes using max doc ids.
https://issues.apache.org/jira/browse/LUCENE-2293?focusedCommentId=12841923&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#action_12841923

The area that isn't fully fleshed out is the terms dictionary,
which needs to be sorted prior to queries executing. Currently
IW implements a specialized hash table. Michael B has a
suggestion here:
https://issues.apache.org/jira/browse/LUCENE-2293?focusedCommentId=12841915&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#action_12841915

---

Migrated from LUCENE-2312 by Jason Rutherglen, updated Sep 09 2011
Attachments: LUCENE-2312.patch (versions: 3), LUCENE-2312-FC.patch
Linked issues:

• Per thread DocumentsWriters that write their own private segments [LUCENE-2324] #3400
• Concurrent byte and int block implementations [LUCENE-2575] #3649
• Add non-desctructive sort to BytesRefHash [LUCENE-3199] #4272
• Enable replace-able field caches [LUCENE-3399] #4472
• Explore other in-memory postinglist formats for realtime search [LUCENE-2346] #3422
• CASSANDRA-2915

[asfimport]

Jason Rutherglen (migrated from JIRA)

In regards to the terms dictionary, keeping it sorted or not, I think it's best to sort it on demand because otherwise there will be yet another parameter to pass into IW (i.e. sortRAMBufTerms or something like that).

[asfimport]

Jason Rutherglen (migrated from JIRA)

I set out implementing a simple method DocumentsWriter.getTerms
which should return a sorted array of terms over the current RAM
buffer. While I think this can be implemented, there's a lot of
code in the index package to handle multiple threads, which is
fine, except I'm concerned the interleaving of postings won't
perform well. So I think we'd want to implement what's been
discussed in #3369, per thread ram buffers. With that
change, it seems implementing this issue could be
straightforward.

[asfimport]

Jason Rutherglen (migrated from JIRA)

From #3369: > (b-tree, or, simply sort-on-demand the

first time a query needs it, though that cost increases the
larger your RAM segments get, ie, not incremental to the # docs
you just added)

For the terms dictionary, perhaps a terms array (this could be a
RawPostingList[], or an array of objects with pointers to a
RawPostingList with some helper methods like getTerm and
compareTo), is kept in sorted order, we then binary search and
insert new RawPostingLists/terms into the array. We could
implement a 2 dimensional array, allowing us to make a per
reader copy of the 1st dimension of array. This would maintain
transactional consistency (ie, a reader's array isn't changing
as a term enum is traversing in another thread).

Also, we have to solve what happens to a reader using a
RAM segment that's been flushed. Perhaps we don't reuse RAM at
that point, ie, rely on GC to reclaim once all readers using
that RAM segment have closed.

I don't think we have a choice here?

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

For the terms dictionary, perhaps a terms array (this could be a
RawPostingList[], or an array of objects with pointers to a
RawPostingList with some helper methods like getTerm and
compareTo), is kept in sorted order, we then binary search and
insert new RawPostingLists/terms into the array. We could
implement a 2 dimensional array, allowing us to make a per
reader copy of the 1st dimension of array. This would maintain
transactional consistency (ie, a reader's array isn't changing
as a term enum is traversing in another thread).

I don't think we can do term insertion into an array – that's O(N^2)
insertion cost – we should use a btree instead.

Also, we could store the first docID stored into the term, too – this
way we could have a ordered collection of terms, that's shared across
several open readers even as changes are still being made, but each
reader skips a given term if its first docID is greater than the
maxDoc it's searching. That'd give us point in time searching even
while we add terms with time...

Also, we have to solve what happens to a reader using a RAM segment that's been flushed. Perhaps we don't reuse RAM at that point, ie, rely on GC to reclaim once all readers using that RAM segment have closed.

I don't think we have a choice here?

I think we do have a choice.

EG we could force the reader to cutover to the newly flushed segment
(which should be identical to the RAM segment), eg by making [say] a
DelegatingSegmentReader.

Still... we'd probably have to not re-use in that case, since there
can be queries in-flight stepping through the RAM postings, and, we
have no way to accurately detect they are done. But at least with
this approach we wouldn't tie up RAM indefinitely...

Or maybe we simply state that the APP must aggressively close NRT
readers with time else memory use grows and grows... but I don't
really like that. We don't have such a restriction today...

[asfimport]

Jason Rutherglen (migrated from JIRA)

Mike, Why does DocFieldConsumers have DocFieldConsumer one and two? How is this class used? Thanks.

[asfimport]

Michael Busch (migrated from JIRA)

Also, we could store the first docID stored into the term, too - this
way we could have a ordered collection of terms, that's shared across
several open readers even as changes are still being made, but each
reader skips a given term if its first docID is greater than the
maxDoc it's searching. That'd give us point in time searching even
while we add terms with time...

Exactly. This is what I meant in my comment:
https://issues.apache.org/jira/browse/LUCENE-2293?focusedCommentId=12841915&page=com.atlassian.jira.plugin.system.issuetabpanels%3Acomment-tabpanel#action_12841915

But I mistakenly said lastDocID; of course firstDocID is correct.

[asfimport]

Michael Busch (migrated from JIRA)

I'll try to tackle this one!

[asfimport]

Jason Rutherglen (migrated from JIRA)

A few notes so far:

• IW flush could become thread dependent (eg, it'll only flush
  for the current doc writer) or maybe it should flush all doc
  writers? Close will shut down and flush all doc writers.

• A new term will first check the hash table for existence (as
  currently), if it's not in the term hash table only then will it
  be added to the btree (btw, binary search is O(log N) on
  average?) This way we're avoiding the somewhat costlier btree
  existence check per token.

• The algorithm for flushing doc writers based on RAM
  consumption can simply be, on exceed, flush the doc writer
  consuming the most RAM?

• I gutted the PerThread classes, then realized, it's all too
  intertwined. I'd rather get something working, than spend an
  excessive amount of time rearranging code that already works.

[asfimport]

Jason Rutherglen (migrated from JIRA)

• IW commitMerge calls docWriter's remapDeletes, a synchronized method to prevent concurrent updates. I'm not sure how we should efficiently block calls to the different DW's.

• _mergeInit calls docWriter getDocStoreSegment - unsure what to change

• Some of the config settings (such as maxBufferedDocs) can simply be removed from DW, and instead accessed via WriterConfig

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

Michael are you also going to [first] tackle truly separating the RAM segments? I think we need this first ...

Mike, Why does DocFieldConsumers have DocFieldConsumer one and two? How is this class used? Thanks.

This is so we can make a "tee" in the indexing chain. Here's the default chain (copied out of comment in DW):

DocConsumer / DocConsumerPerThread
  --> code: DocFieldProcessor / DocFieldProcessorPerThread
    --> DocFieldConsumer / DocFieldConsumerPerThread / DocFieldConsumerPerField
      --> code: DocFieldConsumers / DocFieldConsumersPerThread / DocFieldConsumersPerField
        --> code: DocInverter / DocInverterPerThread / DocInverterPerField
          --> InvertedDocConsumer / InvertedDocConsumerPerThread / InvertedDocConsumerPerField
            --> code: TermsHash / TermsHashPerThread / TermsHashPerField
              --> TermsHashConsumer / TermsHashConsumerPerThread / TermsHashConsumerPerField
                --> code: FreqProxTermsWriter / FreqProxTermsWriterPerThread / FreqProxTermsWriterPerField
                --> code: TermVectorsTermsWriter / TermVectorsTermsWriterPerThread / TermVectorsTermsWriterPerField
          --> InvertedDocEndConsumer / InvertedDocConsumerPerThread / InvertedDocConsumerPerField
            --> code: NormsWriter / NormsWriterPerThread / NormsWriterPerField
        --> code: StoredFieldsWriter / StoredFieldsWriterPerThread / StoredFieldsWriterPerField

The tee is so the doc fields can go to both DocInvert (for creating postings & term vectors) and to stored fields writer.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

IW flush could become thread dependent

Right, we want this – different RAM segments should be flushed at different times. This gives us better concurrency since IO/CPU resource consumption will now be more interleaved. While one RAM segment is flushing, the others are still indexing.

A new term will first check the hash table for existence (as
currently), if it's not in the term hash table only then will it
be added to the btree (btw, binary search is O(log N) on
average?) This way we're avoiding the somewhat costlier btree
existence check per token.

Yes, we could have btree on-the-side but still use hash for mapping (vs using btree alone). Hash will be faster lookups... btree could be created/updated on demand first time something needs to .next() through the TermsEnum.

{quote
The algorithm for flushing doc writers based on RAM
consumption can simply be, on exceed, flush the doc writer
consuming the most RAM

Sounds good :) The challenge will be balancing things... eg if during the time 1 RAM segment is flushed, the others are able to consume more RAM that was freed up by flushing this one RAM segment, you've got a problem... or maybe at that point you go and flush the next one now using the most RAM, so it'd self balance with time.

This will mean the RAM usage is able to flare up above the high water mark...

I gutted the PerThread classes, then realized, it's all too
intertwined. I'd rather get something working, than spend an
excessive amount of time rearranging code that already works.
{quote}

For starters I would keep the *PerThread, but create multiple DWs? Ie, removing the PerThread layer doesn't have to happen at first.

Or we could do the nuclear option – make a new indexing chain.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

IW commitMerge calls docWriter's remapDeletes, a synchronized method to prevent concurrent updates. I'm not sure how we should efficiently block calls to the different DW's.

Yeah this is because when we buffer a delete Term/Query, the docID we store against it is absolute. It seems like it could/should be relative (ie, within the RAM segment), then remapping wouldn't be needed when a merge commits. I think?

_mergeInit calls docWriter getDocStoreSegment - unsure what to change

It wouldn't anymore once we have private RAM segments: we would no longer share doc stores across segments, meaning merging will always merge doc stores and there's no need to call that method nor have all the logic in SegmentMerger to determine whether doc store merging is required.

This will necessarily be a perf hit when up and building a large index from scratch in a single IW session. Today that index creates one large set of doc stores and never has to merge it while building. This is the biggest perf downside to this change, I think.

But maybe the perf loss will not be so bad, because of bulk merging, in the case when all docs always add the same fields in the same order. Or... if we could fix lucene to always bind the same field name to the same field number (#2811) then we'd always bulk-merge regardless of which & which order app adds fields to docs.

Some of the config settings (such as maxBufferedDocs) can simply be removed from DW, and instead accessed via WriterConfig

Ahh, you mean push IWC down to DW? That sounds great.

[asfimport]

Jason Rutherglen (migrated from JIRA)

Mike, rollback is pausing all threads and calling doc writer abort. This should probably happen across all (per thread) doc writers?

[asfimport]

Michael Busch (migrated from JIRA)

Well, we need to keep our transactional semantics. So I assume while a flush will happen per doc writer independently, a commit will trigger all (per thread) doc writers to flush. Then a rollback also has to abort all per thread doc writers.

[asfimport]

Michael Busch (migrated from JIRA)

Michael are you also going to [first] tackle truly separating the RAM segments? I think we need this first ...

Yeah I agree. I started working on a patch for separating the doc writers already.

I also have a separate indexing chain prototype working with searchable RAM buffer (single-threaded), but slightly different postinglist format (some docs nowadays only have 140 characters ;) ). It seems really fast. I spent a long time thinking about lock-free algorithms and data structures, so indexing performance should be completely independent of the search load (in theory). I need to think a bit more about how to make it work with "normal" documents and Lucene's current in-memory format.