1. The generation of a unique id
2. The mapping of the id into a short_url that is less than 10 characters long
3. The storage and retrieval of the id + long_url

There are a few ideas that can be found be moving the operations around to different components of the system.

1. The generation of a unique id
2. The mapping of the id into a short_url that is less than 10 characters long
3. The storage and retrieval of the id + long_url

Generation of the unique id:

1. Generate an id on the application side and attempt to insert it. If there are multiple applications, we’d have to implement this everywhere.
2. Generate an id in a 3rd system and attempt to insert it. If there are multiple systems needing a unique id, this may be the way.
3. Write the url to the database and auto-increment the primaryid.

For systems 1 and 2, we need to still guarantee the uniqueness or we may have to account for retrying on collisions. In the simplest form, this could be using an MD5/SHA of the long-url or generate a UUID.

Mapping of the id to short_url less than 10 characters long:

This needs to be a 1-1 mapping. Whether this is a 64-bit int primary key in the database or a UUID, we can use encoding (base64) to shorten it up to the required length and give this out to the user as our short url.

Let’s make a few assumptions regarding the scale up and do some rounding for convenience.

• The maximum size of a URL is 512 bytes and the short url can only be 10 bytes. We can estimate this as 500 bytes / url.
• The number of reads is 10 times the number of writes.
• At some point in time, we have 100x more load on the system.
• The number of seconds in a day is 86400 which we’ll estimate as 1e5.

Make a table and compare in the next step.

100x

Note that depending on our storage medium, a write could take anywhere between 1 IOP and 3 IOP. We’re roughly ballparking requirements, so we don’t need a high-level of precision. See IOPS for more details.

Another thing to note is that the worst-case storage requirements are 5 PB. We’ll need to calculate the cost tradeoff between disk vs cpu for compression. We’re growing at approximately 3PB / year if we compress the data.

We need to store a total of 1E13 urls. First, we need to know the total number of bits we need to represent this.

Since \(2^{10} = 10^{3}\), we need a total of

10¹³ = 2¹⁰ * 2¹⁰ * 2¹⁰ * 2¹⁰ * 10

~= 2⁴⁴

This means we need approximately 44 bits of address space to store all of our URLs over the lifetime of the system.

We need to generate a unique key and the easiest way of doing so could be taking an md5/sha/uuid of the long url. Then we map/encode the key and store it.

An MD5/SHA/UUID is \(32 hexchar * 4 bits/hexchar = 128 bits\)

For the best user experience, we would like to just have the characters [a-z0-9] - which would give us base36 encoding. If we use [a-zA-Z0-9], that would be base 62 encoding, however, we’ll be using base64 to do our estimations as \(64 = 2^6\)

We need to figure out the total length of the short url based on an 128 bit id.

• base2 representation, the total length would be 128. We can imagine this as a set of 128 elements each having values 0 or 1.

• base16 representation, a hex value is 4-bits. Each character now represents \(2^4 = 16\) values. We can group the 128 elements into groups of 4. This would be 32 groupings. In mathematical terms, 2¹²⁸ = (2⁴)³² . 32 hex characters is the standard representation of a UUID/md5/sha.

• base64 representation \(2^{128} = (2^6)^x\) . Taking \(log_2\) of each side, \(x = ¹²⁸⁄₆ ~= 21\)

Even in base64 representation, a 128-bit id will be represented by 21 - base64 characters.

We need to make sure that we can store \(10^{13}\) in the worst case scenario of 100x more traffic.

We should calculate the maximum address space available to us for 10 elements:

• base32 -> \((2^5 )^{10} = 2^{50} = (2^{10})^5 = (10^3)^5 = 10^{15}\)
• base64 -> \((2^6) ^{10} = 2^{60} = (2^{10})^6 = (10^3)^6 = 10^{18}\)
• 10¹³ in base32 -> \(10^{13} = (2^5)^x\) . Then taking \(log_2\) again, \(13 * log_2(10) = 13 * 3.5 = 5 * x\) and \(x \approx 9\)
• 10¹³ in base64 -> \(10^{13} = (2^6)^x\) . Then taking \(log_2\) again, \(13 * log_2(10) = 13 * 3.5 = 6 * x\) and \(x \approx 8\)

Given that we need about 8 characters of [a-zA-Z0-9] and 9 characters of [a-z0-9], using base32 probably provides a better user experience.

Since we calculated we only need 44-bits earlier, we can use a 64-bit key. There are other hashing functions such as murmur or fnv which are fast and support lower bit-lengths.

Let’s quickly look through the other designs.

In this case, we are essentially going to make a single counter. Incrementing a counter in memory takes about 0.2-0.3 microseconds given it should take 2 memory accesses and an addition. This is \(0.3 * 10^{-6} = 3 * 10^{-7}\) . This would give \(0.33 * 10^7 = 3.33 * 10^6\) increments in a second. A rough guesstimate of 3 million in a second or 3333 increments per ms. Note that this is for single threaded counter. With a multi-threaded counter, we’d have to deal with locks on the memory if we wanted accuracy or the counter to be atomic, which we need to have to guarantee uniqueness.

Although our memory is fast enough, the bottleneck occurs somewhere else. From redis benchmarks, the incr operations maxes out at 150e3 requests per second. In our first phase of the lifecycle, we only need to do 333 writes per second on average and 3333 writes per second on peak (10x).

At this point, this design requires a 3rd component, so let’s avoid the extra complexity unless necessary. We’d need to figure out how to make this resilient, which could be tricky.

We already examined the application limits, we know the address space works fine as we need 44-bits and we can have 64-bit indexes.

From the initial requirements table we need to have a total of 50TB of storage and support a total IOPS of 4000 or 40000 at peak.

