Scala Streams: A Deeper Look

To start, let’s take a look at the following code:

def process(xs: => Traversable[Int]) = xs.map(_ + 10).filter(_ % 3 == 0).map(_ * 2)

process function is just a chain of transformations on the given Traversable. Each of these transformations will create an intermediate traversable to be passed to the next transformation function. Given xs = Array(1, 2, 5), the manual tracing output would be:

1 is increased by 10 so transferred to 11
2 is increased by 10 so transferred to 12
5 is increased by 10 so transferred to 15
11 is filtered out because it is not a multiple of 3
12 is kept because it is a multiple of 3
15 is kept because it is a multiple of 3
12 is multiplied by 2 so transferred to 24
15 is multiplied by 2 so transferred to 30

In imperative programming style, this computation can be done “easily” with a while loop which transform each element of xs to the final desired value in one go. So no intermediate traversable will be created and this means less memory allocation. In this case, the manual tracing output would be:

1 is increased by 10 so transferred to 11
11 is filtered out because it is not a multiple of 3
2 is increased by 10 so transferred to 12
12 is kept because it is a multiple of 3
12 is multiplied by 2 so transferred to 24
5 is increased by 10 so transferred to 15
15 is kept because it is a multiple of 3
15 is multiplied by 2 so transferred to 30

How can we keep the compositional style (composing higher order functions like map, filter etc.) but without creating intermediate results to use memory more efficiently?

This can be achieved by using non-strict data structures. Non-strict (or lazy) data structures defer a computation until it is needed. In Scala, Stream is an implementation of non-strict sequence. Here is a simplified version of Stream implementation:

trait Stream[+A]
case class Cons[+A](head: A, tail: () => Stream[A]) extends Stream[A]
case object Empty extends Stream[Nothing]  

As seen above, the main difference between Stream and other strict sequences such as List is that the tail is a function instead of a strict value. So, tail is not being evaluated until it is forced. Let’s play with our Stream data structure to see how it works.

First, let’s create a convenient apply function

object Stream {
   def apply[A](xs: A*): Stream[A] = if (xs.isEmpty) Empty else Cons(xs.head, () => apply(xs.tail:_*))
}

Now let’s add a simple version of map and filter to our Stream trait.

trait Stream[+A] {
   def map[B](f: A => B): Stream[B] = this match {
      case Empty => Empty
      case Cons(h, t) => Cons(f(h), () => t().map(f))
   }

   def filter(f: A => Boolean): Stream[A] = this match {
      case Empty => Empty
      case Cons(h, t) =>
         if (f(h)) 
            Cons(h, () => t().filter(f)) 
         else 
            t().filter(f)
  }
}

Now, let’s partially trace our motivating example:

Stream(1, 2, 5).map(_ + 10).filter(_ % 3 == 0).map(_ * 2)

Upon the invocation of the first map, Stream(1, 2, 5) is matched with the second case (line 4) so Cons(11, function0) is created. function0 notation denotes on a function which if it is invoked, it calls map(_ + 10) on the tail of the original stream. Next, filter function is invoked on the result of the first step which was Cons(11, function0). So it is matched with the second case (line 9). Since 11 is not a multiple of 3, it should be filtered out so else branch is executed. Therefore, function0 is invoked to be evaluated. So we enter again in the map function and again we match to the second case (line 4) and Cons(12, function1) is created. Upon executing filter on this intermediate result, it is again matched to the second case (line 9) but this time, since 12 is a multiple of 3, it is not filtered out (line 11). So Cons(12, function2) is created. Now, map(_ * 2) will be executed on this intermediate result and so on so forth.

As you see:

  • Intermediate results are type of Stream which only has its head evaluated and the rest is not evaluated.
  • The order of the transformations is the same as while loop.

This is why sometimes streams are referred as first-class loops [1]. It seems that we should use this first-class loop instead of strict collections whenever we have a chain of transformations. Is it true?

To answer this question, I benchmarked Scala standard Stream against Array from both memory and throughput aspects. The benchmark source code can be found here.

For memory usage comparison, I implemented MemoryUsage application and monitored the memory usage of different approaches with VisualVM.

I increased the size of data to 50 million elements to make the result more visible in VisualVM. Here is the result:

