Design Google Drive File Sync & Storage

1. Problem Statement & Scope

System Mission

Design an enterprise-grade, cross-platform cloud file storage and multi-device synchronization engine capable of managing over 500 Million registered users and billions of files. The architecture must feature Content-Defined Chunking (CDC) using rolling polynomial Rabin Fingerprints for block-level deduplication, differential delta synchronization (transferring only mutated 4MB chunks), optimistic concurrency control for file revision trees, and a sub-500ms real-time mutation fanout pipeline across 250 Million concurrent connected devices.

Synthesizing vector architecture diagram...

Functional Requirements

1. Hierarchical File & Directory Namespace: Create, rename, move, copy, and delete files and deeply nested directories with ACID atomicity and POSIX permissions.
2. Block-Level Differential Delta Synchronization: Split mutated files using Content-Defined Chunking (CDC, average $4\text{ MB}$ chunks), compute cryptographic SHA-256 block hashes, and negotiate with the server to upload only novel, uncommitted blocks.
3. Global Content Addressable Storage (CAS) Deduplication: Deduplicate identical blocks across all files and users globally, referencing shared binary blocks in S3 via reference counting.
4. Real-Time Cross-Device Push Sync: Deliver instant remote file mutation notifications to all active desktop, mobile, and web sessions via persistent WebSocket connections within $< 500\text{ ms}$.
5. Revision History & Conflict Resolution: Maintain a 30-day immutable revision tree with optimistic concurrency locking on monotonic revision IDs, automatically generating "Conflicted Copies" during concurrent offline edits.

Non-Functional Requirements (SLAs/SLOs)

• High Availability: $99.999\%$ availability for file metadata query and sync commit APIs ($< 5.26\text{ minutes}$ downtime/year).
• Data Durability: $99.999999999\%$ (11 Nines) zero-byte-loss durability guaranteed by Amazon S3 multi-AZ storage and S3 Object Lock.
• Latency SLOs:
  • Delta Commit & Negotiation Latency: $< 100\text{ ms}$ ($P95$), $< 250\text{ ms}$ ($P99$).
  • Sync Push Fanout Latency: $< 500\text{ ms}$ ($P95$) from commit finalization to peer device WebSocket frame receipt.
• Bandwidth Reduction Efficiency: $\ge 90\%$ bandwidth reduction on incremental edits compared to full-file re-uploads.
• CAP / PACELC Classification:
  • Metadata & Commit Store: CP / PC-EC (Consistent revision numbers, strict serializability via DynamoDB transactional writes or Aurora PostgreSQL).
  • CAS Block Storage: AP / PA-EL (Immutable content-addressed S3 chunks, eventually consistent cache reads).

---

2. Capacity & Scale Estimation

Traffic Calculations

• User Population: $500\text{ Million}$ total registered users; $100\text{ Million}$ Daily Active Users (DAU).
• Active Connected Devices: Average $2.5\text{ devices/DAU} \implies \mathbf{250\text{ Million Concurrent WebSocket Connections}}$.
• Daily File Modifications / Sync Commits:
  • Average $10\text{ sync commits/user/day} \implies 1\text{ Billion sync commits/day}$.
  • Commit API QPS: $\text{Avg Sync QPS} = \frac{10^9\text{ commits}}{86,400\text{ sec}} \approx \mathbf{11,574\text{ QPS}}$ $\text{Peak Sync QPS (3}\times\text{ surge)} = 11,574 \times 3 \approx \mathbf{34,722\text{ QPS}}$
• WebSocket Notification Fanout Volume:
  • Each commit fans out to an average of $1.5$ other online peer devices owned by the user. $\text{Fanout Event Rate} = 11,574 \text{ commits/sec} \times 1.5 = \mathbf{17,361\text{ push frames/sec (Peak: } 52,083\text{ frames/sec)}}$

Storage Calculations (3-Year Horizon)

