zindex - index and search large gzipped files quickly

We generate an awful lot of logs at work. The application I work on outputs a large JSON log line each time we make a decision, and we make a lot of decisions. We end up with many tens of gigabytes of JSON log file per machine per day.

All this is then gzipped, archived and placed into longer-term storage, accessible to me over NFS. If we need to do any diagnostics or answer historical questions about the decisions our software made, the main tools we used were zgrep and jq. These are both irreplaceably awesome, but zgrep in particular understandably take a little while to run. The gzip file format does not in general1 support random access, and so zgrep is forced to decompress the entire file serially and then search each line.

I thought there must be a better way, and when I discovered the zran.c example in the zlib sources (a way to accelerate seeks inside gzipped files) I set to work on zindex.

zindex creates an index on your gzipped files and then zq lets you quickly search that index. Not only does zindex create an index based on a configurable key per line, it also creates an acceleration structure to allow random access within an existing gzipped file. That makes it super fast to query and return the matching lines without the index itself being too large.

Random access is afforded by a “checkpoint” of the decompressor’s state being stored every few megabytes of data. Later on, this checkpoint can be used to re-initialise the decompressor to decompress from within the middle of the file. To read from a particular offset in the file, the nearest checkpoint before the required data is found, the decompressor initialized with its state, and then data decompressed and discarded until the required offset is found. This bounds the amount of time needed to read a file to be on average the time taken to decompress half the checkpoint size’s amount of data. Without checkpoints the average time is half the time needed to decompress the entire file.

The index itself can be generated in a number of ways:

By default the index is created as <FILENAME>.gz.zindex, but this can be changed if (for example) your gzip file is on a read-only NFS share.

Once the index is built, querying it is simple: run zq and pass it the path to the gzipped file and then whatever queries you want to make. zq will use the default index on a file unless told otherwise: it can also query by line number. I plan on adding support for multiple indices soon.

Typical numeric indexes I have built are around 20% of the size of the compressed file size, which is to say around 4% of the uncompressed size. Indexing runs at around 50MB of compressed data per second (250MB/sec uncompressed). I suspect the limiting factor in my tests is NFS.

Querying the index is pretty fast; taking on average 0.01s per query in my tests.

Still to do are supporting multiple indices, and optimizing some cases where I can reuse the decompression state without rewinding and starting again.

As you’d expect the source is available on github and I welcome patches. Ideas and bug reports are also welcomed. I hope to get a few things fixed up and then do a v1.0 release, complete with binaries: at the moment you’ll need to build from source.


  1. It is possible to create points in the gzip stream where one can later seek() to by resetting the state of the compressor and flushing it periodically. That wasn’t an option in our case as the file archival process is not something I had the freedom to change. 

Filed under: Coding
Posted at 13:15:00 BST on 27th May 2015.

The runtime performance of Rust for a simple path tracer

In my last article I described my port of smallpt to Rust.

In this short post I’m updating with some performance figures. I’m really impressed; the Rust version really is as good as the C++ version! I tested on my home server, a 4-core 2.5GHz X3323, which was otherwise idle.

Due to some stack limitations in Rust, the Rust code bails out after 500 levels of recursion; so I modified smallpt to do the same.

I ran smallpt like this:

$ g++ -O3 -ffast-math -march=native -fopenmp smallpt.c \
  && time ./a.out 1024
Rendering (1024 spp) 100.00%
real    13m5.357s
user    51m56.112s
sys     0m0.303s

And then I ran the rust code with:

$ cargo build --release \
  && time cargo run --release -- -s 1024
