lucene中的PackedInts源码解读(2)-Packed64SingleBlock

紧接上一篇文章，介绍一下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);  
     。。。。//还有好多，省略了  
} 

 看第一个Packed64SingleBlock1，继承自Packed64SingleBlock，而他又继承自 PackedInts.MutableImpl  ，这个类又继承自Mutable，即Packed64SingleBlock1就是一个Mutable。其中 PackedInts.MutableImpl仅仅是保存了bitPerValue和valueCount，绝大部分代码都在Packed64SingleBlock中，我们看一下这个类的set方法代码（方法名：org.apache.lucene.util.packed.Packed64SingleBlock.set(int, long[], int, int)，目的是讲多个值进行写入）:

@Override
public int set(int index, long[] arr, int off, int len) {
    assert len > 0 : "len must be > 0 (got " + len + ")";
    assert index >= 0 && index < valueCount;
    len = Math.min(len, valueCount - index);
    assert off + len <= arr.length;

    final int originalIndex = index;

    // go to the next block boundary
    final int valuesPerBlock = 64 / bitsPerValue;
    // 看看插入点index是不是在一个新的long的开始，如果！=0，则表示是在一个已经有值的long里面。这个代码其实是为下面的bulk set做准备的，先将一些数字存储，然后等到index恰好是一个新的long的开始
    final int offsetInBlock = index % valuesPerBlock;
    if (offsetInBlock != 0) {//将最开始的几个放入到现在long里面，
    	for (int i = offsetInBlock; i < valuesPerBlock && len > 0; ++i) {
    		set(index++, arr[off++]);//单独的调用set
    		--len;
    	}
    	if (len == 0) {//如果已经完了，则直接返回
    		return index - originalIndex;
    	}
    }

    //bulk set  开始的地方一定是一个新的block，即一个新的long
    assert index % valuesPerBlock == 0;//开始的那个一定是在一个新的long里面。
    final BulkOperation op = BulkOperation.of(PackedInts.Format.PACKED_SINGLE_BLOCK, bitsPerValue);//将方法封装在一个类中了，下面有代码分析
    assert op.longBlockCount() == 1;
    assert op.longValueCount() == valuesPerBlock;
    final int blockIndex = index / valuesPerBlock;//在第几个long上。
    final int nblocks = (index + len) / valuesPerBlock - blockIndex;//使用的long一共有几个。这个值有可能是0，因为可能len不够一个valuesPerBlock。
    
    op.encode(arr, off, blocks, blockIndex, nblocks);//下面有介绍
    final int diff = nblocks * valuesPerBlock;//上面的op.encode使用了几个long，可能是0，因为可能剩下的数字不够一个long的，这时候就是0
    index += diff; len -= diff;

    if (index > originalIndex) {//index不可能小于originalIndex，只要有数字进行了编码就会是大于，不过即使是大于，也会有的数字没有编码，比如上面的op.encode就可能没有编码任何数字，不过没关系，会进行下一次编码的。
	    // stay at the block boundary
	    return index - originalIndex;
    } else {
    	// no progress so far => already at a block boundary but no full block to set  没有进行一个的设置，原因就是数字很少，不到一个long，而且插入点index一开始就是在一个新的long里面。此时就要调用子类的set方法。
    	assert index == originalIndex;
    	return super.set(index, arr, off, len);//父类方法中单独的调用set方法，即一个一个的设置
    }
}

 下面看一下上面的BulkOperation op = BulkOperation.of(PackedInts.Format.PACKED_SINGLE_BLOCK, bitsPerValue);以及他的encode方法

 

public static BulkOperation of(PackedInts.Format format, int bitsPerValue) {
    switch (format) {
    case PACKED:
      assert packedBulkOps[bitsPerValue - 1] != null;
      return packedBulkOps[bitsPerValue - 1];
    case PACKED_SINGLE_BLOCK:
      assert packedSingleBlockBulkOps[bitsPerValue - 1] != null;
      return packedSingleBlockBulkOps[bitsPerValue - 1];//这个很简单，就是一个数组里面的内容
    default:
      throw new AssertionError();
    }
}

 上面的packedSingleBlockBulkOps数组

 

 

