So, yes, the article is an interesting war story and I don't want to diminish the pain of the writer, who inherited a system he didn't particularly want to touch. But yes, the solution is basically "sharding". Personally I'd start with per-customer sharding, and hope that A: that holds for long enough that I'm much bigger before it's a problem and B: that if I'm already sharding by customer, when the day comes that one customer is too big for a single instance of whatever I'm using that the architecture won't get too offended if we shard a single customer multiple times.

(If I were doing both of the things, I'd certainly architect the former so the latter was possible at a later date. It's not that difficult, really; you've already got the "split problem -> process subprobems -> combine results" architecture in place, you just have to make sure not to accidentally grind in the nature of the subproblems too deeply into the system, which is just boring ol' software engineering. It doesn't even cost you much since you're not going to win that much by assuming the nature of the subproblems; it really just would be sloppy programming.)

The main challenge here was lack of resources and the importance of getting it right, rather than the challenge of the problem itself, which I don't think is anything the author doesn't know and didn't acknowledge already.