Dropwizard Reservoir Concurrency

Dropwizard Metrics

A senior colleague was recently writing some code that required some sliding window book-keeping. Worried about throughput and concurrency, the colleague opted for a home-grown solution following the single-writer principle.

From prior experience with Dropwizard Metrics, my quick quip was “meh, just use Dropwizard’s SlidingTimeWindowReservoir”, as I had come to expect the library to provide robust & highly concurrent data structures for metrics.

He ended up diving into the implementation and sure enough — found it to be quite ingenious. It took me a little bit of understanding so I thought I would explain it here for my future self.

Underlying Datastructure

When drumming up ways to implement a SlidingTimeWindowReservoir, various data structures could be used however Dropwizard opt’s for a ConcurrentSkipListMap, which is a lock free NavigableMap.

The map is sorted on tick (time), and the interface NavigableMap, allows for easy trimming.


The key to the ConcurrentSkipListMap is the clock tick.

How do we solve the scenario where multiple writers try to record a value at the same clock granularity?

This is where the implementation is quite neat, by introducing a COLLISION_BUFFER.

Original source

In the unlikely case where multiple writers are trying to add to the Map in the same clock granularity (i.e. clock.getTick() returns the same exact value) the use of a CAS allows the code to keep looping incrementing the tick value by 1 within a COLLISION_BUFFER.

Consider the simple case where clock.getTick() returns 2 & oldTick returns 256 (1 * 256).

The first writer does: tick - oldTick and assigns newTick as tick. The compareAndSet is successful and lastTick is set as 512.

The second writer fails the CAS and loops again but now lastTick is 512.
newTick will now be 513 and be set.

Spray – Building a website

Spray what?

So for my current ongoing project we’ve been using the excellent Play! Framework; which although primarily designed for websites we used it for an API WebService. So I figure I’d do the opposite with Spray. Spray is a http framework for building web services on top of Akka actors. The next few posts will probably be around some patterns I did in getting a MVP Login demo that accepts UserPassword or OAuth[2] providers.

The following is the specific commit which I believe I’ve achieved enough of an MVP if you’d like to later browse how its done.

Composing Routes

All the examples on the Spray website show the DSL for the Routes in a single class however I found this to be confusing and exploded to be too large. There are two options people have discussed when composing routes:

  1. Create multiple HttpService actors. Have the main actor forward the RequestContext to other actors based on some route prefix
  2. Use a trait to easily compose the routes that will be given to the runRoute method of the single HttpActor

Although option (2) sounds less everything on Akka ideal, it was the option I chose as I found it very easy to bootstrap and the results were fantastic.

My next thing: Django + [Insert Here]

I’ve decided to give a bit of rest to my relentless onslaught of projects towards Hype Machine (somewhat at the request/annoyance of Anthony Volodkin). As always, I like to pick projects where I have completely almost zero experience with and use it as a good chance to learn something new and possibly have fun.

As much as it pains me to start to admit it, I think web development is slightly growing on me. It’s kind of funny however that although I’ve been hacking together Javascript for the past little while, I still don’t at all completely understand the syntax and how it works. I should probably do something start, and go buy a book and read up on it… I’ve decided then to continue in my exploration of the interwebz through creation of a Django project.

Django is a high-level Python Web framework that encourages rapid development and clean, pragmatic design.

I have yet to figure out what I would like to do with the Django application I’d like to develop. Thoughts that I were tossing around were perhaps working with an additional site/SDK such as Facebook’s, Soundcloud’s etc… to try and deliver some neat functionality. If you have any suggestions, throw them my way.

My choice to use Django was pretty easy. I love python and hate ruby.

Continue reading “My next thing: Django + [Insert Here]”

I want built in Design Patters

So I’ve been going through the book Coders At Work by Peter Seibel, which has been amazing so far. It’s almost jaw dropping reading the stories from the programmers he’s interviewed and really reading about their thoughts at the time of key development. What was most shocking of all was just how a lot of the major milestones in web development and programming as a whole were not planned. Perhaps this message is most true when someone would discuss web development and how Javascript took off to be essentially the largest programming language of the world now in terms of SLOC written.

It is comforting that everyone else seems to share a disdain for C++ and concurrency issues (no surprise in really though).

