Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Integrate Hashed Timing Wheel (Data Structure) Into bip_select #132

Open
GGist opened this issue Oct 22, 2017 · 0 comments
Open

Integrate Hashed Timing Wheel (Data Structure) Into bip_select #132

GGist opened this issue Oct 22, 2017 · 0 comments

Comments

@GGist
Copy link
Owner

GGist commented Oct 22, 2017

Right now, we have two approaches for timeout semantics available:

  1. When we tell a client to send a message, we also give them a duration for which to notify us if we havent gotten a response to the message.

Advantages:

  • Simple on our side, client handles timeout logic
  • Very performant, peer can handle all of these timeouts on a single timer (we should be able to be performant with the other approach as well, depending on how we do it)

Disadvantages:

  • Client either has to store the full message, so they can pass it back to us when the timeout is up so we can associate it with something on our end (now they have to store a cloned copy of the message, potentially expensive, but they may not know that) OR we have to give them a cheap id, so we store the association on our end
  • They may not have visibility into the magnitude of timeouts we expect their timer to support, forcing them to pay attention to documentation for each module (if it exists...)
  • If we want just some message to say wake me up at this time, so not a timeout, just something we do every x milliseconds, that would be a different message and would be hard to configure (doesnt map 1:1 with stimulus response, so its hard to do with streams and sinks)
  1. We tell a client to periodically send a Tick message to us, at whatever interval they decide. The more fine grained, the better, but generally, anything less than 100 ms should be fine, which gives them some flexibility, and is also easier reason about/harder to screw up.

Advantages:

  • Peer controls granularity of timeouts, while we control magnitude of timeouts, so we get the best of both worlds
  • We know how expensive our messages are, so we can choose to store cheap data representing the actual messages
  • If a peer disconnects, the client doesnt have to implement logic for removing their timeouts, we can handle that on our side and avoid the influx of unnecessary timeout messages this could generate if done incorrectly by the client
  • If we want to do something every x milliseconds, we can handle that out of band, as the client will be periodically waking us up, regardless if we have any traditional timeouts waiting; this gives enormous flexibility in how we emit events as we dont have to constantly tell the client to wake us up in x milliseconds, we just do that ourselves (there is some concern to be had, if for example, the client isnt consuming these "generated" events fast enough, though for most usages, I would imagine we may not want to queue these, as they could lead to bursts of unnecessary traffic, eg, SendDhtAnnounce)

Disadvantages:

  • If our timer wheel tick interval is different than the clients tick interval, we may have to compensate (which isnt TOO difficult, as long as their tick interval is consistent), it also wouldnt be too hard to make this configurable for the client
  • If we broadcast the Tick messages to too many modules, there could be too much overhead if we arent really tracking any timeouts; though I think we wont have more than 8 modules realistically (1 revelation, 1 selection, 1 queueing, ~5 discovery), and this can be controlled by the client; and I think this would only be an issue if we had hundreds of thousands of modules in use

We could use the timer wheel data structure in tokio_timer, but im not sure atm how tied it is to the runtime (the thread & channels it spins up), as we would ideally just want the data structure, and not the resources around it that drives it forward.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant