Requirements

Functional Requirements:

• Allow users to upload and store text or code snippets.
• Generate a unique shareable URL for each paste.
• Enable retrieval of paste content by URL.
• Support expiration and TTL for pastes.
• Allow paste owners or the system to delete a paste before its natural expiration.

Non-Functional Requirements:

• Scalability: The application should be scalable. The number of reads would be far greater than number of writes. We can assume that the system should handle 1M daily writes and 2M daily reads from users. The DAU can be around 4M. The number of DB Queries for writes (notes + url): 1 + 1 = 2. Thus for 1M writes per day: we should have 2M writes per day = 2M/86400 = approx: 20QPS
• Then number of reads are much higher, can be double of write QPS: 40QPS.
• Availability: The system should be highly available, since users prefer to get the access and read more often than edit/ create uploads.
• Eventual Consistency: Since the system is preferred to be highly available, consistent hashing can be used for eventual consistency.
• CAP theorem tradeoff: Availability over consistency.
• Reliability: The notes uploaded/ read should not be changed apart from the author or the person who has access to the particular upload.
• Security: The notes uploaded should be encrypted at rest so that the uploads are not leaked accidently from the db. PII data should be hidden in flow of requests as much as possible.
• portability: The system should be able to work in android, ios as well as website.

API Design

1. POST /api/v1/paste Auth: Bearer <token(contains user uuid)> payload: s3Url for each chunk, metadata for each chunk. response: 201 Created (success) 400, 401, 403 (failure)
2. GET /api/v1/paste/{id} get the content by id (200 OK) client side failures: (404, 401, 403)
3. DELETE /api/v1/paste/{id} : delete by id 200 OK, 401, 403, 404

High-Level Design

1. Client: Can be website, ios or android.
2. Load Balancer: Traffic management as well as forwarding request to the correct micro service based on request path
3. Core Components: 1. PasteBox Service: Takes the input from the user and stores them in the DB. 2. Key Generation Service: Generated a unique id based on the uploaded notes , so that url generation becomes easier. this unique key is then stored in the KeyGeneration DB.3. S3: multipart upload of notes/ other uploads using the concept of pre-signed urls.
4. Database used: NoSql DB for pasteBin due to high availability (Mongo DB) following master-slave architecture with slaves being for reads and writes only to the master. consistent Hashing used for eventual consistency betwee n the master and the slave.
5. Key-Value based DB like Dynamo DB for storing the urls and the pasteBin unique id. Better scalabilty than rdbms.

Detailed Component Design

1. Load Balancer: We will place a network load balancer so as to filter the packets at layer 4 level and protect our system from network attacks such as TCP sync attack or UDP overflow.
2. API Gateway will handle auth, rate limiting and cache responses as required. Rate limiting will be using the tocken Bucket algorithm with 60 requests/ sec per user. If the reate of requests exceed, 429 will be returned to the user from the api gateway itself. The allowed rate can be increased for subscribed and premium users.
3. CDN: To improve P95 and P99 latency, we can cache the results in CDN, thus ensuring ultra low latency at edge locations.
4. Cache: Redis is used as a cache to store the unique keys and primary key mapping of pasteBin DB. It also has the mapping of chunkId and respective mapping of the S3 url where the chunk is stored, with a TTL of 10min. Follows LRU Cache eviction policy. Write through policy followed for writing in cache, and Cache aside policy followed for reads.
5. PasteBin Service: Handles the fetching of presigned s3 urls for each chunk for multi part upload, and DB look up for metadata of each chunk. This can be made highly available by having more than one instance in more than one availability Zone using Auto scaling groups.
6. Key generation Service: Generates a unique key for each upload, there by storing the mapping of one key to the primary key of the PasteBin DB.Computes the hash of the incoming primary key and the timestamp to generate the hash, thereby avoiding collisions. the first 20 characters are used for the unique key, there by having a total of 20 raised to 20 combinations.
7. S3 is used for object store as the file size of upload might be in MB or GB, thus cannot be stored in DB. Lifecycle policies can be used to optimize cost. A server less architecture comprising of S3, event bridge, SQS and lambda combination can be used to populate the metadata in the PasteBin DB asynchronously.

Tradeoffs:

1. Single point of failure: Load Balancer can act as a single point of failure, thus we need to make it highly available by having 3 backups in multiple availability zones and regions, thus making disaster recovery possible.
2. Concurrent writes: When two users are actively editing the doc, then all the edits should be saved in a buffer, and then after a timeout, the updates should be sent in batches, in order to minimise network calls.
3. Eventual Consistency: Since the sytem is highly available, if another user immediately opens the generated link, then the recent edits might take time to show (4 to 5s). This can be improved by making our system write optimised and using DB such as Cassandra where Leaderless principle is used, as opposed to MongoDB (which uses Master-Slave)
4. Cache TTL: The stale data might be visible in cache for TTL of 10min, thus cache should be updated everytime there are new edits.

Additions:

1. We can run a schedular job ,where a worker queries the DB every 15min to check the content which has reached its expiration, and can delete such content from the DB, thus making some space free. This can be server less as well.
2. We can use a message queue like Kafka between the PasteBin service and Key generator service inroder to decouple the application, by making them publishers and consumers of respective topics, thus making scalability easier.
3. Another advantage of adding Kafka is that, even though the DB goes down temporarily, Kafka will have the data retained for 1 week, thus giving us ample time to run the script to populate the DB async.
4. To prevent Cache stampede, we can pre fill the cache with the most common/ required data from the DB on boot up/ when the cache node restarts.
5. In order to deal with hot Keys, the cache can be distributed into a cluster, where each cache will have the details about the hot key.
6. Celebrity problem: When a particular user has a very popular upload, where many reads are occurring, the content can be cached in CDN itself, thereby reducing the load to DB and cache.
7. Problematic IPs and hazardous IPs can be blacklisted by adding a WAF in front of the Load Balancer to prevent network attacks from bots/ malicious users.
8. Regex pattern matching can be implemented in api gateway to prevent XSS and SQL injection attacks.
9. POST api should be idempotent in nature, in order to prevent duplicate entries in DB and S3, thus saving cost.
10. On API failure in internal services, there should be a maximum of 3 retries. Since message queues are used in between services, retries are possible since request/ job wont be deleted from the queue. Upon successful processing of the request/ job, it can be removed from the queue.
11. On network failures of DB/ Cache/ Internal micro services, circuit breaker pattern should be used in the micro services in order to reduce the number of network calls. Timeout should be set to 1 min, where a scout is sent every 1min to check the network health of the target.
12. For generating a unique key, there might be an edge case where 2 keys would be same, for this, a distributed counter shuld be appended to the hashed value and rehashed using a salt value.
13. Read replicas should be created for databases. The PasteBin DB can be and RDBMS / Sql DB like postgres for storing metadata of the uplaods that includes chunkId, expiration_timestamp, id (PK) and S3 url. Key Generator DB can be a key value store like dynamo DB for high availability and scalablity.
14. Sharding strategies for RDBMS table: the Db should be shared based on the Id of the row. Consistent hashing should be used for sharding, so that only the affected rows withing the updated row is reconfigured, there by reducing the number of re arrangements.Partitioning based on mod of id should be implemented within the same shard.

PS: many of the details which should be there in HLD have been included in detailed component design XD idk why I did this, open for suggestions in the comments