5 ms·

Still not fixing the core issue - intelligent routing. I've played around with various routing methods before, and intelligent routing does seem to be incredib

by RyanZAG 14y ago

Still not fixing the core issue - intelligent routing. I've played around with various routing methods before, and intelligent routing does seem to be incredibly difficult at scale. I don't think anybody gets it right? Any examples of intelligent routing at scale that works properly? If not, might be a good place to start an OSS project into and benefit everyone. Intelligent routing should be far from impossible, all you need is very basic communication between servers and routers, possibly using some form of minimal broadcasting or multicast? A simple solution could be having each server send 'dont send me more requests' and 'im ready for more requests'

wmf 14y ago
What's your definition of "at scale"? HAProxy can handle over 100K requests/s and 10 Gbps. Is there any Heroku app larger than that?
- RyanZAG 14y ago
  You're correct on HAProxy - I didn't realize HAProxy had a 'maxconn' flag. I'm guessing the issue for Heroku is that that don't have 1 router/haproxy per app, and that 1 server can handle many dynamos/apps. Heroku likely has their own custom routing software that communicates with their databases to route incoming requests to the correct dynamos, etc. EDIT: Key problem with the 'at scale' part is that Heroku does not have a single router, they have many many routers. I don't work there, so I have no idea if/why a single HAProxy couldn't handle it all, but obviously it can't or they'd just do that and save money! Using a HAProxy with 'maxconn' flag works only for that single router instance. If a request arrives at a different router, it has no knowledge that server is wants to route the request to is already processing a request. That knowledge is internal state in a different router. The key here would be to communicate this state between all routers. As I thought in the OP, the correct way to handle this at scale is some form of multicast - across a 1gbps network, broadcasted status updates should account for a tiny percent of traffic/processing, yet allow intelligent routing that would decrease latency immensely. So I guess the original question still stands: is there any router project that communicates state between multiple load balancers/routers to allow intelligent routing at scale ? EDIT2: Here we go - looks like research is being done in this area. Maybe Heroku should read this paper: http://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1051&context=csearticles http://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=10...
  - wmf 14y ago
    Why is a single app mapped to multiple routers? Why not just map it to one?
    - mixedbit 14y ago
      Then you would need another level of HTTP routers that would route to this application specific router. Also the router becomes a single point of failure and possibly a bottleneck: if a backend returns large responses, all of them go through this single router.
      - wmf 14y ago
        Or you could use DNS to map each app to its assigned router. (Of course, when I say "router" I mean at minimum a redundant active/passive pair.)
    - cpleppert 14y ago
      Because you don't want to scale up just by adding more shards that consist of a single router. The distribution of the traffic to each shard isn't random, some applications are more popular than others. Additionally, you don't have any redundancy if a router goes down.
    - jfim 14y ago
      What happens if your single router catches on fire?
- aphyr 14y ago
  "Is there any Heroku app larger than that?" Yes. Consider that Heroku publishes DNS records for all their customers to the same set of nodes; those nodes must be responsible for routing all Heroku traffic. Sharding customers onto individual Haproxy LBs would require either updating an upstream load balancer (which just pushes the problem around) or updating DNS (which comes with long convergence times).
ericmj 14y ago
What is wrong with the random routing they are doing now? Random routing works if your dynos can handle concurrent requests.
- CyrusL 14y ago
  It requires a much larger number of dynos to achieve similar performance as the same setup with intelligent routing.
  - deleted 14y ago
    [deleted]
  - andrewcooke 14y ago
    why? do you have any proof/calculations? what you're stating seems unintuitive to me. would't you expect intelligent routing and random routing to converge in the limit of many concurrent processes?
    - RyanZAG 14y ago
      The issue is that while the average time is going to converge - users aren't interested in the average time! Consider the following scenario: - Two types of requests, A and B - Request A takes 200ms to process - Request B takes 10 seconds to process - Each dynamo can take 4 concurrent requests If you are receiving 1000s of requests per minute, it is very likely that you will eventually allocate more than 4 request B to a single dynamo. One this has happened, that dynamo is now locked for 10 seconds. All of the request As that we route to that dynamo will take over 10 seconds to return. If request A is a credit card transaction, and request B is just some data lookup with a loading UI spinner, then every time this occurs our poor app has lost money as the user has navigated away from our app before the transaction (request A) can complete! Ouch! Intelligent routing solves this by ensuring that request A will only go to a dynamo that is open, thereby ensuring no user will have to wait 10 seconds for their quick credit card transaction. The take away here is that the important measure is the slowest user facing request, not the average request time across all requests.
