The Google File System

wangfans

4. Once all the replicas have acknowledged receiving the
data, the client sends a write request to the primary.
The request identifies the data pushed earlier to all of
the replicas. The primary assigns consecutive serial
numbers to all the mutations it receives, possibly from
multiple clients, which provides the necessary serialization.
It applies the mutation to its own local state
in serial number order.

wangfans

5. The primary forwards the write request to all secondary
replicas. Each secondary replica applies mutations
in the same serial number order assigned by
the primary.

wangfans

6. The secondaries all reply to the primary indicating
that they have completed the operation.
7. The primary replies to the client. Any errors encountered
at any of the replicas are reported to the client.
In case of errors, the write may have succeeded at the
primary and an arbitrary subset of the secondary replicas.
(If it had failed at the primary, it would not
have been assigned a serial number and forwarded.)
The client request is considered to have failed, and the
modified region is left in an inconsistent state. Our
client code handles such errors by retrying the failed
mutation. It will make a few attempts at steps (3)
through (7) before falling backt o a retry from the beginning
of the write.

wangfans

If a write by the application is large or straddles a chunk
boundary, GFS client code breaks it down into multiple
write operations. They all follow the control flow described
above but may be interleaved with and overwritten by concurrent
operations from other clients. Therefore, the shared

wangfans

file region may end up containing fragments from different
clients, although the replicas will be identical because the individual
operations are completed successfully in the same
order on all replicas. This leaves the file region in consistent
but undefined state as noted in Section 2.7.

wangfans

3.2 Data Flow
We decouple the flow of data from the flow of control to
use the networke fficiently. While control flows from the
client to the primary and then to all secondaries, data is
pushed linearly along a carefully picked chain of chunkservers
in a pipelined fashion. Our goals are to fully utilize each
machine’s networkb andwidth, avoid network bottlenecks
and high-latency links, and minimize the latency to push
through all the data.

wangfans

To fully utilize each machine’s networkb andwidth, the
data is pushed linearly along a chain of chunkservers rather
than distributed in some other topology (e.g., tree). Thus,
each machine’s full outbound bandwidth is used to transfer
the data as fast as possible rather than divided among
multiple recipients.

wangfans

To avoid network bottlenecks and high-latency links (e.g.,
inter-switch links are often both) as much as possible, each
machine forwards the data to the “closest” machine in the
networkto pology that has not received it. Suppose the
client is pushing data to chunkservers S1 through S4.

wangfans

It
sends the data to the closest chunkserver, say S1. S1 forwards
it to the closest chunkserver S2 through S4 closest to
S1, say S2. Similarly, S2 forwards it to S3 or S4, whichever
is closer to S2, and so on. Our networkt opology is simple
enough that “distances” can be accurately estimated from
IP addresses.

wangfans

Finally, we minimize latency by pipelining the data transfer
over TCP connections. Once a chunkserver receives some
data, it starts forwarding immediately. Pipelining is especially
helpful to us because we use a switched networkwit h
full-duplex links. Sending the data immediately does not
reduce the receive rate.