left-icon

The Kademlia Protocol Succinctly®
by Marc Clifton

download-button

Previous
Chapter

of

Next
Chapter

A
A
A

CHAPTER 7

The DHT Class

The DHT Class

We use a wrapper Dht class, which will become the main entry point for our peer, for interacting with other peers. The purposes of this class are:

  • When storing a value, use the lookup algorithm to find other closer peers to propagate the key-value.
  • When looking up a value, if our peer doesn’t have the value, we again use the lookup algorithm to find other closer nodes that might have the value.
  • Later, we’ll add a bootstrapping method that registers our peer with another peer and initializes our bucket list with that peer’s closest contacts.

Implementation

Code Listing 54: The Dht Class

public class Dht
{
  public BaseRouter Router { get { return router; } }
  public IProtocol Protocol { get { return protocol; } }
  public IStorage OriginatorStorage { get { return originatorStorage; } }

  public Contact Contact { get { return ourContact; } }


  protected BaseRouter router;

  protected IStorage originatorStorage;

  protected IProtocol protocol;

  protected Node node;

  public Dht(
    ID id,
    IProtocol protocol,
    Func<IStorage> storageFactory,
    BaseRouter router)

    {

      originatorStorage = storageFactory();

      FinishInitialization(id, protocol, router);

    }

  protected void FinishInitialization(ID id, IProtocol protocol, BaseRouter router)

  {

    ourId = id;

    ourContact = new Contact(protocol, id);

    node = new Node(ourContact);

    node.Dht = this;

    node.BucketList.Dht = this;

    this.protocol = protocol;

    this.router = router;

    this.router.Node = node;

    this.router.Dht = this;

  }

  public void Store(ID key, string val)

  {

    TouchBucketWithKey(key);

    // We're storing to k closer contacts.

    originatorStorage.Set(key, val);

    StoreOnCloserContacts(key, val);

  }


  public (bool found, List<Contact> contacts, string val) FindValue(ID key)

  {

    TouchBucketWithKey(key);

    string ourVal;

    List<Contact> contactsQueried = new List<Contact>();

    (bool found, List<Contact> contacts, string val) ret = (false, null, null);

    if (originatorStorage.TryGetValue(key, out ourVal))

    {

      // Sort of odd that we are using the key-value store to find
      // something the key-value that we originate.

      ret = (true, null, ourVal);

    }
    // else this is where we will deal with republish and cache storage later
    else

    {

      var lookup = router.Lookup(key, router.RpcFindValue);

      if (lookup.found)

      {

        ret = (true, null, lookup.val);

        // Find the first close contact (other than the one the value
        // was found by) in which to *cache* the key-value.

        var storeTo = lookup.contacts.Where(c => c != lookup.foundBy).
          OrderBy(c => c.ID ^ key).FirstOrDefault();

        if (storeTo != null)

        {

          int separatingNodes = GetSeparatingNodesCount(ourContact, storeTo);

          RpcError error = storeTo.Protocol.Store(
            node.OurContact,
            key,
            lookup.val,
            true,
            expTimeSec);

         HandleError(error, storeTo);

        }

      }

    }

  return ret;

  }

}

What exactly should the sender do when a value is not found? The Dht returns the nearest nodes, but given that the lookup failed to find the value, we know these nodes also do not have the value. As far as I’ve been able to determine, neither the spec nor a search of the web indicates what to do.

Unit tests

LocalStoreFoundValue

To get started, let’s just make sure we can set and get values in our local store with an empty bucket list.

Code Listing 55: LocalStoreFindValueTest

[TestMethod]

public void LocalStoreFoundValueTest()

{

  VirtualProtocol vp = new VirtualProtocol();

  Dht dht = new Dht(ID.RandomID, vp, () => new VirtualStorage(), new Router());

  vp.Node = dht.Router.Node;

  ID key = ID.RandomID;

  string val = "Test";

  dht.Store(key, val);

  string retval = dht.FindValue(key).val;

  Assert.IsTrue(retval == val, "Expected to get back what we stored");

}

ValueStoredInCloserNode

This test creates a single contact and stores the value in that contact. We set up the IDs so that the contact’s ID is less (XOR metric) than our peer’s ID, and we use a key of ID.Zero to prevent further complexities when computing the distance. Most of the code here is to set up the conditions to make this test!

Code Listing 56: ValueStoredInCloserNodeTest

[TestMethod]

public void ValueStoredInCloserNodeTest()

{

  VirtualProtocol vp1 = new VirtualProtocol();

  VirtualProtocol vp2 = new VirtualProtocol();

  VirtualStorage store1 = new VirtualStorage();

  VirtualStorage store2 = new VirtualStorage();

  // Ensures that all nodes are closer, because ID.Max ^ n < ID.Max when n > 0.

  Dht dht = new Dht(ID.Max, vp1, new Router(), store1, store1, new VirtualStorage());

  vp1.Node = dht.Router.Node;

  ID contactID = ID.Mid;      // a closer contact.

  Contact otherContact = new Contact(vp2, contactID);

  Node otherNode = new Node(otherContact, store2);

  vp2.Node = otherNode;

           

  // Add this other contact to our peer list.

  dht.Router.Node.BucketList.AddContact(otherContact);

  // We want an integer distance, not an XOR distance.

  ID key = ID.Zero;

  // Set the value in the other node, to be discovered by the lookup process.

  string val = "Test";

  otherNode.SimpleStore(key, val);

  Assert.IsFalse(store1.Contains(key),
    "Expected our peer to NOT have cached the key-value.");

  Assert.IsTrue(store2.Contains(key),
    "Expected other node to HAVE cached the key-value.");

  // Try and find the value, given our Dht knows about the other contact.

  string retval = dht.FindValue(key).val;

  Assert.IsTrue(retval == val, "Expected to get back what we stored");

}

The method SimpleStore simply stores the value in the node’s storage—this method is available only in DEBUG mode for unit testing.

Code Listing 57: SimpleStore

#if DEBUG           // For unit testing

public void SimpleStore(ID key, string val)

{

  storage.Set(key, val);

}

#endif

ValueFoundInFartherNode

We can change the setup of the IDs and verify that the we find the value in a farther node.

Code Listing 58: ValueStoredInFartherNodeTest

[TestMethod]

public void ValueStoredInFartherNodeTest()

{

  VirtualProtocol vp1 = new VirtualProtocol();

  VirtualProtocol vp2 = new VirtualProtocol();

  VirtualStorage store1 = new VirtualStorage();

  VirtualStorage store2 = new VirtualStorage();

  // Ensures that all nodes are closer, because ID.Max ^ n < ID.Max when n > 0.

  Dht dht = new Dht(ID.Zero, vp1, new Router(), store1, store1,
    new VirtualStorage());

  vp1.Node = dht.Router.Node;

  ID contactID = ID.Max;      // a farther contact.

  Contact otherContact = new Contact(vp2, contactID);

  Node otherNode = new Node(otherContact, store2);

  vp2.Node = otherNode;

  // Add this other contact to our peer list.

  dht.Router.Node.BucketList.AddContact(otherContact);

  // We want an integer distance, not an XOR distance.

  ID key = ID.One;

  // Set the value in the other node, to be discovered by the lookup process.

  string val = "Test";

  otherNode.SimpleStore(key, val);

  Assert.IsFalse(store1.Contains(key),
    "Expected our peer to NOT have cached the key-value.");

  Assert.IsTrue(store2.Contains(key),
    "Expected other node to HAVE cached the key-value.");

  // Try and find the value, given our Dht knows about the other contact.

  string retval = dht.FindValue(key).val;

  Assert.IsTrue(retval == val, "Expected to get back what we stored");

}

ValueStoredGetsPropagated

Here we test that when we store a value to our peer, it also gets propagated to another peer that our peer knows about.

Code Listing 59: ValueStoredGetsPropagatedTest

[TestMethod]

public void ValueStoredGetsPropagatedTest()

