File Storage System

Functional Requirements

1. Upload/Download Files: Support objects from 1 byte to 5 TB.
2. Multi-part Upload: Split large files into chunks for parallel upload and resumability.
3. Versioning: Maintain multiple versions of an object; support rollback.
4. Access Control: Bucket-level and object-level ACLs, IAM policies.
5. Lifecycle Policies: Auto-transition objects between storage tiers (hot → warm → cold).
6. MFA Delete: Require multi-factor authentication for permanent deletion.
7. Object Lock: WORM (Write Once Read Many) compliance for regulatory requirements.
8. Cross-Region Replication: Async replication to a secondary region.

Non-Functional Requirements

Requirement	Target
Durability	99.999999999% (11 nines)
Availability	99.99%
Throughput	100K+ concurrent uploads/downloads
Object Size	1 byte – 5 TB
Latency (first byte)	< 100ms for hot data
Scalability	Trillions of objects, exabytes of data
Cost Efficiency	Pay-per-use, tiered storage

High-Level Architecture

┌──────────┐     ┌──────────────┐     ┌──────────────────┐
│  Client   │────▶│ API Gateway  │────▶│  Metadata Service │
│ (SDK/CLI/ │     │ (Auth, Rate  │     │  (Object Index)   │
│  Console) │     │  Limiting)   │     │  MySQL/etcd       │
└──────────┘     └──────────────┘     └────────┬─────────┘
                                                │
                              ┌─────────────────┼─────────────────┐
                              ▼                 ▼                 ▼
                       ┌──────────┐     ┌──────────┐     ┌──────────┐
                       │ Data Node│     │ Data Node│     │ Data Node│
                       │  (Tier 1)│     │  (Tier 2)│     │  (Tier 3)│
                       │  Hot/SSD │     │  Warm/HDD│     │  Cold/   │
                       │          │     │          │     │  Glacier │
                       └────┬─────┘     └────┬─────┘     └────┬─────┘
                            │                 │                 │
                            ▼                 ▼                 ▼
                       ┌──────────┐     ┌──────────┐     ┌──────────┐
                       │ Storage  │     │ Storage  │     │ Storage  │
                       │ Disks    │     │ Disks    │     │ Tape/Vault│
                       └──────────┘     └──────────┘     └──────────┘

Data Model

Account
  └── Bucket
        ├── Object (key)
        │     ├── Version (version_id)
        │     │     ├── Chunk 1 (chunk_id, checksum, data_node)
        │     │     ├── Chunk 2 (chunk_id, checksum, data_node)
        │     │     └── Chunk N
        │     ├── ACL (owner, permissions)
        │     ├── Metadata (content_type, encoding, tags)
        │     └── Lifecycle (tier, expiration, transition_date)
        └── Bucket Policy

Schema:

-- Metadata tables
CREATE TABLE buckets (
    bucket_id     BIGINT PRIMARY KEY,
    account_id    BIGINT NOT NULL,
    name          VARCHAR(63) UNIQUE,
    region        VARCHAR(16),
    versioning    ENUM('enabled', 'suspended', 'disabled'),
    created_at    TIMESTAMP,
    lifecycle     JSON  -- tiering rules
);

CREATE TABLE objects (
    object_id     BIGINT PRIMARY KEY,
    bucket_id     BIGINT,
    key           VARCHAR(1024),  -- S3 allows 1024-byte keys
    version_id    BIGINT,
    is_latest     BOOLEAN DEFAULT TRUE,
    size_bytes    BIGINT,
    etag          VARCHAR(32),
    content_type  VARCHAR(128),
    checksum      VARCHAR(64),  -- SHA-256
    storage_class ENUM('STANDARD', 'REDUCED_REDUNDANCY', 'STANDARD_IA', 'ONEZONE_IA', 'GLACIER', 'DEEP_ARCHIVE'),
    created_at    TIMESTAMP,
    deleted_at    TIMESTAMP NULL,
    UNIQUE KEY (bucket_id, key, version_id)
);

CREATE TABLE chunks (
    chunk_id      BIGINT PRIMARY KEY,
    object_id     BIGINT,
    version_id    BIGINT,
    chunk_index   INT,
    size_bytes    BIGINT,
    checksum      VARCHAR(64),
    data_node_id  INT,
    storage_path  VARCHAR(512),
    replicas      JSON,  -- [{node_id, path, checksum}]
    INDEX (object_id, version_id)
);

API Design

