You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@beam.apache.org by "arunpandianp (via GitHub)" <gi...@apache.org> on 2026/10/14 19:56:58 UTC

[PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

arunpandianp opened a new pull request, #40593:
URL: https://github.com/apache/beam/pull/40593

   
   `KeyGroupWorkQueue` guarded a doubly-linked global queue and per-key-group queues with a single `ReentrantLock`, creating lock contention across worker and `GetWork` threads when multi-key bundles are enabled.
   
   Use `LinkedBlockingQueue` as the `BoundedQueueExecutor` work queue unconditionally, and index stealable work in `KeyGroupWorkIndex` across 64 fixed `HashMap<QueueKey, ArrayDeque<QueuedWork>>` shards synchronized per shard. An executor thread and `pollWork` coordinate on a `QueuedWork` via a single atomic state transition, clearing work and budget references immediately upon claim. Claimed entries at the head of a key-group queue are drained in amortized O(1) time during index mutations, and stale shells left in `LinkedBlockingQueue` by stolen work are purged in bulk once the queue size exceeds twice `maximumElementsOutstanding`.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "arunpandianp (via GitHub)" <gi...@apache.org>.
arunpandianp commented on code in PR #40593:
URL: https://github.com/apache/beam/pull/40593#discussion_r4296958813


##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -328,49 +346,129 @@ public synchronized void close() {
     }
   }
 
