CODEWITHSUNDEEP
javauniqueidentifier
James P.
James P.

Reputation: 19607

Enforcing a unique id in a class

Just for the sake of a thought exercise, how could the uniqueness of an attribute be enforced for each instance of a given class ?

Uniqueness here can be defined as being on a single JVM and within a single user session.

This is at Java-level and not to do with databases, the main purpose being to verify if a collision has occurred.

The first obvious step is to have a static attribute at class level.

How should this problem be tackled ? What solutions/approaches might already exist ?

Upvotes: 3

Views: 831

Answers (3)

EIIPII
EIIPII

Reputation: 1871

UUID is a good solution, but UUID.randomUUID() on the backend use method:

synchronized public void SecureRandom.nextBytes(byte[] bytes)

So this is slow: threads lock a single monitor object in each id generation operation.

The AtomicInteger is better, because it loops in a CAS operation. But again, for each id generation operation a synchronization operation must be done.

In the solution below, only prime numbers generation is synchronized. Synchronization is on a volatile int, so is fast and thread-safe. Having a set of primes, many ids are generated in a iteration.

Fixed number of threads

Edit: Solution for fixed number of thread

I you know apriory how many threads will use the Id generation, then You can generate IDs with values 

Id = I mod X + n*X

Where X is the number of threads, I is the thread number, and N is a local variable that is incremented for each Id generation. The code for this solution is really simple, but it must be integrated with the hole program infrastructure.

Ids generated from primes

The idea is to generate the ids as factors of prime numbers id = p_1^f1 * p_2^f2 * p_2^f3 * ... * p_n^fn

We use different prime numbers in each thread to generate different sets of ids in each thread.

Assuming that we use primes (2,3,5), the sequence will be:

2, 2^2, 2^3, 2^4, 2^5,..., 2^64

Then, when we see that a overflow will be generated, we roll the factor to the next prime:

3, 2*3 , 2^2*3, 2^3*3, 2^4*3, 2^5*3,..., 2^62*3

and next

3^2, 2*3^2 , 2^2*3^2, .....

Generation class

Edit: primer order generation must be done on AtomicInteger to be correct

Each instance of class IdFactorialGenerator will generate different sets of ids.

To have a thread save generation of Ids, just use ThreadLocal to have a per-thread instance setup. Synchronization is realized only during prime number generation.

package eu.pmsoft.sam.idgenerator;

public class IdFactorialGenerator {
    private static AtomicInteger nextPrimeNumber = 0;

    private int usedSlots;
    private int[] primes = new int[64];
    private int[] factors = new int[64];
    private long id;
    public IdFactorialGenerator(){
        usedSlots = 1;
        primes[0] = Sieve$.MODULE$.primeNumber(nextPrimeNumber.getAndAdd(1));
        factors[0] = 1;
        id = 1;
    }

    public long nextId(){
        for (int factorToUpdate = 0; factorToUpdate < 64; factorToUpdate++) {
            if(factorToUpdate == usedSlots) {
                factors[factorToUpdate] = 1;
                primes[factorToUpdate] = Sieve$.MODULE$.primeNumber(nextPrimeNumber.getAndAdd(1));
                usedSlots++;
            }
            int primeToExtend = primes[factorToUpdate];
            if( primeToExtend < Long.MAX_VALUE / id) {
                // id * primeToExtend < Long.MAX_VALUE
                factors[factorToUpdate] = factors[factorToUpdate]*primeToExtend;
                id = id*primeToExtend;
                return id;
            } else {
                factors[factorToUpdate] = 1;
                id = 1;
                for (int i = 0; i < usedSlots; i++) {
                    id = id*factors[i];
                }
            }
        }
        throw new IllegalStateException("I can not generate more ids");
    }
}

To get the prime numbers I use a implementations on scala provided here in the problem 7: http://pavelfatin.com/scala-for-project-euler/

object Sieve {

  def primeNumber(position: Int): Int = ps(position)

  private lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i =>
    ps.takeWhile(j => j * j <= i).forall(i % _ > 0))
}

Upvotes: 2

Evgeniy Dorofeev
Evgeniy Dorofeev

Reputation: 135992

If you care about performance, here is a thread safe, fast (lock-free) and collision-free version of unique id generation

    public class Test {
        private static AtomicInteger lastId = new AtomicInteger();
        private int id;

        public Test() {
            id = lastId.incrementAndGet();
        }
...

Upvotes: 4

vijay
vijay

Reputation: 2694

Simply use the UUID class in Java http://docs.oracle.com/javase/6/docs/api/java/util/UUID.html. Create a field of the type UUID in the classes under inspection and initialize this field in the constructor.

public class Test  {
   public UUID id;
   public Test() {
      id = UUID.randomUUID();
   }
}

When it comes time for detecting collisions, simply compare the string representations of the UUIDs of the objects like this ...

Test testObject1 = new Test();
Test testObject2 = new Test();
boolean collision = testObject1.id.toString().equals(testObject2.id.toString());

Or more simply use the compareTo() method in the UUID class ...

boolean collision = testObject2.id.compareTo(testObject1.id) == 0 ? true : false;

0 means that the ids are the same. +1 and -1 when they are not equal.

Merit: universally unique (can be time based, random) and hence should takes care of threading issues (some one should confirm this ... this is based off the best of my knowledge). more information here and here.

To make it thread-safe refer to this question on SO is java.util.UUID thread safe?

Demerit: will require a change in the structure of the classes under inspection, i.e. the id field will have to added in the source of the classes themselves. which might or might not be convenient.

Upvotes: 3

Related Questions