Sequential Guid in Java

Considering the post I've m开发者_运维知识库ade about the sequential guid performance on Microsoft.NET framework (see What are the performance improvement of Sequential Guid over standard Guid?) does somebody have a proper, sure, fast and well working Java implementation of the same algorithm implemented in the Windows DLLs?

Regards Massimo

See this article: http://www.informit.com/articles/article.aspx?p=25862&seqNum=7 (linked to Page 7).

It contains an algorithm for what the author refers to as "COMB" Guids; I reproduce his code (SQL) below:

SET @aGuid = CAST(CAST(NEWID() AS BINARY(10)) 
+ CAST(GETDATE() AS BINARY(6)) AS UNIQUEIDENTIFIER)

Trivial to convert this to Java, or your desired language. The obvious underlying principle is to make the date a component of the Guid. The entire article is a good read, as he does a nice analysis of the performance of the various approaches.

For sequential UUIDs, you are looking for a version 1 UUID. Java UUID Generator project seems to work quite well and is pretty easy to use:

Generators.timeBasedGenerator().generate().toString()

This page links to a couple of version 1 (sequential) UUID implementations in Java: http://johannburkard.de/blog/programming/java/Java-UUID-generators-compared.html

This utility class that generates COMB UUIDs, conceived by Jimmy Nilsson in this article: http://www.informit.com/articles/article.aspx?p=25862. Feel free to use and share.

package your.package.name;

import java.security.SecureRandom;
import java.util.Random;
import java.util.UUID;

/**
 * Utility class that creates COMB UUIDs.
 * 
 * The COMB UUIDs combine the creation time and random bytes.
 * 
 * The PREFIX or SUFFIX has 6 bytes and corresponds to the milliseconds since
 * 1970-01-01T00:00:00Z (Unix epoch).
 * 
 * For RFC-4122 compliance, it uses the version number 4.
 * 
 * Read: The Cost of GUIDs as Primary Keys
 * http://www.informit.com/articles/article.aspx?p=25862
 * 
 */
public abstract class CombUuidCreator {

    private static final int RANDOM_VERSION = 4;

    /**
     * Returns a prefix COMB UUID.
     * 
     * It uses a thread local {@link SecureRandom}.
     * 
     * @return a random-based UUID
     */
    public static UUID getPrefixComb() {
        return getPrefixComb(SecureRandomLazyHolder.THREAD_LOCAL_RANDOM.get());
    }

    /**
     * Returns a prefix COMB UUID.
     * 
     * It uses any instance of {@link Random}.
     * 
     * @return a random-based UUID
     */
    public static UUID getPrefixComb(Random random) {
        return getCombGuid(random, /* prefix = */true);
    }

    /**
     * Returns a suffix COMB UUID.
     * 
     * It uses a thread local {@link SecureRandom}.
     * 
     * @return a random-based UUID
     */
    public static UUID getSuffixComb() {
        return getSuffixComb(SecureRandomLazyHolder.THREAD_LOCAL_RANDOM.get());
    }

    /**
     * Returns a suffix COMB UUID.
     * 
     * It uses any instance of {@link Random}.
     * 
     * @return a random-based UUID
     */
    public static UUID getSuffixComb(Random random) {
        return getCombGuid(random, /* prefix = */false);
    }

    /**
     * Returns prefix or suffix COMB UUID.
     * 
     * It uses any instance of {@link Random}.
     * 
     * @return a random-based UUID
     */
    private static UUID getCombGuid(Random random, boolean prefix) {

        long msb = 0;
        long lsb = 0;

        // (3) set bits randomly
        final byte[] bytes = new byte[16];
        random.nextBytes(bytes);
        final long rand0 = (bytes[8] << 8) | (bytes[9] & 0xff);
        final long rand1 = toNumber(bytes, 0, 8);

        // Insert the prefix in the MSB
        final long timestamp = System.currentTimeMillis();
        if (prefix) {
            msb = (rand0 & 0x000000000000ffffL) | ((timestamp & 0x0000ffffffffffffL) << 16);
            lsb = rand1;
        } else {
            msb = rand1;
            lsb = (rand0 << 48) | (timestamp & 0x0000ffffffffffffL);
        }

        // Apply version and variant bits (required for RFC-4122 compliance)
        msb = (msb & 0xffffffffffff0fffL) | (RANDOM_VERSION & 0x0f) << 12; // apply version bits
        lsb = (lsb & 0x3fffffffffffffffL) | 0x8000000000000000L; // apply variant bits

        // Return the UUID
        return new UUID(msb, lsb);
    }

