Loading...
Write: User sends a long url to the creation service, and gets a short url as response.
Read: User types a short url in web browser address bar. It sends a request to the read/translate service, and the service responds with the corresponding url if found, otherwise responds with an error code indicating there is no corresponding url.
Uniqueness: it's ok for a same long url to be shortened to different short urls. However, it's NOT ok for a same short url to be translated back to different long urls.
Durability: urls data should be stored permanently until expiration.
Traffic: say we process 100 million write requests (creation of short urls) per year, and 1 billion read requests (translate short urls back to long urls) per year. So write:read = 1:10
Durability: say we store urls data for one year. Expired urls data will be deleted
Availability: the service shall be available as much as possible
Data: the short urls shall be as short as possible to save storage budget
QPS:
write: 100 million / 365 days / 86400 secs = 3.2
read: write * 10 = 32
The traffic can be easily handled by a single modern server. However, for sake of high availability, we should have redundancy to ensure uninterrupted service as much as possible.
Storage:
To save storage, and make short url easily readable, we can use base 62 encoding: characters chosen from 0-9a-zA-Z. We can remove some confusing characters, like 1/I/l or 0/O. This kind of details don't change our fundamentals, though. So let's keep base 62.
Since we store one year of data, and average writes is 100 million yearly, 62^5 = 916 million. Taking into account traffic variations, 5-character-long short url keys should be more than enough to store all the data. Total short urls of one year = 5 byte * 100 million = 500 MB
Another option is to use integer ids (unsigned 4-byte integer can store up to 4 billion records). However, integer ids are easy to guess or speculate. A hacker can simply iterate thru a range of integers to know what urls are stored in your database and do something harmful.
A long url length varies a lot, let's take 500 chars, which is typically enough for moderate to high traffic sites, or for urls including reasonable amount of GET params. Total long urls of one year = 500 byte * 100 million = 50 GB. Say if we have some outliers, 100 GB should be enough.
The amount of data can be easily fit into a single modern database. However, for sake of durability and availability, we don't want to lose data, neither temporarily or permanently. Replication is required.
It's unclear to tell whether we need to partition the data. But what we know is that partition will add design complexity. We choose to begin with no partitioning for simplicity and small scale of data. We will revisit at later stage.
Write (Create)
Read (Visit)
Because we say that a single short url should be only mapped to one long url, but not necessarily vice versa, naturally we have a key-value pattern, where the key is short url, and value is long url.
Option 1: SQL:
short_url: varchar(5)
long_url: varchar(1000)
We can let API service to reject any urls longer than 1000 chars, which is uncommon
Option 2: key-value store:
same schema as SQL
Note that our write QPS is low, and read QPS is low to moderate. Also, most read queries are random. That said, there's no significant concern on choosing one over the other. We can choose SQL to start with.
If the traffic is much higher, we would lean towards key-value store due to its high read/write performance and easy to scale.
Say we have two clients, where one wants to create a short url, and the other wants to visit a short url.
For the client who wants to create a short url, it sends a write request to server (leader). Server (leader) generates a short url and writes to database (leader). Then, server (leader) responds the short url back to client (create short url).
For the client who wants to visit a short url, it first inputs the url into browser address bar, where browser looks up the ip address of the short url servicer from its cache or from a DNS, and directs the client there. It sends a read request to server (leader), which pulls the corresponding long url from database (leader) and responds back to the client.
Meanwhile, as we require replicas for availability reason, we have multiple server followers. Heartbeat messages are exchanges between these server instances. The followers do not handle any client request, unless the server leader is dead and a then-follower is elected as a leader.
Similarly, we also have multiple database followers. As soon as database leader commits a change, it pushes the same change to database followers.
As we estimated earlier, the traffic is low, and thus one single leader is able to handle it. Followers are mainly for availability and durability.
I've explained the request flows in high-level design.
One big thing is how the server is able to generate a unique 5-char long string for every incoming write request. There're a few approaches:
Option 1: We can have a batch process running async to pre-generate random 5-char strings and store them in a database table. When there comes in a write request, the server simply grab one and remove it from the table. This saves on-the-fly computation time of string generation, although add a round trip to database. So the performance impact may vary (I'll explain more details in Option 2). On the other hand, because the job is running async ahead of time, and the table is also separate from the main table, it doesn't add too much of system complexity. However, we do need this new batch job and new table, which are additional resource cost.
Option 2: We let the server to randomly generate a string when receives a write request. This would not take much time initially, as generating 5 random characters is fast. However, since we want to avoid collision, we need to check it against existing keys. To do that, we need to query the database table to see if the new key exists (which takes a database round trip, plus an index search for a SQL database). If we want to be faster, we should load the existing keys in the server memory. That said, as the number of short urls grow, chances of collision would become dramatically higher, especially when the magnitude of number of keys is approaching limit. To mitigate this, we need to pick a longer length at the very beginning, say 6 or 7 characters, which yields larger storage and memory space.
Option 3: We can do deterministic encoding on the long url characters. There're existing hashing algorithms that maps arbitrarily long bytes into a fixed length string, e.g., MD5, SHA-1, etc. We can rely on one of these algorithm, and further map it down to 5 characters; or we could develop our own base 62 hashing function. Since the input length is a url, the computational cost is expected to be small. For a well-designed hashing function, the probability of collision is also negligible at our scale. However, note that this also requires us to check the newly generated key against existing ones in the database.
I'd recommend we go with Option 1 or 3.
For replicas, as mentioned earlier, we use them to provide user high availability. We use them in async mode to minimize latency for users.
Besides what I've explained in the previous sections, we may consider letting server followers and database followers to handle user read requests.
Pros: server leader and database leader will handle writes only, relieving a lot of burden on them.
Cons: the followers work in an async mode. There's a small chance that user may not be able to visit most recently created short urls.
Caveat: for a user who just created a short url, directing read to followers may yield inconsistent user experience (i.e. short url not found). We should make such "read after write" requests to go to the server and database leader.
When server leader is down, the server followers will elect a new leader. There will be a short amount of system down time before a new leader is elected.
When database leader is down, the database followers will elect a new leader. Meanwhile, the followers may not keep up to date as the leader, missing some most recent data; also, the leader may be dead in the middle of updating some data. To mitigate the inconsistency issue, we can keep a write-ahead log on each database, and make a rule that a write is considered fully committed by server only if both the leader and at least some followers have committed the data. One of the followers who has the consistent cursor in write-ahead log will be elected as the new leader. The write-ahead log can also mitigate the issue of leader being dead in the middle of a database operation.
If traffic is much higher, we should consider load balancing user requests to different server instances.
If data is much more, we should consider partitioning databases, and not to use SQL because it would become slower on both read and write.