CODEWITHSUNDEEP
multithreadingscala
Shirish Kumar
Shirish Kumar

Reputation: 1532

Why this code is generating duplicate id?

I have the following code to generate unique eventId. This is not a pure GUID generator but a way to generate unique id across different machines/processes. 

import java.util.concurrent.atomic.AtomicInteger

object EventIdGenerator extends Serializable {
  val totalBits = 64
  private val epochBits = 42
  private val partitionIdBits = 10
  private val sequenceBits = 12
  private val sequenceInt = new AtomicInteger(0)

  private val maxPartitionId = (Math.pow(2, partitionIdBits) - 1).toInt
  private val maxSequenceId = (Math.pow(2, sequenceBits) - 1).toInt

  def nextEventId(partitionId: Int): Long = {
    assert(partitionId <= maxPartitionId)

    val nextSequence = sequenceInt.incrementAndGet() % maxSequenceId

    val timestamp =  if (nextSequence == 0) {
      Thread.sleep(1)
      System.currentTimeMillis()
    } else System.currentTimeMillis()

    timestamp << (totalBits - epochBits) |
    partitionId << (totalBits - epochBits - partitionIdBits) |
    nextSequence
  }
}

This is supposed to be called from a distributed program running over several JVMs in different machines. Here partition id is going to be unique across different JVMs and machine.

When I run this program in a single thread, it works fine. But when I run it in multiple threads where each thread calls nextEventId with a unique partition id, sometimes I get duplicate event Ids. I am not able to figure out what the problem is with the code below.

Upvotes: 1

Views: 166

Answers (1)

simpadjo
simpadjo

Reputation: 4017

You have only 1024 different values for nextSequence. So if you have request rate more than 1024 per millisecond (for 1 partition) you have ~100% chance of collision. In fact I believe that collision will appear with even much smaller rates because of clock precision.

I see that you tried to sidestep it with sleep(1) if you detected an overflow of nextSequence. But it doesn't work in a multithreaded environment. A particular partition may even never see nextSequence equal to 0.

Upvotes: 1

Related Questions