Redis의 LRU 정책

Redis의 LRU 정책

• Redis의 LRU(Least Recently Used) 정책은 캐시 메모리 관리 기법으로, 가장 오랫동안 사용되지 않은 데이터를 우선적으로 제거하는 방식입니다.
• Redis는 메모리 내 데이터를 캐싱하기 때문에, 설정한 메모리 한도를 넘기지 않도록 데이터를 관리할 필요가 있습니다. 이때 메모리가 가득 차면 오래된 데이터를 제거해야 하며, 이를 위해 LRU 정책이 자주 사용됩니다.

---

Redis LRU 정책

Redis에서 지원하는 LRU 정책은 몇 가지가 있을 것이다며, 그 중에서 원하는 방식을 선택할 수 있습니다. 주요 정책은 다음과 같습니다:

1. noeviction
   • 새로운 데이터를 저장하려 할 때 메모리가 부족하면 오류를 반환합니다. 기본적으로는 데이터를 제거하지 않는 정책입니다.
2. allkeys-lru
   • 모든 키에 대해 LRU 알고리즘을 적용하여 가장 오랫동안 사용되지 않은 키를 제거합니다. 캐시로 적합한 방식입니다.

3. volatile-lru

• 만료 시간(TTL)이 설정된 키에 한해 LRU 알고리즘을 적용합니다. 만료 시간 없이 상주해야 하는 데이터는 제거되지 않습니다.

4. allkeys-random

• 모든 키 중에서 임의로 데이터를 제거합니다. 특정 사용 패턴이 없을 때 활용할 수 있습니다.

5. volatile-random

• 만료 시간이 설정된 키 중에서 임의로 데이터를 제거합니다.

6. volatile-ttl

• 만료 시간이 가장 가까운 키를 우선적으로 제거합니다.

---

Redis LRU 설정하기

• Redis 설정 파일인 redis.conf 또는 Redis CLI에서 설정할 수 있습니다.

1. maxmemory 설정

예시: 메모리 최대 사용량을 512MB로 설정하고 싶다면:

# redis.conf
maxmemory 536870912 # 최대 메모리 512MB

1. maxmemory-policy 설정: 위의 정책을 입력하면 됩니다.

maxmemory-policy allkeys-lru # 모든 키에 LRU 정책 사용

1. maxmemory-samples 설정: 샘플링 개수를 설정합니다.

예를 들어, 샘플링 키 개수를 10으로 설정하고 싶다면:

maxmemory-samples 10

Redis 서버를 시작 시 설정을 적용합니다.

redis-server /path/to/redis.conf

Redis CLI에서 적용하기

redis-cli config set maxmemory 536870912
redis-cli config set maxmemory-policy allkeys-lru
redis-cli config set maxmemory-samples 10

설정 적용된 값 확인하기

redis-cli config get maxmemory
redis-cli config get maxmemory-policy
redis-cli config get maxmemory-samples

---

LRU 알고리즘의 구현

• Redis는 엄격한 LRU 대신 샘플링 기반의 LRU를 사용합니다. 즉, 모든 데이터를 비교하지 않고, 일부 데이터만 샘플링하여 그 중 가장 오랫동안 사용되지 않은 데이터를 선택하는 방식입니다. 이는 성능 최적화를 위해 선택된 방법으로, maxmemory-samples 설정에 따라 샘플링할 개수를 조정할 수 있습니다. 기본적으로는 5개의 샘플을 비교하며, 더 많은 샘플을 비교할수록 LRU 알고리즘의 정확도가 높아집니다.
• 이를 통해 Redis는 적절한 메모리 사용을 보장하면서도 빠른 응답 성능을 유지할 수 있습니다.

---

LRU 내부 정책

• Redis에서 LRU(Least Recently Used) 알고리즘은 “오랫동안 사용되지 않은 데이터”를 판단하기 위해 각 키에 대한 접근 시간을 추적합니다. 이를 통해 가장 오랫동안 접근되지 않은 키를 찾아서 우선적으로 제거할 수 있습니다. Redis는 이를 효율적으로 처리하기 위해 특정 메커니즘을 사용합니다.

1. 접근 시간 추적 방식

Redis는 각 키에 대해 LRU 시계(time) 필드를 사용하여 마지막으로 접근된 시간을 기록합니다. 이 시간 정보는 다음과 같은 경우에 업데이트 됩니다

• 키가 읽힐 때(GET 같은 읽기 연산).
• 키가 수정될 때(SET, HSET 같은 쓰기 연산).

이때, 접근 시간은 시스템 시간을 정확히 기록하는 것이 아니라, 더 가벼운 방식으로 관리됩니다. Redis는 각 키의 LRU 타임스탬프를 24비트 숫자로 저장하는데, 이는 매우 효율적인 방식으로 메모리 오버헤드를 줄이기 위함입니다.

2. 샘플링 기반 선택

Redis는 모든 키를 일일이 확인하는 대신 샘플링 방식을 사용하여 LRU 알고리즘을 구현합니다. 샘플링의 구체적인 과정은 다음과 같습니다:

