Lucene单值编码压缩算法源码解析

目录

• 引言
• VInt编码
• 编码原理
• VInt编码1314
• VInt编码10
• VInt编码-10
• 源码实现
• 编码
• 解码
• zigzag编码
• 编码原理
• 源码
• 编码
• 解码
• ZFloat
• 编码原理
• 源码编码
• 解码
• ZDouble
• 编码原理
• 源码编码
• 解码
• TLong
• 编码原理
• 源码编码
• 解码

引言

本文收集了我在看Lucene源码中遇到的所有的对单值（int，long，float，double）的压缩算法，可能一种类型针对不同的场景会有多种不同的压缩策略，本文会随着我自己的源码阅读不断持续更新。

不管是什么类型的数值，在计算机中存储都是二进制存储，而我们说对其进行压缩或者编码，其实就是只保留有效信息，什么是有效信息？就是哪些bit位上面是1。所以所有的压缩编码方式都是设计一定的策略，只保留有效信息，并且能够解码或者解压缩。

注意：本文源码基于lucene-core-9.1.0

VInt编码

编码原理

int是4个字节，VInt是对int类型的压缩编码，VInt中的v指的是variant（可变的），也就是VInt编码的int的存储空间的大小是以字节为单位的变长大小。VInt编码结果中的每个字节分为两部分：

• 第1位：标记位，如果是1，表示后面的字节也属于当前value的VInt编码结果，如果是0，则表示当前value的VInt编码结果结束。
• 剩下的7位：数据位，VInt中所有字节的低7位合起来就是完成的value的值。

我们来看几个例子更好理解：

VInt编码1314

如上图所示，整型1314原始编码需要4字节，但是我们可以发现高位的一连串0其实都是无效信息，其实是不需要存储的。VInt编码首先取原始二进制编码的最低7位，如上图绿色所示，这部分构成VInt的第一个字节的最低7位，因为1314除了最低7位，剩下的非全0，所以第一个VInt编码的字节的首位的标记位为1，表示VInt编码后面还有一个字节参与编码。VInt编码的第二个字节的最低7位就是由原始二进制编码中红色的部分表示（可以通过右移7位，获取最低7位得到），1314剩下的数据都是0，则VInt编码的第2个字节的第一位标记位为0，表示1314的VInt编码结束了。所以1314的VInt编码就是两个字节。

VInt编码10

如上图所示，对于整型10，正常的的4字节编码，前3个字节都是0，可以做个标记，不用占用真实的空间。

换成VInt编码，只需要一个字节。需要注意的是，这个字节的第一位是标记位。如果标记位是0，则表示当前字节就是数值的结束字节。如果标记位是1，则表示后面有字节属于当前数值。如下图所示：

VInt编码-10

如果使用VInt编码算法对-10进行编码，结果如下图所示：

我们会发现，-10的VInt编码居然要5个字节，因此VInt编码只对正数有压缩作用。

源码实现

编码

public final void writeVInt(int i) throws IOException {
  // 如果i的最低7位置0后i非0
  while ((i & ~0x7F) != 0) {
    // i & 0x7F：取最低7位
    // | 0x80 为flag为置1
    writeByte((byte) ((i & 0x7F) | 0x80));
    // i 右移7位
    i >>>= 7;
  }
  // 剩下不足7位的
  writeByte((byte) i);
}

解码

public int readVInt() throws IOException {
  byte b = readByte();
  // 如果 b >= 0, 说明flag位是0，当前要读的值只有一个字节。
  if (b >= 0) return b;
  int i = b & 0x7F;
  b = readByte();
  i |= (b & 0x7F) << 7;
  if (b >= 0) return i;
  b = readByte();
  i |= (b & 0x7F) << 14;
  if (b >= 0) return i;
  b = readByte();
  i |= (b & 0x7F) << 21;
  if (b >= 0) return i;
  b = readByte();
  // 最后一个字节最多只有4位是有效的
  i |= (b & 0x0F) << 28;
  // 如果最后一个字节只有低四位有效，则说明格式正确
  if ((b & 0xF0) == 0) return i;
  throw new IOException("Invalid vInt detected (too many bits)");
}

VLong编码

对long类型的变长编码原理同VInt，不再赘述。

zigzag编码

编码原理

zigzag是一种编码方式，可以用于int和long，原理一模一样，下面以int为例子。

我们想一下为什么负数会阻碍数据压缩呢？我们知道，数据压缩其实就是保留有效信息，在计算机中，数据就是0和1,1肯定是有效信息，所以压缩就是去掉无效的0。

先观察下正数和负数二进制的规律：

虽然我们举的例子10和-10只是个例，但是了解负数补码的计算方式，就知道，负数是正数按位取反再加1。所以正数的高位是连续的0，负数的高位是连续的1。

因此，可以分两步来处理，首先要想办法把这个符号位1处理下，简单的做法就是把1挪到最后一位。剩下的数据位，我们可以把数据位取反，数据位和符号位异或就可以取反。

