lucene-java-3.4.0/lucene/contrib/misc/src/java/org/apache/lucene/index/BalancedSegmentMergePolicy.java

   1 package org.apache.lucene.index;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20
  21 import java.io.IOException;
  22 import java.util.Collections;
  23 import java.util.Map;
  24
  25 /**
  26  * Merge policy that tries to balance not doing large
  27  * segment merges with not accumulating too many segments in
  28  * the index, to provide for better performance in near
  29  * real-time setting.
  30  *
  31  * <p>This is based on code from zoie, described in more detail
  32  * at http://code.google.com/p/zoie/wiki/ZoieMergePolicy.</p>
  33  */
  34 public class BalancedSegmentMergePolicy extends LogByteSizeMergePolicy {
  35
  36   public static final int DEFAULT_NUM_LARGE_SEGMENTS = 10;
  37
  38   private boolean _partialExpunge = false;
  39   private int _numLargeSegments = DEFAULT_NUM_LARGE_SEGMENTS;
  40   private int _maxSmallSegments = 2 * LogMergePolicy.DEFAULT_MERGE_FACTOR;
  41   private int _maxSegments = _numLargeSegments + _maxSmallSegments;
  42
  43   public BalancedSegmentMergePolicy() {
  44   }
  45
  46   public void setMergePolicyParams(MergePolicyParams params) {
  47     if (params!=null) {
  48       setPartialExpunge(params._doPartialExpunge);
  49       setNumLargeSegments(params._numLargeSegments);
  50       setMaxSmallSegments(params._maxSmallSegments);
  51       setPartialExpunge(params._doPartialExpunge);
  52       setMergeFactor(params._mergeFactor);
  53       setUseCompoundFile(params._useCompoundFile);
  54       setMaxMergeDocs(params._maxMergeDocs);
  55     }
  56   }
  57
  58   @Override
  59   protected long size(SegmentInfo info) throws IOException {
  60     long byteSize = info.sizeInBytes(true);
  61     float delRatio = (info.docCount <= 0 ? 0.0f : ((float)info.getDelCount() / (float)info.docCount));
  62     return (info.docCount <= 0 ?  byteSize : (long)((1.0f - delRatio) * byteSize));
  63   }
  64
  65   public void setPartialExpunge(boolean doPartialExpunge) {
  66     _partialExpunge = doPartialExpunge;
  67   }
  68
  69   public boolean getPartialExpunge() {
  70     return _partialExpunge;
  71   }
  72
  73   public void setNumLargeSegments(int numLargeSegments) {
  74     if (numLargeSegments < 2) {
  75       throw new IllegalArgumentException("numLargeSegments cannot be less than 2");
  76     }
  77
  78     _numLargeSegments = numLargeSegments;
  79     _maxSegments = _numLargeSegments + 2 * getMergeFactor();
  80   }
  81
  82   public int getNumLargeSegments() {
  83     return _numLargeSegments;
  84   }
  85
  86   public void setMaxSmallSegments(int maxSmallSegments) {
  87     if (maxSmallSegments < getMergeFactor()) {
  88       throw new IllegalArgumentException("maxSmallSegments cannot be less than mergeFactor");
  89     }
  90     _maxSmallSegments = maxSmallSegments;
  91     _maxSegments = _numLargeSegments + _maxSmallSegments;
  92   }
  93
  94   public int getMaxSmallSegments() {
  95     return _maxSmallSegments;
  96   }
  97
  98   @Override
  99   public void setMergeFactor(int mergeFactor) {
 100     super.setMergeFactor(mergeFactor);
 101     if (_maxSmallSegments < getMergeFactor()) {
 102       _maxSmallSegments = getMergeFactor();
 103       _maxSegments = _numLargeSegments + _maxSmallSegments;
 104     }
 105   }
 106
 107   @Override
 108   public MergeSpecification findMergesForOptimize(SegmentInfos infos, int maxNumSegments, Map<SegmentInfo,Boolean> segmentsToOptimize) throws IOException {
 109
 110     assert maxNumSegments > 0;
 111
 112     MergeSpecification spec = null;
 113
 114     if (!isOptimized(infos, maxNumSegments, segmentsToOptimize)) {
 115
 116       // Find the newest (rightmost) segment that needs to
 117       // be optimized (other segments may have been flushed
 118       // since optimize started):
 119       int last = infos.size();
 120       while(last > 0) {
 121
 122         final SegmentInfo info = infos.info(--last);
 123         if (segmentsToOptimize.containsKey(info)) {
 124           last++;
 125           break;
 126         }
 127       }
 128
 129       if (last > 0) {
 130
 131         if (maxNumSegments == 1) {
 132
 133           // Since we must optimize down to 1 segment, the
 134           // choice is simple:
 135           if (last > 1 || !isOptimized(infos.info(0))) {
 136
 137             spec = new MergeSpecification();
 138             spec.add(new OneMerge(infos.asList().subList(0, last)));
 139           }
 140         } else if (last > maxNumSegments) {
 141
 142           // find most balanced merges
 143           spec = findBalancedMerges(infos, last, maxNumSegments, _partialExpunge);
 144         }
 145       }
 146     }
 147     return spec;
 148   }
 149
 150   private MergeSpecification findBalancedMerges(SegmentInfos infos, int infoLen, int maxNumSegments, boolean partialExpunge)
 151     throws IOException {
 152     if (infoLen <= maxNumSegments) return null;
 153
 154     MergeSpecification spec = new MergeSpecification();
 155
 156     // use Viterbi algorithm to find the best segmentation.
 157     // we will try to minimize the size variance of resulting segments.
 158
 159     double[][] variance = createVarianceTable(infos, infoLen, maxNumSegments);
 160
 161     final int maxMergeSegments = infoLen - maxNumSegments + 1;
 162     double[] sumVariance = new double[maxMergeSegments];
 163     int[][] backLink = new int[maxNumSegments][maxMergeSegments];
 164
 165     for(int i = (maxMergeSegments - 1); i >= 0; i--) {
 166       sumVariance[i] = variance[0][i];
 167       backLink[0][i] = 0;
 168     }
 169     for(int i = 1; i < maxNumSegments; i++) {
 170       for(int j = (maxMergeSegments - 1); j >= 0; j--) {
 171         double minV = Double.MAX_VALUE;
 172         int minK = 0;
 173         for(int k = j; k >= 0; k--) {
 174           double v = sumVariance[k] + variance[i + k][j - k];
 175           if(v < minV) {
 176             minV = v;
 177             minK = k;
 178           }
 179         }
 180         sumVariance[j] = minV;
 181         backLink[i][j] = minK;
 182       }
 183     }
 184
 185     // now, trace back the back links to find all merges,
 186     // also find a candidate for partial expunge if requested
 187     int mergeEnd = infoLen;
 188     int prev = maxMergeSegments - 1;
 189     int expungeCandidate = -1;
 190     int maxDelCount = 0;
 191     for(int i = maxNumSegments - 1; i >= 0; i--) {
 192       prev = backLink[i][prev];
 193       int mergeStart = i + prev;
 194       if((mergeEnd - mergeStart) > 1) {
 195         spec.add(new OneMerge(infos.asList().subList(mergeStart, mergeEnd)));
 196       } else {
 197         if(partialExpunge) {
 198           SegmentInfo info = infos.info(mergeStart);
 199           int delCount = info.getDelCount();
 200           if(delCount > maxDelCount) {
 201             expungeCandidate = mergeStart;
 202             maxDelCount = delCount;
 203           }
 204         }
 205       }
 206       mergeEnd = mergeStart;
 207     }
 208
 209     if(partialExpunge && maxDelCount > 0) {
 210       // expunge deletes
 211       spec.add(new OneMerge(Collections.singletonList(infos.info(expungeCandidate))));
 212     }
 213
 214     return spec;
 215   }
 216
 217   private double[][] createVarianceTable(SegmentInfos infos, int last, int maxNumSegments) throws IOException {
 218     int maxMergeSegments = last - maxNumSegments + 1;
 219     double[][] variance = new double[last][maxMergeSegments];
 220
 221     // compute the optimal segment size
 222     long optSize = 0;
 223     long[] sizeArr = new long[last];
 224     for(int i = 0; i < sizeArr.length; i++) {
 225       sizeArr[i] = size(infos.info(i));
 226       optSize += sizeArr[i];
 227     }
 228     optSize = (optSize / maxNumSegments);
 229
 230     for(int i = 0; i < last; i++) {
 231       long size = 0;
 232       for(int j = 0; j < maxMergeSegments; j++) {
 233         if((i + j) < last) {
 234           size += sizeArr[i + j];
 235           double residual = ((double)size/(double)optSize) - 1.0d;
 236           variance[i][j] = residual * residual;
 237         } else {
 238           variance[i][j] = Double.NaN;
 239         }
 240       }
 241     }
 242     return variance;
 243   }
 244
 245   @Override
 246   public MergeSpecification findMergesToExpungeDeletes(SegmentInfos infos)
 247     throws CorruptIndexException, IOException {
 248     final int numSegs = infos.size();
 249     final int numLargeSegs = (numSegs < _numLargeSegments ? numSegs : _numLargeSegments);
 250     MergeSpecification spec = null;
 251
 252     if(numLargeSegs < numSegs) {
 253       // hack to create a shallow sub-range as SegmentInfos instance,
 254       // it does not clone all metadata, but LogMerge does not need it
 255       final SegmentInfos smallSegments = new SegmentInfos();
 256       smallSegments.rollbackSegmentInfos(infos.asList().subList(numLargeSegs, numSegs));
 257       spec = super.findMergesToExpungeDeletes(smallSegments);
 258     }
 259
 260     if(spec == null) spec = new MergeSpecification();
 261     for(int i = 0; i < numLargeSegs; i++) {
 262       SegmentInfo info = infos.info(i);
 263       if(info.hasDeletions()) {
 264         spec.add(new OneMerge(Collections.singletonList(infos.info(i))));
 265       }
 266     }
 267     return spec;
 268   }
 269
 270   @Override
 271   public MergeSpecification findMerges(SegmentInfos infos) throws IOException {
 272     final int numSegs = infos.size();
 273     final int numLargeSegs = _numLargeSegments;
 274
 275     if (numSegs <= numLargeSegs) {
 276       return null;
 277     }
 278
 279     long totalLargeSegSize = 0;
 280     long totalSmallSegSize = 0;
 281     SegmentInfo info;
 282
 283     // compute the total size of large segments
 284     for(int i = 0; i < numLargeSegs; i++) {
 285       info = infos.info(i);
 286       totalLargeSegSize += size(info);
 287     }
 288     // compute the total size of small segments
 289     for(int i = numLargeSegs; i < numSegs; i++) {
 290       info = infos.info(i);
 291       totalSmallSegSize += size(info);
 292     }
 293
 294     long targetSegSize = (totalLargeSegSize / (numLargeSegs - 1));
 295     if(targetSegSize <= totalSmallSegSize) {
 296       // the total size of small segments is big enough,
 297       // promote the small segments to a large segment and do balanced merge,
 298
 299       if(totalSmallSegSize < targetSegSize * 2) {
 300         MergeSpecification spec = findBalancedMerges(infos, numLargeSegs, (numLargeSegs - 1), _partialExpunge);
 301         if(spec == null) spec = new MergeSpecification(); // should not happen
 302         spec.add(new OneMerge(infos.asList().subList(numLargeSegs, numSegs)));
 303         return spec;
 304       } else {
 305         return findBalancedMerges(infos, numSegs, numLargeSegs, _partialExpunge);
 306       }
 307     } else if (_maxSegments < numSegs) {
 308       // we have more than _maxSegments, merge small segments smaller than targetSegSize/4
 309       MergeSpecification spec = new MergeSpecification();
 310       int startSeg = numLargeSegs;
 311       long sizeThreshold = (targetSegSize / 4);
 312       while(startSeg < numSegs) {
 313         info = infos.info(startSeg);
 314         if(size(info) < sizeThreshold) break;
 315         startSeg++;
 316       }
 317       spec.add(new OneMerge(infos.asList().subList(startSeg, numSegs)));
 318       return spec;
 319     } else {
 320       // hack to create a shallow sub-range as SegmentInfos instance,
 321       // it does not clone all metadata, but LogMerge does not need it
 322       final SegmentInfos smallSegments = new SegmentInfos();
 323       smallSegments.rollbackSegmentInfos(infos.asList().subList(numLargeSegs, numSegs));
 324       MergeSpecification spec = super.findMerges(smallSegments);
 325
 326       if(_partialExpunge) {
 327         OneMerge expunge  = findOneSegmentToExpunge(infos, numLargeSegs);
 328         if(expunge != null) {
 329           if(spec == null) spec = new MergeSpecification();
 330           spec.add(expunge);
 331         }
 332       }
 333       return spec;
 334     }
 335   }
 336
 337   private OneMerge findOneSegmentToExpunge(SegmentInfos infos, int maxNumSegments) throws IOException {
 338     int expungeCandidate = -1;
 339     int maxDelCount = 0;
 340
 341     for(int i = maxNumSegments - 1; i >= 0; i--) {
 342       SegmentInfo info = infos.info(i);
 343       int delCount = info.getDelCount();
 344       if (delCount > maxDelCount) {
 345         expungeCandidate = i;
 346         maxDelCount = delCount;
 347       }
 348     }
 349     if (maxDelCount > 0) {
 350       return new OneMerge(Collections.singletonList(infos.info(expungeCandidate)));
 351     }
 352     return null;
 353   }
 354
 355
 356   public static class MergePolicyParams {
 357     private int _numLargeSegments;
 358     private int _maxSmallSegments;
 359     private boolean _doPartialExpunge;
 360     private int _mergeFactor;
 361     private boolean _useCompoundFile;
 362     private int _maxMergeDocs;
 363
 364     public MergePolicyParams() {
 365       _useCompoundFile = true;
 366       _doPartialExpunge = false;
 367       _numLargeSegments = DEFAULT_NUM_LARGE_SEGMENTS;
 368       _maxSmallSegments = 2 * LogMergePolicy.DEFAULT_MERGE_FACTOR;
 369       _maxSmallSegments = _numLargeSegments + _maxSmallSegments;
 370       _mergeFactor = LogMergePolicy.DEFAULT_MERGE_FACTOR;
 371       _maxMergeDocs = LogMergePolicy.DEFAULT_MAX_MERGE_DOCS;
 372     }
 373
 374     public void setNumLargeSegments(int numLargeSegments) {
 375       _numLargeSegments = numLargeSegments;
 376     }
 377
 378     public int getNumLargeSegments() {
 379       return _numLargeSegments;
 380     }
 381
 382     public void setMaxSmallSegments(int maxSmallSegments) {
 383       _maxSmallSegments = maxSmallSegments;
 384     }
 385
 386     public int getMaxSmallSegments() {
 387       return _maxSmallSegments;
 388     }
 389
 390     public void setPartialExpunge(boolean doPartialExpunge) {
 391       _doPartialExpunge = doPartialExpunge;
 392     }
 393
 394     public boolean getPartialExpunge() {
 395       return _doPartialExpunge;
 396     }
 397
 398     public void setMergeFactor(int mergeFactor) {
 399       _mergeFactor = mergeFactor;
 400     }
 401
 402     public int getMergeFactor() {
 403       return _mergeFactor;
 404     }
 405
 406     public void setMaxMergeDocs(int maxMergeDocs) {
 407       _maxMergeDocs = maxMergeDocs;
 408     }
 409
 410     public int getMaxMergeDocs() {
 411       return _maxMergeDocs;
 412     }
 413
 414     public void setUseCompoundFile(boolean useCompoundFile) {
 415       _useCompoundFile = useCompoundFile;
 416     }
 417
 418     public boolean isUseCompoundFile() {
 419       return _useCompoundFile;
 420     }
 421   }
 422 }