As a software Engineer, I find the talks regarding Design Patterns pretty fascinating. I mean we were introduced Design Patterns by the GoF in University as these powerful tools to help solve intricate and complex problems. However I have always felt myself leaning towards the camp of that these design patters should be intrinsic to the language if they are so important and useful. Many notable programmers from the book divide themselves clearly on Design Patters as either a blessing from god or a curse from the devil and I find myself in the latter. I think to put it best, one of the programmers make note that the use of design patterns only display the defunct capabilities of the language in use. Definitely through my experience with C#, I enjoyed using EventHandlers nicely incorporated to the language in comparison to perhaps the way Observers are performed in Java.

My only gripe with the book is how “old school programmers” are constantly referred to as “hackers” and how many of these hackers advocate that perhaps these new generations of programmers (such as myself) will never be up to par because of our lack of experience of bit twiddling and working immensely in machine code/assembly.

On the internship side of things, I am finally approaching the top of the learning curve in my opinion of working with a huge code base. Perhaps the largest hurdle was just getting a mental map of the whole API and the network of dependencies. There is a fine line between discovering the implementation or interface for a specific functionality I am looking for or just asking a coworker. I think it is important to balance between doing it yourself so that I become more familiar with the code base but however do not waste too much time going in all directions.

It’s pretty eye opening to see how a multi platform game is being produced and the difficulties in such a task.

C++ for real now!

Another work term another technology.

This term I have the fun interesting experience of getting to program in C++. The project I am helping contribute to is not your average run of the mill C++ project. I am contributing to a code base close to 1 million SLOC.

Having very limited (frankly none) experience with projects this big, I was a bit frightened of exploring the Solution explorer within Microsoft Visual Studio and finding files. However help was on the way, in the form of advice from our lead programmer. He advised me on getting Workspace Whiz!, a Visual studio Add-in.

Workspace Whiz!

Workspace Whiz is a powerful add-in for Visual Studio .NET 2002/2003/2005/2008 and Visual C++ 6 designed to improve developer productivity by making available such features as:

  1. Incremental searching of files throughout the workspace, global include/source directories, or user specified directories.
  2. Incremental tag searches either by identifier name or a parent class or namespace.
  3. Switching between the declaration and definition of functions.
    Tag completion at the press of a key while typing.
    Powerful code templates.

Quick key-bindings to immediately love:

  • ALT+SHIFT+O – This brings up a search box where you can search using RegEx for any file within the solution
  • ALT+O – switching between .cpp and header files in a sinch!

Aside from that, I thought I was a good C++ programmer. However I was quickly humbled and learnt that no C++ programming I had done in school even remotely comes close to level of complexity that I am currently sifting through.

For instance I barely even use macros when I program in C++ and barely pay attention to memory usage and optimization, three things which I am quickly getting a crash course into.

There is a high learning curve but hopefully I will prevail.

Inspiration for the masses

Getting closer to my work term I also look for inspiration to motivate me and peak my enthusiasm so that I can bring into the workplace. Browsing TED (something I’ve missed doing in a while), I immediately came across Steve Job’s Stanford Commencement speech.

Stay Hungry, Stay Foolish

I got an eerie chill listening to his story and how pieces to his puzzle of life only seemed to fit after reflecting upon them; for instance like his calligraphy lessons. The point of the talk was aimed at don’t accept anything but true love and passion for a job and constantly be on the lookout and search for that passion. I am hoping that in this new job, my search is over.

Seth Godin

I really like Seth Godin. He gives riveting talks that are funny while still driving home a message. He is a wealth of stories, of which I could sit for hours probably just listening to. Although everything i’ve heard him say ( I plan to read a few of his books) is accurate and logical he seems to be always reinventing his own wheel between each talk, but at the end of the day it’s still a wheel? Confused by what I said? I know I am.
Essentially what I get from each of his talks is that :

  1. mass marketing is dead.
  2. viral marketing is the future/present
  3. marketing now for the extremes rather than the average

These are the staples of most talks he give, and he will bundle them up in a brand new metaphor or idea differently between all he talks I’ve seen. It’s not the problem that he is reiterating the message continuously, but rather that he it seems as if he is attempting through rewording the message to create a new one?

Regardless great talks.

Take care of my thoughts, won’t you?

Final Thoughts on 3B – Mainly Concurrency not Concurrently

So I have just finished my 3B term with courses: Algorithms, SciFi, Concurrency, Software Engineering Requirements and Specification, Databases, Upper Year Design Project. From all the courses this semester, my favourite by far was Concurrency (CS343).

As I’ve covered in a previous post, the bulk all of concurrency was devoted to learning UW’s open source C++ extension uC++. My last blog covered up to only coroutines, however uC++ increased in complexity tenfolds by the end the of term. uC++ offers _Task, _Monitor, _CoMonitor constructs which are essentially native mechanisms for implementing a concurrent application. I can not go into too much detail (as it would take 4 months) but I believe the implementation of uC++ was exceptionally straightforward and allowed for daily concurrent problems to be solved easily, versus thread libraries such as those included in Java. The environment was even nice enough to inform you when a deadlock had occurred (useful for a learning environment).

Back to Work

Me in a wet suit.
This wetsuit is too tight.

So I have successfully completed my 3B Software Engineering term, surpassingly with strong marks. I was shocked to discover with enough caffeine, I had successfully managed to keep on track with gym, weight loss, hockey, studies and a generous helping of partying.

I will begin my new internship at Digital Extremes developing an upcoming Ps3 title. I am excited to try out a job I’ve dreamed about and I am hoping it does not ruin the magic, similar to learning a magician’s lies secrets. I am looking forward to the myriad of new developer related trials and information I will absorb and store here, instead of my overstuffed cranium.

Things to write

If I don’t write my thoughts out now I will forget. This upcomming 4 months will be hectic and here is why:

  • Software Engineering Project: Tournica – Insights onto developing a Ruby on Rails application.
  • Keeping track of weight loss, weight exercises and general nutritional tips to myself (mainly involving recipes I’ve found effective).
  • Digital Extremes Problems – Problems faced and hopefully solutions discovered
  • I will be attempting to repass through a large quantity of games this semester, hopefully analyzing them now with a deeper knowledge of game development.

Science Fiction

On a completely different topic, I’ve finally finished Paul of Dune , leaving me the next volume to read. I’ve recently just taken a SciFi course where the professor was overly critical of Dune. Most of his points involved the fact that it is too “Black & White”. For example, the antagonist the Baron Harokonnen is a fat, sadistic, cruel , gay and sodomizing bastard. Although most of his points I agreed with, I only did so for the original novel. I’ve actually enjoyed the extended storyline by Frank Herbert’s son and believe that he has really shown in the prequels and other novels a nice examples of conflicting heroes and anti-heroes.

Quotes I liked

The greatest personality change in a young man’s maturity occurs when he discovers that his own father is mortal, human, and fallible. [Paul of Dune, p.43]

I want no allies but myself. Friends can be as dangerous as enemies. [Paul of Dune, p.406]

A sharp edge does not automatically make a sword a good weapon. Only the wielder can do that. [Paul of Dune, p.385]

Weapons come in an infinite variety of shapes and designs. Some look exactly like people. [Paul of Dune, p.334]

Course Work

I’m considering beginning to save all my course work on my blog such as my concurrency assignments (which I am very proud of), and my work reports as well as solutions to assignments. I will think about it… I am so proud of my concurrency work; concurrency problems never failed to be easy to me.

EDIT: I have updated the projects page (look above) with some coursework and relevant documents. More to come.

uC++ and Shooting Yourself in the foot

Almost at midterms….
One of the most enjoyable courses this term have been my concurrency course CS343. In the class we are using uC++ (mico C++); which is an extension by the University of Waterloo to add high-level concurrency in an object oriented language. So far what we have covered is the ability for “Coroutines” to maintain a separate stack through execution. Using this feature we have been able to solve some interesting problems in novel ways.

Here is an example of some uC++ code. Every coroutine must have a main method which is executing upon calling the inherited Resume() function of every couroutine on the this object. Once inside main(), you can suspend() the coroutine and execution will then unwind back to the original caller. Further resumes() cause the coroutine to start from the same location where the suspend() had occurred (“partial coroutines”).

I am curious to see where the course leads us to in use of uC++. Would be perhaps even neater to learn some GPGPU “ultimate concurrency” in my opinion.

Shooting myself in the foot

Interviews have begun and I made the mistake of applying to 54 jobs. The result is that I now have tons of interviews. Sounds like a good thing? In theory perhaps; although I am finding myself short on time to complete assignments and my extra curricular activities. I will try and get a photo up soon of all the interviews I’ve had once they are complete.

Crossing my fingers

IronPython, C# 4.0 & Me

IronPython In Action

This week I had picked up a copy of IronPython in Action.
Lately I have been writing or mentioning at least how I am pretty impressed about the .NET framework/Visual Studio/C#. I found things to be extremely fluid, logical and pretty much straight forward using C# (with the nice room to get complicated if you’d like).

Python though has remained outside my scope of knowledge for quite a while. I have friends who swear by it and I’ve been always been meaning to learn properly a scripting language. I had briefly touched Python in one my CS courses, however it was using Jython which is an implementation of Python written in Java. To be honest, at the time of learning Jython (pretty much Python) scared me a little.