Streaming vs Collection

As seen, applying the aforementioned chain of transformations on Array needs considerably bigger heap size. However, when the size of data is smaller, the differences is less tangible. But memory usage is just one side of the coin. What about throughput?

Stream data structure heavily uses memoizing. This means that functions that are passed to the constructor are cached in lazy vals to prevent being re-computed. Although lazy values have been designed exactly for this purpose, comparing to vals, they have worse performance. So we can expect that the throughput of stream transformations is less than arrays (or generally strict collections). To experiment this, I did a micro-benchmark using jmh and sbt-jmh. I chose Array and Stream with 10000 elements with the following benchmark setup:

sbt "run -i 5 -wi 5 -f1 -t1 \"StreamingBenchmark\""

And here is the result:

[info]
[info] # Run complete. Total time: 00:00:20
[info]
[info] Benchmark                             Mode  Cnt     Score     Error  Units
[info] StreamingBenchmark.streaming         thrpt    5   880.009 ±  75.244  ops/s
[info] StreamingBenchmark.strictProcessing  thrpt    5  4078.819 ± 276.049  ops/s

As seen, given the previously mentioned transformation chain, Stream throughput is around 4 times less than Array throughput.

Conclusion

Although Streams eliminate intermediate collections upon transformations, it has considerably less throughput comparing Array (of course Array is optimised for traversing but I also executed the benchmark against other strict data structures like Vector and List and in all cases Stream has worse performance but with different ratios). Stream and other non-strict data types are great data structures but they should be used when their characteristics are really needed.

[1]. Chiusano P. and Bjarnason R. (2015). Functional Programming in Scala by Manning

RabbitMQ Exchange Federation in Multiple AWS Availability Zones

Federation is one of the ways by which a software system can benefit from having multiple RabbitMQ brokers distributed on different machines. Clustering and shovel are two other ways to provide distributed brokers. Choosing between these approaches completely depends on your context and what you want to achieve. In this blog post, I am going to focus on exchange federation feature of RabbitMQ to achieve highly available messaging system spread in multiple AWS availability zones. Whether this is a right choice or not will be explained at the very end.

RabbitMQ provides two types of federation: exchange and queue. The focus here is the former. Imagine the goal is to have three RabbitMQ instances spread in three different AWS availability zones located in AWS Ireland region. So, if any of these availability zones has connectivity problem or temporarily goes down, the messaging system continues working. Let’s think about a scenario where there is a direct exchange to which different publishers can publish messages. So each message, based on its routing key, will be delivered to one or more queues. In the distributed brokers architecture, it should be possible that a message is published to an exchange on one node and be received on a bound queue on another node. The exchange federation makes this possible by defining other nodes as upstream of the current node. So if nodes ‘a’, ‘b’ and ‘c’ construct the RabbitMQ fleet, by using exchange federation, it is possible to define ‘b’ and ‘c’ as the upstream of node ‘a’. So any messages published to the RabbitMQ exchange located on ‘b’ and ‘c’, will be replicated on the corresponding exchange on node ‘a’.

I assume that you already setup your RabbitMQ instances on AWS and defined a load balancer in front of them. A good instruction to do that can be found here. If you want to achieve high availability, setting up a load balancer in front of the RabbitMQ instances is a good practice because it makes brokers distribution transparent from the message publishers.

Now it is time to setup the exchange federation between RabbitMQ nodes. Federation is a RabbitMQ plugin coming with the RabbitMQ distribution. For this experiment, I installed rabbitmq-server-3.3.4-1 on EC2 instances with Amazon Linux AMI.

The federation plugin is not enabled by default, so the first step is to enable it.

rabbitmq-plugins enable rabbitmq_federation

RabbitMQ server needs to be restarted after enabling federation plugin to make it take effect. Afterwards, the upstream links can be defined to form the federation topology. The federation topology can vary based on the purpose. It can be ring, fan-out, complete graph etc. More details about different federation topology can be found here. Since we want to achieve completely transparent highly available RabbitMQ fleet, complete graph federation topology should be set up. Imagine the RabbitMQ fleet consists of the following 3 instances:

  1. ip-172-30-5-106
  2. ip-172-30-4-187
  3. ip-172-30-3-13

