Lucene - Core
  1. Lucene - Core
  2. LUCENE-2357

Reduce transient RAM usage while merging by using packed ints array for docID re-mapping

    Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 4.0-ALPHA, 5.0
    • Component/s: core/index
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      We allocate this int[] to remap docIDs due to compaction of deleted ones.

      This uses alot of RAM for large segment merges, and can fail to allocate due to fragmentation on 32 bit JREs.

      Now that we have packed ints, a simple fix would be to use a packed int array... and maybe instead of storing abs docID in the mapping, we could store the number of del docs seen so far (so the remap would do a lookup then a subtract). This may add some CPU cost to merging but should bring down transient RAM usage quite a bit.

      1. LUCENE-2357.patch
        15 kB
        Adrien Grand
      2. LUCENE-2357.patch
        16 kB
        Michael McCandless
      3. LUCENE-2357.patch
        16 kB
        Adrien Grand
      4. LUCENE-2357.patch
        17 kB
        Michael McCandless
      5. LUCENE-2357.patch
        17 kB
        Adrien Grand

        Issue Links

          Activity

          Uwe Schindler made changes -
          Status Resolved [ 5 ] Closed [ 6 ]
          Adrien Grand made changes -
          Link This issue relates to LUCENE-4792 [ LUCENE-4792 ]
          Adrien Grand made changes -
          Status Reopened [ 4 ] Resolved [ 5 ]
          Assignee Michael McCandless [ mikemccand ] Adrien Grand [ jpountz ]
          Resolution Fixed [ 1 ]
          Hide
          Adrien Grand added a comment -

          Committed (r1349234 on trunk and r1349241 on branch 4.x).

          Show
          Adrien Grand added a comment - Committed (r1349234 on trunk and r1349241 on branch 4.x).
          Adrien Grand committed 1349241 (2 files)
          Reviews: none

          LUCENE-2357: Changing acceptableOverheadRatio from FAST to COMPACT (merged from r1349234).

          Adrien Grand committed 1349234 (2 files)
          Reviews: none

          LUCENE-2357: Changing acceptableOverheadRatio from FAST to COMPACT.

          Hide
          Simon Willnauer added a comment -

          s/(Adrien Grand via Mike McCandless)/(Adrien Grand)

          otherwise +1

          Show
          Simon Willnauer added a comment - s/(Adrien Grand via Mike McCandless)/(Adrien Grand) otherwise +1
          Hide
          Adrien Grand added a comment -

          I am going to commit this change next week unless someone objects.

          Show
          Adrien Grand added a comment - I am going to commit this change next week unless someone objects.
          Michael McCandless made changes -
          Fix Version/s 5.0 [ 12321663 ]
          Michael McCandless made changes -
          Resolution Fixed [ 1 ]
          Status Resolved [ 5 ] Reopened [ 4 ]
          Hide
          Michael McCandless added a comment -

          Reopen so we remember to change to COMPACT...

          Show
          Michael McCandless added a comment - Reopen so we remember to change to COMPACT...
          Hide
          Michael McCandless added a comment -

          I think changing to COMPACT is good....

          Show
          Michael McCandless added a comment - I think changing to COMPACT is good....
          Hide
          Adrien Grand added a comment -

          I ran a quick test that indexes a few millions of documents with only one field (index, not stored, not analyzed, no terms vectors, ...) with different ratios of deleted documents, ram buffer sizes (between 1 and 50 MB) and merge factors (between 3 and 20). The global speedup with PackedInts.FAST was between 0.2% and 1.7% compared to PackedInts.COMPACT (although I ran this test on a low-end computer, other people might have slightly better results with the FAST version on a better machine). This is probably not worth the potential memory overhead. Would someone disagree to replace FAST with COMPACT for the docmaps instantiation?

          Show
          Adrien Grand added a comment - I ran a quick test that indexes a few millions of documents with only one field (index, not stored, not analyzed, no terms vectors, ...) with different ratios of deleted documents, ram buffer sizes (between 1 and 50 MB) and merge factors (between 3 and 20). The global speedup with PackedInts.FAST was between 0.2% and 1.7% compared to PackedInts.COMPACT (although I ran this test on a low-end computer, other people might have slightly better results with the FAST version on a better machine). This is probably not worth the potential memory overhead. Would someone disagree to replace FAST with COMPACT for the docmaps instantiation?
          Hide
          Adrien Grand added a comment -

          While working on LUCENE-4062, I had in mind that FAST (50%) would be ok for transient data structures while COMPACT (0%) and DEFAULT (20%) would be better for big and long-living structures depending on the performance requirements. However, it is true that the DocMap might not be the bottleneck for merging (especially since this operation involves disk accesses). I can try to run some benchmarks next week to find out whether COMPACT (or maybe DEFAULT) could be a better tradeoff.

          Show
          Adrien Grand added a comment - While working on LUCENE-4062 , I had in mind that FAST (50%) would be ok for transient data structures while COMPACT (0%) and DEFAULT (20%) would be better for big and long-living structures depending on the performance requirements. However, it is true that the DocMap might not be the bottleneck for merging (especially since this operation involves disk accesses). I can try to run some benchmarks next week to find out whether COMPACT (or maybe DEFAULT ) could be a better tradeoff.
          Hide
          Robert Muir added a comment -

          Do we have any high-level idea of what the performance cost of COMPACT vs FAST is for merging?
          (e.g. typical case of Lucene40 codec). Is COMPACT maybe a good tradeoff?

          Show
          Robert Muir added a comment - Do we have any high-level idea of what the performance cost of COMPACT vs FAST is for merging? (e.g. typical case of Lucene40 codec). Is COMPACT maybe a good tradeoff?
          Hide
          Adrien Grand added a comment -

          This is the theoretical improvement. However, in order not to slow merging down too much, I instantiate the PackedInts.Mutable that holds the doc map with acceptableOverheadRatio=PackedInts.FAST=50% (see LUCENE-4062), so the actual improvement might be a little worse than the theoretical improvement. If you are more interested in memory usage than in merge speed, you could still reach the theoretical improvement by replacing PackedInts.FAST with PackedInts.COMPACT in MergeState.DocMap.build.

          Show
          Adrien Grand added a comment - This is the theoretical improvement. However, in order not to slow merging down too much, I instantiate the PackedInts.Mutable that holds the doc map with acceptableOverheadRatio=PackedInts.FAST=50% (see LUCENE-4062 ), so the actual improvement might be a little worse than the theoretical improvement. If you are more interested in memory usage than in merge speed, you could still reach the theoretical improvement by replacing PackedInts.FAST with PackedInts.COMPACT in MergeState.DocMap.build .
          Hide
          Adrien Grand added a comment -

          Hi Otis,

          Before this change, each doc map used ~ maxDoc * 32 bits while they now use ~ maxDoc * lg(min(numDocs, numDeletedDocs)) (where lg is the ceil of log in base 2) bits. So even in the worst case (numDocs = numDeleted = maxDoc / 2), the improvement is ((31 - lg(maxDoc))/32. On a segment with maxDoc=10000000, this is a 22% improvement. But the improvement is much better when the number of deleted documents is close to 0 or to maxDoc. For example, if your segment has maxDoc=10000000 and numDeletedDocs=100000, the improvement (32 - lg(min(numDocs, numDeletedDocs))/32) is close to 50%. If numDeletedDocs=100, the improvement is close to 80%.

          Show
          Adrien Grand added a comment - Hi Otis, Before this change, each doc map used ~ maxDoc * 32 bits while they now use ~ maxDoc * lg(min(numDocs, numDeletedDocs)) (where lg is the ceil of log in base 2) bits. So even in the worst case (numDocs = numDeleted = maxDoc / 2), the improvement is ((31 - lg(maxDoc))/32 . On a segment with maxDoc=10000000, this is a 22% improvement. But the improvement is much better when the number of deleted documents is close to 0 or to maxDoc. For example, if your segment has maxDoc=10000000 and numDeletedDocs=100000, the improvement ( 32 - lg(min(numDocs, numDeletedDocs))/32 ) is close to 50%. If numDeletedDocs=100, the improvement is close to 80%.
          Hide
          Otis Gospodnetic added a comment -

          Woho, I love seeing old issues getting love like this!
          Has anyone measured (or at least eyeballed) how much RAM this saves?

          Show
          Otis Gospodnetic added a comment - Woho, I love seeing old issues getting love like this! Has anyone measured (or at least eyeballed) how much RAM this saves?
          Michael McCandless made changes -
          Status Open [ 1 ] Resolved [ 5 ]
          Fix Version/s 4.0 [ 12314025 ]
          Fix Version/s 4.1 [ 12321140 ]
          Resolution Fixed [ 1 ]
          Hide
          Michael McCandless added a comment -

          Thanks Adrien!

          Show
          Michael McCandless added a comment - Thanks Adrien!
          Hide
          Michael McCandless added a comment -

          Thanks Adrien, new patch looks great... I'll commit shortly.

          Show
          Michael McCandless added a comment - Thanks Adrien, new patch looks great... I'll commit shortly.
          Adrien Grand made changes -
          Attachment LUCENE-2357.patch [ 12530057 ]
          Hide
          Adrien Grand added a comment -

          New Patch with two minor modifications:

          • I replaced PackedInts.bitsRequired(numDocs) with PackedInts.bitsRequired(Math.max(0, numDocs - 1)) in buildDirectDocMap since the highest doc id mapping is numDocs - 1,
          • Since DocMap.get now relies on liveDocs to return the doc mapping, I added an assert in build to ensure that liveDocs is never null when numDeletedDocs > 0.
          Show
          Adrien Grand added a comment - New Patch with two minor modifications: I replaced PackedInts.bitsRequired(numDocs) with PackedInts.bitsRequired(Math.max(0, numDocs - 1)) in buildDirectDocMap since the highest doc id mapping is numDocs - 1 , Since DocMap.get now relies on liveDocs to return the doc mapping, I added an assert in build to ensure that liveDocs is never null when numDeletedDocs > 0.
          Michael McCandless made changes -
          Attachment LUCENE-2357.patch [ 12530029 ]
          Hide
          Michael McCandless added a comment -

          New patch. Same as Mike's but with the code of DocMap.equals moved to the test case.

          Thanks Adrien!

          I sync'd the patch to trunk, and also tweaked the DocMaps to hold onto the Bits liveDocs and first use that to check if a doc is still live, and secondarily checked the packed ints arrays for the remapping. This enables us to simplify the lookup (eg, in the inverted case we need only one lookup).

          Show
          Michael McCandless added a comment - New patch. Same as Mike's but with the code of DocMap.equals moved to the test case. Thanks Adrien! I sync'd the patch to trunk, and also tweaked the DocMaps to hold onto the Bits liveDocs and first use that to check if a doc is still live, and secondarily checked the packed ints arrays for the remapping. This enables us to simplify the lookup (eg, in the inverted case we need only one lookup).
          Hide
          Michael McCandless added a comment -

          I just created LUCENE-4080 for the SegmentReader.numDeletedDocs() issue.

          Thanks Adrien.

          Show
          Michael McCandless added a comment - I just created LUCENE-4080 for the SegmentReader.numDeletedDocs() issue. Thanks Adrien.
          Adrien Grand made changes -
          Attachment LUCENE-2357.patch [ 12529991 ]
          Hide
          Adrien Grand added a comment -

          New patch. Same as Mike's but with the code of DocMap.equals moved to the test case.

          Show
          Adrien Grand added a comment - New patch. Same as Mike's but with the code of DocMap.equals moved to the test case.
          Hide
          Adrien Grand added a comment -

          I just created LUCENE-4080 for the SegmentReader.numDeletedDocs() issue.

          Show
          Adrien Grand added a comment - I just created LUCENE-4080 for the SegmentReader.numDeletedDocs() issue.
          Hide
          Michael McCandless added a comment -

          Is "cleaner hairier" code a new oxymoron?

          I guess so!!

          What I meant was ... it would be best if the SegmentReader's numDeletedDocs were always correct, but, fixing that in IndexWriter is somewhat tricky. Ie, the fix could be hairy but the end result ("SegmentReader.numDeletedDocs can always be trusted") would be cleaner...

          Show
          Michael McCandless added a comment - Is "cleaner hairier" code a new oxymoron? I guess so!! What I meant was ... it would be best if the SegmentReader's numDeletedDocs were always correct, but, fixing that in IndexWriter is somewhat tricky. Ie, the fix could be hairy but the end result ("SegmentReader.numDeletedDocs can always be trusted") would be cleaner...
          Hide
          Dawid Weiss added a comment -

          It would be cleaner (but I think hairier)

          Is "cleaner hairier" code a new oxymoron?

          Show
          Dawid Weiss added a comment - It would be cleaner (but I think hairier) Is "cleaner hairier" code a new oxymoron?
          Michael McCandless made changes -
          Attachment LUCENE-2357.patch [ 12529978 ]
          Hide
          Michael McCandless added a comment -

          New patch, just passing down the correct delCount so we don't have to re-count.

          It would be cleaner (but I think hairier) to create a new SR for merging that holds the correct delCount, but let's do that under the separate issue.

          Show
          Michael McCandless added a comment - New patch, just passing down the correct delCount so we don't have to re-count. It would be cleaner (but I think hairier) to create a new SR for merging that holds the correct delCount, but let's do that under the separate issue.
          Hide
          Michael McCandless added a comment -

          I implemented equals only for testing purposes (see TestSegmentMerger.java) and then hashCode for consistency. I can move the equals code to the test case if you prefer.

          Ahh, OK. Yeah I think move it to the test case? Thanks.

          There used to be an assert in SegmentMerger but it was removed in r1148938

          Ahh you're right! Hmm, but, we actually know the accurate delCount higher up; let me tweak the patch a bit to pass this down, so we don't have to re-count it separately.

          so I assumed the numDeletedDocs() was unreliable and the del count should be computed from liveDocs. I am not familiar enough with the merge process to know whether some invariants are broken or not. Should I open a bug?

          As far as I know, it's only unreliable in this context (SegmentReader passed to SegmentMerger for merging); this is because we allow newly marked deleted docs to happen concurrently up until the moment we need to pass the SR instance to the merger (search for "// Must sync to ensure BufferedDeletesStream" in IndexWriter.java) ... but it would be nice to fix that, so I think open a new issue (it won't block this one)? We should be able to make a new SR instance, sharing the same core as the current one but using the correct delCount...

          Show
          Michael McCandless added a comment - I implemented equals only for testing purposes (see TestSegmentMerger.java) and then hashCode for consistency. I can move the equals code to the test case if you prefer. Ahh, OK. Yeah I think move it to the test case? Thanks. There used to be an assert in SegmentMerger but it was removed in r1148938 Ahh you're right! Hmm, but, we actually know the accurate delCount higher up; let me tweak the patch a bit to pass this down, so we don't have to re-count it separately. so I assumed the numDeletedDocs() was unreliable and the del count should be computed from liveDocs. I am not familiar enough with the merge process to know whether some invariants are broken or not. Should I open a bug? As far as I know, it's only unreliable in this context (SegmentReader passed to SegmentMerger for merging); this is because we allow newly marked deleted docs to happen concurrently up until the moment we need to pass the SR instance to the merger (search for "// Must sync to ensure BufferedDeletesStream" in IndexWriter.java) ... but it would be nice to fix that, so I think open a new issue (it won't block this one)? We should be able to make a new SR instance, sharing the same core as the current one but using the correct delCount...
          Hide
          Adrien Grand added a comment -

          I implemented equals only for testing purposes (see TestSegmentMerger.java) and then hashCode for consistency. I can move the equals code to the test case if you prefer.

          Regarding numDeletedDocs, I tried to add the following assert

          assert docCount == reader.reader.numDocs() : "docCount=" + docCount + ", numDocs=" + reader.reader.numDocs();
          

          to line 321 of SegmentMerger (before applying the patch) and it fails across a large number of tests (try to run TestAddIndexes a few times for example, and at least one of the testWithpendingDeletes* should fail). There used to be an assert in SegmentMerger but it was removed in r1148938 (http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/index/SegmentMerger.java?r1=1147671&r2=1148938&pathrev=1148938&diff_format=h) so I assumed the numDeletedDocs() was unreliable and the del count should be computed from liveDocs. I am not familiar enough with the merge process to know whether some invariants are broken or not. Should I open a bug?

          Show
          Adrien Grand added a comment - I implemented equals only for testing purposes (see TestSegmentMerger.java) and then hashCode for consistency. I can move the equals code to the test case if you prefer. Regarding numDeletedDocs, I tried to add the following assert assert docCount == reader.reader.numDocs() : "docCount=" + docCount + ", numDocs=" + reader.reader.numDocs(); to line 321 of SegmentMerger (before applying the patch) and it fails across a large number of tests (try to run TestAddIndexes a few times for example, and at least one of the testWithpendingDeletes* should fail). There used to be an assert in SegmentMerger but it was removed in r1148938 ( http://svn.apache.org/viewvc/lucene/dev/trunk/lucene/src/java/org/apache/lucene/index/SegmentMerger.java?r1=1147671&r2=1148938&pathrev=1148938&diff_format=h ) so I assumed the numDeletedDocs() was unreliable and the del count should be computed from liveDocs . I am not familiar enough with the merge process to know whether some invariants are broken or not. Should I open a bug?
          Michael McCandless made changes -
          Labels gsoc2012 lucene-gsoc-12
          Assignee Michael McCandless [ mikemccand ]
          Hide
          Michael McCandless added a comment -

          Patch looks great!

          Do we really need to impl DocMap.equals/hashCode? Costly equals methods scare me... can we simply throw UOE from these methods? Nobody should be calling them, I think.

          Instead of looping through numDocs summing up the del count, I think you should be able to set numDeletes = reader.numDeletedDocs()? And maybe just consolidate those two build methods...

          Show
          Michael McCandless added a comment - Patch looks great! Do we really need to impl DocMap.equals/hashCode? Costly equals methods scare me... can we simply throw UOE from these methods? Nobody should be calling them, I think. Instead of looping through numDocs summing up the del count, I think you should be able to set numDeletes = reader.numDeletedDocs()? And maybe just consolidate those two build methods...
          Adrien Grand made changes -
          Attachment LUCENE-2357.patch [ 12529913 ]
          Hide
          Adrien Grand added a comment -

          This patch should fix this issue. I replaced the int[] by an abstract MergeState.DocMap class which has two main implementations: a direct one which maps doc ids to their new value directly, and another one which counts the number of documents which have been deleted so far to know how much to decrement doc ids.

          Show
          Adrien Grand added a comment - This patch should fix this issue. I replaced the int[] by an abstract MergeState.DocMap class which has two main implementations: a direct one which maps doc ids to their new value directly, and another one which counts the number of documents which have been deleted so far to know how much to decrement doc ids.
          Robert Muir made changes -
          Fix Version/s 4.1 [ 12321140 ]
          Fix Version/s 4.0 [ 12314025 ]
          Hide
          Michael McCandless added a comment -

          Hi Iulius,

          The basic idea is to replace the fixed int[] that we now have (in oal.index.MergeState's docMaps array) with a PackedInts store (see oal.util.packed.PackedInts.getMutable). This should be fairly simple, since a PackedInts store is concetually just like an int[].

          I think that (a rote swap) would be phase one.

          After that, we can save more RAM by storing either the new docID (what we do today), or, inverting that and storing instead the number of del docs seen so far, depending on which requires fewer bits. EG if we are merging 1M docs but only 100K are deleted it's cheaper to store the number of deletes...

          Show
          Michael McCandless added a comment - Hi Iulius, The basic idea is to replace the fixed int[] that we now have (in oal.index.MergeState's docMaps array) with a PackedInts store (see oal.util.packed.PackedInts.getMutable). This should be fairly simple, since a PackedInts store is concetually just like an int[]. I think that (a rote swap) would be phase one. After that, we can save more RAM by storing either the new docID (what we do today), or, inverting that and storing instead the number of del docs seen so far, depending on which requires fewer bits. EG if we are merging 1M docs but only 100K are deleted it's cheaper to store the number of deletes...
          Hide
          Iulius Curt added a comment -

          Could I have some of your time for a few more details, to help a new commer be able to dig into this, please?

          Show
          Iulius Curt added a comment - Could I have some of your time for a few more details, to help a new commer be able to dig into this, please?
          Michael McCandless made changes -
          Labels gsoc2012 lucene-gsoc-12
          Mark Thomas made changes -
          Workflow Default workflow, editable Closed status [ 12563588 ] jira [ 12585173 ]
          Mark Thomas made changes -
          Field Original Value New Value
          Workflow jira [ 12503243 ] Default workflow, editable Closed status [ 12563588 ]
          Hide
          Michael McCandless added a comment -

          I won't have any time to take this any time soon So if anyone has the itch, jump!

          Show
          Michael McCandless added a comment - I won't have any time to take this any time soon So if anyone has the itch, jump!
          Michael McCandless created issue -

            People

            • Assignee:
              Adrien Grand
              Reporter:
              Michael McCandless
            • Votes:
              2 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development