UNDF: UNDF-2026-000000350

artemis-0001: BindingsImpl routeFromCluster O(R×A) → O(R+A)

Location

artemis-server/src/main/java/org/apache/activemq/artemis/core/postoffice/impl/BindingsImpl.java Lines 630–664 (routeFromCluster)

Severity

HIGH — called on every clustered message that requires selective ACK routing

Description

routeFromCluster decodes two byte arrays: ids (all binding IDs to route to) and idsToAck (subset that require ACK). It builds idsToAckList as an ArrayList<Long>, then iterates over ids calling idsToAckList.contains(bindingID) for each entry.

For R route targets and A ACK targets, this is O(R×A). Since this method is called on the hot message routing path in clustered deployments, it compounds per message.

Root Cause

private void routeFromCluster(final Message message, final RoutingContext context,
                               final byte[] ids) throws Exception {
    byte[] idsToAck = (byte[]) message.removeProperty(Message.HDR_ROUTE_TO_ACK_IDS);
    List<Long> idsToAckList = new ArrayList<>();          // ← ArrayList

    if (idsToAck != null) {
        ByteBuffer buff = ByteBuffer.wrap(idsToAck);
        while (buff.hasRemaining()) {
            idsToAckList.add(buff.getLong());             // populate O(A)
        }
    }

    ByteBuffer buff = ByteBuffer.wrap(ids);
    while (buff.hasRemaining()) {                         // O(R) loop
        long bindingID = buff.getLong();
        Binding binding = bindingsIdMap.get(bindingID);
        if (binding != null) {
            if (idsToAckList.contains(bindingID)) {      // O(A) scan → O(R×A) total
                binding.routeWithAck(message, context);
            } else {
                binding.route(message, context);
            }
        }
    }
}

Fix

Use a HashSet<Long> instead of ArrayList<Long> for idsToAckSet:

private void routeFromCluster(final Message message, final RoutingContext context,
                               final byte[] ids) throws Exception {
    byte[] idsToAck = (byte[]) message.removeProperty(Message.HDR_ROUTE_TO_ACK_IDS);
    Set<Long> idsToAckSet = new HashSet<>();              // ← HashSet

    if (idsToAck != null) {
        ByteBuffer buff = ByteBuffer.wrap(idsToAck);
        while (buff.hasRemaining()) {
            idsToAckSet.add(buff.getLong());              // populate O(A)
        }
    }

    ByteBuffer buff = ByteBuffer.wrap(ids);
    while (buff.hasRemaining()) {                         // O(R) loop
        long bindingID = buff.getLong();
        Binding binding = bindingsIdMap.get(bindingID);
        if (binding != null) {
            if (idsToAckSet.contains(bindingID)) {       // O(1) → O(R+A) total
                binding.routeWithAck(message, context);
            } else {
                binding.route(message, context);
            }
        }
    }
}

Complexity

	Before	After
routeFromCluster	O(R×A)	O(R+A)

Where R=routing targets, A=ACK targets. At R=100 bindings, A=50 ACKs: 5,000 ops per message → 150 ops (33x improvement). Under sustained load of 10,000 msg/s this saves ~49.8M operations/second.

Context

This is in the clustered message routing path — called when the broker receives a message with HDR_ROUTE_TO_ACK_IDS set, routing to multiple queues where some require acknowledgment. In large clustered deployments with many queues per address, R and A can be large.

3.4 KiB Raw Permalink Blame History Unescape Escape