Author Archives: seanbo

Reactor vs. Proactor: Part 1 – The Reactor

Currently I’m working with Python’s “event-driven networking engine” Twisted and Boost ASIO. Both libraries make use of the Reactor and Proactor design patterns.

Finding information on the difference between the two patterns was difficult. The best source I found was Pattern-Oriented Software Architecture Volume 2 (Patterns for Concurrent and Networked Objects) by Schmidt, Stal, Rohnert, and Buschmann.

I was interested in understanding the difference between Reactors and Proactors while learning about Linux system calls used in the patterns (like epoll).

This is the first post in a series where I’ll share what I’ve learned about the Reactor design pattern. In later posts we’ll go over the Proactor pattern.

A Reactor allows you to register event handlers. In this example, when you receive the event signified by “one” it will fire the callback printing “one handler called!”. Similarly there is an event handler for “two”. In the real world these would more likely be events triggered by client connects to a server or responses from an HTTP request, for example.

int main() {
    Reactor reactor;

    reactor.addHandler("one", [](){
        std::cout << "one handler called!" << '\n';
    });
    reactor.addHandler("two", [](){
        std::cout << "two handler called!" << '\n';
    });

    reactor.run();
}

Reactors need to manage what is known as a synchronous event demultiplexer like epoll or select. Epoll, which is what we’ll use in this example, is described in the Linux man pages as an “I/O event notification facility”. It is synchronous in that when we call wait it blocks: our application stops processing when wait is called until the operating system lets us know an event has occurred. In this example we tell epoll to let us know when input has been entered by registering interest in the stdin file descriptor. Once we are notified by epoll that a subscribed-to event has arrived we fire off the corresponding handler. In essence this is what a Reactor does: it utilizes a system call like epoll or select to listen to events and fires off a handler when it receives them.

In the following source code our simplified Reactor class manages an Epoll instance. The reactor waits for epoll to let us know something was entered on standard input and then fires off the matching event handler.

class Reactor {
 public:
    Reactor() {
        epoll.control();
    }

    void addHandler(std::string event, std::function<void()> callback) {
        handlers.emplace(std::move(event), std::move(callback));
    }

    void run() {
        while (true) {
            int numberOfEvents = wait();

            for (int i = 0; i < numberOfEvents; ++i) {
                std::string input;
                std::getline(std::cin, input);

                try {
                    handlers.at(input)();
                } catch (const std::out_of_range& e) {
                    std::cout << "no handler for " << input << '\n';
                }
            }
        }
    }

 private:
    std::unordered_map<std::string, std::function<void()>> handlers{};
    Epoll epoll;

    int wait() {
        int numberOfEvents = epoll.wait();
        return numberOfEvents;
    }
};

An example run of the program:


$ g++ reactor.cpp -std=c++14
$ ./a.out
a
no handler for a
b
no handler for b
one
one handler called!
two
two handler called!
one
one handler called!
c
no handler for c

Here is a simplified epoll wrapper that does leave out a lot of details and error handling for the sake of brevity:

class Epoll {
 public:
    static const int NO_FLAGS = 0;
    static const int BLOCK_INDEFINITELY = -1;
    static const int MAX_EVENTS = 1;

    Epoll() {
        fileDescriptor = epoll_create1(NO_FLAGS);

        event.data.fd = STDIN_FILENO;
        event.events = EPOLLIN | EPOLLPRI;
    }

    int control() {
        return epoll_ctl(fileDescriptor, EPOLL_CTL_ADD, STDIN_FILENO, &event);
    }

    int wait() {
        return epoll_wait(
                fileDescriptor,
                events.begin(),
                MAX_EVENTS,
                BLOCK_INDEFINITELY);
    }

    ~Epoll() {
        close(fileDescriptor);
    }

 private:
    int fileDescriptor;

    struct epoll_event event;
    std::array<epoll_event, MAX_EVENTS> events{};
};

Reactors can be beneficial in that they lack the overhead (context switching, shared mutable data safety, etc.) associated with servers that spawn a thread per connection. In the case of a Reactor it is important that the handler functionality is able to complete quickly so that the application can return to servicing other events as soon as possible.

