Cache Stampede: Ketika Cache Gagal dan System Diseruduk Beramai-ramai

Mendapatkan data yang butuh komputasi yang berat atau melibatkan query yang kompleks dapat membuat system jadi lambat. Permasalahan itu bisa diatasi dengan cache agar data yang pernah didapat disimpan di memori dalam jangka waktu tertentu. Namun, saat cache expired semua request yang masuk harus melakukan komputasi lagi berbarengan sehingga bisa membuat server jebol. Inilah yang disebut dengan Cache Stampede Problem🦬.

Contoh Kasus

Misalnya kita bikin aplikasi yang ada fitur untuk menampilkan data seperti produk populer, produk rekomendasi, analitik penjualan harian, dan sejenisnya. Fitur tersebut sering diakses user beramai-ramai dan querynya cukup kompleks, sedangkan datanya jarang berubah secara real-time. Solusinya adalah kita cache hasil dari data sebelumnya sehingga request selanjutnya ga perlu komputasi atau query lagi selama beberapa saat.

@RequiredArgsConstructor
public class PopularProductUseCase{
	public static final String PRODUCT_POPULAR_KEY = "product:popular";

	private final StringRedisTemplate redis;
	private final ObjectMapper objectMapper;
	private final ProductGateway gateway;

	public void execute(PopularProductRequest request, PopularProductPresenter presenter){
		String json = redis.opsForValue().get(PRODUCT_POPULAR_KEY);
		if(json != null){
			TypeReference<List<Product>> reference = new TypeReference<>(){};
			presenter.present(objectMapper.readValue(json, reference));
			return;
		}
		List<Product> products = gateway.findPopularProducts(request.limit());
		String productsJson = objectMapper.writeValueAsString(products);
		Duration expirationTime = Duration.of(6, ChronoUnit.HOURS);
		redis.opsForValue().set(PRODUCT_POPULAR_KEY, productsJson, expirationTime);
		presenter.present(products);
	}
}

Pada code di atas gw menggunakan Spring Redis sebagai cache dan Jackson Object Mapper untuk serialization. Fitur produk populer gw cache selama 6 jam. Kalau ga ada di cache, maka akan query ke database. Misalkan untuk fitur-fitur lainnya seperti produk rekomendasi, analitik penjualan harian, dan sebagainya juga kurang lebih sama flownya seperti di atas.

Masalah

Saat aplikasi pertama kali jalan, user berbondong-bondong mengakses fitur-fitur tersebut. Saat itu cache belum tersimpan karena itu request pertama. Ini bisa bikin system jadi berat. Setelahnya, karena udah ada cache mungkin akan aman dan lebih cepat. 6 jam kemudian ketika semua cache expired, system kembali jadi berat saat diakses beramai-ramai🦬. Ini akan berulang terus-terusan tiap 6 jam sekali😱. Untuk mengatasinya ada beberapa hal yang perlu dilakukan seperti Mutex, SWR, dan Jitter.

Mutex

Mutex artinya saat diakses bersamaan hanya 1 request yang boleh masuk, sisanya harus ngantri. Kita bisa menggunakan Distributed Lock untuk hal ini. Misalkan ada 10 request yang masuk bersamaan, hanya 1 yang boleh eksekusi. 9 sisanya ditahan dan coba lagi nanti⛔. 1 request yang masuk itu akan melakukan eksekusi dan cache. Setelah itu 9 request sisanya akan mengambil data dari cache tanpa perlu eksekusi.

SWR (Stale While Revalidate)

Stale While Revalidate artinya saat expired kita masih memberikan data yang lama, tapi di background process kita akan melakukan revalidasi cache dengan data terbaru🥷. Jadi di sini kita butuh 2 properti expiration: Hard Expiration Time untuk expiration di Redis, dan Soft Expiration Time untuk expiration di logic. Misalnya kita ingin data tersebut expire dalam waktu 6 jam, ini jadi Hard Expiration Time. 1 menit sebelum expire kita perlu melakukan revalidasi di background process, ini jadi Soft Expiration Time. Jika ada request yang masuk selama revalidasi, maka data yang ditampilkan masih dari data cache yang lama selama Hard Expiration Time dari Redis belum lewat.

