Review Board 1.7.22

QPID-3960 Performance regression in priority queue implementatino.

Review Request #4814 - Created April 19, 2012 and submitted

Alan Conway
gordon, kgiusti
Commit 1307582 introduced a serious regression in the performance of priority queues.

 QPID-3603: Keep acquired messages on queues for all queue types.

 Updated priority and lvq queues to keep acquired messages, and supply 
 them to browsers if requested. This is necessary so replicating
 subscriptions can back-up these queue types without message loss.

The commit replaced a o(1) algorithm for push() with an o(log(n)) algorithme, the result is increasingly bad performance as a queue gets longer.

To demonstrate the slowdown, run this on the broker before and after the commit:

qpid-send -a "test1;{create:always,node:{x-declare:{arguments:{'qpid.priorities':10}}}}" --priority 5 --content-size 259 -m 25000 --report-total

E.g. on my test I see 24112 m/s before and 4549 after. Note that if you repeatedly run the test the results get progressively worse, so it appears to be related to queue depth.

This patch uses the old multi-deque algorithm for push and consume, and adds a MessageDeque index for fast browsign. It appears to fix the performance problem but fails 2 tests, I'm hoping someone can spot my mistake.

Make check fails in 2 places:

../../../qpid/cpp/src/tests/cluster_test.cpp(1227): error in "testFairsharePriorityDelivery": check browse(c0, "q", 12) == browse(c1, "q"\
, 12) failed [msg-4 msg-6 msg-8 msg-10 msg-11 msg-12 msg-13 msg-14 msg-15 msg-16 msg-17 msg-18  != msg-4 msg-6 msg-8 msg-10 msg-12 msg-14 msg-16 msg-18 msg-9 msg-10 msg-12 msg-14 ]
FAIL: run_cluster_test ........ fail
Error during test:  Traceback (most recent call last):
    File "/home/aconway/qpidha/opt/src/tests/python/commands/qpid-python-test", line 340, in run
    File "/home/aconway/qpidha/qpid/tests/src/py/qpid_tests/broker_0_10/", line 276, in test_reroute_priority_queue
      self.assertEqual(result.status, 0)
    File "/usr/lib64/python2.6/", line 349, in failUnlessEqual
      (msg or '%r != %r' % (first, second))
  AssertionError: 7 != 0
FAIL: python_tests
Review request changed
Updated (April 20, 2012, 5:56 p.m.)
This one passes the full make check, it does cluster updates in FIFO order at both ends.
Ship it!
Posted (April 23, 2012, 1:50 p.m.)