scheme-gnunet/doc/distributed-hash-table.tm

<TeXmacs|2.1>

<project|scheme-gnunet.tm>

<style|tmmanual>

<\body>
  GNUnet has a service that maintains a <em|distributed hash
  table><index|distributed hash table><index|DHT><index|R5N>, mapping keys to
  values. The module <scm|(gnu gnunet dht client)><index|(gnu gnunet dht
  client)> can be used to interact with the service. The connection can be
  made with the procedure <scm|connect>. It returns a <em|DHT server
  object><index|DHT server object><subindex|server object|DHT>.

  <\explain>
    <scm|(connect <var|config> <var|#:connected> <var|#:disconnected>
    <var|#:spawn>)><subindex|connect|DHT>
  <|explain>
    Connect to the DHT service, using the configuration <var|config>. The
    connection is made asynchronuously; the optional thunk <var|connected> is
    called when the connection has been made. The connection can break; the
    optional thunk <var|disconnected> is called when it does. If the
    connection breaks, the client code automatically tries to reconnect, so
    <var|connected> can be called after <var|disconnected>.
  </explain>

  <\explain>
    <scm|(disconnect! <var|server>)><subindex|disconnect!|DHT>
  <|explain>
    Asynchronuously disconnect from the DHT service and stop reconnecting,
    even if not connected. This is an idempotent operation.
  </explain>

  Some time after the returned server object becomes unreachable, it will
  automatically be disconnected. Active lingering operations and reachable
  operations keeps the server object reachable. <todo|test this!>

  <section|Data in the DHT>

  To insert data into the DHT, the DHT service needs various information \U
  the key and the value, but also some other information. Likewise, when the
  DHT service has found the datum, this information is available as well. A
  datum in the DHT is represented as a <em|datum object><index|datum object>.
  The object holding the information required for inserting something in the
  DHT is called an <em|insertion object><index|insertion object>. Likewise,
  the information of searching for something in the DHT is in a <em|query
  object><index|query object>. The result of a query is a <em|search result
  object><index|search result object>.

  These objects only hold information; creating them does not have any side
  effects.

  <\explain>
    <scm|(make-datum <var|type> <var|key> <var|value>
    <var|#:expiration>)><index|make-datum>
  <|explain>
    Make a datum object of block type <var|type> (or its corresponding
    numeric value), with key <var|key> (a readable <scm|/hashcode:512>
    bytevector slice), value <var|value> (a readable bytevector slice) and
    expiring at <var|expiration> (<todo|type, epoch>). The keyword argument
    <var|expiration> is optional, see <reference|???>.

    The numeric value of the block type can be retrieved with the accessor
    <scm|datum-type>. The accessors <scm|datum-key><index|datum-key>,
    <scm|datum-value><index|datum-value> and
    <scm|datum-expiration><index|datum-expiration> return the key, value and
    expiration time respectively. It can be tested if an object is a datum
    object with the predicate <scm|datum?><index|datum?>.

    The length of <var|value> may be at most
    <scm|%max-datum-value-length><index|%max-datum-value-length>. If this
    bound is exceeded, an appropriate <scm|&overly-large-datum><index|&overly-large-datum>
    and <scm|&who> condition is raised.
  </explain>

  <\explain>
    <scm|(datum-\<gtr\>insertion <var|datum>
    #:desired-replication-level)><index|datum-\<gtr\>insertion>
  <|explain>
    Make an insertion object for inserting the datum <var|datum>, desiring a
    replication level <var|desired-replication-level> (see
    <reference|replication levels???>)<todo|various options>.

    The datum and desired replication level can be recovered with the
    accessors <scm|insertion-\<gtr\>datum><index|insertion-\<gtr\>datum> and
    <var|insertion-desired-replication-level><index|insertion-desired-replication-level>.
    It can be tested if an object is an insertion object with the predicate
    <scm|insertion?><index|insertion?>.
  </explain>

  <\explain>
    <scm|(make-query <var|type> <var|key>
    #:desired-replication-level)><index|make-query>
  <|explain>
    Make a query object for searching for a value of block type <var|type>
    (or its corresponding numeric value), with key <var|key> (a readable
    <scm|/hashcode:512> bytevector slice), at desired replication level
    <scm|desired-replication-level> (see <reference|replication levels???>).
    <todo|various options, xquery>

    The numeric value of the block type, the key and the desired replication
    level can be recovered with the accessors
    <scm|query-type><index|query-type>, <scm|query-key><index|query-key> and
    <scm|query-desired-replication-level><index|query-desired-replication-level>.
    It can be tested if an object is a query object with the predicate
    <scm|query?><index|query?>.
  </explain>

  <\explain>
    <scm|(datum-\<gtr\>search-result <var|datum> #:get-path
    #:put-path)><index|datum-\<gtr\>search-result>
  <|explain>
    Make a search result object for the datum <var|datum>. The datum can be
    recovered with the accessor <scm|search-result-\<gtr\>datum><index|search-result-\<gtr\>datum>.
    It can be tested if an object is a search result with the predicate
    <scm|search-result?><index|search-result?>. The optional arguments
    <var|get-path> and <var|put-path>, when not false, are bytevector slices
    consisting of a list of <scm|/dht:path-element><index|/dht:path-element><index|path
    element>.

    The <var|get-path><index|get path> , if any, is the path from the storage
    location to the current peer. Conversely, the <var|put-path><index|put
    path>, if any, is a path from the peer that inserted the datum into the
    DHT to the storage location. The <var|get-path> and <var|put-path> can be
    accessed with <scm|search-result-get-path><index|search-result-get-path>
    and <scm|search-result-put-path><index|search-result-put-path>
    respectively.

    When the datum, get path and put path together are too large, a
    <scm|&overly-large-paths><index|&overly-large-paths> condition is raised.
    When the bytevector slice length of <var|get-path> or <var|put-path> is
    not a multiple of the size of a path element, then a
    <scm|&malformed-path><index|&malformed-path> condition is raised.
  </explain>

  <section|Accessing data in the DHT>

  To insert a datum into the DHT, the procedure <scm|put!> is used. To find
  data matching a query, the procedure <scm|start-get!> is
  used.<index|searching the DHT><index|inserting data into the DHT>

  <\explain>
    <scm|(start-get! <var|server> <var|query> <var|found>
    <var|#:linger?>=#false)><index|start-get!>
  <|explain>
    Search for data matching <var|query> in the DHT. When a datum is found,
    call the unary procedure <var|found> on the search result. It is possible
    to find multiple data matching a query. In that case, <var|found> is
    called multiple times. Searching happens asynchronuously; to stop the
    search, a fresh <em|search object><index|search object> for controlling
    the search is returned.

    The procedure <var|found> is run from the context of <var|server>. As
    such, if <var|found> blocks, then all operations on <var|server> might
    block. As such, it is recommended for <var|found> to do as little as
    possible by itself and instead delegate any work to a separate fiber.

    To avoid expensive copies, the implementation can choose to reuse
    internal buffers for the slices passed to <var|found>, which could be
    overwritten after the call to <var|found>. As such, it might be necessary
    to make a copy of the search result, using <scm|copy-search-result>.

    When the boolean <var|linger?> is false (this is the default), the search
    is automatically cancelled when the search object becomes unreachable
    according to the GC.

    <\warning>
      Guile currently (3.0.8) uses a conservative GC, so it cannot always
      detect unreachability when it should.
    </warning>
  </explain>

  <\explain>
    <scm|(stop-get! <var|search>)><index|stop-get!>
  </explain|Cancel the get operation described by the search object
  <var|search>. This is an asynchronuous operation; it does not have an
  immediate effect. This is an idempotent operation: cancelling a search does
  not have any additional effect.>

  <\explain>
    <scm|(put! <var|server> <var|insertion> <var|#:confirmed>)><index|put!>
  <|explain>
    Perform the insertion <var|insertion>. When the datum has been inserted,
    the optional thunk <var|confirmed> is called. A <em|put object> is
    returned which can be used to cancel the insertion.

    <todo|TODO: actually call <var|confirmed>>
  </explain>

  <\explain>
    <scm|(copy-query <var|old>)><index|copy-query>

    <scm|(copy-datum <var|old>)><index|copy-datum>

    <scm|(copy-insertion <var|old>)><index|copy-insertion>

    <scm|(copy-search-result <var|old>)><index|copy-search-result>
  <|explain>
    Make a copy of the object <var|old> (a query, datum, insertion or search
    result object, depending on the procedure), such that modifications to
    the slices in <var|old> do not impact the new object.
  </explain>

  <todo|cancellation>

  <section|Constructing and analysing network messages>

  The DHT client and service communicate by sending <em|messages>. Usually,
  only the implementation of the client and service need to construct and
  analyse these messages, but nothing prevents other uses of the procedures
  in <scm|(gnu gnunet dht network)><index|(gnu gnunet dht network)>, e.g. for
  learning, in a tool like Wireshark or for tests.

  The <em|analysis> procedures<index|analysis procedures> assume that the
  message is well-formed and avoid constructing new bytevector slices by
  taking subslices. The <em|construction> procedures<index|construction
  procedures> create fresh well-formed read-write bytevector slices.

  <\warning>
    Possibly the type of <var|options> will change and possibly the options
    will be moved into the query object and insertion object.
  </warning>

  <\explain>
    <scm|(construct-client-get <var|query> <var|unique-id> #:optional
    (<var|options> 0))><index|construct-client-get>
  <|explain>
    Create a new <scm|/:msg:dht:client:get><index|/:msg:dht:client:get>
    message for the query object <var|query>, with <var|unique-id> as
    \<#2018\>unique id\<#2019\> and <var|options> as options.
  </explain>

  <\explain>
    <scm|(construct-client-get-stop <var|key>
    <var|unique-id>)><index|construct-client-get-stop>
  </explain|Create a new <scm|/:msg:dht:client:get:stop> message for
  cancelling a get request.>

  <\explain>
    <scm|(construct-client-put <var|insertion> #:optional (options
    0))><index|construct-client-put>
  <|explain>
    Create a new <scm|/:msg:dht:client:put><index|/:msg:dht:client:put>
    message for the insertion object <var|insertion> with <var|options> as
    options.
  </explain>

  <\explain>
    <scm|(construct-client-result <var|search-result>
    <var|unique-id>)><index|construct-client-result>
  <|explain>
    Create a new <scm|/:msg:dht:client:result><index|/:msg:dht:client:result>
    message for the search result object <var|search-result>, with
    <var|unique-id> as \<#2018\>unique id\<#2019\> .
  </explain>

  <\explain>
    <scm|(analyse-client-get <var|message>)><index|analyse-client-get>
  <|explain>
    Return the query object, the unique id and the options corresponding to
    the <scm|/:msg:dht:client:result><index|/:msg:dht:client:result> message
    <var|message>. Xqueries are currently unsupported.
  </explain>

  <\explain>
    <scm|(analyse-client-get-stop <var|message>)><index|analyse-client-get-stop>
  </explain|Return the unique id and the key corresponding to the
  <scm|/:msg:dht:client:stop> message <var|message>.>

  <\explain>
    <scm|(analyse-client-put <var|message>)><index|analyse-client-put>
  <|explain>
    Return the insertion object and options corresponding to the
    <scm|/:msg:dht:client:put><index|/:msg:dht:client:put> message
    <var|message>.
  </explain>

  <\explain>
    <scm|(analyse-client-result <var|message>)><index|analyse-client-result>
  <|explain>
    Return search result object and unique id for the
    <scm|/:msg:dht:client:result><index|/:msg:dht:client:result> message
    <var|message>.
  </explain>

  <todo|monitoring messages>

  <section|How to handle invalid data>

  <todo|todo!>

  <section|Monitoring: spying on what other applications and peers are doing>

  <todo|todo!>
</body>

<\initial>
  <\collection>
    <associate|page-medium|paper>
    <associate|save-aux|false>
  </collection>
</initial>