Jitter

Jitter adalah nilai random yang ditambahkan pada waktu expire agar masing-masing waktu expire di tiap fitur berbeda-beda🕰️. Misalkan pada fitur produk populer, produk rekomendasi, analitik penjualan harian, dan sejenisnya kita ingin semuanya expire setelah 6 jam. Kita harus atur agar expirenya ga serentak banget 6 jam di detik yang sama. Waktu expirenya perlu kita tambahin beberapa detik secara random untuk menghindari ini.

Contoh Code

Kita butuh wrapper untuk membungkus data yang mau di-cache dengan properti soft expiration time untuk revalidate nanti. Untuk handle cache kita pisah ke CacheHandler biar generic dan bisa di-reuse. Di use case kita perlu bungkus method yang hasil eksekusinya perlu di-cache ke dalam lambda function Callable agar method tersebut bisa dioper ke CacheHandler.

public record CacheWrapper<T>(T data, long softExpirationTime){
}

@Slf4j
@RequiredArgsConstructor
public class CacheHandler{
	public static final String LOCK_KEY = "lock:";

	private final StringRedisTemplate redis;
	private final ObjectMapper objectMapper;

	public <T> List<T> handleList(Callable<List<T>> function, String key, Class<T> dataClass){
		String json = redis.opsForValue().get(key);
		JavaType listType = objectMapper.getTypeFactory()
				.constructParametricType(List.class, dataClass);
		if(json == null){
			return getMutex(function, key, listType);
		}
		return getCached(json, function, key, listType);
	}

	public <T> T handle(Callable<T> function, String key, Class<T> dataClass){
		String json = redis.opsForValue().get(key);
		JavaType javaType = objectMapper.getTypeFactory()
				.constructType(dataClass);
		if(json == null){
			return getMutex(function, key, javaType);
		}
		return getCached(json, function, key, javaType);
	}

	private <T> T getCached(String json, Callable<T> function, String key, JavaType javaType){
		JavaType wrapperType = objectMapper.getTypeFactory()
				.constructParametricType(CacheWrapper.class, javaType);
		CacheWrapper<T> wrapper = objectMapper.readValue(json, wrapperType);
		if(System.currentTimeMillis() > wrapper.softExpirationTime()){
			revalidate(function, key);
		}
		log.info("Returning data from cache");
		return wrapper.data();
	}

	private <T> void revalidate(Callable<T> function, String key){
		Boolean acquired = redis.opsForValue().setIfAbsent(
				LOCK_KEY + key, LOCK_KEY, Duration.ofSeconds(30)
		);
		if(Boolean.TRUE.equals(acquired)){
			CompletableFuture.runAsync(() -> {
				try{
					log.info("Revalidating from database");
					fetchAndCacheFromDb(function, key);
				} finally{
					redis.delete(LOCK_KEY + key);
				}
			});
		} else {
			log.info("Already revalidates cache");
		}
	}

	@SneakyThrows
	private <T> T getMutex(Callable<T> function, String key, JavaType javaType){
		int retry = 0;
		while(retry < 10){
			String json = redis.opsForValue().get(key);
			if(json != null){
				log.info("Returning from cache after retry");
				JavaType wrapperType = objectMapper.getTypeFactory()
						.constructParametricType(CacheWrapper.class, javaType);
				CacheWrapper<T> wrapper = objectMapper.readValue(json, wrapperType);
				return wrapper.data();
			}
			Boolean acquired = redis.opsForValue().setIfAbsent(
					LOCK_KEY + key, LOCK_KEY, Duration.ofSeconds(30)
			);
			if(Boolean.TRUE.equals(acquired)){
				try{
					log.info("Obtained lock");
					return fetchAndCacheFromDb(function, key);
				} finally{
					redis.delete(LOCK_KEY + key);
				}
			}
			TimeUnit.SECONDS.sleep(1);
			retry++;
			log.info("Failed to obtain lock. Retrying...");
		}
		throw new RuntimeException("Failed to get data");
	}

