Major performance optimizations in mod_multicast

When I finished my Google Summer of Code 2007 project about implementing XEP-0033: Extended Stanza Addressing in ejabberd, I ran some benchmarking and found that my multicast module performed really bad.

It was explained in ejabberd gets XEP-0033: Extended Stanza Addressing. For example, CPU consumption was multiplied by x3 when users sent XEP33 packets to around 40 destinations.

This result was not surprising since my focus during the GSoC time was to implement XEP33 correctly, not efficiently. I added as a post-GSoC task to perform code profiling, find bottlenecks and deficiencies in mod_multicast, and improve the code accordingly.

Used tools

During September I've learned about several tools in Erlang/OTP to analyze Erlang source code. After experimenting with them in several of my ejabberd contributions, this weekend I decided it was time to come back to mod_multicast.

The tools I used for code profiling are:

• Debugger: graphical tool which can be used for debugging and testing of Erlang programs.
• Dialyzer: static analysis tool that identifies software discrepancies such as type errors, unreachable code, unnecessary tests.
• Cover: coverage analysis tool for Erlang. Shows how many times is executed each line of the source code file.
  
• Fprof: profiling tool that can be used to get a picture of how much processing time different functions consumes and in which processes.

For benchmarking, I used those tools:

• Timer:tc: Measure the elapsed real time while executing a function.
  
• Testsuite: to create a lot of Jabber accounts.
• ejabberd's mod_shared_roster: to populate the rosters with a lot of contacts.
  
• Jabsimul: stress the server sending constant presence changes.
  
• top: view ejabberd consumption of CPU and RAM.
  
• etop: similar to top, but to view Erlang processes.
  

Performance improvements

The part of mod_multicast packet processing that consumed more time was the traversal and formatting of the list of destination addresses. A task was specially time consuming in my early code: conversion of string to JID. And to make things worse, each destination address was converted from string to JID several times, for stupid reasons.

Yesterday I rewrote and reorganized a lot of the code that handles multicast packets. I'll now describe the important changes.

* Software engineering 101

Replace the do_route* control-passing functions with a main function 'route_untrusted' that has the control and calls worker functions.

* Erlang/OTP Programming with Style 101

Use Throw and Catch.

* Route_unstrusted

The function route_untrusted is used for any multicast packet that was sent from an untrusted source (local user, remote user, remote server, remote service). This packet is completely checked: access permissions, packet format, limit of number of destinations, packet relay.

* Route_trusted

The function route_trusted is used by local services like MUC and the session manager. Since the source of the packet is trusted by the multicast service, the packet is not checked.

* Route_common

The function route_common performs the main processing tasks: find a multicast service for each remote server (either in cache or start the query process), and send the packets.

* Packet prebuilding

There are two important improvements in the packets building task: the set of 'address' elements that represents each group of destinations is built initially, not for every packet sent. This is where the 'delivered=true' attribute is added.

Also for each group of destinations, they get a prebuilt packet which includes all the other addresses (with the 'delivered=true' attribute already present).

Finally, the list of groups is traversed, and for each one the only remaining duty is to build the final packet (by simply concatenating the list of addresses), and route to the destination.

This implementation has a complexity of order N, while the old implementation had complexity of order N^N.


Conclusions

I've described the nature of the performance improvements in mod_multicast. I'll soon describe how I ran the benchmarking tools, and the observed results.