Skip to main content

Id generation from prime numbers factorization

How to generate unique ID numbers on a multithread application??

Assumptions:

  • Generated ID are unique
  • Minimal synchronization between thread
  • No synchronization between thread during generation
  • No order assumed, just different values

Ids generated from primes

The idea is to generate the ids as product of powers 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

Generation class

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.

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))
}

Comments

Post a Comment

Popular posts from this blog

Canonical Protocol

Introduction I will like to show some ideas about the canonical protocol I have defined. In the final example it is shown that such protocol provide features given by OAuth at the protocol level, it means that You can pass external resources without any change on services implementations or additional inter-service integration. RPC integration paradigm When using webservices to integrate remote systems, the development process can be summarized to: Client side -- Prepare request data from context -- make call -- Parse response and interpret result Service provider side -- Parse request -- interpret data to make internal API calls -- Create response Well, not so difficult. But the problem is that all the code used to serialize/parse context information and interpret request/response does not add any value to the system. Note that change from technologies like CORBA to web-services is just a standardization of the binary format used to create/parse the messages. The RPC ...
Post a Comment
Read more

Inverse of Control is not Dependency Injection

How to understand the difference between "Dependency Injection" and "Inverse of Control"? Problem lies in lack of examples to "Inverse of Control" different than "Dependency Injection". So, below You can find a simple example to see the difference. On car traffic, each car is "controlled" by a driver. On front of stoplights, cars line up waiting for green light. Drivers accelerate at the sight of green lights, but they do it with delay. This leads to a situation as shown: Applying the Inverse of Control principle, stoplights could take "control" of car's acceleration and execute a synchronized and fast start on green light. So inverse of control for car-semaphore scenario looks like this: How is Dependency Injection related to Inverse of Control?? Well, on Dependency Injection you take the "control" over the new statement from developers to architect. Control on developer looks like this: public clas...
2 comments
Read more

Controlled scope

Introduction A specific use of Guice custom scopes is presented. You can have many problems trying something similar, so be careful. The reason to present this post, it to have a reference to explain a similar custom scope used in Service Architecture Model: ExtrenalBindingInfrastructureModule Problem: nested passing of parameters A business operation may be explicitly defined in a context of several high-level context objects. To improve reusability, code is split in several layers and nested method execution pass the context object. In the example below such situation is shown in one class. public class NestedParamaterPass { public void businessOperation(BusinessData data, Person person, Manager manager, Context context){ // some operation firstNestedCall(data, person, manager, context); } private void firstNestedCall(BusinessData data, Person person, Manager manager, Context context) { secondNestedCall(data, person, manager, context); } private void secondNested...
Post a Comment
Read more