Details

    • Type: Bug Bug
    • Status: Resolved
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: Realtime Branch
    • Fix Version/s: Realtime Branch
    • Component/s: core/index
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      With separate DocumentsWriterPerThreads (DWPT) it can currently happen that the delete part of an updateDocument() is flushed and committed separately from the corresponding new document.

      We need to make sure that updateDocument() is always an atomic operation from a IW.commit() and IW.getReader() perspective. See LUCENE-2324 for more details.

      1. LUCENE-2956.patch
        76 kB
        Simon Willnauer
      2. LUCENE-2956.patch
        68 kB
        Simon Willnauer

        Issue Links

          Activity

          Hide
          Michael Busch added a comment -

          An idea from Mike how to fix this problem:

          To avoid the full-stop, I think during the flush we can have two global delete pools. We carefully sweep all DWPTs and flush each, in succession. Any DWPT not yet flushed is free to continue indexing as normal, putting deletes into the first global pool, flushing as normal. But, a DWPT that has been flushed by the "sweeper" must instead put deletes for an updateDocument carefully into the 2nd pool, and not buffer the delete into DWPTs not yet flushed.

          Show
          Michael Busch added a comment - An idea from Mike how to fix this problem: To avoid the full-stop, I think during the flush we can have two global delete pools. We carefully sweep all DWPTs and flush each, in succession. Any DWPT not yet flushed is free to continue indexing as normal, putting deletes into the first global pool, flushing as normal. But, a DWPT that has been flushed by the "sweeper" must instead put deletes for an updateDocument carefully into the 2nd pool, and not buffer the delete into DWPTs not yet flushed.
          Hide
          Jason Rutherglen added a comment -

          What is the status of this one? If no one's working on it, I can take a stab.

          Show
          Jason Rutherglen added a comment - What is the status of this one? If no one's working on it, I can take a stab.
          Hide
          Simon Willnauer added a comment -

          Jason I am working on this. First patch is not too far away.

          Show
          Simon Willnauer added a comment - Jason I am working on this. First patch is not too far away.
          Hide
          Simon Willnauer added a comment -

          FYI I have a working patch for this. it needs some cleanup so I will hopefully upload beginning next week....

          Show
          Simon Willnauer added a comment - FYI I have a working patch for this. it needs some cleanup so I will hopefully upload beginning next week....
          Hide
          Simon Willnauer added a comment -

          Attaching an initial patch. This patch uses a entirely non-blocking approach to deletes based on a specialized linked list that only uses CAS operations.

          Since this issue is quiet complex I tried to add as many useful comments as possible inline in the patch to make reviewing easier. So for details check out the patch.

          All test on realtime branch pass with this patch. (once in a while I have a failure in the healthiness test but the assumptions in that test seem to be too strict and I need to fix that separately)

          Reviews are very very much appreciated!

          Show
          Simon Willnauer added a comment - Attaching an initial patch. This patch uses a entirely non-blocking approach to deletes based on a specialized linked list that only uses CAS operations. Since this issue is quiet complex I tried to add as many useful comments as possible inline in the patch to make reviewing easier. So for details check out the patch. All test on realtime branch pass with this patch. (once in a while I have a failure in the healthiness test but the assumptions in that test seem to be too strict and I need to fix that separately) Reviews are very very much appreciated!
          Hide
          Jason Rutherglen added a comment -

          I think I have an idea, however can you explain the ticketQueue?

          Show
          Jason Rutherglen added a comment - I think I have an idea, however can you explain the ticketQueue?
          Hide
          Simon Willnauer added a comment -

          I think I have an idea, however can you explain the ticketQueue?

          Sure, since with DWPT the flush process is concurrent and several DWPT could flush at the same time we must maintain the order of the flushes before we can apply the flushed segment and the frozen global
          deletes it is buffering. The reason for this is that the global deletes mark a certain point in time where we took a DWPT out of rotation and freeze the global deletes.

          Example: A DWPT 'A' starts flushing and freezes the global deletes, then DWPT 'B' starts flushing and freezes all deletes occurred since 'A' has started. if 'B' finishes before 'A' we need to wait until 'A' is done otherwise the deletes frozen by 'B' are not applied to 'A' and we might miss to deletes documents in 'A'.

          The Ticket queue simply ensures that we push the frozen deletes and the new created segment in the same order as the corresponding DWPT have started flushing. If a DWPT finishes flushing we update its Ticket and then check the head of the queue if we can remove / publish the ticket. if so we continue publishing until the head of the queue can not be published yet or the queue is empty.

          Show
          Simon Willnauer added a comment - I think I have an idea, however can you explain the ticketQueue? Sure, since with DWPT the flush process is concurrent and several DWPT could flush at the same time we must maintain the order of the flushes before we can apply the flushed segment and the frozen global deletes it is buffering. The reason for this is that the global deletes mark a certain point in time where we took a DWPT out of rotation and freeze the global deletes. Example: A DWPT 'A' starts flushing and freezes the global deletes, then DWPT 'B' starts flushing and freezes all deletes occurred since 'A' has started. if 'B' finishes before 'A' we need to wait until 'A' is done otherwise the deletes frozen by 'B' are not applied to 'A' and we might miss to deletes documents in 'A'. The Ticket queue simply ensures that we push the frozen deletes and the new created segment in the same order as the corresponding DWPT have started flushing. If a DWPT finishes flushing we update its Ticket and then check the head of the queue if we can remove / publish the ticket. if so we continue publishing until the head of the queue can not be published yet or the queue is empty.
          Hide
          Michael McCandless added a comment -

          Patch looks great Simon!

          Very impressive how this patch makes delete handling fully lockless!
          The inline comments are very helpful...

          Some small stuff:

          • I think we do need delete-by-Term[] (and Query[]) to be atomic?
            (IW has these methods, and I think they are atomic now?) This is
            from the TODOs in DocumentsWriterDeleteQueue...
          • Does TestRollingUpdates really need to use LogMP?
          • raceing -> racing; {@link BuffereDeletes}

            ->

            {@link BufferedDeletes}

            ; DocumensWriter -> DocumentsWriter

          Show
          Michael McCandless added a comment - Patch looks great Simon! Very impressive how this patch makes delete handling fully lockless! The inline comments are very helpful... Some small stuff: I think we do need delete-by-Term[] (and Query[]) to be atomic? (IW has these methods, and I think they are atomic now?) This is from the TODOs in DocumentsWriterDeleteQueue... Does TestRollingUpdates really need to use LogMP? raceing -> racing; {@link BuffereDeletes} -> {@link BufferedDeletes} ; DocumensWriter -> DocumentsWriter
          Hide
          Michael Busch added a comment -

          Cool patch!
          Though it worries me a little how complex the whole delete/update logic is becoming (not only the part this patch adds).

          Originally we decided to not go with sequenceIDs partly because we thought the implementation might be too complex, but I think it'd be simpler than the current approach that uses bits.

          The sequenceIDs approach we had in the beginning was also completely lockless in a very very simple way.

          Anyway, I have yet to take a closer look here. Just something that might be worth discussing.

          Show
          Michael Busch added a comment - Cool patch! Though it worries me a little how complex the whole delete/update logic is becoming (not only the part this patch adds). Originally we decided to not go with sequenceIDs partly because we thought the implementation might be too complex, but I think it'd be simpler than the current approach that uses bits. The sequenceIDs approach we had in the beginning was also completely lockless in a very very simple way. Anyway, I have yet to take a closer look here. Just something that might be worth discussing.
          Hide
          Simon Willnauer added a comment -

          Though it worries me a little how complex the whole delete/update logic is becoming (not only the part this patch adds).

          I can not more agree. Its been very complex making all the tests pass and figuring out all the little nifty cornercases here. A different, somewhat simpler approach would be great. Eventually for Searchable Ram Buffers we might need to switch to seq. ids anyway but I think for landing DWPT on trunk we can go with the current approach.
          I will update the latest patch and commit it to the branch and merge with trunk again. Once that is done I will setup a hudson build for RT so we give it a little exercise while we prepare moving to trunk.

          Show
          Simon Willnauer added a comment - Though it worries me a little how complex the whole delete/update logic is becoming (not only the part this patch adds). I can not more agree. Its been very complex making all the tests pass and figuring out all the little nifty cornercases here. A different, somewhat simpler approach would be great. Eventually for Searchable Ram Buffers we might need to switch to seq. ids anyway but I think for landing DWPT on trunk we can go with the current approach. I will update the latest patch and commit it to the branch and merge with trunk again. Once that is done I will setup a hudson build for RT so we give it a little exercise while we prepare moving to trunk.
          Hide
          Simon Willnauer added a comment -

          here is an updated patch fixing some spellings, adds atomic updates for Term[] and Query[] and removes the LogMergePolicy restriction from TestRollingUpdates

          Show
          Simon Willnauer added a comment - here is an updated patch fixing some spellings, adds atomic updates for Term[] and Query[] and removes the LogMergePolicy restriction from TestRollingUpdates
          Hide
          Simon Willnauer added a comment -

          I committed that patch and merged with trunk

          Show
          Simon Willnauer added a comment - I committed that patch and merged with trunk
          Hide
          Jason Rutherglen added a comment -

          Simon, nice work. I agree with Michael B. that the deletes are super complex. We had discussed using sequence ids for all segments (not just the RT enabled DWPT ones) however we never worked out a specification, eg, for things like wrap around if a primitive short[] was used.

          Shall we start again on LUCENE-2312? I think we still need/want to use sequence ids there. The RT DWPTs shouldn't have so many documents that using a long[] for the sequence ids is too RAM consuming?

          Show
          Jason Rutherglen added a comment - Simon, nice work. I agree with Michael B. that the deletes are super complex. We had discussed using sequence ids for all segments (not just the RT enabled DWPT ones) however we never worked out a specification, eg, for things like wrap around if a primitive short[] was used. Shall we start again on LUCENE-2312 ? I think we still need/want to use sequence ids there. The RT DWPTs shouldn't have so many documents that using a long[] for the sequence ids is too RAM consuming?
          Hide
          Simon Willnauer added a comment -

          Shall we start again on LUCENE-2312? I think we still need/want to use sequence ids there. The RT DWPTs shouldn't have so many documents that using a long[] for the sequence ids is too RAM consuming?

          Jason I think nothing prevents you from start working on this again.... Yet, I think we should freeze the branch now and only allow merging, bug fixes, tests and documentation fixes until we land on trunk. Once we are there we can freely push stuff in the branch again and make it work with seq. ids.

          thoughts?

          Show
          Simon Willnauer added a comment - Shall we start again on LUCENE-2312 ? I think we still need/want to use sequence ids there. The RT DWPTs shouldn't have so many documents that using a long[] for the sequence ids is too RAM consuming? Jason I think nothing prevents you from start working on this again.... Yet, I think we should freeze the branch now and only allow merging, bug fixes, tests and documentation fixes until we land on trunk. Once we are there we can freely push stuff in the branch again and make it work with seq. ids. thoughts?
          Hide
          Simon Willnauer added a comment -

          committed to branch

          Show
          Simon Willnauer added a comment - committed to branch
          Hide
          Jason Rutherglen added a comment -

          Jason I think nothing prevents you from start working on this again.... Yet, I think we should freeze the branch now and only allow merging, bug fixes, tests and documentation fixes until we land on trunk. Once we are there we can freely push stuff in the branch again and make it work with seq. ids.

          OK, great. I remember now that our main concern was the memory usage of using a short[] (for the seq ids) if the total number of documents is numerous (eg, 10s of millions). Also at some point we'd have double the memory usage when we roll over to the next set, until the previous readers are closed.

          I think we should freeze the branch now and only allow merging, bug fixes, tests and documentation fixes until we land on trunk

          Maybe once LUCENE-2312 sequence ids work for deletes, we can look at creating a separate branch that implements seq id deletes for all segments, and compare with the BV approach. Eg, performance, memory usage, and simplicity.

          Show
          Jason Rutherglen added a comment - Jason I think nothing prevents you from start working on this again.... Yet, I think we should freeze the branch now and only allow merging, bug fixes, tests and documentation fixes until we land on trunk. Once we are there we can freely push stuff in the branch again and make it work with seq. ids. OK, great. I remember now that our main concern was the memory usage of using a short[] (for the seq ids) if the total number of documents is numerous (eg, 10s of millions). Also at some point we'd have double the memory usage when we roll over to the next set, until the previous readers are closed. I think we should freeze the branch now and only allow merging, bug fixes, tests and documentation fixes until we land on trunk Maybe once LUCENE-2312 sequence ids work for deletes, we can look at creating a separate branch that implements seq id deletes for all segments, and compare with the BV approach. Eg, performance, memory usage, and simplicity.
          Hide
          Simon Willnauer added a comment -

          Maybe once LUCENE-2312 sequence ids work for deletes, we can look at creating a separate branch that implements seq id deletes for all segments, and compare with the BV approach. Eg, performance, memory usage, and simplicity.

          I don't think we need to create a different branch until then DWPT will be no trunk and we can simply compare to trunk, no?

          Show
          Simon Willnauer added a comment - Maybe once LUCENE-2312 sequence ids work for deletes, we can look at creating a separate branch that implements seq id deletes for all segments, and compare with the BV approach. Eg, performance, memory usage, and simplicity. I don't think we need to create a different branch until then DWPT will be no trunk and we can simply compare to trunk, no?

            People

            • Assignee:
              Simon Willnauer
              Reporter:
              Michael Busch
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development