Specialization routing
A node should track its own specialization.
This would probably be done using 2 variables: the KEY (peak) of the specialization and the RANGE of specialization. Initially the key will be in the middle of the key space and the range will represent 50% of key space on either side indicating no specialization.
Nodes should announce these variables whenever connecting to another node.
At this point the node should accept all inserts and requests.
As soon as the node notices a peak in its datastore (due to a peak in requests around a certain key) it should adjust its specialisation to center around that area of keyspace.
As the load on the node increases the node should enforce its specialization by reducing the RANGE of its specialization.
Nodes should keep a large routing table including each node’s specialization key and range. The routing table should also keep track of the speed at which previous keys were retrieved from each node so that when more than 1 node with similar or overlapping specialization is available it can try to route to the fastest one. If the highly specialized nodes are very slow/busy it can try some of the less specialised ones encouraging them take up more of the load.
As the load on the node increases it should start to QR requests that are not in its RANGE. The probability of rejection should be based on load and the distance from the specialisation peak key. The QR message should include a list of nodes from its routing table that DO specialize in that key. I.e. the node is saying, I’m busy but these other nodes should be able to help you. The requesting node should then add these nodes to its routing table and try routing there.
If the load continues to increase the node should further narrow its RANGE
For as long as possible the node should avoid QR requests that are in its datastore. I.e. under extreme load it will get to a point where it only serves requests from the local datastore.
This next point may be rather open to abuse, but if a node gets a request for a key, which is in its datastore AND that request comes from a node that has almost the same specialization it should give that request priority above all others. In effect this will be a “sister” node, which looks after the same area of keyspace.
Hopefully popular areas of keyspace will have many such overlapping “sister” nodes and when they get busy they can load balance between them by QR with a list of “sister nodes”. In fact a busy node might be able to point the requester to a “sister” that specializes in keyspace that is slightly to the left or to the right of its own specialization.
If a node is not busy and it has keys in its datastore that do not belong in its RANGE, the node might want to contact a node that does specialise in that range and offer these keys to it. That node can then say, no thanks I already have it, request those keys, or say its busy but it will keep those keys in mind. That node can then keep a list/index of these keys in its datastore so that if a request for that key comes in it can retrieve that key from this node even though this node does not “look after” this keyspace. It can also pick those keys up at a later time when its not busy. The node may try to ensure that at least a few specialised nodes have the key before deleting it from its datastore. Once the datastore is full the keys furthest away from the specialization peak should be pruned first.
There may be other ways to “cluster” sister nodes together so that they maintain an index of what keys are (or are likely to be) in each other’s datastores making it easier to find keys fast. But its 4.30 am :)
Nodes that are on slow links (especially slow upstream) will overload quickly and therefore reduce their RANGE to a minute slither of the keyspace, which they can handle.
If a node appears to be under-utilised it should broaden its range which may cause it to shift its specialization left or right as time goes on and find areas of keyspace that are overloaded.
If a node accepts a request, the first thing it should do is send back a list of nodes that also specialise in that area of keyspace (i.e. its sister nodes are announced whether the request is accepted or QR) this way should the transfer fail for any reason, or if the transfer is very slow, the node can try other nodes and see if others are faster.
The routing table size will need to be very big… in fact it would probably be good to have 2 routing tables.
The first large routing table should have a large and accurate list of nodes that specialise in the keyspace around our own area of keyspace.. ie our sister nodes and those nodes that service keyspace directly to the left and right of ours. This gives us a very accurate picture of all the nodes servicing our “neighbourhood”. We should probably periodically contact these nodes to update their status.
The second, and probably smaller routing table should have a list of nodes that service the rest of the keyspace… preferably equally spaced.. i.e. few nodes that service “a” keys, “b” keys etc.
When a request comes in for a key that is close, but not quite within our range, we can QR the request and give the requesting node a very good list of nodes that can handle its request from the first routing table.
If we need a key from another part of the keyspace we can ask one of the nodes in our second routing table, and if its not close enough to service our request, it will give us a list of nodes in its “neighbourhood” which should give us a choice of nodes that specialize in our desired key. That node may even be able to send us its estimators telling us which nodes it found to be the fastest in its neighbourhood.
This may be stored in a temporary routing table and discarded once we complete the request… we may copy a few entries into our second routing table, but we shouldn’t try to keep an accurate picture of the rest of the keyspace, only our own.
Some of these features should only come into effect once our node has started to specialise.
Inserts should work the same way as requests: nodes should only insert keys into nodes that specialise in that area of keyspace, and if they are all slow/busy they should insert them into unspecialised nodes which should cause those nodes to specialise in that area.
Multiplexing will help a lot and can later be used to better “cluster” sister nodes.
Obviously this still needs a lot of work, the more I think about it the more I come up with and the more problems I see, but I do believe that specialization, distribution and load balancing is the only way it can work.
I hope at least some of this helps.
DigitalE
_______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
