Free lesson · System Design Interviews

Step 5: Database Design

Hard11 min readsystem-designinterview-prep

Database design for Pastebin is where you have to resist the instinct to put everything in one table. The critical insight - and the thing I look for when I ask this question - is that content and metadata are different data types with different access patterns, and they deserve different storage engines. The metadata goes in PostgreSQL. The content goes in S3. The paste ID is the bridge between them.

But there's more nuance here than just "use S3 for blobs." The metadata schema design, the paste ID generation strategy, the expiration cleanup mechanics, and the interaction between S3 and the database all matter. Let me walk through each decision.

The Metadata Schema

CREATE TABLE paste_metadata (
    id                  BIGSERIAL PRIMARY KEY,
    paste_id            VARCHAR(8) NOT NULL UNIQUE,
    title               VARCHAR(255),
    language            VARCHAR(50) DEFAULT 'text',
    content_size        INTEGER NOT NULL,                -- Bytes (original, uncompressed)
    compressed_size     INTEGER NOT NULL,                -- Bytes (gzip compressed, as stored in S3)
    s3_key              VARCHAR(100) NOT NULL,           -- S3 object key: "pastes/x7Kf2mBp"
    content_hash        CHAR(64) NOT NULL,               -- SHA-256 of content (for deduplication)
    visibility          VARCHAR(10) DEFAULT 'unlisted',  -- public, unlisted
    delete_token_hash   CHAR(64),                        -- SHA-256 of the delete token
    creator_ip          INET,                            -- For abuse detection
    created_at          TIMESTAMP NOT NULL DEFAULT NOW(),
    expires_at          TIMESTAMP,                       -- NULL = never expires
    deleted_at          TIMESTAMP,                       -- Soft delete timestamp
    
    -- Indexes
    INDEX idx_paste_id (paste_id),
    INDEX idx_expires_at (expires_at) WHERE deleted_at IS NULL,
    INDEX idx_content_hash (content_hash),
    INDEX idx_created_at (created_at)
);

Column-by-Column Design Decisions

paste_id (VARCHAR(8), UNIQUE)

The user-facing identifier. 8-character Base62 gives 218 trillion codes - effectively infinite for 5 million pastes per day. Like URL Shortener, I'd use an integer primary key for index efficiency and keep paste_id as a separate indexed column.

Why not use the paste_id as the primary key? Same reasoning as URL Shortener - integer primary keys produce smaller, more cache-friendly B-tree indexes. At 150 million active records, index size matters. An 8-byte integer PK versus a variable-length string PK means roughly 40% smaller indexes.

content_size and compressed_size (INTEGER)

Storing both the original and compressed sizes serves multiple purposes:

s3_key (VARCHAR(100))

The pointer from metadata to content. The format is pastes/{paste_id}. Storing this explicitly (rather than computing it from paste_id) means you can change the S3 key structure in the future without updating application code - just update the stored key.

In practice, this column might seem redundant - why not just compute pastes/{paste_id} at runtime? The reason is operational flexibility. If you ever need to migrate content to a different bucket, reorganise the key structure (e.g., partition by date: pastes/2026/06/x7Kf2mBp), or store some content in a different storage class, the explicit S3 key lets you do that per-paste without changing the application.

content_hash (CHAR(64))

SHA-256 hash of the original content. This serves two purposes:

1. Content deduplication (optional). If two users paste the exact same content, you can detect it and store the content once in S3, with both metadata records pointing to the same S3 key. At 5 million pastes per day, deduplication could save 5-15% of storage. Whether it's worth the complexity depends on your storage costs.

2. Content integrity verification. When serving content, you can verify the hash to ensure the content hasn't been corrupted in S3. This is defence-in-depth - S3 has its own integrity checks, but belt-and-suspenders is appropriate for user data.

def create_paste_with_dedup(content, **kwargs):
    content_hash = hashlib.sha256(content.encode()).hexdigest()
    
    # Check if identical content already exists
    existing = db.query(
        "SELECT s3_key FROM paste_metadata WHERE content_hash = %s LIMIT 1",
        content_hash
    )
    
    if existing:
        # Reuse the S3 object - just create a new metadata record
        s3_key = existing.s3_key
    else:
        # New content - upload to S3
        s3_key = f"pastes/{paste_id}"
        s3.put_object(
            Bucket="paste-content",
            Key=s3_key,
            Body=gzip.compress(content.encode())
        )
    
    # Create metadata record (always new, even if content is deduped)
    db.execute(
        "INSERT INTO paste_metadata (paste_id, s3_key, content_hash, ...) "
        "VALUES (%s, %s, %s, ...)",
        paste_id, s3_key, content_hash
    )

