GFS NAMESPACE DESIGN
────────────────────

Traditional FS:           GFS:
──────────────           ─────

Directory tree:          Flat lookup table:
/                        ┌─────────────────────────────────┐
├── home                 │ Full Path → Metadata            │
│   ├── user1            ├─────────────────────────────────┤
│   └── user2            │ /home → {dir metadata}          │
└── data                 │ /home/user1 → {dir metadata}    │
    └── files            │ /data/files/log1 → {file meta}  │
                         └─────────────────────────────────┘

Each dir has            Single prefix-compressed
list of children        table (efficient)

Problem:                Benefit:
- Tree traversal        - O(1) lookup
- Lock contention       - Fine-grained locking
                        - Parallel operations


IMPLEMENTATION:
──────────────

Data Structure: Prefix-compressed lookup table

Example:
────────
/home/alice/data/file1.txt
/home/alice/data/file2.txt
/home/bob/logs/access.log

Stored as:
──────────
Common prefixes compressed:
↓
Efficient memory usage
Fast lookups
Support for snapshots

METADATA MEMORY LAYOUT
─────────────────────

For 100 million chunks (several petabytes):

File Namespace:
──────────────
• ~10 million files
• ~100 bytes per file
• Total: ~1 GB

Chunk Metadata:
──────────────
• 100 million chunks
• ~64 bytes per chunk
  - Chunk handle (8 bytes)
  - Version number (8 bytes)
  - Replica locations (3-5 locations × 8 bytes)
  - Lease info (16 bytes)
• Total: ~6 GB

Chunkserver State:
─────────────────
• ~1000 chunkservers
• ~1 KB per server
• Total: ~1 MB

TOTAL: < 10 GB (easily fits in RAM of modern server)

Benefits:
────────
✓ Fast operations (no disk I/O)
✓ Simple consistency
✓ Global view for decisions
✓ Easy to scan entire namespace

WHY LEASES?
──────────

Problem Without Leases:
───────────────────────

Distributed consensus for every write:

Client → Replica 1 ┐
Client → Replica 2 ┼→ Agree on order? (Paxos/Raft)
Client → Replica 3 ┘   Slow! Complex!

For each write:
- Multiple round trips
- Consensus protocol
- Failure handling
→ 10-100ms latency per operation


With Leases:
───────────

One-time setup (lease grant):
Master → Primary: "You order operations for 60sec"

Then for each write:
Client → Primary: "Write this"
Primary → Secondaries: "Apply in this order"
→ ~1ms latency per operation

Benefits:
────────
✓ No distributed consensus per operation
✓ Primary makes serialization decision
✓ Low latency writes
✓ Simple protocol
✓ Automatic timeout (no need for perfect failure detection)


LEASE VS LOCK:
─────────────

Lock:
- Must explicitly release
- Failure? → Deadlock or complex recovery

Lease:
- Automatic timeout
- Failure? → Expires naturally
- Master can wait or revoke
- No distributed state

1. Client asks Master for lease: "Write to Chunk C (ref_count=2)"
2. Master sees ref_count > 1:
   a) Pick new chunk handle C'
   b) Tell chunkservers holding C: "Copy C to C' locally"
   c) Update metadata: Current file now points to C' (ref_count=1)
   d) Snapshot still points to C (ref_count=1)
3. Master grants lease for C' to client.
4. Client writes to C' normally.

CHUNK CREATION WORKFLOW
──────────────────────

Scenario: Client creates new file and writes first chunk

1. CLIENT CREATES FILE
   ──────────────────

   Client: "Create file /data/logs/2003-10-15"
   Master:
     a) Create namespace entry
     b) Log operation to disk
     c) Return success

2. CLIENT WRITES DATA
   ──────────────────

   Client: "Write to /data/logs/2003-10-15, offset 0, 1MB"
   Master:
     a) File has no chunks yet
     b) Need to create chunk 0

3. MASTER ALLOCATES CHUNK
   ──────────────────────

   a) Generate chunk handle (globally unique 64-bit)
      chunk_handle = 0x1a2b3c4d5e6f7g8h

   b) Select 3 chunkservers:

      Available servers: [cs-1, cs-2, ..., cs-50]

      Filter:
      • Enough disk space
      • Below average utilization
      • Rack diversity

      Selected: [cs-5, cs-12, cs-23]
      (cs-5 and cs-12 in rack-1, cs-23 in rack-2)

   c) Designate primary (lowest load)
      Primary: cs-5

   d) Grant lease to cs-5 (60 seconds)

   e) Increment version to 1

   f) Log operation:
      "CHUNK_CREATE: handle=0x1a2b, file=/data/logs/2003-10-15,
       index=0, version=1, locations=[cs-5, cs-12, cs-23]"

4. MASTER CONTACTS CHUNKSERVERS
   ────────────────────────────

   Master → cs-5, cs-12, cs-23:
     "Create chunk 0x1a2b, version 1"

   Each chunkserver:
     a) Create empty file /gfs/chunks/0x1a2b3c4d5e6f7g8h
     b) Initialize version to 1
     c) ACK to master

5. MASTER RETURNS TO CLIENT
   ────────────────────────

   Master → Client:
     "Chunk 0 metadata:
      handle: 0x1a2b3c4d5e6f7g8h
      primary: cs-5
      secondaries: [cs-12, cs-23]
      version: 1
      lease_expiration: T+60"

6. CLIENT WRITES DATA
   ──────────────────

   (Normal write flow as described in Chapter 2)

RE-REPLICATION WORKFLOW
──────────────────────

Trigger: Chunkserver cs-12 fails

1. DETECTION
   ─────────

   Master heartbeat timeout:
   • cs-12 hasn't responded in 10+ seconds
   • Mark cs-12 as dead
   • Scan all chunks on cs-12

2. IDENTIFY UNDER-REPLICATED CHUNKS
   ────────────────────────────────

   Chunks on cs-12:
   ┌─────────────────────────────────────┐
   │ Chunk 0x1a2b: [cs-5, cs-12, cs-23]  │
   │   → Now only 2 replicas (cs-5, cs-23) │
   │   → Need re-replication!            │
   │                                     │
   │ Chunk 0x2c3d: [cs-7, cs-12, cs-15]  │
   │   → Now only 2 replicas             │
   │   → Need re-replication!            │
   └─────────────────────────────────────┘

3. PRIORITIZATION
   ──────────────

   Sort chunks by priority:

   Priority factors:
   • Current replication count (1 > 2 > 3)
   • Recently accessed (hot chunks first)
   • Blocks client writes (highest priority)

   Example order:
   1. Chunk 0x9f8e: 1 replica (URGENT!)
   2. Chunk 0x7d6c: 2 replicas, blocking write
   3. Chunk 0x1a2b: 2 replicas, recently read
   4. Chunk 0x5b4a: 2 replicas, cold data

4. SELECT SOURCE AND DESTINATION
   ──────────────────────────────

   For chunk 0x1a2b:

   Existing replicas: [cs-5, cs-23]

   Select source: cs-5 (lowest load)

   Select destination:
   • Filter: Not in same rack as cs-5 or cs-23
   • Prefer: Low disk usage, low load
   • Result: cs-31 (in rack-3)

5. ISSUE RE-REPLICATION
   ────────────────────

   Master → cs-31:
     "Copy chunk 0x1a2b from cs-5, version 1"

   cs-31 → cs-5:
     "Send me chunk 0x1a2b"

   cs-5 → cs-31:
     [chunk data, 64MB]

   cs-31:
     • Writes to local disk
     • Verifies checksums
     • ACKs to master

6. UPDATE METADATA
   ───────────────

   Master updates chunk 0x1a2b:
   Locations: [cs-5, cs-23, cs-31]

   Chunk now has 3 replicas again ✓


RATE LIMITING:
─────────────

Master limits re-replication rate:
• Max concurrent re-replications: 50-100
• Avoids overwhelming network
• Background process, not urgent
• Gradually restores replication

MASTER REPLICATION
─────────────────

Primary Master:
┌──────────────────────────────────────┐
│ • Handles all operations             │
│ • In-memory metadata                 │
│ • Operation log (on disk)            │
└──────────────────────────────────────┘
           │
           │ Replicates to:
           │
           ↓
┌──────────────────────────────────────┐
│ Shadow Masters (multiple)            │
│ • Read-only replicas                 │
│ • Lag slightly behind primary        │
│ • Can serve reads                    │
│ • Quick promotion on failure         │
└──────────────────────────────────────┘
           │
           │ Operation log also on:
           │
           ↓
┌──────────────────────────────────────┐
│ Remote Disks (multiple)              │
│ • Different failure domains          │
│ • Different datacenters              │
│ • Disaster recovery                  │
└──────────────────────────────────────┘


OPERATION LOG REPLICATION:
─────────────────────────

Every metadata mutation:

1. Primary logs operation
2. Replicates to shadow masters
3. Replicates to remote disks
4. Waits for ACKs from ALL
5. Then applies to memory
6. Then returns success to client

Guarantee: If client sees success, operation is durable


SHADOW MASTER OPERATION:
───────────────────────

Shadow continuously:
• Reads operation log from primary
• Replays operations locally
• Builds same in-memory state
• Lags by ~seconds

Can serve:
• Read-only operations
• Metadata queries
• File listings

Cannot serve:
• Writes (redirects to primary)
• Lease grants
• Chunk creation


FAILOVER:
────────

Primary master fails:
1. Monitoring detects failure (<10 sec)
2. External system promotes shadow
3. Shadow becomes primary
4. Updates DNS/configuration
5. Clients redirect to new primary

Downtime: ~1 minute (conservative)

Data loss: None (operation log replicated)