Security News
JavaScript Leaders Demand Oracle Release the JavaScript Trademark
In an open letter, JavaScript community leaders urge Oracle to give up the JavaScript trademark, arguing that it has been effectively abandoned through nonuse.
Stability: 1 - Experimental
Kademlia DHT K-bucket implementation as a binary tree.
@tristanls, @mikedeboer, @deoxxa, @feross, @nathanph
npm install k-bucket
npm test
var KBucket = require('k-bucket');
var kBucket = new KBucket({
localNodeId: new Buffer("my node id") // default: random data
});
A Distributed Hash Table (DHT) is a decentralized distributed system that provides a lookup table similar to a hash table.
k-bucket is an implementation of a storage mechanism for keys within a DHT. It stores contact
objects which represent locations and addresses of nodes in the decentralized distributed system. contact
objects are typically identified by a SHA-1 hash, however this restriction is lifted in this implementation. Additionally, node ids of different lengths can be compared.
This Kademlia DHT k-bucket implementation is meant to be as minimal as possible. It assumes that contact
objects consist only of id
. It is useful, and necessary, to attach other properties to a contact
. For example, one may want to attach ip
and port
properties, which allow an application to send IP traffic to the contact
. However, this information is extraneous and irrelevant to the operation of a k-bucket.
This k-bucket implementation implements a conflict resolution mechanism using an arbiter
function. The purpose of the arbiter
is to choose between two contact
objects with the same id
but perhaps different properties and determine which one should be stored. As the arbiter
function returns the actual object to be stored, it does not need to make an either/or choice, but instead could perform some sort of operation and return the result as a new object that would then be stored. See kBucket.update(contact, index) for detailed semantics of which contact
(incumbent
or candidate
) is selected.
For example, an arbiter
function implementing a vectorClock
mechanism would look something like:
// contact example
var contact = {
id: new Buffer('contactId'),
vectorClock: 0
};
function arbiter(incumbent, candidate) {
if (incumbent.vectorClock > candidate.vectorClock) {
return incumbent;
}
return candidate;
};
Alternatively, consider an arbiter that implements a Grow-Only-Set CRDT mechanism:
// contact example
var contact = {
id: new Buffer('workerService'),
workerNodes: {
'17asdaf7effa2': { host: '127.0.0.1', port: 1337 },
'17djsyqeryasu': { host: '127.0.0.1', port: 1338 }
}
};
function arbiter(incumbent, candidate) {
// we create a new object so that our selection is guaranteed to replace
// the incumbent
var merged = {
id: incumbent.id, // incumbent.id === candidate.id within an arbiter
workerNodes: incumbent.workerNodes
};
Object.keys(candidate.workerNodes).forEach(function (workerNodeId) {
merged.workerNodes[workerNodeId] = candidate.workerNodes[workerNodeId];
});
return merged;
}
Notice that in the above case, the Grow-Only-Set assumes that each worker node has a globally unique id.
Implementation of a Kademlia DHT k-bucket used for storing contact (peer node) information.
For a step by step example of k-bucket operation you may find the following slideshow useful: Distribute All The Things.
KBucket starts off as a single k-bucket with capacity of k. As contacts are added, once the k+1 contact is added, the k-bucket is split into two k-buckets. The split happens according to the first bit of the contact node id. The k-bucket that would contain the local node id is the "near" k-bucket, and the other one is the "far" k-bucket. The "far" k-bucket is marked as don't split in order to prevent further splitting. The contact nodes that existed are then redistributed along the two new k-buckets and the old k-bucket becomes an inner node within a tree data structure.
As even more contacts are added to the "near" k-bucket, the "near" k-bucket will split again as it becomes full. However, this time it is split along the second bit of the contact node id. Again, the two newly created k-buckets are marked "near" and "far" and the "far" k-bucket is marked as don't split. Again, the contact nodes that existed in the old bucket are redistributed. This continues as long as nodes are being added to the "near" k-bucket, until the number of splits reaches the length of the local node id.
As more contacts are added to the "far" k-bucket and it reaches its capacity, it does not split. Instead, the k-bucket emits a "ping" event (register a listener: kBucket.on('ping', function (oldContacts, newContact) {...});
and includes an array of old contact nodes that it hasn't heard from in a while and requires you to confirm that those contact nodes still respond (literally respond to a PING RPC). If an old contact node still responds, it should be re-added (kBucket.add(oldContact)
) back to the k-bucket. This puts the old contact on the "recently heard from" end of the list of nodes in the k-bucket. If the old contact does not respond, it should be removed (kBucket.remove(oldContact)
) and the new contact being added now has room to be stored (kBucket.add(newContact)
).
Public API
firstId
: Buffer Buffer containing first id.secondId
: Buffer Buffer containing second id.firstId
and secondId
.Finds the XOR distance between firstId and secondId.
options
:
arbiter
: Function (Default: vectorClock arbiter) function (incumbent, candidate) { return contact; }
An optional arbiter
function that givent two contact
objects with the same id
returns the desired object to be used for updating the k-bucket. For more details, see arbiter function.localNodeId
: String (base64) or Buffer An optional String or a Buffer representing the local node id. If not provided, a local node id will be created via crypto.randomBytes(20)
. If a String is provided, it will be assumed to be base64 encoded and will be converted into a Buffer.numberOfNodesPerKBucket
: Integer (Default: 20) The number of nodes that a k-bucket can contain before being full or split.numberOfNodesToPing
: Integer (Default: 3) The number of nodes to ping when a bucket that should not be split becomes full. KBucket will emit a ping
event that contains numberOfNodesToPing
nodes that have not been contacted the longest.root
: Object CAUTION: reserved for internal use Provides a reference to the root of the tree data structure as the k-bucket splits when new contacts are added.Creates a new KBucket.
contact
: Object The contact object to add.
id
: Buffer Contact node id.contact
object will not be altered, only id
is used.bitIndex
: Integer (Default: 0) CAUTION: reserved for internal use The bit index to which bit to check in the id
Buffer.Adds a contact
to the k-bucket.
contact
: Object The contact object to find closest contacts to.
id
: Buffer Contact node id.contact
object will not be altered, only id
is used.n
: Integer The maximum number of closest contacts to return.bitIndex
: Integer (Default: 0) CAUTION: reserved for internal use The bit index to which bit to check in the id
Buffer.n
closest contacts to the contact
.Get the n
closest contacts to the provided contact
. "Closest" here means: closest according to the XOR metric of the contact
node id.
Counts the total number of contacts in the tree.
CAUTION: reserved for internal use
id
: Buffer Id to compare localNodeId
with.bitIndex
: Integer (Default: 0) The bit index to which bit to check in the id
Buffer.id
at bitIndex
is 0, 1 otherwise.Determines whether the id
at the bitIndex
is 0 or 1. If 0, returns -1, else 1.
id
: Buffer The ID of the contact
to fetchbitIndex
: Integer (Default: 0) CAUTION: reserved for internal use The bit index to which bit to check in the id
Buffer.contact
if available, otherwise nullRetrieves the contact
.
CAUTION: reserved for internal use
contact
: Object The contact object.
id
: Buffer Contact node id.contact
object will not be altered, only id
is used.contact
if it exists, -1 otherwise.Returns the index of the contact
if it exists, returns -1 otherwise.
_NOTE: kBucket.indexOf(contact)
does not use arbiter
in the comparison.
contact
: Object The contact object to remove.
id
: Buffer contact node id.contact
object, only id
is usedbitIndex
: Integer (Default: 0) CAUTION: reserved for internal use The bit index to which bit to check in the id
Buffer.Removes the contact
.
CAUTION: reserved for internal use
contact
: Object The contact object to add.
id
: Buffer Contact node id.contact
object will not be altered, only id
is used.bitIndex
: Integer (Default: 0) The bit index to which bit to check in the id
Buffer.Splits the bucket, redistributes contacts to the new buckets, and marks the bucket that was split as an inner node of the binary tree of buckets by setting self.bucket = undefined
. Also, marks the "far away" bucket as dontSplit
.
Traverses the tree, putting all the contacts into one array.
CAUTION: reserved for internal use
contact
: Object The contact object to update.
id
: Buffer Contact node idcontact
object will not be altered, only id
is used.index
: Integer The index in the bucket where contact exists (index has already been computed in previous calculation).Updates the contact
by using the arbiter
function to compare the incumbent and the candidate. If arbiter
function selects the old contact
but the candidate is some new contact
, then the new contact
is abandoned. If arbiter
function selects the old contact
and the candidate is that same old contact
, the contact
is marked as most recently contacted (by being moved to the right/end of the bucket array). If arbiter
function selects the new contact
, the old contact
is removed and the new contact
is marked as most recently contacted.
oldContacts
: Array The array of contacts to ping.newContact
: Object The new contact to be added if one of old contacts does not respond.Emitted every time a contact is added that would exceed the capacity of a don't split k-bucket it belongs to.
The implementation has been sourced from:
FAQs
Kademlia DHT K-bucket implementation as a binary tree
We found that k-bucket demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
In an open letter, JavaScript community leaders urge Oracle to give up the JavaScript trademark, arguing that it has been effectively abandoned through nonuse.
Security News
The initial version of the Socket Python SDK is now on PyPI, enabling developers to more easily interact with the Socket REST API in Python projects.
Security News
Floating dependency ranges in npm can introduce instability and security risks into your project by allowing unverified or incompatible versions to be installed automatically, leading to unpredictable behavior and potential conflicts.