兑换码CDK生成算法

接到新需求,用户可以通过兑换码领取免单券。
大羊毛来了,到时候肯定会有恶意猜解的,所以我们得好好设计一下兑换码生成的算法。

网上搜索了一圈,发现没有太合适的算法,那就自己设计一个吧。
设计之前需要好好考虑一下我们对生成出来的兑换码有什么要求。
* 1.安全性:避免被黑客轻易尝试出兑换码,当然可以结合其他手段防止被暴力猜解,但是生成的兑换码本身就应该尽可能随机。
* 2.唯一性:很显然兑换码是全局唯一的。如果是一次生成所有的兑换码,全局唯一很好控制;如果需要多次生成多批兑换码,就需要额外考虑如何满足全局唯一了。
* 3.用户友好:对用户来说应该要易识别,好输入。虽然增加兑换码长度或加入特殊字符可以有更多种组合,从而增加安全性,但是对用户来说也变麻烦了。
* 4.可用性:兑换码对于服务器要友好,不要给服务器带来过多的压力,同时我要多少兑换码就得生成多少,不能因为去重就少了几个兑换码。
* 5.灵活性:可修改兑换码长度。

大概就是这些了吧。

确定字符集

考虑到用户友好性,特殊字符我们就不需要了,并且手机上切换大小写很不方便,所以兑换码对大小写不敏感。
英文字母有26个,数字有10个,一共有36个可用字符,而在某些字体中,l和o在大写情况下容易和1、0混淆,让用户摸不着头脑,所以排除掉,一共剩余34个可用字符。

确定兑换码长度

在字符集确定后,兑换码的长度就和安全性密切相关了,但是太长用户输入也不方便。
我们计算一下不同长度下的兑换码的全排列数量:
34^2=1,156‬
34^3=39,304‬
34^4=1,336,336
34^5=45,435,424
34^6=1,544,804,416
好了,不用算了。6位字符长度感觉很理想,不长,可能的组合也很多。

确保全局唯一性

如果所有的兑换码要一次性全部生成,确保全局唯一很容易,我们可以使用Set这种数据结构去重。
但是如果兑换码位数足够长,生成的兑换码足够多的,那么一次性生成的消耗就比较大,不过这不是问题,很多CDK就是采用这种方式来做的。
根据我这次的需求,因为免单券会卖给企业方,所以会分批发放,我们要多次生成多批兑换码。
当日我们也可以先一次性生成,存入数据库,分批方法券的时候只是绑定一下兑换码与券的关系就行了。
但是我又想了想,根据我们老板的风格,到时候又会让我去生产环境数据库,给他导XX个兑换码下来,想想就头痛,不如在他生成的时候就返回出来。
当然出于安全考虑,提前生成好了,如果因为漏洞被脱裤了,好家伙,这一波薅羊毛可以直接让公司破产。
反正最终我还是选择了每次只生成指定数量的兑换码。
那么问题就来了,如何保证全局唯一呢?每次生成的兑换码都去数据库查一下存不存在?注意可用性-性能的问题,这样给数据库造成了额外的压力。而且随着产生的兑换码越多,发送重复的可能性越大,性能也就会越差。
怎么办呢?根据之前生成订单号的经验,我加入了批次号这么一个概念。
每次生成兑换码后,批次号就+1,所以每一次使用的批次号都不同,从而保证了全局唯一性。
但是批次号是需要占用位数的,而且同一批的批次号一样,容易被找到规律。
对,这个就涉及到安全性了。

灵活性

结合业务,近阶段我们至少需要2位字符来标识批次号,但以后呢?
所以我们需要能够灵活控制兑换码的长度,方便以后增加位数。
在生成兑换码时我们就要根据指定的长度控制批次号位数,和随机码的位数。

校验码

