TJ’s Completely Professional Guide to Building Sh*t (Software and Systems)

We’re expecting a billion urls a month. Let’s make a few additional 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 \(10^5\).

Initial estimate ¹²¹²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.

Year	\(1\)	\(10\)
Total urls / year	\(12 \times 10^9\)	\(12 \times 10^9\)
Cumulative urls	\(12 \times 10^9\)	\(12 \times 10^{10}\)
Total uncompressed storage	\(500 \times 12 \times 10^9 = 6 \times 10^{12}\)	\(60 \times 10^{12}\)
Total compressed storage	\(3 \times 10^{12}\)	\(30 \times 10^{12}\)
Writes / second	\(10^9 / 10^5 / 30 = 333\)	\(333\)
Reads / second (100x writes)	\(3333\)	\(3333\)
IOPS / second	\(4000\)	\(4000\)

100x ¹³¹³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.

Year	\(1\)	\(10\)
Total urls / year	\(1.2 \times 10^{12}\)	\(1.2 \times 10^{12}\)
Cumulative urls	\(1.2 \times 10^{12}\)	\(12 \times 10^{12}\)
Total uncompressed storage	\(600 \times 10^{12}\)	\(6 \times 10^{15}\)
Total compressed storage	\(300 \times 10^{12}\)	\(3 \times 10^{15}\)
Writes / second	\(10^{11}/ 10^5 / 30 = 33 \times 10^{3}\)	\(33 \times 10^3\)
Reads / second (100x writes)	\(333 \times 10^6\)	\(333 \times 10^6\)
IOPS / second	\(350 \times 10^6\)	\(350 \times 10^6\)

Each placement of the component generation generates a different tradeoff if we want to guarantee uniqueness.

• client-side - From a security perspective, clients can send what they want, so that means we may need to implement collision handling or use some other method to guarantee uniqueness.
• app server - This would likely be implemented as a library which is fine for single-language systems.
• database - Scaling is limited by the database if we are using the primary keys / auto-increment
• other system - An extra system specialized for id generation requires extra maintenance and we’re trading extra network latency for the ability to use the same service across many languages/systems and the ability to scale this independently. ¹⁴¹⁴Not many cases where this makes sense - twitter and high-frequency trading are possibly two.

On top of that, there are a few ways to generate a unique id:

• randomness ¹⁵¹⁵This could be slow or we could run out of random bits.
• monotonically increasing or random UUID’s
• hash of the URL
• hash of the URL with additional bits (time or randomness)

And in all cases, we finally need to be able to turn the id into something user-friendly enough that it can pass for a short url.

For our system to work, we need to be able to have a bi-directional mapping from the id to a short-url and back. If we had a unique id for the long url, a simple idea encode the id into a shorter identifier. Naively, we can hash the long url to create an unique id. ¹⁶¹⁶Some common hashes are MD5 or SHA which use a 128-bit address space. An md5 is of the form 7a4c751fa75da88f57e215562f9e1063 and contains 32 characters which each 16 bits. Most UUID libraries also generate 128-bit. There are shorter hashes that are more applicable to our problem.

We can use base conversion to change form of the representation. Assuming we’re using a hash like md5 our id is 128-bits and we need to figure out the appropriate encoding so the short url is less than 10 characters. ¹⁷¹⁷We know base16 encoding gives length 32. A sequence of 128 bits (values of either 0 or 1) can be represented by a sequence of 32 characters between [0-9a-f] which represent \(2^4\) values. So we can group the 128 elements into groups of 4. This would be 32 groupings. In mathematical terms, \(2^{128} = (2^{4})^{32}\) A base62 encoding uses the alphanumeric characters [a-zA-Z0-9] which would satisfy the ease of use requirements. Estimating the length with a base64 representation of 128 bits would give a length of \(2^{128} = (2^6)^l\) . Taking \(log_2\) of each side, \(l = 128/6 ~= 21\). Even in base64 representation, a 128-bit id will give a length of 21 characters which is far too long for a short url and base62 would be slightly longer.

Luckily, we only need to make sure that we can store \(10^{13}\) in the worst case scenario of 100x more traffic. ¹⁸¹⁸No, we don’t need a calculator.

