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, finalizeadjustCounter, apply, decodeCounter, encodeCounterclone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitcopyCachingConfigToadjustCounter, apply, decodeCounter, encodeCounter, getRange, getRange, removeRangepublic 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()
CachingConfigDefault is 10485760L.
getMaxRangeBytes in interface CachingConfigpublic void setMaxRangeBytes(long maxRangeBytes)
CachingConfigDefault is 10485760L.
setMaxRangeBytes in interface CachingConfigmaxRangeBytes - maximum bytes in any one rangepublic long getMaxTotalBytes()
CachingConfigDefault is 104857600L.
getMaxTotalBytes in interface CachingConfigpublic void setMaxTotalBytes(long maxTotalBytes)
CachingConfigDefault is 104857600L.
setMaxTotalBytes in interface CachingConfigmaxTotalBytes - maximum cached rangespublic int getMaxRanges()
CachingConfigDefault is 256.
getMaxRanges in interface CachingConfigpublic void setMaxRanges(int maxRanges)
CachingConfigDefault is 256.
setMaxRanges in interface CachingConfigmaxRanges - maximum cached rangespublic double getWaitFactor()
CachingConfigThe 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 CachingConfigpublic void setWaitFactor(double waitFactor)
CachingConfigDefault is 1.5.
setWaitFactor in interface CachingConfigwaitFactor - wait factorpublic boolean isReadAhead()
CachingConfigDefault is true.
isReadAhead in interface CachingConfigpublic void setReadAhead(boolean readAhead)
CachingConfigDefault is true.
setReadAhead in interface CachingConfigreadAhead - 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 KVStoreget in class ForwardingKVStorekey - keypublic CloseableIterator<KVPair> getRange(byte[] minKey, byte[] maxKey, boolean reverse)
KVStoreIterator'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 KVStoregetRange in class ForwardingKVStoreminKey - 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 KVStoregetAtLeast in class ForwardingKVStoreminKey - 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 KVStoregetAtMost in class ForwardingKVStoremaxKey - 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)
KVStoreput in interface KVStoreput in class ForwardingKVStorekey - keyvalue - valuepublic void remove(byte[] key)
KVStoreremove in interface KVStoreremove in class ForwardingKVStorekey - 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 KVStoreremoveRange in class ForwardingKVStoreminKey - 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 CloseableKVStoreclose in interface Closeableclose in interface AutoCloseableclose in class CloseableForwardingKVStorepublic double getRttEstimate()
Copyright © 2020. All rights reserved.