zigzag对正数的编码，其实就是正数左移一位。

源码

编码

public static int zigZagEncode(int i) {
  // (i >> 31)：处理符号位，把所有的位都设置为符号位，等待和0（数据位左移1位空出来的0）做异或，就能保留符号位在最后一位
  // (i << 1)：处理数据位，数据为左移1位，把最后一位用来存符号位，其他数据为都和符号位做异或编码
  return (i >> 31) ^ (i << 1);
}

解码

public static int zigZagDecode(int i) {
  // (i >>> 1)：还原数据位，最后和符号位做异或解码
  // -(i & 1)：还原符号位，i的最后一位是符号位，该表达式把每一位都设置为符号位
  return ((i >>> 1) ^ -(i & 1));
}

ZFloat

编码原理

ZFloat对float的编码分为3种情况来处理：

• 情况1：如果float的值强转成int类型后的值intVal和float相等，并且intVal的范围在[-1，125]之间，这种情况只用一个byte就可以，将byte的最高位设为1标记这种情况，把intVal的值加1后存储在byte的低7位中。
• 情况2：排除第一种情况之外，如果float>0，则按IEEE 754的标准直接存储，并没有压缩处理。
• 情况3：其他情况首先写入一个byte：0xFF标记最后一种情况，然后直接按IEEE 754的标准直接存储，并没有压缩处理。

从上面的说明可能会有一些疑问：

• 第一种情况中为什么范围就是[-1，125]？

  最终存储的时候会加1，范围变成了[0，126]，二进制的范围[0000 0000，0111 1110]，因为最高位会设置成1标记这种情况，而1111 1111留出来作为情况3的标记，所以范围就是[-1，125]。

• 后面两种根本就没有做压缩，第三种情况还额外要多一个字节，不能和第2种情况合并吗？

  不能合并，合并了，属于情况3的值会和情况1的有冲突，读取的时候无法识别。

• 凭什么说，zfloat是对float的压缩算法？

  我觉得还是要分场景，如果大部分数值都是属于情况1，那压缩效果是比较好的，如果大部分的数值都是属于情况3，则不仅没有压缩，反而膨胀了。

上面说的可能还没有直接看源码来的清楚。

源码编码

static void writeZFloat(DataOutput out, float f) throws IOException {
  int intVal = (int) f;
  final int floatBits = Float.floatToIntBits(f);
  // 为什么负数只对-1处理呢？原因是-1+1可以变成0
  // 为什么正数直到125呢，是因为第3个分支，会先写个标记byte：0xFF，所以不能包括126,126+1=127=0xFF会冲突
  if (f == intVal && intVal >= -1 && intVal <= 0x7D && floatBits != NEGATIVE_ZERO_FLOAT) {
    // 最高位是1表示这种情况
    out.writeByte((byte) (0x80 | (1 + intVal)));
  } else if ((floatBits >>> 31) == 0) { // 其他大于0的情况
    // 为什么不直接writeInt呢？我也不清楚，单独的lucene-core模块没有找到原因。
    out.writeByte((byte) (floatBits >> 24));
    out.writeShort((short) (floatBits >>> 8));
    out.writeByte((byte) floatBits);
  } else { // 其他小于0的情况
    out.writeByte((byte) 0xFF);
    out.writeInt(floatBits);
  }
}

解码

static float readZFloat(DataInput in) throws IOException {
  // 先读取第一个字节，用来判断属于哪种情况
  int b = in.readByte() & 0xFF;
  if (b == 0xFF) { // 情况3，后面还有4字节IEEE 754编码的float
    return Float.intBitsToFloat(in.readInt());
  } else if ((b & 0x80) != 0) { // 情况1
    // b & 0x7f：最高位设为0
    // -1 是因为编码的时候进行加1了
    return (b & 0x7f) - 1;
  } else { // 情况2
    int bits = b << 24 | ((in.readShort() & 0xFFFF) << 8) | (in.readByte() & 0xFF);
    return Float.intBitsToFloat(bits);
  }
}

ZDouble

编码原理

double的编码和float的非常像，但是多了一种情况，如果double的值强转成float后精度没有丢失，则直接用float存储。其他情况和float的一模一样，我们就直接看源码吧。

源码编码

static void writeZDouble(DataOutput out, double d) throws IOException {
  int intVal = (int) d;
  final long doubleBits = Double.doubleToLongBits(d);
  // 因为多了一种情况，所以需要多一个标记，因此范围成了 [-1..124]
  if (d == intVal && intVal >= -1 && intVal <= 0x7C && doubleBits != NEGATIVE_ZERO_DOUBLE) {
    out.writeByte((byte) (0x80 | (intVal + 1)));
    return;
  } else if (d == (float) d) { // 和zfloat相比，多出来的一种情况，使用标记：0xFE
    out.writeByte((byte) 0xFE);
    out.writeInt(Float.floatToIntBits((float) d));
  } else if ((doubleBits >>> 63) == 0) { // 同zfloat情况2
    out.writeByte((byte) (doubleBits >> 56));
    out.writeInt((int) (doubleBits >>> 24));
    out.writeShort((short) (doubleBits >>> 8));
    out.writeByte((byte) (doubleBits));
  } else { // 同zfloat情况3
    out.writeByte((byte) 0xFF);
    out.writeLong(doubleBits);
  }
}

