commit e676368dafd3a2091c5c9e689da444546a18c713
parent 1d9a242abd1b70ac49d88baf529cb141f02ab484
Author: Martin Schanzenbach <schanzen@gnunet.org>
Date: Tue, 22 Feb 2022 21:10:44 +0100
some reorg. still rough
Diffstat:
1 file changed, 174 insertions(+), 171 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -331,7 +331,7 @@ Connectivity | |Underlay| |Underlay|
required depending on the respective <tt>Block-Type</tt>.
A <tt>Block-Type</tt> must define if the <tt>XQuery</tt> can or must
be used and what the specific format of its contents should be.
- See also <xref target="block_types"/>.
+ See also <xref target="blockstorage"/>.
</dd>
<dt>Result-Filter:</dt>
<dd>
@@ -1359,168 +1359,108 @@ Connectivity | |Underlay| |Underlay|
</section>
<section anchor="blockstorage" numbered="true" toc="default">
<name>Block 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>
- Block validation may be necessary for both request as well as
- reply messages.
- When evaluating request messages and their metadata, the possible
- evaluation results are:
- </t>
- <!--<t>RequestEvaluationResult</t>-->
- <dl>
- <dt>REQUEST_VALID</dt>
- <dd>Query is valid, no reply given.</dd>
- <dt>REQUEST_INVALID</dt>
- <dd>
- Query format does not match block type. For example, XQuery not
- given or of size of XQuery is not appropriate for type.
- </dd>
- </dl>
- <t>
- When evaluating result messages, the possible evaluation results
- are:
- </t>
- <!-->t>ReplyEvaluationResult</t>-->
- <!-- FIXME this is not integrated into the message processing
- or block processing. We need to specifiy where this is used.
- My guess is that we should handle result types in the message
- processing descriptions -->
- <dl>
- <dt>OK_MORE</dt>
- <dd>Valid result, and there may be more.</dd>
- <dt>OK_LAST</dt>
- <dd>Last possible valid result.</dd>
- <dt>OK_DUPLICATE</dt>
- <dd>Valid result, but duplicate.</dd>
- <dt>RESULT_INVALID</dt>
- <dd>Invalid result. Block does not match query. Value = 4.</dd>
- <dt>RESULT_IRRELEVANT</dt>
- <dd>Block does not match xquery. Valid result, but not relevant for the request.</dd>
- </dl>
- </section>
- <section anchor="block_functions">
- <name>Block Functions</name>
- <t>
- Any block type implementation <bcp14>MUST</bcp14> implement the following functions.
- </t>
- <dl>
- <dt>ValidateBlockQuery(Key, XQuery) -> RequestEvaluationResult</dt>
- <dd>
- is used to evaluate the request for a block. It is used as part of
- <tt>GetMessage</tt> processing, where the block payload is still unkown,
- but the block <tt>XQuery</tt> <!--(FIXME: Undefined here)-->
- and <tt>Key</tt> can and
- <bcp14>MUST</bcp14> be verified, if possible.
- </dd>
- <dt>ValidateBlockStoreRequest(Block, Key) -> RequestEvaluationResult</dt>
- <dd>
- is used to evaluate a block including its key and payload.
- It is used as part of <tt>PutMessage</tt> processing.
- The validation <bcp14>MUST</bcp14> include a check of the block payload against the
- <tt>Key</tt> under which it is requested to be stored.
- </dd>
- <dt>ValidateBlockReply(Block, XQuery, Key) -> ReplyEvaluationResult</dt>
- <dd>
- is used to evaluate a block including its <tt>Key</tt> and payload.
- It is used as part <tt>ResultMessage</tt> processing.
- The validation of the respective <tt>Block</tt> requires a pending local query
- or a previously routed request of another peer and its associated
- XQuery data and Key.
- The validation <bcp14>MUST</bcp14> include a check of the block payload against the
- key under which it is requested to be stored.
- </dd>
- <dt>DeriveBlockKey(Block) -> Key</dt>
- <dd>
- is used to synthesize the block key from the block payload
- and metadata. It is used as part of FIND-peer message processing.
- </dd>
- <dt>FilterResult(Block, XQuery, Key) -> ReplyEvaluationResult</dt>
- <dd>
- is used to filter results stored in the local block storage for local
- queries. Locally stored blocks from previously observed
- <tt>ResultMessages</tt> and <tt>PutMessages</tt> <bcp14>MAY</bcp14> use this
- function instead of <tt>ValidateBlockReply</tt> in order to
- avoid revalidation of the block and only perform filtering based on
- request parameters.
- </dd>
- </dl>
- </section>
- <section anchor="block_types">
- <name>Block Types</name>
+ <name>Blocks</name>
<t>
Applications can and should define their own block types.
The block type determines the format and handling of the block
payload by peers in PUT and RESULT messages.
Block types <bcp14>MUST</bcp14> be registered with GANA <xref target="gana"/>.
</t>
- <t>
- For bootstrapping and peer discovery, the DHT implementation uses
- its own block type called "HELLO". A block with this block type
- contains the peerID of the peer initiating the GET request.
- </t>
+ <section>
+ <name>Block Processing</name>
+ <t>
+ Block validation may be necessary for both request as well as
+ reply messages.
+ When evaluating request messages and their metadata, the possible
+ evaluation results are:
+ </t>
+ <!--<t>RequestEvaluationResult</t>-->
+ <dl>
+ <dt>REQUEST_VALID</dt>
+ <dd>Query is valid, no reply given.</dd>
+ <dt>REQUEST_INVALID</dt>
+ <dd>
+ Query format does not match block type. For example, XQuery not
+ given or of size of XQuery is not appropriate for type.
+ </dd>
+ </dl>
+ <t>
+ When evaluating result messages, the possible evaluation results
+ are:
+ </t>
+ <!-->t>ReplyEvaluationResult</t>-->
+ <!-- FIXME this is not integrated into the message processing
+ or block processing. We need to specifiy where this is used.
+ My guess is that we should handle result types in the message
+ processing descriptions -->
+ <dl>
+ <dt>OK_MORE</dt>
+ <dd>Valid result, and there may be more.</dd>
+ <dt>OK_LAST</dt>
+ <dd>Last possible valid result.</dd>
+ <dt>OK_DUPLICATE</dt>
+ <dd>Valid result, but duplicate.</dd>
+ <dt>RESULT_INVALID</dt>
+ <dd>Invalid result. Block does not match query. Value = 4.</dd>
+ <dt>RESULT_IRRELEVANT</dt>
+ <dd>Block does not match xquery. Valid result, but not relevant for the request.</dd>
+ </dl>
+ </section>
+ <section anchor="block_functions">
+ <name>Block Functions</name>
+ <t>
+ Any block type implementation <bcp14>MUST</bcp14> implement the following functions.
+ </t>
+ <dl>
+ <dt>ValidateBlockQuery(Key, XQuery) -> RequestEvaluationResult</dt>
+ <dd>
+ is used to evaluate the request for a block. It is used as part of
+ <tt>GetMessage</tt> processing, where the block payload is still unkown,
+ but the block <tt>XQuery</tt> <!--(FIXME: Undefined here)-->
+ and <tt>Key</tt> can and
+ <bcp14>MUST</bcp14> be verified, if possible.
+ </dd>
+ <dt>ValidateBlockStoreRequest(Block, Key) -> RequestEvaluationResult</dt>
+ <dd>
+ is used to evaluate a block including its key and payload.
+ It is used as part of <tt>PutMessage</tt> processing.
+ The validation <bcp14>MUST</bcp14> include a check of the block payload against the
+ <tt>Key</tt> under which it is requested to be stored.
+ </dd>
+ <dt>ValidateBlockReply(Block, XQuery, Key) -> ReplyEvaluationResult</dt>
+ <dd>
+ is used to evaluate a block including its <tt>Key</tt> and payload.
+ It is used as part <tt>ResultMessage</tt> processing.
+ The validation of the respective <tt>Block</tt> requires a pending local query
+ or a previously routed request of another peer and its associated
+ XQuery data and Key.
+ The validation <bcp14>MUST</bcp14> include a check of the block payload against the
+ key under which it is requested to be stored.
+ </dd>
+ <dt>DeriveBlockKey(Block) -> Key</dt>
+ <dd>
+ is used to synthesize the block key from the block payload
+ and metadata. It is used as part of FIND-peer message processing.
+ </dd>
+ <dt>FilterResult(Block, XQuery, Key) -> ReplyEvaluationResult</dt>
+ <dd>
+ is used to filter results stored in the local block storage for local
+ queries. Locally stored blocks from previously observed
+ <tt>ResultMessages</tt> and <tt>PutMessages</tt> <bcp14>MAY</bcp14> use this
+ function instead of <tt>ValidateBlockReply</tt> in order to
+ avoid revalidation of the block and only perform filtering based on
+ request parameters.
+ </dd>
+ </dl>
+ </section>
<section anchor="hello_block">
- <name>HELLO</name>
+ <name>Hello Block</name>
+ <t>
+ For bootstrapping and peer discovery, the DHT implementation uses
+ its own block type called "HELLO". A block with this block type
+ contains the peerID of the peer initiating the GET request.
+ </t>
<t>
The HELLO block type wire format is illustrated in
<xref target="figure_hello"/>. A query for block of type HELLO <bcp14>MUST NOT</bcp14>
@@ -1652,32 +1592,95 @@ gnunet+tcp://12.3.4.5/ \
</section>
</section>
<section>
- <name>Caching Strategy</name>
+ <name>Persistence</name>
<t>
- An implementation <bcp14>MUST</bcp14> implement an eviction strategy
- for blocks stored in the block storage layer.
+ 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>
- In order to ensure the freshness of blocks, an implementation
- <bcp14>MUST</bcp14> evict expired blocks in favor of
- new blocks.
+ 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>
- 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.
+ 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>
- An implementation <bcp14>MAY</bcp14> preserve blocks which are close
- to the local peer ID.
+ 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 <bcp14>MAY</bcp14> provide configurable storage
- quotas and
- adapt its eviction strategy based on the current storage size
- or other constrained resources.
+ 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>Caching Strategy</name>
+ <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>
<section anchor="security" numbered="true" toc="default">