Dynamic programming languages scare me a little
The ability to cast on the fly scares me.
The ability to create member variables on the fly scares me.

Data attributes correspond to “instance variables” in Smalltalk, and to “data members” in C++. Data attributes need not be declared; like local variables, they spring into existence when they are first assigned to. For example, if x is the instance of MyClass created above, the following piece of code will print the value 16, without leaving a trace

I can see the benfit of being able to do it and the marvels that it can accomplish; but it seems it might cause a nightmare for debugging someone else’s code. Although I’ve never tried so hopefully I’m wrong.
I think buying this book is a good start. It seems as if Dynamic programming requires rethinking problems in a different way; similar to trying to solve a problem parellelly rather than sequentially.

The real reasons what attracted me to try and learn IronPython is the development cycle to create a sample WinForms application looks to be much shorter and much of it can afterwards be easily ported to straight C#. Finally a good CS professor once told the class that:

All programmers should know at least one scripting language

C# 4.0

Seems as if learning Dynamic programming design pattern and principiles could be useful especially with the upcomming release of C# 4.0 I was recently going over the WhitePaper for C#4.0 and they are heavily entering the forray of dynamic programming it seems especially.

C# 4.0 introduces a new static type called dynamic. When you have an object of type dynamic you can “do things to it” that are resolved only at runtime:

The C# compiler allows you to call a method with any name and any arguments on d because it is of type dynamic. At runtime the actual object that d refers to will be examined to determine what it means to “call M with an int” on it.
Other things which will allow for code refactoring seem to be introduced in C# 4.0 as well such as optional and named arguments. I can finally stop from creating so may overloaded methods.

Anyways in the mean time I will be playing with IronPython. There is something sexy about interacting with a GUI through an interactive interpreter.

What did you do with my resources?

add_action(‘wp_head’, ‘mypage_head’);

I spent a good chunk of my day today really trying to learn about .NET Garbage Collection because as I had found I was under a lot of misconceptions/misunderstandings of how it works.


I was mistaking this for something similar to a destructor which in C# is the finalize method. This method is defined for any class that inherits from the IDisposable Interface. Implementing the interface allows you to also declare the object with the “using” keyword.
The purpose of this method is to provide the programmer a chance to “clean up” the object properly before they are released especially if they have references to unmanaged code (Window handles etc..)

The part where I was thrown off and took a long time reading to understand and learn is that in most cases (pretty much all if done correctly) you still don’t need to call Dispose on the object.

For instance, say you have a managed object with an unmanaged member variable. If the Dispose design method is implemented properly there should be a Finalize method that is declared which calls Dispose () anyways.

But remember, C# doesn’t support destructors. Don’t let the identical syntax fool you.

The problems begin to creep up in doing this in a efficient way. Thankfully .NET provides all the functionality needed to properly do this. When a class implements a finalize method, the way in which it gets garbage collected is differently than other items (Garbage Collection: Automatic Memory Management in the Microsoft .NET Framework).In short, it gets put on a different queue which can result in a large performance cost.

The following example from MSDN shows how to properly implement the Dispose pattern:

You can see how using this proper dispose pattern, if Dispose() was called by the programmer the finalize method is suppressed removing the need to call it again which would essential attempt to clean up the resource twice and we reattain the lost performance.

So I am in the woods on when someone would have to or would actually want to call Dispose on an object considering the GC will eventually call it for me anyways and the following:

What doesn’t happen when you call Dispose():

  1. Calling Dispose does not prioritize the object for garbage collection. It simply unloads the object’s (unmanaged) resources from memory.
  2. Calling Dispose does not deallocate the object from memory. Only the GC does that when it performs a collection of the generation in which the object resides.
  3. The CLR does not insert or run any code not in Dispose. The behaviour of Dispose is defined by the developer.
  4. Dispose must be called explicitly by the application. It is never called by the runtime. The only exceptions are when using C#’s using statement (see ShawnFa’s article for a good explanation of what exactly goes on), and the foreach keyword in C# will result in Dispose being called on the Enumerator
  5. Dispose is NOT threadsafe. This means two threads can call Dispose on the same object at the same time. Like for any other synchronization-sensitive method, take steps to make sure this doesn’t happen. I’ll give an example of when this might happen in the next section.

The oddest aspect as well is that the object is still alive after a call to Dispose (can very well be alive for a long while if the GC is in fact not needed to be called) and can be continued to be used unless the class checks in every method isDisposed which they never do.

Who knew being a garbage could be so fascinating…