flake_id.ex (5212B)
1 # Pleroma: A lightweight social networking server
2 # Copyright © 2017-2019 Pleroma Authors <https://pleroma.social/>
3 # SPDX-License-Identifier: AGPL-3.0-only
4
5 defmodule Pleroma.FlakeId do
6 @moduledoc """
7 Flake is a decentralized, k-ordered id generation service.
8
9 Adapted from:
10
11 * [flaky](https://github.com/nirvana/flaky), released under the terms of the Truly Free License,
12 * [Flake](https://github.com/boundary/flake), Copyright 2012, Boundary, Apache License, Version 2.0
13 """
14
15 @type t :: binary
16
17 use Ecto.Type
18 use GenServer
19 require Logger
20 alias __MODULE__
21 import Kernel, except: [to_string: 1]
22
23 defstruct node: nil, time: 0, sq: 0
24
25 @doc "Converts a binary Flake to a String"
26 def to_string(<<0::integer-size(64), id::integer-size(64)>>) do
27 Kernel.to_string(id)
28 end
29
30 def to_string(<<_::integer-size(64), _::integer-size(48), _::integer-size(16)>> = flake) do
31 encode_base62(flake)
32 end
33
34 def to_string(s), do: s
35
36 def from_string(int) when is_integer(int) do
37 from_string(Kernel.to_string(int))
38 end
39
40 for i <- [-1, 0] do
41 def from_string(unquote(i)), do: <<0::integer-size(128)>>
42 def from_string(unquote(Kernel.to_string(i))), do: <<0::integer-size(128)>>
43 end
44
45 def from_string(<<_::integer-size(128)>> = flake), do: flake
46
47 def from_string(string) when is_binary(string) and byte_size(string) < 18 do
48 case Integer.parse(string) do
49 {id, ""} -> <<0::integer-size(64), id::integer-size(64)>>
50 _ -> nil
51 end
52 end
53
54 def from_string(string) do
55 string |> decode_base62 |> from_integer
56 end
57
58 def to_integer(<<integer::integer-size(128)>>), do: integer
59
60 def from_integer(integer) do
61 <<_time::integer-size(64), _node::integer-size(48), _seq::integer-size(16)>> =
62 <<integer::integer-size(128)>>
63 end
64
65 @doc "Generates a Flake"
66 @spec get :: binary
67 def get, do: to_string(:gen_server.call(:flake, :get))
68
69 # checks that ID is is valid FlakeID
70 #
71 @spec is_flake_id?(String.t()) :: boolean
72 def is_flake_id?(id), do: is_flake_id?(String.to_charlist(id), true)
73 defp is_flake_id?([c | cs], true) when c >= ?0 and c <= ?9, do: is_flake_id?(cs, true)
74 defp is_flake_id?([c | cs], true) when c >= ?A and c <= ?Z, do: is_flake_id?(cs, true)
75 defp is_flake_id?([c | cs], true) when c >= ?a and c <= ?z, do: is_flake_id?(cs, true)
76 defp is_flake_id?([], true), do: true
77 defp is_flake_id?(_, _), do: false
78
79 # -- Ecto.Type API
80 @impl Ecto.Type
81 def type, do: :uuid
82
83 @impl Ecto.Type
84 def cast(value) do
85 {:ok, FlakeId.to_string(value)}
86 end
87
88 @impl Ecto.Type
89 def load(value) do
90 {:ok, FlakeId.to_string(value)}
91 end
92
93 @impl Ecto.Type
94 def dump(value) do
95 {:ok, FlakeId.from_string(value)}
96 end
97
98 def autogenerate, do: get()
99
100 # -- GenServer API
101 def start_link(_) do
102 :gen_server.start_link({:local, :flake}, __MODULE__, [], [])
103 end
104
105 @impl GenServer
106 def init([]) do
107 {:ok, %FlakeId{node: worker_id(), time: time()}}
108 end
109
110 @impl GenServer
111 def handle_call(:get, _from, state) do
112 {flake, new_state} = get(time(), state)
113 {:reply, flake, new_state}
114 end
115
116 # Matches when the calling time is the same as the state time. Incr. sq
117 defp get(time, %FlakeId{time: time, node: node, sq: seq}) do
118 new_state = %FlakeId{time: time, node: node, sq: seq + 1}
119 {gen_flake(new_state), new_state}
120 end
121
122 # Matches when the times are different, reset sq
123 defp get(newtime, %FlakeId{time: time, node: node}) when newtime > time do
124 new_state = %FlakeId{time: newtime, node: node, sq: 0}
125 {gen_flake(new_state), new_state}
126 end
127
128 # Error when clock is running backwards
129 defp get(newtime, %FlakeId{time: time}) when newtime < time do
130 {:error, :clock_running_backwards}
131 end
132
133 defp gen_flake(%FlakeId{time: time, node: node, sq: seq}) do
134 <<time::integer-size(64), node::integer-size(48), seq::integer-size(16)>>
135 end
136
137 defp nthchar_base62(n) when n <= 9, do: ?0 + n
138 defp nthchar_base62(n) when n <= 35, do: ?A + n - 10
139 defp nthchar_base62(n), do: ?a + n - 36
140
141 defp encode_base62(<<integer::integer-size(128)>>) do
142 integer
143 |> encode_base62([])
144 |> List.to_string()
145 end
146
147 defp encode_base62(int, acc) when int < 0, do: encode_base62(-int, acc)
148 defp encode_base62(int, []) when int == 0, do: '0'
149 defp encode_base62(int, acc) when int == 0, do: acc
150
151 defp encode_base62(int, acc) do
152 r = rem(int, 62)
153 id = div(int, 62)
154 acc = [nthchar_base62(r) | acc]
155 encode_base62(id, acc)
156 end
157
158 defp decode_base62(s) do
159 decode_base62(String.to_charlist(s), 0)
160 end
161
162 defp decode_base62([c | cs], acc) when c >= ?0 and c <= ?9,
163 do: decode_base62(cs, 62 * acc + (c - ?0))
164
165 defp decode_base62([c | cs], acc) when c >= ?A and c <= ?Z,
166 do: decode_base62(cs, 62 * acc + (c - ?A + 10))
167
168 defp decode_base62([c | cs], acc) when c >= ?a and c <= ?z,
169 do: decode_base62(cs, 62 * acc + (c - ?a + 36))
170
171 defp decode_base62([], acc), do: acc
172
173 defp time do
174 {mega_seconds, seconds, micro_seconds} = :erlang.timestamp()
175 1_000_000_000 * mega_seconds + seconds * 1000 + :erlang.trunc(micro_seconds / 1000)
176 end
177
178 defp worker_id do
179 <<worker::integer-size(48)>> = :crypto.strong_rand_bytes(6)
180 worker
181 end
182 end