commit 479f8e89792716c4fb6fe382be281fa2fe860963
parent c403cce27d359266f8f3d8570512d115a217265e
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Tue, 22 Feb 2022 20:39:35 +0100
add text wrt storage API
Diffstat:
1 file changed, 85 insertions(+), 21 deletions(-)
diff --git 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) -> List of Blocks</dt>
+ <dd>
+ Retrieves the blocks stored under the specified key.
+ </dd>
+ <dt>LookupApproximate(Key) -> 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>
@@ -1588,28 +1648,32 @@ gnunet+tcp://12.3.4.5/ \
</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">
