Implementing Quicksort-as-a-(Micro)Service

TL;DR Microservices are not so cumbersome and tedious to develop as you may think. They only require the right tool (Jolie) for the job. I report my experience in implementing a simple staple utility (quicksort) as-a-service. The service recursively calls itself using internal memory but it is very easy to make it accept also HTTP calls or to distribute the workflow on different instances of the same service.

Scenario: for the release of the new Jolie website we decided to add external blog posts in a dedicated “blogs” section. After ~230 lines of Jolie code we had our own news retrieval service. The service reads the RSS feed from our collection of blogs and serves them as a single flow of news.

Problem: we had different sources that returned a stream of articles ordered by date. We collected them into a single stream but still they were not ordered properly.

Solution: one word (well actually a compound, but still) QuickSort-as-a-(micro)service

QuickSort …

Best thing I love about QuickSort is its elegant recursive implementation.

As Wikipedia puts it (slightly modified):

function quicksort(A)
	less, equal, greater := three empty arrays
	if length(A) > 1  
  	pivot := select any element of A
  	for each x in A
      if x <= pivot then add x to less
      if x > pivot then add x to greater
  	quicksort(less)
  	quicksort(greater)
  A := concatenate(less, pivot, greater)

In English, you want to order A, which is an array of sortable (comparable) elements. You take a pivot element (e.g., from the middle of the array) and cycle through the whole array to divide it into two halves, less and greater. less will contain all elements lesser than or equal to the pivot and greater the remaining greater-than-pivot elements. Done that you can apply quicksort to less and greater which will order them. Finally you assemble less, the pivot, and greater (in this order) and return the result.

… as a (Micro)Service

Let us take that pseudo-code implementation of quicksort and translate it into a microservice. (Btw, if you are into THAT kind of microservice-porn, here you can find a recursive algorithm of the Tower of Hanoi).

In the pseudo-code we define a function called quicksort. Being a little more detailed we can add some typing to it. We want quicksort to take an array and return it sorted, hence we have something like function quicksort( Array[ T ] : A ) : Array[ T ]. T being the type of the elements we want to sort.

In Jolie we can model function calls as request-response operations. Hence we can define the interface of our quicksort service as

interface QuickSortInterface {
	RequestResponse: quicksort( QSType )( QSType )
}

Jolie interfaces describe which operations a service can implement and the type of their input and output. The type of QSType can be something like

type QSType: void {
	.e* : T
}

Remember that every variable in Jolie is a tree ¹, therefore our type will have a root, say QSType, which is empty (void) and then we allow it to have 0 to n leaves e[0], …, e[n-1] of type T.

As said, let us begin with the request-response operation

quicksort( req )( res ){ ... }

As you might guess, req and res have both type QSType. The body of the operation will contain the behaviour of the quicksort.

function quicksort( A )
 if length(A) > 1
  pivot := select any element of A
  for each x in A
   if x <= pivot then add x to less
   if x > pivot then add x to greater
  quicksort(less)
  quicksort(greater)
 A := concatenate(less, pivot, greater)

