SONAR-8332 allow faster UUID generation with increment only change

the 2 strategies (full new UUID or only increment changed) are exposed in new class UuidGeneratorImpl

4 files changed, 247 insertions, 48 deletions

diff --git a/sonar-core/src/main/java/org/sonar/core/util/UuidFactoryImpl.java b/sonar-core/src/main/java/org/sonar/core/util/UuidFactoryImpl.java
index 5f29df4d5fb..bac2b17fa54 100644
--- a/sonar-core/src/main/java/org/sonar/core/util/UuidFactoryImpl.java
+++ b/sonar-core/src/main/java/org/sonar/core/util/UuidFactoryImpl.java
@@ -19,14 +19,9 @@
  */
 package org.sonar.core.util;
 
-import java.security.SecureRandom;
-import java.util.concurrent.atomic.AtomicInteger;
 import org.apache.commons.codec.binary.Base64;
 
 /**
- * Heavily inspired from Elasticsearch {@code TimeBasedUUIDGenerator}, which could be directly
- * used the day {@code UuidFactoryImpl} is moved outside module sonar-core.
- * See https://github.com/elastic/elasticsearch/blob/master/core/src/main/java/org/elasticsearch/common/TimeBasedUUIDGenerator.java
  */
 public enum UuidFactoryImpl implements UuidFactory {
 
@@ -36,52 +31,11 @@ public enum UuidFactoryImpl implements UuidFactory {
    */
   INSTANCE;
 
-  // We only use bottom 3 bytes for the sequence number. Paranoia: init with random int so that if JVM/OS/machine goes down, clock slips
-  // backwards, and JVM comes back up, we are less likely to be on the same sequenceNumber at the same time:
-  private final AtomicInteger sequenceNumber = new AtomicInteger(new SecureRandom().nextInt());
-
-  // Used to ensure clock moves forward
-  private long lastTimestamp = 0L;
-
-  private final byte[] secureMungedAddress = MacAddressProvider.getSecureMungedAddress();
+  private final UuidGenerator uuidGenerator = new UuidGeneratorImpl();
 
   @Override
   public String create() {
-    int sequenceId = sequenceNumber.incrementAndGet() & 0xffffff;
-    long timestamp = System.currentTimeMillis();
-
-    synchronized (this) {
-      // Don't let timestamp go backwards, at least "on our watch" (while this JVM is running). We are still vulnerable if we are
-      // shut down, clock goes backwards, and we restart... for this we randomize the sequenceNumber on init to decrease chance of
-      // collision:
-      timestamp = Math.max(lastTimestamp, timestamp);
-
-      if (sequenceId == 0) {
-        // Always force the clock to increment whenever sequence number is 0, in case we have a long time-slip backwards:
-        timestamp++;
-      }
-
-      lastTimestamp = timestamp;
-    }
-
-    byte[] uuidBytes = new byte[15];
-
-    // Only use lower 6 bytes of the timestamp (this will suffice beyond the year 10000):
-    putLong(uuidBytes, timestamp, 0, 6);
-
-    // MAC address adds 6 bytes:
-    System.arraycopy(secureMungedAddress, 0, uuidBytes, 6, secureMungedAddress.length);
-
-    // Sequence number adds 3 bytes:
-    putLong(uuidBytes, sequenceId, 12, 3);
-
-    return Base64.encodeBase64URLSafeString(uuidBytes);
+    return Base64.encodeBase64URLSafeString(uuidGenerator.generate());
   }
 
-  /** Puts the lower numberOfLongBytes from l into the array, starting index pos. */
-  private static void putLong(byte[] array, long l, int pos, int numberOfLongBytes) {
-    for (int i = 0; i < numberOfLongBytes; ++i) {
-      array[pos + numberOfLongBytes - i - 1] = (byte) (l >>> (i * 8));
-    }
-  }
 }
diff --git a/sonar-core/src/main/java/org/sonar/core/util/UuidGenerator.java b/sonar-core/src/main/java/org/sonar/core/util/UuidGenerator.java
new file mode 100644
index 00000000000..0bf4a3301d6
--- /dev/null
+++ b/sonar-core/src/main/java/org/sonar/core/util/UuidGenerator.java
@@ -0,0 +1,80 @@
+/*
+ * SonarQube
+ * Copyright (C) 2009-2016 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+ */
+package org.sonar.core.util;
+
+/**
+ * A generator of UUID as a byte array which is made of two parts:
+ * <ul>
+ *   <li>a base, which is machine and time dependant and therefor will change with time</li>
+ *   <li>an increment</li>
+ * </ul>
+ *
+ * <p>
+ * This generator can be used in two ways:
+ * <ul>
+ *   <li>either the base and the increment are changed for each UUID (with time for the base, with each call to
+ *   {@link #generate()} for the increment) and {@link #generate()} should be used</li>
+ *   <li>or the increment can be the only changing part (for performance boost and less concurrency) and
+ *   {@link #withFixedBase()} should be used.</li>
+ * </ul>
+ * </p>
+ *
+ * <p>
+ * <strong>Warning:</strong> {@link WithFixedBase#generate(int)} can be considerably faster than {@link #generate()} but
+ * is limited to generate only 2^23-1 unique values.
+ * </p>
+ *
+ * <p>
+ * Heavily inspired from Elasticsearch {@code TimeBasedUUIDGenerator}, which could be directly
+ * used the day {@code UuidFactoryImpl} is moved outside module sonar-core.
+ * See https://github.com/elastic/elasticsearch/blob/master/core/src/main/java/org/elasticsearch/common/TimeBasedUUIDGenerator.java
+ * </p>
+ */
+public interface UuidGenerator {
+  /**
+   * Generates a UUID which base and increment are always different from any other value provided by this method.
+   */
+  byte[] generate();
+
+  /**
+   * Provide a new UUID generating instance which will allow generation of UUIDs which base is constant and can
+   * vary according to a provided increment value (see {@link WithFixedBase#generate(int)}).
+   */
+  WithFixedBase withFixedBase();
+
+  @FunctionalInterface
+  interface WithFixedBase {
+    /**
+     * Generate a new unique universal identifier using the last 3 bytes of the specified int.
+     * <p>
+     * <strong>This implies that this method of a given {@link WithFixedBase} instance can only generate up to
+     * 2^23-1 unique values if provided with unique int arguments.</strong>
+     * </p>
+     * <p>
+     * This is up to the caller to ensure that unique int values are provided to a given instance's {@link #generate(int)}
+     * method.
+     * </p>
+     * <p>
+     * This method is faster than {@link UuidGenerator#generate()} due to less computation and less internal concurrency.
+     * </p>
+     */
+    byte[] generate(int increment);
+  }
+}
diff --git a/sonar-core/src/main/java/org/sonar/core/util/UuidGeneratorImpl.java b/sonar-core/src/main/java/org/sonar/core/util/UuidGeneratorImpl.java
new file mode 100644
index 00000000000..f76adf7e0cc
--- /dev/null
+++ b/sonar-core/src/main/java/org/sonar/core/util/UuidGeneratorImpl.java
@@ -0,0 +1,113 @@
+/*
+ * SonarQube
+ * Copyright (C) 2009-2016 SonarSource SA
+ * mailto:contact AT sonarsource DOT com
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
+ */
+package org.sonar.core.util;
+
+import java.security.SecureRandom;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.Supplier;
+
+public final class UuidGeneratorImpl implements UuidGenerator {
+
+  private final FullNewUuidGenerator fullNewUuidGenerator = new FullNewUuidGenerator();
+
+  @Override
+  public byte[] generate() {
+    return fullNewUuidGenerator.get();
+  }
+
+  @Override
+  public WithFixedBase withFixedBase() {
+    return new FixedBasedUuidGenerator();
+  }
+
+  private static class UuidGeneratorBase {
+    private final byte[] buffer = new byte[15];
+    // We only use bottom 3 bytes for the sequence number. Paranoia: init with random int so that if JVM/OS/machine goes down, clock slips
+    // backwards, and JVM comes back up, we are less likely to be on the same sequenceNumber at the same time:
+    private final AtomicInteger sequenceNumber = new AtomicInteger(new SecureRandom().nextInt());
+    private final byte[] secureMungedAddress = MacAddressProvider.getSecureMungedAddress();
+    // Used to ensure clock moves forward
+    private long lastTimestamp = 0L;
+
+    void initBase(int sequenceId) {
+      long timestamp = System.currentTimeMillis();
+
+      synchronized (this) {
+        // Don't let timestamp go backwards, at least "on our watch" (while this JVM is running). We are still vulnerable if we are
+        // shut down, clock goes backwards, and we restart... for this we randomize the sequenceNumber on init to decrease chance of
+        // collision:
+        timestamp = Math.max(lastTimestamp, timestamp);
+
+        if (sequenceId == 0) {
+          // Always force the clock to increment whenever sequence number is 0, in case we have a long time-slip backwards:
+          timestamp++;
+        }
+
+        lastTimestamp = timestamp;
+      }
+
+      // Only use lower 6 bytes of the timestamp (this will suffice beyond the year 10000):
+      putLong(buffer, timestamp, 0, 6);
+
+      // MAC address adds 6 bytes:
+      System.arraycopy(secureMungedAddress, 0, buffer, 6, secureMungedAddress.length);
+    }
+
+    protected byte[] generate(int increment) {
+      // Sequence number adds 3 bytes
+      putLong(buffer, increment, 12, 3);
+
+      return buffer;
+    }
+
+    int getSequenceId() {
+      return sequenceNumber.incrementAndGet() & 0xffffff;
+    }
+
+    /** Puts the lower numberOfLongBytes from l into the array, starting index pos. */
+    private static void putLong(byte[] array, long l, int pos, int numberOfLongBytes) {
+      for (int i = 0; i < numberOfLongBytes; ++i) {
+        array[pos + numberOfLongBytes - i - 1] = (byte) (l >>> (i * 8));
+      }
+    }
+  }
+
+  private static final class FullNewUuidGenerator extends UuidGeneratorBase implements Supplier<byte[]> {
+
+    @Override
+    public byte[] get() {
+      int sequenceId = getSequenceId();
+      initBase(sequenceId);
+      return super.generate(sequenceId);
+    }
+  }
+
+  private static class FixedBasedUuidGenerator extends UuidGeneratorBase implements WithFixedBase {
+    FixedBasedUuidGenerator() {
+      int sequenceId = getSequenceId();
+      initBase(sequenceId);
+    }
+
+    @Override
+    public byte[] generate(int increment) {
+      return super.generate(increment);
+    }
+  }
+}
diff --git a/sonar-core/src/test/java/org/sonar/core/util/UuidGeneratorImplTest.java b/sonar-core/src/test/java/org/sonar/core/util/UuidGeneratorImplTest.java
new file mode 100644
index 00000000000..b5a3d85d200
--- /dev/null
+++ b/sonar-core/src/test/java/org/sonar/core/util/UuidGeneratorImplTest.java
@@ -0,0 +1,52 @@
+package org.sonar.core.util;
+
+import java.util.Base64;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+import org.junit.Test;
+
+import static org.assertj.core.api.Assertions.assertThat;
+
+public class UuidGeneratorImplTest {
+  private UuidGeneratorImpl underTest = new UuidGeneratorImpl();
+
+  @Test
+  public void generate_returns_unique_values_without_common_initial_letter_given_more_than_one_milisecond_between_generate_calls() throws InterruptedException {
+    Base64.Encoder encoder = Base64.getEncoder();
+    int count = 30;
+    Set<String> uuids = new HashSet<>(count);
+    for (int i = 0; i < count; i++) {
+      Thread.sleep(5);
+      uuids.add(encoder.encodeToString(underTest.generate()));
+    }
+    assertThat(uuids).hasSize(count);
+
+    Iterator<String> iterator = uuids.iterator();
+    String firstUuid = iterator.next();
+    String base = firstUuid.substring(0, firstUuid.length() - 4);
+    for (int i = 1; i < count; i++) {
+      assertThat(iterator.next()).describedAs("i=" + i).doesNotStartWith(base);
+    }
+  }
+
+  @Test
+  public void generate_from_FixedBase_returns_unique_values_where_only_last_4_later_letter_change() {
+    Base64.Encoder encoder = Base64.getEncoder();
+    int count = 100_000;
+    Set<String> uuids = new HashSet<>(count);
+
+    UuidGenerator.WithFixedBase withFixedBase = underTest.withFixedBase();
+    for (int i = 0; i < count; i++) {
+      uuids.add(encoder.encodeToString(withFixedBase.generate(i)));
+    }
+    assertThat(uuids).hasSize(count);
+
+    Iterator<String> iterator = uuids.iterator();
+    String firstUuid = iterator.next();
+    String base = firstUuid.substring(0, firstUuid.length() - 4);
+    while (iterator.hasNext()) {
+      assertThat(iterator.next()).startsWith(base);
+    }
+  }
+}