{

  VirtualProtocol vp1 = new VirtualProtocol();

  VirtualProtocol vp2 = new VirtualProtocol();

  VirtualStorage store1 = new VirtualStorage();

  VirtualStorage store2 = new VirtualStorage();

  // Ensures that all nodes are closer, because ID.Max ^ n < ID.Max when n > 0.

  Dht dht = new Dht(ID.Max, vp1, new Router(), store1, store1, new VirtualStorage());

  vp1.Node = dht.Router.Node;

  ID contactID = ID.Mid;      // a closer contact.

  Contact otherContact = new Contact(vp2, contactID);

  Node otherNode = new Node(otherContact, store2);

  vp2.Node = otherNode;

  // Add this other contact to our peer list.

  dht.Router.Node.BucketList.AddContact(otherContact);

  // We want an integer distance, not an XOR distance.

  ID key = ID.Zero;

  string val = "Test";

  Assert.IsFalse(store1.Contains(key), "Obviously we don't have the key-value yet.");

  Assert.IsFalse(store2.Contains(key),
    "And equally obvious, the other peer doesn't have the key-value yet either.");

  dht.Store(key, val);

  Assert.IsTrue(store1.Contains(key),
    "Expected our peer to have stored the key-value.");

  Assert.IsTrue(store2.Contains(key),
    "Expected the other peer to have stored the key-value.");

}

GetValuePropagatesToCloserNode

This test verifies that, given three nodes (the first of which is us), where node 2 has the value, a get value also propagates to node 3 because a lookup was performed.

Code Listing 60: GetValuePropagatesToCloserNodeTest

[TestMethod]

public void GetValuePropagatesToCloserNodeTest()

{

  VirtualProtocol vp1 = new VirtualProtocol();

  VirtualProtocol vp2 = new VirtualProtocol();

  VirtualProtocol vp3 = new VirtualProtocol();

  VirtualStorage store1 = new VirtualStorage();

  VirtualStorage store2 = new VirtualStorage();

  VirtualStorage store3 = new VirtualStorage();

  VirtualStorage cache3 = new VirtualStorage();

  // Ensures that all nodes are closer, because ID.Max ^ n < ID.Max when n > 0.

  Dht dht = new Dht(ID.Max, vp1, new Router(), store1, store1, new VirtualStorage());

  vp1.Node = dht.Router.Node;

  // Setup node 2:

  ID contactID2 = ID.Mid;      // a closer contact.

  Contact otherContact2 = new Contact(vp2, contactID2);

  Node otherNode2 = new Node(otherContact2, store2);

  vp2.Node = otherNode2;

  // Add the second contact to our peer list.

  dht.Router.Node.BucketList.AddContact(otherContact2);

  // Node 2 has the value.

  // We want an integer distance, not an XOR distance.

  ID key = ID.Zero;

  string val = "Test";

  otherNode2.Storage.Set(key, val);

  // Setup node 3:

  ID contactID3 = ID.Zero.SetBit(158);      // 01000.... -- a farther contact.

  Contact otherContact3 = new Contact(vp3, contactID3);

  Node otherNode3 = new Node(otherContact3, store3, cache3);

  vp3.Node = otherNode3;

  // Add the third contact to our peer list.

  dht.Router.Node.BucketList.AddContact(otherContact3);

  Assert.IsFalse(store1.Contains(key), "Obviously we don't have the key-value yet.");

  Assert.IsFalse(store3.Contains(key),
    "And equally obvious, the third peer doesn't have the key-value yet either.");

  var ret = dht.FindValue(key);

  Assert.IsTrue(ret.found, "Expected value to be found.");

  Assert.IsFalse(store3.Contains(key), "Key should not be in the republish store.");

  Assert.IsTrue(cache3.Contains(key), "Key should be in the cache store.");

  Assert.IsTrue(cache3.GetExpirationTimeSec(key.Value) ==
    Constants.EXPIRATION_TIME_SECONDS / 2, "Expected 12 hour expiration.");

}

Scroll To Top
Disclaimer
DISCLAIMER: Web reader is currently in beta. Please report any issues through our support system. PDF and Kindle format files are also available for download.

Previous

Next

A
A
A

of



You are one step away from downloading ebooks from the Succinctly® series premier collection!
A confirmation has been sent to your email address. Please check and confirm your email subscription to complete the download.