You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@flink.apache.org by GitBox <gi...@apache.org> on 2018/08/02 15:45:21 UTC

[GitHub] asfgit closed pull request #6467: [FLINK-9887] Ensure serializer upgrades work with timer service remake

asfgit closed pull request #6467: [FLINK-9887] Ensure serializer upgrades work with timer service remake
URL: https://github.com/apache/flink/pull/6467
 
 
   

This is a PR merged from a forked repository.
As GitHub hides the original diff on merge, it is displayed below for
the sake of provenance:

As this is a foreign pull request (from a fork), the diff is supplied
below (as it won't show otherwise due to GitHub magic):

diff --git a/docs/_includes/generated/rocks_db_configuration.html b/docs/_includes/generated/rocks_db_configuration.html
index 57b95114976..8983f8b41dd 100644
--- a/docs/_includes/generated/rocks_db_configuration.html
+++ b/docs/_includes/generated/rocks_db_configuration.html
@@ -13,9 +13,9 @@
             <td>The local directory (on the TaskManager) where RocksDB puts its files.</td>
         </tr>
         <tr>
-            <td><h5>state.backend.rocksdb.timer-service.impl</h5></td>
+            <td><h5>state.backend.rocksdb.timer-service.factory</h5></td>
             <td style="word-wrap: break-word;">"HEAP"</td>
-            <td>This determines the timer service implementation. Options are either HEAP (heap-based, default) or ROCKSDB for an implementation based on RocksDB.</td>
+            <td>This determines the factory for timer service state implementation. Options are either HEAP (heap-based, default) or ROCKSDB for an implementation based on RocksDB .</td>
         </tr>
     </tbody>
 </table>
diff --git a/flink-core/src/main/java/org/apache/flink/api/common/typeutils/base/LongSerializer.java b/flink-core/src/main/java/org/apache/flink/api/common/typeutils/base/LongSerializer.java
index cbdc3db7476..2ed2cec5e53 100644
--- a/flink-core/src/main/java/org/apache/flink/api/common/typeutils/base/LongSerializer.java
+++ b/flink-core/src/main/java/org/apache/flink/api/common/typeutils/base/LongSerializer.java
@@ -18,12 +18,12 @@
 
 package org.apache.flink.api.common.typeutils.base;
 
-import java.io.IOException;
-
 import org.apache.flink.annotation.Internal;
 import org.apache.flink.core.memory.DataInputView;
 import org.apache.flink.core.memory.DataOutputView;
 
+import java.io.IOException;
+
 @Internal
 public final class LongSerializer extends TypeSerializerSingleton<Long> {
 
@@ -31,7 +31,7 @@
 	
 	public static final LongSerializer INSTANCE = new LongSerializer();
 	
-	private static final Long ZERO = Long.valueOf(0);
+	private static final Long ZERO = 0L;
 
 	@Override
 	public boolean isImmutableType() {
@@ -55,17 +55,17 @@ public Long copy(Long from, Long reuse) {
 
 	@Override
 	public int getLength() {
-		return 8;
+		return Long.BYTES;
 	}
 
 	@Override
 	public void serialize(Long record, DataOutputView target) throws IOException {
-		target.writeLong(record.longValue());
+		target.writeLong(record);
 	}
 
 	@Override
 	public Long deserialize(DataInputView source) throws IOException {
-		return Long.valueOf(source.readLong());
+		return source.readLong();
 	}
 	
 	@Override
diff --git a/flink-core/src/main/java/org/apache/flink/core/memory/ByteArrayInputStreamWithPos.java b/flink-core/src/main/java/org/apache/flink/core/memory/ByteArrayInputStreamWithPos.java
index 1447e9661c8..bc81593dea4 100644
--- a/flink-core/src/main/java/org/apache/flink/core/memory/ByteArrayInputStreamWithPos.java
+++ b/flink-core/src/main/java/org/apache/flink/core/memory/ByteArrayInputStreamWithPos.java
@@ -30,20 +30,23 @@
 @Internal
 public class ByteArrayInputStreamWithPos extends InputStream {
 
+	private static final byte[] EMPTY = new byte[0];
+
 	protected byte[] buffer;
 	protected int position;
 	protected int count;
 	protected int mark = 0;
 
+	public ByteArrayInputStreamWithPos() {
+		this(EMPTY);
+	}
+
 	public ByteArrayInputStreamWithPos(byte[] buffer) {
 		this(buffer, 0, buffer.length);
 	}
 
 	public ByteArrayInputStreamWithPos(byte[] buffer, int offset, int length) {
-		this.position = offset;
-		this.buffer = buffer;
-		this.mark = offset;
-		this.count = Math.min(buffer.length, offset + length);
+		setBuffer(buffer, offset, length);
 	}
 
 	@Override
@@ -122,4 +125,11 @@ public void setPosition(int pos) {
 		Preconditions.checkArgument(pos >= 0 && pos <= count, "Position out of bounds.");
 		this.position = pos;
 	}
+
+	public void setBuffer(byte[] buffer, int offset, int length) {
+		this.count = Math.min(buffer.length, offset + length);
+		setPosition(offset);
+		this.buffer = buffer;
+		this.mark = offset;
+	}
 }
diff --git a/flink-core/src/main/java/org/apache/flink/util/StateMigrationException.java b/flink-core/src/main/java/org/apache/flink/util/StateMigrationException.java
index 00e0e73dc5c..12f3ee43583 100644
--- a/flink-core/src/main/java/org/apache/flink/util/StateMigrationException.java
+++ b/flink-core/src/main/java/org/apache/flink/util/StateMigrationException.java
@@ -24,6 +24,8 @@
 public class StateMigrationException extends FlinkException {
 	private static final long serialVersionUID = 8268516412747670839L;
 
+	public static final String MIGRATION_NOT_SUPPORTED_MSG = "State migration is currently not supported.";
+
 	public StateMigrationException(String message) {
 		super(message);
 	}
@@ -35,4 +37,8 @@ public StateMigrationException(Throwable cause) {
 	public StateMigrationException(String message, Throwable cause) {
 		super(message, cause);
 	}
+
+	public static StateMigrationException notSupported() {
+		return new StateMigrationException(MIGRATION_NOT_SUPPORTED_MSG);
+	}
 }
diff --git a/flink-core/src/test/java/org/apache/flink/core/memory/ByteArrayInputStreamWithPosTest.java b/flink-core/src/test/java/org/apache/flink/core/memory/ByteArrayInputStreamWithPosTest.java
index 4797c0a338c..62ad911ab25 100644
--- a/flink-core/src/test/java/org/apache/flink/core/memory/ByteArrayInputStreamWithPosTest.java
+++ b/flink-core/src/test/java/org/apache/flink/core/memory/ByteArrayInputStreamWithPosTest.java
@@ -81,4 +81,18 @@ public void testSetNegativePosition() throws Exception {
 		thrown.expectMessage("Position out of bounds.");
 		stream.setPosition(-1);
 	}
+
+	@Test
+	public void testSetBuffer() {
+		ByteArrayInputStreamWithPos in = new ByteArrayInputStreamWithPos();
+		Assert.assertEquals(-1, in.read());
+		byte[] testData = new byte[]{0x42, 0x43, 0x44, 0x45};
+		int off = 1;
+		int len = 2;
+		in.setBuffer(testData, off, len);
+		for (int i = 0; i < len; ++i) {
+			Assert.assertEquals(testData[i + off], in.read());
+		}
+		Assert.assertEquals(-1, in.read());
+	}
 }
diff --git a/flink-end-to-end-tests/test-scripts/test_resume_savepoint.sh b/flink-end-to-end-tests/test-scripts/test_resume_savepoint.sh
index 26a7e855c3c..fd0bf913a85 100755
--- a/flink-end-to-end-tests/test-scripts/test_resume_savepoint.sh
+++ b/flink-end-to-end-tests/test-scripts/test_resume_savepoint.sh
@@ -59,7 +59,7 @@ backup_config
 change_conf "taskmanager.numberOfTaskSlots" "1" "${NUM_SLOTS}"
 
 if [ $STATE_BACKEND_ROCKS_TIMER_SERVICE_TYPE == 'rocks' ]; then
-  set_conf "state.backend.rocksdb.timer-service.impl" "rocksdb"
+  set_conf "state.backend.rocksdb.timer-service.factory" "rocksdb"
 fi
 
 setup_flink_slf4j_metric_reporter
diff --git a/flink-runtime/pom.xml b/flink-runtime/pom.xml
index ab4521cf51f..733ddf6f23a 100644
--- a/flink-runtime/pom.xml
+++ b/flink-runtime/pom.xml
@@ -115,12 +115,6 @@ under the License.
 			<!-- Version is set in root POM -->
 		</dependency>
 
-		<dependency>
-			<groupId>it.unimi.dsi</groupId>
-			<artifactId>fastutil</artifactId>
-			<version>8.2.1</version>
-		</dependency>
-
 		<dependency>
 			<groupId>org.scala-lang</groupId>
 			<artifactId>scala-library</artifactId>
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/AbstractKeyedStateBackend.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/AbstractKeyedStateBackend.java
index 17d24f77472..1c2d2a3ecaf 100644
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/AbstractKeyedStateBackend.java
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/AbstractKeyedStateBackend.java
@@ -313,7 +313,7 @@ StreamCompressionDecorator getKeyGroupCompressionDecorator() {
 	 * Returns the total number of state entries across all keys/namespaces.
 	 */
 	@VisibleForTesting
-	public abstract int numStateEntries();
+	public abstract int numKeyValueStateEntries();
 
 	// TODO remove this once heap-based timers are working with RocksDB incremental snapshots!
 	public boolean requiresLegacySynchronousTimerSnapshots() {
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/DefaultOperatorStateBackend.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/DefaultOperatorStateBackend.java
index f1d0b57e906..dfff50dff64 100644
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/DefaultOperatorStateBackend.java
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/DefaultOperatorStateBackend.java
@@ -260,7 +260,7 @@ public void dispose() {
 				// the new serializer; we're deliberately failing here for now to have equal functionality with
 				// the RocksDB backend to avoid confusion for users.
 
-				throw new StateMigrationException("State migration isn't supported, yet.");
+				throw StateMigrationException.notSupported();
 			}
 		}
 
@@ -781,7 +781,7 @@ public void addAll(List<S> values) throws Exception {
 				// the new serializer; we're deliberately failing here for now to have equal functionality with
 				// the RocksDB backend to avoid confusion for users.
 
-				throw new StateMigrationException("State migration isn't supported, yet.");
+				throw StateMigrationException.notSupported();
 			}
 		}
 
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/InternalPriorityQueue.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/InternalPriorityQueue.java
index dc46c8ab637..fb3ee82f984 100644
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/InternalPriorityQueue.java
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/InternalPriorityQueue.java
@@ -26,8 +26,6 @@
 import javax.annotation.Nullable;
 
 import java.util.Collection;
-import java.util.function.Consumer;
-import java.util.function.Predicate;
 
 /**
  * Interface for collection that gives in order access to elements w.r.t their priority.
@@ -37,16 +35,6 @@
 @Internal
 public interface InternalPriorityQueue<T> {
 
-	/**
-	 * Polls from the top of the queue as long as the the queue is not empty and passes the elements to
-	 * {@link Consumer} until a {@link Predicate} rejects an offered element. The rejected element is not
-	 * removed from the queue and becomes the new head.
-	 *
-	 * @param canConsume bulk polling ends once this returns false. The rejected element is nor removed and not consumed.
-	 * @param consumer consumer function for elements accepted by canConsume.
-	 */
-	void bulkPoll(@Nonnull Predicate<T> canConsume, @Nonnull Consumer<T> consumer);
-
 	/**
 	 * Retrieves and removes the first element (w.r.t. the order) of this set,
 	 * or returns {@code null} if this set is empty.
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/RegisteredKeyValueStateBackendMetaInfo.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/RegisteredKeyValueStateBackendMetaInfo.java
index d49a05ca3f9..b0248fc59d5 100644
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/RegisteredKeyValueStateBackendMetaInfo.java
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/RegisteredKeyValueStateBackendMetaInfo.java
@@ -144,6 +144,12 @@ public int hashCode() {
 		TypeSerializer<N> newNamespaceSerializer,
 		StateDescriptor<?, S> newStateDescriptor) throws StateMigrationException {
 
+		Preconditions.checkState(restoredStateMetaInfoSnapshot.getBackendStateType()
+				== StateMetaInfoSnapshot.BackendStateType.KEY_VALUE,
+			"Incompatible state types. " +
+				"Was [" + restoredStateMetaInfoSnapshot.getBackendStateType() + "], " +
+				"registered as [" + StateMetaInfoSnapshot.BackendStateType.KEY_VALUE + "].");
+
 		Preconditions.checkState(
 			Objects.equals(newStateDescriptor.getName(), restoredStateMetaInfoSnapshot.getName()),
 			"Incompatible state names. " +
@@ -160,7 +166,7 @@ public int hashCode() {
 
 			Preconditions.checkState(
 				newStateDescriptor.getType() == restoredType,
-				"Incompatible state types. " +
+				"Incompatible key/value state types. " +
 					"Was [" + restoredType + "], " +
 					"registered with [" + newStateDescriptor.getType() + "].");
 		}
@@ -184,7 +190,7 @@ public int hashCode() {
 
 		if (namespaceCompatibility.isRequiresMigration() || stateCompatibility.isRequiresMigration()) {
 			// TODO state migration currently isn't possible.
-			throw new StateMigrationException("State migration isn't supported, yet.");
+			throw StateMigrationException.notSupported();
 		} else {
 			return new RegisteredKeyValueStateBackendMetaInfo<>(
 				newStateDescriptor.getType(),
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/TieBreakingPriorityComparator.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/TieBreakingPriorityComparator.java
deleted file mode 100644
index 94aed45a03e..00000000000
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/TieBreakingPriorityComparator.java
+++ /dev/null
@@ -1,117 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.flink.runtime.state;
-
-import org.apache.flink.api.common.typeutils.TypeSerializer;
-import org.apache.flink.core.memory.ByteArrayOutputStreamWithPos;
-import org.apache.flink.core.memory.DataOutputViewStreamWrapper;
-import org.apache.flink.util.FlinkRuntimeException;
-
-import javax.annotation.Nonnull;
-
-import java.io.IOException;
-import java.util.Comparator;
-
-/**
- * This class is an adapter between {@link PriorityComparator} and a full {@link Comparator} that respects the
- * contract between {@link Comparator#compare(Object, Object)} and {@link Object#equals(Object)}. This is currently
- * needed for implementations of
- * {@link org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet.OrderedSetCache} that are implemented
- * on top of a data structure that relies on the this contract, e.g. a tree set. We should replace this in the near
- * future.
- *
- * @param <T> type of the compared elements.
- */
-public class TieBreakingPriorityComparator<T> implements Comparator<T>, PriorityComparator<T> {
-
-	/** The {@link PriorityComparator} to which we delegate in a first step. */
-	@Nonnull
-	private final PriorityComparator<T> priorityComparator;
-
-	/** Serializer for instances of the compared objects. */
-	@Nonnull
-	private final TypeSerializer<T> serializer;
-
-	/** Stream that we use in serialization. */
-	@Nonnull
-	private final ByteArrayOutputStreamWithPos outStream;
-
-	/** {@link org.apache.flink.core.memory.DataOutputView} around outStream. */
-	@Nonnull
-	private final DataOutputViewStreamWrapper outView;
-
-	public TieBreakingPriorityComparator(
-		@Nonnull PriorityComparator<T> priorityComparator,
-		@Nonnull TypeSerializer<T> serializer,
-		@Nonnull ByteArrayOutputStreamWithPos outStream,
-		@Nonnull DataOutputViewStreamWrapper outView) {
-
-		this.priorityComparator = priorityComparator;
-		this.serializer = serializer;
-		this.outStream = outStream;
-		this.outView = outView;
-	}
-
-	@SuppressWarnings("unchecked")
-	@Override
-	public int compare(T o1, T o2) {
-
-		// first we compare priority, this should be the most commonly hit case
-		int cmp = priorityComparator.comparePriority(o1, o2);
-
-		if (cmp != 0) {
-			return cmp;
-		}
-
-		// here we start tie breaking and do our best to comply with the compareTo/equals contract, first we try
-		// to simply find an existing way to fully compare.
-		if (o1 instanceof Comparable && o1.getClass().equals(o2.getClass())) {
-			return ((Comparable<T>) o1).compareTo(o2);
-		}
-
-		// if objects are not equal, their serialized form should somehow differ as well. this can be costly, and...
-		// TODO we should have an alternative approach in the future, e.g. a cache that does not rely on compare to check equality.
-		try {
-			outStream.reset();
-			serializer.serialize(o1, outView);
-			int leftLen = outStream.getPosition();
-			serializer.serialize(o2, outView);
-			int rightLen = outStream.getPosition() - leftLen;
-			return compareBytes(outStream.getBuf(), 0, leftLen, leftLen, rightLen);
-		} catch (IOException ex) {
-			throw new FlinkRuntimeException("Serializer problem in comparator.", ex);
-		}
-	}
-
-	@Override
-	public int comparePriority(T left, T right) {
-		return priorityComparator.comparePriority(left, right);
-	}
-
-	public static int compareBytes(byte[] bytes, int offLeft, int leftLen, int offRight, int rightLen) {
-		int maxLen = Math.min(leftLen, rightLen);
-		for (int i = 0; i < maxLen; ++i) {
-			int cmp = bytes[offLeft + i] - bytes[offRight + i];
-			if (cmp != 0) {
-				return cmp;
-			}
-		}
-		return leftLen - rightLen;
-	}
-}
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/AbstractHeapPriorityQueue.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/AbstractHeapPriorityQueue.java
new file mode 100644
index 00000000000..f2981bd0b8e
--- /dev/null
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/AbstractHeapPriorityQueue.java
@@ -0,0 +1,222 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.runtime.state.heap;
+
+import org.apache.flink.runtime.state.InternalPriorityQueue;
+import org.apache.flink.util.CloseableIterator;
+
+import javax.annotation.Nonnegative;
+import javax.annotation.Nonnull;
+import javax.annotation.Nullable;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+import static org.apache.flink.util.CollectionUtil.MAX_ARRAY_SIZE;
+
+/**
+ * Abstract base class for heap (object array) based implementations of priority queues, with support for fast deletes
+ * via {@link HeapPriorityQueueElement}.
+ *
+ * @param <T> type of the elements contained in the priority queue.
+ */
+public abstract class AbstractHeapPriorityQueue<T extends HeapPriorityQueueElement>
+	implements InternalPriorityQueue<T> {
+
+	/** The array that represents the heap-organized priority queue. */
+	@Nonnull
+	protected T[] queue;
+
+	/** The current size of the priority queue. */
+	@Nonnegative
+	protected int size;
+
+	@SuppressWarnings("unchecked")
+	public AbstractHeapPriorityQueue(@Nonnegative int minimumCapacity) {
+		this.queue = (T[]) new HeapPriorityQueueElement[getHeadElementIndex() + minimumCapacity];
+		this.size = 0;
+	}
+
+	@Override
+	@Nullable
+	public T poll() {
+		return size() > 0 ? removeInternal(getHeadElementIndex()) : null;
+	}
+
+	@Override
+	@Nullable
+	public T peek() {
+		// References to removed elements are expected to become set to null.
+		return queue[getHeadElementIndex()];
+	}
+
+	@Override
+	public boolean add(@Nonnull T toAdd) {
+		addInternal(toAdd);
+		return toAdd.getInternalIndex() == getHeadElementIndex();
+	}
+
+	@Override
+	public boolean remove(@Nonnull T toRemove) {
+		final int elementIndex = toRemove.getInternalIndex();
+		removeInternal(elementIndex);
+		return elementIndex == getHeadElementIndex();
+	}
+
+	@Override
+	public boolean isEmpty() {
+		return size() == 0;
+	}
+
+	@Override
+	public int size() {
+		return size;
+	}
+
+	@Override
+	public void addAll(@Nullable Collection<? extends T> toAdd) {
+
+		if (toAdd == null) {
+			return;
+		}
+
+		resizeForBulkLoad(toAdd.size());
+
+		for (T element : toAdd) {
+			add(element);
+		}
+	}
+
+	@SuppressWarnings({"unchecked"})
+	@Nonnull
+	public <O> O[] toArray(O[] out) {
+		final int heapArrayOffset = getHeadElementIndex();
+		if (out.length < size) {
+			return (O[]) Arrays.copyOfRange(queue, heapArrayOffset, heapArrayOffset + size, out.getClass());
+		} else {
+			System.arraycopy(queue, heapArrayOffset, out, 0, size);
+			if (out.length > size) {
+				out[size] = null;
+			}
+			return out;
+		}
+	}
+
+	/**
+	 * Returns an iterator over the elements in this queue. The iterator
+	 * does not return the elements in any particular order.
+	 *
+	 * @return an iterator over the elements in this queue.
+	 */
+	@Nonnull
+	@Override
+	public CloseableIterator<T> iterator() {
+		return new HeapIterator();
+	}
+
+	/**
+	 * Clears the queue.
+	 */
+	public void clear() {
+		final int arrayOffset = getHeadElementIndex();
+		Arrays.fill(queue, arrayOffset, arrayOffset + size, null);
+		size = 0;
+	}
+
+	protected void resizeForBulkLoad(int totalSize) {
+		if (totalSize > queue.length) {
+			int desiredSize = totalSize + (totalSize >>> 3);
+			resizeQueueArray(desiredSize, totalSize);
+		}
+	}
+
+	protected void resizeQueueArray(int desiredSize, int minRequiredSize) {
+		if (isValidArraySize(desiredSize)) {
+			queue = Arrays.copyOf(queue, desiredSize);
+		} else if (isValidArraySize(minRequiredSize)) {
+			queue = Arrays.copyOf(queue, MAX_ARRAY_SIZE);
+		} else {
+			throw new OutOfMemoryError("Required minimum heap size " + minRequiredSize +
+				" exceeds maximum size of " + MAX_ARRAY_SIZE + ".");
+		}
+	}
+
+	protected void moveElementToIdx(T element, int idx) {
+		queue[idx] = element;
+		element.setInternalIndex(idx);
+	}
+
+	/**
+	 * Implements how to remove the element at the given index from the queue.
+	 *
+	 * @param elementIndex the index to remove.
+	 * @return the removed element.
+	 */
+	protected abstract T removeInternal(@Nonnegative int elementIndex);
+
+	/**
+	 * Implements how to add an element to the queue.
+	 *
+	 * @param toAdd the element to add.
+	 */
+	protected abstract void addInternal(@Nonnull T toAdd);
+
+	/**
+	 * Returns the start index of the queue elements in the array.
+	 */
+	protected abstract int getHeadElementIndex();
+
+	private static boolean isValidArraySize(int size) {
+		return size >= 0 && size <= MAX_ARRAY_SIZE;
+	}
+
+	/**
+	 * {@link Iterator} implementation for {@link HeapPriorityQueue}.
+	 * {@link Iterator#remove()} is not supported.
+	 */
+	private final class HeapIterator implements CloseableIterator<T> {
+
+		private int runningIdx;
+		private final int endIdx;
+
+		HeapIterator() {
+			this.runningIdx = getHeadElementIndex();
+			this.endIdx = runningIdx + size;
+		}
+
+		@Override
+		public boolean hasNext() {
+			return runningIdx < endIdx;
+		}
+
+		@Override
+		public T next() {
+			if (runningIdx >= endIdx) {
+				throw new NoSuchElementException("Iterator has no next element.");
+			}
+			return queue[runningIdx++];
+		}
+
+		@Override
+		public void close() {
+		}
+	}
+}
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/CachingInternalPriorityQueueSet.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/CachingInternalPriorityQueueSet.java
deleted file mode 100644
index b1ad0df6d5e..00000000000
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/CachingInternalPriorityQueueSet.java
+++ /dev/null
@@ -1,356 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.flink.runtime.state.heap;
-
-import org.apache.flink.runtime.state.InternalPriorityQueue;
-import org.apache.flink.util.CloseableIterator;
-import org.apache.flink.util.FlinkRuntimeException;
-
-import javax.annotation.Nonnegative;
-import javax.annotation.Nonnull;
-import javax.annotation.Nullable;
-
-import java.util.Collection;
-import java.util.function.Consumer;
-import java.util.function.Predicate;
-
-import static org.apache.flink.runtime.state.heap.KeyGroupPartitionedPriorityQueue.ENABLE_RELAXED_FIRING_ORDER_OPTIMIZATION;
-
-/**
- * This class is an implementation of a {@link InternalPriorityQueue} with set semantics that internally consists of
- * two different storage types. The first storage is a (potentially slow) ordered set store manages the ground truth
- * about the elements in this queue. The second storage is a (fast) ordered set cache, typically with some limited
- * capacity. The cache is used to improve performance of accesses to the underlying store and contains an ordered
- * (partial) view on the top elements in the ordered store. We are currently applying simple write-through to keep cache
- * and store in sync on updates and refill the cache from the store when it is empty and we expect more elements
- * contained in the store.
- *
- * @param <E> the type if the managed elements.
- */
-public class CachingInternalPriorityQueueSet<E> implements InternalPriorityQueue<E>, HeapPriorityQueueElement {
-
-	/** A ordered set cache that contains a (partial) view on the top elements in the ordered store. */
-	@Nonnull
-	private final OrderedSetCache<E> orderedCache;
-
-	/** A store with ordered set semantics that contains the ground truth of all inserted elements. */
-	@Nonnull
-	private final OrderedSetStore<E> orderedStore;
-
-	/** This flag is true if there could be elements in the backend that are not in the cache (false positives ok). */
-	private boolean storeOnlyElements;
-
-	/** Management data for the {@link HeapPriorityQueueElement} trait. */
-	private int pqManagedIndex;
-
-	@SuppressWarnings("unchecked")
-	public CachingInternalPriorityQueueSet(
-		@Nonnull OrderedSetCache<E> orderedCache,
-		@Nonnull OrderedSetStore<E> orderedStore) {
-		this.orderedCache = orderedCache;
-		this.orderedStore = orderedStore;
-		// We are careful and set this to true. Could be set to false if we know for sure that the store is empty, but
-		// checking this could be an expensive operation.
-		this.storeOnlyElements = true;
-		this.pqManagedIndex = HeapPriorityQueueElement.NOT_CONTAINED;
-	}
-
-	@Nullable
-	@Override
-	public E peek() {
-
-		checkRefillCacheFromStore();
-
-		return orderedCache.peekFirst();
-	}
-
-	@Override
-	public void bulkPoll(@Nonnull Predicate<E> canConsume, @Nonnull Consumer<E> consumer) {
-		if (ENABLE_RELAXED_FIRING_ORDER_OPTIMIZATION) {
-			bulkPollRelaxedOrder(canConsume, consumer);
-		} else {
-			bulkPollStrictOrder(canConsume, consumer);
-		}
-	}
-
-	private void bulkPollRelaxedOrder(@Nonnull Predicate<E> canConsume, @Nonnull Consumer<E> consumer) {
-		if (orderedCache.isEmpty()) {
-			bulkPollStore(canConsume, consumer);
-		} else {
-			while (!orderedCache.isEmpty() && canConsume.test(orderedCache.peekFirst())) {
-				final E next = orderedCache.removeFirst();
-				orderedStore.remove(next);
-				consumer.accept(next);
-			}
-
-			if (orderedCache.isEmpty()) {
-				bulkPollStore(canConsume, consumer);
-			}
-		}
-	}
-
-	private void bulkPollStrictOrder(@Nonnull Predicate<E> canConsume, @Nonnull Consumer<E> consumer) {
-		E element;
-		while ((element = peek()) != null && canConsume.test(element)) {
-			poll();
-			consumer.accept(element);
-		}
-	}
-
-	private void bulkPollStore(@Nonnull Predicate<E> canConsume, @Nonnull Consumer<E> consumer) {
-		try (CloseableIterator<E> iterator = orderedStore.orderedIterator()) {
-			while (iterator.hasNext()) {
-				final E next = iterator.next();
-				if (canConsume.test(next)) {
-					orderedStore.remove(next);
-					consumer.accept(next);
-				} else {
-					orderedCache.add(next);
-					while (iterator.hasNext() && !orderedCache.isFull()) {
-						orderedCache.add(iterator.next());
-					}
-					break;
-				}
-			}
-		} catch (Exception e) {
-			throw new FlinkRuntimeException("Exception while bulk polling store.", e);
-		}
-	}
-
-	@Nullable
-	@Override
-	public E poll() {
-
-		checkRefillCacheFromStore();
-
-		final E first = orderedCache.removeFirst();
-
-		if (first != null) {
-			// write-through sync
-			orderedStore.remove(first);
-		}
-
-		return first;
-	}
-
-	@Override
-	public boolean add(@Nonnull E toAdd) {
-
-		checkRefillCacheFromStore();
-
-		// write-through sync
-		orderedStore.add(toAdd);
-
-		final boolean cacheFull = orderedCache.isFull();
-
-		if ((!cacheFull && !storeOnlyElements) || orderedCache.isInLowerBound(toAdd)) {
-
-			if (cacheFull) {
-				// we drop the element with lowest priority from the cache
-				orderedCache.removeLast();
-				// the dropped element is now only in the store
-				storeOnlyElements = true;
-			}
-
-			orderedCache.add(toAdd);
-			return toAdd.equals(orderedCache.peekFirst());
-		} else {
-			// we only added to the store
-			storeOnlyElements = true;
-			return false;
-		}
-	}
-
-	@Override
-	public boolean remove(@Nonnull E toRemove) {
-
-		checkRefillCacheFromStore();
-
-		boolean newHead = toRemove.equals(orderedCache.peekFirst());
-		// write-through sync
-		orderedStore.remove(toRemove);
-		orderedCache.remove(toRemove);
-		return newHead;
-	}
-
-	@Override
-	public void addAll(@Nullable Collection<? extends E> toAdd) {
-
-		if (toAdd == null) {
-			return;
-		}
-
-		for (E element : toAdd) {
-			add(element);
-		}
-	}
-
-	@Override
-	public int size() {
-		return orderedStore.size();
-	}
-
-	@Override
-	public boolean isEmpty() {
-		checkRefillCacheFromStore();
-		return orderedCache.isEmpty();
-	}
-
-	@Nonnull
-	@Override
-	public CloseableIterator<E> iterator() {
-		if (storeOnlyElements) {
-			return orderedStore.orderedIterator();
-		} else {
-			return orderedCache.orderedIterator();
-		}
-	}
-
-	@Override
-	public int getInternalIndex() {
-		return pqManagedIndex;
-	}
-
-	@Override
-	public void setInternalIndex(int updateIndex) {
-		this.pqManagedIndex = updateIndex;
-	}
-
-	/**
-	 * Refills the cache from the store when the cache is empty and we expect more elements in the store.
-	 *
-	 * TODO: We can think about exploiting the property that the store is already sorted when bulk-filling the cache.
-	 */
-	private void checkRefillCacheFromStore() {
-		if (storeOnlyElements && orderedCache.isEmpty()) {
-			try (final CloseableIterator<E> iterator = orderedStore.orderedIterator()) {
-				while (iterator.hasNext() && !orderedCache.isFull()) {
-					orderedCache.add(iterator.next());
-				}
-				storeOnlyElements = iterator.hasNext();
-			} catch (Exception e) {
-				throw new FlinkRuntimeException("Exception while refilling store from iterator.", e);
-			}
-		}
-	}
-
-	/**
-	 * Interface for an ordered cache with set semantics of elements to be used in
-	 * {@link CachingInternalPriorityQueueSet}. Cache implementations typically have a limited capacity as indicated
-	 * via the {@link #isFull()} method.
-	 *
-	 * @param <E> the type of contained elements.
-	 */
-	public interface OrderedSetCache<E> {
-
-		/**
-		 * Adds the given element to the cache (if not yet contained). This method should only be called if the cache
-		 * is not full.
-		 * @param element element to add to the cache.
-		 */
-		void add(@Nonnull E element);
-
-		/**
-		 * Removes the given element from the cache (if contained).
-		 * @param element element to remove from the cache.
-		 */
-		void remove(@Nonnull E element);
-
-		/**
-		 * Returns <code>true</code> if the cache is full and no more elements can be added.
-		 */
-		boolean isFull();
-
-		/**
-		 * Returns <code>true</code> if the cache is empty, i.e. contains ne elements.
-		 */
-		boolean isEmpty();
-
-		/**
-		 * Returns true, if the element is compares smaller than the currently largest element in the cache.
-		 */
-		boolean isInLowerBound(@Nonnull E toCheck);
-
-		/**
-		 * Removes and returns the first (smallest) element from the cache.
-		 */
-		@Nullable
-		E removeFirst();
-
-		/**
-		 * Removes and returns the last (larges) element from the cache.
-		 */
-		@Nullable
-		E removeLast();
-
-		/**
-		 * Returns the first (smallest) element from the cache (without removing it).
-		 */
-		@Nullable
-		E peekFirst();
-
-		/**
-		 * Returns the last (larges) element from the cache (without removing it).
-		 */
-		@Nullable
-		E peekLast();
-
-		/**
-		 * Returns an iterator over the store that returns element in order. The iterator must be closed by the client
-		 * after usage.
-		 */
-		@Nonnull
-		CloseableIterator<E> orderedIterator();
-	}
-
-	/**
-	 * Interface for an ordered store with set semantics of elements to be used in
-	 * {@link CachingInternalPriorityQueueSet}. Stores are assumed to have (practically) unlimited capacity, but their
-	 * operations could all be expensive.
-	 *
-	 * @param <E> the type of contained elements.
-	 */
-	public interface OrderedSetStore<E> {
-
-		/**
-		 * Adds the given element to the store (if not yet contained).
-		 * @param element element to add to the store.
-		 */
-		void add(@Nonnull E element);
-
-		/**
-		 * Removed the given element from the cache (if contained).
-		 * @param element element to remove from the cache.
-		 */
-		void remove(@Nonnull E element);
-
-		/**
-		 * Returns the number of elements in the store.
-		 */
-		@Nonnegative
-		int size();
-
-		/**
-		 * Returns an iterator over the store that returns element in order. The iterator must be closed by the client
-		 * after usage.
-		 */
-		@Nonnull
-		CloseableIterator<E> orderedIterator();
-	}
-}
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapKeyedStateBackend.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapKeyedStateBackend.java
index 2c6101ed943..34c9698bc8e 100644
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapKeyedStateBackend.java
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapKeyedStateBackend.java
@@ -28,6 +28,7 @@
 import org.apache.flink.api.common.state.State;
 import org.apache.flink.api.common.state.StateDescriptor;
 import org.apache.flink.api.common.state.ValueStateDescriptor;
+import org.apache.flink.api.common.typeutils.CompatibilityResult;
 import org.apache.flink.api.common.typeutils.CompatibilityUtil;
 import org.apache.flink.api.common.typeutils.TypeSerializer;
 import org.apache.flink.api.common.typeutils.UnloadableDummyTypeSerializer;
@@ -79,6 +80,7 @@
 
 import javax.annotation.Nonnull;
 
+import java.io.IOException;
 import java.io.InputStream;
 import java.io.OutputStream;
 import java.util.ArrayList;
@@ -111,60 +113,15 @@
 			Tuple2.of(FoldingStateDescriptor.class, (StateFactory) HeapFoldingState::create)
 		).collect(Collectors.toMap(t -> t.f0, t -> t.f1));
 
-	@SuppressWarnings("unchecked")
-	@Nonnull
-	@Override
-	public <T extends HeapPriorityQueueElement & PriorityComparable & Keyed> KeyGroupedInternalPriorityQueue<T> create(
-		@Nonnull String stateName,
-		@Nonnull TypeSerializer<T> byteOrderedElementSerializer) {
-
-		final StateSnapshotRestore snapshotRestore = registeredStates.get(stateName);
-
-		if (snapshotRestore instanceof HeapPriorityQueueSnapshotRestoreWrapper) {
-			//TODO Serializer upgrade story!?
-			return ((HeapPriorityQueueSnapshotRestoreWrapper<T>) snapshotRestore).getPriorityQueue();
-		} else if (snapshotRestore != null) {
-			throw new IllegalStateException("Already found a different state type registered under this name: " + snapshotRestore.getClass());
-		}
-
-		final RegisteredPriorityQueueStateBackendMetaInfo<T> metaInfo =
-			new RegisteredPriorityQueueStateBackendMetaInfo<>(stateName, byteOrderedElementSerializer);
-
-		return createInternal(metaInfo);
-	}
-
-	@Nonnull
-	private <T extends HeapPriorityQueueElement & PriorityComparable & Keyed> KeyGroupedInternalPriorityQueue<T> createInternal(
-		RegisteredPriorityQueueStateBackendMetaInfo<T> metaInfo) {
-
-		final String stateName = metaInfo.getName();
-		final HeapPriorityQueueSet<T> priorityQueue = priorityQueueSetFactory.create(
-			stateName,
-			metaInfo.getElementSerializer());
-
-		HeapPriorityQueueSnapshotRestoreWrapper<T> wrapper =
-			new HeapPriorityQueueSnapshotRestoreWrapper<>(
-				priorityQueue,
-				metaInfo,
-				KeyExtractorFunction.forKeyedObjects(),
-				keyGroupRange,
-				numberOfKeyGroups);
-
-		registeredStates.put(stateName, wrapper);
-		return priorityQueue;
-	}
-
-	private interface StateFactory {
-		<K, N, SV, S extends State, IS extends S> IS createState(
-			StateDescriptor<S, SV> stateDesc,
-			StateTable<K, N, SV> stateTable,
-			TypeSerializer<K> keySerializer) throws Exception;
-	}
+	/**
+	 * Map of registered Key/Value states.
+	 */
+	private final Map<String, StateTable<K, ?, ?>> registeredKVStates;
 
 	/**
-	 * Map of registered states for snapshot/restore.
+	 * Map of registered priority queue set states.
 	 */
-	private final Map<String, StateSnapshotRestore> registeredStates = new HashMap<>();
+	private final Map<String, HeapPriorityQueueSnapshotRestoreWrapper> registeredPQStates;
 
 	/**
 	 * Map of state names to their corresponding restored state meta info.
@@ -172,7 +129,7 @@
 	 * <p>TODO this map can be removed when eager-state registration is in place.
 	 * TODO we currently need this cached to check state migration strategies when new serializers are registered.
 	 */
-	private final Map<String, StateMetaInfoSnapshot> restoredKvStateMetaInfos;
+	private final Map<StateUID, StateMetaInfoSnapshot> restoredStateMetaInfo;
 
 	/**
 	 * The configuration for local recovery.
@@ -203,6 +160,9 @@ public HeapKeyedStateBackend(
 
 		super(kvStateRegistry, keySerializer, userCodeClassLoader,
 			numberOfKeyGroups, keyGroupRange, executionConfig, ttlTimeProvider);
+
+		this.registeredKVStates = new HashMap<>();
+		this.registeredPQStates = new HashMap<>();
 		this.localRecoveryConfig = Preconditions.checkNotNull(localRecoveryConfig);
 
 		SnapshotStrategySynchronicityBehavior<K> synchronicityTrait = asynchronousSnapshots ?
@@ -211,7 +171,7 @@ public HeapKeyedStateBackend(
 
 		this.snapshotStrategy = new HeapSnapshotStrategy(synchronicityTrait);
 		LOG.info("Initializing heap keyed state backend with stream factory.");
-		this.restoredKvStateMetaInfos = new HashMap<>();
+		this.restoredStateMetaInfo = new HashMap<>();
 		this.priorityQueueSetFactory = priorityQueueSetFactory;
 	}
 
@@ -219,17 +179,85 @@ public HeapKeyedStateBackend(
 	//  state backend operations
 	// ------------------------------------------------------------------------
 
+	@SuppressWarnings("unchecked")
+	@Nonnull
+	@Override
+	public <T extends HeapPriorityQueueElement & PriorityComparable & Keyed> KeyGroupedInternalPriorityQueue<T> create(
+		@Nonnull String stateName,
+		@Nonnull TypeSerializer<T> byteOrderedElementSerializer) {
+
+		final HeapPriorityQueueSnapshotRestoreWrapper existingState = registeredPQStates.get(stateName);
+
+		if (existingState != null) {
+			// TODO we implement the simple way of supporting the current functionality, mimicking keyed state
+			// because this should be reworked in FLINK-9376 and then we should have a common algorithm over
+			// StateMetaInfoSnapshot that avoids this code duplication.
+			StateMetaInfoSnapshot restoredMetaInfoSnapshot =
+				restoredStateMetaInfo.get(StateUID.of(stateName, StateMetaInfoSnapshot.BackendStateType.PRIORITY_QUEUE));
+
+			Preconditions.checkState(
+				restoredMetaInfoSnapshot != null,
+				"Requested to check compatibility of a restored RegisteredKeyedBackendStateMetaInfo," +
+					" but its corresponding restored snapshot cannot be found.");
+
+			StateMetaInfoSnapshot.CommonSerializerKeys serializerKey =
+				StateMetaInfoSnapshot.CommonSerializerKeys.VALUE_SERIALIZER;
+
+			CompatibilityResult<T> compatibilityResult = CompatibilityUtil.resolveCompatibilityResult(
+				restoredMetaInfoSnapshot.getTypeSerializer(serializerKey),
+				null,
+				restoredMetaInfoSnapshot.getTypeSerializerConfigSnapshot(serializerKey),
+				byteOrderedElementSerializer);
+
+			if (compatibilityResult.isRequiresMigration()) {
+				throw new FlinkRuntimeException(StateMigrationException.notSupported());
+			} else {
+				registeredPQStates.put(
+					stateName,
+					existingState.forUpdatedSerializer(byteOrderedElementSerializer));
+			}
+
+			return existingState.getPriorityQueue();
+		} else {
+			final RegisteredPriorityQueueStateBackendMetaInfo<T> metaInfo =
+				new RegisteredPriorityQueueStateBackendMetaInfo<>(stateName, byteOrderedElementSerializer);
+			return createInternal(metaInfo);
+		}
+	}
+
+	@Nonnull
+	private <T extends HeapPriorityQueueElement & PriorityComparable & Keyed> KeyGroupedInternalPriorityQueue<T> createInternal(
+		RegisteredPriorityQueueStateBackendMetaInfo<T> metaInfo) {
+
+		final String stateName = metaInfo.getName();
+		final HeapPriorityQueueSet<T> priorityQueue = priorityQueueSetFactory.create(
+			stateName,
+			metaInfo.getElementSerializer());
+
+		HeapPriorityQueueSnapshotRestoreWrapper<T> wrapper =
+			new HeapPriorityQueueSnapshotRestoreWrapper<>(
+				priorityQueue,
+				metaInfo,
+				KeyExtractorFunction.forKeyedObjects(),
+				keyGroupRange,
+				numberOfKeyGroups);
+
+		registeredPQStates.put(stateName, wrapper);
+		return priorityQueue;
+	}
+
 	private <N, V> StateTable<K, N, V> tryRegisterStateTable(
 			TypeSerializer<N> namespaceSerializer, StateDescriptor<?, V> stateDesc) throws StateMigrationException {
 
 		@SuppressWarnings("unchecked")
-		StateTable<K, N, V> stateTable = (StateTable<K, N, V>) registeredStates.get(stateDesc.getName());
+		StateTable<K, N, V> stateTable = (StateTable<K, N, V>) registeredKVStates.get(stateDesc.getName());
 
 		RegisteredKeyValueStateBackendMetaInfo<N, V> newMetaInfo;
 		if (stateTable != null) {
 			@SuppressWarnings("unchecked")
 			StateMetaInfoSnapshot restoredMetaInfoSnapshot =
-				restoredKvStateMetaInfos.get(stateDesc.getName());
+				restoredStateMetaInfo.get(
+					StateUID.of(stateDesc.getName(), StateMetaInfoSnapshot.BackendStateType.KEY_VALUE));
 
 			Preconditions.checkState(
 				restoredMetaInfoSnapshot != null,
@@ -250,7 +278,7 @@ public HeapKeyedStateBackend(
 				stateDesc.getSerializer());
 
 			stateTable = snapshotStrategy.newStateTable(newMetaInfo);
-			registeredStates.put(stateDesc.getName(), stateTable);
+			registeredKVStates.put(stateDesc.getName(), stateTable);
 		}
 
 		return stateTable;
@@ -259,20 +287,17 @@ public HeapKeyedStateBackend(
 	@SuppressWarnings("unchecked")
 	@Override
 	public <N> Stream<K> getKeys(String state, N namespace) {
-		if (!registeredStates.containsKey(state)) {
+		if (!registeredKVStates.containsKey(state)) {
 			return Stream.empty();
 		}
 
-		final StateSnapshotRestore stateSnapshotRestore = registeredStates.get(state);
-		if (!(stateSnapshotRestore instanceof StateTable)) {
-			return Stream.empty();
-		}
+		final StateSnapshotRestore stateSnapshotRestore = registeredKVStates.get(state);
 		StateTable<K, N, ?> table = (StateTable<K, N, ?>) stateSnapshotRestore;
 		return table.getKeys(namespace);
 	}
 
 	private boolean hasRegisteredState() {
-		return !registeredStates.isEmpty();
+		return !(registeredKVStates.isEmpty() && registeredPQStates.isEmpty());
 	}
 
 	@Override
@@ -318,9 +343,9 @@ public void restore(Collection<KeyedStateHandle> restoredState) throws Exception
 	@SuppressWarnings({"unchecked"})
 	private void restorePartitionedState(Collection<KeyedStateHandle> state) throws Exception {
 
-		final Map<Integer, String> kvStatesById = new HashMap<>();
-		int numRegisteredKvStates = 0;
-		registeredStates.clear();
+		final Map<Integer, StateMetaInfoSnapshot> kvStatesById = new HashMap<>();
+		registeredKVStates.clear();
+		registeredPQStates.clear();
 
 		boolean keySerializerRestored = false;
 
@@ -369,70 +394,131 @@ private void restorePartitionedState(Collection<KeyedStateHandle> state) throws
 				}
 
 				List<StateMetaInfoSnapshot> restoredMetaInfos =
-						serializationProxy.getStateMetaInfoSnapshots();
-
-				for (StateMetaInfoSnapshot restoredMetaInfo : restoredMetaInfos) {
-					restoredKvStateMetaInfos.put(restoredMetaInfo.getName(), restoredMetaInfo);
-
-					StateSnapshotRestore snapshotRestore = registeredStates.get(restoredMetaInfo.getName());
+					serializationProxy.getStateMetaInfoSnapshots();
 
-					//important: only create a new table we did not already create it previously
-					if (null == snapshotRestore) {
+				createOrCheckStateForMetaInfo(restoredMetaInfos, kvStatesById);
 
-						if (restoredMetaInfo.getBackendStateType() == StateMetaInfoSnapshot.BackendStateType.KEY_VALUE) {
-							RegisteredKeyValueStateBackendMetaInfo<?, ?> registeredKeyedBackendStateMetaInfo =
-								new RegisteredKeyValueStateBackendMetaInfo<>(restoredMetaInfo);
-
-							snapshotRestore = snapshotStrategy.newStateTable(registeredKeyedBackendStateMetaInfo);
-							registeredStates.put(restoredMetaInfo.getName(), snapshotRestore);
-						} else {
-							createInternal(new RegisteredPriorityQueueStateBackendMetaInfo<>(restoredMetaInfo));
-						}
-						kvStatesById.put(numRegisteredKvStates, restoredMetaInfo.getName());
-						++numRegisteredKvStates;
-					} else {
-						// TODO with eager state registration in place, check here for serializer migration strategies
-					}
+				readStateHandleStateData(
+					fsDataInputStream,
+					inView,
+					keyGroupsStateHandle.getGroupRangeOffsets(),
+					kvStatesById, restoredMetaInfos.size(),
+					serializationProxy.getReadVersion(),
+					serializationProxy.isUsingKeyGroupCompression());
+			} finally {
+				if (cancelStreamRegistry.unregisterCloseable(fsDataInputStream)) {
+					IOUtils.closeQuietly(fsDataInputStream);
 				}
+			}
+		}
+	}
 
-				final StreamCompressionDecorator streamCompressionDecorator = serializationProxy.isUsingKeyGroupCompression() ?
-					SnappyStreamCompressionDecorator.INSTANCE : UncompressedStreamCompressionDecorator.INSTANCE;
+	private void readStateHandleStateData(
+		FSDataInputStream fsDataInputStream,
+		DataInputViewStreamWrapper inView,
+		KeyGroupRangeOffsets keyGroupOffsets,
+		Map<Integer, StateMetaInfoSnapshot> kvStatesById,
+		int numStates,
+		int readVersion,
+		boolean isCompressed) throws IOException {
 
-				for (Tuple2<Integer, Long> groupOffset : keyGroupsStateHandle.getGroupRangeOffsets()) {
-					int keyGroupIndex = groupOffset.f0;
-					long offset = groupOffset.f1;
+		final StreamCompressionDecorator streamCompressionDecorator = isCompressed ?
+			SnappyStreamCompressionDecorator.INSTANCE : UncompressedStreamCompressionDecorator.INSTANCE;
 
-					// Check that restored key groups all belong to the backend.
-					Preconditions.checkState(keyGroupRange.contains(keyGroupIndex), "The key group must belong to the backend.");
+		for (Tuple2<Integer, Long> groupOffset : keyGroupOffsets) {
+			int keyGroupIndex = groupOffset.f0;
+			long offset = groupOffset.f1;
 
-					fsDataInputStream.seek(offset);
+			// Check that restored key groups all belong to the backend.
+			Preconditions.checkState(keyGroupRange.contains(keyGroupIndex), "The key group must belong to the backend.");
 
-					int writtenKeyGroupIndex = inView.readInt();
+			fsDataInputStream.seek(offset);
 
-					try (InputStream kgCompressionInStream =
-							streamCompressionDecorator.decorateWithCompression(fsDataInputStream)) {
+			int writtenKeyGroupIndex = inView.readInt();
+			Preconditions.checkState(writtenKeyGroupIndex == keyGroupIndex,
+				"Unexpected key-group in restore.");
 
-						DataInputViewStreamWrapper kgCompressionInView =
-							new DataInputViewStreamWrapper(kgCompressionInStream);
+			try (InputStream kgCompressionInStream =
+					 streamCompressionDecorator.decorateWithCompression(fsDataInputStream)) {
 
-						Preconditions.checkState(writtenKeyGroupIndex == keyGroupIndex,
-							"Unexpected key-group in restore.");
+				readKeyGroupStateData(
+					kgCompressionInStream,
+					kvStatesById,
+					keyGroupIndex,
+					numStates,
+					readVersion);
+			}
+		}
+	}
 
-						for (int i = 0; i < restoredMetaInfos.size(); i++) {
-							int kvStateId = kgCompressionInView.readShort();
-							StateSnapshotRestore registeredState = registeredStates.get(kvStatesById.get(kvStateId));
+	private void readKeyGroupStateData(
+		InputStream inputStream,
+		Map<Integer, StateMetaInfoSnapshot> kvStatesById,
+		int keyGroupIndex,
+		int numStates,
+		int readVersion) throws IOException {
+
+		DataInputViewStreamWrapper inView =
+			new DataInputViewStreamWrapper(inputStream);
+
+		for (int i = 0; i < numStates; i++) {
+
+			final int kvStateId = inView.readShort();
+			final StateMetaInfoSnapshot stateMetaInfoSnapshot = kvStatesById.get(kvStateId);
+			final StateSnapshotRestore registeredState;
+
+			switch (stateMetaInfoSnapshot.getBackendStateType()) {
+				case KEY_VALUE:
+					registeredState = registeredKVStates.get(stateMetaInfoSnapshot.getName());
+					break;
+				case PRIORITY_QUEUE:
+					registeredState = registeredPQStates.get(stateMetaInfoSnapshot.getName());
+					break;
+				default:
+					throw new IllegalStateException("Unexpected state type: " +
+						stateMetaInfoSnapshot.getBackendStateType() + ".");
+			}
 
-							StateSnapshotKeyGroupReader keyGroupReader =
-								registeredState.keyGroupReader(serializationProxy.getReadVersion());
+			StateSnapshotKeyGroupReader keyGroupReader = registeredState.keyGroupReader(readVersion);
+			keyGroupReader.readMappingsInKeyGroup(inView, keyGroupIndex);
+		}
+	}
 
-							keyGroupReader.readMappingsInKeyGroup(kgCompressionInView, keyGroupIndex);
-						}
+	private void createOrCheckStateForMetaInfo(
+		List<StateMetaInfoSnapshot> restoredMetaInfo,
+		Map<Integer, StateMetaInfoSnapshot> kvStatesById) {
+
+		for (StateMetaInfoSnapshot metaInfoSnapshot : restoredMetaInfo) {
+			restoredStateMetaInfo.put(
+				StateUID.of(metaInfoSnapshot.getName(), metaInfoSnapshot.getBackendStateType()),
+				metaInfoSnapshot);
+
+			final StateSnapshotRestore registeredState;
+
+			switch (metaInfoSnapshot.getBackendStateType()) {
+				case KEY_VALUE:
+					registeredState = registeredKVStates.get(metaInfoSnapshot.getName());
+					if (registeredState == null) {
+						RegisteredKeyValueStateBackendMetaInfo<?, ?> registeredKeyedBackendStateMetaInfo =
+							new RegisteredKeyValueStateBackendMetaInfo<>(metaInfoSnapshot);
+						registeredKVStates.put(
+							metaInfoSnapshot.getName(),
+							snapshotStrategy.newStateTable(registeredKeyedBackendStateMetaInfo));
 					}
-				}
-			} finally {
-				if (cancelStreamRegistry.unregisterCloseable(fsDataInputStream)) {
-					IOUtils.closeQuietly(fsDataInputStream);
-				}
+					break;
+				case PRIORITY_QUEUE:
+					registeredState = registeredPQStates.get(metaInfoSnapshot.getName());
+					if (registeredState == null) {
+						createInternal(new RegisteredPriorityQueueStateBackendMetaInfo<>(metaInfoSnapshot));
+					}
+					break;
+				default:
+					throw new IllegalStateException("Unexpected state type: " +
+						metaInfoSnapshot.getBackendStateType() + ".");
+			}
+
+			if (registeredState == null) {
+				kvStatesById.put(kvStatesById.size(), metaInfoSnapshot);
 			}
 		}
 	}
@@ -478,12 +564,10 @@ public String toString() {
 	@VisibleForTesting
 	@SuppressWarnings("unchecked")
 	@Override
-	public int numStateEntries() {
+	public int numKeyValueStateEntries() {
 		int sum = 0;
-		for (StateSnapshotRestore state : registeredStates.values()) {
-			if (state instanceof StateTable) {
-				sum += ((StateTable<?, ?, ?>) state).size();
-			}
+		for (StateSnapshotRestore state : registeredKVStates.values()) {
+			sum += ((StateTable<?, ?, ?>) state).size();
 		}
 		return sum;
 	}
@@ -492,12 +576,10 @@ public int numStateEntries() {
 	 * Returns the total number of state entries across all keys for the given namespace.
 	 */
 	@VisibleForTesting
-	public int numStateEntries(Object namespace) {
+	public int numKeyValueStateEntries(Object namespace) {
 		int sum = 0;
-		for (StateSnapshotRestore state : registeredStates.values()) {
-			if (state instanceof StateTable) {
-				sum += ((StateTable<?, ?, ?>) state).sizeOfNamespace(namespace);
-			}
+		for (StateTable<?, ?, ?> state : registeredKVStates.values()) {
+			sum += state.sizeOfNamespace(namespace);
 		}
 		return sum;
 	}
@@ -574,7 +656,7 @@ public boolean isAsynchronous() {
 
 		private final SnapshotStrategySynchronicityBehavior<K> snapshotStrategySynchronicityTrait;
 
-		public HeapSnapshotStrategy(
+		HeapSnapshotStrategy(
 			SnapshotStrategySynchronicityBehavior<K> snapshotStrategySynchronicityTrait) {
 			this.snapshotStrategySynchronicityTrait = snapshotStrategySynchronicityTrait;
 		}
@@ -592,28 +674,31 @@ public HeapSnapshotStrategy(
 
 			long syncStartTime = System.currentTimeMillis();
 
-			Preconditions.checkState(registeredStates.size() <= Short.MAX_VALUE,
-				"Too many KV-States: " + registeredStates.size() +
-					". Currently at most " + Short.MAX_VALUE + " states are supported");
-
-			List<StateMetaInfoSnapshot> metaInfoSnapshots =
-				new ArrayList<>(registeredStates.size());
+			int numStates = registeredKVStates.size() + registeredPQStates.size();
 
-			final Map<String, Integer> kVStateToId = new HashMap<>(registeredStates.size());
+			Preconditions.checkState(numStates <= Short.MAX_VALUE,
+				"Too many states: " + numStates +
+					". Currently at most " + Short.MAX_VALUE + " states are supported");
 
-			final Map<String, StateSnapshot> cowStateStableSnapshots =
-				new HashMap<>(registeredStates.size());
-
-			for (Map.Entry<String, StateSnapshotRestore> kvState : registeredStates.entrySet()) {
-				String stateName = kvState.getKey();
-				kVStateToId.put(stateName, kVStateToId.size());
-				StateSnapshotRestore state = kvState.getValue();
-				if (null != state) {
-					final StateSnapshot stateSnapshot = state.stateSnapshot();
-					metaInfoSnapshots.add(stateSnapshot.getMetaInfoSnapshot());
-					cowStateStableSnapshots.put(stateName, stateSnapshot);
-				}
-			}
+			final List<StateMetaInfoSnapshot> metaInfoSnapshots = new ArrayList<>(numStates);
+			final Map<StateUID, Integer> stateNamesToId =
+				new HashMap<>(numStates);
+			final Map<StateUID, StateSnapshot> cowStateStableSnapshots =
+				new HashMap<>(numStates);
+
+			processSnapshotMetaInfoForAllStates(
+				metaInfoSnapshots,
+				cowStateStableSnapshots,
+				stateNamesToId,
+				registeredKVStates,
+				StateMetaInfoSnapshot.BackendStateType.KEY_VALUE);
+
+			processSnapshotMetaInfoForAllStates(
+				metaInfoSnapshots,
+				cowStateStableSnapshots,
+				stateNamesToId,
+				registeredPQStates,
+				StateMetaInfoSnapshot.BackendStateType.PRIORITY_QUEUE);
 
 			final KeyedBackendSerializationProxy<K> serializationProxy =
 				new KeyedBackendSerializationProxy<>(
@@ -692,13 +777,14 @@ private void unregisterAndCloseStreamAndResultExtractor() {
 							keyGroupRangeOffsets[keyGroupPos] = localStream.getPos();
 							outView.writeInt(keyGroupId);
 
-							for (Map.Entry<String, StateSnapshot> kvState : cowStateStableSnapshots.entrySet()) {
+							for (Map.Entry<StateUID, StateSnapshot> stateSnapshot :
+								cowStateStableSnapshots.entrySet()) {
 								StateSnapshot.StateKeyGroupWriter partitionedSnapshot =
-									kvState.getValue().getKeyGroupWriter();
+
+									stateSnapshot.getValue().getKeyGroupWriter();
 								try (OutputStream kgCompressionOut = keyGroupCompressionDecorator.decorateWithCompression(localStream)) {
-									String stateName = kvState.getKey();
 									DataOutputViewStreamWrapper kgCompressionView = new DataOutputViewStreamWrapper(kgCompressionOut);
-									kgCompressionView.writeShort(kVStateToId.get(stateName));
+									kgCompressionView.writeShort(stateNamesToId.get(stateSnapshot.getKey()));
 									partitionedSnapshot.writeStateInKeyGroup(kgCompressionView, keyGroupId);
 								} // this will just close the outer compression stream
 							}
@@ -747,5 +833,80 @@ public boolean isAsynchronous() {
 		public <N, V> StateTable<K, N, V> newStateTable(RegisteredKeyValueStateBackendMetaInfo<N, V> newMetaInfo) {
 			return snapshotStrategySynchronicityTrait.newStateTable(newMetaInfo);
 		}
+
+		private void processSnapshotMetaInfoForAllStates(
+			List<StateMetaInfoSnapshot> metaInfoSnapshots,
+			Map<StateUID, StateSnapshot> cowStateStableSnapshots,
+			Map<StateUID, Integer> stateNamesToId,
+			Map<String, ? extends StateSnapshotRestore> registeredStates,
+			StateMetaInfoSnapshot.BackendStateType stateType) {
+
+			for (Map.Entry<String, ? extends StateSnapshotRestore> kvState : registeredStates.entrySet()) {
+				final StateUID stateUid = StateUID.of(kvState.getKey(), stateType);
+				stateNamesToId.put(stateUid, stateNamesToId.size());
+				StateSnapshotRestore state = kvState.getValue();
+				if (null != state) {
+					final StateSnapshot stateSnapshot = state.stateSnapshot();
+					metaInfoSnapshots.add(stateSnapshot.getMetaInfoSnapshot());
+					cowStateStableSnapshots.put(stateUid, stateSnapshot);
+				}
+			}
+		}
+	}
+
+	private interface StateFactory {
+		<K, N, SV, S extends State, IS extends S> IS createState(
+			StateDescriptor<S, SV> stateDesc,
+			StateTable<K, N, SV> stateTable,
+			TypeSerializer<K> keySerializer) throws Exception;
+	}
+
+	/**
+	 * Unique identifier for registered state in this backend.
+	 */
+	private static final class StateUID {
+
+		@Nonnull
+		private final String stateName;
+
+		@Nonnull
+		private final StateMetaInfoSnapshot.BackendStateType stateType;
+
+		StateUID(@Nonnull String stateName, @Nonnull StateMetaInfoSnapshot.BackendStateType stateType) {
+			this.stateName = stateName;
+			this.stateType = stateType;
+		}
+
+		@Nonnull
+		public String getStateName() {
+			return stateName;
+		}
+
+		@Nonnull
+		public StateMetaInfoSnapshot.BackendStateType getStateType() {
+			return stateType;
+		}
+
+		@Override
+		public boolean equals(Object o) {
+			if (this == o) {
+				return true;
+			}
+			if (o == null || getClass() != o.getClass()) {
+				return false;
+			}
+			StateUID uid = (StateUID) o;
+			return Objects.equals(getStateName(), uid.getStateName()) &&
+				getStateType() == uid.getStateType();
+		}
+
+		@Override
+		public int hashCode() {
+			return Objects.hash(getStateName(), getStateType());
+		}
+
+		public static StateUID of(@Nonnull String stateName, @Nonnull StateMetaInfoSnapshot.BackendStateType stateType) {
+			return new StateUID(stateName, stateType);
+		}
 	}
 }
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueue.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueue.java
index 22b24197e84..2dd57010fea 100644
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueue.java
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueue.java
@@ -18,22 +18,10 @@
 
 package org.apache.flink.runtime.state.heap;
 
-import org.apache.flink.runtime.state.InternalPriorityQueue;
 import org.apache.flink.runtime.state.PriorityComparator;
-import org.apache.flink.util.CloseableIterator;
 
 import javax.annotation.Nonnegative;
 import javax.annotation.Nonnull;
-import javax.annotation.Nullable;
-
-import java.util.Arrays;
-import java.util.Collection;
-import java.util.Iterator;
-import java.util.NoSuchElementException;
-import java.util.function.Consumer;
-import java.util.function.Predicate;
-
-import static org.apache.flink.util.CollectionUtil.MAX_ARRAY_SIZE;
 
 /**
  * Basic heap-based priority queue for {@link HeapPriorityQueueElement} objects. This heap supports fast deletes
@@ -51,7 +39,7 @@
  * @param <T> type of the contained elements.
  */
 public class HeapPriorityQueue<T extends HeapPriorityQueueElement>
-	implements InternalPriorityQueue<T> {
+	extends AbstractHeapPriorityQueue<T> {
 
 	/**
 	 * The index of the head element in the array that represents the heap.
@@ -61,17 +49,8 @@
 	/**
 	 * Comparator for the priority of contained elements.
 	 */
-	private final PriorityComparator<T> elementPriorityComparator;
-
-	/**
-	 * The array that represents the heap-organized priority queue.
-	 */
-	private T[] queue;
-
-	/**
-	 * The current size of the priority queue.
-	 */
-	private int size;
+	@Nonnull
+	protected final PriorityComparator<T> elementPriorityComparator;
 
 	/**
 	 * Creates an empty {@link HeapPriorityQueue} with the requested initial capacity.
@@ -83,124 +62,31 @@
 	public HeapPriorityQueue(
 		@Nonnull PriorityComparator<T> elementPriorityComparator,
 		@Nonnegative int minimumCapacity) {
-
+		super(minimumCapacity);
 		this.elementPriorityComparator = elementPriorityComparator;
-		this.queue = (T[]) new HeapPriorityQueueElement[QUEUE_HEAD_INDEX + minimumCapacity];
 	}
 
-	@Override
-	public void bulkPoll(@Nonnull Predicate<T> canConsume, @Nonnull Consumer<T> consumer) {
-		T element;
-		while ((element = peek()) != null && canConsume.test(element)) {
-			poll();
-			consumer.accept(element);
+	public void adjustModifiedElement(@Nonnull T element) {
+		final int elementIndex = element.getInternalIndex();
+		if (element == queue[elementIndex]) {
+			adjustElementAtIndex(element, elementIndex);
 		}
 	}
 
 	@Override
-	@Nullable
-	public T poll() {
-		return size() > 0 ? removeElementAtIndex(QUEUE_HEAD_INDEX) : null;
-	}
-
-	@Override
-	@Nullable
-	public T peek() {
-		return size() > 0 ? queue[QUEUE_HEAD_INDEX] : null;
-	}
-
-	/**
-	 * Adds the element to add to the heap. This element should not be managed by any other {@link HeapPriorityQueue}.
-	 *
-	 * @return <code>true</code> if the operation changed the head element or if is it unclear if the head element changed.
-	 * Only returns <code>false</code> iff the head element was not changed by this operation.
-	 */
-	@Override
-	public boolean add(@Nonnull T toAdd) {
-		return addInternal(toAdd);
-	}
-
-	/**
-	 * This remove is based on object identity, not the result of equals. We use the objects managed index to find
-	 * the instance in the queue array.
-	 *
-	 * @return <code>true</code> if the operation changed the head element or if is it unclear if the head element changed.
-	 * Only returns <code>false</code> iff the head element was not changed by this operation.
-	 */
-	@Override
-	public boolean remove(@Nonnull T toRemove) {
-		return removeInternal(toRemove);
-	}
-
-	@Override
-	public boolean isEmpty() {
-		return size() == 0;
-	}
-
-	@Override
-	@Nonnegative
-	public int size() {
-		return size;
-	}
-
-	public void clear() {
-		size = 0;
-		Arrays.fill(queue, null);
-	}
-
-	@SuppressWarnings({"unchecked"})
-	@Nonnull
-	public <O> O[] toArray(O[] out) {
-		if (out.length < size) {
-			return (O[]) Arrays.copyOfRange(queue, QUEUE_HEAD_INDEX, QUEUE_HEAD_INDEX + size, out.getClass());
-		} else {
-			System.arraycopy(queue, QUEUE_HEAD_INDEX, out, 0, size);
-			if (out.length > size) {
-				out[size] = null;
-			}
-			return out;
-		}
-	}
-
-	/**
-	 * Returns an iterator over the elements in this queue. The iterator
-	 * does not return the elements in any particular order.
-	 *
-	 * @return an iterator over the elements in this queue.
-	 */
-	@Nonnull
-	public CloseableIterator<T> iterator() {
-		return new HeapIterator();
+	protected int getHeadElementIndex() {
+		return QUEUE_HEAD_INDEX;
 	}
 
 	@Override
-	public void addAll(@Nullable Collection<? extends T> restoredElements) {
-
-		if (restoredElements == null) {
-			return;
-		}
-
-		resizeForBulkLoad(restoredElements.size());
-
-		for (T element : restoredElements) {
-			add(element);
-		}
-	}
-
-	private boolean addInternal(@Nonnull T element) {
+	protected void addInternal(@Nonnull T element) {
 		final int newSize = increaseSizeByOne();
 		moveElementToIdx(element, newSize);
 		siftUp(newSize);
-		return element.getInternalIndex() == QUEUE_HEAD_INDEX;
 	}
 
-	private boolean removeInternal(@Nonnull T elementToRemove) {
-		final int elementIndex = elementToRemove.getInternalIndex();
-		removeElementAtIndex(elementIndex);
-		return elementIndex == QUEUE_HEAD_INDEX;
-	}
-
-	private T removeElementAtIndex(int removeIdx) {
+	@Override
+	protected T removeInternal(int removeIdx) {
 		T[] heap = this.queue;
 		T removedValue = heap[removeIdx];
 
@@ -220,13 +106,6 @@ private T removeElementAtIndex(int removeIdx) {
 		return removedValue;
 	}
 
-	public void adjustModifiedElement(@Nonnull T element) {
-		final int elementIndex = element.getInternalIndex();
-		if (element == queue[elementIndex]) {
-			adjustElementAtIndex(element, elementIndex);
-		}
-	}
-
 	private void adjustElementAtIndex(T element, int index) {
 		siftDown(index);
 		if (queue[index] == element) {
@@ -285,11 +164,6 @@ private boolean isElementPriorityLessThen(T a, T b) {
 		return elementPriorityComparator.comparePriority(a, b) < 0;
 	}
 
-	private void moveElementToIdx(T element, int idx) {
-		queue[idx] = element;
-		element.setInternalIndex(idx);
-	}
-
 	private int increaseSizeByOne() {
 		final int oldArraySize = queue.length;
 		final int minRequiredNewSize = ++size;
@@ -300,56 +174,4 @@ private int increaseSizeByOne() {
 		// TODO implement shrinking as well?
 		return minRequiredNewSize;
 	}
-
-	private void resizeForBulkLoad(int totalSize) {
-		if (totalSize > queue.length) {
-			int desiredSize = totalSize + (totalSize >>> 3);
-			resizeQueueArray(desiredSize, totalSize);
-		}
-	}
-
-	private void resizeQueueArray(int desiredSize, int minRequiredSize) {
-		if (isValidArraySize(desiredSize)) {
-			queue = Arrays.copyOf(queue, desiredSize);
-		} else if (isValidArraySize(minRequiredSize)) {
-			queue = Arrays.copyOf(queue, MAX_ARRAY_SIZE);
-		} else {
-			throw new OutOfMemoryError("Required minimum heap size " + minRequiredSize +
-				" exceeds maximum size of " + MAX_ARRAY_SIZE + ".");
-		}
-	}
-
-	private static boolean isValidArraySize(int size) {
-		return size >= 0 && size <= MAX_ARRAY_SIZE;
-	}
-
-	/**
-	 * {@link Iterator} implementation for {@link HeapPriorityQueue}.
-	 * {@link Iterator#remove()} is not supported.
-	 */
-	private class HeapIterator implements CloseableIterator<T> {
-
-		private int iterationIdx;
-
-		HeapIterator() {
-			this.iterationIdx = QUEUE_HEAD_INDEX - 1;
-		}
-
-		@Override
-		public boolean hasNext() {
-			return iterationIdx < size;
-		}
-
-		@Override
-		public T next() {
-			if (iterationIdx >= size) {
-				throw new NoSuchElementException("Iterator has no next element.");
-			}
-			return queue[++iterationIdx];
-		}
-
-		@Override
-		public void close() {
-		}
-	}
 }
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSet.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSet.java
index 79f319c8d8a..c0215acb06c 100644
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSet.java
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSet.java
@@ -106,11 +106,7 @@ public HeapPriorityQueueSet(
 	@Nullable
 	public T poll() {
 		final T toRemove = super.poll();
-		if (toRemove != null) {
-			return getDedupMapForElement(toRemove).remove(toRemove);
-		} else {
-			return null;
-		}
+		return toRemove != null ? getDedupMapForElement(toRemove).remove(toRemove) : null;
 	}
 
 	/**
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSetFactory.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSetFactory.java
index b0255d3afad..80d79ac1fc1 100644
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSetFactory.java
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSetFactory.java
@@ -59,7 +59,7 @@ public HeapPriorityQueueSetFactory(
 		@Nonnull String stateName,
 		@Nonnull TypeSerializer<T> byteOrderedElementSerializer) {
 
-		return new HeapPriorityQueueSet<T>(
+		return new HeapPriorityQueueSet<>(
 			PriorityComparator.forPriorityComparableObjects(),
 			KeyExtractorFunction.forKeyedObjects(),
 			minimumCapacity,
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSnapshotRestoreWrapper.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSnapshotRestoreWrapper.java
index 5fd67f07be1..fc1e0db3360 100644
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSnapshotRestoreWrapper.java
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/HeapPriorityQueueSnapshotRestoreWrapper.java
@@ -68,16 +68,6 @@ public HeapPriorityQueueSnapshotRestoreWrapper(
 	@Override
 	public StateSnapshot stateSnapshot() {
 		final T[] queueDump = (T[]) priorityQueue.toArray(new HeapPriorityQueueElement[priorityQueue.size()]);
-
-		final TypeSerializer<T> elementSerializer = metaInfo.getElementSerializer();
-
-		// turn the flat copy into a deep copy if required.
-		if (!elementSerializer.isImmutableType()) {
-			for (int i = 0; i < queueDump.length; ++i) {
-				queueDump[i] = elementSerializer.copy(queueDump[i]);
-			}
-		}
-
 		return new HeapPriorityQueueStateSnapshot<>(
 			queueDump,
 			keyExtractorFunction,
@@ -99,4 +89,26 @@ public StateSnapshotKeyGroupReader keyGroupReader(int readVersionHint) {
 	public HeapPriorityQueueSet<T> getPriorityQueue() {
 		return priorityQueue;
 	}
+
+	@Nonnull
+	public RegisteredPriorityQueueStateBackendMetaInfo<T> getMetaInfo() {
+		return metaInfo;
+	}
+
+	/**
+	 * Returns a deep copy of the snapshot, where the serializer is changed to the given serializer.
+	 */
+	public HeapPriorityQueueSnapshotRestoreWrapper<T> forUpdatedSerializer(
+		@Nonnull TypeSerializer<T> updatedSerializer) {
+
+		RegisteredPriorityQueueStateBackendMetaInfo<T> updatedMetaInfo =
+			new RegisteredPriorityQueueStateBackendMetaInfo<>(metaInfo.getName(), updatedSerializer);
+
+		return new HeapPriorityQueueSnapshotRestoreWrapper<>(
+			priorityQueue,
+			updatedMetaInfo,
+			keyExtractorFunction,
+			localKeyGroupRange,
+			totalKeyGroups);
+	}
 }
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/KeyGroupPartitionedPriorityQueue.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/KeyGroupPartitionedPriorityQueue.java
index d8b0a5a6628..79787644e0d 100644
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/KeyGroupPartitionedPriorityQueue.java
+++ b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/KeyGroupPartitionedPriorityQueue.java
@@ -35,8 +35,6 @@
 import java.util.Collection;
 import java.util.HashSet;
 import java.util.Set;
-import java.util.function.Consumer;
-import java.util.function.Predicate;
 
 /**
  * This implementation of {@link InternalPriorityQueue} is internally partitioned into sub-queues per key-group and
@@ -49,11 +47,9 @@
 public class KeyGroupPartitionedPriorityQueue<T, PQ extends InternalPriorityQueue<T> & HeapPriorityQueueElement>
 	implements InternalPriorityQueue<T>, KeyGroupedInternalPriorityQueue<T> {
 
-	static final boolean ENABLE_RELAXED_FIRING_ORDER_OPTIMIZATION = false;
-
 	/** A heap of heap sets. Each sub-heap represents the partition for a key-group.*/
 	@Nonnull
-	private final HeapPriorityQueue<PQ> heapOfkeyGroupedHeaps;
+	private final HeapPriorityQueue<PQ> heapOfKeyGroupedHeaps;
 
 	/** All elements from keyGroupHeap, indexed by their key-group id, relative to firstKeyGroup. */
 	@Nonnull
@@ -83,55 +79,30 @@ public KeyGroupPartitionedPriorityQueue(
 		this.totalKeyGroups = totalKeyGroups;
 		this.firstKeyGroup = keyGroupRange.getStartKeyGroup();
 		this.keyGroupedHeaps = (PQ[]) new InternalPriorityQueue[keyGroupRange.getNumberOfKeyGroups()];
-		this.heapOfkeyGroupedHeaps = new HeapPriorityQueue<>(
+		this.heapOfKeyGroupedHeaps = new HeapPriorityQueue<>(
 			new InternalPriorityQueueComparator<>(elementPriorityComparator),
 			keyGroupRange.getNumberOfKeyGroups());
 		for (int i = 0; i < keyGroupedHeaps.length; i++) {
 			final PQ keyGroupSubHeap =
-				orderedCacheFactory.create(firstKeyGroup + i, totalKeyGroups, elementPriorityComparator);
+				orderedCacheFactory.create(firstKeyGroup + i, totalKeyGroups, keyExtractor, elementPriorityComparator);
 			keyGroupedHeaps[i] = keyGroupSubHeap;
-			heapOfkeyGroupedHeaps.add(keyGroupSubHeap);
-		}
-	}
-
-	@Override
-	public void bulkPoll(@Nonnull Predicate<T> canConsume, @Nonnull Consumer<T> consumer) {
-		if (ENABLE_RELAXED_FIRING_ORDER_OPTIMIZATION) {
-			bulkPollRelaxedOrder(canConsume, consumer);
-		} else {
-			bulkPollStrictOrder(canConsume, consumer);
-		}
-	}
-
-	private void bulkPollRelaxedOrder(@Nonnull Predicate<T> canConsume, @Nonnull Consumer<T> consumer) {
-		PQ headList = heapOfkeyGroupedHeaps.peek();
-		while (headList.peek() != null && canConsume.test(headList.peek())) {
-			headList.bulkPoll(canConsume, consumer);
-			heapOfkeyGroupedHeaps.adjustModifiedElement(headList);
-		}
-	}
-
-	private void bulkPollStrictOrder(@Nonnull Predicate<T> canConsume, @Nonnull Consumer<T> consumer) {
-		T element;
-		while ((element = peek()) != null && canConsume.test(element)) {
-			poll();
-			consumer.accept(element);
+			heapOfKeyGroupedHeaps.add(keyGroupSubHeap);
 		}
 	}
 
 	@Nullable
 	@Override
 	public T poll() {
-		final PQ headList = heapOfkeyGroupedHeaps.peek();
+		final PQ headList = heapOfKeyGroupedHeaps.peek();
 		final T head = headList.poll();
-		heapOfkeyGroupedHeaps.adjustModifiedElement(headList);
+		heapOfKeyGroupedHeaps.adjustModifiedElement(headList);
 		return head;
 	}
 
 	@Nullable
 	@Override
 	public T peek() {
-		return heapOfkeyGroupedHeaps.peek().peek();
+		return heapOfKeyGroupedHeaps.peek().peek();
 	}
 
 	@Override
@@ -140,7 +111,7 @@ public boolean add(@Nonnull T toAdd) {
 
 		// the branch checks if the head element has (potentially) changed.
 		if (list.add(toAdd)) {
-			heapOfkeyGroupedHeaps.adjustModifiedElement(list);
+			heapOfKeyGroupedHeaps.adjustModifiedElement(list);
 			// could we have a new head?
 			return toAdd.equals(peek());
 		} else {
@@ -157,7 +128,7 @@ public boolean remove(@Nonnull T toRemove) {
 
 		// the branch checks if the head element has (potentially) changed.
 		if (list.remove(toRemove)) {
-			heapOfkeyGroupedHeaps.adjustModifiedElement(list);
+			heapOfKeyGroupedHeaps.adjustModifiedElement(list);
 			// could we have a new head?
 			return toRemove.equals(oldHead);
 		} else {
@@ -330,6 +301,7 @@ public int comparePriority(Q o1, Q o2) {
 		PQS create(
 			@Nonnegative int keyGroupId,
 			@Nonnegative int numKeyGroups,
+			@Nonnull KeyExtractorFunction<T> keyExtractorFunction,
 			@Nonnull PriorityComparator<T> elementPriorityComparator);
 	}
 }
diff --git a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/TreeOrderedSetCache.java b/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/TreeOrderedSetCache.java
deleted file mode 100644
index 14c281effc9..00000000000
--- a/flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/TreeOrderedSetCache.java
+++ /dev/null
@@ -1,135 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.flink.runtime.state.heap;
-
-import org.apache.flink.util.CloseableIterator;
-import org.apache.flink.util.Preconditions;
-
-import it.unimi.dsi.fastutil.objects.ObjectAVLTreeSet;
-
-import javax.annotation.Nonnegative;
-import javax.annotation.Nonnull;
-import javax.annotation.Nullable;
-
-import java.util.Comparator;
-
-/**
- * Implementation of {@link org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet.OrderedSetCache} based
- * on an AVL-Tree. We chose the implementation from fastutil over JDK for performance reasons.
- *
- * <p>Maintainer notes: We can consider the following potential performance improvements. First, we could introduce a
- * bulk-load method to OrderedSetCache to exploit the fact that adding from an OrderedSetStore is already happening in
- * sorted order, e.g. there are more efficient ways to construct search trees from sorted elements. Second, we could
- * replace the internal AVL-Tree with an extended variant of {@link HeapPriorityQueueSet} that is organized as a
- * Min-Max-Heap.
- *
- * @param <E> type of the contained elements.
- */
-public class TreeOrderedSetCache<E> implements CachingInternalPriorityQueueSet.OrderedSetCache<E> {
-
-	/** The tree is used to store cached elements. */
-	@Nonnull
-	private final ObjectAVLTreeSet<E> avlTree;
-
-	/** The element comparator. */
-	@Nonnull
-	private final Comparator<E> elementComparator;
-
-	/** The maximum capacity of the cache. */
-	@Nonnegative
-	private final int capacity;
-
-	/**
-	 * Creates a new {@link TreeOrderedSetCache} with the given capacity and element comparator. Capacity must be > 0.
-	 * @param elementComparator comparator for the cached elements.
-	 * @param capacity the capacity of the cache. Must be > 0.
-	 */
-	public TreeOrderedSetCache(@Nonnull Comparator<E> elementComparator, @Nonnegative int capacity) {
-		Preconditions.checkArgument(capacity > 0, "Cache capacity must be greater than 0.");
-		this.avlTree = new ObjectAVLTreeSet<>(elementComparator);
-		this.elementComparator = elementComparator;
-		this.capacity = capacity;
-	}
-
-	@Override
-	public void add(@Nonnull E element) {
-		assert !isFull();
-		avlTree.add(element);
-	}
-
-	@Override
-	public void remove(@Nonnull E element) {
-		avlTree.remove(element);
-	}
-
-	@Override
-	public boolean isFull() {
-		return avlTree.size() == capacity;
-	}
-
-	@Override
-	public boolean isEmpty() {
-		return avlTree.isEmpty();
-	}
-
-	@Override
-	public boolean isInLowerBound(@Nonnull E toCheck) {
-		return avlTree.isEmpty() || elementComparator.compare(peekLast(), toCheck) > 0;
-	}
-
-	@Nullable
-	@Override
-	public E removeFirst() {
-		if (avlTree.isEmpty()) {
-			return null;
-		}
-		final E first = avlTree.first();
-		avlTree.remove(first);
-		return first;
-	}
-
-	@Nullable
-	@Override
-	public E removeLast() {
-		if (avlTree.isEmpty()) {
-			return null;
-		}
-		final E last = avlTree.last();
-		avlTree.remove(last);
-		return last;
-	}
-
-	@Nullable
-	@Override
-	public E peekFirst() {
-		return !avlTree.isEmpty() ? avlTree.first() : null;
-	}
-
-	@Nullable
-	@Override
-	public E peekLast() {
-		return !avlTree.isEmpty() ? avlTree.last() : null;
-	}
-
-	@Nonnull
-	@Override
-	public CloseableIterator<E> orderedIterator() {
-		return CloseableIterator.adapterForIterator(avlTree.iterator());
-	}
-}
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/InternalPriorityQueueTestBase.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/InternalPriorityQueueTestBase.java
index 0cd551ca0e5..935ebb69c92 100644
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/InternalPriorityQueueTestBase.java
+++ b/flink-runtime/src/test/java/org/apache/flink/runtime/state/InternalPriorityQueueTestBase.java
@@ -21,13 +21,17 @@
 import org.apache.flink.api.common.typeutils.CompatibilityResult;
 import org.apache.flink.api.common.typeutils.TypeSerializer;
 import org.apache.flink.api.common.typeutils.TypeSerializerConfigSnapshot;
+import org.apache.flink.core.memory.ByteArrayOutputStreamWithPos;
 import org.apache.flink.core.memory.DataInputView;
 import org.apache.flink.core.memory.DataOutputView;
+import org.apache.flink.core.memory.DataOutputViewStreamWrapper;
 import org.apache.flink.runtime.state.heap.HeapPriorityQueueElement;
 import org.apache.flink.util.CloseableIterator;
 import org.apache.flink.util.MathUtils;
 import org.apache.flink.util.TestLogger;
 
+import org.apache.flink.shaded.guava18.com.google.common.primitives.UnsignedBytes;
+
 import org.junit.Assert;
 import org.junit.Test;
 
@@ -35,6 +39,7 @@
 
 import java.io.IOException;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Comparator;
 import java.util.HashSet;
 import java.util.Iterator;
@@ -53,14 +58,15 @@
 	protected static final KeyExtractorFunction<TestElement> KEY_EXTRACTOR_FUNCTION = TestElement::getKey;
 	protected static final PriorityComparator<TestElement> TEST_ELEMENT_PRIORITY_COMPARATOR =
 		(left, right) -> Long.compare(left.getPriority(), right.getPriority());
-	protected static final Comparator<TestElement> TEST_ELEMENT_COMPARATOR = (o1, o2) -> {
-		int priorityCmp = TEST_ELEMENT_PRIORITY_COMPARATOR.comparePriority(o1, o2);
-		if (priorityCmp != 0) {
-			return priorityCmp;
-		}
-		// to fully comply with compareTo/equals contract.
-		return Long.compare(o1.getKey(), o2.getKey());
-	};
+	protected static final Comparator<TestElement> TEST_ELEMENT_COMPARATOR = new TestElementComparator();
+
+	protected Comparator<Long> getTestElementPriorityComparator() {
+		return Long::compareTo;
+	}
+
+	private long getHighestPriorityValueForComparator() {
+		return getTestElementPriorityComparator().compare(-1L , 1L) > 0 ? Long.MAX_VALUE : Long.MIN_VALUE;
+	}
 
 	protected static void insertRandomElements(
 		@Nonnull InternalPriorityQueue<TestElement> priorityQueue,
@@ -107,13 +113,14 @@ protected static void insertRandomElements(
 	public void testPeekPollOrder() {
 		final int initialCapacity = 4;
 		final int testSize = 1000;
+		final Comparator<Long> comparator = getTestElementPriorityComparator();
 		InternalPriorityQueue<TestElement> priorityQueue =
 			newPriorityQueue(initialCapacity);
 		HashSet<TestElement> checkSet = new HashSet<>(testSize);
 
 		insertRandomElements(priorityQueue, checkSet, testSize);
 
-		long lastPriorityValue = Long.MIN_VALUE;
+		long lastPriorityValue = getHighestPriorityValueForComparator();
 		int lastSize = priorityQueue.size();
 		Assert.assertEquals(testSize, lastSize);
 		TestElement testElement;
@@ -122,7 +129,7 @@ public void testPeekPollOrder() {
 			Assert.assertEquals(lastSize, priorityQueue.size());
 			Assert.assertEquals(testElement, priorityQueue.poll());
 			Assert.assertTrue(checkSet.remove(testElement));
-			Assert.assertTrue(testElement.getPriority() >= lastPriorityValue);
+			Assert.assertTrue(comparator.compare(testElement.getPriority(), lastPriorityValue) >= 0);
 			lastPriorityValue = testElement.getPriority();
 			--lastSize;
 		}
@@ -136,7 +143,7 @@ public void testPeekPollOrder() {
 	public void testRemoveInsertMixKeepsOrder() {
 
 		InternalPriorityQueue<TestElement> priorityQueue = newPriorityQueue(3);
-
+		final Comparator<Long> comparator = getTestElementPriorityComparator();
 		final ThreadLocalRandom random = ThreadLocalRandom.current();
 		final int testSize = 300;
 		final int addCounterMax = testSize / 4;
@@ -148,6 +155,8 @@ public void testRemoveInsertMixKeepsOrder() {
 		// check that the whole set is still in order
 		while (!checkSet.isEmpty()) {
 
+			final long highestPrioValue = getHighestPriorityValueForComparator();
+
 			Iterator<TestElement> iterator = checkSet.iterator();
 			TestElement element = iterator.next();
 			iterator.remove();
@@ -160,16 +169,23 @@ public void testRemoveInsertMixKeepsOrder() {
 				priorityQueue.remove(element);
 			}
 
-			long lastPriorityValue = removesHead ? element.getPriority() : Long.MIN_VALUE;
+			long currentPriorityWatermark;
+
+			// test some bulk polling from time to time
+			if (removesHead) {
+				currentPriorityWatermark = element.getPriority();
+			} else {
+				currentPriorityWatermark = highestPrioValue;
+			}
 
 			while ((element = priorityQueue.poll()) != null) {
-				Assert.assertTrue(element.getPriority() >= lastPriorityValue);
-				lastPriorityValue = element.getPriority();
+				Assert.assertTrue(comparator.compare(element.getPriority(), currentPriorityWatermark) >= 0);
+				currentPriorityWatermark = element.getPriority();
 				if (--iterationsTillNextAdds == 0) {
 					// some random adds
 					iterationsTillNextAdds = random.nextInt(addCounterMax);
 					insertRandomElements(priorityQueue, new HashSet<>(checkSet), 1 + random.nextInt(3));
-					lastPriorityValue = priorityQueue.peek().getPriority();
+					currentPriorityWatermark = priorityQueue.peek().getPriority();
 				}
 			}
 
@@ -182,6 +198,7 @@ public void testRemoveInsertMixKeepsOrder() {
 	@Test
 	public void testPoll() {
 		InternalPriorityQueue<TestElement> priorityQueue = newPriorityQueue(3);
+		final Comparator<Long> comparator = getTestElementPriorityComparator();
 
 		Assert.assertNull(priorityQueue.poll());
 
@@ -189,12 +206,12 @@ public void testPoll() {
 		HashSet<TestElement> checkSet = new HashSet<>(testSize);
 		insertRandomElements(priorityQueue, checkSet, testSize);
 
-		long lastPriorityValue = Long.MIN_VALUE;
+		long lastPriorityValue = getHighestPriorityValueForComparator();
 		while (!priorityQueue.isEmpty()) {
 			TestElement removed = priorityQueue.poll();
 			Assert.assertNotNull(removed);
 			Assert.assertTrue(checkSet.remove(removed));
-			Assert.assertTrue(removed.getPriority() >= lastPriorityValue);
+			Assert.assertTrue(comparator.compare(removed.getPriority(), lastPriorityValue) >= 0);
 			lastPriorityValue = removed.getPriority();
 		}
 		Assert.assertTrue(checkSet.isEmpty());
@@ -286,18 +303,21 @@ public void testAdd() {
 		InternalPriorityQueue<TestElement> priorityQueue =
 			newPriorityQueue(1);
 
-		TestElement lowPrioElement = new TestElement(4711L, 42L);
-		TestElement highPrioElement = new TestElement(815L, 23L);
-		Assert.assertTrue(priorityQueue.add(lowPrioElement));
+		final List<TestElement> testElements =
+			Arrays.asList(new TestElement(4711L, 42L), new TestElement(815L, 23L));
+
+		testElements.sort((l, r) -> getTestElementPriorityComparator().compare(r.priority, l.priority));
+
+		Assert.assertTrue(priorityQueue.add(testElements.get(0)));
 		if (testSetSemanticsAgainstDuplicateElements()) {
-			priorityQueue.add(lowPrioElement.deepCopy());
+			priorityQueue.add(testElements.get(0).deepCopy());
 		}
 		Assert.assertEquals(1, priorityQueue.size());
-		Assert.assertTrue(priorityQueue.add(highPrioElement));
+		Assert.assertTrue(priorityQueue.add(testElements.get(1)));
 		Assert.assertEquals(2, priorityQueue.size());
-		Assert.assertEquals(highPrioElement, priorityQueue.poll());
+		Assert.assertEquals(testElements.get(1), priorityQueue.poll());
 		Assert.assertEquals(1, priorityQueue.size());
-		Assert.assertEquals(lowPrioElement, priorityQueue.poll());
+		Assert.assertEquals(testElements.get(0), priorityQueue.poll());
 		Assert.assertEquals(0, priorityQueue.size());
 	}
 
@@ -327,7 +347,7 @@ public void testRemove() {
 	/**
 	 * Payload for usage in the test.
 	 */
-	protected static class TestElement implements HeapPriorityQueueElement {
+	protected static class TestElement implements HeapPriorityQueueElement, Keyed<Long>, PriorityComparable<TestElement> {
 
 		private final long key;
 		private final long priority;
@@ -339,7 +359,12 @@ public TestElement(long key, long priority) {
 			this.internalIndex = NOT_CONTAINED;
 		}
 
-		public long getKey() {
+		@Override
+		public int comparePriorityTo(@Nonnull TestElement other) {
+			return Long.compare(priority, other.priority);
+		}
+
+		public Long getKey() {
 			return key;
 		}
 
@@ -366,8 +391,8 @@ public boolean equals(Object o) {
 				return false;
 			}
 			TestElement that = (TestElement) o;
-			return getKey() == that.getKey() &&
-				getPriority() == that.getPriority();
+			return key == that.key &&
+				priority == that.priority;
 		}
 
 		@Override
@@ -378,6 +403,14 @@ public int hashCode() {
 		public TestElement deepCopy() {
 			return new TestElement(key, priority);
 		}
+
+		@Override
+		public String toString() {
+			return "TestElement{" +
+				"key=" + key +
+				", priority=" + priority +
+				'}';
+		}
 	}
 
 	/**
@@ -386,9 +419,11 @@ public TestElement deepCopy() {
 	 */
 	protected static class TestElementSerializer extends TypeSerializer<TestElement> {
 
+		private static final int REVISION = 1;
+
 		public static final TestElementSerializer INSTANCE = new TestElementSerializer();
 
-		private TestElementSerializer() {
+		protected TestElementSerializer() {
 		}
 
 		@Override
@@ -461,14 +496,85 @@ public int hashCode() {
 			return 4711;
 		}
 
+		protected int getRevision() {
+			return REVISION;
+		}
+
 		@Override
 		public TypeSerializerConfigSnapshot snapshotConfiguration() {
-			throw new UnsupportedOperationException();
+			return new Snapshot(getRevision());
 		}
 
 		@Override
 		public CompatibilityResult<TestElement> ensureCompatibility(TypeSerializerConfigSnapshot configSnapshot) {
-			throw new UnsupportedOperationException();
+			return (configSnapshot instanceof Snapshot) && ((Snapshot) configSnapshot).revision <= getRevision() ?
+				CompatibilityResult.compatible() : CompatibilityResult.requiresMigration();
+		}
+
+		public static class Snapshot extends TypeSerializerConfigSnapshot {
+
+			private int revision;
+
+			public Snapshot() {
+			}
+
+			public Snapshot(int revision) {
+				this.revision = revision;
+			}
+
+			@Override
+			public boolean equals(Object obj) {
+				return obj instanceof Snapshot && revision == ((Snapshot) obj).revision;
+			}
+
+			@Override
+			public int hashCode() {
+				return revision;
+			}
+
+			@Override
+			public int getVersion() {
+				return 0;
+			}
+
+			public int getRevision() {
+				return revision;
+			}
+
+			@Override
+			public void write(DataOutputView out) throws IOException {
+				super.write(out);
+				out.writeInt(revision);
+			}
+
+			@Override
+			public void read(DataInputView in) throws IOException {
+				super.read(in);
+				this.revision = in.readInt();
+			}
+		}
+	}
+
+	/**
+	 * Comparator for test elements, operating on the serialized bytes of the elements.
+	 */
+	protected static class TestElementComparator implements Comparator<TestElement> {
+
+		@Override
+		public int compare(TestElement o1, TestElement o2) {
+
+			ByteArrayOutputStreamWithPos os = new ByteArrayOutputStreamWithPos();
+			DataOutputViewStreamWrapper ow = new DataOutputViewStreamWrapper(os);
+			try {
+				TestElementSerializer.INSTANCE.serialize(o1, ow);
+				byte[] a1 = os.toByteArray();
+				os.reset();
+				TestElementSerializer.INSTANCE.serialize(o2, ow);
+				byte[] a2 = os.toByteArray();
+				return UnsignedBytes.lexicographicalComparator().compare(a1, a2);
+			} catch (Exception e) {
+				throw new RuntimeException(e);
+			}
 		}
 	}
 }
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/MemoryStateBackendTest.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/MemoryStateBackendTest.java
index 0ba4c33bd0f..215d7d36c96 100644
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/MemoryStateBackendTest.java
+++ b/flink-runtime/src/test/java/org/apache/flink/runtime/state/MemoryStateBackendTest.java
@@ -33,6 +33,7 @@
 import org.apache.flink.runtime.state.memory.MemoryStateBackend;
 import org.apache.flink.testutils.ArtificialCNFExceptionThrowingClassLoader;
 import org.apache.flink.util.FutureUtil;
+
 import org.junit.Assert;
 import org.junit.Ignore;
 import org.junit.Test;
@@ -154,6 +155,7 @@ public void testOperatorStateRestoreFailsIfSerializerDeserializationFails() thro
 	@Test
 	public void testKeyedStateRestoreFailsIfSerializerDeserializationFails() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		KeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 		ValueStateDescriptor<String> kvId = new ValueStateDescriptor<>("id", String.class, null);
@@ -161,7 +163,7 @@ public void testKeyedStateRestoreFailsIfSerializerDeserializationFails() throws
 
 		HeapKeyedStateBackend<Integer> heapBackend = (HeapKeyedStateBackend<Integer>) backend;
 
-		assertEquals(0, heapBackend.numStateEntries());
+		assertEquals(0, heapBackend.numKeyValueStateEntries());
 
 		ValueState<String> state = backend.getPartitionedState(VoidNamespace.INSTANCE, VoidNamespaceSerializer.INSTANCE, kvId);
 
@@ -170,11 +172,13 @@ public void testKeyedStateRestoreFailsIfSerializerDeserializationFails() throws
 		state.update("hello");
 		state.update("ciao");
 
-		KeyedStateHandle snapshot = runSnapshot(((HeapKeyedStateBackend<Integer>) backend).snapshot(
-			682375462378L,
-			2,
-			streamFactory,
-			CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot = runSnapshot(
+			((HeapKeyedStateBackend<Integer>) backend).snapshot(
+				682375462378L,
+				2,
+				streamFactory,
+				CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		backend.dispose();
 
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/StateBackendTestBase.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/StateBackendTestBase.java
index bfdc05d2747..059a706c6a8 100644
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/StateBackendTestBase.java
+++ b/flink-runtime/src/test/java/org/apache/flink/runtime/state/StateBackendTestBase.java
@@ -50,7 +50,10 @@
 import org.apache.flink.api.java.typeutils.runtime.PojoSerializer;
 import org.apache.flink.api.java.typeutils.runtime.kryo.JavaSerializer;
 import org.apache.flink.api.java.typeutils.runtime.kryo.KryoSerializer;
+import org.apache.flink.core.memory.ByteArrayInputStreamWithPos;
+import org.apache.flink.core.memory.ByteArrayOutputStreamWithPos;
 import org.apache.flink.core.memory.DataInputView;
+import org.apache.flink.core.memory.DataInputViewStreamWrapper;
 import org.apache.flink.core.memory.DataOutputView;
 import org.apache.flink.core.memory.DataOutputViewStreamWrapper;
 import org.apache.flink.core.testutils.CheckedThread;
@@ -77,6 +80,7 @@
 import org.apache.flink.runtime.util.BlockerCheckpointStreamFactory;
 import org.apache.flink.testutils.ArtificialCNFExceptionThrowingClassLoader;
 import org.apache.flink.types.IntValue;
+import org.apache.flink.util.ExceptionUtils;
 import org.apache.flink.util.IOUtils;
 import org.apache.flink.util.StateMigrationException;
 import org.apache.flink.util.TestLogger;
@@ -87,6 +91,7 @@
 import com.esotericsoftware.kryo.io.Input;
 import com.esotericsoftware.kryo.io.Output;
 import org.apache.commons.io.output.ByteArrayOutputStream;
+import org.junit.Assert;
 import org.junit.Rule;
 import org.junit.Test;
 import org.junit.rules.ExpectedException;
@@ -295,6 +300,7 @@ public void testGetKeys() throws Exception {
 	public void testBackendUsesRegisteredKryoDefaultSerializer() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
 		Environment env = new DummyEnvironment();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE, env);
 
 		// cast because our test serializer is not typed to TestPojo
@@ -330,7 +336,9 @@ public void testBackendUsesRegisteredKryoDefaultSerializer() throws Exception {
 
 		try {
 			// backends that lazily serializes (such as memory state backend) will fail here
-			runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+			runSnapshot(
+				backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 		} catch (ExpectedKryoTestException e) {
 			numExceptions++;
 		} catch (Exception e) {
@@ -350,6 +358,7 @@ public void testBackendUsesRegisteredKryoDefaultSerializer() throws Exception {
 	public void testBackendUsesRegisteredKryoDefaultSerializerUsingGetOrCreate() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
 		Environment env = new DummyEnvironment();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE, env);
 
 		// cast because our test serializer is not typed to TestPojo
@@ -390,7 +399,9 @@ public void testBackendUsesRegisteredKryoDefaultSerializerUsingGetOrCreate() thr
 
 		try {
 			// backends that lazily serializes (such as memory state backend) will fail here
-			runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+			runSnapshot(
+				backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 		} catch (ExpectedKryoTestException e) {
 			numExceptions++;
 		} catch (Exception e) {
@@ -409,8 +420,8 @@ public void testBackendUsesRegisteredKryoDefaultSerializerUsingGetOrCreate() thr
 	public void testBackendUsesRegisteredKryoSerializer() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
 		Environment env = new DummyEnvironment();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE, env);
-
 		env.getExecutionConfig()
 				.registerTypeWithKryoSerializer(TestPojo.class, ExceptionThrowingTestSerializer.class);
 
@@ -444,7 +455,9 @@ public void testBackendUsesRegisteredKryoSerializer() throws Exception {
 
 		try {
 			// backends that lazily serializes (such as memory state backend) will fail here
-			runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+			runSnapshot(
+				backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 		} catch (ExpectedKryoTestException e) {
 			numExceptions++;
 		} catch (Exception e) {
@@ -464,6 +477,7 @@ public void testBackendUsesRegisteredKryoSerializer() throws Exception {
 	public void testBackendUsesRegisteredKryoSerializerUsingGetOrCreate() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
 		Environment env = new DummyEnvironment();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE, env);
 
 		env.getExecutionConfig().registerTypeWithKryoSerializer(TestPojo.class, ExceptionThrowingTestSerializer.class);
@@ -500,7 +514,9 @@ public void testBackendUsesRegisteredKryoSerializerUsingGetOrCreate() throws Exc
 
 		try {
 			// backends that lazily serializes (such as memory state backend) will fail here
-			runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+			runSnapshot(
+				backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 		} catch (ExpectedKryoTestException e) {
 			numExceptions++;
 		} catch (Exception e) {
@@ -528,6 +544,7 @@ public void testBackendUsesRegisteredKryoSerializerUsingGetOrCreate() throws Exc
 	public void testKryoRegisteringRestoreResilienceWithRegisteredType() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
 		Environment env = new DummyEnvironment();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE, env);
 
 		TypeInformation<TestPojo> pojoType = new GenericTypeInfo<>(TestPojo.class);
@@ -548,11 +565,13 @@ public void testKryoRegisteringRestoreResilienceWithRegisteredType() throws Exce
 		backend.setCurrentKey(2);
 		state.update(new TestPojo("u2", 2));
 
-		KeyedStateHandle snapshot = runSnapshot(backend.snapshot(
+		KeyedStateHandle snapshot = runSnapshot(
+			backend.snapshot(
 				682375462378L,
 				2,
 				streamFactory,
-				CheckpointOptions.forCheckpointWithDefaultLocation()));
+				CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		backend.dispose();
 
@@ -617,9 +636,9 @@ public void testKryoRegisteringRestoreResilienceWithDefaultSerializer() throws E
 				682375462378L,
 				2,
 				streamFactory,
-				CheckpointOptions.forCheckpointWithDefaultLocation()));
+				CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
-			snapshot.registerSharedStates(sharedStateRegistry);
 			backend.dispose();
 
 			// ========== restore snapshot - should use default serializer (ONLY SERIALIZATION) ==========
@@ -639,13 +658,14 @@ public void testKryoRegisteringRestoreResilienceWithDefaultSerializer() throws E
 			// update to test state backends that eagerly serialize, such as RocksDB
 			state.update(new TestPojo("u1", 11));
 
-			KeyedStateHandle snapshot2 = runSnapshot(backend.snapshot(
-				682375462378L,
-				2,
-				streamFactory,
-				CheckpointOptions.forCheckpointWithDefaultLocation()));
+			KeyedStateHandle snapshot2 = runSnapshot(
+				backend.snapshot(
+					682375462378L,
+					2,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
-			snapshot2.registerSharedStates(sharedStateRegistry);
 			snapshot.discardState();
 
 			backend.dispose();
@@ -715,13 +735,14 @@ public void testKryoRegisteringRestoreResilienceWithRegisteredSerializer() throw
 			backend.setCurrentKey(2);
 			state.update(new TestPojo("u2", 2));
 
-			KeyedStateHandle snapshot = runSnapshot(backend.snapshot(
-				682375462378L,
-				2,
-				streamFactory,
-				CheckpointOptions.forCheckpointWithDefaultLocation()));
+			KeyedStateHandle snapshot = runSnapshot(
+				backend.snapshot(
+					682375462378L,
+					2,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
-			snapshot.registerSharedStates(sharedStateRegistry);
 			backend.dispose();
 
 			// ========== restore snapshot - should use specific serializer (ONLY SERIALIZATION) ==========
@@ -740,13 +761,13 @@ public void testKryoRegisteringRestoreResilienceWithRegisteredSerializer() throw
 			// update to test state backends that eagerly serialize, such as RocksDB
 			state.update(new TestPojo("u1", 11));
 
-			KeyedStateHandle snapshot2 = runSnapshot(backend.snapshot(
-				682375462378L,
-				2,
-				streamFactory,
-				CheckpointOptions.forCheckpointWithDefaultLocation()));
-
-			snapshot2.registerSharedStates(sharedStateRegistry);
+			KeyedStateHandle snapshot2 = runSnapshot(
+				backend.snapshot(
+					682375462378L,
+					2,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
 			snapshot.discardState();
 
@@ -783,6 +804,7 @@ public void testKryoRegisteringRestoreResilienceWithRegisteredSerializer() throw
 	public void testKryoRestoreResilienceWithDifferentRegistrationOrder() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
 		Environment env = new DummyEnvironment();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 
 		// register A first then B
 		env.getExecutionConfig().registerKryoType(TestNestedPojoClassA.class);
@@ -790,83 +812,91 @@ public void testKryoRestoreResilienceWithDifferentRegistrationOrder() throws Exc
 
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE, env);
 
-		TypeInformation<TestPojo> pojoType = new GenericTypeInfo<>(TestPojo.class);
+		try {
 
-		// make sure that we are in fact using the KryoSerializer
-		assertTrue(pojoType.createSerializer(env.getExecutionConfig()) instanceof KryoSerializer);
+			TypeInformation<TestPojo> pojoType = new GenericTypeInfo<>(TestPojo.class);
 
-		ValueStateDescriptor<TestPojo> kvId = new ValueStateDescriptor<>("id", pojoType);
-		ValueState<TestPojo> state = backend.getPartitionedState(VoidNamespace.INSTANCE, VoidNamespaceSerializer.INSTANCE, kvId);
+			// make sure that we are in fact using the KryoSerializer
+			assertTrue(pojoType.createSerializer(env.getExecutionConfig()) instanceof KryoSerializer);
 
-		// access the internal state representation to retrieve the original Kryo registration ids;
-		// these will be later used to check that on restore, the new Kryo serializer has reconfigured itself to
-		// have identical mappings
-		InternalKvState internalKvState = (InternalKvState) state;
-		KryoSerializer<TestPojo> kryoSerializer = (KryoSerializer<TestPojo>) internalKvState.getValueSerializer();
-		int mainPojoClassRegistrationId = kryoSerializer.getKryo().getRegistration(TestPojo.class).getId();
-		int nestedPojoClassARegistrationId = kryoSerializer.getKryo().getRegistration(TestNestedPojoClassA.class).getId();
-		int nestedPojoClassBRegistrationId = kryoSerializer.getKryo().getRegistration(TestNestedPojoClassB.class).getId();
+			ValueStateDescriptor<TestPojo> kvId = new ValueStateDescriptor<>("id", pojoType);
+			ValueState<TestPojo> state = backend.getPartitionedState(VoidNamespace.INSTANCE, VoidNamespaceSerializer.INSTANCE, kvId);
 
-		// ============== create snapshot of current configuration ==============
+			// access the internal state representation to retrieve the original Kryo registration ids;
+			// these will be later used to check that on restore, the new Kryo serializer has reconfigured itself to
+			// have identical mappings
+			InternalKvState internalKvState = (InternalKvState) state;
+			KryoSerializer<TestPojo> kryoSerializer = (KryoSerializer<TestPojo>) internalKvState.getValueSerializer();
+			int mainPojoClassRegistrationId = kryoSerializer.getKryo().getRegistration(TestPojo.class).getId();
+			int nestedPojoClassARegistrationId = kryoSerializer.getKryo().getRegistration(TestNestedPojoClassA.class).getId();
+			int nestedPojoClassBRegistrationId = kryoSerializer.getKryo().getRegistration(TestNestedPojoClassB.class).getId();
 
-		// make some more modifications
-		backend.setCurrentKey(1);
-		state.update(new TestPojo("u1", 1, new TestNestedPojoClassA(1.0, 2), new TestNestedPojoClassB(2.3, "foo")));
+			// ============== create snapshot of current configuration ==============
 
-		backend.setCurrentKey(2);
-		state.update(new TestPojo("u2", 2, new TestNestedPojoClassA(2.0, 5), new TestNestedPojoClassB(3.1, "bar")));
+			// make some more modifications
+			backend.setCurrentKey(1);
+			state.update(new TestPojo("u1", 1, new TestNestedPojoClassA(1.0, 2), new TestNestedPojoClassB(2.3, "foo")));
 
-		KeyedStateHandle snapshot = runSnapshot(backend.snapshot(
-			682375462378L,
-			2,
-			streamFactory,
-			CheckpointOptions.forCheckpointWithDefaultLocation()));
+			backend.setCurrentKey(2);
+			state.update(new TestPojo("u2", 2, new TestNestedPojoClassA(2.0, 5), new TestNestedPojoClassB(3.1, "bar")));
 
-		backend.dispose();
+			KeyedStateHandle snapshot = runSnapshot(
+				backend.snapshot(
+					682375462378L,
+					2,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
-		// ========== restore snapshot, with a different registration order in the configuration ==========
+			backend.dispose();
 
-		env = new DummyEnvironment();
+			// ========== restore snapshot, with a different registration order in the configuration ==========
 
-		env.getExecutionConfig().registerKryoType(TestNestedPojoClassB.class); // this time register B first
-		env.getExecutionConfig().registerKryoType(TestNestedPojoClassA.class);
+			env = new DummyEnvironment();
 
-		backend = restoreKeyedBackend(IntSerializer.INSTANCE, snapshot, env);
+			env.getExecutionConfig().registerKryoType(TestNestedPojoClassB.class); // this time register B first
+			env.getExecutionConfig().registerKryoType(TestNestedPojoClassA.class);
 
-		snapshot.discardState();
+			backend = restoreKeyedBackend(IntSerializer.INSTANCE, snapshot, env);
 
-		// re-initialize to ensure that we create the KryoSerializer from scratch, otherwise
-		// initializeSerializerUnlessSet would not pick up our new config
-		kvId = new ValueStateDescriptor<>("id", pojoType);
-		state = backend.getPartitionedState(VoidNamespace.INSTANCE, VoidNamespaceSerializer.INSTANCE, kvId);
+			// re-initialize to ensure that we create the KryoSerializer from scratch, otherwise
+			// initializeSerializerUnlessSet would not pick up our new config
+			kvId = new ValueStateDescriptor<>("id", pojoType);
+			state = backend.getPartitionedState(VoidNamespace.INSTANCE, VoidNamespaceSerializer.INSTANCE, kvId);
 
-		// verify that on restore, the serializer that the state handle uses has reconfigured itself to have
-		// identical Kryo registration ids compared to the previous execution
-		internalKvState = (InternalKvState) state;
-		kryoSerializer = (KryoSerializer<TestPojo>) internalKvState.getValueSerializer();
-		assertEquals(mainPojoClassRegistrationId, kryoSerializer.getKryo().getRegistration(TestPojo.class).getId());
-		assertEquals(nestedPojoClassARegistrationId, kryoSerializer.getKryo().getRegistration(TestNestedPojoClassA.class).getId());
-		assertEquals(nestedPojoClassBRegistrationId, kryoSerializer.getKryo().getRegistration(TestNestedPojoClassB.class).getId());
+			// verify that on restore, the serializer that the state handle uses has reconfigured itself to have
+			// identical Kryo registration ids compared to the previous execution
+			internalKvState = (InternalKvState) state;
+			kryoSerializer = (KryoSerializer<TestPojo>) internalKvState.getValueSerializer();
+			assertEquals(mainPojoClassRegistrationId, kryoSerializer.getKryo().getRegistration(TestPojo.class).getId());
+			assertEquals(nestedPojoClassARegistrationId, kryoSerializer.getKryo().getRegistration(TestNestedPojoClassA.class).getId());
+			assertEquals(nestedPojoClassBRegistrationId, kryoSerializer.getKryo().getRegistration(TestNestedPojoClassB.class).getId());
 
-		backend.setCurrentKey(1);
+			backend.setCurrentKey(1);
 
-		// update to test state backends that eagerly serialize, such as RocksDB
-		state.update(new TestPojo("u1", 11, new TestNestedPojoClassA(22.1, 12), new TestNestedPojoClassB(1.23, "foobar")));
+			// update to test state backends that eagerly serialize, such as RocksDB
+			state.update(new TestPojo("u1", 11, new TestNestedPojoClassA(22.1, 12), new TestNestedPojoClassB(1.23, "foobar")));
 
-		// this tests backends that lazily serialize, such as memory state backend
-		runSnapshot(backend.snapshot(
-			682375462378L,
-			2,
-			streamFactory,
-			CheckpointOptions.forCheckpointWithDefaultLocation()));
+			// this tests backends that lazily serialize, such as memory state backend
+			runSnapshot(
+				backend.snapshot(
+					682375462378L,
+					2,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
-		backend.dispose();
+			snapshot.discardState();
+		} finally {
+			backend.dispose();
+		}
 	}
 
 	@Test
 	public void testPojoRestoreResilienceWithDifferentRegistrationOrder() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
 		Environment env = new DummyEnvironment();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 
 		// register A first then B
 		env.getExecutionConfig().registerPojoType(TestNestedPojoClassA.class);
@@ -874,60 +904,66 @@ public void testPojoRestoreResilienceWithDifferentRegistrationOrder() throws Exc
 
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE, env);
 
-		TypeInformation<TestPojo> pojoType = TypeExtractor.getForClass(TestPojo.class);
+		try {
 
-		// make sure that we are in fact using the PojoSerializer
-		assertTrue(pojoType.createSerializer(env.getExecutionConfig()) instanceof PojoSerializer);
+			TypeInformation<TestPojo> pojoType = TypeExtractor.getForClass(TestPojo.class);
 
-		ValueStateDescriptor<TestPojo> kvId = new ValueStateDescriptor<>("id", pojoType);
-		ValueState<TestPojo> state = backend.getPartitionedState(VoidNamespace.INSTANCE, VoidNamespaceSerializer.INSTANCE, kvId);
+			// make sure that we are in fact using the PojoSerializer
+			assertTrue(pojoType.createSerializer(env.getExecutionConfig()) instanceof PojoSerializer);
 
-		// ============== create snapshot of current configuration ==============
+			ValueStateDescriptor<TestPojo> kvId = new ValueStateDescriptor<>("id", pojoType);
+			ValueState<TestPojo> state = backend.getPartitionedState(VoidNamespace.INSTANCE, VoidNamespaceSerializer.INSTANCE, kvId);
 
-		// make some more modifications
-		backend.setCurrentKey(1);
-		state.update(new TestPojo("u1", 1, new TestNestedPojoClassA(1.0, 2), new TestNestedPojoClassB(2.3, "foo")));
+			// ============== create snapshot of current configuration ==============
 
-		backend.setCurrentKey(2);
-		state.update(new TestPojo("u2", 2, new TestNestedPojoClassA(2.0, 5), new TestNestedPojoClassB(3.1, "bar")));
+			// make some more modifications
+			backend.setCurrentKey(1);
+			state.update(new TestPojo("u1", 1, new TestNestedPojoClassA(1.0, 2), new TestNestedPojoClassB(2.3, "foo")));
 
-		KeyedStateHandle snapshot = runSnapshot(backend.snapshot(
-			682375462378L,
-			2,
-			streamFactory,
-			CheckpointOptions.forCheckpointWithDefaultLocation()));
+			backend.setCurrentKey(2);
+			state.update(new TestPojo("u2", 2, new TestNestedPojoClassA(2.0, 5), new TestNestedPojoClassB(3.1, "bar")));
 
-		backend.dispose();
+			KeyedStateHandle snapshot = runSnapshot(
+				backend.snapshot(
+					682375462378L,
+					2,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
-		// ========== restore snapshot, with a different registration order in the configuration ==========
+			backend.dispose();
 
-		env = new DummyEnvironment();
+			// ========== restore snapshot, with a different registration order in the configuration ==========
 
-		env.getExecutionConfig().registerPojoType(TestNestedPojoClassB.class); // this time register B first
-		env.getExecutionConfig().registerPojoType(TestNestedPojoClassA.class);
+			env = new DummyEnvironment();
 
-		backend = restoreKeyedBackend(IntSerializer.INSTANCE, snapshot, env);
+			env.getExecutionConfig().registerPojoType(TestNestedPojoClassB.class); // this time register B first
+			env.getExecutionConfig().registerPojoType(TestNestedPojoClassA.class);
 
-		snapshot.discardState();
+			backend = restoreKeyedBackend(IntSerializer.INSTANCE, snapshot, env);
 
-		// re-initialize to ensure that we create the PojoSerializer from scratch, otherwise
-		// initializeSerializerUnlessSet would not pick up our new config
-		kvId = new ValueStateDescriptor<>("id", pojoType);
-		state = backend.getPartitionedState(VoidNamespace.INSTANCE, VoidNamespaceSerializer.INSTANCE, kvId);
+			// re-initialize to ensure that we create the PojoSerializer from scratch, otherwise
+			// initializeSerializerUnlessSet would not pick up our new config
+			kvId = new ValueStateDescriptor<>("id", pojoType);
+			state = backend.getPartitionedState(VoidNamespace.INSTANCE, VoidNamespaceSerializer.INSTANCE, kvId);
 
-		backend.setCurrentKey(1);
+			backend.setCurrentKey(1);
 
-		// update to test state backends that eagerly serialize, such as RocksDB
-		state.update(new TestPojo("u1", 11, new TestNestedPojoClassA(22.1, 12), new TestNestedPojoClassB(1.23, "foobar")));
+			// update to test state backends that eagerly serialize, such as RocksDB
+			state.update(new TestPojo("u1", 11, new TestNestedPojoClassA(22.1, 12), new TestNestedPojoClassB(1.23, "foobar")));
 
-		// this tests backends that lazily serialize, such as memory state backend
-		runSnapshot(backend.snapshot(
-			682375462378L,
-			2,
-			streamFactory,
-			CheckpointOptions.forCheckpointWithDefaultLocation()));
+			// this tests backends that lazily serialize, such as memory state backend
+			runSnapshot(
+				backend.snapshot(
+					682375462378L,
+					2,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()), sharedStateRegistry);
 
-		backend.dispose();
+			snapshot.discardState();
+		} finally {
+			backend.dispose();
+		}
 	}
 
 	@Test
@@ -957,13 +993,14 @@ public void testStateSerializerReconfiguration() throws Exception {
 			assertTrue(internal.getValueSerializer() instanceof TestReconfigurableCustomTypeSerializer);
 			assertFalse(((TestReconfigurableCustomTypeSerializer) internal.getValueSerializer()).isReconfigured());
 
-			KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(
-				682375462378L,
-				2,
-				streamFactory,
-				CheckpointOptions.forCheckpointWithDefaultLocation()));
+			KeyedStateHandle snapshot1 = runSnapshot(
+				backend.snapshot(
+					682375462378L,
+					2,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
-			snapshot1.registerSharedStates(sharedStateRegistry);
 			backend.dispose();
 
 			// ========== restore snapshot, which should reconfigure the serializer, and then create a snapshot again ==========
@@ -995,13 +1032,14 @@ public void testStateSerializerReconfiguration() throws Exception {
 
 			state.update(new TestCustomStateClass("new-test-message-2", "extra-message-2"));
 
-			KeyedStateHandle snapshot2 = runSnapshot(backend.snapshot(
-				682375462379L,
-				3,
-				streamFactory,
-				CheckpointOptions.forCheckpointWithDefaultLocation()));
+			KeyedStateHandle snapshot2 = runSnapshot(
+				backend.snapshot(
+					682375462379L,
+					3,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
-			snapshot2.registerSharedStates(sharedStateRegistry);
 			snapshot1.discardState();
 			backend.dispose();
 
@@ -1055,13 +1093,14 @@ public void testSerializerPresenceOnRestore() throws Exception {
 			backend.setCurrentKey(2);
 			state.update(new TestCustomStateClass("test-message-2", "this-should-be-ignored"));
 
-			KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(
-				682375462378L,
-				2,
-				streamFactory,
-				CheckpointOptions.forCheckpointWithDefaultLocation()));
+			KeyedStateHandle snapshot1 = runSnapshot(
+				backend.snapshot(
+					682375462378L,
+					2,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
-			snapshot1.registerSharedStates(sharedStateRegistry);
 			backend.dispose();
 
 			// ========== restore snapshot, using the new serializer (that has different classname) ==========
@@ -1093,23 +1132,120 @@ public void testSerializerPresenceOnRestore() throws Exception {
 			backend.setCurrentKey(2);
 			state.update(new TestCustomStateClass("new-test-message-2", "extra-message-2"));
 
-			KeyedStateHandle snapshot2 = runSnapshot(backend.snapshot(
-				682375462379L,
-				3,
-				streamFactory,
-				CheckpointOptions.forCheckpointWithDefaultLocation()));
+			KeyedStateHandle snapshot2 = runSnapshot(
+				backend.snapshot(
+					682375462379L,
+					3,
+					streamFactory,
+					CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
-			snapshot2.registerSharedStates(sharedStateRegistry);
 			snapshot1.discardState();
 		} finally {
 			backend.dispose();
 		}
 	}
 
+	@Test
+	public void testPriorityQueueSerializerUpdates() throws Exception {
+
+		final String stateName = "test";
+		final CheckpointStreamFactory streamFactory = createStreamFactory();
+		final SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
+
+		AbstractKeyedStateBackend<Integer> keyedBackend = createKeyedBackend(IntSerializer.INSTANCE);
+
+		try {
+			TypeSerializer<InternalPriorityQueueTestBase.TestElement> serializer =
+				InternalPriorityQueueTestBase.TestElementSerializer.INSTANCE;
+
+			KeyGroupedInternalPriorityQueue<InternalPriorityQueueTestBase.TestElement> priorityQueue =
+				keyedBackend.create(stateName, serializer);
+
+			priorityQueue.add(new InternalPriorityQueueTestBase.TestElement(42L, 0L));
+
+			RunnableFuture<SnapshotResult<KeyedStateHandle>> snapshot =
+				keyedBackend.snapshot(0L, 0L, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation());
+
+			KeyedStateHandle keyedStateHandle = runSnapshot(snapshot, sharedStateRegistry);
+
+			keyedBackend.dispose();
+
+			// test restore with a modified but compatible serializer ---------------------------
+
+			keyedBackend = restoreKeyedBackend(IntSerializer.INSTANCE, keyedStateHandle);
+
+			serializer = new ModifiedTestElementSerializer();
+
+			priorityQueue = keyedBackend.create(stateName, serializer);
+
+			final InternalPriorityQueueTestBase.TestElement checkElement =
+				new InternalPriorityQueueTestBase.TestElement(4711L, 1L);
+			priorityQueue.add(checkElement);
+
+			snapshot = keyedBackend.snapshot(1L, 1L, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation());
+
+			keyedStateHandle = runSnapshot(snapshot, sharedStateRegistry);
+
+			keyedBackend.dispose();
+
+			// test that the modified serializer was actually used ---------------------------
+
+			keyedBackend = restoreKeyedBackend(IntSerializer.INSTANCE, keyedStateHandle);
+			priorityQueue = keyedBackend.create(stateName, serializer);
+
+			priorityQueue.poll();
+
+			ByteArrayOutputStreamWithPos out = new ByteArrayOutputStreamWithPos();
+			DataOutputViewStreamWrapper outWrapper = new DataOutputViewStreamWrapper(out);
+			serializer.serialize(checkElement, outWrapper);
+			InternalPriorityQueueTestBase.TestElement expected =
+				serializer.deserialize(new DataInputViewStreamWrapper(new ByteArrayInputStreamWithPos(out.toByteArray())));
+
+			Assert.assertEquals(
+				expected,
+				priorityQueue.poll());
+			Assert.assertTrue(priorityQueue.isEmpty());
+
+			keyedBackend.dispose();
+
+			// test that incompatible serializer is rejected ---------------------------
+
+			serializer = InternalPriorityQueueTestBase.TestElementSerializer.INSTANCE;
+			keyedBackend = restoreKeyedBackend(IntSerializer.INSTANCE, keyedStateHandle);
+
+			try {
+				// this is expected to fail, because the old and new serializer shoulbe be incompatible through
+				// different revision numbers.
+				keyedBackend.create("test", serializer);
+				Assert.fail("Expected exception from incompatible serializer.");
+			} catch (Exception e) {
+				Assert.assertTrue("Exception was not caused by state migration: " + e,
+					ExceptionUtils.findThrowable(e, StateMigrationException.class).isPresent());
+			}
+		} finally {
+			keyedBackend.dispose();
+		}
+	}
+
+	public static class ModifiedTestElementSerializer extends InternalPriorityQueueTestBase.TestElementSerializer {
+
+		@Override
+		public void serialize(InternalPriorityQueueTestBase.TestElement record, DataOutputView target) throws IOException {
+			super.serialize(new InternalPriorityQueueTestBase.TestElement(record.getKey() + 1, record.getPriority() + 1), target);
+		}
+
+		@Override
+		protected int getRevision() {
+			return super.getRevision() + 1;
+		}
+	}
+
 	@Test
 	@SuppressWarnings("unchecked")
 	public void testValueState() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 		ValueStateDescriptor<String> kvId = new ValueStateDescriptor<>("id", String.class);
@@ -1138,7 +1274,9 @@ public void testValueState() throws Exception {
 		assertEquals("1", getSerializedValue(kvState, 1, keySerializer, VoidNamespace.INSTANCE, namespaceSerializer, valueSerializer));
 
 		// draw a snapshot
-		KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot1 = runSnapshot(
+			backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		// make some more modifications
 		backend.setCurrentKey(1);
@@ -1149,7 +1287,9 @@ public void testValueState() throws Exception {
 		state.update("u3");
 
 		// draw another snapshot
-		KeyedStateHandle snapshot2 = runSnapshot(backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot2 = runSnapshot(
+			backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		// validate the original state
 		backend.setCurrentKey(1);
@@ -1320,7 +1460,7 @@ public void run() {
 	@SuppressWarnings("unchecked")
 	public void testMultipleValueStates() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
-
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(
 				IntSerializer.INSTANCE,
 				1,
@@ -1350,7 +1490,9 @@ public void testMultipleValueStates() throws Exception {
 
 		// draw a snapshot
 		KeyedStateHandle snapshot1 =
-			runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+			runSnapshot(
+				backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
 		backend.dispose();
 		backend = restoreKeyedBackend(
@@ -1394,6 +1536,7 @@ public void testValueStateNullUpdate() throws Exception {
 		}
 
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 		ValueStateDescriptor<Long> kvId = new ValueStateDescriptor<>("id", LongSerializer.INSTANCE, 42L);
@@ -1422,7 +1565,9 @@ public void testValueStateNullUpdate() throws Exception {
 		assertEquals(42L, (long) state.value());
 
 		// draw a snapshot
-		KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot1 = runSnapshot(
+			backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		backend.dispose();
 		backend = restoreKeyedBackend(IntSerializer.INSTANCE, snapshot1);
@@ -1438,6 +1583,7 @@ public void testValueStateNullUpdate() throws Exception {
 	@SuppressWarnings("unchecked,rawtypes")
 	public void testListState() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 		ListStateDescriptor<String> kvId = new ListStateDescriptor<>("id", String.class);
@@ -1470,7 +1616,9 @@ public void testListState() throws Exception {
 		assertEquals("1", joiner.join(getSerializedList(kvState, 1, keySerializer, VoidNamespace.INSTANCE, namespaceSerializer, valueSerializer)));
 
 		// draw a snapshot
-		KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot1 = runSnapshot(
+			backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		// make some more modifications
 		backend.setCurrentKey(1);
@@ -1483,7 +1631,9 @@ public void testListState() throws Exception {
 		state.add("u3");
 
 		// draw another snapshot
-		KeyedStateHandle snapshot2 = runSnapshot(backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot2 = runSnapshot(
+			backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		// validate the original state
 		backend.setCurrentKey(1);
@@ -1756,7 +1906,7 @@ public void testListStateAPIs() throws Exception {
 			state.clear();
 
 			// make sure all lists / maps are cleared
-			assertThat("State backend is not empty.", keyedBackend.numStateEntries(), is(0));
+			assertThat("State backend is not empty.", keyedBackend.numKeyValueStateEntries(), is(0));
 		} finally {
 			keyedBackend.close();
 			keyedBackend.dispose();
@@ -1870,7 +2020,7 @@ public void testListStateMerging() throws Exception {
 			state.setCurrentNamespace(namespace1);
 			state.clear();
 
-			assertThat("State backend is not empty.", keyedBackend.numStateEntries(), is(0));
+			assertThat("State backend is not empty.", keyedBackend.numKeyValueStateEntries(), is(0));
 		}
 		finally {
 			keyedBackend.close();
@@ -1882,6 +2032,7 @@ public void testListStateMerging() throws Exception {
 	@SuppressWarnings("unchecked")
 	public void testReducingState() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 		ReducingStateDescriptor<String> kvId = new ReducingStateDescriptor<>("id", new AppendingReduce(), String.class);
@@ -1910,7 +2061,9 @@ public void testReducingState() throws Exception {
 		assertEquals("1", getSerializedValue(kvState, 1, keySerializer, VoidNamespace.INSTANCE, namespaceSerializer, valueSerializer));
 
 		// draw a snapshot
-		KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot1 = runSnapshot(
+			backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		// make some more modifications
 		backend.setCurrentKey(1);
@@ -1921,7 +2074,9 @@ public void testReducingState() throws Exception {
 		state.add("u3");
 
 		// draw another snapshot
-		KeyedStateHandle snapshot2 = runSnapshot(backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot2 = runSnapshot(
+			backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		// validate the original state
 		backend.setCurrentKey(1);
@@ -2019,7 +2174,7 @@ public void testReducingStateAddAndGet() throws Exception {
 			state.clear();
 
 			// make sure all lists / maps are cleared
-			assertThat("State backend is not empty.", keyedBackend.numStateEntries(), is(0));
+			assertThat("State backend is not empty.", keyedBackend.numKeyValueStateEntries(), is(0));
 		}
 		finally {
 			keyedBackend.close();
@@ -2137,7 +2292,7 @@ public void testReducingStateMerging() throws Exception {
 			state.setCurrentNamespace(namespace1);
 			state.clear();
 
-			assertThat("State backend is not empty.", keyedBackend.numStateEntries(), is(0));
+			assertThat("State backend is not empty.", keyedBackend.numKeyValueStateEntries(), is(0));
 		}
 		finally {
 			keyedBackend.close();
@@ -2192,7 +2347,7 @@ public void testAggregatingStateAddAndGetWithMutableAccumulator() throws Excepti
 			state.clear();
 
 			// make sure all lists / maps are cleared
-			assertThat("State backend is not empty.", keyedBackend.numStateEntries(), is(0));
+			assertThat("State backend is not empty.", keyedBackend.numKeyValueStateEntries(), is(0));
 		}
 		finally {
 			keyedBackend.close();
@@ -2310,7 +2465,7 @@ public void testAggregatingStateMergingWithMutableAccumulator() throws Exception
 			state.setCurrentNamespace(namespace1);
 			state.clear();
 
-			assertThat("State backend is not empty.", keyedBackend.numStateEntries(), is(0));
+			assertThat("State backend is not empty.", keyedBackend.numKeyValueStateEntries(), is(0));
 		}
 		finally {
 			keyedBackend.close();
@@ -2365,7 +2520,7 @@ public void testAggregatingStateAddAndGetWithImmutableAccumulator() throws Excep
 			state.clear();
 
 			// make sure all lists / maps are cleared
-			assertThat("State backend is not empty.", keyedBackend.numStateEntries(), is(0));
+			assertThat("State backend is not empty.", keyedBackend.numKeyValueStateEntries(), is(0));
 		}
 		finally {
 			keyedBackend.close();
@@ -2483,7 +2638,7 @@ public void testAggregatingStateMergingWithImmutableAccumulator() throws Excepti
 			state.setCurrentNamespace(namespace1);
 			state.clear();
 
-			assertThat("State backend is not empty.", keyedBackend.numStateEntries(), is(0));
+			assertThat("State backend is not empty.", keyedBackend.numKeyValueStateEntries(), is(0));
 		}
 		finally {
 			keyedBackend.close();
@@ -2495,6 +2650,7 @@ public void testAggregatingStateMergingWithImmutableAccumulator() throws Excepti
 	@SuppressWarnings("unchecked,rawtypes")
 	public void testFoldingState() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 		FoldingStateDescriptor<Integer, String> kvId = new FoldingStateDescriptor<>("id",
@@ -2526,7 +2682,9 @@ public void testFoldingState() throws Exception {
 		assertEquals("Fold-Initial:,1", getSerializedValue(kvState, 1, keySerializer, VoidNamespace.INSTANCE, namespaceSerializer, valueSerializer));
 
 		// draw a snapshot
-		KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot1 = runSnapshot(
+			backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		// make some more modifications
 		backend.setCurrentKey(1);
@@ -2538,7 +2696,9 @@ public void testFoldingState() throws Exception {
 		state.add(103);
 
 		// draw another snapshot
-		KeyedStateHandle snapshot2 = runSnapshot(backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot2 = runSnapshot(
+			backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		// validate the original state
 		backend.setCurrentKey(1);
@@ -2594,6 +2754,7 @@ public void testFoldingState() throws Exception {
 	@SuppressWarnings("unchecked,rawtypes")
 	public void testMapState() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<String> backend = createKeyedBackend(StringSerializer.INSTANCE);
 
 		MapStateDescriptor<Integer, String> kvId = new MapStateDescriptor<>("id", Integer.class, String.class);
@@ -2633,7 +2794,9 @@ public void testMapState() throws Exception {
 			getSerializedMap(kvState, "11", keySerializer, VoidNamespace.INSTANCE, namespaceSerializer, userKeySerializer, userValueSerializer));
 
 		// draw a snapshot
-		KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot1 = runSnapshot(
+			backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		// make some more modifications
 		backend.setCurrentKey("1");
@@ -2645,7 +2808,9 @@ public void testMapState() throws Exception {
 		state.putAll(new HashMap<Integer, String>() {{ put(1031, "1031"); put(1032, "1032"); }});
 
 		// draw another snapshot
-		KeyedStateHandle snapshot2 = runSnapshot(backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot2 = runSnapshot(
+			backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		// validate the original state
 		backend.setCurrentKey("1");
@@ -2920,6 +3085,7 @@ public void testKeyGroupSnapshotRestore() throws Exception {
 		final int MAX_PARALLELISM = 10;
 
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		final AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(
 				IntSerializer.INSTANCE,
 				MAX_PARALLELISM,
@@ -2951,7 +3117,9 @@ public void testKeyGroupSnapshotRestore() throws Exception {
 		state.update("ShouldBeInSecondHalf");
 
 
-		KeyedStateHandle snapshot = runSnapshot(backend.snapshot(0, 0, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot = runSnapshot(
+			backend.snapshot(0, 0, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		List<KeyedStateHandle> firstHalfKeyGroupStates = StateAssignmentOperation.getKeyedStateHandles(
 				Collections.singletonList(snapshot),
@@ -3004,6 +3172,8 @@ public void testKeyGroupSnapshotRestore() throws Exception {
 	public void testRestoreWithWrongKeySerializer() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
 
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
+
 		// use an IntSerializer at first
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
@@ -3018,7 +3188,9 @@ public void testRestoreWithWrongKeySerializer() throws Exception {
 		state.update("2");
 
 		// draw a snapshot
-		KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot1 = runSnapshot(
+			backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		backend.dispose();
 
@@ -3036,6 +3208,7 @@ public void testRestoreWithWrongKeySerializer() throws Exception {
 	@SuppressWarnings("unchecked")
 	public void testValueStateRestoreWithWrongSerializers() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 		try {
@@ -3049,7 +3222,9 @@ public void testValueStateRestoreWithWrongSerializers() throws Exception {
 			state.update("2");
 
 			// draw a snapshot
-			KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+			KeyedStateHandle snapshot1 = runSnapshot(
+				backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
 			backend.dispose();
 			// restore the first snapshot and validate it
@@ -3080,6 +3255,7 @@ public void testValueStateRestoreWithWrongSerializers() throws Exception {
 	@SuppressWarnings("unchecked")
 	public void testListStateRestoreWithWrongSerializers() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 		try {
@@ -3092,7 +3268,9 @@ public void testListStateRestoreWithWrongSerializers() throws Exception {
 			state.add("2");
 
 			// draw a snapshot
-			KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+			KeyedStateHandle snapshot1 = runSnapshot(
+				backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
 			backend.dispose();
 			// restore the first snapshot and validate it
@@ -3123,6 +3301,7 @@ public void testListStateRestoreWithWrongSerializers() throws Exception {
 	@SuppressWarnings("unchecked")
 	public void testReducingStateRestoreWithWrongSerializers() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 		try {
@@ -3137,7 +3316,9 @@ public void testReducingStateRestoreWithWrongSerializers() throws Exception {
 			state.add("2");
 
 			// draw a snapshot
-			KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+			KeyedStateHandle snapshot1 = runSnapshot(
+				backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
 			backend.dispose();
 			// restore the first snapshot and validate it
@@ -3168,6 +3349,7 @@ public void testReducingStateRestoreWithWrongSerializers() throws Exception {
 	@SuppressWarnings("unchecked")
 	public void testMapStateRestoreWithWrongSerializers() throws Exception {
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 		try {
@@ -3180,7 +3362,9 @@ public void testMapStateRestoreWithWrongSerializers() throws Exception {
 			state.put("2", "Second");
 
 			// draw a snapshot
-			KeyedStateHandle snapshot1 = runSnapshot(backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+			KeyedStateHandle snapshot1 = runSnapshot(
+				backend.snapshot(682375462378L, 2, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+				sharedStateRegistry);
 
 			backend.dispose();
 			// restore the first snapshot and validate it
@@ -3421,6 +3605,7 @@ public void testQueryableStateRegistration() throws Exception {
 		KvStateRegistry registry = env.getKvStateRegistry();
 
 		CheckpointStreamFactory streamFactory = createStreamFactory();
+		SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 		AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE, env);
 		KeyGroupRange expectedKeyGroupRange = backend.getKeyGroupRange();
 
@@ -3439,7 +3624,9 @@ public void testQueryableStateRegistration() throws Exception {
 				eq(env.getJobID()), eq(env.getJobVertexId()), eq(expectedKeyGroupRange), eq("banana"), any(KvStateID.class));
 
 
-		KeyedStateHandle snapshot = runSnapshot(backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+		KeyedStateHandle snapshot = runSnapshot(
+			backend.snapshot(682375462379L, 4, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+			sharedStateRegistry);
 
 		backend.dispose();
 
@@ -3465,13 +3652,16 @@ public void testEmptyStateCheckpointing() {
 
 		try {
 			CheckpointStreamFactory streamFactory = createStreamFactory();
+			SharedStateRegistry sharedStateRegistry = new SharedStateRegistry();
 			AbstractKeyedStateBackend<Integer> backend = createKeyedBackend(IntSerializer.INSTANCE);
 
 			ListStateDescriptor<String> kvId = new ListStateDescriptor<>("id", String.class);
 
 			// draw a snapshot
 			KeyedStateHandle snapshot =
-				runSnapshot(backend.snapshot(682375462379L, 1, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()));
+				runSnapshot(
+					backend.snapshot(682375462379L, 1, streamFactory, CheckpointOptions.forCheckpointWithDefaultLocation()),
+					sharedStateRegistry);
 			assertNull(snapshot);
 			backend.dispose();
 
@@ -3491,7 +3681,7 @@ public void testNumStateEntries() throws Exception {
 
 		ValueStateDescriptor<String> kvId = new ValueStateDescriptor<>("id", String.class);
 
-		assertEquals(0, backend.numStateEntries());
+		assertEquals(0, backend.numKeyValueStateEntries());
 
 		ValueState<String> state = backend.getPartitionedState(VoidNamespace.INSTANCE, VoidNamespaceSerializer.INSTANCE, kvId);
 
@@ -3499,22 +3689,22 @@ public void testNumStateEntries() throws Exception {
 		state.update("hello");
 		state.update("ciao");
 
-		assertEquals(1, backend.numStateEntries());
+		assertEquals(1, backend.numKeyValueStateEntries());
 
 		backend.setCurrentKey(42);
 		state.update("foo");
 
-		assertEquals(2, backend.numStateEntries());
+		assertEquals(2, backend.numKeyValueStateEntries());
 
 		backend.setCurrentKey(0);
 		state.clear();
 
-		assertEquals(1, backend.numStateEntries());
+		assertEquals(1, backend.numKeyValueStateEntries());
 
 		backend.setCurrentKey(42);
 		state.clear();
 
-		assertEquals(0, backend.numStateEntries());
+		assertEquals(0, backend.numKeyValueStateEntries());
 
 		backend.dispose();
 	}
@@ -4048,14 +4238,19 @@ public void testCheckConcurrencyProblemWhenPerformingCheckpointAsync() throws Ex
 	}
 
 	protected KeyedStateHandle runSnapshot(
-		RunnableFuture<SnapshotResult<KeyedStateHandle>> snapshotRunnableFuture) throws Exception {
+		RunnableFuture<SnapshotResult<KeyedStateHandle>> snapshotRunnableFuture,
+		SharedStateRegistry sharedStateRegistry) throws Exception {
 
 		if (!snapshotRunnableFuture.isDone()) {
 			snapshotRunnableFuture.run();
 		}
 
 		SnapshotResult<KeyedStateHandle> snapshotResult = snapshotRunnableFuture.get();
-		return snapshotResult.getJobManagerOwnedSnapshot();
+		KeyedStateHandle jobManagerOwnedSnapshot = snapshotResult.getJobManagerOwnedSnapshot();
+		if (jobManagerOwnedSnapshot != null) {
+			jobManagerOwnedSnapshot.registerSharedStates(sharedStateRegistry);
+		}
+		return jobManagerOwnedSnapshot;
 	}
 
 	public static class TestPojo implements Serializable {
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/CachingInternalPriorityQueueSetTestBase.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/CachingInternalPriorityQueueSetTestBase.java
deleted file mode 100644
index 79fd5566a9a..00000000000
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/CachingInternalPriorityQueueSetTestBase.java
+++ /dev/null
@@ -1,43 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.flink.runtime.state.heap;
-
-import org.apache.flink.runtime.state.InternalPriorityQueue;
-import org.apache.flink.runtime.state.InternalPriorityQueueTestBase;
-
-/**
- * Test for {@link CachingInternalPriorityQueueSet}.
- */
-public abstract class CachingInternalPriorityQueueSetTestBase extends InternalPriorityQueueTestBase {
-
-	@Override
-	protected InternalPriorityQueue<TestElement> newPriorityQueue(int initialCapacity) {
-		final CachingInternalPriorityQueueSet.OrderedSetCache<TestElement> cache = createOrderedSetCache();
-		final CachingInternalPriorityQueueSet.OrderedSetStore<TestElement> store = createOrderedSetStore();
-		return new CachingInternalPriorityQueueSet<>(cache, store);
-	}
-
-	@Override
-	protected boolean testSetSemanticsAgainstDuplicateElements() {
-		return true;
-	}
-
-	protected abstract CachingInternalPriorityQueueSet.OrderedSetStore<TestElement> createOrderedSetStore();
-
-	protected abstract CachingInternalPriorityQueueSet.OrderedSetCache<TestElement> createOrderedSetCache();
-}
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/HeapKeyedStateBackendSnapshotMigrationTest.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/HeapKeyedStateBackendSnapshotMigrationTest.java
index 7b8d69f2cb6..1ca3e80b3cc 100644
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/HeapKeyedStateBackendSnapshotMigrationTest.java
+++ b/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/HeapKeyedStateBackendSnapshotMigrationTest.java
@@ -235,7 +235,7 @@ public void testRestore1_2ToMaster() throws Exception {
 
 			InternalListState<String, Integer, Long> state = keyedBackend.createInternalState(IntSerializer.INSTANCE, stateDescr);
 
-			assertEquals(7, keyedBackend.numStateEntries());
+			assertEquals(7, keyedBackend.numKeyValueStateEntries());
 
 			keyedBackend.setCurrentKey("abc");
 			state.setCurrentNamespace(namespace1);
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/KeyGroupPartitionedPriorityQueueTest.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/KeyGroupPartitionedPriorityQueueTest.java
index d348e10458f..175c6153a0b 100644
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/KeyGroupPartitionedPriorityQueueTest.java
+++ b/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/KeyGroupPartitionedPriorityQueueTest.java
@@ -19,6 +19,11 @@
 
 import org.apache.flink.runtime.state.InternalPriorityQueue;
 import org.apache.flink.runtime.state.InternalPriorityQueueTestBase;
+import org.apache.flink.runtime.state.KeyExtractorFunction;
+import org.apache.flink.runtime.state.KeyGroupRange;
+import org.apache.flink.runtime.state.PriorityComparator;
+
+import javax.annotation.Nonnull;
 
 /**
  * Test for {@link KeyGroupPartitionedPriorityQueue}.
@@ -34,20 +39,46 @@
 			KEY_GROUP_RANGE, KEY_GROUP_RANGE.getNumberOfKeyGroups());
 	}
 
-	protected KeyGroupPartitionedPriorityQueue.PartitionQueueSetFactory<
-			TestElement, CachingInternalPriorityQueueSet<TestElement>> newFactory(int initialCapacity) {
+	private KeyGroupPartitionedPriorityQueue.PartitionQueueSetFactory<
+			TestElement, KeyGroupHeapPQSet<TestElement>> newFactory(int initialCapacity) {
 
-		return (keyGroupId, numKeyGroups, elementComparator) -> {
-			CachingInternalPriorityQueueSet.OrderedSetCache<TestElement> cache =
-				new TreeOrderedSetCache<>(TEST_ELEMENT_COMPARATOR, 32);
-			CachingInternalPriorityQueueSet.OrderedSetStore<TestElement> store =
-				new TestOrderedStore<>(TEST_ELEMENT_COMPARATOR);
-			return new CachingInternalPriorityQueueSet<>(cache, store);
-		};
+		return (keyGroupId, numKeyGroups, keyExtractorFunction, elementComparator) ->
+			new KeyGroupHeapPQSet<>(
+				elementComparator,
+				keyExtractorFunction,
+				initialCapacity,
+				KeyGroupRange.of(keyGroupId, keyGroupId),
+				numKeyGroups);
 	}
 
 	@Override
 	protected boolean testSetSemanticsAgainstDuplicateElements() {
 		return true;
 	}
+
+	private static class KeyGroupHeapPQSet<T extends HeapPriorityQueueElement> extends HeapPriorityQueueSet<T>
+		implements HeapPriorityQueueElement {
+
+		private int internalIndex;
+
+		public KeyGroupHeapPQSet(
+			@Nonnull PriorityComparator<T> elementPriorityComparator,
+			@Nonnull KeyExtractorFunction<T> keyExtractor,
+			int minimumCapacity,
+			@Nonnull KeyGroupRange keyGroupRange,
+			int totalNumberOfKeyGroups) {
+			super(elementPriorityComparator, keyExtractor, minimumCapacity, keyGroupRange, totalNumberOfKeyGroups);
+			this.internalIndex = HeapPriorityQueueElement.NOT_CONTAINED;
+		}
+
+		@Override
+		public int getInternalIndex() {
+			return internalIndex;
+		}
+
+		@Override
+		public void setInternalIndex(int newIndex) {
+			internalIndex = newIndex;
+		}
+	}
 }
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/OrderedSetCacheTestBase.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/OrderedSetCacheTestBase.java
deleted file mode 100644
index 1d627edc883..00000000000
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/OrderedSetCacheTestBase.java
+++ /dev/null
@@ -1,102 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-package org.apache.flink.runtime.state.heap;
-
-import org.junit.Assert;
-import org.junit.Test;
-
-import java.util.Random;
-import java.util.TreeSet;
-
-/**
- * Test base for instances of
- * {@link org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet.OrderedSetCache}.
- */
-public abstract class OrderedSetCacheTestBase {
-
-	@Test
-	public void testOrderedSetCacheContract() {
-		final Random random = new Random(0x42);
-		final int capacity = 5000;
-		final int keySpaceUpperBound = 100 * capacity;
-		final TreeSet<Integer> checkSet = new TreeSet<>(Integer::compareTo);
-		final CachingInternalPriorityQueueSet.OrderedSetCache<Integer> testInstance = createInstance(capacity);
-
-		Assert.assertTrue(testInstance.isEmpty());
-
-		while (checkSet.size() < capacity) {
-			Assert.assertEquals(checkSet.size() >= capacity, testInstance.isFull());
-			if (!checkSet.isEmpty() && random.nextInt(10) == 0) {
-				final int toDelete = pickContainedRandomElement(checkSet, random);
-				Assert.assertTrue(checkSet.remove(toDelete));
-				testInstance.remove(toDelete);
-			} else {
-				final int randomValue = random.nextInt(keySpaceUpperBound);
-				checkSet.add(randomValue);
-				testInstance.add(randomValue);
-			}
-			Assert.assertEquals(checkSet.isEmpty(), testInstance.isEmpty());
-
-			Assert.assertEquals(checkSet.first(), testInstance.peekFirst());
-			Assert.assertEquals(checkSet.last(), testInstance.peekLast());
-
-			Assert.assertFalse(testInstance.isInLowerBound(checkSet.last()));
-			Assert.assertTrue(testInstance.isInLowerBound(checkSet.last() - 1));
-		}
-
-		Assert.assertTrue(testInstance.isFull());
-		Assert.assertFalse(testInstance.isInLowerBound(checkSet.last()));
-		Assert.assertTrue(testInstance.isInLowerBound(checkSet.last() - 1));
-
-		testInstance.remove(pickNotContainedRandomElement(checkSet, random, keySpaceUpperBound));
-		Assert.assertTrue(testInstance.isFull());
-
-		int containedKey = pickContainedRandomElement(checkSet, random);
-
-		Assert.assertTrue(checkSet.remove(containedKey));
-		testInstance.remove(containedKey);
-
-		Assert.assertFalse(testInstance.isFull());
-
-		for (int i = 0; i < capacity; ++i) {
-			if (random.nextInt(1) == 0) {
-				Assert.assertEquals(checkSet.pollFirst(), testInstance.removeFirst());
-			} else {
-				Assert.assertEquals(checkSet.pollLast(), testInstance.removeLast());
-			}
-		}
-
-		Assert.assertFalse(testInstance.isFull());
-		Assert.assertTrue(testInstance.isEmpty());
-	}
-
-	private int pickNotContainedRandomElement(TreeSet<Integer> checkSet, Random random, int upperBound) {
-		int notContainedKey;
-		do {
-			notContainedKey = random.nextInt(upperBound);
-		} while (checkSet.contains(notContainedKey));
-		return notContainedKey;
-	}
-
-	private int pickContainedRandomElement(TreeSet<Integer> checkSet, Random random) {
-		assert !checkSet.isEmpty();
-		return checkSet.ceiling(1 + random.nextInt(checkSet.last()));
-	}
-
-	protected abstract CachingInternalPriorityQueueSet.OrderedSetCache<Integer> createInstance(int capacity);
-}
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/SimpleCachingInternalPriorityQueueSetTest.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/SimpleCachingInternalPriorityQueueSetTest.java
deleted file mode 100644
index 4c4eb460ae3..00000000000
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/SimpleCachingInternalPriorityQueueSetTest.java
+++ /dev/null
@@ -1,35 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.flink.runtime.state.heap;
-
-/**
- * Test for {@link CachingInternalPriorityQueueSet}.
- */
-public class SimpleCachingInternalPriorityQueueSetTest extends CachingInternalPriorityQueueSetTestBase {
-
-	@Override
-	protected CachingInternalPriorityQueueSet.OrderedSetStore<TestElement> createOrderedSetStore() {
-		return new TestOrderedStore<>(TEST_ELEMENT_COMPARATOR);
-	}
-
-	@Override
-	protected CachingInternalPriorityQueueSet.OrderedSetCache<TestElement> createOrderedSetCache() {
-		return new TreeOrderedSetCache<>(TEST_ELEMENT_COMPARATOR, 3);
-	}
-}
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/TestOrderedStore.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/TestOrderedStore.java
deleted file mode 100644
index 36a334122c4..00000000000
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/TestOrderedStore.java
+++ /dev/null
@@ -1,60 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.flink.runtime.state.heap;
-
-import org.apache.flink.util.CloseableIterator;
-
-import javax.annotation.Nonnull;
-
-import java.util.Comparator;
-import java.util.TreeSet;
-
-/**
- * Simple implementation of {@link org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet.OrderedSetStore}
- * for tests.
- */
-public class TestOrderedStore<T> implements CachingInternalPriorityQueueSet.OrderedSetStore<T> {
-
-	private final TreeSet<T> treeSet;
-
-	public TestOrderedStore(Comparator<T> comparator) {
-		this.treeSet = new TreeSet<>(comparator);
-	}
-
-	@Override
-	public void add(@Nonnull T element) {
-		treeSet.add(element);
-	}
-
-	@Override
-	public void remove(@Nonnull T element) {
-		treeSet.remove(element);
-	}
-
-	@Override
-	public int size() {
-		return treeSet.size();
-	}
-
-	@Nonnull
-	@Override
-	public CloseableIterator<T> orderedIterator() {
-		return CloseableIterator.adapterForIterator(treeSet.iterator());
-	}
-}
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/TreeOrderedSetCacheTest.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/TreeOrderedSetCacheTest.java
deleted file mode 100644
index cfe823effed..00000000000
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/heap/TreeOrderedSetCacheTest.java
+++ /dev/null
@@ -1,30 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.flink.runtime.state.heap;
-
-/**
- * Test for {@link TreeOrderedSetCache}.
- */
-public class TreeOrderedSetCacheTest extends OrderedSetCacheTestBase {
-
-	@Override
-	protected CachingInternalPriorityQueueSet.OrderedSetCache<Integer> createInstance(int capacity) {
-		return new TreeOrderedSetCache<>(Integer::compareTo, capacity);
-	}
-}
diff --git a/flink-runtime/src/test/java/org/apache/flink/runtime/state/ttl/mock/MockKeyedStateBackend.java b/flink-runtime/src/test/java/org/apache/flink/runtime/state/ttl/mock/MockKeyedStateBackend.java
index 9e9328b75fa..805ae1cd4e7 100644
--- a/flink-runtime/src/test/java/org/apache/flink/runtime/state/ttl/mock/MockKeyedStateBackend.java
+++ b/flink-runtime/src/test/java/org/apache/flink/runtime/state/ttl/mock/MockKeyedStateBackend.java
@@ -109,7 +109,7 @@
 	}
 
 	@Override
-	public int numStateEntries() {
+	public int numKeyValueStateEntries() {
 		int count = 0;
 		for (String state : stateValues.keySet()) {
 			for (K key : stateValues.get(state).keySet()) {
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBCachingPriorityQueueSet.java b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBCachingPriorityQueueSet.java
new file mode 100644
index 00000000000..64f6eb795e2
--- /dev/null
+++ b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBCachingPriorityQueueSet.java
@@ -0,0 +1,561 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.contrib.streaming.state;
+
+import org.apache.flink.api.common.typeutils.TypeSerializer;
+import org.apache.flink.core.memory.ByteArrayInputStreamWithPos;
+import org.apache.flink.core.memory.ByteArrayOutputStreamWithPos;
+import org.apache.flink.core.memory.DataInputViewStreamWrapper;
+import org.apache.flink.core.memory.DataOutputViewStreamWrapper;
+import org.apache.flink.runtime.state.InternalPriorityQueue;
+import org.apache.flink.runtime.state.heap.HeapPriorityQueueElement;
+import org.apache.flink.util.CloseableIterator;
+import org.apache.flink.util.FlinkRuntimeException;
+
+import org.apache.flink.shaded.guava18.com.google.common.primitives.UnsignedBytes;
+
+import org.rocksdb.ColumnFamilyHandle;
+import org.rocksdb.RocksDB;
+import org.rocksdb.RocksDBException;
+
+import javax.annotation.Nonnegative;
+import javax.annotation.Nonnull;
+import javax.annotation.Nullable;
+
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Comparator;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.TreeSet;
+
+import static org.apache.flink.contrib.streaming.state.RocksDBCachingPriorityQueueSet.OrderedByteArraySetCache.LEXICOGRAPHIC_BYTE_COMPARATOR;
+
+/**
+ * A priority queue with set semantics, implemented on top of RocksDB. This uses a {@link TreeSet} to cache the bytes
+ * of up to the first n elements from RocksDB in memory to reduce interaction with RocksDB, in particular seek
+ * operations. Cache uses a simple write-through policy.
+ *
+ * @param <E> the type of the contained elements in the queue.
+ */
+public class RocksDBCachingPriorityQueueSet<E extends HeapPriorityQueueElement>
+	implements InternalPriorityQueue<E>, HeapPriorityQueueElement {
+
+	/** Serialized empty value to insert into RocksDB. */
+	private static final byte[] DUMMY_BYTES = new byte[] {};
+
+	/** The RocksDB instance that serves as store. */
+	@Nonnull
+	private final RocksDB db;
+
+	/** Handle to the column family of the RocksDB instance in which the elements are stored. */
+	@Nonnull
+	private final ColumnFamilyHandle columnFamilyHandle;
+
+	/**
+	 * Serializer for the contained elements. The lexicographical order of the bytes of serialized objects must be
+	 * aligned with their logical order.
+	 */
+	@Nonnull
+	private final TypeSerializer<E> byteOrderProducingSerializer;
+
+	/** Wrapper to batch all writes to RocksDB. */
+	@Nonnull
+	private final RocksDBWriteBatchWrapper batchWrapper;
+
+	/** The key-group id in serialized form. */
+	@Nonnull
+	private final byte[] groupPrefixBytes;
+
+	/** Output stream that helps to serialize elements. */
+	@Nonnull
+	private final ByteArrayOutputStreamWithPos outputStream;
+
+	/** Output view that helps to serialize elements, must wrap the output stream. */
+	@Nonnull
+	private final DataOutputViewStreamWrapper outputView;
+
+	@Nonnull
+	private final ByteArrayInputStreamWithPos inputStream;
+
+	@Nonnull
+	private final DataInputViewStreamWrapper inputView;
+
+	/** In memory cache that holds a partial view on the head of the RocksDB content. */
+	@Nonnull
+	private final OrderedByteArraySetCache orderedCache;
+
+	/** This holds the key that we use to seek to the first element in RocksDB, to improve seek/iterator performance. */
+	@Nonnull
+	private byte[] seekHint;
+
+	/** Cache for the head element in de-serialized form. */
+	@Nullable
+	private E peekCache;
+
+	/** This flag is true if there could be elements in the backend that are not in the cache (false positives ok). */
+	private boolean storeOnlyElements;
+
+	/** Index for management as a {@link HeapPriorityQueueElement}. */
+	private int internalIndex;
+
+	RocksDBCachingPriorityQueueSet(
+		@Nonnegative int keyGroupId,
+		@Nonnegative int keyGroupPrefixBytes,
+		@Nonnull RocksDB db,
+		@Nonnull ColumnFamilyHandle columnFamilyHandle,
+		@Nonnull TypeSerializer<E> byteOrderProducingSerializer,
+		@Nonnull ByteArrayOutputStreamWithPos outputStream,
+		@Nonnull ByteArrayInputStreamWithPos inputStream,
+		@Nonnull RocksDBWriteBatchWrapper batchWrapper,
+		@Nonnull OrderedByteArraySetCache orderedByteArraySetCache) {
+		this.db = db;
+		this.columnFamilyHandle = columnFamilyHandle;
+		this.byteOrderProducingSerializer = byteOrderProducingSerializer;
+		this.outputStream = outputStream;
+		this.inputStream = inputStream;
+		this.batchWrapper = batchWrapper;
+		this.storeOnlyElements = true;
+		this.outputView = new DataOutputViewStreamWrapper(outputStream);
+		this.inputView = new DataInputViewStreamWrapper(inputStream);
+		this.orderedCache = orderedByteArraySetCache;
+		this.groupPrefixBytes = createKeyGroupBytes(keyGroupId, keyGroupPrefixBytes);
+		this.seekHint = groupPrefixBytes;
+		this.internalIndex = HeapPriorityQueueElement.NOT_CONTAINED;
+	}
+
+	@Nullable
+	@Override
+	public E peek() {
+
+		checkRefillCacheFromStore();
+
+		if (peekCache != null) {
+			return peekCache;
+		}
+
+		byte[] firstBytes = orderedCache.peekFirst();
+		if (firstBytes != null) {
+			peekCache = deserializeElement(firstBytes);
+			return peekCache;
+		} else {
+			return null;
+		}
+	}
+
+	@Nullable
+	@Override
+	public E poll() {
+
+		checkRefillCacheFromStore();
+
+		final byte[] firstBytes = orderedCache.pollFirst();
+
+		if (firstBytes == null) {
+			return null;
+		}
+
+		// write-through sync
+		removeFromRocksDB(firstBytes);
+
+		if (orderedCache.isEmpty()) {
+			seekHint = firstBytes;
+		}
+
+		if (peekCache != null) {
+			E fromCache = peekCache;
+			peekCache = null;
+			return fromCache;
+		} else {
+			return deserializeElement(firstBytes);
+		}
+	}
+
+	@Override
+	public boolean add(@Nonnull E toAdd) {
+
+		checkRefillCacheFromStore();
+
+		final byte[] toAddBytes = serializeElement(toAdd);
+
+		final boolean cacheFull = orderedCache.isFull();
+
+		if ((!cacheFull && !storeOnlyElements) ||
+			LEXICOGRAPHIC_BYTE_COMPARATOR.compare(toAddBytes, orderedCache.peekLast()) < 0) {
+
+			if (cacheFull) {
+				// we drop the element with lowest priority from the cache
+				orderedCache.pollLast();
+				// the dropped element is now only in the store
+				storeOnlyElements = true;
+			}
+
+			if (orderedCache.add(toAddBytes)) {
+				// write-through sync
+				addToRocksDB(toAddBytes);
+				if (toAddBytes == orderedCache.peekFirst()) {
+					peekCache = null;
+					return true;
+				}
+			}
+		} else {
+			// we only added to the store
+			addToRocksDB(toAddBytes);
+			storeOnlyElements = true;
+		}
+		return false;
+	}
+
+	@Override
+	public boolean remove(@Nonnull E toRemove) {
+
+		checkRefillCacheFromStore();
+
+		final byte[] oldHead = orderedCache.peekFirst();
+
+		if (oldHead == null) {
+			return false;
+		}
+
+		final byte[] toRemoveBytes = serializeElement(toRemove);
+
+		// write-through sync
+		removeFromRocksDB(toRemoveBytes);
+		orderedCache.remove(toRemoveBytes);
+
+		if (orderedCache.isEmpty()) {
+			seekHint = toRemoveBytes;
+			peekCache = null;
+			return true;
+		}
+
+		if (oldHead != orderedCache.peekFirst()) {
+			peekCache = null;
+			return true;
+		}
+
+		return false;
+	}
+
+	@Override
+	public void addAll(@Nullable Collection<? extends E> toAdd) {
+
+		if (toAdd == null) {
+			return;
+		}
+
+		for (E element : toAdd) {
+			add(element);
+		}
+	}
+
+	@Override
+	public boolean isEmpty() {
+		checkRefillCacheFromStore();
+		return orderedCache.isEmpty();
+	}
+
+	@Nonnull
+	@Override
+	public CloseableIterator<E> iterator() {
+		return new DeserializingIteratorWrapper(orderedBytesIterator());
+	}
+
+	/**
+	 * This implementation comes at a relatively high cost per invocation. It should not be called repeatedly when it is
+	 * clear that the value did not change. Currently this is only truly used to realize certain higher-level tests.
+	 */
+	@Override
+	public int size() {
+
+		if (storeOnlyElements) {
+			int count = 0;
+			try (final RocksBytesIterator iterator = orderedBytesIterator()) {
+				while (iterator.hasNext()) {
+					iterator.next();
+					++count;
+				}
+			}
+			return count;
+		} else {
+			return orderedCache.size();
+		}
+	}
+
+	@Override
+	public int getInternalIndex() {
+		return internalIndex;
+	}
+
+	@Override
+	public void setInternalIndex(int newIndex) {
+		this.internalIndex = newIndex;
+	}
+
+	@Nonnull
+	private RocksBytesIterator orderedBytesIterator() {
+		flushWriteBatch();
+		return new RocksBytesIterator(
+			new RocksIteratorWrapper(
+				db.newIterator(columnFamilyHandle)));
+	}
+
+	/**
+	 * Ensures that recent writes are flushed and reflect in the RocksDB instance.
+	 */
+	private void flushWriteBatch() {
+		try {
+			batchWrapper.flush();
+		} catch (RocksDBException e) {
+			throw new FlinkRuntimeException(e);
+		}
+	}
+
+	private void addToRocksDB(@Nonnull byte[] toAddBytes) {
+		try {
+			batchWrapper.put(columnFamilyHandle, toAddBytes, DUMMY_BYTES);
+		} catch (RocksDBException e) {
+			throw new FlinkRuntimeException(e);
+		}
+	}
+
+	private void removeFromRocksDB(@Nonnull byte[] toRemoveBytes) {
+		try {
+			batchWrapper.remove(columnFamilyHandle, toRemoveBytes);
+		} catch (RocksDBException e) {
+			throw new FlinkRuntimeException(e);
+		}
+	}
+
+	private void checkRefillCacheFromStore() {
+		if (storeOnlyElements && orderedCache.isEmpty()) {
+			try (final RocksBytesIterator iterator = orderedBytesIterator()) {
+				orderedCache.bulkLoadFromOrderedIterator(iterator);
+				storeOnlyElements = iterator.hasNext();
+			} catch (Exception e) {
+				throw new FlinkRuntimeException("Exception while refilling store from iterator.", e);
+			}
+		}
+	}
+
+	private static boolean isPrefixWith(byte[] bytes, byte[] prefixBytes) {
+		for (int i = 0; i < prefixBytes.length; ++i) {
+			if (bytes[i] != prefixBytes[i]) {
+				return false;
+			}
+		}
+		return true;
+	}
+
+	@Nonnull
+	private byte[] createKeyGroupBytes(int keyGroupId, int numPrefixBytes) {
+
+		outputStream.reset();
+
+		try {
+			RocksDBKeySerializationUtils.writeKeyGroup(keyGroupId, numPrefixBytes, outputView);
+		} catch (IOException e) {
+			throw new FlinkRuntimeException("Could not write key-group bytes.", e);
+		}
+
+		return outputStream.toByteArray();
+	}
+
+	@Nonnull
+	private byte[] serializeElement(@Nonnull E element) {
+		try {
+			outputStream.reset();
+			outputView.write(groupPrefixBytes);
+			byteOrderProducingSerializer.serialize(element, outputView);
+			return outputStream.toByteArray();
+		} catch (IOException e) {
+			throw new FlinkRuntimeException("Error while serializing the element.", e);
+		}
+	}
+
+	@Nonnull
+	private E deserializeElement(@Nonnull byte[] bytes) {
+		try {
+			inputStream.setBuffer(bytes, 0, bytes.length);
+			inputView.skipBytes(groupPrefixBytes.length);
+			return byteOrderProducingSerializer.deserialize(inputView);
+		} catch (IOException e) {
+			throw new FlinkRuntimeException("Error while deserializing the element.", e);
+		}
+	}
+
+	/**
+	 * Wraps an iterator over byte-arrays with deserialization logic, so that it iterates over deserialized objects.
+	 */
+	private class DeserializingIteratorWrapper implements CloseableIterator<E> {
+
+		/** The iterator over byte-arrays with the serialized objects. */
+		@Nonnull
+		private final CloseableIterator<byte[]> bytesIterator;
+
+		private DeserializingIteratorWrapper(@Nonnull CloseableIterator<byte[]> bytesIterator) {
+			this.bytesIterator = bytesIterator;
+		}
+
+		@Override
+		public void close() throws Exception {
+			bytesIterator.close();
+		}
+
+		@Override
+		public boolean hasNext() {
+			return bytesIterator.hasNext();
+		}
+
+		@Override
+		public E next() {
+			return deserializeElement(bytesIterator.next());
+		}
+	}
+
+	/**
+	 * Adapter between RocksDB iterator and Java iterator. This is also closeable to release the native resources after
+	 * use.
+	 */
+	private class RocksBytesIterator implements CloseableIterator<byte[]> {
+
+		/** The RocksDb iterator to which we forward ops. */
+		@Nonnull
+		private final RocksIteratorWrapper iterator;
+
+		/** Cache for the current element of the iteration. */
+		@Nullable
+		private byte[] currentElement;
+
+		private RocksBytesIterator(@Nonnull RocksIteratorWrapper iterator) {
+			this.iterator = iterator;
+			try {
+				// We use our knowledge about the lower bound to issue a seek that is as close to the first element in
+				// the key-group as possible, i.e. we generate the next possible key after seekHint by appending one
+				// zero-byte.
+				iterator.seek(Arrays.copyOf(seekHint, seekHint.length + 1));
+				currentElement = nextElementIfAvailable();
+			} catch (Exception ex) {
+				// ensure resource cleanup also in the face of (runtime) exceptions in the constructor.
+				iterator.close();
+				throw new FlinkRuntimeException("Could not initialize ordered iterator.", ex);
+			}
+		}
+
+		@Override
+		public void close() {
+			iterator.close();
+		}
+
+		@Override
+		public boolean hasNext() {
+			return currentElement != null;
+		}
+
+		@Override
+		public byte[] next() {
+			final byte[] returnElement = this.currentElement;
+			if (returnElement == null) {
+				throw new NoSuchElementException("Iterator has no more elements!");
+			}
+			iterator.next();
+			currentElement = nextElementIfAvailable();
+			return returnElement;
+		}
+
+		private byte[] nextElementIfAvailable() {
+			final byte[] elementBytes;
+			return iterator.isValid()
+				&& isPrefixWith((elementBytes = iterator.key()), groupPrefixBytes) ? elementBytes : null;
+		}
+	}
+
+	/**
+	 * Cache that is organized as an ordered set for byte-arrays. THe byte-arrays are sorted in lexicographic order
+	 * of their content. Caches typically have a bounded size.
+	 */
+	public interface OrderedByteArraySetCache {
+
+		/** Comparator for byte arrays. */
+		Comparator<byte[]> LEXICOGRAPHIC_BYTE_COMPARATOR = UnsignedBytes.lexicographicalComparator();
+
+		/**
+		 * Returns the number of contained elements.
+		 */
+		int size();
+
+		/**
+		 * Returns the maximum number of elements that can be stored in the cache.
+		 */
+		int maxSize();
+
+		/**
+		 * Returns <code>size() == 0</code>.
+		 */
+		boolean isEmpty();
+
+		/**
+		 * Returns <code>size() == maxSize()</code>.
+		 */
+		boolean isFull();
+
+		/**
+		 * Adds the given element, if it was not already contained. Returns <code>true</code> iff the cache was modified.
+		 */
+		boolean add(@Nonnull byte[] toAdd);
+
+		/**
+		 * Removes the given element, if it is contained. Returns <code>true</code> iff the cache was modified.
+		 */
+		boolean remove(@Nonnull byte[] toRemove);
+
+		/**
+		 * Returns the first element or <code>null</code> if empty.
+		 */
+		@Nullable
+		byte[] peekFirst();
+
+		/**
+		 * Returns the last element or <code>null</code> if empty.
+		 */
+		@Nullable
+		byte[] peekLast();
+
+		/**
+		 * Returns and removes the first element or returns <code>null</code> if empty.
+		 */
+		@Nullable
+		byte[] pollFirst();
+
+		/**
+		 * Returns and removes the last element or returns <code>null</code> if empty.
+		 */
+		@Nullable
+		byte[] pollLast();
+
+		/**
+		 * Clears the cache and adds up to <code>maxSize()</code> elements from the iterator to the cache.
+		 * Iterator must be ordered in the same order as this cache.
+		 *
+		 * @param orderedIterator iterator with elements in-order.
+		 */
+		void bulkLoadFromOrderedIterator(@Nonnull Iterator<byte[]> orderedIterator);
+	}
+}
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBKeyedStateBackend.java b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBKeyedStateBackend.java
index 72aa4fbaeb2..9f45252c848 100644
--- a/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBKeyedStateBackend.java
+++ b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBKeyedStateBackend.java
@@ -27,6 +27,7 @@
 import org.apache.flink.api.common.state.State;
 import org.apache.flink.api.common.state.StateDescriptor;
 import org.apache.flink.api.common.state.ValueStateDescriptor;
+import org.apache.flink.api.common.typeutils.CompatibilityResult;
 import org.apache.flink.api.common.typeutils.CompatibilityUtil;
 import org.apache.flink.api.common.typeutils.TypeSerializer;
 import org.apache.flink.api.common.typeutils.UnloadableDummyTypeSerializer;
@@ -84,13 +85,10 @@
 import org.apache.flink.runtime.state.StateUtil;
 import org.apache.flink.runtime.state.StreamCompressionDecorator;
 import org.apache.flink.runtime.state.StreamStateHandle;
-import org.apache.flink.runtime.state.TieBreakingPriorityComparator;
 import org.apache.flink.runtime.state.UncompressedStreamCompressionDecorator;
-import org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet;
 import org.apache.flink.runtime.state.heap.HeapPriorityQueueElement;
 import org.apache.flink.runtime.state.heap.HeapPriorityQueueSetFactory;
 import org.apache.flink.runtime.state.heap.KeyGroupPartitionedPriorityQueue;
-import org.apache.flink.runtime.state.heap.TreeOrderedSetCache;
 import org.apache.flink.runtime.state.metainfo.StateMetaInfoSnapshot;
 import org.apache.flink.runtime.state.ttl.TtlTimeProvider;
 import org.apache.flink.util.ExceptionUtils;
@@ -262,6 +260,7 @@
 	/** Factory for priority queue state. */
 	private final PriorityQueueSetFactory priorityQueueFactory;
 
+	/** Shared wrapper for batch writes to the RocksDB instance. */
 	private RocksDBWriteBatchWrapper writeBatchWrapper;
 
 	public RocksDBKeyedStateBackend(
@@ -458,6 +457,11 @@ public int getKeyGroupPrefixBytes() {
 		return keyGroupPrefixBytes;
 	}
 
+	@VisibleForTesting
+	PriorityQueueSetFactory getPriorityQueueFactory() {
+		return priorityQueueFactory;
+	}
+
 	public WriteOptions getWriteOptions() {
 		return writeOptions;
 	}
@@ -481,6 +485,9 @@ public WriteOptions getWriteOptions() {
 		final CheckpointStreamFactory streamFactory,
 		CheckpointOptions checkpointOptions) throws Exception {
 
+		// flush everything into db before taking a snapshot
+		writeBatchWrapper.flush();
+
 		return snapshotStrategy.performSnapshot(checkpointId, timestamp, streamFactory, checkpointOptions);
 	}
 
@@ -1311,7 +1318,6 @@ private void copyStateDataHandleData(
 		RegisteredKeyValueStateBackendMetaInfo<N, S> newMetaInfo;
 		if (stateInfo != null) {
 
-			@SuppressWarnings("unchecked")
 			StateMetaInfoSnapshot restoredMetaInfoSnapshot = restoredKvStateMetaInfos.get(stateDesc.getName());
 
 			Preconditions.checkState(
@@ -1390,7 +1396,7 @@ public boolean supportsAsynchronousSnapshots() {
 	@VisibleForTesting
 	@SuppressWarnings("unchecked")
 	@Override
-	public int numStateEntries() {
+	public int numKeyValueStateEntries() {
 		int count = 0;
 
 		for (Tuple2<ColumnFamilyHandle, RegisteredStateMetaInfoBase> column : kvStateInformation.values()) {
@@ -1775,9 +1781,6 @@ public void close() {
 
 			final CloseableRegistry snapshotCloseableRegistry = new CloseableRegistry();
 
-			// flush everything into db before taking a snapshot
-			writeBatchWrapper.flush();
-
 			final RocksDBFullSnapshotOperation<K> snapshotOperation =
 				new RocksDBFullSnapshotOperation<>(
 					RocksDBKeyedStateBackend.this,
@@ -2643,19 +2646,19 @@ public static RocksIteratorWrapper getRocksIterator(
 	class RocksDBPriorityQueueSetFactory implements PriorityQueueSetFactory {
 
 		/** Default cache size per key-group. */
-		private static final int DEFAULT_CACHES_SIZE = 1024;
+		private static final int DEFAULT_CACHES_SIZE = 128; //TODO make this configurable
 
 		/** A shared buffer to serialize elements for the priority queue. */
 		@Nonnull
 		private final ByteArrayOutputStreamWithPos elementSerializationOutStream;
 
-		/** A shared adapter wrapper around elementSerializationOutStream to become a {@link DataOutputView}. */
+		/** A shared buffer to de-serialize elements for the priority queue. */
 		@Nonnull
-		private final DataOutputViewStreamWrapper elementSerializationOutView;
+		private final ByteArrayInputStreamWithPos elementSerializationInStream;
 
 		RocksDBPriorityQueueSetFactory() {
 			this.elementSerializationOutStream = new ByteArrayOutputStreamWithPos();
-			this.elementSerializationOutView = new DataOutputViewStreamWrapper(elementSerializationOutStream);
+			this.elementSerializationInStream = new ByteArrayInputStreamWithPos();
 		}
 
 		@Nonnull
@@ -2665,57 +2668,77 @@ public static RocksIteratorWrapper getRocksIterator(
 			@Nonnull String stateName,
 			@Nonnull TypeSerializer<T> byteOrderedElementSerializer) {
 
-			final PriorityComparator<T> priorityComparator =
-				PriorityComparator.forPriorityComparableObjects();
-
-			Tuple2<ColumnFamilyHandle, RegisteredStateMetaInfoBase> entry =
+			Tuple2<ColumnFamilyHandle, RegisteredStateMetaInfoBase> metaInfoTuple =
 				kvStateInformation.get(stateName);
 
-			if (entry == null) {
+			if (metaInfoTuple == null) {
+				final ColumnFamilyHandle columnFamilyHandle = createColumnFamily(stateName);
+
 				RegisteredPriorityQueueStateBackendMetaInfo<T> metaInfo =
 					new RegisteredPriorityQueueStateBackendMetaInfo<>(stateName, byteOrderedElementSerializer);
 
-				final ColumnFamilyHandle columnFamilyHandle = createColumnFamily(stateName);
+				metaInfoTuple = new Tuple2<>(columnFamilyHandle, metaInfo);
+				kvStateInformation.put(stateName, metaInfoTuple);
+			} else {
+				// TODO we implement the simple way of supporting the current functionality, mimicking keyed state
+				// because this should be reworked in FLINK-9376 and then we should have a common algorithm over
+				// StateMetaInfoSnapshot that avoids this code duplication.
+				StateMetaInfoSnapshot restoredMetaInfoSnapshot = restoredKvStateMetaInfos.get(stateName);
+
+				Preconditions.checkState(
+					restoredMetaInfoSnapshot != null,
+					"Requested to check compatibility of a restored RegisteredKeyedBackendStateMetaInfo," +
+						" but its corresponding restored snapshot cannot be found.");
+
+				StateMetaInfoSnapshot.CommonSerializerKeys serializerKey =
+					StateMetaInfoSnapshot.CommonSerializerKeys.VALUE_SERIALIZER;
+
+				TypeSerializer<?> metaInfoTypeSerializer = restoredMetaInfoSnapshot.getTypeSerializer(serializerKey);
+
+				if (metaInfoTypeSerializer != byteOrderedElementSerializer) {
+					CompatibilityResult<T> compatibilityResult = CompatibilityUtil.resolveCompatibilityResult(
+						metaInfoTypeSerializer,
+						null,
+						restoredMetaInfoSnapshot.getTypeSerializerConfigSnapshot(serializerKey),
+						byteOrderedElementSerializer);
+
+					if (compatibilityResult.isRequiresMigration()) {
+						throw new FlinkRuntimeException(StateMigrationException.notSupported());
+					}
 
-				entry = new Tuple2<>(columnFamilyHandle, metaInfo);
-				kvStateInformation.put(stateName, entry);
+					// update meta info with new serializer
+					metaInfoTuple.f1 =
+						new RegisteredPriorityQueueStateBackendMetaInfo<>(stateName, byteOrderedElementSerializer);
+				}
 			}
 
-			final ColumnFamilyHandle columnFamilyHandle = entry.f0;
-
-			@Nonnull
-			TieBreakingPriorityComparator<T> tieBreakingComparator =
-				new TieBreakingPriorityComparator<>(
-					priorityComparator,
-					byteOrderedElementSerializer,
-					elementSerializationOutStream,
-					elementSerializationOutView);
+			final ColumnFamilyHandle columnFamilyHandle = metaInfoTuple.f0;
+			final PriorityComparator<T> priorityComparator =
+				PriorityComparator.forPriorityComparableObjects();
 
 			return new KeyGroupPartitionedPriorityQueue<>(
 				KeyExtractorFunction.forKeyedObjects(),
 				priorityComparator,
-				new KeyGroupPartitionedPriorityQueue.PartitionQueueSetFactory<T, CachingInternalPriorityQueueSet<T>>() {
+				new KeyGroupPartitionedPriorityQueue.PartitionQueueSetFactory<T, RocksDBCachingPriorityQueueSet<T>>() {
 					@Nonnull
 					@Override
-					public CachingInternalPriorityQueueSet<T> create(
+					public RocksDBCachingPriorityQueueSet<T> create(
 						int keyGroupId,
 						int numKeyGroups,
+						@Nonnull KeyExtractorFunction<T> keyExtractor,
 						@Nonnull PriorityComparator<T> elementPriorityComparator) {
-
-						CachingInternalPriorityQueueSet.OrderedSetCache<T> cache =
-							new TreeOrderedSetCache<>(tieBreakingComparator, DEFAULT_CACHES_SIZE);
-						CachingInternalPriorityQueueSet.OrderedSetStore<T> store =
-							new RocksDBOrderedSetStore<>(
-								keyGroupId,
-								keyGroupPrefixBytes,
-								db,
-								columnFamilyHandle,
-								byteOrderedElementSerializer,
-								elementSerializationOutStream,
-								elementSerializationOutView,
-								writeBatchWrapper);
-
-						return new CachingInternalPriorityQueueSet<>(cache, store);
+						TreeOrderedSetCache orderedSetCache = new TreeOrderedSetCache(DEFAULT_CACHES_SIZE);
+						return new RocksDBCachingPriorityQueueSet<>(
+							keyGroupId,
+							keyGroupPrefixBytes,
+							db,
+							columnFamilyHandle,
+							byteOrderedElementSerializer,
+							elementSerializationOutStream,
+							elementSerializationInStream,
+							writeBatchWrapper,
+							orderedSetCache
+						);
 					}
 				},
 				keyGroupRange,
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBOptions.java b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBOptions.java
index 18f9ec95244..c85a7b2077c 100644
--- a/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBOptions.java
+++ b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBOptions.java
@@ -39,9 +39,10 @@
 	/**
 	 * Choice of timer service implementation.
 	 */
-	public static final ConfigOption<String> TIMER_SERVICE_IMPL = ConfigOptions
-		.key("state.backend.rocksdb.timer-service.impl")
+	public static final ConfigOption<String> TIMER_SERVICE_FACTORY = ConfigOptions
+		.key("state.backend.rocksdb.timer-service.factory")
 		.defaultValue(HEAP.name())
-		.withDescription(String.format("This determines the timer service implementation. Options are either %s " +
-			"(heap-based, default) or %s for an implementation based on RocksDB.", HEAP.name(), ROCKSDB.name()));
+		.withDescription(String.format("This determines the factory for timer service state implementation. Options " +
+			"are either %s (heap-based, default) or %s for an implementation based on RocksDB .",
+			HEAP.name(), ROCKSDB.name()));
 }
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBOrderedSetStore.java b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBOrderedSetStore.java
deleted file mode 100644
index 4068c508955..00000000000
--- a/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBOrderedSetStore.java
+++ /dev/null
@@ -1,274 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.flink.contrib.streaming.state;
-
-import org.apache.flink.api.common.typeutils.TypeSerializer;
-import org.apache.flink.core.memory.ByteArrayInputStreamWithPos;
-import org.apache.flink.core.memory.ByteArrayOutputStreamWithPos;
-import org.apache.flink.core.memory.DataInputViewStreamWrapper;
-import org.apache.flink.core.memory.DataOutputViewStreamWrapper;
-import org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet;
-import org.apache.flink.util.CloseableIterator;
-import org.apache.flink.util.FlinkRuntimeException;
-
-import org.rocksdb.ColumnFamilyHandle;
-import org.rocksdb.RocksDB;
-import org.rocksdb.RocksDBException;
-
-import javax.annotation.Nonnegative;
-import javax.annotation.Nonnull;
-import javax.annotation.Nullable;
-
-import java.io.IOException;
-import java.util.NoSuchElementException;
-
-/**
- * Implementation of {@link org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet.OrderedSetStore}
- * based on RocksDB.
- *
- * <p>IMPORTANT: The store is ordered and the order is determined by the lexicographic order of the byte sequences
- * produced by the provided serializer for the elements!
- *
- * @param <T> the type of stored elements.
- */
-public class RocksDBOrderedSetStore<T> implements CachingInternalPriorityQueueSet.OrderedSetStore<T> {
-
-	/** Serialized empty value to insert into RocksDB. */
-	private static final byte[] DUMMY_BYTES = new byte[] {0};
-
-	/** The RocksDB instance that serves as store. */
-	@Nonnull
-	private final RocksDB db;
-
-	/** Handle to the column family of the RocksDB instance in which the elements are stored. */
-	@Nonnull
-	private final ColumnFamilyHandle columnFamilyHandle;
-
-	/**
-	 * Serializer for the contained elements. The lexicographical order of the bytes of serialized objects must be
-	 * aligned with their logical order.
-	 */
-	@Nonnull
-	private final TypeSerializer<T> byteOrderProducingSerializer;
-
-	/** Wrapper to batch all writes to RocksDB. */
-	@Nonnull
-	private final RocksDBWriteBatchWrapper batchWrapper;
-
-	/** The key-group id in serialized form. */
-	@Nonnull
-	private final byte[] groupPrefixBytes;
-
-	/** Output stream that helps to serialize elements. */
-	@Nonnull
-	private final ByteArrayOutputStreamWithPos outputStream;
-
-	/** Output view that helps to serialize elements, must wrap the output stream. */
-	@Nonnull
-	private final DataOutputViewStreamWrapper outputView;
-
-	public RocksDBOrderedSetStore(
-		@Nonnegative int keyGroupId,
-		@Nonnegative int keyGroupPrefixBytes,
-		@Nonnull RocksDB db,
-		@Nonnull ColumnFamilyHandle columnFamilyHandle,
-		@Nonnull TypeSerializer<T> byteOrderProducingSerializer,
-		@Nonnull ByteArrayOutputStreamWithPos outputStream,
-		@Nonnull DataOutputViewStreamWrapper outputView,
-		@Nonnull RocksDBWriteBatchWrapper batchWrapper) {
-		this.db = db;
-		this.columnFamilyHandle = columnFamilyHandle;
-		this.byteOrderProducingSerializer = byteOrderProducingSerializer;
-		this.outputStream = outputStream;
-		this.outputView = outputView;
-		this.batchWrapper = batchWrapper;
-		this.groupPrefixBytes = createKeyGroupBytes(keyGroupId, keyGroupPrefixBytes);
-	}
-
-	private byte[] createKeyGroupBytes(int keyGroupId, int numPrefixBytes) {
-
-		outputStream.reset();
-
-		try {
-			RocksDBKeySerializationUtils.writeKeyGroup(keyGroupId, numPrefixBytes, outputView);
-		} catch (IOException e) {
-			throw new FlinkRuntimeException("Could not write key-group bytes.", e);
-		}
-
-		return outputStream.toByteArray();
-	}
-
-	@Override
-	public void add(@Nonnull T element) {
-		byte[] elementBytes = serializeElement(element);
-		try {
-			batchWrapper.put(columnFamilyHandle, elementBytes, DUMMY_BYTES);
-		} catch (RocksDBException e) {
-			throw new FlinkRuntimeException("Error while getting element from RocksDB.", e);
-		}
-	}
-
-	@Override
-	public void remove(@Nonnull T element) {
-		byte[] elementBytes = serializeElement(element);
-		try {
-			batchWrapper.remove(columnFamilyHandle, elementBytes);
-		} catch (RocksDBException e) {
-			throw new FlinkRuntimeException("Error while removing element from RocksDB.", e);
-		}
-	}
-
-	/**
-	 * This implementation comes at a relatively high cost per invocation. It should not be called repeatedly when it is
-	 * clear that the value did not change. Currently this is only truly used to realize certain higher-level tests.
-	 *
-	 * @see org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet.OrderedSetStore
-	 */
-	@Override
-	public int size() {
-
-		int count = 0;
-		try (final RocksToJavaIteratorAdapter iterator = orderedIterator()) {
-			while (iterator.hasNext()) {
-				iterator.next();
-				++count;
-			}
-		}
-
-		return count;
-	}
-
-	@Nonnull
-	@Override
-	public RocksToJavaIteratorAdapter orderedIterator() {
-
-		flushWriteBatch();
-		return new RocksToJavaIteratorAdapter(
-			new RocksIteratorWrapper(
-				db.newIterator(columnFamilyHandle)));
-	}
-
-	/**
-	 * Ensures that recent writes are flushed and reflect in the RocksDB instance.
-	 */
-	private void flushWriteBatch() {
-		try {
-			batchWrapper.flush();
-		} catch (RocksDBException e) {
-			throw new FlinkRuntimeException(e);
-		}
-	}
-
-	private static boolean isPrefixWith(byte[] bytes, byte[] prefixBytes) {
-		for (int i = 0; i < prefixBytes.length; ++i) {
-			if (bytes[i] != prefixBytes[i]) {
-				return false;
-			}
-		}
-		return true;
-	}
-
-	private byte[] serializeElement(T element) {
-		try {
-			outputStream.reset();
-			outputView.write(groupPrefixBytes);
-			byteOrderProducingSerializer.serialize(element, outputView);
-			return outputStream.toByteArray();
-		} catch (IOException e) {
-			throw new FlinkRuntimeException("Error while serializing the element.", e);
-		}
-	}
-
-	private T deserializeElement(byte[] bytes) {
-		try {
-			// TODO introduce a stream in which we can change the internal byte[] to avoid creating instances per call
-			ByteArrayInputStreamWithPos inputStream = new ByteArrayInputStreamWithPos(bytes);
-			DataInputViewStreamWrapper inputView = new DataInputViewStreamWrapper(inputStream);
-			inputView.skipBytes(groupPrefixBytes.length);
-			return byteOrderProducingSerializer.deserialize(inputView);
-		} catch (IOException e) {
-			throw new FlinkRuntimeException("Error while deserializing the element.", e);
-		}
-	}
-
-	/**
-	 * Adapter between RocksDB iterator and Java iterator. This is also closeable to release the native resources after
-	 * use.
-	 */
-	private class RocksToJavaIteratorAdapter implements CloseableIterator<T> {
-
-		/** The RocksDb iterator to which we forward ops. */
-		@Nonnull
-		private final RocksIteratorWrapper iterator;
-
-		/** Cache for the current element of the iteration. */
-		@Nullable
-		private T currentElement;
-
-		private RocksToJavaIteratorAdapter(@Nonnull RocksIteratorWrapper iterator) {
-			this.iterator = iterator;
-			try {
-				// TODO we could check if it is more efficient to make the seek more specific, e.g. with a provided hint
-				// that is lexicographically closer the first expected element in the key-group. I wonder if this could
-				// help to improve the seek if there are many tombstones for elements at the beginning of the key-group
-				// (like for elements that have been removed in previous polling, before they are compacted away).
-				iterator.seek(groupPrefixBytes);
-				deserializeNextElementIfAvailable();
-			} catch (Exception ex) {
-				// ensure resource cleanup also in the face of (runtime) exceptions in the constructor.
-				iterator.close();
-				throw new FlinkRuntimeException("Could not initialize ordered iterator.", ex);
-			}
-		}
-
-		@Override
-		public void close() {
-			iterator.close();
-		}
-
-		@Override
-		public boolean hasNext() {
-			return currentElement != null;
-		}
-
-		@Override
-		public T next() {
-			final T returnElement = this.currentElement;
-			if (returnElement == null) {
-				throw new NoSuchElementException("Iterator has no more elements!");
-			}
-			iterator.next();
-			deserializeNextElementIfAvailable();
-			return returnElement;
-		}
-
-		private void deserializeNextElementIfAvailable() {
-			if (iterator.isValid()) {
-				final byte[] elementBytes = iterator.key();
-				if (isPrefixWith(elementBytes, groupPrefixBytes)) {
-					this.currentElement = deserializeElement(elementBytes);
-				} else {
-					this.currentElement = null;
-				}
-			} else {
-				this.currentElement = null;
-			}
-		}
-	}
-}
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackend.java b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackend.java
index 056484939e7..b8bd73c08e1 100644
--- a/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackend.java
+++ b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackend.java
@@ -60,7 +60,7 @@
 import java.util.Random;
 import java.util.UUID;
 
-import static org.apache.flink.contrib.streaming.state.RocksDBOptions.TIMER_SERVICE_IMPL;
+import static org.apache.flink.contrib.streaming.state.RocksDBOptions.TIMER_SERVICE_FACTORY;
 import static org.apache.flink.util.Preconditions.checkNotNull;
 
 /**
@@ -271,7 +271,7 @@ private RocksDBStateBackend(RocksDBStateBackend original, Configuration config)
 		this.enableIncrementalCheckpointing = original.enableIncrementalCheckpointing.resolveUndefined(
 			config.getBoolean(CheckpointingOptions.INCREMENTAL_CHECKPOINTS));
 
-		final String priorityQueueTypeString = config.getString(TIMER_SERVICE_IMPL);
+		final String priorityQueueTypeString = config.getString(TIMER_SERVICE_FACTORY);
 
 		this.priorityQueueStateType = priorityQueueTypeString.length() > 0 ?
 			PriorityQueueStateType.valueOf(priorityQueueTypeString.toUpperCase()) : original.priorityQueueStateType;
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/TreeOrderedSetCache.java b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/TreeOrderedSetCache.java
new file mode 100644
index 00000000000..c48cc745ae3
--- /dev/null
+++ b/flink-state-backends/flink-statebackend-rocksdb/src/main/java/org/apache/flink/contrib/streaming/state/TreeOrderedSetCache.java
@@ -0,0 +1,104 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.contrib.streaming.state;
+
+import javax.annotation.Nonnull;
+import javax.annotation.Nullable;
+
+import java.util.Iterator;
+import java.util.TreeSet;
+
+/**
+ * Implementation of a lexicographically ordered set of byte-arrays, based on a {@link TreeSet}.
+ */
+public class TreeOrderedSetCache implements RocksDBCachingPriorityQueueSet.OrderedByteArraySetCache {
+
+	/** Maximum capacity. */
+	private final int maxSize;
+
+	@Nonnull
+	private final TreeSet<byte[]> treeSet;
+
+	TreeOrderedSetCache(int maxSize) {
+		this.maxSize = maxSize;
+		this.treeSet = new TreeSet<>(LEXICOGRAPHIC_BYTE_COMPARATOR);
+	}
+
+	@Override
+	public int size() {
+		return treeSet.size();
+	}
+
+	@Override
+	public int maxSize() {
+		return maxSize;
+	}
+
+	@Override
+	public boolean isEmpty() {
+		return treeSet.isEmpty();
+	}
+
+	@Override
+	public boolean isFull() {
+		return treeSet.size() >= maxSize;
+	}
+
+	@Override
+	public boolean add(@Nonnull byte[] toAdd) {
+		return treeSet.add(toAdd);
+	}
+
+	@Override
+	public boolean remove(@Nonnull byte[] toRemove) {
+		return treeSet.remove(toRemove);
+	}
+
+	@Nullable
+	@Override
+	public byte[] peekFirst() {
+		return !isEmpty() ? treeSet.first() : null;
+	}
+
+	@Nullable
+	@Override
+	public byte[] peekLast() {
+		return !isEmpty() ? treeSet.last() : null;
+	}
+
+	@Nullable
+	@Override
+	public byte[] pollFirst() {
+		return !isEmpty() ? treeSet.pollFirst() : null;
+	}
+
+	@Nullable
+	@Override
+	public byte[] pollLast() {
+		return !isEmpty() ? treeSet.pollLast() : null;
+	}
+
+	@Override
+	public void bulkLoadFromOrderedIterator(@Nonnull Iterator<byte[]> orderedIterator) {
+		treeSet.clear();
+		for (int i = maxSize; --i >= 0 && orderedIterator.hasNext(); ) {
+			treeSet.add(orderedIterator.next());
+		}
+	}
+}
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/CachingInternalPriorityQueueSetWithRocksDBStoreTest.java b/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/CachingInternalPriorityQueueSetWithRocksDBStoreTest.java
deleted file mode 100644
index 5f26835282c..00000000000
--- a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/CachingInternalPriorityQueueSetWithRocksDBStoreTest.java
+++ /dev/null
@@ -1,65 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.flink.contrib.streaming.state;
-
-import org.apache.flink.core.memory.ByteArrayOutputStreamWithPos;
-import org.apache.flink.core.memory.DataOutputViewStreamWrapper;
-import org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet;
-import org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSetTestBase;
-import org.apache.flink.runtime.state.heap.TreeOrderedSetCache;
-
-import org.junit.Rule;
-
-/**
- * Test for {@link CachingInternalPriorityQueueSet} with a
- * {@link org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet.OrderedSetStore} based on RocksDB.
- */
-public class CachingInternalPriorityQueueSetWithRocksDBStoreTest extends CachingInternalPriorityQueueSetTestBase {
-
-	@Rule
-	public final RocksDBResource rocksDBResource = new RocksDBResource();
-
-	@Override
-	protected CachingInternalPriorityQueueSet.OrderedSetStore<TestElement> createOrderedSetStore() {
-		return createRocksDBStore(0, 1, rocksDBResource);
-	}
-
-	@Override
-	protected CachingInternalPriorityQueueSet.OrderedSetCache<TestElement> createOrderedSetCache() {
-		return new TreeOrderedSetCache<>(TEST_ELEMENT_COMPARATOR, 32);
-	}
-
-	public static CachingInternalPriorityQueueSet.OrderedSetStore<TestElement> createRocksDBStore(
-		int keyGroupId,
-		int totalKeyGroups,
-		RocksDBResource rocksDBResource) {
-		ByteArrayOutputStreamWithPos outputStream = new ByteArrayOutputStreamWithPos(16);
-		DataOutputViewStreamWrapper outputView = new DataOutputViewStreamWrapper(outputStream);
-		int prefixBytes = RocksDBKeySerializationUtils.computeRequiredBytesInKeyGroupPrefix(totalKeyGroups);
-		return new RocksDBOrderedSetStore<>(
-			keyGroupId,
-			prefixBytes,
-			rocksDBResource.getRocksDB(),
-			rocksDBResource.getDefaultColumnFamily(),
-			TestElementSerializer.INSTANCE,
-			outputStream,
-			outputView,
-			rocksDBResource.getBatchWrapper());
-	}
-}
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/KeyGroupPartitionedPriorityQueueWithRocksDBStoreTest.java b/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/KeyGroupPartitionedPriorityQueueWithRocksDBStoreTest.java
index 42782a40e87..2cd16cf57ae 100644
--- a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/KeyGroupPartitionedPriorityQueueWithRocksDBStoreTest.java
+++ b/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/KeyGroupPartitionedPriorityQueueWithRocksDBStoreTest.java
@@ -18,36 +18,54 @@
 
 package org.apache.flink.contrib.streaming.state;
 
-import org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet;
+import org.apache.flink.core.memory.ByteArrayInputStreamWithPos;
+import org.apache.flink.core.memory.ByteArrayOutputStreamWithPos;
+import org.apache.flink.runtime.state.InternalPriorityQueue;
+import org.apache.flink.runtime.state.InternalPriorityQueueTestBase;
 import org.apache.flink.runtime.state.heap.KeyGroupPartitionedPriorityQueue;
-import org.apache.flink.runtime.state.heap.KeyGroupPartitionedPriorityQueueTest;
-import org.apache.flink.runtime.state.heap.TreeOrderedSetCache;
 
 import org.junit.Rule;
 
 /**
- * Test of {@link KeyGroupPartitionedPriorityQueue} powered by a {@link RocksDBOrderedSetStore}.
+ * Test of {@link KeyGroupPartitionedPriorityQueue} powered by a {@link RocksDBCachingPriorityQueueSet}.
  */
-public class KeyGroupPartitionedPriorityQueueWithRocksDBStoreTest extends KeyGroupPartitionedPriorityQueueTest {
+public class KeyGroupPartitionedPriorityQueueWithRocksDBStoreTest extends InternalPriorityQueueTestBase {
 
 	@Rule
 	public final RocksDBResource rocksDBResource = new RocksDBResource();
 
 	@Override
-	protected KeyGroupPartitionedPriorityQueue.PartitionQueueSetFactory<
-			TestElement, CachingInternalPriorityQueueSet<TestElement>> newFactory(
-		int initialCapacity) {
-
-		return (keyGroupId, numKeyGroups, elementComparator) -> {
-			CachingInternalPriorityQueueSet.OrderedSetCache<TestElement> cache =
-				new TreeOrderedSetCache<>(TEST_ELEMENT_COMPARATOR, 32);
-			CachingInternalPriorityQueueSet.OrderedSetStore<TestElement> store =
-				RocksDBOrderedSetStoreTest.createRocksDBOrderedStore(
-					rocksDBResource,
-					TestElementSerializer.INSTANCE,
-					keyGroupId,
-					numKeyGroups);
-			return new CachingInternalPriorityQueueSet<>(cache, store);
+	protected InternalPriorityQueue<TestElement> newPriorityQueue(int initialCapacity) {
+		return new KeyGroupPartitionedPriorityQueue<>(
+			KEY_EXTRACTOR_FUNCTION,
+			TEST_ELEMENT_PRIORITY_COMPARATOR,
+			newFactory(initialCapacity),
+			KEY_GROUP_RANGE, KEY_GROUP_RANGE.getNumberOfKeyGroups());
+	}
+
+	@Override
+	protected boolean testSetSemanticsAgainstDuplicateElements() {
+		return true;
+	}
+
+	private KeyGroupPartitionedPriorityQueue.PartitionQueueSetFactory<
+		TestElement, RocksDBCachingPriorityQueueSet<TestElement>> newFactory(int initialCapacity) {
+
+		return (keyGroupId, numKeyGroups, keyExtractorFunction, elementComparator) -> {
+			ByteArrayOutputStreamWithPos outputStreamWithPos = new ByteArrayOutputStreamWithPos(32);
+			ByteArrayInputStreamWithPos inputStreamWithPos = new ByteArrayInputStreamWithPos();
+			int keyGroupPrefixBytes = RocksDBKeySerializationUtils.computeRequiredBytesInKeyGroupPrefix(numKeyGroups);
+			TreeOrderedSetCache orderedSetCache = new TreeOrderedSetCache(32);
+			return new RocksDBCachingPriorityQueueSet<>(
+				keyGroupId,
+				keyGroupPrefixBytes,
+				rocksDBResource.getRocksDB(),
+				rocksDBResource.getDefaultColumnFamily(),
+				TestElementSerializer.INSTANCE,
+				outputStreamWithPos,
+				inputStreamWithPos,
+				rocksDBResource.getBatchWrapper(),
+				orderedSetCache);
 		};
 	}
 }
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBAsyncSnapshotTest.java b/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBAsyncSnapshotTest.java
index a8e5a36fbff..e34463888f1 100644
--- a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBAsyncSnapshotTest.java
+++ b/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBAsyncSnapshotTest.java
@@ -256,7 +256,7 @@ public void testCancelFullyAsyncCheckpoints() throws Exception {
 
 		File dbDir = temporaryFolder.newFolder();
 
-		final RocksDBStateBackend.PriorityQueueStateType timerServicePriorityQueueType = RocksDBStateBackend.PriorityQueueStateType.valueOf(RocksDBOptions.TIMER_SERVICE_IMPL.defaultValue());
+		final RocksDBStateBackend.PriorityQueueStateType timerServicePriorityQueueType = RocksDBStateBackend.PriorityQueueStateType.valueOf(RocksDBOptions.TIMER_SERVICE_FACTORY.defaultValue());
 
 		final int skipStreams;
 
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBOrderedSetStoreTest.java b/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBOrderedSetStoreTest.java
deleted file mode 100644
index 0b1d07bd082..00000000000
--- a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBOrderedSetStoreTest.java
+++ /dev/null
@@ -1,136 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License.  You may obtain a copy of the License at
- *
- *     http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package org.apache.flink.contrib.streaming.state;
-
-import org.apache.flink.api.common.typeutils.TypeSerializer;
-import org.apache.flink.api.common.typeutils.base.IntSerializer;
-import org.apache.flink.core.memory.ByteArrayOutputStreamWithPos;
-import org.apache.flink.core.memory.DataOutputViewStreamWrapper;
-import org.apache.flink.runtime.state.heap.CachingInternalPriorityQueueSet;
-import org.apache.flink.util.CloseableIterator;
-
-import org.junit.Assert;
-import org.junit.Rule;
-import org.junit.Test;
-
-import javax.annotation.Nonnegative;
-import javax.annotation.Nonnull;
-
-import java.util.NoSuchElementException;
-
-/**
- * Test for RocksDBOrderedStore.
- */
-public class RocksDBOrderedSetStoreTest {
-
-	@Rule
-	public final RocksDBResource rocksDBResource = new RocksDBResource();
-
-	@Test
-	public void testOrderedIterator() throws Exception {
-		CachingInternalPriorityQueueSet.OrderedSetStore<Integer> store = createRocksDBOrderedStore();
-
-		//test empty iterator
-		try (final CloseableIterator<Integer> emptyIterator = store.orderedIterator()) {
-			Assert.assertFalse(emptyIterator.hasNext());
-			try {
-				emptyIterator.next();
-				Assert.fail();
-			} catch (NoSuchElementException expected) {
-			}
-		}
-
-		store.add(43);
-		store.add(42);
-		store.add(41);
-		store.add(41);
-		store.remove(42);
-
-		// test in-order iteration
-		try (final CloseableIterator<Integer> iterator = store.orderedIterator()) {
-			Assert.assertTrue(iterator.hasNext());
-			Assert.assertEquals(Integer.valueOf(41), iterator.next());
-			Assert.assertTrue(iterator.hasNext());
-			Assert.assertEquals(Integer.valueOf(43), iterator.next());
-			Assert.assertFalse(iterator.hasNext());
-			try {
-				iterator.next();
-				Assert.fail();
-			} catch (NoSuchElementException expected) {
-			}
-		}
-	}
-
-	@Test
-	public void testAddRemoveSize() {
-
-		CachingInternalPriorityQueueSet.OrderedSetStore<Integer> store = createRocksDBOrderedStore();
-
-		// test empty size
-		Assert.assertEquals(0, store.size());
-
-		// test add uniques
-		store.remove(41);
-		Assert.assertEquals(0, store.size());
-		store.add(41);
-		Assert.assertEquals(1, store.size());
-		store.add(42);
-		Assert.assertEquals(2, store.size());
-		store.add(43);
-		Assert.assertEquals(3, store.size());
-		store.add(44);
-		Assert.assertEquals(4, store.size());
-		store.add(45);
-		Assert.assertEquals(5, store.size());
-
-		// test remove
-		store.remove(41);
-		Assert.assertEquals(4, store.size());
-		store.remove(41);
-		Assert.assertEquals(4, store.size());
-
-		// test set semantics by attempt to insert duplicate
-		store.add(42);
-		Assert.assertEquals(4, store.size());
-	}
-
-	public static <E> RocksDBOrderedSetStore<E> createRocksDBOrderedStore(
-		@Nonnull RocksDBResource rocksDBResource,
-		@Nonnull TypeSerializer<E> byteOrderSerializer,
-		@Nonnegative int keyGroupId,
-		@Nonnegative int totalKeyGroups) {
-
-		ByteArrayOutputStreamWithPos outputStreamWithPos = new ByteArrayOutputStreamWithPos(32);
-		DataOutputViewStreamWrapper outputView = new DataOutputViewStreamWrapper(outputStreamWithPos);
-		int keyGroupPrefixBytes = RocksDBKeySerializationUtils.computeRequiredBytesInKeyGroupPrefix(totalKeyGroups);
-		return new RocksDBOrderedSetStore<>(
-			keyGroupId,
-			keyGroupPrefixBytes,
-			rocksDBResource.getRocksDB(),
-			rocksDBResource.getDefaultColumnFamily(),
-			byteOrderSerializer,
-			outputStreamWithPos,
-			outputView,
-			rocksDBResource.getBatchWrapper());
-	}
-
-	protected RocksDBOrderedSetStore<Integer> createRocksDBOrderedStore() {
-		return createRocksDBOrderedStore(rocksDBResource, IntSerializer.INSTANCE, 0, 1);
-	}
-}
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackendConfigTest.java b/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackendConfigTest.java
index d6c3144d94b..b7d05b3455e 100644
--- a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackendConfigTest.java
+++ b/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackendConfigTest.java
@@ -35,11 +35,13 @@
 import org.apache.flink.runtime.state.StateBackend;
 import org.apache.flink.runtime.state.TestTaskStateManager;
 import org.apache.flink.runtime.state.filesystem.FsStateBackend;
+import org.apache.flink.runtime.state.heap.HeapPriorityQueueSetFactory;
 import org.apache.flink.runtime.state.memory.MemoryStateBackend;
 import org.apache.flink.runtime.taskmanager.TaskManagerRuntimeInfo;
 import org.apache.flink.runtime.util.TestingTaskManagerRuntimeInfo;
 import org.apache.flink.util.IOUtils;
 
+import org.junit.Assert;
 import org.junit.Rule;
 import org.junit.Test;
 import org.junit.rules.TemporaryFolder;
@@ -48,6 +50,7 @@
 import org.rocksdb.DBOptions;
 
 import java.io.File;
+import java.util.Collections;
 
 import static org.hamcrest.CoreMatchers.anyOf;
 import static org.hamcrest.MatcherAssert.assertThat;
@@ -125,6 +128,45 @@ public void testSetDbPath() throws Exception {
 		}
 	}
 
+	@Test
+	public void testConfigureTimerService() throws Exception {
+
+		final Environment env = getMockEnvironment(tempFolder.newFolder());
+
+		// Fix the option key string
+		Assert.assertEquals("state.backend.rocksdb.timer-service.factory", RocksDBOptions.TIMER_SERVICE_FACTORY.key());
+
+		// Fix the option value string and ensure all are covered
+		Assert.assertEquals(2, RocksDBStateBackend.PriorityQueueStateType.values().length);
+		Assert.assertEquals("ROCKSDB", RocksDBStateBackend.PriorityQueueStateType.ROCKSDB.toString());
+		Assert.assertEquals("HEAP", RocksDBStateBackend.PriorityQueueStateType.HEAP.toString());
+
+		// Fix the default
+		Assert.assertEquals(
+			RocksDBStateBackend.PriorityQueueStateType.HEAP.toString(),
+			RocksDBOptions.TIMER_SERVICE_FACTORY.defaultValue());
+
+		RocksDBStateBackend rocksDbBackend = new RocksDBStateBackend(tempFolder.newFolder().toURI().toString());
+
+		RocksDBKeyedStateBackend<Integer> keyedBackend = createKeyedStateBackend(rocksDbBackend, env);
+		keyedBackend.restore(Collections.emptyList());
+		Assert.assertEquals(HeapPriorityQueueSetFactory.class, keyedBackend.getPriorityQueueFactory().getClass());
+		keyedBackend.dispose();
+
+		Configuration conf = new Configuration();
+		conf.setString(
+			RocksDBOptions.TIMER_SERVICE_FACTORY,
+			RocksDBStateBackend.PriorityQueueStateType.ROCKSDB.toString());
+
+		rocksDbBackend = rocksDbBackend.configure(conf);
+		keyedBackend = createKeyedStateBackend(rocksDbBackend, env);
+		keyedBackend.restore(Collections.emptyList());
+		Assert.assertEquals(
+			RocksDBKeyedStateBackend.RocksDBPriorityQueueSetFactory.class,
+			keyedBackend.getPriorityQueueFactory().getClass());
+		keyedBackend.dispose();
+	}
+
 	@Test
 	public void testStoragePathWithFilePrefix() throws Exception {
 		final File folder = tempFolder.newFolder();
diff --git a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackendTest.java b/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackendTest.java
index 6b254ce50d3..0ea0d3fb653 100644
--- a/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackendTest.java
+++ b/flink-state-backends/flink-statebackend-rocksdb/src/test/java/org/apache/flink/contrib/streaming/state/RocksDBStateBackendTest.java
@@ -23,6 +23,7 @@
 import org.apache.flink.api.common.state.ValueState;
 import org.apache.flink.api.common.state.ValueStateDescriptor;
 import org.apache.flink.api.common.typeutils.base.IntSerializer;
+import org.apache.flink.configuration.Configuration;
 import org.apache.flink.core.testutils.OneShotLatch;
 import org.apache.flink.runtime.checkpoint.CheckpointOptions;
 import org.apache.flink.runtime.execution.Environment;
@@ -124,6 +125,11 @@ protected RocksDBStateBackend getStateBackend() throws IOException {
 		dbPath = tempFolder.newFolder().getAbsolutePath();
 		String checkpointPath = tempFolder.newFolder().toURI().toString();
 		RocksDBStateBackend backend = new RocksDBStateBackend(new FsStateBackend(checkpointPath), enableIncrementalCheckpointing);
+		Configuration configuration = new Configuration();
+		configuration.setString(
+			RocksDBOptions.TIMER_SERVICE_FACTORY,
+			RocksDBStateBackend.PriorityQueueStateType.ROCKSDB.toString());
+		backend = backend.configure(configuration);
 		backend.setDbStoragePath(dbPath);
 		return backend;
 	}
diff --git a/flink-streaming-java/pom.xml b/flink-streaming-java/pom.xml
index 02da827c190..e64ed48c712 100644
--- a/flink-streaming-java/pom.xml
+++ b/flink-streaming-java/pom.xml
@@ -42,6 +42,8 @@ under the License.
 			<groupId>org.apache.flink</groupId>
 			<artifactId>flink-core</artifactId>
 			<version>${project.version}</version>
+			<scope>test</scope>
+			<type>test-jar</type>
 		</dependency>
 
 		<dependency>
diff --git a/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimeServiceManager.java b/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimeServiceManager.java
index 29b89c28113..ff48c3fae03 100644
--- a/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimeServiceManager.java
+++ b/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimeServiceManager.java
@@ -37,7 +37,7 @@
 /**
  * An entity keeping all the time-related services available to all operators extending the
  * {@link AbstractStreamOperator}. Right now, this is only a
- * {@link HeapInternalTimerService timer services}.
+ * {@link InternalTimerServiceImpl timer services}.
  *
  * <b>NOTE:</b> These services are only available to keyed operators.
  *
@@ -46,31 +46,29 @@
 @Internal
 public class InternalTimeServiceManager<K> {
 
-	//TODO guard these constants with a test
-	private static final String TIMER_STATE_PREFIX = "_timer_state";
-	private static final String PROCESSING_TIMER_PREFIX = TIMER_STATE_PREFIX + "/processing_";
-	private static final String EVENT_TIMER_PREFIX = TIMER_STATE_PREFIX + "/event_";
+	@VisibleForTesting
+	static final String TIMER_STATE_PREFIX = "_timer_state";
+	@VisibleForTesting
+	static final String PROCESSING_TIMER_PREFIX = TIMER_STATE_PREFIX + "/processing_";
+	@VisibleForTesting
+	static final String EVENT_TIMER_PREFIX = TIMER_STATE_PREFIX + "/event_";
 
-	private final int totalKeyGroups;
 	private final KeyGroupRange localKeyGroupRange;
 	private final KeyContext keyContext;
 
 	private final PriorityQueueSetFactory priorityQueueSetFactory;
 	private final ProcessingTimeService processingTimeService;
 
-	private final Map<String, HeapInternalTimerService<K, ?>> timerServices;
+	private final Map<String, InternalTimerServiceImpl<K, ?>> timerServices;
 
 	private final boolean useLegacySynchronousSnapshots;
 
 	InternalTimeServiceManager(
-		int totalKeyGroups,
 		KeyGroupRange localKeyGroupRange,
 		KeyContext keyContext,
 		PriorityQueueSetFactory priorityQueueSetFactory,
 		ProcessingTimeService processingTimeService, boolean useLegacySynchronousSnapshots) {
 
-		Preconditions.checkArgument(totalKeyGroups > 0);
-		this.totalKeyGroups = totalKeyGroups;
 		this.localKeyGroupRange = Preconditions.checkNotNull(localKeyGroupRange);
 		this.priorityQueueSetFactory = Preconditions.checkNotNull(priorityQueueSetFactory);
 		this.keyContext = Preconditions.checkNotNull(keyContext);
@@ -86,7 +84,7 @@
 		TimerSerializer<K, N> timerSerializer,
 		Triggerable<K, N> triggerable) {
 
-		HeapInternalTimerService<K, N> timerService = registerOrGetTimerService(name, timerSerializer);
+		InternalTimerServiceImpl<K, N> timerService = registerOrGetTimerService(name, timerSerializer);
 
 		timerService.startTimerService(
 			timerSerializer.getKeySerializer(),
@@ -97,11 +95,11 @@
 	}
 
 	@SuppressWarnings("unchecked")
-	<N> HeapInternalTimerService<K, N> registerOrGetTimerService(String name, TimerSerializer<K, N> timerSerializer) {
-		HeapInternalTimerService<K, N> timerService = (HeapInternalTimerService<K, N>) timerServices.get(name);
+	<N> InternalTimerServiceImpl<K, N> registerOrGetTimerService(String name, TimerSerializer<K, N> timerSerializer) {
+		InternalTimerServiceImpl<K, N> timerService = (InternalTimerServiceImpl<K, N>) timerServices.get(name);
 		if (timerService == null) {
 
-			timerService = new HeapInternalTimerService<>(
+			timerService = new InternalTimerServiceImpl<>(
 				localKeyGroupRange,
 				keyContext,
 				processingTimeService,
@@ -113,7 +111,7 @@
 		return timerService;
 	}
 
-	Map<String, HeapInternalTimerService<K, ?>> getRegisteredTimerServices() {
+	Map<String, InternalTimerServiceImpl<K, ?>> getRegisteredTimerServices() {
 		return Collections.unmodifiableMap(timerServices);
 	}
 
@@ -126,7 +124,7 @@
 	}
 
 	public void advanceWatermark(Watermark watermark) throws Exception {
-		for (HeapInternalTimerService<?, ?> service : timerServices.values()) {
+		for (InternalTimerServiceImpl<?, ?> service : timerServices.values()) {
 			service.advanceWatermark(watermark.getTimestamp());
 		}
 	}
@@ -155,16 +153,12 @@ public void restoreStateForKeyGroup(
 		serializationProxy.read(stream);
 	}
 
-	public boolean isUseLegacySynchronousSnapshots() {
-		return useLegacySynchronousSnapshots;
-	}
-
 	////////////////////			Methods used ONLY IN TESTS				////////////////////
 
 	@VisibleForTesting
 	public int numProcessingTimeTimers() {
 		int count = 0;
-		for (HeapInternalTimerService<?, ?> timerService : timerServices.values()) {
+		for (InternalTimerServiceImpl<?, ?> timerService : timerServices.values()) {
 			count += timerService.numProcessingTimeTimers();
 		}
 		return count;
@@ -173,7 +167,7 @@ public int numProcessingTimeTimers() {
 	@VisibleForTesting
 	public int numEventTimeTimers() {
 		int count = 0;
-		for (HeapInternalTimerService<?, ?> timerService : timerServices.values()) {
+		for (InternalTimerServiceImpl<?, ?> timerService : timerServices.values()) {
 			count += timerService.numEventTimeTimers();
 		}
 		return count;
diff --git a/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/HeapInternalTimerService.java b/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimerServiceImpl.java
similarity index 92%
rename from flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/HeapInternalTimerService.java
rename to flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimerServiceImpl.java
index 6c1b1886b94..3bded50378b 100644
--- a/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/HeapInternalTimerService.java
+++ b/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimerServiceImpl.java
@@ -43,7 +43,7 @@
 /**
  * {@link InternalTimerService} that stores timers on the Java heap.
  */
-public class HeapInternalTimerService<K, N> implements InternalTimerService<N>, ProcessingTimeCallback {
+public class InternalTimerServiceImpl<K, N> implements InternalTimerService<N>, ProcessingTimeCallback {
 
 	private final ProcessingTimeService processingTimeService;
 
@@ -95,7 +95,7 @@
 	/** The restored timers snapshot, if any. */
 	private InternalTimersSnapshot<K, N> restoredTimersSnapshot;
 
-	HeapInternalTimerService(
+	InternalTimerServiceImpl(
 		KeyGroupRange localKeyGroupRange,
 		KeyContext keyContext,
 		ProcessingTimeService processingTimeService,
@@ -117,7 +117,7 @@
 	}
 
 	/**
-	 * Starts the local {@link HeapInternalTimerService} by:
+	 * Starts the local {@link InternalTimerServiceImpl} by:
 	 * <ol>
 	 *     <li>Setting the {@code keySerialized} and {@code namespaceSerializer} for the timers it will contain.</li>
 	 *     <li>Setting the {@code triggerTarget} which contains the action to be performed when a timer fires.</li>
@@ -227,37 +227,29 @@ public void onProcessingTime(long time) throws Exception {
 		// inside the callback.
 		nextTimer = null;
 
-		processingTimeTimersQueue.bulkPoll(
-			(timer) -> (timer.getTimestamp() <= time),
-			(timer) -> {
-				keyContext.setCurrentKey(timer.getKey());
-				try {
-					triggerTarget.onProcessingTime(timer);
-				} catch (Exception e) {
-					throw new FlinkRuntimeException("Problem in trigger target.", e);
-				}
-			});
+		InternalTimer<K, N> timer;
 
-		if (nextTimer == null) {
-			final TimerHeapInternalTimer<K, N> timer = processingTimeTimersQueue.peek();
-			if (timer != null) {
-				nextTimer = processingTimeService.registerTimer(timer.getTimestamp(), this);
-			}
+		while ((timer = processingTimeTimersQueue.peek()) != null && timer.getTimestamp() <= time) {
+			processingTimeTimersQueue.poll();
+			keyContext.setCurrentKey(timer.getKey());
+			triggerTarget.onProcessingTime(timer);
+		}
+
+		if (timer != null && nextTimer == null) {
+			nextTimer = processingTimeService.registerTimer(timer.getTimestamp(), this);
 		}
 	}
 
 	public void advanceWatermark(long time) throws Exception {
 		currentWatermark = time;
-		eventTimeTimersQueue.bulkPoll(
-			(timer) -> (timer.getTimestamp() <= time),
-			(timer) -> {
-				keyContext.setCurrentKey(timer.getKey());
-				try {
-					triggerTarget.onEventTime(timer);
-				} catch (Exception e) {
-					throw new FlinkRuntimeException("Problem in trigger target.", e);
-				}
-			});
+
+		InternalTimer<K, N> timer;
+
+		while ((timer = eventTimeTimersQueue.peek()) != null && timer.getTimestamp() <= time) {
+			eventTimeTimersQueue.poll();
+			keyContext.setCurrentKey(timer.getKey());
+			triggerTarget.onEventTime(timer);
+		}
 	}
 
 	/**
diff --git a/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimerServiceSerializationProxy.java b/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimerServiceSerializationProxy.java
index ce490b5dfc0..dea17f98665 100644
--- a/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimerServiceSerializationProxy.java
+++ b/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/InternalTimerServiceSerializationProxy.java
@@ -77,13 +77,13 @@ public int getVersion() {
 	@Override
 	public void write(DataOutputView out) throws IOException {
 		super.write(out);
-		final Map<String, HeapInternalTimerService<K, ?>> registeredTimerServices =
+		final Map<String, InternalTimerServiceImpl<K, ?>> registeredTimerServices =
 			timerServicesManager.getRegisteredTimerServices();
 
 		out.writeInt(registeredTimerServices.size());
-		for (Map.Entry<String, HeapInternalTimerService<K, ?>> entry : registeredTimerServices.entrySet()) {
+		for (Map.Entry<String, InternalTimerServiceImpl<K, ?>> entry : registeredTimerServices.entrySet()) {
 			String serviceName = entry.getKey();
-			HeapInternalTimerService<K, ?> timerService = entry.getValue();
+			InternalTimerServiceImpl<K, ?> timerService = entry.getValue();
 
 			out.writeUTF(serviceName);
 			InternalTimersSnapshotReaderWriters
@@ -104,7 +104,7 @@ protected void read(DataInputView in, boolean wasVersioned) throws IOException {
 				.getReaderForVersion(readerVersion, userCodeClassLoader)
 				.readTimersSnapshot(in);
 
-			HeapInternalTimerService<K, ?> timerService = registerOrGetTimerService(
+			InternalTimerServiceImpl<K, ?> timerService = registerOrGetTimerService(
 				serviceName,
 				restoredTimersSnapshot);
 
@@ -113,7 +113,7 @@ protected void read(DataInputView in, boolean wasVersioned) throws IOException {
 	}
 
 	@SuppressWarnings("unchecked")
-	private <N> HeapInternalTimerService<K, N> registerOrGetTimerService(
+	private <N> InternalTimerServiceImpl<K, N> registerOrGetTimerService(
 		String serviceName, InternalTimersSnapshot<?, ?> restoredTimersSnapshot) {
 		final TypeSerializer<K> keySerializer = (TypeSerializer<K>) restoredTimersSnapshot.getKeySerializer();
 		final TypeSerializer<N> namespaceSerializer = (TypeSerializer<N>) restoredTimersSnapshot.getNamespaceSerializer();
diff --git a/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/StreamTaskStateInitializerImpl.java b/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/StreamTaskStateInitializerImpl.java
index a6bee4c8070..64af9939834 100644
--- a/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/StreamTaskStateInitializerImpl.java
+++ b/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/StreamTaskStateInitializerImpl.java
@@ -205,7 +205,6 @@ public StreamOperatorStateContext streamOperatorStateContext(
 		final KeyGroupRange keyGroupRange = keyedStatedBackend.getKeyGroupRange();
 
 		final InternalTimeServiceManager<K> timeServiceManager = new InternalTimeServiceManager<>(
-			keyedStatedBackend.getNumberOfKeyGroups(),
 			keyGroupRange,
 			keyContext,
 			keyedStatedBackend,
diff --git a/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/TimerSerializer.java b/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/TimerSerializer.java
index 73f42ef308b..a83cc3a8797 100644
--- a/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/TimerSerializer.java
+++ b/flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/TimerSerializer.java
@@ -19,9 +19,12 @@
 package org.apache.flink.streaming.api.operators;
 
 import org.apache.flink.api.common.typeutils.CompatibilityResult;
+import org.apache.flink.api.common.typeutils.CompatibilityUtil;
 import org.apache.flink.api.common.typeutils.CompositeTypeSerializerConfigSnapshot;
 import org.apache.flink.api.common.typeutils.TypeSerializer;
 import org.apache.flink.api.common.typeutils.TypeSerializerConfigSnapshot;
+import org.apache.flink.api.common.typeutils.UnloadableDummyTypeSerializer;
+import org.apache.flink.api.java.tuple.Tuple2;
 import org.apache.flink.core.memory.DataInputView;
 import org.apache.flink.core.memory.DataOutputView;
 import org.apache.flink.util.MathUtils;
@@ -29,6 +32,7 @@
 import javax.annotation.Nonnull;
 
 import java.io.IOException;
+import java.util.List;
 import java.util.Objects;
 
 /**
@@ -42,6 +46,9 @@
 
 	private static final long serialVersionUID = 1L;
 
+	private static final int KEY_SERIALIZER_SNAPSHOT_INDEX = 0;
+	private static final int NAMESPACE_SERIALIZER_SNAPSHOT_INDEX = 1;
+
 	/** Serializer for the key. */
 	@Nonnull
 	private final TypeSerializer<K> keySerializer;
@@ -208,8 +215,35 @@ public TypeSerializerConfigSnapshot snapshotConfiguration() {
 	@Override
 	public CompatibilityResult<TimerHeapInternalTimer<K, N>> ensureCompatibility(
 		TypeSerializerConfigSnapshot configSnapshot) {
-		//TODO this is just a mock (assuming no serializer updates) for now and needs a proper implementation! change this before release.
-		return CompatibilityResult.compatible();
+
+		if (configSnapshot instanceof TimerSerializerConfigSnapshot) {
+			List<Tuple2<TypeSerializer<?>, TypeSerializerConfigSnapshot>> previousSerializersAndConfigs =
+				((TimerSerializerConfigSnapshot) configSnapshot).getNestedSerializersAndConfigs();
+
+			if (previousSerializersAndConfigs.size() == 2) {
+				Tuple2<TypeSerializer<?>, TypeSerializerConfigSnapshot> keySerializerAndSnapshot =
+					previousSerializersAndConfigs.get(KEY_SERIALIZER_SNAPSHOT_INDEX);
+				Tuple2<TypeSerializer<?>, TypeSerializerConfigSnapshot> namespaceSerializerAndSnapshot =
+					previousSerializersAndConfigs.get(NAMESPACE_SERIALIZER_SNAPSHOT_INDEX);
+				CompatibilityResult<K> keyCompatibilityResult = CompatibilityUtil.resolveCompatibilityResult(
+					keySerializerAndSnapshot.f0,
+					UnloadableDummyTypeSerializer.class,
+					keySerializerAndSnapshot.f1,
+					keySerializer);
+
+				CompatibilityResult<N> namespaceCompatibilityResult = CompatibilityUtil.resolveCompatibilityResult(
+					namespaceSerializerAndSnapshot.f0,
+					UnloadableDummyTypeSerializer.class,
+					namespaceSerializerAndSnapshot.f1,
+					namespaceSerializer);
+
+				if (!keyCompatibilityResult.isRequiresMigration()
+					&& !namespaceCompatibilityResult.isRequiresMigration()) {
+					return CompatibilityResult.compatible();
+				}
+			}
+		}
+		return CompatibilityResult.requiresMigration();
 	}
 
 	@Nonnull
@@ -230,16 +264,29 @@ public TypeSerializerConfigSnapshot snapshotConfiguration() {
 	 */
 	public static class TimerSerializerConfigSnapshot<K, N> extends CompositeTypeSerializerConfigSnapshot {
 
+		private static final int VERSION = 1;
+
 		public TimerSerializerConfigSnapshot() {
 		}
 
-		public TimerSerializerConfigSnapshot(TypeSerializer<K> keySerializer, TypeSerializer<N> namespaceSerializer) {
-			super(keySerializer, namespaceSerializer);
+		public TimerSerializerConfigSnapshot(
+			@Nonnull TypeSerializer<K> keySerializer,
+			@Nonnull TypeSerializer<N> namespaceSerializer) {
+			super(init(keySerializer, namespaceSerializer));
+		}
+
+		private static TypeSerializer<?>[] init(
+			@Nonnull TypeSerializer<?> keySerializer,
+			@Nonnull TypeSerializer<?> namespaceSerializer) {
+			TypeSerializer<?>[] timerSerializers = new TypeSerializer[2];
+			timerSerializers[KEY_SERIALIZER_SNAPSHOT_INDEX] = keySerializer;
+			timerSerializers[NAMESPACE_SERIALIZER_SNAPSHOT_INDEX] = namespaceSerializer;
+			return timerSerializers;
 		}
 
 		@Override
 		public int getVersion() {
-			return 0;
+			return VERSION;
 		}
 	}
 }
diff --git a/flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/InternalTimeServiceManagerTest.java b/flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/InternalTimeServiceManagerTest.java
new file mode 100644
index 00000000000..905e8d75208
--- /dev/null
+++ b/flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/InternalTimeServiceManagerTest.java
@@ -0,0 +1,41 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.streaming.api.operators;
+
+import org.apache.flink.util.TestLogger;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * Tests for {@link InternalTimeServiceManager}.
+ */
+public class InternalTimeServiceManagerTest extends TestLogger {
+
+	/**
+	 * This test fixes some constants, because changing them can harm backwards compatibility.
+	 */
+	@Test
+	public void fixConstants() {
+		String expectedTimerStatePrefix = "_timer_state";
+		Assert.assertEquals(expectedTimerStatePrefix, InternalTimeServiceManager.TIMER_STATE_PREFIX);
+		Assert.assertEquals(expectedTimerStatePrefix + "/processing_", InternalTimeServiceManager.PROCESSING_TIMER_PREFIX);
+		Assert.assertEquals(expectedTimerStatePrefix + "/event_", InternalTimeServiceManager.EVENT_TIMER_PREFIX);
+	}
+}
diff --git a/flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/HeapInternalTimerServiceTest.java b/flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/InternalTimerServiceImplTest.java
similarity index 95%
rename from flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/HeapInternalTimerServiceTest.java
rename to flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/InternalTimerServiceImplTest.java
index 957a53516ba..f2da6da3b05 100644
--- a/flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/HeapInternalTimerServiceTest.java
+++ b/flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/InternalTimerServiceImplTest.java
@@ -61,10 +61,10 @@
 import static org.mockito.Mockito.verify;
 
 /**
- * Tests for {@link HeapInternalTimerService}.
+ * Tests for {@link InternalTimerServiceImpl}.
  */
 @RunWith(Parameterized.class)
-public class HeapInternalTimerServiceTest {
+public class InternalTimerServiceImplTest {
 
 	private final int maxParallelism;
 	private final KeyGroupRange testKeyGroupRange;
@@ -73,7 +73,7 @@
 		return any();
 	}
 
-	public HeapInternalTimerServiceTest(int startKeyGroup, int endKeyGroup, int maxParallelism) {
+	public InternalTimerServiceImplTest(int startKeyGroup, int endKeyGroup, int maxParallelism) {
 		this.testKeyGroupRange = new KeyGroupRange(startKeyGroup, endKeyGroup);
 		this.maxParallelism = maxParallelism;
 	}
@@ -89,7 +89,7 @@ public void testKeyGroupStartIndexSetting() {
 
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
 
-		HeapInternalTimerService<Integer, String> service = createInternalTimerService(
+		InternalTimerServiceImpl<Integer, String> service = createInternalTimerService(
 			testKeyGroupList,
 			keyContext,
 			processingTimeService,
@@ -117,7 +117,7 @@ public void testTimerAssignmentToKeyGroups() {
 		final PriorityQueueSetFactory priorityQueueSetFactory =
 			createQueueFactory(keyGroupRange, totalNoOfKeyGroups);
 
-		HeapInternalTimerService<Integer, String> timerService = createInternalTimerService(
+		InternalTimerServiceImpl<Integer, String> timerService = createInternalTimerService(
 			keyGroupRange,
 			keyContext,
 			new TestProcessingTimeService(),
@@ -182,7 +182,7 @@ public void testOnlySetsOnePhysicalProcessingTimeTimer() throws Exception {
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
 		PriorityQueueSetFactory priorityQueueSetFactory =
 			new HeapPriorityQueueSetFactory(testKeyGroupRange, maxParallelism, 128);
-		HeapInternalTimerService<Integer, String> timerService =
+		InternalTimerServiceImpl<Integer, String> timerService =
 				createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, priorityQueueSetFactory);
 
 		int key = getKeyInKeyGroupRange(testKeyGroupRange, maxParallelism);
@@ -244,7 +244,7 @@ public void testRegisterEarlierProcessingTimerMovesPhysicalProcessingTimer() thr
 
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
 
-		HeapInternalTimerService<Integer, String> timerService =
+		InternalTimerServiceImpl<Integer, String> timerService =
 				createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, createQueueFactory());
 
 		int key = getKeyInKeyGroupRange(testKeyGroupRange, maxParallelism);
@@ -277,7 +277,7 @@ public void testRegisteringProcessingTimeTimerInOnProcessingTimeDoesNotLeakPhysi
 
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
 
-		final HeapInternalTimerService<Integer, String> timerService =
+		final InternalTimerServiceImpl<Integer, String> timerService =
 				createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, createQueueFactory());
 
 		int key = getKeyInKeyGroupRange(testKeyGroupRange, maxParallelism);
@@ -328,7 +328,7 @@ public void testCurrentProcessingTime() throws Exception {
 
 		TestKeyContext keyContext = new TestKeyContext();
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
-		HeapInternalTimerService<Integer, String> timerService =
+		InternalTimerServiceImpl<Integer, String> timerService =
 				createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, createQueueFactory());
 
 		processingTimeService.setCurrentTime(17L);
@@ -346,7 +346,7 @@ public void testCurrentEventTime() throws Exception {
 
 		TestKeyContext keyContext = new TestKeyContext();
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
-		HeapInternalTimerService<Integer, String> timerService =
+		InternalTimerServiceImpl<Integer, String> timerService =
 				createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, createQueueFactory());
 
 		timerService.advanceWatermark(17);
@@ -366,7 +366,7 @@ public void testSetAndFireEventTimeTimers() throws Exception {
 
 		TestKeyContext keyContext = new TestKeyContext();
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
-		HeapInternalTimerService<Integer, String> timerService =
+		InternalTimerServiceImpl<Integer, String> timerService =
 				createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, createQueueFactory());
 
 		// get two different keys
@@ -411,7 +411,7 @@ public void testSetAndFireProcessingTimeTimers() throws Exception {
 
 		TestKeyContext keyContext = new TestKeyContext();
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
-		HeapInternalTimerService<Integer, String> timerService =
+		InternalTimerServiceImpl<Integer, String> timerService =
 				createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, createQueueFactory());
 
 		// get two different keys
@@ -458,7 +458,7 @@ public void testDeleteEventTimeTimers() throws Exception {
 
 		TestKeyContext keyContext = new TestKeyContext();
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
-		HeapInternalTimerService<Integer, String> timerService =
+		InternalTimerServiceImpl<Integer, String> timerService =
 				createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, createQueueFactory());
 
 		// get two different keys
@@ -515,7 +515,7 @@ public void testDeleteProcessingTimeTimers() throws Exception {
 
 		TestKeyContext keyContext = new TestKeyContext();
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
-		HeapInternalTimerService<Integer, String> timerService =
+		InternalTimerServiceImpl<Integer, String> timerService =
 				createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, createQueueFactory());
 
 		// get two different keys
@@ -590,7 +590,7 @@ private void testSnapshotAndRestore(int snapshotVersion) throws Exception {
 
 		TestKeyContext keyContext = new TestKeyContext();
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
-		HeapInternalTimerService<Integer, String> timerService =
+		InternalTimerServiceImpl<Integer, String> timerService =
 			createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, createQueueFactory());
 
 		// get two different keys
@@ -665,7 +665,7 @@ private void testSnapshotAndRebalancingRestore(int snapshotVersion) throws Excep
 		TestKeyContext keyContext = new TestKeyContext();
 		TestProcessingTimeService processingTimeService = new TestProcessingTimeService();
 		final PriorityQueueSetFactory queueFactory = createQueueFactory();
-		HeapInternalTimerService<Integer, String> timerService =
+		InternalTimerServiceImpl<Integer, String> timerService =
 			createAndStartInternalTimerService(mockTriggerable, keyContext, processingTimeService, testKeyGroupRange, queueFactory);
 
 		int midpoint = testKeyGroupRange.getStartKeyGroup() +
@@ -730,7 +730,7 @@ private void testSnapshotAndRebalancingRestore(int snapshotVersion) throws Excep
 		TestProcessingTimeService processingTimeService1 = new TestProcessingTimeService();
 		TestProcessingTimeService processingTimeService2 = new TestProcessingTimeService();
 
-		HeapInternalTimerService<Integer, String> timerService1 = restoreTimerService(
+		InternalTimerServiceImpl<Integer, String> timerService1 = restoreTimerService(
 			snapshot1,
 			snapshotVersion,
 			mockTriggerable1,
@@ -739,7 +739,7 @@ private void testSnapshotAndRebalancingRestore(int snapshotVersion) throws Excep
 			subKeyGroupRange1,
 			queueFactory);
 
-		HeapInternalTimerService<Integer, String> timerService2 = restoreTimerService(
+		InternalTimerServiceImpl<Integer, String> timerService2 = restoreTimerService(
 			snapshot2,
 			snapshotVersion,
 			mockTriggerable2,
@@ -806,13 +806,13 @@ private static int getKeyInKeyGroupRange(KeyGroupRange range, int maxParallelism
 		return result;
 	}
 
-	private static HeapInternalTimerService<Integer, String> createAndStartInternalTimerService(
+	private static InternalTimerServiceImpl<Integer, String> createAndStartInternalTimerService(
 			Triggerable<Integer, String> triggerable,
 			KeyContext keyContext,
 			ProcessingTimeService processingTimeService,
 			KeyGroupRange keyGroupList,
 			PriorityQueueSetFactory priorityQueueSetFactory) {
-		HeapInternalTimerService<Integer, String> service = createInternalTimerService(
+		InternalTimerServiceImpl<Integer, String> service = createInternalTimerService(
 			keyGroupList,
 			keyContext,
 			processingTimeService,
@@ -824,7 +824,7 @@ private static int getKeyInKeyGroupRange(KeyGroupRange range, int maxParallelism
 		return service;
 	}
 
-	private static HeapInternalTimerService<Integer, String> restoreTimerService(
+	private static InternalTimerServiceImpl<Integer, String> restoreTimerService(
 			Map<Integer, byte[]> state,
 			int snapshotVersion,
 			Triggerable<Integer, String> triggerable,
@@ -834,7 +834,7 @@ private static int getKeyInKeyGroupRange(KeyGroupRange range, int maxParallelism
 			PriorityQueueSetFactory priorityQueueSetFactory) throws Exception {
 
 		// create an empty service
-		HeapInternalTimerService<Integer, String> service = createInternalTimerService(
+		InternalTimerServiceImpl<Integer, String> service = createInternalTimerService(
 			keyGroupsList,
 			keyContext,
 			processingTimeService,
@@ -848,7 +848,7 @@ private static int getKeyInKeyGroupRange(KeyGroupRange range, int maxParallelism
 				try (ByteArrayInputStream inputStream = new ByteArrayInputStream(state.get(keyGroupIndex))) {
 					InternalTimersSnapshot<?, ?> restoredTimersSnapshot =
 						InternalTimersSnapshotReaderWriters
-							.getReaderForVersion(snapshotVersion, HeapInternalTimerServiceTest.class.getClassLoader())
+							.getReaderForVersion(snapshotVersion, InternalTimerServiceImplTest.class.getClassLoader())
 							.readTimersSnapshot(new DataInputViewStreamWrapper(inputStream));
 
 					service.restoreTimersForKeyGroup(restoredTimersSnapshot, keyGroupIndex);
@@ -886,7 +886,7 @@ protected PriorityQueueSetFactory createQueueFactory(KeyGroupRange keyGroupRange
 		});
 	}
 
-	private static <K, N> HeapInternalTimerService<K, N> createInternalTimerService(
+	private static <K, N> InternalTimerServiceImpl<K, N> createInternalTimerService(
 		KeyGroupRange keyGroupsList,
 		KeyContext keyContext,
 		ProcessingTimeService processingTimeService,
@@ -896,7 +896,7 @@ protected PriorityQueueSetFactory createQueueFactory(KeyGroupRange keyGroupRange
 
 		TimerSerializer<K, N> timerSerializer = new TimerSerializer<>(keySerializer, namespaceSerializer);
 
-		return new HeapInternalTimerService<>(
+		return new InternalTimerServiceImpl<>(
 			keyGroupsList,
 			keyContext,
 			processingTimeService,
diff --git a/flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/TimerSerializerTest.java b/flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/TimerSerializerTest.java
new file mode 100644
index 00000000000..9fe4ffcce95
--- /dev/null
+++ b/flink-streaming-java/src/test/java/org/apache/flink/streaming/api/operators/TimerSerializerTest.java
@@ -0,0 +1,62 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.flink.streaming.api.operators;
+
+import org.apache.flink.api.common.typeutils.SerializerTestBase;
+import org.apache.flink.api.common.typeutils.TypeSerializer;
+import org.apache.flink.api.common.typeutils.base.LongSerializer;
+import org.apache.flink.streaming.api.windowing.windows.TimeWindow;
+
+/**
+ * Test for {@link TimerSerializer}.
+ */
+public class TimerSerializerTest extends SerializerTestBase<TimerHeapInternalTimer<Long, TimeWindow>> {
+
+	private static final TypeSerializer<Long> KEY_SERIALIZER = LongSerializer.INSTANCE;
+	private static final TypeSerializer<TimeWindow> NAMESPACE_SERIALIZER = new TimeWindow.Serializer();
+
+	@Override
+	protected TypeSerializer<TimerHeapInternalTimer<Long, TimeWindow>> createSerializer() {
+		return new TimerSerializer<>(KEY_SERIALIZER, NAMESPACE_SERIALIZER);
+	}
+
+	@Override
+	protected int getLength() {
+		return Long.BYTES + KEY_SERIALIZER.getLength() + NAMESPACE_SERIALIZER.getLength();
+	}
+
+	@SuppressWarnings("unchecked")
+	@Override
+	protected Class<TimerHeapInternalTimer<Long, TimeWindow>> getTypeClass() {
+		return (Class<TimerHeapInternalTimer<Long, TimeWindow>>) (Class<?>) TimerHeapInternalTimer.class;
+	}
+
+	@SuppressWarnings("unchecked")
+	@Override
+	protected TimerHeapInternalTimer<Long, TimeWindow>[] getTestData() {
+		return (TimerHeapInternalTimer<Long, TimeWindow>[]) new TimerHeapInternalTimer[]{
+			new TimerHeapInternalTimer<>(42L, 4711L, new TimeWindow(1000L, 2000L)),
+			new TimerHeapInternalTimer<>(0L, 0L, new TimeWindow(0L, 0L)),
+			new TimerHeapInternalTimer<>(1L, -1L, new TimeWindow(1L, -1L)),
+			new TimerHeapInternalTimer<>(-1L, 1L, new TimeWindow(-1L, 1L)),
+			new TimerHeapInternalTimer<>(Long.MAX_VALUE, Long.MIN_VALUE, new TimeWindow(Long.MAX_VALUE, Long.MIN_VALUE)),
+			new TimerHeapInternalTimer<>(Long.MIN_VALUE, Long.MAX_VALUE, new TimeWindow(Long.MIN_VALUE, Long.MAX_VALUE))
+		};
+	}
+}
diff --git a/flink-streaming-java/src/test/java/org/apache/flink/streaming/runtime/operators/windowing/TriggerTestHarness.java b/flink-streaming-java/src/test/java/org/apache/flink/streaming/runtime/operators/windowing/TriggerTestHarness.java
index 15369567362..bc5bb1bdef0 100644
--- a/flink-streaming-java/src/test/java/org/apache/flink/streaming/runtime/operators/windowing/TriggerTestHarness.java
+++ b/flink-streaming-java/src/test/java/org/apache/flink/streaming/runtime/operators/windowing/TriggerTestHarness.java
@@ -115,11 +115,11 @@ public int numEventTimeTimers(W window) {
 	}
 
 	public int numStateEntries() {
-		return stateBackend.numStateEntries();
+		return stateBackend.numKeyValueStateEntries();
 	}
 
 	public int numStateEntries(W window) {
-		return stateBackend.numStateEntries(window);
+		return stateBackend.numKeyValueStateEntries(window);
 	}
 
 	/**
diff --git a/flink-streaming-java/src/test/java/org/apache/flink/streaming/util/KeyedOneInputStreamOperatorTestHarness.java b/flink-streaming-java/src/test/java/org/apache/flink/streaming/util/KeyedOneInputStreamOperatorTestHarness.java
index 2035c4659c7..caf846fdf12 100644
--- a/flink-streaming-java/src/test/java/org/apache/flink/streaming/util/KeyedOneInputStreamOperatorTestHarness.java
+++ b/flink-streaming-java/src/test/java/org/apache/flink/streaming/util/KeyedOneInputStreamOperatorTestHarness.java
@@ -72,7 +72,7 @@ public int numKeyedStateEntries() {
 		AbstractStreamOperator<?> abstractStreamOperator = (AbstractStreamOperator<?>) operator;
 		KeyedStateBackend<Object> keyedStateBackend = abstractStreamOperator.getKeyedStateBackend();
 		if (keyedStateBackend instanceof HeapKeyedStateBackend) {
-			return ((HeapKeyedStateBackend) keyedStateBackend).numStateEntries();
+			return ((HeapKeyedStateBackend) keyedStateBackend).numKeyValueStateEntries();
 		} else {
 			throw new UnsupportedOperationException();
 		}
@@ -82,7 +82,7 @@ public int numKeyedStateEntries() {
 		AbstractStreamOperator<?> abstractStreamOperator = (AbstractStreamOperator<?>) operator;
 		KeyedStateBackend<Object> keyedStateBackend = abstractStreamOperator.getKeyedStateBackend();
 		if (keyedStateBackend instanceof HeapKeyedStateBackend) {
-			return ((HeapKeyedStateBackend) keyedStateBackend).numStateEntries(namespace);
+			return ((HeapKeyedStateBackend) keyedStateBackend).numKeyValueStateEntries(namespace);
 		} else {
 			throw new UnsupportedOperationException();
 		}
diff --git a/flink-streaming-java/src/test/java/org/apache/flink/streaming/util/KeyedTwoInputStreamOperatorTestHarness.java b/flink-streaming-java/src/test/java/org/apache/flink/streaming/util/KeyedTwoInputStreamOperatorTestHarness.java
index 607eee045bd..c00e59a3b33 100644
--- a/flink-streaming-java/src/test/java/org/apache/flink/streaming/util/KeyedTwoInputStreamOperatorTestHarness.java
+++ b/flink-streaming-java/src/test/java/org/apache/flink/streaming/util/KeyedTwoInputStreamOperatorTestHarness.java
@@ -62,7 +62,7 @@ public int numKeyedStateEntries() {
 		AbstractStreamOperator<?> abstractStreamOperator = (AbstractStreamOperator<?>) operator;
 		KeyedStateBackend<Object> keyedStateBackend = abstractStreamOperator.getKeyedStateBackend();
 		if (keyedStateBackend instanceof HeapKeyedStateBackend) {
-			return ((HeapKeyedStateBackend) keyedStateBackend).numStateEntries();
+			return ((HeapKeyedStateBackend) keyedStateBackend).numKeyValueStateEntries();
 		} else {
 			throw new UnsupportedOperationException();
 		}
diff --git a/flink-tests/src/test/java/org/apache/flink/test/checkpointing/EventTimeWindowCheckpointingITCase.java b/flink-tests/src/test/java/org/apache/flink/test/checkpointing/EventTimeWindowCheckpointingITCase.java
index e9a2e45d260..4fa90206a75 100644
--- a/flink-tests/src/test/java/org/apache/flink/test/checkpointing/EventTimeWindowCheckpointingITCase.java
+++ b/flink-tests/src/test/java/org/apache/flink/test/checkpointing/EventTimeWindowCheckpointingITCase.java
@@ -29,6 +29,7 @@
 import org.apache.flink.configuration.Configuration;
 import org.apache.flink.configuration.HighAvailabilityOptions;
 import org.apache.flink.configuration.TaskManagerOptions;
+import org.apache.flink.contrib.streaming.state.RocksDBOptions;
 import org.apache.flink.contrib.streaming.state.RocksDBStateBackend;
 import org.apache.flink.core.fs.Path;
 import org.apache.flink.runtime.state.AbstractStateBackend;
@@ -167,26 +168,18 @@ private Configuration getConfiguration() throws Exception {
 				break;
 			}
 			case ROCKSDB_FULLY_ASYNC: {
-				String rocksDb = tempFolder.newFolder().getAbsolutePath();
-				String backups = tempFolder.newFolder().getAbsolutePath();
-				RocksDBStateBackend rdb = new RocksDBStateBackend(new FsStateBackend("file://" + backups));
-				rdb.setDbStoragePath(rocksDb);
-				this.stateBackend = rdb;
+				setupRocksDB(-1, false);
 				break;
 			}
 			case ROCKSDB_INCREMENTAL:
+				// Test RocksDB based timer service as well
+				config.setString(
+					RocksDBOptions.TIMER_SERVICE_FACTORY,
+					RocksDBStateBackend.PriorityQueueStateType.ROCKSDB.toString());
+				setupRocksDB(16, true);
+				break;
 			case ROCKSDB_INCREMENTAL_ZK: {
-				String rocksDb = tempFolder.newFolder().getAbsolutePath();
-				String backups = tempFolder.newFolder().getAbsolutePath();
-				// we use the fs backend with small threshold here to test the behaviour with file
-				// references, not self contained byte handles
-				RocksDBStateBackend rdb =
-					new RocksDBStateBackend(
-						new FsStateBackend(
-							new Path("file://" + backups).toUri(), 16),
-						true);
-				rdb.setDbStoragePath(rocksDb);
-				this.stateBackend = rdb;
+				setupRocksDB(16, true);
 				break;
 			}
 			default:
@@ -195,6 +188,20 @@ private Configuration getConfiguration() throws Exception {
 		return config;
 	}
 
+	private void setupRocksDB(int fileSizeThreshold, boolean incrementalCheckpoints) throws IOException {
+		String rocksDb = tempFolder.newFolder().getAbsolutePath();
+		String backups = tempFolder.newFolder().getAbsolutePath();
+		// we use the fs backend with small threshold here to test the behaviour with file
+		// references, not self contained byte handles
+		RocksDBStateBackend rdb =
+			new RocksDBStateBackend(
+				new FsStateBackend(
+					new Path("file://" + backups).toUri(), fileSizeThreshold),
+				incrementalCheckpoints);
+		rdb.setDbStoragePath(rocksDb);
+		this.stateBackend = rdb;
+	}
+
 	protected Configuration createClusterConfig() throws IOException {
 		TemporaryFolder temporaryFolder = new TemporaryFolder();
 		temporaryFolder.create();


 

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on 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


With regards,
Apache Git Services