DelayedMessageStore: O(N²) insert causes broker startup to hang with large delayed-message backlogs

[84bot]

Summary

LavinMQ::AMQP::DelayedExchangeQueue::DelayedMessageStore::DelayedRequeuedStore#insert has quadratic (O(N²)) behavior, which caused a production cluster to get stuck in a start/restart loop with a large backlog of delayed messages (millions, via x-delay on a delayed-exchange queue).

Incident background

• Cluster (production) had ~4M messages when an OOM triggered a leader re-election.
• The newly elected leader got stuck during startup — no useful logs even at trace level.
• strace -f -c on the running process showed almost no syscall activity (mostly epoll_wait/clock_nanosleep), i.e. not I/O-bound.
• perf top on the pid showed:

  98.45% lavinmq [.] *LavinMQ::AMQP::DelayedExchangeQueue::DelayedMessageStore::DelayedRequeuedStore#insert<LavinMQ::SegmentPosition, Int64>:Nil
  

• Claude was asked to investigate assuming a large delayed-message backlog, and confirmed quadratic behavior by benchmarking the insert:
  • 100k inserts → 1.2s
  • 400k inserts → 18.8s (4× the messages, ~15× the time)
  • Extrapolated to 4M messages: ~30+ minutes just for this step.
  • Root cause: Deque#insert shifts up to half the deque element-by-element on every insert, so N random-delay inserts is O(N²).
• Confirmed in practice: 1.5M delayed messages alone was enough to stall a cluster restart.
• Workaround used to recover the cluster: used lmqrecover to identify the queue with the delayed messages (lmqrecover -D <file> -d -m show_sp surfaces the AMQPTable, including the x-delay header) and deleted that queue (with customer's permission), which allowed the broker to start.
• systemd's TimeoutStartSec (customer bootstrap sets TimeoutStopSec=600 for stop, but start timeout was still the default ~300s / whatever configured) was also killing the process mid-recovery, compounding the problem — the process needed more than the configured start timeout just to churn through the delayed store.

Proposed fix

Since the delayed message store only ever needs the minimum entry (peek min / pop min / time-to-next-expiration), a Deque is the wrong data structure for this. A binary min-heap would give O(log n) insert and O(1) peek, fixing both:

1. Slow/stuck startup when recovering a large delayed-message backlog.
2. Slow publishing into a large delayed queue at runtime (same O(N²) insert path is presumably hit during normal operation too, not just startup).

Alternative structures discussed: skip list or B-tree (potentially better if working set fits in CPU cache).

Troubleshooting guide (for future reference, added to this issue for visibility)

1. LavinMQ pinned at 1 core, 100% CPU, cluster/node stuck starting.
2. strace -f -p <pid> -c and iostat show no significant syscall/IO activity — process isn't stuck on I/O.
   • Trace-level logs can help but may show nothing (as in this case).
3. Run perf top -p <pid> to see where CPU time is actually spent.
4. If it points at the Delayed Store — need to identify which queue has the large delayed backlog.
5. du -h | sort -h under /var/lib/lavinmq/ to find the largest queue directories.
6. cat <largest queues>/.queue to inspect.
7. lmqrecover -D <file> -d -m show_sp to dump segment positions/headers, which will include the x-delay AMQPTable entry identifying the delayed queue.
8. If customer agrees, delete the offending queue to unblock startup.

[lukas8219]

I'll take this beauty

[lukas8219]

EDIT:

Some considerations after brainstorming a bit with Claude.

SkipList:

• Not good if we consider the allocations. Can be heavy for many objects.
• Good option if we want to be able to "delete" certain delayed messages in Mgmt UI in the future.

Heap (min-heap)

• Easiest one: Few lines of implementation. Least resource intensive
• Has no way to "manage" delayed messages.

Kafka/Netty (HashedWheelTimer)

• Bucketize per second. Many Dequeue structures.
• Almost a overhaul on the entire implementation. Has some "future-proofness" on it since other techs uses it.

[lukas8219]

Another option if we focus completely on the restart issue itself and not the O(N2) insert complexity. In this case exposing a bulk_insert that inserts stuff and runs a sort! right after the bulk could solve it w/o risking changing the internal structure itself