Generic ID generation

idgen.go

// A package for generating and consuming intelligent IDs.
//
// This package exposes a factory function for ID generators, that creates IDs
// that are 64-bit unsigned ints, with bits breaking down as possible:
//
//   [TYPE: 8 bits] [ID: 52 bits]
//
// - TYPE (256 options): The type of the object the ID represents.
// - ID (4.5 quadrillion options): The actual ID, depending on the indicated
//   sequence type. It should ideally be monotonically increasing so that IDs
//   are sortable by age. Could be a timestamp, Redis counter, or random number.
package idgen

import (
	"fmt"
	"time"
)

type generator func() uint64

type sequenceType string

// The types of ID sequences available for generation.
const (
	// An ID sequence that encodes the time when it was created at 1/50th of a
	// microsecond granularity. The allows the encoding ~45 years of objects
	// before needing to expand the ID space.
	// 2^56 / (50 * 1000µs * 1000ms * 60s * 60m * 24h * 365d) = 45 years
	SequenceTimestamp sequenceType = "timestamp"
)

// The bit length of the parts of the ID.
const (
	lenObjType  = 8
	lenSequence = 56
)

// The amount by which to divide the default nanosecond timestamp granularity
// fot the purposes of a longer timestamp
const nsGranularity = 20

// The offset against which all ID timestamps are based.
var epoch = time.Date(2015, time.September, 30, 0, 0, 0, 0, time.UTC)

// Create a new ID generator of the given type.
func MakeIDGenerator(objType uint8, seq sequenceType) (generator, error) {
	var generateSequence generator
	switch seq {
	case SequenceTimestamp:
		generateSequence = generateTimestampID
	default:
		return nil, fmt.Errorf("idgen: Invalid sequence type '%s'", seq)
	}

	// Position the object type in the first 8 bits
	objTypeMask := uint64(objType) << lenSequence
	generateID := func() uint64 {
		// We assume here that generateSequence() will always return 56 bits max
		return objTypeMask | generateSequence()
	}
	return generateID, nil
}

// Given an object ID, parse out the object type part.
func GetObjectTypeFromID(id uint64) uint8 {
	return uint8(id >> lenSequence)
}

// Given an object ID generated by SequenceTimestamp, parse out the timestamp.
func GetTimeFromID(id uint64) time.Time {
	// Zero the top 8 bits (the object part) of the ID
	sequence := (id << lenObjType) >> lenObjType
	return epoch.Add(time.Duration(sequence * nsGranularity))
}

// Generate a 56-bit timestamp sequence.
func generateTimestampID() uint64 {
	now := time.Now()
	// Diff is the integer difference in nanoseconds
	diff := now.Sub(epoch)
	// We do integer division to 1/50th of a microsecond, because we want to save
	// more than 2.5 years of IDs
	timestamp := diff / nsGranularity
	// Finally we convert to uint and zero the top 8 bits
	return (uint64(timestamp) << lenObjType) >> lenObjType
}

idgen.js

/**
 * Generic ID generation
 *
 * IDs are 64-bit integers, hex-encoded, with bits breaking down as follows:
 *
 *   [TYPE: 8] [ID: 52]
 *
 * TYPE (256 options): The type of the object.
 * ID (4.5 quadrillion options): The actual ID, depending on the indicated ID
 *   type. It should ideally be monotonically increasing so that IDs are
 *   sortable by age. Could be a timestamp, Redis counter, or random number.
 */
'use strict';

const ALPHABET = '0123456789abcdef'

const EPOCH = new Date('2015-07-18').getTime()

var Sequence = exports.Sequence = {
  TIMESTAMP_RAND: Symbol('timestamp_rand'),
}

const Len = {
  ALL: 16,
  TYPE: 2,
  TIME: 10,
  RAND: 4,
}

/**
 * Create a reusable ID-generation function.
 *
 * @param {number} objType
 * @param {Sequence} seqType
 * @return {function(Object=):string}
 */
