[lsd0004] branch master updated: add text wrt storage API

[gnunet]

This is an automated email from the git hooks/post-receive script.

martin-schanzenbach pushed a commit to branch master
in repository lsd0004.

The following commit(s) were added to refs/heads/master by this push:
     new 479f8e8  add text wrt storage API
479f8e8 is described below

commit 479f8e89792716c4fb6fe382be281fa2fe860963
Author: Martin Schanzenbach <schanzen@gnunet.org>
AuthorDate: Tue Feb 22 20:39:35 2022 +0100

    add text wrt storage API
---
 draft-schanzen-r5n.xml | 106 +++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 85 insertions(+), 21 deletions(-)

diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
index 45039ef..16fa7a1 100644
--- a/draft-schanzen-r5n.xml
+++ b/draft-schanzen-r5n.xml
@@ -1359,6 +1359,66 @@ Connectivity | |Underlay|  |Underlay|
     </section>
     <section anchor="blockstorage" numbered="true" toc="default">
       <name>Storage</name>
+      <t>
+        An implementation MUST provide a local persistence mechanism for
+        blocks.
+        The local storage MUST provide the following API:
+      </t>
+      <dl>
+        <dt>Store(Key, Block)</dt>
+        <dd>
+          Stores a block under the specified key.
+        </dd>
+        <dt>Lookup(Key) -&gt; List of Blocks</dt>
+        <dd>
+          Retrieves the blocks stored under the specified key.
+        </dd>
+        <dt>LookupApproximate(Key) -&gt; List of Blocks</dt>
+        <dd>
+          Retrieves the blocks stored under the specified key and
+          any blocks under keys close to the specified key.
+        </dd>
+      </dl>
+      <t>
+        Over time a peer may accumulate a significant number of blocks
+        which are stored locally in the persistence layer.
+        Due to the expected high number of blocks, the method to
+        retrieve blocks close to the specified lookup key in the
+        <tt>LookupApproximate</tt> API must be implemented with care
+        with respect to efficiency.
+      </t>
+      <t>
+        It is <bcp14>RECOMMENDED</bcp14> to limit the number of results
+        from the <tt>LookupApproximate</tt> procedure to a result size
+        which is manageable by the local system.
+      </t>
+      <t>
+        In order to efficiently find a suitable result set, the implementation
+        SHOULD follow the following procedure:
+      </t>
+      <ol>
+        <li>
+          Sort all blocks by the block key in ascending (decending) order.
+          The block keys are interpreted as integer.
+        </li>
+        <li>
+          Alternatingly select a block with a key larger and smaller from
+          the sortings.
+          The resulting set is sorted by XOR distance.
+          The selection process continues until the upper bound for the
+          result set is reached and both sortings do not yield any closer
+          blocks.
+        </li>
+      </ol>
+      <t>
+        An implementation MAY decide to use a custom algorithm in order to
+        find the closest blocks in the local storage.
+        But, especially for more primitive approaches, such as only
+        comparing XOR distances for all blocks in the storage, the
+        procedure may become ineffective for large storages.
+      </t>
+      <!-- FIXME the result set is then filtered again by the block
+      plugin. But we should discuss this elsewhere -->
       <section>
         <name>Block Processing</name>
         <t>
@@ -1587,29 +1647,33 @@ gnunet+tcp://12.3.4.5/ \
           </figure>
         </section>
       </section>
-      <section>
-        <name>Storage API</name>
-        <!--
-          FIXME TODO
-          We need exact store, lookup and APPROXIMATE
-          - Approximate: look for X blocks with key > lookupKey and key > 
lookupKey
-          each and then order by XOR distance. Return X results.
-          - AFTER that we filter through block plugin (may discard bc of 
xquery)
-          - Implementation should decide if further results required based on
-          resources / storage size.
-        -->
-      </section>
       <section>
         <name>Caching Strategy</name>
-        <!--
-          FIXME TODO
-          What should an implementation consider when managing the
-          cached blocks?
-          - Number of served requests for the block (MAY, can be expensive)
-          - Proximity my peer ID (MAY)
-          - Configurable quotas / local storage size (SHOULD)
-          - Block expiration (this is what we do atm) (MUST)
-        -->
+        <t>
+          An implementation <bcp14>MUST</bcp14> implement an eviction strategy
+          for blocks stored in the block storage layer.
+        </t>
+        <t>
+          In order to ensure the freshness of blocks, an implementation
+          <bcp14>MUST</bcp14> evict expired blocks in favor of
+          new blocks.
+        </t>
+        <t>
+          An implementation <bcp14>MAY</bcp14> preserve blocks which are often
+          requested.
+          This approach can be expensive as it requires the implementation
+          to keep track of how often a block is requested.
+        </t>
+        <t>
+          An implementation <bcp14>MAY</bcp14> preserve blocks which are close
+          to the local peer ID.
+        </t>
+        <t>
+          An implementation <bcp14>MAY</bcp14> provide configurable storage
+          quotas and
+          adapt its eviction strategy based on the current storage size
+          or other constrained resources.
+        </t>
       </section>
     </section>
     <section anchor="security" numbered="true" toc="default">

-- 
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.