Package io.permazen.kv.caching

Class CachingKVStore

java.lang.Object
io.permazen.kv.util.ForwardingKVStore
io.permazen.kv.util.CloseableForwardingKVStore
io.permazen.kv.caching.CachingKVStore
All Implemented Interfaces:
CachingConfig, CloseableKVStore, KVStore, Closeable, AutoCloseable
public class CachingKVStore extends CloseableForwardingKVStore implements CachingConfig
A caching layer for read-only KVStore's that have high latency for individual reads but low latency for consecutive key/value pairs in a KVStore.getRange() range read.

An example is a KVStore backed by a service provided over the network. Reading one key/value pair costs a network round trip, whereas when reading a whole range of keys the round trip time is amortized over the whole range because many key/value pairs can be streamed in a single response.

Caching and Read-Ahead

All queries to the underlying KVStore are range queries. Internally, instances store the results from these queries as contiguous key ranges with the associated values. Queries contained within a known range can be answered immediately; other queries trigger the creation of a new range or the extension of an existing range.

By default, instances are configured for read ahead, so that underlying range reads extend past the end of the requested limit, in anticipation of further queries from the nearby region of the key space.

These underlying queries are performed asynchronously in background tasks, and multiple background range queries may be running at the same time. To avoid creating redundant background queries, when handling a query for a key/value pair that may possibly be answered by an existing but uncompleted background range query (depending on key/value pairs yet to arrive), instances will sometimes speculatively delay creating a new task. This decision is based on an ongoing estimation of round-trip time, and the uncompleted background query's data arrival rate.

Configuration

Instances are configured with limits on the maximum number of contiguous key/value ranges, the maximum amount of data to preload into a single contiguous key/value range, and the maximum total amount of data to cache. Once these limits are exceeded, stored ranges are discarded on a least-recently-used basis.

Consistency Assumptions

This class assumes the underlying key/value store is read-only and unchanging, so that cached values are always up-to-date. Attempts to modify the key/value store will result in an UnsupportedOperationException.

Warning: this class assumes that the underlying KVStore provides fully consistent reads: the data returned by any two read operations, no matter when they occur, will be consistent. Enabling assertions on this package may detect some violations of this assumption.

