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 ProductRepository productRepository;

	public List<Product> getPopularProducts(){
		String popularProductsJson = redis.opsForValue().get(PRODUCT_POPULAR_KEY);
		if(popularProductsJson != null){
			TypeReference<List<Product>> productListTypeReference = new TypeReference<>(){};
			return objectMapper.readValue(popularProductsJson, productListTypeReference);
		}
		List<Product> products = productRepository.findPopularProducts();
		String productsJson = objectMapper.writeValueAsString(products);
		Duration expirationTime = Duration.of(6, ChronoUnit.HOURS);
		redis.opsForValue().set(PRODUCT_POPULAR_KEY, productsJson, expirationTime);
		return 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. 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.

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

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

	private final StringRedisTemplate redis;
	private final ObjectMapper objectMapper;
	private final ProductRepository productRepository;

	public List<Product> getPopularProducts(){
		String popularProductsJson = redis.opsForValue().get(PRODUCT_POPULAR_KEY);
		if(popularProductsJson == null){
			return getMutexPopularProducts();
		}
		return getCachedPopularProducts(popularProductsJson);
	}

	private List<Product> getCachedPopularProducts(String popularProductsJson){
		TypeReference<CacheWrapper<List<Product>>> reference = new TypeReference<>(){};
		CacheWrapper<List<Product>> wrapper = objectMapper.readValue(popularProductsJson, reference);
		if(System.currentTimeMillis() > wrapper.softExpirationTime()){
			revalidateCache();
		}
		log.info("Returning popular products from cache");
		return wrapper.data();
	}

	private void revalidateCache(){
		Boolean acquired = redis.opsForValue().setIfAbsent(
				PRODUCT_POPULAR_LOCK_KEY, PRODUCT_POPULAR_LOCK_KEY, Duration.ofSeconds(30)
		);
		if(Boolean.TRUE.equals(acquired)){
			CompletableFuture.runAsync(() -> {
				try{
					log.info("Revalidating popular products from database");
					fetchAndCachePopularProductsFromDb();
				} finally{
					redis.delete(PRODUCT_POPULAR_LOCK_KEY);
				}
			});
		} else {
			log.info("Already revalidate popular products cache");
		}
	}

	@SneakyThrows
	private List<Product> getMutexPopularProducts(){
		int retry = 0;
		while(retry < 10){
			String popularProductsJson = redis.opsForValue().get(PRODUCT_POPULAR_KEY);
			if(popularProductsJson != null){
				log.info("Returning popular products from cache after retry");
				TypeReference<CacheWrapper<List<Product>>> reference = new TypeReference<>(){};
				return objectMapper.readValue(popularProductsJson, reference).data();
			}
			Boolean acquired = redis.opsForValue().setIfAbsent(
					PRODUCT_POPULAR_LOCK_KEY, PRODUCT_POPULAR_LOCK_KEY, Duration.ofSeconds(30)
			);
			if(Boolean.TRUE.equals(acquired)){
				try{
					log.info("Obtained lock for popular products");
					return fetchAndCachePopularProductsFromDb();
				} finally{
					redis.delete(PRODUCT_POPULAR_LOCK_KEY);
				}
			}
			TimeUnit.SECONDS.sleep(1);
			retry++;
			log.info("Failed to obtain lock for popular products. Retrying...");
		}
		throw new RuntimeException("Failed to get popular products");
	}

	private List<Product> fetchAndCachePopularProductsFromDb(){
		List<Product> popularProducts = productRepository.findPopularProducts();
		int jitter = ThreadLocalRandom.current().nextInt(1, 900);
		Duration hardExpirationTime = Duration.of(6, ChronoUnit.HOURS).plusSeconds(jitter);
		Instant softExpirationTime = Instant.now().plus(hardExpirationTime).minusSeconds(60);
		CacheWrapper<List<Product>> wrapper = new CacheWrapper<>(popularProducts, softExpirationTime.toEpochMilli());
		String popularProductsJson = objectMapper.writeValueAsString(wrapper);
		redis.opsForValue().set(PRODUCT_POPULAR_KEY, popularProductsJson, hardExpirationTime);
		return products;
	}

}

Saat diakses kita perlu cek ke cache dulu. Jika ga ada, maka kita akan ambil data dari database secara Mutex dengan bikin 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 1 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, sisanya nunggu selama 1 detik lalu retry. Saat retry cek dulu ke cache apakah udah ada atau belum. 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 error.

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 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. Kita bisa mengatasinya dengan memastikan hanya ada satu request yang boleh melakukan eksekusi. Kita perlu menambahkan angka random pada waktu expire agar 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 jadi lebih halus😎.