簡介：?我們在開發中后臺應用或者中間件的時候，會存儲一些數據在內存中以加快訪問速度。隨著數據量的增加，除了可以放置于堆外，還可以通過實時壓縮來緩解。今天就給大家介紹一種壓縮整形數組的方式。

作者 | 玄胤
來源 | 阿里技術公眾號

我們在開發中后臺應用或者中間件的時候，會存儲一些數據在內存中以加快訪問速度。隨著數據量的增加，除了可以放置于堆外，還可以通過實時壓縮來緩解。今天就給大家介紹一種壓縮整形數組的方式。

一 數據壓縮

數組指 long[] 或者 int[] 類型，在 Java 中應用很廣。當數據量很大時，其內存占用的問題便突顯出來，原因是一個 long 類型是占 8 個字節，而 int 也是占用 4 個字節，當有千萬級別的數據時，其占用的空間便是上百 MB 級別的了。

1 去冗余

首先想到的就是縮減每個數字占用的空間。因為我們都知道就正數而言，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 級別，單次存取肯定是夠了。

壓縮效果

2 偏移量存儲

利用桶內是順序查找的性質，我們可以只在桶內第一個元素存原數字，后面的都存一個偏移量，因為當數據不會明顯離散（即一會兒是十幾，一會是幾十億那種），可以很好地縮減數據大小，比如兩個數都占用了 3 個字節，存偏移量后，第二個數字就可以使用 1~2 個字節來表示了。當然如果你對數組本身的順序沒有要求的話，還可以先對數組進行排序，這種偏移量的效果就可以暴表了。多數情況下，可以縮減 70% 以上。

二 存取優化

上述方案在線上某應用性能壓測時我們發現：單次隨機獲取沒有受到影響，但是批量順序獲取接口下降高達 97%，從 2800 多下降到了 72。經過研究發現，批量接口之所以下降明顯是由于觸及到了隨機獲取的 TPS 上限，在 ”圖：壓縮效果“ 中顯示，隨機獲取的極限 TPS 為 100w 左右，但是批量順序場景中每次批量操作會執行 1\~3w 次取操作，每次取操作走的是隨機獲取接口，所以只能是 72 這種兩位數的 TPS 了，因此我們需要深度優化壓縮數據的存取效率，為此采取了如下手段。

1 變固定長度桶為變長桶

之前采用二分查找是因數我們采用定長的桶（即每個桶存儲的字節數是相等的），每個桶存儲的數字數量不定，但如果我們采用變長桶，讓每個桶存儲 N 個數，那么，便可以直接通過 “整除+求余” 的方式快速打到數所在的桶，這樣在尋找桶下標的時候變可以以 O(1) 的復雜度找到，相比之前二分的 O(logn) 快了很多。經過測試批量接口的 TPS 增加為 320 左右，提升 4 倍以上，效果明顯。

非固定桶長度可以使索引塊長度固定，可快速查找

2 編寫專用迭代器

批量其實也就是遍例操作，在之前遍例都是單獨一個一個取的，即每次都通過 get 接口。這個接口每次都會計算一遍桶的位置，然后是偏移量，再從桶開始處依據偏移量挨個查找，在大量請求下性能開銷當然大。為此我們可以根據其順序取的特點專門設計一個迭代器，這個迭代器第一次初始化會記錄下桶的位置的，下一次就可以真接偏移一個數的長度 n 而直接找到一下個數據了，其時間復雜度為 O(1)。經過測試批量接口的 TPS 可以提升至 680 左右。

3 減少中間數據，使用棧直傳遞共用

在原來的解壓流程中，我們將數據從桶中讀取出來，然后傳遞給解決方法進行解壓，這里會在堆在產生大量的中間數據，并且之前使用許多 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 多。

4 將堆數據變為棧數據

這個改造點有些難度的，對于中間變量來說，有些是可以避免的，我們可以使用上述的方式解決，但是有些是不能避免的，比如我們最后在解壓數據的時候，對于需要返回的數字，我們肯定需要一個臨時存儲的地方，這就是 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 左右。

5 內聯短函數

每次函數調用都需要進行一次進棧退棧操作，也是費時的，在日常程序中這些損耗都可以忽略不計，但是在本次批量情況下就被放大了，通過前面的代碼我們可以發現 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()——當然，這是在極致性能下

減少中間數據、減少臨時變量

任何細小的性能損失在巨大的調用量在都會成倍擴大，所以對于批量接口要倍加小心

原文鏈接
本文為阿里云原創內容，未經允許不得轉載。

總結

以上是生活随笔為你收集整理的一种通用整形数组压缩方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。