9 ms·

It seems to me that Heroku is still failing to understand (or at least cop to) the fact that the switch from intelligent to randomized routing was a loss of a m

by ebbv 14y ago

It seems to me that Heroku is still failing to understand (or at least cop to) the fact that the switch from intelligent to randomized routing was a loss of a major reason people chose Heroku in the first place. A lot of Heroku's apparent value came from the intelligent routing feature. Everybody knew that it was harder to implement than random routing, that's why they were willing to pay Heroku for it. Nobody's arguing random routing isn't easier and more stable; of course it is. The problem is that by switching over to it, Heroku gave up a major selling point of their platform. Are they really blind enough not to know this? I have a hard time believing that. It seems to me the real way to make people happy is to discount the "base" products which come with random routing and make intelligent routing available as a premium feature. Of course, people who thought they were getting intelligent routing should be credited.

tptacek 14y ago
Is anybody operating at Heroku's scale offering centralized request routing queues? At what price?
- ebbv 14y ago
  Not that I know of but that's why I'm saying it would be a premium product. Likely pricing would have to scale with the number of dynos running behind the router. But that's the service people thought they were getting and what they wanted. If Heroku prices out the intelligent routing and says; "Ok you can have intelligent routing with your current backend stack, but it's going to cost you $25/mo for evert 10 dynos, or you can switch your stack and use randomized routing for free." Then they are empowering their customers to make the choice rather than dictating to them what they should do.
  - chc 14y ago
    $25 a month? Did you forget a few zeroes?
    - ebbv 14y ago
      It was just a placeholder price. :)
  - tptacek 14y ago
    If it's truly impossible to get centralized request routing queues at Heroku's scale in any other product offering, that is evidence that a demand that Heroku provide it might be unreasonable. Aside from that, I am extremely sympathetic to Heroku's engineering point here --- it's obviously hard for HN to extract the engineering from the drama in this case! Randomized dispatch seems like an eminently sound engineering solution to the request routing problem, and the problems actually implementing it in production seem traceable almost entirely to††† the ways Rails managed to set back scalable web request dispatch by roughly a decade††††. ††† IT IS ALL LOVE WITH ME AND THIS POINT COMING UP HERE... †††† ...it was probably worth it!
    - jules 14y ago
      Random routing vs fully centralized request routing is a false dichtonomy. Suppose you have 100 nodes, and you have a router that routes randomly to one of those 100 nodes. This works very poorly. Now suppose you have 100 nodes, and you have a router that routes intelligently too one of those 100 nodes, e.g. to the one with the smallest request queue. From a theoretical perspective this works really well but it may be impossible to implement efficiently. The solution is to combine the two approaches. You split the 100 nodes into 10 groups of 10, you route randomly to one of the groups, and then within a group you route intelligently. This works really well. The probability of one of the request queues filling up is astronomically small, because for a request queue to fill up, all 10 request queues in a group have to fill up simultaneously (and as we know from math, the chance that an event with probability p occurs at n places simultaneously is exponentially small in n). Even if you route randomly to 50 groups of 2, that works a lot better than routing randomly to 100 groups of 1 (though obviously not as well as 10 groups of 10). There is a paper about this: http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20... This is essentially what they are suggesting: run multiple concurrent processes on one dyno. Then the requests are routed randomly to a dyno, but within a dyno the requests are routed intelligently to the concurrent processes running on that dyno. There are two problems with this: (1) dynos have ridiculously low memory so you may not be able to run many (if any) concurrent processes on a single dyno (2) if you have contention for a shared resource on a dyno (e.g. the hard disk) you're back to the old situation. They are partially addressing point (1) by providing dynos with 2x the memory of a normal dyno, which given a Rails app's memory requirements is still very low (you probably have to look hard to find a dedicated server that doesn't have at least 20x as much memory). They could be providing intelligent routing within groups of dynos (say groups of 10) and random routing to each group, but apparently they have decided that this is not worth the effort. Another thing is that apparently their routing is centralized for all their customers. Rapgenius did have what, 150 requests per second? Surely that can even be handled by a single intelligent router if they had a dedicated router per customer that's above a certain size (of course you still have to go to the groups of dynos model once a single customer grows beyond the size that a single intelligent router can handle).
- wmf 14y ago
  Amazon ELB? It does cost significantly more than Heroku AFAIK.
  - adamwiggins 14y ago
    My understanding is that ELBs are HAProxy, and they may be set to use the leastconn algorithm (a global request queue that is friendly to concurrent backends). However, once you get any amount of traffic they start to scale out the nodes in the ELB, which produces essentially the same results as the degradation of the Bamboo router that we've documented. The difference, of course, is that ELBs are single-tenant. So a big app might only end up with half a dozen nodes, instead of the much larger number in Heroku's router fleet. Offering some kind of single-tenant router is one possibility we've considered. Partitioning the router fleet, homing... all are ideas we've experimented with and continue to explore. If one of these produces conclusive evidence that it provides a better product for our customers and in keeping with the Heroku approach to product design, obviously we'll do it.
    - twic 14y ago
      I hope you'll be able to share your findings with us, even if they're negative. As someone who has no stake in Heroku, i have the luxury of finding this problem simply interesting! My hypothesis is that tenant-specific intelligent load balancers would be plausible; i would guess that you would never need more than a handful of HAProxy or nginx-type balancers to front even a large application. Your main challenge would then be routing requests to the right load balancer cluster. If you had your own hardware, LVS could handle that (i believe that Wikipedia in 2010 ran all page text requests through a single LVS in each datacentre), but i'm not sure what you do on EC2. However, "hypothesis" is just a fancy way of saying "guess", which is why your findings from actual experiments would be so interesting.
  - bgentry 14y ago
    ELBs have a least-conn per node routing behavior. If your ELB is present in more than 1 AZ, then you have more than one node. If you have any non-trivial amount of scale, then you probably have well more than 1 node.
deleted 14y ago
[deleted]
- dangrossman 14y ago
  http://rapgenius.com/James-somers-herokus-ugly-secret-lyrics http://rapgenius.com/James-somers-herokus-ugly-secret-lyrics There are screenshots of the website where it said that in multiple places.
- habosa 14y ago
  Unless I'm entirely misunderstanding the situation, this was definitely the premise of the "intelligent routing mesh" that Heroku used for so long on the Bamboo stack.
adamwiggins 14y ago
I hear you. Heroku's value proposition is that we abstract away infrastructure tasks and let you focus on your app. Keeping you from needing to deal with load balancers is one part of that. If you're worried about how routing works then you're in some way dealing with load balancing. However, if someone chose us purely because of a routing algorithm, we probably weren't a great fit for them to begin with. We're not selling algorithms, we're selling abstraction, convenience, elasticity, and productivity. I do see that part of the reason this topic has been very emotional (for us inside Heroku as well as our customers and the community) is that the Heroku router has historically been seen as a sort of magic black box. This matter required peeking inside that black box, which I think has created a sense of some of that magic being dispelled.
- cynicalkane 14y ago
  You sound like a politician talking to someone of the opposite party, in that you say "I hear you", but then completely fail to address anyone's concerns. Selling a "magic black box" that guarantees certain properties, changes them, then lies about having changed them presents a liability for users who want to do serious work. A major selling point of Heroku is that scaling dynos wouldn't be a risk. This guarantee is now gone and it's not coming back soon even if routing behavior is reverted, because users prefer good communication and trust with their providers. The responses of Heroku are blithe non-acknowledgement acknowledgements of this problem.
  - adamwiggins 14y ago
    Harsh. I'm going to ignore the more inflammatory parts of this (feel free to restate if you want me to engage in discussion), but one bit did grab my attention: "A major selling point of Heroku is that scaling wouldn't be a risk" This is interesting, especially the word "risk." Can you expand on this?
    - jfabre 14y ago
      Very small customer here. I don't know much about the abstraction you provide us and I don't want to know as long as things go well. To my point of view, the routing is "random" thus kind of unpredictable. If scaling becomes more of an issue with my business, the last thing I want is to have random scaling issues that I can not do anything about because the load balancer is queuing requests randomly to my dynos. I want my business to be predictable and if I'm not able to have it I'm going to pack my stuff and move somewhere else. For now, I'm happy with you except for your damn customer service. They take way too long to answer our questions! Cheers! :)
rhizome 14y ago
I'm sure at least one person's job depends on this working out in the direction they've been trying to go, cf. Blaine Cook (who I think got a raw deal).
aphyr 14y ago
"the switch from intelligent to randomized routing" As I understand it, Heroku (on the Bamboo stack) didn't up and decide "Hey, we're gonna switch from intelligent to random routing." The routers are still (individually) intelligent. It's just that there are more of them now, and they were never designed to distribute their internal queue state across the cluster. The system as a whole behaves more and more like a random router as the number of intelligent bamboo routing nodes increases.
- adamwiggins 14y ago
  True, although it's more confusing than this. We didn't make an explicit decision for Bamboo, and thus the big problem — docs fell out of date, at a minimum. For Cedar, we did make an explicit decision. People on the leading edge of web development were running concurrent backends and long-running requests. Our experimental support for Node.js in 2010 was a big driver here, but also people who wanted to use concurrency in Ruby, like Ilya Grigorick's Goliath and Rails becoming threadsafe. These folks complained that the single-request-per-backend algorithm was actually in their way. This plus horizontal scaling / reliability demands caused us to make an explicit product decision for Cedar.
  - obilgic 14y ago
    > true that makes sense, i was wondering how intelligent routing was implemented in the first place.
    - adamwiggins 14y ago
      Oh, got it. How's this: In the early days, Heroku only had a single routing node that sat out front. So it wasn't a distributed systems problem at that point. You could argue that Heroku circa 2009 was more of a prototype or a toy than a scalable piece of infrastructure. You couldn't run background workers, or large databases. We weren't even charging money yet. Implementing a single global queue in a single node is trivial. In fact, this is what Unicorn (and other concurrent backends) do: put a queue within a single node, in this case a dyno. That's how we implemented it in the Heroku router (written in Erlang). Later on, we scaled out to a few nodes, which meant a few queues. This was close enough to a single queue that it didn't matter much in terms of customer impact. In late 2010 and early 2011 our growth started to really take off, and that's when we scaled out our router nodes to far more than a handful. And that's when the global queue effectively ceased to exist, even though we hadn't changed a line of code in the router. The problem with this, of course, is that we didn't give it much attention because we had just launched a new product which made the explicit choice to leave out global queueing. It's this failure to continue full stewardship of our existing product that's the mistake that really hurt customers. So to answer your question, there was never some crazy-awesome implementation of a distributed global queue that we got rid of. It was a single node's queue, a page of code in Erlang which is not too different from the code that you'll find in Unicorn, Puma, GUnicorn, Jetty, etc.
jcampbell1 14y ago
Random routing will work fine so long as the operating system has the ability to intelligently schedule the work. The problem is that the dynos were setup to handle request sequentially. Unicorn will help mitigate the problem, but the best solution is to not try and serve webpages from hardware that is about as powerful as an old mobile phone. The 2x dynos are a step in the right direction, but I have no idea why they don't offer a real app server like a 16x dyno.
- adamwiggins 14y ago
  It's probably easy to guess that once we have 2X dynos, 4X dynos (and up) may be on the way. We'll drive this according to demand, so if you need/want dynos of a particular size, drop us a line.

by ebbv 14y ago

tptacek 14y ago

Is anybody operating at Heroku's scale offering centralized request routing queues? At what price?

ebbv 14y ago
Not that I know of but that's why I'm saying it would be a premium product. Likely pricing would have to scale with the number of dynos running behind the router. But that's the service people thought they were getting and what they wanted. If Heroku prices out the intelligent routing and says; "Ok you can have intelligent routing with your current backend stack, but it's going to cost you $25/mo for evert 10 dynos, or you can switch your stack and use randomized routing for free." Then they are empowering their customers to make the choice rather than dictating to them what they should do.
- chc 14y ago
  $25 a month? Did you forget a few zeroes?
  - ebbv 14y ago
    It was just a placeholder price. :)