An EBS volume (gp2) can be up to 16TB with 10k IOPS per volume. And naively, we can put 23 such volumes onto a single machine. The total storage over 10 years is approximately 60 TB. Hopefully, having 5 such volumes would work. Naively, the from a IOPS and disk storage can be managed on a single machine. From Aurora benchmarks, a machine can do 100k writes and 500k reads with a r3.8xlarge with 32 cores and 244 GB memory, so the cpu should also be fine at the database layer. Finally, the network would be at peak \(40000 * 500 bytes = 4 x 10^4 * 500 = 2000 * 10^4 = 20 * 10^6 = 20 MB/s\) . Most systems have gbit links, so even with multiple slaves, this should not be an issue.

The app should only take a few ms and then we are hopefully in an epoll loop at the database end. The entire request cycle should be around 10 ms, the main question is how much context-switching would affect the overall throughput. Naively, we can say each core can handle \(1 / (10 ms / request) = 100 requests/sec\) . This would mean at average we need 40 cores and at peak 400 cores. However, we know it should be much less because of the epoll loop. The application side encode/decode/http-request handling/db query should be on the order of ms. Benchmark your own code to confirm.

This covers the cpu, memory, network, and disk on the app and database. Regarding fault tolerance, we need to have a standard master-slave situation. Automated failover ranges from 30s to 90s.

For the initial requirements, this is the simplest design from a development and maintenance perspective also.

One idea is that we can use different sequence numbers on each database:

• Even and odd id generation on different databases
• Have each id generated start with a prefix based on the database.

This is essentially a pre-sharding scheme as the number of databases will need to be known beforehand.

Given that we need 5 PB of data, assuming that we have a maximum of 50TB of data per machine, this means we need 100 machines. This accounts for the storage volume and the overall iops, given that we don’t have any hotspots. The memory and cpu also should be approximately the same as our previous analysis.

We have to handle 400k IOPS on average and 4m IOPs at peak for reads and writes. If we can avoid hotspots, each shard will need to handle \(4 x 10^6 / 1 x 10^2 = 4 x 10^4\) . Naively, we may be able to handle peak load, but this is something that would have to be performance tested. Alternatively, we can add caches to reduce the read load, which we’ll need to handle the hotspots in any case, and keep our shard count to the minimum required for disk space.

We still need to reconsider the number of network connections and the number of app servers that we have. Given 100 shards and assuming 20 tcp connections can handle the number of requests, for each app server we would need $tcp_connection_pool_count x db_shard_count = 20 x 100 = 2000 $ . On the database end, we have app_server_count * tcp_connection_pool_count = total_connections

The next step is to understand how many app servers we need. Previously, we calculated that we need 400 cores at peak, now we would need 40k. Given 40 cores per machine, that would be 1000 app servers needed. On each database, we would have 20000 active connections for the database pool. To solve this problem, we need to add an additional layer of abstraction. This would either be a consolidated database pool between application servers or we would have to pin a set of app servers to a set of database shards or we need to move this to the client side on the request and solve this via dns.

Need a diagram describing 3 states:

1. just sharded databases - how does the appserver go to the db for a particular hash?
2. dns lb
3. app pinning for certain urls

From the previous design, we know we need 100 shards of 50 TB. We can use the first 10-bits to represent 1024 shards, but only use the correct amount aka 100. Note that if we are using a database that represents its data as a binary tree, this will cause some write amplification on some inserts where the child pages need to be split. With a binary tree index, we are trading off random writes for easier reads. Because the hash is essentially random, the IO patterns will be mostly random, which is much slower than sequential. In fact, there are old bugs with mysql such that UUID insert performance decreases with the number of keys.

Unix-timestamp is 32-bit - which lasts from the year 1970 to 2038. Also, we can start our count from a custom epoch like 2018 instead of 1970.

We would like to include milliseconds which can be represented by 10 bits (\(2^{10} = 1024\))

64-bits total:

• 10-bits for number of shards = 2^10 = 1024 - random - we don’t want a bad hash - still can have hotspots.
• 42-bits for time in milliseconds = 70 years of time from custom epoch. We can possibly reduce the bits here since we don’t need 70 years.
• 12-bits = 2^12 = 4096 values per millisecond. We need to atomically increment a counter in some layer for this to work.

This design will allow 4k writes per ms per shard . Very conveniently, we previously calculated that we can increment a counter on a single machine around 3.5k/s. We can pre-shard to 1024 and distribute over 1 machine to start, then slowly ramp it up to n-machines as necessary.

Also, in addition to perhaps being a faster insert, another interesting property of this is that it is roughly ordered..

We can still make this design work by:

• batching out groups of 10 elements and doing the rest of the counting on the app servers
• having multiple id servers - 10 servers each serving id’s of mod 10.

Also, as a side note to get faster counters, we can do sloppy counting (equivalent of batching) per CPU and try to use the L1 cache, but most applications don’t need such a hard limit.

In this case, the number of writes > reads.

Questions - can we support the writes directly? If not, can we do batching? How accurate does the count need to be over what time? What is our maximum data loss? Introduction to CRDT - sum-only - eventually consistent.

• Affinity
• Split shards across regions and do replication across even/odd shard numbers
• Write queues and read caches (hub + spoke) model - could have issues with consistency
• How do you guarantee consistency at a latency of 25 ms? What happens afterwards?

Packed binary-coded decimal => 2 numbers can fit into 8 bits, one in the higher bits, one in the lower. Aside - BCD is generally advantageous to do digit by digit conversion to a string while binary representation saves 25% space. Can also assign different values to each bit - instead of 8/4/2/1 can have 8/4/-2/-1.