Wandering Thoughts archives

2014-10-11

Thinking about how to create flexible aggregations from causes

Every so often I have programming puzzles that I find frustrating, not so much because I can't solve them as such but because I feel that there must already be a solution for them if I could both formulate the problem right and then use that formulation to search existing collections of algorithms and such. Today's issue is a concrete problem I am running into with NFS activity monitoring.

Suppose that you have a collection of specific event counters, where you know that userid W on machine X working against filesystem Y (in ZFS pool Z) did N NFS operations per second. My goal is to show aggregate information about the top sources of operations on the server, where a source might be one machine, one user, one filesystem, one pool, or some combination of these. This gives me two problems.

The first problem is efficiently going 'upwards' to sum together various specific event counters into more general categories (with the most general one being 'all NFS operations'). This feels like I want some sort of clever tree or inverted tree data structure, but I could just do it by brute force since I will probably not be dealing with too many specific event counters at any one time (from combinations we can see that each 4-element specific initial event maps to 16 categories; this is amenable to brute force on modern machines).

The second problem is going back 'down' from a category sum to the most specific cause possible for it so that we can report only that. The easiest way to explain this is with an example; if we have (user W, machine X, fs Y, pool Z) with 1000 operations and W was the only user to do things from that machine or on that filesystem, we don't want a report that lists every permutation of the machine and filesystem (eg '1000 from X', '1000 against Y', '1000 from X against Y', etc). Instead we want to report only that 1000 events came from user W on machine X doing things to filesystem Y.

If I wind up with a real tree, this smells like a case of replacing nodes that have only one child with their child (with some special cases around the edges). If I wind up with some other data structure, well, I'll have to figure it out then. And a good approach for this might well influence what data structure I want to use for the first problem.

If all of this sounds like I haven't even started trying to write some code to explore this problem, that would be the correct impression. One of my coding hangups is that I like to have at least some idea of how to solve a problem before I start trying to tackle it; this is especially the case if my choice of language isn't settled and I might want to use a different solution depending on the language I wind up in.

(There are at least three candidate languages for what I want to do here, including Go if I need raw speed to make a brute force approach feasible.)