The Google File System

wangfans

The state of a file region after a data mutation depends
on the type of mutation, whether it succeeds or fails, and
whether there are concurrent mutations. Table 1 summarizes
the result. A file region is consistent if all clients will
always see the same data, regardless of which replicas they
read from.

wangfans

A region is defined after a file data mutation if it
is consistent and clients will see what the mutation writes in
its entirety. When a mutation succeeds without interference
from concurrent writers, the affected region is defined (and
by implication consistent): all clients will always see what
the mutation has written. Concurrent successful mutations
leave the region undefined but consistent: all clients see the
same data, but it may not reflect what any one mutation
has written.

wangfans

Typically, it consists of mingled fragments from
multiple mutations. A failed mutation makes the region inconsistent
(hence also undefined): different clients may see
different data at different times. We describe below how our
applications can distinguish defined regions from undefined

wangfans

regions. The applications do not need to further distinguish
between different kinds of undefined regions.
Data mutations may be writes or record appends. A write
causes data to be written at an application-specified file
offset. A record append causes data (the “record”) to be
appended atomically at least once even in the presence of
concurrent mutations, but at an offset of GFS’s choosing
(Section 3.3). (In contrast, a “regular” append is merely a
write at an offset that the client believes to be the current
end of file.) The offset is returned to the client and marks
the beginning of a defined region that contains the record.
In addition, GFS may insert padding or record duplicates in
between. They occupy regions considered to be inconsistent
and are typically dwarfed by the amount of user data.

wangfans

region is guaranteed to be defined and contain the data written
by the last mutation. GFS achieves this by (a) applying
mutations to a chunkin the same order on all its replicas
(Section 3.1), and (b) using chunkv ersion numbers to detect
any replica that has become stale because it has missed mutations
while its chunkserver was down (Section 4.5). Stale
replicas will never be involved in a mutation or given to
clients asking the master for chunk locations. They are
garbage collected at the earliest opportunity.

wangfans

Since clients cache chunkl ocations, they may read from a
stale replica before that information is refreshed. This window
is limited by the cache entry’s timeout and the next
open of the file, which purges from the cache all chunki nformation
for that file. Moreover, as most of our files are
append-only, a stale replica usually returns a premature
end of chunkra ther than outdated data. When a reader
retries and contacts the master, it will immediately get current
chunkl ocations.

wangfans

of course still corrupt or destroy data. GFS identifies failed
chunkservers by regular handshakes between master and all
chunkservers and detects data corruption by checksumming
(Section 5.2). Once a problem surfaces, the data is restored
from valid replicas as soon as possible (Section 4.3). A chunk
is lost irreversibly only if all its replicas are lost before GFS
can react, typically within minutes. Even in this case, it becomes
unavailable, not corrupted: applications receive clear
errors rather than corrupt data.

wangfans

2.7.2 Implications for Applications
GFS applications can accommodate the relaxed consistency
model with a few simple techniques already needed for
other purposes: relying on appends rather than overwrites,
checkpointing, and writing self-validating, self-identifying
records.

wangfans

Practically all our applications mutate files by appending
rather than overwriting. In one typical use, a writer generates
a file from beginning to end. It atomically renames the
file to a permanent name after writing all the data, or periodically
checkpoints how much has been successfully written.
Checkpoints may also include application-level checksums.

wangfans

Readers verify and process only the file region up
to the last checkpoint, which is known to be in the defined
state. Regardless of consistency and concurrency issues, this
approach has served us well. Appending is far more efficient
and more resilient to application failures than random
writes. Checkpointing allows writers to restart incrementally
and keeps readers from processing successfully written