Saas系统设计之高效去重

78人浏览 / 0人评论 / 添加收藏

Saas系统用户数据非常多,如何设计一个占用内存小,高效去重的方案?

在这样的一个场景下,租户的信息下面有很多子租户,租户的标示一般会关联一个手机号码或者唯一标识,如何校验这个手机号码或者唯一标识就摆在我们的眼前。

这个时候我们一般会考虑到使用位图。

bitmap 索引具有非常高效的数据结构,可以用于存储大规模数据的位信息。其中每一位对应一个元素,如果当前位为1,则表示该元素存在于集合中,否则表示不存在。如果要表示一个包含 100个元素的数据集,那么我们可以创建一个包含 100 位的位数组。

image.png

这个时候有人要问,如果我们要存储手机号码?该如何处理,比如134-5678-0001,难道我们申请10^11位这么长?大家想一想可以这么设计吗?

实际上是可以这么设计的,但是如果数据很大的话,那么占用的空间会很大,我们可以考虑使用分段的策略来完成。

比如我们可以把134-5678-0001分成三段,每一段使用一个位图集,那么我们只需要三个位图集就可以处理该问题了。这样是不是就可以了?

bitmap可以支持插入与查找,但是不能对重复的数据做插入和查找。

插入操作的时候是将对应位置的位从把0 设置为 1,将元素添加到数据集中。查找操作通过检查相应位置的位来确定元素是否存在于数据集中。如果位为 1,表示元素存在;如果为 0,表示元素不存在。

bitmap 非常高效,空间复杂度是O(n),时间复杂度为O(1)。因为位操作可以直接定位,就像Hashmap算法一样,不受数据集大小的限制。

我们使用java代码来实现它。

在这里我们先阐述几个概念.

long类型是64位,2个Long类型是可以标示2*64=128位,也相当于可以标识1-128这个数字范围。

因为我们使用的是long数组,所以我们是先要定位到时拿一个数组下标,然后再修改这个long的位。比如long[2],我现在有一个数字是68,那么我需要先定位到是哪个数组下标,数组下标:68/64=1,如何计算修改它的位:68%64=4。所以我们就可以得出如果要插入68的话,要修改数组1下标的第4位。

Java代码来实现:

package com.mgface.platform.core.task;

import java.util.Random;

/**
 * 位图实现
 */
public class BitMap {

    private long[] bits;
    //因为long类型是64位,所以这里我们设置为64
    private int BIT_SIZE = 64;

    //我们暂定每一个对象只存储最大不超过9999,9999/64取值大于128所以设置为256
    public BitMap() {
        bits = new long[256];
    }

    public BitMap(int n) {
        bits = new long[n];
    }


    /**
     * 添加num
     */
    public void add(long num) {
        int index = getIndex(num);
        long position = getPosition(num);
        // 将1左移position位后,position那个位置就是1,
        // 然后数组的index位置做与运算,这样index索引中的position位置就替换成1了
        bits[index] = bits[index] | (1 << position);
    }

    /**
     * 判断指定数字num是否存在
     */
    public boolean contains(int num) {
        int index = getIndex(num);
        long position = getPosition(num);
        // 将1左移position后,position那个位置就是1,然后和以前的数据做与运算,判断是否为0即可
        return (bits[index] & 1 << position) != 0;
    }

    /**
     * 重置num在位图的索引位置
     */
    public void clear(long num) {
        int index = getIndex(num);
        long position = getPosition(num);
        // 对1进行左移position个位置,然后取反,最后与byte[index]进行与操作
        bits[index] &= ~(1 << position);
    }

    /**
     * 得到long[]的下标
     */
    public int getIndex(long num) {
        return (int) num / BIT_SIZE;
    }

    /**
     * 得到num在64bit数组上的分布
     */
    public long getPosition(long num) {
        return num % BIT_SIZE;
    }

    public static void main(String[] args) {
        // 假设有1亿个手机号
        long numberOfPhoneNumbers = 100_000_000L;
        // 存储前3位,3位最大标示为999,取16
        BitMap firstDigitsSet = new BitMap(16);
        // 存储后8位,8位最大标示为9999_9999/64=156_2499我们取2^21
        //这里可以使用2个位图集合,为了方便只使用1个,可以自己替换
        BitMap lastDigitsSet = new BitMap(209_7152);
        long time = System.currentTimeMillis();
        // 模拟手机号数据,将已存在的手机号设置为true
        for (long i = 0; i < numberOfPhoneNumbers; i++) {
            // 手机号
            String phoneNumber = generateRandomPhoneNumber();
            // 提取手机号的前3位和后8位,忽略掉地区编码,如有需要,自己改动
            String firstDigits = phoneNumber.substring(3, 6);
            String lastDigits = phoneNumber.substring(6);
            int firstDigitsIndex = Integer.parseInt(firstDigits);
            int lastDigitsIndex = Integer.parseInt(lastDigits);

            // 检查前3位是否重复
            if (firstDigitsSet.contains(firstDigitsIndex)) {
                // 检查后8位是否重复
                if (lastDigitsSet.contains(lastDigitsIndex)) {
                    // 打印重复的号码
                    System.out.println("重复的号码:" + firstDigits + lastDigits);
                } else {
                    // 不重复则存储号码后8位
                    lastDigitsSet.add(lastDigitsIndex);
                }
            } else {
                firstDigitsSet.add(firstDigitsIndex);
            }
        }

        time = System.currentTimeMillis() - time;
        System.out.println(time);
    }


    /**
     * 随机电话号码生成
     */
    private static String generateRandomPhoneNumber() {
        Random random = new Random();

        // 生成国家或地区代码
        String countryCode = "+86";
        // 随机生成前三位
        String prefix = String.format("%03d", random.nextInt(1000));
        // 随机生成号码4位前缀、4位后缀
        String middle = String.format("%04d", random.nextInt(10000));
        String suffix = String.format("%04d", random.nextInt(10000));
        // 拼接生成的手机号码
        return countryCode + prefix + middle + suffix;
    }
}

扫码_搜索联合传播样式-白色版.png

全部评论