一厚棵、使用的場景
日常業(yè)務中需要大量存儲一些重復的字符串烤宙，例如每日簽到用戶、朋友圈點贊的好友婿崭、計算每日登錄用戶等拨拓。字符串無論長短不僅會浪費大量的存儲資源，而且讀取查詢也耗時耗資源氓栈，那有沒有一種存儲方式對這一類場景進行優(yōu)化呢渣磷。
二、什么原理
1授瘦、Bitmap如何解決這個問題
拿每日簽到用戶的場景舉例醋界，首先對用戶id進行編號(offset)。
圖1.png
這樣我們只需要每天創(chuàng)建一個只存儲位的數(shù)組提完，比如2023-12-8日只有zhangsan和zhaoliu進行了登錄形纺，我們只需要一個4位的字節(jié)數(shù)組來進行存儲：
圖2.png
這樣就達到了減少存儲的目的。
2徒欣、壓縮Bitmap是如何做到壓縮的
然而現(xiàn)實的場景中逐样，存儲的數(shù)據(jù)并不是連續(xù)的，而是稀疏的打肝，而且創(chuàng)建Bitmap的時候脂新，長度必須是最大的offset的長度，例如我們有64個用戶粗梭，那么創(chuàng)建的位數(shù)組就是64位争便。
假如我們有1萬個用戶，但今天只有編號9999的用戶登錄了系統(tǒng)断医，那我們還是創(chuàng)建一個1萬個Byte的數(shù)組始花，反而增加了內存的消耗。
為了更容易理解這個問題孩锡，我們還是以64位Bitmap為例，也就是最大支持存儲64個用戶亥贸，當我們只存儲63時：
圖3.png
先創(chuàng)建了長度為64位的數(shù)組躬窜，只在63這個位置上的存儲是有意義的，其他位置都是0炕置，那這種情況是不是可以進行優(yōu)化呢荣挨？
我們把數(shù)組拆分成2組，1到32的用戶存儲到第1組朴摊，把33到64的用戶存儲到第二組。這個時候我們發(fā)現(xiàn)第一組的數(shù)組里全是0，那第一組是不是可以不創(chuàng)建弃鸦？這樣我們就用一個32位大小的數(shù)組存儲了64位的數(shù)據(jù)曲楚。
接下來更進一步，把64位的數(shù)組拆成每16個一組，那么我們只需要創(chuàng)建最后一個分組的數(shù)組鹃操，也就是16位的數(shù)組來達到進一步壓縮的目的韭寸。
第4組
圖4.png
未命名流程圖.jpg
三、怎么模擬實現(xiàn)
代碼來簡單的模擬實現(xiàn)壓縮Bitmap
1荆隘、先創(chuàng)建一個類累存儲單個的Bitmap
public class ArrayContainer {
public char[] values;
public ArrayContainer(int initialCapacity) {
this.values = new char[initialCapacity];
}
}
2恩伺、實現(xiàn)壓縮Bitmap的邏輯
public class CompressedBitmap {
public static final char Y = 1;
public static final char N = 0;
public static final int ARRAY_CONTAINER_SIZE = 16;
ArrayContainer[] containers;
public CompressedBitmap(long initialCapacity) {
int containersSize = (int)(initialCapacity / ARRAY_CONTAINER_SIZE);
this.containers = new ArrayContainer[containersSize];
}
public void add(long offset){
int shardIndex = getShardIndex(offset);
ArrayContainer container = containers[shardIndex];
if(container == null){
container = new ArrayContainer(ARRAY_CONTAINER_SIZE);
}
int shardOffset = getShardOffset(offset);
container.values[shardOffset] = Y;
containers[shardIndex] = container;
}
public int get(long offset){
int shardIndex = getShardIndex(offset);
ArrayContainer container = containers[shardIndex];
if(container == null){
return N;
}
int shardOffset = getShardOffset(offset);
if(Y == container.values[shardOffset]){
return Y;
}
return N;
}
public int getShardIndex(long offset){
return (int)((offset - 1) / ARRAY_CONTAINER_SIZE);
}
public int getShardOffset(long offset){
return (int)(offset % ARRAY_CONTAINER_SIZE);
}
public static void main(String[] args) {
System.out.println(2 / ARRAY_CONTAINER_SIZE);
}
}
3、測試使用
public static void main(String[] args) {
CompressedBitmap bitmap = new CompressedBitmap(64);
bitmap.add(63);
System.out.println(bitmap.get(63));
System.out.println(bitmap.get(64));
System.out.println(bitmap.get(2));
}
四椰拒、Redis實現(xiàn)壓縮Bitmap存儲
Redis本身是支持Bitmap存儲的晶渠，但是壓縮的Bitmap是不支持的。根據(jù)上面的原理燃观，同樣可以把一個大的Bitmap轉成一個個小的Bitmap來達到壓縮的目的褒脯。
1、包裝實體保存壓縮位圖的信息
public class CompressedBitInfo implements Serializable {
/**
* 真實offset
*/
private long sourceOffset;
/**
* 分桶的編號
*/
private long bucketIndex;
/**
* 桶內的offset
*/
private long bucketOffset;
public long getSourceOffset() {
return sourceOffset;
}
public void setSourceOffset(long sourceOffset) {
this.sourceOffset = sourceOffset;
}
public long getBucketIndex() {
return bucketIndex;
}
public void setBucketIndex(long bucketIndex) {
this.bucketIndex = bucketIndex;
}
public long getBucketOffset() {
return bucketOffset;
}
public void setBucketOffset(long bucketOffset) {
this.bucketOffset = bucketOffset;
}
@Override
public String toString() {
return "CompressedBitInfo{" + "sourceOffset=" + sourceOffset + ", bucketIndex=" + bucketIndex + ", bucketOffset=" + bucketOffset + '}';
}
}
2仪壮、工具類計算每個小桶的Bitmap
public class CompressedBitTookit {
public static final long DEFAULT_BUCKET_SIZE = 65536L;
public static CompressedBitInfo getBitInfo(long sourceOffset, long bucketSize) {
CompressedBitInfo bucketInfo = new CompressedBitInfo();
bucketInfo.setSourceOffset(sourceOffset);
long bucketIndex = sourceOffset / bucketSize;
long bucketOffset = sourceOffset % bucketSize;
bucketInfo.setBucketIndex(bucketIndex);
bucketInfo.setBucketOffset(bucketOffset);
return bucketInfo;
}
public static CompressedBitInfo getBitInfo(long sourceOffset) {
CompressedBitInfo bucketInfo = getBitInfo(sourceOffset, DEFAULT_BUCKET_SIZE);
return bucketInfo;
}
public static long getSourceOffset(long bucketIndex, long bucketSize, long bucketOffset) {
return bucketIndex * bucketSize + bucketOffset;
}
public static long getSourceOffset(long bucketIndex, long bucketOffset) {
return getSourceOffset(bucketIndex, DEFAULT_BUCKET_SIZE, bucketOffset);
}
3憨颠、讀寫B(tài)itmap
public void setCompressedBit(String key, long offset, boolean value, int expireSeconds) {
CompressedBitInfo bitInfo = CompressedBitTookit.getBitInfo(offset);
String bitKey = getBitKey(key, bitInfo.getBucketIndex());
redis.setBit(bitKey, bitInfo.getBucketOffset(),value);
redis.expire(bitKey, expireSeconds);
}
public void setCompressedBit(String key, long offset, boolean value) {
CompressedBitInfo bitInfo = CompressedBitTookit.getBitInfo(offset);
String bitKey = getBitKey(key, bitInfo.getBucketIndex());
redis.setBit(bitKey, bitInfo.getBucketOffset(),value);
}
public void setCompressedBit(String key, long offset) {
this.setCompressedBit(key, offset, true);
}
public void remCompressedBit(String key, long offset) {
this.setCompressedBit(key, offset, false);
}
public Boolean getCompressedBit(String key, long offset) {
CompressedBitInfo bitInfo = CompressedBitTookit.getBitInfo(offset);
String bitKey = getBitKey(key, bitInfo.getBucketIndex());
log.debug("getCompressedBit with key:{}, offset:{}",bitKey, bitInfo.getBucketOffset());
return redis.getBit(bitKey, bitInfo.getBucketOffset());
}
public void deleteAllCompressedBit(String key, long maxOffset) {
CompressedBitInfo bitInfo = CompressedBitTookit.getBitInfo(maxOffset);
for (int i = 0; i < bitInfo.getBucketIndex(); i++) {
String bitKey = getBitKey(key, i);
redis.expire(bitKey, 0);
}
}
private String getBitKey(String key, long bucketIndex) {
return new StringBuffer(key).append("_").append(bucketIndex).toString();
}
