flink-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From StefanRRichter <...@git.apache.org>
Subject [GitHub] flink pull request #6228: [FLINK-9491] Implement timer data structure based ...
Date Tue, 03 Jul 2018 13:56:17 GMT
Github user StefanRRichter commented on a diff in the pull request:

    https://github.com/apache/flink/pull/6228#discussion_r199816139
  
    --- Diff: flink-runtime/src/main/java/org/apache/flink/runtime/state/heap/KeyGroupPartitionedPriorityQueue.java
---
    @@ -0,0 +1,280 @@
    +/*
    + * 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.KeyExtractorFunction;
    +import org.apache.flink.runtime.state.KeyGroupRange;
    +import org.apache.flink.runtime.state.KeyGroupRangeAssignment;
    +import org.apache.flink.util.CloseableIterator;
    +import org.apache.flink.util.IOUtils;
    +
    +import javax.annotation.Nonnegative;
    +import javax.annotation.Nonnull;
    +import javax.annotation.Nullable;
    +
    +import java.util.Collection;
    +import java.util.Comparator;
    +
    +/**
    + * This implementation of {@link InternalPriorityQueue} is internally partitioned into
sub-queues per key-group and
    + * essentially works as a heap-of-heaps. Instances will have set semantics for elements
if the sub-queues have set
    + * semantics.
    + *
    + * @param <T> the type of elements in the queue.
    + * @param <PQ> type type of sub-queue used for each key-group partition.
    + */
    +public class KeyGroupPartitionedPriorityQueue<T, PQ extends InternalPriorityQueue<T>