Interview: What to say: "I'd store a SHA-256 hash of the content for optional deduplication. If two users paste the same content, I can detect the duplicate and point both metadata records to the same S3 object. At 5 million pastes per day, realistic dedup savings are 5-15%. I wouldn't implement dedup from day one - I'd add it when storage costs justify the complexity. But having the hash in the schema from the start means I can add it later without a migration."

expires_at (TIMESTAMP, nullable)

NULL means the paste never expires. A non-NULL timestamp means the paste expires at that time. The partial index WHERE deleted_at IS NULL on this column ensures the cleanup worker's expiration query is fast - it only scans active (non-deleted) pastes.

deleted_at (TIMESTAMP, nullable)

Soft delete. When a user deletes their paste (via delete token) or the cleanup worker removes an expired paste, this field is set to the current timestamp. The paste metadata is retained for 30 days after deletion (for audit/debugging), then hard-deleted by a separate cleanup process.

Why soft delete instead of hard delete? Because it allows:

• Returning 410 Gone instead of 404 Not Found for deleted pastes
• Auditing deletion patterns (detecting abuse)
• Recovery from accidental deletions (within the 30-day window)
• Gradual cleanup that doesn't cause large transaction log spikes

Index Design

-- Primary lookup for viewing pastes (used on every read)
CREATE UNIQUE INDEX idx_paste_id ON paste_metadata (paste_id);

-- Cleanup worker query: find expired, non-deleted pastes
CREATE INDEX idx_expires_cleanup ON paste_metadata (expires_at)
    WHERE deleted_at IS NULL AND expires_at IS NOT NULL;

-- Content deduplication lookup
CREATE INDEX idx_content_hash ON paste_metadata (content_hash);

-- Chronological listing (if we add a "recent public pastes" feature)
CREATE INDEX idx_created_at ON paste_metadata (created_at)
    WHERE visibility = 'public' AND deleted_at IS NULL;

The partial indexes (WHERE deleted_at IS NULL) are critical for performance. Without them, the cleanup query would scan the entire table - millions of already-deleted rows - to find the ones that need cleanup. With partial indexes, it scans only active records.

Tip: Partial indexes are a senior signal. Most candidates create basic indexes. Mentioning WHERE deleted_at IS NULL on the expiration index shows you understand that the index should only cover the working set, not the entire table. This is a production optimisation that comes from operating databases at scale.

Paste ID Generation

The same three approaches from URL Shortener apply here, with the same trade-offs:

For Pastebin, I'd recommend random generation with collision check, and here's why it's different from URL Shortener:

