Local Cache

covers the more advanced scenarios. This article is about the more simple scenarios. The content in this article is rather trivial, but I have written it for completeness as the two articles listed above are missing some stuff.

All examples below will try to cache a simulated database operation that takes 10 milliseconds.

The non-solution:

All modern programming environments has a datastructure for fast lookup (hash table based, tree based or whatever).

package demo;

import java.util.HashMap;
import java.util.Map;
import java.util.function.Function;

public class TestPrimitive {
    private static final int DT = 10;
    private static final int SIZE = 1000;
    private static String realLookup(int key) {
        // simulate expensive DB operation
        try {
            Thread.sleep(DT);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        return "Value#" + key;
    }
    private static Map<Integer, String> cache;
    private static String cacheLookup(int key) {
        String val = cache.get(key);
        if(val == null) {
            val = realLookup(key);
            cache.put(key,  val);
        }
        return val;
    }
    public static void test(String lbl, int startKey, int endKey, Function<Integer, String> lookup) {
        long t1 = System.currentTimeMillis();
        for(int i = startKey; i <= endKey; i++) {
            String val = lookup.apply(i);
            if(!val.equals("Value#" + i)) throw new RuntimeException("Ooops");
        }
        long t2 = System.currentTimeMillis();
        System.out.printf("%s keys %d - %d : %d ms\n", lbl, startKey, endKey, t2 - t1);
    }
    public static void main(String[] args) throws Exception {
        cache = new HashMap<Integer, String>();
        test("No cache", 1, SIZE, key -> realLookup(key));
        test("Cache (1st)", 1, SIZE, key -> cacheLookup(key));
        test("Cache (2nd)", 1, SIZE, key -> cacheLookup(key));
        test("Cache (half)", SIZE / 2 + 1, 3 * SIZE / 2, key -> cacheLookup(key));
        test("Cache (back)", 1, SIZE, key -> cacheLookup(key));
    }
}

using System;
using System.Collections.Generic;
using System.Threading;

namespace LocalCache.TestPrimitive
{
    public class Program
    {
        private const int DT = 10;
        private const int SIZE = 1000;
        private static string RealLookup(int key)
        {
            // simulate expensive DB operation
            Thread.Sleep(DT);
            return "Value#" + key;
        }
        private static IDictionary<int, string> cache;
        private static string CacheLookup(int key)
        {
            string val;
            if(!cache.ContainsKey(key))
            {
                val = RealLookup(key);
                cache[key] = val;
            }
            else
            {
                val = cache[key];
            }
            return val;
        }
        public static void Test(string lbl, int startKey, int endKey, Func<int, string> lookup)
        {
            DateTime t1 = DateTime.Now;
            for(int i = startKey; i <= endKey; i++)
            {
                string val = lookup(i);
                if(val != "Value#" + i) throw new Exception("Ooops");
            }
            DateTime t2 = DateTime.Now;
            Console.WriteLine("{0} keys {1} - {2} : {3} ms", lbl, startKey, endKey, (long)(t2 - t1).TotalMilliseconds);
        }
        public static void Main(string[] args)
        {
            cache = new Dictionary<int, string>();
            Test("No cache", 1, SIZE, key => RealLookup(key));
            Test("Cache (1st)", 1, SIZE, key => CacheLookup(key));
            Test("Cache (2nd)", 1, SIZE, key => CacheLookup(key));
            Test("Cache (half)", SIZE / 2 + 1, 3 * SIZE / 2, key => CacheLookup(key));
            Test("Cache (back)", 1, SIZE, key => CacheLookup(key));
            Console.ReadKey();
        }
    }
}

from time import sleep, time

DT = 10
SIZE = 1000

def real_lookup(key):
    sleep(DT / 1000.0)
    return 'Value#' + str(key)

cache = {}
def cache_lookup(key):
    if key not in cache:
        val = real_lookup(key)
        cache[key] = val
    else:
        val = cache[key]
    return val

def test(lbl, start_key, end_key, lookup):
    t1 = time()
    for i in range(start_key, end_key + 1):
        val = lookup(i)
        if val != 'Value#' + str(i):
            raise Exception('Ooops')
    t2 = time()
    print('%s keys %d - %d : %d ms' % (lbl, start_key, end_key, (t2 - t1) * 1000));
        
test('No cache', 1, SIZE, lambda key: real_lookup(key));
test('Cache (1st)', 1, SIZE, lambda key: cache_lookup(key));
test('Cache (2nd)', 1, SIZE, lambda key: cache_lookup(key));
test('Cache (half)', SIZE // 2 + 1, 3 * SIZE // 2, lambda key: cache_lookup(key));
test('Cache (back)', 1, SIZE, lambda key: cache_lookup(key));

<?php

define('DT', 10);
define('SIZE', 1000);

function real_lookup($key) {
    usleep(DT * 1000);
    return 'Value#' . $key;
}

$cache = [];
function cache_lookup($key) {
    global $cache;
    if(!isset($cache[$key])) {
        $val = real_lookup($key);
        $cache[$key] = $val;
    } else {
        $val = $cache[$key];
    }
    return $val;
}

function test($lbl, $start_key, $end_key, $lookup) {
    $t1 = microtime(true);
    for($i = $start_key; $i <= $end_key; $i++) {
        $val = $lookup($i);
        if($val != 'Value#' . $i) throw new Exception('Ooops');
    }
    $t2 = microtime(true);
    printf("%s keys %d - %d : %d ms\n", $lbl, $start_key, $end_key, ($t2 - $t1) * 1000);
}

test('No cache', 1, SIZE, fn($key) => real_lookup($key));
test('Cache (1st)', 1, SIZE, fn($key) => cache_lookup($key));
test('Cache (2nd)', 1, SIZE, fn($key) => cache_lookup($key));
test('Cache (half)', SIZE / 2 + 1, 3 * SIZE / 2, fn($key) => cache_lookup($key));
test('Cache (back)', 1, SIZE, fn($key) => cache_lookup($key));

?>

The problem:

Biggest problem is that no entries get removed from the cache ever, so the size of the cache will keep growing over time. In many cases that will cause the application to run out of memory and crash. Not good.

Another potential problem is that in some cases the business logic considers it acceptable if the cache returns an obsolete value for X seconds after the value has been updated without the cache being updated (simple example: a DBA changed data in the database at an SQL prompt), but if no entries removed from the cache ever, then the obsolete value could be used for hours/days/months. Not good.

A cache library is basically something providing map / dictionary / associative array functionality but with mechanisms to get entries out of the cache again.

All examples below will try to implement a size limit of 1000 entries and expiration after 60 seconds.

Note that practically all cache libraries are a bit relaxed regarding purge of entries for performance reasons. Do not expect purge to start exactly when the size limit is reached. Do not expect entries to be purged exactly at expiration time. The cache library purges when considered convenient.

Java:

.NET:

Python:

It is worth noting that Python has a unique annotation/attribute based approach to caching the requires a lot less code than in other languages.

PHP:

The variety of PHP execution models make even no-distributed cache in PHP tricky.

Local Cache

Content:

Introduction:

The non-solution:

The problem:

Java:

.NET:

Python:

PHP:

Article history:

Other articles:

Comments: