Sebastian Cohnen

How to Find Periodic Effects on Performance using Autocorrelation

2012-02-21T10:30:00+01:00

For one of my clients I’m doing performance assessments on a quite regular basis. For adcloud, performance is a primary key to success. To give you a little background: adcloud’s adserver system is serving thousands of requests per second — only with a couple of application servers. And since customers don’t like slow loading ads on their pages, latency besides raw throughput is a fundamental criteria defining the service’s quality.

We basically run extensive load tests with different scenarios all the time to ensure that a new feature or even a small improvement does not compromise the stability and quality of the system — especially under load. Functional correctness is covered by unit and integration tests, but non-functional aspects like throughput and latency are a bit harder to measure and to deliver. How exactly the setup looks like, which I created to help adcloud to run automated, distributed load tests, will be the topic of another post. For this article I’d like to outline an idea I have had in mind for quite some time now and which has been proven to work at least once.

Please note that I cannot present you real numbers here as they are confidential. I hope that the concept behind the idea is still comprehensible.

The Problem: Periodic Effects

A few weeks ago, while performance testing a rather important and big release, we tried to figure out why sometimes the average response times (and the variation too) were looking okay and sometimes not. I had a suspicion that we could have a semi-periodic variance in the average response times, due to tasks running in the background. By just looking at the data and plotted graphs (see next next image), it was very hard to see.

So how can you verify that you have other (background) processes, scheduled activities or other external factors that influence your performance?

A Possible Solution: Autocorrelation

It turns out, that this problem was the topic of a lecture at the university. I remembered a lecture about the “scientific basics of audio-visual media”, where our professor explained a quite simple, yet powerful tool to uncover periodicities in semi-periodic signals: Autocorrelation. Okay, we don’t have a signal in the sense of audio-visual media, but we could think of the response time as a function over time, which would make it kind of like a signal.

Autocorrelation (short ACF, autocorrelation function) is a cross-correlation of a signal with itself. By correlating a signal with itself, repetitive patterns will stand out and make it much easier to see. The (discrete) autocorrelation of a signal x is defined by the following simple equation.

The entire signal x is shifted by an offset j and then multiplied by the original signal. This is repeated for every sample in the discrete signal. R[0] is basically the energy of the signal and therefore the maximum of the ACF. R[1] is the correlation of the signal with itself shifted by one sample — you get the idea. If the signal has a significant enough self-similarity, the ACF will show this relation. In the case of a suspected periodicity the signal will repeat itself after each period. All we have to do now is run the autocorrelation and check for maxima in the result. If the maxima are within a certain delta of your suspected periodicity, you were right!

So far, so good. I started to implement a discrete autocorrelation function in Ruby to give it a try.

autocorrelation (autocorrelation.rb) download

def autocorrelate(signal, window_size)
  r = Array.new

  def r.[](idx)
    (idx < 0 or idx >= self.size) ? 0 : super(idx)
  end

  (0..signal.size).step do |n|
    (0..window_size).step do |i|
      r[i] += signal[n] * signal[n - i]
    end
  end

  return r
end

autocorrelate will cross-correlate the given signal with itself, returning a new signal. I am using a sliding window here to optimize the process a bit (see below how to choose it properly). Also note that I patched the internal array’s element accessor [] in order to return 0 instead of nil for indices that are not set. To ease up further analysis you can normalize the signal. This is easy since the 0th shift is the maxima of the signal.

normalization (normalization.rb) download

def normalize(signal)
  signal.map { |signal_n| signal_n / signal[0] }
end

Now, all you have to do, is read your signal with something like signal = load_signal("data/requests.txt") (signal needs to be an array of floats) and dump it into the method shown above.

How to choose a proper size for the sliding window? window_size has to be big enough to catch your suspected periodicity. Choosing it too big just slows down the process and does not increase the accuracy. In our case I chose window_size to be ~300 samples wide, since I had the suspicion, that one of our periodic executed background tasks could be responsible for the variation. This task runs every 30 minutes, and since tsung generates one sample every 10 seconds, I was on the safe side using 300 samples for the window_size in this case.