quicksort( req )( res ){
 if( #req.e > 1 ){
  // 1. partition the request
  pivot = #req.e / 2;
  for ( i = 0, i < #req.e, i++ ) {
   if( i != pivot ) {
    if( req.e[ i ] <= req.e[ pivot ] ) {
     less.e[ #less.e ] << req.e[ i ]
    } else {
     greater.e[ #greater.e ] << req.e[ i ]
    }
   }
  };
  // 2. order the two partitions
  // 3. merge the result
 } else {
  res << req
 }
}

First we check if the array in the request has less than 2 elements. Jolie provides the # operator that returns the number of leaves in the branch at its right. Its behaviour is not different from the usual req.e.length of C++/Java. In case there are less than 2 elements (else branch), we return as response exactly the request. res << req (<< being the deep-copy operator) means “copy the whole structure and values of variable req in res”.

If there are more elements we can sort them. Although there are plenty of optimisations [1][2][3][4], we will stick to the good ol’ “take the middle element as pivot”. We use # to address the n-th+1 leaf and store the whole structure of the i-th element of req.e.

Beware: pedantic observation!. We are using << to copy the values of the leaves. Why didn’t we use the expression less.e[ #less.e ] = req.e[ i ]? If we assume the type T of req.e[ i ] to be a basic type (int, string, double, …), using = would yield the same result as <<. On the contrary, if we want to bring along a sub-structure rooted in req.e[ i ] (e.g., blog posts) we need to deep-copy it.

Let us get to the recursive calls. We need to create two ports, one inputPort and one outputPort.

outputPort SelfOut {
	Interfaces: QuicksortInterface
}

inputPort SelfIn {
	Location: "local"
	Interfaces: QuicksortInterface
}

We use the "local" location, which is a lightweight medium that exploits in-memory messages between services running in the same interpreter. In this case we use it to let the QuickSort Service call itself.

Almost finished. Let us invoke quicksort on the two partitions created earlier.

// 2. order the two partitions
quicksort@SelfOut( less )( res );
quicksort@SelfOut( greater )( greater )

Note that we store the sorting of less in res. This comes handy when we will merge the result together

// merge the result
res.e[ #res.e ] << req.e[ pivot ];
for ( i=0, i<#greater.e, i++) {
	res.e[ #res.e ] << greater.e[ i ]
}

We append the pivot and the elements of greater to res, which concludes the behaviour of quicksort.

Just a couple of things and we are ready to run our service. First, we set to concurrent the execution mode of our service. In concurrent mode Jolie creates a new instance of the service at any new request.

execution{ concurrent }

and second we add the init procedure which, like the main, is a special procedure. If present init is executed before the main. To enable quicksort call itself we need to set the local location of outputPort SelfOut to the value returned by the runtime service

init { getLocalLocation@Runtime()( SelfOut.location ) }

Runtime is a service of the Jolie Standard Library, imported with the line include "runtime.iol"

To wrap up

Let us pull together the parts we wrote above into a single Jolie service (for simplicity I set the type of the content of the array to int). Note that we enclosed operation quicksort into the main procedure.

include "runtime.iol"

execution{ concurrent }

type QSType: void{
	.e*: int
}

interface QuicksortInterface {
  RequestResponse: quicksort( QSType )( QSType )
}

inputPort SelfIn {
  Location: "local"
  Interfaces: QuicksortInterface
}

inputPort SelfHttp {
  Location: "socket://localhost:8000"
  Protocol: http
  Interfaces: QuicksortInterface
}

outputPort SelfOut{
  Location: "local"
  Interfaces: QuicksortInterface
}

init { getLocalLocation@Runtime()( SelfOut.location ) }

main
{
  quicksort( req )( res ){
  if( #req.e > 1 ){
   // 1. partition the request
   pivot = #req.e / 2;
   for ( i = 0, i < #req.e, i++ ) {
    if( i != pivot ) {
     if( req.e[ i ] <= req.e[ pivot ] ) {
      less.e[ #less.e ] << req.e[ i ]
     } else {
      greater.e[ #greater.e ] << req.e[ i ]
     }
    }
   };
  // 2. order the two partitions
  quicksort@SelfOut( less )( res );
  quicksort@SelfOut( greater )( greater );
  // merge the result
  res.e[ #res.e ] << req.e[ pivot ];
  for ( i=0, i<#greater.e, i++) {
    res.e[ #res.e ] << greater.e[ i ]
    }
  } else {
   res << req
   }
  }
}

Did you notice I also added a new port to the service?

inputPort SelfHttp {
  Location: "socket://localhost:8000"
  Protocol: http
  Interfaces: QuicksortInterface
}

What it does is to enable the service to accept a request from any browser. How cool is that?! We developed an application for in-memory requests and with just 4 lines of declarative code we have it accepting calls from HTTP! Fire up your browser and write this URL:

http://localhost:8000/quicksort?e=5&e=21&e=13&e=34&e=1&e=1&e=2&e=3

(or if you are REALLY lazy click here, after you launched the quicksort service, of course.)

Still here? Get yourself a Jolie and start tinkering with microservices :)

I want more

You want more? Really? Ok, one last candy. As you may be aware of (or maybe not) the ; in Jolie does not mark the end of a statement. It is the sequential composition operator by which A ; B means after the execution of A executes B. Jolie also provides the parallel composition operator which executes two statements concurrently.

Want to optimise for multi-core computation?

{ quicksort@SelfOut( less )( res ) | quicksort@SelfOut( greater )( greater ) }

you can send two parallel requests to quicksort. Note that we enclosed the two requests into a scope. In this way the instructions after the scope will be performed only when both requests return their results.

Want more? Take a cloud, deploy several copies of quicksort and call them

{ quicksort@Instance1( less )( res ) | quicksort@Instance2( greater )( greater ) }

And this is only the tip of the iceberg as you can aggregate a cloud of services into a single point of workflow distribution, as well as proxies, load-balancers, and many other architectural patterns.

Always without leaving the Jolie language.

Pardon me if I ask it again. What are you waiting for getting yourself a Jolie?

Happy microservices :)