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); 。。。。//还有好多,省略了 }
因为篇幅太长了,我转移到下一篇去了。
上一篇: 搞笑醉人的二货男女
推荐阅读
-
Windows 10 19H1中的新灯光主题详细解读
-
11.Spark Streaming源码解读之Driver中的ReceiverTracker架构设计以及具体实现彻底研究
-
11.Spark Streaming源码解读之Driver中的ReceiverTracker架构设计以及具体实现彻底研究
-
koa源码中promise的解读
-
【OVS2.5源码解读】 内核中的flow table流表操作
-
Spring源码学习:第1步--在Spring源码中添加最简单的Demo代码
-
深入解读Node.js中的koa源码
-
ActiveMQ 源码学习 1:从源码中找寻设计模式的踪影 activemqjavadesign_patternconcurrencysource
-
Windows 10 19H1中的新灯光主题详细解读
-
koa源码中promise的解读