java - 12位唯一分布式随机数发生器

Question

我将sonyflake移植到 Java，它运行良好。但是，我希望生成 12 位唯一数字，而不是生成 8 位数字。原始端口使用 16 位machineId. 因为我们至少有 2 个数据中心，但不限于，我为数据中心添加了 8 位 - 使用 IP 地址的第二个八位字节。我调整了位长的所有设置，无法生成 12 位数字。是否有受 sonyflake 或 Twitters Snowflake启发的算法来生成使用 16 位machineId和 8 位的唯一 12 位数字dataCenterId？

注意：由于公司政策，我不能在这里发布我原来的 Java 端口。

编辑：这就是我想出的。但是，它不会生成 12 位十进制数字，而是生成 10 位或 11 位数字。我可以对其进行哪些更改以使其始终返回 12 位十进制数？我知道我需要更改sequence并重新计算时间。但是，我目前想专注于生成 12 位十进制数。

public class Demo {

    /// 17 time + 4 dc + 10 machine + 8 sequence

    private static final int BIT_LEN_TIME = 17;
    private static final long BIT_WORKER_ID = 10L;
    private static final long BIT_LEN_DC = 4L;
    private static final long BIT_LEN_SEQUENCE = 8L;

    private static final int MAX_WORKER_ID = (int) (Math.pow(2, BIT_WORKER_ID) - 1);
    private static final long MAX_SEQUENCE = (int) (Math.pow(2, BIT_LEN_SEQUENCE) - 1);

    private static final double FLAKE_TIME_UNIT = 1e7; // nsec, i.e. 10 msec
    private static final double LEN_LIMIT = 1e11;
    private static final int START_SEQ = 0;

    private final ReentrantLock mutex = new ReentrantLock();

    private final Instant startInstant;
    private final long startTime;
    private final long dc;
    private long sequence;
    private long lastElapsedTime;
    private long worker;

    public Demo(Instant startInstant) {
        Objects.requireNonNull(startInstant, "startInstant cannot be null");
        if (startInstant.isBefore(Instant.EPOCH) || startInstant.isAfter(Instant.now())) {
            throw new EverestFlakeException("Base time should be after UNIX EPOCH, or before current time.");
        }

        this.startInstant = startInstant;
        this.startTime = this.toEverestFlakeTime(startInstant);
        this.sequence = START_SEQ;
        this.dc = this.msb(this.getDcId()); // 4 bits at most
        this.worker = this.workerId() & ((1 << BIT_WORKER_ID) - 1); // 10 bits at most
    }

    public long next() {
        long currentElapsedTime = this.currentElapsedTime(this.startTime);

        mutex.lock();
        long time = currentElapsedTime & ((1 << BIT_LEN_TIME) - 1); // 17 bits at most
        if (this.sequence == MAX_SEQUENCE) {
            this.sequence = START_SEQ;
            System.out.println("time = " + time);
            sleepMicro(currentElapsedTime - this.lastElapsedTime);
            time = this.currentElapsedTime(this.startTime) & ((1 << BIT_LEN_TIME) - 1);
            System.out.println("time = " + time);
        } else {
            // less than 15000
            if((currentElapsedTime - this.lastElapsedTime) < 0x3a98) {
                sleepMicro(currentElapsedTime - this.lastElapsedTime);
                time = this.currentElapsedTime(this.startTime) & ((1 << BIT_LEN_TIME) - 1);
            }
            this.sequence += (START_SEQ + 1) & MAX_SEQUENCE;
        }

        long id = (time << BIT_LEN_TIME) |
                (worker << BIT_WORKER_ID) |
                (dc << BIT_LEN_DC) |
                (sequence << BIT_LEN_SEQUENCE);
        id += LEN_LIMIT;
        this.lastElapsedTime = currentElapsedTime;
        mutex.unlock();

        return id;
    }