- tptacek 14y ago
  If it's truly impossible to get centralized request routing queues at Heroku's scale in any other product offering, that is evidence that a demand that Heroku provide it might be unreasonable. Aside from that, I am extremely sympathetic to Heroku's engineering point here --- it's obviously hard for HN to extract the engineering from the drama in this case! Randomized dispatch seems like an eminently sound engineering solution to the request routing problem, and the problems actually implementing it in production seem traceable almost entirely to††† the ways Rails managed to set back scalable web request dispatch by roughly a decade††††. ††† IT IS ALL LOVE WITH ME AND THIS POINT COMING UP HERE... †††† ...it was probably worth it!
  - jules 14y ago
    Random routing vs fully centralized request routing is a false dichtonomy. Suppose you have 100 nodes, and you have a router that routes randomly to one of those 100 nodes. This works very poorly. Now suppose you have 100 nodes, and you have a router that routes intelligently too one of those 100 nodes, e.g. to the one with the smallest request queue. From a theoretical perspective this works really well but it may be impossible to implement efficiently. The solution is to combine the two approaches. You split the 100 nodes into 10 groups of 10, you route randomly to one of the groups, and then within a group you route intelligently. This works really well. The probability of one of the request queues filling up is astronomically small, because for a request queue to fill up, all 10 request queues in a group have to fill up simultaneously (and as we know from math, the chance that an event with probability p occurs at n places simultaneously is exponentially small in n). Even if you route randomly to 50 groups of 2, that works a lot better than routing randomly to 100 groups of 1 (though obviously not as well as 10 groups of 10). There is a paper about this: http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf http://www.eecs.harvard.edu/~michaelm/postscripts/handbook20... This is essentially what they are suggesting: run multiple concurrent processes on one dyno. Then the requests are routed randomly to a dyno, but within a dyno the requests are routed intelligently to the concurrent processes running on that dyno. There are two problems with this: (1) dynos have ridiculously low memory so you may not be able to run many (if any) concurrent processes on a single dyno (2) if you have contention for a shared resource on a dyno (e.g. the hard disk) you're back to the old situation. They are partially addressing point (1) by providing dynos with 2x the memory of a normal dyno, which given a Rails app's memory requirements is still very low (you probably have to look hard to find a dedicated server that doesn't have at least 20x as much memory). They could be providing intelligent routing within groups of dynos (say groups of 10) and random routing to each group, but apparently they have decided that this is not worth the effort. Another thing is that apparently their routing is centralized for all their customers. Rapgenius did have what, 150 requests per second? Surely that can even be handled by a single intelligent router if they had a dedicated router per customer that's above a certain size (of course you still have to go to the groups of dynos model once a single customer grows beyond the size that a single intelligent router can handle).
