Redis의 LRU 알고리즘을 자세히 설명하는 기사
- 青灯夜游앞으로
- 2021-10-13 10:33:304768검색
이 글에서는 Redis의 LRU(Least Recent Used)를 소개하겠습니다. 도움이 되셨으면 좋겠습니다!
Redis는 메모리 저장을 기반으로 하는 키-값 데이터베이스입니다. 메모리는 빠르지만 공간이 작으므로 시스템이 매우 느리게 실행됩니다. 스왑 메커니즘은 메모리의 일부를 저장하며, 스왑을 통한 교환은 시스템이 계속 실행되도록 보장하지만 스왑은 하드 디스크 스토리지이며 속도는 스왑 파티션보다 훨씬 느립니다. 특히 Redis와 같이 QPS가 매우 높은 서비스의 경우 수신 시에는 이 작업을 수행할 수 없습니다. (스왑 파티션 메모리도 가득 차면 시스템에 오류가 발생하니 참고하세요!) [관련 권장사항: Redis 동영상 튜토리얼]
Linux 운영체제는 free -m을 통해 스왑 크기를 확인할 수 있습니다:
그러면 어떻게 Redis에서 이러한 상황이 발생하지 않도록 방지하는 것이 매우 중요합니다(면접관은 Redis에 관해 질문을 받을 때 이 지식 포인트에 대해 거의 묻지 않습니다).
2. maxmemory 구성
Redis는 위의 문제를 해결하기 위해 maxmemory 구성을 제공합니다. 이 구성은 일반적으로 redis.conf 파일에서 구성하거나 CONFIG SET을 사용하여 구성할 수 있습니다. 런타임 시 명령.
redis.conf 파일의 구성 항목에 대한 도식적 다이어그램:
기본적으로 Redis는 64비트 운영 체제에 기본적으로 메모리 제한이 없음을 공식적으로 소개합니다. -bit 운영 체제에는 기본 3GB 암시적 메모리 구성이 있습니다. maxmemory가 0이면 메모리가 무제한이라는 의미입니다.
따라서 캐시 아키텍처를 구축할 때 하드웨어 리소스 + 비즈니스 요구 사항을 기반으로 적절한 최대 메모리 구성을 만들어야 합니다.
3. 메모리가 maxmemory에 도달하면 어떻게 해야 합니까? maxmemory가 최대 한도에 도달하면 Redis는 이 문제를 어떻게 처리합니까? 이것이 이 글의 초점입니다. Redis는 조건을 충족하는 키를 삭제하는 maxmemory-policy 제거 전략을 제공합니다(
이 글은 LRU에 대해서만 설명하고 LFU는 포함하지 않습니다, LFU는 다음 글에서 설명합니다). 오래된 것에 작별을 고하고 새로운 것을 환영합니다. maxmemory-policy 제거 전략:
- noeviction:
- 메모리 제한에 도달하고 클라이언트가 더 많은 메모리를 사용할 수 있는 명령을 실행하려고 하면 오류가 반환됩니다. 간단히 말해서 읽기 작업은 다음과 같습니다. 여전히 허용되지만 쓰기는 허용되지 않습니다. 새 데이터의 경우 del(삭제) 요청은 허용됩니다 . allkeys-lru:
- lru(Least Recent Used - Least Recent Used) 알고리즘을 통해 모든 키에서 제거 allkeys-random:
- 모든 키에서 무작위로 제거 휘발성-lru:
- 모든 키에서 만료 시간이 설정되면 lru(Least Recent Used - Least Recent Used) 알고리즘을 통해 제거됩니다. 이렇게 하면 만료 시간이 설정되지 않고 유지되어야 하는 데이터가 제거 대상으로 선택되지 않습니다. - 무작위: 만료 시간이 설정된 모든 키에서 무작위로 제거
- 휘발성-ttl: 만료 시간이 설정된 모든 키에서 키의 남은 만료 시간 TTL 값을 비교하여 TTL이 작을수록 빠름
- 및 휘발성-lfu/allkeys-lfu를 제거하면 두 알고리즘이 다릅니다! 임의 제거는 메모리 공간을 삭제하고 해제하기 위해 일부 키만 무작위로 선택하면 됩니다. ttl 만료 시간이 짧고 키가 먼저 제거되며 ttl의 크기를 비교하여 작은 ttl 값으로 키를 삭제할 수도 있습니다. 메모리 공간을 해제합니다.
먼저 Java 컨테이너를 사용하여 간단한 LRU 알고리즘을 구현합니다. ConcurrentHashMap을 사용하여 키-값 결과 저장 요소의 매핑 관계를 수행하고 ConcurrentLinkedDeque를 사용하여 키 액세스 시퀀스를 유지합니다.
package com.lizba.redis.lru;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedDeque;
/**
* <p>
* LRU简单实现
* </p>
*
* @Author: Liziba
* @Date: 2021/9/17 23:47
*/
public class SimpleLru {
/** 数据缓存 */
private ConcurrentHashMap<string> cacheData;
/** 访问顺序记录 */
private ConcurrentLinkedDeque<string> sequence;
/** 缓存容量 */
private int capacity;
public SimpleLru(int capacity) {
this.capacity = capacity;
cacheData = new ConcurrentHashMap(capacity);
sequence = new ConcurrentLinkedDeque();
}
/**
* 设置值
*
* @param key
* @param value
* @return
*/
public Object setValue(String key, Object value) {
// 判断是否需要进行LRU淘汰
this.maxMemoryHandle();
// 包含则移除元素，新访问的元素一直保存在队列最前面
if (sequence.contains(key)) {
sequence.remove();
}
sequence.addFirst(key);
cacheData.put(key, value);
return value;
}
/**
* 达到最大内存，淘汰最近最少使用的key
*/
private void maxMemoryHandle() {
while (sequence.size() >= capacity) {
String lruKey = sequence.removeLast();
cacheData.remove(lruKey);
System.out.println("key: " + lruKey + "被淘汰！");
}
}
/**
* 获取访问LRU顺序
*
* @return
*/
public List<string> getAll() {
return Arrays.asList(sequence.toArray(new String[] {}));
}
}复制代码</string></string></string>
테스트 코드:
package com.lizba.redis.lru;
/**
* <p>
* 测试最近最少使用
* </p>
*
* @Author: Liziba
* @Date: 2021/9/18 0:00
*/
public class TestSimpleLru {
public static void main(String[] args) {
SimpleLru lru = new SimpleLru(8);
for (int i = 0; i <p>테스트 결과: <strong></strong></p><p><strong></strong>위 테스트 결과에서 알 수 있듯이, 먼저 추가되었던 key0, key1이 제거되어 삭제되었습니다. added last 키는 시퀀스의 선두에 저장된 최신 키이기도 합니다. </p>이 솔루션을 사용하면 LRU 알고리즘을 쉽게 구현할 수 있지만 단점도 매우 분명합니다. 이 솔루션에서는 키 액세스 순서를 저장하기 위해 추가 데이터 구조를 사용해야 하므로 솔루션 자체가 사용됩니다. 하지만 메모리를 많이 소모하므로 이는 분명히 불가능합니다. <p><img src="https://img.php.cn/upload/image/775/594/750/163409191823487Redis%EC%9D%98%20LRU%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84%20%EC%9E%90%EC%84%B8%ED%9E%88%20%EC%84%A4%EB%AA%85%ED%95%98%EB%8A%94%20%EA%B8%B0%EC%82%AC" title="163409191823487Redis의 LRU 알고리즘을 자세히 설명하는 기사" alt="Redis의 LRU 알고리즘을 자세히 설명하는 기사"></p><h2 data-id="heading-4">5. Redis의 대략적인 LRU</h2><p>이러한 상황에 대응하여 Redis는 최근 사용 빈도가 가장 낮은 키를 제거하는 데 있어서 완전히 정확하지는 않지만 전체적인 정확성은 보장할 수 있는 대략적인 LRU 알고리즘을 사용합니다. <br>대략적인 LRU 알고리즘은 매우 간단합니다. Redis 키 개체에는 최신 액세스의 시스템 타임스탬프를 저장하기 위해 24비트가 추가됩니다. 클라이언트가 Redis 서버에 키 쓰기 관련 요청을 보내면 메모리가 발견됩니다. 최대 메모리에 도달합니다. 이때 Redis 서비스는 무작위 샘플링을 통해 조건을 충족하는 5개의 키를 선택합니다. (이 무작위 샘플링 <strong>allkeys-lru</strong>은 모든 키에서 무작위로 샘플링되고 <strong>휘발성-lru</strong>은 모든 키에서 샘플링됩니다. 만료 시간이 설정된 경우 무작위 샘플링) 키 개체에 기록된 최신 액세스 타임스탬프를 비교하고 메모리가 여전히 충분하지 않은 경우 5개 키 중 가장 오래된 키를 제거하고 이 단계를 계속 반복합니다. <br></p><p><strong>5는 Redis의 기본 무작위 샘플링 값 크기이며 redis.conf의 maxmemory_samples를 통해 구성할 수 있습니다. </strong></p><p><img src="https://img.php.cn/upload/image/866/655/134/163409192913128Redis%EC%9D%98%20LRU%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84%20%EC%9E%90%EC%84%B8%ED%9E%88%20%EC%84%A4%EB%AA%85%ED%95%98%EB%8A%94%20%EA%B8%B0%EC%82%AC" title="163409192913128Redis의 LRU 알고리즘을 자세히 설명하는 기사" alt="Redis의 LRU 알고리즘을 자세히 설명하는 기사"></p><p><strong>위의 무작위 LRU 알고리즘에 대해 Redis 공식은 테스트 정확도 데이터 차트를 제공했습니다. : </strong></p>
- 밝은 회색 레이어는 제거된 키를 나타냅니다. 그림 1은 표준 LRU 알고리즘 제거의 개략도입니다.
- 가운데 어두운 회색 레이어는 제거되지 않은 이전 키를 나타냅니다. 연한 녹색 레이어는 가장 최근에 액세스한 키
Redis3.0의 LRU 알고리즘은 Redis2.8의 LRU 알고리즘보다 더 정확합니다
. Redis3.0은 키가 제거될 때마다 maxmemory_samples와 동일한 크기의 제거 풀을 추가하기 때문입니다. 제거 대기 중인 제거 풀 키를 비교하여 최종적으로 가장 오래된 키를 제거합니다. 실제로 제거를 위해 선택한 키를 모아서 다시 비교하면 가장 오래된 키가 제거됩니다. 6. 문제가 있습니다
LRU 알고리즘이 사용하기 쉬운 것 같지만 불합리한 곳도 있습니다. 예를 들어 A와 B 두 개의 키가 제거되기 1시간 전에 동시에 추가되었습니다. 처음에는 49분 동안 1,000번 액세스되었지만 다음 11분 동안에는 액세스되지 않았습니다. 이 시간에 LRU 알고리즘이 사용된 경우 A와 B가 모두인 경우 B에는 한 번만 액세스되었습니다. Redis 샘플링을 통해 A가 제거되는 것은 분명 불합리한 일입니다.
이러한 상황에 대응하여 Redis 4.0에서는 가장 적게 사용되는 알고리즘인 LFU 알고리즘을 추가했습니다. 이 알고리즘은 LRU보다 더 합리적입니다. 필요한 경우 아래에서 제거 알고리즘에 대해 알아보겠습니다. 내 칼럼에.
더 많은 프로그래밍 관련 지식을 보려면
위 내용은 Redis의 LRU 알고리즘을 자세히 설명하는 기사의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!