FAILED WRITE GUARANTEE
─────────────────────

Operation: write(offset, data)
Result: Some replicas fail to apply

Guarantee: INCONSISTENT
──────────────────────

Scenario:
────────
Client writes "HELLO" at offset 1000

Process:
1. Data pushed to all replicas ✓
2. Primary applies write ✓
3. Secondary 1 applies write ✓
4. Secondary 2 FAILS (disk error, crash, etc.)

Primary returns ERROR to client

After:
┌─────────────────────────────────┐
│ Replica 1 (primary): "HELLO"    │
│ Replica 2: "HELLO"              │
│ Replica 3: "xxxxx" (old data)   │
└─────────────────────────────────┘

State: INCONSISTENT
• Replicas disagree
• Some have new data, some have old
• Client knows write failed
• Client will retry


CLIENT RETRY:
────────────

Client retries same write:

1. Data pushed again
2. Primary applies again at offset 1000
3. All replicas succeed this time

After retry:
┌─────────────────────────────────┐
│ All replicas: "HELLO"           │
└─────────────────────────────────┘

State: Now DEFINED

Old inconsistent region overwritten
→ Application sees defined data


WHAT IF CLIENT DOESN'T RETRY?
────────────────────────────

Inconsistent region remains:

┌─────────────────────────────────┐
│ R1: "HELLO"                     │
│ R2: "HELLO"                     │
│ R3: "xxxxx"                     │
└─────────────────────────────────┘

Future reads:
• Some clients see "HELLO"
• Some see "xxxxx"
• Undefined behavior!

Application must:
• Either retry on failure
• Or use record append (atomic)
• Or validate data when reading

CONCURRENT WRITES GUARANTEE
──────────────────────────

Operation: Multiple clients write to same offset
Result: All succeed

Guarantee: CONSISTENT but UNDEFINED
──────────────────────────────────

Scenario:
────────
Client A writes "AAA" at offset 1000
Client B writes "BBB" at offset 1000
(simultaneously)

What happens:
────────────

Primary serializes:
1. Receives both requests
2. Assigns serial numbers:
   A → serial #42
   B → serial #43

3. Applies in order:
   - Apply "AAA" → offset 1000 = "AAA"
   - Apply "BBB" → offset 1000 = "BBB"

4. Tells secondaries: "Apply #42 then #43"

5. All replicas: "BBB" (last write wins)

Result:
┌─────────────────────────────────┐
│ All replicas: "BBB"             │
└─────────────────────────────────┘

State: CONSISTENT (all agree)
       But UNDEFINED (not what A expected!)

Client A thinks it wrote "AAA"
Client B thinks it wrote "BBB"
Actual result: "BBB" (B won)

→ Data is consistent across replicas
→ But result is undefined from app perspective
→ Application shouldn't do concurrent writes!


GFS RECOMMENDATION:
──────────────────

DON'T do concurrent writes to same offset

Instead:
• Use record append (atomic, serialized)
• Use application-level locking
• Write to different files
• Write to different regions


WHY ALLOW THIS?
──────────────

GFS doesn't prevent it because:
• Simplifies protocol (no distributed locking)
• Application should handle coordination
• Record append is the "right" way
• Focus on common case (sequential appends)

RECORD APPEND GUARANTEE
──────────────────────

Operation: record_append(data)
Result: Success (or retry if failure)

Guarantee: DEFINED AT LEAST ONCE
────────────────────────────────

Properties:
──────────

1. ATOMICITY:
   • Record written atomically
   • All or nothing per replica
   • No partial records

2. AT-LEAST-ONCE:
   • Guaranteed to succeed eventually
   • May appear more than once (duplicates)
   • Client receives offset on success

3. DEFINED:
   • Successful appends create defined regions
   • All replicas have same data
   • Reading from any replica sees same record

4. SERIAL ORDERING:
   • Primary assigns offset
   • All replicas apply at same offset
   • Concurrent appends serialized by primary


SUCCESS CASE:
────────────

Client A: append("AAA")
Client B: append("BBB")

Primary serializes:
1. A arrives first → offset 1000
2. B arrives second → offset 1003

Result:
┌─────────────────────────────────┐
│ All replicas:                   │
│   Offset 1000: "AAA"            │
│   Offset 1003: "BBB"            │
└─────────────────────────────────┘

Both defined regions
Both clients get their offsets
Both succeed


FAILURE + RETRY CASE:
────────────────────

Client appends "AAA"
1. Data pushed to all replicas
2. Primary applies at offset 1000
3. Secondary 1 applies ✓
4. Secondary 2 FAILS
5. Primary returns ERROR

Client retries:
1. Data pushed again
2. Primary assigns NEW offset 1003
3. All replicas apply at 1003
4. Primary returns SUCCESS, offset=1003

Result:
┌─────────────────────────────────┐
│ Replica 1: 1000="AAA", 1003="AAA" │
│ Replica 2: 1000="AAA", 1003="AAA" │
│ Replica 3: 1000=junk,  1003="AAA" │
└─────────────────────────────────┘

