Algorithm-Kademlia
view release on metacpan or search on metacpan
These are bitwise logic utilities for the Kademlia XOR metrics.
## `xor_distance( $id1, $id2 )`
Returns the bitwise XOR of two binary strings.
```perl
my $id1 = pack('H*', '00' x 20);
my $id2 = pack('H*', 'ff' x 20);
my $dist = xor_distance($id1, $id2);
say unpack('H*', $dist); # ffffffffffffffffffffffffffffffffffffffff
```
## `xor_bucket_index( $id1, $id2 )`
Calculates the index of the k-bucket that `$id2` would fall into relative to `$id1`. Returns `undef` if the IDs are
identical.
The index corresponds to the bit position of the most significant bit that differs between the two IDs. For 160-bit
IDs, the result is between 0 and 159.
```perl
my $local = pack('H*', '00' x 20);
my $peer = pack('H*', '80' . ('00' x 19)); # 160th bit differs
my $idx = xor_bucket_index($local, $peer);
say $idx; # 159
```
# Algorithm::Kademlia::RoutingTable
This class implements the 160 k-bucket structure (or appropriate size for the ID length provided). Peers are bucketed
by their XOR distance from the local node ID.
## `new( local_id_bin => ..., [ k => 20 ] )`
Constructor. `local_id_bin` is the binary string of the local node's ID.
$rt->evict_peer($stale_id);
```
## `find_closest( $target_id_bin, [ $count ] )`
Returns a list of up to `$count` (defaults to `k`) peers closest to the target ID according to the XOR metric.
```perl
my @peers = $rt->find_closest($target_key, 10);
for my $peer (@peers) {
say 'Node ' . unpack('H*', $peer->{id}) . ' is at ' . $peer->{data}{ip};
}
```
## `size( )`
Returns the total number of peers across all buckets.
```
say 'Routing table has ' . $rt->size . ' peers';
```
# Algorithm::Kademlia::Storage
A simple in-memory key-value store intended to hold the DHT data.
## `new( [ ttl => 86400 ] )`
Constructor. `ttl` is the time-to-live for entries in seconds.
die 'Expired or not found' unless defined $data;
```
## `entries( )`
Returns a hash reference of all non-expired entries in the store.
```perl
my %all = $storage->entries();
for my ($key, $info) (%all) {
say 'Key: ' . unpack('H*', $key) . ' Value: ' . $info->{value};
}
```
# Algorithm::Kademlia::Search
A state manager for the iterative Kademlia lookup algorithm. It tracks which nodes have been queried, which have
responded, and which have failed.
## `new( target_id_bin => ..., [ k => 20, alpha => 3 ] )`
```
$search->add_candidates( $rt->find_closest($target_key) );
```
## `pending_queries( )`
Returns a list of nodes that have been queried but have not yet responded or failed.
```perl
my @waiting = $search->pending_queries();
say 'Waiting for ' . scalar(@waiting) . ' nodes...';
```
## `next_to_query( )`
Returns a list of up to `alpha` nodes that have not yet been queried, sorted by proximity to the target.
```perl
my @to_query = $search->next_to_query();
# Now send your RPCs to these nodes...
```
eg/kademlia_demo.pl view on Meta::CPAN
my $local_id = pack 'H*', '00' x 32;
my $rt = Algorithm::Kademlia::RoutingTable->new( local_id_bin => $local_id );
# Fill with some dummy peers
for ( 1 .. 50 ) {
my $pid = pack 'C*', map { int rand 256 } 1 .. 32;
$rt->add_peer( $pid, { index => $_ } );
}
my $target = pack 'H*', 'ff' x 32;
my @closest = $rt->find_closest( $target, 3 );
say 'Top 3 closest peers to FF...:';
say sprintf ' - ID: %s (Peer #%s)', unpack( 'H*', $_->{id} ), $_->{data}{index} for @closest
lib/Algorithm/Kademlia.pod view on Meta::CPAN
These are bitwise logic utilities for the Kademlia XOR metrics.
=head2 C<xor_distance( $id1, $id2 )>
Returns the bitwise XOR of two binary strings.
my $id1 = pack('H*', '00' x 20);
my $id2 = pack('H*', 'ff' x 20);
my $dist = xor_distance($id1, $id2);
say unpack('H*', $dist); # ffffffffffffffffffffffffffffffffffffffff
=head2 C<xor_bucket_index( $id1, $id2 )>
Calculates the index of the k-bucket that C<$id2> would fall into relative to C<$id1>. Returns C<undef> if the IDs are
identical.
The index corresponds to the bit position of the most significant bit that differs between the two IDs. For 160-bit
IDs, the result is between 0 and 159.
my $local = pack('H*', '00' x 20);
my $peer = pack('H*', '80' . ('00' x 19)); # 160th bit differs
my $idx = xor_bucket_index($local, $peer);
say $idx; # 159
=head1 Algorithm::Kademlia::RoutingTable
This class implements the 160 k-bucket structure (or appropriate size for the ID length provided). Peers are bucketed
by their XOR distance from the local node ID.
=head2 C<new( local_id_bin =E<gt> ..., [ k =E<gt> 20 ] )>
Constructor. C<local_id_bin> is the binary string of the local node's ID.
lib/Algorithm/Kademlia.pod view on Meta::CPAN
Removes a peer from the routing table. Usually called after a stale peer fails a ping check.
$rt->evict_peer($stale_id);
=head2 C<find_closest( $target_id_bin, [ $count ] )>
Returns a list of up to C<$count> (defaults to C<k>) peers closest to the target ID according to the XOR metric.
my @peers = $rt->find_closest($target_key, 10);
for my $peer (@peers) {
say 'Node ' . unpack('H*', $peer->{id}) . ' is at ' . $peer->{data}{ip};
}
=head2 C<size( )>
Returns the total number of peers across all buckets.
say 'Routing table has ' . $rt->size . ' peers';
=head1 Algorithm::Kademlia::Storage
A simple in-memory key-value store intended to hold the DHT data.
=head2 C<new( [ ttl =E<gt> 86400 ] )>
Constructor. C<ttl> is the time-to-live for entries in seconds.
my $storage = Algorithm::Kademlia::Storage->new( ttl => 3600 );
lib/Algorithm/Kademlia.pod view on Meta::CPAN
my $data = $storage->get($cid_bin);
die 'Expired or not found' unless defined $data;
=head2 C<entries( )>
Returns a hash reference of all non-expired entries in the store.
my %all = $storage->entries();
for my ($key, $info) (%all) {
say 'Key: ' . unpack('H*', $key) . ' Value: ' . $info->{value};
}
=head1 Algorithm::Kademlia::Search
A state manager for the iterative Kademlia lookup algorithm. It tracks which nodes have been queried, which have
responded, and which have failed.
=head2 C<new( target_id_bin =E<gt> ..., [ k =E<gt> 20, alpha =E<gt> 3 ] )>
Constructor. C<alpha> is the concurrency parameter (how many parallel queries to allow).
lib/Algorithm/Kademlia.pod view on Meta::CPAN
Adds new potential nodes to the search shortlist.
$search->add_candidates( $rt->find_closest($target_key) );
=head2 C<pending_queries( )>
Returns a list of nodes that have been queried but have not yet responded or failed.
my @waiting = $search->pending_queries();
say 'Waiting for ' . scalar(@waiting) . ' nodes...';
=head2 C<next_to_query( )>
Returns a list of up to C<alpha> nodes that have not yet been queried, sorted by proximity to the target.
my @to_query = $search->next_to_query();
# Now send your RPCs to these nodes...
=head2 C<mark_responded( $id_bin, @new_peers )>
( run in 0.373 second using v1.01-cache-2.11-cpan-483215c6ad5 )