이 글에서는 Redis의 LRU 캐시 제거 알고리즘 구현과 관련된 문제를 주로 소개하는Redis 튜토리얼에 대한 관련 지식을 제공합니다. LRU는 연결 목록을 사용하여 캐시에 있는 각 데이터의 액세스 상태를 유지합니다. 데이터에 대한 실시간 접근 및 연결리스트의 데이터 위치 조정이 모든 분들께 도움이 되기를 바랍니다.
추천 학습:Redis 학습 튜토리얼
LRU의 구현 원리,Least Recent Used(Least Recent Used, LRU), 클래식 캐시 알고리즘입니다.
LRU는 Linked List를 사용하여 캐시에 있는 각 데이터의 접근 상태를 유지하고, 데이터의 실시간 접근을 기반으로 Linked List 내 데이터의 위치를 조정한 후 데이터의 위치를 활용하게 됩니다. 최근에 데이터에 액세스했는지 여부를 나타내기 위해 연결 목록에 표시됩니다.
LRU는 체인의 헤드와 테일을 각각 MRU 끝과 LRU 끝으로 설정합니다.
LRU는 다음과 같은 경우로 나눌 수 있습니다.
케이스 2의 예시: 링크드 리스트의 길이는 5이고, 링크드 리스트의 선두부터 꼬리까지 저장된 데이터는 5개입니다. 각각 33, 9, 10, 8입니다. 데이터 9에 한 번 액세스한 다음 9는 연결 목록의 선두로 이동하고 동시에 데이터 5와 33은 모두 연결 목록의 끝으로 한 위치 이동한다고 가정합니다.
그래서 LRU에 따라 엄격하게 구현한다면 Redis가 많은 데이터를 저장한다고 가정하고 코드로 구현해야 합니다.
Redis가 최대 메모리를 사용할 때 모든 링크 목록을 유지합니다. 수용할 수 있는 데이터
링크드 리스트를 저장할 추가 메모리 공간
새 데이터가 삽입되거나 기존 데이터에 다시 액세스할 때마다 여러 개의 링크드 리스트 작업을 수행해야 합니다
데이터에 액세스하는 과정에서 Redis는 데이터 이동 및 연결 목록 작업의 오버헤드에 영향을 받습니다
결국 Redis 액세스 성능이 저하됩니다.
그래서 메모리 절약을 위해서든 Redis의 고성능을 유지하기 위해서든 Redis는 LRU의 기본 원칙에 따라 엄격하게 구현되지는 않지만대략적인 LRU 알고리즘 구현을 제공합니다.
Redis의 메모리 제거 메커니즘은 어떻게 근사 LRU 알고리즘을 활성화하나요? redis.conf의 다음 구성 매개변수:
maxmemory, Redis 서버가 사용할 수 있는 최대 메모리 용량을 설정합니다. 서버에서 사용하는 실제 메모리가 임계값을 초과하면 서버는 다음에 따라 메모리 제거를 수행합니다. maxmemory-policy 구성 정책을 운영하여 대략적인 LRU, LFU, TTL 값에 의한 제거 및 무작위 제거 등을 포함한 Redis 서버 메모리 제거 전략을 설정합니다.
그래서, maxmemory 옵션이 설정되면 maxmemory-policy가 allkeys-lru 또는 휘발성-lru로 구성되면 대략적인 LRU가 활성화됩니다. allkeys-lru와 휘발성-lru는 모두 대략적인 LRU를 사용하여 데이터를 제거합니다. 차이점은 다음과 같습니다.
allkeys-lru는 모든 KV 쌍에서 제거할 데이터를 필터링합니다.
LRU 클럭 값의 키 값 초기화 및 업데이트
근사 LRU 알고리즘의 실제 실행
2.1 전역 LRU 클럭 값 계산
대략적인 LRU 알고리즘은 여전히 다양한 데이터의 액세스 적시성을 구별해야 합니다. 즉, Redis는 데이터의 최신 액세스 시간을 알아야 합니다. 따라서 LRU 클럭은 데이터에 대한 각 액세스의 타임스탬프를 기록합니다.
각 KV 쌍의 LRU 클럭 값은 어떻게 계산되나요? Redis 서버는 인스턴스 수준의 글로벌 LRU 클럭을 사용하며, 각 KV 쌍의 LRU 시간은 글로벌 LRU 클럭에 따라 설정됩니다.
이 전역 LRU 시계는 Redis 전역 변수 서버의 멤버 변수에 저장됩니다.lruclock
Redis 서버가 시작되고 initServerConfig가 호출되어 다양한 매개 변수를 초기화하면 getLRUClock이 호출되어 값을 설정합니다. lruclock:
따라서 데이터 조각에 대한 두 번의 액세스 사이의 시간 간격이 1초 미만인 경우 두 액세스의 타임스탬프가 동일하다는 점에 유의해야 합니다! **LRU 클럭 정확도는 1초이므로 1초 미만의 간격으로 서로 다른 타임스탬프를 구분할 수 없습니다!
getLRUClock 함수는 LRU_CLOCK_RESOLUTION으로 얻은 UNIX 타임스탬프를 나누어 현재 LRU 시계 값인 LRU 시계 정밀도로 계산된 UNIX 타임스탬프를 얻습니다.
getLRUClock은 LRU 시계 값과 매크로 정의 LRU_CLOCK_MAX(LRU 시계가 나타낼 수 있는 최대값) 사이에서 AND 연산을 수행합니다.
그래서 기본적으로 전역 LRU 시계 값은 1초의 정밀도로 계산된 UNIX 타임스탬프이며 initServerConfig에서 초기화됩니다.
Redis 서버가 실행 중일 때 전역 LRU 시계 값은 어떻게 업데이트되나요? 이벤트 기반 프레임워크에서 Redis Server의 정기적으로 실행되는 시간 이벤트에 해당하는 serverCron과 관련됩니다.
serverCron은 시간 이벤트에 대한 콜백 함수로 주기적으로 실행됩니다. 빈도 값은 redis.conf의hz 구성 항목에 의해 결정됩니다. 기본값은 10입니다. 즉, serverCron 함수는 100ms마다 실행됩니다. (1초/10 = 100ms). serverCron에서는 getLRUClock을 호출하여 이 함수의 실행 빈도에 따라 전역 LRU 시계 값이 정기적으로 업데이트됩니다.
이러한 방식으로 각 KV 쌍은 전역 LRU 시계에서 최신 액세스 타임스탬프를 얻을 수 있습니다.
각 KV 쌍에 대해 해당 redisObject.lru가 초기화되고 업데이트되는 기능은 무엇입니까?
KV 쌍의 경우 LRU 시계 값은 KV 쌍이 생성될 때 처음 설정됩니다. 이 초기화 작업은createObject 함수에서 호출됩니다. Redis가 KV 쌍을 생성하려고 할 때 호출됩니다.
redisObject에 메모리 공간을 할당하는 것 외에도 createObject는 maxmemory_policy 구성에 따라 redisObject.lru를 초기화합니다.
LRU_CLOCK은 현재 전역 LRU 시계 값을 반환합니다. KV 쌍이 생성되면 이는 액세스와 동일하며 해당 LRU 시계 값은 액세스 타임스탬프를 나타냅니다.
해당 KV 쌍의 LRU 시계 값은 언제 다시 업데이트됩니까?
KV 쌍에 액세스하는 한 해당 LRU 클럭 값이 업데이트됩니다! KV 쌍에 액세스하면 액세스 작업이 결국lookupKey를 호출하게 됩니다.
lookupKey는 글로벌 해시 테이블에서 액세스할 KV 쌍을 조회합니다. KV 쌍이 존재하는 경우, lookupKey는 maxmemory_policy의 구성 값을 기반으로 액세스 타임스탬프인 키-값 쌍의 LRU 시계 값을 업데이트합니다.
maxmemory_policy가 LFU 정책으로 구성되지 않은 경우 lookupKey 함수는 LRU_CLOCK 함수를 호출하여 현재 전역 LRU 시계 값을 얻고 이를 키-값 쌍의 redisObject 구조에 있는 lru 변수에 할당합니다
이러한 방식으로 각 KV 쌍에 액세스하면 최신 액세스 타임스탬프를 얻을 수 있습니다. 하지만 궁금할 수도 있습니다. 이러한 액세스 타임스탬프는 데이터 제거를 위한 LRU 알고리즘을 근사화하는 데 궁극적으로 어떻게 사용됩니까?
Redis가 근사 LRU를 구현하는 이유는 메모리 자원의 오버헤드와 작업 시간을 줄이기 위해서입니다.
근사 LRU의 주요 로직은 PerformEvictions에 있습니다.
performEvictions는 evictionTimeProc에 의해 호출되고 evictionTimeProc 함수는 processCommand에 의해 호출됩니다.
processCommand, Redis는 각 명령을 처리할 때 호출합니다.
그런 다음 isSafeToPerformEvictions는 다음 조건에 따라 PerformEvictions 실행을 계속할지 여부를 다시 판단합니다.
performEvictions가 호출되고 maxmemory-policy가 allkeys-lru 또는 휘발성-lru로 설정되면 대략적인 LRU 실행이 트리거됩니다.
실행은 다음 단계로 나눌 수 있습니다.
getMaxmemoryState를 호출하여 현재 메모리 사용량을 평가하고 현재 Redis 서버 메모리 용량이 maxmemory 구성 값을 초과합니다.
maxmemory를 초과하지 않으면 C_OK가 반환되고, PerformEvictions도 직접 반환됩니다.
getMaxmemoryState가 현재 메모리 사용량을 평가할 때 사용된 메모리가 maxmemory를 초과하는 것으로 확인되면 해제해야 하는 메모리 양을 계산합니다. 해제된 메모리의 크기 = 사용된 메모리의 양 - maxmemory.
그러나 사용된 메모리 양에는 마스터-슬레이브 복제에 사용되는 복사 버퍼 크기가 포함되지 않습니다. 이는 freeMemoryGetNotCountedMemory를 호출하여 getMaxmemoryState로 계산됩니다.
현재 서버에서 사용하는 메모리 양이 최대 메모리 상한을 초과하는 경우, PerformEvictions는 while 루프를 실행하여 데이터를 제거하고 메모리를 해제합니다.
제거 데이터의 경우 Redis는 제거할 후보 KV 쌍을 저장하기 위해 EvictionPoolLRU 배열을 정의합니다. 요소 유형은 제거할 KV 쌍의 유휴 시간, 해당 K 및 기타 정보를 저장하는 evictionPoolEntry 구조입니다.
2.3.2.3 제거된 KV 쌍을 선택하고 삭제합니다.
evictionPoolPopulate가 EvictionPoolLRU 배열을 업데이트했고 배열의 K가 유휴 시간에 작은 것부터 큰 것으로 정렬되기 때문입니다. 따라서 PerformEvictions는 EvictionPoolLRU 배열을 한 번 순회하고 배열의 마지막 K에서 선택을 시작합니다. 선택한 K가 비어 있지 않으면 제거할 최종 K로 사용됩니다.
제거할 후보 KV 쌍의 집합을 업데이트하고 최종 제거 K를 선택하는 과정을
반복합니다. 해제할 공간이 크기 요구 사항을 충족합니다.
퇴거 수행 프로세스:
근사 LRU 알고리즘은 시간과 공간을 많이 소모하는 연결 리스트를 사용하지 않고,고정 크기의 제거 대상 데이터 세트를 사용하고, 매번 제거 대상 데이터 세트에 추가할 일부 K를 무작위로 선택합니다. .
마지막으로, 제거할 세트 내 K의 유휴 시간 길이에 따라 유휴 시간이 가장 긴 K를 삭제합니다.
LRU 알고리즘의 기본 원리에 따르면, LRU 알고리즘을 기본 원리에 따라 엄격하게 구현한다면 개발된 시스템에서는 LRU 연결 리스트를 저장하기 위해 추가 메모리 공간이 필요하다는 것을 알 수 있으며, 시스템은 LRU 연결 목록 작업의 오버헤드도 작업에 영향을 미칩니다.
Redis의 메모리 리소스와 성능은 모두 중요하므로 Redis는 대략적인 LRU 알고리즘을 구현합니다.
알고리즘의 기본 원리와 실제 알고리즘 실행은 다음과 같습니다. 개발 중에 특정 절충안이 있을 수 있으며, 알고리즘의 엄격한 구현으로 인해 발생하는 리소스 및 성능 오버헤드를 피하기 위해 개발된 시스템의 리소스 및 성능 요구 사항을 포괄적으로 고려해야 합니다.
추천 학습:Redis 튜토리얼
위 내용은 Redis의 LRU 캐시 제거 알고리즘 구현을 간략하게 이해합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