Result

Initially I had some problems getting my peak-picker working properly, so I decided to just plot the results using gnuplot. The following image shows the plotted autocorrelated and normalized values of the initial signal, R[j]. The x-axis represents the used time-based shift. Keep in mind that tsung takes 1 sample every 10 seconds.

As you can clearly see, we have a peak at about every 180 samples, indicating that we have a base frequency of 1/1800 seconds, or 1/30 minutes. And 30 minutes looks pretty much exactly like one of our background tasks. The process runs for a few minutes, which is the reason the result is not a perfectly sharp spike. In the end, we optimized the task to have significantly less impact on the system’s latency and shipped the feature — end of story :)

PS: adcloud is always looking for skilled developers. Feel free to contact me if you want to get in touch and make sure to visit their dev site.

Ruby is Magic!

2012-01-25T18:46:00+01:00

As you might have been noticed already Dirk and I started rubyismagic.de. First it was just a quick idea to give a talk at cologne.rb – the local Ruby User Group here in Cologne. We talked about the seven types of closures in Ruby and we good quite positiv feedback right after the talk. So we decided to make the show a regular one at colognerb. We will take a closer look stuff you see everyday using Ruby, like closures.

For every presentation at colognerb we’ll post an article, the slides and code. Additionally we’ll add some articles in between on subjects that are related to the shows topics.

We hope you have fun reading the first episodes post about Closures in Ruby.

Riak talk at NoSQL UG Cologne

2012-01-16T09:36:00+01:00

I helt a another little talk (in German) where I presented Riak at the NoSQL Usergroup Colgogne. A little late (sorry, caught a cold), but here are my slides.

CouchDB Talk at NoSQL Cologne

2011-11-16T00:00:00+01:00

I helt a little talk (in German) where I presented/introduced CouchDB at the NoSQL Usergroup Colgogne on Nov. 2nd. A little late, but here are my slides.

Native List Functions with CouchDB

2010-11-25T00:00:00+01:00

Show and List Functions are used to transform single documents (show) and multiple documents e.g. from a view (list) into anything you want: JSON, HTML lists, SVG graphs…

You might know that you can write CouchDB Views in Erlang. But you can also write Show and List functions in Erlang as well. Today I played a bit around with a list function I’ve implemented in JavaScript first. I wanted to know, how much faster a native version would be and I wanted to write some Erlang too. I’ve not done any extensive benchmarking, just simple queries, but the difference is quite significant. Writing Erlang - if you aren’t used to it - might be an obstacle though.

So, what have I done? First you need to enable the Erlang view server. The “How to Enable Erlang Views” wiki page tells you what to do: Add a new section to your local.ini or via Futon.

[native_query_servers]
erlang = {couch_native_process, start_link, []}

Here is the list function, I’ve written in JavaScript: It’s purpose is to filter view results based upon uniqueness of a specific field ad_id in that case.

function(head, req) {
  var row, last_ad_id = "";

  start({ "headers": { "Content-Type": "text/plain" } });

  while(row = getRow()) {
    if (last_ad_id != row.doc.ad_id) {
      send(row.doc.ad_id + " with " + row.doc.text + "\n");
      last_ad_id = row.doc.ad_id
    }
  }
}

And here is the Erlang version with the same functionality. I’m very new to Erlang so there might be (much) room for improvement :)

fun(Head, {Req}) ->
    Fun = fun({Row}, PrevAdID) ->
        {Doc} = couch_util:get_value(<<"doc">>, Row),
        Resp = case couch_util:get_value(<<"ad_id">>, Doc) of
          undefined ->
            undefined;
          AdID ->
            if
              AdID /= PrevAdID ->
                DocID = couch_util:get_value(<<"id">>, Row),
                Text = couch_util:get_value(<<"text">>, Doc),
                Send(list_to_binary(io_lib:format("Doc-ID ~p~n", [DocID]))),
                Send(list_to_binary(io_lib:format("Text ~p~n", [Text])));
              true ->
                null
            end,
            AdID
        end,
        {ok, Resp}
    end,
    FoldRows(Fun, nil),
    nil
