Detailed Component Design

for unique id generation we'll use base62 encoding with 7 letters - that about 56 billion possible ids. the problem is what happens with multiple instances of the writer service. for that we can use the Redis cache to also store a global atomic counter. each instance would get a set amount of ids equal to a 1000 and update the counter when even the writer service reaches the 1000 and get 1000 more. in case of writer service failure we have redundancy of services and other writer service will share the load, but in general we would monitor the service and scale up or down when needed(usage above 80% and 20% accordingly). for scale we could add more letters by allowing the global counter to go even higher, and support up to 10 digits which is more than enough and still sits with our rough estimates.

the hot path of our system is the read path and it has to be as fast as possible. using a CDN near to the client to cache metadata and content of pastes with low TTL contributes to low latency and handles roughly 90% of the traffic since it stores the signed links. we will also use multiple reader services, just like for the writer service, to spread the load and provide high availability. again failure in one reader service spreads the load over the rest of the reader services. the reader service also utilizes the Redis cache that can hold all the metadata in it, again reducing latency to about 5-10 ms on a cache hit. in case of a cache miss we fetch the metadata from the postgres DB, fill the cache and return a response to the user.

again the key is an atomically incremented counter inside the Redis cache(which will also be backed up to the metadata DB). each access to the global counter ensures single access and increment for the accessing service. that way a range a specific writer service fetches is unique and never repeated again.

if a service crashes we loose those 1000 ids for good, but the address space is large enough for us to continue as usual. the keys are then ingested by the writer service to create a unique set of generated ids that are used, base62(num in received range, salt) which will guarantee uniqueness and prevent collisions.

the key could be made hard to guess using some random salt that would be saved along side the global counter, or alternatively use an obfuscation method.

the id of a paste is idempotent. upon request we would also receive a hash of the content(sha256) to store for a short time(10 minutes), write the hash to both the cache and the database the id has a constraint to be unique. if another request comes for the same request, meaning the same hash(timestamp is probably different, but content is not), we would check if the data already exists in both metadataDB and S3 by comparing checking if the metadata contains the same hash value. if so the status of the metadata with status PENDING means the user already received the presignedURL and uploads the paste so we would drop the request. otherwise we would continue to return a response to the user to continue with saving the data.

if multiple requests come in at the same time, the load is spread across multiple writer services, each with its own range of ids from the global counter(writer1 - 1000-1999, write2 - 2000-2999 and so on). each request atomically increments the local counter in each service, ensuring unique ids per request.

for the write path we are ok with eventual consistency, but we still want low latency. we receive a request from the user generate a unique,base62 encoded id, fetch a presigned URL from S3 and write the metadata to the metadata DB, then return a response to the user. we avoid handling large files by letting the user upload the data by themselves, reducing load from the system, the metadata written is roughly 100b, with 100 million users a day, and even distribution throughout the day thats 100M*100b/24h which is roughly 1Kb of data per second. both the writer service and the metadata database can handle both easily.

S3 is a cheap NoSQL database, that can hold all the data we need. the average document will be around 0.5Mb or even less, which fits easily in S3. the metadata for a single record is roughly 100b, and roughly 1M users create pastes each day - that is 0.1Gb per day and 36.5Gb a year which fits nicely in a single postgres instance even without deleting irrelevant pastes metadata, and we could store data for years ahead.

we do however want to shard the postgres and S3 by the id to avoid congestion of request to a single data base instance, another suitable variation is to keep the region of the created user and use that as the partition key because most probably that the paste is shared with people from the same region, which allows better latency and scalability.

the Redis cache can store all data for the same day in a single instance - 100b * 1 million metadata records is about 0.1GB. we could store multiple days in a single instance without any problem. since pastes can't be changed after creation we can use a mapping of id to metadata with a TTL value of 12 hours for the heavy reads, and with an LRU eviction policy. also using a redis cluster to handle redundancy in case of failure. the CDN will also use LRU eviction policy with a shorter TLL value of 10 minutes.

to avoid a cache stampede we would batch together requests for the same resource(metadata and data) and use request coalescing to send a single request to fetch the data and/or metadata. that way we avoid overwhelming the cache and the database. in case of a cache failure and unavailability response latency will go up to around 50ms from the metadata DB but will still be functional. we could rebuild the cache by prefetching popular pastes and data about pastes from the last 6 hours using another worker for that.

for rate limiting in the API gateway we'll use token backet strategy, limiting non-member users(based on IP) to 5 pastes per minute and member users to 20 pastes per minute.

hot keys are spread out through multiple shards ensuring balancing load of incoming traffic, they are also cached in the Redis cache and the CDN.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10