Implementation of redemption coupons (UUID, snowflake algorithm, self-increasing id)

Make a request:

Algorithm Analysis

UUID

Advantages: unique, highly random, 32-bit hexadecimal, not bad in readability

Disadvantages: takes up too much memory (32*16=128 bits), uncontrollable

Snowflake algorithm:

Advantages: Globally unique, suitable for distributed systems, high generation efficiency, ID is a number and easy to understand

Disadvantages: Not suitable for situations that require high readability, and it is not easy to prevent flash flooding (here you can learn about the composition of the snowflake algorithm, which consists of a sign bit, a sign bit of 0, and then a 41-bit timestamp, 10 bits Working machine ID, 12-digit serial number), when the data is large, there may be performance problems.

Auto-increment id

Pros: Efficient, usually numerical, easy to understand

Disadvantages: Not suitable for global uniqueness, difficult to prevent explosions, obvious patterns, and unable to meet special character requirements.

Here we will introduce Base32

Marker

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Characters

A

B

C

D

E

F

G

H

J

K

L

M

N

P

Q

R

Marker

16

17

18

19

20

twenty one

twenty two

twenty three

twenty four

25

26

27

28

29

30

31

Characters

S

T

U

V

W

X

Y

Z

2

3

4

5

6

7

8

9

for example:

01001 00010 01100 10010 01101 11000 01101 00010 11110 11010

  • 01001 is converted to decimal 9, and the character obtained by checking the array is: K

  • The conversion of 00010 to decimal is 2, and the character obtained by checking the array is: C

  • 01100 is converted to decimal 12, and the character obtained by checking the array is: N

  • The conversion of 10010 to decimal is 18, and the character obtained by checking the array is: B

  • Converting 01101 to decimal is 13, and the character obtained by checking the array is: P

  • 11000 converted to decimal is 24, the character obtained by checking the array is: 2

But think about it, we ultimately require that characters cannot exceed 10 bits, and each character corresponds to 5 bits, so the binary number cannot exceed 50 bits.

The results obtained by UUID and Snowflake algorithm, one is 128 bits and the other is 64 bits, both far exceed our requirements.

Does the auto-increment ID algorithm meet our needs?

The self-increasing ID increases from 1 to the maximum value of Integer, which can reach more than 4 billion numbers, and the bytes occupied are only 4 bytes, which is 32 bits, which is still far from the 50 bit limit. The rest meets the requirements!

Then we want to redeem it again

How to judge the redemption issue? There are two options here:

  • Based on the database: When we designed the database, there was a field that marked the status of the redemption code. Each time you redeem the code, you can go to the database to query the status to avoid redemption.

    • Advantages: simple

    • Disadvantages: high pressure on database

  • Based on BitMap: Redemption or no redemption are two states, corresponding to 0 and 1, and the redemption code uses an auto-incrementing ID. If each auto-incrementing ID corresponds to a bit, we use the status of each bit to represent the redemption status. Is it a perfect solution to the problem? This algorithm happens to be the underlying implementation of BitMap, and BitMap in Redis can support 2^32 bits.

    • Advantages: short answer, efficient, good performance

    • Disadvantages: Depends on Redis

Riot prevention

Consider the idea of JWT

  • Header: Recording algorithm

  • Payload: Record user information

  • Verify Signature: Verification, used to verify the entire token

Therefore, we can also simulate this idea:

  • First prepare a secret key

  • Then use the secret key to encrypt the self-increasing ID and generate a signature

  • Use Base32 to transcode the signature and self-incremented ID to generate a redemption code.

As long as the secret key is not leaked, no one can forge the redemption code. As long as the redemption code is tampered with, the verification will fail.

Of course, we cannot use MD5 and RSA algorithms to generate signatures here, because the signatures obtained by these algorithms are too long, generally more than 128 bits, exceeding the length limit.

Therefore, here we must use a special signature algorithm. Since the core of our redemption code is an auto-increasing ID, which is a number, here we plan to use a bit-weighted signature algorithm:

  • Divide the self-increasing ID (32 bits) into one group of every 4 digits, a total of 8 groups, and convert them to decimal

  • Give each group a different weight

  • After weighting and summing each group of numbers, the result is the signature.

  • For example

    The final weighted sum is: 4*2 + 2*5 + 9*1 + 10*3 + 8*4 + 2*7 + 1*8 + 6*9 = 165

    The weight array here can be understood as the encryption key.

  • Of course, in order to prevent the secret key from being guessed, we can prepare 16 sets of secret keys. Splice a 4-digit fresh value before the redemption code’s auto-incremented ID, which can be random. Whatever this value is, which group of keys is taken.

CodeUtil

package com.tianji.promotion.utils;

import com.tianji.common.constants.RegexConstants;
import com.tianji.common.exceptions.BadRequestException;

