6/6/16

A Simple Distributed Hash Table (DHT).



-=- A Spherical Double-Spiral. -=-

Can be used in forming Distributed Objects in 3D,
including Distributed Stitie Space in 3D, or Distributed Hash Table in 3D,

... it has a communication cycle & fairly efficiently uses 3D Space,
... without forcing client object to reach inside, past the outer layer.
a client object can, for example scan,
(using directional/cone multicast wireless communication for example)
for 108 closest data structure objects, with load report,
then can choose either at random or by workload an object to communicate with.

... see also, if You wish: Stitie Grid.

A POV-Ray source code available for: download.
Credits: Andrea Lohmüller + Friedrich A. Lohmüller.



1. Hash Table.

1.1. Description.

'Hash Table' is a dictionary data structure that allows for a quick & usually cheap location of data in the large data-set.


1.2. Hash Function & Capacity.

There's 'hash function' that given identifier returns 'address' describing where in the table data can be found.

Each 'address' has a limited capacity ... if that data item can't be fit in its 'address', it's assigned to next available, looping around.



A hash table with a size of 8 & a capacity of 3.



2. Distributed Hash Table (DHT).

2.1. Description.

It's hash table that is spread across multiple distributed machines connected with the network, for example: with the Internet.

This allows for the larger data-capacity & data replication functionality for safety.

Another use is to synchronize multiple processes using shared memory that a DHT is.


2.2. IP Directories.

Each of machines that form DHT contains a directory - list of all of machines' IP addresses, sorted the same way on each of the machines.

There are mechanisms (more about these later in this article) that synchronize the directories, updating in the case of individual machine(s) failure(s).


2.3. Hash Function.

As with Hash Table, DHT uses a hash function. The same hash function is used in each of the machines.


2.4. Store & Retrieval.

DHT stores data objects, that have identifiers. These identifiers & a hash function allow to find machine where data objects are located or are to be located.

Data objects are replicated among multiple machines - for example on a first machine pointed by the hash function in the directory & on three next machines.

When retrieving or storing data, DHT's client connects to any of these machines & gets a response with proper data object's locations (each of the machines contain this functionality, having synchronized directory & the same hash function), then tries these IP address(-es) for desired data objects. Either with store or retrieve, there's only one succesful request with a directory-machine required, as data is replicated transparently to the user.


2.5. When a machine is down.

Machines occasionally ping it's successors (ip addresses in directory loop back to start, forming a ring instead of a list) to check if these are functioning. When a successor is/are not responding, is added to malfunctioning list & a message is passed to next successor with failing machine(s) list. Using that list, successors update their directories (not deleting, just noting machines that are off) & pass message along the ring. Then data objects are replicated on the successors.

When a DHT's client contacts machine for data object's location, it might retrieve a list with working machines according to directory.

When machine is detected as failing by the client, client informs any of the machines & the machine's status in directories is updated (after proper failing-machine detection procedures are executed on DHT).

Occassionally machines marked down are pinged to check if are available. If available, directories are updated, objects from predecessors are replicated & objects in successors are deleted, as is proper & sane.