See Also:

  • Field Details

    • DEFAULT_MAX_RANGES

      public static final int DEFAULT_MAX_RANGES
      Default maximum number of contiguous ranges of key/value pairs to allow before we start purging the least recently used ones (256).
      See Also:

    • DEFAULT_MAX_RANGE_BYTES

      public static final long DEFAULT_MAX_RANGE_BYTES
      Default maximum number of bytes to cache in a single contiguous range of key/value pairs (10485760L).
      See Also:

    • DEFAULT_MAX_TOTAL_BYTES

      public static final long DEFAULT_MAX_TOTAL_BYTES
      Default maximum total number of bytes to cache including all ranges (104857600L).
      See Also:

  • Constructor Details

    • CachingKVStore

      public CachingKVStore(KVStore kvstore, ExecutorService executor, long rttEstimate)
      Constructor.
      Parameters:
      kvstore - underlying key/value store
      executor - executor for performing asynchronous batch queries
      rttEstimate - initial round trip time estimate in nanoseconds
      Throws:
      IllegalArgumentException - if either parameter is null
      IllegalArgumentException - if rttEstimate is negative

    • CachingKVStore

      public CachingKVStore(CloseableKVStore kvstore, ExecutorService executor, long rttEstimate)
      Constructor for when the underlying KVStore should be closed when this instance is closed.
      Parameters:
      kvstore - underlying key/value store; will be closed on close()
      executor - executor for performing asynchronous batch queries
      rttEstimate - initial round trip time estimate in nanoseconds
      Throws:
      IllegalArgumentException - if either parameter is null
      IllegalArgumentException - if rttEstimate is negative

  • Method Details

    • getMaxRangeBytes

      public long getMaxRangeBytes()
      Description copied from interface: CachingConfig
      Get the maximum number of bytes to cache in a single contiguous range of key/value pairs.

      Default is 10485760L.

      Specified by:
      getMaxRangeBytes in interface CachingConfig
      Returns:
      maximum bytes in any one range

    • setMaxRangeBytes

      public void setMaxRangeBytes(long maxRangeBytes)
      Description copied from interface: CachingConfig
      Configure the maximum number of bytes to cache in a single contiguous range of key/value pairs.

      Default is 10485760L.

      Specified by:
      setMaxRangeBytes in interface CachingConfig
      Parameters:
      maxRangeBytes - maximum bytes in any one range

    • getMaxTotalBytes

      public long getMaxTotalBytes()
      Description copied from interface: CachingConfig
      Get the total number of bytes to cache. This is an overal maximum incluging all ranges.

      Default is 104857600L.

      Specified by:
      getMaxTotalBytes in interface CachingConfig
      Returns:
      maximum cached ranges

    • setMaxTotalBytes

      public void setMaxTotalBytes(long maxTotalBytes)
      Description copied from interface: CachingConfig
      Configure the total number of bytes to cache. This is an overal maximum incluging all ranges.

      Default is 104857600L.

      Specified by:
      setMaxTotalBytes in interface CachingConfig
      Parameters:
      maxTotalBytes - maximum cached ranges

    • getMaxRanges

      public int getMaxRanges()
      Description copied from interface: CachingConfig
      Get the maximum number of contiguous ranges of key/value pairs to allow before we start purging the least recently used ones.

      Default is 256.

      Specified by:
      getMaxRanges in interface CachingConfig
      Returns:
      maximum cached ranges

    • setMaxRanges

      public void setMaxRanges(int maxRanges)
      Description copied from interface: CachingConfig
      Configure the maximum number of contiguous ranges of key/value pairs to allow before we start purging the least recently used ones.

      Default is 256.

      Specified by:
      setMaxRanges in interface CachingConfig
      Parameters:
      maxRanges - maximum cached ranges

    • getWaitFactor

      public double getWaitFactor()
      Description copied from interface: CachingConfig
      Get the wait factor.

      The wait factor, when multiplied by the estimated amount of time we expect to have to wait for incoming data that's already on its way, is how long we will actually wait for that data before initiating a new query. A value of zero means never wait, i.e., always start a new query immediately; a value of 1.0 would mean to wait up to the estimated amount of time; a very high value would mean wait until the outstanding query either produces the data or completes.

      Default is 1.5.

      Specified by:
      getWaitFactor in interface CachingConfig
      Returns:
      wait factor

    • setWaitFactor

      public void setWaitFactor(double waitFactor)
      Description copied from interface: CachingConfig
      Set the wait factor.

      Default is 1.5.

      Specified by:
      setWaitFactor in interface CachingConfig
      Parameters:
      waitFactor - wait factor

    • isReadAhead

      public boolean isReadAhead()
      Description copied from interface: CachingConfig
      Get whether this instance is configured to perform read-ahead.

      Default is true.

      Specified by:
      isReadAhead in interface CachingConfig
      Returns:
      true if read-ahead is enabled, otherwise false

    • setReadAhead

      public void setReadAhead(boolean readAhead)
      Description copied from interface: CachingConfig
      Configure whether read-ahead is enabled.

      Default is true.

      Specified by:
      setReadAhead in interface CachingConfig
      Parameters:
      readAhead - true to enable read-ahead, false to disable

    • get

      public ByteData get(ByteData key)
      Description copied from interface: KVStore
      Get the value associated with the given key, if any.
      Specified by:
      get in interface KVStore
      Overrides:
      get in class ForwardingKVStore
      Parameters:
      key - key
      Returns:
      value associated with key, or null if not found

    • getRange

      public CloseableIterator<KVPair> getRange(ByteData minKey, ByteData maxKey, boolean reverse)
      Description copied from interface: KVStore
      Iterate the key/value pairs in the specified range. The returned CloseableIterator's remove() method must be supported and should have the same effect as invoking remove() on the corresponding key.

      If keys starting with 0xff are not supported by this instance, and minKey starts with 0xff, then this method returns an empty iteration.

      If keys starting with 0xff are not supported by this instance, and maxKey starts with 0xff, then this method behaves as if maxKey were null.

      The returned CloseableIterator is weakly consistent (see java.util.concurrent). In short, the returned CloseableIterator must not throw ConcurrentModificationException; however, whether or not a "live" CloseableIterator reflects any modifications made after its creation is implementation dependent. Implementations that do make post-creation updates visible in the CloseableIterator, even if the update occurs after some delay, must preserve the order in which the modifications actually occurred.

      The returned CloseableIterator itself is not guaranteed to be thread safe; is should only be used in the thread that created it.

      Invokers of this method are encouraged to close() the returned iterators, though this is not required for correct behavior.

      Specified by:
      getRange in interface KVStore
      Overrides:
      getRange in class ForwardingKVStore
      Parameters:
      minKey - minimum key (inclusive), or null for no minimum (start at the smallest key)
      maxKey - maximum key (exclusive), or null for no maximum (end at the largest key)
      reverse - true to return key/value pairs in reverse order (i.e., keys descending)
      Returns:
      iteration of key/value pairs in the range minKey (inclusive) to maxKey (exclusive)

    • getAtLeast

      public KVPair getAtLeast(ByteData minKey, ByteData maxKey)
      Description copied from interface: KVStore
      Get the key/value pair having the smallest key greater than or equal to the given minimum, if any.

      An optional (exclusive) maximum key may also be specified; if maxKey is null, there is no upper bound; if maxKey <= minKey, null is always returned.

      If keys starting with 0xff are not supported by this instance, and minKey starts with 0xff, then this method returns null.

      Specified by:
      getAtLeast in interface KVStore
      Overrides:
      getAtLeast in class ForwardingKVStore
      Parameters:
      minKey - minimum key (inclusive), or null for no minimum (get the smallest key)
      maxKey - maximum key (exclusive), or null for no maximum (no upper bound)
      Returns:
      smallest key/value pair with key >= minKey and key < maxKey, or null if none exists

    • getAtMost

      public KVPair getAtMost(ByteData maxKey, ByteData minKey)
      Description copied from interface: KVStore
      Get the key/value pair having the largest key strictly less than the given maximum, if any.

      An optional (inclusive) minimum key may also be specified; if minKey is null, there is no lower bound (equivalent to a lower bound of the empty byte array); if minKey >= maxKey, null is always returned.

      If keys starting with 0xff are not supported by this instance, and maxKey starts with 0xff, then this method behaves as if maxKey were null.

      Specified by:
      getAtMost in interface KVStore
      Overrides:
      getAtMost in class ForwardingKVStore
      Parameters:
      maxKey - maximum key (exclusive), or null for no maximum (get the largest key)
      minKey - minimum key (inclusive), or null for no minimum (no lower bound)
      Returns:
      largest key/value pair with key < maxKey and key >= minKey, or null if none exists

    • put

      public void put(ByteData key, ByteData value)
      Description copied from interface: KVStore
      Set the value associated with the given key.
      Specified by:
      put in interface KVStore
      Overrides:
      put in class ForwardingKVStore
      Parameters:
      key - key
      value - value

    • remove

      public void remove(ByteData key)
      Description copied from interface: KVStore
      Remove the key/value pair with the given key, if it exists.
      Specified by:
      remove in interface KVStore
      Overrides:
      remove in class ForwardingKVStore
      Parameters:
      key - key

    • removeRange

      public void removeRange(ByteData minKey, ByteData maxKey)
      Description copied from interface: KVStore
      Remove all key/value pairs whose keys are in a given range.

      The minKey must be less than or equal to maxKey; if they equal (and not null) then nothing happens; if they are both null then all entries are deleted.

      If keys starting with 0xff are not supported by this instance, then:

      • If minKey starts with 0xff, then no change occurs
      • If maxKey starts with 0xff, then this method behaves as if maxKey were null
      Specified by:
      removeRange in interface KVStore
      Overrides:
      removeRange in class ForwardingKVStore
      Parameters:
      minKey - minimum key (inclusive), or null for no minimum
      maxKey - maximum key (exclusive), or null for no maximum

    • close

      public void close()
      Close this instance and release any resources associated with it.

      This does not shutdown the ExecutorService provided to the constructor.

      If this instance is already closed, then nothing happens.

      Specified by:
      close in interface AutoCloseable
      Specified by:
      close in interface Closeable
      Specified by:
      close in interface CloseableKVStore
      Overrides:
      close in class CloseableForwardingKVStore

    • getRttEstimate

      public double getRttEstimate()
      Get the current round trip time estimate.
      Returns:
      current RTT estimate in nanoseconds