[GitHub] [beam] dmvk commented on a change in pull request #11533: [BEAM-9827] Ensure minimum watermark hold is computed across all keys

[GitBox <gi...@apache.org>]

dmvk commented on a change in pull request #11533:
URL: https://github.com/apache/beam/pull/11533#discussion_r415735715



##########
File path: runners/flink/src/main/java/org/apache/beam/runners/flink/translation/wrappers/streaming/state/FlinkStateInternals.java
##########
@@ -76,8 +76,8 @@
   private final KeyedStateBackend<ByteBuffer> flinkStateBackend;
   private Coder<K> keyCoder;
 
-  // Combined watermark holds for all keys of this partition
-  private final Map<String, Instant> watermarkHolds = new HashMap<>();
+  // Watermark holds for all keys/windows of this partition
+  private final PriorityQueue<Long> watermarkHolds = new PriorityQueue<>();

Review comment:
       To sum up if I understand this correctly
   - We only need to keep a single value (the minimum)
   - We can not use scalar value that would hold the minimum, because we need a mutable wrapper
   
   in this case can we only keep the minimum value in order to have O(log N) complexity? eg.:
   ```
   void insertAndKeepMinimum(PriorityQueue<T> pq, T element) {
     pq.insert(element)
     while(pq.size() > 1) {
       pq.remove();
     }
   }
   ```
   
   `pq.remove(T ...)` has linear time complexity




----------------------------------------------------------------
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.

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