You are viewing a plain text version of this content. The canonical link for it is here.
Posted to jira@kafka.apache.org by GitBox <gi...@apache.org> on 2020/08/07 16:22:42 UTC

[GitHub] [kafka] jeqo opened a new pull request #9138: Backward windowstore

jeqo opened a new pull request #9138:
URL: https://github.com/apache/kafka/pull/9138


   Depends on https://github.com/apache/kafka/pull/9137
   
   *More detailed description of your change,
   if necessary. The PR title and PR message become
   the squashed commit message, so use a separate
   comment to ping reviewers.*
   
   *Summary of testing strategy (including rationale)
   for the feature or bug fix. Unit and/or integration
   tests are expected for any behaviour change and
   system tests should be considered for larger changes.*
   
   ### Committer Checklist (excluded from commit message)
   - [ ] Verify design and implementation 
   - [ ] Verify test coverage and CI build status
   - [ ] Verify documentation (including upgrade notes)
   


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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r482160859



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/ReadOnlyWindowStore.java
##########
@@ -136,34 +174,64 @@
      * <p>
      * This iterator must be closed after use.
      *
-     * @param from      the first key in the range
-     * @param to        the last key in the range
-     * @param fromTime  time range start (inclusive)
-     * @param toTime    time range end (inclusive)
-     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive), where iteration starts.
+     * @param timeTo   time range end (inclusive), where iteration ends.
+     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}, from beginning to end of time.
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException If {@code null} is used for any key.
-     * @throws IllegalArgumentException if duration is negative or can't be represented as {@code long milliseconds}
+     * @throws NullPointerException       If {@code null} is used for any key.
+     * @throws IllegalArgumentException   if duration is negative or can't be represented as {@code long milliseconds}
      */
-    KeyValueIterator<Windowed<K>, V> fetch(K from, K to, Instant fromTime, Instant toTime)
+    KeyValueIterator<Windowed<K>, V> fetch(K from, K to, Instant timeFrom, Instant timeTo)
         throws IllegalArgumentException;
 
     /**
-    * Gets all the key-value pairs in the existing windows.
-    *
-    * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
-    * @throws InvalidStateStoreException if the store is not initialized
-    */
+     * Get all the key-value pairs in the given key range and time range from all the existing windows
+     * in backward order with respect to time (from end to beginning of time).
+     * <p>
+     * This iterator must be closed after use.
+     *
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive), where iteration ends.
+     * @param timeTo   time range end (inclusive), where iteration starts.
+     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}, from end to beginning of time.
+     * @throws InvalidStateStoreException if the store is not initialized
+     * @throws NullPointerException       If {@code null} is used for any key.
+     * @throws IllegalArgumentException   if duration is negative or can't be represented as {@code long milliseconds}
+     */
+    KeyValueIterator<Windowed<K>, V> backwardFetch(K from, K to, Instant timeFrom, Instant timeTo)

Review comment:
       https://github.com/apache/kafka/pull/9137#discussion_r468852245 old discussion for context.
   
   @guozhangwang is this scenario only possible with composite stores? or are there other implementations where this is an alternative path?




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r478769493



##########
File path: streams/src/test/java/org/apache/kafka/streams/state/internals/AbstractWindowBytesStoreTest.java
##########
@@ -287,17 +308,43 @@ public void shouldFetchAllInTimeRange() {
         final KeyValue<Windowed<Integer>, String> four = windowedPair(4, "four", startTime + 4);
         final KeyValue<Windowed<Integer>, String> five = windowedPair(5, "five", startTime + 5);
 
-        assertEquals(
-            new HashSet<>(asList(one, two, four)),
-            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 1), ofEpochMilli(startTime + 4)))
+        assertArrayEquals(
+            new LinkedHashSet<>(asList(one, two, four)).toArray(),
+            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 1), ofEpochMilli(startTime + 4))).toArray()
         );
-        assertEquals(
-            new HashSet<>(asList(zero, one, two)),
-            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 0), ofEpochMilli(startTime + 3)))
+        assertArrayEquals(
+            new LinkedHashSet<>(asList(zero, one, two)).toArray(),
+            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 0), ofEpochMilli(startTime + 3))).toArray()
         );
-        assertEquals(
-            new HashSet<>(asList(one, two, four, five)),
-            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 1), ofEpochMilli(startTime + 5)))
+        assertArrayEquals(
+            new LinkedHashSet<>(asList(one, two, four, five)).toArray(),

Review comment:
       Haha actually I think I was the one who added the initial conversion from list to set to begin with, so I was clearly asking for trouble




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



[GitHub] [kafka] guozhangwang commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
guozhangwang commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r482525737



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/ReadOnlyWindowStore.java
##########
@@ -136,34 +174,64 @@
      * <p>
      * This iterator must be closed after use.
      *
-     * @param from      the first key in the range
-     * @param to        the last key in the range
-     * @param fromTime  time range start (inclusive)
-     * @param toTime    time range end (inclusive)
-     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive), where iteration starts.
+     * @param timeTo   time range end (inclusive), where iteration ends.
+     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}, from beginning to end of time.
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException If {@code null} is used for any key.
-     * @throws IllegalArgumentException if duration is negative or can't be represented as {@code long milliseconds}
+     * @throws NullPointerException       If {@code null} is used for any key.
+     * @throws IllegalArgumentException   if duration is negative or can't be represented as {@code long milliseconds}
      */
-    KeyValueIterator<Windowed<K>, V> fetch(K from, K to, Instant fromTime, Instant toTime)
+    KeyValueIterator<Windowed<K>, V> fetch(K from, K to, Instant timeFrom, Instant timeTo)
         throws IllegalArgumentException;
 
     /**
-    * Gets all the key-value pairs in the existing windows.
-    *
-    * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
-    * @throws InvalidStateStoreException if the store is not initialized
-    */
+     * Get all the key-value pairs in the given key range and time range from all the existing windows
+     * in backward order with respect to time (from end to beginning of time).
+     * <p>
+     * This iterator must be closed after use.
+     *
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive), where iteration ends.
+     * @param timeTo   time range end (inclusive), where iteration starts.
+     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}, from end to beginning of time.
+     * @throws InvalidStateStoreException if the store is not initialized
+     * @throws NullPointerException       If {@code null} is used for any key.
+     * @throws IllegalArgumentException   if duration is negative or can't be represented as {@code long milliseconds}
+     */
+    KeyValueIterator<Windowed<K>, V> backwardFetch(K from, K to, Instant timeFrom, Instant timeTo)

Review comment:
       The composite stores are the ones used in IQ. So IQ queries would get impacted by this, for processing, since it is always within a single task there should be no problems.




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r476969847



