Cache Penetration이란?
Cache Penetration은 존재하지 않는 데이터에 대한 요청이 캐시를 무력화시키는 현상이다.
일반적인 캐시 조회 흐름을 먼저 살펴보자.
이 흐름은 데이터가 존재하는 경우에는 잘 동작한다. Cache Miss가 발생해도 DB에서 조회한 결과를 캐시에 저장하므로, 이후 동일한 요청은 캐시에서 처리된다.
그런데 존재하지 않는 데이터를 요청하면 어떻게 될까?
DB 조회 결과가 null이면 캐시에 저장할 값이 없다. 따라서 같은 요청이 반복될 때마다 매번 캐시를 통과해서 DB에 직접 도달한다. 이것이 Cache Penetration이다.
왜 위험한가?
단순히 한두 건의 요청이라면 큰 문제가 아니다. 하지만 다음과 같은 상황을 생각해보자.
- 악의적인 사용자가 존재하지 않는 ID를 랜덤으로 대량 요청
- 삭제된 데이터에 대한 요청이 캐시 만료 후 반복 유입
- 아직 생성되지 않은 데이터에 대한 선행 요청
이 경우 캐시가 존재하는 의미가 없어지고, 모든 요청이 그대로 DB에 부하를 전가한다. 캐시의 존재 이유 자체가 무력화되는 것이다.
이 문제를 해결하기 위한 두 가지 접근 방식을 알아보자.
해결 방법 1: Null Object Pattern
개념
가장 직관적인 해결 방법이다. DB 조회 결과가 null이더라도, "비어있음"을 나타내는 객체를 캐시에 저장하는 것이다.
핵심은 null 대신 의미 있는 빈 객체를 캐시에 저장하는 것이다. 이후 동일한 요청이 들어오면 캐시에서 NullObject를 반환하고, DB 조회는 발생하지 않는다.
구현
@Service
@RequiredArgsConstructor
public class ProductCacheService {
private final ProductService productService;
// 데이터가 없음을 나타내는 Null Object 정의
private static final ProductResponse EMPTY = ProductResponse.empty();
@Cacheable(cacheNames = "product", key = "#productId")
public ProductResponse findById(Long productId) {
ProductResponse response = productService.findById(productId);
// DB 결과가 null이면 NullObject를 캐시에 저장
if (response == null) {
return EMPTY;
}
return response;
}
}@Cacheable은 메서드의 반환값을 캐시에 저장한다. DB 결과가 null이더라도 EMPTY를 반환하므로, 이 값이 캐시에 저장되어 이후 요청에서 DB 조회를 방지한다.
특징과 한계
Null Object Pattern은 존재하지 않는 키의 범위가 한정적일 때 효과적이다. 예를 들어 삭제된 게시글에 대한 캐시 방어처럼, 특정 키에 반복 요청이 집중되는 경우에 적합하다.
하지만 공격자가 매번 다른 랜덤 키로 요청을 보낸다면, 캐시에 무의미한 NullObject가 무한히 쌓이게 된다. 또한, Null Object를 반환받는 클라이언트 코드에서는 해당 객체가 실제 유효한 데이터인지 확인하는 로직이 필요할 수 있다. 이런 경우에는 요청이 DB에 도달하기 전에 차단하는 접근이 필요하다.
해결 방법 2: Bloom Filter
개념
Bloom Filter는 "이 데이터가 존재하는가?"를 확률적으로 판단하는 자료구조다.
핵심 특성은 다음과 같다:
- "없다"고 판단하면 확실히 없다 (False Negative 없음)
- "있다"고 판단해도 실제로는 없을 수 있다 (False Positive 가능)
이 특성을 활용하면, 존재하지 않는 데이터에 대한 요청을 DB에 도달하기 전에 차단할 수 있다.
Bloom Filter 내부 동작 원리
Bloom Filter는 비트 배열과 여러 개의 해시 함수로 구성된다.
데이터 추가
입력값을 여러 해시 함수에 통과시켜 나온 인덱스 위치의 비트를 1로 설정한다.
데이터 조회
조회 시 해당 인덱스의 비트가 모두 1이면 "있을 수 있음", 하나라도 0이면 "확실히 없음"으로 판단한다.
최적의 Bloom Filter 파라미터
Bloom Filter의 성능은 네 가지 파라미터에 의해 결정된다:
- n: 저장할 데이터 수
- p: 허용할 False Positive Rate (오차율)
- m: 비트 배열 크기 (n, p로부터 자동 계산)
- k: 해시 함수 수 (n, m으로부터 자동 계산)
비트 배열 크기 (m) = -(n × ln(p)) / (ln2)²
해시 함수 수 (k) = (m / n) × ln2예를 들어 데이터 1,000건에 오차율 1%를 허용하면:
- m ≈ 9,585 bits (약 1.2KB)
- k ≈ 7개의 해시 함수
매우 적은 메모리로 효과적인 필터링이 가능하다.
해시 함수 선택: Guava의 MurmurHash
Bloom Filter의 해시 함수는 빠르면서도 균일한 분포를 제공해야 한다. 암호학적 안전성은 필요 없으므로, 비암호학적 해시 함수가 적합하다.
여기서는 Google Guava 라이브러리가 제공하는 MurmurHash3를 사용한다. MurmurHash는 높은 처리 속도와 낮은 충돌률로 Bloom Filter에 널리 사용되는 해시 알고리즘이다.
(wikipedia murmurhash: https://en.wikipedia.org/wiki/MurmurHash)
k개의 해시 함수가 필요하지만, 실제로 k개의 서로 다른 해시 알고리즘을 구현할 필요는 없다. 같은 MurmurHash에 서로 다른 seed 값을 부여하면 독립적인 해시 함수처럼 동작한다. Hashing.murmur3_128(seed)에서 seed를 0, 1, 2, ...로 바꿔가며 k개의 함수를 생성한다.
구현
BloomFilter 클래스
public class BloomFilter {
private final String name;
private final long expectedSize; // 예상 데이터 수 (n)
private final double fpp; // 허용 오차율 (p)
private final long bitSize; // 비트 배열 크기 (m)
private final int hashCount; // 해시 함수 수 (k)
private final List<ToLongFunction<String>> hashFunctions;
private BloomFilter(String name, long expectedSize, double fpp) {
this.name = name;
this.expectedSize = expectedSize;
this.fpp = fpp;
this.bitSize = optimalBitSize(expectedSize, fpp);
this.hashCount = optimalHashCount(expectedSize, bitSize);
// seed를 달리한 murmur3_128로 k개의 독립적인 해시 함수 생성
this.hashFunctions = IntStream.range(0, hashCount)
.mapToObj(seed -> (ToLongFunction<String>) value ->
Math.abs(Hashing.murmur3_128(seed)
.hashString(value, UTF_8)
.asLong() % bitSize))
.toList();
}
public static BloomFilter of(String name, long expectedSize, double fpp) {
return new BloomFilter(name, expectedSize, fpp);
}
// -(n * ln(p)) / (ln2)^2
private static long optimalBitSize(long n, double p) {
return (long) Math.ceil(-(n * Math.log(p)) / Math.pow(Math.log(2), 2));
}
// (m / n) * ln2
private static int optimalHashCount(long n, long m) {
return (int) Math.ceil((m / (double) n) * Math.log(2));
}
public List<Long> computeHashIndexes(String value) {
return hashFunctions.stream()
.map(fn -> fn.applyAsLong(value))
.toList();
}
}Redis 기반 Bloom Filter Repository
Bloom Filter의 비트 배열을 Redis의 SETBIT / GETBIT 명령으로 관리한다.
@Component
@RequiredArgsConstructor
public class BloomFilterRepository {
private final StringRedisTemplate redis;
public void put(BloomFilter filter, String value) {
String key = resolveKey(filter);
List<Long> indexes = filter.computeHashIndexes(value);
redis.executePipelined((RedisCallback<?>) action -> {
StringRedisConnection conn = (StringRedisConnection) action;
indexes.forEach(idx -> conn.setBit(key, idx, true));
return null;
});
}
public boolean mightContain(BloomFilter filter, String value) {
String key = resolveKey(filter);
List<Long> indexes = filter.computeHashIndexes(value);
return redis.executePipelined((RedisCallback<?>) action -> {
StringRedisConnection conn = (StringRedisConnection) action;
indexes.forEach(idx -> conn.getBit(key, idx));
return null;
})
.stream()
.map(Boolean.class::cast)
.allMatch(Boolean.TRUE::equals);
}
private String resolveKey(BloomFilter filter) {
return "bf:" + filter.getName();
}
}파이프라이닝을 사용해 여러 비트 연산을 한 번의 네트워크 왕복으로 처리한다.
초기 메모리 할당
Redis에서 큰 비트 배열을 처음 사용할 때, 한 번에 메모리를 할당하면 싱글 스레드 특성상 블로킹이 발생할 수 있다.
(redis 공식 문서: https://redis.io/docs/latest/commands/setbit/)
이를 방지하기 위해 일정 단위(예: 8MB)씩 점진적으로 메모리를 확보하는 init 과정을 거친다.
public void warmUp(BloomFilter filter) {
String key = resolveKey(filter);
long step = 8L * 1024 * 1024 * 8; // 8MB 단위
for (long offset = 0; offset < filter.getBitSize(); offset += step) {
redis.opsForValue().setBit(key, offset, false);
}
}setBit은 해당 오프셋까지의 메모리를 자동으로 확장한다. 한 번에 전체 크기를 할당하는 대신 8MB씩 나눠서 호출하면, 각 호출 사이에 다른 Redis 명령이 처리될 여지를 남겨둘 수 있다. Bloom Filter를 활성화하기 전에 관리 도구 등에서 미리 수행해두면 운영 중 블로킹을 예방할 수 있다.
캐시 서비스에서의 활용
@Service
@RequiredArgsConstructor
public class ProductBloomFilterService {
private final ProductService productService;
private final BloomFilterRepository bloomFilterRepository;
private static final BloomFilter FILTER = BloomFilter.of("product", 10_000, 0.01);
public ProductResponse findById(Long productId) {
// Bloom Filter에 없으면 확실히 존재하지 않는 데이터
if (!bloomFilterRepository.mightContain(FILTER, String.valueOf(productId))) {
return null;
}
// Bloom Filter를 통과하면 실제 조회 수행
return productService.findById(productId);
}
public ProductResponse register(ProductCreateRequest request) {
ProductResponse response = productService.register(request);
// 데이터 생성 시 Bloom Filter에 등록
bloomFilterRepository.put(FILTER, String.valueOf(response.id()));
return response;
}
}Bloom Filter의 한계
위 그래프를 보면 n이 커질수록 오차율 (p) 가 급격하게 1에 가까워지는 것을 알 수 있다.
이 한계들을 단계적으로 해결해보자.
개선 1: Split Bloom Filter — 비트 배열 분할
처음부터 데이터 수용 크기를 크게 잡기
문제
Redis의 String 타입은 최대 512MB다. 대량의 데이터를 다루는 Bloom Filter는 이 제한을 초과할 수 있다. 또한 하나의 거대한 키에 모든 비트를 저장하면, 초기 메모리 할당 시 Redis가 블로킹될 수 있다.
해결: 비트 배열을 여러 키로 분할
하나의 큰 비트 배열을 일정 단위로 잘라서 여러 개의 Redis 키에 분산 저장한다.
예를 들어 분할 단위가 1024비트라면, 해시 결과 인덱스 2500은 split:2 키의 2500 % 1024 = 452 오프셋에 매핑된다.
구현
SplitBloomFilter 클래스
public class SplitBloomFilter {
private final BloomFilter bloomFilter;
private final long chunkCount;
private static final long CHUNK_SIZE = 1L << 32; // 분할 단위
public SplitBloomFilter(String name, long expectedSize, double fpp) {
this.bloomFilter = BloomFilter.of(name, expectedSize, fpp);
this.chunkCount = (bloomFilter.getBitSize() - 1) / CHUNK_SIZE + 1;
}
// 해시 인덱스가 어느 분할에 속하는지 계산
public long resolveChunkIndex(long hashedIndex) {
return hashedIndex / CHUNK_SIZE;
}
// 분할 내 상대적 오프셋 계산
public long resolveOffset(long hashedIndex) {
return hashedIndex % CHUNK_SIZE;
}
}SplitBloomFilter Redis Repository
@Component
@RequiredArgsConstructor
public class SplitBloomFilterRepository {
private final StringRedisTemplate redis;
public void put(SplitBloomFilter filter, String value) {
redis.executePipelined((RedisCallback<?>) action -> {
StringRedisConnection conn = (StringRedisConnection) action;
for (Long hashedIndex : filter.getBloomFilter().computeHashIndexes(value)) {
long chunkIdx = filter.resolveChunkIndex(hashedIndex);
long offset = filter.resolveOffset(hashedIndex);
conn.setBit(toKey(filter, chunkIdx), offset, true);
}
return null;
});
}
public boolean mightContain(SplitBloomFilter filter, String value) {
return redis.executePipelined((RedisCallback<?>) action -> {
StringRedisConnection conn = (StringRedisConnection) action;
for (Long hashedIndex : filter.getBloomFilter().computeHashIndexes(value)) {
long chunkIdx = filter.resolveChunkIndex(hashedIndex);
long offset = filter.resolveOffset(hashedIndex);
conn.getBit(toKey(filter, chunkIdx), offset);
}
return null;
})
.stream()
.map(Boolean.class::cast)
.allMatch(Boolean.TRUE::equals);
}
private String toKey(SplitBloomFilter filter, long chunkIndex) {
return "sbf:%s:chunk:%d".formatted(filter.getName(), chunkIndex);
}
}Split Bloom Filter의 한계
비트 배열 분할로 Redis 단일 키 크기 제한은 해결했다. 하지만 모든 분할 키가 여전히 하나의 Redis 인스턴스에 존재한다면, 그 인스턴스가 단일 장애점(SPOF)이 된다. 또한 모든 읽기/쓰기 트래픽이 한 노드에 집중되므로 처리량에도 한계가 있다.
이 문제를 해결하기 위해 샤딩(Sharding)을 결합한다.
Split Bloom Filter + 샤딩
샤딩은 데이터를 여러 독립적인 필터로 분산시키는 기법이다. 입력값을 해싱하여 어떤 샤드(필터)에 속하는지 결정하고, 해당 샤드에서만 연산을 수행한다.
각 샤드는 독립적인 SplitBloomFilter다. 입력값을 해싱하여 어떤 샤드에서 연산할지 결정하므로, 하나의 값은 항상 같은 샤드에 매핑된다.
샤드 라우팅에도 Guava의 MurmurHash를 사용한다. 비트 배열 인덱싱에는 128비트 버전(murmur3_128)을, 샤드 결정에는 32비트 버전(murmur3_32)을 사용한다. 샤드 라우팅은 샤드 수(보통 한 자릿수)로 나누는 단순한 연산이므로 32비트로 충분하다.
ShardedBloomFilter 클래스
public class ShardedBloomFilter {
private final List<SplitBloomFilter> shards;
private final int shardCount;
public ShardedBloomFilter(String name, long expectedSize, double fpp, int shardCount) {
this.shardCount = shardCount;
// 데이터를 샤드 수만큼 균등 분배
long perShard = expectedSize / shardCount;
long remainder = expectedSize % shardCount;
this.shards = IntStream.range(0, shardCount)
.mapToObj(i -> new SplitBloomFilter(
name + ":shard:" + i,
perShard + (i < remainder ? 1 : 0),
fpp
))
.toList();
}
// 입력값의 해시로 샤드 결정 (Guava의 murmur3_32 사용)
public SplitBloomFilter routeShard(String value) {
int index = Math.abs(
Hashing.murmur3_32_fixed()
.hashString(value, UTF_8)
.asInt() % shardCount
);
return shards.get(index);
}
}ShardedBloomFilter Repository
샤딩 저장소는 기존 SplitBloomFilterRepository에 위임하는 구조다. 샤드를 찾아서 기존 로직에 넘기기만 하면 되므로, 분할 로직을 중복 구현할 필요가 없다.
@Component
@RequiredArgsConstructor
public class ShardedBloomFilterRepository {
// 기존 SplitBloomFilter 저장소를 재사용
private final SplitBloomFilterRepository splitRepository;
public void warmUp(ShardedBloomFilter shardedFilter) {
shardedFilter.getShards().forEach(splitRepository::warmUp);
}
public void put(ShardedBloomFilter shardedFilter, String value) {
SplitBloomFilter target = shardedFilter.routeShard(value);
splitRepository.put(target, value);
}
public boolean mightContain(ShardedBloomFilter shardedFilter, String value) {
SplitBloomFilter target = shardedFilter.routeShard(value);
return splitRepository.mightContain(target, value);
}
}routeShard로 대상 샤드를 결정한 뒤, 실제 비트 연산은 SplitBloomFilterRepository가 처리한다. 각 계층이 자신의 책임만 갖는 구조다.
샤딩의 이점
| 관점 | 단일 필터 | 샤딩 적용 |
| 메모리 분산 | 하나의 Redis 인스턴스에 집중 | 여러 인스턴스에 분산 가능 |
| 처리량 | 단일 인스턴스 성능에 제한 | 샤드 수만큼 병렬 처리 가능 |
| 장애 영향 | 전체 필터 사용 불가 | 해당 샤드만 영향 |
| 확장성 | 수직 확장만 가능 | 샤드 추가로 수평 확장 |
Redis Cluster 환경에서 각 샤드의 키가 서로 다른 해시 슬롯에 분배되면, 자연스럽게 여러 노드에 분산된다.
Split + Sharding의 한계
분할과 샤딩으로 확장성 문제는 해결했지만, 근본적인 문제가 하나 남아있다.
Bloom Filter는 생성 시점에 용량(dataCount)이 고정된다. 데이터가 예상을 초과하면 오차율이 급격히 증가하고, 필터의 의미가 사라진다. 그렇다고 처음부터 지나치게 큰 용량을 잡으면 메모리 낭비다.
개선 2: Sub Bloom Filter — 동적 확장
아이디어
용량이 가득 차면, 기존 필터는 그대로 두고 더 큰 새로운 필터를 추가한다.
각 Sub Filter는 이전보다 2배 큰 용량과 절반의 오차율로 생성된다. 쓰기는 항상 가장 최근(활성) 필터에만 수행하고, 읽기는 모든 필터를 확인한다.
오차율을 절반으로 줄이는 이유는 전체 오차율의 누적을 억제하기 위해서다. 조회 시 모든 필터를 순회하므로, 각 필터의 False Positive가 합산된다. 필터가 추가될수록 개별 오차율을 줄여야 전체 시스템의 오차율이 발산하지 않는다. p, p/2, p/4, ...로 설정하면 전체 오차율의 상한은 p + p/2 + p/4 + ... = 2p로 수렴한다.
조회 흐름
어느 시점에 추가된 데이터인지 모르므로, 모든 필터를 순회하며 하나라도 "있을 수 있음"이면 존재 가능성이 있다고 판단한다.
구현
ScalableBloomFilter
public class ScalableBloomFilter {
private final String name;
private final ShardedBloomFilter baseFilter;
public ScalableBloomFilter(String name, long expectedSize, double fpp, int shardCount) {
this.name = name;
this.baseFilter = new ShardedBloomFilter(name, expectedSize, fpp, shardCount);
}
// Sub Filter 생성: 용량 2배, 오차율 절반씩 스케일
public ShardedBloomFilter growFilter(int generation) {
return new ShardedBloomFilter(
name + ":gen:" + generation,
baseFilter.getExpectedSize() * (1L << (generation + 1)),
baseFilter.getFpp() / (1L << (generation + 1)),
baseFilter.getShardCount()
);
}
// 현재 활성화된 (쓰기 대상) 필터 반환
public ShardedBloomFilter activeFilter(int generationCount) {
if (generationCount == 0) {
return baseFilter;
}
return growFilter(generationCount - 1);
}
// 조회 시 모든 필터 목록 반환 (base + 모든 generation)
public List<ShardedBloomFilter> allFilters(int generationCount) {
List<ShardedBloomFilter> filters = new ArrayList<>();
filters.add(baseFilter);
for (int i = 0; i < generationCount; i++) {
filters.add(growFilter(i));
}
return filters;
}
}ScalableBloomFilter Repository
@Component
@RequiredArgsConstructor
public class ScalableBloomFilterRepository {
private final StringRedisTemplate redis;
private final DistributedLockProvider lockProvider;
private final ShardedBloomFilterRepository shardedRepository;
private static final int MAX_GENERATIONS = 2;
public void put(ScalableBloomFilter scalable, String value) {
int genCount = currentGeneration(scalable);
ShardedBloomFilter active = scalable.activeFilter(genCount);
// 활성 필터에 데이터 추가
shardedRepository.put(active, value);
// 데이터 수 증가 후 용량 초과 여부 확인
Long count = redis.opsForValue().increment(dataCountKey(active));
growIfNeeded(scalable, active, count);
}
private void growIfNeeded(ScalableBloomFilter scalable, ShardedBloomFilter active, Long count) {
if (count == null || active.getExpectedSize() > count) {
return;
}
// 분산 락으로 동시 확장 방지
String lockKey = "scalable-bf:grow-lock:" + scalable.getName();
if (!lockProvider.lock(lockKey, Duration.ofMinutes(1))) {
return;
}
try {
int genCount = currentGeneration(scalable);
if (genCount >= MAX_GENERATIONS) {
log.warn("필터 최대 세대 도달. name={}, gen={}", scalable.getName(), genCount);
return;
}
// 새 세대 필터 초기화 후 세대 카운트 증가
shardedRepository.warmUp(scalable.growFilter(genCount));
redis.opsForValue().increment(generationKey(scalable));
} finally {
lockProvider.unlock(lockKey);
}
}
public boolean mightContain(ScalableBloomFilter scalable, String value) {
int genCount = currentGeneration(scalable);
// 모든 세대를 순회하며 하나라도 true면 "있을 수 있음"
return scalable.allFilters(genCount).stream()
.anyMatch(filter -> shardedRepository.mightContain(filter, value));
}
// ...
}Sub Bloom Filter의 주의점
정리
| 방법 | Cache Penetration 방어 |
메모리 효율 | 구현 복잡도 | 적합한 상황 |
| Null Object Pattern | O | 낮음 (키당 객체 저장) | 낮음 | 비정상 키 범위가 한정적일 때 |
| Bloom Filter | O | 높음 (비트 배열) | 중간 | 대량 데이터, 고정 용량 |
| Split Bloom Filter + Sharding | O | 높음 | 높음 | 대규모 분산 환경 |
| Sub Bloom Filter | O | 높음 | 매우 높음 | 데이터가 지속적으로 증가하는 환경 |
Cache Penetration은 캐시 시스템에서 흔히 간과되는 문제다. 단순히 "캐시에 없으면 DB에서 조회"하는 전략만으로는 존재하지 않는 데이터에 대한 반복 요청을 막을 수 없다.
Null Object Pattern은 간단하지만 메모리 효율이 떨어지고, Bloom Filter는 메모리 효율이 뛰어나지만 용량 제한과 확장성에 대한 고민이 필요하다. Split, Sharding, Sub Filter로 점진적으로 개선해 나가며, 서비스의 규모와 데이터 특성에 맞는 적절한 수준의 해결책을 선택하면 된다.
'데이터베이스 > Redis' 카테고리의 다른 글
| [Redis] Cache Stampede: 캐시가 만료되는 순간, 모든 요청이 DB로 몰린다면 (0) | 2026.02.18 |
|---|---|
| Redis란? (1) | 2025.01.02 |
