Skip to main content

Posts

Showing posts from 2013

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 {