RSS

Tradeoffs in messaging oriented architectures

Messaging systems are a very important component of the data pipeline in any large scale system.   Consider a simple web application that serves all its requests online (ie directly from the source of truth data store without any preprocessing or offline index generation):

screen-shot-2016-12-10-at-2-46-54-pm

Pretty soon as load increases and horizontal scaling schemes (partitioning, replication, LB etc) have been exhausted strict consistency has to be relaxed by separating the read and write paths, which necessitates the employment of message passing (or event dispatching) across the differents components (services) in your ecosystem, resulting in (a broader version of) the following (each tier is actually Load Balanced in a cluster for high availability):screen-shot-2016-12-10-at-2-56-51-pm

Message passing in a service-oriented architecture (SOA) is very critical for scalability and availability (from enabling eventual consistency to offline processing and analytics to buffering of event firehoses and so on).   In the simplest and most abstract term, message passing can be just thought of as firing off events (user action, metrics, errors, conditions, sensor data, stock prices etc) for asynchronous consumption and processing by one or more consumers depending on application needs.    Several systems enable messaging, eg Kafka, Google PubSub, Amazon SQS, RabbitMQ, ZeroMQ, and others.  While the overarching goal is asynchronous message delivery and consumption, these systems vary greatly on delivery semantics, persistence, ordering, access pattern optimization and so on.

Delivery Semantics

When messages are sent/fired, their delivery is never guaranteed in a distributed system (due to failures, corruption, unbounded network partitions etc).   At the highest level there are 3 delivery guarantees:

  1. exactly-once – Messages are delivered exactly once, processed exactly once and “verified/acknowledged” exactly once despite the level of resiliency in a system in a scalable and cost-efficient manner.  In practice, this requires a lot of application of idempotency constraints/tricks and expensive infrastructure and coordination.
  2. at-most-once: Messages are delivered, processed, verified at most once (including never).   Unfortunately if an acknowledgment is never received by the event processor or the receiver terminated during the processing the message is lost with no traces of its status.
  3. at-least-once: Messages can be delivered repeated until a successful verification – by far the simplest guarantee to provide.

Most systems provide at-least-once guarantee, and really, it takes us a very long way.   By easing the strictness of these guarantees, implementation costs are lowered and other semantics can be built *on top* of this.  A simple and widespread of this in practise is TCP/IP which provides ordering and reliability by building on top of IP (which is unreliable and unordered).

Persistence/Durability and Consumer state

Persistence and durability of messages affect delivery and processing requirements for consumers.   This is a major tradeoff between write-only queues and message brokers.  For example write-only queues like Kafka (and Amazon Kinesis and IBM MessageHub and others) are extremely producer/publisher-centric in that messages are published (reliably and ordered) at very high rates, but ultimately it is up-to the design of the consumers (in the architecture) to ensure a meaningful processing of messages and offset advancements in the message logs/queues.  ie Messages write scaling is independent of the number (or online/offline state) of consumers.  Adversely, higher durability and persistence guarantees are required since messages may be consumed offline at a different time to when the messages were actually published (which puts an upward pressure on write latencies).

In comparison typical message brokers (like RabbitMQ and *MQ) are great for enabling complicated topic and routing strategies but come at expense of state management across the consumers (by the broker).   Additionally depending on persistence configurations, the extra cost of state management affects how inexpensively writes can be scaled (hint: it is expensive) so are suited for cases with low write rates and suited more for “online” consumers rather than offline consumption and processing of messages.   If the requirement for asynchronicity is for online consumers for immediate consumption of messages then persistence constraints can be relaxed as the need and significance of “historical” messages may be low (eg in online learning systems).

Interface to a messaging system

Despite the fact that a messaging system is essentially an abstraction for storing messages for asynchronous consumption, the tradeoffs above influence different usage scenarios.   It so happens that building on top of a simpler abstraction (like a high throughput durable ordered queue) can lead to interesting routing strategies and workflows like those possible by a more complicated message broker.   What this boils down is to let the topology of consumers (and subsequent publishers) guide your guarantees at different parts of the system which requires more fine tunning and manual approach in topology selection and design.   There are ways to build this in a more reasoned approach, which is the topic of another blog (Spoiler Alert – Stream Processing).

 

 

 
Leave a comment

