3
\$\begingroup\$

I'm trying to make an ID generator that generates 64 bit longs. The IDs should be globally unique even between two offline machines. This is the same idea as UUID (GUID), but UUID is 128 bit long and contains redundant (constant) bits (eg. it uses the millisecs passed since the year 1980 and has 5-8 versioning bits). I could use either the least or most significant 64 bits of a UUID, but because it contains these constant bits, it may not be unique enough.

So I made my own logic. It's important that it has to run everywhere, so I can't use MAC address, because it's not always accessible (eg. on Android). What do you think of my code?

public class UID {

private static long swRndVal;
private static Random random = new Random();
private static final long mstsigMask = 0b11111111_00000000_00000000_00000000_00000000_00000000_00000000_00000000L;
private static final long middleMask = 0b00000000_11111111_11111111_11111111_11111111_11111111_11111111_11111111L;
private static final long lstsigMask = 0b00000000_00000000_00000000_00000000_00000000_00001111_11111111_11111111L;

static {
    String s1 = System.getProperty("os.arch", "");
    String s2 = System.getProperty("os.version", "");
    String s3 = System.getProperty("java.vm.version", "");
    String s4 = System.getProperty("java.class.version", "");
    Random rand1 = new Random((s1+s2+s3+s4).hashCode());
    Random rand2 = new Random();
    swRndVal = rand1.nextLong() ^ rand2.nextLong();
}

public static long getUniqueLong() {
    //8 bits of random, 36 bits of millis (~800 days), 20 bits of nanos (~1ms)
    return ((random.nextLong() & mstsigMask) | (System.currentTimeMillis() & middleMask) | (System.nanoTime() & lstsigMask)) ^ swRndVal;
}
}
\$\endgroup\$
3
\$\begingroup\$

I would just use SecureRandom#nextLong(). SecureRandom will seed itself and shouldn't be the same between two similar computers at the same time. Also, it uses more bits of state than Random (128 vs 48).

I don't know exactly what computers you'll be running this on, but if it's something like a cluster of servers they'll probably have the exact same s1/s2/s3/s4. If they happen to start at the same time (plausible if two processes on two cores are launched by a parents at the same time), then that only leaves the 48 bits of random state.

If you use SecureRandom, you can just call it and immediately get a 64 bit UUID that will have as few collisions as you can possibly guarantee with two offline computers.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ SecureRandom is a good idea, I think I'll use it instead of random and rand2. But I think it's a good idea to leave some machine-specific info in it. It won't help in cluster scenarios, but it won't really hurt either. And in any other situation it can help. Currently I plan to use it in an Android app that will eventually synchronize back to a server. Also I intend to use this mostly for small projects, so I wouldn't worry that much about collision. For larger projects I would probably find a way to include the MAC address. \$\endgroup\$ – Ádám Bozzay May 18 at 13:18
  • 1
    \$\begingroup\$ It's a bit counterintuitive, but adding something machine specific won't help unless you can guarantee that it will be unique (i.e. MAC address) and separate it from the random value. If you don't separate it from the random value (e.g. by XORing it in), it adds nothing as the result has the same chance of collisions. If you separate it from the random value (by masking off the random value and ORing it in), then it's beneficial if you can guarantee uniqueness and detrimental otherwise, as it removes entropy. \$\endgroup\$ – Leo Adberg May 19 at 2:37
  • \$\begingroup\$ That's right, I didn't see that. So I should ditch the machine specific part, because it would take away too much random state if I separated it from the rest. But I can still see that adding the time is useful. I would use this for an application where the IDs are generated in about 5pcs batch and at least a few seconds are passed between batches. Do you think it's a better idea to leave out the nanos and use 28 bits of random instead? \$\endgroup\$ – Ádám Bozzay May 20 at 7:36
0
\$\begingroup\$

It's a terrible idea to use only 64 bits for a "globally unique ID". As soon as you generate \$2^{32}\$ IDs with that, the probability of a collision is 50 percent, and \$2^{32}\$ can be achieved in less than a day by a single computer.

I also cannot follow your reasoning:

UUID uses 128 bits in the encoded value, and 6 of them are fixed when using random UUIDs. This means 122 random bits remain. That's not enough for me, therefore I use my own scheme that has only 64 bits of randomness.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ That is nothing like my reasoning. I said that I must have 64 bit ids, 128 bit is out of question. So I could take a UUID and split it to 2 pieces. Java has two methods for this: getMostSignificantBits() and getLeastSignificantBits(). My reasoning is that neither of these have 64 bits of randomness in a certain timeframe. I agree that using a UUID as it is is better than my method, but using half of it is worse. \$\endgroup\$ – Ádám Bozzay May 18 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.