From ab31b7a55f57aa9d85b4bae88879c4598c2f6521 Mon Sep 17 00:00:00 2001 From: =?utf8?q?S=C3=A9bastien=20Lesaint?= Date: Tue, 8 Nov 2016 15:45:17 +0100 Subject: [PATCH] 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 --- .../org/sonar/core/util/UuidFactoryImpl.java | 50 +------- .../org/sonar/core/util/UuidGenerator.java | 80 +++++++++++++ .../sonar/core/util/UuidGeneratorImpl.java | 113 ++++++++++++++++++ .../core/util/UuidGeneratorImplTest.java | 52 ++++++++ 4 files changed, 247 insertions(+), 48 deletions(-) create mode 100644 sonar-core/src/main/java/org/sonar/core/util/UuidGenerator.java create mode 100644 sonar-core/src/main/java/org/sonar/core/util/UuidGeneratorImpl.java create mode 100644 sonar-core/src/test/java/org/sonar/core/util/UuidGeneratorImplTest.java 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: + * + * + *

+ * This generator can be used in two ways: + *

+ *

+ * + *

+ * Warning: {@link WithFixedBase#generate(int)} can be considerably faster than {@link #generate()} but + * is limited to generate only 2^23-1 unique values. + *

+ * + *

+ * 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 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. + *

+ * 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. + *

+ *

+ * This is up to the caller to ensure that unique int values are provided to a given instance's {@link #generate(int)} + * method. + *

+ *

+ * This method is faster than {@link UuidGenerator#generate()} due to less computation and less internal concurrency. + *

+ */ + 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 { + + @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 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 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 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 iterator = uuids.iterator(); + String firstUuid = iterator.next(); + String base = firstUuid.substring(0, firstUuid.length() - 4); + while (iterator.hasNext()) { + assertThat(iterator.next()).startsWith(base); + } + } +} -- 2.39.5