	@SneakyThrows
	private <T> T fetchAndCacheFromDb(Callable<T> function, String key){
		T data = function.call();
		int jitter = ThreadLocalRandom.current().nextInt(0, 900);
		Duration hardExpirationTime = Duration.of(6, ChronoUnit.HOURS).plusSeconds(jitter);
		Instant softExpirationTime = Instant.now().plus(hardExpirationTime).minusSeconds(60);
		CacheWrapper<T> wrapper = new CacheWrapper<>(data, softExpirationTime.toEpochMilli());
		String json = objectMapper.writeValueAsString(wrapper);
		redis.opsForValue().set(key, json, hardExpirationTime);
		return data;
	}
}

@RequiredArgsConstructor
public class PopularProductUseCase{
	public static final String PRODUCT_POPULAR_KEY = "product:popular";

	private final CacheHandler cacheHandler;
	private final PopularProductGateway gateway;

	public void execute(PopularProductRequest request, PopularProductPresenter presenter){
		Callable<List<Product>> function = () -> gateway.findPopularProducts(request.limit());
		List<Product> result = cacheHandler.handleList(function, PRODUCT_POPULAR_KEY, Product.class);
		presenter.present(result);
	}
}

Saat diakses kita perlu cek ke cache dulu. Jika ga ada, maka kita akan ambil data dari database secara Mutex dengan bikin key lock pake Redis, fetch & cache data dari database, lalu unlock dengan menghapus key lock di Redis. Saat cache di sini gw generate angka random dari 0 sampai 900 detik untuk Jitter (sekitar 0-15 menit). Jadi, Hard Expiration Time untuk Redis adalah 6 jam + angka random sekian detik. Cache perlu dibungkus dengan CacheWrapper untuk menyimpan Soft Expiration Time dengan waktu expire 60 detik sebelum Hard Expiration Time.

Jika lebih dari satu request yang masuk, maka hanya satu yang bisa fetch & cache karena udah dikunci pake key lock sebelumnya, sisanya nunggu selama 1 detik lalu retry. Saat retry cek dulu ke cache apakah udah ada atau belum. Jika ada maka return data dari cache. Jika masih ga ada maka nunggu lagi 1 detik. Kemudian retry seperti sebelumnya. Begitu seterusnya hingga maksimal 10 kali. Jika udah 10 kali maka tampilkan error, artinya ada masalah lain yang terjadi. Kita batasi retry 10 kali biar ga retry terus-terusan saat ada masalah.

Jika saat diakses ada di cache, maka kita cek dulu Soft Expiration Time datanya. Jika Soft Expiration Time belum lewat, maka langsung kembalikan data dari cache. Jika sudah lewat, maka tetap kembalikan data lama dari cache lalu revalidate cache secara asynchronous dengan cara bikin lock pake Redis, fetch data ke database & cache data terbaru, lalu unlock dengan menghapus key lock di Redis. Lock dibutuhkan agar hanya ada satu request aja yang melakukan revalidasi. Request lainnya akan skip dan langsung kembalikan data dari cache.

Verdict

Cache Stampede adalah situasi ketika cache sedang kosong atau sudah expired, lalu datang banyak request yang mencoba mendapatkan data dalam waktu yang sama sehingga dapat memberatkan system. Ini bagian dari Thundering Herd Problem dan dikenal juga dengan istilah Dogpile Effect. Kita bisa mengatasinya dengan memastikan hanya ada satu request yang boleh melakukan eksekusi. Kita perlu menambahkan angka random pada waktu expire agar semua cache ga expire serentak di detik yang sama. Kita juga perlu membuat logic Soft Expiration Time agar data cache bisa diperbarui sebelum data tersebut benar-benar expire dari cache dan performa aplikasi saat pembaruan cache lebih halus😎.