& HeapPriorityQueueElement>
    +	implements InternalPriorityQueue<T> {
    +
    +	/** A heap of heap sets. Each sub-heap represents the partition for a key-group.*/
    +	@Nonnull
    +	private final HeapPriorityQueue<PQ> keyGroupHeap;
    +
    +	/** All elements from keyGroupHeap, indexed by their key-group id, relative to firstKeyGroup.
*/
    +	@Nonnull
    +	private final PQ[] keyGroupLists;
    +
    +	/** Function to extract the key from contained elements. */
    +	@Nonnull
    +	private final KeyExtractorFunction<T> keyExtractor;
    +
    +	/** The total number of key-groups (in the job). */
    +	@Nonnegative
    +	private final int totalKeyGroups;
    +
    +	/** The smallest key-group id with a subpartition managed by this ordered set. */
    +	@Nonnegative
    +	private final int firstKeyGroup;
    +
    +	@SuppressWarnings("unchecked")
    +	public KeyGroupPartitionedPriorityQueue(
    +		@Nonnull KeyExtractorFunction<T> keyExtractor,
    +		@Nonnull Comparator<T> elementComparator,
    +		@Nonnull PartitionQueueSetFactory<T, PQ> orderedCacheFactory,
    +		@Nonnull KeyGroupRange keyGroupRange,
    +		@Nonnegative int totalKeyGroups) {
    +
    +		this.keyExtractor = keyExtractor;
    +		this.totalKeyGroups = totalKeyGroups;
    +		this.firstKeyGroup = keyGroupRange.getStartKeyGroup();
    +		this.keyGroupLists = (PQ[]) new InternalPriorityQueue[keyGroupRange.getNumberOfKeyGroups()];
    +		this.keyGroupHeap = new HeapPriorityQueue<>(
    +			new InternalPriorityQueueComparator<>(elementComparator),
    +			keyGroupRange.getNumberOfKeyGroups());
    +		for (int i = 0; i < keyGroupLists.length; i++) {
    +			final PQ keyGroupCache =
    +				orderedCacheFactory.create(firstKeyGroup + i, totalKeyGroups, elementComparator);
    +			keyGroupLists[i] = keyGroupCache;
    +			keyGroupHeap.add(keyGroupCache);
    +		}
    +	}
    +
    +	@Nullable
    +	@Override
    +	public T poll() {
    +		final PQ headList = keyGroupHeap.peek();
    +		final T head = headList.poll();
    +		keyGroupHeap.adjustModifiedElement(headList);
    +		return head;
    +	}
    +
    +	@Nullable
    +	@Override
    +	public T peek() {
    +		return keyGroupHeap.peek().peek();
    +	}
    +
    +	@Override
    +	public boolean add(@Nonnull T toAdd) {
    +		final PQ list = getListForElementKeyGroup(toAdd);
    +
    +		// the branch checks if the head element has (potentially) changed.
    +		if (list.add(toAdd)) {
    +			keyGroupHeap.adjustModifiedElement(list);
    +			// could we have a new head?
    +			return toAdd.equals(peek());
    +		} else {
    +			// head unchanged
    +			return false;
    +		}
    +	}
    +
    +	@Override
    +	public boolean remove(@Nonnull T toRemove) {
    +		final PQ list = getListForElementKeyGroup(toRemove);
    +
    +		final T oldHead = peek();
    +
    +		// the branch checks if the head element has (potentially) changed.
    +		if (list.remove(toRemove)) {
    +			keyGroupHeap.adjustModifiedElement(list);
    +			// could we have a new head?
    +			return toRemove.equals(oldHead);
    +		} else {
    +			// head unchanged
    +			return false;
    +		}
    +	}
    +
    +	@Override
    +	public boolean isEmpty() {
    +		return peek() == null;
    +	}
    +
    +	@Override
    +	public int size() {
    +		int sizeSum = 0;
    +		for (PQ list : keyGroupLists) {
    +			sizeSum += list.size();
    +		}
    +		return sizeSum;
    +	}
    +
    +	@Override
    +	public void addAll(@Nullable Collection<? extends T> toAdd) {
    +
    +		if (toAdd == null) {
    +			return;
    +		}
    +
    +		// TODO consider bulk loading the partitions and "heapify" keyGroupHeap once after
all elements are inserted.
    +		for (T element : toAdd) {
    +			add(element);
    +		}
    +	}
    +
    +	@Nonnull
    +	@Override
    +	public CloseableIterator<T> iterator() {
    +		return new KeyGroupConcatenationIterator<>(keyGroupLists);
    +	}
    +
    +	private PQ getListForElementKeyGroup(T element) {
    +		return keyGroupLists[computeKeyGroupIndex(element)];
    +	}
    +
    +	private int computeKeyGroupIndex(T element) {
    +		final Object extractKeyFromElement = keyExtractor.extractKeyFromElement(element);
    +		final int keyGroupId = KeyGroupRangeAssignment.assignToKeyGroup(extractKeyFromElement,
totalKeyGroups);
    +		return keyGroupId - firstKeyGroup;
    +	}
    +
    +	/**
    +	 * Iterator for {@link KeyGroupPartitionedPriorityQueue}. This iterator is not guaranteeing
any order of elements.
    +	 * Using code must {@link #close()} after usage.
    +	 *
    +	 * @param <T> the type of iterated elements.
    +	 */
    +	private static final class KeyGroupConcatenationIterator<
    +		T, PQS extends InternalPriorityQueue<T> & HeapPriorityQueueElement>
    +		implements CloseableIterator<T> {
    +
    +		/** Array with the subpartitions that we iterate. No null values in the array. */
    +		@Nonnull
    +		private final PQS[] keyGroupLists;
    +
    +		/** The subpartition the is currently iterated. */
    +		@Nonnegative
    +		private int index;
    +
    +		/** The iterator of the current subpartition. */
    +		@Nonnull
    +		private CloseableIterator<T> current;
    +
    +		private KeyGroupConcatenationIterator(@Nonnull PQS[] keyGroupLists) {
    +			this.keyGroupLists = keyGroupLists;
    +			this.index = 0;
    +			this.current = CloseableIterator.empty();
    +		}
    +
    +		@Override
    +		public boolean hasNext() {
    +			boolean currentHasNext = current.hasNext();
    +
    +			// find the iterator of the next partition that has elements.
    +			while (!currentHasNext && index < keyGroupLists.length) {
    +				IOUtils.closeQuietly(current);
    +				current = keyGroupLists[index++].iterator();
    +				currentHasNext = current.hasNext();
    +			}
    +			return currentHasNext;
    +		}
    +
    +		@Override
    +		public T next() {
    +			return current.next();
    +		}
    +
    +		@Override
    +		public void close() throws Exception {
    +			current.close();
    +		}
    +	}
    +
    +	/**
    +	 * Comparator that compares {@link InternalPriorityQueue} objects by their head element.
Must handle null results
    +	 * from {@link #peek()}.
    +	 *
    +	 * @param <T> type of the elements in the compared queues.
    +	 * @param <Q> type of queue.
    +	 */
    +	private static final class InternalPriorityQueueComparator<T, Q extends InternalPriorityQueue<T>>
    +		implements Comparator<Q> {
    +
    +		/** Comparator for the queue elements, so we can compare their heads. */
    +		@Nonnull
    +		private final Comparator<T> elementComparator;
    +
    +		InternalPriorityQueueComparator(@Nonnull Comparator<T> elementComparator) {
    +			this.elementComparator = elementComparator;
    +		}
    +
    +		@Override
    +		public int compare(Q o1, Q o2) {
    +			final T leftTimer = o1.peek();
    +			final T rightTimer = o2.peek();
    --- End diff --
    
    👍 


---

Mime
View raw message