关于数组:一种通用整形数组压缩方法

简介：咱们在开发中后盾利用或者中间件的时候，会存储一些数据在内存中以放慢访问速度。随着数据量的减少，除了能够搁置于堆外，还能够通过实时压缩来缓解。明天就给大家介绍一种压缩整形数组的形式。

作者 | 玄胤
起源 | 阿里技术公众号

咱们在开发中后盾利用或者中间件的时候，会存储一些数据在内存中以放慢访问速度。随着数据量的减少，除了能够搁置于堆外，还能够通过实时压缩来缓解。明天就给大家介绍一种压缩整形数组的形式。

数组指 long[] 或者 int[] 类型，在 Java 中利用很广。当数据量很大时，其内存占用的问题便突显进去，起因是一个 long 类型是占 8 个字节，而 int 也是占用 4 个字节，当有千万级别的数据时，其占用的空间便是上百 MB 级别的了。

首先想到的就是缩减每个数字占用的空间。因为咱们都晓得就负数而言，int 3 个字节以上即可示意 2^24 = 16M 即 1600 百万个数，而再往后，即应用第 4 个字节，绝大多数咱们是用不到的，但也不能砍掉，万一还会用到的；所以能够将高位去掉，是一种可行的思路，但必须动静去掉，该用的时候还是得用，这就须要存储用到多少个字节了（见图：数字压缩基本原理）。

数字压缩基本原理

示意数据占用字节数有两种形式：一是借用原数据的几位来示意，就拿 long 来说，咱们只须要借用 3 位就能够笼罩用到的字节数了（因为 2ˆ3 = 8），因为 2^60 当前曾经是十分大的数了，简直用不到，所以咱们借用也根本不会产生负面成果；另一种就是利用字节最高位示意还有残余数据（见图 2），Facebook 在 Thrift 中就是应用此办法来压缩传输数据的。总之，咱们就是要把 long 或者 int 数组压缩成 byte 数组，在应用时再根据 byte 数组中存储的信息将对应的数字还原。

解压时辨认数据大小办法

以上压缩思路在传输场景下能够很好的解决存取问题，因为都是后退先出的思路，然而如果咱们须要压缩后的构造依然具备数组的下标拜访能力怎么办？

这里的难点是：之前每个数字都是固定长度，咱们能够通过“[单个数字占用的字节数]*[第几个]”很快地找到对应的内存地址，然而压缩过后每个数字占用的空间不是一样的，这种形式就生效了，咱们无奈得悉第 N 个数所处的内存地位。要取下标为 200 的值，难道只能线性查找 200 次吗？显然这样的效率是相当低的，其工夫复杂度就由 O(1) 降落为了 O(n)。有没有更好的方法呢？当然是有的。咱们能够建设索引（如下图），即：

将数字分为若干个桶，桶的大小可心调节（比方能够 1KB 一个桶，4KB 一个桶等）
咱们应用另一个数组，大小为桶的数量，存储每个桶所第一个数据所在的下标
在查找时我首先应用二分查找到对应的桶，再应用线性查找到对应的数据

带索引可晋升压缩后下标获取速度

因为只是在桶内是线性查找，而其个别不会太大，为 1KB 或者 4 KB（不能太少，因为每个桶的数组指针也是须要占用 16B 的）。因为第一次的索引二分查找解决了大部分问题，查找速度晋升显著，靠近 O(logN)。应用这套形式，经测试，在 4 亿随机数据的状况占用的空间能够缩减 30% 左右。通过简略测试 TPS 能够达到 100w 级别，单次存取必定是够了。

压缩成果

利用桶内是程序查找的性质，咱们能够只在桶内第一个元素存原数字，前面的都存一个偏移量，因为当数据不会显著离散（即一会儿是十几，一会是几十亿那种），能够很好地缩减数据大小，比方两个数都占用了 3 个字节，存偏移量后，第二个数字就能够应用 1~2 个字节来示意了。当然如果你对数组自身的程序没有要求的话，还能够先对数组进行排序，这种偏移量的成果就能够暴表了。少数状况下，能够缩减 70% 以上。

上述计划在线上某利用性能压测时咱们发现：单次随机获取没有受到影响，然而批量程序获取接口降落高达 97%，从 2800 多降落到了 72。通过钻研发现，批量接口之所以降落显著是因为涉及到了随机获取的 TPS 下限，在”图：压缩成果“中显示，随机获取的极限 TPS 为 100w 左右，然而批量程序场景中每次批量操作会执行 1\~3w 次取操作，每次取操作走的是随机获取接口，所以只能是 72 这种两位数的 TPS 了，因而咱们须要深度优化压缩数据的存取效率，为此采取了如下伎俩。