Operation	Method	Description
PutObject	PUT	Upload an object (up to 5GB single PUT)
GetObject	GET	Download an object
DeleteObject	DELETE	Soft-delete (marks as deleted)
HeadObject	HEAD	Get object metadata without body
ListObjects	GET	List objects in a bucket (paginated)
InitiateMultipartUpload	POST	Start multi-part upload
UploadPart	PUT	Upload a chunk of a multi-part upload
CompleteMultipartUpload	POST	Finalize multi-part upload
AbortMultipartUpload	DELETE	Cancel incomplete multi-part upload
CopyObject	PUT	Server-side copy
GetObjectAttributes	GET	Get checksum, storage class, etc.

Upload Flow (Multi-part)

1. Client                    API Gateway              Metadata Service
  │                             │                          │
  │──InitiateMultipartUpload──▶│                          │
  │                             │──Create Upload Entry───▶│
  │                             │◀──upload_id─────────────│
  │◀──upload_id────────────────│                          │
  │                             │                          │
  │──UploadPart (chunk 1)─────▶│                          │
  │                             │──Store chunk────────────▶│
  │◀──part ETag────────────────│                          │
  │                             │                          │
  │──UploadPart (chunk 2)─────▶│  (parallel uploads)      │
  │                             │                          │
  │──CompleteMultipartUpload──▶│                          │
  │                             │──Create Object Entry───▶│
  │                             │──Mark chunks as live────▶│
  │◀──200 OK + ETag────────────│                          │

Chunk size selection:

Object Size	Recommended Chunk
< 100 MB	Single PUT (no multipart)
100 MB – 1 GB	8 MB chunks
1 GB – 10 GB	16 MB chunks
10 GB – 100 GB	32 MB chunks
> 100 GB	64 MB chunks (max 10,000 parts)

Download Flow

1. Client                    API Gateway              Metadata Service        Data Nodes
  │                             │                          │                      │
  │──GetObject─────────────────▶│                          │                      │
  │                             │──Lookup object──────────▶│                      │
  │                             │◀──chunk locations────────│                      │
  │                             │                          │                      │
  │                             │──Fetch chunks───────────▶│ (parallel)           │
  │                             │◀──chunk data─────────────│                      │
  │◀──stream response──────────│                          │                      │

Optimizations:

• Range requests: Support Range: bytes=0-1023 for partial downloads.
• Parallel chunk download: Fetch non-dependent chunks in parallel.
• CDN integration: Cache hot objects at edge locations.
• Byte-range fetching: Client can request specific byte ranges for large objects.

Storage Tiers

Tier	Media	Access Time	Durability	Cost/GB/month	Use Case
Hot (Standard)	SSD	< 10ms	11 nines	$0.023	Frequently accessed
Warm (Standard-IA)	HDD	< 50ms	11 nines	$0.0125	Infrequent access
Cold (Glacier)	Tape/Vault	minutes–hours	11 nines	$0.004	Archive/compliance
Deep Archive	Tape	hours	11 nines	$0.00099	Long-term archive

Lifecycle Policy Engine

class LifecyclePolicy:
    def apply(self, object):
        age_days = (now() - object.created_at).days
        
        # Transition rules (evaluated in order)
        for rule in sorted(self.rules, key=lambda r: r.days):
            if age_days >= rule.days and object.storage_class != rule.target_class:
                self.transition(object, rule.target_class)
                break
        
        # Expiration rules
        if self.expiration_days and age_days >= self.expiration_days:
            self.delete(object)

Example lifecycle configuration:

{
  "rules": [
    {
      "id": "transition-to-warm",
      "prefix": "logs/",
      "transition": {
        "days": 30,
        "storage_class": "STANDARD_IA"
      }
    },
    {
      "id": "transition-to-cold",
      "prefix": "logs/",
      "transition": {
        "days": 90,
        "storage_class": "GLACIER"
      }
    },
    {
      "id": "expire-old-logs",
      "prefix": "logs/",
      "expiration": {
        "days": 365
      }
    }
  ]
}

Consistency Model

Operation	Consistency
PUT new object	Strongly consistent (read-after-write)
GET existing object	Strongly consistent
DELETE object	Strongly consistent
LIST objects	Eventually consistent (may lag behind writes)
Overwrite existing object	Strongly consistent

Why eventual consistency for LIST?

• LIST operations scan large metadata indexes.
• Maintaining strong consistency for LIST would require distributed transactions across all metadata partitions, which is expensive.
• S3 now provides strong consistency for LIST (since Dec 2020), but this requires careful metadata service design.

