Understanding Google's File System (2020)(micahlerner.com)

Understanding Google's File System (2020)

https://www.micahlerner.com/2020/03/22/understanding-googles-file-system.html

42 comments

The key thing to understand about GFS and relatives is how essential it is for distributed computation.

It is natural for us to look at a big file and think, "I need to do something complicated, so I'll do a distributed calculation, then get a new file." This makes the file you start with, and the file you wind up with, both bottlenecks to the calculation.

Instead you really want to have data distributed across machines. Now do a distributed map-reduce calculations, and get another distributed dataset. Then create a pipeline of such calculations. Leading to a distributed calculation with no bottlenecks. Anywhere.

(Of course this is a low-level view of how it works. We may want to build that pipeline automatically off of, say, a SQL statement. To get a distributed query against a datastore.)

Absolutely essential for this is the ability to have a distributed, replicated, filesystem. This is what GFS was. When you try to scale a system, you focus on your current bottlenecks, and accept that there will be later ones. GFS did not distribute metadata. It did not play well with later systems created for managing distributed machines. But it was an important step towards a distributed world. And the fact that Google was so far ahead of everyone else on this was a giant piece of their secret sauce.

True story. I went to Google at about the same time that eBay shut down their first datacenter. So I was reading an article from eBay about how more work it took to shut down a datacenter without disrupting operations. And how proud they are at succeeding. And then I saw the best practices that Google was using so that users wouldn't notice if a random datacenter went offline without warning. Which was a capacity that Google regularly tested. Because if you're afraid to test your emergency systems, they probably don't work.

What eBay was proud of doing with a lot of work, was entirely taken for granted and automated at Google.

pclmulqdq2년 전

I'm biased because I did some work on Colossus for a few years, but it's my opinion that Google's main advantage in its ability to build complex distributed systems is Colossus (and GFS). The Colossus layer is the point where a lot of systems actually take care of the CAP theorem, and because Colossus does it so well they almost don't have to worry about it at all.

Ceph, Hadoop, scale-out ZFS, and others that came afterward got the idea of distributing a filesystem but sort of missed the point that GFS/Colossus's great advantage was that it's so damn good at being a distributed system, and has been tried and tested through a lot of different kinds of failure modes.

tdba2년 전

Link to any resources you consider valuable for learning about Colossus?

pclmulqdq2년 전

Sadly, the best public material is the technical marketing for GCP, see the following for example (a few other materials can be found in this comments section):

https://cloud.google.com/blog/products/storage-data-transfer...

If you want to learn about modern exascale filesystems, the best paper today is probably from Facebook:

https://www.usenix.org/conference/fast21/presentation/pan

jeffbee2년 전

> you really want to have data distributed across machines

It's funny how poorly Hadoop, HDFS, and HBase learned this lesson. HBase tries to keep a replica of its data on the local machine, under the incorrect belief that a local RegionServer (approx: chunk server) will be somehow better than a building full of them. This is why HBase performance is hideous. But it is all supposedly inspired by or modeled after GFS and Bigtable?

jimbokun2년 전

Hadoop and family fell squarely in the category of something where I always felt I was missing something important. Because it was being discussed everywhere, but I could never match it up with a problem I needed to solve, even though we were dealing with other “big data” systems.

woooooo2년 전

If I recall correctly, hbase performance problems had a lot to do with jdk 1.6 garbage collection, rather than the data location strategy.

woooooo2년 전

One interesting idea that got lost in the last 10 years was "push compute to the data", saving a network transfer.

It seems like these days most systems prefer the flexibility of separate data/compute and are willing to pay the network tax for it.

the-rc2년 전

BigTable did have coprocessors, but they were only ever described with not a lot of detail in a Jeff Dean talk. That didn't stop HBase from implementing their own take. See https://www.cs.cornell.edu/projects/ladis2009/talks/dean-key...

jeffbee2년 전

It wasn't an interesting idea, it was a footgun. There's nothing naturally advantageous about the machine your process happens to be running on. In the era of very large machines there may be substantial contention for the block device that by coincidence is in the same chassis as your CPU.

woooooo2년 전

It's a footgun if your cluster is providing data/compute to other systems, absolutely, the case you mentioned is a risk worth extra network traffic to avoid.

But theoretically, if we're trying to beat a benchmark or something, the "move compute to data" idea has something to it. Nobody transfers the LLM weights off of card memory, let alone to other machines for compute.

mbreese2년 전

