redis 내부 데이터 구조의 SDS 간단 한 동적 문자열 상세 설명

머리말
reids 는 C 언어의 전통 적 인 문자열 표시(빈 문자 로 끝 나 는 문자 배열)를 직접 사용 하지 않 고 간단 한 동적 문자열 이라는 추상 적 인 형식 을 구축 하고 redis 의 기본 문자열 로 표시 합 니 다.C 문자열 은 redis 가 문자열 의 안전성,효율 과 기능 에 대한 수 요 를 만족 시 키 지 못 하기 때 문 입 니 다.
1.SDS 정의
C 언어 에서 문자열 은'\0'문자 끝(NULL 끝 문자)의 문자 배열 로 저 장 됩 니 다.보통 문자 포인터 형식(char*)으로 표 시 됩 니 다.문자열 사이 에 바이트 0 이 나타 나 는 것 을 허용 하지 않 기 때문에 임의의 바 이 너 리 데 이 터 를 저장 할 수 없습니다.
sds 형식 정의

typedef char *sds;

 

  sds.h/sdshdr      SDS   
struct sdshdr{ 
//  buf             
//  sds          
int len; 

//  buf        
int free; 

//    ，        
} 


* free      0,    SDS             
* len      5,    SDS             
* buf      char     ,    5        'R','e','d','i','s'    ,               '\0' 

틀림없이 누군가가 곤 혹 스 러 워 할 것 이다.sds 가 char*와 같다 니?
sds 는 전통 적 인 C 언어 문자열 과 형식 을 호 환 하기 때문에 그들의 유형 정 의 는 똑 같 습 니 다.모두 char*입 니 다.어떤 경우 에는 C 언어 문자열 을 입력 해 야 하 는 곳 도 sds 에 들 어 갈 수 있 습 니 다.
그러나 sds 와 char*는 같 지 않 습 니 다.sds 는 Binary Safe 입 니 다.임의의 바 이 너 리 데 이 터 를 저장 할 수 있 습 니 다.C 언어 문자열 처럼 문자'\0'으로 문자열 의 끝 을 표시 할 수 없 기 때문에 길이 필드 가 있 을 것 입 니 다.이 필드 는 header 에 있 습 니 다.
sds 의 header 구조