Metadata Service Design for Strong Consistency:

┌──────────────────────────────────────────────────┐
│              Metadata Service                     │
│                                                   │
│  ┌─────────────┐    ┌─────────────┐             │
│  │  Primary     │───▶│  Replica 1  │             │
│  │  (Leader)    │    │  (Follower) │             │
│  └──────┬──────┘    └─────────────┘             │
│         │                                        │
│         ▼                                        │
│  ┌─────────────┐    ┌─────────────┐             │
│  │  Replica 2  │    │  Replica 3  │             │
│  │  (Follower) │    │  (Follower) │             │
│  └─────────────┘    └─────────────┘             │
│                                                   │
│  Consensus: Raft or Multi-Paxos                  │
│  Replication: Synchronous (leader → majority)    │
└──────────────────────────────────────────────────┘

Write path (strong consistency):

1. Client sends PUT to metadata service.
2. Leader appends to write-ahead log (WAL).
3. Leader replicates to majority (2 of 3 followers).
4. Leader commits and responds to client.
5. Followers apply committed entries asynchronously.

Read path (strong consistency):

1. Client sends GET to metadata service.
2. Read from leader (or follower that is caught up).
3. Return latest committed version.

Versioning Implementation

Object: "photos/image.jpg"
  ├── version "3939393939" (latest)
  │     ├── chunk_001 → data_node_5
  │     ├── chunk_002 → data_node_12
  │     └── chunk_003 → data_node_8
  ├── version "3939393940"
  │     ├── chunk_001 → data_node_3
  │     └── chunk_002 → data_node_7
  └── version "3939393941" (archived)
        └── chunk_001 → data_node_2

• Each PUT creates a new version (if versioning enabled).
• DELETE adds a delete marker; previous version remains accessible.
• Old versions can be expired via lifecycle policies.
• is_latest flag tracks the current version for GET operations.

Data Placement Strategy

Consistent Hashing for Chunk Distribution:

Consistent Hash Ring

         node_A
        /       \
       /         \
  node_D          node_B
       \         /
        \       /
         node_C

Chunk placement: hash(chunk_id) → nearest node clockwise

class ConsistentHash:
    def __init__(self, nodes, virtual_nodes=150):
        self.ring = SortedDict()
        for node in nodes:
            for i in range(virtual_nodes):
                key = hash(f"{node}:{i}")
                self.ring[key] = node
    
    def get_node(self, chunk_id):
        key = hash(chunk_id)
        idx = self.ring.bisect_right(key) % len(self.ring)
        return self.ring.values()[idx]
    
    def get_replicas(self, chunk_id, replication_factor=3):
        nodes = []
        key = hash(chunk_id)
        idx = self.ring.bisect_right(key)
        while len(nodes) < replication_factor:
            node = self.ring.values()[idx % len(self.ring)]
            if node not in nodes:
                nodes.append(node)
            idx += 1
        return nodes

Replication factor = 3: Each chunk stored on 3 different data nodes (ideally across 3 racks or availability zones).

Erasure Coding (Reed-Solomon)

For large objects, erasure coding is more storage-efficient than 3x replication:

Original: [D1] [D2] [D3] [D4]
Encoded:  [D1] [D2] [D3] [D4] [P1] [P2]  (4+2 scheme)

Storage: 6 chunks for 4 data chunks = 1.5x overhead
           (vs 3x for replication)

Fault tolerance: Can survive ANY 2 chunk losses

Reed-Solomon (k, m) scheme:

Scheme	Data Chunks	Parity Chunks	Overhead	Fault Tolerance
(3, 1)	3	1	1.33x	1 failure
(4, 2)	4	2	1.50x	2 failures
(6, 3)	6	3	1.50x	3 failures
(10, 4)	10	4	1.40x	4 failures

When to use erasure coding vs replication:

Use Case	Strategy	Reason
Hot data (< 30 days)	3x replication	Fast reads, no decode overhead
Warm data (30–90 days)	Erasure coding (4+2)	Storage savings, acceptable decode cost
Cold/archive data	Erasure coding (6+3)	Maximum storage efficiency

Cross-Region Replication

Region A (Primary)              Region B (Replica)
┌──────────────┐               ┌──────────────┐
│  Data Node 1  │──async──────▶│  Data Node 4  │
│  Data Node 2  │──async──────▶│  Data Node 5  │
│  Data Node 3  │──async──────▶│  Data Node 6  │
└──────────────┘               └──────────────┘
       │                              │
       ▼                              ▼
  Metadata Service              Metadata Service
  (Primary)                     (Replica)

