lucene中的PackedInts源码解读-1

之前在看lucene4.x的源码的时候，老是遇见packedInts这个类，当时没有看懂，所以这个周一没事做又看了一下，茅塞顿开，看懂了，记个笔记，装一下B。如果读者认为我的博客中含有错误，请联系我，我的qq是1308567317，以免误人子弟。

顺便说一下，我这里看的是lucene6.6.0的代码。

之前阿帅写个关于博客是写PackedInts，不过他仅仅写了PackedInts的思路和好处，没有深入到代码中，我个人还是感觉不爽，我喜欢一行一行的抠代码。PackedInt的好处我这里就不再写了，可以参考帅广应的博客（http://blog.51cto.com/sbp810050504/1531624），我这里重点抠源码。他的优点其实就是一句话——省空间，因为lucene中为了记录他的索引信息，保存了大量的数字，所以如果有更好的保存数字的方式，是可以大量的节省空间的。我们从norm（也就是标准因子）入手，在norm存储在内存的时候，是保存在一个叫做PackedLongValues.Builder的对象内，这个其实是一个生成器模式中的生成器，先保存在他内部的long[]数字里面，当一个数组的长度满足一定值后，就要将数字打包，打包其实就是将数字放入到packedInts里面，因为他省空间.具体的代码为（方法的名字为：org.apache.lucene.util.packed.PackedLongValues.Builder.pack(long[], int, int, float)）：

 

void pack(long[] values, int numValues, int block, float acceptableOverheadRatio) {//第一个参数为准备打包的数组，第二个是要打包的数字的个数，第三个是打包后生成的Mutable是第几个（和咱要说的没有任何关系），第四个的是决定使用的Mutable的参数，即保存这些数字使用的空间
	assert numValues > 0;
	// compute max delta
	long minValue = values[0];
	long maxValue = values[0];
	for (int i = 1; i < numValues; ++i) {//循环所有的数字，找出最小值和最大值，方便确定下面的bitPerValue，即最大的一个数字需要多少个位，那么其他所有的数字都不会超过这个位数了
		minValue = Math.min(minValue, values[i]);
		maxValue = Math.max(maxValue, values[i]);
	}

	// build a new packed reader
	if (minValue == 0 && maxValue == 0) {//如果所有的值都是0，则单独生成一个NullReader，标识所有的值都是0.
		this.values[block] = new PackedInts.NullReader(numValues);
	} else {
		final int bitsRequired = minValue < 0 ? 64 : PackedInts.bitsRequired(maxValue);//最大的数字需要多少位，如果是负数，则需要64位，否则为（64-他的开始的0的数量）
		final PackedInts.Mutable mutable = PackedInts.getMutable(numValues, bitsRequired, acceptableOverheadRatio);//这个方法便是生成一个打包后的包，可以将数字存放在这里面，节省空间。Mutbale就是最后的包，
		for (int i = 0; i < numValues;) {
			i += mutable.set(i, values, i, numValues - i);//将数字放在生成的包里面
		}
		this.values[block] = mutable;
	}
}

 

从上面的方法中看，其实最终生成的不是PackedInts实例，只不过都是调用的packedInts方法。最终获得的是Mutable对象，也就是我们要的包。

 一个方法一个方法的看吧，先看下：PackedInts.bitsRequired(maxValue)，他里面就是调用的 return Math.max(1, 64 - Long.numberOfLeadingZeros(bits));他的意思是讲一个数字从高位到地位，从第一个不是0的位计算，一共多少位，因为最高位的多个0是没有必要的。

下面是最关键的方法：

 

 PackedInts.getMutable(numValues, bitsRequired, acceptableOverheadRatio);

 

public static Mutable getMutable(int valueCount, int bitsPerValue, float acceptableOverheadRatio) {
	final FormatAndBits formatAndBits = fastestFormatAndBits(valueCount, bitsPerValue, acceptableOverheadRatio);//根据要保存的数量和bitPerValue获得最终使用的存储格式（先不用管什么鬼）和真正的bitPerValue（即存储一个数字使用的位数可能会变）
	return getMutable(valueCount, formatAndBits.bitsPerValue, formatAndBits.format);//根据格式和bitPerValue获得最后的Mutable
}