    private static long toNumber(final byte[] bytes, final int start, final int length) {
        long result = 0;
        for (int i = start; i < length; i++) {
            result = (result << 8) | (bytes[i] & 0xff);
        }
        return result;
    }

    // Holds thread local secure random
    private static class SecureRandomLazyHolder {
        static final ThreadLocal<Random> THREAD_LOCAL_RANDOM = ThreadLocal.withInitial(SecureRandom::new);
    }

    /**
     * For tests!
     */
    public static void main(String[] args) {

        Random random = new Random();

        System.out.println("// Prefix COMB using thread local `java.security.SecureRandom` (DEFAULT)");
        System.out.println("CombUuidCreator.getPrefixComb()");
        System.out.println();
        for (int i = 0; i < 5; i++) {
            System.out.println(" " + CombUuidCreator.getPrefixComb());
        }
        System.out.println("|----prefix---|----------------------|");

        System.out.println();
        System.out.println("// Prefix COMB using `java.util.Random` (FASTER)");
        System.out.println("CombUuidCreator.getPrefixComb(new Random())");
        System.out.println();
        for (int i = 0; i < 5; i++) {
            System.out.println(" " + CombUuidCreator.getPrefixComb(random));
        }
        System.out.println("|----prefix---|----------------------|");

        System.out.println();
        System.out.println("// Suffix COMB using thread local `java.security.SecureRandom` (DEFAULT)");
        System.out.println("CombUuidCreator.getSuffixComb()");
        System.out.println();
        for (int i = 0; i < 5; i++) {
            System.out.println(" " + CombUuidCreator.getSuffixComb());
        }
        System.out.println("|-----------------------|---suffix---|");

        System.out.println();
        System.out.println("// Suffix COMB using `java.util.Random` (FASTER)");
        System.out.println("CombUuidCreator.getSuffixComb(new Random())");
        System.out.println();
        for (int i = 0; i < 5; i++) {
            System.out.println(" " + CombUuidCreator.getSuffixComb(random));
        }
        System.out.println("|-----------------------|---suffix---|");
    }
}

This is the output:

// Prefix COMB using thread local `java.security.SecureRandom` (DEFAULT)
CombUuidCreator.getPrefixComb()

 0173861f-4445-459b-87d2-39a970520fff
 0173861f-4445-465d-a216-7b13d86c83a1
 0173861f-4445-4c67-b75e-3845c2911420
|----prefix---|----------------------|

// Prefix COMB using `java.util.Random` (FASTER)
CombUuidCreator.getPrefixComb(new Random())

 0173861f-4445-44f6-bfa4-e272c9c369aa
 0173861f-4445-446e-baf2-6db6ab808094
 0173861f-4445-40e8-a452-184dcf9736fd
|----prefix---|----------------------|

// Suffix COMB using thread local `java.security.SecureRandom` (DEFAULT)
CombUuidCreator.getSuffixComb()

 726b6717-001a-4317-9a9b-0173861f4446
 dfdce2d2-7517-4a3f-9f3d-0173861f4446
 a7fd6236-8065-4395-b49a-0173861f4446
|-----------------------|---suffix---|

// Suffix COMB using `java.util.Random` (FASTER)
CombUuidCreator.getSuffixComb(new Random())

 41a6a4cd-eb4c-410f-8eb2-0173861f4446
 7c0a315e-54de-476a-a2a8-0173861f4446
 4e9ddf9e-ac07-4cf3-bf3f-0173861f4446
|-----------------------|---suffix---|

You can also use the uuid-creator library. See these examples:

// Create a prefix COMB UUID
UUID uuid = UuidCreator.getPrefixComb();

// Create a suffix COMB UUID
UUID uuid = UuidCreator.getSuffixComb();

Project page: https://github.com/f4b6a3/uuid-creator

I use this to generate UUIDs (Universally Unique IDs) for my DTOs which act as surrogate keys for transient collections. Don't know if it's the same thing, but it may point you in the right direction.

import java.util.UUID;
...
    private String uuid=null;
...
    protected String getUuid() {
        synchronized (this) {
          if (null ==uuid) {
            uuid = UUID.randomUUID().toString();
          }
          return uuid;
        }
      }