| // Copyright 2015 The Vanadium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| package io.v.todos.persistence.syncbase; |
| |
| import java.util.UUID; |
| |
| public class IdGenerator { |
| // TODO(rosswang): Escape collection IDs to allow any character. A lot of this logic can be |
| // simplified if we can use any character. |
| // TODO(rosswang): Put this into Syncbase utils. |
| |
| private final IdAlphabet mAlphabet; |
| |
| /** |
| * the length we *would* need if we could use an underscore for the first character |
| */ |
| private final int mLongUniformRadixLength; |
| private final int mLongEncodedLength; |
| |
| /** |
| * This is related to unsigned division. |
| * @see #transformToSignedDivision(long) |
| */ |
| private final int mMaxSafeMostSignificantDigit; |
| /** |
| * This is related to unsigned division. |
| * @see #transformToSignedDivision(long) |
| */ |
| private final long mMostSignificantUnit, mMaxSafeMostSignificantValue; |
| |
| private static final double LOG_LONG = Long.SIZE * Math.log(2); |
| |
| /** |
| * @param alphabet the alphabet of legal characters for IDs generated by this generator |
| * @param perturb whether or not to perturb generated IDs by a random perturbation to avoid |
| * collisions in distributed key generation. Pass {@code false} if this generator |
| * is used to generate a sort key that is a secondary key where ordering |
| * conflicts can be deterministically resolved by the primary key. This setting |
| * only applies to the {@code generate...} methods. |
| */ |
| public IdGenerator(IdAlphabet alphabet, boolean perturb) { |
| mAlphabet = alphabet; |
| mPerturb = perturb; |
| |
| // ceil(log_RADIX(Long.MAX + 1)) |
| mLongUniformRadixLength = (int)Math.ceil(LOG_LONG / Math.log(alphabet.radix())); |
| |
| // int pow, msu = radix ^ url |
| long mostSignificantUnit = alphabet.radix(); |
| for (int i = 2; i < mLongUniformRadixLength; i++) { |
| mostSignificantUnit *= alphabet.radix(); |
| } |
| mMostSignificantUnit = mostSignificantUnit; |
| |
| mMaxSafeMostSignificantDigit = (int)(Long.MAX_VALUE / mMostSignificantUnit); |
| mMaxSafeMostSignificantValue = mMaxSafeMostSignificantDigit * mMostSignificantUnit; |
| |
| // The first character may have additional restrictions, so we have less chars to work with |
| // for the first digit. If we still have enough digits, we'll proceed and just use a special |
| // mapping for the leading digit. Otherwise, we'll pad by a leading 0, thus making the |
| // remaining encoding the common case. |
| |
| // So, what most-significant digit do we need to encode the max unsigned value? |
| PartialDivisionResult div = transformToSignedDivision(-1); |
| int maxMostSignfiicantDigit = div.partialMostSignificantDigit + |
| (int)(div.partialRemainder / mMostSignificantUnit); |
| mLongEncodedLength = maxMostSignfiicantDigit < alphabet.leadingRadix() ? |
| mLongUniformRadixLength : mLongUniformRadixLength + 1; |
| } |
| |
| private static class PartialDivisionResult { |
| public int partialMostSignificantDigit; |
| public long partialRemainder; |
| |
| public PartialDivisionResult(int partialMostSignificantDigit, long partialRemainder) { |
| this.partialMostSignificantDigit = partialMostSignificantDigit; |
| this.partialRemainder = partialRemainder; |
| } |
| } |
| |
| /** |
| * Performs partial calculation of the most significant digit for the alphabet-radix |
| * representation of {@code unsigned}. To achieve unsigned division, we first assume the |
| * most significant digit is at least as large as the max safe most significant digit for signed |
| * division, add one more if neccessary to push the "remainder" positive, and then do normal |
| * division for the rest. |
| */ |
| private PartialDivisionResult transformToSignedDivision(long unsigned) { |
| if (unsigned < 0) { |
| long naiveRemainder = unsigned - mMaxSafeMostSignificantValue; |
| return naiveRemainder < 0 ? |
| // need one more |
| new PartialDivisionResult(mMaxSafeMostSignificantDigit + 1, |
| naiveRemainder - mMostSignificantUnit) : |
| new PartialDivisionResult(mMaxSafeMostSignificantDigit, naiveRemainder); |
| } else { |
| // Already positive; handle with normal arithmetic. |
| return new PartialDivisionResult(0, unsigned); |
| } |
| } |
| |
| /** |
| * Converts a signed {@code long} to a {@code String} consistent with the pattern |
| * {@code [0-9A-Za-z][0-9A-Za-z_]*}, required by Syncbase for |
| * {@link io.v.v23.services.syncbase.Id} names, with lexicographic ordering consistent with the |
| * numeric ordering. |
| * <p> |
| * Example transformations using {@link IdAlphabets#COLLECTION_ID}: |
| * <pre> |
| * -9223372036854775808 -> 00000000000 |
| * -9223372036854775807 -> 00000000001 |
| * -9223372036854775806 -> 00000000002 |
| * -1 -> 9MxfBQuKjH7 |
| * 0 -> 9MxfBQuKjH8 |
| * 1 -> 9MxfBQuKjH9 |
| * 9223372036854775805 -> IivLMqoeTYD |
| * 9223372036854775806 -> IivLMqoeTYE |
| * 9223372036854775807 -> IivLMqoeTYF |
| * </pre> |
| */ |
| public String longToPaddedIdentifier(long x) { |
| StringBuilder s = new StringBuilder(mLongEncodedLength); |
| long unsignedWithSameOrdering = x - Long.MIN_VALUE; |
| PartialDivisionResult signedSubproblem = |
| transformToSignedDivision(unsignedWithSameOrdering); |
| long leftToEncode = signedSubproblem.partialRemainder; |
| |
| for (int placeValue = 0; placeValue < mLongUniformRadixLength - 1; placeValue++) { |
| if (leftToEncode > 0) { |
| s.append(mAlphabet.encodeDigit((int) (leftToEncode % mAlphabet.radix()))); |
| leftToEncode /= mAlphabet.radix(); |
| } else { |
| s.append(mAlphabet.encodeDigit(0)); |
| } |
| } |
| |
| // The most-significant digit needs to be handled specially, accounting for the signed |
| // division adjustment and using a possibly different character mapping. |
| int mostSignificantDigit = signedSubproblem.partialMostSignificantDigit + (int)leftToEncode; |
| if (mLongEncodedLength > mLongUniformRadixLength) { |
| // just 0-pad |
| s.append(mAlphabet.encodeDigit(mostSignificantDigit)) |
| .append(mAlphabet.encodeLeadingDigit(0)); |
| } else { |
| // use the special leading-digit mapping |
| s.append(mAlphabet.encodeLeadingDigit(mostSignificantDigit)); |
| } |
| |
| return s.reverse().toString(); |
| } |
| |
| /** |
| * Perturbs IDs to mitigate collision during distributed, eventually consistent insertion. |
| * {@link UUID#randomUUID()} is used for perturbation. The perturbed ID is strictly greater than |
| * the base ID but less than the next increment from the base ID except in the degenerate case |
| * where the base ID must be extended to increment. |
| */ |
| public String perturb(String baseId) { |
| UUID uuid = UUID.randomUUID(); |
| return baseId + |
| longToPaddedIdentifier(uuid.getMostSignificantBits()) + |
| longToPaddedIdentifier(uuid.getLeastSignificantBits()); |
| } |
| |
| /** |
| * Increments an ID with a proposed base length. If the increment cannot be done under these |
| * constraints, the ID is extended. The incremented ID is guaranteed to be greater than the |
| * given {@code fullId}. |
| * <p> |
| * Example transformations: |
| * <pre> |
| * 0000 -> 01 |
| * AZ00 -> A_ |
| * Az00 -> B0 |
| * Zz00 -> a0 |
| * zz00 -> zz1 |
| * zzz0 -> zzz1 |
| * zzzz -> zzzz0 |
| * </pre> |
| */ |
| public String increment(String fullId, int proposedCutoff) { |
| StringBuilder mutable = new StringBuilder(fullId); |
| |
| if (proposedCutoff > fullId.length()) { |
| proposedCutoff = fullId.length(); |
| } |
| |
| // First try normal incrementing |
| for (int i = proposedCutoff - 1; i > 0; i--) { |
| int newValue = mAlphabet.decodeDigit(mutable.charAt(i)) + 1; |
| if (newValue < mAlphabet.radix()) { |
| mutable.setCharAt(i, mAlphabet.encodeDigit(newValue)); |
| mutable.setLength(proposedCutoff); |
| return mutable.toString(); |
| } else { |
| mutable.setCharAt(i, mAlphabet.encodeDigit(0)); |
| } |
| } |
| |
| // Process the leading digit specially |
| if (proposedCutoff > 0){ |
| int newValue = mAlphabet.decodeLeadingDigit(mutable.charAt(0)) + 1; |
| if (newValue < mAlphabet.leadingRadix()) { |
| mutable.setCharAt(0, mAlphabet.encodeLeadingDigit(newValue)); |
| mutable.setLength(proposedCutoff); |
| return mutable.toString(); |
| } |
| } |
| |
| // If we've gotten to this point, we can't increment the prefix; start looking at the |
| // suffix. |
| |
| // Reset mutable |
| mutable.setLength(0); |
| mutable.append(fullId); |
| |
| for (int i = proposedCutoff; i < fullId.length(); i++) { |
| int newValue = mAlphabet.decodeDigit(mutable.charAt(i)) + 1; |
| if (newValue < mAlphabet.radix()) { |
| mutable.setCharAt(i, mAlphabet.encodeDigit(newValue)); |
| mutable.setLength(i + 1); |
| return mutable.toString(); |
| } |
| } |
| // By this point, we just have to extend the string. |
| mutable.append(mAlphabet.encodeDigit(0)); |
| return mutable.toString(); |
| } |
| |
| public String increment(String previous) { |
| return increment(previous, mLongEncodedLength); |
| } |
| |
| private final Object mLargestKnownIdMutex = new Object(); |
| private String mLargestKnownId; |
| private final boolean mPerturb; |
| |
| public String generateTailId() { |
| String candidate = longToPaddedIdentifier(System.currentTimeMillis()); |
| synchronized (mLargestKnownIdMutex) { |
| if (mLargestKnownId != null && candidate.compareTo(mLargestKnownId) <= 0) { |
| candidate = increment(mLargestKnownId); |
| } |
| return mLargestKnownId = mPerturb? perturb(candidate) : candidate; |
| } |
| } |
| |
| public void registerId(String id) { |
| synchronized (mLargestKnownIdMutex) { |
| if (mLargestKnownId == null || id.compareTo(mLargestKnownId) > 0) { |
| mLargestKnownId = id; |
| } |
| } |
| } |
| } |