[개발자를 위한 레디스] 캐시 스탬피드 현상

문제 설명

• 캐시를 사용하는 경우, 만료 시간을 설정하는 것이 필수적이다.
• 모든 키에 대해 만료 시간을 동일하게 설정하는 경우, 대규모 트래픽 환경에서 캐시 스탬피드(cache stampede) 현상이 발생가능함.
• 많은 요청이 동시에 캐시 만료를 인식하고, DB 에 접근하여 서버에 과부하를 일으키는 상황이 발생한다.

발생 원인

• 애플리케이션이 look-aside 방식을 사용하여 키를 관리

  Look-Aside

  • 캐시에서 데이터를 먼저 찾고, 없으면 DB에서 찾는다.
  • DB 에서 찾은 데이터를 캐시에 삽입하는 과정도 수행된다.

  
  하는 경우, 캐시된 데이터가 만료되는 경우 어플은 DB에 접근하여 데이터를 가져와서 캐시에 다시 저장한다.
  여러 어플이 동시에 특정 키가 만료되었음을 인지하는 경우, 동시에 DB에 접근하여 데이터를 가져오려고 시도한다.
  → DB 과부하가 발생함.

문제상황

1. 어플리케이션 1과 2 동시에 캐시된 키가 만료됨 인지
2. 동시에 DB 접근하여 데이터를 조회
   1. 만약 메인페이지의 호출이라면 대략 1초당 몇백 ~ 몇천개의 IO 가 발생가능.(동기화시까지)
   2. DB 서버가 죽어버리는 위험성도 있음
3. DB 부하가 발생하고, 서비스 성능 저하

해결방안

1. 적절한 만료 시간 설정

   • 만료 시간을 너무 짧게 설정 x
   • 데이터 특성에 맞춰 설정

2. 선 계산

   • 키가 만료되기 전에 미리 값을 갱신

3. 확률적 접근

   • 만료 시간이 가까워질수록 확률적으로 DB에 접근해 데이터를 갱신

   import java.util.Random;
   
   public class Cache {
       private static final int BASE_EXPIRATION_TIME = 300; // 기본 만료 시간 (초)
       private static final int RANDOMIZATION_RANGE = 60; // 랜덤화 범위 (초)
       private Random random = new Random();
   
       public int getExpirationTime() {
           return BASE_EXPIRATION_TIME + random.nextInt(RANDOMIZATION_RANGE);
       }
   }

   • ttl (캐시의 남은 시간) - 랜덤 값 ⇒ 남은 시간이 0 보다 큰 경우 캐시의 남은 시간이 랜덤 값보다 크기에, 캐시가 아직 유효하다고 판단됨.
     • 해당 유효건의 경우 패스,
     • 만약 그 시간보다 짧다고 판단되는 경우, 캐시 갱신을 해준다.

4. PER 알고리즘

   import java.util.Random;
   
   public class Cache {
       private static final int EXPIRATION_TIME = 300; // 기본 만료 시간 (초)
       private static final double RECOMPUTE_PROBABILITY = 0.1; // 재계산 확률
       private long lastUpdateTime;
       private Random random = new Random();
   
       public Cache() {
           this.lastUpdateTime = System.currentTimeMillis();
       }
   
       public boolean shouldRecompute() {
           long currentTime = System.currentTimeMillis();
           long elapsedTime = (currentTime - lastUpdateTime) / 1000; // 경과 시간 (초)
   
           if (elapsedTime >= EXPIRATION_TIME) {
               return true; // 만료 시간 경과
           }
   
           double probability = RECOMPUTE_PROBABILITY * (elapsedTime / (double) EXPIRATION_TIME);
           return random.nextDouble() < probability;
       }
   
       public void updateCache() {
           // 캐시 갱신 로직
           this.lastUpdateTime = System.currentTimeMillis();
       }
   }

• 확률적 조기 재계산(Probabilistic Early Recompilation) 알고리즘 사용
• 주요 사항
  1. randValue : 0 과 1 사이의 랜덤값을 설정
  2. BETA : 조정 가능한 상수로, 로그 값에 곱해주는 값이다.
  3. ttl - (BETA * Math.log(randValue) * EXPIRY_GAP)
     • 캐시의 남은 만료 시간에 랜덤 값을 조정해 뺀 값을 계산하고, 해당 값이 0보다 크다면, 캐시가 유효하다고 판단함

이전의 3번과 뭐가 다른건데?

• PER 알고리즘과 확률적 접근의 차이점
  1. 차이점
     • 확률적 접근
       1. 방법적
          1. 캐시 만료 시간을 랜덤하게 설정함
       2. 작동 방식
          1. 캐시 만료 시간이 일정 범위 내에서 무작위로 설정됨
       3. 기본 만료 시간이 5분이라면, 실제 만료 시간은 5분에서 6분 사이의 랜덤한 시간으로 설정된다. ( 위 코드 예시 참고)
       4. 장점
          1. 간단하다.
          2. 캐시 만료 시간을 분산해 여러 클라이언트가 동시에 캐시를 갱신하지 않는다.
     • PER 알고리즘
       1. 방법적
          1. 캐시 만료되기 전에 일정 확률로 미리 캐시를 갱신한다.
       2. 작동 방식
          1. 캐시 만료 전에 일정 확률로 캐시를 갱신한다.
          2. 캐시 만료 시점에 여러 클라이언트가 동시에 캐시를 갱신하지 않도록 함.
       3. 기본 만료 시간이 5분이라면, 5분이 되기 전에, 10% 확률로 캐시를 미리 갱신한다.
       4. 장점
          1. 캐시가 만료되기 전에 미리 갱신하여, 캐시 만료 시점에 부하가 집중되는 것을 방지한다.
  • 단순히 방법적인 차이고, 장- 단점의 엄청난 차이는 없음.