Posted by on December 10, 2016 in Uncategorized

 

Machine learning @ Coursera

[TL;DR;] Machine learning is not as hard as I imagined and is a great/fun toolset to learn and Andrew Ng’s course on Coursera is the best place to start!

There is something about darkness, that brings to life all our fears. It is tempting to say this (illogical manifestation of fears) only occurs during our childhood. The slightest rattles in the attick or the creaks on the floor board is enough to unlock your wildest and horrific imaginations of perhaps the bogeyman hiding under your bed or the *monster* lurking outside your house waiting to pounce on you (something I am still terrified of as I put the garbage bins on collection night).

*But*, shine a light on the darkness the next morning and your fears vanish! The strange, seemingly inexplicable noises and phenomena you observed earlier seem absurd suddenly can be explained (racoons the roof causing the rattle, somebody walking down the kitchen to get a drink, etc).

As strange as this may seem, this fear of darkness and all that lies within is rooted in our prehistoric past.   Wierdly and worse annoyingly this fear transcends the realm of darkness and caves into our modern daily lives plainly, simply and even boringly as the FEAR OF THE UNKNOWN.

For me that fear for years has been Machine Learning.   Actually, it was a combination of fear, laziness and simply brushing off ML as simply statistics and a whole lot of heuristics.   The long thanksgiving weekend was upon me and I really really really wanted to try something different and “new”.   A lunch with a machine learning expert-colleague-friend somehow got me curious to give it a shot.  And since not a day goes by when you dont hear how awesome Andrew Ng is in the field, his ML course on Coursera seemed like the most natural place to start!

Beset by notions of the course being heavy on statistics, I’d be lying if proclaimed my eagerness to it.   However, I was curious to see what the fuss was about!   It seemed every developer, her gardener and his dog were using ML for *something*, so it could’nt really be as fearsome as I had made it to be?

You see where this is going dont you?   Like a true [hb]ollywood flick this has all the promise of taking a carefree ladies man relinquishing his bachelor lifestyle when he falls for “the one”!   Well ok let us not kid ourselves.    This is real life, not bollywood!    More like man learns to appreciate friends he seldom focussed on… or better yet hardworking family man learns to appreciate all the things his partner does for him!

Firstly on ML itself.   It is surprisingly not as heavy on statistics on I had feared.   On the contrary it is pleasantly focussed on linear algebra and from what my limited experience has shown me takes the concept of linear regression to devastating effect.   As scary as that sounds this is actually the most fun part of ML (apart from the large scale infra side of things).   Knowing this 10 years ago would have exponentially altered my life, but better than knowing this *in* 10 years time!

Secondly the course is a testament to the hardwork Andrew Ng has put in personally not only in the study of the field, but also in improving himself as a presenter.   He has clearly taken a topic that has great scope and distilled it in a clear and structured manner.   It is almost as if he has a knack for predicting the kind of questions you would have about a topic and would proceed to address it immediately.   Each lesson builds on the previous chapters and is actually very easy to follow.   Even the math is layered in such a way that the reader can take as much as they would like and go as deeply as they would want without it being a hurdle to proceed (for example the derivation of cost and gradient functions while not explained are extremely fun exercises that you should try out – coming in another blog).

Finally the choice of language.   At first being faced with Octave incited the same gasp that would be incited in any self respective developer.  But not having to implement numeric computing routines (and optimising it) is a huge blessing!    Even for an Octave/Matlab newbie (atleast not having used it for 20 years) the language and environment were painless to get (back) into.

