Developer Blog
Generating unique identifiers in distributed systems presents significant challenges. While single-server environments can easily rely on auto-increment values or sequences, distributed environments where multiple servers must simultaneously generate IDs require careful consideration to ensure efficiency and avoid duplication.
In this article, we'll explore an effective implementation of a unique identifier generator designed for distributed environments: the DistributedIdGenerator.
Here's an example implementation of an identifier generator for distributed environments:
import kr.co.example.global.extension.now
import java.time.ZoneOffset
import java.util.concurrent.atomic.AtomicLong
class DistributedIdGenerator(
private val serverId: Int
) {
companion object {
const val MAX_SERVER_ID = 1000
}
private val maxSequence = 999999
private val counter = AtomicLong()
init {
require(serverId < MAX_SERVER_ID) {
throw IllegalStateException("exceed max server id $serverId")
}
}
fun generate(): String {
val timestamp = now().toEpochSecond(ZoneOffset.UTC)
val uniqueId = counter.updateAndGet { current ->
if (current >= maxSequence) 0 else current + 1
}
return String.format("%s%03d%06d", timestamp, serverId, uniqueId)
}
}This implementation works as follows:
The final identifier format is: "Timestamp (seconds) + Server ID (3 digits) + Sequence Number (6 digits)".
The diagram above illustrates how multiple servers can generate unique IDs simultaneously without coordination. Each server:
This ensures that even if multiple servers generate IDs at the exact same millisecond, the resulting IDs will still be globally unique.
The following test code verifies that the identifier generator meets the requirements:
import org.assertj.core.api.Assertions.assertThat
import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Assertions.assertTrue
import org.junit.jupiter.api.DisplayName
import org.junit.jupiter.api.RepeatedTest
import org.junit.jupiter.api.Test
import java.util.concurrent.ConcurrentHashMap
import java.util.concurrent.Executors
import java.util.concurrent.TimeUnit
class DistributedIdGeneratorTest {
private val DistributedIdGenerator = DistributedIdGenerator(1)
@Test
@DisplayName("serverId_validation")
fun test_constructor() {
// given
val invalidServerId = 1000
val maxServerId = 999
// when
val failedResult = runCatching { DistributedIdGenerator(invalidServerId) }
.onFailure { it.printStackTrace() }
val successResult = runCatching { DistributedIdGenerator(maxServerId) }
.onFailure { it.printStackTrace() }
// then
assertThat(failedResult.isFailure).isTrue
assertThat(failedResult.exceptionOrNull()).isInstanceOf(IllegalStateException::class.java)
assertThat(successResult.isSuccess).isTrue
}
@RepeatedTest(10)
@DisplayName("should_generate_1M_ids_per_second_with_max_length_20")
fun test_generate_should_not_over_20_length_should_not_duplicated_value() {
val totalKeys = 1_000_000 // Total number of keys to generate
val threadCount = 10 // Number of threads to use
val keysPerThread = totalKeys / threadCount // Keys to generate per thread
val generatedKeys = ConcurrentHashMap.newKeySet<String>() // ConcurrentHashSet to check for duplicates
val executor = Executors.newFixedThreadPool(threadCount) // Thread pool creation
(1..threadCount).forEach { i ->
executor.submit {
(1..keysPerThread).forEach { j ->
val key = DistributedIdGenerator.generate()
assertTrue(key.length <= 20, "Key length exceeded 20 characters: $key")
generatedKeys.add(key) // Add the generated key to the Set
}
}
}
// Wait for all threads to complete their work
executor.shutdown()
executor.awaitTermination(1, TimeUnit.HOURS)
// Verify that the total number of keys generated matches the expected count
assertEquals(totalKeys, generatedKeys.size, "Duplicate keys detected!")
}
}Here's an example of how to integrate the DistributedIdGenerator into a Spring Boot application:
import kr.co.example.global.ActiveProfileManager
import org.slf4j.LoggerFactory
import org.springframework.boot.SpringApplication
import org.springframework.context.ApplicationContext
import org.springframework.context.annotation.Bean
import org.springframework.context.annotation.ComponentScan
import org.springframework.context.annotation.Configuration
import kotlin.math.absoluteValue
@Configuration
@ComponentScan(basePackages = ["kr.co.example.notification"])
class BeanConfig(
private val detector: ActiveProfileManager,
private val applicationContext: ApplicationContext
) {
private val logger = LoggerFactory.getLogger(javaClass)
@Bean
fun distributedIdGenerator(): DistributedIdGenerator {
val serverId: Int = if (detector.isLocal()) {
1
} else {
val podName = System.getenv("HOSTNAME")
if (podName.isNullOrEmpty()) {
logger.info("HOSTNAME is not set. Shutting down the application.")
SpringApplication.exit(applicationContext) // Gracefully shutdown Spring application
}
val uniquePart = podName.substringAfterLast("-")
uniquePart.hashCode().absoluteValue.rem(DistributedIdGenerator.MAX_SERVER_ID)
}
logger.info("server id is : {}", serverId)
return DistributedIdGenerator(serverId)
}
}This configuration class demonstrates intelligent server ID assignment:
Generating unique identifiers in distributed environments requires careful consideration of uniqueness, performance, and scalability. The approach presented here offers a simple yet effective solution that balances these requirements without needing external coordination between servers.
By combining a timestamp, server ID, and sequence number, this implementation can generate millions of unique identifiers per second across a distributed system, with each identifier being no longer than 20 characters.
When implementing your own distributed ID generation system, consider your specific requirements around sortability, predictability, and collision resistance to choose the most appropriate approach.