...

• we propose a public classes, MultiVersionedKeyQuery.
• Moreover, the public interface ValueIterator is added to iterate over different values that are returned from a single-key query (each value corresponds to a timestamp). 
• In addition, a new method is added to the VersionedKeyValueStore interface to support single-key_multi-timestamp queries.
• Finally a field called validTo is added to the VersionedRecord class to enable us retrieving tombstones as well. 

Proposed Changes

To be able to list the tombstones, the VersionedRecord class can accept NULL values as well.the validTo filed is added to the VersionedRecord class.

package org.apache.kafka.streams.state;

public final class VersionedRecord<V> {

    /**
     * Create a new {@link VersionedRecord} instance. {@code value} cannot be {@code null}.
     *
     * @param value      the value
     * @param timestamp  the timestamp
     * @param validTo  the validTo timestamp
     */
     public VersionedRecord(final V value, final long timestamp, final long validTo);


    /**
     * Returns the {@code validTo} 
     */
     public long validTo();
}

For single-key queries, MultiVersionedKeyQuery and ValueIterator classes will be used.

...