Compiling path_tracer v0.1.0 (file:///home/matthew/path-tracer)
Running `target/release/path_tracer -s 1024`
Using 4 threads
Rendering (1024 spp) 99.8698%...
Writing output to 'image.ppm'
real    12m53.603s
user    51m17.749s
sys     0m0.323s

The two output images are similar enough that I’m pretty sure I’m running them with equivalent settings:

A beautiful picture
The output of the Rust version.

A beautiful picture
The output of the C++ version.

Pretty impressive: the Rust version is actually a tiny bit faster that the C++ version. I double-checked that both the Rust and C++ version use all the CPUs on the machine too. If anything, the C++ compiler settings I used are more generous than those the LLVM backend is using for Rust!

Now I just need to get my head around how the borrow checker works: I had some great suggestions on the Rust subreddit but have been unable to get the borrow checker to let me use them.

I plan on hacking more on the tracer, but I know myself too well to promise anything. I’ve had a bunch of suggestions for zindex (which I must blog about very soon), Seasocks and of course GCC Explorer and I will probably spend some time on them. But you can’t really beat the awesome feedback of working on a renderer!

Filed under: Coding
Posted at 05:05:00 BST on 26th May 2015.

Two commutes with Rust

Over the last couple of commutes to and from work I’ve been playing with Rust, which went v1.0 over the weekend.

Rust is touted as a systems language in the same vein as C, C++ and to a lesser extent, Google’s Go. It offers both high level abstractions like generic programming and object-orientism while also giving access to lower-level facilities like fine-grained memory allocation control and even inline assembly.

Critically for me, it has a “only pay for what you use” mentality like C++, a well-sized standard library and runtime, and no garbage collection. It’s quite feasible to use Rust to make a “bare metal” system in (for example, Zinc).

One of the novel things Rust brings to the table is its memory ownership semantics. Each allocation’s lifetime is tracked by the compiler (with an occasional helping hand from the programmer). Passing references to objects invokes the “Borrow Checker” which makes sure nobody holds on to objects beyond their lifetime. This solves a lot of memory ownership issues (maybe all of them?) up front, in the compiler. I love this.

Another nice feature is having proper, deterministic “destructors” that run when a variable binding goes out of scope. I miss this a lot in those times where I’m programming in a language other than C++.

So I loved the sound of all this, but in order to see how it all fitted together in practice, I decided to port a C++ path tracer to Rust, and see how I’d get on. I’m fond of smallpt, a 99-line C++ program that generates lovely images. While I was still at Google, I did the same experiment with the (then unreleased) Go language; and found the code generator lacking, and the development experience a little lacking. How would Rust fare?

Pretty well!

First steps

Firstly I hacked up a Vec3d class to do all the 3D maths needed. It was surprisingly easy to make a struct, and then add an impl to do all the operations I needed. As a bonus, by impl-ing the relevant Add, Sub etc traits, I was able to get things like let a = b + c; working for vectors.

pub struct Vec3d {
    pub x: f64,
    pub y: f64,
    pub z: f64
}
impl Vec3d {
    pub fn dot(self, other: Vec3d) -> f64 {
        self.x * other.x + 
            self.y * other.y + 
            self.z * other.z
    }
    ...
}

impl Add for Vec3d {
    type Output = Vec3d;

    fn add(self, other: Vec3d) -> Vec3d {
        Vec3d { 
            x: self.x + other.x,
            y: self.y + other.y,
            z: self.z + other.z 
        }
    }
}

Source of the above here, full source on github.

Immediate things I found:

Making pictures

Once the Vec3d class was finished (and even had a simple test), I moved on to the body of the renderer. It was fairly simple to get up and running. Probably the trickiest part was remembering to type cargo build instead of make!

Things I learned getting the first image rendered:

This leads to nice code like:

let mut result : Option<HitRecord> = None;
for sphere in scene {
    // if let will assign to 'dist' if the return of intersect
    // matches "Some".
    if let Some(dist) = sphere.intersect(&ray) {
        // if we don't currently have a match, or if this hit
        // is nearer the camera than an existing result, then
        // update 'result' with this hit.
        if match result { None => true,
                          Some(ref x) => dist < x.dist) } {
            result = Some(HitRecord { 
                sphere: &sphere, dist: dist 
            });
        }
    }
}

An example:

struct HitRecord<'a> {
    sphere: &'a Sphere,
    dist: f64
}