It was useful at the time though. Both network and disk were substantially slower at the time. And servers had far fewer cores. So which server stored the data could make your processing faster. And you’d have less risk for IO contention within the same chassis.

Fast forward a few years and compute servers can have hundreds of cores and the network is significantly faster.

I think it was a “good enough” design for the time and those assumptions. And batch processing. Now? I think there are different assumptions to be made.

(And I think there is a good argument that by the time Hadoop/HDFS had stabilized the assumptions had already shifted)

woadwarrior012년 전

It's still around in things like Spanner. Although, compute and storage are mostly disaggregated into different classes of servers now.

DonHopkins2년 전

It got lost a lot longer than 10 years ago. Sun published the NFS 3 spec (NeFS -- Network extensible File System) 34 years ago in 1990, which was in turn based on John Warnock's earlier ideas of using PostScript as a "linguistic motherboard" with "slots" for different kinds of "cards" like graphics and file systems (drawing from his experience at Adobe and Xerox PARC):

        PostScript is a linguistic "mother board", which has "slots"
        for several "cards".  The first card we (Adobe) built was a
        graphics card.  We're considering other cards.  In particular,
        we've thought about other network services, such as a file
        server card.

https://news.ycombinator.com/item?id=34256293

[...]

DonHopkins on Sept 5, 2019 | parent | context | favorite | on: Samsung Announces Key-Value SSD Prototype

It's like NFS 3 (NeFS) in hardware! (NeWS for disks: A PostScript interpreter in the kernel as a file system API.)

https://www.donhopkins.com/home/nfs3_0.pdf

Network Extensible File System Protocol Specification (2/12/90)

Comments to: sun!nfs3 [email protected]

Sun Microsystems, Inc. 2550 Garcia Ave. Mountain View, CA 94043

1.0 Introduction

The Network Extensible File System protocol (NeFS) provides transparent remote access to shared file systems over networks. The NeFS protocol is designed to be machine, operating system, network architecture, and transport protocol independent. This document is the draft specification for the protocol. It will remain in draft form during a period of public review. Italicized comments in the document are intended to present the rationale behind elements of the design and to raise questions where there are doubts. Comments and suggestions on this draft specification are most welcome.

[...]

Although it has features in common with NFS, NeFS is a radical departure from NFS. The NFS protocol is built according to a Remote Procedure Call model (RPC) where filesystem operations are mapped across the network as remote procedure calls. The NeFS protocol abandons this model in favor of an interpretive model in which the filesystem operations become operators in an interpreted language. Clients send their requests to the server as programs to be interpreted. Execution of the request by the server’s interpreter results in the filesystem operations being invoked and results returned to the client. Using the interpretive model, filesystem operations can be defined more simply. Clients can build arbitrarily complex requests from these simple operations.

[...]

https://news.ycombinator.com/item?id=22456710

DonHopkins on March 1, 2020 | parent | context | favorite | on: Sun's NeWS was a mistake, as are all toolkit-in-se...

Owen Densmore recounted John Warnock's idea that PostScript was actually a "linguistic motherboard". (This was part of a discussion with Owen about NeFS, which was a proposal for the next version of NFS to run a PostScript interpreter in the kernel. More about that here:)

https://news.ycombinator.com/item?id=17077721

Owen Densmore's discussion of John Warnock's "Linguistic Motherboard" idea for PostScript:

https://donhopkins.com/home/archive/NeWS/linguistic-motherbo...

    Date: Tue, 20 Feb 90 15:20:52 PST
    From: [email protected] (Owen Densmore)
    To: [email protected]
    Subject: Re:  NeFS

    > They changed the meaning of some of the standard PostScript operators,
    > like read and write, which I don't think was a good idea, for several
    > reasons... They should have used different names, or at least made ..

    Agreed.  And I DO see reasons for the old operators.  They could
    be optimized as a local cache for NeFS to use in its own calcs.

    > Basically, NeFS is a *particular* application of an abstraction of
    > NeWS. The abstract idea is that of having a server with a dynamically
    > extensible interpreter as an interface to whatever library or resource
    > you want to make available over the network (let's call it a generic
    > Ne* server).

    Very true.  This has been particularly difficult for me to get across
    to others here at Sun.  I recently wrote it up for Steve MacKay and
    include it at the end of the message.

    > It's not clear to me if NeFS supports multiple light weight PostScript
    > processes like NeWS.

    I asked Brent about this, and he agreed that it's an issue.  Brent
    has been talking to a guy here who's interested in re-writing the
    NeWS interpreter to be much easier to program and debug.  I'd love
    to see them come up with a NeWS Core that could be used as a generic
    NetWare core.

    I think you should send  your comments off to nfs3 & see what happens!
    I agree with most of your points.

    Owen

    Here's the memo I consed up for MacKay:

