Почему этот код генерирует повторяющийся идентификатор?

Question

У меня есть следующий код для генерации уникального идентификатора события.Это не чистый генератор GUID, а способ генерации уникального идентификатора на разных машинах / процессах.

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

Предполагается, что он вызывается из распределенной программы, работающей на нескольких JVM на разных машинах.Здесь идентификатор раздела будет уникальным для разных виртуальных машин и компьютеров.

Когда я запускаю эту программу в одном потоке, она работает нормально.Но когда я запускаю его в нескольких потоках, где каждый поток вызывает nextEventId с уникальным идентификатором раздела, иногда я получаю повторяющиеся идентификаторы событий.Я не могу понять, в чем проблема с кодом ниже.

Answer 1

У вас есть только 1024 различных значения для nextSequence.Таким образом, если у вас частота запросов более 1024 за миллисекунду (для 1 раздела), у вас есть ~ 100% вероятность столкновения.На самом деле, я полагаю, что столкновение будет происходить с гораздо меньшей частотой из-за точности часов.

Я вижу, что вы пытались обойти его с sleep(1), если обнаружили переполнение nextSequence.Но это не работает в многопоточной среде.Определенный раздел может даже никогда не увидеть nextSequence равным 0.