fn intersect<'a>(scene: &'a [Sphere], ray: &Ray) 
    -> Option<HitRecord<'a>> {...}

Here the lifetime indicator 'a is used to show the sphere reference inside the HitRecord is only valid while the similarly-tagged scene slice is. The compiler will give an error if you try and let a HitRecord outlive the scene it came from.

With all that in place I got my first image:

A beautiful picture
A little example of path tracing in action.

Performance

If you look at the assembly output of Rust (e.g. with Rust explorer, you can see it’s able to utilize the LLVM backend to do some impressive SSE2 code generation. Coupled with the “no allocations unless you ask for them”, and no need to stop the world for garbage collection etc, it performs well.

In my simplistic benchmark on my laptop during my commute, it performs the same (within a second or so) as the smallpt.c compiled with -O3 -fopenmp, at least once I put in rudimentary threading to match the OpenMP implementation in smallpt. I’ll run a longer test (and debug some IO slowdowns that are contributing to the difference) and post again with more information.

All in all I’m extremely excited and I look forward to spending more time hacking on Rust!

UPDATE: I’ve now written a follow-up post on the performance numbers, having fixed a number of bugs in the Rust version.

Filed under: Coding
Posted at 18:40:00 BST on 21st May 2015.

Leaks in javascript

Regular users of GCC Explorer may have noticed its uptime was getting a little choppy. Having moved to using docker and no longer running the site under an auto-restarting supervisor script, the occasional shutdowns I had been intermittantly seeing became longer outages instead of a quick restart.

Rather than resurrect the seemingly unnecessary supervisor, I decided to fix the underlying problem. The main issue was that the node.js process that runs the webserver was slowly “leaking” memory and eventually my Amazon S3 instance would run out of memory. The OOM killer would then come along and whack the process – and I’d get another SMS alert telling me the site was down.

Where to start? How can a garbage collected language leak memory, anyway? Good questions. First up I added instrumentation to a few likely-looking places, but nothing obvious seemed wrong. Then I tried an NPM package called memwatch which seemed to be a step in the right direction.

I ran a bunch of compiles locally and looked at the memwatch output: nothing obviously untoward again. So I deployed the memwatch version to the public site, and kept an eye on it over a period of a couple of weeks. I use (and recommend) papertrail to aggregate all the docker logs and system logs, so with a simple query I could see all the memory usages.

Over that two week period, the site got killed several times. Each time I could see that the memory usage had been steadily increasing, and that seemingly the main thing being retained were strings. That’s no surprise: there’s a bunch of caching of the compiled output done in the server, and each compile output can be 500KB or more. I immediately suspected the LRU cache I used…but after reading the source over and over I couldn’t see how there could be any issues with it.

So what strings were being leaked after all?

I found another NPM package called heapdump and gave that a go. Again I had to deploy to the live site and let it stew for a couple of days to get it anywhere near running out of memory. I then executed kill -USR2 <PID> from within the relevant docker container to trigger a heap dump. The heap dump loads into Google’s Chrome developer tools and let me look around at the contents of those objects in the heap.

As expected there were a tonne of compiler output files, but I spied another set of strings that seemed a little out of place:

Google Chrome heap profile
Google Chrome's heap profiler showing the offending strings

A giant list of temporary directory filenames! Looking at the “Retainers” immediately showed the culprit: another library I used called temp that’s used to make a temporary directory to run the compiler and other tools in for each compile. I always clean up the temporary directory after each compile, but I had left the library in ‘track’ mode where it keeps a list of directories and files to clean up on program termination.

Of course, this is a long-lived server, and the list was getting longer and longer with every compile. A few hundred bytes every compile, and with a few hundred thousand compiles a day, it all adds up!

Rather than give up entirely on the tracking ability, in the fix I just periodically run the cleanup code.

Now the site has been up for a week and has stabilised at a nice round 120MB of memory usage.

Filed under: Coding
Posted at 18:45:00 BST on 7th May 2015.

About Matt Godbolt

Matt Godbolt is a developer working on cool secret stuff for DRW, a fabulous trading company.