More:

https://news.ycombinator.com/item?id=22456710

alt2272년 전

If anything, the interview that this was based on is from 2009 and was a much more interesting read for myself:

https://queue.acm.org/detail.cfm?id=1594206

jeffbee2년 전

(2020) isn't quite enough to clue the reader in that GFS was extirpated at Google more than a decade ago. Historical trivia only.

tivert2년 전

> (2020) isn't quite enough to clue the reader in that GFS was extirpated at Google more than a decade ago. Historical trivia only.

Do you have more info about that? I was just Googling and found this:

https://pdos.csail.mit.edu/6.824/papers/gfs-faq.txt

> Q: Does Google still use GFS?

> A: Rumor has it that GFS has been replaced by something called Colossus, with the same overall goals, but improvements in master performance and fault-tolerance. In addition, many applications within Google have switched to more database-like storage systems such as BigTable and Spanner. However, much of the GFS design lives on in HDFS, the storage system for the Hadoop open-source MapReduce.

> https://cloud.google.com/blog/products/storage-data-transfer...

kccqzy2년 전

At Google the project to migrate GFS to Colossus was called Moonshot. It was endorsed by Eric Schmidt and became a top-down mandate. This goes into details of the migration: https://sre.google/static/pdf/CaseStudiesInfrastructureChang... (scroll to Chapter 1)

rkagerer2년 전

Thanks. This stat from the section on Diskless is interesting:

On shared machines, spinning disk reliability decreased compute reliability; 25%–30% of production task deaths were attributable to disk failure.

nosefrog2년 전

> In addition, many applications within Google have switched to more database-like storage systems such as BigTable and Spanner.

And where do BigTable and Spanner store their data? ;)

dist-epoch2년 전

BigTable stores it's data in Colossus, but Colossus stores it's metadata in BigTable :)

kristjansson2년 전

And Colossus stores its metametametadata in Chubby :)

https://www.pdsw.org/pdsw-discs17/slides/PDSW-DISCS-Google-K...

summerlight2년 전

Interestingly, Colossus was initially designed to be the next generation BigTable storage. It turned out that other teams had a similar problem, so it has become a more general file system.

ithkuil2년 전

Turns out that big table is also useful to implement the storage layer for big table itself. Luckily turtles can be stacked on top of each others

jeffbee2년 전

There is almost nothing public about Colossus. Here's some marketing fluff, but it's clear that Colossus is the successor to GFS and they compare scale (CFS >> GFS). https://cloud.google.com/blog/products/storage-data-transfer...

Also this slide deck https://www.pdsw.org/pdsw-discs17/slides/PDSW-DISCS-Google-K...

joatmon-snoo2년 전

If you do the math for GFS, there are some scaling limits that make it quite evident how long ago Google had to leave GFS :)

pclmulqdq2년 전

Colossus retains a lot of the ideas of GFS, so I wouldn't say that this paper is completely outdated. I would recommend the Tectonic paper from Facebook for a more modern distributed filesystem example:

https://www.usenix.org/conference/fast21/presentation/pan

AtomicOrbital2년 전

It's understandable hyper scalers roll their own infrastructure tools yet naturally small shops reach for 3rd party tools ... it's telling when speaking with each how justified each feels ... yet at the boundary zone between those extremes folks it gets interesting ... mid sized shops need to be aware of the benefits of rolling their own and at a minimum not frown on job candidates coming from a big shop who instinctively lean towards build versus just use off the shelf libs

y04nn2년 전

Does anybody know if there is any usage/implementation of a distributed hash table (with consistent hashing) for reliable file storage in a datacenter instead of internet p2p ? Would that make sense and what would be the drawbacks ?

dekhn2년 전

GFS was terrible. It may have been great in the early days of google when they couldn't build an index, but I recall having to bribe hwops people (with single-malt) to upgrade RAM on the GFS masters, and a few times, my team (Ads) threatened to run our own filesystems that didn't fail so badly.

Colossus, on the other hand, is really good.

tytso2년 전