end.

Although this might not be a very good example, I’ve learned some things. The Bindings available in the native Erlang views are defined in src/couchdb/couch_native_process.erl#299. Available are Log, Emit (for Views), Start, Send and GetRow which are the counterparts to log(), emit(key, value), start(), send() and getRow() in the JavaScript view server. Additionally FoldRows can be used as a helper to iterate over all rows in a list function.

Uh, I almost forgot got talk about speed: The native view was about 75-85% (processing a few hundred rows takes about 200ms with Erlang) faster than the JavaScript version. But speed is not everything and often fast enough is okay. Since I don’t speak Erlang very well, I’d think at least twice before I optimize my views using native Erlang.

Fixing problems with iconv and ruby 1.9.x (rvm)

2010-11-19T00:00:00+01:00

Today I had some weird issues with various gems complaining about missing iconv and readline. Here is how I fixed it: Installing the libs via rvm package install, switched to the system ruby (not sure if this is really necessary), remove ruby 1.9.2 (important!) and reinstall it. Before installing the rvm packages I removed any previous trace of them by rm -rf ~/.rvm/usr.

I hope that might be handy for anyone having issues with that too.

#!/usr/bin/env bash
rm -rf ~/.rvm/usr
rvm package install iconv
rvm package install readline
rvm package install zlib
rvm package install autoconf
rvm use system
rvm remove 1.9.2
rvm install 1.9.2 --with-iconv-dir=$rvm_path/usr \
                  --with-readline-dir=$rvm_path/usr \
                  --with-zlib-dir=$rvm_path/usr \
                  --with-openssl-dir=/usr/local
rvm --default 1.9.2
rvm wrapper 1.9.2 textmate

Using gem edit via TextMate

2010-11-18T00:00:00+01:00

The gemedit-gem is very useful if you want to have a quick look at what the lib you are using is doing. I found myself using gem edit some_gem_name quite often, several times a day. Yesterday I thought it would be nice to have a shortcut to open a gem’s code from within TextMate. So I wrote a little TextMate snippet. You can grab it here: https://gist.github.com/703646 (I’ll also update the gist, if I found any bugs/issues).

If you follow the “installation” instructions, you can now hover over a word, press your chosen shortcut and the script will try to find a gem and opens it in a new TextMate window. If no corrosponding gem is found you’ll get a text box where you can type in the name of the gem you want to see/edit.

Wikipedia on CouchDB

2010-10-01T00:00:00+02:00

This is the first post of a little series I’m planing. It’s about one of my favorite open source projects at the moment: Apache CouchDB. I assume you’ve already heard of the not-so-new player in the NoSQL league and I’m watching the project for quite a while now. Little hint: #couchdb on irc.freenode.net is where you get in touch with the couchers and I’m there most of the day, too.

But what will this little series be about? Short: Play with Wikipedia and CouchDB. I want to give interested people some guidance to CouchDB and working with it. It’s fun, believe me! And why Wikipedia? Because everybody knows it, they have plenty of data to play with and it’s just a perfect match for a document-orientated database like CouchDB. You can keep it simple, just import it, or you go one step further, do benchmarks, see how it performs, add lucene-powered full-text indices, write map/reduce views to analyse Wikipedia’s content… the possibilites are endless and maybe you even create something useful ;)

This first post will be about, how to get the data from Wikipedia into CouchDB.

Some preparations

We will first of all install CouchDB. You can get the latest version from CouchOne. Of course you can build CouchDB from scratch if you like to, but this is perfect to get started. On Linux you might want to use a package out of your distributions repository. For more information check out the offcial wiki page on installing CouchDB.

Once that’s done, you can use my import-tool by cloning my wikiimporter-repository on GitHub:

git clone http://github.com/tisba/wikiimporter.git && cd wikiimporter

