[AMQ-7055] Small optimization on SequenceSet to prevent iterating through the whole set when a value bigger than the last value is added

• Type: Improvement
• Status: Resolved
• Priority: Minor
• Resolution: Fixed
• Affects Version/s: 5.15.6
• Fix Version/s: 5.15.7, 5.16.0
• Component/s: KahaDB
• Assignee: Gary Tully
• Reporter: Alan Protasio
• Created: 19/Sep/18 19:19
• Updated: 18/Oct/19 18:45
• Resolved: 20/Sep/18 09:42

Description

When the index file has a huge number of free pages and the broker is starting up (loading the index) we end up in a O(n2) loop.

This was causing the broker to use 100% cpu and not being able to start up even after a long time (as i remember we had around 3 millions free page in this case)

https://github.com/apache/activemq/blob/master/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/page/PageFile.java#L428

https://github.com/apache/activemq/blob/master/activemq-kahadb-store/src/main/java/org/apache/activemq/store/kahadb/disk/util/SequenceSet.java#L118

I noticed that almost all the free pages was being added to the end of the sequenceSet... So for any free page the broker had to necessity iterate through  all the Set (and after doing that for nothing add . the value to the tail).

With this small change, the broker started up in less than 5 minutes.

Issue Links

• links to: GitHub Pull Request #300
• links to: GitHub Pull Request #300