FlakeId for kaif.io

Base62.java

public class Base62 {

  public static final String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

  public static final long BASE = ALPHABET.length();

  public static String fromBase10(long i) {
    StringBuilder sb = new StringBuilder("");
    while (i > 0) {
      i = fromBase10(i, sb);
    }
    return sb.reverse().toString();
  }

  private static long fromBase10(long i, final StringBuilder sb) {
    int rem = (int) (i % BASE);
    sb.append(ALPHABET.charAt(rem));
    return i / BASE;
  }

  public static long toBase10(String str) {
    return toBase10(new StringBuilder(str).reverse().toString().toCharArray());
  }

  private static long toBase10(char[] chars) {
    long n = 0;
    for (int i = chars.length - 1; i >= 0; i--) {
      n += toBase10(ALPHABET.indexOf(chars[i]), i);
    }
    return n;
  }

  private static long toBase10(long n, int pow) {
    return n * (long) Math.pow(BASE, pow);
  }

  private Base62() {
  }
}

FlakeId.java

/**
 * FlakeId is similar to twitter's SnowFlake, which use 64bit long for unique id.
 * the structure of FlakeId is:
 * <p>
 * <code>
 * |--- 41 bits milli seconds --|-- 12 bits micro seconds --|-- 10 bits node id --|
 * </code>
 * <p>
 * long type is 64 bits but sign bit is not used, so meaningful bits are 63.
 * <p>
 * the timestamp part start from 2015-01-01T00:00:00Z. thus FlakeId could not use time before 2015.
 * <p>
 * for each node, FlakeId can generate 4096000 number of unique id per second
 */
public final class FlakeId implements Comparable<FlakeId> {

  // 2015-01-01T00:00:00Z
  private static final long START_OF_SEQUENCE_TIME = 1420070400000L;
  private static final int SUB_MILLI_BITS = 12;
  private static final int NODE_ID_BITS = 10;
  private static final int MIN_NODE_ID = 0;

  /**
   * minimum value of FlakeId, start from 2015-01-01T00:00:00Z
   */
  public static final FlakeId MIN = new FlakeId(0, MIN_NODE_ID);

  /**
   * maximum value of FlakeId, the epoch time is 2084-09-06T15:47:35.551Z
   */
  public static final FlakeId MAX = new FlakeId(Long.MAX_VALUE);

  /**
   * remove fraction of milli seconds in sequence time
   */
  static long millisOfSequenceTime(long sequenceTime) {
    return sequenceTime >> SUB_MILLI_BITS;
  }

  static long sequenceTimeFromEpochMilli(long epochMilli) {
    return (epochMilli - START_OF_SEQUENCE_TIME) << SUB_MILLI_BITS;
  }

  public static FlakeId fromString(String base62) {
    return new FlakeId(Base62.toBase10(base62));
  }

  public static FlakeId valueOf(long value) {
    return new FlakeId(value);
  }

  /**
   * create a pseudo FlakeId with min value on specified epochMilli time. created FlakeId can use
   * to query time range in database
   */
  public static FlakeId startOf(long epochMilli) {
    long sequenceTime = sequenceTimeFromEpochMilli(epochMilli);
    return new FlakeId(sequenceTime, MIN_NODE_ID);
  }

  /**
   * create a pseudo FlakeId which max value on specified epochMilli time. created FlakeId can use
   * to query time range in database
   */
  public static FlakeId endOf(long epochMilli) {
    long sequenceTime = sequenceTimeFromEpochMilli(epochMilli);
    long maxSubMilli = (1L << SUB_MILLI_BITS) - 1;
    int maxNodeId = (1 << NODE_ID_BITS) - 1;
    return new FlakeId(sequenceTime + maxSubMilli, maxNodeId);
  }

  private final long value;

  FlakeId(long sequenceTime, int nodeId) {
    this((sequenceTime << NODE_ID_BITS) | nodeId);
  }

  private FlakeId(long value) {
    Preconditions.checkArgument(value >= 0, "invalid flakeId");
    this.value = value;
  }

  long sequenceTime() {
    return value >> NODE_ID_BITS;
  }

  int nodeId() {
    return (int) (value % (1L << NODE_ID_BITS));
  }