wmf 14y ago
Amazon ELB? It does cost significantly more than Heroku AFAIK.
- adamwiggins 14y ago
  My understanding is that ELBs are HAProxy, and they may be set to use the leastconn algorithm (a global request queue that is friendly to concurrent backends). However, once you get any amount of traffic they start to scale out the nodes in the ELB, which produces essentially the same results as the degradation of the Bamboo router that we've documented. The difference, of course, is that ELBs are single-tenant. So a big app might only end up with half a dozen nodes, instead of the much larger number in Heroku's router fleet. Offering some kind of single-tenant router is one possibility we've considered. Partitioning the router fleet, homing... all are ideas we've experimented with and continue to explore. If one of these produces conclusive evidence that it provides a better product for our customers and in keeping with the Heroku approach to product design, obviously we'll do it.
  - twic 14y ago
    I hope you'll be able to share your findings with us, even if they're negative. As someone who has no stake in Heroku, i have the luxury of finding this problem simply interesting! My hypothesis is that tenant-specific intelligent load balancers would be plausible; i would guess that you would never need more than a handful of HAProxy or nginx-type balancers to front even a large application. Your main challenge would then be routing requests to the right load balancer cluster. If you had your own hardware, LVS could handle that (i believe that Wikipedia in 2010 ran all page text requests through a single LVS in each datacentre), but i'm not sure what you do on EC2. However, "hypothesis" is just a fancy way of saying "guess", which is why your findings from actual experiments would be so interesting.
