Redis 에서 scan 명령 에 대한 심도 있 는 설명

머리말
레 디 스 를 잘 아 는 사람들 은 모두 그것 이 단일 스 레 드 라 는 것 을 안다.따라서 시간 복잡 도가 O(N)인 명령 을 사용 할 때 는 매우 신중 해 야 한다.자칫 프로 세 스 가 막 혀 레 디 스 가 멈 출 수도 있다.
때때로,우 리 는 조건 에 부합 되 는 일부 명령 에 대해 조작 을 해 야 한다.예 를 들 어 test 를 삭제 하 는 것 이다.시작 키.그럼 이 키 들 을 어떻게 구 할 수 있 을까요?Redis 2.8 버 전에 서 는 keys 명령 을 사용 하여 필요 한 key 를 정규 에 맞 게 얻 을 수 있 습 니 다.그러나 이 명령 은 두 가지 단점 이 있다.
4.567917.limit 이 없 으 면 조건 에 맞 는 키 를 한꺼번에 가 져 올 수 밖 에 없습니다.결과 가 수백 만 개가 있 으 면'무궁무진'문자열 출력 을 기다 리 는 것 입 니 다

keys 명령 은 알고리즘 을 옮 겨 다 니 는 것 이 고 시간 복잡 도 는 O(N)입 니 다.우리 가 방금 말 한 바 와 같이 이 명령 은 Redis 서비스 가 중단 되 기 쉽다.따라서 우 리 는 가능 한 한 생산 환경 에서 이 명령 을 사용 하 는 것 을 피해 야 한다

수요 와 존 재 를 만족 시 키 기 위해 레 디 스 카 튼 은 어떻게 선택해 야 할 까?이 딜레마 에 직면 하여 Redis 는 2.8 버 전에 서 우리 에 게 해결 방법 인 scan 명령 을 제공 했다.
keys 명령 에 비해 scan 명령 은 두 가지 뚜렷 한 장점 이 있 습 니 다.
4.567917.scan 명령 의 시간 복잡 도 는 O(N)이지 만 여러 번 진행 되 며 스 레 드 를 막 지 않 습 니 다4.567917.scan 명령 은 limit 인 자 를 제공 하여 매번 결 과 를 되 돌려 주 는 최대 항목 수 를 제어 할 수 있 습 니 다이 두 가지 장점 은 우리 가 위의 어 려 운 문 제 를 해결 하 는 데 도움 을 주 었 지만 scan 명령 도 완벽 하지 않 습 니 다.돌아 온 결과 가 중복 되 기 때문에 클 라 이언 트 가 다시 해 야 합 니 다.왜 중복 되 는 지 에 대해 서 는 본문 을 다 본 후에 답 이 있 을 것 이 라 고 믿는다.
scan 명령 의 기본 용법 에 대해 서 는 Redis 명령 의 상세 한 설명 을 참조 할 수 있 습 니 다Keys 라 는 글 에서 SCAN 명령 에 대한 소개
SCAN 명령
SCAN 명령 은 SCAN,SSCAN,HSCAN,ZSCAN 이 있 습 니 다.
SCAN 은 모든 keys 를 다 옮 겨 다 니 는 거 예요.
다른 SCAN 명령 은 SCAN 이 선택 한 집합 입 니 다.
SCAN 명령 은 증분 의 순환 으로 호출 할 때마다 작은 요소 만 되 돌려 줍 니 다.그 러 니까 키 즈 가 명령 한 구덩이 가 없 을 거 야.
SCAN 명령 은 0 부터 옮 겨 다 니 며 0 까지 옮 겨 다 니 는 커서 를 되 돌려 줍 니 다.
오늘 우 리 는 주로 저층 의 구조 와 소스 코드 의 측면 에서 scan 이 어떻게 일 하 는 지 토론 한다.
Redis 의 구조
Redis 는 Hash 표를 밑바닥 으로 사 용 했 는데 그 이 유 는 효율 적 이 고 간단 하기 때문이다.Hash 표 하면 많은 자바 프로그래머 들 의 첫 반응 이 HashMap 이다.맞습니다.Redis 바 텀 key 의 저장 구 조 는 HashMap 과 같은 배열+링크 의 구조 입 니 다.그 중에서 1 차원 의 배열 크기 는 2n(n>=0)이다.매번 확장 수조 의 길 이 를 배로 늘리다.
scan 명령 은 이 1 차원 배열 을 옮 겨 다 니 는 것 입 니 다.돌아 올 때마다 커서 값 도 이 배열 의 색인 입 니 다.limit 매개 변 수 는 몇 개의 배열 의 요 소 를 옮 겨 다 니 는 지 나타 내 고 이 요소 들 을 조건 에 맞 는 결 과 를 되 돌려 줍 니 다.요소 마다 연결 되 어 있 는 링크 의 크기 가 다 르 기 때문에 매번 돌아 오 는 결과 의 수량 도 다르다.
SCAN 의 옮 겨 다 니 는 순서
scan 명령 의 옮 겨 다 니 는 순서 에 대해 서 는 작은 밤 으로 구체 적 으로 볼 수 있 습 니 다.

