Keyboard shortcuts

/ or ⌘/Ctrl K
Find a note
j / k
Next / previous section or linked note
h / l
Collapse or go to parent / expand or enter
e or Alt-click
Read a linked note here
o
Open focused note on its own
g g / G
First / last section or linked note
g h / g a
Home / all notes
g b / g t
Backlinks / table of contents
t
Cycle System, Light, Dark
? / Esc
Show / close this reference

Search: ↑/↓ or Ctrl N/P, Enter to open. Shortcuts pause while typing.

sectionGFS (Google File System) [8725974f]

Part of storage
  • Single control plane, master, scared it wouldn't scale but it did

  • Two specialized operations, record append and snapshot, with other basic file operations

    • record append allows multiple clients to append from small records to a file
    • snapshot allows the clients to create a copy of a file or a directory tree
  • batch oriented workloads
  • commodity servers

  • Recovery?

    • Checkpoints on metadata state, operation log
    • shadow managers for recovery to serve read operations only, similar to how RW locks even have contention
  • Notably, GFS places the consistency checking on the client library, where it requires the you (via the client library) to check
  • Is not linearizable

1. Locks

  • Read lock aquired on the directory (full path to the directory so that it's not being edited or renamed)
  • Write lock on the file name so that two or more processes cannot write at the same time
  • Only a small region is locked, since not doing it carefully destroys performance
  • If a manager dies after locking something, the lock goes with it since it's a central master

  • left to right locking, so locks are acquired in the shape of

    • /a, /a/b, /a/b/c for read locks
    • /a/b/c/file.txt for write locks

2. Reading

  1. To read, user request is first processed by the GFS client that finds a chunk index

    • Since each file is divded into 64MB chunks, the client just %'s by 64MB to find the appropriate idx
  2. Then the client requests this information from the manager to get the chunk index and chunk handle, which the manager tells an appropriate replica of
  3. Client then caches the metadata

3. Writing

  • Two kinds of writes, a random write and an append (not POSIX compliant)
  • Replicas hold leases that coordinate the writes
  • Leases expire, and are only active for a small period of time. This means that if a bad replica has a lease, it will expire and a new node will be found
  • Primary replicas exist because they allow the data to be consistent

3.1. Writing Workflow

  • Random write and append operations are roughly the same, random writes use an offset for where the data is written, whereas the append just goes to the last chunk
  • Note that the data is pushed to all the replicas

  • The write (aka commit) happens to the main replica after all the replicas have recieved the data
  • Replicas then ack whether they've received the data or not

3.1.1. Edge Cases on Writing

  • If the last chunk has available space for appending data, then the chunk servers write that data
  • If the chunk is already full, then the chunkserver asks the client to create a new chunk, which requires a new write and request loop from the manager
  • If the last chunk is partially full, the chunkserver holding the last chunk will respond to the client with a message about the available server

3.1.2. Control vs Data Flow

  • GFS, critically, decouples the control and the data. The data physically flows via nearest-in-rack, but the manager still runs things

4. Deletes

  • Garbage collection is done to avoid sync deletes
  • Client says a delete needs to happen, so master creates a read lock on the dir and a write lock on the file
  • Master then revokes the leases in progress, and waits for replicas to finish mutations
  • Afterwards, delete actually happens

5. Consistency Model

GFS consistency starts from issues during write, we need to prevent writing over multiple times (mix data), and also issues with writing over the same data.

5.1. Possible States after mutations

  • Consistent
  • Inconsistent
  • Defined - when mutations happen to a file and the applications can parse it and read it
  • Undefined - when the region hasn't properly changed data yet

6. How to actually maintain consistency?

  • Random writes can result in serial success, where one lease or lock after the other allows writes to go through
  • Concurrent success can happen when you have multiple writes on the same thing, resulting in mixed data
  • Failure
  • Serial success for appends happen the same as random writes, proper offsets are used
  • Concurrent success is when two writes attempt to use the same offset

7. Dealing with Data Inconsistencies

  • It doesn't, you can have overlapping writes, the application level is responsible for locking
  • For append however, appends happen as at least one atomic unit.
  • GFS only deals with stale data because of bad replications

8. Metadata Consistency

  • Chunkservers tell the metadata manager what offsets map to where, but the manager also keeps track of it

  • We also use shadow managers when the client cannot reach the primary manager, which help facilitate primary reads

    • also the shadow might be behind the primary, since it reads off of the master's logs
  • Master is also fully syncronous, it does not respond to the client's requests for updating metadata until everything is done
  • Failures can be retried by the client side, or present in the operation log

9. Scalability

  • Scalability is achieved mostly through having multiple chunkservers, which can be easily added
  • Availability is achieved by having three chunk servers per app by default
  • Replication happens in the background if hosts are lost, and GFS manager has shadow managers that take over should the master go down
  • Durability is acheived that there's replicas for chunkservers and operation logs for the metadata
  • Throughput is achieved by separating the data from the metadata flow
  • Consistency is applied through relaxed consistency, most files are mutated by having append and reads