通俗的理解Bitmap(位圖)和RoaringBitmap(壓縮位圖)

一、使用的場(chǎng)景

日常業(yè)務(wù)中需要大量存儲(chǔ)一些重復(fù)的字符串，例如每日簽到用戶、朋友圈點(diǎn)贊的好友、計(jì)算每日登錄用戶等。字符串無(wú)論長(zhǎng)短不僅會(huì)浪費(fèi)大量的存儲(chǔ)資源，而且讀取查詢也耗時(shí)耗資源，那有沒(méi)有一種存儲(chǔ)方式對(duì)這一類(lèi)場(chǎng)景進(jìn)行優(yōu)化呢。

二、什么原理

1、Bitmap如何解決這個(gè)問(wèn)題

拿每日簽到用戶的場(chǎng)景舉例，首先對(duì)用戶id進(jìn)行編號(hào)(offset)。


圖1.png

這樣我們只需要每天創(chuàng)建一個(gè)只存儲(chǔ)位的數(shù)組，比如2023-12-8日只有zhangsan和zhaoliu進(jìn)行了登錄，我們只需要一個(gè)4位的字節(jié)數(shù)組來(lái)進(jìn)行存儲(chǔ)：


圖2.png

這樣就達(dá)到了減少存儲(chǔ)的目的。

2、壓縮Bitmap是如何做到壓縮的

然而現(xiàn)實(shí)的場(chǎng)景中，存儲(chǔ)的數(shù)據(jù)并不是連續(xù)的，而是稀疏的，而且創(chuàng)建Bitmap的時(shí)候，長(zhǎng)度必須是最大的offset的長(zhǎng)度，例如我們有64個(gè)用戶，那么創(chuàng)建的位數(shù)組就是64位。
假如我們有1萬(wàn)個(gè)用戶，但今天只有編號(hào)9999的用戶登錄了系統(tǒng)，那我們還是創(chuàng)建一個(gè)1萬(wàn)個(gè)Byte的數(shù)組，反而增加了內(nèi)存的消耗。
為了更容易理解這個(gè)問(wèn)題，我們還是以64位Bitmap為例，也就是最大支持存儲(chǔ)64個(gè)用戶，當(dāng)我們只存儲(chǔ)63時(shí)：


圖3.png

先創(chuàng)建了長(zhǎng)度為64位的數(shù)組，只在63這個(gè)位置上的存儲(chǔ)是有意義的，其他位置都是0，那這種情況是不是可以進(jìn)行優(yōu)化呢？
我們把數(shù)組拆分成2組，1到32的用戶存儲(chǔ)到第1組，把33到64的用戶存儲(chǔ)到第二組。這個(gè)時(shí)候我們發(fā)現(xiàn)第一組的數(shù)組里全是0，那第一組是不是可以不創(chuàng)建？這樣我們就用一個(gè)32位大小的數(shù)組存儲(chǔ)了64位的數(shù)據(jù)。
接下來(lái)更進(jìn)一步，把64位的數(shù)組拆成每16個(gè)一組，那么我們只需要?jiǎng)?chuàng)建最后一個(gè)分組的數(shù)組，也就是16位的數(shù)組來(lái)達(dá)到進(jìn)一步壓縮的目的。
第4組


圖4.png
未命名流程圖.jpg

三、怎么模擬實(shí)現(xiàn)

代碼來(lái)簡(jiǎn)單的模擬實(shí)現(xiàn)壓縮Bitmap

1、先創(chuàng)建一個(gè)類(lèi)累存儲(chǔ)單個(gè)的Bitmap

public class ArrayContainer {
    public char[] values;

    public ArrayContainer(int initialCapacity) {
        this.values = new char[initialCapacity];
    }
}

2、實(shí)現(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、測(cè)試使用

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實(shí)現(xiàn)壓縮Bitmap存儲(chǔ)

Redis本身是支持Bitmap存儲(chǔ)的，但是壓縮的Bitmap是不支持的。根據(jù)上面的原理，同樣可以把一個(gè)大的Bitmap轉(zhuǎn)成一個(gè)個(gè)小的Bitmap來(lái)達(dá)到壓縮的目的。

1、包裝實(shí)體保存壓縮位圖的信息

public class CompressedBitInfo implements Serializable {

    /**
     * 真實(shí)offset
     */
    private long sourceOffset;
    /**
     * 分桶的編號(hào)
     */
    private long bucketIndex;
    /**
     * 桶內(nèi)的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、工具類(lèi)計(jì)算每個(gè)小桶的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、讀寫(xiě)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();
    }
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容