Detailed Component Design

Write Flow:

Whenever a user creates a paste, their request is routes to our write service. Here a unique 6 character string i.e. key is generated, this shall be our url_key. This is a unique key which shall be used to access the created paste.

The paste is then stored into AWS S3 object storage using signed url, in response we get a reference id. If the user has provided us with time to live i.e. expiration time, we shall provide that to S3 as TTL, that way we do not need to cleanup S3 manually. We then store the reference ID, url_key, create_at, user_id, incremental id, and expires_at (if provided by user) into DynamoDB.

If the user has provided us with time to live i.e. expiration time, we shall store it as TTL in DynamoDB for this created record. That way DynamoDB takes care of the deleting the record, again eliminating the need for manual cleanup service.

Once the whole process is done, we shall return the response to the user. We shall not cache the new paste i.e. we shall not use write-through cache, since this arises a danger that unused pastes flood our redis memory even though they aren't accessed. Since, we are storing complete pastes to our redis, this is very important.

Key Generation:

For key generation we could potentially think of maintaining a separate service for key generation. But this introduces race conditions, since multiple instances may get the same key, moreover keeping a single service will make it complex to horizontally scale the system in case of traffic spikes. Instead we shall use Snowflake algorithm (like twitter uses) to generate globally unique keys.

We shall generate 64 bit ID, which shall be ID = region_code + machine_id + sequencer + time_stamp. This gives us truly unique id for each instance of each region. We shall then encode this 64bit id to a Base62 encoded string. Since this is encoding and not hashing, it maintains the uniqueness of the key. This generated key shall be our url_key that we use in the write service.

Read flow:

Whenever the short url for the paste is clicked, first our CDN is hit, and the cached pasted is returned. If there is cache miss, the API gateway redirects the request to the read service.

Since our reads are high, we have separated read and write concerns how high availability and low latency. Here we do not hit the DynamoDB, instead we hit the cache and return the complete paste. In case of cache miss, then the read service requests the Dynamo DB for the for the object_reference_id and retrieves the paste from S3.

The whole response is then cached (since we are using cache aside policy) and then returned to the user. We include Cache-control headers, that way CDN caches this paste as well, hence next time this short url is hit, CDN can directly serve the paste.

CDN caching and internal Caching are the most important components of the read flow, since they reduce the DB hits and service hits by 90%.

We have put global index on the url_key, thus when eventually we do need to query the DB, we have fast data retrievals.

Deletion flow:

Whenever a user manually deletes the pastes, the request is routed to the write service again by the API gateway. The write service queries DynamoDB and gets the object_reference_id. The write service uses this object_reference_id to then delete the record from AWS S3, once done, the write service deletes the record from DynamoDB as well and returns 200 OK to the user.

We do not invalidate any caches since we have set TTL of 5 minutes, so eventually the caches will auto delete the records, thus eliminating the need for operational overhead.

We have put global index on the url_key, thus when eventually we do need to query the DB, we have fast data retrievals thus faster deletions.

We have kept all the components loosely coupled and eliminated SPOF , thus enabling easy horizontal scaling.

Tradeoffs:

We can get stale data momentarily from the caches since we do not manually invalidated caches upon expiry time or upon deletion. This may serve some stale data, but after TTL the system becomes eventually consistent. For a system like pastebin, this is acceptable.
We have used AWS S3 instead of storing blobs in DB directly. One could potentially store the pastes in DB itself, but that just puts operational and memory overhead on the DB.
We have used DynamoDB since it provides Global Tables and auto deletion of records after TTL. The tradeoff here is our system isn't immediately consistent globally since deletion and creation of records need time to sync globally. But since we need to make our system highly available with low latency, we can tolerate eventual consistency.
An issue the system might face is, in cases of cache misses, we query S3 and DynamoDB for data retrieval, then the app itself gives the complete pastes to the user. The issue here is the operational over heads, since this approach significantly increases our network bandwidth. Thus, if in case there is cache failure or huge amounts of cache misses, our read service can get overwhelmed. To counter this upto certain extent, we could horizontally scale the system.
Another issue is key generation. We are using Snowflake algorithm to generate unique ids and encode them into keys. The issue here is, with each instance we need to maintain a unique machine_id and sequencer for that machine. The sequencer increments for every request/ ms. This whole key generation gives us an operational over head.
An issue is, since in case of cache misses, there are a lot of calls made to services and DynamoDB. Then a big chunk of data is returned, thus high bandwidth. This is because our read service is returning the whole paste itself. In future we could instead return a signed URL from S3 (that has a small expiry) and return the signed URL itself. This arises a security concerns, since we are directly exposing an AWS S3 signed URL, but it should be fine in most cases, since the expiry time is short.

Concerns:

We take care of security by including authorisation and thus API key with each request. Using this, we implement rate limiting to prevent abuse. Moreover, we do not directly expose a signed AWS S3 url, instead the whole paste goes through our read service and then returned to whoever clicks the link. Thus, we built robust security and abuse prevention.
Using DynamoDB and AWS S3, provides us with durability, data loss prevention. For pastes in AWS S3 (our object store) we enable multi AZ replication, this ensure the pastes are almost never lost. For metadata in DynamoDB, we enable multi AZ replication. Moreover since we are using Global tables, we have data available globally and can be recovered, apart from this we enable PITR (Point In Time Recovery) to recover and minimise data loss.
In case of cache stampedes, Amazon CloudFront , our CDN comes into action. We implement longer TTL for hot items and stale-while-revalidate (serve stale while refreshing). For example our header would look like: Cache-Control: public, max-age=300, stale-while-revalidate=60, stale-if-error=600. Thus, even still, most of the traffic doesn't reach our app servers. Even after all this, in case our app servers get overwhelmed, we implement rate limiting allow requests at a healthy rate to prevent our app servers' health.
Our snowflake algorithm guarantees unique keys, but not necessarily hard to guess keys. For this, the solution is to encode the snowflake ID that we generate in base 62, BUT with a unique salt. This breaks sequential generation of keys and increases unpredictability.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10