You can also checkout this reactor-proactor-example source code on my Github page.

Capturing *this in C++11, 14 and 17

A common need in asynchronous programming is the ability to use *this inside a callback.

In C++11 if you want to create a copy of *this you’d introduce a new lvalue:

auto self = *this;
client->request([self]() {
    self.logger->log("Completed request!");
});

C++14 allows initialization expressions inside the lambda capture. Doing so is helpful for working with move semantics but also allows us to get rid of a line from the C++11 example above.

client->request([self = *this]() {
    self.logger->log("Completed request!");
}); 

With C++17 you can create a copy of *this by doing the following. Note that doing so no longer allows you to use the original pointer this inside the lambda body (unless you created a separate lvalue for it).

client->request([=, *this]() {
    logger->log("Completed request!");
    // "this" is no longer from the outside scope
});

For more info on C++17 lambda capture off *this, visit: P0018R3 Lambda Capture of *this by Value as [=,*this]

Integration Testing Transactional Methods with Spring Boot

Consider a service method in your Spring Boot project that both writes to a queue and a database. If your write to the queue is successful, yet the database call throws an exception, you might not want to keep that item on the queue. Writing the code for this yourself could be cumbersome. Fortunately, Spring provides the handy @Transactional annotation. In this post we’ll look at how to write an integration test for methods using this annotation.

Let’s start with an empty template class for integration test:

@SpringApplicationConfiguration(classes = { Application.class, TestConfig.class })
@WebAppConfiguration
@DirtiesContext
@Slf4j
public class OurCustomServiceIT extends AbstractTestNGSpringContextTests {

}

@SpringApplicationConfiguration loads and configures an ApplicationContext for integration tests. It’s similar to @ContextConfiguration but uses Spring Boot’s SpringApplicationContextLoader. We provide the Application and TestConfig classes. Application is your main Spring Boot entry-point class that contains SpringApplication.run. TestConfig is a custom class we’ll use later to provide mocks for our test.

Use @WebAppConfiguration over @WebIntegrationTest in this example since we will not be testing the HTTP entrypoint into our application (through REST).

@DirtiesContext is necessary here. What it does is mark the ApplicationContext as dirty, thus requiring it to be reloaded for the next integration test. We are going to be using a mocked bean. Since Spring caches the ApplicationContext between test runs, we want to ensure it is not cached with this mocked bean.

@Slf4j is a lombok convenience annotation to prevent us from typing the long-winded:

private static final Logger LOG = LoggerFactory.getLogger(OurCustomServiceIT.class);

Finally extending AbstractTestNGSpringContextTests sets our ApplicationContext up for support with a TestNG environment. Alternatively, you could extend AbstractJUnit4SpringContextTests if you want to use JUnit4.

Now what did we need that TestConfig for?

@Configuration
public class TestConfig {
    @Mock
    RabbitOperations rabbitOperations;

    public TestConfig() {
        MockitoAnnotations.initMocks(this);
    }

    @Bean
    public RabbitOperations rabbitTemplateWithExchange() {
        return rabbitOperations;
    }
}

@Configuration marks our class for use by the Spring context to gather beans.

What we’re doing here is creating a mocked implementation of our queue client. Why do we want a mocked version? Because we are going to simulate the queue client throwing an exception. We want to ensure that when this exception is thrown, that the database entry is not persisted. Indeed, we want the database transaction to rollback.

Now, let’s add the internals to our integration test:

@SpringApplicationConfiguration(classes = { Application.class, TestConfig.class })
@WebAppConfiguration
@DirtiesContext
@Slf4j
public class OurCustomServiceIT extends AbstractTestNGSpringContextTests {
    @Autowired
    private OurCustomService service;

    @Autowired
    private OurCustomRepository repository;

    @Autowired
    @Qualifier("rabbitTemplateWithExchange")
    private RabbitOperations mockedRabbitTemplateWithExchange;

    @Test
    public void testMethodIsTransactional() {
        final String name = "foo";
        doThrow(new RuntimeException("Fake RabbitMQ Failure!")).when(mockedRabbitTemplateWithExchange).send(any(String
                .class));
        try {
            service.addRequestToQueue(name);
        }
        catch (RuntimeException e) {
            LOG.info("Expected failure to trigger transaction caught");
        }

        List<DatabaseRecords> results = repository.getRecords().stream()
                .filter(record -> record.getName().equals(name))
                .collect(Collectors.toList());

        assertThat(results).hasSize(0);
    }
}

We inject our service and repository. Next, we inject our mocked queue client. I use the @Qualifier so I can give the variable name a prefix of “mocked” (as in mockedRabbitTemplateWithExchange). Make sure that people know you are using a mocked version both in this test AND inside your spring boot application.

Finally, the test tells the queue client to throw an exception when it is used. Since it threw an exception, we don’t want our database write to persist – even though the exception occurs after the database call has been made. We check the records in the database to ensure that it has indeed not been written.

Let’s make a red, failing implementation:

public void addRequestToQueue(String name) {
    repository.write(name);
    rabbit.send(name);
}

There’s no @Transactional annotation telling the database to rollback when the queue client throws a RuntimeException.

Finish things up by adding a @Transactional annotation to the addRequestToQueue method and your test should pass with green.

Javascript’s Prototype-Based Inheritance

Let’s create a Dragon “class” in Javascript that we can use to inherit from.

var Dragon = function(color) {
  this.color = color;
}

// prototype is a special object used for inheritance in Javascript.
// We could have added the attack method as a member variable similar to color, however we'll use it on the prototype
// later.
Dragon.prototype.attack = function() {
  console.log("The " + this.color + " dragon breathes fire!");
}

var dragon = new Dragon("red");
dragon.attack();  // The red dragon breathes fire!

Calling “new Dragon();” creates a new object that inherits anything set on the Dragon.prototype object. First, Javascript will check to see if a property exists on Dragon itself. If it doesn’t exist on Dragon, it will check Dragon.prototype. We can check to see whether properties exist on Dragon or it’s prototype as follows:

dragon.hasOwnProperty("color"); // true
dragon.hasOwnProperty("attack"); // false, this is not an "own" property - it's part of the prototype

The hasOwnProperty method differentiates between an objects properties and those that were inherited from it’s prototype. Where does the “hasOwnProperty” method come from? The hasOwnProperty method comes from Object.prototype:

1) dragon inherits from Dragon.prototype
2) Dragon.prototype inherits from Object.prototype
3) Object.prototype inherits from “null” prototype – essentially, null allows is the dead-end in our prototype chain

Let’s try some inheritance out:

Dragon.prototype.fly = function() { console.log("The " + this.color + " dragon flaps its wings and flies!"); }
dragon.fly(); // The red dragon flaps its wings and flies!

// Now lets create a Baby Dragon

var BabyDragon = function(color) {
  Dragon.call(this, color); // Essentially super().  Set color, but on BabyDragon, not Dragon.
  this.fly = function() { console.log("The " + this.color + " dragon tries to fly, but is still too young!"); }
}

// We need to set the BabyDragon prototype to inherit from the Dragon prototype.  This will give us access to the attack method.
BabyDragon.prototype = Object.create(Dragon.prototype);

// Set this, otherwise it will be Dragon
BabyDragon.prototype.constructor = BabyDragon;

var baby = new BabyDragon("green");
baby.fly(); // The green dragon tries to fly, but is still too young!
baby.attack(); // The green dragon breathes fire!

ECMAScript 2015 (6th Edition) introduces the class keyword to Javascript which adds some interesting syntatic sugar for you to explore.

Recursion Optimization: Fibonacci Sequence in Javascript

The Fibonacci Sequence: 1, 1, 2, 3, 5, 8, 13, 21, …

The nth Fibonacci number is defined as (n-1) + (n-2). For example, the 5th Fibonacci number is the sum of the 4th (n-1) and 3rd (n-2) Fibonacci numbers: 3 + 2 = 5.

