k-bucket - npm Package Compare versions

Comparing version 0.3.1 to 0.4.0

index.js

		@@ -7,3 +7,3 @@ /*

		Copyright (c) 2013 Tristan Slominski
		Copyright (c) 2013-2014 Tristan Slominski

		@@ -46,2 +46,10 @@ Permission is hereby granted, free of charge, to any person

		// use an arbiter from options or vectorClock arbiter by default
		self.arbiter = options.arbiter \|\| function arbiter(incumbent, candidate) {
		if (incumbent.vectorClock > candidate.vectorClock) {
		return incumbent;
		}
		return candidate;
		};

		// the bucket array has least-recently-contacted at the "front/left" side
		@@ -334,8 +342,10 @@ // and the most-recently-contaced at the "back/right" side

		// Updates the contact by comparing vector clocks.
		// If new contact vector clock is deprecated, contact is abandoned (not added).
		// If new contact vector clock is the same, contact is marked as most recently
		// Updates the contact selected by the arbiter.
		// If the selection is our old contact and the candidate is some new contact
		// then the new contact is abandoned (not added).
		// If the selection is our old contact and the candidate is our old contact
		// then we are refreshing the contact and it is marked as most recently
		// contacted (by being moved to the right/end of the bucket array).
		// If new contact vector clock is more recent, the old contact is removed and
		// the new contact is marked as most recently contacted.
		// If the selection is our new contact, the old contact is removed and the new
		// contact is marked as most recently contacted.
		// contact: required the contact to update
		@@ -349,6 +359,13 @@ // index: required the index in the bucket where contact exists
		"indexOf() calculation resulted in wrong index");
		if (self.bucket[index].vectorClock > contact.vectorClock)

		var incumbent = self.bucket[index];
		var selection = self.arbiter(incumbent, contact);
		if (selection === incumbent && incumbent !== contact) {
		// if the selection is our old contact and the candidate is some new
		// contact, then there is nothing to do
		return;
		}

		self.bucket.splice(index, 1); // remove old contact
		self.bucket.push(contact); // add more recent contact version
		self.bucket.push(selection); // add more recent contact version
		};

package.json

		{
		"name": "k-bucket",
		"version": "0.3.1",
		"version": "0.4.0",
		"description": "Kademlia DHT K-bucket implementation as a binary tree",
		@@ -5,0 +5,0 @@ "scripts": {

README.md

		@@ -5,2 +5,4 @@ # k-bucket

		[![NPM version](https://badge.fury.io/js/k-bucket.png)](http://npmjs.org/package/k-bucket)

		Kademlia DHT K-bucket implementation as a binary tree.
		@@ -36,6 +38,55 @@

		This Kademlia DHT k-bucket implementation is meant to be as minimal as possible. It assumes that `contact` objects consist only of `id`, and an optional `vectorClock`. 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 the application to send IP traffic to the `contact`. However, this information is extraneous and irrelevant to the operation of a k-bucket.
		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.

		It is worth highlighting the presence of an optional `vectorClock` as part of `contact` implementation. The purpose of the `vectorClock` (a simple integer) is to enable distinguishing between `contact` objects that may have "physically" moved to a different machine while keeping the same `contact.id`. This is useful when working with actors and an actor moves from one machine to another.
		### arbiter function

		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)](#kbucketupdatecontact-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:

		```javascript
		// 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:

		```javascript
		// 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.

		## Documentation
		@@ -75,2 +126,3 @@
		* `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](#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.
		@@ -137,3 +189,3 @@ * `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.

		_NOTE: `kBucket.indexOf(contact)` does not compare `contact.vectorClock`_
		_NOTE: `kBucket.indexOf(contact)` does not use `arbiter` in the comparison.

		@@ -177,3 +229,3 @@ #### kBucket.remove(contact, [bitIndex])

		Updates the `contact` and compares the vector clocks if provided. If new `contact` vector clock is deprecated, `contact` is abandoned (not added). If new `contact` vector clock is the same, `contact` is marked as moste recently contacted (by being moved to the right/end of the bucket array). If new `contact` vector clock is more recent, the old `contact` is removed and the new contact is marked as most recently contacted.
		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.

		@@ -180,0 +232,0 @@ #### Event: 'ping'

k-bucket - npm Package Compare versions

New alerts

Fixed alerts

Improved metrics