Single malt was the currency of choice when bribing and/or placating SRE's and hwops folks. For example, if a SWE botched a rollout that caused a multiple SRE's to get paged at 3am, a bottle of single malt donated to the SRE bar was considered a way of apologizing.

windenntw2년 전

Single Malt, specially Islays, are still very much welcomed :)

the-rc2년 전

Among other things, GFS ran outside of Borg, so you couldn't just donate quota to let it run with more resources, as you found out. Conversely, given that Colossus ran on Borg, part of the migration involved an elaborate system that minted CPU/RAM quota for the storage system users whenever the CFS cell was grown. Then there were all the issues on the low end machines (hello, Nocona) that had not enough resources to run the storage stack AND user jobs. Stuff wouldn't schedule (and the cluster suddenly appeared to be missing some disk), but at least that was a lot more explicit than the performance issues you witnessed on GFS.

robertlagrant2년 전

> part of the migration involved an elaborate system that minted CPU/RAM quota for the storage system users whenever the CFS cell was grown

I've no idea what this is, but it sounds fascinating. Was this a way to auto-allocate more resource based on rules?

the-rc2년 전

Instead of using five masters like GFS, which typically ran on five machines dedicated to the purpose, Colossus uses a variable number of so called curators to handle all the metadata work (think of directory entries and inodes in Unix, separate from the data blocks). They're just regular Borg tasks, running along those from other services like YouTube, Gmail, Reader, etc. The more storage added to the cluster, the more traffic it gets and the busier the curators become. For very small clusters five or fewer curators might suffice, but when you hit hundreds of petabytes, you need many, many more of them. Borg requires identities, including the system account that runs the Colossus service, to have quota, so there needs to be a way to grant it an amount of CPU cores and memory somewhat proportional to the storage cluster size. (Fun things happen when the cell shrinks instead of growing.) Monitoring the entire stack also requires resources of its own, proportional to cluster size, so there were additional grants at higher priority just for those jobs.

crotchfire2년 전

I've always wondered how Google does this internally.

For all the cloud companies, "quota" is literally dollars. Bandwidth, memory, cpu, these are things they sell. So they are measured in money. The existing corporate budgetary process already manages dollars (indeed, that's its main function). If you want more of one of these things, you'll be displacing some customer who stood ready to pay for them (i.e. on the spot market), so you need to replace the revenue they were providing. Very straightforward.

What does google measure all these things in? Quotons? Where do quotons come from? When google becomes more profitable, does the Central Bank of Quoton print more quotons each month than they had previously? Does Google have a Chief Quoton Officer?

Totally curious about this. Google is the only company operating on this scale that doesn't sell raw bandwidth/cpu/ram as their product, nor do they buy these things from underlying cloud vendors (like e.g. Cloudflare does). This makes a lot of things simpler internally and probably avoids a lot of internal conflicts, but it does mean that they have to have a parallel internal accounting system for this stuff.

Is there an official exchange rate between the two accounting systems? Are different teams allowed to sell each other quotons, in exchange for budget dollars? Has the IRS ever audited Google's Quoton books?

Okay that last question was not serious. But the rest were.

the-rc2년 전

Actually, there is an old paper about this: https://research.google/pubs/using-a-market-economy-to-provi...

crotchfire2년 전

That is a nice paper, but it is a hypothetical proposed by a researcher. It doesn't claim to describe what google is actually doing.

robertlagrant2년 전

This is what I was wondering too. I suppose it's useful because it separates internal demand from external prices, so internal teams can be compared with a common currency, and planning can happen on that basis, and then totally different teams can care about how to purchase compute/storage/etc.

crotchfire2년 전

Maybe.

But how do they decide when to expand a datacenter or build a new one?

The demand is priced in quotons but the costs are in dollars.

Somebody somewhere at google must be maintaining a quoton/dollar exchange rate. It's weird that it's hidden from the rest of the company.

> so internal teams can be compared with a common currency

What's wrong with comparing them using dollars (or euros or whatever) as the currency? That's what Google's revenues are measured in terms of. If the price of electricity doubles (like it has in the EU) a team with euro-constant revenues could swing from being highly profitable to a massive loss... and nobody would notice because quotons conceal the cost of electricity.

marklar4232년 전

What I think the GP means is previously, GFS ran on their own machines and didn't need to participate in the Google-wide quota system for CPU/RAM.

However Colossus _does_ run on the general Google compute infrastructure, and so needed a way to get CPU/RAM quota where none existed (because it was all used by existing, non-storage users).

[deleted]2년 전