Design Dropbox File Sync

1
┌─────────────────────────────────────────────────────────────┐
2
│                    Client Sync Engine                        │
3
├─────────────────┬─────────────────┬─────────────────────────┤
4
│   Local Tree    │   Synced Tree   │      Remote Tree        │
5
│  (disk state)   │  (merge base)   │   (server state)        │
6
├─────────────────┼─────────────────┼─────────────────────────┤
7
│ file.txt (v3)   │ file.txt (v2)   │ file.txt (v2)           │
8
│ new.txt         │      -          │       -                 │
9
│      -          │ deleted.txt     │       -                 │
10
└─────────────────┴─────────────────┴─────────────────────────┘

1
Fixed chunking (4-byte blocks):
2
Before: [ABCD][EFGH][IJKL]
3
Insert X at position 2:
4
After:  [ABXC][DEFG][HIJK][L...]  ← All blocks change!
5

6
Content-defined chunking:
7
Before: [ABC|DEF|GHIJ]  (boundaries at content patterns)
8
Insert X at position 2:
9
After:  [ABXC|DEF|GHIJ]  ← Only first block changes

1
// Gear hash: FP_i = (FP_{i-1} << 1) + GearTable[byte]
2
const GEAR_TABLE: Uint32Array = new Uint32Array(256) // Random values
3

4
function findChunkBoundary(
5
  data: Uint8Array,
6
  minSize: number,
7
  maxSize: number,
8
  mask: number, // e.g., 0x1FFF for ~8KB average
9
): number {
10
  let fp = 0
11

12
  // Skip minimum chunk size (cut-point skipping optimization)
13
  for (let i = 0; i < Math.min(minSize, data.length); i++) {
14
    fp = ((fp << 1) + GEAR_TABLE[data[i]]) >>> 0
15
  }
16

17
  // Search for boundary
18
  for (let i = minSize; i < Math.min(maxSize, data.length); i++) {
19
    fp = ((fp << 1) + GEAR_TABLE[data[i]]) >>> 0
20
    if ((fp & mask) === 0) {
21
      return i + 1 // Boundary found
22
    }
23
  }
24

25
  return Math.min(maxSize, data.length) // Force boundary at max
26
}

1
-- File metadata (sharded by namespace_id)
2
CREATE TABLE files (
3
    namespace_id    BIGINT NOT NULL,      -- User/shared folder
4
    file_id         UUID NOT NULL,        -- Stable identifier
5
    path            TEXT NOT NULL,        -- Current path (mutable)
6
    blocklist       UUID[] NOT NULL,      -- Ordered list of block hashes
7
    size            BIGINT NOT NULL,
8
    content_hash    BYTEA NOT NULL,       -- Hash of concatenated blocks
9
    modified_at     TIMESTAMPTZ NOT NULL,
10
    revision        BIGINT NOT NULL,      -- Monotonic version
11
    is_deleted      BOOLEAN DEFAULT FALSE,
12

13
    PRIMARY KEY (namespace_id, file_id)
14
);
15

16
-- Enables path lookups within namespace
17
CREATE INDEX idx_files_path ON files(namespace_id, path)
18
    WHERE NOT is_deleted;
19

20
-- Journal for sync cursor (append-only)
21
CREATE TABLE journal (
22
    namespace_id    BIGINT NOT NULL,
23
    journal_id      BIGINT NOT NULL,      -- Monotonic cursor
24
    file_id         UUID NOT NULL,
25
    operation       VARCHAR(10) NOT NULL, -- 'create', 'modify', 'delete', 'move'
26
    timestamp       TIMESTAMPTZ NOT NULL,
27

28
    PRIMARY KEY (namespace_id, journal_id)
29
);

1
┌────────────────────────────────────────────────────────────┐
2
│                    Cache Hierarchy                          │
3
├──────────────────┬──────────────────┬──────────────────────┤
4
│   Client Cache   │   Edge Cache     │   Origin Cache       │
5
│   (SQLite)       │   (Regional)     │   (Global)           │
6
├──────────────────┼──────────────────┼──────────────────────┤
7
│ Full tree state  │ Hot metadata     │ Frequently accessed  │
8
│ Block cache      │ TTL: 5 seconds   │ TTL: 30 seconds      │
9
│ Offline access   │ Namespace-keyed  │ File-id keyed        │
10
└──────────────────┴──────────────────┴──────────────────────┘

1
{
2
  "namespace_id": "ns_abc123",
3
  "journal_id": 158293,
4
  "hint": "file_changed" // Client fetches details via API
5
}

1
GET /api/v2/files/list_folder/continue

1
{
2
  "cursor": "AAGvR5..." // Opaque cursor encoding (namespace_id, journal_id)
3
}

1
{
2
  "entries": [
3
    {
4
      "tag": "file",
5
      "id": "id:abc123",
6
      "path_display": "/Documents/report.pdf",
7
      "rev": "015a3e0c4b650000000",
8
      "size": 1048576,
9
      "content_hash": "e3b0c44298fc1c149afbf4c8996fb924...",
10
      "server_modified": "2024-01-15T10:30:00Z"
11
    },
12
    {
13
      "tag": "deleted",
14
      "id": "id:def456",
15
      "path_display": "/old-file.txt"
16
    }
17
  ],
18
  "cursor": "AAGvR6...",
19
  "has_more": false
20
}

1
POST /api/v2/files/upload_session/start

1
{
2
  "session_type": "concurrent", // Allows parallel block uploads
3
  "content_hash": "e3b0c44..." // Optional: skip if file unchanged
4
}

1
POST /api/v2/files/upload_session/append_v2
2
Content-Type: application/octet-stream
3
Dropbox-API-Arg: {"cursor": {"session_id": "...", "offset": 0}}
4

5
[4MB binary block data]

1
POST /api/v2/files/upload_session/finish

1
{
2
  "cursor": { "session_id": "...", "offset": 12582912 },
3
  "commit": {
4
    "path": "/Documents/large-file.zip",
5
    "mode": "overwrite",
6
    "mute": false // true = don't notify other clients immediately
7
  }
8
}

1
{
2
  "id": "id:abc123",
3
  "size": 12582912,
4
  "blocks_reused": 2, // Blocks already existed
5
  "blocks_uploaded": 1, // New blocks stored
6
  "bytes_transferred": 4194304 // Only new block data
7
}

1
Timeline:
2
t0: Synced tree = {file.txt, rev=5}
3
t1: Local edit  → Local tree = {file.txt, rev=5, modified}
4
t2: Remote edit → Remote tree = {file.txt, rev=6}
5
t3: Sync attempt → CONFLICT (local modified, remote also modified)

1
def detect_conflict(local: Node, remote: Node, synced: Node) -> ConflictType:
2
    local_changed = local != synced
3
    remote_changed = remote != synced
4

5
    if not local_changed:
6
        return ConflictType.NONE  # Apply remote
7
    if not remote_changed:
8
        return ConflictType.NONE  # Apply local
9
    if local == remote:
10
        return ConflictType.NONE  # Same change, no conflict
11

12
    # Both changed differently
13
    if local.is_delete and remote.is_delete:
14
        return ConflictType.NONE  # Both deleted, no conflict
15
    if local.is_delete or remote.is_delete:
16
        return ConflictType.EDIT_DELETE
17

18
    return ConflictType.EDIT_EDIT

1
Before: [Block A][Block B][Block C]
2
        (hash_a) (hash_b) (hash_c)
3

4
Edit middle of Block B:
5