private static final BulkOperation[] packedSingleBlockBulkOps = new BulkOperation[] {
    new BulkOperationPackedSingleBlock(1),
    new BulkOperationPackedSingleBlock(2),
    new BulkOperationPackedSingleBlock(3),
    new BulkOperationPackedSingleBlock(4),
    new BulkOperationPackedSingleBlock(5),
    new BulkOperationPackedSingleBlock(6),
    new BulkOperationPackedSingleBlock(7),
    new BulkOperationPackedSingleBlock(8),
    new BulkOperationPackedSingleBlock(9),
    new BulkOperationPackedSingleBlock(10),
    null,
    new BulkOperationPackedSingleBlock(12),
    null,
    null,
    null,
    new BulkOperationPackedSingleBlock(16),
    null,
    null,
    null,
    null,
    new BulkOperationPackedSingleBlock(21),
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    null,
    new BulkOperationPackedSingleBlock(32),
};

 可以发现这些都是同一个类，只不过传入的bitPerValue不同，他的查找方式很简单，即使用bitPerValue作为下标进行查找的。我们看一下这个类的encode方法（方法名org.apache.lucene.util.packed.BulkOperationPackedSingleBlock.encode(long[], int, long[], int, int)）

 

 

/** 第一个参数表示此次要加入的值，第二个参数表示要从第一个参数的第几个开始加入，第三个参数表示目的地，也就是存放压缩后的数字的long数组，第四个表示从blocks的第几个开始存放，第五个表示一共几轮循环） */
@Override
public void encode(long[] values, int valuesOffset, long[] blocks, int blocksOffset, int iterations) {
	for (int i = 0; i < iterations; ++i) {
		blocks[blocksOffset++] = encode(values, valuesOffset);//对valueCount个进行编码，返回编码后的long数字，里面的逻辑是将多个数字合并到一个long里面去。
		valuesOffset += valueCount;//valueCount表示一个long可以容纳多少个数字，这个是由bitsPerValue来决定的。
	}
}

 里面的encode方法： 

/** 很简单，就是讲多个数字合并到一个long里面去，前提是多个数字的程度小于64，不然没用 */
private long encode(long[] values, int valuesOffset) {
	long block = values[valuesOffset++];//对几个数字进行存储，使用这个数字，他的最低bitsPerValue位已经包含了原来的值了，高位都是0.
	for (int j = 1; j < valueCount; ++j) {//从1开始，因为最后面的一个（即最低位的数字）不需要移动
		block |= values[valuesOffset++] << (j * bitsPerValue);//除了最低位的数字，挨个移动到高位。
	}
	return block;
}

 看完了这个encode方法，就很简单了，他的目的就是讲多个数字放在一个long里面。

 

上面还提到，如果index不是一个新的logn的开始时，就会调用set方法（上面的加粗标红的代码），我们看一下Packed64SingleBlock的子类对这个方法的实现。因为Packed64SingleBlock有很多子类，我们就挑几个看看。

1、下面是org.apache.lucene.util.packed.Packed64SingleBlock.Packed64SingleBlock1.set(int, long)，即bitPerValue是1的类的实现

 @Override
public void set(int index, long value) {
  final int o = index >>> 6;//找到第几个long，右移6位，即除以64，因为现在一个数字只占用1位，一个long有64个数字，所以要除以64就可以找到第几个long数字
  final int b = index & 63;//在这个long中的开始位置
  final int shift = b << 0;
  blocks[o] = (blocks[o] & ~(1L << shift)) | (value << shift);//(blocks[o] & ~(1L << shift))这个代码的目的是将这个范围的位都置位0，然后再|上 value<<shift，可以看出是先从后边（也就是低位）开始放的，和之前的op.encode的顺序是一样的。
}

 

2、下面是org.apache.lucene.util.packed.Packed64SingleBlock.Packed64SingleBlock3.set(int, long)，即bitPerValue是3的类的实现

@Override
public void set(int index, long value) {
  final int o = index / 21;//除以21，是因为一个64的long最多能存储21个3位的数字，所以除以21就可以找到是第几个long。一个long最多存放21个3位的，所以每个long都会浪费一个位
  final int b = index % 21;//余数找到是这个long的第几个数字
  final int shift = b * 3;//一个数字占3位，b个占b*3位。
  blocks[o] = (blocks[o] & ~(7L << shift)) | (value << shift);//逻辑和上面的一样。7L是因为3位最大是8，他的mask就是8-1=7，mask确保了这个范围内的位都是1。
}

 

