There are two ways to look at this, and depending on your point of view you might be upset.The root of the dispute is how they scale and how that affects latency.

According to these write-ups, Heroku scales performance by doing dynamic scheduling on an array of identical servers (called 'dynos'). The documentation talks about a feature named "Intelligent Routing" which only sends work to a dyno which is available to do work.

That is a pretty ideal setup because in practice it means that you get linear scaling by adding server instances, and since costs are based on total server instances you get both linear scale increase with linear cost increase.

However, there is a very classical problem, first noted by Gene Amdahl, about the cost of figuring out how best to parallelize a stream of requests, vs the rate at which you could satisfy those requests. It became known as "Amdahl's Law"[1]. It limits the practical scalability of a lot of systems.

So at some point, Heroku got big enough, that the cost of figuring out which server instance wasn't busy, was taking "too long". (that cost is the (1-P) part in the Amdahl equation) so they decided to reduce the cost of making the choice by replacing a "data driven choice" with a "statistics driven choice". This too is actually a pretty well known way of doing things (Google and Blekko use it to send search queries to a bunch of waiting backends) But unlike the 'idealized' case which has every server instance handling at most one queue, the value becomes a probability that the server instance is either not-busy, or that the current transaction will finish quickly. This works well for systems where the cost of every transaction is nearly identical, you just add servers until the 90th percentile of requests hits your target, but poorly for systems where each request has a variable amount of work it might do.

I spent a number of years studying these sorts of systems while solving scalability issues at Network Appliance. A file system built out of a distributed set of nodes providing access to a single file system image needs to know a-priori the cost of each transaction flowing through it in order to optimize scheduling. Similarly RAID subsystems need to know which disk I/Os are going to land in the cache or on the disk, and if they land on the disk will they result in a seek or not. You end up with a directed graph of weighted probabilities being shoved through a channel of fixed bandwidth. Its all amazingly fun until someone says "I have to get data back from the disk in no less than 10mS every time" (databases would say stuff like that) and then you start trading dollars for milliseconds as they say.

So Heroku changed their algorithm, didn't tell anyone, and the systemic behavior changed in a very user visible way for large users (in this case Rap Genius). The folks at Rap Genius were pissed off that they made this change without informing them, and they, Rap Genius, looked bad to their customers because of it. Nobody in operations wants to say "Uh, I don't know why your experience with our service is currently sucking."

I can see why Rap Genius is mad, and I can see that Heroku might not have fully thought through the ramifications of their algorithm change.

[1] http://en.wikipedia.org/wiki/Amdahl%27s_law