Let's return now to map-reduce and ask where the data that map-reduce program
require is written, is taking from and where does the output go?
Clearly, map-reduce reads and writes fresh data, right?
As we've seen before, it's a batch process.
The question is, where does it read this data from, and where does it write the
output to? Even if map-reduces and parallel computing
paradigm, what about the data read and write?
Does that form a potential bottleneck? The solution is that the data itself needs
to lie in a distributed format, whether it's a distributed file system or a
database so that we can support parallel reading and writing.
So, that more than one processor is active reading or writing a large file.
Otherwise, input and output itself will become a bottleneck for the map-reduce
parallel computing program. Further, we have discussed processing node
failures, and seen how map-reduce recovers from these without letting the overall map
reduce job fail. But, what if the nodes on which data is
stored failed, they also need to be fall tolerant.
To solve both these problems, distributed file systems were developed primarily
first by Google, and then Yahoo and that's what we are going to study next.
This diagram illustrates the architecture of the, distributed file systems, both the
Google file system as well as the, Hadoop Distributed File System which is Open
Source now, and is essentially the foundation of what is big data technology
wherever it's used. Whether there is a database built on it or
used directly, the HDFS is fundamental to big data.
This is how it works. Large files are distributed into chunks,
typically, of 64 megabytes in size and each of these chunks is stored on what is
called chunk servers. Further, chunk servers are replicated so
that each chunk is stored on three different servers, typically replicated on
multiple racks and in a different network subnet, to take care of all types of
hardware failures. As a result of this replication, the
possibility of data being lost due to hardware failure is minimized
significantly. Of course, the challenge is now to
maintain consistency across all these replicas.
So, here is how that works. When a client application, say, a
map-reduce program, needs to read data, it needs to first figure out where a
particular piece of data resides. A read command typically is issued with a
file name which is a, a path in the directory structure.
And an offset, that is how many bytes ahead in, in the file, the client wants to
read. Data about what parts of a file are on
which chunk server is kept in a master node which is called the Master GFS and
it's called the name node in HDFS, and the client reads the metadata from this master
node. The metadata tells it where the particular
offset that it is asking for resides that is which chunk server.
The metadata itself is cached by the client when it first starts reading so
that it doesn't continuously have to go and ask the name node or the master for
information. Further, while actually reading data, the
client directly contacts the chunk server, which is listening for such requests, and
serves up requests for a particular chunks of data from a file, rather than go
through any centralized systems. So, if there are many clients reading a
large file, typically, they will be accessing different junk servers, and
therefore, these reads are happening in parallel.
And the result input at least doesn't become a bottleneck in a parallel map
reduce job. In case the reading client that is a
mapper fails, to contact the chunk server, it looks up to the master data to figure
out where the next replica is stored and tries again.
Since there are three replicas, the chance of all of them failing is fairly low and
that lends fall tolerance to the input, output process.
Of course, the tricky part comes in writing because while writing data, we
have to main, make, make sure that the, each replica contains the same data all
the time. Here is how writes happen in GFS.
Of the three replicas for each chunk, one is designated as the primary replica.
Could be any one, and that information is kept in the master.
Of course, the master keeps pinging these replicas to make sure that they are alive.
And in case, the primary is down for some reason the master node assigns a new
primary, and possibly even asks for a new replica to be created for that chunk.
Now, when writing data, the client application sends the data to be written
to all three replicas for a particular chunk.
One of them is primary, and it figures out where to write this data, assigns an
offset to write the data, such as typically the end of file, and sends this
offset to the other two replicas. If these replicas succeed in writing at
that particular point, they tell the primary that they have written, and the
write succeeds with the primary informing the client that the operation has
successfully completed. On the other hand, if some of the replicas
failed to write at the designated offset, which can happen, for example, because of
a bad disc sector. Then, they return a failure to the
primary, and the primary retries to write at another offset, could be beyond the end
of the file, for example, and tries again until it succeeds at all replicas.
As a result of this process, large bulk writes can be done in parallel on a large
file by multiple processors, typically reducers, writing the output of a
map-reduce job, while still ensuring that three replicas of every chunk are
maintained synchronously and with the same state.
Gfs and HDFS are the foundation for all big data technology.
Gfs, of course, is proprietary to Google, and is internally used.
Hdfs was developed at Yahoo, and opened sourced as part of the Hadoop Distribution
and has now become, and has now become synonymous with map-reduce and large scale
computing using big data. So, to summarize, what the GFS distributed
file system architecture is really good at is supporting multiple, parallel reads and
writes from a large number of processors. The reads are arbitrary and random access
but the writes are best done when they are appends or writing to the end of a large
file. Because the architecture relies on the
primary replica for a chunk deciding the order, in which multiple append requests
are processed. The data is always consistent, though not
necessarily predictable in terms of which processor data is written first.
That normally doesn't matter because the data is fairly independent, especially in
map-reduced output. At the same time, it's important to
realize that random writes in the middle of some file, while can be handled using
the GFS architecture, exactly the same way as we have described, are not as efficient
as bulk writes towards the end of the file.
Imagine a large number of reducers writing their output to a file, which will
eventually become large. As soon as a reducer decides to write say
64 MB chunk, it has to figure out that this is going to be a new chunk.
And inform the master or the name node, that it's writing a new chunk.
Similarly, other reducers figure out that they're writing new chunks, and inform the
master. The master's updates its metadata, and all
the writes happen in parallel. The master does become a bit of a
bottleneck, but because the writes are fairly large, that doesn't normally create
a problem. On the other hand, if we have random
writes to the middle of a file, The challenge then becomes, what happens when
a chunk essentially overflows and impinges on another, next, the next chunk in the
file. This can create problems in the way the
file is laid out and requires much more synchronization.
Without going into too much detail, it's also shown in the paper on GFS that the
degree of replica consistency that one gets with large bulk of pens is much
stronger than the degree of replica consistency than we get with random writes
and parallel. Nonetheless even with a reduced degree of
consistencies, each reader, in the GFS architecture always sees a consistent data
regardless of which replica it ends up reading from.
That's one of the powers of the GFS architecture.
Still, GFS and HDFS, while supporting bulk parallel reads and writes are nevertheless
file system architectures and not databases as we have come to understand
them over the past 30 to 40 years. Much of the current debate in the big data
and traditional BI communities is about databases.
The big data databases are built on top of distributed file systems llike GFS and
HDFS. But before we turn to these, let's first
take a look at traditional databases and see why they were developed and how
they've actually been used.