The 8th Fibonacci number is the sum of the 7th (8-1) and 6th (8-2) Fibonacci numbers: 13 + 8 = 21.

A recursive Fibonacci function in Javascript works as follows:

var recursiveFib = function(n) {
  // base case: the first two Fib numbers are 1
  if (n <= 2) { 
    return 1; 
  } else {
    // The nth Fib # is (n-1) + (n-2)
    return recursiveFib(n-1) + recursiveFib(n-2);
  }
}

This works, but my browser cannot compute recursiveFib(100); Too much for it to handle?

We can optimize this function using tail-recursion. In the recursiveFib function, a call stack is created to keep track of all the calls to recursiveFib.

function tailRecFib(n) {
  return function(n,a,b) {
    return n > 1 ? arguments.callee(n-1,b,a+b) : a;
  }(n,1,1);
}

This tail-recursive version is more efficient because it simply accumulates the Fibonacci computation in an argument to the function (a+b). No longer do we need to store a tremendous amount of calculations on the stack – it’s now treated much like an iterative for loop.

Finally, there exists a closed-form formula to calculate the nth Fibonacci number. Using this formula, we can arrive at the function:

function closedFormFib(n) {
  var sqrt5 = Math.sqrt(5);
  var a = (1 + sqrt5)/2;
  var b = (1 - sqrt5)/2;
  var ans = Math.round((Math.pow(a, n) - Math.pow(b, n))/sqrt5);
  return ans;
}

* These functions do contain rounding errors due to Javasript’s internal handling of numbers.

Differentiating INNER, LEFT, and RIGHT SQL JOINs

An SQL JOIN returns rows from multiple tables based on a common field between them. Consider the following users and orders tables:

users table

user_idfirst_namelast_nameemail
1JohnAdamsjohna@gmail.com
2MarkSmithmsmith@aol.com
3TomWilliamsontwilliamson@gmail.com

orders table

order_iduser_idtotaldate
10012500.992015-08-02
1002259.992015-08-03
10033602015-08-04

Typically JOIN is synonymous with INNER JOIN. Let’s perform an INNER JOIN on the users and orders table:

SELECT users.user_id, users.first_name, users.last_name, orders.total
FROM users
INNER JOIN orders
ON users.user_id = orders.user_id
ORDER BY users.user_id

Our result, which merges the users and orders tables by matching the user_id field, gets the user_id, first_name, last_name, and total, and finally sorts them by user_id:

user_idfirst_namelast_nametotal
2MarkSmith500.99
2MarkSmith59.99
3TomWilliamson60

An INNER JOIN is similar to the intersection of a set in mathematics, or the intersection of a Venn Diagram. The result includes all the rows with a match on users.user_id = orders.user_id. The result will not include any rows from the left or right table (users and orders, respectively) that do not contain a match within the ON clause.

INNER JOIN

A LEFT OUTER JOIN will return the same result as an INNER JOIN, however it will also include every row in the left table (users), even if there is no match within the ON clause. Fields that do not match will be marked with NULL:

SELECT users.user_id, users.first_name, users.last_name, orders.total
FROM users
LEFT OUTER JOIN orders
ON users.user_id = orders.user_id
ORDER BY users.user_id

user_idfirst_namelast_nametotal
1JohnAdamsNULL
2MarkSmith500.99
2MarkSmith59.99
3TomWilliamson60

LEFT OUTER JOIN

Likewise a RIGHT OUTER JOIN will include all of the rows from the right table (orders) and mark non-matches with a NULL:

user_idfirst_namelast_nametotal
2MarkSmith500.99
2MarkSmith59.99
3TomWilliamson60

RIGHT OUTER JOIN

In this particular example, every row in the right table (orders) has a match and no NULL fields are returned.

Finally, if not evident from the examples given above, it should be noted that LEFT and RIGHT refer to the order of the tables listed in the SQL statement. In our example, users is listed first (becoming the left table) and orders is listed next (effectively making it the right table).