I’ve basically written some little scripts that will help you to fetch the latest XML dump of Wikipedia, parse and transform it to JSON and upload the stuff into your CouchDB instance.

To use my scripts, you need the following dependencies:

gem install nokogiri trollop yajl-ruby

Now we are ready to rumble!

Let’s go!

What’s next? Right: Get the material. I assume you are in the wikiimporter directory:

./bin/wiki2couch.sh enwiki http://localhost:5984/enwiki

This will take some time depending on your bandwidth and IO-performance. You can also cancel the process. Be aware that you cannot resume it at the moment, but if you just want to have a few thousand articles this will work just fine.

If you want more information on wikiimporter check out the projects README on GitHub.

What’s next?

Next time I’ll quickly show how to set up couchdb-lucene to realize a nice fulltext search to explore the imported wikipedia articles.

Hire me!

2010-09-28T00:00:00+02:00

I recently finished my studies in computer science at the Cologne University of Applied Sciences, so you may call me master of computer science now *yay!* ;)

Seriously: It feels good to be (finally) finished with this part of my life now. And now?

I’d like to work on your projects!

I’m specialized in Ruby and Rails and other web technology like JavaScript and all the stack down to application servers, caching, messaging services, protocols like HTTP… – you name it. I also have experience in MySQL as well as several NoSQL datastores (especially CouchDB). My master’s thesis was about design patterns for scalable, service-orientated web-architectures — so designing and implementing scalable web-architectures is something I’m familiar with too.

My desk and working place here in Cologne (Germany) is hosted by the mighty Galaxy Cats which are very passionate developers and geeks — just like me. So if you want to get in touch feel free to drop by (Club Mate is on me).

I’m looking forward to hear from you!

CouchDB Shirt Arrived

2010-05-19T00:00:00+02:00

Have a look what just arrived! :)

Ordered from the German CouchDB-Spreadshirt. If you want to have other products just ping me (I am managing the products there).

CouchDB-Lucene Console

2010-04-21T00:00:00+02:00

Really quick, but I wanted to start with an actual useful blogpost (I’ve some more interesting topics in the queue though). So here we go!

I’m playing a lot with CouchDB and CouchDB-Lucene and I was missing something: An easy way to play with queries to c-l, without having to think about proper URL encodings, without having to remember the current/correct URL and syntax for a given index. And so I wrote this little ruby gem called cl-console!

To get started:

install the gem: gem install cl-console
ensure that CouchDB and CouchDB-Lucene is running
fire up an IRB session: irb -rrubygems -rcl_console
instantiate a CLConsole-object (see readme for details)
have fun!

Here is what a typical session looks like (I’ve used pretty_print for prettier output):

Example session

>> cl = CLConsole.new("cl-test/cl-test/range")
=> #<CLConsole:0x101e2f7c8 @options={}, @cl_url="http://localhost:5984/cl-test/_fti/_design/cl-test/range">
>> pp cl.info
{"doc_count"=>2,
 "disk_size"=>585,
 "current"=>true,
 "ref_count"=>2,
 "fields"=>["price", "default"],
 "optimized"=>true,
 "last_modified"=>"1271589171000",
 "doc_del_count"=>0}
=> nil
>> pp cl.q "test"
>> q: default:test (0ms / 0ms)
{"total_rows"=>1,
 "etag"=>"11a69e6ea30bedf8",
 "search_duration"=>0,
 "q"=>"default:test",
 "rows"=>[{"id"=>"f3fba9f61520e0ef2a245772a900074c", "score"=>1}],
 "fetch_duration"=>0,
 "limit"=>25,
 "skip"=>0}
=> nil
>> pp cl.qd "test"
>> q: default:test (0ms / 19ms)
[{"price"=>"543.00",
  "title"=>"test",
  "_rev"=>"4-7d11268b0aa408f4b55bbd5df5ab2b49",
  "_id"=>"f3fba9f61520e0ef2a245772a900074c"}]
=> nil

I have to admit, cl-console is a very lame name, but who cares? I hope you like it anyways :)