经过上面的代码的分析，我们可以知道Packed64SingleBlock这个类的实现原理了，他就是使用了一个long数组，用多个数字放在一个long数字里面（一个数字不允许横跨两个long），但是他也会浪费空间的，即比如上面加粗标红的，一个long用于存放21个3位的数字会浪费一个位，所以才有了Packed64SingleBlock.isSupported(int)方法，即看看某个bitPerValue是否被支持，仅仅有{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 21, 32}这些数字是被支持的，因为他们用64位的long存储的话省空间，比如这里的21，一个long可以存储3个，仅仅浪费一个位，而如果是20，一共可以存3个，浪费4位，也就是每每存一个就会浪费一个多。存储10位的时候也会浪费4位，但是存储10位的时候可以存6个，即存6个才会浪费4个，效率更高些。

 

 

 看完了上面的编码，还有解码没看呢，即当等到lucene flush的时候，要讲之前存储的所有的数字都读取出来，然后写入到directory中。先看下Packed64SingleBlock的get方法（方法名：org.apache.lucene.util.packed.Packed64SingleBlock.get(int, long[], int, int)）

 

public int get(int index, long[] arr, int off, int len) {
    assert len > 0 : "len must be > 0 (got " + len + ")";
    assert index >= 0 && index < valueCount;
    len = Math.min(len, valueCount - index);
    assert off + len <= arr.length;

    final int originalIndex = index;

    // go to the next block boundary
    final int valuesPerBlock = 64 / bitsPerValue;
    final int offsetInBlock = index % valuesPerBlock;
    if (offsetInBlock != 0) {//和编码时的操作一样，如果不等于0 ，则表示不是一个新的long的开始，此时要先读取一些，直到读取一个新的long
      for (int i = offsetInBlock; i < valuesPerBlock && len > 0; ++i) {
        arr[off++] = get(index++);//单个解压的代码
        --len;
      }
      if (len == 0) {
        return index - originalIndex;
      }
    }

    // bulk get  批量读取，从一个新的long开始。整个思路很明确，和编码的时候很相似
    assert index % valuesPerBlock == 0;
    final PackedInts.Decoder decoder = BulkOperation.of(PackedInts.Format.PACKED_SINGLE_BLOCK, bitsPerValue);//这里的累仍然是上面的数组，所以decode方法还是BulkOperationPackedSingleBlock的方法
    assert decoder.longBlockCount() == 1;
    assert decoder.longValueCount() == valuesPerBlock;
    final int blockIndex = index / valuesPerBlock;
    final int nblocks = (index + len) / valuesPerBlock - blockIndex;
    decoder.decode(blocks, blockIndex, arr, off, nblocks);//下面有解释
    final int diff = nblocks * valuesPerBlock;
    index += diff; len -= diff;

    if (index > originalIndex) {
      // stay at the block boundary
      return index - originalIndex;
    } else {
      // no progress so far => already at a block boundary but no full block to
      // get
      assert index == originalIndex;
      return super.get(index, arr, off, len);
    }
}

 BulkOperationPackedSingleBlock类的decode方法

 

 

public void decode(long[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
	for (int i = 0; i < iterations; ++i) {
		final long block = blocks[blocksOffset++];//要解压这个
		valuesOffset = decode(block, values, valuesOffset);//解压到values里面的第valuesOffset个，返回更新后的valuesOffset值
	}
}

 上面的decode方法

private int decode(long block, long[] values, int valuesOffset) {
	values[valuesOffset++] = block & mask;//第一个，不用移动
	for (int j = 1; j < valueCount; ++j) {//
		block >>>= bitsPerValue;//向后移动位数，这样最低bitPerValue就是下一个数字了
		values[valuesOffset++] = block & mask;
	}
	return valuesOffset;
}

 这样就看完了批量解压的操作，上面的单个的解压代码还是在Packed64SingleBlock类的实现类中，按照上面，还是看两个，Packed64SingleBlock1，和Packed64SingleBlock3.

 

Packed64SingleBlock1的：

 

public long get(int index) {
  final int o = index >>> 6;//第几个long，因为一个logn上有64个，所以要除以64.
  final int b = index & 63;//在这个long上的开始位置（&63，即除以64的余数）
  final int shift = b << 0;
  return (blocks[o] >>> shift) & 1L;
}

 Packed64SingleBlock3的：

 

public long get(int index) {
  final int o = index / 21;//第几个long，以为一个logn上有21个，所以要除以21.
  final int b = index % 21;//在这个long上的开始位置
  final int shift = b * 3;
  return (blocks[o] >>> shift) & 7L;
}

 

这样就看懂了整个Packed64SingleBlock这个Mutable的代码，包括编码和解码的过程，他的思路还是很明确的，就是将多个数字放在一个long里面，不过也会造成一点浪费。在下一篇博客中，看一下另一个类型的Mutable。