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.

LookasideCache.java

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);
}