How to generate unique positive Long using UUID

Question

I have a requirement to generate unique Long ids for my database primary key column.

I thought i can use UUID.randomUUID().getMostSignificantBits() but sometimes its generating some negative long also which is problem for me.

Is it possible to generate only positive long from UUID ?There will be like billions of entries so i want that each generated key must be unique.

Answer 1

UUID.randomUUID().getMostSignificantBits() & Long.MAX_VALUE

The reason why this works is, when you do bitwise & with 1 it allows the same digit to pass as it is and when you do bitwise & with 0 it blocks it and result is 0. Now, Long.MAX_Value in binary is

0111111111111111111111111111111111111111111111111111111111111111 

this is 0 followed by 63 1s (total is 64 bits, it's long in java)

So when you bitwise & a number X with this above number then you will get the same number X except that the leftmost bit is now turned into a zero. Which means you've only changed the sign of that number and not the value.

Answer 2

This code is inspired by @Daniel Nuriyev's answer. But, instead of using nano-time, a counter (or discriminator as I've seen it called) is used when collisions occur in the same millisecond:

private static long previousTimeMillis = System.currentTimeMillis();
private static long counter = 0L;

public static synchronized long nextID() {
    long currentTimeMillis = System.currentTimeMillis();
    counter = (currentTimeMillis == previousTimeMillis) ? (counter + 1L) & 1048575L : 0L;
    previousTimeMillis = currentTimeMillis;
    long timeComponent = (currentTimeMillis & 8796093022207L) << 20;
    return timeComponent | counter;
}

This method generates a semi-unique ID by packing a millisecond timestamp-component together with a counter-component. The algorithm allows for roughly a million (or 1048575 to be exact) unique IDs to be generated in the same millisecond before collisions start to occur. Unique IDs are generated until the year 2248 at which point it will wrap around and start at 0 again.

The ID-generation is done as follows:

Milliseconds since epoch:

|0|000000000000000000000010110111101111100110001001111100101011111|

Bitwise AND with (8796093022207L):

|0|000000000000000000001111111111111111111111111111111111111111111|

to give you the 43 least significant bits as the time-component.

Then shift this to the left by 20 bits to give you:

|0|0010110111101111100110001001111100101011111|00000000000000000000|

Bitwise OR with 20 bits of counter (e.g. if counter is 3) to give you:

|0|0010110111101111100110001001111100101011111|00000000000000000101|

Only 43 bits (and not 44) are used for the time-component as we do not want to allow the most significant bit (which is the sign of the number) to be changed. This results in only positive IDs to be generated.

Answer 3

I want to do it in application side because if i will do it in database side i have to fire one more query again to get the id of the row..and i want to avoid that.

NO! You can use an AUTOINCREMENT primary key, and in JDBC retrieve the generated key with the INSERT.

String insertSQL = "INSERT INTO table... (name, ...)"
        + " VALUES(?, ..., ?)";
try (Connection connection = getConnection();
        PreparedStatement stmt = connection.prepareStatement(insertSQL,
                Statement.RETURN_GENERATED_KEYS)) {
    stmt.setString(1, ...);
    stmt.setInt(2, ...);
    stmt.setBigDecimal(3, ...);
    ...
    stmt.executeUpdate();

    ResultSet keysRS = stmt.getGeneratedKeys();
    if (keysRS.next()) {
        long id = keysRS.getInt(1);
    }
}

This is more efficient, and definitely easier, and safer. UUID are 128 bits. Taking just 64 bits reduces its uniqueness. So at least subjectively not 100% perfect. At least XOR (^) both long parts.

Answer 4

I just came across this solution. I am for the time being trying to understand the solution.It says Java implementation of twitter snowflake. 64 bit sequential ID generator based on twitter snowflake ID generation algorithm.

https://github.com/Predictor/javasnowflake

Any suggestions are welcome.

Answer 5

As the others have written, long does not have enough space for a unique number. But in many cases a number may be unique enough for a specific use. For example, a timestamp with the nanosecond precision is often good enough. To get it, shift the current milliseconds 20 bits left to allocate space for nanoseconds and then overlay it with the nanoseconds:

(System.currentTimeMillis() << 20) | (System.nanoTime() & ~9223372036854251520L);

The nano & ~9223372036854251520L part takes the current nanoseconds and sets the first 44 bytes to 0, leaving only the right 20 bits which represent nanoseconds up to one millisecond (999999 nanos) It is the same as:

nanoseconds & ~1111111111111111111111111111111111111111111100000000000000000000

Side note: nanoseconds should not be used to represent the current time because their starting point is not fixed in time and because they are recycled when they reach the maximum.

You can use any other bit manipulation. It is usually good to take into account the current time and something else such as the current thread id, process id, ip.

Answer 6

Take a look at http://commons.apache.org/sandbox/commons-id//index.html It has a LongGenerator that can give you exactly what you need.

In addition if you are using Hibernate then you can ask it to generate IDs for you (it has several algorithms you can choose from), in if not you can just take a look at their implementation for example http://grepcode.com/file/repo1.maven.org/maven2/hibernate/hibernate/2.1.8/net/sf/hibernate/id/TableHiLoGenerator.java#TableHiLoGenerator)