Redis의 사전, 해시 알고리즘 및 ReHash 원리에 대한 간략한 토론

이 기사는 Redis의 사전, 해시 알고리즘 및 ReHash 원리를 이해하는 데 도움이 되기를 바랍니다.

Redis의 사전은 데이터베이스 및 해시 키를 포함하여 Redis의 다양한 기능을 구현하는 데 널리 사용됩니다.

사전의 기본 구현은 해시 테이블입니다. 각 사전에는 두 개의 해시 테이블이 있으며, 하나는 일반적으로 사용되고 다른 하나는 rehash를 사용하여 공간을 확장하는 데 사용됩니다. [관련 권장사항: Redis 영상 튜토리얼]

Dictionary 구조 정의

typedef struct dict {
	
	// 类型特定函数
	dictType *type;
	
	// 私有数据
	void *privdata;
	
	// 哈希表，两个元素
	dictht ht[2]
	
	// rehash时记录的索引下标，当没有rehash时，值为-1
	int rehashidx;

} dict;

==rehash를 수행할 때 rehashidx로 마이그레이션된 각 인덱스의 항목 데이터는 +1;==

그 중 해시 테이블이 됩니다. dicttht의 구조는 다음과 같이 정의됩니다.

typedef struct dictht {
	
	// 哈希表数组
	dictEntry **table;
	
	// 哈希表大小
	unsigned long size;
	
	// 哈希表大小掩码，用于计算索引值
	unsigned long sizenask;
	
	// 该哈希表已有节点的数量
	unsigned long uesd;

} dictht;

그 중 table은 배열이고 배열의 각 요소는 dictEntry 유형의 포인터를 가리키며 dictEntry 유형은 키-값 쌍을 저장합니다.

여기서도 체인 주소 방식인 해시 충돌 문제를 해결하기 위해 해시 테이블의 노드를 연결 리스트로 연결한 것을 볼 수 있습니다.

해시 충돌 및 해시 알고리즘

키에서 값으로 빠르게 액세스하기 위해 Redis는 해시 테이블을 사용하여 모든 키-값 쌍을 저장합니다. key는 Redis가 설정한 Key에 해당하고, value는 값 자체가 아니라 특정 값을 가리키는 포인터에 해당합니다. 해시 테이블을 사용하는 가장 큰 장점은 O(1) 시간 복잡도로 키-값 쌍을 빠르게 찾을 수 있다는 것입니다. 하지만 해시 테이블이기 때문에 필연적으로 해시 충돌 문제가 발생하게 됩니다.

해시 충돌은 두 키의 해시 값과 해시 버킷을 계산할 때 우연히 동일한 해시 버킷에 속한다는 의미입니다.

Redis가 해시 충돌을 해결하는 방법은 zipper 방식인 체인 해싱을 사용하는 것입니다. 여러 요소가 동일한 해시 버킷을 가리키는 경우 연결 목록을 사용하여 해당 데이터를 동일한 해시 버킷에 저장하고 포인터를 사용하여 차례로 연결합니다.

해시 알고리즘

새 키-값 쌍이 사전에 추가되면 프로그램은 먼저 키-값 쌍을 기반으로 해시 값과 인덱스 값을 계산한 다음 인덱스 값을 기반으로 새 키가 포함됩니다. 값 쌍의 해시 테이블 노드는 해시 테이블 배열의 지정된 인덱스에 배치됩니다.

reHash 프로세스

해시 테이블에 저장되는 키-값 쌍의 수를 제어하기 위해 해시 테이블에 로드 팩터가 있습니다. 이를 완료하려면 다시 해시 작업이 필요합니다. 그 중 로드 팩터의 계산 공식은 다음과 같습니다.

// 负载因子 = 哈希表已保存的节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

해시 테이블 확장 및 축소 조건은 다음과 같습니다.

• 서버가 현재 BGSAVE 명령 또는 BGREWRITEAOF 명령을 실행하고 있지 않으며 해시의 로드 팩터는 다음과 같습니다. table은 1보다 크거나 같습니다.
• Server BGSAVE 명령 또는 BGREWRITEAOF 명령이 현재 실행 중이고 해시 테이블의 로드 비율이 5보다 크거나 같습니다.

위 조건 중 하나에 해당하는 경우 충족되면 다시 해시 프로세스가 실행됩니다.

서버가 BGSAVE 또는 BGREWRITEAOF를 실행하는 경우 Redis는 현재 서버 프로세스의 하위 프로세스를 생성합니다.

재해시 프로세스는 대략 세 단계로 나뉩니다.

• 해시 테이블 2에 더 큰 공간을 할당합니다. 예: 현재 해시는 해시 테이블 1의 두 배입니다.

• 해시 테이블 1의 데이터를 다시 매핑하여 해시 테이블 2에 복사합니다.

• 해시 테이블 1의 공간을 해제합니다. 단계 할당 공간의 크기는 현재 재해시 작업 유형과 현재 해시 테이블의 키-값 쌍 수에 따라 결정됩니다.

확장 작업을 수행할 때 할당된 공간 크기는 (해시 테이블의 키-값 쌍 수 * 2)보다 크거나 같은 첫 번째 2^n 값입니다. 현재 키-값 쌍의 수는 4 이고, 4 * 2 = 8입니다. 8은 2^3과 정확히 같기 때문입니다. 이는 2^n과 같은 첫 번째 값과 정확히 동일하므로 확장 공간은 8입니다.

• 축소 작업이 수행되면 할당된 공간의 크기는 (해시 테이블의 키-값 쌍 수)보다 크거나 같은 첫 번째 2^n 값입니다.

• Progressive reHash

해시 테이블의 개수가 많은 경우 모든 데이터를 한꺼번에 복사하게 되면 서버에 영향을 미칠 가능성이 매우 높습니다. 따라서 Redis는 재해시를 여러 번 수행하는데, 이는 점진적인 재해시입니다. 간단히 말해서 두 번째 단계에서 Redis는 요청이 처리될 때마다 해시 테이블 1의 첫 번째 인덱스 위치부터 시작하여 클라이언트 요청을 정상적으로 처리합니다. 다음 요청이 있을 때 항목 요소가 해시 테이블 2에 복사됩니다. 생성되면 다음 인덱스 위치의 항목이 복사됩니다. 이러한 방식으로 한 번에 많은 복사본의 오버헤드를 교묘하게 복사하여 여러 처리 요청 프로세스에 적용되고 시간이 많이 걸리는 작업을 피하며 데이터에 대한 빠른 액세스를 보장합니다.

재해시 기간 동안 해시 테이블 작업

점진적인 재해시 작업 중에는 사전 삭제, 검색, 업데이트 및 기타 작업이 두 개의 해시 테이블에서 수행됩니다. 예를 들어, 사전에서 키를 찾으려면 먼저 원본 테이블에서 이를 쿼리하고, 찾을 수 없으면 새 테이블에서 쿼리합니다. 사전 추가는 새 테이블에만 유지됩니다.

더 많은 프로그래밍 관련 지식을 보려면

프로그래밍 소개

를 방문하세요! !

위 내용은 Redis의 사전, 해시 알고리즘 및 ReHash 원리에 대한 간략한 토론의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!