/* 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[];
};

SDS 에는 모두 5 가지 유형의 header 가 있다.메모리 절약 이 목적 이다.
메모리 주소 앞 뒤 가 인접 한 두 부분 으로 구 성 된 SDS 문자열 의 전체 구조
4.567917.헤더 하나.보통 문자열 의 길이(len),최대 용량(alloc),flags 를 포함 합 니 다.sdshdr 5 는 다르다4.567917.문자 배열이 문자 배열 의 길 이 는 최대 용량+1 과 같 습 니 다.실제 유효한 문자열 데 이 터 는 길이 가 최대 용량 보다 작 습 니 다.실제 문자열 데이터 다음 에는 사용 되 지 않 은 바이트(일반적으로 바이트 0 으로 채 웁 니 다)입 니 다.메모 리 를 재배 치 하지 않 는 전제 에서 문자열 데 이 터 를 뒤로 제한 적 으로 확장 할 수 있 습 니 다.실제 문자열 데이터 뒤에 ASCII 코드 가 0 인'\0'문자 가 있 습 니 다.이것 은 전통 적 인 C 문자열 과 호 환 하기 위해 서 입 니 다.문자 배열 의 길이 가 최대 용량 보다 1 개의 바이트 가 많은 이 유 는 문자열 의 길이 가 최대 용량 에 이 르 렀 을 때 1 개의 바이트 가 NULL 끝 자 를 저장 하기 위해 서 입 니 다sdshdr 5 를 제외 하고 다른 4 개의 header 구 조 는 모두 3 개의 필드 를 포함한다.

len:문자열 의 실제 길 이 를 표시 합 니 다(NULL 종료 부적 은 포함 되 지 않 습 니 다)

alloc:문자열 의 최대 용량(마지막 불필요 한 바이트 포함 하지 않 음)을 표시 합 니 다

flags:항상 바이트 하 나 를 차지 합 니 다.그 중 가장 낮은 3 개의 bit 는 header 의 유형 을 나타 내 는 데 쓰 인 다각 header 의 유형 정의 에서 우리 가 주의해 야 할 부분 이 몇 가지 있 습 니 다.

각 header 의 정의 에 을 사 용 했 습 니 다.attribute__ ((packed))컴 파 일 러 가 메모리 할당 을 위 한 컴 파 일 러 입 니 다.이 속성 이 없 으 면 컴 파일 러 는 struct 필드 를 최적화 정렬 하여 빈 바이트 를 채 울 수 있 습 니 다.그러면 header 와 sds 의 데이터 부분 이 앞 뒤로 바짝 붙 어 있 는 것 을 보장 할 수 없고 낮은 주소 방향 으로 1 개의 바이트 로 고정 적 으로 이동 하 는 방식 으로 flags 필드 를 가 져 올 수 없습니다

4.567917.각 header 의 정의 에서 마지막 으로 char buf[]가 있 습 니 다.길 이 를 가리 키 지 않 은 문자 배열 임 을 알 수 있 습 니 다.이것 은 C 언어 에서 문자 배열 을 정의 하 는 특수 한 쓰기 입 니 다.유연성 배열(flexible array member)이 라 고 부 르 며 하나의 구조 체 의 마지막 필드 에 만 정의 할 수 있 습 니 다.이것 은 flags 필드 뒤에 문자 배열 이 있 거나 flags 필드 뒤에 바짝 붙 어 있 는 이 문자 배열 이 구조 체 에서 의 오프셋 위 치 를 가리 키 는 표시 역할 만 합 니 다.프로그램 이 헤더 에 분 배 된 메모 리 를 사용 할 때 메모리 공간 을 차지 하지 않 습 니 다.sizeof(struct sdshdr 16)의 값 을 계산 하면 결 과 는 5 바이트 이 고 buf 필드 가 없습니다4.567917.sdshdr 5 는 다른 몇 개의 header 구조 와 달리 alloc 필드 를 포함 하지 않 고 길 이 는 flags 의 높 은 5 비트 로 저장 합 니 다.따라서 문자열 에 남 은 공간 을 할당 할 수 없습니다.문자열 이 동적 성장 이 필요 하 다 면 메모 리 를 다시 할당 해 야 합 니 다.따라서 이러한 유형의 sds 문자열 은 정적 인 짧 은 문자열(길이 가 32 보다 작 음)을 저장 하 는 데 더욱 적합 합 니 다이로써 우 리 는 sds 문자열 의 header 가 실제 문자열 데이터 앞 에 숨겨 져 있 음 을 똑똑히 보 았 다.이러한 정 의 는 다음 과 같은 몇 가지 장점 이 있다.
4.567917.header 는 데이터 와 인접 하여 두 개의 메모리 공간 으로 나 누 어 따로 분배 하지 않 아 도 된다.이것 은 메모리 조각 을 줄 이 고 저장 효율(memory efficiency)을 향상 시 키 는 데 유리 하 다4.567917.header 는 여러 가지 유형 이 있 지만 sds 는 통 일 된 char*로 표현 할 수 있 습 니 다.또한 전통 적 인 C 언어 문자열 과 형식 을 호 환 합 니 다.만약 sds 에 인쇄 가능 한 문자열 이 저장 되 어 있다 면,우 리 는 그것 을 C 함수 에 직접 전달 할 수 있 습 니 다.예 를 들 어 strcmp 를 사용 하여 문자열 의 크기 를 비교 하거나 printf 를 사용 하여 인쇄 할 수 있 습 니 다sds 의 데이터 구 조 를 파악 하면 구체 적 인 조작 함수 가 비교적 이해 하기 쉽다.
sds 의 기초 함수
sdslen(const sds):sds 문자열 길 이 를 가 져 옵 니 다

sdssetlen(sds s, size_t newlen):sds 문자열 길 이 를 설정 합 니 다

sdsinclen(sds s, size_t inc):sds 문자열 길 이 를 늘 립 니 다

sdsalloc(const sds):sds 문자열 용량 가 져 오기.

sdssetalloc(sds s, size_t newlen):sds 문자열 용량 을 설정 합 니 다

sdsavail(const sds):sds 문자열 의 남 은 공간(즉 alloc-len)을 가 져 옵 니 다sdsHdr Size(char type):header 형식 에 따라 header 크기 를 얻 을 수 있 습 니 다

sdsReqType(size_t string_size):문자열 데이터 길이 에 따라 필요 한 header 형식 을 계산 합 니 다

2.SDS 배열 동적 할당 전략
헤더 정보 에서 이렇게 많은 필드 를 정의 하 는데 그 중 하 나 는 문자열 에 대한 유연 한 조작 을 실현 하고 메모리 재배 치 와 회수 작업 을 최소 화 하 는 것 이다.
redis 의 메모리 할당 정책 은 다음 과 같 습 니 다.

SDS 의 len 속성 길이 가 1MB 보다 작 을 때 redis 는 len 과 같은 길이 의 free 공간 을 분배 합 니 다.왜 이렇게 분배 하 는 지 에 대해 서 는 지난번 에 len 길이 의 공간 을 사 용 했 습 니 다.그러면 다음 프로그램 도 len 길이 의 공간 을 사용 할 수 있 기 때문에 redis 는 이렇게 많은 공간 을 미리 분배 합 니 다

그러나 SDS 의 len 속성 길이 가 1MB 이상 이면 프로그램 은 1M 의 미사 용 공간 을 더 분배 합 니 다.이 럴 때 나 는 이런 관성 예측 에 따라 분배 하면 얻 는 것 보다 잃 는 것 이 많다.그래서 redis 는 1MB 를 위험 치 로 설정 하 는 것 이다.위험 치 를 사용 하지 않 은 만큼 내 가 너 에 게 줄 것 이다.지나 면 이 위험 치 는 바로 내 가 너 에 게 임계값 을 줄 수 있 는 것 이다

reids 메모리 회수 정책 은 다음 과 같 습 니 다.
4.567917.redis 의 메모리 재 활용 은 타성 재 활용 을 사용 합 니 다.즉,문자열 을 짧게 만 들 었 습 니 다.그러면 남 은 메모리 공간 은 제 가 먼저 운영 체제 에 돌려 주지 않 고 남 겨 두 겠 습 니 다.만약 에 바로 사용 된다 면 요?짧 은 보유 자원 은 자원 을 충분히 이용 할 수도 있 고 자원 을 낭비 하지 않 을 수도 있다.이것 은 매우 우수한 사상 이다다시 말 하면 redis 가 구현 한 고성능 문자열 의 결 과 는 N 차 문자열 을 조작 할 때 N 차 메모리 재 할당 이 인성 최 악 으로 변 할 때 최대 N 차 재 할당 이 발생 합 니 다.

/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
 void *sh, *newsh;
 size_t avail = sdsavail(s);
 size_t len, newlen;
 char type, oldtype = s[-1] & SDS_TYPE_MASK;
 int hdrlen;
 
 /* Return ASAP if there is enough space left. */
 if (avail >= addlen) return s;
 
 len = sdslen(s);
 sh = (char*)s-sdsHdrSize(oldtype);
 newlen = (len+addlen);
 if (newlen < SDS_MAX_PREALLOC)
 newlen *= 2;
 else
 newlen += SDS_MAX_PREALLOC;
 
 type = sdsReqType(newlen);
 
 /* Don't use type 5: the user is appending to the string and type 5 is
 * not able to remember empty space, so sdsMakeRoomFor() must be called
 * at every appending operation. */
 if (type == SDS_TYPE_5) type = SDS_TYPE_8;
 
 hdrlen = sdsHdrSize(type);
 if (oldtype==type) {
 newsh = s_realloc(sh, hdrlen+newlen+1);
 if (newsh == NULL) return NULL;
 s = (char*)newsh+hdrlen;
 } else {
 /* Since the header size changes, need to move the string forward,
  * and can't use realloc */
 newsh = s_malloc(hdrlen+newlen+1);
 if (newsh == NULL) return NULL;
 memcpy((char*)newsh+hdrlen, s, len+1);
 s_free(sh);
 s = (char*)newsh+hdrlen;
 s[-1] = type;
 sdssetlen(s, len);
 }
 sdssetalloc(s, newlen);
 return s;
}
 