/**
 * <h1 style='font-weight:500'>1. Redemption code algorithm description:</h1>
 * <p>The redemption code is divided into plain text and cipher text. The plain text is a 50-digit binary number and the cipher text is a Base32-encoded string of length 10.</p>
 * <h1 style='font-weight:500'>2. Plain text structure of redemption code:</h1>
 * <p style='padding: 0 15px'>14 (check code) + 4 (fresh value) + 32 (serial number)</p>
 * <ul style='padding: 0 15px'>
 * <li>Serial number: a monotonically increasing number that can be generated through Redis</li>
 * <li>Fresh value: It can be the last 4 digits of the coupon ID. The redemption code of the same coupon will have the same mark.</li>
 * <li>Payload: Splice the fresh value (4 bits) with the sequence number (32 bits) to get the payload</li>
 * <li>Check code: The load is divided into groups of 4 digits, each group is multiplied by the weighted number, finally accumulated and summed, and then the remainder is obtained by calculating the remainder of 2^14</li>
 *</ul>
 * <h1 style='font-weight:500'>3. Encryption process of redemption code:</h1>
 * <ol type='a' style='padding: 0 15px'>
 * <li>First use the coupon id to calculate the freshness value f</li>
 * <li>Splice f and serial number s to get the payload</li>
 * <li>Then use f as the corner mark and select one group from the 16 groups of weighted code tables prepared in advance.</li>
 * <li>Perform a weighted calculation on the payload to obtain the check code c</li>
 * <li>Use the last 4 digits of c as a subscript to select a key from the XOR key table prepared in advance: key</li>
 * <li>XOR the payload with the key as the new payload2</li>
 * <li>Then splice the redemption code plain text: f (4 digits) + payload2 (36 digits)</li>
 * <li>Use Base32 to transcode ciphertext and generate redemption code</li>
 * </ol>
 * <h1 style='font-weight:500'>4. Decryption process of redemption code:</h1>
 * <ol type='a' style='padding: 0 15px'>
 * <li>First, use Base32 to decode the redemption code and obtain the plaintext value num.</li>
 * <li>Take the high 14 bits of num to get c1, take the low 36 bits of num to get the payload</li>
 * <li>Use the last 4 digits of c1 as a subscript to select a key from the XOR key table prepared in advance: key</li>
 * <li>XOR the payload with the key as the new payload2</li>
 * <li>Using the encryption algorithm, use payload2 and s1 to calculate the new check code c2, compare c1 and c2, if they are consistent, it passes</li>
 * </ol>
 */
public class CodeUtil {
    /**
     * XOR key table for final data obfuscation
     */
    private final static long[] XOR_TABLE = {
            61261925471L, 61261925523L, 58169127203L, 64169927267L,
            64169927199L, 61261925629L, 58169127227L, 64169927363L,
            59169127063L, 64169927359L, 58169127291L, 61261925739L,
            59169127133L, 55139281911L, 56169127077L, 59169127167L
    };
    /**
     * Offset number of fresh values
     */
    private final static int FRESH_BIT_OFFSET = 32;
    /**
     * The number of offset digits of the check code
     */
    private final static int CHECK_CODE_BIT_OFFSET = 36;
    /**
     *Mask of fresh value, 4 bits
     */
    private final static int FRESH_MASK = 0xF;
    /**
     * Mask of verification code, 14 bits
     */
    private final static int CHECK_CODE_MASK = 0b11111111111111;
    /**
     * Payload mask, 36 bits
     */
    private final static long PAYLOAD_MASK = 0xFFFFFFFFFL;
    /**
     * Serial number mask, 32 bits
     */
    private final static long SERIAL_NUM_MASK = 0xFFFFFFFFL;
    /**
     * Key table for weighted operation of serial numbers
     */
    private final static int[][] PRIME_TABLE = {
            {23, 59, 241, 61, 607, 67, 977, 1217, 1289, 1601},
            {79, 83, 107, 439, 313, 619, 911, 1049, 1237},
            {173, 211, 499, 673, 823, 941, 1039, 1213, 1429, 1259},
            {31, 293, 311, 349, 431, 577, 757, 883, 1009, 1657},
            {353, 23, 367, 499, 599, 661, 719, 929, 1301, 1511},
            {103, 179, 353, 467, 577, 691, 811, 947, 1153, 1453},
            {213, 439, 257, 313, 571, 619, 743, 829, 983, 1103},
            {31, 151, 241, 349, 607, 677, 769, 823, 967, 1049},
            {61, 83, 109, 137, 151, 521, 701, 827, 1123},
            {23, 61, 199, 223, 479, 647, 739, 811, 947, 1019},
            {31, 109, 311, 467, 613, 743, 821, 881, 1031, 1171},
            {41, 173, 367, 401, 569, 683, 761, 883, 1009, 1181},
            {127, 283, 467, 577, 661, 773, 881, 967, 1097, 1289},
            {59, 137, 257, 347, 439, 547, 641, 839, 977, 1009},
            {61, 199, 313, 421, 613, 739, 827, 941, 1087, 1307},
            {19, 127, 241, 353, 499, 607, 811, 919, 1031, 1301}
    };