之前采纳二分查找是因数咱们采纳定长的桶（即每个桶存储的字节数是相等的），每个桶存储的数字数量不定，但如果咱们采纳变长桶，让每个桶存储 N 个数，那么，便能够间接通过“整除 + 求余”的形式疾速打到数所在的桶，这样在寻找桶下标的时候变能够以 O(1) 的复杂度找到，相比之前二分的 O(logn) 快了很多。通过测试批量接口的 TPS 减少为 320 左右，晋升 4 倍以上，成果显著。

非固定桶长度能够使索引块长度固定，可疾速查找

批量其实也就是遍例操作，在之前遍例都是独自一个一个取的，即每次都通过 get 接口。这个接口每次都会计算一遍桶的地位，而后是偏移量，再从桶开始处根据偏移量挨个查找，在大量申请下性能开销当然大。为此咱们能够依据其程序取的特点专门设计一个迭代器，这个迭代器第一次初始化会记录下桶的地位的，下一次就能够真接偏移一个数的长度 n 而间接找到一下个数据了，其工夫复杂度为 O(1)。通过测试批量接口的 TPS 能够晋升至 680 左右。

在原来的解压流程中，咱们将数据从桶中读取进去，而后传递给解决办法进行解压，这里会在堆在产生大量的两头数据，并且之前应用许多 ByteBuffer wrap 操作，wrap 每次都会新建一个 ByteBuffer 对象，相当的耗时。因为这均为只读操作并且目前不反对数据删除，咱们能够间接援用桶内的数据，通过栈传递给解压函数，这样会快很多。

批改前的代码如下，其次要逻辑是

计算数字所在的桶与偏移量，而后将其包装成 ByteBuffer
应用包装好的 ByteBuffer 线性剖析字节数组，通过偏移量查找桶内数字
根据数字的长度信息（即前三个位）将对应的字节复制至一个长期数组中
将长期数组传入 inflate 办法进行解压

public long get(int ix) {
        // 首先寻找 shard, 因为每个桶存储固定数量的数字，因而能够间接映射
        int i = ix / SHARD_SIZE;

        // 剩下的为须要线性查找的偏移量
        ix %= SHARD_SIZE;

        ByteBuffer buf = ByteBuffer.wrap(shards[i]);

        // 找到对应数据的偏移量
        long offset = 0;
        if (ix > 0) {int len = (Byte.toUnsignedInt(buf.get(0)) >>> 5);

            byte[] bag = new byte[len];
            buf.get(bag, 0, len);
            offset = inflate(bag);
        }

        // 重置地位
        buf.position(0);

        int numPos = 0;
        while (ix > 0) {int len = (Byte.toUnsignedInt(buf.get(numPos)) >>> 5);

            numPos += len;
            ix -= 1;
        }
        buf.position(numPos);

        int len = (Byte.toUnsignedInt(buf.get(numPos)) >>> 5);

        byte[] bag = new byte[len];
        buf.get(bag, 0, len);

        return offset + inflate(bag);
    }
}

private static long inflate(byte[] bag) {byte[] num = {0, 0, 0 ,0 ,0 ,0, 0, 0};

        int n = bag.length - 1;
        int i;
        for (i = 7; n >= 0; i--) {num[i] = bag[n--];
        }

        int negative = num[i+1] & 0x10;

        num[i + 1] &= 0x0f;
        num[i + 1] |= negative << 63;

        return negative > 0 ? -ByteBuffer.wrap(num).getLong() : ByteBuffer.wrap(num).getLong();}
}

批改后的代码：

public long get(int ix) {
        // 首先寻找 shard, 因为每个桶存储固定数量的数字，因而能够间接映射
        int i = ix / SHARD_SIZE;

        // 剩下的为须要线性查找的偏移量
        ix %= SHARD_SIZE;

        byte[] shard = shards[i];

        // 找到对应数据的偏移量
        long offset = 0;
        if (ix > 0) {int len = (Byte.toUnsignedInt(shard[0]) >>> 5);
            offset = inflate(shards[i], 0, len);
        }

        int numPos = 0;
        while (ix > 0) {int len = (Byte.toUnsignedInt(shard[numPos]) >>> 5);

            numPos += len;
            ix -= 1;
        }

        int len = (Byte.toUnsignedInt(shard[numPos]) >>> 5);

        return offset + inflate(shards[i], numPos, len);
}

private static long inflate(byte[] shard, int numPos, int len) {byte[] num = {0, 0, 0 ,0 ,0 ,0, 0, 0};

        System.arraycopy(shard, numPos, num, num.length - len, len);

        int i = num.length - len;
        int negative = num[i] & 0x10;

        num[i] &= 0x0f;
        num[i] |= negative << 63;

        return negative > 0 ? -longFrom8Bytes(num) : longFrom8Bytes(num);
}

比照能够看出，这里次要是去除了 bag 数组这个两头变量，通过援用原 shard 中的数据间接去获取数据对应的 byte 数组，之前都是通过 ByteBuffer 去获取桶中的字节数据，当初咱们都通过 shard[i] 间接查找，效率高了很多。通过测试，这一优化能够晋升 45% 左右的性能，间接将 TPS 拉升至 910 多。

