Redis의 LRU 캐시 제거 알고리즘 구현을 완전히 마스터하세요.

이 기사에서는 Redis에 대한 관련 지식을 제공하며 Redis의 근사 LRU 알고리즘 구현, 근사 LRU 알고리즘의 실제 실행 등을 포함하여 LRU 캐시 제거 알고리즘의 구현을 주로 소개합니다. 모두에게 도움이 되십시오.

추천 학습: Redis 학습 튜토리얼

1 표준 LRU

LRU의 구현 원리, Least Recent Used(Least Recent Used, LRU), 클래식 캐시 알고리즘입니다.

LRU는 Linked List를 사용하여 캐시에 있는 각 데이터의 접근 상태를 유지하고, 데이터의 실시간 접근을 기반으로 Linked List 내 데이터의 위치를 ​​조정한 후 데이터의 위치를 ​​활용하게 됩니다. 최근에 데이터에 액세스했는지 여부를 나타내기 위해 연결 목록에 표시됩니다.

LRU는 체인의 헤드와 테일을 각각 MRU 끝과 LRU 끝으로 설정합니다.

• MRU, Most Recent Used의 약어로 여기 데이터가 방금 액세스되었음을 나타냅니다.
• LRU end, 여기 데이터

LRU는 다음과 같은 경우로 나눌 수 있습니다.

• case1: 새로운 데이터가 삽입되면 LRU는 해당 데이터를 체인의 헤드에 삽입함과 동시에 원래 연결 목록의 선두에 있는 데이터와 그 뒤의 데이터 비트
• case2: 데이터에 한 번 액세스한 경우 LRU는 연결 목록의 현재 위치에서 선두로 데이터를 이동합니다. 체인의. 다른 모든 데이터를 연결된 목록의 선두에서 현재 위치로 꼬리 쪽으로 한 비트 이동합니다
• case3: 연결된 목록의 길이가 더 이상 더 이상 데이터를 수용할 수 없어 새 데이터가 삽입되면 LRU는 다음 위치의 데이터를 제거합니다. 이것도 캐시에서 데이터를 삭제하는 것과 같습니다

케이스 2의 예시: 링크드 리스트의 길이는 5이고, 링크드 리스트의 선두부터 테일까지 저장된 데이터는 각각 5, 33, 9, 10, 8. 데이터 9에 한 번 액세스한 다음 9는 연결 목록의 선두로 이동하고 동시에 데이터 5와 33은 모두 연결 목록의 끝으로 한 위치 이동한다고 가정합니다.

그래서 LRU에 따라 엄격하게 구현한다면 Redis가 많은 데이터를 저장한다고 가정하고 코드로 구현해야 합니다.

• Redis가 최대 메모리를 사용할 때 모든 링크 목록을 유지합니다. 수용할 수 있는 데이터

  링크드 리스트를 저장할 추가 메모리 공간

• 새 데이터가 삽입되거나 기존 데이터에 다시 액세스할 때마다 여러 개의 링크드 리스트 작업을 수행해야 합니다

  데이터에 액세스하는 과정에서 Redis는 데이터 이동 및 연결 목록 작업의 오버헤드에 영향을 받습니다

결국 Redis 액세스 성능이 저하됩니다.

그래서 메모리 절약을 위해서든 Redis의 고성능을 유지하기 위해서든 Redis는 LRU의 기본 원칙에 따라 엄격하게 구현되지는 않지만 대략적인 LRU 알고리즘 구현을 제공합니다.

2 Redis에서 근사 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 쌍에서 제거할 데이터를 필터링합니다.

TTL 세트가 있는 KV 쌍의 휘발성-lru 필터 will be Removal

Redis는 대략적인 LRU 알고리즘을 어떻게 구현합니까?

글로벌 LRU 클럭 값 계산

데이터 액세스의 적시성을 판단하기 위해 글로벌 LRU 클럭 값을 계산하는 방법

• LRU 클럭 값의 키 값 초기화 및 업데이트

함수에서, 각 키-값 쌍에 해당하는 LRU 클럭 값이 초기화되고 업데이트됩니다

• 근사 LRU 알고리즘의 실제 실행

근사 LRU 알고리즘을 실행하는 방법, 즉 데이터 제거가 트리거될 때, 그리고 실제 제거 메커니즘을 구현하려면

• 2.1 전역 LRU 클럭 값 계산

  대략적인 LRU 알고리즘은 여전히 ​​다양한 데이터의 액세스 적시성을 구별해야 합니다. 즉, Redis는 데이터의 최신 액세스 시간을 알아야 합니다. 따라서 LRU 클록은 데이터에 대한 각 액세스의 타임스탬프를 기록합니다.