• User Storage Quota & Raw Footprint:
  • Free tier allocation $= 15\text{ GB/user}$; average usage $= 15\text{ GB}$. $\text{Total Raw Stored Footprint} = 500 \times 10^6 \times 15\text{ GB} = 7,500\text{ PB} = \mathbf{7.5\text{ Exabytes}}$
• Deduplication Multiplier (FastCDC Content-Defined Chunking):
  • Cross-user block-level deduplication yields an estimated $3.5\times$ storage footprint reduction. $\text{Physical S3 CAS Storage} = \frac{7.5\text{ Exabytes}}{3.5} \approx \mathbf{2.14\text{ Exabytes}}$
• Total Unique Chunks Managed:
  • Average chunk size $= 4\text{ MB} = 4,194,304\text{ bytes}$. $\text{Total Unique Chunks} = \frac{2.14 \times 10^{18}\text{ bytes}}{4.194 \times 10^6\text{ bytes}} \approx \mathbf{510\text{ Billion Unique Chunks}}$
• Metadata Storage Growth (3 Years):
  • $10^9\text{ commits/day} \times 365\text{ days} \times 3\text{ years} \approx 1.095\text{ Trillion revision records}$.
  • Record size (file pointer + 5 chunk hashes + timestamps): $\approx 500\text{ bytes}$. $\text{Metadata Storage}_{3\text{-yr}} = 1.095 \times 10^{12} \times 500\text{ bytes} \approx \mathbf{547.5\text{ TB (DynamoDB)}}$

Network Bandwidth

• Ingress Bandwidth (With vs Without Delta Sync):
  • Without Delta Sync (re-uploading the whole edited file; the average edited file is a 40 MB document or spreadsheet, i.e. 10 chunks, since tiny files are rarely the ones being re-saved): $\text{Unoptimized Ingress} = \frac{10^9 \times 40\text{ MB} \times 8\text{ bits}}{86,400\text{ sec}} \approx \mathbf{3.7\text{ Tbps}}$
  • With Block-Level Delta Sync (only the 1 modified 4MB chunk of those 10 is uploaded per edit): $\text{Avg Delta Ingress} = \frac{10^9 \times 4\text{ MB} \times 8\text{ bits}}{86,400\text{ sec}} \approx \mathbf{370.4\text{ Gbps}} \quad (\text{Peak: } \mathbf{1.11\text{ Tbps}})$ That is the $90\%$ reduction promised in the NFRs; for micro-edits of 100KB inside 100MB documents, CDC achieves $> 96\%$. Note that delta sync buys nothing for files smaller than one chunk ($\le 4\text{ MB}$): those are always re-uploaded whole, which is why the average is computed over edited files, not all files.
• Egress Bandwidth (Peer Download Path): $\text{Avg Egress Bandwidth} = 370.4\text{ Gbps} \times 1.5\text{ peers} \approx \mathbf{555.6\text{ Gbps}} \quad (\text{Peak: } \mathbf{1.67\text{ Tbps}})$

Memory & Cache Sizing (80/20 Pareto Working Set)

• Top $20\%$ of active daily files generate $80\%$ of read/sync queries.
• Daily active chunk working set: $10^9\text{ commits/day} \times 0.20 = 200\text{ Million chunks/day}$.
• Global Chunk Hash Cache (ElastiCache Redis):
  • Redis Set mapping sha256 -> exists (32 bytes hash + 16 bytes pointer $\approx 48\text{ bytes}$): $200 \times 10^6 \times 48\text{ bytes} \approx \mathbf{9.6\text{ GB RAM}}$