Replication flow:

1. Object PUT in Region A.
2. Metadata service in Region A records replication status: PENDING.
3. Background replicator reads new chunks from Region A.
4. Writes chunks to Region B data nodes.
5. Updates Region B metadata: replication status COMPLETED.
6. If replication lag exceeds SLA, alert ops team.

Consistency: Eventual replication with configurable SLA (typically < 15 minutes).

Garbage Collection

Deleted objects and old versions need space reclamation:

Mark-and-Sweep GC:

Phase 1: Mark
  - Identify all chunks referenced by live objects
  - Mark as "live" in chunk reference table
  
Phase 2: Sweep
  - Scan all chunks on data nodes
  - Any chunk not marked as "live" is a candidate for deletion
  - Delete unreferenced chunks after safety window (24 hours)

class GarbageCollector:
    def run_gc(self):
        # Phase 1: Mark live chunks
        live_chunks = set()
        for obj in self.metadata.list_all_objects():
            for chunk in self.metadata.get_chunks(obj.object_id):
                live_chunks.add(chunk.chunk_id)
        
        # Phase 2: Sweep unreferenced chunks
        for node in self.data_nodes:
            for chunk in node.list_chunks():
                if chunk.chunk_id not in live_chunks:
                    if chunk.age > timedelta(hours=24):  # safety window
                        node.delete_chunk(chunk.chunk_id)
                        self.metadata.delete_chunk_record(chunk.chunk_id)

Garbage collection triggers:

1. Periodic: Run GC every 6 hours.
2. Threshold: When free disk space drops below 20%.
3. Event-driven: After bulk delete operations.

Integrity Verification

Mechanism	Frequency	Scope
Checksum on write	Every PUT	Data integrity at write time
Checksum on read	Every GET	Detect silent corruption
Background scan	Weekly	Full data integrity audit
Replica comparison	Daily	Detect replica divergence

def verify_chunk_integrity(chunk):
    stored_checksum = chunk.checksum
    calculated_checksum = sha256(chunk.data)
    if stored_checksum != calculated_checksum:
        # Log corruption event
        log.warning(f"Chunk {chunk.chunk_id} corrupted")
        # Repair from healthy replica
        repair_from_replica(chunk)
        # Alert ops
        alert(f"Data corruption detected: {chunk.chunk_id}")

Failure Handling & Self-Healing

┌─────────────────────────────────────────────────┐
│            Failure Detection & Recovery          │
│                                                  │
│  1. Heartbeat monitoring (every 5s)              │
│  2. Node misses 3 heartbeats → marked suspect    │
│  3. After 60s → marked failed                    │
│  4. GC triggers replica rebalancing              │
│  5. New replicas created to maintain RF=3         │
│  6. If node recovers → sync and rejoin           │
└─────────────────────────────────────────────────┘

Disk failure handling:

1. SMART monitoring detects failing disk.
2. Data node marks disk as read-only.
3. Background job copies chunks from failing disk to healthy disks.
4. Once copy complete, disk is replaced.

Node failure handling:

1. Cluster manager detects node down.
2. Rebalance chunks: ensure each chunk has 3 healthy replicas.
3. New replicas created on remaining healthy nodes.
4. No data loss as long as <= 2 nodes fail simultaneously.

Performance Benchmarks

Metric	Target	Actual
PUT latency (1MB)	< 200ms	150ms
GET latency (1MB)	< 100ms	80ms
GET first byte (100MB)	< 500ms	350ms
Throughput per connection	1 Gbps	800 Mbps
Metadata service throughput	100K ops/sec	120K ops/sec
Durability	99.999999999%	Verified via audit
Storage efficiency	< 1.5x overhead	1.3x (EC 4+2)

Interview Tips

1. Start with requirements: Clarify durability target (11 nines is standard), object size range, access patterns.
2. Draw the architecture: API → Metadata → Data Nodes → Storage.
3. Explain the upload flow: Multi-part upload, chunk distribution, metadata recording.
4. Discuss durability: Replication vs erasure coding trade-offs, cross-region replication.
5. Cover consistency: Strong consistency for reads/writes, eventual for LIST and replication.
6. Address lifecycle: Hot → warm → cold transitions, expiration, MFA delete.
7. Garbage collection: Mark-and-sweep, safety window, triggers.
8. Failure modes: Disk failure, node failure, rack failure, region failure — always recoverable.