Saturday, March 29, 2014

Something's not write

This is a recount of a recent high pressure debugging session I helped with. As with most difficult debugging sessions it ended up being educational and fun. I'm posting here mostly for posterity and to enlighten the future me.

Two coworkers and I were called in to support a project (not our own) that was going to demo in two days but was experiencing a variety of system-halting problems. This was a system with which I had almost no experience and to complicate matters, since demo was so close, there was no chance we could take down the system to investigate. Our instructions were to engage the production system while the entire user base was attempting to squeeze in last minute testing. Time to go spelunking.

The tasks were broken up between the three of us and my focus was a master-slave setup supporting system automation through a web interface. The machines were running FreeBSD with code written in a variety of languages including C, Python, Perl, and PHP all tied together and coordinated with databases and XML-RPC. The symptom I had to go on was that every once in a while when trying to create a data capture (a file that could ultimately be several Gbs) the resulting file would end up being 0 bytes on disk representing a complete loss of data for that day. There was also a message in the log file that appeared when the data capture failed: 'write failed: Permission Denied'. The strange thing was that this message would appear approximately half way through the transfer so by that time the file had to exist and would have already been written to.

I started by looking at the source code for the offending process. The error was being reported as a result of a failed write call. Strangely, 'Permission Denied' (EACCES) is not listed as a valid error in the write man pages. I wanted to avoid tearing apart the build system to recompile a single source file so I started investigating ways other than editing source to try and figure out why this was happening.

I'm quite unfamiliar with FreeBSD but on Linux I would use something like strace to try an establish a baseline of what is happening. Luckily, FreeBSD has truss which provided close to the same functionality. Unfortunately, the process I wanted to examine was exec'd from deep within some Perl code that kept failing when I tried to prefix the command with truss -o truss.out. Since it was a long running process I ended up attaching to the running process with truss -o truss.out -p 12345.

Now I had a running process that I could monitor and all I needed was to trigger the effect - enter: the heisenbug. Several hours of creating large files without issue forced me to look elsewhere.

I started collecting what information I could about the system and df showed that the data capture file was being written to an NFS mounted location. Since nothing else was out of the ordinary I tried to understand why a write to an NFS file would fail. My first instinct was that there was an overload so I tried several parallel writes of substantial size without issues - no dice. Setting up a tcpdump between the master and slave would have also been tough since all communication throughout the system (including NFS) was handled between these two machines.

Since the process I was monitoring was writing to the master machine and the local code seemed fine I tried digging into why mounted locations would experience random interruptions. I ended up finding a thread on a FreeBSD mailing list that described this exact problem. According to the dialog there, mountd could cause this problem if it received a SIGHUP while the transfer was taking place. I ran a test where I tried transferring a large file while sitting on the destination machine executing kill -s HUP `cat /var/run/`. It took three attempts but I finally triggered the bug - it seems to be a race condition even when doing the very thing that will cause the error.

The only thing left was to determine why mountd might be receiving a SIGHUP. This would happen when calling mount by hand and, as it turns out, some of the tests in the system mount new locations as part of spinning up a test environment. So in the very rare case of creating a data capture while another test mounts a new location and that mount happens to be at the precice moment to interfere with network writes to NFS you get issues. In the general operation this might not ever occur; however, given the load on the system during prep for demo it became a more noticeable (and repeatable) problem.

Considering the the mailing list thread was discussing the issue in FreeBSD 8.3 and this system is still seeing it in 9.1, the ultimate solution was to modify the C code to handle the EACESS case on error from write. As to why the man pages for write do not list EACESS as an error condition... they probably aren't allowed.

Thursday, February 27, 2014

Vertical Histogram

In the process of munging data for my current project I came across the need to compare (visually) the difference between two modes within the same dataset. I was using a simple scatterplot and setting the alpha in the hopes that the over-plotting would indicate which was the major mode. Unfortunately, the size of the data overwhelmed this approach.

I only wanted to use a single image and it was important that I keep the scatterplot to show other features of the data. I started looking for a way to combine a histogram (rotated 90 degrees) with the scatterplot to help describe the density within the plot. A quick search for how to do this in R turned up empty so I decided to implement my own version of such a plot.

Certainly, there are other ways to describe the features that I am trying to present here but in this particular case the following code worked out nicely. Hopefully it proves useful to others as well.

