id_server.erl

-module(id_server).

-behavior(gen_server).
-export([init/1, code_change/3, terminate/2]).
-export([handle_call/3, handle_cast/2, handle_info/2]).


% Unlike Snowflake (Twitter) or Flake (boundary), one of the goals here is for
% IDs to be scattered. This is because it is assumed that there will be some
% kind of sorted index on IDs. In that case, IDs that correlate with time would
% cause the server that owns that portion of the index to ALWAYS be super hot.
% This is why App Engine whent from roughly ordered IDs to scattered IDs.
%
% Of course, if IDs are indexed in a non-ordered way, then this isn't a problem.
% Therefore, one could argue that the problem lies with the indexing choice,
% not the ID selection choice. Meh.
%
% To achieve scalability, delegation is used: there is a root server that can
% allocate many ids to other servers, which can further delegate as traffic
% increases.
%
% Delegation not only reduces the amount of traffic to the root server,
% it ensures that the root server does not need to be up all the time.
% When the root server (or more generally, a parent server) is down, delegatees
% can continue to operate until they've run out of IDS.


-export([new/0, new/1]).
-export([get_id/1, get_ids/2]).


new() ->
  gen_server:start(?MODULE, default, [])
.


new(InitialState) ->
  gen_server:start(?MODULE, InitialState, [])
.


get_id(Server) ->
  [{Id, Id}] = gen_server:call(Server, {get_ids, 1}),
  Id
.


get_ids(Server, HowMany) ->
  gen_server:call(Server, {get_ids, HowMany})
.


% TODO: Implement return_ids.


-record(state, {block_last=8192,
                next_id=1,
                do_not_use,

                % Configuration that generally doesn't change.
                block_size=8192,  % 2^13
                % TODO: To support delegation, we must replace this with a
                % union of intervals, which would be like do_not_use, except
                % that this is the usable set (perhans, s/max_id/usable/).
                max_id=18446744073709551616  % 2^64
               }).


init(default) ->
    init(#state{do_not_use=[]})
;
init(InitialState=#state{do_not_use=DoNotUse}) when is_list(DoNotUse) ->
  {ok, InitialState}
.


code_change(_OldVersion, State, _Extra) ->
  {ok, State}
.


terminate(_Reason, _State) ->
  ok
.


handle_call({get_ids, HowMany}, _From, State) ->
  {Ids, NewState} = server_get_ids(HowMany, State),
  {reply, Ids, NewState}
;
handle_call(UnknownMessage, From, State) ->
  io:format("Unknown call from ~w: ~p", [From, UnknownMessage]),
  {noreply, State}
.


handle_cast(UnknownMessage, State) ->
  io:format("Unknown cast: ~p", [UnknownMessage]),
  {noreply, State}
.


handle_info(UnknownMessage, State) ->
  io:format("Unknown info: ~p", [UnknownMessage]),
  {noreply, State}
.


server_get_ids(HowMany, S=#state{}) ->
  server_get_ids(HowMany, S, [])
.


server_get_ids(HowMany,
               S=#state{block_last=LastId, next_id=NextId,
                        do_not_use=DoNotUse},
               SoFar) ->
  case HowMany > 0 of
    % TODO: Handle negative. In that case, something bad happend. Could be our
    % fault or caller's fault.
    false -> {SoFar, S};
    true ->
      Last = lists:min([LastId, NextId + HowMany - 1]),
      Progress = Last - NextId + 1,
      NewState = case Last == LastId of
        false -> S#state{next_id=Last + 1};
        true ->
          #state{block_size=BlockSize, max_id=MaxId} = S,
          New = {NewFirst, NewLast} = reserve(BlockSize, MaxId, DoNotUse),
          S#state{block_last=NewLast,
                  next_id=NewFirst,
                  do_not_use=[New | DoNotUse]}
      end,
      server_get_ids(HowMany - Progress,
                     NewState,
                     [{NextId, Last} | SoFar])
  end
.


% Test:
%   10> L0 = [].                                
%   []
%   11> L1 = [id_server:reserve(L0, 2, 6) | L0].
%   [{3,4}]
%   12> L2 = [id_server:reserve(L1, 2, 6) | L1].
%   [{1,2},{3,4}]
%   13> L3 = [id_server:reserve(L2, 2, 6) | L2].
%   [{5,6},{1,2},{3,4}]
reserve(Size, MaxId, DoNotUse) ->
  % Pick random number that is a multiple of Size.
  % TODO: If MaxId is not divisible by Size, there are some IDs that cannot be
  % picked. The number of such IDs is < Size. Fix this.
  % TODO: Should be able to pass uniform a number closer to MaxId / Size...
  Last = (random:uniform(MaxId) div Size) * Size,
  First = Last - Size + 1,
  case collides({First, Last}, DoNotUse) of
    false -> {First, Last};

    % Try again. If IDs are requested enough times, this is going to happen more
    % and more often.
    % TODO: If we start approaching that situation, use a more efficient method.
    true -> reserve(Size, MaxId, DoNotUse)
  end
.


collides(Interval, DoNotUse) ->
  lists:any(fun(OldInterval) -> intersect(Interval, OldInterval) end,
            DoNotUse)
.


% Test:
%   > id_server:intersect({5, 10}, {11, 15}).
%   false
%   > id_server:intersect({5, 10}, {10, 15}).
%   true
%   > id_server:intersect({5, 10}, {0, 4}).  
%   false
%   > id_server:intersect({5, 10}, {0, 5}).
%   true
%   > id_server:intersect({5, 10}, {0, 7}).
%   true
%   > id_server:intersect({5, 10}, {7, 12}).
%   true
%   > id_server:intersect({5, 10}, {6, 7}). 
%   true
%   > id_server:intersect({5, 10}, {0, 100}).
%   true
intersect({First, Last}, {OtherFirst, OtherLast}) ->
   Not = Last < OtherFirst orelse OtherLast < First,
   not Not
.

intervals.erl

-module(intervals).

-export([new/0, new/1]).
-export([size/1]).

-compile(export_all).

% A "union" is a the (mathematical) union of a set of "intervals". An interval
% is the set of integers >= First, and <= Last. Intervals are represented as
% {First, Last} tuples.


% private
-record(union, {intervals, size}).


new() ->
  #union{}
.


new(InitialIntervals) ->
  Intervals = compact(InitialIntervals),
  #union{intervals=Intervals,
         size=initial_size(Intervals)}
