You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pulsar.apache.org by lh...@apache.org on 2026/08/17 11:11:21 UTC

(pulsar) branch master updated: [fix][broker] Prevent Key_Shared out-of-order replay starvation at the end of topic (#26268)

This is an automated email from the ASF dual-hosted git repository.

lhotari pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/pulsar.git


The following commit(s) were added to refs/heads/master by this push:
     new bcdbdaaafc42 [fix][broker] Prevent Key_Shared out-of-order replay starvation at the end of topic (#26268)
bcdbdaaafc42 is described below

commit bcdbdaaafc427595f374965a5f7d5f00c2a5a35d
Author: sinan liu <li...@gmail.com>
AuthorDate: Mon Aug 17 19:11:13 2026 +0800

    [fix][broker] Prevent Key_Shared out-of-order replay starvation at the end of topic (#26268)
---
 .../persistent/MessageRedeliveryController.java    |  88 +++++++----
 ...istentStickyKeyDispatcherMultipleConsumers.java |  54 +++----
 ...tickyKeyDispatcherMultipleConsumersClassic.java |   6 +-
 .../MessageRedeliveryControllerTest.java           | 172 +++++++++------------
 ...ntStickyKeyDispatcherMultipleConsumersTest.java |  62 +++++++-
 5 files changed, 228 insertions(+), 154 deletions(-)

diff --git a/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/MessageRedeliveryController.java b/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/MessageRedeliveryController.java
index 46f1f0a53565..9e5ebcf38f43 100644
--- a/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/MessageRedeliveryController.java
+++ b/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/MessageRedeliveryController.java
@@ -19,6 +19,7 @@
 package org.apache.pulsar.broker.service.persistent;
 
 import static org.apache.pulsar.broker.service.StickyKeyConsumerSelector.STICKY_KEY_HASH_NOT_SET;
+import com.google.common.annotations.VisibleForTesting;
 import java.util.ArrayList;
 import java.util.List;
 import java.util.NavigableSet;
@@ -43,7 +44,11 @@ public class MessageRedeliveryController {
     private final boolean allowOutOfOrderDelivery;
     private final boolean isClassicDispatcher;
     private final ConcurrentBitmapSortedLongPairSet messagesToRedeliver;
-    private final ConcurrentLongLongPairHashMap hashesToBeBlocked;
+    // Not final: under out-of-order delivery, whether this map is ever needed isn't known at construction time. Only a
+    // Key_Shared dispatcher records hashes; a plain Shared dispatcher never does. The map is therefore allocated when
+    // add() first receives a real hash. Classic out-of-order returns before that allocation regardless of the hash.
+    private ConcurrentLongLongPairHashMap positionToStickyKeyHash;
+    // Final by contrast: this map is needed exactly when ordering is enforced, which is known at construction time.
     private final ConcurrentLongLongHashMap hashesRefCount;
 
     public MessageRedeliveryController(boolean allowOutOfOrderDelivery) {
@@ -55,16 +60,27 @@ public class MessageRedeliveryController {
         this.isClassicDispatcher = isClassicDispatcher;
         this.messagesToRedeliver = new ConcurrentBitmapSortedLongPairSet();
         if (!allowOutOfOrderDelivery) {
-            this.hashesToBeBlocked = ConcurrentLongLongPairHashMap
-                    .newBuilder().concurrencyLevel(2).expectedItems(128).autoShrink(true).build();
+            this.positionToStickyKeyHash = newPositionToStickyKeyHashMap();
             this.hashesRefCount = ConcurrentLongLongHashMap
                     .newBuilder().concurrencyLevel(2).expectedItems(128).autoShrink(true).build();
         } else {
-            this.hashesToBeBlocked = null;
+            this.positionToStickyKeyHash = null;
             this.hashesRefCount = null;
         }
     }
 
+    private static ConcurrentLongLongPairHashMap newPositionToStickyKeyHashMap() {
+        return ConcurrentLongLongPairHashMap.newBuilder()
+                .concurrencyLevel(2).expectedItems(128).autoShrink(true).build();
+    }
+
+    private ConcurrentLongLongPairHashMap ensurePositionToStickyKeyHashMap() {
+        if (positionToStickyKeyHash == null) {
+            positionToStickyKeyHash = newPositionToStickyKeyHashMap();
+        }
+        return positionToStickyKeyHash;
+    }
+
     public void add(long ledgerId, long entryId) {
         messagesToRedeliver.add(ledgerId, entryId);
     }
@@ -74,30 +90,38 @@ public class MessageRedeliveryController {
             if (!isClassicDispatcher && stickyKeyHash == STICKY_KEY_HASH_NOT_SET) {
                 throw new IllegalArgumentException("Sticky key hash is not set. It is required.");
             }
-            boolean inserted = hashesToBeBlocked.putIfAbsent(ledgerId, entryId, stickyKeyHash, 0);
-            if (!inserted) {
-                hashesToBeBlocked.put(ledgerId, entryId, stickyKeyHash, 0);
-            } else {
-                // Return -1 means the key was not present
-                long stored = hashesRefCount.get(stickyKeyHash);
-                hashesRefCount.put(stickyKeyHash, stored > 0 ? ++stored : 1);
-            }
+        } else if (isClassicDispatcher || stickyKeyHash == STICKY_KEY_HASH_NOT_SET) {
+            // Classic out-of-order dispatchers never read position hashes. Non-classic dispatchers normalize real
+            // sticky-key hashes away from the sentinel, so the sentinel denotes a replay position without a known hash.
+            messagesToRedeliver.add(ledgerId, entryId);
+            return;
+        }
+        ConcurrentLongLongPairHashMap positionToStickyKeyHash = ensurePositionToStickyKeyHashMap();
+        boolean inserted = positionToStickyKeyHash.putIfAbsent(ledgerId, entryId, stickyKeyHash, 0);
+        if (!inserted) {
+            positionToStickyKeyHash.put(ledgerId, entryId, stickyKeyHash, 0);
+        } else if (!allowOutOfOrderDelivery) {
+            // Return -1 means the key was not present
+            long stored = hashesRefCount.get(stickyKeyHash);
+            hashesRefCount.put(stickyKeyHash, stored > 0 ? ++stored : 1);
         }
         messagesToRedeliver.add(ledgerId, entryId);
     }
 
     public void remove(long ledgerId, long entryId) {
-        if (!allowOutOfOrderDelivery) {
-            removeFromHashBlocker(ledgerId, entryId);
-        }
+        removeFromStickyKeyHash(ledgerId, entryId);
         messagesToRedeliver.remove(ledgerId, entryId);
     }
 
-    private void removeFromHashBlocker(long ledgerId, long entryId) {
-        LongPair value = hashesToBeBlocked.get(ledgerId, entryId);
+    private void removeFromStickyKeyHash(long ledgerId, long entryId) {
+        ConcurrentLongLongPairHashMap positionToStickyKeyHash = this.positionToStickyKeyHash;
+        if (positionToStickyKeyHash == null) {
+            return;
+        }
+        LongPair value = positionToStickyKeyHash.get(ledgerId, entryId);
         if (value != null) {
-            boolean removed = hashesToBeBlocked.remove(ledgerId, entryId, value.first, 0);
-            if (removed) {
+            boolean removed = positionToStickyKeyHash.remove(ledgerId, entryId, value.first, 0);
+            if (removed && !allowOutOfOrderDelivery) {
                 long exists = hashesRefCount.get(value.first);
                 if (exists == 1) {
                     hashesRefCount.remove(value.first, exists);
@@ -109,7 +133,11 @@ public class MessageRedeliveryController {
     }
 
     public Long getHash(long ledgerId, long entryId) {
-        LongPair value = hashesToBeBlocked.get(ledgerId, entryId);
+        ConcurrentLongLongPairHashMap positionToStickyKeyHash = this.positionToStickyKeyHash;
+        if (positionToStickyKeyHash == null) {
+            return null;
+        }
+        LongPair value = positionToStickyKeyHash.get(ledgerId, entryId);
         if (value == null) {
             return null;
         }
@@ -118,17 +146,18 @@ public class MessageRedeliveryController {
 
     public void removeAllUpTo(long markDeleteLedgerId, long markDeleteEntryId) {
         boolean bitsCleared = messagesToRedeliver.removeUpTo(markDeleteLedgerId, markDeleteEntryId + 1);
-        // only if bits have been clear, and we are not allowing out of order delivery, we need to remove the hashes
-        // removing hashes is a relatively expensive operation, so we should only do it when necessary
-        if (bitsCleared && !allowOutOfOrderDelivery) {
+        // Only remove the hashes when bits have been cleared. Removing hashes is a relatively expensive operation,
+        // so we should only do it when necessary.
+        ConcurrentLongLongPairHashMap positionToStickyKeyHash = this.positionToStickyKeyHash;
+        if (bitsCleared && positionToStickyKeyHash != null && !positionToStickyKeyHash.isEmpty()) {
             List<LongPair> keysToRemove = new ArrayList<>();
-            hashesToBeBlocked.forEach((ledgerId, entryId, stickyKeyHash, none) -> {
+            positionToStickyKeyHash.forEach((ledgerId, entryId, stickyKeyHash, none) -> {
                 if (ledgerId < markDeleteLedgerId || (ledgerId == markDeleteLedgerId && entryId <= markDeleteEntryId)) {
                     keysToRemove.add(new LongPair(ledgerId, entryId));
                 }
             });
             for (LongPair longPair : keysToRemove) {
-                removeFromHashBlocker(longPair.first, longPair.second);
+                removeFromStickyKeyHash(longPair.first, longPair.second);
             }
         }
     }
@@ -138,8 +167,10 @@ public class MessageRedeliveryController {
     }
 
     public void clear() {
+        if (positionToStickyKeyHash != null) {
+            positionToStickyKeyHash.clear();
+        }
         if (!allowOutOfOrderDelivery) {
-            hashesToBeBlocked.clear();
             hashesRefCount.clear();
         }
         messagesToRedeliver.clear();
@@ -197,4 +228,9 @@ public class MessageRedeliveryController {
     public int size() {
         return messagesToRedeliver.size();
     }
+
+    @VisibleForTesting
+    boolean isPositionToStickyKeyHashInitialized() {
+        return positionToStickyKeyHash != null;
+    }
 }
diff --git a/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumers.java b/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumers.java
index 07177e039b11..9a876220ec4b 100644
--- a/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumers.java
+++ b/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumers.java
@@ -358,28 +358,23 @@ public class PersistentStickyKeyDispatcherMultipleConsumers extends PersistentDi
         acquirePermitsForDeliveredMessages(topic, cursor, totalEntries, totalMessagesSent, totalBytesSent);
 
         // trigger read more messages if necessary
-        if (triggerLookAhead.booleanValue() && (allowOutOfOrderDelivery || cursor.hasMoreEntries())) {
+        if (triggerLookAhead.booleanValue() && cursor.hasMoreEntries()) {
             // When all messages get filtered and no messages are sent, we should read more entries, "look ahead"
             // so that a possible next batch of messages might contain messages that can be dispatched.
             // This is done only when there's a consumer with available permits, and it's not able to make progress
             // because of blocked hashes. Without this rule we would be looking ahead in the stream while the
             // new consumers are not ready to accept the new messages,
             // therefore would be most likely only increase the distance between read-position and mark-delete position.
-            // When ordered delivery is required, look-ahead is engaged only when the cursor has more entries.
-            // Otherwise the next readMoreEntries call would skip replaying the replay queue and pulling due messages
-            // from the delayed delivery tracker, and instead issue a normal read that waits at the end of the topic
-            // for new entries. That would leave deliverable messages stuck in the replay queue or the delayed
-            // delivery tracker until an unrelated event (such as a consumer flow request) triggers another read,
-            // stalling dispatch (issue #21554).
-            // When out-of-order delivery is allowed, look-ahead is engaged unconditionally, as before. In that mode
-            // the replay queue doesn't track sticky key hashes, so the replay position filter cannot exclude
-            // messages for consumers without available permits, and each replay would re-read and discard the same
-            // undispatchable messages. Ending the cycle with a look-ahead attempt (that waits at the end of the
-            // topic when there is nothing to read) prevents such repeated read-and-discard loops.
+            // Look-ahead is engaged only when the cursor has more entries. Otherwise the next readMoreEntries call
+            // would skip replaying the replay queue and pulling due messages from the delayed delivery tracker, and
+            // instead issue a normal read that waits at the end of the topic for new entries. That would leave
+            // deliverable messages stuck in the replay queue or the delayed delivery tracker until an unrelated event
+            // (such as a consumer flow request) triggers another read, stalling dispatch (issue #21554).
+            // The former "allowOutOfOrderDelivery ||" escape here was dropped once ReplayPositionFilter started
+            // filtering out-of-order replay positions by available permits; don't re-add it without removing that.
             skipNextReplayToTriggerLookAhead = true;
             // skip backoff delay before reading ahead in the "look ahead" mode to prevent any additional latency
-            // only skip the delay if there are more entries to read
-            skipNextBackoff = cursor.hasMoreEntries();
+            skipNextBackoff = true;
             return true;
         }
 
@@ -629,19 +624,20 @@ public class PersistentStickyKeyDispatcherMultipleConsumers extends PersistentDi
         private final Map<Consumer, MutableInt> availablePermitsMap = new HashMap<>();
         // tracks the hashes that have been blocked during the filtering
         // it is necessary to block all later messages after a hash gets blocked so that ordering is preserved
-        private final Set<Long> alreadyBlockedHashes = new HashSet<>();
+        private final Set<Long> hashesBlockedForOrdering = new HashSet<>();
 
         @Override
         public boolean test(Position position) {
-            // if out of order delivery is allowed, then any position will be replayed
-            if (isAllowOutOfOrderDelivery()) {
-                return true;
-            }
-            // lookup the sticky key hash for the entry at the replay position
+            // Out-of-order delivery relaxes ordering, not routing: filterAndGroupEntriesForDispatching selects the
+            // owning consumer by hash in both modes, so the hash is needed in both. It feeds the permit check below,
+            // which keeps this read's bounded budget (see MessageRedeliveryController#getMessagesToReplayNow) off
+            // positions that dispatch would only push straight back into the replay queue. Under out-of-order delivery,
+            // that check and the no-consumer check are the only live rejections here, and they made the
+            // "allowOutOfOrderDelivery ||" look-ahead escape removable.
             Long stickyKeyHash = redeliveryMessages.getHash(position.getLedgerId(), position.getEntryId());
             if (stickyKeyHash == null) {
-                // the sticky key hash is missing for delayed messages, the filtering will happen at the time of
-                // dispatch after reading the entry from the ledger
+                // The sticky key hash is missing for delayed messages and positions added through hash-less
+                // redelivery paths. Filtering will happen at dispatch time after reading the entry from the ledger.
                 log.debug()
                         .attr("position", position)
                         .log("replay of entry at position doesn't contain sticky key hash.");
@@ -649,7 +645,7 @@ public class PersistentStickyKeyDispatcherMultipleConsumers extends PersistentDi
             }
             // check if the hash is already blocked, if so, then replaying of the position should be skipped
             // to preserve ordering
-            if (alreadyBlockedHashes.contains(stickyKeyHash)) {
+            if (hashesBlockedForOrdering.contains(stickyKeyHash)) {
                 return false;
             }
 
@@ -657,7 +653,7 @@ public class PersistentStickyKeyDispatcherMultipleConsumers extends PersistentDi
             Consumer consumer = selector.select(stickyKeyHash.intValue());
             // skip replaying the message position if there's no assigned consumer
             if (consumer == null) {
-                alreadyBlockedHashes.add(stickyKeyHash);
+                blockStickyKeyHashIfOrderingRequired(stickyKeyHash);
                 return false;
             }
 
@@ -667,19 +663,25 @@ public class PersistentStickyKeyDispatcherMultipleConsumers extends PersistentDi
                             k -> new MutableInt(getAvailablePermits(consumer)));
             // skip replaying the message position if the consumer has no available permits
             if (availablePermits.intValue() <= 0) {
-                alreadyBlockedHashes.add(stickyKeyHash);
+                blockStickyKeyHashIfOrderingRequired(stickyKeyHash);
                 return false;
             }
 
             if (shouldBlockDispatch(consumer, stickyKeyHash.intValue())) {
                 // the hash is draining and the consumer is not the draining consumer
-                alreadyBlockedHashes.add(stickyKeyHash);
+                blockStickyKeyHashIfOrderingRequired(stickyKeyHash);
                 return false;
             }
 
             availablePermits.decrement();
             return true;
         }
+
+        private void blockStickyKeyHashIfOrderingRequired(long stickyKeyHash) {
+            if (!allowOutOfOrderDelivery) {
+                hashesBlockedForOrdering.add(stickyKeyHash);
+            }
+        }
     }
 
     @Override
diff --git a/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumersClassic.java b/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumersClassic.java
index f7b614d60af3..624c03964180 100644
--- a/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumersClassic.java
+++ b/pulsar-broker/src/main/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumersClassic.java
@@ -554,8 +554,7 @@ public class PersistentStickyKeyDispatcherMultipleConsumersClassic
 
     @Override
     protected synchronized NavigableSet<Position> filterOutEntriesWillBeDiscarded(NavigableSet<Position> src) {
-        // The variable "hashesToBeBlocked" and "recentlyJoinedConsumers" will be null if "isAllowOutOfOrderDelivery()",
-        // So skip this filter out.
+        // Keep the classic out-of-order behavior: replay positions are not filtered before reading.
         if (isAllowOutOfOrderDelivery()) {
             return src;
         }
@@ -603,8 +602,7 @@ public class PersistentStickyKeyDispatcherMultipleConsumersClassic
      */
     @Override
     protected boolean hasConsumersNeededNormalRead() {
-        // The variable "hashesToBeBlocked" and "recentlyJoinedConsumers" will be null if "isAllowOutOfOrderDelivery()",
-        // So the method "filterOutEntriesWillBeDiscarded" will filter out nothing, just return "true" here.
+        // Classic out-of-order replay filtering is bypassed, so normal reads do not need the ordered-mode escape check.
         if (isAllowOutOfOrderDelivery()) {
             return true;
         }
diff --git a/pulsar-broker/src/test/java/org/apache/pulsar/broker/service/persistent/MessageRedeliveryControllerTest.java b/pulsar-broker/src/test/java/org/apache/pulsar/broker/service/persistent/MessageRedeliveryControllerTest.java
index bc73ba64d500..03c7e6cf439e 100644
--- a/pulsar-broker/src/test/java/org/apache/pulsar/broker/service/persistent/MessageRedeliveryControllerTest.java
+++ b/pulsar-broker/src/test/java/org/apache/pulsar/broker/service/persistent/MessageRedeliveryControllerTest.java
@@ -18,20 +18,16 @@
  */
 package org.apache.pulsar.broker.service.persistent;
 
+import static org.apache.pulsar.broker.service.StickyKeyConsumerSelector.STICKY_KEY_HASH_NOT_SET;
 import static org.testng.Assert.assertEquals;
 import static org.testng.Assert.assertEqualsNoOrder;
 import static org.testng.Assert.assertFalse;
-import static org.testng.Assert.assertNotNull;
 import static org.testng.Assert.assertNull;
 import static org.testng.Assert.assertTrue;
-import java.lang.reflect.Field;
 import java.util.Set;
 import java.util.TreeSet;
 import org.apache.bookkeeper.mledger.Position;
 import org.apache.bookkeeper.mledger.PositionFactory;
-import org.apache.bookkeeper.util.collections.ConcurrentLongLongHashMap;
-import org.apache.pulsar.common.util.collections.ConcurrentLongLongPairHashMap;
-import org.apache.pulsar.utils.ConcurrentBitmapSortedLongPairSet;
 import org.testng.annotations.DataProvider;
 import org.testng.annotations.Test;
 
@@ -43,103 +39,61 @@ public class MessageRedeliveryControllerTest {
     }
 
     @Test(dataProvider = "allowOutOfOrderDelivery", timeOut = 10000)
-    public void testAddAndRemove(boolean allowOutOfOrderDelivery) throws Exception {
+    public void testAddAndRemove(boolean allowOutOfOrderDelivery) {
         MessageRedeliveryController controller = new MessageRedeliveryController(allowOutOfOrderDelivery);
 
-        Field messagesToRedeliverField = MessageRedeliveryController.class.getDeclaredField("messagesToRedeliver");
-        messagesToRedeliverField.setAccessible(true);
-        ConcurrentBitmapSortedLongPairSet messagesToRedeliver =
-                (ConcurrentBitmapSortedLongPairSet) messagesToRedeliverField.get(controller);
-
-        Field hashesToBeBlockedField = MessageRedeliveryController.class.getDeclaredField("hashesToBeBlocked");
-        hashesToBeBlockedField.setAccessible(true);
-        ConcurrentLongLongPairHashMap hashesToBeBlocked = (ConcurrentLongLongPairHashMap) hashesToBeBlockedField
-                .get(controller);
-
-        Field hashesRefCountField = MessageRedeliveryController.class.getDeclaredField("hashesRefCount");
-        hashesRefCountField.setAccessible(true);
-        ConcurrentLongLongHashMap hashesRefCount = (ConcurrentLongLongHashMap) hashesRefCountField.get(controller);
-
-        if (allowOutOfOrderDelivery) {
-            assertNull(hashesToBeBlocked);
-            assertNull(hashesRefCount);
-        } else {
-            assertNotNull(hashesToBeBlocked);
-            assertNotNull(hashesRefCount);
-        }
-
+        assertEquals(controller.isPositionToStickyKeyHashInitialized(), !allowOutOfOrderDelivery);
         assertTrue(controller.isEmpty());
-        assertEquals(messagesToRedeliver.size(), 0);
-        if (!allowOutOfOrderDelivery) {
-            assertEquals(hashesToBeBlocked.size(), 0);
-            assertEquals(hashesRefCount.size(), 0);
-        }
+        assertEquals(controller.size(), 0);
 
         controller.add(1, 1);
         controller.add(1, 2);
 
         assertFalse(controller.isEmpty());
-        assertEquals(messagesToRedeliver.size(), 2);
-        assertTrue(messagesToRedeliver.contains(1, 1));
-        assertTrue(messagesToRedeliver.contains(1, 2));
-        if (!allowOutOfOrderDelivery) {
-            assertEquals(hashesToBeBlocked.size(), 0);
-            assertFalse(hashesToBeBlocked.containsKey(1, 1));
-            assertFalse(hashesToBeBlocked.containsKey(1, 2));
-            assertEquals(hashesRefCount.size(), 0);
-        }
+        assertEquals(controller.size(), 2);
+        assertNull(controller.getHash(1, 1));
+        assertNull(controller.getHash(1, 2));
+        assertEquals(controller.isPositionToStickyKeyHashInitialized(), !allowOutOfOrderDelivery);
 
         controller.remove(1, 1);
         controller.remove(1, 2);
 
         assertTrue(controller.isEmpty());
-        assertEquals(messagesToRedeliver.size(), 0);
-        assertFalse(messagesToRedeliver.contains(1, 1));
-        assertFalse(messagesToRedeliver.contains(1, 2));
-        if (!allowOutOfOrderDelivery) {
-            assertEquals(hashesToBeBlocked.size(), 0);
-            assertEquals(hashesRefCount.size(), 0);
-        }
+        assertEquals(controller.size(), 0);
 
         controller.add(2, 1, 100);
         controller.add(2, 2, 101);
         controller.add(2, 3, 101);
 
         assertFalse(controller.isEmpty());
-        assertEquals(messagesToRedeliver.size(), 3);
-        assertTrue(messagesToRedeliver.contains(2, 1));
-        assertTrue(messagesToRedeliver.contains(2, 2));
-        assertTrue(messagesToRedeliver.contains(2, 3));
+        assertEquals(controller.size(), 3);
+        assertTrue(controller.isPositionToStickyKeyHashInitialized());
+        assertEquals(controller.getHash(2, 1), Long.valueOf(100));
+        assertEquals(controller.getHash(2, 2), Long.valueOf(101));
+        assertEquals(controller.getHash(2, 3), Long.valueOf(101));
         if (!allowOutOfOrderDelivery) {
-            assertEquals(hashesToBeBlocked.size(), 3);
-            assertEquals(hashesToBeBlocked.get(2, 1).first, 100);
-            assertEquals(hashesToBeBlocked.get(2, 2).first, 101);
-            assertEquals(hashesToBeBlocked.get(2, 3).first, 101);
-            assertEquals(hashesRefCount.size(), 2);
-            assertEquals(hashesRefCount.get(100), 1);
-            assertEquals(hashesRefCount.get(101), 2);
+            assertTrue(controller.containsStickyKeyHash(100));
+            assertTrue(controller.containsStickyKeyHash(101));
         }
 
         controller.remove(2, 1);
         controller.remove(2, 2);
 
+        assertEquals(controller.size(), 1);
+        assertNull(controller.getHash(2, 1));
+        assertNull(controller.getHash(2, 2));
+        assertEquals(controller.getHash(2, 3), Long.valueOf(101));
         if (!allowOutOfOrderDelivery) {
-            assertEquals(hashesToBeBlocked.size(), 1);
-            assertEquals(hashesToBeBlocked.get(2, 3).first, 101);
-            assertEquals(hashesRefCount.size(), 1);
-            assertEquals(hashesRefCount.get(100), -1);
-            assertEquals(hashesRefCount.get(101), 1);
+            assertFalse(controller.containsStickyKeyHash(100));
+            assertTrue(controller.containsStickyKeyHash(101));
         }
 
         controller.clear();
         assertTrue(controller.isEmpty());
-        assertEquals(messagesToRedeliver.size(), 0);
-        assertTrue(messagesToRedeliver.isEmpty());
+        assertEquals(controller.size(), 0);
+        assertNull(controller.getHash(2, 3));
         if (!allowOutOfOrderDelivery) {
-            assertEquals(hashesToBeBlocked.size(), 0);
-            assertTrue(hashesToBeBlocked.isEmpty());
-            assertEquals(hashesRefCount.size(), 0);
-            assertTrue(hashesRefCount.isEmpty());
+            assertFalse(controller.containsStickyKeyHash(101));
         }
 
         controller.add(2, 2, 201);
@@ -151,43 +105,71 @@ public class MessageRedeliveryControllerTest {
         controller.add(1, 1, 100);
 
         controller.removeAllUpTo(1, 3);
-        assertEquals(messagesToRedeliver.size(), 4);
-        assertTrue(messagesToRedeliver.contains(2, 1));
-        assertTrue(messagesToRedeliver.contains(2, 2));
-        assertTrue(messagesToRedeliver.contains(3, 1));
-        assertTrue(messagesToRedeliver.contains(3, 2));
+        assertEquals(controller.size(), 4);
+        assertNull(controller.getHash(1, 1));
+        assertNull(controller.getHash(1, 2));
+        assertNull(controller.getHash(1, 3));
+        assertEquals(controller.getHash(2, 1), Long.valueOf(200));
+        assertEquals(controller.getHash(2, 2), Long.valueOf(201));
+        assertEquals(controller.getHash(3, 1), Long.valueOf(300));
+        assertEquals(controller.getHash(3, 2), Long.valueOf(301));
         if (!allowOutOfOrderDelivery) {
-            assertEquals(hashesToBeBlocked.size(), 4);
-            assertEquals(hashesToBeBlocked.get(2, 1).first, 200);
-            assertEquals(hashesToBeBlocked.get(2, 2).first, 201);
-            assertEquals(hashesToBeBlocked.get(3, 1).first, 300);
-            assertEquals(hashesToBeBlocked.get(3, 2).first, 301);
-            assertEquals(hashesRefCount.size(), 4);
-            assertEquals(hashesRefCount.get(200), 1);
-            assertEquals(hashesRefCount.get(201), 1);
-            assertEquals(hashesRefCount.get(300), 1);
-            assertEquals(hashesRefCount.get(301), 1);
+            assertFalse(controller.containsStickyKeyHash(100));
+            assertFalse(controller.containsStickyKeyHash(101));
+            assertTrue(controller.containsStickyKeyHash(200));
+            assertTrue(controller.containsStickyKeyHash(201));
+            assertTrue(controller.containsStickyKeyHash(300));
+            assertTrue(controller.containsStickyKeyHash(301));
         }
 
         controller.removeAllUpTo(3, 1);
-        assertEquals(messagesToRedeliver.size(), 1);
-        assertTrue(messagesToRedeliver.contains(3, 2));
+        assertEquals(controller.size(), 1);
+        assertNull(controller.getHash(2, 1));
+        assertNull(controller.getHash(2, 2));
+        assertNull(controller.getHash(3, 1));
+        assertEquals(controller.getHash(3, 2), Long.valueOf(301));
         if (!allowOutOfOrderDelivery) {
-            assertEquals(hashesToBeBlocked.size(), 1);
-            assertEquals(hashesToBeBlocked.get(3, 2).first, 301);
-            assertEquals(hashesRefCount.size(), 1);
-            assertEquals(hashesRefCount.get(301), 1);
+            assertFalse(controller.containsStickyKeyHash(200));
+            assertFalse(controller.containsStickyKeyHash(201));
+            assertFalse(controller.containsStickyKeyHash(300));
+            assertTrue(controller.containsStickyKeyHash(301));
         }
 
         controller.removeAllUpTo(5, 10);
         assertTrue(controller.isEmpty());
-        assertEquals(messagesToRedeliver.size(), 0);
+        assertEquals(controller.size(), 0);
+        assertNull(controller.getHash(3, 2));
         if (!allowOutOfOrderDelivery) {
-            assertEquals(hashesToBeBlocked.size(), 0);
-            assertEquals(hashesRefCount.size(), 0);
+            assertFalse(controller.containsStickyKeyHash(301));
         }
     }
 
+    @Test(timeOut = 10000)
+    public void testOutOfOrderSentinelHashDoesNotInitializePositionHashMap() {
+        MessageRedeliveryController controller = new MessageRedeliveryController(true);
+
+        controller.add(1, 1, STICKY_KEY_HASH_NOT_SET);
+
+        assertFalse(controller.isPositionToStickyKeyHashInitialized());
+        assertEquals(controller.size(), 1);
+        assertNull(controller.getHash(1, 1));
+
+        controller.removeAllUpTo(1, 1);
+        assertTrue(controller.isEmpty());
+        assertFalse(controller.isPositionToStickyKeyHashInitialized());
+    }
+
+    @Test(timeOut = 10000)
+    public void testClassicOutOfOrderDoesNotInitializePositionHashMap() {
+        MessageRedeliveryController controller = new MessageRedeliveryController(true, true);
+
+        controller.add(1, 1, 100);
+
+        assertFalse(controller.isPositionToStickyKeyHashInitialized());
+        assertEquals(controller.size(), 1);
+        assertNull(controller.getHash(1, 1));
+    }
+
     @Test(dataProvider = "allowOutOfOrderDelivery", timeOut = 10000)
     public void testContainsStickyKeyHashes(boolean allowOutOfOrderDelivery) throws Exception {
         MessageRedeliveryController controller = new MessageRedeliveryController(allowOutOfOrderDelivery);
diff --git a/pulsar-broker/src/test/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumersTest.java b/pulsar-broker/src/test/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumersTest.java
index 732537c7b2d1..12fcca9fbe1b 100644
--- a/pulsar-broker/src/test/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumersTest.java
+++ b/pulsar-broker/src/test/java/org/apache/pulsar/broker/service/persistent/PersistentStickyKeyDispatcherMultipleConsumersTest.java
@@ -479,6 +479,11 @@ public class PersistentStickyKeyDispatcherMultipleConsumersTest {
         allEntries.forEach(Entry::release);
     }
 
+    @DataProvider(name = "allowOutOfOrderDelivery")
+    private Object[][] allowOutOfOrderDelivery() {
+        return new Object[][] { { false }, { true } };
+    }
+
     /**
      * Reproduces the dispatch stall behind the flaky
      * KeySharedSubscriptionTest.testContinueDispatchMessagesWhenMessageDelayed (issue #21554).
@@ -489,14 +494,15 @@ public class PersistentStickyKeyDispatcherMultipleConsumersTest {
      * in the replay queue for consumers with available permits were then stuck until an unrelated event, such as a
      * consumer flow request, triggered another read.
      */
-    @Test(timeOut = 30000)
-    public void testLookAheadNotEngagedWhenCursorHasNoMoreEntries() throws Exception {
+    @Test(dataProvider = "allowOutOfOrderDelivery", timeOut = 30000)
+    public void testLookAheadNotEngagedWhenCursorHasNoMoreEntries(boolean allowOutOfOrderDelivery) throws Exception {
         persistentDispatcher.close();
 
         // the mocked executor doesn't support schedule(), so run the rescheduled read directly
         persistentDispatcher = new PersistentStickyKeyDispatcherMultipleConsumers(
                 topicMock, cursorMock, subscriptionMock, configMock,
-                new KeySharedMeta().setKeySharedMode(KeySharedMode.AUTO_SPLIT)) {
+                new KeySharedMeta().setKeySharedMode(KeySharedMode.AUTO_SPLIT)
+                        .setAllowOutOfOrderDelivery(allowOutOfOrderDelivery)) {
             @Override
             protected void reScheduleReadInMs(long readAfterMs) {
                 orderedExecutor.execute(this::readMoreEntries);
@@ -578,6 +584,56 @@ public class PersistentStickyKeyDispatcherMultipleConsumersTest {
         allEntries.forEach(Entry::release);
     }
 
+    @Test(timeOut = 10000)
+    public void testOutOfOrderReplayFilterDoesNotSpendReadBudgetOnConsumerWithoutPermits() {
+        persistentDispatcher.close();
+        persistentDispatcher = new PersistentStickyKeyDispatcherMultipleConsumers(
+                topicMock, cursorMock, subscriptionMock, configMock,
+                new KeySharedMeta().setKeySharedMode(KeySharedMode.AUTO_SPLIT)
+                        .setAllowOutOfOrderDelivery(true));
+
+        persistentDispatcher.addConsumer(consumerMock).join();
+
+        Consumer slowConsumer = createMockConsumer();
+        doReturn("consumer2").when(slowConsumer).consumerName();
+        doReturn(0).when(slowConsumer).getAvailablePermits();
+        persistentDispatcher.addConsumer(slowConsumer).join();
+
+        StickyKeyConsumerSelector selector = persistentDispatcher.getSelector();
+        String keyForConsumer = generateKeyForConsumer(selector, consumerMock);
+        String keyForSlowConsumer = generateKeyForConsumer(selector, slowConsumer);
+        Entry entry1 = createEntry(1, 1, "message1", 1, keyForSlowConsumer);
+        Entry entry2 = createEntry(1, 2, "message2", 2, keyForSlowConsumer);
+        Entry entry3 = createEntry(1, 3, "message3", 3, keyForConsumer);
+        List<Entry> entries = List.of(entry1, entry2, entry3);
+
+        try {
+            for (Entry entry : entries) {
+                ((EntryImpl) entry).retain();
+                persistentDispatcher.addEntryToReplay(entry);
+            }
+
+            Set<Position> positions = persistentDispatcher.getMessagesToReplayNow(1, Long.MAX_VALUE);
+            assertThat(positions).containsExactly(entry3.getPosition());
+        } finally {
+            entries.forEach(Entry::release);
+        }
+    }
+
+    @Test(timeOut = 10000)
+    public void testOutOfOrderReplayFilterIncludesPositionWithoutStickyKeyHash() {
+        persistentDispatcher.close();
+        persistentDispatcher = new PersistentStickyKeyDispatcherMultipleConsumers(
+                topicMock, cursorMock, subscriptionMock, configMock,
+                new KeySharedMeta().setKeySharedMode(KeySharedMode.AUTO_SPLIT)
+                        .setAllowOutOfOrderDelivery(true));
+
+        assertTrue(persistentDispatcher.addMessageToReplay(1, 1));
+
+        Set<Position> positions = persistentDispatcher.getMessagesToReplayNow(1, Long.MAX_VALUE);
+        assertThat(positions).containsExactly(PositionFactory.create(1, 1));
+    }
+
     @Test(timeOut = 30000)
     public void testMessageRedelivery() throws Exception {
         final List<Position> actualEntriesToConsumer1 = new CopyOnWriteArrayList<>();