redis 정수 집 이 왜 강등 되 지 않 는 지 에 대해 말씀 드 리 겠 습 니 다.

머리말
정수 집합 은 어떤 학생 들 이 들 어 본 적 이 없다 고 믿 습 니 다.왜냐하면 redis 가 대외 적 으로 제공 하 는 것 은 포장 한 5 대 대상 만 있 기 때 문 입 니 다!우리 시리즈 의 주 지 는 redis 내부 구 조 를 배 우 는 것 이다.내부 구 조 는 redis 5 대 구조의 중요 한 지탱!
앞에서 우 리 는 redis 내부 구조 에서 redis 의 List,Hash,Zset 세 가지 데이터 구 조 를 분석 했다.오늘 우 리 는 set 데이터 구조 내부 가 어떻게 저장 되 었 는 지 분석 할 것 이다.
기본 구조
src/tset.c 에서 우 리 는 이러한 코드 를 발견 했다.

이 를 통 해 우 리 는 set 에서 두 가지 데이터 구조 로 구 성 된 것 을 알 수 있다.hashtable+intset.redis 내부 의 다른 구조 에 대해 저 는 전문 적 으로[redis 칼럼 에 소개 되 어 있 습 니 다.]에 있 습 니 다.hashtable 은 오늘 의 주인공 이 아 닙 니 다.우 리 는 오늘 intset 속칭 정수 집합 을 분석 합 니 다.

위의 그림 에서 알 수 있 듯 이 나 는 두 개의 set 집합 을 구 조 했 는데 각각[comonset],[cs]이다.두 집합 전 자 는 문자열 을 저장 하고 후 자 는 숫자 를 전문 적 으로 저장 합 니 다.
우 리 는object encoding key을 통 해 다음 두 집합 의 바 텀 데이터 구 조 를 살 펴 보 았 는데 하 나 는 hashtable 이 고 하 나 는 intset 인 것 을 발견 했다.이것 또한 우리 위 에서 set 기본 구조 에 대한 설명 을 검증 했다.
redis 에서 대외 적 으로 5 대 유형 을 제공 하 는 것 은 사실상 redis 의 추상 적 인 대상 을 redisobject 라 고 한다.내부 에 우리 redis 내부 의 데이터 구 조 를 비 추 었 습 니 다.

comonset 과 cs 두 개의 집합 이 내부 데이터 구조 에 대해 서 는 대충 이렇게 이해 할 수 있 습 니 다.

intset 사용 시간
너 는 단순히 숫자 라면 intset 구 조 를 사용 하여 저장 할 것 이 라 고 생각 할 수 있다.나 는 아마 너 에 게 한 방 먹 일 것 이다.사실 그렇지 않 아 요.
다음 과 같은 두 가지 조건 을 동시에 만족 시 켜 야 한다.


intset

그림 에서 잘 보 여 주 었 습 니 다.intset 에 있 는 encoding 은 각각 contents 저장 데이터 형식 을 나타 내 는 세 가지 수치 가 있 습 니 다.여기 서 의문 이 들 수도 있어 요.contents 의 유형 은 int8 이 아 닙 니 다.t 요?왜 인 코딩 이 필요 하지?여 기 는 원본 코드 를 통 해 내 부 를 추적 합 니 다.확실히 int8아무 상관 없어 요.그리고 데이터 의 기본 형식 은 int 16 입 니 다.t 。length 에 대해 서 는 설명 이 필요 없습니다.한 가지 만 기억 하 세 요.contents 요 소 를 나타 내 는 개 수 는 contents 배열 의 길 이 를 나타 내 는 것 이 아 닙 니 다!
intset 를 아 는 학생 들 은 모두 encoding 세 가지 수치 범위 에서 업그레이드 작업 과 관련 된 것 을 알 고 있 습 니 다!업 그 레이 드 를 말 하기 전에 C,C+에서 int 의 수치 범위 가 어떻게 정의 되 는 지 알 아 보 겠 습 니 다.
int8_t 의 수치 범 위 는[-128,127]이다.자바 에서 byte 가 1 바이트,즉 8 자 리 를 차지 하 는 것 과 유사 하 다.그의 수치 범 위 는?


요소 추가

sadd juejin -123
sadd juejin -6
sadd juejin 12
sadd juejin 56
sadd juejin 321	

Juejin 이 키 내 부 는 intset 입 니 다.

위 에 우 리 는 5 개의 요 소 를 추 가 했 고 이 5 개의 요소 의 길 이 는 모두 16 안에 있다!그래서 현재 intset 의 encoding=INTSETENC_INT16。-123 은 콘 텐 츠 에서 16 위 를 차지 했다.
그래서 현재 다섯 개의 요소 가 contents 에서 차지 하 는 길 이 는 16*5=80 이다.
set 는 int 형식 데 이 터 를 저장 할 때 내 부 는 작은 것 부터 큰 것 까지 순서대로 저 장 됩 니 다.
유형 변동