##########
File path: streams/src/test/java/org/apache/kafka/streams/state/internals/ReadOnlyWindowStoreStub.java
##########
@@ -104,7 +121,47 @@ public V fetch(final K key, final long time) {
 
         return new KeyValueIterator<Windowed<K>, V>() {
             @Override
-            public void close() {}
+            public void close() {
+            }
+
+            @Override
+            public Windowed<K> peekNextKey() {
+                throw new UnsupportedOperationException("peekNextKey() not supported in " + getClass().getName());
+            }
+
+            @Override
+            public boolean hasNext() {
+                return iterator.hasNext();
+            }
+
+            @Override
+            public KeyValue<Windowed<K>, V> next() {
+                return iterator.next();
+            }
+
+        };
+    }
+
+    @Override
+    public KeyValueIterator<Windowed<K>, V> backwardAll() {
+        if (!open) {
+            throw new InvalidStateStoreException("Store is not open");
+        }
+        final List<KeyValue<Windowed<K>, V>> results = new ArrayList<>();
+        for (final long now : data.keySet()) {

Review comment:
       Same here (and all the backwards ReadOnlyWindowStoreStub methods): I think we are kind of forced to invert the key ordering for the backwards fetch methods as well, even if we don't necessarily want to. Probably users shouldn't be relying on a strict ordering of the keys anyway but we do have to match the ordering of the cache

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -201,18 +203,48 @@ public synchronized void put(final Bytes key,
         }
 
         final PeekingKeyValueIterator<Bytes, LRUCacheEntry> cacheIterator = wrapped().persistent() ?
-            new CacheIteratorWrapper(key, timeFrom, timeTo) :
-            context.cache().range(cacheName,
-                        cacheFunction.cacheKey(keySchema.lowerRangeFixedSize(key, timeFrom)),
-                        cacheFunction.cacheKey(keySchema.upperRangeFixedSize(key, timeTo))
+            new CacheIteratorWrapper(key, timeFrom, timeTo, true) :
+            context.cache().range(
+                cacheName,
+                cacheFunction.cacheKey(keySchema.lowerRangeFixedSize(key, timeFrom)),
+                cacheFunction.cacheKey(keySchema.upperRangeFixedSize(key, timeTo))
             );
 
         final HasNextCondition hasNextCondition = keySchema.hasNextCondition(key, key, timeFrom, timeTo);
-        final PeekingKeyValueIterator<Bytes, LRUCacheEntry> filteredCacheIterator = new FilteredCacheIterator(
-            cacheIterator, hasNextCondition, cacheFunction
-        );
+        final PeekingKeyValueIterator<Bytes, LRUCacheEntry> filteredCacheIterator =
+            new FilteredCacheIterator(cacheIterator, hasNextCondition, cacheFunction);
 
-        return new MergedSortedCacheWindowStoreIterator(filteredCacheIterator, underlyingIterator);
+        return new MergedSortedCacheWindowStoreIterator(filteredCacheIterator, underlyingIterator, true);
+    }
+
+    @Override
+    public synchronized WindowStoreIterator<byte[]> backwardFetch(final Bytes key,
+                                                                  final Instant from,
+                                                                  final Instant to) {

Review comment:
       I guess we should use the long signature here too, and do the conversion from Instant to long in a default implementation on the WindowStore interface?

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -416,26 +552,43 @@ private long currentSegmentLastTime() {
         }
 
         private void getNextSegmentIterator() {
-            ++currentSegmentId;
-            lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+            if (forward) {
+                ++currentSegmentId;
+                lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
 
-            if (currentSegmentId > lastSegmentId) {
-                current = null;
-                return;
-            }
+                if (currentSegmentId > lastSegmentId) {
+                    current = null;
+                    return;
+                }
 
-            setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());
+                setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());
 
-            current.close();
-            current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+                current.close();
+
+                current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+            } else {
+                --currentSegmentId;
+//                lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));

Review comment:
       Guessing this is not actually meant to be commented out 

##########
File path: streams/src/test/java/org/apache/kafka/streams/state/internals/AbstractWindowBytesStoreTest.java
##########
@@ -287,17 +308,43 @@ public void shouldFetchAllInTimeRange() {
         final KeyValue<Windowed<Integer>, String> four = windowedPair(4, "four", startTime + 4);
         final KeyValue<Windowed<Integer>, String> five = windowedPair(5, "five", startTime + 5);
 
-        assertEquals(
-            new HashSet<>(asList(one, two, four)),
-            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 1), ofEpochMilli(startTime + 4)))
+        assertArrayEquals(
+            new LinkedHashSet<>(asList(one, two, four)).toArray(),
+            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 1), ofEpochMilli(startTime + 4))).toArray()
         );
-        assertEquals(
-            new HashSet<>(asList(zero, one, two)),
-            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 0), ofEpochMilli(startTime + 3)))
+        assertArrayEquals(
+            new LinkedHashSet<>(asList(zero, one, two)).toArray(),
+            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 0), ofEpochMilli(startTime + 3))).toArray()
         );
-        assertEquals(
-            new HashSet<>(asList(one, two, four, five)),
-            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 1), ofEpochMilli(startTime + 5)))
+        assertArrayEquals(
+            new LinkedHashSet<>(asList(one, two, four, five)).toArray(),

Review comment:
       It feels kind of ridiculous to convert this from a list to a set to an array all in one line. Maybe we can use `assertThat(result, equalTo(expectedResult))` here like we've started to do elsewhere in Streams?




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



[GitHub] [kafka] jeqo commented on pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#issuecomment-683830757


   @ableegoldman key ordering is added to `InMemoryWindowStore` now


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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r476962075



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -416,26 +552,43 @@ private long currentSegmentLastTime() {
         }
 
         private void getNextSegmentIterator() {
-            ++currentSegmentId;
-            lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+            if (forward) {
+                ++currentSegmentId;
+                lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
 
-            if (currentSegmentId > lastSegmentId) {
-                current = null;
-                return;
-            }
+                if (currentSegmentId > lastSegmentId) {
+                    current = null;
+                    return;
+                }
 
-            setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());
+                setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());
 
-            current.close();
-            current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+                current.close();
+
+                current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+            } else {
+                --currentSegmentId;
+//                lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));

Review comment:
       Guessing this is not actually meant to be commented out πŸ™‚ 




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r481521637



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/WindowStore.java
##########
@@ -150,13 +185,25 @@
      * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
      * @throws InvalidStateStoreException if the store is not initialized
      */
-    @SuppressWarnings("deprecation") // note, this method must be kept if super#fetchAll(...) is removed
+    // note, this method must be kept if super#fetchAll(...) is removed
+    @SuppressWarnings("deprecation")
     KeyValueIterator<Windowed<K>, V> fetchAll(long timeFrom, long timeTo);
 
     @Override
-    default KeyValueIterator<Windowed<K>, V> fetchAll(final Instant from, final Instant to) {
+    default KeyValueIterator<Windowed<K>, V> fetchAll(final Instant timeFrom, final Instant timeTo) {
         return fetchAll(
-            ApiUtils.validateMillisecondInstant(from, prepareMillisCheckFailMsgPrefix(from, "from")),
-            ApiUtils.validateMillisecondInstant(to, prepareMillisCheckFailMsgPrefix(to, "to")));
+            ApiUtils.validateMillisecondInstant(timeFrom, prepareMillisCheckFailMsgPrefix(timeFrom, "timeFrom")),
+            ApiUtils.validateMillisecondInstant(timeTo, prepareMillisCheckFailMsgPrefix(timeTo, "timeTo")));
+    }
+
+    default KeyValueIterator<Windowed<K>, V> backwardFetchAll(final long timeFrom, final long timeTo) {

Review comment:
       Idk, the current defaults make sense to me. If a user has a custom store and wants to use the new `backwardFetchAll` with both longs and Instants, all they'd have to do is override the long-based `backwardFetchAll` method (they have to implement the long version no matter what, since this is what gets used internally to Streams). If we just throw UnsupportedOperationException directly from the default implementation of the Instant-based `backwardFetchAll`, then they would have to override that as well in their custom store. So we should just let the Instant default to the long method so users only have to implement one method instead of two (plus they would have to do the Instant validation themselves, etc)




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r478774195



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/InMemoryWindowStore.java
##########
@@ -419,13 +504,13 @@ Long minTime() {
         }

Review comment:
       @jeqo I saw that you fixed this in `ReadOnlyWindowStoreStub`, I think `InMemoryWindowStore` is the only places that's still missing to reverse the key ordering on the backwards fetch 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.

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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r477436882



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -416,26 +552,43 @@ private long currentSegmentLastTime() {
         }
 
         private void getNextSegmentIterator() {
-            ++currentSegmentId;
-            lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+            if (forward) {
+                ++currentSegmentId;
+                lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
 
-            if (currentSegmentId > lastSegmentId) {
-                current = null;
-                return;
-            }
+                if (currentSegmentId > lastSegmentId) {
+                    current = null;
+                    return;
+                }
 
-            setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());
+                setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());
 
-            current.close();
-            current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+                current.close();
+
+                current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+            } else {
+                --currentSegmentId;
+//                lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));

Review comment:
       actually it could be removed: `lastSegmentId` should be stable going backwards based on `timeFrom`.
   
   On the `if` branch, I assume that `lastSegmentId` could change in between iterations if `maxObservedTimestamp` is updated right?




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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r478340031



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/WindowStore.java
##########
@@ -119,15 +118,16 @@
      * <p>
      * This iterator must be closed after use.
      *
-     * @param from      the first key in the range
-     * @param to        the last key in the range
-     * @param timeFrom  time range start (inclusive)
-     * @param timeTo    time range end (inclusive)
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive)
+     * @param timeTo   time range end (inclusive)
      * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException if one of the given keys is {@code null}
+     * @throws NullPointerException       if one of the given keys is {@code null}
      */
-    @SuppressWarnings("deprecation") // note, this method must be kept if super#fetch(...) is removed
+    // note, this method must be kept if super#fetch(...) is removed
+    @SuppressWarnings("deprecation")
     KeyValueIterator<Windowed<K>, V> fetch(K from, K to, long timeFrom, long timeTo);

Review comment:
       πŸ‘ I've added the long-based methods to WindowStore to align this. 




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r476849786



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/WindowStore.java
##########
@@ -119,15 +118,16 @@
      * <p>
      * This iterator must be closed after use.
      *
-     * @param from      the first key in the range
-     * @param to        the last key in the range
-     * @param timeFrom  time range start (inclusive)
-     * @param timeTo    time range end (inclusive)
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive)
+     * @param timeTo   time range end (inclusive)
      * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException if one of the given keys is {@code null}
