$50/month would barely scratch the surface.

Let's take a conservative approach, and say there are:

• only 1 billion links
• each link only points to a URL of up to 100 characters in length on average (some will be 1000 or longer, but let's hope some are 50 or shorter)
• less than 10 billion daily hits total (that's an average of 10/link)
• the response time should be well under 50ms.

Now you're looking at 100GB of raw data to put into a database, that needs to return 100K answers/second, in less than 50ms each, worldwide, 24/7.

What is your estimated cloud cost for something like 256GB of RAM, 128 cores, 10Gbps connect, replicated across several zones, and 1TB/day outgoing transfer?

That's only for the redirect responses in read-only mode, nothing else. You will also need some maintenance to keep it 24/7, for when the server catches fire, or gets obsoleted, and when new exploits come up against your software stack.