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

Question

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

注意:由于公司政策，我无法在此处发布我的原始 Java 端口。

编辑:这是我想出的。但是，它不是生成 12 位十进制数，而是生成 10 或 11 位数字。我可以进行哪些更改才能使其始终返回 12 位十进制数？我知道我需要更改序列并重新计算时间。不过，我目前想专注于生成 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 Exception("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);
        }
    }
}

Answer 1

如果您的意思是 12 位十进制数字，那么您可以使用最多 39 位的数字(40 位除了可以表示 12 位数字外，还可以表示 13 位数字)。

如果您采用 16 位作为机器 ID，8 位作为数据中心 ID，则只剩下 15 位作为该机器 ID 的唯一部分(因此每台机器只有 32768 个唯一数字。)数字，您可以选择按顺序分配数字，而不是随机分配数字。

如果您指的是 12 个十六进制(以 16 为基数)数字，那么情况会大大改善:16 位组成 4 位数字，8 位组成另外两个数字，剩下 6 位以 16 为基数的数字ID 的唯一部分，或 16,777,216 个不同的数字(24 位)。有了这么多的数字，您有几种不同的选择让每台机器分配这些数字。您可以按顺序执行此操作，也可以随机执行此操作(使用 java.security.SecureRandom，而不是 java.util.Random )，或使用分辨率为 10 毫秒的时间戳，如 Sonyflake 中所示。

<小时/>

您的问题似乎不是如何生成 12 位唯一 ID，而是如何格式化数字以恰好适合 12 位数字。那么你有两个选择。假设您有一个 39 位整数 x (小于 2³⁹，因此小于 10¹²)。

• 如果您可以接受数字中的前导零，请执行以下操作来格式化 x转换为 12 位数字:String.format("%012d", x) .

• 如果您不能接受数字中的前导零，请将 100000000000 (10¹¹) 添加到 x 。自 x小于 2³⁹，即小于 900000000000，这将得到一个 12 位数字。

<小时/>

您正在随机生成工作人员 ID。一般来说，随机数本身不足以确保唯一性。您需要某种方法来检查您生成的每个工作 ID 的唯一性。完成此操作后，每个工作程序/数据中心对都将是唯一的。因此，每台机器只需要生成一个机器唯一的数字，在您的情况下，该数字的长度为 25 位。有几种方法可以做到这一点:

• 最简单的方法是生成随机数或基于时间的数字(在示例中使用所有 25 位)并使用哈希集检查数字的唯一性(例如 java.util.HashSet )。如果号码已生成，请使用新号码重试。 (使用位集(例如 java.util.BitSet )或压缩位图(例如“咆哮位图”)可能会比哈希表更节省内存。)

• 另一种方法是使用哈希表，其中随机/基于时间的数字作为键，序列 ID 作为值。当需要生成唯一编号时，请执行以下操作:

  1. 生成X 、随机数或基于时间的数字。
  2. 检查某个键是否等于X在哈希表中找到。
  3. 如果该键不存在，则在表中创建一个新条目，其中键为 X值为 0。唯一编号为 X序列号为 0。停止。
  4. 如果该键存在，并且与该键关联的值小于 255，则该值加 1。唯一编号是X以及该值的序列号。停下来。
  5. 如果该键存在，并且与该键关联的值等于或大于 255，请转到步骤 1。