Rewriting LavinMQ's topic exchange: a journey to structured pattern matching

Topic exchanges are the workhorses of AMQP message routing, enabling sophisticated pub/sub patterns through wildcard matching.

In LavinMQ commit cbd8487, we rewrote our topic exchange implementation to fix inconsistencies we discovered with expanded testing, and adopted a structured pattern-matching approach. This rewrite didn’t just boost speed; it fixed core routing bugs and made the code much cleaner.

The approach

Our new implementation takes a completely different approach. Instead of modeling binding patterns through procedural logic, one step at a time, we now treat each part of the pattern as structured data with compositional semantics. This means that each part of the pattern knows how to match itself, and the pieces link together like a chain. The result is code that’s easier to understand, maintain, and verify for correctness.

Iterator-based routing key parsing

struct RkIterator
  getter value : Bytes

  def initialize(raw : Bytes)
    if first_dot = raw.index '.'.ord
      @value = raw[0, first_dot]
      @raw = raw[(first_dot + 1)..]? || Bytes.empty
    else
      @value = raw
      @raw = Bytes.empty
    end
  end

  def next : RkIterator?
    self.class.new(@raw) unless @raw.empty?
  end
end

Segment-based pattern matching

During this rewrite, we built the RkIterator to parse dot-delimited routing keys (separated by .) efficiently without allocating extra memory. Instead of splitting the entire key into an array (a list of segments, where each segment becomes a separate memory object), the RkIterator reads the key segment by segment, only when needed. This approach is much faster and uses memory more efficiently.

The core innovation is representing binding patterns as linked chains of segment matchers:

abstract class Segment
  abstract def match?(rk) : Bool
end

class HashSegment < Segment  # Matches #
class StarSegment < Segment  # Matches *
class StringSegment < Segment # Matches literal strings

As an example of a segment matcher, we have the StarSegment representing the * in an AMQP binding key.

The # wildcard tries matching the next segment at every possible position in the remaining routing key, exactly the “zero or more words” semantics required by AMQP.

StarSegment: exact-one matching

def match?(rk) : Bool
  if check = @next
    if n = rk.next
      check.match?(n)
    else
      false
    end
  else
    rk.next.nil?
  end
end

Conclusion: All systems go (100% compatible)

The rewrite of the Topic Exchange is a massive win for efficiency. While the underlying pattern matching is now more precise and stable, the best news is that everything continues to run exactly as before.

The update is 100% compatible: your existing client code and bindings still work seamlessly, but the system is now leaner and faster - eliminating memory waste and achieving optimal speed. LavinMQ remains your rock-solid foundation.