Cache Algorithms Overview and SpringBoot Caffeine Integration

About Cache Algorithms

Cache design in architecture includes many types; common replacement algorithms are FIFO, LRU, LFU, and the widely used W‑TinyLFU.

FIFO Algorithm

This algorithm is typically applied to a cache queue: when a request hits an element, it is placed into the queue, and subsequent hits follow the same rule until the queue is full, at which point the oldest element is evicted.

Drawback: If an old element is not accessed for a while it moves to the tail of the queue; even if accessed later it remains at the tail, so when eviction occurs the old (potentially hot) element may be mistakenly removed.

LRU Algorithm

When the cache queue already contains elements, a later request that hits an existing element moves that element to the head of the queue, reducing its risk of being cleared.

Drawback: LRU can suffer from cache pollution when a burst of non‑hot queries fills the cache, pushing out true hot data.

To avoid this pollution, the LFU strategy was introduced.

LFU Algorithm

LFU adds an extra memory space to record the access frequency of each cached element and decides which elements to retain or evict based on that frequency.

The main drawback is the additional space required to store counters, which grows with the number of cache entries.

Drawback

LFU can also cause cache pollution; for example, a flash‑sale may cause a batch of data to be accessed millions of times, inflating its frequency, and after the event the data remains in cache despite no longer being needed.

W‑TinyLFU Algorithm

Traditional LFU stores frequencies as key‑value pairs, which consumes a lot of space. W‑TinyLFU compresses frequencies using a bitmap‑like approach, storing each frequency in four bits of a long array (max value 15).

The bitmap maps a key's hash to a bit index; the smallest of four stored 4‑bit values is taken as the frequency. Caffeine treats frequencies >15 as hot data, using only four bits per entry, allowing 16 frequencies per 64‑bit long.

By shifting the hash and adding it four times, up to 13 of the 16 slots are utilized efficiently.

SpringBoot Internal Use of Caffeine Example

First add the following Maven dependencies:

<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-cache</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>
    <dependency>
        <groupId>com.github.ben-manes.caffeine</groupId>
        <artifactId>caffeine</artifactId>
        <version>2.6.2</version>
    </dependency>
</dependencies>

Then configure application.properties :

spring.cache.cache-names=userCache
spring.cache.caffeine.spec=initialCapacity=50,maximumSize=500,expireAfterWrite=10s
server.port=8080

Startup class:

package org.idea.architect.framework.cache;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.cache.annotation.EnableCaching;

@SpringBootApplication
@EnableCaching
public class CacheApplication {
    public static void main(String[] args) {
        SpringApplication.run(CacheApplication.class, args);
    }
}

Cache configuration class:

package org.idea.architect.framework.cache.config;

import com.github.benmanes.caffeine.cache.CacheLoader;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration
public class CacheConfig {
    @Bean
    public CacheLoader
cacheLoader() {
        CacheLoader
cacheLoader = new CacheLoader
() {
            @Override
            public Object load(String s) throws Exception {
                return null;
            }
            @Override
            public Object reload(String key, Object oldValue) throws Exception {
                return oldValue;
            }
        };
        return cacheLoader;
    }
}

UserDao demonstrating cache usage and annotations:

package org.idea.architect.framework.cache.dao;

import com.github.benmanes.caffeine.cache.Cache;
import com.github.benmanes.caffeine.cache.Caffeine;
import org.springframework.cache.annotation.CacheEvict;
import org.springframework.cache.annotation.CachePut;
import org.springframework.cache.annotation.Cacheable;
import org.springframework.stereotype.Service;
import java.util.concurrent.TimeUnit;
import java.util.function.Function;

@Service
public class UserDao {
    private Cache
userCache = Caffeine.newBuilder()
        .maximumSize(10000)
        .expireAfterWrite(100, TimeUnit.SECONDS)
        .build();

    public User queryByUserIdV2(long userId) {
        userCache.get(userId, new Function
() {
            @Override
            public User apply(Long aLong) {
                System.out.println("用户本地缓存不存在，重新计算");
                return new User();
            }
        });
        return userCache.getIfPresent(userId);
    }

    public boolean insertUser(int userId) {
        User user = new User();
        user.setId(userId);
        user.setTel("11111");
        userCache.put((long) userId, user);
        return true;
    }

    @Cacheable(value = "userCache", key = "#userId", sync = true)
    public User queryByUserId(int userId) {
        System.out.println("从数据库查询userId");
        User user = new User();
        user.setId(1001);
        user.setTel("18971823123");
        user.setUsername("idea");
        return user;
    }

    @CachePut(value = "userCache", key = "#user.id")
    public void saveUser(User user) {
        System.out.println("插入数据库一条用户记录");
    }

    @CacheEvict(value = "userCache", key = "#userId")
    public void delUser(int userId) {
        System.out.println("删除用户本地缓存");
    }
}

User entity:

package org.idea.architect.framework.cache.dao;

public class User {
    private int id;
    private String username;
    private String tel;
    public int getId() { return id; }
    public void setId(int id) { this.id = id; }
    public String getUsername() { return username; }
    public void setUsername(String username) { this.username = username; }
    public String getTel() { return tel; }
    public void setTel(String tel) { this.tel = tel; }
    @Override
    public String toString() {
        return "User{" + "id=" + id + ", username='" + username + "', tel='" + tel + "'}";
    }
}

UserController exposing basic APIs:

package org.idea.architect.framework.cache.controller;

import org.idea.architect.framework.cache.dao.User;
import org.idea.architect.framework.cache.dao.UserDao;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;
import javax.annotation.Resource;
import java.util.UUID;
import java.util.concurrent.ThreadLocalRandom;

