Page MenuHomePhorge
Files F85648900

No OneTemporary
Actions

Size
13 KB
Referenced Files
None
Subscribers
None

View Options

diff --git a/README.md b/README.md
index d8022eb..9a097fc 100644
--- a/README.md
+++ b/README.md
@@ -1,21 +1,35 @@
-# FlakeId
+# ❄ FlakeID
-**TODO: Add description**
+> Decentralized, k-ordered ID generation service
## Installation
-If [available in Hex](https://hex.pm/docs/publish), the package can be installed
-by adding `flake_id` to your list of dependencies in `mix.exs`:
+Add `flake_id` to your list of dependencies in `mix.exs`:
```elixir
def deps do
[
{:flake_id, "~> 0.1.0"}
]
end
```
-Documentation can be generated with [ExDoc](https://github.com/elixir-lang/ex_doc)
-and published on [HexDocs](https://hexdocs.pm). Once published, the docs can
-be found at [https://hexdocs.pm/flake_id](https://hexdocs.pm/flake_id).
+## Usage
+```elixir
+iex> FlakeID.get()
+"9n3171dJZpdD77K3DU"
+```
+
+See [https://hexdocs.pm/flake_id](https://hexdocs.pm/flake_id) for the complete documentation.
+
+## Prior Art
+
+* [flaky](https://github.com/nirvana/flaky), released under the terms of the Truly Free License,
+* [Flake](https://github.com/boundary/flake), Copyright 2012, Boundary, Apache License, Version 2.0
+
+## Copyright and License
+
+Copyright © 2017-2019 [Pleroma Authors](https://pleroma.social/)
+
+FlakeID source code is licensed under the GNU LGPLv3 License.
diff --git a/lib/flake_id.ex b/lib/flake_id.ex
index a9660fd..af46a17 100644
--- a/lib/flake_id.ex
+++ b/lib/flake_id.ex
@@ -1,18 +1,157 @@
-defmodule FlakeId do
+# FlakeID: Decentralized, k-ordered ID generation service
+# Copyright © 2017-2019 Pleroma Authors <https://pleroma.social/>
+# SPDX-License-Identifier: LGPL-3.0-only
+
+defmodule FlakeID do
@moduledoc """
- Documentation for FlakeId.
+ Decentralized, k-ordered ID generation service.
"""
+ import Kernel, except: [to_string: 1]
+
@doc """
- Hello world.
+ Converts a binary Flake to a String
## Examples
- iex> FlakeId.hello()
- :world
+ iex> FlakeID.to_string(<<0, 0, 1, 109, 67, 124, 251, 125, 95, 28, 30, 59, 36, 42, 0, 0>>)
+ "9n2ciuz1wdesFnrGJU"
"""
- def hello do
- :world
+
+ # compatibility with older serial integers
+ def to_string(<<0::integer-size(64), id::integer-size(64)>>) do
+ Kernel.to_string(id)
+ end
+
+ def to_string(<<_::integer-size(64), _::integer-size(48), _::integer-size(16)>> = binary_flake) do
+ encode_base62(binary_flake)
+ end
+
+ def to_string(string), do: string
+
+ @doc """
+ Converts a String to a binary Flake
+
+ ## Examples
+
+ iex> FlakeID.from_string("9n2ciuz1wdesFnrGJU")
+ <<0, 0, 1, 109, 67, 124, 251, 125, 95, 28, 30, 59, 36, 42, 0, 0>>
+
+ """
+ @spec from_string(String.t() | integer) :: nil | <<_::128>>
+ def from_string(string)
+
+ # zero or -1 is a null flake
+ for i <- [-1, 0] do
+ def from_string(unquote(i)), do: <<0::integer-size(128)>>
+ def from_string(unquote(Kernel.to_string(i))), do: <<0::integer-size(128)>>
end
+
+ def from_string(int) when is_integer(int) do
+ int
+ |> Kernel.to_string()
+ |> from_string()
+ end
+
+ def from_string(<<_::integer-size(128)>> = flake), do: flake
+
+ def from_string(string) when is_binary(string) and byte_size(string) < 18 do
+ case Integer.parse(string) do
+ {id, ""} -> <<0::integer-size(64), id::integer-size(64)>>
+ _ -> nil
+ end
+ end
+
+ def from_string(string), do: string |> decode_base62 |> from_integer
+
+ @doc """
+ Converts a binary Flake to an integer
+
+ ## Examples
+
+ iex> FlakeID.to_integer(<<0, 0, 1, 109, 67, 124, 251, 125, 95, 28, 30, 59, 36, 42, 0, 0>>)
+ 28939165907792829150732718047232
+
+ """
+ @spec to_integer(<<_::128>>) :: non_neg_integer
+ def to_integer(binary_flake)
+ def to_integer(<<integer::integer-size(128)>>), do: integer
+
+ @doc """
+ Converts an integer to a binary Flake
+
+ ## Examples
+
+ iex> FlakeID.from_integer(28939165907792829150732718047232)
+ <<0, 0, 1, 109, 67, 124, 251, 125, 95, 28, 30, 59, 36, 42, 0, 0>>
+
+ """
+ @spec from_integer(integer) :: <<_::128>>
+ def from_integer(integer) do
+ <<_time::integer-size(64), _node::integer-size(48), _seq::integer-size(16)>> =
+ <<integer::integer-size(128)>>
+ end
+
+ @doc """
+ Generates a string with Flake
+ """
+ @spec get :: String.t()
+ def get, do: FlakeID.Worker.get() |> to_string()
+
+ @doc """
+ Checks that ID is a valid FlakeID
+
+ ## Examples
+
+ iex> FlakeID.flake_id?("9n2ciuz1wdesFnrGJU")
+ true
+
+ iex> FlakeID.flake_id?("#cofe")
+ false
+
+ iex> FlakeID.flake_id?("pleroma.social")
+ false
+ """
+ @spec flake_id?(String.t()) :: boolean
+ def flake_id?(id), do: flake_id?(String.to_charlist(id), true)
+
+ defp flake_id?([c | cs], true) when c >= ?0 and c <= ?9, do: flake_id?(cs, true)
+ defp flake_id?([c | cs], true) when c >= ?A and c <= ?Z, do: flake_id?(cs, true)
+ defp flake_id?([c | cs], true) when c >= ?a and c <= ?z, do: flake_id?(cs, true)
+ defp flake_id?([], true), do: true
+ defp flake_id?(_, _), do: false
+
+ defp encode_base62(<<integer::integer-size(128)>>) do
+ integer
+ |> encode_base62([])
+ |> List.to_string()
+ end
+
+ defp encode_base62(int, []) when int == 0, do: '0'
+ defp encode_base62(int, acc) when int == 0, do: acc
+
+ defp encode_base62(int, acc) do
+ r = rem(int, 62)
+ id = div(int, 62)
+ acc = [nthchar_base62(r) | acc]
+ encode_base62(id, acc)
+ end
+
+ defp decode_base62(s), do: decode_base62(String.to_charlist(s), 0)
+
+ defp decode_base62([c | cs], acc) when c >= ?0 and c <= ?9,
+ do: decode_base62(cs, 62 * acc + (c - ?0))
+
+ defp decode_base62([c | cs], acc) when c >= ?A and c <= ?Z,
+ do: decode_base62(cs, 62 * acc + (c - ?A + 10))
+
+ defp decode_base62([c | cs], acc) when c >= ?a and c <= ?z,
+ do: decode_base62(cs, 62 * acc + (c - ?a + 36))
+
+ defp decode_base62([], acc), do: acc
+
+ defp nthchar_base62(n) when n <= 9, do: ?0 + n
+ defp nthchar_base62(n) when n <= 35, do: ?A + n - 10
+ defp nthchar_base62(n), do: ?a + n - 36
end
diff --git a/lib/flake_id/application.ex b/lib/flake_id/application.ex
index 4af3b55..1b8e223 100644
--- a/lib/flake_id/application.ex
+++ b/lib/flake_id/application.ex
@@ -1,19 +1,22 @@
-defmodule FlakeId.Application do
+# FlakeID: Decentralized, k-ordered ID generation service
+# Copyright © 2017-2019 Pleroma Authors <https://pleroma.social/>
+# SPDX-License-Identifier: LGPL-3.0-only
+
+defmodule FlakeID.Application do
# See https://hexdocs.pm/elixir/Application.html
# for more information on OTP Applications
@moduledoc false
use Application
def start(_type, _args) do
children = [
- # Starts a worker by calling: FlakeId.Worker.start_link(arg)
- # {FlakeId.Worker, arg}
+ FlakeID.Worker
]
# See https://hexdocs.pm/elixir/Supervisor.html
# for other strategies and supported options
- opts = [strategy: :one_for_one, name: FlakeId.Supervisor]
+ opts = [strategy: :one_for_one, name: FlakeID.Supervisor]
Supervisor.start_link(children, opts)
end
end
diff --git a/lib/flake_id/worker.ex b/lib/flake_id/worker.ex
new file mode 100644
index 0000000..b502389
--- /dev/null
+++ b/lib/flake_id/worker.ex
@@ -0,0 +1,70 @@
+# FlakeID: Decentralized, k-ordered ID generation service
+# Copyright © 2017-2019 Pleroma Authors <https://pleroma.social/>
+# SPDX-License-Identifier: LGPL-3.0-only
+
+defmodule FlakeID.Worker do
+ @moduledoc false
+
+ use GenServer
+
+ defstruct node: nil, time: 0, sq: 0
+
+ @type state :: %__MODULE__{
+ node: non_neg_integer,
+ time: non_neg_integer,
+ sq: non_neg_integer
+ }
+
+ def start_link(_) do
+ GenServer.start_link(__MODULE__, [], name: __MODULE__)
+ end
+
+ @impl true
+ @spec init([]) :: {:ok, state}
+ def init([]) do
+ {:ok, %__MODULE__{node: worker_id(), time: time()}}
+ end
+
+ @impl true
+ def handle_call(:get, _from, state) do
+ {flake, new_state} = get(time(), state)
+ {:reply, flake, new_state}
+ end
+
+ @spec get :: binary
+ def get, do: GenServer.call(__MODULE__, :get)
+
+ # Matches when the calling time is the same as the state time. Incr. sq
+ @spec get(non_neg_integer, state) ::
+ {<<_::128>>, state} | {:error, :clock_running_backwards}
+ def get(time, %__MODULE__{time: time} = state) do
+ new_state = %__MODULE__{state | sq: state.sq + 1}
+ {gen_flake(new_state), new_state}
+ end
+
+ # Matches when the times are different, reset sq
+ def get(newtime, %__MODULE__{time: time} = state) when newtime > time do
+ new_state = %__MODULE__{state | time: newtime, sq: 0}
+ {gen_flake(new_state), new_state}
+ end
+
+ # Error when clock is running backwards
+ def get(newtime, %__MODULE__{time: time}) when newtime < time do
+ {:error, :clock_running_backwards}
+ end
+
+ @spec gen_flake(state) :: <<_::128>>
+ def gen_flake(%__MODULE__{time: time, node: node, sq: seq}) do
+ <<time::integer-size(64), node::integer-size(48), seq::integer-size(16)>>
+ end
+
+ def time do
+ {mega_seconds, seconds, micro_seconds} = :erlang.timestamp()
+ 1_000_000_000 * mega_seconds + seconds * 1000 + :erlang.trunc(micro_seconds / 1000)
+ end
+
+ def worker_id do
+ <<worker::integer-size(48)>> = :crypto.strong_rand_bytes(6)
+ worker
+ end
+end
diff --git a/mix.exs b/mix.exs
index a4dd892..bf65e43 100644
--- a/mix.exs
+++ b/mix.exs
@@ -1,28 +1,28 @@
-defmodule FlakeId.MixProject do
+defmodule FlakeID.MixProject do
use Mix.Project
def project do
[
app: :flake_id,
version: "0.1.0",
- elixir: "~> 1.9",
+ elixir: "~> 1.8",
start_permanent: Mix.env() == :prod,
deps: deps()
]
end
# Run "mix help compile.app" to learn about applications.
def application do
[
extra_applications: [:logger],
- mod: {FlakeId.Application, []}
+ mod: {FlakeID.Application, []}
]
end
# Run "mix help deps" to learn about dependencies.
defp deps do
[
{:credo, "~> 1.1.0", only: [:dev, :test], runtime: false}
]
end
end
diff --git a/test/flake_id/worker_test.exs b/test/flake_id/worker_test.exs
new file mode 100644
index 0000000..046288c
--- /dev/null
+++ b/test/flake_id/worker_test.exs
@@ -0,0 +1,38 @@
+defmodule FlakeID.WorkerTest do
+ use ExUnit.Case, async: true
+
+ alias FlakeID.Worker
+
+ test "get/1" do
+ flake = Worker.get()
+
+ assert is_binary(flake)
+ assert <<_::integer-size(128)>> = flake
+ end
+
+ describe "get/2" do
+ test "increment `:sq` when the calling time is the same as the state time" do
+ time = Worker.time()
+ node = Worker.worker_id()
+ state = %Worker{time: time, node: node, sq: 0}
+
+ assert {<<_::integer-size(128)>>, %Worker{node: ^node, time: ^time, sq: 1}} =
+ Worker.get(time, state)
+ end
+
+ test "reset `:sq` when the times are different" do
+ time = Worker.time()
+ node = Worker.worker_id()
+ state = %Worker{time: time - 1, node: node, sq: 42}
+
+ assert {<<_::integer-size(128)>>, %Worker{time: ^time, sq: 0}} = Worker.get(time, state)
+ end
+
+ test "wrror when clock is running backwards" do
+ time = Worker.time()
+ state = %Worker{time: time + 1}
+
+ assert Worker.get(time, state) == {:error, :clock_running_backwards}
+ end
+ end
+end
diff --git a/test/flake_id_test.exs b/test/flake_id_test.exs
index 397bb5c..8bcad76 100644
--- a/test/flake_id_test.exs
+++ b/test/flake_id_test.exs
@@ -1,8 +1,86 @@
-defmodule FlakeIdTest do
- use ExUnit.Case
- doctest FlakeId
+defmodule FlakeIDTest do
+ use ExUnit.Case, async: true
+ doctest FlakeID
- test "greets the world" do
- assert FlakeId.hello() == :world
+ @flake_string "9n2ciuz1wdesFnrGJU"
+ @flake_binary <<0, 0, 1, 109, 67, 124, 251, 125, 95, 28, 30, 59, 36, 42, 0, 0>>
+ @flake_integer 28_939_165_907_792_829_150_732_718_047_232
+
+ test "flake_id?/1" do
+ assert FlakeID.flake_id?(@flake_string)
+ refute FlakeID.flake_id?("http://example.com/activities/3ebbadd1-eb14-4e20-8118-b6f79c0c7b0b")
+ refute FlakeID.flake_id?("#cofe")
+ end
+
+ test "get/0" do
+ flake = FlakeID.get()
+
+ assert String.valid?(flake)
+ assert FlakeID.flake_id?(flake)
+ end
+
+ describe "to_string/1" do
+ test "with binary" do
+ assert FlakeID.to_string(@flake_binary) == @flake_string
+
+ bin = <<1::integer-size(64), 2::integer-size(48), 3::integer-size(16)>>
+ assert FlakeID.to_string(bin) == "LygHa16ApeN"
+ end
+
+ test "does nothing with other types" do
+ assert FlakeID.to_string("cofe") == "cofe"
+ assert FlakeID.to_string(42) == 42
+ end
+ end
+
+ describe "from_string/1" do
+ test "with a flake string" do
+ assert FlakeID.from_string(@flake_string) == @flake_binary
+ end
+
+ test "with an integer" do
+ assert FlakeID.from_string(42) == <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 42>>
+ end
+
+ test "with an integer as string" do
+ assert FlakeID.from_string("42") == <<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 42>>
+ end
+
+ test "with a flake binary" do
+ assert FlakeID.from_string(@flake_binary) == @flake_binary
+ end
+
+ test "with a non flake string" do
+ assert FlakeID.from_string("cofe") == nil
+ end
+ end
+
+ test "to_integer/1" do
+ assert FlakeID.to_integer(@flake_binary) == @flake_integer
+ end
+
+ test "from_integer/1" do
+ assert FlakeID.from_integer(@flake_integer) == @flake_binary
+ end
+
+ describe "fake flakes (compatibility with older serial integers)" do
+ test "from_string/1" do
+ fake_flake = <<0::integer-size(64), 42::integer-size(64)>>
+ assert FlakeID.from_string("42") == fake_flake
+ assert FlakeID.from_string(42) == fake_flake
+ end
+
+ test "to_string/1" do
+ fake_flake = <<0::integer-size(64), 42::integer-size(64)>>
+ assert FlakeID.to_string(fake_flake) == "42"
+ end
+
+ test "zero or -1 is a null flake" do
+ null_flake = <<0::integer-size(128)>>
+ assert FlakeID.from_string(0) == null_flake
+ assert FlakeID.from_string(-1) == null_flake
+ assert FlakeID.from_string("0") == null_flake
+ assert FlakeID.from_string("-1") == null_flake
+ end
end
end

File Metadata

Mime Type
text/x-diff
Expires
Fri, Aug 28, 10:43 PM (1 d, 2 h)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
1736010
Default Alt Text
(13 KB)

Event Timeline