欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

lucene中的PackedInts源码解读-1

程序员文章站 2022-03-23 14:26:05
...

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

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

之前阿帅写个关于博客是写PackedInts,不过他仅仅写了PackedInts的思路和好处,没有深入到代码中,我个人还是感觉不爽,我喜欢一行一行的抠代码lucene中的PackedInts源码解读-1
            
    
    博客分类: lucene lucenePackedInts 。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);
     。。。。//还有好多,省略了
}

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

 

 

 

 

 

 

 

 

 

相关标签: lucene PackedInts