Redis 의 동적 문자열 학습 강좌

sds 의 용도
Sds 가 Redis 에서 의 주요 역할 은 다음 과 같은 두 가지 가 있다.
문자열 개체 구현(StringObject);
Redis 프로그램 내부 에서 char*형식의 대체 품 으로 사용 하기;
다음 두 소절 은 각각 이 두 가지 용도 에 대해 소개 한다.
문자열 개체 구현
Redis 는 데이터베이스(key-value DB)에 대한 키 값 으로 데이터베이스 의 값 은 문자열,집합,목록 등 다양한 유형의 대상 일 수 있 으 며 데이터베이스 의 키 는 항상 문자열 대상 이다.
문자열 값 을 포함 하 는 문자열 대상 에 게 모든 문자열 대상 은 sds 값 을 포함 합 니 다.
"문자열 값 을 포함 하 는 문자열 대상"이라는 말 은 처음에는 이상 하 게 들 릴 수 있 지만 Redis 에 서 는 문자열 값 을 저장 할 수 있 는 것 외 에 log 형식의 값 도 저장 할 수 있 기 때문에 엄밀 하 게 보기 위해 서 는 문자열 대상 이 문자열 을 저장 할 때 sds 값 을 포함 합 니 다.그렇지 않 으 면 롱 형식의 값 입 니 다.
예 를 들 어 다음 명령 은 새로운 데이터베이스 키 쌍 을 만 들 었 습 니 다.이 키 쌍 의 키 와 값 은 모두 문자열 대상 입 니 다.모두 sds 값 을 포함 합 니 다.

redis> SET book "Mastering C++ in 21 days"
OK

redis> GET book
"Mastering C++ in 21 days"

다음 명령 은 다른 키 쌍 을 만 들 었 습 니 다.키 는 문자열 대상 이 고 값 은 집합 대상 입 니 다.

redis> SADD nosql "Redis" "MongoDB" "Neo4j"
(integer) 3

redis> SMEMBERS nosql
1) "Neo4j"
2) "Redis"
3) "MongoDB"