/* Reallocate the sds string so that it has no free space at the end. The
 * contained string remains not altered, but next concatenation operations
 * will require a reallocation.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdsRemoveFreeSpace(sds s) {
 void *sh, *newsh;
 char type, oldtype = s[-1] & SDS_TYPE_MASK;
 int hdrlen;
 size_t len = sdslen(s);
 sh = (char*)s-sdsHdrSize(oldtype);
 
 type = sdsReqType(len);
 hdrlen = sdsHdrSize(type);
 if (oldtype==type) {
 newsh = s_realloc(sh, hdrlen+len+1);
 if (newsh == NULL) return NULL;
 s = (char*)newsh+hdrlen;
 } else {
 newsh = s_malloc(hdrlen+len+1);
 if (newsh == NULL) return NULL;
 memcpy((char*)newsh+hdrlen, s, len+1);
 s_free(sh);
 s = (char*)newsh+hdrlen;
 s[-1] = type;
 sdssetlen(s, len);
 }
 sdssetalloc(s, len);
 return s;
}

3.SDS 의 특징
sds 는 바로 Redis 에서 광범 위 하 게 사용 되 는 문자열 구조 로 Simple Dynamic String 이 라 고 합 니 다.다른 언어 환경 에 나타 난 문자열 에 비해 다음 과 같은 뚜렷 한 특징 을 가지 고 있 습 니 다.
4.567917.동적 확장 메모리.SDS 가 표시 하 는 문자열 의 내용 은 수정 할 수도 있 고 추가 할 수도 있다.많은 언어 에서 문자열 은 mutable 과 immutable 두 가지 로 나 뉘 는데 SDS 는 mutable 형식 에 속한다바 이 너 리 세 이 프(Binary Safe).sds 는 임의의 바 이 너 리 데 이 터 를 저장 할 수 있 습 니 다4.567917.전통 적 인 C 언어 문자열 형식 과 호 환 됩 니 다

미리 분 배 된 공간 은 게 으 르 게 방출 할 수 있 고 메모리 가 부족 할 때 필요 하지 않 은 메모 리 를 줄 일 수 있다

상수 복잡 도 획득 문자열 길이
버퍼 넘 침 방지,경계 검사4.SDS 와 string 의 관 계 를 논 합 니 다.

127.0.0.1:6379> set test test
OK
127.0.0.1:6379> append test " test"
(integer) 9
127.0.0.1:6379> get test
"test test"
127.0.0.1:6379> setbit test 36 1
(integer) 0
127.0.0.1:6379> get test
"test(test"
127.0.0.1:6379> getrange test -5 -1
"(test"

append 작업 은 SDS 의 sdscatlen 을 사용 하여 이 루어 집 니 다

4.567917.setbit 와 getrange 는 키 에 따라 전체 sds 문자열 을 가 져 온 다음 에 문자열 에서 지정 한 부분 을 선택 하거나 수정 합 니 다.SDS 는 문자 배열 이기 때문에 일부분 을 조작 하 는 것 이 쉬 운 것 같 습 니 다그러나 string 은 이러한 조작 을 지원 하 는 것 외 에 저 장 된 값 이 숫자 일 때 incr,decr 등 도 지원 합 니 다.내부 저장 소 는 SDS 가 아 닌 경우 setbit 와 getrange 의 실현 도 다 를 수 있 습 니 다.
총결산
이상 은 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 참고 학습 가치 가 있 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 댓 글 을 남 겨 주 셔 서 저희 에 대한 지지 에 감 사 드 립 니 다.
참고 문장

http://blog.csdn.net/xiejingfa/article/details/50972592

http://blog.csdn.net/acceptedxukai/article/details/17482611

https://segmentfault.com/a/1190000003984537