When the number of active queries exceeds the (internal)
JOBS_MAX_QUERIES limit, which is only supposed to bound
the number of concurrent queries relating to background
jobs, an arithmetic overflow occurs. This is fixed by
using saturating subtraction.
* Configurable multistream-select protocol. Add V1Lazy variant. (#1245)
Make the multistream-select protocol (version) configurable
on transport upgrades as well as for individual substreams.
Add a "lazy" variant of multistream-select 1.0 that delays
sending of negotiation protocol frames as much as possible
but is only safe to use under additional assumptions that
go beyond what is required by the multistream-select v1
specification.
* Improve the code readability of the chat example (#1253)
* Add bridged chats (#1252)
* Try fix CI (#1261)
* Print Rust version on CI
* Don't print where not appropriate
* Change caching strategy
* Remove win32 build
* Remove win32 from list
* Update libsecp256k1 dep to 0.3.0 (#1258)
* Update libsecp256k1 dep to 0.3.0
* Sign now cannot fail
* Upgrade url and percent-encoding deps to 2.1.0 (#1267)
* Upgrade percent-encoding dep to 2.1.0
* Upgrade url dep to 2.1.0
* Revert CIPHERS set to null (#1273)
* Update dependency versions (#1265)
* Update versions of many dependencies
* Bump version of rand
* Updates for changed APIs in rand, ring, and webpki
* Replace references to `snow::Session`
`Session` no longer exists in `snow` but the replacement is two structs `HandshakeState` and `TransportState`
Something will have to be done to harmonize `NoiseOutput.session`
* Add precise type for UnparsedPublicKey
* Update data structures/functions to match new snow's API
* Delete diff.diff
Remove accidentally committed diff file
* Remove commented lines in identity/rsa.rs
* Bump libsecp256k1 to 0.3.1
* Implement /plaintext/2.0.0 (#1236)
* WIP
* plaintext/2.0.0
* Refactor protobuf related issues to compatible with the spec
* Rename: new PlainTextConfig -> PlainText2Config
* Keep plaintext/1.0.0 as PlainText1Config
* Config contains pubkey
* Rename: proposition -> exchange
* Add PeerId to Exchange
* Check the validity of the remote's `Exchange`
* Tweak
* Delete unused import
* Add debug log
* Delete unused field: public_key_encoded
* Delete unused field: local
* Delete unused field: exchange_bytes
* The inner instance should not be public
* identity::Publickey::Rsa is not available on wasm
* Delete PeerId from Config as it should be generated from the pubkey
* Catch up for #1240
* Tweak
* Update protocols/plaintext/src/error.rs
Co-Authored-By: Pierre Krieger <pierre.krieger1708@gmail.com>
* Update protocols/plaintext/src/handshake.rs
Co-Authored-By: Pierre Krieger <pierre.krieger1708@gmail.com>
* Update protocols/plaintext/src/error.rs
Co-Authored-By: Pierre Krieger <pierre.krieger1708@gmail.com>
* Update protocols/plaintext/src/error.rs
Co-Authored-By: Roman Borschel <romanb@users.noreply.github.com>
* Update protocols/plaintext/src/error.rs
Co-Authored-By: Roman Borschel <romanb@users.noreply.github.com>
* Rename: pubkey -> local_public_key
* Delete unused error
* Rename: PeerIdValidationFailed -> InvalidPeerId
* Fix: HandShake -> Handshake
* Use bytes insteadof Publickey to avoid code duplication
* Replace with ProtobufError
* Merge HandshakeContext<()> into HandshakeContext<Local>
* Improve the peer ID validation to simplify the handshake
* Propagate Remote to allow extracting the PeerId from the Remote
* Collapse the same kind of errors into the variant
* [noise]: `sodiumoxide 0.2.5` (#1276)
Fixes https://github.com/RustSec/advisory-db/pull/192
* examples/ipfs-kad.rs: Remove outdated reference to `without_init` (#1280)
* CircleCI Test Fix (#1282)
* Disabling "Docker Layer Caching" because it breaks one of the circleci checks
* Bump to trigger CircleCI build
* unbump
* zeroize: Upgrade to v1.0 (#1284)
v1.0 final release is out. Release notes:
https://github.com/iqlusioninc/crates/pull/279
* *: Consolidate protobuf scripts and update to rust-protobuf 2.8.1 (#1275)
* *: Consolidate protobuf generation scripts
* *: Update to rust-protobuf 2.8.1
* *: Mark protobuf generated modules with '_proto'
* examples: Add distributed key value store (#1281)
* examples: Add distributed key value store
This commit adds a basic distributed key value store supporting GET and
PUT commands using Kademlia and mDNS.
* examples/distributed-key-value-store: Fix typo
* Simple Warning Cleanup (#1278)
* Cleaning up warnings - removing unused `use`
* Cleaning up warnings - unused tuple value
* Cleaning up warnings - removing dead code
* Cleaning up warnings - fixing deprecated name
* Cleaning up warnings - removing dead code
* Revert "Cleaning up warnings - removing dead code"
This reverts commit f18a765e4bf240b0ed9294ec3ae5dab5c186b801.
* Enable the std feature of ring (#1289)
* Cleaning up warnings - removing unused `use`
* Cleaning up warnings - unused tuple value
* Cleaning up warnings - removing dead code
* Cleaning up warnings - fixing deprecated name
* Cleaning up warnings - removing dead code
* Revert "Cleaning up warnings - removing dead code"
This reverts commit f18a765e4bf240b0ed9294ec3ae5dab5c186b801.
* WIP
* plaintext/2.0.0
* Refactor protobuf related issues to compatible with the spec
* Rename: new PlainTextConfig -> PlainText2Config
* Keep plaintext/1.0.0 as PlainText1Config
* Config contains pubkey
* Rename: proposition -> exchange
* Add PeerId to Exchange
* Check the validity of the remote's `Exchange`
* Tweak
* Delete unused import
* Add debug log
* Delete unused field: public_key_encoded
* Delete unused field: local
* Delete unused field: exchange_bytes
* The inner instance should not be public
* identity::Publickey::Rsa is not available on wasm
* Delete PeerId from Config as it should be generated from the pubkey
* Catch up for #1240
* Tweak
* Update protocols/plaintext/src/error.rs
Co-Authored-By: Pierre Krieger <pierre.krieger1708@gmail.com>
* Update protocols/plaintext/src/handshake.rs
Co-Authored-By: Pierre Krieger <pierre.krieger1708@gmail.com>
* Update protocols/plaintext/src/error.rs
Co-Authored-By: Pierre Krieger <pierre.krieger1708@gmail.com>
* Update protocols/plaintext/src/error.rs
Co-Authored-By: Roman Borschel <romanb@users.noreply.github.com>
* Update protocols/plaintext/src/error.rs
Co-Authored-By: Roman Borschel <romanb@users.noreply.github.com>
* Rename: pubkey -> local_public_key
* Delete unused error
* Rename: PeerIdValidationFailed -> InvalidPeerId
* Fix: HandShake -> Handshake
* Use bytes insteadof Publickey to avoid code duplication
* Replace with ProtobufError
* Merge HandshakeContext<()> into HandshakeContext<Local>
* Improve the peer ID validation to simplify the handshake
* Propagate Remote to allow extracting the PeerId from the Remote
* Collapse the same kind of errors into the variant
* Update versions of many dependencies
* Bump version of rand
* Updates for changed APIs in rand, ring, and webpki
* Replace references to `snow::Session`
`Session` no longer exists in `snow` but the replacement is two structs `HandshakeState` and `TransportState`
Something will have to be done to harmonize `NoiseOutput.session`
* Add precise type for UnparsedPublicKey
* Update data structures/functions to match new snow's API
* Delete diff.diff
Remove accidentally committed diff file
* Remove commented lines in identity/rsa.rs
* Bump libsecp256k1 to 0.3.1
* Configurable multistream-select protocol. Add V1Lazy variant. (#1245)
Make the multistream-select protocol (version) configurable
on transport upgrades as well as for individual substreams.
Add a "lazy" variant of multistream-select 1.0 that delays
sending of negotiation protocol frames as much as possible
but is only safe to use under additional assumptions that
go beyond what is required by the multistream-select v1
specification.
* Improve the code readability of the chat example (#1253)
* Add bridged chats (#1252)
* Try fix CI (#1261)
* Print Rust version on CI
* Don't print where not appropriate
* Change caching strategy
* Remove win32 build
* Remove win32 from list
* Update libsecp256k1 dep to 0.3.0 (#1258)
* Update libsecp256k1 dep to 0.3.0
* Sign now cannot fail
* Upgrade url and percent-encoding deps to 2.1.0 (#1267)
* Upgrade percent-encoding dep to 2.1.0
* Upgrade url dep to 2.1.0
* Fix more conflicts
* Revert CIPHERS set to null (#1273)
* protocols/noise: Fix obvious future errors
* protocol/noise: Make Handshake methods independent functions
* protocols/noise: Abstract T and C for handshake
* protocols/noise: Replace FutureResult with Result
* protocols/noise: Introduce recv_identity stub
* protocols/noise: Implement recv_identity stub
* protocols/noise: Change NoiseConfig::Future from Handshake to Result
* protocols/noise: Adjust to new Poll syntax
* protocols/noise: Return early on state creation failure
* protocols/noise: Add bounds Async{Write,Read} to initiator / respoder
* protocols/noise: Add Protocol trait bound for C in rt functions
* protocols/noise: Do io operations on state.io instead of state
* protocols/noise: Have upgrade_xxx return a pinned future
* protocols/noise: Have NoiseOutput::poll_read self be mutable
* protocols/noise: Make recv_identity buffers mutable
* protocols/noise: Fix warnings
* protocols/noise: Replace NoiseOutput io::Read impl with AsyncRead
* protocols/noise: Replace NoiseOutput io::Write impl with AsyncWrite
* protocols/noise: Adjust tests to new futures
* protocols/noise: Don't use {AsyncRead,AsyncWrite,TryStream}*Ext* bound
* protocols/noise: Don't use async_closure feature
* protocols/noise: use futures::ready! macro
* protocols/noise: Make NoiseOutput AsyncRead return unsafe NopInitializer
The previous implementation of AsyncRead for NoiseOutput would operate
on uninitialized buffers, given that it properly returned the number of
bytest that were written to the buffer. With this patch the current
implementation operates on uninitialized buffers as well by returning an
Initializer::nop() in AsyncRead::initializer.
* protocols/noise: Remove resolved TODO questions
* protocols/noise: Remove 'this = self' comment
Given that `let mut this = &mut *self` is not specific to a pinned self,
but follows the dereference coercion [1] happening at compile time when
trying to mutably borrow two distinct struct fields, this patch removes
the code comment.
[1]
```rust
let x = &mut self.deref_mut().x;
let y = &mut self.deref_mut().y; // error
// ---
let mut this = self.deref_mut();
let x = &mut this.x;
let y = &mut this.y; // ok
```
* Remove redundant nested futures.
* protocols/noise/Cargo: Update to futures preview 0.3.0-alpha.18
* protocols/noise: Improve formatting
* protocols/noise: Return pinned future on authenticated noise upgrade
* protocols/noise: Specify Output of Future embedded in Handshake directly
* *: Ensure Noise handshake futures are Send
* Revert "*: Ensure Noise handshake futures are Send"
This reverts commit 555c2df315e44f21ad39d4408445ce2cb84dd1a4.
* protocols/noise: Ensure NoiseConfig Future is Send
* protocols/noise: Use relative import path for {In,Out}boundUpgrade
Make the multistream-select protocol (version) configurable
on transport upgrades as well as for individual substreams.
Add a "lazy" variant of multistream-select 1.0 that delays
sending of negotiation protocol frames as much as possible
but is only safe to use under additional assumptions that
go beyond what is required by the multistream-select v1
specification.
* Rework the transport upgrade API.
ALthough transport upgrades must follow a specific pattern
in order fot the resulting transport to be usable with a
`Network` or `Swarm`, that pattern is currently not well
reflected in the transport upgrade API. Rather, transport
upgrades are rather laborious and involve non-trivial code
duplication.
This commit introduces a `transport::upgrade::Builder` that is
obtained from `Transport::upgrade`. The `Builder` encodes the
previously implicit rules for transport upgrades:
1. Authentication upgrades must happen first.
2. Any number of upgrades may follow.
3. A multiplexer upgrade must happen last.
Since multiplexing is the last (regular) transport upgrade (because
that upgrade yields a `StreamMuxer` which is no longer a `AsyncRead`
/ `AsyncWrite` resource, which the upgrade process is based on),
the upgrade starts with `Transport::upgrade` and ends with
`Builder::multiplex`, which drops back down to the `Transport`,
providing a fluent API.
Authentication and multiplexer upgrades must furthermore adhere
to a minimal contract w.r.t their outputs:
1. An authentication upgrade is given an (async) I/O resource `C`
and must produce a pair `(I, D)` where `I: ConnectionInfo` and
`D` is a new (async) I/O resource `D`.
2. A multiplexer upgrade is given an (async) I/O resource `C`
and must produce a `M: StreamMuxer`.
To that end, two changes to the `secio` and `noise` protocols have been
made:
1. The `secio` upgrade now outputs a pair of `(PeerId, SecioOutput)`.
The former implements `ConnectionInfo` and the latter `AsyncRead` /
`AsyncWrite`, fulfilling the `Builder` contract.
2. A new `NoiseAuthenticated` upgrade has been added that wraps around
any noise upgrade (i.e. `NoiseConfig`) and has an output of
`(PeerId, NoiseOutput)`, i.e. it checks if the `RemoteIdentity` from
the handshake output is an `IdentityKey`, failing if that is not the
case. This is the standard upgrade procedure one wants for integrating
noise with libp2p-core/swarm.
* Cleanup
* Add a new integration test.
* Add missing license.
* Refactor the Identify protocol.
Thereby updating the documentation. The low-level protocol
and handler modules are no longer exposed and some constructors
of the IdentifyEvent renamed.
* Update protocols/identify/src/protocol.rs
Co-Authored-By: Pierre Krieger <pierre.krieger1708@gmail.com>
* Remove tokio-codec dependency from multistream-select.
In preparation for the eventual switch from tokio to std futures.
Includes some initial refactoring in preparation for further work
in the context of https://github.com/libp2p/rust-libp2p/issues/659.
* Reduce default buffer sizes.
* Allow more than one frame to be buffered for sending.
* Doc tweaks.
* Remove superfluous (duplicated) Message types.
* Reduce roundtrips in multistream-select negotiation.
1. Enable 0-RTT: If the dialer only supports a single protocol, it can send
protocol data (e.g. the actual application request) together with
the multistream-select header and protocol proposal. Similarly,
if the listener supports a proposed protocol, it can send protocol
data (e.g. the actual application response) together with the
multistream-select header and protocol confirmation.
2. In general, the dialer "settles on" an expected protocol as soon
as it runs out of alternatives. Furthermore, both dialer and listener
do not immediately flush the final protocol confirmation, allowing it
to be sent together with application protocol data. Attempts to read
from the negotiated I/O stream implicitly flushes any pending data.
3. A clean / graceful shutdown of an I/O stream always completes protocol
negotiation.
The publich API of multistream-select changed slightly, requiring both
AsyncRead and AsyncWrite bounds for async reading and writing due to
the implicit buffering and "lazy" negotiation. The error types have
also been changed, but they were not previously fully exported.
Includes some general refactoring with simplifications and some more tests,
e.g. there was an edge case relating to a possible ambiguity when parsing
multistream-select protocol messages.
* Further missing commentary.
* Remove unused test dependency.
* Adjust commentary.
* Cleanup NegotiatedComplete::poll()
* Fix deflate protocol tests.
* Stabilise network_simult test.
The test implicitly relied on "slow" connection establishment
in order to have a sufficient probability of passing.
With the removal of roundtrips in multistream-select, it is now
more likely that within the up to 50ms duration between swarm1
and swarm2 dialing, the connection is already established, causing
the expectation of step == 1 to fail when receiving a Connected event,
since the step may then still be 0.
This commit aims to avoid these spurious errors by detecting runs
during which a connection is established "too quickly", repeating
the test run.
It still seems theoretically possible that, if connections are always
established "too quickly", the test runs forever. However, given that
the delta between swarm1 and swarm2 dialing is 0-50ms and that the
TCP transport is used, that seems probabilistically unlikely.
Nevertheless, the purpose of the artificial dialing delay between
swarm1 and swarm2 should be re-evaluated and possibly at least
the maximum delay further reduced.
* Complete negotiation between upgrades in libp2p-core.
While multistream-select, as a standalone library and providing
an API at the granularity of a single negotiation, supports
lazy negotiation (and in particular 0-RTT negotiation), in the
context of libp2p-core where any number of negotiations are
composed generically within the concept of composable "upgrades",
it is necessary to wait for protocol negotiation between upgrades
to complete.
* Clarify docs. Simplify listener upgrades.
Since reading from a Negotiated I/O stream implicitly flushes any pending
negotiation data, there is no pitfall involved in not waiting for completion.
* Remove pending RPCs on query completion.
Ensure that any still pending RPCs related to a query are removed
once the query terminates (successfully or through timeout) by
scoping pending RPCs to the lifetime of a query.
* Cleanup.
* Somewhat complete the implementation of Kademlia records.
This commit relates to [libp2p-146] and [libp2p-1089].
* All records expire (by default, configurable).
* Provider records are also stored in the RecordStore, and the RecordStore
API extended.
* Background jobs for periodic (re-)replication and (re-)publication
of records. Regular (value-)records are subject to re-replication and
re-publication as per standard Kademlia. Provider records are only
subject to re-publication.
* For standard Kademlia value lookups (quorum = 1), the record is cached
at the closest peer to the key that did not return the value, as per
standard Kademlia.
* Expiration times of regular (value-)records is computed exponentially
inversely proportional to the number of nodes between the local node
and the closest node known to the key (beyond the k closest), as per
standard Kademlia.
The protobuf messages are extended with two fields: `ttl` and `publisher`
in order to implement the different semantics of re-replication (by any
of the k closest peers to the key, not affecting expiry) and re-publication
(by the original publisher, resetting the expiry). This is not done yet in
other libp2p Kademlia implementations, see e.g. [libp2p-go-323]. The new protobuf fields
have been given somewhat unique identifiers to prevent future collision.
Similarly, periodic re-publication of provider records does not seem to
be done yet in other implementations, see e.g. [libp2p-js-98].
[libp2p-146]: https://github.com/libp2p/rust-libp2p/issues/146
[libp2p-1089]: https://github.com/libp2p/rust-libp2p/issues/1089
[libp2p-go-323]: https://github.com/libp2p/go-libp2p-kad-dht/issues/323
[libp2p-js-98]: https://github.com/libp2p/js-libp2p-kad-dht/issues/98
* Tweak kad-ipfs example.
* Add missing files.
* Ensure new delays are polled immediately.
To ensure task notification, since `NotReady` is returned right after.
* Fix ipfs-kad example and use wasm_timer.
* Small cleanup.
* Incorporate some feedback.
* Adjustments after rebase.
* Distinguish events further.
In order for a user to easily distinguish the result of e.g.
a `put_record` operation from the result of a later republication,
different event constructors are used. Furthermore, for now,
re-replication and "caching" of records (at the closest peer to
the key that did not return a value during a successful lookup)
do not yield events for now as they are less interesting.
* Speed up tests for CI.
* Small refinements and more documentation.
* Guard a node against overriding records for which it considers
itself to be the publisher.
* Document the jobs module more extensively.
* More inline docs around removal of "unreachable" addresses.
* Remove wildcard re-exports.
* Use NonZeroUsize for the constants.
* Re-add method lost on merge.
* Add missing 'pub'.
* Further increase the timeout in the ipfs-kad example.
* Readd log dependency to libp2p-kad.
* Simplify RecordStore API slightly.
* Some more commentary.
* Change Addresses::remove to return Result<(),()>.
Change the semantics of `Addresses::remove` so that the error case
is unambiguous, instead of the success case. Use the `Result` for
clearer semantics to that effect.
* Add some documentation to .
* Adds a retain method to kademlia.
* Add a store_mut getter to Kademlia
* Removes a blank line
* Changes store_mut comment appropriately
* Fixes build
* Return a type, not a trait
* Address some TODOs, refactor queries and public API.
The following left-over issues are addressed:
* The key for FIND_NODE requests is generalised to any Multihash,
instead of just peer IDs.
* All queries get a (configurable) timeout.
* Finishing queries as soon as enough results have been received is simplified
to avoid code duplication.
* No more panics in provider-API-related code paths. The provider API is
however still untested and (I think) still incomplete (e.g. expiration
of provider records).
* Numerous smaller TODOs encountered in the code.
The following public API changes / additions are made:
* Introduce a `KademliaConfig` with new configuration options for
the replication factor and query timeouts.
* Rename `find_node` to `get_closest_peers`.
* Rename `get_value` to `get_record` and `put_value` to `put_record`,
introducing a `Quorum` parameter for both functions, replacing the
existing `num_results` parameter with clearer semantics.
* Rename `add_providing` to `start_providing` and `remove_providing`
to `stop_providing`.
* Add a `bootstrap` function that implements a (almost) standard
Kademlia bootstrapping procedure.
* Rename `KademliaOut` to `KademliaEvent` with an updated list of
constructors (some renaming). All events that report query results
now report a `Result` to uniformly permit reporting of errors.
The following refactorings are made:
* Introduce some constants.
* Consolidate `query.rs` and `write.rs` behind a common query interface
to reduce duplication and facilitate better code reuse, introducing
the notion of a query peer iterator. `query/peers/closest.rs`
contains the code that was formerly in `query.rs`. `query/peers/fixed.rs` contains
a modified variant of `write.rs` (which is removed). The new `query.rs`
provides an interface for working with a collection of queries, taking
over some code from `behaviour.rs`.
* Reduce code duplication in tests and use the current_thread runtime for
polling swarms to avoid spurious errors in the test output due to aborted
connections when a test finishes prematurely (e.g. because a quorum of
results has been collected).
* Some additions / improvements to the existing tests.
* Fix test.
* Fix rebase.
* Tweak kad-ipfs example.
* Incorporate some feedback.
* Provide easy access and conversion to keys in error results.
Refactoring of iterative queries (`query.rs`) to improve both
correctness and performance (for larger DHTs):
Correctness:
1. Queries no longer terminate prematurely due to counting results
from peers farther from the target while results from closer
peers are still pending. (#1105).
2. Queries no longer ignore reported closer peers that are not duplicates
just because they are currently not among the `num_results` closest.
The currently `max_results` closest may contain peers marked as failed
or pending / waiting. Hence all reported closer peers that are not
duplicates must be considered candidates that may still end up
among the `num_results` closest that successfully responded.
3. Bounded parallelism based on the `active_counter` was not working
correctly, as new (not yet contacted) peers closer to the target
may be discovered at any time and thus appear in `closer_peers`
before the already active / pending peers.
4. The `Frozen` query mechanism allowed all remaining not-yet contacted
peers to be contacted, but their results were discarded, because
`inject_rpc_result` would only incorporate results while the
query is `Iterating`. The `Frozen` state has been reworked into
a `Stalled` state that implements a slightly more permissive
variant of the following from the paper / specs: "If a round of
FIND_NODEs fails to return a node any closer than the closest
already seen, the initiator resends the FIND_NODE to all of the
k closest nodes it has not already queried.". Importantly, though
not explicitly mentioned, the query can move back to `Iterating`
if it makes further progress again as a result of these requests.
The `Stalled` state thus allows (temporarily) higher parallelism
in an effort to make progress and bring the query to an end.
Performance:
1. Repeated distance calculations between the same peers and the
target is avoided.
2. Enabled by #1108, use of a more appropriate data structure (`BTreeMap`) for
the incrementally updated list of closer peers. The data structure needs
efficient lookups (to avoid duplicates) and insertions at any position,
both of which large(r) vectors are not that good at. Unscientific benchmarks
showed a ~40-60% improvement in somewhat pathological scenarios with at least
20 healthy nodes, each possibly returning a distinct list of closer 20 peers
to the requestor. A previous assumption may have been that the vector always
stays very small, but that is not the case in larger clusters: Even if the
lists of closer peers reported by the 20 contacted peers are heavily overlapping,
typically a lot more than 20 peers have to be (at least temporarily) considered
as closest peers until the query completes. See also issue (2) above.
New tests are added for:
* Query termination conditions.
* Bounded parallelism.
* Absence of duplicates.
* initial implementation of the records
* move to multihash keys
* correctly process query results
* comments and formatting
* correctly return closer_peers in query
* checking wrong peer id in test
* Apply suggestions from code review
Co-Authored-By: Roman Borschel <romanb@users.noreply.github.com>
* Fix changes from suggestions
* Send responses to PUT_VALUE requests
* Shortcut in get_value
* Update protocols/kad/src/behaviour.rs
Co-Authored-By: Roman Borschel <romanb@users.noreply.github.com>
* Revert "Update protocols/kad/src/behaviour.rs"
This reverts commit 579ce742a7f4c94587f1e1f0866d2a3a37418efb.
* Remove duplicate insertion
* Adds a record to a PUT_VALUE response
* Fix a racy put_value test
* Store value ourselves only if we are in K closest
* Abstract over storage
* Revert "Abstract over storage": bad take
This reverts commit eaebf5b6d915712eaf3b05929577fdf697f204d8.
* Abstract over records storage using hashmap as default
* Constructor for custom records
* New Record type and its traits
* Fix outdated storage name
* Fixes returning an event
* Change FindNodeReq key type to Multihash
* WriteState for a second stage of a PUT_VALUE request
* GET_VALUE should not have a record
* Refactor a match arm
* Add successes and failures counters to PutValueRes
* If value is found no need to return closer peers
* Remove a custo storage from tests
* Rename a test to get_value_not_found
* Adds a TODO to change FindNode request key to Multihash
Co-Authored-By: Roman Borschel <romanb@users.noreply.github.com>
* Move MemoryRecordStorage to record.rs
* Return a Cow-ed Record from get
* Fix incorrect GET_VALUE parsing
* Various fixes with review
* Fixes get_value_not_found
* Fix peerids names in test
* another fix
* PutValue correctly distributes values
* Simplify the test
* Check that results are actually the closest
* Reverts changes to tests
* Fix the test topology and checking the results
* Run put_value test ten times
* Adds a get_value test
* Apply suggestions from code review
Co-Authored-By: Roman Borschel <romanb@users.noreply.github.com>
* Make Record fields public
* Moves WriteState to write.rs
* A couple of minor fixes
* Another few fixes of review
* Simplify the put_value test
* Dont synchronously return an error from put_value
* Formatting fixes and comments
* Collect a bunch of results
* Take exactly as much elements as neede
* Check if the peer is still connected
* Adds a multiple GetValueResults results number test
* Unnecessary mut iterators in put_value
* Ask for num_results in get_value
* Dont allocate twice in get_value
* Dont count same errored peer multiple times
* Apply suggestions from code review
Co-Authored-By: Roman Borschel <romanb@users.noreply.github.com>
* Fix another review
* Apply suggestions from code review
Co-Authored-By: Pierre Krieger <pierre.krieger1708@gmail.com>
* Bring back FromIterator and improve a panic message
* Update protocols/kad/src/behaviour.rs
Co-Authored-By: Pierre Krieger <pierre.krieger1708@gmail.com>
* Fix status updates in KBuckets.
`KBucket::update` does currently not correctly update the `first_connected_pos`
before reinserting the node. This may result in connected nodes being considered
disconnected and thus eligible for replacement by a pending node if the bucket is
full and a new connected node is added.
Tests have been added for checking that `KBucket::update` preserves the status
and ordering of all other nodes in the bucket.
* Small test improvement.
Set an expectation for the new position, instead of taking the assigned position.
* Kademlia: Optimise iteration over closest entries.
The current implementation for finding the entries whose keys are closest
to some target key in the Kademlia routing table involves copying the
keys of all buckets into a new `Vec` which is then sorted based on the
distances to the target and turned into an iterator from which only a
small number of elements (by default 20) are drawn.
This commit introduces an iterator over buckets for finding the closest
keys to a target that visits the buckets in the optimal order, based on
the information contained in the distance bit-string representing the
distance between the local key and the target.
Correctness is tested against full-table scans.
Also included:
* Updated documentation.
* The `Entry` API was moved to the `kbucket::entry` sub-module for
ease of maintenance.
* The pending node handling has been slightly refactored in order to
bring code and documentation in agreement and clarify the semantics
a little.
* Rewrite pending node handling and add tests.
There are two issues with the current definition and use of Kademlia's
XOR metric:
1. The distance is currently equated with the bucket index, i.e.
`distance(a,b) - 1` is the index of the bucket into which either
peer is put by the other. The result is a metric that is not
unidirectional, as defined in the Kademlia paper and as implemented
in e.g. libp2p-go and libp2p-js, which is to interpret the result
of the XOR as an integer in its entirety.
2. The current `KBucketsPeerId` trait and its instances allow computing
distances between types with differing bit lengths as well as between
types that hash all inputs again (i.e. `KadHash`) and "plain" `PeerId`s
or `Multihash`es. This can result in computed distances that are either
incorrect as per the requirement of the libp2p specs that all distances
are to be computed from the XOR of the SHA256 of the input keys, or
even fall outside of the image of the metric used for the `KBucketsTable`.
In the latter case, such distances are not currently used as a bucket index
- they can only occur in the context of comparing distances for the purpose
of sorting peers - but that still seems undesirable.
These issues are addressed here as follows:
* Unidirectionality of the XOR metric is restored by keeping the "full"
integer representation of the bitwise XOR. The result is an XOR metric
as defined in the paper. This also opens the door to avoiding the
"full table scan" when searching for the keys closest to a given key -
the ideal order in which to visit the buckets can be computed with the
help of the distance bit string.
* As a simplification and to make it easy to "do the right thing", the
XOR metric is only defined on an opaque `kbucket::Key` type, partially
derived from the current `KadHash`. `KadHash` and `KBucketsPeerId`
are removed.
