Module rt_chord

Routing Table.

Copyright © 2007-2013 Zuse Institute Berlin

Version: $Id$

Behaviours: rt_beh.

Authors: Thorsten Schuett (schuett@zib.de).

Description

Routing Table

Data Types

client_key()

client_key() = [unicode_char()]

custom_message()

custom_message() = {rt_get_node,
                    Source_PID :: comm:mypid(),
                    Index :: index()}
                 | {rt_get_node_response,
                    Index :: index(),
                    Node :: node:node_type()}

userdevguide-end rt_chord:types

external_rt()

abstract datatype: external_rt()

index()

index() = {pos_integer(), non_neg_integer()}

key()

key() = 0..340282366920938463463374607431768211455

128 bit numbers

rt()

abstract datatype: rt()

unicode_char()

unicode_char() = 0..55295 | 57344..65533 | 65536..1114111

Function Index

activate/1Activate the routing table.
add_range/2Adds the given range, i.e.
check/5Notifies the dht_node and failure detector if the routing table changed.
check/6Notifies the dht_node if the (external) routing table changed.
check_config/0Checks whether config parameters of the rt_chord process exist and are valid.
client_key_to_binary/1
dump/1Dumps the RT state for output in the web interface.
empty_ext/1
export_rt_to_dht_node/2
filter_dead_node/3Removes dead nodes from the routing table.
get_key_segment/1
get_random_in_interval/1Gets input similar to what intervals:get_bounds/1 returns and calculates a random key in this range.
get_random_in_interval/2Gets input similar to what intervals:get_bounds/1 returns and calculates Count number of random keys in this range (duplicates may exist!).
get_random_node_id/0Generates a random node id, i.e.
get_range/2Gets the number of keys in the interval (Begin, End].
get_replica_keys/1Returns the replicas of the given key.
get_size/1Returns the size of the routing table.
get_size_ext/1Returns the size of the external routing table.
get_split_key/3Gets the key that splits the interval (Begin, End] so that the first interval will (roughly) be (Num/Denom) * range(Begin, End).
get_split_keys/3Splits the range between Begin and End into up to Parts equal parts and returning the according split keys.
handle_custom_message/2Chord reacts on 'rt_get_node_response' messages in response to its 'rt_get_node' messages.
handle_custom_message_inactive/2No special handling of messages, i.e.
hash_key/1Hashes the key to the identifier space.
init/0This function is called during the startup of the rt_loop process and is allowed to send trigger messages.
init_stabilize/2Starts the stabilization routine.
n/0Returns the size of the address space.
next_hop/3Returns the next hop to contact for a lookup.
succ/2Return the succ, but get the pid from ERT if possible (to hopefully get a rt_loop pid instead of a dht_node state pid).
to_list/1Converts the (external) representation of the routing table to a list of {Id, Pid} tuples, in the order of the fingers, i.e.
to_pid_list/1Returns the pids of the routing table entries.
unwrap_message/2Unwrap lookup messages.
update/3Updates the routing table due to a changed neighborhood.
wrap_message/5Wrap lookup messages.

Function Details

client_key_to_binary/1

client_key_to_binary(Key :: client_key()) -> binary()

init/0

init() -> ok

This function is called during the startup of the rt_loop process and is allowed to send trigger messages. Noop in chord.

activate/1

activate(Neighbors :: nodelist:neighborhood()) -> rt()

Activate the routing table. This function is called during the activation of the routing table process.

hash_key/1

hash_key(Key :: binary() | client_key()) -> key()

Hashes the key to the identifier space.

get_random_node_id/0

get_random_node_id() -> key()

Generates a random node id, i.e. a random 128-bit number, based on the parameters set in the config file (key_creator and key_creator_bitmask).

init_stabilize/2

init_stabilize(Neighbors :: nodelist:neighborhood(), RT :: rt()) ->
                  rt()

Starts the stabilization routine.

filter_dead_node/3

filter_dead_node(RT :: rt(),
                 DeadPid :: comm:mypid(),
                 Reason :: fd:reason()) ->
                    rt()

Removes dead nodes from the routing table.

to_pid_list/1

to_pid_list(RT :: rt()) -> [comm:mypid()]

Returns the pids of the routing table entries.

get_size/1

get_size(RT :: rt()) -> non_neg_integer()

Returns the size of the routing table.

get_size_ext/1

get_size_ext(RT :: external_rt()) -> non_neg_integer()

Returns the size of the external routing table.

n/0

n() -> 340282366920938463463374607431768211456

Returns the size of the address space.

add_range/2

add_range(Key :: key(), Range :: non_neg_integer()) -> key()

Adds the given range, i.e. Range/n() parts of the key space, to the given key.

get_range/2

get_range(Begin :: key(),
          End :: key() | 340282366920938463463374607431768211456) ->
             number()

Gets the number of keys in the interval (Begin, End]. In the special case of Begin==End, the whole key range as specified by n/0 is returned.

get_split_key/3

