jcs.org
A skeleton web application configured to use Sinatra and ActiveRecord
1#
2# Copyright (c) 2019 joshua stein <jcs@jcs.org>
3#
4# Permission to use, copy, modify, and distribute this software for any
5# purpose with or without fee is hereby granted, provided that the above
6# copyright notice and this permission notice appear in all copies.
7#
8# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15#
16
17class UniqueId
18 #
19 # (roughly) time-sortable, incrementing ids that don't require an
20 # auto_increment database table and will not collide between processes and
21 # servers
22 #
23 # uses 64 bits, the size of a bigint in mysql
24 #
25 # [0, 32] = (time.to_f - EPOCH) * 10
26 # [32, 4] = node id, 0 to 15
27 # [36, 16] = pid
28 # [52, 12] = sequence, 0 to 4095
29 #
30 # this gives us 4096 ids per second, per pid, per node/server
31 # sequences are shared among threads in a process
32 #
33
34 # jan 1, 2019 00:00:00 +0000
35 EPOCH = 1546300800
36
37 LENGTHS = {
38 :time => 32,
39 :node => 4,
40 :pid => 16,
41 :sequence => 12,
42 }.freeze
43
44 attr_reader :binary, :time, :node, :pid, :sequence
45
46 def self.build_binary(time, node, pid, seq)
47 r = sprintf("%0#{LENGTHS[:time]}b%0#{LENGTHS[:node]}b" <<
48 "%0#{LENGTHS[:pid]}b%0#{LENGTHS[:sequence]}b", time, node, pid, seq)
49
50 if r.length != 64
51 raise "created invalid length binary #{r.inspect} (#{r.length})"
52 end
53
54 r
55 end
56
57 def self.get
58 self.get_binary.to_i(2)
59 end
60
61 def self.get_binary
62 self.build_binary((Time.now.to_i - EPOCH), self.node,
63 self.truncate_pid($$), self.sequence)
64 end
65
66 def self.node
67 class_variable_defined?("@@node") ? @@node : 0
68 end
69 def self.node=(what)
70 @@node = what.to_i
71 end
72
73 def self.sequence
74 ret = 0
75
76 (@@sequence_mutex ||= Mutex.new).synchronize do
77 @@sequence ||= 0
78
79 if @@sequence >= (2 ** LENGTHS[:sequence]) - 1
80 ret = @@sequence = 0
81 else
82 ret = (@@sequence += 1)
83 end
84 end
85
86 ret
87 end
88
89 def self.parse(i)
90 UniqueId.new(i)
91 end
92
93 def self.truncate_pid(pid)
94 # pid is technically 17 bits on openbsd, capped at 99999, so cap at 16 bits
95 pid = pid.to_s(2)
96 if pid.length > LENGTHS[:pid]
97 pid = pid[pid.length - LENGTHS[:pid], LENGTHS[:pid]]
98 end
99 pid.to_i(2)
100 end
101
102 def initialize(i)
103 if !i || i > (2 ** 64) - 1 || i < 0
104 raise "invalid id #{i}"
105 end
106
107 @binary = sprintf("%064b", i)
108
109 @time = Time.at(EPOCH + @binary[0, LENGTHS[:time]].to_i(2))
110 z = LENGTHS[:time]
111
112 @node = @binary[z, LENGTHS[:node]].to_i(2)
113 z += LENGTHS[:node]
114
115 @pid = @binary[z, LENGTHS[:pid]].to_i(2)
116 z += LENGTHS[:pid]
117
118 @sequence = @binary[z, LENGTHS[:sequence]].to_i(2)
119 end
120
121 def to_i
122 @binary.to_i(2)
123 end
124end