위의 문 제 는 네가 고려 해 본 적 이 있 는 지 없 는 지,아니면 만난 적 이 있 는 지 모르겠다.intset 기본 값 은 int 16 비트 입 니 다.위 에 추 가 된 다섯 개의 요소 와 같 습 니 다.이때 우리 가 6 번 째 요 소 를 추가 하 는 것 은 65535(32 위)입 니 다.그러면 이때 16 자리 길이 가 부족 합 니 다.이 럴 때 intset 는 어떻게 합 니까?
또한 우리 가 6 번 째 요 소 를 추가 한 후에 65535 를 삭제 한 후에 구 조 는 추가 하기 전과 같 습 니까?다음은 우리 가 이 두 문 제 를 가지 고 결말 을 알 아 보 자!!
업그레이드
우선 첫 번 째 문제 에 대해 살 펴 보 자.원래 다섯 개의 요 소 는 모두 16 자리 면 만족 할 수 있 는데 이때 추 가 된 65535 는 32 자리 길이 이다.그럼 바로 32 분 을 추가 해서 65535 분 께 나 눠 드릴 수 있 지 않 을까요?
정 답 은 안 될 것 입 니 다.우선 배열 요 소 를 보장 할 수 없 는 크기 순 서 를 직접 추가 하 세 요!그 다음 에 다섯 번 째 가 각각 16 위,여섯 번 째 가 32 위 라면 intset 구조 에서 불필요 한 필드 로 표시 하지 않 습 니 다.해석 할 때 16 위 를 해석 해 야 할 지 32 위 를 해석 해 야 할 지 판단 할 수 없다 는 얘 기다.
redis 는 해석 이 편리 하기 때문에 높 은 길이 로 가입 할 때 전체 콘 텐 츠 를 업그레이드 합 니 다.전체 콘 텐 츠 를 먼저 확대 한 다음 데 이 터 를 다시 채 우 겠 다 는 뜻 이다.

가입
우선 length 에 따라 확장 후 요소 의 개 수 는 6 이 고 각각 32 를 차지 하기 때문에 contents 의 길 이 는 32*6=192 이다.이때 상위 80 위 내용 은 변 하지 않 습 니 다.

이전 데이터 시 프 트
충분 한 공간 을 개척 한 후에 우 리 는 오래된 데 이 터 를 옮 길 수 있 습 니 다.여기 서 우 리 는 원래 배열 의 끝 에서 이동 하기 시 작 했 습 니 다.이동 하기 전에 새로운 배열 에서 의 정렬 위 치 를 명 확 히 해 야 합 니 다.이때 우 리 는 먼저 321 을 비교 하여 새 배열 에서 그의 순위 가 5 위 라 는 것 을 확정 하면 그 는 새로운 콘 텐 츠 중 128~159 구간 을 차지 할 것 이다.

결국 앞의 다섯 개의 원소 가 잘 이동 할 것 이다.

마지막 으로 새로 추 가 된 요 소 를 채 워 넣 습 니 다.업그레이드 가 발생 했 을 때 새로운 요소 의 길이 가 원래 의 길이 보다 크기 때 문 일 것 이다.그럼 그 값 은 새 배열 의 양 끝 에 있 을 겁 니 다.음 수 는 맨 왼쪽 에 있 고,정 수 는 맨 오른쪽 에 있다.

강등
다음은 두 번 째 문제 입 니 다.새로 가입 한 65535 가 redis 를 삭제 하면 어떻게 해 야 합 니까?이 럴 때 요소 의 길 이 는 실제 16 비트 로 만족 할 수 있 지만 이때 encoding 은 32 비트 입 니 다.내 생각 에는 강등 이 이 루어 지고 있 을 거 야!
안 타 깝 게 도 redis 는 없 었 습 니 다.왜 없 는 지 생각해 보 세 요.하면,만약,만약...
왜 강등 을 실현 하지 못 합 니까?
요소 가 현재 길 이 를 초과 하면 업그레이드 작업 이 필요 하 다 는 것 을 쉽게 알 수 있 습 니 다.그러나 우리 가 데 이 터 를 삭제 할 때 우 리 는 강등 이 필요 한 지 여 부 를 어떻게 판단 하 는 지 매우 어렵 습 니 다.우 리 는 남 은 요 소 를 현재 길이 보다 작 게 옮 겨 다 니 며 복잡 도 O(N)를 실현 해 야 합 니 다.이것 이 바로 강등 을 하지 않 는 이유 중의 하나 이다.
당신 은 다시 한 번 훑 어 보 는 것 이 빠르다 고 말 할 수 있 습 니 다.어쨌든 메모리 에 있 습 니 다.그러면 강등 후에 또 업그레이드 상황 이 발생 하면 반복 적 인 업그레이드 가 우리 프로그램의 성능 을 떨 어 뜨 릴 것 이 라 고 생각 한 적 이 있 습 니까?업그레이드 가 필요 하 다 는 것 을 알 고 있 습 니 다.그래서 여기 서 리 디 스 를 낮 추 는 것 은 무시 하 는 전략 입 니 다.
작은 매듭

참고 자료:메모리 업그레이드 최적화 메모리 강등
여기 서 redis 정수 집 이 왜 강등 되 지 않 는 지 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 redis 정수 집 강등 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!