get_split_key(Begin :: key(),
              End :: key()
                   | 340282366920938463463374607431768211456,
              SplitFraction ::
                  {Num :: number(), Denom :: pos_integer()}) ->
                 key() | 340282366920938463463374607431768211456

Gets the key that splits the interval (Begin, End] so that the first interval will (roughly) be (Num/Denom) * range(Begin, End). In the special case of Begin==End, the whole key range is split. Beware: (Num/Denom) must be in [0, 1]; the final key will be rounded down and may thus be Begin.

get_split_keys/3

get_split_keys(Begin :: key(),
               End :: key()
                    | 340282366920938463463374607431768211456,
               Parts :: pos_integer()) ->
                  [key()]

Splits the range between Begin and End into up to Parts equal parts and returning the according split keys.

get_random_in_interval/1

get_random_in_interval(I :: intervals:simple_interval2()) -> key()

Gets input similar to what intervals:get_bounds/1 returns and calculates a random key in this range. Fails with an exception if there is no key.

get_random_in_interval/2

get_random_in_interval(X1 :: intervals:simple_interval2(),
                       Count :: pos_integer()) ->
                          [key(), ...]

Gets input similar to what intervals:get_bounds/1 returns and calculates Count number of random keys in this range (duplicates may exist!). Fails with an exception if there is no key.

get_replica_keys/1

get_replica_keys(Key :: key()) -> [key()]

Returns the replicas of the given key.

get_key_segment/1

get_key_segment(Key :: key()) -> pos_integer()

dump/1

dump(RT :: rt()) ->
        KeyValueList :: [{Index :: string(), Node :: string()}]

Dumps the RT state for output in the web interface.

update/3

update(OldRT :: rt(),
       OldNeighbors :: nodelist:neighborhood(),
       NewNeighbors :: nodelist:neighborhood()) ->
          {ok | trigger_rebuild, rt()}

Updates the routing table due to a changed neighborhood.

check_config/0

check_config() -> boolean()

Checks whether config parameters of the rt_chord process exist and are valid.

handle_custom_message_inactive/2

handle_custom_message_inactive(Msg :: custom_message(),
                               MsgQueue :: msg_queue:msg_queue()) ->
                                  msg_queue:msg_queue()

No special handling of messages, i.e. all messages are queued.

handle_custom_message/2

handle_custom_message(Message :: custom_message(),
                      State :: rt_loop:state_active()) ->
                         rt_loop:state_active() | unknown_event

Chord reacts on 'rt_get_node_response' messages in response to its 'rt_get_node' messages.

check/5

check(OldRT :: rt(),
      NewRT :: rt(),
      OldERT :: external_rt(),
      Neighbors :: nodelist:neighborhood(),
      ReportToFD :: boolean()) ->
         NewERT :: external_rt()

Notifies the dht_node and failure detector if the routing table changed. Provided for convenience (see check/5).

check/6

check(OldRT :: rt(),
      NewRT :: rt(),
      OldERT :: external_rt(),
      OldNeighbors :: nodelist:neighborhood(),
      NewNeighbors :: nodelist:neighborhood(),
      ReportToFD :: boolean()) ->
         NewERT :: external_rt()

Notifies the dht_node if the (external) routing table changed. Also updates the failure detector if ReportToFD is set. Note: the external routing table also changes if the neighborhood changes.

empty_ext/1

empty_ext(Neighbors :: nodelist:neighborhood()) -> external_rt()

next_hop/3

next_hop(Neighbors :: nodelist:neighborhood(),
         RT :: external_rt(),
         Id :: key()) ->
            succ | comm:mypid()

Returns the next hop to contact for a lookup. Note, that this code will be called from the dht_node process and it will thus have an external_rt!

succ/2

succ(ERT :: external_rt(), Neighbors :: nodelist:neighborhood()) ->
        comm:mypid()

Return the succ, but get the pid from ERT if possible (to hopefully get a rt_loop pid instead of a dht_node state pid)

export_rt_to_dht_node/2

export_rt_to_dht_node(RT :: rt(),
                      Neighbors :: nodelist:neighborhood()) ->
                         external_rt()

to_list/1

to_list(State :: dht_node_state:state()) ->
           [{key(), comm:mypid()}]

Converts the (external) representation of the routing table to a list of {Id, Pid} tuples, in the order of the fingers, i.e. first=succ, second=shortest finger, third=next longer finger,...

wrap_message/5

wrap_message(Key :: key(),
             Msg :: comm:message(),
             MyERT :: external_rt(),
             Neighbors :: nodelist:neighborhood(),
             Hops :: non_neg_integer()) ->
                comm:message()

Wrap lookup messages. This is a noop in Chord.

unwrap_message/2

unwrap_message(Msg :: comm:message(),
               State :: dht_node_state:state()) ->
                  comm:message()

Unwrap lookup messages. This is a noop in Chord.


Generated by EDoc, Feb 29 2016, 16:12:20.