aristus 14y ago
I have working knowledge of a couple of large routing systems (Yahoo, Facebook) and built a few smaller ones. In general, state is the enemy of scale. You want large systems to be simpler and less stateful, not more stateful and "intelligent". One good notion is to embed server statistics into the response, like in an HTTP header. That way the LB can be aware of queue size, queue wait, utilization, etc. But that only works if the knowledge of server health is global to all load balancers, or if some LBs only talk to some servers. If your requests are more or less the same "size", eg they take roughly the same amount of CPU / wall / etc, all of this gets vastly easier.
- spaghetti 14y ago
  I've never designed large-scale systems however I'm still fascinated. I wonder if LBs could learn over time which requests will probably take a while and which have large probability of being fast? Then the requests could be uniformly distributed amongst the servers. A system like this could have all sorts of knobs to turn. Requests could be partitioned into two groups: "probably fast" and "probably slow". Or three, four, n groups etc. Then the way in which the LBs distribute the requests could be tweaked. For example a ratio of 1/5 slow/fast requests per server. This does require some feedback from the servers to the LBs. However it doesn't have to be fast. The servers could push some (request, time) pairs to some aggregating system at their leisure. Then the response time prediction algorithms used by the LBs are updated at some point. Probably doesn't have to be immediate.
  - aristus 14y ago
    You have good instincts here, but 1) In very large systems there are many many load balancers 2) Server "spikes" (eg swapping) can happen very suddenly, so distributing health info is a hard problem 3) Determining a priori which requests are heavy and light is also hard. Think about "SEO urls": they blow up the cardinality. 4) Even assuming perfect global knowledge, you are proposing to solve a variant of the knapsack problem.
- aphyr 14y ago
  For single-threaded servers, request latency dominates--it's hard to get useful state information out of a dyno, because as soon as it's returned a response, its state has changed. You can add a dedicated stats endpoint to each server, but that requires cooperation from the customer's application. There are... alternate approaches, however.

by RyanZAG 14y ago

wmf 14y ago

What's your definition of "at scale"? HAProxy can handle over 100K requests/s and 10 Gbps. Is there any Heroku app larger than that?

RyanZAG 14y ago
You're correct on HAProxy - I didn't realize HAProxy had a 'maxconn' flag. I'm guessing the issue for Heroku is that that don't have 1 router/haproxy per app, and that 1 server can handle many dynamos/apps. Heroku likely has their own custom routing software that communicates with their databases to route incoming requests to the correct dynamos, etc. EDIT: Key problem with the 'at scale' part is that Heroku does not have a single router, they have many many routers. I don't work there, so I have no idea if/why a single HAProxy couldn't handle it all, but obviously it can't or they'd just do that and save money! Using a HAProxy with 'maxconn' flag works only for that single router instance. If a request arrives at a different router, it has no knowledge that server is wants to route the request to is already processing a request. That knowledge is internal state in a different router. The key here would be to communicate this state between all routers. As I thought in the OP, the correct way to handle this at scale is some form of multicast - across a 1gbps network, broadcasted status updates should account for a tiny percent of traffic/processing, yet allow intelligent routing that would decrease latency immensely. So I guess the original question still stands: is there any router project that communicates state between multiple load balancers/routers to allow intelligent routing at scale ? EDIT2: Here we go - looks like research is being done in this area. Maybe Heroku should read this paper: http://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1051&context=csearticles http://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=10...
- wmf 14y ago
  Why is a single app mapped to multiple routers? Why not just map it to one?
  - mixedbit 14y ago
    Then you would need another level of HTTP routers that would route to this application specific router. Also the router becomes a single point of failure and possibly a bottleneck: if a backend returns large responses, all of them go through this single router.
    - wmf 14y ago
      Or you could use DNS to map each app to its assigned router. (Of course, when I say "router" I mean at minimum a redundant active/passive pair.)
  - cpleppert 14y ago
    Because you don't want to scale up just by adding more shards that consist of a single router. The distribution of the traffic to each shard isn't random, some applications are more popular than others. Additionally, you don't have any redundancy if a router goes down.
  - jfim 14y ago
    What happens if your single router catches on fire?