解码

static double readZDouble(DataInput in) throws IOException {
  int b = in.readByte() & 0xFF;
  if (b == 0xFF) {
    return Double.longBitsToDouble(in.readLong());
  } else if (b == 0xFE) {
    return Float.intBitsToFloat(in.readInt());
  } else if ((b & 0x80) != 0) {
    return (b & 0x7f) - 1;
  } else {
    long bits =
        ((long) b) << 56
            | ((in.readInt() & 0xFFFFFFFFL) << 24)
            | ((in.readShort() & 0xFFFFL) << 8)
            | (in.readByte() & 0xFFL);
    return Double.longBitsToDouble(bits);
  }
}

TLong

编码原理

TLong是对使用long类型存储的毫秒级timestamp的编码算法。TLong的编码有个header记录使用的是哪种编码方式，四种header的格式如下所示：

• day：如果timestap的值是1000*60*60*24的整数倍，则可以保留除以1000*60*60*24之后的值来编码。
• hour：如果timestap的值是1000*60*60的整数倍，则可以保留除以1000*60*60之后的值来编码。
• second：如果timestap的值是1000的整数倍，则可以保留除以1000之后的值来编码。
• uncompressed：其他情况就不需要先处理。

header是一个byte，我们的编码方式只有4种，只需要两位就能标记，剩下的6位我们也不能浪费。用其中5位存储经过上述预处理后的值的低5位，如果除了低5位外非零，使用VLong存储剩下的值。而header剩下的1位就是用来表示除了header之外是否还有剩下的值，我们看个例子，下面的例子中是可以整除hour级别的，因此使用的hour的编码方式：

如上面的例子所示，2022-11-08 10:00:00的毫秒级时间戳是1667872800000，它可以整除1000*60*60，所以使用的header是hour并且整除后的值是463298，463298的二进制和zigzag编码（整数的zigzag编码就是左移一位）如上图所示，把zigzag编码的低5位拷贝到header的低5位，zigzag剩下的值不为0，则header中的标记位设置为1。zigzag剩下的值使用VLong编码，因此TLong编码的结果如上图所示。

源码编码

static void writeTLong(DataOutput out, long l) throws IOException {
  int header;
  if (l % SECOND != 0) { // 无压缩
    header = 0;
  } else if (l % DAY == 0) { // 按天粒度
    header = DAY_ENCODING;
    l /= DAY;
  } else if (l % HOUR == 0) { // 小时粒度
    header = HOUR_ENCODING;
    l /= HOUR;
  } else { // 秒粒度
    header = SECOND_ENCODING;
    l /= SECOND;
  }
  // 先按zigzag编码
  final long zigZagL = BitUtil.zigZagEncode(l);
  // zigzag编码的最后5位放在head的最后5位
  header |= (zigZagL & 0x1F);
  final long upperBits = zigZagL >>> 5;
  if (upperBits != 0) { // 如果zigzag编码的值去除最后5位后非零，则header的第3位设置为1，表示后面还有数据
    header |= 0x20;
  }
  // 写入header
  out.writeByte((byte) header);
  if (upperBits != 0) { // zigzag编码的值去除最后5位剩下的value使用VLong的方式编码
    out.writeVLong(upperBits);
  }
}

解码

static long readTLong(DataInput in) throws IOException {
  // 读取header
  int header = in.readByte() & 0xFF;
  // 取header最后5位
  long bits = header & 0x1F;
  if ((header & 0x20) != 0) { // 判断是否除了header之外后面还有数据
    // in.readVLong()：读取VLong编码的剩下数据
    // << 5： 左移5位，为header中的低5位留出空间
    // bits |=：bits是保存的是完整的数据
    bits |= in.readVLong() << 5;
  }
  // 使用zigzag解码
  long l = BitUtil.zigZagDecode(bits);
  switch (header & DAY_ENCODING) { // 按照不同的编码，乘以相应的倍数还原时间戳
    case SECOND_ENCODING:
      l *= SECOND;
      break;
    case HOUR_ENCODING:
      l *= HOUR;
      break;
    case DAY_ENCODING:
      l *= DAY;
      break;
    case 0:
      break;
    default:
      throw new AssertionError();
  }
  return l;
}

以上就是Lucene单值编码压缩算法源码解析的详细内容，更多关于Lucene单值编码压缩算法的资料请关注我们其它相关文章！