-
Notifications
You must be signed in to change notification settings - Fork 64
Generating a .see response efficiently
All “visible” (that have sent themselves back in a .see) lines are stored in kbuckets, an array of 160 buckets (one per bit, 160 bit hash), each bucket itself being an array containing the lines in that bucket.
A line is assigned to a bucket based on it’s “distance” from us (binary xor of it’s +end and our +end hashes), 50% on average would be the furthest away and be in the first bucket (bucket 0 or bucket 159, should we suggest an ordering to help make sense across implementations?) as they differ on the first bit. Closer ones would be in buckets closer to us. The goal of seeding is to fill as many of the buckets as close to us as possible, so that we can more efficiently respond to +end requests in our vicinity with other switches closer to it.
When a new +end comes in and needs to be responded to with a list of other switches closer to it than us, we first find it’s distance from us and take that bucket of switches, as they would all be the same distance from it (all share the same xor bytes up to that bucket). If we don’t have enough in that bucket, we gather more from buckets closer to us (which may or may not be closer to it but are all closer than buckets further from us). If we still don’t have enough, we start stepping up buckets further from us, until we have at least a few switches, which we then sort based on their distance from the incoming +end, and generate a .see response with those few closest to it.
Maybe:
IPP = “IP:PORT”
A data model inside a switch: every other external “visible” (see other docs) IPP that a local switch knows about would track a “see cache” per external switch, that lists the closest few other visible IPPs to that switch. One function can be used that given a +end hash and any IPP, would take that local see cache, sort it, and either return it or tail recurse down it to find the closest.
Pseudocode:
function getSee(+end, IPP) { # get the cached see Array seecache = IPP seecache # if it's too small, go find some more! (bootstraps a new switch too, nifty) Push seecache, endseeswitch(IPPs +end, SEEDIPP)) if(Length seecache < 5 && IPP != SEEDIPP); # sort the cached see Array sortedipps = Sort seecache by distance from +end # if this switch is the closest, return these results if(sortedipps[0] == sha1(IPP)) { # if this +end == this line then replace the see cache with this result # and every one in the result walk and insert this one into their see cache to "seed" if(sortedipps[0] == +end) { IPP seecache = sortedipps for each sipp in sortedipps { insert IPP into sipp seecache } } return sortedipps; } # whomever is closer, tail recurse them return getSee(+end,sortedipps[0]); }
Also, any incoming +end can use this function, and then cache that mapping (ends are very often repeated).