Redis 데이터 구조의--SDS

7010 단어 redis
개요:
SDS(simple Dynamic String)
Redis 의 문자열 은 두 가지 저장 방식 이 있 습 니 다.redisObject 대상 의 encoding 필드 를 통 해 결정 합 니 다.emstr 의 대응 상 수 는 OBJ 입 니 다.ENCODING_EMBSTR,raw 대응 상수 OBJENCODING_RAW:
길이 가 매우 짧 을 때 emstr 형식 으로 저장 하고 길이 가 44 바이트 가 넘 을 때 raw 형식 으로 저장 합 니 다.왜 44 바이트 일 까요?44+NULL(끝)+SDS(19)=64.embstr 는 RedisObject 대상 헤드 구조 와 SDS 대상 을 연속 으로 저장 하고 malloc 방법 으로 한 번 에 분배 합 니 다
  • 길이 가 44 바이트 가 넘 을 때 raw 를 사용 할 때 처음에 두 번 의 malloc 방법 을 사용 해 야 합 니 다.RedisObject 와 SDS 는 메모리 주소 에서 연속 되 지 않 습 니 다

  • 다음은 string 형식 을 만 드 는 방법 원본 입 니 다:
    /* Create a string object with EMBSTR encoding if it is smaller than
     * OBJ_ENCODING_EMBSTR_SIZE_LIMIT, otherwise the RAW encoding is
     * used.
     *
     * The current limit of 44 is chosen so that the biggest string object
     * we allocate as EMBSTR will still fit into the 64 byte arena of jemalloc. */
    #define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
    robj *createStringObject(const char *ptr, size_t len) {
        if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT)
            return createEmbeddedStringObject(ptr,len);
        else
            return createRawStringObject(ptr,len);
    }
    
    
    
    
    /* Create a string object with encoding OBJ_ENCODING_RAW, that is a plain
     * string object where o->ptr points to a proper sds string. */
    robj *createRawStringObject(const char *ptr, size_t len) {
        return createObject(OBJ_STRING, sdsnewlen(ptr,len));
    }
    
    
    
    
    /* Create a string object with encoding OBJ_ENCODING_EMBSTR, that is
     * an object where the sds string is actually an unmodifiable string
     * allocated in the same chunk as the object itself. */
    robj *createEmbeddedStringObject(const char *ptr, size_t len) {
        robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);
        struct sdshdr8 *sh = (void*)(o+1);
    
        o->type = OBJ_STRING;
        o->encoding = OBJ_ENCODING_EMBSTR;
        o->ptr = sh+1;
        o->refcount = 1;
        if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
            o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
        } else {
            o->lru = LRU_CLOCK();
        }
    
        sh->len = len;
        sh->alloc = len;
        sh->flags = SDS_TYPE_8;
        if (ptr == SDS_NOINIT)
            sh->buf[len] = '\0';
        else if (ptr) {
            memcpy(sh->buf,ptr,len);
            sh->buf[len] = '\0';
        } else {
            memset(sh->buf,0,len+1);
        }
        return o;
    }
    
    
    /* ===================== Creation and parsing of objects ==================== */
    robj *createObject(int type, void *ptr) {
        robj *o = zmalloc(sizeof(*o));
        o->type = type;
        o->encoding = OBJ_ENCODING_RAW;
        o->ptr = ptr;
        o->refcount = 1;
    
        /* Set the LRU to the current lruclock (minutes resolution), or
         * alternatively the LFU counter. */
        if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
            o->lru = (LFUGetTimeInMinutes()<<8) | LFU_INIT_VAL;
        } else {
            o->lru = LRU_CLOCK();
        }
        return o;
    }

    SDS 의 정의
    /* Note: sdshdr5 is never used, we just access the flags byte directly.
     * However is here to document the layout of type 5 SDS strings. */
    struct __attribute__ ((__packed__)) sdshdr5 {
        unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
        char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr8 {
        uint8_t len; /* used */
        uint8_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr16 {
        uint16_t len; /* used */
        uint16_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr32 {
        uint32_t len; /* used */
        uint32_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };
    struct __attribute__ ((__packed__)) sdshdr64 {
        uint64_t len; /* used */
        uint64_t alloc; /* excluding the header and null terminator */
        unsigned char flags; /* 3 lsb of type, 5 unused bits */
        char buf[];
    };

    각 구조 체 구성원 의 용도:
    n:문자열 의 길 이 를 기록 합 니 다
  • alloc:유턴 과 문자열 의 빈 종료 부 호 를 제거 합 니 다\0 후 분 배 된 크기
  • flags:표지 위치,앞의 3 위 는 sds 의 유형 을 저장 하 는 데 사용 되 고 뒤의 5 위 는 사용 되 지 않 습 니 다(8,16,32,64)
  • buf:바이트 배열 은 문자열 을 저장 하 는 데 사 용 됩 니 다.끝 은 C 언어 문자열 관례 에 따라 종지부\\0 을 저장 합 니 다.일부 C 언어 문자열 함 수 를 사용 할 수 있 기 때 문 입 니 다
  • Redis 내부 에서 서로 다른 길이 의 문자열 에 대해 서로 다른 sdshdr 구조 체 를 정의 한 것 을 볼 수 있 습 니 다.len 과 alloc 의 두 필드 를 메모리 로 사용 하 는 것 을 최적화 시 키 는 것 이 목적 입 니 다.모두 기호 없 는 정형 을 사용 합 니 다.
    struct __attribute__ ((__packed__)) 문법 은 바이트 정렬 을 취소 하 는 데 사용 되 며 메모리 사용량 을 최적화 하기 위 한 것 입 니 다.
    플래그 비트
    플래그 비트 flags 필드 와 7 을 통 해 현재 문자열 의 sds 형식(8,16,32,64)을 판단 합 니 다.예 를 들 어 다음 문자열 의 길 이 를 가 져 오 는 방법:
    #define SDS_TYPE_5  0
    #define SDS_TYPE_8  1
    #define SDS_TYPE_16 2
    #define SDS_TYPE_32 3
    #define SDS_TYPE_64 4
    #define SDS_TYPE_MASK 7
    #define SDS_TYPE_BITS 3
    #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
    #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
    #define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
    
    static inline size_t sdslen(const sds s) {
        unsigned char flags = s[-1];
        switch(flags&SDS_TYPE_MASK) {
            case SDS_TYPE_5:
                return SDS_TYPE_5_LEN(flags);
            case SDS_TYPE_8:
                return SDS_HDR(8,s)->len;
            case SDS_TYPE_16:
                return SDS_HDR(16,s)->len;
            case SDS_TYPE_32:
                return SDS_HDR(32,s)->len;
            case SDS_TYPE_64:
                return SDS_HDR(64,s)->len;
        }
        return 0;
    }

    SDS 와 C 언어 문자열 의 차이
    1.상수 복잡 도 문자열 길이 가 져 오기
    4.567917.C 언어 에서 특정한 문자열 의 길 이 를 얻 으 려 면 전체 문자열 을 옮 겨 다 니 며 만 나 는 모든 문자열 을 계산 해 야 합 니 다.\0 을 만 날 때 까지 이 작업 의 복잡 도 는 O(n)입 니 다
  • SDS 에서 하나의 필드 len 으로 문자열 의 길 이 를 추가 로 저장 하고 길 이 를 얻 는 복잡 도 는 O(1)이 며 전형 적 인 공간 교환 시간 입 니 다

  • 2.버퍼 넘 침 방지
  • C 언어 에서 만약 에 우리 가 strcat 로 문자열 을 연결 하기 전에 기 존의 문자열 이 분 배 된 공간 이 연 결 된 문자열 의 크기 를 수용 할 수 없 으 면 데 이 터 는 뒤에 인접 한 공간 으로 넘 쳐 납 니 다.예 를 들 어 문자열 s1 은 redis 이 고 문자열 s2 는 golang 입 니 다.stcat(s1,abc)를 실행 하기 전에 s1 로 메모 리 를 재배 치 하 는 것 을 잊 어 버 리 면 문자열 s2 가 acblang 으로 변 합 니 다
  • SDS 에서 공간 분배 전략 을 통 해 버퍼 가 넘 치 는 것 을 피 할 수 있 습 니 다.SDS 에 대한 수정 이 필요 할 때 먼저 공간 이 필요 한 길 이 를 만족 시 키 는 지 확인 하고 만족 하지 않 으 면 자동 으로 확장 한 다음 에 수정 합 니 다

  • 3.공간 사전 분배
    4.567917.C 언어 에서 만약 에 우리 가 문자열 을 맞 추 려 면 필요 한 공간 을 계산 하고 메모 리 를 분배 한 후에 수정 해 야 한다.한편,메모리 분배 작업 은 시스템 호출 과 관련 되 고 사용자 상태 에서 커 널 상태 로 전환 하 며 복잡 한 메모리 분배 알고리즘 을 통 해 분 배 된 다음 에 커 널 상태 에서 사용자 상태 로 전환 하 며 전체 과정 이 매우 소모 된다
  • SDS 에 서 는 수정 할 때 배 정 된 SDS 의 길 이 를 먼저 계산 하고 SDS 의 길이 가 1M 보다 작 으 면 13 바이트+13 바이트+1byte(\0)바이트 의 공간 을 분배 한다.SDS 길이 가 1M 이상 이면 3M+1M+1byte(\\0)의 공간 이 분 배 됩 니 다

  • 4.바 이 너 리 안전
  • C 언어 에서 기본적으로\0 표지 문자열 로 끝 나 므 로 바 이 너 리 데 이 터 를 저장 하면 자동 으로 차단 되 어 데이터 가 완전 하지 않 습 니 다
  • SDS 에서 len 으로 문자열 의 길 이 를 계산 하기 때문에 바 이 너 리 안전
  • 좋은 웹페이지 즐겨찾기