초기 Redis 분석 - 자료구조

업데이트 내역

2023.12.10 해시 생성 알고리즘, 해시 마스킹 설명 추가

2023.12.12 해시 테이블 resize 과정 추가

들어가기 전에

Redis beta 1 버전을 기준으로 작성한 글입니다.

해당 버전의 코드는 다음 링크에서 확인하실 수 있습니다.

http://redisgate.kr/redis/introduction/redis_release1.php

Redis Release Notes 1

데이터 관리

redis는 데이터를 문자열 형태로 관리한다. 하지만, 문자열 그대로 관리하지 않고, SDS(Simple Dynamic String) 란 객체에 문자열과 메타 데이터를 같이 관리한다.

redis의 가변 문자열 객체

여기서 len은 문자열의 길이, free는 현재 할당된 메모리에서 남은 공간을 의미한다.

char buf[0] 변수는 우리가 저장한 문자열의 시작점을 나타내는 포인터다.

특이한 점은 char buf[0]의 크기는 0이다. 이러한 변수를 둔 이유는 가변길이 데이터의 시작점을 등록해두기 위해서다.

그래서 SDS의 메타 데이터를 가져올 때 다음 방법을 사용한다.

(sds - (sizeof(struct sdshdr))); // SDS 주솟값 - SDS 헤더 구조체 크기 = 메타 데이터 주솟값

가변 문자열 버퍼 늘리기

문자열 이어붙이기, 복사 등을 통해 버퍼가 부족한 경우

sds.c의 sdsMakeRoomFor 란 함수를 통해 문자열 버퍼를 늘릴 수 있다.

만약, 추가할 문자열 크기보다 free 값이 더 크다면 기존 문자열 버퍼를 사용한다.

free 값이 작다면, (현재 문자열 길이 + 추가할 문자 길이) * 2 만큼 새로운 버퍼를 할당받는다.

    newlen = (len+addlen)*2;	// (기존 문자열 길이 + 새로 추가할 길이) * 2
    newsh = realloc(sh, sizeof(struct sdshdr)+newlen+1); // NULL 삽입을 위해 + 1

Key, Value

키의 경우 SDS 형태로 관리를 하지만, 값의 경우 list, set 타입도 저장하기 때문에 robj(Redis Object) 란 구조로 관리한다.
당연히 List나 Set 내부 원소들은 SDS로 구성돼있다.

값을 관리하는 Redis Object

type 변수는 String, List, Set 타입 별로 사전에 명시된 값 (매크로 함수로 정의돼 있다.)

ptr 변수는 데이터가 저장된 주소의 포인터

refcount는 몇 명의 클라이언트가 참조하고 있는지 나타낸다. (기본값 1)

해시 테이블

한 테이블 내엔 여러 Key, Value 쌍의 테이블 항목들이 있기 때문에 dictEntry에 접근할 대한 2차원 포인터를 가지고 있다.

해시 테이블과 그 항목에 대한 객체

used를 통해 해시 테이블 내의 etnry가 몇 개인지 확인할 수 있다.

privdata는 해시 테이블 확장 과정에서 이전 해시 테이블에 대한 정보를 담고 있다.

 

dict 객체와 dictEntry 간 메모리 참조 방식 보기

 

 

table에 저장된 값을 참조해 해시 Entry의 주소들이 있는 가변 배열(*table)에 접근하고
이 가변 배열 내의 주소를 참조하면(**table) 해시 Entry 데이터에 접근할 수 있다

해시 키를 어떻게 만드는지?

문자열 해시 알고리즘 중 하나인 djb2를 사용한다.

아스키 문자에 대해 안정적인 분포를 제공한다 해서 사용한다고 한다.

redis 개발자가 직접 검증했기 때문에 개인적인 정당성 증명은 하지 않는다.

djb2 알고리즘 구현체

 

해시에 사용되는 문자열 길이만큼 해시를 33번 곱한 후, 각 문자열의 아스키 값을 더해 새로운 해시를 만든다.

예를들어 TEST란 문자에 대해 해시를 한다면

1. 5381 * 33 + 84(아스키 T) = 177,657

2. 177,657 * 33 + 69(아스키 E) = 5,862,750

3. 5,862,750 * 33 + 83(아스키 S) = 193,470,833

4. 193,470,833 * 33 + 84(아스키 T) = 1,896,099,360(int 오버플로우) + 193,470,833 + 84 = 2,089,570,277

즉, 해시값은 2,089,570,277, 16진수로 표현하면 0x7C8C4FE5 이 된다.

해시를 테이블에 어떻게 배치하는지?

djb2을 통해 생성한 해시값 & sizemask 을 통해 인덱싱을 한다.

멤버 변수 size - 1 한 값이 sizemask가 된다.

sizemask  = size - 1

1을 빼는 이유는 해시 테이블 크기는 2의 제곱으로 증가하기 때문에 1을 빼면 1로만 이루어진 이진수를 얻는다.

비트 연산 &을 통해 해시 테이블 범위 내에 해시를 저장할 수 있다.

 

2의 제곱이 아닌 수를 해시 테이블 크기로 잡으면 modular를 통해 인덱싱을 해야한다.

하지만, 어셈블리단 기준 비트 연산은 명령어 하나에 끝나지만 modular 연산은 여러 명령이 필요해 비효율적이다.

 

 

값을 찾는 과정에서도 동일한 방법을 사용한다.

O(1) 의 시간 복잡도를 제공하지만, 해시 충돌을 리스트 방식으로 관리하기 때문에 최악의 경우 O(N) 이 나온다.

값 찾기 로직

 

해시 테이블의 복제, 비교, 삭제

해시 테이블마다 복제, 비교, 삭제에 관해선 실행 과정이 다르다.

따라서 dict 객체에서 사전에 정의된 함수 포인터들을 저장해놓은 객체인 dictType을 사용한다.
이 dictType은 자바 기준 interface 객체라고 보면된다.

함수 포인터 정보를 담고 있다.

dicType 을 implement 하는 객체 일부

해시 테이블 재조정

7.2 기준 max load factor는 1.618이다. (5.x 는 1이다.)

이 값을 넘어가면 해시 테이블 재조정이 발생한다.

 

각 키의 해시 값과 새로운 해시 테이블의 sizemask를 & 연산해 새로운 인덱스를 결정한다.

해시 테이블 resize 과정

 

7.2 버전 기준 버킷 수가 10% 미만이면 소규모 해시테이블로 전환한다.

실제 서비스에선 이런 상황은 고려되지 않는다 생각해 더 알아보진 않았다.

여러 개의 해시 테이블 관리

redis 내부에선 여러 개의 해시 테이블을 관리해야 한다.

Redis Server 객체는 해시 테이블이 Entry 참조하듯이, 이 해시 테이블에 대한 2차원 포인터를 가지고 있다.

 

해시 테이블의 개수는 dbnum 값에 따른다. redis 에서 데이터를 백업하기 때문에 테이블당 하나의 DB를 매칭해야 하기 때문이다.

이 값은 redis.conf 에서 조정할 수 있다.

처음 redis 실행시 구성 정보가 등록되는 객체

redisServer 객체와 해시 테이블간 메모리 참조 방식 보기

 

dict에 저장된 값을 참조해 해시 테이블의 주소들이 있는 가변 배열(*dict)에 접근하고
이 가변 배열 내의 주소를 참조하면(**dict) 해시 테이블 데이터에 접근할 수 있다.