exports.makeIdGenerator = function (objType, seqType) {
  if (objType != (objType|0) || 0 > objType || objType > 255) {
    throw new Error('Object type must be an integer in the range [0, 255]')
  }

  let generateSequence
  switch (seqType) {
    case Sequence.TIMESTAMP_RAND:
      generateSequence = generateTimestampWithRandId
      break
    default:
      throw new Error('Invalid sequence type: ' + String(seqType))
  }

  const objPart = (objType < 16 ? '0' : '') + objType.toString(16)
  return function generateId(opt_obj) {
    const id = objPart + generateSequence(opt_obj)

    // Sanity check
    if(id.length != Len.ALL) {
      throw new Error('IDs should be 16 characters long: ' + id)
    }
    return id
  }
}

/**
 * Get the object type from an object ID.
 *
 * @param {string} id
 * @return {number}
 */
exports.getObjectTypeFromId = function (id) {
  return parseInt(id.substr(0, Len.TYPE), 16)
}

/**
 * Get the Unix timestamp from an object ID.
 *
 * @param {string} id
 * @return {number}
 */
exports.getTimestampFromId = function (id) {
  return EPOCH + parseInt(id.substr(Len.TYPE, Len.TIME), 16)
}

/**
 * Generate a hex-encoded 56-bit timestamp-based sequence with a random part.
 *
 * The first 10 bytes represent the time in milliseconds since the EPOCH,
 * the last 4 bytes are randomly generated to reduce collisions.
 *
 * @return {string}
 */
function generateTimestampWithRandId() {
  let time = Date.now() - EPOCH
  const timestampChars = new Array(Len.TIME)
  for (let i = Len.TIME - 1; i >= 0; i--) {
    timestampChars[i] = ALPHABET.charAt(time % 16)
    time = Math.floor(time / 16)
  }
  const timestampPart = timestampChars.join('')

  const randChars = new Array(Len.RAND)
  for (let i = 0; i < Len.RAND; i++) {
    randChars[i] = Math.floor(Math.random() * 16).toString(16)
  }
  const randPart = randChars.join('')

  return timestampPart + randPart
}

idgen_test.go

package idgen

import (
	"testing"
	"time"
)

func TestMakeIDGenerator(t *testing.T) {
	_, err := MakeIDGenerator(1, "foo")
	if err == nil {
		t.Errorf("MakeIDGenerator should fail on invalid sequence type")
	}

	_, err = MakeIDGenerator(1, SequenceTimestamp)
	if err != nil {
		t.Error("MakeIDGenerator should not error on valid input")
	}
}

func TestGetObjectTypeFromID(t *testing.T) {
	expected := uint8(100)
	generate, err := MakeIDGenerator(expected, SequenceTimestamp)
	if err != nil {
		t.Error("MakeIDGenerator should not error on valid input")
	}
	for i := 0; i < 1000; i++ {
		if objType := GetObjectTypeFromID(generate()); objType != expected {
			t.Errorf("IDs should have object type %d, but found %d",
				expected, objType)
			break
		}
	}
}

func TestGetTimeFromID(t *testing.T) {
	generate, err := MakeIDGenerator(0, SequenceTimestamp)
	if err != nil {
		t.Error("MakeIDGenerator should not error on valid input")
	}
	for i := 0; i < 1000; i++ {
		idTime := GetTimeFromID(generate())
		now := time.Now()
		if (now.Unix() - idTime.Unix()) > 1 {
			t.Errorf("ID should have the Unix time %s, but was %s",
				now.Format(time.Stamp), idTime.Format(time.Stamp))
			break
		}
	}
}

func TestGenerateTimestampSequenceSufficientlyVaries(t *testing.T) {
	generate, err := MakeIDGenerator(0, SequenceTimestamp)
	if err != nil {
		t.Error("MakeIDGenerator should not error on valid input")
	}
	var lastId uint64
	dupIds := 0
	for i := 0; i < 10000; i++ {
		id := generate()
		if id == lastId {
			dupIds++
		}
		lastId = id
	}
	if dupIds != 0 {
		t.Errorf("There should not be duplicate IDs, but found %d", dupIds)
	}
}