在此之前我们还需要考虑两个问题,1.批次号太容易被看出规律;2.被暴力破解时能不能减少请求落入数据库的机会?或者说你希望在前端就能一定程度判断是否是错误的兑换码,从而在不用发起请求的情况下提示用户兑换码输入错误?
那就增加一个校验码吧。为了简单方便,我们使用校验和的方式来实现验证码。
如果我们使用规定的34个字符的字符集,那么乱输入一个兑换码,能够通过校验码校验的概率只有1/34,在遇到暴力破解时33/34的请求都不会落入数据库。
另外校验码也很随机,把他放在前面,至少(老板)不会一眼看出批次号。

安全性

其实现在才到重点。
1位校验码+2位批次号,那么只有3位随机码。3位随机码一共有39,304‬种组合。
想想,如果某一批次需要生成100个兑换码,那么碰撞概率很低。
但如果另一批需要生成10000个兑换码,马上碰撞率就接近25%了,很危险。
所以我们希望能够控制碰撞概率。
如果对于3位随机码来说,要保证1%的碰撞概率,那么只能生成393个兑换码。
那么在此基础上,考虑校验码,碰撞的概率能降低到大约0.0003,也就是万分之3。
这么看来即使他看出了批次号的规律,那么1W次请求也就只能猜出3个兑换码,我们的风控很容易就能把他抓出来,这么看来安全性可靠。
但是,如果黑客也看到我这偏文章,那么在知道批次号的情况下,又知道校验码的情况下,碰撞概率就只有1%了。其实风控还是能找出来,但是安全性相对下降了。
对此我们可以修改校验码算法,或者简单点修改一下校验码字符集字母的顺序,从而恢复一定的安全性。
当然如果你的需求不需要检验码,那么不要校验码,留给随机码更好。

再回到一次性生成10000个兑换码的情况,我们需要根据设定的随机码碰撞率,控制每个批次号生成的兑换码数量。当批次号生成了足够数量的兑换码后,就需要将批次号+1,进行下一次生成,最后需要将下次使用的批次号返回给调用方,由调用方保存起来。

封装代码

好像是时候上代码了。

public class CdkCreater {

    /**
     * 基准字符,共34位
     * 不确定显示时候的字体,为了辨识度,移除了o、l
     */
    private static final String BASE_CHAR = "abcdefghijkmnpqrstuvwxyz0123456789";

    /**
     * CDK随机字符长度
     */
    private int CDK_RANDOM_LENGTH = 3;

    /**
     * CDK批次号位数
     */
    private int CDK_BATCH_NO_LENGTH = 2;

    /**
     * 兑换码的最大碰撞概率
     */
    private double MAX_COLLISION_RATE = 0.01;

    public CdkCreater() {
    }

    /**
     * 指定参数构造
     * @param cdkRandomLength CDK随机字符长度
     * @param cdkBatchNoLength CDK批次号位数
     * @param maxCollisionRate 兑换码的最大碰撞概率
     */
    public CdkCreater(int cdkRandomLength, int cdkBatchNoLength, double maxCollisionRate) {
        this.CDK_RANDOM_LENGTH = cdkRandomLength;
        this.CDK_BATCH_NO_LENGTH = cdkBatchNoLength;
        this.MAX_COLLISION_RATE = maxCollisionRate;
    }

    /**
     * 检查CDK校验是否正常
     * @param cdk
     * @return
     */
    public static boolean checkCdk(String cdk) {
        int checkSum = BASE_CHAR.indexOf(cdk.charAt(0));
        int sum = 0;
        for (int i = 1; i < cdk.length(); i++) {
            char c = cdk.charAt(i);
            int index = BASE_CHAR.indexOf(c);
            sum += index;
        }
        sum = sum % BASE_CHAR.length();
        if (checkSum == sum) {
            return true;
        }
        return false;
    }

