建议压缩库尽可能小地获取byte []而不考虑CPU费用？

Question

纠正我，如果我接近这个错误，但我有一个队列服务器和一群我正在群集中运行的Java工作。我的队列的工作单位非常小，但其中有很多。到目前为止，我的基准测试和对工作人员的审查表明，我的速度大约为200mb /秒。

所以我想弄清楚如何通过我的带宽获得更多的工作单位。目前我的CPU使用率并不是很高（40-50％），因为它可以比网络更快地处理数据。我希望通过队列获得更多的工作，并且愿意通过昂贵的压缩/解压来支付费用（因为每个核心的一半现在都处于闲置状态）。

我已经尝试过java的LZO和gzip，但想知道是否有更好的东西（即使它更昂贵的CPU）？

更新：数据是一个字节[]。基本上队列只以这种格式存储，因此我使用ByteArrayOutputStream来写入两个int和一个int []以byte []格式。 int []中的值都是0到100之间的整数（或1000，但绝大多数数字都是零）。这些列表非常大，从1000到10,000个项目（再次，大多数零。int []中不超过100个非零数字]

Answer 1

听起来像使用自定义压缩机制，利用数据可能非常有效。

首先，使用short[]（16位数据类型），而不是一个int[]将减半（！）发送的数据量，你可以做到这一点，因为数字是很容易-2^15（-32768）和2^15-1（32767）之间。这是很容易实现的。其次，您可以使用类似于游程编码的方案：正数表示字面数，而负数表示多个零（取绝对值后）。例如

[10, 40, 0, 0, 0, 30, 0, 100, 0, 0, 0, 0] <=> [10, 40, -3, 30, -1, 100, -4] 

这是很难实现的非常最坏的情况下，仅仅代short为int，但会提供〜80％的压缩（1000号，100非零，其中没有一个是连续的）。

我只是做了一些模拟来计算压缩比率。我测试了上面描述的方法，以及Louis Wasserman和sbridges提出的方法。两者表现都非常好。

假设阵列的长度和非零数的数目都是均匀的边界之间，这两种方法节省约5400 int S（或short多个）上平均具有约2.5％的原始压缩尺寸！运行长度编码方法似乎可以节省大约1个额外的int（或平均压缩大小小0.03％），即基本没有区别，所以应该使用最容易实现的方法。以下是50000个随机样本的压缩率的直方图（它们非常相似！）。

摘要：使用short！而非int S和压缩方法之一，您将能够将数据压缩到原来大小的1％！

对于模拟，我用下述R脚本：

SIZE <- 50000 

lengths <- sample(1000:10000, SIZE, replace=T) 
nonzeros <- sample(1:100, SIZE, replace=T) 

f.rle <- function(len, nonzero) { 
    indexes <- sort(c(0,sample(1:len, nonzero, F))) 
    steps <- diff(indexes) 
    sum(steps > 1) + nonzero # one short per run of zeros, and one per zero 
} 

f.index <- function(len, nonzero) { 
    nonzero * 2 
} 

# using the [value, -1 * number of zeros,...] method 
rle.comprs <- mapply(f.rle, lengths, nonzeros) 
print(mean(lengths - rle.comprs)) # average number of shorts saved 

rle.ratios <- rle.comprs/lengths * 100 
print(mean(rle.ratios)) # average compression ratio 

# using the [(index, value),...] method 
index.comprs <- mapply(f.index, lengths, nonzeros) 
print(mean(lengths - index.comprs)) # average number of shorts saved 

index.ratios <- index.comprs/lengths * 100 
print(mean(index.ratios)) # average compression ratio 


par(mfrow=c(2,1)) 
hist(rle.ratios, breaks=100, freq=F, xlab="Compression ratio (%)", main="Run length encoding") 
hist(index.ratios, breaks=100, freq=F, xlab="Compression ratio (%)", main="Store indices") 

Answer 2

我一直印象深刻BZIP2，用7Z和gzip相比。我没有亲自尝试这个Java实现，但它看起来很容易替换你的GZIP调用，并验证结果。

http://www.kohsuke.org/bzip2

Answer 3

你应该尝试对数据流的所有主要供应商，看看哪个效果最好。您还应该考虑一些算法运行时间会更长，从而为队列增加更多延迟。这可能会也可能不会成为问题，具体取决于您的应用程序。

如果您对数据有所了解，有时可以获得更好的压缩效果。 （dbaupp的回答很好地包含了这个方法）

这个comparison of compression algorithms可能会有用。从文章：

Answer 4

尝试两个varints编码数据，第一varint是序列中的个数指标，二是数字本身。对于0的条目，什么都不写。

Answer 5

我写了一个RLE算法的实现。这在字节数组上运行，因此可以用作现有代码的内联过滤器。如果您的数据将来发生变化，它应该安全地处理大量或负面的数据。

它将零序列编码为{0} {qty}，其中{qty}的范围是1..255。所有其他字节都以字节本身的形式存储。您在发送之前压扁您的字节数组，并在接收时将其膨胀回到完整大小。

public static byte[] squish(byte[] bloated) { 
    int size = bloated.length; 
    ByteBuffer bb = ByteBuffer.allocate(2 * size); 
    bb.putInt(size); 
    int zeros = 0; 
    for (int i = 0; i < size; i++) { 
     if (bloated[i] == 0) { 
      if (++zeros == 255) { 
       bb.putShort((short) zeros); 
       zeros = 0; 
      } 
     } else { 
      if (zeros > 0) { 
       bb.putShort((short) zeros); 
       zeros = 0; 
      } 
      bb.put(bloated[i]); 
     } 
    } 
    if (zeros > 0) { 
     bb.putShort((short) zeros); 
     zeros = 0; 
    } 
    size = bb.position(); 
    byte[] buf = new byte[size]; 
    bb.rewind(); 
    bb.get(buf, 0, size).array(); 
    return buf; 
} 

public static byte[] bloat(byte[] squished) { 
    ByteBuffer bb = ByteBuffer.wrap(squished); 
    byte[] bloated = new byte[bb.getInt()]; 
    int pos = 0; 
    while (bb.position() < bb.capacity()) { 
     byte value = bb.get(); 
     if (value == 0) { 
      bb.position(bb.position() - 1); 
      pos += bb.getShort(); 
     } else { 
      bloated[pos++] = value; 
     } 
    } 
    return bloated; 
}