There *are*  a couple of ways the course may have been improved.   Firstly the language.  While Octave was a pretty appropriate environment for this exercise, I am not sure the same could not have been achieved with NumPy/SciPy or in other “popular” languages.   This is not a big deal, just putting it out there.   Definitely gives me a chance to try to implement a lot of the algorithms in another language like Haskell or Swift!   And by the way if I had to *really* pick on two things about Octave – it would, oh:

  1. A lack of a good debugger.  The only way to set breakpoints it seems is via a dbstop function which is extremely unintuitive.  How about a pythonesque “break” or “set_trace” statement?
  2. This was a major annoyance for me.   1-based indexing.   This is fine when your equations actually all refer to and start with “1”.  But when you infact introduce a 0th term, just the cognitive load of translating between the indexes added a good 30% to my assignment times!

Then there were the quizzes.  Personally I am not a fan of “Exam” type assessments.   I could do assignments/projects all day!   Even within the quizzes, the numerical ones I loved as I knew how to apply the formulas I had learnt, but the ones requiring a more analysis with respect to the wording, I personally felt a bit not so much at ease with.   My OCD mind always tries to end up dissecting the hidden meaning behind how questions are worded and end up making wrong assumptions.

But overall a very effective and awesome course in teaching the concepts of ML whether you are an experienced developer or a mathematician.    Definitely recommend it (if there is still anybody out there who hasnt done the course yet!).

 
3 Comments

Posted by on November 28, 2016 in Uncategorized

 

Tags: ,

Design of an equation editor

Each time I buy a new laptop, I usually copy and backup the contents of my old laptop and it just keeps accumulating.   I was just taking a trip down memory lane and stumbled upon some really old code I had written (about 16 years old to be precise – here at github now). You know the code is *really* old as it is a collection of applets (yep java applets).   One thing that really caught my attention was an equation editor I wrote back then (you can get it up and running from the repo, but here is a screenshot of it):

screen-shot-2016-12-05-at-1-33-50-am

I am still surprised it actually worked as well as it did back then given howcertifiably little I knew.

And given that I wanted blog a few of my learnings from my first machine learning course not having an easy way to do equations on wordpress (short of taking screenshots of rendered latex) rekindled my interest in an equation editor again (for the modern web?).   So In the coming posts Il go through the design of a system that allows one to easily author and host equations (and math) for the web without having to a) create multiple copies or b) copy and paste from different rendered outputs.

Our math editor must have the following essential “features”:

  1. Perform as much as possible with the keyboard (ie latex style) without having to insert a symbol by clicking at some icon (see above screenshot).
  2. No “rendering” step ie any output must be directly reflected in the editor area so that the author can see the result live in the one place as they are typing the equations/math.
  3. Allow for both short snippets of math as well as reasonably sized proofs that can span paragraphs.
  4. Hosting, sharing and privacy controls.
  5. Renderable as an image in any blogging platform without requiring plugins to be installed.
  6. Customizable templates (ie new summation templates etc) in a secure manner.

That seems like a reasonable starting point.   In the next blog, Il go into a bit more detail into a possible API/data model for our content model looks like.   It is worth noting that a lot of this will build on top of existing awesome tools like latex and MathML.

 

 
Leave a comment

Posted by on November 5, 2016 in Uncategorized

 

A libev tutorial and wrapper

I’ve been asked to help people out with libev example code and usage for a while but I never got around to it since I hadnt used libev in ages.  However I have a need for a simple server framework (more on this in another post).   So I figured I’d publish a simple libev tutorial.  More importantly I will create a C library that is a wrapper on top of libev to handle and maintain multiple connections in a clean and extendible way.

A quick introduction to libev is in order.  Back in the day, handling multiple network client connections was either done using multiple threads (one thread per connuction) or via asynchronous apis that multiplexed between several io events across the various connections.  Several APIs existed to enable the later (select/poll, epoll, kqueue etc).  Each of the methods had their own performance guarantees and worse still had platform dependant compatibility issues.  To get around this libevent was developed to provide a uniform interface hiding platform specific details.  Libev developed later was designed to simplify and cleanup several aspects of libevent (eg stripped down, threadsafe, low watcher overhead etc).

The core concept in libev is that of an event loop – a loop that runs continuously listening registered events and calling the associated callback functions.   Events could be io events like file descriptors ready for reads/writes, socket connections accepted etc.

With that it is time to dive in.

