I was talking with one of Qumulo’s animation customers about capacity utilization, and they mentioned that they have a particularly difficult time getting people to delete data: they have roughly a thousand artists all working in the same file system tree with hundreds of millions of files! When they start to run low on capacity, they have to apply backpressure. But, in order to do so effectively, they have to tell people what capacity they’re consuming: it’s not practical for a thousand users to crawl hundreds of millions of files. So, this customer had built custom code that ran for many hours accumulating data about the footprint of every user. This was slow and cumbersome, resource intensive, hard to maintain, and delivered out-of-date information. The customer challenged us to deliver something better.
A painful part of data administration is that people create data, and they never free it. And it doesn’t really hurt anything, until everyone is out of space, and everyone has to go look around for things to delete. By which point their application is falling over and everyone has forgotten what they created.
The timeline kind of looks like this:
Storage administrators know there are a few ways to get people to delete data.
Unfortunately, when dealing with hundreds of millions of files, looking at every single one to create a report simply isn’t an option… it’s a ton of performance for a storage system to deliver, it takes a lot of time to process that much data, and the data you get is out-of-date by the time it’s produced. What is needed is a way of rapidly, and cheaply, computing an answer. 1,000 artists running du’s on 1 billion files would be a trillion stats… not going to happen. We need something more efficient.
It’d be really convenient to sample the file system to find out where the capacity ends up… to choose blocks at random, see where they live, and get a sense of where capacity is going. Sampling works well when you’re looking for the worst offenders in the consumption of some resource, but poorly when looking for small contributors. We’re looking for the worst offenders, so maybe sampling can help.
But one of the maddening things about traditional file systems is that they’re impossible to sample. For most file systems we can’t, for example, take a hundred blocks at random and find out where they live.
It helps to consider trying to implement sampling from the top of a tree down, in diagram 2. In this traditional file system we can’t look at the root and figure out where to look next to take a sample, because there’s nothing to tell us at the root whether we should descend to /home or to /tmp. Naively, we might flip a coin and choose a child with equal probability. It’s pretty easy to see, however, that this would sample something in /home 50% of the time, vs. the expected 0.01%. There simply isn’t enough information in the file system to sample effectively without processing the entire tree first, which would defeat the object.
Sampling would help, but traditional file systems can’t do it.
Qumulo Core maintains the invariant that every directory tracks the total number of blocks, files, and various other things that live anywhere below it. Those totals are called aggregates (with apologies to NetApp), and those aggregates are updated in an eventually-consistent but timely (think 15 seconds) way.
Those aggregates have some useful applications. For example, it’s trivially easy to find out how many blocks are consumed under /home/pete in the example above. We can see at a glance that /home/pete has 10 blocks in it.
Our problem is more complicated, however, because we want to find out how many files are owned by a specific user in a given area of a tree. As we discussed previously, we can use sampling to solve this problem.
It’s easy to see that in a sampling application, we can look at the root of this tree, and decide to sample /home .01% of the time (sum_blocks for /home divided by sum_blocks for / == .01%). We can apply this rule recursively at every level, and eventually sample a single block at random.
Qumulo Core makes this kind of sampling easy with a pre-baked API, /v1/files/:ref:/sample, which takes parameters by-value and limit, which control how to weight, and the number of samples to take, respectively. This API allows us to sample in a way that is weighted by sum_blocks (i.e. /tmp is sampled 99.99% of the time, vs. /home at 0.01%), which is exactly what we need.
Sampling is great, but not enough on its own. It gives us a file list. For example:
A first approximation gives the proportion of space owned by root as 83%, and by pete as 17%. As a next step, we want to break down samples by owners and then display a tree for each owner in turn.
The example above is too simplistic: it shows the same files being sampled repeatedly, because our data set is small. The real world isn’t generally as accommodating: in 100,000 samples of a hundreds-of-millions-of-files data set, we might get a multiple sampling of the same file only a few times. In other words, if we try to show data to users, it’s going to be all leaf and no tree:
Numbers indicate sample count: many files are missed and there’s little variety. What will a user make of this?
Our goal wasn’t to tell users a bunch of anecdotes about files where they have used capacity. Instead it’s to tell users about area of the tree where they may have a lot of data.
To solve this problem, we observe that we can prune leaves in the tree, moving their sample counts up. A sample of a file in a directory is also a sample of the file’s parent directory. In other words, we can repeatedly make the following transformation:
Visually, that transformation looks like this:
In other words, we keep removing low-weight leaves until our tree has been reduced to a smaller number of heavier-weight leaves.
Our goal is to limit the number of results so users can focus on the most relevant files and directories, and also to provide reasonable statistical significance for the amount of capacity displayed. To achieve the first goal, we allow the user to set a limit on the number of leaves. To achieve the second, we allow the user to specify the minimum number of samples allowed at a leaf.
If we set the desired number of leaves to be no more than 5, and the minimum leaf sampling to be 3, eventually we’ll end up with this:
Note that we end up with a smaller number of leaves (3) than the limit, in order to accomplish the goal of minimum leaf weight.
This does a pretty good job of pointing out to a user where space is consumed. We’d love to know if you know of a better way.
While recent elections have cast the legitimacy of sampling into doubt in the minds of many, file systems have some advantages over polls. First, blocks don’t lie about what file they’re a part of. Second, blocks don’t refuse to tell you what file they’re a part of. The combination of those two facts allows us to use confidence intervals to accurately describe the range of capacity consumed by a user in a given area of a file system tree. For this to work we observe that each node in the tree we’re displaying a weight for is based on a certain number of hits in a certain number of samples. If you’re math-challenged like me you may find this for dummies guide to confidence intervals helpful. The main point here is that you can’t get anything 100% with sampling, but you can get a range you’re confident in.
We built a script that:
Running this script against my home directory on our shared build server, I see I have a lot of Windows VM and not a lot else:
I did say that we were going to talk about shameback. No one is naturally ashamed of having a terabyte of data, right? On the other hand, would you be ashamed of costing your company $40/month so that you maintain a library of every windows release from 1991 to 2016? Maybe? So, we added an option (-D) to print out usage in terms of dollars per month.
An example output is below:
The good news is that my windows fetish is at most costing Qumulo 75 cents a month. And probably not even that, because we get our storage pretty much for free!
You can get your copy of capacity_by_user.py here!
We have some ideas about where this should go next, but we’d love to hear from you about what you think.