Pastebin has 50 writes/sec (vs URL Shortener's 1,000 writes/sec). At 50 writes/sec, a collision check against the database is cheap - the UNIQUE index on paste_id makes it a single B-tree lookup. The counter range infrastructure that was justified at 1,000 writes/sec is over-engineering at 50 writes/sec.

import secrets
import string

def generate_paste_id():
    """Generate an 8-character Base62 paste ID."""
    alphabet = string.ascii_letters + string.digits
    return ''.join(secrets.choice(alphabet) for _ in range(8))

def create_paste(content, **kwargs):
    for attempt in range(5):
        paste_id = generate_paste_id()
        try:
            db.execute(
                "INSERT INTO paste_metadata (paste_id, ...) VALUES (%s, ...)",
                paste_id
            )
            return paste_id
        except UniqueViolation:
            continue  # Collision - retry (extremely rare with 218T code space)
    
    raise Exception("Failed to generate unique paste ID after 5 attempts")

At 50 writes/sec and 218 trillion possible codes, the probability of a collision on any given attempt is essentially zero until you've created billions of pastes. Even at year 5 (9 billion pastes), the collision probability per attempt is 9B / 218T = 0.004%. You'll retry approximately once every 25,000 pastes - imperceptible.

Interview: What to say: "For Pastebin, I'd use random ID generation with a collision check against the UNIQUE index. At 50 writes per second, the collision check adds <1ms - unlike URL Shortener at 1,000 writes/sec where I'd use counter ranges to avoid the check entirely. The random approach gives me unpredictable URLs without the complexity of counter range infrastructure. At 218 trillion possible 8-character Base62 codes, collisions are astronomically rare."

Content Storage in S3 - The Schema Complement

While the metadata schema lives in PostgreSQL, the content "schema" lives in S3. Let me detail the S3 object structure:

S3 Object Layout

Bucket: paste-content
Region: us-east-1

Object key: pastes/{paste_id}
Content-Type: text/plain
Content-Encoding: gzip
Metadata:
  x-amz-meta-language: python
  x-amz-meta-original-size: 10240
  x-amz-meta-content-hash: sha256:a3f2b1...

Lifecycle rules:
  - Transition to S3-IA after 30 days
  - Transition to S3 Glacier Instant Retrieval after 365 days
  - Delete objects with tag "expired=true" immediately

Why Flat Key Structure (Not Date-Partitioned)?

You might consider organising S3 keys by date: pastes/2026/06/14/x7Kf2mBp. This helps with listing objects by date range and can improve S3 partition performance. But for Pastebin:

Since we always look up pastes by ID (never by date range), and the paste ID is the only information in the URL, the flat structure is simpler. The cleanup worker uses the PostgreSQL metadata to find expired paste IDs, then deletes the corresponding S3 objects - it doesn't need to list objects by date in S3.

Content Compression Details

All content is stored gzip-compressed in S3:

import gzip

def store_paste_content(paste_id, content):
    compressed = gzip.compress(content.encode('utf-8'), compresslevel=6)
    
    s3.put_object(
        Bucket="paste-content",
        Key=f"pastes/{paste_id}",
        Body=compressed,
        ContentType="text/plain",
        ContentEncoding="gzip",
        Metadata={
            "x-amz-meta-original-size": str(len(content.encode('utf-8'))),
            "x-amz-meta-language": language
        }
    )
    
    return len(content.encode('utf-8')), len(compressed)

Compression level 6 (the default) gives the best balance of compression ratio and CPU time. Level 9 compresses slightly better but uses 3x more CPU. For text content, the difference between level 6 and 9 is typically 1-3%.

Content Deduplication Deep Dive

Deduplication is an optional optimisation, but it's worth discussing because it shows database-plus-storage design thinking.

flowchart TD
    NEW_PASTE["New paste content"] --> HASH["Compute SHA-256 hash"]
    HASH --> LOOKUP{"Hash exists in<br/>paste_metadata?"}
    
    LOOKUP -->|"No - new content"| UPLOAD["Upload to S3<br/>as pastes/{paste_id}"]
    UPLOAD --> META_NEW["Create metadata with<br/>s3_key = pastes/{paste_id}"]
    
    LOOKUP -->|"Yes - duplicate content"| REUSE["Reuse existing S3 object<br/>s3_key = pastes/{existing_id}"]
    REUSE --> META_DUP["Create metadata with<br/>s3_key = pastes/{existing_id}"]
    
    NOTE["Two metadata records,<br/>one S3 object.<br/>Saves storage but adds<br/>deletion complexity."]

Content deduplication flow. When a new paste is created, the system computes a SHA-256 hash of the content and checks if any existing paste has the same hash. If no match is found, the content is uploaded to S3 normally. If a match is found, the new metadata record reuses the existing S3 object - no new upload is needed. This means two metadata records share one S3 object, saving storage. However, this adds complexity to deletion - you can't delete an S3 object when one paste is deleted if another paste still references it. A reference count or an existence check is needed before S3 deletion.

The deletion complexity with deduplication:

If two pastes share the same S3 object, deleting one paste must NOT delete the S3 object - the other paste still needs it. This requires reference counting:

def delete_paste_with_dedup(paste_id, delete_token):
    # Verify delete token...
    
    paste = db.query("SELECT s3_key, content_hash FROM paste_metadata WHERE paste_id = %s", paste_id)
    
    # Soft-delete the metadata
    db.execute("UPDATE paste_metadata SET deleted_at = NOW() WHERE paste_id = %s", paste_id)
    
    # Check if any other active paste references the same S3 object
    ref_count = db.query(
        "SELECT COUNT(*) FROM paste_metadata "
        "WHERE content_hash = %s AND deleted_at IS NULL AND paste_id != %s",
        paste.content_hash, paste_id
    )
    
    if ref_count == 0:
        # No other references - safe to delete S3 object
        s3.delete_object(Bucket="paste-content", Key=paste.s3_key)

This is why I said deduplication is optional - it saves 5-15% of storage but adds meaningful complexity to the deletion path. At $0.023/GB/month for S3, the storage savings at year 1 are roughly $20-40/month. Unless you're at massive scale, the complexity isn't justified.

Warning: Don't over-engineer deduplication. It's a great thing to mention in an interview - "I'd add content hashing for future deduplication" - but don't spend 5 minutes designing the reference counting system. Mention it, note the trade-off, and move on. The interviewer will appreciate the awareness without you burning time on an optimisation that saves $40/month.

Expiration and Cleanup Architecture

Expiration is more important for Pastebin than for URL Shortener because paste content consumes real storage. A 10 MB paste that expired 6 months ago and was never cleaned up is pure waste.

Two-Phase Cleanup

flowchart TD
    subgraph PHASE1["Phase 1: Lazy Expiration (on read)"]
        READ["View paste request"] --> CHECK{"expires_at < NOW()?"}
        CHECK -->|"Not expired"| SERVE["Serve content"]
        CHECK -->|"Expired"| RETURN_410["Return 410 Gone"]
    end
    
    subgraph PHASE2["Phase 2: Background Cleanup (hourly cron)"]
        SCAN["Scan for expired pastes<br/>(batch of 10,000)"]
        SCAN --> DELETE_S3["Delete S3 objects"]
        DELETE_S3 --> SOFT_DEL["Soft-delete metadata"]
        SOFT_DEL --> CACHE_INV["Invalidate cache entries"]
    end
    
    subgraph PHASE3["Phase 3: Hard Delete (daily cron)"]
        HARD["Delete metadata rows<br/>where deleted_at > 30 days ago"]
    end

Three-phase expiration and cleanup system. Phase 1 is lazy expiration on read - when a view request comes in for an expired paste, the system returns 410 Gone without deleting anything. This is free and catches expired pastes immediately on access. Phase 2 is a background cleanup job running hourly that scans for expired pastes in batches of 10,000, deletes their S3 objects, soft-deletes the metadata, and invalidates cache entries. Phase 3 runs daily and hard-deletes metadata rows that were soft-deleted more than 30 days ago, reclaiming database space.

Phase 1: Lazy expiration catches expired pastes at read time - no storage is freed, but the user gets the correct 410 response immediately.

Phase 2: Background cleanup actually frees storage by deleting S3 objects and soft-deleting metadata. Running hourly with a batch size of 10,000 keeps the cleanup predictable and prevents long-running transactions.

Phase 3: Hard delete removes soft-deleted metadata rows after 30 days. This reclaims database space and keeps the paste_metadata table size manageable.

Key Takeaways

1. Content in S3, metadata in PostgreSQL. This separation is the single most important database design decision for Pastebin. Content and metadata have different sizes, access patterns, and scaling properties.

2. Random ID generation is appropriate at Pastebin's write rate. At 50 writes/sec, collision checking against a UNIQUE index is cheap. Counter ranges would be over-engineering. Save the counter range discussion for high-write systems like URL Shortener.

3. Store both original and compressed sizes. Original size for user display and rate limiting. Compressed size for cache sizing and bandwidth estimation. Having both in the schema prevents runtime decompression just to answer "how big is this paste?"

4. Content hashing enables future deduplication. Even if you don't implement dedup from day one, storing the SHA-256 hash means you can add it later without a data migration. Mention this in interviews as a forward-looking design choice.

5. Partial indexes on expires_at for cleanup efficiency. WHERE deleted_at IS NULL ensures the cleanup worker only scans active pastes, not the entire history. This is a production optimisation that shows database expertise.

6. Three-phase cleanup: lazy on read, background hourly, hard delete daily. Each phase serves a different purpose - immediate correctness, storage recovery, and database space reclamation. Together they keep the system clean without any single phase being a heavy operation.

Exercise: Exercise 1: The system has been running for 2 years. The paste_metadata table has 3.6 billion rows (5M/day × 365 × 2). Even with cleanup, the table has 500 million active rows. Query performance is degrading. Design a table partitioning strategy. Would you partition by created_at (range), by paste_id (hash), or by expires_at? What are the trade-offs of each?

Exercise 2: Design the content deduplication reference counting system in detail. When paste A and paste B share the same S3 object, and paste A expires, how do you determine whether to delete the S3 object? What happens if paste A's cleanup job and paste B's deletion request execute concurrently? How do you prevent a race condition from orphaning the S3 object or deleting it while paste B still needs it?

Exercise 3: The product team wants to add "paste versions" - when a user creates a paste with the same title as an existing paste, it creates version 2 instead of a new paste. Design the schema changes needed. How do you handle the paste_id (does each version get its own ID?), the S3 key structure, and the view API (how does a user access version 1 vs version 2)?

Back to System Design Interviews