Let us first start with a socket server structure that is the context for all things related to a multi client TCP server:

struct LEWSocketServer {
    // A pointer to the event loop that is handling event on 
    // this server socket.
    struct ev_loop *eventLoop;

    // Host the server socket is bound to (not used for now)
    char *host;

    // Port the server is running on
    int port;

    // The socket associated with the server.
    int serverSocket;
    struct ev_io acceptWatcher;

    // A listener structure for events on this socket.
    LEWSocketServerListener *listener;
};

A simple server socket API would begin with being able to start a server:

SSSocketServer *ss_start_server(const char *host, 
                                int port,
                                SSSocketServerListener *listener);

SSSocketServerListener is a structure that helps clients manage the callbacks associated with the individual connections instead of having to deal directly with the libev api.

typedef struct LEWSocketServerListener {
    /**
     * Called when a connection was accepted.  This is an opportunity
     * for the handler of this method to create any connection specific data
     * to be created and returned so that any further activities on the connection
     * will be invoked on this object.
     *
     * This method must NOT return NULL.  If it returns NULL, then the connection is refused.
     */
    void *(*createConnectionContext)();

    /**
     * Called when data has been received for this connection from a client.
     */
    void (*processData)(LEWConnection *connection, const char *data, size_t length);

    /**
     * Called to indicate connection was closed.
     */
    void (*connectionClosed)(LEWConnection *connection);

    /**
     * Called to ask the connection handler for data that can be written.
     * The buffer is an output parameters to be updated by the listener.
     * Return the number of bytes available in the buffer.
     */
    size_t (*writeDataRequested)(LEWConnection *connection, const char **buffer);

    /**
     * Called to indicate that nWritten bytes of data has been written and that the connection
     * object should update its write buffers to discard this data.
     */
    void (*dataWritten)(LEWConnection *connection, size_t nWritten);
} LEWSocketServerListener;

The general structure of a connection follows:

  1. Server socket is in listen state
  2. When a new connection is accepted, a client socket is created and added libev’s eventloop for read events.
  3. write events for the client socket are not enabled. The level-triggered nature of libev (by default) will cause unnecessary write event callbacks even when there is no data to be sent. So a design choice made was to make the api caller responsible to initiate writes when it had data to be sent.
  4. When data is available to be read, it is sent via the listener’s processData callback (along with the connection object associated with the client).
  5. When the caller has data to write it invokes the connection’s writeable attribute.
  6. When the writeable attribute on a connection is set, the write events on the client socket are enabled which invokes the writeDataRequested method on the caller until it return 0 (bytes).
  7. Additionally the library calls the dataWritten callback on the listener so that the client can update its own write data buffers (to pop off the written/sent data).

With this the echo server now looks like:


#include 
#include 
#include 
#include "server.h"

typedef struct EchoConnection {
    char readBuffer[4096];
    int length;
} EchoConnection;

/**
 * Called when a connection was accepted.  This is an opportunity
 * for the handler of this method to create any connection specific data
 * to be created and returned so that any further activities on the connection
 * will be invoked on this object.
 *
 * This method must NOT return NULL.  If it returns NULL, then the connection is refused.
 */
void *createConnectionContextCallback()
{
    EchoConnection *out = calloc(1, sizeof(EchoConnection));
    return out;
}

/** 
 * Called when data has been received for this connection from a client.
 */ 
void processDataCallback(LEWConnection *connection, const char *data, size_t length)
{   
    EchoConnection *echoconn = (EchoConnection *)lew_connection_get_context(connection);
    memcpy(echoconn->readBuffer, data, length);
    echoconn->length = length;
    lew_connection_set_writeable(connection);
}   

/**
 * Called to indicate connection was closed.
 */
void connectionClosedCallback(LEWConnection *connection)
{
    printf("Connection closed...\n");
} 

/**
 * Called to ask the connection handler for data that can be written.
 * The buffer is an output parameters to be updated by the listener.
 * Return the number of bytes available in the buffer.
 */
