An ID generator that is decentralized and can be sorted in chronological order.

id.rb

# I implemented Firebase's push ID.
# @see https://firebase.googleblog.com/2015/02/the-2120-ways-to-ensure-unique_68.html
#
# Fancy ID generator that creates 20-character string identifiers with the following properties:
#
# 1. They're based on timestamp so that they sort *after* any existing ids.
# 2. They contain 72-bits of random data after the timestamp so that IDs won't collide with other clients' IDs.
# 3. They sort *lexicographically* (so the timestamp is converted to characters that will sort properly).
# 4. They're monotonically increasing.  Even if you generate more than one in the same timestamp, the
#    latter ones will sort after the former ones.  We do this by using the previous random bits
#    but "incrementing" them by 1 (only in the case of a timestamp collision).
#
# Usage:
#   > gen = IdGenerator.new
#   > gen.make
#   => "-MZOxmHb0hnkYGe-cg9m"
#
#   > time = Time.new(2021, 4, 25)
#   => 2021-04-25 00:00:00 +0900
#
#   > id = gen.make(time)
#   => "-MZ3OFL-E3nklBU242kV"
#
#   > gen.get_time(id)
#   => 2021-04-25 00:00:00 +0900
#
# LICENSE : PUBLIC DOMAIN

require 'securerandom'
require 'time'

class IdGenerator
  TIME_BIT_SIZE = 48
  RANDOM_BIT_SIZE = 72
  BASE64_BIT_SIZE = 6
  CHAR_SIZE = (TIME_BIT_SIZE + RANDOM_BIT_SIZE) / BASE64_BIT_SIZE
  ENCODE_MAP = '-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz'
  DECODE_MAP = ENCODE_MAP.each_char.with_index.to_h{|char, index| [char, index]}

  def initialize
    @pre_epoch = nil
    @pre_random = nil
  end

  # Generate an ID.
  def make(time = Time.now)
    # Convert to elapsed time (ms).
    epoch = (time.to_f * 1000).to_i
    
    if(epoch == @pre_epoch)
      # If it is the same as the time generated last time, the random number part is incremented. This keeps the timeline.
      self.increment
    else
      # Generate a new ID.
      random = SecureRandom.random_number(1 << RANDOM_BIT_SIZE) 
      @pre_epoch = epoch
      @pre_random = random
      self.make_core(epoch, random)
    end
  end

  # Convert a numeric ID to a string.
  # Modeled after base64 web-safe chars, but ordered by ASCII.
  def to_s(id_num)
    result = ''

    CHAR_SIZE.times do
      # Get the lower 6 bits.
      lower_bit = id_num % (1 << BASE64_BIT_SIZE)
      # Converts 6 bits to characters arranged in ASCII order.
      result = ENCODE_MAP[lower_bit] + result
      # Discard lower 6 bits.
      id_num = id_num >> BASE64_BIT_SIZE
    end

    result
  end

  # Converts a string ID to a number.
  def to_i(id_str)
    result = 0

    (0...CHAR_SIZE).each do |index|
      base64_bit = DECODE_MAP[id_str[index]]
      shift_size = (CHAR_SIZE - index - 1) * BASE64_BIT_SIZE
      result |= base64_bit << shift_size
    end

    result
  end

  # Get the time stamp from the ID.
  def get_time(id)
    if id.is_a?(String)
      id = self.to_i(id)
    end

    epoch = id >> RANDOM_BIT_SIZE
    Time.at(epoch * 0.001)
  end

  # Gets the range of minimum and maximum values at a specified time.
  def time_base_range(time)
    epoch = (time.to_f * 1000).to_i

    min_id = self.make_core(epoch, 0)
    max_id = self.make_core(epoch, (1 << RANDOM_BIT_SIZE) - 1)

    (min_id..max_id)
  end

  protected

  def make_core(epoch, random)
    # Concatenate a 48-bit timestamp with a 72-bit random number.
    id_num = (epoch << RANDOM_BIT_SIZE) | random

    # Encode like base64.
    self.to_s(id_num)
  end

  def increment
    @pre_random += 1
    if (1 << RANDOM_BIT_SIZE) <= @pre_random
      @pre_random = 0 
    end

    self.make_core(@pre_epoch, @pre_random)
  end
end