Loading...
Write path:
Let's say this is something on the scale of bitly, I'd guess that bitly has 1M monthly active URL creating users. I'll guess that each user creates 5 URLs a month, so 5M URLs a month. Let's say each URL has to be persisted forever. If we use the character set [a-zA-Z] to generate URL slugs, we'd get 52 ^ (slug length) unique URLs.
52 ^ 6 gets you around 20B URLs, which is plenty, so let's call 6 our slug length. You can store each slug in 6 bytes (can be optimized further, maybe not necessary. Let's just assume a replication factor of 3, and think about our storage use over 20 years. 5M urls/month * 12 months/year * 20 year * 6 bytes/url * 3 = 21.6 GB.
Read URL path:
Each URL probably receives 100 visits on average the first month, then 10 a month for the rest of the year. Let's make this easy and say we are at a steady state system (no spikes in URL creations or visits on a monthly level), and each URL will receive 10 monthly visits. So 5M * 12 * 20 * 10 = 12B visits a month -> 12B * (1 month / 30 days) * (1 day / 24 hours) * (1 hour / 3600 seconds) = 4k QPS.
Read Analytics Path:
I'll assume we get a fairly steady 10 QPS to our analytics service. (assuming people view analytics more often than they create new urls)
CreateUrl(string original_url, UserId user);
RedirectToUrl(string shortened_url);
UpdateUrl(string shortened_url, string new_url, UserId user);
DeleteUrl(string shortened_url, UserId user);
ViewAnalytics(string shortened_url, UserId user);
If we decide we need a customer to be able to see that their newly created URL works right away, we can use a trick like passing in the customer ID with read requests, and then searching their created URLs on a read miss.
We're not going to be doing complicated joins on this data, however serving 4K QPS and handling 2 write QPS is totally reasonable with a full featured RDBMS like Postgres.
We're going to have a single table that has an original URL, a creating customer ID, creation timestamp, last modified timestamp, and the slug for the tiny URL.
We'll have two write replicas in active-passive configuration order to always be able to handle writes. More write replicas is not needed as write traffic is incredibly low, even cross continent latency is probably fine here, I think the write path is not a priority. Read replicas will periodically be updated with the latest data from write replicas, around once every 30 seconds.
The analytics portion will rely on serving nodes to push data at a configurable interval, around every minute. This latency is acceptable because users will not need to see incredibly fresh analytics data, a latency of 5-10 minutes before seeing the newest data is totally fine. (how should I talk about why I chose a push model?) We'll choose a standard time-series database to use for analytics.
Given the latency demands of this service, we absolutely will want to have regional replication of our backing database in several different points of presence. We are just serving URLs so no need for something heavy like a CDN, let's just do standard postgres regional replication to be reasonably near our customers. Something like a topology with a US east and US west replica is probably fine to start, and we can always add more as we expand to new customers.
We are going to anticipate that certain hot URLs will make up much of the traffic and cause most of our headaches. We can handle this by having replicated stateless serving jobs that will cache hot URLs in front of the database replicas. The set of URLs we're serving is very small and the cache will easily fit in memory, so we'll opt for that rather than choosing redis for now. We'll invalidate cache entries every 30 seconds to allow for updates of URLs to become user visible reasonably quickly (please give me feedback on how I should talk about cache sizing and location - in redis/in serving replica memory)
In order to ensure minimal disruption when adding/removing serving replicas to our fleet, we'll take advantage of the widely used consistent hashing algorithm. When a node is removed from the system, clients will discover its removal after a few failed requests and be able to either find the next node in the system locally through a client library, or talk to a cluster manager to determine which new node to send requests to. When new nodes are added, we will pre-warm local caches to ensure that they will be able to handle traffic immediately when they start serving.
Additionally, we will have serving nodes periodically push data to our analytics service. This will be at roughly one minute intervals, so not high traffic. Serving nodes will discover analytics service nodes via the cluster manager.
When a browser requests a URL, if the URL is cached the serving nodes will be able to quickly retrieve it from memory and return it. Otherwise it will have to reach the database. I anticipate the vast majority of traffic will hit the cache. URL writes will have to hit the DB before being updated in the cache, as if we can't write to the DB, being able to serve it from the cache for a few seconds, then losing it is a horrible user experience as they'll think their URL is ready to go but it might not be.
Analytics requests will be polled directly from the analytics service and will always hit the database, the scale will be low enough where this is reasonable for the time being. We can think about using some short-lived caching if analytics sees higher traffic than anticipated, as serving some slightly stale analytics (O(5-10 minutes)) is totally fine.
I believe this is mostly covered above, not sure there's a ton more detail to go into here.
Each component scales well, depending on request patterns we might want to consider switching to a NoSQL database for serving URLs if we see significantly higher read traffic than anticipated. Given that we have cross region replication, every time there's a read miss we'll have to check all write replicas for the data. Read misses are predicted to be incredibly rare as they require one of a few things to happen:
Analytics data might require some periodic compacting into separate views depending on the traffic that we see there. This is probably too simple to start talking about OLAP databases so I'm going to plan not to discuss this here.
I chose postgres for serving as it is a full featured RDBMS and can easily handle the scale we're discussing here. We can consider nosql if we need it, but as data tends to get more relational and interconnected over time, I'm opting not to spring for a NoSQL database unless I truly think I'm going to need it immediately. (and we don't in this case)
On the read path, we could potentially see some hot shards. We should think about load aware replica placement so that we can better scale up to handle hot urls quickly.
The analytics path could become too slow if we have lots of big corporate users, so we should think about introducing a separate serving system that compounds data periodically to better meet their needs.