如何使用BitMap做去重类指标上卷

发表于 分类于

最近有将想法落地到实际的一个大数据行业较为普遍的情况(去重类指标上卷)

场景说明

1
2
3
4
5
6
7
8
9
10
首先,去重类指标上卷和bitmap,大家都不陌生,这个方案也烂大街了
不过自己去实现一下还是有那么一些收获的

场景:
不同国家时区不一致,产生的数据在不同BU下可能需要的统计范围不一致
如,A部门需要的数据是基于北京时间统计出来,B部门需要的数据是基于梅森时间统计
意味有多少国家,同一指标就需要多个任务

去重类指标: 需要distinct类的指标,想要支持上卷就必须保留明细数据,不然就起多个任务重跑不同维度统计数据
BitMap: 用Bit来存放某种状态,适用于大数据量且状态不多的情况

方案

1
2
3
4
5
6
7
8
9
10
11
针对上述场景,将天周期任务重构为小时任务
所有数据来源时间统统转化为北京时间,并以北京时间进行调度
这样,后续只需要根据国家时区维表进行小时分区获取,灵活性大大提升

只不过这样会带来一个很明显的问题,去重类指标的计算
因为最终是给的小时粒度的统计信息,原按天去重统计的指标该如何处理
不可能说重新根据明细数据进行计算,那样重构意义不大了

可想而知,做大数据领域的一下就能get到使用bitmap进行去重指标的统计
我们可以在小时统计结果中,将去重类指标明细用bitmap进行存储
这样后续只需要合并多个小时的bitmap,即可得到天粒度的去重统计结果

实现

BitMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * @Author xz
 * @Date 2022/5/18 14:30
 * @Description 网上撸的一个BitMap自实现
 */
public class BitMap {
    /**
     * 插入数的最大长度，比如100，那么允许插入bitsMap中的最大数为99
     */
    private long length;
    public long size;
    private static int[] bitsMap;
    private static final int[] BIT_VALUE = {0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020,
            0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
            0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
            0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000};

    public BitMap(long length) {
        this.length = length;
        // 根据长度算出，所需数组大小
        bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
        this.size = bitsMap.length;
    }

    /**
     * 根据长度获取数据 比如输入63，那么实际上是确定数62是否在bitsMap中
     *
     * @return index 数的长度
     * @return 1:代表数在其中 0:代表
     */
    public int getBit(long index) {
        if (index < 0 || index > length) {
            throw new IllegalArgumentException("length value illegal!");
        }
        int intData = (int) bitsMap[(int) ((index - 1) >> 5)];
        return ((intData & BIT_VALUE[(int) ((index - 1) & 31)])) >>> ((index - 1) & 31);
    }

    /**
     * @param index 要被设置的值为index - 1
     */
    public void setBit(long index) {
        if (index < 0 || index > length) {
            throw new IllegalArgumentException("length value illegal!");
        }
        // 求出该index - 1所在bitMap的下标
        int belowIndex = (int) ((index - 1) >> 5);
        // 求出该值的偏移量(求余)
        int offset = (int) ((index - 1) & 31);
        int inData = bitsMap[belowIndex];
        bitsMap[belowIndex] = inData | BIT_VALUE[offset];
    }

    public int[] getMaxValue() {
        return BIT_VALUE;
    }

    public int[] getBitsMap() {
        return bitsMap;
    }

    /**
     * 输出bitMap中的二进制形式,方便查看数据的分布
     * @return
     */
    public String bitMapToString() {
        StringBuilder result = new StringBuilder("[\n");
        for (int element : bitsMap) {
            String eleString = Integer.toBinaryString(element);
            StringBuilder one = new StringBuilder();
            for (int i = 0; i < 32 - eleString.length(); i++)
                one.append("0");
            one.append(eleString);
            result.append(one.append(",\n"));
        }
        return result.append("]").toString();
    }
}

BitMapDemo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * @Author xz
 * @Date 2022/5/18 14:30
 * @Description TODO
 */
public class BitMapDemo {
    public static void main(String[] args) {
        BitMap bitMap1 = new BitMap(100);
        BitMap bitMap2 = new BitMap(100);
        long size = bitMap1.size;

        // hh=12时
        bitMap1.setBit(1);
        bitMap1.setBit(34);
        bitMap1.setBit(30);
        // hh=13时
        bitMap2.setBit(30);
        bitMap2.setBit(31);
        bitMap2.setBit(34);

        // 计算去重统计值
        int distinct = 0;
        for (int i = 0; i < size; i++) {
            int tmp = bitMap1.getBitsMap()[i] | bitMap2.getBitsMap()[i];
            distinct += countString(Integer.toBinaryString(tmp), "1");
        }
        System.out.println(distinct);
    }

    public static int countString(String str, String s) {
        String str1 = str.replaceAll(s, "");
        int len1 = str.length(), len2 = str1.length(), len3 = s.length();
        return (len1 - len2) / len3;
    }
}

存在的问题

1
2
3
4
5
6
7
8
9
10
A:
这种方案可以看见BitMap的大小需要指定,够用肯定是够用的
但是需要提前做好ID-Mapping操作,不然字符串没法支持
ID-Mapping如果没做好,会影响最终的结果值

B:
存储问题,怎么对他进行存储是还需要进行讨论的
最终生成的bitmap一定是存储在表内的
这个有时间可以翻翻Doris的底层源码,它是支持bitmap的
而且还支持bitmap的各种操作