On Train Rides and Building Histograms

So you are developing your server application, congrats! no server application is complete without some sort of live telemetry. usually comes in form of:

  1. [Moving/Rolling] Count of event X, or Count of X where X > Y over past T period.
  2. [Moving/Rolling] Sum of X over the past T period.
  3. [Moving/Rolling] Sum/Average/Total/Count/StdDev of X (where X > Y) over past T period.

Sounds familiar? yes it does, because we have all faced one way or another with these requirements. The “live” part here is because you need to answer with data either from memory from some persisted store. Data is usually presented to user plotted on a histogram like diagram.

The requirements itself is not that hard but when you consider locking, memory management you will see the challenge that usually comes associated with them. add to that histogram is usually peripheral to the actual server application (hence it shouldn’t eat away memory nor CPU from the actual server application logic).

In a lot of ways you are trying to build a train conductor – obviously a more elaborate one – like component. Remember that guy/lady that walks around with a clicker in hand, clicks for it every person on the train.

Enter Clicker

The basic idea is a linked List that gets automatically trimmed after a defined period (click keep period). The linked list shouldn’t be locked under any condition. Each *Click* adds a node at the head. The list supports:

  1. Count()
  2. Count (in a timespan) : where timespan is shorter or equal to click keep period
  3. General purpose do & and do(in a timespan), do function takes a function pointer and execute it passing to it a copy of the list where in your function you can do max, average, StdDev or whatever you imagine.
  4. Clicks are events, by default it has a Value, but you can extend it as you like (to include other aggregates).

Chained Clickers, Calculation & Trimming

Because of the way it is implemented I can chain clickers (one for last min, one for last hour and so on) like

// this keeps the clicks for 1 min, then remove anything older
        private Clicker<MyClickType> m_MinuteClicker = new Clicker>MyClickType>(TimeSpan.FromMinutes(1));
// this keeps the clicks for 1 hour, then remove anything older
        private Clicker<MyClickType> m_HourClicker = new Clicker<MyClickType>(TimeSpan.FromHours(1));

// chain minute clicker into hour clicker
m_MinuteClicker.OnTrim = (head) => OnMinuteClickerTrim(head);


// later in the code
// whenever I need to record an event 
m_MinuteClicker.Click(new MyClickType(Add or Processed));

// Let us say i want to know the average of added clicks per min for the last hour
       return m_HourClicker.Do(head =>
                {
                    int sum = 0;
                    int count = 0;
                    var curr = head;
                    while (curr != null && curr.ClickType == Added)
                    {
                        sum = (int) curr.Value;
                        count++;
                        curr = (MyClickType)curr.Next;
                    }
                    return count == 0 ? 0 : sum/count ;
                }); 



// roll up totals into mins, saved for maximum of 1 hour
void OnMinuteClickerTrim(MyClickType head)
{
// my click type is either add event or processed event
            var totalAdd = 0;
            var totalProcessed = 0;

            var curr = head;
            while (curr != null)
            {
                if (curr.ClickType == Added)
                    totalAdd++;
                else
                    totalProcessed++;
            }

            // harvest 
            m_HourClicker.Click(new WorkManagerClick() { ClickType = Add, Value = totalAdd });
            m_HourClicker.Click(new WorkManagerClick() { ClickType = Processed, Value = totalProcessed});
}

the code is published here https://gist.github.com/khenidak/e78a0a3fd6fa071a4308

till next time

@khnidk