git.squeep.com Git - akkoma/blob - lib/pleroma/flake_id.ex

   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   @behaviour 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   # -- Ecto.Type API
  70   @impl Ecto.Type
  71   def type, do: :uuid
  72
  73   @impl Ecto.Type
  74   def cast(value) do
  75     {:ok, FlakeId.to_string(value)}
  76   end
  77
  78   @impl Ecto.Type
  79   def load(value) do
  80     {:ok, FlakeId.to_string(value)}
  81   end
  82
  83   @impl Ecto.Type
  84   def dump(value) do
  85     {:ok, FlakeId.from_string(value)}
  86   end
  87
  88   def autogenerate, do: get()
  89
  90   # -- GenServer API
  91   def start_link do
  92     :gen_server.start_link({:local, :flake}, __MODULE__, [], [])
  93   end
  94
  95   @impl GenServer
  96   def init([]) do
  97     {:ok, %FlakeId{node: worker_id(), time: time()}}
  98   end
  99
 100   @impl GenServer
 101   def handle_call(:get, _from, state) do
 102     {flake, new_state} = get(time(), state)
 103     {:reply, flake, new_state}
 104   end
 105
 106   # Matches when the calling time is the same as the state time. Incr. sq
 107   defp get(time, %FlakeId{time: time, node: node, sq: seq}) do
 108     new_state = %FlakeId{time: time, node: node, sq: seq + 1}
 109     {gen_flake(new_state), new_state}
 110   end
 111
 112   # Matches when the times are different, reset sq
 113   defp get(newtime, %FlakeId{time: time, node: node}) when newtime > time do
 114     new_state = %FlakeId{time: newtime, node: node, sq: 0}
 115     {gen_flake(new_state), new_state}
 116   end
 117
 118   # Error when clock is running backwards
 119   defp get(newtime, %FlakeId{time: time}) when newtime < time do
 120     {:error, :clock_running_backwards}
 121   end
 122
 123   defp gen_flake(%FlakeId{time: time, node: node, sq: seq}) do
 124     <<time::integer-size(64), node::integer-size(48), seq::integer-size(16)>>
 125   end
 126
 127   defp nthchar_base62(n) when n <= 9, do: ?0 + n
 128   defp nthchar_base62(n) when n <= 35, do: ?A + n - 10
 129   defp nthchar_base62(n), do: ?a + n - 36
 130
 131   defp encode_base62(<<integer::integer-size(128)>>) do
 132     integer
 133     |> encode_base62([])
 134     |> List.to_string()
 135   end
 136
 137   defp encode_base62(int, acc) when int < 0, do: encode_base62(-int, acc)
 138   defp encode_base62(int, []) when int == 0, do: '0'
 139   defp encode_base62(int, acc) when int == 0, do: acc
 140
 141   defp encode_base62(int, acc) do
 142     r = rem(int, 62)
 143     id = div(int, 62)
 144     acc = [nthchar_base62(r) | acc]
 145     encode_base62(id, acc)
 146   end
 147
 148   defp decode_base62(s) do
 149     decode_base62(String.to_charlist(s), 0)
 150   end
 151
 152   defp decode_base62([c | cs], acc) when c >= ?0 and c <= ?9,
 153     do: decode_base62(cs, 62 * acc + (c - ?0))
 154
 155   defp decode_base62([c | cs], acc) when c >= ?A and c <= ?Z,
 156     do: decode_base62(cs, 62 * acc + (c - ?A + 10))
 157
 158   defp decode_base62([c | cs], acc) when c >= ?a and c <= ?z,
 159     do: decode_base62(cs, 62 * acc + (c - ?a + 36))
 160
 161   defp decode_base62([], acc), do: acc
 162
 163   defp time do
 164     {mega_seconds, seconds, micro_seconds} = :erlang.timestamp()
 165     1_000_000_000 * mega_seconds + seconds * 1000 + :erlang.trunc(micro_seconds / 1000)
 166   end
 167
 168   defp worker_id do
 169     <<worker::integer-size(48)>> = :crypto.strong_rand_bytes(6)
 170     worker
 171   end
 172 end