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

我移植了 樱花 到Java中,它工作得很好。然而,我希望生成的不是 8 位数的数字,而是 12 位数的唯一数字。原来的 port 使用 16 位 machineId. 因为我们至少有2个数据中心,但不限于,我添加了8位的数据中心 – 使用IP地址的第二个八位组。我调整了所有比特长度的设置,无法生成12位数的数字。是否有受sonyflake的启发的算法?Twitters雪花 生成独特的12位数字,它使用16位的 machineId 和8位 dataCenterId

由于公司政策,我不能在这里发布我的原始Java移植。

EDIT: 这是我想出来的. 然而, 它没有生成 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);
        }
    }
}

解决方案:

如果你的意思是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人)39 所以不到1012).

  • 如果您可以接受数字中的前导零,那么请按以下方式进行格式设置 x 变成一个12位数字。String.format("%012d", x).

  • 如果你不能接受数字中的前导零,那么就在数字中加上100000000000(1011)至 x. 由于 x 小于239小于900000000000,这将产生一个12位数字。


您正在随机生成工人ID。一般来说,随机数本身不足以确保唯一性。您需要某种方法来检查您生成的每个工人 ID 的唯一性。一旦你这样做了,每个workerdatacenter对将是唯一的。因此,每台机器只需要生成一个机器唯一性的号码,在你的情况下,这个号码将是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。

给TA打赏
共{{data.count}}人
人已打赏
解决方案

Dokku 编译错误 - django.core.exceptions.ImproperlyConfigured: 加载psycopg2模块时出错,没有名为'psycopg2'的模块。没有名为'psycopg2'的模块。

2022-4-22 1:00:17

解决方案

在 Cloudformation 模板中,我如何在 IoT Rule 中引用动态生成的 Lambda 函数 ARN?

2022-4-22 1:00:19

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索