+  /**
+   * A {@link Runnable} for an {@link ExecutableWork} that can be claimed either by an executor
+   * thread in {@link #run} or by a multi-key bundle in {@link #pollWork}.
+   *
+   * <p>Thread safety: {@link #state} is {@code volatile} and transitions at most once from {@link
+   * #QUEUED} to {@link #STARTED} or {@link #STOLEN} via {@link #STATE}{@code .compareAndSet}.
+   * Non-final fields {@link #work} and {@link #handle} are written before {@code state} is
+   * initialized in the constructor, and are subsequently read and cleared only by the single thread
+   * that wins that {@code compareAndSet}. All other accesses read only {@code final} fields or
+   * {@code volatile state}.
+   */
   static final class QueuedWork implements Runnable {
 
-    private final ExecutableWork work;
-    private final BoundedQueueExecutorWorkHandleImpl handle;
-
-    public QueuedWork(ExecutableWork work, BoundedQueueExecutorWorkHandleImpl handle) {
+    private static final int QUEUED = 0;
+    private static final int STARTED = 1; // Claimed by an executor thread in run().
+    private static final int STOLEN = 2; // Claimed by a multi-key bundle in pollWork().
+
+    private static final AtomicIntegerFieldUpdater<QueuedWork> STATE =
+        AtomicIntegerFieldUpdater.newUpdater(QueuedWork.class, "state");
+
+    // Non-null iff the work is eligible to be stolen by a multi-key bundle.
+    private final @Nullable KeyGroupWorkIndex keyGroupWorkIndex;
+    private final KeyGroupWorkIndex.@Nullable QueueKey queueKey;
+    // Cleared upon claim so stale shells and claimed index entries do not retain work references.
+    private @Nullable ExecutableWork work;
+    private @Nullable BoundedQueueExecutorWorkHandleImpl handle;
+    private volatile int state = QUEUED;
+
+    QueuedWork(
+        ExecutableWork work,
+        BoundedQueueExecutorWorkHandleImpl handle,
+        @Nullable KeyGroupWorkIndex keyGroupWorkIndex) {
       this.work = work;
       this.handle = handle;
+      Work w = work.work();
+      if (keyGroupWorkIndex != null
+          && !w.getKeyGroup().equals(Work.KeyGroup.DEFAULT)
+          && !w.isMultiKeyBatchingDisabled()) {
+        this.keyGroupWorkIndex = keyGroupWorkIndex;
+        this.queueKey = new KeyGroupWorkIndex.QueueKey(w.getComputationId(), w.getKeyGroup());
+      } else {
+        this.keyGroupWorkIndex = null;
+        this.queueKey = null;
+      }
     }
 
     public ExecutableWork getWork() {

Review Comment:
   Keeping the null checks at one place inside getWork, getHandle and updated visibility of the methods.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "scwhittle (via GitHub)" <gi...@apache.org>.
scwhittle commented on code in PR #40593:
URL: https://github.com/apache/beam/pull/40593#discussion_r4311524848


##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -528,6 +531,12 @@ BoundedQueueExecutorWorkHandleImpl createBudgetHandle(Work work, long bytes) {
   /**
    * Purges stale shells in bulk if they accumulate while all executor threads are busy running
    * multi-key bundles.
+   *
+   * <p>{@code forceExecute} can queue more than {@code maximumElementsOutstanding} unstarted items
+   * (e.g. retries or finalizations). {@code elementsOutstanding} counts non-shell work items, so
+   * comparing {@code workQueue.size()} against {@code elementsOutstanding +
+   * maximumElementsOutstanding} allows up to {@code maximumElementsOutstanding} closed stale shells

Review Comment:
   nit: s/allows up to/means there is at least/



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "arunpandianp (via GitHub)" <gi...@apache.org>.
arunpandianp commented on code in PR #40593:
URL: https://github.com/apache/beam/pull/40593#discussion_r4316761915


##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -528,6 +531,12 @@ BoundedQueueExecutorWorkHandleImpl createBudgetHandle(Work work, long bytes) {
   /**
    * Purges stale shells in bulk if they accumulate while all executor threads are busy running
    * multi-key bundles.
+   *
+   * <p>{@code forceExecute} can queue more than {@code maximumElementsOutstanding} unstarted items
+   * (e.g. retries or finalizations). {@code elementsOutstanding} counts non-shell work items, so
+   * comparing {@code workQueue.size()} against {@code elementsOutstanding +
+   * maximumElementsOutstanding} allows up to {@code maximumElementsOutstanding} closed stale shells

Review Comment:
   done.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on code in PR #40593:
URL: https://github.com/apache/beam/pull/40593#discussion_r4275999072


##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -185,6 +200,18 @@ public boolean executorQueueIsEmpty() {
     return executor.getQueue().isEmpty();

Review Comment:
   **🟢 Low**: With lazy removal of stolen work, `workQueue` may still contain stale `QueuedWork` shells (e.g., if work was stolen and all worker threads are currently blocked inside long-running bundles without dequeuing, and `workQueue.size()` hasn't crossed `purgeQueueSizeThreshold`). As a result, `executorQueueIsEmpty()`—which is used by `StreamingDataflowWorker.executorQueueIsEmpty()` and `WorkerCustomSources` to decide whether to split backlog—can return `false` even when no runnable work remains in the queue. Consider purging stale shells or checking for unclaimed entries if `workQueue` is non-empty here.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "arunpandianp (via GitHub)" <gi...@apache.org>.
arunpandianp commented on code in PR #40593:
URL: https://github.com/apache/beam/pull/40593#discussion_r4296639384


##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -403,25 +501,52 @@ BoundedQueueExecutorWorkHandleImpl createBudgetHandle(Work work, long bytes) {
     checkArgument(handle instanceof BoundedQueueExecutorWorkHandleImpl);
     checkStateNotNull(onFailedWorkHandler);
     BoundedQueueExecutorWorkHandleImpl internalHandle = (BoundedQueueExecutorWorkHandleImpl) handle;
-    if (keyGroupWorkQueue == null) {
+    @Nullable KeyGroupWorkIndex index = keyGroupWorkIndex;
+    if (index == null) {
       return null;
     }
     while (true) {
-      @Nullable QueuedWork queuedWork = keyGroupWorkQueue.pollWork(computationId, keyGroup);
-      if (queuedWork == null) {
+      @Nullable QueuedWork stolen = index.pollAndClaim(computationId, keyGroup);
+      if (stolen == null) {
         return null;
       }
-      Work work = queuedWork.getWork().work();
+      ExecutableWork stolenWork = stolen.getWork();
+      BoundedQueueExecutorWorkHandleImpl stolenHandle = stolen.getHandle();
+      stolen.clearClaimedWork();
+      onWorkStolen();
+      Work work = stolenWork.work();
       if (work.isFailed()) {
-        queuedWork.getHandle().close();
+        stolenHandle.close();
         onFailedWorkHandler.onFailedWork(work);
         continue;
       }
-      internalHandle.merge(queuedWork.getHandle());
-      return queuedWork.getWork();
+      internalHandle.merge(stolenHandle);
+      return stolenWork;
     }
   }
 
+  /**
+   * Purges stale shells in bulk if they accumulate while all executor threads are busy running
+   * multi-key bundles.
+   */
+  private void onWorkStolen() {
+    if (workQueue.size() <= (long) elementsOutstanding.get() + maximumElementsOutstanding

Review Comment:
   If there are many forceExecute calls from retries or finalizations that don't respect the outstanding limit, jobs could reach more than maximumElementsOutstanding items in the queue. I wanted to avoid calling removeIf (O(n)) frequently in such cases.  elementsOutstanding gives us the count of non shell work items, so  elementsOutstanding + maximumElementsOutstanding means we allow up to maximumElementsOutstanding number of shells before removing them at once. I'll add a comment to explain. Let me know if you see other problems with using `elementsOutstanding`



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "arunpandianp (via GitHub)" <gi...@apache.org>.
arunpandianp commented on code in PR #40593:
URL: https://github.com/apache/beam/pull/40593#discussion_r4292181147


##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/KeyGroupWorkIndex.java:
##########
@@ -0,0 +1,175 @@
+/*
+ * 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.beam.runners.dataflow.worker.util;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import javax.annotation.concurrent.ThreadSafe;
+import org.apache.beam.runners.dataflow.worker.streaming.Work;
+import org.apache.beam.runners.dataflow.worker.util.BoundedQueueExecutor.QueuedWork;
+import org.apache.beam.vendor.guava.v32_1_2_jre.com.google.common.annotations.VisibleForTesting;
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+/**
+ * Sharded FIFO index of {@link QueuedWork} by computation and {@link Work.KeyGroup} for work
+ * stealing by multi-key bundles.
+ */
+@ThreadSafe
+final class KeyGroupWorkIndex {
+
+  private static final int NUM_SHARDS = 64;
+  private static final int INITIAL_QUEUE_CAPACITY = 4;
+
+  // Each shard map and its queues are guarded by synchronized (shard).
+  private final List<Map<QueueKey, ArrayDeque<QueuedWork>>> shards;
+
+  KeyGroupWorkIndex() {
+    List<Map<QueueKey, ArrayDeque<QueuedWork>>> list = new ArrayList<>(NUM_SHARDS);
+    for (int i = 0; i < NUM_SHARDS; i++) {
+      list.add(new HashMap<>());
+    }
+    this.shards = Collections.unmodifiableList(list);

Review Comment:
   done.



##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/KeyGroupWorkIndex.java:
##########
@@ -0,0 +1,175 @@
+/*
+ * 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.beam.runners.dataflow.worker.util;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import javax.annotation.concurrent.ThreadSafe;
+import org.apache.beam.runners.dataflow.worker.streaming.Work;
+import org.apache.beam.runners.dataflow.worker.util.BoundedQueueExecutor.QueuedWork;
+import org.apache.beam.vendor.guava.v32_1_2_jre.com.google.common.annotations.VisibleForTesting;
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+/**
+ * Sharded FIFO index of {@link QueuedWork} by computation and {@link Work.KeyGroup} for work
+ * stealing by multi-key bundles.
+ */
+@ThreadSafe
+final class KeyGroupWorkIndex {
+
+  private static final int NUM_SHARDS = 64;
+  private static final int INITIAL_QUEUE_CAPACITY = 4;
+
+  // Each shard map and its queues are guarded by synchronized (shard).
+  private final List<Map<QueueKey, ArrayDeque<QueuedWork>>> shards;
+
+  KeyGroupWorkIndex() {
+    List<Map<QueueKey, ArrayDeque<QueuedWork>>> list = new ArrayList<>(NUM_SHARDS);
+    for (int i = 0; i < NUM_SHARDS; i++) {
+      list.add(new HashMap<>());
+    }
+    this.shards = Collections.unmodifiableList(list);
+  }
+
+  private Map<QueueKey, ArrayDeque<QueuedWork>> shardFor(QueueKey queueKey) {
+    return shards.get(Math.floorMod(queueKey.hashCode(), NUM_SHARDS));
+  }
+
+  /** Adds {@code work} to its key-group queue if it has not been claimed yet. */
+  void add(QueuedWork work) {
+    if (work.isClaimed()) {
+      return;
+    }
+    QueueKey queueKey = work.queueKey();
+    Map<QueueKey, ArrayDeque<QueuedWork>> shard = shardFor(queueKey);
+    synchronized (shard) {
+      if (work.isClaimed()) {
+        return;
+      }
+      ArrayDeque<QueuedWork> queue =
+          shard.computeIfAbsent(queueKey, unused -> new ArrayDeque<>(INITIAL_QUEUE_CAPACITY));
+      drainClaimedFromHead(queue);
+      queue.addLast(work);
+    }
+  }
+
+  /**
+   * Drains claimed work from the head of {@code work}'s key-group queue. If an earlier item is
+   * still unclaimed, {@code work} remains in the queue with its references cleared and is drained
+   * in amortized O(1) time once the earlier item is claimed.
+   */
+  void remove(QueuedWork work) {

Review Comment:
   This is called after the work is claimed. renamed to `drainClaimed` and added a isClaimed check. 



##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/KeyGroupWorkIndex.java:
##########
@@ -0,0 +1,175 @@
+/*
+ * 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.beam.runners.dataflow.worker.util;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import javax.annotation.concurrent.ThreadSafe;
+import org.apache.beam.runners.dataflow.worker.streaming.Work;
+import org.apache.beam.runners.dataflow.worker.util.BoundedQueueExecutor.QueuedWork;
+import org.apache.beam.vendor.guava.v32_1_2_jre.com.google.common.annotations.VisibleForTesting;
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+/**
+ * Sharded FIFO index of {@link QueuedWork} by computation and {@link Work.KeyGroup} for work
+ * stealing by multi-key bundles.
+ */
+@ThreadSafe
+final class KeyGroupWorkIndex {
+
+  private static final int NUM_SHARDS = 64;
+  private static final int INITIAL_QUEUE_CAPACITY = 4;
+
+  // Each shard map and its queues are guarded by synchronized (shard).
+  private final List<Map<QueueKey, ArrayDeque<QueuedWork>>> shards;
+
+  KeyGroupWorkIndex() {
+    List<Map<QueueKey, ArrayDeque<QueuedWork>>> list = new ArrayList<>(NUM_SHARDS);
+    for (int i = 0; i < NUM_SHARDS; i++) {
+      list.add(new HashMap<>());
+    }
+    this.shards = Collections.unmodifiableList(list);
+  }
+
+  private Map<QueueKey, ArrayDeque<QueuedWork>> shardFor(QueueKey queueKey) {
+    return shards.get(Math.floorMod(queueKey.hashCode(), NUM_SHARDS));
+  }
+
+  /** Adds {@code work} to its key-group queue if it has not been claimed yet. */
+  void add(QueuedWork work) {
+    if (work.isClaimed()) {
+      return;
+    }
+    QueueKey queueKey = work.queueKey();
+    Map<QueueKey, ArrayDeque<QueuedWork>> shard = shardFor(queueKey);
+    synchronized (shard) {
+      if (work.isClaimed()) {
+        return;
+      }
+      ArrayDeque<QueuedWork> queue =
+          shard.computeIfAbsent(queueKey, unused -> new ArrayDeque<>(INITIAL_QUEUE_CAPACITY));

Review Comment:
   We create the 64 shards in constructor. The queueKey is based on keyGroup and is not known during the construction. Also extracted Shard to a separate class to improve readability.



##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -185,6 +200,18 @@ public boolean executorQueueIsEmpty() {
     return executor.getQueue().isEmpty();
   }
 
+  /** Returns the number of entries in the executor queue, including stale shells. */

Review Comment:
   The method is used only by tests. Renamed it to rawQueueSizeForTesting to be clear.



##########
runners/google-cloud-dataflow-java/worker/src/test/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutorTest.java:
##########
@@ -693,9 +602,291 @@ public void testPollWork_skipsFailedWorkAndCallsOnFailedWorkHandler() throws Exc
     assertNull(testExecutor.pollWork("compA", keyGroup, stealHandle, onFailedWorkHandler));
 
     blockerStop.countDown();
+    testExecutor.shutdown();
+    assertEquals(0, testExecutor.elementsOutstanding());
+    assertEquals(0, testExecutor.bytesOutstanding());
+  }
+
+  @Test
+  public void testPollWork_stolenWorkLeavesNoOpStaleShell() throws Exception {

Review Comment:
   done.



##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -185,6 +200,18 @@ public boolean executorQueueIsEmpty() {
     return executor.getQueue().isEmpty();

Review Comment:
   Updated to return true only when there are no stolen items in the queue. Also renamed it to executorQueueIsEmptyForTesting to prevent accidental prod use.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "arunpandianp (via GitHub)" <gi...@apache.org>.
arunpandianp commented on code in PR #40593:
URL: https://github.com/apache/beam/pull/40593#discussion_r4296949814


##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########


Review Comment:
   done.



##########
runners/google-cloud-dataflow-java/worker/src/test/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutorTest.java:
##########
@@ -742,25 +688,26 @@ public void testPollWork_purgeBacksOffWhileQueueHoldsMostlyUnstartedWork() throw
           createWorkWithCompIdAndKeyGroup("compA", keyGroup, ignored -> {}), 10);
     }
 
-    // The first steal purges its own stale shell; the remaining steals back off until the queue
-    // grows by more than maximumElementsOutstanding.
-    for (int i = 0; i < numWorks; i++) {
-      assertNotNull(
-          testExecutor.pollWork("compA", keyGroup, stealHandle, FAILING_FAILED_WORK_HANDLER));
-    }
-    assertEquals(numWorks - 1, testExecutor.executorQueueSize());
-
-    for (int i = 0; i <= maximumElementsOutstanding; i++) {
-      testExecutor.forceExecute(
-          createWorkWithCompIdAndKeyGroup("compA", keyGroup, ignored -> {}), 10);
+    // Each steal leaves a stale shell in the executor queue. While bundle1 is open, its stolen
+    // work is still counted in elementsOutstanding, so there is nothing to purge.
+    int numStolenByBundle1 = maximumElementsOutstanding + 2;
+    for (int i = 0; i < numStolenByBundle1; i++) {
+      assertNotNull(testExecutor.pollWork("compA", keyGroup, bundle1, FAILING_FAILED_WORK_HANDLER));
     }
-    assertNotNull(
-        testExecutor.pollWork("compA", keyGroup, stealHandle, FAILING_FAILED_WORK_HANDLER));
-    assertEquals(maximumElementsOutstanding, testExecutor.executorQueueSize());
+    assertEquals(numWorks, testExecutor.rawQueueSizeForTesting());

Review Comment:
   done.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "codecov[bot] (via GitHub)" <gi...@apache.org>.
codecov[bot] commented on PR #40593:
URL: https://github.com/apache/beam/pull/40593#issuecomment-6177747429

   ## [Codecov](https://app.codecov.io/gh/apache/beam/pull/40593?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
   :x: Patch coverage is `93.00699%` with `10 lines` in your changes missing coverage. Please review.
   :white_check_mark: Project coverage is 75.98%. Comparing base ([`76f6e6d`](https://app.codecov.io/gh/apache/beam/commit/76f6e6d7c0c1b2ce582c73d068ad9260cf15c5f3?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`3396fe8`](https://app.codecov.io/gh/apache/beam/commit/3396fe8b2f1c6a4d5edc38d0d6c67c1dfffa0f24?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
   :warning: Report is 171 commits behind head on master.
   
   | [Files with missing lines](https://app.codecov.io/gh/apache/beam/pull/40593?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
   |---|---|---|
   | [...unners/dataflow/worker/util/KeyGroupWorkIndex.java](https://app.codecov.io/gh/apache/beam/pull/40593?src=pr&el=tree&filepath=runners%2Fgoogle-cloud-dataflow-java%2Fworker%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fbeam%2Frunners%2Fdataflow%2Fworker%2Futil%2FKeyGroupWorkIndex.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cnVubmVycy9nb29nbGUtY2xvdWQtZGF0YWZsb3ctamF2YS93b3JrZXIvc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2JlYW0vcnVubmVycy9kYXRhZmxvdy93b3JrZXIvdXRpbC9LZXlHcm91cFdvcmtJbmRleC5qYXZh) | 91.30% | [3 Missing and 3 partials :warning: ](https://app.codecov.io/gh/apache/beam/pull/40593?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
   | [...ers/dataflow/worker/util/BoundedQueueExecutor.java](https://app.codecov.io/gh/apache/beam/pull/40593?src=pr&el=tree&filepath=runners%2Fgoogle-cloud-dataflow-java%2Fworker%2Fsrc%2Fmain%2Fjava%2Forg%2Fapache%2Fbeam%2Frunners%2Fdataflow%2Fworker%2Futil%2FBoundedQueueExecutor.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cnVubmVycy9nb29nbGUtY2xvdWQtZGF0YWZsb3ctamF2YS93b3JrZXIvc3JjL21haW4vamF2YS9vcmcvYXBhY2hlL2JlYW0vcnVubmVycy9kYXRhZmxvdy93b3JrZXIvdXRpbC9Cb3VuZGVkUXVldWVFeGVjdXRvci5qYXZh) | 94.44% | [0 Missing and 4 partials :warning: ](https://app.codecov.io/gh/apache/beam/pull/40593?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
   
   <details><summary>Additional details and impacted files</summary>
   
   
   
   ```diff
   @@              Coverage Diff              @@
   ##             master   #40593       +/-   ##
   =============================================
   + Coverage     56.16%   75.98%   +19.81%     
   + Complexity     2288     2286        -2     
   =============================================
     Files          1124      259      -865     
     Lines        178336    14387   -163949     
     Branches       1489     1479       -10     
   =============================================
   - Hits         100170    10932    -89238     
   + Misses        75645     2763    -72882     
   + Partials       2521      692     -1829     
   ```
   
   | [Flag](https://app.codecov.io/gh/apache/beam/pull/40593/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
   |---|---|---|
   | [go](https://app.codecov.io/gh/apache/beam/pull/40593/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
   | [java](https://app.codecov.io/gh/apache/beam/pull/40593/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `75.98% <93.00%> (+0.19%)` | :arrow_up: |
   | [python](https://app.codecov.io/gh/apache/beam/pull/40593/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
   
   Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#carryforward-flags-in-the-pull-request-comment) to find out more.
   </details>
   
   [:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/beam/pull/40593?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).   
   :loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
   <details><summary> :rocket: New features to boost your workflow: </summary>
   
   - :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
   - :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
   </details>


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "arunpandianp (via GitHub)" <gi...@apache.org>.
arunpandianp commented on code in PR #40593:
URL: https://github.com/apache/beam/pull/40593#discussion_r4296946044


##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -403,25 +501,52 @@ BoundedQueueExecutorWorkHandleImpl createBudgetHandle(Work work, long bytes) {
     checkArgument(handle instanceof BoundedQueueExecutorWorkHandleImpl);
     checkStateNotNull(onFailedWorkHandler);
     BoundedQueueExecutorWorkHandleImpl internalHandle = (BoundedQueueExecutorWorkHandleImpl) handle;
-    if (keyGroupWorkQueue == null) {
+    @Nullable KeyGroupWorkIndex index = keyGroupWorkIndex;
+    if (index == null) {
       return null;
     }
     while (true) {
-      @Nullable QueuedWork queuedWork = keyGroupWorkQueue.pollWork(computationId, keyGroup);
-      if (queuedWork == null) {
+      @Nullable QueuedWork stolen = index.pollAndClaim(computationId, keyGroup);
+      if (stolen == null) {
         return null;
       }
-      Work work = queuedWork.getWork().work();
+      ExecutableWork stolenWork = stolen.getWork();
+      BoundedQueueExecutorWorkHandleImpl stolenHandle = stolen.getHandle();
+      stolen.clearClaimedWork();
+      onWorkStolen();
+      Work work = stolenWork.work();
       if (work.isFailed()) {
-        queuedWork.getHandle().close();
+        stolenHandle.close();
         onFailedWorkHandler.onFailedWork(work);
         continue;
       }
-      internalHandle.merge(queuedWork.getHandle());
-      return queuedWork.getWork();
+      internalHandle.merge(stolenHandle);
+      return stolenWork;
     }
   }
 
+  /**
+   * Purges stale shells in bulk if they accumulate while all executor threads are busy running
+   * multi-key bundles.
+   */
+  private void onWorkStolen() {
+    if (workQueue.size() <= (long) elementsOutstanding.get() + maximumElementsOutstanding

Review Comment:
   Updated javadoc.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "scwhittle (via GitHub)" <gi...@apache.org>.
scwhittle commented on code in PR #40593:
URL: https://github.com/apache/beam/pull/40593#discussion_r4292549671


##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -328,49 +346,129 @@ public synchronized void close() {
     }
   }
 
+  /**
+   * A {@link Runnable} for an {@link ExecutableWork} that can be claimed either by an executor
+   * thread in {@link #run} or by a multi-key bundle in {@link #pollWork}.
+   *
+   * <p>Thread safety: {@link #state} is {@code volatile} and transitions at most once from {@link
+   * #QUEUED} to {@link #STARTED} or {@link #STOLEN} via {@link #STATE}{@code .compareAndSet}.
+   * Non-final fields {@link #work} and {@link #handle} are written before {@code state} is
+   * initialized in the constructor, and are subsequently read and cleared only by the single thread
+   * that wins that {@code compareAndSet}. All other accesses read only {@code final} fields or
+   * {@code volatile state}.
+   */
   static final class QueuedWork implements Runnable {
 
-    private final ExecutableWork work;
-    private final BoundedQueueExecutorWorkHandleImpl handle;
-
-    public QueuedWork(ExecutableWork work, BoundedQueueExecutorWorkHandleImpl handle) {
+    private static final int QUEUED = 0;
+    private static final int STARTED = 1; // Claimed by an executor thread in run().
+    private static final int STOLEN = 2; // Claimed by a multi-key bundle in pollWork().
+
+    private static final AtomicIntegerFieldUpdater<QueuedWork> STATE =
+        AtomicIntegerFieldUpdater.newUpdater(QueuedWork.class, "state");
+
+    // Non-null iff the work is eligible to be stolen by a multi-key bundle.
+    private final @Nullable KeyGroupWorkIndex keyGroupWorkIndex;
+    private final KeyGroupWorkIndex.@Nullable QueueKey queueKey;
+    // Cleared upon claim so stale shells and claimed index entries do not retain work references.
+    private @Nullable ExecutableWork work;
+    private @Nullable BoundedQueueExecutorWorkHandleImpl handle;
+    private volatile int state = QUEUED;
+
+    QueuedWork(
+        ExecutableWork work,
+        BoundedQueueExecutorWorkHandleImpl handle,
+        @Nullable KeyGroupWorkIndex keyGroupWorkIndex) {
       this.work = work;
       this.handle = handle;
+      Work w = work.work();
+      if (keyGroupWorkIndex != null
+          && !w.getKeyGroup().equals(Work.KeyGroup.DEFAULT)
+          && !w.isMultiKeyBatchingDisabled()) {
+        this.keyGroupWorkIndex = keyGroupWorkIndex;
+        this.queueKey = new KeyGroupWorkIndex.QueueKey(w.getComputationId(), w.getKeyGroup());
+      } else {
+        this.keyGroupWorkIndex = null;
+        this.queueKey = null;
+      }
     }
 
     public ExecutableWork getWork() {

Review Comment:
   I think that this and getHandle are maybe only used by the other methods and could be removed?
   See if other methods could be made private or removed as well.



##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -403,25 +501,52 @@ BoundedQueueExecutorWorkHandleImpl createBudgetHandle(Work work, long bytes) {
     checkArgument(handle instanceof BoundedQueueExecutorWorkHandleImpl);
     checkStateNotNull(onFailedWorkHandler);
     BoundedQueueExecutorWorkHandleImpl internalHandle = (BoundedQueueExecutorWorkHandleImpl) handle;
-    if (keyGroupWorkQueue == null) {
+    @Nullable KeyGroupWorkIndex index = keyGroupWorkIndex;
+    if (index == null) {
       return null;
     }
     while (true) {
-      @Nullable QueuedWork queuedWork = keyGroupWorkQueue.pollWork(computationId, keyGroup);
-      if (queuedWork == null) {
+      @Nullable QueuedWork stolen = index.pollAndClaim(computationId, keyGroup);
+      if (stolen == null) {
         return null;
       }
-      Work work = queuedWork.getWork().work();
+      ExecutableWork stolenWork = stolen.getWork();
+      BoundedQueueExecutorWorkHandleImpl stolenHandle = stolen.getHandle();
+      stolen.clearClaimedWork();
+      onWorkStolen();
+      Work work = stolenWork.work();
       if (work.isFailed()) {
-        queuedWork.getHandle().close();
+        stolenHandle.close();
         onFailedWorkHandler.onFailedWork(work);
         continue;
       }
-      internalHandle.merge(queuedWork.getHandle());
-      return queuedWork.getWork();
+      internalHandle.merge(stolenHandle);
+      return stolenWork;
     }
   }
 
+  /**
+   * Purges stale shells in bulk if they accumulate while all executor threads are busy running
+   * multi-key bundles.
+   */
+  private void onWorkStolen() {
+    if (workQueue.size() <= (long) elementsOutstanding.get() + maximumElementsOutstanding

Review Comment:
   could we remove checking elementsOutstanding and revert changing it to an atomic?
   
   seems like we could just use
   workQueue.size() < 2 * maximumElementsOutstanding
   
   That seems like it woudl trigger only if maximumElementsOutstanding stale entries are there



##########
runners/google-cloud-dataflow-java/worker/src/test/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutorTest.java:
##########
@@ -742,25 +688,26 @@ public void testPollWork_purgeBacksOffWhileQueueHoldsMostlyUnstartedWork() throw
           createWorkWithCompIdAndKeyGroup("compA", keyGroup, ignored -> {}), 10);
     }
 
-    // The first steal purges its own stale shell; the remaining steals back off until the queue
-    // grows by more than maximumElementsOutstanding.
-    for (int i = 0; i < numWorks; i++) {
-      assertNotNull(
-          testExecutor.pollWork("compA", keyGroup, stealHandle, FAILING_FAILED_WORK_HANDLER));
-    }
-    assertEquals(numWorks - 1, testExecutor.executorQueueSize());
-
-    for (int i = 0; i <= maximumElementsOutstanding; i++) {
-      testExecutor.forceExecute(
-          createWorkWithCompIdAndKeyGroup("compA", keyGroup, ignored -> {}), 10);
+    // Each steal leaves a stale shell in the executor queue. While bundle1 is open, its stolen
+    // work is still counted in elementsOutstanding, so there is nothing to purge.
+    int numStolenByBundle1 = maximumElementsOutstanding + 2;
+    for (int i = 0; i < numStolenByBundle1; i++) {
+      assertNotNull(testExecutor.pollWork("compA", keyGroup, bundle1, FAILING_FAILED_WORK_HANDLER));
     }
-    assertNotNull(
-        testExecutor.pollWork("compA", keyGroup, stealHandle, FAILING_FAILED_WORK_HANDLER));
-    assertEquals(maximumElementsOutstanding, testExecutor.executorQueueSize());
+    assertEquals(numWorks, testExecutor.rawQueueSizeForTesting());

Review Comment:
   can we verify elementsOutstanding here and below not just the rawQeueuSize?



##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########


Review Comment:
   how about getQueueKey? at call-sites it is confusing with performing queuing action



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "scwhittle (via GitHub)" <gi...@apache.org>.
scwhittle commented on code in PR #40593:
URL: https://github.com/apache/beam/pull/40593#discussion_r4280641824


##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -185,6 +200,18 @@ public boolean executorQueueIsEmpty() {
     return executor.getQueue().isEmpty();

Review Comment:
   maybe this should be 
   `workQueue.isEmpty() || executorQueueSize() == 0` if the size is changed to be correct



##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/KeyGroupWorkIndex.java:
##########
@@ -0,0 +1,175 @@
+/*
+ * 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.beam.runners.dataflow.worker.util;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import javax.annotation.concurrent.ThreadSafe;
+import org.apache.beam.runners.dataflow.worker.streaming.Work;
+import org.apache.beam.runners.dataflow.worker.util.BoundedQueueExecutor.QueuedWork;
+import org.apache.beam.vendor.guava.v32_1_2_jre.com.google.common.annotations.VisibleForTesting;
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+/**
+ * Sharded FIFO index of {@link QueuedWork} by computation and {@link Work.KeyGroup} for work
+ * stealing by multi-key bundles.
+ */
+@ThreadSafe
+final class KeyGroupWorkIndex {
+
+  private static final int NUM_SHARDS = 64;
+  private static final int INITIAL_QUEUE_CAPACITY = 4;
+
+  // Each shard map and its queues are guarded by synchronized (shard).
+  private final List<Map<QueueKey, ArrayDeque<QueuedWork>>> shards;
+
+  KeyGroupWorkIndex() {
+    List<Map<QueueKey, ArrayDeque<QueuedWork>>> list = new ArrayList<>(NUM_SHARDS);
+    for (int i = 0; i < NUM_SHARDS; i++) {
+      list.add(new HashMap<>());
+    }
+    this.shards = Collections.unmodifiableList(list);

Review Comment:
   how about ImmutableList instead of wrapping arraylist?



##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/KeyGroupWorkIndex.java:
##########
@@ -0,0 +1,175 @@
+/*
+ * 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.beam.runners.dataflow.worker.util;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import javax.annotation.concurrent.ThreadSafe;
+import org.apache.beam.runners.dataflow.worker.streaming.Work;
+import org.apache.beam.runners.dataflow.worker.util.BoundedQueueExecutor.QueuedWork;
+import org.apache.beam.vendor.guava.v32_1_2_jre.com.google.common.annotations.VisibleForTesting;
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+/**
+ * Sharded FIFO index of {@link QueuedWork} by computation and {@link Work.KeyGroup} for work
+ * stealing by multi-key bundles.
+ */
+@ThreadSafe
+final class KeyGroupWorkIndex {
+
+  private static final int NUM_SHARDS = 64;
+  private static final int INITIAL_QUEUE_CAPACITY = 4;
+
+  // Each shard map and its queues are guarded by synchronized (shard).
+  private final List<Map<QueueKey, ArrayDeque<QueuedWork>>> shards;
+
+  KeyGroupWorkIndex() {
+    List<Map<QueueKey, ArrayDeque<QueuedWork>>> list = new ArrayList<>(NUM_SHARDS);
+    for (int i = 0; i < NUM_SHARDS; i++) {
+      list.add(new HashMap<>());
+    }
+    this.shards = Collections.unmodifiableList(list);
+  }
+
+  private Map<QueueKey, ArrayDeque<QueuedWork>> shardFor(QueueKey queueKey) {
+    return shards.get(Math.floorMod(queueKey.hashCode(), NUM_SHARDS));
+  }
+
+  /** Adds {@code work} to its key-group queue if it has not been claimed yet. */
+  void add(QueuedWork work) {
+    if (work.isClaimed()) {
+      return;
+    }
+    QueueKey queueKey = work.queueKey();
+    Map<QueueKey, ArrayDeque<QueuedWork>> shard = shardFor(queueKey);
+    synchronized (shard) {
+      if (work.isClaimed()) {
+        return;
+      }
+      ArrayDeque<QueuedWork> queue =
+          shard.computeIfAbsent(queueKey, unused -> new ArrayDeque<>(INITIAL_QUEUE_CAPACITY));

Review Comment:
   should we just create these queues in the constructor? simpler hot-path and not much overhead for 64 empty queues



##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutor.java:
##########
@@ -185,6 +200,18 @@ public boolean executorQueueIsEmpty() {
     return executor.getQueue().isEmpty();
   }
 
+  /** Returns the number of entries in the executor queue, including stale shells. */

Review Comment:
   can we keep track of the stale shell count without removing them so that this reflects the actual queued work without the stale shells?
   
   I'm worried that this might confuse budgeting.



##########
runners/google-cloud-dataflow-java/worker/src/main/java/org/apache/beam/runners/dataflow/worker/util/KeyGroupWorkIndex.java:
##########
@@ -0,0 +1,175 @@
+/*
+ * 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.beam.runners.dataflow.worker.util;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import javax.annotation.concurrent.ThreadSafe;
+import org.apache.beam.runners.dataflow.worker.streaming.Work;
+import org.apache.beam.runners.dataflow.worker.util.BoundedQueueExecutor.QueuedWork;
+import org.apache.beam.vendor.guava.v32_1_2_jre.com.google.common.annotations.VisibleForTesting;
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+/**
+ * Sharded FIFO index of {@link QueuedWork} by computation and {@link Work.KeyGroup} for work
+ * stealing by multi-key bundles.
+ */
+@ThreadSafe
+final class KeyGroupWorkIndex {
+
+  private static final int NUM_SHARDS = 64;
+  private static final int INITIAL_QUEUE_CAPACITY = 4;
+
+  // Each shard map and its queues are guarded by synchronized (shard).
+  private final List<Map<QueueKey, ArrayDeque<QueuedWork>>> shards;
+
+  KeyGroupWorkIndex() {
+    List<Map<QueueKey, ArrayDeque<QueuedWork>>> list = new ArrayList<>(NUM_SHARDS);
+    for (int i = 0; i < NUM_SHARDS; i++) {
+      list.add(new HashMap<>());
+    }
+    this.shards = Collections.unmodifiableList(list);
+  }
+
+  private Map<QueueKey, ArrayDeque<QueuedWork>> shardFor(QueueKey queueKey) {
+    return shards.get(Math.floorMod(queueKey.hashCode(), NUM_SHARDS));
+  }
+
+  /** Adds {@code work} to its key-group queue if it has not been claimed yet. */
+  void add(QueuedWork work) {
+    if (work.isClaimed()) {
+      return;
+    }
+    QueueKey queueKey = work.queueKey();
+    Map<QueueKey, ArrayDeque<QueuedWork>> shard = shardFor(queueKey);
+    synchronized (shard) {
+      if (work.isClaimed()) {
+        return;
+      }
+      ArrayDeque<QueuedWork> queue =
+          shard.computeIfAbsent(queueKey, unused -> new ArrayDeque<>(INITIAL_QUEUE_CAPACITY));
+      drainClaimedFromHead(queue);
+      queue.addLast(work);
+    }
+  }
+
+  /**
+   * Drains claimed work from the head of {@code work}'s key-group queue. If an earlier item is
+   * still unclaimed, {@code work} remains in the queue with its references cleared and is drained
+   * in amortized O(1) time once the earlier item is claimed.
+   */
+  void remove(QueuedWork work) {

Review Comment:
   this is a confusing method name when queue can still contain work after it returns.  Should we be marking work as claimed so it won't be returned after this?



##########
runners/google-cloud-dataflow-java/worker/src/test/java/org/apache/beam/runners/dataflow/worker/util/BoundedQueueExecutorTest.java:
##########
@@ -693,9 +602,291 @@ public void testPollWork_skipsFailedWorkAndCallsOnFailedWorkHandler() throws Exc
     assertNull(testExecutor.pollWork("compA", keyGroup, stealHandle, onFailedWorkHandler));
 
     blockerStop.countDown();
+    testExecutor.shutdown();
+    assertEquals(0, testExecutor.elementsOutstanding());
+    assertEquals(0, testExecutor.bytesOutstanding());
+  }
+
+  @Test
+  public void testPollWork_stolenWorkLeavesNoOpStaleShell() throws Exception {

Review Comment:
   the test name makes it sound like we want a stale shell,  I think we should combine what this verifies into testPollWork (and ideally make it so the impl detail of stale shells isn't visible in the queue size)



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #40593:
URL: https://github.com/apache/beam/pull/40593#issuecomment-6177948363

   Stopping reviewer notifications for this pull request: review requested by someone other than the bot, ceding control. If you'd like to restart, comment `assign set of reviewers`


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "arunpandianp (via GitHub)" <gi...@apache.org>.
arunpandianp commented on PR #40593:
URL: https://github.com/apache/beam/pull/40593#issuecomment-6177909130

   R: @scwhittle 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


Re: [PR] [Multikey] [Dataflow Streaming] Replace KeyGroupWorkQueue with a sharded KeyGroupIndex [beam]

Posted by "derrickaw (via GitHub)" <gi...@apache.org>.
derrickaw merged PR #40593:
URL: https://github.com/apache/beam/pull/40593


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@beam.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org