- bgentry 14y ago
  ELBs have a least-conn per node routing behavior. If your ELB is present in more than 1 AZ, then you have more than one node. If you have any non-trivial amount of scale, then you probably have well more than 1 node.

deleted 14y ago

[deleted]

dangrossman 14y ago
http://rapgenius.com/James-somers-herokus-ugly-secret-lyrics http://rapgenius.com/James-somers-herokus-ugly-secret-lyrics There are screenshots of the website where it said that in multiple places.
habosa 14y ago
Unless I'm entirely misunderstanding the situation, this was definitely the premise of the "intelligent routing mesh" that Heroku used for so long on the Bamboo stack.

adamwiggins 14y ago

I hear you. Heroku's value proposition is that we abstract away infrastructure tasks and let you focus on your app. Keeping you from needing to deal with load balancers is one part of that. If you're worried about how routing works then you're in some way dealing with load balancing. However, if someone chose us purely because of a routing algorithm, we probably weren't a great fit for them to begin with. We're not selling algorithms, we're selling abstraction, convenience, elasticity, and productivity. I do see that part of the reason this topic has been very emotional (for us inside Heroku as well as our customers and the community) is that the Heroku router has historically been seen as a sort of magic black box. This matter required peeking inside that black box, which I think has created a sense of some of that magic being dispelled.