aphyr 14y ago
"Is there any Heroku app larger than that?" Yes. Consider that Heroku publishes DNS records for all their customers to the same set of nodes; those nodes must be responsible for routing all Heroku traffic. Sharding customers onto individual Haproxy LBs would require either updating an upstream load balancer (which just pushes the problem around) or updating DNS (which comes with long convergence times).

ericmj 14y ago

What is wrong with the random routing they are doing now? Random routing works if your dynos can handle concurrent requests.

CyrusL 14y ago
It requires a much larger number of dynos to achieve similar performance as the same setup with intelligent routing.
- deleted 14y ago
  [deleted]
- andrewcooke 14y ago
  why? do you have any proof/calculations? what you're stating seems unintuitive to me. would't you expect intelligent routing and random routing to converge in the limit of many concurrent processes?
  - RyanZAG 14y ago
    The issue is that while the average time is going to converge - users aren't interested in the average time! Consider the following scenario: - Two types of requests, A and B - Request A takes 200ms to process - Request B takes 10 seconds to process - Each dynamo can take 4 concurrent requests If you are receiving 1000s of requests per minute, it is very likely that you will eventually allocate more than 4 request B to a single dynamo. One this has happened, that dynamo is now locked for 10 seconds. All of the request As that we route to that dynamo will take over 10 seconds to return. If request A is a credit card transaction, and request B is just some data lookup with a loading UI spinner, then every time this occurs our poor app has lost money as the user has navigated away from our app before the transaction (request A) can complete! Ouch! Intelligent routing solves this by ensuring that request A will only go to a dynamo that is open, thereby ensuring no user will have to wait 10 seconds for their quick credit card transaction. The take away here is that the important measure is the slowest user facing request, not the average request time across all requests.

aristus 14y ago

I have working knowledge of a couple of large routing systems (Yahoo, Facebook) and built a few smaller ones. In general, state is the enemy of scale. You want large systems to be simpler and less stateful, not more stateful and "intelligent". One good notion is to embed server statistics into the response, like in an HTTP header. That way the LB can be aware of queue size, queue wait, utilization, etc. But that only works if the knowledge of server health is global to all load balancers, or if some LBs only talk to some servers. If your requests are more or less the same "size", eg they take roughly the same amount of CPU / wall / etc, all of this gets vastly easier.

spaghetti 14y ago
I've never designed large-scale systems however I'm still fascinated. I wonder if LBs could learn over time which requests will probably take a while and which have large probability of being fast? Then the requests could be uniformly distributed amongst the servers. A system like this could have all sorts of knobs to turn. Requests could be partitioned into two groups: "probably fast" and "probably slow". Or three, four, n groups etc. Then the way in which the LBs distribute the requests could be tweaked. For example a ratio of 1/5 slow/fast requests per server. This does require some feedback from the servers to the LBs. However it doesn't have to be fast. The servers could push some (request, time) pairs to some aggregating system at their leisure. Then the response time prediction algorithms used by the LBs are updated at some point. Probably doesn't have to be immediate.
- aristus 14y ago
  You have good instincts here, but 1) In very large systems there are many many load balancers 2) Server "spikes" (eg swapping) can happen very suddenly, so distributing health info is a hard problem 3) Determining a priori which requests are heavy and light is also hard. Think about "SEO urls": they blow up the cardinality. 4) Even assuming perfect global knowledge, you are proposing to solve a variant of the knapsack problem.
aphyr 14y ago
For single-threaded servers, request latency dominates--it's hard to get useful state information out of a dyno, because as soon as it's returned a response, its state has changed. You can add a dedicated stats endpoint to each server, but that requires cooperation from the customer's application. There are... alternate approaches, however.