Since the upstream links are one-directional, 6 upstream links are needed to form a complete graph between these nodes. In order to define nodes ‘b’ and ‘c’ as upstream nodes of node ‘a’, assuming that RabbitMQ is running on port 5672, two new federation upstream parameters should be defined on node ‘a’ as follows:

rabbitmqctl set_parameter federation-upstream upstreamB '{"uri":"amqp://ip-172-30-4-187:5672","max-hops":1}'

rabbitmqctl set_parameter federation-upstream upstreamC '{"uri":"amqp://ip-172-30-3-13:5672","max-hops":1}'

By executing above commands, two new parameters called upstreamB and upstreamC for the federation-upstream component will be defined, each of which defining the upstream URI with max-hops set to 1. By setting max-hops to 1, the downstream nodes cannot replicate the messages that they receive from upstream nodes on their own downstream nodes. In complete graph topology, max-hops should be set to 1; otherwise, nodes can receive back the messages that previously they themselves replicated on their downstream nodes. On the other hand, in the ring topology, assuming that there are N nodes, max-hops should be set to N-1 to let all nodes have all messages.

Note that, by defining upstreams, we let brokers connect to each other remotely. Since by default it is not possible to connect to a broker remotely via ‘guest’ user, the RabbitMQ configuration should be altered to open up the ‘guest’ user remote access. This can be achieved by setting loopback_users configuration item to []:

[{rabbit, [{loopback_users, []}]}]

Above approach to let RabbitMQ nodes access each other is safe if nodes are located in private subnets inside VPC. If nodes are accessible via internet, you need to use a more secure approach. For example you may need to configure specific RabbitMQ users with specific access rights.

The federation upstream parameters should be defined in node ‘b’ and ‘c’ in the same way as we have defined them in node ‘a’ to form the complete graph. After that, we should determine that we are interested in applying federation at the exchange level (and not at the queue level):

rabbitmqctl set_policy --apply-to exchanges federate-me "MyExchange" '{"federation-upstream-set":"all"}'

The above command defines a policy called “federate-me” which applies the federation on all the exchanges whose name is “MyExchange”. The name of exchanges can be a regular expression so it may include all the exchanges with the name that matches that regular expression. As you can see, the federation-upstream-set is set to ‘all’. This means that, we want to apply this policy to all upstream nodes that we have previously defined for the current node. You may also group the upstream nodes and define different policies for different groups by setting ‘federation-upstream-set’ parameter to that group.

Again, you need to execute the above set-policy command on all nodes. After that, the federation setup is complete. You can check the federation status using RabbitMQ command line tool as follows:

sudo rabbitmqctl eval 'rabbit_federation_status:status().'

Federation vs Clustering in Cloud Environments

Performance

As mentioned here, performance tests using PerfTest shows that the federation throughput is considerably lower than the clustering throughput. The reason is that, federation works at the higher abstraction level than clustering.

Reliability

RabbitMQ clustering does not tolerate network partitions well so it is recommended to be used in cases where brokers are connected via reliable LAN links. Whether the connections between AZs are reliable or not is debatable. Here it has been mentioned that clustering is fine where the brokers are distributed across multiple AZs. In my personal experience, in a production system running for 6 months having a RabbitMQ cluster of 3 nodes distributed in 3 AZs, we have observed once that the cluster is partitioned due to connection loss between AZs. If in the context of your application this level of unreliability is not acceptable, using federation is recommended. In case of using clustering, the monitoring system should immediately capture that the cluster is partitioned and recovery can be done automatically by re-joining the nodes to the cluster.

Setting Up

Setting up a federated RabbitMQ fleet is more complicated than a RabbitMQ cluster. Specifically upon scaling up, the existing nodes should be re-configured to have the newly added node as their new upstream node. This means that setting up an auto scaling group for a federated RabbitMQ fleet is not a trivial task.

Summary

Federation is a RabbitMQ plugin in order to setup distributed brokers. Generally, in reliable networks, clustering is preferred due to higher throughput and easier setup. Although connection links between AWS AZs are not as reliable as network connections inside a single AZ, by having appropriate monitoring system in-place, clustering is preferred over federation. But it should be mentioned that this still depends on your application context and the level of unreliability that your application can accept.