+     * @throws NullPointerException       if one of the given keys is {@code null}
      */
-    @SuppressWarnings("deprecation") // note, this method must be kept if super#fetch(...) is removed
+    // note, this method must be kept if super#fetch(...) is removed
+    @SuppressWarnings("deprecation")
     KeyValueIterator<Windowed<K>, V> fetch(K from, K to, long timeFrom, long timeTo);

Review comment:
       Ok, given @mjsax 's response on [KAFKA-10434](https://issues.apache.org/jira/browse/KAFKA-10434) it seems like we actually need to add the reverse variation of these long-based methods to the WindowStore API




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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r476796186



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/InMemoryWindowStore.java
##########
@@ -163,7 +164,17 @@ public void put(final Bytes key, final byte[] value, final long windowStartTimes
     @Deprecated
     @Override
     public WindowStoreIterator<byte[]> fetch(final Bytes key, final long timeFrom, final long timeTo) {
+        return fetch(key, timeFrom, timeTo, true);
+    }
+
+    @Override
+    public WindowStoreIterator<byte[]> backwardFetch(final Bytes key, final Instant from, final Instant to) {
+        final long timeFrom = ApiUtils.validateMillisecondInstant(from, prepareMillisCheckFailMsgPrefix(from, "from"));
+        final long timeTo = ApiUtils.validateMillisecondInstant(to, prepareMillisCheckFailMsgPrefix(to, "to"));

Review comment:
       https://issues.apache.org/jira/browse/KAFKA-10434 created to follow up this.

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/InMemoryWindowStore.java
##########
@@ -163,7 +164,17 @@ public void put(final Bytes key, final byte[] value, final long windowStartTimes
     @Deprecated
     @Override
     public WindowStoreIterator<byte[]> fetch(final Bytes key, final long timeFrom, final long timeTo) {
+        return fetch(key, timeFrom, timeTo, true);
+    }
+
+    @Override
+    public WindowStoreIterator<byte[]> backwardFetch(final Bytes key, final Instant from, final Instant to) {
+        final long timeFrom = ApiUtils.validateMillisecondInstant(from, prepareMillisCheckFailMsgPrefix(from, "from"));
+        final long timeTo = ApiUtils.validateMillisecondInstant(to, prepareMillisCheckFailMsgPrefix(to, "to"));

Review comment:
       https://issues.apache.org/jira/browse/KAFKA-10434 created to follow this up.




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r478770009



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -416,26 +552,43 @@ private long currentSegmentLastTime() {
         }
 
         private void getNextSegmentIterator() {
-            ++currentSegmentId;
-            lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+            if (forward) {
+                ++currentSegmentId;
+                lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
 
-            if (currentSegmentId > lastSegmentId) {
-                current = null;
-                return;
-            }
+                if (currentSegmentId > lastSegmentId) {
+                    current = null;
+                    return;
+                }
 
-            setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());
+                setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());
 
-            current.close();
-            current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+                current.close();
+
+                current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+            } else {
+                --currentSegmentId;
+//                lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));

Review comment:
       Ah, good catch. That sounds right, the ending segment shouldn't change when you iterate backwards




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r476001166



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/WindowStore.java
##########
@@ -119,15 +118,16 @@
      * <p>
      * This iterator must be closed after use.
      *
-     * @param from      the first key in the range
-     * @param to        the last key in the range
-     * @param timeFrom  time range start (inclusive)
-     * @param timeTo    time range end (inclusive)
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive)
+     * @param timeTo   time range end (inclusive)
      * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException if one of the given keys is {@code null}
+     * @throws NullPointerException       if one of the given keys is {@code null}
      */
-    @SuppressWarnings("deprecation") // note, this method must be kept if super#fetch(...) is removed
+    // note, this method must be kept if super#fetch(...) is removed
+    @SuppressWarnings("deprecation")
     KeyValueIterator<Windowed<K>, V> fetch(K from, K to, long timeFrom, long timeTo);

Review comment:
       I guess the `note, this method must be kept if super#fetch(...) is removed` comments are making me nervous, but they could be out of date. Anyways I don't think you need to clean all this up right now, just wondering what's going on 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.

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



[GitHub] [kafka] guozhangwang merged pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
guozhangwang merged pull request #9138:
URL: https://github.com/apache/kafka/pull/9138


   


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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r476003479



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/InMemoryWindowStore.java
##########
@@ -163,7 +164,17 @@ public void put(final Bytes key, final byte[] value, final long windowStartTimes
     @Deprecated
     @Override
     public WindowStoreIterator<byte[]> fetch(final Bytes key, final long timeFrom, final long timeTo) {
+        return fetch(key, timeFrom, timeTo, true);
+    }
+
+    @Override
+    public WindowStoreIterator<byte[]> backwardFetch(final Bytes key, final Instant from, final Instant to) {
+        final long timeFrom = ApiUtils.validateMillisecondInstant(from, prepareMillisCheckFailMsgPrefix(from, "from"));
+        final long timeTo = ApiUtils.validateMillisecondInstant(to, prepareMillisCheckFailMsgPrefix(to, "to"));

Review comment:
       Ok, feel free to just create a followup ticket to see if we can clean things up. No need to block this PR on it




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r480481060



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -338,25 +452,36 @@ public synchronized void close() {
 
         private CacheIteratorWrapper(final Bytes key,
                                      final long timeFrom,
-                                     final long timeTo) {
-            this(key, key, timeFrom, timeTo);
+                                     final long timeTo,
+                                     final boolean forward) {
+            this(key, key, timeFrom, timeTo, forward);
         }
 
         private CacheIteratorWrapper(final Bytes keyFrom,
                                      final Bytes keyTo,
                                      final long timeFrom,
-                                     final long timeTo) {
+                                     final long timeTo,
+                                     final boolean forward) {
             this.keyFrom = keyFrom;
             this.keyTo = keyTo;
             this.timeTo = timeTo;
-            this.lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+            this.forward = forward;
 
             this.segmentInterval = cacheFunction.getSegmentInterval();
-            this.currentSegmentId = cacheFunction.segmentId(timeFrom);
 
-            setCacheKeyRange(timeFrom, currentSegmentLastTime());
+            if (forward) {
+                this.lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+                this.currentSegmentId = cacheFunction.segmentId(timeFrom);
 
-            this.current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+                setCacheKeyRange(timeFrom, currentSegmentLastTime());
+                this.current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+            } else {
+                this.currentSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+                this.lastSegmentId = cacheFunction.segmentId(timeFrom);
+
+                setCacheKeyRange(currentSegmentBeginTime(), Math.min(timeTo, maxObservedTimestamp.get()));

Review comment:
       This looks right to me -- in the iterator constructor, we would normally start from `timeFrom` (the minimum time) and advance to the end of the current segment (that's what the "cache key range" defines, the range of the current segment) When iterating backwards, the current segment is actually the largest segment, so the cache key lower range is the current (largest) segment's beginning timestamp, and the upper range is the maximum timestamp of the backwards fetch. Does that make sense?




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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r482810291



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/ReadOnlyWindowStore.java
##########
@@ -136,34 +174,64 @@
      * <p>
      * This iterator must be closed after use.
      *
-     * @param from      the first key in the range
-     * @param to        the last key in the range
-     * @param fromTime  time range start (inclusive)
-     * @param toTime    time range end (inclusive)
-     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive), where iteration starts.
+     * @param timeTo   time range end (inclusive), where iteration ends.
+     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}, from beginning to end of time.
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException If {@code null} is used for any key.
-     * @throws IllegalArgumentException if duration is negative or can't be represented as {@code long milliseconds}
+     * @throws NullPointerException       If {@code null} is used for any key.
+     * @throws IllegalArgumentException   if duration is negative or can't be represented as {@code long milliseconds}
      */
-    KeyValueIterator<Windowed<K>, V> fetch(K from, K to, Instant fromTime, Instant toTime)
+    KeyValueIterator<Windowed<K>, V> fetch(K from, K to, Instant timeFrom, Instant timeTo)
         throws IllegalArgumentException;
 
     /**
-    * Gets all the key-value pairs in the existing windows.
-    *
-    * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
-    * @throws InvalidStateStoreException if the store is not initialized
-    */
+     * Get all the key-value pairs in the given key range and time range from all the existing windows
+     * in backward order with respect to time (from end to beginning of time).
+     * <p>
+     * This iterator must be closed after use.
+     *
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive), where iteration ends.
+     * @param timeTo   time range end (inclusive), where iteration starts.
+     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}, from end to beginning of time.
+     * @throws InvalidStateStoreException if the store is not initialized
+     * @throws NullPointerException       If {@code null} is used for any key.
+     * @throws IllegalArgumentException   if duration is negative or can't be represented as {@code long milliseconds}
+     */
+    KeyValueIterator<Windowed<K>, V> backwardFetch(K from, K to, Instant timeFrom, Instant timeTo)

Review comment:
       thanks @guozhangwang ! I created https://issues.apache.org/jira/browse/KAFKA-10459 to follow up.




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r481519774



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/ReadOnlyWindowStore.java
##########
@@ -136,34 +174,64 @@
      * <p>
      * This iterator must be closed after use.
      *
-     * @param from      the first key in the range
-     * @param to        the last key in the range
-     * @param fromTime  time range start (inclusive)
-     * @param toTime    time range end (inclusive)
-     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive), where iteration starts.
+     * @param timeTo   time range end (inclusive), where iteration ends.
+     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}, from beginning to end of time.
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException If {@code null} is used for any key.
-     * @throws IllegalArgumentException if duration is negative or can't be represented as {@code long milliseconds}
+     * @throws NullPointerException       If {@code null} is used for any key.
+     * @throws IllegalArgumentException   if duration is negative or can't be represented as {@code long milliseconds}
      */
-    KeyValueIterator<Windowed<K>, V> fetch(K from, K to, Instant fromTime, Instant toTime)
+    KeyValueIterator<Windowed<K>, V> fetch(K from, K to, Instant timeFrom, Instant timeTo)
         throws IllegalArgumentException;
 
     /**
-    * Gets all the key-value pairs in the existing windows.
-    *
-    * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
-    * @throws InvalidStateStoreException if the store is not initialized
-    */
+     * Get all the key-value pairs in the given key range and time range from all the existing windows
+     * in backward order with respect to time (from end to beginning of time).
+     * <p>
+     * This iterator must be closed after use.
+     *
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive), where iteration ends.
+     * @param timeTo   time range end (inclusive), where iteration starts.
+     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}, from end to beginning of time.
+     * @throws InvalidStateStoreException if the store is not initialized
+     * @throws NullPointerException       If {@code null} is used for any key.
+     * @throws IllegalArgumentException   if duration is negative or can't be represented as {@code long milliseconds}
+     */
+    KeyValueIterator<Windowed<K>, V> backwardFetch(K from, K to, Instant timeFrom, Instant timeTo)

Review comment:
       Yeah, @jeqo noticed that back in the KeyValueStore PR. That's a good point about clarifying this point in the javadocs, not sure if it makes sense to do so on the ReadOnlyWindowStore methods directly vs on some IQ-related method/class? Maybe we can just do a quick followup PR to shore up the documentation here without blocking this PR




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r475014135



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/AbstractRocksDBSegmentedBytesStore.java
##########
@@ -72,22 +86,40 @@
             searchSpace.iterator(),

Review comment:
       This should be a descending iterator for the reverse case (here and the other reverse methods in this class)

##########
File path: streams/src/test/java/org/apache/kafka/streams/state/internals/SegmentIteratorTest.java
##########
@@ -107,26 +109,76 @@ public void shouldIterateOverAllSegments() {
         assertFalse(iterator.hasNext());
     }
 
+    @Test
+    public void shouldIterateBackwardOverAllSegments() {
+        iterator = new SegmentIterator<>(
+            Arrays.asList(segmentOne, segmentTwo).iterator(),
+            hasNextCondition,
+            Bytes.wrap("a".getBytes()),
+            Bytes.wrap("z".getBytes()),
+            false);
+
+        assertTrue(iterator.hasNext());
+        assertEquals("b", new String(iterator.peekNextKey().get()));
+        assertEquals(KeyValue.pair("b", "2"), toStringKeyValue(iterator.next()));
+
+        assertTrue(iterator.hasNext());
+        assertEquals("a", new String(iterator.peekNextKey().get()));
+        assertEquals(KeyValue.pair("a", "1"), toStringKeyValue(iterator.next()));
+
+        assertTrue(iterator.hasNext());
+        assertEquals("d", new String(iterator.peekNextKey().get()));
+        assertEquals(KeyValue.pair("d", "4"), toStringKeyValue(iterator.next()));
+
+        assertTrue(iterator.hasNext());
+        assertEquals("c", new String(iterator.peekNextKey().get()));
+        assertEquals(KeyValue.pair("c", "3"), toStringKeyValue(iterator.next()));

Review comment:
       This doesn't look quite right...shouldn't it be D, C, B, A? I guess in the test we just need to use a descending iterator 

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -426,7 +558,12 @@ private void getNextSegmentIterator() {
             setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());

Review comment:
       Github won't let me comment up there but on line 418, shouldn't we should have to decrement the currentSegmentId for the reverse case? I'm a little confused because it looks like you have test coverage for the multi-segment case and it seems to pass. Maybe I'm just tired and missing something obvious here..
   For example in `CachingWindowStoreTest#shouldFetchAndIterateOverKeyBackwardRange` the results seem to go across multiple segments, but it looks like we actually do return the record from the largest segment first? 

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/InMemoryWindowStore.java
##########
@@ -163,7 +164,17 @@ public void put(final Bytes key, final byte[] value, final long windowStartTimes
     @Deprecated
     @Override
     public WindowStoreIterator<byte[]> fetch(final Bytes key, final long timeFrom, final long timeTo) {
+        return fetch(key, timeFrom, timeTo, true);
+    }
+
+    @Override
+    public WindowStoreIterator<byte[]> backwardFetch(final Bytes key, final Instant from, final Instant to) {
+        final long timeFrom = ApiUtils.validateMillisecondInstant(from, prepareMillisCheckFailMsgPrefix(from, "from"));
+        final long timeTo = ApiUtils.validateMillisecondInstant(to, prepareMillisCheckFailMsgPrefix(to, "to"));

Review comment:
       I feel like it's a little awkward to have the reverse variations accept time parameters as an `Instant` while the forward versions just use a `long`. I would have thought we could migrate the long methods to Instant at some point but I see all these ` note, this method must be kept if super#fetch(...) is removed` comments littered throughout the code...so maybe there's a reason for sticking with the `long` overrides in the innermost store layer?
   Did you come across anything that suggested a reason for keeping the long flavors? cc @guozhangwang or @mjsax -- why can't we remove these?

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/WindowStore.java
##########
@@ -119,15 +118,16 @@
      * <p>
      * This iterator must be closed after use.
      *
-     * @param from      the first key in the range
-     * @param to        the last key in the range
-     * @param timeFrom  time range start (inclusive)
-     * @param timeTo    time range end (inclusive)
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive)
+     * @param timeTo   time range end (inclusive)
      * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException if one of the given keys is {@code null}
+     * @throws NullPointerException       if one of the given keys is {@code null}
      */
-    @SuppressWarnings("deprecation") // note, this method must be kept if super#fetch(...) is removed
+    // note, this method must be kept if super#fetch(...) is removed
+    @SuppressWarnings("deprecation")
     KeyValueIterator<Windowed<K>, V> fetch(K from, K to, long timeFrom, long timeTo);

Review comment:
       Do you know why we have all these ReadOnlyWindowStore methods also declared here in WindowStore? We don't need reverse variations of these I guess? πŸ€”  

##########
File path: streams/src/test/java/org/apache/kafka/streams/state/internals/ReadOnlyWindowStoreStub.java
##########
@@ -212,17 +316,62 @@ public boolean hasNext() {
         };
     }
 
-    @Override public KeyValueIterator<Windowed<K>, V> fetch(final K from,
-                                                            final K to,
-                                                            final Instant fromTime,
-                                                            final Instant toTime) throws IllegalArgumentException {
+    @Override
+    public KeyValueIterator<Windowed<K>, V> fetch(final K from,
+                                                  final K to,
+                                                  final Instant fromTime,
+                                                  final Instant toTime) throws IllegalArgumentException {
         return fetch(
             from,
-            to, 
+            to,
             ApiUtils.validateMillisecondInstant(fromTime, prepareMillisCheckFailMsgPrefix(fromTime, "fromTime")),
             ApiUtils.validateMillisecondInstant(toTime, prepareMillisCheckFailMsgPrefix(toTime, "toTime")));
     }
 
+    @Override
+    public KeyValueIterator<Windowed<K>, V> backwardFetch(final K from,
+                                                          final K to,
+                                                          final Instant fromTimeInstant,
+                                                          final Instant toTimeInstant) throws IllegalArgumentException {
+        final long timeFrom = ApiUtils.validateMillisecondInstant(fromTimeInstant, prepareMillisCheckFailMsgPrefix(fromTimeInstant, "fromTimeInstant"));
+        final long timeTo = ApiUtils.validateMillisecondInstant(toTimeInstant, prepareMillisCheckFailMsgPrefix(toTimeInstant, "toTimeInstant"));
+        if (!open) {
+            throw new InvalidStateStoreException("Store is not open");
+        }
+        final List<KeyValue<Windowed<K>, V>> results = new ArrayList<>();
+        for (long now = timeFrom; now <= timeTo; now++) {

Review comment:
       Need to flip the loop

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -426,7 +558,12 @@ private void getNextSegmentIterator() {
             setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());
 
             current.close();
-            current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+
+            if (forward) {
+                current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+            } else {
+                current = context.cache().reverseRange(cacheName, cacheKeyFrom, cacheKeyTo);
+            }
         }
 
         private void setCacheKeyRange(final long lowerRangeEndTime, final long upperRangeEndTime) {

Review comment:
       Just noticed that we use `==` instead of `.equals` down on line 437, can you fix that on the side?

##########
File path: streams/src/test/java/org/apache/kafka/streams/state/internals/CompositeReadOnlyWindowStoreTest.java
##########
@@ -135,24 +188,74 @@ public void shouldThrowInvalidStateStoreExceptionOnRebalance() {
         store.fetch("key", ofEpochMilli(1), ofEpochMilli(10));
     }
 
+    @Test(expected = InvalidStateStoreException.class)

Review comment:
       nit: use `assertThrows` 

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/InMemoryWindowStore.java
##########
@@ -419,13 +504,13 @@ Long minTime() {
         }

Review comment:
       As always Github won't let me comment on the line I actually want to (😞 ) but I think we need a descending iterator for the reverse case in `setRecordIterator` (lines 411 & 413)

##########
File path: streams/src/test/java/org/apache/kafka/streams/state/internals/MergedSortedCacheWrappedWindowStoreKeyValueIteratorTest.java
##########
@@ -123,7 +173,8 @@ public void shouldIterateBothStoreAndCache() {
 
     private MergedSortedCacheWindowStoreKeyValueIterator createIterator(
         final Iterator<KeyValue<Windowed<Bytes>, byte[]>> storeKvs,
-        final Iterator<KeyValue<Bytes, LRUCacheEntry>> cacheKvs
+        final Iterator<KeyValue<Bytes, LRUCacheEntry>> cacheKvs,
+        final boolean forward

Review comment:
       nit: the existing style here is  inconsistent with the rest of Streams, should have 1st parameter on same line as method declaration (and everything else aligned to that) 

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -337,25 +462,32 @@ public synchronized void close() {
 
         private CacheIteratorWrapper(final Bytes key,
                                      final long timeFrom,
-                                     final long timeTo) {
-            this(key, key, timeFrom, timeTo);
+                                     final long timeTo,
+                                     final boolean forward) {
+            this(key, key, timeFrom, timeTo, forward);
         }
 
         private CacheIteratorWrapper(final Bytes keyFrom,
                                      final Bytes keyTo,
                                      final long timeFrom,
-                                     final long timeTo) {
+                                     final long timeTo,
+                                     final boolean forward) {
             this.keyFrom = keyFrom;
             this.keyTo = keyTo;
             this.timeTo = timeTo;
             this.lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+            this.forward = forward;
 
             this.segmentInterval = cacheFunction.getSegmentInterval();
             this.currentSegmentId = cacheFunction.segmentId(timeFrom);

Review comment:
       We should start on the largest segment I think (largest segment == farthest advanced in time)




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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r482127067



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/SegmentIterator.java
##########
@@ -67,14 +70,22 @@ public Bytes peekNextKey() {
     public boolean hasNext() {
         boolean hasNext = false;
         while ((currentIterator == null || !(hasNext = hasNextConditionHasNext()) || !currentSegment.isOpen())
-                && segments.hasNext()) {
+            && segments.hasNext()) {
             close();
             currentSegment = segments.next();
             try {
                 if (from == null || to == null) {
-                    currentIterator = currentSegment.all();
+                    if (forward) {
+                        currentIterator = currentSegment.all();
+                    } else {
+                        currentIterator = currentSegment.reverseAll();

Review comment:
       +1. Applying change.




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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r478349804



##########
File path: streams/src/test/java/org/apache/kafka/streams/state/internals/AbstractWindowBytesStoreTest.java
##########
@@ -287,17 +308,43 @@ public void shouldFetchAllInTimeRange() {
         final KeyValue<Windowed<Integer>, String> four = windowedPair(4, "four", startTime + 4);
         final KeyValue<Windowed<Integer>, String> five = windowedPair(5, "five", startTime + 5);
 
-        assertEquals(
-            new HashSet<>(asList(one, two, four)),
-            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 1), ofEpochMilli(startTime + 4)))
+        assertArrayEquals(
+            new LinkedHashSet<>(asList(one, two, four)).toArray(),
+            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 1), ofEpochMilli(startTime + 4))).toArray()
         );
-        assertEquals(
-            new HashSet<>(asList(zero, one, two)),
-            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 0), ofEpochMilli(startTime + 3)))
+        assertArrayEquals(
+            new LinkedHashSet<>(asList(zero, one, two)).toArray(),
+            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 0), ofEpochMilli(startTime + 3))).toArray()
         );
-        assertEquals(
-            new HashSet<>(asList(one, two, four, five)),
-            toSet(windowStore.fetchAll(ofEpochMilli(startTime + 1), ofEpochMilli(startTime + 5)))
+        assertArrayEquals(
+            new LinkedHashSet<>(asList(one, two, four, five)).toArray(),

Review comment:
       Wow this is embarrasing haha, looks like I was trying to get tests green without much thinking πŸ˜… 




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



[GitHub] [kafka] guozhangwang commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
guozhangwang commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r480469688



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/ReadOnlyWindowStore.java
##########
@@ -136,34 +174,64 @@
      * <p>
      * This iterator must be closed after use.
      *
-     * @param from      the first key in the range
-     * @param to        the last key in the range
-     * @param fromTime  time range start (inclusive)
-     * @param toTime    time range end (inclusive)
-     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive), where iteration starts.
+     * @param timeTo   time range end (inclusive), where iteration ends.
+     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}, from beginning to end of time.
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException If {@code null} is used for any key.
-     * @throws IllegalArgumentException if duration is negative or can't be represented as {@code long milliseconds}
+     * @throws NullPointerException       If {@code null} is used for any key.
+     * @throws IllegalArgumentException   if duration is negative or can't be represented as {@code long milliseconds}
      */
-    KeyValueIterator<Windowed<K>, V> fetch(K from, K to, Instant fromTime, Instant toTime)
+    KeyValueIterator<Windowed<K>, V> fetch(K from, K to, Instant timeFrom, Instant timeTo)
         throws IllegalArgumentException;
 
     /**
-    * Gets all the key-value pairs in the existing windows.
-    *
-    * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
-    * @throws InvalidStateStoreException if the store is not initialized
-    */
+     * Get all the key-value pairs in the given key range and time range from all the existing windows
+     * in backward order with respect to time (from end to beginning of time).
+     * <p>
+     * This iterator must be closed after use.
+     *
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive), where iteration ends.
+     * @param timeTo   time range end (inclusive), where iteration starts.
+     * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}, from end to beginning of time.
+     * @throws InvalidStateStoreException if the store is not initialized
+     * @throws NullPointerException       If {@code null} is used for any key.
+     * @throws IllegalArgumentException   if duration is negative or can't be represented as {@code long milliseconds}
+     */
+    KeyValueIterator<Windowed<K>, V> backwardFetch(K from, K to, Instant timeFrom, Instant timeTo)

Review comment:
       This is out of the scope of this PR, but I'd like to point out that the current IQ does not actually obey the ordering when there are multiple local stores hosted on that instance. For example, if there are two stores from two tasks hosting keys {1, 3} and {2,4}, then a range query of key [1,4] would return in the order of `1,3,2,4` but not `1,2,3,4` since it is looping over the stores only. This would be the case for either forward or backward fetches on range-key-range-time.
   
   For single key time range fetch, or course, there's no such issue.
   
   I think it worth documenting this for now until we have a fix (and actually we are going to propose something soon).

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/ReadOnlyWindowStore.java
##########
@@ -33,11 +33,11 @@
     /**
      * Get the value of key from a window.
      *
-     * @param key       the key to fetch
-     * @param time      start timestamp (inclusive) of the window
+     * @param key  the key to fetch
+     * @param time start timestamp (inclusive) of the window
      * @return The value or {@code null} if no value is found in the window
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException If {@code null} is used for any key.
+     * @throws NullPointerException       If {@code null} is used for any key.

Review comment:
       nit: is this intentional? Also I'd suggest we do not use capitalized `If` to be consistent with the above line, ditto elsewhere below.

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/WindowStore.java
##########
@@ -150,13 +185,25 @@
      * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
      * @throws InvalidStateStoreException if the store is not initialized
      */
-    @SuppressWarnings("deprecation") // note, this method must be kept if super#fetchAll(...) is removed
+    // note, this method must be kept if super#fetchAll(...) is removed
+    @SuppressWarnings("deprecation")
     KeyValueIterator<Windowed<K>, V> fetchAll(long timeFrom, long timeTo);
 
     @Override
-    default KeyValueIterator<Windowed<K>, V> fetchAll(final Instant from, final Instant to) {
+    default KeyValueIterator<Windowed<K>, V> fetchAll(final Instant timeFrom, final Instant timeTo) {
         return fetchAll(
-            ApiUtils.validateMillisecondInstant(from, prepareMillisCheckFailMsgPrefix(from, "from")),
-            ApiUtils.validateMillisecondInstant(to, prepareMillisCheckFailMsgPrefix(to, "to")));
+            ApiUtils.validateMillisecondInstant(timeFrom, prepareMillisCheckFailMsgPrefix(timeFrom, "timeFrom")),
+            ApiUtils.validateMillisecondInstant(timeTo, prepareMillisCheckFailMsgPrefix(timeTo, "timeTo")));
+    }
+
+    default KeyValueIterator<Windowed<K>, V> backwardFetchAll(final long timeFrom, final long timeTo) {

Review comment:
       Since we are going to remove deprecated overloads with primitive long in the future, I think we do not need to expose a default function here, but just provide a default impl of the function in 204 below as UnsupportedOperation?

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -338,25 +452,36 @@ public synchronized void close() {
 
         private CacheIteratorWrapper(final Bytes key,
                                      final long timeFrom,
-                                     final long timeTo) {
-            this(key, key, timeFrom, timeTo);
+                                     final long timeTo,
+                                     final boolean forward) {
+            this(key, key, timeFrom, timeTo, forward);
         }
 
         private CacheIteratorWrapper(final Bytes keyFrom,
                                      final Bytes keyTo,
                                      final long timeFrom,
-                                     final long timeTo) {
+                                     final long timeTo,
+                                     final boolean forward) {
             this.keyFrom = keyFrom;
             this.keyTo = keyTo;
             this.timeTo = timeTo;
-            this.lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+            this.forward = forward;
 
             this.segmentInterval = cacheFunction.getSegmentInterval();
-            this.currentSegmentId = cacheFunction.segmentId(timeFrom);
 
-            setCacheKeyRange(timeFrom, currentSegmentLastTime());
+            if (forward) {
+                this.lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+                this.currentSegmentId = cacheFunction.segmentId(timeFrom);
 
-            this.current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+                setCacheKeyRange(timeFrom, currentSegmentLastTime());
+                this.current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+            } else {
+                this.currentSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+                this.lastSegmentId = cacheFunction.segmentId(timeFrom);
+
+                setCacheKeyRange(currentSegmentBeginTime(), Math.min(timeTo, maxObservedTimestamp.get()));

Review comment:
       Why this call is different based on the `forward` boolean? It's not clear to me. cc @ableegoldman @lct45 could you double check?

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/SegmentIterator.java
##########
@@ -67,14 +70,22 @@ public Bytes peekNextKey() {
     public boolean hasNext() {
         boolean hasNext = false;
         while ((currentIterator == null || !(hasNext = hasNextConditionHasNext()) || !currentSegment.isOpen())
-                && segments.hasNext()) {
+            && segments.hasNext()) {
             close();
             currentSegment = segments.next();
             try {
                 if (from == null || to == null) {
-                    currentIterator = currentSegment.all();
+                    if (forward) {
+                        currentIterator = currentSegment.all();
+                    } else {
+                        currentIterator = currentSegment.reverseAll();

Review comment:
       This is not directly related to this PR, but it makes me wondering: why do not keep a separate `range / all` in extended `Segment` interface? Should we just remove that? Now we've added the reverse ones but only in the parent interface, it makes me feeling the original ones on `Segment` is not necessary.

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/AbstractSegments.java
##########
@@ -117,12 +118,20 @@ public void openExisting(final ProcessorContext context, final long streamTime)
     }
 
     @Override
-    public List<S> segments(final long timeFrom, final long timeTo) {
+    public List<S> segments(final long timeFrom, final long timeTo, final boolean forward) {
         final List<S> result = new ArrayList<>();
-        final NavigableMap<Long, S> segmentsInRange = segments.subMap(
-            segmentId(timeFrom), true,
-            segmentId(timeTo), true
-        );
+        final NavigableMap<Long, S> segmentsInRange;
+        if (forward) {

Review comment:
       nit: we can just call `subMap` out of the condition and only call `descendingMap()` based on the condition.

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/AbstractMergedSortedCacheStoreIterator.java
##########
@@ -192,4 +192,3 @@ public void close() {
         storeIterator.close();
     }
 }
-

Review comment:
       Is this intentional? We usually have a newline at file end in case some specific IDEs do not like otherwise.

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -271,27 +345,68 @@ public synchronized void put(final Bytes key,
         final PeekingKeyValueIterator<Bytes, LRUCacheEntry> filteredCacheIterator =
             new FilteredCacheIterator(cacheIterator, hasNextCondition, cacheFunction);
         return new MergedSortedCacheWindowStoreKeyValueIterator(
-                filteredCacheIterator,
-                underlyingIterator,
-                bytesSerdes,
-                windowSize,
-                cacheFunction
+            filteredCacheIterator,
+            underlyingIterator,
+            bytesSerdes,
+            windowSize,
+            cacheFunction,
+            true
+        );
+    }
+
+    @Override
+    public KeyValueIterator<Windowed<Bytes>, byte[]> backwardFetchAll(final long timeFrom,

Review comment:
       See my other comments: I think we do not need to add overloads for primitive types for the newly added APIs?




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r475999351



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/InMemoryWindowStore.java
##########
@@ -419,13 +504,13 @@ Long minTime() {
         }

Review comment:
       I agree that it doesn't matter much, but I think it has to be "reverse" for both time and keys for correctness due to CachingWindowStore. The caching layer just puts everything into one byte buffer so when we go in reverse order it's just the opposite of forward, which means both key and time ordering is flipped. And we unfortunately need the ordering to match up between the cache and the underlying store due to that merging iterator guy




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



[GitHub] [kafka] guozhangwang commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
guozhangwang commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r482526159



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/AbstractSegments.java
##########
@@ -117,12 +118,20 @@ public void openExisting(final ProcessorContext context, final long streamTime)
     }
 
     @Override
-    public List<S> segments(final long timeFrom, final long timeTo) {
+    public List<S> segments(final long timeFrom, final long timeTo, final boolean forward) {
         final List<S> result = new ArrayList<>();
-        final NavigableMap<Long, S> segmentsInRange = segments.subMap(
-            segmentId(timeFrom), true,
-            segmentId(timeTo), true
-        );
+        final NavigableMap<Long, S> segmentsInRange;
+        if (forward) {

Review comment:
       SG, `nit` comments are just suggestions not mandatory.




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r480482350



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/SegmentIterator.java
##########
@@ -67,14 +70,22 @@ public Bytes peekNextKey() {
     public boolean hasNext() {
         boolean hasNext = false;
         while ((currentIterator == null || !(hasNext = hasNextConditionHasNext()) || !currentSegment.isOpen())
-                && segments.hasNext()) {
+            && segments.hasNext()) {
             close();
             currentSegment = segments.next();
             try {
                 if (from == null || to == null) {
-                    currentIterator = currentSegment.all();
+                    if (forward) {
+                        currentIterator = currentSegment.all();
+                    } else {
+                        currentIterator = currentSegment.reverseAll();

Review comment:
       Yeah that's a good question, it does seem like we can just remove the `range` and `all` on the Segment interface




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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r481930378



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/AbstractMergedSortedCacheStoreIterator.java
##########
@@ -192,4 +192,3 @@ public void close() {
         storeIterator.close();
     }
 }
-

Review comment:
       This looks strange. I can see there is a newline in my IDE. Seems that in trunk it had 2 newlines at the end. I can roll-back this change if needed. 




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



[GitHub] [kafka] guozhangwang commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
guozhangwang commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r480473830



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/SegmentIterator.java
##########
@@ -67,14 +70,22 @@ public Bytes peekNextKey() {
     public boolean hasNext() {
         boolean hasNext = false;
         while ((currentIterator == null || !(hasNext = hasNextConditionHasNext()) || !currentSegment.isOpen())
-                && segments.hasNext()) {
+            && segments.hasNext()) {
             close();
             currentSegment = segments.next();
             try {
                 if (from == null || to == null) {
-                    currentIterator = currentSegment.all();
+                    if (forward) {
+                        currentIterator = currentSegment.all();
+                    } else {
+                        currentIterator = currentSegment.reverseAll();

Review comment:
       This is not directly related to this PR, but it makes me wondering: why do we keep a separate `range / all` in extended `Segment` interface? Should we just remove that? Now we've added the reverse ones but only in the parent interface, it makes me feeling the original ones on `Segment` is not necessary.




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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r481931127



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/AbstractSegments.java
##########
@@ -117,12 +118,20 @@ public void openExisting(final ProcessorContext context, final long streamTime)
     }
 
     @Override
-    public List<S> segments(final long timeFrom, final long timeTo) {
+    public List<S> segments(final long timeFrom, final long timeTo, final boolean forward) {
         final List<S> result = new ArrayList<>();
-        final NavigableMap<Long, S> segmentsInRange = segments.subMap(
-            segmentId(timeFrom), true,
-            segmentId(timeTo), true
-        );
+        final NavigableMap<Long, S> segmentsInRange;
+        if (forward) {

Review comment:
       I'd prefer this immutable approach as it's the same used in keyValueStore changes, if that's ok. 




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



[GitHub] [kafka] guozhangwang commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
guozhangwang commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r482524622



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/WindowStore.java
##########
@@ -150,13 +185,25 @@
      * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
      * @throws InvalidStateStoreException if the store is not initialized
      */
-    @SuppressWarnings("deprecation") // note, this method must be kept if super#fetchAll(...) is removed
+    // note, this method must be kept if super#fetchAll(...) is removed
+    @SuppressWarnings("deprecation")
     KeyValueIterator<Windowed<K>, V> fetchAll(long timeFrom, long timeTo);
 
     @Override
-    default KeyValueIterator<Windowed<K>, V> fetchAll(final Instant from, final Instant to) {
+    default KeyValueIterator<Windowed<K>, V> fetchAll(final Instant timeFrom, final Instant timeTo) {
         return fetchAll(
-            ApiUtils.validateMillisecondInstant(from, prepareMillisCheckFailMsgPrefix(from, "from")),
-            ApiUtils.validateMillisecondInstant(to, prepareMillisCheckFailMsgPrefix(to, "to")));
+            ApiUtils.validateMillisecondInstant(timeFrom, prepareMillisCheckFailMsgPrefix(timeFrom, "timeFrom")),
+            ApiUtils.validateMillisecondInstant(timeTo, prepareMillisCheckFailMsgPrefix(timeTo, "timeTo")));
+    }
+
+    default KeyValueIterator<Windowed<K>, V> backwardFetchAll(final long timeFrom, final long timeTo) {

Review comment:
       Ah yes, I was thinking about ReadOnlyWindowStore exposed in IQ only. All good.




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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r475910689



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/WindowStore.java
##########
@@ -119,15 +118,16 @@
      * <p>
      * This iterator must be closed after use.
      *
-     * @param from      the first key in the range
-     * @param to        the last key in the range
-     * @param timeFrom  time range start (inclusive)
-     * @param timeTo    time range end (inclusive)
+     * @param from     the first key in the range
+     * @param to       the last key in the range
+     * @param timeFrom time range start (inclusive)
+     * @param timeTo   time range end (inclusive)
      * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException if one of the given keys is {@code null}
+     * @throws NullPointerException       if one of the given keys is {@code null}
      */
-    @SuppressWarnings("deprecation") // note, this method must be kept if super#fetch(...) is removed
+    // note, this method must be kept if super#fetch(...) is removed
+    @SuppressWarnings("deprecation")
     KeyValueIterator<Windowed<K>, V> fetch(K from, K to, long timeFrom, long timeTo);

Review comment:
       These methods were introduced when adding Duration/Instant support https://github.com/apache/kafka/pull/5682.
   
   I don't think these are needed, we can do a similar change as for SessionStore read operations. wdyt?

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/InMemoryWindowStore.java
##########
@@ -419,13 +504,13 @@ Long minTime() {
         }

Review comment:
       For windowStore, only time-based index is been iterated backward. The KIP didn't considered reversing key/value stores internally. 
   
   We would need another flag (apart from backward) to define order of internal keys, which its cumbersome, and the order between keys doesn't matter much or can be calculated by the user. 

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -426,7 +558,12 @@ private void getNextSegmentIterator() {
             setCacheKeyRange(currentSegmentBeginTime(), currentSegmentLastTime());

Review comment:
       Will have to double check this. I have inverted the current/last segment for backwards use-case though.

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/AbstractRocksDBSegmentedBytesStore.java
##########
@@ -72,22 +86,40 @@
             searchSpace.iterator(),

Review comment:
       `searchSpace` will be reversed based on the `forward` flag, on `AbstractSegments`. 

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/InMemoryWindowStore.java
##########
@@ -163,7 +164,17 @@ public void put(final Bytes key, final byte[] value, final long windowStartTimes
     @Deprecated
     @Override
     public WindowStoreIterator<byte[]> fetch(final Bytes key, final long timeFrom, final long timeTo) {
+        return fetch(key, timeFrom, timeTo, true);
+    }
+
+    @Override
+    public WindowStoreIterator<byte[]> backwardFetch(final Bytes key, final Instant from, final Instant to) {
+        final long timeFrom = ApiUtils.validateMillisecondInstant(from, prepareMillisCheckFailMsgPrefix(from, "from"));
+        final long timeTo = ApiUtils.validateMillisecondInstant(to, prepareMillisCheckFailMsgPrefix(to, "to"));

Review comment:
       Only backward compatibility. If it make sense to remove these deprecations as part of this KIP, I'd be happy to help cleaning it. 

##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -337,25 +462,32 @@ public synchronized void close() {
 
         private CacheIteratorWrapper(final Bytes key,
                                      final long timeFrom,
-                                     final long timeTo) {
-            this(key, key, timeFrom, timeTo);
+                                     final long timeTo,
+                                     final boolean forward) {
+            this(key, key, timeFrom, timeTo, forward);
         }
 
         private CacheIteratorWrapper(final Bytes keyFrom,
                                      final Bytes keyTo,
                                      final long timeFrom,
-                                     final long timeTo) {
+                                     final long timeTo,
+                                     final boolean forward) {
             this.keyFrom = keyFrom;
             this.keyTo = keyTo;
             this.timeTo = timeTo;
             this.lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+            this.forward = forward;
 
             this.segmentInterval = cacheFunction.getSegmentInterval();
             this.currentSegmentId = cacheFunction.segmentId(timeFrom);

Review comment:
       great catch! I think this hasn't pop up yet in the tests as all tests may be using the same segment.
   
   Will double check to add more tests to validate this.




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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r481920572



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/ReadOnlyWindowStore.java
##########
@@ -33,11 +33,11 @@
     /**
      * Get the value of key from a window.
      *
-     * @param key       the key to fetch
-     * @param time      start timestamp (inclusive) of the window
+     * @param key  the key to fetch
+     * @param time start timestamp (inclusive) of the window
      * @return The value or {@code null} if no value is found in the window
      * @throws InvalidStateStoreException if the store is not initialized
-     * @throws NullPointerException If {@code null} is used for any key.
+     * @throws NullPointerException       If {@code null} is used for any key.

Review comment:
       yes, IDE reformatting. I've fixed the capitalized `If` 




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



[GitHub] [kafka] jeqo commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r482160020



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/WindowStore.java
##########
@@ -150,13 +185,25 @@
      * @return an iterator over windowed key-value pairs {@code <Windowed<K>, value>}
      * @throws InvalidStateStoreException if the store is not initialized
      */
-    @SuppressWarnings("deprecation") // note, this method must be kept if super#fetchAll(...) is removed
+    // note, this method must be kept if super#fetchAll(...) is removed
+    @SuppressWarnings("deprecation")
     KeyValueIterator<Windowed<K>, V> fetchAll(long timeFrom, long timeTo);
 
     @Override
-    default KeyValueIterator<Windowed<K>, V> fetchAll(final Instant from, final Instant to) {
+    default KeyValueIterator<Windowed<K>, V> fetchAll(final Instant timeFrom, final Instant timeTo) {
         return fetchAll(
-            ApiUtils.validateMillisecondInstant(from, prepareMillisCheckFailMsgPrefix(from, "from")),
-            ApiUtils.validateMillisecondInstant(to, prepareMillisCheckFailMsgPrefix(to, "to")));
+            ApiUtils.validateMillisecondInstant(timeFrom, prepareMillisCheckFailMsgPrefix(timeFrom, "timeFrom")),
+            ApiUtils.validateMillisecondInstant(timeTo, prepareMillisCheckFailMsgPrefix(timeTo, "timeTo")));
+    }
+
+    default KeyValueIterator<Windowed<K>, V> backwardFetchAll(final long timeFrom, final long timeTo) {

Review comment:
       @guozhangwang do you mean the changes proposed in KIP-667? In that KIP we are removing long-based methods only from `ReadOnlyWindowStore`, but will keep it in `WindowStore`β€”unless you're referring to a different proposal.
   
   I do agree with @ableegoldman. Users will have to opt-in to reverse operations when using custom stores, and by default only add implementation for long-based to support both params options.




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



[GitHub] [kafka] ableegoldman commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
ableegoldman commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r480479677



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -271,27 +345,68 @@ public synchronized void put(final Bytes key,
         final PeekingKeyValueIterator<Bytes, LRUCacheEntry> filteredCacheIterator =
             new FilteredCacheIterator(cacheIterator, hasNextCondition, cacheFunction);
         return new MergedSortedCacheWindowStoreKeyValueIterator(
-                filteredCacheIterator,
-                underlyingIterator,
-                bytesSerdes,
-                windowSize,
-                cacheFunction
+            filteredCacheIterator,
+            underlyingIterator,
+            bytesSerdes,
+            windowSize,
+            cacheFunction,
+            true
+        );
+    }
+
+    @Override
+    public KeyValueIterator<Windowed<Bytes>, byte[]> backwardFetchAll(final long timeFrom,

Review comment:
       We would still need to keep this method: we're not removing all long-based APIs, just the public/IQ methods in ReadOnlyWindowStore. But we still want to keep the long-based methods on WindowStore and all the internal store interfaces for performance reasons.
   Maybe once we move everything to use `Instant` all the way down to the serialization then we can remove these long-based methods. I guess we should consider that when discussing KIP-667, but for the time being at least, we should keep them for internal 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.

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



[GitHub] [kafka] guozhangwang commented on a change in pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
guozhangwang commented on a change in pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#discussion_r482528601



##########
File path: streams/src/main/java/org/apache/kafka/streams/state/internals/CachingWindowStore.java
##########
@@ -338,25 +452,36 @@ public synchronized void close() {
 
         private CacheIteratorWrapper(final Bytes key,
                                      final long timeFrom,
-                                     final long timeTo) {
-            this(key, key, timeFrom, timeTo);
+                                     final long timeTo,
+                                     final boolean forward) {
+            this(key, key, timeFrom, timeTo, forward);
         }
 
         private CacheIteratorWrapper(final Bytes keyFrom,
                                      final Bytes keyTo,
                                      final long timeFrom,
-                                     final long timeTo) {
+                                     final long timeTo,
+                                     final boolean forward) {
             this.keyFrom = keyFrom;
             this.keyTo = keyTo;
             this.timeTo = timeTo;
-            this.lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+            this.forward = forward;
 
             this.segmentInterval = cacheFunction.getSegmentInterval();
-            this.currentSegmentId = cacheFunction.segmentId(timeFrom);
 
-            setCacheKeyRange(timeFrom, currentSegmentLastTime());
+            if (forward) {
+                this.lastSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+                this.currentSegmentId = cacheFunction.segmentId(timeFrom);
 
-            this.current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+                setCacheKeyRange(timeFrom, currentSegmentLastTime());
+                this.current = context.cache().range(cacheName, cacheKeyFrom, cacheKeyTo);
+            } else {
+                this.currentSegmentId = cacheFunction.segmentId(Math.min(timeTo, maxObservedTimestamp.get()));
+                this.lastSegmentId = cacheFunction.segmentId(timeFrom);
+
+                setCacheKeyRange(currentSegmentBeginTime(), Math.min(timeTo, maxObservedTimestamp.get()));

Review comment:
       SG




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



[GitHub] [kafka] jeqo commented on pull request #9138: KAFKA-9929: Support backward iterator on WindowStore

Posted by GitBox <gi...@apache.org>.
jeqo commented on pull request #9138:
URL: https://github.com/apache/kafka/pull/9138#issuecomment-675384593


   @ableegoldman, this PR is ready for review πŸ‘ 
   


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