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/09/09 15:15:08 UTC
(pulsar) 14/14: [fix][ml] Fix active cursor retention and deferred-update synchronization (#26511)
This is an automated email from the ASF dual-hosted git repository.
lhotari pushed a commit to branch branch-4.2
in repository https://gitbox.apache.org/repos/asf/pulsar.git
commit b3dcc415750c667d06f87fa0a0036601ff41b9dc
Author: Lari Hotari <lh...@users.noreply.github.com>
AuthorDate: Wed Sep 9 17:25:52 2026 +0300
[fix][ml] Fix active cursor retention and deferred-update synchronization (#26511)
(cherry picked from commit 72632e512b3714d42966fee1774613071eb89c91)
---
managed-ledger/pom.xml | 5 +
.../impl/ActiveManagedCursorContainerImpl.java | 208 +++++++--
.../ActiveManagedCursorContainerRetentionTest.java | 491 +++++++++++++++++++++
.../ActiveManagedCursorContainerBenchmark.java | 44 +-
...ctiveManagedCursorContainerCohortBenchmark.java | 82 ++++
5 files changed, 798 insertions(+), 32 deletions(-)
diff --git a/managed-ledger/pom.xml b/managed-ledger/pom.xml
index 2af2d596c29f..da1f381f1fe0 100644
--- a/managed-ledger/pom.xml
+++ b/managed-ledger/pom.xml
@@ -67,6 +67,11 @@
<artifactId>guava</artifactId>
</dependency>
+ <dependency>
+ <groupId>it.unimi.dsi</groupId>
+ <artifactId>fastutil</artifactId>
+ </dependency>
+
<dependency>
<groupId>${project.groupId}</groupId>
<artifactId>testmocks</artifactId>
diff --git a/managed-ledger/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerImpl.java b/managed-ledger/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerImpl.java
index 649f3060e9c4..889dee2e2058 100644
--- a/managed-ledger/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerImpl.java
+++ b/managed-ledger/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerImpl.java
@@ -20,13 +20,16 @@ package org.apache.bookkeeper.mledger.impl;
import static java.util.Objects.requireNonNull;
import com.google.common.annotations.VisibleForTesting;
+import it.unimi.dsi.fastutil.objects.ObjectArrayList;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
+import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
-import java.util.PriorityQueue;
+import java.util.NoSuchElementException;
+import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.locks.StampedLock;
@@ -49,10 +52,16 @@ import org.apache.commons.lang3.tuple.Pair;
*/
@Slf4j
public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorContainer {
+ private static final int MIN_REMOVALS_BEFORE_CLEANUP = 64;
+ // Below this size, the JDK 21 object-array sort does not allocate a temporary merge buffer.
+ private static final int SMALL_POSITION_UPDATE_BATCH = 32;
+
private static class Node {
- final ManagedCursor cursor;
+ // Iterators read this without the lock. Removed nodes must not retain the cursor's object graph.
+ volatile ManagedCursor cursor;
Position position;
Position pendingPosition;
+ boolean pendingPositionUpdateQueued;
boolean pendingRemove = false;
MutableInt numberOfCursorsAtSamePositionOrBefore;
Node prev;
@@ -65,6 +74,8 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
}
// number of nodes in the double-linked list
int trackedNodeCount = 0;
+ // Conservative count: a removed node may have been reused since the last cleanup or position flush.
+ private int removalsSinceLastCleanup;
private final long continueCachingAddedEntriesAfterLastActiveCursorLeavesMillis;
private volatile long cursorRemovedTimestampMillis;
private volatile int cursorCount;
@@ -86,18 +97,20 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
// Maps a cursor to the node
private final ConcurrentMap<String, Node> cursors = new ConcurrentHashMap<>();
private final Map<String, Node> pendingRemovedCursors = new HashMap<>();
- private final PriorityQueue<Node> pendingPositionUpdates = new PriorityQueue<>(new Comparator<Node>() {
+ // Accumulate without ordering; only incremental flushes benefit from ordering by old position.
+ private final ObjectArrayList<Node> pendingPositionUpdates = new ObjectArrayList<>();
+ private static final Comparator<Node> PENDING_POSITION_COMPARATOR = new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
if (o1.position == null) {
- return 1; // o1 is null, should be after o2
+ return o2.position == null ? 0 : -1;
}
if (o2.position == null) {
- return -1; // o2 is null, should be after o1
+ return 1;
}
- return o2.position.compareTo(o1.position);
+ return o1.position.compareTo(o2.position);
}
- });
+ };
private final StampedLock rwLock = new StampedLock();
@@ -114,24 +127,26 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
}
node.pendingPosition = null;
} else {
- if (node.pendingPosition == null) {
- pendingPositionUpdates.add(node);
+ // Re-adding an existing cursor cancels pending untracking, just like updateCursor.
+ if (node.pendingRemove) {
+ node.pendingRemove = false;
+ pendingRemovedCursors.remove(cursor.getName());
}
- node.pendingPosition = position;
+ queuePositionUpdate(node, position);
}
} else {
if (position != null) {
node = pendingRemovedCursors.remove(cursor.getName());
if (node != null) {
node.pendingRemove = false;
+ node.cursor = cursor;
}
}
if (node == null) {
node = new Node(cursor, position);
}
if (position != null) {
- node.pendingPosition = position;
- pendingPositionUpdates.add(node);
+ queuePositionUpdate(node, position);
}
if (cursors.put(cursor.getName(), node) == null) {
cursorCount++;
@@ -259,9 +274,16 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
pendingRemovedCursors.put(name, node);
node.pendingRemove = true;
}
+ node.cursor = null;
node.pendingPosition = null;
cursorRemovedTimestampMillis = System.currentTimeMillis();
cursorCount--;
+ // Keep position updates lazy, but bound retained nodes even if nobody queries their ordering.
+ // Scaling the batch with the live set amortizes scanning it over many removals.
+ if (++removalsSinceLastCleanup >= Math.max(MIN_REMOVALS_BEFORE_CLEANUP, cursorCount)
+ || cursorCount == 0) {
+ compactRemovedNodes();
+ }
return true;
} else {
return false;
@@ -271,6 +293,46 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
}
}
+ private void compactRemovedNodes() {
+ // Preserve lazy position updates while compacting the pending list in linear time.
+ pendingPositionUpdates.removeIf(node -> {
+ if (node.cursor == null) {
+ node.pendingPositionUpdateQueued = false;
+ return true;
+ }
+ return false;
+ });
+ if (pendingRemovedCursors.values().removeIf(node -> node.cursor == null)) {
+ Node previous = null;
+ Node current = head;
+ int count = 0;
+ while (current != null) {
+ Node next = current.next;
+ if (current.cursor == null) {
+ if (previous == null) {
+ head = next;
+ } else {
+ previous.next = next;
+ }
+ if (next != null) {
+ next.prev = previous;
+ }
+ current.prev = null;
+ current.next = null;
+ trackedNodeCount--;
+ } else {
+ // Equal-position nodes already share a counter. The last survivor in each group
+ // sets its final rank, avoiding per-removal counter scans and new allocations.
+ current.numberOfCursorsAtSamePositionOrBefore.setValue(++count);
+ previous = current;
+ }
+ current = next;
+ }
+ tail = previous;
+ }
+ removalsSinceLastCleanup = 0;
+ }
+
/**
* Remove a node from the double-linked list and update counters.
*/
@@ -334,17 +396,25 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
pendingRemovedCursors.remove(cursor.getName());
}
// position changed, mark the node as pending
- if (node.pendingPosition == null) {
- pendingPositionUpdates.add(node);
- }
- node.pendingPosition = newPosition;
+ queuePositionUpdate(node, newPosition);
}
} finally {
rwLock.unlockWrite(stamp);
}
}
+ private void queuePositionUpdate(Node node, Position position) {
+ // Clearing pendingPosition cancels an update, but does not remove its pending-list entry.
+ // In particular, reactivating a node must not enqueue the same node again.
+ if (!node.pendingPositionUpdateQueued) {
+ pendingPositionUpdates.add(node);
+ node.pendingPositionUpdateQueued = true;
+ }
+ node.pendingPosition = position;
+ }
+
private void processPendingPositions() {
+ removalsSinceLastCleanup = 0;
if (pendingRemovedCursors.isEmpty() && pendingPositionUpdates.isEmpty()) {
// No pending changes, nothing to do
return;
@@ -365,11 +435,24 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
}
pendingRemovedCursors.clear();
}
- while (true) {
- Node node = pendingPositionUpdates.poll();
- if (node == null) {
- break; // No more pending updates
+ int pendingCount = pendingPositionUpdates.size();
+ if (pendingCount > 1 && pendingCount < SMALL_POSITION_UPDATE_BATCH) {
+ // Keep the efficient small-array sort without allocating a temporary merge buffer.
+ pendingPositionUpdates.sort(PENDING_POSITION_COMPARATOR);
+ } else if (pendingCount >= SMALL_POSITION_UPDATE_BATCH) {
+ // Ordered batches need no sort. Otherwise use in-place sorting to avoid per-flush buffers.
+ for (int i = 1; i < pendingCount; i++) {
+ if (PENDING_POSITION_COMPARATOR.compare(pendingPositionUpdates.get(i - 1),
+ pendingPositionUpdates.get(i)) > 0) {
+ pendingPositionUpdates.unstableSort(PENDING_POSITION_COMPARATOR);
+ break;
+ }
}
+ }
+ while (!pendingPositionUpdates.isEmpty()) {
+ // Drain from the end to process descending old positions without shifting array elements.
+ Node node = pendingPositionUpdates.remove(pendingPositionUpdates.size() - 1);
+ node.pendingPositionUpdateQueued = false;
if (node.pendingPosition != null) {
if (node.position == null) {
node.position = node.pendingPosition;
@@ -393,6 +476,7 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
// Collect all nodes that should be in the list and update their positions
List<Node> activeNodes = new ArrayList<>();
for (Node node : cursors.values()) {
+ node.pendingPositionUpdateQueued = false;
if (node.pendingPosition != null) {
node.position = node.pendingPosition;
node.pendingPosition = null;
@@ -473,12 +557,13 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
// update the position
node.position = newPosition;
- if (node == tail) {
- // Node is at the tail, no need to update counters
+ // A tail that remains in its own position group keeps the same rank and counter.
+ if (node == tail && (node.prev == null
+ || (node.prev.position.compareTo(oldPosition) != 0
+ && node.prev.position.compareTo(newPosition) != 0))) {
return;
}
-
- // update the counters
+ // Even the tail must leave or join shared counters when its position group changes.
if (movingForward) {
// first decrement the counter for the old position
node.numberOfCursorsAtSamePositionOrBefore.decrement();
@@ -684,11 +769,21 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
@Override
public Position getSlowestCursorPosition() {
- long stamp = rwLock.readLock();
+ long stamp = rwLock.tryOptimisticRead();
+ if (stamp != 0 && pendingRemovedCursors.isEmpty() && pendingPositionUpdates.isEmpty()) {
+ // Snapshot scalar fields only; a concurrent writer can invalidate the list before validation.
+ Node first = head;
+ Position position = first != null ? first.position : null;
+ if (rwLock.validate(stamp)) {
+ return position;
+ }
+ }
+ // Flushing pending changes mutates the list and must be exclusive.
+ stamp = rwLock.writeLock();
try {
return internalSlowestReaderPosition();
} finally {
- rwLock.unlockRead(stamp);
+ rwLock.unlockWrite(stamp);
}
}
@@ -725,14 +820,24 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
public Iterator<ManagedCursor> iterator() {
final Iterator<Map.Entry<String, Node>> it = cursors.entrySet().iterator();
return new Iterator<ManagedCursor>() {
+ private ManagedCursor nextCursor;
+
@Override
public boolean hasNext() {
- return it.hasNext();
+ while (nextCursor == null && it.hasNext()) {
+ nextCursor = it.next().getValue().cursor;
+ }
+ return nextCursor != null;
}
@Override
public ManagedCursor next() {
- return it.next().getValue().cursor;
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ ManagedCursor result = nextCursor;
+ nextCursor = null;
+ return result;
}
@Override
@@ -757,6 +862,33 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
}
}
+ @VisibleForTesting
+ int getPendingPositionUpdatesCount() {
+ long stamp = rwLock.readLock();
+ try {
+ return pendingPositionUpdates.size();
+ } finally {
+ rwLock.unlockRead(stamp);
+ }
+ }
+
+ /** Returns one entry per retained node, including null for nodes whose cursor was released. */
+ @VisibleForTesting
+ List<ManagedCursor> getRetainedCursors() {
+ long stamp = rwLock.readLock();
+ try {
+ Set<Node> nodes = new HashSet<>(cursors.values());
+ nodes.addAll(pendingPositionUpdates);
+ nodes.addAll(pendingRemovedCursors.values());
+ for (Node node = head; node != null; node = node.next) {
+ nodes.add(node);
+ }
+ return nodes.stream().map(node -> node.cursor).toList();
+ } finally {
+ rwLock.unlockRead(stamp);
+ }
+ }
+
@Override
public int size() {
return cursorCount;
@@ -784,14 +916,21 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
*/
@VisibleForTesting
void checkOrderingAndNumberOfCursorsState() {
- long stamp = rwLock.readLock();
+ long stamp = rwLock.writeLock();
try {
processPendingPositions();
Node current = head;
+ Node previous = null;
int currentCount = 0;
Position lastPosition = null;
List<String> lastPositionCursorNames = new ArrayList<>();
while (current != null) {
+ if (current.cursor == null) {
+ throw new IllegalStateException("Released node still linked");
+ }
+ if (current.prev != previous) {
+ throw new IllegalStateException("Previous node link is inconsistent");
+ }
if (current.prev != null && current.position.compareTo(current.prev.position) < 0) {
throw new IllegalStateException("Cursors are not ordered: " + current.cursor.getName()
+ " with position " + current.position + " is after cursor " + current.prev.cursor.getName()
@@ -826,11 +965,18 @@ public class ActiveManagedCursorContainerImpl implements ActiveManagedCursorCont
} else {
lastPositionCursorNames.add(current.cursor.getName());
}
+ previous = current;
current = current.next;
-
+ }
+ if (tail != previous) {
+ throw new IllegalStateException("Tail does not match the last linked node");
+ }
+ if (currentCount != trackedNodeCount) {
+ throw new IllegalStateException("Tracked node count does not match the linked list: expected "
+ + trackedNodeCount + ", but found " + currentCount);
}
} finally {
- rwLock.unlockRead(stamp);
+ rwLock.unlockWrite(stamp);
}
}
}
diff --git a/managed-ledger/src/test/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerRetentionTest.java b/managed-ledger/src/test/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerRetentionTest.java
new file mode 100644
index 000000000000..a89a2ea22596
--- /dev/null
+++ b/managed-ledger/src/test/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerRetentionTest.java
@@ -0,0 +1,491 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.bookkeeper.mledger.impl;
+
+import static java.util.concurrent.TimeUnit.SECONDS;
+import static org.apache.bookkeeper.mledger.impl.MockManagedCursor.addCursor;
+import static org.apache.bookkeeper.mledger.impl.MockManagedCursor.createCursor;
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+import static org.awaitility.Awaitility.await;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+import io.netty.util.concurrent.DefaultThreadFactory;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NoSuchElementException;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.Future;
+import java.util.concurrent.atomic.AtomicReference;
+import org.apache.bookkeeper.mledger.ManagedCursor;
+import org.apache.bookkeeper.mledger.Position;
+import org.apache.bookkeeper.mledger.PositionFactory;
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+public class ActiveManagedCursorContainerRetentionTest {
+ private static final Position POSITION = PositionFactory.create(1, 1);
+
+ @DataProvider
+ public Object[][] positionUpdateBatches() {
+ List<Object[]> cases = new ArrayList<>();
+ for (int batchSize : new int[] {1, 31, 32, 33, 80, 100}) {
+ for (boolean reverse : new boolean[] {false, true}) {
+ for (boolean includeNewCursors : new boolean[] {false, true}) {
+ cases.add(new Object[] {batchSize, reverse, includeNewCursors});
+ }
+ }
+ }
+ return cases.toArray(new Object[0][]);
+ }
+
+ @Test(dataProvider = "positionUpdateBatches")
+ public void testBatchedPositionsMatchCursorRanks(int batchSize, boolean reverse, boolean includeNewCursors) {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ Map<String, Position> positions = new HashMap<>();
+ for (int i = 0; i < 200; i++) {
+ Position position = PositionFactory.create(1, i / 3);
+ addCursor(container, "cursor" + i, position);
+ positions.put("cursor" + i, position);
+ }
+ container.getSlowestCursorPosition();
+ for (int round = 0; round < 2; round++) {
+ for (int i = 0; i < batchSize; i++) {
+ int index = reverse ? batchSize - i - 1 : i;
+ String name = includeNewCursors && index % 2 == 0 ? "new" + index : "cursor" + index;
+ Position intermediate = PositionFactory.create(1, 1000 + index);
+ if (!positions.containsKey(name)) {
+ addCursor(container, name, intermediate);
+ } else {
+ container.updateCursor(container.get(name), intermediate);
+ }
+ // Coalesce repeated updates while moving into shared groups in both directions.
+ Position latest = PositionFactory.create(1, (index + round) % 2 == 0 ? index % 7 : 200 + index % 7);
+ container.updateCursor(container.get(name), latest);
+ positions.put(name, latest);
+ }
+ assertThat(container.getPendingPositionUpdatesCount()).isEqualTo(batchSize);
+ for (Map.Entry<String, Position> entry : positions.entrySet()) {
+ int expectedRank = (int) positions.values().stream()
+ .filter(position -> position.compareTo(entry.getValue()) <= 0).count();
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(container.get(entry.getKey())))
+ .as("rank of %s after batch %s", entry.getKey(), round).isEqualTo(expectedRank);
+ }
+ assertThat(container.getSlowestCursorPosition())
+ .isEqualTo(positions.values().stream().min(Position::compareTo).orElseThrow());
+ assertThat(container.getPendingPositionUpdatesCount()).isZero();
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+ }
+
+ @DataProvider
+ public Object[][] tracked() {
+ return new Object[][] {{false}, {true}};
+ }
+
+ @Test(dataProvider = "tracked")
+ public void testRemovedCursorReleasedBeforeCleanup(boolean tracked) {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ ManagedCursor survivor = createCursor(container, "survivor", POSITION);
+ container.add(survivor, POSITION);
+ addCursor(container, "removed", POSITION);
+ if (tracked) {
+ container.getSlowestCursorPosition();
+ }
+ container.removeCursor("removed");
+
+ // Inspect retention without triggering a position flush or relying on GC timing.
+ assertThat(container.getRetainedCursors()).containsExactlyInAnyOrder(survivor, null);
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(survivor)).isEqualTo(1);
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ @Test(dataProvider = "tracked")
+ public void testLastRemovalClearsRetainedNodes(boolean tracked) {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ for (int i = 0; i < 100; i++) {
+ addCursor(container, "cursor", POSITION);
+ if (tracked) {
+ container.getSlowestCursorPosition();
+ }
+ assertThat(container.removeCursor("cursor")).isTrue();
+ assertThat(container.getRetainedCursors()).isEmpty();
+ assertThat(container.size()).isZero();
+ }
+ }
+
+ @Test
+ public void testPendingNodesBoundedWithoutPositionQueries() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ ManagedCursor survivor = createCursor(container, "survivor", POSITION);
+ container.add(survivor, POSITION);
+ for (int i = 0; i < 1000; i++) {
+ addCursor(container, "cursor" + i, POSITION);
+ container.removeCursor("cursor" + i);
+ List<ManagedCursor> retained = container.getRetainedCursors();
+ assertThat(retained).hasSizeLessThanOrEqualTo(65);
+ assertThat(retained.stream().filter(cursor -> cursor != null).toList()).containsExactly(survivor);
+ }
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(survivor)).isEqualTo(1);
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ @Test
+ public void testTrackedRemovalsTriggerCleanupWithoutPendingUpdates() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ for (int i = 0; i < 1000; i++) {
+ addCursor(container, "cursor" + i, PositionFactory.create(1, i));
+ }
+ container.getSlowestCursorPosition();
+ for (int i = 0; i < 900; i++) {
+ container.removeCursor("cursor" + i);
+ assertThat(container.getRetainedCursors()).hasSizeLessThanOrEqualTo(
+ container.size() + Math.max(64, container.size()));
+ if (i == 63) {
+ // A large live set should not be rebuilt every fixed-size batch of removals.
+ assertThat(container.getRetainedCursors()).hasSize(1000);
+ }
+ }
+ assertThat(container.getSlowestCursorPosition()).isEqualTo(PositionFactory.create(1, 900));
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(container.get("cursor999"))).isEqualTo(100);
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ @Test
+ public void testCompactionPreservesPendingUpdatesAndSharedCounters() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ for (int i = 0; i < 200; i++) {
+ addCursor(container, "cursor" + i, PositionFactory.create(1, i / 10));
+ }
+ container.getSlowestCursorPosition();
+ ManagedCursor moved = container.get("cursor199");
+ container.updateCursor(moved, PositionFactory.create(1, 0));
+ for (int i = 0; i < 200; i += 2) {
+ container.removeCursor("cursor" + i);
+ }
+ assertThat(container.getRetainedCursors()).hasSize(100).doesNotContainNull();
+ assertThat(container.getPendingPositionUpdatesCount()).isEqualTo(1);
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(moved)).isEqualTo(6);
+ for (int i = 1; i < 199; i += 2) {
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(container.get("cursor" + i)))
+ .as("rank of cursor%s after compaction and the pending move", i)
+ .isEqualTo(Math.min(100, (i / 10 + 1) * 5 + 1));
+ }
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ @Test
+ public void testPositionQueryResetsCleanupBatch() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ addCursor(container, "survivor", POSITION);
+ for (int i = 0; i < 63; i++) {
+ addCursor(container, "cursor" + i, POSITION);
+ container.removeCursor("cursor" + i);
+ }
+ container.getSlowestCursorPosition();
+ addCursor(container, "removed", POSITION);
+ container.removeCursor("removed");
+ // The query already reclaimed the old batch; this removal should remain deferred.
+ assertThat(container.getRetainedCursors()).hasSize(2).containsNull();
+ }
+
+ @Test
+ public void testReusedNodeUsesCurrentCursorInstance() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ addCursor(container, "survivor", POSITION);
+ addCursor(container, "recreated", POSITION);
+ container.getSlowestCursorPosition();
+ container.removeCursor("recreated");
+ ManagedCursor replacement = createCursor(container, "recreated", POSITION);
+ container.add(replacement, POSITION);
+
+ assertThat(container.get("recreated")).isSameAs(replacement);
+ assertThat(container.getRetainedCursors()).doesNotContainNull().contains(replacement);
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(replacement)).isEqualTo(2);
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ @Test
+ public void testReactivationDoesNotDuplicatePendingUpdates() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ addCursor(container, "first", POSITION);
+ addCursor(container, "second", POSITION);
+ container.getSlowestCursorPosition();
+ for (int i = 0; i < 1000; i++) {
+ container.removeCursor("first");
+ addCursor(container, "first", POSITION);
+ container.removeCursor("second");
+ addCursor(container, "second", POSITION);
+ if (i < 31) {
+ assertThat(container.getPendingPositionUpdatesCount()).isEqualTo(2);
+ } else {
+ // Compaction can discard the removed node before reactivation, leaving new orphan
+ // nodes until the next batch. Reused active nodes must not accumulate pending-list entries.
+ assertThat(container.getPendingPositionUpdatesCount()).isLessThanOrEqualTo(66);
+ }
+ }
+ container.checkOrderingAndNumberOfCursorsState();
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(container.get("first"))).isEqualTo(2);
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(container.get("second"))).isEqualTo(2);
+ }
+
+ @DataProvider
+ public Object[][] pendingUntracking() {
+ return new Object[][] {{1, false}, {1, true}, {10, false}, {10, true}};
+ }
+
+ @Test(dataProvider = "pendingUntracking")
+ public void testAddExistingCursorCancelsPendingUntracking(int cursorCount, boolean untrackWithAdd) {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ for (int i = 0; i < cursorCount; i++) {
+ addCursor(container, "cursor" + i, PositionFactory.create(1, i + 1));
+ }
+ container.getSlowestCursorPosition();
+ int movedIndex = cursorCount / 2;
+ ManagedCursor moved = container.get("cursor" + movedIndex);
+ if (untrackWithAdd) {
+ container.add(moved, null);
+ } else {
+ container.updateCursor(moved, null);
+ }
+ Position later = PositionFactory.create(1, cursorCount + 1);
+ container.add(moved, later);
+ // One pending update rebuilds a singleton container but uses incremental movement with ten cursors.
+ assertThat(container.getSlowestCursorPosition()).isEqualTo(cursorCount == 1 ? later : POSITION);
+ assertThat(container.size()).isEqualTo(cursorCount);
+ for (int i = 0; i < cursorCount; i++) {
+ int expectedRank = i == movedIndex ? cursorCount : (i < movedIndex ? i + 1 : i);
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(container.get("cursor" + i)))
+ .as("rank of cursor%s after cancelling pending untracking", i)
+ .isEqualTo(expectedRank);
+ }
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ @Test
+ public void testReactivatedTailLeavesSharedPositionGroup() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ for (int i = 0; i < 6; i++) {
+ addCursor(container, "cursor" + i, POSITION);
+ }
+ container.getSlowestCursorPosition();
+ // Insert incrementally after the existing group to establish the tail independently of map iteration order.
+ addCursor(container, "tail", POSITION);
+ container.getSlowestCursorPosition();
+ for (int i = 3; i < 6; i++) {
+ container.removeCursor("cursor" + i);
+ }
+ container.getSlowestCursorPosition();
+
+ Position later = PositionFactory.create(1, 2);
+ container.updateCursor(container.get("tail"), later);
+ container.removeCursor("tail");
+ addCursor(container, "tail", later);
+ assertThat(container.getPendingPositionUpdatesCount()).isEqualTo(1);
+ for (int i = 0; i < 3; i++) {
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(container.get("cursor" + i)))
+ .as("rank of cursor%s after the reactivated tail leaves its group", i)
+ .isEqualTo(3);
+ }
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(container.get("tail"))).isEqualTo(4);
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ @Test
+ public void testTailPositionGroupsRemainCorrectAfterCompaction() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ for (int i = 0; i < 4; i++) {
+ addCursor(container, "cursor" + i, POSITION);
+ }
+ addCursor(container, "tail", PositionFactory.create(1, 3));
+ container.getSlowestCursorPosition();
+ ManagedCursor tailCursor = container.get("tail");
+ // Join and leave the preceding group, and move in both directions within a separate tail group.
+ for (int entryId : new int[] {1, 2, 3, 2, 1, 2}) {
+ container.updateCursor(tailCursor, PositionFactory.create(1, entryId));
+ for (int i = 0; i < 4; i++) {
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(container.get("cursor" + i)))
+ .as("rank of cursor%s with tail at entry %s", i, entryId)
+ .isEqualTo(entryId == 1 ? 5 : 4);
+ }
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(tailCursor)).isEqualTo(5);
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ container.removeCursor("cursor0");
+ for (int i = 0; i < 63; i++) {
+ addCursor(container, "temporary" + i, POSITION);
+ container.removeCursor("temporary" + i);
+ }
+ // The removal batch compacts the tracked list without flushing any position updates.
+ assertThat(container.getRetainedCursors()).hasSize(4).doesNotContainNull();
+ for (int i = 1; i < 4; i++) {
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(container.get("cursor" + i)))
+ .isEqualTo(3);
+ }
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(tailCursor)).isEqualTo(4);
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ @Test
+ public void testCompactionRemovesTailBeforeAppending() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ for (int i = 1; i <= 5; i++) {
+ addCursor(container, "cursor" + i, PositionFactory.create(1, i));
+ }
+ container.getSlowestCursorPosition();
+ container.removeCursor("cursor5");
+ for (int i = 0; i < 63; i++) {
+ addCursor(container, "temporary" + i, POSITION);
+ container.removeCursor("temporary" + i);
+ }
+ // Verify compaction occurred without a position query repairing the list first.
+ assertThat(container.getRetainedCursors()).hasSize(4).doesNotContainNull();
+ Position appendedPosition = PositionFactory.create(1, 9);
+ addCursor(container, "appended", appendedPosition);
+ ManagedCursor appended = container.get("appended");
+ assertThat(container.getPendingPositionUpdatesCount()).isEqualTo(1);
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(appended)).isEqualTo(5);
+ container.checkOrderingAndNumberOfCursorsState();
+ for (int i = 1; i <= 4; i++) {
+ container.removeCursor("cursor" + i);
+ }
+ assertThat(container.size()).isEqualTo(1);
+ assertThat(container.getSlowestCursorPosition()).isEqualTo(appendedPosition);
+ assertThat(container.getNumberOfCursorsAtSamePositionOrBefore(appended)).isEqualTo(1);
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ @Test
+ public void testSlowestPositionFlushWaitsForReaders() throws Exception {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ ManagedCursor cursor = mock(ManagedCursor.class);
+ when(cursor.getName()).thenReturn("cursor");
+ container.add(cursor, POSITION);
+ CountDownLatch readLockHeld = new CountDownLatch(1);
+ CountDownLatch releaseReadLock = new CountDownLatch(1);
+ AtomicReference<Thread> flushThread = new AtomicReference<>();
+ assertThat(container.getPendingPositionUpdatesCount()).isEqualTo(1);
+ when(cursor.toString()).thenAnswer(invocation -> {
+ readLockHeld.countDown();
+ assertThat(releaseReadLock.await(30, SECONDS)).isTrue();
+ return "cursor";
+ });
+ ExecutorService executor = Executors.newFixedThreadPool(2,
+ new DefaultThreadFactory("cursor-container-flush-test"));
+ try {
+ Future<String> reader = executor.submit(container::toString);
+ assertThat(readLockHeld.await(10, SECONDS)).isTrue();
+ Future<Position> slowest = executor.submit(() -> {
+ flushThread.set(Thread.currentThread());
+ return container.getSlowestCursorPosition();
+ });
+ // Wait for actual lock contention, rather than assuming the task ran after a fixed delay.
+ // A shared-lock regression completes the task instead and fails the following assertion.
+ await().atMost(10, SECONDS).until(() -> slowest.isDone()
+ || (flushThread.get() != null && flushThread.get().getState() == Thread.State.WAITING));
+ assertThat(slowest.isDone()).isFalse();
+ releaseReadLock.countDown();
+ assertThat(slowest.get(10, SECONDS)).isEqualTo(POSITION);
+ assertThat(reader.get(10, SECONDS)).isEqualTo("[cursor]");
+ assertThat(container.getPendingPositionUpdatesCount()).isZero();
+ } finally {
+ releaseReadLock.countDown();
+ executor.shutdownNow();
+ assertThat(executor.awaitTermination(10, SECONDS)).isTrue();
+ }
+ }
+
+ @Test
+ public void testSlowestPositionReadDoesNotExcludeOtherReaders() throws Exception {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ ManagedCursor cursor = mock(ManagedCursor.class);
+ when(cursor.getName()).thenReturn("cursor");
+ container.add(cursor, POSITION);
+ assertThat(container.getSlowestCursorPosition()).isEqualTo(POSITION);
+
+ CountDownLatch readLockHeld = new CountDownLatch(1);
+ CountDownLatch releaseReadLock = new CountDownLatch(1);
+ when(cursor.toString()).thenAnswer(invocation -> {
+ // toString calls the cursor while holding the container's read lock.
+ readLockHeld.countDown();
+ assertThat(releaseReadLock.await(30, SECONDS)).isTrue();
+ return "cursor";
+ });
+ ExecutorService executor = Executors.newFixedThreadPool(2,
+ new DefaultThreadFactory("cursor-container-read-test"));
+ try {
+ Future<String> reader = executor.submit(container::toString);
+ assertThat(readLockHeld.await(10, SECONDS)).isTrue();
+ Future<Position> slowest = executor.submit(container::getSlowestCursorPosition);
+ assertThat(slowest.get(10, SECONDS)).isEqualTo(POSITION);
+ releaseReadLock.countDown();
+ assertThat(reader.get(10, SECONDS)).isEqualTo("[cursor]");
+ } finally {
+ releaseReadLock.countDown();
+ executor.shutdownNow();
+ assertThat(executor.awaitTermination(10, SECONDS)).isTrue();
+ }
+ }
+
+ @Test
+ public void testSlowestPositionFlushesPendingChanges() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ assertThat(container.getSlowestCursorPosition()).isNull();
+ Position later = PositionFactory.create(1, 2);
+ Position latest = PositionFactory.create(1, 3);
+ addCursor(container, "later", later);
+ assertThat(container.getSlowestCursorPosition()).isEqualTo(later);
+ assertThat(container.getSlowestCursorPosition()).isEqualTo(later);
+ addCursor(container, "earlier", POSITION);
+ assertThat(container.getSlowestCursorPosition()).isEqualTo(POSITION);
+ container.updateCursor(container.get("earlier"), latest);
+ assertThat(container.getSlowestCursorPosition()).isEqualTo(later);
+ container.removeCursor("later");
+ assertThat(container.getSlowestCursorPosition()).isEqualTo(latest);
+ assertThat(container.getSlowestCursorPosition()).isEqualTo(latest);
+ container.removeCursor("earlier");
+ assertThat(container.getSlowestCursorPosition()).isNull();
+ }
+
+ @Test
+ public void testIteratorSkipsRemovedNodes() {
+ ActiveManagedCursorContainerImpl container = new ActiveManagedCursorContainerImpl();
+ addCursor(container, "first", POSITION);
+ addCursor(container, "second", POSITION);
+ Iterator<ManagedCursor> iterator = container.iterator();
+ container.removeCursor("first");
+ container.removeCursor("second");
+ assertThat(iterator.hasNext()).isFalse();
+ assertThatThrownBy(iterator::next).isInstanceOf(NoSuchElementException.class);
+
+ addCursor(container, "third", POSITION);
+ Iterator<ManagedCursor> prefetched = container.iterator();
+ assertThat(prefetched.hasNext()).isTrue();
+ assertThat(prefetched.hasNext()).isTrue();
+ container.removeCursor("third");
+ assertThat(prefetched.next().getName()).isEqualTo("third");
+ assertThat(prefetched.hasNext()).isFalse();
+ }
+}
diff --git a/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerBenchmark.java b/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerBenchmark.java
index 75aea0166fa8..a282953868d7 100644
--- a/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerBenchmark.java
+++ b/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerBenchmark.java
@@ -25,6 +25,7 @@ import java.util.concurrent.TimeUnit;
import java.util.function.Supplier;
import java.util.stream.IntStream;
import org.apache.bookkeeper.mledger.ManagedCursor;
+import org.apache.bookkeeper.mledger.Position;
import org.apache.bookkeeper.mledger.PositionFactory;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
@@ -132,6 +133,47 @@ public class ActiveManagedCursorContainerBenchmark {
return doRandomSeekingForward(threadState);
}
+ @Threads(1)
+ @Benchmark
+ public int tailSeekingForward(ThreadState threadState) {
+ long counter = threadState.nextCounter();
+ ManagedCursor cursor = cursors.get(cursors.size() - 1);
+ // Keep moving the fastest cursor, without joining or leaving a shared position group.
+ cursor.seek(cursor.getReadPosition().getPositionAfterEntries(1));
+ return getNumberOfCursorsAtSamePositionOrBeforeRatio > 0
+ && counter % getNumberOfCursorsAtSamePositionOrBeforeRatio == 0
+ ? container.getNumberOfCursorsAtSamePositionOrBefore(cursor)
+ : (int) cursor.getReadPosition().getEntryId();
+ }
+
+ @Threads(1)
+ @Benchmark
+ public Position slowestCursorPosition01() {
+ return container.getSlowestCursorPosition();
+ }
+
+ @Threads(10)
+ @Benchmark
+ public Position slowestCursorPosition10() {
+ return container.getSlowestCursorPosition();
+ }
+
+ @Threads(1)
+ @Benchmark
+ public int cursorChurn(ThreadState threadState) {
+ long counter = threadState.nextCounter();
+ // Keep the other cursors active while repeatedly replacing one subscription.
+ container.removeCursor(cursors.get(0).getName());
+ // Use a new name and instance so that removed nodes cannot simply be reused indefinitely.
+ MockManagedCursor cursor = MockManagedCursor.createCursor(container, "churn" + counter,
+ PositionFactory.create(0, counter));
+ cursors.set(0, cursor);
+ container.add(cursor, cursor.getReadPosition());
+ return getNumberOfCursorsAtSamePositionOrBeforeRatio > 0
+ && counter % getNumberOfCursorsAtSamePositionOrBeforeRatio == 0
+ ? container.getNumberOfCursorsAtSamePositionOrBefore(cursor) : container.size();
+ }
+
private int doRandomSeekingForward(ThreadState threadState) {
Random random = threadState.random;
long counter = threadState.nextCounter();
@@ -147,4 +189,4 @@ public class ActiveManagedCursorContainerBenchmark {
// we return the entry id of the cursor's read position
: (int) cursor.getReadPosition().getEntryId();
}
-}
\ No newline at end of file
+}
diff --git a/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerCohortBenchmark.java b/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerCohortBenchmark.java
new file mode 100644
index 000000000000..cf233dcb9a0c
--- /dev/null
+++ b/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/ActiveManagedCursorContainerCohortBenchmark.java
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.bookkeeper.mledger.impl;
+
+import java.util.concurrent.TimeUnit;
+import org.apache.bookkeeper.mledger.PositionFactory;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OperationsPerInvocation;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.TearDown;
+import org.openjdk.jmh.annotations.Threads;
+
+@State(Scope.Benchmark)
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.SECONDS)
+public class ActiveManagedCursorContainerCohortBenchmark {
+ @Param({"100", "500"})
+ public int numberOfCursors;
+ private ActiveManagedCursorContainerImpl container;
+ private MockManagedCursor[] cohort;
+
+ @Setup(Level.Trial)
+ public void setup() {
+ container = new ActiveManagedCursorContainerImpl();
+ cohort = new MockManagedCursor[32];
+ for (int i = 0; i < numberOfCursors; i++) {
+ var position = PositionFactory.create(1, i);
+ var cursor = MockManagedCursor.createCursor(container, "cursor" + i, position);
+ container.add(cursor, position);
+ if (i >= numberOfCursors - cohort.length) {
+ cohort[i - (numberOfCursors - cohort.length)] = cursor;
+ }
+ }
+ container.checkOrderingAndNumberOfCursorsState();
+ }
+
+ @Benchmark
+ @Threads(1)
+ @OperationsPerInvocation(32)
+ public int advanceCohort() {
+ // Queue a wave in ascending old-position order. Each cursor advances beyond all old cohort positions.
+ for (var cursor : cohort) {
+ cursor.seek(cursor.getReadPosition().getPositionAfterEntries(cohort.length));
+ }
+ // 32 pending updates stay below trackedNodeCount / 2 for both parameters, forcing incremental processing.
+ return container.getNumberOfCursorsAtSamePositionOrBefore(cohort[cohort.length - 1]);
+ }
+
+ @TearDown(Level.Trial)
+ public void verify() {
+ container.checkOrderingAndNumberOfCursorsState();
+ for (int i = 0; i < cohort.length; i++) {
+ int expected = numberOfCursors - cohort.length + i + 1;
+ if (container.getNumberOfCursorsAtSamePositionOrBefore(cohort[i]) != expected) {
+ throw new AssertionError("Wrong cohort rank at index " + i);
+ }
+ }
+ }
+}