• Global Bloom Filter for Chunk Existence ($510\text{ Billion chunks}$, $p = 0.01$ false positive): $m = - \frac{n \ln p}{(\ln 2)^2} \approx 9.58\text{ bits/chunk} \to 10\text{ bits/chunk} \approx 1.25\text{ bytes/chunk}$ $\text{Total [Bloom Filter](/components/03-bloom-filters-and-counting-filters) RAM} = 510 \times 10^9 \times 1.25\text{ bytes} = \mathbf{637.5\text{ GB RAM}}$ A RedisBloom filter is a single key and therefore lives on a single shard, so one 638 GB filter is impossible; the global filter is partitioned into 256 sub-filters keyed by the first byte of the SHA-256 (bf:blocks:<xx>, $\approx 2.5\text{ GB}$ each), which cluster mode spreads across shards. Provision 32 nodes of cache.r6g.2xlarge ($52.8\text{ GiB}$ each, $\approx 1.7\text{ TB}$ total) so that filter growth, replication buffers and fragmentation have headroom; 20 nodes $\times 32\text{ GB}$ would be full on day one.

Fleet Sizing & Connection Gateway Provisioning

• WebSocket Gateway Fleet:
  • Managing $250\text{ Million}$ persistent WebSocket connections.
  • Linux epoll/Netty containers on AWS ECS Fargate: 50,000 idle TCP connections per container (requiring $4\text{ vCPU}, 16\text{ GB RAM}$). $\text{Gateway Task Count} = \frac{250,000,000\text{ connections}}{50,000\text{ conns/task}} = \mathbf{5,000\text{ ECS Fargate Tasks}}$ Distributed across 3 Availability Zones behind multi-AZ Network Load Balancers (NLB).

---

3. AWS-First High-Level Architecture

Synthesizing vector architecture diagram...

Follow a file edit from device A to device B. Client A splits the changed file into content-defined chunks and asks the commit API which chunks are new. In the "Metadata Engine & CAS Storage Tier" panel, the sync service checks a Bloom filter of existing chunk hashes (most chunks already exist, even across users), uploads only new chunks to S3 under their SHA-256 hash, and records the new file version in DynamoDB as a list of chunk hashes. The "Real-Time Mutation Fanout Pipeline" panel carries that change from DynamoDB Streams through Kinesis to push workers, which look up device B's connection in Redis and notify it over WebSocket; device B then downloads only the chunks it lacks. In the "Garbage Collection & Archival" panel, chunks whose reference count reaches zero are deleted by a GC worker. Content addressing is the key idea: identical chunks are stored once, and a one-line edit transfers one chunk instead of the whole file.

Data Flow Walkthrough

1. Local Chunking & Hashing: When a local file mutates, Client A's OS filesystem watcher activates FastCDC, computing rolling Rabin fingerprints to cut $4\text{ MB}$ chunks, hashing each chunk with SHA-256.
2. Delta Negotiation: Client A invokes POST /v1/files/sync/commit with base version and chunk hashes. The Sync Service checks the Redis Bloom filters first: a negative is definitive (the chunk is new, upload it), but a positive is only "probably exists" and must be confirmed with a BatchGetItem on the BLOCK#<sha256> rows before the client is told to skip an upload, because acting on a false positive would commit a manifest that points at a chunk nobody ever stored. For chunks that do exist, the response also carries a proof-of-possession challenge (Section 8.6) so a client cannot attach someone else's chunk by knowing its hash. The service returns presigned S3 PUT URLs for only the genuinely missing chunks.
3. Immutable CAS Ingestion: Client A uploads only novel chunks directly to s3://drive-blocks/<sha256_hash>.
4. Atomic Manifest Finalization: Client A invokes POST /v1/files/sync/finalize. The Sync Service verifies chunk existence, increments monotonic version ($V_{14} \to V_{15}$), and commits via DynamoDB TransactWriteItems.
5. Real-Time Device Fanout: DynamoDB Streams captures the revision commit, routing through Kinesis to Fanout Workers. Workers query the Redis connection registry and push a lightweight FileUpdated event through the WebSocket Gateway to Client B. Client B downloads only the modified 4MB block from S3.

Concrete Step-by-Step Request Walkthrough: Tracing Delta Sync Commit & Fanout

---

4. API Interface Design