C 기본 char*형식 대신 sds 사용 하기
char*유형의 기능 이 단일 하고 추상 적 인 차원 이 낮 으 며 Redis 가 자주 사용 하 는 작업(예 를 들 어 추가 작업 과 길이 계산 작업)을 효과적으로 지원 하지 못 하기 때문에 Redis 프로그램 내부 에서 대부분 은 char*가 아 닌 sds 를 사용 하여 문자열 을 표시 합 니 다.
성능 문 제 는 잠시 후에 sds 정 의 를 소개 할 때 말 할 것 이다.우 리 는 Redis 의 다른 기능 모듈 을 알 지 못 했 기 때문에 상세 하 게 예 를 들 어 sds 를 사 용 했 지만 뒤의 장 에서 우 리 는 다른 모듈(거의 모든)이 sds 형식 값 을 사용 하 는 것 을 자주 볼 수 있다.
현재 로 서 는 이 사실 만 기억 하면 된다.Redis 에서 클 라 이언 트 가 서버 에 들 어 오 는 프로 토 콜 내용,aof 캐 시,클 라 이언 트 에 게 되 돌아 오 는 답장 등 중요 한 내용 은 모두 sds 형식 으로 저장 된다.
redis 의 문자열
C 언어 에서 문자열 은\0 끝 에 있 는 char 배열 로 표시 할 수 있 습 니 다.
예 를 들 어 hello World 는 C 언어 에서'hello World\0'이 라 고 표시 할 수 있다.
이러한 간단 한 문자열 은 대부분의 경우 요 구 를 만족 시 킬 수 있 지만 길이 계산 과 추가(append)두 가지 조작 을 효과적으로 지원 할 수 없다 는 것 을 나타 낸다.
문자열 길이(strlen(s)를 계산 할 때마다 복잡 도 는?θ(N) 。
문자열 을 N 회 추가 하려 면 문자열 을 N 회 메모리 재배 치(realloc)해 야 합 니 다.
Redis 내부 에 서 는 문자열 의 추가 와 길이 계산 이 흔 하지만 APPEND 와 STRLEN 은 이 두 가지 조작 으로 Redis 명령 에서 직접 매 핑 되 므 로 이 두 가지 간단 한 조작 이 성능 의 병목 이 되 어 서 는 안 된다.
또한 Redis 는 C 문자열 을 처리 하 는 것 외 에 단순 한 바이트 배열 과 서버 프로 토 콜 등 내용 을 처리 해 야 하기 때문에 편 의 를 위해 Redis 문자열 은 바 이 너 리 안전 해 야 한다 고 밝 혔 다.프로그램 은 문자열 에 저 장 된 데 이 터 를 어떠한 가설 도 해 서 는 안 되 고 데 이 터 는\0 으로 끝 나 는 C 문자열 일 수 있다.단순 한 바이트 배열 이나 다른 형식의 데이터 일 수도 있다.
이 두 가지 이 유 를 고려 하여 Redis 는 sds 형식 으로 C 언어의 기본 문자열 을 바 꾸 었 다.sds 는 추가 와 길이 계산 을 효율적으로 실현 할 수 있 을 뿐만 아니 라 바 이 너 리 도 안전 하 다.
sds 의 실현
앞의 내용 에서 우 리 는 sds 를 추상 적 인 데이터 구조 로 설명 해 왔 다.실제로 그의 실현 은 다음 과 같은 두 부분 으로 구성 된다.

typedef char *sds;


struct sdshdr {

  // buf      
  int len;

  // buf       
  int free;

  //             
  char buf[];
};

그 중에서 유형 sds 는 char*의 별명(alias)이 고 구조 sdshdr 는 len,free,buf 세 가지 속성 을 저장 합 니 다.
예 를 들 어 다음은 새로 만 든 것 입 니 다.hello World 문자열 을 저장 하 는 sdshdr 구조 입 니 다.

struct sdshdr {
  len = 11;
  free = 0;
  buf = "hello world\0"; // buf        len + 1
};

len 속성 을 통 해 sdshdr 는 복잡 도 를 실현 할 수 있 습 니 다.θ(1)길이 계산 작업.
다른 한편,buf 에 추가 공간 을 할당 하고 free 를 사용 하여 사용 되 지 않 은 공간의 크기 를 기록 합 니 다.sdshdr 는 추가 작업 을 수행 하 는 데 필요 한 메모리 재 할당 횟수 를 크게 줄 일 수 있 습 니 다.다음 절 에 우 리 는 이 점 을 상세히 토론 할 것 입 니 다.
물론 sds 도 작업 의 정확 한 실현 에 대해 요 구 를 제 기 했 습 니 다.sdshdr 를 처리 하 는 모든 함 수 는 len 과 free 속성 을 정확하게 업데이트 해 야 합 니 다.그렇지 않 으 면 bug 를 초래 할 수 있 습 니 다.
데이터 형식 정의
sds 구현 과 관련 된 데이터 형식 은 두 가지 가 있 습 니 다.하 나 는 sds 입 니 다.

  //          
  typedef char *sds; 

다른 하 나 는 sdshdr:

  //   sds    
  struct sdshdr { 
    // buf               
    int len; 
    // buf            
    int free; 
    //            
    char buf[]; 
  }; 

그 중에서 sds 는 문자열 배열 형식 char*의 별명 일 뿐 sdshdr 는 sds 정 보 를 가지 고 저장 하 는 데 사 용 됩 니 다.
예 를 들 어 sdshdr.len 은 O(1)의 복잡 도 에서 sdshdr.buf 에 저 장 된 문자열 의 실제 길 이 를 가 져 올 수 있 고 sdshdr.free 는 sdshdr.buf 에 저 장 된 예약 공간 이 얼마나 있 는 지 저장 하 는 데 사 용 됩 니 다.
(여기 sdshdr 는 sds handler 의 줄 임 말 일 것 입 니 다)
sdshdr 를 sds 로 사용 합 니 다.
sds 모듈 은 sdshdr 구조 에 작은 기 교 를 사 용 했 습 니 다.포인터 연산 을 통 해 sdshdr 구 조 를 sds 형식 처럼 전송 되 고 처리 할 수 있 으 며 필요 할 때 sdshdr 형식 으로 복원 할 수 있 습 니 다.
아래 의 함수 정 의 를 통 해 이 기 교 를 이해 하 다
sdsnewlen 함수 가 새로운 sds 값 을 되 돌려 줍 니 다.실제로 sdshdr 구 조 를 만 들 었 습 니 다.

  sds sdsnewlen(const void *init, size_t initlen) 
  { 
    struct sdshdr *sh; 
   
    if (init) { 
      //    
      sh = malloc(sizeof(struct sdshdr) + initlen + 1); 
    } else { 
      //     
      sh = calloc(1, sizeof(struct sdshdr) + initlen + 1); 
    } 
   
    if (sh == NULL) return NULL; 
   
    sh->len = initlen; 
    sh->free = 0;  //    free 0 
   
    if (initlen && init) { 
      memcpy(sh->buf, init, initlen); 
    } 
    sh->buf[initlen] = '\0'; 
   
    //    sh->buf        
    return (char *)sh->buf; 
  } 

변 수 를 사용 하여 sds 값 을 가지 고 있 습 니 다.sds 값 자체 만 처리 하 는 함 수 를 만 났 을 때 sds 를 직접 전달 할 수 있 습 니 다.예 를 들 어 sdstoupper 함 수 는 그 중의 한 예 이다.
 

  static inline size_t sdslen(const sds s) 
  { 
    //  sds       sdshdr   
    struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr))); 
   
    return sh->len; 
  } 
   
   
  void sdstoupper(sds s) 
  { 
    int len = sdslen(s), j; 
   
    for (j = 0; j < len; j ++) 
      s[j] = toupper(s[j]); 
  } 