    /**
     * Generate redemption code
     *
     * @param serialNum incremental serial number
     * @return redemption code
     */
    public static String generateCode(long serialNum, long fresh) {
        // 1. Calculate the fresh value
        fresh = fresh & FRESH_MASK;
        // 2. Splice payload, fresh (4 bits) + serialNum (32 bits)
        long payload = fresh << FRESH_BIT_OFFSET | serialNum;
        // 3. Calculate verification code
        long checkCode = calcCheckCode(payload, (int) fresh);
        System.out.println("checkCode = " + checkCode);
        // 4.payload performs XOR operation on large prime numbers to confuse the data
        payload ^= XOR_TABLE[(int) (checkCode & amp; FRESH_MASK)];
        // 5. Splicing the plain text of the redemption code: check code (14 bits) + payload (36 bits)
        long code = checkCode << CHECK_CODE_BIT_OFFSET | payload;
        // 6. Transcoding
        return Base32.encode(code);
    }

    private static long calcCheckCode(long payload, int fresh) {
        // 1. Get the code table
        int[] table = PRIME_TABLE[fresh];
        // 2. Generate a check code, multiply the payload by a weighted number every 4 digits, sum it up, and take the last 13 digits of the result.
        long sum = 0;
        int index = 0;
        while (payload > 0) {
            sum + = (payload & amp; 0xf) * table[index + + ];
            payload >>>= 4;
        }
        return sum & CHECK_CODE_MASK;
    }

    public static long parseCode(String code) {
        if (code == null || !code.matches(RegexConstants.COUPON_CODE_PATTERN)) {
            // Redemption code format error
            throw new BadRequestException("Invalid redemption code");
        }
        // 1.Base32 decoding
        long num = Base32.decode(code);
        // 2. Get the lower 36 bits, payload
        long payload = num & PAYLOAD_MASK;
        // 3. Get the high 14 digits, check code
        int checkCode = (int) (num >>> CHECK_CODE_BIT_OFFSET);
        // 4. XOR the load with a large prime number and parse out the original payload
        payload ^= XOR_TABLE[(checkCode & amp; FRESH_MASK)];
        // 5. Get the high 4 bits, fresh
        int fresh = (int) (payload >>> FRESH_BIT_OFFSET & amp; FRESH_MASK);
        // 6. Verification format:
        if (calcCheckCode(payload, fresh) != checkCode) {
            throw new BadRequestException("Invalid redemption code");
        }
        return payload & SERIAL_NUM_MASK;
    }

    public static void main(String[] args) {
        // define your parameters
        long serialNum = 123456; //Replace with actual serialNum value
        long fresh = 789; //replace with actual fresh value

        //Call the function that generates the redemption code
        String exchangeCode = generateCode(serialNum, fresh);

        //Print the generated redemption code
        System.out.println("Generated redemption code: " + exchangeCode);
        System.out.println(parseCode("HG9SLK6WW4"));
    }

}

RegexConstants
package com.tianji.common.constants;

import cn.hutool.core.lang.RegexPool;

public interface RegexConstants extends RegexPool {
    /**
     * Regular mobile phone number
     */
    String PHONE_PATTERN = "^1([38][0-9]|4[579]|5[0-3,5-9]|6[6]|7[0135678]|9[89])\ \d{8}$";
    /**
     * Email regular
     */
    String EMAIL_PATTERN = "^[a-zA-Z0-9_-] + @[a-zA-Z0-9_-] + (\.[a-zA-Z0-9_-] + ) + $\ ";
    /**
     * Password regularity. 6~32 digits of letters, numbers, and underscores
     */
    String PASSWORD_PATTERN = "^\w{4,24}$";
    /**
     * Regular username. 6~32 digits of letters, numbers, and underscores
     */
    String USERNAME_PATTERN = "^\w{4,32}$";
    /**
     * Verification code is regular, 6 digits or letters
     */
    String VERIFY_CODE_PATTERN = "^[a-zA-Z\d]{6}$";

    /**
     * Coupon redemption code template
     */
    String COUPON_CODE_PATTERN = "^[23456789ABCDEFGHJKLMNPQRSTUVWXYZ]{8,10}$";
}

BadRequestException
package com.tianji.common.exceptions;

import lombok.Getter;

@Getter
public class BadRequestException extends CommonException{
    private final int status = 400;

    public BadRequestException(String message) {
        super(400, message);
    }

    public BadRequestException(int code, String message) {
        super(code, message);
    }

    public BadRequestException(int code, String message, Throwable cause) {
        super(code, message, cause);
    }
}