[OSSCA2024] Redis 자료구조 - 5주차 온라인 미팅

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁

레디스 내부에서 해시를 다루는 방법

Redis에 주요 자료구조 이해

server.c/initServer

• 서버에 필요한 내용 초기화
• signal handler 설정

signal(SIGHUP, SIG_IGN);
signal(SIGPIPE, SIG_IGN);
setupSignalHandlers();

• thread io => thread pool
• Event Loop 설정

server.el = aeCreateEventLoop(server.maxclients+CONFIG_FDSET_INCR);
    if (server.el == NULL) {
        serverLog(LL_WARNING,
            "Failed creating the event loop. Error message: '%s'",
            strerror(errno));
        exit(1);
    }
server.db = zmalloc(sizeof(server)*server.dbnum);

💡이벤트 루프
Redis에서 이벤트 루프(Event Loop)는 비동기 네트워크 서버로서 클라이언트 요청을 처리하고,
비동기 작업을 관리하는 핵심 메커니즘. 이벤트 루프는 주로 네트워크 IO(READ, WRITE...)를 처리하는 데 사용.

Redis는 싱글 스레드로 동작하므로 이벤트 루프는 모든 클라이언트의 요청을 효율적으로 처리하는 데 중요한 역할.
모든 작업처리는 단일 콜스택에서 이루어지고 비동기 처리는 Queue를 이용하여 이벤트 루프방식으로 동작.

여러 개의 소켓이 동시에 연결되어 있고, 이들을 관찰하면서 들어오는 작업을 처리.
이를 통해 Redis는 스레드 동기화, 컨텍스트 스위칭으로 발생하는 리로스 경합 및 오버헤드, 복잡성을 방지.

SELECT

• 디비 번호를 바꾸어서 사용할 수 있는 명령어.(0~15까지)
• flushdb
  • DB 내용 전체 바꾸기
  • 레디스 클라이언트는 디비 번호가 0. 다른 디비를 사용할 수 없음
  • createIntConfig 설정

• 자료구조들 초기화

내부적으로 사용하는 것.

listCreate

• list를 생성

list *listCreate(void)
{
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

dictCreate

typedef struct dictEntry {
    void *key;                 // 항목의 키
    void *val;                 // 항목의 값
    struct dictEntry *next;    // 같은 해시 버킷의 다음 항목을 가리키는 포인터
} dictEntry;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);                // 키를 해싱하는 함수
    void *(*keyDup)(void *privdata, const void *key);             // 키를 복사하는 함수
    void *(*valDup)(void *privdata, const void *obj);             // 값을 복사하는 함수
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 키를 비교하는 함수
    void (*keyDestructor)(void *privdata, void *key);             // 키를 해제하는 함수
    void (*valDestructor)(void *privdata, void *obj);             // 값을 해제하는 함수
} dictType;

typedef struct dict {
    dictEntry **table;         // 해시 테이블의 버킷 배열
    dictType *type;            // 테이블에서 사용할 함수들을 정의하는 dictType 구조체
    unsigned long size;        // 해시 테이블의 버킷 수
    unsigned long sizemask;    // 해시 테이블 크기 마스크 (size - 1)
    unsigned long used;        // 해시 테이블에 저장된 항목 수
    void *privdata;            // 함수 호출에 사용할 사용자 정의 데이터
} dict;

/* Create a new hash table */
static dict *dictCreate(dictType *type, void *privDataPtr) {
    dict *ht = hi_malloc(sizeof(*ht));
    if (ht == NULL)
        return NULL;

    _dictInit(ht,type,privDataPtr);
    return ht;
}

/* Initialize the hash table */
static int _dictInit(dict *ht, dictType *type, void *privDataPtr) {
    _dictReset(ht);
    ht->type = type;
    ht->privdata = privDataPtr;
    return DICT_OK;
}

• hashTable 생성
• dictEntry
  • dictEntry 구조체는 해시 테이블의 각 버킷에 저장되는 개별 항목을 나타냄.
    체인법을 사용하여 충돌을 처리. 
  • key: 해시 테이블에서 항목을 식별하는 데 사용되는 키
  • val: 키에 해당하는 값
  • next: 해시 충돌이 발생했을 때 동일한 버킷 내의 다음 항목을 가리킴. 이를 통해 체인 형태로 연결된 항목들을 관리.
• dictType
  • dictType 구조체는 해시 테이블에서 사용하는 함수들을 정의.
    키와 값의 처리 방식(복사, 비교, 해제 등)을 커스터마이징하는 데 사용. 
  • 함수 포인터 사용 => 다형성 제공
  • hashFunction: 주어진 키에 대해 해시 값을 계산
  • keyDup: 키를 복사
  • valDup: 값을 복사
  • keyCompare: 두 키를 비교
  • keyDestructor: 키를 해제
  • valDestructor: 값을 해제
• dict
  • dict 구조체는 실제 해시 테이블을 나타냄.
    해시 테이블은 키-값 쌍을 저장하는 버킷 배열과 기타 메타 데이터를 포함.
  • table: 해시 테이블의 버킷 배열로, 각 버킷은 dictEntry 포인터를 가짐.
  • type: 이 해시 테이블에서 사용할 함수들을 정의하는 dictType 구조체를 가리킴.
  • size: 해시 테이블의 현재 크기(버킷 수).
  • sizemask: 해시 테이블 크기에서 버킷 인덱스를 계산할 때 사용하는 마스크 값입. 일반적으로 size - 1입니다.
  • used: 현재 해시 테이블에 저장된 항목의 수.
  • privdata: 함수 호출 시 사용할 수 있는 사용자 정의 데이터.
• 생성시에 dictType을 넣어줌
  • _dictInit에서 타입설정
  • dictFind()
    • dictSize는 동일
    • dictCompareKeys() => 키 비교 함수
    • dbDictType
      • sds인지, robj인지 확인
• serverDb
  • 자료구조 설정.

createZset

• sorted set 설정
• dictAddRaw
  
  • 키를 집어 넣는 것.

특정 slot에 포함된 데이터를 가져오려면?

• 선형으로 검색해서 모두 들고 오기(Full Scan)
  • 레디스는 싱글 스레드이기에 멈춰있어야함.
• 처음부터 slot 별로 데이터를 따로 관리
  • 16384개의 dict
  • 위의 문제를 해결하기 위해 kvstore 생성

참조