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 (SQL Database)

Primary ID
paste_key -> 8 value char -> index for faster query
paste_url -> 8 value char-> index for faster query
created_at ->
expires_at -> index for querying expirated rows.

Paste Table: (Key value store such as S3)

Paste_key-> same
Paste Content

MongoDB (NoSQL document database) is preferred for a fitness tracking app because it excels at handling dynamic, structured data with frequent updates and complex query needs. (Fitness app data (workout logs, user progress, and goals) is naturally represented as documents with structured fields. MongoDB stores data in a JSON-like format (BSON), which makes it easier to work with complex data structures and perform rich queries)

Amazon S3 (Object storage service) is optimized for storing and serving static, large objects and doesn't provide the rich query capabilities or flexible update mechanisms that a fitness app requires.

(

Paste content is essentially unstructured data (text or binary blobs) that fits naturally into objects stored on S3
Pastes are static content that, once written, do not change frequently. S3 is optimized to serve static files quickly, and it integrates seamlessly with CDNs for global distribution.

)

Since this is a heavy read operation we will use single leader replication(all writes go to the leader node, read replicas (followers) can be horizontally scaled to handle heavy read loads).

To address concurrency

We will repopulate the table with paste_key and paste_url.

"repopulate" means that for each new paste entry, you generate (or calculate) the paste_key and paste_url for that new record and then add that entry to the table—rather than re-generating or rewriting the entire table with every write

This will be created using MD5 hashing. (Rather than waiting for the user to finish writing the paste and then hashing the complete text, the system precomputes a pool of MD5-generated hash pairs. This means the MD5 algorithm is applied to some predetermined input (like a sequence number, counter, or a random seed) ahead of time. These precomputed values are then stored and ready to be assigned as new pastes are created.)

We can take the first 8 values of the hash as paste_key and the second 8 as paste_url. We will not be creating the hash values upon write but pre-populating them.

In concurrent writes, each write can grab a lock for each index, ensuring its thread is safe.

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

Lock Acquisition on Indexes:

Primary Lock First (paste_key):
Every write operation first acquires a lock on the primary index (paste_key). This ensures that each paste gets a unique primary key in a thread-safe manner, preventing conflicts on the primary identifier.
Secondary Lock (paste_url) Next:
Once the lock on the primary index is acquired, the write operation then proceeds to acquire the lock on the secondary index (paste_url).

Enforcing Lock Ordering to Prevent Deadlocks:

Deadlocks often occur when different transactions lock shared resources in different orders (e.g., Transaction A locks paste_url first, while Transaction B locks paste_key first). To avoid this, the system enforces a strict ordering: always lock the primary index (paste_key) first and only then lock the secondary index (paste_url).
By ensuring all writes follow the same lock acquisition order, the possibility of cyclic waits (where each transaction waits for the other to release a lock) is greatly reduced or eliminated.

Timeouts to Further Prevent Blocking:

In high-concurrency situations, if a transaction is unable to acquire the necessary locks (because another transaction holds them), the system can apply a timeout. This means that if a write operation cannot get the lock within a specified period, it will be aborted or retried.
The timeout mechanism prevents any single write operation from waiting indefinitely for a lock, which helps keep the system responsive.

If you choose to use just the paste_url as the key—eliminating the separate paste_key—you simplify the schema, but you may lose some benefits:

Separation of Concerns:
- Internal vs. Public Identifier:
- Having separate identifiers (paste_key internally and paste_url externally) decouples the internal data management from what users see. The internal paste_key can change behind the scenes without affecting public URLs.
- Flexibility:
- With two keys, you can change how you generate or update one without impacting the other. Using a single key ties your internal representation directly to the public value.
Concurrency and Locking:
- In the two-key design, you can enforce a lock ordering (first on paste_key, then on paste_url) during concurrent writes, which helps avoid deadlocks.
- With only one key, all operations would lock on the same field, which might increase contention and reduce concurrency because every write operation is serializing on a single lock.
Performance:
- Having separate indices for internal operations and public lookups allows you to optimize each independently. With just paste_url, you have to ensure that this one index is optimized for both fast writes and fast lookups by users.

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.

A quorum strategy can help mitigate the effects of this latency on read and write operations in the following ways:

Write Operations:
- When a write is issued, the system doesn’t wait for every single node to update before confirming the write.
- Instead, the write is considered successful after receiving acknowledgments from a quorum (a majority) of nodes.
- This means you only need to wait for a subset of nodes (for example, 3 out of 5) rather than all nodes, thereby reducing the write latency impact caused by slow followers.
Read Operations:
- For reads, instead of fetching data from a single node (which might be lagging), the system queries a quorum of nodes.
- The read operation aggregates responses from enough nodes so that at least one of them has the most recent update.
- By ensuring that the read quorum overlaps with the write quorum (i.e., they share at least one node that was updated by the last write), the system provides a more consistent (fresh) view of the data, even if some nodes are delayed.
Balancing Consistency with Latency:
- The quorum strategy helps balance the trade-off between low latency and strong consistency. You accept that not all nodes are instantly updated, but by requiring a quorum on reads, the system ensures that the read result will include the latest committed change from a majority of nodes.
- This way, even if some followers are delayed, the system waits for enough nodes to respond—thus reducing the chance of returning outdated information.

Let's assume you have 5 nodes labeled 1, 2, 3, 4, and 5. A common quorum configuration is to set both the write quorum (W) and read quorum (R) to 3, ensuring that:

R+W>5(3 + 3 > 5)

This guarantees that the read and write quorums will have at least one node in common.

Example Configuration

Write Quorum:

Suppose you require that nodes 1, 2, and 3 must acknowledge a write before it’s considered successful.
That is, when writing, the system will wait for confirmation from nodes 1, 2, and 3.

Read Quorum:

For reading, you could query nodes 3, 4, and 5.
This means that when performing a read, the system gathers responses from nodes 3, 4, and 5 and uses the overlapping data (node 3 in this case) to ensure that it reflects the latest committed write.

Why This Works

The overlap between the write and read quorums (node 3, in this case) ensures that at least one of the nodes being read has the most recent write.
This helps mitigate replication latency because even if some nodes are delayed, the common node in the overlapping quorum will reflect the latest update.

Note:

if one node (for example, node 3) is slow, overloaded, or temporarily unavailable, the system might choose another set of nodes (like 2, 4, 5 )

What matters is that any read quorum you form must intersect with the write quorum such that at least one node has the most recent update

Submissions

Displaying Solutions with Scores Ranging from 1 to 10