@RestController
public class UserController {
    @Resource
    private UserDao userDao;

    @GetMapping(value = "/queryUser")
    public String queryUser(int id) {
        User user = userDao.queryByUserId(id);
        return user.toString();
    }

    @GetMapping(value = "/insertUser")
    public String insertUser(int id) {
        User user = new User();
        user.setId(id);
        user.setUsername(UUID.randomUUID().toString());
        user.setTel(String.valueOf(ThreadLocalRandom.current().nextInt()));
        userDao.saveUser(user);
        return "success";
    }

    @GetMapping(value = "/delUser")
    public String delUser(int id) {
        userDao.delUser(id);
        return "delete-success";
    }

    @GetMapping(value = "/queryUser-02")
    public String queryUser_02(long userId) {
        User user = userDao.queryByUserIdV2(userId);
        return user.toString();
    }

    @GetMapping(value = "/insertUser-02")
    public String insertUser_02(int userId) {
        try {
            // custom logic
        } catch (Exception e) {
            e.printStackTrace();
        }
        userDao.insertUser(userId);
        return "success";
    }
}

Explanation of Caffeine annotations:

@Cacheable : Stores the method result in a local map; subsequent calls with the same key return the cached value without executing the method.

@CachePut : Always executes the method and updates the cache with the returned value; the sync attribute controls whether concurrent cache misses are synchronized.

@CacheEvict : Removes the cache entry identified by the given key.

Standalone Caffeine Manipulation Cases

Various ways to adjust key expiration strategies:

expireAfterAccess – expires after a specified number of seconds since last access.

expireAfterWrite – expires after a specified number of seconds since write.

expireAfter – custom Expiry implementation.

Example of expireAfterAccess:

public static void testCacheExpireAfterAccess() throws InterruptedException {
    Cache
cache = Caffeine.newBuilder()
        .maximumSize(1)
        .expireAfterAccess(1, TimeUnit.SECONDS)
        .build();
    cache.put("test", 1);
    System.out.println(cache.getIfPresent("test"));
    Thread.sleep(1000);
    System.out.println(cache.getIfPresent("test"));
}

Example of expireAfterWrite:

public static void testCacheExpireAfterWrite() throws InterruptedException {
    Cache
cache = Caffeine.newBuilder()
        .maximumSize(1)
        .expireAfterWrite(1, TimeUnit.SECONDS)
        .build();
    cache.put("test", 1);
    System.out.println(cache.getIfPresent("test"));
    Thread.sleep(1000);
    System.out.println(cache.getIfPresent("test"));
}

Example of custom Expiry implementation (expireAfter):

public static void testCacheExpireAfter() throws InterruptedException {
    long EXPIRE_TIME = 3;
    Cache
cache = Caffeine.newBuilder()
        .maximumSize(1)
        .expireAfter(new Expiry
() {
            @Override
            public long expireAfterCreate(String key, Integer value, long currentTime) {
                return TimeUnit.SECONDS.toNanos(EXPIRE_TIME);
            }
            @Override
            public long expireAfterUpdate(String key, Integer value, long currentTime, long currentDuration) {
                return TimeUnit.SECONDS.toNanos(EXPIRE_TIME);
            }
            @Override
            public long expireAfterRead(String key, Integer value, long currentTime, long currentDuration) {
                return TimeUnit.SECONDS.toNanos(EXPIRE_TIME);
            }
        })
        .build();
    cache.put("test", 1);
    System.out.println(TimeUnit.SECONDS.toNanos(EXPIRE_TIME));
    System.out.println(cache.getIfPresent("test"));
    Thread.sleep(2000);
    System.out.println(cache.getIfPresent("test"));
}

Removal listener example:

public static void testCacheEviction() throws InterruptedException {
    Cache
cache = Caffeine.newBuilder()
        .maximumSize(10)
        .removalListener(new RemovalListener
() {
            @Override
            public void onRemoval(String key, Integer value, RemovalCause cause) {
                System.out.println("remove key:" + key + ",value is:" + value);
            }
        })
        .build();
    cache.put("key1", 1001);
    cache.put("key2", 1002);
    cache.put("key3", 1003);
    cache.put("key4", 1004);
    System.out.println(cache.getIfPresent("key1"));
    System.out.println("移除单个key");
    cache.invalidate("key1");
    Thread.sleep(2000);
    System.out.println("移除所有key");
    cache.invalidateAll();
    System.out.println(cache.getIfPresent("key1"));
}

Cache hit‑rate statistics example:

public static void testCacheHitRate() throws InterruptedException {
    Cache
cache = Caffeine.newBuilder()
        .maximumSize(70)
        .recordStats()
        .build();
    for (int i = 0; i < 100; i++) {
        cache.put("item-" + i, i);
    }
    Thread.sleep(1000);
    for (int j = 0; j < 100; j++) {
        int i = new Random().nextInt(100);
        String key = "item-" + i;
        Integer result = cache.getIfPresent(key);
        if (result == null) {
            System.err.println("缓存key" + key + "不存在");
        }
    }
    long hitCount = cache.stats().hitCount();
    double hitRate = cache.stats().hitRate();
    long evictionCount = cache.stats().evictionCount();
    double averageLoadPenalty = cache.stats().averageLoadPenalty();
    System.out.println("命中率：" + hitRate + ",缓存总数：" + hitCount + ",缓存逐出个数:" + evictionCount + ",加载新数值花费的平均时间:" + averageLoadPenalty);
}

Compared with other cache components, Caffeine offers a compact, high‑performance solution worth trying.