• Offset 1000: INCONSISTENT (skip it)
• Offset 1003: DEFINED (success!)
• Client knows offset 1003 is the real one
• May have duplicate at 1000 (on R1, R2)

Application handles:
• Offset 1003 is guaranteed good
• Offset 1000 may be duplicate
• Use unique IDs to de-duplicate

RECOMMENDED WRITE PATTERNS
─────────────────────────

❌ AVOID: Random writes
──────────────────────

DON'T DO THIS:
─────────────

# Bad: Random writes from multiple clients
client_A.write(file, offset=1000, "AAA")
client_B.write(file, offset=1000, "BBB")
# Undefined result!

# Bad: Overwriting existing data
client.write(file, offset=500, "new data")
# May create inconsistent region if fails


✅ GOOD: Sequential appends
──────────────────────────

Pattern 1: Single writer, append-only
─────────────────────────────────────

writer = GFS.open(file, mode='append')
while has_data():
    data = get_next_data()
    writer.append(data)
writer.close()

# Properties:
# • No concurrent writers
# • Sequential appends
# • All operations defined


Pattern 2: Multiple writers, record append
──────────────────────────────────────────

# Multiple MapReduce tasks writing
for i in range(1000):  # 1000 mappers
    def mapper_task():
        while has_output():
            record = {
                'id': uuid(),
                'data': compute(),
                'checksum': crc32(data)
            }
            offset = GFS.record_append(output_file, record)
            # Atomic, no coordination needed!

# Properties:
# • Concurrent appends OK
# • Each gets unique offset
# • All atomic
# • May have duplicates (de-dup when reading)


Pattern 3: Write-once, read-many
────────────────────────────────

# Producer
writer.create(file)
writer.write(all_data)
writer.close()

# Mark immutable
GFS.finalize(file)

# Many readers
readers = [GFS.open(file, 'read') for _ in range(100)]
# All see consistent, defined data

# Properties:
# • Single write phase
# • Multiple concurrent reads
# • No mutations after finalize
# • Perfect for MapReduce input


Pattern 4: Checkpointing
────────────────────────

# Writer creates checkpoint periodically
def checkpoint_writer():
    current_file = 0

    while producing_data():
        data = produce_batch()

        # Write to new file
        filename = f"checkpoint_{current_file}"
        GFS.write(filename, data)
        GFS.finalize(filename)

        # Atomic rename (metadata-only)
        GFS.rename(filename, "current_checkpoint")

        current_file += 1

# Reader always reads finalized checkpoints
def reader():
    data = GFS.read("current_checkpoint")

# Properties:
# • Readers never see partial writes
# • Atomic switchover via rename
# • Old checkpoints can be kept

MAPREDUCE + GFS PATTERNS
───────────────────────

INPUT FILES (Read-only):
───────────────────────

Preparation:
1. Input data loaded into GFS
2. Files marked immutable
3. Replicated (3x default)

Map Phase Reads:
────────────────
• 1000s of map tasks
• Each reads different chunk
• All concurrent
• No consistency issues (immutable)
• Locality: schedule task near chunk


INTERMEDIATE DATA (Append-only):
────────────────────────────────

Map Task Writes:
───────────────

def map_task(input_chunk):
    results = process(input_chunk)

    for key, value in results:
        partition = hash(key) % NUM_REDUCERS
        filename = f"intermediate_{partition}"

        record = {
            'id': uuid(),  # For de-duplication
            'key': key,
            'value': value,
            'checksum': crc32(key + value)
        }

        # ATOMIC RECORD APPEND
        offset = GFS.record_append(filename, serialize(record))

# 1000s of mappers appending concurrently
# No coordination needed!
# GFS handles serialization

Reduce Task Reads:
─────────────────

def reduce_task(partition_id):
    filename = f"intermediate_{partition_id}"

    records = []
    seen_ids = set()

    for record in GFS.read_records(filename):
        # Validate checksum
        if not valid_checksum(record):
            continue  # Skip inconsistent

        # De-duplicate
        if record.id in seen_ids:
            continue

        records.append(record)
        seen_ids.add(record.id)

    # Process de-duplicated records
    results = reduce_function(records)
    return results


OUTPUT FILES (Sequential Write):
────────────────────────────────

Reduce Task Writes:
──────────────────

def reduce_task_output(partition_id):
    results = reduce_function(...)

    # Each reducer writes to separate file
    output_file = f"output_{partition_id}"

    # Single writer, sequential appends
    writer = GFS.create(output_file)
    for result in results:
        writer.append(result)
    writer.close()

    # Mark immutable
    GFS.finalize(output_file)

# No concurrent writes to same file
# All defined regions
# Safe for next MapReduce job as input


BENEFITS:
────────

✓ High throughput (concurrent appends)
✓ Fault tolerance (retry failed tasks)
✓ Simple coordination (record append)
✓ Scalability (1000s of tasks)
✓ No distributed locking needed