127.0.0.1:6379> keys *
1) "db_number"
2) "key1"
3) "myKey"
127.0.0.1:6379> scan 0 MATCH * COUNT 1
1) "2"
2) 1) "db_number"
127.0.0.1:6379> scan 2 MATCH * COUNT 1
1) "1"
2) 1) "myKey"
127.0.0.1:6379> scan 1 MATCH * COUNT 1
1) "3"
2) 1) "key1"
127.0.0.1:6379> scan 3 MATCH * COUNT 1
1) "0"
2) (empty list or set)

우리 의 Redis 에는 3 개의 key 가 있 습 니 다.우 리 는 매번 1 차원 배열 의 요소 만 옮 겨 다 닙 니 다.위 와 같이 SCAN 명령 의 반복 순 서 는?
0->2->1->3
이 순 서 는 보기에 좀 이상 하 다.우 리 는 그것 을 2 진법 으로 바 꾸 면 좀 이해 하기 쉽다.
00->10->01->11
우 리 는 매번 이 서열 이 높 은 위치 에 1 을 더 한 것 을 발견 했다.보통 2 진법 의 덧셈 은 오른쪽 에서 왼쪽으로 더 하고 진 하 는 것 이다.이 서열 은 왼쪽 에서 오른쪽으로 더 하고 진 위 된 것 이다.이 점 은 redis 의 소스 코드 에서 도 입증 되 었 다.
dict.c 파일 의 dictScan 함수 에서 커서 를 다음 과 같이 처리 하 였 습 니 다.

v = rev(v);
v++;
v = rev(v);

커서 를 거꾸로 놓 고 하 나 를 더 한 후에 거꾸로 놓 는 것,즉 우리 가 말 하 는'높 은 자리 에 1 을 더 하 는 것'의 조작 이라는 뜻 이다.
정상 적 인 0,1,2...........................................................................
SCAN 이 옮 겨 다 니 는 과정 에서 확장 이 발생 했 을 때 옮 겨 다 니 는 것 이 어떻게 진행 되 는 지 살 펴 보 자.원본 배열 에 4 개의 요 소 를 추가 합 니 다.즉,색인 은 두 자리 가 있 습 니 다.이 때 는 3 자리 로 확장 하고 rehash 를 진행 해 야 합 니 다.

원래 xx 에 연 결 된 모든 요 소 는 0xx 와 1xx 에 분배 되 었 다.위의 그림 에서 10 을 옮 겨 다 닐 때 dict 는 rehash 를 진행 합 니 다.이때 scan 명령 은 010 부터 옮 겨 다 니 며 000 과 100(원래 00 에 걸 려 있 는 요소)은 다시 옮 겨 다 니 지 않 습 니 다.
다시 한 번 축소 상황 을 보 자.dict 가 3 비트 에서 2 비트 로 축소 된다 고 가정 하면 110 을 옮 겨 다 닐 때 dict 가 축소 되 었 습 니 다.이때 scan 은 10 을 옮 겨 다 닙 니 다.이 때 010 에 걸 려 있 는 요 소 는 반복 되 지만 010 이전의 요 소 는 반복 되 지 않 습 니 다.그래서 축 용 할 때 중복 요소 가 나타 날 수 있 습 니 다.
Redis 의 rehash
rehash 는 비교적 복잡 한 과정 으로 Redis 의 프로 세 스 를 막 지 않 기 위해 점진 적 인 rehash 체 제 를 사용 했다.

/*    */
typedef struct dict {
 //       
 dictType *type;
 //     
 void *privdata;
 //    
 dictht ht[2];
 // rehash   
 //   rehash      ，   -1
 int rehashidx; /* rehashing not in progress if rehashidx == -1 */
 //                
 int iterators; /* number of iterators currently running */
} dict;