Redis는 redisObject 구조를 사용하여 KV 쌍의 각 V에 대한 포인터를 V에 저장합니다. 값을 기록하는 포인터 외에도 redisObject는 lru 멤버 변수에 해당하는 LRU 클럭 정보를 저장하기 위해 24비트를 사용합니다. 이러한 방식으로 각 KV 쌍은 lru 변수에 최신 액세스의 타임스탬프를 기록합니다.

redisObject 정의에는 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가 초기화되고 업데이트되는 기능은 무엇입니까?

2.2 키-값 쌍의 LRU 시계 값 초기화 및 업데이트

KV 쌍의 경우 LRU 시계 값은 KV 쌍이 생성될 때 처음 설정됩니다. 이 초기화 작업은 createObject 함수에서 호출됩니다. Redis가 KV 쌍을 생성하려고 할 때 호출됩니다.

redisObject에 메모리 공간을 할당하는 것 외에도 createObject는 maxmemory_policy 구성에 따라 redisObject.lru를 초기화합니다.

• maxmemory_policy=LFU인 경우 lru 변수 값이 초기화되어 LFU 알고리즘
• maxmemory_policy≠LFU의 계산된 값으로 설정되고 createObject는 LRU_CLOCK을 호출하여 LRU 값에 해당하는 LRU 클럭 값을 설정합니다. KV 쌍.

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 알고리즘을 근사화하는 데 궁극적으로 어떻게 사용됩니까?

2.3 근사 LRU 알고리즘의 실제 실행

Redis가 근사 LRU를 구현하는 이유는 메모리 자원의 오버헤드와 작업 시간을 줄이기 위해서입니다.

2.3.1 알고리즘 실행은 언제 시작되나요?

근사 LRU의 주요 로직은 PerformEvictions에 있습니다.

performEvictions는 evictionTimeProc에 의해 호출되고 evictionTimeProc 함수는 processCommand에 의해 호출됩니다.

processCommand, Redis는 각 명령을 처리할 때 호출합니다.

그런 다음 isSafeToPerformEvictions는 다음 조건에 따라 PerformEvictions 실행을 계속할지 여부를 다시 판단합니다.

performEvictions가 호출되고 maxmemory-policy가 allkeys-lru 또는 휘발성-lru로 설정되면 대략적인 LRU 실행이 트리거됩니다.

2.3.2 대략적인 LRU 특정 실행 프로세스

실행은 다음 단계로 나눌 수 있습니다.

2.3.2.1 현재 메모리 사용량 확인

getMaxmemoryState를 호출하여 현재 메모리 사용량을 평가하고 현재 Redis 서버는 메모리 용량을 사용하고 있습니다. maxmemory 구성 값이 초과되었습니다.

maxmemory를 초과하지 않으면 C_OK가 반환되고, PerformEvictions도 직접 반환됩니다.

getMaxmemoryState가 현재 메모리 사용량을 평가할 때 사용된 메모리가 maxmemory를 초과하는 것으로 확인되면 해제해야 하는 메모리 양을 계산합니다. 해제된 메모리의 크기 = 사용된 메모리의 양 - maxmemory.

그러나 사용된 메모리 양에는 마스터-슬레이브 복제에 사용되는 복사 버퍼 크기가 포함되지 않습니다. 이는 freeMemoryGetNotCountedMemory를 호출하여 getMaxmemoryState로 계산됩니다.

현재 서버에서 사용하는 메모리 양이 최대 메모리 상한을 초과하는 경우, PerformEvictions는 while 루프를 실행하여 데이터를 제거하고 메모리를 해제합니다.

제거 데이터의 경우 Redis는 제거할 후보 KV 쌍을 저장하기 위해 EvictionPoolLRU 배열을 정의합니다. 요소 유형은 제거할 KV 쌍의 유휴 시간, 해당 K 및 기타 정보를 저장하는 evictionPoolEntry 구조입니다.

이런 식으로 Redis 서버는 초기화를 위해 initSever를 실행할 때 evictionPoolLRU 배열에 메모리 공간을 할당하기 위해 호출합니다. 배열의 크기는 기본적으로 EVPOOL_SIZE에 의해 결정됩니다. KV 쌍이 제거됩니다.

PerformEvictions는 데이터 제거의 순환 프로세스 중에 제거할 후보 KV 쌍 세트인 EvictionPoolLRU 어레이를 업데이트합니다.

2.3.2.2 제거할 후보 KV 쌍 세트 업데이트

performEvictions는 evictionPoolPopulate를 호출합니다. 이는 먼저 dictGetSomeKeys를 호출하여 샘플링할 해시 테이블에서 특정 숫자 K를 무작위로 얻습니다.