.


size(Self=#union{}) ->
  Self#union.size
.


% TODO:


union(#union{intervals=I1}, #union{intervals=I2}) ->
  new(lists:merge(I1, I2))
.


% intersection(One, Another)
% difference(One, Another)

% superset(One, Another)
% contains_element(Self, Element)


pick(Self) ->
  [{Result, Result}] = pick_many(Self, 1),
  Result
.


pick_many(Self, HowMany) ->
  ok
.


% Turns a gumble of intervals into a sorted list of disjoin intervals.
% N.B.: Since we are dealing with sets of integers, and boundaries are
% inclusive, {X, Y} and {Y + 1, Z} should be joined.
%
% Test:
%   215> intervals:compact([]).
%   []
%   216> intervals:compact([{1,2}]).
%   [{1,2}]
%   217> intervals:compact([{1,5}, {2,10}]).
%   [{1,10}]
%   229> intervals:compact([{1,5}, {7,8}, {2,10}]).
%   [{1,10}]
%   230> intervals:compact([{1,5}, {7,8}, {3,10}, {2,2}]).
%   [{1,10}]
%   232> intervals:compact([{1,5}, {7,8}, {3,10}, {2,2}, {-10,-2}]). 
%   [{-10,-2},{1,10}]
%   233> intervals:compact([{1,5}, {7,8}, {3,10}, {2,2}, {-10,-1}]).
%   [{-10,-1},{1,10}]
%   234> intervals:compact([{1,5}, {7,8}, {3,10}, {2,2}, {-10,0}]). 
%   [{-10,10}]
compact(Intervals) ->
  % Perhaps, foldr could be used to avoid the last reverse.
  lists:reverse(lists:foldl(
    fun(I={First, Last}, SoFar) ->
      case SoFar of
        [] -> [I];
        [{OldFirst, OldLast} | Rest] ->
          case {First > OldLast + 1, OldLast >= Last} of
            {true, _} -> [{First, Last} | SoFar];
            {false, true} -> SoFar;
            {false, false} -> [{OldFirst, Last} | Rest]
          end
      end
    end,
    [],
    lists:sort(Intervals)))
.


initial_size(Intervals) ->
  lists:foldl(fun({First, Last}, SoFar) -> SoFar + Last - First + 1 end,
              0,
              Intervals)
.