Redis 의 사전 구조 에는 두 개의 hash 표,새 표,오래된 표 가 있 습 니 다.rehash 과정 에서 redis 는 오래된 표 의 요 소 를 새로운 표 로 옮 겼 습 니 다.다음은 dict 의 rehash 작업 의 소스 코드 를 보 겠 습 니 다.

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
 int empty_visits = n*10; /* Max number of empty buckets to visit. */
 if (!dictIsRehashing(d)) return 0;

 while(n-- && d->ht[0].used != 0) {
 dictEntry *de, *nextde;

 /* Note that rehashidx can't overflow as we are sure there are more
  * elements because ht[0].used != 0 */
 assert(d->ht[0].size > (unsigned long)d->rehashidx);
 while(d->ht[0].table[d->rehashidx] == NULL) {
  d->rehashidx++;
  if (--empty_visits == 0) return 1;
 }
 de = d->ht[0].table[d->rehashidx];
 /* Move all the keys in this bucket from the old to the new hash HT */
 while(de) {
  uint64_t h;

  nextde = de->next;
  /* Get the index in the new hash table */
  h = dictHashKey(d, de->key) & d->ht[1].sizemask;
  de->next = d->ht[1].table[h];
  d->ht[1].table[h] = de;
  d->ht[0].used--;
  d->ht[1].used++;
  de = nextde;
 }
 d->ht[0].table[d->rehashidx] = NULL;
 d->rehashidx++;
 }

 /* Check if we already rehashed the whole table... */
 if (d->ht[0].used == 0) {
 zfree(d->ht[0].table);
 d->ht[0] = d->ht[1];
 _dictReset(&d->ht[1]);
 d->rehashidx = -1;
 return 0;
 }

 /* More to rehash... */
 return 1;
}

주석 을 통 해 rehash 의 과정 은 bucket 을 기본 단위 로 이전 한 다 는 것 을 알 수 있 습 니 다.버 킷 이란 우리 가 앞에서 언급 한 1 차원 배열 의 요소 입 니 다.목록 을 옮 길 때마다다음은 이 코드 를 설명 하 겠 습 니 다.

먼저 rehash 를 진행 하고 있 는 지 여 부 를 판단 하고 만약 에 그렇다면 계속 진행 합 니 다.아니면 그냥 돌아 와.

4.567917.이 어 n 단계 로 나 누 어 점진 적 인 rehash 를 시작 합 니 다.안전성 을 확보 하기 위해 남 은 요소 가 있 는 지 판단 하기 도 한다

rehash 를 진행 하기 전에 이전 할 bucket 이 경 계 를 넘 었 는 지 여 부 를 먼저 판단 합 니 다

그리고 빈 bucket 을 뛰 어 넘 습 니 다.여기 empty 가 있 습 니 다.visits 변 수 는 최대 접근 가능 한 빈 bucket 의 수량 을 표시 합 니 다.이 변 수 는 주로 많은 차단 Redis 를 확보 하기 위해 서 입 니 다

4.567917.다음은 요소 의 이전 입 니 다.현재 bucket 의 모든 요 소 를 rehash 하고 두 장의 표 에 있 는 요소 의 수량 을 업데이트 합 니 다

매번 bucket 을 옮 길 때마다 오래된 표 의 bucket 을 NULL 로 가 리 켜 야 합 니 다

4.567917.마지막 으로 모든 이전 이 완료 되 었 는 지 판단 합 니 다.만약 그렇다면 공간 을 회수 하고 rehash 색인 을 리 셋 합 니 다.그렇지 않 으 면 호출 자 에 게 데이터 가 이전 되 지 않 았 음 을 알려 줍 니 다Redis 는 점진 적 인 rehash 메커니즘 을 사용 하기 때문에 scan 명령 은 새 표 와 오래된 표를 동시에 스 캔 하여 결 과 를 클 라 이언 트 에 되 돌려 야 합 니 다.
총결산
이상 은 이 글 의 전체 내용 입 니 다.본 논문 의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 참고 학습 가치 가 있 기 를 바 랍 니 다.궁금 한 점 이 있 으 시 면 댓 글 을 남 겨 주 셔 서 저희 에 대한 지지 에 감 사 드 립 니 다.