public class CachingKVStore extends CloseableForwardingKVStore implements CachingConfig
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.
CachingKVDatabase
Modifier and Type | Field and Description |
---|---|
static long |
DEFAULT_MAX_RANGE_BYTES
Default maximum number of bytes to cache in a single contiguous range of key/value pairs
(10485760L).
|
static 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).
|
static long |
DEFAULT_MAX_TOTAL_BYTES
Default maximum total number of bytes to cache including all ranges (104857600L).
|
DEFAULT_READ_AHEAD, DEFAULT_WAIT_FACTOR
Constructor and Description |
---|
CachingKVStore(CloseableKVStore kvstore,
ExecutorService executor,
long rttEstimate)
Constructor for when the underlying
KVStore should be closed when this instance is closed. |
CachingKVStore(KVStore kvstore,
ExecutorService executor,
long rttEstimate)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
void |
close()
Close this instance and release any resources associated with it.
|
byte[] |
get(byte[] key)
Get the value associated with the given key, if any.
|
KVPair |
getAtLeast(byte[] minKey,
byte[] maxKey)
Get the key/value pair having the smallest key greater than or equal to the given minimum, if any.
|
KVPair |
getAtMost(byte[] maxKey,
byte[] minKey)
Get the key/value pair having the largest key strictly less than the given maximum, if any.
|
long |
getMaxRangeBytes()
Get the maximum number of bytes to cache in a single contiguous range of key/value pairs.
|
int |
getMaxRanges()
Get the maximum number of contiguous ranges of key/value pairs to allow before we start purging the
least recently used ones.
|
long |
getMaxTotalBytes()
Get the total number of bytes to cache.
|
CloseableIterator<KVPair> |
getRange(byte[] minKey,
byte[] maxKey,
boolean reverse)
Iterate the key/value pairs in the specified range.
|
double |
getRttEstimate()
Get the current round trip time estimate.
|
double |
getWaitFactor()
Get the wait factor.
|
boolean |
isReadAhead()
Get whether this instance is configured to perform read-ahead.
|
void |
put(byte[] key,
byte[] value)
Set the value associated with the given key.
|
void |
remove(byte[] key)
Remove the key/value pair with the given key, if it exists.
|
void |
removeRange(byte[] minKey,
byte[] maxKey)
Remove all key/value pairs whose keys are in a given range.
|
void |
setMaxRangeBytes(long maxRangeBytes)
Configure the maximum number of bytes to cache in a single contiguous range of key/value pairs.
|
void |
setMaxRanges(int maxRanges)
Configure the maximum number of contiguous ranges of key/value pairs to allow before we start purging the
least recently used ones.
|
void |
setMaxTotalBytes(long maxTotalBytes)
Configure the total number of bytes to cache.
|
void |
setReadAhead(boolean readAhead)
Configure whether read-ahead is enabled.
|
void |
setWaitFactor(double waitFactor)
Set the wait factor.
|
delegate, finalize
adjustCounter, apply, decodeCounter, encodeCounter
clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
copyCachingConfigTo
adjustCounter, apply, decodeCounter, encodeCounter, getRange, getRange, removeRange
public static final int DEFAULT_MAX_RANGES
public static final long DEFAULT_MAX_RANGE_BYTES
public static final long DEFAULT_MAX_TOTAL_BYTES
public CachingKVStore(KVStore kvstore, ExecutorService executor, long rttEstimate)
kvstore
- underlying key/value storeexecutor
- executor for performing asynchronous batch queriesrttEstimate
- initial round trip time estimate in nanosecondsIllegalArgumentException
- if either parameter is nullIllegalArgumentException
- if rttEstimate
is negativepublic CachingKVStore(CloseableKVStore kvstore, ExecutorService executor, long rttEstimate)
KVStore
should be closed when this instance is closed.kvstore
- underlying key/value store; will be closed on close()
executor
- executor for performing asynchronous batch queriesrttEstimate
- initial round trip time estimate in nanosecondsIllegalArgumentException
- if either parameter is nullIllegalArgumentException
- if rttEstimate
is negativepublic long getMaxRangeBytes()
CachingConfig
Default is 10485760L.
getMaxRangeBytes
in interface CachingConfig
public void setMaxRangeBytes(long maxRangeBytes)
CachingConfig
Default is 10485760L.
setMaxRangeBytes
in interface CachingConfig
maxRangeBytes
- maximum bytes in any one rangepublic long getMaxTotalBytes()
CachingConfig
Default is 104857600L.
getMaxTotalBytes
in interface CachingConfig
public void setMaxTotalBytes(long maxTotalBytes)
CachingConfig
Default is 104857600L.
setMaxTotalBytes
in interface CachingConfig
maxTotalBytes
- maximum cached rangespublic int getMaxRanges()
CachingConfig
Default is 256.
getMaxRanges
in interface CachingConfig
public void setMaxRanges(int maxRanges)
CachingConfig
Default is 256.
setMaxRanges
in interface CachingConfig
maxRanges
- maximum cached rangespublic double getWaitFactor()
CachingConfig
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.
getWaitFactor
in interface CachingConfig
public void setWaitFactor(double waitFactor)
CachingConfig
Default is 1.5.
setWaitFactor
in interface CachingConfig
waitFactor
- wait factorpublic boolean isReadAhead()
CachingConfig
Default is true.
isReadAhead
in interface CachingConfig
public void setReadAhead(boolean readAhead)
CachingConfig
Default is true.
setReadAhead
in interface CachingConfig
readAhead
- true to enable read-ahead, false to disablepublic byte[] get(byte[] key)
KVStore
Modifications to the returned byte[]
array do not affect this instance.
get
in interface KVStore
get
in class ForwardingKVStore
key
- keypublic CloseableIterator<KVPair> getRange(byte[] minKey, byte[] maxKey, boolean reverse)
KVStore
Iterator
'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 Iterator
must not throw ConcurrentModificationException
;
however, whether or not a "live" Iterator
reflects any modifications made after its creation is
implementation dependent. Implementations that do make post-creation updates visible in the Iterator
,
even if the update occurs after some delay, must preserve the order in which the modifications actually occurred.
The returned Iterator
itself is not guaranteed to be thread safe.
Invokers of this method are encouraged to close()
the returned iterators,
though this is not required for correct behavior.
Modifications to the returned KVPair
key and value byte[]
arrays do not affect this instance.
getRange
in interface KVStore
getRange
in class ForwardingKVStore
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)minKey
(inclusive) to maxKey
(exclusive)public KVPair getAtLeast(byte[] minKey, byte[] maxKey)
KVStore
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.
Modifications to the returned byte[]
arrays do not affect this instance.
getAtLeast
in interface KVStore
getAtLeast
in class ForwardingKVStore
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)key >= minKey
and key < maxKey
, or null if none existspublic KVPair getAtMost(byte[] maxKey, byte[] minKey)
KVStore
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.
Modifications to the returned byte[]
arrays do not affect this instance.
getAtMost
in interface KVStore
getAtMost
in class ForwardingKVStore
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)key < maxKey
and key >= minKey
, or null if none existspublic void put(byte[] key, byte[] value)
KVStore
put
in interface KVStore
put
in class ForwardingKVStore
key
- keyvalue
- valuepublic void remove(byte[] key)
KVStore
remove
in interface KVStore
remove
in class ForwardingKVStore
key
- keypublic void removeRange(byte[] minKey, byte[] maxKey)
KVStore
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:
minKey
starts with 0xff
, then no change occursmaxKey
starts with 0xff
, then this method behaves as if maxKey
were nullremoveRange
in interface KVStore
removeRange
in class ForwardingKVStore
minKey
- minimum key (inclusive), or null for no minimummaxKey
- maximum key (exclusive), or null for no maximumpublic void close()
This does not shutdown the ExecutorService
provided to the constructor.
If this instance is already closed, then nothing happens.
close
in interface CloseableKVStore
close
in interface Closeable
close
in interface AutoCloseable
close
in class CloseableForwardingKVStore
public double getRttEstimate()
Copyright © 2022. All rights reserved.