Skip to content

Instantly share code, notes, and snippets.

@vovagalchenko
Last active November 15, 2020 21:51
Show Gist options
  • Save vovagalchenko/e3e163f09d5b1cddd8e5811682793cf4 to your computer and use it in GitHub Desktop.
Save vovagalchenko/e3e163f09d5b1cddd8e5811682793cf4 to your computer and use it in GitHub Desktop.
Lookaside cache read operation pseudocode. Please don't mistake this for production-ready code. It's not. The aim of the snippet is to illustrate the high level flow of the algorithm.
public class LookasideCache {
private CacheCluster cacheCluster;
private LeaseUtils leaseUtils;
/**
* Read a value utilizing a lookaside cache.
*
* @param key whose value is to be returned
* @param sourceOfTruthComputation the function to use to fetch the value from the
* source of truth if that should become necessary.
* The computation is presumed to be expensive and
* impose significant load on the source of truth
* data store.
* @return a byte[] representing the value associated with the looked up key.
*/
public byte[] read(byte[] key, Function<byte[], byte[]> sourceOfTruthComputation) {
return read(key, sourceOfTruthComputation, Collections.EMPTY_SET);
}
/**
* A private recursive helper for the above read method. Allows us to carry the set
* of previously seen leases on the stack.
*/
private byte[] read(
byte[] key,
Function<byte[], byte[]> sourceOfTruthComputation,
Set<Lease> previouslySeenLeases
) {
// Start by looking up the provided key as well as all previously seen leases.
List<byte[]> cacheKeysToLookUp = new ArrayList<>();
cacheKeysToLookUp.add(key);
for (Lease previouslySeenLease : previouslySeenLeases) {
cacheKeysToLookUp.add(previouslySeenLease.getNonce());
}
List<byte[]> valuesFromCacheServer = cacheCluster.get(cacheKeysToLookUp);
byte[] valueForKey = valuesFromCacheServer.remove(0);
// Check if the value is stashed behind one of the leases we've previously seen.
for (byte[] valueForPreviouslySeenLease : valuesFromCacheServer) {
if (valueForPreviouslySeenLease != null) {
return valueForPreviouslySeenLease;
}
}
if (valueForKey == null) {
// The value is not in the cache. Let's try to grab a lease on this key.
Lease newLease = leaseUtils.createNew();
boolean leaseAddSucceeded = cacheCluster.atomicAdd(key, newLease.getNonce());
if (leaseAddSucceeded) {
// We managed to acquire a lease on this key. This means it's up to us
// to go to the source of truth and populate the cache with the value
// from there.
byte[] valueFromSourceOfTruth = sourceOfTruthComputation.apply(key);
boolean checkAndSetSuccceeded = cacheCluster.atomicCheckAndSet(
key,
newLease.getNonce(),
valueFromSourceOfTruth
);
// Let's use the lease nonce as the key and associate the value
// we computed with it.
cacheCluster.set(newLease.getNonce(), valueFromSourceOfTruth);
return valueFromSourceOfTruth;
} else {
// Another request managed to acquire the lease before us. Let's retry.
return read(key, sourceOfTruthComputation, previouslySeenLeases);
}
} else if (leaseUtils.isCacheValueLease(valueForKey)) {
// Another cache request is holding the lease on this key. Let's give it
// some time to fill it and try again.
sleep(100);
previouslySeenLeases.add(leaseUtils.fromCacheValue(valueForKey));
return read(key, sourceOfTruthComputation, previouslySeenLeases);
} else {
// Got the value from the cache server, let's return it.
return valueForKey;
}
}
private void sleep(int millis) {
try {
Thread.sleep(millis);
} catch (InterruptedException e) {
System.err.println("Sleep interrupted.");
e.printStackTrace();
}
}
}
interface CacheCluster {
/**
* Gets a list of keys from the cache cluster.
* @param keys to get from the cache cluster.
* @return a list of byte[] representing the values associated with the provided
* keys. The returned list will be parallel to the provided list of keys, in other
* words, the value associated with a certain key will be in the same position in
* the returned list as the key is in the keys list. Nulls in the returned list will
* represent cache misses. While this isn't a great way to design an API, it works
* well for this high level illustration of the algorithm.
*/
List<byte[]> get(List<byte[]> keys);
/**
* Sets associates the provided value with the provided key in the cache cluster.
*/
void set(byte[] key, byte[] value);
/**
* Set the provided value for key if and only if the key has not already been set.
* Otherwise, the operation is failed.
* @return true if the operation succeeds and the value has been set,
* false otherwise.
*/
boolean atomicAdd(byte[] key, byte[] value);
/**
* Set the valueToSet for the provided key if and only if the key is currently
* associated with expectedValue.
* @return true if the operation succeeds and the value has been set,
* false otherwise.
*/
boolean atomicCheckAndSet(byte[] key, byte[] expectedValue, byte[] valueToSet);
}
interface Lease {
byte[] getNonce();
}
interface LeaseUtils {
Lease createNew();
Lease fromCacheValue(byte[] nonce);
boolean isCacheValueLease(byte[] value);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment