System requirements

Functional:

1. Users should be able to paste their text for a set period
2. Users should be given a link to their text
3. The content should be accessible for a set period.

Non-Functional:

1. The system should be available
2. The system should be reliable, and no text should be lost

Capacity estimation

DB:

Assuming the Size of text on average =50kb per paste

Assuming 100,000 pastes per day * 50 kb =5GB per day of storage

5GB *365 = 1.825TB of storage for text files in our data base.

Traffic:

Writes:

(100,000/(24*360))=1.16 pastes per second

1.16* 50 kb, roughly 60 kb per second for writes.

Reads:

Assuming 1:1000 read to write ratio:

60 kb*1000= 60 MB

Cache:

1.825TB * 0.2= 256 gb

API design

We will use REST API's

1. POST: create_paste(text) takes the text file as a parameter and returns 200 upon success and 500 if it fails. We will limit the amount of text based on the text box in the UI so as not to surpass the threshold.
2. Success Case : {status:200, message: paste link}
3. Error Case: { status: 500, message: error message}
4. GET: get_paste(url): takes the generated link as input and returns the text in the response message
5. Success Case : {status:200, message: pasted text}
6. Error Case: { status: 400, message: the link is invalid or expired}
7. Error Case: { status: 500, message: server error}

Database design

Since we assume the pastes are anonymous we don't need a users table. We will have one table for pastes as such:

Paste Info Table

1. Primary ID
2. paste_key -> 8 value char -> index for faster query
3. paste_url -> 8 value char-> index for faster query
4. created_at ->
5. expires_at -> index for querying expirated rows.

Paste Table: (Key value store such as S3)

1. Paste_key-> same
2. Paste Content

Since this is a heavy read operation we will use single leader replication. To address concurrency

We will repopulate the table with paste_key and paste_url. This will be created using MD5 hashing. We can take the first eight values of the hash as paste_key and the second 8 as paste_url. In concurrent writes, each write can grab a lock for each index, ensuring its thread is safe. We will not be creating the hash values upon write but prepopulating them.

To address deadlocks the locks will only lock the primary index which also serves as the paste_key and then move to paste_url so there is a lock_ordering. We can also add timeouts

To address expired rows we have created an index on the created_at field and can run a job every given period to detect old rows.

We will use file storage such as Amazon S3 for the paste themselves. The paste_key will serve as the key to the content of the paste. We are confident that we can horizontally scale a S3 service if needed.

To address latency between the leader node and follower nodes, we can use a quorum strategy to address the delay between followers not being updated.

High-level design

Scalability and fault general tolerance:

1. To prevent abuse of our system we can impose a rate limiter based on ip addresses and a bucketing strategy, we can have a higher number for read requests and lower number for writes. If users exceed this amount we can display a message letting them know. The bucketing strategy will prevent distributed types of attacks
2. All read/write requests go through a load balancer that distributes the load based on a server with minimum amount of load We can use a weighted approach to more effectively address the balancing. We will have multiple instances of our micro services to handle increasing load. The load balancer will distribute the load first via health checks and second by the load each server is having
3. We will use single leader replication and follower nodes will act as replicas.
4. The S3 bucket will automatically scale but we can have a backup of s3 with features like Amazon AWS back up as a service
5. To help with our read/write throughput we can implement consistent hashing to shard the database. Since our paste_key is a hashed value we can assume a somewhat even distribution amongst the shards and we won't have to worry about hot spots
6. To address expiration of old pastes we will run a job once a day to delete old records.Since expires_at is a key in our db this will be relatively easy.
7. Since the hashes are prepopulated there will be no cases of collisions during the write.To genrate hashes we can use a md5 hash since its cheaper and easier to generate.

Caching:

1. We can assume a 20% rule where 20% of the writes are generating most of the reads. 365gb can be allocated to cache size. If there is a cache miss the cache will be updated and will reallocate the content of the cache if there is a need.To purge the cache it makes sense to use a LRU approach.Redis can be a good choice here. That being said the number can be increased or decreased based on the access paterns and we can opt for a dynamic solution here.

Writes:

1. After being routed to a server via load balancer a thread can grab a lock on primary_id . To Ensure minimum dead locks we will utilize a time out strategy.
2. Writes will be written to the leader node, and the content of the paste will be copied to the S3 bucket. With the key as the paste_key. When both writes are succesful we can return a response to the user, with the paste url. To prevent discrepencies we can utilize a write ahead log to update our s3. The write ahead log will also help with too many loads

Reads:

1. After being routed to a server via load balancer we will first see the cache, we will implement a write around cache, since most of the writes are unlikely to be in the cache having a write around cache would make sense
2. If its a cache hit we return the response (paste url)
3. If its a miss we will look into follower nodes which will help with read throughput.
4. To minimize the latency between leader and followers we will use a qourom strategy.
5. If there is no content we will return a 400.

Request flows

Same as above high level design

Detailed component design

Same as above

Trade offs/Tech choices

1. SQL Although we have many writes and this could make a nosql db better, we don't want a multi leader type database.Which can disqualify mongodb and cassandra.Although infrequent choosing multi leader databases could yield inaccurate pastes and lead costumers to not trust the product.
2. S3 ideal for putting in paste content, provides additional benefits such as durability and auto scaling.
3. Populating the database with hash values for paste_url and paste_key allows the locks to process writes faster and reduce dead lock scenarios or potential race conditions.Furthermore it will reduce risk of hash collisions but can limit the users who want a customized url.
4. 
   

Failure scenarios/bottlenecks

1. Running out of hashes for our paste url
2. Data base goes down
3. Database gets large
4. Too many requests

Future improvements

1. We can use a larger hashing function to create more rows
2. Utilize a write ahead log to restore
3. We can horizantally scale with each node serving a range of hash values, we are also running jobs to clean our db after expiration.
4. If they are reads we can add more servers, if they are writes we need to scale our db and add more servers