抽奖码生成算法

[TFdream]

业务场景

线上经常举办一些活动，每个用户可以通过做任务获得抽奖码，然后某天定时开奖。

思路

抽奖码要求：

• 每个抽奖码都是全局唯一的，不能重复
• 一个用户可以获得1个或多个 抽奖码
• 抽奖码尽可能短

用户userId肯定是全局唯一的，我们可以生成一个全局唯一的sequence（可以依赖发号器或者数据库自增id），然后把二者结合起来形成一个新的全局唯一 64bit id。

例如，64bit 中 sequence占低32位（可支持40亿个抽奖码），userId占28位（可支持2亿用户），高4位预留（默认为0），格式如下：

| -- 4bit-- | ---------- 28bit ---------- | ------------ 32bit ------------ |

核心算法

LuckyCodeService.java

package io.mindflow.architect.luckcode.service;

import org.springframework.stereotype.Service;

/**
 * 生成抽奖码算法
 * @author Ricky Fung
 */
@Service
public class LuckyCodeService {
    private static final int DICT_BIT_LENGTH = 5;
    private static final int DICT_MASK = (1 << DICT_BIT_LENGTH) - 1;
    private static final int DICT_LENGTH = (1 << DICT_BIT_LENGTH);

    private static final int CODE_LENGTH = 13;

    //码表
    private final char[] dict;

    public LuckyCodeService(char[] dict) {
        if (dict==null || dict.length!= DICT_LENGTH) {
            throw new IllegalArgumentException("码表不合法");
        }
        this.dict = dict;
    }

    //-----------
    /**
     * 序列号
     */
    private static final int SEQUENCE_BIT_LENGTH = 32;
    private static final long SEQUENCE_MASK = (1L << SEQUENCE_BIT_LENGTH) - 1;

    /**
     * 用户id
     */
    private static final int USER_ID_BIT_LENGTH = 28;
    private static final long USER_ID_MASK = (1L << USER_ID_BIT_LENGTH) - 1;
    private static final int USER_LEFT_SHIFT_BITS = SEQUENCE_BIT_LENGTH;

    /**
     * 填充位
     */
    private static final int PADDING_BIT_LENGTH = 4;
    private static final long PADDING_MASK = (1L << PADDING_BIT_LENGTH) - 1;
    private static final int PADDING_LEFT_SHIFT_BITS = USER_ID_BIT_LENGTH + SEQUENCE_BIT_LENGTH;

    private static final long PADDING_NUM = 0;

    /**
     * 根据userId和seq 生成一个新的唯一64bit值
     * @param userId
     * @param seq
     * @return
     */
    public long getUid(long userId, long seq) {
        long uid = PADDING_NUM << PADDING_LEFT_SHIFT_BITS | ((userId & USER_ID_MASK) << USER_LEFT_SHIFT_BITS) | seq & SEQUENCE_MASK;
        return uid;
    }

    /**
     * 转换为定长码
     * @param id
     * @return
     */
    public String getFixedLengthCode(long id) {
        //2.转换为字符串
        StringBuilder sb = new StringBuilder(CODE_LENGTH);
        for (int i=0; i<CODE_LENGTH; i++) {
            int mod = (int) (id & DICT_MASK);
            sb.append(dict[mod]);
            id = id >> DICT_BIT_LENGTH;
        }
        StringBuilder rs = sb.reverse();
        return rs.toString();
    }

    public String getCode(long id) {
        //2.转换为字符串
        StringBuilder sb = new StringBuilder(CODE_LENGTH);
        while (id != 0) {
            int mod = (int) (id & DICT_MASK);
            sb.append(dict[mod]);
            id = id >> DICT_BIT_LENGTH;
        }
        StringBuilder rs = sb.reverse();
        return rs.toString();
    }
}

测试类：

import io.mindflow.architect.luckcode.service.LuckyCodeService;
import org.junit.Before;
import org.junit.Test;

/**
 * @author Ricky Fung
 */
public class AppTest {

    private LuckyCodeService codeService;

    @Before
    public void init() {
        char[] dict = {'A', 'B', 'C', 'D',
                'E', 'F', 'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T',
                'U', 'V', 'W', 'X', 'Y', 'Z', '2', '3', '4', '5', '6', '7', '8', '9'};

        this.codeService = new LuckyCodeService(dict);
    }

    @Test
    public void testBatch() {
        long userId = 24000000l;
        long seq = 364000000l;

        for (int i=0; i<20; i++) {
            long uid = codeService.getUid(userId, seq+i);
            System.out.println(uid +"\t"+codeService.getFixedLengthCode(uid));
        }
    }
}

生成结果如下：

103079215468000000	AC5TYAAL5EN2A
103079215468000001	AC5TYAAL5EN2B
103079215468000002	AC5TYAAL5EN2C
103079215468000003	AC5TYAAL5EN2D
103079215468000004	AC5TYAAL5EN2E
103079215468000005	AC5TYAAL5EN2F
103079215468000006	AC5TYAAL5EN2G
103079215468000007	AC5TYAAL5EN2H
103079215468000008	AC5TYAAL5EN2J
103079215468000009	AC5TYAAL5EN2K
103079215468000010	AC5TYAAL5EN2L
103079215468000011	AC5TYAAL5EN2M
103079215468000012	AC5TYAAL5EN2N
103079215468000013	AC5TYAAL5EN2P
103079215468000014	AC5TYAAL5EN2Q
103079215468000015	AC5TYAAL5EN2R
103079215468000016	AC5TYAAL5EN2S
103079215468000017	AC5TYAAL5EN2T
103079215468000018	AC5TYAAL5EN2U
103079215468000019	AC5TYAAL5EN2V

小结

当然，这样生成的64bit id 针对同一个用户而言的话高32位 是一样，如果产品上要求同一用户高32位 也不一样，我们可以使用 时间戳 来替代userId。时间戳（秒为单位）占28bit 可供使用8年之久，足够活动使了。

针对时间戳 核心逻辑如下：

/**
 * 纪元, 2018-08-01 00:00:00
*/
private static final long epoch = new DateTime(2018, 8, 1, 0, 0, 0).getMillis();

long seconds = (System.currentTimeMillis() - epoch)/1000;
long uid = PADDING_NUM << PADDING_LEFT_SHIFT_BITS | ((seconds & TIMESTAMP_MASK) << TIMESTAMP_LEFT_SHIFT_BITS) | seq & SEQUENCE_MASK;