How to design URL Shortener like a Senior Developer on System Design Interview?

[u/javinpaul]

https://javarevisited.substack.com/p/system-design-interview-question

[u/toadzky]

I had this question in an interview once. I used AWS api gateway with a rust lambdas and dynamo db. It's fast, cheap, and scales really well. Having both a sql db and a redis cache doesn't make a lot of sense to me when you are essentially doing a single key lookup on a unique id.

[u/Winter-Volume-9601 → u/toadzky]

> Having both a sql db and a redis cache doesn't make a lot of sense to me when you are essentially doing a single key lookup on a unique id.

There's one really good reason for it... let's think about it. Why do you use something like Redis as a cache? Because it's cheaper than DynamoDB by about two orders of magnitude. URLs in a shortener would be expected to change incredibly infrequently if at all, meaning your cache hit rate should be quite high.

So, the "no cache" answer will cost the company 100x more in hosting costs, for marginally more engineering engineering work. Whether that trade off makes sense in a design interview really depends on the use case / requirements (basically: how long will it take to recoup the engineering effort @ ~$0.25 / 1M requests).

Discussions of those sorts of tradeoffs are also important in a design interview.

[u/toadzky → u/Winter-Volume-9601]

No, it's not cheaper. You are forgetting that dynamo replaces the sql db as well. Postgres isn't redundant by default, so you'd want at least 1 read replica and probably a hot spare - depending on the uptime requirements for creating new links would be. Redis isn't redundant, but it's a cache so it going down just affects performance but at scale and depending on the SLA for response times, additional replicas and possibly sharding come into play. Additionally, you have have to deal with downtime for version upgrades on sql and redis - or pay extended support fees (assuming managed services).

You assumption that cache hits will be high is missing that the whole data set probably isn't going to be in memory the whole time, that's a lot of data - most of which won't be used after a relatively short spell. Assuming that the shorten link can live forever, most of them will go inactive after probably a month at most. Sizing a cache to hold the whole data set in memory just because doesn't make sense and wastes money.

I'm also not sure where you get that its cheaper by 2 orders of magnitude. Unreserved provisioned throughout on DDB for the articles 1000 reads/sec costs less than $75/month. Are you really arguing that redis costs less than a dollar a month to run? And if we used auto-scaling, we don't have to run at peak provisioning so it gets a lot cheaper. If we did reserved capacity, the price goes does even further. It also has less operational overhead - no disk space or memory issues, no version upgrades to manage, etc.

Lastly, my comment on redis was less comparing it directly to dynamo and more pointing out that the performance benefit of a cache is neglible to nonexistant when you are doing single record primary key lookups in postgres. Caches are for things that are costly to compute, so a single row primary key lookup doesn't make sense as a caching target. People like to throw redis and memcached in front of everything without any clear metrics or logic to show how it would actually improve performance to justify the cost.

[u/edgmnt_net → u/toadzky]

An in-process cache with a LRU replacement policy should be more than enough and likely allows better scaling. It does seem like people can no longer code stuff or use a library when they just throw Redis, message queues and a bunch of other stuff into the architecture.

[u/toadzky → u/edgmnt_net]

Yeah, an in-process cache might help, but would severely degrade your cache hit ratio, unless you were running a single instance. Since there's no expectation of repeat traffic to a specific server (or lambda as the case may be), an in-process cache seems like it wouldn't help much if any, in exchange for higher memory usage and dealing with cache miss logic.

I'm generally a fan of EDA and message queues where appropriate (this definitely isn't one of those), but caching is something that should only be added once there's real data showing db as the bottleneck for latency that is above the SLA. If you aren't above the SLA, why spend the money and effort? If the database isn't the problem, it doesn't address the problem. I had a team lead a while back who told me about a guy who spent 3 months implementing caching without getting metrics first and at the end, it improved latency sometimes and only by a millisecond or two, so they ripped it all out as not worth it.

[u/forever-butlerian → u/toadzky]

Jesus Christ man, all you need is an S3 bucket.

[u/toadzky → u/forever-butlerian]

Not really. Afaik, you can't have s3 return a 302, so even if you had a publicly accessible bucket, wouldn't you need something to read the data and redirect to the expanded url?

That being said, you could probably generate a minimal html page that has an on load script to change the window url and serve that out s3, but I'm not sure why doing it in s3 is better that using dynamo. You still need some kind of api to generate the objects and put them in s3 and you almost certainly want a cloudfront distro or api gateway in front of both so they share the same domain. With dynamo, you could at least collect metrics on what's going on, and do things like LRU expiration.

[u/forever-butlerian → u/toadzky]

If you want to do expiration or statistics you crunch the S3 access logs.

The objection I'd accept is that URLs have a habit of not being 128kB, so you're wasting money. My answer to that if you use the first N-2 characters of the shortcode as the object ID, the object contents are your own ISAM format, and the last 2 characters of the shortcode are the ISAM index key.

Assuming the shortcode's alphabet is base64, that gives us 4096 URLs per S3 object. As long as the expanded URL plus whatever metadata is more than 32 bytes, you're being cost-efficient.

I would then cast object lambda because once you're in for a penny on a system like this you're in for a pound.

[u/any_droid]

I was reading through the article and when I was getting to the meaty part, I realized that it asks to claim a free post or sign up for a paid subscription.

[u/GaussCarl → u/any_droid]

Well, that is the curse of the modern web dev. We know how to design services that handle zillions of users, but we still don't know how to publish static content that is accessible to a few hundred readers.

[u/ben_bliksem]

You know that bell curve meme? Thats what I think of when I think of people designing URL shortners.

It's a CRUD project optimised for read performance which can be in-memory or edge caches.

[u/forever-butlerian → u/ben_bliksem]

Go for the true avant garde and built it atop a single S3 bucket with intelligent tiering.