size_t writeDataRequestedCallback(LEWConnection *connection, const char **buffer)
{
    printf("Write data requested...\n");
    EchoConnection *echoconn = (EchoConnection *)lew_connection_get_context(connection);
    *buffer = echoconn->readBuffer;
    return echoconn->length;
}

/**
 * Called to indicate that nWritten bytes of data has been written and that the connection
 * object should update its write buffers to discard this data.
 */
void dataWrittenCallback(LEWConnection *connection, size_t nWritten)
{
    EchoConnection *echoconn = (EchoConnection *)lew_connection_get_context(connection);
    echoconn->length -= nWritten;
}

int main(void)
{
    LEWSocketServerListener listener;
    listener.createConnectionContext = createConnectionContextCallback;
    listener.processData = processDataCallback;
    listener.connectionClosed = connectionClosedCallback;
    listener.writeDataRequested = writeDataRequestedCallback;
    listener.dataWritten = dataWrittenCallback;

    lew_start_server(NULL, 9999, &listener);
}

While there is still some work to be done to handle edge cases this would be relegated to the library rather than leaking out to the client code and most the client code is actually to do with connection logic rather than messing about with event loops.

Full source code is available at: https://github.com/panyam/LibEvWrapper

 
Leave a comment

Posted by on December 12, 2015 in Uncategorized

 

2014 in review

The WordPress.com stats helper monkeys prepared a 2014 annual report for this blog.

Here’s an excerpt:

A San Francisco cable car holds 60 people. This blog was viewed about 2,800 times in 2014. If it were a cable car, it would take about 47 trips to carry that many people.

Click here to see the complete report.

 
Leave a comment

Posted by on December 29, 2014 in Uncategorized

 

Elements of Programming Interviews

This is an index to the problems from THE book being solved in haskell (and counting). Some of the trivial ones will only be attempted on demand!

Chapter 5 – Primitive Types

EPI 5.1: Find the number of bits set in a number (and Parity)


EPI 5.4: Closest integers with the same weight


EPI 5.5 – Generating Power Sets


EPI 5.6 String to Integer inter conversion functions


EPI 5.7 – Generalised conversion between bases


EPI 5.8 – Spreadsheet Column Encoding


EPI 5.9 – Elias encoding and decoding


EPI 5.10 – Greatest Common Divisor

Chapter 6 – Strings and Arrays


EPI 6.1 Dutch Flag Partition


EPI 6.3 – Max Difference


EPI 6.4 – Generalized Max Difference


EPI 6.5 – Subset summing to 0 mod n


EPI 6.6 – Longest contiguous increasing subarray


EPI 6.13 – Rotating an array


EPI 6.15 – Printing a 2D array in spiral order


EPI 6.18 – Run-Length Encoding


EPI 6.19 – Reversing words in a string

 

EPI 6.18 – Run-length Encoding

Problem:

Implement functions to run length encode a string and decode the RLE value of an encoded string.

For example “aaaabcccaa” should be encoded to “4a1b3c2a”, while “3e4f2e” would be decoded to “eeeffffee”.

Solution:

Encoding is straight forward:

run_length_encode :: [Char] -> [Char]
run_length_encode xs = run_length_encode' 0 '|' xs
    where
        run_length_encode' 0 _ [] = []
        run_length_encode' 0 _ (x:xs) = run_length_encode' 1 x xs
        run_length_encode' count curr_ch [] = (show count) ++ [curr_ch]
        run_length_encode' count curr_ch (x:xs)
            | curr_ch == x = run_length_encode' (count + 1) curr_ch xs
            | otherwise = (show count) ++ [curr_ch] ++ run_length_encode' 1 x xs

Decoding is also fairly straightforward, except we just need to accumulate the “count” before that many characters can be output:

run_length_decode :: [Char] -> [Char]
run_length_decode xs = run_length_decode' 0 xs
    where
        run_length_decode' _ [] = []
        run_length_decode' count (x:xs)
            | isDigit x = run_length_decode' ((count * 10) + (digitToInt x)) xs
            | otherwise = (replicate count x) ++ run_length_decode' 0 xs
 

Tags: , , , ,