这个革新点有些难度的，对于两头变量来说，有些是能够防止的，咱们能够应用上述的形式解决，然而有些是不能防止的，比方咱们最初在解压数据的时候，对于须要返回的数字，咱们必定须要一个长期存储的中央，这就是 inflate 第一行为什么有个 byte[] num = {0, 0, 0 ,0 ,0 ,0, 0, 0}; 语句的起因。然而思考下，这个数组只是为了存储 long 的 8 个字节数据，如果间接应用 long 那么相当于是在栈上初始化了一个 8 字节大小的数组了，这里须要解决的仅仅是针对 long 如何操作指定的字节。其实这里很简略，咱们只须要将对应字节左移至相应的地位即可，例如咱们须要对 long 的第二个字节批改为 0x02 只须要如下操作：

 longData = (longData & ˜(0xff << 2 * 8)) | (0x02 << 2 * 8)

还有一个细节，就是咱们间接从 byte[] 数据中取出的值是以有符号数示意的，间接合用上述上式位移会受符号位的影响，因而咱们须要应用 0xff & byteAry[i] 的形式将其转换成无符号的数。最初优化后的 inflate 办法如下：

private static long inflate(byte[] shard, int numPos, int len) {-        byte[] num = {0, 0, 0 ,0 ,0 ,0, 0, 0};
+       long data = 0;

-       System.arraycopy(shard, numPos, num, num.length - len, len);
+       for (int i = 0; i < len; i++) {+           data |= (long) Byte.toUnsignedInt(shard[numPos + i]) << (len - i - 1) * 8;
+       }

-       int i = num.length - len;
-       int negative = num[i] & 0x10;
+       // 查看符号位
+       long negative = data & (0x10L << (len - 1) * 8);

-       num[i] &= 0x0f;
-       num[i] |= negative << 63;
+       // 将占用位数据清零
+       data &= ~(0xf0L << (len - 1) * 8);

-       return negative > 0 ? -longFrom8Bytes(num) : longFrom8Bytes(num);
+       return negative > 0 ? -data : data;
}

在这里优化后所有的堆数据申明都移除掉了，而且这里还有个附带优化，即之前采纳长期数组的形式咱们还须要将数组转换为 long，即 longFrom8Bytes 办法所起的作用，当初咱们能够间接返回了，进一步的优化了成果，通过测试性能再次晋升 35%，TPS 至 1250 左右。

每次函数调用都须要进行一次进栈退栈操作，也是费时的，在日常程序中这些损耗都能够忽略不计，然而在本次批量状况下就被放大了，通过后面的代码咱们能够发现 get 办法中有一个 updateOffset 的函数，这个性能其实很简略，能够间接内联，也就多了一行代码，如下：

private void updateOffset() {byte[] shard = shards[shardIndex];

            // 找到对应数据的偏移量
            int len = (0xff & shard[0]) >>> 5;

            curOffset = inflate(shard, 0, len);
}

咱们将之内联后示意如下：

if (numPos >= shard.length) {
                shardIndex++;
                numPos = 0;

-              updateOffset();
                // 找到对应数据的偏移量
+              shard = shards[shardIndex];
+              curOffset = inflate(shard, 0, (0xff & shard[0]) >>> 5);
}

还有一些例如 Byte.toUnsignedInt(int) 也就是简略的一行代码，这种都能够间接复制进去去掉办法调用。

最初，咱们批量接口的 TPS 降级至了 1380 左右，相比于最开始 72 曾经晋升了近 20 倍。尽管相比于原数组还有些性能差距，但也是在同一个数量级上了。依照批量是按 5w 放大的计算，程序单次获取的 TPS 曾经达到 6500w，随机单次 get 也达到了 260w TPS，齐全足够满足生产须要了。

从下面的优化咱们能够得出：

Java 根本类型数据结构比对象构造快很多，越面向底层，越快
堆上调配数据很慢，高频调用还会频繁触发 Yong GC，对执行速度影响相当大，所以能栈绝不用堆
对象调用慢于间接操作，因为须要进退栈，所以如果是几行简略调用，间接将逻辑复制调出会快很多，例如 Byte.toUnsignedInt()——当然，这是在极致性能下
缩小两头数据、缩小长期变量
任何细小的性能损失在微小的调用量在都会成倍扩充，所以对于批量接口要倍加小心

原文链接
本文为阿里云原创内容，未经容许不得转载。

关于数组:一种通用整形数组压缩方法

一数据压缩

1 去冗余

2 偏移量存储

二存取优化

1 变固定长度桶为变长桶

2 编写专用迭代器

3 缩小两头数据，应用栈直传递共用

4 将堆数据变为栈数据

5 内联短函数

三性能

四优化总结

一 数据压缩