    /**
     * 生成兑换码
     * @return 下一次使用的batchNo
     */
    public int generator(int batchNo, int num, Set<String> codeSet) {
        double maxBatchNo = Math.pow(BASE_CHAR.length(), CDK_BATCH_NO_LENGTH);
        if (batchNo < 0 || batchNo > maxBatchNo) {
            throw new RuntimeException("batch_no_error");
        }
        /**
         * 控制碰撞的概率:
         * 根据生成数量与随机码的全排列数量之比计算理论碰撞率。
         * 通过增加batchNo编号,将生成数量num拆分到多个batchNo对应的兑换码中,
         * 从而将理论碰撞率控制在设定碰撞概率之下
         */
        double rate = num / Math.pow(BASE_CHAR.length(), CDK_RANDOM_LENGTH);
        int deltaNo = (int) (rate / MAX_COLLISION_RATE) + 1;
        if (batchNo + deltaNo > maxBatchNo) {
            throw new RuntimeException("batch_no_error");
        }
        // 将需要生成的num个兑换码,拆分为deltaNo次生成
        List<Integer> splitList = splitQuantity(num, deltaNo);
        for (Integer splitNum : splitList) {
            Set<String> code = getCodeSet(batchNo, splitNum);
            codeSet.addAll(code);
            batchNo++;
        }
        return batchNo;
    }

    /**
     * 将生成的num个兑换码,拆分为deltaNo次生成
     * @param totalNum 总数量
     * @param delta 拆分总数
     * @return
     */
    private List<Integer> splitQuantity(int totalNum, int delta) {
        List<Integer> ret = new ArrayList<>();
        int baseNum = (int) (MAX_COLLISION_RATE * Math.pow(BASE_CHAR.length(), CDK_RANDOM_LENGTH));
        for (int i = 0; i < delta - 1; i++) {
            ret.add(baseNum);
            totalNum -= baseNum;
        }
        ret.add(totalNum);
        return ret;
    }

    /**
     * 获取指定数量的兑换码集合
     * 兑换码格式:checkSum + batchNo + randomChar
     * @param batchNo
     * @param num
     * @return
     */
    private Set<String> getCodeSet(int batchNo, int num) {
        Set<String> set = new HashSet<>((int) (num / 0.75));
        int sum = 0;
        char[] batchNoChar = new char[CDK_BATCH_NO_LENGTH];
        for (int i = 0; i < CDK_BATCH_NO_LENGTH; i++) {
            int index = batchNo % BASE_CHAR.length();
            sum += index;
            batchNoChar[i] = BASE_CHAR.charAt(index);
            batchNo /= BASE_CHAR.length();
        }
        Random random = new Random(System.currentTimeMillis());
        for (int i = 0; i < num; ) {
            String cdk = nextCode(batchNoChar, sum, random);
            boolean success = set.add(cdk);
            if (success) {
                i++;
            }
        }
        return set;
    }

    /**
     * 获取下一个兑换码
     * 格式:checkSum + batchNo + randomChar
     * @param sum
     * @return
     */
    private String nextCode(char[] batchNoChar, int sum, Random random) {
        char[] randomChar = new char[CDK_RANDOM_LENGTH];
        for (int i = 0; i < CDK_RANDOM_LENGTH; i++) {
            int index = random.nextInt(BASE_CHAR.length());
            sum += index;
            randomChar[i] = BASE_CHAR.charAt(index);
        }
        char checkSumChar = BASE_CHAR.charAt(sum % BASE_CHAR.length());
        StringBuilder sb = new StringBuilder();
        sb.append(checkSumChar).append(batchNoChar).append(randomChar);
        return sb.toString();
    }

}

在需要生成兑换码时,我们构造creater时可以设定随机字符长度、批次号位数、随机码的最大碰撞概率,然后调用generator()方法就可以了。
generator()返回是下次使用的批次号,兑换码放在了参数中,需要传入Set<String>
在接收到兑换码请求后,可以调用CdkCreater.checkCdk()方法判断校验码是否正确,如果不正确就不需要再查询数据库了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据