Here is the link.
4.3 Creation, Re-replication, Rebalancing
Chunk replicas are created for three reasons: chunk creation, re-replication, and rebalancing.
When the master creates a chunk, it chooses where to
place the initially empty replicas. It considers several factors. (1) We want to place new replicas on chunkservers with
below-average disk space utilization. Over time this will
equalize disk utilization across chunkservers. (2) We want to
limit the number of “recent” creations on each chunkserver.
Although creation itself is cheap, it reliably predicts imminent heavy write traffic because chunks are created when demanded by writes, and in our append-once-read-many workload they typically become practically read-only once they
have been completely written. (3) As discussed above, we
want to spread replicas of a chunk across racks.
The master re-replicates a chunk as soon as the number
of available replicas falls below a user-specified goal. This
could happen for various reasons: a chunkserver becomes
unavailable, it reports that its replica may be corrupted, one
of its disks is disabled because of errors, or the replication
goal is increased. Each chunk that needs to be re-replicated
is prioritized based on several factors. One is how far it is
from its replication goal. For example, we give higher priority to a chunk that has lost two replicas than to a chunk that
has lost only one. In addition, we prefer to first re-replicate
chunks for live files as opposed to chunks that belong to recently deleted files (see Section 4.4). Finally, to minimize
the impact of failures on running applications, we boost the
priority of any chunk that is blocking client progress.
The master picks the highest priority chunk and “clones”
it by instructing some chunkserver to copy the chunk data
directly from an existing valid replica. The new replica is
placed with goals similar to those for creation: equalizing
disk space utilization, limiting active clone operations on
any single chunkserver, and spreading replicas across racks.
To keep cloning traffic from overwhelming client traffic, the
master limits the numbers of active clone operations both
for the cluster and for each chunkserver. Additionally, each
chunkserver limits the amount of bandwidth it spends on
each clone operation by throttling its read requests to the
source chunkserver.
Finally, the master rebalances replicas periodically: it examines the current replica distribution and moves replicas
for better disk space and load balancing. Also through this
process, the master gradually fills up a new chunkserver
rather than instantly swamps it with new chunks and the
heavy write traffic that comes with them. The placement
criteria for the new replica are similar to those discussed
above. In addition, the master must also choose which existing replica to remove. In general, it prefers to remove
those on chunkservers with below-average free space so as
to equalize disk space usage.
4.4 Garbage Collection
After a file is deleted, GFS does not immediately reclaim
the available physical storage. It does so only lazily during
regular garbage collection at both the file and chunk levels.
We find that this approach makes the system much simpler
and more reliable.
4.4.1 Mechanism
When a file is deleted by the application, the master logs
the deletion immediately just like other changes. However
instead of reclaiming resources immediately, the file is just
renamed to a hidden name that includes the deletion timestamp. During the master’s regular scan of the file system
namespace, it removes any such hidden files if they have existed for more than three days (the interval is configurable).
Until then, the file can still be read under the new, special
name and can be undeleted by renaming it back to normal.
When the hidden file is removed from the namespace, its inmemory metadata is erased. This effectively severs its links
to all its chunks.
In a similar regular scan of the chunk namespace, the
master identifies orphaned chunks (i.e., those not reachable
from any file) and erases the metadata for those chunks. In
a HeartBeat message regularly exchanged with the master,
each chunkserver reports a subset of the chunks it has, and
the master replies with the identity of all chunks that are no
longer present in the master’s metadata. The chunkserver
is free to delete its replicas of such chunks.
4.4.2 Discussion
Although distributed garbage collection is a hard problem
that demands complicated solutions in the context of programming languages, it is quite simple in our case. We can
easily identify all references to chunks: they are in the fileto-chunk mappings maintained exclusively by the master.
We can also easily identify all the chunk replicas: they are
Linux files under designated directories on each chunkserver.
Any such replica not known to the master is “garbage.”
The garbage collection approach to storage reclamation
offers several advantages over eager deletion. First, it is
simple and reliable in a large-scale distributed system where
component failures are common. Chunk creation may succeed on some chunkservers but not others, leaving replicas
that the master does not know exist. Replica deletion messages may be lost, and the master has to remember to resend
them across failures, both its own and the chunkserver’s.
Garbage collection provides a uniform and dependable way
to clean up any replicas not known to be useful. Second,
it merges storage reclamation into the regular background
activities of the master, such as the regular scans of namespaces and handshakes with chunkservers. Thus, it is done
in batches and the cost is amortized. Moreover, it is done
only when the master is relatively free. The master can respond more promptly to client requests that demand timely
attention. Third, the delay in reclaiming storage provides a
safety net against accidental, irreversible deletion.
In our experience, the main disadvantage is that the delay
sometimes hinders user effort to fine tune usage when storage is tight. Applications that repeatedly create and delete
temporary files may not be able to reuse the storage right
away. We address these issues by expediting storage reclamation if a deleted file is explicitly deleted again. We also
allow users to apply different replication and reclamation
policies to different parts of the namespace. For example,
users can specify that all the chunks in the files within some
directory tree are to be stored without replication, and any
deleted files are immediately and irrevocably removed from
the file system state.
4.5 Stale Replica Detection
Chunk replicas may become stale if a chunkserver fails
and misses mutations to the chunk while it is down. For
each chunk, the master maintains a chunk version number
to distinguish between up-to-date and stale replicas.
Whenever the master grants a new lease on a chunk, it
increases the chunk version number and informs the up-to-date replicas. The master and these replicas all record the
new version number in their persistent state. This occurs
before any client is notified and therefore before it can start
writing to the chunk. If another replica is currently unavailable, its chunk version number will not be advanced. The
master will detect that this chunkserver has a stale replica
when the chunkserver restarts and reports its set of chunks
and their associated version numbers. If the master sees a
version number greater than the one in its records, the master assumes that it failed when granting the lease and so
takes the higher version to be up-to-date.
The master removes stale replicas in its regular garbage
collection. Before that, it effectively considers a stale replica
not to exist at all when it replies to client requests for chunk
information. As another safeguard, the master includes
the chunk version number when it informs clients which
chunkserver holds a lease on a chunk or when it instructs
a chunkserver to read the chunk from another chunkserver
in a cloning operation. The client or the chunkserver verifies
the version number when it performs the operation so that
it is always accessing up-to-date data.
5. FAULT TOLERANCE AND DIAGNOSIS
One of our greatest challenges in designing the system is
dealing with frequent component failures. The quality and quantity of components together make these problems more
the norm than the exception: we cannot completely trust
the machines, nor can we completely trust the disks. Component failures can result in an unavailable system or, worse,
corrupted data. We discuss how we meet these challenges
and the tools we have built into the system to diagnose problems when they inevitably occur.
5.1 High Availability
Among hundreds of servers in a GFS cluster, some are
bound to be unavailable at any given time. We keep the
overall system highly available with two simple yet effective
strategies: fast recovery and replication.
5.1.1 Fast Recovery
Both the master and the chunkserver are designed to restore their state and start in seconds no matter how they
terminated. In fact, we do not distinguish between normal
and abnormal termination; servers are routinely shut down
just by killing the process. Clients and other servers experience a minor hiccup as they time out on their outstanding
requests, reconnect to the restarted server, and retry. Section 6.2.2 reports observed startup times.
5.1.2 Chunk Replication
As discussed earlier, each chunk is replicated on multiple
chunkservers on different racks. Users can specify different
replication levels for different parts of the file namespace.
The default is three. The master clones existing replicas as
needed to keep each chunk fully replicated as chunkservers
go offline or detect corrupted replicas through checksum verification (see Section 5.2). Although replication has served
us well, we are exploring other forms of cross-server redundancy such as parity or erasure codes for our increasing read-only storage requirements. We expect that it is challenging
but manageable to implement these more complicated redundancy schemes in our very loosely coupled system because our traffic is dominated by appends and reads rather
than small random writes.
5.1.3 Master Replication
The master state is replicated for reliability. Its operation
log and checkpoints are replicated on multiple machines. A
mutation to the state is considered committed only after
its log record has been flushed to disk locally and on all
master replicas. For simplicity, one master process remains
in charge of all mutations as well as background activities
such as garbage collection that change the system internally.
When it fails, it can restart almost instantly. If its machine
or disk fails, monitoring infrastructure outside GFS starts a
new master process elsewhere with the replicated operation
log. Clients use only the canonical name of the master (e.g.
gfs-test), which is a DNS alias that can be changed if the
master is relocated to another machine.
Moreover, “shadow” masters provide read-only access to
the file system even when the primary master is down. They
are shadows, not mirrors, in that they may lag the primary
slightly, typically fractions of a second. They enhance read
availability for files that are not being actively mutated or
applications that do not mind getting slightly stale results.
In fact, since file content is read from chunkservers, applications do not observe stale file content. What could be stale within short windows is file metadata, like directory
contents or access control information.
To keep itself informed, a shadow master reads a replica of
the growing operation log and applies the same sequence of
changes to its data structures exactly as the primary does.
Like the primary, it polls chunkservers at startup (and infrequently thereafter) to locate chunk replicas and exchanges
frequent handshake messages with them to monitor their
status. It depends on the primary master only for replica
location updates resulting from the primary’s decisions to
create and delete replicas.
5.2 Data Integrity
Each chunkserver uses checksumming to detect corruption
of stored data. Given that a GFS cluster often has thousands
of disks on hundreds of machines, it regularly experiences
disk failures that cause data corruption or loss on both the
read and write paths. (See Section 7 for one cause.) We
can recover from corruption using other chunk replicas, but
it would be impractical to detect corruption by comparing
replicas across chunkservers. Moreover, divergent replicas
may be legal: the semantics of GFS mutations, in particular
atomic record append as discussed earlier, does not guarantee identical replicas. Therefore, each chunkserver must
independently verify the integrity of its own copy by maintaining checksums.
A chunk is broken up into 64 KB blocks. Each has a corresponding 32 bit checksum. Like other metadata, checksums
are kept in memory and stored persistently with logging,
separate from user data.
For reads, the chunkserver verifies the checksum of data
blocks that overlap the read range before returning any data
to the requester, whether a client or another chunkserver.
Therefore chunkservers will not propagate corruptions to
other machines. If a block does not match the recorded
checksum, the chunkserver returns an error to the requestor
and reports the mismatch to the master. In response, the
requestor will read from other replicas, while the master
will clone the chunk from another replica. After a valid new
replica is in place, the master instructs the chunkserver that
reported the mismatch to delete its replica.
Checksumming has little effect on read performance for
several reasons. Since most of our reads span at least a
few blocks, we need to read and checksum only a relatively
small amount of extra data for verification. GFS client code
further reduces this overhead by trying to align reads at
checksum block boundaries. Moreover, checksum lookups
and comparison on the chunkserver are done without any
I/O, and checksum calculation can often be overlapped with
I/Os.
Checksum computation is heavily optimized for writes
that append to the end of a chunk (as opposed to writes
that overwrite existing data) because they are dominant in
our workloads. We just incrementally update the checksum for the last partial checksum block, and compute new
checksums for any brand new checksum blocks filled by the
append. Even if the last partial checksum block is already
corrupted and we fail to detect it now, the new checksum
value will not match the stored data, and the corruption will
be detected as usual when the block is next read.
In contrast, if a write overwrites an existing range of the
chunk, we must read and verify the first and last blocks of
the range being overwritten, then perform the write, and finally compute and record the new checksums. If we do
not verify the first and last blocks before overwriting them
partially, the new checksums may hide corruption that exists
in the regions not being overwritten.
During idle periods, chunkservers can scan and verify the
contents of inactive chunks. This allows us to detect corruption in chunks that are rarely read. Once the corruption is
detected, the master can create a new uncorrupted replica
and delete the corrupted replica. This prevents an inactive
but corrupted chunk replica from fooling the master into
thinking that it has enough valid replicas of a chunk.
5.3 Diagnostic Tools
Extensive and detailed diagnostic logging has helped immeasurably in problem isolation, debugging, and performance analysis, while incurring only a minimal cost. Without logs, it is hard to understand transient, non-repeatable
interactions between machines. GFS servers generate diagnostic logs that record many significant events (such as
chunkservers going up and down) and all RPC requests and
replies. These diagnostic logs can be freely deleted without
affecting the correctness of the system. However, we try to
keep these logs around as far as space permits.
The RPC logs include the exact requests and responses
sent on the wire, except for the file data being read or written. By matching requests with replies and collating RPC
records on different machines, we can reconstruct the entire interaction history to diagnose a problem. The logs also
serve as traces for load testing and performance analysis.
The performance impact of logging is minimal (and far
outweighed by the benefits) because these logs are written
sequentially and asynchronously. The most recent events
are also kept in memory and available for continuous online
monitoring.
6. MEASUREMENTS
In this section we present a few micro-benchmarks to illustrate the bottlenecks inherent in the GFS architecture and
implementation, and also some numbers from real clusters
in use at Google.
6.1 Micro-benchmarks
We measured performance on a GFS cluster consisting
of one master, two master replicas, 16 chunkservers, and
16 clients. Note that this configuration was set up for ease
of testing. Typical clusters have hundreds of chunkservers
and hundreds of clients.
All the machines are configured with dual 1.4 GHz PIII
processors, 2 GB of memory, two 80 GB 5400 rpm disks, and
a 100 Mbps full-duplex Ethernet connection to an HP 2524
switch. All 19 GFS server machines are connected to one
switch, and all 16 client machines to the other. The two
switches are connected with a 1 Gbps link.
6.1.1 Reads
N clients read simultaneously from the file system. Each
client reads a randomly selected 4 MB region from a 320 GB
file set. This is repeated 256 times so that each client ends
up reading 1 GB of data. The chunkservers taken together
have only 32 GB of memory, so we expect at most a 10% hit
rate in the Linux buffer cache. Our results should be close
to cold cache results.
Figure 3(a) shows the aggregate read rate for N clients
and its theoretical limit. The limit peaks at an aggregate of
125 MB/s when the 1 Gbps link between the two switches
is saturated, or 12.5 MB/s per client when its 100 Mbps
network interface gets saturated, whichever applies. The
observed read rate is 10 MB/s, or 80% of the per-client
limit, when just one client is reading. The aggregate read
rate reaches 94 MB/s, about 75% of the 125 MB/s link limit,
for 16 readers, or 6 MB/s per client. The efficiency drops
from 80% to 75% because as the number of readers increases,
so does the probability that multiple readers simultaneously
read from the same chunkserver.
6.1.2 Writes
N clients write simultaneously to N distinct files. Each
client writes 1 GB of data to a new file in a series of 1 MB
writes. The aggregate write rate and its theoretical limit are
shown in Figure 3(b). The limit plateaus at 67 MB/s because we need to write each byte to 3 of the 16 chunkservers,
each with a 12.5 MB/s input connection.
The write rate for one client is 6.3 MB/s, about half of the
limit. The main culprit for this is our network stack. It does
not interact very well with the pipelining scheme we use for
pushing data to chunk replicas. Delays in propagating data
from one replica to another reduce the overall write rate.
Aggregate write rate reaches 35 MB/s for 16 clients (or
2.2 MB/s per client), about half the theoretical limit. As in
the case of reads, it becomes more likely that multiple clients
write concurrently to the same chunkserver as the number
of clients increases. Moreover, collision is more likely for 16
writers than for 16 readers because each write involves three
different replicas.
Writes are slower than we would like. In practice this has
not been a major problem because even though it increases
the latencies as seen by individual clients, it does not significantly affect the aggregate write bandwidth delivered by
the system to a large number of clients.
6.1.3 Record Appends
Figure 3(c) shows record append performance. N clients
append simultaneously to a single file. Performance is limited by the network bandwidth of the chunkservers that
store the last chunk of the file, independent of the number of clients. It starts at 6.0 MB/s for one client and drops
to 4.8 MB/s for 16 clients, mostly due to congestion and
variances in network transfer rates seen by different clients.
Our applications tend to produce multiple such files concurrently. In other words, N clients append to M shared
files simultaneously where both N and M are in the dozens
or hundreds. Therefore, the chunkserver network congestion
in our experiment is not a significant issue in practice because a client can make progress on writing one file while
the chunkservers for another file are busy.
6.2 Real World Clusters
We now examine two clusters in use within Google that
are representative of several others like them. Cluster A is
used regularly for research and development by over a hundred engineers. A typical task is initiated by a human user
and runs up to several hours. It reads through a few MBs
to a few TBs of data, transforms or analyzes the data, and
writes the results back to the cluster. Cluster B is primarily
used for production data processing. The tasks last much longer and continuously generate and process multi-TB data
sets with only occasional human intervention. In both cases,
a single “task” consists of many processes on many machines
reading and writing many files simultaneously.
6.2.1 Storage
As shown by the first five entries in the table, both clusters
have hundreds of chunkservers, support many TBs of disk
space, and are fairly but not completely full. “Used space”
includes all chunk replicas. Virtually all files are replicated
three times. Therefore, the clusters store 18 TB and 52 TB
of file data respectively.
The two clusters have similar numbers of files, though B
has a larger proportion of dead files, namely files which were
deleted or replaced by a new version but whose storage have
not yet been reclaimed. It also has more chunks because its
files tend to be larger.
6.2.2 Metadata
The chunkservers in aggregate store tens of GBs of metadata, mostly the checksums for 64 KB blocks of user data.
The only other metadata kept at the chunkservers is the
chunk version number discussed in Section 4.5.
The metadata kept at the master is much smaller, only
tens of MBs, or about 100 bytes per file on average. This
agrees with our assumption that the size of the master’s
memory does not limit the system’s capacity in practice.
Most of the per-file metadata is the file names stored in a
prefix-compressed form. Other metadata includes file ownership and permissions, mapping from files to chunks, and
each chunk’s current version. In addition, for each chunk we
store the current replica locations and a reference count for
implementing copy-on-write.
Each individual server, both chunkservers and the master,
has only 50 to 100 MB of metadata. Therefore recovery is
fast: it takes only a few seconds to read this metadata from
disk before the server is able to answer queries. However, the
master is somewhat hobbled for a period – typically 30 to
60 seconds – until it has fetched chunk location information
from all chunkservers.
6.2.3 Read and Write Rates
Table 3 shows read and write rates for various time periods. Both clusters had been up for about one week when
these measurements were taken. (The clusters had been
restarted recently to upgrade to a new version of GFS.)
The average write rate was less than 30 MB/s since the
restart. When we took these measurements, B was in the
middle of a burst of write activity generating about 100 MB/s
of data, which produced a 300 MB/s network load because
writes are propagated to three replicas.
The read rates were much higher than the write rates.
The total workload consists of more reads than writes as we
have assumed. Both clusters were in the middle of heavy
read activity. In particular, A had been sustaining a read
rate of 580 MB/s for the preceding week. Its network configuration can support 750 MB/s, so it was using its resources efficiently. Cluster B can support peak read rates of
1300 MB/s, but its applications were using just 380 MB/s.
6.2.4 Master Load
Table 3 also shows that the rate of operations sent to the
master was around 200 to 500 operations per second. The
master can easily keep up with this rate, and therefore is
not a bottleneck for these workloads.
In an earlier version of GFS, the master was occasionally
a bottleneck for some workloads. It spent most of its time
sequentially scanning through large directories (which contained hundreds of thousands of files) looking for particular
files. We have since changed the master data structures to
allow efficient binary searches through the namespace. It
can now easily support many thousands of file accesses per
second. If necessary, we could speed it up further by placing
name lookup caches in front of the namespace data structures.
6.2.5 Recovery Time
After a chunkserver fails, some chunks will become underreplicated and must be cloned to restore their replication
levels. The time it takes to restore all such chunks depends
on the amount of resources. In one experiment, we killed a
single chunkserver in cluster B. The chunkserver had about 15,000 chunks containing 600 GB of data. To limit the impact on running applications and provide leeway for scheduling decisions, our default parameters limit this cluster to
91 concurrent clonings (40% of the number of chunkservers)
where each clone operation is allowed to consume at most
6.25 MB/s (50 Mbps). All chunks were restored in 23.2 minutes, at an effective replication rate of 440 MB/s.
In another experiment, we killed two chunkservers each
with roughly 16,000 chunks and 660 GB of data. This double
failure reduced 266 chunks to having a single replica. These
266 chunks were cloned at a higher priority, and were all
restored to at least 2x replication within 2 minutes, thus
putting the cluster in a state where it could tolerate another
chunkserver failure without data loss.
6.3 Workload Breakdown
In this section, we present a detailed breakdown of the
workloads on two GFS clusters comparable but not identical to those in Section 6.2. Cluster X is for research and
development while cluster Y is for production data processing.
6.3.1 Methodology and Caveats
These results include only client originated requests so
that they reflect the workload generated by our applications
for the file system as a whole. They do not include inter-server requests to carry out client requests or internal background activities, such as forwarded writes or rebalancing.
Statistics on I/O operations are based on information
heuristically reconstructed from actual RPC requests logged
by GFS servers. For example, GFS client code may break a
read into multiple RPCs to increase parallelism, from which
we infer the original read. Since our access patterns are
highly stylized, we expect any error to be in the noise. Explicit logging by applications might have provided slightly
more accurate data, but it is logistically impossible to recompile and restart thousands of running clients to do so
and cumbersome to collect the results from as many machines.
One should be careful not to overly generalize from our
workload. Since Google completely controls both GFS and
its applications, the applications tend to be tuned for GFS,
and conversely GFS is designed for these applications. Such
mutual influence may also exist between general applications and file systems, but the effect is likely more pronounced in
our case.
6.3.2 Chunkserver Workload
Table 4 shows the distribution of operations by size. Read
sizes exhibit a bimodal distribution. The small reads (under 64 KB) come from seek-intensive clients that look up
small pieces of data within huge files. The large reads (over
512 KB) come from long sequential reads through entire
files.
A significant number of reads return no data at all in cluster Y. Our applications, especially those in the production
systems, often use files as producer-consumer queues. Producers append concurrently to a file while a consumer reads
the end of file. Occasionally, no data is returned when the
consumer outpaces the producers. Cluster X shows this less
often because it is usually used for short-lived data analysis
tasks rather than long-lived distributed applications.
Write sizes also exhibit a bimodal distribution. The large
writes (over 256 KB) typically result from significant buffering within the writers. Writers that buffer less data, checkpoint or synchronize more often, or simply generate less data
account for the smaller writes (under 64 KB).
As for record appends, cluster Y sees a much higher percentage of large record appends than cluster X does because
our production systems, which use cluster Y, are more aggressively tuned for GFS.
Table 5 shows the total amount of data transferred in operations of various sizes. For all kinds of operations, the
larger operations (over 256 KB) generally account for most
of the bytes transferred. Small reads (under 64 KB) do
transfer a small but significant portion of the read data because of the random seek workload.
6.3.3 Appends versus Writes
Record appends are heavily used especially in our production systems. For cluster X, the ratio of writes to record
appends is 108:1 by bytes transferred and 8:1 by operation
counts. For cluster Y, used by the production systems, the
ratios are 3.7:1 and 2.5:1 respectively. Moreover, these ratios suggest that for both clusters record appends tend to
be larger than writes. For cluster X, however, the overall
usage of record append during the measured period is fairly
low and so the results are likely skewed by one or two applications with particular buffer size choices.
As expected, our data mutation workload is dominated
by appending rather than overwriting. We measured the
amount of data overwritten on primary replicas. This approximates the case where a client deliberately overwrites
previous written data rather than appends new data. For
cluster X, overwriting accounts for under 0.0001% of bytes
mutated and under 0.0003% of mutation operations. For
cluster Y, the ratios are both 0.05%. Although this is minute,
it is still higher than we expected. It turns out that most
of these overwrites came from client retries due to errors or
timeouts. They are not part of the workload per se but a
consequence of the retry mechanism.
6.3.4 Master Workload
Table 6 shows the breakdown by type of requests to the
master. Most requests ask for chunk locations (FindLocation) for reads and lease holder information (FindLeaseLocker) for data mutations.
Clusters X and Y see significantly different numbers of
Delete requests because cluster Y stores production data
sets that are regularly regenerated and replaced with newer
versions. Some of this difference is further hidden in the
difference in Open requests because an old version of a file
may be implicitly deleted by being opened for write from
scratch (mode “w” in Unix open terminology).
FindMatchingFiles is a pattern matching request that supports “ls” and similar file system operations. Unlike other
requests for the master, it may process a large part of the
namespace and so may be expensive. Cluster Y sees it much
more often because automated data processing tasks tend to
examine parts of the file system to understand global application state. In contrast, cluster X’s applications are under
more explicit user control and usually know the names of all
needed files in advance.
7. EXPERIENCES
In the process of building and deploying GFS, we have
experienced a variety of issues, some operational and some
technical.
Initially, GFS was conceived as the backend file system
for our production systems. Over time, the usage evolved
to include research and development tasks. It started with
little support for things like permissions and quotas but now
includes rudimentary forms of these. While production systems are well disciplined and controlled, users sometimes
are not. More infrastructure is required to keep users from
interfering with one another.
Some of our biggest problems were disk and Linux related.
Many of our disks claimed to the Linux driver that they
supported a range of IDE protocol versions but in fact responded reliably only to the more recent ones. Since the protocol versions are very similar, these drives mostly worked,
but occasionally the mismatches would cause the drive and
the kernel to disagree about the drive’s state. This would
corrupt data silently due to problems in the kernel. This
problem motivated our use of checksums to detect data corruption, while concurrently we modified the kernel to handle
these protocol mismatches.
Earlier we had some problems with Linux 2.2 kernels due
to the cost of fsync(). Its cost is proportional to the size
of the file rather than the size of the modified portion. This
was a problem for our large operation logs especially before
we implemented checkpointing. We worked around this for
a time by using synchronous writes and eventually migrated
to Linux 2.4.
Another Linux problem was a single reader-writer lock
which any thread in an address space must hold when it
pages in from disk (reader lock) or modifies the address
space in an mmap() call (writer lock). We saw transient
timeouts in our system under light load and looked hard for
resource bottlenecks or sporadic hardware failures. Eventually, we found that this single lock blocked the primary
network thread from mapping new data into memory while
the disk threads were paging in previously mapped data.
Since we are mainly limited by the network interface rather
than by memory copy bandwidth, we worked around this by
replacing mmap() with pread() at the cost of an extra copy.
Despite occasional problems, the availability of Linux code
has helped us time and again to explore and understand
system behavior. When appropriate, we improve the kernel
and share the changes with the open source community.
8. RELATED WORK
Like other large distributed file systems such as AFS [5],
GFS provides a location independent namespace which enables data to be moved transparently for load balance or
fault tolerance. Unlike AFS, GFS spreads a file’s data across
storage servers in a way more akin to xFS [1] and Swift [3] in
order to deliver aggregate performance and increased fault
tolerance.
As disks are relatively cheap and replication is simpler
than more sophisticated RAID [9] approaches, GFS currently uses only replication for redundancy and so consumes
more raw storage than xFS or Swift.
In contrast to systems like AFS, xFS, Frangipani [12], and
Intermezzo [6], GFS does not provide any caching below the
file system interface. Our target workloads have little reuse
within a single application run because they either stream
through a large data set or randomly seek within it and read
small amounts of data each time.
Some distributed file systems like Frangipani, xFS, Minnesota’s GFS[11] and GPFS [10] remove the centralized server and rely on distributed algorithms for consistency and management. We opt for the centralized approach in order to
simplify the design, increase its reliability, and gain flexibility. In particular, a centralized master makes it much easier
to implement sophisticated chunk placement and replication
policies since the master already has most of the relevant
information and controls how it changes. We address fault
tolerance by keeping the master state small and fully replicated on other machines. Scalability and high availability
(for reads) are currently provided by our shadow master
mechanism. Updates to the master state are made persistent by appending to a write-ahead log. Therefore we could
adapt a primary-copy scheme like the one in Harp [7] to provide high availability with stronger consistency guarantees
than our current scheme.
We are addressing a problem similar to Lustre [8] in terms
of delivering aggregate performance to a large number of
clients. However, we have simplified the problem significantly by focusing on the needs of our applications rather
than building a POSIX-compliant file system. Additionally,
GFS assumes large number of unreliable components and so
fault tolerance is central to our design.
GFS most closely resembles the NASD architecture [4].
While the NASD architecture is based on network-attached
disk drives, GFS uses commodity machines as chunkservers,
as done in the NASD prototype. Unlike the NASD work,
our chunkservers use lazily allocated fixed-size chunks rather
than variable-length objects. Additionally, GFS implements
features such as rebalancing, replication, and recovery that
are required in a production environment.
Unlike Minnesota’s GFS and NASD, we do not seek to
alter the model of the storage device. We focus on addressing day-to-day data processing needs for complicated
distributed systems with existing commodity components.
The producer-consumer queues enabled by atomic record
appends address a similar problem as the distributed queues
in River [2]. While River uses memory-based queues distributed across machines and careful data flow control, GFS
uses a persistent file that can be appended to concurrently
by many producers. The River model supports m-to-n distributed queues but lacks the fault tolerance that comes with
persistent storage, while GFS only supports m-to-1 queues
efficiently. Multiple consumers can read the same file, but
they must coordinate to partition the incoming load.
9. CONCLUSIONS
The Google File System demonstrates the qualities essential for supporting large-scale data processing workloads
on commodity hardware. While some design decisions are
specific to our unique setting, many may apply to data processing tasks of a similar magnitude and cost consciousness.
We started by reexamining traditional file system assumptions in light of our current and anticipated application
workloads and technological environment. Our observations
have led to radically different points in the design space.
We treat component failures as the norm rather than the
exception, optimize for huge files that are mostly appended
to (perhaps concurrently) and then read (usually sequentially), and both extend and relax the standard file system
interface to improve the overall system.
Our system provides fault tolerance by constant monitoring, replicating crucial data, and fast and automatic recovery. Chunk replication allows us to tolerate chunkserver failures. The frequency of these failures motivated a novel
online repair mechanism that regularly and transparently repairs the damage and compensates for lost replicas as soon
as possible. Additionally, we use checksumming to detect
data corruption at the disk or IDE subsystem level, which
becomes all too common given the number of disks in the
system.
Our design delivers high aggregate throughput to many
concurrent readers and writers performing a variety of tasks.
We achieve this by separating file system control, which
passes through the master, from data transfer, which passes
directly between chunkservers and clients. Master involvement in common operations is minimized by a large chunk
size and by chunk leases, which delegates authority to primary replicas in data mutations. This makes possible a simple, centralized master that does not become a bottleneck.
We believe that improvements in our networking stack will
lift the current limitation on the write throughput seen by
an individual client.
GFS has successfully met our storage needs and is widely
used within Google as the storage platform for research and
development as well as production data processing. It is an
important tool that enables us to continue to innovate and
attack problems on the scale of the entire web.
