Use sequence ids for deleted docs [LUCENE-2558]

[asfimport]

Utilizing the sequence ids created via the update document
methods, we will enable IndexReader deleted docs over a sequence
id array.

One of the decisions is what primitive type to use. We can start
off with an int[], then possibly move to a short[] (for lower
memory consumption) that wraps around.

---

Migrated from LUCENE-2558 by Jason Rutherglen, updated May 09 2016

[asfimport]

Jason Rutherglen (migrated from JIRA)

I tried to start on this however, nothing can be deleted without the terms dictionary and the terms docs working in order to obtain the doc ids to delete.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

Resolving deleted terms -> doc IDs doesn't require a sorted terms dict right? Ie a simple hash lookup suffices?

[asfimport]

Jason Rutherglen (migrated from JIRA)

Resolving deleted terms -> doc IDs doesn't require a
sorted terms dict right? Ie a simple hash lookup suffices?

True, however I figured it'd be best to try our own dog food, or
APIs. I think the main issue right now is the concurrency of the
*BlockPools from #3649. Then we should be able to
implement deleting, which doesn't require skip lists. I guess if
we really wanted to, we could simply buffer terms and only apply
them in getReader. getReader would block any writes that could
be altering the *BlockPools. Maybe this is a good first step? Is there
any reason we need to apply deletes in the actual updateDoc and
deleteDoc methods?

[asfimport]

Jason Rutherglen (migrated from JIRA)

I'm implementing a basic doc id iterator per DWPT which will allow us to implement delete by term, and the deleted docs sequence ids. This is for merging of segments? However we're using readers to do the merging so this really won't be useful?

[asfimport]

Jason Rutherglen (migrated from JIRA)

For the deleted docs sequence id array, perhaps I'm a little bit
confused, but how will we signify in the sequence id array if a
document is deleted? I believe we need a secondary sequence id
array for deleted docs that is init'd to -1. When a document is
deleted, the sequence id is set for that doc in the
del-docs-seq-arr. When the deleted docs Bits is being accessed,
for a given doc, we'll compare the IRs seq-id-up-to with the
del-docs-seq-id, and if the IR seq-id is greater than or equal
to, the Bits.get method will return true, meaning the document
is deleted.

I am forgetting how concurrency will work in this case, ie,
insuring multi-threaded visibility due to the JMM. Actually,
because we're pausing the writes/deletes when get reader is
called on the DWPT, JMM concurrency should be OK.

[asfimport]

Jason Rutherglen (migrated from JIRA)

If we implement deletes via sequence id across all segments, then the .del file should probably remain the same (a set of bits)? Also, when we load up the BV on IW start, then I guess we'll need to init the array appropriately.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

We could also [someday] move deletes to a stacked model... where we only write "deltas" (newly deleted docs in the current session) against the segment, and on open we coalesce these. Merging would also periodically coalesce and write a new full vector...

[asfimport]

Jason Rutherglen (migrated from JIRA)

In regards to the deltas, when they're in RAM (ie, for norm and DF updates), I'm guessing we'd need to place the updates into a hash map (that hopefully uses primitives instead of objects to save RAM)? We could instantiate a new array when the map reached a certain size?

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

In regards to the deltas, when they're in RAM (ie, for norm and DF updates), I'm guessing we'd need to place the updates into a hash map (that hopefully uses primitives instead of objects to save RAM)? We could instantiate a new array when the map reached a certain size?

Actually I think all lookups for a del doc should still be against the BV.

The "generations"/replay log would only be used to properly do the recycling of an old BV (ie, so you know which parts of the log to "replay" against this BV).

And, for saving the new deletes in the directory (though this is not really important for the RT case).

[asfimport]

An Hong Yun (migrated from JIRA)

Does anybody know where to checkout the realtime branch? I am very interested in it! Thanks!

[asfimport]

Simon Willnauer (@s1monw) (migrated from JIRA)

Does anybody know where to checkout the realtime branch? I am very interested in it! Thanks!

there is no realtime branch open right now. We had to delete it since we re-integrated it for DocumentsWriterPerThread. (SVN requires that once you have re-integrated) However, there is no development happening along those lines right now and we didn't decide if we move forward since for general purpose the NRT features we have is reasonably fast. Anyway, I think there is still a need for this if we can provide it as a non-default option?