plot.vertical.hist <- function(data,breaks=500) {

    agg <- aggregate(data$Y, by=list(xs=data$X), FUN=mean)
    hs <- hist(agg$x / 10000, breaks=breaks, plot=FALSE)

    old.par <- par(no.readonly=TRUE)
    mar.default <- par('mar')
    mar.left <- mar.default
    mar.right <- mar.default
    mar.left[4] <- 0
    mar.right[2] <- 0

    # Main plot 
    par (fig=c(0,0.8,0,1.0), mar=mar.left)
    plot (agg$xs, agg$x / 10000,
          xlab="X", ylab="Y",
          main="Vertical Histogram Side Plot",
          pch=19, col=rgb(0.5,0.5,0.5,alpha=0.5))
    grid ()

    # Vertical histogram of the same data
    par (fig=c(0.8,1.0,0.0,1.0), mar=mar.right, new=TRUE)
    plot (NA, type='n', axes=FALSE, yaxt='n',
          xlab='Frequency', ylab=NA, main=NA,
    axis (1)

    invisible ()

Results look similar to the following:

Initially, I experimented with rug or barplot(..., horiz=TRUE). Unfortunately, rug isn't available on the left or right side and would suffer from the same problem that the alpha settings did and I was unable to get the alignment worked out when using barplot.

Friday, January 24, 2014

Probably not the Best

Probabilities are tricky - for me, at least. The fact that I can not use them like other numbers although they are sometimes represented as floating point numbers often trips me up.

Case in point: I'm designing an approach to a packet forwarding problem that includes calculating the probability of a packet making it through a portion of a network. An example that helps describe the solution is in the following diagram:

Where \(I\) is the ingress node, \(E\) is the egress node and the other nodes are represented by the probability that a given packet will be forwarded (\(P_{f}\)) to \(E\) when received from \(I\).

For any given path \(I\) to \(E\) through a single node, the probability the packet will be delivered (\(P(I \Rightarrow E)\)) is equal to the probability that the intermediary node will forward the packet (ignoring all other details of the medium).

What I [incorrectly] claimed in my presentation of the solution was: if you use all nodes simultaneously and discard duplicates at \(E\), the probability of a packet successfully passing from \(I\) to \(E\) then becomes \(max(N)\). Where \(N\) is the set of nodes between \(I\) and \(E\). Considering the example above that equation results in \(P(I \Rightarrow E) = 0.82\). This is better than choosing the node with \(P_{f} = 0.21\) but it is not the true probability of a packet getting through. 

This design made several rounds of internal review where this error was not noticed; perhaps there is some solace to be had in knowing I am not the only one who is tripped up by this.

When it finally came time to implement this I was discussing the solution with another engineer and he quickly pointed out that my calculation was incorrect. In fact, my estimation was much lower than the actual likelihood of getting a packet through. The true probability of not getting a packet through is the probability of all intermediate nodes dropping the packet.

\[\prod_{i=0}^{n} (1 - P_{f_{n}})\]

The ultimate effect of my proposed approach is the probability of not having that happen or:

\[1 - (\prod_{i=0}^{n} (1 - P_{f_{n}}))\]

For this specific example that is:

1 - ((1 - 0.76) * (1 - 0.21) * (1 - 0.82) * (1 - 0.33))

or 0.977. A much higher value than my originally proposed 0.82.

Friday, August 16, 2013

Visualizing Internet Activity

I've recently been playing with the idea of visualizing the network demand for various activities related to everyday Internet use. Most times the browser presents a view that abstracts this behind-the-scenes activity to provide a seamless experience to the user. Even so, it can be enlightening to peel back the layers just a bit to peek at what is really happening.

In the images below I've tried to present this underlying activity in a way that is intuitive without drowning the reader with information. This is still a work in progress but I feel as though this is a decent start toward that goal.

The graphs below represent network traffic related to three types of activity one might typically engage in while online: browsing facebook, watching a youtube video, and downloading a large file. Each 'bubble' represents a packet; radius is the relative packet size; individual connections are annotated with unique colors; and I add jitter in an attempt to alleviate over-plotting.

The above is the graph for facebook. There is an initial burst of activity to load all the components when you first log in; as you scroll down the page more content is loaded to extend the page on-demand (these are the narrow vertical impulses throughout the graph); then, around time 250 there is a large amount of activity related to opening a photo album and browsing through the pictures. As can be seen by the transitioning colors there are a variety of individual connections used over the course of the facebook session.

This next graph is a view of what happens when watching a youtube video. Again, there is a quick burst to load the page and several connections are used to do this. Once the video is playing, however, there is only very periodic bursts of activity. In fact, if you observe the video progress bar as you watch the video you will notice that youtube front-loads a portion of the video immediately and then, as you start to need more content, requests the next section of the video.

Finally, this is a view of what a large file download requires: very few connections and a consistent, heavy flow of packets across the network.

From an end user point-of-view, the experience related to each of these activities is the same: open a browser, click a few buttons and receive content. The resources and demand to deliver this content, however, is entirely distinct from that experience.

Friday, July 19, 2013

Column-Major Confusion

As a programmer coming from a language like C I am used to understanding multidimensional arrays in the following way:
int matrix[3][3] = {
    { 1, 2, 3 },
    { 4, 5, 6 },
    { 7, 8, 9 }

Understandably, this is a little bit of a setback when trying to grok how a language such as R handles matrices. The example above is 'row-major' but R uses 'column-major' by default. Note that I'm not describing memory layout here - which coincidentally is the same as my description - I referring to how the matrices are presented to the programmer. To complete the example, here is how I would create the same matrix as above in R:
> matrix(1:9,ncol=3)
     [,1] [,2] [,3]
[1,]    1    4    7
[2,]    2    5    8
[3,]    3    6    9

There is no problem with this per se. In fact, I'd imagine that R programmers that come to something like C may feel similar unease in the paradigm shift. I'm finding that this fact is glazed over in some texts offering an introduction to R. This happens in non-obvious ways. In particular, I found this example today:
> matrix(c(1,0,0,0,1,0,0,0,1),ncol=3)
     [,1] [,2] [,3]
[1,]    1    0    0
[2,]    0    1    0
[3,]    0    0    1

The identity matrix is a particularly bad choice in this regard as it gives no indication of the true layout being used. It is probably good for any tutorial using matrices to cover an obvious simple case first to set the stage before moving directly to something like the identity matrix (or any other symmetric matrix for that matter).

Saturday, July 13, 2013

10 points: 10 plots

As an exercise in expanding my ability to display data I challenged myself to present 10 data points in 10 ways that were as distinct as possible. The idea was simple: use 10 random data points; minimize the axis and other ancillary information so as to focus on the data as much as possible; and try to minimize the overlap between each of the approaches.

Initially, I expected this would be a trivial task - something that would take a single sitting and a little bit of thought. A few attempts later and I kept circling back on a few common ideas while considering just how many approaches I'd not considered. What exists below is a collection of the results of that exercise with explanation if necessary.

1 - Standard Cartesian (scatterplot)

2 - Derivative Cartesian: uses labels instead of points to eliminate the need for tick marks on the x-axis.

3 - Impulses. Mixing the number and characters on the x-axis tick marks is questionable and could just as well have been labels at the top of each impulse

4 - Sorted derivative Cartesian

5 - Boxplot

6 - Barplot

7 - Radial. Points are interpreted as radians and placed starting from 0 radians

8 - Heatmap

9 - Cumulative Sum

10 - Financial/Intensity: Positive values are blue, negative are red. Absolute values define the radius of the circle used.

I considered others such as LOESS fit but they either needed the points to accompany them (to show what was being fitted) which made them too close to the Cartesian plot, or they were too complex for just 10 points.

It was interesting to see how difficult it turned out to be to stretch 10 points into 10 distinct presentation approaches.

Thursday, June 27, 2013

Walk this way

I recently found a handy mechanism for walking a directory tree in Linux. In
general, the way I used to do this was to use facilities found in dirent.h and
write my own recursive directory walker. Something similar to:

#include <stdio.h>
#include <string.h>
#include <dirent.h>

void reclist (const char* dirname) {

    DIR* dir = opendir (dirname);
    struct dirent* entry = 0;
    char name[1024] = {0};

    if (! dir) { return; }

    entry = readdir (dir);
    while (entry) {
        if (strncmp (entry->d_name, ".", 1)) {
            switch (entry->d_type) {
                case DT_REG:
                    printf ("%s\n", entry->d_name);
                case DT_DIR:
                    snprintf (name, 1024, "%s/%s", dirname, entry->d_name);
                    reclist (name);
        entry = readdir (dir);
    closedir (dir);

int main(int argc, char** argv) {
    const char * dir = ".";
    if (argc == 2) { dir = argv[1]; }
    reclist (dir);
    return 0;

While that does work, it is rather verbose (especially once you get used to
environments like Ruby and Python). It turns out that ftw.h provides a more
concise way to do the above while managing all the little details like
avoiding '.' and '..' and managing the current path string. Here is what that
looks like to do the same as the above:

#include <stdio.h>
#include <ftw.h>

int handle_entry (const char *entry, const struct stat *sb, int type) {
    if (type == FTW_F) {
        printf("%s\n", entry);
    return 0;

int main() {
    ftw(".", handle_entry, 10);
    return 0;

I also like the fact that a callback is used to operate on each of the files
found. It makes managing changes much easier as the tree walking is separated
from the code that handles the logic associated with inspecting the files.