[
https://issues.apache.org/jira/browse/FLINK-9423?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16488417#comment-16488417
]
ASF GitHub Bot commented on FLINK-9423:
---------------------------------------
Github user sihuazhou commented on a diff in the pull request:
https://github.com/apache/flink/pull/6062#discussion_r190463723
--- Diff:
flink-streaming-java/src/main/java/org/apache/flink/streaming/api/operators/TimerHeapInternalTimer.java
---
@@ -0,0 +1,235 @@
+/*
+ * 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.annotation.Internal;
+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.api.common.typeutils.base.LongSerializer;
+import org.apache.flink.core.memory.DataInputView;
+import org.apache.flink.core.memory.DataOutputView;
+
+import java.io.IOException;
+
+/**
+ * Implementation of {@link InternalTimer} for the {@link
InternalTimerHeap}.
+ *
+ * @param <K> Type of the keys to which timers are scoped.
+ * @param <N> Type of the namespace to which timers are scoped.
+ */
+@Internal
+public final class TimerHeapInternalTimer<K, N> implements
InternalTimer<K, N> {
+
+ /** The index that indicates that a tracked internal timer is not
tracked. */
+ private static final int NOT_MANAGED_BY_TIMER_QUEUE_INDEX =
Integer.MIN_VALUE;
+
+ private final long timestamp;
+
+ private final K key;
+
+ private final N namespace;
+
+ /**
+ * This field holds the current physical index if this timer when it is
managed by a timer heap so that we can
+ * support fast deletes.
+ */
+ private transient int timerHeapIndex;
+
+ TimerHeapInternalTimer(long timestamp, K key, N namespace) {
+ this.timestamp = timestamp;
+ this.key = key;
+ this.namespace = namespace;
+ this.timerHeapIndex = NOT_MANAGED_BY_TIMER_QUEUE_INDEX;
+ }
+
+ @Override
+ public long getTimestamp() {
+ return timestamp;
+ }
+
+ @Override
+ public K getKey() {
+ return key;
+ }
+
+ @Override
+ public N getNamespace() {
+ return namespace;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+
+ if (o instanceof InternalTimer) {
+ InternalTimer<?, ?> timer = (InternalTimer<?, ?>) o;
+ return timestamp == timer.getTimestamp()
+ && key.equals(timer.getKey())
+ && namespace.equals(timer.getNamespace());
+ }
+
+ return false;
+ }
+
+ /**
+ * Returns the current index of this timer in the owning timer heap.
+ */
+ int getTimerHeapIndex() {
+ return timerHeapIndex;
+ }
+
+ /**
+ * Sets the current index of this timer in the owning timer heap and
should only be called by the managing heap.
+ * @param timerHeapIndex the new index in the timer heap.
+ */
+ void setTimerHeapIndex(int timerHeapIndex) {
+ this.timerHeapIndex = timerHeapIndex;
+ }
+
+ /**
+ * This method can be called to indicate that the timer is no longer
managed be a timer heap, e.g. because it as
+ * removed.
+ */
+ void removedFromTimerQueue() {
+ setTimerHeapIndex(NOT_MANAGED_BY_TIMER_QUEUE_INDEX);
+ }
+
+ @Override
+ public int hashCode() {
+ int result = (int) (timestamp ^ (timestamp >>> 32));
+ result = 31 * result + key.hashCode();
+ result = 31 * result + namespace.hashCode();
+ return result;
+ }
+
+ @Override
+ public String toString() {
+ return "Timer{" +
+ "timestamp=" + timestamp +
+ ", key=" + key +
+ ", namespace=" + namespace +
+ '}';
+ }
+
+ /**
+ * A {@link TypeSerializer} used to serialize/deserialize a {@link
TimerHeapInternalTimer}.
+ */
+ public static class TimerSerializer<K, N> extends
TypeSerializer<InternalTimer<K, N>> {
+
+ private static final long serialVersionUID =
1119562170939152304L;
+
+ private final TypeSerializer<K> keySerializer;
+
+ private final TypeSerializer<N> namespaceSerializer;
+
+ TimerSerializer(TypeSerializer<K> keySerializer,
TypeSerializer<N> namespaceSerializer) {
+ this.keySerializer = keySerializer;
+ this.namespaceSerializer = namespaceSerializer;
+ }
+
+ @Override
+ public boolean isImmutableType() {
+ return false;
+ }
+
+ @Override
+ public TypeSerializer<InternalTimer<K, N>> duplicate() {
+ return this;
--- End diff --
This means that the result of `duplicate()` is not a "duplication" if
`keySerializer` or `namespaceSerializer` is stateful.
> Implement efficient deletes for heap based timer service
> --------------------------------------------------------
>
> Key: FLINK-9423
> URL: https://issues.apache.org/jira/browse/FLINK-9423
> Project: Flink
> Issue Type: Improvement
> Components: Streaming
> Affects Versions: 1.6.0
> Reporter: Stefan Richter
> Assignee: Stefan Richter
> Priority: Major
>
> The current data structures in the `HeapInternalTimerService` are not able to
> support efficient timer deletes, the complexity is currently O\(n\), where n
> is the number of registered timers.
>
> We can keep track of timer's positions in the priority queue and (in
> combination with the already existing set/map) have a more efficient
> algorithm for deletes.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