  /**
   * extract epoch milli part in this id
   */
  public long epochMilli() {
    return (value >> (SUB_MILLI_BITS + NODE_ID_BITS)) + START_OF_SEQUENCE_TIME;
  }

  /**
   * long value of FlakeId
   */
  public long value() {
    return value;
  }

  /**
   * Base62 string
   */
  @Override
  public String toString() {
    return Base62.fromBase10(value);
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) {
      return true;
    }
    if (o == null || getClass() != o.getClass()) {
      return false;
    }
    FlakeId flakeId = (FlakeId) o;
    return value == flakeId.value;
  }

  @Override
  public int hashCode() {
    return (int) (value ^ (value >>> 32));
  }

  @Override
  public int compareTo(FlakeId o) {
    return Long.compare(value, o.value);
  }
}

FlakeIdGenerator.java

import java.time.Clock;
import java.time.Instant;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;

/**
 * for every unique id domain usage, you should create it's own sub class, for example:
 * <p>
 * you have two domains that require unique id, and they are allowed to overlay (because different
 * domain), you can create two subclass:
 * <p>
 * CommentFlakeIdGenerator
 * ArticleFlakeIdGenerator
 * <p>
 * CommentFlakeIdGenerator is guarantee all flakeId generated for model (Comment) are unique. so
 * does ArticleFlakeIdGenerator. however, two types of generator may generate duplicate flakeId.
 * <p>
 * the same type of FlakeIdGenerator guarantee generated flakeIds are unique, no matter how many
 * instances of generator.
 */
public abstract class FlakeIdGenerator {

  private static final ConcurrentHashMap<String, AtomicLong> lastSequenceTimeByScope = new ConcurrentHashMap<>();

  private static AtomicLong buildLastSequenceTime(String scope) {
    return lastSequenceTimeByScope.computeIfAbsent(scope, (theScope) -> new AtomicLong());
  }

  private final int nodeId;
  private final Clock clock;
  private final AtomicLong lastSequenceTime;

  protected FlakeIdGenerator(int nodeId) {
    this.nodeId = nodeId;
    this.clock = null;
    this.lastSequenceTime = buildLastSequenceTime(getClass().toString());
  }

  @VisibleForTesting
  FlakeIdGenerator(int nodeId, Clock clock, String scope) {
    this.nodeId = nodeId;
    this.clock = clock;
    this.lastSequenceTime = buildLastSequenceTime(scope);
  }

  private long currentEpochMilli() {
    if (clock == null) {
      return System.currentTimeMillis();
    }
    return Instant.now(clock).toEpochMilli();
  }

  public final FlakeId next() {
    return new FlakeId(getCurrentSequenceTime(), nodeId);
  }

  /*
   * ingram: The code copy from cassandra driver UUIDs class
   *
   * Note that currently we use System.currentTimeMillis() for a base time in
   * milliseconds, and then if we are in the same milliseconds that the
   * previous generation, we increment the number of sub milli second.
   * However, since the precision is 4096/milli-second (12 bit), we can only
   * generate 4096 FlakeId within a millisecond safely. If we detect we have
   * already generated that much FlakeId within a millisecond (which, while
   * admittedly unlikely in a real application, is very achievable on even
   * modest machines), then we stall the generator (busy spin) until the next
   * millisecond as required.
   */
  private long getCurrentSequenceTime() {
    while (true) {
      long now = FlakeId.sequenceTimeFromEpochMilli(currentEpochMilli());
      long last = lastSequenceTime.get();
      if (now > last) {
        if (lastSequenceTime.compareAndSet(last, now)) {
          return now;
        }
      } else {
        long lastMillis = FlakeId.millisOfSequenceTime(last);
        // If the clock went back in time, bail out
        if (FlakeId.millisOfSequenceTime(now) < FlakeId.millisOfSequenceTime(last)) {
          return lastSequenceTime.incrementAndGet();
        }

        long candidate = last + 1;
        // If we've generated more than 4096 FlakeId in that millisecond,
        // we restart the whole process until we get to the next millis.
        // Otherwise, we try use our candidate ... unless we've been
        // beaten by another thread in which case we try again.
        if (FlakeId.millisOfSequenceTime(candidate) == lastMillis && lastSequenceTime.compareAndSet(
            last,
            candidate)) {
          return candidate;
        }
      }
    }
  }

  public final int getNodeId() {
    return nodeId;
  }
}