Google also has the advantages that they now only need a read-only key-value store, and they know the frequency distribution for lookups. This is now the kind of problem many programmers would be happy to spend a weekend optimizing to get an average lookup time down to tens of nanoseconds.

I don't think it would even cost me very much to host all these links on a GCP or AWS thing, I don't think more than a couple hundred dollars a year.

Obviously raw server costs aren't the only costs associated with something like this, you'd still need to pay software people to keep it on life support, but considering how simple URL shorteners are to implement, I still don't think it would be that expensive.

ETA:

I should point out, even something kind of half-assed could be built with Cloud Functions and BigTable really easily; this wouldn't win any kind of contests for low latency, but it would be exceedingly simple code and have sufficient uptime guarantees and would be much less likely to piss off the community.

If I had any idea how to reach out to higher-ups at Google I would offer to contract and build it myself, but that's certainly not necessary, they have thousands of developers, most of which could write this themselves in an afternoon.