1. Delta Sync Commit Negotiation (POST /v1/files/sync/commit)

Negotiates missing chunks with the server prior to data transfer.

httpCopy
POST /v1/files/sync/commit HTTP/1.1
Host: api.drive.aws.internal
Authorization: Bearer <jwt_token>
Content-Type: application/json

{
  "file_id": "file_88129384bc",
  "base_version": 14,
  "file_name": "quarterly_financial_model.xlsx",
  "parent_folder_id": "folder_root_001",
  "file_size_bytes": 20971520,
  "chunk_hashes": [
    "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855",
    "f2ca1bb6c7e907d06dafe4687e579fce76b37e4e93b7605022da52e6ccc26fd2",
    "a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e",
    "5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8",
    "4b227777d4dd1fc61c6f884f48641d02b4d121d3fd328cb08b5531fcacdabf8a"
  ]
}

Response: 200 OK(Upload Only Required For Missing Chunks)

jsonCopy
{
  "file_id": "file_88129384bc",
  "new_version": 15,
  "sync_action": "UPLOAD_REQUIRED",
  "missing_chunks": [
    {
      "chunk_hash": "a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e",
      "presigned_put_url": "https://s3.us-east-1.amazonaws.com/drive-cas-blocks/a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e?X-Amz-Signature=...",
      "expires_at": 1773651600
    }
  ]
}

2. Finalize Commit (POST /v1/files/sync/finalize)

Atomically promotes revision upon verified upload of missing chunks.

httpCopy
POST /v1/files/sync/finalize HTTP/1.1
Host: api.drive.aws.internal
Authorization: Bearer <jwt_token>
Content-Type: application/json

{
  "file_id": "file_88129384bc",
  "base_version": 14,
  "new_version": 15,
  "uploaded_chunk_hashes": [
    "a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e"
  ]
}

Response: 200 OK

jsonCopy
{
  "file_id": "file_88129384bc",
  "status": "COMMITTED",
  "version": 15,
  "committed_at": 1773648500123
}

3. Status Codes & Error Contracts

---

5. Data Models & Storage Architecture

Relational Schema (Amazon Aurora PostgreSQL Alternative)

sqlCopy
CREATE TABLE users (
    user_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    email VARCHAR(255) UNIQUE NOT NULL,
    storage_quota_bytes BIGINT NOT NULL DEFAULT 16106127360, -- 15 GB
    storage_used_bytes BIGINT NOT NULL DEFAULT 0,
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

CREATE TABLE files (
    file_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    user_id UUID NOT NULL REFERENCES users(user_id) ON DELETE CASCADE,
    parent_folder_id UUID REFERENCES files(file_id),
    file_name VARCHAR(255) NOT NULL,
    is_folder BOOLEAN NOT NULL DEFAULT FALSE,
    is_deleted BOOLEAN NOT NULL DEFAULT FALSE,
    current_version INT NOT NULL DEFAULT 1,
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    updated_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    CONSTRAINT unique_file_in_folder UNIQUE (user_id, parent_folder_id, file_name)
);

CREATE TABLE file_versions (
    file_id UUID NOT NULL REFERENCES files(file_id) ON DELETE CASCADE,
    version_number INT NOT NULL,
    file_size_bytes BIGINT NOT NULL,
    chunk_manifest JSONB NOT NULL, -- Array of SHA-256 hashes in sequence
    committed_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    PRIMARY KEY (file_id, version_number)
);

CREATE TABLE cas_blocks (
    block_sha256 CHAR(64) PRIMARY KEY,
    size_bytes INT NOT NULL,
    global_ref_count BIGINT NOT NULL DEFAULT 1,
    s3_storage_tier VARCHAR(32) NOT NULL DEFAULT 'STANDARD',
    first_seen_at TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

CREATE INDEX idx_files_parent ON files(user_id, parent_folder_id) WHERE is_deleted = FALSE;

DynamoDB Single-Table Schema (GoogleDriveCoreTable)

---