    private void sleepNano(long sleepTime) {
        try {
            System.out.println("nano sleeping for: " + sleepTime);
            TimeUnit.NANOSECONDS.sleep(sleepTime);
        } catch (Exception e) {
            //
        }
    }

    private void sleepMicro(long sleepTime) {
        try {
            System.out.println("micro sleeping for: " + sleepTime);
            TimeUnit.MICROSECONDS.sleep(sleepTime/100);
        } catch (Exception e) {
            //
        }
    }

    private long toEverestFlakeTime(Instant startInstant) {
        return unixNano(startInstant);
    }

    private long unixNano(Instant startInstant) {
        return NanoClock.systemUTC().nanos(startInstant);
    }

    private long currentElapsedTime(long startTime) {
        return this.toEverestFlakeTime(NanoClock.systemUTC().instant()) - startTime;
    }

    private long msb(long n) {
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        n >>>= 1;
        n += 1;
        return n;
    }

    private int workerId() {
        return new SecureRandom().nextInt(MAX_WORKER_ID);
    }

    private int getDcId() {
        try {
            Socket socket = new Socket();
            socket.connect(new InetSocketAddress("google.com", 80));
            byte[] a = socket.getLocalAddress().getAddress();
            socket.close();
            return Byte.toUnsignedInt(a[1]);
        } catch (Exception e) {
            String message = "Failed to process machine id.";
            throw new EverestFlakeException(message, e);
        }
    }
}

标签： javarandom

Answer 1

If you mean 12 decimal digits, then you can use a number up to 39 bits (40 bits can represent 13-digit in addition to 12-digit numbers).

If you take 16 bits for the machine ID, and 8 bits for the data center ID, that leaves only 15 bits for the unique portion of the ID for that machine (so only 32768 unique numbers per machine.) With so few numbers, you can choose to assign the numbers sequentially rather than randomly.

If you mean 12 hexadecimal (base-16) digits, then the situation improves considerably: 16 bits makes up 4 digits and 8 bits makes up another two, leaving 6 base-16 digits for the unique portion of the ID, or 16,777,216 different numbers (24 bits). With this many numbers, you have several different choices to have each machine assign these numbers. You can do so sequentially, or at random (using java.security.SecureRandom, not java.util.Random), or using a timestamp with 10 ms resolution, as in Sonyflake.

---

It appears your question is less about how to generate a 12-digit unique ID than it is about how to format a number to fit in exactly 12 digits. Then you have two options. Assume you have a 39-bit integer x (less than 2³⁹ and so less than 10¹²).

• If you can accept leading zeros in the number, then do the following to format x to a 12-digit number:String.format("%012d", x).

• If you can't accept leading zeros in the number, then add 100000000000 (10¹¹) to x. Since x is less than 2³⁹, which is less than 900000000000, this will result in a 12-digit number.

---

You are generating worker IDs at random. In general, random numbers are not enough by themselves to ensure uniqueness. You need some way to check each worker ID you generate for uniqueness. Once you do so, each worker/datacenter pair will be unique. Thus, each machine is required only to generate a machine-unique number, which will be 25 bits long in your case. There are several ways to do so:

• The simplest way is to generate a random number or time-based number (using all 25 bits in your example) and check the number for uniqueness using a hash set (e.g., java.util.HashSet). If the number was already generated, try again with a new number. (Instead of a hash table, it may be more memory-efficient to use a bit set (e.g., java.util.BitSet) or a compressed bitmap (e.g., a "roaring bitmap").)

• Another way is to use a hash table with random/time-based numbers as keys and sequence IDs as values. When a unique number needs to be generated, do the following:

  1. Generate X, a random number or time-based number.
  2. Check whether a key equal to X is found in the hash table.
  3. If the key does not exist, create a new entry in the table, where the key is X and the value is 0. The unique number is X and a sequence number of 0. Stop.
  4. If the key exists, and the value associated with that key is less than 255, add 1 to the value. The unique number is X and a sequence number of that value. Stop.
  5. If the key exists, and the value associated with that key is 255 or greater, go to step 1.