Redis 디자인 및 구현 - 04

황 건 홍 판 독서 노트
해시 시계

해시 표 (hash table): 산 목록 이 라 고도 부 르 며 핵심 코드 값 에 따라 방문 하 는 데이터 구조 입 니 다.검색 속 도 를 높이 기 위해 서 키 코드 값 을 표 의 한 위치 에 표시 합 니 다.이 함수 맵 은 해시 함수 라 고 하 는데 기록 을 저장 하 는 배열 을 산 목록 이 라 고 합 니 다.

해시 표 는 키 를 통 해 대응 하 는 value 를 신속하게 찾 을 때 사용 합 니 다.

해시 표 의 부하 인 자 는 실제 원소 수 / 해시 표 의 용량 과 같 고 부하 인자 가 클 수록 충돌 이 크 고 부하 인자 가 작 을 수록 공간 이 낭비 된다 는 것 을 나타 낸다.일반 부하 인 자 는 0 - 0.7 에 있다.

해시 알고리즘: 사전 에 새로운 키 쌍 을 추가 할 때 키 쌍 의 키 에 따라 해시 값 과 색인 값 을 계산 한 다음 색인 값 에 따라 새로운 키 쌍 을 포함 하 는 해시 표 노드 를 해시 표 배열 의 지정 색인 위 에 올 립 니 다.

키 충돌: 두 개 이상 의 키 가 해시 표 배열 의 같은 색인 에 할당 되 었 을 때 키 충돌 이 라 고 부 릅 니 다. Redis 는 체인 주소 법 으로 충돌 을 해결 합 니 다.dicht 에는 체인 테이블 끝의 지침 이 없습니다. 속 도 를 고려 하여 Redis 는 새로 추 가 된 노드 를 체인 테이블 의 헤더 위치 에 놓 습 니 다.

해시 표 의 부하 인 자 를 합 리 적 인 범위 내 에서 유지 하기 위해 서 는 해시 표 에 저 장 된 키 값 이 수량 이 너무 많 거나 너무 적 을 때 프로그램 은 해시 표 의 크기 를 상응 하 게 확장 하거나 수축 해 야 한다 (rehash 를 통 해 완성).

Redis 가 rehash 를 실행 하 는 절 차 는 다음 과 같다.

은 ht [1] 해시 표 분배 공간 으로 공간 크기 는 실행 할 동작 과 ht [0] 현재 포 함 된 키 쌍 에 달 려 있 습 니 다.

확장 작업 이 라면 ht [1] 의 크기 는 ht [0]. used * 2 와 같은 n 제곱 보다 크다.

수축 작업 이 라면 ht [1] 의 크기 는 첫 번 째 로 ht [0]. used 와 같은 2 의 n 제곱 이다.

ht [0] 에 저 장 된 모든 키 값 대 rehash 를 ht [1] 위 에 저장 합 니 다.

ht [0] 에 포 함 된 모든 키 쌍 이 ht [1] 로 이동 한 후에 ht [0] 을 방출 하고 ht [1] 를 ht [0] 로 설정 하 며 ht [1] 를 공백 해시 표 로 새로 만 듭 니 다.

hash 표 확장 조건, BGSAVE, BGREWRITEAOF 명령 은 새로운 하위 프로 세 스 를 생 성 합 니 다. 대부분의 운영 체 제 는 쓰기 시 복 제 됩 니 다. 하위 프로 세 스 기간 에 해시 표 확장 작업 을 하지 않도록 메모 리 를 절약 합 니 다. Redis 는 이때 확장 작업 에 필요 한 부하 요 소 를 향상 시 킵 니 다.

서버 가 BGSAVE, BGREWRITEAOF 명령 을 실행 하지 않 았 을 때 해시 표 의 부하 인 자 는 1 보다 크다.

서버 가 BGSAVE, BGREWRITEAOF 명령 을 실행 할 때 해시 표 의 부하 인 자 는 5 보다 크다.

hash 수축 작업 의 조건: 부하 인자 가 0.1 보다 적 을 때.

rehash 동작 은 한꺼번에 완 성 된 것 이 아니 라 점진 적 인 것 이다. 상세 한 절 차 는 다음 과 같다.

은 ht [1] 분배 공간

색인 카운터 변수 rehashidx 를 유지 하고 값 을 0

으로 설정 합 니 다.

사전 이 추가, 삭제, 찾기 또는 업데이트 작업 을 수행 할 때 프로그램 은 지정 한 작업 을 수행 하 는 것 외 에 ht [0] 해시 표를 rehashindx 색인 에 있 는 모든 키 값 을 rehash 에 ht [1] 로 추가 합 니 다. 완료 되면 프로그램 은 rehashidx 속성의 값 을 1

증가 합 니 다.

ht [0] 의 모든 키 쌍 이 rehash 에서 ht [1] 로 설정 되 었 을 때 프로그램 은 rehashidx 속성 값 을 - 1 로 설정 합 니 다.

점진 적 rehash 실행 기간 의 해시 표 삭제, 찾기, 업데이트 등 작업 은 두 개의 해시 표 에서 진행 되 며, ht [0] 에서 이 노드 를 찾 지 못 하면 ht [1] 에서 계속 작업 합 니 다.추가 작업 은 ht [1] 에 저 장 됩 니 다. ht [0] 는 추가 작업 을 하지 않 습 니 다.

redis 에서 하 쉬 표 의 구조

typedef struct dictht{
    //      
    dictEntry **table;
    //      
    unsigned long size;
    //        ，       ，    size - 1
    unsigned long sizemask;
    //       
    unsigned long used;
}dictht;

// dictEntry  
typedef struct dictEntry {
    //  
    void *key;
    //  
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    //          ，    ，       
    struct dictEntry *next;
}dictEntry;

자전.

Redis 에서 사전 의 구조

typedef struct dict {
    //       ，  dictType                     ，Redis                  。
    dictType *type;
    //     ，                  。
    void *privdata;
    //    ，        ht[0]， ht[0]  rehash     ht[1]
    dictht ht[2];
    // rehash   ，     rehash   ；  rehash    ，  -1
    int rehashidx;
} dict;

typedef struct dictType {
    //   hash    
    unsigned int (*hashFunction)(const void *key);
    //       
    void *(*keyDup)(void *privdata, const void *key);
    //       
    void *(*valDup)(void *privdata, const void *obj);
    //       
    void *(*keyDestructor)(void *privdata, const void *key);
    //       
    void *(*valDestructor)(void *privdata, const void *obj);
    //       
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

로그'메타프로그램 루비 버전 2'3장 읽기

동적 방법 Object#send 호출 방법은 약간 메모와 Object#send obj.send(:my_method, 3) Object#send를 사용하면 어떤 방법으로든 호출할 수 있습니다. privete 방법을 호...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Redis 디자인 및 구현 - 04 - 사전

좋은 웹페이지 즐겨찾기