URL shortening : data partitioning

Question

I've been looking in many places about this question - most top Google search results are copy-pasted from a single source, and others are not particularly helpful. Not sure if I am allowed to include the links of my search - so refraining for now.

URL shortening has 2 aspects :

1. Write : get a long URL, write a mapping of short vs long, return short URL.
2. Read : get a short URL : find the long URL, and maybe redirect to it.

Common design I see is :

> (Key Generation service) ----> (Application server)
>         |                              |
>         |                              |
>         |                              |
>         V                              V
>     (Key DB)                    DB with Short vs Long mapping

Seems like the same Application server is doing read and write activities.

Now for data partitioning - I am getting a single advice from almost everywhere : hashing (possibly consistent) of long URL to a particular server.This only helps in the write aspect. For reading, we need to check every application server : do you have a long URL for this short URL ? And every one admits that reading is much much more important for this design than writing. So they are optimizing for the least important use case ?

Am I missing something very basic ?

Answer 1

When dealing with a distributed system, you have to accept the fact that, at some point, your nodes will see different data, either because of network partitions or latency over the network. Once you accept that, you can decide what the application will do. Will you throw an error, will you try to rebuild the data, will you go look for the data someplace else, will you display stale information, etc.

I can't know your exact use cases from the information you provided in your question so I'm making some assumptions when saying the following:

• you can replicate the writes. Once a write arrives on a server to map a long URL to a short one, you do so, write the data on that server then send the data to all other servers to store it also. When a read will arrive asking for a short URL, on whatever server you are, you already have the data.
• of course, as already mentioned, the servers might see different data. The previous point works for all servers that receive the data and update it in their DB. If some servers are offline for some reason, when they come back online, they will have some data missing. If you receive a read on such a server for something missing, you go ask other servers if they have it. Once you receive the data on the server, you store it so you don't have to look for it again. You might also have some periodic jobs that synchronize data between the servers, eagerly without it being asked instead of lazily on demand.
• at some point you can still end up with no data and no way to retrieve it, in which case you need to decide what to do: fails with an error message, tell the user to return later, shut down that node, etc, really depends on your use case.

The approach is not very different than how a cache works: got the requested data in cache? Serve it. If not, retrieve it from the main data source, store it, serve it. You might also look at how DNS works for example, and borrow some ideas from there, since a mapping from a short to a long URL is not very different than a mapping from a URL to an IP.

Answer 2

One option is to include a shard id in the tiny url you generate. E.g. Let the first n characters of the tiny url represent the shard id. Then when a read request comes in, your load balancer parses the first n characters out and uses them to redirect the request to the correct application server(s). The obvious disadvantage here is it increases your tiny url length by n characters.

Also to clarify why you may want to use partitioning even if the data fits on a single machine (like it does in this case). One reason could be query throughput. On partitions the queries will run against a smaller volume of data making them faster. Another reason could be wanting to store older (and presumably less frequently accessed data) on a different (maybe cheaper?) storage. I found this article pretty useful when reasoning about these things: https://docs.microsoft.com/en-us/azure/architecture/best-practices/data-partitioning