commit ef0e5f9cc2813d137bb304b51141c183fcc46ab6
parent 82163ff25bfb6da30609991c4066dd969a49a202
Author: Christian Grothoff <christian@grothoff.org>
Date: Sat, 13 Jul 2024 23:11:42 +0200
finish review of section 8. DONE.
Diffstat:
1 file changed, 43 insertions(+), 31 deletions(-)
diff --git a/draft-schanzen-r5n.xml b/draft-schanzen-r5n.xml
@@ -2909,7 +2909,7 @@ BEGIN
corresponding <tt>PUTPATH</tt> (and if applicable
<tt>TRUNCATED ORIGIN</tt>) of that version of the block.
</dd>
- <dt>Lookup(Key) -> List of Blocks</dt>
+ <dt>Lookup(Key) -> Set of Blocks</dt>
<dd>
Retrieves blocks stored under the specified key.
</dd>
@@ -2917,7 +2917,7 @@ BEGIN
<dd>
Retrieves the blocks stored under the specified key and
any blocks under keys close to the specified key, in order
- of decreasing proximity.
+ of decreasing proximity.
</dd>
</dl>
<section anchor="approx_search">
@@ -2931,41 +2931,54 @@ BEGIN
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 easily manageable by the local system.
+ It is <bcp14>RECOMMENDED</bcp14> to limit the number of
+ results from the <tt>LookupApproximate</tt> procedure to a
+ result size which is easily manageable by the local system.
+ The <bcp14>RECOMMENDED</bcp14> default is to return blocks
+ with the four closest keys. Note that filtering by the
+ <tt>RF</tt> will be done by the DHT afterwards and it is
+ <bcp14>NOT RECOMMENDED</bcp14> to fetch additional records
+ even if all four closest keys are filtered by the
+ <tt>RF</tt>. The main reason for this is to ensure peers do
+ not spend extensive resources to process approximate
+ lookups. In particular, implementations <bcp14>MUST</bcp14>
+ limit the worst-case effort they spent on approximate
+ lookups.
</t>
<t>
- In order to efficiently find a suitable result set, the implementation
- <bcp14>SHOULD</bcp14> follow the following procedure:
+ In order to efficiently find a suitable result set, the
+ implementation <bcp14>SHOULD</bcp14> 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.
+ The block keys are interpreted as integers.
</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.
+ Alternatingly select a block with a key larger and smaller
+ from the sortings. The resulting set is then sorted by
+ the XOR distance to the query. 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> 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.
+ An implementation <bcp14>MAY</bcp14> 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), more simplistic procedures may become ineffective
+ for large data sets and care <bcp14>MUST</bcp14> be taken
+ to strictly bound the maximum effort expended per query.
</t>
</section>
<section>
<name>Caching Strategy Considerations</name>
<t>
- An implementation <bcp14>MUST</bcp14> implement an eviction strategy
- for blocks stored in the block storage layer.
+ 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
@@ -2973,20 +2986,19 @@ BEGIN
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.
+ 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 public key.
+ An implementation <bcp14>MAY</bcp14> preserve blocks which
+ are close to the local peer public key.
</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.
+ 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>