这个方法确定最终使用的bitPerValue和存储的格式
public static FormatAndBits fastestFormatAndBits(int valueCount, int bitsPerValue, float acceptableOverheadRatio) {
    if (valueCount == -1) {
      valueCount = Integer.MAX_VALUE;
    }

    acceptableOverheadRatio = Math.max(COMPACT, acceptableOverheadRatio);//
    acceptableOverheadRatio = Math.min(FASTEST, acceptableOverheadRatio);
    float acceptableOverheadPerValue = acceptableOverheadRatio * bitsPerValue; // in bits从这里就可以知道acceptableOverheadRatio的意思了，即在原来的基础上，可以额外消耗多少空间。

    int maxBitsPerValue = bitsPerValue + (int) acceptableOverheadPerValue;//一个数字可以占用的最大位数。包括真正用来存储的部分和浪费的部分的和。

    int actualBitsPerValue = -1;//真正使用的bitPerValue
    Format format = Format.PACKED;//使用的存储的格式，先不用管，
    //这里的bitsPerValue已经是最大值的bitPervalue了，但是还要判断是否过度浪费
    if (bitsPerValue <= 8 && maxBitsPerValue >= 8) {//第一个判断表示如果用8位可以表示，第二个判断是用8位表示一个数字不至于太浪费，也就是说浪费的空间在允许的范围内
      actualBitsPerValue = 8;
    } else if (bitsPerValue <= 16 && maxBitsPerValue >= 16) {
      actualBitsPerValue = 16;
    } else if (bitsPerValue <= 32 && maxBitsPerValue >= 32) {
      actualBitsPerValue = 32;
    } else if (bitsPerValue <= 64 && maxBitsPerValue >= 64) {
      actualBitsPerValue = 64;
    } else if (valueCount <= Packed8ThreeBlocks.MAX_SIZE && bitsPerValue <= 24 && maxBitsPerValue >= 24) {//这个稍后再解释
      actualBitsPerValue = 24;
    } else if (valueCount <= Packed16ThreeBlocks.MAX_SIZE && bitsPerValue <= 48 && maxBitsPerValue >= 48) {//稍后再解释
      actualBitsPerValue = 48;
    } else {//如果不满足上面的条件，就看另一个格式，即PACKED_SINGLE_BLOCK的格式，看看这个可以吗，不过这个格式是有条件的
      for (int bpv = bitsPerValue; bpv <= maxBitsPerValue; ++bpv) {//尝试所有可能的bitPerValue。
        if (Format.PACKED_SINGLE_BLOCK.isSupported(bpv)) {//如果这个数量的是可以被支持的，即这个格式的使用是有条件的。下一篇博客中会查看下这个方法的意义
          float overhead = Format.PACKED_SINGLE_BLOCK.overheadPerValue(bpv);//这个方法我单独抽出来了，很重要的
          float acceptableOverhead = acceptableOverheadPerValue + bitsPerValue - bpv;//本来的可以接受的上线
          if (overhead <= acceptableOverhead) {//如果现在的上线可以满足条件，即小于原来的上限
            actualBitsPerValue = bpv;
            format = Format.PACKED_SINGLE_BLOCK;
            break;
          }
        }
      }
      if (actualBitsPerValue < 0) {//如果还是没有找到更好的，则使用原来的。此时的format仍然是packed
        actualBitsPerValue = bitsPerValue;
      }
    }
    return new FormatAndBits(format, actualBitsPerValue);
}

 

上面的Format.PACKED_SINGLE_BLOCK.overheadPerValue(bpv)

 

public float overheadPerValue(int bitsPerValue) {
	assert isSupported(bitsPerValue);
	final int valuesPerBlock = 64 / bitsPerValue;因为Format.PACKED_SINGLE_BLOCK的存储格式是使用一个long存储多个数字，这个valuesPerBlock就是表示一个long可以包含多少个数字
	final int overhead = 64 % bitsPerValue;  这个表示余数，即在存储了上面的valuesPerBlock个数字后，64位还剩余多少个，也就是额外消耗的空间
	return (float) overhead / valuesPerBlock; 用额外消耗的空间（也就是浪费的空间）除以记录的数字的数量，即每个数字浪费的空间
}

 

上面的 fastestFormatAndBits方法就可以获得最合适的format和bitPerValue了。在看看根据找到的格式和bitPerValue后再如何获得mutable，即getMutable方法

这个方法即得到最后的Mutable包。
public static Mutable getMutable(int valueCount,   int bitsPerValue, PackedInts.Format format) {
    assert valueCount >= 0;
    switch (format) {//判断使用的格式
      case PACKED_SINGLE_BLOCK://
        return Packed64SingleBlock.create(valueCount, bitsPerValue);
      case PACKED://
        switch (bitsPerValue) {
          case 8:
            return new Direct8(valueCount);
          case 16:
            return new Direct16(valueCount);
          case 32:
            return new Direct32(valueCount);
          case 64:
            return new Direct64(valueCount);
          case 24:
            if (valueCount <= Packed8ThreeBlocks.MAX_SIZE) {
              return new Packed8ThreeBlocks(valueCount);
            }
            break;
          case 48:
            if (valueCount <= Packed16ThreeBlocks.MAX_SIZE) {
              return new Packed16ThreeBlocks(valueCount);
            }
            break;
        }
        return new Packed64(valueCount, bitsPerValue);//如果没有上面的bitPerValue的，则使用这个。
      default:
        throw new AssertionError();
    }
}

 

我们一个一个来，先看最上面的 Packed64SingleBlock create

public static Packed64SingleBlock create(int valueCount, int bitsPerValue) {
    switch (bitsPerValue) {//这个方法里面会根据bitPerValue来查看使用哪一个类，我们看看前几个吧。
      case 1:
        return new Packed64SingleBlock1(valueCount);
      case 2:
        return new Packed64SingleBlock2(valueCount);
      case 3:
        return new Packed64SingleBlock3(valueCount);
     。。。。//还有好多，省略了
}

因为篇幅太长了，我转移到下一篇去了。