• Redis가 메모리가 부족할 때, 설정된 maxmemory-samples 수만큼의 키를 무작위로 선택합니다.
• 선택된 키들 중에서 가장 오래된 LRU 타임스탬프(즉, 가장 오랫동안 접근되지 않은 키)를 찾아 제거합니다.

이 샘플링 방식은 엄격한 LRU가 아니지만, 효율성과 성능을 고려한 타협으로, 비교적 정확하게 LRU 정책을 구현할 수 있습니다.

3. 접근 시간의 표현

• Redis의 LRU 타임스탬프는 시스템 시간과 일치하지 않으며, 상대적인 시간만을 기록합니다. Redis는 내부적으로 1초마다 16비트의 카운터를 증가시키고, 이 카운터 값이 각 키의 LRU 타임스탬프에 저장됩니다. 이를 통해 특정 키가 마지막으로 접근된 시간을 상대적으로 추정할 수 있습니다.
• 예를 들어, 현재 시점에서 LRU 타임스탬프가 100이고, 다른 키의 타임스탬프가 50이라면, 두 번째 키가 첫 번째 키보다 상대적으로 더 오래전에 접근되었음을 알 수 있습니다.

4. 비교의 간단화

• 키의 접근 시간이 저장된 24비트 타임스탬프는 메모리 공간을 절약하기 위한 것으로, 키가 마지막으로 사용된 정확한 시간을 알 필요는 없기 때문에 “현재 시점”에 대한 절대적인 기준은 중요하지 않습니다.
• Redis는 샘플링된 키들 간의 상대적인 LRU 값을 비교해서 가장 오래된 키를 선택하는 데 집중합니다.

5. 다른 정책들과의 차이

• Redis는 LRU 외에도 LFU(Least Frequently Used)와 같은 다른 정책도 제공하는데, 이는 “얼마나 자주 사용되었는가”를 기반으로 데이터를 제거합니다. LFU의 경우 Redis는 각 키의 사용 빈도를 추적하는 추가 메커니즘을 활용합니다.

---

maxmemory-samples

• Redis에서 LRU 정책의 maxmemory-samples 값을 높이는 것은 LRU 알고리즘의 정확도를 높이기 위한 방법이지만, 샘플링 개수를 늘리면 그만큼 성능 오버헤드도 증가할 수 있습니다.
• 오버헤드의 주요 요인은 다음과 같습니다:
  • CPU 부하
    • maxmemory-samples 값을 높이면 Redis는 더 많은 키를 비교해야 합니다. Redis는 기본적으로 O(1) 시간 복잡도를 제공하는 빠른 성능을 목표로 하기 때문에, 키를 비교하는 데 걸리는 시간이 증가할수록 CPU 사용량이 높아집니다.
    • 샘플 크기가 클수록 LRU 계산을 위해 더 많은 키를 조회하고 해당 키들의 사용 빈도를 분석해야 하므로, 비교 횟수와 CPU 연산이 늘어납니다. 그러나 이 연산은 메모리에서 이루어지므로, 대체로 그리 큰 비용을 요구하지는 않습니다.
  • 메모리 접근 비용
    • Redis가 더 많은 샘플을 메모리에서 읽어와야 하기 때문에 메모리 접근 횟수도 늘어납니다. 그러나 메모리 접근 자체는 CPU 연산보다 상대적으로 느린 작업이지만, Redis가 메모리 기반 데이터베이스라는 특성상 이 비용은 큰 문제가 되지는 않을 가능성이 큽니다.
  • LRU 정확도와 성능의 트레이드오프
    • maxmemory-samples 값이 작으면, 샘플링된 소수의 키들 중에서 가장 오랫동안 사용되지 않은 키를 선택하게 되므로, 최적의 LRU 대상 키를 제거하지 못할 가능성이 있습니다. 이는 LRU 정확도 저하로 이어지지만, 성능 측면에서는 오버헤드가 적습니다.
    • 반대로 maxmemory-samples 값이 크면, Redis가 더 많은 키들을 비교하기 때문에 제거할 키를 더 정확하게 선택할 수 있습니다. 하지만 그만큼 더 많은 리소스를 소모하게 됩니다.
• 성능 영향의 크기
  • 실제 오버헤드는 Redis가 처리하는 요청의 양, 서버의 하드웨어 성능, 키의 수 등에 따라 다릅니다. Redis는 싱글 스레드로 동작하므로, 샘플링 오버헤드가 증가하면 다른 명령어 처리 성능에도 영향을 미칠 수 있습니다. 일반적인 환경에서는 maxmemory-samples 값을 5 또는 10으로 유지하는 것이 균형을 맞추는 데 적합하다고 평가됩니다. 샘플 수를 극단적으로 크게(예: 100개 이상) 설정하면 과도한 CPU 부하를 초래할 수 있지만, 소수의 샘플링에서는 그 영향이 미미합니다.