scwhittle commented on code in PR #41468:
URL: https://github.com/apache/beam/pull/41468#discussion_r4628146346


##########
sdks/java/core/src/main/java/org/apache/beam/sdk/transforms/DoFnTester.java:
##########
@@ -548,18 +548,40 @@ public void output(OutputT output, Instant timestamp, 
BoundedWindow window) {
 
         @Override
         public <T> void output(TupleTag<T> tag, T output, Instant timestamp, 
BoundedWindow window) {
-          getMutableOutput(tag)
-              .add(
-                  ValueInSingleWindow.of(
-                      output,
-                      timestamp,
-                      window,
-                      PaneInfo.NO_FIRING,
-                      null,
-                      null,
-                      CausedByDrain.NORMAL,
-                      null,
-                      ValueKind.INSERT));
+          outputWindowedValue(
+              tag, output, timestamp, Collections.singletonList(window), 
PaneInfo.NO_FIRING);
+        }
+
+        @Override
+        public void outputWindowedValue(
+            OutputT output,
+            Instant timestamp,
+            Collection<? extends BoundedWindow> windows,
+            PaneInfo paneInfo) {
+          outputWindowedValue(mainOutputTag, output, timestamp, windows, 
paneInfo);
+        }
+
+        @Override
+        public <T> void outputWindowedValue(
+            TupleTag<T> tag,
+            T output,
+            Instant timestamp,
+            Collection<? extends BoundedWindow> windows,
+            PaneInfo paneInfo) {
+          List<ValueInSingleWindow<T>> outputs = getMutableOutput(tag);
+          for (BoundedWindow window : windows) {
+            outputs.add(
+                ValueInSingleWindow.of(

Review Comment:
   this behavior seems odd.  Can you either enforce it is a single window since 
this is just for testing support or pass through all the windows?



##########
sdks/java/core/src/main/java/org/apache/beam/sdk/transforms/DoFn.java:
##########
@@ -136,6 +136,43 @@ public abstract class FinishBundleContext {
      */
     public abstract <T> void output(
         TupleTag<T> tag, T output, Instant timestamp, BoundedWindow window);
+
+    /**
+     * Adds the given element to the main output {@code PCollection} at the 
given timestamp, in the
+     * given windows, and with the given {@link PaneInfo}.
+     *
+     * <p>Once passed to {@code outputWindowedValue} the element should not be 
modified in any way.
+     *
+     * <p><i>Note:</i> A splittable {@link DoFn} is not allowed to output from 
the {@link
+     * FinishBundle} method.
+     */
+    public void outputWindowedValue(

Review Comment:
   this should be separate PR
   
   We should have Kenn and Radek review.  
   
   I'm curious if we should have version that allows outputting a WindowedValue 
directly as well as a way to consume WindowedValue directly in processElement 
(instead of binding separate window/pane etc params). There are other things 
within the WindowedValue that we are not currently propagating through and this 
BundleLifterDoFn is supposed to be a pass-through.



##########
sdks/java/core/src/main/java/org/apache/beam/sdk/util/BundleLifter.java:
##########
@@ -57,89 +90,316 @@ public class BundleLifter<T> extends 
PTransform<PCollection<T>, PCollectionTuple
 
   final TupleTag<T> smallBatchTag;
   final TupleTag<T> largeBatchTag;
-  final int threshold;
+  final long threshold;
+  final long maxBufferedBytes;
+  final int maxLiftedKeys;
   final SerializableFunction<T, Integer> elementSizer;
+  final @Nullable SerializableFunction<T, ? extends @Nullable Object> keyFn;
+
+  /** The default memory cap: twice the threshold. */
+  static long defaultMaxBufferedBytes(long threshold) {
+    return threshold > Long.MAX_VALUE / 2 ? Long.MAX_VALUE : 2 * threshold;
+  }
 
   /**
-   * A DoFn that buffers elements within a bundle and outputs them to 
different tags in
-   * finish_bundle based on the total bundle size.
+   * A DoFn that buffers elements per key within a bundle and outputs them to 
the large tag once a
+   * key reaches the threshold, or to the small tag otherwise.
    *
    * @param <T> The type of elements being processed.
    */
   static class BundleLiftDoFn<T> extends DoFn<T, Void> {
     private static final Logger LOG = 
LoggerFactory.getLogger(BundleLiftDoFn.class);
 
+    /** The key shared by all elements without a key, or whose key function 
returns null. */
+    private static final Object UNKEYED = new Object();
+
     final TupleTag<T> smallBatchTag;
     final TupleTag<T> largeBatchTag;
-    final int threshold;
+    final long threshold;
+    final long maxBufferedBytes;
+    final int maxLiftedKeys;
     final SerializableFunction<T, Integer> elementSizer;
+    final @Nullable SerializableFunction<T, ? extends @Nullable Object> keyFn;
 
-    private transient @MonotonicNonNull List<T> buffer;
-    private transient long bundleSizeBytes;
-    private transient @Nullable MultiOutputReceiver receiver;
+    // Per-bundle state, allocated once in setup and cleared at the start of 
each bundle.
+    private transient @MonotonicNonNull Map<Object, KeyBuffer<T>> buffers;
+    private transient @MonotonicNonNull Set<Object> liftedKeys;
+    // Reset in startBundle; not transient so SpotBugs doesn't flag them as 
unrestored state.
+    private long bufferedBytes;
+    // Set once the memory cap is exceeded or the lifted key limit is reached 
in this bundle: keys
+    // that are neither buffered nor lifted are no longer tracked and go to 
the small output
+    // immediately.
+    private boolean keysFinalized;
 
     BundleLiftDoFn(
         TupleTag<T> smallBatchTag,
         TupleTag<T> largeBatchTag,
-        int threshold,
-        SerializableFunction<T, Integer> elementSizer) {
+        long threshold,
+        long maxBufferedBytes,
+        int maxLiftedKeys,
+        SerializableFunction<T, Integer> elementSizer,
+        @Nullable SerializableFunction<T, ? extends @Nullable Object> keyFn) {
       this.smallBatchTag = smallBatchTag;
       this.largeBatchTag = largeBatchTag;
       this.threshold = threshold;
+      this.maxBufferedBytes = maxBufferedBytes;
+      this.maxLiftedKeys = maxLiftedKeys;
       this.elementSizer = elementSizer;
+      this.keyFn = keyFn;
+    }
+
+    @Setup
+    public void setup() {
+      buffers = new LinkedHashMap<>();
+      liftedKeys = new HashSet<>();
     }
 
     @StartBundle
     public void startBundle() {
-      buffer = new ArrayList<>();
-      receiver = null;
-      bundleSizeBytes = 0L;
+      checkStateNotNull(buffers, "Buffers should be set by setup.").clear();
+      checkStateNotNull(liftedKeys, "Lifted keys should be set by 
setup.").clear();
+      bufferedBytes = 0L;
+      keysFinalized = false;
     }
 
     @ProcessElement
-    public void processElement(@Element T element, MultiOutputReceiver mor) {
-      if (receiver == null) {
-        receiver = mor;
+    public void processElement(
+        @Element T element,
+        @Timestamp Instant timestamp,
+        BoundedWindow window,
+        PaneInfo pane,
+        MultiOutputReceiver receiver) {
+      Map<Object, KeyBuffer<T>> buffers =
+          checkStateNotNull(this.buffers, "Buffers should be set by setup.");
+      Set<Object> liftedKeys =
+          checkStateNotNull(this.liftedKeys, "Lifted keys should be set by 
setup.");
+
+      Object key;
+      if (keyFn == null) {
+        key = UNKEYED;
+      } else {
+        @Nullable Object userKey = keyFn.apply(element);
+        key = new WindowedKey(window, pane, userKey == null ? UNKEYED : 
userKey);

Review Comment:
   Timestamps makes sense, I'm fine just leaving as is.  However I do think we 
should change WriteFiles to have bundle lifter be on KV<dest, value> and then 
the keyfn can just be KV.key()



##########
sdks/java/core/src/main/java/org/apache/beam/sdk/util/BundleLifter.java:
##########
@@ -57,89 +90,313 @@ public class BundleLifter<T> extends 
PTransform<PCollection<T>, PCollectionTuple
 
   final TupleTag<T> smallBatchTag;
   final TupleTag<T> largeBatchTag;
-  final int threshold;
+  // Once a key reaches this threshold all elements for the key are output to 
largeBatchTag.
+  final long threshold;
+  final long maxBufferedBytes;
+  final int maxLiftedKeys;
   final SerializableFunction<T, Integer> elementSizer;
+  final @Nullable SerializableFunction<T, ? extends @Nullable Object> keyFn;
+
+  static long defaultMaxBufferedBytes(long threshold) {
+    return threshold > Long.MAX_VALUE / 2 ? Long.MAX_VALUE : 2 * threshold;
+  }
 
   /**
-   * A DoFn that buffers elements within a bundle and outputs them to 
different tags in
-   * finish_bundle based on the total bundle size.
+   * A DoFn that buffers elements per key within a bundle and outputs them to 
the large tag once a
+   * key reaches the threshold, or to the small tag otherwise.
    *
    * @param <T> The type of elements being processed.
    */
   static class BundleLiftDoFn<T> extends DoFn<T, Void> {
     private static final Logger LOG = 
LoggerFactory.getLogger(BundleLiftDoFn.class);
 
+    /** The key shared by all elements without a key, or whose key function 
returns null. */
+    private static final Object UNKEYED = new Object();
+
     final TupleTag<T> smallBatchTag;
     final TupleTag<T> largeBatchTag;
-    final int threshold;
+    // Once a key reaches this threshold all elements for the key are output 
to largeBatchTag.
+    final long threshold;
+    final long maxBufferedBytes;
+    final int maxLiftedKeys;
     final SerializableFunction<T, Integer> elementSizer;
+    final @Nullable SerializableFunction<T, ? extends @Nullable Object> keyFn;
 
-    private transient @MonotonicNonNull List<T> buffer;
-    private transient long bundleSizeBytes;
-    private transient @Nullable MultiOutputReceiver receiver;
+    // Per-bundle state, allocated once in setup and cleared at the start of 
each bundle.
+    private transient @MonotonicNonNull Map<WindowedKey, KeyBuffer<T>> buffers;
+    // Keys which have been emitted to the largeBatchTag and for which future 
elements should also
+    // be routed to the largeBatchTag.
+    private transient @MonotonicNonNull Set<WindowedKey> liftedKeys;
+    // Reset in startBundle.
+    private long bufferedBytes;
+    // Set once the memory cap is exceeded or the lifted key limit is reached 
in this bundle: keys
+    // that are neither buffered nor lifted are no longer tracked and go to 
the small output
+    // immediately.
+    private boolean keysFinalized;
 
     BundleLiftDoFn(
         TupleTag<T> smallBatchTag,
         TupleTag<T> largeBatchTag,
-        int threshold,
-        SerializableFunction<T, Integer> elementSizer) {
+        long threshold,
+        long maxBufferedBytes,
+        int maxLiftedKeys,
+        SerializableFunction<T, Integer> elementSizer,
+        @Nullable SerializableFunction<T, ? extends @Nullable Object> keyFn) {
       this.smallBatchTag = smallBatchTag;
       this.largeBatchTag = largeBatchTag;
       this.threshold = threshold;
+      this.maxBufferedBytes = maxBufferedBytes;
+      this.maxLiftedKeys = maxLiftedKeys;
       this.elementSizer = elementSizer;
+      this.keyFn = keyFn;
+    }
+
+    @Setup
+    public void setup() {
+      buffers = new HashMap<>();
+      liftedKeys = new HashSet<>();
     }
 
     @StartBundle
     public void startBundle() {
-      buffer = new ArrayList<>();
-      receiver = null;
-      bundleSizeBytes = 0L;
+      checkStateNotNull(buffers, "Buffers should be set by setup.").clear();
+      checkStateNotNull(liftedKeys, "Lifted keys should be set by 
setup.").clear();
+      bufferedBytes = 0L;
+      keysFinalized = false;
     }
 
     @ProcessElement
-    public void processElement(@Element T element, MultiOutputReceiver mor) {
-      if (receiver == null) {
-        receiver = mor;
+    public void processElement(
+        @Element T element,
+        @Timestamp Instant timestamp,
+        BoundedWindow window,
+        PaneInfo pane,
+        MultiOutputReceiver receiver) {
+      Map<WindowedKey, KeyBuffer<T>> buffers =
+          checkStateNotNull(this.buffers, "Buffers should be set by setup.");
+      Set<WindowedKey> liftedKeys =
+          checkStateNotNull(this.liftedKeys, "Lifted keys should be set by 
setup.");
+
+      @Nullable Object userKey = keyFn == null ? null : keyFn.apply(element);
+      WindowedKey key = new WindowedKey(window, pane, userKey == null ? 
UNKEYED : userKey);
+
+      if (liftedKeys.contains(key)) {
+        // This key already reached the threshold in this bundle; stream it 
through.
+        receiver
+            .get(largeBatchTag)
+            .outputWindowedValue(element, timestamp, 
Collections.singletonList(window), pane);
+        return;
+      }
+
+      KeyBuffer<T> buffer = buffers.get(key);
+      if (buffer == null) {
+        if (keysFinalized) {
+          // The memory cap was exceeded earlier in this bundle; don't track 
new keys.
+          receiver
+              .get(smallBatchTag)
+              .outputWindowedValue(element, timestamp, 
Collections.singletonList(window), pane);
+          return;
+        }
+        buffer = new KeyBuffer<>();
+        buffers.put(key, buffer);
+      }
+      long elementBytes = elementSizer.apply(element);
+      buffer.add(new BufferedElement<>(element, timestamp, window, pane), 
elementBytes);
+      bufferedBytes += elementBytes;
+
+      if (buffer.sizeBytes >= threshold) {
+        buffers.remove(key);
+        bufferedBytes -= buffer.sizeBytes;
+        liftedKeys.add(key);
+        LOG.debug(
+            "Key reached {} estimated bytes; emitting {} buffered elements to 
tag: '{}'",
+            buffer.sizeBytes,
+            buffer.elements.size(),
+            largeBatchTag.getId());
+        emit(buffer, receiver.get(largeBatchTag));
+        buffer.elements.clear();
+        if (liftedKeys.size() >= maxLiftedKeys) {
+          // No other key can be lifted in this bundle; release the remaining 
buffers.
+          keysFinalized = true;
+          OutputReceiver<T> small = receiver.get(smallBatchTag);
+          Iterator<KeyBuffer<T>> it = buffers.values().iterator();
+          while (it.hasNext()) {
+            KeyBuffer<T> other = it.next();
+            it.remove();
+            emit(other, small);
+            other.elements.clear();
+          }
+          bufferedBytes = 0L;
+        }
+        return;
+      }
+
+      // Anything that isn't in lifted keys or buffers is sent to small keys 
immediately.
+      if (bufferedBytes > maxBufferedBytes) {
+        keysFinalized = true;
+        evictSmallestKeys(buffers, receiver.get(smallBatchTag));
       }
-      checkArgumentNotNull(buffer, "Buffer should be set by startBundle.");
-      buffer.add(element);
-      bundleSizeBytes += elementSizer.apply(element);
     }
 
     @FinishBundle
-    public void finishBundle() {
-      checkArgumentNotNull(buffer, "Buffer should be set by startBundle.");
-      if (buffer.isEmpty()) {
-        return;
+    public void finishBundle(FinishBundleContext context) {
+      Map<WindowedKey, KeyBuffer<T>> buffers =
+          checkStateNotNull(this.buffers, "Buffers should be set by setup.");
+      Iterator<KeyBuffer<T>> it = buffers.values().iterator();
+      while (it.hasNext()) {
+        KeyBuffer<T> buffer = it.next();
+        it.remove();
+        LOG.debug(
+            "Emitting {} elements of {} estimated bytes to tag: '{}'",
+            buffer.elements.size(),
+            buffer.sizeBytes,
+            smallBatchTag.getId());
+        for (BufferedElement<T> e : buffer.elements) {
+          context.outputWindowedValue(
+              smallBatchTag, e.value, e.timestamp, 
Collections.singletonList(e.window), e.pane);
+        }
+        buffer.elements.clear();
+      }
+      checkStateNotNull(this.liftedKeys).clear();
+      bufferedBytes = 0L;
+      keysFinalized = false;
+    }
+
+    /**
+     * Buffered elements are re-emitted from {@link ProcessElement} with their 
own timestamps, which
+     * may be earlier than the current element's. This is safe because they 
belong to the same
+     * bundle, so the input watermark is still held at or before them.
+     */
+    @Override
+    public Duration getAllowedTimestampSkew() {
+      return Duration.millis(Long.MAX_VALUE);
+    }
+
+    /**
+     * Emits the smallest keys to the small output until at most half of 
{@code maxBufferedBytes}
+     * remains buffered (keeping at least one key so it can still reach {@code 
threshold}), so each
+     * call frees a large chunk and the sort's cost stays amortized.
+     */
+    private void evictSmallestKeys(
+        Map<WindowedKey, KeyBuffer<T>> buffers, OutputReceiver<T> small) {
+      long target = maxBufferedBytes / 2;
+      List<Map.Entry<WindowedKey, KeyBuffer<T>>> bySize = new 
ArrayList<>(buffers.entrySet());
+      bySize.sort(Comparator.comparingLong(entry -> 
entry.getValue().sizeBytes));
+      for (Map.Entry<WindowedKey, KeyBuffer<T>> entry : bySize) {
+        if (bufferedBytes <= target || buffers.size() <= 1) {
+          break;
+        }
+        KeyBuffer<T> buffer = entry.getValue();
+        buffers.remove(entry.getKey());
+        bufferedBytes -= buffer.sizeBytes;
+        emit(buffer, small);
+        buffer.elements.clear();
+      }
+    }
+
+    private static <T> void emit(KeyBuffer<T> buffer, OutputReceiver<T> 
receiver) {
+      for (BufferedElement<T> e : buffer.elements) {
+        receiver.outputWindowedValue(
+            e.value, e.timestamp, Collections.singletonList(e.window), e.pane);
+      }
+    }
+  }
+
+  /** The buffered elements of one key, in arrival order. */
+  private static class KeyBuffer<T> {
+    private final List<BufferedElement<T>> elements = new ArrayList<>();
+    private long sizeBytes;
+
+    void add(BufferedElement<T> element, long elementBytes) {
+      elements.add(element);
+      sizeBytes += elementBytes;
+    }
+  }
+
+  /** A buffered element with the metadata needed to re-emit it. */
+  private static class BufferedElement<T> {
+    private final T value;
+    private final Instant timestamp;
+    private final BoundedWindow window;
+    private final PaneInfo pane;
+
+    BufferedElement(T value, Instant timestamp, BoundedWindow window, PaneInfo 
pane) {
+      this.value = value;
+      this.timestamp = timestamp;
+      this.window = window;
+      this.pane = pane;
+    }
+  }
+
+  /** A user key scoped to a window and pane. */
+  private static class WindowedKey {
+    private final BoundedWindow window;
+    private final PaneInfo pane;
+    private final Object key;
+
+    WindowedKey(BoundedWindow window, PaneInfo pane, Object key) {
+      this.window = window;
+      this.pane = pane;
+      this.key = key;
+    }
+
+    @Override
+    public boolean equals(@Nullable Object o) {
+      if (this == o) {
+        return true;
       }
+      if (!(o instanceof WindowedKey)) {
+        return false;
+      }
+      WindowedKey other = (WindowedKey) o;
+      return window.equals(other.window) && pane.equals(other.pane) && 
key.equals(other.key);
+    }
 
-      // Select the target tag based on the bundle size
-      TupleTag<T> targetTag;
-      targetTag = (bundleSizeBytes < threshold) ? smallBatchTag : 
largeBatchTag;
-      LOG.debug(
-          "Emitting {} elements of {} estimated bytes to tag: '{}'",
-          buffer.size(),
-          bundleSizeBytes,
-          targetTag.getId());
+    @Override
+    public int hashCode() {
+      return Objects.hash(window, pane, key);

Review Comment:
   could calculate this once and memorize it, just returning here and then also 
adding it as fast difference in equals.  Since keys could be large and we are 
using this in several maps.



-- 
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: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to