6
After:  [Block A][Block B'][Block C]
7
        (hash_a) (hash_b') (hash_c)
8

9
Blocks to upload: only Block B' (hash_b')
10
Bandwidth saved: 66% (2 of 3 blocks reused)

1
def compute_delta(old_block: bytes, new_block: bytes) -> Delta:
2
    """Rsync algorithm: find matching regions, send only diffs."""
3
    BLOCK_SIZE = 700  # Rolling checksum window
4

5
    # Build index of old block's checksums
6
    old_checksums = {}
7
    for i in range(0, len(old_block) - BLOCK_SIZE, BLOCK_SIZE):
8
        weak = adler32(old_block[i:i+BLOCK_SIZE])
9
        strong = sha256(old_block[i:i+BLOCK_SIZE])
10
        old_checksums[weak] = (i, strong)
11

12
    # Scan new block with rolling checksum
13
    delta = []
14
    i = 0
15
    while i < len(new_block) - BLOCK_SIZE:
16
        weak = rolling_adler32(new_block, i, BLOCK_SIZE)
17

18
        if weak in old_checksums:
19
            offset, expected_strong = old_checksums[weak]
20
            actual_strong = sha256(new_block[i:i+BLOCK_SIZE])
21

22
            if actual_strong == expected_strong:
23
                # Match found - emit COPY instruction
24
                delta.append(Copy(source_offset=offset, length=BLOCK_SIZE))
25
                i += BLOCK_SIZE
26
                continue
27

28
        # No match - emit literal byte
29
        delta.append(Literal(new_block[i]))
30
        i += 1
31

32
    return delta

1
a(i+1, i+n) = a(i, i+n-1) - old_byte + new_byte
2
b(i+1, i+n) = b(i, i+n-1) - n*old_byte + a(i+1, i+n)
3
checksum = b * 65536 + a

1
┌─────────────────────────────────────────────────────┐
2
│              Compression Pipeline                    │
3
├─────────────────────────────────────────────────────┤
4
│ 1. Chunk file (CDC)                                 │
5
│ 2. Compress each chunk independently (parallel)     │
6
│ 3. Concatenate compressed streams                   │
7
│ 4. Upload concatenated result                       │
8
├─────────────────────────────────────────────────────┤
9
│ Broccoli modifications:                             │
10
│ - Uncompressed meta-block header for context        │
11
│ - Disabled dictionary references across blocks      │
12
│ - Enables parallel compression + concatenation      │
13
└─────────────────────────────────────────────────────┘

1
GET https://<lan-peer>/blocks/{namespace_id}/{block_hash}
2
Authorization: Bearer <namespace-scoped-certificate>

1
┌────────────────────────────────────────────────────────────┐
2
│                    Desktop Client                           │
3
├──────────────────────────────────────────────────────────────┤
4
│  ┌─────────────┐  ┌─────────────┐  ┌─────────────────────┐  │
5
│  │ File System │  │ Sync Engine │  │ Network Layer       │  │
6
│  │ Watcher     │  │             │  │                     │  │
7
│  │             │  │ Three Trees │  │ HTTP/2 multiplexing │  │
8
│  │ inotify/    │──│ Reconciler  │──│ WebSocket notify    │  │
9
│  │ FSEvents    │  │             │  │ Block upload/down   │  │
10
│  │             │  │ Conflict    │  │                     │  │
11
│  │             │  │ Handler     │  │ Retry + backoff     │  │
12
│  └─────────────┘  └─────────────┘  └─────────────────────┘  │
13
│                                                              │
14
│  ┌─────────────────────────────────────────────────────────┐│
15
│  │                    Local Database                        ││
16
│  │  SQLite: tree state, block cache index, sync cursor     ││
17
│  └─────────────────────────────────────────────────────────┘│
18
└──────────────────────────────────────────────────────────────┘

1
interface SyncStatus {
2
  state: "synced" | "syncing" | "paused" | "offline" | "error"
3
  pendingFiles: number
4
  pendingBytes: number
5
  currentFile?: {
6
    path: string
7
    progress: number // 0-100
8
    speed: number // bytes/sec
9
  }
10
  errors: SyncError[]
11
}

1
interface SelectiveSyncConfig {
2
  // Folders to sync (whitelist approach)
3
  includedPaths: string[]
4

5
  // Or folders to exclude (blacklist approach for "sync everything except")
6
  excludedPaths: string[]
7

8
  // Smart sync: files appear in finder but download on-demand
9
  smartSyncEnabled: boolean
10
  smartSyncPolicy: "local" | "online-only" | "mixed"
11
}

1
┌─────────────────────────────────────────────────────────────┐
2
│                     AWS Infrastructure                       │
3
├─────────────────────────────────────────────────────────────┤
4
│                                                              │
5
│  ┌──────────────┐     ┌──────────────┐     ┌─────────────┐ │
6
│  │ Route 53     │────▶│ CloudFront   │────▶│ ALB         │ │
7
│  │ (DNS)        │     │ (CDN)        │     │             │ │
8
│  └──────────────┘     └──────────────┘     └──────┬──────┘ │
9
│                                                    │        │
10
│  ┌────────────────────────────────────────────────▼──────┐ │
11
│  │                    ECS / EKS                          │ │
12
│  │  ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │ │
13
│  │  │ API      │ │ Metadata │ │ Block    │ │ Notify   │ │ │
14
│  │  │ Gateway  │ │ Service  │ │ Service  │ │ Service  │ │ │
15
│  │  └──────────┘ └──────────┘ └──────────┘ └──────────┘ │ │
16
│  └───────────────────────────────────────────────────────┘ │
17
│                                                              │
18
│  ┌─────────────────────────────────────────────────────────┐│
19
│  │                    Data Layer                           ││
20
│  │                                                         ││
21
│  │  ┌──────────────┐  ┌──────────────┐  ┌──────────────┐  ││
22
│  │  │ Aurora       │  │ ElastiCache  │  │ S3           │  ││
23
│  │  │ PostgreSQL   │  │ Redis        │  │ (Block Store)│  ││
24
│  │  │ (Metadata)   │  │ (Cache)      │  │              │  ││
25
│  │  └──────────────┘  └──────────────┘  └──────────────┘  ││
26
│  │                                                         ││
27
│  │  ┌──────────────┐  ┌──────────────┐                    ││
28
│  │  │ DynamoDB     │  │ SQS/SNS      │                    ││
29
│  │  │ (Journal)    │  │ (Events)     │                    ││
30
│  │  └──────────────┘  └──────────────┘                    ││
31
│  └─────────────────────────────────────────────────────────┘│
32
└─────────────────────────────────────────────────────────────┘