cynicalkane 14y ago
You sound like a politician talking to someone of the opposite party, in that you say "I hear you", but then completely fail to address anyone's concerns. Selling a "magic black box" that guarantees certain properties, changes them, then lies about having changed them presents a liability for users who want to do serious work. A major selling point of Heroku is that scaling dynos wouldn't be a risk. This guarantee is now gone and it's not coming back soon even if routing behavior is reverted, because users prefer good communication and trust with their providers. The responses of Heroku are blithe non-acknowledgement acknowledgements of this problem.
- adamwiggins 14y ago
  Harsh. I'm going to ignore the more inflammatory parts of this (feel free to restate if you want me to engage in discussion), but one bit did grab my attention: "A major selling point of Heroku is that scaling wouldn't be a risk" This is interesting, especially the word "risk." Can you expand on this?
  - jfabre 14y ago
    Very small customer here. I don't know much about the abstraction you provide us and I don't want to know as long as things go well. To my point of view, the routing is "random" thus kind of unpredictable. If scaling becomes more of an issue with my business, the last thing I want is to have random scaling issues that I can not do anything about because the load balancer is queuing requests randomly to my dynos. I want my business to be predictable and if I'm not able to have it I'm going to pack my stuff and move somewhere else. For now, I'm happy with you except for your damn customer service. They take way too long to answer our questions! Cheers! :)

rhizome 14y ago

I'm sure at least one person's job depends on this working out in the direction they've been trying to go, cf. Blaine Cook (who I think got a raw deal).

aphyr 14y ago

"the switch from intelligent to randomized routing" As I understand it, Heroku (on the Bamboo stack) didn't up and decide "Hey, we're gonna switch from intelligent to random routing." The routers are still (individually) intelligent. It's just that there are more of them now, and they were never designed to distribute their internal queue state across the cluster. The system as a whole behaves more and more like a random router as the number of intelligent bamboo routing nodes increases.

adamwiggins 14y ago
True, although it's more confusing than this. We didn't make an explicit decision for Bamboo, and thus the big problem — docs fell out of date, at a minimum. For Cedar, we did make an explicit decision. People on the leading edge of web development were running concurrent backends and long-running requests. Our experimental support for Node.js in 2010 was a big driver here, but also people who wanted to use concurrency in Ruby, like Ilya Grigorick's Goliath and Rails becoming threadsafe. These folks complained that the single-request-per-backend algorithm was actually in their way. This plus horizontal scaling / reliability demands caused us to make an explicit product decision for Cedar.
- obilgic 14y ago
  > true that makes sense, i was wondering how intelligent routing was implemented in the first place.
  - adamwiggins 14y ago
    Oh, got it. How's this: In the early days, Heroku only had a single routing node that sat out front. So it wasn't a distributed systems problem at that point. You could argue that Heroku circa 2009 was more of a prototype or a toy than a scalable piece of infrastructure. You couldn't run background workers, or large databases. We weren't even charging money yet. Implementing a single global queue in a single node is trivial. In fact, this is what Unicorn (and other concurrent backends) do: put a queue within a single node, in this case a dyno. That's how we implemented it in the Heroku router (written in Erlang). Later on, we scaled out to a few nodes, which meant a few queues. This was close enough to a single queue that it didn't matter much in terms of customer impact. In late 2010 and early 2011 our growth started to really take off, and that's when we scaled out our router nodes to far more than a handful. And that's when the global queue effectively ceased to exist, even though we hadn't changed a line of code in the router. The problem with this, of course, is that we didn't give it much attention because we had just launched a new product which made the explicit choice to leave out global queueing. It's this failure to continue full stewardship of our existing product that's the mistake that really hurt customers. So to answer your question, there was never some crazy-awesome implementation of a distributed global queue that we got rid of. It was a single node's queue, a page of code in Erlang which is not too different from the code that you'll find in Unicorn, Puma, GUnicorn, Jetty, etc.

jcampbell1 14y ago

Random routing will work fine so long as the operating system has the ability to intelligently schedule the work. The problem is that the dynos were setup to handle request sequentially. Unicorn will help mitigate the problem, but the best solution is to not try and serve webpages from hardware that is about as powerful as an old mobile phone. The 2x dynos are a step in the right direction, but I have no idea why they don't offer a real app server like a 16x dyno.

adamwiggins 14y ago
It's probably easy to guess that once we have 2X dynos, 4X dynos (and up) may be on the way. We'll drive this according to demand, so if you need/want dynos of a particular size, drop us a line.