• 10 characters of base32 gives \((2^5)^{10} = 2^{50} = (2^{10})^5 = (10^3)^5 = 10^{15}\) total urls.
• 10 characters of base64 gives \((2^6)^{10} = 2^{60} = (2^{10})^6 = (10^3)^6 = 10^{18}\) total urls.

We should also calculate the maximum address space available to us for 10 elements/characters for usability. Since \(2^{10} \approx 10^{3}\), we need a total of

\[10^{13} = 2^{10} * 2^{10} * 2^{10} * 2^{10} * 10 ~= 2^{44}\]

This means we need approximately 44 bits of address space to store all of our URLs over the lifetime of the system. These 44 bits in base32 and base64 encoding can be represented by:

• \(10^{13}\) in base32 -> \(10^{13} = 2^{44} = (2^5)^x\) . After taking \(log_2\), x ≈ 9 elements.
• \(10^{13}\) in base64 -> \(10^{13} = 2^{44} = (2^6)^x\) . After taking \(log_2\), x ≈ 8 elements.

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

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

The simplest possible design is to use a relational database like Postgresql or Mysql to autoincrement an id and then encode it into a short url. Generally, using an RDBMs for the first phase of the application lifecycle works pretty well. ²⁰²⁰Now, you might be thinking, well, I can use a NOSQL database like DynamoDB or Cassandra and then I can totally scale forever! But not quite. Alas, this section is the pre-cursor to sharding, but most of these databases have shards and you have a limit on the IOPS on each of these shards. For DynamoDB, you used to have a global IOP limit that is divided equally over all the shards. So, if you have a particularly hot set of keys that are pinned to a shard, your performance will be in shambles or cost you an arm and a leg. Been there, done that. Anyway, the whole point is to be able to understand the limits of the databases and understand the pitfalls rather than experiencing them first-hand.

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.

But what are the other limits? When will this design fail? Can we use a single database and expect it to work? We need to examine the cpu, network, and storage, and IOPS requirements.

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.

For the storage layer, if we’re using AWS, 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.²¹²¹Which, from when I tested way back when, doesn’t really work. The total storage over 10 years is approximately 60 TB. But, hopefully, having 5 such volumes would work. So from a IOPS and disk storage can be managed on a single machine.

From Aurora benchmarks, a machine can do 100k writes/s and 500k reads/s with a r3.8xlarge with 32 cores and 244 GB memory. We can probably do a smaller size and manage our peak read/write capacity of 40k. 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 replicating, this should not be an issue.

The app server should only take a few ms to parse the user request and send it off to the database. At that point, we’re hopefully in an epoll loop ²²²²Select, poll, and epoll are three different ways to handle IO requests in the kernel. Edge-polling (epoll) was an evolutionary step in scaling up the amount of concurrent requests can be handled. I was going to initially say file descriptors, but then my footnotes will need footnotes.. 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.

So, for the initial requirements, this is the simplest design and the least amount of cost from a development and maintenance perspective.

But how would we scale this up?

Now there are a few things to know before we start, namely how all these servers connect to each other. You see, a single application server has a set of 10-20 connections it opens to the database. This is what we call a database connection pool. If you have 100 concurrent connections on the application server, each of them will time-slice the usage of the database pool. Of course, we can actually tie up the usage of the entire database connection pool with long queries, and then 80 of our clients will have to wait.

So one of the simpler ideas is to have each id generated based on a pre-selected prefix based on the database. This is essentially a pre-sharding scheme as the number of databases will need to be known beforehand. If we have 100 databases, we can prefix our generated id with the numbers 001-100 and continue using the unique id generated by the db.

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

This design requires a 3rd system to generate the ids rather than the app server or database.

So where’s the limit on this? Likely it will be if we can increment fast enough.

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.

The real question in this design is how do we ensure that multiple application servers can generate unique ids? Because our only requirement is that we’re shortening urls and they are public, we can just use the hash of the url and encode it. But if we also wanted to offer the users a count of times it was used, we would have to make these unique, but we have a few bits to spare.

This was the shared nothing design where we could use a 64-bit hash. However, we can actually do better than a hash.

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..

This was having a 3rd system to generate the id.

In this case, in our worst case scenario of 100x traffic x 10x peak, we’d have 333e3 requests per second.

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.