[Redis] Redis는 key expiration을 어떻게 관리할까?

1. CPU가 1초마다 전체 키를 순회하면서 expire을 체크하는 방식일까? (Polling)

2. 이 방법은 CPU 사용과 같은 자원 소모가 막심할 것으로 보인다.

3. expire time이 설정된 키는 TTL(Time2Live) 값을 가진다.

4. 이 값은 Secondary Hash Table에 저장된다.

5. 키에 접근할 때 (GET), 해당 테이블에 값이 있는지 없는지 먼저 확인한다.

6. 만약 만료되었다면, 키를 제거하고 nil을 반환한다.

7. 즉, Redis가 1초마다 전체 키를 순회 및 체크하는 방식이 아닌, 만료용 보조 테이블을 통해 관리한다.

8. 하지만 여기서 클라이언트가 해당 키에 단 한 번도 접근하지 않는다면?

9. 만료가 되어도 키가 제거되지 않은 채 공간만 차지하고 있을 것이다.

10. 이럴 때를 대비해서 Redis는 주기적으로 보조 해시 테이블에서 랜덤하게 키를 샘플링한다.

11. 샘플링 방식은 맨 처음 추측했던 '주기적인 체크 방식'과 유사하다.

12. 하지만 이 접근 방식의 문제점은 샘플링 및 키 삭제 루프가 진행됨에 따라 만료된 TTL을 가진 키가 점점 줄어들고 관련 없는 키 제거가 거의 발생하지 않아 CPU 사이클을 낭비하게 된다는 것이다.

13. 이러한 이유로 알고리즘은 만료 후보가 구성 가능한 임계값(기본값은 25%) 이하로 떨어질 때 샘플링을 중지한다. (Redis 6.0 버전 이전)

14. 25%의 키는 끝내 여전히 메모리를 사용하고 있음을 의미한다.

15. 공간만 차지하고 있는 키를 식별해야 하지만 무의미한 샘플링을 수행하면 또 안되는.. 공간 사용과 자원 사용의 딜레마에 빠진 셈이다!

16. Redis 6.0 이후부터는 Radix Tree(기수 트리)를 이용해서 언급한 문제점을 개선했다. 

- Radix Tree는 공통 접두사가 겹치는 문자열들을 하나의 노드로 압축하여 메모리 공간을 효과적으로 사용하는 자료구조로 대용량/주기성 데이터를 취급하는 Redis Stream에도 사용된다.

17. TTL이 설정된 키를 보조 해시 테이블에 저장하는 것까지는 이전 버전과 동일하다.

단, 만료 시간이 가까운 키로 분류되면 기수 트리에 저장한다.

이는 다음 샘플링 수행 시, 힌트(조회 시작점)로 사용하기 위함이다.

18. 이후 Redis는 샘플링을 수행할 때, 먼저 기수 트리에서 만료 시간이 가까운 키를 확인한다.

19. 키의 TTL이 만료되면, 기수 트리에서 해당 키를 찾아 제거하고 메모리를 해제한다.

 

20. 기수 트리를 사용한 expire 처리 방식은 기존 방식인 랜덤 샘플링 방식에 비해 다음과 같은 이점을 갖는다.

- 만료 시간이 가까운 키를 기수 트리에 저장하고, 이후 샘플링 주기에서 이 키들을 우선적으로 처리함으로써 불필요한 메모리 사용을 줄임-> 25%를 남기지 않고 전부 처리하여 공간 사용 딜레마 해결

- 기수 트리를 사용하면 만료 키를 더 빠르게 검색하고 제거할 수 있고 만료 가능성이 높은 키를 집중적으로 처리하여 CPU 자원 사용을 최적화 -> 자원 사용 딜레마 해결