여기에 지침 연산 을 통 해 sds 값 에서 해당 하 는 sdshdr 구 조 를 계산 할 수 있 는 기술 이 있 습 니 다.
sds 는 char*를 가리 키 는 buf(ps:그리고 빈 배열 은 메모리 공간 을 차지 하지 않 습 니 다.배열 이름 은 메모리 주소 입 니 다)이지 만 할당 할 때 size of(struct sdshdr)+initlen+1 을 분배 합 니 다.sds-size of(struct sdshdr)를 통 해 struct sdshdr 의 첫 주 소 를 계산 하여 len 과 free 정 보 를 얻 을 수 있 습 니 다.

sdsavail 함 수 는 이 기술 을 사용 하 는 예 입 니 다.
 

  static inline size_t sdsavail(const sds s) 
  { 
    struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr))); 
   
    return sh->free; 
  } 

메모리 할당 함수 구현
Reids 의 의사 결정 실현 과 관련 된 함 수 는 sds MakeRoomFor 입 니 다.
 

  sds sdsMakeRoomFor(sds s, size_t addlen) 
  { 
    struct sdshdr *sh, *newsh; 
    size_t free = sdsavail(s); 
    size_t len, newlen; 
   
    //               
    if (free >= addlen) return s; 
   
    len = sdslen(s); 
    sh = (void *)(s - (sizeof(struct sdshdr))); 
   
    //    sds       
    //                      
    //                
    newlen = (len + addlen); 
    if (newlen < 1024 * 1024) 
      newlen *= 2; 
    else 
      newlen += 1024; 
   
    //     sdshdr 
    newsh = realloc(sh, sizeof(struct sdshdr) + newlen + 1); 
    if (newsh == NULL) return NULL; 
   
    newsh->free = newlen - len; 
   
    //          
    return newsh->buf; 
  } 

이러한 메모리 할당 정책 은 sds 값 을 확장(expand)할 때 추가 공간 을 미리 남 겨 두 고 더 많은 메모 리 를 사용 하여 메모리 재 할당(reallocate)횟수 를 줄 이 고 다음 확장 작업 의 처리 속 도 를 최적화 하 는 것 을 나타 낸다.
다시 redis 의 sds 문자열 확장 방법 을 적용 하면 좋 은 생각 입 니 다.

  /** 
   *    len  sds，  t   sds    
   */ 
  sds sdscatlen(sds s, const void *t, size_t len) 
  { 
    struct sdshdr *sh; 
   
    size_t curlen = sdslen(s); 
   
    // O(N) 
    s = sdsMakeRoomFor(s, len); 
    if (s == NULL) return NULL; 
   
    //    
    memcpy(s + curlen, t, len); 
   
    //   len free   
    sh = (void *)(s - (sizeof(struct sdshdr))); 
    sh->len = curlen + len; 
    sh->free = sh->free - len; 
   
    //     
    s[curlen + len] = '\0'; 
   
    return s; 
  } 
   
  /** 
   *    char     sds    
   */ 
  sds sdscat(sds s, const char *t) 
  { 
    return sdscatlen(s, t, strlen(t)); 
  }