dictGetSomeKeys 샘플링된 해시 테이블 , by maxmemory_policy 구성 항목은 다음을 결정합니다.
1. maxmemory_policy=allkeys_lru인 경우 샘플링할 해시 테이블은 Redis 서버의 전역 해시 테이블, 즉 모든 KV 쌍에서 샘플링됩니다.
   • 그렇지 않으면 샘플링할 해시 테이블 TTL 세트 K 해시 테이블과 함께 저장됩니다.

dictGetSomeKeys가 샘플링한 K 샘플 수는 구성 항목 maxmemory-samples에 의해 결정되며 기본값은 5입니다.

따라서 dictGetSomeKeys는 샘플링된 KV 쌍 세트를 반환합니다. evictionPoolPopulate는 샘플링된 KV 쌍의 실제 수를 기반으로 루프를 실행합니다. estimateObjectIdleTime을 호출하여 샘플링 세트에 있는 각 KV 쌍의 유휴 시간을 계산합니다.

그런 다음 evictionPoolPopulate는 제거할 후보 KV 쌍 세트를 순회합니다. 즉, EvictionPoolLRU 어레이는 다음 조건 중 하나에 따라 샘플링된 각 KV 쌍을 EvictionPoolLRU 어레이에 삽입하려고 시도합니다.

아직 KV 쌍을 삽입하지 않은 어레이에서 빈 슬롯을 찾을 수 있습니다.
1. 찾을 수 있습니다. 유휴 시간이 있는 어레이의 KV 쌍 다음으로, PerformEvictions는 결국 제거될 KV 쌍을 선택하기 시작합니다.

2.3.2.3 제거된 KV 쌍을 선택하고 삭제합니다.

evictionPoolPopulate가 EvictionPoolLRU 배열을 업데이트했고 배열의 K가 유휴 시간에 작은 것에서 큰 것으로 정렬되기 때문입니다. 따라서 PerformEvictions는 EvictionPoolLRU 배열을 한 번 순회하고 배열의 마지막 K에서 선택을 시작합니다. 선택한 K가 비어 있지 않으면 제거할 최종 K로 사용됩니다. 이 프로세스의 실행 논리:

제거된 K가 선택되면, PerformEvictions는 Redis 서버의 지연 삭제 구성에 따라 동기 삭제 또는 비동기 삭제를 수행합니다.

이 시점에서, PerformEvictions K 하나를 제거했습니다. 이때 해제된 메모리 공간이 충분하지 않은 경우, 즉 해제할 공간에 도달하지 않은 경우, PerformEvictions도

제거할 후보 KV 쌍의 집합을 업데이트하고 최종 제거 K를 선택하는 과정을 반복합니다. 해제할 공간이 크기 요구 사항을 충족합니다.

퇴거 절차 수행:

근사 LRU 알고리즘은 시간과 공간을 많이 소모하는 연결리스트를 사용하지 않고, 고정 크기의 데이터 세트를 사용하여 제거하고, 데이터 세트에 추가할 일부 K를 무작위로 선택하여 매번 제거됨.

마지막으로, 제거할 세트 내 K의 유휴 시간 길이에 따라 유휴 시간이 가장 긴 K를 삭제합니다.

요약

LRU 알고리즘의 기본 원리에 따르면, LRU 알고리즘을 기본 원리에 따라 엄격하게 구현한다면 개발된 시스템에서는 LRU 연결 리스트를 저장하기 위해 추가 메모리 공간이 필요하다는 것을 알 수 있으며, 시스템은 LRU 연결 목록 작업의 오버헤드도 작업에 영향을 미칩니다.

Redis의 메모리 리소스와 성능은 모두 중요하므로 Redis는 대략적인 LRU 알고리즘을 구현합니다.

• 먼저 글로벌 LRU 시계를 설정하고 KV 쌍이 있을 때 액세스 타임스탬프로 전역 LRU 시계 값을 얻습니다. 생성되고, 각 액세스에서 전역 LRU 시계 값을 얻고 액세스 타임스탬프를 업데이트합니다
• 그런 다음 Redis가 명령을 처리할 때 PerformEvictions가 호출되어 메모리를 해제해야 하는지 결정합니다. 사용된 메모리가 maxmemory를 초과하는 경우 일부 KV 쌍을 무작위로 선택하여 제거할 후보 세트를 구성하고 액세스 타임스탬프를 기준으로 가장 오래된 데이터를 선택하여 제거합니다

알고리즘의 기본 원리와 실제 알고리즘 실행은 다음과 같습니다. 개발 중에 특정 절충안이 있을 수 있으며, 알고리즘의 엄격한 구현으로 인해 발생하는 리소스 및 성능 오버헤드를 피하기 위해 개발된 시스템의 리소스 및 성능 요구 사항을 포괄적으로 고려해야 합니다.

추천 학습: Redis 튜토리얼

위 내용은 Redis의 LRU 캐시 제거 알고리즘 구현을 완전히 마스터하세요.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!