The Kademlia Protocol Succinctly®
CHAPTER 6
Value Lookup
From the spec: “FIND_VALUE behaves like FIND_NODE - returning (IP address, UDP port, Node ID) triples - with one exception. If the RPC recipient has received a STORE RPC for the key, it just returns the stored value.”
That seems clear enough, but we must consider this part of the spec as well:
“To find a (key,value) pair, a node starts by performing a lookup to find the k nodes with IDs closest to the key. However, value lookups use FIND_VALUE rather than FIND_NODE RPCS. Moreover, the procedure halts immediately when any node returns the value. For caching purposes, once a lookup succeeds, the requesting node stores the (key,value) pair at the closest node it observed to the key that did not return the value.”
However, the spec says this: “Most operations are implemented in terms of the above lookup procedure.” When we’re performing a lookup, the initiator will be using the lookup call for both finding nodes and finding values. If it’s finding values, it needs to stop if/when the value is found.
This statement from the spec can be ambiguous: “For caching purposes, once a lookup succeeds, the requesting node stores the (key,value) pair at the closest node it observed to the key that did not return the value.” What does “requesting node” mean? Is it the node performing the lookup, or the node that made the GetValue request? It would seem to be the former, because “it observed to the key that did not return the value” would otherwise not make any sense.
Going back to the code:
Func<ID, Contact, (List<Contact> contacts, Contact foundBy, string val)> rpcCall
We can see now the reason for passing in the RPC, as we want to use the exact same lookup algorithm for FindNode as we do for FindValue.
Discussing value lookup tests doesn’t make sense outside of the context of the Dht wrapper, so the unit tests for the value lookup will be done in the Dht testing.
Implementation
First, we need to implement a simple virtual (in memory) storage mechanism. We don’t show the implementation of the full interface, as that isn’t required yet.
Code Listing 51: Basic Virtual Storage
public class VirtualStorage : IStorage { protected ConcurrentDictionary<BigInteger, StoreValue> store; public VirtualStorage() { store = new ConcurrentDictionary<BigInteger, StoreValue>(); } { return store.ContainsKey(key.Value); } public string Get(ID key) { return store[key.Value].Value; } public string Get(BigInteger key) { return store[key].Value; } } |
We can also now implement Store and FindValue in the Node class.
Code Listing 52: Node Store
public void Store( { Validate.IsFalse<SendingQueryToSelfException>(sender.ID == ourContact.ID, bucketList.AddContact(sender); if (isCached) { cacheStorage.Set(key, val, expirationTimeSec); } else { SendKeyValuesIfNewContact(sender); storage.Set(key, val, Constants.EXPIRATION_TIME_SECONDS); } } |
Code Listing 53: Node FindValue
public (List<Contact> contacts, string val) FindValue(Contact sender, ID key) { Validate.IsFalse<SendingQueryToSelfException>(sender.ID == ourContact.ID, SendKeyValuesIfNewContact(sender); bucketList.AddContact(sender); if (storage.Contains(key)) { return (null, storage.Get(key)); } else if (CacheStorage.Contains(key)) { return (null, CacheStorage.Get(key)); } else { // Exclude sender. return (bucketList.GetCloseContacts(key, sender.ID), null); } } |
- 1800+ high-performance UI components.
- Includes popular controls such as Grid, Chart, Scheduler, and more.
- 24x5 unlimited support by developers.