module NoBrainer::Document::PrimaryKey::Generator

Constants

BASE_TABLE
ID_STR_LENGTH

Total: 83 bits With 14 digits in [A-Za-z0-9], we can represent 83 bits: Math.log(62**14)/Math.log(2) = 83.35

MACHINE_ID_BITS

24 bits of machine id 0.1% of chance to have a collision with 183 servers: Math.sqrt(-2*(2**24)*Math.log(0.999)) = 183.2 1% of chance to have a collision with ~580 servers. When using more than 500 machines, it’s therefore a good idea to set the machine_id manually to avoid collisions. XXX This is referenced in nobrainer/config.rb#default_machine_id

MACHINE_ID_MASK
MACHINE_ID_SHIFT
PID_BITS

15 bits for the current pid. We wouldn’t need it if the sequence number was on a piece of shared memory :)

PID_MASK
PID_SHIFT
SEQUENCE_BITS

14 bits of sequence number. max 16k values per 1s slices. We want something >10k because we want to be able to do high speed inserts on a single process for future benchmarks.

SEQUENCE_MASK
SEQUENCE_SHIFT
TIMESTAMP_BITS

30 bits timestamp with 1s resolution -> We overflow in year 2048. Good enough. Math.log(Time.parse(‘2048-01-01’).to_f - TIME_OFFSET)/Math.log(2) = 29.999

TIMESTAMP_MASK
TIMESTAMP_SHIFT
TIME_OFFSET

Public Class Methods

_generate() click to toggle source
# File lib/no_brainer/document/primary_key/generator.rb, line 45
def self._generate
  timestamp = (Time.now.to_i - TIME_OFFSET) & TIMESTAMP_MASK

  unless @last_timestamp == timestamp
    # more noise is better in the ID, but we prefer to avoid
    # wrapping the sequences so that Model.last on a single
    # machine returns the latest created document.
    @first_sequence = sequence = rand(SEQUENCE_MASK/2)
    @last_timestamp = timestamp
  else
    sequence = (@sequence + 1) & SEQUENCE_MASK
    raise Retry if @first_sequence == sequence
  end
  @sequence = sequence

  machine_id = NoBrainer::Config.machine_id & MACHINE_ID_MASK

  pid = Process.pid & PID_MASK

  (timestamp << TIMESTAMP_SHIFT) | (sequence << SEQUENCE_SHIFT) |
    (machine_id << MACHINE_ID_SHIFT) | (pid << PID_SHIFT)
rescue Retry
  sleep 0.1
  retry
end
convert_to_alphanum(id) click to toggle source
# File lib/no_brainer/document/primary_key/generator.rb, line 71
def self.convert_to_alphanum(id)
  result = []
  until id.zero?
    id, r = id.divmod(BASE_TABLE.size)
    result << BASE_TABLE[r]
  end
  result.reverse.join.rjust(ID_STR_LENGTH, BASE_TABLE[0])
end
field_type() click to toggle source
# File lib/no_brainer/document/primary_key/generator.rb, line 85
def self.field_type
  String
end
generate() click to toggle source
# File lib/no_brainer/document/primary_key/generator.rb, line 81
def self.generate
  convert_to_alphanum(@lock.synchronize { _generate })
end